Changeset 13041 for OpenSceneGraph/trunk/src/osg/KdTree.cpp

Timestamp:

03/21/12 18:36:20 (14 months ago)

Author:

robert

Message:

Ran script to remove trailing spaces and tabs

Files:

• OpenSceneGraph/trunk/src/osg/KdTree.cpp (modified) (38 diffs)

OpenSceneGraph/trunk/src/osg/KdTree.cpp

@@ -1 @@
-/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield 
+/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
  *
- * This library is open source and may be redistributed and/or modified under  
- * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or 
+ * This library is open source and may be redistributed and/or modified under
+ * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
  * (at your option) any later version.  The full license is in LICENSE file
  * included with this distribution, and on the openscenegraph.org website.
- * 
+ *
  * This library is distributed in the hope that it will be useful,
  * but WITHOUT ANY WARRANTY; without even the implied warranty of
- * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the 
+ * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  * OpenSceneGraph Public License for more details.
 */
@@ -70 +70 @@
         const osg::Vec3& v1 = (*(_buildKdTree->_kdTree.getVertices()))[p1];
         const osg::Vec3& v2 = (*(_buildKdTree->_kdTree.getVertices()))[p2];
-    
+
         // discard degenerate points
         if (v0==v1 || v1==v2 || v1==v2)
@@ -79 +79 @@
 
         unsigned int i = _buildKdTree->_kdTree.addTriangle(KdTree::Triangle(p0,p1,p2));
-        
+
         osg::BoundingBox bb;
         bb.expandBy(v0);
@@ -87 +87 @@
         _buildKdTree->_centers.push_back(bb.center());
         _buildKdTree->_primitiveIndices.push_back(i);
-        
-    }
-    
+
+    }
+
     BuildKdTree* _buildKdTree;
 
@@ -101 +101 @@
 bool BuildKdTree::build(KdTree::BuildOptions& options, osg::Geometry* geometry)
 {
-    
-#ifdef VERBOSE_OUTPUT    
+
+#ifdef VERBOSE_OUTPUT
     OSG_NOTICE<<"osg::KDTreeBuilder::createKDTree()"<<std::endl;146
 #endif
@@ -108 +108 @@
     osg::Vec3Array* vertices = dynamic_cast<osg::Vec3Array*>(geometry->getVertexArray());
     if (!vertices) return false;
-    
+
     if (vertices->size() <= options._targetNumTrianglesPerLeaf) return false;
 
     _bb = geometry->getBound();
     _kdTree.setVertices(vertices);
-    
+
     unsigned int estimatedSize = (unsigned int)(2.0*float(vertices->size())/float(options._targetNumTrianglesPerLeaf));
 
-#ifdef VERBOSE_OUTPUT    
+#ifdef VERBOSE_OUTPUT
     OSG_NOTICE<<"kdTree->_kdNodes.reserve()="<<estimatedSize<<std::endl<<std::endl;
 #endif
 
     _kdTree.getNodes().reserve(estimatedSize*5);
-    
+
     computeDivisions(options);
 
@@ -145 +145 @@
     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());
@@ -152 +152 @@
         triangleList[i] = _kdTree.getTriangle(_primitiveIndices[i]);
     }
-    
+
     _kdTree.getTriangles().swap(triangleList);
-    
-    
-#ifdef VERBOSE_OUTPUT    
+
+
+#ifdef VERBOSE_OUTPUT
     OSG_NOTICE<<"Root nodeNum="<<nodeNum<<std::endl;
 #endif
-    
-    
+
+
 //    OSG_NOTICE<<"_kdNodes.size()="<<k_kdNodes.size()<<"  estimated size = "<<estimatedSize<<std::endl;
 //    OSG_NOTICE<<"_kdLeaves.size()="<<_kdLeaves.size()<<"  estimated size = "<<estimatedSize<<std::endl<<std::endl;
@@ -174 +174 @@
                          _bb.zMax()-_bb.zMin());
 
-#ifdef VERBOSE_OUTPUT    
+#ifdef VERBOSE_OUTPUT
     OSG_NOTICE<<"computeDivisions("<<options._maxNumLevels<<") "<<dimensions<< " { "<<std::endl;
 #endif
 
     _axisStack.reserve(options._maxNumLevels);
