Marching Cubes with Multiple Materials

Recommended Posts

Consider how one makes terrain using marching cubes. By having a grid of floats we can represent a continuous field that marching cubes will interpolate and turn into a nice smooth isosurface for the player to walk around on. This is easy and excellent for creating mountains and valleys and so on, but what if we want more variety in our game? A game is not normally made of just grass and sky. Maybe some places should be sand, or water, or road. How could that be worked into the mesh that we're getting from marching cubes?

The obvious approach seems to be to have multiple fields, so each point on the grid has a certain level of sand, soil, rock, water, and so on. Then we modify the marching cubes algorithm to look for transitions between materials, so it puts a surface between areas of mostly one material and areas that are mostly other materials. We'd also want to keep track of when these surfaces touch the air, because that's the only time when we'd actually want to triangulate and render the surfaces.

Suddenly the delightfully simple marching cubes algorithm is looking a lot less obvious. Has anything like this ever been done? Does anyone have any tips? Is this the right approach?

Edit: Embarrassing mistake! I didn't think of phrasing the problem as "multiple materials" until I went to post this question, but now that I have I see there are plentiful google results for marching cubes with multiple materials. I'm still interested in any tips and advice, but now I have other resources to help with this problem.

From the Google results, this paper looks especially interesting: Automatic 3D Mesh Generation for A Domain with Multiple Materials

Edited by Outliner

Share this post


Link to post
Share on other sites

That paper seems about right. Basically in the simple form of marching cubes you create a surface in every cube that contains a sign-change. To add materials, you need to also produce a surface in every cube that contains a material change.

Share this post


Link to post
Share on other sites
19 minutes ago, LifeIsGood said:

The paper on Dual Contouring also provides a solution to realize multiple materials.

This paper? Dual Contouring of Hermite Data by Tao Ju et al.

If I have this right, then the essence of the problem is to convert the marching cubes algorithm from an algorithm where the corners of each cube can only be positive or negative, into an algorithm where the corners of each cube can take anywhere up to 8 distinct values. If I have this right, then while ordinary marching cubes deals with 2^8 possibilities, the multiple material marching cubes needs to deal with a far greater number of possibilities. It's not as many as 8^8, but it's still quite a few. Hopefully one of these papers will go into a way to enumerate the possibilities.

Supposing that we're dealing with sand, rock, and air, then each corner has three numbers, one for each material, and the material of the corner is whichever has the greatest number. When two adjacent corners have distinct materials, then the algorithm will put a vertex somewhere on the edge between the corners. Supposing that the one of the corners is sand and the other is rock, we can linearly interpolate the values of sand and rock between the two corners, and the position of the vertex should be the point at which we switch from sand having the greatest value to rock having the greatest value. It's possible that if we interpolated the air value we'd find that air has the greatest value somewhere along the edge, but it's probably fair to just ignore that.

I should focus on implementing a multiple material marching squares as a starting point, then move up to marching cubes once I'm confident I've got all the details worked out for the 2D version. Unfortunately it's not so easy to find resources for the 2D case.

 

Share this post


Link to post
Share on other sites
27 minutes ago, Outliner said:

If I have this right, then the essence of the problem is to convert the marching cubes algorithm from an algorithm where the corners of each cube can only be positive or negative, into an algorithm where the corners of each cube can take anywhere up to 8 distinct values. If I have this right, then while ordinary marching cubes deals with 2^8 possibilities, the multiple material marching cubes needs to deal with a far greater number of possibilities. It's not as many as 8^8, but it's still quite a few. Hopefully one of these papers will go into a way to enumerate the possibilities.

Their is a more straightforward way of dealing with this. For any one material, there are at most 2^8 possible configurations. And there are at most 8 possible materials that could intersect in any one cell.

Worst case is you have to run the exact same marching cubes algorithm 8 times (once for each material present in the current cube). The tables don't expand any, if you don't mind hard transitions between materials.

Share this post


Link to post
Share on other sites
2 minutes ago, swiftcoder said:

Worst case is you have to run the exact same marching cubes algorithm 8 times (once for each material present in the current cube).

Just running the marching cubes algorithm for each material doesn't seem like it would work. Hard transitions are exactly what I want, since that's easier to render than fading between materials, but if we just do 8 separate marching cubes, then what would prevent the materials from clipping into each other?

