All Right ?

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

[Chapter 3]

- Background -

 게임 산업에서 보이지 않는 것을 제거해야 할 필요성은 계속 존재해 왔으며 앞으로도 계속해서 매우 크게 존재할 것입니다. 비록 그래픽카드가 엄청난 성능을 가지는 오늘날에도 이것은 여전히 사실입니다. 게임을 만들때 목표는 프레임율 입니다. 최소 사양의 시스템에서 30 frames/second 정도는 나와줘야 합니다. 몇 년 전만 해도 텍스쳐가 입혀진 5000개가 넘는 폴리곤을 프레임당 그려야 한다는 것은 매우 많은 양임을 의미했습니다. 오늘날에는 최적화된 조건에서 수백만 개의 폴리곤을 프레임당 그릴 수 있는 그래픽카드들이 시장에 나와있습니다. 그래도 은면을 제거할 필요성은 존재합니다. 왜일까요? 그것은 은면을 제거해서 남은 자원을 그려질 폴리곤에 쓸수 있기 때문입니다. 이것으로 씬을 보다 상세하게 표현할 수 있으며, 게임 비쥬얼을 보다 매력적으로 만들수 있게 됩니다. 문제는 어느 정도나 떨어진 폴리곤들을 제거해야 하는지 입니다. 은면을 제거하기 위해서는 절두체 선별(view frustum culling)과 포탈 렌더링(portal rendering)과 같은 무거운 계산들을 필요로 합니다. 게임에서 AI나 충돌 체크를 하는데 쓰여지게 될 CPU시간들이 위와 같은 계산들을 하기 위해서도 사용되게 됩니다. 따라서 은면을 제거하는 알고리즘을 개발하는 데에는 많은 노력을 필요로 합니다. 가려진 각각의 폴리곤들을 제거하는 게임은 거의 없습니다. 대부분의 게임들은 하나의 가려진 폴리곤의 집합(노드나 객체같은)을 제거하는 것으로 만족합니다. 이것은  폴리곤 하나 하나를 따지지 않으므로 가려진 부분을 제거할 때 약간 더 그려지는 한계를 가진 계산이나 이를 감수하는 것이 맞다는 것을 의미합니다.

 FPS 게임을 만들때 은면 제거를 위해서 쓰이는 가장 일반적인 기술은 포탈 렌더링 입니다. 이 기법이 BSP-tree를 필요로 하지 않지만 BSP-tree의 이점을 사용하기에 아주 적합합니다. 우리는 이것을 사용하기로 생각했지만 보다 정적으로 구상하는 것이 BSP-tree 렌더링을 더욱 빠르게 한다고 생각했습니다. 포탈 렌더링은 거울이나 감시 카메라와 같이 좋은 부수적인 효과를 가지지만 우리의 기법들과 함께 사용될 수는 없습니다. 반면에 우리 기법들은 런타임에서 아주 적은 계산만을 필요로 합니다. // 다시말해 포탈 랜더링 기법을 사용하지만 동적으로 구성하지 않기 때문에 포탈 렌더링이 가지는 여러 다른 이점들을 모두 활용할 수는 없다는 이야기 같습니다. //
 

- Portal Rendering -

 월드는 포탈(portal)들을 통해서 연결 되어진 섹터(sector)들로 표현될 수 있습니다. 섹터는 볼록(convex)하며 닫힌(closed) 폴리곤들의 집합입니다. 닫혀있다는 의미는 섹터 안에서 밖으로 선을 그을때 폴리곤을 만나지 않고는 불가능하다는 말입니다. 이것은 각각의 노드들의 빈틈은 포탈 폴리곤으로 채워져야 함을 의미합니다. 포탈 폴리곤들을 위치시키는 것은 수동이나 자동으로 할 수 있습니다. 이미 언급했듯이 하드웨어 가속 Z 버퍼로 인해서 섹터들이 볼록섹터(convex sector)일 필요성은 사라졌으므로 많은 게임 엔진에서 이 원칙은 생략하고 있습니다. 하지만 우리는 과거의 방식이 어떤 식이였는지 설명할 것입니다.

 포탈 렌더링의 기본적인 아이디어는 뷰어의 위치에서 절두체를 가지고 씬을 렌더링 할때 절두체가 포탈 폴리곤과 만나게 되면 포탈 폴리곤으로 절두체를 클립(clip)하는 것입니다. 그리고 나서 이웃한 섹터를 렌더링 할때 같은 뷰어의 위치를 기준으로 하지만 절두체는 이전에 클리핑되어 만들어진 새 절두체를 사용하게 됩니다. 이것은 매우 간단하고 재귀 함수에 적합한 접근입니다. 절두체가 정확히 뷰어가 볼 수 있는 공간으로 제한되기 때문에 많은 오브젝트들이 쉽게 선별될 수 있습니다. 아래 그림이 포탈 엔진에서 어떻게 절두체가 클립되는지 보여줍니다.

