On Centroidal Voronoi Tessellation—
Energy Smoothness and Fast Computation

Yang Liu1,2, Wenping Wang1, Bruno Lévy2, Feng Sun1, Dong-Ming Yan1, Lin Lu1, Chenglei Yang3

1Department of Computer Science, The University of Hong Kong
2Project ALICE, INRIA, Villers les Nancy, France
3School of Computer Science and Technology, Shandong University, China

Lion model (# of faces: 50,000, # of vertices: 25,002, # of seeds: 25,002). Left: The input mesh; Left middle: the initial Voronoi diagram; Right middle:: CCVT computed by L-BFGS; Right: the triangle mesh dual to CCVT.

Rocker model (# of faces: 11,316, # of vertices: 5,658, # of seeds: 5,658). Left: The input mesh; Left middle: the initial Voronoi diagram; Right middle:: CCVT computed by L-BFGS; Right: the triangle mesh dual to CCVT.

 

Abstract: Centroidal Voronoi tessellation (CVT) is a fundamental geometric structure that finds many applications in computational science and engineering, including computer graphics. The prevailing method for computing CVT is Lloyd's method, which has linear convergence and is inefficient in practice. Our goal is to develop efficient methods for CVT computation, justify the fast convergence of these methods theoretically and demonstrate their superiority with experimental examples in various cases. Specifically, it is shown that the CVT energy function has C2 smoothness in convex domains and in most other commonly encountered domains with smooth density, correcting the view in the literature that this function is non-smooth (that is, merely C0 but not C1). Due to its C2 smoothness, it is therefore possible to minimize the CVT energy functions using Newton-like optimization methods and expect fast convergence. We apply quasi-Newton methods to computing CVT and demonstrate their faster convergence than Lloyd's method and their better robustness than the Lloyd-Newton method, a previous attempt at CVT computation acceleration. The application of these results to surface remeshing in computer graphics is also studied.


PDF (8.91M)

See also CVT page at Alice@loria