voxels/thru : 2011

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

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

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:(

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.

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.

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