Monday, September 17, 2018

Car + City Traffic Revisited

Update on City Cars and Traffic

I've made some progress on city traffic since my previous post from two weeks ago. I left off trying to solve problems related to traffic and gridlock, mostly caused by stopped cars blocking intersections near roads connecting to adjacent cities. Here's an example screenshot from two weeks ago showing the problem.

Original 3-way connector road intersection with gridlock due to short roads and too many left turns.

The center of the city is off toward the upper left corner of the image. The majority of cars entering from the connector road on the right make right turns, then left turns. The first right turn takes them onto the tiny road segment with the two orange cars that's only long enough to hold three or four cars. Once that lane is full from cars turning right, all it takes is one car coming from the bottom of the screen and going straight to block that intersection. In this case, it's the red car causing the problem. Once the red car is there, the blue car waiting to make a left turn in the opposite lane will be stuck there forever. The red car can't move until the brown car at the intersection makes its left, but it's waiting on the light gray car, which is waiting on the blue car. The problem is a circular loop of blocked left turns.

One hack that will at least guarantee progress is to allow the brown or blue cars to give up and go straight instead. However, this ultimately won't solve the problem, because eventually these cars are going to get back here trying to reach their destination and will get stuck again. Cars arrive at this intersection faster than cars can give up making left turns and go straight. All this does is delay the problem for a few minutes.

My solution is to fix the intersection so that it's a proper 4-way connection. Now instead of turning right then left, most of the cars go straight. There's no turning, so cars can't get stuck in the intersection mid-turn. Also, this removes the short road segment with limited car capacity. Here is what this same area looks like if we join the connector road to an existing 3-way intersection rather than inserting a new one.

Improved traffic flow using 4-way connector road intersections. Most cars go straight rather than turning.

Everything is going smoothy here. Actually, there are fewer cars than I expect at this location. I wonder why that is? I'll have to get back to that later...

I let the cars run in the background while I went off and did other things. The first time I tried this is crashed after a while, but I think I fixed the problem. Here is what the central city looks like after about 20 minutes of simulation.

Half of the cars have accumulated in the central city, which has roads connecting it to the other seven cities.

It looks like about 40% of the total cars have accumulated in the central city, which has roads connecting it to each of the other 7 cities. Aha! This is why there were so few cars at that other intersection we looked at in the last image. There are so many cars here that the streets are full and none of them can move. This is a new problem for me. I've never gotten this far before, because traffic gridlock would prevent the distribution of cars from ever reaching this state.

Here is the overhead map of the connected cities. The biggest problems occur in that square city to the right of center where the red dot is. The red dot is the player camera position, and it's near where the screenshot above was taken. Those three connector roads very close together in the bottom left corner of the city near the camera are no good for traffic. Also note that some of the connector roads are 4-way intersections, while others remain 3-way intersections.

Top view of cities showing connector roads (gray), bridges (white), and tunnels (brown).

This problem can't be solved by micro-scale changes such as having cars avoid blocking intersections. I'm not sure if it can be fixed by adding more road capacity (lanes). It's possible the only real solution is improvements to car navigation.

Some people have suggested using dynamic path finding where cars try to avoid traffic even if it results in longer travel distances. Read the comments in the previous blog post. This could work. I started with an easier approach: Don't choose destination cities with high traffic density. I modified each city to calculate the total length of all contained roads, and to also track the number of cars within the city each frame. I estimate traffic density as number_of_cars/total_road_length. When it comes time to choose a new destination city, cars will select cities with lower traffic density with a higher probability. This should result in a stable state where all cities have the same traffic density, right?

Well, not really. It actually results in a distribution where two cities have high density and most of the other cities have very low density. Some of the low density cities only have connections to high density cities. Since both connected cities have high density, these cities have no choice but to send their cars to them. The cars travel to these high density cities, get stuck, and never make it back out. So the low density cities keep sending cars there until they have no cars left to send. Maybe a better solution is to implement a cap on the max number of cars in a city, and stop sending new cars there if the cap is reached? That way, the low density cities won't send all of their cars to high density cities. I don't know, this may make inter-city travel dry up. I guess that's better than having gridlock though.

Where do the cars get stuck in these high density cities? They most frequently get stuck at the occasional 3-way connector road intersection. I did add 4-way connector road intersections, but they don't always get selected. Sometimes there's no way to route a road to exactly meet an existing, unused 3-way edge intersection. Maybe all the nearby intersections on that edge of the city are already connected to. Maybe the intersection doesn't line up with the intersection of the adjacent city and they're too close together to insert a jog. Maybe there are other roads, water, or mountains in the way. Etc.

There are several solutions to this problem:
  1. Adjust the road grid to force a road at the connection position by moving one of the roads around, which leaves an uneven distance to the existing roads on each side.
  2. Adjust the road grid by shifting multiple nearby roads to spread out the difference.
  3. Shift the entire city so that one of the roads is aligned to the chosen connector road position.
  4. Force a jog into the connector road, even if it looks odd and is otherwise too close to a blocker.
  5. Insert a non-axis aligned, slightly curved road to connect two opposing intersections.
  6. Add some random variation in city road widths to make it more likely that roads can line up.
Yeah, I'm really not sure about this. None of these are particularly easy to implement, and most of them add strange visuals. I tried to implement some of these, but they didn't really work out. #1 had the unexpected problem of two connector roads trying to connect to different ends of the same city road that couldn't agree on where to place the road. Also, moving the road increased the city plot sizes to the point where they no longer fit into the shadow frustums, leading to shadowing artifacts. I think #2 would likely fail for the same reasons. Shifting the city for #3 breaks the nice city placement pipeline/flow and can lead to iteration of the placement algorithm. #5 and #6 are just too messy and complex. Maybe the traffic has won this round. I think I put up a good fight.

I did manage to get somewhere with #4. I added a config file option to prefer adding roads with a single jog that end in two 4-way intersections over a single straight road with a 3-way intersection at one end. I'm not sure it helps much. The connectivity graph is worse, and cars have to travel further to get to their destinations. Maybe the only real benefit is extra road length to hold waiting cars. I can use this as a last resort if needed.

It could be time to start teleporting those pesky cars that block the intersection somewhere else on the map while the player isn't looking. I added wait time tracking for cars stopped at lights or in intersections. If the car has been waiting for more than a minute, it's front end is out in the intersection (blocking it), and the light has turned yellow, it's removed and respawned somewhere else in a random city. I didn't bother to implement the "when the player isn't looking" part because that makes it too hard to debug. Did that car I was looking at 30 seconds ago finally get to turn, or was it teleported somewhere else? I can't tell! If only I could see it teleport, then I would know that code was working.

