Friday, November 29, 2019

Procedural City: Building Roofs

This is a shorter post that was originally split off the longer "procedural city update" post I was working on. Let's get back to the house roofs. I want to work on building interiors, but the roofs aren't quite right and don't have enough variety. They're intended to be simple to generate and fast to draw. Most small house types had simple sloped roof sections on each part of the building. Since 3DWorld can currently only generate rectangular, L-shaped, and T-shaped houses, there are either one or two rectangular parts to the house.The roof needs to look correct and interesting for all of these cases.

Here is a list with descriptions of some of the common house roof types. Flat roofs aren't too interesting, so I won't discuss them here. I'll leave them for larger buildings. I was originally adding only gabled roofs to small 1-2 part houses. I recently added hipped and half-hipped roofs into the mix (randomly selected). It was easy to add these roof types to simple rectangular houses, but adding them to multi-part houses proved to be more difficult than I expected. The two different parts of the houses can be different widths and different heights, which makes the math for lining up the roof triangles and quads complex. It took many iterations to get a hipped roof to line up with another roof section that had a different width and peak height. There are quite a few special cases where sections of roof need to be clipped or extended so that they join properly with no holes or triangles that stick out. In addition, I need to make sure the roof from one part doesn't intersect the living area of the other part. This wasn't a problem until I started adding building interiors, in which case it's obvious if the roof extends into, say, a bedroom.

Here are some examples of two part houses and what their roofs look like. There are maybe a dozen different pairs of roof types/intersections. Most of them look correct, but a few of them still look odd. For example, some parts have a roof on each side that end at a horizontal line that would need a gutter between the sections as in the first screenshot. I'm not sure if I'll go back and fix them or not.

Low house with relatively flat hipped and gabled roof sections.

L-shaped house with hipped and half hipped roof. The roof line consists of complex geometry and angles that were difficult to get right.

House with two gabled roof sections intersecting at a T-junction.

Large house with low hipped roof on taller section and gabled roof on shorter section.

L-Shaped house with gabled roof intersecting at a T-junction and a smaller, lower porch roof in the back.

There are plenty of other house roof styles out there. I'm considering adding more of them, but it will probably have to wait until I've made more progress with building interiors.

I might have to go back and improve the variety of office building roof types later as well. Right now there are only two types: flat and beveled edges. This image shows two buildings with flat tops and beveled edges.

Office buildings with roofs that have flat tops and beveled edges.

On a somewhat related note, I added glowing colored lights to those antennas on the tops of tall buildings that appear at night. I think these are supposed to keep planes and helicopters from crashing into them. I wonder if that means I need to add helicopters in the sky above the cities as well?

Night time city showing colored lights on the tall building antennas.

Friday, November 15, 2019

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.


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!