Monday, December 16, 2019

Procedural City: Stairs, Elevators, and Room Lights for Buildings

I've made lots of progress on building interiors since the last post two weeks ago. I started working on adding stairs and elevators to connect the floors together, but then I got distracted trying to add lights to room ceilings to improve the visuals. I was able to complete stairs, and they look much better when lit with shadows. I didn't get very far with elevators yet. The placement code is written, and the basic drawing code for elevator shafts is written, but I haven't gotten to drawing elevator interiors and details.

I'm going to show what I have at this point because I'll be flying to PA next weekend to visit my parents for Christmas and won't be able to work on 3DWorld for a few weeks. I can't really do graphics development on my old work laptop.

Room Lights and Shadows

It wasn't too difficult to get lighting and shadows to work for building interiors by using the existing lighting system I had in place for city blocks, which itself was adapted from fixed (non-tiled) terrain lighting for gameplay mode. I used the same lighting settings from the city config file, which is currently set to up to 1000 light sources and 40 shadowed spotlights. That was enough for city blocks, but is somewhat short of the number of lights and shadows needed inside buildings. Well, at least it's enough for the interior when the player is inside a building. It doesn't work as well when the player is outside looking in through the windows.

A rectangular light is placed in the center of the ceiling of each room. 50% of the lights are on, based on a random number. Rooms with stairs and elevators have a higher probability that the light is lit. These lights illuminate their respective rooms and sometimes the light extends into adjacent rooms through open doors. Here is a screenshot of a lit room with a table and some chairs, where everything is casting shadows. I use a 9-tap percentage closer filter with Poisson sampling to achieve smooth shadow outlines.

Room with a table and chairs, lit by an overhead light with soft shadows.

If you look closely you'll notice that the ceiling isn't very well lit. That's because I've modeled this light source as a spotlight pointing down. It's a bit misleading drawing the light as a rectangular cube on the ceiling. The problem is that 3DWorld doesn't support area light sources that have shadows. I only have shadowed spotlights and point lights. Point lights need six shadow maps, one for each cube face, which is a bit too much for these scenes. Spotlights can use a single shadow map (shadow plane), but the trade-off is that they're limited to somewhat less than a 180 degree (hemisphere) field of view. That means the light can only point downward and can't illuminate the ceiling.

My fix is to add a second light that has a wider field of view. To save on performance, this second light is smaller in radius and doesn't use a shadow map. I can't set it to more than 180 degrees because it will shine on the bottom surfaces of any objects on the floor above. But I can set it to right around 180 degrees so that it at least illuminates the ceiling somewhat. I need to be careful to make it small enough that it doesn't light the walls of adjacent rooms. That's why the light on the upper walls and the ceiling is somewhat dim. Well, the middle part of the wall is also light by both lights.

There's no real indirect lighting yet. I do have code to calculate the average ambient lighting in each room as a function of room light on/off state and incident sun/moon light through the windows, normalized to the room's surface area. So far I haven't figured out how to use this properly. The shaders I'm using don't have any easy/efficient way to set per-object/room material properties. So I use a simple constant ambient lighting term as a hack to avoid having the unlit surfaces appear black. It works well enough for now, but it's likely something I'll have to get back to later. At least the ambient lighting varies with the time of day so that it's darker at night.

Here's another screenshot showing some connected rooms with multiple lights and objects. This is the sort of geometry generated in buildings formed from overlapping cubes. The wall placement algorithm can't quite figure these out because of the irregular floorplans produced by the overlaps. It ends up with walls that end in the middle of rooms. It's not entirely wrong - I've seen offices with partial walls like this. It's not what I was intending to produce though. Oh well, there are more important problems that I need to fix, so I'll have to live with this for now. Just one more minor todo item for my list. At least this problem is pretty rare. This is the only building near the starting location where I've seen it.

Multiple rooms in an open floorplan with tables and chairs, lit with shadows.

