acceptodds
Under review as a conference paper at ICLR 2027

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

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.

Primary area:
learning on graphs and other geometries & topologies
Keywords:
reinforcement learning, combinatorial optimization, geometric deep learning, mesh generation, computational geometry, graph neural networks

Reviews

Among:
Shape:
1234this paper, Top 32%
Figure 1. Mean review rating of the reviewed papers at ICLR 2027. This paper averages 2.50 over 2 reviews, above 68% of the others.
Reviewer_ZicYOpenReview ↗
Rating
2
Confidence
3
Informativeness
2
Presentation
3
Soundness
2
Read review
Paper summary

The paper studies coarse quadrilateral block decomposition of planar domains. It uses a lower bound on total vertex-degree irregularity derived from the discrete Gauss-Bonnet identity as an optimality certificate: a valid all-quadrilateral mesh attaining this bound is optimal for that objective. The policy constructs meshes from the domain boundary through local DCEL edits, using half-edge convolutions that follow the mesh connectivity. Training begins with behavior cloning on demonstrations generated by working backward from constructible optimal meshes, followed by PPO. The evaluation procedure includes smoothing, multiple rollouts and repair, with an additional search for domains with curved boundaries. The reported results show low vertex irregularity and high completion rates on generated straight-sided domains, including larger instances and domains with holes, but performance is less consistent across larger domains with curved boundaries.

Critical strengths

1.The method performs well at generating coarse, regular block decompositions on the tested domains. Table 1 reports complete all-quadrilateral meshes for all 96 in-distribution domains, with mean counts of 95.7 usable meshes and 90.2 meshes at par across evaluation seeds. By comparison, Gmsh's quasi-structured method produces 96 usable meshes but reaches par on only two domains, while using approximately 3.2 times as many elements. These results are meaningful for applications where connectivity regularity and mesh coarseness matter. The certificate also provides a precise guarantee: valid meshes that reach par are optimal for the stated irregularity objective.

2.The experiments show a substantial benefit from the training recipe. In Table 9, behavior cloning followed by 1M PPO steps increases the mean number of in-distribution domains reaching par from 22.3 with cloning alone to 76.2. PPO trained from scratch for the same number of steps reaches par on only 7.2 domains. The paper also evaluates larger domains, domains with holes, and 48 held-out instances with nonzero par, reaching par on 47 of the latter. Together, these experiments provide strong evidence that combining certified demonstrations with subsequent reinforcement learning is effective beyond a small set of illustrative shapes.

Critical weaknesses

1.The contribution relative to the closest prior work is not sufficiently established. Narayanan et al. already define an irregularity lower bound, terminate when it is reached, and normalize returns by the remaining gap (arXiv:2309.06484). They also use DCEL-based convolutions combining cyclic-next and twin features, with a learnable boundary vector. For the same fixed desired-degree assignment, their bound coincides with the expression underlying par, by the Gauss-Bonnet identity. The present paper cites this work, and constructing meshes from a bare boundary, allowing non-quadrilateral intermediate states, and incorporating certified demonstrations and geometric quality are meaningful differences. However, Sections 1 and 7 should distinguish these changes more carefully from the existing mechanisms. More importantly, the external baselines are all Gmsh configurations; the closest learning-based method is not included. The reported comparisons therefore demonstrate advantages over the tested production meshers in obtaining coarse, regular decompositions, but do not establish the benefit of the proposed changes over the prior RL framework. This gap directly affects the assessment of the methodological contribution.

2.The curved-domain experiments do not separate the effects of search and candidate selection, and they show clear limitations in generalization. Table 2 reports that repair search increases the number of meshes meeting the tangent-based usability criterion from 74 to 95 out of 96, and the number reaching par from 19 to 37. However, Appendix L also describes a change in the selection criterion: the search procedure prioritizes regularity among usable candidates, whereas the no-search variant uses quality-first selection. The difference in at-par counts therefore cannot be attributed to additional search alone. A comparison using the same ranking rule is needed to separate these effects. The search can take up to 600 seconds per domain. Across the two larger curved-domain suites in Table 10, only 40 of 64 meshes meet the tangent-based usability criterion, and only two reach par. Although the paper acknowledges these limitations, they restrict how broadly the results can be interpreted as evidence of generalization by the learned policy. Separating the gains due to search from those due to candidate selection, and reporting the trade-off between runtime and quality, would make this claim more convincing.

Questions for authors

1.Clarify the incremental contribution relative to Narayanan et al. In particular, distinguish boundary-only construction and training on certified demonstrations from the lower-bound termination, normalized returns and DCEL convolutions already used in their framework. Can you provide a direct comparison on a common subset of domains? If there are substantive obstacles to such a comparison, please explain them and provide an appropriate controlled alternative.

2.Can you report the results with and without repair search on domains with curved boundaries under the same candidate-ranking rule, together with a summary of per-domain runtimes? How much of the observed improvement remains when the candidate-selection rule is held fixed?

1 comment
AuthorsOpenReview ↗

Comparison to prior learning-based methods and updates on curved boundary handling

