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

Fast Triangle Reordering for Vertex Locality and Reduced Overdraw
ACM Transactions on Graphics (Proc. SIGGRAPH), August 2007

Pedro V. Sander, Diego Nehab, Joshua Barczak

(a) Lin and Yu 2006,
4.76sec, 0.63 ACMR
(b) Hoppe 1999,
226ms, 0.65 ACMR
(c) Our work,
51ms, 0.69 ACMR
(d) Nehab et al. 2006,
40sec, 1.21 MOVR, 0.73 ACMR
(e) Our work,
76ms, 1.18 MOVR, 0.72 ACMR

Vertex cache efficiency and overdraw. Views of a 40k triangle Dragon model are shown, where red regions represent cache misses, and dark regions represent high overdraw rate. As a preprocessing stage, real-time rendering applications optimize the order triangles are issued to reduce the average post-transform vertex cache miss ratio (ACMR) (a-c). Recent algorithms also minimize the overdraw ratios (OVR) (d-e) with little cache degradation. We present novel algorithms that result in excellent vertex cache efficiency (c) as well as low overdraw (e). Our methods are significantly faster than previous approaches (compare timings), and are suitable for run-time execution.


We present novel algorithms that optimize the order in which triangles are rendered, to improve post-transform vertex cache efficiency as well as for view-independent overdraw reduction. The resulting triangle orders perform on par with previous methods, but are orders magnitude faster to compute. The improvements in processing speed allow us to perform the optimization right after a model is loaded, when more information on the host hardware is available. This allows our vertex cache optimization to often outperform other methods. In fact, our algorithms can even be executed interactively, allowing for re-optimization in case of changes to geometry or topology, which happen often in CAD/CAM applications. We believe that most real-time rendering applications will immediately benefit from these new results.

Citation (BibTeX)

Pedro V. Sander, Diego Nehab, and Joshua Barczak. Fast Triangle Reordering for Vertex Locality and Reduced Overdraw. ACM Transactions on Graphics (Proc. SIGGRAPH) 26(3), August 2007.

  PDF file