Building Our Own Quad Retopology Algorithm: The Hard Parts

A quad has four corners. Building a program that writes four vertex indices is straightforward. Building a program that consistently turns a complicated 3D model into useful quads requires decisions about almost everything surrounding those indices: which points belong together, which openings must survive, how far a surface may move, and what to do when no acceptable result appears.

That is the work behind MessyPoly’s new retopologizer. Our current app integration calls a standalone C++17 solver, qem-matching/2, through a versioned adapter. The method combines constrained triangle simplification with graph matching, then checks the result before handing it to Blender for export and baking. QuadriFlow is no longer a fallback in that app route.

This article explains the challenges we encountered and the choices visible in our implementation as of October 1, 2026. “From scratch” means we wrote our own implementation and construction pipeline; the mathematical foundations come from established research. Owning the code also means owning its limitations, its failure reports, and the evidence required before calling an output successful.

First decide what a successful mesh means#

A useful specification has to say more than “all faces are quads.” Imagine a scanned mug with an open rim, a handle, a thin wall, and a separate decorative badge. A result might contain beautiful four-sided faces while filling the rim, closing the handle, merging the badge into the body, or allowing the inner wall to pass through the outer wall.

Those failures involve different properties. Topology describes connectivity: components, holes, and boundaries. Embedding describes how that connected surface sits in 3D, including whether it crosses itself. Fidelity describes how closely the replacement follows the source. Quad quality adds questions about corners, folds, and degeneracy. A convincing wireframe cannot establish all four.

We therefore build and evaluate against several conditions together:

• Preserve the supported surface structure, including components and openings.
• Produce admissible quads that remain within geometric tolerances.
• Complete construction and validation within resource limits.
• Validate the serialized candidate and complete the app’s finalization stages.

A promising intermediate mesh is evidence of progress; a successful job requires the later checks too.

The input is already a geometry problem#

Before selecting an algorithm, you need a trustworthy representation of the input. Two vertices at the same coordinate may be deliberately separate because of a texture seam or material split. Two surfaces almost touching may belong to different parts. Welding everything within a convenient distance can change the object before retopology begins.

Our solver works with indexed triangular surfaces. Connectivity comes from shared vertex identities, rather than a guess that nearby coordinates should be connected. Input admission checks orientation, degenerate and duplicate faces, non-manifold structure, and forbidden contacts. Limited normalization can repair some representation problems when the operation is demonstrably safe. Unresolved cases can be refused.

The second method version supports valid oriented, embedded surfaces with open boundaries, multiple components, and arbitrary orientable genus. In everyday terms, that includes surfaces with rims, separate pieces, and handles. This broadens what the solver can represent. It does not establish that every such input can be reduced to every requested density.

The app also prepares inputs above 200,000 triangles down to that limit and checks the prepared result. It retains the original upload as the reference for quality scoring and texture baking. Keeping those identities distinct matters: agreement with a simplified working mesh alone would hide errors introduced during preparation.

Choosing a construction method chooses your difficulties#

There are several ways to approach quadrangulation. Field methods establish preferred directions over the surface and use them to organize a layout. Instant Field-Aligned Meshes optimizes edge orientations and vertex positions. QuadriFlow builds on that line of work and uses global and local constraints to reduce singularities, the irregular vertices where a regular quad grid changes direction.

We selected a different construction for our implementation: simplify the source triangulation while enforcing constraints, then pair adjacent triangles into quads. This gives us a direct relationship between the source surface, the coarsened surface, and the resulting faces. Shared indexed boundaries make the pieces meet without a later approximate welding step.

That choice carries a specific tradeoff. Pairing can produce a complete quad surface without constructing a global direction field, but the resulting edge flow depends on the surviving triangulation and the pairs selected. Our method does not optimize a field’s singularity count or guarantee loops suitable for character animation. Authored UV, material, region, and rigging constraints are also outside its current contract, and explicit sharp-feature preservation is unsupported.

Those limits belong in the description of the algorithm. Otherwise a geometric remesher can accidentally be presented as an automatic substitute for every decision an artist makes.

A small error metric needs a large safety system#

Our simplification stage uses a quadric error metric, or QEM. Garland and Heckbert’s original research introduced an efficient way to approximate surface error during simplification by accumulating distances to planes. The compact representation makes it practical to compare many possible contractions.

In our implementation, each triangle contributes its plane, weighted by area, to its vertices. When an edge is considered for contraction, the solver combines the endpoint quadrics and evaluates candidate replacement positions. It uses a fixed ordering to resolve ties and projects the selected proposal toward the immutable source.

The score answers a limited question: how expensive does this movement look under the accumulated plane model? It does not, by itself, establish that the movement preserves a handle, avoids an opposite wall, or leaves valid neighboring faces. Every proposed contraction therefore also faces topology, area, orientation, distance, and contact checks.

A rejected contraction must leave the previous mesh intact. That sounds like ordinary software hygiene until one operation touches positions, triangles, adjacency, quadrics, and spatial search structures. Updating only some of those structures can make the next decision depend on a surface that never actually existed. Committing a valid change as one coherent operation is part of the geometry algorithm.

