Decorating the Ocean (Part One)

Oceans can create large empty spaces in a map, so you often see embellishments added to create some visual interest and/or to break up the empty space.  For example, one of the things you'll often see on fantasy maps is some embellishment where the ocean meets the land.  Here's an example:

Here the map maker added a series of contours around the edge of the coast to suggest the ocean getting shallower inland.  In this series of postings I'll discuss various approaches that Dragons Abound uses to illustrate, decorate and label oceans and coastlines.

---

The default ocean rendering in Dragons Abound is to use a single flat color:

The only mildly interesting thing here is how Dragons Abound selects a color for the ocean.  I want to have a variety of possible ocean colors.  Initially I created an array of RGB color values that worked well as oceans and chose randomly from that array, but eventually I wanted a wider selection of colors.  I also found that the random ocean color often didn't work well with the random land color.

The key insight was to select randomly in the Hue - Saturation - Luminosity (HSL) color space rather than the Red - Green - Blue (RGB) color space.  The colors that work well for oceans are all in a single stretch of the hue space, from slightly green-blue (0.50) to slightly violet-blue (0.60).  And the clash between ocean and land colors is not a hue problem, but occurs when there is a mismatch between the Saturation or the Luminosity of the colors.  So by choosing randomly in the hue space of 0.50 to 0.60 and matching my Saturation and Luminosity appropriately to the land color, I end up with an ocean color that usually looks pretty good.

A flat ocean color is a little boring for a fantasy map, but it works well on something like a geopolitical map:

---

You'll notice that the example map at the top of this posting has a grain texture added to the ocean. This seems like a fairly simple embellishment, but SVG is a vector graphics format, and things like texture that are fairly straightforward in a raster-based format are more challenging in SVG.  You can get some texture effects using SVG's filter system, but it isn't simple to figure out. After some experimentation, I have this:

I'm not entirely happy with how it looks and so it continues to be a work in progress.

It's so difficult to find good information on SVG filters that it might be helpful if I mention a few resources I use.   Two tutorials I've looked at a lot are from Smashing Magazine and from Creative Bloq.  Neither of these has anything to do with maps, but both have a lot of interesting material and give you a good idea of the versatility of SVG filters.

Another good resource is Inkscape.  Inkscape is an open-source vector (SVG) graphical editor.  It includes a large number of filters, so it's often useful to take a look at the filters there and if you find something useful, look at the source of the filter to see how it is constructed.

Finally, there's filtered, an open-source SVG filter editor.  It allows you to compose a filter and see what it looks like on an image.  It's old and seems to be abandoned, but it still works fine for me and can be a quick way to try out different parameters, settings and compositions.

---

Moving on from the grain effect, the next embellishment I looked at was to mottle the ocean.  The idea here is to add some subtle texture to the ocean color.  (You can see some use of this in the example map at the top of this post.) This helps break up a large stretch of unrelieved color on the map and adds some visual interest.

This is fairly straightforward because I don't color the ocean as a single big polygon.  Instead, I color each of the world locations that make up the ocean individually and then apply a slight blur to merge them together.  So mottling is accomplished by coloring the individual locations differently.  Here's an example where I give each ocean polygon a slightly randomized color:

