UE::Geometry::FSegmentTree3 Class Reference

#include <SegmentTree3.h>

Classes
struct	FBoxesSet
struct	FRayNearestSegmentInfo
struct	FSegment
struct	FTreeBox

Public Types
using	GetSplitAxisFunc = TUniqueFunction< int(int Depth, const FAxisAlignedBox3d &Box)>

Public Member Functions
template<typename SegmentIDEnumerable , typename GetSegmentFunc >
void	Build (SegmentIDEnumerable Enumerable, GetSegmentFunc GetSegmentForID, int32 NumSegmentsHint=0)
void	Build (const TArray< FSegment3d > &Segments)
bool	FindNearestSegment (const FVector3d &P, FSegment &NearestSegmentOut, const IMeshSpatial::FQueryOptions &Options=IMeshSpatial::FQueryOptions()) const
bool	FindNearestVisibleSegmentHitByRay (const FRay3d &Ray, TFunctionRef< bool(int32, const FVector3d &, const FVector3d &)> WithinToleranceCheck, FSegment &NearestHitSegmentOut, FRayNearestSegmentInfo &NearestInfo, const IMeshSpatial::FQueryOptions &Options=IMeshSpatial::FQueryOptions()) const
void	SetTolerance (double Tolerance)

Protected Member Functions
void	BuildTopDown (TArray< int > &SegmentIndices, TArray< FVector3d > &SegmentCenters, int32 NumSegments)
int	SplitSegmentSetMidpoints (TArray< int > &SegmentIndices, TArray< FVector3d > &SegmentCenters, int StartIdx, int Count, int Depth, int MinSegmentCount, FBoxesSet &SegmentBoxes, FBoxesSet &Nodes, FAxisAlignedBox3d &Box)
double	GetBoxDistanceSqr (int BoxIndex, const FVector3d &V) const
double	GetRayBoxIntersectionParam (int BoxIndex, const FRay3d &Ray, double Radius=0) const
void	FindNearestSegmentInternal (int BoxIndex, const FVector3d &P, double &NearestDistSqr, int &NearSegmentIdx, const IMeshSpatial::FQueryOptions &Options) const
void	FindNearestVisibleSegmentHitByRayInternal (int BoxIndex, const FRay3d &Ray, TFunctionRef< bool(int32, const FVector3d &, const FVector3d &)> WithinToleranceCheck, int &NearSegmentIdx, FRayNearestSegmentInfo &NearestInfo, const IMeshSpatial::FQueryOptions &Options) const

Static Protected Member Functions
static GetSplitAxisFunc	MakeDefaultSplitAxisFunc ()

Protected Attributes
int	TopDownLeafMaxSegmentCount = 8
GetSplitAxisFunc	GetSplitAxis = MakeDefaultSplitAxisFunc()
TArray< FSegment >	SegmentList
TArray< FTreeBox >	TreeBoxes
TArray< int >	IndexList
int	SegmentsEnd = -1
int	RootBoxIndex = -1
double	BoxEps = FMathd::ZeroTolerance

Detailed Description

FSegmentTree3 is a spatial data structure for a set of 3D line segments. The line segments are provided externally, and each segment can have an arbitrary ID. The line segment geometry (ie endpoints) are stored directly by FSegmentTree3, so the class does not hold onto any reference to the source geometry (ie unlike FMeshAABBTree3).

Available queries:

• FindNearestSegment(Point) - finds the nearest segment to the 3D point
• FindNearestVisibleSegmentHitByRay(Ray) - finds the nearest segment that is "hit" by the ray under a tolerance check (see comments below). This is mainly intended for UI hit testing.

Member Typedef Documentation

GetSplitAxisFunc

using UE::Geometry::FSegmentTree3::GetSplitAxisFunc = TUniqueFunction<int(int Depth, const FAxisAlignedBox3d& Box)>

Member Function Documentation

Build() [1/2]

void UE::Geometry::FSegmentTree3::Build ( const TArray< FSegment3d > &  Segments )

inline

Build() [2/2]

template<typename SegmentIDEnumerable , typename GetSegmentFunc >

void UE::Geometry::FSegmentTree3::Build ( SegmentIDEnumerable  Enumerable, GetSegmentFunc  GetSegmentForID, int32  NumSegmentsHint = 0  )

inline

Build the segment tree based on the given Enumerable (ie something that supports a range-based for loop over a set of integer IDs) and a function GetSegmentForID that returns the 3D line segment for a given ID. Gaps/etc are allowed but all enumerated IDs must be valid.

BuildTopDown()

void UE::Geometry::FSegmentTree3::BuildTopDown ( TArray< int > &  SegmentIndices, TArray< FVector3d > &  SegmentCenters, int32  NumSegments  )

