Pattern-Based Quadrangulation for N-Sided Patches

Takayama, Panozzo, Sorkine-Hornung — Computer Graphics Forum 33(5) (SGP 2014)
Explained assuming: you know quad meshes, valence/irregular vertices, and mesh boundaries at a working level. No deep learning, no global field or PDE at all here — this is a combinatorial, pattern-matching approach, explained from scratch below.

One-sentence version: Given nothing but an isolated disk-shaped region's boundary — how many quad-edges cross each of its N sides (2 ≤ N ≤ 6) — fill its interior with a valid all-quad mesh, guaranteed to succeed for literally any valid input, using a small proven-complete library of combinatorial templates instead of a field or energy to optimize.

A fundamentally different kind of problem than field-based quadrangulation

Field-based quad remeshing methods (smoothing a cross field, then a position field, over an entire surface) solve one global problem over the whole surface at once: a single consistent field has to be found everywhere simultaneously, which is exactly why they all need the input to be a coherent, well-defined 2-manifold overall.

This paper asks a completely different, much more local question: given just a single disk-shaped region — topologically trivial, no genus, no holes — bounded by N sides (N between 2 and 6), with a prescribed number of edge subdivisions specified on each side, is there a valid all-quad tessellation of the interior, and if so, what is it? Nothing about the rest of the model matters at all; the patch is solved in total isolation, given only its own boundary as input.

Why isolation is the whole point. Because each patch is solved independently given only its own boundary, this composes into a "fill the gap" or "stitch two regions together" workflow: wherever a hole or seam needs bridging in an existing quad mesh, that hole/seam is exactly an N-sided patch with prescribed boundary subdivisions (inherited from whatever quad edges already terminate there) — hand it to this algorithm and the result connects seamlessly, without needing to re-solve or even be aware of any global field over the rest of the model.

Why this is harder than it sounds

The boundary subdivision counts aren't free to choose arbitrarily and still be quad-fillable — there's a parity-style feasibility condition any valid input must satisfy (loosely: the counts around the patch have to be compatible enough that an integer number of quads can tile the interior at all). Beyond that, some feasible inputs are highly asymmetric: one side subdivided many times, an adjacent side barely subdivided at all — exactly the kind of input where a naive tessellation strategy either fails outright or is forced into a large number of irregular (non-valence-4) interior vertices. Prior algorithms for this exact sub-problem existed but, per the paper, "none of them provide guarantee to succeed for arbitrary cases" — this asymmetric-input regime being precisely where they broke down.

The fix: a small, proven-sufficient library of topological patterns

Rather than search a continuous solution space, the paper shows the (much larger, seemingly intractable) space of all possible N-sided boundary inputs can first be reduced, via a canonical simplification, to a much smaller set of essential cases — and that a small fixed library of discrete combinatorial templates ("topological patterns") is provably sufficient to cover every one of them. Determining whether a given pattern satisfies a given input reduces to a small integer linear program, cheap enough to solve per-patch. By default the algorithm picks the pattern minimizing the number of irregular vertices in the result, but because the underlying search is explicit and enumerable rather than a single continuous optimum, a user can also ask for a different feasible solution — e.g. one that relocates an irregular vertex somewhere more visually convenient — by solving a small variant ILP, not by re-running a whole global optimization.

N-sided patch boundary edge-subdivision counts per side, no data from the rest of the model Canonical simplification + match against a small library of provably-sufficient topological patterns Small integer linear program picks minimal-irregularity pattern (or an alternative) All-quad interior, guaranteed to exist stitches seamlessly to whatever the boundary already met
Blue = the only input this method ever sees — a patch's own boundary, nothing global. Orange = the paper's combinatorial contribution — pattern matching + a small ILP, no field or energy anywhere. Green = a guaranteed, seamlessly-stitchable result.

Practical use: sketch-based retopology

The paper integrates this into an interactive tool where an artist directly sketches patch boundary curves on top of an existing mesh, subdividing the surface into a set of N-sided regions by hand (possibly containing multiple quads each), and the system immediately fills every enclosed patch the moment its boundary is complete. Because filling one patch never needs to know anything about the field, connectivity, or history of any other patch, patches can be edited, re-drawn, or re-subdivided incrementally without invalidating or needing to re-solve anything elsewhere on the model.

Source: Takayama, K., Panozzo, D., Sorkine-Hornung, O., "Pattern-Based Quadrangulation for N-Sided Patches," Computer Graphics Forum 33(5) (Symposium on Geometry Processing 2014).