Hi,


(TLDR)
I have a somewhat raw, badly documented, irritatingly generic, partially implemented, and hacked implementation of the TVA algorithm by Eric Lengyel (http://www.terathon.com/voxels/) (tyvm). Not for the faint of heart, the minimally documented, template-heavy C++ is quite harsh .

I've got a partially implemented/hacked/bugged demo, in Ogre. It actually misuses TVA to generate a sphere on the fly, but top down (lowest LOD first), on the fly. And it doesn't do it too well (yet). I have some old videos of what I mean http://www.youtube.com/watch?v=4wVx2wTDP7A and http://www.youtube.com/watch?v=FpmRKo54-yU, both without transvoxel, which I intend to rectify.

The library is super-generic with some specialized adapters for polyvox.

There are *many* outstanding issues, some I've already solved and am porting from an un-refactored version and some I could use some help with, and also and particularly with my odd top-down approach, which adds a host of problems, but demonstrates a possible way to perhaps obtain absolutely huge highly detailed procedural volumes. For example two problems are shading (it's gotta be somewhat procedural probably), and invalid LOD generation (top down approach probably shouldn't just sample a density field that has a higher frequency then voxels, it tends to create lots of insane popping).

Reading the README is a must.

The library requires boost.

All my code is under zlib, except Eric's data file, which is under a license he wrote. The license actually appears to be equivalent to zlib, but when I contacted him about me converting it to zlib he requested I leave it as is.


https://gitorious.org/polyvox-tva/polyvox-tva

^^ repo

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

Sounds very interesting! I know a lot of people have been interested in the Transvoxel algorithm in the past.

Can you elaborate on the PolyVox integration? Are you storing your data in one of the PolyVox volumes, for example? Or when you say it is generating a shpere on the fly do you mean it's not actually using volume data yet? Does it generate a PolyVox mesh?

I'd also be interested on the kinds of voxels it will work with. Obviously it uses density values, but it's never been clear to me if/how materials are handled. So if you have a 'rock' voxel next to a 'soil' voxel then what do the lower LOD levels do?

Regarding the licensing, Eric did actually post a response in this thread. Clearly his intentions are good, but I'm not sure how much weight a forum post carries from a legal standpoint. It will need some consideration before the tables can be included in PolyVox.

Well, I use a deck-row-cell iterater concept, for which I provided a polyvox implementation; it takes a polyvox RawVolume atm, because that is what I am using. For the nature of my implementation this was best, and furthermore I might have had the impression at one time that copying to a RawVolume might be worth it in any case for cache coherency and repeated calls to getVoxelAt() (not a tested theory). However, I should probably genericize this to any polyvox volume (easily done).


Well I basically fill up 17^3 chunks on the fly from the spherical density field, and then for each level I split that bounding box into 8 smaller nodes and fill those up. This is why I use a raw volume; they are all local to their chunk. So I am not using LargeVolume data, but I am using volume data in a way.


Actually no. The extractor itself uses the OutputIterator concept; it takes a vertex_output_iterator and index_output_iterator, which I found simplest to just dump into a vector. It can be just as easy to put them in the SurfaceMesh class or w/e you want. This is why I like output iterators; they allow for many more paradigms.


Well for the videos I posted above, it was an initial version of the TVA marching cubes, just no transitions. So I initially used my own voxel class, and found it easier to use floats (on the fly generation has less of an issue with memory). For the current demo, I use the MaterialDensityPair, which I suspect is the cause of a slightly noticable normal artifact (just run the demo to see) due to the integrals, but I am not sure. I will switch to floats eventually I think. I am trying to use polyvox as much as possible in the demo so I used your voxel class. As for materials, I actually leave material selection up to a traits function, which gets lots of contextual information, and decides the material. I myself am not clear on what the paper means in its description of material selection, so I actually just use the interpolation factor to choose between the two corners' materials (you probably understand that having implemented MC). Also the paper insists on duplicating vertices that have conflicting materials, which I don't do either yet, until I am clear on how to proceed.

As for your direct question ("''rock' voxel next to a 'soil'"), since I don't actually generate LOD from the bottom up, I haven't yet had to solve that problem (I don't have a LOD generator). The paper discusses that under Material Specification (Figure 5.7), which is part of what I didn't understand yet, above. The extractors are more like primitives, they just do two things: extract the volume (surface_extractor), and extract given transition faces (transition extractor). Putting it all together is another hard design problem, aside from these issues, and the length of the demo (together with having an octree lib) proves it.





This is the text of the license in the tables:


Taking this apart:


Great.

This is already done by virtue of keeping this very text inside the data file, and is the same terms as zlib. To quote from zlib: "This notice may not be removed or altered from any source distribution".



And to quote from zlib license: "you must not claim that you wrote the original software".

This is why I scratched my head and thought of just converting this to zlib ... it is a subset of zlib it seems to me. However, in email conversations Eric didn't want me to change the license text so I obliged.

If it is a still a problem, I can write to him again and ask.

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

I assume you are aware that the RawVolume::Sampler is also an iterator-type concept? There has been talk about reworking these samplers to make them more STL compatible. At the moment I'm refactoring PolyVox from the bottom up; i.e. I'm refactoring the voxel types at the moment and will look at the Volume/Sampler classes next. So I think it will happen in the next few months.



Interesting... maybe we should also consider making the SurfaceMesh class more STL compatible as well. Well, it's something to keep in mind.



There is no requirement that your code has to handle materials... if it just works on densities I'm sure it will still be useful to people. I'm currently removing the whole 'getMaterial()', 'getDensity()', etc concepts from the voxel classes so that primitive types can be used in the volume and can represent whatever you like.



It's not quite the same as the zlib, simply because it's phrased differently. People who want to use the code now have to read two licenses. Or maybe they don't... Eric said in the forum thread that he is happy for us to include the attribution just in PolyVox and that it needn't bother end users. But do the end users agree with this? Do their lawyers agree with this, and in that case do they need to see the forum message? And what if people want to fork the PolyVox code, or host it somewhere which only allows open source licenses?

I'm being rather pedantic here, but the point is that it creates a little uncertainty. Everyone knows licenses like zlib and GPL because they are widely used and approved by the Open Source Initiative. If we have to describe PolyVox as 'zlib, with exceptions' then people are not immediately sure if they can use it without going through the kind of discussion we have here.



Fortunately I think this issue is actually quite easy to work around. One option would be to simply include a dummy header in the place of the Transvoxel tables, and provide a comment and #error directive to explain to users that they can download the correct file from Eric's website if they agree to the license. People will only see this if they actually include the header for your transvoxel implementation, so it shouldn't bother other users.

Added a bottom-up approach demo (DemoB). The highest resolution volume is also a sphere (simply because it is easy to do without a noise library), and it is unshaded. This demo follows more closely to the paper's intended use.

I have a ton of documentation discussing design choices, some of which may be applicable to voxels in general. It currently resides on my personal wiki. Shall I move it to the project wiki?

I also have a bunch of unit tests and they seemed to pass lots of random volumes, so I am beginning to think that I can approach beta-state.

I also made a primitive volume serializer so that if a particular volume fails, it can be reported with the volume that causes it, and I can reproduce it.

Also it would be nice if we had a collection of various sample volumes that could be used for testing and demoing.

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

Ok, interesting stuff. I've downloaded your code and skimmed over it, but I didn't compile (I'm on Windows). Here are a few things I thought about in no particular order:

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? The code seems quite large and very generic, so perhaps the second option is better?

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.

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?

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?

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.



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.



Yeah, for terrain there's not much except using Perlin noise. If you want real objects though there are a number of interesting CT scans floating around the internet. Animals, household objects, etc. Perhaps we should also keep a list of these on the wiki?

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.


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.


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).


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.


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:



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:



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.


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.



https://github.com/realazthat/polyvox-tva/wiki

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

Right, sorry for the slow reply. There's lots to say so I needed a proper chance to write it all down...



There's a number of considerations here. From my point of view the main concern is that I need to understand and maintain any code which gets added to PolyVox. There may be some degree of user support required but in general I would leave that to you. If we decide we need PolyVox on some new platform such as iPhone/Android then I need to understand the code well enough to port it. Also, if I make some sweeping change (for example removing the Density and Material classes as I'm doing now) then I need to understand what impact this has on all parts of the code.

From your point of view you need to think about whether you want to be tied to PolyVox for input data. With your generic interface I assume your users could currently use Field3D, Boost GIL, or perhaps even some mathematical function representing the density field. Do you want to keep this flexibility? Also, what will you do with your scene management code? Will that stay in your own lbrary, and if so is this convienient for your users? Lastly, do you mind changing things like naming conventions to match the PolyVox style?

Overall, I think the best approach is to add a new library to PolyVox. This would sit alongside PolyVoxCore and PolyVoxUtil and be called something like PolyVoxTVA. Initially it would just contain the adapters needed to work with your library, and it would have a dependency on your library. Over time we could move the extractors into PolyVoxTVA, and then perhaps other parts of the system as well. At that point we can just work it out as we go along, deciding what is most appropriate.

Because it is a seperate library it could have some extra dependancies (though I don't know if Ogre is too heavy?), and CMake scripts would just disable building PolyVoxTVA if the dependancies were not met. In this way it should have minimal impact on the existing code in PolyVox.

I'm also in favour of this gradual approach because it requires less upfront work from our side. Things are pretty busy with Voxeliens and just adding the adapters initially should be quicker and safer than a full merge of your work.



In some cases, yes. I do intend to rework some of the Volume and Sampler code to make it more STL compatible, and being able to use (e.g) for-each loops is certainly useful. I won't be aiming to make proper STL containers out of them though as I belive they are more specific than that. I would also like to allow custom memory allocators though I don't know if this will follow the STL approach. For the surface extractors I don't currently plan to accept anything other than Volumes or output anything other than meshes, though there could be use cases for this (e.g. writing directly to the users chosen mesh format).

Basically I have to strike a balance between spending time making the code generic (which is hard!) and working on other features. Both are desirable but time is limited, so the results are generally driven by my own needs as well as what features people are asking for most frequently.



I'm not completely against a header-only dependancy on Boost, though ideally the Boost headers should then be shipped with PolyVox. I have also been thinking about other header only dependancies such as a compression library. If we did ship the Boost headers with PolyVox then (as with the TVA tables) we need to consider that the license is technically different. Perhaps we just add a dependancies folder with a clear notice explaining that these files are not part of PolyVox. Also, if PolyVox ships with and uses one version of Boost and a users application requires a differnt version of Boost then are there potential incompatibilities? Anyway, if we go for a PolyVoxTVA library as described above then you can have a dependncy on Boost if you wish.



This is indeed useful, though I'd like to come back to it in the future when I look at STL compatibility for the volumes and samplers. I did add a class to PolyVox called IteratorController and this serves a similar purpose (iterating over a region) though it was just a quick test and is not a final solution. Something STL/foreach compatible is better here.



I agree. Extra operations on Regions are desirable although I need to think about which ones should be members and which ones should be free functions. I've been wanting to expand the Region class for a while, actually.



Not so sure about these... I did want a way of specifying direction (Positive X, Negative Y, etc) but I think a simple enum will work for most purposes. I don't think we need the cube/face/edge stuff in PolyVox but of course you can still use it in TVA.



I'll have to come back to that as I've written enough for this post. In general it looks good (particualrly the material stuff) and I think parts of it can be moved/copied to the PolyVox Wiki.

One last point to discuss is timescales. Actually the time required for integration (and to properly think things through) is my biggest sticking point just because we're so busy. We're currently expecting to release Voxeliens by the end of April, though there will be followup work with marketing, bringing to more distribution systems, etc. I intend to do a new release of PolyVox once the voxel-type refactoring is done, and I think we're hoping to have a better release system (with version numbers, GIT branches, changelogs) for future releases as well. I'll have to check with Matt about this.

Probably we can start integrating your work after the PolyVox release in about two months, but how does that fit in with your own plans? Do you have many more features, changes, etc which you want to make? You can have longer of course, that doesn't matter to us.

I've got lots of documentation that needs to be ported from an unrefactored version. The documentation is quite dense; it does a line-by-line explanation of the code.


It should be easily adaptable, with little change.


Yes I want to keep this flexibility, but I imagine my primary users would be PolyVox users, so I think it is important to maintain the PolyVox adaptors. The adaptors are the high-level method, which would tie users to PolyVox input data, and you are right, it can be adapted to other types of input data. The mathematical density field is basically exactly what I am doing (using a noise lib as the function). As a side point, such a function can be expensive to compute, and the extractor will evaluate the function several times at the same location, so I have so far assumed that it is actually better to just copy them into a RawVolume (or similar, array based volume), and extract from there. But the point being, I want to focus on using PolyVox with TVA, and once PolyVox users understand how to use the PolyVox adaptors, they can decide to specialize it to whatever they want.


I want to supply the tools for scene management (octree, cube lib, utilities), and demo examples. I think it is too specialized and coupled with the 3d engine to make entirely generic, but a well-done demo using the utilities gives a good starting point. Along the way of creating the demo, I put aside lots of necessary utilities that most implementors will need.


Sounds good.


Right, Ogre is required for the demos, but not required for the library. I just used Ogre because that is what I am familiar with. But yes, the cmake scripts can do sensible defaults of what to build. The library itself is header only, so no fancy CMake scripts required (other then an install target perhaps).


Sure, no rush.



I can try and make more generic versions of things, and add in some missing stl-style typedefs (value_type is something I wish PolyVox had more of for example). However this would probably be breaking, so you would have to review, copy what you like, perhaps on a "version" change.





Yes I meant for PolyVoxTVA, not trying to shove boost into PolyVox if you don't want it .



Try doing this with enums:

Doing that with enums drove me absolutely nuts .


No rush. I am looking forward to your Voxeliens release .


Yes. PolyVoxTVA is no where near as stable and mature as PolyVox itself. I do have additional features I want to implement, such as skinny-triangle-elimination, geomorphing, and other features in the paper, and also provide some good base shaders for the demos as a starting point for others.

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

TLDR sorry

Transvoxel in PolyVox I want!