Progressive Embedding | About Zhongshi

Abstract

Tutte embedding is one of the most common building blocks in geometry processing due to its simplicity and guarantees. Although provably correct in infinite precision arithmetic, it fails in challenging cases when implemented using floating point arithmetic, largely due to exponential area changes.

We propose Progressive Embedding, with similar theoretical guarantees to Tutte, but more resilient to rounding error. Inspired by progressive meshes, we collapse edges on an invalid embedding to a valid, simplified mesh, then insert points back while maintaining validity. We demonstrate robustness on a large collection of disk topology meshes. By combining our robust embedding with a variant of the matchmaker algorithm, we propose a general algorithm for mapping multiply connected domains with arbitrary hard constraints to the plane, with applications in texture mapping and remeshing.

Method – collapse then grow valid – Step 1 collapse — **Method Step 1 – Collapse onto valid coarse.** Invalid Tutte (red flips) → priority queue by area distortion → link-condition edge collapses → coarse valid mesh. 1800×1125 → hero width 100%, centered, rounded corners.

Motivation: The Floating-Point Failure of a Theoretically Perfect Algorithm

Tutte solves

$$ L \mathbf{U} = 0,\quad \mathbf{U}_{\partial} = \text{fixed convex boundary}$$

with cotangent Laplacian $L$. The map is bijective if all $\det J_t > 0$ in $\mathbb{R}$. Numerically, area $A_t = \det J_t$ suffers:

$$\tilde{A}_t = A_t + \epsilon_{\text{round}}\cdot \kappa(L), \quad \kappa(L)>10^{12}\ \text{on stretched domains}$$

When $\tilde{A}_t$ flips sign, the whole algorithm tangles — a single flipped triangle invalidates downstream MiQ / parameterizations.

Method overview – feasible polygon insertion – Step 2 feasible — **Method Step 2 – Feasible Polygon.** For uninserted vertex, convex feasible polygon = intersection half-planes (green). Chebyshev center insertion maintains $area>10^{-8}$. 2400×800 ultra-wide scaled 100% width , no stretch, rounded.

Core idea: If initial embedding is invalid, simplify until valid, then grow. Validity is not repaired post-hoc; it is a hard invariant through every insertion.

Method: Progressive Stages

1. Collapse Invalid to Valid Coarse

Priority queue $Q$ of flipped triangles sorted by area distortion. Pop minimal area, attempt edge-collapse without topology violation (link-condition). Restrict embedding to coarse mesh, keep if valid. Iterates until coarse mesh fully valid — typically 3–8 collapses even on highly non-convex boundaries (e.g., 62415_sf retinal cap).

2. Feasible Polygon Insertion

For each uninserted $v$ with one-ring $\mathcal{N}(v)$ embedded validly, seek $p$ s.t.

$$\forall t \in \text{star}(v): \text{area}(t,p) > \tau_{\min}=10^{-8}$$

This is intersection of half-planes — convex polygon (possibly empty). We compute Chebyshev center:

Valid interval: linear feasibility via half-plane intersection $O(k \log k)$
Barycentric fallback: if empty, collapse further locally
Local smoothing: one Gauss-Seidel sweep minimizing symmetric Dirichlet:

$$E_{\text{SD}} = \sum_t (\sigma_1 + \sigma_1^{-1} + \sigma_2 + \sigma_2^{-1})$$ Validity preservation feasible polygon – Step 2 detail – feasible polygon

Step 2 detail – Validity: Feasible polygon (green) – intersection of half-planes from incident edges. Insert only if non-empty. $E_{SD}$ Gauss-Seidel local smoothing minimizes symmetric Dirichlet.

3. Matchmaker++: Multiply-Connected Domains

Tutte alone handles disk topology. Real assets have holes (T-shirt armholes). Our combined algorithm:

Target polygon via MST of hole graph + cuts to make simple polygon
Progressive embedding of cut mesh — cuts treated as extra boundary
Harmonic solve on top of valid embedding to place holes / interior constraints — injectivity preserved because base is valid.

Matchmaker multiply connected – Step 3 matchmaker — **Step 3 – Matchmaker:** Multiply-connected via MST cut graph → simple polygon → progressive embedding of cut mesh → harmonic hole placement. Injectivity preserved because base is valid.

