从 3D 网格生成 2D 横截面多边形 [英] Generate 2D cross-section polygon from 3D mesh

问题描述

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

I'm writing a game which uses 3D models to draw a scene (top-down orthographic projection), but a 2D physics engine to calculate response to collisions, etc. I have a few 3D assets for which I'd like to be able to automatically generate a hitbox by 'slicing' the 3D mesh with the X-Y plane and creating a polygon from the resultant edges.

谷歌在这方面让我失望(而且关于 SO 的有用材料也不多).建议?

Google is failing me on this one (and not much helpful material on SO either). Suggestions?

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

The meshes I'm dealing with will be simplified versions of the displayed models, which are connected, closed, non-convex and have zero genus.

推荐答案

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

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.

这是一种方法:

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 支持恒定时间删除(例如哈希集).

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.

这篇关于从 3D 网格生成 2D 横截面多边形的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！