區塊式LOD網格細化於大型地形視覺模擬之應用

Tile-Based Mesh Refinement for Large 3D Terrain Visualization

邱煥智(Huan-chih Chiu)

指導教授 ： 蔡富安

國立中央大學/工學院/土木工程學系/碩士(2008年)

摘要

虛擬城市視覺化或三維地理資訊系統中，地形是最重要的成像元素之ㄧ。然而大型地形成像經常遇到兩個難題，包括資料量過大及地形網格解析度過高。以層級精細度(LOD)建置多解析度地形網格並根據視覺條件展現合理精細層級是常用的解決方式，但是仍有許多待克服之難題。本研究延續先前類似作法，以區塊式網格細化處理地形成像；利用前處理產生多重層級的LOD地形區塊，視覺模擬時可經過視覺條件判斷，載入適當的層級資料成像。
研究重點在於改良舊有區塊式LOD之資料處理與成像運算之缺點，以建立高效能的大型地形視覺模擬系統。在資料處理部份，本研究延續先前區塊式LOD方法，以像空間近似誤差概念為基礎進一步開發新門檻值設定方式，可有效地根據成像條件合理地設定四分樹分割的門檻值，並與視覺重要性相連結。此外，進行大範圍地形視覺模擬時只有一組少數層級的LOD仍顯不足，而使用多層級的LOD則大幅增加前處理工作及資料儲存空間，造成成像處理時的浪費；因此本研究開發ㄧ二段式LOD方式，其概念是建立另一組更粗糙的LOD層級組專供成像初期快速顯像，以提高大範圍成像的效率。在即時成像運算處理上，由於區塊間網格不連續(T-junctions)，造成視覺表現上的裂縫，因此本研究開發一套演算法即時移除。
實驗結果顯示本研究所研發的區塊式地形成像系統可讓使用者即時獲得大範圍地形視覺模擬結果。本研究提出的新門檻值可使資料前處理的四分樹分割更合理，且能確實依據視覺條件選擇合適地LOD層級。成像過程中的區塊間裂縫皆可即時移除，且對整體成像效率影響甚微。此外，於視覺模擬初始階段使用二段式LOD可有效提高成像效率。本研究採用兩組大範圍DEM資料進行測試，其結果皆顯示本系統能即時有效成像且產生無接縫的地形，提供使用近即時的地形視覺模擬應用。

關鍵字

地形視覺模擬 ； 層級精細度 ； 三維地理資訊系統 ； 四分樹分割 ； 區塊式網格細化

並列摘要

Three-Dimensional (3D) terrain rendering is one of the most important components in the visualization of cyber city and other 3D GIS applications. When dealing with large-area terrain visualization, the vast amount of data may exceed the rendering capability of graphic hardware and cause poor performance of the system. Most importantly, in real-time visualization applications, the data resolution is much higher than screen, thus resulting in data redundancy and lowering efficiency. Furthermore, it may produce aliasing artifacts when rendering dense meshes.
In order to reduce the number of polygons, tile-based approaches have become popular for large-area terrain visualization because the original DEM data can be pre-processed by tiles and only visible tiles need to be rendered in runtime. When rendering, the data will be loaded and rendered quickly without further effort for triangulation. In a previous study, a set of LODs was generated for each tile using a dynamic quadtree algorithm. When rendering the terrain, view frustum culling was used to decide visible tiles and computed view importance to assign suitable tile LOD. This study further improves the developed tile-based terrain visualization system. Firstly, the original thresholds for quadtree were determined by the height difference in each tile, but it is difficult to connect the LODs with view importance. A new thresholding scheme based on view-dependent image-space error metric is proposed to achieve more reasonable LOD generation.
Secondly, conventional LOD systems often divide the data set into small tiles geographically. This may result in poor performance or abrupt LOD changes when dealing with large-area visualization projects, especially during the initial stage. To address this issue, a discontinuous LOD system is developed to create a finer set of LOD tiles and a coarser LOD set for quick representation of large areas. The switch between the two LOD sets is established according to viewer altitude, distance and resolution dependency etc. Thirdly, when visualizing a terrain by mesh tiles, there are usually discontinuities along tile edges, causing so-called T-junctions among different tiles. A mesh-merging algorithm is also proposed to refine the determined LOD meshes in order to eliminate T-junctions. Augmented with these improvements, the developed system will produce seamless landscape scenes consisting of multiple tiles of different LOD layers more efficiently.
The developed tile-based terrain rendering system allows users to obtain near real-time visualization of large terrain data sets. The proposed new thresholding scheme based on Ground Sample Distance enables more reasonable quadtree-based LOD generation for data pre-processing. It also provides better relationship between the LOD generation and view-importance for determining appropriate LOD levels of visible tiles. The developed T-junction removal algorithm can eliminate discontinuities between adjacent tile meshes effectively and have little impact to the overall rendering performance. Using discontinuous LOD improves the performance significantly, especially during the initial stage of visualization. Test examples with two large DEM datasets conducted in this study demonstrate that the developed system can produce seamless rendered scenes with high performance in near real-time visualization applications.

並列關鍵字

Quadtree ； 3D terrain visualization ； LOD ； 3D GIS ； Mesh refinement

參考文獻

連翊涵，區塊式Level of Detail地景視覺模擬之研究，國立中央大學土木工程學系碩士論文，2006年。

劉濠雄，漸變式多重解析度於大型地景視覺模擬之應用，國立中央大學土木工程學系碩士論文，2007年。

Cignoni, P., E. Puppo, R. Scopigno, 1997. “Representation and visualization of terrain surfaces at variable resolution”, The Visual Computer, 13(5), pp. 199-217.

Cignoni, P., C. Montani, R. Scopigno, 1998. “A comparison of mesh simplification algorithms”, Computers & Graphics, 22(1), pp.37–54.

Cignoni, P., F. Ganovelli, E. Gobbetti, F. Marton, F. Ponchio, R. Scopigno, 2003. “BDAM - batched dynamic adaptive meshes for high performance terrain visualization”, Proceedings of EUROGRAPHICS, 22(3), pp. 505–514.