[그래픽스] 충돌 검사 - 점과 점/선/평면과의 충돌

오늘의 TIL 목차 (23. 01. 10)

 

• 점과 점/선/평면과의 충돌

점과 점 사이의 거리

---

1. 2차원 상의 점과 점 사이의 거리

피타고라스 정리를 이용하여 구한다.

2차원 상의 점과 점 사이의 거리 =피타고라스)

 

2. 3차원 상의 점과 점 사이의 거리

각각의 좌표값의 차를 제곱해서 모두 더해준 후 루트를 씌우면 점과 점 사이의 거리를 구할 수 있다.

3차원 상의 점과 점 사이의 거리 공식

빗변: 방향벡터, 밑변: zy 평면 상의 점 P와 Q 사이의 빗변

 

※ 실제 코드에서는 제곱근(루트, sqrt)을 구하는 것이 비용이 높기 때문에
충돌 검사 시 거리 대신 거리의 제곱값을 사용하는 것이 보통이다. 

두 중심 사이의 거리는 벡터를 이용해서 구할 수 있다.

// || P-Q ||
XMVector3Length(VectorP - VectorQ);

 

점과 선 사이의 거리

---

점과 선 사이의 거리는 직선, 반직선, 선분으로 구분지을 수 있다.

1. 점과 직선 상의 거리

직선은 양쪽으로 끝없이 뻗어나가는 선이다.

점과 직선 사이의 거리는 점에서 직선으로 수직인 선분을 그리면 그 선분의 길이(높이)가 거리가 된다.

점과 직선 상의 거리 제곱값 구하는 공식

 

공식을 아래 그림에 따라 설명하면 다음과 같다.

피타고라스의 정리에 의하여 $높이 = \sqrt{빗변 - 밑변}$을 이용하여 구한다.

빗변 = | P - Q |

밑변 = 벡터 w를 벡터 v에 투영한 값 (벡터 투영 공식 참고)

2. 점과 반직선 상의 거리

반직선(광선)은 한 방향으로 무한히 뻗어나가는 선이다.

반직선 $L(t) = Q + t * v(0 <= t)의 경우, 점과 반직선 사이의 거리는 두 가지 경우로 나뉜다.

• 점이 반직선 위에 있는 경우 $(0 <= t)$
• 점이 반직선 위에 없는 경우 $(0 > t)$

2.1. 반직선 위에 있는 경우

점과 직선 사이의 거리를 구하는 식을 그대로 사용하면 된다.

점과 직선 상의 거리 제곱값 구하는 공식

2.2. 반직선 위에 없는 경우

점 P와 점 Q 사이의 거리를 구하면 된다. 아래 공식 혹은 |벡터P - 벡터Q|로 구한다.

2차원 상의 점과 점 사이의 거리 =피타고라스)

3차원 상의 점과 점 사이의 거리 공식

점이 반직선 위에 있는지 판단하는 법

두 벡터를 내적하여 나온 값 t가 0보다 크거나 같다면 반직선 상에 위치하고, 0보다 작으면 반직선 상에 없음을 의미한다.

t 값은 아래의 과정을 통해 구할 수 있다.

 

점 R은 점 Q에 벡터 w = (P - Q)를 벡터 v에 투영한 벡터와 더하면 나온다.

벡터 투영 공식을 이용하여 구하는 방식

또한 점 R이 직선상에 위치함은 확실하므로 아래 직선의 방정식으로도 구할 수 있다.

직선상의 점을 표현하는 방식

 

만약 t 값이 0 보다 크거나 같다면 점 R은 반직선상에 있게 된다. t값은 아래를 통해 다음과 같이 구할 수 있다.

w: 점 P와 점 Q 사이의 빗변, v: 반직선 상의 벡터

분모 $v \cdot v$는 반드시 0보다 크기 때문에 분자 $w \cdot v$만을 검사하는 것만으로 판단할 수 있다.

XMVector w = abs(vectorP - vectorQ);
XMVector v = 반직선;

if(0 <= XMVector3Dot(w, v)) // t가 0 이상이면 반직선 상에 위치
	점과 직선 사이의 거리
else // t가 0 이하면 반직선 상에 없음
	점과 점 사이의 거리

3. 점과 선분 사이의 거리

선분은 시작점과 끝점이 정해져 있는 선이다.

반직선 $L(t) = Q + t * v(0 <= t <=1)의 경우, 점과 선분 사이의 거리는 세 가지 경우로 나뉜다.

• 점이 선분 위에 없으며, 선분의 시작점보다 작을 경우 $(0 > t)$
• 점이 선분 위에 있는 경우 $(0 <= t <= 1)$
• 점이 선분 위에 없으며, 선분의 끝점보다 큰 경우 $(1 < t)$

점 P와 선분 L(t) 사이의 거리

점이 선분으로부터 어디에 위치하는지 판단하는 법

점이 반직선 위에 있는지 $t$를 이용하여 판단하는 것과 동일하게 진행한다.

 

3.1. 점이 선분 위에 없으며 선분의 시작점보다 작을 경우

t가 0보다 작으면 이에 해당한다.

점P와 점Q 사이의 거리를 구한다.

 

3.2. 점이 선분 위에 있는 경우

점과 직선 사이의 거리를 구한다.

3.3. 점이 선분 위에 없으며 선분의 끝점보다 클 경우

t가 1보다 크면 이에 해당한다.

점 P와 점(Q + v) 사이의 거리를 구한다.

점과 평면 사이의 거리

---

점과 평면 사이의 거리

점과 평면 사이의 거리는 점 P가 평면에 수직인 선분을 그리면 그 선분의 길이(높이)가 거리가 된다.

즉, 점과 평면 사이의 거리 d는 벡터 $v = P - Q$를 법선벡터 $n$에 투영한 것과 같다. 

법선 벡터 n이 단위 벡터(=크기가 1인 벡터)라면 $v\cdot n$이 점과 평면 사이의 거리가 된다.

$v\cdot n$과 평면의 방정식의 관계

점과 평면상의 거리는 점과 평면상의 점 사이의 방향벡터를 법선벡터에 투영시켜 구할 수 있다.

이는 점 P를 평면의 방정식에 대입한 값 / 법선벡터의 크기와 동일하다.

평면의 방정식

$$ax + by + cz + d = 0$$

• a, b, c: 평면의 법선 벡터
• x, y, z: 평면 상의 점 (점과 평면 사이의 거리에서는 점 P로도 구할 수 있음.)
• d: 원점부터 평면까지의 거리 (평면으로부터의 거리가 아님!)

$$ d = -(ax + by + cz) = - dot( normalize(a, b, c), point(x, y, z))$$

 

$v\cdot  n$는 평면의 방정식에 점을 대입한 것과 동일하다.

단, 두 벡터가 단위벡터 일 때

$$v \cdot n = ap_{x} + bp_{y} + cp_{z} + d$$

 

법선벡터를 정규화하면, 점과 평면 상의 위치 관계만 파악 (거리X)

$$ v · n = ap_{x} + bp_{y} + cp_{z} + d = ap_{x} + bp_{y} + cp_{z} - ( ap_{x} + bp_{y} + cp_{z}) = 0 $$

이기 때문에, 법선 벡터를 정규화하지 않고 실제로 법선벡터의 크기를 나눠주어야 실제 거리를 구할 수 있다.

거리 제곱값

 

참고문헌

 

[1] 양영욱, 수학으로 시작하는 3D 게임 개발, e퍼플, 2020, pp.219-228.