Sunday, February 14, 2021

Knurden Style: Labels & Etc (Part 6)

In previous postings, I implemented the major portions of Daniel Hasenbro's Knurden map style, the mountains and the forests.  I also previously handled the shoreline and the basic colors.  There remain a few more elements to implement.

One important element is the labeling.  The excerpt above shows examples of the important label types.

The font used for the labels is one of the IM Fell fonts (DW pica).  The city labels are filled in a light reddish brown, and stroked in a dark red brown.  There are two other potential elements to labels.  The first is a mask that blocks out the background around the letters; these labels do not appear to have any masking.  The second is a halo.  This is usually a white blur that surrounds the letters and also helps separate them from the background.  The Knurden city labels have a narrow, somewhat transparent white blur.  Matching the style is then a matter of trying different colors, sizes, blurs and so on until I get something that looks approximately the same.
The colors are still a little bit off because fonts are treated somewhat different in SVG than in Photoshop, but it's a fairly close match.

The labels for woods use an italic version of the IM Fell font.  The letters are outlined in the same dark brown but filled with white, and there does not seem to be a mask or halo.  The forest labels are also fairly small, about 60% or so the size of the town labels.  But here I run into a problem.

The italic version of the IM Fell font has characters that are a little too skinny at the size I need for the forest labels.  In theory, that's not a problem, because you can change the thickness of fonts by using the CSS “font-weight" style.  By setting the font-weight appropriately, I can get a thickness that is readable and roughly matches the Knurden map.  However, I discovered that setting font-weight breaks the font stroke (outline).  You can make the font fatter, or you can have an outline, but you can't have both.

This is probably because font outlining is done using the generic SVG shape stroking capability.  The text is just treated as an SVG shape and then the perimeter of the shape is stroked to create an outline.  Font weight, on the other hand, is a CSS style feature that presumably happens later in the display pipeline.  If the shape is already stroked, it can't then be made fatter.

As it turns out, there is a CSS style to stroke a font as well, called “-webkit-text-stroke"  So you might guess that it would be possible to use this in combination with font-weight to get weighted, stroked text.  Unfortunately you'd be wrong, as -webkit-text-stroke doesn't seem to work on SVG text.

Another possibility for creating an outline effect is to put two copies of the same text on top of each other, and make the back copy thicker using font-weight so that it shows around the edges of the top copy.  Then make the top copy the fill color and the bottom copy the stroke color, and it will appear that you have stroked the outside of the text in a different color.  And while this does work, it turns out that the difference in thickness between the heaviest and the lightest font weights is still pretty minimal, so that the stroke is very thin.  
Just a hair of black peeking out.  So on a practical level, this doesn't work.

Yet another possibility is to make the bottom copy bigger by changing it's size.  The problem with this idea is that when the font changes size, the individual characters don't stay centered on each other.  The space between characters also gets bigger, and this throws everything off.
In theory I suppose you could handle every character separately and line them up correctly, but ... not going to go down that rabbit hole!

After much experimentation, I found yet another way to get the desired effect.  There's a little-known attribute for SVG text called “paint-order" which can be used to modify the order in which the fill, stroke and markers get drawn.  It turns out that when the stroke is drawn first (instead of the fill), “font-weight" starts working!  
I'm not entirely sure of the reasoning here, but I'll take it!

