Visualization of very large terrain data in network environments is an important issue in GIS, computer games, and military applications. For real-time visualization, however, the problems due to the narrow bandwidth of the network and the limited computational power are to be solved. Although the previous algorithms based on a qaudtree structure can visualize terrain data in real-time, they require too large amount of data to be transmitted over the network. Therefore, we propose a real-time terrain visualization algorithm combined with wavelet-based compression. Our approach introduces a wavelet-based compression scheme having a multi-resolution structure to compress a large terrain data, thereby, handle it interactively. Also, for visualization, a surface mesh model is updated in real-time by using wavelet coefficients. To achieve this real-time mesh updating, a new mesh approximation method using restricted quadtree triangulation is designed on the basis of wavelet coefficients representing surface complexity. By combining the wavelet compression and wavelet-coefficient-based visualization techniques, the compressed data can be decoded and visualized interactively. Simulation results show the proposed algorithm can change the viewpoint and display very large terrain data in real-time with only several tens of kbits per second. Hence, the proposed algorithm is appropriate for the applications in network environments that usually have a limited narrow bandwidth and a low computational power.
네트워크를 통해서 대용량 지형 정보를 자유롭게 도시하는 문제는 지리정보시스템(GIS), 컴퓨터 게임 등 다양한 응용 분야에서 점점 더 중요한 이슈가 되고 있다. 특히, 대용량 데이터를 실시간으로 도시하기 위해서는 네트워크의 작은 대역폭과 사용자 컴퓨터의 제한된 계산능력 내에서 대용량의 지형 정보 데이터를 다룰 수 있어야 한다. 최근에는 대용량의 지형 정보를 실시간으로 도시할 수 있는 쿼드트리(quad-tree) 기반의 알고리즘들이 제안되어 왔지만, 도시 과정에서 네트워크를 통해서 전송해야 하는 데이터의 양이 너무 크다는 한계를 가지고 있다. 이러한 문제를 해결하기 위해, 이 논문에서는 웨이블릿(wavelet) 압축을 효과적으로 결합한 실시간 지형 정보 도시 알고리즘을 제안하였다.
먼저, 웨이블릿 계수를 이용하는 쿼드트리 기반의 삼각형 근사화 알고리즘을 제안하였다. 이 방법에서는 웨이블릿 계수로부터 역 변환을 통해서 지표면의 높이 데이터를 얻어내며, 각 웨이블릿 계수를 대응되는 지표면의 복잡도를 나타내는 척도로 직접 사용함으로써 삼각형 근사화를 수행하였다. 따라서, 삼각형 근사화에 필요한 데이터를 지형 정보의 웨이블릿 계수만으로 한정시킬 수 있다. 다음으로, 대용량 지형 정보를 효과적으로 압축하고 다룰 수 있도록, 기존의 압축 성능을 유지하며 다양한 특성들을 갖는 새로운 웨이블릿 압축 방법인 BHSPIHT 방법을 제안하였다. BHSPIHT는 블록 단위로 압축/복원하기 때문에 원하는 영역에 해당되는 압축 데이터에 자유롭게 접근할 수 있으며, 블록 계층구조를 통해서 제한 없는 다해상도 계층구조를 생성할 수 있어서 대용량 지형 정보를 다루는데 효과적이다. 또한, 각 블록의 압축된 비트열(bit-stream)이 해상도별로 점진적으로 압축되어 있어서, 필요한 해상도에 대응되는 비트열만 부분적으로 선택함으로써 전송되는 데이터를 크게 줄일 수 있다. 이렇게 제안된 웨이블릿 기반의 삼각형 근사화 알고리즘과 웨이블릿 기반의 압축 알고리즘을 효과적으로 결합하여, 압축된 비트열에서 대용량 지형 정보를 빠르고 자유롭게 도시할 수 있다. 마지막으로, 관찰자의 시점에 따라 상세도 레벨(LOD: level of detail) 조정이 가능한 지형 정보 도시 알고리즘을 구현하였다. 이 알고리즘에서는 지형 데이터를 블록 단위로 나누고, 화면에 보여지는 각 블록마다 시점으로부터의 거리에 따라 상세도 레벨을 결정한다. 각 블록마다 정해진 상세도 레벨에 따라서 필요한 비트열들을 서버로부터 가져오고, 앞서 제안한 삼각형 근사화 알고리즘을 이용하여 지표면 삼각형 모델을 서버에서 받은 비트열로부터 생성하게 된다.
제안된 웨이블릿 기반의 삼각형 근사화 알고리즘은 기존의 알고리즘과 비슷한 근사화 성능을 갖는 반면에, 요구되는 데이터는 절반 이하로 크게 줄일 수 있음을 실험 결과를 통해 검증하였다. 또한, 대용량 지형 데이터 위를 날아가는 실험을 통해서, 2GHz 펜티움4 CPU와 512MByte 메모리를 갖는 보통 PC 상에서 대용량 데이터를 실시간으로 도시할 수 있음을 보였다. 특히, 제안된 알고리즘의 높은 압축 성능으로 인해, 필요한 평균 데이터 전송률이 단지 수십kbps 수준으로 낮출 수 있음을 보였다. 이와 같이, 제안된 알고리즘이 작은 대역폭과 사용자 컴퓨터의 계산 능력 제한되는 네트워크 환경에 적합함을 확인하였다. 또한, 제안된 알고리즘이 수십 배의 압축률을 갖기 때문에, 지형 정보를 저장해두는 부담을 크게 줄일 수 있는 장점도 부가적으로 얻을 수 있다.
