#include <CDGrid.h>

Classes
struct	BinDir

Public Types
typedef std::list< CD::Volume * >	BinOccupiersList

typedef std::list< const Math::Point< int > * >	OccupiedBinsList

typedef std::map< const Math::Point< int > *, BinOccupiersList >	BinOccupiersMap

typedef std::map< CD::Volume *, OccupiedBinsList >	OccupiedBinsMap

Public Member Functions
	Grid (Utils::uint initXDivs_, Utils::uint initYDivs_, Utils::uint initZDivs_, Utils::uint maxSubdivs_)

	Grid (const Grid &grid_)

virtual	~Grid ()

virtual bool	calcOccupiedBins (CD::Volume *vol_, bool calcPlanes_=true, bool useOctalPartitioning_=false, bool decrementPrevOccupiedBins_=false)

virtual bool	calcOccupiedBins (bool calcPlanes_=true, bool useOctalPartitioning_=false)

const Math::Point &	getMaxCorner () const

void	translateMaxCorner ()

const Math::Point &	getSize () const

const Math::Point< Utils::uint > &	getAxisDivs () const

const Math::Point &	getBinSize () const

bool	isSubdivided () const

const Utils::uint &	getSubNum () const

void	getBin (const Math::Point<> &p_, Math::Point< int > &bin_) const

unsigned short	getNumOccupants (const Math::Point< int > &bin_)

bool	decrementBin (const Math::Point< int > &bin_)

void	incrementBin (const Math::Point< int > &bin_)

void	clearBin (const Math::Point< int > &bin_)

bool	isObjectOutside (const int &minBinX_, const int &maxBinX_, const int &minBinY_, const int &maxBinY_, const int &minBinZ_, const int &maxBinZ_) const

bool	isObjectOutside (const Math::Point< int > &bin_) const

void	getOccupiedBins (std::vector< const Math::Point< int > * > &bins_) const

OccupiedBinsList &	getOccupiedBins (CD::Volume *vol_)

BinOccupiersList &	getOccupiers (const Math::Point< int > *bin_)

void	getNeighbors (const Math::Point< int > &bin_, std::vector< BinDir > &neighbors_, Utils::uint numOccupants_=0, bool allowDiagonals_=false, bool allowCorners_=false) const

Math::Point	translatePointByBin (const Math::Point<> &p_, const Math::Point< int > &bin_) const

Math::Point	getNearestBinCenter (const Math::Point<> &p_) const

Static Public Member Functions
Shutdown Operations
static void	shutDown ()

Public Attributes
const Utils::uint	INITIAL_X_DIVISIONS

const Utils::uint	INITIAL_Y_DIVISIONS

const Utils::uint	INITIAL_Z_DIVISIONS

const Utils::uint	MAX_SUBDIVISIONS

const Utils::uint	MAX_X_DIVISIONS

const Utils::uint	MAX_Y_DIVISIONS

const Utils::uint	MAX_Z_DIVISIONS

Protected Member Functions
void	makeSubGrid ()

void	cullObjectOutside (int &minBinX_, int &maxBinX_, int &minBinY_, int &maxBinY_, int &minBinZ_, int &maxBinZ_) const

void	cullObjectOutside (Math::Point< int > &bin_) const

void	calcOccupiedBinsUsingOctalPartitioning (Volume *vol_, const Math::Point< Utils::uint > &minBin_, const Math::Point< Utils::uint > &maxBin_, const Math::Point<> &maxCenter_)

Protected Attributes
bool	_didDynamicallyAllocateMem

const Math::Point **	_corners

Math::Point *	_maxCorner

Math::Point *	_size

Math::Point *	_binSize

std::set< CD::Volume * > **	_nodes

bool	_isSub

Utils::uint	_subNum

Math::Point< Utils::uint >	_axisDivisions

Math::Point	_subBinSize

Utils::HashTableUIntKeys < unsigned short >	_isBinOccupied

BinOccupiersMap	_binOccupiers

OccupiedBinsMap	_occupiedBins

Friends
class	PF::Manager

Setup Operations
void	setCorners (const Math::Point<> *corners_)

void	setNodes (std::set< CD::Volume * > &nodes_)

std::set< CD::Volume * > *	getNodes () const

void	resetGrid ()

static void	init (Utils::uint initGlobalXDivs_, Utils::uint initGlobalYDivs_, Utils::uint initGlobalZDivs_, Utils::uint maxGlobalSubdivs_)

static void	resetAllGlobalGrids ()

Detailed Description

A Grid is an AABB subdivided into smaller AABBs with functionality useful for broadphase collision detection and pathfinding. Using the default Grid constructor allocates dynamic memory for specifying the corners and data indicating which bins are occupied. Using the copy constructor does not allocate dynamic memory and uses the data from the Grid to be copied. The assignment operator is currently disallowed.

