algorithm - 从 3D 网格生成 2D 横截面多边形

Question

我正在编写一个游戏，它使用 3D 模型绘制场景(自上而下的正交投影)，但使用 2D 物理引擎来计算对碰撞的响应等。我有一些我想要的 3D Assets 能够通过使用 X-Y 平面“切片”3D 网格并从结果边缘创建多边形来自动生成碰撞框。

谷歌在这方面让我失望(而且在 SO 方面也没有太多有用的 Material )。有什么建议吗？

我正在处理的网格将是所显示模型的简化版本，它们是连通的、封闭的、非凸的并且具有零亏格。

Answer 1

由于您的网格不是凸面的，因此生成的横截面可能会断开连接，因此实际上由多个多边形组成。这意味着必须检查每个三角形，因此对于 n 个三角形，您至少需要 O(n) 次操作。

这是一种方法:

T <- the set of all triangles
P <- {}
while T is not empty:
  t <- some element from T
  remove t from T
  if t intersects the plane:
    l <- the line segment that is the intersection between t and the plane
    p <- [l]
    s <- l.start
    while l.end is not s:
      t <- the triangle neighbouring t on the edge that generated l.end
      remove t from T
      l <- the line segment that is the intersection between t and the plane
      append l to p
    add p to P

对于 n 个三角形，这将在 O(n) 时间内运行，前提是您的三角形具有指向其三个邻居的指针，并且 T 支持恒定时间删除(例如哈希集)。

与所有几何算法一样，细节决定成败。例如，仔细考虑三角形的顶点恰好在平面内的情况。