“Practical hex-mesh optimization via edge-cone rectification” by Livesu, Sheffer, Vining and Tarini

The usability of hexahedral meshes depends on the degree to which the shape of their elements deviates from a perfect cube; a single concave, or inverted element makes a mesh unusable. While a range of methods exist for discretizing 3D objects with an initial topologically suitable hex mesh, their output meshes frequently contain poorly shaped and even inverted elements, requiring a further quality optimization step. We introduce a novel framework for optimizing hex-mesh quality capable of generating inversion-free high-quality meshes from such poor initial inputs. We recast hex quality improvement as an optimization of the shape of overlapping cones, or unions, of tetrahedra surrounding every directed edge in the hex mesh, and show the two to be equivalent. We then formulate cone shape optimization as a sequence of convex quadratic optimization problems, where hex convexity is encoded via simple linear inequality constraints. As this solution space may be empty, we therefore present an alternate formulation which allows the solver to proceed even when constraints cannot be satisfied exactly. We iteratively improve mesh element quality by solving at each step a set of local, per-cone, convex constrained optimization problems, followed by a global energy minimization step which reconciles these local solutions. This latter method provides no theoretical guarantees on the solution but produces inversion-free, high quality meshes in practice. We demonstrate the robustness of our framework by optimizing numerous poor quality input meshes generated using a variety of initial meshing methods and producing high-quality inversion-free meshes in each case. We further validate our algorithm by comparing it against previous work, and demonstrate a significant improvement in both worst and average element quality.

