移动点和移动线段的碰撞位置和时间（连续碰撞检测）

Question

我正在研究一个 2D 对撞机系统，该系统将形状分解为一个可能的基元：由两点定义的不可穿透的部分。为了为该系统提供碰撞检测，我使用了一种静态碰撞检测方法，该方法每帧计算一次线段的边缘与当前处理的线段之间的距离（点/线距离）。如果距离太小，则在该帧期间触发碰撞。这工作正常，但如果一个或多个物体表现出高速，则会出现已知的隧道问题。所以我正在修补替代品。

现在我想介绍在动态点/动态段上运行的连续碰撞检测（CCD）。我的问题是：我不知道怎么做。我知道如何在两个移动点、移动点和静态段之间进行连续碰撞，但不知道如何在移动点（由点 P 定义）和移动段（由点 U 和 V 定义，两者都可以）之间进行 CCD完全自由移动）。

但没有提出这些确切的要求：

• 点和线段都在移动

• 段可以旋转和拉伸（因为 U 和 V 可以自由移动）

• 需要准确找到两帧之间的碰撞时间和碰撞点（CCD，无静态碰撞测试）

• 如果可能的话，我更喜欢数学上完美的解决方案（没有迭代近似算法，扫描体积）

• 注意：扫掠线形状并不总是凸多边形，因为 U、V 点的自由度

• 注意：测试与扫描体积的碰撞测试是不准确的，因为与多边形的碰撞点并不意味着实际运动中的碰撞点（参见图像，一旦实际段穿过轨迹，该点将离开多边形点）

到目前为止，我想出了以下方法，给出：

• sP（帧开始时的 P），

• eP（帧末尾的 P），

• sU（帧开始处的 U），

• eU（帧末尾的 U），

• sV（帧开始时的 V），

• eV（帧末尾的 V）

问题：它们会碰撞吗？如果是，何时何地？

解决方案：

将帧中每个点的时间轨迹建模为线性运动（0 <= t <= 1的线轨迹）

• P(t) = sP * (1 - t) + eP * t

• U(t) = sU * (1 - t) + eU * t

• V(t) = sV * (1 - t) + eV * t

（0 <= a <= 1表示由 U 和 V 定义的线段上的位置）：

• UV(a, t) = U(t) * (1 - a) + V(t) * a

通过使点和线段方程相等来模拟碰撞：

• P(t) = UV(a, t)

• P(t) = U(t) * (1 - a) + V(t) * a

为从点 P 到线段上的点的向量导出一个函数：

• F(a, t) = P(t) - (1 - a) * U(t) - a * V(t)

现在要找到碰撞，需要找到a和t，以便F(a, t) = (0, 0)和[0, 1] 中的 a,t。这可以建模为具有 2 个变量的寻根问题。

将时间轨迹方程插入F(a, t)中：

• F(a, t) = (sP * (1 - t) + eP * t) - (1 - a) * (sU * (1 - t) + eU * t) - a * (sV * (1 - t ) + eV * t)

按维度（x 和 y）分离时间轨迹方程：

• Fx(a, t) = (sP.x * (1 - t) + eP.x * t) - (1 - a) * (sU.x * (1 - t) + eU.x * t) - a * (sV.x * (1 - t) + eV.x * t)

• Fy(a, t) = (sP.y * (1 - t) + eP.y * t) - (1 - a) * (sU.y * (1 - t) + eU.y * t) - a * (sV.y * (1 - t) + eV.y * t)

现在我们有两个方程和两个要求解的变量（分别为Fx、Fy和a、t），因此我们应该能够使用求解器来获得a和t，然后检查它们是否位于 [0, 1]..对吗？

Answer 1

