Chapter 1 Introduction (실시간 충돌탐지)

Chapter 1 Introduction
이 책은 충돌탐지의 주제와 관련이 있다. 그것은 겉보기에 간단한 문제를 다루는 넓은 주제이다: 두 개 (또는 그 이상의 오브젝트들이 교차하는지를 탐지한다. 좀 더 특정하게, 충돌 탐지는 두 오브젝트가 접촉 하는지(if), 언제(when), 어디에서(where)를 결정하는 문제와 관련이 있다. "If"가 Boolean result를 만드는 것을 포함한다. 그리고 그것은 그 오브젝트가 교차하는지 아닌지에 대한 질문에 답한다. "When"은 부가적으로 움직이는 동안 충돌이 무슨 시간에 발생했는지를 결정한다. "Where"은 그 오브젝트가 어떻게 접촉했는지를 설립한다. 대강, 이러한 세 가지 질문의 유형들은 점점 더 주어진 순서대로 답하기 위해 복잡해진다.

when과 where에 대한 정보를 얻는 것은(Boolean collision detection result외에도) 가끔씩 collision determination이라고 이름 붙여진다. intersection detection과 interference detection이라는 용어는 충돌 탐지와 동일하게 가끔 사용된다.

충돌 탐지는 많은 다양한 프로그램에 기본적이다. 그것은 컴퓨터 게임, 물리 기반 시뮬레이션(컴퓨터 애니메이션), 로보틱스, 가상 프로토타이핑, 공학 시뮬레이션을 포함한다.

컴퓨터 게임에서, 충돌 탐지는 한 solid world의 환각이 유지되도록 보장한다. 그것은 플레이어 캐릭터가 바닥에서 떨어지거나 벽을 통과하지 않게 한다; 그것은 line-of-sight queries를 제공하고, 적에게 그것들이 플레이어를 볼 수 있는지를 말하고, 그러므로 공격할 수 있다고 말해준다; 그리고 그것은 스케이트보드를 타는 사람이 보이지 않는 guide surface에 붙어있도록 유지한다. 그리고 이것은 플레이어가 안전하게 airborne 을 한 후에 halfpipe로 떨어지게 해준다.

컴퓨터 애니메이션에서, 충돌 탐지는 예를들어 천의 물리 재현을 제약하기 위해 사용된다. 이것은 천이 실제와 같은 방식으로 행동하고, 캐릭터가 움직일 때, 캐릭터에 미끄러지지 않도록 보장한다. 충돌 탐지는 로보틱스 프로그램에서 path planning을 위해 사용된다. 그리고 이것은 로봇들이 장애물로부터 피하도록 도와준다. virtual prototyping에서 충돌 타미는 clearances를 연산하는데 도움울 주고, 전반적으로 프로토타입들이 물리적 모델의 생산없이 정제되도록 한다. 충돌 탐지는 충돌 테스트에 사용되고 다른 공학 시뮬레이션에서 사용된다.

path planning과 animation rendering같은 몇 가지 적용은 그것들의 충돌 시스템의 실시간 성능을 요구하지 않는다. 특히, 컴퓨터 게임과 같은 다른 프로그램들은 충돌 탐지 시스템의 실시간 효율성에 대해 비범한 요구를 갖는다. 컴퓨터 그리고 콘솔 기반의 액션 게임들은 많은 수의 쿼리들이 초당 약 30 ~ 60 프레임에서 (fps) 수행되어야 하는 것을 요구하는 시뮬레이션을 포함한다. 그러한 힘든 시간 제약과, 충돌 탐지로, 게임과 물리엔진의 중요한 부분이 충돌 탐지는 게임 프레임을 완료하는데 걸리는 시간의 많은 퍼센트를 차지한다. 컴퓨터 게임에서, 나쁘게 설계된 충돌 시스템은 쉽게 주요 bottleneck이 된다.

이 책은 일반적으로 충돌탐지에 대한 것이 아니라, 특정하게, 실시간 프로그램에서 충돌 탐지 문제를 해결하는 자료구조와 알고리즘의 효율적인 구현에 관한 것이다. 게임 영역이 종종 예시를 위해서 사용되지만, 몇 가지 게임이 아닌 프로그램들은 그러한 게임들과 유사한 성능 요구사항을 갖는다 (또는 더 큰 요구사항), 그리고 그것을 haptic (Force feedback) systems, particle simulations, surgical simulators, 그리고 다른 가상 현실 시뮬레이션들. 여기에서 설명되는 방법들은 이러한 프로그램에 동일하게 잘 적용된다.

여기에서 이야기되는 많은 방법들은 충돌 탐지외의 분야에도 적용가능하다. 예를들어, Chapters 6에서 8까지 이야기되는 방법들은 ray tracing과 ray casting을 가속하는데 사용될 수 있다(가령, scene lighting을 계산하는 것), 그리고 geographic information systems와 관련하여, 큰 지리 데이터베이스에 대한 쿼리를 답하기 위해 사용될 수 있다. 컴퓨터 그래픽스 분야에서의 몇 가지 문제들은 충돌 탐지 문제로 해결될 수 있다. 예를들어, view frustum culling은 Chapters 6과 7에서 설명되는 방법들을 사용하여 다뤄질 수 있다.

1.1 Content Overview
다음의 섹션은 이 책의 챕터들의 간단한 개요를 제공한다.

1.1.1 Chapter 2: Collision Detection Design Issues
이 챕터는 충돌 탐지 시스템을 구성할 때 고려되어야 할 이슈들에 대해 이야기하고, 무슨 요소들이 디자인에 영향을 끼치는지에 대해 말한다. 그러한 요소들은 오브젝트들이 어떻게 표현되어야 하고, 그것들이 얼마나 많이 있어야 하고, 그것들이 어떻게 움직이고, 사용자는 무슨 종류의 충돌 queries를 날리길 원하는지를 포함한다.  Chapter 2는 또한 이 책의 나머지 전반에서 사용되는 용어를 소개한다.

1.1.2 Chapter 3: A Math and Geometry Primer
어떤 사소하지 않는 충돌 탐지 시스템은 collision queries의 if, when, where를 처리하기 위해 기하 중심의 수학의 많은 부분을 요구한다. Chapter 3는 남은 챕터에서 살펴볼 주제를 이해하는데 필요한 수학적 그리고 기하적인 개념들을 소개한다.

1.1.3 Chapter 4: Bounding Volumes
충돌 질의를 가속하기 위해서, 구와 박스같은 간단한 기하 오브젝트들이 좀 더 복잡한 특성을 가진 오브젝트들을 나타내기 위해 처음에 사용된다. 오직 그 "simple" bounding volumes (복잡한 오브젝트들을 캡슐화하기에 충분히 큰)들이 충돌한다면, 테스트들은 복잡한 기하에 대해 수행된다. Chapter 4는 몇 가지 bounding volume types에 대해 설명하고, 그것들에 대해 교차 테스트를 어떻게 수행하고, 복잡한 오브젝트에 대해 bounding volume을 어떻게 맞추는지를 설명한다.

1.1.4 Chapter 5: Basic Primitive Tests
이전 챕터에서 몇 가지 교차 테스트를 소개한 후에, Chapter 5는 lines, rays, segments, planes, triangles, polygons, spheres, boxes, cylinders, and polyhedra들을 포함하는 다양한 타입들의 오브젝트 쌍 사이의 교차 상태와 거리를 결정하기 위한 많은 수의 테스트를 설명한다. 두 개의 정적이고 움직이는 오브젝트들이 이러한 테스트에서 고려된다.

1.1.5 Chapter 6: Bounding Volume Hierarchies
큰 오브젝트들에 대해, 그리고 오브젝트들의 모음에 대해, 그 오브젝트(들)에 대한 bounding volumes의 hierarchies를 구성하여 성능 이득이 취해질 수 있다. 그러한 hierarchies는 오브젝트들 또는 충돌에 참여할 수 없는 한 오브젝트의 부분들에 대해 빠른 확인을 할 수 있게 한다. 그리고 이것은 질의들이 작은 수의 오브젝트들 또는 오브젝트의 부분들에 대해 테스팅을 제한하는 것을 허용한다. Chapter 6는 bounding volume hierarchies의 바람직한 특징과 방식에 대해 말한다. 그것들에 대해 구성하고 쿼리를 수행하는 것에 대해. 이 챕터는 또한 이러한 hierarchies를 표기하는 것의 효율적인 방식을 알아본다.

1.1.6 Chapter 7: Spatial Partitioning
많은 수의 오브젝트들이 충돌을 위해 고려될 때, 그 오브젝트들은 빠른 테스트를 가능하게 하기 위해, 작은 disjoint subgroups(서로소 부분그룹)에 분할되어야만 한다(모든 다른 오브젝트들에 대해 모든 오브젝트들을 검증하는 최악의 quadratic behavior를 피해서). Chapter 6에서 이야기 된 bounding volume hierarchies는 그러한 분할을 수행하는 한 방법을 나타낸다. Chapter 7은 grids, trees, and object sorting을 기반으로 다른 partitioning approaches를 조사한다.

1.1.7 Chapter 8: BSP Tree Hierarchies
충돌 탐지 데이터를 나타내는 가장 다재다능한 트리 구조 중의 하나는 binary space partitioning (BSP) tree이다. BSP trees는 공간에 있는 오브젝트들로부터 독립적으로 공간을 분할하는데 사용될 수 있다. 그것들은 또한 한 오브젝트가 있는 공간으로 부터 한 오브젝트의 boundary를 분할하는데 사용될 수 있다. 그것으로 인해 이것은 효과적으로 그 오브젝트의 volume representation을 형성한다. Chapter 8은 BSP trees를 튼튼하게 구성하는 것에 대해 이야기하고, 그 최종 트리에 대해 테스트를 어떻게 수행하는지에 대해 말한다.

1.1.8 Chapter 9: Convexity-based Methods
Chapter 9는 convex objects에 대해 충돌 질의를 수행하기 위해 많은 좀 더 고급의 방법들을 본다. 이것은 볼록 오브젝트의 특별한 특성을 이용한다. hierarchial representations, V-Clip closest feature algorithm, linear and quadratic programming의 수학적 최적화 방법, 효율적인 Gilbert-Johnson-Keerthi algorithm, 그리고 Chung and Wang에 의해 만들어진 separating vector algorithm이 소개된다.

1.1.9 Chapte 10: GPU-assisted Collision Detection
PC 상품 그래픽스 카드는 그것들이 main PC CPU보다 좀 더 많은 연산력을 통합하는 한 지점으로 진보했다. 이 변환느 그래픽스 카드로 연산을 아웃소싱하는 흥미를 촉발 시켰다. Chapter 10은 그래픽스 하드웨어를 사용하여 어떻게 충돌 탐지 검사를 수행할지를 간단하게 본다.

1.1.10 Chapter 11: Numerical Robustness
충돌 탐지 시스템에서 심지어 아주 작은 에러들은 재앙적인 실패를 이끌 수 있다. 예를들어 world geometry와 충돌에 실패한 오브젝트들이 그 world 밖으로 떨어지게 되는 것 같은 것이 있다. 이 챕터는 floating-point arithmetic과 작업하는 것과 연관된 robustness 문제에 대해 이야기하고, 이러한 문제들을 다루는 접근법을 제안한다.

1.11 Chapter 12: Geometrical Robustness
Chapter 11이 계산을 튼튼하게 수행하는 방법에 대해 보았지만, Chapter 12는 임의의 폴리곤 집합을 취하고, 그것을 충돌 탐지 시스템의 입력에 적절한 잘 형성된 기하로 바꾸는 것의 문제를 고려한다. welding of vertices, removal of gaps and cracks, merging of coplanar faces, and decomposition of objects into convex (or triangular) pieces에 대한 방법들이 소개된다.

1.12 Chapter 13: Optimization
이 책의 마지막 챕터는 책 전체에 보여진 효율적인 자료구조와 알고리즘을 어떻게 취할지에 대해 말하고, 특정 하드웨어 플랫폼에 대해 그것들을 어떻게 타겟팅하고 튜닝할지에 대해 이야기한다. 큰 성능의 이득은 메모리 구조(caches), 코드와 데이터 병렬성을 이용하기 위해 코드를 최적화하여 얻어질 수 있다. Chapter 13는 그러한 최적화를 어떻게 수행하는지에 대해 세부적인 설명을 보여준다.

1.2 About the Code
이 책의 직접 해보는 특성의 일부로서, 보여지는 많은 아이디어들은 코드 예제들로 보충된다. 많은 책들이 한 알고리즘의 넓은 아이디어들을 전달하기 위해 high-level pseudocode에만 의존하는 반면에, 여기에서 대다수의 코드는 C++로 주어진다. 코드를 이러한 세부사항으로 보여주는 두 가지 이유가 있다. 첫 째로, 그것은 한 알고리즘의 이해 (그리고 구현)에 종종 필수적인 세부사항을 제공한다. 둘 째로, 이해하는 것은 이제 부가적으로 그 코드를 실행시키고 실행하는 동안 변하는 값들을 조사하여 얻어질 수 있다. 그 후자는 특히 특별한 알고리즘 구현에 요구되는 수학에 완전히 정통하지 않을지도 모르는 독자에게 중요하다. 슈도코드로 표현되는 주어진 코드는 오직 그 책의 적은 장소에만 있다. 우선적으로 거기에서, 그것은 완전한 구현을 제공하는 것이 실용적이지 않을 것이다.

비록 C++이 책의 코드를 위해 사용되었을지라도, 그 책의 중점은 C++에 있다는 것이 아니라는 것이 강조되어야 한다. C++은 오직 설명되는 개념의 세부적인ㅅ ㅣㄹ행가능한 묘사를 보여주는 수단으로서 사용된다. 어떤 컴퓨터 언어든 이 목적을 수행할 것이지만, C++은 몇 가지 이유로 선택되었다. 그것은 그것의 인기와 간결한 방식의 추상화 능력, classes와 (overloaded) infix operators를 사용한 points and vectors와 같은 geometrical entities의 low-level manipulation들을 포함한다. 보여진 코드가 많은 프로그래머들에게 간으한한 접근가능하도록 하기 위해서 (예를들어, C또는 자바에 친숙한 사람들), 템플릿과 STL같은 C++의 어떤 특징들은 신중하게 가능하면 피해졌다. C++ 순혈주의자들은 각 챕터에서 시작에서 깊은 한 숨을 쉬길 우너할지도 모른다.

유사하게, 이 책은 소프트웨어 공학에 대한 책이 아니다. 가능한한 가장 좋은 것을 만나는 기본 아이디어를 얻기위해, 그 코드는 짧아지고, 요점만 유지한다. 글을 장황한 C++ syntax로 채우지 않기 위해서 양해가 구해져야 한다. 예를들어, 클래스 정의는 의도적으로 최소화된다 (또는 조냊하지 않는다), 전역 변수는 가끔씩 적절한 멤버 변수로 대체된다, 포인터들은 const (or restrict)로 선언되지 않는다, 그리고 배열들은 적절한 사이즈가 동적으로 할당되는 대신에 고정된 사이즈로 선언된다. 변수 이름들은 또한 typeset page에 코드 라인들이 더 잘맞도록 길이가 제한된다.

보여진 코드가 실제 production code로 바뀌기 위해서, 몇 가지 additions이 필요할지도 모른다. 예를들어, division by zero에 대한 테스트는 전반적인 접근법의 이해를 해칠지도 모르는 세부사항을 피하기 위해서 항상 수행되지 않는다. 유사하게, 몇 가지 코드 테스트들은 완전한 robustness를 위해 추가되어야 할 tolerance values를 요구할지도 모른다. 그 의도는presented code가 robust production code로 바뀌기 위해서 무슨 변화가 필요한지를 명확히 하기 위해 Chapter 11에서 robustness에 대해 이야기를 하기 위한 의도이다.

어떤 함수 인자들이 입력이고, 아웃풋인지 명확히 하는 것을 돕기위해, 입력 변수들은 종종 value으로 넘겨지고, output 변수들은 reference로 넘겨진다. 어떤 경우에, 입력 변수를 reference로 넘기는 것이 좀 더 효율적일 것이다. 이것은 독자를 위한 exercise로 남겨질 것이다.

주석들은 필기체로 써져있다. 반면에 코드는 boldface이다. 함수, 클래스들, 구조체, 그리고 사용자 정의 타입들의 일므은 대문자로 시작한다. 변수들은 소문자로 시작한다. 가능하면, 변수 이름들은 따라오는 텍스트에서 사용되는 표기를 따르도록 선택되어진다. 어떤 경우에 이러한 규칙은 대립한다. 옐르들어, points는 텍스트에서 대문자를 사용해서 표기되지만, 코드에서 그것들은 소문자이다.

이 책에 보여지는 코드는 동봉된 CD에서 이용 가능하다. 하지만, 독자들은 코드의 최신 버전을 위해 책의 companion web를 방문하길 원할지도 모른다. 그리고 거기에 수정, 변화, 추가들이 통합되어있다.