Master's Thesis: Efficient Triangle Reordering for Improved Vertex Cache Utilisation in Realtime Rendering


In this thesis, realtime rendering optimisations based on the reordering of data and changing of data format are evaluated. The optimisations include improved vertex cache utilisation, overdraw reduction, improved vertex data read patterns and conversion of inefficient triangle strips into triangle lists. The improvements are evaluated by integrating them into existing high-level 3D graphics frameworks for embedded environments such as M3G. In particular, fast algorithms for reordering triangles in order to improve the utilisation of vertex caches are studied. The memory usage and run time performance of the algorithms are improved by making small compromises in the end result.

Full content


(These errors have been corrected in the PDF online.)

Algorithm implementations

The sample implementations in the appendix of the thesis are available for download, licensed under the zlib license:


// Martin Storsjö ()