quadtree problem

OpenGL OpenGL: Basic Coding
1

Whenever I store data in a quadtree, I provide its BB and an algorithm finds the correct nodes in the quadtree containing the provided BB.

My problem is the special case where the BB I provide shares boundaries with quadtree boxes. In this case more than 1 quadtree box with fit the search criterion (containment) and my data will be consequently written into more than 1 node.

Example:
A BB stretches from (-0.5, -0.5) to (0.5, 0.5), but there are quadtree boxes to the left and right, up and down of this BB, as well as diagonally, and these will duplicate the data I provide, as they all share 1 boundary with this box. Even worse, the quadtree boxes laying diagonally from this box share exactly 1 pixel (the corner) with it, hence they are taken in too, for a whooping total of 9 boxes having the provided data written into. A picture:

B|B|B
B|X|B
B|B|B

You can see 9 quadtree boxes (B) and the provided one (X) fitting a quadtree box completely.

How do you solve this problem of shared boundaries?

2

This is more of general graphics question than an OpenGL question but…

There are at least four ways to deal with objects that could be in more than one node:

  1. Instead of storing the object in a leaf node, store it in the deepest node that completely contains it.
  2. Break the object into multiple objects, one for each leaf node that it intersects. In practice, this is usually pretty difficult.
  3. Store a pointer to the object in each leaf node that it intersects. Use a flag or frame count so the object isn’t rendered, or whatever, redundantly.
  4. Use loose quadtrees, where node’s BB overlap each other.

Or consider using a less rigid data structure such as bounding volume hierarchy (BVH).

Let me know if you need more information on any of the above.

Regards,
Patrick

3
  1. Instead of storing the object in a leaf node, store it in the deepest node that completely contains it.

What if no such node exists? This is possible if the box you want to store data in has the quadtree origin as a corner.

  1. Break the object into multiple objects, one for each leaf node that it intersects. In practice, this is usually pretty difficult.

Yes, I suppose I’d be better to just use a BSP tree in this case.

  1. Store a pointer to the object in each leaf node that it intersects. Use a flag or frame count so the object isn’t rendered, or whatever, redundantly.

good idea

  1. Use loose quadtrees, where node’s BB overlap each other.

good idea also

How about detecting the case of two boxes sharing a face, edge of vertex and rejecting such pairs of objects for storage of data? How to detect this?

4

There should always exist a node, even if it is the root node, unless the object is not completely within the tree’s extent.

I’m not sure that I’m following. Can you provide an example?

Regards,
Patrick

5

It’s the standard quadtree scenario:

#X#

the #s are boxes, the box X that the user provides equals one of them and all 9 would normally store the data. However, we cleverly detect that the #s share only a face or pixel with the X box and so reject them. I suppose we need to calculate the intersection of boxes, if they intersect, and reject the candidate #s if the resulting intersection box is planar.

6

Thanks. I see now.

If this edge case is important to you, you could minimize its impact by using node ranges <= and <, e.g. the x range for the root node’s children would be [0, 1) and [1, 2]. Since 2 is on the edge of the tree, it is <=.

I believe your approach will also work. The intersection of two boxes is straightforward.

Patrick

7

Now it’s my turn to be puzzled. Node ranges? Do you mean to replace the <= with < in the interval intersection test? Good idea actually.

8

You got it.