Sunday, February 8, 2015

Volume Lighting Effects with Smoke and Fog

This past week or so I've been working on improving the volumetric lighting of smoke and fog in 3DWorld. The engine supports full-scene volumetric smoke in a uniform 3D grid, as well as full-scene uniform fog. Smoke is generated by weapons, fires, and explosions in gameplay mode (first person shooter). Smoke and fog use the same algorithm and code, and use the same data, so we can only have one enabled at a time. The only real difference is that smoke is dynamic and varies over the volume vs. fog, which is uniform and constant (= more efficient). So I'll just refer to it as "smoke" here.

Each frame, the generated smoke is accumulated and diffused through open spaces in the scene, with a bias that pushes the smoke upward over time so that it accumulates near the ceilings. Most of the time I use something like a 128x128x64 grid, which is a reasonable tradeoff between quality and performance. Now that I have a new computer + GPU I might be able to get away with a higher resolution, though it's nice to make everything a power of 2, and increasing by 2x in all three dimensions is 8x more volume data to store and process. 4MB of texture data for smoke density + RGB indirect colors is a reasonable amount of data to generate and upload to the GPU each frame, but 32MB is a lot.

The smoke effect is implemented in my GLSL fragment shader of every material used in the indoor scene. It's generally too expensive to use on vegetation due to high pixel overdraw, but that's okay, the grass and trees are all outside and can be smoke-free. Standard fog without volumetric lighting can still be used on the outdoor parts of the scene. To get the true volumetric effect, smoke can't be explicitly rendered in a way that modifies the dept buffer. The individual smoke puffs can be rendered that way, but it doesn't make a convincing room full of smoke.

For each triangle fragment of indoor geometry we need to do a 3D volume ray traversal from the fragment (point on the scene geometry) to the camera/player/eye in world space, and accumulate light along the ray to include the effects of both forward and back scattering. The shader performs this ray marching in a loop, where each iteration:
  • Looks up the smoke density and local indirect lighting in a 3D texture that's incrementally updated each frame
  • Computes the forward and back scattering at that point using the smoke density and color
  • Checks the scene shadow map to determine if the point is visible to the sun and adds sun light
  • Finds any nearby dynamic light sources and adds their light contributions
In the real world we have a set of differential equations with exponential relationships between the variables, but I'm not trying to write a physically correct (slow) model here. I want it to be as simple and fast as possible, and also easy to tweak to get the effects I want. So I just went with a simplified linear equation, and the code looks like this (edited/simplified from the original shader):

vec3 dir      = eye_pos - vpos; // pos to eye
vec3 normal   = normalize(dir); // used for dynamic lights
vec3 pos      = vpos; // world space
float nsteps  = length(dir)/step_delta;
int num_steps = 1 + int(nsteps); // round up to nearest int
vec3 delta    = dir/(nsteps*scene_scale); // world space delta for each iteration
float step_weight  = fract(nsteps); // needed to remove sharp transitions (popping)
float smoke_sscale = SMOKE_SCALE*step_delta;
vec4 cur_epos   = fg_ModelViewMatrix * vec4(vpos, 1.0); // world => eye space
vec3 epos_delta = fg_NormalMatrix * delta; // eye space delta
 
// smoke volume iteration using 3D texture, pos to eye
for (int i = 0; i < num_steps; ++i) {
 vec4 tex_val = texture(smoke_texture, pos.zxy); // rgba = {indir_color.rgb, smoke}
 // add dynamic lighting
 tex_val.rgb += add_dynamic_lights(pos, normal); // world space
 // add sun light with shadows
 const float smoke_albedo = 0.9;
 tex_val.rgb  += smoke_albedo * get_shadow_map_weight(cur_epos) * light.diffuse.rgb;
 cur_epos.rgb += epos_delta; // move position in eye space
 // final calculation at this step
 float smoke  = smoke_sscale*tex_val.a*step_weight; // smoke density
 color        = mix(color, vec4((tex_val.rgb * smoke_color), 1.0), smoke);
 pos         += delta*step_weight; // move position in world space
 step_weight  = 1.0;
} // for i
return color;
 
