Chapter 5 Basic Primitive Tests (실시간 충돌탐지)

Chapter 5 Basic Primitive Tests
high-level system (BV Test)이 이후의 충돌 테스트로부터 가능한한 많은 오브젝트들을 제외한 후에, 모든 충돌 시스템은 intersection tests들을 결정하기 위해 primitives 또는 BV사이의 low-level tests를 수행해야만 한다. 어떤 경우에, 충돌이 있다는 간단한 indication은 충분하다. 다른 경우들에서, intersection의 실제 지점이 요구된다.  이 챕터는 어떻게 이러한 low-level tests들이 효과적으로 수행되어질 수 있는지를 설명한다. 게다가, 그 목표는 충분한 구체적인 수학적인 세부사항을 제공하는 것인데, 이 presentation의 범위를 넘어서는 테스트들의 유도를 허용하기 위해서이다, 그래서 여기에서 조사되는 수학적 아이디어들을 사용한다.

여기에서 보여지는 어떤 수식들이 부동소수점 연산에서 구현될 때 numerical accuracy problem에 종속되었을지도 모른다는 것에 주목해라. 이러한 문제들은여기에서 명료하게 다뤄진다. numerical accuracy problems에 의한 robustness issues에 대한 깊은 이야기는 Chapter 11에서 된다.

5.1 Closest-point Computations
Closest-point queries는 collision queries의 가장 강력한 것이다. 두 오브젝트들 사이의 가장 가까운 점들이 주어진다면, 그 오브젝트들 사이의 거리가 얻어진다. 만약 두 오브젝트들의 결합된 maximum movement가 그것들 사이의 거리보다 작다면, 한 충돌은 제외될 수 있다. hierarchical representation에서, closest-point computations은 충돌할 만큼 충분히 결코 가까워지지 않을 hierarchy의 부분들이 나중의 고려사항으로부터 쳐내어지도록 한다.

두 오브젝트들 사이의 가장 가까운 점들을 얻는 것은 minimization문제로서 보여질 수 있다. 한 가지 접근법은 그 minimization problem을 공식화 하는 것이고, 적분의 방법을 사용해서 그것을 해결하는 것이다 (Largrange multipliers의 방법 같은). 이 교재에서, 좀 더 기하학적인 접근법이 선호되고, 다음의 subsections들은 그 가장 가까운 점들이 다양한 geometric objects들에 대해 어떻게 얻어질 수 있는지를 보여준다.

두 오브젝트들사이의 가장 가까운 점들은 가끔씩 낮은 비용에서 증가적으로 유지되어질 수 있는데, 빠른 충돌탐지를 용이하게 하면서. 가장 가까운 점의 Incremental computation은 Chapter 9에서 더 조사된다, convex objects들 사이의 충돌의 맥락에서.

5.1.1 Closest Point on Plane to Point
한 점 P와 normal n으로 정의된, plane 𝞹가 주어진다면, 그 평면위의 모든 점 X들은
dot(n, (X - P)) = 0 을 만족한다 (즉, P에서 X로가는 벡터는 n에 수직이다). 이제 Q가 공간에서 임의의 점이라고 하자. 평면 위에서 Q에 가장 가까운 점 R은 Q의 평면에 대한 orthogonal projection인데, Q를 평면쪽으로 (n과 관련하여) 수직으로 이동시켜서 얻어진다. 즉, 그림 5.1에서 보여지듯이, 어떤 t의 값에 대해 R = Q - tn이 된다. R에 대한 이 수식을 평면의 방정식에 삽입하고 t에 대해 푸는것은 다음을 준다:



t에 대한 이 식을 R = Q - tn에 대체하는 것은 projection point R을 다음으로 준다



n이 단위 길이일 때, t는 t = n • (Q - P)로 간단하게 되고, R을 간단하게 R = Q - (n • (Q - P))n 으로 만든다. 이 방정식으로 부터, 어떤 임의의 점 Q에 대해, t = n • (Q - P)는 n의 단위 길이에서, 그 평면으로 부터의 Q의 양의 거리와 일치한다는 것을 보는 것은 쉽다. 만약 t가 양수라면, Q는 평면의 앞에 있다 (음수라면, Q는 그 평면의 뒤에 있다).

그 평면이 n • X = d인 4개의 컴포넌트 형식으로 주어질 때, t에 대응되는 식은
t = (n • Q - d) / (n • n) 이다. 평면에서 한 점으로 가는 가장 가까운 점은 그러므로 다음이 된다:

Point ClosestPtPointPlane(Point q, Plane p)
{
     float t = (Dot(p.n,q) - p.d) / Dot(p.n, p.n);
     return q - t * p.n;
}

만약 그 평면의 방정식이 표준화되었다고 알려진다면, 이것은 t = (n • Q - d) 로 간단하게 되고 다음을 준다:

Point ClosestPtPointPlane(Point q, Plane p)
{
     float t = (Dot(p.n,q) - p.d);
     return q - t * p.n;
}

평면에서 Q의 양의 거리는 t의 연산된 값을 반환하여 주어진다:

float DistPointPlane(Point q, Plane p)
{
     // return Dot(q, p.n) - p.d; if plane equation normalized (||p.n|| == 1)
     return (Dot(p.n, q) - p.d) / Dot(p.n, p.n);
}

5.1.2 Closest Point on Line Segment to Point
AB가 끝점 A와 B로 명시된 선분이라고 하자. 임의의 점 C가 주어진다면, 그 문제는 C와 가장 가까운 AB위의 점 D를 결정하는 것이다. 그림 5.2에서 보여지듯이, C를 AB를 지나는 연장된 직선에 사영하는 것은 그 해결책을 제공한다. 만약 그 사영점 P가 선분 내에 있다면, P는 그 자체로 정확한 답이다. 만약 P가 그 선분의 밖에 있다면, 가장 가까운 점은C에 가장 가까운 선분의 끝점이 된다.

AB를 지나는 직선위의 어떤 점은 parametrically하게 P(t) = A + t(B-A)로 표현될 수 있따. 내적의 사영 특성을 사용하여, C의 line으로의 사영에 대응되는 것은
t = (C - A) • n / ||B - A|| 로 주어지고, 여기에서 n = (B - A) / ||B - A|| 인 AB 방향의 단위 벡터이다.

{
너가 그림 그려서 해본다면 저 t가 왜 나온지 쉽게 알 수 있다.
다음의 코드를 위해서 t를 제대로 표현한다면

이렇게 된다, n에서 ||B-A||를 빼왔다.

사실 내 생각에 정확히 P(t)를 표현하자면
t가 1일 때 B이고, 0일 때 A이기 위해서 P(t)가 저렇게 쓰였고,
t가 저렇게 구해진다.
}

line segment의 가장가까운 점이 요구되기 때문에, t는 0<= t <= 1의 간격으로 clamped 되어야 한다, 그 후에 D는 t를 parametric equation으로 대체하여 얻어질 수 있다. 구현된다면,이것이 된다:

// Given segment ab and point c, computes closest point d on ab.
// Also returns t for the position of d, d(t) = a + t * (b - a)
void ClosestPtPointSegment(Point c, Point a, Point b, float& t, Point& d)
{
     Vector ab = b - a;
     // Project c onto ab, computing parameterized position d(t) = a + t * (b - a)
     t = Dot(c - a, ab) / Dot(ab, ab);
     // If outside segment, calmp t (and therefore d) to the closest endpoint
     if(t < 0.0f) t = 0.0f;
     if(t > 1.0f) t = 1.0f;
     // Compute projected position from the clamped t
     d = a + t * ab;
}

만약 나누기가 비싸다면, 그 나누기 연산은 분모로 비교하는 양 변을 곱하여 지연될 수 있다, 그리고 그 square term으로서의 그것으 음수가 아닌 것이 보장된다. 이 방식으로 최적화하여 그 코드는 다음이 된다:

// Given segment ab and point c, computes closest point d on ab.
// Also returns t for the position of d, d(t) = a + t * (b - a)
void ClosestPtPointSegment(Point c, Point a, Point b, float& t, Point& d)
{
     Vector ab = b - a;
     // Project c onto ab, but deferring divide by Dot(ab, ab)
     t = Dot(c - a, ab);
     if (t <= 0.0f)
     {
          // c projects outside the [a,b] interval, on the a side; clamp to a
          t = 0.0f;
          d = a;
     }
     else
     {
          float denom = Dot(ab, ab);
          if (t >= denom)
          {
               // c projects outside the [a,b] interval, on the b side; clamp to b
               t = 1.0f;
               d = b;
          }
          else
          {
               // c projects inside the [a,b] interval; must do deferred divide now
               t = t / denom;
               d = a + t * ab;
          }
     }
}

그 같은기본 방법들은 ray위에 있는 가장 가까운 점을 찾거나, 직선 위에 있는 가장 가까운 점을 찾는데 사용될 수 있다. 한 ray에 대해, t가 음수가 될 때 그것을 clamp하는게 필수적이다. 한 line에 대해 t를 clamp할 필요가 없다.

5.1.2.1 Distance of Point to Segment
한 점 C와 선분 AB 사이의 제곱 거리는 직접적으로 AB위에서 C에 가장 가까운 점 D를 explicitly하게 연산하지 않고 연산되어질 수 있다. 이전의 섹션에서 처럼, 고려해야 할 세 개의 경우들이 있다. AC•AB <= 0일 떄, A가 C와 가장 가깝고, 그 제곱 거리는 AC•AC로 주어진다. AC • AB >= AB • AB일 때, (즉 t가 1일 때) B가 C에 가장 가까운 점이고, 그 제곱거리는 BC • BC이다. 나머지 경우는 0 < AC • AB < AB • AB (즉, 0 < t < 1)인 겨우인데, 그 제곱 거리는 CD • CD로 주어진다, 거기에서

D = A + (AC • AB)/(AB • AB) AB

이고, 그러나, 그 수식 CD • CD 는 다음으로 간단하게 된다

AC • AC -  (AC • AB)^2 / AB • AB.   (즉, 피타고라스 정리에 의해 구한 것이다.)

이렇게 되므로, D가 요구되지 않는다. 몇 가지 subterms들이 재발하기 때문에, 그 구현은 효율적으로 다음으로 쓰여질 수 있다:

// Returns the squared distance between point c and segment ab
float SqDistPointSegment(Point a, Point b, Point c)
{
     Vector ab = b - a, ac = c - a, bc = c - b;
     float e = Dot(ac, ab);
     // Handle cases where c projects outside ab
     if(e <= 0.0f) return Dot(ac, ac);
     float f = Dot(ab, ab);
     if (e >= f) return Dot(bc, bc);
     // Handle cases where c projects onto ab
     return Dot(ac, ac) - e * e / f;
}

5.1.3 Closest Point on AABB to Point
B가 axis-aligned bounding box이고, P가 공간에서 임의의 점이라고 하자. P에 가장 가까운 B 위에 (또는 안에) 있는 점 Q는 P를 B의 bounds에 componentwise basis에 clamping하여 얻어진다. clamping이 바람직한 결과를 주는지 확인하기위해 고려해야 할 네 가지 경우들이 있다. 만약 P가 B안에 있다면, 그 clamped point는 P 그 자체이고, 그것은 또한 P에 가장 가까운 B안에 있는 점이다. 만약 P가 B의 face Voronoi region에 있다면, 그 clamping operation은 P를 B의 그 face로 가져올 것이다. (Voronoi regions은 Chapter 3에서 소개되었다.) 그 clmaping은 P에서 B로의 orthogonal projection과 일치하고, 그러므로 B에서 가장 가까운 점을 만들어 내야 한다. P가 B의 vertex Voronoi region일 때, P를 clamping하는 것은 그 정점을 한 결과로서 주고, 그리고 그것은 또 다시 B에서의 가장 가까운 정점이다. 마지막으로, P가 edge Voronoi region에 있을 때, P를 clamping하는 것은 edge로의 orthogonal projection과 일치하고, 그것은 또한 P로가는 B에서의 가장 가까운 점임에 틀림 없다. 이 절차는 2,3차원 둘 다에서 작동한다. 2D box에 대한 clmaping procedure는 그림 5.3에서 보여진다, edge Vornoi region (a)에 놓여있는 점 P에 대해, 그리고 vertex Voronoi region(b)에 대해.

다음의 코드는 가장 가까운 점 operation을 구현한다:

// Given point p, return the point q on or in AABB b that is closest to p
void ClosestPtPointAABB(Point p, AABB b, Point& q)
{
     // For each coordinate axis, if the point coordinate value is
     // outside box, clamp it to the box,else keep it as is
     for(int i = 0; i < 3; ++i)
     {
          float v = p[i];
          if(v < b.min[i]) v = b.min[i]; // v = max(v, b.min[i])
          if(v > b.max[i]) v = b.max[i]; // v = min(v, b.max[i])
          q[i] = v;
     }
}

{
이게 어떻게 되는지 잘 이해가 안되지만, 직관적으로 이해하자면, 각 axis에 대해 가장 가까운 점은 min < q < max 가 되도록 한다고 생각하면 된다.
그러니까 component wise하게, 그것이 min보다 작으면 min이되게하고, max보다 크면 max가  되게하여 그 사이 값에 들어가게 된다. 그러나, min max사이에 있다면 그대로 유지한다. 그러면 잘 된다. 
}

SIMD 명령어를 지원하는 CPU 아키텍쳐에서, 이 함수는 종종 그냥 두 개의 명령어로 구현되어질 수 있다: max instruction 다음에 min instruction!

5.1.3.1 Distance of Point to AABB
한 주어진 점 P에 가장 가까운 한 AABB B위에 있는 점 Q가  P와 Q사이의 거리를 결정하기 위해 연산될 때, 그 거리는 Q를 explicitly하게 얻어서 연산되어질 수 있따. 이것은 다음의 코드에 의해 그려진다. 계산을 간단히하고, 비싼 square root call을 피하기 위해서, 제곱 거리가 연산된다.

// Computes the square distance between a point p and an AABB b
float SqDistPointAABB(Point p, AABB b)
{
     float sqDist = 0.0f;
     for(int i = 0; i < 3; ++i)
     {
          // For each axis count any excess distance outside box extents
          float v = p[i];
          if(v < b.min[i]) sqDist += (b.min[i] - v) * (b.min[i] -  v);
          if(v > b.max[i]) sqDist += (v - b.max[i]) * (v - b.max[i]);
     }
     return sqDist;
}

{
이 코드가 어떻게 작동하냐면,
clamped 될 때, 그 clamped 되는 거리 (차이)가 거리를 구하기 위한 요소가 된다.
clamped 되지 않는다면,  그 컴포넌트에 대해서는 그 AABB에 대해 같은 요소에 있기 때문에 구할 필요가 없다.
}

5.1.4 Closest Point on OBB to Point
B가 중심점 C가 주어진 OBB라고 하자; 세 개의 orthogonal unit vectors u_0, u_1, 그리고 u_2가 B의 x,y,z 축들의 방향을 명시한다고 하자; 그리고 세 개의 스칼라 값 e0, e1, e2가 각 축에 따라 box halfwidths를 명시한다고 하자 (그림 5.4). 이 표기법에서), B에 의해 포함되는 모든 점들 S는 S = C + au_0 + bu_1 + cu_2로 쓰여질 수 있고, |a| <= e_0, |b| <= e1, |c| <= e2 이다.

world space에있는 한 점 P는 OBB의 좌표계에서 그것의 대응되는 점 Q = (x,y,z)와 대응되는데 P = C + xu_0 + yu_1 + zu_2로서 된다.  P가 주어진다면, 그 OBB-space 좌표들은 다음으로 해결될 수 있다. 그 x좌표의 유도는 여기에서 보여진다. 그 다른 좌표들은 비슷한 방식으로 해결되어질 수 있다.



OBB 좌표들의 full set은 따라서 다음으로 주어진다

x = (P - C) • u_0
y = (P - C) • u_1
z = (P - C) • u_2

P에 가장 가까운 B 위에 (또는 안에) 있는 점 R을 연산하기 위해서, AABB에 대해 사용된 같은 접근법이 P를 OBB 좌표에서 Q로 표현하여 적용되어질수 있고, Q를 e0, e1, e2의 길이로 clamping하고, Q를 월드 좌표계로 다시 표현하여 된다. 이것에 대한 코드는 다음과 같다.

// Given point p, return point q on (or in) OBB b, closest to p
void ClosestPtPointOBB(Point p, OBB b, Point& q)
{
     Vector d = p - b.c;
     // Start result at center of box; make steps from there
     q = b.c;
     // For each OBB axis
     for(int i = 0; i < 3; ++i)
     {
          // ...project d onto that axis to get the distance
          // along the axis of d from the box center
          float dist = Dot(d, b.u[i]);
          // If distance farther than the box extents, clamp to the box
          if(dist > b.e[i]) dist = b.e[i];
          if(dist < -b.e[i]) dist = -b.e[i];
          // Step that distance along the axis to get world coordinate
          q += dist * b.u[i];
     }
}

