프러스텀 컬링 기법
Moderator: 류광
-
- Posts: 19
- Joined: 2004-11-13 00:12
프러스텀 컬링 기법
내용 삭제했습니다.
밑에 행인님의 리플과 같은 내용이니 참조하세요...
밑에 행인님의 리플과 같은 내용이니 참조하세요...
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:
-
- Posts: 19
- Joined: 2004-11-13 00:12
-
- Posts: 3805
- Joined: 2001-07-25 09:00
- Location: GPGstudy
- Contact:
삭제할 필요 있을까요? 무엇보다도 그 논문은 영어이고 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:
아 그리고 참고로, 논문을 전문적으로 검색할 만한 곳으로 CiteSeer http://citeseer.ist.psu.edu/ 가 유명하구요. 또 얼마전에 구글이 논문 전문 검색 서비스 구글 스칼라 http://scholar.google.com/ 를 시작했습니다.
-
- Posts: 62
- Joined: 2004-05-25 22:30
re
안녕하세요.
좋은 글 감사합니다. 제가 쓰는 식이랑 똑같이 나오는거 같습니다. 확인해 보세요. 다만, 증명하는 과정이 약간 다르군요.
임의의 R, S, T를 기본축으로 하고, 크기도 R, S, T인 상자에 대해서, 한 평면 L= < N, D> 의 N방향에 대한 Effective radius는,
입니다. (왜 이렇게 되는지는 직선과 상자를 그려서 보시면 됩니다 ^^)
이제 이상자가 이 평면의 양의 쪽에 있는지, 음의 쪽에 있는지는 이 상자의 중심 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 를 다음과 같이 계산합니다.
이제, 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 도 다음과 같이 계산합니다.
앞의 1과는 체크하는 부호만 바뀌었습니다. checkvalue 가 0보다 크면 이 평면이 양의 쪽에 들어간다고 판단되므로, counter를 두어서 증가시키면 되겠습니다. 6개의 평면에대해서 모두 체크한 후에 counter가 6이면 프러스텀 내에 완전히 들어간다고 보면 됩니다. 그외의 경우는 부분적으로 겹치는 경우가 됩니다.
결과는 말씀하신것과 완전히 같습니다.
PS. 이방법이 최고는 아닙니다만, 간단해서 사용하고 있습니다. 그 논문인지는 모르겠으나 보면, 계산할 필요가 없을때도 따져주고 제법 복잡하게 따지던거 같습니다 그리고 이렇게 체크하는건 사각형이 길 경우 쥐약입니다.
좋은 글 감사합니다. 제가 쓰는 식이랑 똑같이 나오는거 같습니다. 확인해 보세요. 다만, 증명하는 과정이 약간 다르군요.
임의의 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
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
결과는 말씀하신것과 완전히 같습니다.
PS. 이방법이 최고는 아닙니다만, 간단해서 사용하고 있습니다. 그 논문인지는 모르겠으나 보면, 계산할 필요가 없을때도 따져주고 제법 복잡하게 따지던거 같습니다 그리고 이렇게 체크하는건 사각형이 길 경우 쥐약입니다.
-
- Posts: 19
- Joined: 2004-11-13 00:12
-
- Posts: 62
- Joined: 2004-05-25 22:30
re
같은 것으로 보입니다만 ^^
각 평면에 대해서 한번만 계산한다는 점이 똑같습니다. Min, Max 리스트는 저장해둘 필요는 굳이 없을거 같은데요?
PS. 그리고 이 쓰레드는 지우지 말았으면 합니다. 이 쓰레드에서 프러스텀 컬링에서 할수 있는 온갖 나쁜 짓을 다뤘으면 합니다.
글을 덧붙이면 보기 싫을 듯하여, 여기다 씁니다. 계산을 굳이 할필요가 없다는 말입니다. 위의 제가 적은 코드에서 보듯이, 비교하는 시점에서 평면의 노멀값의 부호를 따져주면 min, max를 저장할 필요가 없다는 뜻이였습니다. ^^ 다시봐도 완전히 동일합니다. P0는 min에, P1은 max에 해당하겠군요.
각 평면에 대해서 한번만 계산한다는 점이 똑같습니다. Min, Max 리스트는 저장해둘 필요는 굳이 없을거 같은데요?
PS. 그리고 이 쓰레드는 지우지 말았으면 합니다. 이 쓰레드에서 프러스텀 컬링에서 할수 있는 온갖 나쁜 짓을 다뤘으면 합니다.
글을 덧붙이면 보기 싫을 듯하여, 여기다 씁니다. 계산을 굳이 할필요가 없다는 말입니다. 위의 제가 적은 코드에서 보듯이, 비교하는 시점에서 평면의 노멀값의 부호를 따져주면 min, max를 저장할 필요가 없다는 뜻이였습니다. ^^ 다시봐도 완전히 동일합니다. P0는 min에, P1은 max에 해당하겠군요.
Last edited by 행인 on 2005-01-13 23:38, edited 1 time in total.
음..
정리해보면, 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 스타일입니다.)
결국은 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 스타일입니다.)
안되는 경우가 너무 많은데 ㅡㅡㅋ
1. 중심점에서 사각형의 꼭지점 까지의 거리를 r로 하는 '구' 의 Crash처리는 바운딩 박스가 정육면체가 아니면 힘들다.
2. 바운딩 박스의 8개 점을 이용하는 방법은... 프러스텀이 바운딩 박스에 속해버릴 경우 처리가 안된다.
해결 방법이 없을까요 ㅡㅡㅋ
2. 바운딩 박스의 8개 점을 이용하는 방법은... 프러스텀이 바운딩 박스에 속해버릴 경우 처리가 안된다.
해결 방법이 없을까요 ㅡㅡㅋ