esg::BVH

BVH Class Reference

#include <BVH.h>

Inheritance diagram for BVH:

SDS FDHTree SphereTree FDH14Tree FDH6Tree List of all members.

Public Member Functions

 BVH (unsigned, unsigned, bool, BVList::SplitStrategy)
virtual ~BVH ()
virtual SDS * clone () const =0
virtual Iterator * createIterator ()
virtual InspectorSDS * createInspector (unsigned)
virtual int append (SceneGraphObject *)
virtual SceneGraphObject * detach (SceneGraphObject::OID)
virtual bool update (void)
virtual bool build (void)
unsigned leafLimit (void) const
unsigned depthLimit (void) const
virtual double distance (Matrix4 *, BVH &, Matrix4 *, Node **, Node **, Vector3 *pDir=NULL, unsigned d1=UINT_MAX, unsigned d2=UINT_MAX)
virtual bool separation (Matrix4 *, BVH &, Matrix4 *, Vector3 *pDir=NULL, unsigned d1=UINT_MAX, unsigned d2=UINT_MAX)
virtual Geometry ** collision (Matrix4 *, float, float, float, float, int *)
virtual void dump (const char *, const char *)
virtual void __debug (void)
virtual void __debug (Node *n, int d)
void __get_edges (Matrix4 *, Node *, unsigned, unsigned, int, float *, unsigned &)
float * __getEdges (Matrix4 *pMyTr, unsigned level, int rot, unsigned &size)
void __get_meshes (Matrix4 *, Node *, unsigned, unsigned, int, Mesh **, unsigned &)
Mesh ** __getMeshes (Matrix4 *pMyTr, unsigned level, int rot, unsigned &size)
virtual void dump (const char *)

Static Public Member Functions

static Matrix4 * multiTrans (const Matrix4 *, const Matrix4 *, Vector3 &)
static Matrix4 * multiTrans (const Matrix4 *, const Matrix4 *, double &)

Protected Member Functions

bool _append (SceneGraphObject *, Geometry *, Node *, unsigned)
void _remove_leaf (Node *)
void _build_tree (Node *, unsigned)
void _destroy_tree (Node *)
void _rebuild_tree (Node *)
Geometry * _create_bv (BVList &)
void _collision (Node *, Geometry &, List< SceneGraphObject > *)
void _dump (const Node *, const char *, const char *)
virtual DistRot * _create_dist_rot (BVH::Node *)
virtual void _dr_init (const Matrix4 *, const Matrix4 *, BVH *)
virtual void _dr_primitives (DRInfo &, Node *, Vector3 *)
virtual void _dr_leaf (DRInfo &, Node *, unsigned)
virtual void _dr_inner (DRInfo &, Node *, Node *, unsigned)
virtual bool _enlarge_bv (Geometry **, Geometry &)=0
virtual Geometry * _create_bv (List< SceneGraphObject > &)=0
virtual Geometry * _create_bv (Geometry &, Geometry &)=0
virtual Geometry * _create_bv (SceneGraphObject &)=0
virtual BVList * _create_list ()=0
virtual void _duplicate_attributes (const SDS &)
 BVH ()

Protected Attributes

esg::BVH::DRInfo _drInfo
Node * _root
Node * _leftLeaf
unsigned _leafLimit
unsigned _depthLimit
unsigned _treeDepth
Matrix4 _myTrMat
Matrix4 _coordMat
 matrix transforming my coords to the partner's
double _scaleRatio
 metric ratio scale from _pCoordMat
BVH * _pPartner
 partner during collision detection
BVList::SplitStrategy _splitStrategy
bool _delayBuild
List< SceneGraphObject > _intangibleChildren

Friends

class IteratorBVH
class InspectorBVH
class BVDistance
class BVExplorer

Classes

struct  DRInfo
struct  Node

Detailed Description

Generic class for Bounding Volume Hierarchy spacial data structure.

Protocol1:

