Collision Detection

전체 글

(1)

Collision Detection

Wanho Choi

(wanochoi.com)

(2)

Collision (

충돌)

Real world objects

충돌시 서로 통과하지 못함 (non-penetrating solidity)

Virtual world objects

(3)

Collision Resolution (

충돌 처리)

Collision detection (

충돌 탐지)

두 물체가 충돌하는가?

기하학(geometry)적인 문제

Collision response (

충돌 반응)

만약 두 물체가 충돌한다면 충돌 후 어떻게 반응하는가?

물리학(physics)적인 문제

(4)

Collision Resolution (

충돌 처리)

Collision detection (

충돌 탐지)

두 물체가 충돌하는가?

기하학(geometry)적인 문제

Collision response (

충돌 반응)

만약 두 물체가 충돌한다면 충돌 후 어떻게 반응하는가?

물리학(physics)적인 문제

이 발표에서는 collision detection만을 다룸.

(5)

Strategy (

전략)

Collision detection

을 두 단계로 나누어서 진행한다!

Broad-phase collision detection

우선 충돌 가능성 여부를 단순화하여 빠르게 찾아냄

충돌 가능성이 없는 물체들을 신속하게 제거함

정밀 테스트를 위한 후보군을 추려냄

Narrow-phase collision detection

첫 번째 테스트를 통과한 충돌 가능성이 있는 후보군에 대

해서 정밀 검사를 수행함

(6)

Strategy (

전략)

(7)

Strategy (

전략)

(8)

Strategy (

전략)

(9)

k-Dop

k

개의 고정된 방향의 평면들로 둘러싸여진 부피

AABB

의 모서리를 잘라낸 형태

(10)

k-Dop

k

개의 고정된 방향의 평면들로 둘러싸여진 부피

AABB

의 모서리를 잘라낸 형태

(11)

Bounding Volume Elements

(12)

Sphere Packing

(13)

Level Set Method

(14)

Brute Force Algorithm

충돌 검출을 해야하는 n개의 물체가 있을 때,

i

번째 물체에 대해서 나머지 (n-1)개의 물체들에 대해서

충돌 여부를 계산

Complexity:

O(n

2

)

Computer Graphics

에서 절대적으로 피해야하는 복잡도!

(15)

Spatial partitioning

Acceleration Structure

(16)

Uniform Hash Grid

(17)

Quadtree (Octree) Grid

(18)

k-D Tree

(19)

BVH (Bounding Volume Hierarchy)

(20)

수치

Updating...

참조

  1. wanochoi.com)
관련 주제 :