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 to 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.

Sunday, February 25, 2018

Cities With Roads

It's been over a month since my last post. I had been working on fixing the ship AI for universe mode planet colonization, which required me to constantly run simulations on my PC. That topic doesn't make for a very interesting blog post because it's too technical and there aren't any good screenshots. However, in the past two weeks I've switched back to working on terrain and cities. This time I'm trying to combine the work I did with city generation and eroded terrain to create an environment that's a mix of natural and man-made structures. The end goal of the 3DWorld project is to generate a procedural universe that the player can seamlessly explore, from galaxies all the way down to individual trees and buildings. There's still so much work to do. The new addition to 3DWorld is city road networks.

I'm starting with the same 7Kx7K heightmap output from the erosion process described in a previous post. I exported it to a 65MB, 16-bit PNG image so that I can reload it without redoing the erosion simulation. This scene is huge, around 14km on a side. The cities are currently all placed in the relatively flat area in the bottom center of the map, between the ocean to the south and the mountain range to the north. Remember that this is an island, even though there's very little water in the screenshots below.

The steps I'm using to generate and connect cities are:
  1. Determine city location(s) by looking for relatively flat areas of the terrain, away from water
  2. Flatten a rectangular area of terrain to the city elevation (avg terrain elevation)
  3. Select the location of X and Y roads based on user-specified parameters
  4. Split roads into road segments, 2/3/4 way intersections, and building plots in between
  5. Create road networks that connect all cities (straight roads and roads with one 90-deg bend)
  6. Smooth the mesh around roads and intersections so that they're slightly above the terrain
  7. Generate procedural buildings and place them into the city plots
Items 1-6 are described here. Procedural building generation was explained in some previous blog posts and won't be discussed again. Look here and here for reference. All of these steps take less than one second of runtime: heightmap texture <=> floating-point array (330ms on 4 cores/8 threads), road network generation (70ms), and building generation/placement (185ms). This is much faster than the 2.1s actually spent loading the heightmap image as a texture.

City generation first reads a configuration file that specifies the size and number of cities, road length/width/spacing, max slope, terrain smoothing parameters, building parameters, etc. In total, there are 12 city parameters and 45 building generation parameters. These can all be edited by the user to customize city generation.

The first procedural generation step is selecting a site for each city. A few thousand locations are randomly chosen from the user-selected region of the heightmap, and the best one is selected. Locations are scored based on the RMS height difference between the average height and each height value around the perimeter of the city. I chose to use the perimeter rather than the full site area because it's more efficient to compute. Its unlikely for the player to notice if the city happens to flatten an entire hill or fill an entire valley anyway. It's more noticeable when there are steep slopes at the edges of the city. Each site must also not overlap a previous city, and must contain no water. I could have it fill in the water with land, but I do like to keep all of those small rivers and lakes.

Once the best site has been selected, that area is flattened to an elevation equal to the average elevation around the city perimeter. Note that the heightmap is normally stored as 16-bit integer values, but is converted to/from a floating-point array for the purposes of city generation. This conversion process takes about half the total city generation time. A boundary region is used to gradually transition from the city's elevation to the original terrain elevation to avoid sharp cliffs at the edge of the city. A smoothstep function is used to prevent slope discontinuities that would otherwise be obvious and appear unnatural to the player. Roads are flattened and smoothed in a similar way, but with a more complex function that handles fixed (but nonzero) slopes. The flattening step also replaces any grass inside the city perimeter with dirt.

Roads are placed on a uniform grid that exactly fills the city area, and are oriented in both the X (east-west) and Y (north-south) directions. The config file defines road width and spacing values. 4-way intersections are created in the interior of the city, 3-way intersections along the edges, and 2-way intersections at the corners. The space between roads is filled with a tiled concrete sidewalk texture that matches the border of the road and intersection textures. Buildings will be placed in these areas in the final step.

Intersections, plots, and road segments between intersections are sorted into the terrain tiles that contain their center points for drawing. This also serves as a useful spatial subdivision for later collision queries. For each visible tile, the city objects associated with it are drawn using the tile's shadow maps. This system is meant to scale to very large maps with potentially hundreds of cities, where only a subset of the cities is visible at any one time. I've tested it with 49K buildings and 90K road segments and still get 136 FPS (frames per second).

