Changeset 8415 for OpenSceneGraph/trunk/examples/osgkdtree/osgkdtree.cpp

Timestamp:

06/06/08 15:21:27 (5 years ago)

Author:

robert

Message:

Introduce a lower overhead data structure for leaves.

Files:

• OpenSceneGraph/trunk/examples/osgkdtree/osgkdtree.cpp (modified) (25 diffs)

OpenSceneGraph/trunk/examples/osgkdtree/osgkdtree.cpp

@@ -45 +45 @@
 {
 
+typedef int value_type;
+typedef std::vector< value_type >   Indices;
+
+//#define LEAF_OBJECT
+//#define VERBOSE_OUTPUT
+
+#ifdef LEAF_OBJECT
 class KDNode
 {
@@ -50 +57 @@
     
         KDNode():
-            _leftChild(0),
-            _rightChild(0) {}
+            first(0),
+            second(0) {}
     
         KDNode(const KDNode& rhs):
-            _leftChild(rhs._leftChild),
-            _rightChild(rhs._rightChild) {}
+            first(rhs.first),
+            second(rhs.second) {}
 
         KDNode& operator = (const KDNode& rhs)
         {
-            _leftChild = rhs._leftChild;
-            _rightChild = rhs._rightChild;
+            first = rhs.first;
+            second = rhs.second;
             return *this;
         }
 
-        typedef short value_type;
-
-        value_type _leftChild;
-        value_type _rightChild;
+        value_type first;
+        value_type second;
 };
 
@@ -75 +80 @@
     
         KDLeaf() {}
-    
-        typedef unsigned int index_type;
-        typedef std::vector< index_type > Indices;
 
         Indices _vertexIndices;        
@@ -86 +88 @@
 };
 
+#else
+    typedef std::pair< value_type, value_type> KDNode;
+    typedef std::pair< value_type, value_type> KDLeaf;
+#endif
+
+
 class KDTree : public osg::Shape
 {
@@ -97 +105 @@
 
         META_Shape(osg, KDTree)
+        
     
         typedef std::vector< unsigned int > AxisStack;
-        typedef std::vector< KDNode > KDNodeList;
+        typedef std::vector< KDNode >       KDNodeList;
+
+#ifdef LEAF_OBJECT
         typedef std::vector< osg::ref_ptr<KDLeaf> > KDLeafList;
-        
-        
+
         /// note, leafNum is negative to distinguish from nodeNum
         int addLeaf(KDLeaf* leaf) { int num = _kdLeaves.size(); _kdLeaves.push_back(leaf); return -(num+1); }
@@ -131 +141 @@
             return _kdLeaves[num].get();
         }
+
+#else
+        typedef std::vector< KDLeaf > KDLeafList;
+
+        /// note, leafNum is negative to distinguish from nodeNum
+        int addLeaf(const KDLeaf& leaf) { int num = _kdLeaves.size(); _kdLeaves.push_back(leaf); return -(num+1); }
+
+        int replaceLeaf(int leafNum, const KDLeaf& leaf)
+        {
+            int num = -leafNum-1; 
+            
+            if (num>_kdLeaves.size()-1)
+            {
+                osg::notify(osg::NOTICE)<<"Warning: replaceChild("<<leafNum<<", leaf), num = "<<num<<" _kdLeaves.size()="<<_kdLeaves.size()<<std::endl;
+                return leafNum;
+            }
+            
+            _kdLeaves[num] = leaf; return leafNum;
+        }
+
+        /// note, leafNum is negative to distinguish from nodeNum
+        KDLeaf& getLeaf(int leafNum)
+        {
+            int num = -leafNum-1;
+            if (num<0 || num>_kdLeaves.size()-1)
+            {
+                osg::notify(osg::NOTICE)<<"Warning: getLeaf("<<leafNum<<", num = "<<num<<") _kdLeaves.size()="<<_kdLeaves.size()<<std::endl;
+            }
+
+            return _kdLeaves[num];
+        }
+#endif        
+        
         
         int addNode(const KDNode& node)
@@ -156 +199 @@
         AxisStack                       _axisStack;
         KDNodeList                      _kdNodes;
-        KDLeafList                      _kdLeaves; 
+        KDLeafList                      _kdLeaves;
+        Indices                         _vertexIndices;
 };
 
