Can Ogre handle voxel environments?

Anything and everything that's related to OGRE or the wider graphics field that doesn't fit into the other forums.
Post Reply
User avatar
PolyVox
OGRE Contributor
OGRE Contributor
Posts: 1316
Joined: Tue Nov 21, 2006 11:28 am
Location: Groningen, The Netherlands
x 18
Contact:

Can Ogre handle voxel environments?

Post by PolyVox »

Hi all,

For about a year I have been working in volume graphics and attempting to build a voxel-based 3D graphics engine. Obviously building any 3D engine is a massive undertaking and I'm starting to think it would be benificial to integrate my work with an existing 3D engine so I can take advantage of all the facilities which are already provided (maths library, scene graph support, particle systems, etc). Ogre has come to my attention as being a well respected and flexible option.

For the uninitiated I will quickly explain the basics. Most 3d engines represent the world as a set of polygons. A room, for example, might be built of 6 polygons for the 4 walls, the ceiling, and the floor. This is very fast to render but has the limitation that the geometry is largely static. A voxel world, on the other hand, stores the world on a large 3D grid, say 512x512x512 voxels - literally the 3D equivilent of a 2d image. Each point on the grid keeps a flag indicating whether it is 'solid' or 'air' - no polygons are actually stored. The advantage of such a scheme is that it is very easy to change the flag bit so that 'solid' becomes 'air'; this gives truely destructible environments.

