What are voxels and how do they work.

It's a volumetric description of space!It can use to made destroyable system or dynamic terrain.

http://en.wikipedia.org/wiki/Voxel

Quote:

It's a volumetric description of space

Could you expand on that please? Is it a sphere or something then?

Quote:

It can use to made destroyable system or dynamic terrain.

When I said how they work in terms of games I was more implying how do they fit in with the fact that GPUs work on polygons etc.

I have implement for cad-cam system and i never implement in a game. My system are very simple and i use a 3d array of bit. The bit was set to true if there's metal and false if in empty. I start with a block of full metal, all array was set to true, after i simulate the machine work and when the tool meet the material (element of matrix true) i set it false. This is a very simple implementation.
I have read of GPU implementation bat i never work on it.

Xues32

Here goes, imagine an area of 3d space. Imagine a 3d pixel (a small cube) in this space. Your screen is made up of a lot of pixels and your 3d space in comparison is made up of a lot of this cubic pixels, called voxels. Hence the name, voxel (volumetric pixel). Instead of building a 3d house out of polygons, as per traditional 3d graphics, you could build it out of 1000's of these little cubes (each with its own color). This is the art of voxel graphics. There are many things voxels can do that polygons cant, but the big problem is that there is no real hardware support for voxels, which is why they are not commonly used.

The best example of voxels is ken silverman's voxlap engine.
Demo can be found here http://www.advsys.net/ken/voxlap/cavedemo.zip

Try going realy close to a cave wall to see the tiny voxels that make up the surface.

Quote:

Original post by chosendl Here goes, imagine an area of 3d space. Imagine a 3d pixel (a small cube) in this space. Your screen is made up of a lot of pixels and your 3d space in comparison is made up of a lot of this cubic pixels, called voxels. Hence the name, voxel (volumetric pixel). Instead of building a 3d house out of polygons, as per traditional 3d graphics, you could build it out of 1000's of these little cubes (each with its own color). This is the art of voxel graphics. There are many things voxels can do that polygons cant, but the big problem is that there is no real hardware support for voxels, which is why they are not commonly used.

Put another way, they are rarely, if ever, used in games. [smile]

-me

Quote:

There are many things voxels can do that polygons cant, but the big problem is that there is no real hardware support for voxels, which is why they are not commonly used.

Brilliant explaination, thank you. :) They seem very impressive, although I'm curious to what they can do that polygons can't?

Quote:

Try going realy close to a cave wall to see the tiny voxels that make up the surface.

Yes, I notice now. ;)

Quote:

Put another way, they are rarely, if ever, used in games.

I guess this is because of the processing required and the lack of hardware support?

---

They look very interesting, certainly something I would like to learn much more about. Could anybody point me to resources where I could learn more about them - but more importantly how to apply them into games?

Thank you,
NB.

Is it safe to say that (computer graphically), pixels make voxels and voxels make the objects in the scene?

Is there such a thing as a voxel shadow or voxel light?

That i am not so sure about, as there are not many games that use them. and yes, speed is a huge problem for voxel engines, although ken's work is rather impressive, and if combined with some form of hardware accelaration, it should produce gameable results, i'd say.

A voxel engine is completely, at present, software drive. So voxel shadows and lighting effects, are whatever you program them to be, if any.

They are indeed very interesting, and the Voxlap demo is a good example of them in action. For me the thing which makes them interesting is the dynamic environment - individual voxels can be easily created or destroyed to allow you to blast holes though walls, etc. If you didn't try this in the Voxlap demo then you missed the best part!

The most significant drawback is probably the amount of memory required, as has been mentioned already. Because you are essentially breaking the world into a 3D grid and storing a value for every point memory dissapears very quickly. Imagine you have an environment 10m x 10m x 10m, and that you want to represent details down to 1cm (i.e. using 1cm voxels). That's 1000x1000x1000 voxels! With a naive approach that would be 1GB memory, but Run-Length Encoding approaches can be used to reduce the memory requirements.

There is also no native way to render them. In my engine I generate a mesh from the volume and update that each time the volume changes. It works well, but the drawback is that you have a lot of polygons to render. See my project here:

http://www.david-williams.info/index.php?option=com_content&task=view&id=24&Itemid=37
http://www.ogre3d.org/phpBB2/viewtopic.php?t=27394

An alternative is to use raycasting to render the volume. This can now be accelerated on the GPU as is done by the only other engine I know of:

http://www.xinix.org/sven/main/publications.htm
http://www.gamedev.net/community/forums/topic.asp?topic_id=465985

For learning it about them you should Google for 'marching cubes' for the surface extraction or 'GPU Volume Raycasting' for the raycating approach. Well, that should get you started anyway :-)

I suggest you play with the various existing engines and think what you want to do. I'm currently trying to seperate my voxel code into a library which can be used by other applications, so if you give me a few weeks you might be able to make use of that (it will probably be GPL).

