Partitioning Meshes into Strips using the Enhanced Tunnelling Algorithm (ETA)

Abstract

Triangle meshes are the most used representations for three-dimensional objects, and triangle strips are the organization of triangles mostly used for efficient rendering. Since the problem of optimal strip decomposition of a given mesh is NP-complete, many different heuristics have been proposed; the quality of the stripification is usually evaluated using standard indicators as the total number of strips, the number of isolated triangles, the cache coherence, the number of swap vertices. In this paper we present the Enhanced Tunnelling Algorithm (ETA), a stripification method working on the dual graph of a mesh. The method uses a sophisticated mechanism of dynamical update of identifiers, guided by a localization procedure. The algorithm adopts a modified search approach in the dual graph that accelerated the convergence speed of the algorithm. The ETA results efficient and robust, able to deal with datasets of any dimension. The quality of the stripification is remarkable: very few strips (not seldom just one), no isolated triangles, good cache coherence (ACMR value), good number of vertex per triangle.