vcglib: base.h Source File

00001 /****************************************************************************
00002 * VCGLib                                                            o o     *
00003 * Visual and Computer Graphics Library                            o     o   *
00004 *                                                                _   O  _   *
00005 * Copyright(C) 2004                                                \/)\/    *
00006 * Visual Computing Lab                                            /\/|      *
00007 * ISTI - Italian National Research Council                           |      *
00008 *                                                                    \      *
00009 * All rights reserved.                                                      *
00010 *                                                                           *
00011 * This program is free software; you can redistribute it and/or modify      *   
00012 * it under the terms of the GNU General Public License as published by      *
00013 * the Free Software Foundation; either version 2 of the License, or         *
00014 * (at your option) any later version.                                       *
00015 *                                                                           *
00016 * This program is distributed in the hope that it will be useful,           *
00017 * but WITHOUT ANY WARRANTY; without even the implied warranty of            *
00018 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the             *
00019 * GNU General Public License (http://www.gnu.org/licenses/gpl.txt)          *
00020 * for more details.                                                         *
00021 *                                                                           *
00022 ****************************************************************************/
00023 
00024 /****************************************************************************
00025 History
00026 
00027 $Log: not supported by cvs2svn $
00028 Revision 1.2  2005/10/05 01:43:28  m_di_benedetto
00029 Removed "parent" pointer class member in Node class.
00030 
00031 Revision 1.1  2005/09/28 19:44:49  m_di_benedetto
00032 First Commit.
00033 
00034 
00035 ****************************************************************************/
00036 
00037 #ifndef __VCGLIB_AABBBINARYTREEBASE_H
00038 #define __VCGLIB_AABBBINARYTREEBASE_H
00039 
00040 // standard headers
00041 #include <assert.h>
00042 
00043 // stl headers
00044 #include <vector>
00045 
00046 // vcg headers
00047 #include <vcg/space/point3.h>
00048 #include <vcg/space/box3.h>
00049 
00050 /***************************************************************************/
00051 
00052 namespace vcg {
00053 
00054 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00055 class AABBBinaryTree {
00056         public:
00057                 typedef AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE> ClassType;
00058                 typedef OBJTYPE ObjType;
00059                 typedef ObjType * ObjPtr;
00060                 typedef SCALARTYPE ScalarType;
00061                 typedef NODEAUXDATATYPE NodeAuxDataType;
00062                 typedef Point3<ScalarType> CoordType;
00063 
00064                 typedef std::vector<ObjPtr> ObjPtrVector;
00065                 typedef typename ObjPtrVector::iterator ObjPtrVectorIterator;
00066                 typedef typename ObjPtrVector::const_iterator ObjPtrVectorConstIterator;
00067 
00068         public:
00069                 class AABBBinaryTreeNode {
00070                         public:
00071                                 CoordType boxCenter;
00072                                 CoordType boxHalfDims;
00073                                 ObjPtrVectorIterator oBegin;
00074                                 ObjPtrVectorIterator oEnd;
00075                                 AABBBinaryTreeNode * children[2];
00076                                 unsigned char splitAxis;
00077                                 NodeAuxDataType auxData;
00078 
00079                                 inline AABBBinaryTreeNode(void);
00080                                 inline ~AABBBinaryTreeNode(void);
00081 
00082                                 inline void Clear(void);
00083                                 inline bool IsLeaf(void) const;
00084                                 inline unsigned int ObjectsCount(void) const;
00085 
00086                                 inline unsigned int & Flags(void);
00087                                 inline const unsigned int & Flags(void) const;
00088 
00089                                 inline ScalarType & ScalarValue(void);
00090                                 inline const ScalarType & ScalarValue(void) const;
00091 
00092                                 inline int & IntValue(void);
00093                                 inline const int & IntValue(void) const;
00094 
00095                                 inline unsigned int & UIntValue(void);
00096                                 inline const unsigned int & UIntValue(void) const;
00097 
00098                                 inline void * & PtrValue(void);
00099                                 inline const void * & PtrValue(void) const;
00100 
00101                         protected:
00102                                 union SharedDataUnion {
00103                                         unsigned int flags;
00104                                         int intValue;
00105                                         unsigned int uintValue;
00106                                         ScalarType scalarValue;
00107                                         void * ptrValue;
00108                                 };
00109 
00110                                 SharedDataUnion sharedData;
00111                 };
00112 
00113                 typedef AABBBinaryTreeNode NodeType;
00114 
00115                 ObjPtrVector pObjects;
00116                 NodeType * pRoot;
00117 
00118                 inline AABBBinaryTree(void);
00119                 inline ~AABBBinaryTree(void);
00120 
00121                 inline void Clear(void);
00122 
00123                 template <class OBJITERATOR, class OBJITERATORPTRFUNCT, class OBJBOXFUNCT, class OBJBARYCENTERFUNCT>
00124                 inline bool Set(const OBJITERATOR & oBegin, const OBJITERATOR & oEnd, OBJITERATORPTRFUNCT & objPtr, OBJBOXFUNCT & objBox, OBJBARYCENTERFUNCT & objBarycenter, const unsigned int maxElemsPerLeaf = 1, const ScalarType & leafBoxMaxVolume = ((ScalarType)0), const bool useVariance = true);
00125 
00126         protected:
00127                 template <class OBJBOXFUNCT, class OBJBARYCENTERFUNCT>
00128                 inline static NodeType * BoundObjects(const ObjPtrVectorIterator & oBegin, const ObjPtrVectorIterator & oEnd, const unsigned int size, const unsigned int maxElemsPerLeaf, const ScalarType & leafBoxMaxVolume, const bool useVariance, OBJBOXFUNCT & getBox, OBJBARYCENTERFUNCT & getBarycenter);
00129 
00130                 template <class OBJBARYCENTERFUNCT>
00131                 inline static int BalanceMedian(const ObjPtrVectorIterator & oBegin, const ObjPtrVectorIterator & oEnd, const int size, const int splitAxis, OBJBARYCENTERFUNCT & getBarycenter, ObjPtrVectorIterator & medianIter);
00132 };
00133 
00134 
00135 
00136 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00137 AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::AABBBinaryTree(void) {
00138         this->pObjects.clear();
00139         this->pRoot = 0;
00140 }
00141 
00142 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00143 AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::~AABBBinaryTree(void) {
00144         this->pObjects.clear();
00145         delete this->pRoot;
00146 }
00147 
00148 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00149 void AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::Clear(void) {
00150         this->pObjects.clear();
00151         delete this->pRoot;
00152         this->pRoot = 0;
00153 }
00154 
00155 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00156 template <class OBJITERATOR, class OBJITERATORPTRFUNCT, class OBJBOXFUNCT, class OBJBARYCENTERFUNCT>
00157 bool AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::Set(const OBJITERATOR & oBegin, const OBJITERATOR & oEnd, OBJITERATORPTRFUNCT & objPtr, OBJBOXFUNCT & objBox, OBJBARYCENTERFUNCT & objBarycenter, const unsigned int maxElemsPerLeaf, const ScalarType & leafBoxMaxVolume, const bool useVariance) {
00158         this->Clear();
00159 
00160         if ((maxElemsPerLeaf == 0) && (leafBoxMaxVolume <= ((ScalarType)0))) {
00161                 return (false);
00162         }
00163 
00164         const unsigned int size = (unsigned int)std::distance(oBegin, oEnd);
00165 
00166         this->pObjects.reserve(size);
00167         for (OBJITERATOR oi=oBegin; oi!=oEnd; ++oi) {
00168                 this->pObjects.push_back(objPtr(*oi));
00169         }
00170 
00171         this->pRoot = ClassType::BoundObjects(this->pObjects.begin(), this->pObjects.end(), size, maxElemsPerLeaf, leafBoxMaxVolume, useVariance, objBox, objBarycenter);
00172 
00173         return (this->pRoot != 0);
00174 }
00175 
00176 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00177 template <class OBJBOXFUNCT, class OBJBARYCENTERFUNCT>
00178 typename AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::NodeType * AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::BoundObjects(const ObjPtrVectorIterator & oBegin, const ObjPtrVectorIterator & oEnd, const unsigned int size, const unsigned int maxElemsPerLeaf, const ScalarType & leafBoxMaxVolume, const bool useVariance, OBJBOXFUNCT & getBox, OBJBARYCENTERFUNCT & getBarycenter) {
00179         if (size <= 0) {
00180                 return (0);
00181         }
00182 
00183         NodeType * pNode = new NodeType();
00184         if (pNode == 0) {
00185                 return (0);
00186         }
00187 
00188         pNode->children[0] = 0;
00189         pNode->children[1] = 0;
00190 
00191         pNode->oBegin = oBegin;
00192         pNode->oEnd = oEnd;
00193 
00194         Box3<ScalarType> bbox;
00195         bbox.SetNull();
00196         for (ObjPtrVectorConstIterator oi=pNode->oBegin; oi!=pNode->oEnd; ++oi) {
00197                 Box3<ScalarType> tbox;
00198                 getBox(*(*oi), tbox);
00199                 bbox.Add(tbox);
00200         }
00201 
00202         pNode->boxCenter = bbox.Center();
00203         pNode->boxHalfDims = bbox.Dim() / ((ScalarType)2);
00204 
00205         const bool bMaxObjectsReached = (((maxElemsPerLeaf > 0) && (size <= maxElemsPerLeaf)) || (size == 1));
00206         const bool bMaxVolumeReached = ((leafBoxMaxVolume > ((ScalarType)0)) && (bbox.Volume() <= leafBoxMaxVolume));
00207         const bool isLeaf = bMaxObjectsReached || bMaxVolumeReached;
00208 
00209         if (isLeaf) {
00210                 pNode->splitAxis = 0;
00211                 return (pNode);
00212         }
00213 
00214         CoordType pSplit;
00215 
00216         if (useVariance) {
00217                 CoordType mean((ScalarType)0, (ScalarType)0, (ScalarType)0);
00218                 CoordType variance((ScalarType)0, (ScalarType)0, (ScalarType)0);
00219                 for (ObjPtrVectorIterator oi=oBegin; oi!=oEnd; ++oi) {
00220                         CoordType bc;
00221                         getBarycenter(*(*oi), bc);
00222                         mean += bc;
00223                         variance[0] += bc[0] * bc[0];
00224                         variance[1] += bc[1] * bc[1];
00225                         variance[2] += bc[2] * bc[2];
00226                 }
00227                 variance[0] -= (mean[0] * mean[0]) / ((ScalarType)size);
00228                 variance[1] -= (mean[1] * mean[1]) / ((ScalarType)size);
00229                 variance[2] -= (mean[2] * mean[2]) / ((ScalarType)size);
00230                 pSplit = variance;
00231         }
00232         else {
00233                 pSplit = pNode->boxHalfDims;
00234         }
00235 
00236         ScalarType maxDim = pSplit[0];
00237         unsigned char splitAxis = 0;
00238         if (maxDim < pSplit[1]) {
00239                 maxDim = pSplit[1];
00240                 splitAxis = 1;
00241         }
00242         if (maxDim < pSplit[2]) {
00243                 maxDim = pSplit[2];
00244                 splitAxis = 2;
00245         }
00246 
00247         pNode->splitAxis = splitAxis;
00248 
00249         ObjPtrVectorIterator median;
00250         const int lSize = ClassType::BalanceMedian(pNode->oBegin, pNode->oEnd, size, splitAxis, getBarycenter, median);
00251         const int rSize = size - lSize;
00252 
00253         if (lSize > 0) {
00254                 pNode->children[0] = ClassType::BoundObjects(pNode->oBegin, median, lSize, maxElemsPerLeaf, leafBoxMaxVolume, useVariance, getBox, getBarycenter);
00255                 if (pNode->children[0] == 0) {
00256                         delete pNode;
00257                         return (0);
00258                 }
00259         }
00260 
00261         if (rSize > 0) {
00262                 pNode->children[1] = ClassType::BoundObjects(median, pNode->oEnd, rSize, maxElemsPerLeaf, leafBoxMaxVolume, useVariance, getBox, getBarycenter);
00263                 if (pNode->children[1] == 0) {
00264                         delete pNode;
00265                         return (0);
00266                 }
00267         }
00268 
00269         return (pNode);
00270 }
00271 
00272 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00273 template <class OBJBARYCENTERFUNCT>
00274 int AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::BalanceMedian(const ObjPtrVectorIterator & oBegin, const ObjPtrVectorIterator & oEnd, const int size, const int splitAxis, OBJBARYCENTERFUNCT & getBarycenter, ObjPtrVectorIterator & medianIter) {
00275         const int iMedian = (size + 1) / 2;
00276 
00277         ObjPtrVectorIterator l, r, i, j;
00278         ObjPtr iTmp;
00279         ScalarType pos;
00280         ObjPtrVectorIterator median = oBegin + iMedian;
00281         CoordType bc;
00282 
00283         l = oBegin;
00284         r = oEnd - 1;
00285 
00286         while (l < r) {
00287                 getBarycenter(*(*r), bc);
00288                 pos = bc[splitAxis];
00289 
00290                 i = l;
00291                 j = r - 1;
00292 
00293                 while (true) {
00294                         getBarycenter(*(*i), bc);
00295                         while ((bc[splitAxis] <= pos) && (i < r)) {
00296                                 i++;
00297                                 getBarycenter(*(*i), bc);
00298                         }
00299                         getBarycenter(*(*j), bc);
00300                         while ((bc[splitAxis] > pos) && (j > l)) {
00301                                 j--;
00302                                 getBarycenter(*(*j), bc);
00303                         }
00304                         if (i >= j) {
00305                                 break;
00306                         }
00307                         iTmp = (*i);
00308                         (*i) = (*j);
00309                         (*j) = iTmp;
00310                 }
00311 
00312                 iTmp = (*i);
00313                 (*i) = (*r);
00314                 (*r) = iTmp;
00315 
00316                 if (i >= (median)) {
00317                         r = i - 1;
00318                 }
00319                 if (i <= (median)) {
00320                         l = i + 1;
00321                 }
00322         }
00323 
00324         medianIter = median;
00325 
00326         return (iMedian);
00327 }
00328 
00329 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00330 AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::AABBBinaryTreeNode::AABBBinaryTreeNode(void) {
00331         this->children[0] = 0;
00332         this->children[1] = 0;
00333 }
00334 
00335 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00336 AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::AABBBinaryTreeNode::~AABBBinaryTreeNode(void) {
00337         delete this->children[0];
00338         delete this->children[1];
00339 }
00340 
00341 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00342 void AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::AABBBinaryTreeNode::Clear(void) {
00343         delete this->children[0];
00344         this->children[0] = 0;
00345 
00346         delete this->children[1];
00347         this->children[1] = 0;
00348 }
00349 
00350 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00351 bool AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::AABBBinaryTreeNode::IsLeaf(void) const {
00352         return ((this->children[0] == 0) && (this->children[1] == 0));
00353 }
00354 
00355 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00356 unsigned int AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::AABBBinaryTreeNode::ObjectsCount(void) const {
00357         return ((unsigned int)(std::distance(this->oBegin, this->oEnd)));
00358 }
00359 
00360 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00361 unsigned int & AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::AABBBinaryTreeNode::Flags(void) {
00362         return (this->sharedData.flags);
00363 }
00364 
00365 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00366 const unsigned int & AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::AABBBinaryTreeNode::Flags(void) const {
00367         return (this->sharedData.flags);
00368 }
00369 
00370 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00371 int & AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::AABBBinaryTreeNode::IntValue(void) {
00372         return (this->sharedData.intValue);
00373 }
00374 
00375 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00376 const int & AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::AABBBinaryTreeNode::IntValue(void) const {
00377         return (this->sharedData.intValue);
00378 }
00379 
00380 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00381 unsigned int & AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::AABBBinaryTreeNode::UIntValue(void) {
00382         return (this->sharedData.uintValue);
00383 }
00384 
00385 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00386 const unsigned int & AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::AABBBinaryTreeNode::UIntValue(void) const {
00387         return (this->sharedData.uintValue);
00388 }
00389 
00390 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00391 typename AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::ScalarType & AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::AABBBinaryTreeNode::ScalarValue(void) {
00392         return (this->sharedData.scalarValue);
00393 }
00394 
00395 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00396 const typename AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::ScalarType & AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::AABBBinaryTreeNode::ScalarValue(void) const {
00397         return (this->sharedData.scalarValue);
00398 }
00399 
00400 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00401 void * & AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::AABBBinaryTreeNode::PtrValue(void) {
00402         return (this->sharedData.ptrValue);
00403 }
00404 
00405 template <class OBJTYPE, class SCALARTYPE, class NODEAUXDATATYPE>
00406 const void * & AABBBinaryTree<OBJTYPE, SCALARTYPE, NODEAUXDATATYPE>::AABBBinaryTreeNode::PtrValue(void) const {
00407         return (this->sharedData.ptrValue);
00408 }
00409 
00410 }       // end namespace vcg
00411 
00412 #endif // #ifndef __VCGLIB_AABBBINARYTREEBASE_H