I'm always looking to improve the realism and variety of 3DWorld's procedurally generated buildings. One problem I have with some of the larger office buildings is that they don't have enough natural light. Sometimes they don't even have enough artificial light when the placement algorithm fails to add light fixtures to the ceiling. I can fix this (at least for the top floor) by adding skylights to some of the buildings with flat roofs.
This was no easy task, and required implementing and fixing a variety of systems. What makes this especially challenging is that skylights form an interface between the interior and exterior of the building. These two parts are drawn using entirely different approaches and code, so it's not clear exactly how a skylight fits into this system. For example, interiors are only illuminated by room point light sources, while exteriors are illuminated by directional lights from the sun and moon. The solution I ended up using was drawing the transparent glass as part of a building's exterior, while the horizontal metal bars separating and supporting the glass panes are drawn as part of the interior. More on that below.
Before I jump into drawing and lighting skylights, I have to go over how they're placed and incorporated into the building's exterior geometry. The easiest case is to only add skylights to buildings with large flat roofs. This limits skylights to office buildings, since houses always have sloped roofs. (Plus, I'm not sure how well skylights combine with attics.) In addition, skylights are only added to cube-shaped (non-rounded/angled) buildings because these are the only type of buildings with generated interiors. If there's no interior, then what's visible through the skylight? Empty space? The ground?
Once a suitable roof is chosen, the skylight is dropped somewhere within it, in most cases near the center. The size is chosen randomly from between 20% and 40% of the roof size in each dimension. Ideally we want to place the skylight in some sort of public area like a hallway or lobby, but unfortunately rooms haven't been assigned yet. In fact the walls haven't been added at this point. Skylights can be seen on distant buildings when flying above them long before the interior walls and room objects can be seen, so we must generate them first. I guess the room placement algorithm will have to handle this later. As it turns out, this breaks my floor-planning system. Office building floor plans are shared across multiple floors and can't easily be customized for the top floor to handle a skylight. The template-based hallway assignment system of larger buildings also isn't flexible enough to work around a skylight that's larger than a single room. I want to support large skylights without this size limitation.
So in the end I simply cut the walls, doors, and door frames a bit shorter so that they can fit under the skylight, and I draw their top surfaces since they're visible in this situation. That leaves the elevators to deal with. Ideally the tops of the elevators shouldn't reach the skylight. Real elevators usually have machinery in the space above them. However, some skylights cover the entire valid elevator placement area, so there's no way to place an elevator that doesn't intersect a skylight. The best I can do is clip the top of the elevator in the same way as the walls so that it just touches the bottom glass of the skylight. The problem here is that the light and inside roof of the elevator car can extend above this point. I had to hack around this with some not-quite-volume-preserving adjustments to the elevator car z-values when it reaches the top floor. We just squish the ceiling down a little bit. It's difficult to spot though, so I expect users to not even notice.
Now that we've chosen the skylight location and hacked the geometry under it to make it look correct to the casual observer, it's time to cut the hole out of the roof. Fortunately, I can reuse the code that cuts holes in the roof for the roof access stairs. This is probably the only part of skylight addition where I can reuse existing code! The next step is to fill in that hole with a partially transparent glass plane that's recessed slightly vertically. Which of course doesn't "just work" because alpha blending is disabled for building exteriors. No problem, I can simply add the skylight as a fake "window" and that surprisingly worked the first time. I don't have to worry about lighting from the interior lights on the glass because skylights are transparent enough that the user can't tell if the lighting is incorrect.
The next step is to add the white metal horizontal supports for the glass panes. At first I wasn't sure how to do this because they need to be lit from the sun or moon above, and from the room lights below. Exterior objects are only lit by the sun/moon, while interior objects are only lit by room lights. I think that's too much geometry for the exterior, so it makes more sense to have the bars be interior room geometry. As for the sunlight from above, I can place an invisible room light in the air far above the skylight with a projected volume that exactly covers the skylight. No one said room lights had to be *in* a room! As a matter of fact, I can have this fake light illuminate the walls, floors, and objects inside the building below the skylight. If I make the bars shadow casters, I can even have them cast nice shadow lines on objects below.
With all of those additions, we have skylights that look like this viewed from above:
 |
| Office building skylight as viewed from above the roof, with a person standing in front of the elevator. |
Maybe the bars and tops of the walls should have more color contrast? I'm not sure. Skylights look mostly correct when viewed from below (inside the building) as well:
 |
| A different skylight viewed from inside the building. The horizontal bars cast shadows on the walls and floors. |
Did you notice something off about those two screenshots above? The sun shines on both walls of the hallway in the first screenshot, and the shadows of the bars on the far wall aren't parallel in the second screenshot. What's going on? This is because the real sun is a directional light source nearly infinitely far away. Shadows cast from parallel objects remain parallel. But the building interior system doesn't support directional lights, it only supports point lights and spotlights. My fake sun is really like a super bright spotlight hanging high up in the air above the building. The light rays diverge from that point, which is why the shadows cast on the walls and floors look that way. I don't really have a good solution for this, so I'm hoping no one notices.
Ah, but there's another problem. What do I do with the room lights that would normally be placed on the ceilings? I tried putting them on the bottom of the skylight, but that just looks wrong. Maybe I need a smaller type of light that goes onto the horizontal bars? Maybe it only matters at night when there's no light coming in from the sky. For now I can ignore this problem. There's a similar problem with floor signs above stairs. In that case it's easy enough to move the signs off to the side, and attach them to the stairs wall that holds the railing rather than to the underside of the skylight.
The next feature to implement is indirect lighting for skylights. (In reality, this task was easier to do, so I added indirect lighting before direct lighting for skylights.) Once again, I can treat skylights as windows, except that they're horizontal rather than vertical. They're also quite a bit larger than windows and need far more light rays for a smooth (non-noisy) indirect lighting result. I went with 8x more rays, which makes skylight indirect lighting quite expensive to compute. Here is what indirect lighting looks like for the same skylight as in the above screenshot:
 |
| The same skylight as above, this time with indirect lighting enabled. |
Maybe that's too bright near the top? I'm using the same light intensity as I use for regular windows though. I think this is correct: skylights do let in much more direct sunlight than windows, at least when the sun is high in the sky. So this could be "correct" lighting for a skylight this large at midday.
Skylights can be placed over offices as well. Unfortunately, these offices usually don't have ceiling lights and are very dark at night. I could put a light on the wall if I had implemented non-vertical spotlights.
 |
| Another skylight above an office. There was no room to place a light fixture on the ceiling. |
I did, however, add a check to avoid placing bathrooms under skylights. It just feels odd to fly over a building where I can see into the bathroom. I'm not sure if this applies to real buildings or not. My previous house in fact had a skylight in the bathroom, but I'm not sure what exactly a person "flying" above it would actually be able to see.
All of that discussion above was on placing and drawing skylights. There was even more work to be done. For example, skylights increase the ambient lighting in the building, which affects things like zombie visibility in gameplay mode. They also need to participate in occlusion culling. Objects that were previously hidden from the player by the roof may now be visible through a skylight when the player is above the building. The skylight must be treated as a visibility portal in the roof. I can't remember exactly what else I had to change in the code to implement skylights, but it was a lot of work. The only thing I didn't have to change was player collision detection because the skylight can be walked on the same as the roof.
Hello, your project is amazing. I have read some of your blog posts and one question I have is how are spatial queries performed ? For collision detection, culling, LOD etc. do you use one or multiple acceleration data structures (octrees, BSP trees, etc.) ? How are they initialized and updated as the scene hierarchy expands/changes and objects move ? Optimizations that you have done ? Do you pre-compute data (e.g. octree with polygons stored in its leaves) ? Can you describe the control flow of how you manage your scenes (expansion of the scene hierarchy, LOD, culling) ? Thank you so much.
ReplyDeleteThanks! I use bounding volume hierarchies (BVH) for various purposes in 3DWorld, such as for collision detection, ray casts, visibility queries, etc.
DeleteHowever, for the procedural city environment, I use a fixed set of hierarchies instead. The world is divided into terrain tiles that are smaller than a city but large enough to hold several city blocks. Buildings are assigned to terrain tiles, and there's a mapping system to quickly get the tile for a given (X,Y) location. This is where all queries start, but iterating over buildings and other objects within a terrain tile. Any query for an object outside a building usually ends here. Any query for a building interior continues into a building.
Each building is represented as several "parts". For example, an L-shaped house is two parts, while a complex office tower can have 8 or more parts. The query will iterate over parts to find the correct one, then determine the floor index, then iterate over the list of rooms for that floor. Then we can iterate over the objects within that room to find collisions, etc. Then the objects inside that object (for shelves, closets, etc.)
So that's how it generally works: tile => building => part => floor => room => object => sub-object. Each level has at most a few tens of items and doesn't need any other acceleration structure. It just needs a lot of bookkeeping to query items contained in other items.
One tricky part is allowing the player to move objects between rooms or even buildings. There's a separate "expanded objects" vector that has to be searched through for most queries. When the player takes an object, it's replaced with a dummy placeholder. When the user puts the object back down, it's added to the special container that needs to be searched. But unless the player is determined to put thousands of objects all in one place, iterating over it isn't much of a problem.
One big advantage of this system is that I can incrementally add and remove tiles, buildings, rooms, etc. without needing to modify any unrelated objects. Since there's no global acceleration structure, I never have to rebuild an expensive object. All updates are incremental and can be spread across multiple frames.
Oh and for people and cars: People in buildings are stored inside their respective buildings and iterated over at the same level as building parts. People out on city streets are stored per block (which I refer to as "plot", as in plot of land). When they cross the street they're moved from one plot to another, and we can easily get the plots within a tile. Cars are stored by road and will be moved to different roads when they cross through intersections. Again, we can get the set of roads for a given city, which we can get for a given tile.
DeleteThank you so much for your detailed reply. That's a very thoughtful way to organize a scene. A lot of food for thought. I have some further questions if you don't mind.
ReplyDeleteJust to get an idea of how large your system is. Approximately how many terrain tiles are there ? It sounds like there might be hundreds or thousands of terrain tiles.
What kind of mapping system do you use to map positions to terrain tiles ? I imagine some kind of spatial hash or regular grid would work well.
One important thing I want to clarify, do all ray traces, bounding volume intersection tests etc. and any spatial queries in general for collision detection, physics, AI and whatever else, all start from the level of terrain tiles ? And then for each relevant terrain tile iterate through the various relevant collections and descend through the various relevant hierarchies ? I assume that you perform view frustum culling, occlusion culling, LOD etc. in the same manner, at the level of terrain tiles and then for each terrain tile iterate through the various collections and descend down the various hierarchies.
It sounds like terrain tiles are very flat data structures, that basically are containers of linear lists, one linear list for buildings, another linear list for objects outside of buildings, another linear list for roads, and another linear list for plots. Querying a terrain tile amounts to a linear scan through the relevant list(s) with possible descent into composite objects like buildings, which are basically containers themselves.
To make things more concrete, as an example, when a spider attempts to calculate a new movement vector it "maps" its current position to the relevant parent terrain tile, and then iterates through the buildings of this relevant parent terrain tile to find its parent building (bounding volume contains its current position), and then iterates through the building "parts" of this parent building to find its parent building "part" (bounding volume contains its current position), and then "looks up" its parent building floor (on the basis of the vertical component of its current position), and then it iterates through the rooms of this relevant building floor to find its parent room (bounding volume contains its current position), and then it traverses a BVH that contains the static geometry of its parent room, to find the surrounding polygons that make its immediate environment.
It's not easy to type a reply of this length in the small reply box. It might be better if you can email me, at fgennari AT gmail.com. But I can try to reply here, one question at a time. Note that I'm not editing or really proofreading this reply.
DeleteThere are an infinite number of terrain tiles because new ones will be generated as the player moves around. Well I suppose there are 2^64 total tiles because they're 32-bit integer coordinates in X and Y. But the view distance is around 11-12 tiles, so there would normally be about 500 total tiles visible at any given time.
I use a tile map that's an unordered_map from (x,y) integer pair to tile pointer. The integer indices are the integer part of the floating-point coordinates and can be trivially calculated from them. They form a regular grid, but it's not always a full square. Tiles may be generated ahead of time or destroyed later based on player motion prediction, priority (underwater has lower priority), etc.
Not everything starts from the tiles. Ray vs. terrain queries use the actual terrain heightmap (when loaded from an image) or the procedural height function itself rather than the tiles. Other queries will cache things like the building that contains an object so that it doesn't need to start from the tile each time. One way to make the queries faster for commonly used objects is to cache part of the path to the object and only update it when the object crosses the boundary between floor/building/tile/etc. Since every level of hierarchy has a bounding cube, it's trivial to check for objects leaving them. Plus this happens relatively rarely. For example, a car will stay on the same road for thousands of frames, and a pedestrian will stay on the same city block for thousands of frames. When the object leaves a bcube, it has to redo the query starting from the parent in the hierarchy to find the new container.
View frustum and distance culling (rendering in general) iterates over tiles and their contained objects recursively and early terminates whenever a bounding cube isn't visible. However, groups of objects are drawn in a single draw call, so it doesn't go all the way down to the leaves of the hierarchy.
Occlusion culling works at several levels. Each terrain tile has a lower resolution 4x4 quad contained occluder. Each building can act as an occluder, as well as individual building walls/ceilings/floors. At the beginning of each frame, the set of nearby large occluders are gathered, possible merged into larger shapes, and used to occlude other objects. This works on things like entire terrain tiles, cars, people, buildings, and objects (appliances, furniture, etc.) inside buildings. I have LODs as well, which are mostly based on distance from the object to the player.
I got an error that my comment was too long, so here's the rest:
DeleteThe terrain tiles themselves only directly contain the natural objects on the terrain: the heightmap, trees, plants, rocks, grass, animals, etc. The building manager has a different map from the same (X,Y) values to buildings that mirrors the terrain tiles. Most of the building hierarchy refers to objects by index so that I can have a smaller number of large flat containers to improve memory access patterns and reduce overhead. In some cases objects are sorted by building/room/floor/etc. so that I only have to store the starting index into the array in the parent.
For your example, spiders are "owned" by the building containing them, so the system always starts at that building rather than the tiles. Spiders don't leave the building or interact with anything outside the building. The same is true for rats, snakes, and "building people". The system handles thousands of these dynamic entities. High count groups such as rat swarms are handled with grouped queries that gather together a list of all objects near any member of the group. Then each member of the group is sorted by position (x-value) and checked against each of these objects using a sliding window collision system. The most expensive check is for dynamic entities colliding with other dynamic entities!
It's really the player queries that walk the entire hierarchy. Things like visibility, collision, project tile tests, and throwing objects. The only BVH used in tiled terrain mode is the one that stores all of the static opaque objects inside a building for lighting and visibility queries. The system needs to support a large number of these queries, so iterating over the entire hierarchy for each one is too slow.
Sorry, my original comment was to long. So I have added more questions and comments in this comment :).
ReplyDeleteOne question I have is where do acceleration data structures like the BVH trees exist in this structure ?
Do acceleration structures exist at the terrain tile -level ? Or just at the building and lower -levels ?
Are acceleration structures used to organize dynamic objects like pedestrians, cars and items ?
Is there a transformation hiearchy ? From the sound of things, objects don't contain references to parent objects or parent "containers" like in a scene graph.
From your reply, it sounds like most or all dynamic objects are organized into linear lists.
The key is how to "move" the dynamic objects between the linear lists. I suppose this amounts to, on every change in position, a spatial query with its past or last known position to determine its past "container(s)"
and a spatial query with its new or current position to determine its new or current "container(s)"" and then "migrating"
the dynamic object from the relevant linear lists of its past "container(s)" to the relevant linear lists of its new or current "container(s)."
All in all, it sounds like a very specialized approach that basically amounts to semantic or purpose -specific "look up tables" or "hash tables" or "key -value indices."
The advantage as you say, is that there is no one global scene graph or acceleration structure that has strong coupling between its elements and that basically requires global updating.
One interesting thing you mention is that "updates are incremental" and can be "spread across multiple frames."
Could you describe some examples of how you do this ? Adding and removing and changing things in a incremental manner over multiple frames.
Thank you again for writing such a detailed reply and your very interesting blog posts that are filled with so much interesting ideas.
Each building contains its own BVH of objects for use with ray queries (mostly for lighting). Iterating over the hierarchy works well for point/sphere collisions, but not for long lines. Some of the 3D models that support lighting and per-triangle collision detection also contain their own BVH. I think the only one that has this in my buildings scene is that Ferris wheel model I added. Other objects are stored in (X,Y) grids or lists of objects. Some of these are sorted so that binary search can be used. It's really customized for each level of hierarchy/type of container.
DeleteObjects are instanced with translations, and rotations in some cases. For example, buildings, cars, people, furniture, etc. can all be rotated. I don't think anything is scaled other than that Ferris wheel. Most objects don't have pointers back to their parents because they're accessed top-down. Everything is nested; I don't have a flat list of objects because that doesn't scale to huge scenes. (The test scene I have is a 49 square mile island with 18,000 buildings.)
Dynamic objects are stored the same as static objects. The only real difference is that they sometimes need to be reordered when moved. Well, in theory, most objects are interactive and can potentially be dynamic. The player can take, move, destroy, or interact with almost everything. This includes opening/closing doors, turning lights on and off, using the elevator, picking up and dropping room items, moving furniture, and even blowing up cars. So basically the framework has to support incrementally updating everything. Which is why having a big flat list of objects doesn't work.
Continuing:
DeleteWhen the player picks up an object in a building, a dummy object is added in its place to avoid making bigger changes. If the player drops the object somewhere else, we first try to find a dummy object in the correct location that we can use. Otherwise, a new object is added to the end. In this way I never have to reorder the entire container. Any object that doesn't change building/floor/room can simply be transformed to the correct location.
Everything I did was customized to handle billions of virtual objects without actually storing them all at the same time. Anything that the player didn't interact with can be discarded and regenerated from the same seed when needed. And it's impractical for the player to interact with so many objects that it runs out of memory. This is why I had to create a custom game engine.
There are no global updates. Everything that occurs after loading the initial scene is incremental. All of the generation is broken down into many small steps and spread across frames. Even the generation of a single building happens in several incremental steps: generation of exterior, floorplanning (walls/ceilings/floors/rooms), room assignment, object placement, dynamic entity placement. You can teleport across the map and it will generate everything around the player in ~100 frames.
Common events are optimized for. Building doors are stored in a separate container and drawn independently so that only that part needs to be updated when the player opens and closes a door. The same with lights. And elevators.
Sorry for the detailed questions. Thank you so much for taking the time and effort to kindly explain how you have developed things.
ReplyDeleteThat's more complex than I imagined. I am just starting to learn game engine development, so it all sounds very advanced to me. Very smart optimizations.
I am a bit confused about how queries are implemented to cache things. It sounds like queries are stateful objects that internally store the last known path to the data of interest
(e.g. an internal key-value look-up table). A query processor can either re-use the encached last known path data within the query or perform explicit container traversal and store the newly found path
as the new encached data within the query.
The "grouped queries" and "sliding window collision" techniques are pretty interesting. How are grouped queries generated and processed ?
Just the clarify, the building manager manages the building hierarchy. The building hierarchy is basically a large flat collection of objects and a forest of shallow trees.
The building manager contains a hash map that maps (X,Y) position to a corresponding building. In addition the building manager contains at least one large flat collection (basically a linear list) of objects. This is basically a global dataset of all known objects. A building as a hierarchy is basically a container of semantic -specific collections (e.g. "objects in room #2") that each store indices into the large flat collection of objects contained in the building manager. These semantic -specific collisions are themselves basically (sorted or unsorted) linear lists or hash maps (position to object) or grids. Does that sound basically right ?
Somehow I get the impression, that a building is not a simply a pure data structure but also a update system that processes the update loops of its "owned" objects.
So in the case of spiders, it can bunch spiders into groups and then for each group attempt to update the motion and perform collision detection and response.
At least thats how I think it might work :P
Could you describe the sliding window collision ? It sounds very interesting.
So the rendering data is contained in intermediate levels in the hierarchy, generally as batches to minimize draw calls.
Do you perform occlusion culling in software ? What algorithm(s) do you use to cull objects against the occluders ? I imagine its a very clever approach :D
The big concepts I have learned from your replies, is that for large and dynamic scenes it is strongly beneficial to:
(A) make the scene hierarchy as flat and as shallow as possible
(B) store objects in large flat collections, so that objects are not moved around between containers or collections or trees or graphs
(C) store indices to objects in semantic -specific collections or containers of objects, like a room of a building
(C) store indices to objects in semantic -specific trees or graphs, like a building
(B) use as direct as possible look ups to semantic -specific collections or containers of objects, queries should be "aware" of the right semantic -specific collections to iterate through
(C) use spatial hashing to directly look-up things at or near positions
Thank you again for taking the time to write such detailed posts and replies too. Its all very kind of you. If and when I have any more questions I will be sure to e-mail you.
How did you fit all of that into one comment!?
DeleteYes, it's all very complex. This took me years of part time work at night and on the weekends to write. It's a very interesting and also very challenging project. All of the optimizations were made using profiling (Very Sleepy profiler and internal timing instrumentation code).
Caching of object paths works in various ways. Many objects store things like building_id, plot_id, room_id, etc. For example, an object that has a valid room_id can jump directly to that room rather than iterating over rooms in the building, saving lots of runtime. If it finds the object is no longer within the bounds of the room, it will have to iterate over rooms to find the new room and update the field. That typically only happens less than 1% of the time. The queries themselves are stateless.
Another optimization comes from the way objects are generally sorted spatially. If we find that spider N is in room R, then we can check if spider N+1 is also in room R to avoid iterating.
This can be extended to group queries. If we have a set of spiders in the same room, we can gather together all objects in that room once, and then test each spider in that room against only the objects in that room. However, I usually only run this sort of grouped query per-floor because that's simpler and seems to work well enough.
The building manager itself has a flat list of buildings with a 2D grid acceleration structure with the indices of the buildings within each grid. There's also a city manager that groups buildings by city and contains all of the info for roads, plots, pedestrians, cars, etc. And then there's a building tile manager, which is used to generate infinite "secondary" buildings out in the distance. I don't use this on the island maps but I use it in some other situations. This last one is the only one that uses an unordered_map (hash map) because the size is unbounded and a fixed grid doesn't work.
Each building contains its own set of objects. Objects aren't shared between buildings. However, they can be moved between buildings by removing them from the object set of one building and adding them to the object set of another.
The updates of people, zombies, spiders, rats, snakes, etc. are all done by the building because it contains all of these objects. The building class has something like 400 member functions. You can find the code here: https://github.com/fegennari/3DWorld/blob/master/src/buildings.h
DeleteSliding window collision detection is very simple and used in multiple places in 3DWorld, in general when the objects are small and of similar sizes. We have a window as wide as the largest object. All objects are sorted in one dimension, typically in X. Then we iterate over them in order. Each time we see a new object we add it to the fixed width window, and remove any objects that drop off the other side of the window when obj.x < window_x - max_obj_size. When an object is added, it's tested for collision against all other objects currently within the window, which is a contiguous range.
Rendering data is stored per-material. The building manager owns the exterior geometry data. Each building owns and draws its own interior. I use free lists so that memory is reused across buildings. When the player gets far from a building, it's vertex data is returned to the free list and used for another building that comes into view. When drawing, all nearby buildings are queried and their geometry is grouped by material and then drawn, which reduces the number of texture changes.
Occlusion culling is all done in software. I find the largest occluders, which are convex shapes such as cubes. These are potentially merged into larger occluders. Then I perform occlusion culling hierarchically. If an entire building is occluded, I don't need to test each object inside the building. For each occlusion query, I find the subset of occluders that are between the object and the camera/viewer, sort these by projected area, and then test them one by one. The test works by finding the six visible vertices of the object's bounding cube. They I do a ray test (line/cube intersection) for the line from the viewer to each corner of the cube. If each of the 6 lines intersects the occluder, the object is occluded and not drawn. This is valid because the occluders are all convex.
Also, in some cases I cache the occluder from the previous frame and re-check that occluder first in the next frame.
DeleteThere are many ways to implement all of this. What I ended up with is the product of several years of incremental improvements and optimizations. It's not necessarily the best solution, though it appears to work very well in practice.
Some general advice when dealing with many objects it to try and pack them in as little memory as possible and always iterate in order to get good cache behavior. The CPU can iterate over hundreds of cubes *faster* then randomly accessing a few tens of large objects that are spread out in memory.
Also, many small containers are bad for cache behavior and memory overhead. Don't store objects like this. Store them in groups of at least a few hundred, and refer to them by index in containers. If you sort by position you only need to store the first object's index in each grid. When iterating, jump to that index and break out of the loop when you see an object in a different grid.
When removing objects, don't set up your containers so that you have to iterate over or copy/move the entire array to remove an element. Simply replace that object with some dummy placeholder, and maybe go back and clean up many removed objects in a single step later.
If you have many thousands of objects, you need to add a new one, and there's no space left - just create a new bucket of objects. Trying to resize/re-allocate some massive container will create too much lag on that frame. And when you remove all of the objects from the container, keep that container around for use with the next set of objects.
Spatial hashing is good for moving objects and unbounded search spaces. But be aware that building this data structure takes time. Don't rebuild it every frame unless you expect to query it so often that the query time dominates over the build time. If you spend more time managing the acceleration structure then querying it, you've done something wrong. Fixed grids are almost always faster to build and query than hash maps or BVHs, when you can get away with using them. This approach works best when you have relatively uniform distributions of similar sized objects in a finite area.
Sorry for the delay in reply but I was sick for the last week and things are only now starting to get better. Thank you so much for describing things in detail. Sounds like you use regular grids as the principal spatial acceleration data structure. Is that also for collision detection purposes of objects against meshes (building walls for example). Taking your advice into account. I am thinking that it would probably be best to simply use very many 2D and 3D regular grids. A regular grid to store, for example, cities. Another regular grid to store city blocks per city. Another grid to store buildings per city block. A 3D regular grid for each building, and simply store the polygons of the entire building in it. If buildings become too big, then use two types of regular grids. One to map viewer/agent position to a floor, and then use a grid per floor. This use of very many grids would make things much simpler than using trees and probably more efficient too. What are your thoughts ?
ReplyDeleteSorry to hear you were sick.
DeleteRegular grids work well for uniform distributions of static objects over a finite area. I use these for collision detection of tiles, city blocks, and buildings. Everything inside a building uses the part/floor/room hierarchy.
I'm kind of surprised that you didn't just export the top story of buildings with skylights to the "exterior" so you could use the whole "exterior" rendering pipeline. I guess that would probably be more work than the spotlight hack.
ReplyDeleteThe indirect lighting doesn't look correct, because the window is acting as a diffuse light source. It's a difficult thing to get right though. It might look better if the light were sky blue, since it is emulating the diffuse light from the sky.
As to the placement, it's certainly wrong. Having worked in construction design, you never put a skylight over room boundaries and walls. Honestly, with a giant skylight like that, I would expect to see a multi-story atrium inside. Could be a neat addition to building generation! You could use them for building entrances as well!
If you don't want to change the wall generation code, the skylights should be small, and placed over individual rooms. Yes, our house has a skylight over the bathroom. The attic is walled off in that area, which is how I would approach it for residential buildings.
It's been a while since I worked on this, and I don't quite remember what all the limitations were. I do remember it was more difficult than I expected to make skylights work.
DeleteAt that time I didn't have any easy way to make part of the building interior lit with exterior lighting. Interiors and exteriors were drawn with two different geometry management and rendering systems. The lighting worked differently as well. Keep in mind that the exterior lighting isn't just the sun and moon but also the streetlights, car headlights, etc. The exterior was generated for all buildings ahead of time, while the interior was only created for buildings visible to the player.
Now I have a type of interior-exterior geometry that's generated as part of the "interior" but drawn with exterior lighting. I use this for things like signs, window frames, fire escapes, balconies, etc. (Most of this is in later blog posts.) I did go back and try making the skylights use this system, but there were other problems and I reverted the changes.
The indirect lighting is off for various reasons. The sun is too bright, the window is too large for the indirect system, it spans multiple rooms, I get strange reflections off those ceiling beams, etc. I eventually got frustrated with trying to fix it. I don't really have a good way to visualize what's going on. The light color is a mix of yellow-ish from the sun and blue-ish from the clouds, which averages to white-ish. I don't think the color is too far off, the problem is that the top edges near the ceiling are too bright. This is because the floor and opposite walls seem to focus the light into those areas. Maybe I need to model this as both a yellow point light source for the sun and a blue area light source for the sky and that would look better.
I tried various things with the skylight placement. Since this is part of the building exterior, it runs before the rooms are assigned, so I can't easily place the skylight into a particular room. I tried removing the walls under the skylight, but that caused a different set of problems with odd room layouts - in particular when the skylight clipped off a small section of wall at the corner of a room and left a gap in the wall too small for a person to fit through. Maybe I should put a raised skylight over the entire roof.
My old house had a bathroom skylight, very high up there. I haven't attempted to add skylights to houses in 3DWorld yet. That would require cutting up the top floor ceiling, roof, attic, solar panels, attic beams, ventilation, etc. It seems like it would be more complex than offices that have flat roofs and no attics. Maybe I can only add it to houses that don't have attics and that would make things easier. Or remove the attic if there's a skylight. I'll have to think about it.
Thanks for the feedback!
Also, I did eventually hang ceiling lights under the beams of the skylights so that all areas had night time lights.
Delete