This is more interesting than the flat ocean, but overall not really that good.  Mottling works best when the effect is subtle (so that it doesn't distract from the map content) and not obviously patterned or random.  The above map uses random mottling that only changes the shade of the ocean color. This looks okay but obviously mechanical.

Here's a version using noise:

This isn't as obviously mechanical as the purely random mottling, but has a tendency to look like clouds, which can be distracting.  There's a lot of room for experimentation here, and much probably depends on your particular tastes.

I have also experimented with mottling by changing the hue instead of the shade.  For example, by making parts of the ocean greener or more purple.  That doesn't seem to work as well; or at least is difficult to do well for an arbitrary color.  Since the oceans on my maps can be a variety of shades from green-blue to purple-blue, I have not been able to get this working to my satisfaction, so it's not currently an option.

---

Another interesting embellishment is to indicate deep water by using a darker color and outlining the deep water areas.  This is a sort of "continental shelf" effect that shows where the open ocean starts:

Here you can see at the bottom middle the dotted darker area of the deep sea.  In ancient and medieval times, this would mark the area of dangerous sailing, away from the shallower and calmer shore waters.  I implement this by coloring the deep area a shade darker than the shallow area, but there are a few tricks to doing this well.

The first is figuring out the threshold depth for deep water: Where does "deep" start? One approach is to look at a bunch of maps and figure out a good typical depth value.  This has the advantage that you'll sometimes get a map with a lot of deep water and sometimes a map with no deep water, so you automatically get some variety.  The disadvantage is that you have no control over when deep water shows up, since it's a side-effect of the terrain generation.  An alternate approach is to randomly generate (or select) how much deep water should appear on the map, and then set the threshold depth accordingly.  So if you want about 30% of your ocean to be "deep water", then sort all the ocean depths and pick the one that is 30% from the bottom of the ocean to be the threshold for "deep water".

The second trick is to relax (smooth) the contour between the shallow water and the deep water.  The coast is an example of a depth contour (it separates the positive height land from the negative height land), and you can see that it is very wiggly and fractal.  The same level of detail doesn't look good as a water depth contour:

It's harder to map ocean depths than coastlines, so our eyes expect to see less detail in these sorts of contours.  The fix is to apply fairly heavy smoothing to the contour line before drawing it.

The third trick is to generate the color of the deep water by reducing the luminosity of the base ocean color.  This looks good, and it works well for any color, which lets me use random ocean colors without having to worry about the corresponding deep ocean color.  (As an aside, it turns out to be very useful to have a utility routine for changing the luminosity of a color.  The deep ocean here is the ocean color with less luminosity; the same thing is done for the darker shade around the edge of the forests.  You can do this by converting your standard Red-Green-Blue (RGB) color into a Hue-Saturation-Luminosity (HSL) color, reducing the luminosity, and then converting it back.)

---

An obvious extension of this deep water embellishment is to shade all of the water by depth, making the shallow areas lighter and the deep areas darker, essentially a depth map.  Here's an example of what that looks like:

(I'm showing more of the map here so that you can get a sense of the ocean depths.)

Interestingly, this looks a lot like the noise-based mottling.  If you know it's a depth chart then you can see it makes sense, but at a glance you'd probably just take it to be decorative.

When making the depth-based map I temporarily turned off the normal blurring of the ocean colors, and although the ocean above looks pretty smooth, if I zoom in far enough you can see the individual triangles that make up the ocean:

Finally, here's a map combining grain, mottling and ocean depths:

Next time I'll start talking about decorating the coastline.

Labels Postscript (Part Seven)

This is a bit of a miscellaneous grab-bag of topics left over from the previous labels posts.

---

One problem I still see occasionally on crowded maps is overlapping labels, usually a region label with a city label, as in this example:

The probable cause is treating all overlaps as equal.  A major overlap of a region label with a city label is just as bad as an overlap of a region label with a tiny bit of coastline.  To improve this, I can calculate the area of overlap and weight the penalty accordingly, so that the simulated annealing tries hard to avoid major overlaps and will trade a couple of minor overlaps for a major overlap.

The area of overlap for two axis-aligned bounding boxes is trivial to calculate.  The area of overlap of two general polygons is more complex.  This page has an explanation of one commonly used method; the summary is that you break the polygon into some convenient triangles and sum the areas of the triangles.  If you're doing lots of these calculations, there are more efficient implementations.

After implementing area-of-overlap weighting, the map looks like this:

The algorithm has resolved most of the overlaps.  Some collision is inevitable in the lower left example; the algorithm has found a solution that has only overlaps along the coastline.  Although the closeness of the two labels is not visually appealing, the algorithm doesn't care because there isn't any actual overlap; they're just butted together.

---

Simulated annealing -- the algorithm I'm using to place the labels -- is an iterative algorithm.  The longer it runs, the better chance it has to find a good solution.  (Although since simulated annealing is purposely designed to sometimes go "backwards" to get out of a local minima, there's always a chance that running the algorithm longer finds a worse solution.)  On the other hand, I don't want to sit around forever waiting for label placement.  So it's useful to experiment a little to see how the number of iterations affects the quality of the solution.

Here's the map I'm using for this little experiment, showing the initial placement of all the labels:

All the city labels are dropped right on top of the city symbols, and the region labels are at an initial guess location.  (The river labels aren't showing quite yet.)

Initially I'll try running the algorithm for only 100 iterations, a very short time:

Even this small amount of effort produces "pretty good" results.  Most city labels are fairly close to their anchors without overlapping anything else.  The two obvious problems are that a city label is sticking off the edge of the map, and the "Kusilsik" region label is overlapping a border.

At 1000 iterations:

Most of the city labels are now optimal.  "Kusilsik" has been moved off the border, but now sticks outside the map borders, as does the city name "Mumatkus" above it.   "Nustatnuniak" overlaps a border, but if you examine that area of the map it's apparent that is actually a pretty good placement -- there just isn't room to place that label there without overlapping or going off the map.

At 2000 iterations:

At this point, the algorithm has traded off the various problems in the previous map for only one problem:  the "Smultulup" label goes off the edge of the map.

At 4000 iterations:

At this point the algorithm has found a fairly optimal solution.  All the city labels are well-placed near their anchor points, the region labels are entirely within their regions and without overlap.  A human labeler might choose to put "Smamat Tusul" to the upper right of the city symbol, letting it overlap the coast line in a few places and run out to sea.  The algorithm prefers to avoid most overlap and put the label in the less optimal upper left position.

An interesting thing happens when the algorithm runs for 8000 iterations:

This time the algorithm has settled on the same (sub-optimal) solution it found after 2000 iterations. This illustrates the point I made earlier:  Since the simulated annealing algorithm is designed to "jump out" of local minima, that sometimes leads it to abandon a good solution for a worse solution.

The algorithm outputs the final score of the label placement, so I can plot how the algorithm thinks the label placement improves by iterations:

This makes it pretty clear that most of the improvement happens pretty quickly.  For most purposes, a fairly small number of iterations (~1000) produces an acceptable result with very little time spent.

---

One of the goals of Dragons Abound is to create maps that look hand-crafted. Previously I wrote about making lines that look hand-drawn.  An obvious way to make text look hand-drawn is to use a handwriting font, as I do when I generate "D&D" style maps that are supposed to look like something a Dungeon Master would draw up for his campaign:

However, the handwriting fonts don't work very well on a map that's supposed to look like it is from an old book.  Instead, I use older fonts like IM Fell to create some of that "old book" atmosphere. Another little tweak I can add to help recreate that old book feeling is the occasional typesetting error.  Today's computer generated type never has a setting error, but back in the old days of Linotype and older mechanical type setting, you'd get the occasional error where a letter was too low, too high or even a little rotated.

This turns out to be pretty easy to recreate in SVG, because SVG has the capability to rotate and offset individual letters within text.  So it's just a matter of going through each label with a small chance to tweak each letter within the label.  Here's an example:

I've exaggerated this a bit to make the effect obvious, but you can see how the "n" in "Un Ime" has been rotated.

Offsets are a little trickier:

In this example the "S" in "Nun So" has been offset upwards, but you see that the "o" is also offset. Why's that?  It turns out that when you apply an offset this way in SVG, it becomes the new baseline for subsequent characters.  (Rotation doesn't work this way; it only affects a single character.)  So to get a typesetting error look, I need to un-apply the offset on the next character:

Here you can see the "N" and the "i" in "Nueppiuhhaup" have been offset upwards, and then cancelled on the next character.

It's easy to go overboard with this effect.  It's best to use it very sparingly and with small offsets to create an almost-subliminal feeling of handcraft.  See if you can spot the typesetting errors :-)

