“Hexahedral mesh re-parameterization from aligned base-complex” by Gao, Deng and Chen

Recently, generating a high quality all-hex mesh of a given volume has gained much attention. However, little, if any, effort has been put into the optimization of the hex-mesh structure, which is equally important to the local element quality of a hex-mesh that may influence the performance and accuracy of subsequent computations. In this paper, we present a first and complete pipeline to optimize the global structure of a hex-mesh. Specifically, we first extract the base-complex of a hex-mesh and study the misalignments among its singularities by adapting the previously introduced hexahedral sheets to the base-complex. Second, we identify the valid removal base-complex sheets from the base-complex that contain misaligned singularities. We then propose an effective algorithm to remove these valid removal sheets in order. Finally, we present a structure-aware optimization strategy to improve the geometric quality of the resulting hex-mesh after fixing the misalignments. Our experimental results demonstrate that our pipeline can significantly reduce the number of components of a variety of hex-meshes generated by state-of-the-art methods, while maintaining high geometric quality.

1. Bazilevs, Y., Beirao Da Veiga, L., Cottrell, J., Hughes, T., and Sangalli, G. 2006. Isogeometric analysis: approximation, stability and error estimates for h-refined meshes. Mathematical Models and Methods in Applied Sciences 16, 07, 1031–1090.Google ScholarCross Ref
2. Bommes, D., Lempfer, T., and Kobbelt, L. 2011. Global structure optimization of quadrilateral meshes. CGF 30, 2, 375–384.Google ScholarCross Ref
3. Bommes, D., Lévy, B., Pietroni, N., Puppo, E., Silva, C., Tarini, M., and Zorin, D. 2013. Quad-mesh generation and processing: A survey. CGF 32, 6, 51–76. Google ScholarDigital Library
4. Borden, M. J., Benzley, S. E., and Shepherd, J. F. 2002. Hexahedral sheet extraction. In Proc. of the 11th International Meshing Roundtable, 147–152.Google Scholar
5. Brewer, M., Diachin, L., Knupp, P., Leurent, T., and Melander, D. 2003. The mesquite mesh quality improvement toolkit. In Proc. of the 12th International Meshing Roundtable, 239–250.Google Scholar
6. Dong, S., Bremer, P.-T., Garland, M., Pascucci, V., and Hart, J. C. 2006. Spectral surface quadrangulation. ACM Trans. Graph. 25, 3 (July), 1057–1066. Google ScholarDigital Library
7. Floater, M. S. 2003. Mean value coordinates. Computer Aided Geometric Design 20, 1, 19–27. Google ScholarDigital Library
8. Gao, X., Huang, J., Li, S., Deng, Z., and Chen, G. 2014. An evaluation of the quality of hexahedral meshes via modal analysis. In 1st Workshop on Structured Meshing: Theory, Applications, and Evaluation.Google Scholar
9. Gregson, J., Sheffer, A., and Zhang, E. 2011. All-hex mesh generation via volumetric polycube deformation. CGF 30, 5, 1407–1416.Google ScholarCross Ref
10. Hacon, D., and Tomei, C. 1989. Tetrahedral decompositions of hexahedral meshes. Eur. J. Comb. 10, 5 (Aug.), 435–443. Google ScholarDigital Library
11. Huang, J., Tong, Y., Wei, H., and Bao, H. 2011. Boundary aligned smooth 3d cross-frame field. ACM Trans. Graph. 30, 6 (Dec.), 143:1–143:8. Google ScholarDigital Library
12. 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, 25:1–25:11. Google ScholarDigital Library
13. Hughes, T. J., Cottrell, J. A., and Bazilevs, Y. 2005. Isogeometric analysis: Cad, finite elements, nurbs, exact geometry, and mesh refinement. Computer Methods in Applied Mechanics and Engineering 194, 4135–4195.Google ScholarCross Ref
14. Jiang, T., Huang, J., Yuanzhen Wang, Y. T., and Bao, H. 2014. Frame field singularity correction for automatic hexahedralization. IEEE TVCG 20, 8 (Aug.), 1189–1199. Google ScholarDigital Library
15. Ju, T., Schaefer, S., and Warren, J. 2005. Mean value coordinates for closed triangular meshes. ACM Trans. Graph. 24, 3 (July), 561–566. Google ScholarDigital Library
16. Leonard, B., Patel, A., and Hirsch, C. 2000. Multigrid acceleration in a 3d navier-stokes solver using unstructured hexahedral meshes with adaptation. In Multigrid Methods VI. Springer, 150–156.Google Scholar
17. Li, B., and Qin, H. 2012. Full component-aware tensor-product trivariate splines of arbitrary topology. Comput. Graph. (SMI 2012) 36, 5 (Aug.), 329–340. Google ScholarDigital Library
18. Li, Y., Liu, Y., Xu, W., Wang, W., and Guo, B. 2012. All-hex meshing using singularity-restricted field. ACM Trans. Graph. 31, 6 (Nov.), 177:1–177:11. Google ScholarDigital Library
19. Li, B., Li, X., Wang, K., and Qin, H. 2013. Surface mesh to volumetric spline conversion with generalized poly-cubes. IEEE TVCG 19, 9, 1539–1551. Google ScholarDigital Library
20. Livesu, M., Vining, N., Sheffer, A., Gregson, J., and Scateni, R. 2013. Polycut: monotone graph-cuts for polycube base-complex construction. ACM Trans. Graph. 32, 6, 171. Google ScholarDigital Library
21. Martin, T., Cohen, E., and Kirby, M. 2008. Volumetric parameterization and trivariate B-spline fitting using harmonic functions. In ACM SPM ’08, 269–280. Google ScholarDigital Library
22. Motooka, Y., Noguchi, S., and Igarashi, H. 2011. Evaluation of hexahedral mesh quality for finite element method in electromagnetics. Materials Science Forum 670, 318–324.Google ScholarCross Ref
23. Myles, A., Pietroni, N., Kovacs, D., and Zorin, D. 2010. Feature-aligned t-meshes. ACM Trans. Graph. 29 (July), 117:1–117:11. Google ScholarDigital Library
24. Nieser, M., Reitebuch, U., and Polthier, K. 2011. Cubecover- parameterization of 3d volumes. CGF 30, 5, 1397–1406.Google ScholarCross Ref
25. Pietroni, N., Tarini, M., and Cignoni, P. 2010. Almost isometric mesh parameterization through abstract domains. IEEE TVCG 16, 4 (July), 621–635. Google ScholarDigital Library
26. Shepherd, J. F., and Johnson, C. R. 2008. Hexahedral mesh generation constraints. Eng. with Comput. 24, 3 (June), 195–213. Google ScholarDigital Library
27. Tarini, M., Puppo, E., Panozzo, D., Pietroni, N., and Cignoni, P. 2011. Simple quad domains for field aligned mesh parametrization. ACM Trans. Graph. 30, 6 (Dec.), 142:1–142:12. Google ScholarDigital Library
28. Tautgesa, T. J., and Knoopb, S. E. 2003. Topology modification of hexahedral meshes using atomic dual-based operations. Algorithms 11, 12.Google Scholar
29. Wada, Y., Shinbori, J., and Kikuchi, M. 2006. Adaptive fem analysis technique using multigrid method for unstructured hexahedral meshes. Key Engineering Materials 306, 565–570.Google ScholarCross Ref
30. Wang, K., Li, X., Li, B., Xu, H., and Qin, H. 2012. Restricted trivariate polycube splines for volumetric data modeling. IEEE TVCG 18, 5, 703–716. Google ScholarDigital Library
31. Yen, J. Y. 1971. Finding the k shortest loopless paths in a network. Management Science 17, 11, 712–716.Google ScholarDigital Library
32. Zhang, Y., Bajaj, C., and Xu, G. 2005. Surface smoothing and quality improvement of quadrilateral/hexahedral meshes with geometric flow. Communications in Numerical Methods in Engineering 25, 1, 1–18.Google ScholarCross Ref