BVH g(ll, dl, false); [g.append(o); ... g.append(o);] [g.build();] [g.append(o); ... g.append(o)] ______________/ ____/ _____________/ \/ \/ \/ (add objects to hierarchy) (does nothing here) (add objects to hierarchy)

Protocol2:

BVH g(ll, dl, true); [g.append(o); ... g.append(o);] g.build(); [g.append(o); ... g.append(o)] ______________/ ___/ _____________/ \/ \/ \/ (store temporarilly) (create balanced hierarchy) (add objects)

Definition at line 37 of file BVH.h.

Constructor & Destructor Documentation

BVH (   )  [inline, protected]
 

Definition at line 110 of file BVH.h.

BVH (  unsigned  ,
unsigned  ,
bool  ,
BVList::SplitStrategy 
) 
 

Definition at line 505 of file BVH.cc.

References BVH::_depthLimit, BVH::_leafLimit, BVH::_leftLeaf, BVH::_pPartner, BVH::_root, BVH::_scaleRatio, and BVH::_splitStrategy.

~BVH (   )  [virtual]
 

Definition at line 517 of file BVH.cc.

References BVH::_destroy_tree(), and BVH::_root.

Member Function Documentation

void __debug (  Node *  n,
int  d
)  [virtual]
 

Definition at line 769 of file BVH.cc.

References BVH::__debug(), BVList::__debug(), Geometry::__debug(), BVH::Node::bv, BVH::Node::leaf, BVH::Node::leftChild, BVH::Node::list, and BVH::Node::rightChild.

void __debug (  void   )  [virtual]
 

Reimplemented from SDS.

Definition at line 762 of file BVH.cc.

References BVH::_root.

Referenced by BVH::__debug().

void __get_edges (  Matrix4 *  ,
Node *  ,
unsigned  ,
unsigned  ,
int  ,
float *  ,
unsigned & 
) 
 

Definition at line 782 of file BVH.cc.

References BVH::_coordMat, BVH::Node::bv, Geometry::clone(), Mesh::getActVert1(), Mesh::getActVert2(), Mesh::goToNextSolid(), BVH::Node::leaf, BVH::Node::leftChild, Geometry::mesh(), Mesh::resetActSolid(), Mesh::resetEdgeWalkInSolid(), BVH::Node::rightChild, and Mesh::stepInEdgeWalkInSolid().

Referenced by BVH::__getEdges().

void __get_meshes (  Matrix4 *  ,
Node *  ,
unsigned  ,
unsigned  ,
int  ,
Mesh **  ,
unsigned & 
) 
 

Definition at line 846 of file BVH.cc.

References BVH::_coordMat, BVH::Node::bv, Geometry::clone(), BVH::Node::leaf, BVH::Node::leftChild, Geometry::mesh(), and BVH::Node::rightChild.

Referenced by BVH::__getMeshes().

float * __getEdges (  Matrix4 *  pMyTr,
unsigned  level,
int  rot,
unsigned &  size
) 
 

Definition at line 832 of file BVH.cc.

References BVH::__get_edges(), and BVH::_root.

Mesh ** __getMeshes (  Matrix4 *  pMyTr,
unsigned  level,
int  rot,
unsigned &  size
) 
 

Definition at line 871 of file BVH.cc.

References BVH::__get_meshes(), and BVH::_root.

bool _append (  SceneGraphObject *  ,
Geometry *  ,
Node *  ,
unsigned 
)  [protected]
 

Definition at line 9 of file BVH.cc.

References BVH::_create_bv(), BVH::_create_list(), BVH::_depthLimit, BVH::_enlarge_bv(), BVH::_leafLimit, BVH::_leftLeaf, BVH::_splitStrategy, BVList::append(), BVH::Node::bv, BVH::Node::leaf, BVH::Node::leftChild, BVList::length(), BVH::Node::list, BVH::Node::parent, BVH::Node::rightChild, BVH::Node::sibling, and BVList::split().

