Monday, February 26, 2018

Epic Fails in City Road Generation

This is a follow-up to my previous post on city generation where I show some of the fun bugs I had in the code and other failed attempts at placing roads. This first set shows off some actual bugs, though I had to go back and re-break the code in order to take these screenshots. Keep in mind that I did, in fact, encounter these problems when coding this stuff up. Roads aren't easy!

Here we have a road connecting two cities that are on opposite sides of this city shown in the screenshot. It was some problem with the tracking of which city the road is supposed to connect to. Roads are placed after city plots, so they have final say in what the terrain height should be.

But sir, you told me you wanted an express lane THROUGH the city!

This one was a failed intersection test between two connector roads. I was checking for overlap in all three dimensions (x, y, z). These roads don't overlap in z, but there's still an intersection. Just because they don't overlap in z doesn't mean they're okay! Only dimensions x and y should be checked. I had to print all sorts of debug text to the terminal to figure this one out. Doh!

We ran over budget constructing all these elevated roadways, and we didn't have the funds to dig the tunnel. We'll just have to put it on CA Proposition 39 in June for voter approval of a $9 parcel tax.

This is some problem with setting the height of the small 90-degree bend section at the wrong place in the control flow. The two 90-degree straight segments cause some interference here, and the bend has to smooth it over in a postprocessing pass. It took a while to come up with a fix for this one. I had to make several attempts before I got something that fixed all variants of this problem.

If you're not going to add a guard rail, can you at least post a warning sign? On second though, this might be good for drift racing!

Here's what happens when the slope direction Boolean is inverted. A number of different variables are XOR-ed together here to determine the sign of the slope of each road segment. It took a lot of trial-and-error to come up with the right conditionals. Maybe I shouldn't have been so greedy, trying to pack this info into a single byte in memory for each road segment. Ah well, I got it working in the end.

"Speed Bumps"

In this case, the two roads don't overlap, but their sloped boundaries do. The road on the right is created first. The road on the left is going to a higher altitude destination city. It creates a sharp cliff that falls to the right, then the smoothing pass smooths it out - right on top of the other road. The fix is to expand the road by its smoothing border before checking for intersections with other roads. It's a good change anyway, as it spaces roads out better. Bonus: the texture is all squished in that road segment in the lower left corner between the two intersections.

I'll take the high road and you take the low road. Sucker.

A similar problem can occur with cities, since they also have smoothing borders. I had to fix the problem in the same way as roads, by padding city bounding cubes by the smoothing distance prior to checking for intersections.

Someone forgot to build a retaining wall. Oops. I guess the 5th floor tenants get their backyard gardens after all.

I'm not sure exactly what caused steep roads to dip under the terrain. It's probably a floating-point rounding issue when converting to/from integer grid points/texels, or maybe during the 16-bit height <=> floating-point value calculation. One fix is to shift the road up in Z by an amount equal to (dz/dx)*pixel_size_in_x. I'm not sure if this is the correct solution as it causes steep roads to "float" above the terrain, but it's one of the only things I tried that works. As long as the steepness of the road is limited, it's not too noticeable.


At one point early in road development, I had a problem where the grass and roads were using two different coordinate systems. Grass is owned by the terrain tiles and is in tile-relative coordinates, which change as the player moves. Roads, cities, and buildings are always in constant global coordinates so that their vertex data can be stored on the GPU once and reused. A bit of math was required to fix this problem.

Can someone send a landscaping crew out to cut the grass growing on I-101? Maybe that will keep the cows from grazing in the middle of the road.

These next four screenshots weren't actual problems I ran into, but they still look interesting. This is the insanity resulting from disabling the connector road intersection tests so that they can go anywhere they want without restrictions.

Connecting every city directly to every other city is now possible, but not a good idea:

Ready for some off-road action? I think the engineer was off his meds when designing this.

A road was routed underneath this city. Presumably, it connects together two lower elevation cities on opposite sides of this one. I can't really tell in all the chaos. Some buildings have decided that they want to use the mesh height from the road rather than the mesh height for the rest of the city.

To protect against nuclear attacks, this shopping mall was built under the city. Or maybe it's a secret spy lair (with a big road leading up to it)?

This is the same problem, but inverted. Here the road connects together two higher elevation cities, dragging some buildings up with it. I could fix both of these issues by using the city elevation for buildings rather than terrain elevation. But this is just an experiment; this situation shouldn't come up, so why bother trying to handle it?

Now guests on every floor can have a room with a view! I just hope the kids don't decide to roll tires down that hill.

In this next case, the upper road was created first, and the lower roads were created later. Once a road is routed, it's done. The lower roads will modify the height of the terrain, but not the height of the upper road. In this particular case, it looks like a pretty cool bridge, though it needs some actual structure to be more realistic. Maybe I'll try to come up with a way to make this work. We still need to get rid of that road in the very front though.

A marvel of modern engineering, or a waste of our tax dollars?

That's all. I'll spare you the dozen or so screenshots of misaligned and incorrectly oriented road textures, which was another big time sink.

Sunday, February 25, 2018

Cities With Roads

It's been over a month since my last post. I had been working on fixing the ship AI for universe mode planet colonization, which required me to constantly run simulations on my PC. That topic doesn't make for a very interesting blog post because it's too technical and there aren't any good screenshots. However, in the past two weeks I've switched back to working on terrain and cities. This time I'm trying to combine the work I did with city generation and eroded terrain to create an environment that's a mix of natural and man-made structures. The end goal of the 3DWorld project is to generate a procedural universe that the player can seamlessly explore, from galaxies all the way down to individual trees and buildings. There's still so much work to do. The new addition to 3DWorld is city road networks.

I'm starting with the same 7Kx7K heightmap output from the erosion process described in a previous post. I exported it to a 65MB, 16-bit PNG image so that I can reload it without redoing the erosion simulation. This scene is huge, around 14km on a side. The cities are currently all placed in the relatively flat area in the bottom center of the map, between the ocean to the south and the mountain range to the north. Remember that this is an island, even though there's very little water in the screenshots below.

