HexEx: robust hexahedral mesh extraction

Abstract

State-of-the-art hex meshing algorithms consist of three steps: Frame-field design, parametrization generation, and mesh extraction. However, while the first two steps are usually discussed in detail, the last step is often not well studied. In this paper, we fully concentrate on reliable mesh extraction.

Parametrization methods employ computationally expensive countermeasures to avoid mapping input tetrahedra to degenerate or flipped tetrahedra in the parameter domain because such a parametrization does not define a proper hexahedral mesh. Nevertheless, there is no known technique that can guarantee the complete absence of such artifacts.

We tackle this problem from the other side by developing a mesh extraction algorithm which is extremely robust against typical imperfections in the parametrization. First, a sanitization process cleans up numerical inconsistencies of the parameter values caused by limited precision solvers and floating-point number representation. On the sanitized parametrization, we extract vertices and so-called darts based on intersections of the integer grid with the parametric image of the tetrahedral mesh. The darts are reliably interconnected by tracing within the parametrization and thus define the topology of the hexahedral mesh. In a postprocessing step, we let certain pairs of darts cancel each other, counteracting the effect of flipped regions of the parametrization. With this strategy, our algorithm is able to robustly extract hexahedral meshes from imperfect parametrizations which previously would have been considered defective. The algorithm will be published as an open source library [Lyon et al. 2016].

References

1. Bommes, D., Campen, M., Ebke, H.-C., Alliez, P., and Kobbelt, L. 2013. Integer-grid maps for reliable quad meshing. ACM Transactions on Graphics 32, 4 (July).
2. Ebke, H.-C., Bommes, D., Campen, M., and Kobbelt, L. 2013. QEx: Robust quad mesh extraction. ACM Transactions on Graphics 32, 6 (Nov.).
3. Ebke, H.-C., Campen, M., Bommes, D., and Kobbelt, L. 2014. Level-of-detail quad meshing. ACM Transactions on Graphics 33, 6 (Dec).
4. Gregson, J., Sheffer, A., and Zhang, E. 2011. All-hex mesh generation via volumetric polycube deformation. Computer Graphics Forum 30, 5.
5. Huang, J., Jiang, T., Shi, Z., Tong, Y., Bao, H., and Desbrun, M. 2014. l1-based construction of polycube maps from complex shapes. ACM Trans. Graph. 33, 3 (June).
6. Jiang, T., Huang, J., Wang, Y., Tong, Y., and Bao, H. 2014. Frame field singularity correction for automatic hexahedralization. IEEE Transactions on Visualization and Computer Graphics 20, 8.
7. Kraemer, P., Untereiner, L., Jund, T., Thery, S., and Cazier, D. 2014. CGoGN: n-dimensional meshes with combinatorial maps. In Proceedings of the 22nd International Meshing Roundtable.
8. Kremer, M., Bommes, D., and Kobbelt, L. 2012. OpenVolumeMesh -- a versatile index-based data structure for 3d polytopal complexes. In Proceedings of the 21st International Meshing Roundtable.
9. Li, Y., Liu, Y., Xu, W., Wang, W., and Guo, B. 2012. All-hex meshing using singularity-restricted field. ACM Transactions on Graphics 31, 6 (Nov.).
10. Livesu, M., Vining, N., Sheffer, A., Gregson, J., and Scateni, R. 2013. PolyCut: Monotone graph-cuts for polycube base-complex construction. Transactions on Graphics (Proc. SIGGRAPH ASIA 2013) 32, 6.
11. Livesu, M., Sheffer, A., Vining, N., and Tarini, M. 2015. Practical hex-mesh optimization via edge-cone rectification. ACM Trans. Graph. 34, 4 (July).
12. Lyon, M., Bommes, D., and Kobbelt, L., 2016. libHexEx: a robust hexahedral mesh extraction library. http://www.graphics.rwth-aachen.de/software/libHexEx.
13. Möbius, J., and Kobbelt, L. 2012. OpenFlipper: An open source geometry processing and rendering framework. In Curves and Surfaces, vol. 6920 of Lecture Notes in Computer Science.
14. Nieser, M., Reitebuch, U., and Polthier, K. 2011. Cube-Cover - parameterization of 3D volumes. Comp. Graph. Forum.
15. Ray, N., and Sokolov, D. 2015. On smooth 3D frame field design. Computing Research Repository.
16. Shepherd, J. F., and Johnson, C. R. 2008. Hexahedral mesh generation constraints. Engineering with Computers 24, 3.
17. Shewchuk, J. R. 1997. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18, 3 (Oct.).
18. Shimada, K. 2006. Current trends and issues in automatic mesh generation. Computer-Aided Design & Applications 3, 6.

Index Terms

• Applied computing

  • Physical sciences and engineering

    • Engineering

      • Computer-aided design

• Computing methodologies

  • Computer graphics

    • Animation

      • Physical simulation

    • Shape modeling