Space partitioning algorythms

Hi Everyone!

I’m interested: what space partitioning algorythms exist? Their pros/cons?

I’ve found a great nVidia paper “Modern graphics engine design”, but it reviews just AABoxTree(?) thing…

I would search that in google, using keywords: “BSP”, “bounding volumes”, etc.

There’s a site called citeseer that is quite good for finding technical papers. The paper’s are dense, as they are usually theses and journal articles.

dont forget octree, quadtree, portal… they are also space division and culling schemes.

I’m currently thinking of portals, because (I read somewhere) they offer zero overdraw…

Any links?

Thanks everyone for answers, guys!

Portal renderers can offer zero overdraw, but I don’t think people really take them that far anymore these days. I recently posted a portal rendering demo on www.delphi3d.net if you’re interested.

Portals are great for indoor scenery, but hard to apply to polygon soup. If you have complex scenes with no distinction between indoor and outdoor stuff, I’d look into an octree instead, and investigate occlusion culling.

– Tom

check this: http://www.flipcode.com/harmless/
explains octree, bsp, pvs, etc…

This is my personal opinion about culling/partition algorithms:

  1. BSPs. Dont fit well in modern HW if done by polygon basis. You can wait HOURS until the BSP is well balanced. Nice to do bak-front or front-back sorting. Very fast to render due to its hierarchy.

  2. Quadtree/Octree. Relatively new. Very nice for outdoor scenes. No cons I think… Easy to make and render. Fast due to its hierarchy.

  3. PVS. Loooooong time to generate well. Very very fast but could be imprecise.

  4. Portals. Typically for indoor scenes. Can be placed manually or automatically. Not easy to clip them but very nice technique. It is an occlusion technique really.

  5. Simple object frustrum culling. AABB/OBB/Sphere-camera planes intersection. Easy and fast for not much objects.

  6. Backface culling. As simple as a DotProduct!!!. Some objects need to be marked as “double faced”, so this technique is not always applicable.

  7. HP_occlusion_test extension. Not all hw supports it. Can be slower then these other methods or not…it depends.

But remember… probably the best solution is to MIX all, and make to fit to your project.

See “Realtime Rendering” from möller/haines AK.Peters www.realtimerendering.com

Quadtrees are new? Like 30 years new?

The important questions to ask in picking a culling algorithm are the data size, distribution (density), and dynamism. BSP is lousy for dynamic scenes. Certain kinds of trees can get bogged down with too much density (meaning you tend to keep the tree shallow to compensate), and some algorithms are more scalable than others. Quadtrees, for example, with such a low cost per test, scale up to many powers of two without too much effort.

The safest bet for a general-purpose HW-accelerated app IMEx is a tree of nested bounding spheres used in simple frustum culling and using the HW to do most of the depth sorting and fine-grain screen-space culling. But that’s basic. Hybrid approaches can approach the ideal once you know what your database looks like.

BSP - Binary Space Partition - Is a class of algorithms, any algorithm that divides space into two halves at any step is a DSP algorithm. Quad-trees divide space into 4 pieces at a time, and they are usually axis aligned. Oct-trees divide 8 ways. All of these classes of algorithms existed before I was born. And some before my parents were born.

These algorithms have two factors to weigh when creating the trees, splitting minimization (minimizing tree size), and tree balance (minimizing the difference in heights of branches). Either can be done perfectly, but the best trees (fastest renderable) usually incorporates both. These trees can take exponentially long time to find.

PVS is an orthogonal component to any space partition algorithm. Pre-computed Visible Set. At each tree node one stores only those geometry nodes that are visible from within that node, and during rendering skip processing any node that is not visible.

Portals come in two varieties. Classic portals is an orthogonal component to space partition algorithms. Essentially it was a method to keep track of the locations on the screen that do not have rendered images on them yet, and only expand the draw-traversal through those openings. This form should also have zero overdraw but usually it is converted to a tile-based overdraw system. Where if a tile is fully occluded by a piece of drawn geometry the tile is turned off. (Like a large pixelated depth buffer).

The newer version of portals is similar to the Descent 1 engine. Essentially space is partitioned into convex polyhedra, and classic portals is used to expand the draw-traversal through transparent polyhedral faces. This kind of portal offers zero-overdraw, and fast tests. The down-side is the draw time is proportional to the depth of field.

BSP is lousy for dynamic scenes.

State-of-the-art on BSPs allows parameterized movement of any object, without recompiling the tree. For every degree of freedom you wish an object to have, you potentially increase the tree size by a log factor. For instance, doors, skeletally animated enemies confined to a convex region of space, things that spin in place, can all be incorporated into a modern BSP. Though, the average John Carmack probably wouldn’t understand the math, and that’s saying something big, (as he’s incredibly intelligent and probably the most experienced BSP person out there). There is only one implementation of the modern algorithm, and it only supports up to 2 degrees of freedom(one object)(because the math got complicated, tensors, ick). And its covered under pending patent. This is an interesting one as well, since it offers zero overdraw with moving pieces.