Playing to Par

90 / 96

held-out domains meshed provably optimally

median irregular vertices above par, against 7.5–26 for Gmsh

2×

the training size, still nearly optimal with no retraining

curved domains seen in training, yet at par on 37 of 96

The idea

A certificate of optimality, and an agent that earns it

A block decomposition splits a domain into quadrilaterals, and it is judged largely by how many of its vertices are irregular. For every domain there is a floor on that number, fixed before any mesh exists. We train an agent to reach it.

The bound: par

The discrete Gauss–Bonnet identity fixes a lower bound on irregularity from the domain's corner angles and topology alone. A mesh that reaches it is provably optimal in its connectivity.

I(M) ≥ par(Ω) = |c(Ω) + 4χ|

An agent on the half-edge mesh

Starting from the bare boundary, the agent inserts chords and vertices on a doubly connected edge list. Its convolutions follow next, previous and twin, so it runs unchanged on domains larger than any seen in training.

Cloning past a sparse reward

Random play almost never reaches par. Optimal meshes that are trivial to construct, walked backward into demonstrations, get PPO started; PPO on generated domains takes it from there.

In action

Watch it mesh, one move at a time

Shaded faces are not yet quadrilaterals. Dots mark the irregular vertices of the finished mesh; on the curved domain they are exactly the three its corners force.

A part with a hole optimal18 corners, 29 moves

Twice the training size optimaltwo holes, 73 moves

Curved, never seen at par 3fillets and a notch, 66 moves

Single greedy rollouts of the released agent. The tables below use the paper's full evaluation procedure.

Against Gmsh

Fewer irregular vertices, at the same element count

Our agent and Gmsh on three domains, with irregular vertices marked

On the same domains, Gmsh's meshers leave many irregular vertices (the dots) even when they are allowed several times the elements. The agent's meshes are at or near the bound.

Top: an in-distribution part with a hole, which the agent meshes optimally. Middle: a domain twice the training size. Bottom: a curved domain with holes, never seen in training.

Results

Held-out mechanical parts

Counts are domains. Excess is the median number of irregular vertices above par; at par counts domains meshed provably optimally.

96 domains, 8–24 corners

Method	all-quad	usable	excess	at par
Gmsh blossom	51	38	9	0
Gmsh frontal-quad	43	29	8	1
Gmsh quasi-structured	96	96	7.5	2
Gmsh blossom-full	96	96	26	0
Ours	96.0	95.7	0	90.2

64 domains, 25–50 corners

Method	all-quad	usable	excess	at par
Gmsh blossom	26	18	39	0
Gmsh frontal-quad	15	14	34	0
Gmsh quasi-structured	64	60	22	0
Gmsh blossom-full	64	64	156	0
Ours	64.0	62.0	0.75	31.0

Gmsh blossom and frontal-quad run at our element count; quasi-structured and blossom-full at their natural sizes, 3–15× ours. Ours: five attempts per domain at a doubled move budget with a split-and-continue repair, averaged over evaluation seeds. Curved-boundary results and full tables are in the paper.

Training data for free

Optimal meshes, walked backward

Some optimal meshes are easy to build: polyominoes, annuli, meshes around a hub. Undoing one edge at a time turns each into a sequence of the agent's own moves that ends at par, so behaviour cloning has unlimited, certified demonstrations.

Each row shows a constructed optimal mesh, a point part-way along the backward walk, the single face it starts from, and the instance the agent trains on.

Certified instances: constructed optimal meshes walked backward to a single face

Code

Get started

Install

git clone https://github.com/ArjunNarayanan/par-quad.git
cd par-quad
python3.12 -m venv venv
venv/bin/pip install -r requirements.txt

The paper's domains come from geo2d, released soon. Until then export GEOGEN_PATH=tools/geo2d_lite runs everything on a stand-in generator whose domains differ from the paper's.

Mesh a domain with the released agent

venv/bin/python utilities/animate_rollout.py \
    -suite straight-holes -draw 10 -n 24 \
    -out out -name demo

Writes out/demo.mp4. The README covers the paper's evaluation, the Gmsh comparison, the curved repair search and training from scratch (about four hours on a laptop).

Mesh Quest

Can you beat the agent?

Play the agent's game in your browser: the same moves, the same bound. It solves every straight-sided level, but not every curved one.

Play now

Mesh Quest, the block decomposition puzzle game

Citation

Cite this work

@article{narayanan2026playing,
  title   = {Playing to Par: Reinforcement Learning for Provably Optimal
             Quadrilateral Block Decompositions},
  author  = {Narayanan, Arjun and Persson, Per-Olof},
  journal = {arXiv preprint arXiv:2609.32146},
  year    = {2026}
}