Voxel Terrain/Environment

[zauberparacelsus]

One nice (but advanced) feature to have would be support for voxel-based terrain, environments, or levels. There are quite a few algorithms available for converting voxels to mesh, some of which support paging the terrain in chunks (like minecraft), for generating LOD meshes, or for adaptive generation (creating optimized meshes).

@nickgildea has a blog detailing his own work on writing a dual-contouring algorithm with LOD support, at http://ngildea.blogspot.com/

@Lin20 has a repo on github containing example/testing code for several different voxel-to-mesh algorithms, though they are unoptimized and written in C# - https://github.com/Lin20/isosurface

There is also a reddit devoted to game development with voxels, which likely has useful information: https://www.reddit.com/r/VoxelGameDev/

And lastly, there's a blog post that contains links to research papers for various voxel-to-mesh algorithms - https://swiftcoder.wordpress.com/planets/isosurface-extraction/

[zauberparacelsus]

I forgot to note, that Blender does have some mesh-to-voxel-to-mesh code, in the form of the Remesh modifier, which converts a mesh to voxels and then generates a new mesh from those voxels. Not quite sure which algorithms are used, though.

[zauberparacelsus]

Also worth mentioning are Sparse Voxel Octrees:

https://research.nvidia.com/publication/efficient-sparse-voxel-octrees

[adriansnetlis]

Voxel engine would be great addition.:)

[JeannotLandry]

I agree, a quick way to make terrain that auto generates LODs (dynamic LODs) would be great! Also the ability to add echosystem (vegetation) that also carries LODs. It would also be cool to have vegetation affected by wind effects as well as collisions with mesh (like a character walking through tall grass and the grass either split or flatten).

[adriansnetlis]

For grass a single-sphere ground-constrained collision system would be cool. It'd be very performance efficient, but would loook amazingly realistic. I can try helping to set such a thing up, but no promises as I've never done it before.

[zauberparacelsus]

Off the top of my head, the only algorithms that include LOD are Adaptive Skeleton Climbing and Transvoxel. Several of the algorithms mentioned in the last link of the first post generate "adaptive geometry", meaning they'll simplify the mesh into a more optimized form, reducing the need for LOD somewhat (though not enough for lower-end systems).

[adriansnetlis]

For basic terrain a good idea could be tesselation. Using 16x16(for example) base planes and tesselating them as player approaches up to some limit(e.g. 1024x1024, but it must be user defined). This works as a great LOD, but doesn't have any popping or such, looks smooth and allows almost infinite detail:)

[zauberparacelsus]

@adriansnetlis Interesting. And could that be extrapolated from a simple minecraft-style terrain?

[cuechan]

[...] Im sorry, i probably forgot to lock my phone before putting it back into my pocket. Just ignore this.

[zauberparacelsus]

@cuechan I think your blackberry mangled your reply.

[zauberparacelsus]

I've heard of butt dialing. Never heard of butt emailing though, lol.

[HeadClot]

I really think we should get a heightmap based terrain system with LODs in before we even consider Voxels for terrain. While I have a great interest in Voxels you got to learn to walk before you can run.

[zauberparacelsus]

As a note, generating the mesh from the voxel data may be much slower on HTML5. However, if it were implemented in a way that can take advantage of GPU acceleration, then it may be workable.

OpenCL is an obvious choice for GPU acceleration, since it will work on just about any GPU. For HTML5 though, there is a web version of it, called WebCL: https://www.khronos.org/webcl/

[zauberparacelsus]

The VolumeComponent from Ogre3D may be worth researching as a basis for voxel terrain in armory. It uses the Dual Marching Cubes algorithm. In addition to supporting distance LOD and sharp features, it can also produce efficient geometry:

Lower left is standard marching cubes, lower right is dual-contouring, and upper right is dual marching cubes.

[jreach-dev]

This has been a passion of mine for a while. The Ogre3D dual marching cubes is only a partial implementation. It does not retain sharp edges.

I cannot count the number of times I read the whitepaper that those figures come from, but I cannot find a way to efficiently compute least squares optimization problems in real time on large data sets to accomplish this.

Recently, and the reason I found Armory, I found BMesh in blender while searching for a better solution to real-time terrain editing. That meshing kernel is extremely powerful and more useful for real-time terrain edits from my perspective. At least that is my theory. I want to test it out to see if it performs well. Unfortunately I cannot think of a way to use that code without breaking licensing compatibility.

Anyhow there is one other solution out there that I really like for real time world editing. http://sauerbraten.org/

That uses a very clever combination of strategies and I am sure could be adapted for smooth voxel terrains. It is also zlib.

[zauberparacelsus]

