Hai-Etlik

04-13-2011, 04:14 AM

I've been wanting to try this for a while now and after attending a talk by Martin Davis about JTS Topology Suite, a Java library he wrote (along with others) for computational geometry, I decided to give it a shot.

Basically, Weighted Centroidal Voronoi Stippling is a way to produce an image like a stipple drawing, with many little dots that get denser to make a dark tone, and wider to make a light tone, and within a tone, are approximately evenly spaced.

Basically it goes like this: 1) Spread out a bunch of points over the area in question. 2) Compute the Voronoi tessellation for the points. 3) Replace the points with the the centroids for the Voronoi polygons, but weight the polygons' areas with a scalar field (Like an inverted greyscale image) 4) Repeat 2 and 3 many times.

My implementation is a bit odd at the moment in that it supports a vector mask (I clip the Voronoi polygons at each step), and it currently uses just a simple function rather than an image. It's also very, very slow: I was able to speed it up a fair bit by splitting the weighted centroid computation across multiple threads but it's still really slow. I compute the centroid by iterating over a grid of points, adding together the point times the weight function, and the weight function by itself, then divide the first sum by the second.

So, here's what I can produce so far:

35062

The mask is just an OGC Simple Features WKT string, the weight function is (x/width)^2, there are 6000 stipples, and I gave it 50 iterations. Output is an SVG file which I rendered in Inkscape. The seed points are distributed randomly with a further random rejection factor based on the weight function.

It took several minutes to run but hopefully I can improve it. Eventually I plan to use it to distribute terrain symbology like trees, mountains, hills, etc.

The code is nowhere near ready for distribution but I'll probably release it under the GPL if it ever is.

Basically, Weighted Centroidal Voronoi Stippling is a way to produce an image like a stipple drawing, with many little dots that get denser to make a dark tone, and wider to make a light tone, and within a tone, are approximately evenly spaced.

Basically it goes like this: 1) Spread out a bunch of points over the area in question. 2) Compute the Voronoi tessellation for the points. 3) Replace the points with the the centroids for the Voronoi polygons, but weight the polygons' areas with a scalar field (Like an inverted greyscale image) 4) Repeat 2 and 3 many times.

My implementation is a bit odd at the moment in that it supports a vector mask (I clip the Voronoi polygons at each step), and it currently uses just a simple function rather than an image. It's also very, very slow: I was able to speed it up a fair bit by splitting the weighted centroid computation across multiple threads but it's still really slow. I compute the centroid by iterating over a grid of points, adding together the point times the weight function, and the weight function by itself, then divide the first sum by the second.

So, here's what I can produce so far:

35062

The mask is just an OGC Simple Features WKT string, the weight function is (x/width)^2, there are 6000 stipples, and I gave it 50 iterations. Output is an SVG file which I rendered in Inkscape. The seed points are distributed randomly with a further random rejection factor based on the weight function.

It took several minutes to run but hopefully I can improve it. Eventually I plan to use it to distribute terrain symbology like trees, mountains, hills, etc.

The code is nowhere near ready for distribution but I'll probably release it under the GPL if it ever is.