Game Physics Engine Development - Chapter 13 : 접촉 발생

Chapter 13. 접촉 발생

 접촉을 처리하는 것은 하나의 교차 지점에서 발생하는 충돌을 감지하는 것보다 복잡하고, 이를 완수하기 위한 작업 시간도 더 오래 걸린다.

보통 2단계의 접촉 처리 프로세스를 가진다. 처리해야 할 접촉 여부를 결정하는 국지적 충돌 감지 단계(narrow-phase collision detection step)와

이후 현재 발생하고 있는 모든 접촉을 처리하는 접촉 처리 단계(contact generation step)가 바로 그것이다.

13.1 충돌 지오메트리

 수많은 게임에 등장하는 시각적으로 복잡해 보이는 기하학적인 도형들은 신속하게 접촉을 처리하기에는 너무 복잡해 보인다.

대신에 이들은 물리학적으로 다루기 쉬운 덩어리 모양으로 단순화되어 처리된다. 만약 이들 덩어리들이 구나 박스, 실린더와 같은

단순한 기하학적인 모양으로 구성된다면 충돌 감지 알고리즘은 일반적인 메시 방식보다 간단하게 구현이 가능할 것이다.

 충돌 지오메트리를 생성하는 것은 많은 개발자들이 자동화하기를 원하는 단계이며, 이를 위한 가장 쉬운 방법은 전 과정에서

다면체 메시(polyhedral mesh)를 사용하는 것이다. 이 장에서는 다면체 메시를 사용하는 과정에서 성능을 개선하는 법까지 다룬다.

 충돌 지오메트리는 포괄적 충돌 감지에서 사용되는 바운딩 볼륨과 동일한 것은 아니다. 따라서 일반적으로 게임 안에 등장하는

오브젝트는 하나 혹은 그 이상의 바운딩 볼륨과 그와는 별도의 충돌 지오메트리를 가지며 레벨의 디테일에 따라 달라지는 수많은

렌더링 지오메트리를 가지게 되는 것이다.

 가장 자주 고려해야 하는 상황 중의 하나는 오브젝트가 레벨의 배경 지오메트리와 충돌하는 경우이다.

대부분의 경우 이는 지면이나 벽면과 같은 다른 형태의 평면과 충돌이 발생하는 것을 의미한다. 이런 경우를 지원하기 위해 평면을

우리가 다루게 될 기본적인 도형의 범주에 추가하도록 한다. 물론 씬에서 오브젝트가 움직이는 과정을 표현하는 데는

이 평면이 사용될 일은 거의 없다.

13.1.1 기본적인 도형의 조합

 그림 13.1은 박스와 구를 조합해 오브젝트를 구분해서 나눈 것을 보여주고 있다. 두 개 이상의 간단한 도형 조합으로 이루어진 오브젝트를

충돌시키기 위해서는 각 오브젝트를 구성하고 있는 기본적인 도형 조합의 모든 충돌 가능성을 고려해 봐야 한다.

이런 방식은 앞 장에서 살펴본 바운딩 볼륨 계층 구조와도 유사하다. 앞서 살펴본 바와 같이, 하나의 오브젝트를 구성하는 컴포넌트끼리의

충돌은 고려하지 않아도 된다.

 이런 조합물들은 기본적인 도형의 리스트로 표현이 가능하며 원래 오브젝트의 각 기본 도형에 대응하는 변환 매트릭스로 표현이 가능하다.

13.2 접촉 발생

 이 장의 첫 부분에서도 살펴보았듯이 충돌 감지와 접촉 생성을 구별할 필요가 있다.

- 충돌 감지(Collision Detection) : 한 쌍의 오브젝트가 서로 관통하는지를 결정하는 것.

   충돌 감지기에서 사용되는 알고리즘은 일반적으로 관통의 깊이와 충돌이 발생하는 포인트를 결과값으로 반환한다.

   전형적으로 기본적인 도형 조합에서도 단 하나의 지점에서만 충돌이 발생할 것이다.

- 접촉 생성(Contact Generation) : 한 쌍의 오브젝트가 서로 관통하는지를 결정하고 만약 그럴 경우 일련의 접촉 데이터를 반환한다.

    접촉 데이터에는 접촉을 처리하기 위해 필요한 모든 정보가 포함된다.

    여기에는 각 오브젝트의 접촉 지점(혹은 좀 더 광범위한 접촉이 발생할 경우 접촉하는 영역),

    방향과 접촉이 발생했을 때의 최대 관통 깊이 등의 정보가 포함된다.

 이 비슷해 보이는 두 가지 개념을 확실히 구별할 필요가 있다. 이는 알고리즘에 직접적인 영향을 끼치며 또한 물리 엔진의 접촉 생성에도 쉽게

반영되기 때문이다.

 13.5절에서 하나의 접촉을 발생시키는 알고리즘을 확장하기 위해 일관성(con-tact coherence)이라는 기법을 

어떻게 사용하는지에 대해서 알아볼 것이다. 이 기술을 활용해 하나의 접촉을 발생시키는 것과 관련된 최악의 행동들을 방지할 수 있을것이다.

하지만 이 기법도 완벽한 것은 아니어서 상당한 양의 코드를 추가로 작성해야한다.

13.2.1 접촉 유형

 두 개의 오브젝트가 접촉하거나 혹은 서로 관통할 때 3D 형상에 미치는 접촉 패치(contact patch)가 발생할 수 있다.

접촉을 처리해야 할 때 이 부분을 처리하는 것이 쉽지 않다. 파트 2에서 우리는 접촉에 대해서 알아보고 이런 접촉과 상호 관통을 한

