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

Arjun Narayanan; Per-Olof Persson

cs.LGSep 26, 2026

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

Authors: Arjun Narayanan, Per-Olof Persson

Organizations: UC Berkeley

Abstract

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.

Figures & tables

Figure 1: Our agent and Gmsh on the same three domains. Top: an in-distribution domain (chamfered, with a hole,

18

corners). Middle: a larger-boundary domain (

38

corners), beyond any seen in training. Bottom: a curved domain with holes (

33

corners); the agent was never trained on a curved boundary, and quality is given against the arc tangents and on chords (Section 6.4 ). Gmsh blossom is asked for our element count and returns the closest it can reach; quasi-structured runs at its natural size. Every irregular vertex is marked. Our top mesh has none, which the Gauss–Bonnet bound (Section 2 ) certifies as optimal; the middle one has one, against

32

and

16

for Gmsh, and the curved one

15

, against

64

and

35

. Domains are chosen by the rule of Appendix M , which shows one per family.

Panel of Figure 2 — Figure 2: (a) A mesh is stored as a doubly connected edge list: every edge carries two oppositely oriented half-edges, and all connectivity is expressed through next and prev , which walk a face loop counter-clockwise, and twin , which crosses to the adjoining face. A half-edge on $\partial\Omega$ has no twin, and the network is told so by a sentinel distinct from the one marking a neighbour that merely fell outside the window. (b) From a half-edge $h$ with source $u$ , three actions insert a chord to the vertex $j+2$ positions ahead in the face loop, cutting off a sub-face of $j+3$ sides; the fourth splits $h$ ’s own edge with a new vertex. Chords leaving a $2$ -gon on either side are masked out.

96 in-distribution domains ( $8$ – $24$ corners)
							our win rate
	all-quad	usable	excess	at par	elements	$\times$ ours	quality	regularity
Gmsh blossom	$51$	$38$	$9$	$0$	$19$	$1.2$	$90\%$	$100\%$
Gmsh frontal-quad	$43$	$29$	$8$	$1$	$16$	$1.0$	$90\%$	$100\%$
Gmsh quasi-structured	$\mathbf{96}$	$\mathbf{96}$	$7.5$	$2$	$51$	$3.2$	$67\%$	$100\%$
Gmsh blossom-full	$\mathbf{96}$	$\mathbf{96}$	$26$	$0$	$220$	$14.0$	$37\%$	$100\%$

Table 1: Top: the 96 in-distribution domains, mean over six evaluation seeds (per family: Table 7 ). Bottom: the 64 larger-boundary domains, four evaluation seeds; its last rows remove parts of the evaluation-time procedure (cumulatively) and add attempts. Columns and win rates as defined in Section 6.1 ; each Gmsh configuration is asked for our element count and returns the closest it can reach. Bold: best in column within a block (elements: among methods complete on every domain).

							usable		quality win
	all-quad	excess	at par	elem.	$\times$ ours	reg. win	tangent	chord	tangent	chord
Gmsh blossom	$62$	$20$	$0$	$60$	$1.1$	$100\%$	$7$	$54$	$94\%$	$54\%$
Gmsh frontal-quad	$55$	$22$	$0$	$58$	$1.1$	$100\%$	$2$	$42$	$100\%$	$78\%$
Gmsh quasi-structured	$\mathbf{96}$	$10$	$0$	$83$	$1.5$	$100\%$	$6$	$64$	$95\%$	$67\%$
Gmsh blossom-full	$93$	$32$	$0$	$235$	$4.4$	$100\%$	$25$	$79$	$74\%$	$47\%$
Ours	$\mathbf{96}$	$\mathbf{2}$	$\mathbf{37}$	$\mathbf{54}$	$1.0$		$\mathbf{95}$	$\mathbf{88}$

Table 2: Curved boundaries: the released agent without retraining, one evaluation pass on

96

domains with

8

–

24

