root/OpenSceneGraph/trunk/src/osg/KdTree.cpp @ 13587

Revision 13587, 24.1 kB (checked in by robert, 25 hours ago)

Improved handling of setting of the depth of the UI.

  • Property svn:eol-style set to native
Line 
1/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
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
5 * (at your option) any later version.  The full license is in LICENSE file
6 * included with this distribution, and on the openscenegraph.org website.
7 *
8 * This library is distributed in the hope that it will be useful,
9 * but WITHOUT ANY WARRANTY; without even the implied warranty of
10 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
11 * OpenSceneGraph Public License for more details.
12*/
13
14#include <osg/KdTree>
15#include <osg/Geode>
16#include <osg/TriangleIndexFunctor>
17#include <osg/Timer>
18
19#include <osg/io_utils>
20
21using namespace osg;
22
23//#define VERBOSE_OUTPUT
24
25////////////////////////////////////////////////////////////////////////////////
26//
27// BuildKdTree Declarartion - class used for building an single KdTree
28
29struct BuildKdTree
30{
31    BuildKdTree(KdTree& kdTree):
32        _kdTree(kdTree) {}
33
34    typedef std::vector< osg::Vec3 >            CenterList;
35    typedef std::vector< unsigned int >           Indices;
36    typedef std::vector< unsigned int >         AxisStack;
37
38    bool build(KdTree::BuildOptions& options, osg::Geometry* geometry);
39
40    void computeDivisions(KdTree::BuildOptions& options);
41
42    int divide(KdTree::BuildOptions& options, osg::BoundingBox& bb, int nodeIndex, unsigned int level);
43
44    KdTree&             _kdTree;
45
46    osg::BoundingBox    _bb;
47    AxisStack           _axisStack;
48    Indices             _primitiveIndices;
49    CenterList          _centers;
50
51protected:
52
53    BuildKdTree& operator = (const BuildKdTree&) { return *this; }
54};
55
56////////////////////////////////////////////////////////////////////////////////
57//
58// Functor for collecting triangle indices from Geometry
59
60struct TriangleIndicesCollector
61{
62    TriangleIndicesCollector():
63        _buildKdTree(0)
64    {
65    }
66
67    inline void operator () (unsigned int p0, unsigned int p1, unsigned int p2)
68    {
69        const osg::Vec3& v0 = (*(_buildKdTree->_kdTree.getVertices()))[p0];
70        const osg::Vec3& v1 = (*(_buildKdTree->_kdTree.getVertices()))[p1];
71        const osg::Vec3& v2 = (*(_buildKdTree->_kdTree.getVertices()))[p2];
72
73        // discard degenerate points
74        if (v0==v1 || v1==v2 || v1==v2)
75        {
76            //OSG_NOTICE<<"Disgarding degenerate triangle"<<std::endl;
77            return;
78        }
79
80        unsigned int i = _buildKdTree->_kdTree.addTriangle(KdTree::Triangle(p0,p1,p2));
81
82        osg::BoundingBox bb;
83        bb.expandBy(v0);
84        bb.expandBy(v1);
85        bb.expandBy(v2);
86
87        _buildKdTree->_centers.push_back(bb.center());
88        _buildKdTree->_primitiveIndices.push_back(i);
89
90    }
91
92    BuildKdTree* _buildKdTree;
93
94};
95
96
97////////////////////////////////////////////////////////////////////////////////
98//
99// BuildKdTree Implementation
100
101bool BuildKdTree::build(KdTree::BuildOptions& options, osg::Geometry* geometry)
102{
103
104#ifdef VERBOSE_OUTPUT
105    OSG_NOTICE<<"osg::KDTreeBuilder::createKDTree()"<<std::endl;146
106#endif
107
108    osg::Vec3Array* vertices = dynamic_cast<osg::Vec3Array*>(geometry->getVertexArray());
109    if (!vertices) return false;
110
111    if (vertices->size() <= options._targetNumTrianglesPerLeaf) return false;
112
113    _bb = geometry->getBound();
114    _kdTree.setVertices(vertices);
115
116    unsigned int estimatedSize = (unsigned int)(2.0*float(vertices->size())/float(options._targetNumTrianglesPerLeaf));
117
118#ifdef VERBOSE_OUTPUT
119    OSG_NOTICE<<"kdTree->_kdNodes.reserve()="<<estimatedSize<<std::endl<<std::endl;
120#endif
121
122    _kdTree.getNodes().reserve(estimatedSize*5);
123
124    computeDivisions(options);
125
126    options._numVerticesProcessed += vertices->size();
127
128    unsigned int estimatedNumTriangles = vertices->size()*2;
129    _primitiveIndices.reserve(estimatedNumTriangles);
130    _centers.reserve(estimatedNumTriangles);
131
132    _kdTree.getTriangles().reserve(estimatedNumTriangles);
133
134    osg::TriangleIndexFunctor<TriangleIndicesCollector> collectTriangleIndices;
135    collectTriangleIndices._buildKdTree = this;
136    geometry->accept(collectTriangleIndices);
137
138    _primitiveIndices.reserve(vertices->size());
139
140    KdTree::KdNode node(-1, _primitiveIndices.size());
141    node.bb = _bb;
142
143    int nodeNum = _kdTree.addNode(node);
144
145    osg::BoundingBox bb = _bb;
146    nodeNum = divide(options, bb, nodeNum, 0);
147
148    // now reorder the triangle list so that it's in order as per the primitiveIndex list.
149    KdTree::TriangleList triangleList(_kdTree.getTriangles().size());
150    for(unsigned int i=0; i<_primitiveIndices.size(); ++i)
151    {
152        triangleList[i] = _kdTree.getTriangle(_primitiveIndices[i]);
153    }
154
155    _kdTree.getTriangles().swap(triangleList);
156
157
158#ifdef VERBOSE_OUTPUT
159    OSG_NOTICE<<"Root nodeNum="<<nodeNum<<std::endl;
160#endif
161
162
163//    OSG_NOTICE<<"_kdNodes.size()="<<k_kdNodes.size()<<"  estimated size = "<<estimatedSize<<std::endl;
164//    OSG_NOTICE<<"_kdLeaves.size()="<<_kdLeaves.size()<<"  estimated size = "<<estimatedSize<<std::endl<<std::endl;
165
166
167    return !_kdTree.getNodes().empty();
168}
169
170void BuildKdTree::computeDivisions(KdTree::BuildOptions& options)
171{
172    osg::Vec3 dimensions(_bb.xMax()-_bb.xMin(),
173                         _bb.yMax()-_bb.yMin(),
174                         _bb.zMax()-_bb.zMin());
175
176#ifdef VERBOSE_OUTPUT
177    OSG_NOTICE<<"computeDivisions("<<options._maxNumLevels<<") "<<dimensions<< " { "<<std::endl;
178#endif
179
180    _axisStack.reserve(options._maxNumLevels);
181
182    for(unsigned int level=0; level<options._maxNumLevels; ++level)
183    {
184        int axis = 0;
185        if (dimensions[0]>=dimensions[1])
186        {
187            if (dimensions[0]>=dimensions[2]) axis = 0;
188            else axis = 2;
189        }
190        else if (dimensions[1]>=dimensions[2]) axis = 1;
191        else axis = 2;
192
193        _axisStack.push_back(axis);
194        dimensions[axis] /= 2.0f;
195
196#ifdef VERBOSE_OUTPUT
197        OSG_NOTICE<<"  "<<level<<", "<<dimensions<<", "<<axis<<std::endl;
198#endif
199    }
200
201#ifdef VERBOSE_OUTPUT
202    OSG_NOTICE<<"}"<<std::endl;
203#endif
204}
205
206int BuildKdTree::divide(KdTree::BuildOptions& options, osg::BoundingBox& bb, int nodeIndex, unsigned int level)
207{
208    KdTree::KdNode& node = _kdTree.getNode(nodeIndex);
209
210    bool needToDivide = level < _axisStack.size() &&
211                        (node.first<0 && static_cast<unsigned int>(node.second)>options._targetNumTrianglesPerLeaf);
212
213    if (!needToDivide)
214    {
215        if (node.first<0)
216        {
217            int istart = -node.first-1;
218            int iend = istart+node.second-1;
219
220            // leaf is done, now compute bound on it.
221            node.bb.init();
222            for(int i=istart; i<=iend; ++i)
223            {
224                const KdTree::Triangle& tri = _kdTree.getTriangle(_primitiveIndices[i]);
225                const osg::Vec3& v0 = (*_kdTree.getVertices())[tri.p0];
226                const osg::Vec3& v1 = (*_kdTree.getVertices())[tri.p1];
227                const osg::Vec3& v2 = (*_kdTree.getVertices())[tri.p2];
228                node.bb.expandBy(v0);
229                node.bb.expandBy(v1);
230                node.bb.expandBy(v2);
231
232            }
233
234            if (node.bb.valid())
235            {
236                float epsilon = 1e-6f;
237                node.bb._min.x() -= epsilon;
238                node.bb._min.y() -= epsilon;
239                node.bb._min.z() -= epsilon;
240                node.bb._max.x() += epsilon;
241                node.bb._max.y() += epsilon;
242                node.bb._max.z() += epsilon;
243            }
244
245#ifdef VERBOSE_OUTPUT
246            if (!node.bb.valid())
247            {
248                OSG_NOTICE<<"After reset "<<node.first<<","<<node.second<<std::endl;
249                OSG_NOTICE<<"  bb._min ("<<node.bb._min<<")"<<std::endl;
250                OSG_NOTICE<<"  bb._max ("<<node.bb._max<<")"<<std::endl;
251            }
252            else
253            {
254                OSG_NOTICE<<"Set bb for nodeIndex = "<<nodeIndex<<std::endl;
255            }
256#endif
257        }
258
259        return nodeIndex;
260
261    }
262
263    int axis = _axisStack[level];
264
265#ifdef VERBOSE_OUTPUT
266    OSG_NOTICE<<"divide("<<nodeIndex<<", "<<level<< "), axis="<<axis<<std::endl;
267#endif
268
269    if (node.first<0)
270    {
271        // leaf node as first <= 0, so look at dividing it.
272
273        int istart = -node.first-1;
274        int iend = istart+node.second-1;
275
276        //OSG_NOTICE<<"  divide leaf"<<std::endl;
277
278        float original_min = bb._min[axis];
279        float original_max = bb._max[axis];
280
281        float mid = (original_min+original_max)*0.5f;
282
283        int originalLeftChildIndex = 0;
284        int originalRightChildIndex = 0;
285        bool insitueDivision = false;
286
287        {
288            //osg::Vec3Array* vertices = kdTree._vertices.get();
289            int left = istart;
290            int right = iend;
291
292            while(left<right)
293            {
294                while(left<right && (_centers[_primitiveIndices[left]][axis]<=mid)) { ++left; }
295
296                while(left<right && (_centers[_primitiveIndices[right]][axis]>mid)) { --right; }
297
298                while(left<right && (_centers[_primitiveIndices[right]][axis]>mid)) { --right; }
299
300                if (left<right)
301                {
302                    std::swap(_primitiveIndices[left], _primitiveIndices[right]);
303                    ++left;
304                    --right;
305                }
306            }
307
308            if (left==right)
309            {
310                if (_centers[_primitiveIndices[left]][axis]<=mid) ++left;
311                else --right;
312            }
313
314            KdTree::KdNode leftLeaf(-istart-1, (right-istart)+1);
315            KdTree::KdNode rightLeaf(-left-1, (iend-left)+1);
316
317#if 0
318            OSG_NOTICE<<"In  node.first     ="<<node.first     <<" node.second     ="<<node.second<<std::endl;
319            OSG_NOTICE<<"    leftLeaf.first ="<<leftLeaf.first <<" leftLeaf.second ="<<leftLeaf.second<<std::endl;
320            OSG_NOTICE<<"    rightLeaf.first="<<rightLeaf.first<<" rightLeaf.second="<<rightLeaf.second<<std::endl;
321            OSG_NOTICE<<"    left="<<left<<" right="<<right<<std::endl;
322
323            if (node.second != (leftLeaf.second +rightLeaf.second))
324            {
325                OSG_NOTICE<<"*** Error in size, leaf.second="<<node.second
326                                        <<", leftLeaf.second="<<leftLeaf.second
327                                        <<", rightLeaf.second="<<rightLeaf.second<<std::endl;
328            }
329            else
330            {
331                OSG_NOTICE<<"Size OK, leaf.second="<<node.second
332                                        <<", leftLeaf.second="<<leftLeaf.second
333                                        <<", rightLeaf.second="<<rightLeaf.second<<std::endl;
334            }
335#endif
336
337            if (leftLeaf.second<=0)
338            {
339                //OSG_NOTICE<<"LeftLeaf empty"<<std::endl;
340                originalLeftChildIndex = 0;
341                //originalRightChildIndex = addNode(rightLeaf);
342                originalRightChildIndex = nodeIndex;
343                insitueDivision = true;
344            }
345            else if (rightLeaf.second<=0)
346            {
347                //OSG_NOTICE<<"RightLeaf empty"<<std::endl;
348                // originalLeftChildIndex = addNode(leftLeaf);
349                originalLeftChildIndex = nodeIndex;
350                originalRightChildIndex = 0;
351                insitueDivision = true;
352            }
353            else
354            {
355                originalLeftChildIndex = _kdTree.addNode(leftLeaf);
356                originalRightChildIndex = _kdTree.addNode(rightLeaf);
357            }
358        }
359
360
361        float restore = bb._max[axis];
362        bb._max[axis] = mid;
363
364        //OSG_NOTICE<<"  divide leftLeaf "<<kdTree.getNode(nodeNum).first<<std::endl;
365        int leftChildIndex = originalLeftChildIndex!=0 ? divide(options, bb, originalLeftChildIndex, level+1) : 0;
366
367        bb._max[axis] = restore;
368
369        restore = bb._min[axis];
370        bb._min[axis] = mid;
371
372        //OSG_NOTICE<<"  divide rightLeaf "<<kdTree.getNode(nodeNum).second<<std::endl;
373        int rightChildIndex = originalRightChildIndex!=0 ? divide(options, bb, originalRightChildIndex, level+1) : 0;
374
375        bb._min[axis] = restore;
376
377
378        if (!insitueDivision)
379        {
380            // take a second reference to node we are working on as the std::vector<> resize could
381            // have invalidate the previous node ref.
382            KdTree::KdNode& newNodeRef = _kdTree.getNode(nodeIndex);
383
384            newNodeRef.first = leftChildIndex;
385            newNodeRef.second = rightChildIndex;
386
387            insitueDivision = true;
388
389            newNodeRef.bb.init();
390            if (leftChildIndex!=0) newNodeRef.bb.expandBy(_kdTree.getNode(leftChildIndex).bb);
391            if (rightChildIndex!=0) newNodeRef.bb.expandBy(_kdTree.getNode(rightChildIndex).bb);
392
393            if (!newNodeRef.bb.valid())
394            {
395                OSG_NOTICE<<"leftChildIndex="<<leftChildIndex<<" && originalLeftChildIndex="<<originalLeftChildIndex<<std::endl;
396                OSG_NOTICE<<"rightChildIndex="<<rightChildIndex<<" && originalRightChildIndex="<<originalRightChildIndex<<std::endl;
397
398                OSG_NOTICE<<"Invalid BB leftChildIndex="<<leftChildIndex<<", "<<rightChildIndex<<std::endl;
399                OSG_NOTICE<<"  bb._min ("<<newNodeRef.bb._min<<")"<<std::endl;
400                OSG_NOTICE<<"  bb._max ("<<newNodeRef.bb._max<<")"<<std::endl;
401
402                if (leftChildIndex!=0)
403                {
404                    OSG_NOTICE<<"  getNode(leftChildIndex).bb min = "<<_kdTree.getNode(leftChildIndex).bb._min<<std::endl;
405                    OSG_NOTICE<<"                                 max = "<<_kdTree.getNode(leftChildIndex).bb._max<<std::endl;
406                }
407                if (rightChildIndex!=0)
408                {
409                    OSG_NOTICE<<"  getNode(rightChildIndex).bb min = "<<_kdTree.getNode(rightChildIndex).bb._min<<std::endl;
410                    OSG_NOTICE<<"                              max = "<<_kdTree.getNode(rightChildIndex).bb._max<<std::endl;
411                }
412            }
413        }
414    }
415    else
416    {
417        OSG_NOTICE<<"NOT expecting to get here"<<std::endl;
418    }
419
420    return nodeIndex;
421
422}
423
424////////////////////////////////////////////////////////////////////////////////
425//
426// IntersectKdTree
427//
428struct IntersectKdTree
429{
430    IntersectKdTree(const osg::Vec3Array& vertices,
431                    const KdTree::KdNodeList& nodes,
432                    const KdTree::TriangleList& triangles,
433                    KdTree::LineSegmentIntersections& intersections,
434                    const osg::Vec3d& s, const osg::Vec3d& e):
435                        _vertices(vertices),
436                        _kdNodes(nodes),
437                        _triangles(triangles),
438                        _intersections(intersections),
439                        _s(s),
440                        _e(e)
441    {
442        _d = e - s;
443        _length = _d.length();
444        _inverse_length = _length!=0.0f ? 1.0f/_length : 0.0;
445        _d *= _inverse_length;
446
447        _d_invX = _d.x()!=0.0f ? _d/_d.x() : osg::Vec3(0.0f,0.0f,0.0f);
448        _d_invY = _d.y()!=0.0f ? _d/_d.y() : osg::Vec3(0.0f,0.0f,0.0f);
449        _d_invZ = _d.z()!=0.0f ? _d/_d.z() : osg::Vec3(0.0f,0.0f,0.0f);
450    }
451
452    void intersect(const KdTree::KdNode& node, const osg::Vec3& s, const osg::Vec3& e) const;
453    bool intersectAndClip(osg::Vec3& s, osg::Vec3& e, const osg::BoundingBox& bb) const;
454
455    const osg::Vec3Array&               _vertices;
456    const KdTree::KdNodeList&           _kdNodes;
457    const KdTree::TriangleList&         _triangles;
458    KdTree::LineSegmentIntersections&   _intersections;
459
460    osg::Vec3 _s;
461    osg::Vec3 _e;
462
463    osg::Vec3 _d;
464    float     _length;
465    float     _inverse_length;
466
467    osg::Vec3 _d_invX;
468    osg::Vec3 _d_invY;
469    osg::Vec3 _d_invZ;
470
471
472protected:
473
474    IntersectKdTree& operator = (const IntersectKdTree&) { return *this; }
475};
476
477
478void IntersectKdTree::intersect(const KdTree::KdNode& node, const osg::Vec3& ls, const osg::Vec3& le) const
479{
480    if (node.first<0)
481    {
482        // treat as a leaf
483
484        //OSG_NOTICE<<"KdTree::intersect("<<&leaf<<")"<<std::endl;
485        int istart = -node.first-1;
486        int iend = istart + node.second;
487
488        for(int i=istart; i<iend; ++i)
489        {
490            //const Triangle& tri = _triangles[_primitiveIndices[i]];
491            const KdTree::Triangle& tri = _triangles[i];
492            // OSG_NOTICE<<"   tri("<<tri.p1<<","<<tri.p2<<","<<tri.p3<<")"<<std::endl;
493
494            const osg::Vec3& v0 = _vertices[tri.p0];
495            const osg::Vec3& v1 = _vertices[tri.p1];
496            const osg::Vec3& v2 = _vertices[tri.p2];
497
498            osg::Vec3 T = _s - v0;
499            osg::Vec3 E2 = v2 - v0;
500            osg::Vec3 E1 = v1 - v0;
501
502            osg::Vec3 P =  _d ^ E2;
503
504            float det = P * E1;
505
506            float r,r0,r1,r2;
507
508            const float esplison = 1e-10f;
509            if (det>esplison)
510            {
511                float u = (P*T);
512                if (u<0.0 || u>det) continue;
513
514                osg::Vec3 Q = T ^ E1;
515                float v = (Q*_d);
516                if (v<0.0 || v>det) continue;
517
518                if ((u+v)> det) continue;
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.0f-u-v;
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;
546                if (t<0.0 || t>_length) continue;
547
548                u *= inv_det;
549                v *= inv_det;
550
551                r0 = 1.0f-u-v;
552                r1 = u;
553                r2 = v;
554                r = t * _inverse_length;
555            }
556            else
557            {
558                continue;
559            }
560
561            osg::Vec3 in = v0*r0 + v1*r1 + v2*r2;
562            osg::Vec3 normal = E1^E2;
563            normal.normalize();
564
565#if 1
566            _intersections.push_back(KdTree::LineSegmentIntersection());
567            KdTree::LineSegmentIntersection& intersection = _intersections.back();
568
569            intersection.ratio = r;
570            intersection.primitiveIndex = i;
571            intersection.intersectionPoint = in;
572            intersection.intersectionNormal = normal;
573
574            intersection.p0 = tri.p0;
575            intersection.p1 = tri.p1;
576            intersection.p2 = tri.p2;
577            intersection.r0 = r0;
578            intersection.r1 = r1;
579            intersection.r2 = r2;
580
581#endif
582            // OSG_NOTICE<<"  got intersection ("<<in<<") ratio="<<r<<std::endl;
583        }
584    }
585    else
586    {
587        if (node.first>0)
588        {
589            osg::Vec3 l(ls), e(le);
590            if (intersectAndClip(l,e, _kdNodes[node.first].bb))
591            {
592                intersect(_kdNodes[node.first], l, e);
593            }
594        }
595        if (node.second>0)
596        {
597            osg::Vec3 l(ls), e(le);
598            if (intersectAndClip(l,e, _kdNodes[node.second].bb))
599            {
600                intersect(_kdNodes[node.second], l, e);
601            }
602        }
603    }
604}
605
606bool IntersectKdTree::intersectAndClip(osg::Vec3& s, osg::Vec3& e, const osg::BoundingBox& bb) const
607{
608    //return true;
609
610    //if (!bb.valid()) return true;
611
612    // compate s and e against the xMin to xMax range of bb.
613    if (s.x()<=e.x())
614    {
615
616        // trivial reject of segment wholely outside.
617        if (e.x()<bb.xMin()) return false;
618        if (s.x()>bb.xMax()) return false;
619
620        if (s.x()<bb.xMin())
621        {
622            // clip s to xMin.
623            s = s+_d_invX*(bb.xMin()-s.x());
624        }
625
626        if (e.x()>bb.xMax())
627        {
628            // clip e to xMax.
629            e = s+_d_invX*(bb.xMax()-s.x());
630        }
631    }
632    else
633    {
634        if (s.x()<bb.xMin()) return false;
635        if (e.x()>bb.xMax()) return false;
636
637        if (e.x()<bb.xMin())
638        {
639            // clip s to xMin.
640            e = s+_d_invX*(bb.xMin()-s.x());
641        }
642
643        if (s.x()>bb.xMax())
644        {
645            // clip e to xMax.
646            s = s+_d_invX*(bb.xMax()-s.x());
647        }
648    }
649
650    // compate s and e against the yMin to yMax range of bb.
651    if (s.y()<=e.y())
652    {
653
654        // trivial reject of segment wholely outside.
655        if (e.y()<bb.yMin()) return false;
656        if (s.y()>bb.yMax()) return false;
657
658        if (s.y()<bb.yMin())
659        {
660            // clip s to yMin.
661            s = s+_d_invY*(bb.yMin()-s.y());
662        }
663
664        if (e.y()>bb.yMax())
665        {
666            // clip e to yMax.
667            e = s+_d_invY*(bb.yMax()-s.y());
668        }
669    }
670    else
671    {
672        if (s.y()<bb.yMin()) return false;
673        if (e.y()>bb.yMax()) return false;
674
675        if (e.y()<bb.yMin())
676        {
677            // clip s to yMin.
678            e = s+_d_invY*(bb.yMin()-s.y());
679        }
680
681        if (s.y()>bb.yMax())
682        {
683            // clip e to yMax.
684            s = s+_d_invY*(bb.yMax()-s.y());
685        }
686    }
687
688    // compate s and e against the zMin to zMax range of bb.
689    if (s.z()<=e.z())
690    {
691
692        // trivial reject of segment wholely outside.
693        if (e.z()<bb.zMin()) return false;
694        if (s.z()>bb.zMax()) return false;
695
696        if (s.z()<bb.zMin())
697        {
698            // clip s to zMin.
699            s = s+_d_invZ*(bb.zMin()-s.z());
700        }
701
702        if (e.z()>bb.zMax())
703        {
704            // clip e to zMax.
705            e = s+_d_invZ*(bb.zMax()-s.z());
706        }
707    }
708    else
709    {
710        if (s.z()<bb.zMin()) return false;
711        if (e.z()>bb.zMax()) return false;
712
713        if (e.z()<bb.zMin())
714        {
715            // clip s to zMin.
716            e = s+_d_invZ*(bb.zMin()-s.z());
717        }
718
719        if (s.z()>bb.zMax())
720        {
721            // clip e to zMax.
722            s = s+_d_invZ*(bb.zMax()-s.z());
723        }
724    }
725
726    // OSG_NOTICE<<"clampped segment "<<s<<" "<<e<<std::endl;
727
728    // if (s==e) return false;
729
730    return true;
731}
732
733
734////////////////////////////////////////////////////////////////////////////////
735//
736// KdTree::BuildOptions
737
738KdTree::BuildOptions::BuildOptions():
739        _numVerticesProcessed(0),
740        _targetNumTrianglesPerLeaf(4),
741        _maxNumLevels(32)
742{
743}
744
745////////////////////////////////////////////////////////////////////////////////
746//
747// KdTree
748
749KdTree::KdTree()
750{
751}
752
753KdTree::KdTree(const KdTree& rhs, const osg::CopyOp& copyop):
754    Shape(rhs, copyop),
755    _vertices(rhs._vertices),
756    _kdNodes(rhs._kdNodes),
757    _triangles(rhs._triangles)
758{
759}
760
761bool KdTree::build(BuildOptions& options, osg::Geometry* geometry)
762{
763    BuildKdTree build(*this);
764    return build.build(options, geometry);
765}
766
767bool KdTree::intersect(const osg::Vec3d& start, const osg::Vec3d& end, LineSegmentIntersections& intersections) const
768{
769    if (_kdNodes.empty())
770    {
771        OSG_NOTICE<<"Warning: _kdTree is empty"<<std::endl;
772        return false;
773    }
774
775    unsigned int numIntersectionsBefore = intersections.size();
776
777    IntersectKdTree intersector(*_vertices,
778                                _kdNodes,
779                                _triangles,
780                                intersections,
781                                start, end);
782
783    intersector.intersect(getNode(0), start, end);
784
785    return numIntersectionsBefore != intersections.size();
786}
787
788////////////////////////////////////////////////////////////////////////////////
789//
790// KdTreeBuilder
791KdTreeBuilder::KdTreeBuilder():
792    osg::NodeVisitor(osg::NodeVisitor::TRAVERSE_ALL_CHILDREN)
793{
794    _kdTreePrototype = new osg::KdTree;
795}
796
797KdTreeBuilder::KdTreeBuilder(const KdTreeBuilder& rhs):
798    osg::Referenced(true),
799    osg::NodeVisitor(osg::NodeVisitor::TRAVERSE_ALL_CHILDREN),
800    _buildOptions(rhs._buildOptions),
801    _kdTreePrototype(rhs._kdTreePrototype)
802{
803}
804
805void KdTreeBuilder::apply(osg::Geode& geode)
806{
807    for(unsigned int i=0; i<geode.getNumDrawables(); ++i)
808    {
809
810        osg::Geometry* geom = geode.getDrawable(i)->asGeometry();
811        if (geom)
812        {
813            osg::KdTree* previous = dynamic_cast<osg::KdTree*>(geom->getShape());
814            if (previous) continue;
815
816            osg::ref_ptr<osg::Object> obj = _kdTreePrototype->cloneType();
817            osg::ref_ptr<osg::KdTree> kdTree = dynamic_cast<osg::KdTree*>(obj.get());
818
819            if (kdTree->build(_buildOptions, geom))
820            {
821                geom->setShape(kdTree.get());
822            }
823        }
824    }
825}
Note: See TracBrowser for help on using the browser.