Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram
Top Cited Papers
- 1 July 2009
- journal article
- Published by Wiley in Computer Graphics Forum
- Vol. 28 (5), 1445-1454
- https://doi.org/10.1111/j.1467-8659.2009.01521.x
Abstract
We propose a new isotropic remeshing method, based on Centroidal Voronoi Tessellation (CVT). Constructing CVT requires to repeatedly compute Restricted Voronoi Diagram (RVD), defined as the intersection between a 3D Voronoi diagram and an input mesh surface. Existing methods use some approximations of RVD. In this paper, we introduce an efficient algorithm that computes RVD exactly and robustly. As a consequence, we achieve better remeshing quality than approximation-based approaches, without sacrificing efficiency. Our method for RVD computation uses a simple procedure and a kd-tree to quickly identify and compute the intersection of each triangle face with its incident Voronoi cells. Its time complexity is O(mlog n), where n is the number of seed points and m is the number of triangles of the input mesh. Fast convergence of CVT is achieved using a quasi-Newton method, which proved much faster than Lloyd's iteration. Examples are presented to demonstrate the better quality of remeshing results with our method than with the state-of-art approaches.Keywords
This publication has 17 references indexed in Scilit:
- On centroidal voronoi tessellation—energy smoothness and fast computationACM Transactions on Graphics, 2009
- On Mesh Geometry and Stiffness Matrix Conditioning for General Finite Element SpacesSIAM Journal on Numerical Analysis, 2009
- A fast Voronoi-diagram algorithm with applications to geographical optimization problemsPublished by Springer Science and Business Media LLC ,2005
- Variational tetrahedral meshingACM Transactions on Graphics, 2005
- Centroidal Voronoi diagrams for isotropic surface remeshingGraphical Models, 2004
- Constrained Centroidal Voronoi Tessellations for SurfacesSIAM Journal on Scientific Computing, 2003
- Interactive geometry remeshingACM Transactions on Graphics, 2002
- On the limited memory BFGS method for large scale optimizationMathematical Programming, 1989
- Least squares quantization in PCMIEEE Transactions on Information Theory, 1982
- Reentrant polygon clippingCommunications of the ACM, 1974