# [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.

## Recommended Posts

I have a working algorithm for a 2D ray traversal of a quadtree.
        public void InsertRay(CD_Ray2D 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: and this is the incorrect result for -X ray direction: Where has my logic failed? Thank you.

1. 1
2. 2
Rutin
19
3. 3
khawk
19
4. 4
5. 5
A4L
11

• 9
• 12
• 16
• 26
• 10
• ### Forum Statistics

• Total Topics
633771
• Total Posts
3013762
×