KR100550127B1 - 3차원 라인의 근사 클리핑 방법 및 이를 이용한 3차원영상의 표시방법 - Google Patents

Abstract

3차원라인의 근사 클리핑으로 클리핑속도를 향상시키고, 낮은 성능의 모바일 기기에서도 3차원 지도 등의 3차원 영상을 화면에 표시할 수 있다.

투영중심위치를 기준으로 투영평면에 투영할 3차원 영상 내에서 3차원 라인을 구성하는 모든 노드들을 뷰 볼륨 안 또는 밖에 위치하는 노드로 판단하고, 노드들이 뷰 볼륨 안과 밖에 걸쳐져 있는 3차원라인을 뷰 볼륨 안의 노드들로 새로운 3차원라인으로 구성하는 것으로 뷰 볼륨 안에 위치하는 3차원라인의 노드의 개수를 탐색하여 탐색한 개수만큼 메모리의 영역을 할당하고, 뷰 볼륨 안에 위치하는 노드의 좌표 값을 메모리의 해당 영역에 저장하여 새로운 3차원라인을 구성하거나, 3차원라인을 노드들을 순차적으로 선택하여 뷰 볼륨 안에 위치하는 노드일 경우에 그 노드의 좌표 값을 메모리의 해당 영역에 저장하며, 뷰 볼륨 밖에 위치하는 노드일 경우에 그 노드가 3차원라인의 시작노드인지의 여부를 판단하여, 시작노드일 경우에 처음으로 뷰 볼륨 안에 위치하는 노드의 좌표 값을 메모리의 해당 영역에 저장하며, 시작노드가 아닐 경우에 상기 메모리에 저장한 바로 이전 노드의 좌표 값을 복사하여 메모리의 해당 영역에 저장한다.

3차원 지도, 3차원 영상, 근사 클리핑, 3차원라인, 투영평면, 네비게이션

Description

3차원 라인의 근사 클리핑 방법 및 이를 이용한 3차원 영상의 표시방법{Method for approximately clipping three dimensional line and method for displaying three dimensional image using the same}

도 1은 일반적인 3차원 그래픽스의 처리과정에 포함되어 있는 라인 클리핑을 설명하기 위한 도면.

도 2a 및 도 2b는 투영중심의 후방에 존재하는 데이터들에 대한 역투영 현상을 설명하기 위한 도면.

도 3은 3차원 지도의 표시에서 발생되는 출력 오류를 보인 도면.

도 4는 3차원라인클리핑 및 투영의 실제 개념을 설명하기 위한 도면.

도 5는 종래의 3차원라인 클리핑 방법을 설명하기 위한 도면.

도 6은 본 발명의 3차원라인 클리핑이 적용되는 네비게이션 시스템의 구성을 보인 블록도.

도 7a 내지 도 7c는 본 발명의 라인 클리핑 방법에 따라 라인 클리핑을 수행하면서 2차원 지도를 3차원 지도로 변환하여 화면에 표시하는 과정을 예로 들어 보인 신호흐름도.

도 8은 도 7b에서 새로운 3차원라인을 구축하는 일 실시 예를 보인 신호흐름도.

도 9a 및 도 9b는 도 8에서 새로운 3차원라인을 구축하는 과정을 설명하기 위한 도면.

도 10은 도 7b에서 새로운 3차원라인을 구축하는 다른 실시 예를 보인 신호흐름도.

도 11a 및 도 11b와, 도 12a 및 도 12b는 도 10에서 새로운 3차원라인을 구축하는 과정을 설명하기 위한 도면.

본 발명은 3차원 네비게이션 시스템이나 3차원 게임 등에 있어서, 3차원 지도 등과 같은 소정의 3차원 영상에서 노드와 링크의 구조를 가지는 3차원라인을 근사(近似) 클리핑하는 3차원라인의 근사 클리핑 방법과, 그 3차원라인의 근사 클리핑을 이용하여 소정의 3차원 영상의 3차원라인들을 근사 클리핑하면서 화면에 표시하는 3차원라인의 근사 클리핑을 이용한 3차원 영상의 표시방법에 관한 것이다.

보다 상세하게는 투영평면에 걸쳐져 있는 3차원라인들에 대하여 투영평면과의 교차점을 구하지 않고, 투영 중심위치와 투영평면의 사이에 형성한 클리핑 평면 안쪽에 위치하는 뷰 볼륨(view volume)내의 노드들만으로 새로운 구조의 3차원라인을 구성하는 3차원라인의 근사 클리핑 방법과, 그 3차원라인의 근사 클리핑을 이용하여 3차원 지도 등과 같은 소정의 3차원 영상의 3차원라인들을 근사 클리핑하고, 투영평면에의 투영하여 화면에 표시하는 3차원라인의 근사 클리핑을 이용한 3차원 영상의 표시방법에 관한 것이다.

일반적인 3차원 그래픽스의 처리과정 중에는 화면상에 표시되지 않는 3차원 영상을 제거하는 클리핑이 포함되어 있다. 상기 클리핑은 예를 들면, 도 1에 도시된 바와 같이 시점(view point)인 투영중심위치(100)에서 투영평면(110)에 뷰 볼륨(120)의 안쪽에 위치한 3차원 영상의 데이터들을 투영시키고, 뷰 볼륨의 경계면 바깥쪽 즉, 투영평면(110), 뷰 볼륨(120)의 상, 하, 좌, 우 및 후방의 여섯 면에서 바깥쪽에 위치하는 3차원 영상의 데이터들을 제거하는 것으로서 3차원 처리에 필요한 데이터의 양을 줄여 계산량을 줄이고, 처리속도를 향상시킬 수 있도록 하기 위한 것이다.