{
상당히 여기 공부할 때 선형대수가 가장 많이 쓰인다. 좌표계 변환에 대해 나의 뇌를 적응하게 하기 위해서, 항상 반복 공부해야 한다. 그래서 여기에서 좀 제대로 써보자.

먼저 좌표계변환, 그러니까 기저 변환에 대해서 설명해보자.

뭔저 위의 예시에 맞게 World Coordinate Space와 Local Space라고 하고,  두 개를 W와 L로 칭하겠다.

우리는 W<->L 간에 변화를 쉽게 해야 한다.

선형대수에 따르면, W<->L로 한 벡터의 좌표계를 바꾸는 행렬에 대해서 말하자면

W<-L : 즉, Local Space에서 World Space로 바꿀 때, Local의 기저들을 World의 기저들의 관점에서 표현하는 행렬이다. 즉, Local의 기저들을 u0, u1, u2라고 하자.



위의 예제에 따르면 u0, u1, u2는 R^3에서 표현되어 있기 때문에, 이것은 Local Space의 기저들을 world space의 기저로 표현한 것과 다름 없다. 그래서



그러므로,



직관적으로 설명하자면 Local의 기저들을 World Space에서 표현했고, 그 local space의 vector를 P(W<-L)에 곱하게 된다면, world space에서의 좌표가 나오게 된다.

좀 더 직관적인 설명은 v_local 이 (1, 0, 0)이라 하면은 그 v'_world = (u0.x, u0.y, u0.z)가 되어서, Local의 x축을 world space로 표현하게 된다.

그렇다면 그 반대인 World Space -> Local Space는 무엇인가?
우리가 잘 알듯이, P(W<-L)의 역행렬을 취하면 되고, 거기에다가 그 행렬이 orthogonality의 특성이 있기 때문에 transpose(전치행렬)을 취하면 된다. 따라서


그리고 더 정확하게 말하자면 World Space의 기저들을 Local Space의 관점에서 표현한 것이다.

그러므로


이게 되고,



이렇게 된다. 따라서, 이제 우리는 위의 코드를 이해할 준비가 되었다.

(여기에서 기저변환 행렬의 elements들을 보면 왜 이렇게 해야 되는지 무언가 직관적인 이해가 오는 것 같다. P(W<-L) 같은 경우는 Local Space기저를 World로 표현하니, Local 벡터를 거기에 곱한다면 바로 World Vector가 나온다는게 직관적으로 이해된다. P(L<-W)가 좀 잘 이해가 안됐는데, World Space의 기저들을 Local Space로 표현한다는게, Local Basis들의 X component가 (1,0,0)을 Local X-axis를 표현하게 된다. 여튼 이런식으로 직관적 이해를하는 것은 기억력에 많은 도움이 될 것이다.)

이전의 AABB 처럼 clmaping 방식대로 한 축에 대해서 진행된다는 것에 주의해라.
하지만 이번엔 OBB의 local space 대로 한다.

우선 벡터 d = p - b.c를 통해 b의 center point에서 p로 가는 벡터를 구해놓는다.
이제 이것을 clamping 할껀데, OBB의 local space에서 진행한다.

q = b.c로 나중의 world space로 바꿀 때 편하게 하기 위해 이렇게 해놓는다.

그리고 반복문에서 첫 명령어로

float dist = Dot(d, b.u[i])가 되는데,

d라는 world space벡터를 b의 local space로 바꿔야 한다.


이렇게 되고, dot(d, b.u[i])를 통해 local space의 x축에 대한 dist를 알게 된다.
그래서 이 dist가 b.e[i]보다 크다면 b.e[i]로 clamp하고
dist가 -b.e[i]보다 작으면 dist = -b.e[i]로 clamp해서 사영시킨다.

그리고 나서 우리는 다시 그 거리를 world coordinate로 바꾸어야 한다.

즉,


여기에서 상당히 헷갈릴 수 있는데,

우리는 위의 행렬을 가지고 있고, v_local에서 x component만 가지고 있다는 것을 다시 기억해라.

그렇다면 P(W<-L) * (x, 0, 0)과 같게 되고, 이것은 dist * b.u[i] 와 똑같이 된다.
이제야 q += dist * b.u[i]가 이해 될 것이다.

우리는 이제 이것을 행렬로 표현하는 방법을 알게 될 것이다.

즉, OBB space에서 사영된 벡터 k를 구하고
P(W<-L) * k를 한 것을 q에 더해줘도 같은 결과이다.
}

수학적으로, 설명되는 방법은 점 P를 OBB의 local 좌표계로 변환하고, 변환된 점에 가장 가까운 OBB 위에 있는 점을 (이제 효과적으로 AABB와 같다) 연산하고, 그 결과 point를 다시 world coordinates로 변환하는 것과 같다.

5.1.4.1 Distance of Point to OBB
점 P와 OBB B 위의 가장 가까운 점 사이의 제곱 거리를 얻기 위해서, 이전 함수는 이 방식으로 호출될 수 있다:

// Computes the square distance between pointp and OBB b
float SqDistPointOBB(Point p, OBB b)
{
     Point closest;
     ClosestPtPointOBB(p, b, closest);
     float sqDist = Dot(closest - p, closest - p);
     return sqDist;
}

만약 가장 가까운 점이 아닌 squared distance만 필요하다면, 이 코드는 더욱 간단하게 될 수 있따. B의 center로부터의 P까지의 벡터 v를 세 개의 OBB axes의 각각에 사영하여, P에서 각 axis를 따른 box center 까지의 거리 d가 얻어진다.

// Compute the square distance between point p and OBB b
float SqDistPointOBB(Point p, OBB b)
{
     Vector v = p - b.c;
     float sqDist = 0.0f;
     for (int i = 0; i < 3; ++i)
     {
          // Project vector from box center to p on each axis, getting the distance
          // of p along that axis, and count any excess distance outside box extents
          float d = Dot(v, b.u[i]), excess = 0.0f;
          if(d < -b.e[i])
               excess = d + b.e[i];
          else if(d > b.e[i])
               excess = d - b.e[i];
          sqDist += excess * excess;
     }
     return sqDist;
}

{
기저 변환을 잘 이해했다면 위의 코드가 이제 쉽다. AABB에서 clamping 함과 동시에 어떻게 Dist를 구했는지를 기억해라. 그냥 그 사영되어지는 지점과 점의 차이 만큼 제곱을한 것이다. 그래서 OBB의 space로 좌표계를 변환하면, e라는 벡터의 각 컴포넌트가 min, max와 같게 되는 것이다. 그래서 그것들을 초과한 만큼의 거리를 구하고 그것을 제곱하면 거리가 된다. 이것은 선형변환에서는 벡터의 크기를 바꾸지 않기 때문에, 다시 world space로 돌릴 필요가 없다!
}

5.1.4.2 Closest Point on 3D Rectangle to Point
한 주어진 점 P에 가장 가까운 3D rectangular R 위에 있는 점 Q를 결정하는 것은 가상적으로 OBB 위에 있는 가장 가까운 점을 찾는 문제와 같다. 3D rectangle이 z축을 따라서 zero extent를 가진 OBB라고 보여질 수 있다는 점에서이다.

그러듯이, 한 Rectangle은 center point C에 의해 정의되고, R의 x와 y축의 방향을 명시하는  두 개의 orthogonal unit vectors u0과 u1과, 각 축을 따라 rectangle halfwidth extents를 명시하는 e0과 e1의 두 개의 스칼라 값으로 정의된다. 이 표기법에서, R에 의해 포함되는 모든 점들은 S는 S = C + au0 + bu1 에의해 주어지고, |a| <= e0이고 |b| <= e1이다. 코드로 표현된다면, 이 rectangle structure는 다음 처럼 된다:

struct Rect
{
 glm::vec3 c; // center point of rectangle
 glm::vec3 u[2]; // unit vectors determining local x and y axes for rectangle
 float e[2]; // the halfwidth extents of the rectangle along the axes
};

zero-extent z axis 고려하는 ClosestPtPointOBB()를 다시 쓰는 것은 3D rectangle에서 가장 가까운 점을 찾는 것에 대해 다음의 코드를 만들어낸다.

void RTCD::ClosestPtPointRect(const Point & p, const Rect & r, Point & q)
{
 glm::vec3 d = p - r.c;
 // Start result at center of rect; make steps from there
 q = r.c;
 // For each rect axis...
 for (int i = 0; i < 2; ++i)
 {
  // ...project d onto that axis to get the distance
  // along the axis of d from the rect center
  float dist = glm::dot(d, r.u[i]);
  // If distance farther than the rect extents, clamp to the rect
  if (dist > r.e[i]) dist = r.e[i];
  if (dist < -r.e[i]) dist = -r.e[i];
  // Step that distance along the axis to get world coordinate
  q += dist * r.u[i];
 }
}

3D rectangle R은 또한 세 개의 점들에 의해서 주어지는데 (A, B, C), B - A와 C - A벡터가 그 rectangle을 span하도록 한다. R에 있는 모든 점들 S는 이제 S = A + u(B - A) + v(C - A)에 의해 주어지고, 0<=u<=1 이고 0<=v<=1이다. 이 시나리오 에서, 비슷한 projection approach는 사용될 수 있다 (그러나 새로운 clamping intervals에 대해 조정된다). 이 경우에 대한 구현을 최적화하는 것은 다음의 코드를 만들어낸다.

// Return point q on (or in) rect (specified by a, b, and c), closeset to given point p
void RTCD::ClosestPtPointRect(
 const Point & p, 
 const Point & a, const Point & b, const Point & c, 
 Point & q)
{
 glm::vec3 ab = b - a; // Vector across rect
 glm::vec3 ac = c - a; // vector down rect
 glm::vec3 d = p - a;
 // Start result at top-left corner of rect; make steps from there
 q = a;
 // Clamp p' (projection of p to plane of r) to rectangle in the across direction
 float dist = glm::dot(d, ab);
 float maxdist = glm::dot(ab, ab);
 if (dist >= maxdist)
  q += ab;
 else if (dist > real(0.0))
  q += (dist / maxdist) * ab;
 // Clamp p' (projection of p to plane of r) to rectangle in the down direction
 dist = glm::dot(d, ac);
 maxdist = glm::dot(ac, ac);
 if (dist >= maxdist)
  q += ac;
 else if (dist > real(0.0))
  q += (dist / maxdist) * ac;
}

{
이 코드를 간단하게 생각하자면, a가 top-left corner이고, b가 오른쪽에 있고
c가 아래쪽에 있다고 가정하자.

먼저 p가 ab 변의 왼쪽 위 또는 그 변의 위 또는 오른쪽 위라고 생각한다면
왜 코드가 저렇게 되어있는지 알게 될 것이다. 그 변에 d를 사영시켜서 하는 것이다.

ac에 대한 것도 위와 같은 방식으로 하면 된다.
}

이것은 초기의 접근법보다 조금 더 비싸다, 왜냐하면 그것은 precalculation step 동안에 rectangle의 across and down vector의 표준화로부터 이익을 얻지 않기 때문이다.

5.1.5 Closest Point on Triangle to Point
삼각형 ABC가 주어진다면, 그리고 한 점 P가 주어진다면, Q를 P에 가장 가까운 ABC 위에 있는 점으로 설명하자. Q를 얻는 한 방법은 만약 P가 ABC 안으로 orthogonally하게 사영된다면, 그 projection point가 가장 가까운 Q라는 사실에 의존한다. 만약 P가 ABC 밖에 사영된다면, 그 가장 가까운 점은 그것의 edges들 중 하나에 놓여있다. 이 경우에, Q는 선분 AB, BC CA의 각각에 대해 가장 가까운 점을 연산하고, P에 대해 가장 가까운 점을 반환한다. 비록 이것이 작동할지라도, 이것은 매우 효율적인 접근법은 아니다. 더 좋은 솔루션은 그 삼각형의 Voronoi feature regions 어디에 P가 있는지를 연산하는 것이다.

P의 대응되는 feature로 orthogonal projection이 결정된다면, 그것은 Q를 얻기위해 연산되어야 한다.

P가 vertex Voronoi region안에 있는지 결정될 수 있는지 보기 위해서, A의 vertex Voronoi region을 고려해라. 이 지역은 A를 지나는 두 개의 평면의 negative halfspaces의 교차로 결정된다. 하나는 B - A의 normal를 가진 평면이고, 다른 하나는 C - A normal를 가진 평면이다.

P가 edge Voronoi regions중의 하나에 있는지 결정하는 것은 많은 방식들로 처리될 수 있다. 한 효율적인 테스트는 효과적으로 P의 ABC로의 orthogonal projection인 R의 barycentric coordinates를 연산하는 것으로 밝혀졌다. Section 3.4로부터 R의 무게중심 좌표들이 삼각형 ABC에 대해 삼각형 RAB, RBC, 그리고 RCA의 양의 넓이의 비율로서 주어진다는 것을 회상해라. n이 삼각형 ABC의 normal이라고 하고, 어떤 t에 대해 R = P - tn이라고 하자. R의 barycentric coordinates (u,v,w)는 그러고나서 다음의 양들로 연산되어질 수 있다

Vector n = Cross(b - a, c - a);
float rab = Dot(n, Cross(a - r, b - r)); // proportional to signed area of RAB
float rbc = Dot(n, Cross(b - r, c - r)); // proportional to signed area of RBC
float rca = Dot(n, Cross(c - r, a - r)); // proportional to signed area of RCA
float abc = rab + rbc + rca; // proportional to signed area of ABC

u = rbc/abc, v = rca/abc, w = rab/abc이기 때문이다. 그러나,작은 vector arithmetic은 이러한 수식들을 간단하게 된다는것을 보여준다. 예를들어, rab에 대한수식은 다음으로 간단하게 된다:



다시 말해서, R의 무게 중심 좌표는 R을 연산하는 것 없이 P로부터 직접적으로 얻어질 수 있다.

