“MAPS: multiresolution adaptive parameterization of surfaces” by Lee, Sweldens, Schröder, Cowsar and Dobkin

We construct smooth parameterizations of irregular connectivity triangulations of arbitrary genus 2-manifolds. Our algorithm uses hierarchical simplification to efficiently induce a parameterization of the original mesh over a base domain consisting of a small number of triangles. This initial parameterization is further improved through a hierarchical smoothing procedure based on Loop subdivision applied in the parameter domain. Our method supports both fully automatic and user constrained operations. In the latter, we accommodate point and edge constraints to force the alignment of iso-parameter lines with desired features. We show how to use the parameterization for fast, hierarchical subdivision connectivity remeshing with guaranteed error bounds. The remeshing algorithm constructs an adaptively subdivided mesh directly without first resorting to uniform subdivision followed by subsequent sparsification. It thus avoids the exponential cost of the latter. Our parameterizations are also useful for texture mapping and morphing applications, among others.

1. BAJAJ, C. L., BERNADINI, F., CHEN, J., AND SCHIKORE, D. R. Automatic Reconstruction of 3D CAD Models. Tech. Rep. 96-015, Purdue University, February 1996.
2. BROWN, P. J. C., AND FAIGLE, C. T. A Robust Efficient Algorithm for Point Location in Triangulations. Tech. rep., Cambridge University, February 1997.
3. CERTAIN, A., POPOVld, J., DEROSE, T., DUCHAMP, T., SALESIN, D., AND STUETZLE, W. Interactive Multiresolution Surface Viewing. In Computer Graphics (SIGGRAPH 96 P1vceedings), 91-98, 1996.
4. COHEN, J., MANOCHA, D., AND OLANO, M. Simplifying Polygonal Models Using Successive Mappings. In Proceedings IEEE Visualization 97, 395-402, October 1997.
5. DOBKIN, D., AND KIRKPATRICK, D. A Linear Algorithm for Determining the Separation of Convex Polyhedra. Journal of Algorithms 6 (1985), 381-392.
6. DUCHAMP, T., CERTAIN, A., DEROSE, T., AND STUETZLE, W. Hierarchical Computation of PL harmonic Embeddings. Tech. rep., University of Washington, July 1997.
7. ECK, M., DEROSE, T., DUCHAMP, T., HOPPE, H., LOUNSBERY, M., AND STUETZLE, W. Multiresolution Analysis of Arbitrary Meshes. In Computer Graphics (SIGGRAPH 95 P1vceedings), 173-182, 1995.
8. ECK, M., AND HOPPE, H. Automatic Reconstruction of B-Spline Surfaces of Arbitrary Topological Type. In Computer Graphics (SIGGRAPH 96 P1vceedings), 325-334, 1996.
9. GARLAND, M., AND HECKBERT, P. S. Fast Polygonal Approximation of Terrains and Height Fields. Tech. Rep. CMU-CS-95-181, CS Dept., Carnegie Mellon U., September 1995.
10. GUIBAS, L., AND STOLFI, J. Primitives for the Manipulation of General Subdivisions and the Computation of Voronoi Diagrams. ACM Transactions on Graphics 4, 2 (April 1985), 74-123.
11. HECKBERT, P. S., AND GARLAND, M. Survey of Polygonal Surface Simplification Algorithms. Tech. rep., Camegie Mellon University, 1997.
12. HOPPE, H. Progressive Meshes. In Computer Graphics (SIGGRAPH 96 P1vceedings), 99-108, 1996.
13. HOPPE, H. View-Dependent Refinement of Progressive Meshes. In Computer Graphics (SIGGRAPH 97 P1vceedings), 189-198, 1997.
14. HOPPE, H., DEROSE, T., DUCHAMP, T., HALSTEAD, M., JIN, H., MCDON- ALD, J., SCHWEITZER, J., AND STUETZLE, W. Piecewise Smooth Surface Reconstruction. In Computer Graphics (SIGGRAPH 94 Proceedings), 295-302, 1994.
15. KIRKPATRICK, D. Optimal Search in Planar Subdivisions. SIAMJ. Comput. 12 (1983), 28-35.
16. KLEIN, A., CERTAIN, A., DEROSE, T., DUCHAMP, T., AND STUETZLE, W. Vertex-based Delaunay Triangulation of Meshes of Arbitrary Topological Type. Tech. rep., University of Washington, July 1997.
17. KRISHNAMURTHY, V., AND LEVOY, M. Fitting Smooth Surfaces to Dense Polygon Meshes. In Computer Graphics (SIGGRAPH 96 P1vceedings), 313- 324, 1996.
18. LOOP, C. Smooth Subdivision Surfaces Based on Triangles. Master’s thesis, University of Utah, Department of Mathematics, 1987.
19. LOUNSBERY, M. Multiresolution Analysis for Sulfaces of Arbitrary Topological Type. PhD thesis, Department of Computer Science, University of Washington, 1994.
20. LOUNSBERY, M., DEROSE, T., AND WARREN, J. Multiresolution Analysis for Surfaces of Arbitrary Topological Type. Transactions on Graphics 16, 1 (January 1997), 34-73.
21. M~CKE, E.P. Shapes and Implementations in Three-Dimensional Geometry. Technical Report UIUCDCS-R-93-1836, University of Illinois at Urbana- Champaign, 1993.
22. SCHRODER, P., AND SWELDENS, W. Spherical Wavelets: Efficiently Representing Functions on the Sphere. In Computer Graphics (SIGGRAPH 95 P~vceedings), Annual Conference Series, 1995.
23. SCHWEITZER, J. E. Analysis and Application of Subdivision Sulfaces. PhD thesis, University of Washington, 1996.
24. SPANIER, E. H. Algebraic Topology. McGraw-Hill, New York, 1966.
25. XIA, J. C., AND VARSHNEY, A. Dynamic View-Dependent Simplification for Polygonal Models. In P~vceedings Visualization 96, 327-334, October 1996.
26. ZORIN, D. Subdivision and Multiresolution Smface Representations. PhD thesis, California Institute of Technology, 1997.
27. ZORIN, D., SCHRODER, P., AND SWELDENS, W. Interpolating Subdivision for Meshes with Arbitrary Topology. In Computer Graphics (SIGGRAPH 96 P1vceedings), 189-192, 1996.
28. ZORIN, D., SCHRODER, P., AND SWELDENS, W. Interactive Multiresolution Mesh Editing. In Computer Graphics (SIGGRAPH 97 P1vceedings), 259-268, 1997.