Monday, April 30, 2018

Building Window Generation

I'm continuing to work on 3DWorld's procedural cities, in particular the buildings. I want to make them look more interesting and realistic. Some of the building textures are plain brick or concrete block. There are no windows, doors, or other features. I've disabled these in many of my city screenshots because they look out of place next to the office buildings and other types that do have windows. It's time to fix this.

I decided to generate windows for buildings. Windows are just drawn as a texture in a postprocessing pass on top of the original geometry for the day time scenes. I draw the geometry of these buildings a second time, which applies the windows as decals using an alpha mask to let the bricks show through non-window areas. However, at night, building lights come on and the windows are emissive. These are drawn in yet a third pass with a different shader. I'll describe this more later.

I began by adding uniform 2D grids of windows to the previously windowless brick and concrete block buildings. I scaled the windows to approximately match the vertical floor spacing of the office buildings that already had windows in their textures. It makes sense that the various building types would be at the same scale. I made the center of windows a dark gray with a light gray window frame around them. There is only one window texture, and it contains exactly one window. The texture is generated based on user-specified config files that control window width, height, x-space, y-space, and border width. Window spacing and grayscale color can also be specified per-building material to help them match the surface textures with good contrast. Here are two screenshots of buildings with windows added. Note that I also added sloped roofs to some of the larger rectangular buildings.

Brick and concrete block buildings with generated windows in a uniform grid.

More brick and block buildings with generated windows. Window colors have been adjusted for good contrast.

The next step was making these windows look better at night. Previously, buildings were all a uniform grayish color in the dark. Car headlights and city streetlights definitely improved the look of the city, but buildings were still dull and boring. Night lighting really made buildings come to life.

This part was inspired by Shamus Young's Pixel City project from 2009. Apparently, this project has been restarted. I'm not going for the same look as Pixel City though. I want cities to look good in daytime, night time, and in between. I want them to be viewed from street level instead of just from above. I haven't added the window shape/color variation, lighted signs, and other detail lighting and geometry yet. I don't think my city lights look as good as Pixel City, but I'm still working on them.

I started by adding lights to some of the windows that were generated by the procedure above. These include smaller brick and block buildings that were placed outside the main city. I had them shoved out of the way to keep the windowless buildings out of my screenshots. There are no roads, cars, or streetlights out here. It's easier to experiment with lighting with the other light sources turned off anyway. Here is how it turned out.

Buildings with generated windows lit up at night in shades of white, yellow, and blue.

Each building has a single window light color that's randomly generated to be in the bright yellow to light blue spectrum. It's a little difficult to see unless you click on the image to zoom in. Too much color variations looks unnatural. This allows for various light styles including incandescent, fluorescent, and LED. It's the same technique I used for car headlights. In addition, each building has a random number of lit windows, between 10% and 50% of the total.

You might wonder how I'm able to light a random subset of the windows efficiently when there's only a single texture. All of the magic is in the fragment shader. We have access to two important parameters here: the texture UV coordinates and the per-building emissive light color. Texture coordinates are generated by scaling the building {x,y,z} vertex positions in world space. This ensures that textures align correctly across building faces that are split into multiple quads/triangles. Unfortunately, this also causes windows to sometimes wrap around the corners of buildings. I can't think of an easy fix for this.

The window texture contains a single window + frame within the texture's UV range of [0.0, 0.0] to [1.0, 1.0]. We can split the texture coordinates into an integer and a floating-point fractional component using the fract() GLSL function. The fractional components tell us where this texel is within the window. If it's around 0.5, the texel is near the center of the window. If it's close to 0.0, it's on the bottom/left, and if it's close to 1.0, it's near the top/right. The integer components give us the world space index of the window (u=x or y, v=z). We therefore have two pieces of data here that can be used to add variation to windows:
  • The window color, which is per-building
  • The integer texture coordinate (window ID), which is per-window
These values can be used as seeds in a pseudorandom number generator within the shader. The window color is hashed to produce a lit window density value between 10% and 50%. This will determine what percentage of windows in the current building are lit. The integer texture coordinate can be used to generate a random number to compare against this lit threshold. Together, these variables will determine which windows are lit and which ones are dark. Fragments from dark windows are discarded (not drawn) by the shader. Since all fragments (pixels) of a window have the same window ID, they will all be either lit or dark.

