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

Question

我正在写一个游戏中使用的3D模型绘制场景(自上而下的正投影),但2D物理引擎计算响应碰撞等我有一些3D的资产,我想为其能通过使用XY平面"切片"3D网格并从结果边创建多边形来自动生成命中框.

谷歌在这个问题上让我失望(在SO上也没有太多有用的材料).建议？

我正在处理的网格将是显示模型的简化版本,它们是连接的,封闭的,非凸的并且具有零属.

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

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

与所有几何算法一样,魔鬼在细节中.例如,仔细考虑三角形顶点正好在平面中的情况.