Procedural Buildings: Floorplans, Indirect Lighting, and People

I have a long todo list for procedural city buildings, and I managed to work my way through a number of items in the past few weeks. I improved building exterior structures and interior floorplans. I worked on room light culling, optimizations, and indirect lighting. I added more types and larger numbers of stairs and elevators. I even placed people into some buildings. This is going to be a screenshot heavy post!


Office Building Floorplans

My original building floorplans consisted of rooms recursively subdivided by random walls and offices with a single large hallway with rooms on both sides. I read some online articles on interior building floorplan generation, which gave me some new ideas. First of all, my buildings don't have any courtyards. That's not too difficult to fix. I can create some doughnut shaped buildings with holes for courtyards in the middle, and a door leading out to the courtyard. Like this:

Building with an interior courtyard. And green chairs!

If you look closely you'll see that the chair seats are green. That's another detail I added. Chairs now use a color randomly selected from a list. Each section/wing of a building will have chairs of a consistent color. It adds a bit of variety to the otherwise grayscale interiors.

The next item to work on is increasing the complexity of office building hallways. This probably took as long as everything else in this post combined. It's incredibly difficult to generate a network of hallways and rooms within a given rectangular area that meets all of my various requirements:

• The entire floorplan is connected and walkable by the player
• Each floor is connected to the floor above and below (if present) by one or more set of stairs
• Each large area floor is connected to the floor above and below by one or more elevator
• Each office/room is connected to at least one adjacent office/room or hallway by a door
• All hallways are connected to each other in a graph
• All hallways and rooms are some minimum size (around 2x the player diameter)
• No walls intersect windows (this was a tough one)
• As many rooms/offices as possible have a window (all the ones on the exterior of the building)
• No walls, lights, stairs, elevators, tables, chairs, etc. can intersect any other objects
• There must be enough unobstructed clearance at doors, stairs, and elevator entrances for the player to enter and exit. For example, doors can't open into each other.

It took me many hours to get this all right. Each of the different steps for placing walls, room objects, stairs, elevators, etc. needs to know about the previously placed objects to satisfy the last two constraints. I had to reorder the placement steps quite a few times. In some cases I had to make a number of iterations to place an object with varying position and size. If placement failed, I either reduced the object size, ripped up and moved something that was previously placed, or selected a different type of object to place.

Placing stairs was the most complex because of they way they span multiple floors that may have different floorplans, the clearance requirements around the two ends of the stairs, and the requirement that the player be able to walk from the stairs to the hallway. Keeping walls from intersecting windows probably took the most actual time because of the number of locations I had to deal with this in the code. For example, if there's a large room I want to split in half with a wall, the halfway point may put the wall ending in the middle of a window. I can move the wall to one side of the window, but that may make the smaller room have too little space for a door/table or for the player to walk around some placed stairs.

I ended up with over a thousand lines of code for this part and had to split it into its own source file. It's probably even more complex and time consuming than the city car/traffic logic I worked on last year. But it does seem to finally work. I'm not saying 100% of buildings satisfy these constraints, but all of the buildings around the player starting area seem too. I've looked at a few dozen (out of 14,000 buildings). I iterated over and over with this until I couldn't find a building that looked bad. Actually I did add internal consistency checks for things such as required stairs placement, which is one of the most important constraints for building connectivity.

Anyway, there are now two new types of large office building floorplans. One of these is randomly selected when a building floor is above a minimum size in each dimension. First I added floorplans with a primary hallway and multiple secondary hallways off to each side, with rooms coming off of them. Usually there are 3 hallways on each side but I've seen 2-4 of them, maybe as many as 5. The placer tries to insert stairs and elevators in the primary hallway but will place them in the rooms if it needs to  (secondary halls are usually too narrow for stairs). The rooms at the far end of the halls and ends of the building have 1-2 windows and the rooms at the corners have more. Some hallways also have a window at their ends. Here's an example:

Office building with secondary hallways branching off the main hallway with rooms on both sides.

Another type of floorplan is the loop hallway with a primary hallway and two secondary hallways on each side that loop around and connect to it. The final hall network is a rectangular circle with a line connected through it. This produces an inner row of windowless offices on each side of the main hall that have doors connecting to the primary hallway, secondary hallway, or both. Then there are rings of exterior rooms with 1-2 windows each along the side and both ends. There are smaller rooms at the ends of each hallway and corner rooms that they connect to. Here is a screenshot from the inside corner of a secondary hallway.

