+/*
+ * Sixth - System for data storage, computation, exploration and interaction.
+ * Copyright ©2012-2016, Svjatoslav Agejenko, svjatoslav@svjatoslav.eu
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 3 of the GNU Lesser General Public License
+ * or later as published by the Free Software Foundation.
+ */
+
+package eu.svjatoslav.sixth.e3d.renderer.octree;
+
+import eu.svjatoslav.sixth.e3d.renderer.octree.raytracer.Ray;
+import eu.svjatoslav.sixth.e3d.renderer.raster.Color;
+import eu.svjatoslav.sixth.e3d.renderer.raster.shapes.basic.line.LineAppearance;
+
+/**
+ * <pre>
+ * There are 3 cell types:
+ *
+ * UNUSED
+ *
+ * SOLID
+ * contains:
+ * original color
+ * visible color, after being illuminated by nearby light sources
+ *
+ * CLUSTER
+ * contains pointers to 8 sub cells
+ * </pre>
+ */
+
+public class OctreeVolume {
+
+ public static final int TRACE_NO_HIT = -1;
+ /**
+ * Single solid color.
+ */
+ private static final int CELL_STATE_SOLID = -2;
+ private static final int CELL_STATE_UNUSED = -1;
+ final LineAppearance factory = new LineAppearance();
+ public int ce1[];
+ public int ce2[];
+ public int ce3[];
+ public int ce4[];
+ public int ce5[];
+ public int ce6[];
+ public int ce7[];
+ public int ce8[];
+ public int cellAllocationPointer = 0;
+ public int usedCellsCount = 0;
+ public int masterCellSize;
+
+ public OctreeVolume() {
+ initWorld(1500000, 256 * 64);
+ }
+
+ public void breakSolidCell(final int pointer) {
+ final int color = getCellColor(pointer);
+ final int illumination = getCellIllumination(pointer);
+
+ ce1[pointer] = makeNewCell(color, illumination);
+ ce2[pointer] = makeNewCell(color, illumination);
+ ce3[pointer] = makeNewCell(color, illumination);
+ ce4[pointer] = makeNewCell(color, illumination);
+ ce5[pointer] = makeNewCell(color, illumination);
+ ce6[pointer] = makeNewCell(color, illumination);
+ ce7[pointer] = makeNewCell(color, illumination);
+ ce8[pointer] = makeNewCell(color, illumination);
+ }
+
+ public void clearCell(final int pointer) {
+ ce1[pointer] = 0;
+ ce2[pointer] = 0;
+ ce3[pointer] = 0;
+ ce4[pointer] = 0;
+
+ ce5[pointer] = 0;
+ ce6[pointer] = 0;
+ ce7[pointer] = 0;
+ ce8[pointer] = 0;
+ }
+
+ public void deleteCell(final int cellPointer) {
+ clearCell(cellPointer);
+ ce1[cellPointer] = CELL_STATE_UNUSED;
+ usedCellsCount--;
+ }
+
+ public int doesIntersect(final int cubeX, final int cubeY, final int cubeZ,
+ final int cubeSize, final Ray r) {
+
+ // ray starts inside the cube
+ if ((cubeX - cubeSize) < r.x)
+ if ((cubeX + cubeSize) > r.x)
+ if ((cubeY - cubeSize) < r.y)
+ if ((cubeY + cubeSize) > r.y)
+ if ((cubeZ - cubeSize) < r.z)
+ if ((cubeZ + cubeSize) > r.z) {
+ r.hitX = r.x;
+ r.hitY = r.y;
+ r.hitZ = r.z;
+ return 1;
+ }
+ // back face
+ if (r.zp > 0)
+ if ((cubeZ - cubeSize) > r.z) {
+ final double mult = ((cubeZ - cubeSize) - r.z) / r.zp;
+ final double hitX = (r.xp * mult) + r.x;
+ if ((cubeX - cubeSize) < hitX)
+ if ((cubeX + cubeSize) > hitX) {
+ final double hitY = (r.yp * mult) + r.y;
+ if ((cubeY - cubeSize) < hitY)
+ if ((cubeY + cubeSize) > hitY) {
+ r.hitX = hitX;
+ r.hitY = hitY;
+ r.hitZ = cubeZ - cubeSize;
+ return 2;
+ }
+ }
+ }
+
+ // up face
+ if (r.yp > 0)
+ if ((cubeY - cubeSize) > r.y) {
+ final double mult = ((cubeY - cubeSize) - r.y) / r.yp;
+ final double hitX = (r.xp * mult) + r.x;
+ if ((cubeX - cubeSize) < hitX)
+ if ((cubeX + cubeSize) > hitX) {
+ final double hitZ = (r.zp * mult) + r.z;
+ if ((cubeZ - cubeSize) < hitZ)
+ if ((cubeZ + cubeSize) > hitZ) {
+ r.hitX = hitX;
+ r.hitY = cubeY - cubeSize;
+ r.hitZ = hitZ;
+ return 3;
+ }
+ }
+ }
+
+ // left face
+ if (r.xp > 0)
+ if ((cubeX - cubeSize) > r.x) {
+ final double mult = ((cubeX - cubeSize) - r.x) / r.xp;
+ final double hitY = (r.yp * mult) + r.y;
+ if ((cubeY - cubeSize) < hitY)
+ if ((cubeY + cubeSize) > hitY) {
+ final double hitZ = (r.zp * mult) + r.z;
+ if ((cubeZ - cubeSize) < hitZ)
+ if ((cubeZ + cubeSize) > hitZ) {
+ r.hitX = cubeX - cubeSize;
+ r.hitY = hitY;
+ r.hitZ = hitZ;
+ return 4;
+ }
+ }
+ }
+
+ // front face
+ if (r.zp < 0)
+ if ((cubeZ + cubeSize) < r.z) {
+ final double mult = ((cubeZ + cubeSize) - r.z) / r.zp;
+ final double hitX = (r.xp * mult) + r.x;
+ if ((cubeX - cubeSize) < hitX)
+ if ((cubeX + cubeSize) > hitX) {
+ final double hitY = (r.yp * mult) + r.y;
+ if ((cubeY - cubeSize) < hitY)
+ if ((cubeY + cubeSize) > hitY) {
+ r.hitX = hitX;
+ r.hitY = hitY;
+ r.hitZ = cubeZ + cubeSize;
+ return 5;
+ }
+ }
+ }
+
+ // down face
+ if (r.yp < 0)
+ if ((cubeY + cubeSize) < r.y) {
+ final double mult = ((cubeY + cubeSize) - r.y) / r.yp;
+ final double hitX = (r.xp * mult) + r.x;
+ if ((cubeX - cubeSize) < hitX)
+ if ((cubeX + cubeSize) > hitX) {
+ final double hitZ = (r.zp * mult) + r.z;
+ if ((cubeZ - cubeSize) < hitZ)
+ if ((cubeZ + cubeSize) > hitZ) {
+ r.hitX = hitX;
+ r.hitY = cubeY + cubeSize;
+ r.hitZ = hitZ;
+ return 6;
+ }
+ }
+ }
+
+ // right face
+ if (r.xp < 0)
+ if ((cubeX + cubeSize) < r.x) {
+ final double mult = ((cubeX + cubeSize) - r.x) / r.xp;
+ final double hitY = (r.yp * mult) + r.y;
+ if ((cubeY - cubeSize) < hitY)
+ if ((cubeY + cubeSize) > hitY) {
+ final double hitZ = (r.zp * mult) + r.z;
+ if ((cubeZ - cubeSize) < hitZ)
+ if ((cubeZ + cubeSize) > hitZ) {
+ r.hitX = cubeX + cubeSize;
+ r.hitY = hitY;
+ r.hitZ = hitZ;
+ return 7;
+ }
+ }
+ }
+ return 0;
+ }
+
+ /**
+ * Fill 3D rectangle.
+ */
+ public void fillRect3D(int x1, int y1, int z1, int x2, int y2, int z2,
+ final Color color) {
+ int t;
+ if (x1 > x2) {
+ t = x1;
+ x1 = x2;
+ x2 = t;
+ }
+
+ if (y1 > y2) {
+ t = y1;
+ y1 = y2;
+ y2 = t;
+ }
+
+ if (z1 > z2) {
+ t = z1;
+ z1 = z2;
+ z2 = t;
+ }
+
+ for (int x = x1; x <= x2; x++)
+ for (int y = y1; y <= y2; y++)
+ for (int z = z1; z <= z2; z++)
+ putCell(x, y, z, 0, 0, 0, masterCellSize, 0, color);
+
+ }
+
+ public int getCellColor(final int pointer) {
+ return ce2[pointer];
+ }
+
+ public int getCellIllumination(final int pointer) {
+ return ce3[pointer];
+ }
+
+ public void initWorld(final int bufferLength, final int masterCellSize) {
+ // System.out.println("Initializing new world");
+
+ // initialize world storage buffer
+ this.masterCellSize = masterCellSize;
+
+ ce1 = new int[bufferLength];
+ ce2 = new int[bufferLength];
+ ce3 = new int[bufferLength];
+ ce4 = new int[bufferLength];
+
+ ce5 = new int[bufferLength];
+ ce6 = new int[bufferLength];
+ ce7 = new int[bufferLength];
+ ce8 = new int[bufferLength];
+
+ for (int i = 0; i < bufferLength; i++)
+ ce1[i] = CELL_STATE_UNUSED;
+
+ // initialize master cell
+ clearCell(0);
+ }
+
+ public boolean isCellSolid(final int pointer) {
+ return ce1[pointer] == CELL_STATE_SOLID;
+ }
+
+ public int makeNewCell() {
+ for (; ; ) {
+ if (cellAllocationPointer >= ce1.length)
+ cellAllocationPointer = 0;
+
+ if (ce1[cellAllocationPointer] == CELL_STATE_UNUSED) {
+
+ clearCell(cellAllocationPointer);
+
+ usedCellsCount++;
+ return cellAllocationPointer;
+ } else
+ cellAllocationPointer++;
+ }
+ }
+
+ public int makeNewCell(final int color, final int illumination) {
+ final int pointer = makeNewCell();
+ markCellAsSolid(pointer);
+ setCellColor(pointer, color);
+ setCellIllumination(pointer, illumination);
+ return pointer;
+ }
+
+ public void markCellAsSolid(final int pointer) {
+ ce1[pointer] = CELL_STATE_SOLID;
+ }
+
+ public void putCell(final int x, final int y, final int z, final Color color) {
+ putCell(x, y, z, 0, 0, 0, masterCellSize, 0, color);
+ }
+
+ private void putCell(final int x, final int y, final int z,
+ final int cellX, final int cellY, final int cellZ,
+ final int cellSize, final int cellPointer, final Color color) {
+
+ if (cellSize > 1) {
+
+ // if case of big cell
+ if (isCellSolid(cellPointer)) {
+
+ // if cell is already a needed color, do notheing
+ if (getCellColor(cellPointer) == color.toInt())
+ return;
+
+ // otherwise break cell up
+ breakSolidCell(cellPointer);
+
+ // continue, as if it is cluster now
+ }
+
+ // decide witch subcube to use
+ int subCubeArray[];
+ int subX, subY, subZ;
+
+ if (x > cellX) {
+ subX = (cellSize / 2) + cellX;
+ if (y > cellY) {
+ subY = (cellSize / 2) + cellY;
+ if (z > cellZ) {
+ subZ = (cellSize / 2) + cellZ;
+ // 7
+ subCubeArray = ce7;
+ } else {
+ subZ = (-cellSize / 2) + cellZ;
+ // 3
+ subCubeArray = ce3;
+ }
+ } else {
+ subY = (-cellSize / 2) + cellY;
+ if (z > cellZ) {
+ subZ = (cellSize / 2) + cellZ;
+ // 6
+ subCubeArray = ce6;
+ } else {
+ subZ = (-cellSize / 2) + cellZ;
+ // 2
+ subCubeArray = ce2;
+ }
+ }
+ } else {
+ subX = (-cellSize / 2) + cellX;
+ if (y > cellY) {
+ subY = (cellSize / 2) + cellY;
+ if (z > cellZ) {
+ subZ = (cellSize / 2) + cellZ;
+ // 8
+ subCubeArray = ce8;
+ } else {
+ subZ = (-cellSize / 2) + cellZ;
+ // 4
+ subCubeArray = ce4;
+ }
+ } else {
+ subY = (-cellSize / 2) + cellY;
+ if (z > cellZ) {
+ subZ = (cellSize / 2) + cellZ;
+ // 5
+ subCubeArray = ce5;
+ } else {
+ subZ = (-cellSize / 2) + cellZ;
+ // 1
+ subCubeArray = ce1;
+ }
+ }
+ }
+
+ int subCubePointer;
+ if (subCubeArray[cellPointer] == 0) {
+ // create empty cluster
+ subCubePointer = makeNewCell();
+ subCubeArray[cellPointer] = subCubePointer;
+ } else
+ subCubePointer = subCubeArray[cellPointer];
+
+ putCell(x, y, z, subX, subY, subZ, cellSize / 2, subCubePointer,
+ color);
+ } else {
+ ce1[cellPointer] = CELL_STATE_SOLID;
+ ce2[cellPointer] = color.toInt();
+ ce3[cellPointer] = CELL_STATE_UNUSED;
+ // System.out.println("Cell written!");
+ }
+ }
+
+ public void setCellColor(final int pointer, final int color) {
+ ce2[pointer] = color;
+ }
+
+ public void setCellIllumination(final int pointer, final int illumination) {
+ ce3[pointer] = illumination;
+ }
+
+ /**
+ * @return intersecting cell pointer or -1 if no cell in intersecting this
+ * ray.
+ */
+ public int traceCell(final int cellX, final int cellY, final int cellZ,
+ final int cellSize, final int pointer, final Ray ray) {
+ if (isCellSolid(pointer)) {
+ // solid cell
+ if (doesIntersect(cellX, cellY, cellZ, cellSize, ray) != 0) {
+ ray.hitCellSize = cellSize;
+ ray.hitCellX = cellX;
+ ray.hitCellY = cellY;
+ ray.hitCellZ = cellZ;
+ return pointer;
+ }
+ return TRACE_NO_HIT;
+ } else // cluster
+ if (doesIntersect(cellX, cellY, cellZ, cellSize, ray) != 0) {
+ final int halfOfCellSize = cellSize / 2;
+ int rayIntersectionResult;
+
+ if (ray.x > cellX) {
+ if (ray.y > cellY) {
+ if (ray.z > cellZ) {
+ // 7
+ // 6 8 3 5 2 4 1
+
+ if (ce7[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY + halfOfCellSize,
+ cellZ + halfOfCellSize, halfOfCellSize,
+ ce7[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce6[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY - halfOfCellSize,
+ cellZ + halfOfCellSize, halfOfCellSize,
+ ce6[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce8[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY + halfOfCellSize,
+ cellZ + halfOfCellSize, halfOfCellSize,
+ ce8[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce3[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY + halfOfCellSize,
+ cellZ - halfOfCellSize, halfOfCellSize,
+ ce3[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce2[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY - halfOfCellSize,
+ cellZ - halfOfCellSize, halfOfCellSize,
+ ce2[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce4[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY + halfOfCellSize,
+ cellZ - halfOfCellSize, halfOfCellSize,
+ ce4[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce5[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY - halfOfCellSize,
+ cellZ + halfOfCellSize, halfOfCellSize,
+ ce5[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce1[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY - halfOfCellSize,
+ cellZ - halfOfCellSize, halfOfCellSize,
+ ce1[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ } else {
+ // 3
+ // 2 4 7 1 6 8 5
+ if (ce3[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY + halfOfCellSize,
+ cellZ - halfOfCellSize, halfOfCellSize,
+ ce3[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce2[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY - halfOfCellSize,
+ cellZ - halfOfCellSize, halfOfCellSize,
+ ce2[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce4[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY + halfOfCellSize,
+ cellZ - halfOfCellSize, halfOfCellSize,
+ ce4[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce7[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY + halfOfCellSize,
+ cellZ + halfOfCellSize, halfOfCellSize,
+ ce7[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce6[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY - halfOfCellSize,
+ cellZ + halfOfCellSize, halfOfCellSize,
+ ce6[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce8[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY + halfOfCellSize,
+ cellZ + halfOfCellSize, halfOfCellSize,
+ ce8[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce1[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY - halfOfCellSize,
+ cellZ - halfOfCellSize, halfOfCellSize,
+ ce1[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce5[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY - halfOfCellSize,
+ cellZ + halfOfCellSize, halfOfCellSize,
+ ce5[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ }
+ } else if (ray.z > cellZ) {
+ // 6
+ // 5 2 7 8 1 3 4
+ if (ce6[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY - halfOfCellSize, cellZ
+ + halfOfCellSize, halfOfCellSize, ce6[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce7[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY + halfOfCellSize, cellZ
+ + halfOfCellSize, halfOfCellSize, ce7[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce2[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY - halfOfCellSize, cellZ
+ - halfOfCellSize, halfOfCellSize, ce2[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce5[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY - halfOfCellSize, cellZ
+ + halfOfCellSize, halfOfCellSize, ce5[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce8[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY + halfOfCellSize, cellZ
+ + halfOfCellSize, halfOfCellSize, ce8[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce3[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY + halfOfCellSize, cellZ
+ - halfOfCellSize, halfOfCellSize, ce3[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce1[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY - halfOfCellSize, cellZ
+ - halfOfCellSize, halfOfCellSize, ce1[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce4[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY + halfOfCellSize, cellZ
+ - halfOfCellSize, halfOfCellSize, ce4[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ } else {
+ // 2
+ // 1 3 6 5 4 7 8
+ if (ce2[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY - halfOfCellSize, cellZ
+ - halfOfCellSize, halfOfCellSize, ce2[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce3[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY + halfOfCellSize, cellZ
+ - halfOfCellSize, halfOfCellSize, ce3[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce1[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY - halfOfCellSize, cellZ
+ - halfOfCellSize, halfOfCellSize, ce1[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce6[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY - halfOfCellSize, cellZ
+ + halfOfCellSize, halfOfCellSize, ce6[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce7[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY + halfOfCellSize, cellZ
+ + halfOfCellSize, halfOfCellSize, ce7[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce5[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY - halfOfCellSize, cellZ
+ + halfOfCellSize, halfOfCellSize, ce5[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce4[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY + halfOfCellSize, cellZ
+ - halfOfCellSize, halfOfCellSize, ce4[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce8[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY + halfOfCellSize, cellZ
+ + halfOfCellSize, halfOfCellSize, ce8[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ }
+ } else if (ray.y > cellY) {
+ if (ray.z > cellZ) {
+ // 8
+ // 5 7 4 1 6 3 2
+
+ if (ce8[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY + halfOfCellSize, cellZ
+ + halfOfCellSize, halfOfCellSize, ce8[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce7[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY + halfOfCellSize, cellZ
+ + halfOfCellSize, halfOfCellSize, ce7[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce5[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY - halfOfCellSize, cellZ
+ + halfOfCellSize, halfOfCellSize, ce5[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce4[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY + halfOfCellSize, cellZ
+ - halfOfCellSize, halfOfCellSize, ce4[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce3[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY + halfOfCellSize, cellZ
+ - halfOfCellSize, halfOfCellSize, ce3[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce1[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY - halfOfCellSize, cellZ
+ - halfOfCellSize, halfOfCellSize, ce1[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce6[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY - halfOfCellSize, cellZ
+ + halfOfCellSize, halfOfCellSize, ce6[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce2[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY - halfOfCellSize, cellZ
+ - halfOfCellSize, halfOfCellSize, ce2[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ } else {
+ // 4
+ // 1 3 8 5 7 2 6
+
+ if (ce4[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY + halfOfCellSize, cellZ
+ - halfOfCellSize, halfOfCellSize, ce4[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce8[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY + halfOfCellSize, cellZ
+ + halfOfCellSize, halfOfCellSize, ce8[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce3[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY + halfOfCellSize, cellZ
+ - halfOfCellSize, halfOfCellSize, ce3[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce1[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY - halfOfCellSize, cellZ
+ - halfOfCellSize, halfOfCellSize, ce1[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce7[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY + halfOfCellSize, cellZ
+ + halfOfCellSize, halfOfCellSize, ce7[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce5[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ - halfOfCellSize, cellY - halfOfCellSize, cellZ
+ + halfOfCellSize, halfOfCellSize, ce5[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce2[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY - halfOfCellSize, cellZ
+ - halfOfCellSize, halfOfCellSize, ce2[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce6[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX
+ + halfOfCellSize, cellY - halfOfCellSize, cellZ
+ + halfOfCellSize, halfOfCellSize, ce6[pointer],
+ ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ }
+ } else if (ray.z > cellZ) {
+ // 5
+ // 1 6 8 4 2 7 3
+
+ if (ce5[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX - halfOfCellSize,
+ cellY - halfOfCellSize, cellZ + halfOfCellSize,
+ halfOfCellSize, ce5[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce1[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX - halfOfCellSize,
+ cellY - halfOfCellSize, cellZ - halfOfCellSize,
+ halfOfCellSize, ce1[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce6[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX + halfOfCellSize,
+ cellY - halfOfCellSize, cellZ + halfOfCellSize,
+ halfOfCellSize, ce6[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce8[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX - halfOfCellSize,
+ cellY + halfOfCellSize, cellZ + halfOfCellSize,
+ halfOfCellSize, ce8[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce4[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX - halfOfCellSize,
+ cellY + halfOfCellSize, cellZ - halfOfCellSize,
+ halfOfCellSize, ce4[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce7[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX + halfOfCellSize,
+ cellY + halfOfCellSize, cellZ + halfOfCellSize,
+ halfOfCellSize, ce7[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce2[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX + halfOfCellSize,
+ cellY - halfOfCellSize, cellZ - halfOfCellSize,
+ halfOfCellSize, ce2[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce3[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX + halfOfCellSize,
+ cellY + halfOfCellSize, cellZ - halfOfCellSize,
+ halfOfCellSize, ce3[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ } else {
+ // 1
+ // 5 2 4 8 6 3 7
+
+ if (ce1[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX - halfOfCellSize,
+ cellY - halfOfCellSize, cellZ - halfOfCellSize,
+ halfOfCellSize, ce1[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce5[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX - halfOfCellSize,
+ cellY - halfOfCellSize, cellZ + halfOfCellSize,
+ halfOfCellSize, ce5[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce2[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX + halfOfCellSize,
+ cellY - halfOfCellSize, cellZ - halfOfCellSize,
+ halfOfCellSize, ce2[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce4[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX - halfOfCellSize,
+ cellY + halfOfCellSize, cellZ - halfOfCellSize,
+ halfOfCellSize, ce4[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce6[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX + halfOfCellSize,
+ cellY - halfOfCellSize, cellZ + halfOfCellSize,
+ halfOfCellSize, ce6[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce8[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX - halfOfCellSize,
+ cellY + halfOfCellSize, cellZ + halfOfCellSize,
+ halfOfCellSize, ce8[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+
+ if (ce3[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX + halfOfCellSize,
+ cellY + halfOfCellSize, cellZ - halfOfCellSize,
+ halfOfCellSize, ce3[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ if (ce7[pointer] != 0) {
+ rayIntersectionResult = traceCell(cellX + halfOfCellSize,
+ cellY + halfOfCellSize, cellZ + halfOfCellSize,
+ halfOfCellSize, ce7[pointer], ray);
+ if (rayIntersectionResult >= 0)
+ return rayIntersectionResult;
+ }
+ }
+ }
+ return TRACE_NO_HIT;
+ }
+
+}