Encapsulates a node in a BSP tree. More...

#include <OgreBspNode.h>

Inheritance diagram for Ogre::BspNode:

Collaboration diagram for Ogre::BspNode:

Classes
struct	Brush

Public Types
typedef set< const MovableObject * >::type	IntersectingObjectSet

typedef vector< Brush * >::type	NodeBrushList

Public Member Functions
	BspNode (BspLevel *owner, bool isLeaf)
	Constructor, only to be used by BspLevel. More...

	BspNode ()

	~BspNode ()

void	_addMovable (const MovableObject *mov)
	Internal method for telling the node that a movable intersects it. More...

void	_removeMovable (const MovableObject *mov)
	Internal method for telling the node that a movable no longer intersects it. More...

BspNode *	getBack (void) const
	Returns a pointer to a BspNode containing the subspace on the negative side of the splitting plane. More...

const AxisAlignedBox &	getBoundingBox (void) const
	Returns the axis-aligned box which contains this node if it is a leaf. More...

Real	getDistance (const Vector3 &pos) const
	Gets the signed distance to the dividing plane. More...

int	getFaceGroupStart (void) const
	Returns the index to the face group index list for this leaf node. More...

BspNode *	getFront (void) const
	Returns a pointer to a BspNode containing the subspace on the positive side of the splitting plane. More...

BspNode *	getNextNode (const Vector3 &point) const
	Gets the next node down in the tree, with the intention of locating the leaf containing the given point. More...

int	getNumFaceGroups (void) const
	Returns the number of faces contained in this leaf node. More...

const IntersectingObjectSet &	getObjects (void) const

Plane::Side	getSide (const Vector3 &point) const
	Determines which side of the splitting plane a worldspace point is. More...

const NodeBrushList &	getSolidBrushes (void) const
	Get the list of solid Brushes for this node. More...

const Plane &	getSplitPlane (void) const
	Returns details of the plane which is used to subdivide the space of his node's children. More...