Let's move on to the inner city, which is full of tall office buildings that already include windows in their textures. I decided to create a larger city this time. The city is a single flat rectangular area of several square km with a total of 3700 buildings. Each building uses one of 12 unique side textures. Here is how the city looks in the day time. I get around 92 FPS with this view. All windows are part of the original building textures; none of them are generated by the new algorithm.

A large city that stretches to the horizon. These office buildings all have windows as part of their 12 different texture maps.

Here is how it looks at night, before I made any modifications. The buildings are the same bland grayish colors as the brick and stone buildings. All the texture detail is muted by the dark lighting, except at ground level where the streetlights and headlights illuminate it. The moon is out here. Without the moon, the scene is even darker gray.

A large city at night. The cars and streetlights produce light, but building windows are all dark. This will have to be fixed.

Here is the same scene with window lights enabled. I think they look pretty good for medium to far distance buildings. This addition makes the scene look much more interesting. Note that distant building lights are obscured by fog, allowing them to blend into the background. This helps to hide aliasing for sub-pixel windows. Also, I moved the moon below the horizon for this image so that the lights stand out more.

The same city as above, but with lit windows added to the office buildings. Looks much more interesting.

This screenshot shows just how large the city is. There are thousands of buildings stretching to the horizon.

Smaller city with cars, headlights, streetlights, and building window lights.

Here are some images showing how window lights look at a street level view. I don't think the nearby windows look very good because they aren't perfectly aligned with the building textures. I spent a long time finding the optimal values of texture xscale, yscale, xoffset, and yoffset to use with each of the 12 building textures. This helped, but didn't really work for buildings with nonuniform window size or placement. Some textures have large gaps between every few floors. Some have different window size/spacing/placement on some floors. Others have groups of 2-4 windows closely spaced together with larger gaps between the groups. It's just too difficult and time consuming to manually align all of the light rectangles with the actual windows for each texture. I did the best I could in one night of work.

Street view showing city lights. Nearby lit windows don't look as good here.

Street view again. These buildings have better alignment of window lights because windows are spaced out in a regular grid.

One hack to help with this problem is to fade nearby window lights to transparent by adjusting their alpha values based on distance to the camera. It's one line of shader code. This improves the screenshots, but the fade looks a bit odd when the player is moving.

Street view with nearby window lights faded out to transparent. See the mostly faded lighting on the left side building.

Here is a screenshot showing buildings placed on the hilly landscape. There are no roads, cars, streetlights, or traffic lights here. The foreground buildings are office towers, and there are some brick/stone buildings in the background. This is what the placement algorithm produces when roads are disabled.

Buildings lit up at night. These buildings are scattered over the scene at various elevations, with no roads.

I added an experimental bloom effect for city building windows. It works well enough for mid distance windows. Bloom applies to headlights, streetlights, and traffic lights as well as windows. I tried using a two pass x/y separable Gaussian blur, but the x and y blur directions were obvious. This technique works better with round or spherical light sources than it does with square light sources. I had to switch to using a more expensive single pass 2D Gaussian blur for the bloom effect. A 17x17 kernel size produces pretty good results with little change in frame rate. I suspect this is because the GPU is spending so much time in the vertex shader drawing car models. The bloom shader can be found here. The following two screenshots show city lights with bloom. Note how bright it makes the car headlights appear. Nearby buildings have lights that are fading out and therefore have less bloom.

Street view of city night time lights with bloom effect applied to make lights appear to be brighter.

City lights with bloom effect, shown from above.

Enabling all of these effects drops the frame rate to 58 FPS for a street level view facing into the heart of the city. This includes terrain, grass, 3700 buildings, roads, 4000 cars, traffic lights, streetlights, 1024 dynamic spot light sources, 40 dynamic shadow maps, a city lights pass, and a large kernel radius bloom filter. Oh, and also water with reflections, even though it's occluded behind the buildings. I'm sure I can optimize this if needed.

That's it for now. I think the results are good, a huge improvement to the look of night time cities. I still need to work on some lighting effects. I would like to add a better bloom effect to make windows look brighter, especially in the distance. It would be great if I could find a way to improve window lights for nearby buildings. I would also like to come up with some system for adding detail to the windows: shadows, furniture, etc. I'm not sure if I can generate these details in the shader using the window ID. Maybe, I'll have to experiment with this.

Monday, April 23, 2018

Dynamic City Shadows

This post is a short update on my procedural city project within 3DWorld. Last time I added car headlights, streetlights, and parking lots. This time I've added shadows to go with nearby headlights and streetlights. This was challenging to do efficiently due to the dynamic nature of the cars, the large number of nearby light sources, and the high complexity of the car models.

