/* -*-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 #include #include namespace osg { /** Implementation of a kdtree for Geometry leaves, to enable fast intersection tests.*/ 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; }; /** Build the kdtree from the specified source geometry object. * retun true on success. */ virtual bool build(BuildOptions& buildOptions, osg::Geometry* geometry); struct LineSegmentIntersection { LineSegmentIntersection(): ratio(-1.0), p0(0), p1(0), p2(0), r0(0.0f), r1(0.0f), r2(0.0f), primitiveIndex(0) {} bool operator < (const LineSegmentIntersection& rhs) const { return ratio < rhs.ratio; } typedef std::vector IndexList; typedef std::vector RatioList; double ratio; osg::Vec3d intersectionPoint; osg::Vec3 intersectionNormal; unsigned int p0; unsigned int p1; unsigned int p2; float r0; float r1; float r2; unsigned int primitiveIndex; }; typedef std::vector LineSegmentIntersections; /** compute the intersection of a line segment and the kdtree, return true if an intersection has been found.*/ virtual bool intersect(const osg::Vec3d& start, const osg::Vec3d& end, LineSegmentIntersections& intersections) const; 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; }; struct Triangle { Triangle(): p0(0),p1(0),p2(0) {} Triangle(unsigned int ip0, unsigned int ip1, unsigned int ip2): p0(ip0), p1(ip1), p2(ip2) {} bool operator < (const Triangle& rhs) const { if (p0rhs.p0) return false; if (p1rhs.p1) return false; return p2 KdNodeList; typedef std::vector< Triangle > TriangleList; int addNode(const KdNode& node) { int num = static_cast(_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; } void setVertices(osg::Vec3Array* vertices) { _vertices = vertices; } const osg::Vec3Array* getVertices() const { return _vertices.get(); } unsigned int addTriangle(const Triangle& tri) { unsigned int num = static_cast(_triangles.size()); _triangles.push_back(tri); return num; } Triangle& getTriangle(unsigned int i) { return _triangles[i]; } const Triangle& getTriangle(unsigned int i) const { return _triangles[i]; } TriangleList& getTriangles() { return _triangles; } const TriangleList& getTriangles() const { return _triangles; } protected: osg::ref_ptr _vertices; KdNodeList _kdNodes; TriangleList _triangles; }; 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(osg::Geode& geode); KdTree::BuildOptions _buildOptions; osg::ref_ptr _kdTreePrototype; protected: virtual ~KdTreeBuilder() {} }; } #endif