• Advertisement

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
Advertisement
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


  • Advertisement
  • Advertisement
  • Popular Tags

  • Advertisement
  • Popular Now

  • Similar Content

    • By Bokchee 88
      I am animator by hand, and i am doing game animation for at least 8 years so far. During the last 2 years, i came with a idea for game and maybe some day, i want to start indie game company. As i am thinking to start game company, i am also thinking what kind of value i can give to the company. For example, am experience in animation,sales(I was selling web development services, before i jumped to gaming), bit of rigging- just not for production, i am learning on the side as well. The rest of the gaming production, like modeling, concept art, texturing, i am total noob or to say better, i am no near interest to do modeling for example, don't have such a patience to do it. But before characters and things are made for animating, what the hell i am would do?
      Also, what is the ideal size of the founding team of a game company? Positions to be filled mostly are, Concept artist, Modeler/Texture artist, programmer, animator-rigger. And later would need more people to join, like more animators, programmers, sound, fx,etc.
       
      And lastly, do i need to have something,like a prototype, to show people and get them interest, or should i ask someone i know, for skill that i lack, for example, Modeling would be great, texturing and rigging, and to start all together from scratch?  
    • By francoisdiy
      So I wrote a programming language called C-Lesh to program games for my game maker Platformisis. It is a scripting language which tiles into the JavaScript game engine via a memory mapper using memory mapped I/O. Currently, I am porting the language as a standalone interpreter to be able to run on the PC and possibly other devices excluding the phone. The interpreter is being written in C++ so for those of you who are C++ fans you can see the different components implemented. Some background of the language and how to program in C-Lesh can be found here:

      http://www.codeloader.net/readme.html
      As I program this thing I will post code from different components and explain.
    • By isu diss
      I'm trying to duplicate vertices using std::map to be used in a vertex buffer. I don't get the correct index buffer(myInds) or vertex buffer(myVerts). I can get the index array from FBX but it differs from what I get in the following std::map code. Any help is much appreciated.
      struct FBXVTX { XMFLOAT3 Position; XMFLOAT2 TextureCoord; XMFLOAT3 Normal; }; std::map< FBXVTX, int > myVertsMap; std::vector<FBXVTX> myVerts; std::vector<int> myInds; HRESULT FBXLoader::Open(HWND hWnd, char* Filename, bool UsePositionOnly) { HRESULT hr = S_OK; if (FBXM) { FBXIOS = FbxIOSettings::Create(FBXM, IOSROOT); FBXM->SetIOSettings(FBXIOS); FBXI = FbxImporter::Create(FBXM, ""); if (!(FBXI->Initialize(Filename, -1, FBXIOS))) { hr = E_FAIL; MessageBox(hWnd, (wchar_t*)FBXI->GetStatus().GetErrorString(), TEXT("ALM"), MB_OK); } FBXS = FbxScene::Create(FBXM, "REALMS"); if (!FBXS) { hr = E_FAIL; MessageBox(hWnd, TEXT("Failed to create the scene"), TEXT("ALM"), MB_OK); } if (!(FBXI->Import(FBXS))) { hr = E_FAIL; MessageBox(hWnd, TEXT("Failed to import fbx file content into the scene"), TEXT("ALM"), MB_OK); } FbxAxisSystem OurAxisSystem = FbxAxisSystem::DirectX; FbxAxisSystem SceneAxisSystem = FBXS->GetGlobalSettings().GetAxisSystem(); if(SceneAxisSystem != OurAxisSystem) { FbxAxisSystem::DirectX.ConvertScene(FBXS); } FbxSystemUnit SceneSystemUnit = FBXS->GetGlobalSettings().GetSystemUnit(); if( SceneSystemUnit.GetScaleFactor() != 1.0 ) { FbxSystemUnit::cm.ConvertScene( FBXS ); } if (FBXI) FBXI->Destroy(); FbxNode* MainNode = FBXS->GetRootNode(); int NumKids = MainNode->GetChildCount(); FbxNode* ChildNode = NULL; for (int i=0; i<NumKids; i++) { ChildNode = MainNode->GetChild(i); FbxNodeAttribute* NodeAttribute = ChildNode->GetNodeAttribute(); if (NodeAttribute->GetAttributeType() == FbxNodeAttribute::eMesh) { FbxMesh* Mesh = ChildNode->GetMesh(); if (UsePositionOnly) { NumVertices = Mesh->GetControlPointsCount();//number of vertices MyV = new XMFLOAT3[NumVertices]; for (DWORD j = 0; j < NumVertices; j++) { FbxVector4 Vertex = Mesh->GetControlPointAt(j);//Gets the control point at the specified index. MyV[j] = XMFLOAT3((float)Vertex.mData[0], (float)Vertex.mData[1], (float)Vertex.mData[2]); } NumIndices = Mesh->GetPolygonVertexCount();//number of indices MyI = (DWORD*)Mesh->GetPolygonVertices();//index array } else { FbxLayerElementArrayTemplate<FbxVector2>* uvVertices = NULL; Mesh->GetTextureUV(&uvVertices); int idx = 0; for (int i = 0; i < Mesh->GetPolygonCount(); i++)//polygon(=mostly triangle) count { for (int j = 0; j < Mesh->GetPolygonSize(i); j++)//retrieves number of vertices in a polygon { FBXVTX myVert; int p_index = 3*i+j; int t_index = Mesh->GetTextureUVIndex(i, j); FbxVector4 Vertex = Mesh->GetControlPointAt(p_index);//Gets the control point at the specified index. myVert.Position = XMFLOAT3((float)Vertex.mData[0], (float)Vertex.mData[1], (float)Vertex.mData[2]); FbxVector4 Normal; Mesh->GetPolygonVertexNormal(i, j, Normal); myVert.Normal = XMFLOAT3((float)Normal.mData[0], (float)Normal.mData[1], (float)Normal.mData[2]); FbxVector2 uv = uvVertices->GetAt(t_index); myVert.TextureCoord = XMFLOAT2((float)uv.mData[0], (float)uv.mData[1]); if ( myVertsMap.find( myVert ) != myVertsMap.end() ) myInds.push_back( myVertsMap[ myVert ]); else { myVertsMap.insert( std::pair<FBXVTX, int> (myVert, idx ) ); myVerts.push_back(myVert); myInds.push_back(idx); idx++; } } } } } } } else { hr = E_FAIL; MessageBox(hWnd, TEXT("Failed to create the FBX Manager"), TEXT("ALM"), MB_OK); } return hr; } bool operator < ( const FBXVTX &lValue, const FBXVTX &rValue) { if (lValue.Position.x != rValue.Position.x) return(lValue.Position.x < rValue.Position.x); if (lValue.Position.y != rValue.Position.y) return(lValue.Position.y < rValue.Position.y); if (lValue.Position.z != rValue.Position.z) return(lValue.Position.z < rValue.Position.z); if (lValue.TextureCoord.x != rValue.TextureCoord.x) return(lValue.TextureCoord.x < rValue.TextureCoord.x); if (lValue.TextureCoord.y != rValue.TextureCoord.y) return(lValue.TextureCoord.y < rValue.TextureCoord.y); if (lValue.Normal.x != rValue.Normal.x) return(lValue.Normal.x < rValue.Normal.x); if (lValue.Normal.y != rValue.Normal.y) return(lValue.Normal.y < rValue.Normal.y); return(lValue.Normal.z < rValue.Normal.z); }  
    • By nick1
      Hello,

      I have limited programming experience in C++, but have always had a passion for games.  Where do I start?  I have a rough idea of the type of game I want to develop and am ready to commit the time necessary to learn new languages.  Are mobile games too difficult to begin with? Should I begin learning the basics of keyboard controls before attempting touch screens?  I would appreciate any input or advice!
      Thanks!
      Nick1
    • By khawk
      Dene Carter, Managing Directory @ Fluttermind LLC (@fluttermind)
      From Indie to Fable and Back. 30 Years of Wisdom.
      Started writing games in 1984 when he was 14 years old. What has he done in 33 years?
      Druid - Commodore 64 Original Dungeon Keeper core team Fable franchise and more Indie through AAA.
      "I am an idiot" - first learned in 1984, and every year after.
      Rockman - made $7500 for 2 weeks of work. Figured he could make 26 games a year, or $438k in today's money.
      Takeaway: Really stupid at 14.
      Even in 1980's, developer only got 12-14% royalties.
      (Side note: Dene is fun to listen to. Recommend this on the Vault when it goes online.)

      You are not your players.
      Made a black and white game on a Spectrum, which was color. Did it because he was poor. Problem is his audience were not poor, and had color TV's. Reviews were not nice. Players see things completely different to you. Do not forget that your players have not seen the game as much as you. Avoid difficulty/complexity-creep. The real world has distractions and beer - they don't care about your game as much as you do. Test your mobile game on the toilet - that's what your real players do. Fundamentally, players live inside their own brains, not yours. Those you ignore will ignore you in return. Design for your players' minds, not for you. Generalizing is Really useful
      "An expert who is too narrow has difficulty colaborationg" - Valve Employee Manual Did a lot of things over the course of his career. Everyone did everything in the 1980's and 1990's. Most developers generalized. Developing a broad skill-set aids communication. Large teams require collaboration and clear communication. Knowledge breeds respect (never say 'JUST'). 'Just' suggests a task is easy. It might not be. Ignorance is an energy. Don't forget you are human. You are designed to adapt and can do anything if you put your mind to it. Be a human. Learn a skill outside your area. Programmer learn how to 3D model. Artist learn how to code. Learn music, theater. Think of yourself as an artist. Rapid Team Growth is Dangerous
      "If your team can eat more than two pizzas, it's too large." Werner Vogels, Amazon VP/CTO Early Fable - 3 developers. Communication very easy. Later Fable, team grew bigger. At 12 people rumor mill started to develop. Can't have everyone in every meeting at same time. Pockets and cliques develop. Fred Brooks. Communication paths don't grow linearly. Team communication grows exponentially. [n * (n-1)] / 2 8 people on team, 28 connections. Ringelmann Effect - "Larger groups lead to less motivation & coordination & productivity." Decreased motivation - larger group, start to feel like a cog in the machine. Decreased coordination - communication pathways explode. Suggestion: Increase identifiability. Make sure everyone knows everyone's contribution. Most of all: think before growing your team. Blandness Has Its Uses
      Pursuit of excellence can be wasteful. Sounds counterintuitive. Blandness helps disguise repetition. Think reusing assets. Players notice the patterns. When asking for something to be made, communicate the context of assets - how will they be seen or heard? Often find they need to be bland. Prototypes Can Be Misleading
      Experiential games are difficult to prototype. More useful for mechanical games. Fable only came together at the very end - threw away at least one entire combat system. Looking back, it wasn't polished not necessarily bad. Bland prototypes are better than ugly ones for experiential. Keep prototype completely separate. Define prototypes success criteria. Art Style is More Important Than You Think
      Curate rather than create Style can hide the fact you can't draw. Restrict complexity. Style is marketing. Unique style tells players there may be something unique about your game. Streamline Your Process
      What is your iteration cost? Recognize your cost to try something and learn from it. Making your life easier is real work. Resist self-sabotage. (context of making tools) Closing Thoughts
      Don't let technology dictate your game's core promise. Static screenshots have to look good, too. No 1 pixel lines. Don't worry about the things people don't ever get to see. Don't panic if your game sucks - fix it. Editor thought: Really enjoyed this talk. Dene is a fun speaker, and his advice was raw, real world advice for anyone aspiring to make it in game development.
  • Advertisement