6. Detection Collision (1)

지금까지

• input, output, scenegraph
• 이제 input을 어떻게 update할 것인가에 대해 배워보자

Simulataion/Update 모드에서 필요한 것은?

• 행위 시뮬레이션 (애니메이션)
  • 점프를 하고, 걷는 시뮬레이션 , 그 외에 걷다가 넘어지는 등의 작업
• 물리
  • 초창기에는 많은 물리 계산을 할 수 없어서 못했지만 이제는 가능해짐
    -게임의 자유도가 높아질 수있도록 물리 계산이 중요해짐

물리 모듈

• 동역학을 계산해서 시뮬레이션 해야함
• 부딛힘을 알아야, F=ma 식으로 변화량을 계산할 수 있다

Collision Detection

• 대부분의 상호작용이 물리적 자극과 충돌로 인해 발생한다
• 부딛힘을 인지하는 것 / 반응이 동시에 일어나는 것이 중요하다
  • 시뮬레이션 : 각 물체의 속도, 이동량
  • 렌더링 : 겹치지 않게 하는 데에 필요하다 (조금은 겹쳐도 됨)
    -> 같은 계산이지만 목적이 다르기 때문에 다른 계산을 쓰기도 한다

예시로 설명해보자

• 복잡한 미로를 걷는다고 쳐보자
• 어디에 부딛힐까? 1) 벽 2) 좀비!

Case1: Navigation (point - object)

• 플레이어가 특정 지점에 갈 수 있는지를 판단해야 함
• 플레이어가 보고있는 시점으로 이동할 수 있는가?
• 미로 벽과 나의 시점이 충돌하는지 확인해야 함
  -> 내가 이동하려는 지점 (point)가 다른 object의 내부에 있는지 확인하자!

Point Inclusion Test

💡Bounding Sphere

• 물체가 구 라면 가장 쉽게 체크할 수 있다. 구의 방정식 쓰면 됨!
  • 방정식에 값을 넣어서 < 0 이면 구의 내부, >0 이면 구의 외부, = 0 이면 딱 접함
• Bounding Sphere(=컨저버티브 볼륨) : 물체를 둘러싸는 구를 만들어서 구끼리 부딛히는지 계산하는 방법
• Bounding Sphere를 사용하면 적어도 방어적으로 뚫고가는 케이스는 막을 수 있다!

Bounding Sphere의 문제점

• 빈 공간이 너무 많다. 세로로 엄청 긴 물체가 있다면 가로 부분이 너무 많이 빈다!
  -> 구 말고 박스를 쓰면 어떨까?

💡Bounding Box

• 충돌을 박스 형태로 확인하자!
• Axis Aligned Bounding Box (AABB)
  • x,y 축의 가장 작은값, 큰값을 기준으로 박스를 만들어서 물체를 둘러싸서 충돌을 체크한다
    -> 계산이 쉽다 !
  • 단점 : Bounding Sphere처럼 빈공간이 많이 생길수도 있다 → 물체가 회전하면 빈 공간이 더 늘어날 수도 있다
    
• Oriented Bounding Box (OBB) : 물체가 회전했을 때 박스도 같이 회전한다. 회전 값을 미리 계산해서 박스의 형태를 만들어둔다 → 회전이 많이 일어나고 정확성이 중요할 때 사용한다
  

Bounding Box Inclusion Test

• AABB : x,y,z 좌표의 최댓값과 최솟값 사이에 존재하면 충돌한다
• OBB

  • 정육면체 한 면의 평면의 방정식과 각각 다 계산해서 확인한다

  • 평면 위의 한점 x 와 특정 점을 잇는 벡터와, 평면의 법선 벡터를 내적 = 0 이면 같은 평면에 있다!

    → 두 개 이상의 평면과 닿았는지를 확인할 때는 정사영해서 구할 수 있다

Point Inclusion만으로 충분할까?

• 아니다! 속도가 너무 빠르면 벽을 뛰어넘어 갈 수도 있다
• 내가 이동하려는 경로의 직선의 방정식 - 벽이 닿았는지 확인해야 한다 ⇒ Ray Intersection
  

💡 Ray Intersection

• x1 지점부터 x2 지점까지의 직선의 방정식을 벡터로 표현한 후 밑의 식처럼 표현되면 만난다고 할 수 있다

이제 알게된 것

• 이제 우리는 오브젝트를 둘러싼 바운딩 영역과 - 벽이 닿는지를 계산했다!
• 실제 매시와 벽이 닿았는지도 확인해야 한다! → mesh 와 ray 간의 충돌 검사를 해보자. 근데 복잡함! → 어떻게 하면 매시들을 모두 충돌검사를 할 수 있을까?
  