The steps I'm using to generate and connect cities are:
  1. Determine city location(s) by looking for relatively flat areas of the terrain, away from water
  2. Flatten a rectangular area of terrain to the city elevation (avg terrain elevation)
  3. Select the location of X and Y roads based on user-specified parameters
  4. Split roads into road segments, 2/3/4 way intersections, and building plots in between
  5. Create road networks that connect all cities (straight roads and roads with one 90-deg bend)
  6. Smooth the mesh around roads and intersections so that they're slightly above the terrain
  7. Generate procedural buildings and place them into the city plots
Items 1-6 are described here. Procedural building generation was explained in some previous blog posts and won't be discussed again. Look here and here for reference. All of these steps take less than one second of runtime: heightmap texture <=> floating-point array (330ms on 4 cores/8 threads), road network generation (70ms), and building generation/placement (185ms). This is much faster than the 2.1s actually spent loading the heightmap image as a texture.

City generation first reads a configuration file that specifies the size and number of cities, road length/width/spacing, max slope, terrain smoothing parameters, building parameters, etc. In total, there are 12 city parameters and 45 building generation parameters. These can all be edited by the user to customize city generation.

The first procedural generation step is selecting a site for each city. A few thousand locations are randomly chosen from the user-selected region of the heightmap, and the best one is selected. Locations are scored based on the RMS height difference between the average height and each height value around the perimeter of the city. I chose to use the perimeter rather than the full site area because it's more efficient to compute. Its unlikely for the player to notice if the city happens to flatten an entire hill or fill an entire valley anyway. It's more noticeable when there are steep slopes at the edges of the city. Each site must also not overlap a previous city, and must contain no water. I could have it fill in the water with land, but I do like to keep all of those small rivers and lakes.

Once the best site has been selected, that area is flattened to an elevation equal to the average elevation around the city perimeter. Note that the heightmap is normally stored as 16-bit integer values, but is converted to/from a floating-point array for the purposes of city generation. This conversion process takes about half the total city generation time. A boundary region is used to gradually transition from the city's elevation to the original terrain elevation to avoid sharp cliffs at the edge of the city. A smoothstep function is used to prevent slope discontinuities that would otherwise be obvious and appear unnatural to the player. Roads are flattened and smoothed in a similar way, but with a more complex function that handles fixed (but nonzero) slopes. The flattening step also replaces any grass inside the city perimeter with dirt.

Roads are placed on a uniform grid that exactly fills the city area, and are oriented in both the X (east-west) and Y (north-south) directions. The config file defines road width and spacing values. 4-way intersections are created in the interior of the city, 3-way intersections along the edges, and 2-way intersections at the corners. The space between roads is filled with a tiled concrete sidewalk texture that matches the border of the road and intersection textures. Buildings will be placed in these areas in the final step.

Intersections, plots, and road segments between intersections are sorted into the terrain tiles that contain their center points for drawing. This also serves as a useful spatial subdivision for later collision queries. For each visible tile, the city objects associated with it are drawn using the tile's shadow maps. This system is meant to scale to very large maps with potentially hundreds of cities, where only a subset of the cities is visible at any one time. I've tested it with 49K buildings and 90K road segments and still get 136 FPS (frames per second).

The screenshot below shows a pair of adjacent procedurally generated cities with roads and buildings. Note that the buildings all cast correct shadows on the roads and sidewalks. At this point in development, the cities haven't been connected.

Two adjacent cities with roads and 1268 buildings, viewed from above.

The player is free to walk around the city. There are no vehicles yet, but it's possible to walk very fast using the "R" key. The buildings have player collision detection enabled. The terrain can be edited in realtime as well, but the buildings and roads won't move with the terrain height like the vegetation does. Below is a "street view" image showing another city in the background. To give you a sense of the terrain resolution relative to the objects, a city road is slightly larger than 4 terrain texels wide.

View of the road bend at the edge of one city, with another city in the distance.

There are some minor issues visible in this screenshot that I might go back and try to fix later. There are texture seams between some of the intersections and the roads. It might help to rotate or mirror the textures to line them up better. I could look for a different set of road textures, but this set was the best I could find in my initial searching for free textures.

You can see some grass sticking up through the sidewalk at the edge of the city. This has been fixed already. Grass and plants are 5-10x larger than they should be compared to other city elements, and trees are 2-4x larger. I'm not sure if I should make the vegetation smaller, or make the buildings larger. If I make the vegetation smaller, then I have to generate a whole lot more of it to fill the scene, which will hurt scene creation time and frame rate. If I make buildings larger, then they don't look right against the mountains, lakes, and rivers. I'll leave it the way it is for now. Maybe I'll do something about it later.

Here's a shot where I turn the camera around to view the mountains next to the city. Everything shown here is real geometry. The player can walk into the mountains seamlessly.

Road at edge of city with mountains to the left and buildings to the right.

This is what the city footprint looks like without the buildings. The grid of roads can more easily be seen, along with the sidewalk textured plots where buildings will be placed. While cities are level, roads can be sloped to connect two cities of different elevations. The road that cuts through the hills in the back left is sloped upward. I have pine trees enabled since the scale problem isn't as obvious without the buildings. Note that the vegetation placement algorithm will avoid placing grass, trees, plants, and other scenery objects over the city and connector roads. The bounding cubes of cities and roads are used as blockers for scenery placement.

City plots, local roads, and connector roads shown without the buildings.

The image below shows how several nearby cities have been connected by roads. In this example, I configured the road router to connect the first (center) city to each of the other cities with a single straight road. Right now I only have road textures with a single lane in each direction. I'm not sure if I want to add another set of textures for multi-lane highways between cities. I've disabled fog to make the distant city in the back more visible.

