• Advertisement
Sign in to follow this  

[C#] Ray quadtree traversal with negative ray direction

This topic is 2903 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