Quote:Original post by taz0010
These lines. Bits 0 and 2 are swapped, so do index |= 1 instead of |= 4, and vice verca. Do the same on the other lines.
I've now tried that but node 2 is crossed when node 7 is crossed (original ordering)and vice versa. This is the same as node 3 and node 6 for my node ordering.
Quote:
Is there any documentation for this method? It's different to how I traverse the nodes, and I'm having trouble making sense of it.
The original paper can be found
here.
My complete algorithm based off the paper is as follows. I've made some changes to avoid dealing with divisions by 0.
public void InsertRay(CD_Ray ray) { InsertRay(octree_Root, ray); } private void InsertRay(Node_Octree node, CD_Ray ray) { int a = 0; Vector3 direction = ray.Direction; Vector3 origin = ray.Origin; // If ray direction is negative along either axis if (direction.X < 0.0f) { // Create reflected ray direction.X = (2 * node.halfWidth.X) - direction.X; a |= 4; } if (direction.Y < 0.0f) { // Create reflected ray direction.Y = (2 * node.halfWidth.Y) - direction.Y; a |= 2; } if (direction.Z < 0.0f) { // Create reflected ray direction.Z = (2 * node.halfWidth.Z) - direction.Z; a |= 1; } // Epsilon for dealing with parallel rays (avoids divide by 0) Vector3 e = new Vector3(); e.X = Settings.EPSILON; e.Y = Settings.EPSILON; e.Z = Settings.EPSILON; direction += e; Vector3 t0 = node.MinPoint - origin; t0 /= direction; Vector3 t1 = node.MaxPoint - origin; t1 /= direction; float tMin = Math_Util.Max3(t0.X, t0.Y, t0.Z); float tMax = Math_Util.Min3(t1.X, t1.Y, t1.Z); if (tMin < tMax) { // Check this node's children Subtree(node, t0.X, t0.Y, t0.Z, t1.X, t1.Y, t1.Z, a); } } private void Subtree(Node_Octree node, float t0x, float t0y, float t0z, float t1x, float t1y, float t1z, int a) { if (t1x < 0f || t1y < 0f || t1z < 0f) { return; } node.DrawNode = true; float tMx = 0.5f * (t0x + t1x); float tMy = 0.5f * (t0y + t1y); float tMz = 0.5f * (t0z + t1z); // Find the index of the first child node crossed by the ray int index = 0; float max = Math_Util.Max3(t0x, t0y, t0z); // |= bit (Turns bit on) // &= ~bit (Turns bit off) if (t0x == max) { // YZ entry plane if (tMy < t0x) index |= 2; // Bit 1 affected (2^1) if (tMz < t0x) index |= 4; // Bit 2 affected (2^2) } if (t0y == max) { // XZ entry plane if (tMx < t0y) index |= 1; // Bit 0 affected (2^0) if (tMz < t0y) index |= 4; // Bit 2 affected (2^2) } if (t0z == max) { // XY entry plane if (tMx < t0z) index |= 1; // Bit 0 affected (2^0) if (tMy < t0z) index |= 2; // Bit 1 affected (2^1) } // z // / // / // __________ // / 3 / 7 /| // y /____/____/ | // | / 2 / 6 /|7| // | /____/____/ |/| // | 2 | 6 |6|5/ // |____|____|/|/ // | 0 | 4 |4/ // |____|____|/ --- x do { switch (index) { case 0: { if (node.child[a] != null) { Subtree(node.child[a], t0x, t0y, t0z, tMx, tMy, tMz, a); index = NextSubNode(tMx, 4, tMy, 2, tMz, 1); } else { index = 8; } break; } case 1: { if (node.child[1 ^ a] != null) { Subtree(node.child[1 ^ a], t0x, t0y, tMz, tMx, tMy, t1z, a); index = NextSubNode(tMx, 5, tMy, 3, t1z, 8); } else { index = 8; } break; } case 2: { if (node.child[2 ^ a] != null) { Subtree(node.child[2 ^ a], t0x, tMy, t0z, tMx, t1y, tMz, a); index = NextSubNode(tMx, 6, t1y, 8, tMz, 3); } else { index = 8; } break; } case 3: { if (node.child[3 ^ a] != null) { Subtree(node.child[3 ^ a], t0x, tMy, tMz, tMx, t1y, t1z, a); index = NextSubNode(tMx, 7, t1y, 8, t1z, 8); } else { index = 8; } break; } case 4: { if (node.child[4 ^ a] != null) { Subtree(node.child[4 ^ a], tMx, t0y, t0z, t1x, tMy, tMz, a); index = NextSubNode(t1x, 8, tMy, 6, tMz, 5); } else { index = 8; } break; } case 5: { if (node.child[5 ^ a] != null) { Subtree(node.child[5 ^ a], tMx, t0y, tMz, t1x, tMy, t1z, a); index = NextSubNode(t1x, 8, tMy, 7, t1z, 8); } else { index = 8; } break; } case 6: { if (node.child[6 ^ a] != null) { Subtree(node.child[6 ^ a], tMx, tMy, t0z, t1x, t1y, tMz, a); index = NextSubNode(t1x, 8, t1y, 8, tMz, 7); } else { index = 8; } break; } case 7: { if (node.child[7 ^ a] != null) { Subtree(node.child[7 ^ a], tMx, tMy, tMz, t1x, t1y, t1z, a); index = 8; } else { index = 8; } break; } } } while (index != 8); } private int NextSubNode(float t1x, int nIndex0, float t1y, int nIndex1, float t1z, int nIndex2) { // Index of next sub node (where 8 means that the ray has left the parent node) int index = 8; float min = Math_Util.Min3(t1x, t1y, t1z); if (t1x == min) { // YZ exit plane index = nIndex0; } if (t1y == min) { // XZ exit plane index = nIndex1; } if (t1z == min) { // XY exit plane index = nIndex2; } return index; }
The only part I'm not completely certain about is the NextSubNode() method, but everything else follows the paper closely.
Quote:What variable holds the ray?
The ray class has the following variables:
public class CD_Ray : Shape3D { public const float MAX_LENGTH = 5000; Vector3 direction; Vector3 origin; VertexPositionColor[] vertices;
Thank you for having a look at this, it is very much appreciated.