edge Voronoi region에 있는 P에 대해, 예를들어, edge AB에 대응되는 것, P는 AB 위에 또는 밖에 놓여있어야만 한다. 그리고 이것은 rab <= 0으로 나타내어지고, 뿐만 아내라 planes의 positive halfspaces 내에서, dot((X-A), (B-A) = 0이고 dot((X-B), (A-B) = 0이여야 한다. P가 AB 밖에 있는지를 테스트하는것은 충분하지 않다는 것에 주목해라, A에 둔각을 가진 삼각형에 대해P가 AB 밖에 있을 수 있고, 실제로 edgeCA의 Voronoi region에 위치할지도 모른다는 점에서 (그림 5.6).  (유사하게, 예를들어, P가 AB 밖에 놓여있고 dot((P-A), (B - A) < 0 이면  A가 P의 가장 가까운 점이라고 가정하는 것은 흔한 실수이다.) 만약 P가 vertex or edge Voronoi regions중 어떠한 것에서도 있다고 발견되지 않는다면, Q는 ABC 안에 있어야만 하고, 사실, orthogonal projection R이 되어야 한다, 그리고 이것은 이제 쉽게 이전 것으로 연산되어질 수 있다. 이 정보는 이제 code solution을 만들어 내기에 충분하다.

Point RTCD::CloseestPtPointTriangle(const Point & p, const Point & a, const Point & b, const Point & c)
{
 glm::vec3 ab = b - a;
 glm::vec3 ac = c - a;
 glm::vec3 bc = c - b;

 // Compute parametric position s for projection P' of P on AB,
 // P' = A + s * AB, s = snom / (snom + sdenom)
 real snom = glm::dot(p - a, ab), sdenom = glm::dot(p - b, a - b);

 // Compute parametric position t for projection P' of P on AC,
 // P' = A + t * AC, s = tnom/(tnom + tdenom)
 real tnom = glm::dot(p - a, ac), tdenom = glm::dot(p - c, a - c);

 if (snom <= real(0.0) && tnom <= real(0.0)) return a; // Vertex region early out

 // Compute parametric position u for projection P' of P on BC,
 // P' = B + u * BC, u = unom/(unom + udenom)
 real unom = glm::dot(p - b, bc), udenom = glm::dot(p - c, b - c);

 if (sdenom <= real(0.0) && unom <= real(0.0)) return b; // Vertex region early out
 if (tdenom <= real(0.0) && udenom <= real(0.0)) return c; // Vertex region early out

 // P is outside (or on) AB if the triple sclar product [N PA PB] <= 0
 // testing if P lies on Edge Voronoi Region
 glm::vec3 n = glm::cross(ab, ac);
 real vc = glm::dot(n, glm::cross(a - p, b - p));
 // If P outside AB and within feature region of AB,
 // return projection of P onto AB
 if (vc <= real(0.0) && snom >= real(0.0) && sdenom >= real(0.0))
  return a + snom / (snom + sdenom) * ab;

 // P is outside (or on) BC if the triple scalar product [N PB PC] <= 0
 real va = glm::dot(n, glm::cross(b - p, c - p));
 // If P outside BC and within feature region of BC,
 // return projection of P onto BC
 if (va <= real(0.0) && unom >= real(0.0) && udenom >= real(0.0))
  return b + unom / (unom + udenom) * bc;

 // P is outside (or on) CA if the triple scalar product [N PC PA] <= 0
 real vb = glm::dot(n, glm::cross(c - p, a - p));
 // If P outside CA and within feature region of CA,
 // return projection of P onto CA
 if (vb <= real(0.0) && tnom >= real(0.0) && tdenom >= real(0.0))
  return a + tnom / (tnom + tdenom) * ac;

 // P must project inside face region. Compute Q using barycentric coordinates
 real u = va / (va + vb + vc);
 real v = vb / (va + vb + vc);
 real w = real(1.0) - u - v; // = vc / (va + vb + vc)
 return u * a + v * b + w * c;
}

{
상당히 어려운 로직이였지만 책에 나와 있는데로 순서대로 따라가면 코드가 이해된다.
먼저 vertex region에 대해 각각 검사한다. 각 삼각형의 변을 normal로 하는 두 개의 평면들의 negative halfspace에 동시에 있으면 vertex region이 판명되므로 그에 해당되는 vertex를 반환한다.

그게 아니면 이제 edge region에서 판단한다. 그래서 barycentric coordinate 특성에 의해서, 그리고 수식을 연산을 간단히해서 {N PX1 PX2]의 스칼라 삼중적이 음수이면 Edge 가능성이 있고, 거기에다가, edge region에 있는지 확실히 하기 위해 그것이 그 변위에 사영되는 것을 판단하여 즉 (snom >= real(0.0) && sdenom >= real(0.0)) 이 부분이 그 변 위에 있는지를 보는 것이다. 그렇게 된다면, 그 점 p가 있는 비율을 계산하여, 해당점과 가장 가까운 점을 반환한다.

그것도 아니라면, 점 P는 삼각형의 면 위에 있는 것이므로, barycentric 좌표를 그냥 구하여 반환한다.
}

보여지듯이, 이 코드는 4개의 외적 호출을 포함한다. 외적은 내적보다 계산하기에 좀 더 비싸기 때문에, 이러한 것들이 경제적인 수식들로 대체될 수 있는지를 보는 것은 조사할 가치가 있다. 그 Lagrange identity



는 그 세 개의 삼중적을 6개의 내적으로 표현할 수 있다.

사실, 이러한 6개의 내적들, d1에서 d6은 snom, sdenom, tnom, tdenom, unom, 그리고 udenom항들을 또한 계산하는데 사용되어질 수 있다:

그 벡터 n은 더 이상 필요하지 않다. 이것은 그 코드가 최정 버전으로 최적화되도록 허용한다.

Point RTCD::FastClosestPtPointTriangle(const Point & p, const Point & a, const Point & b, const Point & c)
{
 // Check if P in vertex region outside A
 glm::vec3 ab = b - a;
 glm::vec3 ac = c - a;
 glm::vec3 ap = p - a;
 real d1 = glm::dot(ab, ap);
 real d2 = glm::dot(ac, ap);
 if (d1 <= real(0.0) && d2 <= real(0.0)) return a; // barycentric coordinates (1,0,0)

 // Check if P in vertex region outside B
 glm::vec3 bp = p - b;
 real d3 = glm::dot(ab, bp);
 real d4 = glm::dot(ac, bp);
 if (d3 >= real(0.0) && d4 <= d3) return b; // barycentric coordinates (0,1,0)

 // Check if P in edge region of AB, if so return projection P onto AB
 real vc = d1 * d4 - d3 * d2;
 if (vc <= real(0.0) && d1 >= real(0.0) && d3 <= real(0.0))
 {
  real v = d1 / (d1 - d3);
  return a + v * ab;  // barycentric coordinates (1-v, v, 0)
 }

 // Check if P in vertex region outside C
 glm::vec3 cp = p - c;
 real d5 = glm::dot(ab, cp);
 real d6 = glm::dot(ac, cp);
 if (d6 >= real(0.0) && d5 <= d6) return c; // barycentric coordinate (0, 0, 1)
 
 // Check if P in edge region of AC, if so return projection of P onto AC
 real vb = d5 * d2 - d1 * d6;
 if (vb <= real(0.0) && d2 >= real(0.0) & d6 <= real(0.0))
 {
  real w = d2 / (d2 - d6);
  return a + w * ac; // barycentric coordinates (1-w, 0, w)
 }

 // Check if P in edge region of BC, if so return projection of P onto BC
 real va = d3 * d6 - d5 * d4;
 if (va <= real(0.0) && (d4 - d3) >= real(0.0) && (d5 - d6) >= real(0.0))
 {
  real w = (d4 - d3) / (d4 - d3) + (d5 - d6);
  return b + w * (c - b); // barycentric coordinates (0, 1 - w, w)
 }

 // P inside face region. COmpute Q through its barycentric coordinates (u,v,w)
 real denom = real(1.0) / (va + vb + vc);
 real v = vb * denom;
 real w = vc * denom;
 return a + ab * v + ac * w; // = u*a + v*b + w*c, u = va * denom = 1.0f - v - w
}

가장 가까운 점을 얻는 세 번째 방법은 벡터 적분 접근법을 사용하는 것이다, [Eberly01]에 제안되듯이. 간단히, 삼각형 ABC는 T(s, t) = A + s(B - A) + t (C - A)로 파라미터화 되고,
s >= 0, t>= 0이고, s + t <= 1이다. 주어진 점 P에 가장 가까운 점은 이제
d(s,t) = ||T(s,t) - P||^2 인 제곱 거리 함수의 최소값과 일치하는데, 이것은 s와 t에서의 이차식이다. 이 함수의 최소값은 세 가지 경우 중 하나에서 발생해야만 한다: vertex에서, edge에서, 또는 삼각형의 내부에서. 처음에 d(s,t)를 이러한 세 가지 경우에 관하여 미분하여, (즉, s = 0, t = 0, or t = 1- s 필요하다면), 그 도함수를 0으로 설정하고 풀고, 그러고나서 결과 s와 t를 triangle bounds와 비교하여, 어떤 경우가 최소에 대응되는지를 발견하는 것이 가능하다.

이 특별한 적용에 대해, 벡터 적분 해결책은 설명된 것 보다 복잡하다. 그러나, 그 문제를 quadratic minimization problem로서 보는 것의 일반적인 접근법은 가치가 있고, 그 같은 아이디어는 가령, 직선과 선분 그리고 삼각형 사이의 거리를 결정하기 위해 사용될 수 있다. pesudocode를 포함한 벡터 적분 접근법에 대한 부가적인 정보는 [Eberly01]에서 주어진다.

5.1.6 Closest Point on Tetrahedron to Point
한 점 P가 주어진다면, 그 문제는 사면체 ABCD에서 P에 가장 가까운 점 Q를 결정하는 것이다 (그림 5.7에서 그려지듯이). 간단한 솔루션은 사면체 P의 각 face plane에 대해 한 번씩 ClosestPtPointTriangle() 함수를 (이전 섹션에서 정의된) 호출하여 Q를 연산하는 것이다. 모든 연산된 점들 중에서, P의 가장 가까운 것이 Q로 반환된다. distance tests와 별개로, 다른 테스트가 P가 모든 face planes 안에 놓여있는지를 보기위해 만들어진다. 그럴 때, P는 그 자체로 가장 가까운 점이다.

tetrahedron ABCD가 그것의 면들 ABC, ACD, ADB, BDC가 그 tetraheron 밖에서 보아질 때 모두 시계 반대 방향으로 정돈되어 정의되었다고 가정한다면, 이 솔루션은 다음처럼 구현되어질 수 있따.

Point RTCD::ClosestPtPointTetrahedron(const Point & p, const Point & a, const Point & b, const Point & c, const Point & d)
{
 // Start out assuming point inside all halfspaces, so closest to itself
 Point closestPt = p;
 real bestSqDist = REAL_MAX;
 // If point outside face abc then compute closest point on abc
 if (PointOutsideOfPlane(p, a, b, c))
 {
  Point q = FastClosestPtPointTriangle(p, a, b, c);
  real sqDist = glm::dot(q - p, q - p);
  // Update best closest point if (squared) distance is less than current best
  if (sqDist < bestSqDist) bestSqDist = sqDist, closestPt = q;
 }
 // Repeat test for face acd
 if (PointOutsideOfPlane(p, a, c, d))
 {
  Point q = FastClosestPtPointTriangle(p, a, c, d);
  real sqDist = glm::dot(q - p, q - p);
  if (sqDist < bestSqDist) bestSqDist = sqDist, closestPt = q;
 }
 // Repeat test for face adb
 if (PointOutsideOfPlane(p, a, d, b))
 {
  Point q = FastClosestPtPointTriangle(p, a, d, b);
  real sqDist = glm::dot(q - p, q - p);
  if (sqDist < bestSqDist) bestSqDist = sqDist, closestPt = q;
 }
 // Repeat test for face bdc
 if (PointOutsideOfPlane(p, b, d, c))
 {
  Point q = FastClosestPtPointTriangle(p, b, d, c);
  real sqDist = glm::dot(q - p, q - p);
  if (sqDist < bestSqDist) bestSqDist = sqDist, closestPt = q;
 }
 return closestPt;
}

int RTCD::PointOutsideOfPlane(const Point & p, const Point & a, const Point & b, const Point & c)
{
 return glm::dot(p - a, glm::cross(b - a, c - a)) >= real(0.0);
}

여기에서 PointOutsideOFplane(P, A, B, C)의 값은 vectors P - A, B - A, C - A의 스칼라 삼중적의 부호와 일치한다.

종종 사면체 정점들의 winding이 사전에 알려져 있지 않다, 그리고 그것은 가령 면 ABC가 사면체 밖에서 보아질 떄 시계 반대 방향이라는 것이 가정될 수 없다는 것을 의미한다. 이 경우에, 그 해결책은 부가적으로 PointOutsideOfPlane()에 4번째 사면체의 정점을 넘기고, 그것과 테스트되는 점이 그 테스트되는 사면체 face의 반대면에 놓여있는지를 확실히 하는 것이다. 다시 말해서, 그 함수는 이렇게 된다:

// Test if point p and d lie on opposite sides of plane through abc
int RTCD::PointOutsideOfPlane(const Point & p, const Point & a, const Point & b, const Point & c, const Point & d)
{
 real signp = glm::dot(p - a, glm::cross(b - a, c - a)); // [AP AB AC]
 real signd = glm::dot(d - a, glm::cross(b - a, c - a)); // [AD AB AC]
 // Points on opposite sides if expression signs are opposite
 return signp * signd < real(0.0);
}

이 전반적인 접근법은 잘 작동하고, 구현하기에 쉽다. 그러나, 삼각형에서 가장 가까운 점을 찾는데 사용되는 같은 기본 방법을 적용하여, 좀 더 효율적인 솔루션을 유도하는게 가능하다. 처음에, 점 P가 위치한 Voronoi feature region이 결정된다. 그 feature가 얻어지기만 한다면, Q는 P의 이 feature로의 orthogonal projection이다. tetrahedron에 대해서, 고려되어야 할 14개의 전반적인 Voronoi feature regions가 있다: 4개의 vertex regions, 6개의 edge regions, 4개의 face regions. 만약 P가 그 feature regions 중 하나에도 있지 않다면, P는 기본적으로 사면체 안에 포함되었을 것이다. 한 feature region에서 포함되는 것에 대한 테스트들은 삼각형에 대해 이전에 만들어진 것과 유사하다. 예를들어, 만약 다음의 수식을 만족한다면, P가 이제 A의 vertex Voronoi region에 있다고 결정된다.



edge AB와 관련된 Voronoi region에 놓여있는 P에 대해, 다음의 테스트들이 만족되어야 한다( 또다시, 면들의 알려진 시계 반대방향의 winding이 가정하여)



유사한 수식들의 집합이 나머지 영역에서 containment를 테스트하기 위해 정의될 수 있따. 처음에 봐서, 이것은 이전 테스트에 대한 개선이 아닌 것처럼 보일지도 모른다. 그러나, 연산된 양은 다른 Voronoi regions 사이에서 공유되고 재 연산될 필요가 없다. 또한 closest-point-on-triagnle test에서 했던 최적화와 유사하게 Lagrange identity를 사용하여 Voronoi regions을 테스팅하는데 연관된 수식들을 간단하게 하는 것이 가능하다. 이 경우에, 모든 테스트들이 10개의 다른 내적의 관점으로 구성될 수 있다는 것이 밝혀진다.

5.1.7 Closest Point on Convex Polyhedron to Point
몇 가지 접근법들이 공간에 있는 한 점 P에 가장 가까운 convex polyhedron H에 있는 점을 찾는 것이 이용가능 하다. 구현하기에 간단한 O(n) method는 P에 가장 가까운 각 polyhedron face에서의 점을 연산하고, P와 가장 가까운 것을 반환한다. 동시에 작동되는 테스트는 P가 H의 모든 면 안에 놓여있는지를 결정한다, 그 경우에 P는 H의 내부에 있다. 그 테스트를 가속하기 위해서, 그 face distance calculation은 P가 face의 앞에 있을 때에만 작동되어야만 한다.

더 큰 polyhedra에 대해, 더 빠른 접근법은 precomputation으로서, polyheron의 부분들에 대한 hierarchy를 구성하는 것이다. 미리 연산된 hierarchy를 활용하는 것은 가장 가까운 점이 logarithmic time에 찾아지도록 한다. 그러한 hierarchy의 한 예시는 Dobkin-Kirkpatric hierarchy인데, Chapter 9에서 설명된다. Chapter 9는 또한 효율적으로 polyhedra에서 가장 가까운 점을 찾아낼 수 있는 다른 접근법들을 설명한다 (GJK 알고리즘 같은)

5.1.8 Closest Points of Two Lines
2차원에서 한 쌍의 직선들이 평행하지 않다면 항상 교차하는 반면에, 3차원에서 한 쌍의 직선들은 거의 결코 교차하지 않는다. 게다가, 비록 두 개의 3D 직선들이 정확한 실제의 연산에서 교차할지라도, 부동소수점 연산에서, 그것들의 꽤 그렇지 않을 가능성이 높다, rounding errors 때문에. 따라서 튼튼하게 두 개의 3D 직선들의 교차를 테스트할 수 있게 하기 위해, 직선들이 교차하지 않을 지도 모르지만, 서로에게 충분히 가깝다고 가정하는 것이 가장 좋다. 그 교차 테스트는 그러고나서 그 직선 사이의 거리를 결정하게 되고, 그 거리가 주어진 threshold value보다 더 작은지를 체크한다.

두 직선의 가장 가까운 점들은 다음과 같이 결정될 수 있다. 직선 L1과 L2가 점들 P1과 Q1그리고 P2와 Q2로 parametrically하게 명시되게 하자:



s와 t에 대한 어떤 값들의 쌍에 대해, L1(s)와 L2(t)는 직선들에서 가장 가까운 점들과 일치하고, v(s, t) = L_1(s) - L2(t) 이것은 그것들 사이의 한 벡터를 묘사한다 (그림 5.8).

그 점들은 v가 최소 길이 일 때 그것들이 가장 가까이에 있다. 그 주된 깨달음은 이것인 v가 L1과 L2 둘 다에 수직일 때 발생한다는 것이다. 이것을 보기 위해서, 한 점 P와 직선 L 사이의 최단 거리가 P에서 L로의 orthogonal projection과 일치하는 P와 Q사이의 직선 거리라는 것을 고려해라. 결과적으로 그 직선 PQ는 L에 직교한다. 이 추론은 L2에 관해 L1(s)에 유효하고, L1에 대해 L2(t)에도 둘 다 유효하기 떄문에, v는 두 직선에 수직해야만 한다. 평행하지 않은 직선들에 대해 v는 유일하다.

그 문제는 이제 이러한 두 개의 수직성 제약을 만족하는 s와 t에 대한 값을 찾는 것이다:



v(s,t)에 대한 parametric equation을 대체하는 것은 다음을 준다:



이것은 선형 방정식의 2x2 system으로 표현될 수 있다



여기에서 r = P1 - P2 이다.

symbolically하게 행렬 표기로 쓰여진다면, 이것은 다음과 같다



여기에서
a = d1 • d1
b = d1 • d2
c = d1 • r
e = d2 • d2
f = d1 • r

이예를들어 이 방정식은 Cramer의 규칙을 사용해서 풀어지고, 다음을 준다



여기에서  d = ae - b^2 이다. d >= 0이라는 것을 주목해라


라는 점에서. d가 0일 때, 두 직선은 평행하고, 별개로 다뤄져야 한다. 이 경우에, 어떤 점 P는 한 직선에서 선택되어질 수 있다. 다른 직선에서, P에 가장 가까운 점은 Section 5.1.2에서 설명된 projection method를 사용해서 선택된다.

{
원래는 s와 t의 d의 부호가 바껴야 하는데, 한 번더 -를 취해주어서 결과는 어차피 같다.
}

5.1.9 Closest Points of Two Line Segments
두 선분들 S1과 S2의 가장 가까운 점을 결정하는 문제



는 선분들이 한 일부인 직선 L1과 L2의 가장 가까운 점들을 연산하는 것 보다 더 복잡하다. L1과 L2의 가장 가까운 점이 선분위에만 놓여있을 때, 직선 사이의 가장 가까운 점에 대한 방법이 적용된다. 직선 L1과 L2 사이의 가장 가까운 점들이 한 개 또는 두 선분 밖에 놓여있는 경우에 대해, 흔한 잘못된 개념은, 그 바깥 점들을 가장 가까운 선분의 끝점으로 clamp하는 것이 충분하다는 것이다. 그러나, 그림 5.9의 케이스 (b)와 (c)가 보여주듯이, 이것은 유효한 가정은 아니다.

만약 직선들 사이의 가장 가까운 점들 중 하나가 그것의 대응되는 선분 밖에 있다면, 그 점은 그 선분의 적절한 끝점에 clamped 될 수 있고, 그 끝점에 가장 가까운 다른 선분의 점은 연산된다 [Lumelesky85]. 이것은 그림 5.9에서 case (B)와 일치한다, 거기에서 L1에서 가장 가까운 점은 선분 S1에 있는 끝점 Q1으로 clamped 된다. L2에서 Q1으로 가장 가까운 점인 R은 그러고나서 연산되고, 선분 S2위에서 발견된다. 이것은 가장 가까운점을 Q1과 R로서 남긴다.

만약 두 점들이 그것들의 각각의 선분 밖에 있다면, 그 같은 clamping 절차는 두 번 반복되어야 한다, 그림 5.9에서 case (c)에서 보이듯이. 또 댜시, L1에 있는 가장 가까운 점은 S1에서 Q1 끝점으로 clamped 된다. L2에서 Q1으로 가장 가까운 점 R이 연산된다. R이 선분 S2 밖에 있는 것으로 발견되기 때문에, 그것은 가장 가까운 segment endpoint Q2로 clamped된다. L1에서 Q2로의 가장 가까운 점 S는 그러고나서 연산되고, 이제 선분 S1에 있는 것으로 발견되고, Q2와 S를 가장 가까운 점으로 남긴다.

두 번째 선분 위에 있는 한 점 S2(t) = P_2 + td_2가 주어진다면, L1위에 있는 가장 가까운 점 L1(s)은 다음으로 주어진다



유사하게, S1위의 점 S1(s) = P_1 + sd_1이 주어진다면, L2위의 가장 가까운 점 L2(t)는 다음으로 연산된다



대안적으로, 가우스 소거법이 다른 것의 관점에서 미지수를 해결하기 위해 2x2 연립 선형 방정식에 사용될 수 있다. 둘 중 하나의 경우에 대해, s와 t에 대한 식은 다음으로 간단하게 된다



{
Cramer's rule로 안하고 그냥, 관계식으로 s와 t에 대해 나타낸다면
}



{
Cramer's rule로 나타낸다면
}


여기에서
a = d1 • d1
b = d1 • d2
c = d1 • r
e = d2 • d2
f = d2 • r
r = p1 - p2

이 함수를 구현하는 코드는 다음이다.

// Computes closest points C1 and C2 of S1(s) = P1 + s * (Q1 - P1) and
// S2(t) = P2 + t * (Q2 - P2), returning s and t. Function result is squared
// distance between S1(s) and S2(t)
real RTCD::ClosestPtSegmentSegment(const Point & p1, const Point & q1, const Point & p2, const Point & q2, real & s, real & t, Point & c1, Point & c2)
{
 glm::vec3 d1 = q1 - p1; // Direction vector of segment s1
 glm::vec3 d2 = q2 - p2; // Direction vector of segment s2
 glm::vec3 r = p1 - p2;
 real a = glm::dot(d1, d1); // Squared length of segment s1, always nonnegative
 real e = glm::dot(d2, d2); // Squared length of segment s2, always nonnegative
 real f = glm::dot(d2, r);

 // Check if either or both segments degenerate into points
 if (a <= EPSILON && e <= EPSILON)
 {
  // Both segments degenerate into points
  s = t = real(0.0);
  c1 = p1;
  c2 = p2;
  return glm::dot(c1 - c2, c1 - c2);
 }

 if (a <= EPSILON)
 {
  // First segment degenerates into a point
  s = real(0.0);
  t = f / e; // s = 0 => t = (b * s + f) / e = f / e
  t = Clamp(t, real(0.0), real(1.0));
 }
 else
 {
  real c = glm::dot(d1, r);
  if (e <= EPSILON)
  {
   // Second segment degenerates into a point
   t = real(0.0);
   s = Clamp(-c / a, real(0.0), real(1.0)); // t = 0 => s = (b * t - c) / a = -c / a
  }
  else
  {
   // The general nondegenerate case starts here
   real b = glm::dot(d1, d2);
   real denom = a * e - b * b; // Always nonnegative

   // If segments not parallel, compute closest point on L1 to L2 and
   // clamp to segment S1. ELse pick arbitrary s (here 0)
   if (denom != real(0.0))
    s = Clamp((b * f - c * e) / denom, real(0.0), real(1.0));
   else
    s = real(0.0);

   // Compute point on L2 closest to S1(s) using
   // t = Dot((P1 + D1 * s) - P2, DD2) / Dot(D2, D2) = (b * s + f) / e
   t = (b * s + f) / e;

   // If t in [0, 1] done. Else clamp t, recompute s for the new value
   // of t using s = Dot((P2 + D2 * t) - P1, D1) / Dot(D1, D1) = (t * b - c) / a
   // and clamp s to [0,1]
   if (t < real(0.0))
   {
    t = real(0.0);
    s = Clamp(-c / a, real(0.0), real(1.0));
   }
   else if (t > real(1.0))
   {
    t = real(1.0);
    s = Clamp((b - c) / a, real(0), real(1));
   }
  }
 }

 c1 = p1 + d1 * s;
 c2 = p2 + d2 * t;
 return glm::dot(c1 - c2, c1 - c2);
}

한 최적화로서, e로 나누는 것은 t가 range[0,1]의 범위에 있다고 알려질 때 까지 지연될 수 있따. 그리고 이것은 큰 else statement의 코드가 다음으로 읽어지게 만든다:

// Compute point on L2 closest to S1(s) using
// t = Dot((P1 + D1 * s) - P2, DD2) / Dot(D2, D2) = (b * s + f) / e
// t = (b * s + f) / e; => changed with the optimized one
real tnom = b * s + f;

// If t in [0, 1] done. Else clamp t, recompute s for the new value
// of t using s = Dot((P2 + D2 * t) - P1, D1) / Dot(D1, D1) = (t * b - c) / a
// and clamp s to [0,1]
if (tnom < real(0.0))
{
 t = real(0.0);
 s = Clamp(-c / a, real(0.0), real(1.0));
}
else if (tnom > e)
{
 t = real(1.0);
 s = Clamp((b - c) / a, real(0), real(1));
}
else
{
 t = tnom / e;
}

이 지연은 일반적인 겨웅에 종종 비싼 나누기 연산을 덜어준다.

5.1.9.1 2D Segment Intersection
두 개의 2D segments AB와 CD가 교차하는지를 테스트하는 것은 그것들의 연장된 선의 교차점을 연산하고, 그러고나서 그 교차점이 각 segment의 bounding box안에 있는지를 확인하여 처리될 수 있다. 예시로 그림 5.10a와 b를 참조해라. 평행인 직선들의 경우는 별개로 다뤄져야만 한다.

그 연장된 선 사이의 교차는 첫 번째 직선은 explicit form으로 쓰고, L1(t) = A + t(B - A), 그리고 두 번째 직선을 implicit form으로 n • (X - C) = 0, 써서 연산될 수 있다. 여기에서
n = (D - C)^\perp는 CD에 수직이다. 두 번째 방정식에서 미지의 점에 대한 첫 번째 직선의 방정식을 대체하고, 그러고나서 t에 대해 해결하는 것은 다음을 준다:



실제 교차점 P = L1(t)는 이제 t를 explicit equation에 넣어서 얻어질 수 있다. P가 AB의 bounding box에 놓여있는지를 테스팅하는 대안은 0 <= t <= 1을 확인하는 것이다.

2D 선분에 대한 대안의 overlap test는 선분이 둘 중 하나의 선분의 끝점들이 다른 선분을 지나는 연장된 직선의 다른 sides위에 위치한다면 교차한다는 통찰력에 기반할 수 있다. 즉, AB와 CD가 중첩되기 위해서, A와 B는 C와 D의 다른 sides에 있어야 하고, C와 D는 AB의 다른 sides에 있어야 한다.

끝점 C와 D가 AB의 다른 면에 있는지를 테스트하는 것은 삼각형 ABD와 ABC가 다른 방향으로 감기는지를 확인하여 처리될 수 있따 (그림 5.10c에 보여지듯이) 그 winding을 결정하기 위해, signed triangle area가 연산될 수 있다. 양의 넓이는 삼각형이 시계 반대방향으로 감기면 양수이고, 시계방향으로 감기면 음수이고, 삼각형이 degenerate라면 (collinear or coincident points) zero라는 것을 기억해라.

// Returns 2 times the signed triangle area. The result is positive if
// abc is ccw, negative if abc is cw, zero if abc is degenerate.
real RTCD::Signed2DTriArea(const Point & a, const Point & b, const Point & c)
{
 // perpdot(CA, CB)
 return (a.x - c.x) * (b.y - c.y) - (a.y - c.y) * (b.x - c.x);
}

선분들이 교차하고 있는 경우에, 이것을 탐지하기 위해 연산된 양의 넓이들이 또한 교차점을 연산하기 위해 사용될 수 있다는 것이 밝혀졌다. 그 연산과 그것의 유도는 다음의 구현에서 주어진다.

// Test if segments ab and cd overlap. If they do, compute and return
// intersection t value along ab and intersection position p
int RTCD::Test2DSegmentSegment(const Point & a, const Point & b, const Point & c, const Point & d, real & t, Point & p)
{
 // Sign of areas correspond to which side of ab points c and d are
 real a1 = Signed2DTriArea(a, b, d); // Compute winding of abd (+ or -)
 real a2 = Signed2DTriArea(a, b, c); // To intersect, must have sign opposite of a1

 // If c and d are on different sides of ab, areas have different signs
 if (a1 * a2 < real(0.0))
 {
  // Compute signs for a and b with respect to segment cd
  real a3 = Signed2DTriArea(c, d, a); // Compute winding of cda (+ or -)
  // Since area is constant a1 - a2 = a3 - a4, or a4 = a3 + a2 - a1
  real a4 = a3 + a2 - a1;
  // Points a and b on different sides of cd if areas have different signs
  if (a3 * a4 < real(0.0))
  {
   // Segments intersect. Find intersection point along L(t) = a + t * (b - a).
   // Given height h1 of an over cd and height h2 of b over cd,
   // t = h1 / (h1 - h2) = (b * h1/2 - b*h2/2) = a3 / (a3 - a4),
   // where b (the base of the triangles cda and cdb, i.e., the length
   // of cd) cancels out
   t = a3 / (a3 - a4);
   p = a + t * (b - a);
   return 1;
  }
 }
 // Segments not intersecting (or collinear)
 return 0;
}

여기에서 a1 * a2 < 0.0f 수식은 a1와 a2가 다른 기호를 가지는지 테스트하기 위해 사용된다 (a3와 a4에도 같다). 양의 정수와 작업할 때, 더 좋은 대안은 곱 대신에 exclusive-or를 사용하는 것이다, a1 ^ a2 < 0, 그것으로 인해 overflow를 가진 잠재적인 문제를 피할 수 있다. collinear points의 존재에서, a1과 a2 둘 다 또는 둘 중 하나가 0일지도 모른다. 이러한 경우에 적절한 교차를 탐지하기 위해서, 그 테스트는 다음의 라인들을 따라 쓰여야할 것이다:

if ( a1 != real(0.0) && a2 != real(0.0)&& a1 * a2 < real(0.0)) // for floating-point variables
if ((a1 | a2) != 0 && a1 ^ a2 < 0) ... // for integer variables

마지막으로, 어떤 프로그램에 대해, 이러한 선분 intersection tests를 진행하기 전에 AB와 CD의 bounding boxes가 중첩하는지를 테스트하는 것이 가치가 있다. 이것은 특히 3D에서 선분의 intersection을 결정하는데 유효하다. 그리고 그 때, 관련된 연산은 더 비싸다.

5.1.10 Closest Points of a Line Segment and a Triangle
선분 PQ와 삼각형 ABC 사이의 가장 가까운 점들의 쌍은 반드시 유일하지 않다. 그 선분이 삼각형의 평면과 평행할 때, 거의 동등하게 가까운 무한 개의 쌍들이 있을지도 모른다. 그러나, 선분이 평면과 평행한 것과 상관없이, 최소거리가 선분의 한 끝점과 삼각형의 내부 사이에 발생하거나(a) 또는 선분과 삼각형의 한 변에서 발생하도록(b) 점들을 찾는 것은 항상 가능하다. 이러한 두 경우들은 그림 5.11에서 보여진다.

Case(a)는 오직 한 선분의 supporting plane으로의 사영이 삼각형 내부에 있다면 발생할 수 있다. 그러나, 심지어 한 선분의 끝점이 삼각형 안으로 사영될 때, 그 삼각형의 한 변이 선분에 더 가까운 점을 제공할지도 모른다. 따라서, 점들의 가장 가까운 쌍은 entities 사이의 가장 가까운 점들의 쌍을 연산하여 발견될 수 있다.

선분 PQ와 삼각형 변 AB
선분 PQ와 삼각형 변 BC
선분 PQ와 삼각형 변 CA
선분 끝점 P와 삼각형의 평면 (P가 ABC 내부에 사영될 때)
선분 끝점 Q와 삼각형의 평면 (Q가 ABC 내부에 사영될 때)

그리고 전체의 가장 작은 최소 separating distance를 가진 쌍을 결과로서 반환한다.

요구되어지는 테스트들의 개수는 어떤 경우에 줄어들 수 있다. 예를들어, 두 끝점이 삼각형안에 사영될 때, 어떠한 segment-edge tests들은 필요하지 않다. 왜냐하면 end point projection 둘 중 하나가 가장 가까운 점과 일치하기 때문이다. 한 끝점이 그 삼각형의 내부에 사영될 때, 오직 한 segment-edge test만 요구된다. 두 개의 끝점 삼각형 밖으로 사영될 때, 그 segment-edge tests들 중 하나가 필요하지 않다. 후자 두 경우에 대해, 필요한 segment-edge tests들은 그 segment 끝점이 어떤 Voronoi regions에 놓여 있는지를 조사하여 결정되어질 수 있다.

나머지 케이스는 선분이 그 삼각형과 교차할 때 이다. 가로지르는 교차에 대해, 그 교차점은 가장 가까운 점과 일치한다. 그 선분이 삼각형의 평면에 놓여 있을 때, 그 삼각형과 교차하는 선분위의 어떤 점이 가장 가까운 점들이라는 것을 안다. 선분과 삼각형 사이의 가장 가까운 점들을 결정하는, 벡터 적분 접근법을 기반으로하는, 대안의 방법은 [Eberly01]과 [Schneider02]에서 보여진다.

5.1.11 Closest Points of Two Triangles
선분과 삼각형 사이의 가장 가까운 점들을 결정하는 케이스에서 처럼, 두 삼각형 사이에 무한한 동등하게 가까운 점들이 있을지도 모른다. 그러나, 두 삼각형 T1과 T2 사이의 가장 가까운 점들을 항상 한 점이 그 삼각형들 중의 하나의 boundary에 놓여있게 된다고 깨달아질 수 있다. 결과적으로, 두 삼각형 사이의 가장 가까운 점들의 한 쌍은 다른 삼각형에 대해 테스트되는 한 삼각형으로부터 한 edge의 모든 6개의 가능한 조합에 대한 segment and triangle 사이의 가장 가까운 점을 연산하여 발견될 수 있다. 가장 적은 (squared) distance를 갖는 점들의 쌍은 그러고나서 minimum global distance의 점들의 가장 가까운 쌍과 일치한다.

Segment-triangle distance tests는 꽤 비싸고, 따라서 더 좋은 깨달음은, T1과 T2 사이의 점들의 가장 가까운 쌍이 각 삼각형의 한 edge에서 발생한다고 발견되거나 (그림 5.12a), 한 삼각형의 한 정점과 그 다른 삼각형의 내부에 있는 점으로서 발생한다고 발견될 수 있다. (그림 5.12b) 그 문제는 이제 각 삼각형으로부터 하나씩 edges의 모든 쌍 사이의 가장 가까운 점을 연산하는 것이 되고, 각 삼각형의 각 정점에 대해 반대 삼각형에서 가장 가까운 점을 연산하는 것이 된다 (정점이 다른 삼각형 내부로 사영된다고 말해질 때). 6개의 vertex-triangle tests와 9개의 edge-edge tests가 요구된다. 가장 가까운 점들의 모든 쌍에서, 전체적으로 가장 작은 거리를 가진 것이 삼각형 사이의 globally하게 점들의 가장 가까운 쌍과 일치한다.

만약 그 삼각형이 사전에 disjoint하다고 알려져 있지 않다면, 부가적인 테스트가 두 삼각형의 교차를 제외하기 위해 요구된다. 교차할 때, 그 삼각형들 사이의 거리는 자명하게 zero이다. 그러나 가장 가까운 점들은 잘 정의되지 않을 가능성이 높다. 왜냐하면 무한히 많이 있을지도 모르기 때문이다 (예를들어, 만야 그 삼각형들이 평행하고, 겹친다면)

5.2 Testing Primitives
primitives의 testing은 그것들 사이의 거리 연산보다 덜 일반적이다. 일반적으로,한 테스트는 그 primitives가 교차하고 있다는 것만을 가리키고, 그것들이 어디에서 얼마나 교차하고 있는지를 결정하지 않는다. 그러므로, 이러한 교차 테스트는 종종 부가적인 정보를 반환하는 테스트들 보다 더 빠르다.

5.2.1 Separating-axis Test
다양한 교차 테스트들을 구현하는 데 있어서 매우 유용한 도구는
separating-axis test(SAT)이다. 그것은 separating hyperplane theorem을 따르는데, convex analysis의 기본적인 결과이다. 이 정리는 두 개의 볼록 집합 A와 B가 주어진다면, 그 두 집합들 중 하나는 교차하거나 또는 A가 P의 한 side에 있고, B가 다른 곳에 있게 하는 separating hyperplane P가 존재한다는 둘 중 하나일 것이라고 말한다.

SAT는 직관적으로 그 정리를 따른다, 왜냐하면 두 볼록 오브젝트들은 서로를 주위로 "curve" 될 수 없기 때문이다. 따라서, 그것들이 교차하고 있지 않을 때, 그것들 사이에 한 gap이 생기는데, 거기에서 한 평면이 그 두 개의 오브젝트들을 분리하기 위해 삽입될 수 있따. 오브젝트 둘 중 하나 또는 둘 다 concave할 때, 한 평면은 일반적으로 교차하지 않는 오브젝트들을 분리하는데 더 이상 충분하지 않을 것이다. 대신에, cuved surface는 그 오브젝트들을 분리하는데 요구될 것이다. 그 오브젝트들이 교차하고 있을 때, 어떠한 표면 - curved or not-도 그것들을 분리하기 위해 오브젝트들 사이에 삽입될 수 없다.

A와 B를 분리시키는 hyperplane P가 주어진다면, separating axis는 P에 수직한 직선 L이다. 그것은 separating axis라고 불려지는데, 왜냐하면 A와 B의 L로의 orthogonal projection은 두 개의 nonoverlapping intervals를 만들어내기 때문이다 (그림 5.13). 왜냐하면 그 두 개의 intervals(간격이) 중첩되지 않기 때문에, 결론은 그 기하들이 분리되어있음에 틀림 없다는 것이다. separating axis가 존재한다 <=> separating hyperplane이 존재한다라는 것 때문에, 둘 중 하나가 테스트되어질 수 있다. 그러나, 실제로 한 축에 대한 separation을 테스트하는 것이 더 좋다고 밝혀졌다, 그것이 덜 비싼 테스트를 만든다는 점에서.

SAT를 수행하는 것에 대해, 많은 collision primitives - segments, AABB, OBBs, k-DOPs, and spheres같은 - 들은 그것들이 중심점 C를 가진다는 의미에서 symmetrical하다는 것을 주목할 가치가 있다. 그리고 그것은 항상 한 축으로의 사영의 projection interval의 중간으로 사영된다. 한 잠재적으로 separating axis L이 주어진다면, 두 symmetrical objects A와 B의 효율적인 분리 테스트는 그러므로 그것들의 projection intervals의 halfwidth or radii를 연산하고, 그것들의 중심의 projections 사이의 거리와 projection intervals의 합을 비교하는 거싱다. 만약 그 합이 그 center projections사이의 거리보다 더 작다면, 그 오브젝트들은 분리되어있음에 틀림없다. 한 예제가 그림 5.14에서 주어지는데, 거기에서 A와 B는 한 원과 한 방향이 있는 rectangle과 같다 (또는 동등하게, 한 sphere와 한 OBB, 그side로부터 보여짖듯이). 처음에, 각 오브젝트에 대해, L을 따라 supproting point가 얻어진다; 즉, L의 방향을 따라 object center로부터 가장 먼 거리의 한 점이다 (그 사영이 symmetrical 하다는 점에서, 그 방향은 중요하지않다; 두 방향에서 동등히 먼 점이 있을 것이다). 그 두 개의 object radii, r_A와 r_B는 그러고나서 object centers의 L로의 사영과 그것들 각각의 가장 멀리 있는 점 사이의 거리를 연산하여 얻어진다. center projections 사이의 거리 d는 또한 연산된다. 이러한 여산된 양이 주어진다면, 그 오브젝트들은 r_A + r_B < d라면 분리되어있다.

ㄱ SAT는 심지어 한 오브젝트가 symmetric하지 않을 때에도 적용된다. - 예를들어, 임의의 convex hull의 경우에서, 그러나 그 테스트는 projection intervals를 찾기위해 hull vertices를 그 축에 사영하도록 수정되어야만 할 것이다.

Separating axes는 검사에 의해 찾기에 쉽다. 그러나, 구현에 있어서, 자동으로, 무한한 잠재적인 separating axes를 몇 개의 테스트되는 axes로 제한할 수 있는 것이 중요하다. convex polyhedra에 대해, 테스트할 축들의 개수를 극적으로 줄이는 것이 가능하다. 순서를 무시하여, 두 개의 polyhedral objects들은 그것들의 features와 관련하여, 6개의 다른 방식에서 접촉할지도 모른다. 그것들은 face-face face-edge, face-vertex, edge-edge, edge-vertex, or vertex - vertex로 만날 수 있따. 정점들이 edges의 부분으로 고려될 수 있기 때문에, 정점과 관련된 조합들은 edges와 연관된 같은 상황으로 포함된다. 이것은 contact situations를 본질적으로 세 개의 다른 조합으로 만든다: face - face, face - edge, and edge-edge.

face-face and face-edge cases에 대해, 두 오브젝트들의 face normals을 잠재적인 separating axes로 테스트하는 것이 충분하다. edge-edge case에 대해, 테스트되어야 할 잠재적인 separating axis는 두 edges의 외적과 일치한다. 외적이 edge-edge case에서 separating-axis test에 대해 사용되는 이유는, 두 오브젝트가 edge to edge로 접촉하게 될 때 무엇이 발생하는 지를 고려하면 정당화 될 수 있다. 서로에게 가장 가까이에 있는 edges에 있는 점들은 두 edges 사이의 수직의 발을 형성한다. 이 수직은 edges의 외적이기 때문에, separating axis로서 테스트할 올바른 후보군이다. 요약해서, 두 개의 polyhedral objects의 separability를 테스트하기 위해, 다음의 축들이 테스트되어야 한다.

• object A의 face normals에 평행한 축들
• object B의 face normals에 평행한 축들
• A에 있는 모든 edges와 B에 있는 모든 edges의 외적으로 부터 나온 벡터에 평행한 축들

separating axis가 발견되자 마자, 한 테스트는 "no intersection"으로 즉시 종료될 수 있다. 만약 모든 축들이 테스트 되었다면, 즉 어떠한 separating axis도 발견되지 않았다면,그 오브젝트들은 교차하고 있음에 틀림없다.

같은 개수의 faces (F)와 edges(E)를 가진 두 개의 일반적인 polytopes에 대해, 2F + E^2 개의 잠재적인 separating axes가 있다. 왜냐하면 separating axes의 개수는 edges의 개수에 2차식이기 때문에, SAT는 중간에서 높은 복잡성을 가진 오브젝트에 대해 그럴듯 하지 않을지도 모른다. 그러나, 마지막 성공적인 SEPARATING AXIS를 캐싱하고, 그것을 차후의 query에 대해 처음에 테스트하여 SAT를 가속시키는 것이 가능하다. 이것은 queries 사이의 오브젝트들의 spatial and temporal coherency 덕택에, early nonintersection exit을 얻는 것을 희망한다는 것에서 한다.

두 개의 polytopes가 충돌할 때, SAT는 또한 contact information을 연산하는 것을 도울 수 있다. 한 overlap이 한 axis에서 탐지될 떄, early exit 대신에, 모든 축들이 overlap에대해 테스트되이진다. 모든 축들이 테스트되고 나서, 가장 적은 (normalized된) overlap을 가진 축은 contact normal로서 사용될 수 있고, 그 overlap은 penetration depth를 측정하기 위해 사용될 수 있다. 몇 가지 추가 작업으로, contact points는 또한 separating axis의 도움으로 연산될 수 있다. 더 관심있는 사람들에게, SAT는 [Larcombe95]에 의해 oriented bonding boxes의 collision detection에 대해 제안된다.

5.2.1.1 Robustnessof the Separating-axis Test
SAT가 가진 한 가지 잠재적인 문제는 각 오브젝트의 한 edge의 외적으로 형성된 separating axis의 경우에서의 robustness이다. 이러한 두 edges가 평행할 때, 그 결과는 zero vector이고, 이 축으로의 모든 사영과,이러한 사영의 합들을 그러므로 0이다. 따라서, 만약 그 테스트가 신중히 만들어지지 않는다면, zero vector는 부정확하게 separating axis로 해석되어질 지도 모른다. 부동소수점 연산의 사용에 의해, 이 문제는 심지어 두 개의 거의 평행한 edges에 대해 거의 zero vector의 경우에서 발생할지도 모른다. 사실, SAT의 robustness problem은 OBB-OBB intersection test의 맥락에서 Section 4.4.2에서 만났었따, 그 특정한 context에서 문제에 대한 해결책은 여기에서 발견될 수 있다.

가능할 때, 그것이 발생할 맥락에서 robustness problem을 분석하는 것이 가장 좋다. 그 문제에 대한 generic solution은 결과 외적 벡터가 (near) zero vector인지를 테스트하는 것이고, 만약 그렇다면, 그 두 개의 벡터에 수직 한 또 다른 축을 만들어 내거나, 그 축에 대한 separation이 제외될 수 있다면, 그 축을 무시하여 다루려고 시도하는 것이다.

다음의 코드 조각은 edges AB와 CD에 대해 어떻게 좀 더 튼튼한 SSAT가 구현되어질 수 있는지를 보여준다.

// Compute a tentative separating axis for ab and cd
Vector m = Cross(ab, cd);
if (!IsZeroVector(m))
{
     // Edges ab and cd not parallel continue with m as a potential separating axis
     ...
}
else
{
     // Edges ab and cd must be (near) parallel, and therefore lie in same plane P.
     // Thus, as a separating axis try an axis perpendicular to ab and lying in P
     m = Cross(ab, n);
     if (!IsZeroVector(m))
     {
          // Continue with m as a potential separating axis
          ...
     }
     // ab and ac are parallel too, so edges must be on a line. Ignore testing
     // the axis for this combination of edges as it won't be a separating axis.
     // (Alternatively, test if edges overlap on this line,in which case the
     // objects are overlapping.)
     ...
}

그 IsZeroVector() 함수는 그것의 인자가 0에 충분히 가까운 크기를 가진 벡터인지를 검사한다 (어떤 tolerance value에 따라서, Section 11.3.1을 보아라). 그 tolerance intervals을 넓히고, 거의 평행인 edges를 평행으로 다루는 것은 intersections에가까운 것을 intersections으로 만들 것이다. 결국, 이것은 대안보다 훨씬 더 매력적이다: 예를들어 zero-vector separating axis로의 projection에 의해서 교차하지 않는다고 잘못 보고되는 두 개의 교차하는 오브젝트들.

robustness errors와 관련된 source는 외적에 사용된 벡터들이 큰 크기를 가졌을 때 이다. 그리고 이것은 외적과 관련된 계산에서 부가적인 정확도의 손실을 발생시킬지도 모른다. 만약 그 input vectors의 크기에 대한 bound가 알려져 있지 않다면, 정확도를 유지하기 위해 외적을 연산하기 전에 그것들을 표준화하는 것이 신중한 것이다.

5.2.2 Testing Sphere Against Plane
몇 가지 방식들로, plane에 대해 sphere를 테스트하는 것이 가능하다. 이 섹션은 세 가지 그러한 방법들을 설명한다: 그 sphere가 plane에 교차하는지, 그 sphere가 plane의 완전한 뒤에 있는지, 그리고 그 sphere가 palne의 negative halfspace와 교차하는지를. 그림 5.15는 이러한 세 개의 시나리오를 보여준다.

sphere가 center Position C와 radius r에 의해 명시된 S라고 하고, 평면 𝝿를 (n • X) =d 라고 명시하자. 여기에서 n은 단위 벡터이다; 즉, ||n|| = 1이다. 그 sphere가 plane에 교차하는지를 보기 위해서, 그 평면의 방정식이 sphere의 center에 대해 얻어질 수 있다. n이 단위벡터이기 때문에, 그 결과 값은 평면으로부터의 양의 거리이다. 만약 그 거리의 절대값이 sphere radius 안이라면, 그 평면은 sphere와 교차한다:

// Determine whether planep intersects sphere s
int RTCD::TestSpherePlane(const Sphere & s, const Plane & p)
{
 // For a normlized plane (|p.n| = 1), evaluating the plane equation
 // for a point gives the signed distance of the point to the plane
 real dist = glm::dot(s.c, p.n) - p.d;
 // If sphere center within +/- radius from plane, plane intersects sphere
 return real_abs(dist) <= s.r;
}

sphere가 plane 𝝿 뒤에 완전히 놓여있는지 결정하기위해 (그러니까 평면의 negative halfspace 안에), 그 테스트는 다음으로 변한다

// Determine whether sphere s is fully begind (inside negative halfspace of) plane p
int RTCD::InsideSpherePlane(const Sphere & s, const Plane & p)
{
 real dist = glm::dot(s.c, p.n) - p.d;
 return dist < -s.r;
}

// Determine whether sphere s intersects negative halfspace of plane p
int RTCD::TestSphereHalfspace(const Sphere & s, const Plane & p)
{
 real dist = glm::dot(s.c, p.n) - p.d;
 return dist <= s.r;
}

만약 대신에 그 평면의 negative halfspace가 sphere와의 테스트에 대해 solid하다고 고려된다면, 그 테스트는 다음으로 변한다 (위의 두 번째 코드)

5.2.3 Testing Box Against Plane
평면 P가 (n • X) = d로 주어진다고 하자. box B가 P와 교차하는 것을 테스트하는 것은 또한 SAT로 얻어질 수 있다. 여기에서, 평면의 normal n에 평행한 축만이 테스트될 필요가 있다. 그 평면은 무한히 확장하기 때문에, edge-edge axis combinations를 형성한 어떠한 edgees가 없다. box의 face normals에 일치하는 축들은 테스팅으로부터 제거될 수 있는데, 왜냐하면 그 평면의 무한한 길이가, 그 평면이 만약 그 face와 평행하지 않다면, 결코 box faces들 중 하나 밖으로 결코 있지 못한다는 것을 의미하기 때문이다. plane normal axis에 의해 이미 처리된 axis이다.

처음에 OBB인 B의 경우를 고려하자. 그것은 center C의 보통 표기로 주어진다. local coordinate axes u0, u1, u2; 그리고 세 개의 스칼라 값 e0, e1, e2. (OBB의 변을 2ei로 만든다 0 <= i <=2). OBB안에 있는 점들 R은 R = c +- a0u0  +- a1u1 +- a2u2로 주어지고,
|ai| <= ei 이다. 유사하게, OBB의 8개의 정점들 Vi, 0<= i <= 7, 은 Vi = C +- e0u0 +- e1u1 +- e2u2 로 주어진다.

n과 평행한 L이 separating axis로서 역할을 한다는 점에서, 좋은 선택은 box center를 지나가는 L을 갖는 것이다. 이것은 L을 L(t) C + tn으로서 준다. 그 box center C는 t = 0일 때 L로 사영된다. OBB가 center에 대해 symmetrical이기 떄문에, L로의 사영은 대칭적인 간격의 사영을 만들어 낸다 [C - rn, C + rn], C를 중심으로, 그리고 r의 반width (또는 반지름)으로. B가 P와 교차하는 것을 테스트하는 것은 이제 projection interval의 반지름 r을 계산하고, P까지의 B의 중심점의 거리가 r보다 작은지를 점검하는 것으로 종합된다.

OBB의 중심으로부터 가장 멀리 있는 점들은 OBB의 정점이기 때문에, 어떤 벡터 n으로 전체 maximum projection radius는 그 정점들 중 하나에 의해 알아차려질 것이다. 따라서, 그 radius r을 연산할 때 이러한 것만을 고려하는 것이 충분하다. 8개의 정점의 projection radii ri는 다음으로 주어진다



내적의 분배법칙으로 인해, 이 수식은 다음으로 쓰여질 수 있다



그 maximum positive radius r은 모든 관련됭 항이 양수일 때 얻어지고, n을 따라 오직 양의 steps들과 일치한다. 그리고 그것은 그것들을 더하기 전에 그 항들의 절대값을 취하여 얻어진다:



그 extents는 양수로 가정되기 때문에, r은 다시 이렇게 쓰여질 수 있따



그 separating-axis vector n이 단위 벡터가 아닐 때, r은 대신에 다음이 된다



P에서 C의 양의 거리 s는 C에 대한 평면의 방정식을 evaluating하여 얻어진다, 그리고
s = n • C - d를 준다. s를 얻는 또 다른 방법은 C로부터 P의 거리 u를 연산하는 것이다, s = -u. P가 n • X = d인 것을 기억해라. 거기에서 평면에 있는 어떤 점 Q에 대해 d = Q • n이다. P위에 있는 모든 점들은 L 위에 있는 단일의 점으로 사영되기 떄문에, Q의 L로의 사영으로 작업하는 것은 충분하다. 그러므로 거리 u는 u = (Q - C) • n = Q • n - C • n = d - C • n이다. 그리고 이것은 sign change까지 box center에 대한 평면의 방정식의 evaluation과 같다. 그림 5.16은 이 테스트에서 사용되는 양을 보여준다.

OBB B와 평면 P 사이의 교차는 -r <= s <= r일 때만 발생하기 떄문에, 동등히, |s| <= r일 때, 이제 그 테스트를 구현할 충분한 정보가 있다.

// Test if OBB b intersects plane p
int RTCD::TestOBBPlane(const OBB & b, const Plane & p)
{
 // Compute the projection interval radius of b onto L(t) = b.c + t * p.n
 real r = b.e.x * glm::dot(b.u[0], p.n) +
    b.e.y * glm::dot(b.u[1], p.n) +
    b.e.z * glm::dot(b.u[2], p.n);

 // Compute distance of box center from plane
 real s = glm::dot(p.n, b.c) - p.d;
 // Intersection occurs when distance s falls within [-r, +r] interval
 return real_abs(s) <= r;
}

테스트를 작동하기 위해 n이 표준화 되어야 하는 것은 필수적이지 않다. 만약 n이 단위벡터가 아니라면, 그 r과 s 둘 다 ||n|| 만큼 더 크고, 이것은 테스트에 영향을 미치지 않는다.

다른 테스트들도 쉽게 같은 경향으로 구현되어질 수 있다. 예를들어, OBB는 plane의 negative halfspace 안에 떨어진다, 만약 s <= -r이라면. 만약  r <= s는 OBB는 plane의 완전한 halfspace위에 있다. B = C + k0v0 + k1v1 + k2v2, 0 <= k0, k1, k2 <= 1로 주어지는 OBB에 대해, OBB의 반지름 r은 r = (|v0 • n|) +(|v1 • n|) + (|v2 • n|) / 2 로 어덩진다. axis-aligned box B에 대해, local axes u0, u1, u2는 미리 알려져있고, 따라서 그 코드는 그에 따라 간단하게 되어질 수 있다.

// Test if AABB b intersects plane p
int RTCD::TestAABBPlane(const AABB & b, const Plane & p)
{
 // These two lines not necessary with a (center, extents) AABB representation
 Point c = (b.max + b.min) * real(0.5); // Compute AABB center
 Point e = b.max - c; // compute positive extents

 // Compute the projection interval radius of b onto L(t) = b.c + t * p.n
 real r = e[0] * real_abs(p.n[0]) + e[1] * real_abs(p.n[1]) + e[2] * real_abs(p.n[2]);
 // Compute distance of box center from plane
 real s = glm::dot(p.n, c) - p.d;
 // Intersection occurs when distance s falls within [-r, +r] interval
 return real_abs(s) <= r;
}

이 테스트는 plane normal을 따라 가장 멀리 있는 한 AABB 정점을 찾고, 그 정점과 평면의 반대면에 놓여있도록 하는 것과 같다.

5.2.4 Testing Cone Against Plane
한 평면이 (n • X) = d로 주어지고, 평면위의 한 점 P에 대해 d = -P • n이고, n은 단위 벡터이다. 한 원뿔이 그것의 tip T, 표준화된 axis direction d, height h, 그리고 bottom radius r로 명시된다고 하자 (그림 5.17). 그 원뿔은 plane의 negative halfspace와 교차하고 있다. 만약 그 cone의 어떤 점이 negative halfspace 안에 있다면; 즉, cone의 점 X가 (n • X) < d가 되는. 한 원뿔에 대해, 오직 두 개의 점들이 이 조건에 대해 테스트되어져야 한다.

• cone의 tip T
• cone의 circular endcap의 점 Q, 그리고 그것은 -n의 방향으로 가장 멀다.

두 번째 테스트에 대해서, Q가 찾아져야 한다. 원뿔이 주어지는 형식 덕택에, Q는 쉽게 tip으로부터 그 방향벡터를 따라서 circular bottom endcap으로 나아가서 얻어진다. 그리고 그 plane을따라서 endcap아래로:

그 벡터 m은 m = (n X v) X v로 주어진다.

만약 n X v가 zero라면, 그 cone axis는 plane normal과 평행하다. 그 경우에, Q = T + hv는 그 half space에 대해 테스트할 정확한 점이다. 그러나, 이 경우에 m은 또한 ㅋero이고, 따라서 이 경우를 특별히 처리할 필요는 없다.

종종 원뿔은 원뿔 꼭대기에서 halfangle alpha를 주어서명시된다, bottom radius r보다는. tan(alpha) = r/h라는 점에서, 이러한 경우에 r는 r = htan(alpha)로 얻어진다. alpha보다 r을 주는 것은 명백히 이 테스트에 대한 더 좋은 표기이다.

만약 그 교차 테스트가 halfspace가 아닌 plane 그 자체라면, Q에 대한 연산은 바꿔져야 하는데, n의 방향에서 가장 멀게 놓이도록 한다, T가 그 평면 뒤에 놓여있는 경우에.. 교차에 대한 테스트는 이제 T와 Q가 그 평면의 다른 곳에 있는지를 테스트하는 것이 된다,
(n • T) - d와 (n • Q) - d에 의해서 가르켜지고, 다른 부호를 갖게 된다. 이러한 것 중에서
(n • T) - d는 이미 T가 그 평면의 어디에 놓여있는지를 결정하기 위해 연산되어질 수 있다.

5.2.5 Testing Sphere Against AABB
한 sphere가 axis-algined bounding box와 교차하는지 테스트하는 것은 sphere center와 AABB 사이의 거리를 연산하여 최상으로 처리된다 (see Section 5.1.3.1) 그리고 이 거리와 sphere radius와 비교한다. 만약 그 거리가 radius보다 작다면, 그 sphere와 AABB는 교차하고 있다. 비싼 square root operations를 피하기 위해, distance와 radius 둘 다 그 테스트 결과를 바꾸는 것 없이 비교를 하기전에 제곱되어질 수 있다. Section 5.1.3.1에서 정의된 SqDistPointAABB() 함수를 사용하여, 그 구현은 다음이 된다:

// Returns true if sphere s intersects AABB b, false otherwise
int RTCD::TestSphereAABB(const Sphere & s, const AABB & b)
{
 // Compute squared distance between sphere center and AABB
 real sqDist = SqDistPointAABB(s.c, b);
 // Sphere and AABB intersect if the (squared) distance
 // between them is less than the (squared) sphere radius
 return sqDist <= s.r * s.r;
}

충돌 처리를 위해서, sphere center에 가장 가까운 AABB 위의 점이 반환되게 하는 것은 유용하다. 그 경우에, 그 테스트는 ClosestPtPointAABB()가 대신에 사용되어 쓰일 수 있다:

// Returns true if sphere s intersects AABB b, false otherwise
// The point p on the AABB closest to the sphere center is also returned
int RTCD::TestSphereAABB(const Sphere & s, const AABB & b, Point & p)
{
 // Find point p on AABB closest to sphere center
 ClosestPtPointAABB(s.c, b, p);

 // Sphere and AABB intersect if the (squared) distance from sphere
 // center to points p is less than the (squared) sphere radius
 glm::vec3 v = p - s.c;
 return glm::dot(v, v) <= s.r * s.r;
}

sphere가 그 AABB의 한 개 이상의 faces 밖에 완전히 있는지 테스트 하는 것은 sphere와 AABB 사이의 교차를 결정하기에 충분한 테스트가 아니라는 것에 주목해라. 예를들어, 한 sphere는 AABB의 한 edge 밖에서 교차하지 않는 포지션에 있찌만, 두 개의 AABB faces 들 중 하나 밖에 놓여있지 않을지도 모른다, edge에서 만다서, 그림 5.18에서 보여지듯이.

5.2.6 Testing Sphere Against OBB
OBB에 대해 sphere를 테스트하는 것은 AABB에 대해 테스트하는 것과 거의 같다. ClosestPtPointAABB()에 대한 호출을 ClosestPtPointOBB() 호출로 바꾸어서:

// Returns true if sphere s intersects OBB b, false otherwise.
// The point p on the OBB closest to the sphere center is also returned
int RTCD::TestSphereOBB(const Sphere & s, const OBB & b, Point & p)
{
 // Find point p on OBB closest to sphere center
 ClosestPtPointOBB(s.c, b, p);

 // Sphere and OBB intersect if the (squared) distance from sphere
 // center to point p is less than the (squared sphere radius)
 glm::vec3 v = p - s.c;
 return glm::dot(v, v) <= s.r * s.r;
}

5.2.7 Testing Sphere Against Triangle
sphere와 한 삼각형 사이의 교차 테스트는 box에 대한 sphere test와 같은 패턴을 따른다. 처음에, sphere center에 가장 가까운 삼격형 위의 점 P가 연산된다. P와 sphere center 사이의 거리는 그러고나서 가능한 교차를 탐지하기 위해 sphere radius와 비교된다:

// Returns true if sphere s intersects triangle ABC, false otherwise.
// The point p on abc closest to the sphere center is also returned
int RTCD::TestSphereTriangle(const Sphere & s, const Point & a, const Point & b, const Point & c, Point & p)
{
 // Find point p on triangle ABC closest to sphere center
 p = ClosestPtPointTriangle(s.c, a, b, c);

 // Sphere and triangle intersect if the (squared) distance from sphere
 // center to point p is less than the (squared) sphere radius
 glm::vec3 v = p - s.c;
 return glm::dot(v, v) <= s.r * s.r;
}

비싼 square root operation을 피하기 위해서, 그 제곱된 거리가 그 코드에서 비교된다.

5.2.8 Testing Sphere Against Polygon
sphere가 한 polygon가 교차하는지를 테스트하는 것은, 지난 몇 가지 테스튿ㄹ과 유사하게 처리될 수 있다: sphere center에 폴리곤에서 가장 가까운 점을 연산하고, 이러한 두 점 사이의 거리를 sphere radius에 비교한다. 한 주어진 점 P에 대해 한 폴리곤에서 가장 가까운 점은 그 polygon을 삼각형화하고, 각 삼각형에 대해 P에 가장 가까운 점을 연산하고, P에 가장 가까운 점을 결과로 반환하여 연산될 수 있다. 그러나, 이것은 큰 폴리곤에 대해 효율적이지 ㅇ낳다, n - 2 triangle tests가 n개의 정점들을 가진 폴리곤에 대해 수행되어야만 하기 때문이다.

대안의 방법은 다음의 테스트들을 차례로 수행하는 것이다:

1. sphere가 폴리곤의 평면과 교차하는지를 테스트해라. 만약 그렇지 않다면 false로 종료
2. 폴리곤이 sphere를 관통하는지 보기 위해 polygon의 각 edge를 테스트해라. 만약 그렇다면 true로 종료해라.
3. 그 sphere center를 폴리곤의 평면에 사영해라. 점이 폴리고 내부에 있는지 보기 위해 point-in-polygon test (see Section 5.4.1)을 수행해라. 만약 그렇다면, ture로 종료해라. 그렇지 않다면, false로 종료해라. sphere가 그 polygon과 종료하지 않기 때문에.

다음의 코드조각은 그 테스트가 어떻게 구현되어질 수 있는지를 보여준다.

// Test whether sphere s intersects polygon p
int TestSpherePolygon(Sphere s, Polygon p)
{
     // Compute normal for the plane of the polygon
     Vector n = Normalize(Cross(p.v[1] - p.v[0], p.v[2] - p.v[0]));
     // Compute the plane equation for p
     Plane m; m.n = n; m.d = -Dot(n, p.v[0]);
     // No intersection if sphere not intersecting plane of polygon
     if(!TestSpherePlane(s, m)) return 0;
     // Test to see if any one of the polygon edges pierces the sphere
     for(int k = p.numVerts, i = 0, j = k - 1; i < k; j = i, i++)
     {
          float t;
          Point q;
          // Test if edge (p.v[j], p.v[i]) intersects s
          if (IntersectRaySphere(p.v[j], p.v[i] - p.v[j], s, t, q) && t <= 1.0f)
               return 1;
     }
     // Test if the orthogonal projection q of the sphere center onto m is inside p
     Point q = ClosestPtPointPlane(s.c, m);
     return PointInPolygon(q, p);
}

최적화로서, steps 2에 대해, sphere와 polygon을 principal plane에 사영하는 것이 가능하다. 거기에서 그 폴리곤은 가장 큰 넓이를 가지고, 그 문제를 polygon에 대해 circle의 2D test로서 다루게 된다. 이것은 그 테스트에 요구되는 전체 연산을 줄인다.

5.2.9 Testing AABB Against Triangle
box B와 교차하는 삼각형 T의 테스트는 SAT 접근법을 사용하여 효과적으로 구현될 수 있다 ([Eberly01], [Akenine-Moller01]). projection을 위해 고려되어야 할 13개의 축들이 있따:

1. AABB의 세 개의 face normals
2. triangle의 한 개의 face normal
3. 둘 다로 부터 나온 edges의 조합의 외적에 의해 주어지는 9개의 축들.

이전처럼, SAT가 발견되자마자, 그 테스트는 "no intersection" result로 즉시 종료할 수 있다. 만약 모든 축들이 테스트되고, 어떠한 separating axis도 발견되지 않는다면, 그 box와 삼각형은 교차하고 있음에 틀림없다. 이러한 세 개의 테스트 셋을 수행하는 가장 효율적인 순서는 3-1-2라고 제안된다 [Akenine-Moller01].

그 같은 13개의 축들은 OBB와 AABB 둘 다에 적용된다. 그러나, AABB에 대해 (box의 로컬 축등리 알려져있기 때문에) 몇 가지 최적화는 테스트에 요구되는 런타임 계산을 가속하는데 만들어질 수 있다. 여기에서 오직 AABB 테스트만이 보여지지만, 유사성을 더 잘 보여주기 위해 - 뿐만 아니라 AABB에 특정한 최적화를 하기위해 - AABB가 OBB에 공통되게 사용된 형식으로 주어진다고 가정한다. 즉, center C에 의해; local axes u0 = (1,0,0), u1 = (0,1,0), and u2 = (0,0,1); 그리고 extents e0, e1, e2. 그것이 테스트되는 삼각형은 점 V0, V1, V2의 점으로 주어진다.

그 AABB의 세 개의 face normals 들은 자명하게 삼각형의 AABB를 연산하고 B와 삼각형의 AABB를 overlap에 대해 테스트하여 테스트된다. 만약 그 두 개의 AABB가 교차하지 않는다면 B와 T 둘다 교차하지 않느다. 삼각형의 face normal에 평행한 축을 테스트하는 것은 AABB가 그 삼각형의 평면에 교차하는지를 테스트하는 것과 같다. 이 테스트가 Section 5.2.3에서 설명되었기 때문에, 여기에서 더 이상 자세히 하지 않는다. 남은 것은 B의 세 개의 edge directions와 T의 세 개의 edge directions의 외적과 일치하는 9개의 축들을 테스트하는 것이다.

대부분의 SATs와 함께 처럼, 그 연산은 한 오브젝트를 (존재한다면, 대칭적인 것) 원점으로 움직여서 간단하게 된다. 여기에서 그 box center는 원점과 정렬되어 움직여지고, 다음의 변수 업데이트를 만든다 : V0 <- V0 - C, V1 <- V1 - C, V2 <- V2 - C, 그리고 C <- (0,0,0). 삼각형 edges가 다음으로 인해 주어진다고 하자 f0 = V1 - V0, f1 = V2 -V1, f2 = V0 - V2. 그 separating axes로서 고려되는 9개의 축들은 그러고나서 aij = ui X fj로 명시될 수 있다. u0과 u1 그리고 u2는 간단한 형태를 가지기 때문에, 이러한 축들은 다음으로 간단하게 된다:

axis n과 관련하여 box의 projection radius는 다음으로 주어진다는 것을 기억해라



n = a00인 겨우에, 이 것은 다음으로 간단하게 된다

r = e0|0| + e1|-a00z| + e2|a00y|
r = e1|f0z| + e2|f0y|

유사하게, AABB projection radius에 대한 간단한 수식들은 나머지 aij axes에 대해서 쉽게 얻어진다. 모든 경우에, 그 box의 projection interval은 [-r, r]이다.

T를 주어진 축 n에 사영하는 것은 projection interval [min(p0, p1, p2), max(p0, p1, p2)]를 만들어내고, p0, p1, p2는 원점에서 삼각형 정점들을 n으로 사영한 거리이다. n = a00인 것에 대해 이것은 당므을 준다:

p0 = V0 • a00 = V0 • (0, -f0z, f0y) = ..
p1 = p0
p2 = ..

만약 그 projection intervals[-r,r]과 [min(p0,p1,p2), max(p0,p1,p2)]가 주어진 축에 대해 disjoint하다면, 그 축은 separating axis이고, 그 삼각형과 AABB는 중첩되지 않는다.

이 축에 대해, n = a00, 그것은 p0 = p1이고, 그 삼각형에 대한 projection interval은 [min(p0,p2), max(p0, p2)]로 간단하게 된다. 그 삼각형 projection intervals는 모든 9개의 projection axes에 대해 같은 방식으로 간단하게 된다. 그것들이 모두 한 개의 zero component를 가지고 있기 때문이다. 여기에서 AABB와 삼각형 projection intervals는 그러므로 disjoint하다 만약 max(p0, p2) < -r or min(p0, p2) > r 이라면. min() and max() 연사이 target architecture에서 native floating-pointi instructions으로서 이용가능하다면, 한 개의 (잠재적으로 비싼) 비교를 피하는 동등한 수식은 max(-max(p0,p2), min(p0,p2)) > r이다. 그 후자 공식은 SIMD 구현에서 특별히 사용가능하다 (SIMD 구현에 대해 더 많은 것은 Chapter 13을 보아라).

다음의 코드 조각은 이 테스트가 어떻게 구현되는지를 보여준다.

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 test 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);
}

categories 2의 테스트와 (degenerate or oversized triangle에 대해 face normal를 계산할 때) 3의 테스트와 (zero vector를 주는 두 개의 평행한 edges의 외적) 관련된 robustness 문제들이 있다는 것에 주목해라. 완전히 robust 구현에서 이러한 경우들을 다루기 위해서 무어싱 처리되는지에 대한 이야기를 위해 Section 5.2.1.1을 보아라.

trinagle-AABB overlap testing의 topic은 [Voorhies92]에서 이야기된다. AABB에 대한 임의의 polygons의 한 테스트는 [Green95]에서 주어진다.

5.2.10 Testing Triangle Against Triangle
많은 알고리즘들이 두 삼각형 ABC와 DEF의 교차를 탐지하기 위해 제안되었다. 가장 간단한 테스트는 일반적으로 두 삼각형이 다른 삼각형의 내부를 관통하여 한 삼각형의 두 개의 edges와 교차하거나 다른 삼각형의 내부에 관통하여 각 삼각형의 한 edge와 교차할 때 라는 사실에 기반한다 (그림 5.19).

삼각형-삼각형 테스트는 그러므로 6개 (까지의) edge-triangle  테스트의 관점에서 구현될 수 있다. 마약 한 삼각형의 한 edge가 다른 삼각형과 교차한다면, 그 삼각형은 교차한다. 만약 모든 6개의 테스트가 실패한다면, 그것들은 교차하고 있지 않다.

그 삼각형들이 coplanar인 겨웅에, 또는 하나 또는 삼각형 둘 다 degenerate인 경우는 (두 개 이상의 coincident vertices, 삼각형을 선이나 점으로 만들면서) 이 테스트에서 정확히 다뤄지지 않는다. 사실, 삼각형-삼각형 교차에 대한 제안된 알고리즘들 어떠한 것도 이러한 경우들을 기본적으로 처리하지 않는다: 그것들은 모두 특별 케이스로서 다뤄지는 것에 의존한다.

두 번째 접근법은 SAT를 적용하는 것이다. 교차하는 두 개의 삼각형에 대해, 11개의 separating axes가 테스트되어야만 한다: 두 삼각형의 각각에 대해 그 face normal에 평행한 한 axis, 더해서 edges의 9개의 조합, 각 삼각형으로부터 한 edge와. 각 축에 대해, 그 삼각형은 그 축에 사영되고, 그 projection intervals는 overlap에 대해 테스트된다. 만약 그 projection intervals가 어떤 축에서 disjoint하다고 발견된다면, 그 삼각형은 교차하고 있지 않고, 그 테스트는 즉시 종료될 수 있다. 그러나, projection intervals가 모든 11개의 축에서 겹친다면, 그 삼각형은 교차하고 있음에 틀림없다.

SAT와 비슷한 한 테스트는 [Moller97b]에서 제안된 interval overlap method이다. 그러나, 그것은 이전의 두개의 테스트들 보다 덜 비싸다. ...~~~

생략 나중에 필요하면 공부할 것.

5.3 Intersecting Lines, Rays, and (Directed) Segments
직선, rays, 그리고 선분과 관련된 테스트들은 자주 사용된다, 예를들어, 발사된 bullet을 재현하기 위해, 또는 시야의 line을 테스트하기 위해. line tests들은 가끔씩 좀 더 복잡한 queries 대신에 사용된다. 예를들어, 환경에 대한 한 player 캐릭터의 손 또는 발의 접촉 또는 땅에 대한 vehicle wheel의 접촉은 종종 효과적으로 simple line test로 모델링 돌 수 있다. 다음의 섹션들은 다양한 흔한 collision primitives에 대해 lines, rays, and segments 의 효율적인 테스트를 알아본다.

5.3.1 Intersecting Segments Against Plane
plane P가 (n • X) = d에 의해 주어진다고 하고,  한 선분이 parametric equation S(t) = A + t(B - A) for 0 <= t <= 1로 주어진다고 하자 (그림 5.20). 평면과의 선분의 교차의 t값은 평면의 방정식에 X에 대해 parametric equation을 대신하고 t를 해결해서 얻어진다:



t에 대한 수식은 이제 선분에 대한 parametric euqtion에 삽입될 수 있고, 실제 교차점 Q를 찾게 된다



이것은 다음으로 구현될 수 있다.

int RTCD::IntersectSegmentPlane(const Point & a, const Point & b, const Plane & p, real & t, Point & q)
{
 // Compute the t value for the directed line ab intersecting the plane
 glm::vec3 ab = b - a;
 t = (p.d - glm::dot(p.n, a)) / glm::dot(p.n, ab);

 // If t in [0..1] compute and return intersection point
 if (t >= real(0.0) && t <= real(0.0))
 {
  q = a + t * ab;
  return 1;
 }
 // Else no intersection
 return 0;
}

이 코드는 division by zero를 explicitly하게 처리하지 않는다는 것에 주목해라. IEEE-754 부동 소수점 연산을 가정하여, 그것은 denominator가 0인 경우에도 올바른 결과를 준다. 그것들을 explicitly하게 테스트할 필요 없이 division-by-zero errors를 어떻게 정확히 다루는지에 대한 세부사항을 infinity arithmetic에 관한 Section 11.2를 참조해라.

만약 그 평면이 explicitly하게 주어지지 않는다면, 오직 세 개의 평면의 점에 의해 명시된다면 (non-collinear), 그 테스트는 다음의 방식으로 대신에 쓰여질 수 있다.

// Intersect segment ab against plane of triangle def. If intersecting,
// return t value and position q of intersection
int RTCD::IntersectSegmentPlane(const Point & a, const Point & b, 
 const Point & d, const Point & e, const Point & f, 
 real & t, Point & q)
{
 Plane p;
 p.n = glm::cross(e - d, f - d);
 p.d = glm::dot(p.n, d);
 return IntersectSegmentPlane(a, b, p, t, q);
}

5.3.2 Intersecting Ray or Segment Against Sphere
한 ray가 R(t) = P + td, t>=0 으로 주어진다고 하고, P는 ray origin이고, d는 표준화된 방향벡터라고 하자, |d| = 1. 만약 R(t)가 ray가 아닌 선분이라고 설명한다면, 그러면 0<= t <= t_max이다. 그 sphere boundary가 (X - C) • (X - C) = r^2 이라고 정의하자, 여기에서 C는 구의 중심점이고, r은 그것의 반지름이다. 그 ray가 sphere의 표면과 교차하는 t값을 찾기 위해, R(t)는 X에 대해 대체되어 다음을 준다.



m = P - C라고 하자, 그러면:


이것은 t에 대한 이차식이다. 이차 방정식 t^2 + 2bt + c = 0에 대해, 그 솔루션은 t = -b +- root(b^2 - c)로 주어진다. 여기에서 b = m • d이고, c = (m • m) - r^2 이다.

이차 방정식을 푸는 것은 세 개의 결과를 가지는데, 판별식 d = b^2 - c에 의해서 분류된다. 만약 d < 0이라면, 어떠한 실수근도 없고, 그것은 완전히 sphere를 놓친 ray와 일치한다. 만약 d = 0이라면, 한 개의 real (double) 근이 있고, ray가 한 점에 접선으로 구와 부딪히는 것과 일치한다. 만약  d > 0 이라면, 두 개의 실수근이 있고, 그 ray는 구와 두 번 교차한다 : 한 번은 들어가고, 한 번은 그 sphere boundary를 떠날 때. 후자의 경우에, 더 작은 intersection t값이 관련되어있다, t = -b - root(b^2 - c)에 의해 주어지는. 그러나, 그 sphere 밖에서 시작하고 그것으로부터 멀리 가리키고 intersection value t < 0인 ray의 잘못된 intersection을 구분하는 것은 중요하다, 이 경우는 그림 5.21에서 보여진다, 모든 다른 ray-sphere intersection 관계를 따라.

다음의 코드는 ray-sphere intersection test를 구현한다.

// Intersects ray r = p + td, |d| = 1, with sphere s and, if intersecting, 
// returns t value of intersection and intersection point q
int RTCD::IntersectRaySphere(const Point & p, const glm::vec3 & d, const Sphere & s, real & t, Point & q)
{
 glm::vec3 m = p - s.c;
 real b = glm::dot(m, d);
 real c = glm::dot(m, m) - s.r* s.r;
 // Exit if r's origin outside s (c > 0) and r pointing away from s (b > 0)
 if (c > real(0.0) && b > real(0.0)) return 0;
 real discr = b * b - c;
 // A negative discriminant corresponds to ray missing sphere
 if (discr < real(0.0)) return 0;
 // Ray now found to intersect sphere, compute smallest t value of intersection
 t = -b - real_sqrt(discr);
 // If t is negative, ray started inside sphere so clamp t to zero
 if (t < real(0.0)) t = real(0.0);
 q = p + t * d;
 return 1;
}

sphere에 대해 방향이 있는 선분 AB를 교차시키는 것에 대해, 그 같은 코드는 P = A 그리고 d = (B - A) / || B - A ||로 설정하여 사용될 수 있따. 교차시에, t <= ||B - A||인 것을 확인하는게 중요하다. 탐지된 intersection이 선분의 끝점을 넘어가지 않도록 하기 위해서이다.

그 ray가 sphere와 교차하는지 테스트하기 위해 (그러나 언제 또는 어디에서가 아닌), 그 코드는 잠재적으로 비싼 square root operation을 수행해야만 하지 않도록 최적화될 수 있다.

가능한 빠르게 early exits을 만들어서, 그 코드는 다음으로 된다

// Test if ray r = p + td intersects sphere s
int RTCD::TestRaySphere(const Point & p, const glm::vec3 & d, const Sphere & s)
{
 glm::vec3 m = p - s.c;
 real c = glm::dot(m, m) - s.r * s.r;
 // If there is definitely at least one real root, there must be an intersection
 if (c <= real(0.0)) return 1;
 real b = glm::dot(m, d);
 // Early exit if ray origin outside sphere and ray pointing away from sphere
 if (b > real(0.0)) return 0;
 real disc = b * b - c;
 // A negative discriminant corresponds to ray missing sphere
 if (disc < real(0.0)) return 0;
 // Now ray must hit sphere
 return 1;
}

만약 d가 표준화 되지 않았다면, 해결해야 할 2차 방정식은
(d • d)t^2 + 2(m • d)t + (m • m) - r^2 = 0이다. 이것과 같은 이차 방정식에 대해, at^2 + 2bt +c = 0에 대해, 그 솔루션들은 다음으로 주어진다



판별식 d = b^2 - ac이다.

5.3.3 Intersecting Ray or Segment Against Box
한 slab의 정의가 평행 면들의 한 쌍 사이의 공간으로서 정의된다는 것을 회상하면, 한 rectangular box의 volume이 서로에게 직각인 세개의 그러한 slabs의 교차로서 보여질 수 있다. 이제, 한 점이 모든 세 개의 slabs안에 놓여 있다 <=> 한 점은 그 box 안에 있다 처럼, 한 선분은 박스와 교차한다 <=> 선분과 그 slabs 사이의 교차가 모두 중첩된다. 만약 slabs와 그 segment의 교차가 중첩되지 않는다면, 그 segment는 동시에 그 slabs에 놓여있을 수 없고, 그러므로 그 slabs의 교차에 의해 형성되는 volume과 교차할 수 없다. 그 같은 원리는 박스와 ray or line의 교차에도 적용된다. x slab과 y slab의 교차로서 형성된 2D box에 대한 ray의 교차와 nonintersection은 그림 5.22에서 보여진다.

ray와 box에 대한 교차 테스트는 그러므로 slabs의 평면들과 ray의 intersection intervals를 연산할 필요가 있고 그리고 ray를 따라서 모든 intersection intervals의 logical intersection을 유지하기 위해 어떤 간단한 비교 연산을 수행할 필요가 있다. 요구되는 모든 것은 slab으로가는 모든 entries중에서 가장 멀리 있는것을 추적하는 것이다. 모든 것 중에 가장 가까이 있는 것은 slab에서 나가진다. 만약 그 가장 멀리있는 entry가 the nearest exit보다 더 멀리 있게 된다면, 그 ray는 slab intersection volume과 교차할 수 없고, 그 테스트는 일찍 끝날 수 있다 (nonintersection의 결과로).

slabs과의 ray의 intersection intervals은 ray의 parametric equation R(t) = P + td를 slab의 plane equations X • n_i = d_i에 넣고, t에 대해 풀어서 얻어진다,

t = (d_i - P • n_i) / (d • n_i)

AABB에 대해, 그 normal의 두 개의 컴포넌트들은 zero이고, 따라서 P = (px, py, pz) and d = (dx, dy, dz) 가 주어진다면, 예를들어 그 식은 t = (d - px) / dx로 간단하게 된다, x축에 수직인 한 평면에 대해. 거기에서 d는간단히 그 평면의 x축을 따라가는 위치와 일치한다. ray가 slab과 평행할 때 0으로 나누는 것을 피하기 위해서, 이 케이스는 분리해서 가장 잘 처리된다, ray origin이 slab에 포함되도록 하는 테스트로 대체하여. 그 다음의 코드는 AABB에 대한 ray의 test의 구현이다.

// Intersect ray R(t) = p + t*d against AABB a. When intersecting,
// return intersection distance tmin and point q of intersection
int RTCD::IntersectRayAABB(const Point & p, const glm::vec3 & d, const AABB & a, real & tmin, Point & q)
{
 tmin = real(0.0);  // set to -FLT_MAX to get firsthit on line
 real tmax = REAL_MAX; // set to max distance ray can travel (for segment)

 // For all three slabs
 for (int i = 0; i < 3; ++i)
 {
  if (real_abs(d[i]) < EPSILON)
  {
   // Ray is parallel to slab. No hit if origin not within slab
   /* 
   it means that you will test each axis of world, X, Y, Z
   So the meaning of ray parallel to the each slab is
   the dot product of the normal of slab will be zero.
   Therefore, if X component of direction will be zero,
   it means the X axis normals of slabs will be parallel to the ray direction
   */
   if (p[i] < a.min[i] || p[i] > a.max[i]) return 0;
  }
  else
  {
   // Compute intersection t value of ray with near and far plane of slab
   real ood = real(1.0) / d[i]; // the normal component of slab will be 1
   real t1 = (a.min[i] - p[i]) * ood;
   real t2 = (a.max[i] - p[i]) * ood;
   // Make t1 be intersection with near plane, t2 with far lane
   if (t1 > t2) swap(t1, t2);
   // Compute the intersection of slab intersection intervals
   if (t1 > tmin) tmin = t1;
   if (t2 > tmax) tmax = t2;
   // Exit with no collision as soon as slab intersection becomse empty
   if (tmin > tmax) return 0;
  }
 }
 // Ray intersects all 3 slabs. Return point (q) and intersection t value (tmin)
 q = p + d * tmin;
 return 1;
}

만약 그 같은 ray가 많은 수의 boxes에 대해 교차되어진다면, 그 관련된 세 개의 나눗셈은 그 ray에 대해 한 번 연산되어질 수 있고, 모든 테스트들에 대해 재사용되어질 수 있다. 더 최적화로서, if(t1> t2) Swap(t1, t2)의 문장의 결과는 또한 ray direction vector의 컴포넌트들의 signs에 의해서 미리 결정되어진다. 그러므로 그것은 미리 8개의 (또는 2D test에 대해 4개) 호출할 대안 routines 중의 한 개를 결정하여 제거될 수 있따. 거기에서 그 if문의 효과는 surrounding code로 접어질 것이다.

보여진 ray-box intersection test는 Kay-Kajiya slab volume에 대한 ray의 intersection test의 특별 케이스라는 것에 주목해라, Section 4.6.1에서 설명된. slab의 개수를 증가시키는 것은 오브젝트들의 convex hulls의 임의의 좋은 fit이 성취되도록 허용한다. Kay-Kajiya test는 차례로, Cyrus-Beck clipping algorithm의 실제로 특수화이다 [Cyrus78]. Cyrus-Beck같은 접근법은 또한 convex polyhedron에 대한 ray or segment의 교차에 대해 Section 5.3.8에서 사용된다.

만약 그 문제가 선분이 bo와 교차하는지를 테스트 한다면, 교차점을 결정하는 것 없이, 대안의 솔루션은 SAT를 사용하는 것이다. 일반성의 손실없이, 한 좌표계가 선택되어질 수 있는데, 그 좌표계에서 그 박스는 원점에 중심이고, 좌표축의 방향을 갖는다. AABB에 대해,그 centering은 선분을 AABB를 따라 원점으로 평행이동 시켜서 얻어진다. OBB에 대해, 그 segment endpoints는 world space에서 OBB space로 변환되어질 수 있고, 그 후에, 둘 다 같은 방식으로 AABB에 대해 원점으로 평행이동 될 수 있다. OBB가 중심점 C, halfwidth extent vector e = (e0,e1,e2), 그리고 로컬 좌표계 u0,u1,u2 에 의해 주어진다고 가정하여, world space P에 있는 한 점 P는 OBB 좌표계에서 점 (x, y, z)로 표현될 수 있다, 거기에서
x = (P - C) • u0, y = (P - C) • u1, z = (P - C) • u2 이다.

그 선분이 midpoint M = (mx, my, mz)와 끝점 M - d and M + d로 설명된다고 하자. 거기에서 d = (dx, dy, dz)는 그 선분에 대한 방향벡터이다. 그 segment의 halflength는 ||d||이다. 그 선분을 원점을 지나는 어떤 separating axis v = (vx, vy, vz)에 사영시키는 것은 signed distance ds = (M • v) / ||v||에 원점으로 부터 (v를 따라) 중심을 두고, 반지름 (or halflength) of rs = |d • v| / ||v|| projection interval을 만들어낸다. rb가 그 box의 vector v로의 projection interval radius라고 표기하여, v는 |ds| > rb + rs라면 separating axis로 행동한다 (그림 5.23).

세 개의 orthogonal unit vectors u0, u1, u2와 세 개의 halflength extents e0, e1, e2에 의해 명시된 OBB에 대해, 그 projectioninterval radius r_b는 다음으로 주어진다



u0 = (1, 0, 0), u1 = (0, 1, 0), u2 = (0, 0, 1)로 대체하여, AABB에 대한 식은 다음으로 주어진다



separating axes로서 테스트 되어야 할 6개의 축들이 있다: AABB facenormals와 대응되는 세 개 (v0 = (1, 0, 0), v1 = (0, 1, 0), v2 = (0, 0, 1), 그리고 선분의 방향벡터와 face normals 사이의 외적에 대응되는 세 개 (v3 = d X (1,0,0), v4 = d X (0,1,0), v5 = d X (0, 0, 1)). 테이블 5.1은 그 수식을 d_s, r_b, r_s에 대해 처리하는 결과들을 주고, 이러한 6개의 축들에 대한 |d_s| >r_b + r_s 를 준다.

테이블 5.1에서 주어진 separation에 대한 식은 직접적으로 효율적인 구현으로 된다.

// Test if segment specified by points p0 and p1 intersects AABB b
int RTCD::TestSegmentAABB(const Point & p0, const Point & p1, const AABB & b)
{
 Point c = (b.min + b.max) * real(0.5); // Box center-point
 glm::vec3 e = b.max - c;      // Box halflength extents
 Point m = (p0 + p1) * real(0.5);       // Segment midpoint
 glm::vec3 d = p1 - m;       // Segment halflength vector
 m = m - c;          // Translate box and segment to origin
 // Try world coordinates axes as separating axes
 real adx = real_abs(d.x);
 if (real_abs(m.x) > e.x + adx) return 0;
 real ady = real_abs(d.y);
 if (real_abs(m.y) > e.y + ady) return 0;
 real adz = real_abs(d.z);
 if (real_abs(m.z) > e.z + adz) return 0;

 // Addin an epsilon term to counteract arithmetic errors when segment is
 // (near) parallel to a coordinate axis (see text for detail)
 adx += EPSILON; ady += EPSILON; adz += EPSILON;
 // Try cross proudcts of segment direction vectorwith coordinate axes
 if (real_abs(m.y * d.z - m.z * d.y) > e.y * adz + e.z * ady) return 0;
 if (real_abs(m.z * d.x - m.x * d.z) > e.x * adz + e.z * adx) return 0;
 if (real_abs(m.x * d.y - m.y * d.x) > e.x * ady + e.y * adx) return 0;

 return 1;
}

쓰여져 있듯이, e, d, m에 대한 수식들은 모두 제거되어질 수 있는 0.5 factor를 가지고, 이것은 intial setup code의 처음 5줄이 간단하게 되도록 한다.

다뤄야할 남아있는 것은 segment direction vector d가 좌표축들 중 하나에 평할 때에 대한 코드의 robustness이다. 이것은 세 개의 외적이 zero vector result를 만들게 한다. 만약 그 segment가 AABB와 교차하지 않는다면, 그 처음의 세 개의if tests들은 이것을 정확히 탐지할 것이다.  만약 그 선분이 교차한다면, 그 후자의 세 개의 if 문은 0 > 0 tests들과 일치할 것이다. 축이 부정확하게 separating하다고 해석되는 것을 발생시키는 rounding errors를 피하기위해서, 작은 epsilon term이 adx, ady, adz 값에 더해질 수 있다, 그 comparison을 bias하기 위해서, Chapter 4에서 OBB-OBB test에 대해 처리되던 것과 유사하다.

5.3.4 Intersecting Line Against Triangle
삼각형들에 대한 lines (뿐만아니라rays와 segments도) 의 교차는 매우 흔한 테스트이다. 이 이유 때문에, 이테스트는 이번과 두 개의 다음섹션에서 이야기된다. lines과 관련된 테스트로 시작하여, 삼각형 ABC와 점 P와 Q를 지나는 한 직선이 주어진다고 하자. 그 직선 PQ는 삼각형과 교ㅏ한다 만약, 직선과 ABC 평면 사이의 교차점 R이 삼각형 내부에 있다면 (그림 5.24). 그 교차 문제에 대한 한 가지 솔루션은 그러므로 R을 연산하고 point-in-triangle test를 그것과 함께 수행하는 것이다. 만약 ABC가 주어진 바라보는 방향에서 시계 반대방향으로 배치되었다면, R은 만약 삼각형 edges AB, BC, and CA의 왼쪽에 놓여있다면 (그 edges가 directed line segments로 고려된다) ABC 안에 있게 된다. 유사하게, 만약 ABC가 시계 방향이라면, R은 만약 R이 모든 삼각형 edges의 오른쪽에 있다면 ABC안에 있게 된다.

sidedness test에서 사용하기 위해 R을 explicitly하게 연산하는 것 대신에, 그 테스트는 삼각형 edges에 대한 line PQ와 직접적으로 수행되어질 수 있다. 스칼라삼중적을 고려해라:

u = [ PQ PC PB ]
v = [ PQ PA PC ]
w = [ PQ PB PA ]

만약 ABC가 시계 반대 방향이라면, edges BC, CA, and AB의 왼쪽으로 지나가는 PQ에 대해, 그 수식들 u >= 0, v >= 0, w >= 0 (개별적으로) 사실임에 틀림없다. 유사하게, ABC가 시계 방향일 때, 그 스칼라 삼중적은 그 edges의 오른쪽을 지나는 PQ에 대해 nonpositive임에 틀림 없다. double-sided triangle에 대해, 그것이 어떤 면에서 보아지느냐에 따라 clockwise and counterclosiwe 둘 다 인, PQ는 그 내부를 지난다. 만약 모든 three scalartripe products가 같은 부호를 갖는다면 (zeroes를 무시하고).

ABC와 교차점을 얻는 것에 대해, u, v, w는 u*, v*, w*에 비례하는 것으로 보여질 수 있다:

u* = ku = [ PR PC PB ]
v* = kv = [ PR PA PC ]
w* = kw = [ PR PB PA ]

여기에서 k = ||PR|| / || PQ||

여기에서, u*,  v*, w*는 사면체 RBCP, RCAP, RABP의 부피와 비례한다. 이러한 사면체 모두 같은 높이를 갖기 때문에 (Section 3.4에서 보여지듯이, barycentric coordinates에서), 그 부피들은 그에 따라 그것들의 base triangles RBC, RCA, RAB의 넓이에 비례한다. 그것은 u, v*, w* (그리고 더 중요하게, u, v, w) 그러므로 이것들은직접적으로 R의 무게중심 좌표를 연산하는데 사용될 수 있다. 이제 시계 반대 방향의 삼각형 ABC에 대해 line PQ를 테스트하여, 교차점의 무게중심 좌표를 연산하는 것에 대한 코드를 유도하는 것은 간단하다.

// Given line pq and ccw triangle abc, return whether line piercestriangle. If
// so, also return the barycentric coordinates (u,v,w) of the intersection point
int RTCD::IntersectLIneTriangle(const Point & p, const Point & q, const Point & a, const Point & b, const Point & c, real & u, real & v, real & w)
{
 glm::vec3 pq = q - p;
 glm::vec3 pa = a - p;
 glm::vec3 pb = b - p;
 glm::vec3 pc = c - p;
 // Test if pq is inside the edges bc, ca, and ab. Done by testing
 // that the signed tetrahedral volumes, computed using scalar triple
 // products, are all positive
 u = ScalarTriple(pq, pc, pb);
 if (u < real(0.0)) return 0;
 v = ScalarTriple(pq, pa, pc);
 if (v < real(0.0)) return 0;
 w = ScalarTriple(pq, pb, pa);
 if (w < real(0.0)) return 0;

 // Compute the barycentriccoordinates (u,v,w) determining the
 // intersection point r, r = u*a + v*b + w*c
 real denom = real(1.0) / (u + v + w);
 u *= denom;
 v *= denom;
 w *= denom; // w = 1.0f - u - v;
 return 1;
}

robustness에 대해, PQ가 ABC 평면위에 놓여 있는 경우는 별개로 다뤄져야 한다. PQ가 ABC의 평면위에 있을 때, u, v, w = 0이 되고, 그것은 처리되지 않은 채 남아있다면, division-by-zero 에러를 발생시킬 것이다.

그 코드는 스칼라 삼중적의 식에서 그 항들을 재배치 하여 최적화될 수있는데, 그 외적이 그것들의 두 개 사이에서 공유되도록 하여, 이것은 그 코드의 중간을 다음으로 바꾼다

Vector m = Cross(pq, pc);
u = Dot(pb, m); // ScalarTriple(pq, pc, pb);
if (u < 0.0f) return 0;
v = -Dot(pa, m); // ScalarTriple(pq, pa, pc);
if(v < 0.0f) return 0;
w = ScalarTriple(pq, pb, pa);
if (w < 0.0f) return 0;

double-sided test에 대해 그 같은 코드는 대신에 이렇게 된다

Vector m = Cross(pq, pc);
u = Dot(pb, m); // ScalarTriple(pq, pc, pb);
v = -Dot(pa, m); // ScalarTriple(pq, pa, pc);
if (!SameSign(u, v)) return 0;
w = ScalarTriple(pq, pb, pa);
if (!SameSign(u, w)) return 0;

또한 이 테스트의 연산을 다음 또는 다음으로 동일하게 바꿀 수 있다

Vector m = Cross(pq, p);
u = Dot(pq, Cross(c, b)) + Dot(m ,c - b);
v = Dot(pq, Cross(a, c)) + Dot(m, a - c);
w = Dot(pq, Cross(b, a)) + Dot(m, b - a);

Vector m = Cross(pq, q);
float s = Dot(m, c - b);
float t = Dot(m, a - c);
u = Dot(pq, Cross(c, b)) + s;
v = Dot(pq, Cross(a, c)) + t;
w = Dot(pq, Cross(b, a)) - s -t;

그 세 개의 외적 C X B, A X C, B X A는 주어진 삼각형에 대해 상수이고, 그 벡터들
e0 = c - b, e1 = a - c도그렇다. 만약 이러한 것들이 그 삼각형과 함께 저장된다면, 오직 하나의 외적과 5개의 내적이 런타임에 얻어질 필요가 있다. 나머지 외적은 오직 그 직선의 값에만 의존하기 때문에, 그것은 오직 비록 그 직선이 많은 삼각형에 대해 테스트되어질지라도 한 번 얻어져야 만 한다. 이 마지막 공식은 line PQ와 삼각형 edges를 Plucker coordinates를 사용한 직선으로 표현하여 intersection test를 수행한 것과 같다 [Amanatides97]. Plucker coordinates에 대한 간단하지만 좋은 소개는 [Erickson97]과 [Shoemake98]에서 주어진다. 비록 Plucker coordinate 공식이 다소 더 적은 부동소수점 연산을 만들어 낼지라도 (어떠한 특별한 dot or cross-product 명령어가 이용가능하지 않다고 가정하여), 실제로 발생되는 추가 메모리 접근은 스칼라 삼중적 솔루션 보다 더 느리게 만들가능성이 높다. 게다가, 그 Plucker coordinate approach의 더 높은 메모리 오버헤드는 매력적이지 않다. 마지막으로, 삼각형 face normal인 n = (B - A) X (C - A)는 그 세 개의 저장된 외적인 n = - (C X B) - (A X C) - (B X A)로 부터 회복될 수 있다.

이러한 유형의 테스트는 L(t) = P + t (Q - P)의 intersection t value를 explicitly하게 연산하여, ABC의 평면과의 선분에 대한 테스트로 확장될 수 있다. 거기에서 그 직선 PQ가 ABC와 교차한다고 발견되기만 한다면, 그리고 0<= t <= 1이 아니라면 intersection을 버린다. segment와 triangle의 교차에 대한 대안 접근법은 Section 5.3.6에서 주어진다.

삼각형의 edges에 대해 직선의 sidedness를 직접 연산하여 3D에서 한 직선 또는 한 선분이 한 삼각형의 내부와 교차하는 것을 결정하는 것은 결국 삼각형 교차 테스트를 수행하는 가장 robust way이다. SEction 11.3.3은 이 내재된 robustness에 대해 그 이유를 이야기한다.

그 교차가 edge 밖에서 일어나는지를 결정하기 위해 스칼라 삼중적을 사용하는 방법은 또한 임의의 convex polygons에도 적용될 수 있지만, 효율성을 위해, polygon interior에 대해 line과 plane사이의 교차점을 테스트하는 것이 더 좋다. 그러나, 스칼라 삼중적 방법은 좋게 quadrilaterals에 대한 교차에도 확장된다, 다음 섹션에서 보여짇스이.

5.3.5 Intersecting Line Against Quadrilateral
이전 섹션에서 설명되었듯이, 스칼라 삼중적 방법은 사각형 ABCD와 한 직선의 교차점 R을 연산하는데 거의 바뀌지 않은 채로 사용되어질 수 있다. ABCD가 convex하고 시계 반대방향으로 주어진다고 가정하자. ABCD안에 있는 한 점은 삼각형 ABC 또는 삼각형 DAC안에 둘 중 하나에 있어야만 한다.

그 edge CA는 두 삼각형에 의해 공유되어지기 때문에, 이 edge가 처음에 테스트된다면, 효과적으로 R이 어떤 삼각형 안에 있지 않은지를 효과적으로 구별해내는데사용될 수 있다. 예를들어, R이 CA의 왼쪽에 있다면, R은 DAC안에 놓여질수 없고, 따라서 오직 ABC만이 테스트되어야 한다, 테스트해야 할 오직 두 개의 부가적인 edges로. 만약 대신에 R이 CA의 오른쪽에 놓여 있다면, DAC만이 테스트되어야 한다, R이 ABC안에 놓일 수 없다는 점에서. 또 다시, 두 개의 부가적인 edges만이 테스트되어야 한다. R이 CA 위에 놓이는경우는 임의로 삼각형 둘 중 하나에 배정되어질 수 있다. R이 CA의 왼쪽 또는 오른쪽에 놓이든, 둘 다의 경우에 오직 세 개의 edges만이 모두 테스트된다. 부동소수점 연산의 관점에서, 사각형에 대한 line이 교차하는 것의 비용은 그러므로 삼각형에 대해 교차시키는 것과 같다.

이 교차테스트에 대해, 그 교차점의 무게중심 좌표를 직접적으로 반환하는 것은 가능하지 않다. 부가적으로, 좌표가 그 두 개의 삼각형들 중 어떤 것에 연관되었는지가 명시되어져야 하고, 또는 대안적으로 그 좌표들이 항상 가령 ABC와 관련하여 주어져야 한다, 비록 그 ㄱ차점이 DAC안에 있을지라도. 다음의 샘플 구현에서, 그 교차점은 그 함수 안에서 연산되고, 점의 무게중심 좌표 대신에 반환된다.

// Given line pq and ccwquadrilateral abcd, return whether the line
// piercesthe triangle. If so, also return the point of intersection
int RTCD::IntersectLineQuad(const Point & p, const Point & q, const Point & a, const Point & b, const Point & c, const Point & d, Point & r)
{
 glm::vec3 pq = q - p;
 glm::vec3 pa = a - p;
 glm::vec3 pb = b - p;
 glm::vec3 pc = c - p;
 // Determine which triangle to test against by testing against diagonal first
 glm::vec3 m = glm::cross(pc, pq);
 real v = glm::dot(pa, m); // ScalarTriple(pq, pa, pc);
 if (v >= real(0.0))
 {
  // Test intersection against triangle abc
  real u = -glm::dot(pb, m); // ScalarTriple(pq, pc, pb);
  if (u < real(0.0)) return 0;
  real w = ScalarTriple(pq, pb, pa);
  // Compute r, r = u * a + v * b + w * c, from barycentric coordinates (u,v,w)
  real denom = real(1.0) / (u + v + w);
  u *= denom;
  v *= denom;
  w *= denom; // w = 1.0f - u - v;
  r = u * a + v * b + w * c;
 }
 else
 {
  // Test intersection against triangle dac
  glm::vec3 pd = d - p;
  real u = glm::dot(pd, m); // ScalarTriple(pq, pd, pc);
  if (u < real(0.0)) return 0;
  real w = ScalarTriple(pq, pa, pd);
  if (w < real(0.0)) return 0;
  v = -v;
  // compute r, r = u*a + v*d + w*c, from barycentric coordinates (u,v,w)
  real denom = real(1.0) / (u + v + w);
  u *= denom;
  v *= denom;
  w *= denom; // w = 1.0f - u - v;
  r = u * a + v * b + w * c;
 }
 return 1;
}

이 특별한 교차 방법은 또한 concave quadrilateral에 대해 테스팅 할 때도 사용되어질수 있다, 이것은 사각형의 내부에 완전히 diagonal이 first test에 대해 사용된다고 가정된다. 효과적으로 이것을 달성하는 한 방법은 전처리 과정에서 내부 대각선을 결정하고, 그것의 끝 정점들 중 하나를 첫 번째 정점으로 만들어내고, 따라서 diagonal CA가 내부 대각선이 되도록 만드는 것이다. 그러나, Self-intersecting quadrilaterals는 직접적으로 이 방법으로 테스트될 수 없다.




여기까지 공부하고, 이제 GPED책과 Chris hecker책으로 돌아가기.
나머지는 필요할 때 찾아서 공부하자.
5.3.6 Intersecting Ray or Segment Against Triangle
나중에 삼각형에 대해 Ray 교차를 탐색하는게 필요할텐데 나중에 하자.


5.3.7 Intersecting Ray or Segment Against Cylinder
5.3.8 Intersecting Ray or Segment Against Convex Polyhedron

5.4 Additional Tests
5.4.1 Testing Point in Polygon
5.4.2 Testing Point in Triangle
5.4.3 Testing Point in Polyhedron
5.4.4 Intersection of Two Planes
5.4.5 Intersection of Three Planes

5.5 Dynamic Intersection Tests
지금까지, 설명된 테스트들은 static objects인 것들을 포함한다: time안에 주어진점에서 두 오브젝트들의 교차. static testing이 가지는 한 문제는 그 오브젝트 움직임이 시간에서 한 점 사이에서 증가하고 다음에도 그렇게 할 때, 한 오브젝트가 다른 오브젝트를 지나서 점프하는 가능성이 생긴다. 이 원치않은 현상은 tunneling이다. 그림 5.32a는 rectangular obstruction을 지나서 tunneling하는 움직이는 구가 있는 이 케이스를 보여준다.

이상적인 솔루션은 그 오브젝트가 그것의 움직임의 경로를 따라서 지속적으로 움직이게 하는 것인데, 그리고 그 움직임을 시간에 따라서 parametrically하게 묘사하고, 어떤 다른 오브젝트에 대한 거리가 zero가 되는 시간의 점에 대해 해결하는 것이다. 그림 5.32b는 이 continuous swept test를 보여준다. 그러나, 충돌시간을 해결하는 것이 간단한 움직임과 오브젝트들에 대해 그럴듯할지라도, 임의의 움직임과 복잡한 오브젝트들을 다루는 것은 좀 더 어려운 문제이다. 사실, 대부분의 실시간 프로그램에서 다루기에 매우 비싸다.

타협점은 그 오브젝트의 경로를 sample하고, single object movement동안 몇 가지 static object tests를수행하는 것이다. 그림 5.32c는 그 sphere의 움직임이 어떻게 더 작은 steps로 subdivided될 수 있는지를 보여준다, 이것은 각 sample point에서의 static object-object test를 수행한다.

Tunneling은 움직이는 오브젝트가 한 샘플포인트에서 다른쪽으로 그 자첼 중첩되도록 하여 부분적으로 피해질 수 있다. 그러나, 그림의 part (c)에서 검정색 삼각형에 의해 가리켜지듯이, small or narrow objects들이 지나가서 tunneled될지도 모르는 장소들이 있다. 완전히 tunneling problem을 다루기위해서, 그 오브젝트들은 또한 모든 샘플들이 함께 완전히 그 지속적으로 swept object에 의해 형성된 volume을 커버하도록 사이즈에서 확장되어야 한다.

샘플링이 가지는 단점은, 최약의 경우에, 어떠한 충돌이 발생하지 않고, 움직임의 경로를 따라 모든 n개의 샘플 점들이 테스트되어야하고, 이것은 O(n) 시간 복잡도를 발생시킨다. sampling method에 대해, subdivided되고 sampled되어야 하는것은 시간이 아니라 object motion이라는 것에 주목해라. object overlap을 유지하기위해 object motion을 subdivide하는 것은 가장 간단한 움직임 외에 다른 것에 대해서 사소한 문제가 아니다.

많은 경우에, 오브젝트들은 선형으로 piecewise로 움직인다고 가정되어질 수 있다; 즉, 위치 사이로 평행이동만하는, 움직임의 시작 또는 끝에서 즉각적인 rotational changes와 함께. 따라서, 두 오브젝트들 A와 B에 대해, 오브젝트 B의 움직임은 오브젝트 A로부터 뺄셈될 수 있다. 이제 오브젝트 B는 정지하고, 어떤 교차 테스트는 정지한 object B에 대해 움직이는 오브젝트 A만을 고려할 필요가 있다. 즉, 그 테스트는 효과적으로 서로를 기준으로 그 오브젝트의 움직임을 고려하는 것이다. 만약 한 교차점이 연산된다면, B의 움직임은 오브젝트 관련 좌표보다는 실제 월드 좌표를 얻기 위해 연산된 교차점으로 추가되어야 한다. 다음 섹션에서, dynamic tests에 대한 처음 두 개의 generic methods들은 탐험되고, 그리고나서 공통된 교차 문제들을 다루는 많은 구체적인 방법들이 나온다.


5.5.1 Interval Halving for Intersecting Moving Objects
5.5.2 Separating Axis Test for Moving Convex Objects
5.5.3 Intersecting Moving Sphere Against Plane
5.5.4 Intersecting Moving AABB Against Plane
5.5.5 Intersecting Moving Sphere Against Sphere
5.5.6 Intersecting Moving Sphere Against Triangle (and Polygon)
5.5.7 Intersecting Moving Sphere Against AABB
5.5.8 Intersecting Moving AABB Against AABB

5.6 Summary