TMeshAABBTree3

Choose your operating system:

Windows

macOS

Linux

Inheritance Hierarchy

ISpatial

IMeshSpatial

TMeshAABBTree3

References

Module

GeometryCore

Header

/Engine/Source/Runtime/GeometryCore/Public/Spatial/MeshAABBTree3.h

Include

#include "Spatial/MeshAABBTree3.h"

Syntax

template<class TriangleMeshType>
class TMeshAABBTree3 : public UE::Geometry::IMeshSpatial

Variables

Name Description

Public variable

TDynamicVector<...

 

BoxCenters

Protected variable

double

 

BoxEps

TODO: move BoxEps to IMeshSpatial::FQueryOptions.

Public variable

TDynamicVector<...

 

BoxExtents

Public variable

TDynamicVector<...

 

BoxToIndex

Storage for Box Nodes.

Protected variable

GetSplitAxisFun...

 

GetSplitAxis

Public variable

TDynamicVector<...

 

IndexList

List of indices for a given Box.

Protected variable

const TriangleM...

 

Mesh

Protected variable

uint64

 

MeshChangeStamp

Public variable

int

 

RootIndex

BoxToIndex[RootIndex] is the root node of the tree.

Protected variable

int

 

TopDownLeafMaxTriCount

Public variable

int

 

TrianglesEnd

IndexList[i] for i < TrianglesEnd is a triangle-index list, otherwise Box-index pair/single.

Constructors

Name Description

Public function

TMeshAABBTree3()

Public function

TMeshAABBTree3

(
    const TriangleMeshType* Source...,
    bool bAutoBuild
)

Functions

Name Description

Public function Static

void

 

AddTriTriIntersectionResult

(
    const FIntrTriangle3Triangle3d& In...,
    int TID_A,
    int TID_B,
    MeshIntersection::FIntersectionsQue...
)

Helper to add a triangle-triangle intersection result from to a intersection result struct

Public function Const

double

 

box_box_distsqr

(
    int iBox,
    const FAxisAlignedBox3d& testBox
)

Public function Const

bool

 

box_box_intersect

(
    int IBox,
    const FAxisAlignedBox3d& TestBox
)

Public function Const

bool

 

box_contains

(
    int IBox,
    const FVector3d& P
)

Public function Const

double

 

box_ray_intersect_t

(
    int IBox,
    const FRay3d& Ray
)

Public function Const

double

 

BoxDistanceSqr

(
    int IBox,
    const FVector3d& V
)

Public function

void

 

Build

(
    const TArray< int32 >& TriangleLis...
)

Public function

void

 

Build()

Public function

void

 

BuildTopDown

(
    bool bSorted,
    TriIndexEnumerable TriangleList,
    int32 NumTriangles
)

Public function

void

 

BuildTopDown

(
    bool bSorted
)

Public function

void

 

BuildTopDown

(
    TArray< int >& Triangles,
    TArray< FVector3d >& Centers,
    int32 NumTriangles
)

Public function Virtual Const

void

 

DoTraversal

(
    FTreeTraversal& Traversal,
    const FQueryOptions& Options
)

Hierarchically descend through the tree Nodes, calling the FTreeTraversal functions at each level

Public function Const

int

 

find_any_intersection

(
    int iBox,
    const FTriangle3d& Triangle,
    const FAxisAlignedBox3d& triBounds,
    TFunctionRef< bool...,
    const FQueryOptions& Options
)

Public function Const

bool

 

find_any_intersection

(
    int iBox,
    const TMeshAABBTree3& OtherTree,
    const TFunction< FVector3d...,
    int oBox,
    int depth,
    TFunctionRef< bool...,
    const FQueryOptions& Options,
    const FQueryOptions& OtherTreeOpti...
)

Public function Const

void

 

find_intersections

(
    int iBox,
    const TMeshAABBTree3& OtherTree,
    const TFunction< FVector3d...,
    int oBox,
    int depth,
    MeshIntersection::FIntersectionsQue...,
    TFunctionRef< bool...,
    const FQueryOptions& Options,
    const FQueryOptions& OtherTreeOpti...
)

Protected function Const

void

 

find_nearest_tri

