움직이는 지점과 움직이는 선분의 충돌 위치 및 시간 (연속 충돌 감지)
저는 모양을 하나의 가능한 기본 요소로 나누는 2D 충돌체 시스템에서 작업하고 있습니다. 두 점으로 정의되는 뚫을 수없는 세그먼트입니다. 이 시스템에 대한 충돌 감지를 제공하기 위해 프레임마다 한 번씩 한 세그먼트의 가장자리와 현재 처리 된 세그먼트 (포인트 / 라인 거리) 사이의 거리를 계산하는 정적 충돌 감지 방식을 사용하고 있습니다. 거리가 너무 작 으면 해당 프레임 동안 충돌이 발생합니다. 이것은 잘 작동하지만 하나 이상의 몸체가 고속을 나타내는 경우 터널링이라는 알려진 문제가 있습니다. 그래서 저는 대안을 고민하고 있습니다.
이제 동적 포인트 / 동적 세그먼트에서 작동하는 연속 충돌 감지 (CCD)를 소개하고 싶습니다. 내 문제는 : 정확히 어떻게하는지 모르겠습니다. 두 이동 지점, 이동 지점과 정적 세그먼트간에 연속 충돌을 수행하는 방법을 알고 있지만 이동 지점 (포인트 P로 정의 됨)과 이동 세그먼트 (포인트 U 및 V로 정의 됨)간에 CCD를 수행하는 방법은 알 수 없습니다. 완전히 자유롭게 움직입니다).
문제의 그림
SO 및 기타 플랫폼에서 유사한 질문을 받았지만 다음과 같은 정확한 요구 사항이 없습니다.
- 점과 세그먼트가 모두 움직이고 있습니다.
- 세그먼트는 회전 및 늘일 수 있습니다 (U와 V가 자유롭게 움직이기 때문에)
- 충돌 시간과 충돌 지점은 두 프레임 사이에서 정확하게 찾아야합니다 (CCD, 정적 충돌 테스트 없음).
- 가능한 경우 수학적으로 완벽한 솔루션을 선호합니다 (반복 근사 알고리즘 없음, 스윕 볼륨 없음).
- 참고 : U, V 점의 자유로 인해 스윕 된 선 모양이 항상 볼록 다각형이되는 것은 아닙니다 ( 이미지 참조 ).
- 참고 : 다각형과의 충돌 지점이 실제 움직임에서 충돌 지점을 의미하지 않기 때문에 스윕 된 볼륨 테스트를 통한 충돌 테스트는 정확하지 않습니다 ( 이미지 참조 , 실제 세그먼트가 궤적을 통과하면 지점이 다각형을 떠났습니다. 요점)
지금까지 나는 다음과 같은 접근 방식 내놓았다 주어진 :
- sP (프레임 시작시 P),
- eP (프레임 끝의 P),
- sU (프레임 시작시 U),
- eU (프레임 끝의 U),
- sV (프레임 시작시 V),
- eV (프레임 끝의 V)
질문 : 충돌할까요? 그렇다면 언제 어디서?
"if"라는 질문에 답하기 위해이 문서가 유용하다는 것을 알았습니다. https://www.cs.ubc.ca/~rbridson/docs/brochu-siggraph2012-ccd.pdf(섹션 3.1) "언제"와 "어디"에 대한 답을 도출 할 수 없었습니다. 또한 여기에서 문제에 대한 다른 설명을 찾았습니다.http://15462.courses.cs.cmu.edu/fall2018/article/13 (세 번째 질문)
해결책 :
프레임 동안 각 지점의 시간 궤적을 선형 이동으로 모델링합니다 ( 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 그림 참조 ).
- F (a, t) = P (t)-(1-a) * U (t)-a * V (t)
이제 충돌을 찾으려면 a 및 t 를 찾아야 합니다 . 따라서 [0, 1]에서 F (a, t) = (0, 0) 및 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] .. 맞죠?
이것을 파이썬 sympy에 연결하면 다음과 같이 해결됩니다.
from sympy import symbols, Eq, solve, nsolve
def main():
sxP = symbols("sxP")
syP = symbols("syP")
exP = symbols("exP")
eyP = symbols("eyP")
sxU = symbols("sxU")
syU = symbols("syU")
exU = symbols("exU")
eyU = symbols("eyU")
sxV = symbols("sxV")
syV = symbols("syV")
exV = symbols("exV")
eyV = symbols("eyV")
a = symbols("a")
t = symbols("t")
eq1 = Eq((sxP * (1 - t) + exP * t) - (1 - a) * (sxU * (1 - t) + exU * t) - a * (sxV * (1 - t) + exV * t))
eq2 = Eq((syP * (1 - t) + eyP * t) - (1 - a) * (syU * (1 - t) + eyU * t) - a * (syV * (1 - t) + eyV * t))
sol = solve((eq1, eq2), (a, t), dict=True)
print(sol)
if __name__ == "__main__":
main()
나는 거대한 크기의 솔루션을 얻었으며 평가하는 데 5 분 정도 걸립니다. 실제 엔진 코드에서 그렇게 큰 표현을 사용할 수 없으며이 솔루션은 나에게 옳지 않은 것 같습니다.
내가 알고 싶은 것은 : 여기에 뭔가 빠졌나요? 이 문제는 이해하기 쉬운 것 같지만 동적 포인트 / 동적 세그먼트에 대한 영향 솔루션 의 시간 ( t )과 포인트 ( a ) 를 찾는 수학적으로 정확한 방법을 알아낼 수 없습니다 . 누군가가 그렇게 할 수 없다고 말하더라도 어떤 도움이라도 대단히 감사합니다.
답변
TLDR
"... 평가하는 데 5 분 정도 ..."를 읽었습니다.
너무 길지 않습니다. 이것은 많은 선과 점에 대한 실시간 솔루션입니다.
죄송합니다. 이것은 요격 지점을 찾을 완전한 대답이 아닙니다 (방정식을 합리화하지 않고 단순화하지 않았습니다).
또한 삼각형 (이미지 참조)을 중심으로 회전하므로 솔루션에 대한 몇 가지 접근 방식을 볼 수 있습니다. 아래 접근 방식은 삼각형의 긴 변이 짧은 두 변의 합과 같은 시점을 찾습니다.
u (시간)에 대한 해결
이것은 각 점의 단위 시간에 대한 벡터 인 3 개의 시작점에서 파생 된 계수를 사용하여 단순 2 차로 수행 할 수 있습니다. 당신을 위해 해결
아래 이미지는 자세한 내용을 제공합니다.
- 점 P 는 점 의 시작 위치입니다.
- 점 L1 , L2 는 선 끝의 시작점입니다.
- 벡터 V1 은 단위 시간 동안 (녹색 선을 따라) 점에 대한 것입니다.
- 벡터 V2 , V3 은 단위 시간 동안의 라인 끝을위한 것입니다.
- u 는 단위 시간입니다.
- A 는 점 (파란색)이고 B 와 C 는 선 끝점 (빨간색)입니다.
A 가 라인 B , C 에있는 시점 u 가 있을 수 있습니다 . 이 시점에서 라인 AB ( a )와 AC ( c )의 길이는 BC 라인 ( b ) (주황색 라인) 의 길이와 같습니다 .
이는 b-(a + c) == 0 일 때 점이 선 위에 있음을 의미합니다. 이미지에서 점은 약간 단순화되므로 제곱됩니다. b 2- (a 2 + c 2 ) == 0
이미지 하단에는 u, P, L1, L2, V1, V2, V3 측면에서 방정식 (2 차)이 있습니다.
이 방정식은 (???) u 2 + (???) u + (???) = 0 이되도록 재정렬해야합니다.
수동으로 수행하는 것은 매우 지루하고 실수하기 쉽습니다. 나는 그것을 할 수있는 도구가 없으며 파이썬을 사용하지 않으므로 사용중인 수학 라이브러리를 알 수 없습니다. 그러나 (???) u 2 + (???) 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 {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
*/
이것은 2 차
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
따라서 계수는
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
2 차 공식을 사용하여 풀 수 있습니다 (오른쪽 상단 이미지 참조).
참고 두 가지 솔루션이있을 수있다. 예제에서는 두 번째 솔루션을 무시했습니다. 그러나 첫 번째가 선분에 있지 않을 수 있으므로 첫 번째가 실패 할 경우를 대비하여 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 = 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>