source: GTP/trunk/Lib/Vis/Preprocessing/src/havran/ktbtrav.h @ 2629

Revision 2629, 15.3 KB checked in by bittner, 17 years ago (diff)

commit after merge with vlastimil

Line 
1// ===================================================================
2// $Id: $
3//
4// ktbtrav.h
5//      Traversal class for CKTB structures
6//
7// Class: CKTBTraversal
8//
9// REPLACEMENT_STRING
10//
11// Copyright by Vlastimil Havran, 2007 - email to "vhavran AT seznam.cz"
12// Initial coding by Vlasta Havran, 2006
13
14#ifndef __KTBTRAV_H__
15#define __KTBTRAV_H__
16
17// GOLEM headers
18#include "configh.h"
19#include "ktbconf.h"
20#include "ktb.h"
21#include "ktb8b.h"
22#include "raypack.h"
23// From the framework of Jiri Bittner et al. GTP
24#include "SimpleRay.h"
25
26
27#ifdef __SSE__
28#include <xmmintrin.h>
29#endif
30
31namespace GtpVisibilityPreprocessor {
32 
33//#define TRV000
34//#define TRV001
35//#define TRV002
36//#define TRV003
37//#define TRV004
38//#define TRV005
39//#define TRV006
40//#define TRV007
41#define TRV00F
42
43// forward declarations
44class SKTBNode;
45
46// This is debugging of traversal for a new traversal variant
47//#define _DEBUGKTB
48
49// This is debugging of traversal storing depth at the stack
50//#define _KTBEXTSTACK
51 
52// VERSION1 - the version, where we prepare a sequence of boxes
53//            which never overlap (file ktbmtrav.cpp)
54// VERSION2 - the sequence of boxes can overlap and we solve which
55//            boxes to traverse online during the traversal (file ktbm2trv.cpp)
56// VERSION3 - the stackless algorithm based on interval tracking
57//            keeping entry and exit point (file ktbm3trv.cpp)
58// VERSION4 - the stack-based algorithm rewritten from ktbm3trv.cpp
59//            by adding the stack (file ktbm4trv.cpp)
60// VERSION5 - another stackless algorithm based on a single point and
61//            virtual box tracking (file ktbm5trv.cpp)
62// VERSION6 - simple sequential traversal algorithm without stack (TA_A)
63//            published originally already in year 1985 by Kaplan
64//            (file ktbm6trv.cpp)
65
66// //#define _KTBTRAV_VERSION0
67//#define _KTBTRAV_VERSION1
68//#define _KTBTRAV_VERSION2
69//#define _KTBTRAV_VERSION3
70//#define _KTBTRAV_VERSION4
71#define _KTBTRAV_VERSION5
72//#define _KTBTRAV_VERSION6
73
74// We cull away the nodes to be visited if they would be the same
75// as the next box in the sequence of nodes with boxes
76#define _CULL_IN_INTERIOR_NODES
77
78// If this macro is defined, then we extract the sequence of boxes to
79// the output buffer when visiting a leaf. When this macro is disabled,
80// we make test upon visiting a box node, which can be faster, as the
81// number of box nodes is smaller than the number of leaves visited
82#define EXTRACTSEQENENCEINLEAVES
83
84// This is special development debug
85#define _DEBUG_SAMELEAF
86
87// Pseudo visualization
88#define VIS_TRAVERSEDNODED
89
90// If this macro is defined, we use increment of
91// the signed distance to avoid visiting the same node again
92// by multiplication and addition
93// Otherwise (macro commented) we use a special function for that
94// based on IEEE754 representation of floating-point
95//#define INCTMIN
96
97// These are constants to increase signed distance when exiting leaf
98#define onePlusEps 1.000008f
99#define epsAdd 0.000008f
100
101//#define onePlusEps 1.00005f
102//#define epsAdd 0.0001f
103//const float onePlusEps = 1.0001f;
104//const float epsAdd = 0.0001f;
105//const float onePlusEps = 1.00008f;
106//const float epsAdd = 0.00005f;       
107//const float onePlusEps = 1.000008f;
108//const float epsAdd = 0.000008f;             
109//const float onePlusEps = 1.0000008f;
110//const float epsAdd = 0.00001f;       
111
112// Here are the macros to avoid traversing the same leaf again
113#define _DEBUGULPS
114#define INCULPS 1
115
116#ifndef _KTB8Bytes
117// 12 Bytes representation
118#undef  SKTBNodeT
119#define SKTBNodeT CKTBNodeAbstract::SKTBNode
120#else
121// 8 Bytes representation
122#undef  SKTBNodeT
123#define SKTBNodeT CKTB8BNodeAbstract::SKTBNode
124#endif
125
126// 12 Bytes representation
127class CKTBNodeIteratorPredecessor:
128#ifndef _KTB8Bytes
129  public CKTBNodeIterator
130#else
131  public CKTB8BNodeIterator
132#endif
133{
134public:
135  virtual int FindNearestI(const SimpleRay &ray) { return 0; }
136  virtual int FindNearestI(const SimpleRay &ray, const AxisAlignedBox3 &localbox) { return 0;}
137  void SetOffset(int offset) { rayOffset = offset; }
138  virtual int FindNearestI_16oneDir(SimpleRayContainer &rays) { return 0; }
139  virtual int FindNearestI_16oneDir(SimpleRayContainer &rays,
140                                    int offset, int copyOffset) { return 0; }
141  virtual int FindNearestI_16oneDirNoSSE(SimpleRayContainer &rays, int offset) { return 0; }
142  virtual int FindNearestI_16twoDir(SimpleRayContainer &rays) { return 0; }
143
144  // the number of nested kd-trees at most
145  enum { MAX_NESTING = 2};
146 
147#ifdef _USE_HAVRAN_SSE 
148  // The same operations for packets of rays, if implemented by
149  // a particular ASDS, otherwise it is emulated by decomposition
150  // of a packet to individual rays and traced individually.
151  virtual void FindNearestI(RayPacket2x2 &raypack) { }
152  virtual void FindNearestI(RayPacket2x2 &raypack, const Vector3 &boxMin,
153                            const Vector3 &boxMax) { }
154#endif
155 
156  virtual void PrintStatsTR(ostream &) { }
157  virtual void DynamicStatsReset() { }
158};
159
160// ---------------------------------------------------------------------------
161// Note on the usage:
162// Allow only one macro from the tree: _KTBTRAV_JANSEN86, _KTBTRAV_JGT98
163// and  _KTBTRAV_OPTIMIZED86
164
165// macro for using algorithm for traversal CKTB trees as stated by Jansen86,
166// Arvo88, and Kelving/Sung92 in Gems III.
167//#define _KTBTRAV_JANSEN86
168
169// Faster and robust algorithm is used, published in JGT 98
170// by Havran+Bittner+Kopal+Zara. It is fastest at the moment, measured in year 2005/6
171#define _KTBTRAV_JGT98
172
173// Modified algorithm from Jansen86 (Arvo88, Kelving/Sung92), optimized for
174// modern processors.
175//#define _KTBTRAV_OPTIMIZED86
176
177// ------------------------------------------------------------
178#undef _COMPUTE_INVERTED_DIR_KTB
179// This avoids the division when computed signed distance by precomputation
180// of the inverse of ray.dir for all three components
181#define _COMPUTE_INVERTED_DIR_KTB
182
183// Check if the only traversal algorithm was used.
184#ifdef _KTBTRAV_JANSEN86
185#if (defined(_KTBTRAV_JGT98) || defined(_KTBTRAV_OPTIMIZED86))
186#error "Allow only one of macros  _KTBTRAV_OPTIMIZED86, _KTBTRAV_JGT98, _KTBTRAV_OPTIMIZED86"
187#endif
188#endif
189//-------------------------
190#ifdef _KTBTRAV_JGT98
191#if (defined(_KTBTRAV_JANSEN86) || defined(_KTBTRAV_OPTIMIZED86))
192#error "Allow only one of macros  _KTBTRAV_OPTIMIZED86, _KTBTRAV_JGT98, _KTBTRAV_OPTIMIZED86"
193#endif
194#endif
195//-------------------------
196#ifdef _KTBTRAV_OPTIMIZED86
197#if (defined(_KTBTRAV_JANSEN86) || defined(_KTBTRAV_JGT98))
198#error "Allow only one of macros  _KTBTRAV_OPTIMIZED86, _KTBTRAV_JGT98, _KTBTRAV_OPTIMIZED86"
199#endif
200#endif
201
202// -------------------------------------------------------------------
203// robust statistically optimized algorithm for CKTB ray-traversal
204// version 025
205// This version appeared in JGT(Journal of Graphics Tools, Vol. 2, No.4,
206// 1997, pp.15-23. with title:
207// "FAST Robust KD-Tree Traversal Algorithm for Ray Tracing"
208
209class CKTBTraversal:
210  public CKTBNodeIteratorPredecessor
211{
212public:
213  // maximal height of the CKTB tree for nesting
214  enum { MAX_TRAVERSAL_HEIGHT = (MAX_HEIGHT * MAX_NESTING) };
215
216protected:
217  // the stack element for CKTB tree traversal
218  struct SStackElem {
219    SKTBNodeT *nodep;  // pointer to the node
220    // Vector3 point;  // entry/exit point
221    float    x,y,z;  // entry/exit point
222    float    t;      // signed distance of the point
223    SStackElem *prev;
224    SKTBNodeT *lastBoxNode; // here is the alingment
225#ifdef _KTBEXTSTACK
226    int       dummy; // storing the depth here
227#endif   
228  };
229
230  // the stack element for CKTB tree traversal
231  struct SStackElem2 {
232    SKTBNodeT *nodep;  // pointer to the node
233    int      dummy;
234    float    tmin;      // entry signed distance
235    float    tmax;      // exit signed distance
236  };
237  struct SStackElem3 {
238    SKTBNodeT *nodep;  // pointer to the node
239    float    tmax;     // exit signed distance
240  };
241
242  struct SStackElem4 {
243    SKTBNodeT *nodep;  // pointer to the node
244    int      mask;     // mask
245    int      pad[2];   // alignment to 16 bytes
246    union { float tmin4[4];
247#ifdef __SSE__
248      __m128 tmin_4;
249#endif
250    };
251    union { float tmax4[4];
252#ifdef __SSE__
253      __m128 tmax_4;
254#endif
255    };
256  };
257
258 
259  // the stack of elems - declared as static not to allocate it every time
260  static struct SStackElem stack[MAX_TRAVERSAL_HEIGHT];
261  static struct SStackElem2 stack2[MAX_TRAVERSAL_HEIGHT];
262  static struct SStackElem3 stack3[MAX_TRAVERSAL_HEIGHT];
263  static struct SStackElem4 stack4[MAX_TRAVERSAL_HEIGHT];
264
265#define cntMaxRays 16
266  static struct CKTBTraversal::SStackElem3 stackA[cntMaxRays * MAX_HEIGHT];
267
268  // the axis aligned box for CKTB tree space
269  AxisAlignedBox3 bbox;
270  // root node of the CKTB tree
271  SKTBNodeT *root;
272  // the small epsilon that is computed from the size of the whole box
273  float epsilon;
274
275  // sets the stack pointers that are used for the traversal.
276  void GetStackPointers(struct SStackElem *&entryPointer,
277                        struct SStackElem *&exitPointer);
278  void GetStartStackPointer(struct SStackElem *&exitPointer);
279 
280  // this function should be called when exiting from the traversal function
281  // to keep the track on the traversalDepth (of kd-trees, when they are nested).
282  void RestoreStackPointers();
283
284  // the depth of traversal when kd-trees are nested. The global (the highest
285  // level) kd-tree is at the depth 0.
286  static int traversalDepth;
287
288#ifdef __TRAVERSAL_STATISTICS
289  long unsigned int _allNodesTraversed;
290  long unsigned int _fullLeavesTraversed;
291  long unsigned int _emptyLeavesTraversed;
292#endif
293
294public:
295  // default constructor
296  CKTBTraversal();
297
298  // destructor
299  virtual ~CKTBTraversal() {}
300
301  // sets the bbox and the root node for this traversal class
302  virtual void Setup(const AxisAlignedBox3 &box, SKTBNodeT *Nroot)
303    { bbox = box; root = Nroot; epsilon=(float)(1e-6*Magnitude(bbox.Size())); }
304
305  // potentionally, sets the list of unbounded objects if required
306  virtual void Setup2(CObjectList *) { // int count = unboundeds->ListCount();
307  }
308
309  virtual int FindNearestI(const SimpleRay &ray);
310  virtual int FindNearestI(const SimpleRay &ray, const AxisAlignedBox3 &localbox);
311  virtual int FindNearestI_16oneDir(SimpleRayContainer &rays,
312                                    int offset, int copyOffset)
313#ifdef _USE_HAVRAN_SSE 
314    ; // this is implemented with SSE in ktbftrav.cpp !
315#else
316  { return 0;}
317#endif
318   
319  virtual int FindNearestI_16oneDirNoSSE(SimpleRayContainer &rays, int offset);
320
321  int PrecomputeData(SimpleRayContainer &rays);
322  void ReverseRay(const int indexA);
323  virtual int FindNearestI_16twoDir(SimpleRayContainer &rays);
324
325#ifdef _USE_HAVRAN_SSE 
326#ifdef __SSE__
327  // The same operations for packets of rays, if implemented by
328  // a particular ASDS, otherwise it is emulated by decomposition
329  // of a packet to individual rays and traced individually.
330  virtual void FindNearestI(RayPacket2x2 &raypack);
331  virtual void FindNearestI(RayPacket2x2 &raypack, const Vector3 &boxMin,
332                            const Vector3 &boxMax);
333#endif // __SSE__
334#endif // _USE_HAVRAN_SSE 
335 
336  virtual void PrintStatsTR(ostream &) { }
337
338  void AssignIDs(SKTBNodeT *node = NULL);
339
340  // this resets the nesting to start from the zero depth (root)
341  virtual void ResetTraversalDepth() { traversalDepth = 0;}
342
343  // Here we find the node (preferably minbox node) containing
344  // the point
345  virtual const SKTBNode* Locate(const Vector3 &position);
346};
347
348#if 0
349// The version taking into account min boxes sparsely distributed in
350// the kd-tree.
351class CKTBMinBoxesTraversal:
352  public CKTBNodeIteratorPredecessor
353{
354protected:
355  // the stack element for CKTB tree traversal
356  struct SStackElem {
357    SKTBNodeT *nodep;  // pointer to the node
358    // Vector3 point;  // entry/exit point
359    float    x,y,z;  // entry/exit point
360    float    t;      // signed distance of the point
361    SStackElem *prev;
362    SKTBNodeT *lastBoxNode; // here is the alingment
363//#ifdef _KTBEXTSTACK
364    int       dummy; // storing the depth here
365//#endif   
366  };
367
368  // maximal height of the CKTB tree for nesting
369  enum { MAX_TRAVERSAL_HEIGHT = (MAX_HEIGHT * MAX_NESTING) };
370 
371  // the stack of elems - declared as static not to allocate it every time
372  static struct SStackElem stack[MAX_TRAVERSAL_HEIGHT];
373
374  // the axis aligned box for CKTB tree space
375  AxisAlignedBox3 bbox;
376  // root node of the CKTB tree
377  SKTBNodeT *root;
378  // the small epsilon that is computed from the size of the whole box
379  float epsilon;
380  // size of the write buffer
381  int size1D;
382
383  // sets the stack pointers that are used for the traversal.
384  void GetStackPointers(struct SStackElem *&entryPointer,
385                        struct SStackElem *&exitPointer);
386  void GetStartStackPointer(struct SStackElem *&exitPointer);
387 
388  // this function should be called when exiting from the traversal function
389  // to keep the track on the traversalDepth (of kd-trees, when they are nested).
390  void RestoreStackPointers();
391
392  // the depth of traversal when kd-trees are nested. The global (the highest
393  // level) kd-tree is at the depth 0.
394  static int traversalDepth;
395
396#ifdef __TRAVERSAL_STATISTICS
397  long unsigned int _allNodesTraversed;
398  long unsigned int _fullLeavesTraversed;
399  long unsigned int _emptyLeavesTraversed;
400#endif
401 
402public:
403  // default constructor
404  CKTBMinBoxesTraversal(int size1Dv);
405
406  // destructor
407  virtual ~CKTBMinBoxesTraversal();
408
409  // sets the bbox and the root node for this traversal class
410  virtual void Setup(const AxisAlignedBox3 &box, SKTBNodeT *Nroot)
411    { bbox = box; root = Nroot; epsilon=(float)(1e-6*Magnitude(bbox.Size())); }
412
413  // potentionally, sets the list of unbounded objects if required
414  virtual void Setup2(CObjectList *) { // int count = unboundeds->ListCount();
415  }
416
417  virtual int FindNearestI(SimpleRay &ray);
418
419#ifdef _USE_HAVRAN_SSE 
420#ifdef __SSE__
421  // The same operations for packets of rays, if implemented by
422  // a particular ASDS, otherwise it is emulated by decomposition
423  // of a packet to individual rays and traced individually.
424  virtual void FindNearestI(RayPacket2x2 &raypack);
425  virtual void FindNearestI(RayPacket2x2 &raypack, const Vector3 &boxMin,
426                            const Vector3 &boxMax);
427#endif // __SSE__
428#endif // _USE_HAVRAN_SSE 
429
430  virtual void DynamicStatsReset();
431 
432  virtual void PrintStatsTR(ostream &);
433
434  void AssignIDs(SKTBNodeT *node = NULL);
435
436  // this resets the nesting to start from the zero depth (root)
437  virtual void ResetTraversalDepth() { traversalDepth = 0;}
438
439#ifdef __TRAVERSAL_STATISTICS
440  unsigned long int statsMB_UpTraversals;
441  unsigned long int statsMB_DownTraversals;
442  unsigned long int statsMB_cntRays;
443  unsigned long int statsMB_cntRaysHB;
444  unsigned long int statsMB_UseTraversals;
445  unsigned long int statsMB_UseValidTraversals;
446  unsigned long int statsMB_allNodesTraversed;
447  unsigned long int statsMB_fullLeavesTraversed;
448  unsigned long int statsMB_emptyLeavesTraversed;
449  unsigned long int bugTheSameLeaf;
450  unsigned long int statsMB_writtenBoxes;
451  unsigned long int statsMB_readBoxes;
452  unsigned long int statsMB_cntWrittenBoxSequenceEvent;
453  unsigned long int statsMB_cntReadBoxSequenceEvent;
454#endif
455
456  // Here we find the node (preferably minbox node) containing
457  // the point
458  virtual const SKTBNode* Locate(const Vector3 &position);
459};
460#endif
461 
462} // namespace
463
464#endif // __KTBTRAV_H__
465
Note: See TracBrowser for help on using the repository browser.