ACM Transactions on Graphics · SIGGRAPH Asia 2021

Efficient and Robust Discrete Conformal Equivalence with Boundary

Marcel Campen · Ryan Capouellez · Hanxiao Shen · Leyi Zhu · Daniele Panozzo · Denis Zorin

Osnabrück University | Courant Institute, New York University

DOI: 10.1145/3478513.3480557 · Vol. 40, No. 6 · December 2021

Use ↓ / ↑, scroll wheel, or Space to navigate · F for fullscreen

Outline

02 / 16

This talk walks through the problem, the mathematical machinery, our algorithmic contributions, and the empirical results.

01

Motivation & problem statement

02

Discrete conformal equivalence

03

Why fixed triangulations fail

04

Two flip strategies: degeneration vs. Delaunay

05

The hyperbolic Ptolemy trick

06

Newton algorithm with line search

07

Boundary handling: symmetric double cover

08

Symmetric flip catalogue

09

Results on real meshes

10

Numerical limits & comparison

Motivation & Problem

03 / 16

Given a manifold triangle mesh $M=(V,E,F)$ with edge lengths $\ell:E\to\mathbb{R}^{>0}$ and a target curvature $\hat\kappa_i$ per vertex, find new edge lengths that realise these curvatures while remaining conformally equivalent to the input.

Discrete curvature

Let $\Theta_i = \sum_{T_{ijk}}\alpha^i_{jk}$ be the angle sum at $v_i$. Then

\kappa_i = \begin{cases}2\pi - \Theta_i & v_i\text{ interior (Gaussian)}\\ \pi - \Theta_i & v_i\text{ boundary (geodesic)}\end{cases}

Applications

Flattenings: prescribe $\hat\kappa_i = 0$ in the interior.
Cone metrics: prescribe non-zero $\hat\kappa$ at a few cone points.
Seamless quad maps: $\hat\kappa_i = k_i\,\pi/2$ with $k_i\in\mathbb{Z}$.

Conformal scale factor on a complex model — easily spans many orders of magnitude.

Why is this hard?

Conformal scale factors can span hundreds of orders of magnitude.
Triangle inequality cuts the feasible region $\Omega$ into a tricky shape.
Surfaces with boundary need symmetry-aware machinery.

Discrete Conformal Equivalence

04 / 16

Per-vertex log-scale factors $\mathbf{u}:V\to\mathbb{R}$ reshape edge lengths multiplicatively (Luo, 2004):

\tilde\ell_{ij}(\mathbf{u}) \;=\; \ell_{ij}\;\exp\!\Big(\tfrac{u_i+u_j}{2}\Big)

For target angles $\hat\Theta$, a conformally equivalent metric satisfies, for every $i$:

g_i(\mathbf{u}) \;=\; \hat\Theta_i \;-\; \Theta_i(\mathbf{u}) \;=\; \hat\Theta_i \;-\; \sum_{T_{ijk}}\alpha^i_{jk}(\mathbf{u}) \;=\; 0

Key fact (Springborn 2008)

$\mathbf{g}(\mathbf{u})$ is the gradient of a twice-differentiable convex energy on the feasible set $\Omega_M\subset\mathbb{R}^n$.

So in principle a Newton method on $\mathbf{u}$ converges to the unique optimum.

The catch

The optimum may live outside $\Omega_M$ — the prescribed $\hat\Theta$ may be unreachable with the input triangulation.

For a vertex $v_i$ of valence $k$, no Euclidean metric admits

\kappa_i \;\le\; (2-k)\pi

since each interior angle is bounded by $\pi$.

Resolution. Allow the triangulation itself to change during optimisation.

Two Strategies for Dynamic Triangulation

05 / 16

Left: flip-on-degeneration. Right: flip-on-Delaunay-violation. Light blue: feasible $\Omega$. White: Delaunay cell $\Delta$. The cross marks the current $\mathbf{u}$.

Degeneration flips

Luo 2004; Campen et al. 2017

Flip when a triangle degenerates (boundary of $\Omega$).
Stays in Euclidean feasible region.
Must locate every flip event along the path.
Open theoretical issues with simultaneous degeneracies.

