Hiking the Contential Divide Trail(CDT) for the next 4-5 months. It is a 3,000 mile trail running from the US/Mexico Border in New Mexico to the US/Canada border in Montana.
I'm starting April 20th at Crazy Cook, NM. Will walk across New Mexico, Colorado, Wyoming, and Montana, and some of Idaho.
Old post by Tim Sweeny regarding Garbage Collection
So UClass/UFunction/UProperty(which still exist in Unreal) etc. appear to date to at least 1999
Tim Sweeny 1999
Sun Shafts & SSAO
Added screen space sun shafts, based on this article from GPU Gems 3.
Also added basic SSAO(screen space ambient occlusion). Right now it is just using the depth buffer. For performance I will switch this over to using a downsampled depth buffer at some point in the future. There are also some alternative methods that take into account surface normals that tend to generate more accurate results, so I might add one of those methods later.
 |
| Ambient Occlusion |
Atmospheric Scattering
Atmospheric scattering based on Eric Bruneton's Precomputed Atmospheric Scattering.
I really like the look this algorithm gives, I'm only part way through implementing it so not everything is working, or at least as well as I'd like.
His algorithm produces three colors, inscatter color, ground color, and sun color. Although Bruton's sun color looks good in his screen shots, in the demo it looks rather bad; I believe the demo is an incomplete version.
Part of the algorithm requires the distance from the viewer, here I am reconstructing based on the depth buffer, and to get this working I went ahead and implemented a proper deferred renderer, so yeah!
Oh, and the first time I ran the atmospheric code this is what my planet looked like(precomputed table wasn't right )....
Deferred Texturing ?
One method I tried, that didn't end up working very well, was deferred texturing for the terrain.
The terrain texture coordinates are based on its world coordinates and normal. Using the GBuffer normal + depth buffer to reconstruct world position gave me what I needed.
And while this worked and produced identical texture coordinates, the gradients were not always correct, resulting in some nasty looking aliasing anywhere that the depth buffer contained a large difference between adjacent pixels(because originally they were separate objects).
My understanding is that the graphics card works on 2x2 pixels--
AB
CD
So the world coordinates are calculated in the four pixels, the difference between the adjacent pixels world coordinates is used as the derivative for MIP calculation.
But if pixel A was from a completely different mesh than pixel C, and 1000 meters closer to the camera, it ends up with really large derivatives and selects the lowest MIP--this is not what you want!
So everything ends up with a blocky/pixelated outline that shimmers and looks just awful.
If you passed down the derivative information perhaps you could work around it, but that is quite a large amount of extra data, and I didn't want to go down that route.
The terrain texture coordinates are based on its world coordinates and normal. Using the GBuffer normal + depth buffer to reconstruct world position gave me what I needed.
And while this worked and produced identical texture coordinates, the gradients were not always correct, resulting in some nasty looking aliasing anywhere that the depth buffer contained a large difference between adjacent pixels(because originally they were separate objects).
My understanding is that the graphics card works on 2x2 pixels--
AB
CD
So the world coordinates are calculated in the four pixels, the difference between the adjacent pixels world coordinates is used as the derivative for MIP calculation.
But if pixel A was from a completely different mesh than pixel C, and 1000 meters closer to the camera, it ends up with really large derivatives and selects the lowest MIP--this is not what you want!
So everything ends up with a blocky/pixelated outline that shimmers and looks just awful.
If you passed down the derivative information perhaps you could work around it, but that is quite a large amount of extra data, and I didn't want to go down that route.
Terrain Video
I made a short little video flying around the terrain, 1080p if you click on on the word youtube.
Terrain Blending
NOTE: the methods in this post are old & moronic, don't use them:)
Blending:
I've updated the terrain so that it blends seamlessly between different LOD's. Previously it would just switch from one LOD to the next without any attempt to blend, which looked pretty bad, especially if running the terrain at a fairly low detail setting.
Textures:
For now just using some random textures off the internet. Texturing is being applied using triplanar texturing. Currently it is just a global set of 3 textures, but eventually I plan to make it store per vertex a texture ID, so that the terrain can be, at least to some degree, painted upon.
 |
| Seamless blending & basic texturing |
Some blending details...
Typically terrain blending is done via vertex morphing & manual texturing blending, at least this is how most height field based algorithms work.
I am using voxels though. Rendered as chunks of triangles, essentially each LOD's meshes are unrelated to the next LOD's meshes. There is no real obvious way to morph between these meshes since they have nothing in common.
What I have seen done before is alpha blending between LOD's. Nvidia did this in their GPU terrain demo. I plan to use a deferred renderer, which generally runs counter to alpha blending, so I've modified this idea somewhat. Currently what I am doing is rendering high detail terrain into one set of buffers, and low detail/parent terrain into another. In post I blend them together based on a few different things. The overhead for this is actually surprisingly small, and eventually I will be able to blend the data together prior to lighting being applied, essentially dumping the result into the deferred gbuffer.
and cracks..
Are gone, mostly. I added a check so that if no data is found in the high details, it tries to fill it from the low detail, this seems to fix most cracks. I will probably expand on this to remove all cracks at some point in the future, but it removes most already.
 |
| Blue represents any location that was hole filled or crack patched, red represents places where fixes failed. (The sky is red, which is good since it is shouldn't be patched). |
Components system + Flow Graph
Like lots of other games, my game uses a component system.
This system is designed to allow for improved cache usage and easy parallelization.
It is loosely based on this article published by Insomniacs.
For cache friendly behavior all components of a given type live in contiguous memory, and are all updated together.
To specify attributes for components I have a Lua file, which for each component type indicates, among other things, how they should update(parallel, serial), and which other component types they depend on.
I use TBB Flow Graph to express dependencies, any component that has a dependency on another being updated prior to it, just lists that component as a dependency in the Lua file.
For instance this is the declaration of my Occlusion Rasterizer component in Lua.
reg("occlusion_rasterizer", no_inteface, TM.MULTI, 0.0, 3, {"commands"})
The parameters in order are:
name - name in C++, this matches them up
interface - specifies which interface, if any, the component implements, if Occlusion Rasterizer had implemented an interface this would be the name of that component. This allows for things like finding all components that implement a given interface.
parallel - either SINGLE or MULTI, SINGLE means each component of this type is updated sequencially, MULTI means they are all updated in parallel
time delay - how long between updates to this type, so if you want a given type to only update 4 times per second make this value 0.25 etc
count - how many components to reserve, this allocates a contiguous block of memory. It will grow as needed, but this allows for the equivalent of a vector.reserve()
dependencies - list of any components that must update prior to this component, TBB flow graph guarantees they will finish updating prior to this component updating. Occlusion Rasterizer depends on a command list being generated, so it lists "commands" as a dependency.
Each component type derives from a base component type in C++, currently this adds 12 bytes of overhead to each instance in 32 bit builds, and 16 bytes in 64 bit builds.
The base component contains this:
vtable ptr - 4/8 bytes. Removing this is possible but makes the system somewhat clumsier to use.
chain index - 4 bytes, which chain it is on, chains are a series of components
type - 2 bytes, each component type has a unique ID
offset - 2 bytes, index into the pool containing components of its type
I've been pretty happy with this system, my components are small self contained little objects, they are cache friendly, and can be allocated and destroyed in large numbers. Adjusting dependencies as new types are added is also a very simple since no recompilation is needed, just a chance to a Lua script file.
A major advantage of component systems, which I think does not get stated clearly enough, is how much glue code they save you from writing. Having to create classical C++ game objects and populate them with appropriate member data, worry about all the fragile and arbitrary hierarchies, and then writing all the systems that control them is a huge amount of unnecessary code.
This system is designed to allow for improved cache usage and easy parallelization.
It is loosely based on this article published by Insomniacs.
For cache friendly behavior all components of a given type live in contiguous memory, and are all updated together.
To specify attributes for components I have a Lua file, which for each component type indicates, among other things, how they should update(parallel, serial), and which other component types they depend on.
I use TBB Flow Graph to express dependencies, any component that has a dependency on another being updated prior to it, just lists that component as a dependency in the Lua file.
For instance this is the declaration of my Occlusion Rasterizer component in Lua.
reg("occlusion_rasterizer", no_inteface, TM.MULTI, 0.0, 3, {"commands"})
The parameters in order are:
name - name in C++, this matches them up
interface - specifies which interface, if any, the component implements, if Occlusion Rasterizer had implemented an interface this would be the name of that component. This allows for things like finding all components that implement a given interface.
parallel - either SINGLE or MULTI, SINGLE means each component of this type is updated sequencially, MULTI means they are all updated in parallel
time delay - how long between updates to this type, so if you want a given type to only update 4 times per second make this value 0.25 etc
count - how many components to reserve, this allocates a contiguous block of memory. It will grow as needed, but this allows for the equivalent of a vector.reserve()
dependencies - list of any components that must update prior to this component, TBB flow graph guarantees they will finish updating prior to this component updating. Occlusion Rasterizer depends on a command list being generated, so it lists "commands" as a dependency.
Each component type derives from a base component type in C++, currently this adds 12 bytes of overhead to each instance in 32 bit builds, and 16 bytes in 64 bit builds.
The base component contains this:
vtable ptr - 4/8 bytes. Removing this is possible but makes the system somewhat clumsier to use.
chain index - 4 bytes, which chain it is on, chains are a series of components
type - 2 bytes, each component type has a unique ID
offset - 2 bytes, index into the pool containing components of its type
I've been pretty happy with this system, my components are small self contained little objects, they are cache friendly, and can be allocated and destroyed in large numbers. Adjusting dependencies as new types are added is also a very simple since no recompilation is needed, just a chance to a Lua script file.
A major advantage of component systems, which I think does not get stated clearly enough, is how much glue code they save you from writing. Having to create classical C++ game objects and populate them with appropriate member data, worry about all the fragile and arbitrary hierarchies, and then writing all the systems that control them is a huge amount of unnecessary code.
Microsoft's vector and alignment
Can't use Microsoft's implementation of vector with aligned data, all because of one line.
void resize(size_type _Newsize, _Ty _Val)
Change it to
void resize(size_type _Newsize, const _Ty& _Val)
And everything works. But is hacking my STL files a good idea or should I use some other version of vector just for aligned data?
The standard was updated recently and indicates that 2nd version is now the correct way, so I believe this will be fixed eventually, probably the next edition of Visual C++, ah well-- I'll just hack it for now..
-edit(9/28/2013): this is no longer an issue in Visual Studio 2013, it works out of the box
void resize(size_type _Newsize, _Ty _Val)
Change it to
void resize(size_type _Newsize, const _Ty& _Val)
And everything works. But is hacking my STL files a good idea or should I use some other version of vector just for aligned data?
The standard was updated recently and indicates that 2nd version is now the correct way, so I believe this will be fixed eventually, probably the next edition of Visual C++, ah well-- I'll just hack it for now..
-edit(9/28/2013): this is no longer an issue in Visual Studio 2013, it works out of the box
Occlusion Culling #1
(this is a very old post, I no longer use any of this)
Recently I decided to try adding real occlusion system to my game. There are a bunch of different ways to accomplish this, here are some common ones.
1) GPU occlusion queries
2) Software rendering for occlusion testing
3) Manual artist created portals and other similar systems(like Quake)
#3 is a non-starter for me as I want a dynamic game world, and don't have artists to throw around.
#1 I have tried before, but found that the inherit latency of CPU->GPU->CPU too large. I tried cheating by issuing a query for each rendered object every frame, and simply not drawing in if it failed the query test from the previous frame, but this suffered from pop-in.
#2 has become rather popular of late, and it is the method I decided to try this time.
A software renderer could be implemented as either a rasterizer or a ray tracer, and since I already had support for ray casting into my scene, via Bullet, I decided to try that first.
I wrote a little program to generate depth map of the scene by casting rays through the physics system, it was trivial to parallelize it since each ray was independent of the others.
Unfortunately performance was not good , as it turned out Bullet just wasn't fast enough to be ray casting 20,000+ rays each frame. I believe part of this is the fault of my levels which have far more objects than a typical game.
So I went back on that idea and switched to rasterisation. I stumbled across this post on devmaster by Nick, which was very helpful in getting a basic triangle rasterizer up and running.
I am at the point now where I can rasterize the scene on the CPU and performance is overall much better than the previous ray tracing attempt. I haven't even parrallelized or SSE'd it yet and it performs quite well(rendering ~50,000 triangles).
For my terrain I am using convex hulls of each chunk, these typically use a small fraction of the actual number of triangles that the rendered terrain contains. Unfortunately the generated hulls aren't exactly conservative(meaning they sometimes extend beyond the bounds of the source mesh), so I am certain I will see situations where the occlusion system says something is occluded when it really isn't...
...more on this later.
Lua needs
Lua is great, but it is missing a few things..
1. continue -- although Lua 5.2 adds goto, which does allow you to simulate this, but I don't see myself using goto..
2. no ++ or += etc. -- don't know why this isn't supported, shouldn't be too hard to add with custom pre-compiler
3. metaprogramming --Lua just doesn't have any good support for this, have to manipulate strings to accomplish anything
1. continue -- although Lua 5.2 adds goto, which does allow you to simulate this, but I don't see myself using goto..
2. no ++ or += etc. -- don't know why this isn't supported, shouldn't be too hard to add with custom pre-compiler
3. metaprogramming --Lua just doesn't have any good support for this, have to manipulate strings to accomplish anything
Lisp
Recently I've been teaching myself lisp-- so far it seems like a very creative language, which I like, as I view creativity as one of the most important skills for a programmer to have.
There are like a million different versions of lisp it seems and no single standard implementation.
And for whatever reason I decided to write yet another...
My lisp compiles to Lua, I figured that LuaJIT2 is the fastest dynamic language VM around, so targeting it should allow my Lisp implementation to perform better than most. I had no experience with Lisp prior to this, but I certainly learned lisp fairly well while writing a compiler for it-- also improved my Lua.
It is somewhat different from the lisp norm in that it does not use lists and cons cells, instead I use a Lua table in array form. No named arguments either, although you can fake them just as you would in Lua. I also use { to introduce raw Lua code, and } to return to Lisp.
Still have to implement most of the library functions that come with most lisp implementations, and I'm sure I'll have to fix a few bugs in the compiler yet, but it is working, including support for macros.
I also saw that the creator of Lisp, John McCarthy, died a few days ago:(
There are like a million different versions of lisp it seems and no single standard implementation.
And for whatever reason I decided to write yet another...
My lisp compiles to Lua, I figured that LuaJIT2 is the fastest dynamic language VM around, so targeting it should allow my Lisp implementation to perform better than most. I had no experience with Lisp prior to this, but I certainly learned lisp fairly well while writing a compiler for it-- also improved my Lua.
It is somewhat different from the lisp norm in that it does not use lists and cons cells, instead I use a Lua table in array form. No named arguments either, although you can fake them just as you would in Lua. I also use { to introduce raw Lua code, and } to return to Lisp.
Still have to implement most of the library functions that come with most lisp implementations, and I'm sure I'll have to fix a few bugs in the compiler yet, but it is working, including support for macros.
I also saw that the creator of Lisp, John McCarthy, died a few days ago:(
Fast Grid Aligned Noise
Here is a method to produce noise faster than the traditional approach, such as perlin noise, where you sample the 8 integer corners and perform trilinear interpolation, with the limitation that it must be axis aligned and have a constant frequency for a given octave.
I'm focusing on perlin/improved noise here, not simplex noise, which is not axis aligned to begin with.
One of the slowest aspects of perlin noise is generation the pseudo random values for the 8 corners. Perlin uses a LUT, others use integer hashing(particularly necessary if you want to use SSE/AVX).
Say you want to generate a 3D grid 32^3 of noise values, this requires 32,768 calls to noise, and internally the generation of 262,144 (32^3 * 8) pseudo random values.
Many of these values are identical, how many depends on the frequency you are sampling at. The smoother the resulting noise is, the less unique pseudo random values were required.
This approach only requires P^3 pseudo random values, where P is always less than or equal to half of N(most often P is only a small fraction of N, it depends on the frequency). Even at half of N this only requires 4096 (16^3) pseudo random values.
One case where this is particularly applicable is when summing multiple octaves. In many cases 20+ octaves will be used. The outer octaves are very low frequency, there is no need to be calculating so many pseudo random values.
A second major optimization is the interpolation pass. These passes are separable. This means we can interpolate all of the X, then all of the Y, and then all of the Z. This reduces the number of interpolations required from (N^3 * 7) to (N*P*P + N*N*P + N*N*N).
Here is the basic algorithm for generating grid aligned noise. It is much more complicated than perlin noise, and much less flexible. But it is far faster. It also allows for the use of cubic noise with no visible grid structure. It operates on blocks of noise, instead of on individual samples.
This is described in the context of 3D noise, but can be applied to other dimensions.
I'm focusing on perlin/improved noise here, not simplex noise, which is not axis aligned to begin with.
One of the slowest aspects of perlin noise is generation the pseudo random values for the 8 corners. Perlin uses a LUT, others use integer hashing(particularly necessary if you want to use SSE/AVX).
Say you want to generate a 3D grid 32^3 of noise values, this requires 32,768 calls to noise, and internally the generation of 262,144 (32^3 * 8) pseudo random values.
Many of these values are identical, how many depends on the frequency you are sampling at. The smoother the resulting noise is, the less unique pseudo random values were required.
This approach only requires P^3 pseudo random values, where P is always less than or equal to half of N(most often P is only a small fraction of N, it depends on the frequency). Even at half of N this only requires 4096 (16^3) pseudo random values.
One case where this is particularly applicable is when summing multiple octaves. In many cases 20+ octaves will be used. The outer octaves are very low frequency, there is no need to be calculating so many pseudo random values.
A second major optimization is the interpolation pass. These passes are separable. This means we can interpolate all of the X, then all of the Y, and then all of the Z. This reduces the number of interpolations required from (N^3 * 7) to (N*P*P + N*N*P + N*N*N).
Here is the basic algorithm for generating grid aligned noise. It is much more complicated than perlin noise, and much less flexible. But it is far faster. It also allows for the use of cubic noise with no visible grid structure. It operates on blocks of noise, instead of on individual samples.
This is described in the context of 3D noise, but can be applied to other dimensions.
- Using the initial location and the frequency determine how many psuedo random values are required for N^3 cube of noise. The result should be a much smaller cube P^3.
- Generate all the pseudo random values required for P^3
- Now we must perform some type of interpolation to create a smoothed representation of P^3. Perlins approach can be used, it is fast and only uses linear interpolation, but it does exhibit some grid structure. Alternatively cubic interpolation can be used, although this requires sampling 4 values per axis, and that we have padded P by 1 on either side.
- Perform interpolation along X axis of P^3, this will result in a block of data N*P*P size
- Perform interpolation along Y axis, resulting in a block of N*N*P size
- Perform interpolation along Z axis, now we have the final result that is N*N*N in size and is properly interpolated.
To make it fast, operate on blocks that fit in the L1 cache.
I used this technique for a project I worked on about six years ago. It is very fast, but I'm not using it for my current project as the grid aligned and constant frequency requirements got in the way. It is also only really efficient when you need large blocks of noise, which my current project does not.
Just thought I'd document it. I'm sure someone else has done this as it is fairly obvious.
Just thought I'd document it. I'm sure someone else has done this as it is fairly obvious.
Pacific Crest Trail
I was gone for a really long time.
Hiked the Pacific Crest Trail(PCT) from Mexico to Canada, started May 1st, ended on Oct 9th.
It was the best time I've ever had, and along the way I met some great people.
Now back to what is commonly called the real world...
Just a few images from the entire 2650 mile trail--
Southern California, not just a Desert after all
The monument by the Mexican border
Eagle Rock
We are descending into Tuolumne Meadows
Hiked the Pacific Crest Trail(PCT) from Mexico to Canada, started May 1st, ended on Oct 9th.
It was the best time I've ever had, and along the way I met some great people.
Now back to what is commonly called the real world...
Just a few images from the entire 2650 mile trail--
 |
| Wilson, my soccer ball-- he lasted 800 miles |
One of many raging creeks in the Sierras
Muir Hut 
One of the 10 or so passes in the Sierras
Southern California, not just a Desert after all
The monument by the Mexican border
Eagle Rock 
We are descending into Tuolumne Meadows Geometry shader = BSOD?
So I am rendering some points and wanted to quickly visualize them as billboards. The geometry shader is a good way to do this so I wrote a GS to output a screen aligned triangle where each point would be. This works-- mostly, except when I randomly get a nice blue screen of death while looking at the output.
I wonder if I'm stressing the GS too much somehow. While I am only outputting 3 verts for each incoming vert, I am rendering millions of points. I've tried a few different variations of the shader and they all seem to eventually BSOD on me.
Hard boot restart each time it happens, grrrr.
I wonder if I'm stressing the GS too much somehow. While I am only outputting 3 verts for each incoming vert, I am rendering millions of points. I've tried a few different variations of the shader and they all seem to eventually BSOD on me.
Hard boot restart each time it happens, grrrr.
Terrain Collision
NOTE: this post is old and nonsensical but I'll leave it for now..
 |
| Testing terrain collision with the green blocks near bottom. Here they are about to drop over the edge of the cliff. |
 |
| Dropped a few hundred balls on terrain as stress test. |
Added terrain collision last week, but as I'm not using heightfields I had to use
something slightly different from the norm.
First I tried a pure triangle mesh based approach, I knew this would be slow as
hell and use a ton of memory but I wanted to have a working baseline to compare
against.
Initially for physics I used Havok,but after getting the basic triangle mesh collision working I switched to Bullet. Why? I don't have $100,000 laying around to
waste on a physics engine for which I only have access to the binary version--and Havok only supplies libs for VS2008, not VS2010 which I what I am using, although I was able to
get the 2008 libs working, also I just like having the source code.
waste on a physics engine for which I only have access to the binary version--and Havok only supplies libs for VS2008, not VS2010 which I what I am using, although I was able to
get the 2008 libs working, also I just like having the source code.
I'd used Bullet before so it was easy to get it switched over, and once I had
the triangle mesh collision set up I gave it a trial run.
the triangle mesh collision set up I gave it a trial run.
The triangle mesh collision used approximatly one gig of memory, although
generation speed for the btBvhTriangleMeshShape was fairly quick. I created a
task to generate collision and spread the work across the cores which made
generation faster.
generation speed for the btBvhTriangleMeshShape was fairly quick. I created a
task to generate collision and spread the work across the cores which made
generation faster.
I added spheres and boxes that I could drop onto the terrain to test the accuracy
and performance of the collision detection.
and performance of the collision detection.
A gig of memory for terrain collision was obviously out of the question so I began
testing convex hulls.
testing convex hulls.
Bullet has a btConvexHullShapewhich takes an array of vertices in floating point format. This worked and reduced memory usage by more than half. Still wasn't good enough though.
I wrote my own convex hull shape which I called
btCompressedConvexHullShape, as the name implies it uses compressed verts
(about 1/4th the memory per vert).
btCompressedConvexHullShape, as the name implies it uses compressed verts
(about 1/4th the memory per vert).
I also started using Bullets utility class btShapeHull. This class takes in
an array of vertices and produces a convex tri mesh with a greatly reduced
number of vertices. Feed it 2000 verts and get back a 14 vert convex mesh,
that type of thing.
number of vertices. Feed it 2000 verts and get back a 14 vert convex mesh,
that type of thing.
I feed the results of the btShapeHull back into btCompressedConvexHullShape or a btConvexTriangleMeshShape(favoring btCompressedConvexHullShape as they both seem to produce the same results and it uses less memory).
Memory usage for the physics simulation was greatly reduced at this point,
down to about 100 megs. There are still a few optimizations I'd like to do,
mostly to reduce the allocations taking place in the btShapeHull step, but
overall the performance and memory usage is fairly good at this point.
down to about 100 megs. There are still a few optimizations I'd like to do,
mostly to reduce the allocations taking place in the btShapeHull step, but
overall the performance and memory usage is fairly good at this point.
I've also got the physics simulation running as it's own task, with adding and
removing of objects done asynchronously. This helps because as you move through
the world a great many terrain chunks(each as a convex hull) are being added and removed.
Collision seems to be fairly accurate as long as I don't have it too far off
from the visual representation.
My gravity is currently just set using Bullets built in system, which is directional.
This means if I navigate to the side of the planet I can start dropping objects
and watch them bounce along through mountains and valleys for miles as they
travel along the edge of the planet.
Need to add a character control system soon.
Subscribe to:
Posts (Atom)