그리고 3차원라인을 투영평면에 투영할 경우에 3차원라인의 한쪽 끝이 될 수도 있는 투영중심위치의 후방에 존재하는 노드들은 기대와는 반대방향으로 역투영되므로 라인클리핑을 수행하여 제거해야 된다. 즉, 도 2a에 도시된 바와 같이 투영중심위치(200)에서 뷰 볼륨(210) 상의 3차원라인(220)을 투영평면(230)에 투영할 경우에 투영평면(230)에는 2차원 라인(240)으로 투영된다. 그러나, 도 2b에 도시된 바와 같이 투영중심위치(200)가 전진하여 3차원라인(220)의 일측 노드의 좌표(x, y, z)가 투영중심위치(200)의 후방에 위치하게 되면, 이 노드의 좌표(x, y, z)가 투영평면(120)의 무한 아래의 투영좌표(x_p, y_p)로 떨어져 투영평면(240)에는 실제와 상이한 2차원 라인(240a)으로 투영되는 오류가 발생하게 된다.

도 3은 이러한 오류가 발생되는 실제의 예를 보인 것으로서 화면에 표시되는 3차원 지도에서 도로 및 물줄기 등이 실제와는 상이하게 공중에 떠 있는 상태로 표시됨을 알 수 있다.

도 4는 3차원라인의 클리핑과 투영의 실제 개념을 설명하기 위한 도면으로서 투영평면(400)에서 3차원라인(410)을 클리핑하고, 투영중심위치(420)에서 투영평면(400)의 안쪽 즉, 뷰 볼륨의 내의 노드들만이 투영평면(400)에 투영되는 것을 보이고 있다. 여기서, 3차원라인(410)과 투영평면(400)이 교차되는 교차점의 계산과, 새로운 3차원라인의 구조를 위하여 메모리의 할당이 필요하다. 예를 들면, 원래, v0∼v4의 노드와 링크로 이루어진 3차원라인(410)에 대하여 투영평면(400)과의 교차점에 nv1, nv2 및 nv3을 더하고, 뷰 볼륨 밖의 v0 및 v3을 제거하여, nv1, v1, v2, nv2, nv3 및 v4의 5개의 노드로 이루어지는 새로운 구조의 3차원라인(410)으로 변경하는 것이다.

이러한 라인 클리핑에 있어서, 종래에는 6면 즉, 투영평면과, 뷰 볼륨의 상, 하, 좌, 우 및 후방의 6면에서 각기 라인 클리핑을 수행하였다. 예를 들면, 도 5에 도시된 바와 같이 v0, v1, v2, v3, v4, v5 및 v6 7개의 노드들로 이루어진 3차원라인(500)에 대하여 투영중심위치(510)를 기준으로 투영평면(520)과 뷰 볼륨(530)의 상, 하, 좌, 우 및 후면의 여섯 면에서 3차원라인(500)과의 교차점인 ve2, ve4 및 ve6을 계산하여 ve0(v0), ve1(v1), ve2, ve4, ve5(v5) 및 ve6로 이루어지는 새로운 구조의 3차원라인을 구성하였다.

그러나 상기한 종래의 기술은 3차원라인을 구성하는 각 노드들과 링크들을 순차적으로 탐색하면서 뷰 볼륨의 6개의 경계 면에서 교차되는지의 여부를 판단하 고, 교차될 경우에 교차점을 계산해야 되며, 새로운 노드 및 링크로 이루어지는 3차원라인의 구조체를 저장하기 위하여 메모리를 재할당해야 되는 등의 복잡한 과정을 수행해야 되어 처리속도가 매우 느리고, 이로 인하여 이동통신 단말기 등과 같이 낮은 성능의 모바일 기기에서 3차원 지도 등과 같은 3차원 영상을 표시할 수 없는 문제점이 있었다.

본 발명의 목적은 3차원라인을 근사 클리핑하여 클리핑속도를 향상시키고, 효율적으로 수행할 수 있는 3차원라인의 근사 클리핑 방법 및 이를 이용한 3차원 영상의 표시방법을 제공하는데 있다.

본 발명의 다른 목적은 이동통신 단말기 등과 같이 낮은 성능의 모바일 기기에서도 3차원 지도 등과 같은 3차원 영상을 화면에 표시할 수 있는 3차원라인의 근사 클리핑 방법 및 이를 이용한 3차원 영상의 표시방법을 제공하는데 있다.

이러한 목적을 가지는 본 발명의 3차원라인의 근사 클리핑 방법 및 이를 이용한 3차원 영상의 표시방법은, 3차원라인을 클리핑할 경우에 투영평면에 교차되는 3차원라인들과 투영평면과의 교차점을 구하여 투영평면에의 투영을 위한 새로운 구조의 3차원라인을 생성하지 않고, 투영중심위치와 투영평면의 사이에 클리핑평면을 형성하고, 그 클리핑 평면의 안쪽인 뷰 볼륨 안쪽의 노드들만을 연결하여 새로운 구조의 3차원라인을 형성한 후 투영평면에 투영하여 화면에 표시함으로써 3차원라인의 근사 클리핑에 따라 발생되는 에러 부분이 투영평면과 클리핑평면의 사이에 위치되어 화면에는 근사 클리핑에 따른 에러부분이 표시되지 않도록 하는 것이다.

본 발명의 제 1 특징에 따르면, 노드와 링크로 구성된 일반적인 구조의 3차원라인을 입력하여 사용한다.

본 발명의 제 2 특징에 따르면, 2차원 지도데이터를 로딩하거나 또는 미리 3차원 모델링된 데이터를 로딩할 경우에 1차 클리핑을 수행하고, 투영변환을 수행하기 전에 2차 클리핑을 수행한다.

본 발명의 제 3 특징에 따르면, 상기 1차 클리핑은 2차원 지도데이터 또는 3차원 모델링된 데이터를 로딩할 경우에 투영중심위치를 기준으로 주변의 2차원 지도데이터 또는 3차원 모델링된 데이터만을 로딩하는 것으로 실행된다. 즉, 투영평면에 투영할 소정 영역의 데이터만을 로딩함으로써 메모리 사용의 효율을 높이는 간접적인 1차 클리핑이 이루어진다.

본 발명의 제 4 특징에 따르면, 상기 2차 클리핑은 3차원 라인을 이루는 구성 요소들 중에서 투영평면과 투영중심위치의 후방에 위치하는 있는 라인 및 노드를 제거하는 것으로서 투영중심위치와 투영평면의 사이에 투영평면과 평행한 임의의 평면을 정하여 클리핑 평면으로 규정하고, 이 클리핑 평면에서 직접적인 클리핑을 수행한다. 여기서, 클리핑 평면의 바깥쪽을 뷰 볼륨 밖이라고 하고, 클리핑 평면의 안쪽을 뷰 볼륨 안이라고 한다.