<Figure 10. View frustum clipping>

 위의 그림에서 뷰어의 위치는 V이고 최초의 절두체는 F1 입니다. F1이 포탈 폴리곤이 P1과 만나게 되면 클립되어 F2가 됩니다. 그후 F2가 P2,P3 포탈들을 만나서 클립되고 F3과 F4가 됩니다. 포탈 P4와 만나게 되면 F3은 깍여져서 F5가 되고 F4는 깍여져서 F6이 됩니다. 이 프로세스는 재귀함수에 적합합니다.

 포탈 렌더링 엔진에서 오브젝트를 선별하기 위해서, 사실 어떤 3D 엔진이라도, 이 프로세스를 보다 빠르게 처리하기 위한 단계들이 있습니다. 첫번째는 오브젝트의 경계구(bounding sphere)를 계산하는 것으로, 경계구라는 것은 오브젝트를 모두 포함하는 가장 작은 구를 뜻합니다. 최선으로 오브젝트 생성시 딱 한번만 경계구를 생성하게 하는 것입니다. 그리고 나서 절두체의 각 면들에 대해서 경계구를 테스트합니다. 경계구가 모든 면들에 대해서 음의 방향에 존재한다면 오브젝트는 보일수 없는 것이고 따라서 그려지지 않습니다. 아래 상황은 선별되어서 그려지지 않는 오브젝트와 이와 달리 그려지는 오브젝트를 보여주고 있습니다.

<Figure 11. Culling of objects>

 그림에서 오브젝트1은 절두체의 오른쪽 면을 기준으로 했을 때 양의 방향에 있지만 왼쪽 면을 기준으로 하면 음의 방향에 있으므로 선별됩니다. 반면에 오브젝트2는 왼쪽 면을 기준으로 완전히 양의 방향이고 오른쪽 면을 기준으로 하면 일부분 양의 방향이므로 선별되지 않습니다.

 포탈 엔진의 원래 아이디어는 폴리곤들을 클리핑하여 중복해서 그리지 않음으로써 보일 수 있는 지역만 그려지게 하는 것입니다. 오늘날에는 이런 방식은 굉장히 많은 CPU타임을 소모합니다. 하여튼 폴리곤이 씬을 그리는 재귀 함수 안에서 여러 번 나오게 되므로 우리는 이 폴리곤이 그려졌는지의 여부를 알 필요가 있습니다. 이것을 구현하는 좋은 방법은 폴리곤이 그려진 마지막 프레임을 가리키는 프레임 카운터를 폴리곤에 붙이는 것입니다. 그림10의 오른쪽 벽의 경우를 보면 절두체F5 와 F6안에서 그려져야 하고 이 폴리곤들은 이 프레임에서 그려졌는지 아닌지를 여부를 가져야 합니다. 그렇지 않다면 Z버퍼링에 오류가 발생합니다. // 과거 하드웨어 가속 Z버퍼링이 없었을때 포탈 렌더링을 이용하여 폴리곤을 선별시 Z버퍼링을 위하여 프레임 카운터 같은 것이 폴리곤마다 저장되어야 했다는 이야기 입니다. 물론 오늘날에는 전혀 쓸모없는 방식이지요. //

 포탈 엔진에서 렌더링을 수행하기 위해 우리는 절두체가 무엇으로 구성되는지 정의할 필요가 있습니다. 절두체는 n개의 면을 가지는 구조이고 각각의 면들의 법선 방향은 절두체 안쪽을 향하며 따라서 절두체 안은 닫혀진 공간이 됩니다. 아래 알고리즘은 한 폴리곤이 절두체 안에 있는지 없는지를 판단하는 것입니다. 여기서 우리는 하나의 면과 하나의 점을 취하는 CALSSIFY_POINT 함수를 사용합니다.

