Monday, May 20, 2019

Map Borders (Part 11)

I have two major items left on my initial map borders list: Celtic knots and corner boxes.  In this post I start working on Celtic knots.  Although they look simple, it was not intuitive to me how to construct and draw them, so this installment proceeds fairly slowly to describe Celtic knots and illustrate how they “work." 

For those of you who are unfamiliar with Celtic knots (or unfamiliar with the term), Celtic knots are a kind of illustrated braidwork that has been used as a decoration for many years, including on medieval manuscripts.  Here's a simple example:
The interlacing of the various strands is the defining characteristic of Celtic knots.  Among their uses, they've long been popular as an element in map borders.  Here's an example from one of my inspirational maps:
Here's another one, with a more complicated pattern:
The key feature of Celtic knotwork is that each cord crosses other cords in an alternating pattern: first over, then under, then over, and so on.  If you trace any cord in the example above you'll see that's true.

What was not so obvious to me initially is that a row of crossings always have the same “handedness".  That is, every crossing in the top row of this braid has the same cord on top:
And then the next row of crossings has the other handedness, to maintain the over/under pattern:
So you can immediately tell how two cords should cross by the row they appear in.  (Or to put it another way, you can draw all the crossing in a row the same way.)

Another feature of knots is that the crossings alternate columns:
The crossings in all the red columns have the same handedness and the crossings in all the blue columns have the other handness.  (Another way to put this is that the rows are offset from each other.)

Now take another look at the example knot:
Notice anything about it?  It was drawn incorrectly!
In the bottom row, the cords go over-over (and under-under) instead of over-under as they should.

(Ironically, the first Celtic knot from my inspirational maps is not a true Celtic knot either; it has three rows and Celtic knots always have an even number of rows.)

With some insight into the crossings, let's look at the edges.  When a knot is artistically drawn it may not be immediately apparent, but at the edges of the design the cords “bounce off" of invisible walls at 90 degree angles:
Here you can see how the blue cord hits the top edge of the pattern and “bounces off."  In the corners, the cord bounces twice.  Knotwork is usually drawn with the cords following the walls (as in this example) or with rounded turns (as in the broken knotwork example above) which somewhat obscures the way the cord bounces off the edges.

That's about all you need to know to understand a simple braid.  What about a more complex pattern?
More complex patterns are created by adding additional walls where the pattern is interrupted and reflects off the new walls just as it does with the edges.  In this case, I've added three walls:
In the bottom corners, the pattern now bounces off three walls in row.

The last thing you might want to note is that spaces between the crossings form a regular grid, and the walls always connect two dots on this grid:
The crossings (or reflections of walls) all happen halfway between the red dots.  Here's a picture of the above pattern showing just the walls and the grid:
The big black dots here correspond to the red dots above, and the gray dots are the in-between dots where the cords cross or reflect off of walls.  This diagram also suggests a representation / implementation for Celtic knots:  an array where the black dot positions are ignored, and the gray dot positions are either “open," “vertical wall," or “horizontal wall."  Patterns can be created by placing a few walls into the array and leaving most positions “open."

The illustration above comes from a very useful online Celtic knot tool that you can find here.  That will let you play around with placing walls and designing patterns.  Try it out, it's quite entertaining!  For more interesting information on Celtic knotwork, see the tutorial here.  The tutorial has a clear explanation of how knotwork is designed and drawn.  The tutorial here provides an alternate explanation in terms of graph theory.

Now that I have an understanding of Celtic knotwork and an idea of how to represent a knot, let me  consider how to draw a knot from the representation.

My initial thought was to draw the knot as a series of paths, each one tracing completely through one of the loops of the knot.  I could start at one of the gray dots and trace through until I returned to the same dot, creating the path to draw.  However, I realized pretty quickly that this wouldn't work.  The problem occurs in the crossings.  In each crossing, I need one path to be atop the other path.  I thought I could do this by masking out the lower path.  (A mask blocks an area of the image from showing, so by blocking whichever path was supposed to be on the bottom, the other path would appear like it was on top.)  But many times a path crosses itself.  In that case, masking out the bottom path would also mask out the top path!