corners. Left: columns that do not depend on how quality is measured, as in Table 1 (at par with

q\geq 0.1

on the tangents; on chords quasi-structured reaches par on

2

). Right: usable count and our win rate on quality, with element quality judged against the arc tangents or chords. Ours: with the repair search; the row below it is the five attempts and doubled budget of Section 6.1 without any repair. Bold: best in column (elements: among methods complete on every domain).

Appendix figures & tables14 assets

Supplementary material from the paper’s appendix.

Appendix

Figure 3: Certified instances, one per family, each the first accepted at a fixed seed. Columns: the constructed optimal mesh; the backward walk a third of the way through; the single face it ends on, which is the start state; and the training instance, the transformed outline with the recorded moves replayed on it and accepted as solved. The last three rows are drawn with rotation and scale undone. Holed outlines keep one edge joining the hole to the outer boundary, so that the start state is a single face. Shaded: faces that are not quadrilaterals.

set	sub-problems	par $0$	$1$	$2$	$3$	$\geq 4$	par $>0$	episodes
96 in-distribution	$2{,}195$	$60.7\%$	$33.8\%$	$4.6\%$	$0.8\%$	$0.1\%$	$39.3\%$	$75$ of $96$
64 larger	$11{,}717$	$26.7\%$	$59.0\%$	$10.9\%$	$3.0\%$	$0.4\%$	$73.3\%$	$64$ of $64$

Appendix

Table 3: Bounds of the sub-problems met in the released agent’s greedy attempt on the par-zero evaluation domains; the last column counts episodes that meet at least one sub-problem with par above zero.

	par $1$ ( $11$ )	$2$ ( $17$ )	$3$ ( $17$ )	$4$ ( $3$ )	total	all-quad
Ours	$\mathbf{11}$	$\mathbf{16}$	$\mathbf{17}$	$\mathbf{3}$	$\mathbf{47}$	$\mathbf{48}$
Gmsh quasi-structured	$2$	$6$	$0$	$0$	$8$	$\mathbf{48}$
Gmsh packing	$0$	$3$	$4$	$0$	$7$	$8$
Gmsh frontal-quad	$1$	$0$	$0$	$0$	$1$	$27$
Gmsh blossom	$0$	$0$	$0$	$0$	$0$	$30$
Gmsh blossom-full	$0$	$0$	$0$	$0$	$0$	$9$

Appendix

Table 4:

48

held-out domains with par above zero: domains at par, by par. Ours: best of five attempts, ranked by completion and then closeness to par, at the default move budget. Gmsh: at the agent’s element count where it can reach it.

Panel of Figure 4 — Figure 4: The policy. The trunk is per half-edge: convolved features pass through a shared per-slot linear layer to the action head. Pooling is a branch — it collapses the half-edge axis, and the global vector and progress scalar, which never enter message passing, join there. The context vector it produces is one vector per state: the critic’s only input, and, on the actor side, an identical shift added to every half-edge before a shared linear head. It can therefore re-weight the four action types but cannot by itself favour one half-edge over another — selecting where to act rests on the convolution and on the rule that decides which half-edges are in the window at all.

observation window $n_{T}$	$64$ half-edges
edge-length feature	divided by the window’s median
global scalars	per face, seven entries
actions per half-edge	$4$ : chords to $+2$ , $+3$ , $+4$ ; vertex insertion
default move budget $T_{\max}$	$\max(12,\lceil 3\|\mathcal{H}_{0}\|\rceil)$
smoothing per move	$5$ Laplacian sweeps, corners pinned
potential weights $w_{v}$ , $w_{q}$ , $q^{\star}$	$1$ , $8$ , $0.4$

Appendix

Table 5: The released configuration.

							our win rate
	all-quad	usable	excess	at par	elements	$\times$ ours	quality	regularity