<INSIDE_FRUSTUM>

 포탈엔진의 렌더링 메인 함수는 다음과 같습니다.

<RENDER_PORTAL_ENGINE>

- Placing the portals -

 전에도 언급했듯이 포탈 엔진의 큰 문제들 중 하나는 포탈들을 위치 시키는 것입니다. 수동으로 포탈들을 위치시킨다면 맵 디자이너의 능력이 요구되어야함은 말할 것도 없이 시간이 매우 많이 걸리게 됩니다. 다른 여러가지 요소와 더불어 이 시간 역시 다른 곳에서 더 좋게 쓰여질 수 있습니다. 따라서 자동으로 포탈을 위치시키는 좋은 알고리즘이 필요합니다. 제 동료인 Andreas Brinck는 이 문제에 대해 좋은 답을 내놨습니다. 그의 답을 이용하려면 BSP-tree가 이용되야 합니다.

 기본 아이디어는 포탈이 반드시 트리를 나누는데 기준이 되었던 폴리곤들로 정의되는 면상에  있는 것입니다. 최초로 생성되는 포탈 폴리곤은 트리에 존재하는 전체 노드들을 포함하고 있는 바운딩 박스를 넘어서는 사각형 폴리곤(four-sided polygon)으로 초기화합니다. 그 다음에 각각의 포탈 폴리곤은 해당 노드의 서브 트리들로 타고 내려갑니다. 포탈 폴리곤이 서브 트리들중 하나의 노드를 통과하게 될때 그 노드에 있는 분할 기준 폴리곤으로 정의 되는 면이 있다면 이것으로 포탈 폴리곤을 클립합니다. 또한 포탈 폴리곤이 리프 노드에 도달하면 리프 노드에 있는 모든 폴리곤들로 클립 됩니다. 포탈 폴리곤이 클립되었다면 그 결과인 두 부분은 트리의 꼭대기로부터 다시 내려오게 됩니다. 만약 포탈 폴리곤이 클리핑 될 필요가 없다면 이 포탈 폴리곤은 현재 방문하고 있는 노드의 서브 트리들로 내려갑니다. 이것이 뜻하는 것은 클립된 부분이 기준 면의 양의 방향이라면 오른쪽 서브 트리로 내려가게 되고 음의 방향이라면 왼쪽 서브 트리로 내려가게 됩니다. 그러나 만약 기준 면과 동일면상에 있다면 양쪽 서브 트리로 모두 내려갑니다.

 트리에 모든 포탈들을 위치시키는 알고리즘을 정의하기 위해서 우리는 폴리곤을 어떻게 클립할 것인지 정의해야 합니다. 따라서 우리는 선과 면이 만나서 생기는 점을 리턴하는 INTERSECTION_POINT 함수가 있음을 가정합니다.

<CLIP_POLYGON>
 
 인제 우리는 BSP-tree안에 어떻게 포탈들을 분포시킬지 정의할 수 있습니다. 알고리즘은 트리의 루트 노드의 바운딩박스 보다 큰 포탈 폴리곤으로 시작합니다. 우리는 이 함수의 설계를 스웨덴의 DICE에서 일하는 게임 프로그래머 Andreas Brinck로 부터 얻었습니다. 

<PLACE_PORTALS>

// 아래 예제설명 내용을 보면 리프가 아닌 노드의 분할 기준면을 포탈 폴리곤으로 만든 후, 의사코드에서는 왼쪽 서브트리를 먼저 타게 되는데 오른쪽을 먼저 타야 할거 같습니다. //

