Single-Strip Triangulation of Manifolds with Arbitrary Topology

Title: Single-Strip Triangulation of Manifolds with Arbitrary Topology

Research Question: Can we develop an algorithm that takes a triangulated model and creates a single strip triangulation, while preserving the geometry of the input model and minimizing the increase in the number of triangles?

Methodology: The researchers developed an algorithm that applies a dual graph matching algorithm to partition the mesh into cycles. They then merge pairs of cycles by splitting adjacent triangles when necessary. New vertices are introduced at midpoints of edges, and the new triangles formed are coplanar with their parent triangles. This ensures that the visual fidelity of the geometry is not changed. The algorithm also provides tight bounds on the number of triangles needed for a single-strip representation of a model with holes on its boundary.

Results: The algorithm successfully created a single triangle loop or strip from a triangulated model while preserving the geometry of the input model. The increase in the number of triangles due to this splitting was less than 2% for all models tested. The algorithm can be used not only for efficient rendering but also for other applications, such as generating space-filling curves on manifolds of arbitrary topology.

Implications: The algorithm bridges the gap between existing research in triangle strips and provides a solution that allows for a single strip triangulation from an input triangulation. This can enable a wide range of applications, such as geometric and topological algorithms, that require a single strip representation of a model.

Link to Article: https://arxiv.org/abs/0405036v1 Authors: arXiv ID: 0405036v1