I forgot to post links to the stuff for Dual Marching Cubes. Sad to hear that Ogre3D's volumecomponent doesn't support sharp features, though perhaps its LOD management could be adapted?

Anyways, I did find another implementation of DMC, though I don't know how complete/suitable it is: https://github.com/dominikwodniok/dualmc

And here's a document from volume-gfx.com - https://www.volume-gfx.com/volume-rendering/dual-marching-cubes/

And the original paper: https://www.cs.rice.edu/~jwarren/papers/dmc.pdf

[zauberparacelsus]

PS: I looked at blender's BMesh system, and unfortunately it is licensed GPL like the rest of blender, so it couldn't be integrated into armory or other projects without the whole project being re-licensed as GPL.

[jreach-dev]

Ogre3D Dual Marching cubes does a lot of things right. I contacted the author and he said it is possible to finish the sharp feature detection. Would need someone who understands least squares optimization math to finish that work though.

Thanks for the links. I will definitely check out the github link you pointed out.

I heard some of the Blender components are LGPL. If BMesh is completely GPL then I will continue with my plan to use http://sauerbraten.org/ strategy for adaptive voxel terrain. I have done some initial prototyping and this solution is extremely powerful.

Here is a closeup on that lower left corner. This is a 10 level octree. The 21 level variant became unstable with single precision floats!

With this strategy you can have adaptivity, sharp features, smooth features, high resolution, effecient storage, efficient access, dynamic modification, etc... I will have to learn Haxe to port this to Armory3D but it doesn't use anything special other than a hashmap.

[luboslenco]

Continuing at the voxel_world module: https://github.com/armory3d/voxel_world/issues/6

[zauberparacelsus]

@ubaldy Yeah, bmesh is not one of the LGPL ones: https://github.com/dfelinto/blender/blob/master/source/blender/bmesh/bmesh.h

As for octree depth, my plan was that if i ever got to the point of coding one, I would just break the terrain up into 32x32x32 or 64x64x64 chunks (depending on which had the best performance characteristics) and have each chunk be a separate octree. Don't know how well that would work compared to the world as one big octree though (with the world potentially being dozens of miles across).

Maybe one big octree would be better for a small world, while subdividing into chunks would be better for a massive open world. Or maybe it doesn't matter. I just remembered that OpenVDB has some custom structures for storing sparse voxel data, including methods for accelerating access (including a way to directly address a specific node without running through the upper levels).

[jreach-dev]

@zauberparacelsus Thanks for confirming, Octree it is!

I have experience making 'infinite' terrains with marching cubes. Instead of the chunks being marching cubes I can make them octrees. Using the Cube2 strategy it will be capable of sharp and smooth features and will be much more resource friendly than marching cubes for large terrains.

I did look into OpenVDB and that could easily be used for the underlying data structure. I am currently using a linear octree in a hash map as that is significantly more simple for prototyping and still has O(1) access times on the nodes (you don't need to traverse the tree).

http://www.csee.usf.edu/~tuy/Literature/QTree-Represent-CACM82.pdf https://geidav.wordpress.com/2014/08/18/advanced-octrees-2-node-representations/ https://github.com/greg7mdp/sparsepp

I just added the feature to 'carve' various sized cubes out of the octree. I will add the screenshot later when I get the chance. Would you be interested in helping design the component?

[zauberparacelsus]

I can offer input and testing, though I lack the necessary math background to do the coding.

I did start work a couple years back on making a chunked voxel mesher, and for storage I wrote an octree from scratch. Didn't really know what I was doing with either, though. The voxel mesher was sorta similar to naive surface nets, but I didn't know how to calculate normals, and so all of the faces were flat-shaded and would randomly be back-facing, and I had trouble with blockiness. The octree had O(n) access times, though I did have one or two custom node types I used to reduce memory usage, and I also wrote a custom serializer that could store the octree in a compact binary form.

Anyways, as far as going with a "chunked" design (or rather, a grid of smaller octrees instead of one big octree) the advantages would presumably be:

• Making it easier serialize and save changes to the world
• When the world is edited, it may presumably make rebuilds of the terrain mesh faster.
• Avoid having to keep the entire world in memory (important for massive worlds)
• Avoid having to generate the entire world ahead of time (useful for procedural worlds)
• Individual chunks can be used to manage extra data, such as entities or game objects

Though, now it occurs to me that most of those above problems could be avoided with an O(1) access time like you described, and if the octree can be partially loaded, and if mesh rebuilds are done at a certain node level. Chunks would still be useful though for storing data separate from the terrain, such as entities and game objects.

[jreach-dev]

Sounds good. Let us move further discussions to: armory3d/voxel_world#6