Office building with multiple looping/grid hallways with rooms along them in various sizes/orientations.

I might add more types, but it's a lot of work to add each one. There are various random parameters that control the layout of rooms and actual spacing values given the rough selected floorplan.

To give you an idea of the size of these buildings, the building this screenshot was taken from has 52 rooms in each floor, 24 floors, 1248 total rooms, and 1742 room lights (hallways have 2-3 lights). There are 14,000 buildings, which is a lot of geometry! The floorplan and room layout are done for all buildings up front, and it takes less than a second using 4 CPU cores. Only visible building interior walls/ceilings/floors are drawn. Room detail geometry such as tables, chairs, and lights are generated dynamically and drawn for nearby buildings as the player moves around. It's multi-threaded and surprisingly fast.


Stairs

I mentioned the complexity of placing stairs in the floorplan section above. A row of straight stairs is sometimes difficult to place because it's longer than the length of most non-hallway rooms. That means they can't be placed in normal offices, only larger rooms and hallways. I did add a pass that tries to place incrementally smaller stairs until it finds one that fits. It gives up when the stairs become too small for the player to use.

I also added U-shaped stairs that wrap back on themselves. This square size is sometimes easier to place. I had to enclose the sides with thin walls so that the player doesn't fall off. It just didn't look right without the extra walls. These stairs are common in wide office building hallways. Here's a screenshot:

U-shaped enclosed stairs connecting hallways across multiple floors.

Special single flight stairs are used to connect vertically stacked building sections that have different floorplans. Each rectangular block that shares a common floorplan has one or more stairwells cut vertically through all of the floors. These extra stairs are needed to connect together adjacent floors that don't have their stairwells aligned. They look like this:

Stairs connecting hallways of two floors that have different room floorplans.

Sometimes the hallways of the floors above and below misalign such that stairs can't be placed in them. For example, the halls may be offset so that the wall on one floor runs down the center of the hall on the other floor. In this situation, the placer will attempt to insert narrower/steeper stairs that connect an office above with an office below. Like this:

Stairs leading from an upper story penthouse room down to a hidden office in the floor below.

Elevators are also extended to floorplans above and below if there's space for them, they don't block anything critical, and the open end of the elevator has enough clearance. It's acceptable (and even preferred) to place the back or side of the elevator against a wall.

Note that placement of stairs and elevators requires cutting holes in ceilings and floors. This is done with CSG operations on the cube geometry, similar to how doorways are cut into walls. The system even keeps track of which cube faces are visible to optimize drawing. Placed room lights may also be moved to the side or removed when cutting holes in the ceiling.


Indirect Interior Lighting

Building interiors are mostly a dull, flat gray color. The problem is that I included direct lighting but no indirect (bounce) lighting to add color variation. I've had indirect lighting on my TODO list for a while but haven't figured out how to do it efficiently. My first real attempt was to use the same system of precomputed volumetric lighting I had used for static scenes in the past. Here is a link for a blog post from long ago. This system involves path tracing and 3D voxel lighting textures. The three biggest problems are that it's slow, has relatively low resolution that produces color bleeding, and only works for one building at a time. But how bad is it? There was only one way to find out. My first attempt gave me results like this:

Indirect interior lighting gone wild. This actually looks pretty cool, like reflective aluminum foil walls.

This actually looks really cool. The normal maps on the walls make them look like crinkled reflective metal. The problem here is that the constants are optimized for full scene buildings, not for a tiny building inside a huge scene. The offset in the direction of the normal applied to the lighting lookup values was an order of magnitude too large. It took a while to figure this out, but I eventually was able to get it to work (better):

Corrected indirect room lighting, fast but low quality (100K rays per light, 1.3s)

There's a lot of noise in the lighting. Some of the darker walls are hit by a sparse scattering of bright rays of light. There just aren't enough light rays to get a noise free result. If I increase the number of rays by 20x and let it run for 26s (for this one building), the results look much better:

Higher quality but slower room lighting (2M rays per light, 26s.)