void _build_tree (  Node *  ,
unsigned 
)  [protected]
 

Definition at line 143 of file BVH.cc.

References BVH::_create_bv(), BVH::_depthLimit, BVH::_leafLimit, BVH::Node::bv, BVH::Node::leaf, BVList::length(), and BVH::Node::list.

Referenced by BVH::build().

void _collision (  Node *  ,
Geometry &  ,
List< SceneGraphObject > * 
)  [protected]
 

Definition at line 241 of file BVH.cc.

References List::append(), BVH::Node::bv, BVList::firstItem(), BVH::Node::leaf, BVH::Node::list, BVList::nextItem(), and Geometry::separation().

Referenced by BVH::collision().

virtual Geometry* _create_bv (  SceneGraphObject &   )  [protected, pure virtual]
 

Implemented in FDH14Tree, FDH6Tree, FDHTree, and SphereTree.

virtual Geometry* _create_bv (  Geometry &  ,
Geometry & 
)  [protected, pure virtual]
 

Implemented in FDH14Tree, FDH6Tree, FDHTree, and SphereTree.

virtual Geometry* _create_bv (  List< SceneGraphObject > &   )  [protected, pure virtual]
 

Implemented in FDH14Tree, FDH6Tree, FDHTree, and SphereTree.

Geometry * _create_bv (  BVList &   )  [protected]
 

Definition at line 229 of file BVH.cc.

References List::append(), BVList::firstItem(), and BVList::nextItem().

Referenced by BVH::_append(), BVH::_build_tree(), BVH::_rebuild_tree(), BVH::_remove_leaf(), BVH::collision(), and BVH::detach().

DistRot * _create_dist_rot (  BVH::Node *   )  [protected, virtual]
 

Reimplemented in FDH14Tree.

Definition at line 284 of file BVH.cc.

References BVH::_coordMat, BVH::_scaleRatio, and BVH::Node::bv.

Referenced by BVH::_dr_inner(), BVH::distance(), and BVH::separation().

virtual BVList* _create_list (   )  [protected, pure virtual]
 

Implemented in FDHTree, and SphereTree.

Referenced by BVH::_append().

void _destroy_tree (  Node *   )  [protected]
 

Definition at line 195 of file BVH.cc.

References BVH::Node::bv, BVH::Node::leaf, BVH::Node::leftChild, BVH::Node::list, and BVH::Node::rightChild.

Referenced by BVH::~BVH().

void _dr_init (  const Matrix4 *  ,
const Matrix4 *  ,
BVH * 
)  [protected, virtual]
 

Reimplemented in FDH14Tree.

Definition at line 289 of file BVH.cc.

References BVH::_coordMat, BVH::_myTrMat, BVH::_pPartner, BVH::_scaleRatio, and SDS::multiTrans().

Referenced by FDH14Tree::_dr_init(), BVH::distance(), and BVH::separation().

void _dr_inner (  DRInfo &  ,
Node *  ,
Node *  ,
unsigned 
)  [protected, virtual]
 

Definition at line 414 of file BVH.cc.

References BVH::_create_dist_rot(), BVH::_dr_leaf(), BVH::_pPartner, BVH::Node::bv, DistRot::distance(), BVH::DRInfo::hisMaxDepth, BVH::Node::leaf, BVH::DRInfo::leafInMe, BVH::Node::leftChild, BVH::DRInfo::maxDepth, BVH::DRInfo::minD, BVH::DRInfo::myMaxDepth, BVH::DRInfo::pDistRot, BVH::DRInfo::pLeaf, and BVH::Node::rightChild.

Referenced by BVH::distance(), and BVH::separation().

void _dr_leaf (  DRInfo &  ,
Node *  ,
unsigned 
)  [protected, virtual]
 

Definition at line 347 of file BVH.cc.

