Chapter 6. 충돌과 반응

- 직선과 직선의 교차

- 선분과 선분의 교차

- 직선과 평면과의 교차

- 직선과 구와의 교차

- 직선과 삼각형과의 교차

- 공과 공의 충돌

- 공과 공의 충돌반응

- Ball Collision & Response Program

- 공간 분할 기법

6.1 직선-직선 교차

두 개의 직선이 그림과 같이 주어져 있다고 생각하자.

첫 번째 직선 [eqn: P(t)]은 두 개의 점 [eqn: P _{1} ,`P _{2}]를 지나고, 두 번째 직선 [eqn: Q(s)]은 두 개의 점 [eqn: Q _{1} ,`Q _{2}]를 지나고 있다. 이들의 방정식은 다음과 같다.

[eqn: P(t)=P _{1} +t(P _{2} -P _{1} )]

[eqn: Q(s)=Q _{1} +s(Q _{2} -Q _{1} )]

※ 주의점

두 개의 직선을 표현할 때 다른 매개변수를 사용하여야 한다. 만약 동일한 매개변수 t 를 사용한다면 직선을 나타내는 것이 아니라 시간의 변화에 따른 점의 움직임을 표현하게 된다.

교차점 [eqn: I]를 구하기 위해서는 두 개의 선분이 만나는 경우인데, 두 개의 점이 일치한다는 의미이다.

[eqn: P _{1} +t(P _{2} -P _{1} )=Q _{1} +s(Q _{2} -Q _{1} )]

두 점이 일치한다는 의미는 두 점의 x값과 y값이 일치한다는 의미이다.

[eqn: P _{1x} +t(P _{2x} -P _{1x} )=Q _{1x} +s(Q _{2x} -Q _{1x} )]

[eqn: P _{1y} +t(P _{2y} -P _{1y} )=Q _{1y} +s(Q _{2y} -Q _{1y} )]

위 식은 다음으로 정리될 수 있다.

[eqn: t(P _{2x} -P _{1x} )+s(Q _{1x} -Q _{2x} )=Q _{1x} -P _{1x}]

[eqn: t(P _{2y} -P _{1y} )+s(Q _{1y} -Q _{2y} )=Q _{1y} -P _{1y}]

그러므로 구하고자 하는 [eqn: t ^{*}] 와 [eqn: s ^{*}] 값은 다음과 같다.

