Journal Home > Volume 1 , Issue 3

In this paper, we propose a simple-yet-effective method for isotropic meshing relying on Euclidean distance transformation based centroidal Voronoi tessellation (CVT). Our approach improves the performance and robustness of computing CVT on curved domains while simultaneously providing high-quality output meshes. While conventional extrinsic methods compute CVTs in the entire volume bounded by the input model, we restrict the computation to a 3D shell of user-controlled thickness. Taking voxels which contain surface samples as sites, we compute the exact Euclidean distance transform on the GPU. Our algorithm is parallel and memory-efficient, and can construct the shell space for resolutions up to 20483 at interactive speed. The 3D centroidal Voronoi tessellation and restricted Voronoi diagrams are also computed efficiently on the GPU. Since the shell space can bridge holes and gaps smaller than a certain tolerance, and tolerate non-manifold edges and degenerate triangles, our algorithm can handle models with such defects, which typically cause conventional remeshing methods to fail. Our method can process implicit surfaces, polyhedral surfaces, and point clouds in a unified framework. Computational results show that our GPU-based isotropic meshing algorithm produces results comparable to state-of-the-art techniques, but is significantly faster than conventional CPU-based implementations.


menu
Abstract
Full text
Outline
About this article

A unified framework for isotropic meshing based on narrow-band Euclidean distance transformation

Show Author's information Yuen-Shan Leung1Xiaoning Wang1Ying He1( )Yong-Jin Liu2Charlie C. L. Wang3
School of Computer Engineering, Nanyang Technological University, Singapore.
Department of Computer Science and Technology Tsinghua University China.
Department of Mechanical and Automation Engineering, The Chinese University of Hong Kong, Hong Kong, China.

Abstract

In this paper, we propose a simple-yet-effective method for isotropic meshing relying on Euclidean distance transformation based centroidal Voronoi tessellation (CVT). Our approach improves the performance and robustness of computing CVT on curved domains while simultaneously providing high-quality output meshes. While conventional extrinsic methods compute CVTs in the entire volume bounded by the input model, we restrict the computation to a 3D shell of user-controlled thickness. Taking voxels which contain surface samples as sites, we compute the exact Euclidean distance transform on the GPU. Our algorithm is parallel and memory-efficient, and can construct the shell space for resolutions up to 20483 at interactive speed. The 3D centroidal Voronoi tessellation and restricted Voronoi diagrams are also computed efficiently on the GPU. Since the shell space can bridge holes and gaps smaller than a certain tolerance, and tolerate non-manifold edges and degenerate triangles, our algorithm can handle models with such defects, which typically cause conventional remeshing methods to fail. Our method can process implicit surfaces, polyhedral surfaces, and point clouds in a unified framework. Computational results show that our GPU-based isotropic meshing algorithm produces results comparable to state-of-the-art techniques, but is significantly faster than conventional CPU-based implementations.

Keywords: GPU, centroidal Voronoi tessellation (CVT), Euclidean distance transformation, isotropic meshing, polygonal meshes, point clouds, implicit surfaces

References(37)

