Wednesday, May 14, 2014

Introduction to Multimaterial Terrain

Introduction:

In this post I will be taking about the technical aspects of implementing multimaterial support for your voxel engine. I will discuss everything from shaders to atlas construction. For this article I will talk about the basics of marching cubes and how we extract material information form it.

Brief Introduction to Marching Cubes:

Matching cubes works by sampling the corners of a cube and determining where the triangles (isosurface) will lay. 

The edges are labeled in green and the vertices are labeled in red. The triangles are generated based on whether or not the corners are considered to be "in" or "out" side the volume. Usually each corner is associated with a weight that when above a certain value is consider to be in the volume else its considered outside. The vertices of the generated triangle are interpolated between the "inside" and the "outside" of the terrian.
For most voxel engines each corner represents a voxel and each voxel will have a weight and a material associated with it (e.g. rock, dirt wood, etc). 

To learn more about marching cubes:

From Voxels To Triangles:

So now that I've discussed the basics of marching cubes lets talk about texturing our triangles outputted from marching cubes. 
Every vertex has an associated material. This material is found by looking at which voxel was the primary contributor to that vertex. In marching cubes its particularly easy to associate a vertex with a voxel in other isosurface extraction methods its more complex. 

Since we want to support a lot of materials we are going to need to make use of an atlas. An atlas binds together a bunch of textures into one file so that the graphics card doesn’t have to switch textures everytime you need to render a new material.

Introduction to Atlas Construction:

Atlases provided a huge speed up when you need at lots of textures all at once. But they have a lot of problems associated with them to. The primary problems using atlases include (but not limited to) are:
  • They are hard to mipmap
  • Require more complicated texture wrapping (tiling)
  • Limits the resolution of your material
Lets start by talking about one of the most troubling problems, mipmapping. For a fully mipmapable atlas you'll have to throw away the 1/4 of your intended resolution. Below is an atlas that's been constructed to be fully mipmapable.
Atlas that's fully mipmapable

Its certainly possible to create an atlas that supports up to a certain level of mipmapping which  may or may not be good enough for your application.

To learn more about constructing tilable atlases:


Texturing Multimaterial Triangles (shaders!):

So now that we have triangles with specific material and an atlas lets talk about putting everything together.
So each triangle will have a vertex, a normal, and a material type. One of the first problems you'll find is that if you want to support blending of things that are on the same atlas. So, you have to some how get the material types of each vertex to the pixel/fragment shader. This is a huge problem because you can't just interpolate the material index. The only solution that I could find was to store every material index in every vertex of the triangle. This also means that our vertices are no longer unique and cant be shared across multiple triangles (huge decrease in efficiency). 

Another thing we'll have to store is a weight per vertex. This would be a vec3 and allows of to nicely blend between different materials. 

So lets review whats going to our vertex shader:
Types in triangle - vec3 
Type Weight - vec3
Vertex Position - vec3 
Normal - vec3


So here is our vertex shader code:

/* compute offset into atlas suff here */
float atlasFrac = (1.0/m_atlasSize);
float floored;
floored = floor(vertexType.x / m_atlasSize);
offsets[0] = vec2(vertexType.x - floored * m_atlasSize , floored) * atlasFrac + m_baseOffSet;
floored = floor(vertexType.y / m_atlasSize);
offsets[1] = vec2(vertexType.y - floored * m_atlasSize , floored) * atlasFrac + m_baseOffSet;
floored = floor(vertexType.z / m_atlasSize);
offsets[2] = vec2(vertexType.z - floored * m_atlasSize , floored) * atlasFrac + m_baseOffSet;
All that are vertex shader is really going to do is calculate the atlas offset for each material need.
This could easily be done outside of the vertex shader. Everything else is passed to the fragment shader.

So here is our fragment shader:


uniform sampler2D m_cAtlas;
uniform float m_baseWidth;

varying vec3 normal;
varying vec4 vertex;
varying vec3 vertexWieght; 
varying vec2 offsets[3];

