Monday, July 6, 2020

A Meandering Subject

For the past few months I've spent some time away from Dragons Abound to pursue other hobbies and interests.  I've had a surprising number of people contact me to ask about my well-being.  I am very touched that people care enough to inquire!  I'm perfectly fine, but I find that (for me at least) “Forever Projects" like Dragons Abound work best if I allow my attention to be pre-empted by other projects and interests.  Sometimes I come back to the original project, and sometimes I don't, but I think that's better than getting caught up in trying to meet some preconceived notion of what I should be “accomplishing."  I have some much longer thoughts on Forever Projects that I'll try to post soon.

In the meantime, I recently had some thoughts about rivers and decided to spend a little time on that topic.

This map excerpt illustrates one aspect of Dragons Abound's rivers that bothers me.  Rivers often have stretches of wiggles as you see on the right-hand branch of the river in the plains.  This happens because the rivers are drawn from the center of one Voronoi polygon to the next, and three adjacent centers are almost never collinear, so rivers always have a kind of snaky path.

To some extent I can eliminate this by smoothing the river's path before drawing it.  In fact, the example above has been smoothed.  Without smoothing it looks like this:
You can see that smoothing has already greatly improved the look of the river.  

One possible solution is to increase the density of the Voronoi polygons that underlie the map.  The river will still wiggle, but at a finer scale that will be much less noticeable.  
Here (at 150%) you can still see some wriggles, but they're less noticeable and essentially invisible without some magnification. However, this solution creates other problems, most noticeably performance.  In this case I quadrupled the number of underlying polygons and increased the runtime by about 10x.

A better solution is to remove the river's strict tracing from the center of a Voronoi polygon to a neighboring polygon.  I'd like to do this in a way that eliminates the small wiggles while retaining (as much as possible) the overall path of the river.  Conveniently, there's an algorithm to do exactly this -- Visvalingam's algorithm.   I've written about this algorithm previously, when I used it to (ironically) simplify river paths when attaching labels.  There's a detailed explanation in that previous posting, but the simple version is that algorithm removes the point that creates the least change in the path.  You then do that repeatedly until you (say) remove 50% of the points in the path.  This has the effect of removing the highest frequency “noise" first.  Here's the river with 70% (!) of the path removed:
Visvalingam's algorithm is so good you have to remove a surprising amount of the path to make a noticeable difference, but you can see that it has retained the shape of the river and the broader curves while eliminating the wiggles.  Unfortunately, it has created a new problem.   One of the junctions of two rivers is now wrong, and the joining river overshoots.  This happens because the point where the two rivers joined has been removed.  To fix this problem, I have to modify Visvalingam's algorithm so that it doesn't try to remove any point where rivers join.  I already have that fix in place for the smoothing algorithm, so it's mostly a matter of applying the same logic.
Now the wiggles are gone but (at least to my eye) the rivers lack character.  They're reasonable, and they look a lot like other procedurally-generated rivers, like these from Azgaar's generator:
Most procedurally-generated rivers look like wandering lines with some side-to-side perturbation.  Real rivers seem to have more radical bends to them.  For example, this is a stretch of the New River in Virginia:
Note how the river bends so much that it actually reverses direction four or five times along this stretch.  There's nothing particularly unusual about this stretch of river.  You'll see this on almost any river you examine.  I actually picked the New River because it is (ironically) the oldest river in the US, and I figured it would have fewer bends than younger rivers.

In the example above, the New River is winding around hills.  Where the terrain is flatter, rivers can form meanders with even more dramatic bends:
But you'll rarely (never?) see this sort of river on a procedurally-generated map.  There are a number of reasons, but the primary reason is that procedurally-generated terrain only looks realistic at certain scales.  It doesn't have the right characteristics for drainage that mimics the real world.  And most procedurally-generated worlds don't implement realistic river erosion, either.  Whatever the reasons, the Dragons Abound rivers don't have realistic bends and twists, so I want to see if I can add some.