- 
+
     for(unsigned int level=0; level<options._maxNumLevels; ++level)
     {
@@ -194 +194 @@
         dimensions[axis] /= 2.0f;
 
-#ifdef VERBOSE_OUTPUT    
+#ifdef VERBOSE_OUTPUT
         OSG_NOTICE<<"  "<<level<<", "<<dimensions<<", "<<axis<<std::endl;
 #endif
     }
 
-#ifdef VERBOSE_OUTPUT    
+#ifdef VERBOSE_OUTPUT
     OSG_NOTICE<<"}"<<std::endl;
 #endif
@@ -210 +210 @@
     bool needToDivide = level < _axisStack.size() &&
                         (node.first<0 && static_cast<unsigned int>(node.second)>options._targetNumTrianglesPerLeaf);
-                        
+
     if (!needToDivide)
     {
@@ -217 +217 @@
             int istart = -node.first-1;
             int iend = istart+node.second-1;
-    
+
             // leaf is done, now compute bound on it.
             node.bb.init();
@@ -229 +229 @@
                 node.bb.expandBy(v1);
                 node.bb.expandBy(v2);
-                
+
             }
 
@@ -242 +242 @@
                 node.bb._max.z() += epsilon;
             }
-            
-#ifdef VERBOSE_OUTPUT    
+
+#ifdef VERBOSE_OUTPUT
             if (!node.bb.valid())
             {
@@ -263 +263 @@
     int axis = _axisStack[level];
 
-#ifdef VERBOSE_OUTPUT    
+#ifdef VERBOSE_OUTPUT
     OSG_NOTICE<<"divide("<<nodeIndex<<", "<<level<< "), axis="<<axis<<std::endl;
 #endif
 
     if (node.first<0)
-    {    
+    {
         // leaf node as first <= 0, so look at dividing it.
-        
+
         int istart = -node.first-1;
         int iend = istart+node.second-1;
 
         //OSG_NOTICE<<"  divide leaf"<<std::endl;
-        
+
         float original_min = bb._min[axis];
         float original_max = bb._max[axis];
@@ -289 +289 @@
             int left = istart;
             int right = iend;
-            
+
             while(left<right)
             {
@@ -295 +295 @@
 
                 while(left<right && (_centers[_primitiveIndices[right]][axis]>mid)) { --right; }
-                
+
                 while(left<right && (_centers[_primitiveIndices[right]][axis]>mid)) { --right; }
 
@@ -305 +305 @@
                 }
             }
-            
+
             if (left==right)
             {
@@ -311 +311 @@
                 else --right;
             }
-            
+
             KdTree::KdNode leftLeaf(-istart-1, (right-istart)+1);
             KdTree::KdNode rightLeaf(-left-1, (iend-left)+1);
@@ -358 +358 @@
         }
 
-        
+
         float restore = bb._max[axis];
         bb._max[axis] = mid;
@@ -366 +366 @@
 
         bb._max[axis] = restore;
-        
+
         restore = bb._min[axis];
         bb._min[axis] = mid;
@@ -372 +372 @@
         //OSG_NOTICE<<"  divide rightLeaf "<<kdTree.getNode(nodeNum).second<<std::endl;
         int rightChildIndex = originalRightChildIndex!=0 ? divide(options, bb, originalRightChildIndex, level+1) : 0;
-        
+
         bb._min[axis] = restore;
-        
+
 
         if (!insitueDivision)
@@ -381 +381 @@
             // have invalidate the previous node ref.
             KdTree::KdNode& newNodeRef = _kdTree.getNode(nodeIndex);
-        
+
             newNodeRef.first = leftChildIndex;
-            newNodeRef.second = rightChildIndex; 
+            newNodeRef.second = rightChildIndex;
 
             insitueDivision = true;
@@ -417 +417 @@
         OSG_NOTICE<<"NOT expecting to get here"<<std::endl;
     }
-    
+
     return nodeIndex;
-    
+
 }
 
@@ -444 +444 @@
         _inverse_length = _length!=0.0f ? 1.0f/_length : 0.0;
         _d *= _inverse_length;
-        
+
         _d_invX = _d.x()!=0.0f ? _d/_d.x() : osg::Vec3(0.0f,0.0f,0.0f);
         _d_invY = _d.y()!=0.0f ? _d/_d.y() : osg::Vec3(0.0f,0.0f,0.0f);
@@ -464 +464 @@
     float     _length;
     float     _inverse_length;
-    
+
     osg::Vec3 _d_invX;
     osg::Vec3 _d_invY;
