Friday, April 30, 2021

Procedural Buildings: Object Management

I've explained how 3DWorld generates procedural buildings and populates them with objects in previous posts. My cities test scene contains about 15,000 total buildings. Together they contain on the order of:

  • 40K shapes (mostly cubes)
  • 100K floors/stories
  • 600K rooms
  • 2M walls (cubes)
  • 1M doors
  • 10M placed objects (not including nested/contained objects) - my best guess
  • 25M nested objects - my best guess
  • 2B+ triangles - my best guess

How is 3DWorld able to generate and draw all of this in realtime? I use various tricks, including "only generate and draw what the player can see." Let me break them down by category and describe them in some detail. This is going to be a long post full of mostly text. If you're not interested in all the technical details, you can skip to the short elevator video at the bottom.



I currently place all buildings at once during scene load, and generate their exterior geometry on multiple threads in parallel. I do have a tile-based system that will generate blocks of buildings as the player moves around, for potentially infinite cities. This works pretty well, but has some drawbacks. For example, there can be some framerate stutter when generating new building tiles.

But the biggest limitation is that I haven't figured out how to get people, cars, and helicopters to properly interact with buildings generated per-tile. My goal is to have a living world where everything is simulated for the entire city, even if the player can't see it all. This means that you can walk or fly around very quickly and any AI agents that you see are in the process of going somewhere. If I was to generate a building when it first becomes visible, then all the AI's interacting with it would appear in their starting states. That can look unnatural, for example if a person is spawned in a location that intersects furniture. It's also not possible to model things like road/hallway congestion that has accumulated over time when using this approach.

So for now I'm generating all of the buildings and their large scale geometry during scene load. All I really need is the rough exterior geometry that's visible from the distance, the windows for night lighting, and a rough floorplan for the AI people to use in path finding and navigation.


Exterior Walls and Windows

I've explained how exterior walls work in previous posts, so I'll give a shorter update here. I use a view distance of several miles, so building exteriors are visible from very far away. In addition, their window lights can be seen in the distance at night. This means I need to draw not only a lot of buildings, but also a huge number of windows. Drawing every window with individual polygons would be slow and take significant GPU memory.

My solution was to split the exterior walls and windows into two different drawing passes that use the same vertex data (quads). Windows are drawn first, and the pixels are written to a stencil buffer that's used to mask the areas where exterior walls are drawn. A horizontally and vertically repeated texture is used to control the location of each window within a wall quad. The interior part of windows are nearly transparent so that the player can see through them, while the surrounding frames are opaque. (Window panes are also drawn as emissive for night lighting.) The space between windows that should remain as walls uses an alpha value of 0, which is rejected by the alpha test, skipping writing to the stencil buffer.

With this solution, I can create an unlimited number of building windows by drawing each wall exactly twice using vertex data that's partially shared. In fact I only need to draw windowless sections of walls once. The actual implementation is more complex than this, but that's the high level idea. This system has worked pretty well so far.

However, there's something missing here. Since windows are drawn as quad cutouts, they have no depth. Exterior walls are zero thickness. Doesn't that make things look wrong? Well, it's not clear that walls have no thickness when viewing distant buildings because the inside edges of the windows aren't really visible at that distance anyway. When the player gets close to a building, I generate and draw window frames that do have some thickness. These cover up the edges of the walls so that you can't even tell that they're simple 2D quads with two different wall textures on the outside vs. inside. I can hide all of this so that it appears correct to the viewer.

Interior Walls, Ceilings, Floors, and Doors

There are two high level approaches for drawing building interiors: Generate, store, and draw them per-building, or batch them across buildings. I chose to batch across buildings to reduce the number of draw calls to a reasonable number, which improves frame rate at the cost of increased GPU memory usage for storing geometry that may not be drawn. The downside of batching across buildings is that I have to generate and draw vertex data for many buildings that aren't actually visible. Note that I took the other approach for smaller and more numerous interior room objects, as described later.

The second reason I generate rooms, walls, and doors for every building in advance is that it allows me to place people in rooms and simulate their movement within the building. I don't need to place all of the objects in rooms to get the AI working, but I do have to generate a basic floorplan. The goal is to have a system that can simulate people in buildings even if those buildings aren't currently visible to the player.

I generate the entire interior wall, floor, and ceiling geometry for each of the 15K buildings in the scene at load time. There are over a million walls, so isn't this very wasteful? Well, there's a trick I can play. If I use the same vertical/stacked floorplan for a range of floors, I can actually have the walls extend through much of the building so that the same triangles are shared across many floors. I can also skip drawing of the top surface, bottom surface, and any invisible/hidden edges of walls. Ceilings and floors are even easier: I only have to draw the bottom surfaces of ceilings and the top surfaces of floors.

