[펌] www.gpgstudy.com에서 퍼온 Frustum Culling 최적화 루틴에 관한 글입니다.

urin (참고) 개선된 프러스텀 컬링 기법

안녕하세요, 우린입니다.

지금 여기에 설명하려는 프러스텀 컬링 기법은 저희 게임에서 사용되고 있는 bsp포탈 구조의 막대한 양의 프러스텀 컬링에 대해 옵티마이징을 하면서, 며칠간 고민끝에 발견해낸 기법입니다. 물론 다른 어느 분이 이미 개발하여 쓰고 있을지도 모르지만 저로써는 순수히 맨땅에 헤딩해서 개발한 기법입니다.

이 기법의 포용 범위는 min,max값으로 구성된 박스에 한정됩니다.

일반적인 프러스텀 컬링은 6개의 평면에 대해 평면의 방정식을 통해 8개의 점의 평면의방정식 값이 0보다 큰가를 검사합니다. 이를 위해 최대 48번의 도트프러덕트 연산이 수행됩니다.
여기서 요점은, 하나의 평면에 대해 8개의 점중에 하나라도(또는 가장 평면의방정식 값이 큰점이), 평면의방정식 값이 0보다 크다면 프러스텀 컬링에 포함된다는 것입니다.

min,max값 만으로 구성된 박스는 그 값에 상관 없이 하나의 평면에 대해, 가장 큰 값을 갖는 점이 정해져 있습니다. 이에 대해 수학적 증명을 해보겠습니다.

max(x,y,z);
min(x1,y1,z1);
x>x1
y>y1
z>z1
일 경우

Ax+By+Cz+D = 0;이라는 평면을 생각해봅시다.

A가 0보다 크면
Ax+By+Cz+D 는
Ax1+By+Cz+D 보다 큽니다.

B가 0보다 크면
Ax+By+Cz+D 는
Ax+By1+Cz+D 보다 큽니다.

C가 0보다 크면
Ax+By+Cz+D 는
Ax+By+Cz1+D 보다 큽니다.

즉 하나의 평면이 검사를 해야할 정점 Vector는

Vector.x = (A > 0 )? max.x:min.x;
Vector.y = (B > 0 )? max.y:min.y;
Vector.z = (C > 0 )? max.z:min.z;

이렇게 구성됩니다.

if(A*Vector.x+B*Vector.y+C*Vector.z+D <0)
{
이 프러스텀에 대해 포함되지 않음
}

물론 이런 식으로 이 평면이 검사해야할 점이 몇번 점인가를 찾는것은 프러스텀을 생성한후 6개의 평면에 대해 각각 1회씩만 하면 됩니다. 박스의 minmax값이 하나의 플롯형 배열로 구성되어있는 경우 각 평면이 연산해야할 점을 빠르게 찾아서 연산해줄 수 있겠지요.

여기에 추가로
하나의 박스가 프러스텀에 포함될때 완전히 포함되는가 아니면 인터섹트가 일어나는가를 검사해봅니다.
가장 거리가 작은 점이 프러스텀에 포함되지 않으면 이 박스는 인터섹트가 일어납니다.

Vector.x = (A < 0 )? max.x:min.x;
Vector.y = (B < 0 )? max.y:min.y;
Vector.z = (C < 0 )? max.z:min.z;

이렇게 구성됩니다.
if(A*Vector.x+B*Vector.y+C*Vector.z+D <0)
{
인터섹트가 일어남
}

위의 방식으로 최대 12회 검사를 통해 프러스텀 컬링이 완성됩니다.


밑에 어느분이 답글에서 이 부분에 대해 논문이 있다는 얘기를 듣고 깜짝이야, 놀랐습니다.
부끄러워서 폭파시키려다가 그냥 놔둬봅니다.

저는 지난 2004년 11월 사전제작지원 공모에 우수상을 수상한 페이퍼맨의 클라이언트 프로그래머로 일하고 있습니다. 소속은 엔트랜드라고 돼어있지만 실제론 다섯명의 개발자가 아무런 외부 도움없이 1년간 작업을 해왔어요. 넷마블 VOD게시판 관리해주면서 한사람당 월 8만원 받고 1년을 버텼답니다...
올 7월에 저희게임 오픈하면 많이 구경와주시기 바랍니다.
그 전에 클로즈하게되면 또 많이 와주시기 바라고요.


urin 가 2005-01-13 23:28에 수정함, 총 2 번 수정됨

류광 ...

고맙습니다. (그리고 수상 축하드립니다~)

시간 내서 찬찬히 읽어봐야겠습니다...

duckimg  관련 논문 참고

Assarsson 아저씨의 논문이 있습니다.

"Optimized View Frustum Culling Algorithms for Bounding Boxes"

