Different Subdivision Algorithms

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

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]

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