root/OpenSceneGraph/trunk/include/osg/KdTree @ 13041

Revision 13041, 5.6 kB (checked in by robert, 3 years ago)

Ran script to remove trailing spaces and tabs

  • Property svn:eol-style set to native
  • Property svn:keywords set to Author Date Id Revision
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#ifndef OSG_KDTREE
15#define OSG_KDTREE 1
16
17#include <osg/Shape>
18#include <osg/Geometry>
19
20#include <map>
21
22namespace osg
23{
24
25/** Implementation of a kdtree for Geometry leaves, to enable fast intersection tests.*/
26class OSG_EXPORT KdTree : public osg::Shape
27{
28    public:
29
30
31        KdTree();
32
33        KdTree(const KdTree& rhs, const osg::CopyOp& copyop=osg::CopyOp::SHALLOW_COPY);
34
35        META_Shape(osg, KdTree)
36
37        struct OSG_EXPORT BuildOptions
38        {
39            BuildOptions();
40
41            unsigned int _numVerticesProcessed;
42            unsigned int _targetNumTrianglesPerLeaf;
43            unsigned int _maxNumLevels;
44        };
45
46
47        /** Build the kdtree from the specified source geometry object.
48          * retun true on success. */
49        virtual bool build(BuildOptions& buildOptions, osg::Geometry* geometry);
50
51        struct LineSegmentIntersection
52        {
53            LineSegmentIntersection():
54                ratio(-1.0),
55                p0(0),
56                p1(0),
57                p2(0),
58                r0(0.0f),
59                r1(0.0f),
60                r2(0.0f),
61                primitiveIndex(0) {}
62
63            bool operator < (const LineSegmentIntersection& rhs) const { return ratio < rhs.ratio; }
64
65            typedef std::vector<unsigned int>   IndexList;
66            typedef std::vector<double>         RatioList;
67
68            double                          ratio;
69            osg::Vec3d                      intersectionPoint;
70            osg::Vec3                       intersectionNormal;
71
72            unsigned int                    p0;
73            unsigned int                    p1;
74            unsigned int                    p2;
75            float                           r0;
76            float                           r1;
77            float                           r2;
78
79            unsigned int                    primitiveIndex;
80        };
81
82
83        typedef std::vector<LineSegmentIntersection> LineSegmentIntersections;
84
85        /** compute the intersection of a line segment and the kdtree, return true if an intersection has been found.*/
86        virtual bool intersect(const osg::Vec3d& start, const osg::Vec3d& end, LineSegmentIntersections& intersections) const;
87
88
89        typedef int value_type;
90
91        struct KdNode
92        {
93            KdNode():
94                first(0),
95                second(0) {}
96
97            KdNode(value_type f, value_type s):
98                first(f),
99                second(s) {}
100
101            osg::BoundingBox bb;
102
103            value_type first;
104            value_type second;
105        };
106
107        struct Triangle
108        {
109            Triangle():
110                p0(0),p1(0),p2(0) {}
111
112            Triangle(unsigned int ip0, unsigned int ip1, unsigned int ip2):
113                p0(ip0), p1(ip1), p2(ip2) {}
114
115            bool operator < (const Triangle& rhs) const
116            {
117                if (p0<rhs.p0) return true;
118                if (p0>rhs.p0) return false;
119                if (p1<rhs.p1) return true;
120                if (p1>rhs.p1) return false;
121                return p2<rhs.p2;
122            }
123
124            unsigned int p0;
125            unsigned int p1;
126            unsigned int p2;
127        };
128
129        typedef std::vector< KdNode >       KdNodeList;
130        typedef std::vector< Triangle >     TriangleList;
131
132        int addNode(const KdNode& node)
133        {
134            int num = static_cast<int>(_kdNodes.size());
135            _kdNodes.push_back(node);
136            return num;
137        }
138
139        KdNode& getNode(int nodeNum) { return _kdNodes[nodeNum]; }
140        const KdNode& getNode(int nodeNum) const { return _kdNodes[nodeNum]; }
141
142        KdNodeList& getNodes() { return _kdNodes; }
143        const KdNodeList& getNodes() const { return _kdNodes; }
144
145        void setVertices(osg::Vec3Array* vertices) { _vertices = vertices; }
146        const osg::Vec3Array* getVertices() const { return _vertices.get(); }
147
148        unsigned int addTriangle(const Triangle& tri)
149        {
150            unsigned int num = static_cast<unsigned int>(_triangles.size());
151            _triangles.push_back(tri);
152            return num;
153        }
154
155        Triangle& getTriangle(unsigned int i) { return _triangles[i]; }
156        const Triangle& getTriangle(unsigned int i) const { return _triangles[i]; }
157
158        TriangleList& getTriangles() { return _triangles; }
159        const TriangleList& getTriangles() const { return _triangles; }
160
161
162    protected:
163
164        osg::ref_ptr<osg::Vec3Array>        _vertices;
165        KdNodeList                          _kdNodes;
166        TriangleList                        _triangles;
167
168};
169
170class OSG_EXPORT KdTreeBuilder : public osg::NodeVisitor
171{
172    public:
173
174        KdTreeBuilder();
175
176        KdTreeBuilder(const KdTreeBuilder& rhs);
177
178        META_NodeVisitor("osg","KdTreeBuilder")
179
180        virtual KdTreeBuilder* clone() { return new KdTreeBuilder(*this); }
181
182        void apply(osg::Geode& geode);
183
184        KdTree::BuildOptions _buildOptions;
185
186        osg::ref_ptr<osg::KdTree> _kdTreePrototype;
187
188
189
190    protected:
191
192        virtual ~KdTreeBuilder() {}
193
194};
195
196}
197
198#endif
Note: See TracBrowser for help on using the browser.