Suppose we have three materials on the corners of a cube, then it seems they ought to divide the cube among themselves around a point in the middle. Using three separate marching cube procedures the materials might end up leaving an empty space in the middle, or they might end up clipping into each other so some parts of the cube are claimed by more than one material, but it seems impossible for the cube to be properly partitioned among the materials. The geometry of the situation is more complicated than single-material marching cubes ever needs to deal with.

As it happens, I think I've found the actual number of possibilities for multi-material cubes. It's called the 8th Bell number, and it is 4140. It's roughly 16 times the 256 possibilities of single-material marching cubes, but still well within the range of a 16-bit integer.

Share this post


Link to post
Share on other sites

Finding a good index for the lookup table is tricky. There are 4140 cases for a cube with various materials on its corners, but how should we number those cases? There are 28 comparisons we could do between the corners of a cube, and if we give each comparison a bit in the index, then we end up with an array of 268,435,456 elements, of which only 4140 will ever be used.

Here's a blog entry about generating lists of set partitions. It generates partitions in a particular order, but it's not clear how to reverse the process and generate a number when given a partition. Enumerating set partitions with Bell numbers and Stirling numbers of the second kind.

Share this post


Link to post
Share on other sites
18 hours ago, Outliner said:

but if we just do 8 separate marching cubes, then what would prevent the materials from clipping into each other?

Depends how watertight/deterministic your marching cubes is, I guess. I'll have to give this a try at some point.

Share this post


Link to post
Share on other sites
10 minutes ago, swiftcoder said:

Depends how watertight/deterministic your marching cubes is, I guess.

If I understand this correctly, then the issue isn't about floating point errors or deterministic behavior. Even with absolute precision there would still be no way to avoid clipping except by having large gaps between materials. For example:

59c01e839184b_MarchingSquaresGap.gif.e8400bb72ca14365193b06a2c681d6b0.gif

On the left we have a Marching Squares square with three materials inserted with three separate single-material marching squares passes. Unfortunately there is a gap, so picture grass, sand, and water meeting at a point that includes a hole to infinity. If we want to fill that gap, we're forced to do something like shown on the right, where we increase the magnitude of one of the materials, but if we increase any of the materials even slightly it will not only start to fill the gap, but also start to overlap with the other materials.

Share this post


Link to post
Share on other sites

In the past, I never bothered with marching different meshes for different terrain materials. I just marches the terrain as a single mesh, then used vertex colors (generated after marching the surface, using various techniques) to blend between terrain textures in the shader. Something like this (very quick example):

797O5Ok.png

With a tri-planar shader that displays different textures for the top surface than what it displays for the side surfaces, then you can just paint the v-colors (either procedurally, or by hand if that is your wish, in a post-process step) for different materials, and the shader will handle blending between the types and applying the tri-planar projection. A single color layer provides for 5 base terrain materials, if you count black(0,0,0,0) as one material, red(1,0,0,0), green(0,1,0,0), blue(0,0,1,0) and alpha(0,0,0,1) as the others. Provide another RGBA v-color layer and you can bump that to 9.

