Thursday, October 27, 2016

Cluster Culling

AMD's GPUOpen has an article on Cluster Culling

Basically for a given mesh cluster, you can often perform a variant of backface culling on the entire cluster. 

You do this by calculating a cone that represents the region in which the cluster is not visible. 
Any viewer located within the cone, is unable to see the cluster, so it can be culled.

 AMD implementation works like this: 

  1. Find the average normal of the cluster
  2. Take the dot product of each normal against the average normal, and find the minimum. 
  3. Use this as cone angle, anything greater than 0 can be culled in some situations.  
They also do some other work involving the bounding box, to prevent some errors cases they had to deal with. 

This is a smallest circle problem, the AMD solution using the average axis is rarely going to produce the tightest circle.

For my code I run multiple algorithms, the average, the min/max axis, and then run 1 round of ritters method over the data using whichever axis was the best. The average axis is pretty bad generally, so even just using min/max axis is a good improvement.

If you want an exact algorithm, you could try this method, although it will be slower to calculate.

The cull rate various heavily depending on the scene. It is also much more effective at higher details(smaller cluster size).  Sometimes it is only 1%, but I have seen it go up to around 15%.  

My engine does not generate clusters if they are outside the frustum or occluded, which reduces opportunities for culling. 
In a standard game engine with offline generated content the cull rate would likely be higher.