OpenSceneGraph 3.6.5
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
27{
28 public:
29
30
32
34
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
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; }
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; }
66 const Indices& getVertexIndices() const { return _vertexIndices; }
67
68
69 inline unsigned int addPoint(unsigned int p0)
70 {
71 unsigned int i = _vertexIndices.size();
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();
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();
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();
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 {
121 first(0),
122 second(0) {}
123
125 first(f),
126 second(s) {}
127
129
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
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
190};
191
193{
194 public:
195
197
199
201
202 virtual KdTreeBuilder* clone() { return new KdTreeBuilder(*this); }
203
204 void apply(Geometry& geometry);
205
206 KdTree::BuildOptions _buildOptions;
207
209
210
211
212 protected:
213
214 virtual ~KdTreeBuilder() {}
215
216};
217
218}
219
220#endif
#define OSG_NOTICE
Definition Notify:86
The core osg library provides the basic scene graph classes such as Nodes, State and Drawables,...
Definition AlphaFunc:19
TemplateArray< Vec3, Array::Vec3ArrayType, 3, GL_FLOAT > Vec3Array
Definition Array:449
BoundingBoxd BoundingBox
Definition BoundingBox:257
Copy Op(erator) used to control whether shallow or deep copy is used during copy construction and clo...
Definition CopyOp:41
@ SHALLOW_COPY
Definition CopyOp:47
Definition Geometry:31
void intersect(IntersectFunctor &functor, const KdNode &node) const
Definition KdTree:150
unsigned int addTriangle(unsigned int p0, unsigned int p1, unsigned int p2)
Definition KdTree:89
Indices & getPrimitiveIndices()
Definition KdTree:60
void setVertexIndices(const Indices &indices)
Definition KdTree:64
const Indices & getVertexIndices() const
Definition KdTree:66
unsigned int addPoint(unsigned int p0)
Definition KdTree:69
const osg::Vec3Array * getVertices() const
Definition KdTree:53
META_Shape(osg, KdTree) struct OSG_EXPORT BuildOptions
Definition KdTree:35
KdNode & getNode(int nodeNum)
Definition KdTree:142
int addNode(const KdNode &node)
Definition KdTree:135
unsigned int addLine(unsigned int p0, unsigned int p1)
Definition KdTree:78
Indices _primitiveIndices
Definition KdTree:187
Indices _vertexIndices
Definition KdTree:188
const KdNodeList & getNodes() const
Definition KdTree:146
int value_type
Definition KdTree:116
std::vector< unsigned int > Indices
Definition KdTree:56
unsigned int _degenerateCount
Definition KdTree:182
KdNodeList _kdNodes
Definition KdTree:189
std::vector< KdNode > KdNodeList
Definition KdTree:133
Indices & getVertexIndices()
Definition KdTree:65
void setVertices(osg::Vec3Array *vertices)
Definition KdTree:52
osg::ref_ptr< osg::Vec3Array > _vertices
Definition KdTree:186
const KdNode & getNode(int nodeNum) const
Definition KdTree:143
KdTree(const KdTree &rhs, const osg::CopyOp &copyop=osg::CopyOp::SHALLOW_COPY)
virtual bool build(BuildOptions &buildOptions, osg::Geometry *geometry)
Build the kdtree from the specified source geometry object.
void setPrimitiveIndices(const Indices &indices)
Definition KdTree:59
unsigned int addQuad(unsigned int p0, unsigned int p1, unsigned int p2, unsigned int p3)
Definition KdTree:101
const Indices & getPrimitiveIndices() const
Definition KdTree:61
KdNodeList & getNodes()
Definition KdTree:145
Definition KdTree:119
value_type second
Definition KdTree:131
osg::BoundingBox bb
Definition KdTree:128
value_type first
Definition KdTree:130
KdNode(value_type f, value_type s)
Definition KdTree:124
KdNode()
Definition KdTree:120
KdTree::BuildOptions _buildOptions
Definition KdTree:206
virtual ~KdTreeBuilder()
Definition KdTree:214
void apply(Geometry &geometry)
osg::ref_ptr< osg::KdTree > _kdTreePrototype
Definition KdTree:208
KdTreeBuilder(const KdTreeBuilder &rhs)
META_NodeVisitor(osg, KdTreeBuilder) virtual KdTreeBuilder *clone()
Definition KdTree:200
Visitor for type safe operations on osg::Nodes.
Definition NodeVisitor:82
virtual Object * clone(const CopyOp &) const =0
Clone an object, with Object* return type.
Smart pointer for handling referenced counted objects.
Definition ref_ptr:32
Base class for all shape types.
Definition Shape:49
#define OSG_EXPORT
Definition Export:39

osg logo
Generated at Wed Jul 23 2025 00:00:00 for the OpenSceneGraph by doxygen 1.14.0.