This shader does a ton of work, over 100 iterations of this loop per fragment, where each iteration does a 3D texture lookup, shadow map texture lookup, lighting computation, and various vector floating-point math. All this done at 1080p = 1920x1080 pixels. It hasn't been practical to use this approach until I got my new computer and GPU (GeForce GTX 770), where I now get at least 60 fps. That's good enough for this one effect, but not good that this single effect takes most of my allocated frame time. Oh well, maybe I can optimize this more later. If I was using a deferred rendering pipeline I could do the volume lighting on a lower resolution (half? quarter?) target then upsample and blur it. But I'm doing this with a forward renderer, which means I need to process every fragment independently.

Now that I have this effect working, I can have fun setting the scene on fire to get some nice looking volumetric smoke. The plasma cannon does a nice job of creating fire and smoke. Here is a screenshot of the lobby area of my office building (modeled by myself). The fires are out, but the room is filled with smoke, and you can see the shafts of sunlight coming from the windows around the stairwell above.

[Note: I'm not sure why the left side of these screenshots has a tiny strip of pixels from the right edge. It's not clear what stage of my screen capture, image resize, and bmp->jpg compression did this.]
Sunlight filtering down between the stairs, producing light shafts in a smoke-filled room.
If you look at the floor, you can see that the sunlight isn't very strong. That's because I also compute a shadow term for each fragment that accumulates smoke along the direction of the sun light to produce soft partial shadows due to the smoke itself. This is a nice effect, but not one that would normally be noticed without me pointing it out.

Over time, the smoke will dissipate as it diffuses through the air, up the stairs, and out the doors. If I was to shoot out the windows, the smoke would quickly escape the building and the air would clear up in a few seconds. This is because the smoke diffusion algorithm uses dynamically updated flow vectors for each cell that determine the rate at which smoke can flow between that cell and the adjacent cell in {x, y, z}, based on cross sectional area of a 2D cut. When the scene is modified/destroyed, this data is updated, and the smoke diffusion algorithm incrementally updates the 3D texture across several frames.

Here is another screenshot showing high contrast light and shadows caused by a skylight in the ceiling. Volumetric smoke is added when the smoke puffs rising from the fires hit the glass plate in the ceiling. I had to use a pretty small step size of 0.2x cell grid size (5 steps per texel) to remove the aliasing effects at the shadow boundary, which hurt the frame rate. There is still a small amount of aliasing present if you look at the right angle.
Light from the overhead skylight scatters in the smoky room to produce volumetric shadows.




Dynamic and static scene lights also contribute scattered light to smoke. As I've shown in previous posts, 3DWorld supports hundreds of dynamic point and line light sources. These can be made to illuminate smoke particles as well as scene geometry, though this decreases the frame rate to only 30 fps in some cases. In this screenshot you can see the glow/halos from the laser beam line light source and the blue floating point light source interacting with a smoky basement.

A laser beam and blue floating point light illuminate the surrounding smoke, producing a glow due to light scattering.

Finally, here is a screenshot of my "God Rays" implementation in tiled terrain mode. In this case there is no 3D volume texture, since the scene is "infinite" in size, so the cloud density is procedural. The shader is different, but the general idea is the same. I'm evaluating 4 octaves of Perlin noise at every step along the ray, for every fragment (pixel) of every object in this scene, at > 2M pixels, so I only get 22 fps. This is a very brute force solution, so it's impractical to have this effect in a realtime engine, but it makes a pretty picture:
God rays from sun filtering through rain clouds in tiled terrain mode.

I still have more work to do, mostly improving the performance, but the results look pretty good so far. I'll have to see if there's some way to do the ray marching on a lower resolution image. Or maybe I can find a way to decrease the number of steps and use some kind of blur to remove the aliasing and noise from the shadow map. There are plenty of papers and presentations available on this topic. Overall, this volumetric scattering approach produces some pretty nice effects.


Sunday, January 25, 2015

Voxel Terrain Generation and Rendering

This time I'll present 3DWorld's voxel terrain system.

