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;
10 import eu.svjatoslav.sixth.e3d.renderer.raster.shapes.basic.line.LineAppearance;
14 * There are 3 cell types:
21 * visible color, after being illuminated by nearby light sources
24 * contains pointers to 8 sub cells
28 public class OctreeVolume {
30 // cell is not hit by the ray
31 public static final int TRACE_NO_HIT = -1;
33 // solid cell (contains color and illumination)
34 private static final int CELL_STATE_SOLID = -2;
37 private static final int CELL_STATE_UNUSED = -1;
47 public int cellAllocationPointer = 0;
48 public int usedCellsCount = 0;
49 public int masterCellSize;
51 public OctreeVolume() {
52 initWorld(1500000, 256 * 64);
55 public void breakSolidCell(final int pointer) {
56 final int color = getCellColor(pointer);
57 final int illumination = getCellIllumination(pointer);
59 ce1[pointer] = makeNewCell(color, illumination);
60 ce2[pointer] = makeNewCell(color, illumination);
61 ce3[pointer] = makeNewCell(color, illumination);
62 ce4[pointer] = makeNewCell(color, illumination);
63 ce5[pointer] = makeNewCell(color, illumination);
64 ce6[pointer] = makeNewCell(color, illumination);
65 ce7[pointer] = makeNewCell(color, illumination);
66 ce8[pointer] = makeNewCell(color, illumination);
69 public void clearCell(final int pointer) {
81 public void deleteCell(final int cellPointer) {
82 clearCell(cellPointer);
83 ce1[cellPointer] = CELL_STATE_UNUSED;
87 public int doesIntersect(final int cubeX, final int cubeY, final int cubeZ,
88 final int cubeSize, final Ray r) {
90 // ray starts inside the cube
91 if ((cubeX - cubeSize) < r.origin.x)
92 if ((cubeX + cubeSize) > r.origin.x)
93 if ((cubeY - cubeSize) < r.origin.y)
94 if ((cubeY + cubeSize) > r.origin.y)
95 if ((cubeZ - cubeSize) < r.origin.z)
96 if ((cubeZ + cubeSize) > r.origin.z) {
97 r.hitPoint = r.origin.clone();
101 if (r.direction.z > 0)
102 if ((cubeZ - cubeSize) > r.origin.z) {
103 final double mult = ((cubeZ - cubeSize) - r.origin.z) / r.direction.z;
104 final double hitX = (r.direction.x * mult) + r.origin.x;
105 if ((cubeX - cubeSize) < hitX)
106 if ((cubeX + cubeSize) > hitX) {
107 final double hitY = (r.direction.y * mult) + r.origin.y;
108 if ((cubeY - cubeSize) < hitY)
109 if ((cubeY + cubeSize) > hitY) {
110 r.hitPoint = new Point3D(hitX, hitY, cubeZ
118 if (r.direction.y > 0)
119 if ((cubeY - cubeSize) > r.origin.y) {
120 final double mult = ((cubeY - cubeSize) - r.origin.y) / r.direction.y;
121 final double hitX = (r.direction.x * mult) + r.origin.x;
122 if ((cubeX - cubeSize) < hitX)
123 if ((cubeX + cubeSize) > hitX) {
124 final double hitZ = (r.direction.z * mult) + r.origin.z;
125 if ((cubeZ - cubeSize) < hitZ)
126 if ((cubeZ + cubeSize) > hitZ) {
127 r.hitPoint = new Point3D(hitX, cubeY - cubeSize,
135 if (r.direction.x > 0)
136 if ((cubeX - cubeSize) > r.origin.x) {
137 final double mult = ((cubeX - cubeSize) - r.origin.x) / r.direction.x;
138 final double hitY = (r.direction.y * mult) + r.origin.y;
139 if ((cubeY - cubeSize) < hitY)
140 if ((cubeY + cubeSize) > hitY) {
141 final double hitZ = (r.direction.z * mult) + r.origin.z;
142 if ((cubeZ - cubeSize) < hitZ)
143 if ((cubeZ + cubeSize) > hitZ) {
144 r.hitPoint = new Point3D(cubeX - cubeSize, hitY,
152 if (r.direction.z < 0)
153 if ((cubeZ + cubeSize) < r.origin.z) {
154 final double mult = ((cubeZ + cubeSize) - r.origin.z) / r.direction.z;
155 final double hitX = (r.direction.x * mult) + r.origin.x;
156 if ((cubeX - cubeSize) < hitX)
157 if ((cubeX + cubeSize) > hitX) {
158 final double hitY = (r.direction.y * mult) + r.origin.y;
159 if ((cubeY - cubeSize) < hitY)
160 if ((cubeY + cubeSize) > hitY) {
161 r.hitPoint = new Point3D(hitX, hitY, cubeZ
169 if (r.direction.y < 0)
170 if ((cubeY + cubeSize) < r.origin.y) {
171 final double mult = ((cubeY + cubeSize) - r.origin.y) / r.direction.y;
172 final double hitX = (r.direction.x * mult) + r.origin.x;
173 if ((cubeX - cubeSize) < hitX)
174 if ((cubeX + cubeSize) > hitX) {
175 final double hitZ = (r.direction.z * mult) + r.origin.z;
176 if ((cubeZ - cubeSize) < hitZ)
177 if ((cubeZ + cubeSize) > hitZ) {
178 r.hitPoint = new Point3D(hitX, cubeY + cubeSize,
186 if (r.direction.x < 0)
187 if ((cubeX + cubeSize) < r.origin.x) {
188 final double mult = ((cubeX + cubeSize) - r.origin.x) / r.direction.x;
189 final double hitY = (r.direction.y * mult) + r.origin.y;
190 if ((cubeY - cubeSize) < hitY)
191 if ((cubeY + cubeSize) > hitY) {
192 final double hitZ = (r.direction.z * mult) + r.origin.z;
193 if ((cubeZ - cubeSize) < hitZ)
194 if ((cubeZ + cubeSize) > hitZ) {
195 r.hitPoint = new Point3D(cubeX + cubeSize, hitY,
207 public void fillRect3D(int x1, int y1, int z1, int x2, int y2, int z2,
228 for (int x = x1; x <= x2; x++)
229 for (int y = y1; y <= y2; y++)
230 for (int z = z1; z <= z2; z++)
231 putCell(x, y, z, 0, 0, 0, masterCellSize, 0, color);
235 public int getCellColor(final int pointer) {
239 public int getCellIllumination(final int pointer) {
243 public void initWorld(final int bufferLength, final int masterCellSize) {
244 // System.out.println("Initializing new world");
246 // initialize world storage buffer
247 this.masterCellSize = masterCellSize;
249 ce1 = new int[bufferLength];
250 ce2 = new int[bufferLength];
251 ce3 = new int[bufferLength];
252 ce4 = new int[bufferLength];
254 ce5 = new int[bufferLength];
255 ce6 = new int[bufferLength];
256 ce7 = new int[bufferLength];
257 ce8 = new int[bufferLength];
259 for (int i = 0; i < bufferLength; i++)
260 ce1[i] = CELL_STATE_UNUSED;
262 // initialize master cell
266 public boolean isCellSolid(final int pointer) {
267 return ce1[pointer] == CELL_STATE_SOLID;
270 public int makeNewCell() {
272 if (cellAllocationPointer >= ce1.length)
273 cellAllocationPointer = 0;
275 if (ce1[cellAllocationPointer] == CELL_STATE_UNUSED) {
277 clearCell(cellAllocationPointer);
280 return cellAllocationPointer;
282 cellAllocationPointer++;
286 public int makeNewCell(final int color, final int illumination) {
287 final int pointer = makeNewCell();
288 markCellAsSolid(pointer);
289 setCellColor(pointer, color);
290 setCellIllumination(pointer, illumination);
294 public void markCellAsSolid(final int pointer) {
295 ce1[pointer] = CELL_STATE_SOLID;
298 public void putCell(final int x, final int y, final int z, final Color color) {
299 putCell(x, y, z, 0, 0, 0, masterCellSize, 0, color);
302 private void putCell(final int x, final int y, final int z,
303 final int cellX, final int cellY, final int cellZ,
304 final int cellSize, final int cellPointer, final Color color) {
308 // if case of big cell
309 if (isCellSolid(cellPointer)) {
311 // if cell is already a needed color, do notheing
312 if (getCellColor(cellPointer) == color.toInt())
315 // otherwise break cell up
316 breakSolidCell(cellPointer);
318 // continue, as if it is cluster now
321 // decide witch subcube to use
323 int subX, subY, subZ;
326 subX = (cellSize / 2) + cellX;
328 subY = (cellSize / 2) + cellY;
330 subZ = (cellSize / 2) + cellZ;
334 subZ = (-cellSize / 2) + cellZ;
339 subY = (-cellSize / 2) + cellY;
341 subZ = (cellSize / 2) + cellZ;
345 subZ = (-cellSize / 2) + cellZ;
351 subX = (-cellSize / 2) + cellX;
353 subY = (cellSize / 2) + cellY;
355 subZ = (cellSize / 2) + cellZ;
359 subZ = (-cellSize / 2) + cellZ;
364 subY = (-cellSize / 2) + cellY;
366 subZ = (cellSize / 2) + cellZ;
370 subZ = (-cellSize / 2) + cellZ;
378 if (subCubeArray[cellPointer] == 0) {
379 // create empty cluster
380 subCubePointer = makeNewCell();
381 subCubeArray[cellPointer] = subCubePointer;
383 subCubePointer = subCubeArray[cellPointer];
385 putCell(x, y, z, subX, subY, subZ, cellSize / 2, subCubePointer,
388 ce1[cellPointer] = CELL_STATE_SOLID;
389 ce2[cellPointer] = color.toInt();
390 ce3[cellPointer] = CELL_STATE_UNUSED;
391 // System.out.println("Cell written!");
395 public void setCellColor(final int pointer, final int color) {
396 ce2[pointer] = color;
399 public void setCellIllumination(final int pointer, final int illumination) {
400 ce3[pointer] = illumination;
404 * Trace ray through the world and return pointer to intersecting cell.
406 * @return pointer to intersecting cell or TRACE_NO_HIT if no intersection.
408 public int traceCell(final int cellX, final int cellY, final int cellZ,
409 final int cellSize, final int pointer, final Ray ray) {
410 if (isCellSolid(pointer)) {
412 if (doesIntersect(cellX, cellY, cellZ, cellSize, ray) != 0) {
413 ray.hitCellSize = cellSize;
414 ray.hitCellX = cellX;
415 ray.hitCellY = cellY;
416 ray.hitCellZ = cellZ;
421 if (doesIntersect(cellX, cellY, cellZ, cellSize, ray) != 0) {
422 final int halfOfCellSize = cellSize / 2;
423 int rayIntersectionResult;
425 if (ray.origin.x > cellX) {
426 if (ray.origin.y > cellY) {
427 if (ray.origin.z > cellZ) {
431 if (ce7[pointer] != 0) {
432 rayIntersectionResult = traceCell(cellX
433 + halfOfCellSize, cellY + halfOfCellSize,
434 cellZ + halfOfCellSize, halfOfCellSize,
436 if (rayIntersectionResult >= 0)
437 return rayIntersectionResult;
439 if (ce6[pointer] != 0) {
440 rayIntersectionResult = traceCell(cellX
441 + halfOfCellSize, cellY - halfOfCellSize,
442 cellZ + halfOfCellSize, halfOfCellSize,
444 if (rayIntersectionResult >= 0)
445 return rayIntersectionResult;
447 if (ce8[pointer] != 0) {
448 rayIntersectionResult = traceCell(cellX
449 - halfOfCellSize, cellY + halfOfCellSize,
450 cellZ + halfOfCellSize, halfOfCellSize,
452 if (rayIntersectionResult >= 0)
453 return rayIntersectionResult;
455 if (ce3[pointer] != 0) {
456 rayIntersectionResult = traceCell(cellX
457 + halfOfCellSize, cellY + halfOfCellSize,
458 cellZ - halfOfCellSize, halfOfCellSize,
460 if (rayIntersectionResult >= 0)
461 return rayIntersectionResult;
464 if (ce2[pointer] != 0) {
465 rayIntersectionResult = traceCell(cellX
466 + halfOfCellSize, cellY - halfOfCellSize,
467 cellZ - halfOfCellSize, halfOfCellSize,
469 if (rayIntersectionResult >= 0)
470 return rayIntersectionResult;
472 if (ce4[pointer] != 0) {
473 rayIntersectionResult = traceCell(cellX
474 - halfOfCellSize, cellY + halfOfCellSize,
475 cellZ - halfOfCellSize, halfOfCellSize,
477 if (rayIntersectionResult >= 0)
478 return rayIntersectionResult;
481 if (ce5[pointer] != 0) {
482 rayIntersectionResult = traceCell(cellX
483 - halfOfCellSize, cellY - halfOfCellSize,
484 cellZ + halfOfCellSize, halfOfCellSize,
486 if (rayIntersectionResult >= 0)
487 return rayIntersectionResult;
490 if (ce1[pointer] != 0) {
491 rayIntersectionResult = traceCell(cellX
492 - halfOfCellSize, cellY - halfOfCellSize,
493 cellZ - halfOfCellSize, halfOfCellSize,
495 if (rayIntersectionResult >= 0)
496 return rayIntersectionResult;
502 if (ce3[pointer] != 0) {
503 rayIntersectionResult = traceCell(cellX
504 + halfOfCellSize, cellY + halfOfCellSize,
505 cellZ - halfOfCellSize, halfOfCellSize,
507 if (rayIntersectionResult >= 0)
508 return rayIntersectionResult;
511 if (ce2[pointer] != 0) {
512 rayIntersectionResult = traceCell(cellX
513 + halfOfCellSize, cellY - halfOfCellSize,
514 cellZ - halfOfCellSize, halfOfCellSize,
516 if (rayIntersectionResult >= 0)
517 return rayIntersectionResult;
519 if (ce4[pointer] != 0) {
520 rayIntersectionResult = traceCell(cellX
521 - halfOfCellSize, cellY + halfOfCellSize,
522 cellZ - halfOfCellSize, halfOfCellSize,
524 if (rayIntersectionResult >= 0)
525 return rayIntersectionResult;
528 if (ce7[pointer] != 0) {
529 rayIntersectionResult = traceCell(cellX
530 + halfOfCellSize, cellY + halfOfCellSize,
531 cellZ + halfOfCellSize, halfOfCellSize,
533 if (rayIntersectionResult >= 0)
534 return rayIntersectionResult;
536 if (ce6[pointer] != 0) {
537 rayIntersectionResult = traceCell(cellX
538 + halfOfCellSize, cellY - halfOfCellSize,
539 cellZ + halfOfCellSize, halfOfCellSize,
541 if (rayIntersectionResult >= 0)
542 return rayIntersectionResult;
544 if (ce8[pointer] != 0) {
545 rayIntersectionResult = traceCell(cellX
546 - halfOfCellSize, cellY + halfOfCellSize,
547 cellZ + halfOfCellSize, halfOfCellSize,
549 if (rayIntersectionResult >= 0)
550 return rayIntersectionResult;
553 if (ce1[pointer] != 0) {
554 rayIntersectionResult = traceCell(cellX
555 - halfOfCellSize, cellY - halfOfCellSize,
556 cellZ - halfOfCellSize, halfOfCellSize,
558 if (rayIntersectionResult >= 0)
559 return rayIntersectionResult;
562 if (ce5[pointer] != 0) {
563 rayIntersectionResult = traceCell(cellX
564 - halfOfCellSize, cellY - halfOfCellSize,
565 cellZ + halfOfCellSize, halfOfCellSize,
567 if (rayIntersectionResult >= 0)
568 return rayIntersectionResult;
572 } else if (ray.origin.z > cellZ) {
575 if (ce6[pointer] != 0) {
576 rayIntersectionResult = traceCell(cellX
577 + halfOfCellSize, cellY - halfOfCellSize, cellZ
578 + halfOfCellSize, halfOfCellSize, ce6[pointer],
580 if (rayIntersectionResult >= 0)
581 return rayIntersectionResult;
584 if (ce7[pointer] != 0) {
585 rayIntersectionResult = traceCell(cellX
586 + halfOfCellSize, cellY + halfOfCellSize, cellZ
587 + halfOfCellSize, halfOfCellSize, ce7[pointer],
589 if (rayIntersectionResult >= 0)
590 return rayIntersectionResult;
592 if (ce2[pointer] != 0) {
593 rayIntersectionResult = traceCell(cellX
594 + halfOfCellSize, cellY - halfOfCellSize, cellZ
595 - halfOfCellSize, halfOfCellSize, ce2[pointer],
597 if (rayIntersectionResult >= 0)
598 return rayIntersectionResult;
600 if (ce5[pointer] != 0) {
601 rayIntersectionResult = traceCell(cellX
602 - halfOfCellSize, cellY - halfOfCellSize, cellZ
603 + halfOfCellSize, halfOfCellSize, ce5[pointer],
605 if (rayIntersectionResult >= 0)
606 return rayIntersectionResult;
608 if (ce8[pointer] != 0) {
609 rayIntersectionResult = traceCell(cellX
610 - halfOfCellSize, cellY + halfOfCellSize, cellZ
611 + halfOfCellSize, halfOfCellSize, ce8[pointer],
613 if (rayIntersectionResult >= 0)
614 return rayIntersectionResult;
616 if (ce3[pointer] != 0) {
617 rayIntersectionResult = traceCell(cellX
618 + halfOfCellSize, cellY + halfOfCellSize, cellZ
619 - halfOfCellSize, halfOfCellSize, ce3[pointer],
621 if (rayIntersectionResult >= 0)
622 return rayIntersectionResult;
625 if (ce1[pointer] != 0) {
626 rayIntersectionResult = traceCell(cellX
627 - halfOfCellSize, cellY - halfOfCellSize, cellZ
628 - halfOfCellSize, halfOfCellSize, ce1[pointer],
630 if (rayIntersectionResult >= 0)
631 return rayIntersectionResult;
633 if (ce4[pointer] != 0) {
634 rayIntersectionResult = traceCell(cellX
635 - halfOfCellSize, cellY + halfOfCellSize, cellZ
636 - halfOfCellSize, halfOfCellSize, ce4[pointer],
638 if (rayIntersectionResult >= 0)
639 return rayIntersectionResult;
645 if (ce2[pointer] != 0) {
646 rayIntersectionResult = traceCell(cellX
647 + halfOfCellSize, cellY - halfOfCellSize, cellZ
648 - halfOfCellSize, halfOfCellSize, ce2[pointer],
650 if (rayIntersectionResult >= 0)
651 return rayIntersectionResult;
654 if (ce3[pointer] != 0) {
655 rayIntersectionResult = traceCell(cellX
656 + halfOfCellSize, cellY + halfOfCellSize, cellZ
657 - halfOfCellSize, halfOfCellSize, ce3[pointer],
659 if (rayIntersectionResult >= 0)
660 return rayIntersectionResult;
663 if (ce1[pointer] != 0) {
664 rayIntersectionResult = traceCell(cellX
665 - halfOfCellSize, cellY - halfOfCellSize, cellZ
666 - halfOfCellSize, halfOfCellSize, ce1[pointer],
668 if (rayIntersectionResult >= 0)
669 return rayIntersectionResult;
671 if (ce6[pointer] != 0) {
672 rayIntersectionResult = traceCell(cellX
673 + halfOfCellSize, cellY - halfOfCellSize, cellZ
674 + halfOfCellSize, halfOfCellSize, ce6[pointer],
676 if (rayIntersectionResult >= 0)
677 return rayIntersectionResult;
680 if (ce7[pointer] != 0) {
681 rayIntersectionResult = traceCell(cellX
682 + halfOfCellSize, cellY + halfOfCellSize, cellZ
683 + halfOfCellSize, halfOfCellSize, ce7[pointer],
685 if (rayIntersectionResult >= 0)
686 return rayIntersectionResult;
688 if (ce5[pointer] != 0) {
689 rayIntersectionResult = traceCell(cellX
690 - halfOfCellSize, cellY - halfOfCellSize, cellZ
691 + halfOfCellSize, halfOfCellSize, ce5[pointer],
693 if (rayIntersectionResult >= 0)
694 return rayIntersectionResult;
696 if (ce4[pointer] != 0) {
697 rayIntersectionResult = traceCell(cellX
698 - halfOfCellSize, cellY + halfOfCellSize, cellZ
699 - halfOfCellSize, halfOfCellSize, ce4[pointer],
701 if (rayIntersectionResult >= 0)
702 return rayIntersectionResult;
704 if (ce8[pointer] != 0) {
705 rayIntersectionResult = traceCell(cellX
706 - halfOfCellSize, cellY + halfOfCellSize, cellZ
707 + halfOfCellSize, halfOfCellSize, ce8[pointer],
709 if (rayIntersectionResult >= 0)
710 return rayIntersectionResult;
714 } else if (ray.origin.y > cellY) {
715 if (ray.origin.z > cellZ) {
719 if (ce8[pointer] != 0) {
720 rayIntersectionResult = traceCell(cellX
721 - halfOfCellSize, cellY + halfOfCellSize, cellZ
722 + halfOfCellSize, halfOfCellSize, ce8[pointer],
724 if (rayIntersectionResult >= 0)
725 return rayIntersectionResult;
727 if (ce7[pointer] != 0) {
728 rayIntersectionResult = traceCell(cellX
729 + halfOfCellSize, cellY + halfOfCellSize, cellZ
730 + halfOfCellSize, halfOfCellSize, ce7[pointer],
732 if (rayIntersectionResult >= 0)
733 return rayIntersectionResult;
735 if (ce5[pointer] != 0) {
736 rayIntersectionResult = traceCell(cellX
737 - halfOfCellSize, cellY - halfOfCellSize, cellZ
738 + halfOfCellSize, halfOfCellSize, ce5[pointer],
740 if (rayIntersectionResult >= 0)
741 return rayIntersectionResult;
743 if (ce4[pointer] != 0) {
744 rayIntersectionResult = traceCell(cellX
745 - halfOfCellSize, cellY + halfOfCellSize, cellZ
746 - halfOfCellSize, halfOfCellSize, ce4[pointer],
748 if (rayIntersectionResult >= 0)
749 return rayIntersectionResult;
752 if (ce3[pointer] != 0) {
753 rayIntersectionResult = traceCell(cellX
754 + halfOfCellSize, cellY + halfOfCellSize, cellZ
755 - halfOfCellSize, halfOfCellSize, ce3[pointer],
757 if (rayIntersectionResult >= 0)
758 return rayIntersectionResult;
761 if (ce1[pointer] != 0) {
762 rayIntersectionResult = traceCell(cellX
763 - halfOfCellSize, cellY - halfOfCellSize, cellZ
764 - halfOfCellSize, halfOfCellSize, ce1[pointer],
766 if (rayIntersectionResult >= 0)
767 return rayIntersectionResult;
769 if (ce6[pointer] != 0) {
770 rayIntersectionResult = traceCell(cellX
771 + halfOfCellSize, cellY - halfOfCellSize, cellZ
772 + halfOfCellSize, halfOfCellSize, ce6[pointer],
774 if (rayIntersectionResult >= 0)
775 return rayIntersectionResult;
778 if (ce2[pointer] != 0) {
779 rayIntersectionResult = traceCell(cellX
780 + halfOfCellSize, cellY - halfOfCellSize, cellZ
781 - halfOfCellSize, halfOfCellSize, ce2[pointer],
783 if (rayIntersectionResult >= 0)
784 return rayIntersectionResult;
791 if (ce4[pointer] != 0) {
792 rayIntersectionResult = traceCell(cellX
793 - halfOfCellSize, cellY + halfOfCellSize, cellZ
794 - halfOfCellSize, halfOfCellSize, ce4[pointer],
796 if (rayIntersectionResult >= 0)
797 return rayIntersectionResult;
800 if (ce8[pointer] != 0) {
801 rayIntersectionResult = traceCell(cellX
802 - halfOfCellSize, cellY + halfOfCellSize, cellZ
803 + halfOfCellSize, halfOfCellSize, ce8[pointer],
805 if (rayIntersectionResult >= 0)
806 return rayIntersectionResult;
808 if (ce3[pointer] != 0) {
809 rayIntersectionResult = traceCell(cellX
810 + halfOfCellSize, cellY + halfOfCellSize, cellZ
811 - halfOfCellSize, halfOfCellSize, ce3[pointer],
813 if (rayIntersectionResult >= 0)
814 return rayIntersectionResult;
817 if (ce1[pointer] != 0) {
818 rayIntersectionResult = traceCell(cellX
819 - halfOfCellSize, cellY - halfOfCellSize, cellZ
820 - halfOfCellSize, halfOfCellSize, ce1[pointer],
822 if (rayIntersectionResult >= 0)
823 return rayIntersectionResult;
825 if (ce7[pointer] != 0) {
826 rayIntersectionResult = traceCell(cellX
827 + halfOfCellSize, cellY + halfOfCellSize, cellZ
828 + halfOfCellSize, halfOfCellSize, ce7[pointer],
830 if (rayIntersectionResult >= 0)
831 return rayIntersectionResult;
833 if (ce5[pointer] != 0) {
834 rayIntersectionResult = traceCell(cellX
835 - halfOfCellSize, cellY - halfOfCellSize, cellZ
836 + halfOfCellSize, halfOfCellSize, ce5[pointer],
838 if (rayIntersectionResult >= 0)
839 return rayIntersectionResult;
842 if (ce2[pointer] != 0) {
843 rayIntersectionResult = traceCell(cellX
844 + halfOfCellSize, cellY - halfOfCellSize, cellZ
845 - halfOfCellSize, halfOfCellSize, ce2[pointer],
847 if (rayIntersectionResult >= 0)
848 return rayIntersectionResult;
850 if (ce6[pointer] != 0) {
851 rayIntersectionResult = traceCell(cellX
852 + halfOfCellSize, cellY - halfOfCellSize, cellZ
853 + halfOfCellSize, halfOfCellSize, ce6[pointer],
855 if (rayIntersectionResult >= 0)
856 return rayIntersectionResult;
860 } else if (ray.origin.z > cellZ) {
864 if (ce5[pointer] != 0) {
865 rayIntersectionResult = traceCell(cellX - halfOfCellSize,
866 cellY - halfOfCellSize, cellZ + halfOfCellSize,
867 halfOfCellSize, ce5[pointer], ray);
868 if (rayIntersectionResult >= 0)
869 return rayIntersectionResult;
872 if (ce1[pointer] != 0) {
873 rayIntersectionResult = traceCell(cellX - halfOfCellSize,
874 cellY - halfOfCellSize, cellZ - halfOfCellSize,
875 halfOfCellSize, ce1[pointer], ray);
876 if (rayIntersectionResult >= 0)
877 return rayIntersectionResult;
880 if (ce6[pointer] != 0) {
881 rayIntersectionResult = traceCell(cellX + halfOfCellSize,
882 cellY - halfOfCellSize, cellZ + halfOfCellSize,
883 halfOfCellSize, ce6[pointer], ray);
884 if (rayIntersectionResult >= 0)
885 return rayIntersectionResult;
888 if (ce8[pointer] != 0) {
889 rayIntersectionResult = traceCell(cellX - halfOfCellSize,
890 cellY + halfOfCellSize, cellZ + halfOfCellSize,
891 halfOfCellSize, ce8[pointer], ray);
892 if (rayIntersectionResult >= 0)
893 return rayIntersectionResult;
896 if (ce4[pointer] != 0) {
897 rayIntersectionResult = traceCell(cellX - halfOfCellSize,
898 cellY + halfOfCellSize, cellZ - halfOfCellSize,
899 halfOfCellSize, ce4[pointer], ray);
900 if (rayIntersectionResult >= 0)
901 return rayIntersectionResult;
904 if (ce7[pointer] != 0) {
905 rayIntersectionResult = traceCell(cellX + halfOfCellSize,
906 cellY + halfOfCellSize, cellZ + halfOfCellSize,
907 halfOfCellSize, ce7[pointer], ray);
908 if (rayIntersectionResult >= 0)
909 return rayIntersectionResult;
912 if (ce2[pointer] != 0) {
913 rayIntersectionResult = traceCell(cellX + halfOfCellSize,
914 cellY - halfOfCellSize, cellZ - halfOfCellSize,
915 halfOfCellSize, ce2[pointer], ray);
916 if (rayIntersectionResult >= 0)
917 return rayIntersectionResult;
920 if (ce3[pointer] != 0) {
921 rayIntersectionResult = traceCell(cellX + halfOfCellSize,
922 cellY + halfOfCellSize, cellZ - halfOfCellSize,
923 halfOfCellSize, ce3[pointer], ray);
924 if (rayIntersectionResult >= 0)
925 return rayIntersectionResult;
932 if (ce1[pointer] != 0) {
933 rayIntersectionResult = traceCell(cellX - halfOfCellSize,
934 cellY - halfOfCellSize, cellZ - halfOfCellSize,
935 halfOfCellSize, ce1[pointer], ray);
936 if (rayIntersectionResult >= 0)
937 return rayIntersectionResult;
940 if (ce5[pointer] != 0) {
941 rayIntersectionResult = traceCell(cellX - halfOfCellSize,
942 cellY - halfOfCellSize, cellZ + halfOfCellSize,
943 halfOfCellSize, ce5[pointer], ray);
944 if (rayIntersectionResult >= 0)
945 return rayIntersectionResult;
947 if (ce2[pointer] != 0) {
948 rayIntersectionResult = traceCell(cellX + halfOfCellSize,
949 cellY - halfOfCellSize, cellZ - halfOfCellSize,
950 halfOfCellSize, ce2[pointer], ray);
951 if (rayIntersectionResult >= 0)
952 return rayIntersectionResult;
955 if (ce4[pointer] != 0) {
956 rayIntersectionResult = traceCell(cellX - halfOfCellSize,
957 cellY + halfOfCellSize, cellZ - halfOfCellSize,
958 halfOfCellSize, ce4[pointer], ray);
959 if (rayIntersectionResult >= 0)
960 return rayIntersectionResult;
963 if (ce6[pointer] != 0) {
964 rayIntersectionResult = traceCell(cellX + halfOfCellSize,
965 cellY - halfOfCellSize, cellZ + halfOfCellSize,
966 halfOfCellSize, ce6[pointer], ray);
967 if (rayIntersectionResult >= 0)
968 return rayIntersectionResult;
971 if (ce8[pointer] != 0) {
972 rayIntersectionResult = traceCell(cellX - halfOfCellSize,
973 cellY + halfOfCellSize, cellZ + halfOfCellSize,
974 halfOfCellSize, ce8[pointer], ray);
975 if (rayIntersectionResult >= 0)
976 return rayIntersectionResult;
979 if (ce3[pointer] != 0) {
980 rayIntersectionResult = traceCell(cellX + halfOfCellSize,
981 cellY + halfOfCellSize, cellZ - halfOfCellSize,
982 halfOfCellSize, ce3[pointer], ray);
983 if (rayIntersectionResult >= 0)
984 return rayIntersectionResult;
986 if (ce7[pointer] != 0) {
987 rayIntersectionResult = traceCell(cellX + halfOfCellSize,
988 cellY + halfOfCellSize, cellZ + halfOfCellSize,
989 halfOfCellSize, ce7[pointer], ray);
990 if (rayIntersectionResult >= 0)
991 return rayIntersectionResult;