Recursive subdivision on octahedron in OpenGL

Question

I have been referring to this post Drawing Sphere in OpenGL without using gluSphere()? which has helped me quite a lot but i'm stumped now.

I have an octahedron in my scene and I would now like to recursively subdivide the triangles to create a sphere. I found this block of code which is supposed to carry out the subdivision for me but I don't understand it fully

void subdivide(GLfloat v1[3], GLfloat v2[3], GLfloat v3[3], int depth)
{
    GLfloat v12[3], v23[3], v31[3]; int i;
    if (depth == 0) {
    drawTriangle(v1, v2, v3);
    return;
}
for (i = 0; i < 3; i++) 
{
    v12[i] = (v1[i]+v2[i])/2.0;
    v23[i] = (v2[i]+v3[i])/2.0;
    v31[i] = (v3[i]+v1[i])/2.0;
}

I set up a struct to hold a position, normal and a color

// simple vertex container
struct SimpleVertex
{
    vec3        pos;    // Position
    vec3        normal  // Normal
    vec4        colour; // Colour
};

and this is where I set up my vertices

 /*
    *
    * This is just one triangle form my octahedron
    *
    */
     static void createVertexBuffer()
        {
            // Create some vertices to put in our VBO.
            // Create vertex buffer
            SimpleVertex vertices[] =

            {
                // Side 1 Front
                { vec3(0.0f, 1.0f, 1.0f), vec3(0.0f, 0.0f, 1.0f), vec4(1.0f, 0.0f, 0.0f, 1.0f) },
                { vec3(-1.0f, 0.0f, 0.0f), vec3(0.0f, 0.0f, 1.0f), vec4(0.0f, 1.0f, 0.0f, 1.0f) },
                { vec3(1.0f, 0.0f, 0.0f), vec3(0.0f, 0.0f, 1.0f), vec4(0.0f, 0.0f, 1.0f, 1.0f) },
            }
        }

If anyone could explain how I could use the method above to subdivide my triangles, i'd appreciate it.

Answer 1

The recursive subdivision itself is fairly straightforward, and you have parts of it already. Taking one triangle of the octahedron, we seed the recursive calls by passing the coordinates of the full triangle to the recursive function, together with the desired subdivision level (something in the range of 3 to 5 will give reasonable spheres):

subdivide(1.0f, 0.0f, 0.0f,
          0.0f, 1.0f, 0.0f,
          0.0f, 0.0f, 1.0f,
          LEVEL_COUNT);

Then, in the recursive function, we first check if we reached level 0, in which case we have a final triangle. Otherwise we split the triangle into 4, and make the recursive call for each of them. The vertices of the 4 sub-triangles are formed from the original triangle vertices and the middle of their edges, based on the diagrams you already found:

      v3
     /  \
    /    \
  v13----v23
  /  \  /  \
 /    \/    \
v1----v12---v2

The recursive function then looks like this:

void subdivide(float v1x, float v1y, float v1z,
               float v2x, float v2y, float v2z,
               float v3x, float v3y, float v3z,
               int level) {
    if (level == 0) {
        // Reached desired tessellation level, emit triangle.
        drawTriangle(v1x, v1y, v1z,
                     v2x, v2y, v2z,
                     v3x, v3y, v3z);
    } else {
        // Calculate middle of first edge...
        float v12x = 0.5f * (v1x + v2x);
        float v12y = 0.5f * (v1y + v2y);
        float v12z = 0.5f * (v1z + v2z);
        // ... and renormalize it to get a point on the sphere.
        float s = 1.0f / sqrt(v12x * v12x + v12y * v12y + v12z * v12z);
        v12x *= s;
        v12y *= s;
        v12z *= s;

        // Same thing for the middle of the other two edges.
        float v13x = 0.5f * (v1x + v3x);
        float v13y = 0.5f * (v1y + v3y);
        float v13z = 0.5f * (v1z + v3z);
        float s = 1.0f / sqrt(v13x * v13x + v13y * v13y + v13z * v13z);
        v13x *= s;
        v13y *= s;
        v13z *= s;

        float v23x = 0.5f * (v2x + v3x);
        float v23y = 0.5f * (v2y + v3y);
        float v23z = 0.5f * (v2z + v3z);
        float s = 1.0f / sqrt(v23x * v23x + v23y * v23y + v23z * v23z);
        v23x *= s;
        v23y *= s;
        v23z *= s;

        // Make the recursive calls.
        subdivide(v1x, v1y, v1z,
                  v12x, v12y, v12z,
                  v13x, v13y, v13z,
                  level - 1);
        subdivide(v12x, v12y, v12z,
                  v2x, v2y, v2z,
                  v23x, v23y, v23z,
                  level - 1);
        subdivide(v13x, v13y, v13z,
                  v23x, v23y, v23z,
                  v3x, v3y, v3z,
                  level - 1);
        subdivide(v12x, v12y, v12z,
                  v23x, v23y, v23z,
                  v13x, v13y, v13z,
                  level - 1);
    }
}

This gives you all the vertices you need. But it calculates each vertex of the tessellation multiple times. Where it gets slightly painful is if you want to calculate each vertex only once, and store them in a vertex buffer. To do that, you'll have to also pass indices to the recursive function, and do some math on those indices so that you can place each resulting vertex at a unique index. It gets even more cumbersome if you want nice triangle strips from all the resulting unique vertices.

Unfortunately all those details are somewhat beyond the scope of an answer here. But I hope that the above will at least clearly explain the underlying math and logic needed to do the actual subdivision.