1. Aigerman, N., and Lipman, Y. 2013. Injective and bounded distortion mappings in 3d. ACM Trans. Graph. 32, 4. Google ScholarDigital Library
2. Blacker, T. 2000. Meeting the challenge for automated conformal hexahedral meshing. In Proc. International Meshing Roundtable.Google Scholar
3. Brewer, M. L., Diachin, L. F., Knupp, P. M., Leurent, T., and Melander, D. J. 2003. The mesquite mesh quality improvement toolkit. In Proc. International Meshing Roundtable.Google Scholar
4. Cignoni, P., Rocchini, C., and Scopigno, R. 1998. Metro: Measuring Error on Simplified Surfaces. Comput. Graph. Forum 17, 2.Google ScholarCross Ref
5. Erickson, J. 2014. Efficiently hex-meshing things with topology. Discrete and Computational Geometry 52, 3, 427–449. Google ScholarDigital Library
6. Freitag Diachin, L., Knupp, P., Munson, T., and Shontz, S. 2006. A comparison of two optimization methods for mesh quality improvement. Engineering with Computers 22, 2, 61–74. Google ScholarDigital Library
7. Frey, P. J., and George, P. 2007. Mesh Generation: Application to Finite Elements. Google ScholarDigital Library
8. Gregson, J., Sheffer, A., and Zhang, E. 2011. All-hex mesh generation via volumetric polycube deformation. Computer Graphics Forum (Proc. SGP 2011).Google Scholar
9. Gurobi Optimization, 2013. http://www.gurobi.com/.Google Scholar
10. 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), 25:1–25:11. Google ScholarDigital Library
11. Knupp, P. M. 2001. Hexahedral and tetrahedral mesh untangling. Engineering with Computers 17, 3, 261–268.Google ScholarCross Ref
12. Knupp, P. M. 2003. A method for hexahedral mesh shape optimization. Intl. Journal for Numerical Methods in Engineering 58, 2, 319–332.Google ScholarCross Ref
13. Labelle, F., and Shewchuk, J. R. 2007. Isosurface stuffing: fast tetrahedral meshes with good dihedral angles. ACM Trans. Graph. 26. Google ScholarDigital Library
14. Li, Y., Liu, Y., Xu, W., Wang, W., and Guo, B. 2012. All-hex meshing using singularity-restricted field. ACM Trans. Graph. 31, 6. Google ScholarDigital Library
15. 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. Google ScholarDigital Library
16. Marechal, L. 2009. Advances in octree-based all-hexahedral mesh generation: handling sharp features. In Proc. International Meshing Roundtable.Google ScholarCross Ref
17. Miyoshi, K., and Blacker, T. 2000. Hexahedral mesh generation using multi-axis cooper algorithm. In Proc. International Meshing Roundtable, 89–97.Google Scholar
18. Nieser, M., Reitebuch, U., and Polthier, K. 2011. Cube-Cover – Parameterization of 3D Volumes. Computer Graphics Forum.Google Scholar
19. Nocedal, J., and Wright, S. 2006. Numerical Optimization. Springer-Verlag, New York.Google Scholar
20. Owen, S. 2009. A survey of unstructured mesh generation technology. http://www.andrew.cmu.edu/user/sowen/survey/hexsurv.html.Google Scholar
21. Paillé, G.-P., Poulin, P., and Lévy, B. 2013. Fitting polynomial volumes to surface meshes with Voronoï squared distance minimization. Computer Graphics Forum 32, 5, 103–112. Google ScholarDigital Library
22. Pébay, P. P., Thompson, D., Shepherd, J., Knupp, P., Lisle, C., Magnotta, V. A., and Grosland, N. M. 2007. New applications of the verdict library for standardized mesh verification pre, post, and end-to-end processing. In Proc. International Meshing Roundtable. 535–552.Google Scholar
23. Ruiz-Gironés, E., Roca, X., Sarrate, J., Montenegro, R., and Escobar, J. 2014. Simultaneous untangling and smoothing of quadrilateral and hexahedral meshes using an object-oriented framework. Advances in Engineering Software.Google Scholar
24. Ruiz-Gironé S, E., Roca, X., and Sarrate, J. 2014. Optimizing mesh distortion by hierarchical iteration relocation of the nodes on the CAD entities. In Proc. International Meshing Roundtable.Google Scholar
25. Sastry, S. P., and Shontz, S. M. 2009. A comparison of gradient-and hessian-based optimization methods for tetrahedral mesh quality improvement. In Proc. International Meshing Roundtable.Google Scholar
26. Sastry, S., and Shontz, S. 2014. A parallel log-barrier method for mesh quality improvement and untangling. Engineering with Computers 30, 4, 503–515. Google ScholarDigital Library
27. Schneiders, R. 1996. A grid-based algorithm for the generation of hexahedral element meshes. Engineering with Computers 12, 168–177.Google ScholarCross Ref
28. Schüller, C., Kavan, L., Panozzo, D., and Sorkine-Hornung, O. 2013. Locally injective mappings. Computer Graphics Forum (Proc. SGP) 32, 5, 125–135. Google ScholarDigital Library
29. Shepherd, J. F., and Johnson, C. R. 2008. Hexahedral mesh generation constraints. Eng. with Computers 24, 3, 195–213. Google ScholarDigital Library
30. Sorkine, O., and Alexa, M. 2007. As-rigid-as-possible surface modeling. In Proc. SGP, 109–116. Google ScholarDigital Library
31. Sun, L., Zhao, G., and Ma, X. 2012. Quality improvement methods for hexahedral element meshes adaptively generated using grid-based algorithm. Intl. Journal for Numerical Methods in Engineering 89, 6, 726–761.Google ScholarCross Ref
32. Tautges, T. J., Blacker, T., and Mitchell, S. A. 1996. The whisker weaving algorithm: a connectivity-based method for constructing all-hexahedral finite element meshes. Intl. Journal for Numerical Methods in Engineering 39, 19, 3327–3349.Google ScholarCross Ref
33. Vartziotis, D., and Himpel, B. 2014. Efficient and global optimization-based smoothing methods for mixed-volume meshes. In Proc. International Meshing Roundtable. 293–311.Google Scholar
34. Vartziotis, D., and Papadrakakis, M. 2013. Improved GETMe by adaptive mesh smoothing. Computer Assisted Methods in Engineering and Science, 20, 55–71.Google Scholar
35. Wilson, T., Sarrate, J., Roca, X., Montenegro, R., and Escobar, J. 2012. Untangling and smoothing of quadrilateral and hexahedral meshes. In Eighth Intl. Conference on Engineering Computational Technology.Google Scholar
36. Wilson, T., 2011. Simultaneous untangling and smoothing of hexahedral meshes.Google Scholar
37. Zhang, Y., Bajaj, C., and Xu, G. 2009. 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