2 * Sixth 3D engine. Author: Svjatoslav Agejenko.
3 * This project is released under Creative Commons Zero (CC0) license.
5 package eu.svjatoslav.sixth.e3d.renderer.octree;
7 import eu.svjatoslav.sixth.e3d.geometry.Point3D;
8 import eu.svjatoslav.sixth.e3d.renderer.octree.raytracer.Ray;
9 import eu.svjatoslav.sixth.e3d.renderer.raster.Color;
13 * There are 3 cell types:
20 * visible color, after being illuminated by nearby light sources
23 * contains pointers to 8 sub cells
27 public class OctreeVolume {
29 // cell is not hit by the ray
30 public static final int TRACE_NO_HIT = -1;
32 // solid cell (contains color and illumination)
33 private static final int CELL_STATE_SOLID = -2;
36 private static final int CELL_STATE_UNUSED = -1;
46 public int cellAllocationPointer = 0;
47 public int usedCellsCount = 0;
48 public int masterCellSize;
50 public OctreeVolume() {
51 initWorld(1500000, 256 * 64);
54 public void breakSolidCell(final int pointer) {
55 final int color = getCellColor(pointer);
56 final int illumination = getCellIllumination(pointer);
58 ce1[pointer] = makeNewCell(color, illumination);
59 ce2[pointer] = makeNewCell(color, illumination);
60 ce3[pointer] = makeNewCell(color, illumination);
61 ce4[pointer] = makeNewCell(color, illumination);
62 ce5[pointer] = makeNewCell(color, illumination);
63 ce6[pointer] = makeNewCell(color, illumination);
64 ce7[pointer] = makeNewCell(color, illumination);
65 ce8[pointer] = makeNewCell(color, illumination);
68 public void clearCell(final int pointer) {
80 public void deleteCell(final int cellPointer) {
81 clearCell(cellPointer);
82 ce1[cellPointer] = CELL_STATE_UNUSED;
86 public int doesIntersect(final int cubeX, final int cubeY, final int cubeZ,
87 final int cubeSize, final Ray r) {
89 // ray starts inside the cube
90 if ((cubeX - cubeSize) < r.origin.x)
91 if ((cubeX + cubeSize) > r.origin.x)
92 if ((cubeY - cubeSize) < r.origin.y)
93 if ((cubeY + cubeSize) > r.origin.y)
94 if ((cubeZ - cubeSize) < r.origin.z)
95 if ((cubeZ + cubeSize) > r.origin.z) {
96 r.hitPoint = r.origin.clone();
100 if (r.direction.z > 0)
101 if ((cubeZ - cubeSize) > r.origin.z) {
102 final double mult = ((cubeZ - cubeSize) - r.origin.z) / r.direction.z;
103 final double hitX = (r.direction.x * mult) + r.origin.x;
104 if ((cubeX - cubeSize) < hitX)
105 if ((cubeX + cubeSize) > hitX) {
106 final double hitY = (r.direction.y * mult) + r.origin.y;
107 if ((cubeY - cubeSize) < hitY)
108 if ((cubeY + cubeSize) > hitY) {
109 r.hitPoint = new Point3D(hitX, hitY, cubeZ
117 if (r.direction.y > 0)
118 if ((cubeY - cubeSize) > r.origin.y) {
119 final double mult = ((cubeY - cubeSize) - r.origin.y) / r.direction.y;
120 final double hitX = (r.direction.x * mult) + r.origin.x;
121 if ((cubeX - cubeSize) < hitX)
122 if ((cubeX + cubeSize) > hitX) {
123 final double hitZ = (r.direction.z * mult) + r.origin.z;
124 if ((cubeZ - cubeSize) < hitZ)
125 if ((cubeZ + cubeSize) > hitZ) {
126 r.hitPoint = new Point3D(hitX, cubeY - cubeSize,
134 if (r.direction.x > 0)
135 if ((cubeX - cubeSize) > r.origin.x) {
136 final double mult = ((cubeX - cubeSize) - r.origin.x) / r.direction.x;
137 final double hitY = (r.direction.y * mult) + r.origin.y;
138 if ((cubeY - cubeSize) < hitY)
139 if ((cubeY + cubeSize) > hitY) {
140 final double hitZ = (r.direction.z * mult) + r.origin.z;
141 if ((cubeZ - cubeSize) < hitZ)
142 if ((cubeZ + cubeSize) > hitZ) {
143 r.hitPoint = new Point3D(cubeX - cubeSize, hitY,
151 if (r.direction.z < 0)
152 if ((cubeZ + cubeSize) < r.origin.z) {
153 final double mult = ((cubeZ + cubeSize) - r.origin.z) / r.direction.z;
154 final double hitX = (r.direction.x * mult) + r.origin.x;
155 if ((cubeX - cubeSize) < hitX)
156 if ((cubeX + cubeSize) > hitX) {
157 final double hitY = (r.direction.y * mult) + r.origin.y;
158 if ((cubeY - cubeSize) < hitY)
159 if ((cubeY + cubeSize) > hitY) {
160 r.hitPoint = new Point3D(hitX, hitY, cubeZ
168 if (r.direction.y < 0)
169 if ((cubeY + cubeSize) < r.origin.y) {
170 final double mult = ((cubeY + cubeSize) - r.origin.y) / r.direction.y;
171 final double hitX = (r.direction.x * mult) + r.origin.x;
172 if ((cubeX - cubeSize) < hitX)
173 if ((cubeX + cubeSize) > hitX) {
174 final double hitZ = (r.direction.z * mult) + r.origin.z;
175 if ((cubeZ - cubeSize) < hitZ)
176 if ((cubeZ + cubeSize) > hitZ) {
177 r.hitPoint = new Point3D(hitX, cubeY + cubeSize,
185 if (r.direction.x < 0)
186 if ((cubeX + cubeSize) < r.origin.x) {
187 final double mult = ((cubeX + cubeSize) - r.origin.x) / r.direction.x;
188 final double hitY = (r.direction.y * mult) + r.origin.y;
189 if ((cubeY - cubeSize) < hitY)
190 if ((cubeY + cubeSize) > hitY) {
191 final double hitZ = (r.direction.z * mult) + r.origin.z;
192 if ((cubeZ - cubeSize) < hitZ)
193 if ((cubeZ + cubeSize) > hitZ) {
194 r.hitPoint = new Point3D(cubeX + cubeSize, hitY,
206 public void fillRect3D(int x1, int y1, int z1, int x2, int y2, int z2,
227 for (int x = x1; x <= x2; x++)
228 for (int y = y1; y <= y2; y++)
229 for (int z = z1; z <= z2; z++)
230 putCell(x, y, z, 0, 0, 0, masterCellSize, 0, color);
234 public int getCellColor(final int pointer) {
238 public int getCellIllumination(final int pointer) {
242 public void initWorld(final int bufferLength, final int masterCellSize) {
243 // System.out.println("Initializing new world");
245 // initialize world storage buffer
246 this.masterCellSize = masterCellSize;
248 ce1 = new int[bufferLength];
249 ce2 = new int[bufferLength];
250 ce3 = new int[bufferLength];
251 ce4 = new int[bufferLength];
253 ce5 = new int[bufferLength];
254 ce6 = new int[bufferLength];
255 ce7 = new int[bufferLength];
256 ce8 = new int[bufferLength];
258 for (int i = 0; i < bufferLength; i++)
259 ce1[i] = CELL_STATE_UNUSED;
261 // initialize master cell
265 public boolean isCellSolid(final int pointer) {
266 return ce1[pointer] == CELL_STATE_SOLID;
269 public int makeNewCell() {
271 if (cellAllocationPointer >= ce1.length)
272 cellAllocationPointer = 0;
274 if (ce1[cellAllocationPointer] == CELL_STATE_UNUSED) {
276 clearCell(cellAllocationPointer);
279 return cellAllocationPointer;
281 cellAllocationPointer++;
285 public int makeNewCell(final int color, final int illumination) {
286 final int pointer = makeNewCell();
287 markCellAsSolid(pointer);
288 setCellColor(pointer, color);
289 setCellIllumination(pointer, illumination);
293 public void markCellAsSolid(final int pointer) {
294 ce1[pointer] = CELL_STATE_SOLID;
297 public void putCell(final int x, final int y, final int z, final Color color) {
298 putCell(x, y, z, 0, 0, 0, masterCellSize, 0, color);
301 private void putCell(final int x, final int y, final int z,
302 final int cellX, final int cellY, final int cellZ,
303 final int cellSize, final int cellPointer, final Color color) {
307 // if case of big cell
308 if (isCellSolid(cellPointer)) {
310 // if cell is already a needed color, do notheing
311 if (getCellColor(cellPointer) == color.toInt())
314 // otherwise break cell up
315 breakSolidCell(cellPointer);
317 // continue, as if it is cluster now
320 // decide witch subcube to use
322 int subX, subY, subZ;
325 subX = (cellSize / 2) + cellX;
327 subY = (cellSize / 2) + cellY;
329 subZ = (cellSize / 2) + cellZ;
333 subZ = (-cellSize / 2) + cellZ;
338 subY = (-cellSize / 2) + cellY;
340 subZ = (cellSize / 2) + cellZ;
344 subZ = (-cellSize / 2) + cellZ;
350 subX = (-cellSize / 2) + cellX;
352 subY = (cellSize / 2) + cellY;
354 subZ = (cellSize / 2) + cellZ;
358 subZ = (-cellSize / 2) + cellZ;
363 subY = (-cellSize / 2) + cellY;
365 subZ = (cellSize / 2) + cellZ;
369 subZ = (-cellSize / 2) + cellZ;
377 if (subCubeArray[cellPointer] == 0) {
378 // create empty cluster
379 subCubePointer = makeNewCell();
380 subCubeArray[cellPointer] = subCubePointer;
382 subCubePointer = subCubeArray[cellPointer];
384 putCell(x, y, z, subX, subY, subZ, cellSize / 2, subCubePointer,
387 ce1[cellPointer] = CELL_STATE_SOLID;
388 ce2[cellPointer] = color.toInt();
389 ce3[cellPointer] = CELL_STATE_UNUSED;
390 // System.out.println("Cell written!");
394 public void setCellColor(final int pointer, final int color) {
395 ce2[pointer] = color;
398 public void setCellIllumination(final int pointer, final int illumination) {
399 ce3[pointer] = illumination;
403 * Trace ray through the world and return pointer to intersecting cell.
405 * @return pointer to intersecting cell or TRACE_NO_HIT if no intersection.
407 public int traceCell(final int cellX, final int cellY, final int cellZ,
408 final int cellSize, final int pointer, final Ray ray) {
409 if (isCellSolid(pointer)) {
411 if (doesIntersect(cellX, cellY, cellZ, cellSize, ray) != 0) {
412 ray.hitCellSize = cellSize;
413 ray.hitCellX = cellX;
414 ray.hitCellY = cellY;
415 ray.hitCellZ = cellZ;
420 if (doesIntersect(cellX, cellY, cellZ, cellSize, ray) != 0) {
421 final int halfOfCellSize = cellSize / 2;
422 int rayIntersectionResult;
424 if (ray.origin.x > cellX) {
425 if (ray.origin.y > cellY) {
426 if (ray.origin.z > cellZ) {
430 if (ce7[pointer] != 0) {
431 rayIntersectionResult = traceCell(cellX
432 + halfOfCellSize, cellY + halfOfCellSize,
433 cellZ + halfOfCellSize, halfOfCellSize,
435 if (rayIntersectionResult >= 0)
436 return rayIntersectionResult;
438 if (ce6[pointer] != 0) {
439 rayIntersectionResult = traceCell(cellX
440 + halfOfCellSize, cellY - halfOfCellSize,
441 cellZ + halfOfCellSize, halfOfCellSize,
443 if (rayIntersectionResult >= 0)
444 return rayIntersectionResult;
446 if (ce8[pointer] != 0) {
447 rayIntersectionResult = traceCell(cellX
448 - halfOfCellSize, cellY + halfOfCellSize,
449 cellZ + halfOfCellSize, halfOfCellSize,
451 if (rayIntersectionResult >= 0)
452 return rayIntersectionResult;
454 if (ce3[pointer] != 0) {
455 rayIntersectionResult = traceCell(cellX
456 + halfOfCellSize, cellY + halfOfCellSize,
457 cellZ - halfOfCellSize, halfOfCellSize,
459 if (rayIntersectionResult >= 0)
460 return rayIntersectionResult;
463 if (ce2[pointer] != 0) {
464 rayIntersectionResult = traceCell(cellX
465 + halfOfCellSize, cellY - halfOfCellSize,
466 cellZ - halfOfCellSize, halfOfCellSize,
468 if (rayIntersectionResult >= 0)
469 return rayIntersectionResult;
471 if (ce4[pointer] != 0) {
472 rayIntersectionResult = traceCell(cellX
473 - halfOfCellSize, cellY + halfOfCellSize,
474 cellZ - halfOfCellSize, halfOfCellSize,
476 if (rayIntersectionResult >= 0)
477 return rayIntersectionResult;
480 if (ce5[pointer] != 0) {
481 rayIntersectionResult = traceCell(cellX
482 - halfOfCellSize, cellY - halfOfCellSize,
483 cellZ + halfOfCellSize, halfOfCellSize,
485 if (rayIntersectionResult >= 0)
486 return rayIntersectionResult;
489 if (ce1[pointer] != 0) {
490 rayIntersectionResult = traceCell(cellX
491 - halfOfCellSize, cellY - halfOfCellSize,
492 cellZ - halfOfCellSize, halfOfCellSize,
494 if (rayIntersectionResult >= 0)
495 return rayIntersectionResult;
501 if (ce3[pointer] != 0) {
502 rayIntersectionResult = traceCell(cellX
503 + halfOfCellSize, cellY + halfOfCellSize,
504 cellZ - halfOfCellSize, halfOfCellSize,
506 if (rayIntersectionResult >= 0)
507 return rayIntersectionResult;
510 if (ce2[pointer] != 0) {
511 rayIntersectionResult = traceCell(cellX
512 + halfOfCellSize, cellY - halfOfCellSize,
513 cellZ - halfOfCellSize, halfOfCellSize,
515 if (rayIntersectionResult >= 0)
516 return rayIntersectionResult;
518 if (ce4[pointer] != 0) {
519 rayIntersectionResult = traceCell(cellX
520 - halfOfCellSize, cellY + halfOfCellSize,
521 cellZ - halfOfCellSize, halfOfCellSize,
523 if (rayIntersectionResult >= 0)
524 return rayIntersectionResult;
527 if (ce7[pointer] != 0) {
528 rayIntersectionResult = traceCell(cellX
529 + halfOfCellSize, cellY + halfOfCellSize,
530 cellZ + halfOfCellSize, halfOfCellSize,
532 if (rayIntersectionResult >= 0)
533 return rayIntersectionResult;
535 if (ce6[pointer] != 0) {
536 rayIntersectionResult = traceCell(cellX
537 + halfOfCellSize, cellY - halfOfCellSize,
538 cellZ + halfOfCellSize, halfOfCellSize,
540 if (rayIntersectionResult >= 0)
541 return rayIntersectionResult;
543 if (ce8[pointer] != 0) {
544 rayIntersectionResult = traceCell(cellX
545 - halfOfCellSize, cellY + halfOfCellSize,
546 cellZ + halfOfCellSize, halfOfCellSize,
548 if (rayIntersectionResult >= 0)
549 return rayIntersectionResult;
552 if (ce1[pointer] != 0) {
553 rayIntersectionResult = traceCell(cellX
554 - halfOfCellSize, cellY - halfOfCellSize,
555 cellZ - halfOfCellSize, halfOfCellSize,
557 if (rayIntersectionResult >= 0)
558 return rayIntersectionResult;
561 if (ce5[pointer] != 0) {
562 rayIntersectionResult = traceCell(cellX
563 - halfOfCellSize, cellY - halfOfCellSize,
564 cellZ + halfOfCellSize, halfOfCellSize,
566 if (rayIntersectionResult >= 0)
567 return rayIntersectionResult;
571 } else if (ray.origin.z > cellZ) {
574 if (ce6[pointer] != 0) {
575 rayIntersectionResult = traceCell(cellX
576 + halfOfCellSize, cellY - halfOfCellSize, cellZ
577 + halfOfCellSize, halfOfCellSize, ce6[pointer],
579 if (rayIntersectionResult >= 0)
580 return rayIntersectionResult;
583 if (ce7[pointer] != 0) {
584 rayIntersectionResult = traceCell(cellX
585 + halfOfCellSize, cellY + halfOfCellSize, cellZ
586 + halfOfCellSize, halfOfCellSize, ce7[pointer],
588 if (rayIntersectionResult >= 0)
589 return rayIntersectionResult;
591 if (ce2[pointer] != 0) {
592 rayIntersectionResult = traceCell(cellX
593 + halfOfCellSize, cellY - halfOfCellSize, cellZ
594 - halfOfCellSize, halfOfCellSize, ce2[pointer],
596 if (rayIntersectionResult >= 0)
597 return rayIntersectionResult;
599 if (ce5[pointer] != 0) {
600 rayIntersectionResult = traceCell(cellX
601 - halfOfCellSize, cellY - halfOfCellSize, cellZ
602 + halfOfCellSize, halfOfCellSize, ce5[pointer],
604 if (rayIntersectionResult >= 0)
605 return rayIntersectionResult;
607 if (ce8[pointer] != 0) {
608 rayIntersectionResult = traceCell(cellX
609 - halfOfCellSize, cellY + halfOfCellSize, cellZ
610 + halfOfCellSize, halfOfCellSize, ce8[pointer],
612 if (rayIntersectionResult >= 0)
613 return rayIntersectionResult;
615 if (ce3[pointer] != 0) {
616 rayIntersectionResult = traceCell(cellX
617 + halfOfCellSize, cellY + halfOfCellSize, cellZ
618 - halfOfCellSize, halfOfCellSize, ce3[pointer],
620 if (rayIntersectionResult >= 0)
621 return rayIntersectionResult;
624 if (ce1[pointer] != 0) {
625 rayIntersectionResult = traceCell(cellX
626 - halfOfCellSize, cellY - halfOfCellSize, cellZ
627 - halfOfCellSize, halfOfCellSize, ce1[pointer],
629 if (rayIntersectionResult >= 0)
630 return rayIntersectionResult;
632 if (ce4[pointer] != 0) {
633 rayIntersectionResult = traceCell(cellX
634 - halfOfCellSize, cellY + halfOfCellSize, cellZ
635 - halfOfCellSize, halfOfCellSize, ce4[pointer],
637 if (rayIntersectionResult >= 0)
638 return rayIntersectionResult;
644 if (ce2[pointer] != 0) {
645 rayIntersectionResult = traceCell(cellX
646 + halfOfCellSize, cellY - halfOfCellSize, cellZ
647 - halfOfCellSize, halfOfCellSize, ce2[pointer],
649 if (rayIntersectionResult >= 0)
650 return rayIntersectionResult;
653 if (ce3[pointer] != 0) {
654 rayIntersectionResult = traceCell(cellX
655 + halfOfCellSize, cellY + halfOfCellSize, cellZ
656 - halfOfCellSize, halfOfCellSize, ce3[pointer],
658 if (rayIntersectionResult >= 0)
659 return rayIntersectionResult;
662 if (ce1[pointer] != 0) {
663 rayIntersectionResult = traceCell(cellX
664 - halfOfCellSize, cellY - halfOfCellSize, cellZ
665 - halfOfCellSize, halfOfCellSize, ce1[pointer],
667 if (rayIntersectionResult >= 0)
668 return rayIntersectionResult;
670 if (ce6[pointer] != 0) {
671 rayIntersectionResult = traceCell(cellX
672 + halfOfCellSize, cellY - halfOfCellSize, cellZ
673 + halfOfCellSize, halfOfCellSize, ce6[pointer],
675 if (rayIntersectionResult >= 0)
676 return rayIntersectionResult;
679 if (ce7[pointer] != 0) {
680 rayIntersectionResult = traceCell(cellX
681 + halfOfCellSize, cellY + halfOfCellSize, cellZ
682 + halfOfCellSize, halfOfCellSize, ce7[pointer],
684 if (rayIntersectionResult >= 0)
685 return rayIntersectionResult;
687 if (ce5[pointer] != 0) {
688 rayIntersectionResult = traceCell(cellX
689 - halfOfCellSize, cellY - halfOfCellSize, cellZ
690 + halfOfCellSize, halfOfCellSize, ce5[pointer],
692 if (rayIntersectionResult >= 0)
693 return rayIntersectionResult;
695 if (ce4[pointer] != 0) {
696 rayIntersectionResult = traceCell(cellX
697 - halfOfCellSize, cellY + halfOfCellSize, cellZ
698 - halfOfCellSize, halfOfCellSize, ce4[pointer],
700 if (rayIntersectionResult >= 0)
701 return rayIntersectionResult;
703 if (ce8[pointer] != 0) {
704 rayIntersectionResult = traceCell(cellX
705 - halfOfCellSize, cellY + halfOfCellSize, cellZ
706 + halfOfCellSize, halfOfCellSize, ce8[pointer],
708 if (rayIntersectionResult >= 0)
709 return rayIntersectionResult;
713 } else if (ray.origin.y > cellY) {
714 if (ray.origin.z > cellZ) {
718 if (ce8[pointer] != 0) {
719 rayIntersectionResult = traceCell(cellX
720 - halfOfCellSize, cellY + halfOfCellSize, cellZ
721 + halfOfCellSize, halfOfCellSize, ce8[pointer],
723 if (rayIntersectionResult >= 0)
724 return rayIntersectionResult;
726 if (ce7[pointer] != 0) {
727 rayIntersectionResult = traceCell(cellX
728 + halfOfCellSize, cellY + halfOfCellSize, cellZ
729 + halfOfCellSize, halfOfCellSize, ce7[pointer],
731 if (rayIntersectionResult >= 0)
732 return rayIntersectionResult;
734 if (ce5[pointer] != 0) {
735 rayIntersectionResult = traceCell(cellX
736 - halfOfCellSize, cellY - halfOfCellSize, cellZ
737 + halfOfCellSize, halfOfCellSize, ce5[pointer],
739 if (rayIntersectionResult >= 0)
740 return rayIntersectionResult;
742 if (ce4[pointer] != 0) {
743 rayIntersectionResult = traceCell(cellX
744 - halfOfCellSize, cellY + halfOfCellSize, cellZ
745 - halfOfCellSize, halfOfCellSize, ce4[pointer],
747 if (rayIntersectionResult >= 0)
748 return rayIntersectionResult;
751 if (ce3[pointer] != 0) {
752 rayIntersectionResult = traceCell(cellX
753 + halfOfCellSize, cellY + halfOfCellSize, cellZ
754 - halfOfCellSize, halfOfCellSize, ce3[pointer],
756 if (rayIntersectionResult >= 0)
757 return rayIntersectionResult;
760 if (ce1[pointer] != 0) {
761 rayIntersectionResult = traceCell(cellX
762 - halfOfCellSize, cellY - halfOfCellSize, cellZ
763 - halfOfCellSize, halfOfCellSize, ce1[pointer],
765 if (rayIntersectionResult >= 0)
766 return rayIntersectionResult;
768 if (ce6[pointer] != 0) {
769 rayIntersectionResult = traceCell(cellX
770 + halfOfCellSize, cellY - halfOfCellSize, cellZ
771 + halfOfCellSize, halfOfCellSize, ce6[pointer],
773 if (rayIntersectionResult >= 0)
774 return rayIntersectionResult;
777 if (ce2[pointer] != 0) {
778 rayIntersectionResult = traceCell(cellX
779 + halfOfCellSize, cellY - halfOfCellSize, cellZ
780 - halfOfCellSize, halfOfCellSize, ce2[pointer],
782 if (rayIntersectionResult >= 0)
783 return rayIntersectionResult;
790 if (ce4[pointer] != 0) {
791 rayIntersectionResult = traceCell(cellX
792 - halfOfCellSize, cellY + halfOfCellSize, cellZ
793 - halfOfCellSize, halfOfCellSize, ce4[pointer],
795 if (rayIntersectionResult >= 0)
796 return rayIntersectionResult;
799 if (ce8[pointer] != 0) {
800 rayIntersectionResult = traceCell(cellX
801 - halfOfCellSize, cellY + halfOfCellSize, cellZ
802 + halfOfCellSize, halfOfCellSize, ce8[pointer],
804 if (rayIntersectionResult >= 0)
805 return rayIntersectionResult;
807 if (ce3[pointer] != 0) {
808 rayIntersectionResult = traceCell(cellX
809 + halfOfCellSize, cellY + halfOfCellSize, cellZ
810 - halfOfCellSize, halfOfCellSize, ce3[pointer],
812 if (rayIntersectionResult >= 0)
813 return rayIntersectionResult;
816 if (ce1[pointer] != 0) {
817 rayIntersectionResult = traceCell(cellX
818 - halfOfCellSize, cellY - halfOfCellSize, cellZ
819 - halfOfCellSize, halfOfCellSize, ce1[pointer],
821 if (rayIntersectionResult >= 0)
822 return rayIntersectionResult;
824 if (ce7[pointer] != 0) {
825 rayIntersectionResult = traceCell(cellX
826 + halfOfCellSize, cellY + halfOfCellSize, cellZ
827 + halfOfCellSize, halfOfCellSize, ce7[pointer],
829 if (rayIntersectionResult >= 0)
830 return rayIntersectionResult;
832 if (ce5[pointer] != 0) {
833 rayIntersectionResult = traceCell(cellX
834 - halfOfCellSize, cellY - halfOfCellSize, cellZ
835 + halfOfCellSize, halfOfCellSize, ce5[pointer],
837 if (rayIntersectionResult >= 0)
838 return rayIntersectionResult;
841 if (ce2[pointer] != 0) {
842 rayIntersectionResult = traceCell(cellX
843 + halfOfCellSize, cellY - halfOfCellSize, cellZ
844 - halfOfCellSize, halfOfCellSize, ce2[pointer],
846 if (rayIntersectionResult >= 0)
847 return rayIntersectionResult;
849 if (ce6[pointer] != 0) {
850 rayIntersectionResult = traceCell(cellX
851 + halfOfCellSize, cellY - halfOfCellSize, cellZ
852 + halfOfCellSize, halfOfCellSize, ce6[pointer],
854 if (rayIntersectionResult >= 0)
855 return rayIntersectionResult;
859 } else if (ray.origin.z > cellZ) {
863 if (ce5[pointer] != 0) {
864 rayIntersectionResult = traceCell(cellX - halfOfCellSize,
865 cellY - halfOfCellSize, cellZ + halfOfCellSize,
866 halfOfCellSize, ce5[pointer], ray);
867 if (rayIntersectionResult >= 0)
868 return rayIntersectionResult;
871 if (ce1[pointer] != 0) {
872 rayIntersectionResult = traceCell(cellX - halfOfCellSize,
873 cellY - halfOfCellSize, cellZ - halfOfCellSize,
874 halfOfCellSize, ce1[pointer], ray);
875 if (rayIntersectionResult >= 0)
876 return rayIntersectionResult;
879 if (ce6[pointer] != 0) {
880 rayIntersectionResult = traceCell(cellX + halfOfCellSize,
881 cellY - halfOfCellSize, cellZ + halfOfCellSize,
882 halfOfCellSize, ce6[pointer], ray);
883 if (rayIntersectionResult >= 0)
884 return rayIntersectionResult;
887 if (ce8[pointer] != 0) {
888 rayIntersectionResult = traceCell(cellX - halfOfCellSize,
889 cellY + halfOfCellSize, cellZ + halfOfCellSize,
890 halfOfCellSize, ce8[pointer], ray);
891 if (rayIntersectionResult >= 0)
892 return rayIntersectionResult;
895 if (ce4[pointer] != 0) {
896 rayIntersectionResult = traceCell(cellX - halfOfCellSize,
897 cellY + halfOfCellSize, cellZ - halfOfCellSize,
898 halfOfCellSize, ce4[pointer], ray);
899 if (rayIntersectionResult >= 0)
900 return rayIntersectionResult;
903 if (ce7[pointer] != 0) {
904 rayIntersectionResult = traceCell(cellX + halfOfCellSize,
905 cellY + halfOfCellSize, cellZ + halfOfCellSize,
906 halfOfCellSize, ce7[pointer], ray);
907 if (rayIntersectionResult >= 0)
908 return rayIntersectionResult;
911 if (ce2[pointer] != 0) {
912 rayIntersectionResult = traceCell(cellX + halfOfCellSize,
913 cellY - halfOfCellSize, cellZ - halfOfCellSize,
914 halfOfCellSize, ce2[pointer], ray);
915 if (rayIntersectionResult >= 0)
916 return rayIntersectionResult;
919 if (ce3[pointer] != 0) {
920 rayIntersectionResult = traceCell(cellX + halfOfCellSize,
921 cellY + halfOfCellSize, cellZ - halfOfCellSize,
922 halfOfCellSize, ce3[pointer], ray);
923 if (rayIntersectionResult >= 0)
924 return rayIntersectionResult;
931 if (ce1[pointer] != 0) {
932 rayIntersectionResult = traceCell(cellX - halfOfCellSize,
933 cellY - halfOfCellSize, cellZ - halfOfCellSize,
934 halfOfCellSize, ce1[pointer], ray);
935 if (rayIntersectionResult >= 0)
936 return rayIntersectionResult;
939 if (ce5[pointer] != 0) {
940 rayIntersectionResult = traceCell(cellX - halfOfCellSize,
941 cellY - halfOfCellSize, cellZ + halfOfCellSize,
942 halfOfCellSize, ce5[pointer], ray);
943 if (rayIntersectionResult >= 0)
944 return rayIntersectionResult;
946 if (ce2[pointer] != 0) {
947 rayIntersectionResult = traceCell(cellX + halfOfCellSize,
948 cellY - halfOfCellSize, cellZ - halfOfCellSize,
949 halfOfCellSize, ce2[pointer], ray);
950 if (rayIntersectionResult >= 0)
951 return rayIntersectionResult;
954 if (ce4[pointer] != 0) {
955 rayIntersectionResult = traceCell(cellX - halfOfCellSize,
956 cellY + halfOfCellSize, cellZ - halfOfCellSize,
957 halfOfCellSize, ce4[pointer], ray);
958 if (rayIntersectionResult >= 0)
959 return rayIntersectionResult;
962 if (ce6[pointer] != 0) {
963 rayIntersectionResult = traceCell(cellX + halfOfCellSize,
964 cellY - halfOfCellSize, cellZ + halfOfCellSize,
965 halfOfCellSize, ce6[pointer], ray);
966 if (rayIntersectionResult >= 0)
967 return rayIntersectionResult;
970 if (ce8[pointer] != 0) {
971 rayIntersectionResult = traceCell(cellX - halfOfCellSize,
972 cellY + halfOfCellSize, cellZ + halfOfCellSize,
973 halfOfCellSize, ce8[pointer], ray);
974 if (rayIntersectionResult >= 0)
975 return rayIntersectionResult;
978 if (ce3[pointer] != 0) {
979 rayIntersectionResult = traceCell(cellX + halfOfCellSize,
980 cellY + halfOfCellSize, cellZ - halfOfCellSize,
981 halfOfCellSize, ce3[pointer], ray);
982 if (rayIntersectionResult >= 0)
983 return rayIntersectionResult;
985 if (ce7[pointer] != 0) {
986 rayIntersectionResult = traceCell(cellX + halfOfCellSize,
987 cellY + halfOfCellSize, cellZ + halfOfCellSize,
988 halfOfCellSize, ce7[pointer], ray);
989 if (rayIntersectionResult >= 0)
990 return rayIntersectionResult;