src/main/java/eu/svjatoslav/sixth/e3d/renderer/octree/OctreeVolume.java

   1 /*
   2  * Sixth 3D engine. Author: Svjatoslav Agejenko.
   3  * This project is released under Creative Commons Zero (CC0) license.
   4  */
   5 package eu.svjatoslav.sixth.e3d.renderer.octree;
   6
   7 import eu.svjatoslav.sixth.e3d.geometry.Point3D;
   8 import eu.svjatoslav.sixth.e3d.renderer.octree.raytracer.Ray;
   9 import eu.svjatoslav.sixth.e3d.renderer.raster.Color;
  10
  11 /**
  12  * <pre>
  13  * There are 3 cell types:
  14  *
  15  *      UNUSED
  16  *
  17  *      SOLID
  18  *          contains:
  19  *              original color
  20  *              visible color, after being illuminated by nearby light sources
  21  *
  22  *      CLUSTER
  23  *          contains pointers to 8 sub cells
  24  * </pre>
  25  */
  26
  27 public class OctreeVolume {
  28
  29     // cell is not hit by the ray
  30     public static final int TRACE_NO_HIT = -1;
  31
  32     // solid cell (contains color and illumination)
  33     private static final int CELL_STATE_SOLID = -2;
  34
  35     // unused cell
  36     private static final int CELL_STATE_UNUSED = -1;
  37
  38     public int[] ce1;
  39     public int[] ce2;
  40     public int[] ce3;
  41     public int[] ce4;
  42     public int[] ce5;
  43     public int[] ce6;
  44     public int[] ce7;
  45     public int[] ce8;
  46     public int cellAllocationPointer = 0;
  47     public int usedCellsCount = 0;
  48     public int masterCellSize;
  49
  50     public OctreeVolume() {
  51         initWorld(1500000, 256 * 64);
  52     }
  53
  54     public void breakSolidCell(final int pointer) {
  55         final int color = getCellColor(pointer);
  56         final int illumination = getCellIllumination(pointer);
  57
  58         ce1[pointer] = makeNewCell(color, illumination);
  59         ce2[pointer] = makeNewCell(color, illumination);
  60         ce3[pointer] = makeNewCell(color, illumination);
  61         ce4[pointer] = makeNewCell(color, illumination);
  62         ce5[pointer] = makeNewCell(color, illumination);
  63         ce6[pointer] = makeNewCell(color, illumination);
  64         ce7[pointer] = makeNewCell(color, illumination);
  65         ce8[pointer] = makeNewCell(color, illumination);
  66     }
  67
  68     public void clearCell(final int pointer) {
  69         ce1[pointer] = 0;
  70         ce2[pointer] = 0;
  71         ce3[pointer] = 0;
  72         ce4[pointer] = 0;
  73
  74         ce5[pointer] = 0;
  75         ce6[pointer] = 0;
  76         ce7[pointer] = 0;
  77         ce8[pointer] = 0;
  78     }
  79
  80     public void deleteCell(final int cellPointer) {
  81         clearCell(cellPointer);
  82         ce1[cellPointer] = CELL_STATE_UNUSED;
  83         usedCellsCount--;
  84     }
  85
  86     public int doesIntersect(final int cubeX, final int cubeY, final int cubeZ,
  87                              final int cubeSize, final Ray r) {
  88
  89         // ray starts inside the cube
  90         if ((cubeX - cubeSize) < r.origin.x)
  91             if ((cubeX + cubeSize) > r.origin.x)
  92                 if ((cubeY - cubeSize) < r.origin.y)
  93                     if ((cubeY + cubeSize) > r.origin.y)
  94                         if ((cubeZ - cubeSize) < r.origin.z)
  95                             if ((cubeZ + cubeSize) > r.origin.z) {
  96                                 r.hitPoint = r.origin.clone();
  97                                 return 1;
  98                             }
  99         // back face
 100         if (r.direction.z > 0)
 101             if ((cubeZ - cubeSize) > r.origin.z) {
 102                 final double mult = ((cubeZ - cubeSize) - r.origin.z) / r.direction.z;
 103                 final double hitX = (r.direction.x * mult) + r.origin.x;
 104                 if ((cubeX - cubeSize) < hitX)
 105                     if ((cubeX + cubeSize) > hitX) {
 106                         final double hitY = (r.direction.y * mult) + r.origin.y;
 107                         if ((cubeY - cubeSize) < hitY)
 108                             if ((cubeY + cubeSize) > hitY) {
 109                                 r.hitPoint = new Point3D(hitX, hitY, cubeZ
 110                                         - cubeSize);
 111                                 return 2;
 112                             }
 113                     }
 114             }
 115
 116         // up face
 117         if (r.direction.y > 0)
 118             if ((cubeY - cubeSize) > r.origin.y) {
 119                 final double mult = ((cubeY - cubeSize) - r.origin.y) / r.direction.y;
 120                 final double hitX = (r.direction.x * mult) + r.origin.x;
 121                 if ((cubeX - cubeSize) < hitX)
 122                     if ((cubeX + cubeSize) > hitX) {
 123                         final double hitZ = (r.direction.z * mult) + r.origin.z;
 124                         if ((cubeZ - cubeSize) < hitZ)
 125                             if ((cubeZ + cubeSize) > hitZ) {
 126                                 r.hitPoint = new Point3D(hitX, cubeY - cubeSize,
 127                                         hitZ);
 128                                 return 3;
 129                             }
 130                     }
 131             }
 132
 133         // left face
 134         if (r.direction.x > 0)
 135             if ((cubeX - cubeSize) > r.origin.x) {
 136                 final double mult = ((cubeX - cubeSize) - r.origin.x) / r.direction.x;
 137                 final double hitY = (r.direction.y * mult) + r.origin.y;
 138                 if ((cubeY - cubeSize) < hitY)
 139                     if ((cubeY + cubeSize) > hitY) {
 140                         final double hitZ = (r.direction.z * mult) + r.origin.z;
 141                         if ((cubeZ - cubeSize) < hitZ)
 142                             if ((cubeZ + cubeSize) > hitZ) {
 143                                 r.hitPoint = new Point3D(cubeX - cubeSize, hitY,
 144                                         hitZ);
 145                                 return 4;
 146                             }
 147                     }
 148             }
 149
 150         // front face
 151         if (r.direction.z < 0)
 152             if ((cubeZ + cubeSize) < r.origin.z) {
 153                 final double mult = ((cubeZ + cubeSize) - r.origin.z) / r.direction.z;
 154                 final double hitX = (r.direction.x * mult) + r.origin.x;
 155                 if ((cubeX - cubeSize) < hitX)
 156                     if ((cubeX + cubeSize) > hitX) {
 157                         final double hitY = (r.direction.y * mult) + r.origin.y;
 158                         if ((cubeY - cubeSize) < hitY)
 159                             if ((cubeY + cubeSize) > hitY) {
 160                                 r.hitPoint = new Point3D(hitX, hitY, cubeZ
 161                                         + cubeSize);
 162                                 return 5;
 163                             }
 164                     }
 165             }
 166
 167         // down face
 168         if (r.direction.y < 0)
 169             if ((cubeY + cubeSize) < r.origin.y) {
 170                 final double mult = ((cubeY + cubeSize) - r.origin.y) / r.direction.y;
 171                 final double hitX = (r.direction.x * mult) + r.origin.x;
 172                 if ((cubeX - cubeSize) < hitX)
 173                     if ((cubeX + cubeSize) > hitX) {
 174                         final double hitZ = (r.direction.z * mult) + r.origin.z;
 175                         if ((cubeZ - cubeSize) < hitZ)
 176                             if ((cubeZ + cubeSize) > hitZ) {
 177                                 r.hitPoint = new Point3D(hitX, cubeY + cubeSize,
 178                                         hitZ);
 179                                 return 6;
 180                             }
 181                     }
 182             }
 183
 184         // right face
 185         if (r.direction.x < 0)
 186             if ((cubeX + cubeSize) < r.origin.x) {
 187                 final double mult = ((cubeX + cubeSize) - r.origin.x) / r.direction.x;
 188                 final double hitY = (r.direction.y * mult) + r.origin.y;
 189                 if ((cubeY - cubeSize) < hitY)
 190                     if ((cubeY + cubeSize) > hitY) {
 191                         final double hitZ = (r.direction.z * mult) + r.origin.z;
 192                         if ((cubeZ - cubeSize) < hitZ)
 193                             if ((cubeZ + cubeSize) > hitZ) {
 194                                 r.hitPoint = new Point3D(cubeX + cubeSize, hitY,
 195                                         hitZ);
 196                                 return 7;
 197                             }
 198                     }
 199             }
 200         return 0;
 201     }
 202
 203     /**
 204      * Fill 3D rectangle.
 205      */
 206     public void fillRect3D(int x1, int y1, int z1, int x2, int y2, int z2,
 207                            final Color color) {
 208         int t;
 209         if (x1 > x2) {
 210             t = x1;
 211             x1 = x2;
 212             x2 = t;
 213         }
 214
 215         if (y1 > y2) {
 216             t = y1;
 217             y1 = y2;
 218             y2 = t;
 219         }
 220
 221         if (z1 > z2) {
 222             t = z1;
 223             z1 = z2;
 224             z2 = t;
 225         }
 226
 227         for (int x = x1; x <= x2; x++)
 228             for (int y = y1; y <= y2; y++)
 229                 for (int z = z1; z <= z2; z++)
 230                     putCell(x, y, z, 0, 0, 0, masterCellSize, 0, color);
 231
 232     }
 233
 234     public int getCellColor(final int pointer) {
 235         return ce2[pointer];
 236     }
 237
 238     public int getCellIllumination(final int pointer) {
 239         return ce3[pointer];
 240     }
 241
 242     public void initWorld(final int bufferLength, final int masterCellSize) {
 243         // System.out.println("Initializing new world");
 244
 245         // initialize world storage buffer
 246         this.masterCellSize = masterCellSize;
 247
 248         ce1 = new int[bufferLength];
 249         ce2 = new int[bufferLength];
 250         ce3 = new int[bufferLength];
 251         ce4 = new int[bufferLength];
 252
 253         ce5 = new int[bufferLength];
 254         ce6 = new int[bufferLength];
 255         ce7 = new int[bufferLength];
 256         ce8 = new int[bufferLength];
 257
 258         for (int i = 0; i < bufferLength; i++)
 259             ce1[i] = CELL_STATE_UNUSED;
 260
 261         // initialize master cell
 262         clearCell(0);
 263     }
 264
 265     public boolean isCellSolid(final int pointer) {
 266         return ce1[pointer] == CELL_STATE_SOLID;
 267     }
 268
 269     public int makeNewCell() {
 270         for (; ; ) {
 271             if (cellAllocationPointer >= ce1.length)
 272                 cellAllocationPointer = 0;
 273
 274             if (ce1[cellAllocationPointer] == CELL_STATE_UNUSED) {
 275
 276                 clearCell(cellAllocationPointer);
 277
 278                 usedCellsCount++;
 279                 return cellAllocationPointer;
 280             } else
 281                 cellAllocationPointer++;
 282         }
 283     }
 284
 285     public int makeNewCell(final int color, final int illumination) {
 286         final int pointer = makeNewCell();
 287         markCellAsSolid(pointer);
 288         setCellColor(pointer, color);
 289         setCellIllumination(pointer, illumination);
 290         return pointer;
 291     }
 292
 293     public void markCellAsSolid(final int pointer) {
 294         ce1[pointer] = CELL_STATE_SOLID;
 295     }
 296
 297     public void putCell(final int x, final int y, final int z, final Color color) {
 298         putCell(x, y, z, 0, 0, 0, masterCellSize, 0, color);
 299     }
 300
 301     private void putCell(final int x, final int y, final int z,
 302                          final int cellX, final int cellY, final int cellZ,
 303                          final int cellSize, final int cellPointer, final Color color) {
 304
 305         if (cellSize > 1) {
 306
 307             // if case of big cell
 308             if (isCellSolid(cellPointer)) {
 309
 310                 // if cell is already a needed color, do notheing
 311                 if (getCellColor(cellPointer) == color.toInt())
 312                     return;
 313
 314                 // otherwise break cell up
 315                 breakSolidCell(cellPointer);
 316
 317                 // continue, as if it is cluster now
 318             }
 319
 320             // decide witch subcube to use
 321             int[] subCubeArray;
 322             int subX, subY, subZ;
 323
 324             if (x > cellX) {
 325                 subX = (cellSize / 2) + cellX;
 326                 if (y > cellY) {
 327                     subY = (cellSize / 2) + cellY;
 328                     if (z > cellZ) {
 329                         subZ = (cellSize / 2) + cellZ;
 330                         // 7
 331                         subCubeArray = ce7;
 332                     } else {
 333                         subZ = (-cellSize / 2) + cellZ;
 334                         // 3
 335                         subCubeArray = ce3;
 336                     }
 337                 } else {
 338                     subY = (-cellSize / 2) + cellY;
 339                     if (z > cellZ) {
 340                         subZ = (cellSize / 2) + cellZ;
 341                         // 6
 342                         subCubeArray = ce6;
 343                     } else {
 344                         subZ = (-cellSize / 2) + cellZ;
 345                         // 2
 346                         subCubeArray = ce2;
 347                     }
 348                 }
 349             } else {
 350                 subX = (-cellSize / 2) + cellX;
 351                 if (y > cellY) {
 352                     subY = (cellSize / 2) + cellY;
 353                     if (z > cellZ) {
 354                         subZ = (cellSize / 2) + cellZ;
 355                         // 8
 356                         subCubeArray = ce8;
 357                     } else {
 358                         subZ = (-cellSize / 2) + cellZ;
 359                         // 4
 360                         subCubeArray = ce4;
 361                     }
 362                 } else {
 363                     subY = (-cellSize / 2) + cellY;
 364                     if (z > cellZ) {
 365                         subZ = (cellSize / 2) + cellZ;
 366                         // 5
 367                         subCubeArray = ce5;
 368                     } else {
 369                         subZ = (-cellSize / 2) + cellZ;
 370                         // 1
 371                         subCubeArray = ce1;
 372                     }
 373                 }
 374             }
 375
 376             int subCubePointer;
 377             if (subCubeArray[cellPointer] == 0) {
 378                 // create empty cluster
 379                 subCubePointer = makeNewCell();
 380                 subCubeArray[cellPointer] = subCubePointer;
 381             } else
 382                 subCubePointer = subCubeArray[cellPointer];
 383
 384             putCell(x, y, z, subX, subY, subZ, cellSize / 2, subCubePointer,
 385                     color);
 386         } else {
 387             ce1[cellPointer] = CELL_STATE_SOLID;
 388             ce2[cellPointer] = color.toInt();
 389             ce3[cellPointer] = CELL_STATE_UNUSED;
 390             // System.out.println("Cell written!");
 391         }
 392     }
 393
 394     public void setCellColor(final int pointer, final int color) {
 395         ce2[pointer] = color;
 396     }
 397
 398     public void setCellIllumination(final int pointer, final int illumination) {
 399         ce3[pointer] = illumination;
 400     }
 401
 402     /**
 403      * Trace ray through the world and return pointer to intersecting cell.
 404      *
 405      * @return pointer to intersecting cell or TRACE_NO_HIT if no intersection.
 406      */
 407     public int traceCell(final int cellX, final int cellY, final int cellZ,
 408                          final int cellSize, final int pointer, final Ray ray) {
 409         if (isCellSolid(pointer)) {
 410             // solid cell
 411             if (doesIntersect(cellX, cellY, cellZ, cellSize, ray) != 0) {
 412                 ray.hitCellSize = cellSize;
 413                 ray.hitCellX = cellX;
 414                 ray.hitCellY = cellY;
 415                 ray.hitCellZ = cellZ;
 416                 return pointer;
 417             }
 418             return TRACE_NO_HIT;
 419         } else // cluster
 420             if (doesIntersect(cellX, cellY, cellZ, cellSize, ray) != 0) {
 421                 final int halfOfCellSize = cellSize / 2;
 422                 int rayIntersectionResult;
 423
 424                 if (ray.origin.x > cellX) {
 425                     if (ray.origin.y > cellY) {
 426                         if (ray.origin.z > cellZ) {
 427                             // 7
 428                             // 6 8 3 5 2 4 1
 429
 430                             if (ce7[pointer] != 0) {
 431                                 rayIntersectionResult = traceCell(cellX
 432                                                 + halfOfCellSize, cellY + halfOfCellSize,
 433                                         cellZ + halfOfCellSize, halfOfCellSize,
 434                                         ce7[pointer], ray);
 435                                 if (rayIntersectionResult >= 0)
 436                                     return rayIntersectionResult;
 437                             }
 438                             if (ce6[pointer] != 0) {
 439                                 rayIntersectionResult = traceCell(cellX
 440                                                 + halfOfCellSize, cellY - halfOfCellSize,
 441                                         cellZ + halfOfCellSize, halfOfCellSize,
 442                                         ce6[pointer], ray);
 443                                 if (rayIntersectionResult >= 0)
 444                                     return rayIntersectionResult;
 445                             }
 446                             if (ce8[pointer] != 0) {
 447                                 rayIntersectionResult = traceCell(cellX
 448                                                 - halfOfCellSize, cellY + halfOfCellSize,
 449                                         cellZ + halfOfCellSize, halfOfCellSize,
 450                                         ce8[pointer], ray);
 451                                 if (rayIntersectionResult >= 0)
 452                                     return rayIntersectionResult;
 453                             }
 454                             if (ce3[pointer] != 0) {
 455                                 rayIntersectionResult = traceCell(cellX
 456                                                 + halfOfCellSize, cellY + halfOfCellSize,
 457                                         cellZ - halfOfCellSize, halfOfCellSize,
 458                                         ce3[pointer], ray);
 459                                 if (rayIntersectionResult >= 0)
 460                                     return rayIntersectionResult;
 461                             }
 462
 463                             if (ce2[pointer] != 0) {
 464                                 rayIntersectionResult = traceCell(cellX
 465                                                 + halfOfCellSize, cellY - halfOfCellSize,
 466                                         cellZ - halfOfCellSize, halfOfCellSize,
 467                                         ce2[pointer], ray);
 468                                 if (rayIntersectionResult >= 0)
 469                                     return rayIntersectionResult;
 470                             }
 471                             if (ce4[pointer] != 0) {
 472                                 rayIntersectionResult = traceCell(cellX
 473                                                 - halfOfCellSize, cellY + halfOfCellSize,
 474                                         cellZ - halfOfCellSize, halfOfCellSize,
 475                                         ce4[pointer], ray);
 476                                 if (rayIntersectionResult >= 0)
 477                                     return rayIntersectionResult;
 478                             }
 479
 480                             if (ce5[pointer] != 0) {
 481                                 rayIntersectionResult = traceCell(cellX
 482                                                 - halfOfCellSize, cellY - halfOfCellSize,
 483                                         cellZ + halfOfCellSize, halfOfCellSize,
 484                                         ce5[pointer], ray);
 485                                 if (rayIntersectionResult >= 0)
 486                                     return rayIntersectionResult;
 487                             }
 488
 489                             if (ce1[pointer] != 0) {
 490                                 rayIntersectionResult = traceCell(cellX
 491                                                 - halfOfCellSize, cellY - halfOfCellSize,
 492                                         cellZ - halfOfCellSize, halfOfCellSize,
 493                                         ce1[pointer], ray);
 494                                 if (rayIntersectionResult >= 0)
 495                                     return rayIntersectionResult;
 496                             }
 497
 498                         } else {
 499                             // 3
 500                             // 2 4 7 1 6 8 5
 501                             if (ce3[pointer] != 0) {
 502                                 rayIntersectionResult = traceCell(cellX
 503                                                 + halfOfCellSize, cellY + halfOfCellSize,
 504                                         cellZ - halfOfCellSize, halfOfCellSize,
 505                                         ce3[pointer], ray);
 506                                 if (rayIntersectionResult >= 0)
 507                                     return rayIntersectionResult;
 508                             }
 509
 510                             if (ce2[pointer] != 0) {
 511                                 rayIntersectionResult = traceCell(cellX
 512                                                 + halfOfCellSize, cellY - halfOfCellSize,
 513                                         cellZ - halfOfCellSize, halfOfCellSize,
 514                                         ce2[pointer], ray);
 515                                 if (rayIntersectionResult >= 0)
 516                                     return rayIntersectionResult;
 517                             }
 518                             if (ce4[pointer] != 0) {
 519                                 rayIntersectionResult = traceCell(cellX
 520                                                 - halfOfCellSize, cellY + halfOfCellSize,
 521                                         cellZ - halfOfCellSize, halfOfCellSize,
 522                                         ce4[pointer], ray);
 523                                 if (rayIntersectionResult >= 0)
 524                                     return rayIntersectionResult;
 525                             }
 526
 527                             if (ce7[pointer] != 0) {
 528                                 rayIntersectionResult = traceCell(cellX
 529                                                 + halfOfCellSize, cellY + halfOfCellSize,
 530                                         cellZ + halfOfCellSize, halfOfCellSize,
 531                                         ce7[pointer], ray);
 532                                 if (rayIntersectionResult >= 0)
 533                                     return rayIntersectionResult;
 534                             }
 535                             if (ce6[pointer] != 0) {
 536                                 rayIntersectionResult = traceCell(cellX
 537                                                 + halfOfCellSize, cellY - halfOfCellSize,
 538                                         cellZ + halfOfCellSize, halfOfCellSize,
 539                                         ce6[pointer], ray);
 540                                 if (rayIntersectionResult >= 0)
 541                                     return rayIntersectionResult;
 542                             }
 543                             if (ce8[pointer] != 0) {
 544                                 rayIntersectionResult = traceCell(cellX
 545                                                 - halfOfCellSize, cellY + halfOfCellSize,
 546                                         cellZ + halfOfCellSize, halfOfCellSize,
 547                                         ce8[pointer], ray);
 548                                 if (rayIntersectionResult >= 0)
 549                                     return rayIntersectionResult;
 550                             }
 551
 552                             if (ce1[pointer] != 0) {
 553                                 rayIntersectionResult = traceCell(cellX
 554                                                 - halfOfCellSize, cellY - halfOfCellSize,
 555                                         cellZ - halfOfCellSize, halfOfCellSize,
 556                                         ce1[pointer], ray);
 557                                 if (rayIntersectionResult >= 0)
 558                                     return rayIntersectionResult;
 559                             }
 560
 561                             if (ce5[pointer] != 0) {
 562                                 rayIntersectionResult = traceCell(cellX
 563                                                 - halfOfCellSize, cellY - halfOfCellSize,
 564                                         cellZ + halfOfCellSize, halfOfCellSize,
 565                                         ce5[pointer], ray);
 566                                 if (rayIntersectionResult >= 0)
 567                                     return rayIntersectionResult;
 568                             }
 569
 570                         }
 571                     } else if (ray.origin.z > cellZ) {
 572                         // 6
 573                         // 5 2 7 8 1 3 4
 574                         if (ce6[pointer] != 0) {
 575                             rayIntersectionResult = traceCell(cellX
 576                                             + halfOfCellSize, cellY - halfOfCellSize, cellZ
 577                                             + halfOfCellSize, halfOfCellSize, ce6[pointer],
 578                                     ray);
 579                             if (rayIntersectionResult >= 0)
 580                                 return rayIntersectionResult;
 581                         }
 582
 583                         if (ce7[pointer] != 0) {
 584                             rayIntersectionResult = traceCell(cellX
 585                                             + halfOfCellSize, cellY + halfOfCellSize, cellZ
 586                                             + halfOfCellSize, halfOfCellSize, ce7[pointer],
 587                                     ray);
 588                             if (rayIntersectionResult >= 0)
 589                                 return rayIntersectionResult;
 590                         }
 591                         if (ce2[pointer] != 0) {
 592                             rayIntersectionResult = traceCell(cellX
 593                                             + halfOfCellSize, cellY - halfOfCellSize, cellZ
 594                                             - halfOfCellSize, halfOfCellSize, ce2[pointer],
 595                                     ray);
 596                             if (rayIntersectionResult >= 0)
 597                                 return rayIntersectionResult;
 598                         }
 599                         if (ce5[pointer] != 0) {
 600                             rayIntersectionResult = traceCell(cellX
 601                                             - halfOfCellSize, cellY - halfOfCellSize, cellZ
 602                                             + halfOfCellSize, halfOfCellSize, ce5[pointer],
 603                                     ray);
 604                             if (rayIntersectionResult >= 0)
 605                                 return rayIntersectionResult;
 606                         }
 607                         if (ce8[pointer] != 0) {
 608                             rayIntersectionResult = traceCell(cellX
 609                                             - halfOfCellSize, cellY + halfOfCellSize, cellZ
 610                                             + halfOfCellSize, halfOfCellSize, ce8[pointer],
 611                                     ray);
 612                             if (rayIntersectionResult >= 0)
 613                                 return rayIntersectionResult;
 614                         }
 615                         if (ce3[pointer] != 0) {
 616                             rayIntersectionResult = traceCell(cellX
 617                                             + halfOfCellSize, cellY + halfOfCellSize, cellZ
 618                                             - halfOfCellSize, halfOfCellSize, ce3[pointer],
 619                                     ray);
 620                             if (rayIntersectionResult >= 0)
 621                                 return rayIntersectionResult;
 622                         }
 623
 624                         if (ce1[pointer] != 0) {
 625                             rayIntersectionResult = traceCell(cellX
 626                                             - halfOfCellSize, cellY - halfOfCellSize, cellZ
 627                                             - halfOfCellSize, halfOfCellSize, ce1[pointer],
 628                                     ray);
 629                             if (rayIntersectionResult >= 0)
 630                                 return rayIntersectionResult;
 631                         }
 632                         if (ce4[pointer] != 0) {
 633                             rayIntersectionResult = traceCell(cellX
 634                                             - halfOfCellSize, cellY + halfOfCellSize, cellZ
 635                                             - halfOfCellSize, halfOfCellSize, ce4[pointer],
 636                                     ray);
 637                             if (rayIntersectionResult >= 0)
 638                                 return rayIntersectionResult;
 639                         }
 640
 641                     } else {
 642                         // 2
 643                         // 1 3 6 5 4 7 8
 644                         if (ce2[pointer] != 0) {
 645                             rayIntersectionResult = traceCell(cellX
 646                                             + halfOfCellSize, cellY - halfOfCellSize, cellZ
 647                                             - halfOfCellSize, halfOfCellSize, ce2[pointer],
 648                                     ray);
 649                             if (rayIntersectionResult >= 0)
 650                                 return rayIntersectionResult;
 651                         }
 652
 653                         if (ce3[pointer] != 0) {
 654                             rayIntersectionResult = traceCell(cellX
 655                                             + halfOfCellSize, cellY + halfOfCellSize, cellZ
 656                                             - halfOfCellSize, halfOfCellSize, ce3[pointer],
 657                                     ray);
 658                             if (rayIntersectionResult >= 0)
 659                                 return rayIntersectionResult;
 660                         }
 661
 662                         if (ce1[pointer] != 0) {
 663                             rayIntersectionResult = traceCell(cellX
 664                                             - halfOfCellSize, cellY - halfOfCellSize, cellZ
 665                                             - halfOfCellSize, halfOfCellSize, ce1[pointer],
 666                                     ray);
 667                             if (rayIntersectionResult >= 0)
 668                                 return rayIntersectionResult;
 669                         }
 670                         if (ce6[pointer] != 0) {
 671                             rayIntersectionResult = traceCell(cellX
 672                                             + halfOfCellSize, cellY - halfOfCellSize, cellZ
 673                                             + halfOfCellSize, halfOfCellSize, ce6[pointer],
 674                                     ray);
 675                             if (rayIntersectionResult >= 0)
 676                                 return rayIntersectionResult;
 677                         }
 678
 679                         if (ce7[pointer] != 0) {
 680                             rayIntersectionResult = traceCell(cellX
 681                                             + halfOfCellSize, cellY + halfOfCellSize, cellZ
 682                                             + halfOfCellSize, halfOfCellSize, ce7[pointer],
 683                                     ray);
 684                             if (rayIntersectionResult >= 0)
 685                                 return rayIntersectionResult;
 686                         }
 687                         if (ce5[pointer] != 0) {
 688                             rayIntersectionResult = traceCell(cellX
 689                                             - halfOfCellSize, cellY - halfOfCellSize, cellZ
 690                                             + halfOfCellSize, halfOfCellSize, ce5[pointer],
 691                                     ray);
 692                             if (rayIntersectionResult >= 0)
 693                                 return rayIntersectionResult;
 694                         }
 695                         if (ce4[pointer] != 0) {
 696                             rayIntersectionResult = traceCell(cellX
 697                                             - halfOfCellSize, cellY + halfOfCellSize, cellZ
 698                                             - halfOfCellSize, halfOfCellSize, ce4[pointer],
 699                                     ray);
 700                             if (rayIntersectionResult >= 0)
 701                                 return rayIntersectionResult;
 702                         }
 703                         if (ce8[pointer] != 0) {
 704                             rayIntersectionResult = traceCell(cellX
 705                                             - halfOfCellSize, cellY + halfOfCellSize, cellZ
 706                                             + halfOfCellSize, halfOfCellSize, ce8[pointer],
 707                                     ray);
 708                             if (rayIntersectionResult >= 0)
 709                                 return rayIntersectionResult;
 710                         }
 711
 712                     }
 713                 } else if (ray.origin.y > cellY) {
 714                     if (ray.origin.z > cellZ) {
 715                         // 8
 716                         // 5 7 4 1 6 3 2
 717
 718                         if (ce8[pointer] != 0) {
 719                             rayIntersectionResult = traceCell(cellX
 720                                             - halfOfCellSize, cellY + halfOfCellSize, cellZ
 721                                             + halfOfCellSize, halfOfCellSize, ce8[pointer],
 722                                     ray);
 723                             if (rayIntersectionResult >= 0)
 724                                 return rayIntersectionResult;
 725                         }
 726                         if (ce7[pointer] != 0) {
 727                             rayIntersectionResult = traceCell(cellX
 728                                             + halfOfCellSize, cellY + halfOfCellSize, cellZ
 729                                             + halfOfCellSize, halfOfCellSize, ce7[pointer],
 730                                     ray);
 731                             if (rayIntersectionResult >= 0)
 732                                 return rayIntersectionResult;
 733                         }
 734                         if (ce5[pointer] != 0) {
 735                             rayIntersectionResult = traceCell(cellX
 736                                             - halfOfCellSize, cellY - halfOfCellSize, cellZ
 737                                             + halfOfCellSize, halfOfCellSize, ce5[pointer],
 738                                     ray);
 739                             if (rayIntersectionResult >= 0)
 740                                 return rayIntersectionResult;
 741                         }
 742                         if (ce4[pointer] != 0) {
 743                             rayIntersectionResult = traceCell(cellX
 744                                             - halfOfCellSize, cellY + halfOfCellSize, cellZ
 745                                             - halfOfCellSize, halfOfCellSize, ce4[pointer],
 746                                     ray);
 747                             if (rayIntersectionResult >= 0)
 748                                 return rayIntersectionResult;
 749                         }
 750
 751                         if (ce3[pointer] != 0) {
 752                             rayIntersectionResult = traceCell(cellX
 753                                             + halfOfCellSize, cellY + halfOfCellSize, cellZ
 754                                             - halfOfCellSize, halfOfCellSize, ce3[pointer],
 755                                     ray);
 756                             if (rayIntersectionResult >= 0)
 757                                 return rayIntersectionResult;
 758                         }
 759
 760                         if (ce1[pointer] != 0) {
 761                             rayIntersectionResult = traceCell(cellX
 762                                             - halfOfCellSize, cellY - halfOfCellSize, cellZ
 763                                             - halfOfCellSize, halfOfCellSize, ce1[pointer],
 764                                     ray);
 765                             if (rayIntersectionResult >= 0)
 766                                 return rayIntersectionResult;
 767                         }
 768                         if (ce6[pointer] != 0) {
 769                             rayIntersectionResult = traceCell(cellX
 770                                             + halfOfCellSize, cellY - halfOfCellSize, cellZ
 771                                             + halfOfCellSize, halfOfCellSize, ce6[pointer],
 772                                     ray);
 773                             if (rayIntersectionResult >= 0)
 774                                 return rayIntersectionResult;
 775                         }
 776
 777                         if (ce2[pointer] != 0) {
 778                             rayIntersectionResult = traceCell(cellX
 779                                             + halfOfCellSize, cellY - halfOfCellSize, cellZ
 780                                             - halfOfCellSize, halfOfCellSize, ce2[pointer],
 781                                     ray);
 782                             if (rayIntersectionResult >= 0)
 783                                 return rayIntersectionResult;
 784                         }
 785
 786                     } else {
 787                         // 4
 788                         // 1 3 8 5 7 2 6
 789
 790                         if (ce4[pointer] != 0) {
 791                             rayIntersectionResult = traceCell(cellX
 792                                             - halfOfCellSize, cellY + halfOfCellSize, cellZ
 793                                             - halfOfCellSize, halfOfCellSize, ce4[pointer],
 794                                     ray);
 795                             if (rayIntersectionResult >= 0)
 796                                 return rayIntersectionResult;
 797                         }
 798
 799                         if (ce8[pointer] != 0) {
 800                             rayIntersectionResult = traceCell(cellX
 801                                             - halfOfCellSize, cellY + halfOfCellSize, cellZ
 802                                             + halfOfCellSize, halfOfCellSize, ce8[pointer],
 803                                     ray);
 804                             if (rayIntersectionResult >= 0)
 805                                 return rayIntersectionResult;
 806                         }
 807                         if (ce3[pointer] != 0) {
 808                             rayIntersectionResult = traceCell(cellX
 809                                             + halfOfCellSize, cellY + halfOfCellSize, cellZ
 810                                             - halfOfCellSize, halfOfCellSize, ce3[pointer],
 811                                     ray);
 812                             if (rayIntersectionResult >= 0)
 813                                 return rayIntersectionResult;
 814                         }
 815
 816                         if (ce1[pointer] != 0) {
 817                             rayIntersectionResult = traceCell(cellX
 818                                             - halfOfCellSize, cellY - halfOfCellSize, cellZ
 819                                             - halfOfCellSize, halfOfCellSize, ce1[pointer],
 820                                     ray);
 821                             if (rayIntersectionResult >= 0)
 822                                 return rayIntersectionResult;
 823                         }
 824                         if (ce7[pointer] != 0) {
 825                             rayIntersectionResult = traceCell(cellX
 826                                             + halfOfCellSize, cellY + halfOfCellSize, cellZ
 827                                             + halfOfCellSize, halfOfCellSize, ce7[pointer],
 828                                     ray);
 829                             if (rayIntersectionResult >= 0)
 830                                 return rayIntersectionResult;
 831                         }
 832                         if (ce5[pointer] != 0) {
 833                             rayIntersectionResult = traceCell(cellX
 834                                             - halfOfCellSize, cellY - halfOfCellSize, cellZ
 835                                             + halfOfCellSize, halfOfCellSize, ce5[pointer],
 836                                     ray);
 837                             if (rayIntersectionResult >= 0)
 838                                 return rayIntersectionResult;
 839                         }
 840
 841                         if (ce2[pointer] != 0) {
 842                             rayIntersectionResult = traceCell(cellX
 843                                             + halfOfCellSize, cellY - halfOfCellSize, cellZ
 844                                             - halfOfCellSize, halfOfCellSize, ce2[pointer],
 845                                     ray);
 846                             if (rayIntersectionResult >= 0)
 847                                 return rayIntersectionResult;
 848                         }
 849                         if (ce6[pointer] != 0) {
 850                             rayIntersectionResult = traceCell(cellX
 851                                             + halfOfCellSize, cellY - halfOfCellSize, cellZ
 852                                             + halfOfCellSize, halfOfCellSize, ce6[pointer],
 853                                     ray);
 854                             if (rayIntersectionResult >= 0)
 855                                 return rayIntersectionResult;
 856                         }
 857
 858                     }
 859                 } else if (ray.origin.z > cellZ) {
 860                     // 5
 861                     // 1 6 8 4 2 7 3
 862
 863                     if (ce5[pointer] != 0) {
 864                         rayIntersectionResult = traceCell(cellX - halfOfCellSize,
 865                                 cellY - halfOfCellSize, cellZ + halfOfCellSize,
 866                                 halfOfCellSize, ce5[pointer], ray);
 867                         if (rayIntersectionResult >= 0)
 868                             return rayIntersectionResult;
 869                     }
 870
 871                     if (ce1[pointer] != 0) {
 872                         rayIntersectionResult = traceCell(cellX - halfOfCellSize,
 873                                 cellY - halfOfCellSize, cellZ - halfOfCellSize,
 874                                 halfOfCellSize, ce1[pointer], ray);
 875                         if (rayIntersectionResult >= 0)
 876                             return rayIntersectionResult;
 877                     }
 878
 879                     if (ce6[pointer] != 0) {
 880                         rayIntersectionResult = traceCell(cellX + halfOfCellSize,
 881                                 cellY - halfOfCellSize, cellZ + halfOfCellSize,
 882                                 halfOfCellSize, ce6[pointer], ray);
 883                         if (rayIntersectionResult >= 0)
 884                             return rayIntersectionResult;
 885                     }
 886
 887                     if (ce8[pointer] != 0) {
 888                         rayIntersectionResult = traceCell(cellX - halfOfCellSize,
 889                                 cellY + halfOfCellSize, cellZ + halfOfCellSize,
 890                                 halfOfCellSize, ce8[pointer], ray);
 891                         if (rayIntersectionResult >= 0)
 892                             return rayIntersectionResult;
 893                     }
 894
 895                     if (ce4[pointer] != 0) {
 896                         rayIntersectionResult = traceCell(cellX - halfOfCellSize,
 897                                 cellY + halfOfCellSize, cellZ - halfOfCellSize,
 898                                 halfOfCellSize, ce4[pointer], ray);
 899                         if (rayIntersectionResult >= 0)
 900                             return rayIntersectionResult;
 901                     }
 902
 903                     if (ce7[pointer] != 0) {
 904                         rayIntersectionResult = traceCell(cellX + halfOfCellSize,
 905                                 cellY + halfOfCellSize, cellZ + halfOfCellSize,
 906                                 halfOfCellSize, ce7[pointer], ray);
 907                         if (rayIntersectionResult >= 0)
 908                             return rayIntersectionResult;
 909                     }
 910
 911                     if (ce2[pointer] != 0) {
 912                         rayIntersectionResult = traceCell(cellX + halfOfCellSize,
 913                                 cellY - halfOfCellSize, cellZ - halfOfCellSize,
 914                                 halfOfCellSize, ce2[pointer], ray);
 915                         if (rayIntersectionResult >= 0)
 916                             return rayIntersectionResult;
 917                     }
 918
 919                     if (ce3[pointer] != 0) {
 920                         rayIntersectionResult = traceCell(cellX + halfOfCellSize,
 921                                 cellY + halfOfCellSize, cellZ - halfOfCellSize,
 922                                 halfOfCellSize, ce3[pointer], ray);
 923                         if (rayIntersectionResult >= 0)
 924                             return rayIntersectionResult;
 925                     }
 926
 927                 } else {
 928                     // 1
 929                     // 5 2 4 8 6 3 7
 930
 931                     if (ce1[pointer] != 0) {
 932                         rayIntersectionResult = traceCell(cellX - halfOfCellSize,
 933                                 cellY - halfOfCellSize, cellZ - halfOfCellSize,
 934                                 halfOfCellSize, ce1[pointer], ray);
 935                         if (rayIntersectionResult >= 0)
 936                             return rayIntersectionResult;
 937                     }
 938
 939                     if (ce5[pointer] != 0) {
 940                         rayIntersectionResult = traceCell(cellX - halfOfCellSize,
 941                                 cellY - halfOfCellSize, cellZ + halfOfCellSize,
 942                                 halfOfCellSize, ce5[pointer], ray);
 943                         if (rayIntersectionResult >= 0)
 944                             return rayIntersectionResult;
 945                     }
 946                     if (ce2[pointer] != 0) {
 947                         rayIntersectionResult = traceCell(cellX + halfOfCellSize,
 948                                 cellY - halfOfCellSize, cellZ - halfOfCellSize,
 949                                 halfOfCellSize, ce2[pointer], ray);
 950                         if (rayIntersectionResult >= 0)
 951                             return rayIntersectionResult;
 952                     }
 953
 954                     if (ce4[pointer] != 0) {
 955                         rayIntersectionResult = traceCell(cellX - halfOfCellSize,
 956                                 cellY + halfOfCellSize, cellZ - halfOfCellSize,
 957                                 halfOfCellSize, ce4[pointer], ray);
 958                         if (rayIntersectionResult >= 0)
 959                             return rayIntersectionResult;
 960                     }
 961
 962                     if (ce6[pointer] != 0) {
 963                         rayIntersectionResult = traceCell(cellX + halfOfCellSize,
 964                                 cellY - halfOfCellSize, cellZ + halfOfCellSize,
 965                                 halfOfCellSize, ce6[pointer], ray);
 966                         if (rayIntersectionResult >= 0)
 967                             return rayIntersectionResult;
 968                     }
 969
 970                     if (ce8[pointer] != 0) {
 971                         rayIntersectionResult = traceCell(cellX - halfOfCellSize,
 972                                 cellY + halfOfCellSize, cellZ + halfOfCellSize,
 973                                 halfOfCellSize, ce8[pointer], ray);
 974                         if (rayIntersectionResult >= 0)
 975                             return rayIntersectionResult;
 976                     }
 977
 978                     if (ce3[pointer] != 0) {
 979                         rayIntersectionResult = traceCell(cellX + halfOfCellSize,
 980                                 cellY + halfOfCellSize, cellZ - halfOfCellSize,
 981                                 halfOfCellSize, ce3[pointer], ray);
 982                         if (rayIntersectionResult >= 0)
 983                             return rayIntersectionResult;
 984                     }
 985                     if (ce7[pointer] != 0) {
 986                         rayIntersectionResult = traceCell(cellX + halfOfCellSize,
 987                                 cellY + halfOfCellSize, cellZ + halfOfCellSize,
 988                                 halfOfCellSize, ce7[pointer], ray);
 989                         if (rayIntersectionResult >= 0)
 990                             return rayIntersectionResult;
 991                     }
 992                 }
 993             }
 994         return TRACE_NO_HIT;
 995     }
 996
 997 }