Four connected square cities shown without fog or trees to better view the road network.

Here is another screenshot showing how two cities are connected by a road through the hills. The connection algorithm chose to place the road near the edge of the city to minimize the amount of material added/removed (required terrain height change) for placing a straight road. If the road was placed more toward the center of the city, it would have cut deeper into the hills. I like how the pine trees and terrain cast shadows on the roads. These shadows will move with the position of the sun.

Connector road cut into a wooded hillside. This was the location that required the min amount of height change.

This next image shows a view of the downtown area. The camera is on a road in the middle of a city, looking down the length of the road. The large office towers look good here, and seem to be the correct scale relative to the road. Now all I need to add are streetlights, traffic lights, signs, and maybe even moving cars. It would look better if I could fill in all those small empty spaces between the buildings. These spaces are too small to fit additional buildings.

Street view inside a city. It would look better with streetlights, signs, and benches.

Here's a screenshot taken from the roof of a building. Buildings don't have stairs (or any interior), but I can use flight mode to get up here. Once I'm on the roof, I can walk around on it. There are 680 buildings in this city. Trees and mountains can be seen in the distance. Note that this screenshot, and all the others, are running at around 200 FPS.

Rooftop view from a tall skyscraper. Yes, the player can walk around on top of these.

After creating all the images above, I went back and did another pass at connector roads. First, I made the cities smaller so that I could place more of them in the same view area. I also added config options for size ranges of cities, which means that cities can now be different sizes and non-square.

Next, I changed the routing algorithm to try to connect every city to every other city. This isn't possible in general without bridges or tunnels, neither of which have been implemented. I had to add collision detection for roads colliding with the wrong city or other connector roads. If no valid path is found after 50 random attempts, the router gives up and doesn't connect that particular pair of cities. I could have added 4-way intersections in locations where two connector roads crossed, but I decided not to do that. That's a lot of complexity to add, and I was worried it would clutter up the scene with too many roads and intersections. Plus it's difficult to get the elevations of the roads to match at the intersection. I might go back and add a config option for that later.

Finally, I added support for connector roads with a single 90-degree bend. It would have looked more natural to use roads that were curved or had multiple smaller bends, but there are several problems with that approach:
  • My texture set only includes textures for 90-degree bends, and I haven't found any good curved/shallow bend road textures online that will tile with straight road textures.
  • It's not easy to connect non-rectangular roads together. Simple quads don't work well. They would either produce texture distortion/shear, or would leave gaps in the mesh.
  • The math is much more complex, and slower. It's difficult to determine intersections.
  • Flattening the terrain heightmap is both inefficient and prone to aliasing issues. Straight, axis aligned roads are simple rectangles in texture space, while arbitrary angle roads require complex line drawing algorithms to move in texture space.
I haven't attempted this yet, but it's possible future work. Even getting this far took me a few late nights of programming. For now we just get crazy right angle roads like this.

Small cities connected together by a network of straight and right angle roads.

These roads are all straight and have constant slopes. This means they tend to cut through mountains, creating deep valleys. They also create strange land bridges across low lying areas between two higher elevation cities. This doesn't look very practical. What where those civil engineers thinking! I'll bet these would make for some good runways though, if I decide to add an airport to my map. And as long as the plane can take off before the 90 degree bend. And clear those steep mountains.

Here's another shot. See the mountain pass the algorithm carved in the front right and those two elevated roadways on the left in the distance. The cities and buildings look pretty good though.

Several non-square cities of various sizes connected by some crazy long roads.

I decided that these long straight segments themselves were okay, but the fixed slope was not. I added a segment_length config option to split the connector roads up into multiple runs that could have their own slopes. The elevations of the intermediate points between segments were set equal to the terrain height so that roads roughly followed terrain. This removed the deep valleys and land bridges, but added some very steep road segments. Roads now went up the mountain and down the other side instead of cutting straight through it. This makes sense from an engineering perspective, at least for lightly traveled roads where vehicles can be expected to make it up and down the steep parts.

I decided that a slope limit was needed to prevent very steep segments. I chose a rise-over-run value of 0.3, which removed the small number of very steep segments while keeping the others. In cases where the midpoint between two road segments generated a slope that was too high on one side, the midpoint was moved vertically by either shifting the terrain up or down to try and straighten the segments out in Z (up). In the worst case, the road was converted back into a single segment with constant slope, assuming the overall slope (city elevation difference divided by city horizontal distance) was under the limit. These changes produced a road network as shown below.

Roads split into segments that follow the contour of the terrain. Road segments with slopes >0.3 were rejected. Fog disabled.

The road that's just to the left of center had too high of a slope to go over the hill, so it cut through the hill instead. There are still some strange paths, such as that one in the very back that goes up and down an invisible mountain. Note that the mountain is only invisible because I've turned the fog off and the draw distance of roads is larger than the draw distance of terrain. Overall, the results look acceptable, and are much more practical than the fixed slope roads. I'll keep this set of options for now.

I'll throw in an overhead map image so you can get an idea of what this looks like as terrain. Water is blue (of course), low areas are brown, mid elevation areas are green, and mountains are gray/white. Cities are same-color rectangles. For example, that large greenish-brown square in the bottom left is a low elevation city. Roads are thin horizontal or vertical lines of similar colored pixels. Some roads are sloped, giving them color gradients. Overall, the placement algorithm has done a pretty good job avoiding the mountains and deep valleys. The algorithm has successfully avoided placing cities and roads over water, as expected.

Overhead map view of center of heightmap showing how city plots and connector roads have changed height values.

