src/main/java/eu/svjatoslav/sixth/e3d/renderer/octree/OctreeVolume.java

   1 /*
   2  * Sixth 3D engine. Copyright ©2012-2018, Svjatoslav Agejenko, svjatoslav@svjatoslav.eu
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of version 3 of the GNU Lesser General Public License
   6  * or later as published by the Free Software Foundation.
   7  *
   8  */
   9
  10 package eu.svjatoslav.sixth.e3d.renderer.octree;
  11
  12 import eu.svjatoslav.sixth.e3d.renderer.octree.raytracer.Ray;
  13 import eu.svjatoslav.sixth.e3d.renderer.raster.Color;
  14 import eu.svjatoslav.sixth.e3d.renderer.raster.shapes.basic.line.LineAppearance;
  15
  16 /**
  17  * <pre>
  18  * There are 3 cell types:
  19  *
  20  *      UNUSED
  21  *
  22  *      SOLID
  23  *          contains:
  24  *              original color
  25  *              visible color, after being illuminated by nearby light sources
  26  *
  27  *      CLUSTER
  28  *          contains pointers to 8 sub cells
  29  * </pre>
  30  */
  31
  32 public class OctreeVolume {
  33
  34     public static final int TRACE_NO_HIT = -1;
  35     /**
  36      * Single solid color.
  37      */
  38     private static final int CELL_STATE_SOLID = -2;
  39     private static final int CELL_STATE_UNUSED = -1;
  40     final LineAppearance factory = new LineAppearance();
  41     public int ce1[];
  42     public int ce2[];
  43     public int ce3[];
  44     public int ce4[];
  45     public int ce5[];
  46     public int ce6[];
  47     public int ce7[];
  48     public int ce8[];
  49     public int cellAllocationPointer = 0;
  50     public int usedCellsCount = 0;
  51     public int masterCellSize;
  52
  53     public OctreeVolume() {
  54         initWorld(1500000, 256 * 64);
  55     }
  56
  57     public void breakSolidCell(final int pointer) {
  58         final int color = getCellColor(pointer);
  59         final int illumination = getCellIllumination(pointer);
  60
  61         ce1[pointer] = makeNewCell(color, illumination);
  62         ce2[pointer] = makeNewCell(color, illumination);
  63         ce3[pointer] = makeNewCell(color, illumination);
  64         ce4[pointer] = makeNewCell(color, illumination);
  65         ce5[pointer] = makeNewCell(color, illumination);
  66         ce6[pointer] = makeNewCell(color, illumination);
  67         ce7[pointer] = makeNewCell(color, illumination);
  68         ce8[pointer] = makeNewCell(color, illumination);
  69     }
  70
  71     public void clearCell(final int pointer) {
  72         ce1[pointer] = 0;
  73         ce2[pointer] = 0;
  74         ce3[pointer] = 0;
  75         ce4[pointer] = 0;
  76
  77         ce5[pointer] = 0;
  78         ce6[pointer] = 0;
  79         ce7[pointer] = 0;
  80         ce8[pointer] = 0;
  81     }
  82
  83     public void deleteCell(final int cellPointer) {
  84         clearCell(cellPointer);
  85         ce1[cellPointer] = CELL_STATE_UNUSED;
  86         usedCellsCount--;
  87     }
  88
  89     public int doesIntersect(final int cubeX, final int cubeY, final int cubeZ,
  90                              final int cubeSize, final Ray r) {
  91
  92         // ray starts inside the cube
  93         if ((cubeX - cubeSize) < r.x)
  94             if ((cubeX + cubeSize) > r.x)
  95                 if ((cubeY - cubeSize) < r.y)
  96                     if ((cubeY + cubeSize) > r.y)
  97                         if ((cubeZ - cubeSize) < r.z)
  98                             if ((cubeZ + cubeSize) > r.z) {
  99                                 r.hitX = r.x;
 100                                 r.hitY = r.y;
 101                                 r.hitZ = r.z;
 102                                 return 1;
 103                             }
 104         // back face
 105         if (r.zp > 0)
 106             if ((cubeZ - cubeSize) > r.z) {
 107                 final double mult = ((cubeZ - cubeSize) - r.z) / r.zp;
 108                 final double hitX = (r.xp * mult) + r.x;
 109                 if ((cubeX - cubeSize) < hitX)
 110                     if ((cubeX + cubeSize) > hitX) {
 111                         final double hitY = (r.yp * mult) + r.y;
 112                         if ((cubeY - cubeSize) < hitY)
 113                             if ((cubeY + cubeSize) > hitY) {
 114                                 r.hitX = hitX;
 115                                 r.hitY = hitY;
 116                                 r.hitZ = cubeZ - cubeSize;
 117                                 return 2;
 118                             }
 119                     }
 120             }
 121
 122         // up face
 123         if (r.yp > 0)
 124             if ((cubeY - cubeSize) > r.y) {
 125                 final double mult = ((cubeY - cubeSize) - r.y) / r.yp;
 126                 final double hitX = (r.xp * mult) + r.x;
 127                 if ((cubeX - cubeSize) < hitX)
 128                     if ((cubeX + cubeSize) > hitX) {
 129                         final double hitZ = (r.zp * mult) + r.z;
 130                         if ((cubeZ - cubeSize) < hitZ)
 131                             if ((cubeZ + cubeSize) > hitZ) {
 132                                 r.hitX = hitX;
 133                                 r.hitY = cubeY - cubeSize;
 134                                 r.hitZ = hitZ;
 135                                 return 3;
 136                             }
 137                     }
 138             }
 139
 140         // left face
 141         if (r.xp > 0)
 142             if ((cubeX - cubeSize) > r.x) {
 143                 final double mult = ((cubeX - cubeSize) - r.x) / r.xp;
 144                 final double hitY = (r.yp * mult) + r.y;
 145                 if ((cubeY - cubeSize) < hitY)
 146                     if ((cubeY + cubeSize) > hitY) {
 147                         final double hitZ = (r.zp * mult) + r.z;
 148                         if ((cubeZ - cubeSize) < hitZ)
 149                             if ((cubeZ + cubeSize) > hitZ) {
 150                                 r.hitX = cubeX - cubeSize;
 151                                 r.hitY = hitY;
 152                                 r.hitZ = hitZ;
 153                                 return 4;
 154                             }
 155                     }
 156             }
 157
 158         // front face
 159         if (r.zp < 0)
 160             if ((cubeZ + cubeSize) < r.z) {
 161                 final double mult = ((cubeZ + cubeSize) - r.z) / r.zp;
 162                 final double hitX = (r.xp * mult) + r.x;
 163                 if ((cubeX - cubeSize) < hitX)
 164                     if ((cubeX + cubeSize) > hitX) {
 165                         final double hitY = (r.yp * mult) + r.y;
 166                         if ((cubeY - cubeSize) < hitY)
 167                             if ((cubeY + cubeSize) > hitY) {
 168                                 r.hitX = hitX;
 169                                 r.hitY = hitY;
 170                                 r.hitZ = cubeZ + cubeSize;
 171                                 return 5;
 172                             }
 173                     }
 174             }
 175
 176         // down face
 177         if (r.yp < 0)
 178             if ((cubeY + cubeSize) < r.y) {
 179                 final double mult = ((cubeY + cubeSize) - r.y) / r.yp;
 180                 final double hitX = (r.xp * mult) + r.x;
 181                 if ((cubeX - cubeSize) < hitX)
 182                     if ((cubeX + cubeSize) > hitX) {
 183                         final double hitZ = (r.zp * mult) + r.z;
 184                         if ((cubeZ - cubeSize) < hitZ)
 185                             if ((cubeZ + cubeSize) > hitZ) {
 186                                 r.hitX = hitX;
 187                                 r.hitY = cubeY + cubeSize;
 188                                 r.hitZ = hitZ;
 189                                 return 6;
 190                             }
 191                     }
 192             }
 193
 194         // right face
 195         if (r.xp < 0)
 196             if ((cubeX + cubeSize) < r.x) {
 197                 final double mult = ((cubeX + cubeSize) - r.x) / r.xp;
 198                 final double hitY = (r.yp * mult) + r.y;
 199                 if ((cubeY - cubeSize) < hitY)
 200                     if ((cubeY + cubeSize) > hitY) {
 201                         final double hitZ = (r.zp * mult) + r.z;
 202                         if ((cubeZ - cubeSize) < hitZ)
 203                             if ((cubeZ + cubeSize) > hitZ) {
 204                                 r.hitX = cubeX + cubeSize;
 205                                 r.hitY = hitY;
 206                                 r.hitZ = hitZ;
 207                                 return 7;
 208                             }
 209                     }
 210             }
 211         return 0;
 212     }
 213
 214     /**
 215      * Fill 3D rectangle.
 216      */
 217     public void fillRect3D(int x1, int y1, int z1, int x2, int y2, int z2,
 218                            final Color color) {
 219         int t;
 220         if (x1 > x2) {
 221             t = x1;
 222             x1 = x2;
 223             x2 = t;
 224         }
 225
 226         if (y1 > y2) {
 227             t = y1;
 228             y1 = y2;
 229             y2 = t;
 230         }
 231
 232         if (z1 > z2) {
 233             t = z1;
 234             z1 = z2;
 235             z2 = t;
 236         }
 237
 238         for (int x = x1; x <= x2; x++)
 239             for (int y = y1; y <= y2; y++)
 240                 for (int z = z1; z <= z2; z++)
 241                     putCell(x, y, z, 0, 0, 0, masterCellSize, 0, color);
 242
 243     }
 244
 245     public int getCellColor(final int pointer) {
 246         return ce2[pointer];
 247     }
 248
 249     public int getCellIllumination(final int pointer) {
 250         return ce3[pointer];
 251     }
 252
 253     public void initWorld(final int bufferLength, final int masterCellSize) {
 254         // System.out.println("Initializing new world");
 255
 256         // initialize world storage buffer
 257         this.masterCellSize = masterCellSize;
 258
 259         ce1 = new int[bufferLength];
 260         ce2 = new int[bufferLength];
 261         ce3 = new int[bufferLength];
 262         ce4 = new int[bufferLength];
 263
 264         ce5 = new int[bufferLength];
 265         ce6 = new int[bufferLength];
 266         ce7 = new int[bufferLength];
 267         ce8 = new int[bufferLength];
 268
 269         for (int i = 0; i < bufferLength; i++)
 270             ce1[i] = CELL_STATE_UNUSED;
 271
 272         // initialize master cell
 273         clearCell(0);
 274     }
 275
 276     public boolean isCellSolid(final int pointer) {
 277         return ce1[pointer] == CELL_STATE_SOLID;
 278     }
 279
 280     public int makeNewCell() {
 281         for (; ; ) {
 282             if (cellAllocationPointer >= ce1.length)
 283                 cellAllocationPointer = 0;
 284
 285             if (ce1[cellAllocationPointer] == CELL_STATE_UNUSED) {
 286
 287                 clearCell(cellAllocationPointer);
 288
 289                 usedCellsCount++;
 290                 return cellAllocationPointer;
 291             } else
 292                 cellAllocationPointer++;
 293         }
 294     }
 295
 296     public int makeNewCell(final int color, final int illumination) {
 297         final int pointer = makeNewCell();
 298         markCellAsSolid(pointer);
 299         setCellColor(pointer, color);
 300         setCellIllumination(pointer, illumination);
 301         return pointer;
 302     }
 303
 304     public void markCellAsSolid(final int pointer) {
 305         ce1[pointer] = CELL_STATE_SOLID;
 306     }
 307
 308     public void putCell(final int x, final int y, final int z, final Color color) {
 309         putCell(x, y, z, 0, 0, 0, masterCellSize, 0, color);
 310     }
 311
 312     private void putCell(final int x, final int y, final int z,
 313                          final int cellX, final int cellY, final int cellZ,
 314                          final int cellSize, final int cellPointer, final Color color) {
 315
 316         if (cellSize > 1) {
 317
 318             // if case of big cell
 319             if (isCellSolid(cellPointer)) {
 320
 321                 // if cell is already a needed color, do notheing
 322                 if (getCellColor(cellPointer) == color.toInt())
 323                     return;
 324
 325                 // otherwise break cell up
 326                 breakSolidCell(cellPointer);
 327
 328                 // continue, as if it is cluster now
 329             }
 330
 331             // decide witch subcube to use
 332             int subCubeArray[];
 333             int subX, subY, subZ;
 334
 335             if (x > cellX) {
 336                 subX = (cellSize / 2) + cellX;
 337                 if (y > cellY) {
 338                     subY = (cellSize / 2) + cellY;
 339                     if (z > cellZ) {
 340                         subZ = (cellSize / 2) + cellZ;
 341                         // 7
 342                         subCubeArray = ce7;
 343                     } else {
 344                         subZ = (-cellSize / 2) + cellZ;
 345                         // 3
 346                         subCubeArray = ce3;
 347                     }
 348                 } else {
 349                     subY = (-cellSize / 2) + cellY;
 350                     if (z > cellZ) {
 351                         subZ = (cellSize / 2) + cellZ;
 352                         // 6
 353                         subCubeArray = ce6;
 354                     } else {
 355                         subZ = (-cellSize / 2) + cellZ;
 356                         // 2
 357                         subCubeArray = ce2;
 358                     }
 359                 }
 360             } else {
 361                 subX = (-cellSize / 2) + cellX;
 362                 if (y > cellY) {
 363                     subY = (cellSize / 2) + cellY;
 364                     if (z > cellZ) {
 365                         subZ = (cellSize / 2) + cellZ;
 366                         // 8
 367                         subCubeArray = ce8;
 368                     } else {
 369                         subZ = (-cellSize / 2) + cellZ;
 370                         // 4
 371                         subCubeArray = ce4;
 372                     }
 373                 } else {
 374                     subY = (-cellSize / 2) + cellY;
 375                     if (z > cellZ) {
 376                         subZ = (cellSize / 2) + cellZ;
 377                         // 5
 378                         subCubeArray = ce5;
 379                     } else {
 380                         subZ = (-cellSize / 2) + cellZ;
 381                         // 1
 382                         subCubeArray = ce1;
 383                     }
 384                 }
 385             }
 386
 387             int subCubePointer;
 388             if (subCubeArray[cellPointer] == 0) {
 389                 // create empty cluster
 390                 subCubePointer = makeNewCell();
 391                 subCubeArray[cellPointer] = subCubePointer;
 392             } else
 393                 subCubePointer = subCubeArray[cellPointer];
 394
 395             putCell(x, y, z, subX, subY, subZ, cellSize / 2, subCubePointer,
 396                     color);
 397         } else {
 398             ce1[cellPointer] = CELL_STATE_SOLID;
 399             ce2[cellPointer] = color.toInt();
 400             ce3[cellPointer] = CELL_STATE_UNUSED;
 401             // System.out.println("Cell written!");
 402         }
 403     }
 404
 405     public void setCellColor(final int pointer, final int color) {
 406         ce2[pointer] = color;
 407     }
 408
 409     public void setCellIllumination(final int pointer, final int illumination) {
 410         ce3[pointer] = illumination;
 411     }
 412
 413     /**
 414      * @return intersecting cell pointer or -1 if no cell in intersecting this
 415      * ray.
 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 }