Path Labels (Part Six)

Back in Part 4 of this series on path labels, I started constructing polygonal bounding boxes for path labels and using them during simulated annealing to detect if a path label was overlapping a feature or another label:

This has the advantage of greatly improving path label placement, but it also has a major disadvantage:  It takes a lot more computation.

When all the labels are represented as axis-aligned bounding boxes, it is fairly easy to calculate whether they are overlapping.  But now that the path labels are represented by an arbitrary polygon, that problem has gotten a lot more difficult.  The problem of detecting whether two arbitrary polygons overlap is very difficult.  Even if you avoid things like polygons with holes in them, the calculations are still complex.

In the end I settled on using a library based upon the Greiner-Horman algorithm. This library was small, self-contained and fairly speedy.  I used this for all path label comparisons, and for comparing path labels to features.  (For the other types of labels I can still use the fast bounding-box overlap.)

But it still added a lot of computation.  Run time for a map was 140 to 200 seconds. Ouch.

Most of this time is taken up in checking for collisions between a path label (a polygon) and a fixed feature on the map (a bounding box).  It occurred to me eventually that there was probably a faster algorithm for the special case of clipping a polygon to a bounding box.  It turns out there are several, depending upon how complex the polygons are, but a good one for my case is the Sutherland-Hodgman algorithm. The good folks at Mapbox have done a Javascript implementation.

