[3D] 절두체 컬링의 종류

절두체 컬링의 종류화 간단한 이해를 적은 글로 GPG 5권 1.6 개선된 절두체 선별을 보고 공부한 후 작성했습니다.

컬링이란 게임 내의 물체를 적절히 관리해 렌더링을 효과적으로 하기 위한 일로

쉽게 말하면 부하가 심해져서 프로그램에 렉이 걸리지 않기위해 하는 것이다.

절두체란 시야에 보이는 영역을 표현한 입체로 카메라 투영행렬로 나타낼 수 있다.

1. 6 평면 방식

- 가장 일반적인 방법의 컬링이 절두체의 6 평면을 이용한 것인데,

한 정점이 절두체 안에 있는지 알기 위해 평면 방정식으로 판단하는 것으로 6 평면 모두를 판단 한다.

단점은 모든 평면의 평면 방정식을 만족해야 안심할 수 있다는 것이다.

또한 절두체의 위치나 방향을 얻는데 드는 비용이 상당하기 때문에 카메라 이동 시 마다 계산한다고 해도  불필요한 연산을

하게 된다.

2. 레이더 접근 방식

 - 레이더 파형 안에 있는 물체만 화면에 나타내는 것으로

간단하게 말하자면, 점 P가 근, 원, 좌, 우, 상, 하 경계 내에 있으면 절두체 내에 있다는 것이다.

어떤 한 정점P 을 카메라의 원점 O와 잇는 벡터를 만들고, 

시야 벡터와 우향 벡터를 이용해 길이와 너비를 잰 뒤 범위 내에 있는지 판단한다.

상, 하의 경우 너비에 종횡비를 곱해서 나온 높이 값으로 범위 판단 한다.

3. 경계구 판정

- 경계구 판정은 레이더 접근 방식과 비슷합니다. 단지 정점이 아닌 오브젝트를 감싸는 큰 원을 두고

그 원의 중점이 절두체 내부에 반지름 r 만큼 떨어진 거리에도 존재 하는지 판단하면 됩니다.

달라진 것은 단지 반지름 r의 크기입니다.

이 경우 완전한 외부, 완전한 내부, 겹침 의 3가지 경우가 있으며 겹침의 경우는 또 다른 방식으로 판정합니다.

4. 계통적 장면 조직화

- 모든 물체를 절두체와 비교하는 것은 최적이 아니다. 따라서 장면의 물체를 감싼 경계 입체들로 구성된 장면 계통 구조를 사용해

판정의 횟수를 줄일 수 있다.

여기서 사용되는 알고리즘이 쿼드 트리, 옥트리, BSP 트리, KD 트리 ABT 등이 있다.

여기서 좀 더 최적화 하는 방법이 

- 평면 마스킹 이다.

평면 마스킹이란 부모 물체가 근, 원, 좌, 우, 상, 하 에 판단 하는지 보고 그 여부를 비트로 저장하는 것이다.

만약 근, 원, 상, 하 내에 있다면 101 이 될 것이다.

이렇게 되면 그 부모 물체 내부의 자식 들은 좌, 우 판정만 하면 되므로 또 연산 회수가 감소한다.

이처럼 계통 구조를 따라 판정을 수행할 때 특정 축들에 대한 판정을 생략하는 것을 평면 마스킹이라고 한다.

- 평면 응집성

그 전에 판정에 실패한 물체는 다음 판정에서도 실패할 가능성이 크다는 것이다. 

따라서 이전 프레임에서 실패한 판정부터 수행한다면, 불필요한 판정을 줄일 수 있다.

이 역시 판정 결과를 비트로 저장해 다음 판정에 도움이 되게 한다.

- 절두체를 감싸는 AABB 판정

AABB 란 Asix-Alined Bounding Box 로 "축에 정렬된 경계 상자" 라는 뜻이다.

AABB에 대한 판정은 축당 2번, 총 6번만 비교하면 되기 때문에 아주 빠르다. 

결론부터 말하자면 절두체를 큰 AABB로 감싸 내부에 있다고 판단되지 않는 것은 절두체에 있지 않다고 판단하는 것이다.

물론 걸쳐져 있다면 다른 판정을 수행해야 한다.