Level of detail on meshes (part 24)

When we look at the terrain we're adding our level of detail on the GPU.

I've applied a similar technique in the space colonization write-up I did last year to generate tree models. There we start with a basic cube based mesh and increase the LOD on the GPU as well. The result is a nice subdivided mesh but it is a technique only really suitable for organic shapes as the end result is a nicely rounded model. Also when we look at models with a lot of small details you may only wish to have those details rendered when the model is close enough to the viewer.

For our example today we're again going to use a tree but this time one that is pre-rendered at two different levels of detail and we'll introduce a third level of detail through a technique called billboarding. We'll then use these to render a whole forest. Well, a bunch of trees anyway as we still have a way to go to remove overhead in rendering things we shouldn't render. Still I went from 5 fps rendering all 1000 trees at full LOD back to 60 fps rendering all the trees with our LOD checks in place so. The goal however is to render loads more trees.

The basis of the LOD system is to have multiple versions of the same mesh at different levels of detail and choose which one to render based on the distance between the object and the camera. We're going to implement our LOD on the nodes we introduced in part 21. This allows us to do the LOD switching on a node and render multiple related meshes. In our case there will be two, one for the tree and one for the leaves but the system would allow us to make further LOD choices on the details using the highest definition main mesh but bringing in more detail when it comes closer. Think of a high level mesh for a car but having the interior only defined when we're really close to the camera.

Our structure for a single instance of a tree will be something like this:
- Tree_[n], firstVisOnly => true
  - TreeLod1, maxDist = 5000.0
    - Hidef tree trunc mesh
    - Hidef leaves mesh
  - TreeLod2, maxDist = 15000.0
    - Lodef tree trunc mesh
    - Lodef leaves mesh
  - TreeLod3, maxDist = 0 (0 = unlimited)
    - Billboard

On our container node we turn a new property "firstVisOnly" to true which means it will only render the first child of this node deemed visible.
Then each child node has a maxDist, the TreeLod1 will be rendered if we're less then 5000.0 units from the camera, TreeLod2 if we're less then 15000.0 units from the camera, else TreeLod3 is rendered.

Note that the first two levels of detail are loaded as meshes but the third we're going to generate in our engine so yes, I'm sneaking a render to texture into this write-up !!

As always however, we've got a few things to do before we can get into this.

Small changes to our materials library

There are a few small changes to our materials library.

The first is that our matSelectProgram now returns a boolean. If we can't setup our shader it's likely we won't be able to in subsequent renders so I wanted to return a false so we can stop rendering meshes that fail to render due to an issue on its material and not fill the logs with copies of the same error message.

The second is the introduction of a new variable called twoSided which basically turns off our backface culling. This does need some more work as the shaders need to be adjusted but it will do for now.

The third is a tiny change that we now communicate our ambient value and store that into our lightSource structure. Note that for this we've also added retrieving our uniform id for our ambient factor in our shader code.

And the last is one that has a lot of impact for such a simple thing and that is that we turn our diffuse maps into mipmaps when loading our materials file. Again this could use a bit more intelligence as we could have textures with mipmaps already baked in. We'll discuss mipmaps in a bit more detail later on.

Small changes to our mesh library

Our mesh library has a few small changes as well.

Deceptively small I've enhanced the solution we added last part to render between triangles and patches to also add rendering lines. We won't be using that yet in this part but it'll be very handy in our next part. As a result some of the methods that generate meshes now have a parameter to state if we want lines, triangles or quads. We also have an meshAddLine for adding lines to our mesh.

For this part however I've added meshAddVT which is a method that works the same way as meshAddVertex but instead of taking a vertex, it takes its individual components i.e. a positional vector, a normal and a texture coords.  We'll be using it to create our bill board mesh.

Adding the LOD functionality to our mesh library

Okay, now it's time to get into the thick of things. As per our introduction up above we've added two new variables to our meshnode structure:
- firstVisOnly, defines we're only going to render the first child node that is deemed visible
- maxDist, defines the maximum distance from the camera before the mesh is no longer visible

Our main logic all happens in meshNodeBuildRenderList which builds our arrays of meshes to be rendered from our nodes. Other then some of the parameters now being defined as constant for safety we have one new parameter which passes the coordinates of the camera.

We also now return true or false depending on whether the node was added to our render list.

Let's have a closer look at this method:

