2 * Sixth 3D engine. Copyright ©2012-2018, Svjatoslav Agejenko, svjatoslav@svjatoslav.eu
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.
10 package eu.svjatoslav.sixth.e3d.renderer.octree;
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;
18 * There are 3 cell types:
25 * visible color, after being illuminated by nearby light sources
28 * contains pointers to 8 sub cells
32 public class OctreeVolume {
34 public static final int TRACE_NO_HIT = -1;
38 private static final int CELL_STATE_SOLID = -2;
39 private static final int CELL_STATE_UNUSED = -1;
40 final LineAppearance factory = new LineAppearance();
49 public int cellAllocationPointer = 0;
50 public int usedCellsCount = 0;
51 public int masterCellSize;
53 public OctreeVolume() {
54 initWorld(1500000, 256 * 64);
57 public void breakSolidCell(final int pointer) {
58 final int color = getCellColor(pointer);
59 final int illumination = getCellIllumination(pointer);
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);
71 public void clearCell(final int pointer) {
83 public void deleteCell(final int cellPointer) {
84 clearCell(cellPointer);
85 ce1[cellPointer] = CELL_STATE_UNUSED;
89 public int doesIntersect(final int cubeX, final int cubeY, final int cubeZ,
90 final int cubeSize, final Ray r) {
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) {
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) {
116 r.hitZ = cubeZ - cubeSize;
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) {
133 r.hitY = cubeY - cubeSize;
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;
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) {
170 r.hitZ = cubeZ + cubeSize;
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) {
187 r.hitY = cubeY + cubeSize;
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;
217 public void fillRect3D(int x1, int y1, int z1, int x2, int y2, int z2,
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);
245 public int getCellColor(final int pointer) {
249 public int getCellIllumination(final int pointer) {
253 public void initWorld(final int bufferLength, final int masterCellSize) {
254 // System.out.println("Initializing new world");
256 // initialize world storage buffer
257 this.masterCellSize = masterCellSize;
259 ce1 = new int[bufferLength];
260 ce2 = new int[bufferLength];
261 ce3 = new int[bufferLength];
262 ce4 = new int[bufferLength];
264 ce5 = new int[bufferLength];
265 ce6 = new int[bufferLength];
266 ce7 = new int[bufferLength];
267 ce8 = new int[bufferLength];
269 for (int i = 0; i < bufferLength; i++)
270 ce1[i] = CELL_STATE_UNUSED;
272 // initialize master cell
276 public boolean isCellSolid(final int pointer) {
277 return ce1[pointer] == CELL_STATE_SOLID;
280 public int makeNewCell() {
282 if (cellAllocationPointer >= ce1.length)
283 cellAllocationPointer = 0;
285 if (ce1[cellAllocationPointer] == CELL_STATE_UNUSED) {
287 clearCell(cellAllocationPointer);
290 return cellAllocationPointer;
292 cellAllocationPointer++;
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);
304 public void markCellAsSolid(final int pointer) {
305 ce1[pointer] = CELL_STATE_SOLID;
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);
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) {
318 // if case of big cell
319 if (isCellSolid(cellPointer)) {
321 // if cell is already a needed color, do notheing
322 if (getCellColor(cellPointer) == color.toInt())
325 // otherwise break cell up
326 breakSolidCell(cellPointer);
328 // continue, as if it is cluster now
331 // decide witch subcube to use
333 int subX, subY, subZ;
336 subX = (cellSize / 2) + cellX;
338 subY = (cellSize / 2) + cellY;
340 subZ = (cellSize / 2) + cellZ;
344 subZ = (-cellSize / 2) + cellZ;
349 subY = (-cellSize / 2) + cellY;
351 subZ = (cellSize / 2) + cellZ;
355 subZ = (-cellSize / 2) + cellZ;
361 subX = (-cellSize / 2) + cellX;
363 subY = (cellSize / 2) + cellY;
365 subZ = (cellSize / 2) + cellZ;
369 subZ = (-cellSize / 2) + cellZ;
374 subY = (-cellSize / 2) + cellY;
376 subZ = (cellSize / 2) + cellZ;
380 subZ = (-cellSize / 2) + cellZ;
388 if (subCubeArray[cellPointer] == 0) {
389 // create empty cluster
390 subCubePointer = makeNewCell();
391 subCubeArray[cellPointer] = subCubePointer;
393 subCubePointer = subCubeArray[cellPointer];
395 putCell(x, y, z, subX, subY, subZ, cellSize / 2, subCubePointer,
398 ce1[cellPointer] = CELL_STATE_SOLID;
399 ce2[cellPointer] = color.toInt();
400 ce3[cellPointer] = CELL_STATE_UNUSED;
401 // System.out.println("Cell written!");
405 public void setCellColor(final int pointer, final int color) {
406 ce2[pointer] = color;
409 public void setCellIllumination(final int pointer, final int illumination) {
410 ce3[pointer] = illumination;
414 * @return intersecting cell pointer or -1 if no cell in intersecting this
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)) {
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;
430 if (doesIntersect(cellX, cellY, cellZ, cellSize, ray) != 0) {
431 final int halfOfCellSize = cellSize / 2;
432 int rayIntersectionResult;
440 if (ce7[pointer] != 0) {
441 rayIntersectionResult = traceCell(cellX
442 + halfOfCellSize, cellY + halfOfCellSize,
443 cellZ + halfOfCellSize, halfOfCellSize,
445 if (rayIntersectionResult >= 0)
446 return rayIntersectionResult;
448 if (ce6[pointer] != 0) {
449 rayIntersectionResult = traceCell(cellX
450 + halfOfCellSize, cellY - halfOfCellSize,
451 cellZ + halfOfCellSize, halfOfCellSize,
453 if (rayIntersectionResult >= 0)
454 return rayIntersectionResult;
456 if (ce8[pointer] != 0) {
457 rayIntersectionResult = traceCell(cellX
458 - halfOfCellSize, cellY + halfOfCellSize,
459 cellZ + halfOfCellSize, halfOfCellSize,
461 if (rayIntersectionResult >= 0)
462 return rayIntersectionResult;
464 if (ce3[pointer] != 0) {
465 rayIntersectionResult = traceCell(cellX
466 + halfOfCellSize, cellY + halfOfCellSize,
467 cellZ - halfOfCellSize, halfOfCellSize,
469 if (rayIntersectionResult >= 0)
470 return rayIntersectionResult;
473 if (ce2[pointer] != 0) {
474 rayIntersectionResult = traceCell(cellX
475 + halfOfCellSize, cellY - halfOfCellSize,
476 cellZ - halfOfCellSize, halfOfCellSize,
478 if (rayIntersectionResult >= 0)
479 return rayIntersectionResult;
481 if (ce4[pointer] != 0) {
482 rayIntersectionResult = traceCell(cellX
483 - halfOfCellSize, cellY + halfOfCellSize,
484 cellZ - halfOfCellSize, halfOfCellSize,
486 if (rayIntersectionResult >= 0)
487 return rayIntersectionResult;
490 if (ce5[pointer] != 0) {
491 rayIntersectionResult = traceCell(cellX
492 - halfOfCellSize, cellY - halfOfCellSize,
493 cellZ + halfOfCellSize, halfOfCellSize,
495 if (rayIntersectionResult >= 0)
496 return rayIntersectionResult;
499 if (ce1[pointer] != 0) {
500 rayIntersectionResult = traceCell(cellX
501 - halfOfCellSize, cellY - halfOfCellSize,
502 cellZ - halfOfCellSize, halfOfCellSize,
504 if (rayIntersectionResult >= 0)
505 return rayIntersectionResult;
511 if (ce3[pointer] != 0) {
512 rayIntersectionResult = traceCell(cellX
513 + halfOfCellSize, cellY + halfOfCellSize,
514 cellZ - halfOfCellSize, halfOfCellSize,
516 if (rayIntersectionResult >= 0)
517 return rayIntersectionResult;
520 if (ce2[pointer] != 0) {
521 rayIntersectionResult = traceCell(cellX
522 + halfOfCellSize, cellY - halfOfCellSize,
523 cellZ - halfOfCellSize, halfOfCellSize,
525 if (rayIntersectionResult >= 0)
526 return rayIntersectionResult;
528 if (ce4[pointer] != 0) {
529 rayIntersectionResult = traceCell(cellX
530 - halfOfCellSize, cellY + halfOfCellSize,
531 cellZ - halfOfCellSize, halfOfCellSize,
533 if (rayIntersectionResult >= 0)
534 return rayIntersectionResult;
537 if (ce7[pointer] != 0) {
538 rayIntersectionResult = traceCell(cellX
539 + halfOfCellSize, cellY + halfOfCellSize,
540 cellZ + halfOfCellSize, halfOfCellSize,
542 if (rayIntersectionResult >= 0)
543 return rayIntersectionResult;
545 if (ce6[pointer] != 0) {
546 rayIntersectionResult = traceCell(cellX
547 + halfOfCellSize, cellY - halfOfCellSize,
548 cellZ + halfOfCellSize, halfOfCellSize,
550 if (rayIntersectionResult >= 0)
551 return rayIntersectionResult;
553 if (ce8[pointer] != 0) {
554 rayIntersectionResult = traceCell(cellX
555 - halfOfCellSize, cellY + halfOfCellSize,
556 cellZ + halfOfCellSize, halfOfCellSize,
558 if (rayIntersectionResult >= 0)
559 return rayIntersectionResult;
562 if (ce1[pointer] != 0) {
563 rayIntersectionResult = traceCell(cellX
564 - halfOfCellSize, cellY - halfOfCellSize,
565 cellZ - halfOfCellSize, halfOfCellSize,
567 if (rayIntersectionResult >= 0)
568 return rayIntersectionResult;
571 if (ce5[pointer] != 0) {
572 rayIntersectionResult = traceCell(cellX
573 - halfOfCellSize, cellY - halfOfCellSize,
574 cellZ + halfOfCellSize, halfOfCellSize,
576 if (rayIntersectionResult >= 0)
577 return rayIntersectionResult;
581 } else if (ray.z > cellZ) {
584 if (ce6[pointer] != 0) {
585 rayIntersectionResult = traceCell(cellX
586 + halfOfCellSize, cellY - halfOfCellSize, cellZ
587 + halfOfCellSize, halfOfCellSize, ce6[pointer],
589 if (rayIntersectionResult >= 0)
590 return rayIntersectionResult;
593 if (ce7[pointer] != 0) {
594 rayIntersectionResult = traceCell(cellX
595 + halfOfCellSize, cellY + halfOfCellSize, cellZ
596 + halfOfCellSize, halfOfCellSize, ce7[pointer],
598 if (rayIntersectionResult >= 0)
599 return rayIntersectionResult;
601 if (ce2[pointer] != 0) {
602 rayIntersectionResult = traceCell(cellX
603 + halfOfCellSize, cellY - halfOfCellSize, cellZ
604 - halfOfCellSize, halfOfCellSize, ce2[pointer],
606 if (rayIntersectionResult >= 0)
607 return rayIntersectionResult;
609 if (ce5[pointer] != 0) {
610 rayIntersectionResult = traceCell(cellX
611 - halfOfCellSize, cellY - halfOfCellSize, cellZ
612 + halfOfCellSize, halfOfCellSize, ce5[pointer],
614 if (rayIntersectionResult >= 0)
615 return rayIntersectionResult;
617 if (ce8[pointer] != 0) {
618 rayIntersectionResult = traceCell(cellX
619 - halfOfCellSize, cellY + halfOfCellSize, cellZ
620 + halfOfCellSize, halfOfCellSize, ce8[pointer],
622 if (rayIntersectionResult >= 0)
623 return rayIntersectionResult;
625 if (ce3[pointer] != 0) {
626 rayIntersectionResult = traceCell(cellX
627 + halfOfCellSize, cellY + halfOfCellSize, cellZ
628 - halfOfCellSize, halfOfCellSize, ce3[pointer],
630 if (rayIntersectionResult >= 0)
631 return rayIntersectionResult;
634 if (ce1[pointer] != 0) {
635 rayIntersectionResult = traceCell(cellX
636 - halfOfCellSize, cellY - halfOfCellSize, cellZ
637 - halfOfCellSize, halfOfCellSize, ce1[pointer],
639 if (rayIntersectionResult >= 0)
640 return rayIntersectionResult;
642 if (ce4[pointer] != 0) {
643 rayIntersectionResult = traceCell(cellX
644 - halfOfCellSize, cellY + halfOfCellSize, cellZ
645 - halfOfCellSize, halfOfCellSize, ce4[pointer],
647 if (rayIntersectionResult >= 0)
648 return rayIntersectionResult;
654 if (ce2[pointer] != 0) {
655 rayIntersectionResult = traceCell(cellX
656 + halfOfCellSize, cellY - halfOfCellSize, cellZ
657 - halfOfCellSize, halfOfCellSize, ce2[pointer],
659 if (rayIntersectionResult >= 0)
660 return rayIntersectionResult;
663 if (ce3[pointer] != 0) {
664 rayIntersectionResult = traceCell(cellX
665 + halfOfCellSize, cellY + halfOfCellSize, cellZ
666 - halfOfCellSize, halfOfCellSize, ce3[pointer],
668 if (rayIntersectionResult >= 0)
669 return rayIntersectionResult;
672 if (ce1[pointer] != 0) {
673 rayIntersectionResult = traceCell(cellX
674 - halfOfCellSize, cellY - halfOfCellSize, cellZ
675 - halfOfCellSize, halfOfCellSize, ce1[pointer],
677 if (rayIntersectionResult >= 0)
678 return rayIntersectionResult;
680 if (ce6[pointer] != 0) {
681 rayIntersectionResult = traceCell(cellX
682 + halfOfCellSize, cellY - halfOfCellSize, cellZ
683 + halfOfCellSize, halfOfCellSize, ce6[pointer],
685 if (rayIntersectionResult >= 0)
686 return rayIntersectionResult;
689 if (ce7[pointer] != 0) {
690 rayIntersectionResult = traceCell(cellX
691 + halfOfCellSize, cellY + halfOfCellSize, cellZ
692 + halfOfCellSize, halfOfCellSize, ce7[pointer],
694 if (rayIntersectionResult >= 0)
695 return rayIntersectionResult;
697 if (ce5[pointer] != 0) {
698 rayIntersectionResult = traceCell(cellX
699 - halfOfCellSize, cellY - halfOfCellSize, cellZ
700 + halfOfCellSize, halfOfCellSize, ce5[pointer],
702 if (rayIntersectionResult >= 0)
703 return rayIntersectionResult;
705 if (ce4[pointer] != 0) {
706 rayIntersectionResult = traceCell(cellX
707 - halfOfCellSize, cellY + halfOfCellSize, cellZ
708 - halfOfCellSize, halfOfCellSize, ce4[pointer],
710 if (rayIntersectionResult >= 0)
711 return rayIntersectionResult;
713 if (ce8[pointer] != 0) {
714 rayIntersectionResult = traceCell(cellX
715 - halfOfCellSize, cellY + halfOfCellSize, cellZ
716 + halfOfCellSize, halfOfCellSize, ce8[pointer],
718 if (rayIntersectionResult >= 0)
719 return rayIntersectionResult;
723 } else if (ray.y > cellY) {
728 if (ce8[pointer] != 0) {
729 rayIntersectionResult = traceCell(cellX
730 - halfOfCellSize, cellY + halfOfCellSize, cellZ
731 + halfOfCellSize, halfOfCellSize, ce8[pointer],
733 if (rayIntersectionResult >= 0)
734 return rayIntersectionResult;
736 if (ce7[pointer] != 0) {
737 rayIntersectionResult = traceCell(cellX
738 + halfOfCellSize, cellY + halfOfCellSize, cellZ
739 + halfOfCellSize, halfOfCellSize, ce7[pointer],
741 if (rayIntersectionResult >= 0)
742 return rayIntersectionResult;
744 if (ce5[pointer] != 0) {
745 rayIntersectionResult = traceCell(cellX
746 - halfOfCellSize, cellY - halfOfCellSize, cellZ
747 + halfOfCellSize, halfOfCellSize, ce5[pointer],
749 if (rayIntersectionResult >= 0)
750 return rayIntersectionResult;
752 if (ce4[pointer] != 0) {
753 rayIntersectionResult = traceCell(cellX
754 - halfOfCellSize, cellY + halfOfCellSize, cellZ
755 - halfOfCellSize, halfOfCellSize, ce4[pointer],
757 if (rayIntersectionResult >= 0)
758 return rayIntersectionResult;
761 if (ce3[pointer] != 0) {
762 rayIntersectionResult = traceCell(cellX
763 + halfOfCellSize, cellY + halfOfCellSize, cellZ
764 - halfOfCellSize, halfOfCellSize, ce3[pointer],
766 if (rayIntersectionResult >= 0)
767 return rayIntersectionResult;
770 if (ce1[pointer] != 0) {
771 rayIntersectionResult = traceCell(cellX
772 - halfOfCellSize, cellY - halfOfCellSize, cellZ
773 - halfOfCellSize, halfOfCellSize, ce1[pointer],
775 if (rayIntersectionResult >= 0)
776 return rayIntersectionResult;
778 if (ce6[pointer] != 0) {
779 rayIntersectionResult = traceCell(cellX
780 + halfOfCellSize, cellY - halfOfCellSize, cellZ
781 + halfOfCellSize, halfOfCellSize, ce6[pointer],
783 if (rayIntersectionResult >= 0)
784 return rayIntersectionResult;
787 if (ce2[pointer] != 0) {
788 rayIntersectionResult = traceCell(cellX
789 + halfOfCellSize, cellY - halfOfCellSize, cellZ
790 - halfOfCellSize, halfOfCellSize, ce2[pointer],
792 if (rayIntersectionResult >= 0)
793 return rayIntersectionResult;
800 if (ce4[pointer] != 0) {
801 rayIntersectionResult = traceCell(cellX
802 - halfOfCellSize, cellY + halfOfCellSize, cellZ
803 - halfOfCellSize, halfOfCellSize, ce4[pointer],
805 if (rayIntersectionResult >= 0)
806 return rayIntersectionResult;
809 if (ce8[pointer] != 0) {
810 rayIntersectionResult = traceCell(cellX
811 - halfOfCellSize, cellY + halfOfCellSize, cellZ
812 + halfOfCellSize, halfOfCellSize, ce8[pointer],
814 if (rayIntersectionResult >= 0)
815 return rayIntersectionResult;
817 if (ce3[pointer] != 0) {
818 rayIntersectionResult = traceCell(cellX
819 + halfOfCellSize, cellY + halfOfCellSize, cellZ
820 - halfOfCellSize, halfOfCellSize, ce3[pointer],
822 if (rayIntersectionResult >= 0)
823 return rayIntersectionResult;
826 if (ce1[pointer] != 0) {
827 rayIntersectionResult = traceCell(cellX
828 - halfOfCellSize, cellY - halfOfCellSize, cellZ
829 - halfOfCellSize, halfOfCellSize, ce1[pointer],
831 if (rayIntersectionResult >= 0)
832 return rayIntersectionResult;
834 if (ce7[pointer] != 0) {
835 rayIntersectionResult = traceCell(cellX
836 + halfOfCellSize, cellY + halfOfCellSize, cellZ
837 + halfOfCellSize, halfOfCellSize, ce7[pointer],
839 if (rayIntersectionResult >= 0)
840 return rayIntersectionResult;
842 if (ce5[pointer] != 0) {
843 rayIntersectionResult = traceCell(cellX
844 - halfOfCellSize, cellY - halfOfCellSize, cellZ
845 + halfOfCellSize, halfOfCellSize, ce5[pointer],
847 if (rayIntersectionResult >= 0)
848 return rayIntersectionResult;
851 if (ce2[pointer] != 0) {
852 rayIntersectionResult = traceCell(cellX
853 + halfOfCellSize, cellY - halfOfCellSize, cellZ
854 - halfOfCellSize, halfOfCellSize, ce2[pointer],
856 if (rayIntersectionResult >= 0)
857 return rayIntersectionResult;
859 if (ce6[pointer] != 0) {
860 rayIntersectionResult = traceCell(cellX
861 + halfOfCellSize, cellY - halfOfCellSize, cellZ
862 + halfOfCellSize, halfOfCellSize, ce6[pointer],
864 if (rayIntersectionResult >= 0)
865 return rayIntersectionResult;
869 } else if (ray.z > cellZ) {
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;
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;
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;
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;
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;
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;
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;
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;
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;
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;
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;
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;
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;
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;
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;
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;
1004 return TRACE_NO_HIT;