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.
Generation
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.
Conclusion
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.