Doing it this way, you don't have to be content with sharp edges between terrain types, since the shader is content to smoothly blend between materials as needed, and you don't deal with the hassle of marching multiple terrain meshes.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now


  • Forum Statistics

    • Total Topics
      628639
    • Total Posts
      2983972
  • Similar Content

    • By Michael Pearson
      Hello all!   I'm currently in my third year on my 3D Animation & Games Development course, and I am in the process of doing some basic primary research for my dissertation project, which is to create a high quality 3D Environment for use in video games and potentially VR.   I have a questionnaire (targeting other artists in the field), and I would really appreciate it if you took some time to have a look and fill it out:   https://docs.google.com/forms/d/e/1FAIpQLScW12nFI8-fMlAUMNSQvOInxhnIfXpG91iRCm25TVlZufrvbQ/viewform?usp=sf_link   Thank you in advance!   Mike.
    • By pabloreda
       
      I am coding the rasterization of triangles by the baricentric coordinate method.
      Look a lot of code and tutorials that are on the web about the optimization of this algorithm.
      I found a way to optimize it that I did not see it anywhere.
      I Only code the painting of triangles without Zbuffer and without textures. I am not comparing speeds and I am not interested in doing them, I am simply reducing the amount of instructions that are executed in the internal loop.
      The idea is simple, someone must have done it before but he did not publish the code or maybe in hardware it is already that way too.
      It should be noted that for each horizontal line drawn, of the three segments, you only need to look at one when going from negative to positive to start drawing and you only need to look at one when it goes from positive to negative when you stop drawing.
      I try it and it works well, now I am implementing a regular version with texture and zbuffer to realize how to add it to this optimization.
      Does anyone know if this optimization is already done?
      The code is in https://github.com/phreda4/reda4/blob/master/r4/Dev/graficos/rasterize2.txt
      From line 92 to 155
       
    • By Kerrick
      TL;DR: noob non-coding teacher somehow thinks they can build a narrative educational game in WordPress; plz halp how do I games?
      I'm mostly a teacher with no coding background--I played with teaching myself Java for a bit but couldn't really code anything from scratch. I'm interested in developing (as a hobbyist) an educational game that would be a sort of choice-based narrative branching storyline, a bit like Fallen London/Storynexus. Because it's so storyline based and I don't need crazy 3d animation, I'm considering just building it as a WordPress site with a couple of gamification plug ins to handle inventory and choice consequences. The unique hook is that the game requires (suggests really) that the player accomplish real world building challenges to accomplish your goals. I.e. Your character has to cross a river? Get some popsicle sticks or cardboard or whatever and build a model bridge. Take a photo of your bridge and upload it to your portfolio to continue (and maybe I don't develop this feature right away).
      I'm in this for three reasons: the educational value for families and teachers, the storyline and world I'm building that I'm super excited about, and the fame and massive wealth (just kidding but it has to have to potential to pay for itself).
      Before I sink too much of my life into this, I want to know more about what I'll need to do to make it work.
      Specifically my questions are:
      1) I get that WordPress isn't optimal for developing games. But can I do it or will I have to learn a new engine because I can't make do what I want? (And if so, what's a better engine with low-to-no coding prereq that will still allow me to sell my game?)
      2) How do I budget for a project like this? (The link to the Reddit post about legal fees was very useful thank you)
      3) What are the additional considerations when creating a game like this intended for children with adult supervision? (Obviously privacy, and I need to cover my assets in case some kid takes "go build a bridge!" too literally and gets hurt with mama's table saw in the garage...)
      4) Is this not the forum for this since what I'm talking about is something more like educational narrative fiction and certainly not the spectacularly complex and amazing projects you all are working on?
      Thank you for any and all thoughts.
    • By Kieron Wiltshire
      Background
      I'm new to game development as a whole but I've been programming for almost 7 years now, it's my daily job. I work mainly in web development creating data aggregation and analytic tools. I currently work for a company called Concept Gaming, we design and develop online casino based games like roulette, slots and blackjack etc..
      I'd like to move more away from my field and experiment with game engines like CryEngine in order to create AAA games. Now I'm not an naive, I understand that these types of games requires heaps of time and effort and usually a dedicated team. So my goal is not to create a game as of yet.
      That being said I've decided to learn CryEngine rather than Unity or Unreal. Most will probably mention that Unity has a much more community friendly environment in terms of helping beginners out and I will agree, however I've chosen CryEngine by preference. I found that after downloading all 3, CryEngine seemed to be the one to appeal to me the most.
       
      Question
      So I want to know how you'd go about creating an open/infinite world in CryEngine. I know it's practically impossible to just straight up create a universe due to memory constraints and processing power etc.. but if you take a look at games like Star Citizen who also use CryEngine, they've managed to actually achieve some way of simulating a seamless universe. Now I do know that they work closely with the CryTek team and they're solution is mostl likely proprietary, but could someone please explain how I'd go about achieving this in CryEngine?
       
      much appreciated,
      ~ Kieron
    • By Vegermy
      What are some of the best ways to actually sell your prototype or a Proof of Concept to a company? Would a power point presentation be best? Or maybe a video like a teaser trailer to go along with a power point presentation? I'm just trying to get some ideas of how to best go about this.
  • Popular Now