All lights used are directional spotlights, so their shadows can each be stored in a single shadow map. Both the light sources and the shadow casters can include dynamic objects, which means that shadow maps usually can't be reused across frames. I didn't attempt to detect and optimize for the case where everything was static (streetlights with no moving cars in their light volumes). No, every shadow map is recreated each frame by rendering all objects within their view frustums. Only the texture slots are shared across frames.

In the case of cars, I used a lower detail model where the materials that had little effect on the shadow were disabled. In most cases, I only enabled the car body and underside. These materials represent maybe 20-25% of the total triangles. This means that there were some light leaks through holes in various places where objects/triangles were missing such as wheels, headlights, etc. This made such a huge difference in frame rate (14 FPS => 48 FPS for 64 lights) that I decided it was worth the loss in quality. For most of the car models, the visual difference wasn't really that noticeable.

I'm using 512x512 texel shadow maps for dynamic objects, which is a compromise between performance and quality. For reference, the global sun and moon shadows use multiple 4096x4096 shadow maps - about one per city. Shadow maps use a 9-tap PCF (Percentage Closer Filter) with a Poisson distribution of sample points. This makes the shadow edges softer and hides aliasing.

Now that I have the 3DWorld source code up on GitHub, I can actually point to the source files:
  • C++ code for city generation, road networks, and cars can be found here.
  • C++ code for building generation and rendering can be found here.
  • GLSL Shader code for dynamic light sources with shadow maps can be found here. Note that this is just part of a shader.
Here are some night time city screenshots with shadows. They're not the highest quality, but I was able to get 48 FPS with 64 shadowed lights and 58 FPS with 40 shadowed lights. There aren't too many detail objects in the city to cast interesting shadows. I'll probably add in some more objects later.

The lamp post casts a shadow on the cars and building behind it.

Dynamic lights + dynamic shadows with car headlights. The area under and in front of the cars is dark due to shadowing.

The orange car is caught in the police car's headlights and projects a shadow on the building behind it.

The traffic light casts a shadow on the blue car to the left.

Soft shadows from cars parked under a streetlight.

Shadows cast by various parked cars in a parking lot with streetlights.

Streetlight shadows produced by the lamp post and the building.

I also added car shadows for the sun and moon, but only for static parked cars. These were relatively easy and inexpensive to add, once I had the framework in place. If you look closely you can see some of the new car models I'm using. The number of unique models has increased from 6 to10. I also tuned some of the level of detail parameters to improve frame rates.

Here is a screenshot of the current state of parking lots. In addition to shadows, I randomized car parking positions some more.

Soft sun shadows from parked cars. Moving cars still use the cheap method of a dark textured quad under each car.

That's it for this post. I still need to figure out how to add better sun and moon shadows for dynamic cars. Currently, sun and moon shadow maps are generated once and cached, and only updated when the sun/moon moves. There are many high resolution shadow maps involved, and objects are drawn to them in full detail. I'm not sure how to do this efficiently for moving cars. I think it may require a new system.

I'm probably done with city lighting and shadows for now. There are still quite a few other tasks that I can work on. For example, I need to add more objects to fill in the empty spaces between buildings. I also need to add windows to the smaller brick and concrete block buildings somehow. I've removed them from the city scenes because they appear too plain and somewhat out of place. Ideally, I want to find a way to combine different window textures/types with the various brick and block exterior building material textures.

Tuesday, April 10, 2018

Procedural City Update: Lights and Parking Lots

I'm continuing to work on 3DWorld's procedural city. In the last post, I added cars. In this post, I'll describe some of the other features I've added to improve the look and realism of cities. Here is a summary of the main accomplishments, listed in the order in which I implemented them:
  • Ambient Occlusion under cars (added as an update in the previous post)
  • Dynamic lighting for car headlights on roads, buildings, and other cars
  • Parking lots full of parked cars
  • Occlusion culling of cars using buildings
  • City streetlights
That's three (two and two halves) of my future work list from the last post. Pretty good progress so far.

Ambient occlusion was already shown in the previous post. It's a pretty simple trick using a partially transparent gray texture under each car, so there's not much to say about it. I would love to add car shadows, but unfortunately I still haven't figured out how to do that efficiently. I'll keep it on the todo list for now.

