충돌처리 - 직선 교차점 이용

1. 충돌처리
· 직선 교차점 알고리즘

1.        직선을 정의하는 두 점(선분의 시작점과 끝점)이 모두 평면의 한쪽 방향에 위치하고 있다면 직선은 
절대로 평면과 교차할 수 없기 때문에 이 두 점이 폴리곤의 양쪽 방향에  존재하는지를 알아본다.
2.        폴리곤을 정의하는 평면과 직선의 교차점을 계산한다.
3.        평면과 직선의 교차점이 폴리곤 영역 안에 포함되어 있는지를 검사해서 폴리곤 영역에 포함될 경우 
충돌을 나타내고 그렇지 않을 경우 충돌하지 않은 것을 나타낸다.

· 평면과 직선의 교차
직선을 정의하는 두 점이 폴리곤을 정의하는 평면의 양쪽에 존재하는지를 알아보는 첫번째 과정은 상당히 쉽다. 
수학에서 정의하는 3차원 평면에 대한 방정식으로 유도할 수 있다.

평면의 방정식
Ax + By + Cz + D = 0
위의 식에서 A, B, C는 평면의 노말 벡터의  x, y, z 요소를 각각 나타내고 D는 폴리곤 위에 존재하는 임의의 
한 점을 방정식에 대입해서 구할 수 있는 값이다.

평면의 방정식의 특징은 평면위에 존재하는 어떤 점을 x, y, z에 대입하더라도 항상 0 이 된다. 이러한 특성을 
이용하여 충돌처리를 할 수 있는데 평면의 방정식의 특성상 평면의 뒤쪽에 존재하는 점을 방정식의 x, y, z에 
대입한다면 음수 값을 가지고 앞쪽에 존재하는 점을 대입하면 양수 값을 갖게 된다. 따라서 직선을 정의하는 두 
점이 평면의 양쪽에 존재하는지를 알아보기 위해서는 단순히 두 점을 평면의 방정식에 대입해서 그 부호가 서로 
다른지를 알아보면 된다.
그럼 다음 함수를 보자
bool LineCrossPlane( Vector *line, Vector &normal, float &D )
{
        float        sign1, sign2;

        sign1 = (normal.i * line[0].x + normal.j * line[0].y + normal.k * line[0].z + D);
        sign2 = (normal.i * line[1].x + normal.j * line[1].y + normal.k * line[1].z + D);

        if( sign1 * sign2 >= 0.0 )
         return false;
        
return true;
}
위의 말을 더 쉽게 풀이해 보면
한 삼각형(평면)의 Face Normal을 Nx, Ny, Nz라고 정의하구 삼각형(평면)의 한점을 Px, Py Pz 라고 한다면, 
삼각형의 노말과 그 삼각형에 속하는 한점을 DotProduct를 하면 0 이 된다.이 말을 평면의 방정식에 대입하면 
이렇게 된다...
Nx * Px + Ny * Py + Nz * Pz + D = 0 ........ (1)
(평면의 방정식 A*x + B*y + C*z + D = 0 )

여기서
A = Nx
B = Ny
C = Nz
D = -( Nx * Px + Ny * Py + Nz * Pz )
Px, Py, Pz 는 평면에 속하는 한점이다.

· 교차점 계산
직선을 정의하는 두 점이 평면의 양쪽에 존재한다면 반드시 직선과 폴리곤이 교차하는 교차점이 존재한다고 
할 수 있다. 이러한 교차점을 구하기 위해서는 평면과 직선을 모두 방정식으로 표현해야 한다.

평면의 방정식
Ax + By + Cz + D = 0

직선을 방정식으로 표현하는 방법은 여러 가지가 있지만 그 중에서 직선 위에 존재하는 모든 점을 가장 간편하게 
나타내는 방정식은 직선의 시작점으로 부터의 거리를 이용하는 방법이다.

P(d) = Po + dD
위의 식에서 D는 직선의 방향을 나타내는 단위 벡터이고 P(0)는 시작점을 그리고 d는 P(0)으로부터 D 벡터가 정의
하는 방향으로 떨어져 있는 거리를 나타낸다. 따라서 P(d)는 P(0)으로부터 d만큼 D방향에 떨어져 있는 직선 위의 
한 점을 나타낸다. 위에서 정의한 일반식을 x, y, z 요소로 분할하면 다음과 같음을 알 수 있다.

