[Graphics] Ray와 물체의 충돌 판정 알고리즘(AABB/OBB)

AABB(Axis-Aligned Bounding Box)

 

ray와 AABB의 충돌을 판단하는 알고리즘은 Cyrus-Beck Clipping 이라고도 한다.

Clipping는 오린다, 자른다는 뜻이다. 

 

Box는 평행한 두 면의 쌍 3개로 이루어져 있다. 즉 xy, yz, zx 면이 2개씩 있다. 

 

대표적으로 xy면을 보자. 

xy면은 두 개의 x값을 가지고 두 개의 y값을 가진다. 

이 값을 따라서 평행하게 직선으로 이어본다. 

ray는 지나가면서 이 네 개의 직선, 즉 작은x값, 큰x값, 작은y값, 큰y값을 지나게 될 것이다. 

 

 

 

아래와 같이 ray가 각 직선을 지나는 위치를 살펴본다. 

아래의 경우 작은Y값, 큰Y값을 먼저 지난 후, 작은 X값, 큰 X값을 지났다. 

즉 값을 비교하면 nearY < farY < nearX < farX  이다. 

이렇게 near보다 far가 더 작은 경우가 있다면 ray는 AABB를 지나지 않았다고 판단한다. 

 

 

 

반면 아래의 경우 nearY < nearX < farY < farX 로, 모든 near보다 far의 값이 더 크다. 

이 경우는 도형을 잘 보면, x와 y가 교차되는 부분이 있다. 즉 xy면의 내부를 지난 것이다. 

 

 

이렇게 모든 near보다 far가 더 큰 것이 xy, yz, zx 면에 대해 모두 성립하면 ray가 AABB와 충돌했다고 판단한다. 

 

 

 

 

OBB(Oriented Bounding Box)

 

AABB와 같은 알고리즘을 이용한다.

다만 축이 틀어져있기 때문에 좌표축에 projection을 하여 nearX,farX,nearY,farY를 구한다.