I've definitely made progress using these improvements, but not enough to have the car simulation run forever without cars getting stuck. I have to get back to preventing cars from stopping in intersections. That's the root problem. I need something more complex than looking one car ahead, something with longer term planning. Someone suggested looking at all the cars in front of the current car and calculating whether or not they can fit in the current road segment if they were to stop. This makes sense. If they can't all fit, the querying car should stop before entering the intersection. That's the safest decision it can make.

Skipping to the conclusion - yes, this definitely works, but it's no easy task. I need to find cars on the same road segment when cars are on roads between intersections. When cars are entering or in intersections, I need to find the car in front, which may be in the intersection or on the road segment leading out of the intersection. Cars waiting at lights on the other side of the intersection don't count. Those new 4-way connector road intersections have roads with different city and road IDs on both sides of the intersection, and that has to be handled. There are a lot of cases, but after a lot of work I think I have it right.

If I let the simulation run for a long time (~40 min.), I still get one form of gridlock. I call this the "infamous right turn loop". Here is a picture of it.

The infamous right turn loop. The cars in this loop are all making right turns, but there's no space for any of them to move.

All four roads around this city block are filled with cars. The cars at each of the four intersections of the inside roads of this loop are trying to turn right. It's not really possible for a car to block a right turn unless it's also going in the same direction, so blocked intersections aren't the cause. There simply isn't room for any car to move. All of these cars are waiting because they have no space to move. This is like filling a race track with as many cars as can physically fit and having them race. Not possible! At least not without some car violating the minimum separation distance and risking colliding with the car in front.

None of my previous changes seem to solve this problem. I've tried changing the stopped_at_light state logic, allowing cars to turn left or right instead of going straight when blocked, and a few other things. I can't really think of what else I can try here. How does this get resolved in the real world? Maybe the only solution is someone putting their car in reverse and going a different way. If I don't support this option in 3DWorld, I guess it can't be resolved. Fortunately, this situation isn't very common. I give up on this one for now. Moving on.

The next task is making this system efficient. I don't have any data structure that tells me which cars are on each road or intersection. I prefer not to have to track all of this. What I do have are cars sorted by city ID, then road ID, then road segment ID. I can do a binary search through this data for cars on the correct segment/intersection of the correct road of the correct city. While this is faster than a linear iteration, it's still somewhat slow. All of the changes applied in this post have nearly doubled the car AI/physics/collision detection time. Much of the increase is due to the extra car-in-front logic.

Summary

I think I have cars working pretty well now. I've had the simulation run for half an hour, after which I see no stuck cars. Yes, there's traffic, but it's all moving. The three layers of gridlock avoidance seem to have finally solved this problem:
  1. Don't stop in an intersection (don't even enter the intersection unless there's room)
  2. If you find yourself blocked by a stopped car, choose another direction to go
  3. If you're still stuck in the same place after a minute of waiting, respawn somewhere else
I may finally be done with the car logic. I'm pretty happy how it turned out, though it took way longer than I anticipated. It's been about a month of realtime since I started working on this problem. There are still some minor issues such as cars stopping when they don't really need to, cars following too closely, cars jumping backwards a bit at intersection boundaries, cars colliding temporarily for a frame, minor instability (jittering) when a hundred cars are waiting to enter a city at a light, etc. I'm not sure if I'll try to fix these at some point or just leave them unfixed. They don't seem to hurt the overall traffic flow and ability for cars to get to their destinations. Most of these are only visible when you know what to look for.

