Removed ViewListener interface. Renamed View to ViewPanel.
[sixth-3d.git] / 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 }