An excellent example is Ken Silvermans Voxlap engine (he's the creator of the Duke Nukem 3D engine all those years ago). Like I said I have my own engine but for the moment his is better. If you're curious you can try it at:

http://advsys.net/ken/voxlap/voxlap05.htm

A compiled version is in the ZIP i think.

So my question is how easily can a technology like this be integrated with Ogre? My very quick look at the docs indicates that there is some sort of scene manager which allows scenes to be BPS bsed, Octree based, etc. Is it possible to create a new scene type which is voxel based?

For clarity I've omitted details on efficient storage and rendering, I can give details on these if necessary. Essentially I'm just wondering how adaptable Ogre is to this type of environment.

Any thoughts appriciated,

David
User avatar
Kencho
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 4011
Joined: Fri Sep 19, 2003 6:28 pm
Location: Burgos, Spain
x 2
Contact:

Post by Kencho »

I'm not really sure but I would say "yes". Though Ogre has its own rendering pipeline and algorithms, it's definitely possible to do other kind of renders. Another user recently implemented raytracing instead of rasterising through shaders, so maybe this is the way you should go. I suggest you to ask him about the exact approach to use a different rendering method (voxels in your case) with Ogre.
Image
User avatar
Mikachu
Gnoll
Posts: 603
Joined: Thu Jul 28, 2005 4:11 pm
Location: Nice, France
x 35

Post by Mikachu »

I remember this technology was used in the first Delta Force; It looked quite good for the time, but was really slow because almost everything was done by the CPU. But now, with shaders and volume textures, an implementation inside the GPU may be possible.
I'm pretty sure I've already seen a discussion in the Ogre forum about a rendering method using something else than polygons. Maybe a good place to start?
OgreProcedural - Procedural Geometry for Ogre3D
User avatar
PolyVox
OGRE Contributor
OGRE Contributor
Posts: 1316
Joined: Tue Nov 21, 2006 11:28 am
Location: Groningen, The Netherlands
x 18
Contact:

Post by PolyVox »

Yes, I know the Delta force series used voxel engines and I've heard a game called Outcast used them to good effect too. Essentially they died due to the arrival of graphics hardware which could render polygons very fast but couldn't speed up voxel rendering operations.

This is changing, as the previous poster pointed out it is now possible to do raycasting on the GPU and raycasting is the most popular way to render voxels (that's how Ken Silverman did it, though his implementation was in software). This is a very powerful approach but the drawback is the volume could be very large (hundreds of megabytes uncompressed) and needs to be kept on the GPU. There also needs to be an efficient way to keep the CPU volume in sync with the GPU volume if we are to allow fully destructible worlds.

The alternative to raycasting is to keep the volume just in CPU memory (where it is easier to implement compression) and, each frame, to identify the boundary between 'air' and 'solid'. A polygon mesh is created of this boundary and sent to the graphics card. While it might sound crazy to generate hundreds of thousands of polygon each frame without storing them, this is the approach I have taken so far and I have a proof of concept showing it appears to be possible.

I must admit, I really don't know which way is best and will probably have to implement them both to see.

However, as I think about it more I believe it's likely that it could be integrated with Ogre. The volume can just be considered a way of encoding the positions of the polygons which are extracted and can probably be given a similar interface to other scene managers. Probably I'll spend some time playing with Ogre to undestand how it's designed, as my current prototype won't be finished for a few months...
User avatar
Borundin
Platinum Sponsor
Platinum Sponsor
Posts: 243
Joined: Fri Oct 03, 2003 5:57 am
Location: Sweden
x 2
Contact:

Post by Borundin »

esuvs wrote:A polygon mesh is created of this boundary and sent to the graphics card.
This all sounds very intresting but I was thinking that maybe polygon rendering is not the best fit in this situation. Ogre 1.2 supports point based rendering and maybe that would be a "better" approach? By better I mean keeping closer to the voxel idea.

See this link from before it was implemented http://www.ogre3d.org/phpBB2/viewtopic.php?t=12707

I guess a polygon mesh would mean fewer render calls since it could contain several "voxels". But on recent hardware it seems brute force might be the faster alternative sometimes.
Image : Image
User avatar
PolyVox
OGRE Contributor
OGRE Contributor
Posts: 1316
Joined: Tue Nov 21, 2006 11:28 am
Location: Groningen, The Netherlands
x 18
Contact:

Post by PolyVox »

I haven't read many papers on point based rendering but yes, it is a option. Essentially for each solid voxel in your scene you would render it as an appropriatly scaled circle, something most cards provide decent support for.

Actually, what I currently do isn't *that* different. I use an approach called marching cubes. Each group of 8 voxels defines the corner of a cube, and for a given cube there are only 256 inside/outside combinations. So for each group of 8 voxels I can precompute the set of 1-5 polygons which best fit it.

So basically, for each voxel it's a case of either drawing it as 1-5 polygons or as a point. I'm pretty sure it's faster to draw a point but it doesn't fit the geometry as well. Imagine a corner where 2 walls join, it's quite hard to represent a sharp edge as circles. It's also possible to apply texture mapping and other techniques to polygons to give the impression of more detail (maybe this is also possible with points, I don't know).

That said, you've just given me an excellent idea. Drawing points will be much faster (something like 12 bytes rather than 100 - the graphics bus appears to be abottle neck). It might be worth using points to draw more distant geometry and using my polygon geometry up close. I had been planning to try a level-of-detail approach to distat geometry but maybe point based rendering is better. Will have to try it and see at some point.

All in all this is the reason I'm still in the prototyping stage - lots of ideas to try!
User avatar
Borundin
Platinum Sponsor
Platinum Sponsor
Posts: 243
Joined: Fri Oct 03, 2003 5:57 am
Location: Sweden
x 2
Contact:

Post by Borundin »

esuvs wrote:I use an approach called marching cubes.
Lucky for you that the marching cubes patent just recently expired :D

esuvs wrote:All in all this is the reason I'm still in the prototyping stage - lots of ideas to try!
Please, keep us informed of your progress!
Always a good idea to rethink about "old" concepts when technology advances. They just might be the best choice after all..
Image : Image
User avatar
jacmoe
OGRE Retired Moderator
OGRE Retired Moderator
Posts: 20570
Joined: Thu Jan 22, 2004 10:13 am
Location: Denmark
x 179
Contact:

Post by jacmoe »

Look what I dug up for you - the DWORD marching cubes / isosurfaces demo/code (From way back when Ogre 0.15.x ruled the roost):
http://www.ogre3d.org/phpBB2/viewtopic. ... 8286#68286 :)
/* Less noise. More signal. */
Ogitor Scenebuilder - powered by Ogre, presented by Qt, fueled by Passion.
OgreAddons - the Ogre code suppository.
User avatar
Frenetic
Bugbear
Posts: 806
Joined: Fri Feb 03, 2006 7:08 am

Post by Frenetic »

Because voxel data can be so large, perhaps you could make aggressive use of paging data from disk to memory to GPU, as well as occlusion culling, and using a relatively small clipping volume.

The marching cubes idea seems interesting, because from what I see, you would only have to regenerate the geometry at locations where the voxels have changed. You could make each region an Ogre Renderable with the usual RenderOp and hardware buffer, and only refill the hardware buffer when the voxels for that region have changed.
User avatar
PolyVox
OGRE Contributor
OGRE Contributor
Posts: 1316
Joined: Tue Nov 21, 2006 11:28 am
Location: Groningen, The Netherlands
x 18
Contact:

Post by PolyVox »

jacmoe wrote:Look what I dug up for you - the DWORD marching cubes / isosurfaces demo/code (From way back when Ogre 0.15.x ruled the roost):
http://www.ogre3d.org/phpBB2/viewtopic. ... 8286#68286 :)
Well that's just awesome. If nothing else it proves that Ogre is sufficiently flexible to handle such an approach. I'll look at the code more carefully tonight. Though if you read through the post you'll notice it only runs interactively with a volume of 40x40x40 - most likely there is no culling being performed so the triangle counts get too large.

Using an octree and some hardware occlusion culling I can render my 256x256x256 volume interactively. It's a solid 'block' with eight rooms carved out and connected by tunnels. A 512x512x512 volume drops to about 1 FPS. More work to be done though!
Frenetic wrote:Because voxel data can be so large, perhaps you could make aggressive use of paging data from disk to memory to GPU, as well as occlusion culling, and using a relatively small clipping volume.
If I use a GPU based approach such as raycasting then yes, this could be useful. It could also be useful for only transmitting areas to the grapphics card when they change - i.e. keeping the GPU and CPU volumes in sync For the marching cubes version, however, the volume is not stored on the GPU. Breaking the volume down into blocks has other advantages though, many block are homogenous (all air or all solid) and you can then use sharing with a copy-on-write approach to drastically reduce memory usage. I haven't implemented this myself, but i intend to and it's how the system works at the medical visualisation company where I work.
Frenetic wrote:The marching cubes idea seems interesting, because from what I see, you would only have to regenerate the geometry at locations where the voxels have changed. You could make each region an Ogre Renderable with the usual RenderOp and hardware buffer, and only refill the hardware buffer when the voxels for that region have changed.
Actually I never store the result of the marching cubes - I run it on the volume every frame. That's why the Octree is useful or it would take ages, as it is it's pretty fast. It would be possible to store the mesh and just modify parts as they change but the mesh would get huge (millions of triangles.) Using occlusion culling I try to only run the marching cubes on parts of the volume I can see. Though it's not all working yet...
User avatar
Frenetic
Bugbear
Posts: 806
Joined: Fri Feb 03, 2006 7:08 am

Post by Frenetic »

esuvs wrote:Actually I never store the result of the marching cubes - I run it on the volume every frame. That's why the Octree is useful or it would take ages, as it is it's pretty fast. It would be possible to store the mesh and just modify parts as they change but the mesh would get huge (millions of triangles.) Using occlusion culling I try to only run the marching cubes on parts of the volume I can see. Though it's not all working yet...
I'm talking an incremental approach. Find out what sections (where each section is repesented as an Ogre Node/Object) of the volume are visible, run the marching cubes algo on them, and send that data to a hardware buffer. Only update, delete or add buffers when the structure or visibility of the voxel volumes change. (Areas you can't see should not be stored on the GPU, and in a large volume they could be paged from disk. When an area becomes visible, run the algo on it and store the result in a hardware buffer. When that area changes (ie. the voxels change) then regenerate the polygons and update the buffer (using HBL_DISCARD :)). When an area becomes no longer visible (due to occlusion or leaving the frustum's clipping volume) it should be unloaded from the GPU.

Generating the polygons every frame requires that you send them to the GPU every frame, which is not something GPUs like (especially since -- thanks to the granularity of voxels -- you are sending lots of triangles). Immediate-mode style rendering is very seldom necessary. So I suggest, instead, that you only change things on the GPU when there is a corresponding change in your visible geometry.

[EDIT] [EDIT AGAIN] Nevermind. :P
User avatar
PolyVox
OGRE Contributor
OGRE Contributor
Posts: 1316
Joined: Tue Nov 21, 2006 11:28 am
Location: Groningen, The Netherlands
x 18
Contact:

Post by PolyVox »

Frenetic wrote:I'm talking an incremental approach. Find out what sections (where each section is repesented as an Ogre Node/Object) of the volume are visible, run the marching cubes algo on them, and send that data to a hardware buffer. Only update, delete or add buffers when the structure or visibility of the voxel volumes change. (Areas you can't see should not be stored on the GPU, and in a large volume they could be paged from disk. When an area becomes visible, run the algo on it and store the result in a hardware buffer. When that area changes (ie. the voxels change) then regenerate the polygons and update the buffer (using HBL_DISCARD :)). When an area becomes no longer visible (due to occlusion or leaving the frustum's clipping volume) it should be unloaded from the GPU.

Generating the polygons every frame requires that you send them to the GPU every frame, which is not something GPUs like (especially since -- thanks to the granularity of voxels -- you are sending lots of triangles). Immediate-mode style rendering is very seldom necessary. So I suggest, instead, that you only change things on the GPU when there is a corresponding change in your visible geometry.

[EDIT] [EDIT AGAIN] Nevermind. :P
Hmmm, actually that has a lot of potential. It's basically a nice hybrid between generating everthing on the fly and precomputing the whole mesh - I guess it could almost be considered a kind of caching in that nodes which are likely to be rendered aging in the next frame are kept in an optimal form on the graphics card.

I'm still a little concerned about the memory, scenes can easily have 1,000,000 polygons visible at the moment. But I can easily lower generate level-of-detail meshes for more distant nodes which might just fix it.

At any rate you're certainly right about the large number of triangles being the limiting factor. Actually I do use vertex buffer objects at the moment; one vertex buffer object for each of the 256 combinations in marching cubes. The problem is it isn't really any faster than immediate mode which I put down to VBOs not being optimised for 1-5 triangle meshes, coupled with the fact that I still have to make one OpenGL per voxel (plus transformations).

I'm also wondering whether the next generation of graphics cards with geometry shaders could be useful... Must do some research at some point and find out what they actually do :?

Anyway, I shall definatly be thinking about your idea some more. Thanks!
User avatar
PolyVox
OGRE Contributor
OGRE Contributor
Posts: 1316
Joined: Tue Nov 21, 2006 11:28 am
Location: Groningen, The Netherlands
x 18
Contact:

Post by PolyVox »

I must say, this is the first time I've actually discussed this project with anyone and you've all bee most helpful! My boss just thought I was nuts when I said I thought marching cubes could run in real time!
martin.enge
Gnoblar
Posts: 20
Joined: Thu Feb 09, 2006 12:06 am

Post by martin.enge »

Also, check this out:

http://developer.download.nvidia.com/pr ... aph-06.pdf
the geometry shader for blobs using marching cubes is towards the end- page 43, but the really cool thing is on page 54 where they propose tesselation in post-projection space...

EDIT: I missed your second-to-last post... you probably already saw the presentation. Might be good for someone else, then.
User avatar
PolyVox
OGRE Contributor
OGRE Contributor
Posts: 1316
Joined: Tue Nov 21, 2006 11:28 am
Location: Groningen, The Netherlands
x 18
Contact:

Post by PolyVox »

martin.enge wrote:Also, check this out:

http://developer.download.nvidia.com/pr ... aph-06.pdf
the geometry shader for blobs using marching cubes is towards the end- page 43, but the really cool thing is on page 54 where they propose tesselation in post-projection space...

EDIT: I missed your second-to-last post... you probably already saw the presentation. Might be good for someone else, then.
That's pretty cool. Almost cool enough to make me wonder why I'm spending all this time doing it in software! The problem is I'm actually a little behind in terms of keeping up to date with the latest hardware - at work we still use OpenGL 1.1 and all our volume rendering is in software (shear-warp, etc).

However, even if geometry shaders are used for the actual isosurface extraction, I believe the existing ideas are still valid. The Octree and occlusion culling will still be needed to reduce the workload on the geometry shader. And maybe Frenetic's approach of useing VBO's is still applicaible - presumably it's posible to have the geometry shader write into a vertex buffer object rather than straight to the screen? Maybe that's asking too much?!
User avatar
yuriythebest
Orc
Posts: 468
Joined: Sun Jul 10, 2005 11:44 am
Location: Kiev, Ukraine
Contact:

Post by yuriythebest »

cool- probably the first game to use voxels was "surface tension"

*searches through giant pile of disks- 5 min later"

oh, here it is: created by Compro games in 1996! Surely that predates everything else. You flew a spaceship, it had destructible terrain that looken unlike anything else I've ever seen- it wasn't made of polygons, that's for sure. Ran fine on pentium 1, now that I try to install it- exactly 10 years after it's release, it complains that "this isn't supposed to run on windows NT" I have XP.
asteroidWars - an OGRE game
NOOB MAKE MMORPG- the flash movie
User avatar
Game_Ender
Ogre Magi
Posts: 1269
Joined: Wed May 25, 2005 2:31 am
Location: Rockville, MD, USA

Post by Game_Ender »

Did you try to run it in compatibility mode?
Jovani
Goblin
Posts: 297
Joined: Thu May 12, 2005 2:30 pm

Post by Jovani »

do not know if it was the first. but it run in DOS on a 386dx 16 mhz
http://www.mobygames.com/game/comanche-maximum-overkill
martin.enge
Gnoblar
Posts: 20
Joined: Thu Feb 09, 2006 12:06 am

Post by martin.enge »

Yes, comanche was great fun... it just used a "voxel" heightfield, though. Not exactly the same.
There was a fighting game in the middle of the nineties which used 3d voxels for characters (with bitmaps for background) which was considered pretty cool at the time.
User avatar
PolyVox
OGRE Contributor
OGRE Contributor
Posts: 1316
Joined: Tue Nov 21, 2006 11:28 am
Location: Groningen, The Netherlands
x 18
Contact:

Post by PolyVox »

martin.enge wrote:There was a fighting game in the middle of the nineties which used 3d voxels for characters (with bitmaps for background) which was considered pretty cool at the time.
This is the approach Ken Silverman takes in his voxel engine, *everything* is made of voxels including the animated characters, etc. Although interesting I'm not sure it has any real benifit. I was planning to use voxels for the main world geometry (so it's destructable) but use standard polygons models for objects within the world.

The other interesting problem is how physics works in such an environment. I expect most physics engines can't be used when the environment is not defined by polygons so it may be a case of writing a custom solution. But it may have some advantages - collision detection just becomes a case of taking an objects position and looking in the volume to see if it is 'air' or 'solid'. It's also quite easy to compute surface normals though I suspect some smoothing would be required. I have no experience in physics simulation though - maybe someone can shed some light on it?
User avatar
Kojack
OGRE Moderator
OGRE Moderator
Posts: 7155
Joined: Sun Jan 25, 2004 7:35 am
Location: Brisbane, Australia
x 527

Post by Kojack »

The Novodex/PhysX physics library has pmaps to speed up mesh collision. A pmap is a voxel block (defaults to about 64x64x64) around a mesh, where each voxel (1 bit) specifies if that region of the block is inside or outside of the mesh. But pmaps have been depreciated, so pretend I didn't say anything. :)
big_o
Goblin
Posts: 279
Joined: Sun Feb 19, 2006 1:08 am

Post by big_o »

Yeah, Comanche was my first sim game on the computer. :D I've owned or played every sequal to it since then. It was and still is one of the hardest games around, I haven't finished the last one yet.

Voxels do sound interesting, and in some ways simpler than using polygons, but there still appear to be quite a few gotchas.

Good luck!
User avatar
nikki
Old One
Posts: 2730
Joined: Sat Sep 17, 2005 10:08 am
Location: San Francisco
x 13
Contact:

Re: Can Ogre handle voxel environments?

Post by nikki »

Ok, I decided to try the Ken Silverman Voxlap thing with wine, and I must say, I'm impressed! It's pretty good for the few lines of code it is! I had great fun making underground tunnels. :P One funny thing though: If you make a really big 'island' out of the ground, and then shoot out the bottom (so it becomes a 'seperate piece'), it hovers in the air. :roll: Works for smaller pieces though (like in that 'loop-de-loop' thing).
User avatar
Kojack
OGRE Moderator
OGRE Moderator
Posts: 7155
Joined: Sun Jan 25, 2004 7:35 am
Location: Brisbane, Australia
x 527

Re: Can Ogre handle voxel environments?

Post by Kojack »

It probably only scans a small region to check for connectivity to the ground to speed up the updates. Although it runs so fast (without and gpu or multicore assistance) that I'm sure the island size could be increased.
Post Reply