The first difficulty is that I have to recode the representation of rivers.  Currently, rivers are generated as a sort of linked list between Voronoi locations.  It's only when the river is being drawn that it is converted to a path.  In order to add more realistic curves to the rivers, I need to do is convert the rivers to paths immediately after they're created rather than right before they'd drawn, and then use these paths for the rest of the map creation.  This isn't too hard conceptually, but it involves recoding in a number of places.

[After a few sporadic days of refactoring.]

For various uninteresting reasons, that was much more difficult than it should have been, but the refactoring improved the code a bit, so it was (perhaps) a good investment.

Before I get to work on meanders, I want to see about adding some variety to the width of the river.  For various reasons having to do with the way terrain is generated and smoothed, the width of rivers tend to be smooth, slowly increasing curves, as can be seen in this example:
While there's some variation here, it's generally a pretty smooth curve.  To add some interest, I'll vary the width slightly using a noise source.  Here's an initial attempt:
That's a bit too extreme a variation.  After tweaking the noise parameters a bit to get something I like a little better:
So that adds some interesting variation to the river.  One minor problem is that these width variations are always symmetric, but if that bothers me enough I'll address it later.

Now that I have the river as a polyline, I can look at adding curves to the river.  In the real world, the basic process that creates meanders is pretty simple -- a combination of erosion on the outside of curves and deposition on the inside of curves.  
As water moves through a curve, the water at the outer part of the curve pushes against the bank and erodes it away, causing that bank of the river to move outward.  At the same time, the water moves more slowly on the inside of the curve, which gives any material in the water a chance to settle out, so sand and other materials get deposited on the inside of the curve.  The result is that the curve keeps shifting farther out.

I had a good idea of how to implement this, but coincidentally as I was working on this, Robert Hodgkin released a page describing his Meander project, which contains a better description of my idea than I could have written myself, so I encourage you to read his page.  The “TLDR" is to move each point on the river towards the outside of the current curve and also in the direction the river is flowing at that point.  By modifying the way these two elements combine, you can create various kinds of meandering.

If you read his explanation, Robert's method depends on something he calls the “modified bitangent" of the path of the river.  These look like this:
These lines are perpendicular to the path of the river, point to the outside of the curve, and their length is proportional to the amount the river is curving.  

I have a routine to calculate the normals of a polyline, which are similar but not quite the same:
These vectors are normalized to a length of one and don't always point to the outside of the curve.  To get to the modified bitangent, I have to calculate the curvature of the river at each point, and then scale the vector by that curvature.  To calculate the curvature, I use Menger's Curvature which looks very complicated but is actually simple to implement.  It's also a signed curvature, which means that negative curves will be inward and positive curves will be outside (or vice versa).  The last thing I have to think about is the range of the curvature.  If you look at Robert Hodgkin's example above, it's obvious that he is limiting the curvature measure -- all of the curves below a certain radius have the same length bitangent.  This is necessary because the curvature can have a large range and we don't necessarily want to apply thousands of times more erosion force at one point in the river than in another.

