# Octree index differences. Swapping nodes doesn't work?

This topic is 3056 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

## Recommended Posts

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 = 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?

##### Share on other sites
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 0
x y z

If 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.

##### Share on other sites
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.

##### Share on other sites
        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?

##### Share on other sites
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.

1. 1
2. 2
3. 3
Rutin
19
4. 4
5. 5

• 10
• 14
• 30
• 13
• 11
• ### Forum Statistics

• Total Topics
631782
• Total Posts
3002332
×