2D 충돌처리
(1) 선과 선
- 두 Line의 직선의 방정식을 구함.
P = P1 + u(P2 - P1), P' = P3 + v(P4 - P3)
교차하는 점에선 P == P'이므로,
P1 + u(P2 - P1) = P3 + v(P4 - P3)
각각 x와 y에 대해 정리
x1 + u(x2 - x1) = x3 + v(x4 - x3)
y1 + u(y2 - y1) = y3 + v(y4 - y3)
두 식을 이용해, u와 v에 대해 풀어낸다.
u = ((x4-x3)*(y1-y3)-(y4-y3)*(x1-x3)) / ((x2-x1)*(y4-y3)-(x4-x3)*(y2-y1))
v = ((x2-x1)*(y1-y3)-(y2-y1)*(x1-x3)) / ((x2-x1)*(y4-y3)-(x4-x3)*(y2-y1))
두 선의 각각의 좌표를 이용해 u와 v의 값을 구할 수 있음.
이 때 u나 v가 0이면 수평, 0 < u < 1이고 0 < v < 1이면 교점이 있는 것임. u나 v가 1보다 크면, 만나지 않는 것임.
구한 u와 v를 직선의 방정식에 대입하면, 교점의 좌표도 구할 수 있음.
(2) 선과 사각형
- 사각형의 네 선분에 대해 선과 선 충돌을 검사.
float inputRotation = MathHelper.ToRadians(degree);
Rectangle destRect = new Rectangle(200, 200, 200, 200);
Vector2 vOrg = new Vector2(1, 0);
vOrg = Vector2.Transform(vOrg, Matrix.CreateRotationZ(inputRotation));
BoundingBox box = new BoundingBox(new Vector3(destRect.Left, destRect.Top, 0.0f),
new Vector3(destRect.Right, destRect.Bottom, 0.0f));
Ray ray = new Ray(new Vector3(vStart, 0.0f), new Vector3(vOrg, 0.0f));
float? result = box.Intersects(ray);
if (result != null && result <= lineLength)
{
// 충돌
}
3D에서 충돌을 감지하는 BoundingBox와 Ray를 2D에서 사용하도록 처리한 것입니다.
3차원을 2차원으로 줄이기 위해 Z 값을 0.0f로 설정했구요.
참고로 ray와 boundingbox간 충돌의 결과는 거리가 나오는 데요.
충돌을 하지 않을 경우에는 null이 나오고, 충돌을 하면 충돌된 거리가 나옵니다.
이 충돌된 거리가 직선의 길이보다 작아야 충돌로 인지하게 처리하면 끝이 납니다.
(3) 선과 원
- 원의 중점Pc 에서 선(P1->P2)에 수직하는 선(최단거리)을 만든다. 선과 수선이 만나는 교점이 선의 범위 안에 있으면 충돌
P = P1 + u(P2 - P1) -> 점 P가 교점이라 하면, (Pc - P) dot (P2 - P1) = 0(내적이 0이면 직각)
식을 풀면 u = (Pc - P1) dot (P2 - P1) / (P2 - P1) dot (P2 - P1)
u < 0이면, P1이 원의 중점으로부터 최단 거리(u == 0 이면 P1이 수직인 좌표)
u > 1이면, P2가 원의 중점으로부터 최단 거리(u == 1 이면 P2가 수직인 좌표)
u값을 처음의 식에 대입하면, 교점 P가 나옴
교점 P에서 원의 중점까지의 거리가 원의 반지름보다 작으면 충돌
(4) 사각형과 사각형
- 두 사각형을 R1과 R2라고 했을때, R1의 네점이 R2에 포함되는지, R2의 네점이 R1에 포함되는지 검사.
하나라도 포함되면, 충돌
(5) 사각형과 원
- 원의 중점에서 사각형의 네 꼭지점에 대한 거리가, 원의 반지름보다 작거나 같은 점이 하나라도 있으면 충돌
(6) 원과 원
- 두 원의 중점간의 거리가 두 원의 반지름의 합보다 작거나 같으면 충돌.
이 글은 두 선분의 교차점을 구하는 알고리즘이 작업에 필요해서 작성해둔 글이다. 참고로, 예전에 두선분의 교차점을 구하는 것 자체가 쉬울 것으로 생각하고 흔히 생각하는 기울기, y 절편을 이용하여 접근하려고 하였다. 이는 상당히 비효율적 방법이였고 조금 더 효율적인 방법으로 접근하였다.
먼저 직선의 방정식으로써, 기울기와 절편으로 나타내지 말고, t 매개변수를 이용해 나타내면 다음과 같다.
P1과 P2는 직선의 시작점과 끝점을 나타내며, t의 범위는 0에서 1까지이다. (P1, P2에서 1, 2는 아래첨자로 생각하기 바란다)
선의 식을 알았으니, 이제 두선의 교점을 구해보는 것으로 응용해보자. 먼저 아래 그림을 보자.
Line1은 P1과 P2로 이루어져 있으며, Line2는 P3와 P4로 이루어져 있다. 두개의 라인을 식으로 표현해보면 다음과 같다.
이미 알겠지만, t와 s는 0에서 1부터의 값이며, 두선의 교점은 두선의 공통된 값이므로 P(t)와 P(s)는 같으므로 위의 2개의 식은 아래의 1개의 식으로 나타낼 수 있다.
( 1 - t ) P1 + tP2 = ( 1 - s ) P3 + sP4
다시 위의 식을 x, y로 분리해보면 아래와 같은 두개의 식들로 분리된다.
x로 분리
P1 = x1; P2 = x2; P3 = x3; P4 = x4;
(1-t)x1 + tx2 = (1-s)x3 + sx4
x1 - tx1 + tx2 = x3 -sx3 + sx4
x1 + t (x1 + x2) = x3 + s (x4 - x3)
y로 분리
P1=y1; P2 = y2; P3=y3; P4=y4;
y1 + t (y1 + y2) = y3 + s (y4 - y3)
위의 식을 t와 s에 대해서 정리를 해보면 다음과 같다.
즉, 위의 t와 s는 두선이 서로 만날때의 값이므로, 최종적으로 두선의 교점은 다음과 같이 나타낼 수 있다.
위의 x, y가 우리가 구하고자하는 두 직선의 교점이다.
마지막으로 t와 s에 대해 정리해 보도록 하자.
s와 t의 값이 0과 1 사이를 벗어나는 경우, 두 선은 교차하지 않는다고 판정해야 한다. 그리고 s와 t를 구하는 공식에서 분모가 0인 경우 두 선은 평행하다는 의미이므로 교점은 존재하지 않다. 분모와 분자 모두 0인 경우 두 선은 동일한 선이다.
아래의 코드는 위의 설명을 토대로 작성하였다.
bool checkCross(const CPoint& AP1, const CPoint& AP2, const CPoint& BP1, const CPoint& BP2, CPoint* IP)
{
double t;
double s;
double under = (BP2.y-BP1.y)*(AP2.x-AP1.x)-(BP2.x-BP1.x)*(AP2.y-AP1.y);
if(under==0) return false;
double _t = (BP2.x-BP1.x)*(AP1.y-BP1.y) - (BP2.y-BP1.y)*(AP1.x-BP1.x);
double _s = (AP2.x-AP1.x)*(AP1.y-BP1.y) - (AP2.y-AP1.y)*(AP1.x-BP1.x);
t = _t/under;
s = _s/under;
if(t<0.0 || t>1.0 || s<0.0 || s>1.0) return false;
if(_t==0 && _s==0) return false;
IP->x = AP1.x + t * (double)(AP2.x-AP1.x);
IP->y = AP1.y + t * (double)(AP2.y-AP1.y);
return true;
}
2020/12/15 - [iOS/Tips] - 디버깅 차단 처리 (Anti Debug)
2020/12/14 - [iOS/Tips] - bundle id 알아내기
2020/12/12 - [AI/Algorithm] - 2D 충돌처리
2020/12/11 - [iOS/Swift] - UIViewController 스위칭
2020/12/11 - [개발노트] - PlantUML 설치 (Mac OS X)
2020/12/10 - [iOS/Objective-C] - 웹뷰에서 javascript 함수 동기식 호출
2020/12/10 - [iOS/Tips] - Fat Static Library 빌드 (2/2)
2020/12/10 - [iOS/Tips] - Fat Static Library 빌드 (1/2)
2020/12/10 - [iOS/Tips] - Custom UserAgent 설정
2020/12/10 - [iOS/Tips] - CocoaPods 설치 및 제거
2020/12/10 - [iOS/Tips] - Clang diagnostic 경고 무시하기
2020/12/10 - [개발노트] - Bluetooth UUID
2020/12/08 - [개발노트] - 모바일 앱 메모리덤프 이슈 해결방법
2020/12/08 - [프로그래밍/Java Script] - Android, iOS 앱 설치여부 체크 및 스토어 이동
'개발 > AI,ML,ALGORITHM' 카테고리의 다른 글
| MNIST 데이터셋 다운로드 (0) | 2023.07.19 |
|---|---|
| Neural Network (XOR) (0) | 2022.11.18 |
| Generic algorithm (0) | 2020.05.19 |
| neural network (0) | 2020.05.19 |
| minimax full search example (0) | 2020.05.19 |
SKY STORY