With the curvature measure implemented and forced to a limited range, I can multiply the normals by the curvature to get the “modified bitangents."
However, these modified bitangents are only one part of what I need.  The other part is the tangent.  As it turns out, to generate the bitangent I generate the tangent and rotate it 90 degrees, so conveniently I already have the tangents.  It's a little harder to visualize the tangents because they point straight down the river:
The two vectors are then combined into a vector that points somewhere in-between the two:
This combined vector shows the direction (and scaled distance) the path of the river will move as the curves erode to create meanders.  (Note that combining the tangent and the bitangent this way is equivalent to just rotating the tangent vector 45 degrees.  But it's perhaps easier to visualize this way.)

A couple of things to note about the meander process.  First of all, it's an iterative process.  I need to change the path of the river a little bit according to the combined vectors, then recalculate the vectors and repeat.  If you try to do it all in one shot, you just get a weirdly exaggerated version of the original path.  Second, this process will change the length of the river.  If I want to keep the same uniform distance between points on the river, I'll need to resample the path or add in new points where the existing points have grown to be far apart.  Lastly, there are some points on the river I have to keep the same -- notably the spots where two rivers join each other -- or else I'll have problems where the rivers join.

To start with, I'll do a single iteration at the scale of the visualization and see what that looks like.  Before meander:
After meander:
You can see that the meander process is starting to exaggerate curves in the river.

Here it is with 10 iterations, with smoothing and re-interpolation between each iteration:
It's instructive to vary the direction of the combined vector and see the results.  Here's a version using 90% bitangent and 10% tangent:
This exaggerates the curves.  (And as you would expect, 90% tangent adds only small curves.)  Increasing the strength of the vector also exaggerates the curves:
All these examples have looked mostly okay, bad things can happen when meandering:
This is obviously exaggerated, but illustrates a couple of different problems.  First, meanders can cause a river to cross itself or another river.  Second, meanders can cause problems where rivers meet other rivers or enter the ocean, by creating unrealistic paths.  Multiple approaches will be required to tame these various problems.

I'll start off by avoiding meanders not just where rivers join other rivers or the ocean, but also for a distance on either side.  The easiest cases to handle are the start and end of the river.
The river now meets the ocean cleanly, but there's an abrupt and obvious transition where meandering kicks in.  The solution is to have a “mask" that tapers in the meander:
Here the last part of the river is not meandered at all and then the next part slowly gets more meander.  Now I need to apply the same masking principle to all the joins on the rivers.
Now let me address rivers crossing themselves.  When this happens, the river can be repaired by removing the loop and adding a new point where the intersection occurred.  If I step through the river a segment at a time and see if the current segment intersects any of the later segments, that will provide the new intersection point as well as all the segments that can be eliminated.  In the real world, when this happens the cutoff portion of the river becomes an oxbow lake.  For my purposes, I'll just eliminate the cutoff.
If you compare this map with the one two above, you'll see a river loop has been removed in the area circled in red.

Dealing with rivers crossing other rivers is more difficult.  Here's an example:
Inside the circled area a river crosses one of its tributaries several times.  If this were to happen in real life, the two rivers would join at the crossing point, removing the downstream portion of one of the rivers.  That would be very difficult to implement in Dragons Abound, so instead I'll simply detect when this happens and reject that meander.  A second difficulty is that there can be quite a few rivers on a map, so checking all of them for intersections after every meander iteration will likely be slow.  To address this, I'll only check to see if a river intersects with a river it joins to.  It's very unlikely that a river will intersect with a river that it doesn't join at some point; but if this happens a lot I'll find a way to deal with it.

Here's is the same map with the meanders stopped before they created an intersection:
Now the rivers get very close to each other but do not cross.  However getting very close is not very realistic either, so let me adjust the code to create a buffer between the rivers.  The basic idea is to notice when part of a river is getting too close to another river and freeze that part so that it cannot be meandered further.  I can extend that same idea to self-intersections, so that I don't get spots like in the lower right of the above map where the river is so close to itself the border is lost.  Technically it doesn't intersect, but it gets drawn incorrectly.

With that in place the meanders look like this:
The guardrails do a pretty good job of keeping the rivers from getting into unrealistic paths because of the meanders.  Now I need to think about how I want to use meanders.

Obviously I don't want to meander every river to the extent shown in the examples above.  Meanders ought to be a sort of “special interest" feature like swamps or a deserted coast line.  I could achieve this by treating meanders the same way I do deserted coast lines -- at most one on a map, and often none.  However, unlike deserted coast lines, meanders are infinitely variable, so another possibility is to use only small amounts of meander on most of the map and significant meander in only some places.

In real life, meanders form in river valleys where the down-valley slope is gentle.  Dragons Abound has a measure of slope for each segment of a river, so I can try using that to control the amount of meander applied to the rivers. To start with, I can restrict meanders to the flattest quarter of the rivers:
A small amount of meander is applied to all rivers, but only the center part of the Fine Bight River gets fully-developed meanders.  I've also added a parameter so that on any map at most one river gets the full meander treatment.  A small improvement is to use a noise map to control the amount of base meander applied to rivers.  This will result in rivers in some parts of the map remaining straight while others will develop some gentle curves. 
Here the main meanders remain on the upper Jellyfish River but the Kaumgun River has had it's curves gently exaggerated.

Testing on a different map reveals a problem:
Tributaries are getting detached from their rivers.  Some debugging reveals that my calculations for curvature are broken if two adjacent points on the river are the same; that's fixed by filtering out repeated points, but the above problem remains.  After a couple of days of increasing intense debugging, I finally found the error in a piece of utility code that checks where to not move the rivers.  I had assumed that code was correct (it has been around a while) but it wasn't -- a check of the code base revealed that I'd never actually used it before.  Oh, well.  Don't assume when you are debugging!

With that debugged, meanders are working on this test map as well:

With the meanders more-or-less working (I tend to tweak features for quite a while as I study them more) the next (and last step for this blog post) is to work on naming.

One problem with naming is immediately evident: meandered rivers will never get a label.  This is because rivers use path labels that (more-or-less) follow the river, and with very sinuous rivers the label can never get snug enough to the river to warrant display (or at least not along the sinuous part).  Second, I'd like meandered rivers to get a name that reflects the character of the river, e.g., something like “The Meanders" or “Snake River."  There are a few names like this in the river name generator, but of course they won't necessarily come up on the meandered river.  Finally, in the case (as above) where the meandered river later straightens out and continues on, I'd like to give the meandered part a separate name from the rest of the river.

Since I'll later need to treat the meandered section of a river as a separate river, I'll break it off from the rest of the river and actually make it a separate river.  Then I can give that river its own name.
Unfortunately, this breaks the connections between the rivers and tributaries flowing to the sea, so that the meandered river just ends abruptly and the remainder of the river thinks it is starting from that location.  Fixing that will be very difficult / impossible, so I will have to seek a different solution.

Instead, I will mark the area of the river that has been meandered and save the original river path.  Then when I get to naming I'll add a second name to the meandered portion of the river.  That gives me this:
For the meander, I let the label overlap with the river and try to center it somewhere roughly in the middle of the meanders.  This works okay, but I might have to tweak it a bit in the future if it is too hard to distinguish.

In the map above, the river name was hard-coded.  I need to be able to generate a variety of names for meanders.  In this case, I generate two kinds of names.  One kind is variants of  “The Meander" using different synonyms for meander, both obvious ones like Rambles and archaic ones like “Cringle-Crangles."  The other kind is variants on “The Snake River" with different synonyms for snakes and other snake-like things.
Here it has been called the “Anaconda."  Technically, this is still part of the Moor River, but given how meanders are created, there will always be a join between the meandered part of the river and the other part, so the names don't clash.

In the map above, you might notice that some of the meanders go into the forests, while elsewhere the forests avoid the rivers.  This happens because the forests look at the actual water flux to decide where to avoid, but of course in creating the meanders I've moved the river to places where the flux is low and there wouldn't normally be a river.  So I need to fix how forests detect rivers to a method that looks at the actual river paths.
With that in place, the forests now properly edge back from the meanders.

That's a good stopping point for now.  Next time ... well, I'm not sure what, but don't expect weekly updates as in the past!

Wednesday, February 12, 2020

Creating a Pencil Effect in SVG

Dragons Abound produces maps in SVG, which is a vector graphics format.  Vector graphics have a lot of features (such as lossless zoom) that are nice for maps.  And vector graphics are good for producing crisp, well-defined lines like an ink stroke:
On the other hand, vector graphics are not very good at producing textures with a lot of non-repeating fine detail.  In vector graphics, each drawn element is represented with a description of its size, shape, location, color and so on.  To represent a lot of fine, non-repeating detail, you need to describe lots and lots of elements.  Something like this pencil stroke
would require many tens of thousands of different elements.  Basically each little blob of gray in that image would be separately defined.  Other things, like blurred images, are even more problematic.

This is a pretty big limitation on vector graphics, so SVG has added some workarounds to let you reproduce some of these texture effects more efficiently.  I'm going to explore using some of those SVG features to create something like a pencil line.  Of course, there are many other more sophisticated approaches to replicating pencil strokes.  Academic papers have been written on the subject.  But I'm hoping to create a fairly simple filter that has an acceptable result.

As always, my preference would be to borrow or build on a filter that someone more talented than myself has already created, but in this case I find that there's a surprising paucity of vector pencil filters to use for inspiration.  (Cue ominous foreshadowing music: There may be a reason for this.)  So I'm pretty much on my own.

I've posted previously about Dragons Abound's capabilities to create “hand-drawn" lines.  This was concerned primarily with avoiding mathematically straight lines and instead creating lines with subtle variations that look more like they were drawn by a human hand.  You can see some of this in the mountain illustration above.  This works fairly well to create an ink illustration style, but it doesn't work very well to create a pencil line, because it lacks the pencil texture.

If you look at some pencil strokes, like the example above, or these:
you'll see a number of features that distinguish pencil strokes from ink lines (or computer-drawn lines).  Most importantly, they have a texture caused by the way a pencil interacts with paper.  Paper has a grain and the pencil tends to deposit graphite onto the high parts of the grain and leave the lower parts white.  Rough-grained paper results in more obvious texture; something like illustration board is so fine-grained that it imparts almost no texture.  Second, the edges of pencil lines are somewhat indistinct.  Again, this is largely caused by the irregularities in the paper and in the pencil point itself, which result in varying amounts of graphite being deposited along the edge of the line.

(Of course, there are other effects as well.  Pencil builds up on itself and so can appear darker where strokes cross.  Strokes themselves vary in pressure and this can change the darkness of a stroke along its length.  But for the purposes of this posting, I'm going to be focused primarily on trying to recreate the revealed paper texture.)

To get started, I will set up some plain gray lines:
Here I've “hand-drawn" lines that are 4, 2 and 1 pixel wide.  Unfortunately, SVG effects tend to look different when applied to different width lines, so I want to compare the effect on different sizes.

The primary capability SVG offers for adding texture effects is called filters.  Filters are applied after a vector object is drawn, and they change the way the object is presented -- like looking at the object through a filter, hence the name.  Typical filters can do things like change the color of the object, add noise to the object, etc.  Filters are a fairly complicated topic with a complex syntax, so I won't be offering a full tutorial here on how to use them, but I'll try to give enough detail to make it clear what I've done, and at the bottom of this posting I'll provide a link to a Codepen with the filter so you can play around with it yourself.

To begin, I'll try to change the edges of the lines so that they are not smooth but have irregular edges similar to paper grain.  I'll do this by moving the pixels in the line around.  The filter element that does this is called “feDisplacementMap" and it moves each pixel around based upon the values in a different image.  Since we want each pixel to move around in a random but coherent way, we want to feed noise into feDisplacementMap to control the movement.  Fortunately, SVG provides another filter element call “feTurbulence" that is specifically for producing noise.  So we can combine those two filters to roughen up the edges of the lines.
The amount and roughness of the line can be controlled with parameters to the displacement map and the noise generation.  Unfortunately, the displacement is in absolute units, rather than relative to the line size.  Here I've tweaked these to find something that looks reasonable for all the line widths, but you can see a problem when I increase the scale of displacement:
Now the displacement is big enough to start moving the entire line around, rather than just tweaking the edges.  This effect is magnified on thinner lines.  In this example, the 4 pixel line still looks mostly like the edge is rough, while the two pixel line has had obvious distortions added to it.  So I have to pick a value that doesn't create distortion in the thinner lines.

When I zoom out to regular magnification, this is what the effect looks like (after some tweaking to improve the effect):
At this scale, a lot of the rough edges become spots and speckles.  It's not an entirely unpleasing effect and is somewhat reminiscent of a pencil line.  (However, in general SVG filters seem to have scaling problems -- in many cases they look good when zoomed in but look like they've been put through a poor resizing algorithm when zoomed out.)

Here's what this looks like used to draw mountains (pencil effect to the left):

That's not terrible, but it does have some sharp artifacts that look a little odd.  And when this is applied to thin lines close together, they end up overlapping and merging:
Again, this is not entirely terrible, and the shadows in the pencil mountains end up looking very much like they'd been shaded in with pencil, if that's an effect you want.

This approach adds roughness to the outline of the pencil stroke, but it doesn't change the uniform color of the stroke.  Real pencil strokes have texture inside the stroke as well, as the graphite colors some spots on the paper more than others.

To add texture inside the stroke, I will use an SVG filter that generates noise and then combines the noise with the stroke:
Here in close up you can see how the inside of each stroke is now filled with a pseudo-graphite texture.  Here's what it looks like at normal scale:
This doesn't look too bad, particularly on the thicker lines.  Here's what this looks like used on mountains:
It is not as good at this scale.  Note that this filter also reduces the darkness of the lines; this is a natural result of adding white noise to the lines.  To some extent this can be mitigated by increasing the contrast of the noise, so that some parts of the line are made darker to compensate:
But since the line colors are already pretty dark to start with, this eliminates much of the “pencil" effect.  So if I use this, it will have to be tweaked to produce a pleasing balance.

Obviously, both of these can be combined.  This looks pretty good close up:
It has both the rough edge and the interior texture we expect in a pencil line.  At normal scale it is not quite so good:
because of the sharp artifacts introduced at this scale.

A good trick to make this texture look better is to add a paper texture to the background:
The eye now sees the texture consistently across the image.  Even at a pretty subtle level, this helps trick the eye into believe that the texture in the line comes from the paper.

Here's an example of using this filter on a map (with a paper texture):
Overall this isn't too bad, although on detailed inspection it looks as if there's simply been noise added everywhere.  At 200% artifacts are more evident:

Another way I might create a rough edge for a pencil line is to draw the line multiple times with slightly different perturbations and a lowered opacity.  In the center of the line where the multiple versions overlap, the density will be something like the original line; at the outside edges where sometimes only some of the lines are showing there will be lower opacity and less distinct edges.

The general way to do this with SVG filters is to use feTurbulence and feDisplacementMap together to create a perturbed version of the line, but to do this multiple times and then combine them all at the end with a series of feBlend primitives.  If we blend (say) three copies, we have to also lower the opacity of the lines appropriately.  (I'm not entirely certain how to calculate the appropriate opacity, but I think it might be the cube root of the luminosity of the line.)

That produces an effect like this (with three lines, closeup):
There are a couple of drawbacks with this approach.  The filter has a fixed perturbation, so it has more impact on narrower lines, and you can see that the 1 pixel line is completely separated at points.  Secondly, this is a fairly complex filter that creates three separate perturbations and merges them; this might be very slow on a big complex image like one of Dragons Abound's maps.

Here's what this looks like at normal scale:
This doesn't look exactly like a pencil outline to my eye, but it does do a better job of eliminating the sharp artifacts from the other approach.

This can be combined with the interior texture filter from above to add texture to the inside of the pencil lines, and the paper texture:
Here's what this looks like used on mountains:
This filter tends to spread out the lines more than the other filter -- effectively making them thicker.  Sometimes this generates a sketch-like effect with multiple lines that isn't entirely displeasing.

Here's an example of using this filter on a map:
This maintains the original darkness better than the first filter, and while it doesn't look exactly like pencil to my eye, it isn't entirely unpleasing.  Zoomed in to 200%:
This filter largely avoids the sharp artifacts of the first filter when zoomed in.  The overlapping lines effect on narrower lines (such as the forest) starts to look pretty artificial, but broader lines like the mountain and rivers still look good.  However, the internal noise is almost entirely lost within black lines like the river.

I have put both of these filters up on Codepen so you can try them out yourself.  You can find the first filter here and the second filter here.  I encourage you to play around with them and try to improve them -- and if you do come up with something better, please let me know!  I'd love to have a really good pencil filter!