So I decided to switch the label-feature collision checks from the Greiner-Horman algorithm to the Sutherland-Hodgman algorithm.  The way I did this was to implement the new algorithm, and then run both algorithms in parallel.  If the new algorithm is correct, it should always agree with the old algorithm.   Much to my surprise, I found lots of cases where the algorithms disagreed.

One problem turned out to be this bug in the implementation of Greiner-Horman I am using.  The code gets confused if the polygon repeats its start point at the end.  I was doing this for ease of drawing, but I was able to remove the duplicate end point, and that addressed many of the disagreements I was seeing between the two algorithms.

But not all of them.

The other disagreements seem to be caused by this bug in the Sutherland-Hodgman implementation. What I found was that if the polygon is just touching the bounding box at one of the corners, the code identifies that as an overlap and (incorrectly) returns one entire side of the bounding box as the intersection.  Since there's zero overlap area when two polygons touch at only one point, I don't think this should be considered an intersection.  (And Griener-Horman does not consider this an intersection.)  But this may be a limitation of the algorithm; we'll see what the Mapbox folks say about it.  In some ways this is a fortuitous bug: reporting this as an intersection just means that Dragons Abound will avoid placing labels that touch each other, which is good behavior for my purposes anyway!

Switching to the Sutherland-Hodgman for the path label to feature collision checks cut the run-time dramatically.  A typical map went from 149 seconds to 59 seconds.  The collision checks are only about 4% of that run-time after the switch.

In profiling the code to perform this optimization, I also noticed that findLocAt() was using a lot of time (about 6% of the overall program time).  This is a function that finds a location in the world closest to some (x,y) coordinates.  It wasn't used much when I first wrote it, so I implemented a naive algorithm that just walks through every location in the world and keeps track of the one closest to the given point.  Since then it has become more used in the program and started to be a time sink.

Back when I implemented some initial optimizations for label placement, I talked about putting the features into a quadtree for efficiency.  A quadtree is a data structure that organizes its contents by spatial coordinates.  It's intended to make it quick to search for data based upon location.  It made a big difference in efficiency for label placement, and findLocAt() seems like another good place to use a quadtree.

The change is pretty straightforward.  When I initially create the world's locations, I add them all to a quadtree.  I use the D3 implementation of quadtree, so findLocAt() just becomes quadtree.find(). With this substitution, findLocAt() goes from taking up about 6% of the processing time to almost unmeasurable -- 4672 ms to 2.7 ms on my sample map.  So pay attention in your Data Structures course :-).

---

Amusing code snippet:

    // Check *this* out! :-)
    world.loc[index].index = index;

---

After one of the previous postings on Path Labels, /r/Azgarr suggested adding a metric that would try to place the label for a river near the midpoint of the river.  In truth this isn't an issue for most river labels on my maps, but I happened to run across a map with an example of a label being placed at the end of the river:

