A fan growing algorithm for efficient vertex caching

Franzetti, T., Day, A. M. and Arnold, D. B. (2003) A fan growing algorithm for efficient vertex caching. Computers & Graphics, 27 (5). pp. 773-789. ISSN 0097-8493

Full text not available from this repository. (Request a copy)


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.

Item Type: Article
Faculty \ School: Faculty of Science > School of Computing Sciences
UEA Research Groups: Faculty of Science > Research Groups > Computer Graphics (former - to 2018)
Faculty of Science > Research Groups > Interactive Graphics and Audio
Depositing User: Vishal Gautam
Date Deposited: 13 Jun 2011 11:40
Last Modified: 16 Jun 2023 23:40
URI: https://ueaeprints.uea.ac.uk/id/eprint/22236
DOI: 10.1016/S0097-8493(03)00150-X

Actions (login required)

View Item View Item