(
    int IBox,
    const FVector3d& P,
    double& NearestDistSqr,
    int& TID,
    const FQueryOptions& Options
)

Public function Const

void

 

find_nearest_triangles

(
    int iBox,
    TMeshAABBTree3& OtherTree,
    const TFunction< FVector3d...,
    int oBox,
    int depth,
    double& nearest_sqr,
    FIndex2i& nearest_pair,
    const FQueryOptions& Options,
    const FQueryOptions& OtherTreeOpti...
)

Protected function

void

 

find_nearest_vertex

(
    int IBox,
    const FVector3d& P,
    double& NearestDistSqr,
    int& NearestVertexID,
    const FQueryOptions& Options
)

Public function Const

bool

 

find_self_intersections

(
    MeshIntersection::FIntersectionsQue...,
    bool bIgnoreTopoConnected,
    TFunctionRef< bool...,
    const FQueryOptions& Options
)

Public function Const

bool

 

find_self_intersections_acrossboxes

(
    int Box1,
    int Box2,
    MeshIntersection::FIntersectionsQue...,
    bool bIgnoreTopoConnected,
    int depth,
    TFunctionRef< bool...,
    const FQueryOptions& Options
)

Helper for find_self_intersections that checks intersections between triangles from separate boxes

Public function Const

bool

 

find_tri_tri_intersections

(
    int TID_A,
    int IdxRangeStart,
    int IdxRangeEnd,
    MeshIntersection::FIntersectionsQue...,
    bool bIgnoreTopoConnected,
    TFunctionRef< bool...,
    const FQueryOptions& Options
)

Helper for find_self_intersections that intersects a single triangle vs a range of triangles

Public function Virtual Const

MeshIntersec...

 

FindAllIntersections

(
    const TMeshAABBTree3& OtherTree,
    const TFunction< FVector3d...,
    const FQueryOptions& Options,
    const FQueryOptions& OtherTreeOpti...,
    TFunction< bool...
)

Compute all intersections between two meshes.

Public function Virtual Const

MeshIntersec...

 

FindAllSelfIntersections

(
    bool bIgnoreTopoConnected,
    const FQueryOptions& Options,
    TFunction< bool...
)

Compute self intersections on our mesh.

Protected function Const

void

 

FindHitTriangle

(
    int IBox,
    const FRay3d& Ray,
    double& NearestT,
    int& TID,
    FVector3d& BaryCoords,
    const FQueryOptions& Options
)

Public function Virtual Const

FVector3d

 

FindNearestPoint

(
    const FVector3d& Point,
    const FQueryOptions& Options
)

Convenience function that calls FindNearestTriangle and then finds nearest point

Public function Virtual

FIndex2i

 

FindNearestTriangles

(
    TMeshAABBTree3& OtherTree,
    const TFunction< FVector3d...,
    double& Distance,
    const FQueryOptions& Options,
    const FQueryOptions& OtherTreeOpti...
)

Find nearest pair of triangles on this tree with OtherTree, within Options.MaxDistance.

Public function Virtual

int

 

FindNearestVertex

(
    const FVector3d& P,
    double& NearestDistSqr,
    double MaxDist,
    const FQueryOptions& Options
)

Find the Vertex closest to P, and distance to it, within distance MaxDist, or return InvalidID

Public function Const

FAxisAligned...

 

GetBoundingBox()

Get the overall bounding box of the whole tree

Protected function Const

FAxisAligned...

 

GetBox

(
    int iBox,
    const TFunction< FVector3d...
)

Protected function Const

FAxisAligned...

 

GetBox

(
    int IBox
)

Internals - data structures, construction, etc

Protected function Const

FAxisAligned...

 

GetBoxEps

(
    int IBox,
    double Epsilon
)

Public function Const

const Triang...

 

GetMesh()

Public function Const

bool

 

IsValid

(
    bool bAllowUnsafeModifiedMeshQuerie...
)

Protected function Static

GetSplitAxis...

 

MakeDefaultSplitAxisFunc()

Public function

void

 

SetBuildOptions

(
    int32 MaxBoxTriCount,
    GetSplitAxisFunc&& GetSplitAxisIn
)

Public function

void

 

SetMesh