본 발명의 제 5 특징에 따르면, 상기 제 4 특징에서의 2차 클리핑은 투영평면에 걸쳐져 있는 3차원 라인들에 대하여 실시하는 것으로서 3차원 라인을 구성하는 모든 노드들이 뷰 볼륨 밖에 있으면 모두 제거하며, 모든 노드가 뷰 볼륨 안에 있으면, 그대로 투영평면에 투영한다.

본 발명의 제 6 특징에 따르면, 상기 2차 클리핑 과정에서 투영평면에 걸쳐져 있는 3차원라인에 대해서는 3차원 라인과 투영평면이 교차되는 교차점들을 구하는 일반적인 클리핑을 수행하지 않고, 3차원 라인을 구성하는 노드들 중에서 뷰 볼륨 안의 노드들만으로 이루어지는 새로운 구조의 3차원라인을 구성한다. 이렇게 함으로써 뷰 볼륨 경계의 6개면에서 3차원라인이 교차되는지의 여부를 판단하고, 교차될 경우에 교차점을 계산해야 되는 복잡한 과정을 생략함으로써 3차원라인에 대한 클리핑의 처리속도를 향상시킬 수 있다.

본 발명의 제 7 특징에 따르면, 새로운 구조의 3차원라인을 구성하기 위하여 3차원라인에서 뷰 볼륨 안에 위치하는 노드의 수로 메모리를 할당하거나 또는 3차원라인의 모드를 저장할 메모리의 구조를 변경하지 않고, 뷰 볼륨 밖의 노드들의 좌표 값으로 뷰 볼륨 안의 인접위치에 위치하는 노드의 좌표 값을 복사하여 설정하는 방법을 사용한다.

본 발명의 제 8 특징에 따르면, 상기 제 7 특징에서 뷰 볼륨 안에 위치하는 노드의 수로 메모리를 할당할 경우에 3차원 라인의 노드들을 순차적으로 탐색하면서 뷰 볼륨 안에 위치하는 노드만으로 이루어지는 새로운 구조의 3차원라인을 구성하고, 그 새로운 구조의 3차원라인을 투영평면에 투영하여 2차원으로 변환한 후 화면에 표시한다.

본 발명의 제 9 특징에 따르면, 상기 제 7 특징에서 뷰 볼륨 밖의 노드들의 좌표 값을 뷰 볼륨 안의 인접위치에 위치하는 노드의 좌표 값으로 복사하는 것은, 3차원라인의 노드들을 순차적으로 탐색하면서 뷰 볼륨 밖의 노드들을 골라내고, 그 뷰 볼륨 밖의 노드들의 좌표 값으로 이전의 뷰 볼륨 안에 위치하는 노드의 좌표 값을 복사함으로써 메모리의 구조를 변경하거나 재 할당하지 않고, 간단하고, 빠른 속도로 3차원 라인을 재구성한다.

본 발명의 제 10 특징에 따르면, 상기 제 9 특징에서 3차원라인의 시작 노드가 뷰 볼륨 밖에 위치할 경우에 3차원라인의 노드들 중에서 최초로 뷰 볼륨 안에 위치하는 노드를 찾고, 그 최초로 뷰 볼륨 안에 위치하는 노드의 좌표값을 이전의 노드의 좌표 값으로 복사하여 새로운 구조의 3차원라인을 구성한다.

본 발명의 제 11 특징에 따르면, 본 발명에 따라 3차원라인을 근사 클리핑함에 따라 약간의 클리핑 오류가 발생할 수 있고, 이 오류는 화면에 표시할 경우에 화면의 하단부에 나타나게 되는 것으로서 상기 클리핑 평면을 투영중심위치에 가깝게 형성하여 투영평면과는 멀어지게 함으로써 3차원 영상을 투영평면에 투영하여 화면에 표시할 경우에 오류부분이 표시되지 않도록 한다.

이러한 본 발명에 따르면, 3차원영상을 처리하여 화면에 표시할 경우에 계산량을 현격하게 감소시키고, 계산속도가 빨라 이동통신 단말기 등과 같이 낮은 성능의 모바일 기기에서 3차원 지도 등과 같은 3차원 영상을 표시할 수 있다.

이하, 첨부된 도 6 내지 도 12의 도면을 참조하여 본 발명의 3차원라인의 근사 클리핑 방법 및 이를 이용한 3차원 영상의 표시방법을 상세히 설명한다.

도 6은 본 발명의 라인 클리핑 방법이 적용되는 네비게이션 시스템의 구성을 예로 들어 보인 블록도이다. 이에 도시된 바와 같이 3개 이상의 GPS 위성(600)이 송신하는 위치 데이터를 수신하는 GPS 수신부(610)와, 2차원 지도 데이터를 미리 저장하고 있는 지도 저장부(620)와, 사용자의 조작에 따른 명령을 입력받는 명령 입력부(630)와, 상기 GPS 수신부(610)가 수신한 위치 데이터로 이동체의 현재위치를 판단하고 판단한 현재위치를 기준으로 상기 지도 저장부(620)로부터 소정 지역의 2차원 지도 데이터를 독출하며, 독출한 2차원 지도로 3차원 지도를 생성하여 표시하면서 이동체의 주행경로를 안내하는 제어부(640)와, 상기 제어부(640)의 제어에 따라 3차원 지도와 함께 이동체의 현재위치 및 주행경로 등을 표시패널(660)에 표시하는 표시 구동부(650)로 구성된다.

이러한 구성을 가지는 네비게이션 시스템은 복수의 GPS 위성(600)이 위치 데이터를 송신하고, 그 송신하는 위치 데이터를 GPS 수신부(610)가 수신하여 제어부(640)로 입력시킨다.

