15
$\begingroup$

When placing geometric objects in a quadtree (or octree), you can place objects that are larger than a single node in a few ways:

  1. Placing the object's reference in every leaf for which it is contained
  2. Placing the object's reference in the deepest node for which it is fully contained
  3. Both #1 and #2

For example:

enter image description here

In this image, you could either place the circle in all four of the leaf nodes (method #1) or in just the root node (method #2) or both (method #3).

For the purposes of querying the quadtree, which method is more commonplace and why?

Improve this question
$\endgroup$
5
  • 1
    $\begingroup$ Certainly it should be a reference. I intend to ask if, for the purposes of querying the quadtree, there should be references in the the leaves, non-leaves, or both. $\endgroup$
    – nsantorello
    Mar 6, 2012 at 19:45
  • $\begingroup$ P.S. Edited to hopefully make intentions of the question clearer. $\endgroup$
    – nsantorello
    Mar 6, 2012 at 19:46
  • $\begingroup$ What is the query you are trying to support? $\endgroup$
    – Joe
    Mar 6, 2012 at 21:45
  • $\begingroup$ @Joe I am particularly interested in collision detection, spacial indexing, and region/frustum culling. $\endgroup$
    – nsantorello
    Mar 7, 2012 at 5:45
  • 1
    $\begingroup$ @nsantorello The rule may be different depending on which of those queries you want to support, but this seems very relevant for collision detection: stackoverflow.com/questions/4434335/… $\endgroup$
    – Joe
    Mar 7, 2012 at 6:11

2 Answers 2

Reset to default
8
$\begingroup$

Assuming you are storing a reference, not the object itself, it may make sense to do this differently depending on your application.

For instance, if you were computing collisions with this (solid) circle and the collision was occurring in the lower left hand corner, it'd be easier if you had access to all geometry in that leaf directly from that leaf (method #3) (without having to traverse the tree upward and determine inherited geometry). But, say you were just using quadtrees for drawing geometry, you'd want to use method #1, because it only makes sense to draw something in the node for which it is fully contained (it would be more difficult to figure out which portion to draw for each leaf node and where).

As for what is more commonplace, my only experience with quadtrees is with writing an n-body simulation where the geometric objects were really just points that had no area, so I can't definitively answer that.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks Rafe, I think you are right that it depends on the application. $\endgroup$
    – nsantorello
    Mar 6, 2012 at 19:49
6
$\begingroup$

One of the advantages of a Quadtree is that you don't have to split a node into its child nodes if all of the child nodes would contain the same information. This can save you a lot of memory and can make processing faster.

Following this principle, I think it makes more sense to store it only in the root node (method #2). It could save you a lot of memory and I think would also make processing easier. For example, if you tried to find intersections of the circle with a line that goes through three of the leaf nodes, you would either need to compute the intersection separately for each leaf node, or remember that you already intersected with this circle.

On the other hand, if you have objects in leaf nodes, it could help you eliminate false positives (objects that you have to check for intersection, because they are in the correct node, but that don't actually intersect).

So, I think both approaches have their uses and I'm not sure how to choose which one to use.

I probably wouldn't use approach #3, because I don't see any positives about it.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.