City generation has been a pretty fun and interesting topic. I definitely want to continue working on it. Results seem pretty good so far, but there's so much more work to do here. Of course, this system is already getting complex, with over 1000 lines of source code. You'll probably see at least one more blog post on this topic. To summarize, future work items include:
  • Addition of detail objects within the city (lights, signs, benches, cars, etc.)
  • More realistic roads with more/shallower bends, more gradual slopes, less terrain editing.
  • Smarter building placement that adds larger buildings to the city interior. (Zoning?)
  • Fixing of incorrect size scale for buildings vs. vegetation.
  • Fixing of texture seams for different types of road sections.
  • Addition of normal maps and detail textures for roads and sidewalks.
  • Building interiors! Well, no, probably not any time soon.
  • ... But maybe I can add windows and doors to some of those brick and stone buildings.
I definitely think I'm going to work on cars next. It would be awesome to have tiny cars and trucks moving about on the roads within and between cities.

Tuesday, January 16, 2018

Fields of Grass to the Horizon

This post is an update on the current state of 3DWorld's tiled terrain grass rendering. I've shown infinite fields of grass in a previous post, but since then I've made some graphical improvements. For example, I'm now using GPU tessellation shaders to generate curved grass blades close to the player camera.

Near to far levels of detail include (ordered closer to further):
  1. Individual curved grass blades formed by tessellating the original triangle into many polygons
  2. Single triangle, textured grass blades that move in the wind
  3. Single triangle, untextured green grass blades with no wind
  4. Larger triangles formed from recursively merging two adjacent grass blades into a single triangle where area = sum(areas) and color = average(colors)
  5. Coarse triangles that translate down into the terrain mesh with distance until they disappear
  6. Simple grass texture applied to the 3D mesh surface consisting mostly of green color + noise
The tessellation, triangle merging, and height translation all happen smoothly as continuous functions over distance to prevent noticeable popping artifacts. The only visual transition that I can see is a small amount of flickering/noise when grass blades disappear under the mesh in the distance, when viewed from high above the ground. I'm not sure what causes this. Maybe it's due to depth buffer Z-fighting. The textured => untextured and wind => no wind transitions are very difficult to spot. The tessellation changes and triangle merging are nearly invisible.

A set of 32 grass tiles is generated, and random tiles are selected for use across the terrain. The vertex shader calculates the z-value (height) of each grass blade from the heightmap textures. All vertex data for all levels of detail are stored on the GPU for efficiency. Hardware instancing is used to render all instances of each of the 32 grass tiles in a single draw call.

Here is an example video where I use the camera speed modifier keys to zoom in and out on the grass. The actual rendering is much sharper; video compression has made the grass somewhat blurry. I've disabled the trees, plants, and flowers in the config.txt file to make the grass stand out more and avoid distractions. Without the overhead of video compression, this normally runs at around 300 FPS (frames per second).

As you can see, grass has a nearly seamless transition from a distance of inches to miles. The result is a lush green field that stretches out to the horizon and scrolls to follow the player camera. It's possible to have the entire terrain draw as grass at 150-200 FPS.

Note that the grass colored ground texture is always used. This is here to fill in the space between the grass so that the blades don't need to be packed together as densely to achieve a thick looking cover. The texture and grass blades use the same average colors (across texels) so that they blend together better in the distance. They also use the same normals and shader lighting calculations. To make this work, grass normals are derived from the terrain mesh normals.

Here is a series of images captured of grass, from close up to far away. There are some scattered areas of sand and dirt with lower grass density to break up the scene and add more variety. These can be seen in the last two images. Again, non-grass vegetation and other scenery has been disabled for these screenshots.

The only problem I see with this approach is the tiling artifacts of the distant grass texture. Tiling is most noticeable in the final two images. I spent some time trying to fix this, but never really succeeded. If I use a highly detailed texture, it looks too repetitive. If I use a low contrast green texture, it looks too plain and uninteresting. If I transition between texture scales, the effect is noticeable, and it ruins the immersion. I was able to get away with that last texture scale trick with water because it was moving, but apparently not with grass. Interestingly, this isn't as much of a problem with the rock and snow textures. I wonder what's different about them?

Wednesday, December 20, 2017

Terrain Erosion

3DWorld's terrain generation looks pretty interesting with domain warp noise, but there's one thing that's missing: erosion. I already have erosion working for individual terrain chunks in ground/gameplay mode.  I'm using this erosion implementation from Ranmantaru Games which I've slightly modified to make it more efficient and configurable, and to make it work with a global water height value. The way this algorithm works is by placing one unit of water randomly on the map for each iteration, and computing the path that this water follows to a "sink". A "sink" can be an ocean, a local minima in the mesh, or the edge of the map. Material is removed from steep path segments and deposited when the path levels off, forming a series of peaks and valleys. Local minima eventually form lakes.

It currently takes 36ms to apply 5000 erosion iterations to a 128x128 vertex/texel heightmap. Here is an example of what this looks like. It's not too interesting, though this is proof that the system works.

Erosion on a single 128x128 vertex mesh tile.

This is fine for a single tile, but I want to be able to erode an infinite terrain consisting of an endless grid of tiles. I started working on erosion of large terrains as soon as I finished the previous blog post. My first attempt was to just apply the erosion algorithm independently to each terrain tile as it was generated, after the height values were assigned but before they were used for normals and object placement. Of course, this simple idea doesn't work. There are huge gaps between tiles where heights have been eroded to very different values. There are no constraints that force the edges of the tiles to line up. Take a look at the screenshot below.

Erosion applied independently to each tile produces terrible seams at the tile borders (erosion values are discontinuous).

The problem is that the water and sediment crossing each tile boundary isn't being tracked. Each tile starts out completely dry. There may be a large river valley in one tile that accumulates most of the water for the tile, but the adjacent tile doesn't see a single drop. The valley is deep in the first tile and nonexistent in the adjacent tile. When the river reaches the next tile, it basically stops flowing, and the sediment is lost.

One possible solution is to store data at the boundaries of each generated tile and use that as seed data for any adjacent tiles that are generated later. This has been suggested in a Reddit thread I started on the topic of Procedural Generation, but I haven't implemented it because I don't think this is an ideal solution. There are several problems. First, this only works when downstream tiles are generated after upstream tiles. If the downstream tile is generated first, there's no way to push the valley back up to the water source.

