C语言实现凹多边形三角剖分算法顶点选取错误问题求助

问题描述 #

我在使用C语言实现三角剖分（Triangulation）算法时遇到问题，部分选取的顶点存在错误，暂未定位到出错位置，根据现有经验排查代码逻辑没有明显问题。
补充说明：使用msvc c++编译器进行编译，用于支持v3结构体的部分运算符重载。

核心代码 #

struct shape
{
    u32 VerticesCount;
    v3* Vertices;

    u32 TrianglesCount;
    int* Triangles;
};

static void PolygonTriangulate(shape* Shape)
{
    bool Result = false;

    int  ListSize  = Shape->VerticesCount;
    int* IndexList = (int*)malloc(sizeof(int) * ListSize);
    for(int i = 0; i < ListSize; ++i)
    {
        IndexList[i] = i;
    }

    int TotalTriangleCount = Shape->VerticesCount - 2;
    int TotalTriangleCountIdx = TotalTriangleCount*3;

    int* TrianglesResult = (int*)malloc(sizeof(int)*TotalTriangleCountIdx);
    int  TriangleIdx = 0;

    while(ListSize > 3)
    {
        for(int PolyIdx = 0; PolyIdx < ListSize; ++PolyIdx)
        {
            int cur  = IndexList[PolyIdx];
            int prev = GetListElement(IndexList, ListSize, PolyIdx - 1);
            int next = GetListElement(IndexList, ListSize, PolyIdx + 1);

            v3 A = Shape->Vertices[cur];
            v3 B = Shape->Vertices[prev];
            v3 C = Shape->Vertices[next];

            v3 AB = B - A;
            v3 AC = C - A;
            
            if(Cross(AB, AC).Z < 0.0f)
            {
                continue;
            }

            bool IsEar = true;

            for(int i = 0; i < Shape->VerticesCount; ++i)
            {
                if((cur == i) || (prev == i) || (next == i))
                {
                    continue;
                }

                v3 Point = Shape->Vertices[i];
                
                if(IsPointInTriangle(Point, B, A, C))
                {
                    IsEar = false;
                    break;
                }
            }

            if(IsEar)
            {
                TrianglesResult[TriangleIdx++] = prev;
                TrianglesResult[TriangleIdx++] = cur;
                TrianglesResult[TriangleIdx++] = next;

                RemoveElementFromList(IndexList, &ListSize, PolyIdx);
                break;
            }
        }
    }

    TrianglesResult[TriangleIdx++] = IndexList[0];
    TrianglesResult[TriangleIdx++] = IndexList[1];
    TrianglesResult[TriangleIdx++] = IndexList[2];

    Shape->TrianglesCount = TriangleIdx;
    Shape->Triangles = TrianglesResult;
}

辅助函数代码 #

static bool IsPointInTriangle(v3 Point, v3 A, v3 B, v3 C)
{
    v3 AB = B - A;
    v3 BC = C - B;
    v3 CA = A - C;

    v3 AP = Point - A;
    v3 BP = Point - B;
    v3 CP = Point - C;

    float Cross1 = Cross(AB, AP).Z;
    float Cross2 = Cross(BC, BP).Z;
    float Cross3 = Cross(CA, CP).Z;

    if((Cross1 <= 0.0f) && (Cross2 <= 0.0f) && (Cross3 <= 0.0f))
    {
        return true;
    }

    return false;
}

int GetListElement(int* IndexList, int ListSize, int PolyIdx)
{
    int Result;

    if(PolyIdx < 0)
    {
        Result = IndexList[PolyIdx % ListSize + ListSize];
    }
    else if(PolyIdx >= ListSize)
    {
        Result = IndexList[PolyIdx % ListSize];
    }
    else
    {
        Result = IndexList[PolyIdx];
    }

    return Result;
}

void RemoveElementFromList(int* IndexList, int* ListSize, int PolyIdx)
{
    for(int i = 0; i < *ListSize; ++i)
    {
        if(IndexList[i] >= PolyIdx)
        {
            IndexList[i] = IndexList[i + 1];
        }
    }
    *ListSize -= 1;
}

渲染逻辑代码（已确认无问题） #

for(u32 CoordIdx = 0; CoordIdx < Shape->TrianglesCount; CoordIdx += 3)
    {
        triangle_t Triangle = {};

        Triangle.points[0] = 20*Shape->Vertices[Shape->Triangles[CoordIdx  ]].XY + Center;
        Triangle.points[1] = 20*Shape->Vertices[Shape->Triangles[CoordIdx+1]].XY + Center;
        Triangle.points[2] = 20*Shape->Vertices[Shape->Triangles[CoordIdx+2]].XY + Center;

        DrawTriangle(Triangle, CreateColor(V3(1.0f, 1.0f, 0.0f)));
    }

运行结果 #

• 错误结果1：顶点位置异常
  
• 错误结果2：仅轮廓符合预期，缺失内部三角形
  
• 预期结果：完整三角剖分效果
  

注：截图使用的渲染系统存在画面倒置特性，不会对算法结果产生影响。

问题修复方案 #

1. 修复RemoveElementFromList函数逻辑错误 #

原有代码混淆了列表位置索引和顶点原始索引，你需要删除的是列表中第PolyIdx个位置的元素，正确实现如下：

void RemoveElementFromList(int* IndexList, int* ListSize, int PolyIdx)
{
    for(int i = PolyIdx; i < *ListSize - 1; ++i)
    {
        IndexList[i] = IndexList[i + 1];
    }
    *ListSize -= 1;
}

2. 修正耳点判断的点遍历范围 #

原有代码遍历了所有原始顶点，已经被切掉的顶点不需要再参与耳点判断，改为仅遍历当前剩余的顶点：

for(int i = 0; i < ListSize; ++i)
{
    int pointIdx = IndexList[i];
    if((cur == pointIdx) || (prev == pointIdx) || (next == pointIdx))
    {
        continue;
    }
    v3 Point = Shape->Vertices[pointIdx];
    if(IsPointInTriangle(Point, B, A, C))
    {
        IsEar = false;
        break;
    }
}

3. 校验多边形绕序与叉积判断的一致性 #

你当前判断凸顶点的条件Cross(AB, AC).Z < 0.0f仅适用于逆时针输入的多边形，如果你的输入顶点为顺时针顺序，需要将该判断条件反转，也可以提前统一多边形绕序避免该问题。

4. 匹配点在三角形内判断的叉积符号 #

IsPointInTriangle当前判断三个叉积都<=0，对应点在顺时针三角形内部，需要和前面的凸顶点判断的叉积符号保持一致，如果是逆时针多边形，需改为判断三个叉积都>=0。

内容的提问来源于stack exchange，提问作者Zhukov Artem