References BVH::_coordMat, BVH::_dr_primitives(), BVH::_myTrMat, BVH::_pPartner, BVH::Node::bv, DistRot::distance(), ESG_INVERSE_TR_DIR, BVH::Node::leaf, BVH::DRInfo::leafInMe, BVH::Node::leftChild, BVH::DRInfo::maxDepth, BVH::DRInfo::minD, BVH::DRInfo::pDir, BVH::DRInfo::pDistRot, BVH::DRInfo::pLeaf, BVH::DRInfo::pLeafA, BVH::DRInfo::pLeafB, and BVH::Node::rightChild.

Referenced by BVH::_dr_inner().

void _dr_primitives (  DRInfo &  ,
Node *  ,
Vector3 * 
)  [protected, virtual]
 

Definition at line 304 of file BVH.cc.

References BVH::DRInfo::DISTANCE, BVList::firstItem(), BVH::DRInfo::leafInMe, BVH::Node::list, MAXDOUBLE, BVH::DRInfo::minD, BVList::nextItem(), BVH::DRInfo::pLeaf, BVH::DRInfo::pLeafA, BVH::DRInfo::pLeafB, BVH::DRInfo::POINT_COLLISION, BVH::DRInfo::SEPARATION, and BVH::DRInfo::strategy.

Referenced by BVH::_dr_leaf().

void _dump (  const Node *  ,
const char *  ,
const char * 
)  [protected]
 

Definition at line 259 of file BVH.cc.

References BVH::Node::bv, Geometry::dump(), BVList::firstItem(), BVH::Node::leaf, BVH::Node::list, and BVList::nextItem().

Referenced by BVH::dump().

void _duplicate_attributes (  const SDS &   )  [protected, virtual]
 

Reimplemented from SDS.

Reimplemented in FDH14Tree, FDH6Tree, FDHTree, and SphereTree.

Definition at line 490 of file BVH.cc.

References BVH::_depthLimit, SDS::_duplicate_attributes(), BVH::_leafLimit, BVH::_leftLeaf, BVH::_pPartner, BVH::_root, BVH::_scaleRatio, and BVH::_splitStrategy.

Referenced by SphereTree::_duplicate_attributes(), and FDHTree::_duplicate_attributes().

virtual bool _enlarge_bv (  Geometry **  ,
Geometry & 
)  [protected, pure virtual]
 

Implemented in FDHTree, and SphereTree.

Referenced by BVH::_append().

void _rebuild_tree (  Node *   )  [protected]
 

Definition at line 216 of file BVH.cc.

References BVH::_create_bv(), BVH::Node::bv, BVH::Node::leaf, BVH::Node::leftChild, BVH::Node::list, and BVH::Node::rightChild.

Referenced by BVH::update().

void _remove_leaf (  Node *   )  [protected]
 

Definition at line 86 of file BVH.cc.

References BVH::_create_bv(), BVH::_leftLeaf, BVH::_root, BVH::Node::bv, BVH::Node::leftChild, BVH::Node::list, BVH::Node::parent, and BVH::Node::rightChild.

Referenced by BVH::detach().

int append (  SceneGraphObject *   )  [virtual]
 

Implements SDS.

Definition at line 532 of file BVH.cc.

References SDS::_intangibleChildren, List::append(), and SceneGraphObject::tangible().

bool build (  void   )  [virtual]
 

Implements SDS.

Definition at line 594 of file BVH.cc.

References BVH::_build_tree(), SDS::_delayBuild, and BVH::_root.

virtual SDS* clone (   )  const [pure virtual]
 

Implements SDS.

Implemented in FDH14Tree, FDH6Tree, FDHTree, and SphereTree.

Geometry ** collision (  Matrix4 *  ,
float  ,
float  ,
float  ,
float  ,
int * 
)  [virtual]
 

Definition at line 687 of file BVH.cc.

References BVH::_collision(), BVH::_create_bv(), SDS::_delayBuild, BVH::_root, BVH::_scaleRatio, BVH::Node::bv, List::firstItem(), List::length(), SDS::multiTrans(), and List::nextItem().

