# Meshing algorithm for generating faces in Minecraft

To generate faces of a Minecraft-like world from a three dimensional array, I developed the following meshing algorithm. The faces are given vertices and indices. A vertex consists of a position in space, a normal vector and a texture coordinate. Indices point to vertices to consecutively define faces.

Those variables are used:

// dimensions of the world
#define SIZE 32

// voxel grid representing the world, where 0 means air
uint8_t data[SIZE][SIZE][SIZE];

// results are stored in those vectors
vector<float> positions, normals, texcoords;
vector<unsigned int> elements;


This is the algorithm:

int n = 0;
for(int X = 0; X < SIZE; ++X)
for(int Y = 0; Y < SIZE; ++Y)
for(int Z = 0; Z < SIZE; ++Z)
{
if(data[X][Y][Z])
{
uint8_t tile = clamp((int)data[X][Y][Z], 0, TILES_U * TILES_V - 1);
for(int dim = 0; dim < 3; ++dim) { int dir = -1; do {
ivec3 neigh = Shift(dim, ivec3(dir, 0, 0)) + ivec3(X, Y, Z);

if(Inside(neigh, ivec3(0), ivec3(SIZE) - 1))
if(data[neigh.x][neigh.y][neigh.z])
goto skip;

{
for(float i = 0; i <= 1; ++i)
for(float j = 0; j <= 1; ++j)
{
vec3 vertex = vec3(X, Y, Z) + vec3(Shift(dim, ivec3((dir+1)/2, i, j)));
positions.push_back(vertex.x); positions.push_back(vertex.y); positions.push_back(vertex.z);
}

/*
* the normal vector is not important for this question
*
* vec3 normal = normalize(vec3(Shift(dim, ivec3(dir, 0, 0))));
* for(int i = 0; i < 4; ++i)
* {
*  normals.push_back(normal.x); normals.push_back(normal.y); normals.push_back(normal.z);
* }
*/

/*
* texture coordinates are not important for this question
*
* vec2 coords(tile % TILES_U, tile / TILES_U);
* vec2 position = coords * GRID;
* texcoords.push_back(position.x          + GAP); texcoords.push_back(position.y          + GAP);
* texcoords.push_back(position.x + GRID.x - GAP); texcoords.push_back(position.y          + GAP);
* texcoords.push_back(position.x          + GAP); texcoords.push_back(position.y + GRID.y - GAP);
* texcoords.push_back(position.x + GRID.x - GAP); texcoords.push_back(position.y + GRID.y - GAP);
*/

if(dir == -1) {
elements.push_back(n+0); elements.push_back(n+1); elements.push_back(n+2);
elements.push_back(n+1); elements.push_back(n+3); elements.push_back(n+2);
} else {
elements.push_back(n+0); elements.push_back(n+2); elements.push_back(n+1);
elements.push_back(n+1); elements.push_back(n+2); elements.push_back(n+3);
}
n += 4;
}

skip: dir *= -1; } while(dir > 0); }
}
}


And here are the two helper functions.

bool Inside(ivec3 Position, ivec3 Min, ivec3 Max)
{
if(Position.x < Min.x || Position.y < Min.y || Position.z < Min.z) return false;
if(Position.x > Max.x || Position.y > Max.y || Position.z > Max.z) return false;
return true;
}

ivec3 Shift(int Dimension, ivec3 Vector)
{
if      (Dimension % 3 == 1) return ivec3(Vector.z, Vector.x, Vector.y);
else if (Dimension % 3 == 2) return ivec3(Vector.y, Vector.z, Vector.x);
else                         return Vector;
}


As you can see, the algorithm uses a goto statement to skip faces which adjacent blocks first, are inside the world bounds and second, are not filled with air. Those faces shouldn't be generated since they are not visible to the player.

How can I restructure the statement to not use goto anymore?

• I'm confused, I may be missing something here but why did you feel you needed the goto in the first place? I see only one use and its use precedes the block it is skipping. Couldn't you just combine the logic that determines the goto and use it as the if condition for the block? – Jeff Mercado May 20 '13 at 13:50
• I don't know how that should be done. It is important that the algorithm checks if the block is inside the world first, because otherwise the following look up in the data array would be out of range. – danijar May 20 '13 at 22:35

I may be missing some deep reason here, but it looks like you've got an if-condition that already does exactly what you need, except that you're using it to feed a GOTO instead of to (not) execute the defined code block.... Shouldn't you do something like:

if (!(Inside(neigh, ivec3(0), ivec3(SIZE)-1) && data[neigh.x][neigh.y][neigh.z]))
{
...
}

• Thanks. I wasn't sure if the second condition is guaranteed to not get evaluated if the first condition is false. But I found out. – danijar May 21 '13 at 18:31

First of all, the way you're formatting your code is horribly confusing.

if(Inside(neigh, ivec3(0), ivec3(SIZE) - 1))
if(data[neigh.x][neigh.y][neigh.z])
goto skip;

{
...
}


The block here looks a lot like it's in the if condition but it's not (it's just a C-like block without any condition attached to it). I really suggest using braces for your ifs to avoid confusion. Another confusing part is for(int dim = 0; dim < 3; ++dim) { int dir = -1; do {: when I see a for loop, I don't expect to see another loop at the end of it.

Now, about your question. Some languages (such as Java) support naming loop, which allows you to break to outer loops. This doesn't exist in C++, and the best option is to use a goto.

• The code formatting is necessary. Without that isolated code block the goto statement throws compiler warnings since variable declarations could be skipped. The for loop with nested do while iterates over all six sides of a cube. Can't I get rid of the nested conditionals at all? – danijar May 21 '13 at 8:47
• I'm not against the isolated block, but you should also put braces around the two ifs. I don't think there's an easy way to avoid the conditionals, no. (Well of course you can put them together: if(A && B)). – Quentin Pradet May 21 '13 at 8:57
• Is there anything against putting them together? I just asked another question whether the second condition could be evaluated even if the first resolved to false. Because that would cause and out of bounds error. – danijar May 21 '13 at 9:09