Thursday, January 7, 2021


Finally, a post that's not about procedural building interiors! I added helicopters to 3DWorld's procedural cities environment. It started out simple, and I just kept adding to it like I did with cars. For some reason, I can't stop myself from adding more features. This one was 90% fun and only 10% frustration though as I was able to get most of the features to work pretty quickly.

At first I added helipads to the roofs of some of the larger/taller city buildings. But what good are helipads without helicopters? I had to add them next. I started with one 3D model, but that wasn't enough, I had to make it support multiple models and ended up with two of them. Stationary helicopters aren't so interesting, let me make them fly. They can't just fly anywhere though, they need to choose an unused destination helipad on some other building in some other city. Right, they also need to slowly take off and land, and rotate into the correct orientation in the process. Okay, so now helicopters fly around, that's pretty cool. But wait, they're colliding with buildings! Let me add collision avoidance for buildings and terrain by increasing their altitude to avoid these objects.

That's better, but they need to cast shadows on the buildings and ground. Soft shadows. They need to self-shadow themselves as well. Okay, it was a lot of work to make shadow updates efficient. Oh, wait, the blades need to rotate too. (Or is propeller the correct term here?) The shadows need to show the rotating blades. There, that's more like it. That took, what, only two weeks to add and a few hundred lines of code?

Here's a screenshot of my first helicopter model sitting on the helipad on a building roof.

Helicopter resting on a helipad, casting a soft shadow.

Fortunately, helicopters were much easier to add than cars. Cars took me months of working an hour a day at night to finally complete them. There are several factors that account for the difference. First, I already had all of the 3D model loading and drawing systems for cars that I could reuse. Second, there are only 30 helicopters compared to ~4,000 moving cars, which means I don't have to worry much about the performance of drawing them and running their AI. Third, helicopter fly in 3D, so it's a lot easier to make them avoid colliding with stuff. But most of all, they don't have to use traffic lights or worry about traffic congestion or running people over. I was able to avoid the madness of handling traffic jams.

Helicopter flying above the terrain and buildings.


Helicopters follow a three segment path where they rise vertically while rotating into position, travel in a straight constant elevation line until they reach the destination, then descend to the helipad below. Once they land they will wait 30-60s before taking off again for a new destination helipad. I should probably make them accelerate and decelerate eventually, but I'm not sure how noticeable that would be. Their max altitude is computed as the max of two values: a fixed distance above the higher elevation helipad (source or destination), and a clearance height above the highest elevation obstacle. I chose to use the terrain and buildings as obstacles to avoid. I'm ignoring trees and smaller objects for now, and just assuming my min vertical clearance value is large enough to avoid colliding with tall trees.

I'm computing max terrain height by walking along the path to the destination and checking each heightmap value along the way. Building max height is computed by ray casting through the buildings and calculating the highest point of each building that the ray intersects. Note that any ray passing completely under a building is guaranteed to hit the terrain, so I don't have to handle this case. This is pretty close, but doesn't account for a helicopter clipping the side of a building. I would have to use a projected cylinder or multiple rays to handle that case. The simplest fix for buildings was to expand building bounding cubes by something a bit larger than the radius of the helicopter. I haven't come up with a good way to handle clipping something like the edge of a cliff in the terrain. I've never seen this happen in practice, so I'm ignoring that situation for now.

One feature I didn't add (yet) is collision avoidance between two helicopters. I added simple bounding sphere-sphere collision detection code, but it seems like waiting until a collision has occurred before reacting is far too late. Maybe it's okay to allow two cars to slightly collide and then move them apart a bit so that they "just touch". It doesn't work that way with helicopters. For one, they can't swerve or slam on the breaks to quickly change direction like cars can. Then there's the danger factor of near collisions. Maybe it's okay to stop your car a few inches before hitting the car in front, and no one will even notice. That's believable in a traffic simulation. However, with helicopters, coming within inches of colliding with some other helicopter mid-air is not cool. You're not going to simply scratch your bumper or dent your license plate if you're a bit off. I can't simply move the two helicopters slightly so that they're not intersecting for that frame and expect it to look believable.

Okay then, how does it work? Collisions must be predicted and avoided ahead of time. In real life it's probably on a time scale of tens of seconds to a few minutes depending on speed. Maybe I can get away with a few seconds of motion prediction in my case. Still, helicopters move pretty quickly compared to cars, and they can cover a lot of distance in a few seconds. They would have to look ahead and predict the paths of potentially colliding helicopters out to a relatively large radius in order to correct their velocity in time. That would result in some form of cylinder-cylinder intersection algorithm, which isn't the easiest to get right.

