Archived

This topic is now archived and is closed to further replies.

Different Subdivision Algorithms

This topic is 5515 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

I was wondering if anyone could help me compile a list of Subdivision algorithms. I''m trying to find some hybrid approaches to a project, and was wondering if there''s anything out there that i can put together with what i have. Here''s the list I have so far: Frustum Oct Tree / Quad Tree BSP PVS Heightmap Any other types subdivsion, no matter how minute, would be appriciated. Thanks! ~Main == Colt "MainRoach" McAnlis Programmer www.badheat.com/sinewave

Share this post


Link to post
Share on other sites
Subdivision ? Do you mean culling or spatial organization schemes ? Subdivision is commonly used in tesselation algorithms (subdivision surfaces, Bezier patches, NURBS).

I''m not really sure what exactly you try to list. A frustum has nothing to do with eg. an Octtree. You can implement frustum culling using an octtree or BSP. PVS can be created from a BSP or an Octtree (or even from a polygon soup). And a heightmap is something totally different.

If you mean culling algorithms (from the top of my head):
* frustum culling (available methods: occtrees, quadtrees, BSPs, adaptive binary trees, OBB trees, etc...)
* portal based systems (simple portal/cell structure, dual portals (portal/antiportal), multi-portals).
* backface culling
* occlusion culling (geometric, HOM, IOM)
* importance based culling
* Level of detail (LOD) systems (progressive meshes, geomipmaps, displacement mapping)
* Heightmap terrain HSR (quadtrees, CLOD, geomipmaps)
* Image based rendering (texture clusters, IBR caching)
* PVS based systems (from simple ones using BSPs to fuzzy projections)

And many more obscure ones...

/ Yann

Share this post


Link to post
Share on other sites
Ahh, didn't realize the terminology was the problem in communication.

lets try: list of "Scene Transversal Algoritms"

Thank's for the list you did supply so far though yann

~Main

[edited by - duhroach on November 8, 2002 5:53:47 PM]

Share this post


Link to post
Share on other sites
Well, if you are after spatial subdivision algorithms, then the first line in my list is of interest: octtrees, quadtrees, BSPs, adaptive binary trees, OBB trees.

Those simply divide the space (and geometry contained therein) into a hierachical structure, so that culling is accelerated. On their own, they do nothing, they just provide the structure.

The second part is to choose the culling algorithms, that will make use of that structure. Frustum culling, portals, occlusion culling, importance culling, etc. will all use the structure created above, in order to cull out geometry based on different factors: is the geometry visible on the screen (frustum culling), is it hidden by other geometry (occlusion, portals, PVS), does it contribute much to the final image or not (importance culling), etc.

Simplification algorithms go a step further, as they actually modify the geometry itself. They can also operate on your initial hierarchical structure, although some provide their own. CLOD, geomipmaps, progressive meshes, etc are such algorithms. They dynamically simplify the geometry and remove parts of it that do not contribute to the current frame.

All in all, you need a good and well balanced set of those algorithms to get your engine running. Some of them are mutually exclusive, other will nicely work together. It ultimately depends on what kind of engine you''re after.

/ Yann

Share this post


Link to post
Share on other sites