Terrain Quadtree LOD cracks/t-junction

Question

I've implemented a basic terrain into my graphic engine with a quadtree and now I have a problem with fixing t-junction and cracks. First of all I'm using OpenGL 3.2 so I'm not able to use tesslation. Maybe I'll implement this feature in the nearest future. Basically I have a terrain object which stores a quadtree object and has a method called render:

/**
 * Render tile
 * @param program - shader program
 */
public void render(Camera camera, Shader program)
{
    if(camera.hasMoved())
        this.quadtree.updateQuadTree(camera);

    this.quadtree.render(program);
}

Then my quadtree object has four childrens called TerrainTreeNode and this method:

/**
 * Update quadtree
 * @param camera - camera
 */
public void updateQuadTree(Camera camera)
{
    for(Node node : getChildren())
        ((TerrainTreeNode) node).updateQuadtree(camera);
}

Then my TerrainTreeNode object has these methods:

/**
 * Update quad tree
 * @param camera - camera
 */
public void updateQuadtree(Camera camera)
{
    updateChildNodes(camera.position);

    for(Node node : getChildren())
    {
        ((TerrainTreeNode) node).updateQuadtree(camera);
    }
}

/**
 * Update child nodes
 * @param cameraPosition - camera position
 */
private void updateChildNodes(Vector3f cameraPosition)
{
    Vector3f tempCamera = new Vector3f(cameraPosition);
    Vector3f tempPosition = new Vector3f(this.position);
    Vector3f.sub(tempCamera, tempPosition, tempCamera);
    float distance = tempCamera.length();

    switch(this.lod)
    {
        case 0: 
            if(distance < 1750)
            {
                addChildNodes(this.lod+1);
            }
            else if(distance >= 1750)
            {
                removeChildNodes();
            }
            break;

        case 1: 
            if(distance < 874)
            {
                addChildNodes(this.lod+1);
            }
            else if(distance >= 874)
            {
                removeChildNodes();
            }
            break;

        case 2: 
            if(distance < 386)
            {
                addChildNodes(this.lod+1);
            }
            else if(distance >= 386)
            {
                removeChildNodes();
            }
            break;

        case 3: 
            if (distance < 192)
            {
                addChildNodes(this.lod+1);
            }
            else if(distance >= 192)
            {
                removeChildNodes();
            }
            break;

        case 4: 
            if(distance < 100)
            {
                addChildNodes(this.lod+1);
            }
            else if(distance >= 100)
            {
                removeChildNodes();
            }
            break;

        case 5: 
            if(distance < 50)
            {
                addChildNodes(this.lod+1);
            }
            else if(distance >= 50)
            {
                removeChildNodes();
            }
            break;

        case 6: 
            if(distance < 0)
            {
                addChildNodes(this.lod+1);
            }
            else if(distance >= 0)
            {
                removeChildNodes();
            }
            break;

        case 7: 
            if (distance < 0)
            {
                addChildNodes(this.lod+1);
            }
            else if(distance >= 0)
            {
                removeChildNodes();
            }
            break;
    }
}

/**
 * Add child nodes
 * @param lod - level of detail
 */
public void addChildNodes(int newLod)
{
    if(isLeaf)
    {
        isLeaf = false;
        if(this.mesh != null)
            this.mesh.dispose();
    }
    if(getChildren().size() == 0)
    {   
        float newWidth = this.width/2f;
        float newWidth2 = newWidth/2f;
        for(int i = 0; i < 2; i++)
        {
            for(int j = 0; j < 2; j++)
            {
                float first, second;
                if(i == 0)
                    first = -(newWidth/2f);
                else
                    first = newWidth/2f;
                if(j == 0)
                    second = -(newWidth/2f);
                else
                    second = newWidth/2f;

                Vector3f newPosition = new Vector3f(this.position.x+first, 
                        0f, this.position.z+second);
                addChild(new TerrainTreeNode(newPosition, 
                        newLod, 
                        new Vector2f(i, j), 
                        newWidth));
            }
        }
    }   
}

/**
 * Remove child nodes
 */
private void removeChildNodes()
{
    if(!isLeaf)
    {
        isLeaf = true;
        this.mesh = generateMesh();

    }
    //Remove childrends
    if(getChildren().size() != 0)
    {
        for(Node child : getChildren())
            child.dispose();

        getChildren().clear();
    }
}

As you can see if tree node has a very long distance from the camera then it removes childrens and creates own vao, in the opposite case it creates childrens and removes vao from memory. My vao uses triangle fan and it's looks like this:

1, 2, 4, 6, 8 and 10 vertices are always active, the others I want to turn on and off depends on neighbour level of detail to avoid this:

Algorithm should disactivated red vertices. How can I do this? How to find all vertices which are useless? This algorithm bases on this article from gamesutra.

Thanks for any help!

Edit I've found out (from this link: http://www.dice.se/wp-content/uploads/2014/12/Chapter5-Andersson-Terrain_Rendering_in_Frostbite.pdf -> see page 53-55) that I don't have to turn on and off vertices, instead I have to store all permutations of node in diffrent vao. That's clear. But still don't have any idea how to detect cracks :/.

Answer 1

I prefer not to modify the data, quad tree in your case.

I prefer to select the children and nodes to draw depending on the LOD. When the camera is very far just most children are discarded (their size on screen would be much less than a pixel), many select only the point '1' or some in the connection (2, 4, 6 or 8), and only the closest draw all vetices.

You need to decide which vertex is the "relevant" for each LOD.

You should work on the "select children and nodes" part.

EDIT

What you need is a way of selecting vertices for a patch so that it fits with a neighbor patch which is farther from the camera. Thus, this neighbor uses a different LOD.

The algorithm depends on the relative position (at left or right or up or down) of the neighbour. It also depends on the different LOD of the neighbor compared to the patch (If you use several LODs the LOD-step from a patch to its neighbour should be just one, but with care you can code a junction between high and low LODs without halfway LOD). There are several combinations.

To allow at least two different LODs you need a 5x5 vertices patch. Low LOD patch will be 3x3 (what you draw).

Then you select vertices for the high-LOD (what you call "modifing the qtree", right?) by something like this:

if (LOD1 == high)
   if (LOD1 == LODneighbor)
       get all vertices
   else
       if (neighbor at right)
           get all top vertices
           get second row except right most
           get thrid row
           ....
       else if (neighbor at up)
           get alternate top vertices
           get whole second row
           ....
       else if ...
if (LOD == medium)
   if (neighbor at right)
       get 1, 2, 4
   else if (neighbor at up)
        get 1, 4, 6
    else if ...

The neighbor with low-LOD selects all its vertices.

What is exposed in that link is when you select vertices by using indexed buffer. Each permutation represents the vertices to get depending on the position of the neighbour.