The screenshot below shows a pair of adjacent procedurally generated cities with roads and buildings. Note that the buildings all cast correct shadows on the roads and sidewalks. At this point in development, the cities haven't been connected.

Two adjacent cities with roads and 1268 buildings, viewed from above.

The player is free to walk around the city. There are no vehicles yet, but it's possible to walk very fast using the "R" key. The buildings have player collision detection enabled. The terrain can be edited in realtime as well, but the buildings and roads won't move with the terrain height like the vegetation does. Below is a "street view" image showing another city in the background. To give you a sense of the terrain resolution relative to the objects, a city road is slightly larger than 4 terrain texels wide.

View of the road bend at the edge of one city, with another city in the distance.

There are some minor issues visible in this screenshot that I might go back and try to fix later. There are texture seams between some of the intersections and the roads. It might help to rotate or mirror the textures to line them up better. I could look for a different set of road textures, but this set was the best I could find in my initial searching for free textures.

You can see some grass sticking up through the sidewalk at the edge of the city. This has been fixed already. Grass and plants are 5-10x larger than they should be compared to other city elements, and trees are 2-4x larger. I'm not sure if I should make the vegetation smaller, or make the buildings larger. If I make the vegetation smaller, then I have to generate a whole lot more of it to fill the scene, which will hurt scene creation time and frame rate. If I make buildings larger, then they don't look right against the mountains, lakes, and rivers. I'll leave it the way it is for now. Maybe I'll do something about it later.

Here's a shot where I turn the camera around to view the mountains next to the city. Everything shown here is real geometry. The player can walk into the mountains seamlessly.

Road at edge of city with mountains to the left and buildings to the right.

This is what the city footprint looks like without the buildings. The grid of roads can more easily be seen, along with the sidewalk textured plots where buildings will be placed. While cities are level, roads can be sloped to connect two cities of different elevations. The road that cuts through the hills in the back left is sloped upward. I have pine trees enabled since the scale problem isn't as obvious without the buildings. Note that the vegetation placement algorithm will avoid placing grass, trees, plants, and other scenery objects over the city and connector roads. The bounding cubes of cities and roads are used as blockers for scenery placement.

City plots, local roads, and connector roads shown without the buildings.

The image below shows how several nearby cities have been connected by roads. In this example, I configured the road router to connect the first (center) city to each of the other cities with a single straight road. Right now I only have road textures with a single lane in each direction. I'm not sure if I want to add another set of textures for multi-lane highways between cities. I've disabled fog to make the distant city in the back more visible.

Four connected square cities shown without fog or trees to better view the road network.

Here is another screenshot showing how two cities are connected by a road through the hills. The connection algorithm chose to place the road near the edge of the city to minimize the amount of material added/removed (required terrain height change) for placing a straight road. If the road was placed more toward the center of the city, it would have cut deeper into the hills. I like how the pine trees and terrain cast shadows on the roads. These shadows will move with the position of the sun.

Connector road cut into a wooded hillside. This was the location that required the min amount of height change.

This next image shows a view of the downtown area. The camera is on a road in the middle of a city, looking down the length of the road. The large office towers look good here, and seem to be the correct scale relative to the road. Now all I need to add are streetlights, traffic lights, signs, and maybe even moving cars. It would look better if I could fill in all those small empty spaces between the buildings. These spaces are too small to fit additional buildings.

Street view inside a city. It would look better with streetlights, signs, and benches.

Here's a screenshot taken from the roof of a building. Buildings don't have stairs (or any interior), but I can use flight mode to get up here. Once I'm on the roof, I can walk around on it. There are 680 buildings in this city. Trees and mountains can be seen in the distance. Note that this screenshot, and all the others, are running at around 200 FPS.

Rooftop view from a tall skyscraper. Yes, the player can walk around on top of these.

After creating all the images above, I went back and did another pass at connector roads. First, I made the cities smaller so that I could place more of them in the same view area. I also added config options for size ranges of cities, which means that cities can now be different sizes and non-square.

