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.


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


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.

Saturday, June 2, 2018

City Trees and Other Improvements

I haven't done too much work on cities since the last post. I've been working on a variety of other things in 3DWorld, including portals and a weapon that fires teleporters that bounce around the scene, teleporting anything they touch into the clouds above the scene. However, I'm not here to discuss these changes. You can read about these here.

Previously I had added windows and night time window lights to city buildings. The results looked pretty good, but I did go back and make some improvements to window lights. A Google image search for city lights gave me some ideas for how to make lighting look more realistic. I added a brightness gradient to make the bottom of the windows a bit darker, as if furniture and other objects were blocking some of the light. I made the dark windows have a small amount of light, as if there was some indirect lighting coming from adjacent lit rooms. I also added some random color variation to window lights. Colors are washed out by the bloom effect in bright windows but are more apparent in the darker windows.

The latest version of city window lights at night. Lights have variable brightness and slight color variation.

Night time city streetlights, car headlights, and building window lights.

I would like to add more detail to window lights to make them look more varied, such as dark shadows due to furniture and other objects blocking the light. Shamus Young did a good job with this in PixelCity. However, he took a pre-generated texture approach. That doesn't really work in my flow where the windows themselves are drawn in the fragment shader. I would need to somehow create the darker shapes and color variation within the shader itself. That should be possible, but so far I haven't figured out quite how to do it in a clean and efficient way.

The next type of city object I added was trees. I already had a system for generating and placing procedural trees in the scene, but it was quite a bit more work to add trees to cities. First, I had to generate tree placements that didn't overlap buildings, streetlights, traffic lights, roads, etc. Here are some screenshots showing trees placed in a city.

Procedurally generated and placed trees inside a city, with shadows.

Procedural city trees viewed from above.

The most difficult part was getting dynamic lighting (including shadows) from streetlights and car headlights to work with trees. Dynamic lighting and shadows works with trees in other scene/viewing modes, but I had to make it work with the city system and tiled terrain mode. It's more challenging to get the dynamic lighting solution to work when the player can move over a very large area. This required piecing together various bits of C++ and shader code, and a lot of trial-and-error. The process was different for tree branches vs. leaves, each of which uses a different rendering system. Here are the results. Note that tree leaves use a double sided lighting model, the light is facing downward, the camera is looking mostly at the unlit sides of leaves, which is why they appear so dark.

Night time city trees receiving light from cars and streetlights and casting shadows on the scene.

More lit and shadowing trees at night.

Another view of city trees at night.

I also made some improvements that I can't show in screenshots. For example, I implemented player collision detection with streetlights and traffic lights. [I already had collision detection with buildings.] I tried to add car collision detection, but I found that it didn't work very well. There were various problems. For one, it's too easy for the player to get stuck between parked cars and cars stopped at traffic lights. Maybe I need to make the player model smaller, or less round? It's not clear exactly how cars interact with the player anyway. I haven't figured out how to turn this into a game yet.

I'm still working on adding benches and other city details. I already have the framework to in place. Benches can be placed and integrated into the collision system. The problem is that it's not very fun and interesting. If I draw benches using downloaded 3D models like the cars, it's just more work finding models and fiddling with all the parameters to make them look good and draw fast at the same time. On the other hand, creating them myself is also not really something I want to do. I don't have any good 3D modeling software and I'm not sure how far I can get by hard-coding the shapes into the source code. I know I did that with streetlights and traffic lights, and I could do that again with benches. But it doesn't really seem like productive work. I just have to copy the code for those other objects and change it all to work with benches. Repeat for any other object type. I guess it would really help if I had someone with more artistic skills working on this project.

Someone suggested adding rows of lit window lights for buildings. I made the change, and here's how it looks:

Buildings with groups of lit windows on each floor.

You can definitely see the groups of lit windows now. Not all buildings should have long rows of lit vs. dark windows. I changed the shader code so that building window group sizes varies per-building and per-floor. I also made the ratio of lit to dark windows vary per-floor. Here is what that looks like:

Rows of lit windows that vary in group size per building and per floor.