So I will have to draw the paths piecemeal.  I can certainly draw a whole path from one crossing to the next crossing, but since I'm drawing piecemeal anyway, it seems worthwhile to think about the smallest pieces I can draw.

As it turns out, you can draw any Celtic knot using just four pieces:  a left-handed crossing, a right-handed crossing, a two-sided vertical wall reflection and a two sided horizontal wall reflection:

(If you allow rotations, this is only two pieces, but for illustration purposes I am using four.)  There are two tricks to keep in mind.  First, at the edges of the knot you use only half of the reflection patterns.  Second, where two reflections meet (as in a corner) it is usually drawn more smoothly than just sticking two reflections together.

Here's a simple example of a knot:
And here's the same knot with the different pieces identified:

Note that there are holes between each of the pieces, corresponding to the big black dots in the diagram above.  Nothing needs to be drawn in these areas.  This is clearer if the path is drawn as a thin line:
You can see that in the red and blue tiles, you draw two lines crossing the tile; in the yellow and green tiles you draw two lines along the edges of the tiles.  If you make the lines connect properly at the edges of the tiles, you get a Celtic knot.

To review:  Celtic knots are composed of cords that follow an over/under pattern of crossing and reflect off the edges of the pattern and off of internal walls.  A knot can be represented as an array of points.  Points represent crossings or vertical or horizontal walls.  All crossings in the same row of array cross the same way, and alternating rows have alternating crossings.  To draw a knot from an array, you draw in each point the appropriate crossing or wall, and connect each point to it's neighboring points.

Next time I'll get started on implementing a representation and displaying it.

Monday, May 13, 2019

Map Borders (Part 10)

Addressing more map border problems and adding some new features.

One problem I created when I added elaborate map borders is that they now clash with the map caption (if there is one):
This happens because the caption is placed a fixed distance below the bottom edge of the map.  That was fine before, but now it needs to be placed below the bottom edge of the map border.  The only tricky thing about this is that because the border isn't (necessarily) drawn inside to outside, I actually have to test after every element of the border whether that element is the outside edge.  But once that's in place I just have to place the border outside of that edge:
You can see that the caption is now getting close to the edge of the “paper."  I just have a set amount of space around the map right now, and if I happen to generate a wide border it eats into that space.  The fix is probably to resize the “paper" after the map and border is complete; that's on the TODO list.

Sometimes Dragons Abound generates a “caption box" to frame the caption.  This is intended to look something like the name plate on a painting.  Those are usually centered in the bottom of the frame.  For a similar look, I will center the caption box in the map border.
It looks a little odd when the border line color doesn't match the color of the caption box.  However, there are only a few borders that have non-black lines, so for the moment I'm just going to let this go.

Another element I'd like for pattern borders is a stylized flower shape.  This is just a few petal shapes with a circle in the center.  For each petal, I draw two lines out from the center and then connect them with a quadratic curve:
This looks pretty good unless they get too small:
This is still okay, but just barely.

The number of petals can also be 6 or 7:
Beyond 7 petals the shape becomes illegible.  Right now flowers just draw from the standard border colors, but maybe there should be some flower-specific colors.

Stars and flowers are a nice combination:

Over on Reddit, Watawatabou suggested leaving the dark sides of moons visible like the do on tarot cards.   If you look at the examples on that link, you'll see there's actually a few ways that they do that.  One way is by essentially outlining the whole moon, both the light side and the dark side.

I looked at adding that to my routine for generating a moon shape, but that was decidely non-trivial, since the resulting figure – a circle with an embedded crescent – is not a simple polygon.  Then I realized there was an easier way to do this.  Since the Map Border Description Language (MBDL) can handle drawing a circle, and drawing two things on top of each other, I could just draw the circle for the moon outline and then draw the moon over it.
That's pretty nice and is certainly a good option.

Another possibility is to draw the rest of the moon in a different color.  This could be a slightly lighter or slightly darker color than the background.  Since I'm using a midnight blue border color here, I can try a darker version of the same color.  I use the same trick as above, drawing an entire dark blue moon behind the crescent.
It's somewhat visible but doesn't really stand out.  The very dark blue also registers as black and seems to break the color scheme.  It might be better to use a lighter color instead.
This is more visible, at least, but I'm not sure I really like the effect.  Maybe.