구글님이 알고 계시네요.
_________________
난 너를 만나기 위해 이 세상에 태어났어
그러니 내 생활비는 네가 대 주어야만 해

urin 헉 이럴 수가

24시간 후에 내용 삭제하겠습니다... 이럴수가... 쪽팔리네요...

근데 저 논문은 어떻게 보나요?

류광 ...

삭제할 필요 있을까요? 무엇보다도 그 논문은 영어이고 urin님의 글은 한글인걸요. icon_smile.gif (아, 두 기법이 정확히 동일한 것인지는 확인하지 않았습니다. duckImg 님이확인해 주시면 고맙겠네요...)

그리고 애초에 "물론 다른 어느 분이 이미 개발하여 쓰고 있을지도 모르지만 저로써는 순수히 맨땅에 헤딩해서 개발한 기법입니다. "라고 밝히셨구요. 사실 세계 어느 곳에서 매 순간마다 일어나는 일일 것입니다....

오히려 자랑스러워 하셔도 될 것 같습니다. (물론 다음부터는 검색을 먼저 하는게 좋겠지만요...)
 

        unin 씀:

        근데 저 논문은 어떻게 보나요?

저 논문은 구글에서 검색하면 바로 나옵니다.


류광 ...

아 그리고 참고로, 논문을 전문적으로 검색할 만한 곳으로 CiteSeer http://citeseer.ist.psu.edu/ 가 유명하구요. 또 얼마전에 구글이 논문 전문 검색 서비스 구글 스칼라 http://scholar.google.com/ 를 시작했습니다.

duckimg  ....

에구... 스스로 생각해 내셨다니 대단하다는 말을 쓸려다가 안 썼는데
언짢으셨다면 죄송합니다..
urin님의 글을 무시하는 뜻은 전혀 없었구요,
오히려 이런 좋은 내용이 잘 알려지지 않아서 논문을 링크 시킨 것입니다.

논문의 기본적인 내용은 urin님이 생각하신 내용과 거의 흡사하구요
거기에 기타 다른 기법들이 추가된 것입니다.
_________________
난 너를 만나기 위해 이 세상에 태어났어


행인 re

안녕하세요.
좋은 글 감사합니다. 제가 쓰는 식이랑 똑같이 나오는거 같습니다. 확인해 보세요. 다만, 증명하는 과정이 약간 다르군요.

임의의 R, S, T를 기본축으로 하고, 크기도 R, S, T인 상자에 대해서, 한 평면 L= < N, D> 의 N방향에 대한 Effective radius는,
 

 코드:

Reff = 0.5 * { |R dot N| + |S dot N| + |T dot N|}


 입니다. (왜 이렇게 되는지는 직선과 상자를 그려서 보시면 됩니다 ^^)

이제 이상자가 이 평면의 양의 쪽에 있는지, 음의 쪽에 있는지는 이 상자의 중심 C 와 평면까지의 거리를 구하고, Reff와 비교해주면 됩니다.

Signed Distance = C dot L
1. If Distance < - Reff , or Distance + Reff < 0
이경우에는 상자가 평면의 음의 쪽에 위치하게 됩니다.

2. If Distance > Reff, or Distance - Reff > 0
이때는 상자가 평면의 양의쪽으로 쏙 들어가게 되죠.

3. 그외의 경우
상자가 평면에 걸치는 경우입니다.

P0, P1 을 가지는 축정렬 상자에 대해서 위의 식을 적용하면,
C = 0.5 * (P0 + P1)
DP = P1 - P0
R =
S = <0, P1.y-P0.y, 0>
T = <0, 0, P1.z-P0.z>

이제 위의 1, 2 경우를 체크해주면 됩니다.
1. Distance + Reff
= 0.5 * L dot (P0 + P1) + 0.5 * { |R dot N| + |S dot N| + |T dot N|}
= 0.5 * {N dot P0+ D+ N dot P1 + D + |N.x |*(P1.x - P0.x) + |N.y| *(P1.y - P0.y) + |N.z| *(P1.z - P0.z) }
= D + 0.5 * { N.x * P0.x + N.y * P0.y + N.z * P0.z + N.x * P1.x + N.y * P1.y + N.z * P1.z + |N.x |*(P1.x - P0.x) + |N.y| *(P1.y - P0.y) + |N.z| *(P1.z - P0.z) }

Distance + Reff 를 다음과 같이 계산합니다.

 코드:

checkvalue = D
if N.x > 0
checkvalue += N.x * P1.x
else
checkvalue += N.x * P0.x
if N.y > 0
checkvalue += N.y * P1.y
else
checkvalue += N.y * P0.y
if N.z > 0
checkvalue += N.z * P1.z
else
checkvalue += N.z * P0.z
 

이제, checkvalue 가 0보다 작으면 평면의 음의 쪽에 사각형이 완전히 위치하고, 프러스트럼에서 보이지 않게 됩니다.

2. Distance - Reff, 이는 따로 체크할 필요가 없을수도 있지만, 평면내에 사각형이 완전히 들어가는지 확인할 때 쓰입니다. 그럴 필요가 없다면 1 만 해주면 됩니다.
= D + 0.5 * { N.x * P0.x + N.y * P0.y + N.z * P0.z + N.x * P1.x + N.y * P1.y + N.z * P1.z - |N.x |*(P1.x - P0.x) - |N.y| *(P1.y - P0.y) - |N.z| *(P1.z - P0.z) }
Distance - Reff 도 다음과 같이 계산합니다.

코드:

checkvalue = D
if N.x < 0
checkvalue += N.x * P1.x
else
checkvalue += N.x * P0.x
if N.y < 0
checkvalue += N.y * P1.y
else
checkvalue += N.y * P0.y
if N.z < 0
checkvalue += N.z * P1.z
else
checkvalue += N.z * P0.z
 

앞의 1과는 체크하는 부호만 바뀌었습니다. checkvalue 가 0보다 크면 이 평면이 양의 쪽에 들어간다고 판단되므로, counter를 두어서 증가시키면 되겠습니다. 6개의 평면에대해서 모두 체크한 후에 counter가 6이면 프러스텀 내에 완전히 들어간다고 보면 됩니다. 그외의 경우는 부분적으로 겹치는 경우가 됩니다.

결과는 말씀하신것과 완전히 같습니다.

결과는 말씀하신것과 완전히 같습니다.

PS. 이방법이 최고는 아닙니다만, 간단해서 사용하고 있습니다. 그 논문인지는 모르겠으나 보면, 계산할 필요가 없을때도 따져주고 제법 복잡하게 따지던거 같습니다. 그리고 이렇게 체크하는건 사각형이 길 경우 쥐약입니다.


urin 내용 삭제했습니다.(자삭)

좋은 하루 되세요.

행인 re

같은 것으로 보입니다만 ^^
각 평면에 대해서 한번만 계산한다는 점이 똑같습니다. Min, Max 리스트는 저장해둘 필요는 굳이 없을거 같은데요?

 

PS. 그리고 이 쓰레드는 지우지 말았으면 합니다. 이 쓰레드에서 프러스텀 컬링에서 할수 있는 온갖 나쁜 짓을 다뤘으면 합니다.

글을 덧붙이면 보기 싫을 듯하여, 여기다 씁니다. 계산을 굳이 할필요가 없다는 말입니다. 위의 제가 적은 코드에서 보듯이, 비교하는 시점에서 평면의 노멀값의 부호를 따져주면 min, max를 저장할 필요가 없다는 뜻이였습니다. ^^ 다시봐도 완전히 동일합니다. P0는 min에, P1은 max에 해당하겠군요.

비회원 음....

정리해보면, SAT 등을 사용한 frustum & box 테스트가 아닌 이상,
결국은 plane & box 테스트 최적화로 귀결되는데요.

1. brute force
- 평면에 점 8개 대입, 양의 부호이면 outside, 음의 부호이면 inside, 아니면 intersect
- 부하: dot 8회

2. box's diagonal
- 평면의 normal 기준으로 min, max를 산출
- 평면에 산출 된 2개의 점 대입
- 부하: if 3회, min/max 대입, dot 2회(min, max)

3. urin & 행인's way ^^:
- 평면의 normal에 각 축의 half extent 대입하여 반지름 계산(r)
- 평면에 box의 center를 대입(d), r > d 이면 outside, 음의 부호이면 inside
- 부하: dot 3회(box's axes & plane's normal), dot 1회(box's center & plane)

그런데 여기서 항상 (1)이 후졌다..;; 라고 보기는 어렵습니다.
(1)은 어떤 전처리도 없이 exclusion test만으로 이루어져 있기 때문에 어떤 경우는 더 빠르기 때문이죠.
개인적으로 frustum & box에는 (1)의 방식을, plane & box에서는 (2)의 방식을 쓰고 있습니다만..
frustum & box를 (2)로 바꾸나 (3)으로 바꾸나 거의 차이가 없었습니다.
상황에 따라 어느 놈이 빠르기도 한데 무시할 수 있는 수준이더군요. (outdoor의 MMOG 스타일입니다.)

urin 테스트 결과

1프레임당 약 500여회의 프러스텀 컬링을 실행하는 fps에서 테스트 결과 40프레임대에서 약 2-3프레임 속도 향상을 얻었습니다.