(
    const TriangleMeshType* Source...,
    bool bAutoBuild
)

Public function

void

 

SetTolerance

(
    double Tolerance
)

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

Public function

int

 

SplitTriSetMidpoint

(
    TArray< int >& Triangles,
    TArray< FVector3d >& Centers,
    int IStart,
    int ICount,
    int Depth,
    int MinTriCount,
    FBoxesSet& Tris,
    FBoxesSet& Nodes,
    FAxisAlignedBox3d& Box
)

Protected function Const

bool

 

TestAnyHitTriangle

(
    int IBox,
    const FRay3d& Ray,
    int32& HitTIDOut,
    double MaxDistance,
    const FQueryOptions& Options
)

Public function Virtual Const

bool

 

TestAnyHitTriangle

(
    const FRay3d& Ray,
    const FQueryOptions& Options
)

Public function

void

 

TestCoverage()

1) make sure we can reach every Tri in Mesh through tree (also demo of how to traverse tree...) 2) make sure that Triangles are contained in parent boxes

Public function Virtual Const

bool

 

TestIntersection

(
    const TMeshAABBTree3& OtherTree,
    const TFunction< FVector3d...,
    const FQueryOptions& Options,
    const FQueryOptions& OtherTreeOpti...
)

Returns true if there is any intersection between our mesh and 'other' mesh.

Public function Virtual Const

bool

 

TestIntersection

(
    const TriangleMeshType* TestMe...,
    FAxisAlignedBox3d TestMeshBounds,
    const TFunction< FVector3d...,
    const FQueryOptions& Options
)

Return true if any triangle of TestMesh intersects with our tree.

Public function Virtual Const

bool

 

TestIntersection

(
    const FTriangle3d& Triangle,
    const FQueryOptions& Options
)

Returns true if triangle intersects any triangle of our mesh

Public function Virtual Const

bool

 

TestSelfIntersection

(
    bool bIgnoreTopoConnected,
    const FQueryOptions& Options
)

Public function

double

 

TotalVolume()

Total sum of volumes of all boxes in the tree. Mainly useful to evaluate tree quality.

Protected function Virtual Const

void

 

TreeTraversalImpl

(
    int IBox,
    int Depth,
    FTreeTraversal& Traversal,
    const FQueryOptions& Options
)

Traversal implementation. you can override to customize this if necessary.

Public function Static

bool

 

TriangleIntersection

(
    FIntrTriangle3Triangle3d& Intr
)

Standard tri tri intersection test (with computing intersection geometry)

Public function Static

bool

 

TriangleIntersectionFilter

(
    const FTriangle3d& A,
    const FTriangle3d& B
)

Standard tri tri intersection test (without computing intersection geometry)

Overridden from IMeshSpatial

Name Description

Public function Virtual Const

int

 

FindNearestHitTriangle

(
    const FRay3d& Ray,
    const FQueryOptions& Options
)

Public function Virtual Const

bool

 

FindNearestHitTriangle

(
    const FRay3d& Ray,
    double& NearestT,
    int& TID,
    FVector3d& BaryCoords,
    const FQueryOptions& Options
)

Find nearest triangle from the given ray

Public function Virtual Const

bool

 

FindNearestHitTriangle

(
    const FRay3d& Ray,
    double& NearestT,
    int& TID,
    const FQueryOptions& Options
)

Find nearest triangle from the given ray

Public function Virtual Const

int

 

FindNearestTriangle

(
    const FVector3d& P,
    double& NearestDistSqr,
    const FQueryOptions& Options
)

Find the triangle closest to P, and distance to it, within distance MaxDist, or return InvalidID Use MeshQueries.TriangleDistance() to get more information

Public function Virtual Const

bool

 

SupportsNearestTriangle()

Public function Virtual Const

bool

 

SupportsTriangleRayIntersection()

Overridden from ISpatial

Name Description

Public function Virtual Const

bool

 

IsInside

(
    const FVector3d& Point
)

Public function Virtual Const

bool

 

SupportsPointContainment()

Classes

Name

Description

Public struct

FBoxesSet

Public class

FTreeTraversal

Typedefs

Name

Description

GetSplitAxisFunc

MeshType

Constants

Name

Description

DOUBLE_MAX