[그래픽스] 가시부피와 절단

현재까지 작성한 렌더링 머신은 시야에서 벗어난 물체들에게도 변환 연산을 수행합니다. 

 

 

픽셀을 찍기 전에 해당 좌표가 스크린에 존재하는지 검사하는 조건문이 있기 때문에, 카메라에서 벗어난 물체는 그리지 않습니다.

 

그럼에도 불구하고, 오브젝트를 이루는 모든 정점에 대해 모델링 변환, 뷰 변환, 원근 변환, 그리고 픽셀화 직전까지의 모든 연산이 수행됩니다.

 

따라서 오른쪽 사진에서처럼 렌더링할 물체가 거의 없더라도, 높은 프레임을 유지하지 못하는 이유는 그릴 필요가 없는 물체를 위해 무의미한 연산이 이루어지기 때문입니다.

 

이 문제를 최적화하려면, 그릴 필요가 없는 물체를 빠르게 걸러낼 필요가 있습니다.

 

 

이전 글에서 다뤘듯

뷰 공간에서 NDC 공간을 나타내면 위 그림과 같습니다.

 

해당 사다리꼴 영역을 뷰 공간으로 확장해봅시다.

이러한 사다리꼴 영역을 가시 부피 라고 부릅니다.

 

 

입체적으로 보면 이런 형태로 생겼습니다.

이러한 잘린 피라미드 꼴을 절두체 라고 합니다. 

 

뷰 공간에서 가시부피(Frustum) 밖에 존재하는 오브젝트는 그릴 필요가 없습니다. 만약 뷰 공간에서 오브젝트의 좌표가 가시부피 외부에 있는지, 내부에 있는지를 판단할 수 있다면, 불필요한 연산을 줄일 수 있습니다.

 

이러한 과정을 절단(Culling)이라고 합니다.

 

가시부피는 6개의 평면으로 이루어져 있습니다. 점과 평면 사이의 관계를 이용하면 절단을 구현할 수 있습니다.

 

그렇다면 먼저 가시부피를 이루는 6개의 평면의 방정식을 세워봅시다.

평면의 방정식은 위와 같이 정의됩니다.

평면위의 점과 평면의 법선벡터만 있으면, 평면의 방정식을 정의할 수 있습니다.

 

 

만약, 정규화된 법선벡터로 평면을 정의할 수 있다면 d의 값은 특별한 의미를 가집니다.

p1를 법선벡터와 내적하면 그 절댓값은 원점과 평면의 최단거리를 의미합니다. 

 

 

최단거리를 나타내는 n과 p의 내적은 d의 절댓값과 동일합니다.

d는 양수 혹은 음수일 수 있기 때문에 한가지 정보를 더 가지고 있다고 볼 수 있습니다. 

 

p1과 n이 같은 방향을 바라볼 경우 d는 음수이고

 

p1과 n이 다른 방향을 바라볼 경우 d는 양수입니다.

 

 

즉, d값의 절댓값은 원점과 평면사이의 최단거리를

d의 부호는 평면이 바라보는 방향을 의미한다고 생각할 수 있습니다. 

 

이제 d의 값을 가지고, 공간상의 어떤 점이 평면의 밖에 존재하는지, 안에 존재하는지 판단해봅시다. 

 

 

먼저 P1부터 판단합니다.

 

 

먼저, d가 음수일 경우 p1은 내부 점입니다.

이때, p1와 법선벡터를 내적한 값은 양수입니다.

 

p1을 투영한 값은 최단거리 -d보다 작습니다.

그러므로

 

내적 + d < 0 일 경우, 내부점이라고 생각할 수 있습니다.

 

다음, d가 양수일 경우 p1은 외부 점입니다.

이때, p1와 법선벡터를 내적한 값은 음수입니다.

 

투영벡터의 크기는 -내적 입니다.

한 값은 최단거리 d보다 작습니다.

 

그러므로

내적 + d > 0 일 경우, 외부점이라고 생각할 수 있습니다. 

 

위와같은 판별식은 P2에 대해서도 동일하게 적용됩니다.

 

이제 우리는 d값을 이용해서 점의 내외부 판단을 수행할 수 있게 되었습니다.

 

단, 주의해야할 점은 정규화 법선벡터로 정의된 평면의 방정식에 대해서만 해당 판별식을 사용할 수 있다는 것 입니다.

그러면 임의의 평면의 방정식을 정규화시켜봅시다.

 

정규화 평면의 방정식의 a', b', c'는

법선벡터를 정규화하여 구할 수 있습니다.

 

 

d' 값은 d에 법선벡터의 노름을 나눠주면 구할 수 있습니다.

즉, 정규화 평면의 방정식은 간단하게 정리됩니다. 

 

그렇다면 가시부피를 이루는 평면들의 방정식을 구해보도록 합시다.

 

 

뷰 공간임에 유의하면서

가시부피의 윗면 평면의 방정식을 세워봤습니다.

 

윗면 우측면 아랫면 좌측면은 모두 원점을 지나는 평면이기에 생각보다 식이 간단합니다.

 

 

이제 근평면과 원평면의 방정식을 구해봅시다.

 

 

얍 구해봤습니다.

 

이제까지 서술한 내용을 중점으로

1. 평면의 방정식 클래스

2. 가시부피 클래스

3. 절단

 

3가지를 작성해보겠습니다.

 

 

1. 평면의 방정식 클래스

 

정규화되지 않은 평면의 방정식을 사용할 필요없기 때문에

항상 정규화된 평면을 정의할 수 있도록 하였습니다.

 

2. 가시부피 클래스

 

가시부피는 6개의 평면의 방정식으로 이루어져있습니다.

IsOutside는 공간상의 한 점에 대해서 내외부 판정을 수행합니다.

 

 

렌더링 코드에 가시부피를 정의하고

 

 

대략적으로 절단을 구현해봅니다.

내외부 판단을 위한 점은 오브젝트의 이동 변환에 뷰 행렬을 곱해서 구했습니다. 

 

 

 

절단이 잘됩니다.

 

 

빠르게 물체들을 걸러내다보니 아무것도 그릴 필요가 없을 때

무거운 행렬곱 연산을 줄일 수 있어 프레임이 1000까지 올라갑니다.

 

그런데 하나 문제점이 있습니다.

 

 

절단 영역이 윈도우 크기만큼이 아니라, 정사각형 꼴로 되고 있습니다.

그 이유는 평면을 방정식을 정의할 때 종횡비를 고려하지 않았기 때문입니다.

 

위 프로그램의 경우 횡이 종보다 길이 때문에, 종은 절단이 잘되지만

횡은 제대로 절단이 안되는 모습을 모여줍니다.

 

이 경우 종횡비를 고려하여 좌우측 평면의 방정식을 새롭게 정의해주도록 합니다.

종횡비를 고려하면 화각이 변하게 됩니다.

새로운 평면의 방정식을 정의하려면 역삼각함수로 각도를 구해줘도 되지만

 

결국 필요한 것은 cos, sin 값이므로

NDC와 카메라 사이의 빗면의 길이를 계산하여 cos, sin 값을 직접 구하는 것이 더 효율적입니다.

 

이는 좌우측 평면의 방정식을 정의할 때, 종횡비를 고려하여 새로운 화각을 계산합니다.

그 다음 해당 각도를 이용해서 평면을 정의하면 정확한 가시부피를 얻어낼 수 있습니다.

깔끔하게 절단되는 모습을 보여줍니다.

 

조금 더 쉽게 가시부피를 정의해봅시다.

 

 

 

NDC 좌표계 내에서

x, y, z가 위 범위를 벗어난다면 그리지 않습니다.

 

이를 클립좌표계로 확장해봅시다.

 

NDC 좌표는 클립좌표계에 w값는 나눈것에 불과합니다.

 

 

그러면 절단을 클립좌표계에서 수행할 수 있습니다.

 

이제 원근 투영 과정을 살펴봅시다.

여기서 뷰좌표와 클립좌표계 사이의 관계를 살펴봅시다.

 

원근 투영 행렬의 각 행을 r1, r2, r3, r4 라는 4차원 벡터로 나타낸다고 하고

뷰 벡터를 전치 시키면 두 행렬은 곱셉을 할 수 있습니다.

 

그리고 이 행렬 곱은 결과는 벡터 v와 행들의 내적으로 정리할 수 있습니다.

 

 

그럼 이렇게 클립좌표계와 뷰좌표계 사이의 등식이 성립하게 되고

 

그러면 이런 식으로 클립좌표계 부등식을 뷰 좌표계 부등식으로 변환할 수 있습니다.

 

이를 6개의 부등식으로 분리할 수 있습니다.

이 6개의 부등식을 모두 만족한다면, 점이 가시부피 내에 있다고 판별할 수 있습니다.

 

이 부등식은 NDC 좌표계의 조건부터 차근차근 뷰 좌표계로 확장시킨것이니 쉽게 이해할 수 있습니다.

더 나아가 해당 부등식을 오브젝트의 로컬 좌표계까지 확장시킬 수 있으나 이는 나중에 수행하겠습니다.

 

일단 이 부등식을 통해서 평면의 방정식을 정의할 수 있어야 가시부피를 정의할 수 있을겁니다.

하나의 부등식만 평면의 방정식으로 변화시켜봤습니다.

위와 같은 방식으로 6개의 평면을 모두 정의할 수 있습니다.

 

이 부등식은 정규화 평면의 방정식이 아니기 때문에 정규화를 시켜줘야만 합니다.

또, 현재 코드에 의하면 가시부피에 정의된 평면의 법선벡터는 모두 밖을 바라봐야 합니다.

 

위 부등식들은 [-1, 1] 라는 조건문에서 유도한 것이기 때문에 가시부피 안쪽을 바라보고 있을겁니다.

- 부호를 붙여 평면이 밖을 바라보도록 변경합니다.

 

 

평면의 방정식을 모두 정의할 수 있게 됐습니다. 

 

원근 투영행렬로 평면을 정의하면 삼각함수를 사용하지 않기 때문에 계산의 복잡도가 감소합니다. 

 

 

 

원근 투영 행렬로 가시부피를 정의하는 모습입니다.

