PaperlayerView exact revision on arXiv

Source-linked AI summary

Playing to Par: Reinforcement Learning for Provably Optimal Quadrilateral Block Decompositions

Arjun Narayanan, Per-Olof Persson

arXiv:2609.32146v1cs.LG

TL;DR

Block decompositions need regular connectivity, but common construction approaches often do not target optimality, despite a domain-specific lower bound on irregularity. The paper trains a half-edge reinforcement-learning agent using backward-walked optimal demonstrations to overcome sparse rewards. It reaches the bound on many test domains and remains nearly regular at twice the training scale.

  • Problem

    Block decompositions are still built largely by hand or heuristics that often do not target optimality, although topology and corner angles impose a lower bound on irregularity.

    Source: §1 · p. 1

  • Method

    The agent builds meshes from the bare boundary with local half-edge edits, using backward-walked demonstrations of constructed optima before reinforcement learning.

    Source: §1 · p. 2

  • Results

    The agent produces complete, usable, provably optimal decompositions across evaluated settings and remains nearly regular on larger and curved domains unseen in training.

    Source: §8 · p. 9

  • Takeaways & Limitations

    The resulting decompositions are as regular as the domain permits, while production meshers at the same coarseness essentially never reach the bound.

    Source: §8 · p. 9

    The solved test relies on an untangling smoother, and clearing the quality bar along curved arcs can require a test-time repair search of up to ten minutes per domain.

    Source: §7.1 · p. 9

Abstract

from arXiv · show

A quadrilateral block decomposition of a planar domain is judged by whether it is complete, whether its elements are well shaped, and how many of its vertices are irregular. The last has a provable floor: the discrete Gauss-Bonnet identity enforces a lower bound on the total vertex irregularity of any all-quadrilateral mesh of a given domain purely based on its topology and corner angles. We train a reinforcement learning agent to build decompositions that reach this bound, which we call par. It acts directly on the mesh's half-edge data structure through local edits, with a policy network whose convolutions follow the mesh's own connectivity, so it applies unchanged to domains larger than any seen in training. The reward targets the floor directly, and it is sparse: random play reaches it on no domain with more than eight sides. We overcome this exploration barrier via behaviour cloning on optimal meshes that are trivial to construct, walked backward into demonstrations, before training it with PPO. On 96 held-out domains the agent produces an all-quadrilateral mesh on every one, a usable one on 95.7 on average, and a provably optimal one on 90; Gmsh's strongest configuration at the same element count completes 51, is usable on 38 and optimal on none, and even at three to fourteen times the elements never produces a more regular mesh. On 64 domains twice the training size the agent completes all, is usable on 62, and keeps a median excess over par below one against Gmsh's 39 at the same element count.

1 INTRODUCTION

Block decompositions seek regular connectivity, but hand-built and heuristic methods often do not target optimality. The paper uses a topology-aware reinforcement-learning agent to reach a domain-specific irregularity bound, overcoming sparse rewards through demonstrations and evaluating against Gmsh.

1 INTRODUCTION

  • Block decompositions provide coarse all-quadrilateral partitions with regular connectivity, but are still built largely by hand or heuristics that often do not target optimality.Wrong-valence vertices are singularities that survive refinement, while thin elements can be smoothed or split.Source: §1 · p. 1
  • The discrete Gauss–Bonnet identity gives a lower bound on irregularity from corner angles and topology; reaching it certifies optimal connectivity.The paper calls this bound par and computes it before a mesh exists.Source: §1 · p. 1
  • Behaviour cloning on known optimal trajectories overcomes sparse exploration before reinforcement learning; random play reaches par on no domain with more than eight sides.The policy convolves over half-edge connectivity, and its input representation is designed to scale beyond training mesh sizes.Source: §1 · pp. 1–2
  • In Figure 1’s three domains, the agent’s top mesh has no irregular vertices; its 38-corner example has 1 versus Gmsh’s 32 and 16, and curved example 15 versus 64 and 35.The domains are one per family; Gmsh BLOSSOM is asked for the agent’s element count, while QUASI-STRUCTURED runs at its natural size.Source: Figure 1 · p. 2
  • The contributions include a half-edge action space and policy, the GEO2D benchmark suite, and a training recipe using shaped rewards and backward-walked optimal demonstrations.The demonstrations overcome the exploration barrier that otherwise blocks PPO.Source: §1 · p. 2

