Sign in to follow this  

Traversing backwards through quadtree based on point.

This topic is 2848 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[i];

                    // 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
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[i] = 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[i];

// 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

This topic is 2848 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.

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