충돌 검사

〈가상현실〉 수업 노트

충돌 검사는 특정한 두 대상이 서로 겹치는지 여부를 판단하는 것으로 실현할 수 있다. 현실과 같게, 서로를 통과하지 못하는 두 물체에 대해서 시뮬레이션하고자 한다면, 대개는 외곽선이 맞닿는 지점에서 충돌이 발생한다고 결론지을 수 있을 것이다.

가장 간단한 모형인 두 원(중심점 $c_i$, 반지름 $r_i$)의 충돌 검사는 다음의 수식을 사용하여 실현할 수 있다.

\[\left\| c_1 - c_2 \right\| \leq r_1 + r_2\]

혹은 단순한 다각형에 대해서는 선분 교차 검사를 통해서 충돌 검사를 실현할 수 있다.

\[\begin{aligned} d_1 &= \text{CCW}(p_1, p_2, p_3) = (p_2 - p_1) \times (p_3 - p_1) \\ d_2 &= \text{CCW}(p_1, p_2, p_4) = (p_2 - p_1) \times (p_4 - p_1) \\ d_3 &= \text{CCW}(p_3, p_4, p_1) = (p_4 - p_3) \times (p_1 - p_3) \\ d_4 &= \text{CCW}(p_3, p_4, p_2) = (p_4 - p_3) \times (p_2 - p_3) \\ \end{aligned}\] \[\begin{aligned} d_1 \times d_2 \le 0 \quad &\text{and} \quad d_3 \times d_4 \le 0 \\ \end{aligned}\]

$d_1$, $d_2$, $d_3$, $d_4$ 가 모두 $0$ 이면 네 점이 일직선 위에 있는 상황이므로, 선분이 겹치는지 좌표 크기를 비교한다.

고전 방식

분리 축 정리 (Separating Axis Theorem)

분리 축 정리는 두 물체 사이에 두 물체를 분리할 수 있는 축선이 하나라도 존재한다면, 두 물체는 충돌하지 않았다고 판단할 수 있다는 이론이다.

Lin-Canny Closest Features

Lin-Canny Closest Features 알고리즘은 두 물체 사이의 가장 가까운 점을 찾는 알고리즘이다. 이 알고리즘은 두 물체가 충돌하는지 여부를 판단하기 위해서, 두 물체 사이의 가장 가까운 점을 찾고, 그 거리가 두 물체의 반지름의 합보다 작은지 여부를 판단한다.

GJK (Gilbert-Johnson-Keerthi) 알고리즘

GJK 알고리즘은 민코프스키 차(Minkowski difference)를 이용하여 민코프스키 차에 원점이 포함되는지 여부를 판단한다.

민코프스키 차는 두 물체의 모든 점의 차이로 이루어진 집합으로 정의된다. 이 집합은 연속된 점으로 이루어진 도형이 된다.

두 물체 $A$, $B$ 중 같은 좌표를 갖는 점이 존재한다면, 그 차는 영벡터 $\vec{0}$ 이 되므로, 원점(혹은 영벡터 $\vec{0}$) 이 민코프스키 차에 포함된다는 것은 두 물체가 겹친다는 것을 의미한다. 다시 말해 두 물체가 충돌하는 경우, 민코프스키 차는 원점을 포함하게 된다. 반대로, 두 물체가 충돌하지 않는 경우, 민코프스키 차는 원점을 포함하지 않는다.

민코프스키 차 안에 원점이 있는지 여부를 판단하기 위해서, GJK 알고리즘은 탐색 벡터 $d$ 에 대해 지원점(Support point) $\text{Support}(A, B, \vec{d})$ 을 찾는다.

지원점은 $\vec{d}$ 방향으로 가장 먼 점 $a$ (물체 $A$ 의 극점) 와 $- \vec{d}$ 방향으로 가장 먼 점 $b$ (물체 $B$ 의 극점) 을 찾아 $p = a - b$ 로 계산한다. ($p = \text{Support}(A, B, \vec{d}) = a - b$)

구한 점을 이용해 2차원에서는 삼각형, 3차원에서는 사면체 ‘단체’(Simplex)를 만들어서 원점이 그 안에 포함되는지 여부를 판단한다. 이 단체가 원점을 포함하지 않는 경우, 단체의 가장 가까운 면을 찾아서 그 면의 법선 벡터를 탐색 벡터로 설정하여 지원점을 다시 계산하는 과정을 반복한다.