There's nothing to show for occlusion culling. If done correctly, the player will never see it. It's an optimization where cars that are behind nearby buildings don't need to be drawn. I do this by selecting all visible buildings (in the view frustum) within two city blocks of the player. Then, for each car, I generate rays from the top 4 corners of its bounding cube to the player camera. If all rays intersect any one building, the car is occluded by the building and doesn't need to be drawn. This is only needed for nearby, high detail car models. Since buildings are mostly convex, and rarely have overhangs, this tends to work correctly. Occlusion culling improves frame rates, especially now that I've added parked cars. This optimization increases in-city framerate from 50-60FPS to 80-90 FPS. Yes, most of the time is spent drawing car models. Everything else can be drawn at 200 FPS.

I'll describe what I did for parking lots, headlights, and streetlights below.

Parking Lots

I found something to fill in the empty space between buildings - parking lots! What's a big city without parking lots? Each parking lot is between 12 and 28 spaces wide and between 1 and 3 rows long, as constrained by config file parameters. They're placed wherever there's enough space between a road and a set of buildings. Each parking lot is populated by cars using a random density between 0% and 75%. This results in about the same number of parked cars as there are moving cars on the roads. The parking lots are randomly oriented with randomly selected car directions. I left the cars all pointing in the same way so that the spatial sorting algorithm would magically draw them back to front to make alpha blending of transparent windows work. Here is what a parking lot with 12x3 parking spaces looks like.

Parking lots partially filled with cars. These cars are inactive/static and their headlights are always off.

These parked cars don't take much extra CPU time and memory because they're static instances with no update logic. I haven't implemented car parking behaviors, and I'm not really planning to add that. However, parked cars do take extra GPU resources to draw. This is why I had to add occlusion culling using nearby buildings. Parking lots are only generated when buildings are enabled. They're guaranteed to have padding between streets and buildings so that cars have space to enter and exit.

Car Headlights

It was actually pretty easy to add dynamic lighting support to the city scene. I used the same lighting system as I did for gameplay mode as explained in a previous blog post. Each nearby, visible car has two headlights that automatically come on in the dark. Car headlights make a huge difference in night time scenes and dramatically improve realism. Headlights illuminate the road surface, buildings, and other cars. There are currently no headlight shadows. Here are two screenshots showing car headlights with no buildings.

A row of cars stopped at a light, shining headlights on each other. Buildings have been disabled.

Cars with headlights traveling on roads. Buildings have been disabled.

I've modeled headlights as spotlights (cones) pointing slightly downward, with smooth lighting falloff at the edges of the beam. This is very similar to the "flashlight" in gameplay mode. Colors vary randomly from yellow to blue-white to simulate different lighting technologies (incandescent vs. halogen vs. LEDs). Here are three more images, this time showing buildings.

Cars with headlights driving in a city at night.

Cars with high beams in the city, shown from the point of view of a car. Maybe headlights aim too high?

Cars with headlights driving through an intersection.

The headlights are probably too bright and pointed too much upward so that they shine into the windows of the office buildings. This would probably drive people crazy! I left the settings that way just to make the lighting easier to see; I've switched to "low beams" after taking these screenshots.

City Streetlights

Parking lots and headlights are great, but there are still too many dark, open areas. I decided that I can fill some of the space with streetlights along the roads that come on at night. Each city block has four streetlights, one along each side. They're offset from each other and spaced out evenly along roads to produce somewhat uniform light coverage. I used the same dynamic lighting system as car headlights. Streetlights are also spotlights, but with a 180 degree field of view and pointing down.

Technically, streetlights aren't dynamic because they don't move. However, there are thousands of them, and I can't have them all on at the same time. This would hurt the frame rate too much. Instead, I select and enable only a few hundred of the most influential lights sorted by (radius/distance) that are within the camera's view frustum. The upper limit is 1024 lights combined across car headlights (two per car) and streetlights. Here are some screenshots.

Closeup of a streetlight shining on an empty road in the city.

Streetlights and cars illuminate the roads and buildings at night. Yes, these buildings have no windows or doors.

I haven't implemented shadows for streetlights yet.

These next two images show just how many lights there are in the city. Currently, only nearby cities have lights enabled. Maybe I should add a slider to control streetlight color?

Streetlights and headlights in the city, shown from above.

Streetlights light up the entire city at night. There are about a thousand lights in this scene, half of them dynamic.

All that's left is to add lights in the office buildings. I'm not sure how difficult that is. Would it be possible to have the fragment shader somehow detect windows and add emissive light inside their bounds? I currently don't really know how to do this efficiently, but I guess we'll see in the next post. Oh, and I probably need to add windows to those all-brick buildings, or use different textures.

