Sign in to follow this  
Spa8nky

Octree index differences. Swapping nodes doesn't work?

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

Share this post


Link to post
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 this post


Link to post
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 this post


Link to post
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 this post


Link to post
Share on other sites
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.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this