Gmsh blossom	$51$	$38$	$9$	$0$	$19$	$1.2$	$90\%$	$100\%$
Gmsh frontal-quad	$43$	$29$	$8$	$1$	$16$	$1.0$	$90\%$	$100\%$
Gmsh packing	$8$	$6$	$5$	$0$	$15$	$0.9$	$98\%$	$100\%$
Gmsh simple-recombine	$2$	$1$	$11$	$0$	$14$	$0.9$	$100\%$	$100\%$
Gmsh subdivide	$\mathbf{96}$	$43$	$49$	$0$	$85$	$5.4$	$97\%$	$100\%$

Appendix

Table 6: Seven Gmsh configurations on the 96 in-distribution domains, each asked for the agent’s element count where it can produce one; the elements column gives the mean over its all-quadrilateral meshes and its multiple of our

15.7

. On packing and simple-recombine nearly every win is decided by completion. Bold: best in column; for elements, among methods complete on every domain (packing and simple-recombine average over

8

and

2

meshes). Our win rate: fraction of decided domains on which our mesh is better on quality and on regularity, under the rule of Section 6.1 .

Figure 5: Per-mesh minimum quality and excess over par, one mesh per domain: the agent in one evaluation pass (rollout seed

0

) and Gmsh asked for that pass’s element count on each domain. Quality panels: domains per bin, hatched bar not all-quadrilateral. Excess panels: share of the method’s all-quadrilateral meshes, with the number at zero quoted. The counts are this pass’s; the tables report the mean over evaluation seeds.

family	method	all-quad	usable	excess	at par	elements
chamfered	Ours	$24.0$	$24.0$	$0$	$20.7$	$14$
	Gmsh blossom	$14$	$12$	$8.5$	$0$	$19$
	Gmsh quasi-structured	$24$	$24$	$6.5$	$0$	$54$
rectilinear	Ours	$24.0$	$24.0$	$0$	$23.8$	$10$
	Gmsh blossom	$16$	$10$	$8$	$0$	$15$
	Gmsh quasi-structured	$24$	$24$	$5$	$1$	$38$

Appendix

Table 7: The in-distribution block of Table 1 by family: best of five attempts under the procedure, mean over six evaluation seeds. Columns in the order a mesher is judged: all-quadrilateral, usable (

q\geq 0.3

), median excess over par, and at par (the certified optimum). Gmsh blossom is given the agent’s element count on each domain; quasi-structured cannot go that coarse and runs at its natural size,

3.2\times

the agent’s. Bold: best in column over all 96 domains.

set	column	mean	sd	range
96 in-distribution, $6$ seeds	all-quad	$96.0$	$0.0$	$96$ – $96$
	usable	$95.7$	$0.5$	$95$ – $96$
	excess	$0$	$0.0$	$0$ – $0$
	at par	$90.2$	$1.3$	$88$ – $92$
64 larger, $4$ seeds	all-quad	$64.0$	$0.0$	$64$ – $64$
	usable	$62.0$	$1.0$	$61$ – $63$

Appendix

Table 8: The released agent under the procedure of Section 6.1 : mean, standard deviation across evaluation seeds, and range.

extractor	params	at par
DCEL, $4$ layers	$299$ k	$\mathbf{94.5}$
Transf., $4$ layers	$300$ k	$51.5$

Appendix

Table 9: Left: domains at par of the 96 in-distribution domains, best of five, at a matched

2

M steps under an earlier configuration of the recipe, mean of two seeds. Right: PPO from a fresh network, cloning only, and cloning then PPO, at

1

M PPO steps, seed

1

, best of five at the default move budget and without repair.

suite	method	all-quad	excess	at par	elem.	$\times$ ours	tangent	chord	tangent	chord
							usable		quality win
$8$ – $24$	Gmsh blossom	$35$	$18$	$0$	$60$	$1.1$	$3$	$31$	$94\%$	$50\%$
	Gmsh frontal-quad	$30$	$18$	$0$	$58$	$1.1$	$2$	$23$	$100\%$	$77\%$
	Gmsh quasi-structured	$\mathbf{48}$	$9$	$0$	$81$	$1.6$	$3$	$33$	$94\%$	$71\%$
	Gmsh blossom-full	$\mathbf{48}$	$31$	$0$	$249$	$4.8$	$13$	$44$	$73\%$	$46\%$
	Ours	$\mathbf{48}$	$\mathbf{2}$	$\mathbf{21}$	$\mathbf{52}$	$1.0$	$\mathbf{47}$	$\mathbf{45}$