네비게이션 시스템의 제어부(640)는 이동체가 주행할 경우에 GPS 수신부(610)로부터 입력되는 위치 데이터로 이동체의 현재위치를 판단하고, 판단한 이동체의 현재위치를 기준으로 하여 소정 지역의 2차원 지도를 지도 저장부(620)에서 독출한다. 그리고 제어부(640)는 상기 독출한 2차원 지도를 이용하여 본 발명의 라인 클리핑 방법에 따라 라인을 클리핑하면서 3차원 지도를 생성하고, 생성한 3차원 지도를 표시 구동부(650)로 출력하여 표시패널(660)에 3차원 지도를 표시하며, 그 표시한 3차원 지도에 상기 판단한 이동체의 현재위치를 화살표 등으로 함께 표시하면서 이동체의 주행을 안내한다.

여기서, 상기 네비게이션 시스템은 이동체에 고정 설치된 것을 예로 들어 설 명한 것으로서 모바일용 기기에 설치될 경우에는 지도 저장부(620)의 저장 용량이 한계가 있으므로 명령 입력부(630)의 명령에 따라, 지도를 제공하는 지도 제공용 서버에 접속하여 소정 영역 예를 들면, 서울특별시 전역의 2차원 지도를 다운로드받고, 그 다운로드받은 2차원 지도를 지도 저장부(620)에 저장한 후 사용할 수도 있다.

도 7a 내지 도 7c는 본 발명의 라인 클리핑 방법에 따라 상기 제어부(640)가 라인 클리핑을 수행하면서 2차원 지도를 3차원 지도로 변환하여 화면에 표시하는 과정을 예로 들어 보인 신호흐름도이다. 도 7a에 도시된 바와 같이 단계(700)에서 제어부(640)는 3차원 지도를 생성할 기준위치 좌표를 입력한다. 여기서, 상기 기준위치 좌표는, GPS 수신부(610)의 수신신호로 검출한 이동체의 현재 위치를 기준위치 좌표로 입력할 수 있고, 또는 사용자가 명령 입력부(630) 등을 통해 입력하는 좌표를 기준위치 좌표로 입력할 수 있다.

상기 단계(700)에서 기준위치 좌표의 입력이 완료되면, 제어부(640)는 단계(710)에서 3차원 지도 또는 3차원 모델들을 표시패널(660)의 화면에 표시하기 위한 3차원 환경 초기화 과정을 수행한다. 상기 단계(710)에서의 3차원 환경 초기화 과정은, 단계(711)에서 라이팅 환경을 초기화한다. 상기 단계(711)의 라이팅 환경 초기화는, 시점(view point), 시선, 광원의 방향, 광원의 세기 및 건물들의 각 면의 각도 등에 따라 건물 각 면을 표시할 색상 및 농도 등을 설정한다. 다음 단계(712)에서는 깊이 버퍼를 초기화 즉, 시점으로부터 소정의 표시 대상물이 표시되는 위치까지의 거리를 나타내는 깊이버퍼를 초기화하고, 단계(713)에서 화면의 바탕색을 클리어하여 소정의 색상으로 설정한다.

상기 단계(710)의 3차원 환경 초기화 과정이 완료되면, 단계(720)에서 시점 설정과정을 수행한다. 상기 단계(720)의 시점 설정과정은, 단계(721)에서 시점의 위치를 설정한다. 상기 시점의 위치 설정은 예를 들면, 상기 입력한 기준위치 좌표의 위치를 기준으로 미리 설정된 소정의 높이 위치를 시점으로 설정한다. 다음 단계(722)에서는 상기 설정한 시점의 위치로부터 3차원 지도 또는 3차원 모델을 바라보는 방향인 시선을 설정한다.

상기 단계(720)에서의 시점 설정과정이 완료되면, 제어부(640)는 단계(730)에서 3차원 좌표를 투영 평면에 투영하여 투영 변환할 투영 파라미터를 설정한다.

그리고 상기한 단계(710)의 3차원 환경의 초기화 과정, 단계(720)의 시점설정과정 및 단계(730)의 투영 파라미터 설정동작을 순차적으로 수행함과 동시에 제어부(640)는 단계(740)에서 3차원 지도로 변환할 2차원 지도 데이터를 지도 저장부(620)로부터 로딩한다. 여기서, 상기 2차원 지도데이터의 로딩은 상기 단계(700)에서 입력한 현재위치좌표를 기준으로 하여 그 부근의 지도 도엽만을 지도 저장부(620)로부터 로딩함으로써 1차 클리핑이 이루어지게 한다.

다음 단계(750)에서는 상기 로딩한 2차원 지도의 데이터를 3차원으로 모델링하는 3차원 모델링 과정을 수행한다. 상기 단계(750)에서의 3차원 모델링 과정은, 단계(751)에서 예를 들면, 로딩한 2차원 지도의 데이터에서 3차원 바닥면의 지도를 생성 예를 들면, 도로, 녹지, 강 및 호수 등의 라인을 설정하고, 단계(752)에서 각 건물들의 노드의 높이를 설정하며, 단계(753)에서 상기 설정한 높이로 각 건물들을 생성한 후, 단계(754)에서 이동체의 주행정보의 궤적을 화살표 또는 점선 등으로 생성한다.

여기서, 상기 단계(740)에서의 2차원 지도 데이터의 로딩과, 단계(750)의 3차원 모델링 과정은 네비게이션 시스템에서 3차원 지도를 3차원 지도를 변환하여 표시할 경우를 예로 들어 설명한 것이다. 그러나 3차원 영상을 표시하는 게임 등에서는 미리 3차원 모델이 저장수단에 저장되어 있으므로 상기한 단계(740)에서의 2차원 지도 데이터의 로딩과, 단계(750)의 3차원 모델링 과정을 수행하지 않고, 저장수단으로부터 상기 기준위치의 좌표를 기준으로 소정 영역의 3차원 모델을 직접 로딩할 수 있다.

다음 단계(760)에서 제어부(640)는 시점 변환과정을 수행한다. 상기 단계(760)의 시점 변환과정은, 상기 3차원 모델링 과정에서 3차원으로 확장된 모델의 노드들의 3차원 좌표에 대하여 시점을 기준으로 3차원 이동 및 3차원 회전을 수행하여 시점을 기준으로 하는 시점 기준의 좌표계로 변환한다.