I've had enough of cars for now. It's time to move on to a different topic. The next post will likely cover object physics interactions with cities. [In fact, I've already recorded a video and started writing it.] For example, weapon fire on buildings and cars. I don't plan on making these destroyable yet, I just want to prove that collision detection and collision response work with city elements.


Appendix: 3DWorld City Background Info

Some background on how my data structures work: Each city contains a set of roads, road segments, and intersections. The roads connecting cities are all owned by the "global connector road network", which also acts like a city (with no buildings). Roads and road segments are oriented in either X or Y for simplicity, and each one has only one lane in each direction. Segments have pointers (actually indexes) to their roads and the intersection at each end. Intersections have pointers to 2-4 connected road segments, and the 2-3 roads running through them. The 3 roads case is for 4-way intersections connected to other cities through the global road network. Roads, segments, and intersections are all spatially sorted so that operations such as binary search can be used to find them efficiently.

Cars maintain their current city, current road, current road segment or intersection, destination city, and destination intersection. Cars are kept in sorted order by {city => road => road segment/intersection => position along road}. This allows cars to query the car in front of them in constant time when on road segments. Everything works smoothly for cars on road segments, and I have no problems. Intersections are more difficult, and this is where there can be multiple cars "in front" of the current car, depending on where you look. There can be a car directly in front in the intersection, a car blocking the intersection going left/right (cross traffic), a car turning in front, or no car ahead within the intersection. If the car is in the process of turning and facing some non-XY direction, it's even more complex.

Cars and traffic lights are isolated systems that can query each other, but neither can directly modify the other's state. This models the real world where traffic lights can observe and direct, but not control cars. Cars can observe traffic lights but not directly influence them. Traffic lights run a finite state machine (FSM) that controls the different turning lanes for the entire intersection. This includes sensors that detect waiting cars and can skip light cycles where no cars are waiting. Cars can query the state of the FSM to determine the light colors. Yellow lights aren't actually states; they're determined by querying the traffic light for red/green light state at some time in the future. Since everything is determinstic and time-based, this is possible.

Cars travel at speeds determined by their max speed, the road's speed limits, and the speed of the car in front of them. Cars traveling faster leave more space between them and the car in front for stopping - though cars can actually stop very quickly when needed.

3DWorld cities have crosswalks and sidewalks. However, they're all fixed size, so they don't really need to be taken into account in the math. The dimensions of the driveable areas of the roads and intersections already take the crosswalks and sidewalks into account.

I haven't added the complexity of multiple lanes. Surely this makes the simulation much more difficult. This is one of the reasons why I haven't tried this solution to the traffic problem. However, I suspect multiple lanes would make some of these other problems much easier to solve.

It would probably be easier to prevent blocked intersections if it was more like a 4-way stop sign and the first car to reach the intersection could do what it wanted. The problem is that this won't optimize throughput for busy streets. I want to see those cars moving together as one continuous line of traffic while the light is green. I tried having cars wait until the car in front has cleared the intersection before entering it. It looks pretty bad visually. Imagine what it would be like if the light turned green, and the car in front of you started moving. You can move up to the intersection, but can't pull out into it until the car in front is out. Maybe you're crossing several lanes of traffic. The drivers behind you would be hoking their horns. Yes, this is safe, and it will prevent blocked intersections. I already tried it. It just makes the simulation look like all of the drivers are 90 years old!

Monday, September 3, 2018

Car Navigation Update

Here's a quick update on my car navigation progress. Once I had added the onscreen car stats feature, I was able to figure out what some of the problems were.

1. I fixed the problem where the traffic light "sensor" wasn't picking up cars stopped in the intersection and was skipping their green light cycle. This was an issue when there was no car behind the stopped car that was actually waiting at the light. The stopped car had to sit there in the intersection until another car approached the light behind it, triggering the sensor. The fix was to include cars stopped in the intersection in the sensor's "range". In fact, a stronger fix is to prevent the light from skipping any cycles when a car is stopped in the intersection. Another fix would have been to allow a car to exit the intersection even on a red light, but that seemed more difficult and risky to implement.

2. I changed the logic to allow cars that had entered the intersection to give up on a left turn and go straight instead when the lane was blocked. Previously, cars could only change their turn direction before entering the intersection. Now they can change their decisions as long as they haven't started to turn (rotate) yet. This allows cars to pull out into the intersection to make a left turn, then later give up and go straight instead. This was one of the most common causes of gridlock. However, this isn't enough to completely fix the problem. It's still possible for a car to pull out into the intersection, start to make a left turn, then get stopped by backed up traffic in the lane they're turning into. Once the car has begun the turn, it's too late to back out and go a different way.

3. Cars now have a 25% random chance of choosing a new destination when forced to abort a blocked turn. They also honk their horns in this situation. The new destination is always within the current city in an attempt to avoid the connector road, which is likely the path that was blocked.

4. Cars can now access the car directly in front of them on the current road. This allows them to see if the car is stopped in an intersection, and potentially not enter the intersection in that case. Unfortunately, this doesn't seem to help.

I was hoping that it would fix the problem with cars entering and blocking 3-way and 4-way intersections. This change makes cars occasionally stop before entering the intersection, but the most common case is when a line of cars enters and then quickly stops. The last car to enter saw the car in front of it moving just before it got stuck, since the line of cars always stop in front-to-back order. Cars still can't anticipate stopping.

I was also hoping that this would fix the problem of cars colliding when stopped around a bend in the connector road. The problem here is that the stopped car isn't actually directly in front of the second car, but to the side of it, facing a different direction (right angle). I don't know how to reliably find the car in front without accidentally picking up a car going in a different direction or on a different road connecting to the intersection. I can't use the front car's velocity because it's stopped. The system that sorts cars by position along a road won't necessarily place the two cars on different directions of the bend next to each other either. I don't think any simple position-based sort function would do this. Note that the sort is the most time consuming step of car simulation, so I need to keep it fast.

Sunday, September 2, 2018

Car Path Planning and Navigation Within a City

I'm back to working on 3DWorld's procedural city system. This post is about algorithms, decisions, and trade-offs. It's going to be a big wall of text without many pictures, since I can't easily describe this content with images. The images I do have are mostly of things that went wrong, since I don't really have this system working correctly yet. Sorry to those of you who just want to look at pretty screenshots.

I've had "better car path planning" on my city TO-DO list for a while. The current AI/simulation system was just choosing random turn directions for each car at each intersection. I wanted to change the system to select a real destination for each of the cars from somewhere in one of the connected cities, then let them drive toward their goals. I knew this was going to be a lot of trouble to get right, so that's why I put it off for so long. In my defense, it's not obvious to a casual observer whether cars are moving randomly or purposefully driving to a specific destination. You would need to pick a car and follow it around for many minutes to find out it's just going around in circles.


Destinations and Navigation

The first step in car navigation is choosing a destination. I decided to use road intersections as destinations. Each car starts with a random destination intersection in its current city. When it reaches the destination, it chooses another intersection in either the current city or an adjacent connected city. Choosing a different city is a lower probability that depends on how many cities are connected to the current one. When the destination is in another city, the intersection of the connector road leading to that city is used as a temporary destination until the car reaches it.

Cars run their path finding logic when they reach an intersection with traffic lights where a choice can be made (not a 90 degree road bend). This is generally only once every few hundred frames. They choose to continue straight or turn left/right based on which direction most closely matches the straight line direction to their destination. There are currently no reverse or U-turn options, which simplify the logic. These shouldn't be needed unless cars make incorrect navigation decisions. Since cities are laid out in a fully connected, uniform XY grid, this will produce an optimal path. However, it may lead to many turns in the case of a diagonal destination direction. I haven't yet tried to minimize the number of turns. I suspect it may lead to increased traffic along the edges of the city, which could be a problem. This system works pretty well for getting cars where they need to go. Car path finding only takes around 0.1ms per frame (of the total 0.7ms car physics/collision/AI time) for 4000 cars. The fast time is mostly due to sparse updating of destination parameters only once at each intersection rather than once per frame.

Here is a screenshot of cars in their initial uniformly distributed positions. This looks nice and clean. I've disabled the buildings and trees in all screenshots to make the cars easier to see. I also disabled static parked cars that only add visual clutter.

Initial state of cars before traffic starts to build up. At this stage, everything looks fine.

Traffic Congestion

The only major problem is traffic congestion - and this seems to be nearly unsolvable. I never really had this problem when using random turn directions because that kept the cars distributed uniformly across the city. They never accumulated in one area. But with specific destinations, certain areas of the city such as the connector roads become traffic hotspots. After 5 to 10 minutes of simulation, some of the connector road intersections become gridlocked and stay that way forever. The problem is usually due to cars stopped in the intersection, sometimes in the middle of making a left turn where they block both lanes of traffic. The cars can't finish their turns because they're blocked by oncoming traffic. What we end up with is a situation that looks like the screenshot below, where most of the cars in the city are lined up trying to get out through the single road that connects to the adjacent city.

Traffic jam leading up to the single road exiting this city. There are very few cars behind the player's view.

The source of the traffic jam is two cars trying to make left turns by the connector road. Here is a closeup of the connector road intersection. The three cars waiting at the intersections (two blue and one brown) are all trying to turn left, while the green car is turning right. All of them are blocked by cross traffic, which itself is blocked by other cars turning left. It's unclear how the simulation/AI should handle this situation. I'll present some ideas I tried that didn't work below, along with some other suggestions that I didn't try yet.

Gridlock at a connector road where two cars are trying to make left turns at intersections blocked by oncoming traffic.

Here is an example of something else that can cause gridlock. The yellow car is trying to make a left turn (I think) but can't complete the turn because of the brown car, which is blocking the intersection. (Cars have a minimum spacing around them to allow them to stop before they collide.) The stuck yellow car blocks the red car from either going straight or left. It may also block the red car from turning right because its rear end position may make its padded bounding cube overlap the other lane.

The yellow car is stuck in the intersection mid-turn, blocking it. I'm not sure if it's trying to make a left or a right.

Traffic Solutions

How would real drivers handle this? Maybe they would think ahead and not drive into the intersection in the first place if it looked like they would get stuck there. For example, by seeing that the cars on the other side of the intersection aren't moving and stopping before entering the intersection instead of blocking it. But that's difficult to implement in 3DWorld as it requires some sort of look-ahead and planning. It requires fast forwarding the simulation to predict where cars would be in the near future. Humans are great at this; computers are not as good. Computers may take a lot of computation time for this prediction, and that's not something we want in a simulation of 4000 cars.

Let's assume these real drivers do in fact stop in the intersection, blocking it. That happens all the time at the big intersection outside my real life office. Some options for getting out of this situation are:
  • Back up out of the intersection. This may require a chain of cars to all back up together.
  • Give up on making a left and make a U-turn or right turn instead.
  • Go around the blocking car by driving on the shoulder of the road, etc.
  • Drive in a different lane. Usually intersections like this will have more than one lane.
  • Honk your horn, repeatedly. Wait, this doesn't actually help...
Here are some solutions I've tried that didn't entirely fix the problem, listed approximately in the order I tried them. These changes together definitely improved the situation though, replacing "all cities have gridlock quickly" to "some cities have gridlock eventually".

Higher connector road speed limit: I increased the speed limit by 2x for connector roads. This got cars to their destinations faster, but did nothing to help traffic inside the city. In fact, it probably made traffic build up more quickly. Improving latency doesn't help to improve overall bandwidth in this situation. The rate at which cars can exit the city via the connector roads is limited by how fast they can pass through the intersection, not how fast they can travel once on the road.

Longer light times at connector roads: If cars exiting the city have more green lights, there will be less traffic, right? Well, no. This just means that cars entering the city will have to wait longer because their lights are red more often. Which means they're more likely to block the intersection and stop cars from exiting the city. I'm not sure what overall effect this change has on traffic, but it definitely doesn't solve the problem.

Right turns on red: I added a change that allows cars to make right turns on red when legal and safe. It was easy to do, but doesn't help much. Most of the traffic is due to cars waiting to make left turns, not right turns. This still seems like a good thing to have, as it generally reduces wait times at traffic lights that aren't blocked.

Traffic sensors to control lights: I added traffic sensors at intersections that detect cars waiting at lights. If no car is waiting, some light states may be skipped. This allows cars to get mostly green lights when no other cars are coming from other directions into the intersections. This definitely helps reduce red light delays for cars in the outskirts of the city, but it doesn't help traffic congestion at connector roads. These roads are busy and tend to always have cars waiting in every direction. Lights can rarely be skipped. Also, there's a problem where cars backed up at the light don't stop in the correct place to trigger the sensors and the light skips them. However, this doesn't actually matter to the overall traffic flow, because the cars in this direction can't move anyway. So I haven't bothered to fix it.

Reduce probability of choosing a new city: One simple change is to reduce the probability of a car selecting a neighboring city as its destination. Connector road congestion is more of a problem with cities that only have one road leading out of them. I changed the probability to be a function of the number of adjacent connected cities, and that definitely helped. There are fewer cars traveling through these choke points. Now only some cities formed traffic gridlock, rather than all of them. Though I suspect if I waited long enough eventually they may all fail. Some cities that have 4 connector roads, one on each side, accumulate a lot of traffic in the city center where the east-west and north-south streams of cars attempt to cross each other. This change is borderline cheating. Of course I can eliminate gridlock by setting the probability of choosing a different city close to zero, but that doesn't solve the root problem.

Abort turn and try a different direction: I decided to allow cars to change their minds if waiting to make a left turn at the intersection, where the intersection has been blocked by a full traffic light cycle. This only applies to cars that are right at the intersection and haven't started making a left turn yet. I initially had them go straight instead, but I also experimented with having them go right if straight was also blocked or unavailable. [I was never able to get the turn-right-instead-of-left change to work because, by the time the decision was changed, the car may already be too far into the intersection to turn right.] This definitely helped, but didn't prevent gridlock. It just delayed it. Instead of gridlock after 5 minutes, it came after 10 minutes. Eventually all of those cars turning in the wrong direction would loop back to that intersection and fill up all of the side roads/loops as well, until that entire area of the map was full of cars. The problem is that making other turns didn't get these cars to their destinations. Maybe they need to pick a new destination in this situation? I'm not sure if that would help if they're already stuck and can't move. Anyway, this behavior seemed to be useful, so I left it enabled.

Use collision detection system to navigate between cars: I experimented with ignoring blocked intersections and letting cars try to force their way between other stopped cars. Unfortunately, the collision detection system isn't really up for this. This change just resulted in cars getting stuck in odd positions mid-turn, which made the problem worse. Or it produced multiple cars trying to occupy the same space. Two cars would see a space available and would go for it at the same time. Now any temporarily blocked intersection could turn into a mess of cars where no one could move, which produced gridlock even faster. No, this isn't the correct solution, though maybe it would work in the real world. Maybe it would work if drivers communicate by waving to each other, etc.

Here are some solutions that are more likely to work, but are difficult to implement or have other disadvantages:

Fewer cars on roads: Duh! Obviously, the solution is to reduce the number of active cars on the road, right? Yes, this does fix the problem. Simply reducing from 4000 cars to 3000 cars makes it take a long time (if ever) to get a gridlock situation. But this isn't really a solution to the fundamental problem. It's like saying the solution to world hunger is to kill 25% of the world's population every so often. That's cheating!

Multi-lane roads: This is the next obvious solution. Real world roads have multiple lanes, which can fit more waiting cars into the same distance between intersections. Increasing speed limits won't fix the problem, but increasing capacity will. I definitely think there should be more than one lane in connector roads, but I probably also have to add multiple lanes to the local city roads feeding the connector roads. An optimal solution is to have connector roads turn into major multi-lane streets that cross through the city. The current situation where connector roads turn into left/right T-junctions is far from optimal. [It would be better if connector roads at least ended in 4-way intersections. This doesn't really work though, because two cities don't have their road grids aligned with each other so that they can be directly connected by a single axis aligned (north/south/east/west) road segment.] The difficulty here is that I would need to implement all of the car lane change logic. And I need road textures with two or more lanes. And I need intersection textures with lots of different combinations of lanes in the different directions. And I need to deal with roads/segments that have different widths from different numbers of lanes, which break the uniform city road grid. It seems like a significant amount of work, and it's unclear how well this fixes the problem.

Left turn lanes: This is a subset of the multi-lane roads idea. Instead of having the entire road be multi-lane, maybe we only need turn lanes. Maybe only left turn lanes. That way, one car stuck making a left won't block all of the cars behind it that want to go straight or right. This is easier to implement than multi-lane roads, but still requires new textures, lane change logic, and multiple road widths. It's unclear if this will actually fix the problem. It will certainly delay the gridlock. I suspect there will still be situations where cars pile up in the left turn lane because the one in front is blocked by oncoming traffic. Eventually, the left turn lane will back up into the straight/right lane, blocking it as well. But maybe the extra capacity of those lanes will be enough to handle 4000 cars.

Look-ahead/prediction: This is probably the most likely to work, but also the most difficult to implement. The real solution to gridlock is to not have cars blocking intersections in the first place. If the car in front is stopped, and the car behind it would get stuck if it entered the intersection, then have it wait at the light. This is what's supposed to happen in the real world. Of course, this may not be perfect in practice. For example, say a car is following a moving line of cars into an intersection. The cars are moving, so it looks safe to enter the intersection. Then the car in front of the line stops suddenly, causing a chain of braking that leaves the last car still in the intersection. What now? Clearly, the prediction system must be more complex than just looking at the car in front. How far does a car need to look ahead? All the way to the next intersection? That could be 30 cars away. It's not clear how much this would impact CPU time and frame rate. I'm sure this would be very time consuming to implement (and debug!) It's unclear whether or not a system like this could guarantee there was no gridlock.

"Removal" of offending cars: Removal of cars can be a manual step, rather than an automated one. Let the player select problematic cars and remove them or relocate them somewhere else in the scene. I've been working on making gameplay weapons work in tiled terrain mode. That's likely going to be the subject of my next 3DWorld blog post. I have projectile intersections with the terrain, buildings, and cars working. I have some functional physics effects, including explosions. If I can make the cars destroyable with the rocket launcher or other weapon, that could be a good way to get rid of those pesky cars stopped in the intersection. It would be a lot of fun! I could make some sort of game out of it, though this is probably pretty far in the future.


Collision Detection

Collision detection problems are a side effect of traffic/gridlock. The collision detection system wasn't designed to handle cars stopped in intersections and around bends. It's only intended to stop cars (or in extreme cases move cars back) to prevent them from colliding with other cars in front in the same lane/direction/orientation. I attempted to handle this by tracking which lanes in intersections are blocked, but it doesn't work correctly in all cases. If I make the definition of "blocked" too strong, two cars blocked in different directions at the same time will deadlock the intersection and prevent either one from ever moving. If I make the check too weak we can end up with situations like this:

A bug/limitation of collision detection can result in two cars trying to occupy the same spot when traffic backs up, blocking an intersection.

The orange and blue cars are inside each other. The problem is that the orange car turning right from the right side of the screen tried to squeeze between the yellow car and the blue car, which were both already stopped in the intersection. The turning collision check is something like a simple ray cast, and the car thought it would fit. Or maybe the blue car and the orange car both thought they could fit in the same previous frame, but they couldn't share that spot. In any case, the two cars end up on top of each other. The collision detection system can only move them forward or backward. If it moves them to the side, they can go out of their lanes or off the road, which causes worse problems (such as assertion failure). It can't move them forward or backward because the two yellow cars to the front and back don't give them both enough space to fit. So they're left where they are, overlapping each other. Actually, the collision system is probably trying to move them every frame, but they snap back to their previous positions because the new positions are also invalid. The fallback is that if the collision system can't resolve the collision, the cars are returned to their previous frame's positions. If the traffic in front starts to move, the orange car will move with it, and eventually the blue car will follow. So this is only a temporary failure.

Here is a similar problem. In this case, cars are backed up to a bend in the connector road. Since this road doesn't have any traffic lights or decisions to make, it doesn't have any of that blocked intersection logic. There's nothing that triggers cars to "look ahead". Cars will happily drive from the right into the line of stopped cars. Then the collision detection system will figure out that they intersect and try to move them, which fails in a similar way as the image above. Here a black car and a white car are inside of each other, and the orange car has been pushed behind them, slightly off the road. To make matters worse, the orange car is still considered to be in the right lane. Cars coming up the hill from the other direction (top of the image) will happily collide with - or rather travel through - the orange car.

Collision detection doesn't understand about traffic backed up around a bend in a road with no traffic light to stop the cars.

This problem might not be that hard to solve. The only issue is that it takes a long time before this failure happens. I've rarely seen it occur less than 10 minutes into the simulation. That's a lot of time to wait for debug iterations. Plus it's nondeterministic (doesn't always fail), which makes it difficult to verify the effects of my code changes. I'm not entirely sure what's going on here. There are too many active cars to print out the state of each one to the console. I could reduce the number of cars below 4000, but then traffic won't back up. Maybe I need some sort of car selection UI for debugging where I move the pointer over a car and it prints some onscreen stats? I had to do that for ships in universe mode. In fact, I already have car ray casting working in overhead map mode, so it probably wouldn't be that hard. That might work, if I feel up to implementing it later.