TLDR我确实读过“……大约 5 分钟来评估……”没办法太长，这是一个针对许多线和点的实时解决方案。抱歉，这不是一个完整的答案（我没有合理化和简化方程式），它将找到我留给你的截距点。我还可以看到解决方案的几种方法，因为它围绕一个三角形（见图）旋转，当平面是解决方案时。下面的方法找到三角形的长边等于短边之和的时间点。求解你（时间）这可以作为一个简单的二次方程来完成，其系数从 3 个起点导出，每个点的单位时间向量。为你解决下图提供了更多详细信息。点P是点的起始pos点L1、L2是线端的起点。矢量V1是单位时间内（沿绿线）的点。矢量V2、V3用于单位时间内的线路末端。u是单位时间A是点（蓝色），B和C是线端点（红色）存在（可能）一个时间点u，其中A在B和C线上。此时，线AB（作为a）和AC（作为c）的长度总和等于线BC（作为b）（橙色线）的长度。这意味着当b - (a + c) == 0时，该点在线上。在图像中，点被平方，因为这稍微简化了它。b&nbsp;2&nbsp;- (a&nbsp;2&nbsp;+ c&nbsp;2&nbsp;) == 0图像底部是根据u, P, L1, L2, V1, V2, V3 的方程（二次） 。该等式需要重新排列，以便得到(???)u&nbsp;2&nbsp;+ (???)u + (???) = 0抱歉，手动执行此操作非常乏味且很容易出错。我手头没有工具，也不使用 python，所以我不知道你使用的数学库。但是它应该能够帮助您找到如何计算(???)u&nbsp;2&nbsp;+ (???)u + (???) = 0 的系数更新忽略上面的大部分内容，因为我犯了一个错误。b - (a + c) == 0与b 2 - (a 2 + c 2 ) == 0不同。第一个是需要的，这是处理部首时的一个问题（请注意，仍然可以使用 虚数a + bi == sqrt(a^2 + b^2)在哪里的解决方案）。i另一种解决方案所以我探索了其他选择。最简单的有一个小缺陷。它将返回拦截时间。但是，必须对其进行验证，因为它还会在拦截线时返回拦截时间，而不是线段BC因此，当找到结果时，您可以通过将找到的点和线段的点积除以线段长度的平方来测试它。isPointOnLine请参阅测试片段中的功能。为了解决这个问题，我使用了这样一个事实，即当点在线上时，线BC与从B到A的向量的叉积将为 0。一些重命名使用上图，我重命名了变量，这样我就可以更轻松地完成所有繁琐的工作。/*point P is&nbsp; {a,b}point L1 is&nbsp; {c,d}point L2 is&nbsp; {e,f}vector V1 is {g,h}vector V2 is {i,j}vector V3 is {k,l}Thus for points A,B,C over time u&nbsp; &nbsp; */Ax = (a+g*u)Ay = (b+h*u)Bx = (c+i*u)By = (d+j*u)Cx = (e+k*u)Cy = (f+l*u)/* Vectors BA and BC at u */Vbax = ((a+g*u)-(c+i*u))Vbay = ((b+h*u)-(d+j*u))Vbcx = ((e+k*u)-(c+i*u))Vbcy = ((f+l*u)-(d+j*u))/*&nbsp; &nbsp;thus Vbax * Vbcy - Vbay * Vbcx == 0 at intercept&nbsp;*/这给出了二次0 = ((a+g*u)-(c+i*u)) * ((f+l*u)-(d+j*u)) - ((b+h*u)-(d+j*u)) * ((e+k*u)-(c+i*u))重新排列我们得到0 = -((i*l)-(h*k)+g*l+i*h+(i+k)*j-(g+i)*j)*u* u -(d*g-c*l-k*b-h*e+l*a+g*f+i*b+c*h+(i+k)*d+(c+e)*j-((f+d)*i)-((a+c)*j))*u +(c+e)*d-((a+c)*d)+a*f-(c*f)-(b*e)+c*b因此系数是&nbsp;A = -((i*l)-(h*k)+g*l+i*h+(i+k)*j-(g+i)*j)&nbsp;B = -(d*g-c*l-k*b-h*e+l*a+g*f+i*b+c*h+(i+k)*d+(c+e)*j-((f+d)*i)-((a+c)*j))&nbsp;C = (c+e)*d-((a+c)*d)+a*f-(c*f)-(b*e)+c*b我们可以使用二次公式求解（见右上图）。请注意，可能有两种解决方案。在示例中，我忽略了第二个解决方案。但是，由于第一个可能不在线段上，如果在0 <= u <= 1范围内，您需要保留第二个解决方案，以防第一个失败。您还需要验证该结果。测试为了避免错误，我不得不测试解决方案下面是一个片段，它生成随机的随机线对，然后生成随机线，直到找到截距。感兴趣的功能是movingLineVPoint如果有的话，它返回第一次拦截的单位时间。isPointOnLine来验证结果。const ctx = canvas.getContext("2d");canvas.addEventListener("click",test);const W = 256, H = W, D = (W ** 2 * 2) ** 0.5;canvas.width&nbsp; = W; canvas.height = H;const rand = (m, M) => Math.random() * (M - m) + m;const Tests = 300;var line1, line2, path, count = 0;&nbsp;setTimeout(test, 0);// creating P point L lineconst P = (x,y) => ({x,y,get arr() {return [this.x, this.y]}});&nbsp;const L = (l1, l2) => ({l1,l2,vec: P(l2.x - l1.x, l2.y - l1.y), get arr() {return [this.l1, this.l2]}});&nbsp;const randLine = () => L(P(rand(0, W), rand(0, H)), P(rand(0, W), rand(0, H)));const isPointOnLine = (p, l) =>&nbsp; {&nbsp; &nbsp; const x = p.x - l.l1.x;&nbsp; &nbsp; const y = p.y - l.l1.y;&nbsp; &nbsp; const u = (l.vec.x * x + l.vec.y * y) / (l.vec.x * l.vec.x + l.vec.y * l.vec.y);&nbsp; &nbsp; return u >= 0 && u <= 1;}// See answer illustration for names// arguments in order Px,Py,L1x,l1y,l2x,l2y,V1x,V1y,V2x,V2y,V3x,V3yfunction movingLineVPoint(a,b, c,d, e,f, g,h, i,j, k,l) {&nbsp; &nbsp; var A = -(i*l)-(h*k)+g*l+i*h+(i+k)*j-(g+i)*j;&nbsp; &nbsp; var B = -d*g-c*l-k*b-h*e+l*a+g*f+i*b+c*h+(i+k)*d+(c+e)*j-((f+d)*i)-((a+c)*j)&nbsp; &nbsp; var C = +(c+e)*d-((a+c)*d)+a*f-(c*f)-(b*e)+c*b&nbsp; &nbsp; // Find roots if any. Could be up to 2&nbsp; &nbsp; // Using the smallest root >= 0 and <= 1&nbsp; &nbsp; var u, D, u1, u2;&nbsp; &nbsp; // if A is tiny we can ignore&nbsp; &nbsp; if (Math.abs(A) < 1e-6) {&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; if (B !== 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; u = -C / B;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (u < 0 || u > 1) { return }&nbsp; // !!!!&nbsp; no solution&nbsp; !!!!&nbsp; &nbsp; &nbsp; &nbsp; } else { return }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// !!!!&nbsp; no solution&nbsp; !!!!&nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; B /= A;&nbsp; &nbsp; &nbsp; &nbsp; D = B * B - 4 * (C / A);&nbsp; &nbsp; &nbsp; &nbsp; if (D > 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; D **= 0.5;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; u1 = 0.5 * (-B + D);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; u2 = 0.5 * (-B - D);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if ((u1 < 0 || u1 > 1) && (u2 < 0 || u2 > 1))&nbsp; { return }&nbsp; // !!!!&nbsp; no solution&nbsp; !!!!&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (u1 < 0 || u1 > 1) { u = u2 }&nbsp; &nbsp; &nbsp; &nbsp; // is first out of range&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else if (u2 < 0 || u2 > 1) { u = u1 }&nbsp; &nbsp;// is second out of range&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else if (u1 < u2) { u = u1 }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // first is smallest&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; else { u = u2 }&nbsp; &nbsp; &nbsp; &nbsp; } else if (D === 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; u = 0.5 * -B;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (u < 0 || u > 1)&nbsp; { return }&nbsp; // !!!!&nbsp; no solution&nbsp; !!!!&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; } else { return }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // !!!!&nbsp; no solution&nbsp; !!!!&nbsp;&nbsp; &nbsp; }&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; return u;}function test() {&nbsp; &nbsp;if (count> 0) { return }&nbsp; &nbsp;line1 = randLine();&nbsp; &nbsp;line2 = randLine();&nbsp; &nbsp;count = Tests&nbsp; &nbsp;subTest();}function subTest() {&nbsp; &nbsp;path = randLine()&nbsp; &nbsp;ctx.clearRect(0,0,W,H);&nbsp; &nbsp;drawLines();&nbsp; &nbsp;const u = movingLineVPoint(&nbsp; &nbsp; &nbsp; &nbsp;path.l1.x, path.l1.y,&nbsp; &nbsp; &nbsp; &nbsp;line1.l1.x, line1.l1.y,&nbsp; &nbsp; &nbsp; &nbsp;line2.l1.x, line2.l1.y,&nbsp; &nbsp; &nbsp; &nbsp;path.vec.x, path.vec.y,&nbsp; &nbsp; &nbsp; &nbsp;line1.vec.x, line1.vec.y,&nbsp; &nbsp; &nbsp; &nbsp;line2.vec.x, line2.vec.y&nbsp; &nbsp;);&nbsp; &nbsp;&nbsp; &nbsp;if (u !== undefined) { // intercept found maybe&nbsp; &nbsp; &nbsp; pointAt = P(path.l1.x + path.vec.x * u, path.l1.y + path.vec.y * u);&nbsp; &nbsp; &nbsp; lineAt = L(&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; P(line1.l1.x + line1.vec.x * u, line1.l1.y + line1.vec.y * u),&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; P(line2.l1.x + line2.vec.x * u, line2.l1.y + line2.vec.y * u)&nbsp; &nbsp; &nbsp; );&nbsp; &nbsp; &nbsp; const isOn = isPointOnLine(pointAt, lineAt);&nbsp; &nbsp; &nbsp; if (isOn) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; drawResult(pointAt, lineAt);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; info.textContent = "Found at: u= " + u.toFixed(4) + ". Click for another";&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return;&nbsp; &nbsp; &nbsp; }&nbsp; &nbsp;}&nbsp; &nbsp;setTimeout((--count < 0 ? test : subTest), 18);}&nbsp; &nbsp;function drawLine(line, col = "#000", lw = 1) {&nbsp; &nbsp; ctx.lineWidth = lw;&nbsp; &nbsp; ctx.strokeStyle = col;&nbsp; &nbsp; ctx.beginPath();&nbsp; &nbsp; ctx.lineTo(...line.l1.arr);&nbsp; &nbsp; ctx.lineTo(...line.l2.arr);&nbsp; &nbsp; ctx.stroke();}function markPoint(p, size = 3, col = "#000", lw = 1) {&nbsp; &nbsp; ctx.lineWidth = lw;&nbsp; &nbsp; ctx.strokeStyle = col;&nbsp; &nbsp; ctx.beginPath();&nbsp; &nbsp; ctx.arc(...p.arr, size, 0, Math.PI * 2);&nbsp; &nbsp; ctx.stroke();}function drawLines() {&nbsp; &nbsp;drawLine(line1);&nbsp; &nbsp;drawLine(line2);&nbsp; &nbsp;markPoint(line1.l1);&nbsp; &nbsp;markPoint(line2.l1);&nbsp; &nbsp;drawLine(path, "#0B0", 1);&nbsp; &nbsp;markPoint(path.l1, 2, "#0B0", 2);}function drawResult(pointAt, lineAt) {&nbsp; &nbsp;ctx.clearRect(0,0,W,H);&nbsp; &nbsp;drawLines();&nbsp; &nbsp;markPoint(lineAt.l1, 2, "red", 1.5);&nbsp; &nbsp;markPoint(lineAt.l2, 2, "red", 1.5);&nbsp; &nbsp;markPoint(pointAt, 2, "blue", 3);&nbsp; &nbsp;drawLine(lineAt, "#BA0", 2);}div {position: absolute; top: 10px; left: 12px}canvas {border: 2px solid black}<canvas id="canvas" width="1024" height="1024"></canvas>&nbsp; &nbsp; <div><span id="info">Click to start</span></div>

