All Right ?

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

[Chapter 4]

 레디오시티(radiosity)의 원래 아이디어는 Goral, Torrance, Battaile & Greenberg 이라는 작가들을 통해서 공식화 되었습니다. 그들은 분산 표면(diffuse surface)들 사이에 에너지가 이동되는 것을 시뮬레이션하는 레디오시티를 제안했습니다. 이 면들은 광택나는 면(shiny surfce)들과 달리, 모든 방향으로 같은 양의 빛을 반사합니다. 따라서 이 시뮬레이션의 결과는 관찰자 위치와는 상관없는 결과를 가져오고 이것은 면의 조도(illumination)가 어떤 각도에서 바라보던 간에 같다는 것을 의미합니다. 이것은 맵을 그리기 이전에 딱 한번만 계산하면 되기 때문에 3D게임에 매우 적합하다고 할 수 있습니다.

 우리는 아주 간단하게 레디오시티 알고리즘이 어떻게 작동하는지 살펴보고 BSP-tree가 어떻게 이 계산을 최적화하는지에 초점을 맞추겠습니다. 이 알고리즘에 대해 더 알고 싶다면 이 장에서 제안하는 관련 책들을 읽어보기를 권합니다.

 레디오시티 알고리즘은 씬의 조명이 부드럽고 자연스럽기 위해서 설계되었습니다. 우리가 만약에 각각의 빛들이 세계로 광선을 보내고 이것이 전혀 반사되지 않는 직선적인 조명모델을 사용한다면 그림자는 매우 날카로울 것이고 물체들은 매우 부자연스럽게 보일 것입니다. 레디오시티 알고리즘을 사용하기 위해서는 월드를 패치(patch)들로 나누어야 합니다. 패치라는 것은 월드의 작은 한 부분을 말합니다. 각각의 패치들은 초기 에너지 등급을 가지고 있습니다. 이 값은 대체로 광체나 반짝이는 벽들 같은 것과 달리 빛을 발산하지 않는다면 0일 것입니다.

 월드를 전체에 에너지를 배포시키는 방법은 여러가지가 있습니다. 우리는 반복적(iterative) 레디오시티라고 불리는 방법을 선택했습니다. 이것은 씬에서 보내지지 않은 에너지들 가운데 가장 높은 에너지 등급을 가지는 패치로 부터 에너지를 보내기 시작하고, 그 후에 이 패치의 에너지를 0으로 합니다. 이 과정을 어떤 특정 값 이상인 에너지를 가지는 패치가 존재하지 않을 때까지 반복합니다.

 패치i 로부터 다른 패치j로 에너지를 보낼때 다음과 같은 식이 사용됩니다.

<식- 원문 그림 참고>

위의 식에서 factor는 설명이 더 필요합니다.

<식- 원문 그림 참고>

 위에서 보는 바와 같이 씬에서 레디오시티의 계산은 매우 비쌉니다. 씬에서 패치의 개수를 N이라고 했을때 O(N^3)의 복잡도를 가집니다. 이는 씬에서 하나의 패치는 적어도 다른 모든 패치들에게 에너지를 보내야 함으로 씬의 모든 폴리곤들을 전부 체크하기 때문입니다.(또한 씬에서 패치의 개수가 폴리곤의 수보다 많다고 가정하는 것이 안전합니다.) factor의 한 부분인 H(가시성)는 계산하기에 가장 비싼 부분입니다. 바로 이 부분에서 BSP-tree의 힘이 발휘되는 것을 보여줄 수 있습니다.

