Cotan Embedding

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.

References

• [1] Embedding a triangular graph within a given boundary, Yin Xu, Renjie Chen, Craig Gotsman and Ligang Liu, Computer Aided Geometric Design (2011)
• [2][_Global Parametrization Algorithms for Quadmeshing_](https://hal.univ-lorraine.fr/tel-04346473v1), Guillaume Coiffier, PhD Manuscript (Chapter 3)

Usage

import mouette as M

emb = M.parametrization.CotanEmbedding(mesh, uv_attributes, mode="bfgs")()

or, alternatively:

emb = M.parametrization.CotanEmbedding(mesh, uv_attributes, mode="bfgs")
emb.run()

See this script for a full example.

Method

Notations for triangle $T=(i,j,k)$

The algorithms minimizes the energy \(E_T\) per triangle, defined as:

\[E_T = D_T - A_T\]

where:

\[D_T = \displaystyle \begin{pmatrix} \cot(\alpha_i) & \cot(\alpha_j) & \cot(\alpha_k) \end{pmatrix} . \begin{pmatrix} (u_j - u_k)^2 + (v_j - v_k)^2 \\ (u_i - u_k)^2 + (v_i - v_k)^2 \\ (u_i - u_j)^2 + (v_i - v_j)^2 \end{pmatrix}\]

\[A_T = \frac{1}{2} \det \begin{pmatrix} u_j-u_i & u_k-u_i \\ v_j-v_i & v_k-v_i \end{pmatrix}\]

The first term \(D_T\) of this expression is the dot product between the vector of cotangents and the vector of opposite squared lengths. If the cotangents correspond to the angles made by \(uv\)-coordinates, then this quantity is exactly the unsigned area of triangle \(T\). The other term is half the determinant of \(uv\)-coordinates of the triangle, that is to say the signed area \(A_T\) of triangle \(T\). The energy we consider per triangle is simply the difference between the two.

This energy can be minimized in two ways:

The direct optimization

The first strategy to minimize the energy is to put everything inside a non-linear solver like L-BFGS. However, this optimization may result in cotangents that do not form valid triangles, hence we need to introduce the constraint: \(\cot(\alpha_i)\cot(\alpha_j) + \cot(\alpha_j)\cot(\alpha_k) + \cot(\alpha_k)\cot(\alpha_i) = 1\) for all triangles \(T\).

Using Lagrange multipliers, we are able to reformulate the constrained problem as:

\[\min_{u,v} \sum_{T=(i,j,k)} \sqrt{2( \ell_i \ell_j + \ell_j \ell_k + \ell_k \ell_i) - \ell_i^2 - \ell_j^2 - \ell_k^2} \;-\, A_T\]

where \(\ell_i = (u_j - u_k)^2 + (v_j - v_k)^2\) is the squared distance between \(j\) and \(k\) in parameter space. This means that the final energy only depends on the \(uv\)-coordinates.

The iterative approach

Alternatively, the energy can be minimized by iteratively solving linear systems involving a cotan-Laplacian, where the cotangent are updated at each step to match the cotangents given by the \(uv\)-coordinates:

\[\cot(\alpha_k) = \frac{ (u_i-u_k)(u_j-u_k) + (v_i-v_k)(v_j-v_k) }{(u_i-u_k)(v_j-v_k) - (u_j-u_k)(v_i-v_k)}.\]

This approach is more stable and provides good results in more cases, but the final parametrizations are close to conformal and thus can exhibit high area distortions.

Result

Initial flattening of a butterfly model (with folds in red)

Final result with L-BFGS approach

Final result with iterative Tutte approach

CotanEmbedding(mesh, uv_init, mode='bfgs', verbose=False, **kwargs)

Bases: BaseParametrization

Given a parametrization of a disk where boundary is fixed, we can optimize the difference between unsigned and signed areas of triangles to compute a parametrization that is foldover-free.

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] Embedding a triangular graph within a given boundary, Xu et al. (2011)

Example

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

Parameters:

Name	Type	Description	Default
mesh	SurfaceMesh	the supporting mesh.	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 False.	False
mode	str	optimization mode. Either "bfgs" or "alternate". Defaults to "bfgs".	'bfgs'

Other Parameters:

Name	Type	Description
tutte_if_convex	bool	if True and if the boundary of the shape is convex and mode=="alternate", will simply runs Tutte's embedding. Defaults to True
solver_verbose	bool	solver verbose mode. Defaults to False.

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()

Runs the optimization

Raises:

Type	Description
Exception	Fails if the mesh is not a topological disk
Exception	Fails if the mesh is not triangular

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()

Checks if the mesh is a quadrangulation

Returns:

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

is_triangular()

Checks if the mesh is a triangulation

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)