The most interesting approach is to extend the horns of the moon, as in this fanciful example:
Image result for moon tarot
I like this quite a bit, but drawing this is problematic for Dragons Abound.  The outside of the moon shape remains a portion of a circle – that's okay – but the inside of the shape is not an easy curve to describe.  It's certainly not an elliptical curve between the two points of the horn!  Maybe it's a smaller circle offset within the larger circle?  Maybe it could be approximated by two Bezier curves, but I'm not sure.  Beyond that problem, I don't have a good idea of how to move this through the phases from full moon to sliver and back again.  So I'm not going to tackle this (now) but maybe someone will suggest a good way to draw this curve and progress it through the phases.

One problem with my borders has been that if I have a square offset corner and a pattern, the pattern might not fit nicely in the legs of the offset.  It might get stretched or cut off:
One way to address that problem just occurred to me (somewhat belatedly).  For other layout reasons, before I display a border I go through and measure the length of any patterns in the border to find the maximum length pattern.  Since I know that when I set the square offset, I can use the maximum pattern length as a minimum size for the offset.  This guarantees that the pattern will fit at least once into the corner:
I can imagine complex borders with multiple patterns where this might fail, but it works pretty well for most cases.  The user can still force a particular corner size if that's desirable.

Speaking of corner offsets, another feature I want to implement is a diagonal corner.  I have exactly one example of a diagonal corner in my set of inspirational maps:
It's not impressive, but at least it gives you an idea of what I mean.  The truth is I don't have much interest in diagonal corners, but I tried to implement round corners and ran into such problems that I gave up.  Diagonal corners is a (hopefully) easier place to start.

My approach to a diagonal corner is to stop the horizontal and vertical sides of the border short and join them with a diagonal line.  To start with, I'll get the vertical and horizontal lines to stop the correct distance away from the corner:
Now I need to draw a diagonal line connecting side to top.
That's close-ish.  The problem is that the top line stops short.  This happens because when making a mitered end to a line, the line drawing routine keeps the end of the line at the furthest point of the miter.  This is nice because the line doesn't extend past where it should end, and further it correctly meets a miter from the other direction when they both have the same endpoint.  However, in this case that leaves the miter about a half a line width short of where I want it to be; the fix is to extend the top line a half a linewidth to the left.
Here I've only fixed one side, but it looks about right.

However, this has a glaring problem – the diagonal lines are wider than the horizontal and vertical lines.  This makes some sense when you think about it.  These lines are meeting the mitered ends of the horizontal and vertical lines.  The mitered ends are at a 45 degree angle, so each mitered end is about 1.4 times the width of the line.  (Since the cosine & sine of a 45 degree angle is the square root of 2.)

Fixing this is complicated.  What I need to do is overlap the diagonal line and the horizontal line this way:
Now both lines are the same width and meet at a 45 degree angle.  I know the coordinates of the center of the horizontal line:
And I need to calculate the center of the end of the diagonal line:
And in order to layer lines from inside to outside properly, I need to know the point where the insides of the two lines intersect:
My teeth are hurting just thinking about this!

I did what I always do when I'm faced with a math problem I can't easily solve – I sent it to my kids.  They're much better at math than I am.  (This is an under-appreciated advantage of being an older developer.)  Sure enough, one of them solved for the red point based upon the blue point and the upper vertex.  And it turns out that the pink point is basically offset by the tangent of 22.5 degrees times the width of the line.  (I did that myself so it's probably wrong, but it seems close enough.)  So with those calculations in place:
And now all the lines are the same width and everything matches up nicely!  At least in this corner, I still have to do the other three, but that's mostly a matter of bookkeeping and flipping the sign on the offset calculations appropriately.

The second step of diagonal corners is to make patterns go around the corner.  Initially I wrote two routines that could handle drawing patterns vertically and horizontally.  And those routines were also sufficient (with some tweaking) to handle offset corners, because those are just more vertical and horizontal pieces.  But as I started thinking about implementing diagonal corners I realized that it was better to think about drawing a pattern as laying out elements along a path.  With an algorithm that could “follow a path," I could just trace where I wanted the pattern – around the map, through an offset corner, or any other path.  (For example, I could also use this to draw patterns for map compasses.)  So I decided to refactor my patterns code to follow a path.