Next, I changed the routing algorithm to try to connect every city to every other city. This isn't possible in general without bridges or tunnels, neither of which have been implemented. I had to add collision detection for roads colliding with the wrong city or other connector roads. If no valid path is found after 50 random attempts, the router gives up and doesn't connect that particular pair of cities. I could have added 4-way intersections in locations where two connector roads crossed, but I decided not to do that. That's a lot of complexity to add, and I was worried it would clutter up the scene with too many roads and intersections. Plus it's difficult to get the elevations of the roads to match at the intersection. I might go back and add a config option for that later.

Finally, I added support for connector roads with a single 90-degree bend. It would have looked more natural to use roads that were curved or had multiple smaller bends, but there are several problems with that approach:
  • My texture set only includes textures for 90-degree bends, and I haven't found any good curved/shallow bend road textures online that will tile with straight road textures.
  • It's not easy to connect non-rectangular roads together. Simple quads don't work well. They would either produce texture distortion/shear, or would leave gaps in the mesh.
  • The math is much more complex, and slower. It's difficult to determine intersections.
  • Flattening the terrain heightmap is both inefficient and prone to aliasing issues. Straight, axis aligned roads are simple rectangles in texture space, while arbitrary angle roads require complex line drawing algorithms to move in texture space.
I haven't attempted this yet, but it's possible future work. Even getting this far took me a few late nights of programming. For now we just get crazy right angle roads like this.

Small cities connected together by a network of straight and right angle roads.

These roads are all straight and have constant slopes. This means they tend to cut through mountains, creating deep valleys. They also create strange land bridges across low lying areas between two higher elevation cities. This doesn't look very practical. What where those civil engineers thinking! I'll bet these would make for some good runways though, if I decide to add an airport to my map. And as long as the plane can take off before the 90 degree bend. And clear those steep mountains.

Here's another shot. See the mountain pass the algorithm carved in the front right and those two elevated roadways on the left in the distance. The cities and buildings look pretty good though.

Several non-square cities of various sizes connected by some crazy long roads.

I decided that these long straight segments themselves were okay, but the fixed slope was not. I added a segment_length config option to split the connector roads up into multiple runs that could have their own slopes. The elevations of the intermediate points between segments were set equal to the terrain height so that roads roughly followed terrain. This removed the deep valleys and land bridges, but added some very steep road segments. Roads now went up the mountain and down the other side instead of cutting straight through it. This makes sense from an engineering perspective, at least for lightly traveled roads where vehicles can be expected to make it up and down the steep parts.

I decided that a slope limit was needed to prevent very steep segments. I chose a rise-over-run value of 0.3, which removed the small number of very steep segments while keeping the others. In cases where the midpoint between two road segments generated a slope that was too high on one side, the midpoint was moved vertically by either shifting the terrain up or down to try and straighten the segments out in Z (up). In the worst case, the road was converted back into a single segment with constant slope, assuming the overall slope (city elevation difference divided by city horizontal distance) was under the limit. These changes produced a road network as shown below.

Roads split into segments that follow the contour of the terrain. Road segments with slopes >0.3 were rejected. Fog disabled.

The road that's just to the left of center had too high of a slope to go over the hill, so it cut through the hill instead. There are still some strange paths, such as that one in the very back that goes up and down an invisible mountain. Note that the mountain is only invisible because I've turned the fog off and the draw distance of roads is larger than the draw distance of terrain. Overall, the results look acceptable, and are much more practical than the fixed slope roads. I'll keep this set of options for now.

I'll throw in an overhead map image so you can get an idea of what this looks like as terrain. Water is blue (of course), low areas are brown, mid elevation areas are green, and mountains are gray/white. Cities are same-color rectangles. For example, that large greenish-brown square in the bottom left is a low elevation city. Roads are thin horizontal or vertical lines of similar colored pixels. Some roads are sloped, giving them color gradients. Overall, the placement algorithm has done a pretty good job avoiding the mountains and deep valleys. The algorithm has successfully avoided placing cities and roads over water, as expected.

Overhead map view of center of heightmap showing how city plots and connector roads have changed height values.

