The Marching Cubes Algorithm 2: Meshes & Marching Squares

Mesh

First steps into meshes

The first thing I had to do was to Google what a mesh is, because I really had no clue. A quick Wikipedia read and I am now a meshes expert! If you are also confused like I was by this term, it turns out being a really simple concept:

In 3D computer graphics and solid modeling, a polygon mesh is a collection of vertices, edges and faces that defines the shape of a polyhedral object. (Courtesy of Wikipedia)

Even though I was trying to accomplish it in 2D, I think you got the idea (and if you didn’t, you wil soon, just keep reading :p): I am going to try to smooth out the borders of the caves from my previous post.

The algorithm

The algorithm is the same as the one we discussed before for the 3D case, but in 2D (that’s why it’s called “Marching Squares”). We start by dividing our space into squares, each one having his 4 vertices on 4 adjacent pixels in the drawing (see Figure 1 for an example).

Figure 1: An example of how the cave is divided into squares, using the seed "Marching Cubes"

Each one of these squares will have 4 control points, one on each one of the square’s edges. These points will then be connected based on which vertices have to be inside the wall and which have to be outside; figure 2 displays all the (16) possible combinations.

Figure 2: All the possible combinations

Figure 3: Close up showing the "control points"

Unfortunately, I had to stop working on this “series” of blog posts because of school reasons :( Hopefully, one day I’ll come back to it.