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

Abstract

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

• The full thesis as PDF

Errata

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

• Page 27, Table 6.1; The length of the nextCandidates array should be 3*maxAdjacency

Algorithm implementations

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

• Tipsify
• Forsyth's algorithm

Contact

// Martin Storsjö ()