algorithm - 查找两个移动、旋转边界框的交叉点的时间和位置

Question

重点是找到时间(交叉路口开始的时间)，尽管位置也很重要。边界框(未对齐轴)具有位置、旋转、速度和角速度(旋转速率)。没有加速度，这应该真正简化事情......如果有必要，我也可以删除角速度分量。连续函数或迭代函数都可以工作，但除非迭代函数主动收敛到一个解决方案(或没有解决方案)，否则它可能会太慢。

我看了the SAT , 但它似乎并不是为了找到移动物体的实际碰撞时间而构建的。它似乎只适用于非移动快照，并且设计用于处理比矩形更复杂的对象，所以它实际上似乎不适合这个问题。

我考虑过可能从这 8 个点中的每一个点中绘制出轨迹，然后以某种方式具有一个函数，用于判断一个点是否在另一个形状内或不在另一个形状内，并获得发生这种情况的时间范围，但我很迷茫关于如何去做。一个不错的功能是它完全随时间运行并且忽略了离散“步骤”的想法，但它也让我觉得这是一种低效的方法。

不用担心宽相(确定是否值得查看这两个边界框是否可能重叠)，我已经解决了这个问题。

Answer 1

找到一个准确的碰撞时间本质上是一个非线性的求根问题。这意味着您最终将需要一种迭代方法来确定最终的碰撞时间——但设计碰撞求解器的巧妙之处在于在实际上不需要时避免求根...

SAT 是一个定理，而不是算法:它可以用来指导碰撞求解器的设计，但它本身并不是一个。简而言之，它说，如果你能证明存在一个分离轴，那么物体就没有发生碰撞。相反，如果您可以证明不存在这样的轴，则当前对象确实重叠。正如您所指出的，您可以或多或少地直接使用这个原则来设计一个二元“是/否”查询，以确定给定位置的两个对象是否重叠。

与碰撞求解器的不同之处在于问题是动画的或动力学的:对象位置是时间的函数。解决此问题的一种方法是从有效的“是/否”碰撞测试开始，将所有不等式视为时间的函数，并在此基础上使用求根方法寻找实际碰撞时间。

已发表的学术文献中存在多种现有方法。我建议进行一些图书馆研究:最佳选择可能取决于您的应用程序的详细信息。