A fan growing algorithm for efficient vertex caching

T. Franzetti, A.M. Day, David Arnold

Research output: Contribution to journalArticle

Abstract

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.
Original languageEnglish
Pages (from-to)773-789
Number of pages17
JournalComputers and Graphics
Volume27
Issue number5
Publication statusPublished - Oct 2003

Keywords

  • Graphics processors
  • Graphics data structures
  • Geometric algorithms

Fingerprint Dive into the research topics of 'A fan growing algorithm for efficient vertex caching'. Together they form a unique fingerprint.

  • Cite this

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