我正在研究一個(gè) 2D 對(duì)撞機(jī)系統(tǒng)，該系統(tǒng)將形狀分解為一個(gè)可能的基元：由兩點(diǎn)定義的不可穿透的部分。為了為該系統(tǒng)提供碰撞檢測(cè)，我使用了一種靜態(tài)碰撞檢測(cè)方法，該方法每幀計(jì)算一次線段的邊緣與當(dāng)前處理的線段之間的距離（點(diǎn)/線距離）。如果距離太小，則在該幀期間觸發(fā)碰撞。這工作正常，但如果一個(gè)或多個(gè)物體表現(xiàn)出高速，則會(huì)出現(xiàn)已知的隧道問(wèn)題。所以我正在修補(bǔ)替代品。現(xiàn)在我想介紹在動(dòng)態(tài)點(diǎn)/動(dòng)態(tài)段上運(yùn)行的連續(xù)碰撞檢測(cè)（CCD）。我的問(wèn)題是：我不知道怎么做。我知道如何在兩個(gè)移動(dòng)點(diǎn)、移動(dòng)點(diǎn)和靜態(tài)段之間進(jìn)行連續(xù)碰撞，但不知道如何在移動(dòng)點(diǎn)（由點(diǎn) P 定義）和移動(dòng)段（由點(diǎn) U 和 V 定義，兩者都可以）之間進(jìn)行 CCD完全自由移動(dòng)）。但沒(méi)有提出這些確切的要求：點(diǎn)和線段都在移動(dòng)段可以旋轉(zhuǎn)和拉伸（因?yàn)?U 和 V 可以自由移動(dòng)）需要準(zhǔn)確找到兩幀之間的碰撞時(shí)間和碰撞點(diǎn)（CCD，無(wú)靜態(tài)碰撞測(cè)試）如果可能的話，我更喜歡數(shù)學(xué)上完美的解決方案（沒(méi)有迭代近似算法，掃描體積）注意：掃掠線形狀并不總是凸多邊形，因?yàn)?U、V 點(diǎn)的自由度注意：測(cè)試與掃描體積的碰撞測(cè)試是不準(zhǔn)確的，因?yàn)榕c多邊形的碰撞點(diǎn)并不意味著實(shí)際運(yùn)動(dòng)中的碰撞點(diǎn)（參見(jiàn)圖像，一旦實(shí)際段穿過(guò)軌跡，該點(diǎn)將離開(kāi)多邊形點(diǎn)）到目前為止，我想出了以下方法，給出：sP（幀開(kāi)始時(shí)的 P），eP（幀末尾的 P），sU（幀開(kāi)始處的 U），eU（幀末尾的 U），sV（幀開(kāi)始時(shí)的 V），eV（幀末尾的 V）問(wèn)題：它們會(huì)碰撞嗎？如果是，何時(shí)何地？解決方案：將幀中每個(gè)點(diǎn)的時(shí)間軌跡建模為線性運(yùn)動(dòng)（0 <= t <= 1的線軌跡）P(t) = sP * (1 - t) + eP * tU(t) = sU * (1 - t) + eU * tV(t) = sV * (1 - t) + eV * t（0 <= a <= 1表示由 U 和 V 定義的線段上的位置）：UV(a, t) = U(t) * (1 - a) + V(t) * a通過(guò)使點(diǎn)和線段方程相等來(lái)模擬碰撞：P(t) = UV(a, t)P(t) = U(t) * (1 - a) + V(t) * a為從點(diǎn) P 到線段上的點(diǎn)的向量導(dǎo)出一個(gè)函數(shù)：F(a, t) = P(t) - (1 - a) * U(t) - a * V(t)現(xiàn)在要找到碰撞，需要找到a和t，以便F(a, t) = (0, 0)和[0, 1] 中的 a,t。這可以建模為具有 2 個(gè)變量的尋根問(wèn)題。將時(shí)間軌跡方程插入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）分離時(shí)間軌跡方程：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)現(xiàn)在我們有兩個(gè)方程和兩個(gè)要求解的變量（分別為Fx、Fy和a、t），因此我們應(yīng)該能夠使用求解器來(lái)獲得a和t，然后檢查它們是否位于 [0, 1]..對(duì)嗎？
2 回答
LEATH
TA貢獻(xiàn)1936條經(jīng)驗(yàn) 獲得超7個(gè)贊
TLDR
我確實(shí)讀過(guò)“……大約 5 分鐘來(lái)評(píng)估……”
沒(méi)辦法太長(zhǎng)，這是一個(gè)針對(duì)許多線和點(diǎn)的實(shí)時(shí)解決方案。
抱歉，這不是一個(gè)完整的答案（我沒(méi)有合理化和簡(jiǎn)化方程式），它將找到我留給你的截距點(diǎn)。
我還可以看到解決方案的幾種方法，因?yàn)樗鼑@一個(gè)三角形（見(jiàn)圖）旋轉(zhuǎn)，當(dāng)平面是解決方案時(shí)。下面的方法找到三角形的長(zhǎng)邊等于短邊之和的時(shí)間點(diǎn)。
求解你（時(shí)間）
這可以作為一個(gè)簡(jiǎn)單的二次方程來(lái)完成，其系數(shù)從 3 個(gè)起點(diǎn)導(dǎo)出，每個(gè)點(diǎn)的單位時(shí)間向量。為你解決
下圖提供了更多詳細(xì)信息。
點(diǎn)P是點(diǎn)的起始pos
點(diǎn)L1、L2是線端的起點(diǎn)。
矢量V1是單位時(shí)間內(nèi)（沿綠線）的點(diǎn)。
矢量V2、V3用于單位時(shí)間內(nèi)的線路末端。
u是單位時(shí)間
A是點(diǎn)（藍(lán)色），B和C是線端點(diǎn)（紅色）
存在（可能）一個(gè)時(shí)間點(diǎn)u，其中A在B和C線上。此時(shí)，線AB（作為a）和AC（作為c）的長(zhǎng)度總和等于線BC（作為b）（橙色線）的長(zhǎng)度。
這意味著當(dāng)b - (a + c) == 0時(shí)，該點(diǎn)在線上。在圖像中，點(diǎn)被平方，因?yàn)檫@稍微簡(jiǎn)化了它。b 2 - (a 2 + c 2 ) == 0
圖像底部是根據(jù)u, P, L1, L2, V1, V2, V3 的方程（二次） 。
該等式需要重新排列，以便得到(???)u 2 + (???)u + (???) = 0
抱歉，手動(dòng)執(zhí)行此操作非常乏味且很容易出錯(cuò)。我手頭沒(méi)有工具，也不使用 python，所以我不知道你使用的數(shù)學(xué)庫(kù)。但是它應(yīng)該能夠幫助您找到如何計(jì)算(???)u 2 + (???)u + (???) = 0 的系數(shù)
更新
忽略上面的大部分內(nèi)容，因?yàn)槲曳噶艘粋€(gè)錯(cuò)誤。b - (a + c) == 0與b 2 - (a 2 + c 2 ) == 0不同。第一個(gè)是需要的，這是處理部首時(shí)的一個(gè)問(wèn)題（請(qǐng)注意，仍然可以使用 虛數(shù)a + bi == sqrt(a^2 + b^2)在哪里的解決方案）。i
另一種解決方案
所以我探索了其他選擇。
最簡(jiǎn)單的有一個(gè)小缺陷。它將返回?cái)r截時(shí)間。但是，必須對(duì)其進(jìn)行驗(yàn)證，因?yàn)樗€會(huì)在攔截線時(shí)返回?cái)r截時(shí)間，而不是線段BC
因此，當(dāng)找到結(jié)果時(shí)，您可以通過(guò)將找到的點(diǎn)和線段的點(diǎn)積除以線段長(zhǎng)度的平方來(lái)測(cè)試它。isPointOnLine請(qǐng)參閱測(cè)試片段中的功能。
為了解決這個(gè)問(wèn)題，我使用了這樣一個(gè)事實(shí)，即當(dāng)點(diǎn)在線上時(shí)，線BC與從B到A的向量的叉積將為 0。
一些重命名
使用上圖，我重命名了變量，這樣我就可以更輕松地完成所有繁瑣的工作。
/*
point P is {a,b}
point L1 is {c,d}
point L2 is {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 */
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))
/*
thus Vbax * Vbcy - Vbay * Vbcx == 0 at intercept
*/
這給出了二次
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
因此系數(shù)是
A = -((i*l)-(h*k)+g*l+i*h+(i+k)*j-(g+i)*j)
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))
C = (c+e)*d-((a+c)*d)+a*f-(c*f)-(b*e)+c*b
我們可以使用二次公式求解（見(jiàn)右上圖）。
請(qǐng)注意，可能有兩種解決方案。在示例中，我忽略了第二個(gè)解決方案。但是，由于第一個(gè)可能不在線段上，如果在0 <= u <= 1范圍內(nèi)，您需要保留第二個(gè)解決方案，以防第一個(gè)失敗。您還需要驗(yàn)證該結(jié)果。
測(cè)試
為了避免錯(cuò)誤，我不得不測(cè)試解決方案
下面是一個(gè)片段，它生成隨機(jī)的隨機(jī)線對(duì)，然后生成隨機(jī)線，直到找到截距。
感興趣的功能是
movingLineVPoint如果有的話，它返回第一次攔截的單位時(shí)間。isPointOnLine來(lái)驗(yàn)證結(jié)果。
const ctx = canvas.getContext("2d");
canvas.addEventListener("click",test);
const W = 256, H = W, D = (W ** 2 * 2) ** 0.5;
canvas.width = W; canvas.height = H;
const rand = (m, M) => Math.random() * (M - m) + m;
const Tests = 300;
var line1, line2, path, count = 0;
setTimeout(test, 0);
// creating P point L line
const P = (x,y) => ({x,y,get arr() {return [this.x, this.y]}});
const L = (l1, l2) => ({l1,l2,vec: P(l2.x - l1.x, l2.y - l1.y), get arr() {return [this.l1, this.l2]}});
const randLine = () => L(P(rand(0, W), rand(0, H)), P(rand(0, W), rand(0, H)));
const isPointOnLine = (p, l) => {
const x = p.x - l.l1.x;
const y = p.y - l.l1.y;
const u = (l.vec.x * x + l.vec.y * y) / (l.vec.x * l.vec.x + l.vec.y * l.vec.y);
return u >= 0 && u <= 1;
}
// See answer illustration for names
// arguments in order Px,Py,L1x,l1y,l2x,l2y,V1x,V1y,V2x,V2y,V3x,V3y
function movingLineVPoint(a,b, c,d, e,f, g,h, i,j, k,l) {
var A = -(i*l)-(h*k)+g*l+i*h+(i+k)*j-(g+i)*j;
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)
var C = +(c+e)*d-((a+c)*d)+a*f-(c*f)-(b*e)+c*b
// Find roots if any. Could be up to 2
// Using the smallest root >= 0 and <= 1
var u, D, u1, u2;
// if A is tiny we can ignore
if (Math.abs(A) < 1e-6) {
if (B !== 0) {
u = -C / B;
if (u < 0 || u > 1) { return } // !!!! no solution !!!!
} else { return } // !!!! no solution !!!!
} else {
B /= A;
D = B * B - 4 * (C / A);
if (D > 0) {
D **= 0.5;
u1 = 0.5 * (-B + D);
u2 = 0.5 * (-B - D);
if ((u1 < 0 || u1 > 1) && (u2 < 0 || u2 > 1)) { return } // !!!! no solution !!!!
if (u1 < 0 || u1 > 1) { u = u2 } // is first out of range
else if (u2 < 0 || u2 > 1) { u = u1 } // is second out of range
else if (u1 < u2) { u = u1 } // first is smallest
else { u = u2 }
} else if (D === 0) {
u = 0.5 * -B;
if (u < 0 || u > 1) { return } // !!!! no solution !!!!
} else { return } // !!!! no solution !!!!
}
return u;
}
function test() {
if (count> 0) { return }
line1 = randLine();
line2 = randLine();
count = Tests
subTest();
}
function subTest() {
path = randLine()
ctx.clearRect(0,0,W,H);
drawLines();
const u = movingLineVPoint(
path.l1.x, path.l1.y,
line1.l1.x, line1.l1.y,
line2.l1.x, line2.l1.y,
path.vec.x, path.vec.y,
line1.vec.x, line1.vec.y,
line2.vec.x, line2.vec.y
);
if (u !== undefined) { // intercept found maybe
pointAt = P(path.l1.x + path.vec.x * u, path.l1.y + path.vec.y * u);
lineAt = L(
P(line1.l1.x + line1.vec.x * u, line1.l1.y + line1.vec.y * u),
P(line2.l1.x + line2.vec.x * u, line2.l1.y + line2.vec.y * u)
);
const isOn = isPointOnLine(pointAt, lineAt);
if (isOn) {
drawResult(pointAt, lineAt);
count = 0;
info.textContent = "Found at: u= " + u.toFixed(4) + ". Click for another";
return;
}
}
setTimeout((--count < 0 ? test : subTest), 18);
}
function drawLine(line, col = "#000", lw = 1) {
ctx.lineWidth = lw;
ctx.strokeStyle = col;
ctx.beginPath();
ctx.lineTo(...line.l1.arr);
ctx.lineTo(...line.l2.arr);
ctx.stroke();
}
function markPoint(p, size = 3, col = "#000", lw = 1) {
ctx.lineWidth = lw;
ctx.strokeStyle = col;
ctx.beginPath();
ctx.arc(...p.arr, size, 0, Math.PI * 2);
ctx.stroke();
}
function drawLines() {
drawLine(line1);
drawLine(line2);
markPoint(line1.l1);
markPoint(line2.l1);
drawLine(path, "#0B0", 1);
markPoint(path.l1, 2, "#0B0", 2);
}
function drawResult(pointAt, lineAt) {
ctx.clearRect(0,0,W,H);
drawLines();
markPoint(lineAt.l1, 2, "red", 1.5);
markPoint(lineAt.l2, 2, "red", 1.5);
markPoint(pointAt, 2, "blue", 3);
drawLine(lineAt, "#BA0", 2);
}
div {position: absolute; top: 10px; left: 12px}
canvas {border: 2px solid black}
<canvas id="canvas" width="1024" height="1024"></canvas>
<div><span id="info">Click to start</span></div>
有只小跳蛙
TA貢獻(xiàn)1824條經(jīng)驗(yàn) 獲得超8個(gè)贊
解決方案有兩部分我不明白：
解決
b^2 - (a^2 + c^2) = 0而不是sqrt(b^2)-(sqrt(a^2)+sqrt(b^2)) = 0返回的時(shí)間戳被限制在范圍內(nèi)
[0,1]
也許我遺漏了一些明顯的東西，但無(wú)論如何，我設(shè)計(jì)了一個(gè)解決這些問(wèn)題的解決方案：
求解所有二次項(xiàng)，而不僅僅是一個(gè)
返回的時(shí)間戳沒(méi)有限制
sqrt(b^2)-(sqrt(a^2)+sqrt(b^2)) = 0解決了，而不是b^2 - (a^2 + c^2) = 0
隨意推薦可以優(yōu)化的方法：
# 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_2
def colinear_points_collision(pnt, crt_1, crt_2):
a, b, c, d = pnt.x, pnt.y, pnt.dx, pnt.dy
e, f, g, h = crt_1.x, crt_1.y, crt_1.dx, crt_1.dy
i, j, k, l = crt_2.x, crt_2.y, crt_2.dx, crt_2.dy
m = a - e
n = c - g
o = b - f
p = d - h
q = a - i
r = c - k
s = b - j
u = d - l
v = e - i
w = g - k
x = f - j
y = h - l
# Left-hand expansion
r1 = n * n + p * p
r2 = 2 * o * p + 2 * m * n
r3 = m * m + o * o
r4 = r * r + u * u
r5 = 2 * q * r + 2 * s * u
r6 = q * q + s * s
coef_a = 4 * r1 * r4 # t^4 coefficient
coef_b = 4 * (r1 * r5 + r2 * r4) # t^3 coefficient
coef_c = 4 * (r1 * r6 + r2 * r5 + r3 * r4) # t^2 coefficient
coef_d = 4 * (r2 * r6 + r3 * r5) # t coefficient
coef_e = 4 * r3 * r6 # constant
# Right-hand expansion
q1 = (w * w + y * y - n * n - p * p - r * r - u * u)
q2 = 2 * (v * w + x * y - m * n - o * p - q * r - s * u)
q3 = v * v + x * x - m * m - o * o - q * q - s * s
coef1 = q1 * q1 # t^4 coefficient
coef2 = 2 * q1 * q2 # t^3 coefficient
coef3 = 2 * q1 * q3 + q2 * q2 # t^2 coefficient
coef4 = 2 * q2 * q3 # t coefficient
coef5 = q3 * q3 # constant
# Moves all the coefficients onto one side of the equation to get
# at^4 + bt^3 + ct^2 + dt + e
# solve for possible values of t
p = np.array([coef1 - coef_a, coef2 - coef_b, coef3 - coef_c, coef4 - coef_d, coef5 - coef_e])
def fun(x):
return p[0] * x**4 + p[1] * x**3 + p[2] * x**2 + p[3] * x + p[4]
# could use np.root, but I found this to be more numerically stable
sol = optimize.root(fun, [0, 0], tol=0.002)
r = sol.x
uniques = np.unique(np.round(np.real(r[np.isreal(r)]), 4))
final = []
for r in uniques[uniques > 0]:
if point_between(e + g * r, f + h * r, i + k * r, j + l * r, a + c * r, b + d * r):
final.append(r)
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):
# colinear already checked above, this checks between the other two.
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)
一個(gè)例子（L1 和 L2 是直線的端點(diǎn)）：
P = (0,0) with velocity (0, +1)
L1 = (-1,2) with velocity (0, -1)
L2 = (1,2) with velocity (0, -1)
返回的結(jié)果是t=1，因?yàn)樵?1 個(gè)時(shí)間步后，P 將高出一個(gè)單位，而直線的兩個(gè)端點(diǎn)將分別降低一個(gè)單位，因此，該點(diǎn)與線段相交于t=1。
添加回答
舉報(bào)
0/150
提交
取消