David Williams wrote:
1) Just so we are clear, are you hoping to see this code become part of PolyVox? Or are you just looking to provide compatibility with PolyVox so that we have access to a TVA implementation and you have access to a volume library?
Which ever you prefer. I was thinking that perhaps some of the genericity can be adopted in the future by PolyVox, as there was much discussion about this in other threads, but keeping the libs separate enforces decoupling anyway. What I would eventually want is to have it understood, distributed, and supported together with PolyVox.
The code seems quite large and very generic, so perhaps the second option is better?
Most of the TVA code actually lies in surface_extractor and tva_extractor classes, and additionally in common.h/inl and data.h/inl. Most of the other things are supporting utilities and the PolyVox adaptor + utilities. cube/face/edge/corner/direction reasoning lib is used by the TVA implementation. However, octree lib, is used for scene management in the demo, and I assume all users of TVA would need an octree.
2) You are making heavy use of Boost and also Ogre (though i guess Ogre is just for the demos). Currently in PolyVox we only use Boost to emulate C++11 features, which is basically shared_ptr and function. Longer term the need for Boost will probably decrease until it can be removed. Are there any features of Boost which you are actually depending on? Obviously this only matters if your code is to actually become part of PolyVox.
So, most of the use of boost in TVA itself can be replaced.
In the demo, there are some more important uses of boost, such as multi-index containers. This can be redone ofc with separate containers, at the cost of verbosity. There are some other nifty uses of boost though, that would be annoying to reproduce, such as iterator_range (I forget where I use it), make_function_output_iterator() etc. IMHO, header-only boost is a reasonable dependency, and is useful, not just for things that made it into C++11. Plus, the way I see it, the demo has to rely on a rendering engine anyhow (and official Ogre builds even rely on boost), so relying on boost is fine. If you want to strip the regular library of boost, that is feasible, but we'd be writing lots of iterator interface code (boost has iterator_facade, which simplifies writing iterators, and I provide cell-iterarors for polyvox this way).
3) What is the simplest possible interface to allow a user to make use of TVA? For example, with our Marching Cubes surface extractor the user specifies only a Volume and a Region, and receives a mesh in return. This is far from being a complete terrain engine, but it does provides the user with the core feature they need. How does it work in TVA? Can you allow the user to specify just a Volume, Region, and LOD level? Or do you need more 'global' concepts such as a camera position?
Yes, you hit it the nail on the head. The core stuff is tva::surface_extractor and tva::transition_extractor. I once wrote a non-generic adapter of surface_extractor that matched SurfaceExtractor's interface and dumped vertices into SurfaceMesh; it is trivial to do. I intend to redo this for benchmarking and comparison, perhaps in DemoC. The transition_extractor is similar to the surface_extractor, except that it extracts the face-patches of the region. So for each "chunk" you'd run the surface_extractor once, and the transition_extractor 3 times, one for each internal (or only external) face (you only need 3 faces, see paper for detail, Figure 4.13).
However, scene management becomes a lot more complicated. You don't supply an LOD level at all. Instead you supply a deck-row-cell-iterator interface, (which I can make to skip voxels based on LOD, yes). But the problem is that skipping voxels is not always the correct LOD. TVA assumes that skipping voxels is the correct LOD for densities, but not for materials (Figure 5.7). Which means that you should probably keep multiple volumes in a hierarchy, and never skip voxels when marching (just use the correct sized volume). Furthermore, TVA allows for "Surface Shifting" (4.2.1 Surface Shifting) prevention algorithm, which basically looks one LOD higher to better interpolate the vertices (Figure 4.2, Figure 4.3), and I allow for this as well (I abstracted the interpolation function to the "traits" class, so you can interpolate w/e way you want, and if you have access to higher resolution data, then you can do the Surface Shifting section).
And then you might want to do "vertex adjustment" of the transition cells (see Figure 4.12), which does better shading. This moves transition patch vertices back a half cell or so, which means that you must move some vertices in the volume back from the edge of the region together with the transition vertices. To do this efficiently, it is probably best to separately extract the outer layer of the volume.
And then you realize that all this is just one node in an octree, and you must be able to turn transition patches on and off, and move the edge vertices ("vertex adjustment") as well. This means that you must each frame determine which nodes should be visible, and tell each visible node what level of detail its adjacent neighbors are. This is why the demo is long and complicated. Scene management is complicated, but the primitives are easy to grasp.
4) As far as I can tell, if we actually wanted to make your TVA implementation part of PolyVox then the core parts we would need are the surface_extractor and transition_extractor. Or do these depend on many other files?
Right. You would need only the include header directory, except perhaps the tree subdirectory (octree).
A lot of the supporting files actually contain useful PolyVox utilities. For example, test_utils.h has a lot of test functions to test for some obvious errors, for example that vertices are only generated in the specified region, if normals match the trimesh normal generation algorithm (which is how I generate normals), if two vertices are at the same location (probably the vertices should then be reused/combined), if vertices at the same location have different normals or if volumes are equal. Another useful utility is region_iterator which allows something like this:
Region region = ...;
BOOST_FOREACH(const Vector3DInt32& position, make_region_iterator_range(region))
Other very useful PolyVox utilities can be found in tva/polyvox_utils.h. I am not sure if I just missed similar utilities that might already exist in PolyVox, but here are some useful things it contians:
Vector3DInt32 region_size(const Region& r);
///Size in a single dimension
int32_t region_size(const Region& r, const cube::direction_t& direction);
///Add a layer to the region
Region layered(const Region& region, const Vector3DInt32& scale);
///Remove a layer from the region
Region shrunk(const Region& region, const Vector3DInt32& scale);
bool regions_equal(const Region& lhs, const Region& rhs);
bool operator==(const Region& lhs, const Region& rhs);
///Is a position near the edge of a region?
template<typename Vector3DFloat, typename CellSize>
bool is_near_edge(const Vector3DFloat& position,
const PolyVox::Region& region,
const CellSize& cell_size);
///Obtain a region containing the of the surface of face
Region face_region(const Region& region, const cube::face_t& face);
///Get a vector that has the minimum of all three components
Vector3DInt32 minimized_vector(const Vector3DInt32& lhs, const Vector3DInt32& rhs);
///Get a vector that has the maximum of all three components
Vector3DInt32 maximized_vector(const Vector3DInt32& lhs, const Vector3DInt32& rhs);
///A new region containing both regions
Region merged_region(const Region& lhs, const Region& rhs);
///Extrude a region's face by a specified amount
Region extended_region(const Region& region, const cube::face_t& face, int32_t amount);
Vector3DType negated(const Vector3DType& v);
Vector3DFloat normalized(const Vector3DFloat& v);
Vector3DInt32 get_corner(const Region& region,
const cube::corner_t& corner);
I think these functions would make a great addition to PolyVox.
The cube library too is incredibly useful for reasoning about faces/corners/edges/directions. It takes boring, error-prone, very repetitive math and makes it intuitive and easy-to-read. Before using the cube lib and these utilities, I was rewriting lots of errorful hard-to-read pieces of code.
5) On the other hand, if you/we wanted to keep your library seperate then we just need the adapters (polyvox_volume_t and OutputIterator stuff). These could be part of your library or part of PolyVox, and I'm not sure which option would be best. If they were part of PolyVox then we would want to put them in a seperate module because of the dependany on your library. This is something I've been considering for integration with other libraries as well, such as OpenMesh.
So overall, I think that some small PolyVox-specific (utilities) things should be integrated, and perhaps the cube library as well. The main library uses boost somewhat, so best to keep it separate. And the polyvox specializations should should stay separate too, since they will only be useful for this library which will only be distributed side-by-side.
I'd be interested to see it. Perhaps you can stick it somewhere publically viewable first (does Gitorious have a Wiki... I thought it did but don't see it now). Then the bits that are relevant can get moved across, or possibly all of it depending on what kind of integration we end up with.https://github.com/realazthat/polyvox-tva/wiki