While it was relatively easy to make room lights work, it was quite difficult to make them work efficiently. The first major problem to solve was the interaction between building lights and city lights such as streetlights and car headlights. I was originally combining them both together into a single 2D lighting grid. This lead to poor performance because the different sets of lights had very different scales and densities. Streetlights were spread out over many city blocks far into the distance. Each light covered the area the size of a small building. In contrast, room lights are much smaller and placed very densely. In particular, they're vertically stacked on each floor. It's not uncommon to have several hundred of them, maybe even a thousand, inside a single city block. This same area is shared by no more than a dozen streetlights. The uniform grid structure didn't perform well when the distribution of lights was this nonuniform, where all of the nearby building lights were crammed into a handful of grid cells. In addition, cities and buildings were accessing each other's lights when they didn't need to.

The fix was to split out the lights into two different systems, one for city streets and the other for building interiors. This took considerable time and effort. There were many global functions and variables that had to be moved into their respective city and building manager classes. Of course, it's good to remove global variables. This change resulted in both cleaner (though more complex) code and much faster draw times. Frame rates more than doubled in some of the worse cases. Now the framerate was usually above 30 FPS. That's an improvement, but still not good enough.

The next problem to tackle was related to overdraw and fill rate. The GPU's fragment shader has a ton of work to do with all of these light sources. I'm using a 2D spatial grid data structure to limit the number of light sources contributing to each pixel, but the room lights still overlap a lot in 3D space. Walls and floors block most of the actual light, which is something the shader has to figure out using shadow maps. If you were to stand on the bottom floor of a 20 story building and look up, there would be 20 ceilings drawn above you. Ceilings are added to the list of vertices/quads to draw starting with the first floor and working upwards. This means that the first ceiling will be drawn first and will occlude the others. However, the floors are ordered the same way, so a player standing on the top floor looking down would have to wait until the fragment shader drew all 20 floors. That's terrible for the frame rate! (I guess I should go back and reorder floors. Update: I fixed it but it didn't seem to help.) Even if I can order everything properly, there are still the walls, doors, and other objects to draw.

The solution here is to do a depth pre-pass before the main draw pass to pre-populate the depth buffer with z-values and ensure that each fragment/screen pixel is drawn at most once. This makes a huge difference, nearly halving frame times (again) in some worse case view angles. It did take a lot of work though. I had to add a lot of complexity to select and draw individual tiles of buildings that were near the player. Together these two optimizations made enough of an improvement that walking around inside of buildings ran consistently above 60 FPS, and in most cases above 100 FPS.

Stairs and Elevators

This next image shows a set of stairs that was placed between two floors. Stairwells are generated as vertical slices in the floorplans that extend through all stories of the building. They're cut into the ceilings and floors of buildings using constructive solid geometry operations. Each part of a building has a set of stairs, except for houses, which only have one set of stairs per house. For each set of stairs, a room is selected where stairs can fit in the longer dimension of the room. They're placed so that none of the interior or exterior doors are blocked. Lights are placed only if they don't overlap stairs. Stairs ensure that buildings are fully connected across all floors.

Stairs between building levels, lit with shadows.

Some office buildings have elevators as well as stairs. Elevators are only added to multi-part buildings that already have stairs placed. [To comply with fire code, all buildings must have at least one set of stairs.] Elevators are incomplete at this stage. I have the elevator shafts cut into the ceilings and floors, the wall textured exteriors, and wood panel interiors. The wood paneling is really supposed to only be for the elevator cars, which don't exist yet. I haven't added elevators doors or buttons yet either. I do plan to complete them later, and maybe even add working elevators that the player can use. Here is a screenshot of an elevator tucked into the corner of a building. Elevators can also be added to central hallways of office buildings.

An office building room with an elevator in the corner. Maybe I should make it larger?

Drawing Building Exteriors

