**.**

**ACM Transactions on Graphics (Proceedings of SIGGRAPH Asia 2017) **

Oliver Deussen^{ ＊1,2 }Marc Spicker^{ ＊1 } Qian
Zheng ^{1,3}

University
of Konstanz ^{1 }SIAT Shenzhen ^{2 }Shenzhen University ^{3}

^{＊Joint First Authors}

**Fig.
1**. Starting from a single random point, our dynamic illustration method creates
high-quality stipple drawings with a small number of iterations (left to right: 12, 14, and 18 iterations). In
the example shown above we end up with 36k points of constant size.

**More examples can be found in another project website.** __Click Here____
__

**Abstract**

We propose an adaptive version of Lloyd’s optimization method that distributes points based on Voronoi diagrams. Our inspiration is the Linde–Buzo–Gray–Algorithm in vector quantization, which dynamically splits Voronoi cells until a desired number of representative vectors is reached. We reformulate this algorithm by splitting and merging Voronoi cells based on their size, greyscale level, or variance of an underlying input image. The proposed method automatically adapts to various constraints and, in contrast to previous work, requires no good initial point distribution or prior knowledge about the final number of points. Compared to weighted Voronoi stippling the convergence rate is much higher and the spectral and spatial properties are superior. Further, because points are created based on local operations, coherent stipple animations can be produced. Our method is also able to produce good quality point sets in other fields, such as remeshing of geometry, based on local geometric features such as curvature.

** **

**Algorithm **

**Fig.
2**. LBG-Stippling of a greyscale ramp (see also Figure 6) with color-coded size
error in each cell: (a) initial point distribution with Voronoi
cells. On the left,
only some points are needed, thus cells
are too small (blue) and will be merged (points will be deleted); on the right,
many points are needed, thus cells are too
large (red) and therefore will be split
(new positions of points in green); (b) set after two iterations; (c) set after
six iterations.

**Results**

**Fig.
3**. Different
point diameters used to represent an input image, creating different numbers of
points and levels of abstraction: (a) 56k points (size 2), (b) 14k points
(size 4), and (c) 6.3k points (size 6). Input image courtesy of P. Debevec.

**Fig. 4**. Point
sizes in relation to other constraints: (a) radial increase from the eye of the
model (original image by Bùi Linh
Ngan, Flickr). In (b) the beak of the duck
is rendered with points enlarged depending on their distance to the viewer.

**Fig. 5**. Adaptive
sampling of a height function and a geometric model with density defined by the
color coded mean curvature: (a),(b) about 600 adaptively
sampled points;
(c) 5k adaptive points on the Stanford bunny; (d) remeshed
result of (c).

**Acknowledgments**

The authors would like to thank the German Research Foundation (DFG) for financial support within project A04 of SFB/Transregio 161. We also want to thank the Guangdong Science and Technology Program (2015A030312015), Leading Talents of Guangdong Program (00201509), Shenzhen Innovation Program (JCYJ20151015151249564), and Natural Science Foundation of SZU (827-000196).

**Bibtex**

title = {Weighted Linde–Buzo–Gray Stippling},

author = {Oliver Deussen and Marc Spicker and Qian Zheng},

journal = {ACM Transactions on Graphics (Proc. SIGGRAPH Asia)},

volume = {36},

number = {6},

year = {2017},

pages = {233:1--12},