Answer 2

解决方案有两部分我不明白：解决&nbsp;b^2 - (a^2 + c^2) = 0而不是sqrt(b^2)-(sqrt(a^2)+sqrt(b^2)) = 0返回的时间戳被限制在范围内[0,1]也许我遗漏了一些明显的东西，但无论如何，我设计了一个解决这些问题的解决方案：求解所有二次项，而不仅仅是一个返回的时间戳没有限制sqrt(b^2)-(sqrt(a^2)+sqrt(b^2)) = 0解决了，而不是&nbsp;b^2 - (a^2 + c^2) = 0随意推荐可以优化的方法：# pnt, crt_1, and crt_2 are points, each with x,y and dx,dy attributes# returns a list of timestamps for which pnt is on the segment# whose endpoints are crt_1 and crt_2def colinear_points_collision(pnt, crt_1, crt_2):&nbsp; &nbsp; a, b, c, d = pnt.x, pnt.y, pnt.dx, pnt.dy&nbsp; &nbsp; e, f, g, h = crt_1.x, crt_1.y, crt_1.dx, crt_1.dy&nbsp; &nbsp; i, j, k, l = crt_2.x, crt_2.y, crt_2.dx, crt_2.dy&nbsp; &nbsp; m = a - e&nbsp; &nbsp; n = c - g&nbsp; &nbsp; o = b - f&nbsp; &nbsp; p = d - h&nbsp; &nbsp; q = a - i&nbsp; &nbsp; r = c - k&nbsp; &nbsp; s = b - j&nbsp; &nbsp; u = d - l&nbsp; &nbsp; v = e - i&nbsp; &nbsp; w = g - k&nbsp; &nbsp; x = f - j&nbsp; &nbsp; y = h - l&nbsp; &nbsp; # Left-hand expansion&nbsp; &nbsp; r1 = n * n + p * p&nbsp; &nbsp; r2 = 2 * o * p + 2 * m * n&nbsp; &nbsp; r3 = m * m + o * o&nbsp; &nbsp; r4 = r * r + u * u&nbsp; &nbsp; r5 = 2 * q * r + 2 * s * u&nbsp; &nbsp; r6 = q * q + s * s&nbsp; &nbsp; coef_a = 4 * r1 * r4&nbsp; # t^4 coefficient&nbsp; &nbsp; coef_b = 4 * (r1 * r5 + r2 * r4)&nbsp; # t^3 coefficient&nbsp; &nbsp; coef_c = 4 * (r1 * r6 + r2 * r5 + r3 * r4)&nbsp; # t^2 coefficient&nbsp; &nbsp; coef_d = 4 * (r2 * r6 + r3 * r5)&nbsp; # t coefficient&nbsp; &nbsp; coef_e = 4 * r3 * r6&nbsp; # constant&nbsp; &nbsp; # Right-hand expansion&nbsp; &nbsp; q1 = (w * w + y * y - n * n - p * p - r * r - u * u)&nbsp; &nbsp; q2 = 2 * (v * w + x * y - m * n - o * p - q * r - s * u)&nbsp; &nbsp; q3 = v * v + x * x - m * m - o * o - q * q - s * s&nbsp; &nbsp; coef1 = q1 * q1&nbsp; # t^4 coefficient&nbsp; &nbsp; coef2 = 2 * q1 * q2&nbsp; # t^3 coefficient&nbsp; &nbsp; coef3 = 2 * q1 * q3 + q2 * q2&nbsp; # t^2 coefficient&nbsp; &nbsp; coef4 = 2 * q2 * q3&nbsp; # t coefficient&nbsp; &nbsp; coef5 = q3 * q3&nbsp; # constant&nbsp; &nbsp; # Moves all the coefficients onto one side of the equation to get&nbsp; &nbsp; # at^4 + bt^3 + ct^2 + dt + e&nbsp; &nbsp; # solve for possible values of t&nbsp; &nbsp; p = np.array([coef1 - coef_a, coef2 - coef_b, coef3 - coef_c, coef4 - coef_d, coef5 - coef_e])&nbsp; &nbsp; def fun(x):&nbsp; &nbsp; &nbsp; &nbsp; return p[0] * x**4 + p[1] * x**3 + p[2] * x**2 + p[3] * x + p[4]&nbsp; &nbsp; # could use np.root, but I found this to be more numerically stable&nbsp; &nbsp; sol = optimize.root(fun, [0, 0], tol=0.002)&nbsp; &nbsp; r = sol.x&nbsp; &nbsp; uniques = np.unique(np.round(np.real(r[np.isreal(r)]), 4))&nbsp; &nbsp; final = []&nbsp; &nbsp; for r in uniques[uniques > 0]:&nbsp; &nbsp; &nbsp; &nbsp; if point_between(e + g * r, f + h * r, i + k * r, j + l * r, a + c * r, b + d * r):&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; final.append(r)&nbsp; &nbsp; return np.array(final)# Returns true if the point (px,py) is between the endpoints# of the line segment whose endpoints lay at (ax,ay) and (bx,by)def point_between(ax, ay, bx, by, px, py):&nbsp; &nbsp; # colinear already checked above, this checks between the other two.&nbsp; &nbsp; return (min(ax, bx) <= px <= max(ax, bx) or abs(ax - bx) < 0.001) and (min(ay, by) <= py <= max(ay, by) or abs(ay - by) < 0.001)一个例子（L1 和 L2 是直线的端点）：P = (0,0) with velocity (0, +1)L1 = (-1,2) with velocity (0, -1)L2 = (1,2) with velocity (0, -1)返回的结果是t=1，因为在 1 个时间步后，P 将高出一个单位，而直线的两个端点将分别降低一个单位，因此，该点与线段相交于t=1。