[게임수학] 절두체(Frustum)

절두체 컬링

• 절두체(Frustum)는 평면으로 표현되는 부분을 뜻한다.
  • 즉, 시야에 보이는 영역을 표현한 입체를 뜻한다.
• 절두체 컬링(Frustum Culling)을 이용하여 절두체 영역 밖에 있는 게임 오브젝트를 파악하고 걸러내는 기능을 구현할 수 있다.
  • 카메라 영역 밖에 있는 오브젝트는 드로우콜을 생략할 수 있다.

평면의 방정식

• 세 점이 주어지면 세 점으로부터 두 벡터를 생성해 평면 상의 모든 점을 생성할 수 있다.
  • 따라서 하나의 평면을 정의하려면 최소 3개의 점이 필요하다.
  • 3차원 공간의 평면은 앞면과 뒷면이 존재하기 때문에, 이를 구분할 수 이는 정보도 있어야 한다.

• 평면을 정의할 때는 위 그림의 (a)와 같이 세 점의 정보를 사용하기 보다 (b)와 같이 평면이 바라보는 방향을 알려주는 법선 벡터와 평면 상에 위치한 한 점을 제공하는 방법을 사용한다.
  • 이때 법선 벡터의 크기를 1로 정규화시키는 것이 일반적
• 평면위의 한 점과 노멀벡터를 이용하여 평면의 방정식을 유도할 수 있다.
• 아래의 조건을 통해 평면의 방정식을 유도
  • 법선 벡터 n = (a, b, c)
  • 평면위의 한점 P0 = (x0, y0, z0)
  • 평면위의 임의의 점 P = (x, y, z)
• 법선 벡터의 크기를 1로 정규화하면, 아래 수식이 성립

||n|| = sqrt(n ⋅ n) = sqrt(a^2 + b^2 + c^2) = 1
∴ a^2 + b^2 + c^2 = 1

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

n⋅(P - P_0) = (a, b, c) ⋅ (P - P_0) = 0
a(x - x_0) + b(y - y_0) + c(z - z_0) = 0
ax + by + cz - (ax_0 + by_0 + cz_0) = 0

• 위 식에서 법선 벡터 (a, b, c)와 평면의 점 (x_0, y_0, z_0)는 사전에 주어진 값이므로 - (ax_0 + by_0 + cz_0)는 미리 계산할 수 있는 상수 값이다. 이를 간단히 d로 치환하면 아래 수식으로 표현할 수 있다.
  • 이 식을 평면의 방정식이라고 한다.

ax + by + cz + d = 0

상수 d의 의미

• 상수 d는 법선 벡터와 벡터 (x_0, y_0, z_0)와의 내적에 음의 부호를 설정한 결과로 볼 수 있다.

d = -n ⋅ (x_0, y_0, z_0)

• (x_0, y_0, z_0)는 점 P_0의 좌표이지만, 이는 원점 O에서 점 P_0로 향하는 벡터의 값으로도 사용할 수 있다. 이를 벡터 p로 표시하면 다음과 같이 정리할 수 있다.

d = -(n ⋅ OP_0) = -(n ⋅ p)

• 수식을 시각화하면 위 그림과 같다.
• n ⋅ p는 벡터 내적의 cos 공식을 활용하면 다음과 같이 정리된다.

n ⋅ p = |n||p|⋅cosΘ 

법선 벡터의 크기는 항상 1이므로 다음과 같이 간단히 정리된다.
n ⋅ p = |p|⋅cosΘ

• 평면과 법선 벡터는 서로직교하기 때문에 방금 구한 n ⋅ p의 값은 원점에서 평면까지의 최단 거리를 의미한다.
  • d의 값은 n ⋅ p가 아닌 -n ⋅ p이므로 원점으로부터 평면의 최단 거리에 음의 부호를 설정한다는 특징을 가진다.
  • 거리라는 측정값은 음수가 나올 수 없기 때문에 d의 값은 원점으로부터의 최단 거리와 방향이라는 두 가지 정보를 담고 있다.

• 위 그림과 같이 평면이 원점을 향하는 반대의 경우
  • 평면이 원점을 향하면 두 벡터는 서로 마주보는 상황이므로 내적의 값은 음수가 되고, d의 값은 반대 부호인 양수가 나올 것이다.
• 평면의 방정식의 d값에 따라 평면이 가지는 두 가지 성질을 파악알 수 있다.
  1. d의 부호 : d의 값이 양수이면 평면이 바라보는 방향은 원점을 향하고, 음수면 원점에서 멀어지는 방향을 가진다. 즉, d의 값이 양수이면 원점은 바깥쪽에 위치하고, 음수면 원점은 평면의 안쪽에 위치한 것
  2. d의 절대값 : 평면에서 원점까지의 최단 거리를 의미

• d 값의 성질을 응용하면 주어진 점이 평면의 안쪽에 있는지 바깥쪽에 있는지 판별할 수 있다.
  • 임의의 점 P가 있을 때, 원점에서 점 P로 향하는 벡터 OP를 법선 벡터에 내적한 값을 p로 표기
  • p의 부호를 통해 법선 벡터에 투영한 벡터 OP'의 방향 정보를 파악할 수 있음
  • p가 양수이면 벡터 OP'은 법선 벡터와 같은 방향을 향하고, 음수이면 반대 방향을 향한다.
• p와 평면의 방정식의 상수 d를 서로 더한 값
  • 원점이 평면 안쪽에 있으면 d값은 음수다.
  • 음수 d에 양수인 p를 더한 값이 여전히 음수이면, 점 P는 평면의 안쪽에 있다고 판단할 수 있음
  • 반대로 p와 d를 더한 값이 양수이면 점 P는 평면의 바깥쪽에 있다고 판단할 수 있음
  • 법선 벡터가 반대인 경우에도 이 규칙은 동일함
• 평면에 주어진 점 P(x_1, y_1, z_1)가 평면에 바깥쪽에 있는지 판단하는 수식

(a, b, c) ⋅ (x_1, y_1, z_1) + d > 0

이때 (a, b, c) ⋅ (x_1, y_1, z_1) + d의 값에 절대 값을 취하면
평면에서 해당 점까지의 최단 거리를 의미
distance = |(a, b, c) ⋅ (x_1, y_1, z_1) + d|

평면의 방정식의 정규화

• 만약 n의 크기가 1이 아닌 경우가 있을 수 있다.
• 이 문제를 해결하기 위해 법선 벡터를 한번더 정규화 시키면 된다.

점과 직선 사이의 거리 공식 이용
PH = |ax1 + by1 + cz1 + d| / sqrt(a^2 + b^2 + c^2)

n은 정규화되지 않았기 때문에 a^2 + b^2 + c^2 = 1은 성립하지 않음
동차를 이용해 w개념을 도입
x = x1 + aw
y = y1 + bw
z = z1 + cw

PH^2 = (a^2 + b^2 + c^2)w^2
∴ w = (ax1 + by1 + cz1 + d) / (a^2 + b^2 + c^2)

• 동차를 이용해 d=wn을 만족하는 w를 구할 수 있다.
• 따라서 d에 대해 아래와 같이 표현할 수 있다.
  • n은 정규화 되지 않았으니 꼭 정규화를 기억해주며 수식을 유도

d = w⋅||n||
d = (ax1 + by1 + cz1 + d) / (a^2 + b^2 + c^2)⋅sqrt(a^2 + b^2 + c^2)
d = (ax1 + by1 + cz1 + d) / sqrt(a^2 + b^2 + c^2)

절두체의 6개 평면

• 절두체는 총 6개의 단면을 가지고 있다.
• 전체적인 수식은 아래와 같다.

ax + by + cz + d = 0

근평면과 원평면

• 근평면과 원평면은 카메라가 바라보는 벡터로부터 직교하는 성질을 가진다.
  • 따라서 노말벡터는 (0, 0, 1)이나 (0, 0, -1)이 된다.
  • 노말벡터가 2개인 이유는 절두체의 안과 밖을 구분하기 위해서다.
  • 근평면은 카메라의 원점을 향하고 있으므로 (0, 0, 1)이 된다.
  • 원평면은 이와 반대로 되어야 하므로 (0, 0, -1)로 볼 수 있다.
• 위에서 알아본 수식 중 d값은 근평면과 원평면의 n, f 값이 곧 카메라의 거리이기 때문에 이 두가지 정보를 통해 d값을 얻을 수 있다.
  • 근평면의 nz는 양수이기 때문에 d값도 양수가 되어 d = n이된다.
  • 원평면의 nz는 반대로 음수기 때문에 d = -f가 된다.
• 평면 방정식에 필요한 정보는 다 구했기 때문에 적용해보면 아래와 같다.

a, b는 둘다 0이므로 생략이 되어 아래와 같이 전개된다.

근평면의 방정식
0·x + 0·y + 1·z + d = 0
z + d = 0
z + n = 0

원평면의 방정식
0·x + 0·y + -1·z + d = 0
-z + d = 0
-z - f = 0

• 방정식의 음수와 양수가 다른 이유
  • 각 평면의 방향이 서로 다르기 때문
  • 등호를 기준으로 넘기면 전혀 다른 식이 되어버리기 때문
  • 즉, z + d = 0과 -z - d = 0은 서로 다른 방향을 가진 방정식임

기울어진 평면

• 근평면과 원평면을 제외한 나머지 4개의 평면들은 모두 기울어져 있다.
  • 카메라의 eye 벡터를 노멀벡터로 선언하고 해당 점을 화각의 절반만큼 이동시켜야한다.
  • 이후 90도만큼 올려줘야 진정한 노멀벡터가 된다.
• 상단 평면을 기준으로 방정식을 전개하면 아래와 같다.

eye벡터를 노멀벡터로 선언하고 기울여준다.
기울이는 방법은 삼각함수를 통해 변환이 필요한 y, z에 적용
(0, 1·sin(Θ/2), -1·cos(Θ/2)) = (0, sin(Θ/2), -cos(Θ/2))

• 기존 화각의 절반만 움직이니 삼각함수에 Θ/2를 적용하고, 90도 만큼 이동해준다.
• x축 기준 90도 회전이므로 회전행렬을 통해 값을 구해준다.
• 방정식을 전개하면 아래와 같다.

┌ 1      0         0    ┐   ┌      0      ┐
| 0  cos(π/2) -sin(π/2) | · |   sin(Θ/2)  |
└ 0  sin(π/2)  cos(π/2) ┘   └  -cos(Θ/2)  ┘

= ┌ 1  0  0 ┐   ┌      0      ┐
  | 0  0 -1 | · |   sin(Θ/2)  |
  └ 0  1  0 ┘   └  -cos(Θ/2)  ┘
  
= (0, cos(Θ/2), sin(Θ/2))

• 상단평면은 카메라의 원점을 포함하기 때문에 d가 0이 된다.
• 따라서 최종적인 상단평면의 방정식은 아래와 같다.

cos(Θ/2)y + sin(Θ/2)z = 0

• 나머지 평면도 전개해보면 아래와 같다.

하단 평면
eye벡터를 노멀벡터로 선언하고 기울여준다.
상단과 다르게 y축이 반대로 적용
(0, -1·sin(Θ/2), -1·cos(Θ/2)) = (0, -sin(Θ/2), -cos(Θ/2))

x축 기준으로 -90도 회전이므로 최종적으로 
┌ 1   0  0 ┐
| 0   0  1 |
└ 0  -1  0 ┘
의 값이 나온다.
(0, -cos(Θ/2), sin(Θ/2))
∴ -cos(Θ/2)y + sin(Θ/2)z = 0

좌 평면
eye벡터를 노멀벡터로 선언하고 기울여준다.
좌측이기 때문에 x, z에 영향을 준다.
(1·sin(Θ/2), 0, -1·cos(Θ/2)) = (sin(Θ/2), 0, -cos(Θ/2))

y축 기준으로 -90도 회전이므로 최종적으로 
┌ 0  0  -1 ┐
| 0  1   0 |
└ 1  0   0 ┘
의 값이 나온다.
(cos(Θ/2), 0, sin(Θ/2))
∴ cos(Θ/2)x + sin(Θ/2)z = 0

우 평면
eye벡터를 노멀벡터로 선언하고 기울여준다.
좌측과 다르게 x축이 반대로 적용
(-1·sin(Θ/2), 0, -1·cos(Θ/2)) = (-sin(Θ/2), 0, -cos(Θ/2))

y축 기준으로 90도 회전이므로 최종적으로 
┌  0  0  1 ┐
|  0  1  0 |
└ -1  0  0 ┘
의 값이 나온다.
(-cos(Θ/2), 0, sin(Θ/2))
∴ -cos(Θ/2)x + sin(Θ/2)z = 0

절두체 컬링의 응용

• 절두체를 활용하여 표현할 오브젝트를 판별하는 순서는 다음과 같다.
  1. 한 평면과 임의의 점을 평면의 방정식을 통해 바깥쪽에 있는지 확인
  2. 만약 바깥쪽에 있다면 다른 면은 확인할 필요없이 절두체 내부에 존재하지 않는다고 결론
  3. 안쪽에 있다는 걸 판별하면 계속해서 다음 평면을 가지고 1번으로 되돌아감
• 로직을 순서도로 정리하면 다음과 같다.

문제점

• 물체의 위치값 만으로 컬링하면 결과가 부정확해진다.
  • 눈에서 보이는 오브젝트가 절두체에 걸치더라도 Transform이 밖에 있다면 컬링되는 문제
  • 점이 아닌 부피로 컬링이 진행되어야함
• 종횡비가 고려되지 않음
  •  NDC공간을 생각하지 않고 뷰공간을 기준으로 절두체 컬링을 진행했기 때문에 종횡비가 항상 1대1로 진행
  • 투영 행렬로 해결할 수 있음

투영 행렬 적용

• 투영 행렬과 평면의 방정식을 서로 연관시킬 수 있을지 평면의 방정식을 유도해보자

유도 과정

• 원근 투영 때 배운 클립 좌표계를 유도한 투영 행렬 식을 이용할 수 있다.

        ┌ d/a  0     0       0    ┐   ┌ v(x) ┐   ┌ x ┐
P ⋅ v = |  0   d     0       0    | ⋅ | v(y) | = | y |
        |  0   0  n+f/n-f 2nf/n-f |   | v(z) |   | z |
        └  0   0    -1       0    ┘   └   1  ┘   └ w ┘

• x, y, z, w는 클립 좌표계를 뜻한다.
• 행벡터를 뷰공간의 v랑 내적을 한다고 표현이 가능하기 때문에 아래와 같이 표현이 가능

┌ P(row1) ⋅ v ┐   ┌ x ┐
| P(row2) ⋅ v | = | y |
| p(row3) ⋅ v |   | z |
└ P(row4) ⋅ v ┘   └ w ┘

• 위 식을 방정식으로 풀어보면 

x = P(row1) ⋅ v
y = P(row2) ⋅ v
z = P(row3) ⋅ v
w = P(row4) ⋅ v

• 이때 종횡비로 인해 3차원 NDC공간의 범위 값을 적용해야한다.
  • -1 <= nx <= 1
  • -1 <= ny <= 1
  • -1 <= nz <= 1
• 위 범위를 클립 좌표계에 적용

동차의 성질에 따라 w를 가정하고 NDC의 범위를 나눠줌
-1 <= x/w <= 1
-1 <= y/w <= 1
-1 <= z/w <= 1

양변에 w를 곱함
-w <= x <= w
-w <= y <= w
-w <= z <= w

클립 좌표계를 위 수식에 대입
-P(row4) ⋅ v <= P(row1) ⋅ v <= P(row4) ⋅ v
-P(row4) ⋅ v <= P(row2) ⋅ v <= P(row4) ⋅ v
-P(row4) ⋅ v <= P(row3) ⋅ v <= P(row4) ⋅ v

간단하게 식을 수정
P(row4) + P(row1) ⋅ v >= 0
P(row4) - P(row1) ⋅ v >= 0
P(row4) + P(row2) ⋅ v >= 0
P(row4) - P(row2) ⋅ v >= 0
P(row4) + P(row3) ⋅ v >= 0
P(row4) - P(row3) ⋅ v >= 0

• 위 수식이 평면의 방정식이 된다.

정규화 하기

• 절두체 컬링을 구현하기 위해선 우리가 알고있는 기존 평면의 방정식으로 적용하여 뷰공간의 점 v와 방향을 나타내는 벡터를 활용할 수 있도록 만들어야한다.
• 여기서 뷰공간의 점v는 (x, y, z, 1)로 표현하고, 방향을 표현하는 벡터는 (a, b, c, d)로 표현
• 이를 평면 방정식에 대입

ax + bx + cz + d >= 0

• 평면의 방정식 정규화를 이용해야함. 이때 몇가지 특징이 있음
  • 판별식이므로 평면의 방정식 자체에 부등호가 적용
  • 평면의 방정식은 방향이 NDC 내부, 즉 절두체 내부로 들어가기 때문에 노멀 벡터값을 평면 밖으로 빼주고 빠진걸 걸러내기 위해서 전체적으로 음수를 달아줘야함
  • 같은 평면 위에 존재하는 오브젝트도 화면에 보이기 때문에 부등호가 > 로 바뀐다.
• 이를 수식으로 표현하면 아래와 같은 수식이 나온다.

-(ax + by + cz + d) / sqrt(a^2 + b^2 + c^2) > 0

바운딩 볼륨

• 절두체 컬링을 진행할 때 게임 오브젝트의 메시가 차지하는 영역이 있음에도 불구하고 오브젝트의 기준 위치만 가지고 진행하면 화면의 가장자리에서 튀는 형상이 발생할 수 있다.

• 위 그림과 같은 상황이 발생하면 기존 절두체 컬링 로직에서는 게임 오브젝트의 위치가 절두체 바깥에 있다고 판단해 그리기를 건너뛸 것이다.
  • 하지만 이 게임 오브젝트는 절두체 영역에 걸쳐있기 때문에 그려줘야 한다.
• 이 문제를 해결하기 위해서는 게임 오브젝트의 위치를 대상으로 하지 않고, 메시가 차지하는 영역을 감안해 절두체 컬링을 진행해야 한다.
• 게임 엔진은 메시가 차지하는 영역을 효과적으로 관리하기 위해 구나 박스같은 원시 도형(Primitive shape)을 사용한다.
  • 원시 도형으로 설정한 공간 데이터를 바운딩 볼륨(Bounding volume)이라고 한다.

구 바운딩 볼륨

• 바운딩 볼륨에서 손쉽게 사용되는 원시 도형은 구다.
• 두 영역이 서로 겹치는지, 떨어져 있는지를 가장 쉽고 빠르게 파악할 수 있다.

• 어떤 점이 구의 외부에 있는지 여부를 파악하는 방법은 위 그림의 (a)와 같이 구의 중점에서 점까지의 거리와 구의 반지름 크기를 비교하는 것이다.

d > r_1

• 또한 두 구의 영역이 서로 떨어져 있는지 여부는 (b)와 같이 두 구의 중점간의 거리와 두 구의 반지름을 더한 값을 비교하는 것만으로 쉽게 파악할 수 있다.

d > (r_1 + r_2)

• 구의 반지름 정보를 사용해 위 그림과 같이 메시 영역이 절두체 영역의 안쪽에 있는지, 겹치는지, 벗어나는지 파악할 수 있다.
  • 구의 중점 좌표와 평면의 방정식의 법선 벡터 (a, b, c)와의 내적 값에 d값을 더한 값이 0보다 크다면 구는 평면의 바깥쪽에 위치한다는 의미다.
  • 이 값이 구의 반지름 r보다 더 크다면 해당 구의 영역은 평면으로부터 완전히 벗어난다.
  • 완전히 벗어나는 경우에는 오브젝트를 그리지 않도록 처리
  • 평면으로부터 거리에 해당하는 식의 값이 구의 반지름 r보다 작거나 같으면 구 영역은 절두체 평면과 겹쳐져 있다고 판단할 수 있다.

박스 바운딩 볼륨

• 구 영역 대신 박스 영역을 사용하면 좀 더 정교한 절두체 컬링 작업을 수행할 수 있다.
• 박스 영역을 구성하는 각 축의 최댓값과 최솟값을 설정하고, 메시를 구성하는 점을 순회하면서 각 차원의 값을 비교한다.
  • 현재 박스 영역에 저장된 최댓값보다 크거나 최솟값보다 작다면 박스 영역의 최댓값과 최솟값을 갱신해준다.
  • 모든 점에 대해 이 과정을 거치면 기저 축에 평행한 박스 영역이 형성된다.
  • 기저 축에 정렬되어 있다는 의미로 해당 바운딩 볼륨을 AABB(Axis alogned bounding box)라고 부른다.

• 위 그림의 (a)와 같이 평면의 법선 벡터의 모든 요소가 양수인 상황에서 AABB영역이 평면의 바깥에 위치해 있다면
  • 평면과 가장 가까운 AABB 영역의 점은 AABB의 최솟값이다.
  • AABB영역의 최솟값과 평면과의 차리를 측정하는 값은 양수가 나올 것이다.
• (b)와 같이 평면의 법선 벡터의 모든 요소가 음수인 상황
  • 평면과 가장 가까운 AABB영역의 점은 최대값이고, 최댓값과 평면과의 차이를 측정하는 값 또한 양수가 나온다.
• AABB 영역과 법선 벡터의 x, y, z축은 서로 직교하고 있으므로 각 축의 데이터는 독립적으로 동작한다.
  • 각 법선 벡터의 요소마다 양수인 경우에는 해당 요소의 최솟값을, 음수인 경우에는 해당 요소의 최댓값을 사용하는 것으로 평면에서 가장 가까운 AABB의 점을 구할 수 있다.
  • x축과 z축의 법선 벡터가 음수이고 y축만 양수라면 평면과 가장 가까운 AABB의 좌표는 (Max, Min, Max)가 된다.
• 평면에서 가장 가까운 AABB의 좌표와 평면과의 차이를 측정했을 때 그 값이 양수가 나온다면, AABB 영역은 완전히 평면의 바깥쪽에 위치해 있다고 판정할 수 있다.

• AABB 영역이 절두체의 평면과 교차하는 경우는 다음과 같다.
  • 평면에서 가장 가까운 AABB의 좌표와 평면과의 차이를 측정한 값이 음수가 나오는 경우, 평면에서 가장 가까운 AABB의 좌표와 정반대에 위치한 점으로 다시 평면과의 테스트를 진행해 평면과의 교차 여부를 확인한다.
  • 정반대에 위치한 점과 절두체 평면과의 차이를 측정한 값이 양수가 나오면 위 그림과 같이 절두체 영역과 AABB영역은 서로 교차한다.

삼각형 클리핑

• 지금까지 구현한 방식으로 평면을 그리면 카메라 뒷편에 있는 점이 거꾸로 뒤집혀 투영되는 결과가 발생할 수 있다.
  • 이 문제의 발생 원인을 알아보기 위해 아래 그림과 같이 거대한 삼각형을 카메라 앞뒤에 배치
  • 아래 그림과 같이 삼각형을 구성하는 세 점중에서 한 점이 카메라 뒤쪽에 위치하는 경우, 이를 투영하면 카메라 뒤쪽에 위치한 점은 무한 원점을 중심으로 뒤집혀 투영된다.

• 평면이 올바르게 보이려면 카메라 뒤쪽에 있는 점을 파악해 점이 거꾸로 뒤집혀 투영되지 않도록 예방해야 한다.
• 원근 투영 행렬을 곱해 생성된 클립 좌표계의 w값은 뷰 공간에서의 깊이 값을 의미한다.
  • 따라서 카메라 정면에 위치한 점의 w값은 0보다 크고, 카메라 뒤에 있는 점의 w값은 0보다 작으며, 카메라 초점에 위치한 점의 w 값은 0이 된다.
• 문제 해결을 위해 음의 w 영역에 걸쳐 있는 삼각형을 파악하고 이들이 엉뚱하게 투영되지 않도록 삼각형 영역을 잘라내야 한다.
  • 이를 삼각형 클리핑(Triangle clipling)이라고 한다.
• 삼각형 클리핑 작업은 월드 공간의 좌표를 사용하지 않고 투영 행렬을 적용한 후의 좌표를 사용한다.
  • 사영 공간에서 삼각형 클리핑 작업을 진행하는 것이 더 간편하기 때문

• 위 그림과 같이 위에서 절두체를 내려다본 경우를 생각
  • 그리려는 삼각형의 두 점의 w값은 양수이고, 나머지 하나는 음수인 상황
  • 이 경우 뒤집혀 투영되는 문제를 해결하기 위해 붉은색으로 표시된 음의 영역을 잘라내는 작업이 필요하다.
  • 음의 영역에 위치한 점 P_1을 w = 0 평면에 투영한 두 점 P_c1과 P_c2의 좌표를 구해야 한다.
• 점 P_1과 점 P_2, P_3를 이은 두 선분이 있을 때 점 P_c1과 P_c2의 좌표는 각 선분 위의 점이다.
  • 이중에서 점 P_c1의 좌표는 어파인 결합의 직선의 방정식을 사용해 다음과 같이 구할 수 있다.

P_c1 = P·(1 - t_1) + P_2·t_1

• 점 P_c1은 w = 0인 직선에 위치하므로 P_c1의 w값은 0이다.
  • 따라서 점 P_1과 P_2의 w값을 각각 w_1, w_2로 표기하면 다음 수식이 성립한다.

w_1(1 - t_1) + w_2t_1 = 0

이 식을 t_1에 대해 전개하면 다음 값을 구할 수 있다.
t_1 = w_1 / (w_1 - w_2)

• t_1의 값을 구한 후 P_c1을 구하는 식에 대입하면 점 P_c1의 최종 좌표를 얻을 수 있다.
  • 다른 점 P_c2도 동일한 방법으로 구할 수 있다.
  • 주의할 점은 삼각형을 잘라낸 후에 w = 0 평면에 투영된 두 점과 투영되지 않은 두 점의 영역은 삼각형이 아닌 사각형을 이룬다는 것이다.
  • 따라서 점을 투영한 후에는 사각형을 아래 그림과 같이 두 개의 삼각형으로 분할해야 한다.
  • 분할할 때에는 면의 방향이 동일하도록 정점의 순서도 자르기 전의 삼각형의 순서와 동일해야 한다.

• 자른 후의 두 삼각형은 다음과 같이 정점 순서를 유지해야 한다.
  • 자르기 전 삼각형의 정점 배치 순서 : P_1 -> P_2 -> P_3
  • 삼각형 1의 순서 : P_c1 -> P_2 -> P_3
  • 삼각형 2의 순서 : P_c1 -> P_3 -> P_c2

• 두 점이 음의 영역에 있는 경우에는 언제나 삼각형이 만들어지므로, 두 점의 위치 값만 갱신하는 것으로 삼각형을 손쉽게 잘라낼 수 있다.
• 삼각형의 세 점이 모두 음의 영역에 있다면 해당 삼각형은 시야에 없음을 의미하므로 그리기를  생략하면 된다.
• 마지막으로, 삼각형의 세 점이 모두 양의 영역에 있다면 삼각형을 그래도 그리면 된다.
• 정리하면 동차 좌표계 상에서 삼각형을 분할하는 작업은 다음 순서로 진행된다.
  1. 잘라낼 영역에 몇 개의 점이 속해 있는지 파악
  2. 잘라낼 영역에 점이 없으면 삼각형을 그래도 그린다.
  3. 잘라낼 영역에 한 점이 속해 있으면 평면과의 교차점을 구하고, 교차점으로부터 삼각형을 두 개로 분할한다.
  4. 잘라낼 영역에 두 점이 속해 있으면 교차점을 구해 갱신한다.
  5. 잘라낼 영역에 세 점이 모두 속해 있으면 그리지 않는다.
• 이러한 글리핑 규칙은 절두체를 구성하는 모든 평면에 적용할 수 있다.

• 두개로 분할해본 삼각형의 결과에 이어서 오른쪽 절두체 영역을 잘라내는 상황을 가정하면, 1번 삼각형에 대해서 위 그림과 같은 상황이 될 것이다.
  • 잘라내는 영역에 삼각형의 한 점이 속해했으므로 해당 삼각형은 다시 두 개로 분할돼야 한다.
• 절두체의 오른쪽 평면은 NDC 좌표의 x값이 언제나 1인 평면인데, 이를 클립 좌표계로 표현하면 x/w = 1이 된다.
  • 이는 w = x를 의미한다.
  • 삼각형을 잘라내는 평면의 식이 w = 0에서 w = x로 바뀌었을 뿐 잘라내는 원리는 동일하다.
  • 앞서 잘라내는 영역을 파악하기 위해 음의 영역, 즉 w < 0의 부등식을 사용했는데, 이번 경우에는 다음 식을 사용한다.

x/w > 1
∴ x > w

• 잘라낸 평면 상에 위치한 점의 좌표를 계산하는 방법도 변경된다.
  • 점 P_1과 P_2의 x 값을 각각 x_1, x_2로 지정하고 잘라내는 점의 x값을 x_c1이라고 할때 x_c1을 구하는 수식은 다음과 같다.

x_c1 = x_1(1 - t_1) + x_2t_1

• 이는 w 값에 대해서도 동일하게 성립한다.

w_c1 = w_1(1 - t_1) + w_2t_1

• 오른쪽 절두체 평면에서는 x값과 w값이 동일하므로 x_c1과 w_c1을 구하는 식의 값은 동일하다.

x_1(1 - t_1) + x_2t_1 = w_1(1 - t_1) + w_2t_1

• 위 식으로부터 t_1값을 구하는 수식은 다음과 같이 정리된다.
  • 이 식을 이용해 w = x평면에 위치한 점 P_c1과 P_c2의 좌표를 구할 수 있다.

t_1 = (w_1 - x_1) / ((w_1 - x_1) - (w_2 - x_2))

• 절두체를 구성하는 각 평면마다 삼각형 자르기를 진행하면 아무리 큰 삼각형이라도 절두체 영역에 들어맞는 다각형이 만들어진다.
  • 위 그림에 절두체의 각 평면에 대한 방정식을 정리했다.
  • 절두체 영역의 위, 아래를 담당하는 y축 평면은 그림에서 생략했는데, 이들의 방정식은 w = y와 w = -y이다.
• 절두체를 구성하는 각 평면의 방정식과 외부 영역에 대한 판별식, 그리고 어파인 결합의 계수를 구하는 수식은 아래 표와 같다.

순서	평면	외부 판별식	어파인 결합의 계수
1	w = 0	w < 0
2	w = y	y > w
3	w = -y	y < -w
4	w = x	x > w
5	w = -x	x < -w
6	w = z	z > w
7	w = -z	z < -w

 

 

 

 

 

출처

https://m.yes24.com/Goods/Detail/107025224

이득우의 게임 수학 - 예스24

https://velog.io/@ounols/%EA%B2%8C%EC%9E%84-%EC%88%98%ED%95%99-%EC%A0%88%EB%91%90%EC%B2%B4-%EC%BB%AC%EB%A7%81

[게임 수학] 절두체 컬링의 원리

https://velog.io/@ounols/%EA%B2%8C%EC%9E%84-%EC%88%98%ED%95%99-%ED%8F%89%EB%A9%B4%EC%9D%98-%EB%B0%A9%EC%A0%95%EC%8B%9D

[게임 수학] 평면의 방정식