Over the past few days I have been working on a dedicated vector math library for my LiteGame engine.  I started out needing only a ray-box intersection test, but things have spiraled out of control and now I have loads of really neat and useful stuff in there.  I have been trawling a lot of my past projects in order to extract useful 2D vector algorithms from them, clean them up and throw them into this library.

The basic types so far are [vec2, ray2, box2, mat2, edge2, circle2, plane2] with a horde of functions to operate on all of them.

I wanted some kind of testing for this library, so I have created an interactive test suite currently with 16 different demos using various features of the library.  Above is a video of the test suite in action.  My goal is to add a demo for each new feature I add to the library so it can be verified.

While I have focused on 2D operations currently, there is a skeleton for 3D in the library, and I plan to hoover up all of my nice 3D code from various projects and throw them together into this library.

I have messed around a lot with ray casting and height field voxels, but never true 3D voxels.

This weekend I decided to investigate octrees for true voxel rendering. To keep things simple I have done all of my rendering on the CPU by ray tracing through the octree for each pixel on the screen.  Here is a nice thread of ray box intersection techniques.  Since there is no depth buffer, to draw correctly my octree is traversed front to back order, exiting on the first voxel encountered per ray. My approach for this was to derive a look up table defining all traversal orders for all configurations of ray direction. After a few hours of derpy moments and beard scratching this started to ‘just’ work really well.

Another neat feature I played with was eliminating all pointers relating to the hierarchy of the octree.  This is similar to the linear octree except I also store interior nodes not just leaves. Nodes can be stored linearly in an array and their relationship can be inferred from their location (root being -1):

    inline int getParent( int node )
    {
        return (node / 8) - 1;
    }

    inline int getChild( int node, int child )
    {
        return (node+1)*8 + child;
    }

While this is neat and its nice to be able to wipe out all pointers from the quad tree nodes I do believe this is likely not the most efficient approach. I have observed that a nodes near each other in the list have wildly different x,y,z locations in space. It seems hard to take an x,y,z coordinate and directly calculate the index into the list for that node. This is a property I think should be very important in a good quad tree for voxel use. I will spend more time trying to find a nice solution to this by applying various space filling curves.

In my implementation a node is currently defined as follows:

    struct sNode
    {
        sChunk *buffer;
        u32     data;
    };

the field ‘data’ simply stores the colour of each voxel for now. I have a plan to use ‘buffer’ to store and cache a vertex buffer representing all of the voxels contained by this node.

The octree in the video above is 8×8 which is the falloff point performance wise at 320×240 resolution single threaded. I don’t care so much about the performance CPU side because now that I know the octree works I can move it all to the GPU. I plan to integrate this into my LiteGame engine for 2D / 3D voxel hybrid games.

The source code is not very nice, but can be found here:

https://bitbucket.org/AidanDodds/demo_code

Doom3 stored all of its levels in “*.proc” files, which are plain text not binary.  I have written a small parser to load these files and glob all of it into one large mesh.  In the above picture you can see the mesh data, and the level covered in my procedural demo texture which is useful for debugging UVs.

The PROC files also contain BSP information for quickly mapping an item to a specific sector of the map.  The next step would be to parse this, and implement a small portal system to quickly cull sectors that cannot be seen.  Loading the real textures would be nice too.

Source Code: https://bitbucket.org/AidanDodds/demo_code

Having done my fair share of graphics work on the CPU I think it is high time that I get to know this thing called the GPU.  I have read a lot about GPU rendering over the years but I haven’t actually done what counts, and that is to code something.  I want to correct this, so I have started to create a modern OpenGL demo.

True to my goal, I don’t want to use any wrappers or any libraries which would hide the details of actual graphics programming from me.  So far most of the work has centered around a hand crafted OBJ model loader, and dealing with a few of its strange problems.

The model I use for my demo was created by Dmitry Parkin, an awesome digital artist who has worked on many AAA games.  The nice thing is its free, low poly, and normal mapped.  Its always nice to work with good looking assets instead of my bad programmer art.

