OpenGL Programming/Glescraft 1

A voxel world.

Introduction edit

The processing power available in present day CPUs and GPUs allows one to render a 3D world composed completely of small cubes. Some well-known games that do this are Minecraft (which in turn is inspired by Infiniminer) and Voxatron. Apart from the distinct look this gives those games, restricting oneself to cubes on a grid allows for a lot of simplifications. In this tutorial series, we will see how we can manage a vast number of cubes and how we can draw them very efficiently.

Chunks edit

The first important thing to do is to subdivide the voxel world we want to render into manageable chunks. This way, we can decide which chunks are visible on the screen, and skip rendering invisible chunks. We can also manage memory resources this way; we don't need to keep vertex buffer objects for invisible chunks in GPU memory, for example. But chunks should be large enough that we don't spend most of our time keeping track of them. Let's make the size of a chunk configurable, but start with relatively small chunks of 16x16x16 (4096) blocks. We will use a byte to store the type of a block. A struct that represents such a chunk will look like this:

#define CX 16
#define CY 16
#define CZ 16

struct chunk {
  uint8_t blk[CX][CY][CZ];
  GLuint vbo;
  int elements;
  bool changed;

  chunk() {
    memset(blk, 0, sizeof(blk));
    elements = 0;
    changed = true;
    glGenBuffers(1, &vbo);
  }

  ~chunk() {
    glDeleteBuffers(1, &vbo);
  }

  uint8_t get(int x, int y, int z) {
    return blk[x][y][z];
  }

  void set(int x, int y, int z, uint8_t type) {
    blk[x][y][z] = type;
    changed = true;
  }

  void update() {
    changed = false;
    // Fill in the VBO here
  }

  void render() {
    if(changed)
      update();
    // Render the VBO here
  }
};

The blk array will hold the block types. The get() and set() functions are rather trivial, but will come in handy later. When the set() functions is called, the changed flag is set to true. When the chunk is being rendered and the contents have changed, this will trigger a call to the update() function which will update the Vertex Buffer Object (VBO). This process of turning voxel data into a polygon mesh filling the VBO is called meshing; advanced algorithms are known as Isosurface Extraction. See 0fps Smooth Voxel Terrain for more details.

Only 4 bytes per vertex edit

In the other tutorials, we used GLfloat coordinates for vertices, texture coordinates, colors, et cetera. OpenGL allows us to use other types as well. In our voxel world, all cubes have the same dimensions. It follows then that we can use integers to represent coordinates. Even though the world can be infinite, within one chunk, we only need very small integers to represent all possible coordinates. If we use GLbytes, we can have coordinates ranging from -128 to +127, more than enough for our 16x16x16 chunks!

We can use vectors of up to four components in the shaders, so apart from our x, y and z coordinates, we can add another byte of information. We will store the type of the block in this "coordinate". In a later tutorial, we will use this to derive texture coordinates, but for now we can use it to give each type its own color.

With only 4 bytes per vertex, using an IBO does not give a lot of benefits anymore. When we give each face of a cube a distinct color or texture, using an IBO will actually increase memory usage.

Exercises:

  • Why can we not use GL_BYTE for IBO indices to render our chunk?
  • Calculate the memory it takes to render one cube, with and without using a IBO, and with and without using separate colors for each face.

Filling in the VBO edit

We will be working with a 4-dimensional vector of bytes. Unfortunately, there is no pre-defined type for that available, but GLM allows us to quickly create one that works the same as its other vector types:

typedef glm::tvec4<GLbyte> byte4;

Now we can create an array large enough to hold all the vertices, and fill them in. You should already know how to make a cube. If we put the vertices in the right order, we can use glEnable(GL_CULL_FACE) to avoid drawing the interior faces of the cube.

void update() {
  changed = false;

  byte4 vertex[CX * CY * CZ * 6 * 6];
  int i = 0;

  for(int x = 0; x < CX; x++) {
    for(int y = 0; y < CY; y++) {
      for(int z = 0; z < CZ; z++) {
        uint8_t type = blk[x][y][z];

        // Empty block?
        if(!type)
          continue;

        // View from negative x
        vertex[i++] = byte4(x,     y,     z,     type);        
        vertex[i++] = byte4(x,     y,     z + 1, type);        
        vertex[i++] = byte4(x,     y + 1, z,     type);        
        vertex[i++] = byte4(x,     y + 1, z,     type);        
        vertex[i++] = byte4(x,     y,     z + 1, type);        
        vertex[i++] = byte4(x,     y + 1, z + 1, type);        

        // View from positive x
        vertex[i++] = byte4(x + 1, y,     z,     type);        
        vertex[i++] = byte4(x + 1, y + 1, z,     type);        
        vertex[i++] = byte4(x + 1, y,     z + 1, type);        
        vertex[i++] = byte4(x + 1, y + 1, z,     type);        
        vertex[i++] = byte4(x + 1, y + 1, z + 1, type);        
        vertex[i++] = byte4(x + 1, y    , z + 1, type);        

        // Repeat for +y, -y, +z, and -z directions
        ...
      }
    }
  }

  elements = i;
  glBindBuffer(GL_ARRAY_BUFFER, vbo);
  glBufferData(GL_ARRAY_BUFFER, elements * sizeof *vertex, vertex, GL_STATIC_DRAW);
}