One last point - you may encounter confusion with other games which claim to use voxels, such as the Delta Force games, Outcast, etc. As far as I can tell this is an abuse of the term 'voxel' (probably thanks to the marketing department). The games use raycasting for the rendering (i.e. the same technique that can be used to render voxels) but the world is actually represented by a heightmap.

Quote:

although ken's work is rather impressive, and if combined with some form of hardware accelaration

He certainly seems to know what he's doing! The optimisations in his source code are extreme!

Quote:

you may encounter confusion with other games which claim to use voxels

Yes, I've already seen the marketing for those games, didn't know that it was just hype though.

Quote:

Run-Length Encoding approaches can be used to reduce the memory requirements.

I'm assuming you mean ram here? Although if a voxel is treated as binary, how is colour applied - surely each voxel can't be assigned a 32-bit colour... The memory demands would make it unusable.

Quote:

I'm currently trying to seperate my voxel code into a library which can be used by other applications, so if you give me a few weeks you might be able to make use of that (it will probably be GPL).

I look forward to it and will keep a close eye on the project page. ;)

Quote:

When I said how they work in terms of games I was more implying how do they fit in with the fact that GPUs work on polygons etc.

There are several techniques for rendering volumes. In medical imaging we often use the "slice" technique. Basically you create a 3d texture on the video card, and then you render slices (quads) at regular intervals, setting the texture coordinates accordingly. You can then do some very nice visualizations using clipping planes to see cross sections of the volume or adjust the alpha values to remove voxels of certain tissue density (for example, set the alpha of any voxel with the denisity of skin to 0.0 and visualize only the hard tissue).

Quote:

I guess this is because of the processing required and the lack of hardware support?

Pretty much. Volume rendering can produce a lot of overdraw, which means your video card needs to have a very high fill rate to render a full volume at interactive frame rates. Most video cards have pretty poor fill rate performance due to the limited memory bandwidth (though this is improving). Even if the video card supports 3d textures, the limit will often be 512^3 or 256^3 or smaller. We regularly have to deal with large CT scans that can be 1GB+. This will not obviously not fit in video memory (although this is also changing rapidly). A common solution is to break up the volume into smaller volumes, and build the full volume by rendering the small chunks in multiple passes ("bricking" technique).

Quote:

I'm assuming you mean ram here? Although if a voxel is treated as binary, how is colour applied - surely each voxel can't be assigned a 32-bit colour... The memory demands would make it unusable.

You can use hardware color tables to map voxel values to color values. You can also use pixel shaders to create more complex transfer functions.

Quote:

Original post by NewBreed Quote: although ken's work is rather impressive, and if combined with some form of hardware accelaration He certainly seems to know what he's doing! The optimisations in his source code are extreme!

Check out the publications on Sven's page - I think they have a lot in common with what Ken does. I'm not really able to tell you much about this though...

Quote:

Original post by NewBreed Quote: you may encounter confusion with other games which claim to use voxels Yes, I've already seen the marketing for those games, didn't know that it was just hype though.

Well that's my opineon, rather than solid fact ;-) But they don't use volumes, so it seems a bit cheeky to call it a voxel engine.

Quote:

Original post by NewBreed Quote: Run-Length Encoding approaches can be used to reduce the memory requirements. I'm assuming you mean ram here? Although if a voxel is treated as binary, how is colour applied - surely each voxel can't be assigned a 32-bit colour... The memory demands would make it unusable.

Good question - actually I guess how you do it is up to you. In my case I allow one byte per voxel and this is used as a lookup into a material table (including textures, etc). So this gives you 256 different materials in your world. But the concept of texture mapping doesn't really apply in the same way (you need to think how voxels would get thier texture coordinates?) so you lose a lot of flexibility compared to polygon engines.

Quote:

Original post by NewBreed Quote: I'm currently trying to seperate my voxel code into a library which can be used by other applications, so if you give me a few weeks you might be able to make use of that (it will probably be GPL). I look forward to it and will keep a close eye on the project page. ;)

Great, but it will be a while before I post again as I want to add some physics before showing it off. But I could always send you a private message when the seperation is done.

Quote:

Basically you create a 3d texture on the video card, and then you render slices (quads) at regular intervals, setting the texture coordinates accordingly. You can then do some very nice visualizations using clipping planes to see cross sections of the volume or adjust the alpha values to remove voxels of certain tissue density (for example, set the alpha of any voxel with the denisity of skin to 0.0 and visualize only the hard tissue).

Thanks, I'll have a look at that.

Quote:

Great, but it will be a while before I post again as I want to add some physics before showing it off. But I could always send you a private message when the seperation is done.

That's okay, I've got it bookmarked - I won't be forgetting about it anytime soon! :)

Thanks all,
NB.

Ken Silvermans code was written when he was 16, as was his 3d engine (or before that age).