Second, the results will depend on the order in which tiles are created, which itself depends on the order in which tiles are visited by the player. The problem here is that if objects such as buildings are placed via editing operations on the terrain and saved, they may not be at the correct height later when the tile is approached from a different direction. If the user takes a longer route to the building, it may be floating in the air or buried under the ground. No, this isn't acceptable.

Another approach is to blend the heights between adjacent tiles to remove the gaps. While this is efficient and will produce seamless terrain, the results don't look realistic. River valleys may contain segments that go uphill. This is also unacceptable.

In the end, I decided that I only need erosion to work on island maps, at least for now. Islands are surrounded by water. Erosion stops at the water's edge, so there can be no underwater seams between tiles. All I have to do is clip the island out of the infinite world and generate the erosion solution for the entire heightmap mesh at once. I had to add two features to accomplish this: an option to write a terrain image file from the area visible in overhead map view, and an option to apply erosion to a terrain heightmap during import. This requires some extra steps, but the result is still fully procedural. While not infinite, it would be possible to automate this process for each island visited by the player. Below is an overhead map view of my selected island.

The island of interest. The island isn't exactly square, so some parts have been truncated and part of an adjacent island is visible in the upper left corner. The red dot is the current player position and the black dot shows player orientation.

I've taken a square clip of the terrain. The island itself isn't quite square; I've managed to clip off some small parts of it and included a bit of the adjacent island in the top left corner. This is close enough. The heightmap image will be tiled using mirroring to create a seamless terrain with no gaps between the edges of the image. When the player walks to the edge, the height values will be mirrored and repeat in another copy of the image. The resulting terrain is still infinite, but it repeats a finite amount of unique data. This solution may not work for fully infinite terrains, but it's close enough. The erosion results look just fine using this flow.

The island itself is pretty large. The square area I clipped out was 7085x7085 pixels, for around 49M pixels of data representing 7x7 km of data. This is 200MB of floating-point data, or 65MB when compressed to a 16-bit PNG image. Image writing time is 22s. The compression doesn't help much, so I may be better off using a raw BMP image format to reduce read/write times. However, I don't have any image viewers that can load a 16-bit BMP image of this size, which makes debugging difficult. Reducing bit depth from 16 bit to 8 bits loses too much resolution and makes the height values appear stairstepped like in Minecraft. That's not the look I'm going for. This image may see very large, but it's still a fraction of the size of the 16,384 x 16,384 Puget Sound dataset that has appeared in other blog posts such as this one.

I ran the erosion algorithm using OpenMP with 8 threads on 4 CPU cores including hyperthreading. Runtime was 18s for 10M iterations/samples. I just put an "omp parallel for" around the iterations loop. This implementation can suffer from thread race conditions, but I don't really care because there are so many random numbers used there anyway. This gives me a 5x runtime reduction. 18s is long compared to most of the other operations, but not unreasonable for a map of this size. It should be possible to save the post-eroded terrain back to an image for fast reloading at a later time.

Here is a zoomed in overhead map view of the upper right corner of the island, showing some rivers and lakes that have formed. This example uses domain warping for the noise calculation. I'm using a fixed water height here, which means those rivers and lakes have eroded down below sea level. In the future, I may want to have a way of generating higher altitude lakes where water collects. It's currently a rendering limitation related to water waves and reflections, not a generation limitation. This map looks fairly realistic to me.

Zoomed in view of the island's upper right corner showing small rivers and lakes that are a product of erosion.

Here are some screenshots showing erosion on large, smooth, rolling hills. I find that erosion results look cleaner and are easier to debug when domain warping is disabled. Sometimes it's hard to tell which valleys come from the procedural height generation algorithm and which ones come from erosion. The valleys form nice fractal patterns. Perhaps they're too narrow and deep? It would be nice to have the algorithm produce wider rivers/valleys for areas of higher water flow, which would make the results look more natural. Unfortunately, it's not clear how to extend the selected erosion algorithm to do this.

Erosion applied to a large rounded mountain, no trees. No domain warp has been enabled, so the mesh started out smooth.

Here is another view of eroded grassy cliffs at the edge of the ocean. Ambient occlusion really makes the canyons stand out. The erosion continues under the surface of the water. This is probably incorrect, so I better go fix it. ... This has been fixed in the other screenshots below. Does this look physically correct? It could be, compared to photos of Hawaii such as this and this and this and this, any of these, and other ocean cliff photos such as this.

Heavy erosion on the grassy cliffs near the ocean. Maybe too much erosion, especially under the water.

Here is how things look when enabling domain warping noise again. This image shows one end of the island with steep cliffs, some bays, and a few lakes. Trees have been disabled to make it easier to see the terrain itself, including the details of the narrow ravines. The small bits of greenery are other types of plants that are sparse enough that I left them enabled.

This very rugged terrain produced by domain warping noise has been eroded into many small valleys.

Here is a location along the coast that looks very much like Hawaii. The erosion algorithm now stops at the edge of the water to avoid eroding underwater features.

Another view of eroded domain warped terrain, near the ocean.

Here is an overhead view from a mile up showing a small mountain range and some thin lakes. Some areas between the peaks have been filled in with eroded sediment, producing smooth, flat areas.

Overhead terrain view showing some small lakes and small, sharp peaks that remain after erosion.

Erosion produces natural rivers, and lakes at the bottom of large watersheds. There are two lakes visible in the screenshot below. Each lake is fed by a network of short rivers, but the lakes are at local minima in the terrain and there is no place for the water to drain to. The area shown below is between some large mountain ranges and gets a lot of water.

Two small interior lakes with river networks formed from erosion. The water height is constant, so these lakes have been eroded down to ocean height.

I finally have real, physically modeled, procedural rivers. These rivers are a result of the erosion process, rather than accidents arising from the noise function values. Here is an example river surrounded by pine trees for a more natural effect. The trees are probably drawn too large for this terrain.

