Part of the Khronos Group
OpenGL.org

The Industry's Foundation for High Performance Graphics

from games to virtual reality, mobile phones to supercomputers

Results 1 to 10 of 10

Thread: Space partitioning algorythms

  1. #1
    Intern Newbie
    Join Date
    Oct 2003
    Location
    Russia, Moskow
    Posts
    38

    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...

  2. #2
    Member Regular Contributor
    Join Date
    May 2000
    Location
    Philadelphia
    Posts
    285

    Re: Space partitioning algorythms

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

  3. #3
    Intern Contributor
    Join Date
    Feb 2004
    Posts
    98

    Re: Space partitioning algorythms

    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.

  4. #4
    Junior Member Regular Contributor
    Join Date
    Oct 2002
    Location
    San Diego, CA, USA
    Posts
    209

    Re: Space partitioning algorythms

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

  5. #5
    Intern Newbie
    Join Date
    Oct 2003
    Location
    Russia, Moskow
    Posts
    38

    Re: Space partitioning algorythms

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

    Any links?

    Thanks everyone for answers, guys!

  6. #6
    Advanced Member Frequent Contributor
    Join Date
    Oct 2000
    Location
    Belgium
    Posts
    807

    Re: Space partitioning algorythms

    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

  7. #7
    Intern Contributor
    Join Date
    Feb 2003
    Location
    Mitishy
    Posts
    59

    Re: Space partitioning algorythms

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

  8. #8
    Member Regular Contributor
    Join Date
    Sep 2000
    Location
    Inside an xbox
    Posts
    279

    Re: Space partitioning algorythms

    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

  9. #9
    Junior Member Regular Contributor
    Join Date
    May 2003
    Location
    New York
    Posts
    194

    Re: Space partitioning algorythms

    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.

  10. #10
    Intern Contributor
    Join Date
    Feb 2004
    Posts
    98

    Re: Space partitioning algorythms

    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.

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •