Collision Detection

설치

npm install

실행

npm run start 

SAT 설명

원리

분리축을 구해서 분리축이 한개라도 있으면 충돌 판정

GJK 설명

원리

모든 좌표를 민코프스키 차이를 구해서 원점(0, 0)을 포함하고 있으면 충돌 판정

GJK가 SAT 보다 빠른 이유는

SAT는 다각형일 경우 모든 축에 대한 분리축 검사를 해야합니다.

GJK는 원점을 포함하는 삼각형을 빠르게 구해 SAT 보다 빠르게 검사합니다.

충돌 파악

1D 일때 (1-Simplex)

leftEndpoint < 0rigin < rightEndpoint

2D 일때 원점을 포함하는지 원리 (2-Simplex)

• 민코프스키 공간에 원점을 포함하는 삼각형을 만듭니다.

  • 최고의 3점 만들기

    • 임의 방향을 정합니다.

    • 주어진 방향(D)을 따라 서로 가장 먼 두 점을 찾습니다.

    • 두 점의 민코프스키 차이를 구해 한 지점을 찾습니다.

      • 이 지점이 첫 번째 심플렉스(C)입니다. (0-Simplex)

    • 첫 번째 심플렉스로 부터 원점을 바라보고 수직인 방향을 찾습니다.

    • 수직 방향에서 서로 가장 먼 두 점을 찾습니다.

    • 두 점의 민코프스키 차이를 구해 한 지점을 찾습니다.

      • 이 지점이 두 번째 심플렉스(B)입니다. (1-Simplex)

    • 두 번째 심플렉스가 첫 번째 심플렉스와 원점을 향하는지 확인

      • if ((CO ⋅ OB) > 0)
      • 점의 내적 CO ⋅ OB 이 양수이면 점 B는 원점을 넘어 C방향을 향합니다.
      • 그렇지 않을 경우 다른 방향으로 검사

    • 세 번째 방향을 구합니다.

      • CB에서 원점을 수직으로 향하는 방향을 구합니다.
        • vector triple product 로 원점을 향하게 할 수 있습니다.
        • CB x CO x CB

    • 세 번째 방향으로 가장 먼 두 점을 구하고 마지막 심플렉스(A)를 구합니다.

• 충돌 판정

  • 삼각형이 원점을 포함하는지 확인합니다.
    • 삼각형의 모든 엣지에서 법선 벡터(수직)
    • 삼각형의 반대 정점까지의 원점 벡터
    • 두 벡터의 내적이 양수인지 (0보다 큰지) 확인

관련 링크

• dyn4 Java Collision Detection and Physics Engine