QuadTree Class Reference

#include <QuadTree.h>

Inheritance diagram for QuadTree:

Classes
struct	AddState
	Temporary data structure to pass information between AddBodiesPrepare and AddBodiesFinalize/Abort. More...
struct	Tracking
	Data to track location of a Body in the tree. More...
struct	UpdateState

Public Types
using	Allocator = FixedSizeFreeList<Node>
	Class that allocates tree nodes, can be shared between multiple trees.
using	TrackingVector = Array<Tracking>

Public Member Functions
	~QuadTree ()
	Destructor.
void	SetName (const char *inName)
	Name of the tree for debugging purposes.
const char *	GetName () const
bool	HasBodies () const
	Check if there is anything in the tree.
bool	IsDirty () const
	Check if the tree needs an UpdatePrepare/Finalize()
bool	CanBeUpdated () const
	Check if this tree can get an UpdatePrepare/Finalize() or if it needs a DiscardOldTree() first.
void	Init (Allocator &inAllocator)
	Initialization.
void	DiscardOldTree ()
	Will throw away the previous frame's nodes so that we can start building a new tree in the background.
AABox	GetBounds () const
	Get the bounding box for this tree.
void	UpdatePrepare (const BodyVector &inBodies, TrackingVector &ioTracking, UpdateState &outUpdateState, bool inFullRebuild)
void	UpdateFinalize (const BodyVector &inBodies, const TrackingVector &inTracking, const UpdateState &inUpdateState)
void	AddBodiesPrepare (const BodyVector &inBodies, TrackingVector &ioTracking, BodyID *ioBodyIDs, int inNumber, AddState &outState)
void	AddBodiesFinalize (TrackingVector &ioTracking, int inNumberBodies, const AddState &inState)
	Finalize adding bodies to the quadtree, supply the same number of bodies as in AddBodiesPrepare.
void	AddBodiesAbort (TrackingVector &ioTracking, const AddState &inState)
void	RemoveBodies (const BodyVector &inBodies, TrackingVector &ioTracking, const BodyID *ioBodyIDs, int inNumber)
	Remove inNumber bodies in ioBodyIDs from the quadtree.
void	NotifyBodiesAABBChanged (const BodyVector &inBodies, const TrackingVector &inTracking, const BodyID *ioBodyIDs, int inNumber)
	Call whenever the aabb of a body changes.
void	CastRay (const RayCast &inRay, RayCastBodyCollector &ioCollector, const ObjectLayerFilter &inObjectLayerFilter, const TrackingVector &inTracking) const
	Cast a ray and get the intersecting bodies in ioCollector.
void	CollideAABox (const AABox &inBox, CollideShapeBodyCollector &ioCollector, const ObjectLayerFilter &inObjectLayerFilter, const TrackingVector &inTracking) const
	Get bodies intersecting with inBox in ioCollector.
void	CollideSphere (Vec3Arg inCenter, float inRadius, CollideShapeBodyCollector &ioCollector, const ObjectLayerFilter &inObjectLayerFilter, const TrackingVector &inTracking) const
	Get bodies intersecting with a sphere in ioCollector.
void	CollidePoint (Vec3Arg inPoint, CollideShapeBodyCollector &ioCollector, const ObjectLayerFilter &inObjectLayerFilter, const TrackingVector &inTracking) const
	Get bodies intersecting with a point and any hits to ioCollector.
void	CollideOrientedBox (const OrientedBox &inBox, CollideShapeBodyCollector &ioCollector, const ObjectLayerFilter &inObjectLayerFilter, const TrackingVector &inTracking) const
	Get bodies intersecting with an oriented box and any hits to ioCollector.
void	CastAABox (const AABoxCast &inBox, CastShapeBodyCollector &ioCollector, const ObjectLayerFilter &inObjectLayerFilter, const TrackingVector &inTracking) const
	Cast a box and get intersecting bodies in ioCollector.
void	FindCollidingPairs (const BodyVector &inBodies, const BodyID *inActiveBodies, int inNumActiveBodies, float inSpeculativeContactDistance, BodyPairCollector &ioPairCollector, const ObjectLayerPairFilter &inObjectLayerPairFilter) const
	Find all colliding pairs between dynamic bodies, calls ioPairCollector for every pair found.