Finally, a real river that flows to the sea! Or maybe it's just a stream. Pine trees haven been added for a more natural look. No manual effort was made here, the results are purely procedural.

If I increase the number of erosion iterations by 20x from 10M to 200M, much of the terrain is eroded away. All but the tallest, sharpest peaks have been replaced by smoothly sloped hills. All the material in the mountains was turned into sediment and deposited throughout the scene. The lakes and bays become surrounded by deep canyons.

Erosion with 200M iterations rather than the usual 10M. The mountains have mostly eroded away into smooth sloping plains that eventually end in steep ravines and lakes.

Here is a final screenshot that includes a medium density forest of pine trees. All objects placed on the terrain by either an algorithm or a human should be at the correct heights with this approach.

Final terrain with pine trees, grass, and all effects enabled.

I'm pretty happy with the erosion results on this island. However, there are a few things I would like to improve as future work.

First, I think there are too many narrow valleys. I would like to see wider valleys in locations where the water flow is high. I'm not sure how to accomplish this in a clean, efficient, and stable way. It's not clear if the original erosion algorithm can easily be modified to get this effect. Maybe it can be accomplished with multiple passes over the terrain at increasingly larger grid resolution. I'm not sure if this would have too many grid artifacts or not.

Second, I don't like the manual effort involved in clipping out the island and tweaking parameters to make it work. The problem is that the clipping operation changes the min, max, and average height values, and this affects the biome distribution. The height ranges of the various terrain layers (sand, dirt, grass, rock, and snow) as well as water level are derived from the height histogram. This is estimated by taking a large number (~10K) of random height samples prior to generating any of the tiles. If I clip out part of the scene, it may not include the min or max values. For example, my clip might not contain the highest peak or the lowest part of the ocean floor. Texture layers and water level will be assigned differently when reading the heightmap image back in, which will change the look of the island. For example, it can create an island that's all snowy peaks and no water. To compensate for this, I need to experiment with various config file parameters using trial-and-error. I can have the heightmap clipping algorithm create a table with some constants such as real min and max heights, but there's still some manual iteration required. It should be possible to fix this, though it's a trade-off between a large upfront development cost vs. small amounts of manual work over time.

Saturday, December 16, 2017

Current State of Terrain Generation

I haven't done any major work on terrain or vegetation lately, but I'm constantly tweaking parameters and fixing minor problems. This post shows screenshots and a video of the current state of tiled terrain mode. The technical details have been mostly covered in previous blog posts, so I won't repeat them all here. Feel free to review some of my earlier posts if you're interested.

I've settled on Simplex noise with domain warping as the primary source of noise for procedural terrain height generation. The noise functions are all user configurable from a text config file in case I want to revisit them later. Take a look at my post from May 2017 for more information. Once the terrain is generated, trees, grass, and other scenery objects are placed on the landscape. The type and distribution of objects depends on terrain height/altitude and slope. These first three screenshots show how the noise algorithm can generate realistic looking rivers and lakes using a parallel algorithm where all height values are computed independently. Note that I'm using a 2D sine function here to form a grid of unique islands within an infinite ocean. This is why the terrain is often bordered by water. There's no technical reason why I have to use islands; the generation and rendering system works fine with an infinite forest. I just like the look and feel of islands.

Procedurally generated terrain with sandy lake surrounded by grass, plants, and trees.

Rivers aren't explicitly generated or properly connected based on water flow. They're just the product of narrow ravines produced by the domain warping function. All of the water is drawn at a constant Z height without regard for interior (lakes) vs. exterior (ocean) water. I've experimented with specialized river generation algorithms, but so far I haven't gotten them to work well in tiled terrain mode. In particular, there are heightmap seams at the borders between tiles (which are generated independently). River generation for infinite heightmaps is very difficult.

Procedurally generated terrain with a river that happens to appear.

I've switched from deciduous trees to pine trees in the next two images. 3DWorld can cycle through four tree modes using the F5 key: none, deciduous, pine, and mixed deciduous/pine/palm. In mixed mode, palm trees are placed near the water line, pine trees are placed on mountains, and deciduous trees are placed in between. This provides more vegetation variety, at the cost of increased generation time for new tiles and increased rendering time due to more draw calls. The increased generation time is due to calling multiple tree distribution functions per tile. The increased rendering time comes from extra draw calls and shader state setting for each visible tile.

Hilly terrain with lakes and pine trees.

I used the realtime terrain editing feature of 3DWorld described here to cover almost the entire surface of the ground above the water line with pine trees. I believe there are around 500K trees on the island and 50-100K trees visible in the screenshot below. 3DWorld uses 2D texture billboards to draw distant trees using only one quad (two triangles) each, which allows this scene to be drawn in realtime at 200 Frames Per Second (FPS). It's also possible to zoom out and create a larger landmass that contains 2M trees, 500K of which are in view, which can be drawn at over 60 FPS. This scene looks more like a dense pine forest, though the underlying terrain can hardly be seen.

Forest covered by around 100K pine trees placed with a large editing brush.

I recently optimized palm tree drawing using hardware instancing + Vertex Buffer Objects (VBOs) on the GPU. This allowed me to adjust the view distance of palm trees so that they're visible to the far fog distance, almost out to the horizon. Unlike pine trees, palm trees aren't usually rotationally symmetric about the Z (up) axis. I haven't been able to get billboards to work well with them. Therefore, each one is drawn in native polygon format using 20 palm fronds = 40 quads = 80 triangles each. In addition, trunks are drawn at various Levels of Detail (LODs) from single lines to 32-sided cylinders consisting of 32 quads = 64 triangles each. This allows me to draw more than 10K palm trees at over 100 FPS, as shown in the image below.

Tens of thousands of palm trees drawn out to the horizon at 143 FPS.

