1/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
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.
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.
18#include <osg/Geometry>
25/** Implementation of a kdtree for Geometry leaves, to enable fast intersection tests.*/
26class OSG_EXPORT KdTree : public osg::Shape
33 KdTree(const KdTree& rhs, const osg::CopyOp& copyop=osg::CopyOp::SHALLOW_COPY);
35 META_Shape(osg, KdTree)
37 struct OSG_EXPORT BuildOptions
41 unsigned int _numVerticesProcessed;
42 unsigned int _targetNumTrianglesPerLeaf;
43 unsigned int _maxNumLevels;
47 /** Build the kdtree from the specified source geometry object.
48 * retun true on success. */
49 virtual bool build(BuildOptions& buildOptions, osg::Geometry* geometry);
52 void setVertices(osg::Vec3Array* vertices) { _vertices = vertices; }
53 const osg::Vec3Array* getVertices() const { return _vertices.get(); }
56 typedef std::vector< unsigned int > Indices;
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; }
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; }
69 inline unsigned int addPoint(unsigned int p0)
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);
78 inline unsigned int addLine(unsigned int p0, unsigned int p1)
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);
89 inline unsigned int addTriangle(unsigned int p0, unsigned int p1, unsigned int p2)
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);
101 inline unsigned int addQuad(unsigned int p0, unsigned int p1, unsigned int p2, unsigned int p3)
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);
116 typedef int value_type;
124 KdNode(value_type f, value_type s):
133 typedef std::vector< KdNode > KdNodeList;
135 int addNode(const KdNode& node)
137 int num = static_cast<int>(_kdNodes.size());
138 _kdNodes.push_back(node);
142 KdNode& getNode(int nodeNum) { return _kdNodes[nodeNum]; }
143 const KdNode& getNode(int nodeNum) const { return _kdNodes[nodeNum]; }
145 KdNodeList& getNodes() { return _kdNodes; }
146 const KdNodeList& getNodes() const { return _kdNodes; }
149 template<class IntersectFunctor>
150 void intersect(IntersectFunctor& functor, const KdNode& node) const
155 int istart = -node.first-1;
156 int iend = istart + node.second;
158 for(int i=istart; i<iend; ++i)
160 unsigned int primitiveIndex = _primitiveIndices[i];
161 unsigned int originalPIndex = _vertexIndices[primitiveIndex++];
162 unsigned int numVertices = _vertexIndices[primitiveIndex++];
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;
173 else if (functor.enter(node.bb))
175 if (node.first>0) intersect(functor, _kdNodes[node.first]);
176 if (node.second>0) intersect(functor, _kdNodes[node.second]);
182 unsigned int _degenerateCount;
186 osg::ref_ptr<osg::Vec3Array> _vertices;
187 Indices _primitiveIndices;
188 Indices _vertexIndices;
192class OSG_EXPORT KdTreeBuilder : public osg::NodeVisitor
198 KdTreeBuilder(const KdTreeBuilder& rhs);
200 META_NodeVisitor(osg, KdTreeBuilder)
202 virtual KdTreeBuilder* clone() { return new KdTreeBuilder(*this); }
204 void apply(Geometry& geometry);
206 KdTree::BuildOptions _buildOptions;
208 osg::ref_ptr<osg::KdTree> _kdTreePrototype;
214 virtual ~KdTreeBuilder() {}