게임 엔진은 프레임 단위로 동작하기 때문에 충돌은 프레임마다 계산된다. 때문에 프레임 사이에 발생하는 충돌은 감지할 수 없다.
CCD는 프레임 사이 물체의 이동 경로(혹은 공간)를 계산하여 이 문제를 해결한다.
CCD에는 크게 두 종류가 있다.
Sweep-based CCD
물체의 위치와 이동 벡터를 통해 두 물체의 (time of impact)를 계산한다. 가장 빠른 충돌의 가 (현재 프레임)부터 (다음 프레임)사이일 경우 해당 충돌을 수행한다.
시간에 따른 상대적인 거리를 계산하기 때문에 두 고속 물체 간의 충돌도 계산할 수 있다.
정확도를 높이기 위해 sub-step을 사용할 수 있다; 즉, 프레임 사이에 계산 과정이 여러 번 반복될 수 있다. 프레임 수가 중요한 게임에서는 sub-step의 최대 횟수가 적게 설정된다. (이 경우엔 얇은 객체는 그냥 지나칠 확률도 있다.)
동작 과정
- 모든 물체들의 충돌을 계산()하고 TOI를 우선순위 큐로 관리함
- 가장 빠른 가 이하라면 충돌하는 두 물체의 위치를 만큼 계산하고 충돌 이후의 새 이동 벡터를 계산
- 두 물체와 다른 모든 물체 사이의 충돌을 다시 계산하고 우선순위 큐에 삽입; 두 물체만 상태가 바뀌었기 때문에 다른 물체끼리는 또 계산을 할 필요가 없다. 두 물체의 이전 상태에서 계산된 충돌은 이제 무시한다.
- 2-3을 반복 (반복 횟수에 제한이 있을 수 있다.)
(위 그림에서는 가 time of impact이다.)
이곳의 Continuous Collision Detection 부분에 더 자세히 설명되어 있다.
Spectulative CCD
물체가 있을 수 있는 공간을 (보수적으로) 탐색하고, 해당 공간에 있는 모든 물체와 상호작용한다. 따라서 원래라면 부딪치지 않는 물체와 부딪치거나, 1차 충돌 이후 물체가 공간을 벗어나버려서 다른 물체와 충돌했음에도 충돌이 감지되지 않는 경우도 있다.
sweep-based보다 빠르지만 덜 정확하다.
주로 위치는 고정되어있고 회전하는 물체에 적용한다.
언리얼 엔진에서 CCD 실험
UE5.5.4.에서 실험했다. UE에서는 기본적으로 Sweep-based CCD를 사용한다.
두 구체의 거리를 충돌 지점에서 약 3000cm 차이나도록 설정했다.
그리고 설정한 키를 누르면 구체의 simulate physics가 enable되고 충돌 지점으로 초속 18000cm로 움직이기 시작한다.
fps가 100으로 설정되어 있지만 구체가 워낙 빨라서 CCD 없이는 충돌을 감지하지 못 한다.
영상에는 없는데, 구체의 속도를 20000cm/s로 설정하면, 더 빨라졌음에도 CCD 없이도 충돌을 감지한다. 충돌 순간과 frame rate가 잘 맞아서 발생하는 현상이다.
Reference
