Sunday, May 24, 2020

Procedural City: Adding Content to Building Interiors

Work continues on building interiors for 3DWorld's procedural cities. I had previously added stairs, elevators, lights, tables, chairs, rugs, pictures, and whiteboards. This time I've added trashcans, bookcases, desks, and beds. I'll briefly describe how I place and draw these room objects below, with plenty of images to show what they look like inside buildings.


Trashcans and recycling bins are common in both residential and commercial buildings. They're also simple and easy to draw - at least that's what I originally thought. They required implementing some new features, for example curved surfaces. (Yes, round room lights are also curved cylinders, but they're emissive so I didn't really have to get the normals right for lighting.)

Another difficulty is that I needed to implement two sided lighting so that their interior and exterior surfaces were lit correctly since they have no thickness. I could add a thin rim around the edge to connect the sides and give it some volume, but I don't currently have the code to draw that geometry. It would also take even more triangles. I initially enabled two sided lighting, but it was too much work for the fragment shader and reduced framerate. So I changed the code to add each triangle/quad twice with different normal sign and winding direction. Back face culling was enabled to ensure only the face oriented toward the camera was drawn.

Trashcans are placed in the majority of rooms. They are randomly selected from three different sizes, three different aspect ratios, and several colors (including blue for recycling bins). In addition, some building floors use trashcans with flat sides and others use rounded sides/cylinders. They are always placed near a wall or corner of the room away from doorways and other placed objects. Trashcans have collision detection enabled and cast shadows. Here are two example screenshots.

Flat sided trashcan in the corner of a room of a house.

Small cylindrical recycling bin by the wall in an office.

Adding trashcans to most rooms requires a great deal of total geometry across the set of nearby visible buildings. Some large office buildings have more than a thousand trashcan placements. This was having some effect on framerate, so I had to optimize the drawing code by removing hidden faces, using indexed triangle rendering, disabling shadows when distant, etc. To make it easier to test my optimizations, I temporarily placed up to 20 trashcans in each room. Now a single office building could have more than 10K of them! Here's a wireframe view showing all the trashcans in an office building.

Wireframe model showing a large office building with an excessive number of trashcans and recycling bins.

Most of the cost was in the shadow pass, where a shadow map was created for each of the up to 40 shadow casting lights every frame. Each shadow map had to draw every trashcan in the building because there's no per-building subdivision/acceleration structure for them. I thought about adding one, but I ended up caching shadow maps between frames when they weren't changing (no dynamic shadows from the player or people in the building). This helped a lot. With shadow map caching, my other trashcan drawing optimizations were probably not needed. I'm sure they'll help with non-shadow rendering though.


Next I added bookcases to houses/residential buildings. These can be placed in any room where there's space, as long as they don't block doorways, stairs, or elevators and don't intersect other room objects. I had to update the code that hangs pictures on the walls to avoid placing a picture behind a bookcase. They're relatively narrow and the placer is successful most of the time.

Each one has between three and five shelves, with randomly placed books on most shelves. Books are simple cubes with a variety of colors, sizes, and thicknesses. There are some gaps and the possibility of a fallen over book in the larger gaps. I like the way bookcases and books look, even though the books are simple and untextured. Here are some representative images.

Procedurally generated bookcase with a random selection of colorful books on the shelves. One book on the bottom shelf has fallen over.

Procedural bookcase with random books in a room with a table and rug on the floor.

In the future I might add books placed at angles, leaning on other books, which requires a bit more math. I could add more geometry to show the pages vs. the covers. I did this for books placed on desks below. I might even add pictures and/or words to the covers.


Desks were next on my list of furniture to add. They're similar to tables, but with a higher aspect ratio and only one chair. These are placed more often in building offices, and in smaller rooms of residential buildings where there's no space for a table. Some offices have two desks, but the rest of the rooms have at most one. They're pushed against a wall in a location that doesn't block any doorways, stairs, or elevators. I reused most of the code from tables to save work.

Here's are screenshots of a residential building desk and an office with two desks.

Home office with desk, chair, bookcase, recycling bin, picture on the wall, and rug on the floor.

Large windowless office with two desks with chairs, large whiteboard, and trashcan in the corner.

I placed a randomly sized and colored book on some of the desks, right in front of the chair. These books actually have separate cover vs. pages geometry. Maybe at some point I'll use these models in bookshelves. I might also put titles and pictures on the covers.

