Lesson 10: Collision Detection

공의 충돌 검사는 두 공의 거리가 반지름의 합보다  더 적은지 검사한다.

그러나 300개의 공이 생겼을 때, 모든 공의 충돌을 검사하려면, 5만개의 짝에 대해 검사해야만 한다. 그럼에도 불구하고 실제 충돌은 매우 적다.

우리가 시도해볼 하나는 각 차원을 따라 반으로 큐브를 나누는 것이다. 8개의 작은 큐브로,

그리고 나서, 우리는 각각의 작은 큐브에 있는 모든 공의 짝을 체크하는 것을 계산할 수 있다.

이 그림에서 모든 공의 충돌을 체크하려면, 우리는 105개의 충돌을 검사해야 한다. 그 대신에, 4개의 작은 사각형에서의 각각의 공을 체크한다면, 단지 3 + 3 + 15 + 10 = 31개의 짝만 테스트하면 된다.

공의 갯수 = n이면 충돌 가능한 횟수는 sigma(1 to n-1)이다, ex) 5개의 공은 4+3+2+1 = 10

이것은 3D에서도 같다.

이러한 충돌 계산을 빠르게 하기 위해, 8개의 큐브에서 더 작게 나눌 수 있다. 우리는 무한으로 반복할 수 있지만 리스크가 따른다.

예를들어, 큐브에 3개의 공이 있다면,  그것은 큐브를 계속 나누는 것 보다 체크하는 것이 더 쉽다. 추가로, 더 큐브를 나누는 것은 하나의 공이 다수의 큐브에 나타내어질 수 있다. 이것은 나쁜 경우이다. 그래서 우리는 8개의 작은 큐브로 나눈다..

만약 공이 많이 없다면, 공의 모든 짝을 충돌 검사하기 위해 사용한다.

아래 그림은 tree 구조의 결과이다. 각각의 큐브는 tree의 node이고, 작은 큐브로 나누어 진다면 이 큐브들은 8개의 children이다. 이것은 "octree"로 불려지며 2D에서는 quadtree라 불린다. 아래는 2D 버젼의 tree구조의 예이다.

사각형을 더 많이 나눔으로써, 31에서 15번의 충돌 검사로 줄었다.

하지만 큐브의 길이가 공의 반지름에 도달한다면, 큐브를 구분하기가 매우 평범해 질 것이다. 이것은 나쁜 현상이다. 그래서 tree의 depth를 제한하는 이유이다. 큐브를 세분화하고 싶지만 이미 tree의 x depth이라면 더 이상 나눌 수 없다.

octree를 빈번하게 생성하고 삭제하는 것 보다는, 프로그램의 시작에서 octree를 만들고, 공이 이동하거나 생성되어질 때에는 언제든지, 우리는 octree를 변화할 수 있다.

공이 너무 많을 때 큐브를 세분화할 뿐만아니라, 공이 너무 적을 때 큐브를 un divide해야한다.

뎁스를 초과하지 않는 한도에서 ball의 수가 많다면 우리는 나누어야 하고, 공의 수가 적다면 큐브를 drop한다. 이로써, 큐브를 너무 세분화하는 것을 막을 수 있다.

 

ball-wall의 충돌은 ball-ball의 충돌을 계산하는 시간보다 매우 적기 때문에 이것은 최적화하는 것에 중요한 요소가 아니다.

 

 

공의 이동.

시간간격 dt에 의해 공이 이동하며, 이동 함수 moveBall은  TIME_BETWEEN_UPDATES 시간마다 applyGravity 함수를 호출하여 업데이트 한다. 이것은 실세계와 비슷하게, 공에 중력을 적용하여 GRAVITY * TIME_BETWEEN_UPDATES에 의해 y좌표가 감소된다.

 

충돌검사는 다음과 같다.

(두공의 위치의 차의 거리)^2이 (두공의 반지름의 합)^2보다 작으면 충돌.

 

handleBallBallCollisions은 충돌하는 공의 반응을 만든다.

먼저, 충동하는 것을 찾기 위해 potentialBallBallCollisions 를 호출한 다음, 충돌을 검사 한다. 그다음에 공의 센터로부터의 속도방향에 반대하여 서로의 반응을 만든다.  아래의 사진은 바운싱 후에 공의 속도를 계산하는 방법을 묘사한다.

사진에서, d는 공의 초기속도이다. d-2s는 바운싱 후의 공의 속도이다.

s를 결정하기 위해 우리는 (b1->pos - b2->pos).normalize()를 사용하여 두번 째 공에서 첫번 째공으로의 방향을 찾는다. 그리고나서, 주어진 s의 방향과 초기속도의 내적을 취한다. 마찰이나 반발계수(e:coefficient of restitution)가 없다면, 공이 바운스 할때 속도가 늦어지지 않기 때문에, 공은 영원히 바운싱을 유지할 것이다.