A* Pathfinding Project  4.1.12
The A* Pathfinding Project for Unity 3D
Classes | Public Member Functions | Properties | Private Member Functions | Static Private Member Functions | Private Attributes | List of all members
BBTree Class Reference

Axis Aligned Bounding Box Tree. More...

Detailed Description

Axis Aligned Bounding Box Tree.

Holds a bounding box tree of triangles.

A* Pro Feature:
This is an A* Pathfinding Project Pro feature only. This function/class/variable might not exist in the Free version of the A* Pathfinding Project or the functionality might be limited
The Pro version can be bought here

Classes

struct  BBTreeBox
 

Public Member Functions

void Clear ()
 Clear the tree. More...
 
void OnDrawGizmos ()
 
NNInfoInternal QueryClosest (Vector3 p, NNConstraint constraint, out float distance)
 Queries the tree for the closest node to p constrained by the NNConstraint. More...
 
NNInfoInternal QueryClosest (Vector3 p, NNConstraint constraint, ref float distance, NNInfoInternal previous)
 Queries the tree for the closest node to p constrained by the NNConstraint trying to improve an existing solution. More...
 
NNInfoInternal QueryClosestXZ (Vector3 p, NNConstraint constraint, ref float distance, NNInfoInternal previous)
 Queries the tree for the closest node to p constrained by the NNConstraint trying to improve an existing solution. More...
 
TriangleMeshNode QueryInside (Vector3 p, NNConstraint constraint)
 Searches for a node which contains the specified point. More...
 
void RebuildFrom (TriangleMeshNode[] nodes)
 Rebuilds the tree using the specified nodes. More...
 

Properties

Rect Size [get]
 

Private Member Functions

void EnsureCapacity (int c)
 
void EnsureNodeCapacity (int c)
 
int GetBox (IntRect rect)
 
void GetOrderedChildren (ref int first, ref int second, out float firstDist, out float secondDist, Vector3 p)
 Orders the box indices first and second by the approximate distance to the point p. More...
 
void OnDrawGizmos (int boxi, int depth)
 
void IAstarPooledObject. OnEnterPool ()
 
int RebuildFromInternal (TriangleMeshNode[] nodes, int[] permutation, IntRect[] nodeBounds, int from, int to, bool odd)
 
void SearchBoxClosest (int boxi, Vector3 p, ref float closestSqrDist, NNConstraint constraint, ref NNInfoInternal nnInfo)
 
void SearchBoxClosestXZ (int boxi, Vector3 p, ref float closestSqrDist, NNConstraint constraint, ref NNInfoInternal nnInfo)
 
TriangleMeshNode SearchBoxInside (int boxi, Vector3 p, NNConstraint constraint)
 

Static Private Member Functions

static void DrawDebugNode (TriangleMeshNode node, float yoffset, Color color)
 
static void DrawDebugRect (IntRect rect)
 
static IntRect NodeBounds (int[] permutation, IntRect[] nodeBounds, int from, int to)
 Calculates the bounding box in XZ space of all nodes between from (inclusive) and to (exclusive) More...
 
static bool NodeIntersectsCircle (TriangleMeshNode node, Vector3 p, float radius)
 
static bool RectIntersectsCircle (IntRect r, Vector3 p, float radius)
 Returns true if p is within radius from r. More...
 
static int SplitByX (TriangleMeshNode[] nodes, int[] permutation, int from, int to, int divider)
 
static int SplitByZ (TriangleMeshNode[] nodes, int[] permutation, int from, int to, int divider)
 
static float SquaredRectPointDistance (IntRect r, Vector3 p)
 Returns distance from p to the rectangle r. More...
 

Private Attributes

int count
 
int leafNodes
 
const int MaximumLeafSize = 4
 
TriangleMeshNode [] nodeLookup = null
 
BBTreeBox [] tree = null
 Holds all tree nodes. More...
 

Member Function Documentation

◆ Clear()

void Clear ( )

Clear the tree.

Note that references to old nodes will still be intact so the GC cannot immediately collect them.

◆ DrawDebugNode()

static void DrawDebugNode ( TriangleMeshNode  node,
float  yoffset,
Color  color 
)
staticprivate

◆ DrawDebugRect()

static void DrawDebugRect ( IntRect  rect)
staticprivate

◆ EnsureCapacity()

void EnsureCapacity ( int  c)
private

◆ EnsureNodeCapacity()

void EnsureNodeCapacity ( int  c)
private

◆ GetBox()

int GetBox ( IntRect  rect)
private

◆ GetOrderedChildren()

void GetOrderedChildren ( ref int  first,
ref int  second,
out float  firstDist,
out float  secondDist,
Vector3  p 
)
private

Orders the box indices first and second by the approximate distance to the point p.

◆ NodeBounds()

static IntRect NodeBounds ( int []  permutation,
IntRect []  nodeBounds,
int  from,
int  to 
)
staticprivate

Calculates the bounding box in XZ space of all nodes between from (inclusive) and to (exclusive)

