pouët.net

Want to learn more about how voxel engines work. Not those kind of raymarched voxels that gpu cards can pull off, but more like the ones one can write from scratch like blitting pixels to the frame or videobuffer. Ive made voxel tunnels, voxel-landscapes and voxel-blobs in the past, so i know roughly how those work, but they have limited degrees of freedom due to the precalculated tables they use. Im researching on 6dof to find ways to make one with as little code as possible and find ways to use tables to make them fast.
There's some really cool voxel stuff like in Ken Silverman's demogames, but i dont want to try and interpret the code, i really only wanna know the constituents behind how a 6dof works so i can write my own.

There's an article on page 366 in Graphics Gems 4 called "Voxel traversal along a 3D Line - Daniel Cohen" and "A Fast Voxel Traversal Algorithm for Ray Tracing - John Amanatides" which were used in some raycasted voxels in Shadertoy by some guy, i translated into softrender, and optimized a bit but it still runs too slow for my taste even in 320x200 mode. it looks decent tho:
Actually im looking more into ways of reducing the voxels into just squares like this one http://bruce-lab.blogspot.no/2012/06/destructor-voxel-based-fps-game-power.html. It does not look like they render edges, that is cubes, but more like nearest neighbor interpolation. because I think that would run faster. In the image above i run each pixel through a casting ray using a ray-depth of 32.

There's also some papers ive found, that I will look more closely at though not sure if the technique(s) i am out after is explained there, also they sometimes use different terminology in the papers so.

* A Faster Algorithm for 3D Discrete Lines - V. Boyer, J.j Bourdin - seems like using a DDA method.
* 3D Scan-Conversion Algorithms for Voxel-Based Graphics - Arie Kaufman

Ive been thinking about if there are ways to precalculate a sphere-map from a texture, such that 6dof is achieved that way but that requires a bit of math i havent figured out yet. if the 2d texture floats in 3d space and camera is directed towards it, but one needs to cast rays for each pixel anyway, i dunno if this is the way to precalculate the sphere-map? The same technique is almost used for voxelblobs. but its a different projection scheme there. it just does not work the same way. Anyway, ive been rambling for a bit now, will come back later to see if anyone responds, and if anyone have any ideas for 6dof and easy or intermediate explanation please let me know. 6dof was done in Retroficial but I didnt find the email to pailes to ask of an explanation.

Have you tried voxlap source code ?

Unfortunately the forum when Ken described his full algorithm is down, but let me describe it for you now quickly ;)

It's easy to understand the algorithm when you do not allow tilt (5DOF) and roll (4DOF). AFAIK the first successful commercial game doing it in 5DOF (probably with very the same technique) was Comanche Maximum Overkill (1992) and on demoscene Mars demo (1993).

So, in 4DOF case you do ray-casting for every vertical line on screen (for 640x480 you shoot 640 rays) through 2d grid not 3d (ignoring height). Every grid cell you visit represents a voxel column. Then you can simply draw all solid voxels in a column as a vertical segment. In Comanche-style renderer it was just one segment per column, but you can have as many solid voxel segments as you want.

Now there are two things you have to do to make it fast:
1. Your voxel representation should be a 2d grid of columns with solid voxel segments (sort of like RLE encoding). This is quite space-efficient and you can easily look it up.
2. For every vertical line on screen you can maintain a span-buffer (Quake1-style, except you only need to maintain it for 1 line at a time). So solid voxel segments will be your spans that you will draw and slowly "fill-up" your span-buffer. Once span-buffer for your vertical line is full, you can stop your ray-casting.

In 5DOF, it's basically the same thing - you still do ray-casting through the same 2d grid, however a voxel column will no longer be vertical line on screen. You have to rotate it by roll angle. Note that all lines/columns will be still parallel.

In 6DOF, a previously vertical line on screen now can go in any direction (not parallel anymore). One ray = one line (or half-line) on screen. Lines on screen representing rays intersect at zenith/nadir points. The tricky part here is to understand that to fill-up the whole screen and don't miss any pixel you have to visit (not necessarily redraw it) the same pixel more than once. In total you have to cast (screen width + screen height)*2 rays, when looking straight down.

tomkh: 1 and 2 are basically the same thing I did in my voxel landscape some years back, or close to it. Dunno if i used a s-buffer because I did it directly: rendered spans from front-to-back while ignoring bytes (heights) if current_read_byte < maximum_read_byte from the raycast routine. So voxel landscapes are pretty easy to do imho. And yes Commanche-game ruled back in the day.

