Scribbled Notes

In a previous posting, I described how Dragons Abound make lines that look hand-drawn, and showed these examples:

One thing that still looks unnatural about these mountains is that the shadowed sides are too precisely shaded.  Although the shading lines themselves have a hand-drawn quality, it looks more like technical drawing than hand-drawing.  The precise outline caused by clipping the lines to the shadowed area also doesn't look good, particularly in contrast to real hand-drawn examples:

In these examples, the shading is drawn in with scribbles -- back and forth lines at roughly the angle of the mountain that do not adhere precisely to the shape of the shaded area.  This sort of scribbled shading is something I'd like to have in Dragons Abound.  To be honest, I really don't have any notion of how to implement this, so this posting will be more of a chronicle of my development process than a finished project.  I apologize in advance if it all comes to nothing. :-)

The first thing I do, of course, is to Google around and see if I can find an algorithm I can steal or adapt.  But it's pretty difficult to find any information on how to fill an arbitrary polygon with scribbles.  Apple actually has a patent on a method, but to be honest I don't think much of the approach.  Adobe Illustrator has a scribble effect, but that doesn't help me for obvious reasons.  I've put out a call for help on /r/GraphicsProgramming, so maybe that will yield results, but in the meantime I'm going to have to roll my own.  In general this seems like a pretty hard problem, but you can follow along and see how far I get.

To start with, I'm going to look at filling a simple triangle shape:

Often I tackle a problem like this by figuring it out for a simple case.  Sometimes that leads to insights that let me tackle the harder cases.  Sometimes it turns out that the simple case is good enough for what I need.

When I shade something like this by hand, I draw lines back and forth at roughly the angle of the hypotenuse of the triangle and slide my hand backward along the paper until I've filled the triangle.  So I'll try to implement a similar approach in software.  My general idea is to slide a "finder" line at the basic slant of the scribbles along in the x dimension and identify a sequence of points where the line intersects the shape:

These points are where my pencil turns around when shading by hand.  As you can see, at each step the line intersects the shape in two places.  The scribble is created by going back and forth between the points of intersection:

That looks like it could work -- at least for a convex polygon.  What happens if I don't have a convex polygon?

Here's a concave polygon.  In this case, the finder line intersects in four points instead of two.  In general, an infinite line should intersect the polygon in an even number of points.  (If the line intersects in an odd number of points, it means that one end of the line is inside the polygon.  [But see below for another case I figured out later in the process.])  In this case, I think I can draw two scribbles -- one for the first pair of points and one for the second pair of points.  (I'll probably have to sort the points by their Y value to keep the two pairs correct as the finder line slides along.)

At some point the number of intersecting points goes back to two.  At that point, I can stop drawing one of the lines and finish with the other.

It might be that continuing a line when the number of pairs changes creates problems, but if so a fallback option is just to start new scribbles whenever the number of intersection pairs changes.

Going the other direction -- from one pair of points to two pair -- is similar:  Continue the existing line and start a new line for the second pair of points.  

I can imagine nasty situations where all of this might break down, but I think I'll just push ahead and see how well this works in practice.

The first step in actually implementing this is to define the finder line.  The slope `mu` of the finder line will be specified by the user.  For intersecting with the polygon, it's handy to have the finder line in two point form:  `(x_s, y_s)` and `(x_e, y_e)`:

For the reason mentioned above, I need these points to be outside the polygon.  This can be accomplished by finding the minimum and maximum `y` values for the end points of the line segments in the polygon and then setting `y_s = y_min` and `y_e = y_max`.

Having defined `y_s` and `y_e`, the next problem is to figure out the range on the `x` axis where I am going to slide the finder line.  Ideally, I only want to slide the line through the points where it could actually intersect with the polygon.  It should be obvious that the first point of contact between the finder line and any polygon will be one of the vertices of the polygon:

To find the range on the `x` axis to slide the finder line, I need to intersect the finder line with each vertex of the polygon, project the finder line down to `y_s` and then find the minimum and maximum values for `x` in those projected points.  How do I do that?

Given the slope of the finder line `mu` and the coordinates of the vertex (`x_1`, `y_1`), I want to find the intersection of the finder line with the horizontal line `y_s`:

A little algebra shows that the point `x_i` is given by the equation:

`x_i = x_1 - (y_s-y_1)/mu`

The range of `x` values for sweeping the finder line can then be found by calculating `x_i` for each vertex in the polygon and keeping the minimum (`x_min`) and maximum (`x_max`) values.  At this point, I now have the slope `mu` of the finder line, the two horizontal lines that bracket the top and bottom of the polygon (`y_s` and `y_e`) and the range of `x` values to try (`x_min` to `x_max`).

