Recently, for a Computer Graphics project, I had to implement algorithms which tessellated four different shapes in C++. We were provided various classes that did vector math, transformations, and FLTK setup for us. The only thing we had to do was implement the algorithms to compute vertices and build triangles.

Below I will share the code and a description to those algorithms only. None of the code to the transformations or FLTK or vector math will be shared so if you want any of that stuff, you are on your own.

Tessellation

First, a description of what tessellation is and why one would want to do such a thing:

Computer’s are optimized for dealing with a certain kind of polygon for lighting, material, and effects calculations. Since all of these calculations are done at a vertex, it makes sense to want to maximize the number of vertices on an object without changing the look of an object. That is, we want a cube made up of triangles that still looks like a cube. Enter: tessellation.

Tessellation is a process by which you subdivide an object into a series of triangles. This has a two-fold effect, one being that more accurate lighting and material effects can be generated, and two that the object is optimized for graphics hardware.

There is a let-down though… the algorithm for doing this is only so efficient. To much of a tessellation factor means that you will now be spending more time and resources tessellating than return you get by optimizing it. So, it is important to declare particular constraints as a ceiling for your algorithms. I did not do this for my algorithms because the shapes are so basic(save for the sphere), but for more advanced objects you will want to do this.

Cube

The first task was to tessellate a cube in such a fashion that a single input argument defines the factor of tessellation on all 6 faces of the cube. Though my method is a bit longer, and there is likely definite ways to shorten up the code, it seems unlikely that it could be made any more optimized.

In any event, it will give you a slid jumping off point for your own optimizations:

http://pastebin.com/f606a97bc

Cylinder

After gaining a basic understanding of the math that needed to be done in 3D for shapes, the cylinder came much easier for me. Essentially, the algorithm creates the top and bottom meshes, keeping track of the circumference points around the outside. From there, it simply makes squares going up the sides of the cylinder.

http://pastebin.com/fb6478a8

Cone

The cone was a bit more difficult in theory because it changes the X, Y, and Z directions all at once. I was wrapped up with a bug that I missed because the X and Z directions must be changed independantly of one another for each face of the cone. The Y direction remains uniform throughout the shape.

The algorithm for the cone is very similar to the cylinder, save that it makes a bottom mesh and a top fixed point and then simply makes squares going up the sides, unless its the top in which is simply makes a triangle.

http://pastebin.com/f9bfd0f5

Sphere

The sphere was the hardest shape to do of the four. My approach was to build a icosahedron mesh by hand, and then subdivide it, normalize each vertex, and then add the triangles. It works okay, but there is a bug somewhere that I never found that over-tessellates it for each value of n about1. It still tessellates a sphere just fine, its just a little more of a tessellation factor than there should be for each increasing value of n.

http://pastebin.com/f3295336f

Conclusion

This was a fun project to work on, but quite difficult in theory.  Humans are well capable of seeing in 3D but thinking up the math for 3D calculations and positioning is quite abstract. Here is the code for the entire shape.cpp file:

http://pastebin.com/f5507d250

Remember, this holds none of the other math functions or FLTK setup you need… this is just the algorithms for straight tessellations. The rest is on you.