(I later thought of another way to achieve this effect.  Draw the text first with a thick outline, and then draw the text with no outline over the top.   That might work.  It seems there are many ways to skin this particular cat -- I'm glad at least one of them works!)

With this fix in place it's straightforward to get a reasonably close match:
There are only two river labels on the Knurden map, but they use an interesting technique that is used on other labels on the map as well:
For these labels, Daniel gets a kind of “negative" effect by using a transparent light color for the font and surrounding it with a dark halo.  This is fairly straightforward in Dragons Abound, although it takes a lot of tuning to get the colors close (if not exactly the same):
One problem with this style of label is that it can be hard to read on a busy background:
So I may tweak it a bit to address that at some point.

Ocean labels are much as river labels, adjusted for the ocean colors, so I won't go into any big detail on them.  Region labels are like forest labels, but not italic and in all-caps.

With labels done, I want to go back to forests and pick up an interesting little trick from the Knurden map.  Although forests are done as large masses, Daniel also scatters some solitary trees around the map:
As in this example, the trees are normally scattered around the edges of forests and also along rivers.  The solitary trees sometimes appear as clumps of two, or less frequently, three.

Implementing this was a bit more challenging than I expected.  Finding the border around a shape is not very easy or efficient, and in this case often creates a torus shape (a polygon with a hole in it) which is tricky to work with.  Eventually I settled on iterating over all the underlying Voronoi polygons in the land and deciding for each one whether or not it was in the border area, and then whether or not it should contain a tree clump.  At any rate, after that I have isolated trees around the edges of the forest masses:
Now I can do something similar for rivers.  I'll look for locations near rivers that also have above average precipitation.  (As an aside: I don't actually keep the precipitation values by the time I'm generating these trees, but I do have the biomes for each location, so I can use the biomes as a proxy for the level of precipitation.)  That adds a scattering of trees alongside fertile rivers that get a lot of rainfall:
The last thing I want to replicate from Daniel's map are his rhumblines.  Normally rhumblines radiate from spots in the ocean, or from a compass.  Daniel has done something interesting by making them come from the middle of the land.  This makes them useless as navigational aids, but it looks pretty cool.  It looks a little odd to have these radiate from the exact center of my (square) maps, so I'll offset the lines upward a bit.

The last thing I want to replicate is something Daniel does on the larger islands:
He puts a white circle around the island, and fills the circle with transparent white to lighten the background.  I don't think this means anything; it appears to be just a decoration.  Still, it looks neat and I'd like to be able to duplicate it.

Picking the islands to decorate is an interesting problem.  Daniel doesn't decorate all of the islands, generally avoiding those that are in clusters with other large islands or too close to the mainland.  He also doesn't do this decoration on two islands close to each other.  Here's my first attempt to pick out islands:
I have a test to make sure an island is not too close to the mainland, but I've got the polarity of the test reversed, so I'm picking islands that are close instead of far.  Here's a second attempt:
This is better, but the upper island is too close to another big island.  I want these to be somewhat isolated islands (at least from other big islands).  Filtering for that gets me this:
Now I just need to adjust the circle and fill:
That's a pretty reasonable approximation.

There are a few other features of Daniels' map that I won't be reproducing.  His city icons are little works of art:
And while Dragons Abound's city icons are not terrible, they're not nearly as nice as this.  (But that's something I hope to revisit!)

Daniel also does something nice with his country borders by adding a halo effect:
I rather like that, and stylistically it fits in well with his labels.  Dragons Abound does do country borders and I could add this effect fairly easily, but I'm not happy with how Dragons Abound places borders so I don't use that at the moment.

Finally, there's a coast decoration Daniel does with a looping line on the inside of the coast:
That's very nice but I don't have any good ideas on how to easily recreate it, so I'm going to pass on that as well.

Next time, some complete maps!

Wednesday, February 3, 2021

Knurden Style: Forests (Part 5)

 In the last posting, I created individual trees:

Now I'll work on drawing forests.

In the Knurden map, forests are blobs with individual trees around the edges (and other decorations):
At a simplified level, these forests are a solid color surrounded by a ring of trees.  But drawing this isn't so easy, because the solid color in the center of the forest obscures the trees on the back edge of the forest and is in turn obscured by the trees on the front edge of the forest.  We can't even draw the back trees and then draw the solid color on top of them, because that would cut a straight edge across the back trees!  So how can we draw this effect?

My breakthrough realization was that the trees on the back edges of the forest are a lot like the partial trees in the middle of the forest.  I could draw in the solid color, and then draw “half trees" along the back edges, and then full trees along the front edges.

To start, I have to figure out how to draw a half tree.  To a first approximation, these half trees are like shortened full trees without the bottom part of the outline.  I'll tweak the shape and remove the outline:
But here the dark shadow on the right side of the tree goes across the bottom, which makes these look like complete short trees.  So I'll adjust the shadow so that it doesn't go across the bottom, so the bottom part of the tree looks more cut off.  And I'll draw the top half of the outline.
That looks pretty good (and this is somewhat larger than the trees will be on the map).

Before I can try these half trees out I need to fill in the solid color blob in the middle of the forest.  These really aren't a solid color on the Knurden map but I'll get to that eventually.  For now I'll just get the solid blob down.  This isn't too hard, because I have another forest style that also starts with a blob of color.  But even if I didn't, this is straightforward: identify the area where the forest will be and fill it with color.
Here I'm using a darker version of the land color; I'll probably tweak that eventually.

Now I need to draw the half trees on the “back" edge of this polygon.  But how do I tell which edges are on the back of the polygon?  That turns out to be surprisingly easy.  Imagine that you're walking around the polygon clockwise:
You'll realize after a moment's thought that whenever you're walking to the right, you're on the back edge of the polygon.  (This is one reason it is useful to have your polygons consistently clockwise or counter-clockwise ordered.)  So I can walk around the polygon clockwise, dropping half trees whenever I find myself going to the right:
One thing to note is that this will drop the trees in the wrong drawing order.  The trees need to be drawn from back to front, and this will often drop trees from front to back.  So after creating the trees you have to reorder them from back to front before drawing them.

The other half of this is to draw full trees on the rest of the polygon.  One subtlety to note before we do that.  Because the back trees are only drawn from the midpoint up, and they're drawn on the polygon, the midpoints of those trees are on the polygon.  So I need to do the same thing with the full trees. I don't want to draw them on the polygon, but shift them down some so that their midpoints are on the polygon as well.  Otherwise the front trees will look taller than the back trees.
Overall, this looks pretty good, but there are a few gaps.  After some debugging work, it turns out these are due to a coding error in my routine to interpolate a polygon.

To place the trees regularly around the edge of the polygon, I'm taking the original polygon and interpolating it to create a new polygon which has a point at every place where I'm going to place a tree.  Interpolating a polygon is a little tricky.  Imagine that you have a polygon and you're going to interpolate it so that you have points at some fixed interval instead of the original points:
Here I have a simple two segment polyline in black, and then I've marked out along it in red new points at a fixed interval.  But what happens when I create a new line based on those points?
Whoops!  I've cut off the original corner.  Less obvious but also problematic is that the last segment is much shorter than the other segments.  We really want an interpolation routine that (1) maintains all the original polygon points, and (2) equalizes the intervals between the new points.  It isn't possible to do both perfectly, but a reasonable compromise is to interpolate each line segment individually, selecting the number of pieces for the segment to get as close to the desired interval as possible.  That gives you something like this:
Now I've retained all the original points, and although the points on the second segment are further apart, I've avoided a very short interval right at the end of the line.

So how do you subdivide the segment?  The basic idea is to divide the length of the segment by the desired interval, and then round that number to the nearest integer.  That gives you the number of divisions, and you use that to calculate the actual interval.  (In the worst case, the actual interval will be +/- 50% of the desired interval, but it will usually much closer.)  Since this is a simple line segment, you can create the intervening points using the slope of the line.  Here's what that looks like in Javascript:

// Divides a line segment into step-sized chunks
function divideLineSegment(p1, p2, step) {
    // How many steps in this line?
    const n = Math.round(Utils.distance(p1, p2)/step);
    const dx = (p2[0]-p1[0])/n;
    const dy = (p2[1]-p1[1])/n;
    const npl = [p1];
    // We do this n-1 times so that we can use p2 as
    // the last point just to be sure it doesn't move
    // because of a rounding error.
    for(let i=1;i<n;i++) {
npl.push([p1[0]+dx*i, p1[1]+dy*i]);
    return npl;

Note the trick here that uses the last point rather than calculate it from the slope.  This makes sure the point doesn't move due to a rounding error.  That's important when we're trying to get things to match up precisely on the screen.

Fixing that routine fixes most of the gaps:
Some gaps still arise where line segments are an awkward length, but happily the effect is actually better with occasional small gaps.

There are a couple of other elements needed to complete the forests.  To give the solid interior of the forest some variety, Daniel does a couple of things.  First, he scatters some treetops throughout the forest.  These are basically the same as the half-trees used to line the back edge of the forest, but to my eye a little bit shorter.  To create a good scatter of trees, I can use a Poisson sampling, as I've done before in similar cases.

That gets me to this:
The second thing Daniel adds are some patches of lighter and darker color, as if you're seeing the highlights and shadows of trees without the outlines.  However, the colors are not paired light + dark as they are in a tree, just scattered about.  I can add these by reusing the Poisson sampling to place light and dark patches.  He just draws these as short vertical lines, so I'll do the same.  The contrast on these is not as obvious as on the tree shadows and highlights, so I'll dial that back as well.
This looks okay, but this sort of thing -- a small, irregular dash of color -- is where SVG is weakest.  These spots lack any sort of character.  I've tried adding a blur, but that is not an improvement.  They're not terrible (especially when less zoomed), so I'll certainly keep them in, but I wish I could do something a little better.

Moving on, the last thing Daniel does is to give the solid color in the interior of the forest a slight light to dark gradient in the direction of the lighting.  This is somewhat harder to do in SVG because gradients are based on the rectangular bounding box of the polygon, meaning that they don't follow the contours of the polygon.  So instead of having the left edge of the polygon be lighter in color, you have the left area of the polygon lighter in color.  Which is not the same thing at all, but if the gradient isn't too obvious it still looks okay in many cases:
A side-by-side comparison of the original forests to the DA version:
Obviously it's not a precise match but I think it's pretty close and the overall “feel" is not bad.

In the course of implementing these forests I realized I already had a couple of other tree styles that could be used to draw forests this way instead of the Knurden-style trees, if I just implemented the half-tree and tree highlights.  This turned out to be more difficult than I expected (largely because of a pernicious bug that took a long time to find) but the results are fairly good:
Here I'm using the “fluffy" tree style, and I've implemented a (fairly rudimentary) half-tree as well as the highlight patches for inside the forest.  You can see some problems (primarily the half-trees along the left edge of the forest) but overall I think it looks pretty good.  The colors are more muted in this style, so it isn't as “graphic" as the Knurden style.

Here's the same forest style using fir trees:
This works better (or at least I like it better), partly because the geometry of the fir tree is closer to the Knurden oval tree shape.  

Next time I'll do labels (*) and clean up some last details.

(*) I came back to this to do the last two hybrid forest styles, so you can see the labels are actually implemented in those screenshots.