openscenegraph
KdTree
Go to the documentation of this file.
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
52 void setVertices(osg::Vec3Array* vertices) { _vertices = vertices; }
53 const osg::Vec3Array* getVertices() const { return _vertices.get(); }
54
55
56 typedef std::vector< unsigned int > Indices;
57
58 // index in the VertexIndices vector
59 void setPrimitiveIndices(const Indices& indices) { _primitiveIndices = indices; }
60 Indices& getPrimitiveIndices() { return _primitiveIndices; }
61 const Indices& getPrimitiveIndices() const { return _primitiveIndices; }
62
63 // vector containing the primitive vertex index data packed as no_vertice_indices then vertex indices ie. for points it's (1, p0), for lines (2, p0, p1) etc.
64 void setVertexIndices(const Indices& indices) { _vertexIndices = indices; }
65 Indices& getVertexIndices() { return _vertexIndices; }
66 const Indices& getVertexIndices() const { return _vertexIndices; }
67
68
69 inline unsigned int addPoint(unsigned int p0)
70 {
71 unsigned int i = _vertexIndices.size();
72 _vertexIndices.push_back(_primitiveIndices.size() + _degenerateCount);
73 _vertexIndices.push_back(1);
74 _vertexIndices.push_back(p0);
75 _primitiveIndices.push_back(i);
76 return i;
77 }
78 inline unsigned int addLine(unsigned int p0, unsigned int p1)
79 {
80 unsigned int i = _vertexIndices.size();
81 _vertexIndices.push_back(_primitiveIndices.size() + _degenerateCount);
82 _vertexIndices.push_back(2);
83 _vertexIndices.push_back(p0);
84 _vertexIndices.push_back(p1);
85 _primitiveIndices.push_back(i);
86 return i;
87 }
88
89 inline unsigned int addTriangle(unsigned int p0, unsigned int p1, unsigned int p2)
90 {
91 unsigned int i = _vertexIndices.size();
92 _vertexIndices.push_back(_primitiveIndices.size() + _degenerateCount);
93 _vertexIndices.push_back(3);
94 _vertexIndices.push_back(p0);
95 _vertexIndices.push_back(p1);
96 _vertexIndices.push_back(p2);
97 _primitiveIndices.push_back(i);
98 return i;
99 }
100
101 inline unsigned int addQuad(unsigned int p0, unsigned int p1, unsigned int p2, unsigned int p3)
102 {
103 unsigned int i = _vertexIndices.size();
104 _vertexIndices.push_back(_primitiveIndices.size() + _degenerateCount);
105 _vertexIndices.push_back(4);
106 _vertexIndices.push_back(p0);
107 _vertexIndices.push_back(p1);
108 _vertexIndices.push_back(p2);
109 _vertexIndices.push_back(p3);
110 _primitiveIndices.push_back(i);
111 return i;
112 }
113
114
115
116 typedef int value_type;
117
118 struct KdNode
119 {
120 KdNode():
121 first(0),
122 second(0) {}
123
124 KdNode(value_type f, value_type s):
125 first(f),
126 second(s) {}
127
128 osg::BoundingBox bb;
129
130 value_type first;
131 value_type second;
132 };
133 typedef std::vector< KdNode > KdNodeList;
134
135 int addNode(const KdNode& node)
136 {
137 int num = static_cast<int>(_kdNodes.size());
138 _kdNodes.push_back(node);
139 return num;
140 }
141
142 KdNode& getNode(int nodeNum) { return _kdNodes[nodeNum]; }
143 const KdNode& getNode(int nodeNum) const { return _kdNodes[nodeNum]; }
144
145 KdNodeList& getNodes() { return _kdNodes; }
146 const KdNodeList& getNodes() const { return _kdNodes; }
147
148
149 template<class IntersectFunctor>
150 void intersect(IntersectFunctor& functor, const KdNode& node) const
151 {
152 if (node.first<0)
153 {
154 // treat as a leaf
155 int istart = -node.first-1;
156 int iend = istart + node.second;
157
158 for(int i=istart; i<iend; ++i)
159 {
160 unsigned int primitiveIndex = _primitiveIndices[i];
161 unsigned int originalPIndex = _vertexIndices[primitiveIndex++];
162 unsigned int numVertices = _vertexIndices[primitiveIndex++];
163 switch(numVertices)
164 {
165 case(1): functor.intersect(_vertices.get(), originalPIndex, _vertexIndices[primitiveIndex]); break;
166 case(2): functor.intersect(_vertices.get(), originalPIndex, _vertexIndices[primitiveIndex], _vertexIndices[primitiveIndex+1]); break;
167 case(3): functor.intersect(_vertices.get(), originalPIndex, _vertexIndices[primitiveIndex], _vertexIndices[primitiveIndex+1], _vertexIndices[primitiveIndex+2]); break;
168 case(4): functor.intersect(_vertices.get(), originalPIndex, _vertexIndices[primitiveIndex], _vertexIndices[primitiveIndex+1], _vertexIndices[primitiveIndex+2], _vertexIndices[primitiveIndex+3]); break;
169 default : OSG_NOTICE<<"Warning: KdTree::intersect() encounted unsupported primitive size of "<<numVertices<<std::endl; break;
170 }
171 }
172 }
173 else if (functor.enter(node.bb))
174 {
175 if (node.first>0) intersect(functor, _kdNodes[node.first]);
176 if (node.second>0) intersect(functor, _kdNodes[node.second]);
177
178 functor.leave();
179 }
180 }
181
182 unsigned int _degenerateCount;
183
184 protected:
185
186 osg::ref_ptr<osg::Vec3Array> _vertices;
187 Indices _primitiveIndices;
188 Indices _vertexIndices;
189 KdNodeList _kdNodes;
190};
191
192class OSG_EXPORT KdTreeBuilder : public osg::NodeVisitor
193{
194 public:
195
196 KdTreeBuilder();
197
198 KdTreeBuilder(const KdTreeBuilder& rhs);
199
200 META_NodeVisitor(osg, KdTreeBuilder)
201
202 virtual KdTreeBuilder* clone() { return new KdTreeBuilder(*this); }
203
204 void apply(Geometry& geometry);
205
206 KdTree::BuildOptions _buildOptions;
207
208 osg::ref_ptr<osg::KdTree> _kdTreePrototype;
209
210
211
212 protected:
213
214 virtual ~KdTreeBuilder() {}
215
216};
217
218}
219
220#endif