이 챕터에서, 그리고 다음 챕터에서, 우리는 물리 시뮬레이션을 제작하는 것으로부터 잠시 휴식을 가지고, 충돌 탐지를 알아볼 것이다.
챕터 7에서, 우리는 파티클 엔진에 contacts와 collisions을 추가했었지만, 우리는 회전하는 rigid bodies를 도입하기 위해 그것들을 없앴다. 우리는 간단히 contacts와 collisions을 그 엔진에 신비롭게 도입할 수 있다, 그것들이 어디서 오는지를 걱정하지 않은 채로, chapter 7에서 처럼. 만약 너가 존재하는 충돌 탐지 라이브러리로 작업한다면, 그러면 너는 이 접근법을 취해서 chapter 14로 넘어갈 수 있다. 이 챕터와 다음 챕터는 contact와 collision information이 어디에서 오는지 그리고 그것이 어떻게 생성되는지에 대한 overview이다.
나는 포괄적인 collision detection system을 만드는 시도를 하지 않을 것이다. 이 하나의 주제에 대해 홀로 이 것보다 더 긴 책들이 있고, 이야기될 필요가 있는 많은 함정들과 복잡성들이 있다.
만약 너가 존재하는 게임 엔진으로 작업한다면, 너가 사용할 수 있는 충돌 탐지 시스템을 가질 가능성이 높다. 그러나, 다음의 두 챕터를 읽을 가치가 여전히 있다. 모든 렌더링 엔진들은 비효율적인 충돌 탐지 routines를 제공하거나 (많은 것들이 그려지듯이, 같은 geometry를 사용한다, 그리고 그것은 processing time의 낭비이다), 또는 물리 시스템이 필요한 세부적인 contact data의 종류를 제공하지 않는다.
나는 더 작은 게임들에 유용한 충돌 탐지에 대해 한 가지 특정한 접근법을 통해 나아갈 것이다. 그것은 좀 더 완전한 시스템으로 나아가는 jumping-off point로서 유용하고, 모든 충돌 탐지기에게 흔한 문제의 종류들을 일으키는 한 방식으로서 유용하다.
만약 너가 완전하고 포괄적인 충돌 탐지 시스템을 만들기 원한다면, 나는 Ericson [2005]의 이 책과 같은 시리즈를 추천할 것이다. 그것은 튼튼한 최종 상품에 귀중한 tradeoffs, architecture, and optimization에 대해 세부사항을 포함한다.
12.1 Collision Detection Pipeline
충돌 탐지는매우 time-consuming process가될 수 있다. 게임에서 각 오브젝트들 어떤 다른 오브젝트와 충돌할지도 모르고, 각 그러한 쌍은 체크되어야만 한다. 만약 게임에 수백 개의 오브젝트들이 있다면, 수십만의 checks가 필요할지도 모른다. 설상가상으로, 각 check는 관련된 두 오브젝트들의 도형을 이해해야만 한다. 그리고 그 오브젝트들은 수천개의 폴리곤들로 이루어질지도 모른다. 그래서 완전한 충돌 탐지를 수행하기 위해서, 우리는 엄청나게 많은 시간을 소비하는 checks가 필요할지도 모른다. 이것은 우리가 프레임마다 가지는 시간의 fraction에서 가능한 것이 아니다.
운 좋게도, 개선을 위한 많은 여지가 있다. 두 가지 주된 문제들 - 너무 많은 충돌을 갖는 것과 비싼 checks를 갖는 것 - 은 독립적인 해결책을 갖는다. 필요한 checks의 개수를 줄이기 위해, 우리는 two-step process를 사용한다.
- 처음에, 우리는 서로 접촉(contact)할 가능성이 높은 오브젝트들의 집합들을 찾으려고 하지만, 그것들이 실제로 그러한지에 대해 너무 관여하지 않는다. 이것은 일반적으로 거대한 대다수의 가능한 collision checks를 줄이기 위해서 경험법칙과 특수화된 자료구조를 사용하는 꽤 빠른 프로세스이다. 그것은 "coarse collision detection"라고 불려진다.
- 그러고나서 code의 두 번째 chunk는 candidate collisions를 보고, 그것들이 실제로 접촉한지를 결정하는 check를 한다. 이것은 "fine collision detection"이다. 접촉하는 오브젝트들은 정확히 그 접촉이 각 오브젝트에서 어디에 있는지를 (rigid bodies에 필요한)과 충돌의 normal 결정하기 위해 조사된다. 이것은 가끔씩 "contact generation"이라고 불려지고, 그 결과들은 물리 엔진의 입력을 형성한다.
그 첫 번째 element는 이 챕터에서 다뤄진다; 그 두 번째 element는 chapter 13에서 다뤄진다.
각 check에서 걸리는 시간을 줄이기 위해서, 그 도형은(geometry) 일반적으로 간단하게 된다. 충돌 탐지를 위한 special geometry는 종종 만들어지고, 이것은 contact tests를 더 쉽게 만든다. Collision geometry는 section 13.1에서 이야기 된다.
12.2 Coarse Collision Detection
충돌 탐지의 첫 번째 단계(phase)는 수행될 full-detail checks의 리스트를 만드는 것이 임무이다. (사실, 우리는 두 단계 사이에 넘길 자료구조로서 명시적인 list를 만들지 않을 것이다. coarse collision detector가 간단히 그것이 그럴듯한 충돌을 만날 때 마다 fine collision detector를 호출하도록 하는 것이 훨씬 더 편리하다.. fine collision detector는 그러고나서 물리엔진에 넘길 실제 collision의 실제 list를 축적시킬 수 있다.) 그것은 다음의 주된 특징들을 가질 필요가 있다.
- 그것은 conservative해야만 한다. 다시 말해서, 게임에 있는 모든 충돌들은 checks의 list에 포함되어야만 한다. coarse collision detector는 결국 충돌로 끝나지 않을 checks들을 ("false positives"라고 불리는) 생성하는 것이 허용된다. 그러나, 충돌일 checks ("false negative"라고 불리는) 를 생성하는데에 실패해서는 안된다.
- 그것은 가능한한 작은 리스트를 생성해야만 한다. 이전의 특징과 결합하여, 이것은 그것이 반환하는 가장 작은 리스트가 contacts를 이끌 checks의 리스트라는 것을의미한다. 그 경우에, coarse collision detection은 완전히 정확한 충돌 탐지를 수행할 것이고, 그래서 더 이상의 checks는 필요 없을 것이다. 그러나, 실제로, coarse detection은 보통 많은 false positives를 포함하는 가능한 checks의 한 집합을 반환한다.
- 가능한한 빨라야만 한다. 요구되는 checks의 최적의 개수와 가까운 것을 생성하는 것이 가능할지도 모른다. 그러나 만약 그렇게 하는데 시간이 많이 걸린다면, coarse collision detector의 목적에 피해를 주는 것이다.
두 개의 broad approaches가 coarse collision detection을 위해 사용된다: bounding volume hierarchies and spatial data structures. 우리는 차례로 이것을 볼 것이다.
12.3 Bounding Volumes
bounding volume은 한 오브젝트를 포함한다고 알려진 공간의 한 지역이다. coarse collision detection을 위한 volume을 나타내기 위해, 간단한 도형이 사용된다, 일반적으로 sphere or box. 그 도형은 충분히 크게 만들어지는데, 전체 오브젝트가 그 도형안에 있도록 보장되기 위해서이다.
그 도형은 그러고나서 몇 가지 간단한 충돌 테스트들을 수행하도록 사용되어질 수 있다. 만약 두 오브젝트들이 닿지 않는 bounding volumes를 갖는다면, 그러면 그 오브젝트들이 그것 내에서 접촉할 수 있는 방법은 없다. 그림 12.1은 spherical bounding volumes를 가진 두 오브젝트를 보여준다.
이상적으로 bounding volume은 그것들의 오브젝트에 가능한한 밀접합게 fitting해야한다. 만약 두 개의 close-fitting bounding volumes가 닿는다면,그러면 그것들의 오브젝트들이 닿을 가능성이 높다. 만약 그 bounding volumes내의 대부분의 공간이 채워지지 않았다면, 그러면 닿고있는 bounding volumes는 그 오브젝트가 접촉해있다는 것을 의미하지 않을 가능성이 높다.
Spheress는 편리하다. 왜냐하면 그것들은 나타내기에 쉽기 때문이다. sphere의 중심과 그것의 반지름을 저장하는것으로도 충분하다:
struct BoundingSphere { glm::vec3 center; real radius; }
또한 두 개의 구가 겹치는지 (코드를 위해서 chapter 13을 보아라)를 체크하는 것은 매우 쉽다. 만약 그것들의 중심 사이의거리가 그것들의 반지름의 합보다 작다면, 그것들은 겹친다. Spheres는 대부분의 오브젝트들을 위한 bounding volumes의 좋은 도형이다.
Cubic boxes는 또한 종종 사용된다. 그것들은 중심점과 크기의 집합으로 나타내어질 수 있는데, 각 방향마다 한 개씩 사이즈가 있다. 이러한 크기들은 종종 "half-sizes" or "half-widths"로 불려지는데, 왜냐하면, 그것들이 중심점으로부터 박스의 edge까지의 거리를 나타내기 때문이다. 그리고 이것은 대응되는 방향에서의 박스의 전체 사이즈의 절반이다.
Cubic boxes는 또한 종종 사용된다. 그것들은 중심점과 크기의 집합으로 나타내어질 수 있는데, 각 방향마다 한 개씩 사이즈가 있다. 이러한 크기들은 종종 "half-sizes" or "half-widths"로 불려지는데, 왜냐하면, 그것들이 중심점으로부터 박스의 edge까지의 거리를 나타내기 때문이다. 그리고 이것은 대응되는 방향에서의 박스의 전체 사이즈의 절반이다.
struct BoundingBox { glm::vec3 center; glm::vec3 halfSize; }
boxes를 bounding volumes으로서 사용하는 두 가지 흔한 방법들이 있다: world coordinates에 정렬되거나 ("axis-aligned bounding boxes", or AABB) 오브젝트의 좌표에 정렬되거나 ("object bounding boxes", or OBBs). Spheres는 그러한 구분이 없다. 왜냐하면 그것들은 회전할 때 변화하지 않기 때문이다. 키가 크고 얇은 오브젝트들에 대해, bounding box는 bounding sphere보다 더 잘 tightly하게 들어맞을 것이다. 그러나 닿고있는 boxes를 탐지하는 것은 닿고있는 spheres를 탐지하는 것보다 훨씬 더 복잡하다. 그래서, spheres가 종종 시작하기에 좋은 장소이다.
다른 가능한 bounding volume 표기법이 있고, 그것들 자신의 강단점이 있다. 그러나, 어떠한 것도 널리쓰이지 않는다. 그래서 나는 이 챕터의 목적을 위해서 그것들을 무시할 것이다. 그것들은 Ericson [2005]에서 길게 이야기 된다.
이 챕터의 나머지에서, 나는 오직 bounding spheres만을 사용할 것이다. bounding spheres로 처리되어질 수 있는 어떤 것은 또한 bounding boxes로도 처리될 수 있다. 일반적으로 box version은 정확히 같은 알고리즘을 가지만, 더 오래 걸리고, 좀 더 까다로운 수학을 사용할 것이다. 알고리즘을 사용하는 것을 배울 때, bounding spheres는 작업하기에 더 간단하다.
그러나, tradeoff로서, 우리가 오브젝트들이 닿고있는지를 보는 first check로서 이러한 volumes를 사용한다는 것을 기억하는 것이 중요하다. 만약 우리가 좀 더 정확한 bounding volumes를 가졌다면, 그러면 그 first check는 좀 더 정확해 질 것이다. 그래서, 우리는 해야할 덜 follow-up을 가질 것이다. 많은 경우에 (특히, crates같은 게임에서 박스 같은 것들이 많은), bounding spheres는 bounding boxes보다 훨씬더 잠재적인 충돌을 만들어낼 것이다.그러고나서 더 간단한 sphere-collision tests를 할 때 우리가 절약하는 시간은 이 챕터에서 더 복잡한 collision detection routines를 사용하는 것을 거부하기 위해 부가적인 potentail collisions를 가짐으로써 잃어질 것이다.
12.3.1 Hierarchies
한 bounding volume에서 각 오브젝트가 둘러 싸여 있을 때, 우리는 오브젝트들이 접촉해있을 가능성이 높은지를 보는 cheap test를 수행할 수 있다. 만약 그 bounding volumes가 닿고있다면, 그러면 그 check는 fine collision detector에 의한 좀 더 세부적인 검사를 위해 coarse collision detector로부터 반환될 수 있다. 이것은 collision detection을 극적으로 가속시키지만, 그것은 여전히 오브젝트들의 모든 쌍을 체크하는 것을 포함한다. 우리는 bounding volumes를 hierarchies에 배열함으로써 이러한 checks의 대부분을 하는 것을 피할 수 있다.
Bounding Volume Hierarchy(BVH) tree 자료구조의 leaves에서 그것의 bounding volume에 각 오브젝트를 가진다. 가장 lowest level bounding volumes는 자료구조에서 부모 노드와 연결되고, 그 각각은 그것 자신의 bounding volume을 가진다. parent node에 대한 bounding volume은 그것으로부터 내려받는 모든 오브젝트들을 감쌀만큼 충분히 크다.
우리는 hierarchy에서 각 level에서 bounding box를 계산할 수 있다. 그래서 그것은 가장 잘 그것 내에서 포함되는 오브젝트와 잘 맞는다. 이것은 우리에게 hierarchical voumes의 가장 가능한 집합을 줄 것이다. 그러나, 여러 번, 우리는 모든 그것의 후손들의 bounding volumes를 포함하는 parent node에 대한 bounding volume을 선택하는 것은 더욱 간단한 route를 취할 수 있다. 이것은 더 큰 high-level bounding volumes로 이끌지만, bounding volumes의 재계산은 좀 더 빠를 수 있다. 그러므로, query performance (잠재적 충돌을 결정하는 것)과 자료구조를 구성하는 속도 사이에 tradeoff가 있다.
그림 12.2는 4개의 오브젝트와 3개의 layers를 포함하는 한 hierarchy를 보여준다. 그림에서 부모 노드들에 붙여져있는 오브젝트들이 없는 것을 주목해라. 이것은 절대적인 요구사항은 아니다: 우리는 트리에서 더 높이 있는 오브젝트들을 가질 수 있다. 이것은 그것들의 bounding volume이 완전히 그것들의 후손을 감싼다고 가정한다. 그러나, 대부분의 구현에서, 오브젝트들은 오직 밑바닥에서 발견된다. 트리에서 (즉, 이진 트리 자료구조에서) 각 노드에 대해 두 개의 자식들만을 가지는 것은 또한 흔한 practice이다. 이것을 하는 수학적 이유가 있지만 (충돌 queries의 실행 속도의 관점에서), 이진 트리를 사용하는 가장 좋은 이유는 구현의 편안함 때문이다: 그것은 자료구조가 compact하게 만들고, 우리가 나중에 만날 몇가지 알고리즘을 간단하게 만든다.
우리는 충돌 탐지를 가속화 하기 위해 hierarchy를 사용할 수 있다: 만약 트리에 있는 두 개의 노드들의 bounding volumes가 닿고있지 않다면, 그러면 이러한 노드들로부터 내려가는 오브젝트들 중 어떠한 것도 가능히 접촉할 수 없다. hierarchy에서 같은 높이에 있는 두 개의 bounding volume을 테스트하여, 우리는 모든 그것들의 후손들을 즉시 결론지을 수 있다.
만약 그 두 개의 같은 높이 level의 노드들이 닿는다면, 그러면 각 노드의 자식들은 고려될 필요가 있다. 닿고있는 이러한 자식들의 조합들만이 접촉할 수 있는 후손들을 가질 수 있다. 그 hierarchy는 재귀적으로 내려와진다; 각 스테이지에서, 닿고있는 volumes들의 그러한 조합들은 더 고려된다. 그 알고리즘은 마침내 오브젝트들 사이의 잠재적인 접촉들의 리스트를 생성한다. 이 리스트는 정확히 bounding volumes의 각 가능한 쌍을 고려하여 만들어지는 것과 같지만, 그것은 일반적으로 더 빠르게 여러번 발견된다.
hierarchy가 게임에 있는 모든 오브젝트들을 포함한다고 가정하여, 잠재적인 충돌의 한 리스트를 얻는 코드는 다음처럼 보인다:
다른 가능한 bounding volume 표기법이 있고, 그것들 자신의 강단점이 있다. 그러나, 어떠한 것도 널리쓰이지 않는다. 그래서 나는 이 챕터의 목적을 위해서 그것들을 무시할 것이다. 그것들은 Ericson [2005]에서 길게 이야기 된다.
이 챕터의 나머지에서, 나는 오직 bounding spheres만을 사용할 것이다. bounding spheres로 처리되어질 수 있는 어떤 것은 또한 bounding boxes로도 처리될 수 있다. 일반적으로 box version은 정확히 같은 알고리즘을 가지만, 더 오래 걸리고, 좀 더 까다로운 수학을 사용할 것이다. 알고리즘을 사용하는 것을 배울 때, bounding spheres는 작업하기에 더 간단하다.
그러나, tradeoff로서, 우리가 오브젝트들이 닿고있는지를 보는 first check로서 이러한 volumes를 사용한다는 것을 기억하는 것이 중요하다. 만약 우리가 좀 더 정확한 bounding volumes를 가졌다면, 그러면 그 first check는 좀 더 정확해 질 것이다. 그래서, 우리는 해야할 덜 follow-up을 가질 것이다. 많은 경우에 (특히, crates같은 게임에서 박스 같은 것들이 많은), bounding spheres는 bounding boxes보다 훨씬더 잠재적인 충돌을 만들어낼 것이다.그러고나서 더 간단한 sphere-collision tests를 할 때 우리가 절약하는 시간은 이 챕터에서 더 복잡한 collision detection routines를 사용하는 것을 거부하기 위해 부가적인 potentail collisions를 가짐으로써 잃어질 것이다.
12.3.1 Hierarchies
한 bounding volume에서 각 오브젝트가 둘러 싸여 있을 때, 우리는 오브젝트들이 접촉해있을 가능성이 높은지를 보는 cheap test를 수행할 수 있다. 만약 그 bounding volumes가 닿고있다면, 그러면 그 check는 fine collision detector에 의한 좀 더 세부적인 검사를 위해 coarse collision detector로부터 반환될 수 있다. 이것은 collision detection을 극적으로 가속시키지만, 그것은 여전히 오브젝트들의 모든 쌍을 체크하는 것을 포함한다. 우리는 bounding volumes를 hierarchies에 배열함으로써 이러한 checks의 대부분을 하는 것을 피할 수 있다.
Bounding Volume Hierarchy(BVH) tree 자료구조의 leaves에서 그것의 bounding volume에 각 오브젝트를 가진다. 가장 lowest level bounding volumes는 자료구조에서 부모 노드와 연결되고, 그 각각은 그것 자신의 bounding volume을 가진다. parent node에 대한 bounding volume은 그것으로부터 내려받는 모든 오브젝트들을 감쌀만큼 충분히 크다.
우리는 hierarchy에서 각 level에서 bounding box를 계산할 수 있다. 그래서 그것은 가장 잘 그것 내에서 포함되는 오브젝트와 잘 맞는다. 이것은 우리에게 hierarchical voumes의 가장 가능한 집합을 줄 것이다. 그러나, 여러 번, 우리는 모든 그것의 후손들의 bounding volumes를 포함하는 parent node에 대한 bounding volume을 선택하는 것은 더욱 간단한 route를 취할 수 있다. 이것은 더 큰 high-level bounding volumes로 이끌지만, bounding volumes의 재계산은 좀 더 빠를 수 있다. 그러므로, query performance (잠재적 충돌을 결정하는 것)과 자료구조를 구성하는 속도 사이에 tradeoff가 있다.
그림 12.2는 4개의 오브젝트와 3개의 layers를 포함하는 한 hierarchy를 보여준다. 그림에서 부모 노드들에 붙여져있는 오브젝트들이 없는 것을 주목해라. 이것은 절대적인 요구사항은 아니다: 우리는 트리에서 더 높이 있는 오브젝트들을 가질 수 있다. 이것은 그것들의 bounding volume이 완전히 그것들의 후손을 감싼다고 가정한다. 그러나, 대부분의 구현에서, 오브젝트들은 오직 밑바닥에서 발견된다. 트리에서 (즉, 이진 트리 자료구조에서) 각 노드에 대해 두 개의 자식들만을 가지는 것은 또한 흔한 practice이다. 이것을 하는 수학적 이유가 있지만 (충돌 queries의 실행 속도의 관점에서), 이진 트리를 사용하는 가장 좋은 이유는 구현의 편안함 때문이다: 그것은 자료구조가 compact하게 만들고, 우리가 나중에 만날 몇가지 알고리즘을 간단하게 만든다.
우리는 충돌 탐지를 가속화 하기 위해 hierarchy를 사용할 수 있다: 만약 트리에 있는 두 개의 노드들의 bounding volumes가 닿고있지 않다면, 그러면 이러한 노드들로부터 내려가는 오브젝트들 중 어떠한 것도 가능히 접촉할 수 없다. hierarchy에서 같은 높이에 있는 두 개의 bounding volume을 테스트하여, 우리는 모든 그것들의 후손들을 즉시 결론지을 수 있다.
만약 그 두 개의 같은 높이 level의 노드들이 닿는다면, 그러면 각 노드의 자식들은 고려될 필요가 있다. 닿고있는 이러한 자식들의 조합들만이 접촉할 수 있는 후손들을 가질 수 있다. 그 hierarchy는 재귀적으로 내려와진다; 각 스테이지에서, 닿고있는 volumes들의 그러한 조합들은 더 고려된다. 그 알고리즘은 마침내 오브젝트들 사이의 잠재적인 접촉들의 리스트를 생성한다. 이 리스트는 정확히 bounding volumes의 각 가능한 쌍을 고려하여 만들어지는 것과 같지만, 그것은 일반적으로 더 빠르게 여러번 발견된다.
hierarchy가 게임에 있는 모든 오브젝트들을 포함한다고 가정하여, 잠재적인 충돌의 한 리스트를 얻는 코드는 다음처럼 보인다:
이 코드는 각 노드가 두 volumes가 겹치는지를 보는 것을 체크하는 overlaps method를 구현하는 한, bounding volume hierarchy의 어떤 종류와도 작업할 수 있다. 그 bounding sphere hierarchy는 다음 처럼 구현된다:
완전한 충돌 탐지 시스템에서, 알려진 오브젝트에 대해 hierarchy를 query하는 method를 갖는 것은 흔하다. 이것은 여전히 더 쉽다: 그 오브젝트의 bounding volume은 hierarchy의 root에 대해 체크되고, 그것이 겹치는 한, 각 후손들은 재귀적으로 점검된다.
12.3.2 Building the Hierarchy
이 단계에서 질문한 중요한 질문은 그 hierarchy가 어떻게 구성되는가 이다. 너의 그래픽스 엔진은 이미 준비가 된 bounding volume hierarchy를 가지는 것에 대한 것일지도 모른다. Bounding volume hierarchies는 그려질 필요가 있는 오브젝트들의 수를 줄이기 위해 광범위하게 사용된다. hierarchy의 root node는 현재 카메라에 대해 그것의 volume을 테스트받게 한다. 만약 그 bounding volume의 어떤 부분이 카메라에 의해 보여질 수 있다면, 그러면 그것의 child nodes는 재귀적으로 체크되어진다. 만약 한 노드가 카메라에 의해 보여질 수 없다면, 그러면 그것의 후손들 중 어떠한 것도 체크될 필요가 없다. 이것은 우리가 충돌 탐지를 위해 사용했던 같은 알고리즘이다: 사실, 게임의 보이는 부분과 함께, 그것은 효과적으로 충돌을 점검하는 것이다.
그래픽스 엔진이 무슨 오브젝트가 보여질 수 있는지를 결정하는 존재하는 bounding volume hierarchy를 가지고 있지 않는 경우에, 또는 만약 너가 밑바닥부터 게임을 만든다면, 너는 너 자신의 것을 만들어야 할 것이다. 이상적으로, 그 hierarchy는 어떤 주요 특징을 가져야 한다:
완전한 충돌 탐지 시스템에서, 알려진 오브젝트에 대해 hierarchy를 query하는 method를 갖는 것은 흔하다. 이것은 여전히 더 쉽다: 그 오브젝트의 bounding volume은 hierarchy의 root에 대해 체크되고, 그것이 겹치는 한, 각 후손들은 재귀적으로 점검된다.
12.3.2 Building the Hierarchy
이 단계에서 질문한 중요한 질문은 그 hierarchy가 어떻게 구성되는가 이다. 너의 그래픽스 엔진은 이미 준비가 된 bounding volume hierarchy를 가지는 것에 대한 것일지도 모른다. Bounding volume hierarchies는 그려질 필요가 있는 오브젝트들의 수를 줄이기 위해 광범위하게 사용된다. hierarchy의 root node는 현재 카메라에 대해 그것의 volume을 테스트받게 한다. 만약 그 bounding volume의 어떤 부분이 카메라에 의해 보여질 수 있다면, 그러면 그것의 child nodes는 재귀적으로 체크되어진다. 만약 한 노드가 카메라에 의해 보여질 수 없다면, 그러면 그것의 후손들 중 어떠한 것도 체크될 필요가 없다. 이것은 우리가 충돌 탐지를 위해 사용했던 같은 알고리즘이다: 사실, 게임의 보이는 부분과 함께, 그것은 효과적으로 충돌을 점검하는 것이다.
그래픽스 엔진이 무슨 오브젝트가 보여질 수 있는지를 결정하는 존재하는 bounding volume hierarchy를 가지고 있지 않는 경우에, 또는 만약 너가 밑바닥부터 게임을 만든다면, 너는 너 자신의 것을 만들어야 할 것이다. 이상적으로, 그 hierarchy는 어떤 주요 특징을 가져야 한다:
- bounding volumes의 volumes은 가능한한 작아야 한다, 트리의 각 level에서. 한 부모 노드가 함께 가까운 두 개의 bounding volumes를 그룹 지을 때 이것은 사실이다.
- 어떤 부모의 child bounding volumes는 가능한한 작게 중첩되어야 한다. 종종, 이것은 첫 번째 요구사항과 충돌한다. 그래서, 일반적으로 최소한의 중첩에 대해 더 작은 volume을 선호하는 것이 더 낫다. 사실, 만약 너가 tree의 어떤 low level에서 최소의 overlap을 선택한다면, 더 큰 overlaps이 더 높아지도록 야기시킬 가능성이 높다: 그래서 전반적으로 low overlap을 가진 한 트리는 두 가지 요구사항을 충족시킬 가능성이 높다.
- 그 트리는 가능한한 균형이 맞춰져야 한다. 너는 다른 곳은 얕지만 매우 깊은 트리의 몇 가지 braches들을 갖는 것을 피해야만 한다. 그 최악의 경우 시나리오는 한 가지 길이의 branch를 가진 트리이다. 이 경우에, hierarchy를 가진 것의 장점은 최소가 된다. 가장 큰 속도 상승은 모든 branches들이 대충 같은 길이에 있을 때 얻어진다.
hierarchy를 구성하는 여러가지 방법들이 있다. 그리고 각각은 속도와 퀄리티 사이의 타협이다. 상대적으로 static worlds에 대해, 오브젝트들이 많이 움직이지 않는, 한 hierarchy는 offline으로 만들어질 수 있다 (즉, 그 게임이 작동하지 않는동안: 그 level이 로딩되던지, 좀 더 그럴듯하게, 또는 그것이 배송되기전에 level을구성하는 동안). 매우 dyanmic words에 대해, 오브젝트들이 끊임없이 움직이는 (예를들어, space shooter). 그 hierarchy는 게임 동안에 다시 지어질 필요가 있다.
나는 hierarchies가 어떻게 구성될 수 있는지에 대한 overview와 flavor를 줄 것이지만, 완전한 세부사항으로 들어가는 것은 많은 챕터가 걸릴 것이다. 너는 Ericson [2005]에서 좀 더 많은 정보를 찾을 수 있다.
다음은 BVH(Bounding Volume Hierarchy)를 구성하는 것에 대한 세 가지 접근법들이다.
다음은 BVH(Bounding Volume Hierarchy)를 구성하는 것에 대한 세 가지 접근법들이다.
- Bottom-up : Bottom-up 접근법 (그림 12.3에서 보여지듯이)은 개별 오브젝트와 상응하는 bounding volumes의 리스트로 시작한다. 오브젝트들의 쌍은 이야기된 hierarchy의 요구사항을 기반으로 선택되고, 한 부모노드가 그 pair에 더해진다. 이 parent node는 그러고나서 리스트에 있는 그 오브젝트들을 대체한다. 그 프로세스는 리스트에 오직 한 개의 node가 남을 때 까지 계속된다.
- Top-down : Top-down 접근법 (그림 12.4에서 보여지듯이)은 이전처럼 같은 리스트로 시작한다. 그 알고리즘의 each iteration에서, 리스트에 있는 오브젝트들은 두 개의 그룹으로 나눠지는데, 각 그룹의 멤버들이 함꼐 모이도록 하기 위해서이다. 그 같은 알고리즘은 그러고나서 각 그룹에 적용되고, 그것을 두개로 나누는데, 이것은 각 그룹에 오직 한 개의 오브젝트만이 남을 때 까지 한다. 각 split은 트리에서 한 node를 나타낸다.
- Insertion : insertion approach (그림 12.5에서 보여지듯이)는 게임에서 사용되기에 적합한 유일한 것이다. 그것은 완전히 hierarchy를 다시 구성할 필요 없이 hierarchy를 조정할 수 있다. 그 알고리즘은 존재하는 트리와 함께 시작한다 (그것은 만약 우리가 처음부터 시작한다면 empty tree가 될 수 있다). 한 오브젝트가 그 트리에 재귀적으로 내려감으로써 그 트리에 더해진다: 각 노드에서, 새로운 오브젝트를 가장 잘 수용할 child가 선택된다. 결국 한 존재하는 leaf가 도달되고, 그것은 그러고나서 존재하는 leaf와 새로운 오브젝트 둘 다에 대한 새로운 부모로 대체된다.
각 알고리즘은 많은 변형을 갖는다. 특히, 노드들을 함께 그룹짓는데 사용되는 정확한 기준은 tree의 퀄리티에 큰 영향을 갖는다. bottom-up approach는 일반적으로 그룹지을 근처의 오브젝트들을 찾는다; top-down approach는 그 집합을 나누기 위해 clustering techniques를 얼마든지 사용할 수 있다; 그리고 insertion approach는 트리의 각 level로 어떤 child가 가장 잘 재귀해서 들어갈지를 선택할 필요가 있다. 그 tradeoffs의 세부사항은 복잡하고, 최적의 결과를 얻기위해서, 그것들은 많은 양의 미세한 tuning과 실험을 요구한다.
운 좋게도, 심지어 간단한 구현은 우리에게 합리적인 퀄리티의 트리와 coarse collision detector에 대한 좋은 speed-up을 줄 것이다. 우리의 구현에 대해, 나는 게임동안에 사용할 수 있는 유연성을 위해 insertion algorithm을 선택했다. 우리가 이전에 만들었떤 sphere hierarchy가 주어진다면, 우리는 insertion algorithm을 이 방식으로 구현할 수 있다:
트리의 각 노드에서, 우리는 bounding volume이 새로운 오브젝트가 더해졌을 때 가장 적게 확장될 child를 선택한다. 그 새로운 bounding volume은 현재의 bounding volume과 새로운 오브젝트를 기반으로 계산된다. 두 구의 중심 사이의 선이 발견되고, 그 거리는 그 라인을 따른 두 구 사이의 극단 사이 이다. 그 중심점은 그러고나서 두 극단 사이의 선에서 배치되고, 그 반경은 계산된 거리의 절반이다. 그림 12.6은 이 과정을 보여준다.
결합된 bounding sphere가 두개의 child bounding spheres를 포함하는 것에 주목해라: 일반적으로 그 child objects를포함하는 가장 작은 구는 아니다. 우리는 성능의 이유 때문에 이 추가적으로 낭비되는 공간을 쓰게 된다. 두 오브젝트 사이의 bounding sphere를 계산하기 위해, 우리는 그것들의 도형의 핵심에 파고들어갈 필요가 있다. 이것은 게임에서 사용하기에 프로세스를 너무 느리게 만든다.
우리는 한 오브젝트를 제거하는 유사한 알고리즘을 수행할 수 있다. 이 경우에, 트리에서 어떤 노드의 부모노드에 접근할 수 있도록 하는것이 유용하다. 그러므로, 우리는 이것처럼 hierarchy를 보유하는 자료구조를 확장할 필요가 있다:
한 오브젝트를 hierarchy에서 제거하는 것은 그것의 부모 노드를 그것의 sibling으로 대체하고, bounding volumes을 다시 계산하는 것을 포함한다. 그림 12.7은 이 과정을 보여준다. 그것은 이것처럼 구현될 수 있다:
결합된 bounding sphere가 두개의 child bounding spheres를 포함하는 것에 주목해라: 일반적으로 그 child objects를포함하는 가장 작은 구는 아니다. 우리는 성능의 이유 때문에 이 추가적으로 낭비되는 공간을 쓰게 된다. 두 오브젝트 사이의 bounding sphere를 계산하기 위해, 우리는 그것들의 도형의 핵심에 파고들어갈 필요가 있다. 이것은 게임에서 사용하기에 프로세스를 너무 느리게 만든다.
우리는 한 오브젝트를 제거하는 유사한 알고리즘을 수행할 수 있다. 이 경우에, 트리에서 어떤 노드의 부모노드에 접근할 수 있도록 하는것이 유용하다. 그러므로, 우리는 이것처럼 hierarchy를 보유하는 자료구조를 확장할 필요가 있다:
한 오브젝트를 hierarchy에서 제거하는 것은 그것의 부모 노드를 그것의 sibling으로 대체하고, bounding volumes을 다시 계산하는 것을 포함한다. 그림 12.7은 이 과정을 보여준다. 그것은 이것처럼 구현될 수 있다:
12.3.3 Sub-Object Hierarchies
너가 재현할 필요가 있는 몇 가지 오브젝트들은 크거나 곤란한 도형들을 가진다. 그러한 오브젝트들에게 딱 맞는 어떤 간단한 boinding volume을 만드는 것은 어렵다. 어떤 특정한 bounding volume shape에 대해, 그 format에 간단히 맞지 않는 부가적인 오브젝트들이 있을 것이다. 각 경우에, 그 bounding volume은 너무 크고, 그 coarse collision detector는 너무 많은 false positives를 반환할 것이다.
이 문제를 해결하기 위해서, 한 오브젝트에 대해 수 많은 bounding volumes를 사용하는 것이 가능하다, hierarchy에 배치되는. 그림 12.8에서, 우리는 돌출부가 있는 하나의 길고 얇은 오브젝트를 가지고 있다. bounding box와 sphere 둘 다 그것에 잘 맞지 않는다. 만약 우리가 bounding objects의 hierarchy를 사용한다면, 우리는 좀 더 근접합 fit을 제공할 수 있다. 이 경우에, 그 bounding boxes가 더 좋은 fit을제공한다. 비록 길이에 따라 배치된 많은bounding spheres의 hierarchy를 사용하는 것이 또한 작동할지라도.
충돌을 탐지하기 위한 알고리즘은은 단일 오브젝트 hierarchical bounding volume과 같다. 전체 오브젝트에서의 bounding volume에서 멈추는 것 보다, 우리는 여전히 간단히 bounding volume 비교를 사용하면서 좀 더 미세한 checks의 집합을 수행할 수 있다.
그 같은 프로세스는 우리가 게임 수준 자체에 대해 hierarchy를 구성하는 것을 허용한다. 명백히, 대부분의 게임 levels는 너무 커서, 그것들의 bounding volume은 모든 다른 오브젝트들을 포함할 가능성이 높다 (비록 box로 표현되는 outdoor levels는 높은 고도에 있는 오브젝트들을 제외할 수 있을지라도).
더 좋은 fit을 얻기 위해, 우리는 그 level을 bounding volumes의 hierarchy로 분해할 수 있다. 대부분의 게임 levels의 박스 같은 structure 때문에 (사각형 벽, 평평한 바닥, 등등), bounding box hierarchy가 일반적으로 bounding spheres보다 더 좋다.
이것이 받아들일만하고, 좋은 성능을 제공하고, 몇 몇 게임에서 사용되어왔을지라도, 좀 더 인기있는 접근법은 게임 level의 충돌을 처리하는 spatial data structure를 사용하는 것이다.
너가 재현할 필요가 있는 몇 가지 오브젝트들은 크거나 곤란한 도형들을 가진다. 그러한 오브젝트들에게 딱 맞는 어떤 간단한 boinding volume을 만드는 것은 어렵다. 어떤 특정한 bounding volume shape에 대해, 그 format에 간단히 맞지 않는 부가적인 오브젝트들이 있을 것이다. 각 경우에, 그 bounding volume은 너무 크고, 그 coarse collision detector는 너무 많은 false positives를 반환할 것이다.
이 문제를 해결하기 위해서, 한 오브젝트에 대해 수 많은 bounding volumes를 사용하는 것이 가능하다, hierarchy에 배치되는. 그림 12.8에서, 우리는 돌출부가 있는 하나의 길고 얇은 오브젝트를 가지고 있다. bounding box와 sphere 둘 다 그것에 잘 맞지 않는다. 만약 우리가 bounding objects의 hierarchy를 사용한다면, 우리는 좀 더 근접합 fit을 제공할 수 있다. 이 경우에, 그 bounding boxes가 더 좋은 fit을제공한다. 비록 길이에 따라 배치된 많은bounding spheres의 hierarchy를 사용하는 것이 또한 작동할지라도.
충돌을 탐지하기 위한 알고리즘은은 단일 오브젝트 hierarchical bounding volume과 같다. 전체 오브젝트에서의 bounding volume에서 멈추는 것 보다, 우리는 여전히 간단히 bounding volume 비교를 사용하면서 좀 더 미세한 checks의 집합을 수행할 수 있다.
그 같은 프로세스는 우리가 게임 수준 자체에 대해 hierarchy를 구성하는 것을 허용한다. 명백히, 대부분의 게임 levels는 너무 커서, 그것들의 bounding volume은 모든 다른 오브젝트들을 포함할 가능성이 높다 (비록 box로 표현되는 outdoor levels는 높은 고도에 있는 오브젝트들을 제외할 수 있을지라도).
더 좋은 fit을 얻기 위해, 우리는 그 level을 bounding volumes의 hierarchy로 분해할 수 있다. 대부분의 게임 levels의 박스 같은 structure 때문에 (사각형 벽, 평평한 바닥, 등등), bounding box hierarchy가 일반적으로 bounding spheres보다 더 좋다.
이것이 받아들일만하고, 좋은 성능을 제공하고, 몇 몇 게임에서 사용되어왔을지라도, 좀 더 인기있는 접근법은 게임 level의 충돌을 처리하는 spatial data structure를 사용하는 것이다.
12.4 Spatial Data Structures
coarse collision detection에 대한 몇 가지 다른 접근법들은 "spatial data structures"의 banner 밑에 있는다. spatial data structures와 bounding volumes사이의 구분은 어느정도 흐릿하다.
bounding volume hierarchy는 그것들의 상대적인 위치와 크기를 기반으로 오브젝트들을 함께 그룹짓는다. 만약 그 오브젝트들이 움직인다면, 그러면 그 hierarchy도 또한 움직일 것이다. 다른 오브젝트들의 집합에 대해서, 그 hierarchy는 매우 다른 구조를 가질 것이다.
spatial data structure는 world에 묶여있다. 만약 한 오브젝트가 세계에서 어떤 위치에서 발견된다면, 자료구조에서 한 위치에 매핑될 것이다. spatial data structure는 오브젝트가 그것 내에서 위치되어있는 것에 따라 그것의 구조를 바꾸지 않는다. 이것은 자료구조를 형성하는 것을 훨씬 더 쉽게 만든다.
현실에서, 둘 사이의 선은 흐릿하고, 기법들의 한 조합은 가끔씩 사용된다 (spatial data structure에 삽입된 hierarchies, 예를들어, 또는, 덜 흔하게, hierarchy에서 한 노드에 있는 spatial data structure). 또한 심지어 어떠한 bounding volume hierarchies가 사용되지 않을 때, 각 오브젝트 주위에 bounding volumes를 사용하는 것은 매우 흔하다라는 것에 주목하는 것은 또한 가치가 있다. 이 챕터의 나머지에서, 나는 오브젝트들이 bounding volume에 싸여있다고 가정할 것이다: 그것은 많은 알고리즘들을 훨씬 더 간단하게 만든다.
이 섹션은 세 가지 흔한 spatial data structures를 본다: binary space partition (BSP) trees, quad- and oct- trees, and grids. 대 부분의 게임에서 오직 하나만이 사용될 것이다.
12.4.1 Binary Space Partitioning
binary space partition tree는 bounding volume hierarchy와 유사한 방식으로 행동한다. 그것은 이진 트리 자료구조이고, 그래서 재귀 알고리즘은 그 트리의 꼭대기에서 시작해서, 충돌이 참여할 수 있다면, 자식 노드들로 내려간다.
그러나, bounding volumes를 사용하기 보다는, BSP에서 각 노드는 모든 공간을 둘로 분할하는 plane을 사용한다. 그것은 두 개의 자식 노드들을 가지고, 그 plane은 각 side에 대해 하나씩이다. 그 plane의 한 면 또는 다른 면에 놓여있는 오브젝트들은 대응되는 자식의 한 후손으로서 발견될 것이다. 평면(plane)을 가로지르는 오브젝트들은 다르게 다뤄진다: 그것들은 그 노드에 직접적으로 붙여질 수 있다; 가장 가까이에 있는 자식 노드에 배치된다; 또는, 좀 더 흔하게, 두 자식 노드들에 배치된다.
각 level에서 분할하는 평면들은 다르고, 그리고 이것은 모든 공간은 어떤 방식으로든 분할되는 것을 허용한다. 이 섹션에서 나중에 그 그림은 2D version을 보여주지만, 그 같은 구조는 3차원에 대해서도 작동한다.
BSP에 있는 각 plane은 vector position과 vector direction으로 나타내어진다:
coarse collision detection에 대한 몇 가지 다른 접근법들은 "spatial data structures"의 banner 밑에 있는다. spatial data structures와 bounding volumes사이의 구분은 어느정도 흐릿하다.
bounding volume hierarchy는 그것들의 상대적인 위치와 크기를 기반으로 오브젝트들을 함께 그룹짓는다. 만약 그 오브젝트들이 움직인다면, 그러면 그 hierarchy도 또한 움직일 것이다. 다른 오브젝트들의 집합에 대해서, 그 hierarchy는 매우 다른 구조를 가질 것이다.
spatial data structure는 world에 묶여있다. 만약 한 오브젝트가 세계에서 어떤 위치에서 발견된다면, 자료구조에서 한 위치에 매핑될 것이다. spatial data structure는 오브젝트가 그것 내에서 위치되어있는 것에 따라 그것의 구조를 바꾸지 않는다. 이것은 자료구조를 형성하는 것을 훨씬 더 쉽게 만든다.
현실에서, 둘 사이의 선은 흐릿하고, 기법들의 한 조합은 가끔씩 사용된다 (spatial data structure에 삽입된 hierarchies, 예를들어, 또는, 덜 흔하게, hierarchy에서 한 노드에 있는 spatial data structure). 또한 심지어 어떠한 bounding volume hierarchies가 사용되지 않을 때, 각 오브젝트 주위에 bounding volumes를 사용하는 것은 매우 흔하다라는 것에 주목하는 것은 또한 가치가 있다. 이 챕터의 나머지에서, 나는 오브젝트들이 bounding volume에 싸여있다고 가정할 것이다: 그것은 많은 알고리즘들을 훨씬 더 간단하게 만든다.
이 섹션은 세 가지 흔한 spatial data structures를 본다: binary space partition (BSP) trees, quad- and oct- trees, and grids. 대 부분의 게임에서 오직 하나만이 사용될 것이다.
12.4.1 Binary Space Partitioning
binary space partition tree는 bounding volume hierarchy와 유사한 방식으로 행동한다. 그것은 이진 트리 자료구조이고, 그래서 재귀 알고리즘은 그 트리의 꼭대기에서 시작해서, 충돌이 참여할 수 있다면, 자식 노드들로 내려간다.
그러나, bounding volumes를 사용하기 보다는, BSP에서 각 노드는 모든 공간을 둘로 분할하는 plane을 사용한다. 그것은 두 개의 자식 노드들을 가지고, 그 plane은 각 side에 대해 하나씩이다. 그 plane의 한 면 또는 다른 면에 놓여있는 오브젝트들은 대응되는 자식의 한 후손으로서 발견될 것이다. 평면(plane)을 가로지르는 오브젝트들은 다르게 다뤄진다: 그것들은 그 노드에 직접적으로 붙여질 수 있다; 가장 가까이에 있는 자식 노드에 배치된다; 또는, 좀 더 흔하게, 두 자식 노드들에 배치된다.
각 level에서 분할하는 평면들은 다르고, 그리고 이것은 모든 공간은 어떤 방식으로든 분할되는 것을 허용한다. 이 섹션에서 나중에 그 그림은 2D version을 보여주지만, 그 같은 구조는 3차원에 대해서도 작동한다.
BSP에 있는 각 plane은 vector position과 vector direction으로 나타내어진다:
struct Plane { glm::vec3 position; glm::vec3 direction; }
이것은 plane을 나타내기에 매우 흔한 방식이다: position은 plane에서의 어떤 위치이고, direction은 평면에 수직으로 가리킨다. 그 같은 평면은 만약 방향을 반대로 하면 생성될 수 있다: 그것은 여전히 그 평면에 수직이지만, 반대 방향을 향하고 있다. 그 direction vector가 그 평면의 한 면으로부터 가리킨다는 사실은, 우리가 다른 것으로부터 한 면을 구분할 수 있다는 것을 의미한다. 이 구분은 우리가 BSP에서 적절한 자식 노드를 선택하게 해준다.
한 오브젝트가 평면의 어떤 면에 놓여있는지를 결정하기 위해서, 우리는 chapter 2에서 주어진 스칼라곱의 기하학적 해석을 이용한다. 스칼라곱이 다른 것의 방향에서 한 벡터의 컴포넌트를 발견하게 해준다는 것을 회상해라.
여기에서, p_o는 우리가 관심있는 오브젝트의 위치이고 (우리는 보통 그것의 bounding volume의 중심의 위치를 사용한다), p_p는 평면에서의 어떤 점의 위치이고 (즉, 우리가 평면을 저장하기 위해 사용하는 점), 그리고 d_p는 그 평면이 바라보는 방향이다.
만약 c가 양수라면, 그러면 그 오브젝트는 그것의 방향이 가리키는 평면의 면에 놓여있고, 만약 음수이면, 그 오브젝트는 반대편에 놓여있다. 만약 c가 0이라면, 그러면 그것은 정확히 평면 위에 놓여있다. 그 방향벡터, d_p, 는 normalized vector여야 한다, 그리고 그 경우에 |c|는 평면으로부터의 오브젝트의 거리를 준다.
그 오브젝트가 spherical bounding volume을 가진다고 가정하여, 우리는 그것이 평면의 한 면에 완전히 있는지를 다음을 체크하여 결정할 수 있다
여기에서 r_o는 그 오브젝트의 bounding volume의 radius이다.
우리는 plane과 두 개의 자식 노드들을 포함하는 노드로부터 한 BSP tree를 구성할 수 있다.
한 오브젝트가 평면의 어떤 면에 놓여있는지를 결정하기 위해서, 우리는 chapter 2에서 주어진 스칼라곱의 기하학적 해석을 이용한다. 스칼라곱이 다른 것의 방향에서 한 벡터의 컴포넌트를 발견하게 해준다는 것을 회상해라.
여기에서, p_o는 우리가 관심있는 오브젝트의 위치이고 (우리는 보통 그것의 bounding volume의 중심의 위치를 사용한다), p_p는 평면에서의 어떤 점의 위치이고 (즉, 우리가 평면을 저장하기 위해 사용하는 점), 그리고 d_p는 그 평면이 바라보는 방향이다.
만약 c가 양수라면, 그러면 그 오브젝트는 그것의 방향이 가리키는 평면의 면에 놓여있고, 만약 음수이면, 그 오브젝트는 반대편에 놓여있다. 만약 c가 0이라면, 그러면 그것은 정확히 평면 위에 놓여있다. 그 방향벡터, d_p, 는 normalized vector여야 한다, 그리고 그 경우에 |c|는 평면으로부터의 오브젝트의 거리를 준다.
그 오브젝트가 spherical bounding volume을 가진다고 가정하여, 우리는 그것이 평면의 한 면에 완전히 있는지를 다음을 체크하여 결정할 수 있다
여기에서 r_o는 그 오브젝트의 bounding volume의 radius이다.
우리는 plane과 두 개의 자식 노드들을 포함하는 노드로부터 한 BSP tree를 구성할 수 있다.
struct BSPNode { Plane plane; BSPNode front; BSPNode back; };
우리가 bounding sphere hierarchy에 대해 보았던 것과 같은 방식으로, 이것은 C++로 구현되어질 수 있다:
typedef vector<Object*> BSPObjectSet; enum BSPChildType { NODE, OBJECTS }; struct BSPChild { BSPChildType type; union { BSPNode* node; BSPObjectSet* objects; }; }; struct BSPNode { Plane plane; BSPChild front; BSPChild back; };
polymorphism, 상속, C++의 runtime time inference (RTTI)를 사용하여, 구현은 이것처럼 보일 것이다:
모든 spatial data structures에 대해, leaves는 보통 어떤 개수의 오브젝트들을 가지고 다닐 수 있다. 이것은 bounding volume hierarchies가 유용할 수 있는 부분이다: BSP의 leap에서 오브젝트들의 그룹은 BVH로 나타내어질 수 있다
우리가 한 평면을 교차하는 오브젝트들이 두 개의 자식 노드들에 있는 BSP 트리를 가진다고 가정하자. 다시 말해서, 한 오브젝트는 그 트리에 몇 가지 위치에 있을 수도 있다. 가급적 발생할 수 있는 유일한 충돌들은 트리에서 같은 leaf에 있는 오브젝트들 사이에 있다. 우리는 간단히 차례로 트리의 각 leaf를 고려할 수 있다. 만약 그것이 적어도 그것 내에서 두 개의 포함된 오브젝트들을 가진다면, 그러면 그러한 오브젝트들의 모든 쌍의 조합들은 세부적인 점검을 위해 fine collision detector로 보내질 수 있다.
만약 우리가 BSP tree의 leaves에서 bounding volume hierarchy를 배치한다면, 우리는 그러고나서 각 hierarchy에 대해 coarse collision detection algorithm을 호출할 수 있다. 이 경우에, 우리는 두 개의 coarse collision detection step을 가진다.
만약 많은 오브젝트들, 몇 가지 큰 오브젝트들, 또는 많은 분할 평면들이 있따면, 그러면 트리의 수 많은 branches에서 한 오브젝트를 갖는 것은 엄청나게 큰 자료구조와 좋지 않은 성능으로 이끌 수 있다. 그 앞의 알고리즘은 겹치는 오브젝트들이 오직 하나의 자식노드에 보내지거나, 부모 노드와 함께 한 리스트에 유지될 때, 충돌 탐지를 하기 위해 수정되어질 수 있다. 좀 더 포괄적인 세부사항을 위해서 Ericson [2005]를 보아라.
BSP trees는 렌더링 엔진에서 흔하고, bounding volume hierarchies에 관해, 너는 너의 물리 시스템에 대해 존재하는 구현을 사용할 수 있을지도 모른다. 그것들은 level geometry와 game level사이에서 충돌을 탐지하기 위해 또한 흔히 사용된다. 그림 12.9는 game level의 부분에 대해 작은 BSP를 보여준다.
BSP는 그것의 leaves에 오브젝트들을 보유하지 않지만, 오히려 그 오브젝트가 충돌하는지 아닌지에 대한 boolean indication이 있다. 한 오브젝트는 각 평면에 대해 검사된다, 재귀적으로. 만약 그것이 평면을 교차한다면, 두 자식들은 체크된다; 만약 그렇지 않다면, 오직 하나만이 체크된다, 이전처럼. 만약 그 오브젝트가 충돌로서 표시되는 leaf에 도달한다면, 우리는 충돌이 발생했다는 것을 안다.
대부분의 충돌들은 움직이는 오브젝트들과 level geometry사이에서 발생하기 때문에 (일반적으로 변하지 않거나 전혀 움직일 수 없는), 그 BSP 접근법은 매우 유용하다. 불행하게도, 복잡한 전처리 단계가 level geometry로부터 BSP를 구성하기 위해 요구된다.
12.4.2 Oct-Trees and Quad-Trees
Oct-trees와 quad-trees는 BSP와 BVH 둘 다에 대해 많은 유사성을 가진 spatial data structures이다. Quad-trees는 2차원을 위해 사용되고 (또는 대부분의 오브젝트들이 땅위에 있는 3차원), 그리고 3차원을 위해 oct-trees가 사용된다. 많은 3D 게임에서, quad-tree는 oct-tree만큼 유용하고, 덜 메모리를 취한다. 그래서 나는 그것에 처음에 집중할 것이다.
quad-tree는 4개의 후손들을 가진 각각의 노드들의 한 집합으로 구성된다. 그 노드는 공간을 한 개의 점에서 교차하는 4개의 지역으로 분할한다. 그것은 BSP tree에서 세 개의 노드로 생각되어질 수 있다. 비록 분할되는 방향이 항상 world axes와 정렬될지라도. 한 node는 vector position과 4개의 자식들로 나타내어질 수 있다:
4개의 지역에 대해 한 오브젝트가 어떤 곳에 있는지를 검증하는 것은 그것들의 위치 벡터들의 대응되는 컴포넌트들을 비교하는 간단한 일이다. (1,4,5)에 있는 한 오브젝트와, (2,0,0)에 있는 QuadTreeNode에 대해, 우리는 그것이 top left area에 있다는 것을 안다, 그림 12.10에서 보여지듯이, 왜냐하면 그 오브젝트의 x좌표가 그 노드의 좌표보다 작고, 그 z좌표는 더 크기 때문이다. 우리는 배열에서 다음의 간단한 알고리즘으로 어떤 자식을 사용할지 계산할 수 있다:
여기에서 각 area에 대한 인덱스들은 그림 12.10에 보여지는 그것들과 부합한다.
oct-tree는 정확히 같은 방식으로 작동하지만, 8개의 자식을 갖고, 한 오브젝트가 어디에 위치해 있는지를 결정하기 위해 세 개의 벡터 컴포넌트의 각각에 대해 비교를 수행한다:
이론으로, 각 노드에 대한 position vector가 어디에서 든지 설정되어질 수 있을지라도, quad- and oct-trees에서 각 노드가 그것의 부모를 절반으로 나누는 것이 흔하다. 게임에서 모든 오브젝트들을 커버하는 axis-aligned bounding box로 시작하여, 그 top-level node는 이 박스의 중심점에 위치해 있는다. 이것은 효과적으로 같은 크기의 4개의 박스들을 생성한다 (quad-tree에 대해, oct-tree에 대해서는 8개). 이러한 박스들 각각은 한 노드로 나타내어지고, 그것의 위치는 그 박스의 중심점에 있고, 같은 크기의 좀 더 많은 4개의 박스들을 만든다. 그래서 hierarchy 아래로 내려간다.
이 절반으로 나누는 것을 사용하는 것에 대한 두 가지 이점이 있다. 첫 째로, node 자료구조에서 position vector를 제거하는 것이 가능하고, 트리를 재귀적으로 내려가는 동안 fly에서 point를 계산하는 것이 가능하다. 이것은 메모리를 절약한다.
둘 째로, 그것은 우리가 각 노드의 분할점을 배치할 최상의 장소를 찾는 어떤 계산을 할 필요가 없다는 것을 의미한다. 이것은 초기 hierarchy를 구성하는 것을 더 빠르게 만든다.
재귀의 방법과 각 노드에서 자식의 개수외에도, quad- and oct-trees는 BSP tree와 정확히 같은 방식으로 작동한다. 충돌을 결정하기 위해 BSP tree와 함께 작동하는 알고리즘들은 quad- or oct- tree에 대해서 같다. 그러나 그 테스트는 더 간단하고, 재귀할 좀 더 가능한 자식들이 있다.
또한 BSP tree와 함께, 우리는 분할하는 선을 겹치는 오브젝트들을 어디에 넣어야 할지를 결정해야 한다. 이전 코드 예제에서, 나는 그 오브젝트들이 그것의 중심을 포함하는 자식에 들어가도록 가정했다. 우리는 대신에 그 오브젝트를 그것이 닿는 모든 자식들에 배치할 수 있다, 우리가 BSP tree에 대해 했던 것 처럼, 그리고 같은 간단한 coarse collision detection을 가질 수 있다: 같은 leaf에 있는 오브젝트들만이 가급적 충돌할 수 있다.
Quad-trees는 특히 outdoor scenes에 대해 유용하다. 그리고 거기에서 오브젝트들은 landscape에 배치된다. 그것들은 indoor games에 대해 BSP trees 보다 덜 유용하다. 왜냐하면 그것들은 level의 벽과 충돌 탐지에 대해 쉽게 사용될 수 없기 때문이다. 그리고, BSP trees처럼, 그것들은 렌더링을 최적화하는데 종종 사용되고, 너가 사용하는 어떤 존재하는 렌더링 엔진의 일부가 될지도 모른다.
그것들이 실제로 BSP와 유사하기 때문에, 그것들로 작업하는 코드를 반복하는 것을 피할 것이다. CD에, BSP, quad-trees, and oct-trees에 대한 완전한 구현이 있다. (코드 없음)
12.4.3 Grids
우리의 끝에서 두 번째 공간 자료 구조는 quad-tree의 아이디어를 더 취한다. 만약 몇 가지 레이어가 깊은 절반으로 나눈 quad-tree의 분할된 패턴을 그린다면, 우리는 그것이 한 grid를 형성하는 것을 본다 (그림 12.11). regular grid를 나타내기 위해, 트리 자료구조를 사용하기 보다는, 우리는 간단히 regular grid를 사용할 수 있다.
한 grid는 어떤 수의 오브젝트든 있을지도 모르는, 위치의 배열이다. 그것은 트리 자료구조가 아니다. 왜냐하면 그 위치는 직접적으로 오브젝트의 위치로부터 결정될 수 있기 때문이다. 이것은 한 오브젝트가 트리에 재귀적으로 내려가는 것보다 더 빠르게 찾도록 해준다.
그 grid는 다음의 구조를 갖는다:
여기에서 xExtent와 zExtent는 그리드의 각 방향에서 셀들의 개수를 저장한다; oneOverCellSize 벡터의 x와 z 컴포넌트들은 1을 각 셀의 크기로 나눈 것을 포함한다 (우리는 다음의 알고리즘을 가속화하기 위해 실제 사이즈 보다는 1/value 를 사용한다); 그 y 컴포넌트는 일반적으로 1로 설정된다; origin은 grid의 원점이다. 그 그리드는 충분히 커야만 한다. 그 게임에서의 어떤 오브젝트든 그것 내에 포함되어야 하기 때문이다.
한 오브젝트의 중심점이 포함되는 위치를 결정하기 위해, 우리는 간단한 알고리즘을 사용한다:
이 코드 스니펫에서, 우리는 처음에 그 오브젝트가 어떤 square 안에 있는지를 찾는다. (우리는 1/value를 곱하여 그 분할을 한다). 이것은 우리에게 square라고 불려지는 벡터에서 각 컴포넌트에 대한 floating-point value를 준다. 이러한 floating-point 값들은 unsigned integers로 변환될 필요가 있따. 그 integer values는 그러고나서 반환될 grid array의 index를 찾기위해 사용된다.
BSP와 quad-trees에서 처럼, 우리는 한 quare의 edge에 겹치는 오브젝트들로 무엇을 할 지 결정할 필요가 있따. 그것들을 간단히 한 cell 또는 다른 것에 배치하는 것이 가장 흔하다. 비록 그것들을 그들이 겹치는 모든 셀에 배치하는 것이 가능할지라도. 이전 처럼, 후자는 가능한 충돌의 집합을 결정하는 것을 더욱 빠르게 하지만, 상당히 더 많은 메모리를 먹을 수 있다. 나는 좀 더 복잡한 경우로 돌아가기 전에 더 간단한 경우를 볼 것이다.
각 셀이 그 셀과 겹치는 모든 오브젝트들을 포함하는 grid에서, 충돌의 집합은 매우 간단하게 생성될 수 있다. 두 오브젝트들은 만약 그것들이 그리드에서 같은 위치를 차지한다면 충돌에 있을 수 있다. 우리는 간단히 한 개 이상의 오브젝트를 포함하는 각 위치를 볼 수 있고, 가능한 충돌에 대해 각 pair를 체크할 수 있다.
tree 기반의 표기와 다르게, 우리가 한 위치가 두 개 이상의 오브젝트들을 포함하는 지를 볼 수 있는 유일한 방법은 그것을 확인하는 것이다. 반면에 트리에 대해서, 우리는 각 노드에 오브젝트들의 개수를 저장했었고, 완전히 충돌을 생성할 수 없는 branches들을 놓칠 수 있다. 그래서 여기에서 어떠한 속도 향상이 없다.
가능한 충돌에 대해 수천 개의 위치를 찾는 것을 피하기 위해 (작은 수의 오브젝트들은 시간이 더 걸릴지도 모른다, 만약 우리가 coarse collision detection을 전혀하지 않는 것보다), 우리는 한 개 이상의 오브젝트를 포함하는 그리드 자료구조에서 위치들의 한 집합을 만들 수 있다. 우리가 한 오브젝트를 셀에 추가할 때, 만약 그 셀이 이제 두 개의 오브젝트들을 포함한다면, 그것은 occupied list에 추가되어야만 한다.
마찬가지로, 우리가 셀로부터 한 오브젝트를 제거할 때, 만약 그 셀이 이제 그냥 한 개의 오브젝트만 포함한다면, 그것은 리스트로부터 제거되어야만 한다. 충돌의 완전한 집합을 결정하는 것은 그러면 그 occupied list를 확인하고, pair-wise combinations를 fine-grained collision detector로 넘기는 문제이다.
만약 오브젝트들이 한 셀 이상의 크기라면, 그것들은 그리드에서 많은 셀들을 차지할 필요가 있을 것이다. 이것은 매우 많은 메모리 요구사항을 이끌 수 있다. 많은 낭비된 공간과 함께. PC에서 돌아가는 합리적인 크기의 게임 level에 대해, 이것은 문제가 아닐지도 모르지만, large levels or memory 제약 콘솔에 대해서, 그것은 받아들여지지 않을 수 있다.
만약 우리가 한 오브젝트를 그냥 한 grid cell에만 배치한다면 (그것의 중심이 cell에 보통 있는), 그러면 그 coarse collision detection routine은 이웃한 셀에 있는 오브젝트와의 충돌만을 체크할 필요가 있다. 셀과 같은 크기의 오브젝트에 대해, 그것은 8개로 된 가능한 한 집합으로부터 세 개의 이웃을 최대한으로 검사할 필요가 있다 (그림 12.12 참조). 그러나 이것은 급속히 증가된다. 셀의 크기가 4배가 더 큰 오브젝트에 대해, 가능한 24개의 이웃으로부터 15개가 고려될 필요가 있다. 정확한 이웃을 체크하는 코드를 쓰는 것은 가능하지만, 매우 큰 오브젝트들에 대해, 그것은 많은 낭비되는 노력을 포함한다.
hybrid data structure는 이 상황에 유용할 수 있다. 그리고 그것은 다양한 다른 크기의 그리드를 사용한다. 그것은 보통 "multi-resolution map"이라고 불려진다.
12.4.4 Multi Resolution Maps
multi-resolution map은 증가된 cell sizes가 있는 grdis의 집합이다. 오브젝트들은 그리드들 중의 하나에 추가된다, single grid와 같은 방식으로. 그 grid는 그 오브젝트의 크기를 기반으로 선택된다: 그것은 cells가 그 오브젝트보다 더 큰 가장 작은 그리드가 될 것이다.
종종 그 그리드들은 선택되는데, 각각이 이전의 것의 크기보다 4배나 큰 셀을 갖도록 하기 위해서이다 (쯕, 각 셀에 대해 너비와 길이가 두배인). 이것은 multi-reesolution map이 직접적으로 한 오브젝트를 어떤 그리드에 추가할 지를 계산하는 것을 허용한다.
coarse collision detection 동안에, 그 amp은 single grid algorithm의 수정된 버전을 사용한다. 각 grid에 대해, 그것은 각 오브젝트와 같은 또는 이웃한 셀에 오브젝트 사이의 잠재적인 collision을 만든다 (오브젝트들이 그들보다 작은 grid cell에 있을 수 없기 때문에 이제 체크 할 세 개의 이웃들이 최대 이다). 게다가, 그 오브젝트는 중첩되는 더 큰 셀의 그리드들에서 모든 오브젝트들에 대해 체크되어야 한다. 우리는 더 작은 셀의 그리드에 있는 오브젝트들에 대해서는 확인할 필요가 없다. 왜냐하면 그 작은 오브젝트들은 더 큰 오브젝트들에 대해 검사하는데 책임이 있기 때문이다.
맵에 있는 각 grid에 대해, 우리는 그리드 자료구조를 occupied cells의 같은 집합과 함께 사용할 수 있다. 그러나, 우리는 active list에 한 셀을 추가할 필요가 있는데, 만약 그것이 어떤 오브젝트든지 포함한다면 (왜냐하면 그것들이 이웃과 접촉할지도 모르기 때문이다).
12.5 Summary
Collision detection은 복잡하고 시간이 소모되는 프로세스이다. 그것을 철저히 하는 것은 실시간 물리에 대해 너무 오래걸린다. 그래서 몇 가지 최적화가 필요하다.
우리는 충돌 탐지를 두 단계로 분리할 수 있다: 가능한 접촉들을 찾는 coarse phase (몇몇은 충돌이 아닌 것으로 결과가 날 수 있지만, 그것은 결코 한 충돌을 놓쳐서는 안된다); 그리고 세부적으로 잠재적인 충돌을 체크하고 contact properties를 처리하는 fine-grained phase.
Coarse collision detection은 오브젝트들을 구나 박스같은 간단한 bounding volume에 감싸고, 각 collision volume에 대해 체크를 수행하여 작동한다. 그 collision volumes는 hierarchy에서 배치될 수 있고, 그것은 전체 brances가 제외도록 허용한다, 또는 공간 자료 구조에서도, 그것은 근처의 오브젝트들이 함께 접근되는 것을 허용한다.
다른 메소드들 사이에 tradeoffs가 있고, 많은 경우에 몇 가지들을 합칠 잠재성이 있다. 고려해야 할 가장 중요한 요소들 중의 하나는 그 렌더링 엔진이 그것들이 그려져야할지를 결정하기 위해 오브젝트들을 어떻게 관리할지 이다. 만약 너의 renderer가 준비된 한 시스템이라면, 그것을 사용하여 메모리를 절약하기 위해 채태갛는 것이 충고할만 하다.
그 coarse phase의 결과는 좀 더 상세하게 체크될 필요가 있는 가능한 접촉의 한 집합이다. 우리는 다음 챕터에서 이러한 checks를 수행하는데 필요한 알고리즘들을 볼 것이다.
struct BSPElement { }; struct BSPObjectSet : public BSPElement { vector<Object*> objects; } struct BSPNode : public BSPElement { Plane plane; BSPElement front; BSPElement back; };
모든 spatial data structures에 대해, leaves는 보통 어떤 개수의 오브젝트들을 가지고 다닐 수 있다. 이것은 bounding volume hierarchies가 유용할 수 있는 부분이다: BSP의 leap에서 오브젝트들의 그룹은 BVH로 나타내어질 수 있다
enum BSPChildType { NODE, OBJECTS }; struct BSPChild { BSPChildType type; union { BSPNode* node; BoundingSphereHierarchy* objects; }; }; struct BSPNode { Plane plane; BSPChild front; BSPChild back; };
우리가 한 평면을 교차하는 오브젝트들이 두 개의 자식 노드들에 있는 BSP 트리를 가진다고 가정하자. 다시 말해서, 한 오브젝트는 그 트리에 몇 가지 위치에 있을 수도 있다. 가급적 발생할 수 있는 유일한 충돌들은 트리에서 같은 leaf에 있는 오브젝트들 사이에 있다. 우리는 간단히 차례로 트리의 각 leaf를 고려할 수 있다. 만약 그것이 적어도 그것 내에서 두 개의 포함된 오브젝트들을 가진다면, 그러면 그러한 오브젝트들의 모든 쌍의 조합들은 세부적인 점검을 위해 fine collision detector로 보내질 수 있다.
만약 우리가 BSP tree의 leaves에서 bounding volume hierarchy를 배치한다면, 우리는 그러고나서 각 hierarchy에 대해 coarse collision detection algorithm을 호출할 수 있다. 이 경우에, 우리는 두 개의 coarse collision detection step을 가진다.
만약 많은 오브젝트들, 몇 가지 큰 오브젝트들, 또는 많은 분할 평면들이 있따면, 그러면 트리의 수 많은 branches에서 한 오브젝트를 갖는 것은 엄청나게 큰 자료구조와 좋지 않은 성능으로 이끌 수 있다. 그 앞의 알고리즘은 겹치는 오브젝트들이 오직 하나의 자식노드에 보내지거나, 부모 노드와 함께 한 리스트에 유지될 때, 충돌 탐지를 하기 위해 수정되어질 수 있다. 좀 더 포괄적인 세부사항을 위해서 Ericson [2005]를 보아라.
BSP trees는 렌더링 엔진에서 흔하고, bounding volume hierarchies에 관해, 너는 너의 물리 시스템에 대해 존재하는 구현을 사용할 수 있을지도 모른다. 그것들은 level geometry와 game level사이에서 충돌을 탐지하기 위해 또한 흔히 사용된다. 그림 12.9는 game level의 부분에 대해 작은 BSP를 보여준다.
BSP는 그것의 leaves에 오브젝트들을 보유하지 않지만, 오히려 그 오브젝트가 충돌하는지 아닌지에 대한 boolean indication이 있다. 한 오브젝트는 각 평면에 대해 검사된다, 재귀적으로. 만약 그것이 평면을 교차한다면, 두 자식들은 체크된다; 만약 그렇지 않다면, 오직 하나만이 체크된다, 이전처럼. 만약 그 오브젝트가 충돌로서 표시되는 leaf에 도달한다면, 우리는 충돌이 발생했다는 것을 안다.
대부분의 충돌들은 움직이는 오브젝트들과 level geometry사이에서 발생하기 때문에 (일반적으로 변하지 않거나 전혀 움직일 수 없는), 그 BSP 접근법은 매우 유용하다. 불행하게도, 복잡한 전처리 단계가 level geometry로부터 BSP를 구성하기 위해 요구된다.
12.4.2 Oct-Trees and Quad-Trees
Oct-trees와 quad-trees는 BSP와 BVH 둘 다에 대해 많은 유사성을 가진 spatial data structures이다. Quad-trees는 2차원을 위해 사용되고 (또는 대부분의 오브젝트들이 땅위에 있는 3차원), 그리고 3차원을 위해 oct-trees가 사용된다. 많은 3D 게임에서, quad-tree는 oct-tree만큼 유용하고, 덜 메모리를 취한다. 그래서 나는 그것에 처음에 집중할 것이다.
quad-tree는 4개의 후손들을 가진 각각의 노드들의 한 집합으로 구성된다. 그 노드는 공간을 한 개의 점에서 교차하는 4개의 지역으로 분할한다. 그것은 BSP tree에서 세 개의 노드로 생각되어질 수 있다. 비록 분할되는 방향이 항상 world axes와 정렬될지라도. 한 node는 vector position과 4개의 자식들로 나타내어질 수 있다:
struct QuadTreeNode { glm::vec3 position; QuadTreeNode child[4]; };
4개의 지역에 대해 한 오브젝트가 어떤 곳에 있는지를 검증하는 것은 그것들의 위치 벡터들의 대응되는 컴포넌트들을 비교하는 간단한 일이다. (1,4,5)에 있는 한 오브젝트와, (2,0,0)에 있는 QuadTreeNode에 대해, 우리는 그것이 top left area에 있다는 것을 안다, 그림 12.10에서 보여지듯이, 왜냐하면 그 오브젝트의 x좌표가 그 노드의 좌표보다 작고, 그 z좌표는 더 크기 때문이다. 우리는 배열에서 다음의 간단한 알고리즘으로 어떤 자식을 사용할지 계산할 수 있다:
struct QuadTreeNode { // ... other code as before unsigned int getChildIndex(const glm::vec3& object) { unsigned int index; if(object.x > position.x) index += 1; if(object.z > position.z) index += 2; return index; } }
여기에서 각 area에 대한 인덱스들은 그림 12.10에 보여지는 그것들과 부합한다.
oct-tree는 정확히 같은 방식으로 작동하지만, 8개의 자식을 갖고, 한 오브젝트가 어디에 위치해 있는지를 결정하기 위해 세 개의 벡터 컴포넌트의 각각에 대해 비교를 수행한다:
struct OctTreeNode { glm::vec3 position; OctTreeNode child[8]; unsigned int getChildIndex(const glm::vec3& object) { unsigned int index; if(object.x > position.x) index += 1; if(object.y > position.y) index += 2; if(object.z > position.z) index += 4; return index; } }
이론으로, 각 노드에 대한 position vector가 어디에서 든지 설정되어질 수 있을지라도, quad- and oct-trees에서 각 노드가 그것의 부모를 절반으로 나누는 것이 흔하다. 게임에서 모든 오브젝트들을 커버하는 axis-aligned bounding box로 시작하여, 그 top-level node는 이 박스의 중심점에 위치해 있는다. 이것은 효과적으로 같은 크기의 4개의 박스들을 생성한다 (quad-tree에 대해, oct-tree에 대해서는 8개). 이러한 박스들 각각은 한 노드로 나타내어지고, 그것의 위치는 그 박스의 중심점에 있고, 같은 크기의 좀 더 많은 4개의 박스들을 만든다. 그래서 hierarchy 아래로 내려간다.
이 절반으로 나누는 것을 사용하는 것에 대한 두 가지 이점이 있다. 첫 째로, node 자료구조에서 position vector를 제거하는 것이 가능하고, 트리를 재귀적으로 내려가는 동안 fly에서 point를 계산하는 것이 가능하다. 이것은 메모리를 절약한다.
둘 째로, 그것은 우리가 각 노드의 분할점을 배치할 최상의 장소를 찾는 어떤 계산을 할 필요가 없다는 것을 의미한다. 이것은 초기 hierarchy를 구성하는 것을 더 빠르게 만든다.
재귀의 방법과 각 노드에서 자식의 개수외에도, quad- and oct-trees는 BSP tree와 정확히 같은 방식으로 작동한다. 충돌을 결정하기 위해 BSP tree와 함께 작동하는 알고리즘들은 quad- or oct- tree에 대해서 같다. 그러나 그 테스트는 더 간단하고, 재귀할 좀 더 가능한 자식들이 있다.
또한 BSP tree와 함께, 우리는 분할하는 선을 겹치는 오브젝트들을 어디에 넣어야 할지를 결정해야 한다. 이전 코드 예제에서, 나는 그 오브젝트들이 그것의 중심을 포함하는 자식에 들어가도록 가정했다. 우리는 대신에 그 오브젝트를 그것이 닿는 모든 자식들에 배치할 수 있다, 우리가 BSP tree에 대해 했던 것 처럼, 그리고 같은 간단한 coarse collision detection을 가질 수 있다: 같은 leaf에 있는 오브젝트들만이 가급적 충돌할 수 있다.
Quad-trees는 특히 outdoor scenes에 대해 유용하다. 그리고 거기에서 오브젝트들은 landscape에 배치된다. 그것들은 indoor games에 대해 BSP trees 보다 덜 유용하다. 왜냐하면 그것들은 level의 벽과 충돌 탐지에 대해 쉽게 사용될 수 없기 때문이다. 그리고, BSP trees처럼, 그것들은 렌더링을 최적화하는데 종종 사용되고, 너가 사용하는 어떤 존재하는 렌더링 엔진의 일부가 될지도 모른다.
그것들이 실제로 BSP와 유사하기 때문에, 그것들로 작업하는 코드를 반복하는 것을 피할 것이다. CD에, BSP, quad-trees, and oct-trees에 대한 완전한 구현이 있다. (코드 없음)
12.4.3 Grids
우리의 끝에서 두 번째 공간 자료 구조는 quad-tree의 아이디어를 더 취한다. 만약 몇 가지 레이어가 깊은 절반으로 나눈 quad-tree의 분할된 패턴을 그린다면, 우리는 그것이 한 grid를 형성하는 것을 본다 (그림 12.11). regular grid를 나타내기 위해, 트리 자료구조를 사용하기 보다는, 우리는 간단히 regular grid를 사용할 수 있다.
한 grid는 어떤 수의 오브젝트든 있을지도 모르는, 위치의 배열이다. 그것은 트리 자료구조가 아니다. 왜냐하면 그 위치는 직접적으로 오브젝트의 위치로부터 결정될 수 있기 때문이다. 이것은 한 오브젝트가 트리에 재귀적으로 내려가는 것보다 더 빠르게 찾도록 해준다.
그 grid는 다음의 구조를 갖는다:
struct Grid { unsigned int xExtent; unsigned int zExtent; ObjectSet* locations; // An array of size (xExtent * zExtent) glm::vec3 origin; glm::vec3 oneOverCellSize; };
여기에서 xExtent와 zExtent는 그리드의 각 방향에서 셀들의 개수를 저장한다; oneOverCellSize 벡터의 x와 z 컴포넌트들은 1을 각 셀의 크기로 나눈 것을 포함한다 (우리는 다음의 알고리즘을 가속화하기 위해 실제 사이즈 보다는 1/value 를 사용한다); 그 y 컴포넌트는 일반적으로 1로 설정된다; origin은 grid의 원점이다. 그 그리드는 충분히 커야만 한다. 그 게임에서의 어떤 오브젝트든 그것 내에 포함되어야 하기 때문이다.
한 오브젝트의 중심점이 포함되는 위치를 결정하기 위해, 우리는 간단한 알고리즘을 사용한다:
struct Grid { // ... Previous code as before def getLocationIndex(const glm::vec3& object) { glm::vec3 square = object * oneOverCellSize; return (unsigned int)(square.x) + xExtent *(unsigned int)(square.z); } };
이 코드 스니펫에서, 우리는 처음에 그 오브젝트가 어떤 square 안에 있는지를 찾는다. (우리는 1/value를 곱하여 그 분할을 한다). 이것은 우리에게 square라고 불려지는 벡터에서 각 컴포넌트에 대한 floating-point value를 준다. 이러한 floating-point 값들은 unsigned integers로 변환될 필요가 있따. 그 integer values는 그러고나서 반환될 grid array의 index를 찾기위해 사용된다.
BSP와 quad-trees에서 처럼, 우리는 한 quare의 edge에 겹치는 오브젝트들로 무엇을 할 지 결정할 필요가 있따. 그것들을 간단히 한 cell 또는 다른 것에 배치하는 것이 가장 흔하다. 비록 그것들을 그들이 겹치는 모든 셀에 배치하는 것이 가능할지라도. 이전 처럼, 후자는 가능한 충돌의 집합을 결정하는 것을 더욱 빠르게 하지만, 상당히 더 많은 메모리를 먹을 수 있다. 나는 좀 더 복잡한 경우로 돌아가기 전에 더 간단한 경우를 볼 것이다.
각 셀이 그 셀과 겹치는 모든 오브젝트들을 포함하는 grid에서, 충돌의 집합은 매우 간단하게 생성될 수 있다. 두 오브젝트들은 만약 그것들이 그리드에서 같은 위치를 차지한다면 충돌에 있을 수 있다. 우리는 간단히 한 개 이상의 오브젝트를 포함하는 각 위치를 볼 수 있고, 가능한 충돌에 대해 각 pair를 체크할 수 있다.
tree 기반의 표기와 다르게, 우리가 한 위치가 두 개 이상의 오브젝트들을 포함하는 지를 볼 수 있는 유일한 방법은 그것을 확인하는 것이다. 반면에 트리에 대해서, 우리는 각 노드에 오브젝트들의 개수를 저장했었고, 완전히 충돌을 생성할 수 없는 branches들을 놓칠 수 있다. 그래서 여기에서 어떠한 속도 향상이 없다.
가능한 충돌에 대해 수천 개의 위치를 찾는 것을 피하기 위해 (작은 수의 오브젝트들은 시간이 더 걸릴지도 모른다, 만약 우리가 coarse collision detection을 전혀하지 않는 것보다), 우리는 한 개 이상의 오브젝트를 포함하는 그리드 자료구조에서 위치들의 한 집합을 만들 수 있다. 우리가 한 오브젝트를 셀에 추가할 때, 만약 그 셀이 이제 두 개의 오브젝트들을 포함한다면, 그것은 occupied list에 추가되어야만 한다.
마찬가지로, 우리가 셀로부터 한 오브젝트를 제거할 때, 만약 그 셀이 이제 그냥 한 개의 오브젝트만 포함한다면, 그것은 리스트로부터 제거되어야만 한다. 충돌의 완전한 집합을 결정하는 것은 그러면 그 occupied list를 확인하고, pair-wise combinations를 fine-grained collision detector로 넘기는 문제이다.
만약 오브젝트들이 한 셀 이상의 크기라면, 그것들은 그리드에서 많은 셀들을 차지할 필요가 있을 것이다. 이것은 매우 많은 메모리 요구사항을 이끌 수 있다. 많은 낭비된 공간과 함께. PC에서 돌아가는 합리적인 크기의 게임 level에 대해, 이것은 문제가 아닐지도 모르지만, large levels or memory 제약 콘솔에 대해서, 그것은 받아들여지지 않을 수 있다.
만약 우리가 한 오브젝트를 그냥 한 grid cell에만 배치한다면 (그것의 중심이 cell에 보통 있는), 그러면 그 coarse collision detection routine은 이웃한 셀에 있는 오브젝트와의 충돌만을 체크할 필요가 있다. 셀과 같은 크기의 오브젝트에 대해, 그것은 8개로 된 가능한 한 집합으로부터 세 개의 이웃을 최대한으로 검사할 필요가 있다 (그림 12.12 참조). 그러나 이것은 급속히 증가된다. 셀의 크기가 4배가 더 큰 오브젝트에 대해, 가능한 24개의 이웃으로부터 15개가 고려될 필요가 있다. 정확한 이웃을 체크하는 코드를 쓰는 것은 가능하지만, 매우 큰 오브젝트들에 대해, 그것은 많은 낭비되는 노력을 포함한다.
hybrid data structure는 이 상황에 유용할 수 있다. 그리고 그것은 다양한 다른 크기의 그리드를 사용한다. 그것은 보통 "multi-resolution map"이라고 불려진다.
12.4.4 Multi Resolution Maps
multi-resolution map은 증가된 cell sizes가 있는 grdis의 집합이다. 오브젝트들은 그리드들 중의 하나에 추가된다, single grid와 같은 방식으로. 그 grid는 그 오브젝트의 크기를 기반으로 선택된다: 그것은 cells가 그 오브젝트보다 더 큰 가장 작은 그리드가 될 것이다.
종종 그 그리드들은 선택되는데, 각각이 이전의 것의 크기보다 4배나 큰 셀을 갖도록 하기 위해서이다 (쯕, 각 셀에 대해 너비와 길이가 두배인). 이것은 multi-reesolution map이 직접적으로 한 오브젝트를 어떤 그리드에 추가할 지를 계산하는 것을 허용한다.
coarse collision detection 동안에, 그 amp은 single grid algorithm의 수정된 버전을 사용한다. 각 grid에 대해, 그것은 각 오브젝트와 같은 또는 이웃한 셀에 오브젝트 사이의 잠재적인 collision을 만든다 (오브젝트들이 그들보다 작은 grid cell에 있을 수 없기 때문에 이제 체크 할 세 개의 이웃들이 최대 이다). 게다가, 그 오브젝트는 중첩되는 더 큰 셀의 그리드들에서 모든 오브젝트들에 대해 체크되어야 한다. 우리는 더 작은 셀의 그리드에 있는 오브젝트들에 대해서는 확인할 필요가 없다. 왜냐하면 그 작은 오브젝트들은 더 큰 오브젝트들에 대해 검사하는데 책임이 있기 때문이다.
맵에 있는 각 grid에 대해, 우리는 그리드 자료구조를 occupied cells의 같은 집합과 함께 사용할 수 있다. 그러나, 우리는 active list에 한 셀을 추가할 필요가 있는데, 만약 그것이 어떤 오브젝트든지 포함한다면 (왜냐하면 그것들이 이웃과 접촉할지도 모르기 때문이다).
12.5 Summary
Collision detection은 복잡하고 시간이 소모되는 프로세스이다. 그것을 철저히 하는 것은 실시간 물리에 대해 너무 오래걸린다. 그래서 몇 가지 최적화가 필요하다.
우리는 충돌 탐지를 두 단계로 분리할 수 있다: 가능한 접촉들을 찾는 coarse phase (몇몇은 충돌이 아닌 것으로 결과가 날 수 있지만, 그것은 결코 한 충돌을 놓쳐서는 안된다); 그리고 세부적으로 잠재적인 충돌을 체크하고 contact properties를 처리하는 fine-grained phase.
Coarse collision detection은 오브젝트들을 구나 박스같은 간단한 bounding volume에 감싸고, 각 collision volume에 대해 체크를 수행하여 작동한다. 그 collision volumes는 hierarchy에서 배치될 수 있고, 그것은 전체 brances가 제외도록 허용한다, 또는 공간 자료 구조에서도, 그것은 근처의 오브젝트들이 함께 접근되는 것을 허용한다.
다른 메소드들 사이에 tradeoffs가 있고, 많은 경우에 몇 가지들을 합칠 잠재성이 있다. 고려해야 할 가장 중요한 요소들 중의 하나는 그 렌더링 엔진이 그것들이 그려져야할지를 결정하기 위해 오브젝트들을 어떻게 관리할지 이다. 만약 너의 renderer가 준비된 한 시스템이라면, 그것을 사용하여 메모리를 절약하기 위해 채태갛는 것이 충고할만 하다.
그 coarse phase의 결과는 좀 더 상세하게 체크될 필요가 있는 가능한 접촉의 한 집합이다. 우리는 다음 챕터에서 이러한 checks를 수행하는데 필요한 알고리즘들을 볼 것이다.
댓글 없음:
댓글 쓰기