One more thing: 3DWorld is now on GitHub! Here is the project page. Now you can actually go look at the code, though it may not be easy to read.

Sunday, March 25, 2018

Cities with Cars!

I showed off procedural cities with road networks in a previous post. I'm continuing to add features to my procedural city in 3DWorld. This time I've been working on adding moving cars. Initially, I just wanted to add simple cars that drove around the roads as a type of detail object to bring the city to life. But I kept adding more and more to the car system, and it got pretty interesting. Not only did I add cars, but I added traffic lights as well.

I've added various config file parameters for cars to control their number, size, speed, etc. I'm currently generating between 1000 and 10,000 cars of various colors and placing them within the roads on the seven cities of this map. Cars move around within a city, make turns, and travel between cities. The car AI update logic is very fast, consuming only 1.8ms for 10,000 cars. This is because cars only update their state every so often, rather than every frame. The majority of cars tend to be either traveling at a constant speed on a straight road, stopped at a traffic light, or stopped behind another car. In all of these cases, no velocity or direction update is needed, and the cars don't need to determine which direction to turn. These decisions are triggered by infrequent change-of-state events such as when a car's origin crosses into a new intersection or road segment, when the traffic light turns green, or when the car in front starts moving.

I added traffic lights at all 3-way and 4-way intersections to help control the cars and make the streets look more interesting. I used a minimalist, modern traffic light design. The lights for each direction are in a single vertical cube, with straight and right turn lights on the bottom section and left turn lights (if present) on the top. Red, yellow, and green lights are ordered from top to bottom to match standard traffic light arrangements. I made the light housing black so that I didn't have to worry about shadows and normals (for now). I created the turn arrows in Gimpshop. Lit lights also have an emissive overlay glow texture with additive blending to make them appear brighter, especially at night.

Traffic lights use a finite state machine with states that include a subset of {east left turn, east and west straight + right turn, west left turn, north left turn, north and south straight + right turn, south left turn}, in this order. Some intersections don't have left turns, so their number of states is smaller. The left turn signals have a shorter duration, and cars can sometimes make rights on red. There are currently no U-turns. I'm not sure why that would be needed other than in cases of navigational error, which doesn't happen here.

I started off drawing cars as simple colored, untextured cubes. Then I made them two cubes, one for the bottom and another for the top. I added brake lights for when cars are slowing or stopping, headlights at night, and turn signals that flash on and off when the cars are about to turn. My initial work, using these placeholder car models, is shown in the screenshot below. This is an initial prototype I used to get the vehicle motion right, and has been improved since that screenshot was taken.

Cars were initially drawn as two untextured rectangles, and distant cars are still drawn this way. At least the traffic lights look reasonable.

I tried to model vehicle physics as accurately as possible, including realistic acceleration, deceleration (braking), and turn radius. Deceleration is much higher than acceleration, which means cars can stop quickly at red lights but take a while to accelerate to max speed. Cars move faster when going downhill and slower going uphill. Some cars have higher max speed than others. These tend to form lines/groups of cars where the faster ones are following the slower ones.

Each car is driven by an AI that decides which way to turn at each intersection. I could probably use real path planning here by choosing a destination for each car and calculating the fastest route to get there. This would require writing an algorithm similar to what's used in a GPS. Of course, when there are many cars, the user can't actually tell the difference between random turns and route planning. I suppose this requires picking one car and following it around the city. Furthermore, it's difficult for me to even test path finding in this situation. Turns aren't entirely random; some of the faster cars will turn to go around a slow car that's in front of them.

Cars follow traffic lights, and they slow down for yellow lights and to avoid rear-ending other cars. Each car stays in the proper lane and makes legal turns. I added safe right turns on red when no other cars are traveling in that lane. I implemented collision detection, though the AI is pretty good about not colliding with other cars as long as traffic lights are obeyed. Cars always stay on the roads, so I don't need to worry about collisions with traffic lights or buildings. Collisions between two cars do occasionally happen, usually because a car can't stop fast enough or other cars are blocking the intersection. I found out the hard way that cars starting to pull out into the intersection can collide with cars that entered the intersection in another direction just before the light turned red. That's why yellow lights are needed!