I initially tried to use that same approach with building interior doors, where a single door face extended the entire height of a building section and was shared by multiple floors. It worked well until I allowed the building AI people to open doors. The problem is that it looks very wrong when the AI on a floor above or below the player opens a door in front of you. Why did that door just open? Was it a ghost? The obvious solution was to split the doors into separate drawn objects for each floor, but that nearly doubled GPU memory usage for building geometry from 490MB to 880MB.

Why was I generating every door for every building ahead of time again? Right, so that they could be batched together, because the player can see the interiors through the windows of many buildings even if they're far away. But it's not as easy to see the doors through windows. In fact they're the same general whitish color as the walls they're attached to, so they blend in pretty well. We can simply skip drawing doors for distant buildings and only generate them for nearby buildings as the player comes in range of them. The visual difference is barely noticeable. Maybe walls are better off generated for every building and drawn as large batches, but doors can be treated as interior objects and drawn separately for each nearby building. That was quite a big code change, but overall I'm pretty happy with the new system. I believe it's more efficient to draw doors this way as well.

Placed Objects

I've discussed exterior and interior building walls, windows, floors, ceilings, and doors. That leaves the vast majority of building objects/triangles: all the stuff that's placed in rooms. This includes objects such as furniture, appliances, lights, stairs, pictures, rugs, clutter, etc. These placed items are what make rooms look like bedrooms, bathrooms, kitchens, and offices. I'm not sure exactly how many of these items there are because they're not all generated at once, but I'm pretty sure there are at least 10M of them across all buildings. If there are 15K buildings, and buildings can have dozens of floors, hundreds of rooms, and dozens of items per room, that really adds up quickly.

These objects span a wide range of polygon complexity:

  • Textured quads (rugs, pictures, papers)
  • Simple generated collections of cubes (tables, books, desks)
  • Mathematical shapes/curves (spherical lights, round tables, trashcans, pillows)
  • More complex generated collections of geometry primitives such as cylinders, cones, spherical sections, etc. (bottles, railings, elevators)
  • Full 3D models loaded from files with tens of thousands of polygons (appliances, furniture, people, cars)

The key to making this efficient is placing the objects in a building only when the player is close enough to see them. These objects are only drawn when the building is within the player's view frustum. But that's not good enough, some of the larger office buildings can contain more than 10K objects, which include over 1M triangles, and can't be generated within a frame's ~16ms budget. I use several tricks to overcome these performance limitations.

First, my system never stores triangle geometry for more than one building on the CPU side at once. Each room object is represented as a bounding cube, type, color, and various bit flags, for a total of 60 bytes of data. I use a CPU side geometry buffer for expanding these objects into quads and indexed triangles that's shared across buildings. Once this vertex and index data is sent to the GPU, it's no longer needed on the CPU. It's fast to regenerate everything, and can use multiple threads, so we're free to swap the geometry of different buildings in and out to manage GPU memory usage. Furthermore, I can split the objects by type or material and divide those updates across multiple frames to help smooth out the framerate.

The next optimization is the inside/outside test. Each room is tagged as interior (windowless) vs. exterior, and has various bits representing which walls contain windows. When the player is outside a building, none of the objects placed in interior/windowless rooms are visible or need to be generated. Similarly, objects can be skipped if their rooms don't contain any windows on the walls facing the player because the player can't see into these rooms. For example, none of the objects in the basement need to be drawn because they're not visible from outside the building. [It's actually more complex than that, because we have to take into account objects visible through open doorways of rooms with windows as well. The full system is thousands of lines of code.]

Since the player can be in only one building at any given time, this significantly reduces the total amount of objects that need to be drawn. Similar optimizations can be used for the building containing the player. When the player is in a room with no stairs, we can skip drawing of objects and light sources on floors above and below the current floor. This is a good way to limit drawing in the current building where the exterior windows test doesn't help. I've also implemented occlusion culling of objects using the interior walls, exterior walls, ceilings, and floors of nearby buildings. These culling steps are more aggressive when used with high polygon 3D models compared with simple objects like books. There's a trade-off here where performing view frustum culling and occlusion culling on the CPU only makes sense to do on high polygon count objects that are expensive to draw.

The next category of optimization involves nested objects. This includes objects placed on shelves, books on bookcases, objects in closets, items in drawers, etc. These items aren't generated as part of the building or individually placed in rooms as separate objects. They don't even exist at the time the building is created. The items on a shelf only need to be generated when the room containing the shelf becomes visible to the player. Objects in a closet are only generated when the player opens the closet door. Objects in dresser, desk, and nightstand drawers are only generated and drawn when the player opens the drawer. I call these steps "object expansion" because these objects are nested inside other objects and must be expanded into real objects to be included in drawing or player interaction. In theory the system should be able to handle something like a book placed inside the drawer of a desk on a shelf in a closet.

