“Least squares conformal maps for automatic texture atlas generation” by Levy, Petitjean, Ray and Maillot

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.

1. M. Agrawala, A. Beers, and M. Levoy. 3D painting on scanned surfaces. In Proc. 1995 Symposium on Interactive 3D Graphics, 1995. Google Scholar
2. Y. Azar and L. Epstein. On 2d packing. J. of Algorithms, (25):290-310, 1997. Google Scholar
3. P. Cigogni, C. Montani, C. Rocchini, and R. Scopino. A general method for recovering attributes values on simplified meshes. In Proc. of IEEE Visualization Conf., pages 59-66. ACM Press, 1998. Google Scholar
4. M. Eck, T. DeRose, T. Duchamp, H. Hoppe, M. Lounsbery, and W. Stuetzle. Multiresolution analysis of arbitrary meshes. In SIGGRAPH 95 Conf. Proc., pages 173-182. Addison Wesley, 1995. Google Scholar
5. J. Eells and L. Lemaire. Another report on harmonic maps. Bull. London Math. Soc., 20:385-524, 1988.Google Scholar
6. M. Floater. Parametrization and smooth approximation of surface triangulations. Computer Aided Geometric Design, 14(3):231-250, April 1997. Google Scholar
7. I. Guskov, K. Vidimce, W. Sweldens, and P. Schröder. Normal meshes. In SIGGRAPH 00 Conf. Proc., pages 95-102. ACM Press, 2000. Google Scholar
8. S. Haker, S. Angenent, A. Tannenbaum, R. Kikinis, G. Sapiro, and M. Halle. Conformal surface parameterization for texture mapping. IEEE Transactions on Visualization and Computer Graphics, 6(2):181-189, 2000. Google Scholar
9. P. Hanrahan and P. Haeberli. Direct WYSIWYG painting and texturing on 3D shapes. In SIGGRAPH 90 Conf. Proc., pages 215-223. Addison Wesley, 1990. Google Scholar
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.Google Scholar
11. A. Hubeli and M. Gross. Multiresolution features extraction from unstructured meshes. In Proc. of IEEE Visualization Conf., 2001. Google Scholar
12. M. Hurdal, P. Bowers, K. Stephenson, D. Sumners, K. Rehms, K. Schaper, and D. Rottenberg. Quasi-conformally flat mapping the human cerebellum. In Proc. of MICCAI’99, volume 1679 of Lecture Notes in Computer Science, pages 279-286. Springer-Verlag, 1999. Google Scholar
13. T. Igarashi and D. Cosgrove. Adaptive unwrapping for interactive texture painting. In Symp. on Interactive 3D Graphics, pages 209-216. ACM, 2001. Google Scholar
14. V. Krishnamurthy and M. Levoy. Fitting smooth surfaces to dense polygon meshes. In SIGGRAPH 96 Conf. Proc., pages 313-324. Addison Wesley, 1996. Google Scholar
15. F. Lazarus and A. Verroust. Level set diagrams of polyhedral objects. In Proc. of Solid Modeling and Applications, pages 130-140. ACM Press, 1999. Google Scholar
16. A. Lee, W. Sweldens, P. Schröder, L. Cowsat, and D. Dobkin. MAPS: Multiresolution adaptive parameterization of surfaces. In SIGGRAPH 98 Conf. Proc., pages 95-104. Addison Wesley, 1998. Google Scholar
17. B. Lévy. Constrained texture mapping for polygonal meshes. In SIGGRAPH 01 Conf. Proc., pages 417-424. ACM Press, 2001. Google Scholar
18. B. Lévy and J.-L. Mallet. Non-distorted texture mapping for sheared triangulated meshes. In SIGGRAPH 98 Conf. Proc., pages 343-352. Addison Wesley, 1998. Google Scholar
19. P. Lienhardt. Extension of the notion of map and subdivisions of a 3D space. In Proc. of 5th Symp. on Theo. Aspects in Comp. Sci., pages 301-311, 1988. Google Scholar
20. J. Maillot, H. Yahia, and A. Verroust. Interactive texture mapping. In SIGGRAPH 93 Conf. Proc., pages 27-34. Addison Wesley, 1993. Google Scholar
21. V. Milenkovic. Rotational polygon containment and minimum enclosure using only robust 2D constructions. Computational Geometry, 13(1):3-19, 1999. Google Scholar
22. H. Murata, K. Fujiyoshi, S. Nakatake, and Y. Kajitani. Rectangle-packing-based module placement. In Proc. of ICCAD, pages 472-479. IEEE, 1995. Google Scholar
23. H. Pedersen. Decorating implicit surfaces. In SIGGRAPH 95 Conf. Proc., pages 291-300. Addison Wesley, 1995. Google Scholar
24. U. Pinkall and K. Polthier. Computing discrete minimal surfaces and their conjugates. Experimental Math., 2(15), 1993.Google Scholar
25. D. Piponi and G. Borshukov. Seamless texture mapping of subdivision surfaces by model pelting and texture blending. In SIGGRAPH 00 Conf. Proc., pages 471-478. ACM Press, 2000. Google Scholar
26. E. Praun, A. Finkelstein, and H. Hoppe. Lapped textures. In SIGGRAPH 00 Conf. Proc., pages 465-470. ACM Press, 2000. Google Scholar
27. P. Sander, J. Snyder, S. Gortler, and H. Hoppe. Texture mapping progressive meshes. In SIGGRAPH 01 Conf. Proc., pages 409-416. ACM Press, 2001. Google Scholar
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.Google Scholar
29. Y. Shinagawa, T. Kunii, and Y.-L. Kergosien. Surface coding based on Morse theory. IEEE Computer Graphics and Applications, 11(5):66-78, 1991. Google Scholar
30. W. Tutte. Convex representation of graphs. In Proc. London Math. Soc., volume 10, 1960.Google Scholar
31. G. Zigelman, R. Kimmel, and N. Kiryati. Texture mapping using surface flattening via multi-dimensional scaling. IEEE Transactions on Vis. and C.G., 2001. Google Scholar