Thank you for the detailed review. We have included substantial updates to the manuscript based on the feedback, and changed text is marked in blue.

1. Contribution relative to Narayanan et al. (2024).

We agree that the paper should separate what it inherits from what is new. The revision now does so where appropriate and we summarize below.

  • The half-edge state and the convolution over the next and twin pointers (Section 4). We generalise it from elements with a fixed number of sides to arbitrary polygonal faces.
  • The irregularity lower bound for a fixed assignment of desired degrees, using it as part of a termination test (Section 2). Their rule can sometimes lie above the true optimum due to a rounding artifact (see below).
  • Normalising returns so that domains of different sizes carry equal weight (Section 3.3). They divide the return from each state by the gap remaining at that state; we divide by the initial gap.

New in this work.

  1. Element quality in the reward. Their objective is vertex irregularity alone, so nothing in training discourages thin or inverted elements. Our reward adds a quality term, charged at the move that creates a poorly shaped element (Section 3.3). This is the largest difference in the comparison below: their agent is usable on 23 of 96 domains, against 95.7 for ours.
  2. Tie-aware par. Their rule assigns a 135° corner a single desired degree due to rounding. Par admits either, so on the 36 chamfered domains of our benchmark their bound in fact lies above the true minimum (Section 2, Appendix D).
  3. Construction from the bare boundary through non-quadrilateral states. Their agent edits an all-quadrilateral start mesh produced by a separate mesher and must keep every state all-quadrilateral, requiring rule-based nonlocal action, their global split. Our actions are local and may create faces with any number of sides, and need no hand-designed nonlocal action. We show that our block structure is coarser with fewer irregularities.

Direct comparison. We ran their trained quadrilateral agent, in the configuration of their Table 1, on our 96 in-distribution domains in its own pipeline (see Appendix D).

Head to head, our mesh is better on quality and regularity on 98% of decided domains. Their start meshes carry a median irregularity of 26 to 72 above their own bound, which is reduced to 2 to 4. Even measured against their own sub-optimal bound, they succeed on at most 44 of the 96 domains. The difference in element quality is much larger -- most of their meshes are not usable from a quality perspective. Appendix E compares the block structure each method's mesh implies, and Figure 7 shows the methods on one domain per family. Section 6.2 discusses which differences contribute to the gap.

2. Curved domains: search, candidate selection and runtime.

After submission we tried a simpler alternative to the test-time search: continuing to train the agent with PPO on a mixture of the straight-sided families and curved domains (Appendix F). It proved the better approach, so the revision removes the search and its repair strategy, and Section 6.4 now presents the curved-trained agent. Every agent is evaluated with the same procedure and candidate-ranking rule as Table 1, so the curved results no longer mix the effect of search with that of selection. The new Table 2:

all-quadusablemedian excessat par
Gmsh, four configurations43–963–2610–320
Ours, straight-sided training only9381418
Ours, with curved training9695233

Usable counts here judge quality against the arc tangents. Over six rollout seeds the curved-trained agent reaches par on 31.3 ± 0.9 of 96, and a second training seed gives 28.2. It wins on regularity on 98–100% of decided domains against every Gmsh configuration, and on tangent quality on 86–100%. The tradeoff is reduction in at-par on straight-sided domains from 90.3 to 81.0 of 96, noted as a limitation in Section 7.1, but we still remain the most regular method against all others compared by a significant margin.

Runtime. With no search, the procedure takes a median of 10 s per domain without holes and 17 s with holes on curved domains with 8–24 corners, single-threaded, and about a minute on the larger curved domains below.

Larger curved domains. We agree that these remain harder. On 96 domains with 25–50 corners, the curved-trained agent is usable on 90% and 83% of evaluations over three rollout seeds. Its median excess over par is 8 on both suites, against 25 to 117 for Gmsh at up to eight times the element count. Par is rare at this size for every method (Appendix F, Table 6).

Thank you again. The direct comparison and the controlled curved evaluation make the paper's claims more precise.

Reviewer_DD8zOpenReview ↗
Rating
3
Confidence
2
Informativeness
3
Presentation
2
Soundness
3
Read review
Paper summary

This paper presents a reinforcement learning approach to quadrilateral block decomposition. A policy performs local mesh edits to improve vertex regularity while also considering element shape. Training starts with behavior cloning from demonstrations built by reversing known optimal meshes, followed by PPO. An existing lower bound is used to certify the optimality of outputs that reach the minimum vertex irregularity. The method is evaluated on domains with different sizes, holes, and curved boundaries. 60154_Playing_to_Par_Reinforce

Critical strengths
  1. The method produces highly regular meshes and compares favorably with the tested Gmsh settings. The training ablation is particularly useful: adding PPO after behavior cloning increases the average number of domains reaching the optimality bound from 22.3 to 76.2 out of 96. This provides clear evidence that RL improves the policy beyond imitation alone.

  2. Learning local mesh edits is a natural approach to this structured decision problem. The results on larger domains suggest that the policy learns useful strategies beyond the training sizes. The use of a mathematical lower bound is also valuable, since successful outputs can be checked rather than judged only against baselines.

