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