Here you can see how 'R.Lawtewayiyt' is placed at the end of the river.  (It may look like the lower river label is at the end too, but that's actually about midway on a longer river.)  Since I had a good example handy, I thought I'd try implementing Azgarr's suggestion.

This is fairly straightforward to add; I just calculate the center of the label, measure the distance from there to the midpoint of the river (path) and apply that (with some weighting) as a penalty to the label placement.  Here is an initial result:

You can see this has pulled the river label closer to the center of the river.  I have to be careful with the weighting here, because I'd rather be on a straight part of the river that's further from the center than on a sinuous part of the river right near the center.  The stronger I make the weighting, the more the label is pulled toward the center:

With this weighting, the label is near the midpoint of the river.  In this case the river is pretty straight, but you can see that the end of the label has become slightly distorted to follow the river.

This same map had another problem:

In the center bottom of the map, the river label is on top of a lake.  The reason for this poor placement is clearer once I turn on label boxes:

The green boxes here are areas to avoid.  The edges of the lake are boxed but the lake itself is not. This makes some sense; it would be okay to have the label for a city on a lake entirely in the lake itself.  On the other hand, I might someday add names to the lakes and I'll presumably want those inside the lake.  So it would be better to make the whole lake something to avoid.  I can do that by using the bounding box of the lake as the feature to avoid:

Now the green box encompasses the entire lake and with this constraint in place the algorithm can't find a good spot for the river label and drops it entirely.  Interestingly, the city label 'Toynewnmoyt' was previously in an awkward spot far from its anchor, and now it has moved down to overlap the lake much closer to its anchor.

Path Labels (Part Five)

I ended the last posting with this map:

Although the labels look generally good here, "Chukor" and "R.Tertitdul" fall on mountains and are hard to read as a result.

The obvious way to address this problem is to add mountains to the list of features that the labeling algorithm is trying to avoid.  Labels will then gravitate to spots where they don't overlap mountains. But mountains are big features, and on many maps, that would make label placement very difficult. On this map, for example, it's not obvious that there's anywhere you can put the "R.Tertitdul" label without overlapping the mountains, the coast, or a city.  It's inevitable that labels are going to at least occasionally overlap map features, so I need a way to make labels more readable when they do.

The usual approach is to mask out the features in the area of the label.  Jonathon Roberts talks about this technique a bit over at Fantastic Maps, and that's worth reading.  For those of you who aren't familiar with the idea of masking, the basic concept is to create an area where something (the mountains in this case) won't be shown, i.e., it will be "masked out" of the image.  In many cases, it's easier to draw everything and then block out portions we want to remove than to not draw them in the first place.  For example, at the time I'm creating and drawing the mountains, I don't know if or where text will overlap the mountains.  So it's much more convenient to just draw the mountains and later "erase" the parts I don't want.  The mask is also separate from the image, so we can change the mask without changing the image.  For example, during label placement I can just slide the mask around with the text.

In SVG, you can add a mask to just about anything.  The mask itself is a grayscale image.  Everywhere the mask is white the image shows through; everywhere the mask is black the image is blocked out; and gray scales correspond to partial opacity.  For text, you can create a useful mask by drawing the same text in black with a fatter pen -- that masks out around the edges of the text to whatever distance you've chosen.  Then you place the mask not on the text, but on the image you want to block out.  So in my case, I need to place the mask on the image of the mountains.  Here's what the "R.Tertitdul" label looks like with and without this masking:

You can see that this makes a big difference in the readability of the label.  Jonathon Roberts recommends blurring the mask into the background, and letting some of the background show through. That looks like this (compared to the "normal" mask):

This is a more subtle effect while still making the label more readable.  Jonathon Roberts actually does a white overlay on the background rather than a mask.  This has the advantage of also popping out a label even on a plain background (where the mask has no effect).  Here is a similar effect, compared to just the subtle masking:

I didn't expect to like this effect -- and I may continue to tweak it -- but I find that it does improve the definition and readability of the labels.  One problem is that the effect is much more pronounced on a dark background like a forest:

Unfortunately, SVG doesn't provide a full array of compositing functionality.  If I could use a screen blend mode, as Jonathon Roberts recommends, it would look better over a dark background.