article

Anisotropic surface meshing with conformal embedding

Authors:

Xiaohu GuoAuthors Info & Claims

Graphical Models, Volume 76, Issue 5

Pages 468 - 483

https://doi.org/10.1016/j.gmod.2014.03.011

Published: 01 September 2014 Publication History

Abstract

This paper introduces a parameterization-based approach for anisotropic surface meshing. Given an input surface equipped with an arbitrary Riemannian metric, this method generates a metric-adapted mesh with user-specified number of vertices. In the proposed method, the edge length of the input surface is directly adjusted according to the given Riemannian metric at first. Then the adjusted surface is conformally embedded into a parametric 2D domain and a weighted Centroidal Voronoi Tessellation and its dual Delaunay triangulation are computed on the parametric domain. Finally the generated Delaunay triangulation can be mapped from the parametric domain to the original space, and the triangulation exhibits the desired anisotropic property. We compute the high-quality remeshing results for surfaces with different types of topologies and compare our method with several state-of-the-art approaches in anisotropic surface meshing by using the standard measurement criteria.

References

[1]

Alauzet, F. and Loseille, A., High-order sonic boom modeling based on adaptive methods. J. Comput. Phys. v229 i3. 561-593.

[2]

Narain, R., Samii, A. and O'Brien, J.F., Adaptive anisotropic remeshing for cloth simulation. ACM Trans. Graph. v31 i6. 147:1-147:10.

[3]

Anisotropic centroidal Voronoi tessellations and their applications. SIAM J. Sci. Comput. v26 i3. 737-761.

[4]

Obtuse triangle suppression in anisotropic meshes. Comput. Aid. Geom. Des. v28 i9. 537-548.

[5]

Nash, J., C1-isometric embeddings. Ann. Math. v60 i3. 383-396.

[6]

Zhong, Z., Guo, X., Wang, W., Lévy, B., Sun, F., Liu, Y. and Mao, W., Particle-based anisotropic surface meshing. ACM Trans. Graph. v32 i4.

[7]

Alliez, P., Cohen-Steiner, D., Devillers, O., Lévy, B. and Desbrun, M., Anisotropic polygonal remeshing. ACM Trans. Graph. v22 i3. 485-493.

[8]

Beardon, A.F., A Primer on Riemann Surfaces. 1984. Cambridge University Press.

[9]

G. Rong, M. Jin, X. Guo, Hyperbolic centroidal Voronoi tessellation, in: Proceedings of Symposium of Solid and Physical Modeling (SPM 2010), 2010, pp. 117-126.

[10]

Rong, G., Jin, M., Shuai, L. and Guo, X., Centroidal Voronoi tessellation in universal covering space of manifold surfaces. Comput. Aid. Geom. Des. v28 i8. 475-496.

[11]

Optimal parameterizations for surface remeshing. Eng. Comput. v12. 1-20.

[12]

Du, Q., Faber, V. and Gunzburger, M., Centroidal Voronoi tessellations: applications and algorithms. SIAM Rev. v41 i4. 637-676.

[13]

Lloyd, S., Least squares quantization in PCM. IEEE Trans. Inform. Theor. v28 i2. 129-137.

[14]

Liu, Y., Wang, W., Lévy, B., Sun, F., Yan, D., Lu, L. and Yang, C., On centroidal Voronoi tessellation - energy smoothness and fast computation. ACM Trans. Graph. v28 i4. 101:1-101:17.

[15]

G. Peyre, L. Cohen, Surface segmentation using geodesic centroidal tesselation, in: Proceedings of the 3D Data Processing, Visualization, and Transmission, 2nd International Symposium, 3DPVT '04, 2004, pp. 995-1002.

[16]

H. Edelsbrunner, N.R. Shah, Triangulating topological spaces, in: Symposium on Computational Geometry, 1994, pp. 285-292.

[17]

Du, Q., Gunzburger, M.D. and Ju, L., Constrained centroidal Voronoi tessellations for surfaces. SIAM J. Sci. Comput. v24 i5. 1488-1506.

[18]

Isotropic remeshing with fast and exact computation of restricted Voronoi diagram. Comput. Graph. Forum. v28 i5. 1445-1454.

[19]

Alliez, P., Verdiére, í., Devillers, O. and Isenburg, M., Centroidal voronoi diagrams for isotropic surface remeshing. Graph. Models. v67 i3. 204-231.

