algorithm - 在视锥中找到所有大小为 L 的立方体的方法？

Question

我正在尝试查找或搜索一种方法，该方法可以快速找到将包含在视锥体中的所有大小为 L 的立方体。甚至可能使用 cuda。

我已经为光线转换做了一个 DDA 遍历，这对我来说就像一个 1D 案例并且很简单，因为我只沿着已知距离的线移动。

我的直觉是创建一个平截头体的边界框，并将该空间分割为大小为 L 的立方体的空间网格。然后测试每个单元格的网格中心是否位于平截头体内。考虑到截锥体是金字塔，似乎大约一半的单元格会被边界框占据，我觉得这种方法做的工作太多了。虽然它肯定会起作用，但我希望有一种不那么幼稚或更快的几何方法。

也许射线首先转换左墙，然后是右墙，然后在它们之间转换线？所以简而言之，寻找类似 DDA 遍历的 R3 版本。

Answer 1

检测顶点是否位于平截头体内的最快方法是 dot product .平截头体由 4 个平面组成，即顶部、底部、左侧、右侧，以及两个 z 值、前后剪裁。对于每个顶点检查两件事:首先，它是在前面板还是后面板之外？如果不是，是在四个位面内吗？

1. 要检查一个顶点是在前面板还是后面板之外，您可以根据您的平截头体检查 vertex.Z:

   isInsideZ = vertex.Z >= frustrum.Zmin && vertex.Z <= frustrum.Zmax;
   

2. 要检查它是否在四个平截头体“墙”内，您需要计算 cross vectors对他们来说，面向平截头体的中心。然后检查每个交叉向量的点积和相对于相应平面的顶点的位置向量。您可以通过从您测试的顶点中减去平面上 上的任意点来获得此位置向量。如果点积为正，则顶点位于该平面上方。

   isAbove[i] = Vector3D.Dot(cross[i], vertex - planeloc[i]) > 0;
   

   planeloc[i] 是位于相应平面i 上的任何 点。

如果满足所有条件，则顶点位于平截头体内:

isInside = isInsideZ && isAbove[0] && isAbove[1] && isAbove[2] && isAbove[3];

这听起来有点难处理，但在研磨循环之外可以做很多事情，例如计算叉积，即平截头体平面法线或平面位置向量。例如，如果一个平面被 (1,0,0), (1,1,0) 所跨越，那么 (1,0,0) 已经代表一个点位于那个平面上。