Appendix

Table 10: Table 2 by suite, with the larger domains; every suite is curved. Columns, rows and win rates as there; our regularity win rate is

100\%

against every configuration in every suite and is omitted. Bold: best in column within a suite. The holed larger suite has

16

domains, the others

48

Figure 6: One domain per in-distribution family (

8

–

24

corners).

Figure 7: Larger-boundary domains (

25

–

50

corners), beyond any seen in training: one per family.

Figure 8: Curved domains, one per suite, meshed by the released agent, trained only on straight-sided domains, with the repair search, and by Gmsh as in Figure 1 . A boundary edge that lies on an arc is drawn along the arc; ours has a boundary node every $45^{\circ}$ of arc. Each panel gives the minimum element quality judged against the arc tangents and on the straight sides (Section 6.4 ); the hatching uses the tangent.

RL for Combinatorial Optimization

Reinforcement learning for combinatorial optimization learns sequential decisions and search strategies for difficult discrete problems.

See all 106 papers

Dmsh: A Multi-Agent Reinforcement Learning Framework for All-Quad Mesh Generation
Jun 9, 2026Anirudh Kalyan, Cosmin Anitescu, Xiaoying Zhuang +33D Mesh Generation
Mesh-RL: Coupled subgrid reinforcement learning
Jun 24, 2026Behnam Gheshlaghi, Bahador Rashidi, Shahin AtakishiyevReinforcement Learning Credit Assignment in RL
Independent Researcher · University of Alberta
Mesh-Pro: Asynchronous Advantage-guided Ranking Preference Optimization for Artist-style Quadrilateral Mesh Generation
Feb 28, 2026Zhen Zhou, Jian Liu, Biwen Lei +103D Mesh Generation RL for Generative Models
Institute of Automation, Chinese Academy of Sciences · Tencent Hunyuan · Hong Kong University of Science and Technology

Jun 9, 2026J/K move · Enter open · S save

Dmsh: A Multi-Agent Reinforcement Learning Framework for All-Quad Mesh Generation

Anirudh Kalyan, Cosmin Anitescu, Xiaoying Zhuang, Timon Rabczuk+2

3D Mesh Generation

Open paper AskPDF arXiv

Generating high-quality meshes for arbitrary geometries remains a fundamental bottleneck in computational engineering, often demanding heuristic tuning and semi-manual workflows. In this paper, we introduce Dmsh, a first fully automated reinforcement learning pipeline that unifies geometric decomposition and quadrilateral mesh generation within a single learning-based framework. Dmsh decomposes the problem through three coordinated agents handling topology simplification, geometric regularization, and mesh generation. The meshing process is formulated as a Markov Decision Process and solved using a parametric Soft Actor-Critic architecture with decoupled critics, enabling efficient exploration of a hybrid discrete-continuous action space. A curriculum learning strategy ensures scalability from simple domains to highly complex geometries, suppressing seed variance. By design, the recursive decomposition enables parallel meshing of subregions, yielding globally conforming all-quadrilateral meshes without post hoc correction. Across a wide range of benchmarks, Dmsh consistently outperforms existing methods in automation, robustness, and mesh quality, establishing a new paradigm for learning-based mesh generation.

Abstract

RL for Combinatorial Optimization

Explore similar work

Dmsh: A Multi-Agent Reinforcement Learning Framework for All-Quad Mesh Generation

Mesh-RL: Coupled subgrid reinforcement learning

Mesh-Pro: Asynchronous Advantage-guided Ranking Preference Optimization for Artist-style Quadrilateral Mesh Generation