Local edits can destroy global structure#

An edge contraction looks local: two endpoints become one and nearby triangles change. Its consequences can reach the whole object. Contract the wrong connection around the mug’s handle and the surface can lose a hole. Make a careless change near a rim and a boundary can pinch or split.

The solver constrains those edits and preserves each component’s Euler characteristic and boundary-loop signature through construction. Euler characteristic is the count of vertices minus edges plus faces. Combined with orientation, component identity, and boundary information, it helps track the kind of surface being preserved. It is used alongside local validity checks, rather than as a sufficient test on its own.

Separate components create another challenge. One piece may reach a useful density while another needs substantially more faces. Forcing every component to succeed at the same coarsening checkpoint can discard useful work. The implementation can retain validated component layouts and assemble them when all components are covered, followed by global checks.

It cannot quietly omit the awkward piece. A missing badge, tooth, or shard changes the delivered surface. Partial coverage remains a failure even if the surviving majority looks good in a thumbnail.

Turning triangle pairs into a complete layout#

After coarsening, we construct a dual graph. Each triangle becomes a graph node. Two nodes are connected when their triangles share an edge and removing that edge would produce an admissible quad. The task is to choose pairs so that every triangle belongs to exactly one pair.

A greedy strategy can choose an attractive pair now and leave another triangle stranded later. Maximum-cardinality matching searches for the greatest number of disjoint pairs; a perfect matching covers every node. The Boost Graph documentation explains that distinction and the alternating-path approach underlying Edmonds’ algorithm. Our solver uses its own deterministic implementation of that matching approach.

Geometry decides which graph edges exist. A candidate quad needs four distinct corners, acceptable corner orientation, sufficient area, and acceptable normal agreement. Rejecting a folded or reflex pair removes a possible connection from the graph. Enough removals can make a complete matching impossible even though the triangles form a valid surface.

This is where geometry and combinatorics become inseparable. A low-error contraction can leave a triangulation that cannot be fully paired. A locally attractive quad can belong to a globally poor choice. Our neighbor ordering favors corner quality, but maximum-cardinality matching does not promise the globally best-looking layout. It solves the coverage problem defined by the admissible pairs.

Some failures need new connectivity#

When matching stalls, repeating the same search cannot create an edge absent from its graph. The implementation therefore includes bounded recovery paths that can reconsider terminal patches with reference to the source surface.

One path retriangulates a small disk patch while keeping its boundary fixed. Flipping an interior diagonal changes which triangles are neighbors and can expose a pairing the previous triangulation did not offer. Other local recovery work can consider interior placements, subject to the same acceptance conditions. The patch still has to fit back into the surrounding mesh and pass the geometric checks.

Boundary parity imposes real constraints. For a disk tiled entirely by quads, counting face edges gives an even total number of boundary edges: interior edges contribute twice and quad faces contribute four each. A fixed odd boundary cannot be filled by that construction without changing the boundary. Even parity is only a necessary condition; shape and allowed connectivity can still prevent completion.

Our research fixtures have also exposed a practical distinction between an unpairable topological graph and a graph that becomes unpairable only after poor geometric pairs are removed. Those cases need different repair ideas. A search that reaches its budget provides a third kind of outcome: it did not find a solution within its allowance. Reporting that as proof that no solution exists would overstate what happened.

Thin surfaces make distance misleading#

Consider the space between the mug’s handle and body. A proposed point might be extremely close to the source while sitting on the wrong side of that space. A nearest-surface query can return a perfectly correct distance and still suggest the wrong correspondence for the intended part.

Contact checks address another aspect of this problem. The solver must distinguish a legitimate shared indexed edge from two triangles overlapping beyond that edge. Skipping all adjacent triangles would miss folded neighbors. Checking only unrelated components would miss a surface crossing itself within one component.

Our implementation uses spatial acceleration structures and floating-point geometric predicates to search for forbidden contacts. It checks proposed endpoint embeddings and validates accepted candidates. These are substantial safeguards with precise limits: floating-point predicates are not exact arithmetic, endpoint checks do not establish collision-free motion between states, and finite surface samples are not a continuous error certificate.

Severe folds, tiny gaps, narrow appendages, high curvature, and aggressive reduction can still force a refusal. Increasing a tolerance may admit more candidates, but it changes the meaning of acceptance. We treat that as a policy change requiring evidence, rather than a harmless way to turn a red result green.

The requested count is a preference with consequences#

“Give me 10,000 quads” sounds like a complete request. The source may require more faces to retain its boundaries, separate its nearby sheets, or pass its geometric checks. Exact count and acceptable geometry are separate requirements, and sometimes they conflict.

Our app uses an advisory target. The solver may return a validated candidate above the requested count when its search cannot safely reach the preference. The app independently imposes a hard ceiling of 50,000 quads. That ceiling remains binding even when a larger candidate would be geometrically acceptable.

