x26*_*x26 17 physics collision-detection
我的问题很简单.我有两个四面体,每个四面体都有一个当前位置,一个空间线速度,一个角速度和一个质心(实际上是旋转中心).
有了这些数据,我试图找到一个(快速)算法,它将精确地确定(1)它们是否会在某个时间点发生碰撞,如果是这种情况,(2)在它们碰撞了多长时间之后(3) )碰撞点.
大多数人会通过三角形 - 三角形碰撞检测来解决这个问题,但这会浪费一些冗余操作的CPU周期,例如在检查不同的三角形时检查一个四面体的相同边缘与另一个四面体的相同边缘.这只意味着我会稍微优化一下.没什么好担心的.
问题是我不知道任何公共CCD(连续碰撞检测)三角形 - 三角形算法,它考虑了自转.
因此,我需要一个输入以下数据的算法:
并输出以下内容:
在此先感谢您的帮助.
常用的离散碰撞检测将在连续的离散时间点上检查每个形状的三角形以进行碰撞.虽然直接计算,但由于在测试的离散点之间发生碰撞,它可能会错过快速移动的物体撞击另一个物体.
连续碰撞检测首先计算每个三角形在无限时间内描绘的体积.对于以恒定速度移动且没有旋转的三角形,该体积看起来像三棱柱.然后,CCD将检查卷之间的碰撞,并最终追溯三角形实际上共享相同空间的时间.
当引入角速度时,每个三角形所描绘的体积不再像棱镜那样.它可能看起来更像螺丝的形状,如DNA链,或者通过在任意轴周围旋转三角形同时线性拖动它可能获得的其他一些非平凡的形状.计算这种体积的形状并非易事.
一种方法可能首先计算包含整个四面体的球体,当它以给定的角速度矢量旋转时,如果它没有线性移动.您可以为每个顶点计算旋转圆,并从中导出球体.给定一个球体,我们现在可以将挤出的CCD体积近似为具有球体半径的圆柱体,并沿线性速度矢量前进.找到这些圆柱体的碰撞使我们得到一个区域的第一个近似值来搜索碰撞.
第二种补充方法可能试图将每个三角形所追踪的实际体积近似分解为几乎棱柱形的小体积.它将以两个时间增量取三角形位置,并添加通过在那些时刻跟踪三角形顶点而生成的曲面.它是近似值,因为它连接直线而不是实际曲线.对于避免粗差的近似,每个连续矩之间的持续时间需要足够短,使得三角形仅完成旋转的一小部分.持续时间可以从角速度导出.
第二种方法创建了更多的多边形!您可以使用第一种方法来限制搜索量,然后使用第二种方法来获得更高的精度.
如果你正在为游戏引擎解决这个问题,你可能会发现上面的精度足够了(我仍然会对计算成本感到不寒而栗).相反,如果您正在撰写CAD程序或撰写论文,您可能会发现它不太令人满意.在后一种情况下,您可能希望改进第二种方法,可能是通过对转动的移动三角形所占据的体积进行更好的几何描述 - 当限制为小转弯角度时.