The idea of this website is to create stipple drawings—images composed of small dots that represent shading, textures, and patterns using a technique called weighted Voronoi stippling.

Slide the slider to change the zoom

Weighted Voronoi stippling is a technique in computer graphics used to create stipple drawing/images composed of small dots that represent shading, textures, and patterns. Unlike traditional Voronoi diagrams, which divide space into regions based on proximity to seed points, weighted Voronoi diagrams assign weights to each point, affecting the position of the centroids within each region. The algorithm works by adjusting seed points—dots sampled around the image's darker pixels—and "relaxing" them, or, gradually moving them toward their weighted centroids. In this case, the weight corresponds to the darkness of the pixel.

Many choices can be made about the algorithm implementation, mostly because working with images may be tricky: the are loads os pixels, and most of the time, brute-force algorithms are not an option. A good way to deal with this is to use algorithms that give us good approximation. And we have some options:

Jump flooding algorithm (JFA)

The Jump flooding algorithm starts with an initial grid of seed points and iteratively propagates the influence of each seed across the grid. In each step, the algorithm "jumps" over increasingly larger distances to update the closest seed for each pixel, gradually refining the diagram. The complexity of the algorithm is O(n^2log(n)). For more details, take a look at Jump Flooding Algorithm.

Jump flooding algorithm GPU (JFA GPU)

The same algorithm, but using the GPU. The complexity here is O(log(n))

Ball Algorithm

The Ball Algorithm begins by initializing a set of seed points and expanding spherical regions around them. Each seed grows outward uniformly until it encounters another expanding region, forming the boundaries of the Voronoi cells. This process continues iteratively, refining the diagram as regions interact and adjust. The algorithm is particularly useful for approximating Voronoi diagrams and centroid-based calculations. Its complexity is O(nlog(n)).

Comparing Algorithms

Here, we present two comparisons between some algorithms, including those we discussed. We refer to the brute-force algorithm as "naive.". For a reading about theWavefront Algorithm.

Authors:

Davi Guimarães, Universidade Federal Fluminense; Leonardo Nanci, Universidade Federal Fluminense; Letícia Aleixo, Impatech; Lucas Gonçalves, Impatech; Marcos Melo, Impatech; Paulo de Almeida, Universidad de Buenos Aires; Richard Elias, Impatech; Tainá Drummond, Impatech; Tomaz Cavalcante, Impatech; Vinicius Maciel, Impatech;