Now that I have the finder line defined, how do I determine where it intersects with the polygon?  The straightforward approach is to intersect the finder line with each line segment in the polygon.  A trip to StackOverflow yields a Javascript function to intersect two lines in two-point form, which I have modified slightly here to correct a typo and to work specifically on line segments:

function line_seg_intersect(x1, y1, x2, y2, x3, y3, x4, y4)
{
    var ua, ub, denom = (y4 - y3)*(x2 - x1) - (x4 - x3)*(y2 - y1);
    if (denom != 0) {
       ua = ((x4 - x3)*(y1 - y3) - (y4 - y3)*(x1 - x3))/denom;
       ub = ((x2 - x1)*(y1 - y3) - (y2 - y1)*(x1 - x3))/denom;
       if (ua >= 0 && ua <= 1 && ub >= 0 && ub <= 1) 
         return [x1 + ua*(x2 - x1), y1 + ua*(y2 - y1)];
    };
    return null;
}

Now I can sweep a line over a polygon and find all of the intersections with the polygon:

One problem I encountered in running a few test cases is that sometimes this finds the same intersection twice.  This happens when the finding line exactly intersects a vertex of the polygon.  In that case, the the line intersects with both of the sides of the polygon that meet at the vertex (since they share that point), and the vertex point ends up getting added twice.  That's fixed by checking for duplicates before adding to the list of intersections.

After making sure that the intersection points in each step of the sweep are sorted by the y axis, I can then draw a line connecting all the points:

And a test with a different slope:

So far so good! Let's see what happens with a more complex polygon.

This test turned up another edge case:  Sometimes the finder line only intersects the polygon at one point.  This happens when the finder line intersects the polygon only a corner vertex.  As noted above, that produces two intersections, but they're both the same point, so the fix above that prevents duplicate points eliminates one of them, leaving just a single point of intersection. The fix is to just ignore the single intersection cases -- these points are always in a corner and drawing a line to them would run along the border of the polygon and look bad in any case.

Let's try a concave polygon:

Not so good.  You can see there's a spot with two pairs of points and that the scribble is messed up there.  (I haven't yet implemented the logic to handle more than two intersection points.)  Also notice how the line ends in the upper corner.   Sweeping the finder line with equidistant points doesn't mean the scribbles will be even spaced, because the scribble points are on lines with different slopes.  I hope that when using narrower, more packed scribbles this sort of problem won't be too noticeable.  In the meantime, let me see about the concave polygon problem.

To address this, I have to keep track of how many intersection points are being found on each sweep, and when that number changes, add new paths if it gets bigger, or retire existing paths if it gets smaller.  After that change:

You can see that there's now an orphaned one segment "scribble" where the concave intrusion broke up the main scribble path.  If I increase the density of the scribble lines and zoom in a bit, you can see the secondary path is now longer:

Let's try it with a different slope:

Darn it.  I suspect the problem here is that the wrong path is being continued.  I'd like to keep a long continuous path if possible, but when going from one to two paths or vice versa I don't see any obvious logic for which path to keep and which to drop.

As I mentioned earlier, the alternate approach is to restart all the paths whenever the number of paths changes.  Let me try that:

That fixed it!  The break is more obvious now, but at the scale I'll be using on maps I don't think it will be noticeable.  How about a more challenging example?

Not bad.  And the opposite slope?

Note that there are a bunch of scribbles that are just single straight lines because the number of intersection points keeps changing as the finder line is swept through the middle of the polygon.

However, there is an angle where the algorithm breaks down:

It wasn't immediately obvious to me what happened here, but after some analysis I realize that  the problem occurred where the scribble switches from two paths to two different paths.  Normally the algorithm notices that the scribble is on new paths because the number of paths have changed.  But in this case it can't tell, because the number of paths is the same.  I don't think this is likely to happen often (or even at all) in my case, so I'm not going to put any big effort into fixing it right now.

This posting has gotten long, so I'm going to break here and tackle making the scribbles look more hand-drawn next time.  However, I did do a "quick and dirty" version and used it to shade my simple mountains, just to get an idea of whether this effort is even worth it:

This has more of a the flavor of an architectural drawing than I'm eventually aiming for, but I actually like the way it looks.  At any rate, I think it shows that this approach has some promise for producing scribbles that look realistically hand-drawn!

This Is Where I Draw the Line

Having covered in some detail the world-building aspects of creating mountains, I'm now going to spend some time on how to draw mountains on the map, taking my inspiration from hand-drawn examples such as these:

The first step in getting to this goal is to be able to draw a line.  I like to set my sights high.

Dragons Abound draws maps using "Scalable Vector Graphics" aka SVG.  Unlike the more familiar raster graphics, vector graphics don't represent images as arrays of colored dots (pixels) but rather as a set of shapes.  The web browser (or whatever program displays the SVG) is responsible for figuring out how to translate the shapes into actual pixels for you view.

