Spa8nky 230 Report post Posted March 10, 2010 When I create an Octree my nodes indices are ordered as follows: z / / __________ / 2 / 3 /| y /____/____/ | | / 6 / 7 /|3| | /____/____/ |/| | 6 | 7 |7|1/ |____|____|/|/ | 4 | 5 |5/ |____|____|/ --- x The algorithm I am using to traverse an octree with a ray relies on an octree whose nodes indices are ordered as follows: z / / __________ / 3 / 7 /| y /____/____/ | | / 2 / 6 /|7| | /____/____/ |/| | 2 | 6 |6|5/ |____|____|/|/ | 0 | 4 |4/ |____|____|/ --- x If I swap the nodes over in the algorithm as follows: 0 becomes 4 1 -> 0 2 -> 6 3 -> 2 4 -> 5 5 -> 1 6 -> 7 7 -> 3 Then the following child (sub) node traversal no longer works correctly: 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^4) } 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 4: { 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 0: { 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 6: { 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 2: { 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 5: { 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 1: { 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 7: { 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 3: { 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) { int index = 8; // Index of next sub node (where 8 means that the ray has left the parent node) 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; } Is there any way of swapping the nodes and getting the algorithm to work, or am I going to have to build my octree differently? Currently the nodes are built as follows: for (int i = 0; i < 8; ++i) { // [C++] "if (i & 4)" is equivalent to [C#] "if ((i & 4) != 0)". offset.X = (((i & 1) != 0) ? step : -step); offset.Y = (((i & 2) != 0) ? step : -step); offset.Z = (((i & 4) != 0) ? step : -step); node.child[i] = BuildOctree(centre + offset, step, stopDepth - 1); } The difference is equivalent to rotating the entire octree about the y axis by 90 degrees. Has anyone got any suggestions for what I can do in this situation? 0 Share this post Link to post Share on other sites
taz0010 277 Report post Posted March 10, 2010 I implemented mine as a bitmask, and it looks like your algorithm does the same. Each of the 3 bits that make up the node index represent one of the axis planes.0 0 0x y zIf a node is in front of it's axis plane, that bit is set to 1. Otherwise zero. So the zero node is behind all 3 planes, and the 7 node is in front of all 3. This simplifies a lot of calculations. For example, the child node a point contains can be found with a single line of code.childIndex = ((pt.x > plane.x) << 2) | ((pt.y > plane.y) << 1) | (pt.z > plane.z)Your node layout implies a left handed coordinate system (z directed out of the page), with the high order bit being z.The second layout in your post is a right handed system where the high order bit is x.Changing the algorithm is probably a better choice if you are working with LH coordinates. I'll see if I can rewrite the code for you if you can't work out how to make the changes yourself. 0 Share this post Link to post Share on other sites
Spa8nky 230 Report post Posted March 10, 2010 Quote:Changing the algorithm is probably a better choice if you are working with LH coordinates. I'll see if I can rewrite the code for you if you can't work out how to make the changes yourself.I wouldn't ask you to do that, as that would be asking too much. What would be the fundamental difference for the algorithm, based on the differences in node position?Thanks. 0 Share this post Link to post Share on other sites
taz0010 277 Report post Posted March 10, 2010 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) }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.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. What variable holds the ray? 0 Share this post Link to post Share on other sites
Spa8nky 230 Report post Posted March 11, 2010 Quote:Original post by taz0010These 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. 0 Share this post Link to post Share on other sites