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

问题描述

我正在写一个游戏，它使用3D模型来绘制场景（自顶向下的正射投影），但2D物理引擎计算响应碰撞等我有几个3D资产，我想以能够自动生成一个击中格由'切片'的3D网格的XY平面和创建从所得边的多边形。

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.

谷歌是在这一个失败的我（并没有太大帮助的材料上这样无论是）。建议？

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.

推荐答案

由于您的网格不是凸的，所得到的横截面可被断开，所以实际上由多个多边形。这意味着每个三角形必须进行检查，所以你需要至少为O（n）操作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.

下面是做到这一点的一种方法：

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

这将运行在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.

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