Helicopters

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.