효율적인 충돌 탐지 시스템을 설계하는 것은 퍼즐을 합치는 것과 같다. 많은 조각들이 큰 그림이 나타나기 시작하기 전에 연결되어야 한다. 유사한 방식으로, 이 책의 대다수는 충돌 탐지에 대해 다른 접근법에 들어가기 전에 개별 조각을 조사하는 것과 관련이 있다. 그 큰 그림은 책의 과정 동안 명확해 질 것이다. 이 챕터는 접근법들 사이에서 선택할 때 고려되어야 할 많은 문제들에 대한 빠른 overview를 제공하고, 이러한 접근법들의 컴포넌트들이 어떻게 연관지어야 하는지를 제공한다. 이 챕터는 또한 다음 챕터들에서 정의되고 설명될 많은 용어들을 소개한다. 여기에서 다뤄지는 항목들의 좀 더 깊은 내용들은 책의 나머지 챕터들을 통해 제공된다.
2.1 Collision Algorithm Design Factors
충돌 탐지 시스템을 설계할 때 결정되는 선택들에 영향을 미치는 몇 가지 요소들이 있다. 이러한 요소들은 다음의 분류로 분해될 것이다:
- Application domain representation. scene과 그것의 오브젝트를 위해 사용되는 geometrical representations은 사용되는 알고리즘에 직접적인 영향력을 가진다. 이러한 표기에 대해 더 적은 제한이 더해지면, 좀 더 일반적인 충돌 탐지 솔루션들이 사용되어져야만하고, 가능한 성능 반동이 있게 된다.
- Different types of queries. 일반적으로, query types과 결과가 좀 더 세부적일수록, 그것들을 얻는데 연산 노력이 더 많이 요구된다. 부가적인 자료구조가 어떤 queries를 지원하기 위해 요구되어질지도 모른다. 모든 오브젝트 표기가 모든 query types를 지원하는 것은 아니다.
- Environment simulation parameters. 시뮬레이션 그 자체는 충돌 탐지 시스템에 직접적인 영향을 갖는 몇 가지 파라미터들을 포함한다. 이러한 것은 얼마나 많은 오브젝트들이 있는지, 그것들의 상대적인 크기와 위치가 무엇인지, 그것들이 움직였는지, 어떻게 움직였는지, 그것들이 관통호도록 허용되는지, 그것들이 rigid or flexible한지를 포함한다.
- Performance. 실시간 충돌 탐지 시스템은 엄격한 시간과 사이즈 제한 내에서 작동한다. 시간과 공간이 항상 trade-off여서, 몇 가지 특징들은 보통 명시된 퍼포먼스 요구사항을 충족시키기 위해 균형이 맞춰진다.
- Robustness. 모든 프로그램들이 물리 시뮬레이션의 같은 수준을 요구하는 것은 아니다. 예를들어, 서로의 위에 벽돌을 쌓는 것은 농구 코트에서 튀는 하나의 농구공을 갖는 것보다 충돌 탐지 시스템에서 좀 더 많은 정교함을 요구한다. 조금 너무 이르게 튀는 공이나 어느정도 더 큰 각으로 튀는 공은 눈치채어지지 않을 것이지만, 쌓여진 벽돌들의 접촉점을 연산하는데 있어서 아주 작은 오류들은 서로가 관통하거나 미끄러지도록 하는 결과를 만들어낼 가능성이 높다.
- Ease of implementation and use. 대부분의 프로젝트들은 시간 프레임 위에 있다. 충톨 탐지시스템의 특징을 관리하는 것은 그 시스템이 시간 내에 완료되어서 사용될 수 있는지만을 의미한다. 그러므로 구현의 간결함과 관련된 결정들은 접근법이 취해질 때 큰 역할을 한다.
이러한 문제들은 챕터의 나머지에서 더 세부적으로 다뤄진다.
2.2 Application Domain Representation
적절한 충돌 탐지 알고리즘들을 선택하기 위해, scene과 그것의 오브젝트들을 위해 사용될 geometrical 표기의 유형을 고려하는 것이 중요하다. 이 섹션은 다양한 오브젝트 표기, simplified geometry가 geometry를 모델링하는 것 대신에 어떻게 사용되는지, 그리고 application-specific 지식이 specialized solutions들이 좀 더 generic solutions들에 대해 사용되어지도록 하는지에 대해 간단히 말한다.
2.2.1 Object Representations
가장 현재의 하드웨어는 삼각형들을 기본적인 rendering primitive로 사용한다. 결과적으로, polygonal representation은 scenes과 scene objects에 대한 자연스러운 선택이고, 뿐만 아니라 그것에 대응되는 collision geometry에 대해서도 그렇다. 가장 generic polygonal representation은 polygon soup이다: 한 폴리곤이 다른 것과 어떻게 연결되어지는 지를 명시하는 connectivity information이 없는 폴리곤들의 순서가 없는 집합을 말한다. 내재된 constraints가 없이, 그 polygon soup는 artists와 level designers에게 매력적인 representation이다. polygon soups에 작용되는 알고리즘들은 어느 폴리곤 집합에도 적용되지만, 부가적인 정보를 의존하는 것들보다 덜 효율적이고 덜 튼튼한 경향이 있다. 예를들어, polygon soup은 한 오브젝트의 "내부"에 대한 어떠하나 정보도 포함하지 않는다. 그래서, 한 오브젝트가 어느정도 잘못되게 다른 오브젝트 안에 있는지를 알아내는 쉬운 방법이 없다. 언급된 그 부가적인 정보는 어떤 edges가 어떤 정점에 연결되었는지와 어떤 faces가어떤 주어진face와 연결되었는지, 그오브젝트가 closed solid를 형성하는지, 그 object가 convex 또는concave인지에 대한 것을 포함할 수 있다.
폴리곤들은 polygon mesh라고 불려지는 polygonal surface를 형성하기 위해 그것들의 간선에서 서로에게 연결되어질지도 모른다. polygon meshes의 한 구성으로부터 오브젝트를 구성하는 것은 geometrical models를 관리하는 가장 흔한 방법들중 하나이다 (그림2.1).
Polygonal objects들은 그것들의 vertices, edges, 그리고 faces의 관점에서 정의된다. 이 방식으로 구성될 때, 오브젝트들은 explicit representation을 갖는다고 말해진다. Implicit objects들은 spheres, cones, cylinders, ellipsoids(타원체), tori(도넛모양), 그리고 그러한 방식으로 explicitly하게 정의되지 않지만 수학적 표현으로 implicitly하게 정의되는 다른 기하학적 primitives을 말한다. Implicit objects들은 종종 3D 공간에서 실수로 매핑하는 함수로서 묘사된다, f : R^3 -> R, 거기에서 f(x,y,z) < 0에 의해 주어지는 점은 내부를 구성하고. f(x,y,z) = 0은 경계를, 그리고 f(x,y,z) > 0은 그 오브젝트의 외관을 구성한다 (그림 2.2). implicit function에 의해 정의되는 object boundary는 implicit surface라고 불려진다. Implicit objects들은 빠른 rejection culling을 위해 scene objects의 rough approximations으로서 사용될 수 있다. 그 implicit form은 빠른 intersection tests를 허용한다, 특히 lines and rays와 함께 - ray tracing applications에서 활용되는 사실이다. implicit tests들의 몇 가지 예들은 Chapter 5에서 제공된다.
Convex polygonal objects들은 또한 많은 halfspaces들의 교차로서 묘사될 수 있다. 예를들어, 한 정육면체는 6개의 half-spaces의 교차로서 표현될 수 있다, 그것은 정육면체의 한 면 밖에 놓여있는 공간의 부분을 깍는 각 half space이다. halfspaces들과 halfspace intersection volumes은 좀 더 상세하게 Chapter 3에서 설명된다.
구, 박스, 실린더 같은 Geometricprimitives들은 또한 constructive solid geometry (CSG) framework를 통해 구성되는 오브젝트의 구성하는 블럭들이다. CSG 오브젝트들은 재귀적으로 집합-이론 연산을 (union, intersection, or difference) 기본 geometric shpaes 또는 다른 CSG 오브젝트들에 적용하여 형성되어진다 그리고 이것은 임의의 복잡한 오브젝트들이 구성되는 것을 허용한다. 따라서, 헌 CSG 오브젝트는 (이진) 트리로 나타내어지고, 내부 노드에서 집합-이론 연산이 있고, leaves에는 geometry primitives들이 있다. CSG 오브젝트들은 vertices, edges, and faces가 직접적으로 이용가능하지 않다는 점에서 implicit하다.
CSG 모델링의 강점은 그 결과 오브젝트들이 매우 유효하다는 것이다 - polygonal representations를 오염시키는 cracks과 다른 문제가 없다. CSG는 또한 volume representation인데, 그것은 예를들어, query 지점이 CSG 오브젝트 내부에 있는지를 결정하는 것을 쉽게 만든다. polyhedral objects에 있는 CSG는 예를들어 [Laidlaw86]과 {Thibault87]에 묘사되는 프로세스를 통해 구현되어질 수 있다. 그러나, 관련된 계산에서의 numerical imprecision 때문에 튼튼한 구현을 얻는 것은 어려울 수 있다.
2.2.2 Collision Versus Rendering Geometry
rendering geometry를 직접적으로 충돌 시스템에 넘기는 것이 가능할지라도, 충돌 탐지가 수행되는 별개의 geometry를 갖는 것이 더 좋은 몇 가지 이유들이 있다.
- 그래픽스 플랫폼은 rendering geometry가 너무 복잡해져서 충돌 탐지 또는 물리를 수행하도록 사용될 수 없는 지점까지 발전했다. 게다가, 충돌이 얼마나 정확하는지에 대한 한계가 있다. 따라서, 렌더링을 위해 사용되는 같은 기하를 사용하기 보다, simplified proxy geometry가 충돌 탐지를 위한 자리에서 대체되어질 수 있다. 예를들어, 게임에 대해, 오브젝트 복잡성과 상관없이, 게임 오브젝트를 나타내기 위해, 구와 박스같은 간단한 기하 도형들을에 의존하는 것이 흔하다. 만약 그 proxy object가 충돌한다면, 실제 오브젝트들이 또한 충돌한다고 가정된다. 이러한 간단한 기하 도형들, 또는 bouding volumes들은 무슨 geometry representation이 사용되는 거와 상관없이, collision queries를 가속하기 위해 빈번히 사용된다. Bounding volumes은 일반적으로 그 geometry를 완전히 캡슐화한다. Bounding volumes은 Chpater 4에서 상세히 이야기 된다.
- 현대 하드웨어에 대해, geometry는 매우 특정한 포맷들로 주어지는 경향이 있다 (triangle strips and indexed vertex buffers), 그리고 이것은 충돌 탐지가 아닌, 빠른 렌더링을 위해 그들 자신을 내어준다. 이러한 구조들을 decode하기보다 (비록 decoded data가 재사용하기 위해 캐싱되어질 수 있을지라도), 특별한 collision geometry를 제공하는 것이 보팅 더 효율적이다. 게다가, 그래픽스 하드웨어는 종종 triangle-only formats을 시행한다. collision geometry를 위해, 효율성은 가끔씩 다른, 삼각형이 아닌, 기하들을 지원하여 얻어질 수 있다.
- rendering geometry와 collision geometry의 요구되는 데이터와 데이터 구성은 급격히 다양할 가능성이 높다. static rendering data가 material로 분류되어질지도 모르는 반면에, collision data는 일반적으로 공간으로 구성된다. 렌더링 기하는 material information, vertex colors, 그리고 텍스쳐 좌표같은 embedded data를 요구하고, 반면에 충돌 기하는 관련된 surface properties가 필요하다. 그 두개를 나누고 모든 충돌 관련 정보를 함께 유지하는 것은 충돌 데이터를 더 적게 만든다. 차례로, 더 작은 데이터는 더 좋은 데이터 cache coherency에 의해 효율성 개선으로 이끈다.
- 가끔식, 충돌 기하는 디자인에 의해 랜더링된 기하와 다르다. 예를들어, 스노우보드 게임에서 무릎 깊이의 powder snow는 그 스노우 표면의 렌더링된 representation 보다 two feet 아래로 collision surface에 의해 모델링되어질 수 있다. 발목 깊이의 흔들리는 잔디에서 걷거나 허리 높이의 murky water에서 나아가는 것은 유사하게 다뤄질 수 있다. 비록 렌더링 기하가 충돌기하로 사용될지라도, 충돌기하 데이터 셋으로부터 렌더링 기하를 제외하는 것에 대한 조항들이 있어야 한다. (그리고 부가적인 렌더링이 아닌 기하를 포함하는 것에 대해서도)
- 시뮬레이션 목적을 위해서, 충돌 데이터는 심지어 렌더링 데이터가 보이지 않는 곳에 던져질 때에도 유지되어야만 한다. 충돌 기하가 대응되는 렌더링 기하보다 더 작아진 것과 함께, 영구적인 memory footprint는 그러므로 줄어든다.
- original geometry는 polygon soup 또는 mesh로서 주어질지도 모른다. 반면에 시뮬레이션은 solid-object representation을 요구한다. 이 경우에, 어느정도 original geometrical representation을 solidify하려고 하는 것보다, solid proxy geometry를 연산하는 것이 더 쉽다.
그러나, 별개의 충돌 기하를 쓰는 것에 대한 잠재적인 단점이 있다.
- 데이터 복사 (주로 정점에 대해)는 부가적인 메모리가 사용되도록 한다. 이 문제는 캐싱을 선형화를 통해 (섹션 13.5에서 설명되는) 렌더링 기하로부터 충돌 기하를 만들어서 완화될지도 모른다.
- 비슷한 기하의 두 집합을 만들어내고 유지하기 위해, 추가적이 작업이 요구될지도 모른다. 직접 proxy geometry를 구성하는 것은 그것을 만드는 디자이너의 스케쥴에 피해를 입힐 것이다. 만약 그것이 한 tool에 의해 만들어진다면, 그 툴은 충돌 시스템이 사용될 수 있기 전에 쓰여야 한다. 게다가, 만약 직접 그 툴 output을 수정할 필요가 있다면, 그 변화는 어느정도 그 툴과 원래 데이터셋으로 의사소통이 되어야만 한다.
- 만약 렌더링 기하와 충돌 기하가 별개로 만들어지고 구성된다면, 그것들은 장소에서 잘못 매치될지도 모른다. 충돌기하가 렌더링 기하로서 같은 volume을 채우지 않을 때, 오브젝트들은 부분적으로 사라지거나 다른 오브젝트의 표면 위로 떠 다닐지도 모른다.
- 버전화 그리고 다른 실행 계획 문제들이 두 기하에 대해 나타날 수 있다. 충돌 기하는 실제로 렌더링 기하가 바뀔 때 재구성되었는가? 만약 직접 만들어 졌따면, 어떤 게 먼저인가: 충돌 기하 또는 렌더링 기하? 그리고 너는 다른 것이 변할 때 어떻게 업데이트를 하는가?
게임에 대해서, 실제 비쥬얼과 가까운 (정확히 부합하지 않지만) proxy geometry를 사용하는 것은 꽤 잘 작동한다. 인지적으로, 인간은 정확한 충돌이 발생하고 있는지를 탐지하는 것을 잘 하지 않는다. 관련된 오브젝트가 더 많고, 그것들이 더 빨리 움직일 수록, 그 플레이어가 어떤 불일치를 알아차리는게 덜 가능할 것이다. 사람들은 또한 한 충돌의 결과가 무엇이 되어야 하는지를 예측하는 것을 못한다. 그리고 이것은 collision response와 관련해서 자유성이 취해질 수 있도록 한다. 게임에서, 충돌 탐지와 반응은 효과적으로 "만약 그것이 옳게 보인다면, 옳은 것이다"라는 것에 지배받는다. 다른 프로그램들은 더 엄격한 정확성 요구사항을 가진다.
2.2.3 Collision Algorithm Specialization
모든 수반되는 충돌 탐지 시스템을 갖기 보다는, 특정한 시나리오에 대한 특정화된 충돌 시스템을 제공하는 것이 종종 현명하다. 특수화가 관련된 한 예시는 파티클 충돌이다. 보통의 충돌 시스템을 통해 하나씩 파티클을 보내기 보다는, 그것들은 파티클의 그룹으로서 충돌을 위해 다뤄지고 보내닌다. 거기에서 그 그룹들이 형성되고 context를 기반으로 재 구성된다. 파티클들은 심지어 충돌로부터 제외되어질지도 모른다. 충돌의 부족이 눈치채어지지 않는 경우에.
또 다른 예시는 한 오브젝트와 다른 오브젝트 사이 그리고 오브젝트와 scene 사이의 충돌을 탐지해내는데 별개의 알고리즘들의 사용이다. Object-object 충돌은 심지어 한 플레이어 캐릭터와 빠르게 움직이는 발사체가 다른 오브젝트들로부터 다르게 다뤄지도록 더 특수화 될지도 모른다. 예를들어, 모든 오브젝트들이 항상 플레이어 캐릭터와 충돌하는 한 경우는 그 플레이어캐릭터를 일반적인 충돌 시스템에 넣는 것보다 하드 코딩된 테스트로서 더 잘 처리된다.
또한 large worlds의 시뮬레이션을 고려해라. 작은 월드에 대해서, 충돌 데이터는 메모리가 항상 유지될 수 있다. 크고 seamless(경계가 없는)한 world에 대해서, 그러나, 충돌 데이터는 world가 이동될 때 불러와지거나 안불러와져야 한다. 후자의 경우에, 오브젝트들을 world structure로부터 분리시키는 것이 또 다시 매력적인 선택이다. 그래서 그 오브젝트들은 world structure의 변화에 영향을 받지 않는다. 가령 objects와 world를 유지하기 위해 별개의 구조를 갖는 것의 가능한 단점은 이제 query하는 것이 한 개와 반대로 두 개의 자료구조를 탐색하는 것을 포함한다.
2.3 Types of Queries
가장 간단한 collision query는 interference detection 또는 intersection testing problem이다: 두 개의 (static) 오브젝트들 A와 B가 주어진 위치와 방향에서 중첩되는지에 대한 Boolean question에 답하는것이다. Boolean intersection queries는 빠르면서 구현하기에 쉽다. 그러므로 흔히 사용된다. 그러나, 가끔씩 Boolean result는 충분하지 않고, 교차하는 부분이 발견되어야 한다. intersection finding의 문제는 좀 더 어려운 것인데, 그것은 한 개 이상의 접촉점(points of contact)를 발견하는 것을 포함한다.
어떤 적용에 대해, 그 오브젝트들 사이에 있는 공통의 어떤 한점을 찾는 것이 충분할지도 모른다. 다른 것에서, rigid-body simulations 같은, 접촉하는 점들의 집합 (the set of contacting points, the contact manifold)이 결정되어야 할 필요가 있을지도 모른다. contact manifold를 Robustly하게 연산하는 것은 어려운 문제이다. 결국, Approximate Queries - 그 답들이 주어진 tolerance까지만 정화하도록 요구된다 -가 exact queries보다 더 다루기에 쉽다. Approximate queries는 일반적으로 그 오브젝트와 그것들의 경계에 할당된 특정한 collision properties를 보고하도록 요구된다. 예를들어, 그러한 특성들은 road surface의 slipperiness(미끄러움) 또는 한 wall surface의 climbability를 포함할지도 모른다.
만약 오브젝트들이 관통한다면, 어떤 프로그램들은 penetration depth를 찾는 것을 요구한다. 그 관통 깊이는 보통 minimum translational distance의 관점에서 정의된다: 그것은 그 오브젝트들을 분리하는 가장 짧은 movement vector의 길이이다. 이 movement vector를 연산하는 것은 일반적으로 어려운 문제이다. 두 disjoint objects A와 B사이의 separation distance는 A에 있는 점들과 B에 있는 점들 사이의 거리의 최소로 정의된다. distance가 0일 때, 그 오브젝트들은 교차하고 있다. 두 오브젝트들 사이의 거리 측정을 하는 것은, 충돌의 다음 시간의 예측을 하도록 한다는점에서 유용하다. 좀 더 일반적인 문제는 A와 B의 closest points (가장 가까운 점)을 찾는 문제이다: 그 오브젝트들 사이의 separation distance를 주는 A에 있는 점과 B에 있는 점. 가장 가까운 점들이 필수적으로 unique할 필요가 없다는 것이 주목해라; 무한 개의 가장 가까운 점들이 있을지도 모른다. dynamic objects에 대해, 다음 충돌의 시간을 연산하는 것은 estimated time of arrival (ETA) 또는 time of impact(TOI) 연산으로서 알려져 있다. ETA 값은 예를들어, rigid body simulation에서 time step을 조정하도록 사용된다. Type of motion은 다음 섹션에서 더 이야기되는 simulation 파라미터들 중 하나이다.
2.4 Environment Simulation Parameters
이 챕터에서 이전에 언급되었듯이, 한 시뮬레이션의 몇 가지 파라미터들은 직접적으로 충돌 탐지 시스템에 대해 적절한 선택이 무엇인지에 대해 영향을 미친다. 그것들이 발생시킬지도 모르는 어떤 문제들을 보여주기 위해, 다음 섹션들은 그 오브젝트들의 개수 그리고 그 오브젝트가 충돌 프로세싱과 어떻게 연관되는지를 구체적으로 본다.
2.4.1 Number of Objects
어떤 한 오브젝트가 잠재적으로 어떤 다른 오브젝트와 충돌할 수 있기 때문에, n개의 오브젝트들을 가진 한 시뮬레이션은 O(n^2)의 pairwise tests를 요구한다, 최악의 경우에. quadratic time complexity 때문에, 충돌을 위해 모든 오브젝트 쌍을 단순히 빠르게 테스팅하는 것은 심지어 적당한 값의 n에 대해 비싸다. pairwise test와 관련된 비용을 줄이는 것은 오직 선형으로 런타임에 영향을 미칠 것이다. 그 프로세스를 정말 가속시키기 위해서, 테스트되는 쌍의 개수가 줄어야 한다. 이 감소는 다양한 오브젝트들의 충돌 처리를 두 단계로 나누어서 수행된다: broad phase and narrow phase.
broad phase는 충돌할지도 모르는 오브젝트들의 더 작은 그룹을 확인하고, 명백히 충돌안할 오브젝트들의 그룹을 제외한다. 그 narrow phase는 subgroups 내에서 pairwise tests로 구성된다. 그것은 정확한 충돌을 결정하는데 책임이 있다. 그 broad and narrow phases는 가끔식 n-body processing과 pair processing이라고 개별적으로 불려진다.
그림 2.4는 어떻게 broad-phase processing이 divide-and-conquer 전략을 통해서 작업량을 줄이는지를 보여준다. (박스로 그려진) 11개의 오브젝트들에 대해, 한 모든 pairs test 55개의 개별 pair tests를 요구할 것이다. broad-phase processing가 5개의 disjoint subgroups을 생성한 후에 (그림자 영역으로 표시된), 오직 10개의 개별pair tests가 narrow phase에서 수행되어야 한다. broad-phase processing을 위한 방법들은 챕터 6에서 8까지 이야기 된다. Narrow-phase processig은 Chapters 4, 5, and 9에서 다뤄진다.
오브젝트들의 개수 외에도, 그 오브젝트들의 상대적인 크기는 또한 얼마나 많은 테스트들이 수행되어야 하는지에 영향을 미친다. 한 scene에 작고 큰 오브젝트들 둘 다 존재할 때, broad-phase system은 일반적으로 균일하게 크기가 있는 오브젝트들의 집합에 대해 하는 것 보다 그룹을 확인하기 위해 (또는 좀 더 정확해지기 위해) 더 열심히 일해야 한다. 오브젝트들의 사이즈가 broad-phase methods에 어떻게 영향을 미치는지에 대한 것은 Chapter 7에서 이야기 된다.
2.4.2 Sequential Versus Simultaneous Motion
실제 세계에서, 오브젝트들은 주어진 movement time step동안, simultaneously하게 움직인다, 어떤 eventual collisions이 그 time step내에서 해결되면서. 실제 세계 event의 정확한 컴퓨터 시뮬레이션을 위해, 그 움직이는 오브젝트들 어떤 두 개 사이의 contact의 가장 빠른 시간(earliest time)이 결정되어야만 한다. 그 시뮬레이션은 그러고나서 첫 번째 충돌이 발생할 때에 있어야할 자리에 모든 오브젝트들을 움직이고 나아갈 수 있다. 그 충돌은 그러고나서 해결되고, 그 과정은 다음 충돌을 결정하기 위해 계속되고, 전체 movement time이 다 사용될 때 까지 반복된다.
반복적으로 그 시뮬레이션을 contact의 다음 가장 초기 시간으로 나아가게 하여 시뮬레이션을 실행하는 것은 꽤 비싸다. 예를들어, 한 개 이상의 오브젝트들이 한 표면에 대해 쉬고 있을 때, 충돌의 다음 시간은 거의 현재 충돌 시간 직후에 바로 나온다. 그 시뮬레이션은 그러므로 아주 조금씩 나아가지고, 그래서 그것은 가상적으로 full movement time step을 해결하기 위해 영원히 한다. 이 문제에 대한 한 solution은 그 그룹 내에서 상호작용 할지도 모르는 오브젝트들을 그룹을 확인하는 broad phase를 사요하는 것이다. 그러나, time step동안에 다른 그룹들의 오브젝트와 있지 않는. 각 그룹의 시뮬레이션은 그러므로 다른 비율로 나아간다 그리고 이것은 그 문제를 일반적으로 완화시키는데 도움이 된다.
다른 대안은 오브젝트들을 동시에 움직이지만, 그 움직임에 대해 고정된 (small) time step을 설정하는 것이다. Simultaneous movement는 objects interpenetration을 발생시킬수 있고, 이것은 일반적으로 어느정도 그 시뮬레이션의 더 이전 상태로 백업하여 다뤄진다. 두 경우에, simultaneous updates는 비싸고, 그러므로 종종 정확한 rigid-body simulations을 위해 보존된다. 그러나, 다른 프로그램들 뿐만 아니라, 많은 게임들은 rigid body simulations이 아니다, 그리고 그것은 과도한 것이고, 높은 정확도의 움직임을 재현하려는 노력을 낭비한다. 이것에 대해, 다른 대안은 motion을 sequentially하게 해결하는 것이다. 즉, 오브젝트들은 한 번씩 움직여지고, 그 과정이 다음 오브젝트로 진행하기 전에 어떤 충돌들이 탐지되고 해결된다.
명백히, sequential movement는 물리적으로 정확한 movement model이 아니다. 어떤 오브젝트들은 이 프레임에서 아직 움직이지 않았지만 그 두 오브젝트들이 동시에 움직이는 길을 벗어나서 움직일지도 모른 오브젝트들과 충돌할지도 모른다. (그림 2.5a) 다른 오브젝트들은 그것들이 하기 전에 그리고 이제는 그것들의 경로에 있는 움직였던 오브젝트들과 충돌할지도 모른다. (그림 2.5b) 어떤 경우에, 두 개의 동시에 움직이는 오브젝트들이 그것들의 움직이는 도중에 충돌하는 경우, 충돌들은 이제 놓쳐질 것이다, 한 오브젝트가다른 것을지나갈때 (그림 2.5c). 예를들어, 게임에 대해서, sequential movement model에 의해 생기는 문제들은 종종 무시되어질 수 있다. 높은 프레임의 게임들은 종종 movement step을 매우 작게 만들어서, overlap이 또한 작게 하고 거의 눈치채지 못하게 한다.
sequential movement model의 장점들 중 하나는 한 object nonpenetration invariant가 유지하는데 매우 쉽다는 것이다. 만약 한 오브젝트가 움직이는 동안에 충돌이 있다면, 그 움직임은 쉽게 되돌려 질 수 있다 (예를들어). 한 단일의 오브젝트의 움직임만을 되돌리는 것은 fixed time step을사용하는 simultaneous movement model과 대조된다. 거기에서 모든 동시에 움직여지는 오브젝트들의 움직임은 되돌려져야 한다.
2.4.3 Discrete Versus Continuous Motion
충돌 결과를 결정하는데 필요한 computational effort와 그 결과의 정확성 그 자체 둘 다에 크게 영향을 미치는 어떤 것은 pairwise test에서 관련된 그 두 오브젝트들이 testing time에서 움직이고 있는지이다. Static collision detection은 오브젝트들이 움직이는 동안 이산 시간 지점에서 오브젝트들 사이의 intersection를 탐지하는 것을 포함한다. 시간의 각 그러한 지점에서, 그 오브젝트들은 마치 그것들이 현재 위치에서 zero velocities를 가진 것처럼 다뤄진다. 대조적으로, dynamic collision detection은 주어진 시간 interval 동안 오브젝트들의 완전한 continuous motion을 고려한다. Dynamic collision tests는 보통 충돌의 정확한 시간과 첫 번째 접촉 지점들을 보고할 수 있다. Static tests들은 dynamic tests들보다 훨씬 더 싸지만, test 사이의 time steps들은 짧아야 하는데, 오브젝트들의 움직임이 그 오브젝트들의 공간 크기보다 더 작아야 하도록 하기 위해서이다. 만약 그렇지 않다면, 그 오브젝트들은 간단히 한 time step에서다음으로 갈 때 충돌이 탐지되는 것 없이 서로를 지나갈지도 모른다. 이 현상은 tunneling이라고 언급된다.
주어진 시간 interval동안 continuous motion에 있는 한 오브젝트에 의해 다뤄지는 volume은 swept volume이라고 불려진다. 만약 두 개의 움직이는 오브젝트들의 swept volumes이 교차하지 않는다면, 그 오브젝트들 사이에는 어떠한 교차도 없다. 비록 그 swept volumes이 교차할지라도, 그 오브젝트들은 움직이는 동안 여전히 교차하지 않을지도 모른다. 따라서, 그 swept volumes의 교차는 충분하지만, 오브젝트들 충돌을 위한 조건이 필수적으로 아니다. 복잡한 움직임에 대해, 그 swept volume은 연산하고 작업하기에 둘 다 어렵다. 운 좋게도, 완벽한 정확성은 거의 필수적이지 않다. 복잡한 tumling motion의 Dynamic Collision testing은 보통 piecewise linear motion을 가정하여 간단하게 될 수 있다; 즉, 그 움직임의 범위에 대한 linear translation이다, 그 움직임의 끝(또는 처음에)에 instantaneous rotation이 있는. screw motion(즉, 고정된 회전과 평행이동 움직임)이 있는 unrestricted motion의 대체는 이러한 두 개의 대안 사이 어딘가에 있다.
움직이는 오브젝트와 작업할 때, 한 오브젝트의 움직임을 다른 오브젝트에서 빼서, 따라서 한 오브젝트를 static으로 만들어서, 그 오브젝트들의 상대적인 움직임을 고려하는 것이 가상적으로 항상 선호할만 하다. 그 오브젝트들에 대해 linear translational motion을 가정하는 것은 이 연산이 간단한 벡터 뺄셈으로 만든다. 오직 상대적인 움직임만을 고려하는 것의 주된 이점은 한 움직이는 오브젝트를 한 정적인 오브젝트에 대해 테스팅 하는 것에 대해, swept volume test가 이제 정확한 교차 테스트가 되도록 하는 것이다. 게임에서, 그 전체 swept volume은 가끔식 speed box로 대체된다 : 그것의 전체 움직임에 대해 그 오브젝트를 덮는 길게늘여진 박스 (또는 유사하게 간단한 proxy object, 반드시 box는 아니다).
2.5 Performance
게임 콘솔을 한 예시로 잡아서, 가장 간으한 비쥬얼들에 대해, 게임들은 60fps로 작동해야만 한다 (NTSC TV포맷을가진 나라에서, PAL territory에서 50 FPS). 이 프레임 율은 각 게임 프레임을 준비하는데 16.7 ms를 남긴다. 게임의 유형에 따라서, 충돌 탐지는 가령, 한 프레임의 10~30%를 차지할지도모른다, 차례로 충돌 탐지를 위해 2 ~ 5ms가 되는. 수십개의 충돌 의존적인 오브젝트들이 어떤 주어진 시간에 활성화 되는 한 액션 플랫폼 게임에 대해서, 각 오브젝트에 대해 충돌을 처리하기 위해 이용가능한 약 오직 50에서 250us(nano second)의 시간이 있을지도 모른다 - 많은 시간은 아니다. 명백히, 충돌 쿼리의 평균 작동 시간을 줄이는 것이 중요하다. 그러나, 프레임 율에서 큰 갑작스런 하락은 게임에서 눈치채어질 수 있기 때문에 (나쁜 방식으로), 선택된 알고리즘에 대해 최악의 경우가 평균 케이스보다 더 길게 걸리지 않도록 하는 것이 중요하다.
충돌 처리를 가속하기 위해서 많은 것들이 처리될 수 있다. 그것들은 차례로 큰 부분에서 이 책이 무엇인지에 대한 것이다. 최적화가 충돌 탐지와 무슨 관련이 있는지에 대한 어떤 일반적인 아이디어는 다음 섹션에서 이야기 된다.
2.5.1 Optimization Overview
최적화의 첫 번째 교리는 처음 장소에서 한 task를 수행할 필요가 없는 것보다 빠른 것이 없다는 것이다. 따라서, 어떤 가장 성공적인 속도 최적화는 가능한한 최소의 것으로 빠르게 작업을 쳐내는 것과 관련된다. 그러한 것으로서, 충돌 탐지 시스템에 대해 가장 중요한 최적화중 하나는 Section 2.4.1에서 언급된 broad-phase processing이다 : 오브젝트들의 spatial locality를 이용하는 것이다. 오브젝트들은 그것들에 가까운 것들만 부딪힐 수 있기 때문에, 먼 거리의 오브젝트들에 대한 테스트들은 상황을 공간으로 분해해서 피해질 수 있다. 테스트들은 그러고나서 오직 오브젝트 근처의 영역에 대해서만 된다. 이것은 그 오브젝트와 교차하기에 너무 먼 거리에 있는 것들을 무시한다. 이 공간 분할과 그려지는 그래픽 오브젝트의 개수를 제한하는 view frustum culling을 위해 처리되는 것 사이에 강한 연결성이 있다.
공간 분할은 공간을 단일한 크기의 cell의 한 grid로 나누어서 flat structure를 사용하여 수행될 수 있다. 그것은 또한 hierarchy의 관점에서 구현되어질 수 있다. 거기에서 공간은 재귀적으로 절반으로 나누어지는데, 어떤 종료 목표가 충족될 때 까지 된다. 오브젝트들은 그러고나서 grid 또는 hierarchy에 넣어진다. Grids들과 hierarchical partitioning은 또한 narrow phase의 pair tests에 또한 유용하다, 특히 그 오브젝트들이 높은 복잡성을 가질 때. 다른 것에 대해 한 전체의 오브젝트에 대해 테스트하기 보다는, 그것들은 충돌 테스트가 서로에게 가장 가까운 두 오브젝트의 가장 부분으로 제한되도록 한다. 오브젝트와 공간 분할은 Chapters 6과 7에서 이야기 된다.
좀 더 비싼 geometric test를 수행하기 전에, 값싼 bounding volume tests를 하는 것은 충돌을 결정하는데 필요한 작업의 양을 줄이는 좋은 방법이다. bounding spheres를 수반하는 것이 모든 오브젝트에 추가된다고 가정하자. 그러고나서 간단한 sphere-sphere intersection test가 이제 그 복잡한 포함된 geometry에 대한 테스팅이 필요없다는 것을 보여준다 - 그 spheres들이 중첩되지 않는다. Bounding volumes은 Chapter 4에서 다뤄진다.
오브젝트들이 프레임마다 작은 local steps를 취한다는 경향이 있다는 통찰력 - 만약 움직인다면 -은 세 번째의 가치있는 최적화로 이끈다 : temporal(or frame-to-frame) coherency를 이용하는 것. 예를들어, 지난 프레임을부터 움직이는 오브젝트들 만이 테스트되어야 한다; collision status는 다른 오브젝트들에대해 같게 남아 있는다. 만약 오브젝트들이 임의의 위치로 "텔레포트"하도록 허용된다면 Temporal coherency는 명백히 유효하지 않는다. Coherence는 Chapter 9에서더 이야기 된다.
마지막으로, architecture-specific optimizations이 또한 매우 중요하다. 많은 플랫폼들은 완전히 이용될 때 많은 가속을 제공할 수 있는 코드의 어떤 유형 또는 data parallelism을 지원한다. CPU가 연산하는 속도와 메인 메모리에서 CPU가 연산하도록 데이터를 제공할 수 있도록 하는 속도 사이의 큰 차이 때문에, 충돌 기하와 다른 데이터가 메모리에 어떻게 저장되는지는 충돌 시스템에서 큰 speed impact를 가질 수 있다. 이러한 문제들은 Chapter 13에서 상세히 다뤄진다.
2.6 Robustness
충돌 탐지는 robustness가 매우 중요한 많은 geometrical applications중의 하나이다. 이 책에서, robustness는 간단히 수적인 연산과 어떤 방법으로 다루기에 어려운 기하학적 설정을 다루는 프로그램의 능력을 말한다. 그러한 문제 입력과 직면했을 때, 한 robust program은 예상되는 결과들을 제공한다. nonrobust 프로그램은 같은 상황에서 crash하거나 무한 루프에 들어갈지도 모른다. Robustness problems는 넓게 두 개의 계층으로 분류될 수 있다: numerical robustness의 부족에 의한 것과 geometrical robustness의 부족으로 인한 것들.
Numerical robustness problems은 연산동안 유한 정밀도의 변수를 상요해서 발생한다. 예를들어, 중간 계산이 부동소수점 또는 정수 변수에 의해 나타내어질 수 있는 것보다 더 클 때, 그 중간 결과는 유효하지 않을 것이다. 만약 그러한 문제들이 탐지되지 않는다면, 그 연산의 최정 결과는 부정확할 가능성이 높다. Robust 구현은 그러한 문제가 발생하지 않도록 보장해야만 한다. 또한 만약 그것들이 그렇다면, 그 조정된 유효한 결과가 그것 대신에 반환되어야 한다.
Geometrical robustness는 topological correctness와 전반적인 geometrical consistency를 보장하는 것을 수반한다. 문제들은 종종 불가능한 기하를 포함하거나 기하를 degenerate한다. 이것은 bad numerical calculation의 결과일지도 모른다. 어떤 수준에서 대부분의 알고리즘들은 잘 형성된 입력을 기대한다. 나쁜 입력 geometry가 주어졌을 때, 평면에 정점들이 모두 있지 않는 한 정점 또는 폴리곤들로 퇴화하는 삼각형 같은, 만약 이러한 상황들이 포착되고 다루어지지 않는다면, 어떤 것이 발생할 수 있다.
numerical and geometrical robustness 사이의 구분은 가끔식 구분하기 어렵다. 어떤 것이 다른 것을 발생시킨다는 점에서. 구분하기 어렵고 고치기 어려운 런타임 에러들을 피하기 위해서, robustness는 충돌 탐지 시스템의 설계와 개발 둘 다 도처에서 고려되어야 한다. Chapters 11과 12는 좀 더 깊이 robustness를 이야기 한다.
2.7 Ease of implementation and Use
처음부터 구현된 충돌 탐지 시스템의 경우에, 예상되는 개발 시간의 문제는 요구되느 특징의 집합 만큼 중요할지도 모른다. 예를들어, 게임들은 종종 타이트한 예산과 시간 규격에 있고, 어떤 중요한 컴포넌트에 대한 딜레이는 비쌀 수 있다. 구현의 용이성을 평가할 때, 전반적인 알고리즘의 복잡성을 보는게 아니라, 특병한 경우의 타입들이 얼마나 많이 그리고 무엇이 포함되는지를 보는 것이 흥미롭다. (numerical tolerance같은), 그리고 그 개발 시간에 영향을 미칠지 모르는 다른 제한들을 보는 것.
몇 가지 추가 문제들은 충돌 탐지 시스템의 사용과 연관짓는다. 예를들어, 그 시스템은 얼마나 일반적인가? 그것은 크게 다양한 사이즈들의 오브젝트들을 처리할 수 있는가? 그것은 또한 range queries를 답할 수 있는가? collision-related data structures를 구성하는데 build process에서 얼마나 많은 시간이 요구되는가? 후자의 질문에 대해, 전처리에 소요되는 시간은 런타임 퍼포먼스와 관련없지만, 그것은 여전히 설계와 생산 단계에서 중요하다. 모델의 변화는 개발 중간에 빈번하고, 긴 전처리 시간과 생산성을 저해하고, 실험을 방해한다. 어떤 이러한 문제들은 더 빠르고, 덜 최적화된 데이터 구조 형성으로 완화될 수 있다, 개발 동안, 그리고 non-debug builds로 더 느리지만 좀 더 최적의 구성으로 인해.
2.7.1 Debugging a Collision Detection System
모든 코드 처럼, 충돌 탐지 시스템은 에러에 취약하다. 이러한 에러들을 찾는 것은 가끔씩 어렵고 시간을 소모할 수 있다. 이 디버깅 프로세스가 덜 고통스럽게 만들기 위해 개발하는 동안 단계들이 취해질 수 있다. 몇 가지 좋은 아이디어들은 다음을 포함한다:
- n개의 지난 queries에 대한 arguments의 cyclic buffer를 유지해라. 그 쿼리들은 몇 초간의 데이터 까지와 일치한다. 그러고나서, 어떤 것이 시각적으로 잘못될 때, 그 프로그램은 중지되어질 수 있고, 그 데이터가 나중의 분석을 위해 만들어질 수 있다. 저장된 arguments가 있는calls를 통해 나아감으로써. 그 log data는 또한 asserts가 trigger할 때 유용한 정보를 제공할지도 모른다.
- 충돌 기하를 시각화하는 수단을 제공해라. 예를들어, 너는 테스트된 faces, 그것들의 collision attributes, 그리고 어떤 hierarchies그리고 groupings of the faces를 시각화할지도 모른다. 부가적으로, 충돌 쿼리들을 시각화해라, 이전에 언급된 cyclic buffer로 제공되는 history화 함께. 이 시각화는 나쁜 충돌 쿼리를 포착하는것을 쉽게 만드는 context를 제공한다.
- simple reference algorithm을 구현해라 (서로에 대해 모든 오브젝트 또는 모든 폴리곤들을 테스트하는 brute-force algorithm같은) 그리고 좀 더 정교한 알고리즘과 함께 병행하여 그 레퍼런스 알고리즘을 작동시켜라. 만약 그 결과들이 다르다면, 문제가 있다 (좀 더 고급 알고리즘에 가능성이 있다).
- queries에 대한 test suite를 유지하고, 코드가 변할 때, 그 test suite에 대해 충돌 코드를 작동시켜라. geometric nature의 코드는 많은 특별 경우를 갖는 경향이 있고, 광범위한 테스트들의 한 집합을 갖는 것은 문제를 일찍 포착하는데 도움이 된다. 버그가 발견될 때 마다, 그것이 다시 도입되는지를 탐지할 테스트 케이스를 추가해라.
물론, assert() calls의 자유로운 사용같은 모든 일반적인 디버깅 전략은 또한 적용된다. 그러한 전략의 좋은 이야기는 [McConnel93, Chapter 26]에서 발견된다.
2.8 Summary
이 챕터는 충돌 탐지 시스템을 설계하고 구현할 때 고려되어야 할 많은 요소들을 열거했다. 그것은 충돌 테스트를 수행하기 위해 가능한 충돌 기하 표기, 렌더링 기하 또는 특수화된 기하를 사용할지에 대해 이야기 했다. 충돌 처리는 두 단계로 발생한다고 정의되었다, narrow and broad phase. 그 broad phase는 잠재적으로 충돌하는 오브젝트들의 작은 부분 그룹들을 coarsely하게 확인하는 것과 관련있지만, 반면에 narrow phase는 오브젝트들 사이의 세부적인 pairwise collision tests를 수행한다. Narrow phase testing은 Chapters 4와 5의 주된 토픽이고, 거기에서 다양한 geometrical object representations에 대한 많은 다른 query types이 이야기 된다. Narrow phase testing은 또한 Chapter 9에서 이야기 된다. Broad-phase method들은 Chapters 6 ~8에서 이야기 된다. robustness의 중요성이 강조되었다. 이 책은 robustness의 주제에 대해 두 개의 전체 챕터 Chapter 11 과 12를 헌신한다. 이 책이 실시간 프로그램을 위한 충돌탐지에 대한 것이기 때문에, 성능은 또한 중요한 시스템 고려사항으로서 강조되었다. 어떤 면에서, 대다수의 책은 성능에 관한 것이다. 효율적인 알고리즘과 자료구조가 도처에 이야기 된다는 점에서. 이 책은 Chapter 13에서 최적화에 대한 이야기로 결론짓는다.
============================================
Chapter 3 Math and Geometry Primer
Chapter 4 ~ 5 Narrow Phase
Chpater 6 ~ 8 Broad Phase
Chapter 9 Advanced Narrow Phase
Chapter 10 GPU Collision Detection
Chapter 11 ~ 12 Robustness
Chapter 13 Optimization
댓글 없음:
댓글 쓰기