Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | Directories | File List | Namespace Members | Class Members | File Members

DynamicOctree< OBJ, PREC > Class Template Reference

#include <octree.h>

Collaboration diagram for DynamicOctree< OBJ, PREC >:

Collaboration graph
List of all members.

Public Member Functions

 DynamicOctree (const Point3< PREC > &cellCenterPos, const float exclusionFactor)
void insertObject (const OBJ &, const PREC)
void rebuildAndSort (StaticOctree< OBJ, PREC > *&, OBJ *&)
 ~DynamicOctree ()

Private Types

typedef PREC() ExclusionFactorDecayFunction (const PREC)
typedef bool() LimitingFactorPredicate (const OBJ &, const float)
typedef std::vector< const
OBJ * > 		ObjectList
typedef bool() StraddlingPredicate (const Point3< PREC > &, const OBJ &, const float)

Private Member Functions

void add (const OBJ &)
DynamicOctree * getChild (const OBJ &, const Point3< PREC > &)
void sortIntoChildNodes ()
void split (const PREC)

Private Attributes

DynamicOctree ** _children
ObjectList * _objects
Point3< PREC > cellCenterPos
PREC exclusionFactor

Static Private Attributes

static ExclusionFactorDecayFunction * decayFunction = dsoAbsoluteMagnitudeDecayFunction
static LimitingFactorPredicate * limitingFactorPredicate = dsoAbsoluteMagnitudePredicate
static unsigned int SPLIT_THRESHOLD = 10
static StraddlingPredicate * straddlingPredicate = dsoStraddlesNodesPredicate

template<class OBJ, class PREC>
class DynamicOctree< OBJ, PREC >

Member Typedef Documentation

template<class OBJ, class PREC>
typedef PREC() DynamicOctree< OBJ, PREC >::ExclusionFactorDecayFunction(const PREC) [private]
 

Definition at line 49 of file octree.h.

template<class OBJ, class PREC>
typedef bool() DynamicOctree< OBJ, PREC >::LimitingFactorPredicate(const OBJ &, const float) [private]
 

Definition at line 47 of file octree.h.

template<class OBJ, class PREC>
typedef std::vector<const OBJ*> DynamicOctree< OBJ, PREC >::ObjectList [private]
 

Definition at line 45 of file octree.h.

template<class OBJ, class PREC>
typedef bool() DynamicOctree< OBJ, PREC >::StraddlingPredicate(const Point3< PREC > &, const OBJ &, const float) [private]
 

Definition at line 48 of file octree.h.

Constructor & Destructor Documentation

template<class OBJ, class PREC>
DynamicOctree< OBJ, PREC >::DynamicOctree (  const Point3< PREC > &  cellCenterPos,
const float  exclusionFactor
)  [inline]
 

Definition at line 155 of file octree.h.

Referenced by DynamicOctree< OBJ, PREC >::split().

00156                                                                                    :
00157         _children      (NULL),
00158         cellCenterPos  (cellCenterPos),
00159         exclusionFactor(exclusionFactor),
00160         _objects       (NULL)
00161 {
00162 }

template<class OBJ, class PREC>
DynamicOctree< OBJ, PREC >::~DynamicOctree (   )  [inline]
 

Definition at line 166 of file octree.h.

References DynamicOctree< OBJ, PREC >::_children.

00167 {
00168     if (_children != NULL)
00169     {
00170         for (int i=0; i<8; ++i)
00171         {
00172             delete _children[i];
00173         }
00174 
00175         delete[] _children;
00176     }
00177 }

Member Function Documentation

template<class OBJ, class PREC>
void DynamicOctree< OBJ, PREC >::add (  const OBJ &   )  [inline, private]
 

Definition at line 211 of file octree.h.

References DynamicOctree< OBJ, PREC >::_objects.

Referenced by DynamicOctree< OBJ, PREC >::insertObject(), and DynamicOctree< OBJ, PREC >::sortIntoChildNodes().

00212 {
00213     if (_objects == NULL)
00214         _objects = new ObjectList;
00215 
00216     _objects->push_back(&obj);
00217 }

template<class OBJ, class PREC>
DynamicOctree* DynamicOctree< OBJ, PREC >::getChild (  const OBJ &  ,
const Point3< PREC > & 
)  [private]
 

Referenced by DynamicOctree< OBJ, PREC >::insertObject(), and DynamicOctree< OBJ, PREC >::sortIntoChildNodes().

template<class OBJ, class PREC>
void DynamicOctree< OBJ, PREC >::insertObject (  const OBJ &  ,
const   PREC
)  [inline]
 

