PDA

View Full Version : Weighted Centroidal Voronoi Stippling using JTS



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.

Redrobes
04-13-2011, 08:21 AM
This looks nice but your text fails to say why one might want to use this technique over the usual error distribution ones like say Floyd Steinberg dithering.

Hai-Etlik
04-13-2011, 04:30 PM
This looks nice but your text fails to say why one might want to use this technique over the usual error distribution ones like say Floyd Steinberg dithering.

Dithering takes place on a pixel grid while Weighted Voronoi doesn't have a grid, giving it a more natural look. I might switch to a dithering algorithm for the initial placement of points though.

Also, the Voronoi tesselation itself could be handy. I've been thinking of ways to use it for a forest symbolizer by considering inner and outer edges and their orientation.

Hai-Etlik
04-21-2011, 05:18 AM
More progress. I've spent most of the intervening time playing with various different ways of getting XML in and out of my program but I've finally got it doing a very basic version of what I'm ultimately after:

I feed in a GML file, it breaks the polygons up using Centroidal Voronoi, and then symbolizes it to an SVG file.

So here's my latest test output:

35255

Redrobes
04-21-2011, 12:22 PM
Right, I think I see what your driving at now. Your using the dot placement as a position for an icon so as to create wide seamless expanse of textured area but not using bitmaps. Although this looks 2D Im guessing that your calculating it in 3D so as to get the Z order correct for the trees. Presumably you could zoom in on an area and it would still be in vector format.

Ascension
04-21-2011, 05:25 PM
Fully automated mapping (given some input), pretty cool.

Hai-Etlik
04-21-2011, 07:25 PM
Right, I think I see what your driving at now. Your using the dot placement as a position for an icon so as to create wide seamless expanse of textured area but not using bitmaps. Although this looks 2D Im guessing that your calculating it in 3D so as to get the Z order correct for the trees. Presumably you could zoom in on an area and it would still be in vector format.

Actually, after generating the points, I just sort them by their Y coordinates. I am thinking it would be interesting to add a Y shift based on the height of an underlying DEM though. I'm also planning on trying to write some more interesting symbolizers that work by splitting polygons into many smaller, roughly equal size polygons; I think I could manage a way of drawing forests as contiguous entities rather than bunches of individual trees (As in Ascension's recent practice maps)

RobA
04-21-2011, 08:52 PM
Actually, after generating the points, I just sort them by their Y coordinates. I am thinking it would be interesting to add a Y shift based on the height of an underlying DEM though. I'm also planning on trying to write some more interesting symbolizers that work by splitting polygons into many smaller, roughly equal size polygons; I think I could manage a way of drawing forests as contiguous entities rather than bunches of individual trees (As in Ascension's recent practice maps)

Use the bottom y coordinate where possible, so different symbols of different heights will stack properly (assuming they all sit on the ground ;) )

-Rob A>

Hai-Etlik
04-22-2011, 02:02 AM
Use the bottom y coordinate where possible, so different symbols of different heights will stack properly (assuming they all sit on the ground ;) )

-Rob A>

In this case I have the 'true' place that whatever it is is so I don't need to worry about that at this level. Instead it's a matter of drawing the symbol correctly, which means that the origin for the symbol should be wherever it is (the base of something like a tree or hill)

Hai-Etlik
06-28-2011, 11:51 PM
OK, back at this project again and I'm working on importing SVG data into JTS. This is really much harder than it would seem at first as SVG is really, really loose and flexible compared to GIS formats.

So far I've manage to make a little program that loads up an SVG file, looks for paths, and converts them to linestrings or multilinestrings depending on whether it has multiple subpaths. It only understands moveto, lineto, and closepath commands at the moment and chokes on anything else. It then spits it all out in OGC WKT format.

Roughly speaking, that means it takes this:

<path d="M 258.59905,189.69191 80.812204,365.45845 264.65997,692.74788 220.21325,510.92042 519.21841,434.14883 385.87827,246.26045 z" />
Which can be exported from Inkscape, and produces this:

LINESTRING (258.59905 189.69191, 80.812204 365.45845, 264.65997 692.74788, 220.21325 510.92042, 519.21841 434.14883, 385.87827 246.26045, 258.59905 189.69191)

Which can be loaded into at least some GIS software such as OpenJUMP.

Redrobes
06-29-2011, 08:35 AM
You can do that in three lines of perl or sed using a regular expressions (and one of those was just to add extra spaces after the commas). If this is the sort of thing you are doing then you should ensure your well familiar with them cos it makes manipulation like this so easy.



