Systems for interactive visualization or virtual reality (VR) should maintain a suitable update rate for display according to users'' input. To satisfy this requirement of display performance, the rendering process of visualization systems should be executed within a fixed time, so it is a time critical process. In this thesis, we discuss an approach of scene culling that culls potentially invisible polygons from scene polygons composing a complex virtual environment, and then rendering the scene rapidly with only potentially visible polygons. The culling process mainly consists of two parts. The first part subdivides the viewpoint space into subspaces or cells, and precalculates potentially visible polygons for each cell before interactive visualization. The second part as one of processes for interactive visualization finds the cell where the viewpoint currently resides and fetches the potentially visible polygons that were precalculated for the cell. If the number of fetched polygons is too large to achieve the target display performance, then an additional culling is performed in realtime for the current viewpoint.
We propose a conservative visibility preprocessing method that is applicable to virtual environments modeled on outdoor scenes like city. The "conservative" word means finding potentially visible polygons or a superset of visible polygons from a three-dimensional space other than the exact set of visible polygons. The proposed method deals with invisible polygons jointly blocked by multiple occluders to compute a tight superset and enhance the culling result. In the proposed method, we express the four-dimensional information of area visibility onto two-dimensional spaces and keep it with a TSP (ternary space partitioning) tree. We perform the visibility test by constructing and traversing a TSP tree. In the proposed method, users can make a suitable tradeoff between the preprocessing time or memory usage and the culling result by restricting the number of TSP tree nodes to a suitable one.
We propose a real-time culling method using temporal coherence in visibility. In the proposed method, we avoid performing the culling process everyframe. Instead, as long as there is no possibility for any significant error to appear on rendered images, we rapidly render images for some frames only with the culling result at some old time and at some predicted time. By exploiting the saved time to perform the culling process incrementally for the future and permitting a little error on rendered images, we regulate the frame rate. Additionally, in the proposed method, any other culling method published so far can be used cooperatively to cull potentially invisible polygons for key viewpoints.
가상현실 응용이나 상호작용적 시각화 시스템의 경우, 사용자의 입력에 따른 화면 갱신에 있어 일정 수준 이상의 성능을 보장하여야 한다. 이러한 성능상의 요구 조건으로 인해 시각 시스템에 있어 렌더링 과정은 제한된 시간 내에 수행 되어져야 하는 시간 임계적인 과정이다. 본 논문은 다각형들로 구성된 가상세계를 렌더링하기 전에 보일 가능성이 없는 다각형들을 미리 제거하고, 보일 가능성이 있는 다각형들만을 추려내어 빠른 렌더링을 달성하고자 하는 컬링에 관하여 다루었다. 이러한 컬링(culling)과정은 크게 두부분으로 구성되게 된다. 첫 단계는 가시성 전처리 단계로서 주어진 가상 세계를 여러 개의 부공간(subspace) 혹은 셀(cell)들로 나누고, 각 셀들에서 보일 가능성이 있는 다각형들을 미리 구해 둔다. 그 다음 실시간 렌더링 단계에서는 현재 시점이 어느 셀에 머물고 있는 지를 계산하고, 이 셀을 위해 전처리 단계에서 미리 계산해둔 보일 가능성이 있는 다각형들을 가져온다. 만약 다각형들의 수가 주어진 화면 갱신 속도를 만족시키기에 너무 크면, 주어진 시점에 대하여 추가의 실시간 컬링이 행해진다. 본 논문에서는 도시와 같은 야외 환경을 모델링한 가상 세계에도 적용할 수 있는 포괄적 가시성 전처리 (conservative visibility preprocessing)방법을 제안하였다. 여기서 포괄적(conservative)이라는 말은 주어진 공간에서 보일 가능성이 있는 다각형들, 즉 보이는 다각형들을 포함하는 포함집합(superset)을 찾음을 의미한다. 제안한 방법은 좋은 컬링 효과를 위해서 여러 다각형들에 의해 공통으로 가려져 보이지 않는 다각형들까지 제거 하여 보다 작은 크기의(tight) 포함집합을 찾고자 하였다. 제안된 방법에서는 4차원의 가시성 정보를 2차원의 평면들 상에 나타내고, 이를 3진 공간분할 트리(ternary space partitioning tree)로 표현하였다. 3진 공간분할 트리의 구축과 탐색으로서 주어진 다각형들의 가시성 검사를 수행하였다. 사용자는 구축되는 3진 공간분할 트리의 노드 수에 적절한 제한을 가함으로써 전처리를 위해 요구되는 계산 시간 이나 기억장치 사용량과 계산 결과인 컬링 효과 사이에 적절한 선택을 할 수 있다. 본 논문에서는 가시성에 있어 시간적 응집성(temporal coherence)를 이용한 실시간 컬링 방법을 제안하였다. 제안된 방법은 화면 갱신을 위해 매 프레임 실시간 컬링을 수행하지 않고, 화면상에 큰 에러가 야기 되지 않는 한 과거의 컬링 결과와 다가올 미래의 시점에서의 컬링 결과만을 이용하여 빠르게 당분간의 영상을 생성하는 방법이다. 절약한 계산 시간을 미래를 위한 컬링 계산에 점층적으로 활용하고, 화면상에 있어 적절한 에러를 허용함으로써 사용자는 컬링 만으로 원하는 화면 갱신 속도를 유지할 수 있다. 또한 제안된 방법은 키 시점(key viewpoint)에서의 컬링 계산을 위해 실시간 컬링에 관한 다른 선행연구에서 제안한 방법을 함께 활용 할 수 있다.
