Jump to content
  • Advertisement
Sign in to follow this  
Spa8nky

Traversing backwards through quadtree based on point.

This topic is 3063 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've come up with an algorithm for selecting my 2D quadtree objects in 3D from any angle. Based on the mouse cursor's projected ray and its point of intersection with my quadtree I can then return an object in the quadtree that the mouse is over. The problem is that the following method will only return objects that are fully inside a node and not those at lower depths in the quadtree but still intersecting the node:
        public IQuadtree_Object GetObjectFromPoint(Vector2 point)
        {
            depth = 0;
            return GetObjectFromPoint(quadtree_Root, point);
        }

        private IQuadtree_Object GetObjectFromPoint(Node_2D node, Vector2 point)
        {
            int index = 0;
            bool straddle = false;  // Does the object overlap/straddle a partioning plane or node?

            // Compute the quadrant number [0..3] in which the quadtree_Object sphere centre is in
            // If straddling any of the dividing x or y planes, exit directly
            for (int i = 0; i < 2; ++i)
            {
                float delta = point.Index(i) - node.centre.Index(i);

                if (Math.Abs(delta) <= Settings.EPSILON)
                {
                    straddle = true;
                    break;
                }
                if (delta > 0.0f)
                {
                    index |= (1 << i);  // YX
                }
            }

            if (!straddle && node.child[index] != null)
            {
                // InsertObject will recursively call itself until:
                // - There is no child node to descend into OR
                // - The object is straddling

                // Fully contained in existing child node.  Insert in that subtree (based on index)
                return GetObjectFromPoint(node.child[index], point);
            }
            else
            {
                // Test point against all objects in this node
                for (int i = 0; i < node.list_Object.Count; ++i)
                {
                    IQuadtree_Object o = node.list_Object;

                    // Test to see if point is inside the radius of the object
                    Vector2 p = point - o.body.Position;
                    float radius = o.body.Shape.Radius;

                    if (p.LengthSquared() < radius * radius)
                    {
                        return o;
                    }
                }

                // No object has been found at this point
                return null;
            }
        }

If I have an array of all ancestor nodes "ancestorStack[MaxNodes]", how can I traverse backwards through the depths of the ancestor nodes in order to test the point agaist the objects that are not fully contained inside this node but are straddling/intersecting it? Thank you.

Share this post


Link to post
Share on other sites
Advertisement
I solved the problem by doing the following:

I made sure that each node now has a parent paremeter, the root node has null for a parent.

The quadtree is now created as follows:



quadtree_Root = BuildQuadtree(centre, halfWidth, stopDepth, null);

private Node_2D BuildQuadtree(Vector2 centre, float halfWidth, int stopDepth, Node_2D parent)
{
if (stopDepth < 0)
{
return null;
}
else
{
// Construct and fill in "root" of this subtree
Node_2D node = new Node_2D();
node.centre = centre;
node.halfWidth = halfWidth;
node.parent = parent;

// Recursively construct the four children of the subtree
Vector2 offset;
float step = halfWidth * 0.5f;

for (int i = 0; i < 4; ++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);

node.child = BuildQuadtree(centre + offset, step, stopDepth - 1, node);
}

return node;
}
}




Now I can find the node based on the point of mouse ray intersection and return an object starting with the node found and checking parent nodes recursively if no object is found:


public IQuadtree_Object GetObjectFromPoint(Vector2 point)
{
return GetObjectFromPoint(quadtree_Root, point);
}

private IQuadtree_Object GetObjectFromPoint(Node_2D node, Vector2 point)
{
int index = 0;
bool straddle = false; // Does the object overlap/straddle a partioning plane or node?

// Compute the quadrant number [0..3] in which the quadtree_Object sphere centre is in
// If straddling any of the dividing x or y planes, exit directly
for (int i = 0; i < 2; ++i)
{
float delta = point.Index(i) - node.centre.Index(i);

if (Math.Abs(delta) <= Settings.EPSILON)
{
straddle = true;
break;
}
if (delta > 0.0f)
{
index |= (1 << i); // YX
}
}

if (!straddle && node.child[index] != null)
{
return GetObjectFromPoint(node.child[index], point);
}
else
{
return TestObjectRadius(node, point);
}
}

private IQuadtree_Object TestObjectRadius(Node_2D node, Vector2 point)
{
// Test point against all objects in this node
for (int i = 0; i < node.list_Object.Count; ++i)
{
IQuadtree_Object o = node.list_Object;

// Test to see if point is inside the radius of the object
Vector2 p = point - o.body.Position;
float radius = o.body.Shape.Radius;

if (p.LengthSquared() < radius * radius)
{
return o;
}
}

if (node.parent != null)
{
// If this node has a parent, then test against the objects in that node
return TestObjectRadius(node.parent, point);
}

// No object's radius has been found to encompass the point
return null;
}




It seems to run very quickly with 1000 objects in my quadtree so I am happy to share it in the hope that someone else might find the code helps them in some way.

Thanks guys.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

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

We are the game development community.

Whether you are an indie, hobbyist, AAA developer, or just trying to learn, GameDev.net is the place for you to learn, share, and connect with the games industry. Learn more About Us or sign up!

Sign me up!