5.2.9 Testing AABB Against Triangle

5.2.9 Testing AABB Against Triangle

상자 B를 가로지르는 삼각형 T의 테스트는 seperating-axis 접근법을 사용해 효율적으로 구현할 수 있다.

투영을 고려해야하는 13개의 축이 있다:

1. AABB의 three face normals

2. 삼각형의 one face normal

3. 두 축으로부터의 모서리의 조합 교차 곱에 의해 주어진 9축

이전처럼 분리 축이 발견되면 테스트는 "교차 없음" 결과와 함께 즉시 종료할 수 있다. 모든 축을 테스트하고 분리 축이 발견되지

않으면 상자와 삼각형이 교차해야한다. 이 세 가지 테스트를 수행하는 가장 효율적인 순서는 3-1-2라고 제안되었다.

동일한 13축 테스트가 OBB 및 AABB 모두에 적용된다. 그러나 AABB의 경우 (상자의 로컬 축이 알려져있기 때문에) 테스트에 필요한

런타임 계산 속도를 높이기 위해 최적화를 수행할 수 있다. 여기서는 AABB 테스트만 제시되지만 유사성을 보다 잘 설명하고

AABB 특정 최적화를 용이하게 하기 위해 AABB는 OBB에 일반적으로 사용되는 형태로 제공된다고 가정한다.

즉 중심 C에 의해; 로컬 축 u0 = (1, 0, 0), u1 = (0, 1, 0), u2 = (0, 0, 1); 범위 e0, e1, e2.

테스트 된 삼각형은 V0 = (v0x, v0y, v0z), V1 = (v1x, v1y, v1z), V2 = (v2x, v2y, v2z)로 표시된다.

 AABB의 세 면 법선 (u0, u1, u2)은 삼각형의 AABB를 계산하고 오버랩을 위해 삼각형의 AABB와 B를 쉽게 테스트된다.

두 AABB가 교차하지 않으면 B와 T도 마찬가지이다. 삼각형 면 법선과 평행한 축 검사는 AABB가 삼각형 평면과 교차하는지 테스트하는

것과 같다. 이 테스트는 5.2.3 절에 설명되었으므로 더 자세한 설명은 생략하겠다.

나머지는 B에서 3개의 엣지 방향과 T에서 3개의 엣지 방향의 외적에 해당하는 9개의 축을 테스트하는 것이다.

대부분의 분리 축 테스트와 마찬가지로 하나의 객체(존재하는 경우 대칭 객체)를 원점으로 이동해 계산을 단순화한다.

여기에서 상자 중심은 원점과 정렬되도록 이동되어 V0 ← V0 − C, V1 ← V1−C, V2 ← V2−C, C ← (0, 0, 0) 의 변수 업데이트가 발생한다.

삼각형 모서리 : V0 = ( f0x , f0y, f0z ), f1 = V2 − V1 = ( f1x , f1y, f1z ), f2 = V0 − V2 = ( f2x , f2y, f2z ).

분리 축으로 간주되는 9개의 축은 a ij = ui * fj 로 지정할 수 있다.

u0, u1, u2는 간단한 형식이므로 축은 다음과 같이 단순화된다:

축 n에 대한 상자의 투영 반지름은 다음과 같이 주어진다:

n = a 00의 경우, 이는 다음과 같이 단순화된다:

비슷하게, AABB 투영 반지름에 대한 간단한 식은 나머지 aij 축에 대해 쉽게 구할 수 있다. 모든 경우 상자의 투영 간격은 단순히

[-r, r]이다. 주어진 축 n에 T를 투영하면 투영 간격 [min (p0, p1, p2), max (p0, p1, p2)]이 된다. 여기서 p0, p1, p2는 원점에서

삼각형 정점을 n 위에 놓는다. n = a00의 경우 이 값은 다음과 같다:

