将三角形带的顶点转换为多边形的算法

Question

我有一个包含顶点的三角形条纹数组。 我需要将其转换为多边形。 有许多方法可以做相反的操作，但我找不到解决上述问题的方法。 或者这可能太简单了，我只是看不见。 请帮忙。 OpenGL兼容，参见http://en.wikipedia.org/wiki/Triangle_strip 例如：对于这个条带http://en.wikipedia.org/wiki/File:Triangle_Strip_Small.png，我需要输出A B D F E C或A C E F D B。

- Yarik

---

“三角形带”是什么意思？它是由三角形构成的任意形状吗？还是更具体的东西？ - Rex Kerr

这是针对“三角形条带”，而非“三角形带”的。一个三角带是一种数据格式，它仅使用nTriangles + 2个顶点来指定三角形列表，因为每个三角形在第一个三角形之后都使用前一个三角形的最后两个顶点。 - dash-tom-bang

Answer 1

我相信以下方法应该有效：

遍历顶点列表。将第一个点添加到多边形中。将第二个点推入堆栈。将第三个点添加到多边形中。继续在将点推入堆栈和将它们添加到多边形之间交替，直到到达列表末尾。当到达列表末尾时，弹出堆栈中的点并将它们添加到多边形中。

- Jerry Coffin

---

@belisarius：如果你的意思是它不会尝试“简化”多边形，也就是说，它将创建一个与三角形带轮廓完全匹配的多边形。例如，如果你将一个表面细分成一个绕着很多圈的长三角形带，它将产生一个完全绕着相同方式的多边形。至少在使用3个维度时，你不能做太多其他的事情--内部点通常具有需要保留的不同Z值。 - Jerry Coffin

是的，我认为这是原帖作者的意图。也许我错了。谢谢。 - Dr. belisarius

为了简化多边形，统一相等顶点的名称，然后遍历您的循环列表，用A替换ABA模式，直到不再可能进行此类替换为止。 - Svante

@belisarius - 三角形带上没有内部点。 - dash-tom-bang

@dash-tom-bang 是的，我在发布评论很久以后才明白了。谢谢。 - Dr. belisarius

Answer 2

我会假设你的三角形带总是以相同的方式连接（我相信这对于OpenGL是正确的）。

• “底部”顶点始终相隔两个：A，C，E，...
• “顶部”顶点始终相隔两个：B，D，F，...

取“底部”列表并附加“顶部”列表的反向。（例如ACEFDB）

---

或者更直接地说，使用从零开始的索引而不是字母：

// do "bottom"
for ( i = 0; i < N; i += 2 )
  addVertex( i )

// do "top"
largestOddNumberLessThanN = N % 2 == 0 ? N - 1 : N - 2;
for ( i = largestOddNumberLessThanN; i >= 0; i -= 2 )
  addVertex( i )

- Tom Sirgedas

Answer 3

如果你的形状结构特别简单，可能会有一个快捷方式，但一般来说我认为您想要执行以下操作：

• 从三角形列表中创建顶点和边的列表。这涉及检测共享点（希望它们是精确匹配的，这样你可以通过哈希找到它们而不需要某种模糊搜索）和共享线（那很容易--只需不要在两个共享顶点对之间绘制两条边）。
• 找到左上角最靠上的点。
• 找到尽可能逆时针方向行驶的边，也是最左上角的边。
• 走向下一个顶点。
• 找到尽可能返程的下一条边。
• 一直走到再次碰到左上角最靠上的点。

- Rex Kerr