지점에서 발생하는 것으로 다룰 때의 극복하기 힘든 제약사항들에 대해서도 다루었다. 이러한 '포인트 접촉(point contacts)'은

오히려 상대적으로 다루기 쉬운 문제들이다.

그림 13.3은 두 개의 3D 오브젝트가 접촉할 때 발생할 수 있는 6개의 방법을 보여주고 있다. 이는 곧 면(face)과 선(edge), 정점(vertex)의

모든 조합을 아우르는 것이다. 이 모든 경우에서 단 하나의 접촉 포인트가 발생한다.

 다양한 상황에서 하나 이상의 케이스가 동시에 발생한다. 그림 13.3을 다시 한 번 살펴보자. 여기서 우리는 두 가지 종류의 접촉을

살펴볼 수 있다. 선과 선이 접촉하는 경우가 있으며, 다른 경우는 선과 꼭짓점이 접촉하는 경우이다.

이 경우들은 그림 13.3에서 보이는 것과 같이 선과 꼭짓점의 접촉만을 사용해 모든 접촉을 시뮬레이트 할 수 있다.

선과 정점의 접촉이 선과 선의 접촉보다 우선순위를 가진다.

 이런 방식으로 어떤 접촉이 더 우선순위가 높느냐를 결정할 때는 어떤 것이 최선의 행동인지를 경험을 통해 결정할 수 있다.

그 결과는 다음과 같다.

1. 점-면 그리고 선-선 (평행이 아닌 선들)

2. 선-면 그리고 면-면

3. 점-선, 점-점, 선-선 (평행한 선들) 

 앞선 번호의 경우부터 우선적으로 발생된다. 예를 들어, 면-면 접촉이 발생하는 경우는 아래 두 개 중 하나의 상황을 맞이할 수 있다.

접촉하는 두 면 중의 하나가 곡면인 경우에는 면-면 접촉이 한 점에서만 발생할 것이다. 그렇지 않은 경우, 1번의 경우와 같은

접촉이 최소한 3개 발생할 것이다. 2번 이후의 경우에는 면-면 접촉에 대해 전혀 신경 쓸 필요가 없다.

3번에서 볼 수 있는 3가지 경우의 접촉은 충분히 신뢰할 만한 연산을 수행하기 때문이다.

점-면, 선-선의 접촉처럼 동일한 수준(1번의 경우)의 접촉이 동시 다발적으로 발생한다면 각각의 경우를 모두 고려해 봐야 한다.

이런 경우는 어떤 것이 우선순위를 가진다고 말하기 힘들다.

 이를 수행하기 위해서는 최적화를 더 심화할 필요가 있다. 앞서 살펴본 접촉의 경우들은 씬 안에 존재하는 오브젝트들이 정확한 포지션에

위치해 있을 경우에만 발생한다. 예를 들어, 점과 점이 접촉하는 경우는 이를 목적으로 오브젝트를 위치시키지 않는 이상 실제로 발생할

확률이 아주 낮다. 만약 이런 점-점 접촉을 제대로 처리하지 못한다면 그 다음 프레임에서부터 오브젝트들이 아주 살짝 서로를 관통하기

시작하게 되며, 가장 높은 순위의 접촉이 발생하게 되는 것이다.

 이와 같은 이유로 인해 굳이 어떤 유형의 접촉이 발생하는지 파악하기 위해 노력할 필요가 없다.

점-점 접촉은 특히나 이를 발생시키기 위해 충분한 접촉 데이터를 만들어 내기 힘들다. 이런 경우가 워낙에 드물기 때문이다.

이런 점-점 접촉은 무시해버리는 것이 일반적이다. 만약 점-점 접촉을 시뮬레이션해야 하는 경우라면 충돌 감지기는 일단 이를 무시하고

그 다음 프레임부터 처리하기 적합한 다른 종류의 접촉으로 전환해 버릴 것이다. 이런 처리 방법이 비록 부정확하기는 하지만

눈에 띄지는 않을 것이다. 앞서 살펴본 접촉의 우선순위에 따라 하위 그룹에 위치한 접촉의 경우를 무시하는 것은 일반적이다.

점과 점, 점과 선, 평행하는 선과 선이 접촉하는 경우가 여기에 속한다.

13.2.2 접촉 데이터

 14장에서는 각각의 접촉을 처리하기 위해 필요한 다양한 데이터들에 대해서 다룰 것이다.

접촉 발생기는 이런 데이터를 계산하고 초기화하는 작업을 수행한다.

- 충돌 지점(Collision Point) : 오브젝트들끼리 접촉하는 지점을 말한다. 현실에서는 오브젝트 사이에 어느 정도 상호 관통이 발생하기

   때문에 여러 개의 충돌 포인트가 발생할 수 있다. 또한 이런 여러 지점들에서 한 지점을 골라내는 것은

   다분히 임의적이고 또한 전적으로 물리학적인 측면에 영향을 미치지 않는다.

   각기 다른 접촉 지점에서 각기 다른 충돌 알고리즘이 발생할 수 있으며 대체적으로 이를 바로 활용한다.

- 충돌 방향(Collision Normal) : 이는 두 오브젝트 사이에서 충격으로 인한 자극이 전달되는 방향을 의미한다.

7장에서 살펴본 바와 같이 회전하지 않는 물체의 충돌을 구현했을 때 이는 상호 관통하는 오브젝트가

충돌로 인해 튕겨나가는 방향을 의미한다. 관례상 충돌하는 두 물체는 항상 동일한 규칙을 따르며,

충돌 방향은 첫 번째 물체가 두 번째 물체를 향해 이동하는 방향과 동일하다.

