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!