It's been infuriatingly difficult to keep the cars from colliding or getting stuck in all cases. Everything runs pretty smoothly in most cases, but when I add too many cars, things start to break down. One of the problems is that traffic can back up and cars will stop behind other cars in the middle of an intersection. Maybe they should stop early to avoid blocking cross traffic, if I could find some way to efficiently implement that. However, I think it's reasonable to allow them to stop in the intersection. After all, that happens with real drivers. I take Uber home from work each day. We often make a left turn at a big intersection outside my office. If I don't leave late enough, traffic is backed up and cars are often stopped in the intersection, blocking our way.

I changed the car logic to make cars wait at the light if the intersection is blocked in front of them, even if the light is green. This fixes the problem in most cases, but can result in gridlock when the density of cars in one area is too high. There are situations where two long lines of cars going in opposite directions end in a car trying to make a left turn. The turn is blocked by the line of cars in the other direction, so all the cars just sit there. I think adding a left turn lane would help, though that requires using a set of road textures that has two lanes in each direction. I suppose this is why so many real roads have left turn lanes.

This fix doesn't quite work in all cases. If the intersection is clear, and cars start to pull out, they can become backed up at the next traffic light. One car may be stopped mid-turn, while the car behind it has already started to pull out into the intersection.  The car behind will collide with the car in front if the front car has crossed the halfway point and is considered to now be on the other (new) road. If I make the back car wait, the light can change to red while it's waiting, and cars coming from the other direction can collide with its front end. It's technically not completely in the intersection, and the intersection hasn't yet been flagged as blocked. The real solution seems to require some amount of planning ahead and anticipating problems, which is easy for people but difficult (and slow) for computers. Now I know how self driving cars must feel.

Another problem is that traffic tends to build up at the intersections on the connector roads between cities. Cars are biased toward taking these roads, even though these roads are still single lane. They can get pretty packed with cars. They do have twice the speed limit, but this only allows the cars to pile up faster. Again, the problem is mostly due to that one car waiting to make a left turn at the intersection that leads into the city. It would probably help if the connector road intersection was 4-way rather than a 3-way T junction. I adjusted the traffic light pattern to assign longer times to the incoming direction of that intersection. This helps with the backup at connector road intersections, while making the gridlock worse for cars trying to cross through that intersection from within the city. Oh well, it's good enough for now.

I'm sure you're all thinking about how bad those cube cars look. I was thinking the same thing! Yes, I need better 3D models. I don't have any 3D modeling tools, and I wouldn't know how to use them anyway, so it's off to Google to find some free 3D car models. My first attempt at using 3D models for cars didn't turn out as I expected. Some (most?) 3D modeling tools have the ground as the XZ plane and Y as up. 3DWorld uses XY for the ground and Z for up. I found this easier because I could use 2D math library classes that operated in XY for the terrain, then extend them upward by adding a Z component. I guess I need to add a 90 degree rotation to fix this. The screenshot below is too silly for me to leave out.

First attempt at adding real 3D models for cars. Something's not quite right about these cars. Hmm.

Also note that the cars are different sizes. This seemed fine with cube cars, but looks odd when they're all the same complex 3D model. I've made them all the same size in the remaining screenshots.

This first sports car model is pretty good quality. I downloaded the model in .obj format from the McGuire Computer Graphics Archive. It's way higher detail than I need though, especially considering it has a full interior and engine that can't even be seen from the outside. That's fine, I was able to use the same level of detail (LOD) trick I used with the 10,000 museum objects. 10K cars, 10K museums, it's all the same. See, I knew I could find a real use for that model LOD/instancing system. The one problem with this model is that some of the triangles on the top rear of the car have bad normals that face inward instead of outward, making them appear too dark in the sun. I assume it's a problem with the triangle vertex winding order (CW vs. CCW) in the .obj file. It's not something I can easily fix, so I'll have to live with it. You may notice this in some of the images below.

These models aren't perfect. The wheels don't actually rotate while the car is moving, and don't turn when the car is turning. This makes cars appear a bit odd when they turn. Also, the transition from 3D models to a pair of cubes is noticeable in distant cars. This problem also isn't easy to fix, unless I'm willing to reduce the number of cars to something like 1000.

Speaking of images, here's a night scene where the sports cars have been colored and placed in the correct orientation. I disabled the buildings so that the distant headlights are easier to see.

Multi-colored sports cars in the city at night. Buildings have been disabled to make the headlights easier to see.

These look much better than the cube cars, even with the dark triangles. Headlights are on because it's night time. The glow of the bright lights has a nice effect. I wish I could add spotlights on the road, but I haven't figured out how to do this yet. It's difficult to add support for thousands of moving spotlights in a scene with this large a draw distance in a forward rendering engine. Here's another screenshot, this time during the day, and with buildings enabled.