Delaunay flips

Gu et al. 2018; Springborn 2019

Flip when four vertices become co-circular (boundary of $\Delta$).
Maintains an intrinsic Delaunay triangulation.
Energy becomes convex on all of $\mathbb{R}^n$.
More flips, but each is local and cheap.

The Delaunay strategy unlocks an unconstrained Newton method — and crucially, a hyperbolic re-interpretation that lets flips be applied in any order.

The Hyperbolic Ptolemy Trick

06 / 16

Instead of marching $t$ from 0 to 1 and detecting each Delaunay-critical event, jump straight to $t=1$ and run a generic flip algorithm on the (possibly invalid) lengths.

Algebraic Delaunay test

An edge $e_{ij}$ shared by triangles $T_{ijk},T_{jim}$ is Delaunay iff

\frac{\tilde\ell_{jk}^2+\tilde\ell_{ki}^2-\tilde\ell_{ij}^2}{\tilde\ell_{jk}\,\tilde\ell_{ki}} \;+\; \frac{\tilde\ell_{jm}^2+\tilde\ell_{mi}^2-\tilde\ell_{ij}^2}{\tilde\ell_{jm}\,\tilde\ell_{mi}} \;\ge\; 0

Ptolemy length update

When a flip swaps $e_{ij}\to e_{km}$ in an inscribed quadrilateral:

\boxed{\;\ell_{km} \;=\; \frac{\ell_{jk}\,\ell_{im} \;+\; \ell_{ki}\,\ell_{mj}}{\ell_{ij}}\;}

Applied in the original metric — scale factors $u_i$ cancel.

A Delaunay-critical edge $e_{ij}$ in an inscribed quadrilateral, replaced by $e_{km}$.

Proposition (Weeks; Gu et al.)

Starting from any conformally scaled lengths $\tilde\ell$ — even if they violate the triangle inequality — the flip algorithm using the algebraic test and Ptolemy update terminates with an intrinsic Delaunay triangulation, conformally equivalent to the input. Flips may be applied in any order.

Newton Algorithm

07 / 16

function FindConformalMetric(M, ℓ, Θ̂): u ← 0 (M, ℓ) ← MakeDelaunay(M, ℓ, u) while not converged(M, ℓ, u): g ← Θ̂ − Θ(M, ℓ̃) # gradient H ← Hessian(M, ℓ̃) # Hessian d ← solve(H d = −g) # Newton dir. (M, ℓ, u) ← LineSearch(M, ℓ, u, d) ℓ̃ ← ScaleConformally(M, ℓ, u) return (M, ℓ̃)

Each iteration solves one sparse SPD system. Re-flipping happens lazily inside the line search.

Line search innovations

Trial Delaunay re-flip after every step using Ptolemy, so the Newton direction can step freely beyond $\Omega$.
Armijo-like acceptance test combining gradients at the full and half step: $\tfrac12\!\left(\mathbf{d}^{\!\top}\!g_{1} + \mathbf{d}^{\!\top}\!g_{1/2}\right) \;\le\; \alpha\,\mathbf{d}^{\!\top}\!g_0$
Backtracking until the projected gradient $\mathbf{d}^{\!\top}\!g(\mathbf{u}+\mathbf{d}) \le 0$.

Empirical convergence

$\le 10^{-10}$ angle accuracy in < 15 Newton iterations on the standard MPZ dataset.
0.4 s average wall time on a 1K-vertex sphere with random target curvatures.

Surfaces with Boundary — Symmetric Double Cover

08 / 16

Glue two reflected copies of the boundaried mesh along their boundary loops. The result is closed but carries a reflection symmetry $R$.

Reduce the boundary case to the closed case (Sun et al. 2015 idea), then run the closed-case Newton algorithm — but the symmetry $R$ must be preserved at every step.

What goes wrong with naïve flipping

The reflection creates stable Delaunay-critical configurations: many quadruples become co-circular simultaneously.
Some flips would break $R$; others must happen in coordinated mirror pairs.

Our combinatorial machinery

