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	OnDrawGizmos ()

NNInfoInternal	QueryClosest (Vector3 p, NNConstraint constraint, out float distance)
	Queries the tree for the closest node to p constrained by the NNConstraint.

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.

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.

TriangleMeshNode	QueryInside (Vector3 p, NNConstraint constraint)
	Searches for a node which contains the specified point.

void	RebuildFrom (TriangleMeshNode[] nodes)
	Rebuilds the tree using the specified nodes.

Public Member Functions inherited from IAstarPooledObject
void	OnEnterPool ()

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.

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)

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.

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.

Private Attributes
int	count

int	leafNodes

const int	MaximumLeafSize = 4

TriangleMeshNode[]	nodeLookup = null

BBTreeBox[]	tree = null
	Holds all tree nodes.

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.

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

staticprivate

static void DrawDebugRect ( IntRect rect )

staticprivate

void EnsureCapacity ( int c )

private

void EnsureNodeCapacity ( int c )

private

int GetBox ( IntRect rect )

private

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.

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)

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

staticprivate

void OnDrawGizmos ( )

void OnDrawGizmos	(	int	boxi,
		int	depth
	)

private

void IAstarPooledObject. OnEnterPool ( )

private

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

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

p	Point to search around
constraint	Optionally set to constrain which nodes to return
distance	The 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.
previous	This 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.

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

p	Point to search around
constraint	Optionally set to constrain which nodes to return
distance	The 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.
previous	This 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.

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

void RebuildFrom ( TriangleMeshNode[] nodes )

Rebuilds the tree using the specified nodes.

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

private

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 SearchBoxClosest	(	int	boxi,
		Vector3	p,
		ref float	closestSqrDist,
		NNConstraint	constraint,
		ref NNInfoInternal	nnInfo
	)

private

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

private

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

private

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

staticprivate

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

staticprivate

static float SquaredRectPointDistance	(	IntRect	r,
		Vector3	p
	)

staticprivate

Returns distance from p to the rectangle r.

Member Data Documentation

int count

private

int leafNodes

private

const int MaximumLeafSize = 4

private

TriangleMeshNode [] nodeLookup = null

private

BBTreeBox [] tree = null

private

Holds all tree nodes.

Property Documentation

Rect Size

get

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

/Users/arong/Unity/a-pathfinding-project/Assets/AstarPathfindingProject/Generators/Utilities/BBTree.cs

Detailed Description

Classes

Public Member Functions

Properties

Private Member Functions

Static Private Member Functions

Private Attributes

Member Function Documentation

Member Data Documentation

Property Documentation