Definition at line 181 of file octree.h.

References DynamicOctree< OBJ, PREC >::_children, DynamicOctree< OBJ, PREC >::_objects, DynamicOctree< OBJ, PREC >::add(), DynamicOctree< OBJ, PREC >::cellCenterPos, DynamicOctree< OBJ, PREC >::exclusionFactor, DynamicOctree< OBJ, PREC >::getChild(), DynamicOctree< OBJ, PREC >::limitingFactorPredicate, DynamicOctree< OBJ, PREC >::split(), and DynamicOctree< OBJ, PREC >::straddlingPredicate.

Referenced by StarDatabase::buildOctree(), and DSODatabase::buildOctree().

00182 {
00183     // If the object can't be placed into this node's children, then put it here:
00184     if (limitingFactorPredicate(obj, exclusionFactor) || straddlingPredicate(cellCenterPos, obj, exclusionFactor) )
00185         add(obj);
00186     else
00187     {
00188         // If we haven't allocated child nodes yet, try to fit
00189         // the object in this node, even though it could be put
00190         // in a child. Only if there are more than SPLIT_THRESHOLD
00191         // objects in the node will we attempt to place the
00192         // object into a child node.  This is done in order
00193         // to avoid having the octree degenerate into one object
00194         // per node.
00195         if (_children == NULL)
00196         {
00197             // Make sure that there's enough room left in this node
00198             if (_objects != NULL && _objects->size() >= DynamicOctree<OBJ, PREC>::SPLIT_THRESHOLD)
00199                 split(scale * 0.5f);
00200             add(obj);
00201         }
00202         else
00203             // We've already allocated child nodes; place the object
00204             // into the appropriate one.
00205             this->getChild(obj, cellCenterPos)->insertObject(obj, scale * (PREC) 0.5);
00206     }
00207 }

template<class OBJ, class PREC>
void DynamicOctree< OBJ, PREC >::rebuildAndSort (  StaticOctree< OBJ, PREC > *&  ,
OBJ *& 
)  [inline]
 

Definition at line 263 of file octree.h.

References DynamicOctree< OBJ, PREC >::_children, DynamicOctree< OBJ, PREC >::_objects, DynamicOctree< OBJ, PREC >::cellCenterPos, and DynamicOctree< OBJ, PREC >::exclusionFactor.

Referenced by StarDatabase::buildOctree(), and DSODatabase::buildOctree().

00264 {
00265     OBJ* _firstObject = _sortedObjects;
00266 
00267     if (_objects != NULL)
00268         for (typename ObjectList::const_iterator iter = _objects->begin(); iter != _objects->end(); ++iter)
00269         {
00270             *_sortedObjects++ = **iter;
00271         }
00272 
00273     unsigned int nObjects  = (unsigned int) (_sortedObjects - _firstObject);
00274     _staticNode            = new StaticOctree<OBJ, PREC>(cellCenterPos, exclusionFactor, _firstObject, nObjects);
00275 
00276     if (_children != NULL)
00277     {
00278         _staticNode->_children    = new StaticOctree<OBJ, PREC>*[8];
00279 
00280         for (int i=0; i<8; ++i)
00281             _children[i]->rebuildAndSort(_staticNode->_children[i], _sortedObjects);
00282     }
00283 }

template<class OBJ, class PREC>
void DynamicOctree< OBJ, PREC >::sortIntoChildNodes (   )  [inline, private]
 

Definition at line 244 of file octree.h.

References DynamicOctree< OBJ, PREC >::_objects, DynamicOctree< OBJ, PREC >::add(), DynamicOctree< OBJ, PREC >::cellCenterPos, DynamicOctree< OBJ, PREC >::exclusionFactor, DynamicOctree< OBJ, PREC >::getChild(), and DynamicOctree< OBJ, PREC >::straddlingPredicate.

Referenced by DynamicOctree< OBJ, PREC >::split().

00245 {
00246     unsigned int nKeptInParent = 0;
00247 
00248     for (unsigned int i=0; i<_objects->size(); ++i)
00249     {
00250         const OBJ& obj    = *(*_objects)[i];
00251 
00252         if (straddlingPredicate(cellCenterPos, obj, exclusionFactor) )
00253             (*_objects)[nKeptInParent++] = (*_objects)[i];
00254         else
00255             this->getChild(obj, cellCenterPos)->add(obj);
00256     }
00257 
00258     _objects->resize(nKeptInParent);
00259 }