6DOF are tricky ones to understand. i dont understand the math yet, but thanks for trying to explain. i imagine a camera looking down at the landscape-texture shooting rays like in the previous one, but with width*height rays, but how is that texture-lookup done?
i forgot camera linear-algebra math so id have to read myself up on that again. and see if the same logic as viewing frustum of camera to 3d rasterizer can be done with voxels instead.

i see that your (width+height)*2 rays is faster than what i imagine with (width*height) rays. I just dont understand yet how such lookup is done.

Well, so I forgot there is this thing called wayback machine:))
Here is the link for original thread with Ken's explanation.

There is really not much difference in principle, except those 'upgrades' to support multiple solid voxel columns instead of just one height sample and rasterization order / projection (for 6DOF). Moreover, when you look at the horizon, you even cast the same amount of rays.

just stumbled into this https://sites.google.com/site/letsmakeavoxelengine/home and this https://github.com/AlwaysGeeky/Vox

not sure how helpful they are though

I just had an idea last night, which I would want to try out some day. I think one could try and project using polar-coordinates based on the camera rays. Its similar to pinhole camera like used in raytracing.. And then convert back to cartesian.

tomkh: will check that out

rudi: and about your width*height vs (width+height)*2 remark. Since here you cast rays in 2d, one ray is really a counterpart of packet of rays if you compare to brute-force 3d tracing. In fact, you can think of it as grouping all rays that goes in the same XZ direction (assuming Y is height) into one "packet" which actually goes through pixels that forms straight line on screen. In 4DOF this line is vertical.

to my understanding 6dof is nothing else than what OP already did: raycasting in 3d.

I wonder what machine do you use, that its slow? essentially what is done is 3 times the calculation for each pixel, that Wolfenstein does for a column. Should be piece of cake for todays gpu. Definitly somce compromises need to be done here for more speed. Removing 1-2dof or smth. Precalculating Ray setup. After a ray is inited the rest of the calculation is absolutely minimal.

Oswald: I use cpu. also many calculations are done in floating point divs and muls.



so its 1 div and 6 muls per pixel. also per column there are some muls and divs including rotation. if i was a bit vague in the first post, i meant i did not want to use the gpu.

i tried to convert the above formula to fixedpoint but the whole rendering got messed up.

Most likely you can omit the divs and muls. I have no clue about your per pixel setup code, but for me it looks like you could use a linear interpolation from one edge to the other. Thus currentpixel raydirstuff equals lastpixel raydir stuff plus a fixed delta for the entire line. If i talk bogus sorry but your formula above looks like it's just linear. Take both edge values and divide by tge pixrlcount between to obtain the adding values per pixel.

If that was your per pixel setupcode, like you described it.

You must have seen that, so I have just one more question: Why do you have 6 muls and not 4? Is reducing not possible there? Because of rounding or somehting?

@rudi:

this will teach you how to do it with fixpoint math very fast:

http://permadi.com/1996/05/ray-casting-tutorial-table-of-contents/

just extrapolate the method to 3d. this is how 8 bit machines and amiga does wolf clones.

mad: without the rounding, it fucks up the nearest neighbour interpolation. thats true.
Oswald: yes, nice tut.
will maybe rewrite the entire routine with fixedpoint some day. just need a break from actual coding.

the problem is to find out how many bits per significand and exponent until the visuals starts to jerk. maybe one can fit that into a short datatype, hence taking two pixels per integer. there's alot to consider still.

If I understand correctly you are casting rays and using DDA to check intersections along the voxels (like in a raycaster)
In case you stay with that approach, what you could try to do to accelerate the rendering is to build some octree around the voxels. It might help because during the intersections checks you can use the octree to skip big parts if they contains no voxel at all.



It will probably not help for the small scene you give in your screenshot, but it will definitely accelerate things for big ones.

Tigrou: i understand what you mean if thats an adaptive subsampling technique.

He's talking about speeding it up significantly by using octrees to skip through empty areas

that kind of optimization is only worth in case of raytracers AFAIK. casting rays is cheaper than all the fucking with the octrees. unless the box size is extremely small.

Minecraft has many voxel related extensions.

From using an Xbox cameras depth buffer to generate voxel objects in Minecraft to glsl shaders for all the glsl effects on minecraft chunks that are voxel fields of pointers to materials.

Based on voxel geometry the most recent mod compilation "life in the woods" nicely popularizes voxel engines in JavaScript. It's a great start that can be learned by 10 year olds and is used in some schools to teach programming. If only with ingame redstone-wiring elements.

You definitely get better performance by utilizing "sparse voxel octree" structure. But its significantly better for static scenery than for dynamic scenery.

Definitely a subject to look into if you deal with many voxels.


The "euclideon' engine got infamous over this approach untill I found a practical application in highres distance photography for city planning and archaeology.