There's also the question of which helicopter moves first so that they don't actively move into each other's path. Do you ever find yourself trying to avoid walking into someone in the hallway, so you move to the left? Then that person moves to their right, and you're still on a collision course? So you move right instead, and they move left? Yeah, that's what I'm talking about. That game of chicken would be no fun to play in real life helicopters. I have no idea how pilots actually handle that sort of thing.

Anyway, I'm sure I can solve this, but it's going to be somewhat complex. My solution is unlikely to work the first time. I'll have to try something, test it, fix it, and iterate until it works properly and is visually acceptable. Unfortunately, it seems to be nearly impossible to actually get two helicopters to collide. There are only 30 of them in something like 20 square miles of cities, and they have to collide in all three dimensions. Simply crossing each other's paths in the XY plane isn't good enough, they need to be at similar altitudes as well. Okay, maybe that's really a good thing. If helicopters are incredibly unlikely to collide, then maybe it will never actually happen and I can skip implementing collision avoidance completely? It's worth a try. It's one of those tasks where I probably won't add it until I witness a collision months from now.

Here's a screenshot showing two helicopters using two different models that are very close to each other. You can tell by the shadows they project on the road below that they're maybe 50 feet apart and headed somewhat towards each other. However, they're at different enough altitudes that they don't actually collide. The bottom of the helicopter on the right is about 20 feet above the top of the one on the left. This is the closest I've come to witnessing a mid-air collision. Sure, you wouldn't want to have your helicopters fly that close to each other in real life unless it's a stunt show, but that's not close enough to properly test collision avoidance. Also, good luck trying to capture this situation again. I don't remember how long I had to fly around before I found it.

Two helicopters nearly colliding mid-air. You can see their shadows cast on the road below.

The most time consuming step, by far, was making dynamic shadows from moving helicopters efficient. Everything else in 3DWorld's tiled terrain mode is static, which means shadow maps can be generated once and reused across frames. Yes, cars and people are dynamic, but I have no hope of ever having them all cast shadows while getting a reasonable framerate. I haven't even tried.

The big problem here is that this system was never intended to handle shadow updates every frame. The user won't even notice an extra 20ms generating shadows at startup, but adding 20ms to every frame would kill the framerate. There's a lot of stuff to draw into the shadow map: terrain, buildings, trees, parked cars, etc. - I mean, a real lot of objects. On top of that, there are many optimizations that are used for the main draw pass but haven't been implemented or enabled for the shadow pass:

  • Billboard drawing of objects such as trees are disabled because they make terrible looking shadows, so we draw the full model in the shadow pass.
  • Most objects don't have level-of-detail implemented or enabled for the shadow pass.
  • Occlusion culling has been disabled for shadows and wouldn't work well anyway when the sun is overhead because buildings don't tend to occlude too much of the city from that direction.
  • The shadow map is a higher resolution than the screen, which means more work for the rasterizer.

My first attempt at regenerating shadow maps every frame resulted in unplayable frame rates in the 20s or 30s. Then I realized I only had to regenerate shadow maps for regions around the helicopters. This brought the framerate up to around half of what it was without shadow updates, on average. A typical flyover would drop from 110 FPS to 55 FPS with shadows. I later realized that I could also skip updates when the shadow of the helicopter wasn't visible in the player's view frustum. I can get the shadow location by ray casting into the scene using the helicopter's center point and sun direction. The shadow will land on whatever point the ray intersects the terrain or a building. This helped in many situations, but the worst case when the player was looking down at the shadows was still 55 FPS.

I was able to slowly improve this by making various optimizations to specific types of objects that were drawn:

  • Tree low detail (LOD) drawing was broken (incorrectly disabled) for the shadow pass. This was easy to fix.
  • I was drawing every building in the shadow pass. Changing this code to iterate over building tiles and only drawing visible tiles (copy the code from the normal draw pass) helped a lot.
  • There was a performance bug where I was accidentally drawing traffic lights multiple times. The code was supposed to draw the set within each visible tile, but was drawing them all for each visible tile, for both the main and shadow pass.
  • I wasn't bothering to use view frustum culling of scenery objects such as plants and rocks. Enabling that helped a bit.

These changes together reduced the shadow pass frame time by nearly half, giving me ~71 FPS rather than ~55 FPS. This will help in other cases where the light source (sun or moon) moves as well, such as when the player changes the time-of-day or the dynamic day/night cycle is enabled by the user. The visual quality was nearly identical, and I improved non-shadow frame time for the main pass slightly in the process. That's the low hanging fruit, and good enough for now. I added a hotkey to enable and disable dynamic helicopter shadows to allow the user to select between quality and performance.

