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

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

Havran ray Caster update

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, const Vector3 &boxMax) { }
153#endif
154 
155  virtual void PrintStatsTR(ostream &) { }
156  virtual void DynamicStatsReset() { }
157};
158
159// ---------------------------------------------------------------------------
160// Note on the usage:
161// Allow only one macro from the tree: _KTBTRAV_JANSEN86, _KTBTRAV_JGT98
162// and  _KTBTRAV_OPTIMIZED86
163
164// macro for using algorithm for traversal CKTB trees as stated by Jansen86,
165// Arvo88, and Kelving/Sung92 in Gems III.
166//#define _KTBTRAV_JANSEN86
167
168// Faster and robust algorithm is used, published in JGT 98
169// by Havran+Bittner+Kopal+Zara. It is fastest at the moment, measured in year 2005/6
170#define _KTBTRAV_JGT98
171
172// Modified algorithm from Jansen86 (Arvo88, Kelving/Sung92), optimized for
173// modern processors.
174//#define _KTBTRAV_OPTIMIZED86
175
176// ------------------------------------------------------------
177#undef _COMPUTE_INVERTED_DIR_KTB
178// This avoids the division when computed signed distance by precomputation
179// of the inverse of ray.dir for all three components
180#define _COMPUTE_INVERTED_DIR_KTB
181
182// Check if the only traversal algorithm was used.
183#ifdef _KTBTRAV_JANSEN86
184#if (defined(_KTBTRAV_JGT98) || defined(_KTBTRAV_OPTIMIZED86))
185#error "Allow only one of macros  _KTBTRAV_OPTIMIZED86, _KTBTRAV_JGT98, _KTBTRAV_OPTIMIZED86"
186#endif
187#endif
188//-------------------------
189#ifdef _KTBTRAV_JGT98
190#if (defined(_KTBTRAV_JANSEN86) || defined(_KTBTRAV_OPTIMIZED86))
191#error "Allow only one of macros  _KTBTRAV_OPTIMIZED86, _KTBTRAV_JGT98, _KTBTRAV_OPTIMIZED86"
192#endif
193#endif
194//-------------------------
195#ifdef _KTBTRAV_OPTIMIZED86
196#if (defined(_KTBTRAV_JANSEN86) || defined(_KTBTRAV_JGT98))
197#error "Allow only one of macros  _KTBTRAV_OPTIMIZED86, _KTBTRAV_JGT98, _KTBTRAV_OPTIMIZED86"
198#endif
199#endif
200
201// -------------------------------------------------------------------
202// robust statistically optimized algorithm for CKTB ray-traversal
203// version 025
204// This version appeared in JGT(Journal of Graphics Tools, Vol. 2, No.4,
205// 1997, pp.15-23. with title:
206// "FAST Robust KD-Tree Traversal Algorithm for Ray Tracing"
207
208class CKTBTraversal:
209  public CKTBNodeIteratorPredecessor
210{
211public:
212  // maximal height of the CKTB tree for nesting
213  enum { MAX_TRAVERSAL_HEIGHT = (MAX_HEIGHT * MAX_NESTING) };
214
215protected:
216  // the stack element for CKTB tree traversal
217  struct SStackElem {
218    SKTBNodeT *nodep;  // pointer to the node
219    // Vector3 point;  // entry/exit point
220    float    x,y,z;  // entry/exit point
221    float    t;      // signed distance of the point
222    SStackElem *prev;
223    SKTBNodeT *lastBoxNode; // here is the alingment
224#ifdef _KTBEXTSTACK
225    int       dummy; // storing the depth here
226#endif   
227  };
228
229  // the stack element for CKTB tree traversal
230  struct SStackElem2 {
231    SKTBNodeT *nodep;  // pointer to the node
232    int      dummy;
233    float    tmin;      // entry signed distance
234    float    tmax;      // exit signed distance
235  };
236  struct SStackElem3 {
237    SKTBNodeT *nodep;  // pointer to the node
238    float    tmax;     // exit signed distance
239  };
240
241  struct SStackElem4 {
242    SKTBNodeT *nodep;  // pointer to the node
243    int      mask;     // mask
244    int      pad[2];   // alignment to 16 bytes
245    union { float tmin4[4];
246#ifdef __SSE__
247      __m128 tmin_4;
248#endif
249    };
250    union { float tmax4[4];
251#ifdef __SSE__
252      __m128 tmax_4;
253#endif
254    };
255  };
256
257 
258  // the stack of elems - declared as static not to allocate it every time
259  static struct SStackElem stack[MAX_TRAVERSAL_HEIGHT];
260  static struct SStackElem2 stack2[MAX_TRAVERSAL_HEIGHT];
261  static struct SStackElem3 stack3[MAX_TRAVERSAL_HEIGHT];
262  static struct SStackElem4 stack4[MAX_TRAVERSAL_HEIGHT];
263
264#define cntMaxRays 16
265  static struct CKTBTraversal::SStackElem3 stackA[cntMaxRays * MAX_HEIGHT];
266
267  // the axis aligned box for CKTB tree space
268  AxisAlignedBox3 bbox;
269  // root node of the CKTB tree
270  SKTBNodeT *root;
271  // the small epsilon that is computed from the size of the whole box
272  float epsilon;
273
274  // sets the stack pointers that are used for the traversal.
275  void GetStackPointers(struct SStackElem *&entryPointer,
276                        struct SStackElem *&exitPointer);
277  void GetStartStackPointer(struct SStackElem *&exitPointer);
278 
279  // this function should be called when exiting from the traversal function
280  // to keep the track on the traversalDepth (of kd-trees, when they are nested).
281  void RestoreStackPointers();
282
283  // the depth of traversal when kd-trees are nested. The global (the highest
284  // level) kd-tree is at the depth 0.
285  static int traversalDepth;
286
287#ifdef __TRAVERSAL_STATISTICS
288  long unsigned int _allNodesTraversed;
289  long unsigned int _fullLeavesTraversed;
290  long unsigned int _emptyLeavesTraversed;
291#endif
292
293public:
294  // default constructor
295  CKTBTraversal();
296
297  // destructor
298  virtual ~CKTBTraversal() {}
299
300  // sets the bbox and the root node for this traversal class
301  virtual void Setup(const AxisAlignedBox3 &box, SKTBNodeT *Nroot)
302    { bbox = box; root = Nroot; epsilon=(float)(1e-6*Magnitude(bbox.Size())); }
303
304  // potentionally, sets the list of unbounded objects if required
305  virtual void Setup2(CObjectList *) { // int count = unboundeds->ListCount();
306  }
307
308  virtual int FindNearestI(const SimpleRay &ray);
309  virtual int FindNearestI(const SimpleRay &ray, const AxisAlignedBox3 &localbox);
310  virtual int FindNearestI_16oneDir(SimpleRayContainer &rays,
311                                    int offset, int copyOffset)
312#ifdef _USE_HAVRAN_SSE 
313    ; // this is implemented with SSE in ktbftrav.cpp !
314#else
315  { return 0;}
316#endif
317   
318  virtual int FindNearestI_16oneDirNoSSE(SimpleRayContainer &rays, int offset);
319
320  int PrecomputeData(SimpleRayContainer &rays);
321  void ReverseRay(const int indexA);
322  virtual int FindNearestI_16twoDir(SimpleRayContainer &rays);
323
324#ifdef _USE_HAVRAN_SSE 
325#ifdef __SSE__
326  // The same operations for packets of rays, if implemented by
327  // a particular ASDS, otherwise it is emulated by decomposition
328  // of a packet to individual rays and traced individually.
329  virtual void FindNearestI(RayPacket2x2 &raypack);
330  virtual void FindNearestI(RayPacket2x2 &raypack, const Vector3 &boxMin, const Vector3 &boxMax);
331#endif // __SSE__
332#endif // _USE_HAVRAN_SSE 
333 
334  virtual void PrintStatsTR(ostream &) { }
335
336  void AssignIDs(SKTBNodeT *node = NULL);
337
338  // this resets the nesting to start from the zero depth (root)
339  virtual void ResetTraversalDepth() { traversalDepth = 0;}
340
341  // Here we find the node (preferably minbox node) containing
342  // the point
343  virtual const SKTBNode* Locate(const Vector3 &position);
344};
345
346#if 0
347// The version taking into account min boxes sparsely distributed in
348// the kd-tree.
349class CKTBMinBoxesTraversal:
350  public CKTBNodeIteratorPredecessor
351{
352protected:
353  // the stack element for CKTB tree traversal
354  struct SStackElem {
355    SKTBNodeT *nodep;  // pointer to the node
356    // Vector3 point;  // entry/exit point
357    float    x,y,z;  // entry/exit point
358    float    t;      // signed distance of the point
359    SStackElem *prev;
360    SKTBNodeT *lastBoxNode; // here is the alingment
361//#ifdef _KTBEXTSTACK
362    int       dummy; // storing the depth here
363//#endif   
364  };
365
366  // maximal height of the CKTB tree for nesting
367  enum { MAX_TRAVERSAL_HEIGHT = (MAX_HEIGHT * MAX_NESTING) };
368 
369  // the stack of elems - declared as static not to allocate it every time
370  static struct SStackElem stack[MAX_TRAVERSAL_HEIGHT];
371
372  // the axis aligned box for CKTB tree space
373  AxisAlignedBox3 bbox;
374  // root node of the CKTB tree
375  SKTBNodeT *root;
376  // the small epsilon that is computed from the size of the whole box
377  float epsilon;
378  // size of the write buffer
379  int size1D;
380
381  // sets the stack pointers that are used for the traversal.
382  void GetStackPointers(struct SStackElem *&entryPointer,
383                        struct SStackElem *&exitPointer);
384  void GetStartStackPointer(struct SStackElem *&exitPointer);
385 
386  // this function should be called when exiting from the traversal function
387  // to keep the track on the traversalDepth (of kd-trees, when they are nested).
388  void RestoreStackPointers();
389
390  // the depth of traversal when kd-trees are nested. The global (the highest
391  // level) kd-tree is at the depth 0.
392  static int traversalDepth;
393
394#ifdef __TRAVERSAL_STATISTICS
395  long unsigned int _allNodesTraversed;
396  long unsigned int _fullLeavesTraversed;
397  long unsigned int _emptyLeavesTraversed;
398#endif
399 
400public:
401  // default constructor
402  CKTBMinBoxesTraversal(int size1Dv);
403
404  // destructor
405  virtual ~CKTBMinBoxesTraversal();
406
407  // sets the bbox and the root node for this traversal class
408  virtual void Setup(const AxisAlignedBox3 &box, SKTBNodeT *Nroot)
409    { bbox = box; root = Nroot; epsilon=(float)(1e-6*Magnitude(bbox.Size())); }
410
411  // potentionally, sets the list of unbounded objects if required
412  virtual void Setup2(CObjectList *) { // int count = unboundeds->ListCount();
413  }
414
415  virtual int FindNearestI(SimpleRay &ray);
416
417#ifdef _USE_HAVRAN_SSE 
418#ifdef __SSE__
419  // The same operations for packets of rays, if implemented by
420  // a particular ASDS, otherwise it is emulated by decomposition
421  // of a packet to individual rays and traced individually.
422  virtual void FindNearestI(RayPacket2x2 &raypack);
423  virtual void FindNearestI(RayPacket2x2 &raypack, const Vector3 &boxMin, const Vector3 &boxMax);
424#endif // __SSE__
425#endif // _USE_HAVRAN_SSE 
426
427  virtual void DynamicStatsReset();
428 
429  virtual void PrintStatsTR(ostream &);
430
431  void AssignIDs(SKTBNodeT *node = NULL);
432
433  // this resets the nesting to start from the zero depth (root)
434  virtual void ResetTraversalDepth() { traversalDepth = 0;}
435
436#ifdef __TRAVERSAL_STATISTICS
437  unsigned long int statsMB_UpTraversals;
438  unsigned long int statsMB_DownTraversals;
439  unsigned long int statsMB_cntRays;
440  unsigned long int statsMB_cntRaysHB;
441  unsigned long int statsMB_UseTraversals;
442  unsigned long int statsMB_UseValidTraversals;
443  unsigned long int statsMB_allNodesTraversed;
444  unsigned long int statsMB_fullLeavesTraversed;
445  unsigned long int statsMB_emptyLeavesTraversed;
446  unsigned long int bugTheSameLeaf;
447  unsigned long int statsMB_writtenBoxes;
448  unsigned long int statsMB_readBoxes;
449  unsigned long int statsMB_cntWrittenBoxSequenceEvent;
450  unsigned long int statsMB_cntReadBoxSequenceEvent;
451#endif
452
453  // Here we find the node (preferably minbox node) containing
454  // the point
455  virtual const SKTBNode* Locate(const Vector3 &position);
456};
457#endif
458 
459} // namespace
460
461#endif // __KTBTRAV_H__
462
Note: See TracBrowser for help on using the repository browser.