CQuadTree Class Reference

A quadtree. More...

#include <QuadTree.h>

Collaboration diagram for CQuadTree:

Public Member Functions
	~CQuadTree ()
	Destructor.
void	Initialize (const UINT, const Shapes::CAabb2D &)
	Initialize for a given depth and area.
void	Clear ()
	Clear dynamic and kinematic shape lists in all nodes.
void	Insert (Shapes::CShape *)
	Insert shape.
void	GetLeaves (std::vector< CQuadTreeLeaf * > &) const
	Get leaves with collidable things in them.
const UINT	GetNodeCount () const
	Get number of nodes.
const UINT	GetLeafCount () const
	Get number of leaves.
Vector2	GetLeafArea () const
	Get width and height of area covered by a leaf.
const UINT	GetMaxLeafSize () const
	Get maximum number of shapes in a leaf.
const UINT	GetDepth () const
	Get depth.

Private Member Functions
void	InitAABBs (const Shapes::CAabb2D &)
	Initialize AABBs in all nodes.
void	Insert (Shapes::CShape *, UINT)
	Insert shape at place in tree.
void	GetLeaves (std::vector< CQuadTreeLeaf * > &, UINT) const
	Get leaves with collidable things in them.

Private Attributes
CQuadTreeNode **	m_pTree = nullptr
	Pointer to root.
UINT	m_nDepth = 0
	Depth.
UINT	m_nNumNodes = 0
	Number of nodes.
UINT	m_nFirstLeaf = 0
	Index of first leaf.

Detailed Description

A quadtree is a space dividing data structure used here for collision detection. It is a complete tree of degree four in which the root represents the whole of the game world and each child represents a quadrant of the rectangle represented by its parent. It should ideally have a depth that is deep enough for there to be only a small number of balls in each leaf, but not so deep that the extra time spend traversing the quadtree exceeds any benefit gained from the decrease in the number of narrow phase collision detection calls made.

Member Function Documentation

Clear()

void CQuadTree::Clear

(

)

Clear the kinematic and dynamic shapes out of the quadtree. This includes zeroing out the kinematic and dynamic shape counts at the nodes and the kinematic and dynamic shape lists at the leaves.

Here is the caller graph for this function:

GetDepth()

const UINT CQuadTree::GetDepth

(

)

const

Reader function for the quadtree depth.

Returns

Depth of quadtree.

Here is the caller graph for this function:

GetLeafArea()

Vector2 CQuadTree::GetLeafArea

(

)

const

Reader function for the area covered by each quadtree leaf. Actually, we need only query the first leaf since all leaves have the same area.

Returns

A Vector2 containing the width and height of a quadtree leaf's area.

Here is the caller graph for this function:

GetLeafCount()

const UINT CQuadTree::GetLeafCount

(

)

const

Reader function for the number of leaves.

Returns

Number of leaves in quadtree.

Here is the caller graph for this function:

GetLeaves() [1/2]

void CQuadTree::GetLeaves

(

std::vector< CQuadTreeLeaf * > &

v

)

const

Assemble a vector of leaves that have dynamic shapes in them.

Parameters

v	[OUT] Vector of pointers to leaves with collidable dynamic shapes in them.

Here is the call graph for this function:

GetLeaves() [2/2]

void CQuadTree::GetLeaves ( std::vector< CQuadTreeLeaf * > & v, UINT i ) const

private

Assemble a vector of leaves that are descendants of a given node and have dynamic shapes in them.

Parameters

v	[OUT] Vector of pointers to leaves with collidable dynamic shapes in them.
i	Index of node whose descendants we are to search.

Here is the call graph for this function:

Here is the caller graph for this function:

GetMaxLeafSize()

const UINT CQuadTree::GetMaxLeafSize

(

)

const

The size of a leaf here means the number of shapes in it.

Returns

The number of shapes in the leaf with the most shapes.

Here is the caller graph for this function:

GetNodeCount()

const UINT CQuadTree::GetNodeCount

(

)

const

Reader function for the number of nodes.

Returns

Number of nodes in quadtree.

Here is the caller graph for this function:

InitAABBs()

void CQuadTree::InitAABBs ( const Shapes::CAabb2D & a )

private

Initialize the AABBs in all of the nodes.

Parameters

a	AABB for the entirety of Physics World.

Here is the caller graph for this function:

Initialize()

void CQuadTree::Initialize	(	const UINT	d,
		const Shapes::CAabb2D &	a )

Initialize the quadtree for a given depth. This function assumes that the quadtree has been made null, that is, there is no structure there. Neglecting this will cause a memory leak.

Parameters

d	Desired quadtree depth.
a	An AABB for the entirety of Physics World.

Here is the call graph for this function:

Here is the caller graph for this function:

Insert() [1/2]

void CQuadTree::Insert

(

Shapes::CShape *

p

)

Insert a shape into the shape list of the leafs whose AABBs intersect the shape's AABB, assuming it is still in Physics World.

Parameters

p	Pointer to contact record for shape being inserted.

Here is the call graph for this function:

Insert() [2/2]

void CQuadTree::Insert ( Shapes::CShape * p, UINT i )

private

Insert a shape into the shape list of the leafs whose AABBs intersect the shape's AABB, starting at a particular node of the quadtree.

Parameters

p	Pointer to the shape being inserted.
i	Index of a node in the quadtree.

Here is the call graph for this function:

Here is the caller graph for this function: