实现凹形的三角剖分算法

Question

我在用 c 实现三角剖分算法时遇到了一些问题。有些点选错了，我也不知道哪里会出错，但是对于我这个没有经验的人来说，看起来还不错。

编辑：我正在使用 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)));
    }

我的结果：

我的结果应该是这样的，但是没有内部三角形：

预期结果：

上图请注意：我使用了不同的渲染系统，这就是为什么它看起来是倒置的，这应该不会影响结果。谢谢。

Answer 1

好的，正如 Matt Timmermans 提到的，我只是在 RemoveElementFromList 函数中遇到了简单的错字。

而不是 if (IndexList[i] >= PolyIdx) 应该是 if (i >= PolyIdx):

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

就这么简单。

实现凹形的三角剖分算法

Implementing triangulation algorithm for concave shapes

c++

algorithm

graphics

triangulation