@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",
}

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.