Sometimes, the mesh you use has big triangles, and for increasing the quality of your rendering result you need to increase the tessellation. I faced with this issue while I was working on my Precomputed Ambient Occlusion for Animated Meshes project. For getting high quality AO results, I tessellated my meshes.

General idea of tessellation is simple. It is just an interpolation over all needed information for the new vertex points you create. But, giving correct index orders for newly generated faces, and interpolating the skinning weights (if you do skinning) in the right way might be problematic.

During the project, I used Studiomdl Data file format (SMD) for models, and animations. I send my triangles in clockwise order. For interpolating the values, I used linear interpolation, and interpolated vertex positions, normals, UV coordinates, and skinning weights.

Linear Interpolation is frequently used in computer graphics, and has a simple idea. Linear interpolation generates equal spacing between the interpolated values. Formula of linear interpolation can be seen below:

Since, for generating a new vertex in midpoint (halfway) of two existent vertices, I chose t as 0.5. So simply, I summed my values, and then divide by 2 (multiply by 0.5):

Interpolation of skinning weights follows the same fashion with some additional logic. But, I covered this in this page.

tessel-300x259

When the interpolation process is done, we have a new triangle like in the image above. So, by interpolating 3 existent vertices, we have 4 new, smaller triangles with 3 new vertices.

Now, for seeing the correct result, we need to send all vertices of the mesh in the correct order.

As I mentioned above, I used clockwise order. So, I sent the face indices in the order below:

For different orders (such as counter clockwise), you can adopt a similar idea.

Algorithm

  • Read original vertices
  • Interpolate the values
  • If not reached to tessellation limit, call yourself with triangle #1, #2, #3, and #4
  • If tessellation limit is reached, push faces in correct order