[2582] | 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 |
|
---|
| 31 | namespace 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
|
---|
| 44 | class 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
|
---|
| 127 | class CKTBNodeIteratorPredecessor:
|
---|
| 128 | #ifndef _KTB8Bytes
|
---|
| 129 | public CKTBNodeIterator
|
---|
| 130 | #else
|
---|
| 131 | public CKTB8BNodeIterator
|
---|
| 132 | #endif
|
---|
| 133 | {
|
---|
| 134 | public:
|
---|
| 135 | virtual int FindNearestI(const SimpleRay &ray) { return 0; }
|
---|
[2592] | 136 | virtual int FindNearestI(const SimpleRay &ray, const AxisAlignedBox3 &localbox) { return 0;}
|
---|
[2582] | 137 | void SetOffset(int offset) { rayOffset = offset; }
|
---|
| 138 | virtual int FindNearestI_16oneDir(SimpleRayContainer &rays) { return 0; }
|
---|
[2592] | 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; }
|
---|
[2582] | 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 |
|
---|
[2592] | 147 | #ifdef _USE_HAVRAN_SSE
|
---|
[2582] | 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) { }
|
---|
[2602] | 152 | virtual void FindNearestI(RayPacket2x2 &raypack, const Vector3 &boxMin, const Vector3 &boxMax) { }
|
---|
[2592] | 153 | #endif
|
---|
| 154 |
|
---|
[2582] | 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 |
|
---|
| 208 | class CKTBTraversal:
|
---|
| 209 | public CKTBNodeIteratorPredecessor
|
---|
| 210 | {
|
---|
| 211 | public:
|
---|
| 212 | // maximal height of the CKTB tree for nesting
|
---|
| 213 | enum { MAX_TRAVERSAL_HEIGHT = (MAX_HEIGHT * MAX_NESTING) };
|
---|
| 214 |
|
---|
| 215 | protected:
|
---|
| 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 |
|
---|
| 293 | public:
|
---|
| 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);
|
---|
[2592] | 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);
|
---|
[2582] | 319 |
|
---|
| 320 | int PrecomputeData(SimpleRayContainer &rays);
|
---|
| 321 | void ReverseRay(const int indexA);
|
---|
| 322 | virtual int FindNearestI_16twoDir(SimpleRayContainer &rays);
|
---|
| 323 |
|
---|
[2592] | 324 | #ifdef _USE_HAVRAN_SSE
|
---|
[2582] | 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);
|
---|
[2602] | 330 | virtual void FindNearestI(RayPacket2x2 &raypack, const Vector3 &boxMin, const Vector3 &boxMax);
|
---|
[2582] | 331 | #endif // __SSE__
|
---|
[2592] | 332 | #endif // _USE_HAVRAN_SSE
|
---|
| 333 |
|
---|
[2582] | 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.
|
---|
| 349 | class CKTBMinBoxesTraversal:
|
---|
| 350 | public CKTBNodeIteratorPredecessor
|
---|
| 351 | {
|
---|
| 352 | protected:
|
---|
| 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 |
|
---|
| 400 | public:
|
---|
| 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 |
|
---|
[2592] | 417 | #ifdef _USE_HAVRAN_SSE
|
---|
[2582] | 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);
|
---|
[2602] | 423 | virtual void FindNearestI(RayPacket2x2 &raypack, const Vector3 &boxMin, const Vector3 &boxMax);
|
---|
[2582] | 424 | #endif // __SSE__
|
---|
[2592] | 425 | #endif // _USE_HAVRAN_SSE
|
---|
[2582] | 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 |
|
---|