Here's a YouTube video of me flying around following helicopters as they cross the cities.

You may notice that the blades only rotate on one of the helicopter models. I had to split the model into two parts with the blades rotated differently from the model. This was accomplished by continuously increasing the rotation angle of the propeller while the helicopter was flying. I wanted to use smaller civilian helicopters, but most of the free 3D models I found online were of larger military helicopters. I'm not sure this type can land on typical rooftop helipads. The model I liked the most was in the 3DS file format. It's relatively easy to manually edit a text-based OBJ file model to identify and extract the propeller blades. It's not so easy to do that for a binary 3DS model where everything uses the same material. So for now only one of the two helicopters has rotating blades

I'm pretty happy with the state of helicopters for now. I may get back to them later and work on more shadow optimizations, add more models, improve collision avoidance, or add new types of destinations. I guess we'll have to wait and see.

Friday, January 1, 2021

Procedural Building Interiors: One More Pass?

I'm trying to finish up all the remaining additions I plan to make to procedural building interiors before I move on to other city items. This includes a few new objects and room types.

Interior Objects 

I've added quite a few new object types to building interiors: microwaves, computers, stacks of papers, boxes, horizontal and vertical window blinds, clothes washers, clothes dryers, paint cans, and rooftop solar panels. (Technically, solar panels aren't interior objects, but they're close enough.)

First, I added microwave ovens to some kitchen counters as gray cubes with a microwave texture on the front. This was another one of my daughter's suggestions. A random counter and position are selected, and the microwave is placed at that location if it doesn't intersect any other objects on the counter. I suppose that completes the kitchen, for now. Here's an example screenshot.

This kitchen has a microwave oven in the corner. That completes the basic kitchen setup: table, stove, refrigerator, sink, and microwave.

Up to this point, some desks had computer monitors and keyboards on them, but there was no computer. Fortunately, it's easy to create a simple computer tower by pasting a computer front panel image onto the front of a gray-black cube. Yes, that looks pretty close to the case of the computer I'm using to write 3DWorld and this blog post. I can place these computers under the desk off to one side so that they don't block the chair and can't intersect with anything else placed on top of the desk. Now the office computer desks look more complete.

A computer tower has been placed under desks with monitors, to go with the keyboards.

Some desks have computers, some have books, and others are empty. Empty desks don't look too interesting. Let's add a messy pile of papers on top of some of them. I decided on a mix of mostly white/cream paper with a few yellow pages mixed in. They can be rotated at odd angles and may overlap each other. Objects such as books and bottles can be placed over them. So far I haven't attempted to add any text to these papers; that seems like a major effort that can be done later when I work up the courage to attempt it.

Some desks have a collection of papers scattered on them. The papers are currently colored but blank.

As a final addition to house interiors, I added a chance of placing some boxes on the floor of some room types. Living rooms, dining rooms, bedrooms, and offices can have one or two boxes, while storage rooms can have up to eight boxes. Now I can populate home offices with computers, books, stacks of papers, bottles, and boxes. Here's a representative screenshot of a low-tech (computer-less) home office.

Example home office with a book, papers, bookcase, boxes on the floor, and ... bottle of beer.


The next big topic to address was window coverings, specifically for bedroom windows. I originally wanted to add cloth curtains, but I couldn't quite figure out how to add the material with its smooth wavy curves in an efficient way. There are dozens of windows in each house, and I can't add thousands of polygons for every one. So instead I decided to add straight segmented horizontal blinds similar to the ones I have on some of the windows of my house. It was easy to find a free blinds texture with normal map online. Then I had to apply that to a single cube for each blind, which is very cheap to add to every bedroom window.

I used my random number generator to make some rooms have open blinds and others have closed blinds. Then I added a bit of extra randomness per-window so that they were at slightly different heights, which looked more natural. Most blinds are left open to match the previous look of the rooms. Note that open vs. closed blinds don't actually affect the amount of indirect sun/moon/sky light that contributes to the ambient lighting of the room. Here's an example of a room with blinds that are mostly closed.

A bedroom with horizontal blinds on the windows, mostly closed.

Here is a different bedroom with open blinds. You can see that the texture is squished into the top part of the window such that the total number of slats is the same whether the blinds are open or closed. This is to simulate the rotation of the slats as the cords are used to open and close them. I might have to go back and try to find a better solution to the texture aliasing problem when the slats are too close together. I really like the pattern the normal map makes with the lamp light source in this next image.

The lamp makes an interesting pattern of light on the open horizontal blinds of this bedroom.

