Publications

Publications by year

2014  2013  2012  2011  2010  2009  2008  2007  2006  2005  2004  2003  2002  2001  2000  1999  1998  

Most documents on this website are protected by copyright. By clicking on a PDF icon, you confirm that you or your institution has the right to do so. Note that the definitive versions of all EG papers (Eurographics,...) can be downloaded from http://www.eg.org/EG/DL. ACM papers (Siggraph, ...) can be downloaded from http://www.acm.org/dl/.

 

“Least Squares Conformal Maps for Automatic Texture Atlas Generation”
Bruno Lévy, Sylvain Petitjean, Nicolas Ray and Jérome Maillot
ACM SIGGRAPH conference proceedings, 2002

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.

BibTex reference

@INPROCEEDINGS{levy:LSCM:2002,
   AUTHOR     = "Lévy, Bruno and Petitjean, Sylvain and Ray, Nicolas and Maillo
                   t, Jérome",
   TITLE      = "Least Squares Conformal Maps for Automatic Texture Atlas Generation",
   BOOKTITLE  = "ACM SIGGRAPH conference proceedings",
   YEAR       = "2002",
   EDITOR     = "ACM",
   MONTH      = "Jul",
   URL        = "http://www.loria.fr/publications/2002/A02-R-065/A02-R-065.ps",
}

Supplemental material, links, hindsight ...

Further reading

For a detailed explanation of LSCM and other parameterization methods, see our book Polygon Mesh Processing (Botsch, Kobbelt, Pauly, Alliez and Levy), Chapter 3 (Differential Geometry) and Chapter 5 (Mesh Parameterization).

Resources

  • For an easier-to-understand explanation of the method, see the SIGGRAPH 2007 Parameterization course notes, page 38 and Chapter 10 (pages 79-89). The reader interested in complex analysis may read pages 39,40 but it's not necessary to understand and implement the method.
  • An implementation is available in our OpenNL numerical library (if you need something you can include in your own application),
  • ... and also in Graphite (if you need a GUI).
  • The textured Stanford bunny (teaser image) is available here .
  • The 3D OpenSource modeler Blender now offers LSCM texture unwrapping. Brecht Van Lommel and Jens Ole Wund integrated OpenNL in Blender, more details given here and here .
  • Tutorials for using LSCM in blender: here , here and here (with video).
  • Microsoft's UVatlas (part of DirectX) uses our texture packing algorithm.
  • The 3D modeler Silo uses LSCM for texture atlas generation.

Erratum and discussions

In our paper about Least Squares Conformal Maps, presented at Siggraph in July 2002, we have erroneously claimed that the orientation of the triangles is preserved. Further investigations have shown that the gradient of the LSCM function is equal to the gradient of the Dirichlet energy for inner vertices (i.e. Pinkall's cotangent formula). Therefore, like all other approaches based on this formula triangle flips may occur when the involved coefficients become negative. In practice, we have not observed this phenomenon in real data sets, and our segmentation method splits the corresponding neighborhoods. However, we have found the following 4-triangles surface, for which this problem occurs (Michael Floater has also a similar example on his web-page).

p1 = (3 0 1)

p2 = (1 1 0)

p3 = (0 0 0)

p4 = (1 -1 0)

T1 = (p1, p2, p3)

T2 = (p1, p3, p4)

T3 = (p1, p4, p2)

We are currently investigating ways of characterizing configurations where this problem occurs. Before we have a clean solution, this problem can be fixed using one of the following strategies:

  • As done by Desbrun and Alliez, use Rivara's method, enabling to remove obtuse angles by inserting new vertices in the triangulation.
  • As done by Sheffer, use constrained optimization to enforce the desired properties. In our case, constraining the sign of the Jacobian preserves the orientation of the triangles.
  • Make a chart boundary split the concerned neighborhoods.

Note that this problem does not concern the other properties (quadratic expression of the conformal energy, existence and uniqueness of the solution, independance to resolution, ability to extrapolate the border by constraining two vertices only, independence to a similarity applied to those two constrained vertices).

Why did we make that mistake ?

To study the properties of LSCM, we construct a mesh using two basic operations:

  • glue, i.e. add a new triangle to the border, by connecting three existing vertices;
  • join, i.e. add a new triangle and a new vertex to the border.
Any triangulation homeomorphic to a disc can be constructed by these two operations. Then, we study how these operations modify the linear system solved by LSCM. For the existence and uniqueness (i.e. to prove that the matrix is of maximal rank), join is the easy case (adding a row to a matrix cannot decrease its rank) and glue requires more work (since it adds a triangle and a vertex, it adds a row and a column to the matrix). For the orientation of the triangles (i.e. the sign of the Jacobian), once we had solved what we had taken for the hard case (i.e. glue), we thought we were done. But for the orientation of the triangles, the easy and hard cases are reversed as compared to the rank problem !! In fact, glue is the easy case, and join requires a more careful analysis. Knowing that, the proof in our paper shows in fact that a triangulation constructed by glue operations alone can be parameterized by LSCM without any triangle flip.

DCP = LSCM

Note: There is also a short note on Mathieu Desbrun's home page, indicating the equivalence between his Discrete Conformal Parameterization method (Eurographics, Sept 2002) and LSCM (Siggraph, July 2002).

Mathieu's remark is based on the relation: Ec + A = Ed, where Ec corresponds to the conformal energy (minimized by LSCM), A to the area of the surface, and Ed to the Dirichlet energy. If A is fixed, then it is clear that minimizing Ec and Ed is equivalent. Since that {LSCM, DCP} minimize the {conformal,Dirichlet} energy of the function going from the 3D surface to the (u,v) parameter space, the area A under consideration is the area of the (u,v) space , therefore:

  • In the case of a fixed boundary, A is fixed, and DCP=LSCM (rem: this is no longer the case in presence of triangle flips)
  • In the case of a free boundary, A changes, and more precautions should be taken to determine whether the augmented DCP method (with Mathieu's additional terms to let the border free) is equivalent to LSCM. We have also shown the equivalence between both methods (the proof is too long to be included here). However, experimentally, we have obtained different results using the two methods, and did not manage to properly extrapolate the border of complex charts with DCP. We think this comes from a numerical conditioning problem: the LSCM formulation results in a symmetric matrix, which is not the case of DCP. In fact, LSCM and DCP are the same quadratic form, with the difference that LSCM is the Gauss-reducted expression of this quadratic form.