January 21, 2016 By: David Tse
I've been working on some really important stuff since the last update. You may think generating realistic roads is a challenge, but it's nothing compared to trying to get them to cross each other in a believable way. There are many different types of roads and every combination of intersection needs to be handled differently. Then on top of that some roads can intersect at arbitrary angles, different elevations, and at any part of the terrain. While there is still much more to be done handling these intersections, I've made some significant progress.
I should also note that my laptop broke right before I was going to post this. I'm currently not home and I only had my laptop to work on, so all the screenshots I had planed to use for this post are stuck on there. Luckily I'll be home on Saturday and ordered an NVMe reader to get all the stuff off the laptop's SSD. So there will be screenshots that better describe what I'm talking about then. Also I wrote and posted this using iPad so there may be some issues.
The first thing that I had to do was determine where these intersections were happening and between what types of roads they were happening between. For city roads this is fairly simple because I'm growing roads out from a start point so I know when a road intersects another road because that's part of the growth algorithm. For interstates I had to split them up into temporary collision chunks and just do basic collision tests to get all the intersections.
Old screenshot of circles around the intersection in generation stage.
All of these intersections are expressed as a 0.0 - 1.0 percentage along the spline for reasons that will be made more apparent later on. So a 0.75 indicates the road spline intersected another road after traveling 75% of the way down the spline.
The problem is this spline can be really large and will need to be split up into world chunks for the game to stream in. This means that when we're splitting up the splines for the export chunks we have to grab the intersection percentage then re-normalize the 0.0-1.0 intersection value to fit the new adjusted smaller spline all while taking into account the buffer spline points at the beginning and end of the spline. It was a huge pain in the ass to get this working and all the intersections to perfectly line up once loaded in-game. It took a little while, but it all works now.
Before I go into the actual intersection handling and mesh creation let me take a step back and talk about one really important feature I did that is not exactly related to intersections. When we place roads we can't just put them on top of the terrain and hope for the best. Even the most flat terrain will clip through the road.
When roads are placed they need to completely flatten everything under them and cut through any bumps or hills. Then terrain that is progressively further away from the road is smoothly flattened less and less until it's back at the original terrain value. This can be tweaked in a number of different ways depending on how smooth you want the flattening transition to be, how closely you want to road to adhere to the terrain, or how smooth you want the Actual road to be.
Old screenshot of terrain flattening under a road. Notice how the bumps extend through the road.
The way this works is we take a sample at every point along the road mesh to get the pre-deformed terrain height. Then that height is extended perpendicular to the road in both directions to flatten the terrain. The problem is if we are taking a lot of samples, because we want a decently tessellated road mesh, the road gets really bumpy because we're very closely following the underlying terrain which is usually bumpy. To smooth this out we can do x number of smoothing passes that just take the average heights. Then like I said before all this stuff can be tweaked depending on the road.
Same road and terrain as last screenshot, but this time with the road smoothing.
Once we get the desired terrain adjustment for a road we blend it into the road map texture. Every active chunk gets a road map from a universal pool. This creates a smooth map at chunk stream time that the terrain can quickly sample and reuse for all the different LODs. This theoretically could be done offline, but the amount of memory to store a full texture for every chunk would be insane. Because the chunk sizes are 512x512m and the world size right now is set to 1,000,000x1,000,000m. This road map will also be used for flattening the terrain for building foundations. Should probably change the name to city foundation map or something.
The last little thing I did with the terrain was to get the ground to start at about the same height as sidewalk. Something you expect in real life. To do this I just pushed down the entire road into the terrain and then lowered the terrain even more just where the actual road is. This way it looks like the road is sinking into the terrain and the top of the sidewalk is about level with the terrain.
Arbitrary Intersection Mesh Placement
Reference from google earth of what the goal is for the highway overpass with the arbitrary mesh placement.
One way to handle intersections is to place a pre-made mesh at the intersection point that perfectly lines up the connecting road segments. This is useful where roads intersect at predetermined angles. For example a driveway connecting at 90 degrees with a neighborhood road. Or when a highway passes over a road we use this system to place the bridge mesh. This system will also be used to add road marking decals and anything else that needs to be placed along the road like guard rails.
Model I made to test the spline mesh placement.
This system can place the mesh at any arbitrary point along the spline given a percentage distance along the spline. This is why we store intersections as percentages traveled instead of just points in the world. Think of it like a train moving along the tracks. We can slide a mesh up and down the road spline and it will conform to it perfectly.
Working spline mesh placement of highway overpass. This is old screenshot before I figured out how to blend the terrain flattening for multiple roads.
Custom Intersection Mesh Creation
The next way we handle intersections is by automatically creating a custom mesh to connect the roads. While it is possible to create a perfect mesh that connects the roads, I've decided to go with a bit more of a hacky solution that is much simpler.
So when two roads intersect at an arbitrary angle the first thing we do is get the elevation at the intersection point. Then we set the elevation of all the road points that overlap to that intersection elevation. Then we smoothly fade back to the original road elevation as we move away from the intersection. Because the roads are now smoothly meeting at exactly the same elevation we already created the main road intersection mesh!
Only wireframe screenshot I have. Shows how the triangles just overlap.
The way this works is, we render the roads using world space texture coordinates. When you do that can't even see that the road triangles overlap at all because every point in both roads are sampling the exact same color. This does mean that roads need to use a simple tileable asphalt texture and we lose the road markings and any directional detail/wear.
Same screenshot not in wireframe. Notice how you can't see where any of the triangles overlap. You can also see where the sidewalk corner meshed are needed and how the intersection elevation change still needed to be smoothed out.
To fix this the plan is to use a layer of decal meshes that blend into the road. So we can get lane markings and directional details on straight roads then when we get to intersections we can add all the road markings you expect like turn arrows and stop lines. I think this is the best solution even if it's not the most optimal/efficient. Perfect looking intersections, realistic road markings/details, simple algorithm, and only a few wasted triangles where roads overlap.
High level view of everything working. You can also see the terrain smoothing pretty well in this one.
Now the actual road is intersecting just fine, but the sidewalk and anything else traveling alongside the road needs to be connected properly. To do this we need to stop the side mesh at the same point we start flattening the road at the intersection. Then we create a new corner spline at the 4 or 2 corner points depending if it's a 4 way crossing or T intersection.
Close up of the sidewalk corner meshes and everything coming together. Still has some texture UV issues on sidewalk.
Once we have this spline we just extrude the sidewalk mesh along this new spline connecting the two different road sidewalks. We also need to extrude a standard road mesh along this spline to make sure the road extends all the way to the sidewalk corners. This corner spline can also be used to place an arbitrary mesh using the system I mentioned before. So we can create a special corner sidewalk that has a ramp or a different look if we want.
All of this road stuff is starting to get me really excited, and I can't wait to start working on what's next! That next step is to generate some neighborhoods and start placing houses! Now that the holidays are over and there will be much less going on the next update will actually be in 3-4 weeks and will hopefully have some buildings to explore.