The previous screenshots showed buildings viewed from inside. That's actually the easier case to handle. Floors and ceilings are opaque and solid, except for cutouts where stairs and elevators are placed. That means that in most cases, the lights on floors above and below can be ignored because the player can't see them. The exception is rooms that have stairs, in which case we need to include the lights from the rooms one floor below and above as well. This is needed to allow light to shine up or down the stairs. This works well most of the time. There are rare cases when light should be visible from a room on a floor above or below that's adjacent to the stairs. I'm not sure if I'll fix this or not. These optimizations allow the majority of building lights to be excluded when the player is indoors, which reduces draw time considerably.

When viewing buildings from outside, occlusion culling doesn't work as well. It's not easy to determine which room lights are visible. The set of possibly visible lights for a single building can range in the hundreds, which makes performance (frame rate) suffer. I've written an algorithm that tries to approximate which lights are the most visible and uses a priority system to assign shadows to the 40 most influential lights. It works in most cases, but not always.

There are several optimizations that can be made here, which work well in most cases. (These optimizations are in addition to the simple and obvious distance based light filtering and view frustum/visibility culling.) First, only lights in rooms that have windows to the side of the building facing the player are drawn. Rooms behind them are usually mostly occluded by walls and are of less importance. This causes some drawing artifacts though, most notably when a back room's lights shine through a doorway into a front room with no lights on that would otherwise be dark. To help with this problem, this optimization is disabled for building floors that are on the level of the player. This means that if a player looks directly into a window from outside, all lights on that floor will be drawn.

The second optimization is related to viewing angle. If the player is close to a building, then they're unlikely to be able to see anything significant in rooms many floors above or below their position. This is because the exterior building walls block the line of sight through the windows. Fortunately, I haven't added interiors to all-glass buildings, so there's a good amount of occlusion. I use a test of vertical distance divided by horizontal distance from the light source with a viewing angle threshold. This optimization has a minor impact on visual quality but isn't very noticeable to the player compared to the previous optimization.

Finally, the third optimization is to disable the small unshadowed lights that illuminate the ceilings when the player is outside. These lights cost about a third of the total lighting time, but provide only a small fraction of the visible light in the rooms. This can be seen in the screenshot below, where the ceilings are darker. I might add a config file option to always enable these smaller lights later if it seems to be needed.

View of stairs, tables, and chairs through the building windows. Many of the rooms have their lights turned on.

One great thing is that the room lights are all dynamic. I could probably get away with static lights, but I want to allow the player to turn on and off room lights in the future. Or maybe lights can go on and off randomly as time advances to simulate people using the rooms. I guess at some point I need to add people to these buildings as well. I don't think it takes much frame time to redraw the small shadow maps each frame anyway.

Here is a particularly large office building, one of those types that are formed by gluing together different overlapping cube sections. Actually, this is the exterior of that building with the odd half walls shown in the second image from the top. It's 20 stories tall and has 27 rooms in the floorplan of the main section, for around 500 total rooms. If half of them are lit, that would be 250 lights just in this one building! This is the largest building in the starting area around the player and the one that causes the lowest framerate. I was able to improve the framerate from a low of 38 FPS to a new low of 74 FPS using a variety of optimizations. At this point I'm pretty happy with the 74 FPS. Buildings are now taking similar draw times compared to grass. For reference, this view runs at 134 FPS with building interior lighting disabled. Also, the smaller buildings can be drawn at over 100 FPS.

Looking into the windows of a large 20 story office building. Room interiors are lit.

Here is a wireframe view showing just how many walls, ceilings, floors, doors, tables, chairs, stairs, and lights it has. There are thousands of objects placed in this one (out of 14,000) building. It probably has a thousand stairs alone. However, most of  the frame time is determined by the number of lights and shadow maps used. Even though the building is drawn once for each shadow map, that doesn't contribute very much to the total frame time. I should be able to add several times as many room objects without too much of a framerate hit. I guess we'll see.

Wireframe view of the previous screenshot showing the large number of placed objects and lights in this building.