Bounding Volume Hierarchy

이러한 충돌 검사는 개별 물체에 대해서, 각 물체가 가지고 있는 모든 표면(직선 혹은 삼각형 등)에 대해서 전수검사하는 것으로 구현되었다. 이러한 구현은 물체의 개수가 많아지거나, 물체의 표면이 복잡해지면 충돌 검사의 계산량의 기하급수적인 증가를 초래했다.

그래서 충돌 검사의 계산량을 줄이기 위해서, 충돌 검사를 계층적으로 처리하게 되었다. 모든 도형에 대해서 정밀한 충돌 검사를 수행할 필요는 없으므로, 충돌할 것으로 타당하게 의심되는 도형 쌍을 빠르게 걸러내어, 정밀한 충돌 검사를 수행할 도형 쌍의 수를 줄이는 방식으로 충돌 검사의 계산량을 줄였다.

Bounding Volume Hierarchy (BVH)는 모든 물체들의 관계를 계층화하여, 충돌이 발생할 타당할 우려가 있는 물체 쌍을 같은 계층에 배치, 각 계층에 대해 충돌 검사를 수행하는 방식으로 충돌 검사의 계산량을 줄였다.

AABB (Axis-Aligned Bounding Box) Tree

AABB는 물체들에 대해서, 어떠한 기준 축에 평행한 직육면체로 감싸는 방식으로 충돌 검사를 수행한다. 이렇게 감싼 직육면체는 두 물체의 관계이거나, 이미 직육면체로 감싸진 물체들과의 관계가 될 수 있다. AABB 트리는 이러한 AABB로 감싼 물체들의 계층 구조를 트리 형태로 표현한 것이다.

이와 같이 감싸진, 혹은 트리 상에서 같은 부모를 공유하는 물체 쌍에 대해서만 충돌 검사를 수행한다.

OBB(Oriented Bounding Box)

OBB는 AABB와 달리, 물체의 방향에 맞게 감싸는 직육면체로 충돌 검사를 수행한다. OBB는 AABB보다 더 타이트하게 물체를 감쌀 수 있기 때문에, 충돌 검사의 계산량을 줄이는 데 더 효과적이다.

k-DOP (Discrete Oriented Polytope) Flexibility

k-DOP는 AABB와 OBB의 중간 형태로, k개의 방향으로 감싸는 다면체로 충돌 검사를 수행한다. k-DOP는 AABB보다 더 타이트하게 물체를 감쌀 수 있기 때문에, 충돌 검사의 계산량을 줄이는 데 더 효과적이다.

Spatial Partitioning

Spatial Partitioning은 공간을 일정한 크기의 셀로 나누어서, 각 셀에 포함된 물체들을 관리하는 방식으로 충돌 검사의 계산량을 줄이는 방법이다. 이 방법은 물체들이 공간적으로 분포되어 있을 때, 충돌 검사의 계산량을 줄이는 데 효과적이다.

Temporal Coherence & Sweep and Prune

실시간 물리 시뮬레이션에서 충돌 검사는 매 프레임마다 반복된다. 따라서 시간이 연속적으로 흐를 것이므로, 이전 프레임에서 충돌이 발생한 물체 쌍은 다음 프레임에서도 충돌이 발생할 가능성이 높다. 이것을 시간적 일관성(Temporal Coherence)이라고 한다.

이를 이용해 이전 프레임의 충돌 정보를 캐싱하여 재사용하거나, 변화가 있는 부분만 점진적으로 업데이트하여 계산량을 줄일 수 있다.

Sweep and Prune은 시간적 일관성을 활용한 Broad Phase 알고리즘이다.

우선 모든 물체의 바운딩 박스의 최소값과 최대값을 특정한 축을 기준으로 정렬한다. 이후 정렬된 리스트를 훑으면서(Sweep) 겹치는 구간이 있는지 확인한다. 한 축에서 겹치지 않는다면, 다른 축을 검사할 필요 없이(Prune) 충돌이 발생하지 않는다고 판단할 수 있다.