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.

 

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.

30 comments:

  1. This comment has been removed by the author.

    ReplyDelete
  2. Hi i've been following you're project for a year and ive got to say you are doing some impressive stuff when it comes to building generation. But there are a few questions i have.

    Is it possible to get the program to generate a brand new map for me? In the config_heightmap mode. Maybe like changing a seed value?.

    Also is it possible for you to post another pre-compiled build on github. If it's okay with you that would be nice.

    ReplyDelete
    Replies
    1. Do you mean a new heightmap? That heightmap was created by 3DWorld using domain warped simplex noise on the GPU. I then ran an erosion simulation and switched to overhead map mode with the 'K' key, and then exported the visible part of the terrain to a 16-bit PNG image using the 'H' key. It's not really scriptable with a config file at this point. The reason I don't regenerate the terrain on the fly is because the erosion process takes several times longer than loading an image.

      You can also load a custom image, for example the Puget Sound dataset or something like that. Placing buildings properly requires a backing image storage because the building foundations and roads flatten the heightmap from the version that was procedurally generated.

      If you're talking about generating a different set of cities or buildings, I should add a random seed for that. You should get some variety by changing the number of cities ("num_cities" in config_cities.txt), which will result in a different set of placed buildings.

      I'll create a new release when I get a chance, if I can remember the process. I think I just need to upload new binaries. You're using Windows, right?

      Delete
    2. Yes i am using windows 10. I'm actually going to attempt to compile 3dWorld for the first time. My friend used to do it for me. Visual Studio community 2019 should work great i would asusume.


      Thanks for replying by the way. But yeah a way to change the seed for cities would be much appreciated :)

      Delete
    3. Okay i've managed to figure out how to generate new terrains. And there is a "mesh_seed" setting in config.txt that allows me to alter the overall heightmap output. But there is only 1 issue. Cities don't spawn. There are buildings everywhere but no roads or city blocks. The city generator seems to error out whenever i use a custom generated heightmap witch causes roads and cities to not spawn. Then again i am using the june 2019 version at this moment.

      Delete
    4. You should be able to build with Visual Studio 2019, but you need to set up all the dependencies. I normally just use the debug build because I have optimizations on and it makes debugging easier. The release build seems to be broken by a change I made for 64 bit builds an I'll fix it tonight.

      You need a heightmap for cities because they require flattening the terrain by writing to the heightmap data. Maybe I should have it just generate the full heightmap at load time with a new option? I'm not sure why the 2019 build fails. I'll create a new build later.

      Note that you won't get the 3D models for cars people, building objects, etc. because they're not included in the git repo. These files are 2-3GB total and I don't have permission to distribute some of them. If you want these, you would have to download the models yourself.

      Delete
    5. Sorry about this I don't want to take all your time but in the console when loading a heightmap this is the error that stuck out to me from what i believe causes the cities to not generate. " Assertion failed: assert((wmax + 2*border) < xsize && (hmax + 2*border) < ysize);
      e:\frank\desktop\frank\cs184\3dworld_git\src\city_gen.cpp, Line 650 "

      The way i'm using a custom heightmap is by generating it when loading config.txt using the k "key and H key method you spoke about. Then inside the config_heightmaps.txt file i edit the "mh_filename__tiled_terrain" value to use the heightmap png file i generated. And it usually loads. just without cities. Is there something i'm missing? Another thing i noticed is the default heighmap is exactly 7085 x 7085 pixels. Whilst the heightmaps i generate are unequal in scale e.g 5366 x 3250 i'm not sure if this matters or not.

      Delete
    6. That assert seems to imply that the city is larger than the heightmap. I'm not sure why that would be, maybe a scale is wrong somewhere? Or maybe it's not loading the heightmap correctly. This is still the 2019 version, right? Let me create a new release when I have time and we can see if it still fails. I'll also try to create some heightmaps to see if I can make it fail.

      For reference: The screenshot generated is whatever is shown in the map view (the entire screen). Each pixel is the size of one grid unit, which is determined from 2*X_SCENE_SIZE/MESH_X_SIZE. The factor of 2 is because the scene extends from -X_SCENE_SIZE to X_SCENE_SIZE. If you don't load the heightmap properly then it will default to a single 128x128 tile, which may be too small to fit a city.

      Delete
    7. Ok that sounds like a plan. I attempted to compile a new build in vs2019. I'm not exactly sure how to set up the dependencies manually so it can properly compile as i'm a bit new to this. Do you mind helping me with this?

      Delete
    8. I'll have to get back to you later when I have time. Right now I'm working from home, on a different computer. In fact I'm pretty busy this week, so we might not get it resolved until the weekend.

      Delete
    9. Okay, I fixed that problem with the release build. It seems like a recent Visual Studio update required that I rebuild libjpeg.lib.

      I added a config option "buildings rand_seed " that can be used to generate a different set of buildings.

      I still have to look into that assert to see if I can even reproduce it with the current build.

      I also created a new v1.1 release with the release and debug EXEs. You can try those if you'd like.

      As for building in Visual Studio yourself, you should be able to use the 3DWorld.vcxproj file in the git repo. The dependencies should already be set up (I think). The only one you have to download and install yourself in the OpenAL SDK.

      Delete
    10. Okay, I see what the problem is with that assert. You're capturing the image in the default "ground mode" for config.txt, and it's smaller than the min city size. What you want to do is either:
      (a) zoom out to a larger window in map mode using the 'z' key or mouse wheel, or
      (b) switch to tiled terrain mode using the 'F1' key before changing to overhead map mode with 'K'.

      I fixed the assert so that it won't generate any cities in that case, but that commit didn't make it into the release.

      Delete
    11. Thank you that makes sense. After hours of fiddling around i eventually realized that zooming out further in the map mode and exporting the heightmap would give me ones that would not error so much as they would be larger in pixel count. I figured it may have been that cities couldn't fit. I also finally was able to get it to compile aswell.

      Thanks for the building seed option :)

      Delete
    12. No problem. Let me know if you need help with anything else.

      Delete
    13. Could you send the links to the missing models form where you downloaded them originally? The house props are what i'm really looking for. Like the missing furniture and carpets etc. I've been searching on the sites you linked for the models but the exact ones you've used are a bit hard to find from my experience.

      Delete
    14. There are around 40 different 3D models, so it's not going to be easy to find and link them all. Most of the recent ones came from turbosquid.com. For example:
      https://www.turbosquid.com/3d-models/tv-interior-3d-model-1406049
      You would need to create an account to download them. The free account only lets you download a few models per day, so you would have to spread it out over several days. In addition, I had to make some edits to filenames, textures, materials, etc. to fix the many bugs found in these models.

      If I ever make this into a game for release I would have to buy commercial licenses for these, compress them, remove files I'm not using, and package them up.

      It might be okay to put the *.model3d files somewhere. That's all you need for loading into 3DWorld, and it would help protect the original IP by preventing it from being loaded into other 3D programs. Where exactly am I supposed to put 2-3GB of data that you can access it? I don't think I have enough space in my Dropbox account.

      Do you get any errors from missing models that prevent the scene from loading? I think it should simply not place those items if it's missing the models.

      Delete
    15. The newest release version 1.1 you have does not give me errors that prevent the loading. The january 2021 build i decided to compile a few days ago would crash because it was missing them though. But It's mainly that i wanted to have the full scenery for building interiors for immersion. And also to get a full feel of how room types are selected. You could upload the .model3d files to google drive if you you're okay with that. I don't want to be intrusive however. It just would be nice to have a way to get the external models that would function ingame :)

      Delete
    16. What's the size limit for Google Drive? Does it come out of the normal 15GB quota? I think the cars are the largest models and the room items are smaller. I'll have to find the set of models that are needed, remove the versions of the files that aren't used, package it up, etc. I'm not sure when I'll have a chance to do that, maybe over the weekend.

      Delete
    17. Yea a normal Gdrive is 15gb. You have to pay to get more than that though.

      Delete
    18. Okay, I took all of the models used for cities, cars, people, and building interiors, removed all of the original *.obj files and unused textures, and put them together. Then I added all of the textures that aren't committed to the git repo. This is 357MB of data, which is less than I thought it would be.

      I zipped this down to 222MB and put it on Google Drive. Try this link and let me know if it works:
      https://drive.google.com/file/d/122pNt6VsxlbU4vijRA0HhbiWDF0UQ-07/view?usp=sharing

      To use the models, extract this to a "models" directory that's at the same level as the git repo. Then take the "textures" directory and merge that with the one inside the 3DWorld git repo. These textures are already in my .gitignore, so they won't show up as untracked files.

      If you can get this whole process working, then maybe I'll put these instructions in my GitHub readme.md. Also, please don't use anything in this zip file for commercial purposes or redistribute it.

      Delete
    19. It's really strange. The application still thinks the models aren't there. I have everything from the zip in a "models" folder in the root directory.

      Delete
    20. The paths in config_city.txt are all "../models/", so the "models" folder should be in the folder one level back from where the exe is. Did you build it yourself, or did you use the exe from my release?

      You can also try setting:
      city convert_model_files 0
      in case it's trying to access the obj files for conversion.

      Or maybe the forward slashes are a problem? It should work with both, unless it depends on some Windows setting. Maybe try replacing the forward slashes with backslashes for one of the model paths to see if that fixes it?

      Delete
    21. Okay this works!. The whole time i thought the models folder should be in the root directory with the exe like the "textures" folder. But it needs to be 1 folder out from the exe witch is very weird. If it's possible to make it be the root directory instead i think that would be less confusing. But it now works and i'm happy :)

      Delete
    22. I'm glad to hear that you got it working! What GPU do you have, and how much video memory? You need at least 3GB to load all of the models and their textures along with everything else.

      The models folder isn't part of 3DWorld, it's more general than that. 3DWorld happens to use some of the models in that folder. It actually predates my GitHub account. Back in those days I made manual backups of the 3DWorld project, so I didn't want to have that models folder in there getting backed up each time.

      Delete
    23. I have a GTX1660TI with 6gb vram.

      Delete
  3. This comment has been removed by the author.

    ReplyDelete
  4. The nested spatial system is just how I had imagined it would work. Now that you have blinds, I don't suppose you could put blinds on some portion of windows to keep from having to draw the interior of the rooms?

    Is there a parallel spatial hierarchy for doing physics collisions and stuff?

    ReplyDelete
    Replies
    1. The various objects used in buildings are batched by material (texture, etc.) to reduce the number of draw calls, so I can't control this per-room. Either the entire building interior is drawn, or none is drawn. The exception is 3D models of people, furniture, and appliances. These objects are individually drawn, and I have occlusion culling systems for this. Adding blinds might help to occlude the interior 3D models for rooms on the side of the building facing the player if I took the entire exterior wall as an occluder (all windows covered by blinds). However, it's unclear if this would help enough to make it worth the trouble.

      Physics and collision use some of the same spatial hierarchy system. I don't have to go down to the lowest levels though, because nothing can collide with objects inside drawers, inside boxes, or on shelves at the moment. The player and AI can only collide with the furniture and shelves themselves. Physics is limited to a small number of active objects so it doesn't really need a proper spatial acceleration structure to get good performance. The building people AI generally use bounding cubes of objects for collision detection rather than the actual objects or models.

      Delete
    2. Would be really neat if you did a physics sim on the contents of drawers, so they fly to the front and get jumbled when they are yanked open. You could randomize the initial positions every time the drawer was opened, so you don't have to store the positions when it is closed.

      Delete
    3. I thought about having bottles roll around in drawers, but I never got to that. It's not high on my priority list. Right now I only have one item max per drawer because that's much simpler and more efficient. The item in the drawer doesn't exist in memory. There's a function get_item_in_drawer() that will generate a random but deterministic item every time it's called. This is used for drawing and player interaction. If the item is taken the drawer has the empty flag set.

      Delete