이 책에서 충돌을 처리하는 코드들은 모두 이 관례를 따른다.

- 관통 깊이(Penetration Depth) : 이는 두 물체가 상호 관통하는 총량을 의미한다. 이는 그림 13.4에서 보이는 것과 같이 충돌 지점을

   지나는 두 물체의 충돌 방향을 따라 측정될 수 있다.

- 충돌 반환(Collision restitution) : 이는 충돌로 인한 바운스가 얼마나 많이 발생하는지를 결정하는 것이다. 이는 앞서 언급된 데이터와

    동일한 방식으로는 계산할 수 없다. 우리는 이 값이 충돌에 포함된 바디에 의해 결정되는 것으로

    간주할 뿐, 오브젝트가 가지고 있는 기하학적 조건(geometric configuration)을 전혀 고려하지 않기 때문이다.

    

- 마찰(Friction) : 이 값은 두 물체가 접촉 이후 미끄러질 수 있는지를 결정한다. 

     충돌 반환값과 마찬가지로 이 값은 미리 설정되어 있는 값을 사용한다.

[그림 13.4]

 각기 다른 기본 도형들의 조합에서 발생하는 독특한 충돌 알고리즘을 조사하기 이전에, 앞서 살펴본 접촉의 경우들을 순서대로 살펴보고

각각의 파라미터들이 어떻게 결정되는지 알아보는 것도 의미가 있을 것이다.

13.2.3 점-면 접촉

 이 접촉은 가장 많이 발생하는 중요한 2가지 접촉 유형 중의 하나다.

면이 평면인지 곡면인지와 상관없이 그림 13.6에서 보이는 것과 동일한 방법으로 접촉의 속성이 결정된다.

 접촉 법선은 접촉 지점에 위치한 표면의 방향에 의해 결정된다. 따라서 충돌 방향은 충돌하는 물체 중 면을 가지고 있는

오브젝트가 어떤 면을 가지고 있느냐에 따라 달라진다. 점을 가지고 있는 물체는 모든 방향에서 접근이 가능하다.

 표면이 곡면이라면 평면의 어떤 지점을 가지고 방향을 결정해야 할지가 명확하지 않을 수 있다.

만약 평면과 접촉하는 점이 평면을 꿰뚫고 지나간다면 접촉 법선이 계산되기 전에 어떤 방식으로던 표면 위로 다시

튀어 올라야 할 것이다. 충돌 이후 튕겨나오는 부분의 세부사항들은 일반적으로 그렇게 중요하지는 않다.

 지금 살펴보는 이 경우에는 충돌하는 물체가 구인 경우 문제가 될 수 있다. 반면 튕겨 올라가는 지점은 표면에서 가장 가까운 구의

지점으로 설정하면 되므로 이 부분은 크게 어렵지는 않다.

 접촉에 포함된 모든 지점이 접촉 지점이 될 수 있다. 충돌한 점 부분이 접촉 지점이 될 수도 있다.

이럴 경우는 별 다른 추가적인 조치 없이 이를 접촉 지점으로 활용 가능하다. 충돌 깊이는 점과 면 사이의 거리를 충돌 방향에 맞추어

계산하면 된다.

13.2.4 선-선 접촉

 두 번째로 중요한 유형의 접촉이며, 박스나 다면체 메시와 같이 평평한 면을 가지고 있는 오브젝트에 있어서는 아주 중요한 접촉

유형이라고 할 수 있다. 접촉 데이터는 그림 13.6에서 보는 것과 같다.

 접촉 법선은 양 선이 만나는 접선에서 직각 방향이다. 이를 계산하기 위해 벡터곱이 사용된다.

 접촉 지점은 전형적으로 하나의 선이 다른 선을 만나는 지점에서 가장 가까운 지점이다. 두 선 사이의 가운데 지점을 접촉 지점으로

사용하는 개발자들도 있다. 이 경우 계산에 조금 더 시간이 걸릴지라도 미세하나마 조금 더 정확하다고 말할 수 있다.

개인적으로는 가장 가까운 지점을 접촉 지점으로 사용해도 별다른 문제를 찾을 수 없었다.

 관통 깊이는 두 선 사이의 거리로 표시된다.

13.2.5 선-면 접촉

선-면 접촉은 캡슐의 선이나 구의 표면과 같이 오직 곡면이 포함된 오브젝트의 접촉에만 사용된다. 

그림 13.7에서 보이는 것과 같이, 접촉 데이터는 점-면 접촉에서 발생한 것과 거의 유사한 방식으로 수행된다.

 접촉 법선은 이전에 살펴본 바와 같이 면이 향하고 있는 방향에 따라 달라진다. 이 계산에서 선의 방향은 무시된다.

 접촉 지점을 계산하는 것이 조금 까다로울 수 있다. 이 지점이 관통한 지점의 가장 깊은 지점이라면 좋을 것이다.

일반적으로 임의의 3D 모양을 다루는 경우 이를 계산하는 것은 간단한 일이 아니다. 하지만 이 장에서 우리가 다룰 도형들을 포함하는

가장 간단한 도형에서 이를 찾는 것은 어렵지 않다.

 접촉 지점이 이와 같이 쉽게 계산된다면 관통 깊이는 바로 알아낼 수 있다. 만약 그렇지 않다면 접촉 지점을 지나는 방향을 따라 선과

면 사이의 거리를 복잡한 과정을 통해 일일이 계산해 내야 한다.

13.2.6 면-면 접촉

 면-면 접촉은 평면에 구가 부딪치는 경우처럼 굽은 면을 가진 오브젝트가 평면이나 곡면에 접촉하는 경우를 말한다.

