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 |
|
---|
11 |
|
---|
12 | namespace GtpVisibilityPreprocessor {
|
---|
13 |
|
---|
14 |
|
---|
15 | class TraversalNode;
|
---|
16 | class TraversalLeaf;
|
---|
17 | class TraversalInterior;
|
---|
18 | class Intersectable;
|
---|
19 | class Beam;
|
---|
20 |
|
---|
21 | class TraversalTree;
|
---|
22 |
|
---|
23 |
|
---|
24 | // --------------------------------------------------------------
|
---|
25 | // Static statistics for kd-tree search
|
---|
26 | // --------------------------------------------------------------
|
---|
27 | class TraversalTreeStatistics
|
---|
28 | {
|
---|
29 | public:
|
---|
30 | // total number of nodes
|
---|
31 | int nodes;
|
---|
32 | // number of splits along each of the axes
|
---|
33 | int splits[7];
|
---|
34 | // totals number of rays
|
---|
35 | int rays;
|
---|
36 | // total number of query domains
|
---|
37 | int queryDomains;
|
---|
38 | // total number of ray references
|
---|
39 | int rayRefs;
|
---|
40 | // refs in non empty leafs
|
---|
41 | int rayRefsNonZeroQuery;
|
---|
42 | // total number of query references
|
---|
43 | int objectRefs;
|
---|
44 | // nodes with zero queries
|
---|
45 | int zeroQueryNodes;
|
---|
46 | // max depth nodes
|
---|
47 | int maxDepthNodes;
|
---|
48 | // max depth nodes
|
---|
49 | int minCostNodes;
|
---|
50 | // max number of rays per node
|
---|
51 | int maxObjectRefs;
|
---|
52 | // max number of rays per node
|
---|
53 | int totalObjectRefs;
|
---|
54 | // number of dynamically added ray refs
|
---|
55 | int addedRayRefs;
|
---|
56 | // number of dynamically removed ray refs
|
---|
57 | int removedRayRefs;
|
---|
58 |
|
---|
59 | // Constructor
|
---|
60 | TraversalTreeStatistics()
|
---|
61 | {
|
---|
62 | Reset();
|
---|
63 | }
|
---|
64 |
|
---|
65 | int Nodes() const {return nodes;}
|
---|
66 | int Interior() const { return nodes / 2; }
|
---|
67 | int Leaves() const { return (nodes / 2) + 1; }
|
---|
68 |
|
---|
69 | void Reset()
|
---|
70 | {
|
---|
71 | nodes = 0;
|
---|
72 |
|
---|
73 | for (int i=0; i<7; i++)
|
---|
74 | splits[i] = 0;
|
---|
75 |
|
---|
76 | rays = queryDomains = 0;
|
---|
77 | rayRefs = rayRefsNonZeroQuery = objectRefs = 0;
|
---|
78 | zeroQueryNodes = 0;
|
---|
79 | maxDepthNodes = 0;
|
---|
80 | minCostNodes = 0;
|
---|
81 | maxObjectRefs = 0;
|
---|
82 | totalObjectRefs = 0;
|
---|
83 | addedRayRefs = removedRayRefs = 0;
|
---|
84 | }
|
---|
85 |
|
---|
86 | void Print(ostream &app) const;
|
---|
87 |
|
---|
88 | friend ostream &operator<<(ostream &s, const TraversalTreeStatistics &stat)
|
---|
89 | {
|
---|
90 | stat.Print(s);
|
---|
91 | return s;
|
---|
92 | }
|
---|
93 |
|
---|
94 | };
|
---|
95 |
|
---|
96 |
|
---|
97 | class TraversalInterior;
|
---|
98 |
|
---|
99 | /** Abstract class for kd-tree node
|
---|
100 | */
|
---|
101 | class TraversalNode
|
---|
102 | {
|
---|
103 | public:
|
---|
104 |
|
---|
105 | virtual ~TraversalNode(){};
|
---|
106 |
|
---|
107 | TraversalNode(TraversalInterior *parent);
|
---|
108 | /** Determines whether this node is a leaf or interior node
|
---|
109 | @return true if leaf
|
---|
110 | */
|
---|
111 | virtual bool IsLeaf() const = 0;
|
---|
112 |
|
---|
113 | /** Determines whether this node is the root of the tree
|
---|
114 | @return true if root
|
---|
115 | */
|
---|
116 | virtual bool IsRoot() const
|
---|
117 | {
|
---|
118 | return mParent == NULL;
|
---|
119 | }
|
---|
120 |
|
---|
121 | /** Parent of the node - the parent is a little overhead for
|
---|
122 | maintanance of the tree, but allows various optimizations
|
---|
123 | of tree traversal algorithms
|
---|
124 | */
|
---|
125 | TraversalInterior *mParent;
|
---|
126 |
|
---|
127 |
|
---|
128 | ///////////////////
|
---|
129 | // mailing stuff
|
---|
130 |
|
---|
131 | public:
|
---|
132 |
|
---|
133 | void Mail()
|
---|
134 | {
|
---|
135 | mMailbox = sMailId;
|
---|
136 | }
|
---|
137 |
|
---|
138 | bool Mailed() const
|
---|
139 | {
|
---|
140 | return mMailbox == sMailId;
|
---|
141 | }
|
---|
142 |
|
---|
143 | static void NewMail(const int reserve = 1)
|
---|
144 | {
|
---|
145 | sMailId += sReservedMailboxes;
|
---|
146 | sReservedMailboxes = reserve;
|
---|
147 | }
|
---|
148 |
|
---|
149 | void Mail(const int mailbox)
|
---|
150 | {
|
---|
151 | mMailbox = sMailId + mailbox;
|
---|
152 | }
|
---|
153 |
|
---|
154 |
|
---|
155 | bool Mailed(const int mailbox) const
|
---|
156 | {
|
---|
157 | return mMailbox == sMailId + mailbox;
|
---|
158 | }
|
---|
159 |
|
---|
160 | int mMailbox;
|
---|
161 |
|
---|
162 | static int sMailId;
|
---|
163 | static int sReservedMailboxes;
|
---|
164 | };
|
---|
165 |
|
---|
166 |
|
---|
167 | /** Implementation of the kd-tree interior node
|
---|
168 | */
|
---|
169 | class TraversalInterior : public TraversalNode
|
---|
170 | {
|
---|
171 | public:
|
---|
172 |
|
---|
173 | TraversalInterior(TraversalInterior *parent);
|
---|
174 | ~TraversalInterior();
|
---|
175 |
|
---|
176 | /** \sa TraversalNode::IsLeaf()
|
---|
177 | */
|
---|
178 | bool IsLeaf() const;
|
---|
179 |
|
---|
180 | void SetupChildLinks(TraversalNode *b, TraversalNode *f);
|
---|
181 |
|
---|
182 | void ReplaceChildLink(TraversalNode *oldChild, TraversalNode *newChild);
|
---|
183 |
|
---|
184 |
|
---|
185 | //////////////////////////
|
---|
186 |
|
---|
187 | /// splitting axis
|
---|
188 | int mAxis;
|
---|
189 | /// splitting position, absolute position within the bounding box of this node.
|
---|
190 | float mPosition;
|
---|
191 | /// bounding box of interior node
|
---|
192 | AxisAlignedBox3 mBox;
|
---|
193 |
|
---|
194 | /// back node
|
---|
195 | TraversalNode *mBack;
|
---|
196 | /// front node
|
---|
197 | TraversalNode *mFront;
|
---|
198 | };
|
---|
199 |
|
---|
200 |
|
---|
201 | /** Implementation of the kd-tree leaf node
|
---|
202 | */
|
---|
203 | class TraversalLeaf : public TraversalNode
|
---|
204 | {
|
---|
205 | public:
|
---|
206 |
|
---|
207 | TraversalLeaf(TraversalInterior *parent, const int objects);
|
---|
208 |
|
---|
209 | ~TraversalLeaf();
|
---|
210 |
|
---|
211 | /** \sa TraversalNode::IsLeaf()
|
---|
212 | */
|
---|
213 | virtual bool IsLeaf() const;
|
---|
214 |
|
---|
215 | /////////////////////////////////
|
---|
216 |
|
---|
217 | // pointers to view cells contained in this node
|
---|
218 | ViewCellContainer mViewCells;
|
---|
219 |
|
---|
220 | short mDepth;
|
---|
221 | };
|
---|
222 |
|
---|
223 |
|
---|
224 | /** TraversalTree for indexing scene entities - occluders/occludees/viewcells
|
---|
225 | */
|
---|
226 | class TraversalTree
|
---|
227 | {
|
---|
228 |
|
---|
229 | protected:
|
---|
230 |
|
---|
231 | struct TraversalData
|
---|
232 | {
|
---|
233 | TraversalNode *mNode;
|
---|
234 | AxisAlignedBox3 mBox;
|
---|
235 | int mDepth;
|
---|
236 | float mPriority;
|
---|
237 |
|
---|
238 | TraversalData(): mNode(NULL), mPriority(0), mDepth(0) {}
|
---|
239 |
|
---|
240 | TraversalData(TraversalNode *n, const float p):
|
---|
241 | mNode(n), mPriority(p), mDepth(0)
|
---|
242 | {}
|
---|
243 |
|
---|
244 | TraversalData(TraversalNode *n,
|
---|
245 | const AxisAlignedBox3 &b,
|
---|
246 | const int d):
|
---|
247 | mNode(n), mBox(b), mDepth(d)
|
---|
248 | {}
|
---|
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->mViewCells.size() * mBox.SurfaceArea()
|
---|
258 | <
|
---|
259 | leafb->mViewCells.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(const ViewCellContainer &viewCells);
|
---|
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 | // view cells usually adjacent
|
---|
377 | if (EpsilonEqual(value, b.value, 0.001))
|
---|
378 | return (type == BOX_MAX);
|
---|
379 |
|
---|
380 | return value < b.value;
|
---|
381 | }*/
|
---|
382 | };
|
---|
383 |
|
---|
384 | inline static bool iltS(SortableEntry *a, SortableEntry *b)
|
---|
385 | {
|
---|
386 | // view cells usually adjacent
|
---|
387 | //if (EpsilonEqual(a->value, b->value))
|
---|
388 | // return false;
|
---|
389 | // return (a->type == SortableEntry::BOX_MAX);
|
---|
390 |
|
---|
391 | return a->value < b->value;
|
---|
392 | }
|
---|
393 |
|
---|
394 | // reusable array of split candidates
|
---|
395 | vector<SortableEntry *> *splitCandidates;
|
---|
396 |
|
---|
397 | float BestCostRatio(TraversalLeaf *node,
|
---|
398 | const AxisAlignedBox3 &box,
|
---|
399 | const int axis,
|
---|
400 | float &position,
|
---|
401 | int &objectsBack,
|
---|
402 | int &objectsFront);
|
---|
403 |
|
---|
404 | void SortSubdivisionCandidates(TraversalLeaf *node, const int axis);
|
---|
405 |
|
---|
406 | void EvaluateLeafStats(const TraversalData &data);
|
---|
407 |
|
---|
408 | TraversalNode *SubdivideNode(TraversalLeaf *leaf,
|
---|
409 | const AxisAlignedBox3 &box,
|
---|
410 | AxisAlignedBox3 &backBBox,
|
---|
411 | AxisAlignedBox3 &frontBBox
|
---|
412 | );
|
---|
413 |
|
---|
414 | bool TerminationCriteriaMet(const TraversalLeaf *leaf);
|
---|
415 |
|
---|
416 | int SelectPlane(TraversalLeaf *leaf,
|
---|
417 | const AxisAlignedBox3 &box,
|
---|
418 | float &position);
|
---|
419 |
|
---|
420 | int FindViewCellIntersections(const Vector3 &lStart,
|
---|
421 | const Vector3 &lEnd,
|
---|
422 | const ViewCellContainer &viewCells,
|
---|
423 | ViewCellContainer &hitViewCells,
|
---|
424 | const bool useMailboxing);
|
---|
425 |
|
---|
426 | ////////////////////////
|
---|
427 |
|
---|
428 | int mTermMaxNodes;
|
---|
429 | float mSplitBorder;
|
---|
430 | int mTermMaxDepth;
|
---|
431 | int mTermMinCost;
|
---|
432 | float mMaxCostRatio;
|
---|
433 | float mCt_div_ci;
|
---|
434 | int mSplitMethod;
|
---|
435 | bool mSahUseFaces;
|
---|
436 |
|
---|
437 | /// root of the tree
|
---|
438 | TraversalNode *mRoot;
|
---|
439 | /// bounding box of the tree root
|
---|
440 | AxisAlignedBox3 mBox;
|
---|
441 | TraversalTreeStatistics mStat;
|
---|
442 |
|
---|
443 | };
|
---|
444 |
|
---|
445 |
|
---|
446 | }
|
---|
447 |
|
---|
448 | #endif
|
---|