void main()
{
    //Now that we're in frag shader our type wieghts are "averaged"
    //Now we normalize them:
    vec3 weights =abs( vertexWieght / (vertexWieght.x + vertexWieght.y + vertexWieght.z));
    
    //Do triplaner texturing:
    vec3 blending = (abs( normal ));
    // Force weights to sum to 1.0 (very important!)
    blending = normalize(max(blending, 0.00001));      
    blending /= (blending.x + blending.y + blending.z );
    
    
    ///////////////////////////Type 1////////////////////////////////////////
    vec4 scaled = vertex*.25; //Texture Scaling
    vec4 coords = vec4(fract(scaled.x),fract(scaled.y),fract(scaled.z),1);
    //Normalize to [0-1] space Manually 'wrap' -.75+1 = .25
    coords = min(abs(coords),abs(coords+1))*m_baseWidth;
    vec4 col1 = texture2D( m_cAtlas, coords.yz+offsets[0]);//x dom
    vec4 col2 = texture2D( m_cAtlas, coords.zx+offsets[0]);//y dom
    vec4 col3 = texture2D( m_cAtlas, coords.xy+offsets[0]);//z dom
    //Texture 1:
    vec4 tex1 = (col1 * blending.x + col2 * blending.y + col3 * blending.z);
    //////////////////////////////////////////////////////////////////////////
    
    ///////////////////////////Type 2//////////////////////////////////////////
    scaled = vertex*.25; //Texture Scaling
    coords = vec4(fract(scaled.x),fract(scaled.y),fract(scaled.z),1);
    //Normalize to [0-1] space Manually 'wrap' -.75+1 = .25
    coords = min(abs(coords),abs(coords+1))*m_baseWidth;
    col1 = texture2D( m_cAtlas, coords.yz+offsets[1]);//x dom
    col2 = texture2D( m_cAtlas, coords.zx+offsets[1]);//y dom
    col3 = texture2D( m_cAtlas, coords.xy+offsets[1]);//z dom
    //Texture 2:
    vec4 tex2 = (col1 * blending.x + col2 * blending.y + col3 * blending.z);
    ///////////////////////////////////////////////////////////////////////////
    
    ///////////////////////////Type 3//////////////////////////////////////////
    scaled = vertex*.25; //Texture Scaling
    coords = vec4(fract(scaled.x),fract(scaled.y),fract(scaled.z),1);
    //Normalize to [0-1] space Manually 'wrap' -.75+1 = .25
    coords = min(abs(coords),abs(coords+1))*m_baseWidth;
    col1 = texture2D( m_cAtlas, coords.yz+offsets[2]);//x dom
    col2 = texture2D( m_cAtlas, coords.zx+offsets[2]);//y dom
    col3 = texture2D( m_cAtlas, coords.xy+offsets[2]);//z dom
    //Texture 3:
    vec4 tex3 = (col1 * blending.x + col2 * blending.y + col3 * blending.z);
    ///////////////////////////////////////////////////////////////////////////
    vec4 finalColor = (weights.x * tex1) + (tex2 * weights.y) + (tex3 * weights.z);
    gl_FragColor =  finalColor;//vec4(offsets[0].y,0,0,1);
 
}


So there's a lot going on here. First off at the top we start by normalizing our vertex weights. Then we do something called triplaner texturing. Basically you use the normal to determine which axis you should use for your texture coordinates.

After that we go through each possible material type and do the following:

  • Scale based on texture type (I just left this as a constant .25 for everything)
  • Wrapping for that texture 
  • Then offset for that texture
  • Calculate the color for that texture using triplaner weights. 

Then we get the final color by blending them together based on the vertex weights.

Here is the final result:



Notice that the blending is very linear. There are methods to make the blending much nicer by utilizing a the textures height map. If your interested you should read more here:
http://www.gamasutra.com/blogs/AndreyMishkinis/20130716/196339/Advanced_Terrain_Texture_Splatting.php


I still haven't gotten around to wang tiles hopefully that's what the next post will be about ^.^

Tuesday, April 29, 2014

So, You Want To Make A Voxel Engine?

Introduction to Voxel Engines:

Voxel terrain provides a few things that simple things that hightmaps cant. First off they are capable of representing complex concave geometries, like caves and tunnels.


Terrain created by heightmap

Terrain created by voxel field

Worlds created by voxel fields can easily be modified. This is why voxel based worlds like those seen in Minecraft and Everquest Next Landmark are so enticing. 
Everquest Next Landmark
Minecraft

Choices. Choices. Choices.

The first choice and most significant choice you'll have to make is the method you'll use to extract surface data (triangles) from your 3D voxel grid. It determines whether your world will be blocky like that of Minecraft or support the smooth hills and sharp featured buildings like those seen in Next Landmark. 

In the following chart I've broken down the pro's and con's of each method:

There are other difference that could have a significant effect on your voxel engine. For instance Dual Contour natively supports a more expressive environment which leads to consistent effects from the operations you do on your 3D voxel grid.

The Second DemoThe First Demo
Different geometries being represented by Dual Contour (on left) and Marching Cubes (on right).

There are more decisions to make like how do store, compression and manage your voxel data. There are plenty of other issues that may arise and further complicate the engine your trying to make. For instance consider the following image:

Notice those annoying repeating patterns in the lava and sand? This is due to a low resolution texture being tiled over a long distance. There are few solutions to this problem, wang-tiles being one of them. The point is that for every addition feature you want to support the complexity of your engine increases.

Papers on each method:

Marching Cubes
Dual Contour
Dual Marching Cubes
Conical Marching Squares


Next posts probably going to be on constructing an atlas that supports wang tiles, and how to incorporate them into your voxel terrain system.