Simple Intersection Tests For Games (의역)

[원문]
http://www.gamasutra.com/view/feature/131790/simple_intersection_tests_for_games.php?page=1

 당신의 차가 시속 180마일로 finish line을 통과하든, 총알이 당신 절친의 가슴을 꿰뚫든, 모든 게임의 Object Intersection에서는 충돌탐지를 사용합니다.

 이 기사는 대부분의 형상(Shape)에 활용되는 몇가지 간단한 Intersection Test를 소개합니다. => [Sphere, Box]

Sweep Tests for Moving Objects

Collision Detection의 가장 공통적인 접근법은
 매 Frame이 끝날 때, 두 물체가 Overlap되는지를 테스트 하는 것입니다.
문제는 이 방법이 두 대상이 서로 빠르게 움직이면서 교차할 때, 탐지하지 못할 수도 있다는 것입니다.
 이 문제를 피하기 위해, 물체들의 궤적을 작게 분할한 다음, 매 Point에서 Check 하는 방법을 사용할 수 있습니다. 하지만 이 경우 물체의 (Frame 사이) 이동 간격이 넓을 경우, 너무 비싼 비용을 지불해야 합니다.
 반면에, Sweep Test는 효율적으로 (물체가) Overlap되는 시간 간격을 결정할 수 있고, 이는 Subdivision 알고리즘에서 최적의 시작점으로 이용될 수 있습니다.

A Sphere-Plane Sweep Test

[Figure1. 평면을 통과하는 구]

 위의 그림은, 평면을 빠르게 가로지르는 구의 예를 보여줍니다.
이는 점 C0가 평면의 positive side에, 점 C1가 negative side에 있는 것으로 확인할 수 있습니다.

 일반적으로, 구가 (Frame의 어느 시점에) 평면을 가로지를 때, d0 > r 이고 d1 < r 입니다.

 (r은 구의 반지름, d0과 d1은 점 c0, c1에서 평면까지의 거리)

이제, 점 C에서 평면까지의 (signed)distance는 해당 공식으로 얻을 수 있습니다.

그리고 좀 더 효율적으로, 우리는 평면을 {n, D}이라는 형태로 정리할 수 있지요.

 


그럼, 거리 d는 다음과 같이 계산됩니다.

 

 한편, 점 C0 -> C1 까지의 궤적은 u라는 변수를 통해 파라메터화 할 수 있습니다. 

이 변수는 점 C0에서의 값이 0, 점 C1에서의 값이 1이기 때문에, 

정규화된 시간(변수)로 간주할 수 있습니다.

 (정규화된 시간에서) 구가 처음 평면과 교차하는 시점은, 이렇게 표현 가능합니다.

 이 시점(ui)에서 구의 중심은, 점 C0와 C1의 아핀결합으로 보간(interpolation)될 수 있습니다.

(참고 링크 - https://blog.naver.com/jspark_/220405026284)

위의 공식은 d0가 d1과 다르다는 조건 하에 (displacement(변위 이동)가 발생하는 조건) 

Ci를 정확히 보간합니다. r=0 일 때 조차두요(line segment인 경우)

 원한다면, 파라메터 u는 또한 해당 점에서 물체의 방향을 선형보간 하는데 사용될 수 있습니다.

 해당 예를 통해, 구는 평면의 positive side로부터 접근하고, C0 지점에서 평면을 관통하지 않았다는 사실을 알 수 있습니다.  

 이전 frame에서 이미 관통이 이뤄졌음을 가정한 case라면, |d0| <= r 이라는 조건이 성립해야 합니다.

 Listing 1은 이 sphere - plane sweep 테스트의 구현부입니다.


[번역 추가 중입니다 --]

Listing 1. A sphere-plane sweep test.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55

#include "vector.h" class PLANE { public:     VECTOR N;     //unit normal     SCALAR D;     //distance from the plane to the origin from a      //normal and a point     PLANE(const VECTOR& p0, const VECTOR& n) : N(n), D(-N.dot(p0))     {}     //from 3 points     PLANE(const VECTOR& p0, const VECTOR& p1,         const VECTOR& p2) : N((p1 - p0).cross(p2 - p0).unit()),         D(-N.dot(p0))     {}     //signed distance from the plane topoint 'p' along      //the unit normal     const SCALAR distanceToPoint(const VECTOR& p) const     {         return N.dot(p) + D;     } }; const bool SpherePlaneSweep (     const SCALAR    r,    //sphere radius     const VECTOR&    C0,    //previous position of sphere     const VECTOR&    C1,    //current position of sphere     const PLANE&    plane,    //the plane     VECTOR&    Ci,    //position of sphere when it first touched the plane     SCALAR&    u    //normalized time of collision ) {     const SCALAR d0 = plane.distanceToPoint(C0);     const SCALAR d1 = plane.distanceToPoint(C1);     //check if it was touching on previous frame     if (fabs(d0) <= r)     {         Ci = C0;         u = 0;         return true;     }     //check if the sphere penetrated during this frame     if (d0 > r && d1 < r)     {         u = (d0 - r) / (d0 - d1);    //normalized time         Ci = (1 - u)*C0 + u*C1;    //point of first contact         return true;     }     return false; } Colored by Color Scripter

cs