Least squares conformal maps for automatic texture atlas generation

ABSTRACT

A Texture Atlas is an efficient color representation for 3D Paint Systems. The model to be textured is decomposed into charts homeomorphic to discs, each chart is parameterized, and the unfolded charts are packed in texture space. Existing texture atlas methods for triangulated surfaces suffer from several limitations, requiring them to generate a large number of small charts with simple borders. The discontinuities between the charts cause artifacts, and make it difficult to paint large areas with regular patterns.In this paper, our main contribution is a new quasi-conformal parameterization method, based on a least-squares approximation of the Cauchy-Riemann equations. The so-defined objective function minimizes angle deformations, and we prove the following properties: the minimum is unique, independent of a similarity in texture space, independent of the resolution of the mesh and cannot generate triangle flips. The function is numerically well behaved and can therefore be very efficiently minimized. Our approach is robust, and can parameterize large charts with complex borders.We also introduce segmentation methods to decompose the model into charts with natural shapes, and a new packing algorithm to gather them in texture space. We demonstrate our approach applied to paint both scanned and modeled data sets.

REFERENCES

• 1: Maneesh Agrawala , Andrew C. Beers , Marc Levoy, 3D painting on scanned surfaces, Proceedings of the 1995 symposium on Interactive 3D graphics, p.145-ff., April 09-12, 1995, Monterey, California, United States [doi>10.1145/199404.199429]
• 2: Yossi Azar , Leah Epstein, On two dimensional packing, Journal of Algorithms, v.25 n.2, p.290-310, Nov. 1997 [doi>10.1006/jagm.1997.0876 ]
• 3: P. Cignoni , C. Montani , R. Scopigno , C. Rocchini, A general method for preserving attribute values on simplified meshes, Proceedings of the conference on Visualization '98, p.59-66, October 18-23, 1998, Research Triangle Park, North Carolina, United States
• 4: Matthias Eck , Tony DeRose , Tom Duchamp , Hugues Hoppe , Michael Lounsbery , Werner Stuetzle, Multiresolution analysis of arbitrary meshes, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.173-182, September 1995 [doi>10.1145/218380.218440]
• 5: J. Eells and L. Lemaire. Another report on harmonic maps. Bull. London Math. Soc., 20:385-524, 1988.
• 6: Michael S. Floater, Parametrization and smooth approximation of surface triangulations, Computer Aided Geometric Design, v.14 n.3, p.231-250, April 1997 [doi>10.1016/S0167-8396(96)00031-3 ]
• 7: Igor Guskov , Kiril Vidimče , Wim Sweldens , Peter Schröder, Normal meshes, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.95-102, July 2000 [doi>10.1145/344779.344831]
• 8: Steven Haker , Sigurd Angenent , Allen Tannenbaum , Ron Kikinis , Guillermo Sapiro , Michael Halle, Conformal Surface Parameterization for Texture Mapping, IEEE Transactions on Visualization and Computer Graphics, v.6 n.2, p.181-189, April 2000 [doi>10.1109/2945.856998 ]
• 9: Pat Hanrahan , Paul Haeberli, Direct WYSIWYG painting and texturing on 3D shapes, Proceedings of the 17th annual conference on Computer graphics and interactive techniques, p.215-223, September 1990, Dallas, TX, USA
• 10: K. Hormann and G. Greiner. MIPS: An efficient global parametrization method. In P.-J. Laurent, P. Sablonnière, and L. Schumaker, editors, Curve and Surface Design: Saint-Malo 1999, pages 153-162. Vanderbilt University Press, 2000.
• 11: Andreas Hubeli , Markus Gross, Multiresolution feature extraction for unstructured meshes, Proceedings of the conference on Visualization '01, October 21-26, 2001, San Diego, California
• 12: Monica K. Hurdal , Philip L. Bowers , Ken Stephenson , De Witt L. Sumners , Kelly Rehm , Kirt Schaper , David A. Rottenberg, Quasi-Conformally Flat Mapping the Human Cerebellum, Proceedings of the Second International Conference on Medical Image Computing and Computer-Assisted Intervention, p.279-286, September 19-22, 1999
• 13: Takeo Igarashi , Dennis Cosgrove, Adaptive unwrapping for interactive texture painting, Proceedings of the 2001 symposium on Interactive 3D graphics, p.209-216, March 2001 [doi>10.1145/364338.364404]
• 14: Venkat Krishnamurthy , Marc Levoy, Fitting smooth surfaces to dense polygon meshes, Proceedings of the 23rd annual conference on Computer graphics and interactive techniques, p.313-324, August 1996 [doi>10.1145/237170.237270]
• 15: Francis Lazarus , Anne Verroust, Level set diagrams of polyhedral objects, Proceedings of the fifth ACM symposium on Solid modeling and applications, p.130-140, June 08-11, 1999, Ann Arbor, Michigan, United States [doi>10.1145/304012.304025]
• 16: Aaron W. F. Lee , Wim Sweldens , Peter Schröder , Lawrence Cowsar , David Dobkin, MAPS: multiresolution adaptive parameterization of surfaces, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.95-104, July 1998 [doi>10.1145/280814.280828]
• 17: Bruno Lévy, Constrained texture mapping for polygonal meshes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.417-424, August 2001 [doi>10.1145/383259.383308]
• 18: Bruno Lévy , Jean-Laurent Mallet, Non-distorted texture mapping for sheared triangulated meshes, Proceedings of the 25th annual conference on Computer graphics and interactive techniques, p.343-352, July 1998 [doi>10.1145/280814.280930]
• 19: Pascal Lienhardt, Extension of the Notion of Map and Subdivisions of a Three-Dimensional Space, Proceedings of the 5th Annual Symposium on Theoretical Aspects of Computer Science, p.301-311, February 11-13, 1988
• 20: Jérôme Maillot , Hussein Yahia , Anne Verroust, Interactive texture mapping, Proceedings of the 20th annual conference on Computer graphics and interactive techniques, p.27-34, September 1993 [doi>10.1145/166117.166120]
• 21: Victor J. Milenkovic, Rotational polygon containment and minimum enclosure using only robust 2D constructions, Computational Geometry: Theory and Applications, v.13 n.1, p.3-19, May 1999 [doi>10.1016/S0925-7721(99)00006-1 ]
• 22: Hiroshi Murata , Kunihiro Fujiyoshi , Shigetoshi Nakatake , Yoji Kajitani, Rectangle-packing-based module placement, Proceedings of the 1995 IEEE/ACM international conference on Computer-aided design, p.472-479, November 05-09, 1995, San Jose, California, United States
• 23: Hans Køhling Pedersen, Decorating implicit surfaces, Proceedings of the 22nd annual conference on Computer graphics and interactive techniques, p.291-300, September 1995 [doi>10.1145/218380.218458]
• 24: U. Pinkall and K. Polthier. Computing discrete minimal surfaces and their conjugates. Experimental Math., 2(15), 1993.
• 25: Dan Piponi , George Borshukov, Seamless texture mapping of subdivision surfaces by model pelting and texture blending, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.471-478, July 2000 [doi>10.1145/344779.344990]
• 26: Emil Praun , Adam Finkelstein , Hugues Hoppe, Lapped textures, Proceedings of the 27th annual conference on Computer graphics and interactive techniques, p.465-470, July 2000 [doi>10.1145/344779.344987]
• 27: Pedro V. Sander , John Snyder , Steven J. Gortler , Hugues Hoppe, Texture mapping progressive meshes, Proceedings of the 28th annual conference on Computer graphics and interactive techniques, p.409-416, August 2001 [doi>10.1145/383259.383307]
• 28: A. Sheffer and E. de Sturler. Param. of faceted surfaces for meshing using angle-based flattening. Engineering with Computers, 17(3):326-337, 2001.
• 29: Yoshihisa Shinagawa , Tosiyasu L. Kunii , Yannick L. Kergosien, Surface Coding Based on Morse Theory, IEEE Computer Graphics and Applications, v.11 n.5, p.66-78, September 1991 [doi>10.1109/38.90568 ]
• 30: W. Tutte. Convex representation of graphs. In Proc. London Math. Soc., volume 10, 1960.
• 31: G. Zigelman , R. Kimmel , N. Kiryati, Texture Mapping Using Surface Flattening via Multidimensional Scaling, IEEE Transactions on Visualization and Computer Graphics, v.8 n.2, p.198-207, April 2002 [doi>10.1109/2945.998671 ]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.3 Picture/Image Generation

Additional Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.7 Three-Dimensional Graphics and Realism
          Subjects: Color, shading, shadowing, and texture
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.3 Enhancement
          Subjects: Geometric correction
      I.4.7 Feature Measurement
          Subjects: Texture

General Terms:
Algorithms

Keywords:
paint systems, polygonal modeling, texture mapping