That's for a small-ish house. If I try computing 2M rays per light on that office building with 1742 lights (of which only around 1000 are on), then it takes ... I'm not sure, I gave up waiting for it. It took 24s to do 100K lights so I think that means it would have taken about 8 minutes for 2M. That's way too long for a realtime graphics application.

So, how can I improve this? It would make a huge difference to limit the ray casting to the lights on the current floor. Those are the lights that are likely to make a visual difference. That reduces computation time on the large building down to around 20s, similar to that of the house. However, 20s is still too much time to wait when entering a new building or moving to a new floor.

I think the solution is to let the lighting computation run in a background thread and incrementally update the lighting data sent to the GPU. That way the indirect lighting noise will be reduced gradually over time if the player remains in the same building. I actually do have a system to do this already, and I've used it to allow dynamic sun and moon changes in the Sponza Atrium scene. What I don't have is a priority system that traces lights near the player first, before moving on to less important lights. I'm not sure how difficult that is to implement. It will take more than 20s to converge when running in a background thread and sharing resources with normal rendering. I'll have to try it out later. I guess you'll hear how that went in next month's post.

There's another problem with indirect lighting. I'm using a uniform 3D grid (currently 128x128x64 in {x,y,z}) to store lighting data. If the building is tall, there isn't enough vertical resolution to accurately store lighting. This results in light leaking through the walls, ceilings, and floors. It also leaks through walls, but ceilings and floors seem to be the worst. Here is what light leaking looks like in a large house:

Indirect room lighting showing light leaking through the floor from the room below.

The reason this isn't much of a problem in my other static scenes is that I don't have 20 story buildings, and I made the walls and floors thicker. If they're at least one voxel (1/128 the scene size for walls and 1/64 the scene size for floors) then the light leak will be prevented. Unfortunately, I don't have as much control over the building dimensions in this situation with procedural generation. So far I don't have any good solutions to this problem. I'll keep thinking about it.


People in Buildings

One final major TODO item I checked off was adding people to buildings. It turned out to not be very difficult. For now, they just stand there rather than walking around as they do in cities. I was able to reuse the pedestrian manager code, model loading and drawing, lighting, shadows, etc. The only real difference is that these people are in a separate vector that has no physics/AI update step. At least player collision detection still works.

One minor difficulty was placing people so that they don't collide with room objects such as chairs and tables. The difficulty is that people are placed at building generation time, while room geometry isn't placed until the player gets close to a building. What I had to do to make this work was add people in as virtual blockers for room geometry. Instead of placing people so they don't intersect tables and chairs, I placed the tables and chairs so that they don't intersect previously placed people.

It turns out that occlusion culling works well in this situation, so I can place 50,000 people across my 14,000 buildings with little runtime performance impact. It's fun to play hide-and-seek with a few people in a huge office building! This guy isn't doing a very good job of hiding though, he's right by the window and the front door.

Some tall guy standing in a room of this house near the front door.

These people are sharing the room. They cast nice soft shadows. Note that I've made sure that the lights are on in any room that has a person in it.

Two people in a room casting shadows on the floor and wall.

I might go back and add dynamic movement to people in buildings. This requires writing some sort of indoor navigation system. I think that would be a fun and interesting project, though it could be very time consuming. I can't wait to see how many places they'll get stuck. Another item for the long-term TODO list.


Bonus Screenshots

I experimented with varying building generation parameters in the config file, including setting them to crazy values. This screenshot shows what happens when the building size parameters are set to a huge range. Some buildings are as tall as 180 stories, and some are only one room wide. The building to the right of center with the girl in it is over 100 stories tall and has a single room with a stairwell for most of its height. The part on the top is narrower and doesn't even have room for stairs. All of this runs just fine at almost 100 frames per second.

A scene generated with crazy building size parameters that produce thin buildings that are hundreds of stories tall.

I added short walls around the roof of some building types. I should probably make them use a different texture from the roof texture. I also plan to add more specific objects to rooftops that look more like AC units than these random cubes. I'll need to go looking at reference images of large building roofs.

Office building with a wall around the edge of the roof and a city in the background.

I think this post is long enough. I'll continue with more building updates next time. Maybe by then I'll have indirect lighting working better, and possibly also dynamic/moving people in buildings.