상기 단계(760)에서의 시점 변환과정의 수행이 완료되면, 제어부(640)는 도 7b에 도시된 바와 같이 단계(770)에서 2차 클리핑을 수행하여 3차원에서의 뷰 볼륨 밖의 구성요소들을 모두 제거한다.

상기 단계(770)의 2차 클리핑은, 먼저 단계(771)에서 3차원 영상을 구성하는 모든 노드들의 z축 값을 클리핑 평면의 z축 값(k)과 비교하여 노드들의 z축 값이 z≥k일 경우에는 뷰 볼륨 안으로 판단하고, z＜k일 경우에는 뷰 볼륨 밖으로 판단한 후 단계(772)에서 모든 3차원 라인들의 노드들을 순차적으로 뷰 볼륨 밖 또는 뷰 볼륨 안 인지를 탐색하면서 2차 클리핑을 수행한다.

상기 단계(772)에서의 2차 클리핑 수행은, 단계(772-1)에서 3차원 라인을 구성하는 모든 노드들이 뷰 볼륨 밖인지를 판단하고, 단계(772-2)에서 3차원 라인을 구성하는 모든 노드들이 뷰 볼륨 안인지를 판단한다.

상기 단계(772-1)의 판단 결과 3차원 라인을 구성하는 모든 노드들이 뷰 볼륨 밖일 경우에 제어부(640)는 단계(772-3)에서 상기 뷰 볼륨 밖의 3차원 라인을 버린 후 단계(772-6)에서 모든 3차원 라인에 대한 탐색이 완료되었는지의 여부를 판단하고, 완료되지 않았을 경우에 단계(772-1)로 복귀하여 3차원 라인을 구성하는 모든 노드들이 뷰 볼륨 밖인지 또는 안인 지의 여부를 판단하는 동작을 반복 수행한다.

그리고 상기 단계(772-2)의 판단 결과 3차원 라인을 구성하는 모든 노드들이 뷰 볼륨 안일 경우에는 제어부(640)는 단계(772-5)에서 출력할 3차원 라인으로 판단하고, 단계(772-6)에서 모든 3차원 라인에 대한 탐색이 완료되었는지의 여부를 판단하며, 완료되지 않았을 경우에 단계(772-1)로 복귀하여 3차원 라인을 구성하는 모든 노드들이 뷰 볼륨 밖인지 또는 안인 지의 여부를 판단하는 동작을 반복 수행한다.

또한 상기 단계(772-1)(772-2)의 판단 결과 3차원 라인을 구성하는 모든 노드들이 뷰 볼륨 밖이거나 또는 뷰 볼륨 안이 모두 아닐 경우에는 3차원 라인이 클리핑 평면에 걸쳐져 있는 것으로서 단계(772-4)에서 클리핑 평면에 걸쳐져 있는 3차원 라인의 구조를 변경하여 새로운 구조의 3차원 라인을 구축한다.

도 8은 상기 단계(772-4)에서 새로운 3차원라인을 구축하는 일 실시 예의 과정을 보인 신호흐름도이다. 이에 도시된 바와 같이 제어부(640)는 단계(800)에서 3차원라인을 구성하는 모든 노드들을 순차적으로 탐색하여 뷰 볼륨 안에 위치하는 노드들의 개수를 판단하고, 단계(810)에서 상기 판단한 노드들의 개수만큼 메모리의 저장영역을 할당한 후 단계(820)에서 3차원라인을 구성하는 각 노드들을 순차적으로 탐색하면서 새로운 구조의 3차원라인을 구축한다.

상기 단계(820)의 새로운 3차원라인의 구축은, 단계(821)에서 3차원라인의 첫 번째 노드를 선택하고, 단계(822)에서 상기 선택한 노드가 뷰 볼륨 안에 위치하는지의 여부를 판단하여, 뷰 볼륨 안에 위치할 경우에는 단계(823)에서 그 노드의 좌표 값을 상기 메모리에 저장하고, 뷰 볼륨 안에 위치하지 않을 경우에는 메모리에 저장하지 않는다.

다음 단계(824)에서는 다음 노드가 있는지의 여부를 판단하여 다음 노드가 있을 경우에 단계(825)에서 다음 노드를 선택한 후 상기 단계(822)로 복귀하여 뷰 볼륨 안에 위치하는지의 여부에 따라 메모리에 저장하는 동작을 반복 수행하며, 단계(824)에서 다음 노드가 없을 경우에 복귀한다.

이러한 본 발명의 새로운 3차원라인을 구축하는 일 실시 예는 예를 들면, 도 9a에 도시된 바와 같이 7개의 노드 v0, v1, v2, v3, v4, v5 및 v6으로 이루어지는 3차원라인에 대하여 클리핑 평면(900)의 안쪽인 뷰 볼륨 안에 위치하는 노드들 v0, v1, v5 및 v6의 개수 4를 판단하여 도 9b에 도시된 바와 같이 4개의 노드들의 좌표 값을 저장할 메모리(910)의 영역을 할당하고, 할당한 메모리(910)의 영역에 노드 v0, v1, v5 및 v6의 좌표 값 ve0, ve1, ve5 및 ve6을 각기 저장하여 새로운 구조의 3차원라인을 구축한다.

도 10은 상기 단계(772-4)에서 새로운 3차원라인을 구축하는 다른 실시 예의 과정을 보인 신호흐름도이다. 이에 도시된 바와 같이 제어부(640)는 단계(1000)에서 3차원라인을 구성하는 모든 노드들을 순차적으로 탐색하면서 뷰 볼륨 안에 첫 번째로 위치하는 노드의 좌표 값을 메모리에 임시로 저장한 후 단계(1010)에서 3차원 라인을 구성하는 각 노드들을 순차적으로 탐색하면서 새로운 구조의 3차원라인을 구축한다.

상기 단계(1010)에서의 새로운 3차원라인의 구축은, 단계(1011)에서 순차적으로 하나의 노드를 선택 즉, 첫 번째 노드를 선택하고, 단계(1012)에서 상기 선택한 노드가 뷰 볼륨 밖에 위치하는 노드인지의 여부를 판단하여 뷰 볼륨 밖에 위치하지 않고, 뷰 볼륨 안에 위치하는 노드일 경우에 단계(1013)에서 그 뷰 볼륨 안에 위치하는 노드의 좌표 값을 메모리에 그대로 저장한다.

