Playing to Par: Reinforcement Learning for Provably Optimal Quadrilateral Block Decompositions
Arjun Narayanan, Per-Olof Persson
cs.LG
2026-09-26
Half-edge CNN + PPO builds all-quad meshes from the boundary: 96/96 complete, 95.7 usable, 90.2 at par on held-out domains; matched-count Gmsh completes 51 and hits par on none.
A quadrilateral block decomposition is a coarse all-quad partition of a planar domain, as regular in vertex valence as the domain allows. A skinny element can be smoothed or split. A vertex of the wrong degree is a singularity that survives every refinement. Structured and multi-block discretisations, tensor-product bases, and subdivision all need regular connectivity. Production meshers clean valence up after the fact; advancing fronts insert more singularities than topology requires. These decompositions are still built by hand or by heuristics, and they rarely aim at a bound.
The bound exists. The discrete Gauss-Bonnet identity fixes a lower limit on total vertex irregularity for any all-quad mesh of a given domain, from corner angles and topology alone. The paper calls it par. It is computed before any mesh exists; a decomposition that meets it is provably optimal in connectivity. That makes an unusual RL problem: the reward is sparse, and success carries a certificate. Uniform random play hits par on about 3% of five- and six-sided polygons, and on none with more than eight sides. A 2024 paper from the same group edited an existing all-quad mesh toward ideal degrees. This agent starts from the bare boundary and targets the domain's bound.
The state is a half-edge mesh (a DCEL: two opposite half-edges per edge, connectivity through next, previous, and twin). An episode starts from the domain as a single face. Four local actions: insert a chord from the current half-edge to the vertex 2, 3, or 4 steps ahead in the face loop, or split the edge with a new vertex. Invalid actions are masked. Deletions are off, so the agent cannot undo for free.
The policy convolves along the mesh's own pointers. Each half-edge reads its features and those of next, previous, and twin. About 370k parameters, none indexed by template position or mesh size, so a checkpoint runs on domains larger than any seen in training. The observation is a 64-half-edge window plus a seven-scalar global vector (including distance to par), normalised by face count.
The reward is a potential that charges face defect, irregularity above par, and the worst quality among finished quads, then divides by the initial defect so returns share one scale across domain sizes. An episode is solved when every face is a quad, irregularity equals par, and after one untangling smoother pass the minimum quality q is at least 0.1.
Cloning gets past the sparse-reward wall. Polyominoes, annuli, and polar hub meshes are optimal by construction. Walking them backward through legal inverses yields demonstrations in the agent's action space. 9,000 certified instances, about 187k pairs, six cloning epochs, 93.7% top-one agreement with the certified move sets. PPO then runs for four million steps, with 35% of episodes still starting from fresh certified instances. The value head is warmed for forty epochs on a frozen policy first. The full recipe takes about four hours on an Apple M2 laptop.
Evaluation uses GEO2D, a seeded generator of mechanical-part outlines with chamfers and holes. All test domains are unseen. Each domain gets five attempts (one greedy, four sampled) at double the training move budget, plus up to three split-and-continue repair rounds. Every method is scored after the same untangling smoother.
| method | all-quad | usable (q≥0.3) | at par | excess over par (median) | elements |
| agent (8-24 corners, 96 domains) | 96.0 | 95.7 | 90.2 | 0 | 16 |
| Gmsh blossom, matched count | 51 | 38 | 0 | 9 | 19 |
| Gmsh quasi-structured | 96 | 96 | 2 | 7.5 | 51 (3.2×) |
| Gmsh blossom-full | 96 | 96 | 0 | 26 | 220 (14×) |
| agent (25-50 corners, 64 domains) | 64.0 | 62.0 | 31.0 | 0.75 | 78 |
| Gmsh blossom, matched count | 26 | 18 | 0 | 39 | 97 |
On regularity the agent wins on every decided domain against every Gmsh configuration, at any element count. Across seven Gmsh configs, 672 attempts on the 96-domain set, the certified optimum is hit three times.
PPO from scratch for one million steps reaches par on 7.2 of 96 domains. Cloning alone reaches 22.3. Cloning then PPO reaches 76.2. Under an earlier recipe at two million steps, a Transformer with the same parameter count, given a serialised window without adjacency, hits par on about half as many domains (51.5 vs 94.5). On 96 curved 8-24-corner domains the released weights never saw, with a test-time repair search, median excess over par is 2 and 37 domains hit par; Gmsh excess is 10 to 32 and at most 2 hit par.
A certificate of optimality is a harder stopping rule than "looks structured." The agent grows the mesh from the bare boundary, so it does not need an all-quad initialisation. Size generalisation is built into the convolution, not patched on later.
The use case is narrow: 2D block decompositions that serve as coarse skeletons for structured meshes, multi-block discretisations, or subdivision. Gmsh meshes in milliseconds. This unoptimised agent takes under a second in distribution, seconds on larger domains, minutes on the largest holed ones, and up to ten minutes per domain for the curved repair search. If the goal is a coarse all-quad mesh as regular as topology allows, this is closer. If the goal is speed, density, or arbitrary CAD, production meshers still win.
The authors list three. The smoother sits in the loop; the policy is trained against that test. Runtime is one to two orders of magnitude slower than Gmsh. Curved boundaries need a test-time search to clear the quality bar.
Every evaluation domain has par zero. Non-zero bounds are tested on subproblems and on 48 hold-out certified instances (47 of 48 at par). GEO2D is lattice-based mechanical parts, not arbitrary CAD. The evaluation procedure itself moves the larger-set numbers: default budget is usable on 41.0 of 64, doubling reaches 54.5, repair reaches 62.0. Out of distribution, training-seed spread is about five domains, so the larger-boundary figures should be read as ranges. On 25-50-corner curved domains regularity still leads, but the agent clears the quality bar less often than Gmsh configs that use several times as many elements. No 3D hex experiment.