@@ -174 +218 @@
     
 
-        void traverse(KDLeaf& leaf, unsigned int level)
+        void traverse(KDTree& tree, KDLeaf& leaf, unsigned int level)
         {
             output(level)<<"leaf("<<level<<") { ";
 
+#ifdef LEAF_OBJECT
             for(unsigned int i=0; i<leaf._vertexIndices.size(); ++i)
             {
@@ -183 +228 @@
                 else osg::notify(osg::NOTICE)<<", "<<leaf._vertexIndices[i];                
             }
-
+#else
+            unsigned int end = leaf.first+leaf.second;
+            for(unsigned int i=leaf.first; i<end; ++i)
+            {
+                if (i==leaf.first) osg::notify(osg::NOTICE)<<tree._vertexIndices[i];
+                else osg::notify(osg::NOTICE)<<", "<<tree._vertexIndices[i];                
+            }
+#endif
             osg::notify(osg::NOTICE)<<"}"<<std::endl;;
             
         }
 
-        void traverse(KDTree& tree, KDNode::value_type nodeIndex, unsigned int level)
+        void traverse(KDTree& tree, value_type nodeIndex, unsigned int level)
         {
             output(level)<<"traverse("<<nodeIndex<<", "<< level<<") { "<<std::endl;
@@ -195 +247 @@
             {        
                 KDNode& node = tree._kdNodes[nodeIndex];
-                if (node._leftChild) traverse(tree,node._leftChild,level+1);
+                if (node.first) traverse(tree,node.first,level+1);
                 else output(level+1)<<"empty left child()"<<std::endl;
                 
-                if (node._rightChild) traverse(tree,node._rightChild,level+1);
+                if (node.second) traverse(tree,node.second,level+1);
                 else output(level+1)<<"empty right child()"<<std::endl;
             }
             else 
             {
-                KDNode::value_type leafIndex = -nodeIndex-1;
+                value_type leafIndex = -nodeIndex-1;
+#ifdef LEAF_OBJECT
                 KDLeaf& leaf = *(tree._kdLeaves[leafIndex]);
-                traverse(leaf, level);
+#else
+                KDLeaf& leaf = tree._kdLeaves[leafIndex];
+#endif
+                traverse(tree, leaf, level);
             }
 
@@ -221 +277 @@
             else if (!tree._kdLeaves.empty())
             {
-                traverse(*tree._kdLeaves.front(), 0);
+#ifdef LEAF_OBJECT
+                traverse(tree, *tree._kdLeaves.front(), 0);
+#else
+                traverse(tree, tree._kdLeaves.front(), 0);
+#endif
             }
         }
@@ -269 +329 @@
 KDTree* KDTreeBuilder::createKDTree(osg::Geometry* geometry)
 {
-#if VERBOSE_OUTPUT    
+#ifdef VERBOSE_OUTPUT    
     osg::notify(osg::NOTICE)<<"osg::KDTreeBuilder::createKDTree()"<<std::endl;
 #endif
@@ -283 +343 @@
     unsigned int estimatedSize = (unsigned int)(float(vertices->size())/float(_targetNumVerticesPerLeaf)*1.5);
 
-#if VERBOSE_OUTPUT    
+#ifdef VERBOSE_OUTPUT    
     osg::notify(osg::NOTICE)<<"kdTree->_kdNodes.reserve()="<<estimatedSize<<std::endl<<std::endl;
 #endif
@@ -295 +355 @@
     _numVerticesProcessed += vertices->size();
 
+#ifdef LEAF_OBJECT
     // create initial leaf list    
     KDLeaf* leaf = new KDLeaf;
@@ -302 +363 @@
         leaf->_vertexIndices.push_back(i);
     }
-
+#else
+
+    kdTree->_vertexIndices.reserve(vertices->size());
+    for(unsigned int i=0; i<vertices->size(); ++i)
+    {
+        kdTree->_vertexIndices.push_back(i);
+    }
+    KDLeaf leaf(0, kdTree->_vertexIndices.size());
+
+#endif
+
+    int leafNum = kdTree->addLeaf(leaf);
     osg::BoundingBox bb = kdTree->_bb;
-    
-    int leafNum = kdTree->addLeaf(leaf);
     int nodeNum = divide(*kdTree, bb, leafNum, 0);
-    
-#if VERBOSE_OUTPUT    
+
+
+
+    
+#ifdef VERBOSE_OUTPUT    
     osg::notify(osg::NOTICE)<<"Root nodeNum="<<nodeNum<<std::endl;
 #endif
     
-#if VERBOSE_OUTPUT    
+#ifdef VERBOSE_OUTPUT    
     
     KDTreeTraverser traverser;
@@ -334 +407 @@
                          kdTree._bb.zMax()-kdTree._bb.zMin());
 
