Monday, July 2, 2018

Procedural City: Bridges and Tunnels

I'm still working on the procedural city, even though I took a break from it to work on some other things. Instead of adding more objects along the city streets, I decided to go back to trying to improve the road networks connecting cities together. I didn't like how much the terrain height was changed to place long connector roads. There was too much elevation change, and too much dirt/rock added and removed. Engineers and city planners don't just fill in entire valleys and carve space through mountains to build level roads. They build bridges and tunnels.


It took a considerable amount of time and effort to get bridges and tunnels working in 3DWorld, much more than I initially expected. This was more than the week long project I thought it would be. It seemed like every aspect of them required low-level infrastructure changes to the procedural city system. I'll start by listing some of these challenges and how I solved them.

Placement of both bridges and tunnels is tricky. This requires a certain cooperation between the road placement system and the terrain heightmap system. Both the road networks and terrain heights have to be specifically adjusted to fit these structures in properly without seams or other artifacts. Since these are two different classes/systems in 3DWorld, this required some API changes so that they could better communicate with each other. There were also problems with precision, as the heightmap values can only be modified at its native resolution of around 2 meters per sample.

Bridges and tunnels introduced some new rendering challenges. Everything else in the scene is assigned to a single terrain tile. Most objects are sorted by tile and iterated over in tile order. Per-tile shadow maps and other state are used for drawing these objects. Buildings and cars are small enough to fit into their parent tile with a reasonable shadow map border. Roads are drawn in sections representing individual blocks, which are assigned to tiles. However, bridges and tunnels can be longer, and may cross multiple tiles. I ended up having to split some of the longer ones into two or more separate parts, each of which is drawn using different state/texture bindings. This worked, but added a lot of complexity to the drawing code.

Texturing was also more difficult. The various drawn parts of bridges and tunnels could be high aspect ratio. For example, the bridge guard rails are as long as the bridge but only a few feet high. I had to add support for custom texture scaling for the various cube faces.

Another problem I had to overcome was player collision detection; more specifically, setting the correct z-value (height/altitude) for the player position. Up until now, the player has always been placed exactly on the mesh surface in tiled terrain mode. That is, unless flight mode had been enabled. This makes player physics and collision detection easier because it's mostly 2D. The terrain height is set equal to city and road height to keep things simple, which means that placing the player on the terrain would automatically also place them on the road surface. This system breaks when bridges and tunnels are added, because now the player can be on a road surface that's above or below the terrain mesh. Furthermore, we need to keep track of the previous player z (height) value so that we know if the player is on vs. under a bridge, or inside vs. above a tunnel. I had to add collision detection to keep the player from falling off a bridge or moving through tunnel walls. All of this required significant changes to the code. Cars always follow road surfaces, so at least I didn't have to special case car physics to work with bridges and tunnels.

Tunnels had some additional issues that I had to solve. These are discussed in the tunnel section below.


Bridges are currently placed on road segments that meet the following requirements:
  1. Both end points are at similar heights. The road surface can have at most a minor grade.
  2. Both end points must be significantly higher than the average terrain height of the span.
  3. No point along the length of the bridge can be higher than the end points.
  4. There is a minimum required volume (height integral), otherwise why even build a bridge?
  5. Bridges are clamped to a reasonable size range from 5 to 128 texels (~10 to 256m).
  6. Two bridges can't be placed close together (within adjacent road segments).
With these constraints, I get two bridges for my test scene of five cities. I can tweak some parameters to get three additional bridges, though their placement looks somewhat odd. None of the bridges are quite level. I don't remember ever seeing a sloped bridge in real life, though I don't see why it can't be possible.

I chose to implement suspension bridges with variable length and height designed to fit them into the terrain. Bridges are procedurally generated with between 16 and 48 parabolic arch segments and support cables, depending on bridge length. They may look complex, but there's generally only one bridge visible at a time so I had no performance problems drawing them. I placed streetlights along the interior sides of each bridge between the road surface and guard rails. Bridges cast and receive shadows like everything else in the scene. I think their shadows look much more interesting than building shadows. Here are some bridge screenshots.

Medium size bridge over a deep canyon, with shadows. Cars can be seen crossing the bridge.

Bridge shown from a different viewing direction.

Note that only the road surface, guard rails, and bridge bottom are textured. The supporting arches and support cables are left untextured gray. These represent smooth painted or bare metal. Maybe I should have used some sort of texture or normal map that included bolt patterns for the arches?

Here is a larger bridge over a shallower valley. Real world engineers probably would have made the road curve around this depression rather than spending all that money constructing a bridge. In my defense, the original placement algorithm didn't want to put it here. It only wanted to place that one bridge in the previous image. I had to tweak some parameters to get another bridge, and this is what I got. Note that grass is placed under bridges, but large trees are not. I found it too difficult to ensure the tops of the trees didn't collide with the bottom surfaces of the bridges. I just mask this area as "no trees" to avoid the problem.

Large bridge over a wide, shallow, tree-covered valley.

Here is a night time view of a bridge, with a city in the background. Streetlights are placed at uniform intervals on both sides of the road. They do a good job of lighting the road for the cars. I made it easy to instance this particular streetlight model wherever it's needed. I used the same streetlight system for bridges as I did for roads. This automatically handles drawing, shadows, collision detection, and night time light source generation.

Night time bridge scene with cars, streetlights, and a city in the background.

City lights at night, with a large bridge in the distance.

I placed the streetlights a bit outside the bridge in this screenshot to get a better shadow effect. The bridge support cables really cast some interesting shadows. However, the streetlights don't look right floating in space like that, so I can't leave them there.

Closeup of bridge road surface with shadows. The streetlights have been moved outside the bridge for more extreme shadows effects.

That's all for bridges. Next, on to tunnels.


