“Optimal voronoi tessellations with hessian-based anisotropy” by Budninskiy, Liu, Goes, Tong, Alliez, et al. … – ACM SIGGRAPH HISTORY ARCHIVES

“Optimal voronoi tessellations with hessian-based anisotropy” by Budninskiy, Liu, Goes, Tong, Alliez, et al. …

  • 2016 SA Technical Papers_Budninskiy_Optimal Voronoi Tessellations with Hessian-based Anisotropy

Conference:


Type(s):


Title:

    Optimal voronoi tessellations with hessian-based anisotropy

Session/Category Title:   Tessellations

Presenter(s)/Author(s):


Abstract:


    This paper presents a variational method to generate cell complexes with local anisotropy conforming to the Hessian of any given convex function and for any given local mesh density. Our formulation builds upon approximation theory to offer an anisotropic extension of Centroidal Voronoi Tessellations which can be seen as a dual form of Optimal Delaunay Triangulation. We thus refer to the resulting anisotropic polytopal meshes as Optimal Voronoi Tessellations. Our approach sharply contrasts with previous anisotropic versions of Voronoi diagrams as it employs first-type Bregman diagrams, a generalization of power diagrams where sites are augmented with not only a scalar-valued weight but also a vector-valued shift. As such, our OVT meshes contain only convex cells with straight edges, and admit an embedded dual triangulation that is combinatorially-regular. We show the effectiveness of our technique using off-the-shelf computational geometry libraries.