To finish off the screenshot gallery, I'll add an image of a sunset with long shadows and water reflections. If you look carefully, shadow maps are only used for nearby terrain tiles. You can tell which trees have shadows by looking at the lighting changes for distant trees. Terrain drawn beyond the shadow distance uses a more efficient, precomputed, low-resolution ambient occlusion lighting texture. These two modes are linearly blended to make a smooth transition for the player.

This is required to save GPU memory and CPU time for shadow map generation. I haven't used Cascaded Shadow Maps (CSMs) here because the overhead of drawing the scene multiple times (once per cascade) is too high, especially for the trees. Note that rendering tree billboards into the shadow map doesn't look correct; I have to use the full 3D polygon model of each tree, which is slow. There are a lot of polygons in all of those tree models! This is why I decided to precompute a separate static shadow map for each nearby tile instead.

Sunset on procedurally generated landscape and vegetation showing tree shadows and water reflections.

Finally, here is a video where I walk around the terrain and view some deciduous trees up close. You can watch me walk through a river similar to the one featured in the second image above. Then I enable flight mode and fly across the terrain at high speed. This demonstrates how quickly tiles can be generated as the player moves around in the world. In reality the framerate is a bit erratic, which can't actually be seen from a video played back at a fixed 60 FPS. The frame rate drops during frames where more than one tile needs to be generated, and the GPU must split its time between tile generation and scene rendering. In the end, I change the time of day. The sun goes down and the moon comes up, making interesting light reflections in the water.

This video shows that the grass blades are more than single triangles now when viewed from close up. This is a relatively new feature that was visible in some of my grass/tree fire screenshots but maybe not mentioned until now. I implemented this using tessellation shaders on the GPU. That's also how water waves are implemented in tiled terrain mode.

That's all for this post. Next time I'll probably talk about erosion simulation and water flow. I've experimented with these in the past but never mentioned them in the blog. I already have some interesting screenshots prepared. I haven't gotten erosion to work for infinite terrain tiles though. It currently only supports a single square tile at a time. I wonder if I'll be able to fix this in time for the next post.

Sunday, November 19, 2017

Procedural City Revisited

I introduced 3DWorld's procedural city generation and rendering in a blog post from a few months ago, back in June, then I switched to working on physics and fires. I was reading some online articles on procedural buildings recently, so I decided to go back and improve 3DWorld's buildings. I originally wanted to add real window geometry and building interiors. Unfortunately, that seems to be very difficult given the way I'm implementing buildings. One problem is that I'm using textures that include windows, which I found online. It's not easy to have 3DWorld auto detect where the windows are in the textures and replace them with geometry when the player gets close. Also, I don't want to create, download, or import 3D models of furniture. I want everything to be procedural.

Instead of adding building interiors, I made minor improvements to building placement, textures, rendering, optimizations, etc. Here is a list of the changes:
  • Buildings no longer overlap each other when placed (fixed intersection queries)
  • Added more buildings (denser building placement)
  • Collision detection now works on elliptical building footprints
  • Added roof detail cubes to buildings (AC units, antennas, etc.)
  • Improved building texture (better quality, more variety)
  • Added normal maps for all building textures
  • Fixed texture seams - they should all be gone now
  • Major optimization to building drawing - store vertex data on the GPU - 2-3x faster
I'll describe some of these changes in more detail below, and I'll add screenshots in along the way.

Procedurally generated city with dense office buildings, roof details, window textures, normal maps, and shadows.

New Textures

The original building system used several brick and concrete block textures for houses and small buildings, plus five office building/skyscraper textures. These were fairly low resolution generic textures I found online that were at least somewhat seamless, meaning the image tiles in both the X and Y directions. They all looked fine when viewed from a distance, but I decided that some of them didn't look so good up close. I went searching for better textures using Google image search. I found a site called SketchUp Textures that had a nice collection of skyscraper texture images. I created an account so that I could download my 15 daily free textures. The textures have pretty good variety and quality, but the resolution isn't that great. They're also odd sizes with aspect ratios from 1:2.5 to 1:3.5. They do offer a paid account that has higher image resolution. That's fine, I'll make do with the lower quality free textures. The smaller size/lower resolution textures load faster anyway (I'm using 12 of them).

Procedural city buildings, showing the unlit side. There are 16 unique office building textures and several additional textures for smaller buildings.

Normal Maps

Normal maps, or bump maps, are used as a cheap way to add apparent geometric detail to a model. They interact with the light to create fake geometric edges and shapes in what's really a flat polygon. Now, normal maps don't make all that much of a visual difference on office buildings. Building exteriors consist mostly of flat surfaces such as windows and walls. In fact, very tall building exteriors are designed to be smooth and aerodynamic so that they resist moving with the wind. Maybe there's some geometry around the edges of the windows and between the sections of walls. In any case, all modern games use normal maps, so 3DWorld is going to have them whether or not they're needed.

Unfortunately, SketchUp doesn't provide normal maps for their skyscraper textures. Most sites don't seem to do this. I've used CrazyBump to create normal maps from diffuse textures on my old computer in the past. Hm, it looks like my temporary license has expired. On the other hand, I'm in luck; I can install a new copy on my new computer for another one month free trial. It's a really nice tool, so I should probably buy it. I would definitely buy it if it was $10 or $20, but it's $99. That's a lot for a tool that I would use a few times a year. And it apparently crashes constantly...