I'm generating a 3D array of noise values using different noise functions, computed either on the CPU or on the GPU using a custom fragment shader. The current set of noise functions supported are Perlin noise, Simplex noise, and sum-of-products-of-sines noise (of my own invention). They all seem to produce the same sort of lumpy terrain; in fact, the only real difference is computation time. Naturally, it's faster to generate noise values on the GPU, though reading back all that floating-point data takes around half the time of the CPU noise generation. This inefficiency is partly because I have to generate the volume in 2D slices, to match a 2D frame buffer. If anyone manages to invent a 3D frame buffer then let me know - or I suppose I could give in and use Nvidia-specific compute shaders or CUDA. In the end, it only takes 200ms to generate 16M noise values (64 slices) for a 512x512x64 scene, which comes to 64MB of data.

A big array of noise values is great, but it needs to be rendered. I chose to use the Marching Cubes algorithm because it's fairly simple (compared to the alternatives) and the crazy lookup tables needed for MC can be found online. There are some ambiguous cases in MC, but they tend to not show up often in the scenes I create and I prefer simplicity and efficiency over perfect quality, at least for now. So I can use MC to get triangles, then connect them together and compute the shared vertices so I can render with indexed triangles. This seems to be the most efficient way to render large triangle datasets using OpenGL, and is more compact than storing individual triangles. I divide the scene up into XY tiles (I use Z=up). 16x16 tiles seems to work well, and this division gives some nice benefits:
  • Each block can be generated independently, so I can use openmp to run separate threads on each core. 8 threads (4 core + hyperthreading) gives me about a 5.5x speedup.
  • View frustum culling can be used to drop invisible blocks when rendering
  • Individual blocks can be modified, which is fast enough for realtime voxel editing

Of course I skipped a few steps here, including handling of the mesh boundary, clipping the bottom of the volume with the heightmap floor, removal of disconnected "floaters", etc. This is all pretty standard stuff so I won't go into all of those details. One more important thing is lighting: these voxel scenes just don't look right with simple direct lighting. They need real ambient, and fortunately it's easy to compute ambient occlusion by ray marching through the 3D volume and tracking the visibility of each voxel (again using openmp). I also run path tracing on the triangle mesh like in my previous lighting post with the Sponza scene screenshots. This gives multiple bounce indirect lighting from the sun, moon, etc. for each voxel, which is recomputed (using openmp) when the light sources change.

Here is a screenshot of a 128x128x128 voxel rock/mountain that uses triplanar texturing with different textures + procedural texture selection to give it a variety of rock/grass features. I also placed some dynamic grass blades on the top surfaces of the rock. The shadows and ambient occlusion really bring out the dark crevasses in the rock and make it come to life.

Voxel mountain covered in grass, with indirect lighting, ambient occlusion, and shadows.


Voxel mountain with longer grass blades and denser grass.


Here is another screenshot of a 512x512x64 voxel snowy/icy landscape. The normal maps on the surfaces add nice specular highlights to the snow. The ambient lighting and shadows give depth to the scene, and the indirect lighting is responsible for the blue vs. white coloring. The blue areas are mostly lit by the sky but the white areas include indirect reflections from the sun on the snowy ground and icy walls. I have the indirect term set higher than what is realistic to make the indirect lighting stand out.

If you look at the ridge line on the right, there are some strange cube shapes placed there. These are the results of my voxel editing tests on this scene. I have implemented realtime addition and removal of volumes using different brush shapes (sphere, cube, etc.), sizes, and weights. These brush strokes can be saved to files and re-applied when the scene is loaded after the procedural generation is finished. I decided to store the brushes instead of the raw volume data because it allows for tiny file sizes. It would take a huge amount of time for a user to accumulate 64MB of brush strokes to make the save file exceed the size of the floating-point volume data!

Procedurally generated ice/snow caves + user edits with indirect lighting, ambient occlusion, shadows, and normal mapping.

Here is a zoomed out view of the entire scene - there is a surprising amount of data here! You can easily get lost walking around in this cave system, which is almost entirely connected and walkable. This is 16M voxels, which is converted to around 2M triangles for rendering. I'm getting a nice 300 FPS here with all the effects turned on, even though the camera is too far away to see the details. Oh, and that round hole in the bottom left is a tunnel I made horizontally through the entire scene.