Since each of these actions requires player input, we can have at most one object expansion per frame. This allows the system to handle an immense number of total nested objects hidden inside a building. In fact the object count can be nearly unlimited. In theory, maybe there's a performance problem if the player goes through every room in a collection of nearby buildings and opens/expands every object. However, that would take countless hours of time, and it's not something I'm worried about at this point.

If you think about it, this applies up the hierarchy as well, all the way to the level of terrain tiles. The full hierarchy includes:

  • Terrain tiles, each of which contains several
  • Buildings, each of which contains several
  • Floors, each of which contains several
  • Rooms, each of which contains several
  • Objects, each of which contains several
  • Drawers/Shelves, each of which contains several
  • Smaller objects

The nesting/expansion is exponential here. However, the time taken to generate, query, and draw all of this is almost constant because the expansion factor at every level ("several") is only in the tens. In fact, traversing this hierarchy is so fast that operations such as ray intersection and sphere collision detection take a few microseconds. This is also the key to efficiently simulating thousands of AI people in buildings every frame.

Here's an example of a large 19 story office building containing nearly 1000 rooms. These rooms are full of lights, desks, chairs, tables, whiteboards, trashcans, and all sorts of office supplies. That looks like a lot of triangles, right? What you don't see are the huge number of small items in interior rooms, on shelves, and in desk drawers that may not even have been generated yet. You don't see all of the 3D models of things like toilets in interior rooms. This single building is larger than the levels of most (non open-world) games, and there are thousands like this. This entire thing takes only a few milliseconds to generate!

Wireframe view of a large office building and some smaller surrounding buildings.

Lighting and Shadows

Most rooms contain at least one light source, and most objects cast shadows. Ceiling lights are implemented with both a downward pointing shadowed spotlight and an upward pointing unshadowed spotlight that's constrained to only light the bounding cube of the room. 3DWorld supports up to 1000 active room lights, though distance and visibility culling are generally able to reduce this number to only a few hundred. These lights are prioritized by distance and screen area and only the first 60 use shadow maps. The remaining lights use constrained cube volumes determined by ray casting against the walls, ceilings, and floors to determine the max extents of each light. This both improves performance and reduces light leaking through walls, ceilings, and floors.

Shadow maps are managed by a memory pool with free list to avoid repeatedly allocating and deleting shadow map memory on the GPU. They're also cached across frames when there are no dynamic shadow casters within the light's bounding cube/radius of influence. Dynamic objects such as building AI people, the player, balls, elevators, etc. will force the shadow map of that light to be updated each frame. Typically only a few of the 60 shadow maps are updated in any given frame, which gives reasonable performance. Room object occlusion culling and view frustum tests are enabled during the shadow pass (and reflection pass for mirrors) as well.


Since this post is all text and few images, I'll add a short video at the end showing that I have working elevators. The player can press the call buttons outside the elevator or the buttons on the inside. The buttons and floor numbers light up, and the elevator will go to the correct floor. The doors open and close as well. The elevator has sliding and "ding" sounds that I wasn't able to record in this video.

All of the code can be found in my open source 3DWorld GitHub project. For example, the code to place objects in rooms can be found here.

Sunday, April 11, 2021

Procedural Buildings: Object Interaction

I'm continuing to work on my game where the player steals valuable items from houses and office buildings while avoiding zombies. My goal is to make almost every object inside the building both something the player can steal, and something the player can interact with either before or after stealing it. I also want to make this as silly as possible rather than a horror game. I started with the basic set of player object interactions required for gameplay, and some other easy ones, which were implemented earlier:

  • Picking up objects
  • Opening room, closet, and bathroom stall doors (which may be locked)
  • Opening and closing dresser, desk, and nightstand drawers
  • Turning on and off ceiling room lights and lamps
  • Throwing and kicking basketballs and soccer balls
  • Drinking beverages (wine, beer, Coke, water, and newly added poison)
  • Riding elevators up and down
  • Spinning office chairs

This time I've added many more object interactions to increase the fun level. Why stop at stealing when you can trash someone's house in the process? Add graffiti, make a mess, and run up their utility bills. The zombies won't care, but when those people return to their houses after the invasion, won't they be in for a surprise!

  • Basketballs and soccer balls can now be thrown at zombies to make them temporarily retreat 
  • Spray paint cans that can be used to add graffiti to walls, ceilings, floors, and other flat surfaces
  • Markers that will draw on walls, ceilings, floors, whiteboards, pictures, rugs, mirrors, etc.
  • Turn sinks on and off (to waste water)
  • Flush toilets (to waste water)
  • Pull toilet paper off the roll (future work: wrap toilet paper around objects)
  • Tilt pictures hanging on the wall
  • Various other objects make sounds and/or animate
  • Player can use elevator buttons (fully functioning elevators are in the planning stage)