The way CrazyBump works is that you first load a texture file, it asks you to pick one of two images, it presents you with a 3D rendering with a lot of sliders that can be moved around, then finally it saves a normal map image. The pick-an-image game is there to let the user decide which way the bumps go. Are those circles supposed to be holes that go down, or posts that point up? The sliders take more work to get right, since their default values don't work well on walls and windows. Fortunately, building textures all look similar to a tool like this, so I was able to use nearly the same settings for each texture. Unfortunately, there seems to be no way to save the settings, and the tool crashed when I try to load a new texture over the old one. I had to painfully repeat this process dozens of times for the 20 (5 old + 15 new) textures I was using:
  1. Open CrazyBump and wait for splash/title screen
  2. Select and load a texture. If it crashes (about half the time), go back to step 1.
  3. Pick the image that seems to make the windows point inward.
  4. Select a cube shape for preview, which is the best shape for representing a building. If I got the window direction backward, quit and go back to 1.
  5. Move the 9 sliders around to the positions I decided they should be in for most buildings.
  6. Save the file. If it crashes (occasionally), go back to 1.
Yeah, this was painful and took quite a while. I had to start the program at step 1 maybe 50 times. Each crash brought up that useless Windows 10 "Checking for a solution to this problem online" dialog box that must be clicked on twice (?) to make it go away. It would have been much faster if it didn't crash so much, especially if it saved the slider positions between textures. It would have been awesome if there was a way to write a script that just did these same steps on every texture and output two images for each one (bumps going in vs. out) so that I could pick the correct one at the end. Maybe there is a way to script it, if it could actually get through the script without crashing. Anyway, I finished them all eventually.

[Update: It seems like CrazyBump no longer crashes for me, so it must have fixed itself at some point. Huh. Maybe my computer just needed a therapeutic reboot.]

Normal maps can be seen on the window frames on the building on the left. The small building in the center casts a shadow on the building behind it.

Rendering Optimizations

Up until now I had been using distance culling, view frustum culling, and back face culling on the CPU to limit the amount of building geometry that was drawn each frame. Simply iterate over each part of each building using an acceleration structure and draw it if the following conditions are met:
  1. Close enough to the player (not beyond the far clipping plane/fog distance),
  2. Visible within the players view frustum (field of view), and
  3. Facing the player (not on the other side of the building)
The general idea is that you don't want to be drawing every single triangle of every single building every frame. Twice, if reflections are enabled. Three times, if dynamic shadow maps are enabled. With these tests, only a very small faction of the total building geometry was being drawn. I was normally getting 100-200 FPS (frames per second) for scenes such as the ones shown in these screenshots. But when viewing a large city center from above, with shadows, reflections, and grass enabled, it could drop below 60 FPS. Framerate was even worse when recording video.

Almost all of the CPU time was spent preparing vertex data and sending it to the GPU in a dynamic buffer. Building vertex data isn't stored in memory, it's generated from the overall building shape (from equations) on-demand. Every vertex of every triangle of every building has to be translated, rotated, and scaled to put it in into the correct position. Note that buildings are mostly sharp edges rather than smooth surfaces, so there isn't much sharing of vertex normals. Most vertices belong to only one triangle. I'm not even using indexed triangles here, it's not worth the added complexity.

Okay, we're only drawing about 5% of the total building geometry, but that still takes a long time. This system still needs to test a lot of build parts for visibility, and it's really slow to send dynamic vertex data to the GPU. How bad is it to build a GPU buffer of all of the geometry - every vertex of every triangle of every face of every part of every building? I initially though this would be unreasonable, which is why I didn't start out this way. It turns out to not be that bad at all. This scene has about 40K buildings, 4M vertices, and 1.8M triangles (800K quads and 200K triangles). Together this is only 113MB of vertex data - a lot less data than I expected - and can be drawn at 550 FPS. That's almost 3x faster than the old approach! Just let the GPU draw everything and don't bother culling any of it. Huh. I guess that's the way modern GPUs are to be used. Who needs code branches?

I was later able to further reduce the data to 104MB by removing the bottom surfaces of buildings, which usually can't be seen.

Procedural city viewed from above. There are 39,400 total generated buildings that stretch past the horizon.

Of course, it's not really that easy. There's the minor detail of the tile shadow maps to deal with. Each terrain tile creates and uses its own independent 2048x2048 shadow map. See, buildings don't move, and the ground doesn't move. I haven't yet implemented destroyable geometry in tiled terrain mode. Rather than rendering everything twice (shadow map pass + normal draw pass), the shadow maps can be pre-rendered once and reused. However, we can't just have one shadow map, otherwise we'll constantly need to update it as the player moves around and buildings go in and out of view. Instead, we have N shadow maps that are independently created and destroyed as the player moves around. One shadow map is assigned to each nearby terrain tile.

Ah, that's nice, and it works well, but it does cause a problem - we can't just render the entire city in one draw call per texture/material any more. No, the shadow map texture needs to be updated between tiles. Maybe there's some GPU trick for doing this that I don't know about. Maybe it can be done in Vulcan? I haven't come up with any GPU/driver trickery to make it work yet, so I had to throw CPU cycles at the problem. I used a hybrid approach between the old and new flows.

If the buildings were contained in or assigned to specific tiles then we could have one buffer per material per tile. This doesn't actually work though, because buildings can span multiple tiles and can be translated relative to the tile grid when the scene origin is updated. Instead, I have to keep the old CPU rendering code around and use it to draw nearby buildings that happen to reside in tiles that have active shadow maps. Instead of getting a 3x speedup, I only get a 1.8x speedup. Such is life. At least it's better than it was, and I still get 3x speedup outside of tiled terrain mode. If I disable water reflections it runs at over 200 FPS.

Building skyline at the beach. Buildings reflect in the surface of the water. One lonely windowless brick building is on the left. Can you spot the fish under the water in the bottom center of the image?

That's about it for this post. I didn't have too much new content, but hopefully this post helps to explain some of the problems that must be solved when procedurally generating and rendering cities. It's 10% of the work to make something that looks okay, and the other 90% to polish and fix all of the minor issues. On the bright side, this version of the city system runs at > 100 FPS in all cases and has no rendering artifacts, no texture seams, no glitches, no LOD popping, no shadow problems, and no other issues that I'm aware of. The city stretches for miles and looks just like in these screenshots, while allowing the player to move around at speeds up to hundreds of miles per hour in realtime.