Isotropic remeshing with fast and exact computation of restricted voronoi diagram

Dong Ming Yan*, Bruno Lévy, Yang Liu, Feng Sun, Wenping Wang

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

141 Scopus citations

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.

Original languageEnglish (US)
Pages (from-to)1445-1454
Number of pages10
JournalComputer Graphics Forum
Volume28
Issue number5
DOIs
StatePublished - Jul 2009

Keywords

  • I.3.3 [Computer Graphics]
  • Picture/Image Generation - Line and curve generation

ASJC Scopus subject areas

  • Computer Graphics and Computer-Aided Design

Fingerprint Dive into the research topics of 'Isotropic remeshing with fast and exact computation of restricted voronoi diagram'. Together they form a unique fingerprint.

Cite this