[DX] AABB, OBB 충돌

AABB (Axis-Aligned Bounding Box, 축 정렬 경계 상자)

AABB 충돌은 객체를 좌표축에 평행하는 직육면체의 상자를 만들고, 이 상자들이 서로 겹치는지를 확인하여 객체 간에 충돌을 판단하는 방법입니다. 박스가 좌표 축에 정렬되어 있기 때문에, 박스를 이루는 면의 노말 벡터들이 곧 X, Y, Z 축과 일치하는 모양입니다. 따라서 객체의 x, y, z 좌표의 최솟점과 최댓점을 구하여 정의가 가능합니다.

최솟점과 최댓점의 차에 0.5를 곱해 AABB의 중점과 거리를 구할 수 있습니다.
중점 = 0.5 (Vmin - Vmax)
거리 = 0.5 (Vmax - Vmin)

이러한 방법으로, 회전함에 따라 객체의 크기도 계속 변하게 되고, 축에 일치된 모양이기 때문에 AABB끼리의 충돌 검출은 매우 간편하게 계산됩니다.

 

OBB(Oriented Bounding Box, 회전된 경계 상자)

OBB 충돌은 물체가 회전함에 따라 같이 회전하여, 객체를 둘러싸는 방향의 직육면체 상자를 만들고, 이 상자들이 서로 겹치는지를 확인하여 객체 간의 충돌을 판단하는 방법입니다.

여기서 Oriented는 Box의 축이 표준 좌표죽에 정렬되지 않아도 됨을 의미하므로 대상 객체를 더 정확하게 포함하여 충돌을 검사할 수 있습니다. 이는 AABB보다 정밀한 교차검출이 가능하게 하지만, 그만큼 복잡한 연산을 수행해야 합니다.

 

OBB 충돌에서 필요한 회전 정보는 사원수를 사용했는데, 이는 회전행렬을 받는 것보다 데이터가 훨씬 적기 때문입니다.

사원수 (Quaternion, 쿼터니언)란?
3차원 그래픽에서 회전을 표현할 때, 행렬 대신 사용하는 수학적 개념으로 4개의 값으로 이루어진 복소수 체계이다. (복소수는 가장 큰 숫자 단위로 실수와 허수로 이루어져 있다)

사원수는 행렬에 비해 연산속도가 빠르고, 차지하는 메모리 양도 적고, 결과의 질에 있어서 오류가 날 확률이 적다.

사원수를 사용하는 예시 중에는 짐벌락이 있다.
3개의 축에 대한 회전 연산을 동시에 적용하는 경우 행렬을 사용하면 한 축이 소실되는 짐벌락 현상이 발생할 수 있는데, 이때 사원수(쿼터니언)을 사용하면 이를 막을 수 있다.

4개의 값으로 이루어진 쿼터니언은 q = <w, x, y, z> = w + xi + yj + zk 로 나타낼 수 있고,
w에 해당하는 스칼라 s값과 x, y, z 에 해당하는 벡터 q로 표현하는 q = s + v 형태로 쓰기도 한다.

 

OBB 충돌은 분리 축 이론을 기반으로 동작합니다.

분리 축 이론이란, 두 볼록 다면체(다각형)을 분리할 수 있는 선(축)이 있다면, 두 볼록 다면체는 충돌하지 않았다고 판별하는 것입니다. 따라서, OBB는 경계상자가 직사각형 뿐만 아니라 다른 볼록 다면체와 다각형들에도 적용할 수 있습니다.

 

분리축 이론을 수행하기 위해 두 OBB의 모든 축을 비교하여, 각각의 축에 대해 투영하는 구간을 계산하고, 이러한 구간이 서로 겹치는지를 검사합니다.

만약, 모든 축에서 투영이 겹친다면 두 OBB는 충돌하는 것이고, 하나의 축에서라도 겹치지 않는다면 두 OBB는 충돌하지 않는 것입니다.

 

