Single-strip triangulation of manifolds with arbitrary topology

ABSTRACT

This video illustrates a new method for subdividing the surface of a triangulated 3d polyhedron, without changing the geometry of the model, so that the triangles of the subdivided mesh can be ordered into a single triangle strip. Our method guarantees that the subdivided mesh has at most 3/2 the original number of triangles, and in practice performs much better. Our strips can be used not only for efficient rendering, but also for other applications including the generation of space filling curves.

REFERENCES

• 1: K. Akeley, P. Haeberli, and D. Burns. The tomesh.c program. Technical Report SGI Developer's Toolbox CD, Silicon Graphics, 1990.
• 2: Therese C. Biedl , Prosenjit Bose , Erik D. Demaine , Anna Lubiw, Efficient algorithms for Petersen's matching theorem, Journal of Algorithms, v.38 n.1, p.110-134, Jan. 2001 [doi>10.1006/jagm.2000.1132 ]
• 3: Mike M. Chow, Optimized geometry compression for real-time rendering, Proceedings of the 8th conference on Visualization '97, p.347-ff., October 18-24, 1997, Phoenix, Arizona, United States
• 4: David Eppstein and M. Gopi. Single-strip triangulation of manifolds with arbitrary topology. Submitted, 2004.
• 5: Francine Evans , Steven Skiena , Amitabh Varshney, Optimizing triangle strips for fast rendering, Proceedings of the 7th conference on Visualization '96, p.319-326, October 28-29, 1996, San Francisco, California, United States
• 6: Julius Peter Christian Peterson. Die theorie der regularen graphs (The Theory of Regular Graphs). Acta Mathematica, 15:193--220, 1891.
• 7: Richard Szeliski , Heung-Yeung Shum, Creating full view panoramic image mosaics and environment maps, Proceedings of the 24th annual conference on Computer graphics and interactive techniques, p.251-258, August 1997 [doi>10.1145/258734.258861]
• 8: Mikkel Thorup, Near-optimal fully-dynamic graph connectivity, Proceedings of the thirty-second annual ACM symposium on Theory of computing, p.343-350, May 21-23, 2000, Portland, Oregon, United States [doi>10.1145/335305.335345]
• 9: Xinyu Xiang , Martin Held , Joseph S. B. Mitchell, Fast and effective stripification of polygonal surface models, Proceedings of the 1999 symposium on Interactive 3D graphics, p.71-78, April 26-29, 1999, Atlanta, Georgia, United States [doi>10.1145/300523.300531]

INDEX TERMS

Primary Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Path and circuit problems

Additional Classification:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Boundary representations

General Terms:
Performance

Keywords:
constrained path planning, fundamental cycles, hamiltonian paths and cycles, path planning, space-filling curves, stripification, triangulation