and smooth approximation of surface triangulations, Michael
Floater, CAGD 1997. This paper is a classic for mapping a disk of
triangles to the plane, using a linear least-squares solution. The
boundary of the mesh is mapped to the boundary of the desired
parameterization (usually a square). Each interior vertex tries to map
to the centroid of its neighbors. This mapping is guaranteed not to
fold, if the boundary is convex.
The great thing about this paper is that it actually proves that there
is no folding.
- Basic approach: Map the boundary to a convex, closed
curve. (Usually a circle or square.) For each boundary vertex this
creates a linear constraint vertex -> u,v. For each interior vertex,
create a linear constraint that places the vertex at the centroid of
its neighbors (1/n sum vj - vi = 0), vj is the star of the vertex,
i.e., all of vi's neighbors. Solve the resulting system of equations.
- Variation: Instead of using 1/n, which equally weights all the
neighboring vertices, choose any set of weights wi such that sum wi =
1 and wi are non-negative.
- Chord length variation: choose the weights to make the relative
areas of the triangles be similar. Approach 1) use linear constraints
on the interior edges, forcing them to be particular relative lengths by weighting them by lij. wi = lij / sum lij for all edges adjacent to vi.
- Chord length variation 2: For each vertex, take the star of the
vertex and place it in the plane so that the interior edge lengths are
the same, and the ratio of interior angles is preserved. Make wi be
the area of the resulting triangles, if there are only three adjacent
vertices. Otherwise, try to do the equivalent area ratio with the
polygon defined by the star.