This is a simple tutorial of how to render planet using a triangle subdivision approach. The source is optimized for compactness and to make the algorithm easy to understand. The algorithm renders an icosahedron with 12 triangles, each of which is being sub-divided using a recursive function.

If you would render the planet in a game engine, you would have to render a triangle patch for NxN triangles with a VBO inside the draw_triangle function, rather than a single triangle with gl immediate mode.

The center of detail is where the camera would be in the game. The camera in the demo is above for demonstration purpose.

What the code is :

• A simple demo to show how a planet renderer with subdivision works
• As short as possible so you can experiment with the algorithm
• Easy to understand

What the code is not:

• A ready to use planet rendering library with shaders frustum culling etc
• A way to render a planet with best performance
• A demonstration of modern high performance gl rendering

https://github.com/sp4cerat/Planet-LOD

[attachment=31405:Animation.gif]

struct World
{
    static void draw_triangle(vec3f p1, vec3f p2, vec3f p3)
    {
        glPolygonMode(GL_FRONT_AND_BACK, GL_LINE);
        glBegin(GL_TRIANGLES);
        glVertex3f(p1.x, p1.y, p1.z);
        glVertex3f(p2.x, p2.y, p2.z);
        glVertex3f(p3.x, p3.y, p3.z);
        glEnd();
        glPolygonMode(GL_FRONT_AND_BACK, GL_FILL);
    }
    static void draw_recursive(vec3f p1,vec3f p2,vec3f p3, vec3f center , float size=1)
    {
        float ratio = gui.screen[0].slider["lod.ratio"].val; // default : 1
        float minsize = gui.screen[0].slider["detail"].val;  // default : 0.01
 
        double dot = double(((p1+p2+p3)/3).norm().dot(center));
        double dist = acos(clamp(dot, -1, 1)) / M_PI;
 
        if (dist > 0.5) return;//culling
 
        if (dist > double(ratio)*double(size) || size < minsize) 
        { 
            draw_triangle(p1, p2, p3); 
            return; 
        }
 
        // Recurse
        
        vec3f p[6] = { p1, p2, p3, (p1 + p2) / 2, (p2 + p3) / 2, (p3 + p1) / 2 };
        int idx[12] = { 0, 3, 5, 5, 3, 4, 3, 1, 4, 5, 4, 2 };
 
        loopi(0, 4)
        {
            draw_recursive(
                p[idx[3 * i + 0]].norm(), 
                p[idx[3 * i + 1]].norm(),
                p[idx[3 * i + 2]].norm(),
                center,size/2 );
        }
    }
    static void draw(vec3f center)
    {
        // create icosahedron
        float t = (1.0 + sqrt(5.0)) / 2.0;
 
        std::vector<vec3f> p({ 
            { -1, t, 0 }, { 1, t, 0 }, { -1, -t, 0 }, { 1, -t, 0 },
            { 0, -1, t }, { 0, 1, t }, { 0, -1, -t }, { 0, 1, -t },
            { t, 0, -1 }, { t, 0, 1 }, { -t, 0, -1 }, { -t, 0, 1 },
        });
        std::vector<int> idx({ 
            0, 11, 5, 0, 5, 1, 0, 1, 7, 0, 7, 10, 0, 10, 11,
            1, 5, 9, 5, 11, 4, 11, 10, 2, 10, 7, 6, 10, 7, 6, 7, 1, 8,
            3, 9, 4, 3, 4, 2, 3, 2, 6, 3, 6, 8, 3, 8, 9,
            4, 9, 5, 2, 4, 11, 6, 2, 10, 8, 6, 7, 9, 8, 1
        });
 
        loopi(0, idx.size() / 3)
        {
            draw_recursive(
                p[idx[i * 3 + 0]].norm(), // triangle point 1
                p[idx[i * 3 + 1]].norm(), // triangle point 2
                p[idx[i * 3 + 2]].norm(), // triangle point 3
                center);
        }
    }
};

it's a good start, you should give it a few more iterations.

1.there is a simpler way to tessellate to a sphere, starting with a tetrahedron (4 triangles) and halving the edges of the triangles at every step.
your tessellation has the classical t-junction issue, which usually takes the most code to fix. with tetrahedrons, when you evaluate per-edge, it's actually very simple to get a closed mesh.

2.usually you would increase the tessellation at the silhouette, not at the center (but that decision probably depends on a lot of factors)

Good point.

1. I just changed the algorithm to icosahedron. Now its just 69 lines of code and also a bit faster. The algorithm is now working for an arbitrary triangle mesh. You could also throw a custom 3DS MAX created mesh at it basically.

