Princeton > CS Dept > PIXL > Graphics > Publications Local Access 

Triangle Order Optimization for Graphics Hardware Computation Culling
Symposium on Interactive 3D Graphics and Games, March 2006

Diego Nehab, Joshua Barczak, Pedro V. Sander

(a) (b) (c)

Illustration of overdraw and vertex cache efficiency. In the front views, brighter regions represent high overdraw. In the side views, brighter regions represent cache misses. (a) Rendering triangles in a front-to-back order maximizes the use of early Z-culling, but results in poor vertex cache performance. (b) Conversely, mesh locality optimizations produce excellent cache hit rates but can generate high levels of overdraw. (c) Our method combines both ideas into a view-independent ordering that results in excellent cache performance while minimizing overdraw.


We describe an automatic preprocessing algorithm that reorders triangles in a mesh so as to enable the graphics hardware to efficiently cull vertex and pixel processing at rendering time. Our method starts by dividing the mesh into planar clusters which are subsequently sorted into a view-independent order which greatly reduces overdraw. The result is an increase in the opportunities for early Z-culling, reducing pixel processing time. The clusters are then optimized for mesh locality. This produces high rates of vertex cache hits, reducing vertex processing time. We have found that our method brings the overdraw rates of a wide range of models close to that of front-to-back order, while preserving state of the art vertex cache performance. This results in higher frame-rates for pixel bound applications with no penalty to vertex-bound applications.

Citation (BibTeX)

Diego Nehab, Joshua Barczak, and Pedro V. Sander. Triangle Order Optimization for Graphics Hardware Computation Culling. Symposium on Interactive 3D Graphics and Games, March 2006.

  PDF file