Update: I added car selection with onscreen stats display, similar to the ship stats display in universe mode. It's not the best, but it's ... functional. Now I just need to figure out which of the 36 numeric car class member variables I want to print out.

Car query mode. The crosshair is centered on that white car in the middle. We can see its stats, shown with some odd perspective text that was intended for universe mode.

Summary

All of these collision problems are due to cars stopped in unexpected locations rather than behind traffic lights. If I can solve the traffic and gridlock problems, I don't have to worry about these issues as much. I've spent a lot of time on this and I don't really want a complex solution. I've added a config file variable to control car path finding and left it disabled by default so that cars are back to making random turns. I don't think it has much effect on the overall look of the city anyway. Maybe I can do something easy such as reducing the number of cars if I decide to enable this again in the future. It was definitely an interesting, though frustrating, experience.

In summary, car path planning is hard. Now I think I understand how difficult autonomous vehicle software must be to write. What is a self driving car going to do in these situations? I'm guessing it will be a big problem in the future. Blocked intersections probably aren't that common in their training data.

If you're curious, you can find the source code in my 3DWorld GitHub repo.

I'll continue to think about this. In reality, I'm probably going to move on to weapons physics for building and car destruction. That seems much more fun to implement!

Saturday, September 1, 2018

Solar System with Elliptical Planet and Moon Orbits

