Changeset 8546

Timestamp:

07/07/08 22:27:56

Author:

robert

Message:

Implement hierachy culling in KdTree?::intersect(..)

Files:

• OpenSceneGraph/trunk/include/osg/KdTree (modified) (4 diffs)
• OpenSceneGraph/trunk/src/osg/KdTree.cpp (modified) (7 diffs)
• OpenSceneGraph/trunk/src/osgUtil/LineSegmentIntersector.cpp (modified) (10 diffs)

OpenSceneGraph/trunk/include/osg/KdTree

@@ -35 +35 @@
-        struct BuildOptions
-        {
-
-
-
-
+
-                        
-            int _numVerticesProcessed;
@@ -164 +161 @@
-        }
-
+        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)
-        {
@@ -180 +188 @@
-            return _kdNodes[nodeNum];
-        }
-
-
+
+
+
+
+
+
+
+
+
+
+
+
-        {
-            if (nodeNum<0)
@@ -200 +218 @@
-
-        bool intersect(const KdLeaf& leaf, const osg::Vec3& start, const osg::Vec3& end, LineSegmentIntersections& intersections) const;
+        bool intersect(const KdNode& node, const osg::Vec3& start, const osg::Vec3& end, const osg::Vec3& s, const osg::Vec3& e, LineSegmentIntersections& intersections) const;
+        bool intersectAndClip(osg::Vec3& s, osg::Vec3& e, const osg::BoundingBox& bb) const;
-
-        typedef std::vector< osg::BoundingBox >                 BoundingBoxList;

OpenSceneGraph/trunk/src/osg/KdTree.cpp

@@ -20 +20 @@
-using namespace osg;
-
-
+ 
-
-////////////////////////////////////////////////////////////////////////////////
@@ -58 +58 @@
-// KdTree
-
+KdTree::BuildOptions::BuildOptions():
+        _numVerticesProcessed(0),
+        _targetNumTrianglesPerLeaf(8),
+        _maxNumLevels(24)
+{
+}
+
+////////////////////////////////////////////////////////////////////////////////
+//
+// KdTree
+
-KdTree::KdTree()
-{
@@ -118 +129 @@
-    int nodeNum = divide(options, bb, leafNum, 0);
-
+#if 0    
+    for(KdLeafList::iterator itr = _kdLeaves.begin();
+        itr != _kdLeaves.end();
+        ++itr)
+    {
+        KdLeaf& leaf = *itr;
+        leaf.bb.init();
+        int iend = leaf.first+leaf.second;
+        for(int i=leaf.first; i<iend; ++i)
+        {
+            const Triangle& tri = _triangles[_primitiveIndices[i]];
+            const osg::Vec3& v1 = (*_vertices)[tri._p1];
+            const osg::Vec3& v2 = (*_vertices)[tri._p2];
+            const osg::Vec3& v3 = (*_vertices)[tri._p3];
+            leaf.bb.expandBy(v1);
+            leaf.bb.expandBy(v2);
+            leaf.bb.expandBy(v3);
+        }
+        // osg::notify(osg::NOTICE)<<"leaf.bb.min("<<leaf.bb._min<<") max("<<leaf.bb._max<<")"<<std::endl;
+
+    }
+#endif
+    
-#ifdef VERBOSE_OUTPUT    
-    osg::notify(osg::NOTICE)<<"Root nodeNum="<<nodeNum<<std::endl;
@@ -187 +221 @@
-    {    
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-
-        //osg::notify(osg::NOTICE)<<"  divide leaf"<<std::endl;
@@ -293 +345 @@
-        getNode(nodeNum).second = rightChildIndex; 
-        
+        getNode(nodeNum).bb.init();
+        if (leftChildIndex!=0) getNode(nodeNum).bb.expandBy(getBoundingBox(leftChildIndex));
+        if (rightChildIndex!=0) getNode(nodeNum).bb.expandBy(getBoundingBox(rightChildIndex));
+        
-        return nodeNum;
-    }
@@ -424 +480 @@
-        intersections.insert(intersection);
-
-
+// 
-
-        intersects = true;
@@ -432 +488 @@
-}
-
+bool KdTree::intersect(const KdNode& node, const osg::Vec3& start, const osg::Vec3& end, const osg::Vec3& s, const osg::Vec3& e, LineSegmentIntersections& intersections) const
+{
+    //osg::notify(osg::NOTICE)<<"  Intersect "<<&node<<std::endl;
+    //osg::Vec3 ls(start), le(end);
+    osg::Vec3 ls(s), le(e);
+    int numIntersectionsBefore = intersections.size();
+    if (intersectAndClip(ls, le, node.bb))
+    {
+        if (node.first>0) intersect(getNode(node.first), start, end, ls, le, intersections);
+        else if (node.first<0) intersect(getLeaf(node.first), start, end, intersections);
+
+        if (node.second>0) intersect(getNode(node.second), start, end, ls, le, intersections);
+        else if (node.second<0) intersect(getLeaf(node.second), start, end, intersections);
+    }
+    return numIntersectionsBefore != intersections.size();
+}
+
+bool KdTree::intersectAndClip(osg::Vec3& s, osg::Vec3& e, const osg::BoundingBox& bb) const
+{
+    // compate s and e against the xMin to xMax range of bb.
+    if (s.x()<=e.x())
+    {
+
+        // trivial reject of segment wholely outside.
+        if (e.x()<bb.xMin()) return false;
+        if (s.x()>bb.xMax()) return false;
+
+        if (s.x()<bb.xMin())
+        {
+            // clip s to xMin.
+            s = s+(e-s)*(bb.xMin()-s.x())/(e.x()-s.x());
+        }
+
+        if (e.x()>bb.xMax())
+        {
+            // clip e to xMax.
+            e = s+(e-s)*(bb.xMax()-s.x())/(e.x()-s.x());
+        }
+    }
+    else
+    {
+        if (s.x()<bb.xMin()) return false;
+        if (e.x()>bb.xMax()) return false;
+
+        if (e.x()<bb.xMin())
+        {
+            // clip s to xMin.
+            e = s+(e-s)*(bb.xMin()-s.x())/(e.x()-s.x());
+        }
+
+        if (s.x()>bb.xMax())
+        {
+            // clip e to xMax.
+            s = s+(e-s)*(bb.xMax()-s.x())/(e.x()-s.x());
+        }
+    }
+
+    // compate s and e against the yMin to yMax range of bb.
+    if (s.y()<=e.y())
+    {
+
+        // trivial reject of segment wholely outside.
+        if (e.y()<bb.yMin()) return false;
+        if (s.y()>bb.yMax()) return false;
+
+        if (s.y()<bb.yMin())
+        {
+            // clip s to yMin.
+            s = s+(e-s)*(bb.yMin()-s.y())/(e.y()-s.y());
+        }
+
+        if (e.y()>bb.yMax())
+        {
+            // clip e to yMax.
+            e = s+(e-s)*(bb.yMax()-s.y())/(e.y()-s.y());
+        }
+    }
+    else
+    {
+        if (s.y()<bb.yMin()) return false;
+        if (e.y()>bb.yMax()) return false;
+
+        if (e.y()<bb.yMin())
+        {
+            // clip s to yMin.
+            e = s+(e-s)*(bb.yMin()-s.y())/(e.y()-s.y());
+        }
+
+        if (s.y()>bb.yMax())
+        {
+            // clip e to yMax.
+            s = s+(e-s)*(bb.yMax()-s.y())/(e.y()-s.y());
+        }
+    }
+
+    // compate s and e against the zMin to zMax range of bb.
+    if (s.z()<=e.z())
+    {
+
+        // trivial reject of segment wholely outside.
+        if (e.z()<bb.zMin()) return false;
+        if (s.z()>bb.zMax()) return false;
+
+        if (s.z()<bb.zMin())
+        {
+            // clip s to zMin.
+            s = s+(e-s)*(bb.zMin()-s.z())/(e.z()-s.z());
+        }
+
+        if (e.z()>bb.zMax())
+        {
+            // clip e to zMax.
+            e = s+(e-s)*(bb.zMax()-s.z())/(e.z()-s.z());
+        }
+    }
+    else
+    {
+        if (s.z()<bb.zMin()) return false;
+        if (e.z()>bb.zMax()) return false;
+
+        if (e.z()<bb.zMin())
+        {
+            // clip s to zMin.
+            e = s+(e-s)*(bb.zMin()-s.z())/(e.z()-s.z());
+        }
+
+        if (s.z()>bb.zMax())
+        {
+            // clip e to zMax.
+            s = s+(e-s)*(bb.zMax()-s.z())/(e.z()-s.z());
+        }
+    }
+    
+    // osg::notify(osg::NOTICE)<<"clampped segment "<<s<<" "<<e<<std::endl;
+    
+    // if (s==e) return false;
+
+    return true;    
+}
+
-bool KdTree::intersect(const osg::Vec3& start, const osg::Vec3& end, LineSegmentIntersections& intersections) const
-{
-
-
+
-    bool intersects = false;
-
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-    }
-

OpenSceneGraph/trunk/src/osgUtil/LineSegmentIntersector.cpp

@@ -20 +20 @@
-#include <osg/TriangleFunctor>
-#include <osg/KdTree>
+#include <osg/Timer>
-
-using namespace osgUtil;
@@ -295 +296 @@
-    }
-    
+    osg::Timer_t before_kdTree = osg::Timer::instance()->tick();
+    unsigned int numKdTreeHits = 0;
+    unsigned int numConventionalHits = 0;
+    
-    osg::KdTree* kdTree = dynamic_cast<osg::KdTree*>(drawable->getShape());
+    osg::Vec3d kdTreeHit;
-    if (kdTree)
-    {
@@ -301 +307 @@
-        if (kdTree->intersect(s,e,intersections))
-        {
-
+// 
-            for(osg::KdTree::LineSegmentIntersections::iterator itr = intersections.begin();
-                itr != intersections.end();
@@ -323 +329 @@
-
-                hit.localIntersectionPoint = _start*(1.0-remap_ratio) + _end*remap_ratio;
+                kdTreeHit = hit.localIntersectionPoint;
-                
-
+// 
-                
-                hit.localIntersectionNormal = lsi.intersectionNormal;
@@ -331 +338 @@
-                hit.ratioList.swap(lsi.ratioList);
-
+                ++numKdTreeHits;
-                insertIntersection(hit);
-
@@ -336 +344 @@
-        }
-        
-
+// 
-    }
-    else
@@ -342 +350 @@
-        // osg::notify(osg::NOTICE)<<"Not KdTree available"<<std::endl;
-    }
+
+    osg::Timer_t after_kdTree = osg::Timer::instance()->tick();
-
-    osg::TriangleFunctor<LineSegmentIntersectorUtils::TriangleIntersector> ti;
@@ -347 +357 @@
-    drawable->accept(ti);
-
+    osg::Vec3d conventionalHit;
-    if (ti._hit)
-    {
@@ -372 +383 @@
-
-            hit.localIntersectionPoint = _start*(1.0-remap_ratio) + _end*remap_ratio;
+            conventionalHit = hit.localIntersectionPoint;
-
-            // osg::notify(osg::NOTICE)<<"Conventional: ratio="<<hit.ratio<<" ("<<hit.localIntersectionPoint<<")"<<std::endl;
@@ -402 +414 @@
-            
-            insertIntersection(hit);
-
-
-
-
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
+
-}
-