Procedural City: Building Interiors

I finally started working on generating interiors for 3DWorld's procedural city buildings. This has been on my todo list for awhile but I wasn't able to start working on it because there were some previously unsolved problems. The most important problem was determining how the player would actually view building interiors, given that existing buildings have fully opaque exteriors with fake windows and doors drawn on top as decals. There's no point in even generating interiors if they can't be seen. I considered several possible approaches:

• Let the player fly through buildings to see their interiors. (There's already a key/mode that disables collision detection and allows for flight.)
• Add a key/mode that will disable drawing the exterior walls of nearby buildings so that the interior becomes visible.
• Allow the player to open building doors and enter (somehow).
• Make windows transparent so that the player can see the interiors through the windows.

The first two approaches are the easiest, but they're not very realistic. I want to show the interiors in a natural way that makes the buildings look more real. Allowing players to open doors seems like a lot of work, especially since I would have to implement collision detection with building interiors. So I decided to try that last approach, making windows transparent. An additional advantage is that the windows should appear to be more real/3D rather than a simple texture overlay. While I thought this would be easy, it turned out to be quite difficult. In hindsight, I think adding collision detection for the interior would have been much easier.


Windows

The first task was to cut holes into the exterior walls for real transparent windows. I began with the smaller secondary houses and buildings because they already have windows and doors applied as a separate texture layer. Well, office buildings actually have doors now, but they're placed better in houses and smaller buildings. These generated windows look too simple and ugly and need to be replaced anyway. All I needed was a way to cut square holes into the brick and concrete block walls.

It turns out that this isn't so simple. The obvious solution is to generate quads (rectangles) for each window and subtract them from the walls using CSG (constructive solid geometry) operations. I already have this code from the ground mode collision cube framework. Okay, but how many windows are there? Let's see. There are about 14,000 total buildings. Each one has some number of sides, at least 6 on average. Some of the buildings are tall, but some are small houses, so there are maybe 4 floors on average. Each wall seems to have an average of 8 windows (skewed by the large buildings). So that would give us 14K*6*4*8 = 2.7M window quads, or 5.4M triangles (1 quad = 2 triangles). And that's just the window panes themselves. We also need frames to make them look nice, and all the wall geometry around the windows. That's ... quite a lot of geometry, even with these crude estimates. How many triangles is it exactly? I don't know, I didn't implement it this way. I can't imagine the generation times, draw times, and memory usage would be good!

We need to use a different approach. Opaque windows are currently drawn as repeating textures that cover each wall of the building that's intended to have windows. The same technique can be used here to mask off areas of the walls to not draw, then draw windows and frames in additional passes later. This took quite awhile to figure out. I wasn't able to get anything working that allowed the player to see into the front side windows, through the building interior, and out the back side windows. The best I was able to do was to cut out the windows from only the front facing walls of the buildings. That's probably good enough, considering walls will generally block the view later when I add them in. The steps/draw passes I used are:

1. Draw building interiors because they're not affected by windows (more on this later).
2. Draw back facing walls of buildings (for fragments not blocked by an interior wall). Walls are drawn as two sided surfaces so the backs are still visible.
3. Draw window panes with depth write only (no color writing).
4. Draw front faces of buildings. Any fragments/pixels that fail the depth test from the previous pass are not drawn. This is what produces the window holes.
5. Draw window panes + frames with dept test set to less-than-or-equal to fill the window holes.

If you're interested in the details you can find the code on GitHub here.

This black magic allows 3DWorld to draw walls, window holes, and frames with only a few hundred thousand quads rather many millions of them. It's not perfect. For example, there are some non-anti-aliased edges on the window frames, and things get messed up if the player flies through the windows, but it's good enough for now.

Here is an early screenshot showing buildings with windows cut into the exterior walls but before interior walls were added.

Large house with transparent window rectangles cut into the concrete block exterior, showing interior floors and ceilings.

Many buildings with window cutouts. There are too many windows across all of the buildings to use real geometry.

Walls, Ceilings, and Floors

The next step is to draw the basic building interiors: walls, ceilings, and floors. I've decided to only add these to Manhattan buildings formed from combining adjacent and intersecting cubes. This includes all houses and most of the smaller office buildings in the secondary city. These simpler types of buildings can be filled with Manhattan interiors and is a good place to start.

Ceilings and floors are the easiest. There's one of these for each story of the building. Ceilings and floors together form the separators between the different stories of the building. The first separator has only a floor and the last one has only a ceiling. [There are no ceilings in the attics of houses because there are no windows through which the player can see them.] These are added separately for each cube of the building's footprint where the number of stories is determined from the cube's height. At this point I haven't added any cutouts for stairs or elevators.

Walls are more difficult because they require procedural generation for placement and cutouts for doorways. I decided that all stories can have the same floorplan, which makes generation much easier. Walls can extend the entire height of the building cube, through all floors, greatly reducing the number of quads needed for drawing. This brings the number of walls down to a reasonable number so that I can generate and draw them all up front. Once I have enough details I'll have to start batching the generation and drawing by tile to spread the time out over many frames.

Walls are placed randomly one at a time into each cube of the building. Any walls that extend to an interior face of the cube where two parts of the building meet are converted to T-junctions. I had to spend many hours removing all of the interior parts of the exterior brick/stone walls so that they don't intersect with the interior plaster walls in strange ways. Each cube is recursively subdivided with a randomly placed wall, generally in the longest dimension, until the resulting space is below a certain user-configurable size. This forms individual rooms. Then I go back and remove sections from the walls to make open doorways that connect the rooms together. The resulting geometry is somewhat maze-like and not exactly representative of a real building. However, it's hard to tell by looking at it from outside through the windows. It should at least be the case that all rooms are connected together in any given floor.

There is the occasional misplaced wall that I can't figure out how to fix. Sometimes walls end in the middle of a window. It's difficult to prevent this at this early stage because window positions haven't been generated yet. I think it should be possible to calculate window locations at this point int he generation though, and I'm working on solving it. Sometimes doorways are cut too close to T-junctions so that a wall ends in the middle of the doorway. This isn't easy to fix because the individual cubes don't yet have a way to access the walls placed by their neighbors. I think I need to add cubes at wall end point and check for them when placing later walls. This is still a work in progress, but it's a good start. Now I need to place some furniture into the rooms!

Here are some buildings with interiors added. I didn't add too many walls yet. I think I need to find some better wall placement algorithm that divides interior space in a more interesting way. There also isn't any direct lighting for interiors as they're generally always in shadow. At this point I only have ambient lighting, though at some point I may add some sort of room lights. I'm not sure how to add the thousands of lights that I need for nearby buildings.

Buildings with some (sparse) interior walls dividing internal space into rooms.

More buildings with interior walls, ceilings, and floors.

After writing the text of this post I went back and attempted to generate a more regular building floorplan for rectangular office buildings consisting of a central hallway along the longer dimension with rows of rooms on each side connected by single doorways. I think it will be easier to place furniture and other items in rooms like this because the dimensions are regular and known. I suppose this is more realistic as well, though a bit too simple for a large building.

Rectangular office building with rows of rooms on each side of a central hallway.

Drawing Performance

Let me go off on a tangent about draw times. You can skip this if you're only interested in the procedural generation part. The original idea was to generate and draw interiors for only the visible nearby buildings. It turned out that generation time was only about 200ms, and draw time wasn't much affected by visibility culling, so I ended up generating and drawing them all. Once I add more interior geometry I'll likely have to go back and change the way this works.

One more side note. I find it interesting that performing view frustum (visibility) culling on the CPU on buildings doesn't help much. The GPU is very fast at drawing all that geometry. It helps somewhat when the buildings are mostly off-screen, but it actually hurts when the player is outside the city looking into it because the culling doesn't reduce the number of shapes that need to be drawn. There's some CPU runtime overhead for doing the culling that isn't helping to reduce draw time. This is actually the worst case, so if we want to optimize for worst case framerate it's better to disable view frustum culling.

With this rendering system I get around 140 FPS (frames per second) without interiors and 125 FPS with them in the default view (where the player spawns). This view is at the edge of the city looking away from it. You might think that this would be an easy case, but the framerate doesn't drop if I turn around to look at the city center. There are two reasons. First, I'm sending all geometry to GPU vertex pipeline each frame. The GPU does a good job of culling but it's generally pretty fast about handling buildings. Second, buildings aren't the slow part, grass is. If I disable grass the framerate increases to 260 FPS. Grass isn't drawn where buildings are placed. This means that if I'm looking at buildings, then I'm not looking at dense grass. If I'm looking from the city outward where there are few buildings, then what I see is a huge field of grass. The framerate is actually a bit lower in that case.


Other Changes and Future Work

I made a few additional changes to improve buildings in the process of adding interiors:

• Added a cross-shaped building type/template.
• Removed windows that were partially occluded by sloped house roofs.
• Removed partial windows that were clipped by the other sides of a building.
• Buildings are now an exact number of floors and no longer have floors of different spacing in different parts.
• Building exteriors no longer have intersecting geometry that causes problems with z-fighting.
• Fixed incorrect house brick texture alignment on roof triangles.

There are also a few unfixed problems, and some new problems that need to be dealt with later:

• Windows are still drawn behind small structures such as porch roofs that partially block them.
• Interior walls can end at windows so that the wall edge is seen through the window. [I think I know how to fix this one.]
• Interior walls can end in the middle of doorways in the random maze floorplans.
• Some rooms are odd sizes/aspect ratios or simply too large.
• Players can't see completely through buildings (back facing windows aren't cut out of exterior walls, making them opaque).
• Building interior lighting is flat and uninteresting.
• No furniture or other interior details!