City scene with sports cars on the roads during daytime.

I think we need more variety of cars. Back off to Google to find more 3D models... Okay, this looks better. Let's see, there are now six models: a police car, a white sedan, and three more exotic sports cars. I guess this is a city full of rich kids, and the police are needed to keep them under control. This is the set of six models out of the initial ~15 that passed the first quality filter. Some of these cars have minor problems with textures or normals, but are otherwise okay. And yes, if you look closely, the blue sports cars do have "Hot Wheels" painted on their hoods.

The cars come in various sizes and aspect ratios. I'm scaling them down to the same average size, but preserving the aspect ratio of the models. I use the same headlight, brake light, and turn signal locations for all models, based on the edges of the model's bounding cube. It makes drawing simpler, but the lights are sometimes outside of the car's bounds (especially for cars with curved front/read ends), or too high/low. I'll add several more screenshots below.

Police car making a left turn, viewed from above.

Various screenshots of cars driving on city roads and traversing intersections. There's still a lot of empty space between buildings that needs to be filled.

If you look carefully, distant cars are still drawn using cubes. I don't find this too distracting; at least they're colored to match the car models. Note that there are no car shadows, though traffic lights do have shadows. Cars can receive shadows, but don't cast shadows. This is difficult to do in an efficient way, considering the large number of dynamic models. If they were simple cubes like before, I could add their shadows pretty easily. Unfortunately, cube shadows look horrible with curved 3D models, and it's just too expensive to draw the entire 3D model of every car every frame for every shadow map. So for now I've left the shadows out. Maybe I can go back later and at least add simple dark areas under the cars due to ambient occlusion.

I really need to fill that empty space between buildings and roads with something. What can go here? Maybe parking lots? I could probably put some parked cars there, if I could find a good way to connect those areas to the roads.

Here is a different view showing cars on a long connector road, with a city in the background. The models are drawn tilted to match the slope of the road.

Cars driving on a long connector road between two cities, with a city in the distance.

This is another night time image, showing off car headlights and the glow of traffic lights in the dark. I hope the image isn't too dark to see. The sun and moon are both down so that the only lights are the faint ambient illumination, the car lights, and the traffic lights.

Cars of various types in a city at night. Hopefully this image isn't too dark.

Here I've increased the number of cars from 4,000 to 10,000 and removed the buildings to improve visibility. There are a ton of car models drawn, but they use LOD and this allows me to still get around 60 FPS. This also creates a lot of traffic congestion and related problems. This is probably too many cars to have in the current scene.

This is what you get when increasing the number of cars from 4,000 to 10,000. Buildings have been disabled again. I still get around 60 FPS in this case.

I recorded a video of cars in action, stopping at traffic lights and making smooth turns. You can see that everything works just as it does in the real world. Note that the video is sped up by 2x to make it shorter.

There are a lot of future work items for this post:
  • Add support for other vehicles such as trucks, buses, motorcycles, etc. (which requires finding new 3D models)
  • Fix the remaining problems with car collisions and traffic gridlock by improving the AI.
  • Add car shadows, or at least ambient occlusion.
  • Add spotlights for car headlights and make them shine on the roads, buildings, and other cars.
  • Add more city decorations: street signs, streetlights, benches, parking lots, bridges, etc.
  • Add parked cars as scenery.
  • Figure out how to make the car wheels actually turn.
  • Add support for multi-lane roads, and use a dedicated left turn lane to improve traffic.
I'm not sure how much of this I'll actually do, if any. This system works better than I had originally planned, given the amount of time and effort I spent on it. There are so many possible things I could be working on, considering the broader problem of populating the terrain with interesting content.

Bonus Update: I added ambient occlusion under cars using a single black quad and an opacity map texture with radial falloff.

Cars with ambient occlusion producing dark areas underneath.

Monday, February 26, 2018

Epic Fails in City Road Generation

This is a follow-up to my previous post on city generation where I show some of the fun bugs I had in the code and other failed attempts at placing roads. This first set shows off some actual bugs, though I had to go back and re-break the code in order to take these screenshots. Keep in mind that I did, in fact, encounter these problems when coding this stuff up. Roads aren't easy!

Here we have a road connecting two cities that are on opposite sides of this city shown in the screenshot. It was some problem with the tracking of which city the road is supposed to connect to. Roads are placed after city plots, so they have final say in what the terrain height should be.

