Sunday, December 14, 2014

Indirect Lighting in Sponza Scene

The video from the last post didn't turn out very well. It was smaller and lower resolution than the original, probably because it was compressed (again). So I'll just post images for now and hold off on posting more videos until I figure out a better system.

This time I want to talk about how 3DWorld does lighting in mostly static scenes. There are four types of lighting supported:
  • Directional lights with shadow maps (sun and moon)
  • Indirect lighting from sun, moon, and sky (as an area light source)
  • Static point lights "compiled" into the scene such as room lights and streetlights
  • Dynamic point, line, and spotlights (large number, but no shadows or indirect/ambient)
The directional lights are conventional OpenGL lights with standard shadow maps, nothing really too new. Indirect and static lights are precomputed using ray/path tracing and stored in a matrix + texture. Dynamic lights use textures as an acceleration structure that's traversed in the fragment shader. I'll explain these last two in more detail below.

Indirect Lighting

Indirect and static scene lights are precomputed using ray/path tracing across multiple threads and stored in a 3D volume texture that covers the entire scene. There is also an option to store the data sparsely for scenes that don't really fill a cubicle volume. This data is initially stored in a 3D array on the CPU side and transferred to the GPU once at program startup and also incrementally as lighting changes. There are several components to this lighting:
  • Sun indirect: Updated interactively as the user moves the sun position in background threads (several seconds lag for computation time). Stored as a weight so that changing the sun color or intensity can be done efficiently without recomputing the ray intersections.
  • Sky/Cloud indirect: Precomputed for a large number of point light source emitters positioned in a hemisphere around the scene, and constant for a given scene. Stored as a weight so that the sky color can transition between light blue and near black over the course of a day without recomputing ray intersections.
  • Static point light sources baked into the scene as either point lights or arbitrary area lights. These are mostly for fixed lighting such as lights in the ceiling, outside in street lights, fixed position fires, etc. These lights can have high quality indirect lighting (ambient) and aside from pre-processing time they are "free". They can be combined with dynamic lights so that the combination has some amount of dynamic to it.
This type of lighting produces very nice and close to physically correct soft shadows, ambient occlusion and color bleeding effects. Path tracing does produce great results when you have the CPU time to do it correctly and allow for large numbers of light bounces on a variety of surface types, including partial transparency. For example, here is a screenshot of ambient lighting applied to the Sponza scene:

Crytek Sponza scene with shadows and indirect lighting from both the sun and sky at 335 FPS
Note the green, red, and blue color bleeding on the pillars in the back due to light reflecting off the colored cloth. Note the soft shadow of the large pillar in the top right of the image. Also note the orange glow from a fire on the floor near the back wall which has been added as a static light source. Here is another view from below:

Crytek Sponza scene with fires that produce soft shadows and indirect lighting at 421 FPS
This is a view of the fires that were placed in each corner of the bottom floor of the Sponza atrium. Each of these lights is static and compiled into the scene, but also has a dynamic light placed at the same location that flickers, giving a sense of dynamic intensity to the fire. You can see the shadow of the top of the urn (or whatever it is) on the left side - but that's really a trick, the light is actually a spotlight shining up. Note the normal mapping that gives more 3D volume to the pattern on the bottom right. All types of light sources support normal maps - and specular maps as well, though you can't really tell in these screenshots. Those horizontal black strips in the middle of the pillars are probably incorrect texture UVs from the original model.

This Sponza model was imported from Lightwave Object file format. The original object file was downloaded from

This runs at an amazing 400 FPS (frames per second) because the indirect lighting is implemented as a 3D texture lookup in the fragment shader with no ray marching or loops and almost no CPU work done per frame. In this example I'm using a 128x128x256 RGB (red, green, blue) texture, which has 2M entries and takes a mere 6MB of GPU memory. In reality the size of the texture is limited by the CPU computation time of the path tracing. For this scene, it takes about 10 min. to path trace on a quad core CPU with hyperthreading (8 threads). [Okay, so it's really 8MB of texture since I'm actually storing it as RGBA and using the alpha channel to store volumetric smoke/fog information, but I'll explain that in a later post.]

But what about normals? Don't you need to store at least 3 values in the 3D texture for each face direction {X, Y, Z}? Well, there's a trick to this. Instead of storing ray intersections in the matrix, I store something like lighting flux for each of the RGB channels. Each photon leaves some light in each matrix cell that it passes through, not just in the final cell the ray hits along its path. If you take the difference between two adjacent cells in one dimension (say X), you can determine how many of those photons' paths ended between those two cells. If the delta is large we know there is some sort of wall there that is blocking the light. So what we do in the shader is bias our texture lookup by half a grid cell/texel in the direction of the object normal in world space. For example, if the wall is facing into a bright area, our normal will point toward the light and move our lookup into the middle of a well lit cell where many photons have passed and deposited their light. If the normal is facing into a dark wall or corner, this will move our texture lookup into an area inside of the wall where few photons reached and give us a darker lighting value. It's not physically correct, but it looks plausible.

