Dark Bit Factory & Gravity
GENERAL => Projects => Topic started by: rain_storm on June 21, 2011
-
I'm releasing the source code for my voxel engine. It currently uses quadtree subsampling to reduce the number of rays being cast, and the fast voxel traversal algorithm (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.42.3443&rep=rep1&type=pdf) to accelerate those rays which are cast. I'm planning to take on the sparse voxel octree traversal (http://www.daimi.au.dk/~aquak/MasterThesisKristofRoemisch.pdf) approach if I can manage to pull it off. I'm fairly happy with this as it stands, there are a few things not yet implemented correctly, such as texture mapping in such a way so as to take advantage of the quadtree subsampling, and a proper link list that would allow shapes other than spheres. Still I would like to share the source with others who have some interest in voxels. Voxels are the future make no doubt about it. Polygons have had their day.
Edit - Texture mapping now works better, managed to increase the resolution with no loss in speed. Maximum number of shapes increased to 256. Limited support for discs, capsules and cylinders.
-
This looks interesting! Doesn't work properly for me though. :-\ See attached screenshot.
-
It works well here - the source is very nicely set out too.
K+ Thanks for sharing.
-
That looks fantastic. K++, mate :clap:
-
Awesome work!
Someday I need to start learning this kind of thing. :goodpost:
-
I know my PC is shite, no need to rub it in you lot! :P
-
Doesn't work on mine :(
2GHZ
3GB RAM
GEFORCE 9600M GT 512MB
WINDOW 7
-
This looks interesting! Doesn't work properly for me though. :-\ See attached screenshot.
Same for me on Win7 x64 with a GeForce GTS 250
Looks cool though, even if it is a bit screwed up here.
-
I get the same results only when I set the screen resolution to 800x600. Perhaps this is an issue with StretchDIBits at certain resolutions? For some weird reason clearing the pixel buffer seems to help, why is beyond me as the engine writes a colour to every single pixel each frame. Anyways I have an OpenGL workaround using glDrawPixel that might fix the issue...
WARNING : DO NOT RUN FROM INSIDE THE ZIP, EXTRACT IT FIRST!
the program searches for a file named world.bin in the current directory, if it is not found the program generates a world and writes it to disk. This causes a hang if its being run from within the zip file.
Edit - Attachment removed it didn't fix the issue. First post updated with the proper fix
-
Sorry mate no luck with the OpenGL version here, just a black screen. The normal version looks slightly better though. My resolution is 1440x900. Maybe this is a Nvidia issue since I also got a GeForce?
-
Excellent.......
One things thought....the open gl wouldnt run on mine but when I click on NO for Opengl then it run Great!
-
Awesome stuff, love voxels, started a thread about them on gamedev.net a few years back, to ask why I never see them used, even though I knew some impressive voxel demos. I believe the conclusion was that it takes too much memory...?
When I think about voxels I think about Commanche (helicopter DOS game), with exceptionally cool voxel terrains. I don't see why this game isn't bested yet (to my knowledge), all hardware components have improved over the years and commanche looks good to me even today (screeny (http://www.mobygames.com/game/dos/comanche-maximum-overkill/screenshots/gameShotId,242955/)). Also Ken Silvermans voxlap (http://advsys.net/ken/voxlap/voxlap03.htm) ran silky smooth on my hardware at least 3 years back.
Cool post rain_storm, new exe worked for me, awesome work!
What do you say is holding voxels back?
-
Nice one, shame not working to well on mine XP Pro, Nvidia :telloff: (Nvidia have a lot to answer for in my book)
Thanks for sharing ;D
-
@Kirl
What's been holding voxels back? In my opinion it was a combination of memory footprint, processing power and lack of support from Graphic card vendors.
Nowadays theres more than enough processing power, the above engine is completely software rendered but there are raycasters implemented entirely on the GPU with an order of magnitude in increased power.
Memory footprint is no longer an issue. The sparse octree traversal algorithm is like the google search engine of voxel traversal. Only a tiny subset of the world needs to be physically defined. Any vast empty regions become compressed into a single integer. On the other hand any vast regions entirely made up of a single colour are also compressed into a single integer. This leaves a lot of room for fine detail where its needed. Traversal is also an order of magnitude faster than the meathod I used here. So you have massive terrains with a level of detail not possible with polygons, using an algorithm that runs at real time on todays hardware.
There's nothing holding it back anymore.
@Peeps who are having render issues
The problem is that the initial quadtree subdivision is performed according to the aspect ratio, which forces each block to be a perfect square...
// quadtree subdivision...
int S = Canvas.Width / max(Screen.AspectX, 1);
for (int y = 0; y < Screen.AspectY; y++)
for (int x = 0; x < Screen.AspectX; x++) QuadTree(x*S, y*S, S);
While further quadtree subdivisions are always into 4x4 squares. Which gives a loss in precision if the initial squares are not powers of two...
s = s/2;
QuadTree(x, y, s);
QuadTree(x+s, y, s);
QuadTree(x, y+s, s);
QuadTree(x+s, y+s, s);
I think the solution is something like this...
temp = s/2;
if (temp*2 == s) {
s = s/2;
QuadTree(x, y, s);
QuadTree(x+s, y, s);
QuadTree(x, y+s, s);
QuadTree(x+s, y+s, s);
} else {
// sub divide properly...
}
but its not that easy. The method I use for subdividing requires getting the greatest common divisor of the width and the height. But these are perfect squares. The greatest common divisor is the same as the size. Besides this is an important recursive function I would rather perform the extra overhead outside of this. And ensure that the initial squares are always powers of two. Anybody know how to do that?
-
There's nothing holding it back anymore.
So where are the big studio games, like the endless fps's that all boast destructable terrain? I can see a lot of strategic potential in a dynamic environment that retains it's volume. So wherever you dig/carve/blast/whatever, the rubble remains. I know little to nothing about the technical difficulties, but it seems as easy as emptying one cluster of voxels and filling another.
Actually, I just want to see a 3d digdug game! :)
-
This is some duct tape programming but hey it works, and I can't think of an elegant solution that doesn't require rewriting half the code. See first post for the fix
The voxel games will come, just as soon as the majority of the market all have genaral purpose graphic processors. At the moment you really need that level of processing power to outshine the ploygon based engines. Although Minecraft (http://www.youtube.com/watch?v=FaMTedT6P0I) is a great example of what the current mid range PC is capable of.
-
Cool, works like a charm now! I'll have a deeper look. Thanks for the fix! :clap:
-
Cool, works like a charm now! I'll have a deeper look. Thanks for the fix! :clap:
Works for me too now. Looks really good too.
-
Updated - Quadtree subsampling now works with texture mapping, Added extra shapes, now it supports discs, spheres, capsules and cylinders, and increased the maximum number of shapes to 256.
These extra shapes are only partially implemented. Collision detection is still performed as though all shapes were spheres. So there may be some overlap between shapes. Also the objects are not yet added to the link list based on their volume this can cause artifacts where parts of a shape are not displayed correctly.
-
Very cool stuff, love flying around the cave like environments and losing all track of up/down. How about some destructible voxels?
-
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!
-
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.
-
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 (http://wscg.zcu.cz/wscg2000/Papers_2000/X31.pdf) 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
#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;
}
// 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
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 };
-
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.
-
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.
-
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.
-
sounds good :) i'm learning this stuff too with not much success :D but someday.. :D
-
Works fine here! Thanx for the sources :P Will try to take a look at it... if I have some times... :-[