2. The Tessellation is intentionally in the center. In a common game, you would be walking on the planet surface, which is the point where the highest level of detail is in the demo. The actual camera in the demo is just for demonstration purpose, to have a better overview. If you want the most detail at the silhouette, that would be possible too, but you need to modify the recursion criteria to the following:

if (fabs(0.5-dist) > double(ratio)*double(size) || size < minsize)

The result is as follows

[attachment=31406:Clipboard01.png]

uint32_t edge0 = NeedSubdivide((V0+V1)/2);
uint32_t edge1 = NeedSubdivide((V1+V2)/2);
uint32_t edge2 = NeedSubdivide((V2+V0)/2);
switch(edge0|edge1<<1|edge2<<2)
{
case 0:
//no subdivision, spit out triangle
break;
case 1:
.
.
.
default:
//the way you subdivide now
}
(there is a way more elegant way to solve this,I won't spoil this puzzle :) )

				p[idx[3 * i + 0]].norm(), 
				p[idx[3 * i + 1]].norm(),
				p[idx[3 * i + 2]].norm(),

Thx for the tip :)

The edge idea was good.

Just adopted it to the code.

Your bezier and subdivision samples look nice. I wonder if its easy to make it to a recursive approach (looks like uniform subdivision in the screenshots)

For the planet thats not needed at the moment.

1. Yes, due to normalizing it does not work immediately for the current code, but you could use a displacement map and combine rendering with a tessellation shader.

2. Yes, fly though is in progress. First I needed some basic rendering code however. VBO is now already implemented and next is to find a good mapping for the heightmap to the surface. That will be another challenge to create a seamless heightmap that has same scaling all over the planet.

Results:

The new mesh now looks like the following:

[attachment=31411:Clipboard01.png]

Also using patches is possible right away without further meshes that fix LOD boundaries.

[attachment=31412:patches.png]

The new code looks like this:

static void draw_recursive(vec3f p1,vec3f p2,vec3f p3, vec3f center , float size=1)
{
    float ratio_size = size * gui.screen[0].slider["lod.ratio"].val; // default : 1
    float minsize = gui.screen[0].slider["detail"].val;    // default : 0.01
    vec3f edge_center[3] = { (p1 + p2) / 2, (p2 + p3) / 2, (p3 + p1) / 2 };
    bool edge_test[3]; double angle[3];
 
    loopi(0, 3)
    {
        double dot = edge_center[i].dot(center);
        angle[i] = acos(clamp(dot, -1, 1)) / M_PI;
        edge_test[i] = angle[i] > ratio_size;
    }
 
    if (min(angle[0], min(angle[1], angle[2])) > 0.5) return;//culling
 
    if ((edge_test[0] && edge_test[1] && edge_test[2]) || size < minsize)
    { 
        if (gui.screen[0].checkbox["patches"].checked)
            draw_patch(p1, p2, p3); 
        else
            draw_triangle(p1, p2, p3);
        return; 
    }
    // Recurse
    vec3f p[6] = { p1, p2, p3, edge_center[0], edge_center[1], edge_center[2] };
    int idx[12] = { 0, 3, 5,    5, 3, 4,    3, 1, 4,    5, 4, 2 };
    bool valid[4] = { 1, 1, 1, 1 };
 
    if (edge_test[0]){ p[3] = p1; valid[0] = 0; } // skip triangle 0 ?
    if (edge_test[1]){ p[4] = p2; valid[2] = 0; } // skip triangle 2 ?
    if (edge_test[2]){ p[5] = p3; valid[3] = 0; } // skip triangle 3 ?
 
    loopi(0, 4) if (valid[i])
    {
        draw_recursive(
            p[idx[3 * i + 0]].norm(), 
            p[idx[3 * i + 1]].norm(),
            p[idx[3 * i + 2]].norm(),
            center,size/2 );
    }        
}

This is really cool. You've distilled the process down further than I've ever attempted :)

Your bezier and subdivision samples look nice. I wonder if its easy to make it to a recursive approach (looks like uniform subdivision in the screenshots)

1. Yes, due to normalizing it does not work immediately for the current code, but you could use a displacement map and combine rendering with a tessellation shader.

@Krypt0n: Yes, mega meshes is indeed a very nice paper. I remember that one.

@rept_ai: Very nice Demo ! I will look at the source.

Just modified the rendering. Basically it works nice, but once you go up close then float precision is not enough. What is the best solution to that other than splitting the frustum in near / far ?

Seems I need to read

http://outerra.blogspot.de/2012/11/maximizing-depth-buffer-range-and.html

and

http://www.humus.name/Articles/Persson_CreatingVastGameWorlds.pdf

Edit: The Github code is updated and now also renders a planet with fractal texture+heightmap