There is another advantage of storing light this way. If we add dynamic objects to the scene, they can pick up the indirect lighting even if they are in the middle of the air far from any ray intersection points! They don't need to be present when the original path tracing is done. We just do a volume texture lookup for the dynamic object's location biased by its normal, and as long as the object falls within the texture (the scene bounding cube) we have valid lighting that changes as the object moves. The change is nice and smooth too due to the trilinear texture filtering on the GPU.

Dynamic Lighting

Dynamic lights use several textures as a world-space acceleration structure that's traversed in the shader on the GPU to reduce the number of lights that have to be processed for each fragment. The number of light sources can be very large, currently up to 1024, but for efficiency they should be small in radius/area of effect. There is no limit to the number of lights that can affect a given pixel/fragment, though it certainly does affect frame rates. They also don't cast shadows (yet). Dynamic lights have diffuse and specular components and can be point lights, spotlights (point + direction + angle), or real analytical line lights such as laser beams, which I may post screenshots of later.

This is all made efficient using an acceleration structure that's encoded as three textures:
  • Grid Bag Matrix: This is a 2D or 3D 32-bit integer texture that maps world space position to a {start, end} position within an index texture. We use this to find the set of lights that contribute to the fragment at a given world space position. 2D indexing (X,Y) is much simpler and seems to be faster due to reduced texture memory usage, though can be slow when there are a large number of dynamic lights at the same (x,y) position but different z values. .. But I really should try 3D textures again on my newer Nvidia card.
  • Index Array Texture: This is a 1D 16-bit integer texture that maps to indexes of dynamic light sources. Each grid bag element refers to a contiguous range within this texture. This extra level of indirection effectively allows us to store a variable-sized array within each texel of the grid bag. This is important since current GPUs don't allow dynamic memory allocation.
  • Dynamic Lighting Texture: This 1D 16-bit float RGBA texture stores all the lighting parameters. Technically it's a 2D texture since the lighting parameters don't fit into a single RGBA value and if stored as a single row may exceed the max dimension of a 1D texture (8192 on my old ATI card). Each light is a 16-bit float stored as three RGBA values: {, radius}, {color.rgba}, {, beamwidth}. Line/cylinder light sources store the end point of the line in the direction field.
The code to use these textures to determine which lights contribute to a given point and to calculate the lighting is usually run in he fragment shader, but can also be in the vertex shader.

This lighting system is fairly complex but pretty fast, supporting hundreds of small dynamic lights in realtime. The lights are normally from weapons, explosions, fires, glowing fragments, the player flashlight, etc. I like to use random colored lights for testing since it's a little more stable and repeatable, and more obvious when something is wrong. Here is a screenshot of the Sponza scene with 100 moving colored lights:

Crytek Sponza scene with 100 Dynamic colored lights at 95FPS
Note that you can see some of the normal mapping at work on the sides of the column of the right. I should have put more effort into finding good viewing positions and angles to capture normal mapping. This would also have been better in a video. The lights use collision detection to stay inside the open air of the scene and also cast shadows, though you can't see the shadows at night. Also, you can see the specular reflection of the rightmost yellow light on the shiny floor.

I'll note one odd thing about this screenshot: The blue lights look purple when viewed in Windows Photo Viewer! I originally tried taking the screenshot using 3DWorld's internal screenshot capture function that uses glReadbuffer() and ligjpeg to write it out, but noticed the purple lights. Then I took a screenshot using Fraps (the one posted), which still had purple lights. Now that I see it on this page the lights are in fact blue, so what's going on here??? I kept the Fraps image anyway since it seemed to be better quality, which may just be due to a difference in JPEG compression level.

Wow, that was a lot of text, but it took orders of magnitude less time to write this up than it took to actually write, debug, and test the code. If anyone is interested I might be willing to share some of my C++ and GLSL shader lighting code. It's a bit messy though, and deeply integrated into 3DWorld, and I don't want to open source everything (yet). I would certainly appreciate some feedback on what I've done here.

Wednesday, December 10, 2014

House Scene Video Test

This is my first video recording with Fraps. The original AVI file was 110MB, but I was able to compress it down to 6MB using Movie Maker in Windows. I'll have to work on my video creation skills before I post any really long videos, but for now I just want to see if it works.

This is a scale model of the house where I grew up in Pennsylvania. It's defined in my custom text file format that's powerful but not very user friendly. The objects are mostly cubes, spheres, cylinders, cones, extruded polygons, triangles, and quads. All of these objects are volumetric so they have full physics enabled with collision detection, and can be procedurally edited and destroyed in-game. I'm also able to import heightmap images and place grass, plants, trees, hedges, and water. The vegetation is also destroyable and moves in the wind. Almost all objects cast shadows. The indirect lighting is precomputed using multithreaded path tracing and consists of both sun and sky lighting (to be described in more detail later).

This makes for a good test scene, though I do have higher quality models that I can post screenshots and videos of later.

Monday, December 8, 2014