I can also swap the direction and create vertical blinds for some of the bedrooms. These are a bit different because they start at either side of the window and close in to the center, rather than hanging/extending from the top. Here is how mostly-closed vertical blinds look in the same room as the previous screenshot. The camera is further away from the lamp, near the back wall.

Vertical blinds in a different bedroom, one partially opened and two closed.

That's pretty good for now. I might still add curtains at some point, or maybe add more textures and variety to blinds. I still need to add cloth material to the tops and sides of canopy beds as well.


Storage Rooms

Now we move on to office buildings, in particular storage rooms. Since these rooms are only added to the ground floor of larger buildings, there tend to only be a few of them per office building compared to the hundreds of office rooms. Therefore I can add more storage room items than I can get away with for offices. I wanted to make sure I had enough item variety to make these rooms look interesting.

I showed storage room crates, shelves, and bottles in the previous post. Since then I've added cardboard boxes, computers, keyboards, and paint cans. These are all typical items you would find on office building storage room shelves. Computers and keyboards were easy to add because I already had them placed on/under office desks. Cardboard boxes are simple cubes, while paint cans are single cylinders. These shapes are easy to work with, but the process of finding appropriate free textures online was a lot more work. This is especially true for boxes, where I had to manually separate out the top, bottom, and side textures from a texture atlas in an image editor. Here is the end result: a room full of shelves stocked with lots of different items.

This storage room has boxes, two different crate types, and a chair on the floor. It also has boxes, crates, bottles, computers, keyboards, and paint cans packed onto shelves against the walls.

Note that none of the items on shelves are actually stored in memory on the CPU side, and don't have collision detection enabled. The player and "building people" collide with the shelf bounding cubes themselves and can't get onto the shelves to collide with individual items. Also, storage rooms don't have windows, so I don't have to worry about the player viewing their interiors from outside the building. The shelf contents are generated on-the-fly when the player enters the building, converted to raw vertex data, and sent to the GPU. I can add quite a few items because only a few storage rooms are in GPU memory at any given time.


Solar Panels

The next addition takes us outside the building and onto the roof. I've added rooftop solar panels to some of the houses. The most complex part of this task was deciding which roof section was the best place to add the panel. The hard requirements are that the panel can't be shadowed by another part of the house and can't intersect any other part of the roof, including the chimney. I excluded smaller roof sections such as garage/shed roofs and porch roofs as well as any triangular roof polygons. This left the larger rectangular areas as valid placements. I ordered them by height so that the upper roof sections (which can't be shadowed by another part of the house) have a higher priority. Then I iterated over them, shrunk them by a fixed amount, and checked for intersections with another part of the house. After numerous iterations, I finally got it working. Here is the result.

Solar panels have been placed on the roofs of some houses in the optimal locations.

I did run into some problems with z-fighting (flickering) when viewing solar panels of distant houses because they were too thin, which placed them too close to the roof. I made them thicker until the problem went away. But now the player can sometimes see the inside surface of the panel when standing below the house and looking up at the roof. I guess the best solution is to draw the sides as well as the top surface quad, making the panels properly 3D. I suppose that looks better overall.

Rooftop solar panels look more 3D when I add their sides.

That's all of the interior objects I had on my list, other than the washer and dryer mentioned in the section below. I think that's pretty good for building interiors. I want to go back and work on cities next, possibly fire hydrants, street signs, etc.

Room Types

I have most of the common house rooms assigned now: bedrooms, bathrooms, kitchens, living rooms, dining rooms, offices/studies, and hallways. I even have a few special room types such as libraries, entryways, and rooms containing only stairs that I call "stairs". And of course there are garages and sheds. The only two common rooms that I'm missing are laundry rooms and storage rooms, so I've added these. All of the currently unassigned rooms in houses are assigned to one of these. The first unassigned ground floor room is made into the laundry room, and any remaining rooms are assigned to storage. Since most houses don't have unassigned rooms at this point, the majority have no dedicated laundry or storage rooms. If I want to change that I have to go back and re-assign some rooms, most likely smaller sized bedrooms.

House storage rooms are filled with boxes and possibly some of the other items found in office building storage rooms. They're usually very small; otherwise a bed, table, or desk would have been placed in them and they would have been made into some other room type by this point.

Laundry rooms have a washer and dryer, assuming both will fit. If only one can fit, then it's the washer. The placer prefers to place both against the same wall if possible. I wasn't able to find any free matching washer and dryer 3D models online, so I had to use a mismatched pair. Here's an example of a laundry room.

A laundry room with (mismatched) clothes washer and dryer.

Next up is helicopters. This post is already pretty long, and helicopters aren't related to building interiors, so I'll save that topic for next time.