Changeset 8557

Timestamp:

07/11/08 18:48:39

Author:

robert

Message:

Moved the building and intersecting of the KdTree? into the .cpp, and cleaned up
the header to ready it for wider usage

Files:

• OpenSceneGraph/trunk/include/osg/KdTree (modified) (7 diffs)
• OpenSceneGraph/trunk/src/osg/KdTree.cpp (modified) (16 diffs)

OpenSceneGraph/trunk/include/osg/KdTree

@@ -17 +17 @@
-#include <osg/Shape>
-#include <osg/Geometry>
+
+#include <map>
-
-namespace osg
@@ -51 +53 @@
-            LineSegmentIntersection():
-                ratio(-1.0),
+                p0(0),
+                p1(0),
+                p2(0),
+                r0(0.0f),
+                r1(0.0f),
+                r2(0.0f),
-                primitiveIndex(0) {}
-
@@ -61 +69 @@
-            osg::Vec3d                      intersectionPoint;
-            osg::Vec3                       intersectionNormal;
-
-
+
+
+
+
+
+
+
+
-            unsigned int                    primitiveIndex;
-        };        
-        
-
-multiset
+vector
-        
-        /** compute the intersection of a line segment and the kdtree, return true if an intersection has been found.*/
@@ -73 +87 @@
-
-
-
-        typedef int value_type;
-        typedef std::vector< value_type >   Indices;
-
-        struct KdNode
@@ -95 +107 @@
-        struct Triangle
-        {
-
-
+
+
+
+
+
-
-            bool operator < (const Triangle& rhs) const
-            {
-_p1<rhs._p1
-_p1>rhs._p1
-_p2<rhs._p2
-_p2>rhs._p2
-_p3<rhs._p3
+p0<rhs.p0
+p0>rhs.p0
+p1<rhs.p1
+p1>rhs.p1
+p2<rhs.p2
-            }
-
-_p1
-_p2
-_p3;    
+p0
+p1
+p2;
-        };
-
-        typedef std::vector< unsigned int > AxisStack;
-        typedef std::vector< KdNode >       KdNodeList;
+        typedef std::vector< Triangle >     TriangleList;
-
-        int addNode(const KdNode& node)
@@ -122 +137 @@
-        }
-
-
-
+
+
+
+
+
+
+
+
+
+
-        {
-
-
-
-
-
+
+
+
-        }
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
-
-        osg::ref_ptr<osg::Vec3Array>        _vertices;
-
-
-
+
-        TriangleList                        _triangles;
-        CenterList                          _centers;
-
-};
@@ -211 +183 @@
-
-        osg::ref_ptr<osg::KdTree> _kdTreePrototype;
+
+
-                
-    protected:

OpenSceneGraph/trunk/src/osg/KdTree.cpp

