A fan growing algorithm for efficient vertex caching

In this paper we describe an algorithm to speed up the rendering of triangulated meshes. The gap between the microprocessor's speed and the memory's speed continuously increases so it is important to address, on the software side, the possibilities for reducing this difference. The algorithm reorganises the traversal of the vertex data by taking advantage of the introduction of a vertex cache on the graphics card. By enabling maximum reuse of the vertices in the cache, we reduce the number of bytes that need to be transmitted on the memory-to-processor bus. Our orientation and perimeter constrained fan-growing algorithm can typically give an extra 25% bandwidth saving compared to a standard stripification algorithm. Furthermore, it exhibits cache miss rates per triangle of around 0.65; which means that on average less than one vertex per triangle needs to be loaded from the memory. Our method is similar to a previous approach that uses triangle strips and cache optimisation. The two methods provide equivalent bandwidth savings but our technique can produce significant savings in the execution time.