그림 13.8이 이런 유형의 접촉이 발생할 때의 속성을 보여주고 있다.

 접촉 법선은 한 면의 방향에 따라 결정된다. 이론상으로는 한 면의 반대 방향으로 접촉 법선이 결정되어야 한다.

방향이 완전 정반대가 아닌 경우를 제외하고는 두 개의 면이 접촉할 수 있는 경우는 없다.

하지만 실제로는 이 이론이 완벽하지 않으며, 오브젝트 사이에서 다양한 상호 관통이 발생할 수 있다.

이는 곧 실제 접촉 법선이 일치하지 않을 수 있다는 것을 의미한다. 이 중 하나를 계속 사용하고 나머지 일치하지 않는

경우는 무시해 버리는 것이 상책이다. 어떤 것을 사용할 것인지는 알고리즘에 따라 달라진다.

경우에 따라 독립된 알고리즘을 작성하는 것이 오브젝트를 선택하는 것보다 쉬운 일이라는 것을 알게 될 것이다.

게다가 이런 알고리즘은 시뮬레이션의 품질에도 영향을 미치지 않는다.

 선-면 접촉에서도 말한 바와 같이, 이 경우도 일반적으로 접촉 지점을 계산해 내는 것은 쉬운 일이 아니다.

또한 기본적인 도형을 사용함으로써 최적의 관통 깊이를 바로 찾아낼 수 있다는 점도 유사하다.

그렇지 않다면 관통하는 볼륨 안에서 임의의 지점을 찾아내야만 할 것이다.

 일반적으로 접촉 지점을 계산함으로써 관통 깊이도 바로 알아낼 수 있다. 일반적으로 접촉 지점을 통과하는 법선의

방향으로 각 표면 간의 거리를 구하기 위한 코드를 작성해야 한다.

13.2.7 접촉 발생 이전에 필요한 테스팅

 일부 접촉 발생 알고리즘은 작성하는 데 오랜 시간이 소모된다. 개괄적 충돌 감지는 접촉 이후에 발견될 수 있는 일부 오브젝트의

페어도 만들어 내게 된다. 만약 접촉이 발견되지 않는다면 조속히 종료되는 알고리즘을 만들어 충돌 감지 과정을 좀 더

효율적으로 만들 필요가 있다.

 이후에 소개될 부분에서는 이런 기능을 수행할 수 있는 다양한 접촉 발생 알고리즘을 알아볼 것이며, 소개되는 코드를 통해 여러 가지

이점을 누릴 수 있을 것이다.

 일부 기본적인 충돌 알고리즘은 각기 완전히 다른 구조를 가지고 있어서 스스로 접촉을 발생시키지 않는 접촉이 발생하는지도

파악할 수 있을 것이다. 만약 그런 기능을 수행하는 알고리즘이 존재하고 충분히 속도도 빠르다면 이를 가장 첫 단계로 수행해 볼 수

