Validity-first automatic polycube
labeling for CAD models

Sébastien Mestrallet , Christophe Bourcier , Franck Ledoux
SIAM International Meshing Roundtable Workshop 2025
Reference implementation

Abstract

For many simulation codes, block-structured hex meshes remain preferred while their automatic generation is unsolved. We investigate the usage of a polycube-based approach. More specifically, we focus on the labeling stage, which consists in assigning each boundary facet to one of the 6 signed principal axis. Similar works are confronted with 2 challenges: over-constraining validity criteria, and the conflated processing of validity criteria with quality metrics. We tackle these obstacles with automatic routines based on semi-global labeling operators. Our approach is successfully tested on CAD models, which are of interest for many numerical simulation problems.

Paper

We will link to the IMR 2025 proceedings.

Requirements

• Linux-based OS
• gcc >= 11 (C++20)
• CMake > 3.11
• Geogram's other requirements, such as X11 development libraries

Dependencies

Name	License	Description	Inclusion
geogram	BSD-3-Clause	mesh data structure, I/O and GUI	git submodule
Eigen	Mozilla Public License 2.0	linear algebra, including JacobiSVD solver	CPM.cmake (CMake's FetchContent)
fmt	MIT	modern string formatting	git submodule
dbg-macro	MIT	the must-have dbg(...) macro to replace cout/printf-based debugging	git submodule
nlohmann/json	MIT	JSON for modern C++	git submodule
tinygltf	MIT	glTF 2.0 (the "JPEG of 3D") export	git submodule
DisjointSet	MIT	disjoint-set/union-find data structure, implementation by Nayuki	in the source code
gco-v3.0	for research purposes only, patented	multi-label energies optimization, implementation by Olga Veksler and Andrew Delong	in the source code

How to build

git clone --recurse-submodules https://github.com/LIHPC-Computational-Geometry/validity-first-polycube-labeling.git
cd validity-first-polycube-labeling

Open ext/geogram/src/lib/geogram/mesh/mesh_halfedges.h and change accessibility of MeshHalfedges variables from private to protected.

         void move_to_opposite(Halfedge& H) const;
 
-    private:
+    protected:
         Mesh& mesh_;
         Attribute<index_t> facet_region_;

Then:

# from validity-first-polycube-labeling/
mkdir build_Release
cd build_Release
cmake .. -G Ninja -DCMAKE_BUILD_TYPE=Release
ninja

Remove -G Ninja to use Make instead, if you don't have Ninja.

File format

During development, we used :

• the MEDIT / Gamma mesh file (GMF) ASCII format (.mesh) for tetrahedral and hexahedral meshes
• the Wavefront OBJ (.obj) format for 3D triangle meshes

but, as Geogram-based code, other formats can be used.

The .obj surface of a tetrahedral mesh can be generated withe the extract_surface app.

Polycube labelings are stored in a separate file, in plain text (.txt), with as many lines as there are triangles in the input 3D triangle mesh. For each line there is an integer in [0:5] encoding {+X,-X,+Y,-Y,+Z,-Z}.

Main algorithm : automatic_polycube app

It generates a polycube labeling labeling.txt from a 3D triangle mesh surface.obj.

# from validity-first-polycube-labeling/build_Release/
./bin/automatic_polycube ../data/B0/surface.obj output=../data/B0/labeling.txt gui=false

There is also a graphic user interface, to manually apply labeling operators :

# from validity-first-polycube-labeling/build_Release/
./bin/automatic_polycube ../data/B0/surface.obj gui=true
# or just
./bin/automatic_polycube
# then drag-and-drop a .obj in the 3D viewer

1. In the right panel, click on "Compute graph-cuts labeling" to generate de default initial labeling
2. If the labeling in invalid*, try the "Auto fix validity" button, which loop over manual operators whose button is just above
3. If not all boundaries are monotone*, try "Auto fix monotonicity", which loop over manual operators whose button is just above
4. In the menu bar, click on "File" > "Save as", choose a location and a filename, and select "txt" as extension to export the per-surface-triangle labeling.

*Not the case with the provided B0 model.

Visualize an existing labeling

You can use the labeling_viewer app, which is the base of the automatic_polycube one and does not contain labeling modification buttons.

# from validity-first-polycube-labeling/build_Release/
./bin/labeling_viewer ../data/B0/surface.obj ../data/B0/labeling.txt
# or just
./bin/labeling_viewer
# then drag-and-drop a .obj then a .txt in the 3D viewer

You can also export a .geogram mesh, with the polycube labeling as embedded attribute, and open it with Graphite.

# from validity-first-polycube-labeling/build_Release/
./bin/labeling_viewer ../data/B0/surface.obj ../data/B0/labeling.txt ../data/B0/output_labeled_surface.geogram

Generate a hexahedral mesh from a given labeling

See

• polycube_withHexEx : simple polycube parametrization, then calls libHexEx for the quantization (Lyon et al. 2016)
• robustPolycube : robust quantization (Protais et al. 2022)

You may need to use our volume_labeling app first to export a per-tetrahedron-facet labeling.

How to cite our work

S. Mestrallet, C. Bourcier, and F. Ledoux, "Validity-first automatic polycube labeling for CAD models", Proceedings of the 2025 International Meshing Roundtable, SIAM, March 2025

BibTeX

@inproceedings{mestrallet2025,
    title     = {Validity-first automatic polycube labeling for CAD models},
    author    = {Mestrallet, S{\'e}bastien and Bourcier, Christophe and Ledoux, Franck},
    year      = {2025},
    month     = {March},
    url       = {https://github.com/LIHPC-Computational-Geometry/validity-first-polycube-labeling},
    booktitle = {International Meshing Roundtable},
    publisher = {SIAM}
}

Hayagriva (for Typst)

mestrallet2025:
    title: Validity-first automatic polycube labeling for CAD models
    author: ["Mestrallet, Sébastien", "Bourcier, Christophe", "Ledoux, Franck"]
    type: article
    date: 2025-03
    url: https://github.com/LIHPC-Computational-Geometry/validity-first-polycube-labeling
    parent:
    - type: proceedings
      title: International Meshing Roundtable
      publisher: SIAM