“Anisotropic simplicial meshing using local convex functions” by Fu, Liu, Snyder and Guo – ACM SIGGRAPH HISTORY ARCHIVES

“Anisotropic simplicial meshing using local convex functions” by Fu, Liu, Snyder and Guo

  • 2014 SA Technical Papers Fu_Anisotropic Simplicial Meshing Using Local Convex Functions

Conference:


Type(s):


Title:

    Anisotropic simplicial meshing using local convex functions

Session/Category Title:   Meshing Surface, and Meshing

Presenter(s)/Author(s):


Abstract:


    We present a novel method to generate high-quality simplicial meshes with specified anisotropy. Given a surface or volumetric domain equipped with a Riemannian metric that encodes the desired anisotropy, we transform the problem to one of functional approximation. We construct a convex function over each mesh simplex whose Hessian locally matches the Riemannian metric, and iteratively adapt vertex positions and mesh connectivity to minimize the difference between the target convex functions and their piecewise-linear interpolation over the mesh. Our method generalizes optimal Delaunay triangulation and leads to a simple and efficient algorithm. We demonstrate its quality and speed compared to state-of-the-art methods on a variety of domains and metrics.

References:


    1. Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational tetrahedral meshing. ACM Trans. Graph. (SIGGRAPH) 24, 3, 617–625.
    2. Amari, S.-I., and Armstrong, J. 2014. Curvature of Hessian mnifolds. Differential Geom. Appl., 33, 1–12.Cross Ref
    3. Boissonnat, J.-D., Cohen-Steiner, D., and Yvinec, M. 2008. Comparison of algorithms for anisotropic meshing and adaptive refinement. Tech. rep., INRIA. ACS-TR-362603.
    4. Boissonnat, J.-D., Wormser, C., and Yvinec, M. 2008. Locally uniform anisotropic meshing. In SOCG, 270–277.
    5. Boissonnat, J.-D., Wormser, C., and Yvinec, M. 2011. Anisotropic Delaunay mesh generation. Tech. rep., INRIA. INRIA-00615486.
    6. Boissonnat, J.-D., Shi, K.-L., Tournois, J., and Yvinec, M. 2014. Anisotropic Delaunay meshes of surfaces. ACM Trans. Graph., to appear.
    7. Canas, G. D., and Gortler, S. J. 2011. Orphan-free anisotropic Voronoi diagrams. Discrete Comput. Geom. 46, 3, 526–541.
    8. Chen, L., and Holst, M. 2011. Efficient mesh optimization schemes based on optimal Delaunay triangulations. Comput. Methods in Appl. Mech. Eng. 200, 912, 967–984.
    9. Chen, L., and Xu, J. 2004. Optimal Delaunay triangulations. J. Comput. Math. 22, 299–308.
    10. Chen, L., Sun, P., and Xu, J. 2007. Optimal anisotropic meshes for minimizing interpolation errors in Lp-norm. Math. Comp. 76, 179–204.Cross Ref
    11. Chen, L. 2004. Mesh smoothing schemes based on optimal Delaunay triangulations. In Int. Meshing Roundtable, 109–120.
    12. Cheng, S.-W., Dey, T. K., Ramos, E. A., and Wenger, R. 2006. Anisotropic surface meshing. In SODA, 202–211.
    13. Clark, B., Ray, N., and Jiao, X. 2012. Surface mesh optimization, adaption, and untangling with high-order accuracy. In Int. Meshing Roundtable. 385–402.
    14. Desbrun, M., Donaldson, R. D., and Owhadi, H. 2013. Modeling across scales: discrete geometric structures in homogenization and inverse homogenization. In Multiscale Analysis and Nonlinear Dynamics, 19–64.
    15. Dobrzynski, C., and Frey, P. 2008. Anisotropic Delaunay mesh adaptation for unsteady simulations. In Int. Meshing Roundtable, 177–194.
    16. Du, Q., and Wang, D. 2005. Anisotropic centroidal Voronoi tessellations and their applications. SIAM J. Sci. Comput. 26, 3, 737–761.
    17. Frey, P., and George, P.-L. 2008. Mesh Generation: Application to finite elements, 2 ed. Wiley-ISTE.
    18. Genz, A., and Cools, R. 2003. An adaptive numerical cubature algorithm for simplices. ACM Trans. Math. Softw. 29, 3, 297–308.
    19. Goes, F. D., Memari, P., Mullen, P., and Desbrun, M. 2014. Weighted triangulations for geometry processing. ACM Trans. Graph. 33, 3, 28:1–28:13.
    20. Hecht, F., 1998. BAMG: Bidimensional anisotropic mesh generator. http://www.ann.jussieu.fr/hecht/ftp/bamg.
    21. Jiao, X., Colombi, A., Ni, X., and Hart, J. 2010. Anisotropic mesh adaptation for evolving triangulated surfaces. Eng. with Comput. 26, 4, 363–376.
    22. Klingner, B. M., and Shewchuk, J. R. 2007. Agressive tetrahedral mesh improvement. In Int. Meshing Roundtable, 3–23.
    23. Labelle, F., and Shewchuk, J. R. 2003. Anisotropic Voronoi diagrams and guaranteed-quality anisotropic mesh generation. In SOCG, 191–200.
    24. Lévy, B., and Bonneel, N. 2012. Variational anisotropic surface meshing with Voronoi parallel linear enumeration. In Int. Meshing Roundtable, 349–366.
    25. Lévy, B., and Liu, Y. 2010. Lp centroidal Voronoi tessellation and its applications. ACM Trans. Graph. (SIGGRAPH) 29, 4, 119:1–119:11.
    26. Li, Y., Liu, Y., and Wang, W. 2014. Planar hexagonal meshing for architecture. IEEE. T. Vis. Comput. Gr., to appear.
    27. Liu, Y., Pan, H., Snyder, J., Wang, W., and Guo, B. 2013. Computing self-supporting surfaces by regular triangulation. ACM Trans. Graph. (SIGGRAPH) 32, 4, 92:1–92:10.
    28. Mullen, P., Memari, P., de Goes, F., and Desbrun, M. 2011. HOT: Hodge-optimized triangulations. ACM Trans. Graph. (SIGGRAPH) 30, 4, 103:1–103:12.
    29. Panozzo, D., Puppo, E., Tarini, M., and Sorkine-Hornung, O. 2014. Frame fields: anisotropic and non-orthogonal cross fields. ACM Trans. Graph. (SIGGRAPH) 33, 4, 134:1–134:11.
    30. Persson, P.-O., and Strang, G. 2004. A simple mesh generator in MATLAB. SIAM Rev. 46, 329–345.
    31. Rusinkiewicz, S. 2004. Estimating curvatures and their derivatives on triangle meshes. In 3DPVT, 486–493.
    32. Shewchuk, J. R., 2002. What is a good linear finite element? Interpolation, conditioning, anisotropy, and quality measures.
    33. Shimada, K., Yamada, A., and Itoh, T. 2000. Anisotropic triangulation of parametric surfaces via close packing of ellipsoids. Int. J. Comput. Geom. Ap. 10, 4, 417–440.Cross Ref
    34. Thompson, J. F., Soni, B. K., and Weatherill, N. P., Eds. 1998. Handbook of Grid Generation. Wiley-ISTE.
    35. Tournois, J., Srinivasan, R., and Alliez, P. 2009. Perturbing slivers in 3D Delaunay meshes. In Int. Meshing Roundtable, 157–173.
    36. Tournois, J., Wormser, C., Alliez, P., and Desbrun, M. 2009. Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation. ACM Trans. Graph. (SIGGRAPH) 28, 3, 75:1–75:9.
    37. Valette, S., Chassery, J.-M., and Prost, R. 2008. Generic remeshing of 3D triangular meshes with metric-dependent discrete Voronoi diagrams. IEEE. T. Vis. Comput. Gr. 14, 2, 369–381.
    38. Yan, D.-M., Lévy, B., Liu, Y., Sun, F., and Wang, W. 2009. Isotropic remeshing with fast and exact computation of restricted Voronoi diagram. Comput. Graph. FORUM 28, 5, 1445–1454.
    39. Zhong, Z., Guo, X., Wang, W., Lévy, B., Sun, F., Liu, Y., and Mao, W. 2013. Particle-based anisotropic surface meshing. ACM Trans. Graph. (SIGGRAPH) 32, 4, 99:1–99:14.
    40. Zienkiewicz, O. C., Taylor, R. L., and Zhu, J. 2005. The Finite Element Method: Its Basis and Fundamentals, 6 ed. Butterworth-Heinemann.

ACM Digital Library Publication:


Overview Page:


Submit a story:

If you would like to submit a story about this presentation, please contact us: historyarchives@siggraph.org