구 & 광선 교차 판정 하기

 

 

영어로 자료를 찾을 수 있도록 영어로 표기하였을 때 어떤 단어인지도 적어둔다.

구 : Sphere

광선 : ray

교차 : intersect / 또는 ray tracing 키워드로도 관련 내용이 있는 것 같다.

다각형 : polygon / triangle(삼각형)

 

먼저 교차 판정을 하기 전에 구는 무엇이고, 다각형이 무엇인지 정의를 해야 한다. 수학적인 정의를 말이다.

 

구

3차원 상에서 원점을 기준으로(원점이 아닌 경우는 transformation을 하면 된다.) 거리가 r만큼 떨어진 모든 점의 집합으로 정의할 수 있다.

그러므로 피타고라스 정리에 의해

 

$\sqrt{x^2 + y^2 + z^2} = r$

이 된다.

이를 벡터로 표현한다면 구의 원점을 나타내는 위치 벡터 origin과 구 평면상의 임의의 점 P, 그리고 반지름 R사이에는 다음이 성립한다.

$|P - origin| = R$

정리해서 $|P - origin| - R = 0$ 이다.

 

하지만 프로그래밍을 가지고 표현하려면 이 모든 점을 구조체에 저장할 순 없기 때문에 해당 연산을 수행하기 위한 최소조건만을 저장하고, 이 정보를 가지고 동적으로 x,y,z 좌표 값을 얻을 수 있도록 하는 식으로 되어 있다.

구를 표현하기 위한 최소 조건은 원점 좌표와 반지름이다. 따라서 구를 다음과 같이 표현할 수 있다.

struct Sphere
{
	Vector3 origin;
	float radius;
};

다음은 광선이다. 광선은 쉽게 말하자면 일차함수이다.

<일차 함수>

$ax + by = c$

$y = $ $\frac{-a}{b}$$x +$$\frac{c}{b}$

 

위와 같이 일차함수는 2차원 상에서 간단히 표현할 수 있지만 3차원이라면 당장 기울기부터 다시 정의해야 한다. 기울기는 결국 어디를 향하는 가라는 말로 치환할 수 있다. 기울기가 1이면 x축 양의 방향으로 45도 만큼의 방향으로 나아가고 있다. 이런식으로 해석할 수 있다. 그리고 방향은 벡터로 충분히 표현할 수 있다.

위치 벡터 origin에 대한 기울기(방향) 벡터 direction를 통해 식을 표현하자면

 

임의의 점(위치 벡터) $P = direction * t + origin$ 이 된다. 음, 그러니까 임의의 스칼라 값 t에 대한 벡터 P를 원래 이차원의 일차함수의 x, y 라고 생각하면 된다.

(사족으로, t가 시간이라고 한다면 나는 무려 시간과 3차원 공간을 사용하는 함수를 정의한 것이다... 갑자기 코즈믹 호러가 올거같다.. 테켈레 히ㅣ~)

그러면 Ray도 구조체로 표현하자면 다음과 같을 것이다.

struct Ray
{
	Vector3 origin;
	Vector3 direction;
	float min, max; // 임의의 변수 t가 가질 수 있는 범위 값
};

그러면 이제 구와 이 직선이 교차 하는지 알아봐야 하는데, 구의 중심과 해당 직선의 거리가 구의 반지름보다 같거나 작으면 교차한다고 판정할 수 있다.

 

간단하게 말해, 방정식을 하나 작성한다고 보면 된다. 구 평면 상의 점이 Ray 함수의 임의의 점과 같다고 해서 그 식의 실수 해가 있는지 판정하면 된다.

 

그러면 다음과 같은 식을 쓸 수 있다.

 

$|direction_{Ray}*t+origin_{Ray}-origin_{Sphere}|=radius_{Sphere}$

 

$direction_{Ray}^2*t^2 +2*(origin_{Ray}-origin_{Sphere})*t+(origin_{Ray}-origin_{Sphere})^2=radius_{Sphere}$

 

$direction_{Ray}^2*t^2 +2t*direction_{Ray}*(origin_{Ray}-origin_{Sphere})+(origin_{Ray}-origin_{Sphere})^2 - radius_{Sphere}= 0$

 

이때 너무 당연하게 제곱이라 써버렸는데, 지금 다루고 있는 것이 단순한 스칼라가 아니라 벡터이므로 곱셈을 어떤 연산으로 해주어야 하는지도 제대로 써주어야 한다. 이는 모두 dot 연산으로 이루어져 있다.

$(direction_{Ray}\cdot direction_{Ray})*t^2 +2t*(direction_{Ray}\cdot (origin_{Ray}-origin_{Sphere})+(origin_{Ray}-origin_{Sphere}) \cdot (origin_{Ray}-origin_{Sphere}) - radius_{Sphere}= 0$

 

근데 $direction_{Ray}$는 정규화된 벡터 이므로 값이 1이 된다. 그러면 식은 더 간단해진다.

 

$t^2 +2t*(direction_{Ray}\cdot (origin_{Ray}-origin_{Sphere}))+(origin_{Ray}-origin_{Sphere}) \cdot (origin_{Ray}-origin_{Sphere}) - radius_{Sphere}= 0$

 

그렇다면 t에 대한 이차방정식이 되었으니 근의 공식을 사용하여 교차점을 구해낼 수 있을 것이다. 물론 그전에 판별식 D를 사용하여 구와 광선이 교차하는지를 먼저 체크해야 한다.

 

1차항의 계수가 짝수이므로 짝수 공식을 이용하여 판별식을 표현해보자.

 

$b^2-ac$ 에서

$a = 1$

$b = direction_{Ray}\cdot (origin_{Ray}-origin_{Sphere})$

$c = (origin_{Ray}-origin_{Sphere}) \cdot (origin_{Ray}-origin_{Sphere}) - radius_{Sphere}$

이므로 

$b^2-ac < 0$ 이면 서로 교차하지 않음,

$b^2-ac = 0$ 이면 한 점에서 교차함.

$b^2-ac > 0$ 이면 두 점에서 교차함.

 

이라고 판정할 수 있다. 그러면 이제 이를 프로그래밍으로 표현해보자. 구조체 Ray, Sphere에 대한 Intersect 함수는 다음과 같다.

bool Intersect(Ray& ray, Sphere& sphere)
{
	Vector3 subtract = ray.origin - sphere.origin;
	float b = Vector3::Dot(ray.direction, subtract);
	float c = Vector3::Dot(subtract, subtract) - sphere.radius;
	return b * b - c >= 0;
}