Changeset 13041 for OpenSceneGraph/trunk/src/osg/KdTree.cpp
 Timestamp:
 03/21/12 18:36:20 (5 years ago)
 Files:

 1 modified
Legend:
 Unmodified
 Added
 Removed

OpenSceneGraph/trunk/src/osg/KdTree.cpp
r12437 r13041 1 /* *c++* OpenSceneGraph  Copyright (C) 19982006 Robert Osfield 1 /* *c++* OpenSceneGraph  Copyright (C) 19982006 Robert Osfield 2 2 * 3 * This library is open source and may be redistributed and/or modified under 4 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or 3 * This library is open source and may be redistributed and/or modified under 4 * the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or 5 5 * (at your option) any later version. The full license is in LICENSE file 6 6 * included with this distribution, and on the openscenegraph.org website. 7 * 7 * 8 8 * This library is distributed in the hope that it will be useful, 9 9 * but WITHOUT ANY WARRANTY; without even the implied warranty of 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 11 11 * OpenSceneGraph Public License for more details. 12 12 */ … … 70 70 const osg::Vec3& v1 = (*(_buildKdTree>_kdTree.getVertices()))[p1]; 71 71 const osg::Vec3& v2 = (*(_buildKdTree>_kdTree.getVertices()))[p2]; 72 72 73 73 // discard degenerate points 74 74 if (v0==v1  v1==v2  v1==v2) … … 79 79 80 80 unsigned int i = _buildKdTree>_kdTree.addTriangle(KdTree::Triangle(p0,p1,p2)); 81 81 82 82 osg::BoundingBox bb; 83 83 bb.expandBy(v0); … … 87 87 _buildKdTree>_centers.push_back(bb.center()); 88 88 _buildKdTree>_primitiveIndices.push_back(i); 89 90 } 91 89 90 } 91 92 92 BuildKdTree* _buildKdTree; 93 93 … … 101 101 bool BuildKdTree::build(KdTree::BuildOptions& options, osg::Geometry* geometry) 102 102 { 103 104 #ifdef VERBOSE_OUTPUT 103 104 #ifdef VERBOSE_OUTPUT 105 105 OSG_NOTICE<<"osg::KDTreeBuilder::createKDTree()"<<std::endl;146 106 106 #endif … … 108 108 osg::Vec3Array* vertices = dynamic_cast<osg::Vec3Array*>(geometry>getVertexArray()); 109 109 if (!vertices) return false; 110 110 111 111 if (vertices>size() <= options._targetNumTrianglesPerLeaf) return false; 112 112 113 113 _bb = geometry>getBound(); 114 114 _kdTree.setVertices(vertices); 115 115 116 116 unsigned int estimatedSize = (unsigned int)(2.0*float(vertices>size())/float(options._targetNumTrianglesPerLeaf)); 117 117 118 #ifdef VERBOSE_OUTPUT 118 #ifdef VERBOSE_OUTPUT 119 119 OSG_NOTICE<<"kdTree>_kdNodes.reserve()="<<estimatedSize<<std::endl<<std::endl; 120 120 #endif 121 121 122 122 _kdTree.getNodes().reserve(estimatedSize*5); 123 123 124 124 computeDivisions(options); 125 125 … … 145 145 osg::BoundingBox bb = _bb; 146 146 nodeNum = divide(options, bb, nodeNum, 0); 147 147 148 148 // now reorder the triangle list so that it's in order as per the primitiveIndex list. 149 149 KdTree::TriangleList triangleList(_kdTree.getTriangles().size()); … … 152 152 triangleList[i] = _kdTree.getTriangle(_primitiveIndices[i]); 153 153 } 154 154 155 155 _kdTree.getTriangles().swap(triangleList); 156 157 158 #ifdef VERBOSE_OUTPUT 156 157 158 #ifdef VERBOSE_OUTPUT 159 159 OSG_NOTICE<<"Root nodeNum="<<nodeNum<<std::endl; 160 160 #endif 161 162 161 162 163 163 // OSG_NOTICE<<"_kdNodes.size()="<<k_kdNodes.size()<<" estimated size = "<<estimatedSize<<std::endl; 164 164 // OSG_NOTICE<<"_kdLeaves.size()="<<_kdLeaves.size()<<" estimated size = "<<estimatedSize<<std::endl<<std::endl; … … 174 174 _bb.zMax()_bb.zMin()); 175 175 176 #ifdef VERBOSE_OUTPUT 176 #ifdef VERBOSE_OUTPUT 177 177 OSG_NOTICE<<"computeDivisions("<<options._maxNumLevels<<") "<<dimensions<< " { "<<std::endl; 178 178 #endif 179 179 180 180 _axisStack.reserve(options._maxNumLevels); 181 181 182 182 for(unsigned int level=0; level<options._maxNumLevels; ++level) 183 183 { … … 194 194 dimensions[axis] /= 2.0f; 195 195 196 #ifdef VERBOSE_OUTPUT 196 #ifdef VERBOSE_OUTPUT 197 197 OSG_NOTICE<<" "<<level<<", "<<dimensions<<", "<<axis<<std::endl; 198 198 #endif 199 199 } 200 200 201 #ifdef VERBOSE_OUTPUT 201 #ifdef VERBOSE_OUTPUT 202 202 OSG_NOTICE<<"}"<<std::endl; 203 203 #endif … … 210 210 bool needToDivide = level < _axisStack.size() && 211 211 (node.first<0 && static_cast<unsigned int>(node.second)>options._targetNumTrianglesPerLeaf); 212 212 213 213 if (!needToDivide) 214 214 { … … 217 217 int istart = node.first1; 218 218 int iend = istart+node.second1; 219 219 220 220 // leaf is done, now compute bound on it. 221 221 node.bb.init(); … … 229 229 node.bb.expandBy(v1); 230 230 node.bb.expandBy(v2); 231 231 232 232 } 233 233 … … 242 242 node.bb._max.z() += epsilon; 243 243 } 244 245 #ifdef VERBOSE_OUTPUT 244 245 #ifdef VERBOSE_OUTPUT 246 246 if (!node.bb.valid()) 247 247 { … … 263 263 int axis = _axisStack[level]; 264 264 265 #ifdef VERBOSE_OUTPUT 265 #ifdef VERBOSE_OUTPUT 266 266 OSG_NOTICE<<"divide("<<nodeIndex<<", "<<level<< "), axis="<<axis<<std::endl; 267 267 #endif 268 268 269 269 if (node.first<0) 270 { 270 { 271 271 // leaf node as first <= 0, so look at dividing it. 272 272 273 273 int istart = node.first1; 274 274 int iend = istart+node.second1; 275 275 276 276 //OSG_NOTICE<<" divide leaf"<<std::endl; 277 277 278 278 float original_min = bb._min[axis]; 279 279 float original_max = bb._max[axis]; … … 289 289 int left = istart; 290 290 int right = iend; 291 291 292 292 while(left<right) 293 293 { … … 295 295 296 296 while(left<right && (_centers[_primitiveIndices[right]][axis]>mid)) { right; } 297 297 298 298 while(left<right && (_centers[_primitiveIndices[right]][axis]>mid)) { right; } 299 299 … … 305 305 } 306 306 } 307 307 308 308 if (left==right) 309 309 { … … 311 311 else right; 312 312 } 313 313 314 314 KdTree::KdNode leftLeaf(istart1, (rightistart)+1); 315 315 KdTree::KdNode rightLeaf(left1, (iendleft)+1); … … 358 358 } 359 359 360 360 361 361 float restore = bb._max[axis]; 362 362 bb._max[axis] = mid; … … 366 366 367 367 bb._max[axis] = restore; 368 368 369 369 restore = bb._min[axis]; 370 370 bb._min[axis] = mid; … … 372 372 //OSG_NOTICE<<" divide rightLeaf "<<kdTree.getNode(nodeNum).second<<std::endl; 373 373 int rightChildIndex = originalRightChildIndex!=0 ? divide(options, bb, originalRightChildIndex, level+1) : 0; 374 374 375 375 bb._min[axis] = restore; 376 376 377 377 378 378 if (!insitueDivision) … … 381 381 // have invalidate the previous node ref. 382 382 KdTree::KdNode& newNodeRef = _kdTree.getNode(nodeIndex); 383 383 384 384 newNodeRef.first = leftChildIndex; 385 newNodeRef.second = rightChildIndex; 385 newNodeRef.second = rightChildIndex; 386 386 387 387 insitueDivision = true; … … 417 417 OSG_NOTICE<<"NOT expecting to get here"<<std::endl; 418 418 } 419 419 420 420 return nodeIndex; 421 421 422 422 } 423 423 … … 444 444 _inverse_length = _length!=0.0f ? 1.0f/_length : 0.0; 445 445 _d *= _inverse_length; 446 446 447 447 _d_invX = _d.x()!=0.0f ? _d/_d.x() : osg::Vec3(0.0f,0.0f,0.0f); 448 448 _d_invY = _d.y()!=0.0f ? _d/_d.y() : osg::Vec3(0.0f,0.0f,0.0f); … … 464 464 float _length; 465 465 float _inverse_length; 466 466 467 467 osg::Vec3 _d_invX; 468 468 osg::Vec3 _d_invY; … … 481 481 { 482 482 // treat as a leaf 483 483 484 484 //OSG_NOTICE<<"KdTree::intersect("<<&leaf<<")"<<std::endl; 485 485 int istart = node.first1; 486 486 int iend = istart + node.second; 487 487 488 488 for(int i=istart; i<iend; ++i) 489 489 { … … 499 499 osg::Vec3 E2 = v2  v0; 500 500 osg::Vec3 E1 = v1  v0; 501 501 502 502 osg::Vec3 P = _d ^ E2; 503 503 504 504 float det = P * E1; 505 505 506 506 float r,r0,r1,r2; 507 507 508 508 const float esplison = 1e10f; 509 509 if (det>esplison) … … 511 511 float u = (P*T); 512 512 if (u<0.0  u>det) continue; 513 513 514 514 osg::Vec3 Q = T ^ E1; 515 515 float v = (Q*_d); 516 516 if (v<0.0  v>det) continue; 517 517 518 518 if ((u+v)> det) continue; 519 519 520 float inv_det = 1.0f/det; 521 float t = (Q*E2)*inv_det; 522 if (t<0.0  t>_length) continue; 523 524 u *= inv_det; 525 v *= inv_det; 526 527 r0 = 1.0fuv; 528 r1 = u; 529 r2 = v; 530 r = t * _inverse_length; 531 } 532 else if (det<esplison) 533 { 534 535 float u = (P*T); 536 if (u>0.0  u<det) continue; 537 538 osg::Vec3 Q = T ^ E1; 539 float v = (Q*_d); 540 if (v>0.0  v<det) continue; 541 542 if ((u+v) < det) continue; 543 544 float inv_det = 1.0f/det; 545 float t = (Q*E2)*inv_det; 520 float inv_det = 1.0f/det; 521 float t = (Q*E2)*inv_det; 546 522 if (t<0.0  t>_length) continue; 547 523 … … 554 530 r = t * _inverse_length; 555 531 } 532 else if (det<esplison) 533 { 534 535 float u = (P*T); 536 if (u>0.0  u<det) continue; 537 538 osg::Vec3 Q = T ^ E1; 539 float v = (Q*_d); 540 if (v>0.0  v<det) continue; 541 542 if ((u+v) < det) continue; 543 544 float inv_det = 1.0f/det; 545 float t = (Q*E2)*inv_det; 546 if (t<0.0  t>_length) continue; 547 548 u *= inv_det; 549 v *= inv_det; 550 551 r0 = 1.0fuv; 552 r1 = u; 553 r2 = v; 554 r = t * _inverse_length; 555 } 556 556 else 557 557 { … … 562 562 osg::Vec3 normal = E1^E2; 563 563 normal.normalize(); 564 564 565 565 #if 1 566 566 _intersections.push_back(KdTree::LineSegmentIntersection()); … … 705 705 e = s+_d_invZ*(bb.zMax()s.z()); 706 706 } 707 } 707 } 708 708 else 709 709 { … … 723 723 } 724 724 } 725 725 726 726 // OSG_NOTICE<<"clampped segment "<<s<<" "<<e<<std::endl; 727 727 728 728 // if (s==e) return false; 729 729 730 return true; 730 return true; 731 731 } 732 732 … … 767 767 bool KdTree::intersect(const osg::Vec3d& start, const osg::Vec3d& end, LineSegmentIntersections& intersections) const 768 768 { 769 if (_kdNodes.empty()) 769 if (_kdNodes.empty()) 770 770 { 771 771 OSG_NOTICE<<"Warning: _kdTree is empty"<<std::endl; … … 780 780 intersections, 781 781 start, end); 782 782 783 783 intersector.intersect(getNode(0), start, end); 784 784 785 785 return numIntersectionsBefore != intersections.size(); 786 786 } … … 791 791 KdTreeBuilder::KdTreeBuilder(): 792 792 osg::NodeVisitor(osg::NodeVisitor::TRAVERSE_ALL_CHILDREN) 793 { 793 { 794 794 _kdTreePrototype = new osg::KdTree; 795 795 } … … 805 805 { 806 806 for(unsigned int i=0; i<geode.getNumDrawables(); ++i) 807 { 807 { 808 808 809 809 osg::Geometry* geom = geode.getDrawable(i)>asGeometry(); … … 820 820 geom>setShape(kdTree.get()); 821 821 } 822 } 823 } 824 } 822 } 823 } 824 }