QuadriFlow: A Scalable and Robust Method for Quadrangulation

Huang, Zhou, Niessner, Shewchuk, Guibas — Computer Graphics Forum 37(5) (SGP 2018)
Explained assuming: you're comfortable with meshes and vector fields on surfaces. No deep learning — the new machinery here is combinatorial optimization (minimum-cost flow, Boolean satisfiability), explained from scratch, along with the orientation/position-field setup it builds on.

Where this picks up

This paper builds directly on Jakob et al.'s "Instant Field-Aligned Meshes" (SIGGRAPH Asia 2015), inheriting its two-field setup unchanged: an orientation field (a smooth 4-RoSy cross field, aligned to curvature/sharp features) and a position field (a tangent-plane lattice fit to that orientation, whose agreement between neighbors determines where quad-mesh vertices land). That earlier method's weakness: because both fields are optimized by purely local smoothing, it can't see that two singularities on opposite sides of a model could cancel each other out — an inherently non-local observation — so it leaves behind more irregular vertices than necessary.

QuadriFlow's whole contribution is closing that gap for the position field only — it explicitly does not touch the orientation field, which the paper notes already tends to have far fewer singularities than the position field does. Removing position-field singularities completely, in general, is a mixed-integer program — provably NP-hard, and the reason fully-global prior methods (mixed-integer quadrangulation solvers) don't scale to large meshes. QuadriFlow's trick is finding a much cheaper subproblem that captures almost all of the benefit.

Why position-field singularities are a discrete bookkeeping problem

Think of the position field as, per mesh edge, an integer offset: how many grid steps apart the two endpoints' local lattices are, in each of two lattice directions. Walk around any single triangle and sum up these integer offsets (each properly rotated into a common frame first) — if the total isn't zero, that triangle encloses a singularity. A perfectly regular quad-mesh vertex is one where every triangle around it sums to zero; an irregular vertex is where it doesn't.

Walk the loop around a vertex, add up the (properly rotated) integer offset on each edge you cross. Sum to zero: regular vertex. Sum to anything else: a singularity, with that leftover value as its index.

So "remove a singularity" is exactly "change some integer offsets, as few and as small as possible, until every triangle sums to zero wherever that's achievable." That's an integer program by construction — the paper's real technical contribution is showing a useful class of these problems can be reduced to something solvable in polynomial time.

Minimum-cost flow: the same combinatorial structure, solvable exactly and fast

A minimum-cost (network) flow problem asks: push flow from a source to a sink through a graph of capacity- and cost-limited edges, at minimum total cost, subject to flow being conserved at every intermediate node (whatever flows in must flow out). Unlike general integer programming, this restricted structure has efficient exact solvers (network simplex, or fast max-flow-style approximations for very large graphs).

The paper shows the singularity-removal integer program has exactly this shape: build one flow-network node per triangle-sum constraint, one flow-network edge per integer-offset variable, with edge capacity and cost derived directly from how much that offset is allowed to change. Solving minimum-cost flow on this network is mathematically equivalent to solving the original integer program — but now in polynomial time, globally optimal, no NP-hardness. This is the paper's key insight; the rest is engineering to make it fast at scale (a multi-resolution hierarchy that solves most singularities on a coarsened, order-of-magnitude-smaller network first, then propagates the fix to the full-resolution mesh).

Boolean satisfiability: mopping up the cases the flow solve can't reach

Fixing integer offsets can occasionally flip a triangle inside-out (a face whose orientation becomes inconsistent with its neighbors — an inverted face in the output). Preventing this is a second set of constraints the minimum-cost flow formulation doesn't directly capture. The paper handles most cases with a simple greedy edge-contraction heuristic, then falls back, only for the stubborn remainder, to modeling the local constraints as a small Boolean satisfiability (SAT) problem — a "can these true/false variables be assigned to satisfy all these logical clauses at once" puzzle, solved with an off-the-shelf SAT solver. SAT is famously NP-complete in general, but these subproblems are small and localized (near where an inversion actually occurs), so practical SAT solvers handle them without trouble.

Sharp-feature preservation, applied after singularities are already fixed

Separately from all of the above, when the continuous vertex positions are re-fit to match the newly regularized integer offsets, any vertex sitting on a user-flagged sharp edge (detected via a dihedral angle threshold between two triangles' normals) is constrained to slide only along that crease, not drift across it in the tangent plane. Notice the ordering: this happens strictly after the combinatorial singularity removal, as a constraint on how the resulting structure gets fit back to 3D positions — sharp-feature handling and singularity placement are not jointly optimized here, they're sequential, separable concerns.

Results