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