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

ounols·2021년 12월 28일
0

게임 수학

목록 보기
9/9
post-thumbnail

🧐 해당 파트는 게임 개발 환경을 구성하는 컴퓨터 그래픽스(Computer Graphics)를 이해하기 위한 기초 수학의 간단한 개념에 대해 설명하고 있습니다!

혹여나 이해가 잘 안되거나 잘못된 정보를 발견하시게 되었다면 관련해서 피드백 해주시면 정말 감사하겠습니다!

절두체위에서 바라본 절두체 컬링

사실 절두체는 이전 편에서 한번 간단하게 개념정도만 다뤘습니다. 개념을 다시 복습해보자면 저희는 위에서 왼쪽 그림에서 평면으로 표현되는 부분을 절두체(Frustum)라고 부른다고 배웠습니다.

절두체는 그래픽스에서 많은 도움을 줍니다. 대표적인 예시로는 위 그림처럼 절두체 컬링이라고 불리는 카메라 영역 밖에 있는 오브젝트는 드로우콜을 생략하는 정말 중요한 기법의 연산에 꼭 필요한 데이터를 가지고 있습니다.

이번에는 절두체 컬링을 구현하는 것에 대해 중점적으로 다루고자 합니다.

1. 평면의 방정식

드디어 평면의 방정식을 그래픽스에 응용하는 단계까지 오게 되었습니다!
이번엔 평면의 방정식을 통해 어떻게 절두체에 적용하는지 알아보도록 하겠습니다.

1-1. 절두체의 6개 평면

절두체는 총 6개의 단면을 가지고 있습니다. 여기서 단면의 상태에 따라 처음 연산하는 방식은 조금씩 다를 수 있지만 전체적인 수식은 이전 시간에 배웠던 내용 그대로입니다.

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

먼저 근평면과 원평면부터 알아보겠습니다.

근평면과 원평면

근평면과 원평면은 카메라가 바라보는 벡터로부터 직교하는 성질이 있습니다.
따라서 노멀벡터는 (0,0,1) or (0,0,1)(0, 0, 1) \ \text{or} \ (0, 0, -1) 이 됩니다.

왜 근평면과 원평면의 노멀벡터가 2개로 나뉘나요?

근평면과 원평면은 카메라가 바라보는 벡터로부터 직교하는 공통점을 가지고 있지만
절두체의 앞과 뒷부분을 담당하기 때문에 절두체 평면의 안과 밖을 구별하기 위해선 서로 다른 노멀벡터를 가지고 있어야 합니다.

따라서 근평면은 카메라의 원점을 향하고 있으니 (0,0,1)(0, 0, 1)로 볼 수 있고,
원평면은 그와 반대방향을 바라봐야 하기 때문에 (0,0,1)(0, 0, -1) 으로 볼 수 있습니다.

그리고 dd값은 근평면과 원평면의 각각 n,fn, f값이 곧 카메라와의 거리이기 때문에 이 두가지 정보를 통해 dd값을 얻을 수 있습니다.

여기서 근평면의 nz\vec n_z는 양수이기 때문에 dd값도 양수로 되어 d=nd = n이 됩니다.
그러나 원평면의 nz\vec n_z는 반대로 음수이기 때문에 dd값은 d=fd = -f가 됩니다.

평면의 방정식에 필요한 요소는 모두 구했으니 적용을 해보면
a,ba, b는 둘다 0이므로 생략이 되어 아래와 같이 전개됩니다.

0x+0y+1z+d=0z+d=0z+n=00\cdot x + 0\cdot y + 1\cdot z + d = 0 \\z + d = 0 \\z + n = 00x+0y+1z+d=0z+d=0zf=00\cdot x + 0\cdot y + -1\cdot z + d = 0 \\-z + d = 0 \\-z - f = 0
근평면의 방정식원평면의 방정식

💥 잠깐! 평면의 방정식에서 유의해야할 사항이 있습니다!

근평면과 원평면이 말하는 dd는 둘 다 다른 데이터로 들어가서 n,fn, f로 작성했지, 결국 같은 개념인데 왜 서로 양수 음수가 다를까요?

그건 바로 각 평면의 방향이 서로 다르기 때문입니다.
이건 이전 편에서 dd의 성질을 배우면서 자연스럽게 알게 된 사실입니다.
이는 정말 중요한 개념이라고 볼 수 있는데 그 이유가
등호를 기준으로 넘기면 전혀 다른 식이 되어버리기 때문입니다!

이를 통해 z+d=0z+d=0zd=0-z-d=0 도 서로 다른 뱡향을 가진 방정식이 되니 이 점 유의해주세요!

기울어진 평면

근평면과 원평면을 제외한 나머지 4개의 평면들은 모두 기울어져 있습니다.
따라서 카메라의 eyeeye벡터를 노멀벡터로 선언하고 해당 점을 화각의 절반만큼 이동시켜야 합니다.
그러곤 90°90\degree만큼 올려줘야 진정한 노멀벡터가 됩니다!

이번엔 먼저 상단 평면을 기준으로 방정식을 전개하고, 나머지 평면들도 구해보도록 합시다.
먼저 eyeeye벡터를 노멀벡터로 선언하고 기울여줍니다.

기울이는 방식은 삼각함수를 통해 변환이 필요한 y,zy, z에 적용시켜줍니다.

(0,1sinθ2,1cosθ2)=(0,sinθ2,cosθ2)(0, 1\cdot sin\frac{\theta}{2}, -1\cdot cos\frac{\theta}{2}) \\ = (0, sin\frac{\theta}{2}, -cos\frac{\theta}{2})

기존 화각의 절반만 움직이니 삼각함수에 θ2\frac{\theta}{2}를 적용하고 이제 90°90\degree만큼 다시 이동을 해줍니다.
xx축 기준 90°90\degree회전이기 때문에 이전에 배웠던 회전행렬을 통해 값을 구해주는 것이 정신건강에 이롭습니다.

따라서 아래처럼 방정식을 전개할 수 있습니다.

[1000cos(π2)sin(π2)0sin(π2)cos(π2)][0sin(θ2)cos(θ2)]=[100001010][0sin(θ2)cos(θ2)]=(0,cosθ2,sinθ2)\left[\begin{matrix} 1 & 0 & 0 \\ 0 & \cos\left(\frac{\pi}{2}\right) & -\sin\left(\frac{\pi}{2}\right) \\ 0 & \sin\left(\frac{\pi}{2}\right) & \cos\left(\frac{\pi}{2}\right) \end{matrix}\right] \cdot \left[\begin{matrix} 0 \\ \sin\left(\frac{\theta}{2}\right) \\ -\cos\left(\frac{\theta}{2}\right) \end{matrix}\right] \\ = \left[\begin{matrix} 1 & 0 & 0 \\ 0 & 0 & -1 \\ 0 & 1 & 0 \end{matrix}\right] \cdot \left[\begin{matrix} 0 \\ \sin\left(\frac{\theta}{2}\right) \\ -\cos\left(\frac{\theta}{2}\right) \end{matrix}\right] \\ = (0, cos\frac{\theta}{2}, sin\frac{\theta}{2})

놀랍게도 해당 평면은 카메라인 원점을 포함하기 때문에 dd가 0이 됩니다.
따라서 최종적인 상단 평면의 방정식은 다음과 같습니다.

cosθ2y+sinθ2z=0cos\frac{\theta}{2}y + sin\frac{\theta}{2}z = 0

방정식을 전개하기 위한 모든 준비는 끝났습니다. 나머지 평면도 전개해봅시다!

하단 평면좌 평면
우 평면

eyeeye벡터를 노멀벡터로 선언하고 기울여줍니다. 상단과 다르게 yy축이 반대로 적용됩니다.

(0,1sinθ2,1cosθ2)=(0,sinθ2,cosθ2)(0, -1\cdot sin\frac{\theta}{2}, -1\cdot cos\frac{\theta}{2}) \\ = (0, -sin\frac{\theta}{2}, -cos\frac{\theta}{2})

xx축 기준 90°-90\degree회전이기 때문에 최종적으로 (100001010)\left(\begin{matrix}1 & 0 & 0 \\0 & 0 & 1 \\0 & -1 & 0\end{matrix}\right)의 값이 나옵니다.

(0,cosθ2,sinθ2)cosθ2y+sinθ2z=0(0, -cos\frac{\theta}{2}, sin\frac{\theta}{2}) \\ \therefore -cos\frac{\theta}{2}y + sin\frac{\theta}{2}z = 0

eyeeye벡터를 노멀벡터로 선언하고 기울여줍니다. 좌측이기 때문에 이번엔 x,zx, z에 영향을 줍니다.

(1sinθ2,0,1cosθ2)=(sinθ2,0,cosθ2)(1\cdot sin\frac{\theta}{2}, 0, -1\cdot cos\frac{\theta}{2}) \\ = (sin\frac{\theta}{2}, 0, -cos\frac{\theta}{2})

yy축 기준 90°-90\degree회전이기 때문에 최종적으로 (001010100)\left(\begin{matrix} 0 & 0 & -1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \end{matrix}\right)의 값이 나옵니다.

(cosθ2,0,sinθ2)cosθ2x+sinθ2z=0(cos\frac{\theta}{2}, 0, sin\frac{\theta}{2}) \\ \therefore cos\frac{\theta}{2}x + sin\frac{\theta}{2}z = 0

eyeeye벡터를 노멀벡터로 선언하고 기울여줍니다. 좌측과 다르게 xx축이 반대로 적용됩니다.

(1sinθ2,0,1cosθ2)=(sinθ2,0,cosθ2)(-1\cdot sin\frac{\theta}{2}, 0, -1\cdot cos\frac{\theta}{2}) \\ = (-sin\frac{\theta}{2}, 0, -cos\frac{\theta}{2})

yy축 기준 90°90\degree회전이기 때문에 최종적으로 (001010100)\left(\begin{matrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ -1 & 0 & 0 \end{matrix}\right)의 값이 나옵니다.

(cosθ2,0,sinθ2)cosθ2x+sinθ2z=0(-cos\frac{\theta}{2}, 0, sin\frac{\theta}{2}) \\ \therefore -cos\frac{\theta}{2}x + sin\frac{\theta}{2}z = 0

1-3. 절두체 컬링의 응용

드디어 지금까지 배운 내용들을 모두 응용하는 단계입니다!
일단 어떻게 판별할지 설명을 해본 다음, 순서도로 정리해보도록 하겠습니다.

  1. 먼저 한 평면과 임의의 점을 평면의 방정식을 통해 바깥쪽에 있는지 확인을 해줍니다.
  2. 만약 바깥쪽에 있다면 다른 면은 확인할 필요없이 절두체 내부에 존재하지 않는다고 결론을 내줍니다.
  3. 안쪽에 있다는 걸 판별하면 계속해서 다음 평면을 가지고 1번으로 되돌아갑니다.

생각보다 간단하군요! 이 로직을 순서도로 정리하면 다음과 같습니다.

1-4. 문제점?

열심히 달려왔지만 안타깝게도 지금의 방식엔 문제점이 존재합니다.

  1. 물체의 위치값 만으로 컬링하면 결과가 부정확해진다.
    코드를 리뷰해보면 물체의 Transform만 이용하여 컬링을 진행하는데
    우리 눈으로 보이는 오브젝트가 절두체에 걸치더라도 Transform이 절두체 밖에 있다면
    컬링되는 문제가 발생하게 됩니다.

    따라서 점이 아닌 부피를 통해 컬링을 진행하도록 수정이 필요하겠죠?
    이건 다음 편인 바운딩 볼륨에서 진행하도록 하겠습니다.

  2. 종횡비가 고려되지 않았다.
    위에서 설명한 내용들을 보면 저희가 배웠던 NDC공간을 생각하지 않고 뷰공간을 기준으로 절두체 컬링을 진행했기 때문에 종횡비가 항상 1대1로 진행되어버립니다.

    이 부분은 바로 아래인 투영 행렬로 해결하는 방법으로 진행하겠습니다.

2. 투영 행렬로 해결

이미 NDC 비율 문제를 모두 해결해놓은 투영 행렬을 통해 종횡비 문제를 해결할 수 있을 것 같습니다!
근데 어떻게 투영 행렬과 평면의 방정식을 서로 연관을 지을 수 있을까요?
이제 하나씩 평면의 방정식으로 유도해가며 알아 가보겠습니다!

2-1. 유도 과정

클립 좌표계를 기억하시나요? 클립 좌표계를 유도했던 투영행렬의 식을 한번 들고와봅시다.

P v=[da0000d0000n+fnf2nfnf0010][vxvyvz1]=[xyzw]P\cdot\ v=\left[\begin{matrix}\frac{d}{a}&0&0&0\\0&d&0&0\\0&0&\frac{n+f}{n-f}&\frac{2nf}{n-f}\\0&0&-1&0\\\end{matrix}\right]\left[\begin{matrix}v_x\\v_y\\v_z\\1\\\end{matrix}\right]=\left[\begin{matrix}x\\y\\z\\w\\\end{matrix}\right]

혹시나 해서 다시 말하자면 x,y,z,wx,y,z,w는 클립좌표계를 뜻합니다.
여기서 행벡터를 뷰공간의 vv랑 내적을 한다고 표현이 가능하기 때문에 아래와 같이 표현이 가능합니다.

[Prow1vProw2vProw3vProw4v]=[xyzw]\left[\begin{matrix}P_{row1}\cdot v\\P_{row2}\cdot v\\P_{row3}\cdot v\\P_{row4}\cdot v\\\end{matrix}\right]=\left[\begin{matrix}x\\y\\z\\w\\\end{matrix}\right]

이걸 방정식으로 한번 풀어보겠습니다.

x=Prow1 vy=Prow2 vz=Prow3 vw=Prow4 vx=P_{row1}\cdot\ v \\y=P_{row2}\cdot\ v \\z=P_{row3}\cdot\ v \\w=P_{row4}\cdot\ v

어.. 그럼 이게 끝일까요? 아닙니다!

이전에 NDC 공간을 그대로 사용하기엔 모두 1:1로 대응해버려서 종횡비를 적용하는 과정을 기억하시나요?
종횡비 문제를 NDC 공간에서 모두 해결했기 때문에 저희는 이러한 NDC 공간을 활용하면 굳이 종횡비를 또 계산하는 번거로운 방식을 생략할 수 있습니다

먼저 저희가 3차원 NDC 공간을 적용했던 범위값은 아래와 같습니다.

1nx11ny11nz1-1\le n_x\le1 \\-1\le n_y\le1 \\-1\le n_z\le 1

💡 참고로 위 NDC 범위값은 OpenGL 기준입니다! 💡
DirectX같은 경우엔 nzn_z값이 0nz10\le n_z\le1 이라는 사실도 확인해보세요!

여기서 저희는 클립 좌표계가 적용된 공간에서 뷰공간으로 포팅하기 때문에 이전에 알아본 이전 단계의 공간으로 포팅하는 작업을 아래처럼 적용하면 됩니다. 따라서 동차의 성질에 따라 ww를 가정하고 이 값을 나눠줍니다.

1xw11yw11zw1-1\le\frac{x}{w}\le1 \\-1\le\frac{y}{w}\le1 \\-1\le\frac{z}{w}\le1

여기서 양변에 ww를 곱하면 아래처럼 표현이 가능합니다.

wxwwywwzw-w\le x\le w \\-w\le y\le w \\-w\le z\le w

이제 미리 구해놨던 클립 좌표계를 위 수식에 대입해보겠습니다.

Prow4 vProw1 vProw4 vProw4 vProw2 vProw4 vProw4 vProw3 vProw4 v-P_{row4}\cdot\ v\le P_{row1}\cdot\ v\le P_{row4}\cdot\ v \\-P_{row4}\cdot\ v\le P_{row2}\cdot\ v\le P_{row4}\cdot\ v \\-P_{row4}\cdot\ v\le P_{row3}\cdot\ v\le P_{row4}\cdot\ v

하나의 수식에 3종류의 값을 비교하기 때문에 이를 좀 더 단순한 구조로 수정하도록 하겠습니다.

예를 들어 [Prow4 vProw1 vProw4 v][\red{-P_{row4}\cdot\ v}\le \blue{P_{row1}\cdot\ v}\le \orange{P_{row4}\cdot\ v}] 라는 식에서
[Prow4 vProw1 v][\red{-P_{row4}\cdot\ v}\le \blue{P_{row1}\cdot\ v}][Prow1 vProw4 v][\blue{P_{row1}\cdot\ v}\le \orange{P_{row4}\cdot\ v}]
식을 나눠서 한 쪽을 0으로 만들어보면 아래와 같이 수식을 표현할 수 있습니다.

(Prow4+Prow1) v0(Prow4Prow1) v0(Prow4+Prow2) v0(Prow4Prow2) v0(Prow4+Prow3) v0(Prow4Prow3) v0\left({P_{row4}+P}_{row1}\right)\cdot\ v\geq0 \\\left(P_{row4}-P_{row1}\right)\cdot\ v\geq0 \\\left({P_{row4}+P}_{row2}\right)\cdot\ v\geq0 \\\left(P_{row4}-P_{row2}\right)\cdot\ v\geq0 \\\left(P_{row4}+P_{row3}\right)\cdot\ v\geq0 \\\left(P_{row4}-P_{row3}\right)\cdot\ v\geq0

뭔가 익숙한 느낌이 납니다.. 눈썰미가 좋으신 분들은 이미 눈치채셨겠지만 저 수식이 바로 평면의 방정식입니다!

'아무튼 더 이상 정리하지 못하니 이게 평면의 방정식이야!' 라고 하기엔 아직은 잘 모르겠습니다..
그렇기에 아래에서 해당 수식에서 저번에 배웠던 평면의 방정식으로 유도하는 과정을 자세히 알아보도록 하겠습니다.

2-2. 정규화 하기

절두체 컬링을 구현하기 위해선 우리가 알고있는 기존 평면의 방정식으로 적용하여 뷰공간의 점 vv와 방향을 나타내는 벡터를 활용할 수 있도록 만들어야합니다.

여기서 뷰공간의 점 vv(x,y,z,1)(x, y, z, 1)로 표현하고 방향을 나타내는 벡터는 (a,b,c,d)(a, b, c, d)로 표현하겠습니다. 이를 평면의 방정식에 대입해보도록 하겠습니다.

ax+by+cz+d0ax+by+cz+d\ge0

여기서 이전에 다뤘던 평면의 방정식 정규화를 여기서도 진행하게 되는데 몇가지 특징들이 있습니다. 이번에 다루는 방정식의 특징은 아래와 같습니다.

  • 판별식이므로 평면의 방정식 자체에 부등호가 적용됩니다.
  • 평면의 방정식은 방향이 NDC 내부, 즉 절두체 내부로 들어가기 때문에 노멀 벡터값을 평면 밖으로 빼주고 빠진걸 걸러내기 위해서 전체적으로 음수를 달아줍니다.
  • 같은 평면 위에 존재하는 오브젝트도 화면에 보이기 때문에 부등호가 >> 로 바뀝니다.

이를 수식으로 표현하면 아래와 같은 수식이 나옵니다.

(ax+by+cz+da2+b2+c2)>0-\left(\frac{ax+by+cz+d}{\sqrt{a^2+b^2+c^2}}\right)>0

2-3. 이게 평면의 방정식이라고요?

절두체 중 상단 평면의 방정식을 서로 비교해보면 신기하게도 잘 맞아 떨어지는 걸 볼 수 있습니다. 하지만 너무 추상적인 수식이라서 그런지 감이 잘 잡히진 않습니다. 따라서 이번에 유도한 평면의 방정식을 저희가 저번에 배웠던 평면의 방정식으로 유도하는 과정을 알아봅시다.

먼저 저희가 알고 있는 상단 평면의 방정식은 cosθ2y+sinθ2z>0\cos{\frac{\theta}{2}}y+\sin{\frac{\theta}{2}}z>0 였습니다.
그리고 방금 구했던 방정식 중에 상단 평면에 해당하는 부분은 nyn_y의 상단을 담당하는
Prow2 vProw4 vP_{row2}\cdot\ v\le P_{row4}\cdot\ v(Prow4Prow2) v>0-\left(P_{row4}-P_{row2}\right)\cdot\ v>0 를 한번 풀어보도록 하겠습니다.

먼저 Prow4Prow2P_{row4}-P_{row2}를 투영 행렬의 값을 대입하여 평면의 방정식을 유도합니다.

(Prow4Prow2) v>0((0,0,1,0)(0,d,0,0))v>0(0,d,1,0)v>0(dyz)>0-\left(P_{row4}-P_{row2}\right)\cdot\ v>0 \\ -((0, 0, -1, 0) - (0, d, 0, 0)) \cdot v > 0 \\ -(0, -d, -1, 0) \cdot v > 0 \\ -(dy - z) > 0

여기서 카메라와 NDC의 초점거리인 dd1tan(θ2)\frac{1}{\tan(\frac{\theta}{2})} 임을 저번에 다뤘습니다. 이를 적용해봅시다.

(1tan(θ2)yz)>0-\Big(\frac{1}{tan(\frac{\theta}{2})}y-z\Big) > 0

sin\sincos\cos으로 이루어진 상단 평면의 방정식을 유도하기 위해 tan\tansinθcosθ\frac{\sin\theta}{\cos\theta}로 대입합니다.

(1sinθ2cosθ2yz)>0sinθ2cosθ2y+z>0cosθ2y+sinθ2z>0-\Big(\frac{1}{\frac{\sin\frac{\theta}{2}}{\cos\frac{\theta}{2}}}y - z\Big) > 0 \\ \frac{\sin\frac{\theta}{2}}{\cos\frac{\theta}{2}}y+z > 0 \\ \therefore \cos{\frac{\theta}{2}}y+\sin{\frac{\theta}{2}}z>0

신기하게도 위에서 다룬 방정식으로 유도가 됩니다!

생각보다 다루는 내용이 많았습니다. 하지만 천천히 살펴보면 행렬을 통해 전개를 더욱 간단하게 했다는 점에 대해 알 수 있었던 시간이였습니다.
다음 편엔 바운딩 볼륨과 절두체 컬링의 최종 수식에 대해 알아보도록 하겠습니다!

profile
(게임 엔진 프로그래머가 되고싶은) 게임 클라이언트 프로그래머

0개의 댓글