But sir, you told me you wanted an express lane THROUGH the city!

This one was a failed intersection test between two connector roads. I was checking for overlap in all three dimensions (x, y, z). These roads don't overlap in z, but there's still an intersection. Just because they don't overlap in z doesn't mean they're okay! Only dimensions x and y should be checked. I had to print all sorts of debug text to the terminal to figure this one out. Doh!

We ran over budget constructing all these elevated roadways, and we didn't have the funds to dig the tunnel. We'll just have to put it on CA Proposition 39 in June for voter approval of a $9 parcel tax.

This is some problem with setting the height of the small 90-degree bend section at the wrong place in the control flow. The two 90-degree straight segments cause some interference here, and the bend has to smooth it over in a postprocessing pass. It took a while to come up with a fix for this one. I had to make several attempts before I got something that fixed all variants of this problem.

If you're not going to add a guard rail, can you at least post a warning sign? On second though, this might be good for drift racing!

Here's what happens when the slope direction Boolean is inverted. A number of different variables are XOR-ed together here to determine the sign of the slope of each road segment. It took a lot of trial-and-error to come up with the right conditionals. Maybe I shouldn't have been so greedy, trying to pack this info into a single byte in memory for each road segment. Ah well, I got it working in the end.

"Speed Bumps"

In this case, the two roads don't overlap, but their sloped boundaries do. The road on the right is created first. The road on the left is going to a higher altitude destination city. It creates a sharp cliff that falls to the right, then the smoothing pass smooths it out - right on top of the other road. The fix is to expand the road by its smoothing border before checking for intersections with other roads. It's a good change anyway, as it spaces roads out better. Bonus: the texture is all squished in that road segment in the lower left corner between the two intersections.

I'll take the high road and you take the low road. Sucker.

A similar problem can occur with cities, since they also have smoothing borders. I had to fix the problem in the same way as roads, by padding city bounding cubes by the smoothing distance prior to checking for intersections.

Someone forgot to build a retaining wall. Oops. I guess the 5th floor tenants get their backyard gardens after all.

I'm not sure exactly what caused steep roads to dip under the terrain. It's probably a floating-point rounding issue when converting to/from integer grid points/texels, or maybe during the 16-bit height <=> floating-point value calculation. One fix is to shift the road up in Z by an amount equal to (dz/dx)*pixel_size_in_x. I'm not sure if this is the correct solution as it causes steep roads to "float" above the terrain, but it's one of the only things I tried that works. As long as the steepness of the road is limited, it's not too noticeable.


At one point early in road development, I had a problem where the grass and roads were using two different coordinate systems. Grass is owned by the terrain tiles and is in tile-relative coordinates, which change as the player moves. Roads, cities, and buildings are always in constant global coordinates so that their vertex data can be stored on the GPU once and reused. A bit of math was required to fix this problem.

Can someone send a landscaping crew out to cut the grass growing on I-101? Maybe that will keep the cows from grazing in the middle of the road.

These next four screenshots weren't actual problems I ran into, but they still look interesting. This is the insanity resulting from disabling the connector road intersection tests so that they can go anywhere they want without restrictions.

Connecting every city directly to every other city is now possible, but not a good idea:

Ready for some off-road action? I think the engineer was off his meds when designing this.

A road was routed underneath this city. Presumably, it connects together two lower elevation cities on opposite sides of this one. I can't really tell in all the chaos. Some buildings have decided that they want to use the mesh height from the road rather than the mesh height for the rest of the city.

To protect against nuclear attacks, this shopping mall was built under the city. Or maybe it's a secret spy lair (with a big road leading up to it)?

This is the same problem, but inverted. Here the road connects together two higher elevation cities, dragging some buildings up with it. I could fix both of these issues by using the city elevation for buildings rather than terrain elevation. But this is just an experiment; this situation shouldn't come up, so why bother trying to handle it?

Now guests on every floor can have a room with a view! I just hope the kids don't decide to roll tires down that hill.

In this next case, the upper road was created first, and the lower roads were created later. Once a road is routed, it's done. The lower roads will modify the height of the terrain, but not the height of the upper road. In this particular case, it looks like a pretty cool bridge, though it needs some actual structure to be more realistic. Maybe I'll try to come up with a way to make this work. We still need to get rid of that road in the very front though.

A marvel of modern engineering, or a waste of our tax dollars?

That's all. I'll spare you the dozen or so screenshots of misaligned and incorrectly oriented road textures, which was another big time sink.