Constrained Strip Generation and Management for Efficient Interactive 3D Rendering

Abstract

Representing a triangulated two manifold using a single triangle
strip is an NP-complete problem. By introducing a few Steiner
vertices, recent works find such a single-strip and hence a linear
ordering of edge-connected triangles of the entire triangulation.
In this paper, we highlight and exploit this linear order in efficient
triangle-strip management for high-performance rendering.
We present new algorithms to generate weighted single-strip representations
that respect different constraint-based clustering of triangles.
These functional constraints can be application dependent;
for example, normal-based constraints for efficient visibility culling
or spatial constraints for highly coherent vertex-caching. We also
present a hierarchical single-strip-management strategy for highperformance
interactive 3D rendering.