- Radiosity in BSP-trees -

 실제 씬의 조명이 계산되기 전에 면들은 패치들로 분할되야만 합니다. 한가지 아이디어는 처음에 어느 정도의 크기를 갖는 패치들에서 시작하여 이 패치들의 에너지가 계산될 때 만약 패치 안에서 에너지의 변화량이 매우 크다면 작은 패치들로 분할하는 것입니다. 시간이 부족하기 때문에 우리는 이 아이디어는 무시했고 더욱 중요하다고 생각한 BSP-tree를 이용한 최적화를 생각했습니다.

 패치들을 생성하는 것은 매우 도전적인 문제라고 여겨지지만 이것은 BSP-tree와 상관없고 BSP-tree를 사용할 필요도 없으므로 이것에 대해서는 더 깊이 들어가지 않을 것입니다.
 
 레디오시티의 원래 아이디어는 각각의 빛 소스(light source)가 반드시 하나 이상의 패치들로 생각 되어져야 한다는 것입니다. 우리는 이것을 하는데 다른 방법을 선택했습니다. 각각의 빛 소스는 BSP-tree의 리프들에 저장됩니다. 그리고 첫번째로 각각의 빛이 그들의 에너지를 모든 패치들로 보냅니다. 이것이 끝나게 되면 레디오시티 계산은 끝나게 되고 씬은 보기 매우 좋게 될 것입니다. 그리고 조금 더 보기 좋게 만들기 위해서 우리는 progressive refinement라는 기법을 약간 수정해서 사용합니다. 매번 refinement를 반복할 때 마다 각각의 리프노드에서 가장 높은 에너지를 가지는 패치를 다른 모든 패치에게 에너지를 반사합니다. 이것은 강하게 빛을 받은 패치들로 부터 어두운 패치들에게 에너지가 퍼져나가는 결과를 가져옵니다. 실제로 완벽하게 어두운 것은 없는데 왜냐하면 모든 것이 빛을 어느 정도는 반사하기 때문입니다.

 레디오시티의 계산의 비싼 속성 때문에 우리는 이를 조금 더 최적화해야 할 필요가 있습니다. 에너지를 받아야만 하는 패치들을 선택할 때 BSP-tree 생성시 만들어진 PVS를 사용하여 쓸데없이 많은 계산들을 잘라낼 수 있습니다. 광선 추적(ray tracing)은 PVS를 계산할 때와 마찬가지 방법으로 할 수 있습니다. // factor의 한 부분인 H(가시성)를 계산하기 위해선 두 패치 사이에 광선 추적을해야 합니다. 이것이 PVS를 계산할때 이웃한 노드의 샘플 점들을 이용한 것과 같은 방법이라고 이야기 하는 것 같습니다. //

 에너지를 배포하는 우리의 알고리즘은 다음과 같습니다.

<RADIOSITY>

Complexity analysis:
 이것이 계산 비용에 진짜 킬러입니다. 최악의 경우 모든 광선은 씬에 있는 모든 폴리곤들과 체크되어야 합니다. 이 경우 트리의 있는 패치들의 개수가 N일때 O(N^3)의 복잡도를 가집니다. 다행스럽게도 대부분의 경우 우리가 했던 최적화들이 매운 많은 비용을 없앨겁니다. 하지만 얼만큼의 비용이 절약되는지 말하는 것은 거의 불가능한데 이는 트리의 구조에 따라 크게 다르기 때문입니다.

 이것으로 BSP-tree의 이점을 유용하게 쓰는 씬은 매우 빠른 라이팅이 가능합니다. 특히나 광선 추적하는 것을 매우 많이 줄여서 일을 완료할 수 있습니다. 왜냐하면 맵 디자이너가 언제든지 렌더링 결과가 충분히 좋아 보인다면 루프를 멈춤으로써 씬의 랜더링을 끝낼지 결정할 수 있기 때문입니다. 어떻게 렌더링이 진행되고 있는지 대략적으로 볼 수 있게 pre-render를 두세번씩 하는 것이 각각의 변화를 비싸게 한번에 모두 렌더링 하는 것 보다 매우 쉽습니다. 아래 스크린샷은 우리의 레디오시티 알고리즘으로 랜더링한 샘플입니다.

<Figure 15. Sample of Radiosity>

 위의 이미지는 우리의 방법으로 렌더링 되었습니다. 왼쪽 이미지는 렌더링 되기 전의 씬이고, 오른쪽은 카메라 앞 즈음에 있는 빛으로 렌더링된 씬입니다.

Related reading:
[Saykol, Ediz and Kirimer, Burak. Progressive Refinement of Radiosity]
[Teller, Seth. Application Challenges to Computational Geometry]
[Firebaugh, M. Three-Dimensional Graphics ? Realistic Rendering]
[Nettle, Paul. Radiosity in English]
[Nuydens, Tom. 3D Engine Column, Delphi3D]        

[Chapter 5]

- Summary of BSP-tree rendering -

 우리는 BSP엔진중에 미리 계산이 필요한 부분들에 대해 설명해왔습니다. 다음 알고리즘은 렌더링을 위해 씬을 BSP-tree로 만드는 알고리즘입니다.

- Complexity -

 RENDER-SCENE함수에서 불리는 함수들의 복잡도는 다음과 같습니다.

<표- 원문 그림 참고>

 전형적인 경우(Typical case)는 알고리즘이 일반적으로 걸리는 시간을 측정한 것입니다. 하지만 예전에도 언급했듯이 이것은 씬마다 매우 다릅니다. 복잡도에 가장 많은 영향을 미치는 것은 당연히 RADIOSITY이고 최악의 경우 씬을 렌더링하는데 O(n^3)의 복잡도를 갖게 만듭니다.