Referenced by OSGAdapter::collision().

InspectorSDS * createInspector (  unsigned   )  [virtual]
 

Implements SDS.

Definition at line 527 of file BVH.cc.

References BVH::InspectorBVH.

Iterator * createIterator (   )  [virtual]
 

Implements SDS.

Definition at line 522 of file BVH.cc.

References BVH::IteratorBVH.

Referenced by OSGAdapter::getVertices().

unsigned depthLimit (  void   )  const [inline]
 

Definition at line 159 of file BVH.h.

SceneGraphObject * detach (  SceneGraphObject::OID   )  [virtual]
 

Implements SDS.

Definition at line 567 of file BVH.cc.

References BVH::_create_bv(), BVH::_leftLeaf, BVH::_remove_leaf(), and BVH::Node::rightChild.

double distance (  Matrix4 *  ,
BVH &  ,
Matrix4 *  ,
Node **  ,
Node **  ,
Vector3 *  pDir = NULL,
unsigned  d1 = UINT_MAX,
unsigned  d2 = UINT_MAX
)  [virtual]
 

Definition at line 603 of file BVH.cc.

References BVH::_create_dist_rot(), SDS::_delayBuild, BVH::_dr_init(), BVH::_dr_inner(), BVH::_root, BVH::Node::bv, DistRot::distance(), BVH::DRInfo::DISTANCE, BVH::DRInfo::hisMaxDepth, MAXDOUBLE, BVH::DRInfo::minD, BVH::DRInfo::myMaxDepth, BVH::DRInfo::pDir, BVH::DRInfo::pDistRot, BVH::DRInfo::pLeafA, BVH::DRInfo::pLeafB, and BVH::DRInfo::strategy.

Referenced by OSGAdapter::distance().

virtual void dump (  const char *   )  [inline, virtual, inherited]
 

Reimplemented in OctTree.

Definition at line 80 of file SDS.h.

void dump (  const char *  ,
const char * 
)  [virtual]
 

Implements SDS.

Definition at line 739 of file BVH.cc.

References BVH::_depthLimit, BVH::_dump(), BVH::_leafLimit, BVH::_root, BVH::_splitStrategy, BVH::_treeDepth, BVList::SPLIT_BY_MAX_EXTENT, and BVList::SPLIT_BY_MAX_VARIATION.

unsigned leafLimit (  void   )  const [inline]
 

Definition at line 158 of file BVH.h.

Matrix4 * multiTrans (  const Matrix4 *  ,
const Matrix4 *  ,
double & 
)  [static, inherited]
 

Definition at line 116 of file SDS.cc.

Matrix4 * multiTrans (  const Matrix4 *  ,
const Matrix4 *  ,
Vector3 & 
)  [static, inherited]
 

Definition at line 10 of file SDS.cc.

Referenced by FDH14Tree::_dr_init(), BVH::_dr_init(), and BVH::collision().

bool separation (  Matrix4 *  ,
BVH &  ,
Matrix4 *  ,
Vector3 *  pDir = NULL,
unsigned  d1 = UINT_MAX,
unsigned  d2 = UINT_MAX
)  [virtual]
 

Definition at line 651 of file BVH.cc.

References BVH::_create_dist_rot(), SDS::_delayBuild, BVH::_dr_init(), BVH::_dr_inner(), BVH::_root, BVH::Node::bv, BVH::DRInfo::hisMaxDepth, BVH::DRInfo::minD, BVH::DRInfo::myMaxDepth, BVH::DRInfo::pDir, BVH::DRInfo::pDistRot, BVH::DRInfo::pLeafA, BVH::DRInfo::pLeafB, DistRot::separation(), BVH::DRInfo::SEPARATION, and BVH::DRInfo::strategy.

Referenced by OSGAdapter::separation().

bool update (  void   )  [virtual]
 

