Reinforcement learning finds best mesh decompositions for shapes
Playing to Par: Reinforcement Learning for Provably Optimal Quadrilateral Block Decompositions
Machine Learning
Summary
Complex shapes often need to be divided into smaller pieces, called quadrilateral blocks, for computer graphics and engineering tasks. The authors designed an AI that learns to cut shapes into these blocks as perfectly as possible, following strict math rules about vertex arrangement. Their AI works even on bigger shapes it wasn't trained on and beats existing methods in making neat, efficient block patterns. This advance helps create better meshes, which are essential for simulations and designs in many fields.
What this means in practice
- •For computational geometry developers: Generate optimal quadrilateral mesh decompositions for planar shapes to improve accuracy and efficiency of geometric modeling tasks.
- •For finite element analysis engineers: Produce high-quality quadrilateral meshes that minimize irregularities to enhance the precision and reliability of physical simulations.
Authors
Arjun Narayanan, Per-Olof Persson
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.