The basic code for this idea came together pretty quickly and without a lot of debugging.  This is often the case when you're refactoring code.  It's the second time through, so you understand the problem and you have working code to reuse – both things that improve productivity.  Unfortunately, when I try to draw around the entire map in one path, problems become evident in the corners:
The problem is that the algorithm treats corners as just like any other part of the path, and that can result in elements overlapping, because the algorithm doesn't realize that the path has turned a corner.  In my initial implementation, I drew one segment of the border at a time and carefully added length to one end of each pattern so that the corners would get filled in correctly.  But here the path-following routine doesn't know that extra distance is needed between the pattern elements to avoid an overlap.

There's probably an approach to handle this automatically based upon calculating the distance between the centers of adjacent elements, but there's an easier compromise – I can continue to use the path following routine, but I'll use it to draw each segment of the border (instead of my specialized vertical & horizontal routines).  If this turns out to be particularly painful I can revisit the corners problem.

So with path-following in place, I can handle diagonal corners pretty easily.  There's a little bit of tweaking needed because making lines stack correctly in corners (the pink dot of the math problem above) changes the position of the lines a bit and the pattern needs to account for that.  But once that's all in place:
If the diagonal is too short for a pattern, the program tries to fit it in as best as possible, but the results can look awkward:
I can avoid this by forcing the diagonal corner to be long enough to hold a complete repeat of the pattern.  This works well unless the pattern is too long.  In that case, the diagonal corner becomes quite long clips off a big chunk of the map.

The last thing I need for diagonal corners is a way to clip the map to a diagonal border.  This doesn't happen automatically when I specify a diagonal border because there are times when you want the border (or a piece of it) to be “on top" of the map (as is the case in the first diagonal example map above).  So I have to implement a separate diagonal clipping option.  This turns out to be the same as the square corner clipping area, with one point removed in each corner.
I wouldn't say that was easy, but now that I've worked my way through the challenges of diagonal corners, let me take another shot at implementing round corners.  I have a few example maps with round corners, like The Dominion by Zach Bodenner:
(And before I go on, take a moment to appreciate the clever way Zach flipped the border decoration over to run it through the corner.)

To make a round corner, I want to do essentially the same thing I did with the diagonal corner, except stacking arcs instead of diagonals:
So how do I draw those arcs?  Suppose those arcs are circular.  If think about it a moment you'll realize that in order to stack seamlessly, they need be parts of circles with the same center point:
I can pick the center point arbitrarily, but I want to pick one that is far enough away from the corner so that I get a fairly shallow curve in the corner, and so there's no danger the circles shrink to nothing!  Likewise, I can pick the point where I stop the inside line (the blue line above) to be anything I want.  Then I can measure the distance from the end of the line to the center point I've picked, and that's the radius of the blue circle, and I draw the portion of the blue circle between the two blue lines.  The next line (the green line) I stop a line width closer to the corner and repeat.

Or that's the theory, anyway.  Let's see how it works out.  I'll start by stopping the top and side some distance back from the corner.  Each succeeding line stops a linewidth closer to the corner.
Next I need to draw an arc of a circle from the end of the top line to the end of the left line:
This doesn't quite work.  It's the same problem I had with diagonal lines which required me to use the family math experts.  To get the arc to properly overlap the two side lines, I need to draw to a point that is back inside the side lines.  In this case the calculation is simpler, because I know the radius of the circle:
The spacing is not correct yet, and there's a small problem with one end of the green line (which turned out to be a typo in the code), but it's not bad.  Adding in the correct line stacking:
This is pretty good, at least for reasonable center points.  

Moving on to drawing patterns around the curved corners, it's not much different than the diagonal corners.  I have code to draw a pattern along a path, so I just have to calculate the circle just as I do for lines, but use that as a path rather than drawing it directly:
There's a little bit of kludging here because I don't want to calculate the actual angle at which the circle meets the edges (it varies depending upon how far the border is from the center of the circle) so I use a median value that works well for all reasonable borders.

The last thing to be done for rounded corners is to add the appropriate clipping area to the map.  After a little work to tweak the placement and spacing, this is the result:
And I think that's enough map borders for today!  Next up I finally tackle Celtic knotwork...