Member Typedef Documentation

typedef std::list<CD::Volume*> OpenSkyNet::CD::Grid::BinOccupiersList

Todo:: Use a custom pool allocator

typedef std::map<const Math::Point<int>*, BinOccupiersList> OpenSkyNet::CD::Grid::BinOccupiersMap

typedef std::list<const Math::Point<int>*> OpenSkyNet::CD::Grid::OccupiedBinsList

typedef std::map<CD::Volume*, OccupiedBinsList> OpenSkyNet::CD::Grid::OccupiedBinsMap

Constructor & Destructor Documentation

Grid::Grid	(	Utils::uint	initXDivs_,
		Utils::uint	initYDivs_,
		Utils::uint	initZDivs_,
		Utils::uint	maxSubdivs_
	)

Grid::Grid ( const Grid & grid_ )

Grid::~Grid ( )

virtual

Member Function Documentation

virtual bool OpenSkyNet::CD::Grid::calcOccupiedBins	(	CD::Volume *	vol_,
		bool	calcPlanes_ = `true`,
		bool	useOctalPartitioning_ = `false`,
		bool	decrementPrevOccupiedBins_ = `false`
	)

virtual

Hash the volume to the bin(s) it occupies.

Parameters

calcPlanes_	include PLANE shapes in the calculations
useOctalPartitioning_	for shapes where bin ranges can not be hashed, partition the grid looking for occupants, rather than distance testing with each bin initially
decrementPrevOccupiedBins_	If true, will decrement any previous bins occupied by this volume

virtual bool OpenSkyNet::CD::Grid::calcOccupiedBins	(	bool	calcPlanes_ = `true`,
		bool	useOctalPartitioning_ = `false`
	)

virtual

Hash each object in the Grid to the bin(s) it occupies.

Parameters

calcPlanes_	include PLANE shapes in the calculations
useOctalPartitioning_	for shapes where bin ranges can not be hashed, partition the grid looking for occupants, rather than distance testing with each bin initially

void Grid::calcOccupiedBinsUsingOctalPartitioning	(	Volume *	vol_,
		const Math::Point< Utils::uint > &	minBin_,
		const Math::Point< Utils::uint > &	maxBin_,
		const Math::Point<> &	maxCenter_
	)

protected

void OpenSkyNet::CD::Grid::clearBin ( const Math::Point< int > & bin_ )

inline

Sets the number of occupants of this bin to 0.

void OpenSkyNet::CD::Grid::cullObjectOutside	(	int &	minBinX_,
		int &	maxBinX_,
		int &	minBinY_,
		int &	maxBinY_,
		int &	minBinZ_,
		int &	maxBinZ_
	)		const

protected

void OpenSkyNet::CD::Grid::cullObjectOutside ( Math::Point< int > & bin_ ) const

protected

bool OpenSkyNet::CD::Grid::decrementBin ( const Math::Point< int > & bin_ )

inline

Decrease the number of occupants of this bin by 1. Returns false if already 0.

const Math::Point<Utils::uint>& OpenSkyNet::CD::Grid::getAxisDivs ( ) const

inline

Returns the # of divisions of each axis.

void OpenSkyNet::CD::Grid::getBin	(	const Math::Point<> &	p_,
		Math::Point< int > &	bin_
	)		const

inline

Get the bin hashed to a point.

const Math::Point& OpenSkyNet::CD::Grid::getBinSize ( ) const

inline

Returns the bin size (the spatial distance between axis divisions) for each axis.

const Math::Point& OpenSkyNet::CD::Grid::getMaxCorner ( ) const

inline

Returns the max x, max y, and max z relative to the Grid.

Point Grid::getNearestBinCenter ( const Math::Point<> & p_ ) const

void Grid::getNeighbors	(	const Math::Point< int > &	bin_,
		std::vector< BinDir > &	neighbors_,
		Utils::uint	numOccupants_ = `0`,
		bool	allowDiagonals_ = `false`,
		bool	allowCorners_ = `false`
	)		const

std::set<CD::Volume*>* OpenSkyNet::CD::Grid::getNodes ( ) const

inline

unsigned short OpenSkyNet::CD::Grid::getNumOccupants ( const Math::Point< int > & bin_ )

inline

void OpenSkyNet::CD::Grid::getOccupiedBins ( std::vector< const Math::Point< int > * > & bins_ ) const

Gets the indices of occupied bins.

OccupiedBinsList& OpenSkyNet::CD::Grid::getOccupiedBins ( CD::Volume * vol_ )

inline

BinOccupiersList& OpenSkyNet::CD::Grid::getOccupiers ( const Math::Point< int > * bin_ )

inline

const Math::Point& OpenSkyNet::CD::Grid::getSize ( ) const

inline

Returns the Grid's size.