Px = xo + dDx
Py = yo + dDy
Pz = zo + dDz
위에서 Px, Py, Pz는 직선의 시작점 xo, yo, zo로부터 Dx, Dy, Dz 방향으로 d만큼 떨어져 있는 직선 위의 한 점에 
대한 x-, y-, z- 요소를 나타낸다.

그럼 임의의 한 점에 대한 평면의 방정식을 써보면
Axo + AdDx + Byo + BdDy + Czo + CdDz + D = 0
위와 같이 된다.
만일 직선 위의 한 점 Px, Py, Pz가 평면위에 존재한다면(교차점이라면) 이 방정식의 왼쪽 항은 0값을 갖게 된다. 
따라서 위의 방정식으로부터 교차점을 찾기 위해서 먼저 상수 d에 대해 정리하면

d(Adx + BDy + CDz) + Axo + Byo + Czo + D = 0                 이것을 다시 정리하면
d = -(Axo + Byo + Czo + D) / (ADx + BDy + CDz)

Dx, Dy, Dz는 직선의 방향을 나타내는 단위 벡터이고 A, B, C, D는 평면을 나타내는 방정식의 계수다. 또 xo, 
yo, zo는 직선의 시작점을 나타내기 때문에 모두 상수임을 알 수 있다. 따라서 아무 문제없이 위의 방정식으로부터 d값을 구할 수 있다.

¨ NOTE
만일 평면과 직선이 서로 평행이라면 위의 방정식의 분모는 0 이 된다. 그 이유는 위 방정식의 분모를 보면 
평면에 수직인 법선벡터(A, B, C)와 직선의 방향을 나타내는 벡터(Dx, Dy, Dz)에 대한 내적임을 알 수 있다. 
만일 평면과 직선이 평행이라면 평면에 수직인 법선 벡터와 직선의 방향 벡터가 이루는 각은 90도이다. 따라서 
내적 정의에 의해 0이 된다.

함수는 다음과 같다.
bool  LineIntersectPlane( Vector &point, Vector *line, Vector &normal, float &D )
{
        Vector line2 = line[1] – line[0];
        float        d, first, second;
        
        line2.Normalize();        // 단위벡터로 만든다.

        first = -( normal.i*line[0].x + normal.j*line[0].y + normal.k*line[0].z + D );
        second = ( normal.i * line2.i + normal.j * line2.j + normal.k * line2.k );

        if( second == 0 )
          return false;
        
        d = first / second;

        if( d < 0 )
          return false;

        point = (line[0] + (Vector)(line2 * d));
        return true;
}

· 폴리곤 영역에서 충돌이 일어났는지 판별
폴리곤 영역에서 충돌이 일어났는지 판별하기 위해서는 교차점과 폴리곤의 Vertex가 이루는 각의 합을 계산해서 
360도와 같다면 영역에 포함된다고 할 수 있다.

내적 공식
A · B = |A| |B| cosq
위에서 q는 두 벡터가 이루는 각을 나타낸다. 따라서  이 방정식을 q에 대해 풀면 다음과 같다.

q = cos¯¹ (A · B / (|A| |B|))
위에서 cos¯¹은 코사인 함수의 역함수를 나타낸다. 폴리곤의 버텍스로부터 벡터 A와 B를 계산하기 위해서는 
단순히 각 버텍스에서 교차점을 빼면 된다.

내적 계산
A·B = x1x2 + y1y2 + z1z2