◆ NodeIntersectsCircle()

static bool NodeIntersectsCircle ( TriangleMeshNode  node,
Vector3  p,
float  radius 
)
staticprivate

◆ OnDrawGizmos() [1/2]

void OnDrawGizmos ( )

◆ OnDrawGizmos() [2/2]

void OnDrawGizmos ( int  boxi,
int  depth 
)
private

◆ OnEnterPool()

void IAstarPooledObject. OnEnterPool ( )
private

Implements IAstarPooledObject.

◆ QueryClosest() [1/2]

NNInfoInternal QueryClosest ( Vector3  p,
NNConstraint  constraint,
out float  distance 
)

Queries the tree for the closest node to p constrained by the NNConstraint.

Note that this function will only fill in the constrained node. If you want a node not constrained by any NNConstraint, do an additional search with constraint = NNConstraint.None

◆ QueryClosest() [2/2]

NNInfoInternal QueryClosest ( Vector3  p,
NNConstraint  constraint,
ref float  distance,
NNInfoInternal  previous 
)

Queries the tree for the closest node to p constrained by the NNConstraint trying to improve an existing solution.

Note that this function will only fill in the constrained node. If you want a node not constrained by any NNConstraint, do an additional search with constraint = NNConstraint.None

Parameters
pPoint to search around
constraintOptionally set to constrain which nodes to return
distanceThe best distance for the previous solution. Will be updated with the best distance after this search. Will be positive infinity if no node could be found. Set to positive infinity if there was no previous solution.
previousThis search will start from the previous NNInfo and improve it if possible. Even if the search fails on this call, the solution will never be worse than previous.

◆ QueryClosestXZ()

NNInfoInternal QueryClosestXZ ( Vector3  p,
NNConstraint  constraint,
ref float  distance,
NNInfoInternal  previous 
)

Queries the tree for the closest node to p constrained by the NNConstraint trying to improve an existing solution.

Note that this function will only fill in the constrained node. If you want a node not constrained by any NNConstraint, do an additional search with constraint = NNConstraint.None

This method will completely ignore any Y-axis differences in positions.

Parameters
pPoint to search around
constraintOptionally set to constrain which nodes to return
distanceThe best distance for the previous solution. Will be updated with the best distance after this search. Will be positive infinity if no node could be found. Set to positive infinity if there was no previous solution.
previousThis search will start from the previous NNInfo and improve it if possible. Even if the search fails on this call, the solution will never be worse than previous. Note that the distance parameter need to be configured with the distance for the previous result otherwise it may get overwritten even though it was actually closer.

◆ QueryInside()

TriangleMeshNode QueryInside ( Vector3  p,
NNConstraint  constraint 
)

Searches for a node which contains the specified point.

If there are multiple nodes that contain the point any one of them may be returned.

See also
TriangleMeshNode.ContainsPoint

◆ RebuildFrom()

void RebuildFrom ( TriangleMeshNode []  nodes)

Rebuilds the tree using the specified nodes.

◆ RebuildFromInternal()

int RebuildFromInternal ( TriangleMeshNode []  nodes,
int []  permutation,
IntRect []  nodeBounds,
int  from,
int  to,
bool  odd 
)
private

◆ RectIntersectsCircle()

static bool RectIntersectsCircle ( IntRect  r,
Vector3  p,
float  radius 
)
staticprivate

Returns true if p is within radius from r.

Correctly handles cases where radius is positive infinity.

◆ SearchBoxClosest()

void SearchBoxClosest ( int  boxi,
Vector3  p,
ref float  closestSqrDist,
NNConstraint  constraint,
ref NNInfoInternal  nnInfo 
)
private

◆ SearchBoxClosestXZ()

void SearchBoxClosestXZ ( int  boxi,
Vector3  p,
ref float  closestSqrDist,
NNConstraint  constraint,
ref NNInfoInternal  nnInfo 
)
private

◆ SearchBoxInside()

TriangleMeshNode SearchBoxInside ( int  boxi,
Vector3  p,
NNConstraint  constraint 
)
private

◆ SplitByX()

static int SplitByX ( TriangleMeshNode []  nodes,
int []  permutation,
int  from,
int  to,
int  divider 
)
staticprivate

◆ SplitByZ()

static int SplitByZ ( TriangleMeshNode []  nodes,
int []  permutation,
int  from,
int  to,
int  divider 
)
staticprivate

◆ SquaredRectPointDistance()

static float SquaredRectPointDistance ( IntRect  r,
Vector3  p 
)
staticprivate

Returns distance from p to the rectangle r.

Member Data Documentation

◆ count

int count
private

◆ leafNodes

int leafNodes
private

◆ MaximumLeafSize

const int MaximumLeafSize = 4
private

◆ nodeLookup

TriangleMeshNode [] nodeLookup = null
private

◆ tree

BBTreeBox [] tree = null
private

Holds all tree nodes.

Property Documentation

◆ Size

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