algorithm - 地形四叉树 LOD 裂缝/T 型连接

Question

我已经使用四叉树在我的图形引擎中实现了一个基本地形，现在我遇到了修复 T 型路口和裂缝的问题。首先，我使用的是 OpenGL 3.2，所以我无法使用 tesslation。也许我会在不久的将来实现这个功能。基本上我有一个地形对象，它存储一个四叉树对象并有一个称为渲染的方法:

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

    this.quadtree.render(program);
}

然后我的四叉树对象有四个名为 TerrainTreeNode 的子节点和这个方法:

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

然后我的 TerrainTreeNode 对象有这些方法:

/**
 * 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();
    }
}

如您所见，如果树节点与相机的距离很长，那么它会删除子节点并创建自己的 vao，在相反的情况下，它会创建子节点并从内存中删除 vao。我的 vao 使用三角风扇，它看起来像这样:

1、2、4、6、8 和 10 个顶点始终处于事件状态，我想打开和关闭的其他顶点取决于相邻的细节级别以避免这种情况:

算法应该禁用红色顶点。我怎样才能做到这一点？如何找到所有无用的顶点？该算法基于 gamesutra 的这篇文章。

感谢您的帮助!

编辑我发现(从此链接:http://www.dice.se/wp-content/uploads/2014/12/Chapter5-Andersson-Terrain_Rendering_in_Frostbite.pdf -> 请参阅第 53-55 页)我不必打开和关闭顶点，而是必须将节点的所有排列存储在不同的 vao 中。这很清楚。但仍然不知道如何检测裂缝:/。

Answer 1

我不想修改数据，在你的情况下是四叉树。

我更喜欢根据 LOD 选择要绘制的子节点和节点。当相机距离很远时，只有大多数 child 被丢弃(他们在屏幕上的大小将远小于一个像素)，许多 child 只选择点“1”或连接中的一些(2、4、6 或 8)，并且只最接近的绘制所有 vetices。

您需要确定每个 LOD 的“相关”顶点。

您应该处理“选择子节点和节点”部分。

编辑

您需要的是一种为面片选择顶点的方法，以便它适合距离相机较远的相邻面片。因此，这个邻居使用不同的 LOD。

算法取决于邻居的相对位置(左或右或上或下)。它还取决于与补丁相比邻居的不同 LOD(如果您使用多个 LOD，从补丁到其邻居的 LOD 步应该只是一个，但您可以小心地编码高 LOD 和低 LOD 之间的连接点而不会中途细节层次)。有几种组合。

要允许至少两个不同的 LOD，您需要一个 5x5 顶点补丁。低 LOD 补丁将为 3x3(您绘制的内容)。

然后您通过如下方式为高 LOD 选择顶点(您称之为“修改 qtree”，对吗？):

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 ...

低 LOD 的邻居选择它的所有顶点。

该链接中公开的是当您使用索引缓冲区选择顶点时。每个排列代表根据邻居的位置获得的顶点。