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.