algorithm - 翻转两个三角形的边

Question

我有一个带索引的数组。其中三个指数构成一个三角形。现在我取一个三角形并搜索另一个具有共享边的三角形。这些三角形现在组成了一个对角分割的四边形。我如何(在代码中)翻转这个对角线边缘/三角形以连接相反的对角线？我正在寻找的东西在 3D 程序(如 Blender、Maya、3ds max 等)中通常称为“翻转边缘”。

我被这个困住了。有什么想法吗？

Answer 1

这取决于您如何实现您的结构。例如，如果你有这样的结构:

struct Vertex
{
    double position[3];
};

struct Triangle
{
    unsigned int vertices[3];
};

Vertex nodes[N_NODES];
Triangle triangles[N_TRIANGLES];

其中，vertices是nodes的索引，然后给定两个三角形:

Triangle t1, t2;

如果你有

t1.vertices[i1] = t2.vertices[j1];
t1.vertices[i2] = t2.vertices[j2];

表示 t1.vertices[i1] --- t1.vertices[i2] 是与 t2.vertices[j1] --- t1.vertices[j2] 的共享边，并假设 i3 和 j3 分别是 t1 和 t2 的第 3 个顶点，如图所示在这张图片中:

然后你可以通过改变一些索引来完成翻转。最直接的方法是:

unsigned int t1_v[3], t2_v[3];

t1_v[0] = t1.vertices[i1];  // shared
t1_v[1] = t1.vertices[i2];  // shared
t1_v[2] = t1.vertices[i3];  // not shared

t2_v[0] = t2.vertices[j1];  // shared (unnecessary)
t2_v[1] = t2.vertices[j2];  // shared (unnecessary)
t2_v[2] = t2.vertices[j3];  // not shared

t1.vertices[0] = t1_v[0];  // previously shared
t1.vertices[1] = t1_v[2];  // previously not shared
t1.vertices[2] = t2_v[2];  // previously not shared

t2.vertices[0] = t2_v[0];  // previously shared
t2.vertices[1] = t2_v[2];  // previously not shared
t2.vertices[2] = t1_v[2];  // previously not shared

请注意，每个新三角形由 2 个非共享顶点和一个共享顶点组成。