I'm taking a break from procedural city work to fix up some unrelated features of 3DWorld. A few weeks ago, I came across a Reddit post of someone working on planet orbits, where the author stated that real elliptical orbits were used. 3DWorld was initially using simple circular orbits, so I decided to implement more realistic elliptical orbits. I had actually started writing elliptical orbit physics for planets, but it was incomplete and unused. I also had to fix the orbits for asteroid belts to make them match.

3DWorld orbits are represented by an axis of rotation and two orthogonal vectors of different lengths defining the shape of the ellipse. There were several requirements that made this effort nontrivial. First of all, the system needed to be stable over time. I wanted the planets and moons to orbit for hours while the player explored the universe and participated in ship battles. I didn't want to see planets showing jittery movement after that time. My first attempts at the math worked by iteratively computing the new position of each planet and moon every frame from the previous frame's position and orbital parameters. After a while the system would accumulate too much floating-point error and the planets would drift away from the sun, out of their intended orbits. Moving from floats to doubles extended the period of stability but didn't entirely solve the problem.

A second problem is that there are a lot of planets, and the orbital physics involves some expensive math including trig functions. It took too much CPU time to update every planet and moon in the current galaxy (~400 stars) every frame. I wanted to update more distant bodies at lower intervals, and very distant bodies only when the player flew close to them. This means that the update rate may be only once every few minutes, which is too long to perform an accurate incremental update.

