Octgridに基づく 効率的な3D地形図生成法 ◎佐藤 雄一（東洋大学） 塩野 康徳（東洋大学） 土田 賢省（東洋大学） 夜久 竹夫（日本大学）
発表内容 1. はじめに 2. 準備 3. 3D地形図生成法 4. 考察 5. まとめ 6. 今後の課題 2009/3/19 電子情報通信学会2009年総合大会
１. はじめに 1. 1. 背景 1. 2. 目的 2009/3/19 電子情報通信学会2009年総合大会
1. 1. 背景(1/2) 地形の直感的な理解を補助する手段として，3D地形図がよく用いられている 2009/3/19 電子情報通信学会2009年総合大会
1. 1. 背景(2/2) 我々のプロジェクトは，解像度の異なる地形図データを，統一的かつ効率的に扱うことが目標 すでに我々は，いくつかの均一メッシュを結合し, 不均一メッシュを生成するアルゴリズムを考案 (Kenshi Nomaki, et al., “Octal graph representation of multi resolution 3D landform maps” SIAM Conf. Geometric Design & Computation, Nov. 2005, Phoenix, Arizona, USA.) 我々が開発を進めている地形図エディタは，解像度の異なる地形図データを，統一的かつ効率的に扱うことを目指している 2009/3/19 電子情報通信学会2009年総合大会
Octgridに基づく効率的な3D地形図の生成 1. 2. 目的 Octgridに基づく効率的な3D地形図の生成 2009/3/19 電子情報通信学会2009年総合大会
2. 準備 2. 1. 3D地形図 2. 2. 表の定義 2. 3. Octgridとは 2. 4. H7CODEとは 2009/3/19 電子情報通信学会2009年総合大会
2. 1. 3D地形図 地形を格子状に区切り，その格子の点上の標高データから生成したもの 本研究で扱う3D地形図とは，地形を格子状に区切りその格子の点上の標高データから生成したものである．図は３次元座標から３D地形図を表現した例とそのVRML 図１ 3次元座標から3D地形図を表現した例とそのVRML 2009/3/19 電子情報通信学会2009年総合大会
2. 2. 表の定義 周辺セル(perimeterセル)を表の周囲に持つ形で表を定義 周辺セルは，幅と高さの一方または，両方が０ 表の周辺に周辺セルを持たせた形で表を定義されてます． 周辺セルとは，幅と高さの一方もしくは両方が０でのセルです 図2. 2 周辺セルを持った表の例 2009/3/19 電子情報通信学会2009年総合大会
2. 3. Octgridとは ノードの最大次数は8 図２ 矩形図とそれに対応するoctgrid 最大次数が８などの特徴を持つ． 図２ 矩形図とそれに対応するoctgrid 2009/3/19 電子情報通信学会2009年総合大会
2. 4. H7CODEとは Octgridによりモデル化された3次元地形図のためのリスト型のデータ構造 局所的かつ動的な解像度の変化，平坦な地形や起伏の激しい地形に応じた解像度の変化に対応するために作られた を目的に作られた 2009/3/19 電子情報通信学会2009年総合大会
3. 3D地形図生成法 3. 1. 単位セルと単位セルでないセル 3. 2. 均一領域と不均一領域 3. 3. 3D地形図生成法の流れ 3. 4. 不均一領域抽出アルゴリズム 3. 4. 1. 不均一領域抽出アルゴリズムフェーズⅠ 3. 4. 2. 不均一領域抽出アルゴリズムフェーズⅡ 3. 4. 3. 不均一領域抽出アルゴリズムフェーズⅢ 3. 5. 不均一領域抽出アルゴリズムの計算量 3. 6. 不均一領域のポリゴン生成 3. 7. 均一領域のポリゴン生成 3. 8. ポリゴンの合成 2009/3/19 電子情報通信学会2009年総合大会
3. 1. 単位セルと単位セルでないセル 図3. 1 単位セルと単位セルでないセルの例 地形図の中で基準となる大きさの辺をもつセルと単位セルと呼びます． 単位セルではないセルとは，単位セルが複数結合されてできるセルのことです． 図3. 1 単位セルと単位セルでないセルの例 2009/3/19 電子情報通信学会2009年総合大会
3. 2. 均一領域と不均一領域 図3. 2 均一領域と不均一領域の例 単位セルのみで構成される領域を均一領域と呼びます． 単位セルでないセルを含む領域を不均一領域と呼びます． また，不均一領域はポリゴンを合成する際，ポリゴン同士の重なりがないようにするために矩形である必要があるため，DとEは単位セルですが，矩形を形作るために不均一領域の一部として扱われます． 図3. 2 均一領域と不均一領域の例 2009/3/19 電子情報通信学会2009年総合大会
3. 3. 3D地形図生成方法の流れ(1/2) 図４ 3D地形図生成の流れ 地形の標高データを読み込んで，H7CODEに変換 変換されたデータに対して均一領域か不均一領域かを識別 不均一領域に対してはドロネー三角形分割を用い，均一領域に対してはH7CODEの構造を用いて三角形分割し，それぞれのポリゴンを生成 それらを合成し，1つのVRMLファイルを作成 図４ 3D地形図生成の流れ 2009/3/19 電子情報通信学会2009年総合大会
3. 3. 3D地形図生成方法の流れ(2/2) Input : 解像度の異なる（不均一領域を含む） 地形図データ Output: 地形図データ全体のVRMLファイル 地形の標高データを読み込んで，H7CODEに変換 変換されたデータに対して均一領域か不均一領域かを識別 不均一領域に対してはドロネー三角形分割を用い，均一領域に対してはH7CODEの構造を用いて三角形分割し，それぞれのポリゴンを生成 それらを合成し，1つのVRMLファイルを作成 2009/3/19 電子情報通信学会2009年総合大会
3. 4. 不均一領域抽出アルゴリズム(1/3) Ⅰ Octgridのノード情報から，リスト型のデータ構造 Corner Point Structureを作成 →不均一領域抽出アルゴリズムフェーズⅠ Ⅱ Corner Point Structureに均一，不均一情報などを追加 →不均一領域抽出アルゴリズムフェーズⅡ Ⅲ 不均一領域の拡大，抽出 →不均一領域抽出アルゴリズムフェーズⅢ 2009/3/19 電子情報通信学会2009年総合大会
3. 4. 不均一領域抽出アルゴリズム(2/3) Corner Point Structureとは 抽出アルゴリズムで用いる点（Corner Point）のID,位置情報，Corner Point間のリンク，Corner Point周り4象限の情報を持つデータ構造 2009/3/19 電子情報通信学会2009年総合大会
3. 4. 不均一領域抽出アルゴリズム(3/3) Input: H7CODEファイル Output: 不均一領域 Ri 2009/3/19 電子情報通信学会2009年総合大会
3. 4. 1. 不均一領域抽出アルゴリズムフェーズⅠ 10 20 x 10 y ID x y up low left right 1 10 20 表3. 4. 1 Corner Point Structureの内部データ構造の例 x ID x y up low left right 1 null 2 4 10 3 5 6 20 10 y 各セルの４隅のｘｙ座標を左上から反時計回りに抽出し，その順にポイントのidをつけていく．その後リンクをつくる． 同様に２つ目のセルも情報を得るが，同じｘｙ座標のデータがある場合は，その部分をスキップしてデータを取得しリンクをつくる． 内部のデータ構造はこのような感じです 1 4 6 2 3 5 図3. 4. 1 Corner Pointの作り方 2009/3/19 電子情報通信学会2009年総合大会
3. 4. 2. 不均一領域抽出アルゴリズムフェーズⅡ(1/3) 10 20 30 1 4 2 6 5 7 9 8 均 不 10 3 均 不 どのように均一領域か不均一領域化を判定していくかを説明します． まずは3のポイントを中心に見ていきます． 第一象限の情報を得るために，右と上のエッジをたどり，その情報を用いて不均一領域と判定します． 同様に第二象限，第三象限，第四象限についても情報を得，均一不均一の判定を行います． 20 図3. 4. 2. 1 4象限の均一，不均一データの例 2009/3/19 電子情報通信学会2009年総合大会
3. 4. 2. 不均一領域抽出アルゴリズムフェーズⅡ(2/3) Ｐ Ｐ Ｐ Ｐ 1 4 3 2 7 5 6 8 Ｐ Ｐ Ｐ Ｐ Ｐ Ｐ 具体的にどのような流れで，情報を持たせていくかを説明します． まずはポイントid１のポイントから反時計回りに一番外側のエッジをたどり，外側の象限をペリメーターとしてデータを格納します． Ｐ Ｐ Ｐ Ｐ Ｐ Ｐ Ｐ Ｐ 図3. 4. 2. 2 周辺セルデータの格納例 2009/3/19 電子情報通信学会2009年総合大会
3. 4. 2. 不均一領域抽出アルゴリズムフェーズⅡ(3/3) Ｐ Ｐ Ｐ Ｐ 1 4 3 2 7 5 6 8 1 4 Ｐ 不 不 Ｐ Ｐ 不 不 不 不 Ｐ 2 7 3 Ｐ 均 均 均 均 Ｐ このようにId毎に4証言のｐｐｐｐｐｐｐｐｐｐ Ｐ 均 均 均 均 Ｐ 5 6 8 Ｐ Ｐ Ｐ Ｐ Ｐ Ｐ 図3. 4. 2. 3 均一，不均一データの格納例 2009/3/19 電子情報通信学会2009年総合大会
3. 4. 3. 不均一領域抽出アルゴリズムフェーズⅢ(1/2) 不均一領域を拡張する場合のパターン 均 不 均 不 不 均 図3. 4. 3. 1 不均一領域拡張の６パターン 2009/3/19 電子情報通信学会2009年総合大会
3. 4. 3. 不均一領域抽出アルゴリズムフェーズⅢ(2/2) P P P P P P P 均 不 不 均 不 不 P P 均 不 不 均 不 不 不 不 P P 不 不 不 不 不 均 均 不 P 不 不 均 不 均 P 不均一領域を拡張する場合のパターン 不 不 均 不 均 P P 不 不 均 不 不 均 P P P P P P P 図3. 4. 3. 2 不均一領域拡張の例 2009/3/19 電子情報通信学会2009年総合大会
3. 5. 不均一領域抽出アルゴリズムの計算量 不均一領域抽出アルゴリズムフェーズⅠ →O(n) 不均一領域抽出アルゴリズムフェーズⅡ 不均一領域抽出アルゴリズムフェーズⅢ →O(n) （予想） 全体としても O(n)であることが予想される． ただし，nはノードの個数である． 2009/3/19 電子情報通信学会2009年総合大会
G1 G2 3. 6. 不均一領域のポリゴン生成 R1 R2 図5 不均一領域のポリゴン生成法 今回はこのR1のまわりに単位セル分拡張した領域G1でドロネー三角形分割してポリゴンを生成します． R2についても同様に，拡張した領域G2で三角形分割していきます． R2 図5 不均一領域のポリゴン生成法 2009/3/19 電子情報通信学会2009年総合大会
3. 7. 均一領域のポリゴン生成 図3. 7 均一領域のポリゴン生成法 以下のR1がこれらのアルゴリズムを利用して抽出した不均一領域です． 今回はこのR1のまわりに単位セル分拡張した領域G1でドロネー三角形分割してポリゴンを生成します． R2についても同様に，拡張した領域G2で三角形分割していきます． 図3. 7 均一領域のポリゴン生成法 2009/3/19 電子情報通信学会2009年総合大会
3. 8. ポリゴンの合成 図７ ポリゴンの合成 図 7の通り，ポリゴン同士が重なることなく領域をカバーできる 2009/3/19 図７ ポリゴンの合成 2009/3/19 電子情報通信学会2009年総合大会
4 . 考察(1/5) ドロネー三角形分割 VRML ＋H7CODEを用いた三角形分割 ・データ量で優位 →O(NlogN) と O（N） 地形図データ 均一と不均一メッシュデータ 均一メッシュデータ ドロネー三角形分割 ＋H7CODEを用いた三角形分割 →O(NlogN) と O（N） →O(NlogN) 各々の三角形分割 VRML ・データ量で優位 ・計算量で優位 我々の手法が効果的であると推定される場合の例を図 5. 2. 1に記す．これは秋田県の田沢湖の3D地形図である． この3D地形図は200×200のメッシュから生成され，ポリゴン数は79202である．ここで，湖の部分は不均一領域として一つの大きなセルとし，他の部分は均一領域として均一なメッシュとする．具体的には，湖の中の95×80個のメッシュを1つのセルに結合する．そして我々の手法を用いてポリゴンを生成した場合，ポリゴン数が64004になり，15198個のポリゴンが削減され19％ほどデータ量を減らすことが可能と推定される． 図4. 1 他手法との比較 2009/3/19 電子情報通信学会2009年総合大会
4 . 考察(2/5) メッシュ数200×200でポリゴン数は79202 我々の手法を用いてポリゴンを生成した場合，ポリゴン数が64004になり，15198個のポリゴンが削減され19％ほどデータ量を減らすことが可能と推定 我々の手法が効果的であると推定される場合の例を図 5. 2. 1に記す．これは秋田県の田沢湖の3D地形図である． この3D地形図は200×200のメッシュから生成され，ポリゴン数は79202である．ここで，湖の部分は不均一領域として一つの大きなセルとし，他の部分は均一領域として均一なメッシュとする．具体的には，湖の中の95×80個のメッシュを1つのセルに結合する．そして我々の手法を用いてポリゴンを生成した場合，ポリゴン数が64004になり，15198個のポリゴンが削減され19％ほどデータ量を減らすことが可能と推定される． 図8 本手法が効果的であると予想される場合の例 2009/3/19 電子情報通信学会2009年総合大会
4 . 考察(3/5) 50×50の均一メッシュA Aの中の33×20のセルを１つに結合したメッシュB 2009/3/19 電子情報通信学会2009年総合大会
4 . 考察(4/5) 50×50の均一メッシュA Aの中の33×20のセルを１つに結合したメッシュB ポリゴン数３５８４ ポリゴン数５００２ 図4. 3 本手法が効果的であるメッシュデータAとBのポリゴン 2009/3/19 電子情報通信学会2009年総合大会
4 . 考察(5/5) ・不均一領域全体にドロネー三角形分割を用いた場合の計算量 →O(nlogn) ・本手法を用いた場合の計算量 ドロネー三角形分割 H7CODEを用いた三角形分割 → O(n) 一定量以上，均一領域が存在した場合速くなる 図4. 4 本手法の計算量の考察例 2009/3/19 電子情報通信学会2009年総合大会
5 . まとめ Octgridによりモデル化されたH7CODEに基づく3D地形図生成法の基本設計 不均一領域抽出アルゴリズムの提案 発表する予定です ．３月の・・・ 2009/3/19 電子情報通信学会2009年総合大会
6 . 今後の課題 本手法のエディタ上での実現 不均一領域抽出アルゴリズムの計算量の数学的証明 quadtreeなどで用いられる既存のアルゴリズムとの比較 2009/3/19 電子情報通信学会2009年総合大会
2009/3/19 電子情報通信学会2009年総合大会
2009/3/19 電子情報通信学会2009年総合大会
2009/3/19 電子情報通信学会2009年総合大会
2. 3．Octgridとは(2/2) 辺の位置が等しく， 最も近いセルとの関係をエッジで定義 図2. 3 辺の位置が等しい関係 図の一番上のｂ，ｃはともに北壁が等しいため，ノースウォールエッジで結ぶ． 以下，すべて同様である． 図2. 3 辺の位置が等しい関係 2009/3/19 電子情報通信学会2009年総合大会
3. 4. 2．不均一領域抽出アルゴリズムフェーズⅡ(1/5) 均一不均一の全パターン（ぺりメーターをふくまない） 図3. 4. 2. 1 Corner Point周りの均一，不均一のパターン 2009/3/19 電子情報通信学会2009年総合大会
3. 4. 2．不均一領域抽出アルゴリズムフェーズⅡ(3/5) 均一不均一のデータの受け渡しについて説明します． エッジがつながっているポイント間の第三象限，第四象限と，第二象限，第一象限の均一不均一情報と第一象限第四象限と第二象限第三象限の均一不均一情報が等しいことを利用し，北と西にリンクしているポイントがそれらの情報を格納している場合そのデータを取得します． その後第四象限に対して，均一不均一の判定を行い，それらを合わせたデータを東と南のリンク先のポイントに受け渡します． 不 不 図3. 4. 2. 3 均一，不均一データの受け渡し方 2009/3/19 電子情報通信学会2009年総合大会
不均一領域抽出アルゴリズム 各pointごとの，周り4象限の均一，不均一の判定 1 4 3 2 6 5 9 7 8 10 2009/3/19 電子情報通信学会2009年総合大会
不均一領域抽出アルゴリズム 1 4 3 2 6 5 9 7 8 Ｐ Ｐ Ｐ Ｐ Ｐ Ｐ 10 Ｐ Ｐ Ｐ Ｐ Ｐ Ｐ Ｐ Ｐ Ｐ Ｐ Ｐ Ｐ 2009/3/19 電子情報通信学会2009年総合大会
不均一領域抽出アルゴリズム 1 4 3 2 6 5 9 7 8 Ｐ Ｐ Ｐ Ｐ Ｐ Ｐ 10 Ｐ 不 不 均 均 Ｐ Ｐ 不 不 不 不 均 2009/3/19 電子情報通信学会2009年総合大会
2. 4．H7CODEとは(2/3) 図3 H7CODEのノード 2009/3/19 電子情報通信学会2009年総合大会
2. 4．H7CODEとは(3/3) ノード番号 周辺セル リンク情報 位置座標 図 H7CODEのファイル例 標高 2009/3/19 電子情報通信学会2009年総合大会
3. 4．均一領域のポリゴン生成(2/2) 均一領域部分で三角形分割を行う場合は，次の2パターンのみであり，H7CODEの構造を用いてポリゴンを容易に生成が可能 Ｃ Ｃ Ｃ Ｃ 2009/3/19 電子情報通信学会2009年総合大会
3. 6．均一領域のポリゴン生成 Ｃ Ｃ Ｃ Ｃ 均一領域部分で三角形分割を行う場合について説明します． 次の2パターンのみであり，H7CODEの構造を用いてポリゴンを容易に生成が可能 Ｃ 2009/3/19 電子情報通信学会2009年総合大会
スライス構造と非スライス構造 スライス構造 非スライス構造 2009/3/19 電子情報通信学会2009年総合大会
quadtree NE SE SW NW 2009/3/19 電子情報通信学会2009年総合大会
quadtree 2009/3/19 電子情報通信学会2009年総合大会
計算量 ・ドロネー三角形分割の計算量 →O(nlogn) ・H7CODEを用いて三角形分割した場合の計算量 →O(n) ・本手法を用いた場合の計算量 → O(n) 以上 O(nlogn) 以下 2009/3/19 電子情報通信学会2009年総合大会
不均一領域抽出アルゴリズムの計算量 不均一領域抽出アルゴリズムフェーズⅠ →O(n) 不均一領域抽出アルゴリズムフェーズⅡ 不均一領域抽出アルゴリズムフェーズⅢ 全体としてもO(n)であることが予想されている 2009/3/19 電子情報通信学会2009年総合大会
2009/3/19 電子情報通信学会2009年総合大会
3. 4. 3．不均一領域抽出アルゴリズムフェーズⅢ(2/2) P P P P P P P 均 不 不 均 不 不 P P 不 均 不 均 不 不 不 不 P P 不 不 不 不 不 均 不 均 P 不 均 不 不 均 P 不均一領域を拡張する場合のパターン 不 均 不 不 均 P P 不 不 均 不 不 均 P P P P P P P 2009/3/19 電子情報通信学会2009年総合大会