This makes it very easy to draw a line in SVG.  You just have to provide the start and end point of the line, and the browser takes care of figuring out how to draw from start to end.

Believe it or not, that's actually a screen shot of a line drawn with SVG.  This blog spares no expense in bringing you high quality content.

Drawing a (simple) mountain shape is then just a matter of drawing the appropriate lines:

Kind of a boring mountain, but you get the idea.

One obvious problem is that the lines are too perfect -- razor straight and precise in a way that only a computer can manage.  I'd like to have lines that look more natural, with the kinds of imperfections one sees in hand-drawn lines.

As it happens, there was an effort a few years ago to create plots in Python that would look like the hand-drawn plots Randall Munroe uses in XKCD.

Here's an example of a plot created by the Python code:

I think it does a pretty good job of making the lines look hand-drawn.  Even better, some benighted soul ported the Python code to Javascript and D3, so stealing the code for my own purposes is pretty trivial.

The key element of the code is a function called xinterp that takes a polyline represented as an array of points and interpolates it into a new line with jitter.  The code does a couple of clever things with adding the jitter.  First, the line is initially scaled into a standard coordinate system.  This keeps the magnitude of the jitter independent of the original coordinates.  Second, the jitter is applied in a direction normal to the gradient of the line.  This makes the jitter a natural "side to side" wobble regardless of the orientation of the line.  Here is an example of a jittered line:

As you can see it looks at least somewhat more hand-drawn.  But if I overlay the jittered line on top of the original line, a problem becomes apparent:

You can see that the black jittered line doesn't match up with the blue line at the ends.  This isn't a problem in creating plots, because they're all unconnected lines.  But it is a problem for me, because in some cases I will want to draw separate jittered lines and have them connect.  The fix is avoid adding jitter to the start and end points.  Occasionally this creates a little "hook" at the end of a line where a lot of jitter has to be eliminated, but as long as the magnitude of the jitter is kept small this is a minor problem.

With that fix in place, I can draw the same simple mountain shape using the "hand-drawn" lines.  Here's an example along with the original mountain for comparison:

The new mountain indeed looks more hand-drawn.  So far, so good!

Another feature of hand-drawn lines is the width of the line tends to vary.  That's a bit of a challenge in SVG because the width of a line cannot change.  So to draw a line with changing width, you have to split the line up into pieces and draw each piece a different width.  If you use a fairly small increment of change in width (around a quarter point works well for me) the line appears to be smoothly changing.  I have some experience of this because Dragons Abound can already draw rivers that smoothly grow in width as they flow toward the coast:

To start with, I'll create a line that smoothly varies between two widths.  Here's a comparison of three lines:  The first a standard SVG line, the second a "hand-drawn" line and the last a hand-drawn line that starts with a 3 point width and narrows to 1.5 points width at the end.

A narrowing line of this sort is typical in hand-drawing where the artist reduces the pressure of the pen as he makes a stroke.

Here's an example of the hand-drawn mountain with the narrowing lines, and a comparison to the previous versions:

And another example, with denser shading:

(And also an example of a line with "hook" at the end to compensate for jitter.)

Another obvious variant is to let the width of the line change semi-randomly.  In this case, I chose to let the width of the line increase or decrease by a quarter point at random intervals.  Here's a comparison of four lines:  The first a standard SVG line, the second a "hand-drawn" line, the third a hand-drawn line that starts with a 3 point width and narrows to 1.5 points width at the end, and the fourth a hand-drawn line that varies between 1.5 and 3 points in width:

And here are the random width lines used to draw mountains:

Finally, here's the end-to-end comparison:

It's striking to me how this fairly simple refinement of line-drawing can strongly invoke a hand-drawn style, even with such a simple mountain shape.

ADDENDUM

After writing this blog post, I reorganized my approach to this code.  Although the XKCD-inspired code works well for creating plots, it has a couple of issues for my use.

First, the original code assumes straight lines.  In my case, I often use D3js's capabilities to draw smoothly curved lines, and this breaks the original code in some ways that I'll describe in a future blog posting.  One of the fixes is to be able to break any line down into smaller component lines (resampling) rather than just straight lines.  Resampling a curved line is non-trivial, but one approach that works in SVG is to actually draw the curve and then use the browser's built-in capabilities to step along the curve and resample.  This is not particularly efficient, but it is very general.

Second, the original code goes to some pains to scale the jitter independent of the scale of the graph axes.  This has some problems (namely, you really want to scale the jitter by the displayed size of the lines) and in my case is at any rate irrelevant because I already know the scale of my map.  So I have modified the code to simply take a magnitude for the jitter -- it's up to the user to pick an appropriate level of jitter.

The code for resampling, jittering and creating a hand-drawn line can be found in this gist.