The solution to both problems was to compute the position of the planet or moon from scratch given the starting position, orbit, and current elapsed time. This was applied as a fix-up to the incrementally updated position. It allowed for high accuracy, even with low update frequency. However, there was still some accumulated error in the time variable. What I ended up experimenting with was resetting time back to zero ever few tens of minutes. This can be done when the player isn't nearby or isn't looking at the target. Alternatively, the starting position can be updated to be equal to the current position when the time is reset. The effect is unnoticeable by the user and makes the system stable over hours.


Planets and asteroid belt with elliptical orbits around the star.

All that's really necessary for first order stability is placing the body at the correct distance (radius) based on the orbit for planet <=> star and moon <=> planet. This is trivial when using a circular orbit with constant radius. Elliptical orbits are more complex as the distance depends on the position along the elliptical path. I had to look up the math for this one. I decided to use the current rotation angle to compute the distance using the following online post for reference. My code can be found in the 3DWorld GitHub src directory, function get_elliptical_orbit_radius() in Universe.cpp. This function is used in urev_body::do_update() for planets and moons, and in uasteroid::apply_belt_physics() for asteroids (in asteroid.cpp).

Another problem I encountered was limited floating-point precision in the position update math. This caused planet movement to appear jittery. This was due to the large difference in magnitude between the planet's position in the galaxy compared to the size of the current frame's delta position update. If the position update was less than one mantissa bit, it would only move every few frames. The fix was to make planet motion math relative to the star it was orbiting around, and moon math relative to its parent planet. This kept the magnitude of the numbers smaller, improving the precision of position updates. Note that I actually fixed this problem some time ago.

Here is a video of planets and moons in motion with my attempt at true planetary physics. Keep an eye on the shadows, they look pretty good. I've added a config file variable that I used to speed up time by a factor of 400 over the default timestep values. This makes the planets orbit the sun in a matter of tens of seconds rather than hours. It makes planet and moon orbits much easier (and faster) to debug.



Yes, I'm aware that the planet I'm following is inside the asteroid belt. I'm not trying to fix this right now. The planet-asteroid belt intersection code doesn't handle elliptical orbits.

It took me quite a few attempts to get this right. I should have kept some of the crazy broken videos, but I didn't think of it at the time. I had some where there was an error in the math and the system quickly went out of control, throwing all of the bodies off into space. I had another bug where the orbits were wrong and formed a figure 8 through the sun. And I saw yet another problem that made planets do little loopy dances across the screen. Oh, and I also had one problem where the planet atmospheres trailed behind the planets by a frame. But in the end, I was able to get everything working correctly, stably, and efficiently.

I added another config file option to control elliptical orbits. I'm using circles for the default scene though, so that the changes in orbits don't break my current ship and colony placements.

Sunday, August 12, 2018

3DWorld for Linux

I've been working on getting 3DWorld running on linux for the past month or so. This is why I haven't posted any new blog content. I've also updated some of the dependencies (including the Windows build) to newer versions. I've included all Windows dependencies and many of the smaller 3D models and texture files in the git project. Both the Windows and linux builds should be working now. You can find the code on GitHub.

Monday, July 2, 2018

Procedural City: Bridges and Tunnels

I'm still working on the procedural city, even though I took a break from it to work on some other things. Instead of adding more objects along the city streets, I decided to go back to trying to improve the road networks connecting cities together. I didn't like how much the terrain height was changed to place long connector roads. There was too much elevation change, and too much dirt/rock added and removed. Engineers and city planners don't just fill in entire valleys and carve space through mountains to build level roads. They build bridges and tunnels.

Challenges

It took a considerable amount of time and effort to get bridges and tunnels working in 3DWorld, much more than I initially expected. This was more than the week long project I thought it would be. It seemed like every aspect of them required low-level infrastructure changes to the procedural city system. I'll start by listing some of these challenges and how I solved them.

Placement of both bridges and tunnels is tricky. This requires a certain cooperation between the road placement system and the terrain heightmap system. Both the road networks and terrain heights have to be specifically adjusted to fit these structures in properly without seams or other artifacts. Since these are two different classes/systems in 3DWorld, this required some API changes so that they could better communicate with each other. There were also problems with precision, as the heightmap values can only be modified at its native resolution of around 2 meters per sample.

Bridges and tunnels introduced some new rendering challenges. Everything else in the scene is assigned to a single terrain tile. Most objects are sorted by tile and iterated over in tile order. Per-tile shadow maps and other state are used for drawing these objects. Buildings and cars are small enough to fit into their parent tile with a reasonable shadow map border. Roads are drawn in sections representing individual blocks, which are assigned to tiles. However, bridges and tunnels can be longer, and may cross multiple tiles. I ended up having to split some of the longer ones into two or more separate parts, each of which is drawn using different state/texture bindings. This worked, but added a lot of complexity to the drawing code.

Texturing was also more difficult. The various drawn parts of bridges and tunnels could be high aspect ratio. For example, the bridge guard rails are as long as the bridge but only a few feet high. I had to add support for custom texture scaling for the various cube faces.

Another problem I had to overcome was player collision detection; more specifically, setting the correct z-value (height/altitude) for the player position. Up until now, the player has always been placed exactly on the mesh surface in tiled terrain mode. That is, unless flight mode had been enabled. This makes player physics and collision detection easier because it's mostly 2D. The terrain height is set equal to city and road height to keep things simple, which means that placing the player on the terrain would automatically also place them on the road surface. This system breaks when bridges and tunnels are added, because now the player can be on a road surface that's above or below the terrain mesh. Furthermore, we need to keep track of the previous player z (height) value so that we know if the player is on vs. under a bridge, or inside vs. above a tunnel. I had to add collision detection to keep the player from falling off a bridge or moving through tunnel walls. All of this required significant changes to the code. Cars always follow road surfaces, so at least I didn't have to special case car physics to work with bridges and tunnels.

Tunnels had some additional issues that I had to solve. These are discussed in the tunnel section below.

Bridges

Bridges are currently placed on road segments that meet the following requirements:
  1. Both end points are at similar heights. The road surface can have at most a minor grade.
  2. Both end points must be significantly higher than the average terrain height of the span.
  3. No point along the length of the bridge can be higher than the end points.
  4. There is a minimum required volume (height integral), otherwise why even build a bridge?
  5. Bridges are clamped to a reasonable size range from 5 to 128 texels (~10 to 256m).
  6. Two bridges can't be placed close together (within adjacent road segments).