References:


    1. Alliez, P., Cohen-Steiner, D., Yvinec, M., and Desbrun, M. 2005. Variational tetrahedral meshing. In ACM SIGGRAPH, vol. 24(3), 617–625.
    2. App, A., and Reif, U. 2010. Piecewise linear orthogonal approximation. SIAM J. Num. Anal. 48, 3, 840–856.
    3. Aurenhammer, F. 1987. A criterion for the affine equivalence of cell complexes in Rd and convex polyhedra in Rd+1. Disc. & Comput. Geom. 2, 1, 49–64.
    4. Boissonnat, J.-D., Cohen-Steiner, D., and Yvinec, M. 2006. Comparison of algorithms for anisotropic meshing and adaptive refinement. Tech. Rep. ACS-TR-362603, INRIA.
    5. Boissonnat, J.-D., Wormser, C., and Yvinec, M. 2008. Anisotropic diagrams: Labelle-Shewchuk approach revisited. Theor. Comput. Sci. 408, 2–3, 163–173.
    6. Boissonnat, J.-D., Nielsen, F., and Nock, R. 2010. Bregman Voronoi diagrams. Disc. & Comput. Geom. 44, 2, 281–307.
    7. Boissonnat, J.-D., Shi, K.-L., Tournois, J., and Yvinec, M. 2014. Anisotropic Delaunay meshes of surfaces. ACM Trans. Graph..
    8. Bossen, Frank, J., and Heckbert, P. S. 1996. A pliant method for anisotropic mesh generation. In Int. Meshing Roundtable, 63–76.
    9. CGAL. 2016. CGAL 4.8 User and Reference Manual. CGAL Editorial Board, http://www.cgal.org.
    10. Chen, L., and Holst, M. J. 2011. Efficient mesh optimization schemes based on Optimal Delaunay Triangulations. Comput. Methods Appl. Mech. Engrg. 200, 967–984. Cross Ref
    11. Chen, L., and Xu, J. 2004. Optimal Delaunay triangulations. J. of Comp. Mathematics 22, 2, 299–308.
    12. Chen, L., Sun, P., and Xu, J. 2007. Optimal anisotropic simplicial meshes for minimizing interpolation errors in Lp-norm. Math. of Comput. 76, 257, 179–204.
    13. Chen, Z., Wang, W., Lvy, B., Liu, L., and Sun, F. 2014. Revisiting Optimal Delaunay Triangulation for 3D graded mesh generation. SIAM J. Sci. Comput. 36, 3, 930–954. Cross Ref
    14. Chen, L. 2004. Mesh smoothing schemes based on Optimal Delaunay Triangulations. In Int. Meshing Roundtable, 109–120.
    15. Cheng, S.-W., Dey, T. K., Ramos, E. A., and Wenger, R. 2006. Anisotropic surface meshing. In Symp. Disc. Alg., 202–211.
    16. Dassi, F., Si, H., Perotto, S., and Streckenbach, T. 2015. Anisotropic finite element mesh adaptation via higher dimensional embedding. Procedia Engineering 124, 265–277. Cross Ref
    17. D’Azevedo, E. F., and Simpson, R. B. 1989. On optimal interpolation triangle incidences. SIAM J. Sci. Stat. Comput. 10, 6, 1063–1075.
    18. de Goes, F., Breeden, K., Ostromoukhov, V., and Desbrun, M. 2012. Blue noise through optimal transport. ACM Trans. Graph. 31, 6, Art. 171.
    19. de Goes, F., Alliez, P., Owhadi, H., and Desbrun, M. 2013. On the equilibrium of simplicial masonry structures. ACM Trans. Graph. 32, 4, Art. 93.
    20. de Goes, F., Wallez, C., Huang, J., Pavlov, D., and Desbrun, M. 2015. Power particles: An incompressible fluid solver based on power diagrams. ACM Trans. Graph. 34, 4, Art. 50.
    21. Du, Q., and Emelianenko, M. 2006. Acceleration schemes for computing centroidal Voronoi tessellations. Numer. Linear Algebr. 13, 2–3, 173–192. Cross Ref
    22. Du, Q., and Wang, D. 2005. Anisotropic centroidal Voronoi tessellations and their applications. SIAM J. Sci. Comp. 26, 3, 737–761.
    23. Du, Q., Faber, V., and Gunzburger, M. 1999. Centroidal Voronoi tesselations. SIAM Review 41, 4, 637–676.
    24. Frey, P., and Alauzet, F. 2004. Anisotropic metrics for mesh adaptation. In Comput. Fluid Solid Mech., K. Bathe, Ed., 24–28.
    25. Fu, X.-M., Liu, Y., Snyder, J., and Guo, B. 2014. Anisotropic simplicial meshing using local convex functions. ACM Trans. Graph. 33, 6, Art. 182.
    26. Gao, Z., Yu, Z., and Holst, M. 2012. Quality tetrahedral mesh smoothing via boundary-optimized Delaunay triangulation. Comput. Aided Geom. Design 29, 9, 707–721.
    27. George, P., Frey, P., and Alauzet, F. 2002. Automatic generation of 3D adapted meshes. World Congress on Comput. Mech..
    28. Kuzmin, D. 2010. A Guide to Numerical Methods for Transport Equations. University of Erlangen-Nuremberg.
    29. Labelle, F., and Shewchuk, J. R. 2003. Anisotropic Voronoi diagrams and guaranteed-quality anisotropic mesh generation. In Symp. Comp. Geom., 191–200.
    30. Lee, C. 1991. Regular triangulations of convex polytopes. Applied Geom. & Disc. Math. 4, 443–456.
    31. Lévy, B., and Bonneel, N. 2013. Variational anisotropic surface meshing with Voronoi parallel linear enumeration. In Int. Meshing Roundtable. 349–366.
    32. Lévy, B., and Liu, Y. 2010. Lp Centroidal Voronoi Tessellation and its applications. ACM Trans. Graph. 29, 4, Art. 119.
    33. Liu, Y., Wang, W., Lévy, B., Sun, F., Yan, D.-M., Lu, L., and Yang, C. 2009. On Centroidal Voronoi Tessellation – energy smoothness and fast computation. ACM Trans. Graph. 28, 4, Art. 101.
    34. Liu, Y., Pan, H., Snyder, J., Wang, W., and Guo, B. 2013. Computing self-supporting surfaces by regular triangulation. ACM Trans. Graph. 32, 4, Art. 92.
    35. Loseille, A., and Alauzet, F. 2009. Optimal 3D highly anisotropic mesh adaptation based on the continuous mesh framework. In Int. Meshing Roundtable. 575–594.
    36. Loseille, A., and Alauzet, F. 2011. Continuous mesh framework, Part I: Well-posed continuous interpolation error. SIAM J. Num. Anal. 49, 1, 38–60.
    37. Marsden, J. E., and Tromba, A. 2003. Vector Calculus, 5th ed. W. H. Freeman.
    38. Memari, P., Mullen, P., and Desbrun, M. 2012. Parametrization of generalized primal-dual triangulations. In Int. Meshing Roundtable. 237–253.
    39. Mirebeau, J.-M., and Cohen, A. 2011. Greedy bisection generates optimally adapted triangulations. Math. Comp. 81, 811–837. Cross Ref
    40. Mullen, P., Memari, P., de Goes, F., and Desbrun, M. 2011. HOT: Hodge-optimized triangulations. ACM Trans. Graph. 30, 4, Art. 103.
    41. Nadler, E. 1986. Piecewise linear best L2 approximation on triangulations. In Approx. Theory V, C. K. Chui, L. L. Schumaker, and J. D. Ward, Eds. Academic Press, 499–502.
    42. Nielsen, F., and Nock, R. 2011. Skew Jensen-Bregman Voronoi diagrams. In Transactions on Computational Science XIV, Special Issue on Voronoi Diagrams and Delaunay Triangulation, M. L. Gavrilova, C. J. K. Tan, and M. A. Mostafavi, Eds. Springer, 102–128.
    43. Richter, R., and Alexa, M. 2015. Mahalanobis centroidal Voronoi tessellations. Comp. & Graph. 46, 48–54.
    44. Rycroft, C. H. 2009. Voro++: A three-dimensional Voronoi cell library in C++. Chaos: An Interdisciplinary Journal of Nonlinear Science 19, 4.
    45. Shewchuk, J. 1998. Tetrahedral mesh generation by Delaunay refinement. In Symp. on Comp. Geometry, 86–95.
    46. Sun, F., Choi, Y.-K., Wang, W., Yan, D.-M., Liu, Y., and Lévy, B. 2011. Obtuse triangle suppression in anisotropic meshes. Comput. Aided Geom. Design 28, 9, 537–548.
    47. Tournois, J., Wormser, C., Alliez, P., and Desbrun, M. 2009. Interleaving Delaunay refinement and optimization for practical isotropic tetrahedron mesh generation. ACM Trans. Graph. 28, 3, Art. 75.
    48. Valette, S., Chassery, J.-M., and Prost, R. 2008. Generic remeshing of 3D triangular meshes with metric-dependent discrete Voronoi diagrams. IEEE Trans. Vis. Comp. Graph. 14, 2, 369–381.
    49. Yan, D.-M., Wang, W., Lévy, B., and Liu, Y. 2013. Efficient computation of clipped Voronoi diagram. Computer-Aided Design 45, 4, 843 — 852.
    50. 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. 32, 4, Art. 99.

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