| | 37 | class KDNode |
| | 38 | { |
| | 39 | public: |
| | 40 | |
| | 41 | typedef short value_type; |
| | 42 | |
| | 43 | value_type _leftChild; |
| | 44 | value_type _rightChild; |
| | 45 | }; |
| | 46 | |
| | 47 | class 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 | |
| | 63 | class 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 | |
| | 78 | class 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 | }; |