[20]

Generic remeshing of 3D triangular meshes with metric-dependent discrete Voronoi diagrams. IEEE Trans. Vis. Comput. Graph. v14 i2. 369-381.

[21]

B. Lévy, N. Bonneel, Variational anisotropic surface meshing with Voronoi parallel linear enumeration, in: 21st International Meshing Roundtable, 2012, pp. 349-366.

[22]

Borouchaki, H., George, P.L., Hecht, F., Laug, P. and Saltel, E., Delaunay mesh generation governed by metric specifications. Part I. Algorithms. Finite Elem. Anal. Des. v25 i1-2. 61-83.

[23]

Borouchaki, H., George, P.L. and Mohammadi, B., Delaunay mesh generation governed by metric specifications. Part II. Applications. Finite Elem. Anal. Des. v25 i1-2. 85-109.

[24]

C. Dobrzynski, P. Frey, Anisotropic Delaunay mesh adaptation for unsteady simulations, in: 17th International Meshing Roundtable, 2008, pp. 177-194.

[25]

H.-L. Cheng, T. Dey, H. Edelsbrunner, J. Sullivan, Dynamic skin triangulation, in: ACM-SIAM Symposium on Discrete Algorithms, vol. 25, 2001, pp. 525-568.

[26]

S. Cheng, T. Dey, E. Ramos, T. Ray, Sampling and meshing a surface with guaranteed topology and geometry, in: Proc. 20th Sympos. Comput. Geom., 2004, pp. 280-289.

Digital Library

[27]

S. Cheng, T. Dey, E. Ramos, Anisotropic surface meshing, in: Proc. ACM-SIAM Sympos. Discrete Algorithms, 2006, pp. 202-211.

[28]

J. Boissonnat, C. Wormser, M. Yvinec, Locally uniform anisotropic meshing, in: Proceedings of the 24th Annual Symposium on Computational Geometry, SCG '08, 2008, pp. 270-277.

[29]

J. Boissonnat, C. Wormser, M. Yvinec, Anisotropic Delaunay Mesh Generation, Research Report RR-7712.

[30]

F. Bossen, P. Heckbert, A pliant method for anisotropic mesh generation, in: 5th International Meshing Roundtable, 1996, pp. 63-76.

[31]

K. Shimada, D.C. Gossard, Bubble mesh: automated triangular meshing of non-manifold geometry by sphere packing, in: Proceedings of the 3rd ACM Symposium on Solid Modeling and Applications, 1995, pp. 409-419.

[32]

K. Shimada, A. Yamada, T. Itoh, Anisotropic triangular meshing of parametric surfaces via close packing of ellipsoidal bubbles, in: 6th International Meshing Roundtable, 1997, pp. 375-390.

[33]

S. Yamakawa, K. Shimada, High quality anisotropic tetrahedral mesh generation via packing ellipsoidal bubbles, in: 9th International Meshing Roundtable, 2000, pp. 263-273.

[34]

Jin, M., Kim, J., 0002, F.L. and Gu, X., Discrete surface Ricci flow. IEEE Trans. Vis. Comput. Graph. v14 i5. 1030-1043.

[35]

Gu, X., Wang, Y., Chan, T.F., Thompson, P.M. and tung Yau, S., Genus zero surface conformal mapping and its application to brain surface mapping. IEEE Trans. Med. Imag. v23. 949-958.

[36]

Lévy, B., Petitjean, S., Ray, N. and Maillot, J., Least squares conformal maps for automatic texture atlas generation. ACM Trans. Graph. v21 i3. 362-371.

[37]

Convergence of the Lloyd algorithm for computing centroidal Voronoi tessellations. SIAM J. Numer. Anal. v44 i1. 102-119.

[38]

Renka, R.J., Algorithm 772: atripack: Delaunay triangulation and Voronoi diagram on the surface of a sphere. ACM Trans. Math. Softw. v23 i3. 416-434.

[39]

Cgal, Computational Geometry Algorithms Library. <http://www.cgal.org>.

[40]

F. Nielsen, R. Nock, Hyperbolic voronoi diagrams made easy, in: Proceedings of the 2010 International Conference on Computational Science and Its Applications, ICCSA'10, 2010, pp. 74-80.

[41]

Aurenhammer, F., Power diagrams: properties, algorithms and applications. SIAM J. Comput. v16 i1. 78-96.

[42]

