Isotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagram

dc.contributor.authorYan, Dong-Mingen_US
dc.contributor.authorLevy, Brunoen_US
dc.contributor.authorLiu, Yangen_US
dc.contributor.authorSun, Fengen_US
dc.contributor.authorWang, Wenpingen_US
dc.date.accessioned2015-02-23T15:43:31Z
dc.date.available2015-02-23T15:43:31Z
dc.date.issued2009en_US
dc.description.abstractWe 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.en_US
dc.description.number5en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume28en_US
dc.identifier.doi10.1111/j.1467-8659.2009.01521.xen_US
dc.identifier.issn1467-8659en_US
dc.identifier.pages1445-1454en_US
dc.identifier.urihttps://doi.org/10.1111/j.1467-8659.2009.01521.xen_US
dc.publisherThe Eurographics Association and Blackwell Publishing Ltden_US
dc.titleIsotropic Remeshing with Fast and Exact Computation of Restricted Voronoi Diagramen_US
Files