KdTree
Go to the documentation of this file.
/* -*-c++-*- OpenSceneGraph - Copyright (C) 1998-2006 Robert Osfield
*
* This library is open source and may be redistributed and/or modified under
* the terms of the OpenSceneGraph Public License (OSGPL) version 0.0 or
* (at your option) any later version. The full license is in LICENSE file
* included with this distribution, and on the openscenegraph.org website.
*
* This library is distributed in the hope that it will be useful,
* but WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
* OpenSceneGraph Public License for more details.
*/
#ifndef OSG_KDTREE
#define OSG_KDTREE 1
#include <osg/Shape>
#include <osg/Geometry>
#include <map>
namespace osg
{
class OSG_EXPORT KdTree : public osg::Shape
{
public:
KdTree();
KdTree(const KdTree& rhs, const osg::CopyOp& copyop=osg::CopyOp::SHALLOW_COPY);
META_Shape(osg, KdTree)
struct OSG_EXPORT BuildOptions
{
BuildOptions();
unsigned int _numVerticesProcessed;
unsigned int _targetNumTrianglesPerLeaf;
unsigned int _maxNumLevels;
};
virtual bool build(BuildOptions& buildOptions, osg::Geometry* geometry);
void setVertices(osg::Vec3Array* vertices) { _vertices = vertices; }
const osg::Vec3Array* getVertices() const { return _vertices.get(); }
typedef std::vector< unsigned int > Indices;
// index in the VertexIndices vector
void setPrimitiveIndices(const Indices& indices) { _primitiveIndices = indices; }
Indices& getPrimitiveIndices() { return _primitiveIndices; }
const Indices& getPrimitiveIndices() const { return _primitiveIndices; }
// 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.
void setVertexIndices(const Indices& indices) { _vertexIndices = indices; }
Indices& getVertexIndices() { return _vertexIndices; }
const Indices& getVertexIndices() const { return _vertexIndices; }
inline unsigned int addPoint(unsigned int p0)
{
unsigned int i = _vertexIndices.size();
_vertexIndices.push_back(_primitiveIndices.size() + _degenerateCount);
_vertexIndices.push_back(1);
_vertexIndices.push_back(p0);
_primitiveIndices.push_back(i);
return i;
}
inline unsigned int addLine(unsigned int p0, unsigned int p1)
{
unsigned int i = _vertexIndices.size();
_vertexIndices.push_back(_primitiveIndices.size() + _degenerateCount);
_vertexIndices.push_back(2);
_vertexIndices.push_back(p0);
_vertexIndices.push_back(p1);
_primitiveIndices.push_back(i);
return i;
}
inline unsigned int addTriangle(unsigned int p0, unsigned int p1, unsigned int p2)
{
unsigned int i = _vertexIndices.size();
_vertexIndices.push_back(_primitiveIndices.size() + _degenerateCount);
_vertexIndices.push_back(3);
_vertexIndices.push_back(p0);
_vertexIndices.push_back(p1);
_vertexIndices.push_back(p2);
_primitiveIndices.push_back(i);
return i;
}
inline unsigned int addQuad(unsigned int p0, unsigned int p1, unsigned int p2, unsigned int p3)
{
unsigned int i = _vertexIndices.size();
_vertexIndices.push_back(_primitiveIndices.size() + _degenerateCount);
_vertexIndices.push_back(4);
_vertexIndices.push_back(p0);
_vertexIndices.push_back(p1);
_vertexIndices.push_back(p2);
_vertexIndices.push_back(p3);
_primitiveIndices.push_back(i);
return i;
}
typedef int value_type;
struct KdNode
{
KdNode():
first(0),
second(0) {}
KdNode(value_type f, value_type s):
first(f),
second(s) {}
osg::BoundingBox bb;
value_type first;
value_type second;
};
typedef std::vector< KdNode > KdNodeList;
int addNode(const KdNode& node)
{
int num = static_cast<int>(_kdNodes.size());
_kdNodes.push_back(node);
return num;
}
KdNode& getNode(int nodeNum) { return _kdNodes[nodeNum]; }
const KdNode& getNode(int nodeNum) const { return _kdNodes[nodeNum]; }
KdNodeList& getNodes() { return _kdNodes; }
const KdNodeList& getNodes() const { return _kdNodes; }
template<class IntersectFunctor>
void intersect(IntersectFunctor& functor, const KdNode& node) const
{
if (node.first<0)
{
// treat as a leaf
int istart = -node.first-1;
int iend = istart + node.second;
for(int i=istart; i<iend; ++i)
{
unsigned int primitiveIndex = _primitiveIndices[i];
unsigned int originalPIndex = _vertexIndices[primitiveIndex++];
unsigned int numVertices = _vertexIndices[primitiveIndex++];
switch(numVertices)
{
case(1): functor.intersect(_vertices.get(), originalPIndex, _vertexIndices[primitiveIndex]); break;
case(2): functor.intersect(_vertices.get(), originalPIndex, _vertexIndices[primitiveIndex], _vertexIndices[primitiveIndex+1]); break;
case(3): functor.intersect(_vertices.get(), originalPIndex, _vertexIndices[primitiveIndex], _vertexIndices[primitiveIndex+1], _vertexIndices[primitiveIndex+2]); break;
case(4): functor.intersect(_vertices.get(), originalPIndex, _vertexIndices[primitiveIndex], _vertexIndices[primitiveIndex+1], _vertexIndices[primitiveIndex+2], _vertexIndices[primitiveIndex+3]); break;
default : OSG_NOTICE<<"Warning: KdTree::intersect() encounted unsupported primitive size of "<<numVertices<<std::endl; break;
}
}
}
else if (functor.enter(node.bb))
{
if (node.first>0) intersect(functor, _kdNodes[node.first]);
if (node.second>0) intersect(functor, _kdNodes[node.second]);
functor.leave();
}
}
unsigned int _degenerateCount;
protected:
osg::ref_ptr<osg::Vec3Array> _vertices;
Indices _primitiveIndices;
Indices _vertexIndices;
KdNodeList _kdNodes;
};
class OSG_EXPORT KdTreeBuilder : public osg::NodeVisitor
{
public:
KdTreeBuilder();
KdTreeBuilder(const KdTreeBuilder& rhs);
META_NodeVisitor(osg, KdTreeBuilder)
virtual KdTreeBuilder* clone() { return new KdTreeBuilder(*this); }
void apply(Geometry& geometry);
KdTree::BuildOptions _buildOptions;
osg::ref_ptr<osg::KdTree> _kdTreePrototype;
protected:
virtual ~KdTreeBuilder() {}
};
}
#endif
Geometry
OSG_NOTICE
#define OSG_NOTICE
Definition Notify:86
Shape
osg::CopyOp
Definition CopyOp:41
osg::CopyOp::SHALLOW_COPY
@ SHALLOW_COPY
Definition CopyOp:47
osg::Geometry
Definition Geometry:31
osg::KdTreeBuilder::_buildOptions
KdTree::BuildOptions _buildOptions
Definition KdTree:206
osg::KdTreeBuilder::KdTreeBuilder
KdTreeBuilder()
osg::KdTreeBuilder::~KdTreeBuilder
virtual ~KdTreeBuilder()
Definition KdTree:214
osg::KdTreeBuilder::apply
void apply(Geometry &geometry)
osg::KdTreeBuilder::_kdTreePrototype
osg::ref_ptr< osg::KdTree > _kdTreePrototype
Definition KdTree:208
osg::KdTreeBuilder::KdTreeBuilder
KdTreeBuilder(const KdTreeBuilder &rhs)
osg::KdTreeBuilder::META_NodeVisitor
META_NodeVisitor(osg, KdTreeBuilder) virtual KdTreeBuilder *clone()
Definition KdTree:200
osg::KdTree::intersect
void intersect(IntersectFunctor &functor, const KdNode &node) const
Definition KdTree:150
osg::KdTree::addTriangle
unsigned int addTriangle(unsigned int p0, unsigned int p1, unsigned int p2)
Definition KdTree:89
osg::KdTree::getPrimitiveIndices
Indices & getPrimitiveIndices()
Definition KdTree:60
osg::KdTree::setVertexIndices
void setVertexIndices(const Indices &indices)
Definition KdTree:64
osg::KdTree::getVertexIndices
const Indices & getVertexIndices() const
Definition KdTree:66
osg::KdTree::addPoint
unsigned int addPoint(unsigned int p0)
Definition KdTree:69
osg::KdTree::getVertices
const osg::Vec3Array * getVertices() const
Definition KdTree:53
osg::KdTree::META_Shape
META_Shape(osg, KdTree) struct OSG_EXPORT BuildOptions
Definition KdTree:35
osg::KdTree::getNode
KdNode & getNode(int nodeNum)
Definition KdTree:142
osg::KdTree::addNode
int addNode(const KdNode &node)
Definition KdTree:135
osg::KdTree::addLine
unsigned int addLine(unsigned int p0, unsigned int p1)
Definition KdTree:78
osg::KdTree::_primitiveIndices
Indices _primitiveIndices
Definition KdTree:187
osg::KdTree::_vertexIndices
Indices _vertexIndices
Definition KdTree:188
osg::KdTree::getNodes
const KdNodeList & getNodes() const
Definition KdTree:146
osg::KdTree::value_type
int value_type
Definition KdTree:116
osg::KdTree::Indices
std::vector< unsigned int > Indices
Definition KdTree:56
osg::KdTree::_degenerateCount
unsigned int _degenerateCount
Definition KdTree:182
osg::KdTree::_kdNodes
KdNodeList _kdNodes
Definition KdTree:189
osg::KdTree::KdNodeList
std::vector< KdNode > KdNodeList
Definition KdTree:133
osg::KdTree::getVertexIndices
Indices & getVertexIndices()
Definition KdTree:65
osg::KdTree::setVertices
void setVertices(osg::Vec3Array *vertices)
Definition KdTree:52
osg::KdTree::_vertices
osg::ref_ptr< osg::Vec3Array > _vertices
Definition KdTree:186
osg::KdTree::getNode
const KdNode & getNode(int nodeNum) const
Definition KdTree:143
osg::KdTree::KdTree
KdTree(const KdTree &rhs, const osg::CopyOp &copyop=osg::CopyOp::SHALLOW_COPY)
osg::KdTree::build
virtual bool build(BuildOptions &buildOptions, osg::Geometry *geometry)
osg::KdTree::setPrimitiveIndices
void setPrimitiveIndices(const Indices &indices)
Definition KdTree:59
osg::KdTree::addQuad
unsigned int addQuad(unsigned int p0, unsigned int p1, unsigned int p2, unsigned int p3)
Definition KdTree:101
osg::KdTree::getPrimitiveIndices
const Indices & getPrimitiveIndices() const
Definition KdTree:61
osg::KdTree::getNodes
KdNodeList & getNodes()
Definition KdTree:145
osg::KdTree::KdTree
KdTree()
osg::NodeVisitor
Definition NodeVisitor:82
osg::Object::clone
virtual Object * clone(const CopyOp &) const =0
osg::Shape
Definition Shape:49
osg::ref_ptr
Definition ref_ptr:32
osg
Definition AlphaFunc:19
osg::Vec3Array
TemplateArray< Vec3, Array::Vec3ArrayType, 3, GL_FLOAT > Vec3Array
Definition Array:449
osg::BoundingBox
BoundingBoxd BoundingBox
Definition BoundingBox:257
OSG_EXPORT
#define OSG_EXPORT
Definition osg/Export:39
osg::KdTree::KdNode
Definition KdTree:119
osg::KdTree::KdNode::second
value_type second
Definition KdTree:131
osg::KdTree::KdNode::bb
osg::BoundingBox bb
Definition KdTree:128
osg::KdTree::KdNode::first
value_type first
Definition KdTree:130
osg::KdTree::KdNode::KdNode
KdNode(value_type f, value_type s)
Definition KdTree:124
osg::KdTree::KdNode::KdNode
KdNode()
Definition KdTree:120