inlineprotected

FindNearestSegment()

bool UE::Geometry::FSegmentTree3::FindNearestSegment ( const FVector3d &  P, FSegment &  NearestSegmentOut, const IMeshSpatial::FQueryOptions &  Options = IMeshSpatial::FQueryOptions()  ) const

inline

Find the nearest segment to query point P, and return it in NearestSegmentOut

FindNearestSegmentInternal()

void UE::Geometry::FSegmentTree3::FindNearestSegmentInternal ( int  BoxIndex, const FVector3d &  P, double &  NearestDistSqr, int &  NearSegmentIdx, const IMeshSpatial::FQueryOptions &  Options  ) const

inlineprotected

FindNearestVisibleSegmentHitByRay()

bool UE::Geometry::FSegmentTree3::FindNearestVisibleSegmentHitByRay ( const FRay3d &  Ray, TFunctionRef< bool(int32, const FVector3d &, const FVector3d &)>  WithinToleranceCheck, FSegment &  NearestHitSegmentOut, FRayNearestSegmentInfo &  NearestInfo, const IMeshSpatial::FQueryOptions &  Options = IMeshSpatial::FQueryOptions()  ) const

inline

Find the segment that is hit by a 3D ray under a function WithinToleranceCheck, which will be called with the Ray and Segment points. For example if this is a 3D distance check against a fixed radius, this function essentially raycasts against 3D capsules.

The function compares potential hits (ie that pass the tolerance) with a sort of "distance" metric that tries to balance distance from the ray origin (ie "close to eye") and distance from the hit segment (ie "on the line"). There is no correct way to do this, currently the code uses a metric based on the opening angle between ray and segment points.

FindNearestVisibleSegmentHitByRayInternal()

void UE::Geometry::FSegmentTree3::FindNearestVisibleSegmentHitByRayInternal ( int  BoxIndex, const FRay3d &  Ray, TFunctionRef< bool(int32, const FVector3d &, const FVector3d &)>  WithinToleranceCheck, int &  NearSegmentIdx, FRayNearestSegmentInfo &  NearestInfo, const IMeshSpatial::FQueryOptions &  Options  ) const

inlineprotected

GetBoxDistanceSqr()

double UE::Geometry::FSegmentTree3::GetBoxDistanceSqr ( int  BoxIndex, const FVector3d &  V  ) const

inlineprotected

GetRayBoxIntersectionParam()

double UE::Geometry::FSegmentTree3::GetRayBoxIntersectionParam ( int  BoxIndex, const FRay3d &  Ray, double  Radius = 0  ) const

inlineprotected

MakeDefaultSplitAxisFunc()

static GetSplitAxisFunc UE::Geometry::FSegmentTree3::MakeDefaultSplitAxisFunc ( )

inlinestaticprotected

SetTolerance()

void UE::Geometry::FSegmentTree3::SetTolerance ( double  Tolerance )

inline

Sets the box intersection tolerance TODO: move into the IMeshSpatial::FQueryOptions and delete this function

SplitSegmentSetMidpoints()

int UE::Geometry::FSegmentTree3::SplitSegmentSetMidpoints ( TArray< int > &  SegmentIndices, TArray< FVector3d > &  SegmentCenters, int  StartIdx, int  Count, int  Depth, int  MinSegmentCount, FBoxesSet &  SegmentBoxes, FBoxesSet &  Nodes, FAxisAlignedBox3d &  Box  )

inlineprotected

Member Data Documentation

BoxEps

double UE::Geometry::FSegmentTree3::BoxEps = FMathd::ZeroTolerance

protected

GetSplitAxis

GetSplitAxisFunc UE::Geometry::FSegmentTree3::GetSplitAxis = MakeDefaultSplitAxisFunc()

protected

IndexList

TArray<int> UE::Geometry::FSegmentTree3::IndexList

protected

RootBoxIndex

int UE::Geometry::FSegmentTree3::RootBoxIndex = -1

protected

SegmentList

TArray<FSegment> UE::Geometry::FSegmentTree3::SegmentList

protected

SegmentsEnd

int UE::Geometry::FSegmentTree3::SegmentsEnd = -1

protected

TopDownLeafMaxSegmentCount

int UE::Geometry::FSegmentTree3::TopDownLeafMaxSegmentCount = 8

protected

TreeBoxes

TArray<FTreeBox> UE::Geometry::FSegmentTree3::TreeBoxes

protected

---

The documentation for this class was generated from the following file:

• Engine/Source/Runtime/GeometryCore/Public/Spatial/SegmentTree3.h