[eqn: t ^{*} =` {dmatrix{Q _{1x} -P _{1x}&Q _{1x} -Q _{2x}#Q _{1y} -P _{1y}&Q _{1y} -Q _{2y}}} over {dmatrix{P _{2x} -P _{1x}&Q _{1x} -Q _{2x}#P _{2y} -P _{1y}&Q _{1y} -Q _{2y}}}]

[eqn: s ^{*} =` {dmatrix{P _{2x} -P _{1x}&Q _{1x} -P _{1x}#P _{2y} -P _{1y}&Q _{1y} -P _{1y}}} over {dmatrix{P _{2x} -P _{1x}&Q _{1x} -Q _{2x}#P _{2y} -P _{1y}&Q _{1y} -Q _{2y}}}]

이 수식은 분수로 되어 있기 때문에 확인하여야 하는 점이 존재함을 알고 있어야 한다. 즉, 분모의 값이 0 이 되는 경우를 제외해야 한다. 즉,

[eqn: dmatrix{P _{2x} -P _{1x`}&Q _{2x} -Q _{1x`}#P _{2y} -P _{1y`}&Q _{2y} -Q _{1y`}} =0]

인 경우는 두 직선이 평행한 경우이거나 일치하는 경우이다. 이러한 경우를 제외하면 다음과 같이 두 직선의 교차점을 구할 수 있다.

[eqn: I=P(t ^{*} )=P _{1} +` {dmatrix{Q _{1x} -P _{1x}&Q _{1x} -Q _{2x}#Q _{1y} -P _{1y}&Q _{1y} -Q _{2y}}} over {dmatrix{P _{2x} -P _{1x}&Q _{1x} -Q _{2x}#P _{2y} -P _{1y}&Q _{1y} -Q _{2y}}} (P _{2} -P _{1} )]

6.2 선분-선분 교차

두 개의 선분이 그림과 같이 주어져 있다고 생각하자. 왼쪽의 경우는 교차점이 있는 경우이고 오른쪽의 경우는 교차점이 없는 경우이다.

첫 번째 선분 [eqn: P(t)]은 두 개의 점 [eqn: P _{1} ,`P _{2}]를 지나고, 두 번째 선분 [eqn: Q(s)]은 두 개의 점 [eqn: Q _{1} ,`Q _{2}]를 지나고 있다. 이들의 방정식은 다음과 같다.

[eqn: P(t)=P _{1} +t(P _{2} -P _{1} ),`````````0` LEQ `t` LEQ `1]

[eqn: Q(s)=Q _{1} +s(Q _{2} -Q _{1} ),`````0` LEQ s` LEQ 1]

※ 주의점

두 개의 직선을 표현할 때 다른 매개변수를 사용하여야 한다. 만약 동일한 매개변수 t 를 사용한다면 직선을 나타내는 것이 아니라 시간의 변화에 따른 점의 움직임을 표현하게 된다.

교차점 [eqn: I]를 구하기 위해서는 두 개의 선분이 만나는 경우인데, 두 개의 점이 일치한다는 의미이다.

[eqn: P _{1} +t(P _{2} -P _{1} )=Q _{1} +s(Q _{2} -Q _{1} )]

두 점이 일치한다는 의미는 두 점의 x값과 y값이 일치한다는 의미이다.

[eqn: P _{1x} +t(P _{2x} -P _{1x} )=Q _{1x} +s(Q _{2x} -Q _{1x} )]

[eqn: P _{1y} +t(P _{2y} -P _{1y} )=Q _{1y} +s(Q _{2y} -Q _{1y} )]

위 식은 다음으로 정리될 수 있다.

[eqn: t(P _{2x} -P _{1x} )+s(Q _{1x} -Q _{2x} )=Q _{1x} -P _{1x}]

[eqn: t(P _{2y} -P _{1y} )+s(Q _{1y} -Q _{2y} )=Q _{1y} -P _{1y}]

그러므로 구하고자 하는 [eqn: t ^{*}] 와 [eqn: s ^{*}] 값은 다음과 같다.

[eqn: t ^{*} =` {dmatrix{Q _{1x} -P _{1x}&Q _{1x} -Q _{2x}#Q _{1y} -P _{1y}&Q _{1y} -Q _{2y}}} over {dmatrix{P _{2x} -P _{1x}&Q _{1x} -Q _{2x}#P _{2y} -P _{1y}&Q _{1y} -Q _{2y}}}]

[eqn: s ^{*} =` {dmatrix{P _{2x} -P _{1x}&Q _{1x} -P _{1x}#P _{2y} -P _{1y}&Q _{1y} -P _{1y}}} over {dmatrix{P _{2x} -P _{1x}&Q _{1x} -Q _{2x}#P _{2y} -P _{1y}&Q _{1y} -Q _{2y}}}]

이 수식은 분수로 되어 있기 때문에 확인하여야 하는 점이 존재함을 알고 있어야 한다. 즉, 분모의 값이 0 이 되는 경우를 제외해야 한다. 즉,

[eqn: dmatrix{P _{2x} -P _{1x`}&Q _{2x} -Q _{1x`}#P _{2y} -P _{1y`}&Q _{2y} -Q _{1y`}} =0]

인 경우는 두 직선이 평행한 경우이거나 일치하는 경우이다.

교차점이 선분 사이에 놓여야 하기 때문에 다음과 같은 두 개의 조건을 동시에 만족하여야 한다.

[eqn: 0` LEQ `t ^{*} LEQ 1]

[eqn: 0` LEQ `s ^{*} LEQ 1]

[eqn: I=P(t ^{*} )=P _{1} +` {dmatrix{Q _{1x} -P _{1x}&Q _{1x} -Q _{2x}#Q _{1y} -P _{1y}&Q _{1y} -Q _{2y}}} over {dmatrix{P _{2x} -P _{1x}&Q _{1x} -Q _{2x}#P _{2y} -P _{1y}&Q _{1y} -Q _{2y}}} (P _{2} -P _{1} )]

위 그림의 왼쪽에 있는 경우는 교차점이 있는 경우이며, 오른쪽에 있는 경우의 매개변수값은 다음의 범위에 속하기 때문에 교차점이 없는 경우이다.

[eqn: `t ^{*} >1]

[eqn: 0` LEQ `s ^{*} LEQ 1]

6.3 직선-평면 교차

3차원 공간에 하나의 평면과 하나의 직선이 주어져 있다. 두 물체간의 교차점을 찾도록 하자.

직선의 방정식은 다음과 같다.

[eqn: P(t)=P _{1} +t(P _{2} -P _{1} )]

점 Q를 지나고 법선벡터 N을 가지는 평면은 다음과 같은 방정식을 갖는다.

[eqn: (X-Q) BULLET N=0]

교차점은 두 방정식을 동시에 만족하여야 한다.

[eqn: (P _{1} +t(P _{2} -P _{1} )-Q) BULLET N=0]

정리하여 교차점의 매개변수 [eqn: t ^{*}]를 구하면 다음과 같다.

[eqn: t ^{*} = {(Q-P _{1} ) BULLET N} over {(P _{2} -P _{1} ) BULLET N}]

그러므로 교차점은 다음과 같이 정리된다.

만약 [eqn: (P _{2} -P _{1} ) BULLET N=0] 이면 직선과 평면이 평행하기 때문에 근이 무수히 많이 존재하거나 아니면 존재하지 않게 된다. 그렇지 않을 경우, 즉 [eqn: (P _{2} -P _{1} ) BULLET N != 0] 일 경우에는 다음과 같은 교차점이 존재한다.

[eqn: I=P(t ^{*} )=P _{1} + {(Q-P _{1} ) BULLET N} over {(P _{2} -P _{1} ) BULLET N} (P _{2} -P _{1} )]

6.4 직선-구 교차

3차원 공간에 하나의 구와 하나의 직선이 주어져 있다. 두 물체간의 교차점을 찾도록 하자.

직선의 방정식은 다음과 같다.

[eqn: P(t)=P _{1} +t(P _{2} -P _{1} )]

점 Q를 구의 중심으로 하고 반지름의 길이가 r인 구의 방정식은 다음과 같다.

[eqn: (X-Q) BULLET (X-Q)=r ^{2}]

교차점은 두 방정식을 동시에 만족하여야 한다.

[eqn: (P _{1} +t(P _{2} -P _{1} )-Q) BULLET (P _{1} +t(P _{2} -P _{1} )-Q)=r ^{2}]

계산의 편리를 위하여 다음으로 대체하여 식을 유도한다.

[eqn: A=`P _{2} -P _{1} ,````````````````B=P _{1} -Q]

관계식은 다음으로 정리된다.

[eqn: (At+B) BULLET (At+B)=r ^{2}]

[eqn: (A BULLET A)t ^{2} +2(A BULLET B)t+B BULLET B-r ^{2} =0]

교차점의 매개변수 [eqn: t _{1} ^{*} ,```t _{2} ^{*}]는 다음과 같다.

[eqn: t _{1} ^{*} = {-(A BULLET B)+ sqrt {(A BULLET B) ^{2} -(A BULLET A)(B BULLET B-r ^{2} )}} over {A BULLET A}][eqn: t _{2} ^{*} = {-(A BULLET B)- sqrt {(A BULLET B) ^{2} -(A BULLET A)(B BULLET B-r ^{2} )}} over {A BULLET A}]

6.5 직선-삼각형 교차

3차원 공간에 하나의 삼각형과 하나의 직선이 주어져 있다. 두 물체간의 교차점을 찾도록 하자.

3차원 공간에 놓여 있는 삼각형은 세 개의 꼭지점 좌표에 의해서 그 모양을 결정지을 수 있다. 그러나 일반적인 도형의 방정식이 없기 때문에 교차 문제는 다음과 같은 네 단계 과정을 나누어 처리되어야 한다.

① 삼각형을 포함하는 평면의 방정식을 구한다.

② 직선과 평면과의 교차점을 찾는다.

③ 그 교차점이 삼각형 내부에 있는지를 확인하기 위하여 xy 평면으로 꼬지점과 교차점을 투영시킨다.

④ 투영된 2차원 교차점이 투영된 삼각형의 내부에 존재하는지를 확인한다.

삼각형의 세 꼭지점이 반시계 방향으로 순서화 되어 있고 그들의 좌표가 다음과 같다면

[eqn: A(x _{1} ,`y _{1} ,`z _{1} ),`B(x _{2} ,`y _{2} ,z _{2} ),`C(x _{3} ,`y _{3} ,`z _{3} )]

평면의 방정식은 다음과 같다.

[eqn: (X-A) BULLET N=0]

이때 법선벡터는 다음과 같이 구해진다.

[eqn: N= {(B-A) TIMES (C-A)} over {LEFT ∥ (B-A) TIMES (C-A) RIGHT ∥}]

6.3절에서 설명된 방법에 따라 직선과 평면과의 교차점은 다음과 같이 정리됨을 알 수 있다.

[eqn: I=P(t ^{*} )=P _{1} + {(A-P _{1} ) BULLET N} over {(P _{2} -P _{1} ) BULLET N} (P _{2} -P _{1} )]

이제는 삼각형 꼭지점 세 점 A, B, C와 교차점 I을 xy 평면으로 투영하여 얻은 점들은 다음과 같다.

[eqn: A(x _{1} ,`y _{1} ,0),```B(x _{2} ,`y _{2} ,0),```C(x _{3} ,`y _{3} ,0),```I(I _{x} ,`I _{y} ,0)`]

이제는 한 점이 삼각형 내부에 있는지 외부에 있는지에 대한 평가 방법만 설정하면 된다.  교차점에 의해서 다음과 같은 삼각형들의 면적을 계산한다.

[eqn: alpha `=` TRIANGLE I ^{prime } A ^{prime } B ^{prime } ,``` beta `= TRIANGLE I ^{prime } B ^{prime } `C ^{prime } `,```` gamma = TRIANGLE I ^{prime } `C ^{prime } A ^{'} `],

만약 작은 삼각형들의 면적의 합이 원래 삼각형의 면적과 일치하면 그 점은 내부에 있는 점으로 판정되고, 원래 삼각형의 면적보다 크다면 그 점은 외부에 있다고 판단한다. 그러므로 2차원에 투영된 점이 내부에 있다면 3차원 상에서도 교차점 I 가 삼각형 내부에 있게 됨을 알 수 있다.

6.6 구-평면 교차

3차원 공간에 고정되어 있는 평면이 주어져 있다. 그리고 직선 운동을 하는 공의 반지름은 [eqn: r]이라고 할 때 시간이 [eqn: t=0]일 때 구의 중심이 [eqn: P _{1}]점에 있고 시간이 [eqn: t=1]일 때 구의 중심이 [eqn: P _{2}] 점에 있게 된다고 한다면, 주어진 시간 구간에서 충돌하는지를 파악해 보도록 하자.

3차원 공간에 있는 평면의 방정식은 다음과 같다.

[eqn: (X-Q) BULLET N=0]

이러한 평면의 방정식을 원소 관계식으로 표현하면 다음과 같은 형식으로 변경 가능함을 알고 있다.

[eqn: ax`+by`+`cz`+`d`=`0,`````N=(a,`b,`c)]

두 물체 간의 충돌 여부를 직접적으로 바로 계산하기 전에 시간의 변화에 따른 구의 위치를 대략적으로 파악하도록 하자. 이를 위하여 다음과 같은 식을 이용한다.

[eqn: f(x,y,`z)`=`ax`+by`+`cz`+`d`]

이 식의 값이 양수가 되도록 하는 점들은 평면의 법선 벡터 방향에 있는 반공간이고, 음수를 갖는 경우에는 뒷면에 있는 반공간임을 알 수 있다. 이를 양분하는 것이 평면임을 이미 알 고 있다. 두 점의 좌표가 [eqn: P _{1} (x _{1} ,`y _{1} ,z _{1} ),````P _{2} (x _{2} ,`y _{2} ,z _{2} )]이고, 두 점의 좌표를 수식에 대입하여  다음을 만족하면 충돌이 발생한다고 판정한다.

[eqn: f(x _{1} ,y _{1} ,`z _{1} )f(x _{2} ,`y _{2} ,`z _{2} )`<0`] 또는

[eqn: d(P _{2} ,`Plane)` LEQ r`]

구의 중심의 자취를 나타내는 직선을 구하면 다음과 같다.

[eqn: P(t)=P _{1} +t(P _{2} -P _{1} )]

우리가 찾고자 하는 충돌 점 I는 중심과 평면과의 거리가 r이 되도록 하는 시점에서 발생함을 알 수 있다. 그러므로 시간의 변화에 따른 중심까지의 거리는 다음과 같이 계산된다.

[eqn: d(t)`=`N BULLET (P(t)-Q)]

그러므로 충돌하는 시점 [eqn: t ^{*}]는 다음의 방정식을 만족한다.

[eqn: d(t)`=`N BULLET (P _{1} +t(P _{2} -P _{1} )-Q)=r]

[eqn: d(t)`=`t ^{*} = {r+(Q-P _{1} ) BULLET N} over {N BULLET (P _{2} -P _{1} )}]

그러므로 충돌점 I 는 다음과 같이 계산되어진다.

[eqn: I`=P _{1} + {r+(Q-P _{1} ) BULLET N} over {N BULLET (P _{2} -P _{1} )} (P _{2} -P _{1} )`-r`N]

6.7 구-구 교차

직선 운동을 하는 두 개의 공들의 충돌시점과 충돌지점을 찾고 그에 상응하는 충돌반응을 계산하도록 한다. 첫 번째 공 P는 [eqn: r _{1}]을 반지름으로 하고, 시간이 [eqn: t=0]일 때 구의 중심이 [eqn: P _{1}]에 있고 시간이 [eqn: t=1]일 때 구의 중심이 [eqn: P _{2}]이 되도록 하는 운동을 하고 있다. 두 번째 공 Q는 [eqn: r _{2}]을 반지름으로 하고, 시간이 [eqn: t=0]일 때 구의 중심이 [eqn: Q _{1}]에 있고 시간이 [eqn: t=1]일 때 구의 중심이 [eqn: Q _{2}]이 되도록 하는 운동을 하고 있다. 두 공이 충돌한다는 것은 두 공의 중심 사이의 거리가 반지름의 합과 일치할 때임을 알 수 있다. 이를 이용하여 충돌시점을 먼저 구하도록 한다.

첫 번째 구와 두 번째 구의 중심의 이동방정식은 다음과 같다.

[eqn: P(t)=P _{1} +t(P _{2} -P _{1} )]

[eqn: Q(t)=Q _{1} +t(Q _{2} -Q _{1} )]

두 중심 사이의 거리는 다음의 조건을 만족하여야 한다.

[eqn: d(P(t),`Q(t))`=` LEFT ∥ P(t)-Q(t) RIGHT ∥ =r _{1} +r _{2}]

계산의 편의를 위하여 가리의 제곱을 사용한다.

[eqn: LEFT ∥ P(t)-Q(t) RIGHT ∥ ^{2} = LEFT ∥ P _{1} +tV _{P} -Q _{1} -tV _{Q} RIGHT ∥ ^{2}]

이때

[eqn: V _{P} =P _{2} -P _{1} ,````V _{Q} =Q _{2} -Q _{1}]

그러면

[eqn: LEFT ∥ P(t)-Q(t) RIGHT ∥ ^{2} = LEFT ∥ P _{1} -Q _{1} +t(V _{P} -V _{Q} ) RIGHT ∥ ^{2}]

[eqn: = LEFT ∥ A+tB RIGHT ∥ ^{2}]

따라서

[eqn: d ^{2} = LEFT ∥ A RIGHT ∥ ^{2} +2(A BULLET B)`t+ LEFT ∥ B RIGHT ∥ ^{2} `t ^{2}]

충돌하는 조건은 다음과 같다.

[eqn: LEFT ∥ A RIGHT ∥ ^{2} +2(A BULLET B)`t+ LEFT ∥ B RIGHT ∥ ^{2} `t ^{2} =(r _{1} +r _{2} ) ^{2}]

근의 공식에 의해서 두 개의 시점을 구할 수 있는데 그 중에서 먼저 발생하는 것을 의미한다.

[eqn: t ^{*} = {-(A BULLET B)- sqrt {(A BULLET B) ^{2} - LEFT ∥ B RIGHT ∥ ^{2} ( LEFT ∥ A RIGHT ∥ ^{2} -(r _{1} +r _{2} ) ^{2} )}} over {LEFT ∥ B RIGHT ∥ ^{2}}]

이제는 충돌하는 지점을 찾도록 하자. 충돌시점에서의 두 개의 구의 중심은 다음과 같다.

[eqn: P(t ^{*} )=P _{1} ^{} +t ^{*} V _{P} ,``````Q(t ^{*} )=Q _{1} ^{} +t ^{*} V _{Q} ``]

충돌지점은 이 두 점의 [eqn: r _{1} :`r _{2}]로 내분하는 지점임을 알 수 있다. 그러므로 최종적으로 찾으려고 하는 충돌지점은 다음과 같다.

[eqn: I``=` {r _{2}} over {r _{1} +r _{2}} P(t ^{*} )+ {r _{1}} over {r _{1} +r _{2}} Q(t ^{*} )]

6.8 구-구 충돌반응

움직이는 두 개의 공이 향후 충돌할 지 아니면 충돌하지 않을 지를 빠르게 판단하는 방법을 생각해 보자.

먼저 두 중심 사이의 관계를 나타내는 벡터와 두 공의 움직이는 상태 속도를 정의하자.

[eqn: n=P _{b} -P _{a} ,``V _{ab`} =V _{a} -V _{b}]

만약 [eqn: V _{ab} BULLET n<0] 이면 두 개의 공은 서로 멀어지는 경향이 있음을 알 수 있다. 그러므로 충돌이 발생하지 않게 되는 것이다. 그림에서는 오른쪽의 경우인 셈이다.

그렇지 않다면 6.7절에서 설명된 바와 같이 충돌지점을 찾을 수 있다.

이때 단위벡터 N을 다음과 같이 정의한다.

[eqn: N`=` {n} over {LEFT ∥ n RIGHT ∥}]

충돌하는 두 물체의 고유의 성질인 반발계수([eqn: epsilon])를 반영하여 움직이는 두 물체의 충돌 전/후의 상대속도는 다음과 같은 관계식을 만족하여야 한다.

[eqn: (V _{a} ^{prime } -V _{b} ^{prime } ) BULLET N`=`- epsilon `(V _{a} ^{} -V _{b} ^{} ) BULLET N]                (1)

반발계수가 1이면 완전탄성충돌이며 반발계수가 0이면 찰흙과 같이 비탄성충돌을 의미한다.

충돌하는 두 물체 사이에는 전체 운동량이 보존되어야 하는 것이 원칙이다. 운동량은 질량과 속도의 곱으로 표현되는데 다음의 수식을 따라야 한다는 것이다.

[eqn: m _{a} V _{a} +m _{b} V _{b} =m _{a} V _{a} ^{'} +m _{b} V _{b} ^{'}]

이러한 관계식은 다음과 같이 분리하여 정리할 수 있다.

[eqn: m _{a} V _{a} + alpha N`=`m _{a} V _{a} ^{prime }]

[eqn: m _{b} V _{b} - alpha N`=`m _{b} V _{b} ^{prime }]

위 식을 정리하면 다음과 같다.

[eqn: V _{a} ^{prime } =V _{a} + {alpha } over {m _{a}} N``]

[eqn: V _{b} ^{prime } =V _{b} - {alpha } over {m _{b}} N``]

위 식을 수식 (1)에 대입하여 [eqn: alpha]를 구할 수 있다.

[eqn: alpha `=- {(1+ epsilon )(V _{a} -V _{b} ) BULLET N} over {( {1} over {m _{a}} + {1} over {m _{b}} )}]

그러므로 충돌 후의 속도는 다음과 같다.

[eqn: V _{a} ^{'} `=V _{a} _{} - {(1+ epsilon )m _{b} (V _{a} -V _{b} ) BULLET N} over {m _{a} +m _{b}} N]

[eqn: V _{b} ^{prime } `=V _{b _{}} + {(1+ epsilon )m _{a} (V _{a} -V _{b} ) BULLET N} over {m _{a} +m _{b}} N]

6.9 Ball Collision & Response Program

#include <windows.h>

#include <iostream.h>

#include <math.h>

#include <gl/gl.h>

#include <gl/glu.h>

#include <gl/glut.h> // (or others, depending on the system in use)

#define	PI	3.1415926

#define	epsilon	1.0

float	radius = 5.0;

int	width = 400;

int	height = 400;

float	point_size = 3.0;

int	n = 0;

int	num = 36;

int	c_num = 30;

float	delta;

GLenum	draw_type;

int	collide = 0;

struct Point{

float	x;

float	y;

};

struct Vector{

float	x;

float	y;

};

struct Color{

float	r;

float	g;

float	b;

};

struct Circle{

Point	center;

float	radius;

float	mass;

Color	color;

Vector	velocity;

};

Circle	*circle;

Point	*vertex;

float	delta_x, delta_y;

float	fix_radius;

Point	Window_Center;

float	Window_radius;

void init (void) {

glClearColor (1.0, 0.3, 0.3, 0.0) ; // Set display-window color to white.

glMatrixMode (GL_PROJECTION); // Set projection parameters.

gluOrtho2D (0, width, 0, height);

draw_type = GL_LINES;

vertex = new Point[num];

delta = 2.0 * PI / num;

for ( int i = 0; i < num; i++ ) {

vertex[i].x = cos(delta * i);

vertex[i].y = sin(delta * i);

}

Window_radius = width/3.0;

Window_Center.x = width/2.0;

Window_Center.y = height/2.0;

delta = 2.0 * PI / c_num;

circle = new Circle[c_num];

for ( i = 0; i < c_num; i++ ) {

circle[i].radius = radius * (1.5 + sin(i));

circle[i].center.x = Window_Center.x + Window_radius * cos(delta * i);

circle[i].center.y = Window_Center.y + Window_radius * sin(delta * i);

circle[i].velocity.x = -1.0*(circle[i].center.x - Window_Center.x) / Window_radius;

circle[i].velocity.y = -1.0*(circle[i].center.y - Window_Center.y) / Window_radius;

circle[i].mass = 1.5 + sin(i);

circle[i].color.r = (float)(1.0 -  (i%3)/2);

circle[i].color.g = (float)(1.0 - (c_num - i)/c_num);

circle[i].color.b = (float)(1.0 * (i%10)/9);

}

}

void	Draw_Circle(int	index) {

float	x, y, radius;

x = circle[index].center.x;

y = circle[index].center.y;

radius = circle[index].radius;

glColor3f(circle[index].color.r, circle[index].color.g, circle[index].color.b);

glBegin(GL_POLYGON);

for ( int i = 0; i < num; i++ )

glVertex3f( x + radius * vertex[i].x, y + radius * vertex[i].y, 0.0);

glEnd();

}

void MyReshape(int w, int h) {

glViewport(0, 0, w, h);

glMatrixMode(GL_PROJECTION);

glLoadIdentity();

gluOrtho2D (0, width, 0, height);

glMatrixMode(GL_MODELVIEW);

glLoadIdentity();

}

void	Check_Collision_Ball_Wall(int index) {

if (circle[index].center.x+circle[index].radius>width||circle[index].center.x-circle[index].radius<0)

circle[index].velocity.x *= (-1.0);

if (circle[index].center.y+circle[index].radius>height||circle[index].center.y-circle[index].radius<0)

circle[index].velocity.y *= (-1.0);

}

void	Check_Collision_Ball_Ball(int i, int j) {

float	distance;

Vector	VA, VB, R_AB, normal ;

float	inner_value;

normal.x = circle[j].center.x - circle[i].center.x;

normal.y = circle[j].center.y - circle[i].center.y;

distance = sqrt( normal.x * normal.x + normal.y * normal.y );

if ( distance < circle[j].radius + circle[i].radius ) {

distance = sqrt( normal.x * normal.x + normal.y * normal.y );

normal.x /= distance;

normal.y /= distance;

VA.x = circle[i].velocity.x;

VA.y = circle[i].velocity.y;

VB.x = circle[j].velocity.x;

VB.y = circle[j].velocity.y;

R_AB.x = VA.x - VB.x;

R_AB.y = VA.y - VB.y;

inner_value = R_AB.x * normal.x + R_AB.y * normal.y;

if ( inner_value > 0.0 ) {

circle[i].velocity.x=VA.x-(1+epsilon)*circle[j].mass*

inner_value*normal.x/(circle[i].mass+circle[j].mass);

circle[i].velocity.y=VA.y-(1+epsilon)*circle[j].mass*

inner_value*normal.y/(circle[i].mass+circle[j].mass);

circle[j].velocity.x=VB.x+(1+epsilon)*circle[i].mass*

inner_value*normal.x/(circle[i].mass+circle[j].mass);

circle[j].velocity.y=VB.y+(1+epsilon)*circle[i].mass*

inner_value*normal.y/(circle[i].mass+circle[j].mass);

collide = 1;

}

}

}

void	Update_Position(void) {

for ( int i = 0; i < c_num; i++ ) {

circle[i].center.x += circle[i].velocity.x;

circle[i].center.y += circle[i].velocity.y;

}

}

void RenderScene (void) {

int	i;

glClear (GL_COLOR_BUFFER_BIT);

glColor3f(1.0, 0.0, 0.0);

for ( i = 0; i < c_num; i++ )

Check_Collision_Ball_Wall(i);

Update_Position();

for ( i = 0; i < c_num; i++ ) {

for ( int j = i+1; j < c_num; j++ ) {

if ( i != j )

Check_Collision_Ball_Ball(i, j);

}

}

Update_Position();

for ( i = 0; i < c_num; i++ )

Draw_Circle(i);

glFlush ();

glutSwapBuffers();

}

void SpecialKey( int key, int x, int y) {

int	i;

switch (key) {

case GLUT_KEY_LEFT :

for ( i = 0; i < c_num; i++ ) {

circle[i].velocity.x *= 0.1;

circle[i].velocity.y *= 0.1;

}

break;

case GLUT_KEY_RIGHT :

for ( i = 0; i < c_num; i++ ) {

circle[i].velocity.x *= 1.5;

circle[i].velocity.y *= 1.5;

}

break;

default :	break;

}

}

void IdleFunction (void) {

RenderScene();

glutPostRedisplay();

}

void main (int argc, char** argv) {

glutInit (&argc, argv);

glutInitDisplayMode (GLUT_DOUBLE | GLUT_RGB);

glutInitWindowPosition(100, 100);

glutInitWindowSize(width, height);

glutCreateWindow ("Ball_Ball_Collision_Response");

init();

glutDisplayFunc (RenderScene);

glutReshapeFunc(MyReshape);

glutSpecialFunc(SpecialKey);

glutIdleFunc(IdleFunction);

glutMainLoop();

}

6.10 이진공간분할(BSP)

이진 공간 분할법(영어: Binary Space Partitioning, BSP) 은 재귀적으로 유클리드 공간을 초평면 상의 볼록 집합으로 분할하는 기법이다. 분할 과정으로 BSP 트리라 불리는 트리 구조가 만들어진다.

원래 이러한 기법은 3D 컴퓨터 그래픽 분야에서 렌더링 효율을 높이기 위해서 도입되었지만, CAD에서의 조립식 입체 기하학 (CSG), 로봇 공학에서의 충돌 감지, 3차원 컴퓨터 게임에서 복잡한 공간을 렌더링 하는 등 여러 분야에서 사용되고 있다.

컴퓨터 그래픽 분야에서는 공간을 빠르고 정확하게 그리는 것이 중요하다. 공간을 정확하게 그리는 방법으로는 뒤에서부터 앞에 있는 공간까지 전부 그리는 페인트공의 알고리즘이 있지만, 덮어씌울 필요 없는 부분까지 그리므로 효율적이지 않을 뿐 아니라 모든 물체가 바르게 그려지지도 않는다.

Z축 버퍼링 기법으로 물체를 정확하게 그릴 수 있지만, 이는 추가적인 메모리 사용을 요구한다. 반면에, BSP 트리 알고리즘으로는 Z축 버퍼링이나 물체를 정렬하는 과정 없이 간단히 트리를 바른 순서로 순회하는 것만으로 공간을 정확하게 그릴 수 있게 된다. BSP는 시야에 들어오는 물체만 그릴 수 있게 해 주는 가시 목록과 같은 알고리즘의 기반 역할도 한다.

BSP의 단점은 미리 공간을 구성하기 위한 전처리 시간을 요구한다는 점이다. 미리 공간을 정의해 놓기 때문에 BSP 트리 내에서 물체를 직접 움직이기가 힘들다. 하지만 이 단점은 BSP와 Z축 버퍼링 기법을 혼용하면 극복 가능하다. BSP 공간을 배경으로 두고, 움직일수 있는 물체는 Z 버퍼를 이용하여 그리면 된다.

BSP 기법은 특히 1인칭 슈팅 게임과 같은 3D 컴퓨터 게임에서 널리 사용되는 기법이다. BSP 자료 구조를 가장 처음 도입한 게임은 둠이었다. 그 외에 광선 추적이나 충돌 감지 등의 기법에서도 쓰인다.

이진 공간 분할법은 하나의 공간을 특정한 최종 목적을 만족할 때까지 공간을 재귀적으로 2개씩 분할하는 과정이다. 예를 들면, 충돌 감지을 목적으로 하는 경우에는 원래 물체가 충분히 충돌 검사를 간단하게 할 수 있도록 공간이 분할되며 렌더링을 목적으로 하는 경우에는 페인트공 알고리즘을 가장 효율적으로 사용할 수 있도록 볼록한 도형으로 공간이 분할된다.

분할선이 가로지르는 평면은 반드시 2개로 나누어져야 하므로 최종 물체의 개수는 필연적으로 증가될 수밖에 없다. BSP 트리는 균형이 잘 잡혀 있어야 하기 때문에 올바르고 효율적인 BSP 트리를 생성하는 부분은 구현 과정에서 가장 어려운 부분이라고 할 수 있다. 3D 공간에서 평면은 물체의 면을 분할하는 데에 쓰인다.

아래의 그림은 불규칙한 다각형을 볼록한 다각형 여러 개로 분할하는 과정을 묘사한 것이다. 처음부터 G와 F까지 각각의 단계마다 분할된 다각형의 모서리 수가 적어지며, 마지막 단계에는 완전히 볼록한 다각형이 되는 점에 주목하기 바란다. 어떤 경우에는 분할선이 공간상의 정점과 교차되지 않은 선분 사이를 걸치기도 한다. 만약 분할선이 선분 또는 평면과 교차할 경우에는 교차된 선분 또는 평면은 완전히 독립적인 개체가 되도록 2개로 나뉜다.