Simplifying the Landscape

At the end of the last post I wrote about the actual implementation of my Clockwork Aphid project, I said the next step was going to be display simplification. At that point I’d generated a few landscapes which were just starting barely starting to test the limits of my computer, though they were nothing like the size or complexity I had in mind. That said, it was looking at landscapes containing 1579008 polygons and it was obvious that not all of these needed to be put on screen. Moreover, because my landscapes are essentially made up of discrete samples (or nodes): I needed to reduce the number of samples which were displayed to the user, otherwise my performance was really going to tank as the landscapes increased in size.

Shamus Young talked about terrain simplification some time ago during his original terrain project. This seemed as good a place as any to start, so I grabbed a copy of the paper he used to build his algorithm. I didn’t find it as complicated as it appears he did, but this is probably because I’m more used to reading papers like this (I must have read hundreds during my PhD, and even wrote a couple), so I’m reasonably fluent in academicese. It was, as I suspected, a good starting point, though I wouldn’t be able to use the algorithm wholesale as it’s not directly compatible with the representation I’m using. Happily, my representation does make it very simple to use the core idea, though.

If you remember, my representation stores the individual points in a sparse array, indexed using fractional coordinates. This makes it very flexible, and allows me to use an irregular level of detail (more on that later). Unlike the representation used in the paper, this means a can’t make optimisations based on the assumption that my data is stored in a regular grid. Thankfully, the first stage of the simplification algorithm doesn’t care about this and examines points individually. Also thankfully, the simplification algorithm uses the same parent/child based tessellation strategy that I do.

The first step is decide which points are “active”. This is essentially based on two variables:

  • The amount of “object space error” a point has (i.e. how much it differs from its parents);
  • The distance between the point and the “camera”.

A local constant is also present for each point:

  • The point’s bounding radius, or the distance to its furthest child (if it has children);

I’m not sure if I actually need this last in my current implementation (my gut says no, I’ll explain why later), but I’m leaving it in for the time being. Finally, two global constants are used for tuning, and we end up with this:

SimplificationEquation2

Where:

  • i = the point in question
  • λ = a constant
  • εi = the object space error of i
  • di = the distance between i and the camera
  • ri = the bounding radius of i
  • τ = another constant

This is not entirely optimal for processing, but a little bit of maths wizardry transforms this like so:

SimplificationEquation3

This looks more complicated, and it’s less intuitive to see what it actually does, but from the point of view of the computer it’s a lot simpler, as it avoids the square root needed to calculate the distance between the point and the camera. Now we get to the fun part: diagrams! Consider the following small landscape, coloured as to the granularity of each of the points (aka the distance to the node’s parents, see this post):

AllPoints

Next, we’ll pick some arbitrary values for the constants mentioned above (ones which work well for explanatory purposes), and place the viewpoint in the top left hand corner, and we end up with this the following active points (inactive points are hidden):

ActivePoints

Now, we take the active points with the smallest granularity, and we have them draw their polygons, exactly as before, which looks like this:

SmallestPolygons

When we come to draw the polygons of the next highest granularity you’ll see that we have a problem, though. The previous set of polygons have encroached on their territory. To avoid this, each node informs its parents that it is active and then the parent doesn’t draw any polygons in the direction of its active children. If we add in the polygons drawn by the each of the other levels of granularity, we now end up with this:

FilledPolygons

Oh no! There’s a hole in my landscape! I was actually expecting that my simplistic approach would lead to more or less this result, but it was still a little annoying when it happened. If I was a proper analytical type I would next have sat down and worked over the geometry at play here, then attempted to find a formulation which would prevent this from happening. Instead, though, I stared at it for a good long while, displaying it in various different ways, and waited for something to jump out at me.

Eventually it did, and thankfully it was a very simple rule. Each parent stores a list of the directions in which it has active children in order to prevent overdrawing (as mentioned above). The new rule is that a node is also considered active if this list is non-empty. With this addition, our tessellated landscape now look alike this:

BackfIlledPolygons

Presto! A nice simple rule which fills in all of the gaps in the landscape without any over or under simplification, or any overdrawing. I suspect this rule also negates the need for the bounding radius mentioned above, though I have not as yet tested that thought. To recap, we have three simple rules:

  1. A node is active if the object space error/distance equation says it is;
  2. A node is active if any of its children are active;
  3. Polygons are tessellated for each active point, but not in the direction of any active children.

But what does this look like in actual eye poppingly 3D landscapes? Well, here’s an example, using the height based colouring I’ve used before:

SimplifiedLandscape

I quite pleased with this, though what I’m doing here is still quite inefficient and in need of some serious tuning. There are a couple of further simplification tricks I can try (including the next step from the (paper) paper). More to come later. Honest.

Advertisements

Features

So, in my last post I remarked that for procedurally generated landscapes to be interesting, they would need features. But what sort of features was I talking about? Population centres, in particular, tend to to be found close to certain kinds of… things. The first of these which always comes to my mind is the “defensible position.” Something like, say, this:

Edinburgh Castle

A lot of the truly great cities in Europe tend to centre around castles, but you don’t tend to find castles just plonked anywhere on the landscape. Edinburgh Castle is a good example because:

  1. I think it looks awesome. Look at the way it seems to just grow out of the rock of those cliffs!
  2. It’s pretty much unassailable from every direction but one (I think I mentioned the cliffs);
  3. It’s on a raised vantage point with a decent line of sight to just about every direction of approach.

It’s not the most castle-ey looking castle and it lacks, for instance:

  1. A moat;
  2. The sort of tower Rapunzel might hang out in.

But I think it makes a reasonable example here. I think this is a good rule of thumb: a castle should look good and be well situated (defensibly speaking).

Another feature which population centres tend to spring up around are harbors. They’re very important for trade, thus they attract people. Wikipedia served up a reasonable example:

Capri harbour, Italy

Rule of thumb number one for a harbor: it should be at the intersection of the land and the sea, ideally. If we’re playing in a fantasy sand pit this isn’t actually the only option, but that’s a story for another day. The nature of the coast is important as well, though. You need reasonably deep water right next to the land, but not too deep. Lastly, and just as importantly: it should provide shelter. The boats in the harbor need to be able to survive the harsh weather the sea sometimes serves up. A sheltered cove with high cliffs to each side sounds about right, no?

The last kind of feature I’m thinking of here is again something quite important to trade: the bridging point. You need to get your trade caravan across the river (or gorge) which separates the harbor and the castle (for example), thus you need to cross the bridge. The bride spans the river at a conveniently narrow point and it’s the only one for miles. Thus, the bridge becomes a nexus of activity and a town springs up there. Over time the town increases in size and more bridges get built. Before you know it… BOOM, Florence!

 

Ponte Veccio

This is, of course, just the tip of the ice berg. We’ve not even talked about churches, cathedrals, monasteries, oases, and any number of geological features.

Another question, of course is how to go about actual generating the population centres themselves. Well, I’m going to talk more about this later, when I actually get around to talking some other people doing some procedural content related stuff, but here’s a little something to wet your appetite:

Cool, no? More about procedural city generation from me later (I don’t want to get too far ahead of myself), but you can read more about this project at this excellent series of blogs. Start at the beginning, and be ready to loose a good hour of your time.