Sign in to follow this  
Spa8nky

[C#] Ray quadtree traversal with negative ray direction

Recommended Posts

I have a working algorithm for a 2D ray traversal of a quadtree.
        public void InsertRay(CD_Ray2D ray)
        {
            InsertRay(quadtree_Root, ray);
        }

        private void InsertRay(Node_Quadtree node, CD_Ray2D ray)
        {
            int a = 0;
            Vector2 direction = ray.Direction;
            Vector2 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 |= 1;
            }
            if (direction.Y < 0.0f)
            {
                // Create reflected ray
                direction.Y = (2 * node.halfWidth.Y) - direction.Y;
                a |= 2;
            }

            // Epsilon for dealing with parallel rays (avoids divide by 0)
            Vector2 e = new Vector2();
            e.X = Settings.EPSILON;         
            e.Y = Settings.EPSILON;
            direction += e;

            Vector2 t0 = node.MinPoint - origin;
            t0 /= direction;

            Vector2 t1 = node.MaxPoint - origin;
            t1 /= direction;

            float tMin = Math.Max(t0.X, t0.Y);
            float tMax = Math.Min(t1.X, t1.Y);

            if (tMin < tMax)
            {
                // Check this node's children
                Subtree(node, t0.X, t0.Y, t1.X, t1.Y, a);
            }
        }

        private void Subtree(Node_Quadtree node, float t0x, float t0y, float t1x, float t1y, int a)
        {
            if (t1x < 0f || t1y < 0f)
            {
                return;
            }

            node.DrawNode = true;

            float tMx = 0.5f * (t0x + t1x);
            float tMy = 0.5f * (t0y + t1y);

            // [Child Order]
            //  _______
            // | 2 | 3 |
            // |___|___|
            // | 0 | 1 |
            // |___|___|
            //
            //Subtree(node.child[0], t0x, t0y, tMx, tMy, a);
            //Subtree(node.child[1], tMx, t0y, t1x, tMy, a); 
            //Subtree(node.child[2], t0x, tMy, tMx, t1y, a);
            //Subtree(node.child[3], tMx, tMy, t1x, t1y, a);

            if (tMy < tMx)
            {
                // Ray crosses child 2 (3 if ray is in opposite direction)
                if (node.child[2 ^ a] != null)
                {
                    Subtree(node.child[2 ^ a], t0x, tMy, tMx, t1y, a);        
                }
                if (t0x < tMy)
                {
                    // Ray crosses child 0 (1 if ray is in opposite direction)
                    if (node.child[a] != null)
                    {
                        Subtree(node.child[a], t0x, t0y, tMx, tMy, a);        
                    }
                }
                if (tMx < t1y)
                {
                    // Ray crosses child 3 (2 if ray is in opposite direction)
                    if (node.child[3 ^ a] != null)
                    {
                        Subtree(node.child[3 ^ a], tMx, tMy, t1x, t1y, a);    
                    }
                }
            }
            else if (tMx < tMy)
            {
                // Ray crosses child 1 (0 if ray is in opposite direction)
                if (node.child[1 ^ a] != null)
                {
                    Subtree(node.child[1 ^ a], tMx, t0y, t1x, tMy, a);
                }
                if (t0y < tMx)
                {
                    // Ray crosses child 0
                    if (node.child[a] != null)
                    {
                        Subtree(node.child[a], t0x, t0y, tMx, tMy, a);
                    }
                }
                if (tMy < t1x)
                {
                    // Ray crosses child 3
                    if (node.child[3 ^ a] != null)
                    {
                        Subtree(node.child[3 ^ a], tMx, tMy, t1x, t1y, a);
                    }
                }
            }
        }



The problem is, when the ray has a negative direction, the reflected ray doesn't intersect the nodes correctly. The logical XOR flips the child order from:
            // [Child Order]
            //  _______
            // | 2 | 3 |
            // |___|___|
            // | 0 | 1 |
            // |___|___|

to

            // [Child Order]
            //  _______
            // | 3 | 2 |
            // |___|___|
            // | 1 | 0 |
            // |___|___|
for negative x directions. However this is what I get for +X ray direction: Direction Positive Ray and this is the incorrect result for -X ray direction: Direction Positive Ray Where has my logic failed? Thank you.

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