Awesome library David.

Bunch of rambling ideas/suggestions/questions.

My main use case for polyvox would be surface terrain generation. I would use noise to generate a hollow surface-only volume of voxels and would only generate the hollow part as needed (as it becomes uncovered). Would this possibly reduce computational complexity (maybe from full 3D volume to 3D surface area)? How would the Volume container handle this? Would it be possible to optimize or make a different Volume container that handles it better, etc? Can the surface extractors be optimized for this sort of task?

In my project, having a destructible environment is not my primary concern. Caves, overhangs and other natural looking terrain is my goal. Therefore I would be content with hollow terrain. If/when terrain is destroyed, generating the necessary terrain underneath shouldn't be too difficult. Am I going about things wrong?

For LOD I am thinking of using the first octave of noise for the lowest LOD, and use progressively more octave levels for each level of LOD. This way, instead of requiring the tremendous amount of voxels at the lowest level, and working up to generate lower LODs, would this help to generate the LODs from lowest to highest as it is needed? Am I going about this wrong? I am aware that polyvox does not handle combining volumes of different LODs, but that Eric Lengyel has released his algorithm that can. If polyvox fits what I want, I'll take a look at integrating it into the library.

Also, voxel generation is so slow, how does anyone use paging? It would be nice to be able to access multiple voxels at a time, or to merge volumes together, so that each voxel does not have to be set individually. Each call to setVoxel is so slow ... doing it for a 3D volume is that much slower.

_________________
irc://irc.freenode.net/#polyvox

uhm... are you from Italy? that "content" sounds sooo close to "contento" that is "happy" in english
back on topic, generation of voxels should be faster by using the callback functions provided by the new volume class. Paging is automated so you have almost to do nothing, except for providing that callback function. (the same that would allow you to load volumes from the hard drive)
Regarding speed, I've been studying how to increase polyvox speed a bit, but it's not easy unless you start adding friend classes and functions. One of the ideas I had was to have some way to make a local copy (straight memory copy) from one block to a buffer given by the user, but I'm not sure how much elegant this solution is, and how much faster it would be.

Thanks


Having your terrain as a thin shell rether than a solid object will have a negative effect, because PolyVox will generate polygons on both sides of it. I.e. there will be polygons point up from the shell to the empty space above, but there will also be polygons pointing down from the shell to the empty space below. This is necessary because PolyVox doesn't know where you are going to place the camera.

The volume class will store the data quite happily, but you will get more polygons during surface extraction.



This sounds messy as you've potentially got different data in the differnt LOD levels. The Eric's TransVoxel algorithm will handle the crack which occur when one volume is simply a lower resolution version of another volume, but I think actually placing differnt data into each volume will cause problems.



Yeah, I've heard there are some performance issues here. I can't yet tell you where the problem lies (paging, compression, use of std::map, etc) as it needs some investigation. But I'm currently in the process of modifying PolyVox to allow different volume classes, and will then add a simple raw data volume which can be used for comparison.

'Content' means 'happy' in English as well. Or rather it means 'happy enough'

Oh, I see... I must say I completely forgot about that meaning... Perhaps it's because of all the DLC you get with games now
I don't think they mean "Downloadable Happyness" ^^

That's an idea! I should totally introduce DLCs in my game and regard them as Downloadable Happyness from now

So since I made this post, I have done some research and can now fully articulate what I wanted.

Basically:

A Volume class that instead of storing the entire volume, simply implements getVoxel(). This makes it more amenable to procedurally generated volumes. Caching/compressing etc. is all up to the implementer.

Separating the Surface Extractor into two classes:

A Marcher and a Surface Extractor .

To explain what I mean by Marcher: the current implementation implements a naiive marcher: simply iterate through every possible voxel, call getVoxel(), send a cube at time (8 voxels) to the marching cubes algorithm, or whatever equivalent Surface Extractor is being used.

A smarter Marcher for some use cases, would be given a starting voxel position, and only march along surfaces. Thus, instead of iterating through n^3 voxels, it would travel across O(n^2) in a normal use case. Of course it is possible to make a surface that has a worst case of O(n^3) but that would obviously not be a good use case for a "Crawling"/"Creeping" Marcher. After thinking of this idea, I searched and searched (there must be a paper on this, right?) and I only found an informal idea written by Thomas Schumm: http://www.phong.org/opengl/. Josh Parnell reports on the benifits of the algorithm: http://joshparnell.com/blog/2010/11/26/crawling-cubes-algorithm/. And it makes perfect sense: with O(n^2) average running time, a voxel world is in the same league as traditional graphics and 2D images; making the impossible possible.

Together these two ideas can allow for faster and *much* less memory hungry mesh generation from voxels.

I am trying to implement these on my own for now.

Oh and btw, I really love your coding style; it matches my own +/- some tricks.

_________________
irc://irc.freenode.net/#polyvox

My new ideas solve this of course.

And, with a custom Extractor, I could even generate polygons that face only a certain way etc.

I am working on an implementation of my ideas suggested above, and my Extractor is very generic, and allows callbacks and policies for every detail I can manage. Thus, one can easily choose to ignore triangles, or do any sort of custom generation without too much hassle.


The problem with his algorithm is that it seems to require to average or otherwise process the higher resolution voxels to generate the lower LOD surface. This seems wasteful; it saves space, but requires similar amount of CPU time/computational complexity. Thus for example, you would not be able to deal with an entire (actual size) planet of voxels ... that would require building up from the bottom. But fractal noise naturally builds down from the top ... that is, you get a low resolution of noise (smoothed out), and you then add its own (faded) image four times into itself at half resolution; this adds detail, but from a distance this detail is not really visible. I am trying to apply the same idea to voxel generation. I dunno if it will mess up the crack-patching algorithm; I'll get back to you . Otherwise, there are other methods of zooming with a top-down approach I am investigating.


Noise generation is the best compression .

To support destructibility in my world, I intend to use an inverse Volume; one that would indicate where the world differs from the noise generator. Thus, my volume's getPixel would first check the inverse Volume, then if it finds nothing, it would ask the noise generator for a voxel (I am using the Simplex noise generator for 3D btw).

I am also using my own Surface Extractor for now, using the regular cell data from the Transvoxel Marching cubes.

_________________
irc://irc.freenode.net/#polyvox