None of these really affect gameplay, except for the first bullet point where hitting a zombie above the legs with a ball will cause it to retreat for a few seconds. This gives the player some time to get away. I might add other throwable items, such as books, at a later time. None of these interactions affect the value of items the player has or the player's survivability.

Spray paint and markers are my favorite so far. My daughter Kate also loves to make her artwork in the office buildings. Too bad I haven't implemented a save system for this yet! The player must first find a can of spray paint or a marker on a storage room shelf or in a desk drawer. These will be a color randomly chosen from a set of common colors for those items. Picking up this object will allow the player to carry it around and use it with the action key.

Each key press (or each frame if the key is held down) will generate a circular spot of color as long as it's not too close to the previous spot (optimization). Spray paint and markers have a max range and will only write on certain types of large, flat, static objects. This includes walls, ceilings, floors, windows, mirrors, bathroom stalls, cubicles, stairs, elevators, rugs, pictures, and whiteboards. Each spot is an alpha blended point sprite quad drawn with a circular blur texture. Multiple points placed near each other will merge into solid lines of color that look like real brush strokes. These are oriented in the direction of the surface and shifted a bit in front so that they're drawn on top as decals. The draw order is preserved for blending, so the player can paint over existing spots with new colors. Spray paint that's sprayed from far away creates a larger but lighter circle, while close up sprays produce smaller and stronger color spots.

These quads are stored in a dynamic buffer and sent to the GPU each frame. I could probably break them up into blocks and store them on the GPU in VBOs as an optimization. For now it seems to be fast enough that this isn't needed, unless I really expect players to spend tens of minutes painting the walls. The graffiti will remain in the building until the player starts drawing in some other building. I only allow graffiti in one building at once for now, as an optimization. Paint and marker can be seen through the windows and open doors of a building. Here is an example of my artwork:

Inspecting my artwork in this office building hallway. All it took was three cans of spray paint and a dry erase marker.

Markers will write on whiteboards, but they write just fine on the walls as well. If you take your time it's possible to create very accurate and detailed drawings. The capacity of a spray paint can or marker is large enough to create quite a bit of color. At this point there's no way to erase them, so you need to be careful not to make a mistake.

I left a surprise for someone to find when they get back to the office after this zombie invasion.

Toilet paper rolls can also be taken off the holder and used. (The holder can be stolen as well.) I haven't quite figured out how to use toilet paper, other than pulling it off the roll down to the floor. I was thinking that I would have the action key wrap toilet paper around objects. Or maybe the roll can be thrown and will trail toilet paper behind it. I guess we'll see what I end up doing.

Here's some graffiti to point out that the roll of toilet paper can be taken for some extra fun.

[Yes, the toilet paper roll is attached to the block window. The house near the player starting position is the only house I've seen that's like this. This looks bad for normal transparent windows, so I remove the toilet paper in those cases. But a roll on a glass block window isn't as bad. Maybe it's glued on? So I allow it.]

The player can turn bathroom/kitchen sinks and tubs on and off. The sound of running water is played for a few seconds when these are turned on. I've considered letting the sound play in a loop while the water is running, but I'm not sure how practical it is when the player can turn on every sink in a building. Maybe it should only play when the player is in the bathroom? I don't know, it still seems like the sound would be annoying. I've also added an animated stream of water coming from bathroom sinks when they're on. Here's a screenshot, though you can't really see the animation in the water.

I turned on the water in this sink. You can see the reflection of the previous screenshot in the mirror.

It's silly to tilt the pictures in someone's house after you've stolen all of their valuables and drawn all over their walls. However, this was fun and easy to add.

Does that picture look crooked to you? I swear it was like that when I got here!

The next item on my list is working elevators. I currently have elevators that will move up and down based on the direction the player is looking. I want to add real elevators with call buttons on each floor and a button for each floor inside the elevator. These will control the vertical position of the elevator and the opening and closing of its doors. I've added the call buttons, and they do light up when pressed, but they have no effect on elevators at this time. This is intended for use by the player and not building AI people. Implementing all of this could be time consuming, but sounds like another fun and interesting mini-project.

I really should record another video of all these building interactions. I wish I could figure out how to make audio recording work so that I can show off all the sound effects I've added. Maybe I'll put a video up on YouTube once I get elevator buttons working.