Zoomed out view of voxel ice cave scene.

And finally, that same scene with more interesting lighting: 100 moving, light emitting, colored spheres. This time the sun and moon are both below the horizon for a nice dark night, which makes the colorful light sources stand out. The normal mapping produces some nice specular reflections, though they're a little hard to see at this view distance. I'm still getting a high frame rate of 130 FPS here, even with all the lighting computations for 100 lights.

Ice caves scene with 100 dynamic colored lights.

If I was more of an artist, I would show you some cool screenshots of what I created with the voxel editing tools. However, I was never really into art, and the procedural terrain looks pretty good to me. I'm hoping that I can integrate voxel content into other 3DWorld scene types in the future. 3DWorld already supports the addition of non-voxel polygon objects into voxel-based scenes. For example, I can put the Sponza atrium model on top of these voxels or inside of a large cave. The first person shooter "smiley killer" game can be played in these caves (if you could ever find something to shoot at in the maze). [Yes, I know, I need to post something about that game here since it's not just an engine.]

Well, that's about it for this post. I'll try to put some more screenshots of cool stuff I created with voxels into a later post. I'm sure there's a lot I can do with 3DWorld's voxel framework.

Sunday, January 4, 2015

Procedural Universe and Planet Generation and Rendering

It's time to introduce the "universe" mode of 3DWorld, which is quite a bit different from the other "terrain" modes. This mode doesn't share too much of the high-level classes, functions, and control flow with the rest of 3DWorld, but it does share a lot of the low-level infrastructure. It can also be used to draw a real, animated nighttime starfield (with planets, moons, rings, etc.) in the background of terrain mode.

Universe Objects
There are two classes of objects in universe mode: procedural, natural universe objects and dynamic, manufactured objects such as space ships, their projectiles, and their particles. The procedural universe objects are generated in a hierarchy of cell -> galaxy -> solar system (with star) -> planet -> moon. Each cell contains several galaxies and is identified by 32-bit integers for {x, y, z} grid positions, so the universe is effectively a 3D grid of 2^32 cells, and contains some 2^98 galaxies. I call that universe infinite - in fact any procedural world where you can move at max speed in the same direction for a lifetime without reaching the end is more of less infinite in size. The objects in the universe have compressed scales so that you're not flying for hours in empty space to get from one planet to another, or one star to another. Even with the compression, there are still issues with floating-point precision, so I had to use custom float + int coordinates in some places, and double precision in others.

The universe contains the following physical objects at various levels of the hierarchy:
  • Stars (one per system, up to 500 per galaxy)
  • Nebulae (one or more per galaxy) - volumetric with 3D ridged perlin noise
  • Asteroid fields (multiple per galaxy, either inside or outside of a system)
  • Asteroid belts (in some systems and around some planets)
  • Planets (up to 15 per system)
  • Moons (up to 8 per planet)
  • Comets (spawned near the player, out of view)
Everything is procedurally generated, more or less from scratch. Since the player can travel between star systems in a fraction of a second in hyperspeed, everything needs to be generated within a single frame. In the end I had to move almost all the generation and rendering into large shaders up to 600 lines of GLSL code. So far I haven't been able to find any other online tool/product/demo that draws an entire planet from scratch using a single shader in a single pass. Well, it's not exactly a single shader - I have a shader generation framework that takes bits and pieces of GLSL code and combines them together to create a shader customized for the particular class of planet, moon, etc. being rendered. So it's one shader/pass per planet, but different shaders for each type of planet or moon. The types of planet that 3DWorld supports consist of:
  • Terran/Earth-like: Procedural ground/vegetation color, normal map, water, snow/ice coverage, clouds with shadows, and atmosphere
  • Alien: Colorful terrain, toxic clouds and atmosphere with shadows
  • Ocean/Water: Clouds and atmosphere
  • Ice: Gas clouds/atmosphere
  • Rocky: Procedural height generation in vertex shader, normal maps at multiple octaves, shadows
  • Hot/Lava: Lava instead of water, possible toxic atmosphere, normal maps, colored
  • Gas Giants: Multiple layers of procedural clouds, perturbed 1D color bands, animated procedural cyclone storms, soft cloud shadows
  • Moon: with procedural heightmap and craters generated within the shader using normal maps
