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]);

    };

    npl.push(p2);

    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.