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