Hi everybody,
I recently started a new game project and after a long research I considered jMonkey as the best choice for me to work with. First of all thanks to everybody involved in developing it, it’s great. It simplifies many things, gives handy tools and mechanics while not limiting the programmers capabilities. I for example love the perfect integration with eclipse. Without ever hearing anything about jMonkey before it took me less than an hour to install new eclipse version, integrate jMonkey and set dependiencies, create a project and get the first moving items on the screen. It is very easy to use, very good documented and has a huge community.
Now one month later and after more interesting research on different game development technics I unfortunately miss one thing I’d really like to have in my game. As the title says I want to have a dynamic infinite procedural voxel based terrain. The jMonkey terrain is made for 80% of the programmers goals. Unfortunately it seems what I want is in these missing 20% percent. So I searched the forum and was happy to see that there are quite many other people who are looking for the same or at least partly same kind terrain. And I also found most of the projects related to this theme in the forum I think. Indeed there are a few that sound quite interesting but in most cases the last entries are more than one year old, source is not shared or down. So I decided to start a last call and ask if anyone knows a good solution or updates on older projects for that and if that is not the case I want to start a “project thread” for that. I definately want to have that so why not try to perfectly integrate it with jMonkey.
List of approaches that are interesting:
http://hub.jmonkeyengine.org/groups/terramonkey/forum/topic/procedural-terrain/?topic_page=1&num=15#post-121250
http://hub.jmonkeyengine.org/groups/free-announcements/forum/topic/simple-voxel-engine-starter-kit/#post-126819
http://code.google.com/p/bloxel/
GitHub - ahoehma/bloxel-engine
greetz Xeratos
it’s a good thing i wore my boner pants. i’m all for this, to the power of hell yeah.
if i can help in any way, please let me know. i’m not a voxel expert, but i can definitely lend a hand when it comes to different and strange approaches to designing the algorithms that build the framework ‘behind’ the voxels. i have a good number of ideas on what i’ve dubbed 'meaningful procedural generation that should, in theory ;), lead up to generating very interesting looking terrain, geo- and texture-wise.
if i could add a suggestion for an awesome read, it would be: http://http.developer.nvidia.com/GPUGems3/gpugems3_ch01.html
Hrhr yea that article crossed my way several times from independent sources ;). In fact if there is nothing like a working engine and that is how it looks like, that article is one I intended to put focus on. And all my efforts so far prepare to implement that thing in combination with an infinite procedural fractal map from jmonkey. Actually I found a few more external articles related to this topic I also consider to be very useful:
http://www.procworld.blogspot.de/
http://www.terathon.com/voxels/
http://www.cs.sunysb.edu/vislab/wordpress/projects/volume/Papers/Voxel/index.html
http://www.mpi-inf.mpg.de/~mschwarz/papers/vox-siga10.pdf
I think I will wait a few days and if it turns out that there really is nothing I will start defining the concept more specific and try to find splitable tasks and set up a good team development environment. A friend of mine just joined me on my game project and therefore we need to do it anyways.
Have you seen this one?
http://hub.jmonkeyengine.org/groups/user-code-projects/forum/topic/terrain-side-project/
It’s the most impressive one I’ve seen, thetoucher’s stuff usually is.
I did a little more research and I found some very interesting alghorithms that extend the classic marching cubes. I am trying to find the best solution or combination of these technics and the best way to integrate this into jMonkey for my goal.
For those who are interested here are some links, I hope to get some feedback what your thoughts on these are.
dual marching cubes
http://www.cs.rice.edu/~jwarren/papers/dmc.pdf
http://www.cs.berkeley.edu/~jrs/meshs08/present/Andrews.pdf
http://www.cs.uni-paderborn.de/fileadmin/Informatik/AG-Domik/teaching/lectures/ws0607_advanced_topics/downloads/mcubes.pdf
http://vis.computer.org/vis2004/dvd/vis/papers/nielson2.pdf
tetraheder
http://cs.engr.uky.edu/~cheng/PUBL/Paper_Nielson_Dua.pdf
isosurface extraction - a nice collection and overview on current marching cube technics
http://swiftcoder.wordpress.com/planets/isosurface-extraction/
I also heard about a marching cube implementation in jme2 and some tries to port it to jme3 but I couldn’t find a proper working or open version so far. Maybe someone heard about something.
Hey,
@monkey-tiger contacted me and asked me to post this for him. He has some problems with his account :
Hi,
First of all… since I’m new here, hi to all 
!
Secondly… I’m new here and new to THIS. (3D, games, even Java (have some experience in C++ though), etc.)
I’ve spend my entiiiire day reading up on voxels, marching cubes, culling, LOD, etc. I finally start to understand the different terms some more 
@xeratos : I’ve read most of the links provided (all, except the one in german… and the long research document not entirely .
What I remember from this :
Dual Marching Cubes
pro+ ”crack free” adaptive polygonization (refers to cracks when playing with LOD or something… didn’t get it all)
pro+ sparser polygonization
pro+ captures thin features and uses fewer triangles
(possibility to use Dual Dual Marching Cubes apparently (Quad or how do they call it?)… comes from one of the complicated research docs)
con- some problem with ehh… don’t remember damn… overlapping vertices or something? sorry…
Dual Marching Tetrahedra : didn’t find pros/cons, but did find a little about Marching Tetrahedra that might be interesting to note for some
con- slower than Marching Cubes (the Dual version might also be slower than the Dual MC version?)
con- creates much bigger meshes (maybe the same con for the this Dual MT compared to Dual MC ?)
Surface Nets (the isosurface extraction article said this was really old, but another article explained how it’s more interesting than MC in some cases, so here goes)
pro+ smaller meshes than Marching Cubes (not comparing to Dual M.C. here!)
pro+ faster than Marching Cubes
pro+ can be extended to create high quality meshes using more sophisticated vertex selection algorithms
con- can create non-manifold vertices (damn… didn’t have time to try and understand what this means, and why it is a con 
)
Adaptive Skeleton Climbing : another adaptive Marching Cubes algorithm (quite recent?) (I mainly copy what the article said
pro+ can directly generate multiresolution isosurfaces from volume data (useful for LOD? or I didn’t understand a thing here?)
pro+ generates low resolution isosurfaces with 4-25 times fewer triangles (good depending on what you need)
pro+ does not suffer from gap-filling problem unlike other adaptive MC algorithms (I don’t think Dual MC suffers from the gap-filling problem… not sure I remember correctly though… I remember that Dual MC DOES solve some MC problems)
Marching Cubes (good for comparison’s sake?
con- huge meshes
con- holes if using 15 cube configuration cases (normally 256, but with rotation and mirroring, 15 are enough) (can be solved by using only rotation, which gives 23 cases)
con- grid not adaptive (we’re talking about the standard MC algorithm!
con- many polygons for small meshes
Dual Manifold Contouring
pro+ it is supposed to be good (even better than Dual Marching Cubes), but can’t continue looking up info at the moment… somebody send me better info and I update this post?
con- need to use Hermite data (whatever that is) and this seems to be a problem (big difficulty? add complexity?) for many
Article about this : http://www.frankpetterson.com/publications/dualcontour/dualcontour.pdf
Useful techniques/methods/algorithms that you might want to keep in mind, for use with most of these (sorry, I really didn’t remember everything clearly… or maybe didn’t understand all that much all the time) :
- mesh smoothing algorithms
- mesh decimation algorithms
From what I’ve read, seen and understood (important detail today, Dual Marching Cubes seems good (quality and performance). Other models such as Dual Marching Tetrahedra and Adaptive Skeleton Binding might be better or otherwise good. Surface nets seem to simple (and old? according to some) but from what I’ve seen in one article, the quality was pretty good.
@xeratos said:
Hrhr yea that article crossed my way several times from independent sources . In fact if there is nothing like a working engine and that is how it looks like, that article is one I intended to put focus on. And all my efforts so far prepare to implement that thing in combination with an infinite procedural fractal map from jmonkey. Actually I found a few more external articles related to this topic I also consider to be very useful:
http://www.procworld.blogspot.de/
http://www.terathon.com/voxels/
http://www.cs.sunysb.edu/vislab/wordpress/projects/volume/Papers/Voxel/index.html
http://www.mpi-inf.mpg.de/~mschwarz/papers/vox-siga10.pdf
I think I will wait a few days and if it turns out that there really is nothing I will start defining the concept more specific and try to find splitable tasks and set up a good team development environment. A friend of mine just joined me on my game project and therefore we need to do it anyways.
The TransVoxel algorithm from terathon solves a problem in the Marching Cubes algorithm, but I think this is solved by using the Dual Marching Cubes algorithm. Not sure, and it’s a nice thing to keep in mind anyway :) It is implemented in their engine, and the source is available for download for free apparently… Can be interesting :)
@thetoucher used Marching Cubes, but no voxels if I read his post well.. Everywhere I’ve read things about both of those together, if somebody could quickly slip in a little explanation about this… ?
Some extra links that I just found and seem interesting :
http://www.oocities.org/tzukkers/isosurf/isosurfaces.html
http://www.geisswerks.com/about_terrain.html
@sillyme:
thanks for your reply.
You made a nice little overview here And your links are also interesting I didn’t know these before, but the reference to GPU Gems.
Did you also have a look on the Cubical Marching Squares? After reading a lot I consider that one as the best one. As it solves all of the issues by reducing the problem to 2d. So there is no need to do some weird combinations of the others. The only thing is the triangle count on flat geometries, I think. But should be possible to add that and for terrain not that interesting anyways.
The thing with the voxels is hard to explain as it seems that for many people voxels are completely different or they just don’t know The german wiki even marks the article as not well proved. And also I don’t want to claim that I speak the truth here but after reading a lot about this topic I for myself came to the conclusion that a voxel (“volumetric pixel” referring to wikipedia) is nothing more than an abstract data object containing 3 float values for x,y,z coordinates and some kind of information how to visualize it. This value normally comes from a provided function.
(@sillyme : this is also called hermite data or how I like to call it voxel data because hermite data requires to have a continouus function so you have a value for every x,y,z while you sometimes just provide manually set values or want to modify some and so you have no continouus function anymore. Hermite data is actually not really a problem but rather a precondition for all marching alghorithms as far as I know).
So very similar to the 2D pixel that has two values x,y and a color value. Unlike pixels there is no standard way to interpret the voxel data so the value and interpretation can of course vary. This is why there is so much discussion on that, I guess.
You can use just a colored dot or triangles or even complex meshes if you like to. The marching cube alghorithm though uses a density value for that. It then selects a “cube” which is not really a cube but a rather a set of 8 voxels that would form a cube (it actually never exists as an object) and calculates the needed faces for that “cube” depending on the density values of the voxels. But the returned mesh for one “cube” actually never is a cube. A weird constellation of several “cubes” could lead one “cube” to look like one because of density values of the neighbours though (at this point marching cube problem with sharp features comes into play). The other alghorithms also use this or small variations to visualize the given voxel data. The Marching Tetrahedra alghorithm for example uses not 8 voxels but only 4 that are needed to form a tetrahedra. Therefore implementation of that might be a little easier but a cube is a more intuitive geometry to handle I feel (we all have played with blocks and lego, hrhr). Because like all these blocky games show, for many things it is quite easy to solve them with different kind of blocks. But most of them unfortunately have this “too blocky” issue and thats what these alghorithms are for.
So here is an example on how I understand that:
Some would say these minecraft-like blocks are voxels which is kind of reasonable. But I would give the voxels a little more credit and give them an independent more abstract role. I would say the blocks are voxel-based blocks. So these games, I guess, use indeed kind of voxel data but the interpretation on the data is not as complex as the marching cubes alghorithm. They just seem to use the value to determine the type (earth, grass, wood etc.) and then create 8 vertices to form a block to represent that, I think. So you have one block per voxel whereas marching cubes takes 8 voxels (an abstract “cube”) and does some cool calculations on them to create the needed vertices, edges and triangles or rather chooses the right ones out of these lookup tables.
So while pixels have a “defined standard” value and way to interpret there is nothing like that for a voxel yet. With growing interest in this technique there might be one one day but at the moment everybody can more or less define his own voxels with custom values and interpretation for representing them, I think. So @thetoucher I think also uses voxels but as he said he doesn’t know much about them just didn’t realize it. But marching cubes alghorithm takes voxel data as input so if he uses that he must use some kind of voxels
Again these are just my ideas on this I don’t have proves for any of this. My sources are more or less the links mentioned above, wikipedia and some side links from the links above compared with what I know about computer science and graphics due to my studies at university. I hope I could clear up some things at least.
Sorry but maybe I don’t understand you correctly. But as I see it you want to build a minecraft like voxel engine? If so you might get problems when using some of the described algorithms. This is because I assume you want to have different kinds of blocks? If yes you can’t just merge two faces of different blocks together because then you wouldn’t have correct texture coordinates for them - these algorithms only make sense when you want to merge two equal blocks - but I don’t know if you can use them that selectivly. And even if - in my experience it is a nice optimization but the block tesselated surface shouldn’t be a problem for modern graphic cards even without removing unneccessary vertices.
If you don’t believe me - my game just tesselates the voxels without further optimization: http://www.youtube.com/watch?v=KeRoXpsuebQ
I know there are still some things I have to think about how to realize them. The thing is I want to have an editable terrain in first place or even objects. But you are right I want different kind of “blocks” in a way and that is a problem with the alghoritms(I am not yet really sure in what ways as I am still learning JME capabilities and how everything works together). What I definately dont want is one of these blocky worlds which really s**k (nothing gainst your project surely hard work and quite interesting). No matter what you do they look like 1980s, early 90s-just 3d, I think. Unless you make them really small but than your fps go to -infinity ;). So I want to get rid of the blocks while keeping the functionality and yet let it look better. It does not have to be realistic or nature like but at least like … well not pixels or in this case “voxels” like some would say as mentioned in my previous post. This is a game that comes quite close to that:
http://www.sauropodstudio.com/
I have some ideas how to make that happen. For example:
I think about making an interface for or class of objects that are editable and implement CubicalMarchingSquares or maybe a small variation. Of course the object may only have one material but I can have several materials and in each of them I can implement CMS in Shader, afaik. And also the decision whether a face is drawn or not isnt actually dependant from the material or texture but the density value of the voxel data given to CMS. so I can still give it the border vertices to another object to take into account when calculating.And these “blocks” can be more like the data structure underneath.So a tree can be like a hybrid of voxel data for the trunk and normal polygon models for branches and details combined in a node. And a goldmine has its own mesh with material gold interface editable that replaces a part of the terrain voxel data. and calculates independent. So I have different independent CMS objects that work on the same, partly or complete independent voxel data. How much I can let the GPU calculate is still a question I can not fully answer, not only because jme does not have any shader support for editing triangle list like geometry or tesselation shaders. Maybe you are right and I have to stick to CPU and multithreading and can only do a few calculations on GPU, if at all. Or implement support on my own 
I actually found a patch file that should do that but I didnt try it out so far and I dont know how to apply the patch file. Maybe I take a further look on that within time:
http://hub.jmonkeyengine.org/groups/contribution-depot-jme3/forum/topic/support-for-geometry-and-tesselation-shaders-diff/?topic_page=1&num=15
@entrusc
Anyways you also have a nice little project there and definately have more expierence in JME than me, I guess. Always nice to get fresh ideas and things that you have to consider. Thank you for that.
It has nothing to do with jme, its a simple geometric problem.
I’m not too sure of what you’re looking for, but if you’re talking about infinite, dynamic, “smooth” (unlike cubes in Minecraft) terrain, 3D Perlin noise + marching cubes is working for me so far. I think I used a modified version of this for the marching cubes.
@normen
Sorry, I am not quite sure what you mean. What exactly do you mean by “it”. Do you mean it is a problem like entrusc said or that it is only dependent on how you implement the alghorithms in the logic and organize your data.
@seann999
Thanks. I also made first approaches to this topic with that project. Found it some time ago. It is a good thing to see how the alghorithm works itself. Unfortunately it is for jME2 and I wasnt able to make it run, yet. But I decided to use the CubicalMarchingSquare alghorithm anyways because it has fewer issues with some special voxel arrangement and it also simplifies the problem to 2d which is kind of nice, I think. I have also heard about that perlin noise but some other problems have to be solved first so I enqueued it.
btw: I decided to not make it really infinite anymore because it makes things more complicated while not giving any real advantages that cannot be shadowed through some smart sequences and multithreading and also my desired game goal supports that very good. I already have solutions in mind for that.
@xeratos said:
Sorry, I am not quite sure what you mean.
This:
@xeratos said:
But you are right I want different kind of "blocks" in a way and that is a problem with the alghoritms(I am not yet really sure in what ways as I am still learning JME capabilities and how everything works together).
@normen
Ok, thanks for clearing that up.
I assumed that but wasn’t sure. So I really just need a good data structure, multithreading and gpu usage and flexible scenegraph structure, of course. This should work, I guess. Will discuss that with my teammate soon.
@xeratos said:
@normen
:D Ok, thanks for clearing that up.
I assumed that but wasn't sure. So I really just need a good data structure, multithreading and gpu usage and flexible scenegraph structure, of course. This should work, I guess. Will discuss that with my teammate soon.
Don't discuss it... people LOVE surprises!
Yea, for sure. It is nothing more fun than programming something in weeks and recognize you cannot achieve what you wanted.