Robust Hex-Dominant Mesh Generation using Field-Guided Polyhedral Agglomeration

In ACM Transactions on Graphics (Proceedings of SIGGRAPH 2017)

The po­s­i­tions of the ver­tices of an in­put tet­ra­hed­ral mesh (left, t = 0) are morph­ed (t = 1) in­to a hex-dom­in­ant mesh (right), guided by an ori­ent­a­tion and a po­s­i­tion field. The sin­gu­lar­it­ies of both fields are shown in the middle im­age, in red and yel­low re­spect­ively.


We pro­pose a ro­bust and ef­fi­cient field-aligned volu­met­ric mesh­ing al­gorithm that pro­duces hex-dom­in­ant meshes, i.e. meshes that are pre­dom­in­antly com­posed of hexa­hed­ral ele­ments while con­tain­ing a small num­ber of ir­reg­u­lar poly­hedra. The lat­ter are placed ac­cord­ing to the sin­gu­lar­it­ies of two op­tim­ized guid­ing fields, which al­lows our meth­od to gen­er­ate meshes with an ex­cep­tion­ally high amount of iso­tropy. The field design phase of our meth­od re­lies on a com­pact qua­ternion­ic rep­res­ent­a­tion of volu­met­ric octa-fields and a cor­res­pond­ing op­tim­iz­a­tion that ex­pli­citly mod­els the dis­crete match­ings between neigh­bor­ing ele­ments. This op­tim­iz­a­tion nat­ur­ally sup­ports align­ment con­straints and scales to very large data­sets. We also pro­pose a nov­el ex­trac­tion tech­nique that uses field-guided mesh sim­pli­fic­a­tion to con­vert the op­tim­ized fields in­to a hex-dom­in­ant out­put mesh. Each sim­pli­fic­a­tion op­er­a­tion main­tains to­po­lo­gic­al valid­ity as an in­vari­ant, en­sur­ing man­i­fold out­put. These steps eas­ily gen­er­al­ize to oth­er di­men­sions or rep­res­ent­a­tions, and we show how they can be an as­set in ex­ist­ing 2D sur­face mesh­ing tech­niques. Our meth­od can auto­mat­ic­ally and ro­bustly con­vert any tet­ra­hed­ral mesh in­to an iso­trop­ic hex-dom­in­ant mesh and (with minor modi­fic­a­tions) can also con­vert any tri­angle mesh in­to a cor­res­pond­ing iso­trop­ic quad-dom­in­ant mesh, pre­serving its genus, num­ber of holes, and man­i­fold­ness. We demon­strate the be­ne­fits of our al­gorithm on a large col­lec­tion of shapes provided in the sup­ple­ment­al ma­ter­i­al along with all gen­er­ated res­ults.

Text citation

Xifeng Gao, Wenzel Jakob, Marco Tarini, and Daniele Panozzo. 2017. Robust Hex-Dominant Mesh Generation using Field-Guided Polyhedral Agglomeration. In ACM Transactions on Graphics (Proceedings of SIGGRAPH) 36(4).

    author = {Xifeng Gao and Wenzel Jakob and Marco Tarini and Daniele Panozzo},
    title = {Robust Hex-Dominant Mesh Generation using Field-Guided Polyhedral Agglomeration},
    journal = {ACM Transactions on Graphics (Proceedings of SIGGRAPH)},
    volume = {36},
    number = {4},
    year = {2017},
    month = jul,
    doi = {10.1145/3072959.3073676}