[1]
Yan D.-M.; Lévy B.; Liu Y.; Sun F.; Wang W. Isotropic remeshing with fast and exact computation of restricted Voronoi diagram. Computer Graphics Forum Vol. 28, No. 5, 1445-1454, 2009.
[2]
Yan D.; Wang W.; Lévy B.; Liu Y. Efficient computation of clipped Voronoi diagram for mesh generation. Computer-Aided Design Vol. 45, No. 4, 843-852, 2013.
[3]
Liu Y. J.; Chen Z.; Tang K. Construction of iso-contours, bisectors, and Voronoi diagrams on triangulated surfaces. IEEE Transactions on Pattern Analysis and Machine Intelligence Vol. 33, No. 8, 1502-1517, 2011.
[4]
Liu Y.-J.; Tang K. The complexity of geodesic Voronoi diagrams on triangulated 2-manifold surfaces. Information Processing Letters Vol. 113, No. 4, 132-136, 2013.
[5]
Xu C.; Liu Y.-J.; Sun Q.; Li J.; He Y. Polyline-sourced geodesic Voronoi diagrams on triangle meshes. Computer Graphics Forum Vol. 33, No. 7, 161-170, 2014.
[6]
Du Q.; Gunzburger M. D.; Ju L. Constrained centroidal Voronoi tessellations for surfaces. SIAM Journal on Scientific Computing Vol. 24, No. 5, 1488-1506, 2002.
[7]
Lloyd S. Least squares quantization in PCM. IEEE Transactions on Information Theory Vol. 28, No. 2, 129-137, 1982.
[8]
Liu Y.; Wang W.; Lévy B.; Sun F.; Yan D.-M.; Lu L.; Yang C On centroidal Voronoi tessellation—Energy smoothness and fast computation. ACM Transactions on Graphics Vol. 28, No. 4, Article No. 101, 2009.
[9]
Rong G.; Liu Y.; Wang W.; Yin X.; Gu X. D.; Guo X. GPU-assisted computation of centroidal Voronoi tessellation. IEEE Transactions on Visualization and Computer Graphics Vol. 17, No. 3, 345-356, 2011.
[10]
Alliez P.; de Verdière É. C.; Devillers O.; Isenburg M. Isotropic surface remeshing. In: Proceedings of the Shape Modeling International, 49, 2003.
[11]
Rong G.; Jin M.; Shuai L.; Guo X. Centroidal Voronoi tessellation in universal covering space of manifold surfaces. Computer Aided Geometric Design Vol. 28, No. 8, 475-496, 2011.
[12]
Shuai L.; Guo X.; Jin M. GPU-based computation of discrete periodic centroidal Voronoi tessellation in hyperbolic space. Computer-Aided Design Vol. 45, No. 2, 463-472, 2013.
[13]
Wang X.; Ying X.; Liu Y.-J.; Xin S.-Q.; Wang W.; Gu X.; Mueller-Wittig W.; He Y. Intrinsic computation of centroidal Voronoi tessellation (CVT) on meshes. Computer-Aided Design Vol. 58, 51-61, 2015.
[14]
Lu L.; Lévy B.; Wang W. Centroidal Voronoi tessellation of line segments and graphs. Computer Graphics Forum Vol. 31, No. 2, 775-784, 2012.
[15]
Lévy B.; Bonneel N. Variational anisotropic surface meshing with Voronoi parallel linear enumeration. In: Proceedings of the 21st International Meshing Roundtable, 349-366, 2013.
DOI
[16]
Lévy B.; Liu Y. Lp centroidal Voronoi tessellation and its applications. ACM Transactions on Graphics Vol. 29, No. 4, Article No. 119, 2010.
[17]
Chen Z.; Cao J.; Wang W. Isotropic surface remeshing using constrained centroidal Delaunay mesh. Computer Graphics Forum Vol. 31, No. 7, 2077-2085, 2012.
[18]
Li H.; Zeng W.; Morvan J. M.; Chen L.; Gu X. Surface meshing with curvature convergence. IEEE Transactions on Visualization and Computer Graphics Vol. 20, No. 6, 919-934, 2014.
[19]
Mitchell J. S. B.; Mount D. M.; Papadimitriou C. H. The discrete geodesic problem. SIAM Journal on Computing Vol. 16, No. 4, 647-668, 1987.
[20]
Chen J.; Han Y. Shortest paths on a polyhedron. In: Proceedings of the 6th Annual Symposium on Computational Geometry, 360-369, 1990.
DOI
[21]
Xu C.; Wang T.; Liu Y.; Liu L.; He Y. Fast wavefront propagation (FWP) for computing exact discrete geodesics on meshes. IEEE Transactions on Visualization and Computer Graphics Vol. 21, No. 7, 822-834, 2015.
[22]
Ying X.; Xin S.-Q.; He Y. Parallel chen-han (PCH) algorithm for discrete geodesics. ACM Transactions on Graphics Vol. 33, No. 1, Article No. 9, 2014.
[23]
Kimmel R.; Sethian J. A. Computing geodesic paths on manifolds. Proceedings of the National Academy of Sciences of the United States of America Vol. 95, 8431-8435, 1998.
[24]
Crane K.; Weischedel C.; Wardetzky M. Geodesics in heat: A new approach to computing distance based on heat flow. ACM Transactions on Graphics Vol. 32, No. 5, Article No. 152, 2013.
[25]
Campen M.; Heistermann M.; Kobbelt L. Practical anisotropic geodesy. Computer Graphics Forum Vol. 32, No. 5, 63-71, 2013.
[26]
Ying X.; Wang X.; He Y. Saddle vertex graph (SVG): A novel solution to the discrete geodesic problem. ACM Transactions on Graphics Vol. 32, No. 6, Article No. 170, 2013.
[27]
Jones M. W.; Baerentzen J. A.; Sramek M. 3D distance fields: A survey of techniques and applications. IEEE Transactions on Visualization and Computer Graphics Vol. 12, No. 4, 581-599, 2006.
[28]
Marchand-Maillet S.; Sharaiha Y. M. Euclidean ordering via chamfer distance calculations. Computer Vision and Image Understanding Vol. 73, No. 3, 404-413, 1999.
[29]
Satherley R.; Jones M. W. Vector-city vector distance transform. Computer Vision and Image Understanding Vol. 82, No. 3, 238-254, 2001.
[30]
Hoff III K. E.; Keyser J.; Lin M.; Manocha D.; Culver T. Fast computation of generalized Voronoi diagrams using graphics hardware. In: Proceedings of the 26th Annual Conference on Computer Graphics and Interactive Techniques, 277-286, 1999.
DOI
[31]
Cao T.-T.; Tang K.; Mohamed A.; Tan T.-S. Parallel banding algorithm to compute exact distance transform with the GPU In: Proceedings of the 2010 ACM SIGGRAPH Symposium on Interactive 3D Graphics and Games, 83-90, 2010.
DOI
[32]
Amenta N.; Bern M.; Kamvysselis M. A new Voronoi-based surface reconstruction algorithm. In: Proceedings of the 25th Annual Conference on Computer Graphics and Interactive Techniques, 415-421, 1998.
DOI
[33]
Amenta N.; Choi S.; Dey T. K.; Leekha N. A simple algorithm for homeomorphic surface reconstruction. In: Proceedings of the 16th Annual Symposium on Computational Geometry, 213-222, 2000.
DOI
[34]
Kazhdan M. M.; Bolitho M.; Hoppe H. Poisson surface reconstruction. In: Proceedings of the 4th Eurographics Symposium on Geometry Processing, 61-70, 2006.
[35]
Sheung H.; Wang C. C. L. Robust mesh reconstruction from unoriented noisy points. In: Proceedings of SIAM/ACM Joint Conference on Geometric and Physical Modeling, 13-24, 2009.
DOI
[36]
Dey T. K.; Goswami S. Tight cocone: A water-tight surface reconstructor. In: Proceedings of the 8th ACM Symposium on Solid Modeling and Applications, 127-134, 2003.
DOI
[37]
Wang C. C. L.; Leung Y.-S.; Chen Y. Solid modeling of polyhedral objects by layered depth-normal images on the GPU. Computer-Aided Design Vol. 42, No. 6, 535-544, 2010.
Publication history
Copyright
Acknowledgements
Rights and permissions

Publication history

Revised: 17 August 2015
Accepted: 29 August 2015
Published: 21 October 2015
Issue date: September 2015

Copyright

© The Author(s) 2015

Acknowledgements

The NTU authors are partially supported by AcRF RG40/12 and MOE2013-T2-2-011. Y.-J. Liu is partially supported by National Natural Science Foundation of China (Nos. 61432003 and 61322206) and the TNList Cross-discipline Foundation. C. C. L. Wang is partially supported by HKSAR Research Grants Council (RGC) General Research Fund (GRF), CUHK/14207414.

Rights and permissions

This article is published with open access at Springerlink.com

This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.

Other papers from this open access journal are available free of charge from http://www.springer.com/journal/41095. To submit a manuscript, please go to https://www.editorialmanager.com/cvmj.

Return