With these constraints, I get two bridges for my test scene of five cities. I can tweak some parameters to get three additional bridges, though their placement looks somewhat odd. None of the bridges are quite level. I don't remember ever seeing a sloped bridge in real life, though I don't see why it can't be possible.

I chose to implement suspension bridges with variable length and height designed to fit them into the terrain. Bridges are procedurally generated with between 16 and 48 parabolic arch segments and support cables, depending on bridge length. They may look complex, but there's generally only one bridge visible at a time so I had no performance problems drawing them. I placed streetlights along the interior sides of each bridge between the road surface and guard rails. Bridges cast and receive shadows like everything else in the scene. I think their shadows look much more interesting than building shadows. Here are some bridge screenshots.

Medium size bridge over a deep canyon, with shadows. Cars can be seen crossing the bridge.

Bridge shown from a different viewing direction.

Note that only the road surface, guard rails, and bridge bottom are textured. The supporting arches and support cables are left untextured gray. These represent smooth painted or bare metal. Maybe I should have used some sort of texture or normal map that included bolt patterns for the arches?

Here is a larger bridge over a shallower valley. Real world engineers probably would have made the road curve around this depression rather than spending all that money constructing a bridge. In my defense, the original placement algorithm didn't want to put it here. It only wanted to place that one bridge in the previous image. I had to tweak some parameters to get another bridge, and this is what I got. Note that grass is placed under bridges, but large trees are not. I found it too difficult to ensure the tops of the trees didn't collide with the bottom surfaces of the bridges. I just mask this area as "no trees" to avoid the problem.

Large bridge over a wide, shallow, tree-covered valley.

Here is a night time view of a bridge, with a city in the background. Streetlights are placed at uniform intervals on both sides of the road. They do a good job of lighting the road for the cars. I made it easy to instance this particular streetlight model wherever it's needed. I used the same streetlight system for bridges as I did for roads. This automatically handles drawing, shadows, collision detection, and night time light source generation.

Night time bridge scene with cars, streetlights, and a city in the background.

City lights at night, with a large bridge in the distance.

I placed the streetlights a bit outside the bridge in this screenshot to get a better shadow effect. The bridge support cables really cast some interesting shadows. However, the streetlights don't look right floating in space like that, so I can't leave them there.

Closeup of bridge road surface with shadows. The streetlights have been moved outside the bridge for more extreme shadows effects.

That's all for bridges. Next, on to tunnels.

Tunnels

Tunnels use a very similar placement and drawing system to bridges. At first glance they seem simpler than bridges, at least the drawing part. But I did encounter some new problems when adding support for tunnels.

First, I needed a way to remove (not draw) the terrain mesh at the bridge entrances and exits. If I was using a voxel approach, I could just carve the tunnel shapes into the voxels. It's more difficult to add tunnels to heightmap based terrain. Fortunately, I didn't need to draw the terrain on the inside of the tunnel because it's occluded by the tunnel walls. I eventually decided to implement a terrain mask by setting an invalid state in the landscape texture splat mask. I'm using the four RGBA texture channels to store terrain weights for {sand, dirt, grass, and rock} materials. The fifth material, snow, is calculated by subtracting the sum of the other four weights from 1.0:
snow_weight = 1.0 - sand_weight - dirt_weight - grass_weight - rock_weight

At first glance it seems like there's no room to store a draw/transparency mask. After thinking about it for a while, I realized that I could set the weights to an invalid state such as {sand_weight=1.0, dirt_weight=1.0} to indicate that this mesh texel should not be drawn. This combination of weights can never be procedurally generated in a real tile because they sum to more than 1.0.

While this works great for disabling individual mesh texels, the solution isn't perfect. The first problem is that the mesh is projected into the horizontal X-Y plane. What I really want is a vertical hole in the X-Z or Y-Z planes for the tunnel opening. The second problem is that this has a limited resolution set by the texel resolution of the texture weights mask. For reference, a texel is around 2m/6 feet and the road surface is slightly more than two texels wide. I was only able to work around these issues by making the holes in the terrain larger, and placing a tall concrete block facade at both entrances of each tunnel. This does hide the edges of the holes, but it looks a bit odd and unrealistic. The math for where to place the terrain holes and the facade is also very tricky. It requires some adjusting of the terrain heights to get a steep slope at tunnel entrances as well. This took hours of trial-and-error to get right.

The third problem with transparent pixels was a bit of a surprise: it breaks terrain occlusion culling. The occlusion culling system selects nearby tiles with steep mesh areas as potential occluders of other, more distant background tiles. This improves drawing performance by allowing the rendering system to skip entire mesh tiles that are occluded/hidden, along with whatever objects (trees, grass, etc.) are placed on them. However, this system isn't aware of tunnels that cut through transparent areas of the mesh. When the player is inside a tunnel, the terrain on the other side of the tunnel may suddenly disappear! My first attempted fix was to just disable terrain occlusion culling when the player was inside a tunnel. This almost worked, but still failed to disable occlusion culling when the player was in front of the tunnel looking through it. A better solution was to remove terrain tiles with tunnel openings from the potential occluders pool.

Finally, I had to clamp the mesh height to a minimum value along the length of each tunnel to ensure it stayed out of the tunnel. We can't have terrain blocking the way. Normally, this doesn't happen, but I did see one tunnel with a dip in the middle that I had to fix. I guess this tends to occur more often when the terrain is steep and noisy, such as in the mountains. After that fix I don't see any visual artifacts.

The parameters I used for tunnel generation produced five tunnels of various length and slope in my test scene. I added streetlights to tunnels as I did with bridges. Cars can drive through tunnels without problems - finally something that just works without requiring a complex fix! I haven't yet added indirect lighting or ambient occlusion to tunnels, so the lighting looks a bit flat.

Here are some screenshots of tunnels with cars driving through them. Note that the pine trees are probably too large, and the grass blades are definitely too large. Since vegetation isn't the focus of this post, I didn't bother to take the time and fix that. In fact, I didn't even notice the large grass blades until I added the screenshots to this blog post.

Tunnel through the mountain with tall facade and upward sloped road surface.

Cars going through a long tunnel, with a bridge on the other side. Please ignore the oversized grass.

Here are two night time views of tunnels. As you can see, tunnels also have the same streetlight models as roads and bridges. Shadows work here as well.

Tunnel at night, lit by streetlights and car headlights.

Inside of a tunnel at night. City building lights can be seen on the opposite side entrance.

Maybe tunnel streetlights should be on even in the day time? Maybe cars should always have their headlights on while in tunnels? That sounds like future work.

Overhead Map View

