CQuadTree Class Reference

A quadtree. More...

#include <QuadTree.h>

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

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

Private Attributes
CQuadTreeNode **	m_pTree
	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.

GetDepth()

const UINT CQuadTree::GetDepth

(

)

const

Reader function for the quadtree depth.

Returns

Depth of quadtree.

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.

GetLeafCount()

const UINT CQuadTree::GetLeafCount

(

)

const

Reader function for the number of leaves.

Returns

Number of leaves in quadtree.

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.

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.

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.

GetNodeCount()

const UINT CQuadTree::GetNodeCount

(

)

const

Reader function for the number of nodes.

Returns

Number of nodes in quadtree.

InitAABBs()

void CQuadTree::InitAABBs ( const CAabb2D &  a )

private

Initialize the AABBs in all of the nodes.

Parameters

a	AABB for the entirety of Physics World.

Initialize()

void CQuadTree::Initialize	(	const UINT	d,
		const 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.

Insert() [1/2]

void CQuadTree::Insert

(

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.

Returns

true if the shape is in Physics World.

Insert() [2/2]

void CQuadTree::Insert ( 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.

Returns

true if the shape is inside node i.