Volumes Of Fun
http://www.volumesoffun.com/phpBB3/

Infinite volumes with LOD
http://www.volumesoffun.com/phpBB3/viewtopic.php?f=14&t=317		 Page 1 of 1
Author:  Gnurfos [ Fri Jan 20, 2012 9:22 pm ]
Post subject:  Infinite volumes with LOD
Hello,

Like many, I have the ambition to build a more or less infinite world generator.

After having seen the Paging example, using LargeVolume, I have a few questions:
    - at first the documentation was a bit worrying, with talks about "running out of memory", which made me think that the user has not much control over when paging occurs. But actually, seeing the example and other functions, I would say that, if he is careful of not overflowing memory (it that detected by bad_alloc or something similar?), the user has full control and loads/unloads pages at will. Could you confirm ?
    - it seems that the LargeVolume does not allow variating LOD, because all chunks are of the same dimensions ?

I implemented my own paging system, using SimpleVolumes as pages, so that I could vary their resolution, but I ran of course into alignment problems at the borders between volumes with different resolutions. I remembered there was talk about implementing the "Transvoxel" algorithm in Polyvox some day (maybe in the old forums). Is this still planned ?
One that wiki page, there is an item called "Support for Eric Lengyel's voxel terrain lod system", so that could be it. But that page is old, and the item is not present in git's TODO.txt.

