Collision Detection

Collision Detection

Wanho Choi

(wanochoi.com)

Collision (

충돌)

•

Real world objects

•

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

•

_{Virtual world objects}

Collision Resolution (

충돌 처리)

•

Collision detection (

충돌 탐지)

•

_{두 물체가 충돌하는가?}

•

_{기하학(geometry)적인 문제}

•

Collision response (

충돌 반응)

•

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

•

_{물리학(physics)적인 문제}

Collision Resolution (

충돌 처리)

•

Collision detection (

충돌 탐지)

•

_{두 물체가 충돌하는가?}

•

_{기하학(geometry)적인 문제}

•

Collision response (

충돌 반응)

•

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

•

_{물리학(physics)적인 문제}

※

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

Strategy (

전략)

Collision detection

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

•

_{Broad-phase collision detection}

•

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

•

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

•

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

•

Narrow-phase collision detection

•

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

해서 정밀 검사를 수행함

Strategy (

전략)

Strategy (

전략)

Strategy (

전략)

k-Dop

•

k

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

•

AABB

의 모서리를 잘라낸 형태

k-Dop

•

k

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

•

AABB

의 모서리를 잘라낸 형태

Bounding Volume Elements

Sphere Packing

Level Set Method

Brute Force Algorithm

•

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

i

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

충돌 여부를 계산

•

_Complexity:

_O(n

2

)

Computer Graphics

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

•

Spatial partitioning

Acceleration Structure

Uniform Hash Grid

Quadtree (Octree) Grid

k-D Tree

BVH (Bounding Volume Hierarchy)