-#if VERBOSE_OUTPUT    
+#ifdef VERBOSE_OUTPUT    
     osg::notify(osg::NOTICE)<<"computeDivisions("<<_maxNumLevels<<") "<<dimensions<< " { "<<std::endl;
 #endif
@@ -355 +428 @@
         dimensions[axis] /= 2.0f;
 
-#if VERBOSE_OUTPUT    
+#ifdef VERBOSE_OUTPUT    
         osg::notify(osg::NOTICE)<<"  "<<level<<", "<<dimensions<<", "<<axis<<std::endl;
 #endif
     }
 
-#if VERBOSE_OUTPUT    
+#ifdef VERBOSE_OUTPUT    
     osg::notify(osg::NOTICE)<<"}"<<std::endl;
 #endif
@@ -372 +445 @@
     int axis = kdTree._axisStack[level];
 
-#if VERBOSE_OUTPUT    
+#ifdef VERBOSE_OUTPUT    
     //osg::notify(osg::NOTICE)<<"divide("<<nodeIndex<<", "<<level<< "), axis="<<axis<<std::endl;
 #endif
@@ -378 +451 @@
     if (nodeIndex>=0)
     {
-#if VERBOSE_OUTPUT    
+#ifdef VERBOSE_OUTPUT    
         osg::notify(osg::NOTICE)<<"  divide node"<<std::endl;
 #endif
@@ -386 +459 @@
     else
     {    
+
+#ifdef LEAF_OBJECT
         if (kdTree.getLeaf(nodeIndex)->_vertexIndices.size()<=_targetNumVerticesPerLeaf) return nodeIndex;
-    
+#else
+        if (kdTree.getLeaf(nodeIndex).second<=_targetNumVerticesPerLeaf) return nodeIndex;
+#endif    
         //osg::notify(osg::NOTICE)<<"  divide leaf"<<std::endl;
         
@@ -397 +474 @@
         float mid = (original_min+original_max)*0.5f;
 
+#ifdef LEAF_OBJECT
         {
             osg::ref_ptr<KDLeaf> leaf = kdTree.getLeaf(nodeIndex);
@@ -424 +502 @@
             {
                 //osg::notify(osg::NOTICE)<<"LeftLeaf empty"<<std::endl;
-                kdTree.getNode(nodeNum)._leftChild = 0;
-                kdTree.getNode(nodeNum)._rightChild = kdTree.replaceLeaf(nodeIndex, rightLeaf.get());
+                kdTree.getNode(nodeNum).first = 0;
+                kdTree.getNode(nodeNum).second = kdTree.replaceLeaf(nodeIndex, rightLeaf.get());
             }
             else if (rightLeaf->_vertexIndices.empty())
             {
                 //osg::notify(osg::NOTICE)<<"RightLeaf empty"<<std::endl;
-                kdTree.getNode(nodeNum)._leftChild = kdTree.replaceLeaf(nodeIndex, leftLeaf.get());
-                kdTree.getNode(nodeNum)._rightChild = 0;
+                kdTree.getNode(nodeNum).first = kdTree.replaceLeaf(nodeIndex, leftLeaf.get());
+                kdTree.getNode(nodeNum).second = 0;
             }
             else
             {
-                kdTree.getNode(nodeNum)._leftChild = kdTree.replaceLeaf(nodeIndex, leftLeaf.get());
-                kdTree.getNode(nodeNum)._rightChild = kdTree.addLeaf(rightLeaf.get());
-            }
-
-
-        }
-        
-        int originalLeftChildIndex = kdTree.getNode(nodeNum)._leftChild;
-        int originalRightChildIndex = kdTree.getNode(nodeNum)._rightChild;
+                kdTree.getNode(nodeNum).first = kdTree.replaceLeaf(nodeIndex, leftLeaf.get());
+                kdTree.getNode(nodeNum).second = kdTree.addLeaf(rightLeaf.get());
+            }
+        }
+#else
+        {
+            KDLeaf& leaf = kdTree.getLeaf(nodeIndex);
+
+            osg::Vec3Array* vertices = dynamic_cast<osg::Vec3Array*>(kdTree._geometry->getVertexArray());
+
+            //osg::notify(osg::NOTICE)<<"  divide leaf->_vertexIndices.size()="<<leaf->_vertexIndices.size()<<std::endl;
+
+            unsigned int estimatedSize = leaf.second;
+
+            int end = leaf.first+leaf.second-1;
+            int left = leaf.first;
+            int right = leaf.first+leaf.second-1;
+            
+            while(left<right)
+            {
+                while(left<right && ((*vertices)[kdTree._vertexIndices[left]])[axis]<=mid) { ++left; }
+                
+                while(left<right && ((*vertices)[kdTree._vertexIndices[right]])[axis]>mid) { --right; }
+
+                if (left<right)
+                {
+                    std::swap(kdTree._vertexIndices[left], kdTree._vertexIndices[right]);
+                    ++left;
+                    --right;
+                }
+            }
+            
+            if (left==right)
+            {
+                if (((*vertices)[kdTree._vertexIndices[left]])[axis]<=mid) ++left;
+                else --right;
+            }
+            
+            KDLeaf leftLeaf(leaf.first, (right-leaf.first)+1);
+            KDLeaf rightLeaf(left, (end-left)+1);
+
+#if 0            
+            osg::notify(osg::NOTICE)<<"In  leaf.first     ="<<leaf.first     <<" leaf.second     ="<<leaf.second<<std::endl;
+            osg::notify(osg::NOTICE)<<"    leftLeaf.first ="<<leftLeaf.first <<" leftLeaf.second ="<<leftLeaf.second<<std::endl;
+            osg::notify(osg::NOTICE)<<"    rightLeaf.first="<<rightLeaf.first<<" rightLeaf.second="<<rightLeaf.second<<std::endl;
+            osg::notify(osg::NOTICE)<<"    left="<<left<<" right="<<right<<std::endl;
+
+            if (leaf.second != (leftLeaf.second +rightLeaf.second))
+            {
+                osg::notify(osg::NOTICE)<<"*** Error in size, leaf.second="<<leaf.second
+                                        <<", leftLeaf.second="<<leftLeaf.second
+                                        <<", rightLeaf.second="<<rightLeaf.second<<std::endl;
+            }
+            else
+            {
+                osg::notify(osg::NOTICE)<<"Size OK, leaf.second="<<leaf.second
+                                        <<", leftLeaf.second="<<leftLeaf.second
+                                        <<", rightLeaf.second="<<rightLeaf.second<<std::endl;
+            }
+#endif
+            if (leftLeaf.second<=0)
+            {
+                //osg::notify(osg::NOTICE)<<"LeftLeaf empty"<<std::endl;
+                kdTree.getNode(nodeNum).first = 0;
+                kdTree.getNode(nodeNum).second = kdTree.replaceLeaf(nodeIndex, rightLeaf);
+            }
+            else if (rightLeaf.second<=0)
+            {
+                //osg::notify(osg::NOTICE)<<"RightLeaf empty"<<std::endl;
+                kdTree.getNode(nodeNum).first = kdTree.replaceLeaf(nodeIndex, leftLeaf);
+                kdTree.getNode(nodeNum).second = 0;
+            }
+            else
+            {
+                kdTree.getNode(nodeNum).first = kdTree.replaceLeaf(nodeIndex, leftLeaf);
+                kdTree.getNode(nodeNum).second = kdTree.addLeaf(rightLeaf);
+            }
+        }
+#endif
+        
+        int originalLeftChildIndex = kdTree.getNode(nodeNum).first;
+        int originalRightChildIndex = kdTree.getNode(nodeNum).second;
 
 
@@ -449 +600 @@
         bb._max[axis] = mid;
 