If some external user was to implement it for polyvox (I don't know if I could, but it would surely be interesting to try), what kind of volume do you suggest having it operate on ?

PS: I think there are a few outdated/wrong copy-pasted information in the doc, namely for the constructors of SimpleVolume and RawVolume (they refer to using some other constructor that doesn't seem to exist anymore).
Author:  GM_Riscvul [ Fri Jan 20, 2012 11:09 pm ]
Post subject:  Re: Infinite volumes with LOD
PolyVox has a max amount of chunks it will store in memory, which I believe (correct me if I am wrong) is limited to max uint_32. After that point paging occurs automatically through the overload handlers you provide. Of course you can handle paging yourself using prefetch and flush. However you shouldn't run into any memory allocation issues because polyvox will handle that even if your overloaded handlers are empty.

As far as different LOD I would imagine you would find it easier to write your own extractor class rather than use that many simple volumes.

For your other questions you will have to wait for David. I'm not going to be much help there, although I know there were some threads in the forum about implementing the transvoxel algorithm, perhaps they might help.
Author:  David Williams [ Sat Jan 21, 2012 4:04 pm ]
Post subject:  Re: Infinite volumes with LOD
Gnurfos wrote:
    - at first the documentation was a bit worrying, with talks about "running out of memory", which made me think that the user has not much control over when paging occurs. But actually, seeing the example and other functions, I would say that, if he is careful of not overflowing memory (it that detected by bad_alloc or something similar?), the user has full control and loads/unloads pages at will. Could you confirm ?


The LargeVolume can support an 'infinite' number of blocks but most of these are not loaded into memory at a time. If you try to access a block and it is not in memory then a callback is executed giving you the chance to load that data from disk/network/database/etc. If this causes the number of blocks in memory to become to large then the oldest block is removed from memory and given to you (again through a callback) giving you a chance to store it back somewhere.

Gnurfos wrote:
    - it seems that the LargeVolume does not allow variating LOD, because all chunks are of the same dimensions ?


The representation in memory should be independant from the surface extraction algorithm. Even if the whole volume was one single continous peice of data in memory (i.e. the RawVolume), you can still choose to only extract a surface for only part of it.

At least, that is how it works with the existing extractors. Marching Cubes doesn't care how the data is stored (raw data, octree, blocks) as long as you can call getVoxelAt() on the relevant position.

Perhaps Transvoxel is more complex, but I think the same principle should apply. You choose the region of the volume you want the mesh for (ignoring the underlying representation), you possibly copy that data to a RawVolume and downsample it, and then you run the extractor.

Gnurfos wrote:
I remembered there was talk about implementing the "Transvoxel" algorithm in Polyvox some day (maybe in the old forums). Is this still planned ?
One that wiki page, there is an item called "Support for Eric Lengyel's voxel terrain lod system", so that could be it. But that page is old, and the item is not present in git's TODO.txt.


Hmmm... I forgotten we had two lists - we should resolve that. Anyway it is still planned though not anytime soon as I'm simply not using it in the forseeable future (our current game is bult on the cubic extractor). But I have noticed a few implementations of Transvoxel popping up on the web, so it shouldn't be too hard to implement.

Gnurfos wrote:
If some external user was to implement it for polyvox (I don't know if I could, but it would surely be interesting to try), what kind of volume do you suggest having it operate on ?


Again, ideally it shouldn't matter (though this might not be the case). I don't think we would provide a 'complete' implementation of transvoxel terrain in that I think a complete implementation requires custom vertex shaders for example. In the same way, we don't provide a complete terrain system based on Marching Cubes - we just provide the extractor and leave the user to work out what regions they need to extract. PolyVox has no concept of a camera position (which is relevant for LOD) and I would expect this to stay in user code.

Quote:
PS: I think there are a few outdated/wrong copy-pasted information in the doc, namely for the constructors of SimpleVolume and RawVolume (they refer to using some other constructor that doesn't seem to exist anymore).


I only see one RawVolume constructor and it's this one: http://www.volumesoffun.com/polyvox/doc ... 3ad118987f

Are you referring to something different? But yes, over Christmas I had a discussion with Matt about our release system and what we can change. Using proper version numbers and matching up the docs, etc. Hopefully we will make some improvments here soon.
Author:  Gnurfos [ Sat Jan 21, 2012 5:52 pm ]
Post subject:  Re: Infinite volumes with LOD
David Williams wrote:
I only see one RawVolume constructor and it's this one: http://www.volumesoffun.com/polyvox/doc ... 3ad118987f

Yes that's the one. The doc says at some point "... see the other RawVolume constructor", but there is no other (similar problem in SimpleVolume).

David Williams wrote:
PolyVox has no concept of a camera position (which is relevant for LOD) and I would expect this to stay in user code.

I would too, but I would also leave the paging in user code :)

David Williams wrote:
The representation in memory should be independant from the surface extraction algorithm. Even if the whole volume was one single continous piece of data in memory (i.e. the RawVolume), you can still choose to only extract a surface for only part of it.

Maybe I got LOD a bit wrong, but in my mind it was about being able to extract, for the same world region, different resolution-meshes (not just extracting variable sized chunks at a fixed resolution). As the volume and regions are just integer-indexed data, I don't see how I could achieve this variability with them. Not to mention the fact that sometimes the same world region could require 2 versions of the volume/mesh at the same time (one low-res, one high-res being built).

(I'm not criticizing LargeVolume, just trying to make sure I understand everything).
Author:  David Williams [ Sun Jan 22, 2012 8:45 am ]
Post subject:  Re: Infinite volumes with LOD
Gnurfos wrote:
Yes that's the one. The doc says at some point "... see the other RawVolume constructor", but there is no other (similar problem in SimpleVolume).


Sorry, I'm with you now. I've fixed that in code and the online docs will be updated when we next do a release.

Gnurfos wrote:
David Williams wrote:
PolyVox has no concept of a camera position (which is relevant for LOD) and I would expect this to stay in user code.

I would too, but I would also leave the paging in user code :)


Maybe... actually I haven't used the LargeVolume class enough myself to have a strong opineon here.

Gnurfos wrote:
Maybe I got LOD a bit wrong, but in my mind it was about being able to extract, for the same world region, different resolution-meshes (not just extracting variable sized chunks at a fixed resolution). As the volume and regions are just integer-indexed data, I don't see how I could achieve this variability with them. Not to mention the fact that sometimes the same world region could require 2 versions of the volume/mesh at the same time (one low-res, one high-res being built).


You are right - PolyVox does not provide any kind of multi-resolution representation for the volumes. At the moment your two options are to create multiple volumes at different resolutions, or to create the lower resolution data on the fly as you need it.

The SmoothLODExample demonstrates the second approach. It takes the full resolution data and extracts a mesh for half of it. Then it takes the other half and copies it into another volume, while at the same time reducing it's resolution. This is done with the VolumeResampler class. It then runs the surface extractor on the new lower resolution data. Note that the handling of the different coordinate systems is a little messy and could use some polishing.

Conceptually, you could have a volume where the low resolution version always exists and is automatically syncronised with the high resolution version (I guess this is what you were looking for). Perhaps 'getVoxelAt()' would then also take a LOD parameters, or there would be some similar extension to the interface. I'm not sure whether this appraoch would be better than generating the low res data on demand... probably there are arguments in both directions.
Author:  Gnurfos [ Sun Jan 22, 2012 5:26 pm ]
Post subject:  Re: Infinite volumes with LOD
I think the way things are done in SmoothLODExample would not be suitable for a big/detailled world, because it requires having the highest-res volume pre-filled, even when actually only lower-res meshes are derived from it. This filling can be quite expensive for big regions (computationally and in memory). I can also imagine some kind of "fractal" system, where "the highest-res" has no meaning.

David Williams wrote:
Perhaps 'getVoxelAt()' would then also take a LOD parameters

The only solution I see, if Polyvox is to handle LOD, is to make it aware of world coordinates. Also, for lazy density evaluation, we would need to pass a callback that the volume would call when needed. If you allow that, here's an example of how the API could look/be used:


Code:
// World coordinates are needed
typedef Vector<3, float> WorldCoordinates;

// For lazy density evaluation
typedef boost::function<float(WorldCoordinates)> DensityFunction;
// or:
typedef boost::function<void(WorldCoordinates, VoxelType&)> FillVoxelFunction;


Code:
// Then the usage
float myDensity(WorldCoordinates); // Implemented somewhere else
WorldCoordinates lowerBound(0.0f, 0.0f, 0.0f);
WorldCoordinates upperBound(1000.0f, 1000.0f, 1000.0f);
WorldRegion world_bounds(lowerBound, upperBound);

LODVolume my_volume(my_region, &myDensity);

SurfaceMesh< PositionMaterialNormal > result_mesh;
WorldRegion extract_region(WorldCoordinates(10.0f, 10.0f, 10.0f), WorldCoordinates(20.0f, 20.0f, 20.0f));
int extract_lod = 2;
LODSurfaceExtractor my_extractor(my_volume, extract_region, extract_lod, result_mesh);
my_extractor.execute();


  • This has the advantage of relieving the user of the concern of world to voxel coordinates calculations (not that hard), but also volume edge coordinates handling (I found this a bit more troublesome)
  • There could be on-demand pre-filling of the volume, if the client needs to dissociate the work of filling the volume and that of extracting the mesh.
  • The "LOD policy" (determining the voxel resolution, from the LOD level requested) is hardcoded in the extractor or volume in this example, but could be customizable.
  • All this does not tell how boundaries between different LOD regions are handled (at interface level). I still have some ideas about that, but I don't want to write too complicated things if the beginning is not interesting (in any case, the volume and extractor interfaces would get more complicated, and not compatible with the existing ones. Maybe you don't want to go in that direction ?)

Hoping that all this is readable, and makes some sense. (anyway thanks for your answers so far).
Author:  David Williams [ Tue Jan 24, 2012 10:39 am ]
Post subject:  Re: Infinite volumes with LOD
Hi, sorry for the slow reply.

In your proposed system it seems that your volume data is really defined by your 'myDensity' function with the 'LODVolume' just providing a PolyVox compatible wrapper around this. Do I understand correctly? There are a few things to think about.

The idea of supporting WorldCoordinates does make some sense. For example, it may be possible that both integer and float coordinates could be used to access the volume, with the integer coordinates going from zero to VolumeSize and the float coordinates going from 0.0 to 1.0. OpenCL takes an approach like this to image access. However, it's not quite clear how it works with infinite volumes. Where do 0.0 and 1.0 map to, and do we then allow values outside this range? I guess this is why you are defining lowerBound and upperBound.

Also, a big part of PolyVox is that the terrain can be dynamic. If for some parts of the world only the lower resolution data is stored, then how do we modify this? I think it only makes sense to modify the highest resolution data and have the lower levels rebuilt from it.

In terms of compatibility, such a LODVolume can probably have an extended version of the Volume interface. So you could still use the existing PolyVox classes for processing the highest resolution data. Your LODSurfaceExtractor would require the extended interface and would not work with the other volumes.

Gnurfos wrote:
...I don't want to write too complicated things if the beginning is not interesting (in any case, the volume and extractor interfaces would get more complicated, and not compatible with the existing ones. Maybe you don't want to go in that direction ?


It's interesting, but not something I'm going to work on myself for a while. At the moment I'm refactoring at the lowest level (voxel types) and will build up from that. I will be polishing and refining the Volume classes but I don't expect I will add this LOD support myself. However, it is something I can keep in mind when changing the interface.
Author:  David Williams [ Tue Jan 24, 2012 1:06 pm ]
Post subject:  Re: Infinite volumes with LOD
Also came across this recently: http://www.youtube.com/watch?v=cjAywUh5m2s

Which seems pretty cool. From this guy I believe.
Author:  Gnurfos [ Tue Jan 24, 2012 8:59 pm ]
Post subject:  Re: Infinite volumes with LOD
Hi,

David Williams wrote:
In your proposed system it seems that your volume data is really defined by your 'myDensity' function with the 'LODVolume' just providing a PolyVox compatible wrapper around this. Do I understand correctly?


Yes that's it :) Except that the wrapper would not be so compatible with the rest of PolyVox, after all.

David Williams wrote:
Also, a big part of PolyVox is that the terrain can be dynamic. If for some parts of the world only the lower resolution data is stored, then how do we modify this? I think it only makes sense to modify the highest resolution data and have the lower levels rebuilt from it.


Now with this I realize that our needs differed, and this has a big impact on the underlying implementation: in my mind, the terrain would be almost mathematically defined (with the density function), and nothing would have to be stored if no mesh is needed. I thought about terrain modifications, but imagined them as just a "patch" to the density function (you just store the diffs somehow). I guess that this approach does not scale well when modifications are heavy, finally.

David Williams wrote:
I guess this is why you are defining lowerBound and upperBound.


No, actually I just used them to mimic the existing volumes, without really thinking enough :)

I think at this point (and given your plans), I should think about all this a bit more. And if I ever manage to produce something usable, I'll present you the results, of course.

Cheers !
Author:  David Williams [ Wed Jan 25, 2012 10:18 am ]
Post subject:  Re: Infinite volumes with LOD
No problem. I also think the idea of a procedural volume is interesting (for damage I was thinking of storing the diffs, like you) but it isn't something I've really persued yet. I also hadn't considered the LOD implications.

You might also want to check out the Field3D library from Sony Pictures Imageworks. They have some interesting ideas which we may be able to learn from in PolyVox. For example, they have read-only volumes (which could then be procedural) and also a mapping between voxel coordinates and world coordinates like you described. No support for infinite volumes though, and no algorithms like surface extraction.

But yes, let us know if you come up with anything...
Page 1 of 1 All times are UTC
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/