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.

`PointCloud(data=None)`

Bases: Mesh

A data structure for representing point clouds

Attributes:

Name	Type	Description
`vertices`	`DataContainer`	the container for all vertices
`__str__`	`str`	Representation of the object and its elements as a string.

`id_vertices` `property`

Shortcut for range(len(self.vertices))

`append(x)`

Shortcut for self.vertices.append(x), since we can only append elements in the 'vertices' container

`PolyLine(data=None)`

Bases: Mesh

A data structure for representing polylines.

Attributes:

Name	Type	Description
`vertices`	`DataContainer`	the container for all vertices
`edges`	`DataContainer`	the container for all edges
`__str__`		Representation of the object and its elements as a string.

`id_edges` `property`

Shortcut for range(len(self.edges))

`id_vertices` `property`

Shortcut for range(len(self.vertices))

`SurfaceMesh(data=None)`

Bases: Mesh

A data structure for representing polygonal surfaces.

Attributes:

Name	Type	Description
`vertices`	`DataContainer`	the container for all vertices
`edges`	`DataContainer`	the container for all edges
`faces`	`DataContainer`	the container for all faces
`face_corners`	`DataContainer`	the container for all corner of faces
`boundary_edges`	`list`	list of all edge indices on the boundary
`interior_edges`	`list`	list of all interior edge indices (all edges \ boundary_edges)
`boundary_vertices`	`list`	list of all vertex indices on the boundary
`interior_vertices`	`list`	list of all interior verticex indices (all vertices \ boundary_vertices)
`connectivity`	`_SurfaceConnectivity`	the connectivity utility class

`id_corners` `property`

Shortcut for range(len(self.face_corners))

`id_edges` `property`

Shortcut for range(len(self.edges))

`id_faces` `property`

Shortcut for range(len(self.faces))

`id_vertices` `property`

Shortcut for range(len(self.vertices))

`clear_boundary_data()`

Clear all boundary data. Next call to a boundary/interior container or method will recompute everything

`is_edge_on_border(u, v)`

whether edge (u,v) is a boundary edge or not

Parameters:

Name	Type	Description	Default
`u`	`int`	vertex id	required
`v`	`int`	vertex id	required

Returns:

Name	Type	Description
`bool`	`bool`	whether edge (u,v) is a boundary edge or not. Returns False if (u,v) is not a valid edge.

`is_quad()`

Returns:

Name	Type	Description
`bool`	`bool`	True if the mesh is quadrangular (all faces are quad)

`is_triangular()`

Returns:

Name	Type	Description
`bool`	`bool`	True if the mesh is triangular (all faces are triangles)

`is_vertex_on_border(u)`

whether vertex u is a boundary vertex or not.

Parameters:

Name	Type	Description	Default
`u`	`int`	vertex id	required

Returns:

Name	Type	Description
`bool`	`bool`	whether vertex `u` is a boundary vertex or not.

`ith_vertex_of_face(fid, i)`

helper function to get the i-th vertex of a face, i.e. self.faces[fid][i]

Parameters:

Name	Type	Description	Default
`fid`	`int`	face id	required
`i`	`int`	vertex id in face. Should be 0 <= vid < len(face)	required

Returns:

Name	Type	Description
`int`	`int`	the id of the i-th vertex in face `fid` (`self.faces[fid][i]`)

`pt_of_face(fid)`

point coordinates of vertices of face fid

Parameters:

Name	Type	Description	Default
`fid`	`int`	face id	required

Returns:

Name	Type	Description
`Iterable`		iterator of Vec objects representing point coordinates of vertices

`VolumeMesh(data=None)`

Bases: Mesh

`id_cells` `property`

Shortcut for range(len(self.cells))

`id_corners` `property`

Shortcut for range(len(self.face_corners))

`id_edges` `property`

Shortcut for range(len(self.edges))

`id_faces` `property`

Shortcut for range(len(self.faces))

`id_vertices` `property`

Shortcut for range(len(self.vertices))

`is_edge_on_border(*args)`

Simple test to determine if a given edge is on the boundary of the mesh.

Returns:

Name	Type	Description
`bool`	`bool`	Returns True if the given edge is on the boundary of the mesh.

`is_face_on_border(*args)`

Simple test to determine if a given face is on the boundary of the mesh.

Returns:

Name	Type	Description
`bool`	`bool`	Returns True is the given face exists and is on the boundary of the mesh

`is_tetrahedral()`

Returns:

Name	Type	Description
`bool`	`bool`	True if the mesh is tetrahedral (all cells are tetrahedra)

`WinslowInjectiveEmbedding(mesh, uv_init, 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
`verbose`	`bool`	verbose mode. Defaults to True.	`True`

Other Parameters:

Name	Type	Description
`stop_if_positive`	`bool`	whether to stop the optimization as soon as all determinants are positive. Defaults to False.
`solver_verbose`	`bool`	Verbose tag for the L-BFGS solver. Defaults to False.

`flat_mesh: SurfaceMesh` `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.

Parameters:

Name	Type	Description	Default
`points`	`ndarray[float]`	Initial position of points in 2D. Should be of shape (2*V,)	required
`locked`	`ndarray[bool]`	Which points have a fixed position. Should be of shape (V,)	required
`triangles`	`ndarray[int]`	Indices of triangles. Should be of shape (T,3)	required
`ref_jacs`	`ndarray[float]`	Perfect element to consider for Jacobian computation for each triangle. Should be of shape (T,2,2).	required
`verbose`	`(bool, optional)`	Verbose mode. Defaults to False.	`False`

Other Parameters:

Name	Type	Description
`areas`	`ndarray[float]`	Areas of triangles in original mesh. Used as a weighting term in the energy's summation. Should be of shape (T,). Defaults to np.ones(T).
`weight_angles`	`float`	weight coefficient for the angle conservation term (f). Defaults to 1.
`weight_areas`	`float`	weight coefficient for the area conservation term (g). Defaults to 1.
`iter_max`	`int`	Maximum number of iterations in the L-BFGS solver. Defaults to 10000.
`n_eps_update`	`int`	number of updates of the regularization's epsilon. Defaults to 10.
`stop_if_positive`	`bool`	enable early stopping as soon as all dets are positive. Defaults to False.

Returns:

Type	Description
`ndarray`	np.ndarray[float]: final positions of points in 2D, in shape (2V,)

References

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

Usage

Method

PointCloud(data=None)

id_vertices property

append(x)

PolyLine(data=None)

id_edges property

id_vertices property

SurfaceMesh(data=None)

id_corners property

id_edges property

id_faces property

id_vertices property

clear_boundary_data()

is_edge_on_border(u, v)

is_quad()

is_triangular()

is_vertex_on_border(u)

ith_vertex_of_face(fid, i)

pt_of_face(fid)

VolumeMesh(data=None)

id_cells property

id_corners property

id_edges property

id_faces property

id_vertices property

is_edge_on_border(*args)

is_face_on_border(*args)

is_tetrahedral()

WinslowInjectiveEmbedding(mesh, uv_init, verbose=True, **kwargs)

flat_mesh: SurfaceMesh property

run()

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

`PointCloud(data=None)`

`id_vertices` `property`

`append(x)`

`PolyLine(data=None)`

`id_edges` `property`

`id_vertices` `property`

`SurfaceMesh(data=None)`

`id_corners` `property`

`id_edges` `property`

`id_faces` `property`

`id_vertices` `property`

`clear_boundary_data()`

`is_edge_on_border(u, v)`

`is_quad()`

`is_triangular()`

`is_vertex_on_border(u)`

`ith_vertex_of_face(fid, i)`

`pt_of_face(fid)`

`VolumeMesh(data=None)`

`id_cells` `property`

`id_corners` `property`

`id_edges` `property`

`id_faces` `property`

`id_vertices` `property`

`is_edge_on_border(*args)`

`is_face_on_border(*args)`

`is_tetrahedral()`

`WinslowInjectiveEmbedding(mesh, uv_init, verbose=True, **kwargs)`

`flat_mesh: SurfaceMesh` `property`

`run()`

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