2 QUADRILATERAL BLOCK DECOMPOSITION AND ITS OPTIMALITY BOUND

The paper defines conforming all-quadrilateral meshes and measures vertex irregularity against desired degrees. A discrete Gauss–Bonnet identity yields the par floor, a domain-specific lower bound that certifies optimal connectivity when attained.

2 QUADRILATERAL BLOCK DECOMPOSITION AND ITS OPTIMALITY BOUND

  • A domain is a bounded planar polygonal region with one outer boundary and optionally holes; its conforming block decomposition covers it with quadrilateral faces.The Euler characteristic is χ = |V| − |E| + |F| = 1 − H, fixed by the domain.Source: §2 · p. 3
  • Vertex irregularity measures the difference between actual and desired degree; fully structured meshes have zero irregularity, which some domains cannot attain.Desired degrees depend on whether a vertex is interior or on the boundary, and boundary vertices retain at least their two boundary edges.Source: §2 · p. 3
  • The discrete Gauss–Bonnet identity fixes a signed total of desired-minus-actual degrees at 4χ, regardless of a mesh’s vertex, edge, and face counts.Separating corner-dependent terms gives the bound par(Ω) = c(Ω) + 4χ; both corner angles and topology are known before meshing.Source: §2 · p. 3
  • A mesh reaching par is provably optimal in connectivity, although the bound does not guarantee such a decomposition exists.When corner-angle rounding is tied, par is minimized over the equally admissible corner treatments.Source: §2 · p. 3

3 THE DECOMPOSITION MDP

The decomposition MDP starts from a single face and builds a mesh through local half-edge edits. Its observation combines a fixed local window with global mesh statistics, while reward and termination jointly target par, element quality, and a valid embedding.

3.1 STATES AND OBSERVATIONS

  • The state is the current mesh, a centred half-edge, and move count; a fixed-size pointer-traversal window supplies local features alongside global scalars.Global quantities include distance from par, face defect, odd-sided-face count, worst quality, relative mesh size, and face count.Source: §3.1 · pp. 3–4

3.2 ACTIONS

  • Four local actions insert one of three chords or split the selected edge, while masks exclude invalid edits such as chords that leave a 2-gon.The observation window distinguishes a missing boundary twin from a neighbour outside the window.Source: §3.2 · p. 4, Figure 2 · p. 4

3.3 REWARD AND TERMINATION

  • Reward combines potential progress, a per-move charge, and a solve bonus; normalizing by initial defect keeps returns on one scale across domain sizes.A solved state requires all-quadrilateral faces, irregularity equal to par, and a nondegenerate embedding after smoothing; evaluation usability uses a distinct quality threshold.Source: §3.3 · p. 5

4 A POLICY ON THE HALF-EDGE STRUCTURE

The policy’s message passing follows half-edge connectivity rather than positions in a fixed mesh layout. A pooled mesh context conditions action types and supplies a whole-mesh value estimate.

4.1 CONVOLUTION OVER NEXT, P R E V I O U S AND T W I N

  • Each convolution block combines a half-edge’s features with those of its next, previous, and twin neighbours, using distinct learned vectors for window edges and domain boundaries.No parameter depends on template position or mesh size, so a checkpoint applies unchanged to larger windows and meshes.Source: §4.1 · p. 5

4.2 FROM HALF-EDGES TO A MASKED ACTION DISTRIBUTION

  • Mean- and max-pooled half-edge latents combine with global state features to form context, which shifts action-type logits equally across slots rather than choosing a half-edge.The critic reads the context to estimate value for the whole mesh, independent of the observation window’s centre.Source: §4.2 · p. 5
  • The shared convolutional policy and masked categorical distribution produce four action logits per template slot, with invalid actions excluded.The network has 96 channels, four residual stages, and about 3.7 × 10^5 parameters.Source: §4.2 · p. 5

5 TRAINING UNDER SPARSE REWARD

Because random exploration rarely reaches par, the authors construct certified optimal trajectories and clone them before continuing with PPO. The recipe combines reversible demonstrations from meshes optimal by construction with reinforcement learning on generated and certified domains.