-        //osg::notify(osg::NOTICE)<<"  divide leftLeaf "<<kdTree.getNode(nodeNum)._leftChild<<std::endl;
+        //osg::notify(osg::NOTICE)<<"  divide leftLeaf "<<kdTree.getNode(nodeNum).first<<std::endl;
         int leftChildIndex = divide(kdTree, bb, originalLeftChildIndex, level+1);
 
@@ -457 +608 @@
         bb._min[axis] = mid;
 
-        //osg::notify(osg::NOTICE)<<"  divide rightLeaf "<<kdTree.getNode(nodeNum)._rightChild<<std::endl;
+        //osg::notify(osg::NOTICE)<<"  divide rightLeaf "<<kdTree.getNode(nodeNum).second<<std::endl;
         int rightChildIndex = divide(kdTree, bb, originalRightChildIndex, level+1);
         
         bb._min[axis] = restore;
         
-        kdTree.getNode(nodeNum)._leftChild = leftChildIndex;
-        kdTree.getNode(nodeNum)._rightChild = rightChildIndex; 
+        kdTree.getNode(nodeNum).first = leftChildIndex;
+        kdTree.getNode(nodeNum).second = rightChildIndex; 
         
         return nodeNum;        
@@ -488 +639 @@
 
     osgUtil::UpdateVisitor updateVisitor;
+    updateVisitor.setFrameStamp(new osg::FrameStamp);
     scene->accept(updateVisitor);
+    scene->getBound();