const Utils::uint& OpenSkyNet::CD::Grid::getSubNum ( ) const

inline

Return the number of times this copy of the Grid has been divided.

void OpenSkyNet::CD::Grid::incrementBin ( const Math::Point< int > & bin_ )

inline

Increase the number of occupants of this bin by 1.

void Grid::init	(	Utils::uint	initGlobalXDivs_,
		Utils::uint	initGlobalYDivs_,
		Utils::uint	initGlobalZDivs_,
		Utils::uint	maxGlobalSubdivs_
	)

static

bool OpenSkyNet::CD::Grid::isObjectOutside	(	const int &	minBinX_,
		const int &	maxBinX_,
		const int &	minBinY_,
		const int &	maxBinY_,
		const int &	minBinZ_,
		const int &	maxBinZ_
	)		const

Returns true only if ALL bounds are outside.

bool OpenSkyNet::CD::Grid::isObjectOutside ( const Math::Point< int > & bin_ ) const

bool OpenSkyNet::CD::Grid::isSubdivided ( ) const

inline

void Grid::makeSubGrid ( )

protected

void Grid::resetAllGlobalGrids ( )

static

Call this AFTER EACH call to the method setCorners() but BEFORE all other methods.

void Grid::resetGrid ( )

void Grid::setCorners ( const Math::Point<> * corners_ )

corners_[0] == min x, min y, max z corners_[1] == min x, max y, max z corners_[2] == max x, max y, max z corners_[3] == max x, min y, max z corners_[4] == max x, max y, min z corners_[5] == min x, max y, min z corners_[6] == min x, min y, min z corners_[7] == max x, min y, min z

void OpenSkyNet::CD::Grid::setNodes ( std::set< CD::Volume * > & nodes_ )

inline

Sets all the objects in the Grid.

void Grid::shutDown ( )

static

void OpenSkyNet::CD::Grid::translateMaxCorner ( )

inline

Translate the Grid. Does NOT require resetGrid() to be called afterwards.

Point Grid::translatePointByBin	(	const Math::Point<> &	p_,
		const Math::Point< int > &	bin_
	)		const

Friends And Related Function Documentation

friend class PF::Manager

friend

Member Data Documentation

Math::Point<Utils::uint> OpenSkyNet::CD::Grid::_axisDivisions

protected

BinOccupiersMap OpenSkyNet::CD::Grid::_binOccupiers

protected

Math::Point* OpenSkyNet::CD::Grid::_binSize

protected

bin width (x) and height (y) are based on the max z plane. bin depth (z) is based on the max x plane.

const Math::Point** OpenSkyNet::CD::Grid::_corners

protected

bool OpenSkyNet::CD::Grid::_didDynamicallyAllocateMem

protected

Utils::HashTableUIntKeys<unsigned short> OpenSkyNet::CD::Grid::_isBinOccupied

protected

bool OpenSkyNet::CD::Grid::_isSub

protected

Math::Point* OpenSkyNet::CD::Grid::_maxCorner

protected

_maxCorner == (max pos x), (max pos y), (max pos z)

std::set<CD::Volume*>** OpenSkyNet::CD::Grid::_nodes

protected

OccupiedBinsMap OpenSkyNet::CD::Grid::_occupiedBins

protected

Math::Point* OpenSkyNet::CD::Grid::_size

protected

Math::Point OpenSkyNet::CD::Grid::_subBinSize

protected

Utils::uint OpenSkyNet::CD::Grid::_subNum

protected

const Utils::uint OpenSkyNet::CD::Grid::INITIAL_X_DIVISIONS

Initial x divisions of the grid.

const Utils::uint OpenSkyNet::CD::Grid::INITIAL_Y_DIVISIONS

Initial y divisions of the grid.

const Utils::uint OpenSkyNet::CD::Grid::INITIAL_Z_DIVISIONS

Initial z divisions of the grid.

const Utils::uint OpenSkyNet::CD::Grid::MAX_SUBDIVISIONS

Max # of times the grid can be divided.

const Utils::uint OpenSkyNet::CD::Grid::MAX_X_DIVISIONS

Must = INITIAL_X_DIVISIONS * 2^MAX_SUBDIVISIONS.

const Utils::uint OpenSkyNet::CD::Grid::MAX_Y_DIVISIONS

Must = INITIAL_Y_DIVISIONS * 2^MAX_SUBDIVISIONS.

const Utils::uint OpenSkyNet::CD::Grid::MAX_Z_DIVISIONS

Must = INITIAL_Z_DIVISIONS * 2^MAX_SUBDIVISIONS.

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

Code/Libs/CD_LIB/CDGrid.h
Code/Libs/CD_LIB/CDGrid.cpp

Classes

Public Types

Public Member Functions

Static Public Member Functions

Public Attributes

Protected Member Functions

Protected Attributes

Friends

Setup Operations

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation