직선, 반직선, 또는 선분이 구와 교차하는지 판정하는 방법

직선과 구가 교차하는지 알아 내려면, 직선의 방정식과 구의 방정식을 연립해 풀어서 실근이 있는지 판단하면 됩니다. 그런데, 직선과 구의 교차 판정은 3차원 상의 작업이지만 2차원 상의 방법과 동일하므로, 직선의 방정식과 원의 방정식을 이용하면 됩니다. 한 가지 주의할 점은 직선은 선분과 달리 길이가 무한하다는 것입니다. 그러므로 게임 프로그래밍에 적용할 때 상황에 맞는지 잘 판단해야 합니다.

다음은 직선과 원의 교차 판정 과정입니다.

먼저, 아래처럼 직선의 방정식을 구합니다. 여기에서 p는 직선 상의 점, p0는 직선의 원점, t는 매개변수, 그리고 d는 직선의 방향입니다.

p = p0 + t * d

다음엔 아래처럼 원의 방정식을 구합니다. 원은 원의 중심으로부터 원 위의 점까지의 거리가 원의 반지름과 일치하는 것이므로, 그 정의에 맞춰 방정식을 구하면 됩니다. 여기에서 p는 원 위의 점, q는 원의 중심, 그리고 r은 원의 반지름입니다.

|p – q| = r

위 식에서 절대값을 없애기 위해 양 변을 제곱하면 다음과 같습니다.

(p – q) * (p – q) = r * r

원과 직선이 만나는 점을 구해야 하므로, 원의 방정식에 직선의 방정식을 대입합니다.

(p0 + t * d – q) * (p0 + t * d – q) = r * r

간단히 나타내기 위해서, p0 – q를 s로 치환하겠습니다.

(s + t * d) * (s + t * d) = r * r

위의 식을 풀면 아래처럼 됩니다.

s * s + 2 * s * t * d + t * t * d * d = r * r

위의 식을 t의 이차 방정식 형태로 정리합니다.

d * d * t * t + 2 * s * d * t + s * s – r * r = 0

위 이차 방정식이 실근을 가져야 직선과 원이 교차하는 것입니다.

이차 방정식이 실근을 갖는지 판단하려면, 판별식을 구해서 0보다 작지 않은지 보면 됩니다. a * x * x + b * x + c = 0 꼴인 이차 방정식의 판별식 D는 b * b – 4 * a * c입니다. 그리고 판별식이 0보다 작지 않으면, 직선과 원이 교차하는 것입니다. 그런데 아까 구했던 이차 방정식을 위의 이차 방정식과 비교하면,

a = d * d
b = 2 * s * d
c = s * s – r * r

임을 알 수 있습니다. 이차 방정식의 판별식에 위의 값을 대입해서 풀면, 직선과 원의 교차 판정을 할 수 있습니다.

그런데, b가 지금은 짝수 형태이므로, b’ = b / 2로 놓고 판별식 D / 4 = b’ * b’ – a * c를 이용하면 판정이 더 간단합니다. 즉, D / 4 = b’ * b’ – a * c = (s * d) * (s * d) – (d * d) * (s * s – r * r) >= 0일 때 직선과 원이 교차합니다.

아래는 위의 내용을 C++로 구현한 소스 코드입니다.

bool does_line_intersect_sphere(const vector3_type& line_start,
	const vector3_type& line_direction,
	const vector3_type& sphere_center, float sphere_radius)
{
	vector3_type from_sphere_center_to_line_start = line_start - sphere_center;

	float a = dot_product(line_direction, line_direction);
	float b_prime = dot_product(from_sphere_center_to_line_start, line_direction);
	float c = dot_product(from_sphere_center_to_line_start, from_sphere_center_to_line_start) -
		sphere_radius * sphere_radius;

	return b_prime * b_prime - a * c >= 0.0f;
}

반직선은 직선과 같은 방법으로 처리하면 되는데, 한 가지 조건이 추가됩니다. 즉 반직선의 시작점이 구의 밖에 있고, 구의 중심에서 반직선의 시작점을 향하는 벡터와 반직선의 방향 벡터가 이루는 각이 90도 미만이라면, 반직선과 구는 교차하지 않는다는 것입니다. 아래는 반직선과 구의 교차를 판정하는 C++ 소스 코드입니다.

bool does_ray_intersect_sphere(const vector3_type& ray_origin,
	const vector3_type& normalized_ray_direction,
	const vector3_type& sphere_center, float sphere_radius)
{
	vector3_type from_sphere_center_to_ray_origin = ray_origin - sphere_center;

	float c = dot_product(from_sphere_center_to_ray_origin, from_sphere_center_to_ray_origin) -
		sphere_radius * sphere_radius;

	// 반직선의 시작점부터 구의 중심까지의 거리가 구의 반지름보다 크지 않다면,
	// 반직선의 시작점은 구의 안에 있으므로 교차합니다.
	if (c <= 0.0f)
		return true;

	float b_prime = dot_product(from_sphere_center_to_ray_origin, normalized_ray_direction);

	// 반직선의 시작점이 구의 밖에 있고, 구의 중심에서 반직선의 시작점을 향하는 벡터와
	// 반직선의 방향 벡터가 이루는 각이 90도 미만이라면, 반직선과 구는 교차하지 않습니다.
	if (b_prime > 0.0f)
		return false;

	// 원래는 b' * b' - a * c를 사용해야 합니다. 그런데 반직선의 방향 벡터가 단위 벡터면,
	// a는 dot_product(normalized_ray_direction, normalized_ray_direction) = 1이므로
	// a를 생략 가능합니다.
	return b_prime * b_prime - c >= 0.0f;
}

선분은 반직선과 마찬가지인데, 선분의 시작점부터 교차점까지의 거리가 선분의 길이보다 짧은지도 검사해야 합니다. 아래는 선분과 구의 교차를 판정하는 C++ 소스 코드입니다.

bool does_line_segment_intersect_sphere(const vector3_type& line_segment_start,
	const vector3_type& line_segment_end,
	const vector3_type& sphere_center, float sphere_radius)
{
	vector3_type from_sphere_center_to_line_segment_start = line_segment_start - sphere_center;

	float c = dot_product(from_sphere_center_to_line_segment_start,
		from_sphere_center_to_line_segment_start) - sphere_radius * sphere_radius;

	// 선분의 시작점부터 구의 중심까지의 거리가 구의 반지름보다 크지 않다면,
	// 선분의 시작점이 구의 안에 있으므로 교차합니다.
	if (c <= 0.0f)
		return true;

	vector3_type line_segment_direction = line_segment_end - line_segment_start;
	float line_segment_length = line_segment_direction.length;
	if (line_segment_length == 0.0f)
		return false;
	vector3_type normalized_line_segment_direction = line_segment_direction /
		line_segment_length;
	float b_prime = dot_product(from_sphere_center_to_line_segment_start,
		normalized_line_segment_direction);

	// 선분의 시작점이 구의 밖에 있고, 구의 중심에서 선분의 시작점을 향하는 벡터와 선분의 방향
	// 벡터가 이루는 각이 90도 미만이라면 교차하지 않습니다.
	if (b_prime > 0.0f)
		return false;

	// 원래는 b' * b' - a * c를 사용해야 합니다. 그런데 선분의 방향 벡터가 단위 벡터면,
	// a는 dot_product(normalized_line_segment_direction, normalized_line_segment_direction) =
	// 1이므로, a를 생략 가능합니다.
	float square_root_of_discriminant = sqrt(b_prime * b_prime - c);

	float t1 = -b_prime + square_root_of_discriminant;
	if (t1 >= 0.0f && t1 <= line_segment_length)
		return true;
        
	float t2 = -b_prime - square_root_of_discriminant;
	if (t2 >= 0.0f && t2 <= line_segment_length)
		return true;
}

참고:

Advertisements

답글 남기기

아래 항목을 채우거나 오른쪽 아이콘 중 하나를 클릭하여 로그 인 하세요:

WordPress.com 로고

WordPress.com의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Twitter 사진

Twitter의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Facebook 사진

Facebook의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

Google+ photo

Google+의 계정을 사용하여 댓글을 남깁니다. 로그아웃 / 변경 )

%s에 연결하는 중