So far I can load an OBJ files vertex positions and texture coordinates.  I generate the normals instead of extracting them from the file mostly as a hang up from and earlier stage of my OBJ parser.  All of the geometry is stored in vertex buffer objects, which resides on the GPU instead of in host memory. The lighting is very crude at the moment, really being a bunch of hack in the shaders.  This will be one of the next things to be tackled once I get my head around how to generate a bi-normal and tangent in order to make use of the normal map.  Oh, and free flying cameras are soon to be implemented too, that’s a must.

Stay tuned…

I also started a GIT repo to make the source easier to share:

https://bitbucket.org/AidanDodds/demo_code

Make sure you have SDL and visual studio 2010 (Probably easy to port to Linux however).

I have undertaken another weekend project, this time I wanted to investigate how well a genetic algorithm could find and approximate a variety of 1d functions.  Approximate functions can be very useful to speed up processing time in many areas where accuracy is not crucial.

In total I have spend around 5 hours on this having programmed everything from scratch.  I had worked with genetic algorithms before so I had a good idea how to approach them, and avoid some common pitfalls.

For this task each gene can contain the follow operators [ +, -, *, /, abs() ].  There are 15 operand nodes, and 16 input leaves, forming a binary tree which propagates the overall evaluation towards the root of the tree.

One of major change over my previous designs was to try an maintain diversity in the gene pool as a high priority.  My early tests showed that each gene in the pool would approach the current best gene with minimal to no change.  I took two approaches to combat this.  The easiest was to periodically call a function to kill inbred genes;  if any genes were too similar then the one with the lowest performance would be entirely randomized.  My second strategy was to allow a newly created and mutated gene to replace one of its parents only when it scores better then them, otherwise it will be dumped entirely.  My old approach was to kept any new gene in the pool if it performed better then the worst in the pool, which leads to the best performing genes dominating the pool with no incentive for variance.

I have observed that a species can easily get stuck in a local maxima and take quite a long time to escape it, which is something that can use improvement in the future.

The overall performance of this project is quite pleasing, and it is already churning out some very unusual approximation functions, for instance:

float aprox_tanh( float x )
{
//  return 6.01180618117f / ( 1.201234f * x + 7.38167675703f / x );
    return 5.00469199271f / ( x + 6.14507810887f / x );
}

Continue reading →

Spherical Harmonics are cool.  They are commonly being used for real time GI approximation in many AAA games.  These things are tiny light probes, encoding all incoming light for a single point in 3d space.  One of the main attractions is that they allow you to integrate of all incoming light for a point in space as a mere dot product of coefficients.

I contracted an intense curiosity with this subject, so spent the weekend coding up their little 2D brother, Circular Harmonics.  This is the same stuff that Alex Evans (ex LionHead) used for the lighting in Ragdoll Kung Fu.  While these things only seem to get used for graphics, I think these things have a hidden potential to do awesome stuff for Sound and AI as well.

The image above shows Circular Harmonics being used (shown in white) to approximate a signal (shown in green) of varying magnitude.  Here only 8 coefficients were used, that’s just 8 floats.  Something to try would be to compress each coefficient to just a signed bytes and see how well it would keep its approximation.

Here are some good references on the subject:

http://www.blackpawn.com

http://www.paulsprojects.net

D3DTutorial07_AlexEvans_Final.pdf

There were a number of issues with my real-time raytracer that have presented themselves.  Some things only showed up when testing in debug build, such as multiple threads all contending for use of a single static variable.  I also made the mistake of creating variables on the stack which I then passed to each thread.

A friend from work also ported the code over to linux, and suggested some ways to improve the performance using SSE optimisations provided via GCC, which is awesome.

I have decied to post a revised version of the code with all of these corrections and fixes.  Also thrown into the mix is freznel attenuation for the mirrored surface, as well as light falloff, making things look prettier still.

rt_raytrace.cpp

Updated with arbitrary triangle rendering using vertex and index buffering.  Normals are currently calculated on the fly which is fairly bad.  Will fix that…