5 TRAINING UNDER SPARSE REWARD

  • PPO from a random initialisation reaches par on only 7 of 96 domains after a million steps, motivating behaviour cloning on optimal-by-construction mesh families.Uniform random play reaches par on none of the polygons with more than eight sides.Source: §5 · p. 6

5.1 CERTIFIED INSTANCES WITHOUT SEARCH

  • A backward walk starts from a polyomino’s at-par quadrilateral mesh and reverses legal moves until one face remains, yielding a certified solution in the agent’s action space.The seed families also include annuli, polar meshes about a hub, and pinwheel annuli; deformed polyominoes retain valid solutions when corners stay within their angle bins.Source: §5.1 · p. 6

5.2 CLONING, THEN REINFORCEMENT

  • Cloning 9,000 certified instances (about 187,000 pairs) for six epochs achieves 93.7% top-one agreement with the certified move sets.Independent moves can commute, so the demonstrations record sets of equally optimal moves and train against a uniform distribution over each set.Source: §5.2 · p. 6
  • PPO continues from cloned weights after 40 frozen-policy value-head epochs, training for four million steps on generated and certified domains.Thirty-five percent of episodes start from a freshly generated certified instance; the full recipe takes about four hours on an Apple M2 laptop.Source: §5.2 · p. 6

6 EXPERIMENTS

The experiments evaluate the agent on unseen polygonal domains, comparing completion, usability, excess over par, and certified optimality with Gmsh. The agent’s results extend to larger boundaries and curved domains, with evaluation-time procedures and quality measurement affecting some outcomes.

6.1 SETUP

  • The 64 larger-boundary domains have 25–50 corners, twice anything seen in training; every outline has par zero, while 73% of intermediate subproblems have non-zero bounds.The evaluation outlines are unseen and straight-sided, and are drawn from four families with or without holes.Source: §6.1 · p. 6

6.2 MAIN RESULT

  • On 96 in-distribution domains, the agent completes all, is usable on 95.7, and reaches the certified optimum on 90.2; matched-count Gmsh completes about half and reaches the optimum three times in 672 attempts.Gmsh configurations completing all domains use three to fourteen times the elements, with median excesses of 7.5 and 26; the agent wins on regularity on every decided domain against all four configurations.Source: §6.2 · p. 7, Table 1 · p. 8

6.3 LARGER BOUNDARIES

  • On 64 larger domains, the agent completes every domain, is usable on 62.0, and has median excess over par below one, versus Gmsh’s 39 at matched count.The agent reaches the certified optimum on 31.0 domains, where no Gmsh configuration does.Source: §6.3 · p. 7, Table 1 · p. 8
  • Doubling the move budget completes all 64 larger domains and lifts usability from 41.0 to 54.5; repair raises it to 62.0, while 17 attempts raise it to 63.5.Tripling the budget buys nothing further; doubling uses about a quarter more elements.Source: §6.3 · p. 7, Table 1 · p. 8

6.4 CURVED BOUNDARIES

  • On 96 curved domains, the unchanged agent reaches par on 37 and has median excess over par of 2; Gmsh’s excesses are 10 to 32, and it reaches par on at most 2.The agent is usable on 95 domains when quality is judged against arc tangents and 88 against chords; the table distinguishes quality-independent columns from tangent- or chord-based quality results.Source: §6.4 · p. 8, Table 2 · p. 8
  • The regularity result holds: the agent’s median excess is 8 against Gmsh’s 28 to 101, while it clears the quality bar on fewer domains than Gmsh configurations using several times its elements.Source: §6.4 · p. 9

7 LIMITATIONS AND RELATED WORK

The paper identifies reliance on a smoother and test-time search for curved-boundary quality as limitations. It distinguishes its connectivity-editing, certificate-driven approach from learned meshing methods and classical meshers that optimise other criteria.

7.1 LIMITATIONS •

  • The evaluation untangles meshes before judging them, the agent takes longer than Gmsh, and curved-boundary quality repair can take up to ten minutes per domain.A policy that draws well-shaped elements along arcs without repair remains open.Source: §7.1 · p. 9