@@ -25 +25 @@
-////////////////////////////////////////////////////////////////////////////////
-//
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-};
@@ -55 +53 @@
-////////////////////////////////////////////////////////////////////////////////
-//
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-////////////////////////////////////////////////////////////////////////////////
-//
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
-#ifdef VERBOSE_OUTPUT    
-
+146
-#endif
-
@@ -88 +108 @@
-    if (vertices->size() <= options._targetNumTrianglesPerLeaf) return false;
-
-
-
-
+
+
-    
-    unsigned int estimatedSize = (unsigned int)(2.0*float(vertices->size())/float(options._targetNumTrianglesPerLeaf));
@@ -98 +117 @@
-#endif
-
-Nodes
+Tree.getNodes()
-    
-    computeDivisions(options);
@@ -106 +125 @@
-    unsigned int estimatedNumTriangles = vertices->size()*2;
-    _primitiveIndices.reserve(estimatedNumTriangles);
-    _triangles.reserve(estimatedNumTriangles);
-    _centers.reserve(estimatedNumTriangles);
-
-
+
-
-    osg::TriangleIndexFunctor<TriangleIndicesCollector> collectTriangleIndices;
-k
+buildK
-    geometry->accept(collectTriangleIndices);
-
-    _primitiveIndices.reserve(vertices->size());
-
-
+Tree::Kd
-    node.bb = _bb;
-
-
+_kdTree.
-
-    osg::BoundingBox bb = _bb;
-    nodeNum = divide(options, bb, nodeNum, 0);
-    
+    // now reorder the triangle list so that it's in order as per the primitiveIndex list.
+    KdTree::TriangleList triangleList(_kdTree.getTriangles().size());
+    for(unsigned int i=0; i<_primitiveIndices.size(); ++i)
+    {
+        triangleList[i] = _kdTree.getTriangle(_primitiveIndices[i]);
+    }
+    
+    _kdTree.getTriangles().swap(triangleList);
+    
+    
-#ifdef VERBOSE_OUTPUT    
-    osg::notify(osg::NOTICE)<<"Root nodeNum="<<nodeNum<<std::endl;
@@ -134 +162 @@
-
-
-Nodes
-
-
-KdTree::computeDivisions(
+Tree.getNodes()
+
+
+BuildKdTree::computeDivisions(KdTree::
-{
-    osg::Vec3 dimensions(_bb.xMax()-_bb.xMin(),
@@ -173 +201 @@
-}
-
-KdTree::divide(
-
-Node& node = 
+BuildKdTree::divide(KdTree::
+
+Tree::KdNode& node = _kdTree.
-
-    bool needToDivide = level < _axisStack.size() &&
@@ -191 +219 @@
-            for(int i=istart; i<=iend; ++i)
-            {
-
-
-
-
+
+
+
+
+
-                node.bb.expandBy(v1);
-                node.bb.expandBy(v2);
-                node.bb.expandBy(v3);
-                
-                float epsilon = 1e-6;
@@ -248 +276 @@
-        int originalLeftChildIndex = 0;
-        int originalRightChildIndex = 0;
+        bool insitueDivision = false;
-
-        {
@@ -276 +305 @@
-            }
-            
-
-
+Tree::Kd
+Tree::Kd
-
-#if 0
@@ -303 +332 @@
-                //osg::notify(osg::NOTICE)<<"LeftLeaf empty"<<std::endl;
-                originalLeftChildIndex = 0;
-
+
+
+
-            }
-            else if (rightLeaf.second<=0)
-            {
-                //osg::notify(osg::NOTICE)<<"RightLeaf empty"<<std::endl;
-
+
+
-                originalRightChildIndex = 0;
+                insitueDivision = true;
-            }
-            else
-            {
-
-
+_kdTree.
+_kdTree.
-            }
-        }
@@ -335 +368 @@
-        bb._min[axis] = restore;
-        
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-    }
-    else
@@ -373 +415 @@
-}
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-    if (node.first<0)
-    {
-        // treat as a leaf
-
+
-        //osg::notify(osg::NOTICE)<<"KdTree::intersect("<<&leaf<<")"<<std::endl;
-        int istart = -node.first-1;
@@ -399 +468 @@
-        for(int i=istart; i<iend; ++i)
-        {
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-                continue;
-            }
-
-
-
-
-
-
-
+
+
-            normal.normalize();
-
-
-
-
+
+
+
+
+
-            intersection.ratio = r;
-_primitiveIndices[i]
+i
-            intersection.intersectionPoint = in;
-            intersection.intersectionNormal = normal;
-
-
-
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
-            // osg::notify(osg::NOTICE)<<"  got intersection ("<<in<<") ratio="<<r<<std::endl;
-        }
@@ -518 +565 @@
-    else
-    {
-
-
-
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-{
-    //return true;
@@ -652 +711 @@
-}
-
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// KdTree::BuildOptions
+
+KdTree::BuildOptions::BuildOptions():
+        _numVerticesProcessed(0),
+        _targetNumTrianglesPerLeaf(4),
+        _maxNumLevels(32)
+{
+}
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// KdTree
+
+KdTree::KdTree()
+{
+}
+
+KdTree::KdTree(const KdTree& rhs, const osg::CopyOp& copyop):
+    Shape(rhs)
+{
+}
+
+bool KdTree::build(BuildOptions& options, osg::Geometry* geometry)
+{
+    BuildKdTree build(*this);
+    return build.build(options, geometry);
+}
+
-bool KdTree::intersect(const osg::Vec3& start, const osg::Vec3& end, LineSegmentIntersections& intersections) const
-{
-
-
+
+
+
+
+
+
+
+
+
+
+
-}
-