Complexity analysis:

 이 함수는 분석하기가 매우 복잡하고 또한 설계 역시 우리 것이 아니기 때문에 분석하지 않겠습니다.

 의사코드 10번째 줄을 명확히 하려면 노드에 있는 포탈 폴리곤과 다른 폴리곤들 사이의 동일한 면 부분을 제거하는 것을 보여줄 필요가 있습니다. 다음 이미지를 보겠습니다.

<Figure 12. Removing coinciding parts>

 그림12에서 포탈 폴리곤은 리프노드에 왔습니다. 진한 회색으로 칠해진 1의 영역은 트리를 내려오는 동안 제거된 부분입니다. 밝은 회색의 2,3,4, 부분은 리프 노드의 폴리곤들과 동일한 면 상에 있기 때문에 제거됩니다. 따라서 5로 표시된 부분만이 포탈로 사용될 부분입니다. // 이 그림에서 방에 문(5번영역)이 하나 있다고 생각하시면 됩니다. 그럼 문으로 뚫린 부분만 포탈 폴리곤이 생성되어야 하겠지요. //

 앞 페이지의 알고리즘은 첫 눈에 보기엔 매우 복잡해 보이지만 사실 매우 단순하고 직관적이라고 할 수 있습니다. 끝으로 모든 포탈 폴리곤들은 각각 정확히 두 노드에 존재하게 됩니다. 서로를 볼 수 있는 포탈이 두개 존재 하는 것입니다. 다음 페이지에서 구현된 알고리즘의 예를 들겠습니다.

<Figure 13. An example map for automatic portal placement>

1. 포탈 폴리곤 1 (s1) 이 노드 n1에 들어갑니다. <원문 그림 참고>
 n1에서 포탈 폴리곤은 클리핑되어 맞게 조정되고 중간 부분은 n1 노드에 있는 폴리곤 하나와 동일한 면에 있으므로 제거되게 됩니다. 여기서 p1, p2 이름 지어진 두 포탈 폴리곤을 얻게 됩니다. 이 둘이 s1을 대신합니다.

2. p1 과 p2 가 노드 s2에 들어갑니다.
 노드 s2에서 p1은 s2의 양의 방향에 있기 때문에 기준이 되는 폴리곤 s2 와 함께 n2 노드로 들어가게 됩니다. p2는 s2의 음의 방향에 있기 때문에 s2와 함께 s3 노드로 내려가게 됩니다. s2를 가로지르지 않기 때문에 p1,p2를 클리핑할 필요가 없습니다.

3. p1 과 s2가 노드 n2에 들어갑니다. <원문 그림 참고>

 n2에서 p1 은 포탈로 받아들여집니다. 따라서 노드 n1에서도 바뀌지 않습니다. p3의 한 부분은 이 노드의 한폴리곤과 동일한 면에 있으므로 제거됩니다. 폴리곤 s2는 s3로 보내지며 이제 p3로 불립니다.

4. p2 와 p3가 노드 s3에 들어갑니다. 

// 원문은 p3와 s3가 노드 n3로 들어갑니다 인데 오타 같아서 수정 //
  노드s3에서 p2와 p3 둘다 클립되지 않으므로 s3와 함께 내려가게 됩니다. p3와 s3는 노드 n3으로 내려가게 되고 p2와 s3은 s4로 내려가게 됩니다.

5. p3 와 s3가 노드 n3에 들어갑니다. <원문 그림 참고> // 그림 : n2 -> n3 수정필요 //
 노드 n3에서 p3는 포탈로 받아들여지고 s3는 이전의 나왔던 이유들과 같은 이유로 일부분을 제거합니다. s3은 이제 p4로 불립니다.

7. p2,p4,s4가 노드 n4로 들어갑니다. <원문 그림 참고>
 p2와 p4 노드에 맞추기 위한 것 말고는 클리핑이 필요하지 않습니다. 그러나 s4는 완전이 한 폴리곤과 동일한 면이므로 제거됩니다.

8. n5 노드로 가는 것은 없습니다.
 이 노드는 포탈을 가지지 않으므로 어떤 노드들로 부터도 보여질수 없으며 다른 어떤 노드도 볼 수 없습니다.