Exercises:

  • Write the code to create the vertices of the faces in the y and z directions.
  • It is quite tedious to write code for each of the six faces. Can you think of a better way to do this?

Shaders edit

Before we can draw anything, here are the shaders that are necessary to draw our voxels. First, the vertex shader:

#version 120

attribute vec4 coord;
uniform mat4 mvp;
varying vec4 texcoord;

void main(void) {
        texcoord = coord;
        gl_Position = mvp * vec4(coord.xyz, 1);
}

Vertices enter the vertex shader through the attribute coord. You should create a model-view-projection matrix which is passed as the uniform mvp. The vertex shader will pass the input coordinates unaltered to the fragment shader through the varying texcoord. A basic fragment shader looks like this:

#version 120

varying vec4 texcoord;

void main(void) {
  gl_FragColor = vec4(texcoord.w / 128.0, texcoord.w / 256.0, texcoord.w / 512.0, 1.0);
}

Remember that we use GL_BYTEs, so the "w" coordinate is in the range 0..255. OpenGL does not magically map this to the range 0..1, so we have to divide it to get usable values for the fragment color.

Exercises:

  • Do these shaders only work with our byte4 vertices?

Rendering the chunk edit

Rendering a whole chunk is now very easy. We just point the graphics card to our VBO, and let it draw all the triangles:

void render() {
  if(changed)
    update();

  // If this chunk is empty, we don't need to draw anything.
  if(!elements)
    return;

  glEnable(GL_CULL_FACE);
  glEnable(GL_DEPTH_TEST);

  glBindBuffer(GL_ARRAY_BUFFER, vbo);
  glVertexAttribPointer(attribute_coord, 4, GL_BYTE, GL_FALSE, 0, 0);
  glDrawArrays(GL_TRIANGLES, 0, elements);
}

Exercises:

  • Create a chunk, set() blocks to random values, position a camera, and render it.
  • Put the camera inside the chunk. Try turning GL_CULL_FACE on and off.

Many chunks edit

Now that we know how to draw one chunk, we want to draw lots of them. There are many ways to manage a collection of chunks; you could just have a three-dimensional array of chunks, or an octree structure, or you could have a database that holds any chunks you have. For example, Minecraft used to stores chunks on the harddisk, with the coordinates of the chunks encoded in the filenames, basically using the filesystem as a database.

Let's create a "superchunk", which basically is a three-dimensional array of pointers to normal chunks. Very naively, it would look like this:

#define SCX 16
#define SCY 16
#define SCZ 16

struct superchunk {
  chunk *c[SCX][SCY][SCZ];

  superchunk() {
    memset(c, 0, sizeof c);
  }

  ~superchunk() {
    for(int x = 0; x < SCX; x++)
      for(int y = 0; y < SCX; y++)
        for(int z = 0; z < SCX; z++)
          delete c[x][y][z];
  }

  uint8_t get(int x, int y, int z) {
    int cx = x / CX;
    int cy = y / CY;
    int cz = z / CZ;

    x %= CX;
    y %= CY;
    z %= CZ;

    if(!c[cx][cy][cz])
      return 0;
    else
      return c[cx][cy][cz]->get(x, y, z);
  }

  void set(int x, int y, int z, uint8_t type) {
    int cx = x / CX;
    int cy = y / CY;
    int cz = z / CZ;

    x %= CX;
    y %= CY;
    z %= CZ;

    if(!c[cx][cy][cz])
      c[cx][cy][cz] = new chunk();

    c[cx][cy][cz]->set(x, y, z, type);
  }

  void render() {
    for(int x = 0; x < SCX; x++)
      for(int y = 0; y < SCY; y++)
        for(int z = 0; z < SCZ; z++)
          if(c[x][y][z])
            c[x][y][z]->render();
  }
};

Basically, a superchunk also implements the get(), set() and render() functions that a normal chunk has, and delegates those functions to the appropriate chunk(s). The render() function in the above example lacks an important feature: it should change the model matrix before rendering each chunk, so that they are translated to the correct positions, otherwise they would all be drawn on top of each other:

          if(c[x][y][z]) {
            glm::mat4 model = glm::translate(glm::mat4(1), glm::vec3(x * CX, y * CY, z * CZ));
            // calculate the full MVP matrix here and pass it to the vertex shader
            c[x][y][z]->render();
          }

Exercises:

  • Create a superchunk, set() blocks to random values, position a camera, and render it.
  • Create a landscape by calculating height for every x,z coordinate using Perlin noise or Simplex noise (use GLM's glm::simplex() function for example).
  • Find out what the total surface area of the Earth is. If our voxels are 1 cubic meter, how many voxels do you need to cover the Earth? Using only one byte per voxel, would this fit on your computer's harddisk?

< OpenGL Programming

Browse & download complete code