I added roads, bridges, and tunnels to overhead map view to help debug their placements. Then I decided I liked the look of that, so I added city blocks, cars, and buildings to map view. This produces a nice cartoonish aerial view of the city with pixel accuracy. The user can pan and zoom using the mouse and arrow keys similar to Google Maps. Each pixel of map view makes a ray query into the city database that returns a hit color. Draw time isn't that great, but at least it's multi-threaded. I haven't attempted to make these sorts of queries into the city data optimal. I only get around 10 FPS, but that's good enough for a map.

Overhead map view of road network and cities: gray=road, white=bridge, brown=tunnel, lt_gray=plot, dk_gray=parking lot

Overhead map view of a city showing roads, buildings, parking lots, and cars. Some buildings are the same gray color as the plots and can't easily be seen.
 
This gives as sense of just how large this scene actually is. I haven't implemented moving cars in map mode yet. The control flow currently doesn't even call any of the physics state update. That can be future work. [Update - it's done: now cars move in map mode.] Another future work item is setting the plot colors so that they can never be the same as a building color.

Conclusion

Now that I have bridges and tunnels, I can go back and add more complex road networks. It's likely possible to allow city interconnect roads to cross above or below each other. I'm not sure how much work that would be. I can probably also enable roads over water. I didn't originally want to handle that case because the resulting mesh + water didn't look right. Now I can just make bridges over the water and not have to worry too much about adjusting the mesh height just above the water level.

I was also thinking of maybe adding railroad tracks and a train that goes around a loop. I definitely need to find some gradual bend textures though - trains don't go around sharp 90 degree turns. At some point I need to work on multi-lane roads as well.

Sunday, June 10, 2018

Reflective and Emissive Spheres Test

I came across this Unity GPU path tracing article by David Kuri of Three Eyed Games and decided that I wanted to produce a similar scene in 3DWorld. However, I'm taking a very different approach. Rather than using a ray/path tracing based solution, I'm using precomputed indirect lighting, shadow maps, and cube map reflections. The image quality isn't as good, but it runs in realtime (60+ FPS) and can be viewed from any angle. In fact, the user can even interactively change the sun position and move spheres around in the scene! Ray/path tracing approaches take seconds to minutes per frame, which is thousands of times longer.

I added config file options to place random spheres in 3DWorld. The user specifies the number, size range, spatial distribution, and probabilities for various sphere materials in a text file. These can be added to any scene. In this case, I used a simple white cube for a ground plane. The spheres are placed randomly within a circular region on the ground. I used between 100 and 200 spheres for these tests because that gave reasonable runtime numbers.

3DWorld implements reflective materials using one cube map per object (sphere in this case), as shown in this blog post from last year. The basic description of how cube map reflections work in 3DWorld is shown here. All six cube faces of each object are rendered to textures during update frames. Several update frames are needed to get the nested reflections between multiple nearby reflective objects. For example, two nearby metal spheres will reflect each other recursively. Each update frame takes around 250ms to compute almost 100 cube maps, or around 500 cube face texture images.

Moving individual non-emissive spheres takes 50-100ms per frame to update the needed cube map faces. Moving the sun requires the full 250ms update due to the global affect of sun lighting in the cube maps of all the spheres. Frames where nothing moves but the camera take only around 14ms for these scenes, or about 70 FPS.

Indirect lighting is computed in about two minutes for 14 light sources in 3DWorld. I used the same method as in other scenes, as described in this post. The lighting data can be saved and reused at a later time as long as none of the emissive light spheres move. The lighting grid is stored in a 3D texture on the GPU and used to lookup indirect lighting data in the fragment shader.

For reference, here is the Three Eyed Games image:

GPU path traced image on Three Eyed Games blog that took several minutes to generate.

Here is as close as I was able to get using 3DWorld:

Realtime 3DWorld rendering of similar scene using precomputed indirect lighting, shadow maps, and cube map reflections.

I'm not trying to exactly duplicate the reference image, I just want to make something in a similar style. The goal is to compare the two different rendering approaches.

There are a variety of differences. The most obvious one is that the 3DWorld version is darker than the reference image. This is because there are fewer emissive light source spheres. 3DWorld is currently limited to around a dozen dynamic point lights with cube map shadow maps because it has a fixed number of shadow map slots (64). I could probably increase the limit, though it may hurt performance.

The 3DWorld image has hard shadows, whereas the reference image has soft shadows. That's the difference between using shadow maps vs. ray tracing. There's not much I can do about this one. Soft shadows from many point light sources are difficult to do in realtime.

Another difference is the mixture of materials. The reference image contains a combination of emissive, metal, dielectric, and diffuse spheres. The reflective spheres have variable roughness. 3DWorld has the same types of materials, but seems to use a higher percentage of shiny metals. There are some rough metals and some dielectrics, but the lower lighting levels makes them difficult to see. I've shown rough materials previously. I could tune the random number generation parameters to make them more in agreement. I kind of like all of the reflective spheres in my image though.

The two images have different types of noise. The reference image has high frequency pixel noise that can only really be seen when viewing the image fullscreen. 3DWorld has lower frequency noise due to the sampling of the precomputed indirect lighting grid, currently 192x192x16 texels in size. I spent a while adjusting various parameters in the code and config file to try and minimize noise, and it definitely improved things. I could further reduce the noise with a higher resolution grid. However, this would take more precomputation time, more disk space to write, more GPU memory, and more work in the fragment shader. This leads to increased render time/lower frame rate.

This screenshot shows the same scene during the day under bright sunlight.

Same 3DWorld scene as above, but this time during the day. The bright sun produces sharp shadows on the ground plane.

Here is another view of the 3DWorld scene at night. Now that I look at it, this seems closer to the reference image than my first screenshot.

Another view of night time 3DWorld scene.

Here is a similar scene with 100 spheres in day time. The bright sun makes it easier to see the different materials. This time I used transparent spheres and refractive glass spheres in addition to the other types. The glass spheres with higher index of refraction produce inverted refraction images. I removed the tiny spheres that were difficult to see.


Day time rendering of a similar spheres scene with strong sun lighting. This one has transparent/glass objects as well.

I also found a scene that had two large light emitters near a small glass sphere. This produces caustic lighting where the glass focused the light sources to two bright white spots of light on the ground plane.

Metal, glass, ceramic, and emissive spheres during the day. A caustic refraction can be seen near the center.

Here is the same scene and view, but at night. The indirect sphere lighting is easier to see.

Metal, glass, ceramic, and emissive spheres at night. The two white lights are focused through the glass sphere in the center to produce caustic lighting patterns on the ground.

Here is the same scene, but a different view. We're now looking at the other side of the glass sphere.

Same scene as above, but viewed from the front. The noise in the lighting is due to grid sampling artifacts.

That's it for now. I'll consider making a more complex and interesting scene in the future. I would also like to reduce the indirect lighting noise, though I don't know how to do it efficiently.