Voxel Engine

[Shockwave]

Agreed!  You could make a really excellent updated version of Descent with this engine.

It's cool to see the textures and different objects you have going on now.
Cool stuff!

[JL235]

I was running it at 1920x1080 and it was managing approximately 10 to 15 fps. Considering it's all software rendered, I'm pressed it's at a usable speed.

I am on a 2.4ghz quad core, but only just under 2 cores (around 40% CPU usage). But this is the type of algorithm is (typically) trivial to parallelize, so if you took advantage of all cores then the frame rate should just double. Then it would be perfectly usable in a real game/demo at fullscreen.

Overall I was very impressed; I'd love to build something like this.

[rain_storm]

Thats fairly impressive JL235 but the engine quaters the resolution internally so you're getting 10-15 fps at 960x540. The most important optimization is the quadtree subsampling, it scales logarithmically with resolution. If you double the resolution the framerate doesn't drop by half. I've switched from quadtree to bintree subsampling. It's still a little glitchy but I've managed to double the framerate without having to spawn more threads.

I've managed to implement octree's using the Parametric Octree Traversal Algorithm but the recursion is crippling the framerate. I could try to convert this from recursive to iterative and manage a stack by myself but to be honest the initial results are so underwhelming that I don't think it's worth it. So I'm gonna investigate mipmapping the voxel geometry and see where that takes me.

my octree traversal looks like this

Code: [Select]

#include "raytrace.h"
#include "octree.h"

unsigned char a;

int RayOctree(octree tree, photon ray)
{
    // force positive traversal direction...
    a = 0;
    if (ray.dirx < 0.0f) {
        ray.posx = tree.sumx - ray.posx;
        ray.dirx = -ray.dirx;
        a |= 4;
    }
    if (ray.diry < 0.0f) {
        ray.posy = tree.sumy - ray.posy;
        ray.diry = -ray.diry;
        a |= 2;
    }
    if (ray.dirz < 0.0f) {
        ray.posz = tree.sumz - ray.posz;
        ray.dirz = -ray.dirz;
        a |= 1;
    }

    // calculate slab intersections...
    float tminx = (tree.minx - ray.posx) / ray.dirx;
    float tmaxx = (tree.maxx - ray.posx) / ray.dirx;
    float tminy = (tree.miny - ray.posy) / ray.diry;
    float tmaxy = (tree.maxy - ray.posy) / ray.diry;
    float tminz = (tree.minz - ray.posz) / ray.dirz;
    float tmaxz = (tree.maxz - ray.posz) / ray.dirz;
   
    // continue only if ray intersects bounding cube...
    if (Max(tminx,tminy,tminz) > Min(tmaxx,tmaxy,tmaxz)) {
        return 0;
    }
    return RayNode(tminx,tminy,tminz, tmaxx,tmaxy,tmaxz, tree.root);
}

int RayNode(float tminx, float tminy, float tminz, float tmaxx, float tmaxy, float tmaxz, node *n)
{
    // the octree traversal is dependant on positive direction rays...
    if (n == 0 || tmaxx < 0.0f || tmaxy < 0.0f || tmaxz < 0.0f) {
        return 0;
    }

    // if we reach an atom we are done...
    if (n->type == NODE_ATOM) {
        return RayVoxel(n);
    }

    // otherwise subdivide this node into 8 children...
    float tmidx = 0.5f*(tminx + tmaxx);
    float tmidy = 0.5f*(tminy + tmaxy);
    float tmidz = 0.5f*(tminz + tmaxz);

    // find the first node entered...
    int curNode = FirstNode(tminx, tminy, tminz, tmidx, tmidy, tmidz);

    // travarse the rest of the child nodes using the current node and exit planexyz...
    int rgba = 0;
    do {
        switch (curNode) {
        case 0:
            rgba = RayNode(tminx, tminy, tminz, tmidx, tmidy, tmidz, n->child[a^0]);
            curNode = NextNode(tmidx, 4, tmidy, 2, tmidz, 1);
            break;
        case 1:
            rgba = RayNode(tminx, tminy, tmidz, tmidx, tmidy, tmaxz, n->child[a^1]);
            curNode = NextNode(tmidx, 5, tmidy, 3, tmaxz, 8);
            break;
        case 2:
            rgba = RayNode(tminx, tmidy, tminz, tmidx, tmaxy, tmidz, n->child[a^2]);
            curNode = NextNode(tmidx, 6, tmaxy, 8, tmidz, 3);
            break;
        case 3:
            rgba = RayNode(tminx, tmidy, tmidz, tmidx, tmaxy, tmaxz, n->child[a^3]);
            curNode = NextNode(tmidx, 7, tmaxy, 8, tmaxz, 8);
            break;
        case 4:
            rgba = RayNode(tmidx, tminy, tminz, tmaxx, tmidy, tmidz, n->child[a^4]);
            curNode = NextNode(tmaxx, 8, tmidy, 6, tmidz, 5);
            break;
        case 5:
            rgba = RayNode(tmidx, tminy, tmidz, tmaxx, tmidy, tmaxz, n->child[a^5]);
            curNode = NextNode(tmaxx, 8, tmidy, 7, tmaxz, 8);
            break;
        case 6:
            rgba = RayNode(tmidx, tmidy, tminz, tmaxx, tmaxy, tmidz, n->child[a^6]);
            curNode = NextNode(tmaxx, 8, tmaxy, 8, tmidz, 7);
            break;
        case 7:
            rgba = RayNode(tmidx, tmidy, tmidz, tmaxx, tmaxy, tmaxz, n->child[a^7]);
            curNode = 8;
            break;
        }
        if (rgba) return rgba;
    } while (curNode < 8);
    return 0;
}

int RayVoxel(node *n)
{
    // here I just return a colour, but this could just as easy be a list of objects to test.
    return n->rgba;
}

int FirstNode(float tminx, float tminy, float tminz, float tmidx, float tmidy, float tmidz)
{
    int index = 0;
    if (tminx > tminy && tminx > tminz) {
        if (tmidy < tminx) index |= 2;
        if (tmidz < tminx) index |= 1;
    } else if (tminy > tminz) {
        if (tmidx < tminy) index |= 4;
        if (tmidz < tminy) index |= 1;
    } else {
        if (tmidx < tminz) index |= 4;
        if (tmidy < tminz) index |= 2;
    }
    return index;
}


Code: [Select]

// contents of raytrace.h
typedef struct photon {
float posx;
float posy;
float posz;
float dirx;
float diry;
float dirz;
} photon;

// contents of octree.h
typedef struct node {
node *child[8];
int  type;
int  rgba;
} node;

typedef struct octree {
float  minx, maxx, sumx; // where: (minx < maxx) && (sumx = minx + maxx)
float  miny, maxy, sumy; // where: (miny < maxy) && (sumy = miny + maxy)
float  minz, maxz, sumz; // where: (minz < maxz) && (sumz = minz + maxz)
node   *root;
} octree;

const int OCTREE_NULL   = 0;
const int OCTREE_ROOT   = 1;
const int OCTREE_BRANCH = 2;
const int OCTREE_LEAF   = 3;

and the octree data looks like this

Code: [Select]

node n[8] = {
{ 0,0,0,0,0,0,0,0,NODE_ATOM,0x003333FF },
{ 0,0,0,0,0,0,0,0,NODE_ATOM,0x00FFFF33 },
{ 0,0,0,0,0,0,0,0,NODE_ATOM,0x00FF33FF },
{ 0,0,0,0,0,0,0,0,NODE_ATOM,0x00FF3333 },
{ 0,0,0,0,0,0,0,0,NODE_ATOM,0x0033FFFF },
{ 0,0,0,0,0,0,0,0,NODE_ATOM,0x0033FF33 },
{ 0,0,0,0,0,0,0,0,NODE_ATOM,0x00FFFFFF },
{ 0,0,0,0,0,0,0,0,NODE_ATOM,0x00333333 }
};
node root = { &n[0],0,0,&n[3],0,&n[5],0,0,NODE_ROOT,0x00FF7733 };
octree tree = { -1.0f,1.0f,0.0f, -1.0f,1.0f,0.0f, -1.0f,1.0f,0.0f, &root };


[JL235]

It would be good if you could take advantage of the graphics card, perhaps using OpenCL so it falls back onto the CPU, as then you could probably have it running at 60fps on modest hardware.

[rain_storm]

The current direction I'm moving in is to increase the level of detail. I now have octrees and the fast 3D DDA working together. with mip mapped geometry. It's a lot slower though. But first you gotta make it work then you can make it fast.

[Shockwave]

The frame interpolation gives a strange effect where the scene looks like it's moving back and forth here - Having said that though it's running at about 15fps for me so when it's been optimised for more speed it might make all the difference.

[tomafeha]

sounds good i'm learning this stuff too with not much success but someday..

[jace_stknights]

Works fine here! Thanx for the sources Will try to take a look at it... if I have some times...