Computer Graphics & Visual Computing (CGVC) 2017

Capacity-Constrained Voronoi Tessellation Revisited

Abdalla G. M. Ahmed¹       Oliver Deussen^1,2

¹University of Konstanz, Germany
²SIAT, China

10k-site stippling of Lena. (a) The initial distribution of sites in our implementation, using recursive division (256 points per site, 1.0 second). (b) After CCVT optimization (total 3.8 seconds, using our implementation). (c) BNOT output (52 seconds, using the published code) shown for comparison. All results using a 2.5GHz CORE i5 laptop with 4GB memory.

Abstract

Capacity Constrained Voronoi Tessellation is an important concept that greatly influenced recent research on point sampling. The original concept was based on discretizing the sampled domain, and the algorithm was prohibitively slow, even with some proposed accelerations. We present a few improvements that make a real difference in the speed of the algorithm, bringing it back into presence.

Downloads

	Paper PDF (1.2 MB)
	Source Code ZIP (696 KB)

Bibtex

@inproceedings {cgvc.20171285,
    booktitle = {Computer Graphics and Visual Computing (CGVC)},
    editor = {Tao Ruan Wan and Franck Vidal},
    title = {{Capacity Constrained Voronoi Tessellation Revisited}},
    author = {Ahmed, Abdalla G. M. and Deussen, Oliver},
    year = {2017},
    publisher = {The Eurographics Association},
    ISBN = {978-3-03868-050-5},
    DOI = {10.2312/cgvc.20171285}
}