简单的 3d space 碰撞检查算法
simple 3d space collision check algorithm
我有一个连续的 3d space 由 4 个平面的内部 space 定义，这些平面相交于平行线（无限长的矩形形状）- 我们称之为 'A'。然后在模型中我还有一堆封闭的凸 3d 形状，它们可能重叠也可能不重叠到 space 'A' - 让我们称它们中的每一个为 'B'。我正在寻找的是一种计算效率尽可能高的算法过程，用于破译 'B' 形状是否重叠 'A'。
*每个 'B' 形状都由它的顶点、边和带有平面等的面以及它们之间的链接定义。
*如果其中一些没有意义，我可以做一些涂鸦...
到目前为止，我根据 'A' 检查每个 'B' 形状的过程如下：
检查 b 的任何点是否在 A 的所有 4 个平面内 - 如果是这样 => 重叠（如果它们都落在同一个外面 space => 没有重叠）
检查 a 的任何平行线是否与 b 的任何面相交 - 如果是 => 重叠。
检查 b 的任何边是否与 A 的 4 个面中的任何一个相交 - 如果是 => 重叠。
我还想我可以为每个 'B' 形状创建一个带有中心点和半径的近似边界圆来首先检查以快速消除远处的 'B' 形状...
** 对于第 2 部分和第 3 部分，我使用了一个函数来检查边是否与 3d 对象相交。这是通过将 2 个点与构成对象的每个平面进行比较来查看它们是否是相对的边，然后如果是，则找到平面交点并检查该交点是否在 3d 对象内部。
这似乎可行，但我想看看是否有更好或更快的破解方法？也许我错过了一些明显的东西......
谢谢
请注意，对于无限矩形"tube"，您可以将问题简化为二维情况：只需将所有点和边投影到平面上，垂直于管。
现在你必须寻找多段线（多边形）与矩形的交点（如果你使用管子母线上的点作为基点和向量，则轴对齐）——这个任务肯定更简单。
如果你的形状是凸的，多边形也是凸的，SAT-方法（分离轴定理）非常好（当然对于形状之间的链接不是这样，它们应该分开处理）。
继续MBo的回答，你可以通过顶点的(2D)凸包找到B形的有用轮廓，它是一个凸多边形。
http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull
然后应用 Sutherland-Hodgman 裁剪算法，看看是否还有非空交叉点。
https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm
我有一个连续的 3d space 由 4 个平面的内部 space 定义，这些平面相交于平行线（无限长的矩形形状）- 我们称之为 'A'。然后在模型中我还有一堆封闭的凸 3d 形状，它们可能重叠也可能不重叠到 space 'A' - 让我们称它们中的每一个为 'B'。我正在寻找的是一种计算效率尽可能高的算法过程，用于破译 'B' 形状是否重叠 'A'。
*每个 'B' 形状都由它的顶点、边和带有平面等的面以及它们之间的链接定义。
*如果其中一些没有意义，我可以做一些涂鸦...
到目前为止，我根据 'A' 检查每个 'B' 形状的过程如下：
检查 b 的任何点是否在 A 的所有 4 个平面内 - 如果是这样 => 重叠（如果它们都落在同一个外面 space => 没有重叠）
检查 a 的任何平行线是否与 b 的任何面相交 - 如果是 => 重叠。
检查 b 的任何边是否与 A 的 4 个面中的任何一个相交 - 如果是 => 重叠。
我还想我可以为每个 'B' 形状创建一个带有中心点和半径的近似边界圆来首先检查以快速消除远处的 'B' 形状...
** 对于第 2 部分和第 3 部分，我使用了一个函数来检查边是否与 3d 对象相交。这是通过将 2 个点与构成对象的每个平面进行比较来查看它们是否是相对的边，然后如果是，则找到平面交点并检查该交点是否在 3d 对象内部。
这似乎可行，但我想看看是否有更好或更快的破解方法？也许我错过了一些明显的东西......
谢谢
请注意，对于无限矩形"tube"，您可以将问题简化为二维情况：只需将所有点和边投影到平面上，垂直于管。
现在你必须寻找多段线（多边形）与矩形的交点（如果你使用管子母线上的点作为基点和向量，则轴对齐）——这个任务肯定更简单。
如果你的形状是凸的，多边形也是凸的，SAT-方法（分离轴定理）非常好（当然对于形状之间的链接不是这样，它们应该分开处理）。
继续MBo的回答，你可以通过顶点的(2D)凸包找到B形的有用轮廓，它是一个凸多边形。
http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull
然后应用 Sutherland-Hodgman 裁剪算法，看看是否还有非空交叉点。
https://en.wikipedia.org/wiki/Sutherland%E2%80%93Hodgman_algorithm