Most efficient algorithm for mesh-level, optimal occlusion culling?

Question

I am new to culling. On a first glance, it seems that most occlusion culling algorithms are object-level, not examining single meshes, which would be practical for game rendering.

What I am looking for is an algorithm that culls all meshes within a single object that are occluded for a given viewpoint, with high accuracy. It needs to be at least O(n log n), a naive mesh-by-mesh comparison (O(n^2)) is too slow.

I notice that the Blender GUI identifies the occluded meshes for you in real-time, even if you work with large objects of 10,000+ meshes. What algorithm is used there, pray tell?

Answer 1

Have you looked into things like Octrees?

Answer 2

Usually the first thing you do is see if the meshes have any chance of occluding each other. Often times with a simple bounding primitive (bounding boxes or bounding spheres). If I recall correctly, Octrees will help with this.

Answer 3

The reason why culling is not made on the mesh level is that a mesh is a very dumb renderer level object while a game-object is at the scene level, where all the culling occurs. There are no mesh level culling decision being taken, they are simply a way to batch primitives with similar shader states if their objects needs to be renderered.

If you really need to cull at mesh level, then you might want to create one object per mesh and then create a group object that contains the mesh-objects. Be aware that you might actually lose performance since culling at mesh level is usually not worth it; it might break the flow of data transfers to the hardware.

Answer 4

I tried the naive approach which was actually sufficiently fast for my app.

For each triangle in mesh, check if occluded by any other triangle in mesh, thus O(n2). (I got high accuracy results from only checking whether the center point on each triangle was occluded or not, though you should at least check the triangle corner vertices, too, if accuracy is important).

On a pentium 4 machine (c++) a binary STL object of ~10,000 triangles took about 1 minute to complete.

The algorithm can be optimized up to ~40 percent by sorting the triangles first, for example by area size or distance from view point (more likely to occlude, so you can skip more checks).

Next optimization step would be to put the triangles in an octree, which should greatly reduce number of occlusion checks.

Answer 5

Blender performs both view frustum culling and occlusion culling, based on the dynamic AABB tree acceleration structures from the Bullet physics library. Occluders and objects are represented by their bounding volume (axis aligned bounding box).

View frustum culling just traverses the AABB tree, given a camera frustum.

The occlusion culling is based on a occlusion buffer, a kind of depth buffer that is initialized using a very simple software-renderer: a basic ray tracer using the dynamic AABB tree acceleration structures. You can choose the resolution of the occlusion buffer to trade accuracy versus efficiency.

See also documentation http://wiki.blender.org/index.php/Dev:Ref/Release_Notes/2.49/Game_Engine#Performance

Blender implementation from the Blender source tree: blender\source\gameengine\Physics\Bullet\CcdPhysicsEnvironment.cpp method bool CcdPhysicsEnvironment::cullingTest(PHY_CullingCallback callback, void* userData, PHY__Vector4 *planes, int nplanes, int occlusionRes)

and the Bullet Physics SDK has some C++ sample code in Bullet/Extras/CDTestFramework.