本研究の目的、本論文の構成を述べる。

　GISの歴史と今後の発展について論じる。

　従来の二次元データと高さ情報を用いた三次元的な応用例は,幾つが報告されている.その内部的な実現として,二次元または三次元の空間データ構造が用いられているが,いずれにも問題が存在する.まず,二次元データ構造を用いる場合,二次元データだけがデータ構造に保持される.高さ情報は,非空間属性として,空間データ構造から分離されてしまう.従って,三次元空間検索に対して,効率よく実現することができない.一方,三次元データ構造は,二次元データを直接に管理することができないため,二次元データと高さ情報から,三次元データを求める処理が必要である.しかしながら,求めた三次元データの量は,約8/9の余計なものを含み,元の9倍である.GISのような大規模なデータを扱うシステムには,これは大変な問題になる.この二つの問題点の原因としては,高さに対する見方が間違ったと考えられる.高さ情報は,空間データであるが,座標データに属さない.従って,高さ情報を非空間データあるいは座標データとした管理方式は,適切ではない.即ち,二次元または三次元データ構造は,二次元座標と高さ情報が混在するデータに対して,適用できない.これに対して,本論文は,2.5次元の管理方式を提案する.

　まず,空間データと座標データをより厳密に区別するため,空間データをオブジェクトの幾何的な性質を記述する全ての情報と再定義する.この定義によって,高さ情報も,座標データも空間データの一部になる.しかも,空間データは必ずしも座標データではない.次に,各オブジェクトに対し,そのXY-平面とZ-軸方向の形状を,それぞれ一組の2次元座標データと一つの高さ情報で記述する.このようなデータを2.5次元空間データと呼ぶ.また,空間データ構造は,座標データのみではなく,全ての空間データを管理するべしという主張点により,2次元データ構造に高さ情報を追加する.具体的には,空間データ構造の一種であるGBD木というデータ構造を用いて,対象物を二次元投影形状と,その高さ情報で管理する.GBD木の各ノードに,そのノードより下位の構造に記録されている全ての対象物の高度の最下値(height_min)と最上値(height_max)を記録しておき,これを参照しつつデータの絞り込みを行う.二次元GBD木では木構造の各ノードに,そのノードの下位に位置する全ての図形を内包する,最もタイトな長方形情報(外接長方形)が記録されている.通常は,このデータを手がかりにして,検索対象データの絞り込みを行うが,この外接長方形と先に述べた高さ方向の最下値,最上値間の範囲で作られる三次元空間(以下この空間をMBB:Minimum Bounding Boxと呼ぶ)を用いて,三次元的なデータの絞り込みを効率的に行う.つまり,検索時に検索範囲と各ノードのMBBとの交差比較を行い,両者が重なり合えばより下位のノードまでたどり,詳細な交差比較を行う.またもし,両者が重なりを持たない場合は,そのノードより下位に存在する図形と検索範囲とは重なりを持たないことが保証され,それらの検索を省略できる.これらのMBBは,三次元な範囲であるので,三次元的な検索を完全にサポートすることができる.MBBからみれば,2.5次元GBD木と3次元R木は外見的に似通っている.しかしながら,2.5次元GBD木では,ノードの分割と合併がZ-軸で起こらない,その上,全てのMBBがXY-平面に接するという特徴があるため,三次元データ構造とは,根本から違っている.この管理構造によって,無駄なデータを増やせず,3次元検索を効率よく実現することができる.

　2.5次元データ構造に基づいて,GISアプリケーションのためのグラフィックカーネルを構築する.カーネルシステムの全体は,オブジェクト指向言語C++で実装した.移植性を保持するため,システムを本体とインタフェース部の二つ部分に大きく分ける.本体は,図形データやGISの対象物を表現するクラスライブラリ群と空間データを管理する2.5次元GBD木から構成される.インターフェース部は,表示部とファイル入力部から構成される.また,クラスライブラリは,更に幾何ライブラリ(geometric library),コンテナ(containers),GISオブジェクトライブラリ(geographic object library)に分けられる.全てのオブジェクトは,2.5次元GBD木に暗黙的に管理される.また,オブジェクト間の隣接関係は,オブジェクトの中心点を母点としたボロノイ図(Voronoi diagram)により,定義される.この定義を実現するため,動的にドロネーネーバー(Delaunay neighbors)を検出する方法を開発した.これによって,ボロノイ図の全体を保持せず,隣接オブジェクトを動的に求めることができる.膨大なデータを持つGISには,特に適用である.

　上述のGISカーネルシステムの有効性と効率を検証するため,三次元ウォークスルーの応用例を実現した.ウオークスルーにおいては.表示の実時間性が重要である.品質の劣化を容認しても1秒当たり数フレームの生成が望まれる.しかし,表示を必要とする建物などのオブジェクトの数が多い場合,これを実現することは困難であり,オブジェクト数の限定が必要となる.本論文では,表示するオブジェクト数を限定する方法として描画精度を調整する表現方式提案する.ウォークスルーで生成する画面を考えたとき,遠く離れたものは詳細に表現されている必要はない.それらは,近づいていったときに(必要なら)詳しく見えればよい.このような観点にたったとき,遠く離れたものは複数のものが一つにまとめられて表現されていても良く,近くのものが詳しく表現されていればよいことになる.オブジェクトをまとめる方法としては,上述の拡張GBD木に付加した三次元MBBの情報が利用できる.元々のMBBは,検索対象のオブジェクトを絞り込むためのものであり,各ノードの下位構造に格納されている図形データ群を内包する,タイトな直方体の形状情報である.視点を変えると,このMBBの形状はあるノードの下位構造に含まれるオブジェクトをまとめて表示する際の概略形状を示していることになる.従って,遠くに離れたオブジェクトはこのMBBの形状を表示することにより近似表現できることになる.これにより,同時に表示すべきオブジェクトの数は減少し,レンダリングに要する処理時間も減少させることができる.本表現手法の実現によって、2.5次元管理方式の三次元アプリケーションへの支援が有効であることが明らかになる。

　最後に、本研究において、得られた結論を述べる。