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