“Particle-based anisotropic surface meshing” by Zhong, Guo, Wang, Levy, Sun, et al. …
Conference:
Type(s):
Title:
- Particle-based anisotropic surface meshing
Session/Category Title: Quads & Meshing
Presenter(s)/Author(s):
Moderator(s):
Abstract:
This paper introduces a particle-based approach for anisotropic surface meshing. Given an input polygonal mesh endowed with a Riemannian metric and a specified number of vertices, the method generates a metric-adapted mesh. The main idea consists of mapping the anisotropic space into a higher dimensional isotropic one, called “embedding space”. The vertices of the mesh are generated by uniformly sampling the surface in this higher dimensional embedding space, and the sampling is further regularized by optimizing an energy function with a quasi-Newton algorithm. All the computations can be re-expressed in terms of the dot product in the embedding space, and the Jacobian matrices of the mappings that connect different spaces. This transform makes it unnecessary to explicitly represent the coordinates in the embedding space, and also provides all necessary expressions of energy and forces for efficient computations. Through energy optimization, it naturally leads to the desired anisotropic particle distributions in the original space. The triangles are then generated by computing the Restricted Anisotropic Voronoi Diagram and its dual Delaunay triangulation. We compare our results qualitatively and quantitatively with the state-of-the-art in anisotropic surface meshing on several examples, using the standard measurement criteria.
References:
1. Alauzet, F., and Loseille, A. 2010. High-order sonic boom modeling based on adaptive methods. Journal of Computational Physics 229, 3, 561–593. Google ScholarDigital Library
2. Alliez, P., Cohen-Steiner, D., Devillers, O., Lévy, B., and Desbrun, M. 2003. Anisotropic polygonal remeshing. ACM Transactions on Graphics 22, 3, 485–493. Google ScholarDigital Library
3. Boissonnat, J., Wormser, C., and Yvinec, M. 2008. Anisotropic diagrams: Labelle Shewchuk approach revisited. Theoretical Computer Science 408, 2–3, 163–173. Google ScholarDigital Library
4. Boissonnat, J., Wormser, C., and Yvinec, M. 2008. Locally uniform anisotropic meshing. In Proceedings of the 24th annual symposium on Computational geometry, SCG ’08, 270–277. Google ScholarDigital Library
5. Boissonnat, J., Wormser, C., and Yvinec, M. 2011. Anisotropic Delaunay mesh generation. Research Report RR-7712.Google Scholar
6. Boissonnat, J.-D., Dyer, R., and Ghosh, A. 2012. Stability of Delaunay-type structures for manifolds. In Symposium on Computational Geometry, 229–238. Google ScholarDigital Library
7. Borouchaki, H., George, P. L., Hecht, F., Laug, P., and Saltel, E. 1997. Delaunay mesh generation governed by metric specifications. part I. algorithms. Finite Elements in Analysis and Design 25, 1–2, 61–83. Google ScholarDigital Library
8. Borouchaki, H., George, P. L., and Mohammadi, B. 1997. Delaunay mesh generation governed by metric specifications. part II. applications. Finite Elements in Analysis and Design 25, 1–2, 85–109. Google ScholarDigital Library
9. Borsuk, K. 1948. On the imbedding of systems of compacta in simplicial complexes. Fund. Math 35, 217–234.Google ScholarCross Ref
10. Bossen, F., and Heckbert, P. 1996. A pliant method for anisotropic mesh generation. In 5th International Meshing Roundtable, 63–76.Google Scholar
11. Bronson, J. R., Levine, J. A., and Whitaker, R. T. 2012. Particle systems for adaptive, isotropic meshing of CAD models. Engineering with Computers 28, 4, 331–344.Google ScholarDigital Library
12. Cañas, G. D., and Gortler, S. J. 2006. Surface remeshing in arbitrary codimensions. Visual Computer 22, 9, 885–895. Google ScholarDigital Library
13. D’Azevedo, E. F. 1991. Optimal triangular mesh generation by coordinate transformation. SIAM Journal on Scientific and Statistical Computing 12, 4, 755–786. Google ScholarDigital Library
14. Dey, T. K., and Ray, T. 2010. Polygonal surface remeshing with Delaunay refinement. Engineering with Computers 26, 3, 289–301. Google ScholarDigital Library
15. Dobrzynski, C., and Frey, P. 2008. Anisotropic Delaunay mesh adaptation for unsteady simulations. In 17th International Meshing Roundtable, 177–194.Google Scholar
16. Du, Q., and Wang, D. 2005. Anisotropic centroidal Voronoi tessellations and their applications. SIAM Journal on Scientific Computing 26, 3, 737–761. Google ScholarDigital Library
17. Du, Q., Faber, V., and Gunzburger, M. 1999. Centroidal Voronoi tessellations: Applications and algorithms. SIAM Review 41, 4, 637–676. Google ScholarDigital Library
18. Du, Q., Gunzburger, M. D., and Ju, L. 2003. Constrained centroidal Voronoi tessellations for surfaces. SIAM Journal on Scientific Computing 24, 5, 1488–1506. Google ScholarDigital Library
19. Edelsbrunner, H., and Shah, N. R. 1994. Triangulating topological spaces. In Symposium on Computational Geometry, 285–292. Google ScholarDigital Library
20. Fattal, R. 2011. Blue-noise point sampling using kernel density model. ACM Transactions on Graphics 30, 4, 48:1–48:12. Google ScholarDigital Library
21. Freidlin, M. 1968. On the factorization of non-negative definite matrices. Theory of Probability and Its Applications 13, 2, 354–356.Google ScholarCross Ref
22. Frey, P. J., and Borouchaki, H. 1997. Surface mesh evaluation. In 6th International Meshing Roundtable, 363–373.Google Scholar
23. Heckbert, P. S., and Garland, M. 1999. Optimal triangulation and quadric-based surface simplification. Computational Geometry 14, 1–3, 49–65. Google ScholarDigital Library
24. Horn, R. A., and Johnson, C. R. 1985. Matrix Analysis. Cambridge University Press. Google ScholarDigital Library
25. Kovacs, D., Myles, A., and Zorin, D. 2010. Anisotropic quadrangulation. In Proceedings of the 14th ACM Symposium on Solid and Physical Modeling, SPM ’10, 137–146. Google ScholarDigital Library
26. Kuiper, N. H. 1955. On C1-isometric embeddings I. In Proc. Nederl. Akad. Wetensch. Ser. A, 545–556.Google Scholar
27. Labelle, F., and Shewchuk, J. R. 2003. Anisotropic Voronoi diagrams and guaranteed-quality anisotropic mesh generation. In Proceedings of the 19th Annual Symposium on Computational Geometry, ACM, 191–200. Google ScholarDigital Library
28. Leibon, G., and Letscher, D. 2000. Delaunay triangulations and Voronoi diagrams for Riemannian manifolds. In Proceedings of the Sixteenth Annual Symposium on Computational Geometry, SCG ’00, 341–349. Google ScholarDigital Library
29. Lévy, B., and Bonneel, N. 2012. Variational anisotropic surface meshing with Voronoi parallel linear enumeration. In 21st International Meshing Roundtable, 349–366.Google Scholar
30. Lévy, B., and Liu, Y. 2010. Lp centroidal Voronoi tessellation and its applications. ACM Transactions on Graphics 29, 4, 119:1–119:11. Google ScholarDigital Library
31. Li, H., Wei, L., Sander, P. V., and Fu, C. 2010. Anisotropic blue noise sampling. ACM Transactions on Graphics 29, 6, 167:1–167:12. Google ScholarDigital Library
32. Liu, D. C., and Nocedal, J. 1989. On the limited memory BFGS method for large scale optimization. Mathematical Programming 45, 3, 503–528. Google ScholarDigital Library
33. Liu, Y., Wang, W., Lévy, B., Sun, F., Yan, D., Lu, L., and Yang, C. 2009. On centroidal Voronoi tessellation — energy smoothness and fast computation. ACM Transactions on Graphics 28, 4, 101:1–101:17. Google ScholarDigital Library
34. Lloyd, S. 1982. Least squares quantization in PCM. IEEE Transactions on Information Theory 28, 2, 129–137. Google ScholarDigital Library
35. Loseille, A., and Alauzet, F. 2011. Continuous mesh framework part I: Well-posed continuous interpolation error. SIAM Journal on Numerical Analysis 49, 1, 38–60. Google ScholarDigital Library
36. Loseille, A., and Alauzet, F. 2011. Continuous mesh framework part II: Validations and applications. SIAM Journal on Numerical Analysis 49, 1, 61–86. Google ScholarDigital Library
37. Meyer, M. D., Georgel, P., and Whitaker, R. T. 2005. Robust particle systems for curvature dependent sampling of implicit surfaces. In International Conference on Shape Modeling and Applications, 124–133. Google ScholarDigital Library
38. Mirebeau, J., and Cohen, A. 2010. Anisotropic smoothness classes: From finite element approximation to image models. Journal of Mathematical Imaging and Vision 38, 1, 52–69. Google ScholarDigital Library
39. Mirebeau, J., and Cohen, A. 2012. Greedy bisection generates optimally adapted triangulations. Mathematics of Computation 81, 278, 811–837.Google Scholar
40. Mount, D. M., and Arya, S. 1997. ANN: A library for approximate nearest neighbor searching. In CGC Workshop on Computational Geometry, 33–40.Google Scholar
41. Nash, J. 1954. C1-isometric embeddings. Annals of Mathematics 60, 3, 383–396.Google ScholarCross Ref
42. Peyre, G., and Cohen, L. 2004. Surface segmentation using geodesic centroidal tesselation. In Proceedings of the 3D Data Processing, Visualization, and Transmission, 2nd International Symposium, 3DPVT ’04, 995–1002. Google ScholarDigital Library
43. Peyre, G., Pechaud, M., Keriven, R., and Cohen, L. 2010. Geodesic methods in computer vision and graphics. Foundations and Trends in Computer Graphics and Vision 5, 3-4, 197–397. Google ScholarDigital Library
44. Shapiro, P. R., Martel, H., Villumsen, J. V., and Owen, J. M. 1996. Adaptive smoothed particle hydrodynamics, with application to cosmology: Methodology. Astrophysical Journal Supplement 103, 269–330.Google ScholarCross Ref
45. Shewchuk, J. R. 2002. What is a good linear element? interpolation, conditioning, and quality measures. In 11th International Meshing Roundtable, 115–126.Google Scholar
46. Shimada, K., and Gossard, D. C. 1995. Bubble mesh: Automated triangular meshing of non-manifold geometry by sphere packing. In Proceedings of the 3rd ACM Symposium on Solid Modeling and Applications, 409–419. Google ScholarDigital Library
47. Shimada, K., Yamada, A., and Itoh, T. 1997. Anisotropic triangular meshing of parametric surfaces via close packing of ellipsoidal bubbles. In 6th International Meshing Roundtable, 375–390.Google Scholar
48. Simpson, R. B. 1994. Anisotropic mesh transformations and optimal error control. Applied Numerical Mathematics 14, 1–3, 183–198. Google ScholarDigital Library
49. Sun, F., Choi, Y., Wang, W., Yan, D., Liu, Y., and Lévy, B. 2011. Obtuse triangle suppression in anisotropic meshes. Computer Aided Geometric Design 28, 9, 537–548. Google ScholarDigital Library
50. Turk, G. 1992. Re-tiling polygonal surfaces. In Proceedings of the 19th Annual Conference on Computer Graphics and Interactive Techniques, ACM, SIGGRAPH ’92, 55–64. Google ScholarDigital Library
51. Valette, S., Chassery, J. M., and Prost, R. 2008. Generic remeshing of 3D triangular meshes with metric-dependent discrete Voronoi diagrams. IEEE Transactions on Visualization and Computer Graphics 14, 2, 369–381. Google ScholarDigital Library
52. Witkin, A. P., and Heckbert, P. S. 1994. Using particles to sample and control implicit surfaces. In Proceedings of the 21st Annual Conference on Computer Graphics and Interactive Techniques, ACM, SIGGRAPH ’94, 269–277. Google ScholarDigital Library
53. Yamakawa, S., and Shimada, K. 2000. High quality anisotropic tetrahedral mesh generation via packing ellipsoidal bubbles. In 9th International Meshing Roundtable, 263–273.Google Scholar
54. Yan, D., Lévy, B., Liu, Y., Sun, F., and Wang, W. 2009. Isotropic remeshing with fast and exact computation of restricted Voronoi diagram. Computer Graphics Forum 28, 5, 1445–1454. Google ScholarDigital Library
55. Zhang, M., Huang, J., Liu, X., and Bao, H. 2010. A wave-based anisotropic quadrangulation method. ACM Transactions on Graphics 29, 4, 118:1–118:8. Google ScholarDigital Library
