All Right ?

BSP Trees and Polygon Removal in Real Time 3D Rendering
-Samuel Ranta-Eskola. 2001.1.19

[Abstract]

 BSP-tree는 원래 월드에 있는 폴리곤들을 정렬하기 위해 설계된 알고리즘입니다. 왜냐하면 당시 하드웨어 가속 Z 버퍼가 존재하지 않았고 소프트웨어 Z 버퍼링은 매우 느렸기 때문입니다. 오늘날에 이 용도로는 필요하지 않은데 왜냐하면 하드웨어 가속 z 버퍼가 존재하기 때문입니다. 그 대신에 매우 넓고 다양한 부분의 최적화에 사용되는데 예를 들자면 레디오시티 계산, 월드 드로잉, 충돌 체크, 네트워킹 부분등을 말할 수 있습니다.

 우리는 BSP-tree를 사용함으로써 많은 이점을 가질 수 있는 부분들에 대해 설명할 것이며 이것의 구현 프로세스도 알아 볼 것입니다.

결론적으로 말해 BSP-tree는 대부분의 게임엔진에 있어서 매우 유용합니다. BSP-tree가 정적이며 런타임에 수정하는 것이 매우 많은 비용을 필요로 하는 등의 단점들을 포함하고 있음에도 말입니다. 아마도 BSP-tree 알고리즘으로 부터 얻을 수 있는 몇 가지 아이디어들을 통해서 BSP-tree와 같은 이점을 가지는 보다 동적인 구조들을 개발 할 수도 있을 것입니다.

[Table of Contents]

1. Introduction
- Background
- Problem Statement

2. BSP-Trees
- Background
- The BSP algorithm

3. Hidden Surface Removal
- Background
- Portal Rendering
- Placing the Portals
- Our Solution
- Calculating the PVS
- Static Objects

4. Radiosity
- Background
- Radiosity in BSP-trees

5. Summary of BSP-Tree Rendering

6. Physics In BSP-Trees
- Future Position Calculation
- Collision Detection and Collision Handling

7. Network Optimization Using BSP-Trees

8. Future Work

9. Conclusions

10. Appendix

[Glossary]

FPS
- First person shooter, 적들을 없애는 것이 목적인 일인칭 시점의 게임.

MAP : 맵
- 월드의 다각형들을 가지는 객체.

Z-Value : Z 값
- 뷰어의 위치에서 부터 거리에 따라 분류하기 위해 쓰어지는 측정치.

Frame rate : 프레임율
- 매초마다 화면이 갱신되는 횟수. 모니터의 갱신율과는 아무 상관이 없음. 매 초 마다 월드가 그려지는 횟수. 보통 초당 30번의 갱신 이상이 되어야 연속적이라고 느낄 수 있음.

Pre-processing : 선수행, 미리 계산된
- 런타임 전에 계산이 미리 되어있는것. 따라서 런타임시 CPU타임을 다른 것들을 위해서 사용할 수 있음.

Polygon : 다각형
- 많은 수의 정점과 변들로 이루어진 도형. 삼각형,사각형,육가형,오각형등. 어떤 식이든 연결되어진 선으로 닫혀진 것은 다각형이라 할수 있음. 단 모든 정점들이 같은 면에 존재해야 함.

Plane equation : 면 다항식
- 3차원상의 면을 표현하는 다항식. Ax + By + Cz + D. A~D는 상수계수. A~C는 면의 법선벡터 값이고 D는 원점에서 부터 법선벡터 방향으로 면에 이르는 거리.

Node : 노드
- 트리의 부분. 각각의 노드는 왼쪽과 오른쪽의 sub-tree로 구성됨.

PVS
- Potentially Visible Set. 위치가 주어져 있을때 해당 지역으로 부터 보여질 가능성이 있는 objects/polygons/nodes의 집합.

Portal : 포탈
- 연결된 두 노드를 분할하는 공간, 또는 그려질 장면에 대한 거울(?).

Radiosity : 레디오시티
- 게임엔진에서 일반적으로 사용되는 조명모델. 주요 특징은 color-bledding으로 이웃한 벽으로 색깔을 번지게 하는 것.

Avatar : 아바타
- 가상세계의 플레이어를 대신하는 객체.

