Changeset 8556

Timestamp:

07/10/08 17:50:10

Author:

robert

Message:

Streamlined KdTree? implementation

Files:

• OpenSceneGraph/trunk/include/osg/KdTree (modified) (6 diffs)
• OpenSceneGraph/trunk/src/osg/KdTree.cpp (modified) (14 diffs)

OpenSceneGraph/trunk/include/osg/KdTree

@@ -92 +92 @@
-            value_type second;
-        };
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
-        struct Triangle
-        {
@@ -131 +114 @@
-        typedef std::vector< unsigned int > AxisStack;
-        typedef std::vector< KdNode >       KdNodeList;
-        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>static_cast<int>(_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>static_cast<int>(_kdLeaves.size())-1)
-            {
-                osg::notify(osg::NOTICE)<<"Warning: getLeaf("<<leafNum<<", num = "<<num<<") _kdLeaves.size()="<<_kdLeaves.size()<<std::endl;
-            }
-
-            return _kdLeaves[num];
-        }
-
-        const KdLeaf& getLeaf(int leafNum) const
-        {
-            int num = -leafNum-1;
-            if (num<0 || num>static_cast<int>(_kdLeaves.size())-1)
-            {
-                osg::notify(osg::NOTICE)<<"Warning: getLeaf("<<leafNum<<", num = "<<num<<") _kdLeaves.size()="<<_kdLeaves.size()<<std::endl;
-            }
-
-            return _kdLeaves[num];
-        }
-
-        int addNode(const KdNode& node)
@@ -201 +144 @@
-        osg::BoundingBox& getBoundingBox(int nodeNum)
-        {
-
-
-
-
-
-
-
-
-
+
-        }
-
@@ -217 +152 @@
-        int divide(BuildOptions& options, osg::BoundingBox& bb, int nodeIndex, unsigned int level);
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-        bool intersectAndClip(osg::Vec3& s, osg::Vec3& e, const osg::BoundingBox& bb) const;
-
@@ -231 +186 @@
-        AxisStack                           _axisStack;
-        KdNodeList                          _kdNodes;
-        KdLeafList                          _kdLeaves;
-
-        osg::ref_ptr<osg::Vec3Array>        _vertices;
@@ -237 +191 @@
-        Indices                             _primitiveIndices;
-        
-        BoundingBoxList                     _boundingBoxes;
-        TriangleList                        _triangles;
-        CenterList                          _centers;

OpenSceneGraph/trunk/src/osg/KdTree.cpp

