HexIt: Learning Hexahedral Block Decomposition with Expert Iteration on Combinatorial Maps
Organizations: University of California, Berkeley · Department of Mathematics, University of California, Berkeley
Abstract
Decomposing a polyhedral solid into a few well-shaped hexahedral blocks is a long-standing open problem in mesh generation. We cast it as a sequential decision problem on a 3-dimensional generalised map: an agent splits edges, faces and volumes with three insert operations until every cell is a hexahedron and the mesh passes a quality threshold, and a policy that convolves over the map's involutions chooses each insert. A successful decomposition takes over a hundred decisions, and a uniformly random policy never finds one. We clone a policy from constructed decompositions and improve it by expert iteration. On held-out chamfered solids that share no boundary topology with the cloning data, the final policy solves an expected in samples, and expert iteration raises the best-of-20 solve rate on large chamfered solids from to . At matched compute, PPO, GRPO and VinePPO updates all make the cloned policy worse.
Figures & tables
| Set | Solids | Role | |
|---|---|---|---|
| Rectilinear | polycube / tilted, 17–60 cells | 260 | test |
| Small chamfered | chamfered, ratio 4 | 100 | main test |
| Large chamfered | chamfered, ratio 10, F 16 | 193 | test (size) |
| Unseen corner types | pyramids, octahedron | 4 | test (OOD) |
| Small-chamfered selection | chamfered, ratio 4 | 114 | validation (selection) |
| Large-chamfered selection | chamfered, ratio 10 | 169 | validation (selection) |
| Policy | Rectilinear | Small cham. | Large cham. | Unseen corners |
|---|---|---|---|---|
| Learned | ||||
| Clone , seed 1, | 0.991 ( 0.837 ) | 0.904 (0.430) | 0.187 (0.021) | 0/4 (0.000) |
| Clone , seed 2, | 0.994 (0.836) | 0.926 (0.454) | 0.218 (0.033) | 0/4 (0.000) |
| seed 1 (round 5, ) | 0.996 (0.829) | 0.950 ( 0.537 ) | 0.383 ( 0.072 ) | 0/4 (0.000) |
| seed 2 (round 3, ) | 0.992 (0.789) | 0.939 (0.521) | 0.328 (0.057) | 0/4 (0.000) |
| Seed means, best-of-20 | ||||
| Set | Policy | Solved | C / E / F | Ratio | Hex. | Floor | SJ |
|---|---|---|---|---|---|---|---|
| Rectilinear | s1 | 217/218 | 142/72/3 | 0.96 [0.93, 1.00] | 37 34 | 98.6% | 0.86 |
| s2 | 216/218 | 142/71/3 | 0.96 [0.93, 1.00] | 37 34 | 98.1% | 0.85 | |
| s1 | 217/218 | 145/68/4 | 0.96 [0.92, 1.00] | 37 34 | 96.8% | 0.86 | |
| s2 | 214/218 | 146/66/2 | 0.96 [0.91, 1.00] | 37 33 | 95.8% | 0.86 |
| Hexahedra | Excess | |||||
|---|---|---|---|---|---|---|
| Set | Gmsh | Ratio | Gmsh | Gmsh SJ | ||
| Rectilinear | 32.5 | 878 | 0.03 | 0 | 3,184 | 0.05 |
| Small chamfered | 21 | 296 | 0.07 | 18 | 1,071 | 0.11 |
| Large chamfered | 49 | 756 | 0.07 | 31.5 | 2,594 | 0.06 |
Appendix figures & tables6 assets
Supplementary material from the paper’s appendix.
Appendix
| Seed | Round | New | Upg. | Small sel. | Large sel. | Small val. | ||
|---|---|---|---|---|---|---|---|---|
| 1 | 4 | — | — | 0.483 | 0.974 / 0.595 | 0.152 / 0.027 | 0.947 / 0.534 | |
| 4 | 7,094 | — | 0.533 | 0.974 / 0.664 | 0.236 / 0.063 | — | ||
| 4 | 896 | 291 | 0.537 | 0.974 / 0.710 | 0.242 / 0.071 | — | ||
| 3 | 421 | 445 | 0.543 | 0.965 / 0.657 | 0.259 / 0.060 | 0.972 / 0.584 | ||
| 4 | 213 | 564 | 0.555 | 0.974 / 0.718 | 0.272 / 0.077 | — | ||
| 3 | 164 | 713 | 0.574 | 0.991 / 0.707 | 0.293 / 0.080 | 0.987 / 0.634 |
| Wins | Pool ps | Small val. | |||||
|---|---|---|---|---|---|---|---|
| Arm | it. 2 | it. 3 | Train | Held | ps | Zero | |
| — | — | 0.313 | 0.360 | 0.513 | 0.944 | 6 | |
| POPO, | 362 | 375 | 0.388 | 0.412 | 0.500 | 0.906 | 13 |
| POPO, uniform | 350 | 330 | 0.311 | 0.332 | 0.474 | 0.943 | 6 |
| PPO KL | 242 | 144 | 0.166 | 0.183 | 0.354 | 0.870 | 17 |
| VinePPO KL | 291 | 164 | 0.100 | 0.140 | 0.271 | 0.798 | 26 |
| Source | Contents | Solids | Excl. | Replays ok / failed | States |
| Grid certificates | |||||
| Small certified | polycube, tilted, Geo3D, polar, CC; cells | 5,000 | 357 | 9,236 / 50 | 477,549 |
| Small certified, short | same families, fresh draws | 5,000 | 352 | 9,261 / 35 | 475,989 |
| Large Geo3D | – cells | 1,000 | 0 | 957 / 43 | 191,061 |
| Large polycube / tilted | – cells | 3,000 | 0 | 2,941 / 59 | 517,040 |
| Geo3D, long loops | – cells, face-loop cap | 2,000 | 1 | 1,920 / 79 | 335,326 |
| Archived solids | States | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Seed | Round | SC | CC | LC | RP | Sol. | Archive | Trained | |
| 1 | 1 | 2,872 | 983 | 390 | 2,849 | 7,094 | 963,684 | 321,228 | 1,284,864 |
| 2 | 2,938 | 1,436 | 662 | 2,954 | 8,265 | 1,192,148 | 397,383 | 1,589,504 | |
| 3 | 2,958 | 1,640 | 834 | 2,979 | 8,979 | 1,331,856 | 443,952 | 1,775,744 | |
| 4 | 2,968 | 1,744 | 927 | 2,985 | 9,455 | 1,424,698 | 474,899 | 1,899,584 | |
| 5 | 2,974 | 1,823 | 1,002 | 2,989 | 9,904 | 1,500,295 | 500,098 | 2,000,384 | |
| Seed | Round | GPU-h | Mining | Archive | Val. | CPU total |
|---|---|---|---|---|---|---|
| 1 | 15.7 | — | — | 376 | 439 | |
| 1 | 1.8 | 2,352 | 243 | 263 | 2,872 | |
| 2 | 2.2 | 1,880 | 295 | 189 | 2,375 | |
| 3 | 2.3 | 1,718 | 324 | 191 | 2,245 | |
| 4 | 2.7 ∗ | 1,381 | 332 | 143 | 1,880 | |
| 5 | 2.7 ∗ | 1,415 | 360 | 204 | 2,003 |
| Set | Drawn | Matched in | Reported |
|---|---|---|---|
| Rectilinear | 472 | 212 | 260 |
| Small chamfered | 278 | 178 | 100 |
| Large chamfered | 199 | 6 | 193 |
| Unseen corner types | 4 | 0 | 4 |
3D Mesh Generation
3D mesh generation creates and edits connected 3D surfaces for digital content, reconstruction, animation, and simulation.
See all 85 papers