9. 결과 <원문 그림 참고>
포탈 p1은 n1와 n2에 있습니다.
포탈 p2은 n1와 n4에 있습니다.
포탈 p3은 n2와 n3에 있습니다.
포탈 p4은 n3와 n4에 있습니다.

 이것이 상대적으로 좋은 프레임율을 제공하는 단순한 포탈 엔진을 구현하기 위한 전부입니다.

// 이 알고리즘이 직관적이라고 했지만 이해가 쉽지 않았습니다 . 예제 맵으로 차근차근 알고리즘을 따라가면서 생각해보시는게 설명만 보시는 것보다 좋을거 같습니다. //

- Our Solution -

 포탈 엔진은 몇 가지 좋은 특징을 가지고 있는 매우 탄력적인 구조입니다. 우리가 시스템을 설계하기 시작했을때 우리는 포탈 엔진으로 돌아가게 하려고 생각했지만 몇 가지 문제점들이 있었습니다. 바로 클리핑이 씬을 그리는 중에 일어 난다는 것이였습니다. 그래서 우리는 더 정적인 방법을 통해서 런타임에서 일어나는 비싼 계산을 피하기로 결정했습니다. 아이디어는 대부분 포탈 엔진과 비슷하지만 런타임시 그려질 필요가 있는 것들의 정보가 맵이 그려지기 전에 미리 계산된다는 점이 다릅니다. BSP-tree의 각각의 리프들은 Potentially Visible Set(PVS)를 생성하게 됩니다. PVS란 현재 리프에서 보여질 수 있는 리프들의 집합입니다. 이것은 렌더링 부분에서만 쓰이는 것이 아닙니다. 레디오시티를 계산할때나 네트워킹의 최적화에서도 쓰이게 됩니다.

 PVS는 맵이 그려지기 전에 미리 계산됩니다. 각각 리프에 보여질 가능성이 있는 리프들이 저장됩니다. 씬이 그려져야 할 때 카메라가 위치한 첫번째 리프가 그려지며 다음으로 그 리프의 PVS에 있는 리프들이 그려지게 됩니다. 이것은 당신이 중복된 그리기를 다룰 수 있는 어떤 종류의 알고리즘이 있음을 필요로 합니다. 전에 언급했듯이 오늘날의 그래픽카드는 하드웨어 가속 Z 버퍼를 지원하며 이것으로 충분합니다.

- Calculating the PVS -

 PVS를 계산하기 위해서는 리프 안에 어떤 점들이 다른 리프에서 보이는지를 알기 위하여 리프들 사이의 표준 광선 추적(standard ray tracing)이 필요합니다. 각각의 리프들은 약간의 샘플 점들을 가져야 하며 이것들 사이의 가시성이 추적되야만 합니다. 만약에 한 리프의 중앙에 놓여진 점이 다른 리프로 부터 온 시선에 보인다고 생각되려면, 그 시선은 반드시 리프의 입구를 통과해 와야 합니다. 다음 그림으로 이 점을 명확히 알 수 있습니다.

<Figure 14. Visibilyty between nodes>

 위 그림을 통해서 우리는 한점이 다른 노드에서 부터 보이려면 반드시 해당 노드의 입구를 통과해야 함을 명확히 알 수 있습니다. 이것은 매우 자명한데 왜냐하면 만약에 광선이 다른 어떤 곳을 통과하려 할때 막혀버리면 두 점사이의 가시성은 없기 때문입니다. 따라서 리프의 입구에 샘플 점들을 배치하는 것으로 충분합니다. 아래 설명하는 알고리즘은 BSP-tree에서 어떻게 샘플 점들을 배치하는지 나타냅니다. 이 함수를 위해서 우리는 노드에 점을 배치하기 위한 몇 가지 도우미 함수들이 필요합니다.

* DISTRIBUTE-POINTS (Node)
- 이 함수는 인자로 들어온 노드의 분할 면을 따라서 해당 노드의 바운딩 박스 범위 안에서 일정한 간격으로 점들을 배치합니다. 이 점들의 집합을 리턴합니다. Complexity: O(xy), x 는 바운딩 박스 안에서 분할면의 너비이며 y는 높이 입니다.