Unfortunately, room lights don't match up with lit vs. dark windows at night. Rooms are lit on the CPU side and statically cached in VBOs. Windows are lit dynamically on the GPU inside the fragment shaders by using the window IDs as random number seeds to determine which windows are lit and which are dark. The GPU doesn't even know which windows along a building exterior wall belong to the same room. I have no idea how to solve this problem. It's not so bad though, at least the window lights fade out when the player approaches the building, making the problem less obvious.

What's next? I have several items on my todo list. I need to finish elevators. I would like to add some better form of indirect lighting for rooms using per-room or per-object ambient values, or something better. I also need to revisit some of the light occlusion culling methods to see if I can come up with something that has a better performance vs. quality trade-off. Finally, I need to place more smaller detail objects into rooms.

As usual, all of the code can be found on my 3DWorld GitHub project here and here.

Wednesday, December 4, 2019

Procedural City: More Building Interiors

I started discussing generation of procedural building interiors in the previous post. I've since fixed various problems so that interior walls and doorways are correct and realistic in most cases. Some of the changes even required me to go back and redesign the building exterior geometry. For example, doors are placed after interior walls now so that they don't open up to the end of a wall. I'm also continuing to work on building interior geometry. I've made a lot of progress over the past few weeks, but there's plenty more work to be done before I'm happy with it.


I fixed most of the problems with wall placement. Walls rarely end in the middle of windows now. If this happens, the wall placement will be discarded and a new random placement selected. It can still occur for small sections of building walls (for example the interior of a U-shaped building) that have been clipped in a way that a partial window needed to be dropped. In this case, the other windows are spaced further apart to fill in the gap. This part of window assignment is done later in the drawing setup stage where the vertex data is extracted and stored. The wall generation algorithm doesn't know about this extra spacing of windows because it's too difficult to detect it this early in the flow. It uses the wrong window spacing for checking that a wall ends at a window.

I fixed the misalignment of walls at T-junctions where two adjacent parts of the building place walls that intersect each other. In addition, there was a similar case where two parts try to place walls at the same location between them and the doorway positions don't line up. [Where here "part" means a single geometric primitive that is attached to other primitives to form a building, which in the case of houses is always a cube.] This resulted in either a partial narrow doorway or no opening at all. Now the placement of walls and doors between parts is done in a separate step after all parts have placed their own interior walls. This guarantees that all walls that could intersect the part boundary walls are known and can be considered when placing the final set of walls.

Finally, I improved the placement of doorways. Long walls now have a chance of getting additional doorways that improve room connectivity, adding loops and hallways. A doorway can be placed if it  connects two rooms that were previously not connected by a doorway. I believe the current algorithm should guarantee that every story of the building is fully connected (walkable) so that every room can be reached from every other room through some path. I can't quite prove this, but so far I haven't seen any disconnected rooms in the dozens of buildings I've inspected. Larger rooms are often connected on all four sides to adjacent rooms.

Interior Doors

I added placeholder 2D quads (rectangles) representing doors between interior rooms of buildings. They don't have any width right now. In fact a single door is actually stretched to the entire height of the building, where the door texture is repeated for each story. The doors are all open for now. At some point I might have randomly closed doors, or even allow the player to open and close doors with an action key.

I might have to split up the doors into separate quads for each story/floor. On the other hand, maybe it's okay to use a single tall quad. The player can't see any floor other than the one they're on, so they won't know that they're opening all of the doors on each floor at the same time. Of course this will change when I add stairs (more on this in the next post).

Interior Objects

I started placing simple objects in rooms. At first it was just one cube per room, but now I have tables with up to four chairs around each of them. These are placed at random locations within most of the rooms with constraints that they stay within the room bounds and don't block any doorways. I haven't added textures yet, so all tables and chairs are unlit solid colors. The geometry is procedurally generated and very simple, consisting only of cubes.