Public Member Functions inherited from NonCopyable
	NonCopyable ()=default
	NonCopyable (const NonCopyable &)=delete
void	operator= (const NonCopyable &)=delete

Detailed Description

Internal tree structure in broadphase, is essentially a quad AABB tree. Tree is lockless (except for UpdatePrepare/Finalize() function), modifying objects in the tree will widen the aabbs of parent nodes to make the node fit. During the UpdatePrepare/Finalize() call the tree is rebuilt to achieve a tight fit again.

Member Typedef Documentation

Allocator

using QuadTree::Allocator = FixedSizeFreeList<Node>

Class that allocates tree nodes, can be shared between multiple trees.

TrackingVector

using QuadTree::TrackingVector = Array<Tracking>

Constructor & Destructor Documentation

~QuadTree()

QuadTree::~QuadTree

(

)

Destructor.

Member Function Documentation

AddBodiesAbort()

void QuadTree::AddBodiesAbort	(	TrackingVector &	ioTracking,
		const AddState &	inState )

Abort adding bodies to the quadtree, supply the same bodies and state as in AddBodiesPrepare. This can be done on a background thread without influencing the broadphase.

AddBodiesFinalize()

void QuadTree::AddBodiesFinalize	(	TrackingVector &	ioTracking,
		int	inNumberBodies,
		const AddState &	inState )

Finalize adding bodies to the quadtree, supply the same number of bodies as in AddBodiesPrepare.

AddBodiesPrepare()

void QuadTree::AddBodiesPrepare	(	const BodyVector &	inBodies,
		TrackingVector &	ioTracking,
		BodyID *	ioBodyIDs,
		int	inNumber,
		AddState &	outState )

Prepare adding inNumber bodies at ioBodyIDs to the quad tree, returns the state in outState that should be used in AddBodiesFinalize. This can be done on a background thread without influencing the broadphase. ioBodyIDs may be shuffled around by this function.

CanBeUpdated()

bool QuadTree::CanBeUpdated ( ) const

inline

Check if this tree can get an UpdatePrepare/Finalize() or if it needs a DiscardOldTree() first.

CastAABox()

void QuadTree::CastAABox	(	const AABoxCast &	inBox,
		CastShapeBodyCollector &	ioCollector,
		const ObjectLayerFilter &	inObjectLayerFilter,
		const TrackingVector &	inTracking ) const

Cast a box and get intersecting bodies in ioCollector.

Constructor

Returns true if further processing of the tree should be aborted

Returns true if this node / body should be visited, false if no hit can be generated

Visit nodes, returns number of hits found and sorts ioChildNodeIDs so that they are at the beginning of the vector.

Visit a body, returns false if the algorithm should terminate because no hits can be generated anymore

CastRay()

void QuadTree::CastRay	(	const RayCast &	inRay,
		RayCastBodyCollector &	ioCollector,
		const ObjectLayerFilter &	inObjectLayerFilter,
		const TrackingVector &	inTracking ) const

Cast a ray and get the intersecting bodies in ioCollector.

Constructor

Returns true if further processing of the tree should be aborted

Returns true if this node / body should be visited, false if no hit can be generated

Visit nodes, returns number of hits found and sorts ioChildNodeIDs so that they are at the beginning of the vector.

Visit a body, returns false if the algorithm should terminate because no hits can be generated anymore

CollideAABox()

void QuadTree::CollideAABox	(	const AABox &	inBox,
		CollideShapeBodyCollector &	ioCollector,
		const ObjectLayerFilter &	inObjectLayerFilter,
		const TrackingVector &	inTracking ) const

Get bodies intersecting with inBox in ioCollector.

Constructor

Returns true if further processing of the tree should be aborted

Returns true if this node / body should be visited, false if no hit can be generated

Visit nodes, returns number of hits found and sorts ioChildNodeIDs so that they are at the beginning of the vector.

Visit a body, returns false if the algorithm should terminate because no hits can be generated anymore

CollideOrientedBox()

void QuadTree::CollideOrientedBox	(	const OrientedBox &	inBox,
		CollideShapeBodyCollector &	ioCollector,
		const ObjectLayerFilter &	inObjectLayerFilter,
		const TrackingVector &	inTracking ) const