Infinite Procedural Terrain Features + Screenshots

Today I'll post some screenshots of the 3DWorld "Tiled Terrain" mode. This is a viewing only mode (no gameplay) so I don't need to figure out how to make videos (yet). For some reason the screenshots seem duller than the actual game, possibly something to do with color temperature? The colors are actually much brighter on my new computer with an Nvidia card than on my other computer with an ATI card, where (0,0,0,1) is very black.

Tiled terrain mode is a scrolling terrain that follows the camera. The terrain data can be entirely procedurally generated on either the CPU or the GPU out to an unlimited distance; it can be loaded from a 16-bit heightmap of up to 32k x 32k pixels; It can be created through realtime user editing with brushes; or some combination of those sources.

I have added support for the following features (all realtime and configurable by the user in realtime):
* Procedural terrain with static and dynamic LOD, shadows from terrain, vegetation, clouds, and scenery.
* Water with view-dependent opacity and reflectivity, per-wavelength light attenuation, waves, full scene reflection, caustics, and foam.
* Pine tree forests of up to ~1M visible trees out to ~10Km view distance with dissolve to billboards in the distance.
* 5 types of deciduous trees with hundreds of fully procedural meshes that can be instanced over 10K times and custom normal/texture mapped impostors that fade in with distance.
* Huge fields of procedurally placed grass, flowers, and plants that extend to the horizon and blow in the wind, with soft shadows.
* Rocks, logs, stumps, and other types of ground clutter.
* Two-layer procedural animated cloud layer with fog and atmospheric effects + soft shadows on the ground.
* Dynamic weather effects such as rain, snow, lightning, and wind, day/night cycle, etc.
* User-controlled day/night cycle and nighttime starfield.
* First person shooter and flight simulator cameras with collision detection.

Here are some screenshots. Note that this runs at > 100FPS at 1080p and the player can actually move through the world at a nearly unbounded speed.

Island lake with grass, flowers, pine trees, and snowy peaks

Distant mountain and hills (Mt Rainier from 16k x 16k Puget Sound dataset with increased water level)
10K procedural trees out to the horizon
That's it for today. Later I'll try to take some time to explain how I created all of this. Also, at some point in the future I would like to make a game that uses this game engine in tiled terrain mode, but I'm not entirely sure what type of game to make.

3DWorld 3D Game Engine Intro

This is my first post of my first blog. Let me start with one thing: Graphics development is my hobby, not my job. I don't expect to make any commercial products or get paid for any of this work (yet). My real job is in EDA software development - but there are similar areas of the two fields. For example, I wrote a layout viewer that combines graphics algorithms and EDA algorithms.

This blog will be about my 3DWorld game engine and computer graphics in general. I started working on the 3DWorld project way back in 2001 when I took CS184 Intro to Computer Graphics at UC Berkeley. I wrote an entire game engine in OpenGL from scratch and it has many of the elements used in commercial games, plus some new things I invented. I have two modes - landscape and universe. Well there are really two versions of landscape mode: finite and infinite, so maybe there are really three modes.

The landscape mode has a tiled terrain with generated trees, scenery, water, grass, etc. The user can walk around in an infinite generated virtual world, or I can load landscape data from USGS DEM databases and Google maps. The finite worlds (generated either from finite procedural data or other real-world sources) tend to be more interactive and game-like, but they're, well, finite and less interesting. There is also a geometry file format that can be used to create buildings and stuff like that out of primitive objects (triangles, voxels, or parametric volumes). I created my parents' house and a 4 story office building down to small details. I have a first person shooter "smiley killer" game in there with animated 3D smiley faces. It's pretty funny but also violent as you can kill them in various ways with more than a dozen weapons (and they fight back!) You can shoot them, blow them up, set them on fire, crush them, freeze them, poison gas them, etc. Pretty much everything in the game is dynamic and destroyable with shadows, high quality lighting, very real physics, AI, etc.

The universe mode is more of a space combat game in an infinite generated/procedural universe. It supports multiple governments, fleets of ships, planet colonization, space combat, interstellar travel, etc. The AIs are very good. I have all the real planetary physics in there but on a smaller scale so that planets and stars are closer together for reduced travel time. Everything moves under the influence of gravity (including all stellar bodies) in a reduced timeframe. The ships are very unique and animated, and can be damaged etc. They have fighters, short and long range weapons, "personalities", and all that stuff. I even have code to generate star/planet/moon names. Lately I've been moving all the planet rendering into a single vertex/fragment shader and it looks very real.

Both of these modes can handle larger environments and more dynamic objects than other games I've played. The landscape mode can support tens of thousands of objects and tens of KM view distance, and the universe mode can handle thousands of ships in huge armadas, all with their own AIs.

Since I have everything written and working already (though always in progress), I can't really give my step-by-step progress like I see in other blogs. I can explain some of the ideas and algorithms I came up with, and the problems I ran into with their solutions. I need to figure out how to post screenshots here, and if I can manage to take videos of 3DWorld I'll try to put them up as well.