There are around 600K total rooms in the secondary city buildings. That would translate to around 500K tables and 1M chairs. That's too much geometry to store in memory, so I've created a system to dynamically generate interior room geometry for nearby buildings and delete it when the player moves away from the buildings. This limits the geometry to only a few hundred out of 14K buildings at a time. I'm only storing cubes tagged with metadata for each object on the CPU, which is also needed for player collision detection (future work). Vertex data for each object is sent to the GPU when the buildings are visible but is not stored on the CPU side. This data is freed when buildings disappear from view.

Here is a screenshot of a building with placed room geometry. The camera is outside looking into a room. You can see a table, some chairs, walls, and two doors in the background.

Large house with doors and a table with chairs placed into most of the rooms, looking through the window from outside.

Interior Windows

I spent quite some time trying to get interior windows to work right. The exterior walls of buildings are zero width with brick/stone textures on the outside and plaster textures on the inside. This is done by drawing the front and back faces in two passes using different textures. When the player is outside the building looking in, any face viewed through a window is an interior face and all other faces are exterior. (Note that the previous post still showed brick/stone textures on the insides of buildings.) The entire wall of each building face is a single quad. Windows are cut into it using a depth pre-pass when viewed from the outside and a stencil test when viewed from the inside. I had to implement the inside view a different way because the depth test approach caused artifacts when looking through multiple levels of windows, which wasn't possible until I added interior windows. For example, when looking from the inside of a building out the window into the window of the neighboring building.

The approach I used works because the player can only be inside one building at a time. That building is drawn first using different OpenGL draw modes from the other buildings. Then the other building windows and walls are drawn. It only takes, let me count ... 8 draw passes using different states to get this right.

Here is a screenshot of a room with table and chairs, this time viewed from inside. You can look out the windows and see into other buildings, which also have tables and chairs. I haven't added window panes and frames to interior windows yet. It's quite tricky to get that extra (9th?) pass in there. I also haven't figured out how to let the player look through more than two buildings (a path of interior => exterior => interior windows).

Inside a room of a house with a door, table, and chairs, looking outside at other buildings.

Okay, that solid color geometry and lack of directional lighting on the interior just looks too bad. After adding that screenshot above, I went into the code and enabled 20% diffuse lighting. It's not actually correct, because the sun doesn't shine into the rooms. What I really need is indirect lighting, or light fixtures on the ceilings with shadows. I have no idea how to add either of those for this many buildings in realtime, so that will have to wait until later. I could probably add up to a thousand static spotlights or point lights on the ceilings, but I can't add the shadows. I expect unshadowed room lights to look worse than no lights at all because you would see them shining through walls. I think this lighting looks a bit better than in the previous screenshot even if it's wrong. I also added a simple wood texture for the tables and chairs. Yes, even the chair seats.

Room with some diffuse interior lighting and tables with chairs using a wood texture.

Another view of a room interior.

After adding this screenshot, I went back and added proper support for multiple interior object textures. Now the seat cushions use a ... marble texture? I guess you'll have to wait until the next post to see them though. I can't go using all of my good screenshots on this post.

There's one more problem with these windows. This trick doesn't work when looking out a window into a different window of the same building.This can happen for L, T, H, and U-shaped buildings when the player is in one wing looking across a courtyard at another. The problem here is that the view ray will pass through an interior window, then an exterior window, then another interior window. There's no way to draw both interior windows before the exterior window without splitting the building into two parts that are drawn in different passes. It's the same limitation as alpha with blending. I'm not tracking enough info to draw individual parts of a building at this time. So instead I draw the exterior walls into the stencil buffer to remove the interior windows that look out at the exterior of the other part of the building.

Here is a wireframe view of the edge of the city showing just how much geometry there currently is. The tables and chairs are easy to see. The grass, of course, is the densest and still takes the most draw time. Adding building interior geometry only dropped the framerate from 125 FPS to 120 FPS.

Wireframe view of the edge of the procedural city showing all of the building walls, ceilings, tables, and chairs.

That's all for now. The next step is to connect floors together vertically using stairs and elevators. I've already started working on stairs. It seems like a fun project. There are lots of things that can go wrong, so this step may require going back and rewriting other parts of building generation again.