Real-time voxel raytracing, in development..

[IJs]

I'm currently working on a real-time raytracing project (http://ijs.mtasa.com) which utilizes voxels aligned in a uniform fixed-grid, and is fully implemented on the GPU instead of conventional CPU raytracers.

Inspired by Ken's Voxlap engine which we know utilizes some runtime length encoding based raycasting algorithm, I reckoned it would be cool to get a raytracer running capable of tracing a given voxel data set. I know there's been a lot of research (e.g. medical research) into this subject, and I've seen several approaches on rendering voxel data sets with reasonable speeds but I figured out they were mostly raycasted, which is not what I was looking after.

Latest relevant snapshots
(01-2009) Instant radiosity & ISMs at work


Early proof-of-concept

(07-2008) Beware of bugs! First-hit ray-tracing only (phong shading).

Application: http://ijs.mtasa.com/files/voxeltracer_demo.exe
Dependency libraries: http://ijs.mtasa.com/files/voxeltracer_demo_dlls.exe

You will need a CUDA-compatible graphics card to run this.



One of the keys things here is that the programming, being executed on your GPU, is entirely different than that of a CPU-equivalent but it's pretty interesting and looks like a nice challenge anyways. The framerates are different every day, cause there's hardly any performance debugging available - so it's a matter of slightly brute-forcing stuff and figuring out what runs best. Everything is chopped up in logic blocks (or passes), so secondary (and more) ray tracing should be possible by just slapping another trace pass behind the first one. I'm fairly confident I can use the same technique for photon mapping (voxels seem to lend themselves nicely for the storage structure).. hopefully I'll be able to post some progress on that any time soon.

Currently it's running on my first generation NVidia GeForce 8800GTS (not one of the fastest.. G80, theoretical GFLOPS at ~345, 320-bit memory bus).

The cool thing with voxels in the current implementation is that as you increase your scene complexity in terms of numbers of voxels in your grid, the performance of the tracer remains mostly constant - whereas with polygons (with the tracing done on your GPU) you would tend to get into trouble due to the required random memory lookups in combination with the fairly limited memory bus. I use an acceleration structure that is easy to update through the CPU, so animation is possible.

In short, the voxel grid is traversed using a heavily modified Bresenham algorithm (if you're familiar with the subject you probably know Bresenham used to be the fastest line drawing algorithm around, albeit with some graphical error) utilizing some GPU-optimized memory scheme. Everything is coded in C/C++ using NVIDIA CUDA 2.1.

[Awesoken]

Your video looks very impressive. Please do not hesitate to release a working demo at some point. I must warn you: apegomp (who recently registered under the name, "asdgdhfsg") will soon be your new best friend! : )

[asdgdhfsg]

Feel free to use the Voxelstein 3D dataset (http://rapidshare.com/files/86075076/Voxelstein_3D.rar)

[asdgdhfsg]

No real-time voxel rayTRACERS that I know of though.

REARViEw is a real-time CPU voxel rayTRACER, but it runs in software, and I don't think it takes advantage of parallel processing and I think the project is dead..
http://rearview.sourceforge.net/index.shtml

There is also a real-time Flash ActionScript 3.0 (voxel?) Raytracer demo here:
http://www.strille.net/works/as3/raytracer/

A raytraced voxel game that uses a resolution of 320x240 would run super-smooth on today's computers, especially when powered by the GPU!

[IJs]

I must say that the video is pretty outdated (time to release a new one).. more specifically, before I realized it's probably better for the overall quality to keep the size of 1 voxel equal to 1 pixel on my screen.. the performance to pull it off is there as you can see. That's also the reason why I probably can't use the Voxelstein 3D (although very impressive) dataset at it's current resolution.

And as far as those other raytracers are concerned: I'm not seeing the potential. They come nowhere near the performance and quality that can be achieved by using a good parallel-based algorithm. The AS3 raytracer, although impressive, is probably just based on sphere/plane intersections.

I should be able to release a demo whenever I reach the standards I have in mind, which shouldn't be too long from now. You're gonna need a pretty fast graphics card though : P

[asdgdhfsg]

it's probably better for the overall quality to keep the size of 1 voxel equal to 1 pixel on my screen.. the performance to pull it off is there as you can see. That's also the reason why I probably can't use the Voxelstein 3D (although very impressive) dataset at it's current resolution.

I could try making a high-res dataset.

You're gonna need a pretty fast graphics card though : P

My brother owns a gaming computer! D:

I should be able to release a demo whenever I reach the standards I have in mind, which shouldn't be too long from now.

Be sure to include transparent water/glass voxels in your upcoming demo! just kidding

[IJs]

I could try making a high-res dataset.

That'd be very interesting. Right now I'm just looking into getting some standard raytracer benchmark scenes into there (e.g. Cornell box) as to get the lighting working properly, but it won't be that interesting cause it doesn't show how cool and detailed voxels can be.

I don't think Ken's voxel editing tools support these massive datasets though, that why I'm going to make a suitable polygonal mesh->voxel dataset converter some time soon for very high polycount meshes. But if you're used to voxel editing.. I really don't know any voxel modeling tools out there that seem to do the job.

As far as that 1 pixel per voxel resolution is concerned.. where 1024x1024x256 would be the size of a medium level in Voxlap, 1024x1024x256 would (very) roughly be the size of two human models with this approach in the worst case (given that you're watching them from the same distance in the above screenshot - which would be pretty close anyways). Just to give you an idea of the slightly bigger scale.

Be sure to include transparent water/glass voxels in your upcoming demo! just kidding

That's really not that stupid. Photon mapping seems to fit right into there, so with any luck the first demo should contain a preliminary version of photon mapping (if it doesn't take too long), and eventually you could have caustics and all that : ) - gotta get the basics working first though.

[asdgdhfsg]

Here is a short list of the most important voxel types you should try to put in your engine:

Air voxel: 100% transparent, does not block the player (is not an obstacle)
Solid voxel: 0% transparent, blocks player (obstacle)
grass voxel: ~15% transparent, green, reduces the player's speed (eg. when moving through a big bush), is burnable (when the voxel burns, it a) sends out lightning or b) gets surrounded by fire voxels and subsequently gets replaced with an ash voxel)!
Ash voxel: 0% transparent, not heavy, does not burn.
Fire voxel: ~90% transparent, follows/moves in a fluid pattern, sets nearby burnable voxels on fire (DUH! )
Water voxel: ~90% transparent, same as the fire voxel, except that it extinguishes fire and is much heavier.
Wood voxel: 0% transparent, heavier than grass, 
rubber voxel: 0% transparent, bounces and is burnable!  
metal voxel: 0% transparent, reflects light, does not burn, weighs a lot makes a "pling" sound when hit
Stone voxel: 0% transparent, same as metal voxel, except that it does not make a "pling" sound when dropped etc
blood voxel: This is the most important voxel! should be red in color, ~60% transparent, extinguishes fire, coagulates (gets replaced by a solid organic/grass voxel)!

 

Blender is fun I really want to contribute with something.. therefore I'm going to try to sculpture a high-res human model

We can't stop the evolution of violent video games, so we might as well keep pushing the envelope and continue to evolve the genre! We should make a voxel game called Childhunt! Childhunt will render Manhunt obsolete! Imagine pulling a plastic bag over an innocent little girl's head and subsequently punching her 3 times in her face and then stabbing her in multiple times in her chest with a rusty screwdriver LOL! just kidding

I will continue to learn using Blender now..

[Slang]

Hi IJs,

I would like to strongly recommend you check out Coherent Grid Traversal (pdf link). It is basically for accelerating traversals of coherent primary rays (first-hit) in real-time 'polygon' raytracing, but I believe that it can be used in voxel raytracing as well.

If you have some time to experiment with it and eventually get some results, then please let us know.

[Spacerat]

I should be able to release a demo whenever I reach the standards I have in mind, which shouldn't be too long from now. You're gonna need a pretty fast graphics card though : P

I can't wait to get it  Really impressive stuff.

Did you implement the algorithm in CUDA or by Shaders?
Maybe you can try to raycast even much bigger data-sets. I found its not a big difference between raycasting 1024x1024x1024 and 40.000x1024x40.000 using mipmapping.

However, in my case with CUDA, I found its still very slow in some cases - about 16fps. Hopefully I can increase the speed using some empty-space skipping algorithm...
Will there be a paper once the algorithm is finished ? I'm looking forward to it ^^

A recent paper which might be interesting for the shading is this one here about ambient occlusions for volume rendering and further related papers.
http://viscg.uni-muenster.de/publications/

Oh, and last here two further links to merge 2 other recent discussions about voxel with this thread:
http://www.gamedev.net/community/forums/topic.asp?whichpage=2&pagesize=25&topic_id=480208
http://ompf.org/forum/viewtopic.php?f=4&t=736

-Sven

[asdgdhfsg]

Here is my high-resolution mesh so far:



I think I will continue making low-res voxel models since I am just a hobbyist. Modeling lots of high-resolution voxel models (without the use of a big medical CT scanner of some sort) is a time consuming process that only a big game company can do practically.

A raytraced low-res Voxelstein 3D dataset would run smooth on most computers, especially when played at 320x240. It would be cool if we could play a low-res voxel game while we are waiting for the game industry to stop using those old obsolete boring triangles.

[IJs]

I would like to strongly recommend you check out Coherent Grid Traversal (pdf link). It is basically for accelerating traversals of coherent primary rays (first-hit) in real-time 'polygon' raytracing, but I believe that it can be used in voxel raytracing as well.

Thanks. I think I've read a similar paper before, but that must've been before the voxel times. I'm currently a little limited by the algorithm and it's not-so-wide flexibility but who knows.

Did you implement the algorithm in CUDA or by Shaders?
Maybe you can try to raycast even much bigger data-sets. I found its not a big difference between raycasting 1024x1024x1024 and 40.000x1024x40.000 using mipmapping.

