coarse collision detection은 collision-generating contacts의 첫 번째 단계이다. 이전 챕터에서의 알고리즘들은 pairs들이 실제로 충돌하는 지를 보기 위해 좀 더 상세하게 점검될 필요가 있는 오브젝트들의 쌍의 리스트를 만들어낸다.
많은 충돌 탐지 시스템은 각 쌍에 대해 이 check를 수행하고, 그 오브젝트들이 접촉한다면 maximum interpenetration의 단일점을 반환한다. 그것은 우리가 필요한 것이 아니다. 우리는 contact generation이 필요하다. 충돌하는 두 개의 오브젝트들은 그것들 사이에 있는 한 개이 상의 접촉점을 가질 수 있다. 그 충돌을 단일점으로 나타내는 것은 몇 가지 오브젝트들의 조합에 (sphere and a plane과 같은) 잘 작동하지만 다른 것들에 (자동차와 면 같은: 우리는 어떤 바퀴를 선택해야 하는가?) 대해서는 아니다.
Contact generation은 단일 교차 충돌 탐지보다 더 복잡하고, 완료짓는데 좀 더 processor time이 필요하다. 종종 우리는 contact generation의 두 단계 프로세스를 가질 것이다: 생성할 접촉이 있는지를 결정하는 fine collision detection step과 그러고나서 존재하는 contacts를 처리하는 contact generation step.
우리는 coarse filtering step을 수행했었기 때문에, fine collision detection과 contact generation을 수행하는 만큼의 많은 시간이 필요하다는 것을 의미하지 않는다. 우리는 fine collision detection이 가능한한 빠르게 작동하는 것을 보장할 필요가 있다. 우리는 full-resolution rendering geometry보다는 simplified geometry에 대해 충돌탐지를 수행하여 그 속도를 극적으로 개선시킬 수 있다.
이 챕터는 stand-in collision geometry로서 유용한 geometric primitives 사이의 contacts를 생성하는 것을 본다. 만흥ㄴ 조합들이 있고, 그래서 이 챕터는 대표적인 것을 선택해서 다루려고 한다.
그러나 이 책은 충돌 탐지에 대한 책이 아니다. 이 시리즈에는 다른 책들이 있다, van den Bergen [200]3, Ericson [2005], and Eberly [2004] 이것들은 내가 여기에서 다룰 수 있는 것보다 더 많은 자료들을 포함한다.
13.1 Collision Geometry
많은 게임들에서 복잡한 시각적 geometry는 빠른 contact generation에 대해 너무 많다. 대신에, 그것은 물리엔진을 위해 만들어진 큼지막한 geometry로 간단하게 된다. 만약 이 chunky geomtry가 어떤 geomtry primitives - 이름하여, spheres, boxes, planes, and capsules (끝이 반구인 실린더) - 이루어진다면, 그러면 그 충돌 탐지 알고리즘들은 일반 목적의 메쉬들보다 더 간단해질 수 있다.
이 충돌 geomtry는 coarse collision detection에서 사용된 bounding volume과는 같지 않다. 사실, 너가 다룰 필요가 있는 scenes의 복잡성에 따라, 너는 간단화된 geometry의 많은 다른 levels를 가질지도 모른다.
충돌탐지와 contact generation을 수행하기에 가장 간단한 도형은 구이다; 그러므로 그것이 coarse collsion geomtry로 사용된다. 빠름에도 불구하고, 그러나, 구들은 항상 끔찍히 유용하지 않다. Boxes들이 또한 상대적으로 처리하기에 더 빠르고, 더 많은 상황에서 사용될 수 있다. 캡슐들은 구보다 더 어렵지만, 몇 가지 상황에서 유용하다. disks, cylinders와 같은 trimmed primitives는 또한 유용할 수 있다.
우리가 고려할 필요가 있는 특별한 케이스는 background level geomtry와 오브젝트의 충돌이다. 대개 흔하게, 이것은 ground 또는 몇 가지 다른 평면 (일반적으로 평면으로 나타내어질 수 있는 벽)과의 충돌을 의미한다. 이것을 지원하기 위해, 우리는 또한 primitives and planes 사이의 충돌을 고려할 거싱다.
너의 게임이 필요한 primitives가 게임에 있는 어떤 extent에 의존한다는 것을 기억하는 것이 중요하다. 우리는 이 챕터에서 구와 박스에 대해 상세히 볼 것이다; 만약 그렇지 않는다면, 그 전체 책은 contact generation에 대한 것이 될 것이다. 그 원칙들은 어떤 오브젝트에 대해서든지 같다. 그래서, 이 시리즈에서 collision detection books들의 도움과 함께, 너는 다양한 범위의 primitive pairs에 대해 contacts를 생성할 수 있을 것이다.
그러나 primitives only get you so far. 모든 프리미티브들은 그것들의 오브젝트들에 대강 맞을 수 있다; 그들 자신을 프리미티브와 잘 맞지 않게 되는 오브젝트들이 있다. 이러한 경우에, 일반적인 convex mesh를 (또는 그러한 메쉬들의 집합) 사용하는 것은 더 효율적일 수 있다.
충돌 알고리즘의 각각은 교재에서 상세히 묘사되지만, 대부분의 코드는 CD에 보유된다. 알고리즘 몇몇은 매우 반복적이고, 그 코드는 만약 출력된다면 백 페이지 이상을 넘길 것이다.
13.1.1 Primitive Assemblies
많은 대다수 오브젝트들은 쉽게 단일 primitive shape로 근사되어질 수 없다. 몇 몇 개발자들은 심지어 시도하지 않는다: 그들은 모든 오브젝트들을 근사하기 위해 convex meshes를 사용한다. 또 다른 접근법은 collision geometry로서 pirmitive objects를 모은 것을 사용하는 것이다.
그림 13.1은 boxes와 spheres의 조립으로 근사된 한 오브젝트를 보여준다. 두 조립물을 충돌시키기 위해서, 우리는 각 오브젝트에서 primitives의 모든 쌍 사이의 모든 충돌들을 발견할 필요가 있다 ( 이 방식에서, 그 조립체는 우리가 chpater 12에서 보았던 bounding volumes의 hierarchy처럼 작용한다).
우리는 조립체를 primitives의 한 리스트로 나타낼 수 있다, 그 오브젝트의 원점으로부터 primitive를 이동시키는 transform matrix와 함께.
13.1.2 Generating Collision Geometry
한 오브젝트를 근사시키기 위해 collision geometry를 생성하는 것은 사소하지 않다. 가장 쉬운 방법은 디자이너에게 collision geometry를 수동으로 만들어달라고 요청하는 것이다. 이것은 어떤 특별한 알고리즘을 요구하지 않지만, 모델러와 level designers에게 큰 부담을 증가시킨다. 게임을 개발하는 것의 대부분의 비용이 디자인에 들어가는 것을 고려한다면, 이것은 최상의 경제적인 해결책이 아닐지도 모른다. 훌륭한 그래픽이 있는 많은 게임에서, 물리 통제 하에 있는 오브젝트들이 간단한 primitive shapes가 (crates and barrels, for example) 되는 경향이 있는 것은 우연이 아니다.
내가 아는 몇 개발자들은 collision geometry로서 행동하는 간단화된 convex meshes를 생성하기 위한 툴을 개발했었다. 그들이 사용하는 알고리즘들은 몇 가지 복잡한 geometry와 이 책을 넘어선 수학을 포함한다. 나는 collision primitives의 조립체를 배치할 툴들을 모른다.
13.2 Contact Generation
우리가 이미 이 챕터에서 보았듯이, collision detection과 contact generation 사이의 구분을 하는 것은 중요하다. 충돌 탐지에 대한 대부분의 책들은 너에게 physics engine collision system을 만들라고 말한다. 사실, 대부분의 상업적인 또는 오픈소스 충돌 탐지 시스템은 물리 프로그램에 적합하지 않다.
충돌 탐지는 두 오브젝트가 닿고 있는지 또는 관통하는지를 결정하고, 일반적으로 가장 큰 관통점에 대한 데이터를 제공한다. Contact generation은 접촉한 (또는 관통하고 있는) 각 오브젝트에서의 점들의 집합을 만들어 낸다.
그 차이는 중요하다. 그림 13.2에서, 한 박스는 다른 것을 가로질러서 놓여있다: 그림의 왼쪽 부분에서, 일반적인 충돌 탐지 시스템의 결과가 보여진다: 그 박스가 다소 (미시적으로) 휘어있다, 그래서 한 변이 contact를 생성한다. 그림의 오른쪽 부분에서 정확한 contact patch가 생성된다.
contact patch는 어떤 도형이든 될 수 있다. 이것은 contacts를 resolve할 때 어려운 프로그래밍 작업을 만들 수 있다. 상황을 더 쉽게 하기 위해, 우리는 오직 point contacts만을 다루고 싶다. 그림 13.2에서 보여진 naive collision detection은 이것을 하지만, 현실적인 물리를 생성하기 위해 충분한 contacts를 제공하지 않는다. 우리는 contact patch를 point contacts들의 한 집합으로 간단하게 할 믿을만한 방법이 필요하다.
그것을 하기 위해서, 우리는 그림 13.3에서 보여지듯이 contact situations의 한 집합을 다룬다. 비록 contact patch가 어떤 도형이든 될 수 있을지라도, 그림에서의 simplifications는 합리적인 물리 행동을 생성한다. 최적이 아닌 많은 상황이 있을 수 있지만, 물리가 작동중일 때 그 문제가 눈치 챌만한 것은 거의 없다. 그림 13.3에서, 이러한 경우들이 그것들이 얼마나 유용한지 순서로 배치되어 있다. 만약 우리가 그 리스트에서 더 높이 있는 유용한 contacts를 생성할 수 있다면, 우리는 더 밑에 있는 것들을 무시할 수 있다.
보여진 케이스들 중에서, 우리는 point-point contacts와 point-edge contacts를 전적으로 무시한다. 이러한 것들은 상대적으로 쉽게 다뤄질 수 있지만, 그것들은 드물고, 일반적으로 load를 취할 수 있는 다른 contact cases와 연관된다. contact가 이러한 두 형태들 중의 하나로만 나타내어질 수 있는 작은 수의 경우에, 우리는 그 contact를 놓칠 것ㅅ이다. 경험은 이것이 눈치챌만큼 충분히 중요하지 않다는 것을 보여준다.
우리가 face-face collisions를 다룰 필요가 있는 유일한 경우는 한 면 또는 다른 면이 휘어져있을 때 이다. 모든 다른 경우에, edge-edge and edge-face contacts는 정확한 물리를 줄 것이다. 유사하게, edge-face contacts는 종종 한 쌍의 edge-edge contacts로 대체될 수 있다 (edge가 휘어진 경우를 제외하고), 그리고 우리는 이러한 것을 사용하는 것을 선호할 것이다.
나오는 primitive collision cases의 각각에서, 우리는 point-face contacts와 edge-edge contacts를 처음에 볼 것이다. 곡면이 있는 그러한 primitives는 필요할 때 더 낮은 cases들을 또한 사용할 것이다.
13.2.1 Contact Data
우리가 책에서 나중에 보게 되듯이, 다음 처럼, 생성되는 각 contact에 대해 우리가 필요한 많은 데이터들이 있다.
- Collision Point : 이것은 오브젝트들 사이의 접촉 점이다. 실제로, 오브젝트들은 어느정도 관통하고 있을 것이고, 그래서 어떤 개수든 가능한 점들이 있을 것이다. 많은 옵션들로부터 한 점을 선택하는 것은 대다수 임의적이고, 극적으로 물리에 영향을 미치지 않는다.
- Collision Normal : 이것은 한 impact impulse가 두 오브젝트 사이에서 느껴지는 방향이다. 우리가 chapter 7에서 회전하지 않는 오브젝트들에 대한 충돌을 보았을 때, 이것은 관통하는 오브젝트들이 떨어져서 움직여지는 방향이다. 어떤 경우에 (point-face contacts 같은) 이것은 계산하기에 간단하다; 다른 경우에, 그 normal이 어떤 방향이여야 하는지가 명백하지 않다. 전통적으로, 그 contact normal은 관련된 첫 번째 오브젝트에서 두 번째로 향하도록 한다. 우리는 이 책에서 contact resolution code 전반적으로 이 전통을 가정할 것이다.
- Penetration Depth : 이것은 두 오브젝트들이 관통하고있는 양이다. 충돌점을 통과하여 지나는 collision normal의 방향을 따라 측정된다, 그림 13.4에서 보여지듯이.
이러한 요소들은 contact data structure에 저장된다:
다른 primitive collisions를 보기전에, 차례로 각 contact case를 보고, 그것의 파라미터가 어떻게 결정되는지를 보는 것은 가치가 있다.
13.2.2 Point-Face Contacts
Point-face contacts는 contact의 가장 흔하고, 중요한 타입이다. 그 면이 평평하거나 휘어져있뜬, 그 contact properties는 같은 방식으로 생성된다. 이것은 그림 13.5에서 보여진다.
그 contact normal은 접촉점에서 표면의 normal에 의해 주어진다. 만약 그 오브젝트 point (즉, 면과 접촉해 있는 점)이 그 표면으로 관통된다면, 그러면 그것은 보통 그 contact가 어디에서 측정되었는지를 결정하기 위해 그 표면으로 다시 사영된다.
그 접촉점은 contact와 관련된 점으로서 주어진다. 어떤 경우에, 그 face에서 이 object point와 사영된 point사이의 중간지점에 있는 점이 사용된다. 둘 중 하나의 경우가 잘 작동하지만, 주어진 점을 사용하는 것이 좀 더 효율적이다.
그 penetration depth는 object point와 사영된 point사이의 거리로서 계산된다.
13.2.2 Point-Face Contacts
Point-face contacts는 contact의 가장 흔하고, 중요한 타입이다. 그 면이 평평하거나 휘어져있뜬, 그 contact properties는 같은 방식으로 생성된다. 이것은 그림 13.5에서 보여진다.
그 contact normal은 접촉점에서 표면의 normal에 의해 주어진다. 만약 그 오브젝트 point (즉, 면과 접촉해 있는 점)이 그 표면으로 관통된다면, 그러면 그것은 보통 그 contact가 어디에서 측정되었는지를 결정하기 위해 그 표면으로 다시 사영된다.
그 접촉점은 contact와 관련된 점으로서 주어진다. 어떤 경우에, 그 face에서 이 object point와 사영된 point사이의 중간지점에 있는 점이 사용된다. 둘 중 하나의 경우가 잘 작동하지만, 주어진 점을 사용하는 것이 좀 더 효율적이다.
그 penetration depth는 object point와 사영된 point사이의 거리로서 계산된다.
13.2.3 Edge-Edge Contacts
Edge-edge contacts는 contact의 두 번째로 가장 중요한 타입이고, 평평하거나 concave한면이 있는 오브젝트 사이의 resting contacts에 중요하다. 그 contact data는 그림 13.6에서 보여진다.
그 contact normal은 두 변의 접선에 직각이다. 그 벡터곱은 이것을 계산하는데 사용된다.
Edge-edge contacts는 contact의 두 번째로 가장 중요한 타입이고, 평평하거나 concave한면이 있는 오브젝트 사이의 resting contacts에 중요하다. 그 contact data는 그림 13.6에서 보여진다.
그 contact normal은 두 변의 접선에 직각이다. 그 벡터곱은 이것을 계산하는데 사용된다.
그 contact point는 일반적으로 나머지에 대한 한 변에서 가장 가까운 점이다. 몇 개발자들은 두 변 사이의 중간 점을 사용한다, 그리고 그것을 계산하기에 더 오래걸리지만, 미미하게 더 정확하다. 관통 깊이는 두 변 사이의 거리이다.
13.2.4 Edge-Face Contacts
Edge-face contacts는 곡면과 함께 사용된다 (capsule의 edge, 예를들어, 또는 구의 표면). 그 contact data는 그림 13.7에서 보여지듯이, point-face contacts와 유사한 방법으로 생성된다.
그 contact normal은 이전처럼, face의 normal에 의해 주어진다. 그 edge direction은 이 계산에 의해 무시된다.
contact point가 일반적인 경우에 대해서 계산하기에 더 어렵다. 좀 더 일반적인 케이스에서, 우리는 기하학적으로 가장 깊은 관통점을 계산할 필요가 있다. 몇 가지 primitives에 대해, 이것을 얻는 빠른 방법이 있다.
접촉점이 계산되는 방식 때문에, 우리는 일반적으로 관통 깊이에 대한 직접적인 접근법을 가진다. 만약 그렇지 않다면, 그러면 그것은 긴 방식으로 재계산되어질 필요가 있다. 그것은 접촉점을 통과하는 normal의 방향을 따라서, edge와 face사이의 거리를 처리하여 된다.
13.2.5 Face-Face Contacts
Face-Face contacts는 곡면이 평면에 있는 구 같은 휘어져있거나 평평한 다른 면과 접촉할 때, 발생한다. 그 contact data는 어느정도 다른 경우에 대해 보다도 임의적이다. 그림 13.8은 그 특성을 상세히 보여준다.
그 contact normal은 first face의 normal에 의해 주어진다. 이론적으로, faces들은 반대의 contact normals를가져야 한다: 두 면들은 그것들의 normals이 반대방향인것을 제외하고 닿을 수 없다. 그러나, 실제로, 이것은 완벽하지 않다. 그리고 오브젝트들이 관통할지도 모른다는 사실은, 실제 normals들이 잘못 정렬되어질지도 모른다는 것을 의미한다. 두 오브젝트들이 미래의 contact generations에서 역할을 바꾸지 않는 한 (즉, 다음 프레임에서, 우리는 오브젝트 A와 B가 바뀌는 contact generation을 갖는 것을피해야 한다), 한 contact normal을일관적으로 사용하는 것이 더 쉽다. 그러한 swapping을 찾는 것은 보통 있는 것이 아니며, 그래서 그것은 안전하게 무시된다.
contact point는 또 다시 일반적인 경우에 계산하기에 어렵다. 그리고 다시 한 번, 이 챕터에서 primitives를 사용하여, 우리는 종종 가장 큰 관통점에 직접적으로 도달할 수 있다. 만약 그렇지않다면, 그러면 우리는 관통하는 volume의 내부로부터 어떤 point를 선택할 필요가 있다 (이것을 하는 코드는 내가 본 바로는 꽤 임의적ㄱ이다).
그 contact point calculation은 일반적으로 우리에게 관통 깊이에 대한 직접적인 접근권을 준다. 일반적인 경우에, 우리는 지난 섹션에서 보았듯이, full algorithm을 따를 것이다.
13.2.6 Early-Outs
몇 가지 contact generation algorithms는 꽤 시간을 소모할 수 있다. coarse collision detection은 나중에 접촉하지 않는 것으로 발견될지도 모르는, 오브젝트들의 후보쌍을 만들어낼 것이다. 우리는 만약 어떠한 접촉도 발견되지 않는다면 일찍 종료하는 알고리즘을 만들어서, 충돌 탐지를 훨씬 더 효율적으로 만들 수 있다.
우리가 나중에 보게 될 contact generation algorithms의 일부로서 이것을 하는 수 많은 기회들이 있고, 그 코드는 가능한한 이러한 많은 것들을 이용한다.
Edge-face contacts는 곡면과 함께 사용된다 (capsule의 edge, 예를들어, 또는 구의 표면). 그 contact data는 그림 13.7에서 보여지듯이, point-face contacts와 유사한 방법으로 생성된다.
그 contact normal은 이전처럼, face의 normal에 의해 주어진다. 그 edge direction은 이 계산에 의해 무시된다.
contact point가 일반적인 경우에 대해서 계산하기에 더 어렵다. 좀 더 일반적인 케이스에서, 우리는 기하학적으로 가장 깊은 관통점을 계산할 필요가 있다. 몇 가지 primitives에 대해, 이것을 얻는 빠른 방법이 있다.
접촉점이 계산되는 방식 때문에, 우리는 일반적으로 관통 깊이에 대한 직접적인 접근법을 가진다. 만약 그렇지 않다면, 그러면 그것은 긴 방식으로 재계산되어질 필요가 있다. 그것은 접촉점을 통과하는 normal의 방향을 따라서, edge와 face사이의 거리를 처리하여 된다.
13.2.5 Face-Face Contacts
Face-Face contacts는 곡면이 평면에 있는 구 같은 휘어져있거나 평평한 다른 면과 접촉할 때, 발생한다. 그 contact data는 어느정도 다른 경우에 대해 보다도 임의적이다. 그림 13.8은 그 특성을 상세히 보여준다.
그 contact normal은 first face의 normal에 의해 주어진다. 이론적으로, faces들은 반대의 contact normals를가져야 한다: 두 면들은 그것들의 normals이 반대방향인것을 제외하고 닿을 수 없다. 그러나, 실제로, 이것은 완벽하지 않다. 그리고 오브젝트들이 관통할지도 모른다는 사실은, 실제 normals들이 잘못 정렬되어질지도 모른다는 것을 의미한다. 두 오브젝트들이 미래의 contact generations에서 역할을 바꾸지 않는 한 (즉, 다음 프레임에서, 우리는 오브젝트 A와 B가 바뀌는 contact generation을 갖는 것을피해야 한다), 한 contact normal을일관적으로 사용하는 것이 더 쉽다. 그러한 swapping을 찾는 것은 보통 있는 것이 아니며, 그래서 그것은 안전하게 무시된다.
contact point는 또 다시 일반적인 경우에 계산하기에 어렵다. 그리고 다시 한 번, 이 챕터에서 primitives를 사용하여, 우리는 종종 가장 큰 관통점에 직접적으로 도달할 수 있다. 만약 그렇지않다면, 그러면 우리는 관통하는 volume의 내부로부터 어떤 point를 선택할 필요가 있다 (이것을 하는 코드는 내가 본 바로는 꽤 임의적ㄱ이다).
그 contact point calculation은 일반적으로 우리에게 관통 깊이에 대한 직접적인 접근권을 준다. 일반적인 경우에, 우리는 지난 섹션에서 보았듯이, full algorithm을 따를 것이다.
13.2.6 Early-Outs
몇 가지 contact generation algorithms는 꽤 시간을 소모할 수 있다. coarse collision detection은 나중에 접촉하지 않는 것으로 발견될지도 모르는, 오브젝트들의 후보쌍을 만들어낼 것이다. 우리는 만약 어떠한 접촉도 발견되지 않는다면 일찍 종료하는 알고리즘을 만들어서, 충돌 탐지를 훨씬 더 효율적으로 만들 수 있다.
우리가 나중에 보게 될 contact generation algorithms의 일부로서 이것을 하는 수 많은 기회들이 있고, 그 코드는 가능한한 이러한 많은 것들을 이용한다.
몇 가지 primitive collisions는 완전히 다른 알고리즘을 갖는데, 그것들은 contacts를생성하는 것 없이 contact가 있는지를 결정할 수 있다. 만약 그러한알고리즘이 존재하고 충분히 빠르다면, 첫 번째 단계로서 그것을 호출하는 것은 유용할 수 있다:
if(inContact())
findContacts();
게임 그래픽스에서 책에서 종종 발견되는 충돌 탐지 알고리즘들이 있다.
그러나, 많은 경우에, 빠른 check가 해야만 하는 작업은 contact generation 동안에 요구되는 것과 같다. 둘 다를 하는 것의 속도 가속은 최손한이 될 것이다. 우리가 테스트에서 어떠한 contact도 얻지 못하는 횟수에 대해. 이러한 경우들에서, contact generation algorithm은 그것 스스로 사용되어질 수 있다.
13.3 Primitive Collision Algorithms
if(inContact())
findContacts();
게임 그래픽스에서 책에서 종종 발견되는 충돌 탐지 알고리즘들이 있다.
그러나, 많은 경우에, 빠른 check가 해야만 하는 작업은 contact generation 동안에 요구되는 것과 같다. 둘 다를 하는 것의 속도 가속은 최손한이 될 것이다. 우리가 테스트에서 어떠한 contact도 얻지 못하는 횟수에 대해. 이러한 경우들에서, contact generation algorithm은 그것 스스로 사용되어질 수 있다.
13.3 Primitive Collision Algorithms
이 챕터에서 충돌 알고리즘의 각각은 contact를 검사하고, primitives의 다른 조합에 대해 contact data structures를 생성한다. 몇 가지 알고리즘은 오직 0 또는 한 개의 contact만을 반환하도록 보장된다 (예를들어, sphere-sphere collision). 우리는 이러한 알고리즘들이 contacts를 직접 반환하도록 할 수 있다.
종종 알고리즘들은 zero, one, or 몇 가지의 contacts를 반환할 수 있다. 이 경우에, 우리는 그것이 생성한 contacts들을 알고리즘들이 반환하게 하는 좀 더 유연한 방법이 필요하다. 이것을 하는 가장 간단한 방법은 가능한 contacts의 list or array로 시작하는 것이다. 이 array는 그러고나서 각 contact generation routine이 넘겨진다. 만약 그 routine이 contacts를 발견한다면, 그것은 그것들을 그 array에 쓸 수 있다.
코드에서, 나는 이 과정을 한 클래스에 캡슐화 했다:
각 contact generation routine은 같은 형태를 갖는다:
void detectContacts(const Primitive& firstPrimitive, const Primitive& secondPrimitive,
CollisionData* data);
여기에서 Primitive type은 collision geometry에 대한 데이터를 갖고 있다. 그 Primitive class는 어떤 contact generator든 알 필요가 있는 데이터를 가지고 있다, geometry에 대응되는 rigid body같은것과 rigid body의 좌표 원점으로부터의 primitive의 offset 같은.
이 챕터 전반에 걸쳐, 나는 offset matrix가 translation과 rotation만을 나타낸다고 가정할 것이다: 그것은 어떠한 scaling or skewing effect를 가지고 있지 않다. 우리는 이것을 더 간단하게 만들고, 그 primitive가 완벽히 rigid body의 중심과 회전 없이 일치한다고 가정할 수 있다 (예를들어, 만약 우리가 barrel를 나타내는 cylinder를 가졌다면 사실일 것이다). 불행히도, 이것은 오브젝트의 조립체에 대해 작동하지 않을 것이다, 또는 그것들의 geometric center에 있지 않는 center of mass를 가진 rigid bodies서도 작동하지 않을것이다. 유연성을 위해서, primitives가 그것들의 rigid bodies로부터 offset되도록 하는 것을 허용하는 것이 가장 좋다.
각 구현된 contact generation function은 몇 가지 부가 데이터와 함께 Primitive의 subtype을 사용할 것이다 (Sphere and Plane). 나는 이러한 타입을 진행함에 따라 소개할 것이다.
13.3.1 Colliding Two Spheres
충돌하는 두 구들은 그것을 얻는 만큼 간단하다. 두 구들은 만약 그것들 중심사이의 거리가 그것들의 반지름의 합 보다 작다면 접촉해 있다.
만약 그것들이 접촉해 있다면, 그러면 정확히 한 contact point가 있을 것이다: 각 sphere는 한 가지 표면으로 구성되는데, 그래서 그것은 face-face contact일 것이다 (see Figure 13.8).
가장 깊은 contact point는 sphere centers 사이의 선을 따라 위치해 있다. 이것은 정확히 우리가 chapter 7에서 보았던 것과 같은 알고리즘이다. 우리 particle collision을 보았을 때.
이것을 구현하기 위해서, 우리는 sphere에 대한 자료구조가 필요하다. Spheres는 완전히 그것들의 center point와 radius에 의해 정의된다:
그 구의 center point는 rigid body의 원점으로부터의 offset에 의해 주어지는데, Primitive에 포함된 데이터이다. 그 sphere 구현은 이것처럼 보일 것이다:
그 알고리즘은 두 개의 구를 취하고, contact data에 한 contact를 생성할지도 모른다. 그 두 개의 구가 충돌하는지를 결정할 그 알고리즘이 contact data를 결정하는 것의 일부이기 때문에, 우리는 early out을 제공하는 separate algorithm을 갖지 않는다.
13.3.2 Colliding A Sphere And A Plane
구와 평면이 충돌하는것은 두 개의 구가 충돌하는 것만큼 간단하다. 만약 구의 중심의 거리가 평면으로부터 구의 반지름보다 더 멀리 있다면, 그 구는 평면과 충돌한다. 한 평면으로부터의 한 점의 거리는 다음과 같이 주어진다:
여기에서 l은 평면의 normal vector이고, l은 평면의 위치이다. 이것은 3D 기하에서, 평면을 나타내는 간단한 표준 방식이다.
우리는 평면을 코드로 이렇게 나타낼 수 있다:
평면들은 거의 rigid body보다는 움직일 수 없는 도형과 항상 관련이 있다. 그래서 Primitive class에서 rigid body pointer는 일반적으로 NULL일 것이다.
그 알고리즘은 sphere와 plane을 취하고, contact data에 한 contact를 더할지도 모른다. 또 다시, 그 알고리즘은 분리된 early-out 알고리즘으로부터 이익을 얻지 않을 만큼 충분히 간단하다.
엄격히 말해서, 이것은 sphere-plane collision이 아닌, sphere-half-space collision이다. 그림 13.9는 그 차이점을 보여준다. 평면들은 결코 한 게임에서 필요하지 않다 (왜냐하면 그것들은 무한히 크기 때문에, 그러나 half-spaces는 흔하다. 그것들은 보통 BSP tree의 부분으로서 땅과 벽을 나타내기 위해 사용된다.
그 알고리즘이 진정한 plane-sphere collisions를 수행하기 위해, 우리는 그 거리가 구의 반지름보다 크거나 또는 그 반지름의 음보다 더 작은지를 검사할 필요가 있다.
둘 다 CD에 구현되어지만, 데모에서는 오직 half-space만이 사용된다.
13.3.3 Colliding A Box And A Plane
매우 간단한 contact generation algorithms의 마지막 것은 box와 plane사이의 것이다 (엄밀히 말해서, half-space). 이것은 한 개의 contact이상을 반환 할 수 있는 첫 번째 알고리즘이다.
우리가 가능한한 처리하기에 간단한 contacts를 사용하려고 한다는 것을 기억해라. 우리는 만약 할 수 있다면, point-face를 사용하는 것을 선호한다. 우리가 할 수 있는 경우에. half-space와 한 box의 face의 contact를 반환하기 보다는, 우리는 half-space와의 각 4개의 모서리점에 대한 4개의 contacts를 반환한다. 유사하게, 만약 한 edge가 그 평면과 충돌한다면, 우리는 그것을 두 점으로서 다룬다 - 각 edge의 각 끝에 대한 face contacts. 따라서, 4개 까지의 contacts가 있을 수 있고, 각각은 point-face contact이다. 그림 13.10이 이것을 보여준다.
우리는 하나씩 box의 각 vertex를 간단히 체크하고, 만약 그것이 평면의 밑에 놓여있따면 contact를 생성하여 contacts의 set를 발견할 수 있다.
각 정점에 대한 check는 우리가 sphere-plane detector로 만든것처럼 보인다:
그 정점이 유일한 점이고, 반지름을 가지지 않기 때문에, 우리는 간단히 d의 기호가 양수인지 음수인지를 보기 위해 체크할 필요가 있다. 그러므로 collision은
이라면 발생한다.
p에 있는 한 정점에 대해, contact를 발생시키는 코드는 이것처럼 보인다:
full algorithm은 그 박스의 각 정점에 대해 이 코드를 작동시킨다. 우리는 이것처럼 보이는 box data structure로부터 정점들의 set를 생성시킬 수 있다:
전체 알고리즘은 간단히 차례로 각 정점을생성하고, 평면에 대해 테스트한다. 그리고 필요하다면 contact를 추가한다. 전체 알고리즘은 꽤 반복적이여서, 그래서 나는 그것을 여기에 반복하지 않을 것이다. 너는 그것을 CD에서 찾을 수 있다.
모든 정점들을 생성하고 테스팅하는 것을 피하는 알고리즘이 있다는 것에 주목해라. 평면의 normal에 대해 각 box의 방향을 비교하여, 우리는 검사될 필요가 있는 정점들의 개수를 줄일 수 있다. 너는 그러한 알고리즘ㄷ르이 다른 책이나 또는 온라인으로 발견할지도 모른다.
그러한 알고리즘의 미미한 이론적 장점에도 불구하고, 나는 실제로 어떠한 효율성의 이득이 없다는 것을 알았다. 한 정점을 생성하고 테스팅하는 것은 매우 빨라서, 부가적인 checking은 미미한 효과를 갖는다. 만약 너가 그 기법에 익숙하다면, 너는 이 알고리즘이 SIMD 하드웨어에서 병렬 구현에 그 자체로 내줄 수 있다는 것을 눈치챌 것이다. simd 하드웨어는 그 대안을 훨씬 덜 매력적이게 만든다.
13.3.4 Colliding A Sphere And A Box
한 box는 어느정도 계산을 복잡하게 한다. 한 sphere가 한 box와 충돌할 때, 우리는 한 contact를가질 것이다. 그러나 그것은 어떤 유형의 contact가 될지도 모른다 : face-face contact, edge-face contact, or point-face contact. 각 경우에, 그 sphere (어떠한 edges or vertices를 가지지 않는)는 한 face를 그 contact에 기여하지만, 그것은 box의 face, edge 또는 point 들 중 하나에 닿을지도 모른다. 그림 13.12이 이것을 보여준다.
운 좋게도, 이러한 경우들 모두 세 개가 normal contact와 penetration depth에 대해 같은 계산을 포함한다, face-face contact의 경우에서 그 sphere가 contact normal를 결정한다고 가정하는한. (face-face contacts에 대해, 하나 또는 다른 오브젝트가 normal 처리해야 하는 것을 회상해라.)
또 다시, 우리는 sphere보다는 한 점을 사용하는 이 query를 간단하게 할 수 있다. 이 경우에, 우리는 sphere의 중심으로 가는 박스에서 가장 가까운 점을 찾을 필요가 있다. 이 가장 가까운 점은 박스의 모서리, 변을 따라 있는, 또는 면 위에 있는 점일지도 모른다. 만약 그 가장 가까운 점과 sphere의 중심과의 거리가 구의 반지름보다 작다면, 그러면 그 두 오브젝트들은 닿고있는 중이다.
우리가 같은 방식으로, contact의 모든 세 가지 방식을 다룰 거이기 때문에 - sphere의 특징이 contact data를 결정하게 허용하면서 - 우리는 box에서 가장 가까운 점이 face, edge, or vertex 위에 있는지를 추적할 필요가 없다.
우리의 프로세스의 첫 번째 단계는 구의 중심점을 box의 object coordinates로 변환하는 것이다. 그 box가 어떤 방향에서 든지 향하여 질 수 있다는 것을 기억해라. 우리가 작업하고 있는 점의 좌표가 box의 방향을 기준이라면 처리하기 더 쉬울 것이다. 우리는 다음의 코드를 사용해서 이것을 간단하게 한다:
우리가 박스의 방향과 그것의 중심점 둘 다를 고려한다는 것에 주목해라.
이것은그러고나서 우리가 그 점이 충분히 건드릴만큼 가까운지를 보기 위해 빠른 early-out test를 수행하는 것을 허용한다. 그 contact generation은 이 early test를 통과하는 점들에 대해 보존될 것이다. 우리가 보게 되듯이, 그 contact generation algorithm은 거의 복잡하지는 않고, 우리는 early-out test를 함으로써, 큰 양을 얻지 않는다. 그럼에도 불구하고, 어떤 경우에 그것은 그럴 만한가치가 있다 (특히, 만약 그 coarse collision detection이 비효율적이고, 많은 가능한 collisions를 생성한다면).
그 early-out test는 separating axes의 원리에 의존한다.
Separating Axes
Separating axes는 충돌 탐지에서 가장 유용한 개념들 중 하나이다. 그것은 많은 뉘앙스를 갖는데, 나는 여기에서 다루는 것을 희망할 수 없다. van den Bergen [2003] 또는 Ericson [2005]를 보아라, 완전한 이야기와, 많은 도움되는 다이어그램을 위해서.
그 기본 아이디어는 간단하다: 만약 우리가 두 (convex) 오브젝트들이 충돌하지 않는 공간에서 어떤 방향을 찾을 수 있다면, 그러면 그 오브젝트들은 전혀 충돌하고 있지 않다. 우리의 경우에, 우리는 간단히 그 박스의 세 개의 축들 검사하고, 그 점이 충돌할 것과 멀리 있는지를 검사한다. 만약 이러한 축들 중 어떤 것이 그 점이 너무 멀리 있다는 것을 보여준다면, 그러면 우리는 충돌이 없다는 것을 알고, 우리는 더 일찍 끝낼 수 있다. 그림 13.13은 이것을 2D에서 보여준다.
이 경우에, 그 알고리즘은 좀 더 완전한 contact generation으로 보내질 것이고, 나중에 어떠한 contact가 없다는 것을 탐ㅁ지할 것이다. 우리는 이 경우에 더 멀리 있는 축들을 점검하는 separating axes test를 개선할 수 있다 (box의 중심으로부터 sphere의 center까지의 축이 도움이 될 것이다. 그러나, 이 단계가 우리에게 early-out을 주기위해 설계되었다는 것을 기억해라. 우리는 processing time을 낭비하기를 원하지 않고, 그래서 우리는 이 단계에서 contact가 있는지를 결정하기 위해 많은 시간을 쓸 수 있는데, 다음 phase에서 full contact generation을 수행하지 않음으로써 절약하는 만큼이다. 다음 코드 블럭을 보아라.
Contact Generation
우리의 알고리즘의 마지막 단계는 박스에서 타겟 포인트로 가는 가장 가까운 점을 찾고, 그것으로부터 contact를 생성하는 것이다. 우리는 box의 coordinate에서 이것을 처음에 할 것이다.
이것은 간단한 프로세스이다. 우리가 할 필요가 있는 모든 것은 box의 half-size에 대한 test point의 각 component를 같은 방향으로 clamp하는 것이다. 이 새로운 점으로, 우리는 그러고나서 구의 중심점으로부터 target point까지의 거리를 처리할 수 있고, 만약 그것이 구의 반지름보다 더 크다면, 끝낼 수 있따. 이것에 대한 코드는 간단하다:
그 contact properties는 월드 좌표계에서 주어져야 할 필요가 있다. 그래서 우리가 contact normal을 하기전에, 우리는 world coordinates에서 가장 가까운 점을 찾을 필요가 있다. 이것은 간단히 우리가 이전에 생성한 점을 변환하는 것을 의미한다:
우리는 그러고나서 챕터의 이전처럼 contact properties를 계산할 수 있다. 그 최종 코드는 모두 합쳐서 이렇게 보인다:
13.3.5 Colliding Two Boxes
두 개의 박스들의 충돌은 우리가 이 챕터에서 상세하게 고려할 가장 복잡한 케이스이다. 비록 우리가 여전히 매우 기본 도형을 다루고 있지만, 박스들의 한 쌍을 다루는데 필요한 기법들은 충돌하는 도형들이 좀 더 복잡할 때 사용되는 것들이다. 이 섹션의 마지막에서, 우리는 box-box collision algorithm이 concave shapes의 어떤 상으로 어떻게 확장되어질 수 있는지를 볼 것이다.
두 박스들 사이에 contact의 가능한 6개의 타입들이 있다, 그림 13.14에서 보여지듯이.
우리는 face-face와 edge-face contacts를 피하려고 노력할 것이다. 왜냐하면 그것들은 안정적이지 않기 때문이다. 두 면 사이의 단일의 contact point는 그 평면이 회전하게 한다; contact normal이 두 centers of gravity를 통과하여 지나기 위해서 contact normal가 생성될 가능성은 높지 않다. 만약 우리가 3개 또는 4개의 contacts를 대신에 사용한다면, 그러면 최종 contact resolution은 시각적으로 좀 더 안정된 겨롹를 줄 것이다.
우리는 항상 face-face contact를 4개 까지의 point-face or edge-edge contacts로 대체할 수 있다. 그림 13.15에서 보여지듯이. 유사하게, 우리는 face-edge contacts를 두 개 까지의 point-face or edge-edge contacts로 대체할 수 있다.
그 나머지 두 개의 contacts들 즉, point-point와 point-edge는 다른것들로 대체되어질 수 없다. 우리는 이것들을 탐지하는 코드를 추가하지만, 그것들중 어떠한 것도 collision normal을 계산하는 명백한 방법을 가지지 않는다 (각각에 대해 유효한 collision normals의 무한한 개수가 있다). 우리는 충돌 normal을 얻기위해 몇 가지 추가 hacked code를 필요할 것이다.
내가 구성한 시스템에서, 나는 결코 두 가지 이유 때문에 이것을 하는데 시달리지 않는다. 첫 째로, 이러한 상황들은 고의로 되어지지않는다면, 실제로 일어날 가능성이 매우 낮다. 다른 박스와 완벽히 vertex to vertex로 충돌하는 한 박스의 가능성은 정말로 매우 작다: 그것은 매우 작은 target이니까 (point-edge는 좀 더 일어날 가능성이 높지만, 여전히 놀랄만하게 드물다). 둘 째로, 만약 우리가 이러한 contacts들을 무시한다면, 짧은 순간 뒤에, 그 박스들은 조금 관통할 것이다. 이 경우에, 다른 contacts들 중 하나 (일반적으로 point-face contact)가 생성될 것이고, 물리에 의해 일반적으로 처리된다. 그 결과는 물리적으로 믿을만하고, 그래서 추가 work가 간단히 필요하지 않다.
이러한 두 contact의 타입들을 무시하는 것은, 박스들이 신중하게 corner to corner or edge to corner로 균형 맞추어지는 시나리오들을 구성할 수 없다는 것을 의미한다. 그러나 그것은 너의 게임 디자인에서 높은 우선순위가 아닐 가능성이 높기 때문에, 너는 아마도 작업을 줄이고 그것과 함께 나아갈 수 있따.
박스들 사이의 contacts들을 생성하는 그 알고리즘은 sphere and box에 대한 것과 같은 포맷을 갖는데, 한 가지 추가적인 단계가 있다:
종종 알고리즘들은 zero, one, or 몇 가지의 contacts를 반환할 수 있다. 이 경우에, 우리는 그것이 생성한 contacts들을 알고리즘들이 반환하게 하는 좀 더 유연한 방법이 필요하다. 이것을 하는 가장 간단한 방법은 가능한 contacts의 list or array로 시작하는 것이다. 이 array는 그러고나서 각 contact generation routine이 넘겨진다. 만약 그 routine이 contacts를 발견한다면, 그것은 그것들을 그 array에 쓸 수 있다.
코드에서, 나는 이 과정을 한 클래스에 캡슐화 했다:
각 contact generation routine은 같은 형태를 갖는다:
void detectContacts(const Primitive& firstPrimitive, const Primitive& secondPrimitive,
CollisionData* data);
여기에서 Primitive type은 collision geometry에 대한 데이터를 갖고 있다. 그 Primitive class는 어떤 contact generator든 알 필요가 있는 데이터를 가지고 있다, geometry에 대응되는 rigid body같은것과 rigid body의 좌표 원점으로부터의 primitive의 offset 같은.
이 챕터 전반에 걸쳐, 나는 offset matrix가 translation과 rotation만을 나타낸다고 가정할 것이다: 그것은 어떠한 scaling or skewing effect를 가지고 있지 않다. 우리는 이것을 더 간단하게 만들고, 그 primitive가 완벽히 rigid body의 중심과 회전 없이 일치한다고 가정할 수 있다 (예를들어, 만약 우리가 barrel를 나타내는 cylinder를 가졌다면 사실일 것이다). 불행히도, 이것은 오브젝트의 조립체에 대해 작동하지 않을 것이다, 또는 그것들의 geometric center에 있지 않는 center of mass를 가진 rigid bodies서도 작동하지 않을것이다. 유연성을 위해서, primitives가 그것들의 rigid bodies로부터 offset되도록 하는 것을 허용하는 것이 가장 좋다.
각 구현된 contact generation function은 몇 가지 부가 데이터와 함께 Primitive의 subtype을 사용할 것이다 (Sphere and Plane). 나는 이러한 타입을 진행함에 따라 소개할 것이다.
13.3.1 Colliding Two Spheres
충돌하는 두 구들은 그것을 얻는 만큼 간단하다. 두 구들은 만약 그것들 중심사이의 거리가 그것들의 반지름의 합 보다 작다면 접촉해 있다.
만약 그것들이 접촉해 있다면, 그러면 정확히 한 contact point가 있을 것이다: 각 sphere는 한 가지 표면으로 구성되는데, 그래서 그것은 face-face contact일 것이다 (see Figure 13.8).
가장 깊은 contact point는 sphere centers 사이의 선을 따라 위치해 있다. 이것은 정확히 우리가 chapter 7에서 보았던 것과 같은 알고리즘이다. 우리 particle collision을 보았을 때.
이것을 구현하기 위해서, 우리는 sphere에 대한 자료구조가 필요하다. Spheres는 완전히 그것들의 center point와 radius에 의해 정의된다:
그 구의 center point는 rigid body의 원점으로부터의 offset에 의해 주어지는데, Primitive에 포함된 데이터이다. 그 sphere 구현은 이것처럼 보일 것이다:
그 알고리즘은 두 개의 구를 취하고, contact data에 한 contact를 생성할지도 모른다. 그 두 개의 구가 충돌하는지를 결정할 그 알고리즘이 contact data를 결정하는 것의 일부이기 때문에, 우리는 early out을 제공하는 separate algorithm을 갖지 않는다.
13.3.2 Colliding A Sphere And A Plane
구와 평면이 충돌하는것은 두 개의 구가 충돌하는 것만큼 간단하다. 만약 구의 중심의 거리가 평면으로부터 구의 반지름보다 더 멀리 있다면, 그 구는 평면과 충돌한다. 한 평면으로부터의 한 점의 거리는 다음과 같이 주어진다:
여기에서 l은 평면의 normal vector이고, l은 평면의 위치이다. 이것은 3D 기하에서, 평면을 나타내는 간단한 표준 방식이다.
우리는 평면을 코드로 이렇게 나타낼 수 있다:
평면들은 거의 rigid body보다는 움직일 수 없는 도형과 항상 관련이 있다. 그래서 Primitive class에서 rigid body pointer는 일반적으로 NULL일 것이다.
그 알고리즘은 sphere와 plane을 취하고, contact data에 한 contact를 더할지도 모른다. 또 다시, 그 알고리즘은 분리된 early-out 알고리즘으로부터 이익을 얻지 않을 만큼 충분히 간단하다.
엄격히 말해서, 이것은 sphere-plane collision이 아닌, sphere-half-space collision이다. 그림 13.9는 그 차이점을 보여준다. 평면들은 결코 한 게임에서 필요하지 않다 (왜냐하면 그것들은 무한히 크기 때문에, 그러나 half-spaces는 흔하다. 그것들은 보통 BSP tree의 부분으로서 땅과 벽을 나타내기 위해 사용된다.
그 알고리즘이 진정한 plane-sphere collisions를 수행하기 위해, 우리는 그 거리가 구의 반지름보다 크거나 또는 그 반지름의 음보다 더 작은지를 검사할 필요가 있다.
둘 다 CD에 구현되어지만, 데모에서는 오직 half-space만이 사용된다.
13.3.3 Colliding A Box And A Plane
매우 간단한 contact generation algorithms의 마지막 것은 box와 plane사이의 것이다 (엄밀히 말해서, half-space). 이것은 한 개의 contact이상을 반환 할 수 있는 첫 번째 알고리즘이다.
우리가 가능한한 처리하기에 간단한 contacts를 사용하려고 한다는 것을 기억해라. 우리는 만약 할 수 있다면, point-face를 사용하는 것을 선호한다. 우리가 할 수 있는 경우에. half-space와 한 box의 face의 contact를 반환하기 보다는, 우리는 half-space와의 각 4개의 모서리점에 대한 4개의 contacts를 반환한다. 유사하게, 만약 한 edge가 그 평면과 충돌한다면, 우리는 그것을 두 점으로서 다룬다 - 각 edge의 각 끝에 대한 face contacts. 따라서, 4개 까지의 contacts가 있을 수 있고, 각각은 point-face contact이다. 그림 13.10이 이것을 보여준다.
우리는 하나씩 box의 각 vertex를 간단히 체크하고, 만약 그것이 평면의 밑에 놓여있따면 contact를 생성하여 contacts의 set를 발견할 수 있다.
각 정점에 대한 check는 우리가 sphere-plane detector로 만든것처럼 보인다:
그 정점이 유일한 점이고, 반지름을 가지지 않기 때문에, 우리는 간단히 d의 기호가 양수인지 음수인지를 보기 위해 체크할 필요가 있다. 그러므로 collision은
이라면 발생한다.
p에 있는 한 정점에 대해, contact를 발생시키는 코드는 이것처럼 보인다:
full algorithm은 그 박스의 각 정점에 대해 이 코드를 작동시킨다. 우리는 이것처럼 보이는 box data structure로부터 정점들의 set를 생성시킬 수 있다:
전체 알고리즘은 간단히 차례로 각 정점을생성하고, 평면에 대해 테스트한다. 그리고 필요하다면 contact를 추가한다. 전체 알고리즘은 꽤 반복적이여서, 그래서 나는 그것을 여기에 반복하지 않을 것이다. 너는 그것을 CD에서 찾을 수 있다.
모든 정점들을 생성하고 테스팅하는 것을 피하는 알고리즘이 있다는 것에 주목해라. 평면의 normal에 대해 각 box의 방향을 비교하여, 우리는 검사될 필요가 있는 정점들의 개수를 줄일 수 있다. 너는 그러한 알고리즘ㄷ르이 다른 책이나 또는 온라인으로 발견할지도 모른다.
그러한 알고리즘의 미미한 이론적 장점에도 불구하고, 나는 실제로 어떠한 효율성의 이득이 없다는 것을 알았다. 한 정점을 생성하고 테스팅하는 것은 매우 빨라서, 부가적인 checking은 미미한 효과를 갖는다. 만약 너가 그 기법에 익숙하다면, 너는 이 알고리즘이 SIMD 하드웨어에서 병렬 구현에 그 자체로 내줄 수 있다는 것을 눈치챌 것이다. simd 하드웨어는 그 대안을 훨씬 덜 매력적이게 만든다.
13.3.4 Colliding A Sphere And A Box
한 box는 어느정도 계산을 복잡하게 한다. 한 sphere가 한 box와 충돌할 때, 우리는 한 contact를가질 것이다. 그러나 그것은 어떤 유형의 contact가 될지도 모른다 : face-face contact, edge-face contact, or point-face contact. 각 경우에, 그 sphere (어떠한 edges or vertices를 가지지 않는)는 한 face를 그 contact에 기여하지만, 그것은 box의 face, edge 또는 point 들 중 하나에 닿을지도 모른다. 그림 13.12이 이것을 보여준다.
운 좋게도, 이러한 경우들 모두 세 개가 normal contact와 penetration depth에 대해 같은 계산을 포함한다, face-face contact의 경우에서 그 sphere가 contact normal를 결정한다고 가정하는한. (face-face contacts에 대해, 하나 또는 다른 오브젝트가 normal 처리해야 하는 것을 회상해라.)
또 다시, 우리는 sphere보다는 한 점을 사용하는 이 query를 간단하게 할 수 있다. 이 경우에, 우리는 sphere의 중심으로 가는 박스에서 가장 가까운 점을 찾을 필요가 있다. 이 가장 가까운 점은 박스의 모서리, 변을 따라 있는, 또는 면 위에 있는 점일지도 모른다. 만약 그 가장 가까운 점과 sphere의 중심과의 거리가 구의 반지름보다 작다면, 그러면 그 두 오브젝트들은 닿고있는 중이다.
우리가 같은 방식으로, contact의 모든 세 가지 방식을 다룰 거이기 때문에 - sphere의 특징이 contact data를 결정하게 허용하면서 - 우리는 box에서 가장 가까운 점이 face, edge, or vertex 위에 있는지를 추적할 필요가 없다.
우리의 프로세스의 첫 번째 단계는 구의 중심점을 box의 object coordinates로 변환하는 것이다. 그 box가 어떤 방향에서 든지 향하여 질 수 있다는 것을 기억해라. 우리가 작업하고 있는 점의 좌표가 box의 방향을 기준이라면 처리하기 더 쉬울 것이다. 우리는 다음의 코드를 사용해서 이것을 간단하게 한다:
// Transform the centre of the sphere into box coordinates glm::vec3 centre = sphere.getAxis(3); centre.x -= box.transform[3][0]; centre.y -= box.transform[3][1]; centre.z -= box.transform[3][2]; glm::vec3 relCentre = glm::transpose(glm::mat3(box.transform)) * centre;
우리가 박스의 방향과 그것의 중심점 둘 다를 고려한다는 것에 주목해라.
이것은그러고나서 우리가 그 점이 충분히 건드릴만큼 가까운지를 보기 위해 빠른 early-out test를 수행하는 것을 허용한다. 그 contact generation은 이 early test를 통과하는 점들에 대해 보존될 것이다. 우리가 보게 되듯이, 그 contact generation algorithm은 거의 복잡하지는 않고, 우리는 early-out test를 함으로써, 큰 양을 얻지 않는다. 그럼에도 불구하고, 어떤 경우에 그것은 그럴 만한가치가 있다 (특히, 만약 그 coarse collision detection이 비효율적이고, 많은 가능한 collisions를 생성한다면).
그 early-out test는 separating axes의 원리에 의존한다.
Separating Axes
Separating axes는 충돌 탐지에서 가장 유용한 개념들 중 하나이다. 그것은 많은 뉘앙스를 갖는데, 나는 여기에서 다루는 것을 희망할 수 없다. van den Bergen [2003] 또는 Ericson [2005]를 보아라, 완전한 이야기와, 많은 도움되는 다이어그램을 위해서.
그 기본 아이디어는 간단하다: 만약 우리가 두 (convex) 오브젝트들이 충돌하지 않는 공간에서 어떤 방향을 찾을 수 있다면, 그러면 그 오브젝트들은 전혀 충돌하고 있지 않다. 우리의 경우에, 우리는 간단히 그 박스의 세 개의 축들 검사하고, 그 점이 충돌할 것과 멀리 있는지를 검사한다. 만약 이러한 축들 중 어떤 것이 그 점이 너무 멀리 있다는 것을 보여준다면, 그러면 우리는 충돌이 없다는 것을 알고, 우리는 더 일찍 끝낼 수 있다. 그림 13.13은 이것을 2D에서 보여준다.
이 경우에, 그 알고리즘은 좀 더 완전한 contact generation으로 보내질 것이고, 나중에 어떠한 contact가 없다는 것을 탐ㅁ지할 것이다. 우리는 이 경우에 더 멀리 있는 축들을 점검하는 separating axes test를 개선할 수 있다 (box의 중심으로부터 sphere의 center까지의 축이 도움이 될 것이다. 그러나, 이 단계가 우리에게 early-out을 주기위해 설계되었다는 것을 기억해라. 우리는 processing time을 낭비하기를 원하지 않고, 그래서 우리는 이 단계에서 contact가 있는지를 결정하기 위해 많은 시간을 쓸 수 있는데, 다음 phase에서 full contact generation을 수행하지 않음으로써 절약하는 만큼이다. 다음 코드 블럭을 보아라.
// Early out check to see if we can exclude the contact if (real_abs(relCentre.x) - sphere.radius > box.halfSize.x || real_abs(relCentre.y) - sphere.radius > box.halfSize.y || real_abs(relCentre.z) - sphere.radius > box.halfSize.z) { return 0; }
Contact Generation
우리의 알고리즘의 마지막 단계는 박스에서 타겟 포인트로 가는 가장 가까운 점을 찾고, 그것으로부터 contact를 생성하는 것이다. 우리는 box의 coordinate에서 이것을 처음에 할 것이다.
이것은 간단한 프로세스이다. 우리가 할 필요가 있는 모든 것은 box의 half-size에 대한 test point의 각 component를 같은 방향으로 clamp하는 것이다. 이 새로운 점으로, 우리는 그러고나서 구의 중심점으로부터 target point까지의 거리를 처리할 수 있고, 만약 그것이 구의 반지름보다 더 크다면, 끝낼 수 있따. 이것에 대한 코드는 간단하다:
그 contact properties는 월드 좌표계에서 주어져야 할 필요가 있다. 그래서 우리가 contact normal을 하기전에, 우리는 world coordinates에서 가장 가까운 점을 찾을 필요가 있다. 이것은 간단히 우리가 이전에 생성한 점을 변환하는 것을 의미한다:
우리는 그러고나서 챕터의 이전처럼 contact properties를 계산할 수 있다. 그 최종 코드는 모두 합쳐서 이렇게 보인다:
13.3.5 Colliding Two Boxes
두 개의 박스들의 충돌은 우리가 이 챕터에서 상세하게 고려할 가장 복잡한 케이스이다. 비록 우리가 여전히 매우 기본 도형을 다루고 있지만, 박스들의 한 쌍을 다루는데 필요한 기법들은 충돌하는 도형들이 좀 더 복잡할 때 사용되는 것들이다. 이 섹션의 마지막에서, 우리는 box-box collision algorithm이 concave shapes의 어떤 상으로 어떻게 확장되어질 수 있는지를 볼 것이다.
두 박스들 사이에 contact의 가능한 6개의 타입들이 있다, 그림 13.14에서 보여지듯이.
우리는 face-face와 edge-face contacts를 피하려고 노력할 것이다. 왜냐하면 그것들은 안정적이지 않기 때문이다. 두 면 사이의 단일의 contact point는 그 평면이 회전하게 한다; contact normal이 두 centers of gravity를 통과하여 지나기 위해서 contact normal가 생성될 가능성은 높지 않다. 만약 우리가 3개 또는 4개의 contacts를 대신에 사용한다면, 그러면 최종 contact resolution은 시각적으로 좀 더 안정된 겨롹를 줄 것이다.
우리는 항상 face-face contact를 4개 까지의 point-face or edge-edge contacts로 대체할 수 있다. 그림 13.15에서 보여지듯이. 유사하게, 우리는 face-edge contacts를 두 개 까지의 point-face or edge-edge contacts로 대체할 수 있다.
그 나머지 두 개의 contacts들 즉, point-point와 point-edge는 다른것들로 대체되어질 수 없다. 우리는 이것들을 탐지하는 코드를 추가하지만, 그것들중 어떠한 것도 collision normal을 계산하는 명백한 방법을 가지지 않는다 (각각에 대해 유효한 collision normals의 무한한 개수가 있다). 우리는 충돌 normal을 얻기위해 몇 가지 추가 hacked code를 필요할 것이다.
내가 구성한 시스템에서, 나는 결코 두 가지 이유 때문에 이것을 하는데 시달리지 않는다. 첫 째로, 이러한 상황들은 고의로 되어지지않는다면, 실제로 일어날 가능성이 매우 낮다. 다른 박스와 완벽히 vertex to vertex로 충돌하는 한 박스의 가능성은 정말로 매우 작다: 그것은 매우 작은 target이니까 (point-edge는 좀 더 일어날 가능성이 높지만, 여전히 놀랄만하게 드물다). 둘 째로, 만약 우리가 이러한 contacts들을 무시한다면, 짧은 순간 뒤에, 그 박스들은 조금 관통할 것이다. 이 경우에, 다른 contacts들 중 하나 (일반적으로 point-face contact)가 생성될 것이고, 물리에 의해 일반적으로 처리된다. 그 결과는 물리적으로 믿을만하고, 그래서 추가 work가 간단히 필요하지 않다.
이러한 두 contact의 타입들을 무시하는 것은, 박스들이 신중하게 corner to corner or edge to corner로 균형 맞추어지는 시나리오들을 구성할 수 없다는 것을 의미한다. 그러나 그것은 너의 게임 디자인에서 높은 우선순위가 아닐 가능성이 높기 때문에, 너는 아마도 작업을 줄이고 그것과 함께 나아갈 수 있따.
박스들 사이의 contacts들을 생성하는 그 알고리즘은 sphere and box에 대한 것과 같은 포맷을 갖는데, 한 가지 추가적인 단계가 있다:
- 우리는 separating axes의 원리를 사용해서 early-out test를 수행한다. 이 경우에, contact generation은 충분히 복잡해서, 그 노력을 할 가치가 높다.
- 우리는 두 박스들 사이의 단일의 탐지된 contact를 얻기위해 full collision detection과 contact resolution을 수행한다.
- 우리는 contacts의 완전한 set를 형성하기 위해 새롭게 탐지된 contact를 두 박스들 사이의 이전에 탐지된 contacts와 합친다.
나는 탐지된 contacts를 저장하는 것 뒤에 로직으로 나중에 돌아갈 것이다. 처음에, 어떻게 두 박스들에 대해 separating axis test를 수행하는지를 보자.
Separating Axees
separating axis theorem은 그 오브젝트들이 사영될 수 있는 축에서 그것들이 접촉하고 있지 않은 어떤 축이 있다면 두 개의 오브젝트들이 충돌할 수 없다는 것을 말한다.
우리가 sphere-box case에 대해 보았듯이, 이 check는 그러므로 세 개의 부분들을 갖는다: 첫 째로, 우리는 축을 선택한다, 둘 째로, 우리는 그 오브젝트들을 축에 사영시킨다 (이것은 구의 경우에 사소하지만, 여기에서 좀 더 복잡해질 것이다), 그리고 셋 째로, 우리는 그 사영들이 겹치는지를 보기위해 체크해야 한다. 그림 13.16은 이것을 보여준다.
만약 그 사영이 그 축에서 겹친다면, 그것은 오브젝트가 닿고있다는 것을 의미하는 것은 아니다. 그러나 만약 그것들이 겹치고 있지 않다면, 그러면 우리는 확실히 그 오브젝트들이 닿고있지 않다는 것을 안다. 이것은 early-out으로 작용한다.
이 테스트는 그 box의 half-size를 이 방식으로 separating axis에 사영시켜, 박스에 대해 구현될 수 있다:
{
여기 코드가 잘 이해되지 않는다. Real-time Collision Detection 책을 공부하면서 이해할 필요가 있다. 여기에 있는 모든 Collision Detection은 이 책에 따라 구현되었다.
}
convex objects에 대해, 우리는 한 단계 더 갈 수 있다: 만약 그 오브젝트들이 닿고있지 않다면, 그러면 적어도 이것을 보여줄 한 축이 있어야 한다. 오목이 오브젝트들은 모든 separating axis test를 넘길 수 있고, 여전히 닿고있지 않을 수 있다. 일반적인 오브젝트에 대해, 이것은 특히 실용적인 지식은 아니다, 물론, 왜냐하면 우리는 모든, 가능한 축을 테스트하기를 희망하지 않기 때문이다. 그것은 early-out을 제공하는 이 테스트를 사용하는 것의 목적을 없앨 것이다.
두 박스들이 충돌할 때, 상황은 우리에게 더 쉽다. 우리가 테스트할 수 있는 15개의 축들이 있따. 그 15개중에 어떠한 것도 오브젝트들이 분리되어있는 것을 보여주지 않는다면, 그러면 우리는 그 오브젝트들이 닿고있다는 것을 안다.
이러한 축들은 각 box의 세 개의 주된 축들을 포함한다; 또한 각 box로부터 주된 축들의 각쌍에 수직인지를 검증할 또 다른 9개의 축들이 있다. 우리는 이러한 9개의 축들을, 주된 축들의 각 쌍에 외적을 취하여 생성한다 (외적의 방향은 그것의 벡터에 수직이기 때문에).
완전한 구현은 간단히 이러한 축들을 차례로 계산하고, 그것들을 검사를 위해 separateAlongAxis 함수로 보낸다. 전체 테스트는 그 첫 번째 그러한 함수가 실패를 호출하면 false를 반환한다.
{
Box 관련된 것들을 사실 잘 이해하지 못했다. 그래서 Real-time Collision Detection 책을 공부하고 다시 여기로 올까 생각했지만, 그러기엔 시간이 너무 오래 걸릴 거 같다. 그래서 나의 전략은 motivation-driven strategy로, RTCD를 읽고오면 시간이 너무 오래 걸리고, 눈에 보이는 것을 볼 수 없기에, 학습 동기가 떨어질 것이다. 그래서, 이해가 되지 않더라도, 번역을 하면서 내용을 따라가려고 하자. 그래서 코드가 이해가 정확히 안되겠지만 일단은 대충 어떤 역할을 하는지만 명확히하고 넘어가고, 완성된 거까지 열심히 달리자. 그리고나서, 완성된 것을 보면 학습동기가 더 살아날 것이기 때문에, 놓친부분을 RTCD를 공부하던지 아니면 이 책의 그 부분을 다시 보던지해서 다시 파헤쳐야 겠다.
상당히 어려운 개념들을 한 번에 이해하기란 어려운 것이다. 시간을 들여서 내것으로 만들 필요가 있다. 너가 쿼터니언 카메라를 구현하기 위해, 쿼터니언 관련 자료들을 여러 개 찾고 번역하고 읽어보고, 마침내 어느정도 익숙해져서 쿼터니언 카메라를 구현한 것까지의 시간을 생각해 보아라.
}
Coherence and Contact Generation
두 박스들 사이의 충돌을 계산하기 위해 (그리고 어떤 convex objects들의 쌍) 가장 효율적인 알고리즘들은 가장 깊은 관통점이 발견되었을 때 알고리즘을 종료시키는 shortcuts과 optimizations를 사용한다. 이것은 single contact이다.
contacts의 완전한 set를 생성하는 것은 더 어렵다. 한 개의 contact는 여러 가지 방식으로 해석되어질 수 있다. point-face contact는 다른 면에서의 또 다른 point-face contact로 해석되어질 수 있다, 다른 관통깊이와 함께. 그 상황은 edge-edge contacts보다 훨씬 더 복잡하다.
contact set을 얻기위해, 우리는 새로운 잠재적인 contacts들이 벌써 발견되었는지를 보고, 만약 그렇다면, 그것들을 해석하는 것의 새로운 방법이 더 나은지를 보기위해 체크하는 합리적으로 복잡한 전체 코드를 제공할 필요가 있다. 그리고 최악의 경우 시나리오에서, 한 contact를 재 해석하는 것은 set에 있는 모든 다른 contacts들이 재해석이 필요하다는 것을 의미할지도 모른다. 더 간단한 방법이 없다면, 이것은 노력할 가치가 있지만, 운 좋게도, 우리는 그 전체 문제를 피할 수 있다.
각 프레임에서, 우리는 single contact를 생성한다, 두 밗드르의 maximum penetration을 기반으로. 이것은 보토의 방법을 해결된다. 왜냐하면 우리는 오직 한 개의 contact만 resolved시키기 때문에, 그 박슫르은 그럴듯하게 다음 프레임에서 재해석할 것이지만 종종 다른 방식으로 될 것이다. 이러한 새로운 해석은 새로운 contact로 탐지되고, 그래서 이제 우리는 두 개의 contacts를 갖는다. 이것은 세 번째에 계속하고, 우리가 세 개의 contacts를 가졌을 때, 두 개의 박스들이 안정된 방식으로 쌓여있는 것을 유지하기에 충분하다. 그림 13.17은 2차원에서 두 개의 contacts들에 대해 작동중인 이것을 보여준다.
존재하는 contact가 다음 프레임에서 유용할 것이라는 가능성은 박스가 안정될 때 높지만, 그것들이 움직일 때는, 그 contact가 완전히 다음 프레임에서 틀릴지도 모른다.
박스가 움직일 때 (우리가, 각 프레임에서 single contact를 생성하게 될 것이라는 것을 의미하는), 그 contacts를 버려야만 하는 것을 피하기위해, 우리는 완전한 contact가 아니라, 닿고있는 특징만을 저장한다.
우리는 이 챕터 전반에 특징들(features)를 만나왔다: point, edge, and face. point-edge contact는 어떤 정점과 어떤 면 사이의 접촉이다. contacts 사이의 일관성을 이용하기 위해, 우리는 contact의 type을 저장한다 (우리의 경우에는 오직 point-edge와 edge-edge)그리고, 각 오브젝트에 대해 어떤 특징이 포함되었는지를 저장한다. 그림 13.17은 작동중인 이것을 보여준다. 우리는 point-face contact를 가지고 있고, 다음 프레임에서 같은 contact(즉, 같은 점과 면사이의 contact)를 가지고 있지만, 다른 contact properties를 가진다.
만약 deepest-penetration algorithm이 우리가 이미 가진 contact를 반환한다면, 그러면 우리는 그 contact에 대한 data를 업데이트 한다. 그렇지 않다면 그 새로운 contact는 우리가 그러한 두 개의 오브젝트들에 대해 캐싱한 contacts에 추가된다. 그래서 그 완전한 set은 collision resolver algorithm에 전해진다.
우리의 캐시에 있는 각 contact에 대해, 우리는 변하는 (즉, contact normal and interpenetration depth) 값들을 업데이트 시킬 필요가 있다. 만약 우리가 관통 깊이가 어떤 고정값보다 더 큰 것을 발견한다면, 그러면 그 contact는 어떤 거리만큼 떨어져 움직여야 하고, 따라서 그것을 더 고려하는 것은 말이 맞지 않다. 그래서 우리는 그 캐시로부터 만약 업데이트 될 때, 그것들이 너무 멀리 움직였다면 contacts을 제거한다.
멀리가 얼마나 멀리인가? 만약 우리가 엄격히 zero의 값을 사용한다면, 그러면 우리는 너무 많은 일을 할 것이다. 한 contact가 resolved될 때, 그것의 관통은 zero or less로 가 된다; 그리고 우리는 contact resolution이 우리가 그 캐시로부터 contacts를 제거하도록 하는 것을 원하지 않는다. 왜냐하면 우리는 one-contact-per-frame case로 돌아가야 하기 때문이다. 우리가 contact resolution을 볼 때 보게 되듯이, 한 오브젝트에서 전체 contacts의 set을 해결할 때 관통하지 않는 contacts를 고려하는 것은 도움이 될 수 있다.
그래서 우리는 작은 음수 값을 사용한다. 올바른 값을 얻는 것은 불행하게도, tweaking의 문제이다.
Contact Generation
그래서, 우리는 두 박스들 사이의 contacts의 한 세트를 생성하는 복잡한 일을 가장 깊은 관통점을 찾는 문제로 줄인다. 그러나, 게다가, 우리는 가장 깊은 관통점이 그 contact가 발생한 features를 반환할 수 있어먄 한다는 것을 안다.
다양한 알고리즘ㄷ르은 우리가 두 박스와 일반적인 convex objects들에 대해 이것을 하는 것을 돕는다. V-Clip은 가장 잘알려져있는 것중 하나이고, Lin-Canny의 detection phase와, GJK 또한 유용하다. V-Clip은 Ericsion [2005]에서 상세히 설명된다. 반면에 GJK는 좀 더 포과적으로 van den Bergen [2003]에서 설명된다. 그리고 이것은 충돌 탐지 라이브러리에서 그것들의 선호하는 기법의 각 저자의 사용을 반영한다.
모든 이러한 알고리즘들은 distance algorithms이다: 그것들은 두 다면체 사이의 최단 거리를 반환할 수 있다. 우리의 경우에, 반환된 거리가 0보다 더 작을 때 유용하다: 그 오브젝트들이 관통하고 있다는 것이다. 특히, Lin-Canny는 이 경우에 문제를 가지고 있다; 그것은 관통의 경우를 알아내기 위해 조금 조정될 필요가 있고, infinite loop를 피할 필요가 있다.
V-Clip과 GJK 둘 다 지능적으로 접촉할 수 있는 특징들의 가능한 조합을 찾는다. 그것들은 이것에 대해 충분히 지능적이여서, boxes에 대해 early-out으로서 separating axis text를 수행할 때의 속도 이점이 거의 없다.
일반적인 다면체에 대한 튼튼하고 효율적인 충돌 탐지 시스템을 만들기 위해서, 너는 결국 이러한 기법들 같은 것을 사용할 필요가 있을 것이다. 그러나, V-Clip과 그것의 변혀ㅇ들을 포함하는 다양한 효율적인 충돌 탐지 알고리즘은 특허에 의해 보호받고 있다는 것에 주의해라. 만약 너가 너의 코드에 이러한 알고리즘들을 구현한다면, 너는 라이센스 동의를 얻거나 또는 라이센싱 요금을 낼 필요가 있을지도 모른다.
완전한 충돌 탐지 시스템을 쓰는 것없이 물리를 실험하도록 허용하기 위해서, 우리는 모든 가능한 관통을 체크하는 단순한 알고리즘을 구성할 수 있다. 이것은 6개의 면, 8개의 정점, 그리고 12개의 변을 갖는 한 박스에 대해 작동할 수 있지만, 복잡한 어떤 것에 대해서 production-ready라고 고려되어서는 안된다.
우리의 단순한 contact generator는 간단히 우리가 관심이 있는 contact types 둘다를 체크한다 : point-face contacts and edge-edge contacts. 만약 그것이 하나의 그러한 contact 이상을 발견한다면, 그러면 가장 큰 관통을 가진 contact가 반환된다. 우리가 많은 contacts를 반환하지 않는다는 것을 기어갷라, 왜냐하면 그러한 contacts들의 self-consistent set을 얻는 것은 어려울 수 있기 때문이다.
철저히 contacts를 체크하기 위해, 우리는 두 가지 종류의 점검을 수행한다: 다른 오브젝트에 대해 각 오브젝트에서 각 정점의 point-face check와, 다른 것에 대해 한 오브젝트에서 각 변의 edge-edge check.
Point-Face contact
Point-face contacts는 탐지하기에 쉽다: 그것들은 sphere와 같은 로직을 사용한다 - box collisions 이지만, 0의 반지름을 갖는 구와. 우리는 간단히 한 박스의 각 정점을 다른 것의 주된 축들에 사영시킨다. 만약 그 정점이 박스안에 있다면, 그러면 한 point-face collision이 요구된다. 만약 그 정점이 한 개 이상의 축에서 그 박스에 있다면, 그러면 가장 얕은 관통을 가진 축이 사용된다. 그림 13.18은 이것을 보여준다.
그 알고리즘은 이 방식으로 작동한다:
여기 코드가 잘 이해되지 않는다. Real-time Collision Detection 책을 공부하면서 이해할 필요가 있다. 여기에 있는 모든 Collision Detection은 이 책에 따라 구현되었다.
}
convex objects에 대해, 우리는 한 단계 더 갈 수 있다: 만약 그 오브젝트들이 닿고있지 않다면, 그러면 적어도 이것을 보여줄 한 축이 있어야 한다. 오목이 오브젝트들은 모든 separating axis test를 넘길 수 있고, 여전히 닿고있지 않을 수 있다. 일반적인 오브젝트에 대해, 이것은 특히 실용적인 지식은 아니다, 물론, 왜냐하면 우리는 모든, 가능한 축을 테스트하기를 희망하지 않기 때문이다. 그것은 early-out을 제공하는 이 테스트를 사용하는 것의 목적을 없앨 것이다.
두 박스들이 충돌할 때, 상황은 우리에게 더 쉽다. 우리가 테스트할 수 있는 15개의 축들이 있따. 그 15개중에 어떠한 것도 오브젝트들이 분리되어있는 것을 보여주지 않는다면, 그러면 우리는 그 오브젝트들이 닿고있다는 것을 안다.
이러한 축들은 각 box의 세 개의 주된 축들을 포함한다; 또한 각 box로부터 주된 축들의 각쌍에 수직인지를 검증할 또 다른 9개의 축들이 있다. 우리는 이러한 9개의 축들을, 주된 축들의 각 쌍에 외적을 취하여 생성한다 (외적의 방향은 그것의 벡터에 수직이기 때문에).
완전한 구현은 간단히 이러한 축들을 차례로 계산하고, 그것들을 검사를 위해 separateAlongAxis 함수로 보낸다. 전체 테스트는 그 첫 번째 그러한 함수가 실패를 호출하면 false를 반환한다.
{
Box 관련된 것들을 사실 잘 이해하지 못했다. 그래서 Real-time Collision Detection 책을 공부하고 다시 여기로 올까 생각했지만, 그러기엔 시간이 너무 오래 걸릴 거 같다. 그래서 나의 전략은 motivation-driven strategy로, RTCD를 읽고오면 시간이 너무 오래 걸리고, 눈에 보이는 것을 볼 수 없기에, 학습 동기가 떨어질 것이다. 그래서, 이해가 되지 않더라도, 번역을 하면서 내용을 따라가려고 하자. 그래서 코드가 이해가 정확히 안되겠지만 일단은 대충 어떤 역할을 하는지만 명확히하고 넘어가고, 완성된 거까지 열심히 달리자. 그리고나서, 완성된 것을 보면 학습동기가 더 살아날 것이기 때문에, 놓친부분을 RTCD를 공부하던지 아니면 이 책의 그 부분을 다시 보던지해서 다시 파헤쳐야 겠다.
상당히 어려운 개념들을 한 번에 이해하기란 어려운 것이다. 시간을 들여서 내것으로 만들 필요가 있다. 너가 쿼터니언 카메라를 구현하기 위해, 쿼터니언 관련 자료들을 여러 개 찾고 번역하고 읽어보고, 마침내 어느정도 익숙해져서 쿼터니언 카메라를 구현한 것까지의 시간을 생각해 보아라.
}
Coherence and Contact Generation
두 박스들 사이의 충돌을 계산하기 위해 (그리고 어떤 convex objects들의 쌍) 가장 효율적인 알고리즘들은 가장 깊은 관통점이 발견되었을 때 알고리즘을 종료시키는 shortcuts과 optimizations를 사용한다. 이것은 single contact이다.
contacts의 완전한 set를 생성하는 것은 더 어렵다. 한 개의 contact는 여러 가지 방식으로 해석되어질 수 있다. point-face contact는 다른 면에서의 또 다른 point-face contact로 해석되어질 수 있다, 다른 관통깊이와 함께. 그 상황은 edge-edge contacts보다 훨씬 더 복잡하다.
contact set을 얻기위해, 우리는 새로운 잠재적인 contacts들이 벌써 발견되었는지를 보고, 만약 그렇다면, 그것들을 해석하는 것의 새로운 방법이 더 나은지를 보기위해 체크하는 합리적으로 복잡한 전체 코드를 제공할 필요가 있다. 그리고 최악의 경우 시나리오에서, 한 contact를 재 해석하는 것은 set에 있는 모든 다른 contacts들이 재해석이 필요하다는 것을 의미할지도 모른다. 더 간단한 방법이 없다면, 이것은 노력할 가치가 있지만, 운 좋게도, 우리는 그 전체 문제를 피할 수 있다.
각 프레임에서, 우리는 single contact를 생성한다, 두 밗드르의 maximum penetration을 기반으로. 이것은 보토의 방법을 해결된다. 왜냐하면 우리는 오직 한 개의 contact만 resolved시키기 때문에, 그 박슫르은 그럴듯하게 다음 프레임에서 재해석할 것이지만 종종 다른 방식으로 될 것이다. 이러한 새로운 해석은 새로운 contact로 탐지되고, 그래서 이제 우리는 두 개의 contacts를 갖는다. 이것은 세 번째에 계속하고, 우리가 세 개의 contacts를 가졌을 때, 두 개의 박스들이 안정된 방식으로 쌓여있는 것을 유지하기에 충분하다. 그림 13.17은 2차원에서 두 개의 contacts들에 대해 작동중인 이것을 보여준다.
존재하는 contact가 다음 프레임에서 유용할 것이라는 가능성은 박스가 안정될 때 높지만, 그것들이 움직일 때는, 그 contact가 완전히 다음 프레임에서 틀릴지도 모른다.
박스가 움직일 때 (우리가, 각 프레임에서 single contact를 생성하게 될 것이라는 것을 의미하는), 그 contacts를 버려야만 하는 것을 피하기위해, 우리는 완전한 contact가 아니라, 닿고있는 특징만을 저장한다.
우리는 이 챕터 전반에 특징들(features)를 만나왔다: point, edge, and face. point-edge contact는 어떤 정점과 어떤 면 사이의 접촉이다. contacts 사이의 일관성을 이용하기 위해, 우리는 contact의 type을 저장한다 (우리의 경우에는 오직 point-edge와 edge-edge)그리고, 각 오브젝트에 대해 어떤 특징이 포함되었는지를 저장한다. 그림 13.17은 작동중인 이것을 보여준다. 우리는 point-face contact를 가지고 있고, 다음 프레임에서 같은 contact(즉, 같은 점과 면사이의 contact)를 가지고 있지만, 다른 contact properties를 가진다.
만약 deepest-penetration algorithm이 우리가 이미 가진 contact를 반환한다면, 그러면 우리는 그 contact에 대한 data를 업데이트 한다. 그렇지 않다면 그 새로운 contact는 우리가 그러한 두 개의 오브젝트들에 대해 캐싱한 contacts에 추가된다. 그래서 그 완전한 set은 collision resolver algorithm에 전해진다.
우리의 캐시에 있는 각 contact에 대해, 우리는 변하는 (즉, contact normal and interpenetration depth) 값들을 업데이트 시킬 필요가 있다. 만약 우리가 관통 깊이가 어떤 고정값보다 더 큰 것을 발견한다면, 그러면 그 contact는 어떤 거리만큼 떨어져 움직여야 하고, 따라서 그것을 더 고려하는 것은 말이 맞지 않다. 그래서 우리는 그 캐시로부터 만약 업데이트 될 때, 그것들이 너무 멀리 움직였다면 contacts을 제거한다.
멀리가 얼마나 멀리인가? 만약 우리가 엄격히 zero의 값을 사용한다면, 그러면 우리는 너무 많은 일을 할 것이다. 한 contact가 resolved될 때, 그것의 관통은 zero or less로 가 된다; 그리고 우리는 contact resolution이 우리가 그 캐시로부터 contacts를 제거하도록 하는 것을 원하지 않는다. 왜냐하면 우리는 one-contact-per-frame case로 돌아가야 하기 때문이다. 우리가 contact resolution을 볼 때 보게 되듯이, 한 오브젝트에서 전체 contacts의 set을 해결할 때 관통하지 않는 contacts를 고려하는 것은 도움이 될 수 있다.
그래서 우리는 작은 음수 값을 사용한다. 올바른 값을 얻는 것은 불행하게도, tweaking의 문제이다.
Contact Generation
그래서, 우리는 두 박스들 사이의 contacts의 한 세트를 생성하는 복잡한 일을 가장 깊은 관통점을 찾는 문제로 줄인다. 그러나, 게다가, 우리는 가장 깊은 관통점이 그 contact가 발생한 features를 반환할 수 있어먄 한다는 것을 안다.
다양한 알고리즘ㄷ르은 우리가 두 박스와 일반적인 convex objects들에 대해 이것을 하는 것을 돕는다. V-Clip은 가장 잘알려져있는 것중 하나이고, Lin-Canny의 detection phase와, GJK 또한 유용하다. V-Clip은 Ericsion [2005]에서 상세히 설명된다. 반면에 GJK는 좀 더 포과적으로 van den Bergen [2003]에서 설명된다. 그리고 이것은 충돌 탐지 라이브러리에서 그것들의 선호하는 기법의 각 저자의 사용을 반영한다.
모든 이러한 알고리즘들은 distance algorithms이다: 그것들은 두 다면체 사이의 최단 거리를 반환할 수 있다. 우리의 경우에, 반환된 거리가 0보다 더 작을 때 유용하다: 그 오브젝트들이 관통하고 있다는 것이다. 특히, Lin-Canny는 이 경우에 문제를 가지고 있다; 그것은 관통의 경우를 알아내기 위해 조금 조정될 필요가 있고, infinite loop를 피할 필요가 있다.
V-Clip과 GJK 둘 다 지능적으로 접촉할 수 있는 특징들의 가능한 조합을 찾는다. 그것들은 이것에 대해 충분히 지능적이여서, boxes에 대해 early-out으로서 separating axis text를 수행할 때의 속도 이점이 거의 없다.
일반적인 다면체에 대한 튼튼하고 효율적인 충돌 탐지 시스템을 만들기 위해서, 너는 결국 이러한 기법들 같은 것을 사용할 필요가 있을 것이다. 그러나, V-Clip과 그것의 변혀ㅇ들을 포함하는 다양한 효율적인 충돌 탐지 알고리즘은 특허에 의해 보호받고 있다는 것에 주의해라. 만약 너가 너의 코드에 이러한 알고리즘들을 구현한다면, 너는 라이센스 동의를 얻거나 또는 라이센싱 요금을 낼 필요가 있을지도 모른다.
완전한 충돌 탐지 시스템을 쓰는 것없이 물리를 실험하도록 허용하기 위해서, 우리는 모든 가능한 관통을 체크하는 단순한 알고리즘을 구성할 수 있다. 이것은 6개의 면, 8개의 정점, 그리고 12개의 변을 갖는 한 박스에 대해 작동할 수 있지만, 복잡한 어떤 것에 대해서 production-ready라고 고려되어서는 안된다.
우리의 단순한 contact generator는 간단히 우리가 관심이 있는 contact types 둘다를 체크한다 : point-face contacts and edge-edge contacts. 만약 그것이 하나의 그러한 contact 이상을 발견한다면, 그러면 가장 큰 관통을 가진 contact가 반환된다. 우리가 많은 contacts를 반환하지 않는다는 것을 기어갷라, 왜냐하면 그러한 contacts들의 self-consistent set을 얻는 것은 어려울 수 있기 때문이다.
철저히 contacts를 체크하기 위해, 우리는 두 가지 종류의 점검을 수행한다: 다른 오브젝트에 대해 각 오브젝트에서 각 정점의 point-face check와, 다른 것에 대해 한 오브젝트에서 각 변의 edge-edge check.
Point-Face contact
Point-face contacts는 탐지하기에 쉽다: 그것들은 sphere와 같은 로직을 사용한다 - box collisions 이지만, 0의 반지름을 갖는 구와. 우리는 간단히 한 박스의 각 정점을 다른 것의 주된 축들에 사영시킨다. 만약 그 정점이 박스안에 있다면, 그러면 한 point-face collision이 요구된다. 만약 그 정점이 한 개 이상의 축에서 그 박스에 있다면, 그러면 가장 얕은 관통을 가진 축이 사용된다. 그림 13.18은 이것을 보여준다.
그 알고리즘은 이 방식으로 작동한다:
- object A의 각 정점을 고려해라.
- object B와 그 정점의 관통을 계산해라.
- 그러한 가장 기픈 관통은 보유된다.
- object B의 정점들을 object A에 대해 같은 것을 해라.
- 가장 깊은 관통이 결국에 보유된다.
point-face detection code는 그러므로 이것처럼 보인다:
우리가 sphere-box test에서 했던 것과 정확히 같이 point-face collision을 위해 contact data를 생성한다는 것을 유의해라.
Edge-Edge Contact Generation
edge-edge contacts를 결정하는 것은 훨씬 더 복잡하지는 않다. 우리는 다시, 한 오브젝트로부터 차례로 각 edge를 취하고, 다른 오브젝트에 대해 검사한다. 이 경우에, 우리는 다른 오브젝트에 있는 변에 대해 그것을 검사한다.
우리는 쉽게 두 변 사이의 거리를 계싼할 수 있지만, 그 거리 혼자서는 우리에게 그 변들이 거리에 의해 분리되어 있는지 또는 관통하고 있는지를 말해줄 수 없다. 우리는 추가적인 검사를 더할 필요가 있따. 그 거리 계싼은ㅇ 또한 우리에게 다른 변에 가장 가까운 변에 있는 점을 제공한다. 만약 그 변들이 서로 관통한다면, 그러면 object A에 있는 이 점은 object B의 중심에 object B의 간선에 있는 점 보다 더 가까울 것이고, 역으로도 성립한다. 그림 13.19는 이것을 보여준다. 우리는 거리의 부호를 결정하기 위해 이 체크를 사용하고, 그것이 관통하는지 아닌지를 처리하기 위해서도 이다.
point-face contacts에 대해 우리가 그림 13.18에서 보았떤 것처럼, edge-edge contact는 여러 변들에 대해서 탐지될 것이다. 우리는 오직 가장 얕은 edge-edge contact를 사용할 필요가 있따. 그 알고리즘은 이 방식으로 작동한다:
- object A의 각 변 E를 고려해라.
- object B의 각 변과 그것의 관통을 처리해라.
- 그러한 관통중에서 가장 얕은 것이 E의 관통이다.
- 그러한 가장 깊은 관통을 가진 object A로부터의 간선은 봉ㅇ유된다.
우리는 object B의 관점에서부터 그 과정을 반복할 필요가 없다. 왜냐하면 우리는 간선마다 점검하기 때문이다; 우리는 모든 간선 조합을 이미 체크했을 것이다.
The Final Contact
이제 우리는 point-face calculations로부터 한 winner를 가지고, edge-edge calculations로부터 한 winnder를 가진다. 반환된 contact는 이러한 두 개의 옵션들 중에 더 깊은 것이 될 것이다. 이것은 그러고나서 연속적인 프레임에 대해 contacts의 완전한 set을 생성하기위해 이전에 설명된 caching algorithm에 들어갈 수 있다.
13.3.6 Efficiency and General Polyhedra
명백히, 이전에 설명된 단순한 contact generation algorithm은 상당히 V-Clip, GJK, 또는 포괄적인 충돌 탐지 라이브러리에 사용되는 소랴으이 다른 변형들보다 덜 효율적이다.
너는 CD에서 이 알고리즘을 발견할 것이다, 너가 간단히 복사해서 붙여넣기 할 수 있는 좀 더 효율적인 일반 목적의 contact generation routine가 있는.
그 naive algorithm과 그것의 좀 더 효율적인 사촌들은 box들 사이의 contact generation에 제한되어있지 않다. 그것들은 평평한 표면으로 구성된 어떤 볼록 3D 오브젝트 사이의 contacts를 생성할 수 있는 일반 목적의 알고리즘이다. 이것은 대부분의 게임 에셋들이 폴리곤으로 이루어졌기 때문에 편리하다 (비록 native curved surfaces가 점점 더 흔해지고 있을지라도).
면의 개수가 증가함에 따라, 그러나, 그 알고리즘은 점점 더 크게 느려진다. 그 naive algorithm은 이것을 특히 극심하게 보여준다; 단순한 박스 이상의 것에 대해, 그것은 매우 나쁘게 수행한다. 그러나 V-Clip과 GJK 또한 같은 문제를 겪는다.
이 이유 때문에, 포괄적인 coarse collision detection layer와 함께 매우 효율적인 충돌 탐지 알고리즘을 수행할 때, 너가 렌더링을 위해 하듯이 collision detection을 위해 같은 도형의 집합을 사용하는 것은 충고되지 않는다. 심지어 복잡한 3D assets들은 일반적으로 pimitives의 조립체 또는 간단한 볼록 다면체의 조합 둘 주 ㅇ하나로서 collision detector에게 나타내어질 수 있다. 우리가 구성한 caching system과 결합된 일반적인 polyhedra contact generator는 그런다음에 현실적인 시간의 양으로 현실적인 물리학을 이끄는 contacts의 한 집합을 생성할 수 있다.
13.4 Summary
이러한 충돌 탐지 경우들은 오직 full game engine에서 가능한 것의 표면에서부터 긁어모은다. 충돌 탐지, 그리고 특히 contact generation은 그것 만으로도 큰 분야이고, 물리엔진이 그것에 의존할지라도, 소프트웨어 공학과는 꽤 분리된 영역이다.
너는 지난 두 챕터에서 구성한 충돌 탐지 시스템을 사용할 수 있고, 너가 필요한 부가적인 테스트와 함께 그것을 확장할 수 있다 (이 시리즈의 다른 책들은 많은 충돌 탐지 테스트들을 포함한다). 또는 너는 thire party collision detection system을 가져올 수 있다.
좋은 이용가능한 오픈소스 충돌 탐지와 contact generation algorithms들이 있다. (SOLID와 RAPID같은). 너는 이러한 것들을 너가 이 책에서 개발한 것과 함께 사용할 수 있고, 또는 그것들을 알고리즘을 너만의 코드를 만드는 것에 대해 영감으로서 취할 수 있다.
경고: 많은 경우들이 있고, 가능한 많은 최적하가 있어서, 포괄적인 충돌 탐지 시스템을 작성하는 더 큰 작업이 될 것이다, contacts를 처리하는 너의 물리엔진을 만드는 것보다.
충돌 탐지 시스템을 정확히 작동하게 하여, 우리의 물리엔진에 돌아갈 시간이고, 우리가 발견할 충돌을 처리할 시간이다. Chapter 14는 계속해서 impact collisions의 문제를 다루고, 완전히 회전하는 rigid bodies에 대해 충돌을 지원하기 위해 코드를 어떻게 구성할지를 보여준다.
=====================================================
상당히 어렵고, 저자도 가면 갈수록 설명의 디테일을 줄여간다...
일단, 계속진행하고, 나중에 GJK로 충돌탐지를 다 대체해서 편하게 가야겠다.
댓글 없음:
댓글 쓰기