그리고 상기 단계(1012)의 판단 결과 뷰 볼륨 밖에 위치하는 노드일 경우에 제어부(640)는 단계(1014)에서 상기 선택한 노드가 3차원라인의 시작 노드인지의 여부를 판단하여, 시작노드일 경우에 단계(1015)에서 상기 임시 저장한 노드의 좌표 값 즉, 3차원라인의 노드들 중에서 뷰 볼퓸 안에 위치하는 첫 번째 노드의 좌표 값을 현재노드의 좌표 값으로 저장하며, 상기 단계(1014)의 판단 결과 시작노드가 아닐 경우에 바로 이전 노드의 좌표 값을 현재노드의 좌표 값으로 복사하여 저장한다.

다음 단계(1017)에서는 다음 노드가 있는지의 여부를 판단하고, 다음 노드가 있을 경우에 단계(1011)로 복귀하여 다음 노드를 선택하고, 상기한 동작을 반복 수행하면서 다음 노드의 메모리에 좌표 값을 저장한다.

이러한 본 발명의 새로운 3차원라인을 구축하는 다른 실시 예는 예를 들면, 도 11a에 도시된 바와 같이 클리핑 평면(1100)에 걸쳐져 있는 3차원라인(1110)을 7개의 노드 v0∼v6을 순차적으로 탐색하면서 뷰 볼륨 안에 위치하는 노드 v0 및 v1에 대해서는 도 11b에 도시된 바와 같이 노드 v0, v1, v5 및 v6의 좌표 값 ve0, ve1, ve5 및 ve6을 메모리(1120)에 저장하고, 뷰 볼륨 밖에 위치하는 노드 v2, v3 및 v4에 대해서는 바로 이전의 뷰 볼륨 안에 위치하는 노드 v1의 좌표 값 ve1을 순차적으로 복사하여 저장한다.

그리고 도 12a에 도시된 바와 같이 클리핑 평면(1200)에 걸쳐져 있는 7개의 노드 v0∼v6으로 이루어진 3차원라인(1200)의 시작노드 v0이 뷰 볼륨 밖에 있을 경우에는 3차원라인(1200)의 노드 v0∼v6들 중에서 처음으로 뷰 볼륨 안에 위치하는 노드 v2를 탐색하고, 그 노드 v2의 좌표 값 ve2를 도 12b에 도시된 바와 같이 노드 v0의 좌표 값으로 복사하여 메모리(1220)에 저장하며, 뷰 볼륨 밖에 위치하는 노드 v1의 좌표 값으로는 노드 v0의 좌표 값으로 저장한 ve2를 복사하여 저장하며, 또한 뷰 볼륨 밖에 위치하는 노드 v3 및 v4의 좌표 값으로 노드 v2의 좌표 값 ve2를 순차적으로 복사하여 새로운 구조의 3차원 라인을 구성한다.

상기 단계(770)에서의 2차 클리핑이 완료되면, 제어부(640)는 단계(780)에서 투영변환을 수행한다.

상기 단계(780)의 투영변환은, 단계(781)에서 상기 시점 기준의 좌표계로 변환한 각각의 노드들의 3차원 좌표들에 대하여 투영평면에 투영변환을 실시하여 투영된 2차원 좌표 값을 구하고, 단계(782)에서 각각의 투영된 2차원 좌표 값 즉, 투영좌표를 화면좌표로 변환한다.

여기서, 본 발명의 근사 클리핑에 따라 발생되는 오류가 투영평면의 하단 가장자리 영역에 투영되어 화면에 표시될 수 있다. 그러므로 본 발명에서는 상기 단계(782)에서 투영좌표를 화면좌표로 변환할 경우에 투영평면의 하단 가장자리의 오류가 표시되는 영역을 제외한 화면 표시영역을 설정하고, 그 화면 표시영역 내의 3차원 영상의 투영좌표를 화면좌표로 변환한다.

즉, 본 발명에서 3차원라인을 근사 클리핑 함에 따라 발생되는 오류를, 클리핑 평면에서 근사 클리핑하여 1차로 오류가 화면에 표시되는 것을 방지하고, 투영좌표를 화면좌표로 변환할 경우에 투영평면의 하단부의 소정 영역을 제거하여 2차로 근사 클리핑에 따른 오류가 화면에 표시되지 않도록 한다.

다음 단계(790)에서는 화면 표시과정을 수행한다. 상기 단계(790)의 화면 표시과정은, 단계(791)에서 도로, 녹지, 강 및 호수 등의 평면객체 부분의 다각형 다각라인을 출력하고, 단계(792)에서 이동체의 주행궤적의 다각 라인을 출력하며, 단계(793)에서 각각의 3차원 건물들의 다각형을 출력하며, 단계(794)에서 텍스트 데이터를 출력하여 화면에 표시한다.

한편, 상기에서는 본 발명을 특정의 바람직한 실시 예에 관련하여 도시하고 설명하였지만, 이하의 특허청구범위에 의해 마련되는 본 발명의 정신이나 분야를 이탈하지 않는 한도 내에서 본 발명이 다양하게 개조 및 변화될 수 있다는 것을 당 업계에서 통상의 지식을 가진 자는 용이하게 알 수 있다. 즉, 상기에서는 3차원 네비게이션 시스템에서 2차원 지도 데이터를 3차원으로 변환하여 화면에 표시하는 것에 3차원라인의 근사 클리핑을 적용하여 설명한 것으로서 본 발명을 실시함에 있어서는 이에 한정되지 않고, 표시패널의 화면상에 3차원 영상을 표시하는 각종 응용분야에 간단히 적용하여 실시할 수 있다.

이상에서 설명한 바와 같이 본 발명은 3차원 라인에 대하여 클리핑평면의 안쪽인 뷰 볼륨 안에 위치하는 노드들로 새로운 구조의 3차원라인을 구성함으로써 3차원라인의 클리핑속도가 매우 빠르고, 3차원영상 처리의 계산량을 현격하게 감소시켜 계산속도가 매우 빠르며, 이로 인하여 이동통신단말기 등과 같은 낮은 성능의 모바일 기기에서도 3차원지도 등과 같은 3차원 영상을 표시할 수 있다.

