[2582] | 1 | // ===================================================================
|
---|
| 2 | // $Id: $
|
---|
| 3 | //
|
---|
| 4 | // ktbftrav.cpp
|
---|
| 5 | //
|
---|
| 6 | // class: CKTBTraversal
|
---|
| 7 | //
|
---|
| 8 | // REPLACEMENT_STRING
|
---|
| 9 | //
|
---|
| 10 | // Copyright by Vlastimil Havran, 2007 - email to "vhavran AT seznam.cz"
|
---|
| 11 | // Initial coding by Vlasta Havran, February 2007 (copy from kdrtrav.cpp)
|
---|
| 12 |
|
---|
| 13 | // GOLEM headers
|
---|
| 14 | #include "ktbconf.h"
|
---|
| 15 | #include "ktbtrav.h"
|
---|
| 16 | #include "Intersectable.h"
|
---|
| 17 |
|
---|
| 18 | namespace GtpVisibilityPreprocessor {
|
---|
| 19 |
|
---|
| 20 | #ifdef TRV00F
|
---|
| 21 |
|
---|
[2592] | 22 | // --------------------------------------------------------------
|
---|
| 23 | // Shooting a single ray without SSE
|
---|
[2582] | 24 | int
|
---|
| 25 | CKTBTraversal::FindNearestI(const SimpleRay &ray)
|
---|
| 26 | {
|
---|
| 27 | #if 0
|
---|
| 28 | static int counter = 0;
|
---|
| 29 | counter++;
|
---|
| 30 | bool debug = false;
|
---|
| 31 | if (counter == 530) {
|
---|
| 32 | debug = true;
|
---|
| 33 | cout << "COUNTER = " << counter << endl;
|
---|
| 34 | cout << "DEBUG starts" << endl;
|
---|
| 35 | }
|
---|
| 36 | #endif
|
---|
| 37 |
|
---|
| 38 | // passing through parameters
|
---|
| 39 | float tmin, tmax;
|
---|
[2592] | 40 | SimpleRay::IntersectionRes[0].intersectable = 0;
|
---|
[2582] | 41 |
|
---|
| 42 | // test if the whole CKTB tree is missed by the input ray
|
---|
| 43 | if ( (!root) ||
|
---|
| 44 | (!bbox.ComputeMinMaxT(ray.mOrigin, ray.mDirection, &tmin, &tmax)) ||
|
---|
[2592] | 45 | (tmax < tmin) ||
|
---|
[2582] | 46 | (tmax <= 0.f) ) {
|
---|
| 47 | return 0; // no object can be intersected
|
---|
| 48 | }
|
---|
| 49 |
|
---|
| 50 | //#define _DEBUGKTB
|
---|
| 51 | #ifdef _DEBUGKTB
|
---|
| 52 | int ib = 0;
|
---|
| 53 | int depth = 0;
|
---|
| 54 | #endif
|
---|
| 55 |
|
---|
| 56 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 57 | int allNodesTraversed = 0L;
|
---|
| 58 | int fullLeavesTraversed = 0L;
|
---|
| 59 | int emptyLeavesTraversed = 0L;
|
---|
| 60 | #endif // __TRAVERSAL_STATISTICS
|
---|
| 61 |
|
---|
| 62 | Vector3 invertedDir;
|
---|
[2592] | 63 | invertedDir.x = 1.0f / (ray.mDirection.x - 1e-25f);
|
---|
| 64 | invertedDir.y = 1.0f / (ray.mDirection.y - 1e-25f);
|
---|
| 65 | invertedDir.z = 1.0f / (ray.mDirection.z - 1e-25f);
|
---|
[2582] | 66 |
|
---|
| 67 | // start from the root node
|
---|
| 68 | if (tmin < 0.f)
|
---|
| 69 | tmin = 0.f;
|
---|
| 70 |
|
---|
| 71 | int index = 1;
|
---|
| 72 | stack3[1].nodep = root;
|
---|
| 73 | stack3[1].tmax = tmax;
|
---|
| 74 | tmax = tmin;
|
---|
| 75 | SKTBNodeT * childNodes[2];
|
---|
| 76 | int RayDirs[3];
|
---|
| 77 | RayDirs[0] = ray.mDirection.x < 0.f ? 1 : 0;
|
---|
| 78 | RayDirs[1] = ray.mDirection.y < 0.f ? 1 : 0;
|
---|
| 79 | RayDirs[2] = ray.mDirection.z < 0.f ? 1 : 0;
|
---|
| 80 |
|
---|
| 81 | // we have to check the node
|
---|
| 82 | // current node is not the leaf, empty leaves are NULL pointers
|
---|
| 83 | while (index) {
|
---|
| 84 | register SKTBNodeT *currNode = stack3[index].nodep;
|
---|
| 85 | tmin = tmax;
|
---|
| 86 | tmax = stack3[index].tmax;
|
---|
| 87 | #if 0
|
---|
| 88 | if (debug) {
|
---|
| 89 | cout << "node = " << (void*)currNode
|
---|
| 90 | << " tmin = " << tmin << " tmax = " << tmax
|
---|
| 91 | << endl;
|
---|
| 92 | }
|
---|
| 93 | #endif
|
---|
[2592] | 94 |
|
---|
| 95 | CONTINUE_LINK:
|
---|
| 96 |
|
---|
[2582] | 97 | assert(tmin <= tmax);
|
---|
| 98 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 99 | allNodesTraversed++;
|
---|
| 100 | #endif // __TRAVERSAL_STATISTICS
|
---|
[2592] | 101 |
|
---|
[2582] | 102 | register const int nodeType = GetNodeType(currNode);
|
---|
[2592] | 103 |
|
---|
| 104 | // cout << " tmin = " << tmin << " tmax = " << tmax << " nodeType = " << (int)nodeType << endl;
|
---|
| 105 |
|
---|
[2582] | 106 | if (nodeType < CKTBAxes::EE_Leaf) {
|
---|
| 107 | float tval = (GetSplitValue(currNode) - ray.mOrigin[nodeType]);
|
---|
| 108 | tval *= invertedDir[nodeType];
|
---|
| 109 | SKTBNodeT *near, *far;
|
---|
| 110 | childNodes[0] = GetLeft(currNode);
|
---|
| 111 | childNodes[1] = GetRight(currNode);
|
---|
| 112 | int rayDir = RayDirs[nodeType];
|
---|
| 113 | near = childNodes[rayDir];
|
---|
| 114 | far = childNodes[rayDir ^ 0x1];
|
---|
| 115 |
|
---|
| 116 | stack3[index].nodep = far;
|
---|
| 117 | // stack3[index].tmax = tmax; // not necessary, this is already there !
|
---|
| 118 | // int c = tval < tmax ? 1 : 0;
|
---|
| 119 | index += tval < tmax ? 1 : 0;
|
---|
| 120 | stack3[index].nodep = near;
|
---|
| 121 | stack3[index].tmax = Min(tval, tmax);
|
---|
| 122 | tmax = tmin;
|
---|
| 123 | // int d = tval < tmin ? -1 : 0;
|
---|
| 124 | index += tval < tmin ? -1 : 0;
|
---|
| 125 | }
|
---|
| 126 | else {
|
---|
| 127 | if (nodeType == CKTBAxes::EE_Leaf) {
|
---|
| 128 | // test objects for intersection
|
---|
| 129 | #ifdef _DEBUGKTB
|
---|
| 130 | cout << "Leaf " << endl;
|
---|
| 131 | depth++;
|
---|
| 132 | #endif
|
---|
| 133 | #ifdef _DEBUGKTB
|
---|
| 134 | DEBUG << "currNode = " << currNode << " entp.t = " << entp->t
|
---|
| 135 | << " extp.t = " << extp->t << endl;
|
---|
| 136 | #endif
|
---|
| 137 | if (!IsEmptyLeaf_(currNode)) {
|
---|
| 138 | #ifdef _DEBUGKTB
|
---|
| 139 | cout << "Full leaf at depth= " << depth << endl;
|
---|
| 140 | #endif
|
---|
| 141 |
|
---|
| 142 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 143 | fullLeavesTraversed++;
|
---|
| 144 | #endif // __TRAVERSAL_STATISTICS
|
---|
| 145 | // test the objects in the full leaf against the ray
|
---|
| 146 |
|
---|
[2592] | 147 | SimpleRay::IntersectionRes[0].maxt =
|
---|
| 148 | stack3[index].tmax + Limits::Small;
|
---|
[2582] | 149 | #if 0
|
---|
| 150 | // using subroutine
|
---|
| 151 | if (TestFullLeaf(ray, currNode))
|
---|
| 152 | #else
|
---|
| 153 | // Avoiding function call by copying the code
|
---|
| 154 | const ObjectContainer * const list = GetObjList(currNode);
|
---|
| 155 | int intersected = 0;
|
---|
| 156 | // iterate the whole list and find out the nearest intersection
|
---|
| 157 | ObjectContainer::const_iterator sc_end = list->end();
|
---|
| 158 | for (ObjectContainer::const_iterator sc = list->begin(); sc != sc_end; sc++) {
|
---|
| 159 | // if the intersection realy lies in the node
|
---|
| 160 | intersected += ((*sc)->CastSimpleRay(ray));
|
---|
| 161 | } // for all objects
|
---|
| 162 | if (intersected)
|
---|
| 163 | #endif
|
---|
| 164 | {
|
---|
| 165 | #ifdef _DEBUGKTB
|
---|
| 166 | cout << "Full leaf HIT " << endl;
|
---|
| 167 | #endif
|
---|
| 168 |
|
---|
| 169 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 170 | _allNodesTraversed += allNodesTraversed;
|
---|
| 171 | _fullLeavesTraversed += fullLeavesTraversed;
|
---|
| 172 | _emptyLeavesTraversed += emptyLeavesTraversed;
|
---|
| 173 | #endif // __TRAVERSAL_STATISTICS
|
---|
| 174 |
|
---|
| 175 | // signed distance should be already set in TestFullLeaf
|
---|
| 176 | // the first object intersected was found
|
---|
| 177 | return 1;
|
---|
| 178 | }
|
---|
| 179 | } // full leaf
|
---|
| 180 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 181 | else {
|
---|
| 182 | #ifdef _DEBUGKTB
|
---|
| 183 | cout << "Empty leaf at depth= " << depth << endl;
|
---|
| 184 | #endif
|
---|
| 185 | emptyLeavesTraversed++;
|
---|
| 186 | }
|
---|
| 187 | #endif // __TRAVERSAL_STATISTICS
|
---|
| 188 |
|
---|
| 189 | #ifdef _DEBUGKTB
|
---|
| 190 | cout << "Pop the node" << endl;
|
---|
| 191 | #endif
|
---|
| 192 |
|
---|
| 193 | // pop farChild from the stack
|
---|
| 194 | // restore the current values
|
---|
| 195 | index--;
|
---|
| 196 | continue;
|
---|
| 197 | }
|
---|
| 198 | else {
|
---|
| 199 | assert(nodeType == CKTBAxes::EE_Link);
|
---|
| 200 | #ifdef _DEBUGKTB
|
---|
| 201 | cout << "Link " << endl;
|
---|
| 202 | #endif
|
---|
| 203 | // cout << "Link node was accessed" << endl;
|
---|
[2592] | 204 | currNode = GetLinkNode(currNode);
|
---|
| 205 | goto CONTINUE_LINK;
|
---|
[2582] | 206 | }
|
---|
| 207 | }
|
---|
| 208 | } // while current node is not the leaf
|
---|
| 209 |
|
---|
| 210 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 211 | _allNodesTraversed += allNodesTraversed;
|
---|
| 212 | _fullLeavesTraversed += fullLeavesTraversed;
|
---|
| 213 | _emptyLeavesTraversed += emptyLeavesTraversed;
|
---|
| 214 | #endif // __TRAVERSAL_STATISTICS
|
---|
| 215 |
|
---|
| 216 | // no objects found along the ray path
|
---|
| 217 | return 0;
|
---|
| 218 | } // FindNearestI - single ray
|
---|
| 219 |
|
---|
[2592] | 220 |
|
---|
| 221 | // Shooting a single ray without SSE with prespecified box of the scene, assuming
|
---|
| 222 | // to be contained in the scene box!!!
|
---|
[2582] | 223 | int
|
---|
[2602] | 224 | CKTBTraversal::FindNearestI(const SimpleRay &oray, const AxisAlignedBox3 &localbox)
|
---|
[2582] | 225 | {
|
---|
| 226 | #if 0
|
---|
| 227 | static int counter = 0;
|
---|
| 228 | counter++;
|
---|
| 229 | bool debug = false;
|
---|
| 230 | if (counter == 530) {
|
---|
| 231 | debug = true;
|
---|
| 232 | cout << "COUNTER = " << counter << endl;
|
---|
| 233 | cout << "DEBUG starts" << endl;
|
---|
| 234 | }
|
---|
| 235 | #endif
|
---|
| 236 |
|
---|
| 237 | // passing through parameters
|
---|
| 238 | float tmin, tmax;
|
---|
[2592] | 239 | SimpleRay::IntersectionRes[0].intersectable = 0;
|
---|
[2602] | 240 | SimpleRay ray(oray.mOrigin, oray.mDirection, 0, 0.f, 0);
|
---|
[2582] | 241 |
|
---|
| 242 | // test if the whole CKTB tree is missed by the input ray
|
---|
| 243 | if ( (!root) ||
|
---|
| 244 | (!localbox.ComputeMinMaxT(ray.mOrigin, ray.mDirection, &tmin, &tmax)) ||
|
---|
| 245 | (tmax <= tmin) ||
|
---|
| 246 | (tmax <= 0.f) ) {
|
---|
| 247 | return 0; // no object can be intersected
|
---|
| 248 | }
|
---|
[2602] | 249 | float tminOffset = 0.f;
|
---|
[2582] | 250 |
|
---|
| 251 | //#define _DEBUGKTB
|
---|
| 252 | #ifdef _DEBUGKTB
|
---|
| 253 | int ib = 0;
|
---|
| 254 | int depth = 0;
|
---|
| 255 | #endif
|
---|
| 256 |
|
---|
| 257 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 258 | int allNodesTraversed = 0L;
|
---|
| 259 | int fullLeavesTraversed = 0L;
|
---|
| 260 | int emptyLeavesTraversed = 0L;
|
---|
| 261 | #endif // __TRAVERSAL_STATISTICS
|
---|
| 262 |
|
---|
| 263 | Vector3 invertedDir;
|
---|
[2592] | 264 | invertedDir.x = 1.0f / (ray.mDirection.x - 1e-25f);
|
---|
| 265 | invertedDir.y = 1.0f / (ray.mDirection.y - 1e-25f);
|
---|
| 266 | invertedDir.z = 1.0f / (ray.mDirection.z - 1e-25f);
|
---|
[2582] | 267 |
|
---|
| 268 | // start from the root node
|
---|
| 269 | if (tmin < 0.f)
|
---|
| 270 | tmin = 0.f;
|
---|
[2602] | 271 | else {
|
---|
| 272 | // Here the origin of the ray is always zero - it starts
|
---|
| 273 | // at the box face!!
|
---|
| 274 | tminOffset = tmin;
|
---|
| 275 | tmin = 0.f;
|
---|
| 276 | tmax -= tminOffset;
|
---|
| 277 | ray.mOrigin += ray.mDirection * tminOffset;
|
---|
| 278 | }
|
---|
[2582] | 279 |
|
---|
| 280 | int index = 1;
|
---|
| 281 | stack3[1].nodep = root;
|
---|
| 282 | stack3[1].tmax = tmax;
|
---|
| 283 | tmax = tmin;
|
---|
| 284 | SKTBNodeT * childNodes[2];
|
---|
| 285 | int RayDirs[3];
|
---|
| 286 | RayDirs[0] = ray.mDirection.x < 0.f ? 1 : 0;
|
---|
| 287 | RayDirs[1] = ray.mDirection.y < 0.f ? 1 : 0;
|
---|
| 288 | RayDirs[2] = ray.mDirection.z < 0.f ? 1 : 0;
|
---|
| 289 |
|
---|
| 290 | // we have to check the node
|
---|
| 291 | // current node is not the leaf, empty leaves are NULL pointers
|
---|
| 292 | while (index) {
|
---|
| 293 | register SKTBNodeT *currNode = stack3[index].nodep;
|
---|
| 294 | tmin = tmax;
|
---|
| 295 | tmax = stack3[index].tmax;
|
---|
| 296 | #if 0
|
---|
| 297 | if (debug) {
|
---|
| 298 | cout << "node = " << (void*)currNode
|
---|
| 299 | << " tmin = " << tmin << " tmax = " << tmax
|
---|
| 300 | << endl;
|
---|
| 301 | }
|
---|
| 302 | #endif
|
---|
[2592] | 303 |
|
---|
| 304 | CONTINUE_LINK:
|
---|
[2582] | 305 | assert(tmin <= tmax);
|
---|
[2592] | 306 |
|
---|
[2582] | 307 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 308 | allNodesTraversed++;
|
---|
| 309 | #endif // __TRAVERSAL_STATISTICS
|
---|
[2592] | 310 |
|
---|
[2582] | 311 | register const int nodeType = GetNodeType(currNode);
|
---|
| 312 | if (nodeType < CKTBAxes::EE_Leaf) {
|
---|
| 313 | float tval = (GetSplitValue(currNode) - ray.mOrigin[nodeType]);
|
---|
| 314 | tval *= invertedDir[nodeType];
|
---|
| 315 | SKTBNodeT *near, *far;
|
---|
| 316 | childNodes[0] = GetLeft(currNode);
|
---|
| 317 | childNodes[1] = GetRight(currNode);
|
---|
| 318 | int rayDir = RayDirs[nodeType];
|
---|
| 319 | near = childNodes[rayDir];
|
---|
| 320 | far = childNodes[rayDir ^ 0x1];
|
---|
| 321 |
|
---|
| 322 | stack3[index].nodep = far;
|
---|
| 323 | // stack3[index].tmax = tmax; // not necessary, this is already there !
|
---|
| 324 | // int c = tval < tmax ? 1 : 0;
|
---|
| 325 | index += tval < tmax ? 1 : 0;
|
---|
| 326 | stack3[index].nodep = near;
|
---|
| 327 | stack3[index].tmax = Min(tval, tmax);
|
---|
| 328 | tmax = tmin;
|
---|
| 329 | // int d = tval < tmin ? -1 : 0;
|
---|
| 330 | index += tval < tmin ? -1 : 0;
|
---|
| 331 | }
|
---|
| 332 | else {
|
---|
| 333 | if (nodeType == CKTBAxes::EE_Leaf) {
|
---|
| 334 | // test objects for intersection
|
---|
| 335 | #ifdef _DEBUGKTB
|
---|
| 336 | cout << "Leaf " << endl;
|
---|
| 337 | depth++;
|
---|
| 338 | #endif
|
---|
| 339 | #ifdef _DEBUGKTB
|
---|
| 340 | DEBUG << "currNode = " << currNode << " entp.t = " << entp->t
|
---|
| 341 | << " extp.t = " << extp->t << endl;
|
---|
| 342 | #endif
|
---|
| 343 | if (!IsEmptyLeaf_(currNode)) {
|
---|
| 344 | #ifdef _DEBUGKTB
|
---|
| 345 | cout << "Full leaf at depth= " << depth << endl;
|
---|
| 346 | #endif
|
---|
| 347 |
|
---|
| 348 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 349 | fullLeavesTraversed++;
|
---|
| 350 | #endif // __TRAVERSAL_STATISTICS
|
---|
| 351 | // test the objects in the full leaf against the ray
|
---|
| 352 |
|
---|
[2592] | 353 | SimpleRay::IntersectionRes[0].maxt =
|
---|
| 354 | stack3[index].tmax + Limits::Small;
|
---|
[2582] | 355 | #if 0
|
---|
| 356 | // using subroutine
|
---|
| 357 | if (TestFullLeaf(ray, currNode))
|
---|
| 358 | #else
|
---|
| 359 | // Avoiding function call by copying the code
|
---|
| 360 | const ObjectContainer * const list = GetObjList(currNode);
|
---|
| 361 | int intersected = 0;
|
---|
| 362 | // iterate the whole list and find out the nearest intersection
|
---|
| 363 | ObjectContainer::const_iterator sc_end = list->end();
|
---|
| 364 | for (ObjectContainer::const_iterator sc = list->begin(); sc != sc_end; sc++) {
|
---|
| 365 | // if the intersection realy lies in the node
|
---|
| 366 | intersected += ((*sc)->CastSimpleRay(ray));
|
---|
| 367 | } // for all objects
|
---|
| 368 | if (intersected)
|
---|
| 369 | #endif
|
---|
| 370 | {
|
---|
| 371 | #ifdef _DEBUGKTB
|
---|
| 372 | cout << "Full leaf HIT " << endl;
|
---|
| 373 | #endif
|
---|
| 374 |
|
---|
| 375 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 376 | _allNodesTraversed += allNodesTraversed;
|
---|
| 377 | _fullLeavesTraversed += fullLeavesTraversed;
|
---|
| 378 | _emptyLeavesTraversed += emptyLeavesTraversed;
|
---|
| 379 | #endif // __TRAVERSAL_STATISTICS
|
---|
[2602] | 380 |
|
---|
| 381 | // We have to add the distance from the original ray origin
|
---|
| 382 | SimpleRay::IntersectionRes[0].tdist += tminOffset;
|
---|
[2582] | 383 |
|
---|
| 384 | // signed distance should be already set in TestFullLeaf
|
---|
| 385 | // the first object intersected was found
|
---|
| 386 | return 1;
|
---|
| 387 | }
|
---|
| 388 | } // full leaf
|
---|
| 389 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 390 | else {
|
---|
| 391 | #ifdef _DEBUGKTB
|
---|
| 392 | cout << "Empty leaf at depth= " << depth << endl;
|
---|
| 393 | #endif
|
---|
| 394 | emptyLeavesTraversed++;
|
---|
| 395 | }
|
---|
| 396 | #endif // __TRAVERSAL_STATISTICS
|
---|
| 397 |
|
---|
| 398 | #ifdef _DEBUGKTB
|
---|
| 399 | cout << "Pop the node" << endl;
|
---|
| 400 | #endif
|
---|
| 401 |
|
---|
| 402 | // pop farChild from the stack
|
---|
| 403 | // restore the current values
|
---|
| 404 | index--;
|
---|
| 405 | continue;
|
---|
| 406 | }
|
---|
| 407 | else {
|
---|
| 408 | assert(nodeType == CKTBAxes::EE_Link);
|
---|
| 409 | #ifdef _DEBUGKTB
|
---|
| 410 | cout << "Link " << endl;
|
---|
| 411 | #endif
|
---|
| 412 | // cout << "Link node was accessed" << endl;
|
---|
[2592] | 413 | currNode = GetLinkNode(currNode);
|
---|
| 414 | goto CONTINUE_LINK;
|
---|
[2582] | 415 | }
|
---|
| 416 | }
|
---|
| 417 | } // while current node is not the leaf
|
---|
| 418 |
|
---|
| 419 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 420 | _allNodesTraversed += allNodesTraversed;
|
---|
| 421 | _fullLeavesTraversed += fullLeavesTraversed;
|
---|
| 422 | _emptyLeavesTraversed += emptyLeavesTraversed;
|
---|
| 423 | #endif // __TRAVERSAL_STATISTICS
|
---|
| 424 |
|
---|
| 425 | // no objects found along the ray path
|
---|
| 426 | return 0;
|
---|
| 427 | } // FindNearestI - single ray
|
---|
| 428 |
|
---|
| 429 |
|
---|
| 430 | // Reasonably fast - about 101,500 rays per second for single dir!
|
---|
[2592] | 431 | // It allows fast switching context from one ray to the next ray so it is
|
---|
[2582] | 432 | // virtually independent of memory latency !
|
---|
| 433 | int
|
---|
[2592] | 434 | CKTBTraversal::FindNearestI_16oneDirNoSSE(SimpleRayContainer &rays, int offset)
|
---|
[2582] | 435 | {
|
---|
| 436 | // passing through parameters
|
---|
| 437 | int cntRays = 0;
|
---|
| 438 | if (!root)
|
---|
| 439 | return 0;
|
---|
| 440 |
|
---|
| 441 | // The auxiliary variables to be precomputed
|
---|
| 442 | static float invertedDir[cntMaxRays * 4];
|
---|
| 443 | static float rayOrig[cntMaxRays * 4];
|
---|
| 444 | static int rayDirs[cntMaxRays * 4];
|
---|
| 445 | static int indexRay[cntMaxRays];
|
---|
| 446 | static int indexArray[cntMaxRays];
|
---|
| 447 | static int indexStack[cntMaxRays];
|
---|
| 448 | const int LOG2_MAX_HEIGHT = 5;
|
---|
| 449 | const int MAX_HEIGHT = 1 << LOG2_MAX_HEIGHT;
|
---|
| 450 | assert(MAX_HEIGHT == 32);
|
---|
| 451 | static struct SStackElem3 stackA[cntMaxRays * MAX_HEIGHT];
|
---|
| 452 | static float tmaxArray[cntMaxRays];
|
---|
| 453 | int cntHits = 0;
|
---|
| 454 |
|
---|
| 455 | float tmin, tmax;
|
---|
| 456 | for (int i = 0; i < cntMaxRays; i++) {
|
---|
[2592] | 457 | // Setting zero intersection as original result
|
---|
| 458 | SimpleRay::IntersectionRes[i+rayOffset].intersectable = 0;
|
---|
| 459 | // test if the whole CKTB tree is missed by the input ray
|
---|
[2582] | 460 | if ((!bbox.ComputeMinMaxT(rays[i+offset].mOrigin,
|
---|
| 461 | rays[i+offset].mDirection,
|
---|
| 462 | &tmin, &tmax)) ||
|
---|
| 463 | (tmax <= tmin) ||
|
---|
| 464 | (tmax <= 0.f) ) {
|
---|
| 465 | }
|
---|
| 466 | else {
|
---|
| 467 | int indexR = (cntRays << 2);
|
---|
| 468 | rayOrig[indexR + 0] = rays[i+offset].mOrigin.x;
|
---|
| 469 | rayOrig[indexR + 1] = rays[i+offset].mOrigin.y;
|
---|
| 470 | rayOrig[indexR + 2] = rays[i+offset].mOrigin.z;
|
---|
| 471 | //rayOrig[indexR + 3] = 0.f;
|
---|
[2592] | 472 | invertedDir[indexR + 0] = 1.0f / (rays[i+offset].mDirection.x - 1e-25f);
|
---|
| 473 | invertedDir[indexR + 1] = 1.0f / (rays[i+offset].mDirection.y - 1e-25f);
|
---|
| 474 | invertedDir[indexR + 2] = 1.0f / (rays[i+offset].mDirection.z - 1e-25f);
|
---|
[2582] | 475 | //invertedDir[indexR + 2] = 0.f;
|
---|
| 476 | rayDirs[indexR + 0] = rays[i+offset].mDirection.x < 0.f ? 1 : 0;
|
---|
| 477 | rayDirs[indexR + 1] = rays[i+offset].mDirection.y < 0.f ? 1 : 0;
|
---|
| 478 | rayDirs[indexR + 2] = rays[i+offset].mDirection.z < 0.f ? 1 : 0;
|
---|
| 479 | //rayDirs[indexR + 3] = 0;
|
---|
| 480 | indexRay[cntRays] = i; // the index to the ray
|
---|
| 481 | indexArray[cntRays] = cntRays; // the index to the array
|
---|
| 482 | int indexS = (cntRays << LOG2_MAX_HEIGHT) + 1;
|
---|
| 483 | indexStack[cntRays] = indexS; // the index in the stack
|
---|
| 484 | stackA[indexS].nodep = root; // we start from the root
|
---|
| 485 | stackA[indexS].tmax = tmax; // maximum distance
|
---|
| 486 | if (tmin < 0.f) tmin = 0.f;
|
---|
| 487 | tmaxArray[cntRays] = tmin;
|
---|
| 488 | cntRays++;
|
---|
| 489 | }
|
---|
| 490 | }
|
---|
| 491 |
|
---|
| 492 | //#define _DEBUGKTB
|
---|
| 493 | #ifdef _DEBUGKTB
|
---|
| 494 | int ib = 0;
|
---|
| 495 | int depth = 0;
|
---|
| 496 | #endif
|
---|
| 497 |
|
---|
| 498 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 499 | int allNodesTraversed = 0L;
|
---|
| 500 | int fullLeavesTraversed = 0L;
|
---|
| 501 | int emptyLeavesTraversed = 0L;
|
---|
| 502 | #endif // __TRAVERSAL_STATISTICS
|
---|
| 503 |
|
---|
| 504 | SKTBNodeT * childNodes[2];
|
---|
| 505 |
|
---|
| 506 | #define PREF_DEFAULT _MM_HINT_T0
|
---|
| 507 |
|
---|
| 508 | // we have to check the node
|
---|
| 509 | // current node is not the leaf, empty leaves are NULL pointers
|
---|
| 510 | while (cntRays) {
|
---|
| 511 | // we assume that all the nodes are interior nodes
|
---|
| 512 | for (int i = 0; i < cntRays; i++) {
|
---|
| 513 | // which indices to array should be used
|
---|
| 514 | int indexA = indexArray[i];
|
---|
| 515 | float tmin = tmaxArray[indexA];
|
---|
| 516 |
|
---|
| 517 | // the stack indexing is here
|
---|
| 518 | int indexSA = indexStack[indexA];
|
---|
| 519 | SKTBNodeT *currNode = stackA[indexSA].nodep;
|
---|
| 520 |
|
---|
| 521 | #if 0
|
---|
| 522 | if (debug) {
|
---|
| 523 | cout << "node = " << (void*)currNode
|
---|
| 524 | << " tmin = " << tmin << " tmax = " << tmax
|
---|
| 525 | << endl;
|
---|
| 526 | }
|
---|
| 527 | #endif
|
---|
| 528 |
|
---|
| 529 | #if 0
|
---|
| 530 | if (tmin > tmax) {
|
---|
| 531 | cout << "PROBLEM tmin = " << tmin << " tmax = " << tmax;
|
---|
| 532 | cout << endl;
|
---|
| 533 | }
|
---|
| 534 | #endif
|
---|
| 535 |
|
---|
| 536 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 537 | allNodesTraversed++;
|
---|
| 538 | #endif // __TRAVERSAL_STATISTICS
|
---|
| 539 | const unsigned int nodeType = (GetNodeType(currNode)) & 0x7;
|
---|
| 540 | if (nodeType < CKTBAxes::EE_Leaf) {
|
---|
| 541 | int indexRayOD = (indexA << 2) + nodeType;
|
---|
| 542 | float tval = (GetSplitValue(currNode) - rayOrig[indexRayOD])
|
---|
| 543 | * invertedDir[indexRayOD];
|
---|
| 544 | SKTBNodeT *near, *far;
|
---|
| 545 | childNodes[0] = GetLeft(currNode);
|
---|
| 546 | childNodes[1] = GetRight(currNode);
|
---|
| 547 | int rayDir = rayDirs[indexRayOD];
|
---|
| 548 | near = childNodes[rayDir];
|
---|
| 549 | far = childNodes[rayDir ^ 0x1];
|
---|
| 550 |
|
---|
| 551 | stackA[indexSA].nodep = far; // store far node
|
---|
| 552 | //stackA[indexSA].tmax = tmax; // with correct dist - the same as before
|
---|
| 553 | float tmax = tmaxArray[indexA] = stackA[indexSA].tmax;
|
---|
| 554 | int c = tval < tmax ? 1 : 0;
|
---|
| 555 | indexSA += c;
|
---|
| 556 | stackA[indexSA].nodep = near; // store near node
|
---|
| 557 | stackA[indexSA].tmax = Min(tval, tmax); // with correct dist
|
---|
| 558 | int d = tval < tmin ? 1 : 0;
|
---|
| 559 | indexSA -= d;
|
---|
| 560 | // This is prefetching - so the next time we have it
|
---|
| 561 | // in the cache !
|
---|
| 562 | GPREFETCH(stackA[indexSA].nodep, PREF_DEFAULT);
|
---|
| 563 | // store tmax and index to the stack
|
---|
| 564 | indexStack[indexA] = indexSA;
|
---|
| 565 | tmaxArray[indexA] = tmin;
|
---|
| 566 | }
|
---|
| 567 | else {
|
---|
| 568 | if (nodeType == CKTBAxes::EE_Leaf) {
|
---|
| 569 | // test objects for intersection
|
---|
| 570 | #ifdef _DEBUGKTB
|
---|
| 571 | cout << "Leaf " << endl;
|
---|
| 572 | depth++;
|
---|
| 573 | #endif
|
---|
| 574 | #ifdef _DEBUGKTB
|
---|
| 575 | DEBUG << "currNode = " << currNode << " entp.t = " << entp->t
|
---|
| 576 | << " extp.t = " << extp->t << endl;
|
---|
| 577 | #endif
|
---|
| 578 | float tmax = tmaxArray[indexA] = stackA[indexSA].tmax;
|
---|
| 579 | if (!IsEmptyLeaf_(currNode)) {
|
---|
| 580 | #ifdef _DEBUGKTB
|
---|
| 581 | cout << "Full leaf at depth= " << depth << endl;
|
---|
| 582 | #endif
|
---|
| 583 |
|
---|
| 584 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 585 | fullLeavesTraversed++;
|
---|
| 586 | #endif // __TRAVERSAL_STATISTICS
|
---|
| 587 | // test the objects in the full leaf against the ray
|
---|
| 588 |
|
---|
| 589 | // which ray is processed
|
---|
| 590 | int indexR = indexRay[indexA];
|
---|
[2592] | 591 | SimpleRay::IntersectionRes[indexR + rayOffset].maxt =
|
---|
| 592 | tmax + Limits::Small;
|
---|
[2582] | 593 | if (TestFullLeaf(rays[indexR+offset], currNode, indexR)) {
|
---|
| 594 |
|
---|
| 595 | // we remove the ray from the calculation
|
---|
| 596 | indexArray[i] = indexArray[cntRays-1];
|
---|
| 597 | cntRays--; // we decrease the number of rays
|
---|
| 598 | cntHits++;
|
---|
| 599 | #ifdef _DEBUGKTB
|
---|
| 600 | cout << "Full leaf HIT " << endl;
|
---|
| 601 | #endif
|
---|
| 602 |
|
---|
| 603 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 604 | _allNodesTraversed += allNodesTraversed;
|
---|
| 605 | _fullLeavesTraversed += fullLeavesTraversed;
|
---|
| 606 | _emptyLeavesTraversed += emptyLeavesTraversed;
|
---|
| 607 | #endif // __TRAVERSAL_STATISTICS
|
---|
| 608 |
|
---|
| 609 | // signed distance should be already set in TestFullLeaf
|
---|
| 610 | // the first object intersected was found
|
---|
| 611 | continue;
|
---|
| 612 | }
|
---|
| 613 | } // full leaf
|
---|
| 614 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 615 | else {
|
---|
| 616 | #ifdef _DEBUGKTB
|
---|
| 617 | cout << "Empty leaf at depth= " << depth << endl;
|
---|
| 618 | #endif
|
---|
| 619 | emptyLeavesTraversed++;
|
---|
| 620 | }
|
---|
| 621 | #endif // __TRAVERSAL_STATISTICS
|
---|
| 622 |
|
---|
| 623 | #ifdef _DEBUGKTB
|
---|
| 624 | cout << "Pop the node" << endl;
|
---|
| 625 | #endif
|
---|
| 626 |
|
---|
| 627 | // pop farChild from the stack
|
---|
| 628 | // restore the current values
|
---|
| 629 | --indexSA;
|
---|
| 630 | // This is bits 0,1,2,3,4,5 - the stack depth = 32 !
|
---|
| 631 | if ( (indexSA & 0x1f) == 0) {
|
---|
| 632 | // we remove the ray from the calculation
|
---|
| 633 | indexArray[i] = indexArray[cntRays-1];
|
---|
| 634 | cntRays--; // we decrease the number of rays
|
---|
| 635 | }
|
---|
| 636 | else {
|
---|
| 637 | indexStack[indexA] = indexSA;
|
---|
| 638 | // we prefetch the data to be accessible
|
---|
| 639 | // the next time
|
---|
| 640 | GPREFETCH(stackA[indexSA].nodep, PREF_DEFAULT);
|
---|
| 641 | }
|
---|
| 642 | continue;
|
---|
| 643 | }
|
---|
| 644 | else {
|
---|
| 645 | assert(nodeType == CKTBAxes::EE_Link);
|
---|
| 646 | #ifdef _DEBUGKTB
|
---|
| 647 | cout << "Link " << endl;
|
---|
| 648 | #endif
|
---|
| 649 | stackA[indexSA].nodep = GetLinkNode(currNode);
|
---|
[2592] | 650 | GPREFETCH(stackA[indexSA].nodep, PREF_DEFAULT);
|
---|
[2582] | 651 | // cout << "Link node was accessed" << endl;
|
---|
| 652 | continue;
|
---|
| 653 | }
|
---|
| 654 | } // empty leaf or link
|
---|
| 655 | } // for all active rays
|
---|
| 656 | } // while cntRays
|
---|
| 657 |
|
---|
| 658 | #ifdef __TRAVERSAL_STATISTICS
|
---|
| 659 | _allNodesTraversed += allNodesTraversed;
|
---|
| 660 | _fullLeavesTraversed += fullLeavesTraversed;
|
---|
| 661 | _emptyLeavesTraversed += emptyLeavesTraversed;
|
---|
| 662 | #endif // __TRAVERSAL_STATISTICS
|
---|
| 663 |
|
---|
| 664 | // no objects found along the ray path
|
---|
| 665 | return cntHits;
|
---|
| 666 | }
|
---|
| 667 |
|
---|
| 668 | #endif // TRV00F
|
---|
| 669 |
|
---|
| 670 | } // namespace
|
---|
| 671 |
|
---|