Foldover-free maps

Implementation of the Foldover-free maps in 50 lines of code paper by Garanzha et al.

Usage

import mouette as M
untangler = M.parametrization.WinslowInjectiveEmbedding(mesh, uv_init, lmbd=1.)
untangler.run()

See this script for a full example.

Method

Given a triangulation \(M=(V,T)\) of a disk-topology object and some initial \(uv\)-coordinates on the vertices of \(M\), this method optimizes the \(uv\)-coordinates under fixed boundary so that no triangle is inverted in the final \(uv\)-mapping. This is done through the optimization of an energy function that acts on jacobian matrices \(J \in \mathbb{R}^2\) of each triangle elements:

\[ \min_J f_\varepsilon(J) + g_\varepsilon(J)\]

where:

\[f_\varepsilon(J) = \frac{\text{tr}(J^TJ)}{\chi(\det J, \varepsilon)} \quad \quad g_\varepsilon(J) = \frac{\det{J}^2 + 1}{\chi(\det J,\varepsilon)}\]

and \(\chi\) is a regularization function:

\[\chi(D, \varepsilon) = \frac{D + \sqrt{\varepsilon^2 + D^2}}{2}.\]

\(\varepsilon\) is chosen during optimization as a decreasing sequence.

`WinslowInjectiveEmbedding(mesh, uv_init, lmbd=1.0, n_iter_max=10000, stop_if_positive=False, verbose=True, **kwargs)`

Bases: BaseParametrization

Foldover-free map to the plane: computes an injective embedding in the plane starting from the provided \(uv\)-coordinates by minimizing the regularized Winslow functionnal of Garanzha et al. [1]. This class is essentially a wrapper around the untangle function.

Warning

The input mesh should have the topology of a disk.

UV coordinates are computed per vertex and not per corner. See mouette.attributes.scatter_vertices_to_corners for conversion.

References

[1] Foldover-free maps in 50 lines of code, Garanzha et al., ACM ToG 2021

Example

See https://github.com/GCoiffier/mouette/blob/main/examples/winslow_untangle.py

Parameters:

Name	Type	Description	Default
`mesh`	`SurfaceMesh`	the supporting mesh. Should be a surface with disk topology.	required
`uv_init`	`ArrayAttribute`	array of initial uv-coordinates per vertices. np.array of shape (V,2) or mouette.ArrayAttribute object.	required
`lmbd`	`float`	weighting term between the two energies. Higher lambda means more focus on area preservation instead of angle preservation. Defaults to 1.	`1.0`
`n_iter_max`	`int`	maximal number of BFGS iterations. Defaults to 10_000.	`10000`
`stop_if_positive`	`bool`	whether to stop the optimization as soon as all determinants are positive. Defaults to False.	`False`
`verbose`	`bool`	verbose mode. Defaults to True.	`True`

Other Parameters:

Name	Type	Description
`ref_jacs`	`ndarray`	array of shape (F,2,2) that contains, for each face, the 2x2 reference Jacobian of the face. If not provided, reference Jacobians are taken as the identity matrix. Defaults to None.
`areas`	`Attribute`	face areas, or weight per face in winslow energy. If not provided, weights are taken as 1 for each face. Defaults to None.
`solver_verbose`	`bool`	Verbose tag for the L-BFGS solver. Defaults to False.

Attributes:

Name	Type	Description
`uvs`	`Attribute`	an attribute containing the uv-coordinates of the parametrization

`flat_mesh` `property`

A flat representation of the mesh where uv-coordinates are copied to xy.

Returns:

Name	Type	Description
`SurfaceMesh`	`SurfaceMesh`	the flat mesh

`run()`

Calls the solver.

Raises:

Type	Description
`Exception`	fails if the mesh is not a triangulation of a topological disk

`untangle(points, locked, triangles, ref_jacs, verbose=False, **kwargs)`

Minimizes the regularized Winslow functional to untangle a 2D triangulation.