Critical weaknesses
  1. The paper could better explain why regular quadrilateral block decompositions matter in practical applications. The experiments mainly use generated geometric domains and evaluate mesh quality and regularity. Adding one or two downstream tests, such as finite-element analysis or PDE solving, would help show whether these improvements lead to better accuracy or lower computational cost. This would make the importance of the method clearer.

  2. Some passages feel generic or too compressed, making the paper harder to follow for readers outside mesh generation. A simple running example would help explain how the learned policy, smoothing, and test-time repair work together. The overview should also highlight that the optimality guarantee concerns vertex irregularity, not overall mesh quality. More concrete explanations and smoother transitions would make the presentation feel more complete.

Questions for authors

none

2 comments
AuthorsOpenReview ↗

Motivation for regular meshes and clarifying the optimality bound

Thank you for the careful review and for the two concrete suggestions. We address both below. All changes are in the revised PDF, marked in blue.

1. Why regular block decompositions matter in practice.

We agree that the paper should make this case explicitly. The revision adds a paragraph to Section 1:

  • Regular layouts support smooth high-order bases. On a regular quadrilateral layout one can build tensor-product spline bases: degree-pp B-splines in each direction, Cp−1C^{p-1} across every element boundary. Spline and subdivision surfaces in CAD and graphics, isogeometric analysis (Hughes et al., 2005) and other high-order structured discretisations rely on this.
  • Irregular vertices break that structure. At an irregular vertex no tensor-product structure exists. A discretisation must either drop to C0C^0 there or use a special construction that recovers smoothness at a considerable cost in complexity, often with slower convergence near the vertex (e.g., Collin et al., 2016; Toshniwal et al., 2017).
  • Some problems require the smoothness. Fourth-order problems such as Kirchhoff–Love shells, biharmonic plates and the Cahn–Hilliard equation need C1C^1 (H2H^2-conforming) basis functions, so dropping to C0C^0 is not an option (Cirak et al., 2000; Kiendl et al., 2009; Gómez et al., 2008).
  • Multi-block structured meshing. In computational fluid dynamics and other structured solvers, the domain is cut into blocks that are each filled with a structured grid. This allows boundary-aligned, smoothly graded cells, structured high-order stencils and efficient solvers (Armstrong et al., 2015). Each irregular vertex is a block corner where the grid metrics are singular and standard stencils do not apply, and the block layout couples grid resolution across the domain. Building this layout is still largely manual.

To make the multi-block reading concrete, a new appendix (Appendix E, Table 5 and Figure 5) shows the block structure each method's mesh implies. Tracing the separatrices from every irregular vertex and domain corner partitions a mesh into structured blocks, its base complex (Bommes et al., 2013). Our output is already a block decomposition, with a median of 12 blocks on the 96 domains. The structure implied by Gmsh's quasi-structured meshes has a median of 27 blocks, more than ours on 91 of 96 domains, with singularities beyond the bound. The block count does not change under uniform refinement, so the comparison is fair despite Gmsh's larger element count.

On the suggested finite-element test: we do not claim that low-order solvers are more accurate on regular meshes, and high-order C0C^0 elements also work on irregular ones. The value of regularity lies in smooth high-order bases and the problems that need them, and the revision states this scope explicitly. Because this is well established in the literature cited above, we point to it rather than repeat those studies.

2. Presentation.

Thank you. We revised accordingly:

  • Running example. A new figure (Figure 3, Section 6.1) follows one domain through the whole evaluation procedure. The agent's best attempt has folded elements beside both holes; the untangling smoother unfolds them, leaving one element below the usability bar; the split-and-continue repair inserts a vertex on that element's long side, and the policy finishes a usable mesh. Section 6.1 now explains how the policy, the smoother and the repair fit together.
  • What "optimal" means. The abstract, the introduction where par is introduced, Section 2 and the conclusion now state explicitly that the bound and the certificate concern vertex irregularity. A mesh at par is optimal in vertex regularity; element quality is a separate requirement that we measure with the usability bar.
  • Compressed passages. We rewrote the passages that are hardest to follow without a meshing background. Section 3 now explains how the agent's local window is centred and when an episode ends. Section 6.1 defines the win rate and how ties are handled. Section 6.4 is rewritten around a single evaluation procedure. Every table caption now defines its own metrics, and the appendices are reordered so that the material the main text relies on comes first.

Thank you again. We believe these changes make the practical motivation and the scope of the optimality bound clear.

I thank the authors for their detailed response, which has addressed most of my concerns. I therefore decided to maintain my recommendation of Weak Accept.

Comments on the paper

1 comment

Dear Reviewers,

As the initial review scores for this submission are somewhat divergent, it is important that we thoroughly discuss our perspectives before reaching a final recommendation.

Now that the authors' rebuttal is available, I kindly ask each of you to respond in the discussion and clarify whether your original concerns have been addressed or still remain.

Thank you in advance for your timely engagement before the discussion period ends.

Best, Your AC

From OpenReview, CC BY 4.0. Authors as signed there; shown unedited.

Related papers

Loading the map…

Discussion (0)

Sign in to comment.