Weekend Project – Voxel Octree

 

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

Advertisements

4 thoughts on “Weekend Project – Voxel Octree

  1. Very nice Demo! Question: With your algo, would you see any significant efficiency gained from locking the camera at a 45′ angle in respect to the voxel volume (basically a static isometric view, voxels can rotate around one axis – z)? I ask because I am trying to make an isometric voxel engine that bridges the gap between 2.5d and full 3d and was wondering if you thought there would be any reason (speed wise) to pursue this.

    • Hi, thanks for your great question. I do belive you could gain a fairly large speedup when locking the camera. The ray-box intersection test could be made faster when you know some faces of the voxels would never he hit. Also the front to back traversal of the octree could be hard coded for the fixed camera angle. That way you would avoid a few array lookups and some branching. So, yes I do think there would be benefits from fixing the camera.

      • That was my hunch, I appreciate your insight – Thank you! I haven’t decided yet if I will go the route of using an octree, I can see where the space-skipping would be a bonus, but am feeling that re-generating the octree when the data/terrain is modified is a bottleneck… though, this obviously doesn’t occur as often – also an octree doesn’t maintain the inherent ‘neighboring’ voxel information – to get from one voxel to its neighbor, one must traverse back up the tree then back down to the correct child. My thoughts are that a run-length compression along the z-axis (height) will satisfy (1) decent data compression, (2) quick data modification, (3) quick ability to retrieve neighboring voxel information. Looking forward to seeing your LiteGame engine!

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s