Classify every edge / face by symmetry class: F¹, F², Fˢ; same for edges.
Every flip is labelled by a triple $(\text{face}_a,\text{edge},\text{face}_b)$ — only a small number of combinations actually occur.
Prove that several of these combinations are Delaunay regardless of metric and can be skipped (Prop. on label compatibility).
For the rest, give explicit halfedge-cycle and reflection-map updates.

Symmetric Flip Catalogue

09 / 16

Symmetric pair flips

Two mirror-image flips executed jointly to preserve the reflection $R$.

Self-symmetric (on-axis) flips

A single flip that is its own mirror image — happens at edges lying on the symmetry line.

Why this matters. Without the catalogue, naïvely applying the closed-case flip algorithm on a symmetric mesh produces broken symmetry, runaway flips at the boundary, or incorrect Delaunay states. The classification gives a finite, provably-correct flip vocabulary.

Results — Closed Surfaces

10 / 16

Conformal maps on the Myles et al. 2014 dataset, visualised with an adaptive grid texture. Cone vertices in green/red. Numbers in the corner indicate the number of orders of magnitude spanned by the conformal scale.

Results — Surfaces with Boundary

11 / 16

Geodesic curvature prescribed to zero along boundary loops — the texture grid lines therefore meet the boundary at a constant angle per loop.

Results — Cut-Aligned Maps

12 / 16

Closed models cut to disk topology along a cut graph (black). Geodesic curvature $\hat\kappa = \pi$ is prescribed along the cut so it becomes axis-aligned in the parametrisation. Numerically the most demanding scenario — one example spans 55 orders of magnitude in scale.

Pushing the Limits — Single-Cone Stress Test

13 / 16

A genus-6 torus with all curvature concentrated at one vertex. Top to bottom: input mesh; resulting intrinsic retriangulation; overlay triangulation; hierarchical grid texture spanning 25 levels.

Concentrate all curvature at a single vertex of a $g$-torus (cone angle $2\pi(2g-1)$):

232

orders of magnitude in scale at $g=12$ (still benign in double precision)

$10^{-29}$

residual at $g=150$ with 200-bit arithmetic

611

orders of magnitude at $g=400$

$10^{-65}$

residual at $g=400$ with 400-bit arithmetic

By varying arithmetic precision we can exchange compute for accuracy on truly extreme inputs — there is no fundamental algorithmic barrier.

Comparison vs. Degeneration-Flip Method

14 / 16

73×

average speed-up over the degeneration-flip method on 1000 random cases (10K-vertex sphere)

0.4 s

average wall time to $\varepsilon = 10^{-10}$
vs. 29.6 s for degeneration flips

$10^{-10}$

angle accuracy reached in < 15 Newton iterations on the standard dataset

Why faster?

More flips (cheap, local) but far fewer linear system solves (expensive, global). The Newton step is unconstrained, so the line search no longer fights with feasibility boundaries.

Why more robust?

The hyperbolic interpretation lets intermediate states violate the triangle inequality safely. Extreme small/large prescribed angles converge in cases where the degeneration-flip method stalls or diverges.

Contributions

15 / 16

✓ An efficient, robust Newton algorithm for discrete conformal equivalence built on the hyperbolic-Delaunay framework of Gu et al. and Springborn — with a new line search that exploits the algorithm’s ability to flip in arbitrary order.
✓ First clean treatment of surfaces with boundary via a symmetric double cover, including a complete classification of symmetric flips and proofs of which configurations are unconditionally Delaunay.
✓ Stable handling of Delaunay-critical configurations introduced by symmetry — a previously open algorithmic issue.
✓ A construction of a continuous conformal map from the discrete metric using the overlay data structure of Fisher et al. — usable for parametrisation and quadrangulation.
✓ Extensive numerical evaluation, including arbitrary-precision experiments spanning hundreds of orders of magnitude in scale.

Thank you

Code, data, and additional results accompany the ACM TOG publication.

Marcel Campen, Ryan Capouellez, Hanxiao Shen, Leyi Zhu, Daniele Panozzo, Denis Zorin
ACM Transactions on Graphics (SIGGRAPH Asia), Vol. 40, No. 6, December 2021
DOI 10.1145/3478513.3480557