Each planet can also have rings that cast and receive proper analytical soft shadows, asteroid belts, and one or more moons that revolve around it. All objects rotate and revolve according to the laws of planetary physics. In addition, each object is given a unique generated name.

In addition to creation and rendering, 3DWorld provides a framework for physics simulation, collision detection, and modification of the universe. There are query functions for gravity, temperature, and lighting at any point in the universe. 3DWorld supports efficient object line intersection tests, sphere intersection tests, nearest object queries, future collision queries, and other functions necessary for interacting with the universe. Objects can be destroyed and renamed by the player, and modifications can be saved to disk and reloaded in future sessions.

Screenshots
Here are some screenshots of planets and other universe objects, all procedurally generated and rendered with custom shaders. There are no predefined textures used, all planets are unique, and I'm getting framerates of hundreds of FPS. Note that the planets are closer together than they would be in reality, to make the scene look more interesting with multiple planets in view at the same time.



Volumetric procedural nebula that the player can fly through, using 3D ridged perlin noise. Each one is unique.

Star with asteroid belt and nearby planets, with stars, galaxies, and nebulae in the background.

Closeup of system asteroid belt with 10K large rotating asteroids (perturbed spheres with hardware instancing and LOD) and 1M small asteroids (point sprites). All asteroids rotate around the star, and can be collided with, selected, and destroyed.

Gas giant with swirling animated clouds, animated storm cyclones, cloud shadows, lightning, rings with animated asteroids and particles, soft shadows to/from planet <=> rings, and indirect moon lighting.

Terran planet with procedural terrain (8 octave 3D ridged noise multifractal), normal mapping, snow covered mountains, ice at poles, animated swirly clouds with shadows, specular snow, ice, and water, and atmosphere.
Icy planet near the asteroid belt with some snowy peaks and green forested areas. Note the moon in the back left.

Planet with clouds, toxic atmosphere, and emissive lava glow (black body radiation). You can also see a distant comet in the upper right corner.

Rocky ice planet with nearby asteroids. The vertices are perturbed by evaluating noise in the vertex shader. All planets of this type use a constant/shared VBO of initial sphere vertices.

Ships
In the other category we have artificially created objects consisting of:
  • Space Ships
  • Starbases
  • Planetary Colonies
  • Projectiles (missiles, etc.)
  • Particles and Particle Effects
  • Explosions
This is the space gameplay part of universe mode, where the player engages in colonization and fleet combat with one or more AI-controlled sides. All of these objects are either initially placed in the config file, randomly spawned, created by the player, or created by an AI. We start with the ships, which can create other ships, colonies, projectiles, and particles. All of these objects can interact with universe objects (stars, planets, moons, etc.) and with each other. I'll make a later post with more ship details and screenshots.


Video Update

Here is a procedural universe fly-through recorded by 3DWorld. I fly my ship away from the battle, past a planet, into the asteroid belt, past the star, to a ringed gas giant, back and forth through a nebula, and back into a system to view a planet up close.


YouTube Video Link

At one point I fly my ship into an asteroid and bounce off, which shows how physics and collision detection work with every solid object in the universe. I also get too close to the star at one point and start taking damage, which is why the screen turns red and shakes. (I have the health bar and other UI elements turned off to reduce screen clutter.) The nebula is procedural, which allows the player ship to fly though it. All planets, including the gas giant and Terran planets in the video, are entirely generated and drawn on the GPU. I'm only sending a low-resolution, untextured sphere to the GPU for tessellation and rendering. Everything is generated seamlessly with no visible LOD transitions and no loading screens.

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 http://graphics.cs.williams.edu/data/meshes.xml

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: {center.xyz, radius}, {color.rgba}, {direction.xyz, 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.