The distinction should survive into reports: requested count, selected count, and actual output count should be identifiable. A result with 12,000 quads against a 10,000-quad request may be useful, but it has not achieved that exact reduction. Likewise, increasing a hard output limit changes resource and delivery assumptions; it cannot be hidden inside a quality improvement.

Topology constraints also explain why more time is not always the answer. A search may discover a better route, or it may repeatedly encounter a feature that genuinely requires more resolution under the current rules. Diagnostics must help separate those situations.

Performance includes the work you did not expect#

The obvious expensive steps are simplification, matching, and projection. Real runs also pay for contact scans, adjacency updates, rejected proposals, component recovery, and validation. An optional recovery search repeated across hundreds of components can consume the budget before the main construction makes meaningful progress.

Our solver therefore shares a request-wide work budget across its stages and gives some local searches tighter slices. The app also limits a native attempt to 8 minutes and applies output limits. An exhausted contact scan cannot report “no collision found” as though it completed; an unfinished candidate cannot be published merely because it exists in memory.

Budget allocation affects success too. Generating many promising patch proposals is wasted work if no allowance remains to validate them. Development has included reserving validation capacity and preventing optional searches from starving the rest of the solve. That is an algorithmic scheduling problem as much as a speed problem.

Reproducibility makes these changes reviewable. Stable ordering and tie-breaking help reproduce a result for the same ordered input, settings, and build. We retain solver identity, requests, logs, hashes, and results so a regression can be replayed. Different compilers, floating-point behavior, or source indexing can still change outcomes; determinism needs a stated scope.

Export and baking get their own vote#

The native solver produces a candidate quad mesh. Blender then handles downstream export, UV generation, and texture baking. Keeping that boundary explicit helps identify whether a failure originated in construction, conversion, or finalization.

Export deserves particular care because the delivery representation can differ from the authoring representation. The glTF specification defines triangle primitive modes rather than a quad primitive mode. A quad’s triangulation therefore matters, especially when its four corners are not coplanar. A diagonal chosen later can change the actual surface being tested and baked.

We check serialized geometry and the finalization result instead of assuming that a valid native mesh guarantees a valid deliverable. The original source remains available for fidelity measurements and bake reference. Geometry scores also have limits: a good surface-distance result does not establish that the texture looks correct.

This is why the app fails the job when required stages fail. It does not silently retry QuadriFlow. Keeping the failure attached to the attempted method preserves meaningful evidence for the next solver revision.

What one comparative run actually established#

On September 30, 2026, we completed a research comparison using a frozen set of ten held-out GLBs, each with 199,944–200,000 triangles, at 5 levels of requested density. Under that run’s acceptance criteria, qem-matching/2 produced 34 accepted outputs out of 50 attempts. The then-current QuadriFlow route produced 0 accepted outputs out of 50.

That was useful evidence for selecting the new route. It was also a bounded result. QuadriFlow’s attempts failed within that pipeline, so their shorter runtimes measured time to failure rather than the speed of producing accepted output. The comparison did not establish that our quads universally had better flow, fewer singularities, or better appearance.

Every accepted qem output exceeded its requested target. At the 50,000 target, accepted results reached as high as 59,926 quads. The research run preceded the app’s independent 50,000-quad ceiling, so its acceptance rate cannot be carried over as certification of the current capped app policy.

The remaining qem attempts also matter: the report recorded eleven output refusals and five other failures, including timeouts and a bake-coverage failure. Its geometry profile used 8,192 samples with a fixed seed. The experiment measured a complete route through its stated gates. It did not prove texture appearance quality or performance on every smaller source mesh. These figures come from our repository’s dated research report; the external sources below explain the underlying methods.

Building the next version responsibly#

The most useful failures tell us which question to work on next. Did a component become unpairable? Did a thin region violate contact checks? Did a bounded search miss a valid local arrangement? Did construction succeed and export alter the result? Each answer suggests a different change.

We keep algorithm tuning in the native solver and research harness, then promote a supported revision into the app through a separate, reviewable integration change. That lets improvements carry their own evidence and keeps product limits explicit.

The work ahead includes better candidate construction, broader coverage, and more useful layouts within the supported contract. For anyone building a remesher, our strongest lesson is to define success early enough that the algorithm can refuse honestly. A complete, validated surface and a reproducible explanation of failure are both valuable results. They give the next iteration something concrete to improve.

Sources and further reading#

• Michael Garland and Paul Heckbert: Surface Simplification Using Quadric Error Metrics — original QEM research, paper downloads, and further analysis.
• Boost Graph Library: Maximum Cardinality Matching — matching definitions, Edmonds’ approach, and verification. Cited for the method; our solver has its own implementation.
• Jingwei Huang and colleagues: QuadriFlow — the research project and paper describing its quadrangulation and singularity-reduction approach.
• Wenzel Jakob and colleagues: Instant Field-Aligned Meshes — the authors’ project page, paper, and reference implementation for orientation and position field optimization.
• Khronos Group: glTF 2.0 Specification — mesh primitives and attributes relevant to the final exported surface.