있을 것이다. 

 이를 얼리 아웃(early out0이라고 부른다. 이 기능은 불필요한 동장 없이 알고리즘 수행을 조속히 완료할 수 있게끔 해준다.

이런 테스팅 알고리즘은 종종 게임 그래픽과 관련된 책에서 충돌 감지 루트로 활용되며, 동일한 목적으로 우리가 만들려는 코드에도 

활용이 가능하다. 많은 경우 빠른 점검을 위해 필요한 일들은 우리가 접촉을 발생시키는 과정에서 수행되는 것과 동일하다.

혹은 이 두 경우를 빠르게 수행함으로써 우리가 수행하는 테스트가 실패할 수 있는 경우를 최소화할 수 있을 것이다.

이런 경우는 접촉 발생 알고리즘 자체가 이런 목적을 위해 사용되어야 한다. 여러 알고리즘 사이에서 가장 적합한 경우를 찾아내는 것은

당신의 코드를 훌륭하게 만드는 데 있어서 아주 중요한 일이다.

13.3 간단한 충돌 알고리즘

13.3.1 두 개의 구가 충돌하는 경우

 우리가 가장 먼저 다룰 기본적인 도형은 구이다. 2개의 구를 충돌시키는 것은 아주 간단하다. 만일 2개 구의 중심 간의 거리가 각 구의

반지름을 합한 것보다 적은 경우라면 접촉이 발생한다.

 이들이 접촉하게 되면 정확하게는 단 하나의 접촉 지점이 발생하게 된다. 각각의 구는 하나의 표면으로 이루어져 있으므로 여기서는

면-면 접촉이 적용된다. 그림 13.8에서 이를 설명하고 있다.

 가장 깊은 접촉 지점은 구의 중심을 있는 선 위에 위치한다. 여기에 사용되는 알고리즘은 7장에서 살펴본 입자 충돌에서 사용된 것과

정확하게 일치한다.

13.3.2 구와 평면이 충돌하는 경우

 구와 평면이 충돌하는 경우는 구가 다른 도형들과 충돌하는 것처럼 매우 간단한 케이스에 속한다.

평면으로부터 구의 중심에 이르는 거리가 구의 반지름보다 적다면 구와 평면이 충돌한 것으로 간주한다.

 평면으로부터 이 지점까지의 거리는 다음과 같다

 여기서 l값은 평면의 법선 벡터(normal vector)를 의미하며, l은 평면의 오프셋을 의미한다.

이 공식은 3D 기하학에서 평면을 표현하는 가장 표준적인 방식이다.

 사실 엄밀하게 따지면 이 접촉은 구-평면 접촉이 아니라 구-반무한체(half-space)의 접촉이라고 볼 수 있다.

그림 13.9에서 그 차이를 알 수 있다. 반무한체는 평면의 뒷부분에 속하는 영역이 모두 고체라고 가정했을 때 성립할 수 있다.

따라서 관통하는 오브젝트는 평면 법선의 방향으로 접촉 법선을 가지게 된다.

오브젝트가 평면 뒤에 위치한다고 해도 접촉은 발생할 것이다. 진정한 평면은 아주 얇은 형태를 띠고 있을 것이다.

평면의 뒤쪽에 위치하는 오브젝트는 평면 법선과 반대 방향의 접촉 법선을 가지게 된다.

13.3.3 박스와 평면의 충돌

 앞서 구 형태의 충돌에 대해 살펴보았다. 이제부터는 두 번째 기본 도형인 박스를 알아볼 차례이다.

우선 박스와 평면(엄밀하게 말하면 반무한체) 사이의 접촉 발생 알고리즘에 대해서 알아보자. 이는 우리가 살펴본 알고리즘

중에서 하나 이상의 접촉을 반환할 수 있는 첫 사례가 될 것이다.

 우선 우리가 단일 지점에서 발생하는 하나 혹은 그 이상의 복잡한 접촉이나 상호 관통을 계산하려고 노력하고 있다는 것을

상기할 필요가 있다. 그 일부로 우리는 이미 고려해야 하는 접촉의 우선순위에 대해서 살펴보았고, 따라서 가급적이면 우선순위가

높은 접촉을 반환하는 것이 필요하다는 것을 인지하고 있다.

 13.2절에서도 다루었듯이 박스-평면 충돌은 가장 대표적인 점-면 접촉이라고 할 수 있으며, 이는 가장 높은 우선순위의 경우에

포함되어 있다. 만약 박스가 평면의 평평한 면 위에 올려져 있는 상태라면 박스 표면에 위치하는 각 꼭짓점에서의 접촉만 반환하면

될 것이다. 이와 유사하게, 만약 박스의 모서리가 평면과 충돌한다면 모서리의 끝부분에 위치한 꼭짓점에서의 접촉만 계산하면 될 것이다.

 따라서 총 4개의 접촉이 발생하게 되며, 각각은 점-면 접촉으로 분류될 것이다. 그림 13.10이 이를 설명하고 있다.

 만약 박스가 평면의 아래에 위치하고 있다면 박스의 꼭짓점을 하나하나 순차적으로 체크함으로써 일련의 접촉을 찾아낼 수 있을 것이다.

각 꼭짓점에서 발생하는 접촉을 체크하는 것은 이전에 수행했던 구-평면의 접촉에서 사용했던 방법과 비슷하다.

  정점은 각각이 단 하나의 점으로 이루어져 있고, 반지름 값을 가지지 않기 때문에 단지 d값이 양수인지 음수인지만 구별하면 된다.

따라서 충돌은 다음 조건을 만족할 때 발생한다.

13.3.4 박스와 구 충돌하기

 그럼 이제 지금까지 살펴봤던 기본적인 도형 2가지를 조합해 박스와 구가 어떻게 충돌하는지를 알아보자.

구가 박스와 충돌할 때는 항상 1개의 접촉 지점을 가지게 된다. 그리고 아래 3가지 유형 중의 하나에 속하게 될 것이다.

1. 박스의 정점이 구의 평면과 접촉하게 되면 점-면 접촉이 발생한다. (접촉의 최우선순위에 속하는)

2. 박스의 모서리가 구의 평면과 접촉하게 되면 선-면 접촉이 발생한다. (접촉의 두 번째 우선순위에 속하는)

3. 구가 박스의 한쪽 면과 접촉하게 되면 면-면 접촉이 발생한다. (접촉의 두 번째 우선순위에 속하는)

 각각의 경우에서 구는 면 접촉을 발생시키는 원인을 제공하며, 박스는 점, 선, 면 접촉을 발생시킨다. 그림 13.12에서 이를 설명하고 있다.

 다행히도 이 3가지 경우의 계산은 거의 유사하므로 이를 코드에 구현하는 데에도 큰 무리는 없을 것이다.

각각의 경우에서 구의 중심에서 가장 가까운 박스의 지점이 어디인지를 찾아낼 필요가 있다. 만약 이 거리가 구의 반경보다 작다면

충돌이 발생했다는 것을 알 수 있다. 그리고 이 지점을 접촉 지점으로, 이 지점에서 구의 중심을 향해 그은 선을 접촉 법선으로 활용할 수 있게

되며 상호 관통의 깊이를 알기 위해 두 오브젝트가 겹치는지 테스트했던 계산법도 사용할 수 있게 되는 것이다.

 만약 점-면 접촉이나 선-면 접촉이 발생한다면 여기서 피룡한 계산법은 이미 13.2절에서 살펴본 것과 정확하게 일치할 것이다.

대신 면-면 접촉이 발생한다면 접촉 법선을 발생시키고 이를 계산하기 위해서는 추가적인 설명이 필요하다.

13.2.6절에서 2개의 오브젝트가 정확하게 그 면끼리 접촉하게 된다면 평면 법선은 정확하게 서로 반대 방향으로 나아가게

될 것이라고 말한 바 있다. 하지만 실제로는 상호 관통이 발생하게 되며 이로 인해 앞에서 설명했던 부분이 달라질 수밖에 없게 된다.

여기서 하나의 방법을 제안하고자 한다. 구-박스 충돌을 계산하기 위해 필자가 제안하는 알고리즘에서는 효과적으로 구에 대한 계산을

수행해 낼 것이다. 구의 표면 법선을 사용해 점-면 접촉과 선-면 접촉의 경우를 계산할 것이며, 아울러 면-면 접촉에도 이를 사용할 것이다.

 이 알고리즘 중에서 앞에서 살펴보지 않은 것 중의 하나는 구의 중심에서부터 가장 가까운 박스의 지점을 찾아내는 것이다.

이를 위해서는 2단계의 프로세스가 필요하다.

- 중심점을 박스의 좌표 공간으로 전환한다. 박스는 그 어떤 방향이라도 지향할 수 있으므로 박스의 좌표 공간상에서 계산을

  수행함으로써 초기에 이 방향을 제거할 수 있다면 이후의 계산은 더욱 간단해질 수 있을 것이다.

- 변환된 지점을 박스의 하프사이즈를 사용해 고정하고, 고정된 좌표가 최초의 좌표와 동일한 방향을 가지고 있다는 것을 확인한다.

13.4 분리축 테스트

 SAT(Separating Axis Test)는 충돌 감지에서도 가장 유용한 개념 중의 하나이며,

이 장의 나머지 부분에서 설명할 내용 중에서 주축을 이루게 될 것이다. SAT는 두 오브젝트가 겹치지 않는 어떤 축이 존재한다면

이 오브젝트들은 접촉하지 않는다는 것이 핵심적인 내용이다. 이 테스트를 수행하기 위해서는 3D 오브젝트를 1차원 축에 투영해야 한다.

각각의 오브젝트는 이 축을 따라 최솟값과 최댓값을 가질 것이다. 만약 두 오브젝트의 이 영역이 겹친다면, 이 축은 오브젝트들을 분리할 수 없다.

그림 13.16에서 이를 설명하고 있다.

 SAT는 두 물체 사이에 어떤 접촉도 발생하지 않는다는 사실을 입증한다는 것에 주의해야 한다. 하지만 테스트가 실패하고 겹치는 영역이

발견된다고 해도 이것이 곧 접촉이 발생한다는 이야기는 아니다. 실제로 두 물체가 접촉하는지를 알아내기 위해서는 다양한 SAT를 수행해야 한다.

만약 모든 테스트가 실패한다면 접촉이 발생했다고 추론할 수 있을 것이다. 적합한 축을 제대로 선택했다면 말이다.

 자, 그럼 어떻게 가장 적합한 축을 골라낼 것인가? 거의 무한대의 방향을 가진 축이 설정 가능하며 간단하게 생각한다면 그중 어떤 축이라도

분리축으로 설정될 수 있을 것이다.

 다행히도 우리가 사용하는 기본적인 도형들은 특정한 일련의 축들로 SAT를 수행할 수 있다.

가장 대표적인 것은 볼록 다면체이다. 일반적으로 볼록 다면체는 우리가 가장 마지막에 고려하는 도형의 하나이지만 박스 역시 동일한 유형에

속하는 가장 일반적인 오브젝트라는 것에 주의할 필요가 있다. 사실 SAT를 수행하는 데 있어 이 두 도형에는 거의 동일한 이론이 적용된다.

 다음과 같은 과정을 거쳐 축들이 선택된다.

- 양 오브젝트의 모든 면이 분리축을 생성하며, 이 축은 각 면의 평면 법선과 동일하다.

- 각기 다른 오브젝트의 모든 변의 조합이 분리축을 생성하며, 이 축은 조합의 양 변에서 직각을 이룬다.

- 각기 반대 방향으로 나아가는 중복되는 모든 축을 제거한다.

 두 개의 박스가 있다고 가정해 보자.이 경우 우리는 모두 15개의 축을 조사해야 한다.

각 박스의 면들에 대한 6개의 축(2개의 상자에는 총 12개의 면이 존재하지만 하나의 박스에서 평행으로 존재하는 면들이 

존재하므로 최대 6개의 축만 남는다)과 9개의 변 조합(각 박스에는 12개의 변이 있으며 이들 조합은 모두 12 x 12 = 144개가 나온다.

하지만 각 박스에서 평행한 모서리가 모두 4개이므로, 3 x 3 = 9개의 조합만 체크하면 된다)만 남게된다.

 충돌 감지를 제대로 수행하기 위해서는 이 축에서 반복적으로 SAT를 수행해야 한다. 첫 번째 SAT가 성공한다면 우리는 접촉이

발생하지 않는다는 결론과 함께 이 작업을 종료할 수 있다. 만약 모든 테스트가 실패한다면 오브젝트가 접촉하거나 혹은

겹친다는 사실을 알 수 있을 것이다.

13.4.1 SAT로 접촉 데이터 생성하기

 SAT를 통해 2개의 오브젝트가 어느 정도 겹친다는 것을 알게 된다면 상호 관통의 최댓값은 아마 겹치는 부분보다 크지 않을 것이다.

즉, 2개의 박스가 하나의 유닛만큼 겹치는 것처럼 보이는 축을 발견할 수 있다면 이 박스들이 하나의 유닛 이상만큼 상호 관통하지

않으리라는 사실을 알게 되는 것과 마찬가지이다. 하나의 유닛은 관통할 수 있는 최댓값이 되는 것이다.

물론 앞서 살펴본 바와 같이 테스트가 성공한다면 그 다음 축으로 넘어갈 수도 있고, 이들이 전혀 접촉하지 않는다는 것을 알게 될 수도

있다. 어떤 축이 2개의 오브젝트가 한 유닛 정도 떨어져 있다는 것을 보여준다면 이들이 하나의 유닛보다 적은 거리로 떨어져 있따는

것을 말해주는 것이다. 그림 13.15가 2D의 경우로 이를 설명하고 있다. 2D 이므로 면에 기준한 축들만 표시된다.

따라서 4개의 축만 보이는 것에 유의해야 한다.

 필요한 접촉 데이터를 찾아내기 위해 앞서 살펴본 결과를 활용할 수 있다. 우리가 수행하는 각각의 SAT에서 겹치는 최소 영역을 가지는 축을

찾아낼 수 있을 것이다. 해당 축에서 오브젝트들이 분리되어 있는 것과 같이 오버랩되는 부분이 없다면 이 과정은 바로 종료될 수 있다.

하지만 모든 테스트가 실패하고 오브젝트가 겹친다면 관통 가능한 최댓값이 발견되었다는 것을 의미하는 것이다.

 관통의 최솟값이 어떤 축에서 발견되었느냐에 따라 나머지 데이터들은 다른 방법을 통해 도출될 수 있다.

- 만약 최솟값이 선-선 축에서 발견된다면 접촉은 선-선 접촉으로 발생할 것이며, 2개의 변이 여기에 고나련되어 있다는 사실을 알 수 있다.

- 만약 최솟값이 면 축에서 발견된다면 면-점 접촉이 발생할 것이다.

  (볼록 다면체에서는 면-면 혹은 선-면 접촉이 발생할 수 없다. 점-선 혹은 선-선 접촉만이 우선순위에 따라 발생할 것이다)

  이 경우 한 오브젝트의 면을 관통하는 다른 오브젝트의 점을 찾아내야만 한다.

 이 기법에서 마지막으로 살펴볼 것은 이 기법이 대부분 하나의 접촉만을 찾아낸다는 것이다. 앞서도 살펴보았지만 이 기법만으로 두 물체의

접촉을 완벽하게 시뮬레이션하는 것은 충분하지 않다. 실제로도 각 프레임에서 하나의 접촉만을 반환하는 것은 시뮬레이션에서 다양한 변형과

문제를 낳게 되는 원인이 된다. 반드시 모든 접촉을 계산할 수 있는 방법을 찾아야만 한다. 다행히도 기존 작성된 코드를 거의 수정하지 않고도

이를 수행할 수 있는 방법이 존재한다.

13.4.3 볼록 다면체 충돌하기

- 반무한체와의 충돌 : 실현 가능한 접촉은 오직 점-면 접촉이 유일하며, 접촉하는 면이 반무한체의 형태를 띠고 있다는 것은 이미 주지의 사실이다.

이는 오브젝트의 정점이 반무한체에 부딪히는 것을 간단하게 테스트할 수 있으며, 상호 관통된 각 정점에서의 접촉을 쉽게

발생시킬 수 있다는 것을 의미한다.

- 구와의 충돌 : 적어도 하나 이상의 점-면, 선-면, 면-면 접촉이 발생할 것이다. 각각의 경우 접촉이 발생하기 위해서는 구의 면이 사용된다.

   구의 면은 어떤 정점이나 변도 존재하지 않는다. 우리는 오브젝트에서 구의 중심과 가장 가까운 지점만을 찾아내면 된다.

   만약 이 거리가 구의 반경보다 작다면 접촉이 발생한 것이다. 접촉 데이터는 이 점과 구의 중심점을 활용해 발생 가능하다.

- 다른 볼록 다면체와의 충돌 : 이 경우는 여러 개의 SAT를 수행해 가장 깊은 상호 관통 지점을 계산할 수 있다.

테스트에 사용되는 축들은 각각의 면을 기준으로 도출되며, 각기 다른 오브젝트에서 각각 짝을 맺은 변들과

직각을 이룬다. 결과적으로 적어도 하나 이상의 접촉이 발생하며, 점-점, 선-선 접촉 중의 하나가 발생할 것이다.

점-면 접촉에서 발생하는 접촉 데이터를 계산하기 위해서는 상호 관통이 발생한 이후 가장 깊은 위치에 위치하는

지점을 찾아낼 필요가 있다. 선-선 접촉에서는 두 변들에게 가장 가까운 근사치에 위치한 지점을 찾아야만 한다.

박스의 충돌을 구현했던 코드에서처럼 동일한 분리축을 공유하는 코드가 필요하며 따라서 중복하는 것들을

굳이 테스트할 필요는 없을 것이다. 접촉 데이터를 계산하기 전에 어떤 축의 변이나 면을 접촉에 사용할 것인지를

결정하기 위해 추가적인 작업을 수행할 필요가 있다.

 일반적인 형태의 박스와 볼록 다면체의 가장 중요한 차이점은 바로 크기이다. 만약 다면체가 E개의 변, F개의 면, V개의 정점을 가지고 있고,

이 다면체가 반무한체와 충돌한다면 O(V) 프로세스를 따를 것이며, 구와 충돌할 경우는 O(E+F), 그리고 다른 다면체와 충돌한다면 그 공식은

다음과 같을 것이다.

O(F1 + F2 + E1E2)

 F1과 F2, 그리고 E1과 E2는 충돌하는 각 다면체의 면과 변의 개수를 의미한다. 이런 이차식은 SAT 충돌 감지를 위한 처리 요구사항이 아주

빠른 속도로 증가할 수 있음을 의미한다. 서로 평행하는 면이나 변을 가지지 않는 2개의 장방체가 충돌한다고 가정해 보자.

이 경우 6 + 6 + 12 x 12 = 156개의 축을 테스트해야만 하는 것이다. 대부분의 충돌 지오메트리는 이보다 더 복잡하다.

즉, 이 방식을 사용하는 충돌 감지는 충분히 비실용적일 수 있다는 말이다.

13.5 일관성

 어떤 알고리즘을 사용하느냐와는 별개로 다중 접촉을 해결할 수 있는 방법도 존재한다. 매 프레임마다 지금껏 우리가 배운 방식 중 하나를

사용해 하나의 접촉을 생성하는 것이 바로 그것이다. 이것이 일반적인 방식으로 이 문제를 해결하는 방법이다.

한 번에 하나의 충돌만을 처리할 수 있으므로 충돌 처리가 완벽하지 않으며, 다음 프레임에서 해당 오브젝트들은 아마 상호 관통을

일으킬 것이다. 실제로 충돌은 여러 접촉 지점에서 발생할 것이며, 다음 프레임에서의 상호 관통은 앞 프레임에서 일어난 접촉과 다른 양상을

띨 것이다. 서로 다른 변의 조합이 발견되거나 혹은 점, 혹은 면 조합이 발견될 것이다. 이런 새로운 상호 관통은 앞서와 동일한 방식을 통해

'접촉'으로 인지되게 될 것이다.

 이 프로세스는 프레임과 프레임 사이에서 오브젝트가 아주 멀리 이동하지 않는 전제하에서 성립한다. 우리는 이를 '일관성(coherence)'이라고

부른다. 이는 한 프레임에서 발생한 접촉이 거의 다음 프레임에서도 접촉으로 받아들여진다는 것을 의미한다.

그림 13.17이 2D에서 발생한 2개의 접촉과 여기서 발생하는 액션을 설명해주고 있다.

 이어지는 다음 프레임에서 여전히 존재하는 접촉을 유용하게 사용할 수 있다는 사실은 박스가 안정적일 때 더 유용하다.

하지만 박스가 움직이고 있다면 다음 프레임에서는 완전히 다른 접촉이 발생할 수밖에 없을 것이다. 이 방식에 대해 주의할 사항을 3가지로

추려보면 다음과 같다.

 첫째, 접촉 데이터를 계속해서 추적 가능하고, 이를 다음 프레임에서도 사용 가능하다면 부정확한 충돌 반응에 주의를 기울일 필요가 있다.

접촉이 어느 정도 일관성을 유지한다는 것은 사실이지만, 그렇다고 접촉 데이터도 일관적이라는 것은 아니다. 우리가 저장하는 정보들은

충돌을 만들어 내는 두 오브젝트의 조합에서 발생하는 것들이다. 이런 정보들로부터 접촉 데이터를 새롭게 생성해 내야 하는 것이다.

 예를 들어, 선-선 접촉이 발생한다고 가정해 보자. 이 경우 각각의 두 변에 대한 정보를 저장할 것이다. 그 다음 프레임에서 우리는

각 두 변에서부터 접촉 법선을 이끌어내고, 가장 가까운 근사 지점을 다시 계산할 것이며, 이를 충돌 지점으로 사용하게 될 것이다.

비록 현재 사용하고 있는 정보들이 앞선 프레임에서 전달된 것이더라도 이 데이터들은 현재의 프레임에서 유용하고 정확하다.

 둘째, 2번째 프레임에서 첫 번째 프레임과 동일한 접촉 데이터를 사용하지 않도록 주의해야 한다.

하나의 프레임에서 변1과 변2 사이에서 충돌이 감지되고, 그 다음에도 동일한 충돌이 감지되었다면 단 한 번만 충돌을 처리하면 된다.

중복되는 2개의 충돌을 처리하는 것은 충돌 처리 시스템을 복잡하고 혼랍스럽게 만들 것이다.

 이런 사항들을 고려해야 한다는 것은 기본적인 충돌 감지 알고리즘을 수정해야 한다는 것을 의미하며,

이를 통해 지금까지 살펴본 기본적인 접촉 데이터뿐만 아니라  이런 접촉 데이터에 고유의 식별자를 부여해야 한다는 것을 의미한다.

 셋째로 고려해야 하는 항목은 이미 발생한 접촉을 망각하는 능력이다. 여기에는 일반적으로 3가지 범주가 존재한다.

1. 일부 이전 프레임에서 일정량 이상의 접촉이 발생한다면 이를 캐시에서 삭제해야 한다.

   각각의 프레임에서 요구하는 정확한 접촉의 개수는 대개 잘 정리된 과정을 거쳐 도출된 것이다.

   하지만 필자가 구현했던 시스템 중에서는 그중 일부만으로도 충분한 경우가 있었다.

2. 만약 상호 관통한 깊이가 일정량보다 짧다면 이 접촉은 무시해도 좋은 것으로 분류될 필요가 있다.

   처음 살펴보았을 때 그 깊이가 0이라면 이런 분류를 적용할 충분한 값이 될 것이다.

   하지만 우리가 다음 장에서 만들어 볼 충돌 반응 시스템은 0보다 적은 상호 관통값을 가지는 접촉에서도

   동작하게 될 것이다. 이 값들도 앞서 말한 일정량으로 구분될 수 있을 것이다.

   이런 경우들도 접촉을 처리할 때 관통이 발생할 수 있다. 따라서 이를 통해 접촉 처리 시스템이 이들을 먼저

   인지할 수 있도록 도와줄 수 있다.

3. 만약 접촉의 분리 속도(separation velocity)가 일정량 이상이라면 이 접촉은 튕겨나가고 분리된 것으로 간주될 수 있다.

   이 경우 일관성은 그리 좋은 가정이라고 보기는 힘들다. 왜냐하면 일관성을 고려할 경우 프레임에서 프레임으로 넘어가면서

   거의 변하는 것이 없다고 가정할 수 있기 때문이다.