如何将三角形缠绕为 3D 网格模型的逆时针方向？

Question

首先让我澄清一下..我不是在问 2D 网格，要确定 2D 网格的缠绕顺序，使用法向 z 方向非常容易。

其次，我不要求任何优化算法，我不担心时间或速度，我只想用我的网格来做。

当我使用贪婪投影三角剖分算法对 3D 对象进行三角剖分时，会发生此问题。检查所附图片。

如果我使用“计算有符号面积”或“三角形的 AB 和 BC 向量的交叉产生”对该模型应用 2D 方法，它只能求解 2D 网格，但 3D 网格又如何呢？

首先我们需要检查哪些三角形在 3D 网格中缠绕方向错误，然后我们只考虑这些三角形，那么问题是，我们如何检查哪些三角形在 3D 中缠绕方向错误？我们不能只用 2D 方法来做我已经测试过但没有成功。

例如，对于球体，我们不能对球体应用 2D 方法。那么有没有办法解决这个问题呢？

谢谢。

更新#1：

下面是检查哪条边具有相同缠绕的算法。效果不太好，我不知道为什么。理论上它应该纠正所有三角形，但它没有纠正。例如，在附图中检查球体的情况下。有问题。

void GLReversedEdge(int i, int j, GLFace *temp)
{
    //i'th triangle
    int V1 = temp[i].v1;
    int V2 = temp[i].v2;
    int V3 = temp[i].v3;

    //i'th triangle edges
    int E1[] ={V1, V2};
    int E2[] ={V2, V3};
    int E3[] ={V3, V1};

    //adjacent triangle
    int jV1 = temp[j].v1;
    int jV2 = temp[j].v2;
    int jV3 = temp[j].v3;

    //adjacent edges
    int jE1[] ={jV1, jV2};
    int jE2[] ={jV2, jV3};
    int jE3[] ={jV3, jV1};

    // 1st edge of adjacent triangle is checking with all edges of ith triangle
    if((jE1[0] == E1[0] && jE1[1] == E1[1]) ||
       (jE1[0] == E2[0] && jE1[1] == E2[1]) ||
       (jE1[0] == E3[0] && jE1[1] == E3[1]))
    {
       temp[j].set(jV2, jV1, jV3);      // 1st edges orientation is same, so reverse/swap it
    }
    // 2nd edge of adjacent triangle is checking with all edges of ith triangle
    else if((jE2[0] == E1[0] && jE2[1] == E1[1]) ||
            (jE2[0] == E2[0] && jE2[1] == E2[1]) ||
            (jE2[0] == E3[0] && jE2[1] == E3[1]))
    {
            temp[j].set(jV1, jV3, jV2); // 2nd edges orientation is same, so reverse/swap it
    }
    // 3rd edge of adjacent triangle is checking with all edges of ith triangle
    else if((jE3[0] == E1[0] && jE3[1] == E1[1]) ||
            (jE3[0] == E2[0] && jE3[1] == E2[1]) ||
            (jE3[0] == E3[0] && jE3[1] == E3[1]))
    {
            temp[j].set(jV3, jV2, jV1); // 3rd edges orientation is same, so reverse/swap it
    }
}

void GetCorrectWindingOfMesh()
{
    for(int i=0; i<nbF; i++)
    {
        int j1 = AdjacentTriangleToEdgeV1V2;
        if(j1 >= 0) GLReversedEdge(i, j1, temp);

        int j2 = AdjacentTriangleToEdgeV2V3;
        if(j2 >= 0) GLReversedEdge(i, j2, temp);

        int j3 = AdjacentTriangleToEdgeV3V1;
        if(j3 >= 0) GLReversedEdge(i, j3, temp);
    }
}

Answer 1

为了检索邻近信息，假设我们有返回给定边上三角形的邻居的方法neighbor_on_egde( next_tria, edge )。

该方法可以利用使用该方法的三角形的每个顶点的信息来实现。这是将顶点索引映射到三角形索引列表的字典结构。通过传递三角形列表并在右侧字典元素中设置三角形的每个三角形顶点索引，可以轻松创建它。

遍历是通过存储哪些三角形要检查方向以及哪些三角形已被检查来完成的。虽然有三角形需要检查，但对其进行检查，如果未检查，则添加要检查的邻居。伪代码如下所示：

to_process = set of pairs triangle and orientation edge
             initial state is one good oriented triangle with any edge on it
processed = set of processed triangles; initial empty

while to_process is not empty:
    next_tria, orientation_edge = to_process.pop()
    add next_tria in processed
    if next_tria is not opposite oriented than orientation_edge:
        change next_tria (ABC) orientation  (B<->C)
  for each edge (AB) in next_tria:
      neighbor_tria = neighbor_on_egde( next_tria, edge )
      if neighbor_tria exists and neighbor_tria not in processed:
          to_process add (neighbor_tria, edge opposite oriented (BA))