함수로 표현하면
bool  IsPointBounding( Vector &point, Vector  *Poly, long VertexCount )
{        
float Angle = 0.0f;

const MATCH_FACTOR = 0.99;
Vector A, B;

for( long n = 0; n {
        A = (Vector)(Poly[n] – point);
        B = (Vector)(Poly[(n+1) % VertexCount] – point);
        Angle += acos( A.Dot(B) / (A.Mag() * B.Mag()));
}

if( Angle >= (MATCH_FACTOR * (2.0 * PI)) )        // 360도는 2PI
  return true;
        
return true;
}


위의 세가지 과정을 통합한 것을 함수화 하면
bool LineIntersectsPolygon( Vector *line, Vector *poly, long VertexCount, Vertex &iPoint )
{
float D;
Vector          PolyNormal;

MakeNormal( poly, PolyNormal, D );

if( !LineCrossPlane( line, PolyNormal, D ) )
        return false;

LineIntersectPlane( iPoint, line, PolyNormal, D );

if( !IsPointBounding( iPoint, poly, VertexCount ) )
        return true;
}

· 직선 교차점 알고리즘을 이용한 폴리곤 충돌 검사
위에서 말한 직선 교차점 알고리즘은 직선과 폴리곤의 충돌을 알아보는 방법이었다. 그렇다면 지금부터 이 
알고리즘을 이용해 폴리곤간의 충돌검사 알고리즘을 만들어 보도록 한다. 직선 교차점 알고리즘을 이용해서 
폴리곤 충돌 검사를 하는 것은 매우 단순한 작업이다. 먼저 충돌 검사를 수행할 폴리곤을 A, B라 하고 폴리곤 
A의 각 경계선을 직선으로 정의한다. 그리고 이렇게 정의된 직선들과 폴리곤 B를 직선 교차점 알고리즘을 
이용해서 각각 충돌 검사를 한다. 충돌 검사에서 사용된 직선들은 폴리곤 A의 경계선을 나타내기 때문에 
이들 중 어느 하나라도 폴리곤 B와 교차한다면 두 개의 폴리곤은 서로 교차한다고 말 할 수 있다. 그러나 
어느 한 폴리곤만을 기준으로 처리할 경우 두 개의 폴리곤이 서로 교차함에도 불구하고 교차점을 알아낼 수 
없는 상황이 발생하게 된다. 따라서 A, B 폴리곤의 경계선을 모두 상호 비교해야 한다.

이것을 함수화 하면
bool  PolygonIntersect( Vector *A, long AVertexCount, Vector *B, long BvertexCount, Vector &iPoint )
{
long n;
Vector         Edge[2];

for( n = 0; n < AVertexCount; n++ )
{
  Edge[0] = A[n];
  Edge[1] = A[(n+1) % AVertexCount];
if( LineIntersectsPolygon( Edge, B, BvertexCount, iPoint ) )
        return true;
}

for( n = 0; n < BVertexCount; n++ )
{
  Edge[0] = B[n];
  Edge[1] = B[(n+1) % BVertexCount];
if( LineIntersectsPolygon( Edge, A, AvertexCount, iPoint ) )
        return true;
}

return false;
}

· 복잡한 충돌검사 처리
충돌 검사 알고리즘은 폴리곤에 평행하게 접근하는 직선과 충돌하기 바로 직전에는 평면의 앞쪽에 있다가 
충돌 후에는 폴리곤의 반대편으로 이동하는 경우 충돌을 정확하게 알아내지 못한다. 보통의 경우 이러한 
문제는 따로 처리할 필요가 없다. 왜냐하면, 가상세계의 객체는 복잡한 폴리곤으로 구성되기 때문에 객체를 
구성하는 폴리곤 중 하나라도 충돌이 포착되면 충돌처리를 해주면 되기 때문이다.

그러나 객체의 이동 속도가 굉장히 빠르다거나 혹은 사용자의 컴퓨터가 느릴 경우 객체의 어떤 폴리곤도 
충돌 객체에 걸리지 않고 빠져나가는 경우가 발생하게 된다. 이 문제를 해결하기 위한 가장 간편한 방법은 
첫번째 프레임에서의 객체의 위치와 다음 프레임에서의 객체의 위치를 연결하는 직선을 이용하는 것이다. 
이 직선 중에 하나가 다른 물체와 교차한다면 두 객체가 충돌한 것이기 때문에 물체를 이동시키지 말아야 한다.

· 충돌 검사를 위한 최적화
많은 폴리곤에 대하여 충돌검사를 수행한다면 수많은 수학적 연산에 의해 수행 속도를 떨어뜨릴 위험이 있기 
때문에 충돌검사 최적화를 해주어 충돌검사 회수를 감소시킬 수 있다.
첫번째 최적화 방법은 각 폴리곤과 객체에 대한 바운딩 스피어를 이용하는 방벙이다. 움직이는 객체의 바운딩 
스피어를 가상세계에 존재하는 다른 객체의 바운딩 스피어와 먼저 검사해서 서로 충돌이 발생했다면 각 객체가 
갖는 폴리곤의 바운딩 스피어와 다시 비교해서 충돌이 발생한 폴리곤을 찾는다. 마지막으로 이렇게 찾은 
폴리곤에 대해서 다시 라인 교차점 알고리즘을 이요해 정확한 교차점을 계산한다. 이방법은 바운딩 스피어를 
이용해 비교하는 범위를 줄여 가는 최적화 기법이라 할 수 있다. 따라서 이 방법을 사용할 경우 객체가 갖는 
모든 폴리곤에 대해 라인 교차점 알고리즘을 적용해야 하는 비효율을 줄일 수 있게 된다. 두개의 바운딩 
스피어가 교차하는지를 알아보기 위해서는 두 바운딩 스피어의 중심간의 거리를 계산하면 된다. 만일 이 
거리가 두 바운딩 스피어의 반지름의 합보다 작다면 두개의 구는 서로 교차하고 있다.

¨NOTE
폴리곤 또는 객체에 대한 바운딩 스피어를 계산하기 위해서는 먼저 바운딩 스피어의 중심점으로 사용되는 
객체의 중심점을 계산해야 한다. 모든 버텍스의 x, y, z값을 각각 더한 값을 버텍스의 개수로 나누면 객체의 
중심점을 구할 수 있으며, 이 중심으로부터 가장 먼 거리에 있는 버텍스와 거리가 바로 바운딩 스피어의 
반지름이 된다.

두 번째 최적화 방법은 가상세계를 작은 단위로 분할하는 방법이다. 이렇게 분할된 공간 안에 속하는 폴리곤을 
리스트로 관리하면서 충돌 검사를 할 때는 이 영역에 포함되는 폴리곤에 대해서만 충돌 검사를 수행하는 방법이다. 
이 방법을 사용하게 되면 특정 객체가 존재하는 가상세계의 일부 영역에 대해서만 충돌 검사를 할 수 있기 때문에 
충돌 검사를 해야하는 횟수를 크게 줄일 수 있는 장점이 있다. 하지만 복잡한 자료구조를 구성해야 한다는 단점이 있다.

· 바운딩 박스
바운딩 박스를 만들 때 우선 모든 면의 노말이 밖을 바라보게 바운딩 박스를 만들던지 아니면 모든면이 안으로 보는 
바운딩 박스를 만들어야 한다. 그럼 평면에 방정식을 이용해서 바운딩박스의 각각의 면에 한점이 면의 앞에 있는지
뒤에 있는지를 알수가 있을 것 이다. 만약 모든 바운딩박스의 면을 밖으로 바라보게 하였다면 한점이 바운딩박스의 
모든면에 대해서 평면의방정식 < 0 을 성립한다면 그 한점은
바운딩 박스에 안에 들어 있는 것임을 알수 있다.

· 바운딩 충돌
바운딩 박스는 8점으로 이루워져 있으므로 바운딩박스 & 바운딩박스의 충돌은 한쪽의 바운딩 박스에 다른쪽의 
바운딩박스의 8점을 검색해서 충돌여부를 판단하구 충돌이 없다면 이번에는 반대로 한번 더 검사해서 최종 결정을 
내리면 된다.

· 몇가지 주의점
바운딩박스가 만약 움직이는 물체에 붙어있다면 그 물체가 움직이고 회전하는 값을 그대루 바운딩 박스에 적용해야 
합니다. 바운딩 박스가 회전을 하든지 움직일때 마다 항상 새로 바운딩박스의 면의 노말을 구해서 평면의 방정식에 
사용해야 한다. 그래야 정확한 충돌을 찾을 수 있다.


[원본] http://expert3d.egloos.com/598593