City generation has been a pretty fun and interesting topic. I definitely want to continue working on it. Results seem pretty good so far, but there's so much more work to do here. Of course, this system is already getting complex, with over 1000 lines of source code. You'll probably see at least one more blog post on this topic. To summarize, future work items include:
  • Addition of detail objects within the city (lights, signs, benches, cars, etc.)
  • More realistic roads with more/shallower bends, more gradual slopes, less terrain editing.
  • Smarter building placement that adds larger buildings to the city interior. (Zoning?)
  • Fixing of incorrect size scale for buildings vs. vegetation.
  • Fixing of texture seams for different types of road sections.
  • Addition of normal maps and detail textures for roads and sidewalks.
  • Building interiors! Well, no, probably not any time soon.
  • ... But maybe I can add windows and doors to some of those brick and stone buildings.
I definitely think I'm going to work on cars next. It would be awesome to have tiny cars and trucks moving about on the roads within and between cities.

Tuesday, January 16, 2018

Fields of Grass to the Horizon

This post is an update on the current state of 3DWorld's tiled terrain grass rendering. I've shown infinite fields of grass in a previous post, but since then I've made some graphical improvements. For example, I'm now using GPU tessellation shaders to generate curved grass blades close to the player camera.

Near to far levels of detail include (ordered closer to further):
  1. Individual curved grass blades formed by tessellating the original triangle into many polygons
  2. Single triangle, textured grass blades that move in the wind
  3. Single triangle, untextured green grass blades with no wind
  4. Larger triangles formed from recursively merging two adjacent grass blades into a single triangle where area = sum(areas) and color = average(colors)
  5. Coarse triangles that translate down into the terrain mesh with distance until they disappear
  6. Simple grass texture applied to the 3D mesh surface consisting mostly of green color + noise
The tessellation, triangle merging, and height translation all happen smoothly as continuous functions over distance to prevent noticeable popping artifacts. The only visual transition that I can see is a small amount of flickering/noise when grass blades disappear under the mesh in the distance, when viewed from high above the ground. I'm not sure what causes this. Maybe it's due to depth buffer Z-fighting. The textured => untextured and wind => no wind transitions are very difficult to spot. The tessellation changes and triangle merging are nearly invisible.

A set of 32 grass tiles is generated, and random tiles are selected for use across the terrain. The vertex shader calculates the z-value (height) of each grass blade from the heightmap textures. All vertex data for all levels of detail are stored on the GPU for efficiency. Hardware instancing is used to render all instances of each of the 32 grass tiles in a single draw call.

Here is an example video where I use the camera speed modifier keys to zoom in and out on the grass. The actual rendering is much sharper; video compression has made the grass somewhat blurry. I've disabled the trees, plants, and flowers in the config.txt file to make the grass stand out more and avoid distractions. Without the overhead of video compression, this normally runs at around 300 FPS (frames per second).

As you can see, grass has a nearly seamless transition from a distance of inches to miles. The result is a lush green field that stretches out to the horizon and scrolls to follow the player camera. It's possible to have the entire terrain draw as grass at 150-200 FPS.

Note that the grass colored ground texture is always used. This is here to fill in the space between the grass so that the blades don't need to be packed together as densely to achieve a thick looking cover. The texture and grass blades use the same average colors (across texels) so that they blend together better in the distance. They also use the same normals and shader lighting calculations. To make this work, grass normals are derived from the terrain mesh normals.

Here is a series of images captured of grass, from close up to far away. There are some scattered areas of sand and dirt with lower grass density to break up the scene and add more variety. These can be seen in the last two images. Again, non-grass vegetation and other scenery has been disabled for these screenshots.

The only problem I see with this approach is the tiling artifacts of the distant grass texture. Tiling is most noticeable in the final two images. I spent some time trying to fix this, but never really succeeded. If I use a highly detailed texture, it looks too repetitive. If I use a low contrast green texture, it looks too plain and uninteresting. If I transition between texture scales, the effect is noticeable, and it ruins the immersion. I was able to get away with that last texture scale trick with water because it was moving, but apparently not with grass. Interestingly, this isn't as much of a problem with the rock and snow textures. I wonder what's different about them?