Desk with a red book placed in front of the chair, waiting to be read.

Some desks that are against interior walls (no windows) have taller backs. These may become bookshelves, mirrors, whiteboards, or cork boards in the future. I'll have to think about what I want to hang from their back walls. For now they're extra wooden spaces.

A tall office desk that can be used as a bookcase, mirror, whiteboard, cork board, etc. in the future.


The logic for selecting bed placement was actually pretty complex. Beds are placed only in bedrooms, compared to other room objects such as chairs, desks, bookcases, trashcans, rugs, and pictures, which can be placed in most room types. There are more rules governing assignments of bedrooms than most other rooms and placed objects. For example:
  • Bedrooms are in houses/residential buildings only, not offices
  • No beds in building parts assigned to garages and sheds 
  • No beds in rooms flagged as offices or hallways
  • No beds in rooms with stairs or an elevator
  • Bedrooms should not have an exterior building door (front door) when on the ground floor
  • Rooms can have either a bed or a table, not both (bookcases are okay to mix in)
  • No beds in rooms that are too small to fit them, or too large to be bedrooms
We also have the usual placement constraints and some placement constraints specific to beds:
  • Beds can't block doorways (same as other furniture)
  • Must be space to at least one side of the bed where a player/AI can walk
  • Must be space to navigate around the bed from one doorway to a doorway on the other side of the room
  • Headboard should be against a wall if possible (soft requirement), but need to leave a bit of extra space if along an exterior wall with a window.
I attempted to implement all of those checks and special cases, which required adding a bit more query functionality for buildings. Since beds are only used in houses, which have a smaller number of floors, this doesn't affect runtime or framerate as much as something like a desk which can have a thousand placements in a single large office building. Bed geometry is simple though, at least compared to bookcases full of books.

Beds have a frame with legs, headboard, foot board, mattress, and pillows. Most of the bed is made of a wood material. The sheets and pillows have fabric textures and some randomly chosen colors applied to them. Large beds have two pillows, while narrower beds have a single pillow. For now, all the parts of the bed are drawn with cubes. Here are some examples of beds with various sheet textures.

Bed with two pillows and plain white sheets placed along a wall in the bedroom.

Another bed with patterned/textured sheets and a single pillow next to a bookcase.

A bed with fancy red sheet texture against a wall with windows.

Those are all the features I've added since the last post. I won't get into the various other optimizations and bug fixes this time. There are many more room items to add. I can think of dressers, couches, TVs, lamps, and kitchen items. Offices need cubicles and computers. Maybe indoor potted plants as well? I'm sure it will be tricky designating a room of the house as the kitchen.

Saturday, April 25, 2020

Procedural City: Room Decorations

It's time to add more decorations to the rooms in my procedural buildings. The walls and floors look too plain, so that's a good place to start. First up is office buildings. I added hardwood floor textures to houses, but office buildings are still using simple gray floors. I downloaded five office carpet textures and added them to the pool of randomly selected floor textures for non-house buildings. Here is an example.

One of the new office building carpet textures. This one even has a normal map!

Next up are houses. The hardwood floor textures look good, but I need to add some variety. How about fancy rugs covering some of the floors? I found five rug textures online, and added support for selecting random rugs and placing them in some rooms. Rooms that are otherwise empty (no table or chairs) have a higher chance of getting a rug so that they're not totally empty. These rugs are randomly sized and positioned randomly somewhere near the center of the room.

A house with rugs on the floors of some rooms.

That's good for floors, so it's time to work on the walls. The most obvious decorations to add to walls are framed pictures, and what better pictures to use than my library of 3DWorld screenshots. I added ten full resolution 1920x1024 screenshots of various scenes including nature, reflections, a procedural universe, and buildings. I even threw in one of my skybox images, which wasn't created by me. (Note that these images are large and haven't been added to the 3DWorld GitHub project.) Here is a room with a nebula picture on one wall and a reflective Sponza Atrium picture on the the other wall.

A house with pictures on the walls and rugs on the floors.

But wait! Why limit pictures to existing images? Why not allow the player to create their own photos for hanging up on the walls? Sure, let's do that, just for fun. I added a hotkey to take a screenshot and add it to the building photo library, which replaces the initial screenshot images. Now the user can populate rooms with their own selected artwork.

