Jump to content
  • Advertisement
Sign in to follow this  
Spa8nky

[C#] Ray quadtree traversal with negative ray direction

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

If you intended to correct an error in the post then please contact us.

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
Advertisement
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

GameDev.net is your game development community. Create an account for your GameDev Portfolio and participate in the largest developer community in the games industry.

Sign me up!