bool	isLeaf (void) const
	Returns true if this node is a leaf (i.e. More...

bool	isLeafVisible (const BspNode *leaf) const
	Determines if the passed in node (must also be a leaf) is visible from this leaf. More...

void	operator delete (void *ptr)

void	operator delete (void ptr, void )

void	operator delete (void ptr, const char , int, const char *)

void	operator delete[] (void *ptr)

void	operator delete[] (void ptr, const char , int, const char *)

void *	operator new (size_t sz, const char file, int line, const char func)
	operator new, with debug line info More...

void *	operator new (size_t sz)

void *	operator new (size_t sz, void *ptr)
	placement operator new More...

void *	operator new[] (size_t sz, const char file, int line, const char func)
	array operator new, with debug line info More...

void *	operator new[] (size_t sz)

Protected Attributes
BspNode *	mBack
	Pointer to the node behind this non-leaf node. More...

AxisAlignedBox	mBounds
	The axis-aligned box which bounds node if it is a leaf. More...

int	mFaceGroupStart
	Index to the part of the main leaf facegroup index buffer(held in BspLevel) for this leaf. More...

BspNode *	mFront
	Pointer to the node in front of this non-leaf node. More...

bool	mIsLeaf

IntersectingObjectSet	mMovables

int	mNumFaceGroups
	Number of face groups in this node if it is a leaf. More...

BspLevel *	mOwner

NodeBrushList	mSolidBrushes

Plane	mSplitPlane
	The plane which splits space in a non-leaf node. More...

int	mVisCluster
	The cluster number of this leaf. More...

Friends
class	BspLevel

std::ostream &	operator<< (std::ostream &o, BspNode &n)

Detailed Description

Encapsulates a node in a BSP tree.

A BSP tree represents space partitioned by planes . The space which is partitioned is either the world (in the case of the root node) or the space derived from their parent node. Each node can have elements which are in front or behind it, which are it's children and these elements can either be further subdivided by planes, or they can be undivided spaces or 'leaf nodes' - these are the nodes which actually contain objects and world geometry.The leaves of the tree are the stopping point of any tree walking algorithm, both for rendering and collision detection etc.

Ogre chooses not to represent splitting nodes and leaves as separate structures, but to merge the two for simplicity of the walking algorithm. If a node is a leaf, the isLeaf() method returns true and both getFront() and getBack() return null pointers. If the node is a partitioning plane isLeaf() returns false and getFront() and getBack() will return the corresponding BspNode objects.

Definition at line 51 of file OgreBspNode.h.

Member Typedef Documentation

typedef set<const MovableObject*>::type Ogre::BspNode::IntersectingObjectSet

Definition at line 145 of file OgreBspNode.h.

typedef vector<Brush*>::type Ogre::BspNode::NodeBrushList

Definition at line 152 of file OgreBspNode.h.

Constructor & Destructor Documentation

Ogre::BspNode::BspNode	(	BspLevel *	owner,
		bool	isLeaf
	)

Constructor, only to be used by BspLevel.

Ogre::BspNode::BspNode ( )

Ogre::BspNode::~BspNode ( )

Member Function Documentation

void Ogre::BspNode::_addMovable ( const MovableObject * mov )

Internal method for telling the node that a movable intersects it.

void Ogre::BspNode::_removeMovable ( const MovableObject * mov )

Internal method for telling the node that a movable no longer intersects it.

BspNode* Ogre::BspNode::getBack ( void ) const

Returns a pointer to a BspNode containing the subspace on the negative side of the splitting plane.

This method should only be called on a splitting node, i.e. where isLeaf() returns false. Calling this method on a leaf node will throw an exception.

const AxisAlignedBox& Ogre::BspNode::getBoundingBox ( void ) const

Returns the axis-aligned box which contains this node if it is a leaf.

This method should only be called on a leaf node. It returns a box which can be used in calls like Camera::isVisible to determine if the leaf node is visible in the view.

Real Ogre::BspNode::getDistance ( const Vector3 & pos ) const

Gets the signed distance to the dividing plane.

int Ogre::BspNode::getFaceGroupStart ( void ) const

Returns the index to the face group index list for this leaf node.

The contents of this buffer is a list of indexes which point to the actual face groups held in a central buffer in the BspLevel class (in actual fact for efficiency the indexes themselves are also held in a single buffer in BspLevel too). The reason for this indirection is that the buffer of indexes to face groups is organised in chunks relative to nodes, whilst the main buffer of face groups may not be. Should only be called on a leaf node.

BspNode* Ogre::BspNode::getFront ( void ) const

Returns a pointer to a BspNode containing the subspace on the positive side of the splitting plane.

This method should only be called on a splitting node, i.e. where isLeaf() returns false. Calling this method on a leaf node will throw an exception.

BspNode* Ogre::BspNode::getNextNode ( const Vector3 & point ) const

Gets the next node down in the tree, with the intention of locating the leaf containing the given point.

This method should only be called on a splitting node, i.e. where isLeaf() returns false. Calling this method on a leaf node will throw an exception.

int Ogre::BspNode::getNumFaceGroups ( void ) const

Returns the number of faces contained in this leaf node.

Should only be called on a leaf node.

const IntersectingObjectSet& Ogre::BspNode::getObjects ( void ) const

inline

Definition at line 204 of file OgreBspNode.h.

References mMovables.

Plane::Side Ogre::BspNode::getSide ( const Vector3 & point ) const

Determines which side of the splitting plane a worldspace point is.

This method should only be called on a splitting node, i.e. where isLeaf() returns false. Calling this method on a leaf node will throw an exception.

const NodeBrushList& Ogre::BspNode::getSolidBrushes ( void ) const

Get the list of solid Brushes for this node.

Remarks: Only applicable for leaf nodes.

const Plane& Ogre::BspNode::getSplitPlane ( void ) const

Returns details of the plane which is used to subdivide the space of his node's children.

This method should only be called on a splitting node, i.e. where isLeaf() returns false. Calling this method on a leaf node will throw an exception.

bool Ogre::BspNode::isLeaf ( void ) const

Returns true if this node is a leaf (i.e.

contains geometry) or false if it is a splitting plane. A BspNode can either be a splitting plane (the typical representation of a BSP node) or an undivided region contining geometry (a leaf node). Ogre represents both using the same class for simplicity of tree walking. However it is important that you use this method to determine which type you are dealing with, since certain methods are only supported with one of the subtypes. Details are given in the individual methods. Note that I could have represented splitting / leaf nodes as a class hierarchy but the virtual methods / run-time type identification would have a performance hit, and it would not make the code much (any?) simpler anyway. I think this is a fair trade-off in this case.

bool Ogre::BspNode::isLeafVisible ( const BspNode * leaf ) const

Determines if the passed in node (must also be a leaf) is visible from this leaf.

Must only be called on a leaf node, and the parameter must also be a leaf node. If this method returns true, then the leaf passed in is visible from this leaf. Note that internally this uses the Potentially Visible Set (PVS) which is precalculated and stored with the BSP level.

template<class Alloc >

void Ogre::AllocatedObject< Alloc >::operator delete ( void * ptr )

inlineinherited

Definition at line 95 of file OgreMemoryAllocatedObject.h.

template<class Alloc >

void Ogre::AllocatedObject< Alloc >::operator delete	(	void *	ptr,
		void *
	)

inlineinherited

Definition at line 101 of file OgreMemoryAllocatedObject.h.

template<class Alloc >

void Ogre::AllocatedObject< Alloc >::operator delete	(	void *	ptr,
		const char *	,
		int	,
		const char *
	)

inlineinherited

Definition at line 107 of file OgreMemoryAllocatedObject.h.

template<class Alloc >

void Ogre::AllocatedObject< Alloc >::operator delete[] ( void * ptr )

inlineinherited

Definition at line 112 of file OgreMemoryAllocatedObject.h.

template<class Alloc >

void Ogre::AllocatedObject< Alloc >::operator delete[]	(	void *	ptr,
		const char *	,
		int	,
		const char *
	)

inlineinherited

Definition at line 118 of file OgreMemoryAllocatedObject.h.

template<class Alloc >

void* Ogre::AllocatedObject< Alloc >::operator new	(	size_t	sz,
		const char *	file,
		int	line,
		const char *	func
	)

inlineinherited

operator new, with debug line info

Definition at line 67 of file OgreMemoryAllocatedObject.h.

template<class Alloc >

void* Ogre::AllocatedObject< Alloc >::operator new ( size_t sz )

inlineinherited

Definition at line 72 of file OgreMemoryAllocatedObject.h.

template<class Alloc >

void* Ogre::AllocatedObject< Alloc >::operator new	(	size_t	sz,
		void *	ptr
	)

inlineinherited

placement operator new

Definition at line 78 of file OgreMemoryAllocatedObject.h.

template<class Alloc >

void* Ogre::AllocatedObject< Alloc >::operator new[]	(	size_t	sz,
		const char *	file,
		int	line,
		const char *	func
	)

inlineinherited

array operator new, with debug line info

Definition at line 85 of file OgreMemoryAllocatedObject.h.

template<class Alloc >

void* Ogre::AllocatedObject< Alloc >::operator new[] ( size_t sz )

inlineinherited

Definition at line 90 of file OgreMemoryAllocatedObject.h.

Friends And Related Function Documentation

friend class BspLevel

friend

Definition at line 53 of file OgreBspNode.h.

std::ostream& operator<<	(	std::ostream &	o,
		BspNode &	n
	)

friend

Member Data Documentation

BspNode* Ogre::BspNode::mBack

protected

Pointer to the node behind this non-leaf node.

Definition at line 171 of file OgreBspNode.h.

AxisAlignedBox Ogre::BspNode::mBounds

protected

The axis-aligned box which bounds node if it is a leaf.

Definition at line 188 of file OgreBspNode.h.

int Ogre::BspNode::mFaceGroupStart

protected

Index to the part of the main leaf facegroup index buffer(held in BspLevel) for this leaf.

This leaf uses mNumFaceGroups from this pointer onwards. From here you use the index in this buffer to look up the actual face. Note that again for simplicity and bulk memory allocation the face group list itself is allocated by the BspLevel for all nodes, and each leaf node is given a section of it to work on. This saves lots of small memory allocations / deallocations which limits memory fragmentation.

Definition at line 198 of file OgreBspNode.h.

BspNode* Ogre::BspNode::mFront

protected

Pointer to the node in front of this non-leaf node.

Definition at line 169 of file OgreBspNode.h.

bool Ogre::BspNode::mIsLeaf

protected

Definition at line 160 of file OgreBspNode.h.

IntersectingObjectSet Ogre::BspNode::mMovables

protected

Definition at line 200 of file OgreBspNode.h.

Referenced by getObjects().

int Ogre::BspNode::mNumFaceGroups

protected

Number of face groups in this node if it is a leaf.

Definition at line 190 of file OgreBspNode.h.

BspLevel* Ogre::BspNode::mOwner

protected

Definition at line 159 of file OgreBspNode.h.

NodeBrushList Ogre::BspNode::mSolidBrushes

protected

Definition at line 202 of file OgreBspNode.h.

Plane Ogre::BspNode::mSplitPlane

protected

The plane which splits space in a non-leaf node.

Note that nodes do not allocate the memory for other nodes - for simplicity and bulk-allocation of memory the BspLevel is responsible for assigning enough memory for all nodes in one go.

Definition at line 167 of file OgreBspNode.h.

int Ogre::BspNode::mVisCluster

protected

The cluster number of this leaf.

Leaf nodes are assigned to 'clusters' of nodes, which are used to group nodes together for visibility testing. There is a lookup table which is used to determine if one cluster of leaves is visible from another cluster. Whilst it would be possible to expand all this out so that each node had a list of pointers to other visible nodes, this would be very expensive in terms of storage (using the cluster method there is a table which is 1-bit squared per cluster, rounded up to the nearest byte obviously, which uses far less space than 4-bytes per linked node per source node). Of course the limitation here is that you have to each leaf in turn to determine if it is visible rather than just following a list, but since this is only done once per frame this is not such a big overhead.

Definition at line 185 of file OgreBspNode.h.

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

OgreBspNode.h

Classes

Public Types

Public Member Functions

Protected Attributes

Friends

Detailed Description

Member Typedef Documentation

Constructor & Destructor Documentation

Member Function Documentation

Friends And Related Function Documentation

Member Data Documentation