Claims (15)

1. 투영 중심위치와 투영평면의 사이에 3차원 라인을 클리핑할 클리핑 평면을 생성하고, 상기 투영중심위치를 기준으로 투영평면에 투영할 3차원 영상내에서 3차원 라인을 구성하는 모든 노드들의 z축 값을 상기 클리핑 평면의 z축 값과 각기 비교하여 각 노드가 뷰 볼륨(view volume) 안 또는 뷰 볼륨 밖의 어느 위치에 위치하는 노드인지를 판단하는 위치 판단과정;

   상기 위치 판단과정에서 노드들이 뷰 볼륨 안과 밖에 걸쳐져 있는 3차원라인에 대하여 뷰 볼륨 안의 노드들만으로 새로운 3차원라인을 구성하는 클리핑 과정으로 이루어진 3차원라인의 근사 클리핑 방법.
2. 제 1 항에 있어서, 상기 클리핑 평면은;

   상기 투영중심위치와 투영평면의 사이에 위치하는 것을 특징으로 하는 3차원라인의 근사 클리핑 방법.
3. 제 1 항에 있어서, 상기 클리핑 과정은;

   3차원라인을 구성하는 노드들 중에서 뷰 볼륨 안에 위치하는 노드의 개수를 탐색하는 제 10 과정;

   상기 제 10 과정에서 탐색한 노드의 개수만큼 메모리에 좌표 값을 저장할 영역을 할당하는 제 11 과정; 및

   상기 제 10 과정에서 탐색한 뷰 볼륨 안에 위치하는 노드들의 좌표 값을 상 기 제 11 과정에서 메모리에 할당한 노드의 해당 영역에 저장하여 새로운 3차원라인을 구성하는 제 12 과정으로 이루어지는 것을 특징으로 하는 3차원라인의 근사 클리핑 방법.
4. 제 1 항에 있어서, 상기 클리핑 과정은;

   3차원라인을 구성하는 노드들 중에서 처음으로 뷰 볼륨 안에 위치하는 노드를 탐색하는 제 20 과정;

   3차원라인을 구성하는 노드들을 순차적으로 선택하여 뷰 볼륨 안 또는 밖에 위치하는지의 여부를 판단하는 제 21 과정;

   상기 제 21 과정에서 뷰 볼륨 안에 위치하는 노드일 경우에 그 노드의 좌표 값을 메모리의 해당 영역에 저장하는 제 22 과정;

   상기 제 21 과정에서 뷰 볼륨 밖에 위치하는 노드일 경우에 그 노드가 3차원라인의 시작노드인지의 여부를 판단하는 제 23 과정;

   상기 제 23 과정의 판단 결과 시작노드일 경우에 상기 제 20 과정에서 탐색한 처음으로 뷰 볼륨 안에 위치하는 노드의 좌표 값을 메모리의 해당 영역에 저장하는 제 24 과정; 및

   상기 제 23 과정의 판단 결과 시작노드가 아닐 경우에 상기 제 22 과정 또는 제 24 과정에서 메모리에 저장한 바로 이전 노드의 좌표 값을 복사하여 메모리의 해당 영역에 저장하는 제 25 과정으로 이루어지는 것을 특징으로 하는 3차원라인의 근사 클리핑 방법.
5. 3차원 영상의 표시환경을 초기화하는 3차원 환경 초기화 과정;

   상기 3차원 환경 초기화 과정 이후에 기준위치 좌표를 기준으로 시점 및 시선을 설정하는 시점 설정과정;

   상기 시점 설정과정 이후에 투영 파라미터를 설정하는 투영 파라미터 설정과정;

   기준위치의 좌표를 기준으로 소정 영역의 3차원 좌표 값의 3차원 영상을 입력받는 3차원 모델 입력과정;

   상기 3차원 모델 입력과정에서 입력한 3차원 영상을 상기 시점 설정과정에서 설정한 시점 기준의 좌표계로 변환하는 시점 변환과정;

   상기 시점 변환과정에서 시점 기준의 좌표계로 변환한 3차원 영상 내에서 클리핑 평면에 걸쳐져 있는 3차원 라인들을 뷰 볼륨 안의 노드들로 새로운 3차원라인을 구성하고, 뷰 볼륨 밖의 구성요소들을 제거하며, 상호간에 가려진 3차원 면들을 제거하는 클리핑 과정;

   상기 클리핑 과정에서 클리핑하고 남은 3차원 영상을 상기 투영 파라미터 설정과정에서 설정한 투영 파라미터에 따라 투영평면에 투영하고 투영좌표를 화면좌표로 변환하는 투영 변환과정; 및

   상기 투영 변환과정에서 화면좌표로 변환한 3차원 영상을 화면에 표시하는 표시과정으로 이루어진 3차원라인의 근사 클리핑을 이용한 3차원 영상의 표시방법.
6. 3차원 영상의 표시환경을 초기화하는 3차원 환경 초기화 과정;

   상기 3차원 환경 초기화 과정 이후에 기준위치 좌표를 기준으로 시점 및 시선을 설정하는 시점 설정과정;

   상기 시점 설정과정 이후에 투영 파라미터를 설정하는 투영 파라미터 설정과정;

   기준위치의 좌표를 기준으로 소정 영역의 2차원 지도를 로딩하는 로딩 과정;

   상기 로딩과정에서 로딩한 3차원 지도를 3차원 영상으로 모델링하는 3차원 모델링과정;

   상기 3차원 모델링과정에서 모델링한 3차원 영상을 상기 시점 설정과정에서 설정한 시점 기준의 좌표계로 변환하는 시점 변환과정;

   상기 시점 변환과정에서 시점 기준의 좌표계로 변환한 3차원 영상 내에서 클리핑 평면에 걸쳐져 있는 3차원 라인들을 뷰 볼륨 안의 노드들로 새로운 3차원라인을 구성하고, 뷰 볼륨 밖의 구성요소들을 제거하며, 상호간에 가려진 3차원 면들을 제거하는 클리핑 과정;

   상기 클리핑 과정에서 클리핑하고 남은 3차원 영상을 상기 투영 파라미터 설정과정에서 설정한 투영 파라미터에 따라 투영평면에 투영하고 투영좌표를 화면좌표로 변환하는 투영 변환과정; 및

   상기 투영 변환과정에서 화면좌표로 변환한 3차원 영상을 화면에 표시하는 표시과정으로 이루어진 라인 클리핑을 이용한 3차원 영상의 표시방법.