@@ -21 +21 @@
-using namespace osg;
-
- 
+
-
-////////////////////////////////////////////////////////////////////////////////
@@ -43 +43 @@
-        bb.expandBy((*(_kdTree->_vertices))[p2]);
-        bb.expandBy((*(_kdTree->_vertices))[p3]);
-
-
+
-        _kdTree->_centers.push_back(bb.center());
-
-        _kdTree->_primitiveIndices.push_back(i);
-        
@@ -61 +59 @@
-KdTree::BuildOptions::BuildOptions():
-        _numVerticesProcessed(0),
-4
+2
-        _maxNumLevels(32)
-{
@@ -100 +98 @@
-#endif
-
-
-
+
-    
-    computeDivisions(options);
@@ -109 +106 @@
-    unsigned int estimatedNumTriangles = vertices->size()*2;
-    _primitiveIndices.reserve(estimatedNumTriangles);
-    _boundingBoxes.reserve(estimatedNumTriangles);
-    _triangles.reserve(estimatedNumTriangles);
-    _centers.reserve(estimatedNumTriangles);
@@ -121 +117 @@
-    _primitiveIndices.reserve(vertices->size());
-
-
-
-
-
-
+
+
+
+
-
-    osg::BoundingBox bb = _bb;
-int nodeNum = divide(options, bb, leaf
+nodeNum = divide(options, bb, node
-    
-#ifdef VERBOSE_OUTPUT    
@@ -180 +175 @@
-int KdTree::divide(BuildOptions& options, osg::BoundingBox& bb, int nodeIndex, unsigned int level)
-{
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
-            // leaf is done, now compute bound on it.
-
-
-
-
+
+
-            {
-                const Triangle& tri = _triangles[_primitiveIndices[i]];
@@ -211 +195 @@
-                const osg::Vec3& v2 = (*_vertices)[tri._p2];
-                const osg::Vec3& v3 = (*_vertices)[tri._p3];
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-        //osg::notify(osg::NOTICE)<<"  divide leaf"<<std::endl;
-        
-        int nodeNum = addNode(KdNode());
-
-        float original_min = bb._min[axis];
-        float original_max = bb._max[axis];
@@ -228 +246 @@
-        float mid = (original_min+original_max)*0.5f;
-
-
-
-
+
+
+
+
-            //osg::Vec3Array* vertices = kdTree._vertices.get();
-
-
-
+
+
-            
-            while(left<right)
@@ -258 +276 @@
-            }
-            
-Leaf leftLeaf(leaf.first, (right-leaf.firs
-Leaf rightLeaf(left, (
-
-            
-leaf.first     ="<<leaf.first     <<" leaf.second     ="<<leaf
+Node leftLeaf(-istart-1, (right-istar
+Node rightLeaf(-left-1, (i
+
+
+node.first     ="<<node.first     <<" node.second     ="<<node
-            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;
-
-leaf
-
-leaf
+node
+
+node
-                                        <<", leftLeaf.second="<<leftLeaf.second
-                                        <<", rightLeaf.second="<<rightLeaf.second<<std::endl;
@@ -275 +293 @@
-            else
-            {
-leaf
+node
-                                        <<", leftLeaf.second="<<leftLeaf.second
-                                        <<", rightLeaf.second="<<rightLeaf.second<<std::endl;
-            }
-#endif
+
-            if (leftLeaf.second<=0)
-            {
-                //osg::notify(osg::NOTICE)<<"LeftLeaf empty"<<std::endl;
-getNode(nodeNum).first
-getNode(nodeNum).second = replaceLeaf(nodeIndex, 
+originalLeftChildIndex
+originalRightChildIndex = addNode(
-            }
-            else if (rightLeaf.second<=0)
-            {
-                //osg::notify(osg::NOTICE)<<"RightLeaf empty"<<std::endl;
-getNode(nodeNum).first = replaceLeaf(nodeIndex, 
-getNode(nodeNum).second
+originalLeftChildIndex = addNode(
+originalRightChildIndex
-            }
-            else
-            {
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
-        float restore = bb._max[axis];
-        bb._max[axis] = mid;
-
-        //osg::notify(osg::NOTICE)<<"  divide leftLeaf "<<kdTree.getNode(nodeNum).first<<std::endl;
-divide(options, bb, originalLeftChildIndex, level+1)
+originalLeftChildIndex!=0 ? divide(options, bb, originalLeftChildIndex, level+1) : 0
-
-        bb._max[axis] = restore;
@@ -316 +331 @@
-
-        //osg::notify(osg::NOTICE)<<"  divide rightLeaf "<<kdTree.getNode(nodeNum).second<<std::endl;
-divide(options, bb, originalRightChildIndex, level+1)
+originalRightChildIndex!=0 ? divide(options, bb, originalRightChildIndex, level+1) : 0
-        
-        bb._min[axis] = restore;
-        
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-{
-    //osg::notify(osg::NOTICE)<<"  Intersect "<<&node<<std::endl;
-
-
+
+
+
+
+
+
+
+
+
+
+
-    int numIntersectionsBefore = intersections.size();
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-    return numIntersectionsBefore != intersections.size();
-}
@@ -485 +527 @@
-bool KdTree::intersectAndClip(osg::Vec3& s, osg::Vec3& e, const osg::BoundingBox& bb) const
-{
+    //return true;
+
+    //if (!bb.valid()) return true;
+
-    // compate s and e against the xMin to xMax range of bb.
-    if (s.x()<=e.x())
@@ -608 +654 @@
-bool KdTree::intersect(const osg::Vec3& start, const osg::Vec3& end, LineSegmentIntersections& intersections) const
-{
-osg::Vec3 s(start), e(
-start, end, s,e
+RayData rayData(start,
+rayData, start, end
-}
-