2013-04-10 81 views
2

重点在于查找时间(交点开始时),尽管位置也很重要。边界框(不是轴对齐)具有位置,旋转,速度和角速度(旋转速率)。没有加速度,这应该真的简化了事情......如果有必要的话,我也可以删除角速度分量。无论是连续函数还是迭代函数都可以工作,但除非迭代函数主动向解(或缺少)求解,否则它可能会太慢。查找时间和两个移动的旋转边界框的交点位置

我看着the SAT,但它似乎并没有建立起来,以找到运动物体的实际碰撞时间。它似乎只适用于不移动的快照,并且设计用于处理比矩形更复杂的对象,所以它实际上似乎不适合这个问题。

我已经考虑过可能画出每个8点的轨迹,然后以某种方式有一个功能,如果一个点是在或不在其他形状,并获得发生的时间范围,但我很漂亮失去了如何去做这件事。一个很好的特点是它完全随时间运行,并忽略了离散“步骤”的想法,但它也让我觉得这是一种低效率的方法。

不用担心广泛的阶段(确定是否值得看看这两个边界框是否可能重叠),我已经解决了这个问题。

回答

2

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

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

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

已发表的学术文献中有多种现有方法。我推荐一些图书馆研究:最好的选择可能取决于你的应用程序的细节。

0

首先,而不是两个矩形的思维与速度(x1, y1)(x2, y2)分别移动,可以解决这些问题的一个(其速度设置为(0, 0)),并认为另一个与速度(x2 - x1, y2 - y1)移动。

这样,情况看起来像一个矩形是不可移动的,另一个矩形是经过的,可能会碰到第一个矩形。

  • 假设你没有任何角速度

enter image description here

不难看出,可以然后相交4个轨迹的第二矩形的(它们是从不同的角落开始射线在(x2 - x1, y2 - y1)方向上的边界框的边界),第一个矩形的四边静止。然后,您也必须执行相同的操作 - 找到第一个矩形的相反方向 - (-(x2 - x1), -(y2 - y1))与第二个矩形的4个边的交点。选择你找到的所有交点之间的最小距离(可能有0-8个),你就完成了。

不要忘了考虑很多特殊情况 - 当两个矩形的边是平行的,当有一个在所有等

注意没有交集,这一切都是在O(1)时间内完成,但计算是相当复杂 - 光线和线段的32个交点。

  • 如果你真的希望你的矩形与一些的速度旋转,我会建议考虑什么@comingstorm说:这不过是找到一种非线性方程的根,的问题,即使在这种情况下,如果你的矩形的角速度是有限的,你可以将任务分成一系列的子任务,但我想这只是解决非线性问题的可能方法之一。