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