프러스텀 컬링 기법

2D, 3D, 다각형, 픽셀 등 게임의 그래픽 프로그래밍에 관한 포럼입니다.

Moderator: 류광

Locked
urin
Posts: 19
Joined: 2004-11-13 00:12

프러스텀 컬링 기법

Post by urin »

내용 삭제했습니다.
밑에 행인님의 리플과 같은 내용이니 참조하세요...
Last edited by urin on 2005-01-14 12:08, edited 4 times in total.
류광
Posts: 3805
Joined: 2001-07-25 09:00
Location: GPGstudy
Contact:

Post by 류광 »

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

시간 내서 찬찬히 읽어봐야겠습니다...
ducklmg
Posts: 155
Joined: 2004-11-08 16:46

관련 논문 참고

Post by ducklmg »

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

"Optimized View Frustum Culling Algorithms for Bounding Boxes"

구글님이 알고 계시네요.
난 너를 만나기 위해 이 세상에 태어났어
그러니 내 생활비는 네가 대 주어야만 해
urin
Posts: 19
Joined: 2004-11-13 00:12

내용 삭제했습니다.

Post by urin »

죄송합니다. 좋은 하루 되세요.
Last edited by urin on 2005-01-14 12:07, edited 1 time in total.
류광
Posts: 3805
Joined: 2001-07-25 09:00
Location: GPGstudy
Contact:

Post by 류광 »

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

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

오히려 자랑스러워 하셔도 될 것 같습니다. (물론 다음부터는 검색을 먼저 하는게 좋겠지만요...)
urin wrote: 근데 저 논문은 어떻게 보나요?
저 논문은 구글에서 검색하면 바로 나옵니다.
Last edited by 류광 on 2005-01-13 22:54, edited 1 time in total.
류광
Posts: 3805
Joined: 2001-07-25 09:00
Location: GPGstudy
Contact:

Post by 류광 »

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

Post by ducklmg »

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

논문의 기본적인 내용은 urin님이 생각하신 내용과 거의 흡사하구요
거기에 기타 다른 기법들이 추가된 것입니다.
난 너를 만나기 위해 이 세상에 태어났어
그러니 내 생활비는 네가 대 주어야만 해
행인
Posts: 62
Joined: 2004-05-25 22:30

re

Post by 행인 »

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

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

Code: Select all

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 = <P1.x-P0.x, 0, 0>
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 를 다음과 같이 계산합니다.

Code: Select all

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 도 다음과 같이 계산합니다.

Code: Select all

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이면 프러스텀 내에 완전히 들어간다고 보면 됩니다. 그외의 경우는 부분적으로 겹치는 경우가 됩니다.

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

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

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

Post by urin »

좋은 하루 되세요.
Last edited by urin on 2005-01-14 12:08, edited 2 times in total.
행인
Posts: 62
Joined: 2004-05-25 22:30

re

Post by 행인 »

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

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

글을 덧붙이면 보기 싫을 듯하여, 여기다 씁니다. 계산을 굳이 할필요가 없다는 말입니다. 위의 제가 적은 코드에서 보듯이, 비교하는 시점에서 평면의 노멀값의 부호를 따져주면 min, max를 저장할 필요가 없다는 뜻이였습니다. ^^ 다시봐도 완전히 동일합니다. P0는 min에, P1은 max에 해당하겠군요.
Last edited by 행인 on 2005-01-13 23:38, edited 1 time in total.
비회원

음..

Post by 비회원 »

정리해보면, 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
Posts: 19
Joined: 2004-11-13 00:12

테스트 결과

Post by urin »

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

안되는 경우가 너무 많은데 ㅡㅡㅋ

Post by 비회원 »

1. 중심점에서 사각형의 꼭지점 까지의 거리를 r로 하는 '구' 의 Crash처리는 바운딩 박스가 정육면체가 아니면 힘들다.

2. 바운딩 박스의 8개 점을 이용하는 방법은... 프러스텀이 바운딩 박스에 속해버릴 경우 처리가 안된다.

해결 방법이 없을까요 ㅡㅡㅋ
Locked