Client : 클라이언트, 사용자
- 다수의 유저들이 플레이하는 어플리케이션에서 서버에 연결된 유저.

Viewing frustum : 절두체
- 카메라를 위한 뷰 필드. 흔히 카메라를 꼭지점으로하는 피라미드로 여겨짐.

Target system : 최소 사양 시스템
- 게임이 실행될 수 있어야 하는 최소한의 시스템.

Scene : 씬
- 보는 위치와 각도에 따러 그려질 수 있는 이미지에 존재하는 객체들의 집합

LOD
- Level of Detail. 관찰자로 부터의 거리에 따라 상세함을 달리해서 그리는 기법. 씬에서 폴리곤의 개수를 줄이기 위해 사용. 관찰자에 가까울수록 보다 상세히 그려짐.

Bounding box : 경계 박스
- 어떤 객체(점, 다각형, 바운딩박스)의 집합을 모두 포함할 수 있는 최소의 박스. BSP-node의 바운딩 박스라고 이야기 할때는 node에 포함된 모든 폴리곤을 포함하는 최소의 박스를 의미.

[Chapter 1]

- Introduction -

 - Background -

- Problem Statement -

이 논문에선 다음과 같은 사항을 설명할 것입니다.

- BSP-tree란 무엇인가
- BSP-tree를 어떻게 생성하나
- 장점/단점
- 사용 가능한 비슷한 기술들
- BSP-tree의 유용성
- 기존의 방식과 우리 방식의 차이

 이 주제에 대한 연구는 스웨덴의 O3games라 불리는 회사에서 하였습니다.[http://www.o3games.com] 이 연구의 결과는 자매회사인 Cloop Systems의 상품을 개발하는데 사용되었습니다다. 우리는 BSP-tree와 관련된 모든 이점을 사용하게 구현하였습니다. 즉, BSP-tree의 이점을 적용할 수 있는 모든 부분에 대해 구현하였다는 말입니다. 우리의 논의를 뒷받침하기 위해서 우리가 썼던 코드들을 예제로 사용할 것입니다. C++형태의 의사코드를 사용 하였으며 이것이 명확하지 않을 경우 어디서 최적화가 되었는지 설명하기 위해서 알고리즘의 복잡도(complexity)를 분석할 것입니다. 대부분의 그림 예제들은 2D 기반이지만 3D상에 있는거와 같이 생각할 수 있습니다. 논문을 통틀어서 독자가 3D 관련 기본적인 수학과 벡터 대수에 지식을 가지고 있음을 전제로 합니다.

[Chapter 2]

- Background -

 * 폴리곤이 다른 어떤 폴리곤을 통과하게 되면 제대로 그려지지 않는다.
 * 이 알고리즘은 어렵고 또한 각 프레임마다 순서를 계산해야 하므로 비싸다.
 * 순환적으로 겹쳐진 폴리곤들의 경우 처리할 수가 없다.

<Figure 1. cyclic overlap>

- The BSP Algorithm -

<Figure 2. the difference between a convex set and a non-convex set>

 폴리곤의 집합이 볼록집합인지 아닌지 판단하는지에 대해 필요한 함수들은 다음과 같습니다.

<CLASSIFY_POINT>
<POLYGON_INFRONT>
<IS_CONVEX_SET>

 POLYGON_INFRONT 함수는 non-symmetric 비교입니다. 이 뜻은 폴리곤2가 폴리곤1의 앞에 있다고 해서 반드시 폴리곤1이 폴리곤2의 앞이 라고 할 수 없다는 것입니다. 다음 그림을 통해서 쉽게 아실수 있습니다.

<Figure 3. The non-symmetric nature of the comparison POLYGON_INFRONT>

 그림 3에서 폴리곤1은 폴리곤2의 앞에 있습니다. 왜냐하면 p3 과 p4 모두 폴리곤2의 양의 방향에 존재하기 때문입니다. 하지만 폴리곤2는 폴리곤1의 앞에 있지 않습니다. p2가 폴리곤1의 뒤에 있기 때문입니다.

 볼록집합의 필요에 대한 생각은 약간 수정이 가능한데 이것은 하드웨어 가속 Z 버퍼를 사용할 수 있을 때는 그렇게 민감하지 않기 때문입니다. 이 장의 마지막에 이 문제에 대해 언급하겠습니다.

 BSP-tree 정의에 필요한 구조체들은 다음과 같습니다.

<BSPTree>
<BSPTreeNode>
<BSPTreePolygon>

 위를 보면 알수 있듯이 폴리곤은 단순히 3개의 점으로 구성됩니다. 그 이유는 하드웨어인 그래픽카드가 삼각형을 그리도록 설계 되있기 때문입니다. 그러나 BSP-tree 를 생성하기 위한 알고리즘은 폴리곤이 몇 개의 점을 가지든지 상관없이 점들이 한 평면상에 존재하기만 한다면 적용할 수 있습니다.

 폴리곤 집합을 작은 부분 집합으로 나누는 방법은 여러가지가 있습니다. 예를 들어, 공간에 임의의 한 평면을 정의하여 이 평면에 양의 방향에 있는 폴리곤 집합을 오른쪽 트리로 넣고 음의 방향에 있는 폴리곤 집합을 왼쪽 트리로 넣을 수 있습니다. 문제는 이런 접급 방식으로는 왼쪽,오른쪽 트리의 사이즈를 거의 같게 나누는 평면을 찾기가 매우 힘듭니다. 왜냐면 공간에는 무한의 평면 집합이 존재하기 때문입니다. 따라서 일반적으로 쓰이는 방법은 공간에 있는 폴리곤중에 하나를 선택하여 이 폴리곤으로 정의 되는 면을 기준으로 폴리곤들을 나누는 것입니다.

 우리는 한 폴리곤이 다른 폴리곤의 앞에 있는지를 구별해주는 POLYGON_INFRONT 알고리즘을 정의했습니다. 이제는 한 폴리곤이 다른 폴리곤으로 정의되는 면을 분할하는지(spanning)의 여부도 판단할 수 있도록 이 알고리즘을 수정할 필요가 있습니다. 알고리즘은 다음과 같이 정의 될 수 있습니다.

<CALCULATE_SIDE>

 여기서 문제가 하나 생기는데 면을 분할하는 폴리곤일 경우 어떤 부분집합에 들어가야 하는지 선택해야 합니다. BSP-tree 알고리즘은 이럴 경우 폴리곤을 분할하여 두 개로 만들어 처리합니다. 이렇게 함으로써 Painter's 알고리즘이 가지고 있는 두 가지 문제점, 순환해서 겹쳐진 폴리곤 문제와 서로 교차하는 폴리곤 문제를 해결하게 됩니다. 다음 예제는 어떻게 폴리곤을 분할하는지 보여줍니다.

<Figure 4. Splitting a polygon>

 위의 그림에서 폴리곤1을 기준이 되는 폴리곤이며 폴리곤2를 분류대상이 되는 폴리곤입니다. 폴리곤2가 폴리곤1로 정의되는 면을 분할하므로 폴리곤2는 분할될 필요가 있습니다. 그 결과가 오른쪽 그림입니다. 이제 폴리곤2는 완전하게 폴리곤1에 앞에 있으며 폴리곤3은 완전하게 뒤에 있습니다. 폴리곤2와 폴리곤3의 미세한 여백은 단지 그림에서 두 폴리곤을 구분하기 위해 표시한 것입니다. 실제로 나누어진 후의 두 폴리곤은 맞닿아 있습니다.

<CHOOSE_DIVIDING_POLYGON>

Complexity analysis:
 while 루프 때문에 이 함수의 실행 범위를 찾는 것은 매우 어렵습니다. 씬의 구조에 따라서 while 루프가 많은 시간을 돌아갈지도 모릅니다. MINRELATIONSCALE 값은 수용할 수 있는 최소 상대치(MinRelation)가 한번의 반복마다 얼만큼 줄어드는지를 뜻하며, 따라서 최소 상대치가 최적의 답을 찾을수 있을 정도로 줄어드는데 어느 정도의 시간이 걸리는지 나타냅니다. // 여기서 상대치라는 표현은 트리의 균형성을 말합니다. 0부터 1사이의 값으로 1에 가까울 수록 보다 균형적이라는 뜻입니다. MINRELATIONSCALE 값이 크면 최소로 요구되는 균형성이 빨리 적어지므로 기준이되는 폴리곤을 보다 빨리 찾게 될 것입니다. //

 최악의 경우는 n개의 폴리곤 집합이 볼록집합이 아니면서 최적의 나눔이 한쪽은 1개의 폴리곤을 가지고 다른 한쪽은 n-1개의 폴리곤을 가지게 되는 경우입니다. 이런 경우는 최소 수용 가능 상대치가 1/(n-1) 보다 작을때 가능합니다. 이것은 의사코드의 27번째 라인에서 볼수 있듯이 i를 루프가 반복된 횟수라고 했을때 MinRelation/MINRELATIONSCALE^i < 1/(n-1)인 경우를 의미합니다. 만약에 최초의 MinRelation 값을 1이라고 했다면 (1은 균형성이 가장 좋은 값으로 MinRelation이 가질수 있는 최대값)

MinRelation/MINRELATIONSCALE^i < 1/(n-1)

1/MINRELATIONSCALE^i < 1/(n-1) // MinRelation = 1 //

(n-1)/MINRELATIONSCALE^i < 1    // 양변에 n-1 을 곱함 //

(n-1) < MINRELATIONSCALE^i       // 양변에 MINRELATIONSCALE^i 를 곱함 //

LogMINRELATIONSCALE(n-1)< i           // 양번에 LogMINRELATIONSCALE 취함 //

 여기서 i(루프 반복 횟수)의 최대값은 없습니다. 하지만 i의 값이 최소값에 매우 가까울 것이기 때문에 단순화하여 그 두 값이 같다고 생각할 수 있습니다. 또한 실제적으로 MINRELATIONSCALE값이 항상 2보다 크거나 같다고 가정하게 되면 다음과 같이 됩니다.

LogMINRELATIONSCALE n-1 = i , MINRELATIONSCALE >= 2

i = LogMINRELATIONSCALE(n-1) < Log(n-1) = O(LogN)

 while 루프안에서 폴리곤 집합에 대해 두 개의 반복문이 존재합니다. 이것으로 최악의 경우를 따져본다면 O(N^2 LogN)이지만 전형적으로 대부분의 경우 첫번째 반복에서 조건에 맞는 폴리곤이 발견되는 O(N^2)에 가깝습니다.

 CHOOSE_DIVIDING_POYGON에 있는 루프가 끝나지 않을 경우가 있을것 처럼 보일지도 모르겠습니다. 하지만 이것은 사실이 아닙니다. 왜냐하면 폴리곤 집합이 볼록집합이 아닐 경우에 두 가지 집합으로 나눌수 있는 폴리곤이 항상 한 개는 존재하기 때문입니다. CHOOSE_DIVIDING_POYGON은 폴리곤 분할 횟수가 가정 적은 폴리곤을 선택합니다. 여기서 집합을 전혀 나누지 않는 폴리곤 선택을 피하기 위해 나누어진 양쪽 트리 크기의 균형성을 나타내는 상대치(Relation) 값이 미리 정의된 최소 상대치(MinRelation) 값보다 반드시 커야만 하는 조건이 있습니다. 이것을 보다 잘 설명하기 위해서 가장 적은 수의 폴리곤 분할을 하는 기준 폴리곤을 선택하는데 무한 루프를 돌거 같은 예제를 들겠습니다.

<Figure 5. Problems when choosing dividing polygon>

 위의 예제에서 1,6,7,8폴리곤을 기준 폴리곤으로 선택하게 되면 어떤 폴리곤 분할도 하지 않습니다. 반면에 이 기준 폴리곤 이외의 모든 폴리곤들은 기준 폴리곤의 앞에 존재 하게 되며 다음 루프로 넘어가게 됩니다. 하지만 다음 루프에서 역시 1,6,7,8 폴리곤이 다시 선택되게 되어 무한 루프가 발생할 것 처럼 보일 수 있습니다. 사실 1,6,7,8 // 원래 1,2,3,4 인데 오타 같습니다. //폴리곤은 전체 폴리곤 집합을 가질 수 있는 최소볼록집합(convex hull)의 경계선 위에 있습니다. 이 폴리곤들은 기준 폴리곤이 될 수 없는데 왜냐하면 다른 모든 폴리곤들이 양의 방향쪽으로만 있기 때문입니다. 2,3,4,5 폴리곤들중에 기준 폴리곤을 선택하게 되면 한번의 폴리곤 분할이 일어나게 되지만 두 개의 보다 작은 집합들로 나눠지게 됩니다.

 또한 폴리곤 분할이 최소로 일어나는 폴리곤을 기준으로 잡는 것이 항상 좋은 선택이 될수 없는 이유는 대부분의 경우 비균형적인 트리를 만들기 때문입니다. 균형적인 트리가 비균형적인 것보다 런타임에서 보다 좋은 성능을 낼 것입니다.
 
 최적의 기준 폴리곤이 선택되면 남은 폴리곤들의 집합은 기준 폴리곤에 의하여 부분 집합으로 나누어지게 됩니다. 그리고 이 기준 폴리곤을 다루는 법은 두 가지가 있습니다.

1. 리프가 많은 트리가 생성될 수 있습니다. 이것이 의미하는 바는 모든 폴리곤들을 리프 노드들에 넣는 것으로 기준 폴리곤 역시 두 개의 트리중 한 쪽에 포함되게 합니다. 우리 예제에서는 기준 폴리곤을 양의 방향쪽에 있다고 정하여 양의 방향 트리에 포함 시킵니다.

2. 다른 방법으로 노드들의 내부에 기준 폴리곤을 저장합니다. 이 방식은 각각의 부분 집합에 대해서 볼록집합(convex set)이 될때까지 반복됩니다.

// 의사코드나 이어지는 그림 예제를 보면 위 두가지 방법 모두를 적용하고 있습니다. //

BSP-tree 를 생성하는 알고리즘은 다음과 같습니다.

<GENERATE_BSP_TREE>

Complexity analysis:
 CHOOSE_DIVIDING_POLYGON을 호출하는 것은 O(N^2 LogN) 정도의 Complexity를 가지게 되며, 이것이 재귀함수 호출 부분을 뺀 나머지 함수 부분을 좌우하게 됩니다. 만약에 우리가 폴리곤 집합을 나누는 것이 명확히 짝으로 떨어진다고 가정한다면 GENERATE_BSP_TREE 범위를 다음  같이 계산하여 식을 세울수 있게 됩니다.

T(n) = 2T(N/2) + O(N^2 LogN)

 Master's Theorem 을 사용하면 O(N^2 logN)을 얻을 수 있습니다. 여기서 N 은 폴리곤 집합 안에 있는 폴리곤들의 개수를 의미합니다.

 이어지는 예제는 BSP-tree가 어떻게 생성되는지 보여줍니다. 밑에 구조는 원래의 폴리곤 집합을 보여주며 예제 설명을 쉽게 하기 위해 각각의 폴리곤에 넘버링을 하였습니다. 이 폴리곤 집합이 분할되어 BSP-tree가 되는 것입니다.

<Figure 6. Example structure>

 알고리즘을 실행하기 위해서는 MINIMUMRELATION 과 MINRELATIONSCALE 상수들을 먼저 정해주어야 합니다. 우리는 이것을 각각 0.8과 2로 잡는 것이 매우 좋은 결과를 낳는 것을 발견했습니다. 그러나 다른 숫자들로 실험할 수도 있습니다. MINIMUMRELATION 값이 클수록 보다 좋은 균형의 트리가 생성되지만 폴리곤 분할 횟수가 증가하게 될 것 입니다.

 최초로 주어진 폴리곤 집합은 명확히 볼록집합이 아님을 알수 있고, 따라서 기준 폴리곤을 선택할 수 있습니다. 일단 훑어보게 되면 {1,2,6,22,28} 폴리곤들은 분할 기준이 될수 없음을 알 수 있습니다. 왜냐하면 최소볼록집합의 경계로 포함되기 때문입니다. 그러나 이들을 제외한 나머지 폴리곤들은 모두 기준 폴리곤 후보가 될 수 있습니다. 가장 폴리곤 분할을 적게 하면서 두 부분집합의 사이즈가 최대한 비슷하게 하는 폴리곤으로 16,17을 생각할 수 있습니다. 이들은 한 라인에 존재하며 어떤 폴리곤도 분할하지 않습니다. 또한 이 둘로 나누어진 두 집합의 크기는 음의 방향이 15개 양의 방향이 13개로 거의 같다고 할수 있습니다. 따라서 기준 폴리곤으로 16을 선택하겠습니다. 결과는 다음과 같습니다.

<Figure 7. The result of a split at polygon 16>

양쪽 부분 집합 모두 볼록집합이 아니므로 각각이 모두 새로운 분할 기준 폴리곤을 정해야 합니다.

 왼쪽 부분 집합의 경후 {1,2,6,7}이 최소볼록집합의 경계에 있으므로 기준이 될 수 없습니다. 4, 10 폴리곤의 경우 같은 선상에 있으며 어떤 폴리곤 분할도 하지 않습니다. 그리고 분할 결과 음의 방향이 7개 양의 방향이 8개로 매우 균형적입니다. 폴리곤4를 분할 기준으로 삼겠습니다.

 오른쪽의 경우 {16,17,22,23,28} 폴리곤도 위와 마찬가지로 기준이 될 수 없습니다. {18,19,27,26}은 어떤 폴리곤 분할도 하지 않으나 분할된 결과 음의 방향이 3, 양의 방향이 11로 3/11 의 상대치를 가지는데 이것은 최소 상대치보다 작기 때문에 기준이 될 수 없습니다. 따라서 보다 균형적인 결과를 제공하는 다른 폴리곤을 체크해보아야 합니다. {20,21,24,25}의 경우 한번의 폴리곤 분할이 일어나지만 폴리곤21로 분할했을때 가장 균형적인 결과를 가지게 됩니다. 폴리곤22를 한번 분할 시키고 나면 음의 방향이 6개, 양의 방향이 8개가 됩니다.다음 그림은 이 수행 결과를 보여줍니다.

<Figure 8. The second step>

 역시 어떤 부분 집합들도 볼록집합이 아니므로 각각의 부분 집합에 이와 같은 알고리즘이 적용되게 됩니다. 결과적으로 다음과 같은 트리가 생성됩니다.

<Figure 9. The final tree>

이것이 최적의 답이 아닐지라도 그것에 매우 가까우며 이것을 얻는데 오랜 시간을 필요로 하지 않습니다.

- Drawing the BSP-tree -

 자 인제 BSP-tree가 만들어 졌고 트리의 모든 폴리곤들을 빠짐없이 그리는 것은 매우 쉽습니다. 이어지는 알고리즘이 이것을 뜻합니다. 여기서 IS_LEAF라는 함수는 해당 BSP-node 가 리프일 경우 true 를 리턴하고 아니라면 false를 리턴한다고 가정합니다.

<DRAW_BSP_TREE>

// 의사코드에 렌더링 순서가 잘못됬습니다. front의 경우 left 를 먼저 behind의 경우 right를 먼저 그려야 올바르게 z 버퍼링이 됩니다. //

 이 방식으로 그릴 경우 스크린에 그려지는 폴리곤 숫자의 감소는 없습니다 때문에 수백 수천개의 폴리곤으로 이루어진 맵의 경우 이것이 좋은 답이 될 수 없습니다. // 단지 back to front 순서로 폴리곤을 그리는 알고리즘입니다. // 어떤 방법으로든 보여질 수 없는 노드들 혹은 보여질 수 없는 폴리곤들 까지도 무시 되어져야 합니다. 이것을 은면 제거(hidden surface removal)라고 합니다. 이것을 구현하는 방법은 여러가지가 있습니다. 다음 장에서 그것들에 대해 설명할 것입니다.

Related reading:
[Sunsted, Tod. 3D computer graphics:

 Moving from wire-frame drawings to solid, shaded models]
[Sobey, Anthony. Software Engineering]
[Southwick, Andrew R. Quake Rendering Tutorial]
[Meanie, Mr.. Binary Space Partitioning Trees]
[Royer, Dan. Dan’s Programming Tutorials]
[Feldman, Mark. Introduction to Binary Space Partioning Trees]

번역 : 리안
블로그 : http://blog.naver.com/ryanii
MSN : ryanii@hotmail.com

이 글과 관련있는 글을 자동검색한 결과입니다 [?]

• hurry up to me!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!111 by 참돔