Tunnels use a very similar placement and drawing system to bridges. At first glance they seem simpler than bridges, at least the drawing part. But I did encounter some new problems when adding support for tunnels.

First, I needed a way to remove (not draw) the terrain mesh at the bridge entrances and exits. If I was using a voxel approach, I could just carve the tunnel shapes into the voxels. It's more difficult to add tunnels to heightmap based terrain. Fortunately, I didn't need to draw the terrain on the inside of the tunnel because it's occluded by the tunnel walls. I eventually decided to implement a terrain mask by setting an invalid state in the landscape texture splat mask. I'm using the four RGBA texture channels to store terrain weights for {sand, dirt, grass, and rock} materials. The fifth material, snow, is calculated by subtracting the sum of the other four weights from 1.0:
snow_weight = 1.0 - sand_weight - dirt_weight - grass_weight - rock_weight

At first glance it seems like there's no room to store a draw/transparency mask. After thinking about it for a while, I realized that I could set the weights to an invalid state such as {sand_weight=1.0, dirt_weight=1.0} to indicate that this mesh texel should not be drawn. This combination of weights can never be procedurally generated in a real tile because they sum to more than 1.0.

While this works great for disabling individual mesh texels, the solution isn't perfect. The first problem is that the mesh is projected into the horizontal X-Y plane. What I really want is a vertical hole in the X-Z or Y-Z planes for the tunnel opening. The second problem is that this has a limited resolution set by the texel resolution of the texture weights mask. For reference, a texel is around 2m/6 feet and the road surface is slightly more than two texels wide. I was only able to work around these issues by making the holes in the terrain larger, and placing a tall concrete block facade at both entrances of each tunnel. This does hide the edges of the holes, but it looks a bit odd and unrealistic. The math for where to place the terrain holes and the facade is also very tricky. It requires some adjusting of the terrain heights to get a steep slope at tunnel entrances as well. This took hours of trial-and-error to get right.

The third problem with transparent pixels was a bit of a surprise: it breaks terrain occlusion culling. The occlusion culling system selects nearby tiles with steep mesh areas as potential occluders of other, more distant background tiles. This improves drawing performance by allowing the rendering system to skip entire mesh tiles that are occluded/hidden, along with whatever objects (trees, grass, etc.) are placed on them. However, this system isn't aware of tunnels that cut through transparent areas of the mesh. When the player is inside a tunnel, the terrain on the other side of the tunnel may suddenly disappear! My first attempted fix was to just disable terrain occlusion culling when the player was inside a tunnel. This almost worked, but still failed to disable occlusion culling when the player was in front of the tunnel looking through it. A better solution was to remove terrain tiles with tunnel openings from the potential occluders pool.

Finally, I had to clamp the mesh height to a minimum value along the length of each tunnel to ensure it stayed out of the tunnel. We can't have terrain blocking the way. Normally, this doesn't happen, but I did see one tunnel with a dip in the middle that I had to fix. I guess this tends to occur more often when the terrain is steep and noisy, such as in the mountains. After that fix I don't see any visual artifacts.

The parameters I used for tunnel generation produced five tunnels of various length and slope in my test scene. I added streetlights to tunnels as I did with bridges. Cars can drive through tunnels without problems - finally something that just works without requiring a complex fix! I haven't yet added indirect lighting or ambient occlusion to tunnels, so the lighting looks a bit flat.

Here are some screenshots of tunnels with cars driving through them. Note that the pine trees are probably too large, and the grass blades are definitely too large. Since vegetation isn't the focus of this post, I didn't bother to take the time and fix that. In fact, I didn't even notice the large grass blades until I added the screenshots to this blog post.

Tunnel through the mountain with tall facade and upward sloped road surface.

Cars going through a long tunnel, with a bridge on the other side. Please ignore the oversized grass.

Here are two night time views of tunnels. As you can see, tunnels also have the same streetlight models as roads and bridges. Shadows work here as well.

Tunnel at night, lit by streetlights and car headlights.

Inside of a tunnel at night. City building lights can be seen on the opposite side entrance.

Maybe tunnel streetlights should be on even in the day time? Maybe cars should always have their headlights on while in tunnels? That sounds like future work.

Overhead Map View

I added roads, bridges, and tunnels to overhead map view to help debug their placements. Then I decided I liked the look of that, so I added city blocks, cars, and buildings to map view. This produces a nice cartoonish aerial view of the city with pixel accuracy. The user can pan and zoom using the mouse and arrow keys similar to Google Maps. Each pixel of map view makes a ray query into the city database that returns a hit color. Draw time isn't that great, but at least it's multi-threaded. I haven't attempted to make these sorts of queries into the city data optimal. I only get around 10 FPS, but that's good enough for a map.

Overhead map view of road network and cities: gray=road, white=bridge, brown=tunnel, lt_gray=plot, dk_gray=parking lot

Overhead map view of a city showing roads, buildings, parking lots, and cars. Some buildings are the same gray color as the plots and can't easily be seen.
This gives as sense of just how large this scene actually is. I haven't implemented moving cars in map mode yet. The control flow currently doesn't even call any of the physics state update. That can be future work. [Update - it's done: now cars move in map mode.] Another future work item is setting the plot colors so that they can never be the same as a building color.


Now that I have bridges and tunnels, I can go back and add more complex road networks. It's likely possible to allow city interconnect roads to cross above or below each other. I'm not sure how much work that would be. I can probably also enable roads over water. I didn't originally want to handle that case because the resulting mesh + water didn't look right. Now I can just make bridges over the water and not have to worry too much about adjusting the mesh height just above the water level.

I was also thinking of maybe adding railroad tracks and a train that goes around a loop. I definitely need to find some gradual bend textures though - trains don't go around sharp 90 degree turns. At some point I need to work on multi-lane roads as well.