Get bodies intersecting with an oriented box and any hits to ioCollector.

Constructor

Returns true if further processing of the tree should be aborted

Returns true if this node / body should be visited, false if no hit can be generated

Visit nodes, returns number of hits found and sorts ioChildNodeIDs so that they are at the beginning of the vector.

Visit a body, returns false if the algorithm should terminate because no hits can be generated anymore

CollidePoint()

void QuadTree::CollidePoint	(	Vec3Arg	inPoint,
		CollideShapeBodyCollector &	ioCollector,
		const ObjectLayerFilter &	inObjectLayerFilter,
		const TrackingVector &	inTracking ) const

Get bodies intersecting with a point and any hits to ioCollector.

Constructor

Returns true if further processing of the tree should be aborted

Returns true if this node / body should be visited, false if no hit can be generated

Visit nodes, returns number of hits found and sorts ioChildNodeIDs so that they are at the beginning of the vector.

Visit a body, returns false if the algorithm should terminate because no hits can be generated anymore

CollideSphere()

void QuadTree::CollideSphere	(	Vec3Arg	inCenter,
		float	inRadius,
		CollideShapeBodyCollector &	ioCollector,
		const ObjectLayerFilter &	inObjectLayerFilter,
		const TrackingVector &	inTracking ) const

Get bodies intersecting with a sphere in ioCollector.

Constructor

Returns true if further processing of the tree should be aborted

Returns true if this node / body should be visited, false if no hit can be generated

Visit nodes, returns number of hits found and sorts ioChildNodeIDs so that they are at the beginning of the vector.

Visit a body, returns false if the algorithm should terminate because no hits can be generated anymore

DiscardOldTree()

void QuadTree::DiscardOldTree

(

)

Will throw away the previous frame's nodes so that we can start building a new tree in the background.

FindCollidingPairs()

void QuadTree::FindCollidingPairs	(	const BodyVector &	inBodies,
		const BodyID *	inActiveBodies,
		int	inNumActiveBodies,
		float	inSpeculativeContactDistance,
		BodyPairCollector &	ioPairCollector,
		const ObjectLayerPairFilter &	inObjectLayerPairFilter ) const

Find all colliding pairs between dynamic bodies, calls ioPairCollector for every pair found.

GetBounds()

AABox QuadTree::GetBounds

(

)

const

Get the bounding box for this tree.

GetName()

const char * QuadTree::GetName ( ) const

inline

HasBodies()

bool QuadTree::HasBodies ( ) const

inline

Check if there is anything in the tree.

Init()

void QuadTree::Init

(

Allocator &

inAllocator

)

Initialization.

IsDirty()

bool QuadTree::IsDirty ( ) const

inline

Check if the tree needs an UpdatePrepare/Finalize()

NotifyBodiesAABBChanged()

void QuadTree::NotifyBodiesAABBChanged	(	const BodyVector &	inBodies,
		const TrackingVector &	inTracking,
		const BodyID *	ioBodyIDs,
		int	inNumber )

Call whenever the aabb of a body changes.

RemoveBodies()

void QuadTree::RemoveBodies	(	const BodyVector &	inBodies,
		TrackingVector &	ioTracking,
		const BodyID *	ioBodyIDs,
		int	inNumber )

Remove inNumber bodies in ioBodyIDs from the quadtree.

SetName()

void QuadTree::SetName ( const char * inName )

inline

Name of the tree for debugging purposes.

UpdateFinalize()

void QuadTree::UpdateFinalize	(	const BodyVector &	inBodies,
		const TrackingVector &	inTracking,
		const UpdateState &	inUpdateState )

UpdatePrepare()

void QuadTree::UpdatePrepare	(	const BodyVector &	inBodies,
		TrackingVector &	ioTracking,
		UpdateState &	outUpdateState,
		bool	inFullRebuild )

Update the broadphase, needs to be called regularly to achieve a tight fit of the tree when bodies have been modified. UpdatePrepare() will build the tree, UpdateFinalize() will lock the root of the tree shortly and swap the trees and afterwards clean up temporary data structures.

---

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

• Jolt/Physics/Collision/BroadPhase/QuadTree.h
• Jolt/Physics/Collision/BroadPhase/QuadTree.cpp