# Traversing backwards through quadtree based on point.

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

## 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;
}

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)
{
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)
{

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

{
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 on other sites
A technique called picking works for objects at any depth, takes occlusion into account, and frees up the CPU.

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

1. 1
Rutin
26
2. 2
3. 3
4. 4
5. 5

• 9
• 11
• 10
• 13
• 20
• ### Forum Statistics

• Total Topics
632948
• Total Posts
3009387
• ### Who's Online (See full list)

There are no registered users currently online

×