   An Efficient Voxel Representation
  I was just reading the Virtually Destructible Environments thread. Some of the guys there suggested voxels, but it was said that voxels would require way too much memory to be worth the trouble, at lest from a purely graphical standpoint. With the naive approach to voxels, I cannot agree more. But this got me thinking: it may be possible to make certain optimizations, which would make voxles more practical. Here are the four that I could come up with off the top of my head:1. Don't use the same voxel size all over. Only use smaller voxels where that extra detail is needed. Kinda like an octtree.2. Only place voxels near the surface of the geometry. If you need to make a hole somewhere, and some of the affected area is not voxelated - add a few more voxels to cover the unvoxelated area, and split them as necessary as the hole is made.3. Don't constrain yourself to axis-aligned cube-like voxels. This would make things more complicated, but it will make it easier to represent difficult geometry like walls or even trees with much fewer voxels.4. It is sometimes possible to restrict voxels to the lower frequency data, and add the higher frequecies on top of that procedurally (e.g. with perlin-noise-controlled displacement). This would mean larger and therefore much fewer voxels.What do you think? Has anything like this been done before? What other optimizations could be done?   
  search for ken (EDIT) silverman voxel thing. yes the guy from the duke3d engine.it does quite a huge world in realtime, completely destructible, textured, and generally just looking very awesome.besides, the memory profile seemed not too big when i used it. octrees me thinks, yes, and god knows what other funky things. completely traced in software btw.   ;  teh link for you:http://advsys.net/ken/voxlap/voxlap03.htmit would rock to have this tech develop into hardware. it just opens up so much gameplay possibilities...   ;  Eelco, I checked that out. From what I can see, there is still much to improve there. I couldn't tell if they're using my 2nd suggestion (although I'm guessing they are not), but it doesn't seem they are using any of the other three. It appears they are using axis aligned cube-like voxels of an identical size. Or perhaps they only store the center of each voxel in a uniform grid, and the inersections make them look like cubes... Further, since their voxels are of the same size, the voxels end up being too big, making their demo look like those old DOS games that ran at 320x240 resolution. I doubt most gamers would happily accept that today.I propose a different approach. Don't store only the center of the voxel, but also its dimensions and orientation. Have a few different types of voxels: cube, box, cylinder, etc. Or alternatively, if you want to only store the centers, don't constrain yourself to an axis-aligned uniform grid. This takes care of 1 and 3. Then, don't store any voxels at all where there are no discontinuities near them. That takes care of 2. and beyond that, perhaps use a hybrid approach, where the voxels are just an intermediate step. When you want to render, create a polygonal mesh based on the voxels (e.g. using marching cubes algo), tesselate as necessary, and add fractal detail where appropriate. This eliminates the blocky appearance and takes care of 4. Of course, you could use the voxels for rendering directly, but then you'll need much smaller voxels, which in turn means much more of them to deal with.   ;  to adress your points:Quote:1. Don't use the same voxel size all over. Only use smaller voxels where that extra detail is needed. Kinda like an octtree.its using an octree for sure. otherwise it would never fit into such a small piece of memory, or run this fast.Quote:2. Only place voxels near the surface of the geometry. If you need to make a hole somewhere, and some of the affected area is not voxelated - add a few more voxels to cover the unvoxelated area, and split them as necessary as the hole is made.given this particular demo is voxel-traced, culling hidden geometry makes no sense at all. if you were to rasterize it, then ofcource youd only be interested in the surface, but due to the nature of the octree youre without a doubt using, removing cubes will still only be a pain in the ass.Quote:3. Don't constrain yourself to axis-aligned cube-like voxels. This would make things more complicated, but it will make it easier to represent difficult geometry like walls or even trees with much fewer voxels.appearantly youre not as amazed as i am to see this demo running realtime... stepping away from voxels also means letting go of the destructabe terrain, unless youre planning some fancy CSG as mentioned in the other thread.Quote:4. It is sometimes possible to restrict voxels to the lower frequency data, and add the higher frequecies on top of that procedurally (e.g. with perlin-noise-controlled displacement). This would mean larger and therefore much fewer voxels.possible, but octrees also take case of that in a way. just trace the tree down to the desired resolution. maybe on close range some interpolation could be done as to smooth out the individual voxels, and then addd some noise.stepping away from AA voxels makes the destructive terrain part much and much harder, and stepping away from the raytracing will cause you to have to deal with the tesselation of your solid world to surface representation, not easy either.i think this demo does a very impressive thing, without using any hacks.   ;  It's impressive, but also....useless. It's just not practical for a real game world at this point in time.   ;  Etnu: I watched some of the demos on my TV and it looked really good. I belive that this engine (with some improvements) could be used to create games for gamecube or similiar. Maybe team 17 could make a proper version of worms 3d with it or something...   ;  Maybe, but most of what you could accomplish could be done far more efficiently using traditional polygon-based approaches.*Shrug*.   ;Quote:Original post by Eelcoits using an octree for sure. otherwise it would never fit into such a small piece of memory, or run this fast.I wasn't talking about using an actual octree. It is indeed a possibility, but is not what I meant. I was suggeting the use of voxels that are not all of the same size (as opposed to all the voxel systems I'm familiar with). I only refered to an octree as a visualization aid, because if you have box-like voxels of varying sizes, then they would look very much like the cells (i.e. node volumes) of a typical octtree.Quote:given this particular demo is voxel-traced, culling hidden geometry makes no sense at all. if you were to rasterize it, then ofcource youd only be interested in the surface, but due to the nature of the octree youre without a doubt using, removing cubes will still only be a pain in the ass.It make sense in the fact that *removing* (not just visually culling) such voxels would drastically reduce your storage requirements, regardless of the rendering method. Of course, if you're tracing through transparent geometry, than removing internal voxels may be unwise. But then you have also the tracing performance to deal with. And as for the pains involved - if for each voxel you maintain a set of flags telling you which sides of the voxel touch a discontinuity of some sort, then identifying and removing non-boundary voxels becomes almost trivial.Quote:appearantly youre not as amazed as i am to see this demo running realtime...It is not the first realtime voxel demo that I see. So I already know that voxels can run in realtime and look more or less good while allowing for caves and full deformability. I saw that a long time ago, so I don't really see anything new in this demo, except maybe that the number of voxels has been increased significantly. What I want to see now is the next step - a voxel engine that can actually compete with a modern polygonal engine in terms of visual quality, while still retaining the advantages of voxels.Quote:possible, but octrees also take case of that in a way. [...]Again, my main point here was to reduce the storage requirements.Quote:stepping away from AA voxels makes the destructive terrain part much and much harder, and stepping away from the raytracing will cause you to have to deal with the tesselation of your solid world to surface representation, not easy either.The destruction compexity mostly comes down to how you subdivide your voxels. Like I wrote earlier - you start with one big voxels (or a few big ones), and subdivide it recursively removing what you don't need. Yes, it is more difficult than just marking a few grid cells as empty, but what you loose in simplicity, you gain in storage requirements, and mayeb even performance. That allows you to work with much larger, more detailed worlds. As a compromise, it's possible to stay AA, but still use variable-size voxels. And as for the tesselation - yes, it's hard, but you gain hardware acceleration for the rendering.   ;  In Ken's cave demo,voxels are NOT limited to be axis-aligned.Look better,destroy the world and see how pieces fall.In my direct heightfield raycasting/tracing demo ( Voxel World) , voxels can be interpolated better so as result it does not looks so cubistical.edit:2technobot:and also,i must say,Ken's cavedemo already are VERY complicated thing.Not everyone can imagine.1:It does not store inside of geometry,absolutely surely,otherwise it would take MUCH more ram.2:I guess,it does all practical memory usage reducing tricks,and especially ones you haven't listed there.I think he thought about all that.I know several tricks too but will not explain because i'm working in that field(well,wrong argument in discussion,but really).I independently thought about REALLY many tricks,including non-axis aligned voxels,octtrees,non-cubical voxels,interpolation to make 'em look smooth , and other things (such as storing voxel data in fourier domain ,wavelets...)[Edited by - Dmytry on July 18, 2004 1:34:20 PM]