Menu
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?
278
Simply, a BSP tree is a heirarchical subdivisions of n dimensional space into convex subspaces. Each node has a front and back leaf. Starting off with the root node, all subsequent insertions are partitioned by the hyperplane of the current node. In 2 dimensional space, a hyperplane is a line.
Binary space partitioning was developed in the context of 3D computer graphics in 1969. The structure of a BSP tree is useful in rendering because it can efficiently give spatial information about the objects in a scene, such as objects being ordered from front-to-back with respect to a viewer at a given location.
Binary Space Partitioning is implemented for recursively subdividing a space into two convex sets by using hyperplanes as partitions. This process of subdividing gives rise to the representation of objects within the space in the form of tree data structure known as BSP Tree.
An octree is a tree data structure in which each internal node has exactly eight children. Octrees are most often used to partition a three-dimensional space by recursively subdividing it into eight octants. Octrees are the three-dimensional analog of quadtrees.
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) (archived from original)
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.
74
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
