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