* CLEANUP-POINTS (Node, PointSet)
- 점들의 집합에서 이 노드의 폴리곤과 같은 면에 있거나 바운딩 박스의 바깥쪽에 있는 점들을 제거합니다. Complexity: O(np), n은 노드안에 폴리곤의 개수이며 p는 점집합이 가지는 점들의 개수입니다.

<DISTRIBUTE_SAMEPLE_POINTS>

// 위에서 어렵게 설명한 포탈 생성 알고리즘과 달리 기준 폴리곤으로 생성되는 면에 점들을 적당히 분포시키는 것은 이해가 쉽습니다. 이것도 포탈 이라는 개념으로 부를 수 있을지 잘 모르겠네요. //

Complexity analysis:
 이 함수는 재귀적으로 매번 호출마다 O(np + xy) 정도의 복잡도를 가집니다. ( DISTRIBUTE-POINTS, CLEANUP-POINTS  찹고) 완전한 복잡도를 구하기 위해 다음과 같은 식을 세울 수 있습니다. (우리는 점 집합이 양쪽 트리에 똑같이 분포됨을 가정합니다.)

T(n) = 2T(n/2) + O(np + xy)

Masters Theorem을 사용하면 θ(np + xy) 같은 복잡도를 얻게 됩니다.

 이 함수는 트리의 루트 노드와 비어있는 점 집합을 인자로 처음 호출 됩니다. 말하자면 다음과 같은 흐름입니다. 먼저 BSP-tree의 루트노드에 있는 나누기 기준 폴리곤으로 정의 되는 면 상에 점을 배치 합니다. 면은 무한하기 때문에 이것이 무한 개수의 점을 생성하게 됩니다. 그래서 점을 배치하는데 있어 제한이 있어야 합니다. 이 제한이 바로 루트 노드의 바운딩 박스입니다.

 그후 점들의 배치가 다 끝나면 양쪽 서브 트리로 내려가게 됩니다. 샘플 점들이 노드에 들어갈때 이들은 두 집합으로 나뉘어집니다. 한 집합은 노드의 분할 기준 면의 양의 방향에 있는 집합이고 나머지는 음의 방향에 있는 집합입니다. 면 상에 위치한 점들은 양쪽 집합에 모두 포함됩니다. 그리고 나서 이 노드의 바운딩 박스를 제한으로 분할 기준 면을 따라서 점들이 생성됩니다. 새롭게 생성된 점들은 양쪽 집합에 모두 포함됩니다. 이제 양의 방향의 점 집합은 오른쪽 서브 트리로 내려가고 음의 방향의 점 집합은 왼쪽 서브 트리로 내려갑니다. 이 프로세스가 점 집합이 리프에 도달할때 까지 반복됩니다. 이런 처리 이후에 리프 노드는 노드의 입구에 배치된 샘플 점들의 집합을 가지게 됩니다.

 만약 지금 단계에서 광선 추적을 시행한다면 아마 매우 많은 시간이 걸릴 것입니다. 하지만 만약 서로 연결된 리프들에 대해 알수 있다면 매우 쉬워질 것입니다. 왜냐하면 이것으로 어떤 리프들 사이의 추적은 생략시킬 수 있기 때문입니다. 서로 연결된 리프들을 찾는 것은 매우 쉽습니다. 단순히 서로의 샘플 점 집합을 비교하기만 하면 됩니다. 만약에 두 노드가 한개의 샘플 점이라도 공유한다면 서로 연결되었다고 할수 있는데, 왜냐하면 샘플 점 집합을 배치하는 와중에 점들은 2개의 리프에 속하거나 아니면 아예 속하지 않게 되기 때문입니다. 이제 우리는 서로 연결된 리프들을 알았으니 가시성 추적 알고리즘을 정의 할 수 있습니다. 하지만 일단 도우미 함수들을 정의할 필요가 있습니다.

 가시성을 추적하기 위해선 기본적으로 광선 추적을 해야할 필요가 있습니다. BSP-tree는 광선을 추적하기에 매우 좋은 구조입니다. 왜냐하면 아주 적은 비용으로 월드의 큰 부분을 무시할수 있기 때문입니다. 다음 함수의 집합이 우리의 해결책을 위해 필요한 것입니다.