@@ -481 +481 @@
     {
         // treat as a leaf
-        
+
         //OSG_NOTICE<<"KdTree::intersect("<<&leaf<<")"<<std::endl;
         int istart = -node.first-1;
         int iend = istart + node.second;
-        
+
         for(int i=istart; i<iend; ++i)
         {
@@ -499 +499 @@
             osg::Vec3 E2 = v2 - v0;
             osg::Vec3 E1 = v1 - v0;
-            
+
             osg::Vec3 P =  _d ^ E2;
-            
+
             float det = P * E1;
-            
+
             float r,r0,r1,r2;
-            
+
             const float esplison = 1e-10f;
             if (det>esplison)
@@ -511 +511 @@
                 float u = (P*T);
                 if (u<0.0 || u>det) continue;
-                
+
                 osg::Vec3 Q = T ^ E1;
                 float v = (Q*_d);
                 if (v<0.0 || v>det) continue;
-                
+
                 if ((u+v)> det) continue;
 
-                float inv_det = 1.0f/det;                
-                float t = (Q*E2)*inv_det;            
-                if (t<0.0 || t>_length) continue;
-
-                u *= inv_det;
-                v *= inv_det;
-
-                r0 = 1.0f-u-v;
-                r1 = u;
-                r2 = v; 
-                r = t * _inverse_length;
-            }
-            else if (det<-esplison)
-            {
-
-                float u = (P*T);
-                if (u>0.0 || u<det) continue;
-                
-                osg::Vec3 Q = T ^ E1;
-                float v = (Q*_d);
-                if (v>0.0 || v<det) continue;
-                
-                if ((u+v) < det) continue;
-
-                float inv_det = 1.0f/det;                
-                float t = (Q*E2)*inv_det;            
+                float inv_det = 1.0f/det;
+                float t = (Q*E2)*inv_det;
                 if (t<0.0 || t>_length) continue;
 
@@ -554 +530 @@
                 r = t * _inverse_length;
             }
+            else if (det<-esplison)
+            {
+
+                float u = (P*T);
+                if (u>0.0 || u<det) continue;
+
+                osg::Vec3 Q = T ^ E1;
+                float v = (Q*_d);
+                if (v>0.0 || v<det) continue;
+
+                if ((u+v) < det) continue;
+
+                float inv_det = 1.0f/det;
+                float t = (Q*E2)*inv_det;
+                if (t<0.0 || t>_length) continue;
+
+                u *= inv_det;
+                v *= inv_det;
+
+                r0 = 1.0f-u-v;
+                r1 = u;
+                r2 = v;
+                r = t * _inverse_length;
+            }
             else
             {
@@ -562 +562 @@
             osg::Vec3 normal = E1^E2;
             normal.normalize();
-            
+
 #if 1
             _intersections.push_back(KdTree::LineSegmentIntersection());
@@ -705 +705 @@
             e = s+_d_invZ*(bb.zMax()-s.z());
         }
-    } 
+    }
     else
     {
@@ -723 +723 @@
         }
     }
-    
+
     // OSG_NOTICE<<"clampped segment "<<s<<" "<<e<<std::endl;
-    
+
     // if (s==e) return false;
 
-    return true;    
+    return true;
 }
 
@@ -767 +767 @@
 bool KdTree::intersect(const osg::Vec3d& start, const osg::Vec3d& end, LineSegmentIntersections& intersections) const
 {
-    if (_kdNodes.empty()) 
+    if (_kdNodes.empty())
     {
         OSG_NOTICE<<"Warning: _kdTree is empty"<<std::endl;
@@ -780 +780 @@
                                 intersections,
                                 start, end);
-                    
+
     intersector.intersect(getNode(0), start, end);
-    
+
     return numIntersectionsBefore != intersections.size();
 }
@@ -791 +791 @@
 KdTreeBuilder::KdTreeBuilder():
     osg::NodeVisitor(osg::NodeVisitor::TRAVERSE_ALL_CHILDREN)
-{            
+{
     _kdTreePrototype = new osg::KdTree;
 }
@@ -805 +805 @@
 {
     for(unsigned int i=0; i<geode.getNumDrawables(); ++i)
-    {            
+    {
 
         osg::Geometry* geom = geode.getDrawable(i)->asGeometry();
@@ -820 +820 @@
                 geom->setShape(kdTree.get());
             }
-        }   
-    }
-}
+        }
+    }
+}