When to use Binary Space Partitioning, Quadtree, O

问题:

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?

回答1:

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 and BVHs (Bounding Volume Hierarchies) benefit if the data is three dimensional. It also works very well if your geometric entities are clustered in 3D space. (see Octree vs BVH)

The benefit of Oc- and Quadtrees is that you can stop generating trees anytime you wish. 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 and 3D, but generating good BSP-Trees is an art form on its 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, by the way, is the reason why they were 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.

回答2:

The biggest practical difference between BSP-Trees and other kinds of 3d-trees are that BSP-Trees can be more optimal but only work on static geometry. This is because BSP-Trees are generally very slow to build, often taking hours or days for a typical static urban game level.

The two main reasons BSP-Trees take longer to build are (a) they use non-axis-aligned splitting planes, which take longer to optimally find, and (b) they subdivide geometry on axis boundaries, assuring no objects cross split planes.

Other types of 3d-trees (Octrees, Quadtrees, kd-tree, Bounding-Volume-Hierarchy) use axis-aligned bounding volumes, and volumes are (optionally) allowed to overlap, so contained objects don't need to be cut on volume boundaries. These both make the trees less optimal than BSP-trees, but quicker to build, and easier to change for dynamic objects.

Extrapolating these factors into situations...

Outdoor areas typically use height-field based ground representations, either simple heightmaps or more complex geo-mip-mapping techniques like ROAM. The ground itself doesn't participate in the 3d space partitioning, only objects placed on the ground.

Worlds with lots of instances of simpler and similar geometry (houses, trees, asteroids, etc) will often use a non-BSP-tree (such as a BVH), because putting the geometry into a BSP-tree would mean duplicating and splitting the detail geometry for every instance.

Conversely, a large custom static mesh with no instancing, such as an urban scene, or a complex indoor environment, will typically use a BSP-Tree for improved runtime performance. The fact that the BSP-Tree splits geometry on node-boundaries is helpful for rendering performance, because the BSP nodes can be used as pre-organized triangle rendering batches. The BSP-Tree can also be optimized for occlusion, avoiding the need to draw portions of the BSP-Tree which are known to be behind other geometry.

See also: Octree vs BVH, Bounding Volume Hierarchy Tutorial, BSP Tutorial.

回答3:

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.

回答4:

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.

回答5:

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.

回答6:

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.

回答7:

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.