source: trunk/VUT/GtpVisibilityPreprocessor/src/MeshKdTree.h @ 177

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