7.2 RELATED WORK

  • Unlike learned methods that place elements or steer an advancing front, this agent edits a general polygonal half-edge mesh and ends episodes at an optimality certificate; Narayanan et al. (2024) instead edits an existing all-quadrilateral mesh toward ideal degrees.Other learned mesh work optimises geometry or error rather than connectivity (Lorsung & Barati Farimani, 2023; Yang et al., 2023; Foucart et al., 2023; Thacher et al., 2025).Source: §7.2 · p. 9
  • Classical meshers use local quality heuristics or field alignment, whereas this work uses the bound of Peng & Wonka (2013) and Peng et al. (2014) as an MDP termination criterion.Source: §7.2 · p. 9

8 CONCLUSION

The conclusion frames quadrilateral decomposition as a sparse-reward problem whose successful solutions carry an optimality certificate. It also details the par convention, the centring rule, and how certified meshes become training instances.

8 CONCLUSION

  • Cloning on constructible optima gets exploration past the sparse-reward barrier, and PPO improves on cloning; the resulting meshes are complete, usable, and as regular as the domain permits.At the same coarseness, production meshers essentially never reach the bound; performance remains nearly regular at twice the training scale and on curved boundaries unseen in training.Source: §8 · p. 9

A THE PAR CONVENTION IN FULL

  • At tie corners, par minimizes |c + 4χ| over assignments of either admissible degree, preserving a bound and separable vertex irregularity.Because the two degree options differ by one, the minimum can be found by scanning how many tie corners take the higher value.Source: A THE PAR CONVENTION IN FULL · p. 13

B THE CENTRING RULE

  • The centring rule prioritizes irregular faces and their highest-defect vertices in view, consulting the whole mesh only when no irregularity remains in the window.Once every face is quadrilateral, it centres on the worst vertex anywhere.Source: B THE CENTRING RULE · p. 13

C CERTIFIED INSTANCES

  • Polyominoes, annuli, and polar meshes provide certified seeds: they cover rectilinear domains, holes, and hub meshes with par |4 − m|, respectively.Polyomino seeds are deformed within corner-angle bins, while annuli and polar meshes are mirrored, rotated, and scaled; candidates are replayed and checked as solved before entering the dataset.Source: C CERTIFIED INSTANCES · pp. 13–14

D PAR-ZERO DOMAINS ARE NOT THE EASY CASE

The par-zero evaluation domains still generate subproblems with positive bounds, and on held-out domains with positive par the agent reaches par more often than matched-count Gmsh configurations. The section also describes the policy and the evaluation comparisons.

D PAR-ZERO DOMAINS ARE NOT THE EASY CASE

  • Although every evaluation domain has par zero, 39% of in-distribution subproblems and 73% of larger-set subproblems have nonzero bounds; 75 of 96 and every larger-set episode encounter one.Table 3 counts bounds of subproblems in greedy attempts and episodes meeting at least one positive-bound subproblem.Source: D PAR-ZERO DOMAINS ARE NOT THE EASY CASE · p. 14, Table 3 · p. 15
  • The agent reaches par on 47 of 48 held-out domains with par 1–4; no matched-count Gmsh configuration exceeds 8, and only PACKING reaches par 3 or more, on 4 of 20.Table 4 reports domains at par by par value, using the agent’s best of five attempts and Gmsh at the agent’s element count where possible.Source: D PAR-ZERO DOMAINS ARE NOT THE EASY CASE · p. 15, Table 4 · p. 15

E THE POLICY NETWORK

  • The policy’s pooled context can reweight the four action types but cannot itself select a half-edge; location selection rests on convolution and the window rule.The global vector and progress scalar join after pooling rather than entering message passing.Source: Figure 4 · p. 15

F HYPERPARAMETERS

  • Table 5 presents the released configuration, but the supplied passage gives no hyperparameter values.Source: Table 5 · p. 16

G ALL SEVEN GMSH CONFIGURATIONS

  • Gmsh comparisons use matched element counts where possible, and Table 7 reports in-distribution results by family across completion, usability, median excess over par, and at-par rates.Figure 5 compares per-mesh minimum quality and excess over par domain by domain; its excess panels include only all-quadrilateral meshes.Source: Table 6 · p. 16, G ALL SEVEN GMSH CONFIGURATIONS · p. 16, Table 7 · p. 17

H PER-DOMAIN RESULTS AND EVALUATION NOISE

Per-domain records and scripts support regeneration of the reported tables and head-to-head rates, while evaluation-seed variation measures rollout sampling. The paper also reports a separate development-set score.