Implements SDS.

Definition at line 587 of file BVH.cc.

References SDS::_delayBuild, BVH::_rebuild_tree(), and BVH::_root.

Friends And Related Function Documentation

friend class BVDistance [friend]
 

Definition at line 40 of file BVH.h.

friend class BVExplorer [friend]
 

Definition at line 41 of file BVH.h.

friend class InspectorBVH [friend]
 

Definition at line 39 of file BVH.h.

Referenced by BVH::createInspector().

friend class IteratorBVH [friend]
 

Definition at line 38 of file BVH.h.

Referenced by BVH::createIterator().

Member Data Documentation

Matrix4 _coordMat [protected]
 

matrix transforming my coords to the partner's

Definition at line 125 of file BVH.h.

Referenced by BVH::__get_edges(), BVH::__get_meshes(), BVH::_create_dist_rot(), BVH::_dr_init(), and BVH::_dr_leaf().

bool _delayBuild [protected, inherited]
 

Definition at line 31 of file SDS.h.

Referenced by SDS::_duplicate_attributes(), OctTree::build(), BVH::build(), BVH::collision(), BVH::distance(), BVH::separation(), OctTree::update(), and BVH::update().

unsigned _depthLimit [protected]
 

Definition at line 121 of file BVH.h.

Referenced by BVH::_append(), BVH::_build_tree(), BVH::_duplicate_attributes(), BVH::BVH(), and BVH::dump().

struct esg::BVH::DRInfo _drInfo [protected]
 

List<SceneGraphObject> _intangibleChildren [protected, inherited]
 

Definition at line 32 of file SDS.h.

Referenced by OctTree::append(), Heap::append(), BVH::append(), IteratorSDS::firstChild(), and IteratorSDS::nextChild().

unsigned _leafLimit [protected]
 

Definition at line 120 of file BVH.h.

Referenced by BVH::_append(), BVH::_build_tree(), BVH::_duplicate_attributes(), BVH::BVH(), and BVH::dump().

Node* _leftLeaf [protected]
 

Definition at line 119 of file BVH.h.

Referenced by BVH::_append(), BVH::_duplicate_attributes(), BVH::_remove_leaf(), BVH::BVH(), and BVH::detach().

Matrix4 _myTrMat [protected]
 

Definition at line 124 of file BVH.h.

Referenced by BVH::_dr_init(), and BVH::_dr_leaf().

BVH* _pPartner [protected]
 

partner during collision detection

Definition at line 127 of file BVH.h.

Referenced by BVH::_dr_init(), BVH::_dr_inner(), BVH::_dr_leaf(), BVH::_duplicate_attributes(), and BVH::BVH().

Node* _root [protected]
 

Definition at line 118 of file BVH.h.

Referenced by BVH::__debug(), BVH::__getEdges(), BVH::__getMeshes(), BVH::_duplicate_attributes(), BVH::_remove_leaf(), BVH::build(), BVH::BVH(), BVH::collision(), BVH::distance(), BVH::dump(), BVH::separation(), BVH::update(), and BVH::~BVH().

double _scaleRatio [protected]
 

metric ratio scale from _pCoordMat

Definition at line 126 of file BVH.h.

Referenced by FDH14Tree::_create_dist_rot(), BVH::_create_dist_rot(), FDH14Tree::_dr_init(), BVH::_dr_init(), BVH::_duplicate_attributes(), BVH::BVH(), and BVH::collision().

BVList::SplitStrategy _splitStrategy [protected]
 

Definition at line 129 of file BVH.h.

Referenced by BVH::_append(), BVH::_duplicate_attributes(), BVH::BVH(), and BVH::dump().

unsigned _treeDepth [protected]
 

Definition at line 122 of file BVH.h.

Referenced by BVH::dump().

The documentation for this class was generated from the following files:
Generated on Wed Jun 28 12:24:35 2006 for esg by  doxygen 1.4.6