💡 Bounding Volume Hierarchy

• 오브젝트도 너무 많고, 매시 안에 삼각형도 너무 많아서 계산하기가 너무 어렵다 !
• mesh 삼각형들 간의 충돌 검사를 해야 한다, 너무 많다!
• 계층 구조로 바운딩 박스를 만들어서 충돌을 계산하고, 부모와 충돌하면 자식 노드로 계속 내려간다. → 반드시 자식 바운딩 영역은 부모 영역에 포함된다! → 모든 mesh에서 확인할 필요 없고, 큰 범위에서 먼저 확인하게 된다
  

💡 BSP Tree

• 공간을 여러 개로 나눠가는 트리
• 직선에 의해 공간을 계속해서 나눠서 필요한 공간만 확인한다
• Ray에서 효율적이지는 않다!
• 내 캐릭터가 아무리 해도 몇 초 이내에는 G 영역 안에만 있을것이다 → G 영역만 확인할 수 있어 효율적이다!
  

Case2 : Object vs Object

• 나와 좀비가 닿는지 어떻게 알 수 있을까?
• 1) 오브젝트로 비교하기 : 각 오브젝트의 중심 거리를 비교해서 일정 거리보다 가까우면 충돌한 것으로!
• 2) AABB로 비교하기 : 바운딩 박스의 min, max 값을 비교해서 겹치는지를 판단한다
• 3) OBB로 비교하기 : 두 바운딩 박스를 나누는 평면이 존재하는지를 확인, 모든 평면에 대해 Projection을 진행해서 확인할 수 있다

오브젝트들끼리 충돌했는지는 어떻게 알까?

• 바운딩 영역이 충돌한걸 알았으면 또 매시들끼리 닿았는지도 확인해야 한다
• 비교할 게 너무 많다 ! 1) Octree-based Representation (3DDDA) : 계층 구조로 만든다 2) Refined Bounding Volumes : 바운딩 볼륨을 더 작은 구로 표현해서 계산한다
  

오브젝트가 움직이면 어떻게 하지?

• 두 오브젝트가 이동했을 때 충돌했을까? 이동 속도가 너무 빠르면 충돌 지점을 찾을 수가 없다.. → 자세한 건 다음 시간에!
  

---

💡 Collision Response

• 충돌이 된 상태를 Resolve 해야 한다
  • 절대 겹치면 안된다 (Hard Constraints를 가진다)
• 물리적인 시뮬레이션을 해줘야 한다
  • 튕기기, 부숴지기, 결합 등의 물리적 시뮬레이션
• 시간 계산을 해줘야 한다
  • 시뮬레이션을 언제 할까?

두 가지 경우를 생각해보자

• 당구를 하는 경우!
• 1) 벽에 부딛히는 경우
• 2) 두 개의 공이 부딛히는 경우

Case1) 공과 벽이 부딛히는 경우

• 속도는 ?
  • Perfect Collision : 에너지를 잃지 않는 경우 입사각과 반사각이 동일하게 반사진행한다
  • Energy Loss : 어느 정도 속도를 잃고 진행한다

💡 Elastic vs Inelastic

• 공이 RigidBody라면 유연하지 않기 때문에 바로 반대로 진행할 것이다
• 그러나 말랑한, 유연한 공이라면 2가지의 과정을 가진다
  • 압축 : 공이 부딛히면서 눌리는 순간
  • 복구되는 과정 : 다시 반동으로 튕겨져 나가는 순간
• 손실된 에너지는 소리나 열로 나타난 후 나머지 에너지를 속력으로 가진다
• Rigid vs Elastic vs InElastic
  • Rigid : Compression X (부딛힌 후 바로 반대 방향으로 나간다)
  • Elastic : Compression O, Restitution O
  • InElastic : Compression O, Restitution X ( 부딛힌 후 반동으로 튕겨나가지 않고 합쳐져서 나간다 )

Elastic Collision

• 두 개의 공이 충돌한다고 했을 때, momentum과 kinetic energy가 보존된다는 가정 하에 방정식을 세운다
• 그 때의 질량, 방향 등에 의해 가속도를 변경한다
• 두 물체가 충돌 후 원래의 방향을 어느정도 유지하며 나간다

Perfectly Inelastic Collision

• 두 개의 물체가 부딛힌 후 합쳐져서 진행한다
• momentum 이 보존되지만 kinetic 에너지는 보존되지 않는다

정리

• Collision Detection
  • Hierarchical Approach : BV Hierachy 바운딩 볼륨으로 계층을 사용해서, 아예 아닌 경우에 빨리 탈출하고, 점점 더 정교한 비교를 하도록 한다
• Collision Response
  • Rigid
  • Elastic
  • InElastic