source: GTP/trunk/Lib/Vis/Preprocessing/src/MeshKdTree.h @ 2176

Revision 2176, 5.3 KB checked in by mattausch, 18 years ago (diff)

removed using namespace std from .h

RevLine 
[177]1#ifndef _MeshKdTree_H__
2#define _MeshKdTree_H__
3
4#include <functional>
[2176]5//
[177]6
7#include "Containers.h"
8#include "AxisAlignedBox3.h"
9#include "Ray.h"
10
[860]11namespace GtpVisibilityPreprocessor {
12
[177]13class MeshKdNode;
14class MeshKdLeaf;
15class MeshKdInterior;
16 
17/** Abstract class for kd-tree node */
18class MeshKdNode {
19public:
20  MeshKdNode() {}
21 
22  /** Determines whether this node is a leaf or interior node
23      @return true if leaf
24  */
25  virtual bool IsLeaf() const = 0;
26  virtual ~MeshKdNode() {}
27};
28
29/** Implementation of the kd-tree interior node */
30class MeshKdInterior : public MeshKdNode {
31 
32public:
33  MeshKdInterior():MeshKdNode(),
34                   mBack(NULL), mFront(NULL) {}
35 
36  /** \sa KdNode::IsLeaf() */
37  virtual bool IsLeaf() const { return false; }
38
39  /** splitting axis */
40  int mAxis;
41  /** splitting position, absolute position within the bounding box of this node */
42  float mPosition;
43 
44  /** back node */
45  MeshKdNode *mBack;
46  /** front node */
47  MeshKdNode *mFront;
48
49  void SetupChildLinks(MeshKdNode *b, MeshKdNode *f) {
50    mBack = b;
51    mFront = f;
52  }
53 
54  void ReplaceChildLink(MeshKdNode *oldChild, MeshKdNode *newChild) {
55    if (mBack == oldChild)
56      mBack = newChild;
57    else
58      mFront = newChild;
59  }
60 
61  ~MeshKdInterior() {
62    delete mBack;
63    delete mFront;
64  }
65};
66 
67 
68/** Implementation of the kd-tree leaf node */
69class MeshKdLeaf : public MeshKdNode {
70public:
71  MeshKdLeaf():MeshKdNode() {
72  }
73
74  MeshKdLeaf(const vector<int> &faces):MeshKdNode() {
75    mFaces = faces;
76  }
77 
78  /** \sa KdNode::IsLeaf() */
79  virtual bool IsLeaf() const { return true; }
80 
81  /** indices of contained faces */
82  vector<int> mFaces;
83 
84};
85
86
87
88/** KdTree for indexing scene entities - occluders/occludees/viewcells */
89class MeshKdTree {
90 
91protected:
92  struct TraversalData
93  { 
94    MeshKdNode *mNode;
95    MeshKdInterior *mParent;
96    AxisAlignedBox3 mBox;
97    int mDepth;
98    float mPriority;
99   
100    TraversalData() {}
101   
102    TraversalData(MeshKdNode *n, const float p):
103      mNode(n), mPriority(p)
104    {}
105   
106    TraversalData(MeshKdNode *n,
107                  MeshKdInterior *p,
108                  const AxisAlignedBox3 &b,
109                  const int d):
110      mNode(n), mParent(p), mBox(b), mDepth(d) {}
111   
112   
113    bool operator<(
114                   const TraversalData &b) const {
115      MeshKdLeaf *leafa = (MeshKdLeaf *) mNode;
116      MeshKdLeaf *leafb = (MeshKdLeaf *) b.mNode;
117      return
118        leafa->mFaces.size()*mBox.SurfaceArea()
119        <
120        leafb->mFaces.size()*b.mBox.SurfaceArea();
121    }
122   
123  };
124
125 
126
127public:
128
[1486]129  enum {
130          SPLIT_OBJECT_MEDIAN,
131          SPLIT_SPATIAL_MEDIAN,
132          SPLIT_SAH};
[177]133 
134
135  MeshKdTree(Mesh *mesh);
[1486]136  ~MeshKdTree();
[177]137 
138  virtual bool Construct();
139
140  /** Check whether subdivision criteria are met for the given subtree.
141      If not subdivide the leafs of the subtree. The criteria are specified in
142      the environment as well as the subdivision method. By default surface area
143      heuristics is used.
144       
145      @param subtree root of the subtree
146
147      @return true if subdivision was performed, false if subdivision criteria
148      were already met
149  */
150  virtual MeshKdNode *Subdivide(const TraversalData &tdata);
151 
[1486]152  /** Get the root of the tree
153  */
154  MeshKdNode *GetRoot() const;
[177]155 
[1486]156  AxisAlignedBox3 GetBox() const;
[177]157
158  int
159  CastRay(
160          Ray &ray,
161          MeshInstance *instance
162          );
163
164
165protected:
166 
167  struct RayTraversalData {
168    MeshKdNode *mNode;
169    Vector3 mExitPoint;
170    float mMaxT;
171   
172    RayTraversalData() {}
173    RayTraversalData(MeshKdNode *n,
174                     const Vector3 &p,
175                     const float maxt):
176      mNode(n), mExitPoint(p), mMaxT(maxt) {}
177  };
178
179  // --------------------------------------------------------------
180  // For sorting objects
181  // --------------------------------------------------------------
182  struct  SortableEntry
183  {
184    enum {
185      FACE_MIN,
186      FACE_MAX
187    };
188   
189    int type;
190    float value;
191    int face;
192   
193    SortableEntry() {}
194    SortableEntry(const int t, const float v, const int f):type(t),
195                                                           value(v),
196                                                           face(f) {}
197   
198    bool operator<(const SortableEntry &b) const {
199      return value < b.value;
200    }
201   
202  };
203 
204
205  float
206  BestCostRatio(
207                MeshKdLeaf *node,
208                const AxisAlignedBox3 &box,
209                const int axis,
210                float &position,
211                int &objectsBack,
212                int &objectsFront
213                );
214
215  void
[1233]216  SortSubdivisionCandidates(
[177]217                      MeshKdLeaf *node,
218                      const int axis
219                      );
220
221  MeshKdNode *
222  SubdivideNode(
223                MeshKdLeaf *leaf,
224                MeshKdInterior *parent,
225                const AxisAlignedBox3 &box,
226                const int depth,
227                AxisAlignedBox3 &backBBox,
228                AxisAlignedBox3 &frontBBox
229                );
230
231  bool
232  TerminationCriteriaMet(const MeshKdLeaf *leaf, const int depth);
233 
234  int
235  SelectPlane(MeshKdLeaf *leaf,
236              const AxisAlignedBox3 &box,
237              float &position
238              );
239
240  /// pointer to the mesh owning the tree
241  Mesh *mMesh;
242 
243  /// root of the tree
244  MeshKdNode *mRoot;
245 
246  /// reusable array of split candidates
[1233]247  vector<SortableEntry> *mSubdivisionCandidates;
[177]248
249public:
250  static void ParseEnvironment();
251  static float mSplitBorder;
252  static int mTermMaxDepth;
253  static int mTermMinCost;
254  static float mMaxCostRatio;
255  static float mCt_div_ci;
256  static int mSplitMethod;
257
258};
259 
260
261
[860]262}
[177]263
264
265#endif
Note: See TracBrowser for help on using the repository browser.