Real Time Collision Detection - Chapte 4: Bounding Volumes (1)
Chapter4. Bounding Volumes (1)
4.1 Desirable BV Characteristics
모든 기하학적 오브젝트들이 효과적인 BV로서 역할을 하는 것은 아니다. BV에 대한 바람직한 특성들은 다음을 포함한다:
- Inexpensive intersection tests
- Tight fitting
- Inexpensive to compute
- Easy to rotate and transform
- Use little memory
BV 뒤에 있는 주된 아이디어는 비싼 geometric tests에 앞서서 그 테스트가 빠르게 끝나도록 하는, 소위 "early out"인 비싼
테스트를 선행하게 하는 것이다. 값 싼 overlap tests를 지원하기 위해서, BV는 또한 가능한한 tight fitting해야한다.
이것은 tightness와 intersection test cost 사이의 trade-off를 만들어낸다. 그 intersection test는 필수적으로 같은 유형의
volumes에 대한 비교를 다루지 않지만, 또한 BV의 다른 종류에 대해 테스트를 할지도 모른다. 부가적으로, 테스팅은
point inclusion, ray intersection with the volume, and intersection with planes and polygons같은
queries를 포함할지도 모른다.
BV는 일반적으로 런타임이 아닌 전처리 단계에서 계산됩니다. 그럼에도 불구하고 그들의 구성이 자원 구축 시간에
부정적인 영향을 주지 않는 것이 중요하다. 그러나 일부 경계 볼륨은 포함된 객체가 이동할 때 런타임에 재 정렬되어야한다.
이를 위해 BV가 재정렬을 계산하는데 비용이 많이 든다면 BV를 처음부터 다시 계산하는 것이 바람직하다.
BV는 기하학에 저장되기 때문에 기하학에 메모리를 추가하는 것이 이성적이다. 단순한 기하학적 모양은 메모리 공간을
덜 필요로 한다. 원하는 속성 중 상당 부분이 상호 배타적이므로 특정 BV이 모든 상황에 가장 적합한 선택이 아니다.
대신 가장 적합한 옵션은 몇 가지 서로 다른 BV을 테스트해 해당 응용 프로그램에 가장 적합한 볼륨을 경정하는 것이다.
그림 4.2는 가장 일반적인 BV 유형 중 5가지 간의 절충 사항 중 일부를 보여준다. 더 나은 범위, 더 나은 도려 내기,
빠른 테스트 및 적은 메모리에 관한 주어진 순서는 절대적인 지침이 아닌 거친 것으로 간주되어야한다.
이 장에서 다루는 첫 번째 볼륨은 다음 섹션에서 설명하는 축 정렬 경계 상자이다.
4.2 Axis-aligned Bounding Boxes (AABBs)
축 정렬 경계 상자(AABB)는 가장 일반적인 경계 용적 중 하나이다. 면의 법선이 주어진 좌표계의 축과 항상 평행하도록
면을 향하게해 직사각형의 6면체 상자로 분류된다. AABB의 가장 큰 특징은 개별 좌표 값을 직접 비교하는 빠른 중복 검사이다.
AABB에는 세 가지 공통적인 표현이 있다. 하나는 각 축을 따라 최소 및 최대 좌표 값이다:
1 2 3 4 5 | // region R = (x, y, z) | min.x<=x<=max.x, min.y<=y<=max.y, min.z<=z<=max.z struct AABB { Point min; Point max; }; | cs |
이 표기는 공간의 BV 영역을 두 개의 반대되는 모서리 점 사이의 것으로 명시한다 : min and max. 또 다른 표기는
minimum corner point min과 이 코너로부터의 width 또는 diameter extents dx, dy, dz로서 된다:
1 2 3 4 | // region R = (x, y, z) | min.x<=x<=min.x+dx, min.y<=y<=min.y+dy, min.z<=z<=min.z+dz struct AABB { Point min; float d[3]; // diameter or width extents (dx, dy, dz) }; | cs |
그 마지막 표기는 AABB를 중앙점 C와 그것의 축을 따라서 halfwidth extents or radii rx, ry, rz로서 명시한다:
1 2 3 4 5 | // region R = (x, y, z) | |c.x-x|<=rx, |c.y-y|<=ry, |c.z-z|<=rz struct AABB { Point c; // center point of AABB float r[3]; // radius or halfwidth extents (rx, ry, rz) }; | cs |
저장소 요구 사항 측면에서 중심 반경 값은 중심 위치 값보다 적은 비트 수로 저장 될 수 있기 때문에 가장 효율적이다.
약간의 차이는 있지만 min-width 표현의 width 값에 대해서도 마찬가지이다. 최악은 6개 값 모두가 동일한 정밀도로
저장되어야하는 최소-최대 표현이다. 저장소를 줄이려면 여기에 사용된 것처럼 부동 소수점을 나타내는 AABB를 정수로
나타내야한다. 오브젝트가 단지 이동만으로 움직이는 경우, 6개의 파라미터 중 3개만 업데이트해야하기 때문에 후자의
두 표현을 업데이트하는 것이 min-max 표현보다 저렴하다. 중심 반경 표현의 유용한 특징은 바운딩 구로도 테스트
할 수 있다는 것이다.
4.2.1 AABB-AABB Intersection
AABB 간의 중첩 테스트는 표현과 상관없이 간단하다. 두 개의 AABB는 세 축 모두에서 겹치는 경우에만 겹치며,
각 차원의 해당 범위가 해당 축의 간격으로 표시된다. 최소-최대 표시의 경우, 이 간격 겹침 테스트는 다음과 같다:
1 2 3 4 5 6 7 8 9 | int TestAABBAABB(AABB a, AABB b) { // Exit with no intersection if separated along an axis if (a.max[0] < b.min[0] || a.min[0] > b.max[0]) return 0; if (a.max[1] < b.min[1] || a.min[1] > b.max[1]) return 0; if (a.max[2] < b.min[2] || a.min[2] > b.max[2]) return 0; // Overlapping on all axes means AABBs are intersecting return 1; } | cs |
최소 너비 표현은 덜 매력적이다. 오버랩 테스트는 경제적인 방법으로 작성된 경우에도 수행된 작업 수와 관련해
첫 번째 테스트와 비교되지 않는다:
1 2 3 4 5 6 7 8 | int TestAABBAABB(AABB a, AABB b) { float t; if ((t = a.min[0] - b.min[0]) > b.d[0] || -t > a.d[0]) return 0; if ((t = a.min[1] - b.min[1]) > b.d[1] || -t > a.d[1]) return 0; if ((t = a.min[2] - b.min[2]) > b.d[2] || -t > a.d[2]) return 0; return 1; } | cs |
마지막으로, 중심 반경 표현은 다음 중첩 테스트를 초래한다:
1 2 3 4 5 6 7 | int TestAABBAABB(AABB a, AABB b) { if (Abs(a.c[0] - b.c[0]) > (a.r[0] + b.r[0])) return 0; if (Abs(a.c[1] - b.c[1]) > (a.r[1] + b.r[1])) return 0; if (Abs(a.c[2] - b.c[2]) > (a.r[2] + b.r[2])) return 0; return 1; } | cs |
현대 아키텍처에서 Abs() 호출은 일반적으로 단 하나의 명령어로 변환된다. 그렇지 않으면 함수는 단순히 부동 소수점 값의
2진 표현의 부호 비트를 제거해 효과적으로 구현할 수 있다. AABB 필드가 부동 소수점 대신 정수로 선언되면, 다음과 같이
centerradius 표현에 대한 대체 테스트가 수행 될 수 있다. 정수의 경우 두 범위 [A,B]와 [C,D] 사이의 중첩은 다음 식
1 | overlap = (unsigned int)(B - C) <= (B - A) + (D - C); | cs |
C>B일 때 부호 없는 언더 플로를 강요하면 왼쪽이 매우 큰 값이 되어 표현식을 거짓으로 만든다. 강제 오버플로는
절대 값 함수 호출을 효과적으로 대체하는 역할을 하며 중심 반경 표현 테스트는 다음과 같이 작성된다:
1 2 3 4 5 6 7 8 | int TestAABBAABB(AABB a, AABB b) { int r; r = a.r[0] + b.r[0]; if ((unsigned int)(a.c[0] - b.c[0] + r) > r + r) return 0; r = a.r[1] + b.r[1]; if ((unsigned int)(a.c[1] - b.c[1] + r) > r + r) return 0; r = a.r[2] + b.r[2]; if ((unsigned int)(a.c[2] - b.c[2] + r) > r + r) return 0; return 1; } | cs |
integers로 작업하면 다른 구현 트릭이 가능하며 그 중 많은 것은 아키텍처에 따라 다르다. SIMD 명령어가 존재한다면 일반적으로
AABB 테스트가 단지 몇 가지 명령어 코드로 구현 될 수 있다. 마지막으로, 대량의 오버랩 테스트를 수행해야하는 충돌 감지 시스템에서
테스트가 수행 될 가능성에 따라 테스트를 주문할 가치가 있다. 예를 들어, 조작이 거의 평평한 xz평면에서 크게 발생하면 y좌표 테스트는
가장 차별적이므로 마지막으로 수행해야한다.
4.2.2 Computing and Updating AABBs
BV는 보통 그것들이 bound하는 오브젝트들의 local model space에서 명시된다. (world space에서 일지도 모른다)
두 BV간에 오버랩 쿼리를 수행하려면 볼륨을 공통 좌표 시스템으로 변환해야한다.
이 선택은 BV를 모두 월드 공간으로 변환하고 하나의 BV를 다른 볼륨의 로컬 공간으로 변환하는 것 사이에 있다.
로컬 공간으로 변형 할 때의 한 가지 이점은 월드 공간으로의 변형 작업량의 절반을 수행해야한다는 것이다.
또한, 종종 월드 공간으로 변환하는 것보다 더 좁은 BV을 생성한다. 그림 4.4는 그 개념을 보여준다.
재 계산된 객체 A와 B의 AABB는 월드 공간에서 중첩된다. (그림4.4.a) 그러나 객체 B의 공간에서는 객체가 분리되어
있는 것으로 나타났다. (그림 4.4c) 정확성은 하나의 BV를 다른 볼륨의 로컬 공간으로 변환하는 또 다른 강제적인 이유이다.
월드 공간 테스트는 두 대상을 원점에서 멀리 이동시킬 수 있다. BV의 로컬 근원 좌표를 변환하는 동안 변환을 추가하는
동작은 원래 값의 많은 (또는 심지어 모든) 비트 정밀도를 잃어 버릴 수 있다. 국부적인 공간 테스트의 경우,
객체는 원점 근처에 유지되고 계산에서 정확도가 유지된다. 그러나 변형된 객체가 원점 세계 중심으로 변환되도록
변환을 조정하면 정확도를 유지할 수 있다. 갱신된 BV이 시간 단계동안 일시적으로 캐시 될 수 있으면 월드 공간으로의
변환이 흥미롭습니다. 변환 후 BV를 캐싱함으로써 모든 바운딩 볼륨을 주어진 공간으로 단 한 번 변환해야한다.
월드 공간으로 변환 할 때 모든 BV이 동일한 공간으로 변환되기 때문에 오브젝트가 여러 번 중첩되는지 검사되는
상황에서 승리가 된다. 반대로 업데이트 된 경계 보륨을 캐싱하는 것은 다른 경계 볼륨의 로컬 공간으로 변환 할 때
전혀 도움이 되지 않는다. 모든 변환에는 새 객체 또는 새 대상 좌표 시스템이 포함되기 때문이다.
업데이트된 경계 볼륨의 캐싱은 경계 볼륨 표현의 대부분 필드가 업데이트 중에 변경되므로 필요한 저장 공간을
거의 두 배로 늘리는 단점이 있다. sphere 또는 convex hull과 같은 일부 BV는 특정 방향으로 제한되지 않으므로
자연스럽게 모든 좌표계로 변형된다. 결과적으로, 정렬되지 않거나 (자유롭게) 지향된 경계 볼륨이라고 한다.
대조적으로 정렬된 BV(예:AABB)는 자신이 가정할 수 있는 방향으로 제한된다.
정렬된 BV는 모션 중에 객체 회전으로 인해 정렬되지 않을 때 다시 정렬되어야한다. AABB를 업데이트하거나
재구성하려면 다음 네 가지 공통된 전략이 필요하다:
- 항상 객체를 둘러싼 고정 크기의 느슨한 AABB 활용
- 원래의 점 집합으로부터 긴밀한 동적 재구성 계산
- 힐 클라이밍을 이용한 타이트한 다이내믹 재구성 계산
- 회전된 AABB로부터 근사 동적 재구성 계산
다음 네 섹션은 이러한 접근법을 보다 자세히 설명한다.
4.2.3 AABB from the Object Bounding Sphere
첫 번째 방법은 AABB를 어떤 방향으로든 포함 할 만큼 충분히 크게 만들어서 AABB의 모양을 바꿀 필요를 완전히 회피한다.
AABB를 포함하는 이 고정 크기의 객체는 포함된 객체 A의 경계 영역의 경계 상자로 계산된다.
경계 구체는 차례로 A가 회전하는 피벗 점 P의 가운데에 배치된다. 반경 r은 이 중심에서 가장 멀리있는 오브젝트 정점까지의
거리이다. (그림 4.5 참조) 대상 피벗 P가 대상의 중심에 있는지 확인해 구면 반지름이 최소화된다.
이 표현의 이점은 업데이트하는 동안 이 AABB가 (바운드된 객체에 적용된 동일한 translate를 통해) translate되어야하고,
객체 회전은 완전히 무시될 수 있다. 그러나 경계 구 자체도 이 속성을 갖는다. 따라서, 이 경우에는 BV이 경계 볼륨의
잠재적인 더 나은 선택으로 간주되어야한다.
4.2.4 AABB Reconstructed from Original Point Set
이 섹션에서 설명한 업데이트 전략은 AABB가 좌표계 축과 함께 다시 정렬될 때 동적으로 크기를 조정한다.
단단히 고정된 바운딩 박스의 경우 바운드된 객체의 기본 기하학을 검사하고, 6개의 모든 좌표 축에서 극한 정점을 찾아
상자 경계를 설정한다. 직접적인 접근은 모든 정점을 반복하며 방향 벡터를 따라 가장 가까운 정점을 추적한다.
이 거리는 정점 벡터를 방향 벡터에 투영해 계산할 수 있다. 비교를 위해 방향 벡터를 정규화 할 필요는 없다.
이 절차는 방향 벡터를 따라 가장 먼 지점과 가장 먼 지점을 모두 찾는 다음 코드에 설명되어 있다:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 | // Returns indices imin and imax into pt[] array of the least and // most, respectively, distant points along the direction dir void ExtremePointsAlongDirection(Vector dir, Point pt[], int n, int *imin, int *imax) { float minproj = FLT_MAX, maxproj = -FLT_MAX; for (int i = 0; i < n; i++) { // Project vector from origin to point onto direction vector float proj = Dot(pt[i], dir); // Keep track of least distant point along direction vector if (proj < minproj) { minproj = proj; *imin = i; } // Keep track of most distant point along direction vector if (proj > maxproj) { maxproj = proj; *imax = i; } } } | cs |
n이 클 때, 이 O(n) 프로시저는 런타임시 수행하면 비용이 비쌀 수 있다. 정점 데이터의 사전 처리는 프로세스 속도를 높일 수 있다.
여분의 데이터를 추가하지 않는 간단한 접근법은 객체의 볼록한 선체에 있는 정점만이 경계 체적 모양을 결정하는데 기여할 수 있다는
사실에 기반한다. (그림 4.6) 전처리 단계에서 객체의 볼록 선체에 있는 모든 k개의 꼭지점이 나머지 모든 꼭지점 앞에 오도록 저장된다.
그런 다음, 이 첫번째 정점만 k를 조사해 단단한 AABB를 구성 할 수 있다. 일반적인 오목한 볼륨의 경우 이것은 승리가 될 것이다.
그러나 이미 볼록한 선체에 모든 정점이 있는 블록 볼륨은 개선되지 않을 것이다ㅣ.
추가된 전용 사전 계산 검색 구조를 사용해 극한 정점을 찾는 작업을 O(logn)시간에 수행할 수 있다.
예를 들어, Dobkin-Kirkpatrick 계층 구조를 이 용도로 사용할 수 있다. 그러나 이러한 구조에 필요한 추가 메모리와 이를 통과하는
오버헤드로 인해 대부분의 상황에서는 잔인한 것으로 간주되어야한다. 확실하게 경계의 경계가 중요하다면 AABB보다 더 엄격한
경계가 고려되어야한다.
4.2.5 AABB from Hill-climbing Vertices of the Object Representation
AABB 재정렬 프로세스의 속도를 높이는 또 다른 방법은 정점의 인접한 정점을 빠르게 찾을 수 있는 객체 표현을 사용하는 것이다.
그러한 표현은 새로운 AABB를 정의하는 극단적인 꼭지점이 단순한 등반을 통해 위치 할 수 있게 한다. (그림 4.7)
각 축을 따라 최소 및 최대 범위 값을 추적하는 대신 6개의 정점 포인터가 유지된다. 이전과 같은 값에 해당하며, 이것들은
실제로 각 축 방향을 따라 물체의 (최대 6개의) 극한 꼭지점을 가리킨다. 힐 클라이밍 단계는 참조된 꼭지점을 이웃하는
꼭지점과 비교해 이전과 같은 방향으로 여전히 극단적인지 확인한다. 그렇지 않은 것들은 더 극단적인 이웃들 중 하나로
대체되고 테스트는 그 방향의 극단 정점이 발견될 때까지 반복된다.
따라서 지역 최소치에 머물러 서지 않으려면 등산 과정에서 물체가 볼록해야한다. 이러한 이유 때문에, 산정되지 않은
물체의 사전 계산된 볼록 선체에 언덕 상승이 수행된다. 전반적으로, 단단한 AABB의 재 계산은 예상된 일정 시간 작업이다.
hill-climbing 과정에서 실제로 조사될 때만 꼭지점을 변형해야지 계산 작업이 크게 줄어든다.
그러나 x, y, z 구성 요소 중 하나만 주어진 축을 따라 극점 꼭지점을 찾는데 사용된다는 사실을 알면 더욱 향상될 수 있다.
예를 들어, +x축을 따라 극점을 찾을 때 변환된 꼭지점의 x 구성 요소만 계산해야한다. 따라서 변형 비용은 2/3으로 감소한다.
이 hill-climbing 방법을 강력하게 구현하려면 몇 가지 주의를 기울여야한다. 동일 평면 꼭지점으로 둘러싸인 축을 따라
극한 꼭지점만 고려해라. 객체가 나머지 두 축 중 하나에 대해 180도 회전하면 꼭지점은 같은 축을 따라 반대 방향을 따라
극단이 된다. 그러나, 그것은 동일 평면의 정점에 의해 둘러쌰여 있기 때문에, 등산 단계는 보다 좋은 이웃하는 정점을 찾을
수 없으므로 실제로는 가장 작은 방향의 정점으로 끝난다. 견고한 구현은 이러한 상황을 특별히 고려해야한다.
4.2.6 AABB Recomputed from Rotated AABB
네 개의 재배치 방법 중 마지막으로 가장 일반적인 방법은 회전된 AABB 자체를 새로운 AABB로 간단하게 랩핑하는 것이다.
이것은 타이트한 AABB가 아닌 근사치를 생성한다. 결과 AABB가 시작된 AABB보다 크므로 근사 AABB가 원래 로컬 공간 AABB의
회전으로부터 계산되는 것이 중요하다. 그렇지 않은 경우 이전 시간 단계의 rotate AABB에서 반복해 다시 계산하면 AABB가 무기한 증가한다.
회전 행렬 M의 영향을 받은 축 정렬 바운딩 박스 A'를 생각해보겠다. 그러면 어떤 방향에서 바운딩 박스 A'가 생긴다.
회전 행렬 M의 3개 열(또는 행)은 A의 월도 좌표 축을 로컬 좌표계에 제공한다.
(벡터가 열 벡터이고 행렬의 오른쪽에서 곱해진 경우 M의 열이 축이다. 대신 행렬의 왼쪽에서 벡터가 행 벡터로 곱해지면 M의 행이 축이다.)
A'가 min-max 표현을 사용해 주어지고, M이 열 행렬이라고 가정해보자. A를 경계짓는 축 정렬된 경계 상자 B는 A의 8개의 회전된 정점을
월드 좌표 축에 투영해 형성된 범위 간격으로 지정된다. 예를 들어, B의 x 익스텐트는 M의 열 벡터의 x 구성 요소만 제공한다.
그러므로 범위를 찾는 것은 M행을 가진 최소 및 최대 곱을 생성하는 정점을 찾는 것과 같다. B의 각 정점은 A에서 변환된 최소 또는 최대
값 3개를 조합한 것이다. 최소 범위 값은 더 작은 용어의 합계이고, 최대 범위는 큰 용어의 합이다.
변환은 새 경계 상자의 크기 게산에 영향을 미치지 않고 추가 할 수 있다. 예를 들어, x축의 최대 범위는 다음과 같이 계산할 수 있다:
1 2 3 | B.max[0] = max(m[0][0] * A.min[0], m[0][0] * A.max[0]) + max(m[0][1] * A.min[1], m[0][1] * A.max[1]) + max(m[0][2] * A.min[2], m[0][2] * A.max[2]) + t[0]; | cs |
min-max 표현을 사용해 rotateAABB에 대해 포괄적인 경계 상자를 계산하는 것은 다음과 같이 구현할 수 있다:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | // Transform AABB a by the matrix m and translation t, // find maximum extents, and store result into AABB b. void UpdateAABB(AABB a, float m[3][3], float t[3], AABB &b) { // For all three axes for (int i = 0; i < 3; i++) { // Start by adding in translation b.min[i] = b.max[i] = t[i]; // Form extent by summing smaller and larger terms respectively for (int j = 0; j < 3; j++) { float e = m[i][j] * a.min[j]; float f = m[i][j] * a.max[j]; if (e < f) { b.min[i] += e; b.max[i] += f; } else { b.min[i] += f; b.max[i] += e; } } } } | cs |
그에 상응해 중심 반경 AABB 표현의 코드는 [Arvo90]이 된다:
1 2 3 4 5 6 7 8 9 10 11 12 13 | // Transform AABB a by the matrix m and translation t, // find maximum extents, and store result into AABB b. void UpdateAABB(AABB a, float m[3][3], float t[3], AABB &b) { for (int i = 0; i < 3; i++) { b.c[i] = t[i]; b.r[i] = 0.0f; for (int j = 0; j < 3; j++) { b.c[i] += m[i][j] * a.c[j]; b.r[i] += Abs(m[i][j]) * a.r[j]; } } } | cs |
회전된 AABB에서 AABB를 계산하는 것은 자유 지향적인 경계 상자에서 AABB를 계산하는 것과 같다.
지향 경계 상자와 교차로 테스트에 대해서는 앞에서 자세히 설명한다. 그러나 여기에 제시된 방법과 제시된 방법 사이에서
분류되는 것은 객체로 지향된 경계 상자를 저장하지만 재구성된 AABB와 교차하는 방법이 될 것이다.
이렇게 하려면 방향 매트릭스를 저장하기 위한 추가 메모리가 필요하다.
또한, 배향된 경계 박스의 회전 행렬과 변환 행렬을 결합하기 위한 여분의 행렬-행렬 곱셈을 포함할 것이다.
이 솔루션의 이점은 재구성된 축 정렬 상자가 지향 상자로 시작해 훨씬 더 견고하다는 것이다.
축 정렬 테스트는 지향 상자의 본격적인 테스트보다 훨씬 저렴하다.