当前位置：文江博客话题详情

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

发布于 2024-09-01 00:55:23 字数 210 浏览 8 评论 0原文

我正在编写一个游戏，它使用 3D 模型来绘制场景（自上而下的正交投影），但使用 2D 物理引擎来计算对碰撞的响应等。我有一些 3D 资产，我希望能够通过使用 XY 平面“切片”3D 网格并从生成的边创建多边形来自动生成碰撞盒。

谷歌在这方面让我失望了（而且也没有太多有用的材料）。建议？

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

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

回忆那么伤 2024-09-08 00:55:23

由于网格不是凸的，因此生成的横截面可能会断开，因此实际上由多个多边形组成。这意味着必须检查每个三角形，因此对 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 支持恒定时间删除（例如散列放）。

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

Since your meshes are not convex, the resulting cross-section may be disconnected, so actually consist of multiple polygons. This means that every triangle must be checked, so you'll need at least O(n) operations for n triangles.

Here's one way to do it:

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

This will run in O(n) time for n triangles, provided that your triangles have pointers to their three neighbours, and that T supports constant-time removals (e.g. a hash set).

As with all geometric algorithms, the devil is in the details. Think carefully about cases where a triangle's vertex is exactly in the plane, for example.

回复收藏 0 原文