지정된 축에 대해 투영 간격 [-r, r] 및 [min (p0, p1, p2), max(p0, p1, p2)]가 서로 맞지 않으면 축이 분리 축이고 삼각형과 ABB는 겹치지 않아야한다.

이 축에 대해 n = a00이면 p0 = p1이고 삼각형의 투영 간격은 [min(p0, p2), max(p0, p2)]로 단순화된다.

삼각형 투영 간격은 9개의 투영 축 모두에 대해 동일한 방식으로 단순화된다. 모든 투영 축에는 모두 하나의 영(0) 구성 요소가 포함되어 있다.

따라서, max(p0, p2) < -r 또는 min(p0, p2) > r인 경우 AABB와 삼각형 투영 간격은 서로 연결되지 않는다.

min() 및 max() 연산이 대상 아키텍처에서 네이티브 부동 소수점 명령어로 사용 가능한 경우, 하나의 (잠재적으로 값 비싼) 비교를 피하는

동일한 표현식은 max (-max (p0, p2), min(p0, p2)) > r이다.

후자의 공식은 SIMD 구현에 특히 유용하다. 다음 코드는 이 테스트를 구현하는 방법을 보여준다.

int TestTriangleAABB(Point v0, Point v1, Point v2, AABB b)
{
float p0, p1, p2, r;
// Compute box center and extents (if not already given in that format)
Vector c = (b.min + b.max) * 0.5f;
float e0 = (b.max.x - b.min.x) * 0.5f;
float e1 = (b.max.y - b.min.y) * 0.5f;
float e2 = (b.max.z - b.min.z) * 0.5f;
// Translate triangle as conceptually moving AABB to origin
v0 = v0 - c;
v1 = v1 - c;
v2 = v2 - c;
// Compute edge vectors for triangle
Vector f0 = v1 - v0, f1 = v2 - v1, f2 = v0 - v2;
// Test axes a00..a22 (category 3)
// Test axis a00
p0 = v0.z*v1.y - v0.y*v1.z;
p2 = v2.z*(v1.y - v0.y) - v2.z*(v1.z - v0.z);
r = e1 * Abs(f0.z) + e2 * Abs(f0.y);
if (Max(-Max(p0, p2), Min(p0, p2)) > r) return 0; // Axis is a separating axis
// Repeat similar tests for remaining axes a01..a22
...
// Test the three axes corresponding to the face normals of AABB b (category 1).
// Exit if...
// ... [-e0, e0] and [min(v0.x,v1.x,v2.x), max(v0.x,v1.x,v2.x)] do not overlap
if (Max(v0.x, v1.x, v2.x) < -e0 || Min(v0.x, v1.x, v2.x) > e0) return 0;
// ... [-e1, e1] and [min(v0.y,v1.y,v2.y), max(v0.y,v1.y,v2.y)] do not overlap
if (Max(v0.y, v1.y, v2.y) < -e1 || Min(v0.y, v1.y, v2.y) > e1) return 0;
// ... [-e2, e2] and [min(v0.z,v1.z,v2.z), max(v0.z,v1.z,v2.z)] do not overlap
if (Max(v0.z, v1.z, v2.z) < -e2 || Min(v0.z, v1.z, v2.z) > e2) return 0;
// Test separating axis corresponding to triangle face normal (category 2)
Plane p;
p.n = Cross(f0, f1);
p.d = Dot(p.n, v0);
return TestAABBPlane(b, p);
}

카테고리 2의 테스트 (퇴화되거나 거대한 삼각형에 대한 페이스 노멀을 계산할 때)와 3(제로 벡터를 제공하는 두 개의 평행 엣지의 교차 곱)과

관련된 강건성 문제가 있음에 유의해라. 완전히 견고한 구현에서 이러한 사례를 다루기 위해 해야 할 일에 대한 논의는 5.2.1.1 절을 참조해라.

삼각형 AABB 오버랩 테스트의 주제는 [Voorhies92]에서 논의된다. AABB에 대한 임의의 다각형 테스트는 [Green95]에 나와있다.