Finally, a new part! I had the basics of this working over a week ago. It's been torturing me with strange bugs since then.
I'm working on a small "infinite landscape" demo. I want to keep walking forever and generating procedural landscape as I go. For now, it's just bare terrain without grass, trees or buildings.
For this version, I'm using a height map. Eventually, I will need something that works in three dimensions, so I can do my asteroids. I also don't want anything that relies on a lot of shader magic, since I want this to run on slow devices. I looked around for some algorithms, but didn't see anything I liked. So I wrote my own. This is so simple that I'm sure other people have done exactly the same thing. I just haven't run into a description that matches this.
I don't care about the look of the terrain yet, so I just take the usual simplex noise and mess with it a bit to get mountains. Then I add some color to make it look slightly more natural. This can be improved later.
As the user moves over the landscape, I need to keep adding new areas and deleting old areas that are no longer visible. I do with this a simple 3 by 3 grid. Each grid cell is the size of the view distance -- standing at the edge of a cell, the user can see at least one cell width in all directions. When the user walks into the rightmost column, it's time to add more cells on the right, and delete the ones on the left. The same with movement in other directions.
Next, subdivide the cells in a quad-tree. The size of a cell is determined by how close it is to the eye. Each cell contains the exactly same number of points regardless of size. (I'm using 64 by 64 points per cell). Because the cell sizes increase in powers of two, we can make the view distance large pretty easily.
Figure 3 shows seven levels of division. Since I've been using 1 meter for the basic unit, and cells are 64 points on a side, this is a view distance of 8 kilometers (64 * 27 = 8,192 units). In the demo, I'm using 10 levels of division, for a 64 kilometer view distance. This takes around 120 cells total, or 500,000 points, which is very manageable.
As the user moves, subdivide the cells he's moving closer to, and recombine the four children of cells he's moved away from. When a cell is subdivided, we create a more detailed version using the procedural algorithm that generated the terrain in the first place, just with finer stepping between points. When four child cells are recombined, we take every other data point in the existing data to recreate the parent.
There are two functions in the code, tooCoarse and tooFine. These are evaluated on the entire tree of cells after each movement by the user. If a cell is tooCoarse, the cell is subdivided. If all four children of a cell are tooFine, the children are recombined.
My initial version tried to keep a fixed apparent size of features at all distances. This causes the landscape to break and recombine too often. So now I allow a range of resolutions. I'm calculating the step size of a cell divided by the distance from the eye to the nearest point in the cell. This is the apparent size of features in that cell. The cell containing the eye (and it's parents) get subdivided down to maximum resolution, so there's some bias towards fine detail near the user. Figure 5 shows the result.
This simple algorithm gets me most of what I want. The landscape is infinite and I have a far horizon. The distant scenery is crude, but that's basic to this algorithm. Even with this code, I think distant scenery would look better if my landscape function didn't produce such spikey mountains.
What I have now works just fine when you move at walking speed (the default.) As you kick the speed up, you get close to cells before they have time to rebuild, and the pop from one resolution to another is very noticeable. It's also fairly obvious when distant scenery gets rebuilt, since much finer features are suddenly visible. I'm hoping you just won't notice this with a bit of fog.
Unfortunately, there's more work to do.
The various landscape cells have different resolutions and so they don't match up cleanly. That leaves gaps in the landscape (see Figure 6). To fix this, I need to build what's called a "skirt" at the edge of the cells, to make them match. Since cells increase by powers of two, the high-res cell will always have all the points of its low-res neighbor. For example, in the figure, you can see the two cells match at every fourth point.
To close the gap, when I create a cell, I need to modify high resolution cells to match up with lower resolution ones on their border. For that, I need the scale factor at each edge of the cell. I tried keeping track of this incrementally, based on when cells split and combine, but the book-keeping was a nuisance. Finally, realizing there are only 100 cells, I just did a brute force pass over the entire tree, rebuilding any cells that weren't right.
There are two ways I could make the high res cells match up at the border. One is to interpolate values for them. This is simplest, but I was worried. Whenever you compute a vertex using two different algorithms, you are asking for trouble. Here I have the interpolated vertexes computed in my code vs. the edge of the larger cell as drawn by the display. If these don't match exactly, there will be rasterization differences and you'll see a line on the screen.
The other way to do it is to draw a triangle pattern than uses the four inside (high res) vertexes, and the two outside (low res) vertexes. I tried this, but there's no really obvious pattern of triangles. It gets a bit messy at the corners, when you are trying to adapt to two different neighbors. So I just coded the interpolation version, which seems to be fine.
Now I have a smooth landscape that I can move around in. Am I done yet? Well, no.
Z-Fighting, or "Flimmering"
A fundamental problem with a far horizon is the Z-buffer. This records the distance of each pixel, so that polygons can be painted in any order. When a new polygon is rendered, the distance of the new pixel is compared to what's already on the screen. If the new point is nearer, it is painted. If it's farther, it is ignored.
Unfortunately, the Z-buffer has a fixed resolution. On my system, it's 24 bits deep. On older hardware (probably including some laptops) it will be only 16 bits deep. That means there are only 64K distinct distances. Because of the math used to map coordinates in perspective, the Z values will be tightly spaced near the eye, and very widely spaced in the distance. See this note for more detail.
Look at Figure 8 to see the problem. This would be a distant piece of the landscape. The vertical red bars are the two available Z values at this distance. Everything between the bars will get the same value. If we paint this from back to front, it will look right. If we paint it in reverse order, the Z buffer will be no help, and the mountain will look inside out.
At some distances, the situation will be even worse. At the distance where the depth value changes, the value will depend on round-off error and the exact position of the eye. So depending on tiny amounts of movement, the order of two overlapping polygons will change. This leads to a flickering of the graphics called "z fighting" or "flimmering." It's very annoying.
My distances run from 1/8 units near the eye, out to 64K units at the horizon, for a factor of 500,000. A 24-bit z buffer holds 16 million values, so with care, I could probably make it work. My initial implementation just showed a bit of flicker in the distance. But when I implemented the map view, which looks down on the landscape from 20,000 units, water was a disaster. There's just a thin layer of water over the land, and at that distance, the Z buffer does not have enough resolution. Water flickered in and out everywhere.
On the Mac, I was getting a 16-bit z buffer, and the demo was a disaster. So if I want to run this on less capable machines, I need to solve this problem.
One solution is to not use the Z buffer at all. I don't need it if I sort my graphics. The landscape is fairly easy to sort, but the water is a problem. In Figure 8 you can see what I did. The water is just a single polygon over the entire landscape. The actual intersection between land and water (circled area) is determined by the graphics card when it renders the landscape. Without the Z buffer, I would have to calculate the border of the water by doing the intersections myself.
If I sorted the land into individual triangles, I would have to mix in small triangles of water, since from a distance, you would see land, then the water behind that, then the land under the water, etc. Right now, I render water and land with two different shaders. That would mean switching back and forth between shaders on each triangle, which would ruin performance.
One thing I tried is getting rid of water as a separate polygon. At a distance, I could just raise the sea floor, color it like water, and not have any separate water polygons to sort. See Figure 9. The version on the left is with a water polygon over the landscape. On the right, the landscape has been flattened at the water line and colored based on the depth of the water beneath.
The loss of perspective means the outline of the underwater terrain is in a different place. The shoreline is also rougher since it's done with grid points, not from the intersection of water and terrain. But in the distance, this would be close enough and would be much simpler to sort and render.
So sorting is an option, but kind of a nuisance.
Finally I decided to just extend the Z buffer by using it twice. I draw all the distant landscape, farther than 256 units. The Z buffer depths are now handling only the distance from 256 to 64K, a factor of 256. After this pass, I clear the Z buffer and draw the close landscape, from the eye (1/4 unit) out to 256 units.
There's an extra cost for clearing the Z buffer between passes, and testing all the cells against the view frustum twice, but it seems acceptable. See Figure 10 for the two halves of the landscape, far and near.
Unfortunately, the two halves are still too much for a 16-bit Z buffer. I've tried it on the Mac and there is still a lot of flimmering (love that word). I got a decent version to run there with three passes over the landscape. Surprisingly, it's still keeping up with 60 fps even running full screen. I still have some minor issues, but I will probably release the demo without fixing them. It's already been too long since the last update.
I have to mention that I had a really nasty bug in this area. Some of you may remember that I started with a DirectX implementation. I was using a left-handed coordinate system and using DX routines to initialize the projection matrix. When I switched to OpenGL, I needed to initialize the matrix myself. I also didn't want to change my coordinate system. So I just used the same projection matrix set by DirectX, as indicated by the documentation.
This has worked fine for months now, and I had no reason to think it was wrong. But in my previous demos, I had never relied on the actual clipping of graphics by the front and back planes of the view frustum. When I implemented this two pass approach, nothing worked as planned. I kept getting odd bugs in the image.
You know how it is with debugging -- you play with the thing you most recently changed. Then if that doesn't fix the problem, you back up to less recent changes. The idea is that if something doesn't work, you must have broken it. I absolutely could not find the problem with my rendering or with the frustum test I use to check if an object is visible. Yet some objects which should be drawn were being culled, and others that shouldn't were being drawn twice.
In despair, after days of messing with this, I finally just drew a line of cubes in front of the eye, and set the front and back planes to values that should have clipped some of the cubes out. And it didn't. That finally got me to look at the projection matrix, which I had just assumed worked correctly.
And it turns out that DirectX assumes the projected Z values range from 0 to 1. And on OpenGL, the projected values range from ... -1 to 1. Sigh.
With the new projection matrix, all kinds of things started to work. It really is amazing how something can be completely wrong like that for months and never cause a problem. Software is perverse that way.
Odds and Ends
I have a problem with floating point precision. The application sends 32-bit floats to the display, and those have 24 bits of precision. That would handle an integer up to 16 million or so. If we had a world coordinate like 20 million, we could not store it exactly in a float. It would be approximated and the least significant bits would be lost.
In practice, this means that in 32-bit float arithmetic, 20,000,001 - 20,000,000 is not 1, but zero. If the user were positioned out at coordinate 20 million, we would not be able to calculate his new position correctly when he moves. The position of landscape cells would also be incorrect. Nothing would work.
In the demo, this is not a problem. It would take you about 14 hours of movement at max speed to reach the areas where precision runs out. In the real game though, we'll have an entire solar system to deal with. 20 million meters is 20,000 kilometers, a very reasonable coordinate to use.
Fortunately, this is easily solved. In the application, we can use double-precision coordinates, which have 53 bits of precision (exact values up to 9,007,199,254,740,992.) To avoid sending those to the display, we can work in eye-relative coordinates, which keeps our values in the range 0 to 64K (the view distance.)
Finally, creating a cell of landscape takes a bit of time. On my machine, with compiler optimization turned on, it's about 7 milliseconds. A single cell would be no problem, but the code creates many at a time, when the user moves into a new area that has to be subdivided. Doing that all at once means the demo drops frames. So I have to create a list of out of date cells and regenerate them in a background thread.
Here's a video of the program in action. First, I show the update of the grids as you move. Then there's a eye-level view of grids being built and combined. Finally, the textured view with water, and no grid lines.
For Windows, download Part 28 Demo - Windows.
For Linux, download Part 28 Demo - Linux.
For Mac, download Part 28 Demo - OSX.
Here are the controls:
The Source Code
blog comments powered by Disqus