c++ - 对象内的 3D 点

Question

我已经搜索并搜索了这个问题，但我无法真正理解我找到的任何答案。我的问题很简单：

拥有一个网格（由三角形构建的 3D 非凸多边形），我扫描空间 (xyz)，我需要找到网格“内部”的所有点以供以后处理。我再说一遍，我已经看到了很多关于此的答案，但我无法理解。

身边有人帮忙吗？？

Answer 1

我假设您正在尝试找出给定点是否在网格内（否则，显然有无限数量的点）。

一个简单的解决方案是从该点（在任何方向）投射一条射线，并计算与其相交的三角形的交点数。如果数字是奇数，则该点在里面。当光线击中边缘或顶点时，必须注意将其计为一个交点。射线和三角形的相交是通过将一条线与一个平面相交来完成的，检查该点是否属于射线并且在三角形内部。

Answer 2

检查每个点以查看它是否在网格内会起作用，但从性能角度来看，我们可以做得更好。您当前的方法将在 中运行O(x*y*z*t)，因为点的网格是xby y，z并且网格有t面。

将运行的替代方法O(x*y*t)是考虑穿过网格的网格线 - 找到线和网格之间的交点。应该有偶数个交叉点。一旦这些交点被排序，它们就定义了位于网格内的线区域。然后很容易生成位于这些区域的线上的点。

大致（假设网格位于单位立方体内）：

for each X in [0,1] {
  for each Y in [0,1] {
    Let P be a list of points of intersection between the mesh and the line from (X,Y,0) to (X,Y,1)
    Sort P into ascending order of z-coordinate
    Let I be false
    for each Z in [0,1] {
      if Z > P[0] {
        I = !I
        pop P[0] off the list
      }
      if( I ) {
        point (X,Y,Z) is inside the mesh
      }
    }
  }
}