将重叠的三角形合并为一个多边形

Question

我从投影到二维平面的3D模型中获得了一堆重叠的三角形。我需要将触摸三角形的每个岛合并为一个封闭的非凸多边形。

结果多边形不应该有任何洞（因为源数据没有）。

许多源三角形与源数据中的其他三角形共享（浮点相同）边。

这样做最简单的方法是什么？性能不是特别重要，因为这将在设计时完成。

Answer 1

尝试gpc，或一般多边形帆船库。

Answer 2

想象投影到一个平面上的模型的“视图”（即投影的方向是视线，并且所述突出部你看到的）。在这种情况下，要计算的多边形的边界对应于模型的轮廓。

轮廓反过来是模型中的一组边。对于轮廓中的每个边缘，相邻的面都将具有法线，该法线指向远离平面或朝向平面。您可以检查这是将面法线的点积与平面法线相乘 - 查找相邻面法线具有与投影方向相反符号的点积的边。

一旦你找到了所有的轮廓边，你可以将它们连接在一起进入所需多边形的边界。

一般情况下，你可以通过google搜索术语如mesh silouette finding detection找到更多关于轮廓检测和提取。也许一个好的开始是here。

Answer 3

我也发现这个[1]方法，我将在下一步尝试。

[1] 2d outline algorithm for projected 3D mesh