7. 제 5 항 또는 제 6 항에 있어서, 상기 기준위치 좌표는;

   GPS 수신신호로 검출한 이동체의 위치좌표 또는 사용자가 입력하는 좌표인 것을 특징으로 하는 3차원라인의 근사 클리핑을 이용한 3차원 영상의 표시방법.
8. 제 5 항 또는 제 6 항에 있어서, 상기 3차원 환경 초기화 과정은;

   시점, 시선, 광원의 방향, 광원의 세기 및 건물들의 각 면의 각도 등에 따라 건물 각 면을 표시할 색상 및 농도를 설정하고, 시점으로부터 소정의 표시 대상물이 표시되는 위치까지의 거리를 나타내는 깊이버퍼를 초기화하며, 화면의 바탕색을 소정의 색상으로 설정하는 것을 특징으로 하는 3차원라인의 근사 클리핑을 이용한 3차원 영상의 표시방법.
9. 제 5 항 또는 제 6 항에 있어서, 상기 시점 설정과정은;

   상기 기준위치 좌표를 기준으로 시점을 설정하고, 그 시점에서의 시선을 설정하는 것을 특징으로 하는 3차원라인의 근사 클리핑을 이용한 3차원 영상의 표시방법.
10. 제 6 항에 있어서, 상기 3차원 모델링 과정은;

    2차원 지도에서 3차원의 바닥면 지도를 생성하는 바닥면 지도 생성과정;

    상기 바닥면 지도 생성과정 이후에 각 건물들의 노드의 높이를 설정하여 설정한 높이로 각 건물들을 생성하는 건물 생성과정; 및

    상기 건물 생성과정 이후에 이동체의 주행정보의 궤적을 생성하는 궤적 형성과정으로 이루어지는 것을 특징으로 하는 3차원라인의 근사 클리핑을 이용한 3차원 영상의 표시방법.
11. 제 5 항 또는 제 6 항에 있어서, 상기 클리핑과정의 새로운 3차원라인의 구성은;

    투영중심위치를 기준으로 투영평면에 투영할 3차원 영상 내에서 3차원 라인을 구성하는 모든 노드들의 z축 값을 클리핑 평면의 z축 값과 각기 비교하여 노드가 뷰 볼륨 안 또는 뷰 볼륨 밖에 위치하는 노드인지를 판단하는 위치 판단과정; 및

    상기 위치 판단과정에서 노드들이 뷰 볼륨 안과 밖에 걸쳐져 있는 3차원라인에 대하여 뷰 볼륨 안의 노드들로 새로운 3차원라인을 구성하는 클리핑 과정으로 이루어지는 것을 특징으로 하는 3차원라인의 근사 클리핑을 이용한 3차원 영상의 표시방법.
12. 제 11 항에 있어서, 상기 클리핑 평면은;

    상기 투영중심위치와 투영평면의 사이에 위치하는 것을 특징으로 하는 3차원라인의 근사 클리핑을 이용한 3차원 영상의 표시방법.
13. 제 11 항에 있어서, 상기 클리핑 과정은;

    3차원라인을 구성하는 노드들 중에서 뷰 볼륨 안에 위치하는 노드의 개수를 탐색하는 제 30 과정;

    상기 제 30 과정에서 탐색한 노드의 개수만큼 메모리에 좌표 값을 저장할 영역을 할당하는 제 31 과정; 및

    상기 제 30 과정에서 탐색한 노드의 좌표 값을 상기 제 31 과정에서 할당한 메모리의 해당 영역에 저장하여 새로운 3차원라인을 구성하는 제 32 과정으로 이루어지는 것을 특징으로 하는 3차원라인의 근사 클리핑을 이용한 3차원 영상의 표시방법.
14. 제 11 항에 있어서, 상기 클리핑 과정은;

    3차원라인을 구성하는 노드들 중에서 처음으로 뷰 볼륨 안에 위치하는 노드를 탐색하는 제 40 과정;

    3차원라인을 구성하는 노드들을 순차적으로 선택하여 뷰 볼륨 안 또는 밖에 위치하는지의 여부를 판단하는 제 41 과정;

    상기 제 41 과정에서 뷰 볼륨 안에 위치하는 노드일 경우에 그 노드의 좌표 값을 메모리의 해당 영역에 저장하는 제 42 과정;

    상기 제 41 과정에서 뷰 볼륨 밖에 위치하는 노드일 경우에 그 노드가 3차원라인의 시작노드인지의 여부를 판단하는 제 43 과정;

    상기 제 43 과정의 판단 결과 시작노드일 경우에 상기 제 40 과정에서 탐색한 처음으로 뷰 볼륨 안에 위치하는 노드의 좌표 값을 메모리의 해당 영역에 저장 하는 제 44 과정; 및

    상기 제 43 과정의 판단 결과 시작노드가 아닐 경우에 상기 제 42 과정 또는 제 44 과정에서 메모리에 저장한 바로 이전 노드의 좌표 값을 복사하여 메모리의 해당 영역에 저장하는 제 45 과정으로 이루어지는 것을 특징으로 하는 3차원라인의 근사 클리핑을 이용한 3차원 영상의 표시방법.
15. 제 5 항 또는 제 6 항에 있어서, 상기 투영 변환과정에서의 화면좌표 변환은;

    투영평면에서 하단 가장자리의 설정영역을 제외한 화면 표시영역을 설정하고, 그 화면 표시영역 내의 3차원 영상의 투영좌표를 화면좌표로 변환하는 것을 특징으로 하는 3차원라인의 근사 클리핑을 이용한 3차원 영상의 표시방법.

Images