Planet terrain not connecting properly

Question

I'm trying to generate some simple planets in OpenGL using libnoise (including noiseutils), but the terrain is not correctly connecting where the sphere "completes itself" and I was wondering if someone could explain to me why this is happening and/or point me in the direction to solving this little problem.

I'm generating spheres with a slightly adapted version of this algorithm, with this being my full code:

static void GenerateSphere( VertexBuffer& vertices, IndexBuffer32& indices, uint rings, uint sectors, float radius, const HeightModule* heights )
{
    static const double pi   = glm::pi<double>();
    static const double pi_2 = glm::half_pi<double>();

    // texture-coordinate conversion helpers
    const float rr = 1.0f / float( rings   - 1 );
    const float ss = 1.0f / float( sectors - 1 );

    // clear buffers
    vertices.Clear();
    indices.Clear();

    // iterate through each ring and sector to create the vertices
    float height = 0;
    Vertex v;
    for ( uint r = 0; r < rings; ++r )
    {
        for ( uint s = 0; s < sectors; ++s )
        {
            // calculate point
            glm::vec3 point(
                float( cos( 2 * pi * s * ss ) * sin( pi * r * rr ) ),
                float( sin( -pi_2 + pi * r * rr ) ),
                float( sin( 2 * pi * s * ss ) * sin( pi * r * rr ) )
            );

            // set vertex data
            height = radius + heights->GetHeight( s, r );
            v.TexCoord = glm::vec2( s * ss, r * rr );
            v.Normal   = point;
            v.Position = point * height;
            vertices.Add( v );

            // set index data
            indices.Add( r * sectors + s );
            indices.Add( r * sectors + ( s + 1 ) );
            indices.Add( ( r + 1 ) * sectors + ( s + 1 ) );
            indices.Add( ( r + 1 ) * sectors + s );
        }
    }
}

VertexBuffer and IndexBuffer32 are simple wrappers for their OpenGL counterparts, and HeightModule is a wrapper for some libnoise and noiseutils functions (like NoiseMap, NoiseMapBuilderSphere, and some noise modules).

To illustrate what I mean by heights not matching where the sphere "completes itself," here is a screenshot:

As you can see on the left, the vertices do not quite reach each other (it's like this all the way from pole to pole) and the texture coordinates are messed up on the connecting lines. The blue line you see on the right extends from the origin all the way to the north pole, and after some debugging I've found that all of the vertices generated when r == 0 are the same with the position being [0,-radius,0] and the normal being [0,-1,0] (the texture coordinates appear to the correct though, as they all differ). I suspect the terrain problem is caused by this, but I have no clue how I would go about fixing that.

Answer 1

The algorithm you referenced is horribly broken. It is not clear why it hasn't been redacted.

There are multiple issues here, but basically you need to generate the right set of vertices and connect them properly.

You generate rings*sectors different vertices. This is incorrect. You should have rings*sectors+2. When r = 0, sin( pi * r * rr ) = 0, and sin( -pi_2 + pi * r * rr ) = sin(-pi/2) = -1. Thus you generate sectors many vertices at the south pole. Instead, you need to start r=1 in your loop. This means you will have one ring less in your mesh, but that one ring was actually a pole. The rings variable now means the number of rings of faces in the mesh, not the number of vertex rings. The line going to the north pole comes from the fact that you never generate a north pole vertex, because of the loop test such that r never becomes rings (only rings-1), and so r * rr is never 1.0f.

The mismatch comes from the fact that you reference vertices which you never set. We have already seen that the number of vertices is rings*sectors. Thus valid indices are 0...rings*sectors-1. On the iteration r=rings-1 and s=sectors-1, you add an index ( r + 1 ) * sectors + ( s + 1 ) = rings*sectors+sectors, which is clearly out of bounds.

The Fix

Split your code into two loops. The first generates the vertices, and the second generates the indices. The first should look like:

auto addpoint = [&](uint r, uint s) {
        glm::vec3 point(
            float( cos( 2 * pi * s * ss ) * sin( pi * r * rr ) ),
            float( sin( -pi_2 + pi * r * rr ) ),
            float( sin( 2 * pi * s * ss ) * sin( pi * r * rr ) )
        );

        // set vertex data
        height = radius + heights->GetHeight( s, r );
        v.TexCoord = glm::vec2( s * ss, r * rr );
        v.Normal   = point;
        v.Position = point * height;
        vertices.Add( v );
}; 
for ( uint r = 1; r < rings; ++r )
{
    for ( uint s = 0; s < sectors; ++s )
    {
        addpoint(r,s);
    }
}
addpoint(0,0); // south pole
addpoint(rings, 0); //north pole

This generates the rings in indices [0, (rings-1)*sectors), and the south and north pole at (rings-1)*sectors and (rings-1)*sectors+1. Now we need to generate the indices for triangles in three parts: those around the south pole, those in the regular rings, and those around the north pole.

auto getindex = [&](uint r, uint s) -> uint {
    if(r == 0) return (rings-1)*sectors;
    if(r == rings) return (rings-1)*sectors + 1;
    if(s == sectors) return (r-1) * sectors;
    return (r-1) * sectors + s;
};

Acceptable arguments for getindex are [0,rings] and [0, sectors], with "ring 0" being the south pole, "ring rings" being the north pole. Note also that the indices for ring 1 are [0,sectors), so we need r-1. Note that the sphere wraps on itself, so that getindex(r, 0) == getindex(r, sectors). That is, if we go all the way around the sphere, we get back to the same exact point, so we use the same index. Now our index generation is straightforward:

for(uint r = 0; r < rings; r++)
    for(uint s = 0; s < sectors; s++) {
         if(r != rings-1) {
             indices.Add(getindex(r,s));
             indices.Add(getindex(r+1,s));
             indices.Add(getindex(r+1,s+1));
         }
         if (r != 0) {
             indices.Add(getindex(r+1,s+1));
             indices.Add(getindex(r,s+1));
             indices.Add(getindex(r,s));
         }
}

(Use triangles. Quads are obsolete.)

This needs some explanation. First, we went back to starting r at zero. Now we have rings horizontal loops of triangles, so we will need r to take on rings many values. Further, we need to pass the values zero through rings, inclusive, to getindex to connect something to all the vertices we defined. We do that by letting r represent the lower of the two vertex rings we are connecting on each iteration. s then represents where we are within each ring. Note because of the test in getindex, when s = sectors-1 we connect the last vertices at the end of the ring back to the first ones, ensuring no gaps.

Second, we have these crazy if's. Around the poles, we do not need quads. Because the pole is a single point, we can just connect each pair in ring 1 to the pole with a single triangle. We see in the second if that the triangle is getindex applied to (r+1,s+1), (r,s+1), and (r,s). For most rings, this is one half of the quad. For the bottom ring, when r = 0, (r,s+1) and (r,s) are the same vertex: the south pole. We can see that if r = 0, then getindex always returns the same thing, regardless of s. So in the bottom ring this triangle is degenerate, we might as well not generate it. The same logic holds for the other if: those triangles will be degenerate on the last ring, near the north pole.

It is possible to rewrite this code to generate a triangle strip, but I won't derive that here.