Shuai, L., Guo, X. and Jin, M., GPU-based computation of discrete periodic centroidal voronoi tessellation in hyperbolic space. Comput.-Aid. Des. v45 i2. 463-472.

[43]

Galperin, G., A concept of the mass center of a system of material points in the constant curvature spaces. Commun. Math. Phys. v154 i1. 63-84.

[44]

P.J. Frey, H. Borouchaki, Surface mesh evaluation, in: 6th International Meshing Roundtable, 1997, pp. 363-373.

[45]

M. Garland, P. Heckbert, Simplifying surfaces with color and texture using quadric error metrics, in: Proceedings of the conference on Visualization '98, 1998, pp. 263-269.

Digital Library

[46]

Cañas, G. and Gortler, S., Surface remeshing in arbitrary codimensions. Vis. Comput. Int. J. Comput. Graph. v22 i9. 885-895.

[47]

Chow, B. and Luo, F., Combinatorial Ricci flows on surfaces. Differ. Geom. v63 i1. 97-129.

Cited By

Li MFang QZhang ZLiu LFu X(2023)Efficient Cone Singularity Construction for Conformal ParameterizationsACM Transactions on Graphics10.1145/361840742:6(1-13)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618407
Fang QOuyang WLi MLiu LFu X(2021)Computing sparse cones with bounded distortion for conformal parameterizationsACM Transactions on Graphics10.1145/3478513.348052640:6(1-9)Online publication date: 10-Dec-2021
https://dl.acm.org/doi/10.1145/3478513.3480526
Zhong ZWang WLévy BHua JGuo X(2018)Computing a high-dimensional euclidean embedding from an arbitrary smooth riemannian metricACM Transactions on Graphics10.1145/3197517.320136937:4(1-16)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3197517.3201369
Show More Cited By

Anisotropic surface meshing with conformal embedding
1. Computing methodologies
  1. Computer graphics
    1. Shape modeling
2. Theory of computation

Recommendations

Anisotropic surface meshing
SODA '06: Proceedings of the seventeenth annual ACM-SIAM symposium on Discrete algorithm

We study the problem of triangulating a smooth closed implicit surface Σ endowed with a 2D metric tensor that varies over Σ. This is commonly known as the anisotropic surface meshing problem. We extend the 2D metric tensor naturally to 3D and employ the ...
Locally uniform anisotropic meshing
SCG '08: Proceedings of the twenty-fourth annual symposium on Computational geometry

Various definitions of so called anisotropic Voronoi diagrams have been proposed. These diagrams are typically parameterized by a metric field. Under mild hypotheses on the metric field, such Voronoi diagrams can be refined so that their dual is a ...
Particle-based anisotropic surface meshing

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

Copyright © Elsevier Inc. © 2014.

Publisher

Academic Press Professional, Inc.

United States

Publication History

Published: 01 September 2014

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Li MFang QZhang ZLiu LFu X(2023)Efficient Cone Singularity Construction for Conformal ParameterizationsACM Transactions on Graphics10.1145/361840742:6(1-13)Online publication date: 5-Dec-2023
https://dl.acm.org/doi/10.1145/3618407
Fang QOuyang WLi MLiu LFu X(2021)Computing sparse cones with bounded distortion for conformal parameterizationsACM Transactions on Graphics10.1145/3478513.348052640:6(1-9)Online publication date: 10-Dec-2021
https://dl.acm.org/doi/10.1145/3478513.3480526
Zhong ZWang WLévy BHua JGuo X(2018)Computing a high-dimensional euclidean embedding from an arbitrary smooth riemannian metricACM Transactions on Graphics10.1145/3197517.320136937:4(1-16)Online publication date: 30-Jul-2018
https://dl.acm.org/doi/10.1145/3197517.3201369
Sawhney RCrane K(2017)Boundary First FlatteningACM Transactions on Graphics10.1145/313270537:1(1-14)Online publication date: 28-Dec-2017
https://dl.acm.org/doi/10.1145/3132705
Mansouri SEbrahimnezhad H(2016)Segmentation-based semi-regular remeshing of 3D models using curvature-adapted subdivision surface fittingJournal of Visualization10.1007/s12650-015-0288-819:1(141-155)Online publication date: 1-Feb-2016
https://dl.acm.org/doi/10.1007/s12650-015-0288-8

View Options

View options

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

Media

Figures

Other

Tables

View Issue’s Table of Contents