1 | #ifndef _TraversalTree_H__
|
---|
2 | #define _TraversalTree_H__
|
---|
3 |
|
---|
4 | #include <functional>
|
---|
5 | using namespace std;
|
---|
6 |
|
---|
7 | #include "Containers.h"
|
---|
8 | #include "AxisAlignedBox3.h"
|
---|
9 | #include "Ray.h"
|
---|
10 | //#include "ObjectPvs.h"
|
---|
11 | //#include "Viewcell.h"
|
---|
12 | //#include "VssRay.h"
|
---|
13 | //#include "IntersectableWrapper.h"
|
---|
14 |
|
---|
15 |
|
---|
16 | namespace GtpVisibilityPreprocessor {
|
---|
17 |
|
---|
18 |
|
---|
19 | class TraversalNode;
|
---|
20 | class TraversalLeaf;
|
---|
21 | class TraversalInterior;
|
---|
22 | class Intersectable;
|
---|
23 | class Beam;
|
---|
24 |
|
---|
25 | class TraversalTree;
|
---|
26 |
|
---|
27 | // TraversalTree *SceneTraversalTree;
|
---|
28 |
|
---|
29 | // --------------------------------------------------------------
|
---|
30 | // Static statistics for kd-tree search
|
---|
31 | // --------------------------------------------------------------
|
---|
32 | class TraversalTreeStatistics
|
---|
33 | {
|
---|
34 | public:
|
---|
35 | // total number of nodes
|
---|
36 | int nodes;
|
---|
37 | // number of splits along each of the axes
|
---|
38 | int splits[7];
|
---|
39 | // totals number of rays
|
---|
40 | int rays;
|
---|
41 | // total number of query domains
|
---|
42 | int queryDomains;
|
---|
43 | // total number of ray references
|
---|
44 | int rayRefs;
|
---|
45 | // refs in non empty leafs
|
---|
46 | int rayRefsNonZeroQuery;
|
---|
47 | // total number of query references
|
---|
48 | int objectRefs;
|
---|
49 | // nodes with zero queries
|
---|
50 | int zeroQueryNodes;
|
---|
51 | // max depth nodes
|
---|
52 | int maxDepthNodes;
|
---|
53 | // max depth nodes
|
---|
54 | int minCostNodes;
|
---|
55 | // max number of rays per node
|
---|
56 | int maxObjectRefs;
|
---|
57 | // number of dynamically added ray refs
|
---|
58 | int addedRayRefs;
|
---|
59 | // number of dynamically removed ray refs
|
---|
60 | int removedRayRefs;
|
---|
61 |
|
---|
62 | // Constructor
|
---|
63 | TraversalTreeStatistics()
|
---|
64 | {
|
---|
65 | Reset();
|
---|
66 | }
|
---|
67 |
|
---|
68 | int Nodes() const {return nodes;}
|
---|
69 | int Interior() const { return nodes / 2; }
|
---|
70 | int Leaves() const { return (nodes / 2) + 1; }
|
---|
71 |
|
---|
72 | void Reset()
|
---|
73 | {
|
---|
74 | nodes = 0;
|
---|
75 |
|
---|
76 | for (int i=0; i<7; i++)
|
---|
77 | splits[i] = 0;
|
---|
78 |
|
---|
79 | rays = queryDomains = 0;
|
---|
80 | rayRefs = rayRefsNonZeroQuery = objectRefs = 0;
|
---|
81 | zeroQueryNodes = 0;
|
---|
82 | maxDepthNodes = 0;
|
---|
83 | minCostNodes = 0;
|
---|
84 | maxObjectRefs = 0;
|
---|
85 | addedRayRefs = removedRayRefs = 0;
|
---|
86 | }
|
---|
87 |
|
---|
88 | void Print(ostream &app) const;
|
---|
89 |
|
---|
90 | friend ostream &operator<<(ostream &s, const TraversalTreeStatistics &stat)
|
---|
91 | {
|
---|
92 | stat.Print(s);
|
---|
93 | return s;
|
---|
94 | }
|
---|
95 |
|
---|
96 | };
|
---|
97 |
|
---|
98 |
|
---|
99 | class TraversalInterior;
|
---|
100 |
|
---|
101 | /** Abstract class for kd-tree node
|
---|
102 | */
|
---|
103 | class TraversalNode
|
---|
104 | {
|
---|
105 | public:
|
---|
106 |
|
---|
107 | virtual ~TraversalNode(){};
|
---|
108 |
|
---|
109 | TraversalNode(TraversalInterior *parent);
|
---|
110 | /** Determines whether this node is a leaf or interior node
|
---|
111 | @return true if leaf
|
---|
112 | */
|
---|
113 | virtual bool IsLeaf() const = 0;
|
---|
114 |
|
---|
115 | /** Determines whether this node is the root of the tree
|
---|
116 | @return true if root
|
---|
117 | */
|
---|
118 | virtual bool IsRoot() const
|
---|
119 | {
|
---|
120 | return mParent == NULL;
|
---|
121 | }
|
---|
122 |
|
---|
123 | /** Parent of the node - the parent is a little overhead for maintanance of the tree,
|
---|
124 | but allows various optimizations of tree traversal algorithms
|
---|
125 | */
|
---|
126 | TraversalInterior *mParent;
|
---|
127 |
|
---|
128 |
|
---|
129 | ///////////////////
|
---|
130 | // mailing stuff
|
---|
131 |
|
---|
132 | public:
|
---|
133 |
|
---|
134 | void Mail()
|
---|
135 | {
|
---|
136 | mMailbox = sMailId;
|
---|
137 | }
|
---|
138 |
|
---|
139 | bool Mailed() const
|
---|
140 | {
|
---|
141 | return mMailbox == sMailId;
|
---|
142 | }
|
---|
143 |
|
---|
144 | static void NewMail(const int reserve = 1)
|
---|
145 | {
|
---|
146 | sMailId += sReservedMailboxes;
|
---|
147 | sReservedMailboxes = reserve;
|
---|
148 | }
|
---|
149 |
|
---|
150 | void Mail(const int mailbox)
|
---|
151 | {
|
---|
152 | mMailbox = sMailId + mailbox;
|
---|
153 | }
|
---|
154 |
|
---|
155 |
|
---|
156 | bool Mailed(const int mailbox) const
|
---|
157 | {
|
---|
158 | return mMailbox == sMailId + mailbox;
|
---|
159 | }
|
---|
160 |
|
---|
161 | int mMailbox;
|
---|
162 |
|
---|
163 | static int sMailId;
|
---|
164 | static int sReservedMailboxes;
|
---|
165 | };
|
---|
166 |
|
---|
167 |
|
---|
168 | /** Implementation of the kd-tree interior node
|
---|
169 | */
|
---|
170 | class TraversalInterior : public TraversalNode
|
---|
171 | {
|
---|
172 | public:
|
---|
173 |
|
---|
174 | TraversalInterior(TraversalInterior *parent);
|
---|
175 | ~TraversalInterior();
|
---|
176 |
|
---|
177 | /** \sa TraversalNode::IsLeaf()
|
---|
178 | */
|
---|
179 | bool IsLeaf() const;
|
---|
180 |
|
---|
181 | void SetupChildLinks(TraversalNode *b, TraversalNode *f);
|
---|
182 |
|
---|
183 | void ReplaceChildLink(TraversalNode *oldChild, TraversalNode *newChild);
|
---|
184 |
|
---|
185 |
|
---|
186 | //////////////////////////
|
---|
187 |
|
---|
188 | /// splitting axis
|
---|
189 | int mAxis;
|
---|
190 | /// splitting position, absolute position within the bounding box of this node.
|
---|
191 | float mPosition;
|
---|
192 | /// bounding box of interior node
|
---|
193 | AxisAlignedBox3 mBox;
|
---|
194 |
|
---|
195 | /// back node
|
---|
196 | TraversalNode *mBack;
|
---|
197 | /// front node
|
---|
198 | TraversalNode *mFront;
|
---|
199 | };
|
---|
200 |
|
---|
201 |
|
---|
202 | /** Implementation of the kd-tree leaf node
|
---|
203 | */
|
---|
204 | class TraversalLeaf : public TraversalNode
|
---|
205 | {
|
---|
206 | public:
|
---|
207 |
|
---|
208 | TraversalLeaf(TraversalInterior *parent, const int objects);
|
---|
209 |
|
---|
210 | ~TraversalLeaf();
|
---|
211 |
|
---|
212 | /** \sa TraversalNode::IsLeaf()
|
---|
213 | */
|
---|
214 | virtual bool IsLeaf() const;
|
---|
215 |
|
---|
216 | /////////////////////////////////
|
---|
217 |
|
---|
218 | // pointers to view cells contained in this node
|
---|
219 | ObjectContainer mObjects;
|
---|
220 |
|
---|
221 | short mDepth;
|
---|
222 | };
|
---|
223 |
|
---|
224 |
|
---|
225 | /** TraversalTree for indexing scene entities - occluders/occludees/viewcells
|
---|
226 | */
|
---|
227 | class TraversalTree
|
---|
228 | {
|
---|
229 |
|
---|
230 | protected:
|
---|
231 |
|
---|
232 | struct TraversalData
|
---|
233 | {
|
---|
234 | TraversalNode *mNode;
|
---|
235 | AxisAlignedBox3 mBox;
|
---|
236 | int mDepth;
|
---|
237 | float mPriority;
|
---|
238 |
|
---|
239 | TraversalData() {}
|
---|
240 |
|
---|
241 | TraversalData(TraversalNode *n, const float p):
|
---|
242 | mNode(n), mPriority(p)
|
---|
243 | {}
|
---|
244 |
|
---|
245 | TraversalData(TraversalNode *n,
|
---|
246 | const AxisAlignedBox3 &b,
|
---|
247 | const int d):
|
---|
248 | mNode(n), mBox(b), mDepth(d) {}
|
---|
249 |
|
---|
250 |
|
---|
251 | bool operator<(const TraversalData &b) const
|
---|
252 | {
|
---|
253 | TraversalLeaf *leafa = (TraversalLeaf *) mNode;
|
---|
254 | TraversalLeaf *leafb = (TraversalLeaf *) b.mNode;
|
---|
255 |
|
---|
256 | return
|
---|
257 | leafa->mObjects.size() * mBox.SurfaceArea()
|
---|
258 | <
|
---|
259 | leafb->mObjects.size() * b.mBox.SurfaceArea();
|
---|
260 | }
|
---|
261 |
|
---|
262 |
|
---|
263 | // comparator for the
|
---|
264 | struct less_priority: public
|
---|
265 | binary_function<const TraversalData, const TraversalData, bool>
|
---|
266 | {
|
---|
267 | bool operator()(const TraversalData a, const TraversalData b)
|
---|
268 | {
|
---|
269 | return a.mPriority < b.mPriority;
|
---|
270 | }
|
---|
271 | };
|
---|
272 | };
|
---|
273 |
|
---|
274 |
|
---|
275 | public:
|
---|
276 |
|
---|
277 | enum {SPLIT_OBJECT_MEDIAN,
|
---|
278 | SPLIT_SPATIAL_MEDIAN,
|
---|
279 | SPLIT_SAH};
|
---|
280 |
|
---|
281 | TraversalTree();
|
---|
282 |
|
---|
283 | ~TraversalTree();
|
---|
284 |
|
---|
285 |
|
---|
286 | /** Casts line segment into tree.
|
---|
287 | @returns intersected view cells.
|
---|
288 | */
|
---|
289 | int CastLineSegment(const Vector3 &origin,
|
---|
290 | const Vector3 &termination,
|
---|
291 | ViewCellContainer &viewcells,
|
---|
292 | const bool useMailboxing);
|
---|
293 |
|
---|
294 | virtual bool Construct();
|
---|
295 |
|
---|
296 | /** Check whether subdivision criteria are met for the given subtree.
|
---|
297 | If not subdivide the leafs of the subtree. The criteria are specified in
|
---|
298 | the environment as well as the subdivision method. By default surface area
|
---|
299 | heuristics is used.
|
---|
300 |
|
---|
301 | @param subtree root of the subtree
|
---|
302 |
|
---|
303 | @return true if subdivision was performed, false if subdivision criteria
|
---|
304 | were already met
|
---|
305 | */
|
---|
306 | virtual TraversalNode *Subdivide(const TraversalData &tdata);
|
---|
307 |
|
---|
308 | /** Get the root of the tree
|
---|
309 | */
|
---|
310 | TraversalNode *GetRoot() const
|
---|
311 | {
|
---|
312 | return mRoot;
|
---|
313 | }
|
---|
314 |
|
---|
315 | AxisAlignedBox3 GetBox() const
|
---|
316 | {
|
---|
317 | return mBox;
|
---|
318 | }
|
---|
319 |
|
---|
320 | const TraversalTreeStatistics &GetStatistics() const
|
---|
321 | {
|
---|
322 | return mStat;
|
---|
323 | }
|
---|
324 |
|
---|
325 | void CollectObjects(TraversalNode *n, ObjectContainer &objects);
|
---|
326 |
|
---|
327 | void CollectObjects(const AxisAlignedBox3 &box, ObjectContainer &objects);
|
---|
328 |
|
---|
329 | void CollectLeaves(vector<TraversalLeaf *> &leaves);
|
---|
330 |
|
---|
331 | float GetSurfaceArea(const TraversalNode *node) const
|
---|
332 | {
|
---|
333 | return GetBox(node).SurfaceArea();
|
---|
334 | }
|
---|
335 |
|
---|
336 | AxisAlignedBox3 GetBox(const TraversalNode *node) const;
|
---|
337 |
|
---|
338 |
|
---|
339 | protected:
|
---|
340 |
|
---|
341 | /** Struct for traversing line segment.
|
---|
342 | */
|
---|
343 | struct LineTraversalData
|
---|
344 | {
|
---|
345 | LineTraversalData () {}
|
---|
346 | LineTraversalData (TraversalNode *n, const Vector3 &p, const float maxt):
|
---|
347 | mNode(n), mExitPoint(p), mMaxT(maxt) {}
|
---|
348 |
|
---|
349 | TraversalNode *mNode;
|
---|
350 | Vector3 mExitPoint;
|
---|
351 | float mMaxT;
|
---|
352 | };
|
---|
353 |
|
---|
354 | // --------------------------------------------------------------
|
---|
355 | // For sorting objects
|
---|
356 | // --------------------------------------------------------------
|
---|
357 | struct SortableEntry
|
---|
358 | {
|
---|
359 | enum
|
---|
360 | {
|
---|
361 | BOX_MIN,
|
---|
362 | BOX_MAX
|
---|
363 | };
|
---|
364 |
|
---|
365 | int type;
|
---|
366 | float value;
|
---|
367 | Intersectable *intersectable;
|
---|
368 |
|
---|
369 | SortableEntry() {}
|
---|
370 | SortableEntry(const int t, const float v, Intersectable *i):
|
---|
371 | type(t), value(v), intersectable(i)
|
---|
372 | {}
|
---|
373 |
|
---|
374 | bool operator<(const SortableEntry &b) const
|
---|
375 | {
|
---|
376 | return value < b.value;
|
---|
377 | }
|
---|
378 | };
|
---|
379 |
|
---|
380 | inline static bool iltS(SortableEntry *a, SortableEntry *b)
|
---|
381 | {
|
---|
382 | return a->value < b->value;
|
---|
383 | }
|
---|
384 |
|
---|
385 | // reusable array of split candidates
|
---|
386 | vector<SortableEntry *> *splitCandidates;
|
---|
387 |
|
---|
388 | float BestCostRatio(TraversalLeaf *node,
|
---|
389 | const AxisAlignedBox3 &box,
|
---|
390 | const int axis,
|
---|
391 | float &position,
|
---|
392 | int &objectsBack,
|
---|
393 | int &objectsFront);
|
---|
394 |
|
---|
395 | void SortSubdivisionCandidates(TraversalLeaf *node, const int axis);
|
---|
396 |
|
---|
397 | void EvaluateLeafStats(const TraversalData &data);
|
---|
398 |
|
---|
399 | TraversalNode *SubdivideNode(TraversalLeaf *leaf,
|
---|
400 | const AxisAlignedBox3 &box,
|
---|
401 | AxisAlignedBox3 &backBBox,
|
---|
402 | AxisAlignedBox3 &frontBBox
|
---|
403 | );
|
---|
404 |
|
---|
405 | bool TerminationCriteriaMet(const TraversalLeaf *leaf);
|
---|
406 |
|
---|
407 | int SelectPlane(TraversalLeaf *leaf,
|
---|
408 | const AxisAlignedBox3 &box,
|
---|
409 | float &position);
|
---|
410 |
|
---|
411 |
|
---|
412 | ////////////////////////
|
---|
413 |
|
---|
414 | int mTermMaxNodes;
|
---|
415 | float mSplitBorder;
|
---|
416 | int mTermMaxDepth;
|
---|
417 | int mTermMinCost;
|
---|
418 | float mMaxCostRatio;
|
---|
419 | float mCt_div_ci;
|
---|
420 | int mSplitMethod;
|
---|
421 | bool mSahUseFaces;
|
---|
422 |
|
---|
423 | /// root of the tree
|
---|
424 | TraversalNode *mRoot;
|
---|
425 | /// bounding box of the tree root
|
---|
426 | AxisAlignedBox3 mBox;
|
---|
427 | TraversalTreeStatistics mStat;
|
---|
428 |
|
---|
429 | };
|
---|
430 |
|
---|
431 |
|
---|
432 | }
|
---|
433 |
|
---|
434 | #endif
|
---|