절두체 컬링 (1) 평면의 방정식

- 개요

게임 콘텐츠가 원할하게 동작하기 위해서는 사용자의 입력에 따라 월드 공간의 물체들을 빠르게 그려야 한다

따라서 실제 구현 과정에서 계산량을 조금이라도 줄일 수 있는 방법을 강구해야 한다

이전에 알아본 백페이스 컬링이 이런 방법에 해당한다

이번에는 카메라 시야 영역에 위치한 물체만 빠르게 파악해 그리는 절두체 컬링 기법에 대해 알아본다

 

- 절두체 컬링

절두체를 구성하는 6개의 평면

 

절두체 컬링은 절두체의 영역 밖에 위치한 게임 오브젝트를 필터링하는 기능을 의미한다

절두체 컬링은 절두체를 구성하는 6개의 평면에 대해 각각 평면의 방정식을 세우고,

평면의 방정식을 활용하여 대상 게임 오브젝트의 위치가 평면의 바깥에 있는지 확인하는 절차로 진행한다

대상 게임 오브젝트가 6개의 평면 중에서 하나라도 외부에 위치한다면 그리기에서 제외한다

 

1) 평면의 정의

평면을 이루는 최소 구성 요소

 

세 개의 점이 주어지면 세 점으로부터 두 벡터를 생성하여 평면 상의 모든 점을 생성할 수 있다

따라서 하나의 평면을 정의하려면, 최소 3개의 점이 필요하다

이때 3차원 공간의 평면은 앞면과 뒷면이 존재하므로 이를 구분할 수 있는 정보도 필요하다

그러므로 평면을 정의할 때는 (a)와 같이 세 점의 정보를 사용하는 방식보다는

(b)와 같이 평면이 바라보는 방향을 알려주는 법선 벡터와 평면 상에 위치한 한 점을 제공하는 방식을 사용한다

그리고 (b)에서의 법선 벡터는 크기를 1로 정규화시키는 것이 일반적이다

 

2) 평면의 방정식 계산

 

(b)에서의 법선 벡터 n과 평면 위의 점 P₀로 평면을 정의하여 평면의 방정식을 도출한다

만약, 법선 벡터 n의 값이 (a, b, c)라고 한다면 크기가 1이므로 a² + b² + c² = 1의 조건이 성립한다

또, 평면에 위치한 점 P₀의 값이 (x₀, y₀, z₀)라고 가정한다

이런 상황에서 임의의 점 P(x, y, z)가 같은 평면 위에 있을 조건을 계산한다

평면의 방향을 나타내는 법선 벡터와 평면 위의 두 점을 지나는 벡터는 서로 직교하므로 두 벡터의 내적은 0이 된다

따라서 법선 벡터 n과 점 P₀에서 점 P로 향하는 벡터를 내적하면 위의 수식이 성립한다

 

평면의 방정식

 

위의 식에서 법선 벡터와 평면의 점의 값은 사전에 주어진 값이므로

-(ax₀ + by₀ + cz₀)은 미리 계산할 수 있는 상수 값이고 이를 d로 치환한다

이 경우에 위의 식을 간략하게 표시할 수 있는데, 이를 평면의 방정식이라고 표현한다

 

3) 상수 d의 활용

상수 d의 변환 (1)

 

상수 d는 법선 벡터 (a, b, c)와 벡터(x₀, y₀, z₀)와의 내적에 음의 부호를 설정한 결과로 볼 수 있다

 

상수 d의 변환 (2)

 

(x₀, y₀, z₀)는 점 P₀의 좌표지만, 이는 원점 O에서 점 P₀로 향하는 벡터의 값으로도 사용할 수 있다

이를 p로 표시하고 상수 d에 대한 기존의 식을 위와 같이 표현할 수 있다

 

상수 d와 관련된 두 벡터 n과 p의 시각화

 

상수 d에 관련된 두 벡터 n과 p를 시각화하면 위와 같이 표현할 수 있다

 

법선 벡터 n과 (원점-점P₀) 방향의 벡터 p와의 내적의 표현

 

법선 벡터 n과 벡터 p의 관계는 벡터 내적의 cos 공식을 사용하여 위와 같이 표현할 수 있다

법선 벡터의 크기는 항상 1이므로 최종적으로 위와 같이 계산된다

 

4) 상수 d의 2가지 성질

상수 d와 관련된 두 벡터간의 내적의 의미

 

(n ⋅ p)의 값은 p 벡터를 법선 벡터 n에 투영한 벡터의 크기를 의미한다

평면과 법선 벡터는 서로 직교하므로 (n ⋅ p)의 값은 원점 - 평면까지의 최단 거리를 의미한다

이때 상수 d의 값은 -(n ⋅ p)이므로 원점 - 평면까지의 최단 거리 + 음의 부호를 설정한다는 특징을 지닌다

단, 거리의 측정값은 음수가 나올 수 없으므로 d의 값은 원점으로부터의 최단 거리 + 방향의 정보를 지니고 있다

내적의 성질에서 두 벡터가 같은 방향을 바라보면 +값이 나오고, 반대 방향이면 -값이 계산된다

따라서 d의 값이 음수라면 두 벡터 n과 p는 같은 방향을 바라본다는 의미를 지닌다

 

평면이 반대 방향을 향하는 경우

 

이번에는 반대로 평면이 원점을 향하는 반대의 경우를 가정해본다

이 경우에 두 벡터는 서로 마주보므로 내적의 값은 음수가 되고, d의 값은 반대 부호인 양수가 계산된다

따라서 평면의 방정식 d의 값에 따라서 평면이 가지는 2가지 성질을 파악할 수 있다

• d의 부호
  • d의 값이 양수(+)라면 평면의 방향은 원점을 향하는 방향 = 원점은 평면의 앞쪽에 위치함
  • d의 값이 음수(-)라면 평면의 방향은 원점에서 멀어지는 방향 = 원점은 평면의 뒤쪽에 위치함
  • d의 값이 0이라면 = 원점은 평면 위에 포함됨
• d의 절대값 = 평면에서 원점까지의 최단 거리를 의미함

 

5) 프로젝트에서의 평면의 구현

평면 역할의 Plane 구조체

 

프로젝트에서는 Plane 구조체를 사용하여 평면을 처리한다

Normal 멤버변수를 사용하여 법선 벡터를 저장하고 그 크기는 항상 1이 된다

또, 그 값은 평면의 방정식의 a, b, c 계수에 대응된다

D 멤버변수를 사용하여 평면의 방정식의 상수 d의 값을 저장한다

 

6) 평면의 방정식의 상수 d의 응용 - 임의의 점의 위치 판별

평면의 방정식을 구성하는 상수 d 값의 성질을 응용하면

주어진 임의의 점이 평면의 뒤쪽에 있는지 앞쪽에 있는지도 판별할 수 있다

 

점의 내부 - 외부 판별

 

위와 같은 상황에서 임의의 점 P가 있다고 가정한다

원점에서 점 P로 향하는 벡터 OP를 법선 벡터에 내적한 값을 p로 표기한다

여기서 p의 부호를 통해 법선 벡터에 투영한 벡터 OP`의 방향 정보를 파악할 수 있다

p가 양수면 벡터 OP`는 법선 벡터와 같은 방향을 향하고, 음수면 법선 벡터와 반대 방향을 향한다

위의 상황에서 p는 양수를 의미한다

다음으로 p와 평면의 방정식의 상수 d를 서로 더한 값을 살펴본다

위의 그림에서 원점이 평면의 뒤쪽에 있으므로 d의 값은 음수다

음수 d에 양수인 p를 더한 값이 여전히 음수라면, 점 P는 평면의 뒤쪽에 있다고 판단할 수 있다

반대로 p와 d를 더한 값이 양수라면, 점 P는 평면의 앞쪽에 있다고 판단할 수 있다

 

법선 벡터가 반대 방향인 경우

 

법선 벡터가 반대 방향인 경우에서도 규칙은 동일하게 적용한다

위 상황에서 d 값은 양수가 되고, p는 음수일 것이다

d와 p를 더한 결과값이 여전히 양수라면 점 P는 평면의 앞쪽에 위치할 것이다

 

7) 평면의 방정식의 구성요소의 활용 + 프로젝트에서의 설계

임의의 점 P가 평면의 앞에 있는지 / 뒤에 있는지 판단하는 식

 

최종적으로 법선 벡터 (a, b, c)와 d를 사용하여

평면에 주어진 임의의 점 P가 평면의 앞 / 뒤에 있는지 판단하는 수식은 위와 같다

 

평면에서 임의의 점 P까지의 최단 거리를 계산하는 식

 

(a, b, c) ⋅ (x₁, y₁, z₁) + d의 값에 절댓값을 취하면 이는 평면에서 임의의 점 P까지의 최단 거리를 의미한다

 

 

프로젝트에서는 위와 같이 구현하였더

Distance 멤버 함수를 호출하여 인자로 받은 점과 평면까지의 거리를 계산하여 반환한다

IsOutside 멤버 함수를 호출하여 인자로 받은 점이 평면의 앞 / 뒤에 있는지 판단한다

평면의 앞에 있다면 True를 반환하고, 평면의 뒤에 있다면 False를 반환한다