Are these results better (as in more realistic)? I don't know, maybe, it's hard to tell.

Sunday, May 27, 2018

Teleporters and Portals

This post will be a short break from my procedural cities series. I found this Introduction to Game Development video presentation on the making of Portal and Portal 2 very interesting. I decided that I wanted to make the teleporters in 3DWorld into portals that the player could see through. This way, you can look through the teleporter to see if it's safe on the other side before stepping through. I used a separate rendering pass to create a texture that's drawn on top of the teleporter graphics when the player is close. It uses the same view direction and parameters as the player camera, but the camera origin is placed at teleporter destination location. Here is a screenshot of a teleporter that leads to the roof of the office building.

Teleporter with nested portal image reflected in the floor.

Yes, I made the portal rendering recursive. It only renders one image for each teleporter per frame, but the images accumulate nested/recursive sub-images across several frames. This uses a similar system to 3DWorld's reflective objects. Here is what the player sees when looking through a series of two teleporters, one in the lobby and the other on the roof.

Recursive view through two teleporter portals in the lobby and on the roof.

I decided that I wanted to have some fun with teleporters. I made a freeze gun a few months ago, but nothing is more fun and insane that turning a teleporter into a weapon! I have a new player secondary fire mode for the dodgeball that will instead fire a teleporter that bounces and floats around the scene, teleporting any dynamic objects within range. In particular, it can be used to teleport other players (and yourself if you're not careful). Where should it teleport them? Into outer space? That would be funny, but it takes too long to die. A better solution is to teleport them into the clouds so that they fall and splat on the scene below. It will be literally raining smileys (and body parts). I even added a screaming sound that plays while falling. However, I didn't add portal textures to these teleporters, because it's not too interesting to see inside sky and clouds.

Teleporters are very strange physics objects. They float with only a tiny amount of gravity. They're friction-less and slide across surfaces. They're non-solid so some objects can pass through them. Any gameplay objects (players, rockets, proximity mines, pickup items, body parts, blood, bouncy balls, etc.) can be teleported. Teleporters last for a limited amount of time (around 30s), and there can only be a few of them active at a time.

Here is a video of the teleporter gun in action. Note that the blue smileys are enemies and the red smileys are teammates, though I like to teleport my teammates to their deaths just for fun. You can see how the teleporter teleports a smiley hat, a burning skull, and some proximity mines as well. I teleport suicide twice in the video. Both times you can see objects that have lower terminal velocity than the player in the air as I'm falling. These objects were teleported into the sky a few seconds before I was. An enemy fired a seek-and-destroy (similar to a rocket) at me from the right side just before I teleported the first time. If you look carefully, you can see it exiting the teleporter at the same time as me and flying off into the sky.

Oh, and you can teleport a dynamic teleporter through a fixed/static teleporter. This happens to "just work" in my system.

You might try to be smart and block a teleporter with a movable object such as the chair. That will work if the chair is static; the teleporter will simply bounce off it. However, if the player is pushing the chair, both the player and the chair will be teleported into the sky. The player will hit the ground first. If you're lucky, your eyeball will be looking up after you die to see the chair land on top of it. I would post a video of this if it was easier to pull off.

Here is a screenshot showing multiple teleporters bouncing around. They're drawn using additive blending + emissive 3D animated volumetric procedural clouds. Each one is unique! They even emit dynamic light that changes color over time. You can see the lighting on the ceiling of the office building lobby in the image below.

Multiple dynamic bouncing teleporter objects. The goal is to not be hit by any of them.

That's it. This was a short post. I just wanted to get something out while I'm working on the procedural city update. Teleporters were challenging to integrate into the physics and gameplay system, but were extremely fun to play with.

Monday, April 30, 2018

Building Window Generation

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

City lights with bloom effect, shown from above.

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

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

Monday, April 23, 2018

Dynamic City Shadows

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

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

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

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

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

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

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

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

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

Soft shadows from cars parked under a streetlight.

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

Streetlight shadows produced by the lamp post and the building.

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

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

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

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

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