* POLYGON-IS-HIT (Polygon, Ray)
- 광선이 폴리곤과 겹치는지 여부를 리턴합니다.

* RAY-INTERSECTS-SOMETHING-IN-TREE (Node, Ray)
- 광선이 해당 노드와 그 서브 트리 안의 어떤 것과 겹치는지 여부를 리턴합니다.

* INTERSECTS-SPHERE (Sphere, Ray)
- 광선이 구와 겹치는지 여부를 리턴합니다.

* CREATE-RAY (Point1, Point2)
- 두 점 사이의 광선을 리턴합니다.

 RAY-INTERSECTS-SOMETHING-IN-TREE 함수는 위의 함수들 중 가장 재밌는 함수입니다. 왜냐하면 이것은 BSP-tree의 장점들을 보여주기 때문입니다. 이것은 보통의 광선 추적이 어떻게 BSP-tree를 이용하여 최적화 되는지를 보여줍니다. 이 함수는 처음에 트리의 루트 노드를 인자로 하는 재귀 함수입니다. 알고리즘은 다음과 같습니다.

<RAY-INTERSECTS-SOMETHING-IN-TREE> 

// 이 의사코드는 다음과 같이 수정되야 합니다. //

RAY-INTERSECTS-SOMETHING-IN-TREE (Node, Ray)
{

    if(IS-LEAF(Node))

    {
        for each polygon P in Node
          if(POLYGON-IS-HIT (P, Ray))
              return true;

    }

    else

    {

        startSide = CLASSIFY-POINT(Ray.StartPoint, Node.Divider)
        endSide = CLASSIFY-POINT(Ray.EndPoint, Node.Divider)

        // If the ray spans the splitting plane of this node or if the ray is    
        // coinciding with the plane, send it down to both children

        if ((startSide = COINCIDING and endSide = COINCIDING) or
            startSide <> endSide and startSide <> COINCIDING and endSide <> COINCIDING)
        {
            if (RAY-INTERSECTS-SOMETHING-IN-TREE (Node.LeftChild, Ray))
                return true

            if (RAY-INTERSECTS-SOMETHING-IN-TREE (Node.RightChild, Ray))
                return true
        }

        // If the ray is only on the positive side of the splitting plane
        // send the ray down the right child. The or in the if statement is
        // because one of the points might be coinciding with the plane.

        // If the ray is only on the negative side of the splitting plane
        // send the ray down the right child. The or in the if statement is
        // because one of the points might be coinciding with the plane.

    // There was no intersection anywhere, pass that upwards
    return false

}

Complexity analysis:
 최악의 경우에 광선이 모든 노드를 방문하게 되고 이는 모든 폴리곤들과 비교됨을 의미합니다. 이것은 O(N)을 말하며 N은 트리에 있는 폴리곤의 개수입니다. 하지만 전형적으로 광선이 모든 노드들을 통과하지는 않으므로 비교되야 하는 폴리곤의 수는 줄어들 수 있습니다. 최선의 경우에 오직 하나의 노드만을 방문하게 되면 O(logN)이 되며 이것은 트리 구조에 영향을 받습니다.

<CHECK-VISIBILITY>

Complexity analysis:
 CHECK-VISIBILITY함수는 매우 비싸다고 할수 있습니다. 만약에 리프노드들 사이의 가시성이 없다면 node1의 모든 샘플 점들과 node2의 모든 샘플 점들을 체크해야만 합니다. 최악의 경우에 트리의 모든 폴리곤을 체크해야 하며 따라서 O(s1 s2 p)이라 하겠습니다. s1은 node1의 샘플 점들의 개수이고 s2는 node2의 샘플 점들의 개수이고 p는 트리의 모든 폴리곤의 개수 입니다. 일반적으로 이보다 낫게 O(s1 s2 Log p) 라고 할 수 있는데 이는 트리를 통과하는 광선에 체크가 필요한 폴리곤의 개수가 줄어들기 때문입니다.

<TRACE-VISIBILITY>

 이렇게 생성된 구조는 매 프레임마다 좋은 맵에서 많은 양의 폴리곤들을 무시할 수있습니다. 좋은 맵이라는 것은 가시성을 생각해서 만들어진 것으로 벽과 같이 시선을 막아주는 오브젝트들이 들어있음을 의미합니다. 만약에 맵이 많은 상세한 오브젝트들을 가진 커다란 하나의 방이라면 우리의 엔진으로는 어떤 폴리곤들도 제거되지 않습니다. 이런 나쁜 경우에서도 폴리곤들을 제거하기 위한 다른 기술이 있습니다. 이 기술은 level of detail (LOD) 이라고 불립니다. (Glossary 참고)

- Static Objects -

 하나의 박스 가운데에 구가 놓여진 맵을 생각해 봅시다. 우리가 이 맵으로 BSP-tree를 생성하려 할때 우리는 엄청난 양의 노드를 필요로 하게 되고 많은 폴리곤 분할이 일어나게 됩니다. 왜냐하면 각각의 리프 노드를 구성하는 폴리곤들은 구를 구성하는 각각의 폴리곤들일 것이기 때문입니다. 그래서 만약에 구가 200개 정도의 폴리곤으로 구성되게 되면 이렇게 간단한 씬이라도 200개 정도의 리프를 가지는 BSP-tree로 구성되게 됩니다. 이런 깊이를 (앞의 경우에 깊이는 약 200이 될 것이다.) 가지게 되면 분할과정에서 많은 폴리곤들이 새로 생성되는 것은 말할 것도 없이 런타임에서도 매우 방해의 요소가 됩니다. 따라서 이런 경우를 다룰 수 있는 무엇인가가 필요합니다.

 이 문제를 풀기 위해서 맵 디자이너는 맵의 기하학적 요소를 정의하는 오브젝트를 선택합니다. 위의 예제에서는 박스가 이런 오브젝트가 될 수 있습니다. 그리고 나머지 // 구와 같은 // 오브젝트들은 정적 오브젝트(static object) 로 분류합니다. 이런 정적 오브젝트들은 BSP-tree 생성이나 가시성 테스트시 사용되지 않습니다. 그러나 이들 오브젝트는 맵에 조명을 적용할 단계인 경우 그림자를 생성하게 됩니다. 이 정적 오브젝트들은 가시성 테스트가 끝난 BSP-tree에 추가됩니다. 이것은 정적 오브젝트를 이루는 각각의 폴리곤을 트리로 내려보냄으로써 행해집니다. 트리를 타고 내려가는 폴리곤들을 추가하는 방식은 밑의 알고리즘을 통해 설명할 수 있습니다. 다음과 같습니다.

<PUSH-POLYGON>

// 위 의사코드는 다음과 같은 수정이 필요합니다. //

if (Value = INFRONT or Value = SPANNING)

-> 수정한다.

if (Value = INFRONT or Value = COINCIDING)

 이 프로세스를 하고 나면 리프들은 더 이상 볼록집합(convex set)이 아닙니다. 이런 이유로 충돌 체크시 몇 가지 문제점이 있을 수 있습니다. 이것은 Physics in BSP-tree 장에서 다루도록 하겠습니다.

Related reading:
[Hoff III, Kenneth E. Faster 3D Game Graphics by Not Drawing What Is Not Seen]
[Tyberghein, Jorrit. The Portal Technique for Real-time 3D Engines]
[Bikker, Jacco. Building a 3D Portal Engine]
[Nuydens, Tom. 3D Engine Column, Delphi3D]
[Chalfin, Alex. Cells and Portals]
[Hoff, Kenny. The Warnock Area Subdivision Algorithm for Hidden Surface Removal]

번역 : 리안
블로그 : http://blog.naver.com/ryanii
MSN : ryanii@hotmail.com
[출처] [번역] BSP-tree 논문 : 3장|작성자 리안

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

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