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

Revision 860, 5.4 KB checked in by mattausch, 19 years ago (diff)
Line 
1#ifndef _MeshKdTree_H__
2#define _MeshKdTree_H__
3
4#include <functional>
5using namespace std;
6
7#include "Containers.h"
8#include "AxisAlignedBox3.h"
9#include "Ray.h"
10
11namespace GtpVisibilityPreprocessor {
12
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
129  enum {SPLIT_OBJECT_MEDIAN,
130        SPLIT_SPATIAL_MEDIAN,
131        SPLIT_SAH};
132 
133
134  MeshKdTree(Mesh *mesh);
135  ~MeshKdTree() {
136    if (mSplitCandidates)
137      delete mSplitCandidates;
138   
139    if (mRoot)
140      delete mRoot;
141  }
142 
143  virtual bool Construct();
144
145  /** Check whether subdivision criteria are met for the given subtree.
146      If not subdivide the leafs of the subtree. The criteria are specified in
147      the environment as well as the subdivision method. By default surface area
148      heuristics is used.
149       
150      @param subtree root of the subtree
151
152      @return true if subdivision was performed, false if subdivision criteria
153      were already met
154  */
155  virtual MeshKdNode *Subdivide(const TraversalData &tdata);
156 
157  /** Get the root of the tree */
158  MeshKdNode *GetRoot() const {
159    return mRoot;
160  }
161 
162  AxisAlignedBox3 GetBox() const { return mMesh->mBox; }
163
164  int
165  CastRay(
166          Ray &ray,
167          MeshInstance *instance
168          );
169
170
171protected:
172 
173  struct RayTraversalData {
174    MeshKdNode *mNode;
175    Vector3 mExitPoint;
176    float mMaxT;
177   
178    RayTraversalData() {}
179    RayTraversalData(MeshKdNode *n,
180                     const Vector3 &p,
181                     const float maxt):
182      mNode(n), mExitPoint(p), mMaxT(maxt) {}
183  };
184
185  // --------------------------------------------------------------
186  // For sorting objects
187  // --------------------------------------------------------------
188  struct  SortableEntry
189  {
190    enum {
191      FACE_MIN,
192      FACE_MAX
193    };
194   
195    int type;
196    float value;
197    int face;
198   
199    SortableEntry() {}
200    SortableEntry(const int t, const float v, const int f):type(t),
201                                                           value(v),
202                                                           face(f) {}
203   
204    bool operator<(const SortableEntry &b) const {
205      return value < b.value;
206    }
207   
208  };
209 
210
211  float
212  BestCostRatio(
213                MeshKdLeaf *node,
214                const AxisAlignedBox3 &box,
215                const int axis,
216                float &position,
217                int &objectsBack,
218                int &objectsFront
219                );
220
221  void
222  SortSplitCandidates(
223                      MeshKdLeaf *node,
224                      const int axis
225                      );
226
227  MeshKdNode *
228  SubdivideNode(
229                MeshKdLeaf *leaf,
230                MeshKdInterior *parent,
231                const AxisAlignedBox3 &box,
232                const int depth,
233                AxisAlignedBox3 &backBBox,
234                AxisAlignedBox3 &frontBBox
235                );
236
237  bool
238  TerminationCriteriaMet(const MeshKdLeaf *leaf, const int depth);
239 
240  int
241  SelectPlane(MeshKdLeaf *leaf,
242              const AxisAlignedBox3 &box,
243              float &position
244              );
245
246  /// pointer to the mesh owning the tree
247  Mesh *mMesh;
248 
249  /// root of the tree
250  MeshKdNode *mRoot;
251 
252  /// reusable array of split candidates
253  vector<SortableEntry> *mSplitCandidates;
254
255public:
256  static void ParseEnvironment();
257  static float mSplitBorder;
258  static int mTermMaxDepth;
259  static int mTermMinCost;
260  static float mMaxCostRatio;
261  static float mCt_div_ci;
262  static int mSplitMethod;
263
264};
265 
266
267
268}
269
270
271#endif
Note: See TracBrowser for help on using the repository browser.