It is one of the greatest challenges to improve rendering efficiency. An important issue in rendering is to develop a geometric data structure which provides efficient visibility operations, because the most of the rendering time is spent for performing them. In this thesis, we present new data structures, called {\it visibility layers},to efficiently handle the visibility operations originated from a given area light source.
Our structures maintain scene polygons in a sequence of layers according to their visibility from the source. The polygons in a layer do not obscure each other with respect to the source. From this property, a balanced 3D BSP tree can be constructed to accelerate visibility queries for the layer. Moreover, the shadow volumes cast by the polygons in the layer can be efficiently merged into a composite shadow volume. Since the shadow volume is a simple polyhedron, its boundary can be represented as a planar graph. The balanced BSP tree together with this graph allow ray coherence and output-sensitive clipping for fast visibility operations. We then generalize the visibility layers to accelerate visibility operations not originated from the source.
Finally, we explore the applications of the visibility layers to advanced rendering such as shadow generation with area light sources, ray tracing, radiosity and walkthrough. Our experiments indicate that the visibility layers greatly improve the efficiency of the rendering applications.
3차원 공간상에 기하적인 물체들이 주어져 있을 때, 이들에 대한 사실적인 영상을 생성하는 일련의 과정을 렌더링(rendering)이라고 한다. 광선추적법(ray tracing)이나 래디오시티(radiosity)와 같은 렌더링기법의 개발로 사진과 같은 수준의 매우 사실적인 영상을 생성하게 되었다. 그러나, 사실적인 영상을 생성하기 위해서는 기하급수적으로 많은 렌더링 시간이 필요하다는 단점이 있다. 이러한 문제를 해결하는 효율적인 렌더링 기술에 대한 연구가 집중적으로 진행되어 왔지만 아직은 주목할 만한 기술들이 개발되어 있지 않다. 렌더링의 비용이 많이 드는 이유는 시각적인 특성을 갖는 가시성(visibility) 연산들이 영상을 생성할 때 마다 기하급수적으로 많이 수행되는 다는 것이다. 사실적인 영상의 생성을 위해서는 광원, 반사, 그림자 등과 같은 여러 가지 광학 현상들을 고려해야 한다. 이효과를 영상에 잘 반영하기 위해서는 상당히 많은 기하하학적인 영산이 요구되는데 이들 대부분이 시각적인 특징을 포함하고 있다. 본 논문에서는 효율적으로 가시성 연산들을 처리할 수 있는 자료구조로서 가시 계층을 개발한다.
가시계층은 광원으로 부터의 가시성 연산들을 효율적으로 처리하기 위하여 다각형들을 그 광원에 대한 가시적인 관계에 따라서 여러 계층으로 분류하여 유지한다. 이때, 한 계층에 포함되는 다각형들은 서로를 가리지 않도록 한다. 즉, 광원 상의 한 점에서 출발하는 광선과 교차하는 다각형은 각 계층에 대해서 최대 한 개이다. 이러한 성질로 부터, 가시성 연산의 성능을 향상시키는 다음과 같은 두가지 자료구조를 효율적으로 구성할 수 있다. 첫째는 각 계층에 의해서 생성되는 그림자 영역이다. 이 그림자 영역은 볼록다면체이기 때문에 그 경계를 평면 그래프로 표현할수 있다. 두 번째는 광선 사격(ray-shooting)연산의 성능을 향상시키기 위한 3차원 균형 (balanced) 이진분할트리(binary space partition tree)이다. 평면 그래프와 이진분할트리는 광선들의 연과성(ray coherence)을 잘 반영하고 출력에 민감한(output-sensitive) 절단(clipping) 연산을 제공한다. 또한, 각 계층은 광원에 대해서 깊이 순으로 정렬되어있기 때문에 각 계층을 순차적으로 처리할 수 있다. 이처럼, 가시계층은 광원에 대한 가시성 연산들을 효율적으로 지원한다. 또한,특정한 광원으로 제한되어 있지 않은 일반적인 가시성 연산들을 지원하기 위하여 가시계층을 확장하는 방법을 제안한다.
가시계층은 다양한 렌더링 응용기법에서 요구하는 가시성연산들을 제공하기때문에 그 성능을 향상시킬 수 있다. 본 논문에서는 가시계층을 이용하여 그림자 생성, 광선추적법, 래디오시티, 원크스루(walkthrough) 등과 같은 렌더링 기법의 성능을 향상시키는 알고리즘을 개발하였다. 이들에 대한 실험을 통해서 많은 성능 향상이 있음을 보였다.