$in = '<path d="M 258.59905,189.69191 80.812204,365.45845 264.65997,692.74788 220.21325,510.92042 519.21841,434.14883 385.87827,246.26045 z" />';
$out = $in;

$out =~ s/<path d="M /LINESTRING (/;
$out =~ s/ z" \/>/)/;
$out =~ s/,/, /g;

print "Before: $in\n";
print "After : $out\n";



# Results:
#
# Before: <path d="M 258.59905,189.69191 80.812204,365.45845 264.65997,692.74788 220.21325,510.92042 519.21841,434.14883 385.87827,246.26045 z" />
# After : LINESTRING (258.59905, 189.69191 80.812204, 365.45845 264.65997, 692.74788 220.21325, 510.92042 519.21841, 434.14883 385.87827, 246.26045)
#

Hai-Etlik
06-29-2011, 05:19 PM
That might work in this very specific case, but not for SVG Path Data in general. Like I said, SVG is flexible and allows a lot of different ways of expressing things. Dealing with all those different ways is the hard part. You can express numbers as integers, decimals, or in scientific notiation, you can use commas or spaces as separators, commands and numbers don't need to be separated, but can be, commands can be omitted in which case you repeat the previous one with the next set of parameters, unless it was a moveto command in which case you treat the repetitions as lineto commands. Closed paths are handled differently between the two requiring that you keep track of the first point of any subpath, and just about every command has a relative form requiring you keep track of the most recent point as well.

And that's not even getting into the problem of all the curved path sections like bezier curves and elliptic arcs.

PS:
That said, I am using Regexps, it just takes a fair bit beyond regexps. Also, I wanted to be able to load directly into JTS; the WKT export is just corollary of sorts since JTS already has WKT export. Ultimately I'd be aiming to use the Centroidal Voronoi algorithm from the start of the thread on shapes loaded from an SVG file.

PPS: The topological issues with turning closed SVG paths into JTS Polygons or Multipolygons is going to be a lot of work too. SVG allows subpaths to intersect themselves and each other, and doesn't make topological distinctions between them. The The OGC Simple Features data model used by JTS doesn't allow intersecting rings, and does make a distinction between a polygons with an enclave, and a multipolygon with an exclave.

Master TMO
07-05-2011, 01:11 PM
Lordy, I remember just barely touching on some things similar to these issues way back when in earlier software, and all the headaches it caused.

Good luck, and you have my sympathies!

Terraformer_Author
07-27-2011, 01:44 PM
Ok - who woke me up!!!! Lol.

Hai-Etlik
04-09-2012, 03:00 AM
Inspired by This post (http://www.cartographersguild.com/showthread.php?18080-How-Do-I-make-Random-Map-Generators&p=180957&viewfull=1#post180957) I've done a bit more work on this using the Wang Tile + Progressive Poisson Disc technique rather than Weighted Centroidal Voronoi.

It still needs some work, and there are some bugs I'm feeling completely lost on, but It's producing something somewhat reasonable now, and it's FAR faster.

43867

Hai-Etlik
04-09-2012, 08:07 AM
OK, much smoother now that I've got the re-ranking step done. It dies on the seam finding step at random, so there's something wrong there. I'll be saving the generated tiles and simply load them in future, but it still would be nice to not have to run the generator several times to get a tile set out of it.

43872

Hai-Etlik
04-12-2012, 02:59 AM
Running a greyscale photo through it.

43944

Lukc
04-12-2012, 04:25 AM
Stipple-icious indeed :). Most of this goes a bit over my head, I fear ... but if it was easy to use, I would definitely use it! :)

Hai-Etlik
04-12-2012, 06:58 PM
Stipple-icious indeed :). Most of this goes a bit over my head, I fear ... but if it was easy to use, I would definitely use it! :)

I'll probably try to wrap some kind of interface around it when I've got it cleaned up and tested. For now though, here's a test of a stippled coastline effect.

43970

Hai-Etlik
04-14-2012, 05:20 AM
By using a function of distance inside the polygon for the density, making a simple arc shape as a stipple, and rotating it to face the nearest edge, I managed a fairly good looking forest symbol. It's not perfect, but I can probably improve it a bit.

44006

Lukc
04-14-2012, 05:30 AM
It's quite impressive even as it is!

Hai-Etlik
04-24-2012, 01:34 AM
This should probably get moved to the new Programming forum.

Gidde
04-24-2012, 12:21 PM
Moved as requested :)