Show
Ignore:
Timestamp:
06/03/08 19:29:27 (7 years ago)
Author:
robert
Message:

Fleshed out some basic kd-tree data structures.

Files:
1 modified

Legend:

Unmodified
Added
Removed
  • OpenSceneGraph/trunk/examples/osgkdtree/osgkdtree.cpp

    r8404 r8405  
    3535#include <iostream> 
    3636 
     37class KDNode 
     38{ 
     39    public: 
     40     
     41        typedef short value_type; 
     42 
     43        value_type _leftChild; 
     44        value_type _rightChild; 
     45}; 
     46 
     47class KDLeaf : public osg::Referenced 
     48{ 
     49    public: 
     50     
     51        KDLeaf(); 
     52     
     53        typedef unsigned int index_type; 
     54        typedef std::vector< index_type > Indices; 
     55 
     56        Indices _vertexIndices;         
     57     
     58    protected: 
     59     
     60        virtual ~KDLeaf() {} 
     61}; 
     62 
     63class KDTree : public osg::Referenced 
     64{ 
     65    public: 
     66     
     67        typedef std::vector< unsigned int > AxisStack; 
     68        typedef std::vector< KDNode > KDNodeList; 
     69        typedef std::vector< osg::ref_ptr<KDLeaf> > KDLeafList; 
     70 
     71        osg::BoundingBox    _bb; 
     72 
     73        AxisStack           _axisStack; 
     74        KDNodeList          _kdNodes; 
     75        KDLeafList          _kdLeaves;  
     76}; 
     77 
     78class KDTreeTraverser 
     79{ 
     80    public: 
     81     
     82        void traverse(KDTree& tree, KDNode::value_type nodeIndex) 
     83        { 
     84            if (nodeIndex>=0) 
     85            {         
     86                KDNode& node = tree._kdNodes[nodeIndex]; 
     87                traverse(tree,node._leftChild); 
     88                traverse(tree,node._rightChild); 
     89            } 
     90            else  
     91            { 
     92                KDNode::value_type leafIndex = -nodeIndex-1; 
     93                KDLeaf& leaf = *(tree._kdLeaves[leafIndex]); 
     94            } 
     95        } 
     96 
     97 
     98        void traverse(KDTree& tree) 
     99        { 
     100            if (!tree._kdNodes.empty()) traverse(tree,0); 
     101        } 
     102     
     103}; 
    37104 
    38105int main(int argc, char **argv)