However, in my case with CUDA, I found its still very slow in some cases - about 16fps. Hopefully I can increase the speed using some empty-space skipping algorithm...
Will there be a paper once the algorithm is finished ? I'm looking forward to it ^^

It's not implemented using CUDA due to future plans.. apart from the fact how much I like NVidia's cards, CUDA would require me to completely rewrite the whole thing if I ever wanted to run it on multiple platforms. The Rapidmind library provides an abstraction in between so I don't have to worry about that for now.

As far as mipmapping is concerned, it seems to be a matter of keeping things like the step size pretty constant. I'm using a LOD empty-space skipping algorithm right now that doubles the rendering speed, but no mipmapping is used yet. I'll investigate this pretty soon anyways.

Mind you that raycasting is, in essence, a fraction of the complexity of raytracing.

I think I will continue making low-res voxel models since I am just a hobbyist. Modeling lots of high-resolution voxel models (without the use of a big medical CT scanner of some sort) is a time consuming process that only a big game company can do practically.

That is correct, and that's why I'm working on a polygon->voxel converter that accepts really high polycount meshes. Mind you that polygons aren't that bad, as long as you have lots and lots of them, and it'll be just a matter of converting those into an acceptable voxel data set. Are you actually using blender to make voxel datasets?

[asdgdhfsg]

Are you actually using blender to make voxel datasets?

No, I use Milkshape 3D and poly2vox.

[Spacerat]

It's not implemented using CUDA due to future plans.. apart from the fact how much I like NVidia's cards, CUDA would require me to completely rewrite the whole thing if I ever wanted to run it on multiple platforms. The Rapidmind library provides an abstraction in between so I don't have to worry about that for now.

As far as mipmapping is concerned, it seems to be a matter of keeping things like the step size pretty constant. I'm using a LOD empty-space skipping algorithm right now that doubles the rendering speed, but no mipmapping is used yet. I'll investigate this pretty soon anyways.

Mind you that raycasting is, in essence, a fraction of the complexity of raytracing.

Hm.. Rapidmind is really a good idea to use - especially as Intel etc. are developing CPUs with up to 80 cores.
However, I found that multicore CPUs are not yet as powerful as the GPU mostly due to the limited memory bandwidth..

In case of mipmapping, the advantage is that the number of slabs/RLE elements can be heavily reduced. I am not sure how your algorithm traces the RLE-structure, but I guess you might use binary-search in combination with a coarse 3D-grid to figure out the RLE elements that are hit by a ray. If Mipmaps are included, then the vertical search is at least one iteration faster for each level and the trace-length of the ray is doubled.

Its true that raytracing in general has a higher cost, but it really depends on the scene which algorithm is faster. In my case, I get a lot of overdraw for example, as I have to render most of the vertical elements without knowing which ones are visible. The only help are floating horizons from the top and the bottom that allow to skip RLE elements out of range.
Another thing is the view-transformation for each RLE-element that is required with the conventional voxlap algorithm - meaning a rotation and projection onto the screen. This is not necessary for the ray-tracer.

I'm looking forward to see your algorithms speed with mipmapping    I guess you might get pretty large scenes raycasted. Also it might be useful for reflected rays etc, if the result doesnt need to be too exact.

[IJs]

Primary ray hitting is where raycasting stops and raytracing starts. One of the key points with raytracing will be the lighting equations that can, and will, be added as I've sure you've seen in other raytracers: this is one of the reasons I started developing a real-time raytracing algorithm.

Realistic and physically correct (or approximated, dynamic) global illumination is something you will never be able to achieve with raycasting in it's current form: even rasterization is currently able to get a far higher quality than conventional raycasting with less work. Another point is that the viewpoint is not limited to any particular range either, like you see with some raycasters with nifty encoding techniques. e.g. In the case of photon mapping, it'll be really easy to extend the current raytracing algorithm: instead of tracing from an arbitrary point in space (as camera), just trace a single frame from the lightpoint's view and let the photons bounce around the scene. (This does of course rely on primary, secondary, and deeper rays.) That's just an example of how flexible raytracing can be.

As far as GPU's versus CPU's are concerned, GPU's currently pack a lot more power and are, in comparison with your CPU, more dedicated to 3D maths. They currently seem to be growing significantly faster in their performance, which is imo a good indication of their role in the future - they outrank the fastest desktop CPU out there with a GFLOPS rating that is an order of magnitude higher. Unfortunately it's memory bus does not scale the same way, thus being the major bottleneck in projects like these: it's key is to absolutely keep the bandwidth as low as possible.

My voxels are not encoded in an RLE- or tree-fashion due to performance reasons. However, their data (normals, etc.), which are stored separately from the voxel grid itself, are RLE-encoded (for each z-column) and then linearly iterated after a voxel hit has been found. This requires a maximum iteration of z per ray (in case there are z distinct voxels in one column), where z is the height of the voxel data set. This lookup can be done better, but it's performance hit can be neglected compared to the performance hit of the voxel grid traversal algorithm.