게임 엔진은 프레임 단위로 동작하기 때문에 충돌은 프레임마다 계산된다. 때문에 프레임 사이에 발생하는 충돌은 감지할 수 없다.

CCD는 프레임 사이 물체의 이동 경로(혹은 공간)를 계산하여 이 문제를 해결한다.

CCD에는 크게 두 종류가 있다.

---

Sweep-based CCD

물체의 위치와 이동 벡터를 통해 두 물체의 $TOI$(time of impact)를 계산한다. 가장 빠른 충돌의 $TOI$가 $0$(현재 프레임)부터 $1$(다음 프레임)사이일 경우 해당 충돌을 수행한다.

시간에 따른 상대적인 거리를 계산하기 때문에 두 고속 물체 간의 충돌도 계산할 수 있다.

정확도를 높이기 위해 sub-step을 사용할 수 있다; 즉, 프레임 사이에 계산 과정이 여러 번 반복될 수 있다. fps가 중요한 게임에서는 sub-step의 최대 횟수가 적게 설정된다. (이 경우엔 복잡한 충돌 상황에서 객체를 그냥 지나칠 확률이 커진다.)

위 그림에서는 $t_C$가 $TOI$이다.
원형인 두 물체의 경우 시간 $t$에 따른 위치 함수 $(x(t), y(t))$ 를 사용해 $t_C$를 비교적 쉽게 계산할 수 있다.
원형이 아니라면 많이 어려워진다. 두 물체가 최대한 가까워질 때까지 미세한 이동을 반복하고 GJK 알고리즘 등으로 두 물체의 거리를 계산하는 방법 등을 사용할 수 있다.
sub-step을 사용한다면 $t_C$부터 $t_i$까지 또 다른 충돌을 계산한다.

동작 과정

1. 물체들의 충돌을 계산하고 충돌 정보를 우선순위 큐로 관리
2. 가장 빠른 $TOI$가 $1$ 이하라면 충돌하는 두 물체의 위치를 $TOI$만큼 계산하고 충돌 이후의 새 이동 벡터를 계산
3. 두 물체와 다른 모든 물체 사이의 충돌을 다시 계산하고 우선순위 큐에 삽입; 두 물체만 상태가 바뀌었기 때문에 다른 물체끼리는 또 계산을 할 필요가 없다. 두 물체의 이전 상태에서 계산된 충돌은 이제 무시한다.
4. 2-3을 반복 (반복 횟수에 제한이 있을 수 있다.)

(이곳)의 Continuous Collision Detection 부분에 더 자세히 설명되어 있다.

---

Spectulative CCD

물체가 있을 수 있는 공간을 보수적으로 탐색하고, 해당 공간에 있는 "모든" 물체와 상호작용한다.

원래라면 부딪치지 않는 물체와 부딪칠 수 있고, 탐색 공간 바깥의 물체와는 상호작용하지 않는다. 충돌 이후에 탐색 공간을 벗어나게 될 수 있는데, 다음 프레임에 다시 계산되지 전까지는 다른 물체와 충돌해도 감지되지 않는다.

sweep-based보다 빠르지만 덜 정확하다.

주로 위치는 고정되어있고 회전하는 물체에 적용한다.

---

언리얼 엔진에서 CCD 실험

UE5.5.4.에서 실험했다. UE에서는 기본적으로 Sweep-based CCD를 사용한다.

두 구체의 거리를 충돌 지점에서 약 3000cm 차이나도록 설정했다.
그리고 설정한 키를 누르면 구체의 simulate physics가 enable되고 충돌 지점으로 초속 18000cm로 움직이기 시작한다.

fps가 100으로 설정되어 있지만 구체가 워낙 빨라서 CCD 없이는 충돌을 감지하지 못 한다.

영상에는 없는데, 구체의 속도를 20000cm/s로 설정하면, 더 빨라졌음에도 CCD 없이도 충돌을 감지한다. 충돌 순간과 frame rate가 잘 맞아서 발생하는 현상이다.

---

Reference

• Unity Documentation - Continuous collision detection
• Toptal.Developers - Video Game Physics Tutorial - Part II: Collision Detection for Solid Objects