Hello, my name is John Mecham and this summer I’ll be working on making a voxel terrain system for use in jMonkeyEngine. I hope to make this system light weight and easy to use for jME users.
I’ll be keeping a technical blog which will contain explanations and tutorials on what I’m making.
The blog can be found here: http://voxiworld.blogspot.com/
There will a lot of tough decisions to make this summer about various aspects of this project. So I hope to get your feedback on which choices you’d like to see me make. You can expect (at least) bi-weekly updates starting the week of May, 19th.
Subscribed! What decisions need to be made? The sooner you get them out in the open the better. Doesn’t matter if they’re not that clearly defined yet.
Hey fellow monkey,
nice thing another good looking start on a Voxel Engine for jME. Actually I am working on one, too, which should also be available for other libraries but my main focus lies on jME. I just took a look at your blog and saw you also consider Cubical Marching Squares which is interesting because nearly no one has heard of that and actually I decided to go with that one.
Maybe if you are interested we can talk about all that stuff. If so let me know or just come to the #jmonkeyengine irc channel I am most likely to be found there.
Hello,
One of the first decisions we’ll have to make is choosing an isosurface extraction method. These carry a lot of subtle implications. Right now my primary concern is compatibility with multimaterials.
Usually we store voxel data in a 3D grid and each voxel has a type (e.g. rock, dirt, etc) and a weight. From this grid we extract triangle data (using the chosen extraction method). This issue with multimaterial support is knowing which extracted triangle correlates to which material from the voxel grid.
As of right now I’m really busy with school. This weekend I’ll be working on adding multimaterial and wang tiling to my current demo, hopefully I’ll have that done by monday. I think Cubical Marching Squares is one of the strongest methods, but has the least amount of resources and few open implementations. I’m still doing the research and hopefully by some time next week I’ll have a detailed list of implications for each method.
I haven’t really thought about the multimaterial issue so far. Because I think that it will be possible no matter what. Maybe a little harder than with other methods but I don’t really think so. Afaik it is just a mapping question which depending on the implementation shouldn’t be too hard.
The reason why I decided to go for CMS is that I think most of the issues like cell interpendency, topological and crack patching issues are natively solved and it is a very elegant way of forming the components. Most other methods seem to need some extensions and modifications and that kind of seemed to be workarounds to me. Also as it is based on marching squares one can simplify things easily to 2d. Actually I started making 2d to understand the topic and make things work. Now I started to make things like threading, chunk system and lods in 2d and pseudo 3d so you have less things to care about and less data to check If that is working going the next step to cubical marching squares is not that hard. I already did that in an very early version.
I know there is not much information on that, in fact the paper you mention in your blog is the only one I know. I found it along with a power point presentation and some additional information on the website when I started to research on voxels some time ago but haven’t seen anything else. But the thing is you can kind of consider anything on simple marching squares as information because actually CMS is exactly the same thing just working on “blocks with 6 sides flatten out” one after another. You then just have to understand the idea of CMS and how things become combined to form the exact same components as marching cubes does. Using hermite data to detect sharp features and solve cracks.
Have you guys tried contacting the people who actually wrote these papers to ask them for some pointers? They might be able to refer you to other research.
Nope I didn’t do that so far.
They actually give a lot of references. But they are on issues with surface extraction in general. About marching cubes, octrees, resolving ambuigities and stuff like that. But information directly on their algorithm cubical marching squares is kind of rare. In the end their paper describes it quite ok but there is one thing I don’t really get. They are using hermite data which they generate from different input data like a mesh or scalar field. And that is where they not really give information on how they do it. Afaik hermite data consists of exact intersection points and their normals. But while having a NxNxN field of density values totally makes sense I am a little unsure on how this hermite data is structured. Because “exact” points kind of is a contrast to having a symmetric grid and also you wouldn’t have one point for a specific x,y,z density value in the field but several. And if we save a list of points instead of a density value not only it is a lot more data but also one would lose implicit information which points to use and connect to each other.
Maybe someone has a hint on how hermite data is structured and/or generated. That would really help alot.
In the comments one of the developers talks about CMS:
Philip Trettner:
What is a real game breaker for me is that DC has _a lot_ inter-cell dependencies while CMS manages to reduce them to near zero (even though they claim to have zero inter-cell dependency, I got the impression that they assume that you have the finer-LOD data in transition cases which is often not the case). This dependency is what caused me and my team a lot of headaches and led to "The Stitcher" which caused a lot of bugs and decreased performance. (The Stitcher has to generate small patches between chunks to "stitch" the chunks together)
He also mentions a post or two later that he had problems with getting it to work with multimaterials:
I had to change some aspects as CMS does not work that well in the multi-material case
He also sorta talks about how he stores the hermite data for their DC:
we store several voxels in a "chunk" (e.g. of size 32x32x32 voxels) and within a chunk, materials and intersections are saved in a cache-friendly continuous float array. Shared edges between chunks are saved multiple times and need to be kept in sync. The storage overhead is relatively small given sufficient chunk size.
He also mentions:
The intersection can be stored with one float, the normal with 3. Each material index is typically one int for us (to allow for sufficiently many different materials).
So my guess is that their storing the hermite data with chunk or voxel data.
I don’t know if that helps, but if you read their articles you might find out more.
Oh yea I know that article but haven’t quite read it completely. Maybe now it is time to do so. At the moment I am just working on the voxel data, hence I still have the crack issues at LOD changes. That is my next step to solve.
@FuzzyMonkey
Upvoid actually switched over to CMS ( https://community.upvoid.com/t/your-suggestions-for-upvoidminer/25/8 ) and afaik they haven’t implemented sharp features yet; another thing about the CMS algorithm that I understand is that it didn’t quite cover sharp edges, if I remember correctly; I think it said you had to do it yourself? But if Upvoid implemented the CMS algorithm (which they have) and they still haven’t implemented sharp edges, then it can be assumed that it doesn’t have the feature built in naturally to the algorithm.
@X-Ray-Jin
And here’s an old jme dual contouring project: http://code.google.com/p/dual-contouring/
I don’t think he’s still working on it, but it was certainly a nifty little project (probably could’ve been optimized more idk (I’m thankful for the open source), but if you want more info on hermite data I’d take a look into what this guy’s doing; I don’t believe he’s using QEF’s, I think he’s doing particles instead, but it still uses the same data; check out in the shapes I think).
I would really like to see a fully-fledged CMS implementation though, as I’m not clever enough/have enough free time to do it myself XD I’m not quite sure what the speeds would be like; but something with sharp edges that updates as fast as FuzzyMonkey’s MC would be really cool =D
@nomnom
Thank you. I have found that project, too. But as far as I can see it he also assumes you already have the intersection points and the normals. At least I couldn’t find where he generates them. Would be quite nice if you could find out more, so I don’t have to add another point to the ToDo list. I have also seen the other document but haven’t yet worked through it completely.
And you are right CMS doesn’t naturally handle sharp features. Hermite Data is just the precondition to detect them and then handle them. Actually I had a running CMS implementation in my first version that really just creates a basic mesh without anything in addition like LODs or sharp features.
In my current version I am running rather the classic Marching Squares for simple 2D outline or surface and via extruding on the y-axis I get something I like to call pseudo 3D. It actually looks a little like Minecraft just a little less blocky as it at least is smooth on the xz plane. However with this version I have LODs, a chunk system and threading implemented. Now before I go on making it CMS again I wanted to build in the Hermite Data stuff, sharp features and editing so that all the major problems are solved. The multimaterial thing is something I enqueued to the very end. I am quite positive that that is relatively easy to achieve once everything else is working and you have a nice structure.
So I had a bit of time this weekend to work on adding multimaterial support to my marching cubes demo. I really wanted to get around to wang tiles (makes textures look more organic when tiled) but things took a lot longer then expected. That being said I got most of the multimaterial support done so I thought I’d post the demo for that.
Hey fellow monkey,
nice thing another good looking start on a Voxel Engine for jME. Actually I am working on one, too, which should also be available for other libraries but my main focus lies on jME. I just took a look at your blog and saw you also consider Cubical Marching Squares which is interesting because nearly no one has heard of that and actually I decided to go with that one.
Maybe if you are interested we can talk about all that stuff. If so let me know or just come to the #jmonkeyengine irc channel I am most likely to be found there.
Greetz
There will plenty of opportunities this summer to test the technology. If you want to actively contribute code I’m sure we can work something out. Later in the summer (after the isosurface method is completed) it’ll be easier to contribute new features.
Here’s just a few features that you may be interested in implementing:
-Advanced voxel based physics
-Model voxelization
-Voxel based water
-Procedural generation tools
-Voxel editor plugin
So if any one else is interested in contributing code you can contact me at: jon.mecham@gmail.com
@zarch said:
Really nice work, I especially like the blog post. Excellent detail level.
And GSoC hasn’t even officially started yet!
Thanks ^.^
I really wanted to spend some time on exploring some of the less discussed topics about voxel terrain (e.g. multimaterial support). It has also given me a chance to get familiar with jMonkeyEngine. Before I start working on a new Isosurface technique I want to explore 2 more things in side my marching cubes demo. Lighting and organic texturing support.
By organic texturing I’m referring to the problem of tiling large surfaces with a relatively small texture.
Consider the following image:
Also there are many of other things you can do to make tiling less noticeable.
This has been a really good resource on the topic: UDK | TerrainAdvancedTextures
By the end of next week I’m hoping to be done my marching cubes demo.
Some where in the middle next of the week I plan on doing a detailed post about each isosurface extraction method. It’ll discuss their pro/con’s and implementation timeline. I’m hoping this will give us a chance to discuss which method will be best for me to implement this summer.
For my marching cubes demo I used layered textures… often the same texture just layered at two different resolutions based on distance. Each layer also has its texture coordinates pumped through a noise fractal.
It’s basically lighting.j3md except I’ve replaced the texture lookups. It currently supports normal maps but not parallax maps.
Maybe it’s useful.
Here is an example. It’s not perfect because you can still see some of the stronger elements of the texture repeating in the background but even they are meandering because of the noise-based sampling:
The really nice thing is the seamless transition to a higher resolution as you get closer. This was especially nice on the dirt texture in my marching cubes demo.
What decisions need to be made? The sooner you get them out in the open the better. Doesn’t matter if they’re not that clearly defined yet.
If that is working going the next step to cubical marching squares is not that hard. I already did that in an very early version.
