工學碩士學位論文 대용량비규칙지형데이터의효율적인렌더링기법 Efficient Large-Scale Irregular Terrain Rendering Method 2007 年 2 月 仁荷大學校大學院 컴퓨터 情報工學科 康東洙
工學碩士學位論文 대용량비규칙지형데이터의효율적인렌더링기법 Efficient Large-Scale Irregular Terrain Rendering Method 2007 年 2 月 指導敎授申秉錫 이論文을工學碩士學位論文으로提出함 仁荷大學校大學院컴퓨터 情報工學科康東洙
이論文을康東洙의碩士學位論文으로認定함. 2007 年 2 月 主審 ( 印 ) 副審 ( 印 ) 委員 ( 印 )
요 약 항공LIDAR 스캐너나나측지위성으로부터획득된고도데이터를이용하여실제지형을고해상도로실시간에랜더링하는기술은컴퓨터게임, 가상현실그리고지리정보시스템 (Geographic Information System) 등에서매우중요하게사용되고있다. 기존의지형의실시간렌더링을위해사용되었던대부분의방법들은 DEM(Digital Elevation Map) 이나 DTED(Digital Terrain Elevation Data) 과같은규칙격자 (regular grid) 데이터에적합하게개발되어져왔다. 하지만최근 LIDAR(LIght Detection And Ranging) 와같은 3D 스캐닝기술이발달하여보다정밀하고정확한지형데이터를제공할수있게됨으로서 LIDAR 데이터를이용한보다정밀한지형렌더링기법이요구되고있다. 이를위해서는 LIDAR 데이터와같은비규칙 (irregular grid) 데이터에적합한렌더링기법이필요하다. 하지만기존의방법들은규칙격자데이터에최적화되어져있기때문에적용하기어렵다. 또한 LIDAR 데이터의크기가방대하기때문에일반 PC 에서는처리하기가쉽지않다. 본논문에서는일반 PC에서도처리가능한대용량비규칙데이터의빠르고효율적인렌더링방법을제안한다. 우선입력된데이터에서영상의왜곡을초래하는 outlier를제거한다. 다음으로샘플데이터의공간적분포에따라규칙격자를생성하고, 이격자에맞도록 LIDAR 데이터를재샘플링한후쌍선형보간법을이용하 여영상에틈이발생하지않도록한다. DEM 형태로기하재구성된데이터에쿼 드트리기반의연속적인상세단계알고리즘을적용하여지형을효율적으로렌더링한다. 실험결과에서, 본논문의방법이기존방법에비해높은화질을만들어낼수있을뿐만아니라높은프레임율로대용량지형데이터를렌더링할수있음을알수있다. - i -
ABSTRACT In the field of realistic virtual environment, interactive computer games and GIS application, terrain modeling and rendering are essential techniques. Advanced high resolution scanning technologies such as LIDAR enable us to obtain dense and accurate irregular terrain dataset. However, unlike the regular sampled dataset such as DEM(Digital Elevation Map) and DTED(Digital Terrain Elevation Data), irregular dataset cannot be rendered in real-time due to random distribution of samples. Moreover, because they generally have huge amount of point data, it is very hard to manipulate them in consumer PC. We propose a fast and efficient terrain rendering method using large-scale irregular dataset for computer games application. First, it reconstructs the geometry by converting irregular dataset into regular one, through resampling input data with regular interval considering the spatial distribution of sample points. It can generate animated scene by applying quad-tree based rendering method to converted dataset. Experimental results show that our method normally produces high-quality images, and requires less rendering time compared with the Delaunay triangulation method (previous method). - ii -
목차 요약 ⅰ ABSTRACT ⅱ 제 1 장서론 1 제 2 장관련연구 3 2.1 규칙데이터를이용한지형모델링 6 2.1.1 ROAM 7 2.1.2 쿼드트리 8 2.3 비규칙데이터를이용한지형모델링 9 제 3 장지형가시화알고리즘 12 3.1 기하재구성 13 3.1.1 잡음제거 13 3.1.2 정규화 15 3.1.3 보간 18 3.2 쿼드트리기반연속적인상세단계기법 20 제 4 장실험및결과 23 제 5 장결론및향후연구과제 31 참고문헌 33 - iii -
제 1 장서론 컴퓨터게임, 가상현실분야그리고지리정보시스템 (GIS) 등에서실제환경및가상환경의기반이되는지형의표현은중요한요소이다. 또한전통적인응용분야인가상현실과비행시뮬레이션등에서사실감을더욱극대화하기위해서는빠르고현실감있는지형렌더링이필수적이다. 지형데이터는샘플점들의공간적분포규칙성에따라규칙격자데이터, 비규칙데이터로나눌수있다. 규칙격자지형데이터의대표적인예로는 DEM이나 DTED 등이있으며, 이들의규칙적인공간적분포를이용하는쿼드트리 [1] 나 ROAM (Real-time Optimally Adaptive Meshes)[2] 과같은자료구조들은시각절두체선별과연속상세단계 (Continuous Level of Detail : CLOD) 의구현을용이하게할뿐만아니라실시간으로렌더링을가능하게한다. 하지만, 규칙격자데이터는샘플간격이 10m 이상의저해상도표현만가능하므로지형의상세한모습을나타낼수없다. 오늘날널리쓰이는 LIDAR 데이터는샘플간격이 1m 미만의고해상도를갖는비규칙지형데이터로써항공측량등을통해얻을수있다. 비규칙데이터는 TIN(Triangle Irregular Network) 형태로 Delaunay triangulation 알고리즘 [3] 방법을이용하여 3차원지형을재구성한다. 이러한방법을이용하면지형의상세부분까지표현이가능하여기존의규칙격자데이터의저해상도문제점을해결할수있지만, 데이터로부터기하정보를재구성하기까지의시간이오래걸리는단점이있다. 또한최적화기법을적용해도방대한계산량으로인하여실시간응용프로그램에는부적합하다. 본논문에서는비규칙적공간분포를갖는대용량의지형데이터를효율적으로가시화하기위한규칙데이터로변환하는방법을제안하여지형데이터를실시간으로렌더링할수있게한다. 먼저입력데이터에서영상의왜곡을초래하는 - 1 -
outlier를제거한다. 두번째로데이터의공간분포를고려한규칙격자를생성한후재샘플링 (resampling) 및보간 (interpolation) 하여각셀마다고도데이터정보를채운다. 마지막으로쿼드트리기반의연속적인상세단계기법을적용하여지형을렌더링한다. 이방법은비규칙데이터에서일반적으로사용되는지형가시화알고리즘들에비해화질의저하를최소화하면서빠르게지형을렌더링할수있다. 실험을통해쿼드트리기법을비규칙데이터에적용할수있음을보였다. 기하재구성에소요되는시간과프레임율을측정하여실시간지형렌더링시스템에적합함을확인하였다. 또한기존방법과의결과영상을비교하여화질손상이거의없음을보였다. 논문의구성은다음과같다. 2장에서는데이터특성에따른지형렌더링방법의관련연구를살펴보고, 3장에서는본논문에서제안한알고리즘을살펴본다. 4장에서실험결과를보이고, 5장에서결론을맺는다. - 2 -
제 2 장관련연구 이장에서는지형가시화에사용되는데이터들과각데이터특성에따른렌더링알고리즘을살펴보고, 방대한양의지형데이터를실시간으로렌더링할경우발생하는기존방법의문제점및이를해결하기위해기존에제안되었던방법을소개한다. 2.1 규칙데이터를이용한지형모델링 널리사용되는규칙데이터에는 DTED(Digital Terrain Elevation Data) 이나 DEM(Digital Elevation Map) 이있다. 항공측량이나원격탐사, 위성을이용한측량등으로부터얻는이러한데이터들은일정간격의 (x, y) 좌표에대하여 z축성분인높이를가지는고도필드 (height field) 형태로저장된다. 실시간처리를위하여다양한형태의자료구조와간략화기법들이고안되었는데대표적인기법으로연속적인상세단계 [4] 를이용한방법이있다. 연속적인상세단계는시점의위치와거리에따라동적으로모델의상세단계를조절한다. 고도필드로표현되는지형데이터의경우실행시간에삼각형집합을동적으로생성하는것이불가능하므로, 거리가변함에따라지형의정점들을나누거나합치는방법으로상세단계를동적으로조절하는것이다. 연속적인상세단계기법에사용되는자료구조로써는 ROAM과쿼드트리구조가있다. - 3 -
[ 그림 2-1] 고도필드데이터를흑백이미지로나타낸예. 각이미지의각 픽셀은고도값을나타내며 8bit 256 단계로고도를표시한다. 이미지에서밝은 부분은높은고도, 어두운부분은낮은고도를나타낸다. 2.1.1 ROAM(Real-time Optimally Adaptive Meshes) Duchaineau[2] 이제안한 ROAM은카메라의위치에따라지형을동적으로생성하며이진삼각형트리 (binary triangle tree) 구조를이용한다. 각패치 (patch) 는단순히이등변삼각형이며, 각삼각형을재귀적으로 2분할하여다음레벨의자식노드로만드는이진삼각형트리구조로되어있다. 이방법은카메라로부터가까운곳의지형은재귀적인분할을통하여높은상세단계를표현하며카메라로부터멀리있는곳의지형은삼각형의병합을통하여낮은상세단계를나타낸다. 이와같이 ROAM 방법은상세도조절을위한삼각형의분할과병합이용이한장점을지니지만삼각형분할시인접한삼각형과차이가발생하는 T-정점 (T-vertex) 문제를방지하기위해현재삼각형의분할상태를이웃한삼각형에차례로전파하는강제분할을해야한다. 이는 CPU의부담을증가시킬뿐아니라메모리사용과소요되는시간측면에서도많은비용이든다. - 4 -
[ 그림 2-2] 이진삼각형트리의삼각형분할. 계층의증가는각이등변삼각형 패치를 2 분할하여상세한지형을표현한다. 이와는반대로계층의감소는 삼각형의병합을통하여좀더거친지형을나타낸다. 2.1.2 쿼드트리 쿼드트리는재귀적인방법으로 2 차원공간을 4 개의자식노드로분할하여트리 를구성하는알고리즘으로지형을효율적으로분할하여구성한다. 쿼드트리는부 모노드가절두체에포함되지않는다면, 자식노드들도절두체에포함되지않기때문에부모노드가포함된노드들만절두체탐색을하여시각절두체선별구현에적합한방법이다. 이과정을재귀호출로반복하다보면빠르게절두체선별을할수있다. 또한쿼드트리는상세단계구현에도적합하다. 상세단계구조는카메라에서먼거리에있는노드는자식노드에대한렌더링을하지않고자신의단계에서렌더링을하며, 상대적으로카메라에서가까울수록더하위자식노드로내려가서렌더링한다. 이러한구조적특성들은대용량의지형데이터의실시간렌더링이가능하게한다. - 5 -
[ 그림 2-3] 상향식방법을이용한쿼드트리노드의탐색 쿼드트리를이용한연속적상세단계방법은 Lindstrom[5] 이처음으로제안했다. 이방법은삼각형의분할과합병을결정하는데상향식 (bottom-up) 접근방법을이용한다. 그후 Rottger[4] 에의해서는하향식 (top-down) 접근방법을이용한알고리즘이제안되었다. 이방법은전처리를통해계산된 error metric을이용하여정점을제거하기때문에추가적인비용없이기하모핑을이용할수있으며, 전체데이터중일부분만을탐색하는하향식방법을사용하기때문에거대한지형을빠르게검색하는것이가능하다. 결과적으로높은프레임율의렌더링을보장한다. 이와같이빠르고효율적으로지형을가시화하는쿼드트리는규칙격자데이터에대해서는고속의렌더링이가능하지만입력이규칙격자데이터로제한되어있기때문에 LIDAR 데이터와같이비규칙데이터에는적용할수없다는문제점을가지고있다. - 6 -
[ 그림 2-4] 하향식방법을이용한쿼드트리노드의탐색 2.2 비규칙데이터를이용한지형모델링 LIDAR(LIght Detection And Ranging) 는빛을이용한탐지와거리측정이란뜻으로일반적으로레이저를주사한후레이저가반사되어돌아오는시간을측정하여물체의 3차원위치좌표를계산하는것을기본원리로한다. LIDAR 데이터의장점은항공측량을통하여샘플간격이 1m 미만의고해상도지형데이터를획득할수있지만공간적분포가균일하지않기때문에앞서살펴보았던실시간지형렌더링기법을적용할수없다. 비규칙데이터는주로데이터를삼각형들의집합으로표현하는 TIN(Triangle Irregular Network) 방법으로렌더링한다. TIN은산봉우리, 산맥이나골짜기와같이복잡한지형일수록삼각형이조밀하게생성되므로지형을상세하게나타낼수있다. TIN을구성하는가장대표적인방법은 Delaunay triangulation[3] 방법이다. [ 그림 2-5] 에서보는바와같이 Delaunay triangulation은 Vornoi 다이어그램의 dual 그래프로정의된다. Vornoi diagram[6] 은주어진평면상의점들의집합 V에 - 7 -
대해평면을연속된다각형영역으로분할한것으로, 각각의다각형영역은 V에속한한점 P에대해 V의다른어떤점보다 P에가까운점들을선택하여삼각형화한다. 그러나 TIN을생성하기위하여대부분계산시간이많이소요되기때문에실시간에동적으로생성하기에는부적절하며, 다각형메시의공간적인구성표현이미흡하기때문에충돌검사, 선택, 쿼리등을위한교집합검사등과같은연산을효율적으로다루지못한다. 또한특징점이나선등과같은지형의특성에민감하지못하기때문에이를표현하기위해서는삼각형화를수행하기전에사용자가수동으로특징적인점들과선들을잡아주어야하며, 점들의개수가변하는경우에는전체적인과정을처음부터다시수행해야한다. [ 그림 2-5] 입력점에대한 Vornoi 다이어그램 [6] 과 Delaunay triangulation[3] 이와같은단점들은방대한양의데이터를지니는지형데이터에서더욱두드러 지며, LIDAR 데이터의경우에도예외는아니다. - 8 -
[ 그림 2-6] 512 개의비규칙정점집합으로구성된 TIN 의예 - 9 -
제 3 장지형가시화알고리즘 실제널리쓰이는지형가시화의응용분야에서는현실감있는영상이중요하며, 이를위해실시간에렌더링할것을요구한다. ROAM이나쿼드트리자료구조를이용하면실시간렌더링이가능하지만이들의입력데이터는오직규칙데이터만을다룬다. Delaunay triangulation을이용하여비규칙데이터로부터 TIN을생성할수도있지만방대한양의 LIDAR 데이터와같은지형데이터를처리하기에는삼각형의생성시간을감당할수가없다. 이러한문제점을해결하기위해본연구는비규칙데이터에서도쿼드트리의구조를사용하여지형을가시화할수있도록하는방법을제안한다. [ 그림 3-1] 지형가시화알고리즘의흐름도 지형을가시화하는과정은 [ 그림 3-1] 와같다. 첫번째로, 기하재구성과정을통 하여비규칙데이터를규칙격자데이터형태로변환한다. 기하재구성은먼저입 - 10 -
력데이터의잡음을제거후정규화및보간단계를통하여단위격자를생성한다. 두번째로, 변환된데이터를쿼드트리기반의연속적인상세단계기법 [7] 을적용하 면비규칙데이터에서도빠르게지형을가시화할수있다. 3.1 기하재구성 기하재구성은입력데이터의잡음제거, 비규칙데이터의정규화및보간의 3 단 계로구성되며, 비규칙데이터를쿼드트리방법에적합한형태인단위격자로변환 하여준다. 3.1.1 잡음제거 LIDAR 데이터에는 3D 스캐너장치의기계적오류로인하여잡음이생긴다. 일반적으로잡음은정상적인샘플데이터보다아주크거나아주작은값을가진다. 또한샘플간격이 1m 미만의고해상도를지니는 LIDAR 데이터의특성상데이터간의간격이 1m보다훨씬넓은점들도잡음이된다. 이러한잡음은단위격자생성에있어서오류를발생시키는원인이되며, 원하지않는왜곡된지형영상을생성하게된다. 본연구에서는가상격자 [8] 자료구조를이용하여 LIDAR 데이터의잡음을제거한다. 가상격자는데이터분포에따른 3차원공간을 X-, Y-, Z-축을따라일정간격으로수직하게나눈것으로각격자에포함된샘플데이터들의개수를이용하여잡음을판단한다. 다음은 Z-축으로의가상격자를이용하여잡음을제거하는과정이다. - 11 -
1). Z-축의가상격자를생성한다. (1) 샘플데이터의 z의최대값과최소값을구한다. (2) 데이터의분포를고려하여가상격자의간격을결정한다. (3) z의범위 ( 최대값-최소값 ) 를가상격자의간격으로나누어격자의크기를구한다. 2). 1) 에서생성된가상격자를이용하여잡음을제거한다. (1) 각격자에속하는샘플데이터들을계수한다. (2) 계수한수가임계치보다작을경우, 해당격자의샘플데이터들을잡음이라판단하고이를제거한다. 위의과정과마찬가지로 X-축과 Y-축에서대해서도동일한방법으로잡음을제거한다. LIDAR 데이터의경우계수한값이 0인격자가연이어반복될경우그이후에나오는데이터들은잡음이되므로임계치와의비교없이샘플데이터로부터제거해도무방하다. [ 그림 3-2] 은 Z-축을따라형성한가상격자의예를나타낸것이며 f는격자내에존재하는샘플데이터의수를의미한다. 격자의크기가 8이고임계값이 10인경우, 점선으로표시한원안에포함된데이터들은잡음으로간주되며샘플데이터로부터제거된다. 제거한데이터가잡음이아닌의미있는데이터라하여도 LIDAR 데이터에는지형의상세정보를나타낼만큼의충분한샘플데이터가존재하는고해상도의데이터이기때문에최종영상에는크게영향을미치지않는다. - 12 -
[ 그림 3-2] z- 방향에서의가상격자구성 3.1.2 정규화 규칙격자는 x, y 평면에대하여일정한크기와간격으로형성된격자로서지형데이터는각격자가고도값을가지는고도필드의형태로저장된다. LIDAR 데이터는고도필드형태의저장구조를따르지않는비규칙적데이터이므로규칙격자를생성하고이에따른데이터의재샘플링과정이필요하다. 규칙격자를이용한지형의정확도는격자의크기와간격에의해결정되므로의미존재하는샘플데이터의분포를이용하여정의하여야한다. 가장이상적인경우는하나의샘플데이터가하나의고도데이터로대응되도록격자를나누는것이다. 격자의간격이증가할수록하나의셀안에다수의샘플데이터가포함되며, 이러한셀의고도필드값을결정하는과정에서지형의상세정보가손실된다. 반대로격자의간격이작으면무수히많은셀이생성되며, 이는재샘플링을하는데많은시간이소요된다. 또한, 단하나의샘플데이터조차들어있지않는무의미한셀들이많아지며결과영상에서틈 (hole) 을만들어내는원인이된다. 따라서본논문에서는이상적인규칙격자생성에가장근접하도록다음과같은규칙격자생성방법을제안한다. - 13 -
규칙격자의생성은다음과같이총 4 단계로나눌수있다. (1) 샘플데이터의전체개수 : (2) 규칙격자크기 : = (3) 규칙격자수평범위 : 규칙격자수직범위 : (4) 규칙격자수평간격 : 규칙격자수직간격 : 여기서, 는샘플데이터의 좌표값이다. 잡음이제거된전체샘플데이터의개수를 라할때, 의제곱근으로규칙격자의크기 을결정한다. 그리고샘플데이터의 의최대최소값을구하여수평범위와수직범위를구한다. 이를격자의크기 N으로나누면한셀의크기즉규칙격자의간격 I x, I y 를구하게된다. 이와같이규칙격자를생성한후에고도필드형태로의변환을위해재샘플링한다. 재샘플링은격자의크기와간격에따라샘플데이터를분류한후각셀에속한데이터들을평균하여고도값을계산한다. 하지만셀내에계산할데이터가존재하지않을경우해당값을정하지못하므로기하재구성의마지막단계인보간단계를통하여격자의모든값을채워야한다. - 14 -
(a) 규칙격자생성 (b) 재샘플링 [ 그림 3-3] 정규화단계. (a) 16 개의샘플데이터로부터생성된 4 4 규칙격자, (b) 각셀안에속한데이터의평균으로고도값을계산한다. 3.1.3 보간 정규화단계에서생성된규칙격자의셀들중에는 LIDAR 데이터의불규칙한공간분포특성상단하나의샘플데이터조차포함하지않는셀이생기기마련이며따라서이런경우고도필드값이존재하지않는다. 이러한셀들은지형렌더링시고도데이터가존재하지않기때문에틈이발생하며이는영상의왜곡을초래한다. 본연구에서는틈을없애기위하여다음과같은쌍선형보간법 (bilinear interpolation) 을이용한다. 쌍선형보간법은보간할대상의주변으로부터가장가까운네개의점들에가중치를곱한값들의합으로써값을결정하는방법으로써데이터가존재하지않는영역에적절한값을부여하도록하여준다. [ 그림 3-4] 는쌍선형보간법을보여준다. - 15 -
[ 그림 3-4] 쌍선형보간법. 선형보간이용하여 I 1 과 I 2 를계산한후, 이두값을다시선형보간하여최종결과값 O 를얻는다. 먼저대상점으로부터가장가까운점 D 1, D 2, D 3, D 4 의 4개의점을선택후 D 1 과 D 2, D 3 과 D 4 를각각 α의가중치로써선형보간하여 I 1 과 I 2 를계산한다. 다시 I 1 과 I 2 를 β의가중치를곱한합으로써의선형보간하여최종값 O를구하도록한다. 본연구에서는쌍선형보간법을다음과같이적용한다. (1) 정규화단계후얻어진규칙격자중고도필드가존재하지않는위치를찾는다. (2) 해당위치로부터일정임계치범위안에있는데이터들중가장가까운좌우상하 4개의고도필드를선택한다. (3) 선택된데이터까지의거리를가중치로두어 I 1, I 2 를계산후다시이를선형보간하여해당위치의고도필드값 O를구한다. 임계치범위안에데이터가존재하지않는다는것은현재셀의고도필드에영향 을미칠만한값이존재하지않다는것을의미하며보간법을적용할수없으므로, 이경우의고도필드값은전체샘플데이터의평균값으로대체한다. - 16 -
3.2 쿼드트리기반의연속상세단계기법 앞단계의기하재구성과정의결과로써생성된단위격자를통하여쿼드트리기 반의연속상세단계기법을적용, 다음과같은방법으로지형렌더링한다. (1) 고도필드데이터를탐색하며재귀적으로모든단말노드의 error metric을계산한다. (2) 계산된단말의 error metric을상위노드로전파한다. (3) 계산된 error metric의집합을가지고각노드에서상세도를결정하는함수로현재노드가자식노드를가지게되는지를결정한다. (4) 고도필드는생성된쿼드트리를재귀적으로탐색하면서삼각형집합을생성한다. (5) 생성된삼각형집합을렌더링한다. (3) 의단계는하향식단계로재귀적으로이루어지며쿼드트리를생성한다. (4) 의단계에서쿼드트리의단말노드에도달했을때, 전체혹은부분적인삼각형부채꼴 (triangle fan) 이그려진다. 쿼드트리의각하위노드들의분할여부는 [ 그림 3-5] 에서보는바와같이노드의크기 (d) 와노드와시점간의거리 (l) 에의해결정된다. [ 그림 3-5] 광역해상도결정기준 d 와 l l/d<c 식을만족하도록 d 와 l 을결정하며, 이값을이용하여거리에따라노드 - 17 -
크기를제어할수있다. 여기에서 C는최소광역해상도로써 C의값을크게설정하면많은수의삼각형이생성해야하는것을의미하며, 이는쿼드트리는더작은노드로분할됨을의미한다. 시각의존적인상세단계를표현하기위한 error metric은노드에인접한고도값들가운데그차이의절대값이가장큰값을이용한다. ( 식 (1) 참조 ) 1 d 2 = max dhi 식 (1) d i= 1..6 [ 그림 3-6] 에서보는바와같이 d2 값은노드중심주변의네개의정점이이루는여섯개의간선에서높이의차이를구한후그가운데최대값과노드의길이를나눈값이다. 이값이해당노드의 error metric이되며모든단말노드에서계산되어상위노드로전파된다. 각노드에대한상세도를결정하기위하여다음의식을이용한다. 식 (2) 임의노드에대해서결정변수 f의값을계산했을때그값이 1보다작다면그노드는자식노드를가지고있음을나타낸다. 식 (2) 에서의 c 는원하는해상도까지도달하는정도를나타내며모든노드에대해결정변수로분할여부를판별하여쿼드트리를생성한다. [ 그림 3-6] 높이차이를이용한 error metric 측정 - 18 -
제 4 장실험및결과 실험은펜티엄 IV 3.0GHz CPU와 1GB Main Memory를장착한 PC와 NVIDIA Geforce FX5600 그래픽카드에서수행하였다. 실험데이터는 LIDAR 지형데이터를사용하였고본논문의방법과의비교를위하여 Delaunay triangulation 알고리즘을이용하였다. 표 1은샘플데이터개수에따른본논문의기하재구성시간을측정한것이다. 실험결과 3,408,187개의대용량의 LIDAR 데이터의경우에도기하를재구성하는데약 1분정도밖에필요하지않음을알수있다. 이경우 Delaunay triangulation 알고리즘의방법은동일데이터에서기하모델을구성하는데만무려 12시간이상이소요되었다. 샘플데이터 개수 Delaunay triangulation ( 초 ) 본논문의방법 ( 초 ) 12,961 4.546 0.08 25,179 26.922 0.35 52,119 158.156 0.95 127,048 923.329 3.11 430,674 9,579.781 3.63 845,425 33,513.563 18.19 1,626,972 n/a 28.74 3,408,187 n/a 63.69 [ 표 1] 샘플데이터개수에따른기하재구성시간 [ 그림 3-7] 부터 [ 그림 3-8] 에서는 52,119 개의샘플데이터를지닌 LIDAR 데이터의 기하재구성과정을보여준다. 기하재구성은비규칙데이터를규칙데이터로변환 - 19 -
하는과정이며잡음제거후정규화와쌍선형보간법을통하여이루어진다. [ 그림 3-7] 는메시가존재하지않는점의형태로만지형을표현한영상이다. 이를수평방향에서관측하여보니 [ 그림 3-8](a) 와같이잡음이존재함을알수있었다. 따라서 Z-축방향의가상격자를이용하여잡음을제거하였다. 즉격자의간격을 2m로설정, 실험데이터의고도값은최대 357.08m, 최소 251.12m의분포를보였으므로 52의크기의가상격자가생성되었다. 각격자에속하는데이터들을계수한후그값이 10 이하인격자의샘플데이터약 30여개를제거하였더니 [ 그림 3-8](b) 와같은결과영상을얻게되었다. [ 그림 3-7] 점으로지형을표현한영상 - 20 -
(a) 잡음제거전영상 (b) 잡음제거후결과영상 [ 그림 3-8] 잡음제거단계에서는원안에표시된잡음을제거한다. 잡음이제거된샘플데이터를이용하여 200 200 크기의규칙격자를생성하고격자에맞게재샘플링을하여고도필드를계산하였다. 하지만데이터의비규칙적분포로인하여고도필드가존재하지않는셀이생기며이를아무런처리없이렌더링을하게되면 [ 그림 3-9] 와같은거친영상을얻게된다. 따라서쌍선형보간법을이용하여지형을렌더링하면 [ 그림 3-10] 에서보는바와같이매끄러운영상을얻을수있다. - 21 -
[ 그림 3-9] 200 200 규칙격자생성및그에따른재샘플링결과 [ 그림 3-10] 쌍선형보간법을적용한후의결과영상 - 22 -
[ 그림 3-11] 는기존방법과본연구의화질을비교한것이다. [ 그림 3-11](a) 는샘플데이터원본을점으로만나타낸것이다. 단순히점으로만표현하기때문에렌더링속도가빠르지만, 영상에서보는바와같이현실감이부족하며기하정보를표현할수도없다. Delaunay triangulation 알고리즘을사용한결과영상 [ 그림 3-11](b) 는비록지형의상세한면까지나타낸다하여도데이터의크기에비례하여많은삼각형이생성된다. 따라서렌더링시간도기하급수적으로증가하며, 10fps 보다낮은프레임율을보였다. 본연구에서제안한방법은평균 45fps 이상의프레임율을보인다. [ 그림 3-11](c) 는, 연속적상세단계기법으로인하여기존방법에비해아주자세한지형의정보가드러나지는않지만전반적인외양이나주요한특징들은비교적잘나타남을알수있다. [ 그림 3-12] 은 3,408,187개의샘플데이터를가지는 LIDAR 데이터를렌더링한영상이며 [ 그림 3-13] 은이를활용하여가상환경시스템을구축한예이다. 일반적으로규칙데이터에서의쿼드트리기반의연속적인상세단계기법은실시간에지형을렌더링한다. 따라서본연구에서와같이대용량의비규칙데이터라하더라도기하재구성의과정을수행한다면빠르게지형을렌더링할수있음을알수있다. - 23 -
(a) 데이터를점으로표현한영상 (b) Delaunay triangulation 방법의와이어프레임 ( 좌 ) 과셰이딩 ( 우 ) 결과영상 (c) 제안한방법의와이어프레임 ( 좌 ) 과셰이딩 ( 우 ) 결과영상 [ 그림 3-11] 34,379 개의샘플데이터의 LIDAR 데이터지형렌더링비교영상 - 24 -
(a) 와이어프레임모델 (b) 고도값에따른셰이딩결과영상으로높은고도값을지닐수록밝게 표현된다. [ 그림 3-12] 3,408,187 개의인하대학교 LIDAR 데이터지형렌더링결과영상 - 25 -
[ 그림 3-13] 본논문의방법을이용한지형시뮬레이션결과영상 - 26 -
제 5 장결론및향후과제 GIS, 비행시뮬레이션및가상현실시스템등의분야에서지형데이터의표현은중요한요소이므로빠르고현실감있는지형렌더링의처리기법연구는필수적이라고할수있다. 최근 LIDAR 데이터와같은방대한양의고해상도비규칙지형데이터를손쉽게얻을수있으나기존의방법으로는실시간에렌더링하기가어렵다. 따라서본논문에서는비규칙데이터의기하재구성을통하여실시간렌더링에적합한쿼드트리자료구조를활용할수있는방법을제안하였다. 기하재구성은입력데이터로부터의잡음을제거한후, 데이터의공간적분포를이용한규칙격자생성및격자의크기와간격에따른재샘플링의정규화단계를수행한후쌍선형보간법을통하여영상에서발생할수있는틈을없앤다. 이와같이단위격자형태로재구성된데이터는쿼드트리기반의연속적인상세단계기법으로지형을렌더링한다. 실험을통하여비규칙데이터에서도기하재구성과정을통하여실시간렌더링기법들이적용가능함을확인할수있었다. 특히 LIDAR 데이터와같은방대한양의지형데이터라하더라도기하재구성에소요되는시간이짧았으므로, 기존방법에비해지형을모델링하는시간이빠르다는것을알수있었다. 또한렌더링하는데있어빠른속도의프레임율을보였으므로실시간에지형을가시화하는시스템의목적과도부합된다. 화질역시지형의주요특징들을나타낸결과영상을비교하여차이가없음을확인하였다. 향후연구과제로는서로다른공간분포를보이는비규칙데이터라할지라도자동으로임계치가설정될수있도록하는연구가필요할것이다. 또한기하재구성과정의소요시간을좀더단축하기위한하드웨어기반의렌더링방법에대한연구가필요하다. - 27 -
참고문헌 [1] R. Pajarola, E. Zurich, "Large Scale Terrain Visualization Using the Restricted Quadtree Triangulation", Proceedings of IEEE Visualization 98, pp. 19-24, 1998. [2] M. Duchaineau, M. Wolinsky, D. E. Sigeti, M. Miller, C. Aldrich and M. B. Mineev-Weisstein, "ROAMing Terrain: Real-time Optimally Adaptive Meshes", Proceedings of IEEE Visualization 97, pp. 81-88, 1997. [3] V. Tsai, Delaunay triangulations in TIN creation : an overview and a linear-time algorithm, International Journal of Geographical Information Systems, pp. 501-524, 1993. [4] S. Rottger, W. Heidrich, P. Slasallek and H. Seidel, Real-time Generation of Continuous Level of Detail for Height Fields, Proceedings of 6th International Conference in Central Europe on Computer Graphics and Visualization, pp. 315-322, 1998. [5] P. Lindstrom, D. Koller, W. Ribarsky, L. F. Hodges, N. Faust and G. A. Turner, Real-Time Continuous Level of Detail Rendering of Height Fields, Proceedings of SIGGRAPH 96, pp. 109-118, 1996. [6] F. Aurenhammer. "Voronoi diagrams: A survey of a fundamental geometric data structure" ACM Comput. Surv., no. 23, pp.345-450, 1991. [7] B. S. Shin and E. K. Choi, "An Efficient CLOD Method for Large-Scale Terrain Visualization", Lecture Notes in Computer Science, Volume 3166, pp. 592-597, 2004. [8] W. S. Cho, Y. S. Jwa, H. J. Chang and S. H. Lee, "Pseudo-Grid Based - 28 -
Building Extraction Using Airborne LIDAR Data", Proceedings of ISPRS 2004, Volume 35, pp. 298-301, 2004. [9] D. Cohen-Steiner, E. Colin de Verdiere and M. Yvinec, "Conforming Delaunay triangulations in 3D", Proceedings of 18th ACM Symposium on Computational Geometry, pp. 199-208, 2002. [10] L. Floriani, B. Falcidieno, C. Pienovi, Delaunay-based method for surface approximation, Proceedings of Eurographics 83, pp. 333-350, 1983. [11] M. Levoy, "Display of Surfaces from Volume Data", IEEE Computer Graphics and Applications, Volume 8, no. 3, pp. 29-37, 1988. [12] T. Ulrich, "Continuous LOD Terrain Meshing Using Adaptive Quadtrees", Gamasutra, 2000, http://www.gamasutra.com/features/200000228/ulrich_01. htm [13] 최이규, 신병석, " 깜빡임현상을최소화하는쿼드트리기반의 CLOD기법 ", 한국컴퓨터그래픽스학회 2003 추계학술대회, pp. 33-39, 2003. [14] B. Chen, J. E. Swan, E. Kuo, A. Kaufman, "LOD-Sprite Technique for Accelerated Terrain Rendering," Proceedings of IEEE Visualization 99, 291-298, 1999. [15] Y. J. Kim, B. S. Shin, "Efficient Terrain Rendering Using Irregular Dataset", Proceedings of ASGIS, pp. 21-28, 2005. [16] H. Fuchs, Z. Kedem, S. Uselton, "Optimal surface reconstruction from planar contours", Communications of the ACM, Volume 20, no. 10, pp. 693-702, 1977. [17] T. Akenine-Moller, E. Haines, "Real-Time Rendering", AKPETERS Ltd., Second Edition, 2002. - 29 -