A* Pathfinding Project  3.8.2
The A* Pathfinding Project for Unity 3D
 All Classes Namespaces Files Functions Variables Typedefs Enumerations Properties Events Macros Groups Pages
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.
 
void Insert (MeshNode node)
 Inserts a mesh node in the tree.
 
void OnDrawGizmos ()
 
NNInfo Query (Vector3 p, NNConstraint constraint)
 
NNInfo QueryCircle (Vector3 p, float radius, NNConstraint constraint)
 Queries the tree for the best node, searching within a circle around p with the specified radius.
 
NNInfo QueryClosest (Vector3 p, NNConstraint constraint, out float distance)
 Queries the tree for the closest node to p constrained by the NNConstraint.
 
NNInfo QueryClosest (Vector3 p, NNConstraint constraint, ref float distance, NNInfo previous)
 Queries the tree for the closest node to p constrained by the NNConstraint trying to improve an existing solution.
 
NNInfo QueryClosestXZ (Vector3 p, NNConstraint constraint, ref float distance, NNInfo previous)
 Queries the tree for the closest node to p constrained by the NNConstraint trying to improve an existing solution.
 
MeshNode QueryInside (Vector3 p, NNConstraint constraint)
 
void RebuildFrom (MeshNode[] nodes)
 Rebuilds the tree using the specified nodes.
 

Properties

Rect Size [get]
 

Private Member Functions

void EnsureCapacity (int c)
 
int GetBox (MeshNode node)
 
int GetBox (IntRect rect)
 
void OnDrawGizmos (int boxi, int depth)
 
int RebuildFromInternal (MeshNode[] nodes, int from, int to, bool odd)
 
void SearchBox (int boxi, Vector3 p, NNConstraint constraint, ref NNInfo nnInfo)
 
void SearchBoxCircle (int boxi, Vector3 p, float radius, NNConstraint constraint, ref NNInfo nnInfo)
 
void SearchBoxClosest (int boxi, Vector3 p, ref float closestDist, NNConstraint constraint, ref NNInfo nnInfo)
 
void SearchBoxClosestXZ (int boxi, Vector3 p, ref float closestDist, NNConstraint constraint, ref NNInfo nnInfo)
 
MeshNode SearchBoxInside (int boxi, Vector3 p, NNConstraint constraint)
 

Static Private Member Functions

static IntRect ExpandToContain (IntRect r, IntRect r2)
 Returns a new rect which contains both r and r2.
 
static int ExpansionRequired (IntRect r, IntRect r2)
 Returns the difference in area between r and r expanded to contain r2.
 
static IntRect NodeBounds (MeshNode[] nodes, int from, int to)
 Calculates the bounding box in XZ space of all nodes between from (inclusive) and to (exclusive)
 
static bool NodeIntersectsCircle (MeshNode node, Vector3 p, float radius)
 
static int RectArea (IntRect r)
 Returns the area of a rect.
 
static bool RectIntersectsCircle (IntRect r, Vector3 p, float radius)
 Returns true if p is within radius from r.
 
static int SplitByX (MeshNode[] nodes, int from, int to, int divider)
 
static int SplitByZ (MeshNode[] nodes, int from, int to, int divider)
 

Private Attributes

BBTreeBox[] arr = new BBTreeBox[6]
 Holds an Axis Aligned Bounding Box Tree used for faster node lookups.
 
int count
 

Member Function Documentation

void Clear ( )

Clear the tree.

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

void EnsureCapacity ( int  c)
private
static IntRect ExpandToContain ( IntRect  r,
IntRect  r2 
)
staticprivate

Returns a new rect which contains both r and r2.

static int ExpansionRequired ( IntRect  r,
IntRect  r2 
)
staticprivate

Returns the difference in area between r and r expanded to contain r2.

int GetBox ( MeshNode  node)
private
int GetBox ( IntRect  rect)
private
void Insert ( MeshNode  node)

Inserts a mesh node in the tree.

static IntRect NodeBounds ( MeshNode[]  nodes,
int  from,
int  to 
)
staticprivate

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

static bool NodeIntersectsCircle ( MeshNode  node,
Vector3  p,
float  radius 
)
staticprivate
void OnDrawGizmos ( )
void OnDrawGizmos ( int  boxi,
int  depth 
)
private
NNInfo Query ( Vector3  p,
NNConstraint  constraint 
)
NNInfo QueryCircle ( Vector3  p,
float  radius,
NNConstraint  constraint 
)

Queries the tree for the best node, searching within a circle around p with the specified radius.

Will fill in both the constrained node and the not constrained node in the NNInfo.

See Also
QueryClosest
NNInfo 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, unlike QueryCircle, only fill in the constrained node. If you want a node not constrained by any NNConstraint, do an additional search with constraint = NNConstraint.None

See Also
QueryCircle
NNInfo QueryClosest ( Vector3  p,
NNConstraint  constraint,
ref float  distance,
NNInfo  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, unlike QueryCircle, 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.
See Also
QueryCircle
NNInfo QueryClosestXZ ( Vector3  p,
NNConstraint  constraint,
ref float  distance,
NNInfo  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, unlike QueryCircle, 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.
See Also
QueryCircle
MeshNode QueryInside ( Vector3  p,
NNConstraint  constraint 
)
void RebuildFrom ( MeshNode[]  nodes)

Rebuilds the tree using the specified nodes.

This is faster and gives better quality results compared to calling Insert with all nodes

int RebuildFromInternal ( MeshNode[]  nodes,
int  from,
int  to,
bool  odd 
)
private
static int RectArea ( IntRect  r)
staticprivate

Returns the area of a rect.

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.

void SearchBox ( int  boxi,
Vector3  p,
NNConstraint  constraint,
ref NNInfo  nnInfo 
)
private
void SearchBoxCircle ( int  boxi,
Vector3  p,
float  radius,
NNConstraint  constraint,
ref NNInfo  nnInfo 
)
private
void SearchBoxClosest ( int  boxi,
Vector3  p,
ref float  closestDist,
NNConstraint  constraint,
ref NNInfo  nnInfo 
)
private
void SearchBoxClosestXZ ( int  boxi,
Vector3  p,
ref float  closestDist,
NNConstraint  constraint,
ref NNInfo  nnInfo 
)
private
MeshNode SearchBoxInside ( int  boxi,
Vector3  p,
NNConstraint  constraint 
)
private
static int SplitByX ( MeshNode[]  nodes,
int  from,
int  to,
int  divider 
)
staticprivate
static int SplitByZ ( MeshNode[]  nodes,
int  from,
int  to,
int  divider 
)
staticprivate

Member Data Documentation

BBTreeBox [] arr = new BBTreeBox[6]
private

Holds an Axis Aligned Bounding Box Tree used for faster node lookups.

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
int count
private

Property Documentation

Rect Size
get

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