“HexEx: robust hexahedral mesh extraction”
Conference:
Type:
Title:
- HexEx: robust hexahedral mesh extraction
Session/Category Title: MESHES
Presenter(s)/Author(s):
Moderator(s):
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). Google ScholarDigital Library
2. Ebke, H.-C., Bommes, D., Campen, M., and Kobbelt, L. 2013. QEx: Robust quad mesh extraction. ACM Transactions on Graphics 32, 6 (Nov.). Google ScholarDigital Library
3. Ebke, H.-C., Campen, M., Bommes, D., and Kobbelt, L. 2014. Level-of-detail quad meshing. ACM Transactions on Graphics 33, 6 (Dec). Google ScholarDigital Library
4. Gregson, J., Sheffer, A., and Zhang, E. 2011. All-hex mesh generation via volumetric polycube deformation. Computer Graphics Forum 30, 5.Google ScholarCross Ref
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). Google ScholarDigital Library
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. Google ScholarDigital Library
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.Google Scholar
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.Google Scholar
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.). Google ScholarDigital Library
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. Google ScholarDigital Library
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). Google ScholarDigital Library
12. Lyon, M., Bommes, D., and Kobbelt, L., 2016. libHexEx: a robust hexahedral mesh extraction library. http://www.graphics.rwth-aachen.de/software/libHexEx.Google Scholar
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. Google ScholarDigital Library
14. Nieser, M., Reitebuch, U., and Polthier, K. 2011. Cube-Cover – parameterization of 3D volumes. Comp. Graph. Forum.Google Scholar
15. Ray, N., and Sokolov, D. 2015. On smooth 3D frame field design. Computing Research Repository.Google Scholar
16. Shepherd, J. F., and Johnson, C. R. 2008. Hexahedral mesh generation constraints. Engineering with Computers 24, 3.Google ScholarDigital Library
17. Shewchuk, J. R. 1997. Adaptive precision floating-point arithmetic and fast robust geometric predicates. Discrete & Computational Geometry 18, 3 (Oct.).Google Scholar
18. Shimada, K. 2006. Current trends and issues in automatic mesh generation. Computer-Aided Design & Applications 3, 6.Google ScholarCross Ref