template<class OBJ, class PREC>
void DynamicOctree< OBJ, PREC >::split (  const   PREC  )  [inline, private]
 

Definition at line 221 of file octree.h.

References DynamicOctree< OBJ, PREC >::_children, DynamicOctree< OBJ, PREC >::cellCenterPos, DynamicOctree< OBJ, PREC >::decayFunction, DynamicOctree< OBJ, PREC >::DynamicOctree(), DynamicOctree< OBJ, PREC >::exclusionFactor, DynamicOctree< OBJ, PREC >::sortIntoChildNodes(), Point3< T >::x, XPos, Point3< T >::y, YPos, Point3< T >::z, and ZPos.

Referenced by DynamicOctree< OBJ, PREC >::insertObject().

00222 {
00223     _children = new DynamicOctree*[8];
00224 
00225     for (int i=0; i<8; ++i)
00226     {
00227         Point3<PREC> centerPos    = cellCenterPos;
00228 
00229         centerPos.x     += ((i & XPos) != 0) ? scale : -scale;
00230         centerPos.y     += ((i & YPos) != 0) ? scale : -scale;
00231         centerPos.z     += ((i & ZPos) != 0) ? scale : -scale;
00232 
00233         _children[i] = new DynamicOctree(centerPos,
00234                                          decayFunction(exclusionFactor));
00235     }
00236     sortIntoChildNodes();
00237 }

Member Data Documentation

template<class OBJ, class PREC>
DynamicOctree** DynamicOctree< OBJ, PREC >::_children [private]
 

Definition at line 72 of file octree.h.

Referenced by DynamicOctree< OBJ, PREC >::insertObject(), DynamicOctree< OBJ, PREC >::rebuildAndSort(), DynamicOctree< OBJ, PREC >::split(), and DynamicOctree< OBJ, PREC >::~DynamicOctree().

template<class OBJ, class PREC>
ObjectList* DynamicOctree< OBJ, PREC >::_objects [private]
 

Definition at line 75 of file octree.h.

Referenced by DynamicOctree< OBJ, PREC >::add(), DynamicOctree< OBJ, PREC >::insertObject(), DynamicOctree< OBJ, PREC >::rebuildAndSort(), and DynamicOctree< OBJ, PREC >::sortIntoChildNodes().

template<class OBJ, class PREC>
Point3<PREC> DynamicOctree< OBJ, PREC >::cellCenterPos [private]
 

Definition at line 73 of file octree.h.

Referenced by DynamicOctree< OBJ, PREC >::insertObject(), DynamicOctree< OBJ, PREC >::rebuildAndSort(), DynamicOctree< OBJ, PREC >::sortIntoChildNodes(), and DynamicOctree< OBJ, PREC >::split().

template<class OBJ, class PREC>
DynamicStarOctree::ExclusionFactorDecayFunction * DynamicStarOctree::decayFunction = dsoAbsoluteMagnitudeDecayFunction [static, private]
 

Definition at line 73 of file staroctree.cpp.

Referenced by DynamicOctree< OBJ, PREC >::split().

template<class OBJ, class PREC>
PREC DynamicOctree< OBJ, PREC >::exclusionFactor [private]
 

Definition at line 74 of file octree.h.

Referenced by DynamicOctree< OBJ, PREC >::insertObject(), DynamicOctree< OBJ, PREC >::rebuildAndSort(), DynamicOctree< OBJ, PREC >::sortIntoChildNodes(), and DynamicOctree< OBJ, PREC >::split().

template<class OBJ, class PREC>
DynamicStarOctree::LimitingFactorPredicate * DynamicStarOctree::limitingFactorPredicate = dsoAbsoluteMagnitudePredicate [static, private]
 

Definition at line 69 of file staroctree.cpp.

Referenced by DynamicOctree< OBJ, PREC >::insertObject().

template<class OBJ, class PREC>
unsigned int DynamicStarOctree::SPLIT_THRESHOLD = 10 [static, private]
 

Definition at line 67 of file staroctree.cpp.

template<class OBJ, class PREC>
DynamicStarOctree::StraddlingPredicate * DynamicStarOctree::straddlingPredicate = dsoStraddlesNodesPredicate [static, private]
 

Definition at line 71 of file staroctree.cpp.

Referenced by DynamicOctree< OBJ, PREC >::insertObject(), and DynamicOctree< OBJ, PREC >::sortIntoChildNodes().

The documentation for this class was generated from the following files:
Generated on Sat Jan 14 22:33:18 2006 for Celestia by  doxygen 1.4.1