When to use Binary Space Partitioning, Quadtree, Octree?

Question

I have recently learned about binary space partitioning trees and their application to 3d graphics and collision detection. I have also briefly perused material relating to quadtrees and octrees. When would you use quadtrees over bsp trees, or vice versa? Are they interchangeable? I would be satisfied if I had enough information to fill out a table like this:

            | BSP | Quadtree | Octree
------------+----------------+-------
Situation A |  X  |          |
Situation B |     |     X    |
Situation C |     |          |   X

What are A, B, and C?

Answer 1

I don't have much experience with BSPs, but I can say that you should go with octrees over quadtrees when you the scene you're rendering is tall. That is, the height is more than half the width and depth -- little rule of thumb. Generally, octrees won't bring a huge cost over quadtrees and they have the potential to speed things up a decent bit. YMMV.

Answer 2

Usually these things don't have a clear-cut answer. I would suggest that A,B, and C are the result of a function of the size of your space and the amount of stuff you are differentiating.

Answer 3

A BSP is better for a smaller, simpler space that you only want to do occlusion with. If you want all intersections for a given ray, you'll need to upgrade to a quad/octree.

As for quadtree vs. octree - how many dimensions do you care a lot about? Two dimensions means a quadtree, four an octree. As stated, as quadtree can work in three-space, but if you want each dimension given a proper treatment, an octree is the way to go.

Answer 4

A BSP is best for urban environments.

A Quadtree is best for when you use a height map for terrain, etc.

An Octree is best for when you have clumps of geometry in 3d space, such as a solar system.

Answer 5

BSPs are a good option for accelerating collision-detection, depending on which flavour you use. They're particularly fast at point and line or ray tests, somewhat less fast and a little more complicated for things with volume.

As for their use in graphics, BSPs are pretty much obsolete. Octrees work well for things like gross visibility culling, as do AABB trees.

Answer 6

There is no clear answer to your question. It depends entirely how your data is organized.

Something to keep in mind:

Quadtrees work best for data that is mostly two dimensional like map-rendering in navigation systems. In this case it's faster than octrees because it adapts better to the geometry and keeps the node-structures small.

Octrees benefit if the data is three dimensional. It also works very well if your geometric entities are clusterd in 3D space.

The benefit of Oc- and Quadtrees is that you can stop generating trees anytime you which. If you want to render graphics using a graphic accelerator it allows you to just generate trees on an object level and send each object in a single draw-call to the graphics API. This performs much better than sending individual triangles (something you have to do if you use BSP-Trees to the full extent).

BSP-Trees are a special case really. They work very very well in 2D an 3D, but generating good BSP-Trees is an art form on it's own. BSP-Trees have the drawback that you may have to split your geometry into smaller pieces. This can increase the overall polygon-count of your data-set. They are nice for rendering, but they are much better for collision detection and ray-tracing.

A nice property of the BSP-trees is that they decompose a polygon-soup into a structure that can be perfectly rendered back to front (and vice versa) from any camera position without doing an actual sort. The order from each viewpoint is part of the data-structure and done during BSP-Tree compilation.

That's btw the reason why they've been so popular 10 years ago. Quake used them because it allowed the graphic engine / software rasterizer to not use a costly z-buffer.

All the trees mentioned are just families of trees. There are loose octrees, kd-trees hybrid-trees and lots of other related structures as well.