Matching Edge Altitudes of Different Fractal Squares

We have various situations in which we will be generating terrain fractals at a fine level of detail that must border on other fine-level fractals which were generated later, possibly without any common parent. For instance, if two terrain squares are adjacent across a border between coarse-level map squares, there won't be a common parent: they will be members of entirely different fractals, possibly with different parameters. However, when we generate finely detailed terrain data around the edge, the altitude profile along the edge on the left-hand side must exactly match the altitude profile on the right-hand side. Otherwise there will be an unreasonable wall at the border.

In addition, the altitudes along the edge must come out the same regardless of which side the player approaches from, i.e. which side's fractal is expanded first.

This page discusses ways of achieving this goal. There are several possible meshes on which the fractal can be expanded, but I am only going to discuss the case of a square mesh here. If I end up using a triangular mesh of some sort, I will come back and update this page to reflect that.

I represent the expanded terrain in a quadtree. Before continuing, I need to talk briefly about the way the terrain fractal works. A terrain fractal is initialized on a single coarse-mesh square with four vertex heights. (Here, "height" technically means "radius from the center of the planet.") Consider a square already expanded to some level of detail n (with neighbors also expanded to level n) which we want to further expand to level n-1.

First, we need to expand the four neighboring squares to at least level n, if they aren't already expanded.

Now, we partition the square-to-expand into four quadrants. This means allocating four new nodes on our quadtree. To finish out these squares, we need to know the heights at all of their vertices.

The edge-midpoint heights are the heights interpolated between the two ends of the edge plus the variance at the edge midpoint.

The central height is the central variance plus the height interpolated from two opposing corners. I would recommend alternating the choice of corners in a checkerboard pattern at each level (i.e. taking A and C in one square, B and D in its nearest neighbors, and so on.)

Pseudo-partition each of the four level-n neighbors into level n-1 quadrants, but don't compute any new variances. The heights of the additional points here are purely interpolated values. These quadtree nodes need to be marked as "not really expanded," and expanded later if the algorithm calls for it. The purpose of this step is to make the boundaries of the original expanded square smooth.

Above, I didn't go into the details of computing the height variances. This system puts a very restrictive requirement on the height variance algorithm: it must produce the same height variance for the midpoint of a shared edge from either of the sharing squares. The fractal height variance is something along the lines of

        dz = randomFloat( -1, 1 ) * scale( n )

                                a n
                 scale( n ) = 2    

                  
       a correlates to the roughness, and is usually greater than 1
The key to making the edge-midpoint variance independent of which square is computing it is to make the randomFloat() function use a pseudo-random number seeded from the map position of the edge midpoint. Three integers specify the position of a midpoint: the lowest-level longitude coordinate, the lowest-level latitude coordinate, and the coarse-level square in which it lives. My only requirement for the method of turning these into a random number seed is that it not produce identical patches of terrain at different spots on the globe. Something like
   seed = longitude + LARGE_PRIME * latitude + LARGE_PRIME_2 * coarse-square-id
should accomplish this. When I refer to "lowest-level" coordinates, I mean the number of level-0 grid squares from the southwest corner of the coarsest-level square. So, at level 4, the vertices of a square would be spaced by 2^4 = 16 lowest-level squares.

To know the altitude of the shared edge midpoint, we need more than the variance: we also need the corner altitudes. That means that the adjacent squares of a square that we are expanding from level n to level n-1 must all first be expanded to at least level n. This can be done easily enough.

Finding My Neighbors

These algorithms have many operations of the form, "for this square, do such-and-so to its edge-sharing neighbors." We need to be able to quickly identify the edge-sharing neighbor. I think that the memory requirements are pretty relaxed here: the number of polygons we can render at a reasonable speed is much less than the number we can store. So, we don't need to worry about an efficient storage format. For this reason, I'll keep pointers to each square's four neighbors in the square's quadtree node. The pointers will point to squares at the same level, or else one level coarser. (No square is ever bordered by another square more than one level coarser, according to the fractal expansion rules given above.)

It may turn out that the overhead of updating the pointers is more than the overhead of not having them and having to traverse the tree to find a square's nearest neighbors. I'll try it both ways.

How To Tell When To Stop Expanding

FFE (and other 3d game engines such as Mech Warrior) have had terrible problems with "popping", which means the sudden appearance of new terrain features at the edge of some level of expansion. The way to avoid this seems to be expansion rules that explicitly expand anything creating more than a certain number of screen pixels of change. The maximum number of pixels of movement is computed from the variance as follows:

                a n          screen height
   dz        = 2     *   ---------------------  *  scale constant
     max                 distance from viewer

This may be wrong, but it's something along these lines

Here, a is the roughness parameter and n is the level of the expansion for that square, 0 being the finest level. The constant is the ratio of the finest-level-of-detail grid spacing to the length (or height, or some such) of the view frustum.

In addition to movement, expansions (especially from far off) can significantly change the angle between the surface and the light source. This means that chunks of surface will drastically change shade as the viewer approaches, which is also bad. We can take care of this by imposing a separate limit on the maximum tilt allowed without further expansion. Note that the maximum tilt caused by each further expansion decreases much more slowly with increasing scale than does the maximum movement of vertices: in fact, if a = 1, it doesn't decrease at all as we go to finer and finer levels of detail.

Data Structures for Expanded and Unexpanded Quadtree Nodes

It is likely that we will want to expand swathes of map at once. For instance, if the player is driving in a straight line, the zone of expansion surrounding him will encompass a line of new squares and leave behind a line of old squares all at the same time. The expansion algorithm can clearly be done more efficiently on N nearby squares than on N single squares. For one thing, the generation of "fake" expanded squares (described above) can be bypassed if those squares are going to be expanded next anyway.

Unexpanded squares can be in one of three states: squares that we absolutely don't want to expand any further, squares that should be checked for possibly needing further expansion (according to the max-pixels-moved criterion above,) and squares that should be expanded. Promoting a square from "don't-expand" to "maybe-expand" should probably be handled in some very straightforward way, for instance by labelling all squares within a sphere centered on the player below a certain level as "maybe-expand." There would be one such sphere at each level of detail. Each time the view moves, the "maybes" should all be checked, then the "shoulds" should be expanded.

What race are the child squares when a "should" is expanded? We can check them as if they are "maybes" when they are generated, and based on the results either stick them on the end of the "should" list or the "maybe" list.

There should be equivalent "maybe-compress" and "should-compress" lists for the squares that the player is leaving behind. Only leaves of the quadtree can be on the "maybe-expand" and "should-expand" lists, and only interior nodes can be on the "maybe-compress" and "should-compress" lists.

Example of Expansion and Pseudo-expansion

Below, I show an example of two squares (marked with "X") being expanded, along with the required additional expansions and pseudo-expansions. Here is the initial state of the quadtree before the new expansions:

After the two primary expansions, the two additional expansions required as prerequisites of the primary expansions, and the pseudo-expansions needed to maintain smooth mesh boundaries, the quadtree looks like this:

Home | Terrain Generation