3DRealms found his engine, and bought it/employed him - thats when Duke3D was made (the Build engine, ie Kenneth's Build Engine).

Duke3D was voxeless, even though the engine allowed it (aswell as heaps of other stuff)

They they made Shadow Warrior, and Monolith made Blood. Both these games used voxels.

when i was in the team for duke3d v2 (eduke, the project with matt saettler who was the programmer on blood or shadow warrior - or both, i forgot, check his website) they re-added voxels to the duke3d game.

Also, Ken's code allows for a conversion that generates from a multi-sided sprite into a voxel model (takes slices out of a cube from different angles).

His code is lots of fun to play with - however you (atleast use to) need the watcom compiler and usually used the dos4gw expander. I think there is a free watcom c around somewhere now, and ken may still have the code on his website for the entire build engine.


As for delta force - i think the voxels were only used for the grass (strands of grass) and maybe for some of the towers in the air, and when a weapon was on the ground, the rest was polys.

As for a voxel, it doesnt have to be a cube
http://members.optushome.com.au/jlferry/download/
its any volume. its like when you do FEA, its a voxel, an infinetly small volume, but it can be any shape - cubes and balls are the easiest to render and represent, and in most cases a cube or pyramid is the fastest, but you COULD render thousands of tiny volks wagon beetles, where each car represents a point in space.


http folder

the ball in that image was around 1000000 voxels or something. - i forgot.
basically a sphere with a diameter of about 128 pixels - could have been bigger, i forgot, maybe 256. the data was stored in a 3d link list (oh, the build engine is a great example of a 2d linked list, including the voxels).
In that screenshot, its running at around 30 (top left - and i forgot what the third line/scale was for - it was timing something) - 6 colourd lights (non directional) in textured mode. was on a geforce 2 on a 1.6ghz amd i think.

If you can get it to work I'm rather happy - I'm sitting at work and it won't run :)
If you can run it, the right hand side is to turn on lights and change colours of it etc, the 4 small square icons are for the rendering mode, spherical, cubic, textured cubic or point voxels.
It's about 3 computers and 6 hard drives ago (2002), so i MIGHT be able to find the source code, but I'm not willing to.

//edit - used ubb code instead of html

Quote:

Ken Silvermans code was written when he was 16, as was his 3d engine (or before that age).

16... Erm... wow...

Quote:

when i was in the team for duke3d v2

You helped make duke3d? :O I remember playing that around my mates house for hours and hours! Dukes' voice clips were fantastic. :D Those trip bombs were brill. ;)

Quote:

If you can get it to work I'm rather happy - I'm sitting at work and it won't run :)

No unfortunately it isn't running for me either. I get an unhandled exception when I try to run it.

Quote:

so i MIGHT be able to find the source code, but I'm not willing to.

Well if you change your mind, please do post it. I would be quite interested in seeing it.

---

Something that is still confusing me about using voxels, as good as they seem I can't figure out how you would do animation with them?

For example if you've got a voxelated (?) character, how is animation done without making the entire PC crawl to a stop - and even assuming you used an animation in frames, there is still the tweening to do for the inbetween animations?

Thanks,
NB.

Kens method of using a 6-sided sprite map to generate the voxelated object, is of course a brilliant solution. For each frame, you have 1 of these 6-sided sprites and generate the resulting object in voxels, while you are rendering. This way you do not have to store 1000000's of voxels for all of the frames, you only have to store the sprites!

Ken silverman is my new hero!

Quote:

Kens method of using a 6-sided sprite map to generate the voxelated object, is of course a brilliant solution.

Could you explain this further please?

Quote:

Original post by NewBreed Quote: when i was in the team for duke3d v2 You helped make duke3d? :O I remember playing that around my mates house for hours and hours! Dukes' voice clips were fantastic. :D Those trip bombs were brill. ;)

I would guess that Duke3D v2 was an unofficial update, the Duke3D sourcecode was released under the GNU GPL in 2003.

OK this is a bit hard to explain, im not sure i even understand it correctly, so correct me if im wrong guys, but this is how i would implement it.

like a dice, all voxels have 6 sides, so an object made from voxels could be viewed from 6 sides, flat on. This would give you 6 2d sprites. Our special sprites, contain information: Red, green, blue and depth, for each pixel in the sprite. The rgb is the color of the particular voxel you were seeing along that line and depth is how many voxels deep it is (from the surface of the sprites viewing plane. If you can wrap your head around what ive just said, you will end up with 6 sprites instead of a lot of voxels. Interesting thing is that when you recreate the voxel object from the sprites, you loose alot of voxels that were there before (specifically all inner voxels that you could not see, which is ok, because you couldn't see them to begin with). The object when recreated is actually hollow, only the outer layer of voxels is used, the voxels seen from the 6 sides.

There is of course a problem with this method: When viewed from a side you could miss a ditch or crevice that is only visible from another angle, so you would have to figure out how to code around such problems.