Main Page   Namespace List   Class Hierarchy   Alphabetical List   Compound List   File List   Namespace Members   Compound Members   File Members   Related Pages  

Ogre::BspNode Class Reference

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

#include <OgreBspNode.h>

List of all members.

Public Types

typedef std::set< const MovableObject * > IntersectingObjectSet
typedef std::vector< Brush * > NodeBrushList

Public Methods

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

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

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

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

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

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.

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

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

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

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

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

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

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

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

const NodeBrushListgetSolidBrushes (void)
 Get the list of solid Brushes for this node.

const IntersectingObjectSetgetObjects (void)

Protected Attributes

BspLevelmOwner
bool mIsLeaf
Plane mSplitPlane
 The plane which splits space in a non-leaf node.

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

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

int mVisCluster
 The cluster number of this leaf.

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

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

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

IntersectingObjectSet mMovables
NodeBrushList mSolidBrushes

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 48 of file OgreBspNode.h.


Member Typedef Documentation

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

Definition at line 142 of file OgreBspNode.h.

Referenced by getObjects().

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

Definition at line 149 of file OgreBspNode.h.


Constructor & Destructor Documentation

Ogre::BspNode::BspNode BspLevel   owner,
bool    isLeaf
 

Constructor, only to be used by BspLevel.

Definition at line 34 of file OgreBspNode.cpp.

References isLeaf(), mIsLeaf, and mOwner.

Ogre::BspNode::BspNode  
 

Definition at line 42 of file OgreBspNode.cpp.

Ogre::BspNode::~BspNode  
 

Definition at line 46 of file OgreBspNode.cpp.


Member Function Documentation

void Ogre::BspNode::_addMovable const MovableObject   mov
 

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

Definition at line 160 of file OgreBspNode.cpp.

References mMovables.

Referenced by Ogre::BspLevel::tagNodesWithMovable().

void Ogre::BspNode::_removeMovable const MovableObject   mov
 

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

Definition at line 165 of file OgreBspNode.cpp.

References mMovables.

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.

Definition at line 67 of file OgreBspNode.cpp.

References mBack.

Referenced by getNextNode(), and Ogre::BspLevel::tagNodesWithMovable().

AxisAlignedBox & Ogre::BspNode::getBoundingBox void   
 

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.

Definition at line 89 of file OgreBspNode.cpp.

References mBounds, and mIsLeaf.

Referenced by Ogre::BspSceneManager::walkTree().

Real Ogre::BspNode::getDistance const Vector3   pos
 

Gets the signed distance to the dividing plane.

Definition at line 170 of file OgreBspNode.cpp.

References Ogre::Plane::getDistance(), mSplitPlane, and Ogre::Real.

Referenced by Ogre::BspLevel::tagNodesWithMovable().

int Ogre::BspNode::getFaceGroupStart void   
 

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 efficency 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.

Definition at line 110 of file OgreBspNode.cpp.

References mFaceGroupStart, and mIsLeaf.

Referenced by Ogre::BspSceneManager::processVisibleLeaf().

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.

Definition at line 57 of file OgreBspNode.cpp.

References mFront.

Referenced by getNextNode(), and Ogre::BspLevel::tagNodesWithMovable().

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.

Definition at line 136 of file OgreBspNode.cpp.

References getBack(), getFront(), and getSide().

Referenced by Ogre::BspLevel::findLeaf().

int Ogre::BspNode::getNumFaceGroups void   
 

Returns the number of faces contained in this leaf node.

Should only be called on a leaf node.

Definition at line 100 of file OgreBspNode.cpp.

References mIsLeaf, and mNumFaceGroups.

Referenced by Ogre::BspSceneManager::processVisibleLeaf().

const IntersectingObjectSet& Ogre::BspNode::getObjects void   
 

Definition at line 201 of file OgreBspNode.h.

References IntersectingObjectSet, and mMovables.