A picture showing a screenshot of buildings taken a few seconds earlier, complete with "yellow status text of authenticity". Hey, dude, get out of the photo!

In fact, you can take screenshots of these pictures and create new pictures. The nesting of screenshots is unlimited.

A picture showing a screenshot of a picture of a screenshot. I had to shine the flashlight on it because it was somewhat dark due to the downward direction of the room light.

Here's another example.

A screenshot I took of the nearby city placed as a picture on the wall.

That's good for houses, but office buildings don't have many pictures on their interior walls. What they do have are offices, and many offices have whiteboards. I can conveniently reuse the picture system with a blank white texture and an added ledge to form a whiteboard.

An office with a whiteboard on the wall and a new carpet texture.

That's good enough for now. This was actually a pretty easy task, at least compared to some of the other work I've done on buildings such as navigation for people. At this point it's unclear what I should add next. I suppose more room furniture and smaller details is always useful.

Monday, April 6, 2020

Procedural City: AI Navigation for People in Building Interiors

I've continued to work on procedural city building interiors over the past few weeks. Let me start with something simple, then get into AI navigation later. I added more ceiling and floor textures, for example hardwood floors for houses. This improves the look of all my future indoor house screenshots. These changes also make it more pleasing to debug the wayward AI by watching people walk around for several minutes at a time. At some point I'll go back and add better textures to office buildings as well. Here are some examples:

House with normal mapped light hardwood floor, and ceiling tiles.

House with dark hardwood floor, and a plaster/stucco ceiling texture.

Next, I added animated people who use AI path finding to navigate between rooms of a building. As expected, this was quite time consuming and difficult to get right. It was more difficult than path finding for city pedestrians to avoid buildings and other objects, but it was probably easier than pedestrian street crossing and car avoidance logic. I haven't finished the logic for people to ascend/descend stairs, so for now they stay on a single floor of their building.

People don't exit buildings either. At least, they're not supposed to. When I first implemented moving people it didn't work as expected. (It rarely does.) What I had were people who walked straight out of their buildings, through the sky, to the center of the map. Like this:

Failed attempt at people path finding AI. The all walk out of the buildings and into the sky in the center of the map.

Yes, the 3D models still have their arms out. I haven't fixed that yet.

I eventually got the basic movement working after many hours of work. People slide across the floor and sometimes walked through walls but at least stayed in their buildings. That's progress, but the whole "slid across the floor" situation could be improved. Yes, I have to make my 3D person model animations work in this context. Here I'm using a different shader that supports indoor room lighting, rather than the city shader I was using for pedestrians. The same shader is used for building interiors and people so that I can draw both groups per-building without switching shaders. It already has animation support that I can enable because it shares a base class with the city pedestrian shader. Surely it will work if I just enable animations, right? Let's see...

Accidentally animating buildings using the animation system meant for models of people.

Yeah, I was afraid of that. The building interiors are "animated" as well; meaning, they rotate in some odd way around some random point of the building that the animation system detects as the "legs". That screenshot doesn't really do it justice. In reality, the buildings are all spinning around madly so that you can't even tell what's going on. It's just a mess of polygons flying around that you can only make sense of with a static screenshot. In fact, you can't even see the people through all of the building walls. Well, it makes for an interesting image anyway.

One hack that fixes it is to always set the animation time to zero before drawing buildings. That works well enough for now. Onto the problem of people walking through walls and furniture.

Wait, there's one more thing I need to go back and fix. I quickly realized that halfway open doors would be a problem. I never bothered to include them in collision detection with the player/user because they generally got in the way and prevented the player from walking around in some rooms. There were too many rooms where the combination of a table + chairs in the center plus doors on each side made the room impassible to the player. The AI collision detection ignored doors as well, for similar reasons.

How does this work in the real world? Most of the time, people will open doors as far as they can be opened to get them out of the way. That's either opened 90 degrees until they hit a perpendicular wall, or almost all the way to 180 degrees until they hit the wall containing the doorway. I can do the same here. The room generation and door placement algorithm can determine how far the door can be opened, and open it just short of that value. 15 degrees seemed to work well; large enough to get them out of the way, but small enough that they (or rather their non-existent doorknobs) don't intersect the wall. Now doors are usually open like this:

A man walking into a room through the doorway. The door has room to fully open, so it stays out of the way. Compare this to the 90 degree open doors in the two screenshots at the top of this post.

That's much better. People hardly ever walk through doors now! But they walk through furniture and stairs all the time, and occasionally still walk through walls. And each other. I need to implement path finding through the room graph with collision avoidance for furniture. The first step is to construct a graph of the room connectivity through doorways and stairs. An added bonus is that I can now use this graph to perform connectivity analysis and find all of the buildings where the rooms aren't 100% connected to each other. I can print out their locations for debugging and go find them in the scene.

Okay, that was a lot of work. I thought the floor planning algorithm was pretty good, but apparently there were several bugs that were rare enough that I missed them in my manual building inspection. (I can't quite manually inspect 14K buildings.) Some house cubes/rooms were too small for doors. Some building parts came together at odd positions where walls blocked doorways. Some of them were missing vertical connector stairs that joined stacked floorplans. I was able to fix all but this last category. I have it down to 28 failed placements out of about 14,000 buildings. That's what, 0.2% failed floorplans? Good enough for now. I know where they are if I want to go back and fix them later. These people are asking me to make them stop running into things, I can't make them wait forever.

Right. Finally, after all these changes, I'm ready to start on AI navigation and path finding. I expected this to be interesting, and it was. I copied my A* (A-star) path finding algorithm from the game mode smiley AI waypoint navigation code and made it work with the building room graph. After many many iterations I had a system where my 50,000 people could walk from their current position to the center of a different room in the same building through doorways without walking into walls. It's fast too, only around 3ms for 50K people! If you're interested, the code can be found here in my 3DWorld GitHub project.

Two people of different sizes walking through a room to an adjacent room.

The first part of the algorithm finds the high-level path from the starting room to the destination room by traversing the graph through rooms and doorways. A valid destination point is chosen randomly within the destination room so that it doesn't intersect any placed objects. Once the destination is reached, the AI waits there for a few seconds and then selects a new room to walk to. That part didn't take too long to get right, but it took a long time to smooth the path and push it away from walls and door frames so that people didn't partially intersect them. I had to use a collision radius for each person and shrink room boundaries by that value. This must be done for individuals because some of them have different sizes/radius values.

The next step is planning a valid path from one doorway to another across a room. I started trying to write an A* algorithm for this, but eventually I gave up on that approach. It didn't work and was too difficult to debug. The solution I went with involved picking one or two random points within the room that didn't intersect any geometry. Then the path finder tried to connect the two doorway endpoints with one or both of these points to form a valid path that didn't intersect any of the objects. The shortest valid path was used as the final solution. If there was no path, the path finding failed and the person stood there for one second. After that time was up, the path finding algorithm started again with a new random destination and path.

Since failures seemed to be rare, this kept everyone moving. I couldn't find anyone who seemed like they had somewhere they could go but weren't moving. The only people who couldn't move were those placed in single room houses or in a corner of a room blocked by a table with chairs. My fixes for these cases were to not place people in garages and sheds, and to allow them to walk through geometry on the first segment of their first path. In theory, it shouldn't be possible for them to get stuck again. If they got into that spot, they should be able to get back out (unless pushed by another person).

That handles collisions with static objects. The next task was preventing people from walking through each other like they're ghosts. This was a bit more difficult. People are dynamic, so they can't be included in the path planning system, which determines the entire path ahead of time for each new destination. What I did here was to check for collisions with every person in the same building with a higher ID than the current person. These other people have "priority." The new position of a person is determined by adding their velocity times the elapsed time to their current direction vector, which is a smoothed version of the direction to the next path point. If the new position collides with another person, then no movement is made. If the existing position also collides, then the target person is moved along the collision vector away from the collider. This applies to people who are standing still waiting to choose a new destination as well.

That somewhat works, but it introduces a new problem. People can now push each other into furniture, through walls, and even outside of buildings. I fixed this by clamping their locations to the valid walkable areas of each room. This results in some model intersections, but it's better than intersections with room and wall geometry. I had the room path finding algorithm ignore a person's starting position if it was inside room geometry to allow them to escape once pushed inside tables and chairs. This situation is relatively rare, so it's unclear if my solution always works.

I could go on and on about this system, but I think that's enough details for now. I'll try to add some videos later. There are still some finishing touches I need to add first.

Here is one final image showing the wireframe of a building with people walking around inside of it.

Wireframe view of buildings with people walking inside them.

There is a lot more work to do. I would like to have people ascend and descend stairs to reach different floors of a building. I did some experiments with stairs where people are teleported up or down one level. It works, and the path finding can handle it, but it doesn't look good. I need to figure out how to make them walk up and down the stairs. The hard part here is that they need to start at different ends of the stairs depending on whether they're going up or down, and that's not something I can easily add to the room graph. Maybe I need two different graphs, or two sets of edges corresponding to "up" and "down"? I'll continue to improve it later.

There's one more fun thing I should mention. At one point I occasionally saw people who stood there spinning in circles forever. It took me a long time to figure out why they had this odd behavior. After adding lots of debug code and printouts, I realized they were trying to stand on a very exact spot on the ground. Each time they took a step they overshot their target, then turned and tried to step in a different direction. Their minimum turning radius made sure they could never quite get to the correct spot. If they ended up a very specific distance from the target it caused them to spin in circles. The fix for this was to add a term that decreased their step length when their target position wasn't directly in front of them. This reduced their speed while turning and made their steering more accurate at the ends of their paths.

Sunday, March 29, 2020

Gas Giant Image

Here a screenshot of a gas giant created by 3DWorld in universe mode. This uses a procedurally generated 1D color texture using mostly two colors with shades in between. Then procedural noise is used to offset the texture coordinates and break up the uniform color bands. Finally, 50 storm cyclones are added procedurally by the shader. The planet is drawn in realtime (~200 FPS) without using any 2D textures and allows the player to get very close, which is something you can't easily do with a pre-generated texture approach.

Procedural gas giant generated instantly and drawn in realtime by 3DWorld.

Sunday, March 15, 2020

Procedural Buildings: Getting the Details Right

This is going to be another one of those long posts showing a variety of procedural building updates with lots of screenshots. I've worked on many different procedural building improvements rather than any one large task. I did some experiments with dome and onion roofs. I added roof clutter including AC units, elevator caps, roof access doors, and rooftop walls. I placed trees in house yards and building courtyards and cars in garages. I added player shadows and working elevators. Finally, I improved building indirect lighting performance. I'll discuss each of these below and show some screenshots.

Dome and Onion Roofs

Someone suggested I add onion dome roofs. I didn't think they would look good on modern city buildings, but I decided to give it a try anyway. The goal was to initially generate the onion shape and then go back and work on the textures and colors later. I started with a simple hemispherical dome shape because that was easier. Once I had domes working, I modified the z-value (height) computation to produce the pointed onion shape at the top. My first attempt didn't go very well:

Onion domes gone wrong (divide by zero failure).

That's definitely an interesting look. The problem is that the vertex at the very top results in a near divide-by-zero, pushing that peak vertex up into the clouds towards infinity. Once I fixed that the results looked much more reasonable:

Onion domes on glass and steel office buildings?
That's a nice shape, but it doesn't look right on glass and steel office towers, even if they're cylindrical. It looks even worse on cube-shaped buildings. Onions seem out of place on houses and brick buildings as well. I think they would look fine on a rounded stone church, not that I have any of those in my cities. I'll add a config file option to control this roof type and leave it disabled for now so that buildings will continue to have conventional flat and sloped roofs by default.

Roof AC Units

Some of the cube shaped buildings with flat roofs had roof-colored/textured cubes placed on top of them to represent random objects that were on the roof. That looked fine back when buildings were simple, but it's time to upgrade those objects. What's normally placed on a building roof? What comes to mind is AC units. Lots of buildings have big metal boxes with fans in them placed on the roof, right? If I look out the window at my work I can see some AC units on the roofs of lower adjacent buildings.

I found two AC unit textures online and got to work. Each building can have up to 8 AC units on its roof with sizes that vary according to building dimensions. The units are distributed across the various roof quads/sections that may be at different heights. They're placed randomly, generally in the same orientation and not overlapping anything else (including each other). It took a lot of tweaking to get these right. They're fine for now. I might add additional types of roof objects later. Here is a screenshot.

AC units have been placed on the roofs of some of the flat roof rectangular buildings.

Roof Access Stairs

I want to allow the player to walk on building roofs and collide with the new AC units, so there has to be a way to get up there. I started with flat rectangular roofs because they're easier to work with. The simplest solution is to find a stairwell that reaches the top floor and extend it one extra level to the roof. The top of the stairs is covered with either a triangular hood (for single stairs) or a rectangular box (for U-shaped stairs). [The U-shaped roof stairs are rare and I couldn't find any around the starting area to take a screenshot of. There was one at one point in time that allowed me to get the code right, but I changed some random number generator value and now it's gone.] Then I added a door that opens out to the roof. The player can climb these stairs, walk on the roof, and climb back down. The door is animated and opens for the player just like the ground level building exterior doors. Here is an example image.

Roof access stairs shown from the outside, with some nearby AC units. They do cast shadows, but the shadows are behind the objects.

Here is what the roof access stairs look like from inside the building. The triangular hood isn't well lit and appears a uniform gray. Maybe I'll add a light to the ceiling later.

Roof access stairs shown from the inside. Maybe the table is out of place?

Here is a screenshot of the roof access door of a different building that's open, letting the player pass through from the roof into the building.

The roof access door opens for the player and allow them to enter.


Some houses and buildings have empty space in their rectangular lots. What can I fill that space with? How about procedural trees? I have trees in the dense city area and out in the hills around the city, so why not place them in the lots. They're a good fit for the corner of L-shaped houses and the courtyards of ring-shaped buildings. Here is an example of a tree in the yard next to a house.

A house with a procedural tree in the yard.

Roof Walls

I added raised walls around the edges of the roof of some rectangular buildings. I already had walls around single cube building roofs. These new walls go around the entire roof perimeter and can be more complex than one rectangular ring. They also use the exterior wall material (color and texture) rather than the roof material. Here is an example for a building with a courtyard. If you look closely you'll see that there's also a tree placed in the courtyard, but only the very top is visible. The raised bump on the left side of the roof is the top of an elevator.

Building with roof access door, walls along the edges of the roof, and a tree in the courtyard.

Garages + Cars

Garages and sheds need more work. First of all, they have no doors. I can fix that by adding house doors to sheds and garage doors with a different texture to garages. Now all that's needed is a driveway!

I decided to classify a detached building as a shed vs. garage based on whether or not it can fit an average sized car. Then I updated the drawing and collision detection code to make the doors open and allow the player to enter using the same logic as the main buildings. Here is an example of a house with detached garage.

A house with a detached garage that may contain a car. The garage door can be opened, and the player can now enter.

That's good, but garages and sheds are empty. They don't even have lights on the ceiling. [Now that I write this, I should probably go back and add a light in each one.] The most appropriate items to add to garages are cars. In fact, I already have the code to load and draw car models for cities. I just needed a way to add parked cars that are outside of city blocks. That wasn't too difficult. See the screenshots below.

A car parked in a garage, seen through the window.

A car parked in a garage with the garage door (sort of) open so that the player can see inside.

Okay, it could be better. The car would look better with lighting, and the way the garage door is cut out doesn't look right. I guess I have to model a frame-less door that opens upward and inward rather than swinging outward. I'll get to that later.

Update: I went back made some changes before publishing this post. I added lights to the ceilings of garages and sheds. I also reduced the border around the garage door. I still need the larger border at the bottom because the interior concrete floor slab is higher than the bottom of the exterior building wall and the ground, so I need to cover the edge of it. Here's an updated screenshot:

Garage with car, light on ceiling, and narrower garage door frame.

There, that definitely looks better. It's still not perfect though. The car casts a shadow but it doesn't receive light from the ceiling light above it. I haven't implemented that yet. Also, the windows on the sides of the garage aren't visible through the garage door. They only become visible when the player enters the garage. The car is a collision object so the player can't really get very far into the garage. Yes, someone needs to cut that grass in front of the garage door!

Player Shadows

I somehow had forgotten to add a shadow for the player until now. The player is the only dynamic object inside a building at this point, other than elevators. Fortunately, I was recreating room light shadows every frame anyway, and not taking advantage of the static nature of the geometry. This is mostly because I was reusing the shadow code from cities where light sources (car headlights) and objects were both dynamic. Right now the player doesn't have a real 3D model, so I used a simple sphere like in other gameplay modes. Here is what this shadow looks like in an office building hallway.

The player now casts a dynamic spherical shadow inside buildings, for all nearby lights.

Improved Elevators

My most recently completed task was adding functional elevators. I started with elevator shafts cut through building floors and ceilings with a light wood paneling texture on the inside and gray elevator doors that were sometimes open. This was shown in previous posts. Next I added elevator cars with dark paneling walls, tile floors, and patterned ceilings. (If you look carefully, the ceilings use the same texture as garage doors, for now.) Here is what this looks like, in a screenshot taken with bright precomputed indirect lighting.

Elevators now have proper walls, ceilings, and floors, and can be entered by players. (This screenshot also has indirect lighting included.)

The next step was to make the elevators move up and down. I decided to have them move when the player entered an elevator. I haven't added any buttons or other UI yet, so I decided to let the player control the elevator by moving to one side or the other. When the player stands to the left of center the elevator goes down, and when they stand to the right the elevator goes up. That works well enough for now.

The elevator floor and ceiling are collision objects that the player can stand on so that they move vertically with the elevator. I had to add a special dynamic vertex/material list that is regenerated each frame where an elevator in the current building has moved. I thought that could be difficult, but it happened to work the first time. Shadows should work properly for moving elevators as well. Here is a screenshot of the player in an elevator that is moving downward and is currently between two floors. I'll need to add some buttons to those inside walls later.

Player inside an elevator that is going down. You can see a bit of the floor above because the elevator is between floors. The elevators doors remain open so that the player can enter, exit, and see where they are.

I left the elevator doors open to allow the player to enter and exit at any time. If I add proper elevator controls, then I can have the doors open and close correctly. It's possible for the elevator to stop between floors if the player gets off at the wrong time. The player collision model is actually short enough that it can still fit through the opening of an elevator that is between floors. Maybe I should limit when the player can get off, or at least have the elevator continue until it reaches the next floor before stopping.

Indirect Lighting

There really isn't anything new to show here. I haven't solved the lighting noise or the problem with color bleeding through walls and floors. (Color bleeding can be reduced by using a finer 3D lighting volume grid, but that comes at increased frame time and memory usage.) However, I did partially address the performance problems. I made the indirect lighting computation run in a background thread so that the player can walk around while it's running instead of freezing the game until lighting has been fully computed for the current building. Lights are ray traced based on priority so that the larger lights and the ones closer to the player are added first. That way lighting will be calculated for the floor the player is on while it spends up to 100s computing lighting for other floors in the background. It was a lot of effort to implement, but seems to be working. I'll post some updated screenshots later if/when I improve the lighting quality. This post is already too long to add them here.

Next Steps

I've worked my way through most of my original TODO items. Well, the easy ones anyway. I've added a few minor items that I thought of while writing this post. There are still some improvements that I haven't figured out yet. I already discussed indirect lighting noise and light bleeding above. I would like to add movement of AI people in buildings next, which requires creating a building connectivity graph with path finding. It sounds like a lot of work but can surely be done.

Then there's the question of how to add interiors for city office buildings that use custom textures. These textures have windows included in them, which makes adding interiors significantly more difficult. The brick and block buildings I've been showing use base textures and have window holes cut into them procedurally. Textures that come with windows require the interior generation to work with the existing window positions, which it doesn't know about. Some textures have window spacing that varies on each floor, for example taller windows on the bottom floor(s) with more vertical space. Some of them have variable horizontal space between windows that may differ per floor. How exactly am I supposed to find the window locations? Using machine learning or image processing? Picking them out by hand by drawing window boxes in an image editor? Hard-coding all window spacing parameters for each texture by measuring them in pixels? I have no idea. Most of these solutions require too much work that isn't very interesting to me.

The final TODO item is to add more room objects. I currently have tables, chairs, lights, and stairs. I want to add desks, books, bookcases, trashcans, etc. There are two options for this: create the geometry procedurally in C++, or download existing 3D models. (I don't have the tools, skills, and patience to create the models myself.) Currently cars and people are downloaded 3D models, while everything else is generated with code. Neither of these solutions is great for a large variety of 3D room objects. I don't really have the patience to generate all of these different things, and 3D models take up too much space and require too much preparation work. It would be great if I could farm this off to someone else. For now I'll just leave it on the long-term list and probably add new items incrementally over time.

Tuesday, February 25, 2020

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.


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.