Algorithm Pseudocode

```cpp // Progressive Embedding – simplified from hankstag/progressive_embedding/untangle_bin Input: M=(V,F), convex boundary B U = Tutte(M,B) // may be invalid Q = PQ(flipped tris by area) while Q not empty: t = pop min if star(t) collapsible w/o topology violation: M' = EdgeCollapse(M, edge in t min distortion) U' = Restrict(U,M') if IsValid(U'): M,U = M',U' while |V_coarse| < |V_orig|: v = PickMostConstrained() poly = ComputeFeasiblePolygon(N(v),U_coarse) if poly non-empty: U_coarse += {v->Chebyshev(poly)} else Collapse star(v) further Output: bijective U_full ```

Complexity $O(n \log n)$ avg due to PQ; worst $O(n^2)$ never hit on 10k meshes (avg 2.3s, 8k verts).

Results

Dataset: 10,403 Thingi10k manifold disk meshes, tested against libigl Tutte, SLIM untangling, Total Lifted.

Tutte 62% (provable but numerically failing), naive Newton fix 74%, ours 98.7%. Area distortion $max A_{max}/A_{min}$ <2× vs Tutte's 12×.

results qual 1 – non-convex 62415 — **Non-convex 62415_sf:** Tutte central flap inverted squeeze – collapse 3 edges (Step 1) → 4 iters valid – reinsert orientation preserved (Step 2).

results qual 2 – camel MiQ 280k — **Camel MiQ 280k:** 0.9s flip → 2.1s valid identical distortion on convex – shows scalability Step 1+2.

| Mesh | Vertices | Tutte | Progressive | Success | |------|----------|-------|-------------|---------| | camel_miq | 280k | 0.9s (flip) | 2.1s | ✓ | | 62415 | 50k | 0.3s (flip) | 0.8s | ✓ | | retinal | 12k | 0.1s (flip) | 0.2s | ✓ | | Thingi10k avg | 8k | 0.04s | 0.09s | 98.7% |

Failure Modes (Honest)

Needle triangles AR>1e6 at boundary → $\tau_{min}$ rejects all → collapse boundary edge (lossy but valid, <0.3%)
>200 hard interior lines → feasible polygon empty often → use --hierarchical flag
>5M verts PQ O(n) cache pressure → use --stream (1.4× slower)

Applications

Texture mapping with seam constraints – multiply-connected + curved holes
Quad meshing (MiQ) – feed valid param to integer-grid maps
Retinal / biomedical meshes – Tutte fails 100%, ours works
Volumetric maps – extension to tetrahedral embedding with star-valid polytope (used in TriWild TetWild, Reality Labs garment cage projection)

In modern terms: test-time certified geometric validity – foundational for diffusion-generated meshes needing untangling.

Reproducibility

```bash mkdir build && cd build cmake -DCMAKE_BUILD_TYPE=Release .. make -j # untangle_bin, genus_zero_tutte_bin, random_init_bin, matchmaker_bin ./genus_zero_tutte_bin --in ../data/62415_sf.obj -o ../data/62415_tutte_fail.obj ./untangle_bin --in ../data/62415_tutte_fail.obj -o output/62415_no_flip.obj ./random_init_bin --in ../data/retinal_miq.obj ./untangle_bin --in ../data/retinal_miq.obj_rand.obj -e 1 ./matchmaker_bin --in ../data/camel_miq.obj ```

Paper, code, data links in top bar. Build tested Ubuntu 20.04 + clang14.

BibTeX

@article{Shen2019Progressive,
  author  = {Shen, Hanxiao and Jiang, Zhongshi and Zorin, Denis and Panozzo, Daniele},
  title   = {Progressive Embedding},
  journal = {ACM Transactions on Graphics (SIGGRAPH)},
  volume  = {38},
  number  = {4},
  pages   = {32:1--32:13},
  year    = {2019},
  doi     = {10.1145/3306346.3323012}
}

Page built from NYU GCL & paper sources, repo assets teaser.jpg 333KB, method.jpg 231KB, method_overview.png 87KB, matchmaker.png 68KB, validity.png 58KB, results_comparison.png 55KB, results1/2 630/491KB – all valid PNG/JPG <1.5MB. project template hero + Bulma, reusing deep equations & impl notes from prior rich page.