두 오브젝트들의 기하를 서로에 대해 충돌을 위해 직접적으로 테스트하는 것은 종종 매우 비싸다. 특히 오브젝트들이 수백개 또는 심지어 수천개의 폴리곤들로 구성되었을 때. 이 비용을 최소화 하기 위해서, object bounding volumes가 보통 geometry intersection test가 수행되기전에 중첩에 대해 테스트된다.
bounding volume(BV)는 단일의 simple volume인데, 좀 더 복잡한 특성을 가진 한 개 이상의 오브젝트들을 캡슐화한다. 그 아이디어는 더 간단한 volumes이 (박스와 구같은) 그것들이 bound시키는 복잡한 오브젝트들 보다 더 싼 overlap tests를 갖도록 하는 것이다. BV를 사용하는 것은 빠른 overlap rejection tests를 허용하게 하는데, 왜냐하면 BV에 대한 초기의 overlap query가 postiive result를 줄 때, complex bounded geometry에 대해 테스트가 필요하기 때문이다 (그림 4.1)
물론, 오브젝트들이 정말 겹칠 때, 이 부가적인 테스트는 연산 시간의 증가를 만들어낸다. 그러나, 대부분의 상황에서 오브젝트들은 일반적으로 그것들의 bounding volumes이 중첩되도록 충분히 가깝지 않다. 그러므로, BV를 사용하는 것은 중요한 성능의 이득을 만들어내고, 복잡한 오브젝트들을 이후의 테스트로부터 제거하는 것은 BV 테스트와 연관된 작은 부가적인 cost를 정당화 한다.
어떤 프로그램에 대해, BV intersection test는 그 자체로 충분한 충돌의 증거로서 역할을 한다. 그것이 그렇지 않은 곳에서, 일반적으로 여전히 그 포함된 오브젝트들을 쳐내는 것을 가치가 있다. BV가 겹치는데 포함된 폴리곤에 대해 테스트를 제한하기 위해서. 오브젝트 B의 폴리곤들에 대해 오브젝트 A의 폴리곤을 테스트하는 것은 일반적으로 O(n^2)의 복잡도를 가진다. 그러므로, 만약 테스트되어야 할 폴리곤의 개수가 가령, 절반으로 줄어든다면, 그 작업량은 75%로 줄어들 것이다. 챕터 6 bounding volume hierarchies에서, 어떻게 오브젝트들을 쳐내고 폴리곤 테스팅을 최소한으로 할 지에 대한 세부사항을 제공한다. 이 챕터에서, 이야기 되는 것은 BV의 쌍에 대한 테스트로 제한된다. 게다가, 여기에서 보여지는 테스트는 주로 같은 종류인데, 같은 유형의 BV가 서로에 대해 테스트된다는 점에서. 그러나, 동시에 BV의 여러가지 종류를 사용하는 것은 흔하지 않은 것은 아니다. 몇 가지 동종이 아닌 BV intersection tests는 다음 챕터에서 이야기 된다.
많은 기하학적 도형들은 bounding boxes로서 제안되어진다. 이 챕터는 가장 흔히 사용되는 모양에 집중한다; 이름 그대로, spheres, boxes, 그리고 convex hull-like volumes. 덜 흔한 BV에 대한 포인터들은 Section 4.7에서 제공된다.
4.1 Desirable BV Characteristics
모든 기하학적 오브젝트들이 효과적인 BV로서 역할을 하는 것은 아니다. BV에 대한 바람직한 특성들은 다음을 포함한다:
- 값 싼 intersection tests
- Tight Fitting
- 연산하기에 값 싼
- 회전하고 transform하기에 쉬운
- 적은 메모리를 사용
BV 뒤에 있는 주된 아이디어는 비싼 geometric tests에 앞서서 그 테스트가 빠르게 끝나도록 하는, 소위 "early out"인 덜 비싼 테스트를 선행하게 하는 것이다. 값 싼 overlap tests를 지원하기 위해, BV는 간단한 기하학적 도형을 가져야 한다. 동시에, early-out test를 가능한 효과적으로 하기 위해서, 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는 일반적으로 런타임에서 보다 전처리 단계에서 연산된다. 심지어 그래서, 그것들을 구성하는 것은 부정적으로 resource build times에 영향을 미치지 않는다는 것이 중요하다. 그러나, 몇 가지 BV는 런타임 동안 재정렬되어야 한다, 그것들의 포함된 오브젝트들이 움직일 때. 이러한 것에 대해, BV가 재정렬하는 것을 연산하기에 비싸다면, BV는 그것을 처음부터 재연산하는 것보다 더 선호된다. (더 싸다)
BV는 geometry외에도 저장되어지기 때문에, 그것들은 이상적으로 geometry에 어떠한 추가 메모리를 더하지 않을 것이다. 더 간단한 기하학적 도형은 메모리 공간을 덜 요구한다. 바람직한 많은 특성들이 크게 상호 배타적이기 때문에, 어떠한 특정한 BV도 모든 상황에 대한 최사으이 선택은 아니다. 대신에, 가장 좋은 옵션은 주어진 프로그램에 가장 적절한 것을 결정하기 위해 몇 가지 다른 BV를 테스트하는 것이다. 그림 4.2는 가장 흔한 BV 종류의 5개 중에서 몇 가지 trade-offs를 보여준다. 더 좋은 bounds, 더 좋은 culling, faster tests, 그리고 더 적은 메모리와 관련된 주어진 순서가 absolute, guide보다는 rough하게 보여질 것이다. 이 챕터에서 다뤄지는 BV의 첫 번째 것은 다음 섹션에서 설명되는 axis-aligned bounding box이다.
4.2 Axis-aligend Bounding Boxes (AABBs)
AABB는 가장 흔한 BV중의 하나이다. 그것은 정사각형의 six-sided 된 박스인데 (3D에서, 2D에서 four-sided 이 있는) 그것의 면들이 다음의 방향으로 향하게 한다, 그러니까 그것의 face normals들이 항상 주어진 좌표계의 축들과 평행하다. AABB의 가장 좋은 특징은 그것의 빠른 overlap 체크인데, 이것은 간단히 개별 좌표 값의 직접적인 비교를 포함한다.
AABB에 대한 세 가지 공통된 표기가 있다 (그림 44.3). 하나는 각 축을 따라 최소 최대 좌표 값에 의한 것이다:
// 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; };
이 표기는 공간의 BV 영역을 두 개의 반대되는 모서리점 사이의 것으로 명시한다 : min and max. 또 다른 표기는 minimum corner point min과 이 코너로부터의 width 또는 diameter extents dx, dy, dz로서 된다:
// 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) };
그 마지막 표기는 AABB를 중앙점 C와 그것의 축을 따라서 halfwidth extents or radii rx, ry, and rz로서 명시한다:
// 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) };
저장 요구사항의 관점에서, center radius representation이 가장 효율적이다, 왜냐하면 halfwidth values가 종종 center position values보다 더 작은 비트로 저장되어질 수 있기 때문이다. 그 같은 것은 min-width representation의 width values에도 해당된다, 비록 다소 더 낮은 degree에 해당할지라도. min-max representation이 최악인데, 거기에서 모든 6개의 값들은 같은 정밀도로 저장되어야만 한다. storage를 줄이는 것은 정수를 사용하는 AABB를 표기하는 것을 요구한다, floats가 아닌. 만약 그 오브젝트가 평행이동만 움직인다면, 그 후자의 두 개의 표기는 min-max 표기보다 더 싸다, 왜냐하면 그 6개의 파라미터들 중 세 개만이 업데이트 되어지기 떄문이다. center-radius 표기의 유용한 특징은, 그것이 bounding sphere로서 또한 테스트되어질 수 있다는 것이다.
4.2.1 AABB-AABB Intersection
AABBs들 간의 Overlap tests는 간단하다, 표기와 상관없이. 두 AABB는 그것들이 모든 세 개의 축에서 겹친다면 중복된다. 그리고 거기에서 각 차원을 따라 그것들의 extent는 대응되는 축에서 interval로 보여진다. min-max representation에 대해, 이 interval overlap test는 다음이 된다:
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; }
그 min-width representation이 가장 덜 매력적이다. 그것의 overlap test는 실속적인 방식으로 쓰여질 때, 여전히 수행되는 연산의 개수 관점에서 첫 번쨰 테스트와 비교되지 않는다:
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[1] || -t > a.d[2]) return 0; return 1; }
{
위의 코드가 잘 이해되지 않는다면, 부등식의 항을 바꾸어서 맨 처음의 코드처럼 생각하면 쉽게 이해가 될 것이다.
}
마지막으로, center-radius 표기는 다음의 overlap test를 만들어낸다:
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; }
현대 아키텍쳐에서, Abs() 호출은 일반적으로 단일의 명령어로 바뀐다. 만약 그렇지 않다면, 그 함수는 부동 소수점 값의 이진 표기의 sign bit를 벗겨내서 효과적으로 구현되어질 수 있다. AABB fields가 floats 대신에 integers로 선언되었을 때, center radius representation에 대한 대안의 테스트는 다음으로 수행되어질 수 있따. integers와 함께, 두 범위 [A,B] 와 {C,D] 사이의 overlap은 다음의 수식으로 결정되어질 수 있따
overlap = (unsigned int)(B - C) <= (B - A) + (D - C);
C > B일 때, unsigned underflow를 강요하여, 왼쪽 끝 쪽이 불가능하게 큰 값이 되고, 그 수식을 잘못되게 렌더링한다. 그 강요된 overflow는 효과적으로 절대값 함수를 대체하는 역할을 하고, center radius representation 테스트가 다음으로 쓰여지도록 한다:
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; }
integers로 작업하는 것은 다른 구현 트릭을 허용한다, 그리고 많은 그것들은 아키텍쳐 의존적이다. 만약 존재한다면 SIMD 명령어들은 일반적으로 AABB 테스트가 단지 몇 개의 명령어 코드로 구현되도록 한다 (그것들의 예시들은 Chapter 13에서 보여진다). 마지막으로, 수 많은 overlap tests를 수행해야만 하는 충돌 탐지 시스템에서, 그것들이 취해지는 가능성에 따라 테스트를 ordering하는 것은 가치가 있을지도 모른다. 예를들어, 만약 연산들이 크게 거의 평면 xz plane에서 발생한다면, y좌표 테스트는 마지막으로 수행되어야만 하고, 그것이 가장 덜 차별적이다.
4.2.2 Computing and Updating AABBs
BV는 보통 그것들이 bound하는 오브젝트들의 local model space에서 명시된다 (world space에서 일지도 모른다). 두 개의 BV 사이의 overlap query를 수행하기 위해서, 그 volumes들은 한 공통된 좌표계로 변환되어야만 한다. 그 선택은 두 개의 bounding volumes을 world space로 변환하는 것과 한 bounding volume을 다른 것의 local space로 변환하는 것 사이에 있다. local space로 변환하는 것의 한 이득은 그것이 world space로의 변환의 작업의 절반을 수행해야만 하는 것이다. 그것은 또한 world space로의 변환을 하는 것보다 더 tight한 BV를 만들어낸다. 그림 4.4는 그 개념을 보여준다. 오브젝트 A와 B의 재 계산된 AABBs는 world space에서 중복된다 (그림 4.4a). 그러나, object B의 공간에서, 그 오브젝트들은 분리된 것으로 발견된다 (그림 4.4c)
정확성은 한 BV를 다른 것의 local space로 변환하는 것에 대한 또 다른 강요되는 이유이다. world space test는 두 오브젝트들을 원점에서 멀리 움직일지도 모른다. BV의 local near-origin 좌표로의 변환 동안의 평행이동에서 더하는 행동은 원래 값의 정확도의 많은 비트들이 잃어지도록 할 수 있다. local space test에 대해서, 그 오브젝트들은 origin과 가까이 유지되고, 정확성은 계산에서 유지된다. 그러나, 변환된 오브젝트들이 원점에 중심을 갖도록 하여 평행이동을 조정하여, world space transformations이 정확성을 유지하도록 만들어질 수 있다는 것 또한 주목해라.
world space로의 변환은 업데이트된 BV가 일시적으로 time step의 duration동안 캐싱되어질 수 있따는 것에 흥미롭게 된다. 변환 후에 BV를 캐싱하여, 어떤 BV는 어떤 ㅜ어진 공간으로 한 번에 변화되어야만 한다. 모든 BV가 같은 공간으로 변환되기 때문에, world space로 변환 할 때, 이것은 objects들이 overlap을 위해 여러번 체크되어지는 상황에서 win이 된다. 대조적으로 업데이트된 BV를 캐싱하는 것은 전혀 도움되지 않는다, 다른 BV의 local sapce로 변환할 때, 왜냐하면 모든 변환들은 새로운 오브젝트들 또는 새로운 타겟 좌표 시스템 둘 중하나를 포함하기 때문이다. 업데이트된 BV의 캐싱은 요구되는 저장 공간의 두배의 단점을 가진다, BV 표기의 대부분의 필드가 업데이트동안 바뀌기 때문이다.
spheres 또는 convex hulls 같은 어떤 BV들은 자연스럽게 어떤 좌표계로 변환된다, 그것들이 특정한 방향으로 제한되지 않기 때문이다. 결과적으로, 그것들은 nonaligned or (freely) oriented bounding volumes. 대조적으로 aligned bounding volumes (AABBs같은)들은 그것들이 움직이는 동안 오브젝트 회전에 의해 unaligned 되기 때문에 재정렬되어야 한다. AABB를 업데이트하거나 재구성하는 것에 대해, 4가지 흔한 전략이 있다:
- 항상 그 오브젝트를 감싸는 고정된 사이즈의 loose한 AABB 활용
- 원래의 point set으로부터 tight dynamic reconstruction을 연산
- hill climbing을 사용하여 tight dynamic reconstruction을 연산
- 회전된 AABB로부터 approximate dynamic reconstruction 연산
다음의 4개의 섹션들은 이러한 접근법들을 좀 더 상세히 다룬다.
4.2.3 AABB from the Object Bounding Sphere
첫 번째 방법은 오브젝트를 어떤 방향에서든 포함할만큼 충분히 크게 만들어서, AABB를 다시 만들 필요성을 완전히 우회시킨다. 이 고정된 사이즈의 둘러싸는 AABB는 포함된 오브젝트 A의 bounding sphere의 bounding box로서 연산된다. 그 bounding sphere는 차례로, A가 회전하는 것에 대한 pivot point P를 중심이 된다. 그것의 반지름 r은 이 중심으로부터 가장 멀리 있는 오브젝트 vertex에 대한 거리이다 (그림 4.5에서 그려지듯이). 그 오브젝트 pivot P가 그 오브젝트의 중심에 있도록 하여, 그 sphere radius는 최소화된다.
이 표기의 장점은 업데이트 동안, 이 AABB가 간단히 평행이동 될 필요가 있다는 것이다(그 bounded object에게 적용된 같은 translation으로), 그리고 어떤 오브젝트 회전은 완전히 무시될 수 있다. 그러나, bounding sphere 그 자체로 (AABB보다 더 좋은 sound를 갖는) 또한 이 특성을 가질 것이다. 따라서, bounding spheres는 이 경우에 bounding volume의 잠재적인 더 좋은 선택으로 고려되어야 한다.
4.2.4 AABB Reconstructed fom Original Point Set
이 섹션에서 설명되는 업데이트 전략은 (뿐만 아니라 설명된 남아있는 두 가지 업데이트 전략들) 동적으로 그 AABB를 사이즈를 다시 조정하는데, 그것이 좌표계 축들을 따라 재정렬되도록 한다. tightly fitted bounding box에 대해, 그 bounded object의 underlying geometry는 검사되고, 그 box bounds는 그 좌표축의 모든 여섯 개 방향에서 extreme vertices를 찾아서 만들어진다. 그 간단한 접근법은 모든 정점에 대해 반복한다, 그리고 그 방향벡터를 따라 가장 멀리 있는 정점을 추적한다. 이 거리는 vertex vector를 그 방향 벡터로 사영하여 연산되어질 수 있다. 비교의 이유로, 그 방향벡터를 표준화할 필요가 없다. 이 절차는 다음의 코드에서 보여진다, 그것은 방향벡터를 따라 가장 적고, 가장 멀리 있는 점들 둘 다를 찾는다:
// 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; } } }
n이 클 때, 이 O(n) procedure는 런타임에 수행된다면 비쌀 수 있다. vertex data의 전처리는 그 프로세스를 가속하는 역할을 할 수 있다. 어떠한 추가 데이터를 더하지 않는 한 가지 간단한 접근법은, 그 오브젝트 위에 있는 convex hull에 있는 정점들만이 BV shape를 결정하는데 기여할 수 있다는 사실에 기반한다 (그림 4.6). 전처리단계에서, 그 오브젝트의 convex hull에 있는 모든 k개의 정점들은 저장되어질 것인데, 그것들이 모든 나머지 정점전에 오도록 한다. 그러고나서, tight AABB는 이러한 처음 k개의 정점만을 검사하여 만들어질 수 있다. 일반적인 concave volumes에 대해서, 이것은 win이 될 것이지만, 그것의 convex hull에 모든 정점들이 이미 있는 convex volume은 어떠한 개선을 보지 못할 것이다.
부가적인, 그리고 전용의, 미리 연산된 탐색 구조의 사용에 의해, extremal vertices를 찾는 것은 O(log n) 시간에 수행될 수 있다. 예를들어, Dobkin-Kirkpatric hierarch (Chapter 9에서 설명되는) 이 목적을 위해 사용되어질 수 있다. 그러나, 이러한 구조에 요구되는 추가 메모리에 의해, 뿐만 아니라 그것들을 가로지르는 오버헤드에 의해, 그것들은 대부분의 환겨에서 overkill로 고려되어야만 한다. 확실히 tight bounding volumes가 중요하다면, AABB보다 tighter bounding volumeㄴ가 고려되어야 한다.
4.2.5 AABB from Hill-climbing Vertices of the Object Representation
AABB realignment process를 가속화하는 또 다른 방법은 한 정점의 이웃한 정점들이 빠르게 발견될 수 있는 object representation을 사용하는 것이다. 그러한 표기는 simple hill climbing을 통해 새로운 AABB를 정의하는 extreme vertices가 찾아질 수 있도로 한다.
각 축을 따라 minimum and maximum extent values를 추적하는 대신에, 6개의 vertex pointers가 유지된다. 이전처럼 같은 값으로 대응되어, 이러한 것은 이제 실제로 각 축 방향을 따라 오브젝트의 (6개 까지의) extremal vertices를 가리킨다. hill-climbing step은 이제 referenced vertices를 비교하여 진행하는데, 그것들의 인접한 정점에 대해서 한다, 이것은 그것들이 여전히 이전과 같은 방향에서 extremal한지 보기 위해서이다. 그렇지 않은 정점들은 그것들의 가장 extreme한 이웃들 중 하나로 대체되고, 그 테스트는 그 방향에서의 extremal vertex를 찾을 때 까지 반복된다. local minima에 갖히지 않기 위해서, hill-climbing process는 오브젝트들이 convex이기를 요구한다. 이 이유때문에, hill climbing은 미리 계산된 non convex objects들의 convex hull에 수행된다. 종합적으로, 그 tight AABB의 이 재 계산은 예상되는 constant-time operation이다.
hill-climbing process에 의해 실제로 검사되었을 때, 정점들을 변환해야만 하는 것은 크게 연산 노력을 줄인다. 그러나, 이것은 x,y,z 컴포넌트들 중 하나만이 주어진 축을 따라 extremal vertex를 찾을 때 사용된다는 깨달음에 의해 더 개선되어질 수 있다. 예를들어, +x축을 따라 extremal point를 찾을 때, 그 변환된 정점들의 x 컴포넌트만이 연산되어질 필요가 있다. 그러므로, 그 변환 비용은 2/3가 줄어든다.
이 hill-climbing method의 튼튼한 구현을 쓰기 위해서 어떤 care가 취해져야 한다. coplanar vertices로만 둘러 싸여있는 어떤 축을 따라서 있는 extremal vertex를 고려하자. 만약 그 오브젝트가 이제 어떤 나머지 두 축에 대해 180도를 회전한다면, 그 정점은 그 같은 축을 따라 반대 방향으로 extremal되어진다. 그러나, co-planar vertices에 의해 둘러싸여있기 때문에, hill-climbing step은 더 좋은 이웃 정점을 찾을 수 없고, 따라서 실제로 찾아지는 방향에서 가장 덜 extremal한 정점으로 끝나게 된다. 튼튼한 구현은 이 상황을 스페셜 케이스화 해야한다. 대안적으로, coplanar vertices는 전처리 단계에서 제거되어질 수 있다, Chapter 12에서 묘사되듯이. extremal vertices는 찾는 문제는 Section 9.5.4에서 재방문된다.
4.2.6 AABB Recomputed from Rotated AABB
4개의 재정렬 방법중의 마지막 것인, 가장 흔한 접근법은 회전된 AABB를 한 새로운 AABB로 감싸는 것이다. 이것은 tight AABB보다는 근사를만들어낸다. 그 결과 AABB가 시작되었던 것보다 더 크기 때문에, 근사된 AABB가 원래의 local-space AABB의 회전으로부터 연산되어야 한다는 것이 중요하다. 만약 그렇지 않게 된다면, 이전 타임 스텝의 회전된 AABB로부터의 반복된 재 연산은 AABB가 무한히 크게 만들것이다.
회전 행렬 M에 영향을 받은 AABB A를 고려해보자, 이것은 어떤 방향을 가진 bounding box A'를 만들어낸다. 회전 행렬 M의 그 세 개의 열 (또는 행, 무슨 행렬 convention이 사용되었는지에 따라)은 그것의 local coordinate frame에서 A'의 world-coordinates axes를 준다. (만약 벡터가 column vectors이고, 그 행렬의 오른쪽에서 곱해진다면, 그러면 M의열들이 축들이다. 만약 대신에 그 벡터들이 행렬의 왼쪽에서 곱해지면, 행 벡터로서, 그러면 M의 행들이 축들이다.)
A가 min-max representation을 사용하여 주어지고, M이 column matrix라고 가정하자. A'를 bound하는 AABB B는 A'의 8개의 회전된 정점들의 world-coordinate axex에 대한 사영에 의해 형성된 extent intervals에 의해 명시된다. 가령, B의 x extents에 대해, M의 열 벡터들의 x 컴포넌트만이 기여한다. 그러므로, 그 extents를 찾는 것은 M의 행들로 minmal and maximal products를 만들어내는 정점들을 찾는 것과 같다. B의 각 정점은 A로부터의 세 개의 변환된 min or max values의 조합이다. 그 minimum extent value는 더 작은 항의 합들이고, 그 maximum extent는 더 큰 항들의 합계이다. 평행이동은 새로운 bounding ox의 크기 계산에 영향을 미치지 않고, 그냥 더해질 수 있따. 예를들어, x 축을 따라서 그 maximum extent는 다음으로 연산되어질 수 있다:
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];
{
위의 코드가 되어있어서 나는 glm 라이브러리의 접근법과 똑같다고 생각했는데 달랐다,
m[0][1]은 opengl 코드에서 m[1][0]과 같다. 즉 저 코드는 row vector로 되어있는 것이다.
glm::vec3 min(-1, 0, 0); glm::vec3 max(1, 1, 1); float minX = std::min(rot[0][0] * min[0], rot[0][0] * max[0]) + std::min(rot[1][0] * min[1], rot[1][0] * max[1]) + std::min(rot[2][0] * min[2], rot[2][0] * max[2]);
그래서 앞으로 코드들에서 회전 행렬을 쓰는 것에 대해 이 같은 점을 유의하라.
}
min-max representation을 사용하여 회전된 AABB에 대해 수반되는 bounding box를 연산하는 것은 그러므로 다음과 같이 구현될 수 있다:
// 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; } } } }
그에 맞게, center-radius AABB representation에 대한 코드는 다음과 같이 된다,
// 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) { 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]; } } }
회전된 AABB로부터 AABB를 연산하는 것은 그것은 freely oriented bounding box로부터 연산하는 것과 같다. Oriented bounding boxes와 그것들의 intersection tests는 앞으로 좀 더 상세하게 설명되어질 것이다. 그러나, 여기에서 보여진 방법들과, 앞으로 보여질 것들 사이에 분류되는 것은 오브젝트들과 함께 oriented bounding boxes를 저장하는 방법이 될 것이지만, 재구성된 AABB로서 그것들을 교차하는 방법이 될 것이다 (여기에서 처럼). 그렇게하는것은 orientation matrix를 저장하는 것에 대한 추가 메모리를 요구할 것이다. 그것은 또한 transformation matrix M이 있는 회전행렬을 결합하는 추가 matrix-matrix multiplication을 포함할 것이다. 이 솔루션의 이득은 재구성된 axis-aligned box가 더 타이트해질 것이다, oriented box로 시작해서. 그 axis-aligned test는 oriented boxes에 대해 full-blown test보다 훨씬 더 싸다.
4.3 Spheres
구는 또 다른 매우 흔한 bounding volume이고, AABB와 인기에서 라이벌 관계이다. AABB처럼, 구는 값 싼 intersection tests를 갖는다. Sphers는 또한 회전에서 불변하는 이점을 갖는다, 이것은 그것들이 변환하는 것이 사소하다는 것을 의미한다: 그것들은 간단히 그것들의 새로운 위치로 평행이동 되어야만 한다. 구는 center position과 반지름의 관점에서 정의된다:
// Region R = { (x,y,z) | (x - c.x)^2 + (y - c.y)^2 + z - c.z)^2 <= r^2 } struct Sphere { Point c; // Sphere center float r; // Sphere radius };
4개의 컴포넌트에서, 그 bouding sphere는 가장 메모리 효율적인 BV이다. 종종 이전에 존재하는 object center or origin은 sphere center와 일치하도록 조절될 수 있고, 오직 한 개의 component, 그 반지름이 저장될 필요가 있다. 최적의 bounding sphere를 연산하는 것은 optimal axis-aligned bounding box를 연산하는 것 만큼 쉽지 않다. bounding spheres를 연산하는 몇 가지 방법들은 다음 섹션에서 조사되는데, 증가되는 정확도 순으로 되는데, minimum bounding sphere에 대해 연산하는 알고리즘으로 결론 짓는다. nonoptimal approximation algorithms에 대해 탐사되는 방법들은 그것들이 다른 bounding volumes에도 적용될 수 있다는 점에서 관련이 있다.
4.3.1 Sphere-sphere Intersection
두 개의 구 사이의 중첩 테스트는 매우 간단하다. 두 구의 중심 사이의 Euclidean distance가 연산되고, 그 구의 반지름의 합과 비교된다. 한 종종 비싼 square root 연산을 피하기 위해서, 그 제곱된 거리가 비교된다. 그 테스트는 이것처럼 보인다:
int TestSphereSphere(Sphere a, Sphere b) { // Calculate squared distance between centers Vector d = a.c - b.c; float dist2 = Dot(d, d); // Spheres intersect if squared distance is less than squared sum of radii float radiusSum = a.r + b.r; return dist2 <= radiusSum * radiusSum; }
비록 sphere test가 AABB test보다 조금 더 많은 수학 연산을 가질지라도, 그것은 더 작은 branches를 ㄱ지고, 가져와질 더 적은 데이터를 여구한다. 현대 아키텍쳐에서, sphere test는 아마도 AABB test보다 거의 더 빠르다. 그러나, 이러한 간단한테스트들의 속도는 둘 사이에서 선택하는 것의 주된 factor가 되어서는 안된다. 실제 데이터에 대한 Tightness가 훨씬 더 중요한 고려사항이다.
4.3.2 Computing a Bounding Sphere
간단한 approximative bounding sphere는 모든 점의 AABB를 처음에 연산하여 얻어질 수 있다. AABB의 중간점은 그러고나서 sphere center로서 선택되어지고, 그 sphere radius는 이 중심점으로부터 가장 멀리 있는 점과의 거리로 설정된다. AABB의 midpoint 대신에 모든 점의 geometric center (평균)을 사용하는 것은 균일하지 않게 분산된 점들에 대해 매우 나쁜 bounding spheres를 줄 수 있다 (필요한 반지름의 두 배 까지). 비록 이것이 빠른 방법일지라도, 그것의 fit은 일반적으로 최적의 방법과 비교해서 매우 좋지 않다.
simple approximative bounding sphere를 연산하는 대안의 접근법은 [Ritter90]에 설명된다. 이 알고리즘은 좋은 초기의 거의 bounding sphere를 찾으려고 노력하고, 그러고나서 몇 가지 단계 후에, 그것이 모든 점을 bound할때 까지 그것을 개선시킨다. 그 알고리즘은 두 passes에서 진행한다. 첫 번째 pass에서, 6개의 (반드시 unique가 아닌) extremal points가 좌표축을 따라 발견된다. 이 6개 점들에서, 가장 멀리 있는 점들의 쌍이 선택된다. (이러한 두 점들이 필수적으로 그 점들의 집합의 AABB의 가장 긴 edge를 정의하는 점들과 일치하는 것은아니다.) 그 구의 중심점은 이제 이러한 두 점들의 중간점으로 선텍되고, 그 반지름은 그것들 사이의 거리의 반으로 설정된다. 이 첫 번째 pass에 대한 코드는 function MostSeparatedPointsOnAABB()에서 주어지고, 그 다음 것은 SphereFromDistantPoints()에 주어진다:
// Compute indices to the two most separated points of the (up to) six points // definint the AABB encompassing the point set. Return these as min and max. void MostSeparatedPointsOnAABB(int& min, in& max, Point pt[], int numPts) { // First find most extreme points along pricinpal axes int minx = 0. maxx = 0, miny = 0, maxy = 0, minz = 0, maxz = 0; for(int i = 1; i < numPts; ++i) { if(pt[i].x < pt[minx].x) minx = i; if(pt[i].x > pt[mixx].x) maxx = i; if(pt[i].x < pt[miny].y) miny = i; if(pt[i].x > pt[maxy].y) maxy = i; if(pt[i].x < pt[minz].z) minz = i; if(pt[i].x > pt[maxz].z) maxz = i; } // Compute the squared distances for the three pairs of points float dist2x = Dot(pt[maxx] - pt[minx], pt[maxx] - pt[minx]); float dist2y = Dot(pt[maxy] - pt[miny], pt[maxy] - pt[miny]); float dist2z = Dot(pt[maxz] - pt[minz], pt[maxz] - pt[minz]); // Pick the pair (min, max) of points most distant min = minx; max = maxx; if (dist2y > dist2x && dist2y > dist2z) { max = maxy; min = miny; } if (dist2z > dist2x && dist2z > dist2y) { max = maxz; min = minz; } } void SphereFromDistantPoints(Sphere &s, Point pt[], int numPts) { // Find the most separated point pair defining the encompassing AABB int min, max; MostSeparatedPointsOnAABB(min, max, pt, numPts); // Set up sphere to just encompass these two points s.c = (pt[min] + pt[max]) * 0.5; s.r = Dot(pt[max] - s.c, pt[max] - s.c); s.r = Sqrt(s.r); }
두 번째 pass에서, 모든 점들은 다시 반복되어진다. 현재 sphere의 바깥에 있는 모든 점에 대해, 그 sphere는 그 오래된 sphere와 밖의 점을 감싸는 sphere가 되도록 업데이트 된다. 다시 말해서, 그 새로운 sphere diameter는 outside point에서 outside point의 반대에 있는 old sphere의 뒷면에 있는 점까지 확장된다. old sphere center와 관련하여
// Given Sphere s and Point p, update s (if needed to just encompass p void SphereOfSphereAndPt(Sphere& s, Point& p) { // Compute squared distance between point and sphere center Vector d = p - s.c; float dist2 = Dot(d,d); // Only update s if point p is outside it if(dist2 > s.r * s.r) { float dist = Sqrt(dist2); float newRadius = (s.r + dist) * 0.5f; float k = (newRadius - s.r) / dist; s.r = newRadius; s.c += d * k; } }
approximate bounding sphere를 연산하는 풀 코드는 다음이 된다:
void RitterSphere(Sphere& s, Point pt[], int numPts) { // Gets sphere encompassing two approximately most distant points SphereFromDistantPoints(s, pt, numPts); // Grow spherer to include all points for(int i = 0; i < numPts; ++i) SphereOfSphereAndPt(s, pt[i]); }
true bounding sphere의 더 좋은 approximation으로 시작하여, 최종 sphere는 심지어 더 tighter 해지는 것이 기대될 수 있다. 더 좋은 starting approximation을 사용하는 것은 다음 섹션에서 보아진다.
4.3.3 Bounding Sphere from Direction of Maximum Spread
AABB를 사용하여 멀리 있는점들의 한 쌍을 찾는 것 대신에, 이전 섹션 처럼, 제안된 접근법은 그것의 maximum spread의 방향을 찾기 위해 statistical methods를 사용하여 point cloud를 분석하는 것이다 [Wu92]. 이 방향이 주어진다면, 이 축에 대해 사영될 때 서로에게 가장 멀리 있는 두 점들은 starting sphere의 center와 radius를 결정하는데 사영될 것이다. 그림 4.8은 같은 점 cloud에 대해 두 개의 다른 축에 대해 spread에서의 차이를 가리킨다.
데이터 값들의 한 집합의 평균이 (즉, 모든 값들의 합을 값들의 개수로 나눈 것) 그 값들의 중심적 경향의 척도이듯이, 분산(variance)는 그것들의 dispersion(확산, 분산), or spread(퍼짐)의 척도이다. 그 평균 u와 분산 o^2는 다음으로 주어진다
분산의 제곱근은 standard deviation(표준 편차)로 알려져있다. 한 단일의 축에 따라 펼처진 값에 대해, 그 분산은 쉽게 평균으로부터 값의 제곱 편차의 평균으로 연산되어진다:
// Compute variance of a set of 1D values float Variance(float x[], int n) { float u = 0.0f; for (int i = 0; i < n; ++i) u += x[i]; u /= n; float s2 = 0.0f; for(int i = 0; i < n; ++i) s2 += (x[i] - u) * (x[i] - u); return s2 / n; } float aVariance(float x[], int n) { float u = 0.0f; float s2 = 0.0f; for (int i = 0; i < n; ++i) { u += x[i]; s2 += x[i] * x[i]; } u /= n; s2 /= n; return s2 - (u * u); }
보통 분산과 표준편차의 명백한 직접적인 해석은 없다. 그러나, 비교 척도로서 그것들은 중요하다. 두 개의 변수에 대해, 그 covariance는 함께 vary하는 그것들의 경향을 측정한다. 그것은 그것들의 평균으로부터 변수 값의 편차의 곱의 평균으로 연산된다. 많은 변수에 대해, 데이터의 covariance는 전통적으로 연산되고 행렬로 표현된다. 그 covariance matrix로 (또한 variance-covariance or dispersion matrix로 언급된다).
n개의 점들 P_1, .. P_n의 집합에 대해 그 covariance matrix C = [c_ij]는 다음으로 주어진다
또는 다음에 의해서 같다
그 u_i (and u_j)항은 점들의 i번째 좌표값의 평균이다, 그리고 다음에 의해 주어진다
비공식적으로 그 covariance가 어떻게 작동하는지 보기 위해서, 그 첫 번째 convariance formula를 고려해라. 두 개의 변수들이 그것들의 각각의 평균으로부터 같은 방향에서 벗어나는 경향이 있을 때 그 곱
(P_k,i - u_i)(P_k,j - u_j)
는 음수보다는 종종 양수가 될 것이다. 만약 그 변수들이 다른 방향에서 벗어나는 경향이 있다면, 그 곱은 양수보다는 음수가 될 것이다. 이러한 곱들의 합은 그 변수들이 어떻게 co-vary지를 확인한다. single-precision floats를 사용하여 구현될 때, 그 두 개의 공분산 공식의 전자는 좀 더 많은 정밀도를 보유하여 좀 더 정확한 결과를 만들어내는 경향이 있다. double precision을 사용하여, 일반적으로 결과에 거의 차이가 없다. 다음의 코드는 그 첫 번째 공식을 구현한다:
void CovarianceMatrix(Matrix33& cov, Point pt[], int numPts) { float oon = 1.0f / (float)numPts; Point c = Point(0.0f, 0.0f, 0.0f); float e00, e11, e22, e01, e02, e12; // Compute the center of mass (centroid) of the points for(int i = 0; i < numPts; ++i) c += pt[i]; c *= oon; // Compute covariance elements e00 = e11 = e22 = e01 = e02 = e12 =0.0f; for(int i = 0; i < numPts; ++i) { // Translate points so center of mass is at origin Point p = pt[i] - c; //Compute covariance of translated points e00 += p.x * p.x; e11 += p.y * p.y; e22 *= p.z * p.z; e01 += p.x * p.y; e02 += p.x * p.z; e12 ++ p.y * p.z; } // Fill in the covariance matrix elements cov[0][0] = e00 * oon; cov[1][1] = e11 * oon; cov[2][2] = e22 * oon; cov[0][1] = cov[1][0] = e01 * oon; cov[0][2] = cov[2][0] = e02 * oon; cov[1][2] = cov[2][1] = e12 * oon; }
일단 covariance matrix가 연산되었다면, 그것은 그 분산의 주요 directions에 대해 좀 더 드러내느 방식으로 분해되어질 수 있다. 이 분해는 그 행렬의 고유값과 고유벡터를 연산하여 수행된다. 이러한 것 사이의 관계는 가장 큰 크기를 가진 고유값과 관련된 고유벡터는 그 point data가 가장 큰 분산을 가진 축과 일치한다. 유사하게, 가장 작은 크기의 고유값을 가진 관련된 고유벡터는 그 데이터가 가장 적게 분산된 축이다. 한 행렬의 고유값과 고유벡터를 튼튼히 찾는 것은 일반적으로 사소하지 않은 일이다. 일반적으로, 그것들은 몇 가지 (iterative)한 numerical techniuqe으로 찾아진다 (좋은 source는 [Golub96]이다).
정의에 의해, 공분산은 항상 대칭이다. 결과적으로, 그것은 실수(복소수 보다는) 고유값과 orthonomral basis의 고유벡터로 분해된다. 대칭 행렬에 대해, 더 간단한 분해 접근법이 상요되어질 수 있다. 적당한 크기의 행렬에 대해, 여기에서 처럼, 그 Jacobi method는 꽤 잘 작동한다. Jacobi method의 복잡한 세부사항은 이 책의 범위를 넘어선다. 그러나, 간단히해서, 그 알고리즘은 주어진 입력 행렬에 대해 많은 변환 단계를 수행한다. 각 단계는 행렬에 대한 회전을 적용하고, 그 행렬을 대각 행렬에 더 가깝게 가져오는 것을 포함한다 (대각선을 제외한 모든 원소들이 0). 그 행렬이 대각행렬일 때, 대각에 대한 원소들은 고유값이다. 이것이 되는 동안, 모든 회전은 다른 행렬로 연결되어진다. 종료시에, 이 행렬은 고유벡터들을 포함할 것이다. 이상적으로 이 분해는 numerical errors를 최소화 하기 위해 double-precision 연산에서 수행되어야만 한다. 그 Jacobi method의 다음 코드는 [Golub96]에 있는 프레젠테이션을 기반으로 한다. 처음에 그 회전행렬을 연산하느데 도움을 위한 sub routine이다.
// 2-by-2 Symmetric Schur decomposition. Given an n-by-n symmetric matrix // and indices p, q such that l <= p < q <= n, computes a sine-cosine pair // (s, c) that will serve to form a Jacobi rotation matrix. // // See Golub, Van Loan, Matrix Computations, 3rd ed, p428 void SymSchur2(Matrix33& a, int p, int q, float& c, float& s) { if(Abs(a[p][q]) > 0.0001f) { float r = (a[q][q] - a[p][p]) / (2.0f * a[p][q]); float t; if (r >= 0.0f) t = 1.0f / (r + Sqrt(1.0f + r*r)); else t = -1.0f / (-r + Sqrt(1.0f + r*r)); c = 1.0f / Sqrt(1.0f + t * t); s = t * c; } else { c = 1.0f; s = 0.0f; } }
이 support function이 주어진다면, 그 full Jacobi method는 이제 다음으로 구현된다:
// Computes the eigenvectors and eigenvalues of the symmetric matrix A using // the classic Jacobi method of iteratively updating A as A = J^T * A * J, // where J= J(p, q, theta) is the Jacobi rotation matrix. // // On exit, v will contain the eigenvectors, and the diagonal elements // of a are the coresponding eigenvalues // See Golub, Van Loan, Matrix Computations, 3rd ed, p428 void Jacobi(Matrix33& a, Matrix33& v) { int i, j , n, p, q; float prevoff, c, s; Matrix33 J, b, t; // Initialize v to identify matrix for(i = 0; i < 3; ++i) { v[i][0] = v[i][1] = v[i][2] = 0.0f; v[i][i] = 1.0f; } // Repeat for some maximum number of iterations const int MAX_ITERATIONS = 50; for(n = 0; n < MAX_ITERATIONS; n++) { // Find largest off-diagonal absolute element a[p][q] p = 0; q = 1; for(i = 0; i < 3; i++) { for(j = 0; j< 3; ++j) { if(i == j) continue; if(Abs(a[i][j]) > Abs(a[p][q])) { p = i; q = j; } } } // Compute the Jacobi rotation matrix J(p, q, theta) // (This code can be optimized for the three different cases of rotation) SymSchur2(a, p, q, c, s); for(i = 0; i < 3; ++i) { J[i][0] = J[i][1] = J[i][2] = 0.0f; J[i][1] = 1.0f; } J[p][p] = c; J[p][q] = s; J[q][p] = -s; J[q][q] = c; // Cumulate rotations into what will contain the eigenvectors v = v * J; // Make 'a' more diagonal, until just eigenvalues remain on diagonal a = (J.Transpose() * a) * J; // Compute "norm" of off-diagonal elements float off = 0.0f; for(i = 0; i < 3; ++i) for(j = 0; j < 3; ++j) { if(i == j) continue; off += a[i][j] * a[i][j]; } /* off = sqrt(off); not needed for norm comparison */ // Stop when norm no longer decreasing if(n > 2 && off >= preoff) return; prevoff = off; } }
여기에서 사용되는 그 특별한 3x3 행렬에 대해, Jacobi method같은 일반적인 접근법을 적용하는 대신에, 고유값들은 직접적으로 간단한 cubic equation으로부터 연산되어질 수 있다. 그 고유 벡터들은 가우스 소거법으로 예를들어 쉽게 발견되어질수 있다. 그러한 접근법은 [Cromwell94]에 설명된다. 이전에 정의된 함수가 주어진다면, 두 개의 가장 먼거리의 점들로부터(spread에 따라) 한 sphere를 연산하는것은 이제 이것처럼 보인다:
void EigenSphere(Sphere& eigSphere, Point pt[], int numPts) { Matrix33 m, v; // Compute the covariance matrix m CovarianceMatrix(m, pt, numPts); // Decompose it into eigenvectors (in v) and eigenvalues (in m) Jacobi(m, v); // Find the component with largest magnitude eigenvalue (largest spread) Vector e; int maxc = 0; float maxf, maxe = Abs(m[0][0]); if ((maxf = Abs(m[1][1])) > maxe) maxc = 1, maxe = maxf; if ((maxf = Abs(m[2][2])) > maxe) maxc = 2, maxe = maxf; e[0] = v[0][maxc]; e[1] = v[1][maxc]; e[2] = v[2][maxc]; // Find the most extreme points along direction 'e' int imin, imax; ExtremePointsAlongDirection(e, pt, numPts, &imin, &imax); Point minpt = pt[imin]; Point maxpt = pt[imax]; float dist = Sqrt(Dot(maxpt - minpt, maxpt - minpt)); eigSphere.r = dist * 0.5f; eigSphere.c = (minpt + maxpt) * 0.5f; }
그 approximate bounding sphere를 계산하는 수정된 풀 코드는 다음이 된다:
void RitterEigenSphere(Sphere& s, Point pt[], int numPts) { // Starts with sphere from maximum spread EigenSphere(s, pt, numPts); // Grow sphere to include all points for (int i = 0; i < numPts; i++) SphereOfSphereAndPt(s, pt[i]); }
여기에서 수행된 공분산 분선의 종류는 dimension reduction과 데이터의 통계적 분석에 흔히 사용되고, principla component analysis (PCA)로 알려져있다. PCA에 대한 더 많은 정보는 [Jolliffe02]에서 발견될 수 있따. 공분산 행렬의 고유 벡터들은 또한 섹션 4.4.3에서 oriented bounding box를 방향짓는데 사용되어질 수 있다.
4.3.4 Bounding Sphere Through Iterative Refinement
4.3.5 The Minimum Bounding Sphere
Bounding Sphere를 정확히 계산하는 것은 저기 위의 고유값 벡터를 이용하는 것만 해도될 거같다. 나중에 필요하면 공부하면 될듯하다.
4.4 Oriented Bounding Boxes (OBBs)
oriented bounding box (OBB)는 rectangular block이고, AABB와 많이 유사하지만, 임의의 방향이 있다. OBB에 대한 많은 가능한 표기법들이 있다: 8개의 정점의 모음, 6개의 평면의 모음, 세개의 slabs (평행한 평면의 한 쌍), 한 개의 corner vertex와 세 개의 상호적으로 직교하는 edge vectors, 또는 중심점과 orientation matrix와 세 개의 halfedge lengths. 그 후자가 흔히 OBB에 대해 선호되는 표기이다, 왠하면 그것은 다른 표기법보다 더 싼 OBB-OBB intersection test를 허용하기 때문이다. 이 테스트는 separating axis theorem을 기반으로 하고, Chapter 5에서 좀 더 상세히 이야기 된다.
// Region R = { x | x = c + r* u[0] + s * u[1] + t*[2]}, |r| <= e[0], |s| <= e[1], |t| <= e[2] struct OBB { Point c; // OBB center point Vector u[3]; // Local x-, y-, and z-axes vector e; // Positive halfwidth extents of OBB along each axis };
15개의 floats에서, 또는 IEEE 단일 정밀도 floats에 대한 60 bytes에 대해, OBB는 꽤 메모리 사용 측면에서 비싼 bounding volume이다. 그 메모리 요구사항은 행렬으로서가 아닌 오일러 각 또는 쿼터니언으로서 저장하는 것이 낮춰질 수 있다, 9개 대신에 3개에서 4개의 floating-point components를 사용해서. 불행하게도, OBB-OBB intersection test에 대해, 이러한 표기는 효괒거인 separating axis test에서 사용하기 위해 행렬로 변환되어야만 하고, 그것은 매우 비싼 연산이다. 그러므로 좋은 타협은 그 회전 행렬 축의 두 개를 저장하고, 테스트 타임에 다른 두 개의 외적으로부터 세 번째 것을 연산하는 것이다. 이것은 상대적으로 갑싼 CPU 연산이 세 개의 floating-point components를 구하고, 20% memory 절약을 만들어낸다.
4.4.1 OBB-OBB Intersection
이전 bounding volume intersection tests와 달리, 두 개의 OBB 사이의 overlap에 대한 테스트는 놀랍게도 복잡하다. 처음에, 그것은 다른 것의 한 face의 완전히 밖에 있는 box가 충분하는지를 보는 테스트 처럼 보인다. 그것의 가장 간단한 형태에서, 이 테스트는 box A의 정점들이 모두 box B의 면들에 의해서 정의된 평면 밖에 있는지를 체크하여 수행될 수 있다. 그리고 역으로. 그러나, 이것이 2D에서 작동할지라도, 3D에서 정확히 작동하지 않는다. 그것은 예를들어, A와 B가 거의 edge to edge로 만나고, 서로에게 수직한 edges인 상황에서 다루는 것을 실패한다. 여기에서 그 두 개의 박스 둘 다 완전히 다른 것의 어떤 면 밖에 있지 않다. 결과적으로 가장 간단한 테스트는 그것들이 교차하고 있다고 보고한다, 비록 그러지 않을지라도. 심지어 그래서, 그 간단한 테스트는 여전히 유용할지도 모른다. 비록 그것이 항상 옳지 않더라도, 그것은 그것이 충돌을 탐지하는데 결코 실패하지 않는다는 점에서 보수적이다. 그것이 부정확하게 separated boxes가 overalapping한다고 보고하는 경우에만 그렇다. 그러듯이, 그것은 좀 더 비싼 정확한 테스트에 대해 pretest로서 역할을 할 수 있다.
OBB-OBB intersection에 대한 정확한 테스트는 separating axis test로서 알려진 관점에서 구현되어질 수 있다. 이 테스트는 Chapter 5에서 상세히 이야기 되지만, 여기에서 두 개의 OBB가 분리되어 있는지를 주목하는 것은 충분하다, 만약 어떤 축 L과 관련하여, 그것들의 사영된 radii의 합계가 그것들의 center points의 사영된 것 사이의 거리보다 더 작다면 두 개의 OBB가 분리되어있다. (그림 4.9에 그려져있따). 즉, 만약
OBB에 대해, 이러한 separating axes의 최대 15개가 OBB overlap status를 정확히 결정하기 위해 테스트되어야 한다는 것을 보여주는 것은 가능하다. 이러한 축들은 A의 세 개의 좌표축, B의 세 개의 좌표 축, 그리고 각각으로부터 한 축에 수직인 9개의 축들과 대응된다. 만약 그 박스가 15개의 축들 중 어떤 것에도 overlap되는데 실패한다면, 그것들은 교차하고 있지 않다. 만약 어떠한 축이 이 early out을 제공하지 않는다면, 그것은 그 박스가 겹쳐져있다는 것을 따른다.
이 테스트에서 연산의 개수는 B를 A의 좌표 frame에서 표현하여 줄어들 수 있다. 만약 t가 A에서 B로가는 translation vector이고, R = [r_ij] (B를 A의 좌표 프레임으로 바꾸는 회전행렬)이라면, 다른 축들 L에 대해 수행되어야 하는 테스트들은 테이블 4.1에 요약된다.
이 테스트는 다음으로 구현되어질 수 있다:
int TestOBBOBB(OBB& a, OBB& b) { float ra, rb; Matrix33 R, AbsR; // Compute rotation matrix expressing b in a's coordinate frame for(int i = 0; i < 3; ++i) for(int j =0; j < 3; ++j) R[i][j] = Dot(a.u[i], b.u[j]); // Compute translation vector Vector t = b.c - a.c; // Bring translation into a's coordinate frame t = Vector(Dot(t, a.u[0]), Dot(t, a.u[1]), Dot(t, a.u[2])); // Compute common subexpressions. Add in an epsilon term to // counteract arithmetic errors when two edges are parallel and // their cross product is (near) null (see text for details) for (int i = 0; i < 3; ++i) for (int j = 0; j < 3; ++j) AbsR[i][j] = Abs(R[i][j]) + EPSILON; // Test axes L = AO, L = A1, L = A2 for(int i = 0; i< 3; ++i) { ra = a.e[i]; rb = b.e[0] * AbsR[i][0] + b.e[1] * AbsR[i][1] + b.e[2] * AbsR[i][2]; if(Abs(t[i]) > ra + rb) return 0; } // Test axes L = B0, L = B1, L = B2 for(int i = 0; i < 3; ++i) { ra = a.e[0] * AbsR[0][i] + a.e[1] * AbsR[1][i] + a.e[2] * AbsR[2][1]; rb = b.e[i]; if(Abs(t[0] * R[0][i] + t[1] * R[1][i] + t[2] * R[2][1]) > ra + rb) return 0; } // Test axis L = A0 X B0 ra = a.e[1] * AbsR[2][0] + a.e[2] * AbsR[1][0]; rb = b.e[1] * AbsR[0][2] + b.e[2] * AbsR[0][1]; if(Abs(t[2] * R[1][0] - t[1] * R[2][0]) > ra + rb) return 0; ..... ..... ..... // Since no separating axis is found, the OBBs must be intersecting return 1; }
가능한한 OBB-OBB test를 효율적으로 만들기 위해서, 축들이 Table 4.1에서 주어진 순서대로 테스트되어지는게 중요하다. 이 순서를 사용하는 첫 번째 이유는, 세 개의 orthogonal axes에 대해 처음에 테스트하여, 테스트에서 거의 공간적 중복이 없다는 것이고, 그 전체 공간이 빠르게 처리된다. 둘 쨰로, 여기에서 주어진 설정으로, A가 origin으로 변환되고, 좌표축과 정렬되는, A의 축들로 테스팅하는 것은 B의 축들로 테스팅 하는 비용의 절반이다. 비록 그것이 여기에서 되지 않았지만, R과 AbsR의 계산들은 처음 세 개의 테스트에서 끼워져야 된다, 그것들이 불필요하게 그것들의 entirety에서 수행되지 않도록 하기 위해서이다, OBB test가 처음 몇 개의 if statements에서 종료될 때.
만약 OBB들이 그것들이 종종 현재의 world up과 정렬되는 한 축을 갖는 경향이 있는 프로그램에서, 예를들어, 땅 위를 이동할 때, 이러한 "vertically aligned" OBBs를 특별 케이스화 하는 것은 가치가 있따. 이 간단화는 vertical direction에서 값 싼 테스트 외에도 4개의 separating axes를 검사하는 것만을 포함하는 더 빠른 intersection test를 허용한다.
몇 경우에서, 15개의 축 테스트들 중 처음의 6개를 수행하는 것은 더 빠른 결과를 만들어낼지도 모른다. 경험적인 테스트에서, [Bergen97]은 OBB overlap code에서 마지막 9개의 테스트들이 시간의 15%에 대해 nonintersection을 결정한다고 발견했다. 아마도, 모든 쿼리들의 절반이 양수로 시작하기에, 이러한 9개의 테스트들을 생략하는 것은 그 시간의 6~7%에 대해 false positives를 만들어 낼 것이다. OBB test가 bounded geometry에서 정확한 테스트를 위한 pretest로서 수행 될 때, 이것은 여전히 test conservative를 남기고, 어떠한 충돌들도 놓쳐지지 않는다.
4.4.2 Making the Separating-axis Test Robust
separating axis theorem의 몇 가지 인기있는 처리에서 간과되는 한 가지 중효한 문제는 그 테스트의 robustness이다. 불행하게도, 이 테스트를 구현하는 어떤 코드든 매우 신중하게 의도된대로 작동하도록 만들어져야 한다. separating axxis가 각 bounding box로부터 한 edge의 외적을 취하여 형설될 때, 이러한 edges들이 평행하는 가능성이 있다. 결과적으로, 그것들의 외적은 null vector이고, 이 null vector에 대한 모든 사영은 zero이고, 그 축 부등식의 각 side에 대한 곱의 합은 사라진다. 남는 것은 0 > 0의 비교이다. 정확한 arithmetic mathematics의 완벽한 세계에서, 이 식은 자명하게 잘못ㅅ되었다고 평가된다. 현실에서, 어떤 컴퓨터 구현은 부동 소수점 연산의 사용으로 인해 도입되는 부정확성을 다뤄야만 한다.
일찍이 보여진 최적화된 부등식에 대해, 평행한 edges의 경우는 참조되는 회전 행렬 R이 zero elements와 대응된다. 이론적으로, 이것은 0 > 0의 비교를 만들어낸다. 그러나, 실제로, 에러들의 축적으로 인해, 회전 행렬이 완벽하게 orthonormal하지 않을 것이고, 그것의 zero elements가 정확히 0이 아닐 것이다. 따라서, 그 부등식의 양 변에 곱의 합은 0이 되지 않을 것이지만 몇 가지 작은 에러의 양이 될 것이다. 이 에러의 축적은 부등식의 둘 중 하나의 변이 부호를 바꾸거나 크기에서 이동하게 하기 때문에, 그 결과는 꽤 랜덤이 될 것이다. 결과적으로 만약 그 부등식 테스트들이 신중하게 수행되지 않는다면, 이러한 연산 에러들은 separating axis로서 부정확하게 해석되는 (가까운) null vector를 이끌 것이다. 두 개의 겹치는 OBB들은 그러므로, 부정확하게 nonintersecting하도고 보고되어질 수 있다.
부등식들의 우변이 두 OBBs가 서로 관통할 때 더 커야하기 때문에, 그 문제에 대한 간단한 해결책은 부등식의 우변에 발생하는 행렬 원소의 절대값에 작은 epsilon value를더하는 것이다. near-zero terms에 대해, 이 epsilon term은 우세할 것이고, (거의) parallel edges에 일치하는 axis tests들은 따라서 불균형하게 conservative하도록 만들어진다. 다른 nonzero cases에 대해, 그 small epsilon term은 간단히 사라질 것이다. 회전행렬의 컴포넌트들의 절대값들은 [0, 1]의 범위에 제한되기 때문에, fixed-magnitude epsilon을 사용하는 것이 관련된 박스들의 크기와 상관없이 잘 작동할 것이라는 것에 주목해라. separating axis test의 robustness는 Chapter 5에서 재방문된다.
4.4.3 Computing a Tight OBB
4.4.4 Optimizing PCA-based OBBs
4.4.5 Brute-force OBB Fitting
여기도 Bounding Sphere와 마찬가지로, 나중에 필요하면 공부하면 될 것 같다.
4.5 Sphere-swept Volumes
4.6 Halfspace Intersection Volumes
4.7 Other Bounding Volumes
위의 4.5 ~ 4.7도 복잡해지고 고급 충돌탐지 기법을 위해서 쓰이니 여기는 제외하자.
4.8 Summary
BV는 더욱 큰 기하학적 복잡성을 가진 한 개 이상의 오브젝트들을 캡슐화하기 위해 사용되는 간단한 기하학적 shapes이다. 매우 자주, spheres와 boxes가 bounding volumes으로 사용된다. 만약 really tight fit이 요구된다면, slab volumes or convex hulls가 사용될지도 모른다. BV는 좀 더 비싼 테스트가 그것들 내에서 둘러싸여진 도형들에 수행되기 전에 early overlap rejection test로서 사용된다. Section 4.1에서 이야기 되었듯이, BV shapes의 선택과 관련된 trade-offs들이 있다. tighter fit의 BV를 사용하여, early rejection 의 가능성이 증가하지만, 동시에, BV test는 좀 더 비싸고, BV에 대한 저장공간의 요구는 증가한다. 일반적으로, BV는 전처리 단계에서 연산되고, 필수적으로 런타임 동안에 bounded objects와 objects의 움직임에 부합하도록 변환된다.
가장 흔한 BV를 세부적으로 보고, 어떻게 그것들을 연산하는지 외에도, 이 챕터는 homogeneous intersection tests들을 어떻게 수행하는지를 설명했다 (같은 타입의 volumes사이에). 이러한 테스트들은 Chapter 5로 가는 teaser로서 의도되었다, 거기에서 상당한 세부사항으로 lines and line segments, spheres, boxes, triangles, polygons, and polyhedra같은 primitive geometrical shapes 사이의 거리 계산과 (heterogenous) intersection tests들을 다룬다.
댓글 없음:
댓글 쓰기