// build our no-alpha and alpha render lists based on the contents of our node
bool meshNodeBuildRenderList(const meshNode * pNode, const mat4 * pModel, const vec3 * pEye, dynarray * pNoAlpha, dynarray * pAlpha) {
  mat4 model;
  
  // is there anything to do?
  if (pNode == NULL) {
    return false;
  } else if (pNode->visible == false) {
    return false;
  };
  
  // make our model matrix
  mat4Copy(&model, pModel);
  mat4Multiply(&model, &pNode->position);

So far nothing much has changed, we return false if our node is not initialized or marked as invisible an add our model matrix to our parents matrix.

  // check our distance
  if (pNode->maxDist > 0) {
    float distance;
    vec3  pos;

    // first get our position from our model matrix
    vec3Set(&pos, model.m[3][0], model.m[3][1], model.m[3][2]);

    // subtract our camera position to get our relative position
    vec3Sub(&pos, pEye);

    // and get our distance
    distance = vec3Lenght(&pos);

    if (distance > pNode->maxDist) {
      return false;
    };
  };

So this is our main distance check, we grab our position from our model matrix and subtract the position of our camera. We then calculate the distance and compare this to our maximum distance. We skip the whole check if no maximum distance is set.

  if (pNode->mesh != NULL) {
    if (pNode->mesh->visible == false) {
      return false;
    };

    // add our mesh
    renderMesh render;
    render.mesh = pNode->mesh;
    mat4Copy(&render.model, &model);
    render.z = 0.0; // not yet used, need to apply view matrix to calculate
    
    if (pNode->mesh->material == NULL) {
      dynArrayPush(pNoAlpha, &render); // this copies our structure
    } else if (pNode->mesh->material->alpha != 1.0) {
      dynArrayPush(pAlpha, &render); // this copies our structure      
    } else {
      dynArrayPush(pNoAlpha, &render); // this copies our structure      
    };
  };

This bit remains the same, we just add our mesh to either our non-alpha or alpha array.

  if (pNode->children != NULL) {
    llistNode * node = pNode->children->first;
    
    while (node != NULL) {
      bool visible = meshNodeBuildRenderList((meshNode *) node->data, &model, pEye, pNoAlpha, pAlpha);

      if (pNode->firstVisOnly && visible) {
        // we've rendered our first visible child, ignore the rest!
        node = NULL;
      } else {
        node = node->next;
      };
    };
  };

  return true;
};

Finally in this last part we recursively call our function for our child nodes but we now have the added check that if a node has resulted in meshes being added and our firstVisOnly variable is set, we do not evaluate the rest of the children and exit.

Loading our trees

I'm going to leave the render to texture and bill-board till last (I'm tempted to split this article in two to keep the size down) so let's have a look at our changes in engine.c.

Just to keep the logic more readable I've moved the code loading and positioning our tie-bombers into a function and created a new function called addTrees to add our trees into our scene.

Before we get to our trees however you'll notice another small change and that is that I no longer discard our height field and I keep a pointer to it. I've added a method called getHeight that allows me to retrieve a height value from our map. For this a color lookup has been added to our texture library which for now assumes our data is filled with standard 32bit RGBA values.

I'll be using this function for placing our trees but I'm also using it in our engine_update to ensure that we don't move our camera through the ground.

Another small change is that I'm checking for an 'i' keypress to switch the text we're rendering on/off. Nice little touch as it's just debug info.

So in our addTrees function we're loading our two tree meshes. These btw where generated using the sapling blender plugin so they aren't particularly great meshes but they will do. For a real forest you'd probably have models of a number of different trees to create some diversity.

The loading code for the two meshes is pretty much the same so I'll just show the code for the first one below:

  // load our tree obj files
  text = loadFile(pModelPath, "TreeLOD1.obj");
  if (text != NULL) {
    llist *       meshes = newMeshList();

    // just scale it up a bit
    mat4Identity(&adjust);
    mat4Scale(&adjust, vec3Set(&tmpvector, 40.0, 40.0, 40.0));

    // parse our object file
    meshParseObj(text, meshes, materials, &adjust);

    // and package as a tree node
    treeLod1 = newMeshNode("treeLod1");
    treeLod1->maxDist = 5000.0;
    meshNodeAddChildren(treeLod1, meshes); 

    // and free up what we no longer need
    llistFree(meshes);
    free(text);
  };

So nothing much different here from how we loaded our tie-bomber with the exception that we're setting our maxDist on our node. The tree loaded looks a little like this:

Our second level of detail is the same, we just load a different mesh and change our distance. This tree has much less detail and only 1/4th the number of leaves:

Finally our third level of detail we generate by rendering to a texture and presenting it as a billboard. We'll skip that right now and come back to this later but the end result looks like this:

There is definitely room for improvement here but as it's only rendered when very far away, we don't care as much and it is a really cheap way to get lots of assets rendered in the background.

All that is left now is adding all the trees and we do that in a loop where we randomly place our trees. I'm not doing any checks to rule out trees places too close to others, just keeping it simple:

  // add some trees
  for (i = 0; i < 1000; i++) {
    meshNode * tree;
    char       nodeName[100];

    // create our node
    sprintf(nodeName, "tree_%d", i);
    tree = newMeshNode(nodeName);
    tree->firstVisOnly = true; // only render the highest LOD

    // add our subnodes
    if (treeLod1 != NULL) {
      meshNodeAddChild(tree, treeLod1);
    };
    if (treeLod2 != NULL) {
      meshNodeAddChild(tree, treeLod2);
    };
    if (treeLod3 != NULL) {
      meshNodeAddChild(tree, treeLod3);
    };

    // position our node
    tmpvector.x = randomF(-30000.0, 30000.0);
    tmpvector.z = randomF(-30000.0, 30000.0);
    tmpvector.y = getHeight(tmpvector.x, tmpvector.z) - 15.0;

    mat4Translate(&tree->position, &tmpvector);

    // and add to our scene
    meshNodeAddChild(scene, tree);

    meshNodeRelease(tree);
  };

So we loop 1000 times to create 1000 instances of our trees, inside our loop we:

• create a new meshnode, 
• set firstVisOnly to true
• add our 3 levels of details nodes as child nodes
• randomly position our tree and obtain the Y by looking up the height of our heightmap
• and add the new node to our scene after which we can release it as our scene retains it

Finally at the end of this method we release our three LOD nodes as they are now retained by all our instance nodes.

And here is our end result:

Okay, I think that is already way to much info, I am going to split this writeup in two. All the code including creating the bill boards is already on my GitHub page but I'll be continueing with the second half of this write-up later in the weekend.

So, to be continued...