Referenced by Ogre::BspIntersectionSceneQuery::execute(), and Ogre::BspSceneManager::processVisibleLeaf().

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.

Definition at line 125 of file OgreBspNode.cpp.

References Ogre::Plane::getSide(), and mSplitPlane.

Referenced by getNextNode().

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

Get the list of solid Brushes for this node.

Remarks:
Only applicable for leaf nodes.

Definition at line 181 of file OgreBspNode.cpp.

References mSolidBrushes.

Referenced by Ogre::BspIntersectionSceneQuery::execute().

Plane Ogre::BspNode::getSplitPlane void   
 

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.

Definition at line 77 of file OgreBspNode.cpp.

References mSplitPlane.

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.

Definition at line 51 of file OgreBspNode.cpp.

References mIsLeaf.

Referenced by BspNode(), Ogre::BspLevel::findLeaf(), Ogre::BspLevel::isLeafVisible(), and Ogre::BspLevel::tagNodesWithMovable().

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

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.

Definition at line 120 of file OgreBspNode.cpp.

References Ogre::BspLevel::isLeafVisible(), and mOwner.


Friends And Related Function Documentation

friend class BspLevel [friend]
 

Definition at line 50 of file OgreBspNode.h.

std::ostream& operator<< std::ostream &    o,
BspNode &    n
[friend]
 

Definition at line 186 of file OgreBspNode.cpp.


Member Data Documentation

BspNode* Ogre::BspNode::mBack [protected]
 

Pointer to the node behind this non-leaf node.

Definition at line 168 of file OgreBspNode.h.

Referenced by getBack(), and Ogre::BspLevel::loadQuake3Level().

AxisAlignedBox Ogre::BspNode::mBounds [protected]
 

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

Definition at line 185 of file OgreBspNode.h.

Referenced by getBoundingBox(), Ogre::BspLevel::loadQuake3Level(), and Ogre::operator<<().

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 195 of file OgreBspNode.h.

Referenced by getFaceGroupStart(), Ogre::BspLevel::loadQuake3Level(), and Ogre::operator<<().

BspNode* Ogre::BspNode::mFront [protected]
 

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

Definition at line 166 of file OgreBspNode.h.

Referenced by getFront(), and Ogre::BspLevel::loadQuake3Level().

bool Ogre::BspNode::mIsLeaf [protected]
 

Definition at line 157 of file OgreBspNode.h.

Referenced by BspNode(), getBoundingBox(), getFaceGroupStart(), getNumFaceGroups(), isLeaf(), Ogre::BspLevel::loadQuake3Level(), and Ogre::operator<<().

IntersectingObjectSet Ogre::BspNode::mMovables [protected]
 

Definition at line 197 of file OgreBspNode.h.

Referenced by _addMovable(), _removeMovable(), and getObjects().

int Ogre::BspNode::mNumFaceGroups [protected]
 

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

Definition at line 187 of file OgreBspNode.h.

Referenced by getNumFaceGroups(), Ogre::BspLevel::loadQuake3Level(), and Ogre::operator<<().

BspLevel* Ogre::BspNode::mOwner [protected]
 

Definition at line 156 of file OgreBspNode.h.

Referenced by BspNode(), isLeafVisible(), and Ogre::BspLevel::loadQuake3Level().

NodeBrushList Ogre::BspNode::mSolidBrushes [protected]
 

Definition at line 199 of file OgreBspNode.h.

Referenced by getSolidBrushes(), and Ogre::BspLevel::loadQuake3Level().

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 164 of file OgreBspNode.h.

Referenced by getDistance(), getSide(), getSplitPlane(), Ogre::BspLevel::loadQuake3Level(), and Ogre::operator<<().

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 182 of file OgreBspNode.h.

Referenced by Ogre::BspLevel::isLeafVisible(), Ogre::BspLevel::loadQuake3Level(), and Ogre::operator<<().


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

Copyright © 2002-2003 by The OGRE Team
Last modified Fri May 14 23:23:23 2004