H PER-DOMAIN RESULTS AND EVALUATION NOISE

  • The released archive includes per-domain results and scripts to regenerate tables and win rates; Table 8 summarizes evaluation-seed mean, standard deviation, and range.With domains fixed, deviations across six in-distribution and four larger-set seeds measure rollout sampling alone.Source: H PER-DOMAIN RESULTS AND EVALUATION… · pp. 17–18, Table 8 · p. 18

I THE DEVELOPMENT SET

  • On the development set, the released agent solves all 15 instances greedily and 12 of 14 instances with known optima within the expert’s move count.The authors report this as a development score only; the instances were not used for Section 6 results.Source: I THE DEVELOPMENT SET · p. 18

J ABLATIONS

The ablations show that cloning is needed for PPO to learn the sparse par-targeted reward, while the half-edge convolution outperforms a lossy serialization of mesh connectivity. The section also specifies GEO2D domain generation and a common smoothing procedure for scoring.

J ABLATIONS

  • At 1M PPO steps, cloning then PPO reaches 91.8 usable and 76.2 at par of 96, versus fresh PPO’s 10 quality-passing and 7 at-par domains.Cloning alone reaches par on 22.3; a million PPO steps from it raise that to 76.2. On larger domains, nothing completed by fresh PPO is usable.Source: J ABLATIONS · p. 18, Table 9 · p. 19
  • The half-edge convolution reaches par on about twice as many domains as a same-budget Transformer whose breadth-first serialization loses adjacency information.The Transformer also lagged by the end of cloning; the authors attribute the difference to what the input identifies, not model capacity.Source: J ABLATIONS · p. 18
  • Across seeds, the larger-boundary evaluation varies by 3–5 domains on usable results and about 10 on at-par results.The authors advise reading larger-boundary numbers as ranges because out-of-distribution seed spread is about five domains, above the evaluation-seed spread.Source: J ABLATIONS · p. 18

K GENERATING DOMAINS, AND DRAWING THE MESH

  • GEO2D generates seeded lattice-based mechanical-part outlines with chamfers, fillets, notches, and optional holes, making preset-and-seed ranges define reproducible domain sets.A domain of ratio R fits in an R × R box and admits a uniform mesh of unit size; the larger-boundary set caps longest-to-shortest boundary-edge ratio at ten.Source: K GENERATING DOMAINS, AND DRAWING THE… · p. 19
  • The same untangling smoother and settings are applied to every method before scoring, while cheap Laplacian sweeps run between edits.The reported-quality smoother optimizes a condition-number objective over adjacent corners and permits inserted boundary nodes to slide along the boundary only when the worst adjacent corner does not worsen.Source: K GENERATING DOMAINS, AND DRAWING THE… · p. 19

L CURVED BOUNDARIES

The paper extends its par bound and straight-trained agent to curved domains, using tangent-aware quality checks and a repair search. On larger curved domains, regularity remains strong while quality-bar clearance becomes less frequent.

L CURVED BOUNDARIES

  • A smooth arc contributes to par like a straight edge: a square has par 0, while a disc has par 4 despite both being topological discs.The bound’s proof does not depend on straightness; vertices inside an arc have angle π by tangent continuity.Source: L CURVED BOUNDARIES · p. 19
  • The repair search iterates edits on the worst element of candidate meshes, then selects the lowest-excess mesh that clears the quality bar, breaking ties toward fewer elements.It runs for up to 600 seconds and judges arc corners against their tangents; Gmsh often fails the quality bar under that tangent-based measure.Source: L CURVED BOUNDARIES · pp. 19–20
  • 100% regularity win rate against every configuration in every curved suite; on larger domains, median excess over par is 8 and 13 against 25 to 117, while quality-bar clearance falls.The curved-suite table omits the regularity win-rate column because the agent wins every configuration.Source: Table 10 · p. 20, L CURVED BOUNDARIES · p. 20

M GALLERY

  • Figures 6 and 7 show representative domains from the in-distribution and larger-boundary families; Figure 8 shows curved-suite examples meshed by the released agent with repair search.Figure 8 compares the agent’s tangent-aware quality with Gmsh, and depicts arc edges along the arcs with a boundary node every 45°.Source: M GALLERY · pp. 20, 22, Figure 6 · p. 21, Figure 7 · p. 22
Loading 2609.32146v1…