그 외의 코드는 모두 동일합니다.

 

결과

 

 

절단 자체는 잘 되는데 문제점은 오브젝트의 중심좌표를 기준으로 절단을 수행하기 때문에

이렇게 걸쳐진 오브젝트는 안그려지는 문제가 생깁니다. 

 

절단 작업을 수행할 때는 오브젝트의 중심과 같은 모호한 지점이 아닌, 정점들의 집합을 통해 평면과의 충돌을 정확히 감지해야 합니다. 그러나 모든 정점에 대해 충돌을 감지하는 것은 과도한 연산을 요구합니다. 이를 효율적으로 처리하기 위해 구나 육면체와 같은 단순한 원시 도형을 사용하여 충돌을 대신 판별하는데, 메시를 대표하는 단순한 도형을 바운딩 볼륨(Bounding Volume)이라고 합니다.

 

바운딩 볼륨으로 사용되는 도형으로는 구, AABB, OBB 등이 존재합니다.

 

적당한 정밀도를 가지면서, 구현이 간단한 AABB 도형으로 바운딩 볼륨을 정의해보겠습니다.

 

AABB 바운딩 볼륨을 모든 정점을 포함하면서, 각 면이 X,Y,Z과 평행한 육면체를 의미합니다.

 

 

 

AABB 클래스를 작성해봅시다.

 

 

AABB 클래스는 위와 같습니다.

 

모든 정점 버퍼를 순회하면서, 최소점과 최대점을 갱신합니다.

AABB 도형은 항상 기저축과 평행하기 때문에 2개의 점만 가지고 있어도 충분합니다.

 

이제 AABB 도형과 평면 사이의 충돌을 생각해봅시다.

 

 

충돌 감지를 위해서는 평면과 가장 가까운 AABB 점을 구하고, 해당 점과 평면 사이 내외부 판별을 수행하면 됩니다.

그러면 가장 가까운 AABB 점은 어떻게 구할까요?

 

그림을 2차원으로 간단하게 해봤습니다.

 

도형이 평면 외부에 위치하다고 가정하면

가장 가까운 점은 

법선벡터가 양수 -> Min 선택

법선벡터가 음수 -> Max 선택

을 반복하여 구할 수 있습니다.

 

만약에 도형이 평면과 겹칠 경우에는 어떻게 할까요?

만약, 가장 가까운 점이 내부로 판별되면

반대에 점을 얻어냅니다. 해당 점은 가장 먼 점이 됩니다.

 

이 점이 외부로 판별되면, 도형이 평면과 겹쳐져있다고 판단할 수 있습니다.

 

만약, 반대의 점 또한 내부로 판별되면 도형이 평면 내부라고 판단할 수 있습니다.

 

충돌 플래그를 정의하고

 

오브젝트에 바운드볼륨을 추가해줍니다.

 

 

가시부피에 AABB 충돌 로직을 추가합니다.

 

 

바운딩 볼륨도 뷰 공간으로 변환해야 합니다. 이를 위해 모델링 행렬과 뷰 행렬을 곱하여 바운딩 볼륨의 정점을 변환합니다.

 

뷰 행렬에는 X축과 Z축을 반전시키는 요소가 포함되어 있어, 변환 후 최소점의 X, Z 값은 뷰 좌표의 최대점 X, Z 값이 대응됩니다. 따라서 정확한 최소점과 최대점을 얻기 위해 두 점의 X, Z 값을 서로 교환해주어야 합니다.

 

이 과정을 통해 절단 로직을 완성했습니다. 바운딩 볼륨이 가시부피가 겹칠 경우, 이를 시각적으로 표현하기 위해 텍스처 매핑 대신 와이어 프레임 렌더링을 적용해 보았습니다.

 

 

이런 식으로 코드를 바꾸면 더 정확하게 절단을 수행할 수 있게 됩니다. 

 

여기서 최적화를 수행해봅시다.

 

해당 부등식을 로컬 좌표계까지 확장시킬 수 있다면, AABB 박스의 최댓점 최솟점을 계산하는 과정을 수행하지 않을 수 있습니다.

 

더하여, 이 방식은 계산 오버헤드가 거의 발생하지 않습니다.

한 번 로컬좌표계에서 가시부피를 정의해봅시다.

 

윗부분에서 뷰좌표계에서 절단 판별식을 구한 것과 동일하게

판별식을 구하는 것을 로컬좌표로 차례차례 확장시켜 나갈 수 있습니다. 

 

 

최종적으로는 위와같은 판별식을 얻을 수 있습니다.

여기서 사용되는 r1, r2, r3, r4는 최종 행렬에서 구할 수 있고, 좌표 v는 로컬좌표입니다.

 

이렇게 가시부피를 구현하면 얻을 수 있는 장점은

바운드 볼륨 정점을 변환하지 않아도 되고, 평면의 방정식은 이미 계산된 최종 행렬에서 얻어내는 것이기 때문에 오버헤드가 거의 발생하지 않습니다.

 

이를 이용하여 로직을 최적화해보겠습니다.

 

 

절두체를 간단하게 최종 행렬에서 떼와서 정의합니다.

 

최종 절단 완성