도형의 분리 축 선정방법

분리축은 도형의 노멀벡터를 이용하여 구할 수 있습니다. 한 점에서, 다음 점을 바라보는 벡터를 구하고 그 벡터의 길이가 1인 수직벡터가 분리축이 됩니다.

분리축은 방향과 위치에 따라 겹쳐져있거나 겹쳐져 있지 않음이 달라질 수 있으므로, 한번만 구하면 안되고 모든 분리축을 체크해야 합니다.

 

분리 축 충돌 계산법 (SAT Algorithm)

SAT Algorithm은 폴리곤의 충돌 알고리즘 중 하나로 볼록 다각형에서만 유효한 알고리즘입니다.

볼록 다각형 (Convex Polygon)
1. 다각형의 내각이 항상 180도 보다 작아야 한다.
2. 다각형의 꼭지점을 이은 선들은 항상 다각형 안에 있다.

오목 다각형 (Concave Polygon)
1. 적어도 하나의 다각형의 내각이 180도 보다 크다.
2. 다각형의 꼭지점을 이은 선들 중 적어도 하나는 다각형 안에 없다.

 

 

충돌 계산법을 수식으로 나타낸 그림입니다. 위 수식이 참일 경우 충돌이 되었다고 판정하고, 거짓일 경우 충돌이 되지 않았다고 판정합니다.

 

조금 더 자세한 OBB 충돌 판별 과정을 설명하면 아래와 같습니다.

1. 충돌을 판별할 도형 중 한 변의 수직인 법선벡터(Normal Vector) v를 구한다.
2. 각 도형에서 해당 법선 벡터를 기준으로 투영될 수 있는 최대, 최소인 점을 구한다.
3. 해당 점들을 법선 벡터에 투영시킨 벡터를 구한다.
3-1. 이때, 법선 벡터에 투영시키는 벡터(S1 min → S2 max, S2 min → S1 max)를 법선벡터 v에 내적한다.
4. 점들의 방향벡터와 법선벡터의 내적 결과의 곱이 양수인 경우엔 충돌이 된것이고, 음수인 경우엔 충돌되지 않은 것이다.

 

(자세한 설명과 예시를 PPT로 잘 정리해주신 출처 사이트를 참고하면 더 좋다.)

출처: https://www.slideshare.net/ssuserbe87d6/collision-detection-algorithms?qid=d75a9483-0b7a-454a-8797-d3b24c6c4deb&v=&b=&from_search=3 

충돌 알고리즘(collision detection algorithms)

 

3D 에서의 분리 축 판별은 물체의 변이 분리축이 되는 2D와 달리, 평면이 분리축이 되기 때문에 고려해야 하는 경우의 수가 많습니다.

만약, 큐브 모양의 경계 상자를 충돌한다고 가정할 때 총 15가지의 경우의 수가 존재합니다.

 

A, B 각각의 평면 벡터 3개 + 3개 = 6개
A의 변 벡터 (좌표축) <외적> B의 변 벡터(좌표축) : 3개 * 3개 = 9개

6 + 9 = 15가지의 분리축 비교

 

번외 - Sphere 충돌

https://mathmakeworld.tistory.com/106

Sphere을 보면 center 값과 Radius 값을 각각 가집니다. 이때 두 원형의 정점 간의 거리가 두 원의 반지름을 더한 거리보다 짧으면 충돌이 된 상태로 판별합니다.

---

https://showmiso.tistory.com/57

[3D 수학] 사원수(Quaternion : 쿼터니언)

https://m.blog.naver.com/PostView.naver?isHttpsRedirect=true&blogId=55smile&logNo=221671747433 

분리축이론(SAT)과 OBB 충돌

https://justicehui.github.io/other-algorithm/2018/06/23/OBB/

OBB충돌

https://sanghoon23.tistory.com/82

[DX] ##6. AABB, OBB 충돌 SAT 분리축 이론( Separating Axis Theorem )