(57)【特許請求の範囲】
【請求項１】
３次元の地図を表示する表示手段を有する端末装置と、３次元表示のために各オブジェクトを、当該オブジェクトを構成する面ごとのポリゴンデータとして蓄積し、各ポリゴンに貼り付ける複数のテクスチャーの画像データをポリゴンごとに蓄積した３次元表示用データベースと、視点位置から見える各オブジェクトの面を選択するポリゴン選択手段と、選択されたポリゴンに対応するテクスチャーをグルーピングするテクスチャー処理手段と、を備えた経路探索サーバとを備えたナビゲーションシステムであって、
前記テクスチャー処理手段は、前記ポリゴン選択手段が選択したポリゴンに対応するテクスチャーから共通する画像データであるテクスチャーをテクスチャーグループとして抽出し、前記抽出したテクスチャーグループにユニークな識別符号を決定し、そのうちの１つのテクスチャーの画像データを配信データとし、他の共通のテクスチャーは前記識別符号を配信データとし、共通する画像データがないテクスチャーは画像データのまま配信データとし、前記ポリゴン選択手段が選択したポリゴンとともに、前記端末装置に配信することを特徴とするナビゲーションシステム。
【請求項２】
前記ナビゲーションシステムは、更に、視点位置を設定する視点位置設定手段を備え、
前記視点位置設定手段が設定した視点位置に基づいて、前記ポリゴン選択手段は、当該視点位置から所定の範囲内のポリゴンデータを対象に当該視点位置から見える各オブジェクトの面を選択し、前記表示手段は前記ポリゴン選択手段が選択した面のポリゴンと前記テクスチャー処理手段が配信データとしたテクスチャーに基づいて、前記選択されたポリゴンに対応するテクスチャーを貼り付けて地図を３次元表示することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項３】
前記面ごとのポリゴンデータは、それぞれその表面方向を示す法線ベクトルを含み、前記ポリゴン選択手段は、前記視点位置から前記オブジェクトの各面を見込むベクトルを生成し、当該ベクトルと前記法線ベクトルとがなす角度を算出し、算出した角度が９０°以下の面を選択することを特徴とする請求項１に記載のナビゲーションシステム。
【請求項４】
前記ナビゲーションシステムは、更に、経路探索のための探索用ネットワークデータと、経路探索手段と、を備え、前記視点位置設定手段は、前記経路探索手段が探索した案内経路の所定の位置を視点位置とし、前記ポリゴン選択手段は、該視点位置から所定の範囲内のポリゴンデータを対象に当該視点位置から見える各オブジェクトの面を選択することを特徴とする請求項２に記載のナビゲーションシステム。
【請求項５】
経路探索サーバから配信されるポリゴンデータとテクスチャーデータに基づいて３次元の地図を表示する表示手段を有する端末装置とネットワークを介して接続される経路探索サーバであって、
前記経路探索サーバは、３次元表示のために各オブジェクトを、当該オブジェクトを構成する面ごとのポリゴンデータとして蓄積し、各ポリゴンに貼り付ける複数のテクスチャーの画像データをポリゴンごとに蓄積した３次元表示用データベースと、視点位置から見える各オブジェクトの面を選択するポリゴン選択手段と、選択されたポリゴンに対応するテクスチャーをグルーピングするテクスチャー処理手段と、を備え、
前記テクスチャー処理手段は、前記ポリゴン選択手段が選択したポリゴンに対応するテクスチャーから共通する画像データであるテクスチャーをテクスチャーグループとして抽出し、前記抽出したテクスチャーグループにユニークな識別符号を決定し、そのうちの１つのテクスチャーの画像データを配信データとし、他の共通のテクスチャーは前記識別符号を配信データとし、共通する画像データがないテクスチャーは画像データのまま配信データとし、前記ポリゴン選択手段が選択したポリゴンとともに、前記端末装置に配信することを特徴とする経路探索サーバ。
【請求項６】
前記経路探索サーバは、更に、視点位置を設定する視点位置設定手段を備え、
前記視点位置設定手段が設定した視点位置に基づいて、前記ポリゴン選択手段は、当該視点位置から所定の範囲内のポリゴンデータを対象に当該視点位置から見える各オブジェクトの面を選択し、前記表示手段は前記ポリゴン選択手段が選択した面のポリゴンと前記テクスチャー処理手段が配信データとしたテクスチャーに基づいて、前記選択されたポリゴンに対応するテクスチャーを貼り付けて地図を３次元表示することを特徴とする請求項５に記載の経路探索サーバ。
【請求項７】
前記面ごとのポリゴンデータは、それぞれその表面方向を示す法線ベクトルを含み、前記ポリゴン選択手段は、前記視点位置から前記オブジェクトの各面を見込むベクトルを生成し、当該ベクトルと前記法線ベクトルとがなす角度を算出し、算出した角度が９０°以下の面を選択することを特徴とする請求項５に記載の経路探索サーバ。
【請求項８】
前記経路探索サーバは、更に、経路探索のための探索用ネットワークデータと、経路探索手段と、を備え、前記視点位置設定手段は、前記経路探索手段が探索した案内経路の所定の位置を視点位置とし、前記ポリゴン選択手段は、該視点位置から所定の範囲内のポリゴンデータを対象に当該視点位置から見える各オブジェクトの面を選択することを特徴とする請求項６に記載の経路探索サーバ。
【請求項９】
３次元表示のために各オブジェクトを、当該オブジェクトを構成する面ごとのポリゴンデータとして蓄積し、各ポリゴンに貼り付ける複数のテクスチャーの画像データをポリゴンごとに蓄積した３次元表示用データベースと、視点位置から見える各オブジェクトの面を選択するポリゴン選択手段と、選択されたポリゴンに対応するテクスチャーをグルーピングするテクスチャー処理手段と、を備え、前記テクスチャー処理手段は、前記ポリゴン選択手段が選択したポリゴンに対応するテクスチャーから共通する画像データであるテクスチャーをテクスチャーグループとして抽出し、前記抽出したテクスチャーグループにユニークな識別符号を決定し、そのうちの１つのテクスチャーの画像データを配信データとし、他の共通のテクスチャーは前記識別符号を配信データとし、共通する画像データがないテクスチャーは画像データのまま配信データとし、前記ポリゴン選択手段が選択したポリゴンとともに配信する経路探索サーバにネットワークを介して接続される端末装置であって、
前記端末装置は前記経路探索サーバから受信したポリゴンデータとテクスチャーデータに基づいて地図を３次元表示する表示手段を備え、
前記表示手段は、前記ポリゴン選択手段が選択したポリゴンに対応する１つのテクスチャーの画像データと、その他の共通のテクスチャーは前記識別符号を参照することで、前記選択されたポリゴンに対応するテクスチャーを貼り付けて地図を３次元表示することを特徴とする端末装置。
【請求項１０】
前記端末装置は、更に、視点位置を検出する視点位置検出手段を備え、前記視点位置検出手段が検出した視点位置情報を前記経路探索サーバに送信することを特徴とする請求項９に記載の端末装置。
【請求項１１】
３次元の地図を表示する表示手段と、３次元表示のために各オブジェクトを、当該オブジェクトを構成する面ごとのポリゴンデータとして蓄積し、各ポリゴンに貼り付ける複数のテクスチャーの画像データをポリゴンごとに蓄積した３次元表示用データベースと、視点位置から見える各オブジェクトの面を選択するポリゴン選択手段と、選択されたポリゴンに対応するテクスチャーをグルーピングするテクスチャー処理手段と、を備えたナビゲーションシステムにおける地図表示方法であって、
前記ポリゴン選択手段が視点位置から見える各オブジェクトの面を選択する第１のステップと、
前記テクスチャー処理手段が、前記ポリゴン選択手段が選択したポリゴンに対応するテクスチャーから共通する画像データであるテクスチャーをテクスチャーグループとして抽出し、前記抽出したテクスチャーグループにユニークな識別符号を決定し、そのうちの１つのテクスチャーの画像データを配信データとし、他の共通のテクスチャーは前記識別符号を配信データとし、共通する画像データがないテクスチャーは画像データのまま配信データとする第２のステップと、
前記ポリゴン選択手段が選択したポリゴンとともに、前記テクスチャー処理手段が配信データとしたテクスチャーデータを端末装置に配信するステップと、を有することを特徴とする地図表示方法。
【請求項１２】
前記ナビゲーションシステムは、更に、視点位置を設定する視点位置設定手段を備え、
前記第１のステップは、前記視点位置設定手段が設定した視点位置に基づいて、前記ポリゴン選択手段が、当該視点位置から所定の範囲内のポリゴンデータを対象に当該視点位置から見える各オブジェクトの面を選択する処理を含み、前記表示手段が、前記ポリゴン選択手段が選択した面のポリゴンと前記テクスチャー処理手段が配信データとしたテクスチャーに基づいて、前記選択されたポリゴンに対応するテクスチャーを貼り付けて地図を３次元表示するステップを有することを特徴とする請求項１１に記載の地図表示方法。
【請求項１３】
前記面ごとのポリゴンデータは、それぞれその表面方向を示す法線ベクトルを含み、前記第１のステップは、前記ポリゴン選択手段が前記視点位置から前記オブジェクトの各面を見込むベクトルを生成し、当該ベクトルと前記法線ベクトルとがなす角度を算出し、算出した角度が９０°以下の面を選択する処理を含むことを特徴とする請求項１１に記載の地図表示方法。
【請求項１４】
前記ナビゲーションシステムは、更に、経路探索のための探索用ネットワークデータと、経路探索手段と、を備え、前記視点位置設定手段が、前記経路探索手段が探索した案内経路の所定の位置を視点位置とするステップを有し、前記第１のステップは、前記ポリゴン選択手段が該視点位置から所定の範囲内のポリゴンデータを対象に当該視点位置から見える各オブジェクトの面を選択する処理を含むことを特徴とする請求項１２に記載の地図表示方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、通信型のナビゲーションシステムや地図表示システムなどにおける３次元地図表示データに用いられるテクスチャーデータのダウンロード方式に関するものであり、特に、経路探索サーバが地図表示装置の現在位置や移動方向に基づいて、現在位置から見える面を判別してそのポリゴンデータを地図表示装置に送信する際に、当該ポリゴンの面に配置する各テクスチャーデータを、識別符号を付してグルーピングし、繰り返しパターンとなるテクスチャーデータは識別符号で表現して地図表示装置に送信し、テクスチャーデータの通信量を抑制するようにしたナビゲーションシステム、経路探索サーバ、端末装置および地図表示方法に関するものである。
【背景技術】
【０００２】
従来、見知らぬ土地において目的地となる場所を訪れる場合、地図帳等を頼りに当該地図に描かれた交通機関、道路やランドマーク及び住所を確認しながら到達していた。また、カーナビゲーションシステム（以後単にカーナビと言う）を搭載した自動車においては、該カーナビを起動して目的地を入力することによりナビゲーションシステムからモニタ画面に表示される案内や音声出力される案内（ナビゲーション情報）を得ながら目的地に到達していた。
【０００３】
上記カーナビは、ＧＰＳ（Global Positioning System：全地球測位システム）を利用したものであり、地球上を周回している複数のＧＰＳ衛星から送信されるＧＰＳ信号をＧＰＳアンテナで受信し、該ＧＰＳ信号に含まれる衛星位置や時計情報等を解析して位置の特定を行うものである。該複数のＧＰＳ衛星の個数は少なくとも４個以上必要である。ＧＰＳの単独測位精度は一般的に１０ｍ強であるが、ＤＧＰＳ（Differential GPS：ディファレンシャルＧＰＳ）を採用することにより５ｍ以下に向上する。特に、現在は一部の携帯電話にしか搭載されていないＧＰＳ受信機が、第三世代と称される携帯電話では全ての機種に搭載されるようになってきている。
【０００４】
このような測位機能を有する携帯端末の利用技術としては、種々の分野の技術が提案されており、例えば、自動車用のナビゲーション装置（カーナビ）を発展させ、携帯電話を端末として地図・経路情報を情報配信サーバ（経路探索サーバ）から配信する歩行者用の通信型ナビゲーションシステムが提案されている。
【０００５】
近年、携帯電話、ＰＨＳ等の携帯通信端末機器の性能は飛躍的に向上し、また、多機能化が進んでいる。特に通話機能の他にデータ通信機能が強化され、ユーザに対してインターネットを介した種々のデータ通信サービスが提供されている。ナビゲーションサービスもその１つであり、自動車の運転者のみならず携帯電話ユーザに対して現在位置から目的地までの経路案内を提供する通信ナビゲーションシステムが実用化されている。
【０００６】
一般的なナビゲーション装置、通信ナビゲーションシステムに使用される経路探索装置、経路探索方法は、例えば、下記の特許文献１（特開２００１−１６５６８１号公報）に開示されている。このナビゲーションシステムは、携帯ナビゲーション端末から出発地と目的地の情報を情報配信サーバに送り、情報配信サーバで道路網や交通網のデータから探索条件に合致した経路を探索して案内するように構成されている。探索条件としては、出発地から目的地までの移動手段、例えば、徒歩、自動車、鉄道と徒歩の併用などがあり、これを探索条件の１つとして経路探索する。
【０００７】
情報配信サーバは、地図データの道路（経路）をその結節点、屈曲点の位置をノードとし、各ノードを結ぶ経路をリンクとし、全てのリンクのコスト情報（距離や所要時間）をデータベースとして備えている。そして、情報配信サーバは、データベースを参照して、出発地のノードから目的地のノードに至るリンクを順次探索し、リンクのコスト情報が最小となるノード、リンクをたどって案内経路とすることによって最短の経路を携帯ナビゲーション端末に案内することができる。このような経路探索の手法としてはラベル確定法あるいはダイクストラ法と言われる手法が用いられる。上記特許文献１には、このダイクストラ法を用いた経路探索方法も開示されている。
【０００８】
一般的に通信型のナビゲーションシステムにおいて、端末装置が表示する地図情報は、ネットワークを介して接続される経路探索サーバなどのサーバ装置からダウンロードする。例えば、下記の特許文献２（特開２００３−２４７８３３号公報）や特許文献３（特開２００３−２３２６４４号公報）には、このような通信型のカーナビゲーション装置、地図データのダウンロード方式の発明が開示されている。
【０００９】
上記特許文献２に開示されたナビゲーション装置は、車両に走行中にサーバからの地図情報のダウンロードを許可するか否かを、ユーザが選択設定できるようにしたものであり、次のように構成される。端末側が次の地図を必要とするとき、これがメモリカードにダウンロードされているときには、これを用いて地図表示をする。次の地図情報がダウンロードされておらず、地図情報のダウンロードが許可されている場合には、サーバからこれをダウンロードし、メモリカードに書き込んで使用できる状態とする。しかし、ダウンロードが許可されていないときには、もともとメモリカードに格納されている広域地図を用い、その縮尺率を縮小することにより、拡大して表示するようにする。
【００１０】
また、上記特許文献３に開示された地図データのダウンロード方式は、一般道路か、高速道路か、インターチェンジ付近か又は高速走行中か低速走行中か等の、自動車の走行状態に応じて、ダウンロードセンターから送信される地図データ、すなわちダウンロードする地図データを選択してダウンロードするように構成したものである。これによりユーザが必ずしも必要としない多量の地図データがダウンロードセンター側から送信されることを抑制したものである。
【００１１】
ところで、経路探索サーバなどの情報配信サーバから案内経路の配信を受けた端末装置は液晶表示装置などの表示手段を備えており、表示手段に地図および案内経路を表示するとともに歩行者や自動車の現在位置（端末装置の現在位置）を案内経路上に表示して歩行者や自動車を目的地まで案内する。一般的に表示手段に表示する地図は平面図、すなわち、２次元図形の表示であるが、表示画像に遠近感をもたせた平面鳥瞰図やランドマークや建物の様子を視認し易くするため建物を擬似的に３次元的表現した鳥瞰図を表示する方法や、道路や建物をＺバッファ法により３次元ポリゴン画像として表示する方法も提案されている。
【００１２】
例えば、下記の特許文献４（特開２００１−２７５３５号公報）には、建物や道路を立体的に表示するようにした地図表示装置が開示されている。この特許文献４に開示された地図表示装置においては、３次元地図表示を行う際に、道路に経路案内線に影をつけて立体的に表示するように構成している。また、経路案内線が建物に隠れる位置関係となる場合、その経路案内線の重複部分について重複しない部分と色を変えて表示する。特に、ＶＲＡＭ（ビデオＲＡＭ）上で経路案内線の表示色と建物の表示色とを画素単位に互い違いに設定する半透過の手法で描画し、経路案内線と建物との相対的な位置関係を明確にして経路案内線の視認性を向上するようにしている。
【００１３】
上記のような表示を行うため、特許文献４に開示された地図表示装置において、地図データには、建物の形状データと高さ情報が記憶され、また、立体交差なども道路の形状データが記憶されている。この地図データに基づいて、建物や道路の立体交差部を描画部に３次元的に描画し、車両が進行し経路案内すべき位置に来ると描画部に所望の画像を描画した、音声出力部に所定の音声を発声させて、使用者を目的地へ案内するように構成している。
【００１４】
一般に、ポリゴンデータを用いた地図の３次元的な表示は次のように行われる。すなわち地図に表示するそれぞれの建物を構成する各面をポリゴンデータで準備しておき、地図データとともに建物のポリゴンデータを地図表示装置に送る。地図表示装は地図を表示するとともにその地図上に位置する各建物を、ポリゴンデータを使用して３次元的に表示するものである。この時、建物をよりリアルに表示するため、建物の各面に更にテクスチャーを張り付けて表示する。テクスチャーは建物の面の模様を示すデータであり、建物の窓の形状や、壁面の模様などである。
【００１５】
例えは、下記の特許文献５（特開２０００−２５９８６１号公報）には、ポリゴンデータにテクスチャーを貼り付けて描画するようにしたテクスチャーマッピング装置の発明が開示されている。この特許文献５に開示された発明は、ポリゴンにテクスチャーを正確かつ効率良く貼り付け、その後の編集を容易にするものであ。このテクスチャーマッピング装置は、ワイヤフレーム上のＭ行Ｎ列に配列された四角形のポリゴンＰ１〜Ｐ４とそれに貼り付けるテクスチャーを指定する。指定された複数のポリゴンＰ１〜Ｐ４の辺の長さＬｐ１〜Ｌｐ１２の比に応じて、貼り付け対象のテクスチャーを分割する。分割されたテクスチャーを、対応するポリゴンに、ポリゴンの向きを考慮して貼り付けるように構成したものである。
【００１６】
このようにポリゴンのデータとテクスチャーのデータを用いて建物を３次元表示する場合、建物の各面を示すポリゴンデータと、この面に張り付けるべきテクスチャーデータは１対１に対応するデータであり、ポリゴンデータとともにテクスチャーデータも予めサーバのデータベースに蓄積され、所定の範囲の地図データとともに、その地図上に表示すべき建物のポリゴンデータ、テクスチャーデータが地図表示装置に送信される。
【００１７】
ところで、大きなビルなどの建物の壁面（各面のポリゴン）に張り付けるテクスチャーは、繰り返し模様になる場合が多い。例えば、規則正しく配置された窓やバルコニーなどが多数、繰り返し配置されているテクスチャーの場合、テクスチャーの画像データを削減するために、繰り返し配置される窓やバルコニーの１つを代表テクスチャーとして用意することが行われる。この場合、代表テクスチャーの繰り返しになる全てのテクスチャーをテクスチャーグループとし、テクスチャーグループにはユニークな識別符号を付与して繰り返し配置するポリゴン上の位置のデータをデータベースに蓄積することが行われている。
【００１８】
通信型の地図表示システムやナビゲーションシステムにおいて、端末装置である地図表示装置に上記のような建物を３次元表示する場合、地図データや案内経路データを提供する経路探索サーバと端末装置間のデータ転送負荷が問題になる。クライアントである端末装置の数が多くなると、ネットワーク負荷が増大して、１端末あたりのサービス間隔が長くなり不都合が生ずる。
【００１９】
本願の出願人は、このような不都合を解消することを目的として、特願２００６−０７８６６９号（以下、先願１と称する）の発明を既に出願している。この先願１の発明にかかる３次元地図表示方法は、３次元表示する建物のポリゴンデータのうち、端末装置の位置および進行方向の情報に基づき、端末装置から見える面のポリゴンデータのみを経路探索サーバから端末装置に配信するように構成したものである。これにより経路探索サーバから端末装置に送信する建物のポリゴンデータのデータ量を抑制することができる。
【００２０】
図８は、先願１の３次元地図表示方法の概念を説明するため模式図である。建物のポリゴンは、図８に示すように建物を構成する面の図形データから構成されている。図８において、建物Ａは面ＳＡ１、ＳＡ２、ＳＡ３などの面の図形データから構成され、各面の向きを示す法線ベクトルを有している。例えば、建物Ａの面ＳＡ１は法線ベクトルＡ１を有している。また、図８では建物の裏側の面は見えていないが裏側の各面ＳＡ４、ＳＡ５、ＳＡ６のポリゴンデータが同じように用意されている。例えば、面ＳＡ１の裏側の面は面ＳＡ４であり、面ＳＡ１の法線ベクトルＡ１とは逆向きの法線ベクトルＡ４を有している。なお、この図８は空間の位置関係を説明するために作図したもので、端末装置２０に表示される画像ではない。
【００２１】
建物Ｂについても同様であり、面ＳＢ１〜ＳＢ６の面の図形データから構成され、各面の向きを示す法線ベクトルを有している。これらのポリゴン図形を表示するには、視点位置から各建物の面を見た場合、視点位置から注目する面を見込むベクトルとその面ポリゴンデータに含まれる法線ベクトルから、当該面が視点位置から見えている面か否かと、面の向いている方向を知ることができ、これに基づいてポリゴンを表示することができる。
【００２２】
例えば、図８の視点位置Ｐから注目する面が建物Ａの面ＳＡ１であるとすると、視点位置Ｐから面ＳＡ１を見込むベクトルＶＡ１をとる。このベクトルＶＡ１と法線ベクトルＡ１の成す角度θＡ１（両ベクトルの内積をとればよい）が直角未満であれば、この面の表面は視点方向に向いていることが分かる。従って、この面は表示手段に表示される面であることがわかる。ベクトルＶＢ１と法線ベクトルＢ１のように両ベクトルの成す角度が直角以上ならば、視点位置からは見えていない面であり、この面を表示手段に表示されないことがわかる。図８においてＥは視点位置の高さであり、歩行者が端末装置を使用している場合は、平均的な目の高さ（約１．５ｍ）である。
【００２３】
このように、端末装置２０が３次元の表示を行う場合、ポリゴンデータの全てが必要なわけではなく、視点位置から見えている面のポリゴンデータのみあれば足りるのである。そこで、先願１においては、端末装置が３次元表示を行う場合、端末装置から現在位置を含む視点情報を経路探索サーバに送信し、経路探索サーバが当該視点情報に基づいて表示に必要な面のポリゴンデータを選択して端末装置に配信するように構成している。端末装置においては、受信した面のポリゴンデータを基に、周知のＺバッファ法などを用いて、実際に視点から見える画像を描画していく。
【００２４】
【特許文献１】特開２００１−１６５６８１号公報（図１、図２）
【特許文献２】特開２００３−２４７８３３号公報（図１、図６）
【特許文献３】特開２００３−２３２６４４号公報（図１）
【特許文献４】特開２００１−２７５３５号公報（図１、図４、段落［００５４］）
【特許文献５】特開２０００−２５９８６１号公報（図２、図８）
【発明の開示】
【発明が解決しようとする課題】
【００２５】
先に述べたようにリアルな３次元表示は、特許文献５のように建物などの面を実際の形状を模したポリゴン（面のデータ）で表現するだけでなく、実際のイメージに近いテクスチャー（面の模様や細部の形状など）をポリゴン上に貼り付けることによって行う。このためには３次元表示用のデータベースに用意されることが必要である。テクスチャーは写真などを用いた実写によるイメージデータで用意することも考えられるが、実物と１対１に対応したデータではデータ量が多くなりすぎ、現実的ではない。
【００２６】
たとえば、マンションやオフィスビルに見られるような均一な繰り返しパターンのある画像は、それぞれ小さなテクスチャーを並べて用意されている。通信型のナビゲーションシステムや地図表示システムにおいて、端末装置で３次元表示を行う際には、このテクスチャーのデータが経路探索サーバや地図サーバなどのサーバから端末装置に送信されて、グラフィックエンジンが表示手段の所定の位置に３次元描画を行う。
【００２７】
サーバから端末装置に全ての３次元表示のためのデータ（ポリゴンデータ、テクスチャーデータ）を送信するのは通信負荷が増大するので好ましくない。ポリゴンデータについては、先願１に開示されたように、端末装置の現在位置、視点位置、進行方向を経路探索サーバに送信することにより、端末装置から見える建物の面を特定して、その面のポリゴンデータのみを端末装置に送信することで、経路探索サーバが端末装置に送信するデータ量を抑制することができる。
【００２８】
ポリゴンと同様に、サーバから端末装置に全てのテクスチャーを送信するのは無駄であり、同じイメージ（繰り返し使用される）であるテクスチャーはグループにして代表イメージにユニークなナンバーを付けて送信し、あとはそのナンバーを参照するようにすれば、データの重複送信をしなくて済む。
【００２９】
ところで、テクスチャーデータを蓄積するデータベース上で、代表イメージ（繰り返し使用されるテクスチャーの画像データ）にユニークなナンバーを付けることは容易なようで、実は大変な困難を伴う。
【００３０】
第１には、データベース全体を見渡して、同じテクスチャー（あるいは極めて類似なテクスチャー）のグルーピングを行うことができない。テクスチャー１つに注目しても、既存の代表イメージに等しいか、あるいは他に同じテクスチャーがあって、自らが代表イメージになるべきかを調べるには膨大な処理を伴う。ポリゴンやテクスチャーによる３次元表示データも逐次更新されるので、その都度この処理を行うことは不可能である。
【００３１】
またテクスチャーのテーブルを別に作ったとしても、必ずしも使うとは限らないテクスチャーを含めて端末装置にダウンロードすることになり効率的でない。さらに、３次元データを更新する際に、削除したいテクスチャーが他に使われているかどうかも調べないとテーブルから削除できず、テクスチャーデータのメンテナンスにかかる負荷が非常に大きくなる。これらの処理を所定の大きさに区切られた地図メッシュ（単位地図）の範囲に区切って行うようにしても解決されない問題である。
【００３２】
第２には、先願１のように必要な面のポリゴンのみを端末装置に送信する方法を取った場合、端末装置から見えない面（陰面という）のデータは端末装置に送信しいなので、３次元データベース上、陰面になるポリゴンに対応したテクスチャーの中にグルーピングしたテクスチャーにおける代表イメージとなるデータがあると、その代表テクスチャーは端末装置に送信されず、送信されるポリゴンに対応したテクスチャーはグルーピングしたテクスチャーグループに割り当てたナンバーのみが送信される。このため、代表となるテクスチャーの実体（画像データ）が端末装置に送信されていないので表示できなくなるという問題点が生じる。
【００３３】
どの面のポリゴンが陰面になるかは、端末装置の位置や進行方向によって異なるので特定することができず、予め面を選んで代表テクスチャーを配置することもできない。
【００３４】
本願の発明者は上記の問題点を解消すべく種々検討を重ねた結果、現在ではデータベースを構成する記憶装置は、それ程高価でなく十分な記憶容量を準備できることから、全ての繰り返し使用される同じ画像データのテクスチャーも含め、全てのテクスチャーデータをデータベースに蓄積しておき、経路探索サーバが地図表示装置の現在位置や移動方向に基づいて、現在位置から見える面を判別してそのポリゴンデータを地図表示装置に送信する際に、当該ポリゴンの面に配置する各テクスチャーデータを、識別符号を付してグルーピングし、繰り返しパターンとなるテクスチャーデータは識別符号で表現して地図表示装置に送信するようになせば上記の問題点を解消し得ることに想到して本発明を完成するに至ったものである。
【００３５】
すなわち、本発明は上記の問題点を解消することを課題とし、端末装置に送信する３次元表示のためのポリゴン、テクスチャーのデータ量を抑制することができるナビゲーションシステム、経路探索サーバ、端末装置および地図表示方法を提供することを目的とするものである。
【課題を解決するための手段】
【００３６】
前記課題を解決するために、本願の請求項１にかかる発明は、
３次元の地図を表示する表示手段を有する端末装置と、３次元表示のために各オブジェクトを、当該オブジェクトを構成する面ごとのポリゴンデータとして蓄積し、各ポリゴンに貼り付ける複数のテクスチャーの画像データをポリゴンごとに蓄積した３次元表示用データベースと、視点位置から見える各オブジェクトの面を選択するポリゴン選択手段と、選択されたポリゴンに対応するテクスチャーをグルーピングするテクスチャー処理手段と、を備えた経路探索サーバとを備えたナビゲーションシステムであって、
前記テクスチャー処理手段は、前記ポリゴン選択手段が選択したポリゴンに対応するテクスチャーから共通する画像データであるテクスチャーをテクスチャーグループとして抽出し、前記抽出したテクスチャーグループにユニークな識別符号を決定し、そのうちの１つのテクスチャーの画像データを配信データとし、他の共通のテクスチャーは前記識別符号を配信データとし、共通する画像データがないテクスチャーは画像データのまま配信データとし、前記ポリゴン選択手段が選択したポリゴンとともに、前記端末装置に配信することを特徴とする。
【００３７】
本願の請求項２にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、
前記ナビゲーションシステムは、更に、視点位置を設定する視点位置設定手段を備え、
前記視点位置設定手段が設定した視点位置に基づいて、前記ポリゴン選択手段は、当該視点位置から所定の範囲内のポリゴンデータを対象に当該視点位置から見える各オブジェクトの面を選択し、前記表示手段は前記ポリゴン選択手段が選択した面のポリゴンと前記テクスチャー処理手段が配信データとしたテクスチャーに基づいて、前記選択されたポリゴンに対応するテクスチャーを貼り付けて地図を３次元表示することを特徴とする請求項１に記載のナビゲーションシステム。
【００３８】
本願の請求項３にかかる発明は、請求項１にかかるナビゲーションシステムにおいて、
前記面ごとのポリゴンデータは、それぞれその表面方向を示す法線ベクトルを含み、前記ポリゴン選択手段は、前記視点位置から前記オブジェクトの各面を見込むベクトルを生成し、当該ベクトルと前記法線ベクトルとがなす角度を算出し、算出した角度が９０°以下の面を選択することを特徴とする。
【００３９】
本願の請求項４にかかる発明は、請求項２にかかるナビゲーションシステムにおいて、
前記ナビゲーションシステムは、更に、経路探索のための探索用ネットワークデータと、経路探索手段と、を備え、前記視点位置設定手段は、前記経路探索手段が探索した案内経路の所定の位置を視点位置とし、前記ポリゴン選択手段は、該視点位置から所定の範囲内のポリゴンデータを対象に当該視点位置から見える各オブジェクトの面を選択することを特徴とする。
【００４０】
また、本願の請求項５にかかる発明は、
経路探索サーバから配信されるポリゴンデータとテクスチャーデータに基づいて３次元の地図を表示する表示手段を有する端末装置とネットワークを介して接続される経路探索サーバであって、
前記経路探索サーバは、３次元表示のために各オブジェクトを、当該オブジェクトを構成する面ごとのポリゴンデータとして蓄積し、各ポリゴンに貼り付ける複数のテクスチャーの画像データをポリゴンごとに蓄積した３次元表示用データベースと、視点位置から見える各オブジェクトの面を選択するポリゴン選択手段と、選択されたポリゴンに対応するテクスチャーをグルーピングするテクスチャー処理手段と、を備え、
前記テクスチャー処理手段は、前記ポリゴン選択手段が選択したポリゴンに対応するテクスチャーから共通する画像データであるテクスチャーをテクスチャーグループとして抽出し、前記抽出したテクスチャーグループにユニークな識別符号を決定し、そのうちの１つのテクスチャーの画像データを配信データとし、他の共通のテクスチャーは前記識別符号を配信データとし、共通する画像データがないテクスチャーは画像データのまま配信データとし、前記ポリゴン選択手段が選択したポリゴンとともに、前記端末装置に配信することを特徴とする。
【００４１】
本願の請求項６にかかる発明は、請求項５にかかる経路探索サーバにおいて、
前記経路探索サーバは、更に、視点位置を設定する視点位置設定手段を備え、
前記視点位置設定手段が設定した視点位置に基づいて、前記ポリゴン選択手段は、当該視点位置から所定の範囲内のポリゴンデータを対象に当該視点位置から見える各オブジェクトの面を選択し、前記表示手段は前記ポリゴン選択手段が選択した面のポリゴンと前記テクスチャー処理手段が配信データとしたテクスチャーに基づいて、前記選択されたポリゴンに対応するテクスチャーを貼り付けて地図を３次元表示することを特徴とする請求項５に記載の経路探索サーバ。
【００４２】
本願の請求項７にかかる発明は、請求項５にかかる経路探索サーバにおいて、
前記面ごとのポリゴンデータは、それぞれその表面方向を示す法線ベクトルを含み、前記ポリゴン選択手段は、前記視点位置から前記オブジェクトの各面を見込むベクトルを生成し、当該ベクトルと前記法線ベクトルとがなす角度を算出し、算出した角度が９０°以下の面を選択することを特徴とする。
【００４３】
本願の請求項８にかかる発明は、請求項６にかかる経路探索サーバにおいて、
前記経路探索サーバは、更に、経路探索のための探索用ネットワークデータと、経路探索手段と、を備え、前記視点位置設定手段は、前記経路探索手段が探索した案内経路の所定の位置を視点位置とし、前記ポリゴン選択手段は、該視点位置から所定の範囲内のポリゴンデータを対象に当該視点位置から見える各オブジェクトの面を選択することを特徴とする。
【００４４】
また、本願の請求項９にかかる発明は、
３次元表示のために各オブジェクトを、当該オブジェクトを構成する面ごとのポリゴンデータとして蓄積し、各ポリゴンに貼り付ける複数のテクスチャーの画像データをポリゴンごとに蓄積した３次元表示用データベースと、視点位置から見える各オブジェクトの面を選択するポリゴン選択手段と、選択されたポリゴンに対応するテクスチャーをグルーピングするテクスチャー処理手段と、を備え、前記テクスチャー処理手段は、前記ポリゴン選択手段が選択したポリゴンに対応するテクスチャーから共通する画像データであるテクスチャーをテクスチャーグループとして抽出し、前記抽出したテクスチャーグループにユニークな識別符号を決定し、そのうちの１つのテクスチャーの画像データを配信データとし、他の共通のテクスチャーは前記識別符号を配信データとし、共通する画像データがないテクスチャーは画像データのまま配信データとし、前記ポリゴン選択手段が選択したポリゴンとともに配信する経路探索サーバにネットワークを介して接続される端末装置であって、
前記端末装置は前記経路探索サーバから受信したポリゴンデータとテクスチャーデータに基づいて地図を３次元表示する表示手段を備え、
前記表示手段は、前記ポリゴン選択手段が選択したポリゴンに対応する１つのテクスチャーの画像データと、その他の共通のテクスチャーは前記識別符号を参照することで、前記選択されたポリゴンに対応するテクスチャーを貼り付けて地図を３次元表示することを特徴とする。
【００４５】
本願の請求項１０にかかる発明は、請求項９にかかる端末装置において、
前記端末装置は、更に、視点位置を検出する視点位置検出手段を備え、前記視点位置検出手段が検出した視点位置情報を前記経路探索サーバに送信することを特徴とする。
【００４６】
また、本願の請求項１１にかかる発明は、
３次元の地図を表示する表示手段と、３次元表示のために各オブジェクトを、当該オブジェクトを構成する面ごとのポリゴンデータとして蓄積し、各ポリゴンに貼り付ける複数のテクスチャーの画像データをポリゴンごとに蓄積した３次元表示用データベースと、視点位置から見える各オブジェクトの面を選択するポリゴン選択手段と、選択されたポリゴンに対応するテクスチャーをグルーピングするテクスチャー処理手段と、を備えたナビゲーションシステムにおける地図表示方法であって、
前記ポリゴン選択手段が視点位置から見える各オブジェクトの面を選択する第１のステップと、
前記テクスチャー処理手段が、前記ポリゴン選択手段が選択したポリゴンに対応するテクスチャーから共通する画像データであるテクスチャーをテクスチャーグループとして抽出し、前記抽出したテクスチャーグループにユニークな識別符号を決定し、そのうちの１つのテクスチャーの画像データを配信データとし、他の共通のテクスチャーは前記識別符号を配信データとし、共通する画像データがないテクスチャーは画像データのまま配信データとする第２のステップと、
前記ポリゴン選択手段が選択したポリゴンとともに、前記テクスチャー処理手段が配信データとしたテクスチャーデータを端末装置に配信するステップと、を有することを特徴とする。
【００４７】
本願の請求項１２にかかる発明は、請求項１１にかかる地図表示方法において、
前記ナビゲーションシステムは、更に、視点位置を設定する視点位置設定手段を備え、
前記第１のステップは、前記視点位置設定手段が設定した視点位置に基づいて、前記ポリゴン選択手段が、当該視点位置から所定の範囲内のポリゴンデータを対象に当該視点位置から見える各オブジェクトの面を選択する処理を含み、前記表示手段が、前記ポリゴン選択手段が選択した面のポリゴンと前記テクスチャー処理手段が配信データとしたテクスチャーに基づいて、前記選択されたポリゴンに対応するテクスチャーを貼り付けて地図を３次元表示するステップを有することを特徴とする。
【００４８】
本願の請求項１３にかかる発明は、請求項１１にかかる地図表示方法において、
前記面ごとのポリゴンデータは、それぞれその表面方向を示す法線ベクトルを含み、前記第１のステップは、前記ポリゴン選択手段が前記視点位置から前記オブジェクトの各面を見込むベクトルを生成し、当該ベクトルと前記法線ベクトルとがなす角度を算出し、算出した角度が９０°以下の面を選択する処理を含むことを特徴とする。
【００４９】
本願の請求項１４にかかる発明は、請求項１２にかかる地図表示方法において、
前記ナビゲーションシステムは、更に、経路探索のための探索用ネットワークデータと、経路探索手段と、を備え、前記視点位置設定手段が、前記経路探索手段が探索した案内経路の所定の位置を視点位置とするステップを有し、前記第１のステップは、前記ポリゴン選択手段が該視点位置から所定の範囲内のポリゴンデータを対象に当該視点位置から見える各オブジェクトの面を選択する処理を含むことを特徴とする。
【発明の効果】
【００５０】
請求項１にかかる発明においては、各オブジェクトを、当該オブジェクトを構成する面ごとのポリゴンデータとして蓄積し、各ポリゴンに貼り付ける複数のテクスチャーの画像データをポリゴンごとに蓄積した３次元表示用データベースを備え、ポリゴン選択手段が視点位置から見える各オブジェクトの面を選択し、テクスチャー処理手段が、ポリゴン選択手段が選択したポリゴンに対応するテクスチャーから共通する画像データであるテクスチャーをテクスチャーグループとして抽出し、前記抽出したテクスチャーグループにユニークな識別符号を決定し、そのうちの１つのテクスチャーの画像データを配信データとし、他の共通のテクスチャーは前記識別符号を配信データとし、共通する画像データがないテクスチャーは画像データのまま配信データとし、前記ポリゴン選択手段が選択したポリゴンとともに端末装置に配信する。
【００５１】
このような構成によれば、経路探索サーバから端末装置に送信される３次元表示用のデータは、端末装置から見える面のポリゴン、当該ポリゴンに貼り付けられるテクスチャーのみであり、テクスチャーのデータは、同一のテクスチャーデータについてはグルーピングされ、グルーピングされたテクスチャーにおいては、代表テクスチャーのデータのみが画像データで送信されるから、送信データ量を大幅に軽減することができるようになる。
【００５２】
請求項２にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、ナビゲーションシステムは、更に、視点位置を設定する視点位置設定手段を備え、視点位置設定手段が設定した視点位置に基づいて、ポリゴン選択手段は、当該視点位置から所定の範囲内のポリゴンデータを対象に当該視点位置から見える各オブジェクトの面を選択し、前記表示手段は前記ポリゴン選択手段が選択した面のポリゴンと前記テクスチャー処理手段が配信データとしたテクスチャーに基づいて、前記選択されたポリゴンに対応するテクスチャーを貼り付けて地図を３次元表示する。
【００５３】
このような構成によれば、ナビゲーションシステムは視点位置（例えば、端末装置の位置）から見える面のポリゴンのみを選択することができるようになり、端末装置は、端末装置から見える面のポリゴン、当該ポリゴンに貼り付けられるテクスチャーのみによって地図を３次元表示することができるようになる。
【００５４】
請求項３にかかる発明においては、請求項１にかかるナビゲーションシステムにおいて、面ごとのポリゴンデータは、それぞれその表面方向を示す法線ベクトルを含み、前記ポリゴン選択手段は、前記視点位置から前記オブジェクトの各面を見込むベクトルを生成し、当該ベクトルと前記法線ベクトルとがなす角度を算出し、算出した角度が９０°以下の面を選択する。
【００５５】
このような構成によれば、ナビゲーションシステムは端末装置から見える面のポリゴンのみを選択することができるようになる。
【００５６】
請求項４にかかる発明においては、請求項２にかかるナビゲーションシステムにおいて、ナビゲーションシステムは、更に、経路探索のための探索用ネットワークデータと、経路探索手段と、を備え、前記視点位置設定手段は、前記経路探索手段が探索した案内経路の所定の位置を視点位置とし、前記ポリゴン選択手段は、該視点位置から所定の範囲内のポリゴンデータを対象に当該視点位置から見える各オブジェクトの面を選択する。
【００５７】
このような構成によれば、ナビゲーションシステムは端末装置の要求に基づいて経路探索して端末装置に送信した案内経路上の視点位置に基づいて端末装置から見える面のポリゴンを選択することができるようになる。
【００５８】
請求項５ないし請求項８にかかる発明においては、それぞれ請求項１ないし請求項４にかかるナビゲーションシステムを構成する経路探索サーバを提供することができるようになり、請求項９、請求項１０にかかる発明においては、それぞれ請求項１、請求項２にかかるナビゲーションシステムを構成する端末装置を提供することができるようになる。また、請求項１１ないし請求項１４にかかる発明においては、それぞれ請求項１ないし請求項４にかかるナビゲーションシステムを実現する地図表示方法を提供することができるようになる。
【発明を実施するための最良の形態】
【００５９】
以下、本発明の具体例を実施例及び図面を用いて詳細に説明する。但し、以下に示す実施例は、本発明の技術思想を具体化するためのナビゲーションシステムを例示するものであって、本発明をこのナビゲーションシステムに特定することを意図するものではなく、特許請求の範囲に含まれるその他の実施形態のナビゲーションシステムにも等しく適用し得るものである。
【００６０】
また、以下の実施例においては、経路探索機能を有するナビゲーションシステムを例として本発明を詳細に説明するが、経路探索機能は必須の機能ではなく、本発明において、ナビゲーションシステムは少なくとも端末装置の位置に基づいて地図情報を配信する地図表示システムとしての機能を有していればよい。従って、本発明において、ナビゲーションシステムは地図表示システムを含む広義のナビゲーションシステムを指し、経路探索サーバは地図提供サーバを含む広義のサーバを指す。
【実施例１】
【００６１】
図１は、本発明の実施例にかかるナビゲーションシステムの構成を示すブロック図である。ナビゲーションシステム１０は、図１に示すようにインターネットなどのネットワーク１２を介して接続される端末装置２０と経路探索サーバ３０を備えて構成されている。経路探索サーバ３０は、経路探索手段３１６、探索用ネットワークデータ３１７、地図データを蓄積した地図データベース３１５、道路や建物の３次元ポリゴンおよびテクスチャーなどのデータを蓄積した３次元表示用データベース３１８、テクスチャー処理手段３２１を備えている。
【００６２】
３次元表示用データベース３１８に蓄積される建物のデータは建物の各面を構成するポリゴンと、各面のポリゴンに貼り付けられるテクスチャーとが対応付けられて蓄積されており、テクスチャーは、繰り返し使用される画像を含め全てのテクスチャーが画像データとして蓄積されている。テクスチャー処理手段３２１は、端末装置２０に送信するポリゴンが特定されると、同一の画像データからなるテクスチャーをグループ分けして識別番号を付し、グループの代表テクスチャーを決定し、グループ分けされた他のテクスチャーは識別符号に置き換えて表現し、画像データそのものは代表テクスチャーのみ端末装置に送信するようにされる。この処理の詳細は後で詳述する。
【００６３】
経路探索サーバ３０は、端末装置２０から現在位置、目的地、移動手段（自動車、徒歩、交通機関あるいは徒歩と交通機関併用など）などの経路探索条件を含む経路探索要求があると、探索用ネットワークデータ３１７を参照して経路探索条件に合致した最短の案内経路あるいは経路長順に複数の案内経路を探索する。探索の結果得られた案内経路のデータは、地図データベース３１５から選択した現在位置を含む複数の単位地図データ（緯度・経度で所定の大きさのエリアに区分された地図データ）や３次元表示用データベース３１８から選択した前記単位地図データ上の道路や建物の３次元表示用のポリゴン、テクスチャーのデータとともに端末装置２０に配信される。
【００６４】
探索用ネットワークデータ３１７は、道路ネットワークデータ３１７Ａ、交通ネットワークデータ３１７Ｂを備えており、徒歩や自動車あるいは交通機関を利用した経路を探索することができる。道路ネットワークデータ３１７Ａ、交通ネットワークデータ３１７Ｂは、ノードの高度情報を持たない通常の平面地図に基づくネットワークデータである。従って、経路探索手段３１６によって探索された案内経路のデータは平面的な経路のデータであって、高度情報を持たない。
【００６５】
端末装置２０は、経路探索サーバ３０から目的地までの案内経路を受信すると、表示手段２２１に現在位置付近の地図を表示する。表示手段に表示される地図画像には、案内経路と現在位置を示す現在位置マークとが重ね合わせて表示される。一般的には現在位置マークを表示画面の中央にして、所定の大きさの単位地図が表示される。３次元の立体的な地図表示を行う場合は、経路探索サーバ３０から現在位置周辺の道路、建物の３次元表示用のポリゴン、テクスチャーのデータを受信して表示する。
【００６６】
建物のポリゴンのデータは、後述するように建物などのオブジェクトを構成する各面のデータからなる。本発明においては、端末装置２０は視点位置検出手段２１４により端末装置２０における視点位置、視線の方向などを含む視点位置情報を経路探索サーバ３０に送信する。経路探索サーバ３０は端末装置２０から受信した視点位置情報に基づいて、後述する方法により、端末装置２０から見える面に該当するポリゴンデータのみを選択して端末装置に配信する。
【００６７】
端末装置２０は経路探索サーバから受信したポリゴンデータに基づいて、３次元の地図、建物の画像を表示手段２２１に表示する。この結果、経路探索サーバ３０と端末装置２０との間で送受信されるポリゴンデータは、端末装置２０の視点位置に従って、当該視点位置から見ることのできる面のポリゴンデータのみとなるので、必要最小限度のデータ量で済ませることができるようになる。また、各面に貼り付けられるテクスチャーのデータも繰り返しになる画像はグルーピング処理され、代表テクスチャーのみ画像データで、グルーピングされたテクスチャーはグループの識別番号で端末装置に送信されるので、必要最小限のデータ量に抑制することができる。
【００６８】
経路探索サーバ３０はまた、制御手段３１１、通信手段３１２、配信データ編集手段３１３、案内経路データ作成手段３１４、ポリゴン選択手段３１９、視点位置設定手段３２０を備えている。制御手段３１１は、図示してはいないがＲＡＭ、ＲＯＭ、プロセッサを有するマイクロプロセッサであり、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。通信手段３１２は、ネットワーク１２を介して端末装置２０と通信するためのインターフェースである。案内経路データ作成手段３１４は前述のようにして探索された案内経路のデータや地図データ、ガイダンスポイント、ガイダンスポイントにおけるガイダンスのデータなどを作成し、配信データ編集手段３１３が案内経路などのデータを端末装置２０に配信するためのデータに編集する。
【００６９】
道路ネットワークデータ３１７Ａは以下のように構成されている。例えば、道路が図２に示すように道路Ａ、Ｂ、Ｃからなる場合、道路Ａ、Ｂ、Ｃの端点、交差点、屈曲点などをノードとし、各ノード間を結ぶ道路を有向性のリンクで表し、ノードデータ（ノードの緯度・経度）、リンクデータ（リンク番号）と各リンクのリンクコスト（リンクの距離またはリンクを走行するのに必要な所要時間）をデータとしたリンクコストデータとで構成される。
【００７０】
すなわち、図２において、Ｎｎ（○印）、Ｎｍ（◎印）がノードを示し、Ｎｍ（◎印）は道路の交差点を示している。各ノード間を結ぶ有向性のリンクを矢印線（実線、点線、２点鎖線）で示している。リンクは、道路の上り、下りそれぞれの方向を向いたリンクが存在するが、図２では図示を簡略化するため矢印の向きのリンクのみを図示している。
【００７１】
このような道路ネットワークのデータを経路探索用のデータベースとして経路探索を行う場合、出発地のノードから目的地のノードまで連結されたリンクをたどりそのリンクコストを累積し、累積リンクコストの最少になる経路を探索して案内する。すなわち、図２において出発地をノードＡＸ、目的地をノードＣＹとして経路探索を行う場合、ノードＡＸから道路Ａを走行して２つ目の交差点で右折して道路Ｃに入りノードＣＹにいたるリンクを順次たどりリンクコストを累積し、リンクコストの累積値が最少になる経路を探索して案内する。
【００７２】
図２ではノードＡＸからノードＣＹに至る他の経路は図示されていないが、実際にはそのような経路が他にも存在するため、ノードＡＸからノードＣＹに至ることが可能な複数の経路を同様にして探索し、それらの経路のうちリンクコストが最少になる経路を最適経路として決定するものである。この手法は、例えば、ダイクストラ法と呼ばれる周知の手法によって行われる。
【００７３】
交通ネットワークデータ３１７Ｂのデータも基本的には道路ネットワークデータと同様であるが、路線を運行する電車のそれぞれが各駅間のリンク（各駅がノード、駅間を結ぶリンク）を構成するものとしてネットワークデータが作成されている。従って案内経路はリンクである電車を特定したものとなる。このような交通ネットワークデータを用いて、ある出発地からある目的地までの経路を探索するためには、出発地から目的地まで到達する際に使用（乗車）できる全ての交通手段を探索して探索条件に合致する交通手段を特定して案内経路が特定される。
【００７４】
一方、端末装置２０は、例えばＧＰＳ受信機などからなるＧＰＳ測位手段２１２を搭載した携帯電話機であり、制御手段２１１、ＧＰＳ測位手段２１２、表示モード制御手段２１３、視点位置検出手段２１４、２次元表示制御手段２１５、３次元表示制御手段２１６、通信手段２１７、配信要求編集手段２１８、配信データ記憶手段２１９、ＶＲＡＭ２２０、表示手段２２１、操作・入力手段２２２などを備えて構成されている。利用者は、徒歩あるいは交通機関を移動手段として選択し、徒歩や交通機関を利用した経路案内を受けることができ、また、自動車の助手席に同乗した時には移動手段として自動車を選択して経路案内を受けることができる。
【００７５】
制御手段２１１は、図示してはいないがＲＡＭ、ＲＯＭを有するマイクロプロセッサ（ＣＰＵ）を備えて構成され、ＲＯＭに格納された制御プログラムにより各部の動作を制御する。操作・入力手段２２２は、数字キーやアルファベットキー、その他の機能キー、選択キー、スクロールキーなどからなる操作・入力手段ためのものであり、出力手段である表示手段２２１に表示されるメニュー画面から所望のメニューを選択し、あるいは、キーを操作して種々の入力操作を行うものである。従って、表示手段２２１は操作・入力手段２２２の一部としても機能する。通信手段２１７は、ネットワーク１２を介して経路探索サーバ３０と通信するためのインターフェースである。
【００７６】
利用者が経路探索サーバ３０に経路探索を依頼しようとする場合、端末装置２０において操作・入力手段２２２を操作し、表示手段２２１に表示されるサービスメニューから経路探索を選択し、現在位置、目的地、移動手段（自動車、徒歩、交通機関あるいは徒歩と交通機関併用など）などの経路探索条件を入力する。経路探索条件は配信要求編集手段２１８で経路探索サーバ３０への配信要求に編集され、通信手段２１７を介して経路探索サーバ３０に送信される。
【００７７】
経路探索サーバ３０からの配信データは配信データ記憶手段２１９に一時記憶され、必要に応じて配信データ記憶手段２１９から読み出され、表示手段２２１に表示される。端末装置２０は、配信データに含まれる地図、案内経路、建物画像などを２次元表示あるいは鳥瞰図表示する第１の表示モード（以下、２次元表示モードという）と、３次元表示する３次元表示する第２の表示モード（以下、３次元表示モードという）と、を有しており、表示モード制御手段２１３が２次元表示制御手段２１５、３次元表示制御手段２１６の何れかを選択的に動作させ表示手段２２１への表示を行う。利用者は操作・入力手段２２２を用いて所望の表示モードを指定する。
【００７８】
２次元表示制御手段２１５は経路探索サーバ３０から配信される地図、道路、案内経路、建物などの平面データを用いてそれらを２次元の画像（平面画像）として表示する制御を行う。鳥瞰図表示をする場合、２次元表示制御手段２１５は、２次元の地図や道路を所定の高度の視点位置から見た鳥瞰図の画像を作成して表示する制御を行う。３次元表示制御手段２１６は経路探索サーバ３０から配信される地図、道路、建物などの３次元ポリゴンのデータを用いて３次元画像に処理して表示する制御を行う。２次元表示制御手段２１５、３次元表示制御手段２１６により作成された画像データは、描画手段であるＶＲＡＭ２２０にドット単位で展開され、表示手段２２１に所望の表示モードの画像が表示される。
【００７９】
ＧＰＳ測位手段２１２は端末装置２０の現在位置を周期的に測位し、現在位置（緯度・経度）を取得する。ＧＰＳ測位手段２１２で測位したこの現在位置を示す現在位置マークが表示手段２２１に表示される地図や案内経路などの画像に重ね合わせられて表示される。
【００８０】
次に、本発明における３次元表示のためのテクスチャーデータのグルーピング方法について説明するが、それに先立って、端末装置２０に送信するポリゴンの選択処理を説明する。この選択処理は先願１の発明と同様である。すなわち、経路探索サーバ３０において、ポリゴン選択手段３１９は、端末装置２０から受信した視点位置情報または視点位置設定手段３２０が設定した所定の視点位置の情報に基づいて３次元表示用データベース３１８に蓄積された３次元ポリゴンデータから、端末装置２０から見える面に該当するポリゴンデータのみを選択する。
【００８１】
例えば、図３に示すように端末装置２０がノードＰｎ−１〜ノードＰｎ〜ノードＰｎ＋１の案内経路にそって進んでおり、端末装置２０がこの経路上を進んでいる時の視野範囲が円で示されているものとする。視野範囲Ｖｎの建物Ａ、Ｂ、Ｃが見える位置に端末装置２０が到達した時、端末装置２０から見える建物を面単位（面のポリゴン）で考慮すると、建物Ａの面Ｈ０、建物Ｂの面Ｈ１、建物Ｃの面Ｈ２は端末装置２０から見える面であり、建物Ａの面Ｈ３は該建物Ａの前側の面Ｈ０に隠れて端末装置２０から見えない面である（この面を陰面という）。
【００８２】
図４は、この様子を立体的に示した模式図である。端末装置２０がノードＰｎ−１からＰｎに向かって進んでいる時、端末装置２０から建物Ａの面Ｈ０、建物Ｂの面Ｈ１、建物Ｃの面Ｈ２を見ることになるが、建物Ａの面Ｈ３は手前の面に隠れて見ることができない。なお、図４において参照符号ｈは、端末装置２０の利用者の視点位置の高さを示している。例えば、端末装置２０が携帯電話である場合、携帯電話を使用する利用者の目の高さである。この視点位置と、端末装置２０の進行方向と、建物の各面のポリゴンの法線ベクトルから、端末装置２０から見えるポリゴンを算出する。この算出方法は、図８を参照して説明した先願１と同様の方法である。
【００８３】
すなわち、建物のポリゴンは図８を参照して説明したように、建物を、それを構成する面に分解して、それぞれの形状データ、各頂点の位置データ（位置座標）と、各面が持つ向きを示す法線ベクトルとで表すことができ、建物の各面がどちらの方位を向いているかを法線ベクトルによって知ることができる。従って、端末装置２０の位置と視線方向がわかれば、端末装置２０から見える面を特定することができる。
【００８４】
このように、端末装置２０が３次元表示を行う場合、端末装置２０から視点情報を経路探索サーバ３０に送信し、経路探索サーバ３０が当該視点情報に基づいて表示に必要な面のポリゴンデータを選択して端末装置２０に配信する。端末装置２０においては、受信した面のポリゴンデータを基に、周知のＺバッファ法などを用いて、実際に視点から見える画像を描画していく。
【００８５】
このため、端末装置２０は視点位置検出手段２１４によって視点位置、視線方向を検出して視点情報として経路探索サーバ３０に送信する。視点位置は一般にはＧＰＳ測位手段２１２が測位した現在位置（緯度・経度）であり、視線方向は端末装置２０の進行方向であるが、ナビゲーションシステムによる経路案内においては、案内経路上の移動方向である。
【００８６】
一方、経路探索サーバ３０はポリゴン選択手段３１９を備えており、経路探索サーバ３０は端末装置２０から視点情報を受信すると、視点位置周辺の所定範囲の３次元ポリゴンデータを３次元表示用データベース３１８から読み出し、ポリゴン選択手段３１９は、図８において説明したように、視点位置からオブジェクトである建物の各面を見込むベクトルを作成し、各面が持つ法線ベクトルとのなす角度を計算し、両ベクトルのなす角度が直角以下の面を選択し、その面のポリゴンデータを端末装置２０に配信する。
【００８７】
なお、ポリゴンデータが法線ベクトルを有していなくても、先に述べたように面の頂点の座標データが左周りに記録されているたりものとすれば、各頂点の座標から面が向いている方向を知ることができ、視点位置、視線方向との関係から、視点位置から見える面を選択することができる。
【００８８】
端末装置２０に送信されるポリゴンに対応するテクスチャーは、例えば、図５に示すように各面のポリゴンに対応するそれぞれのテクスチャーデータが用意され、３次元表示用データベース３１８に蓄積されている。すなわち、図５は、図４に対応する建物Ａ〜Ｃのポリゴンとそのテクスチャーの一例を示すものである。図５では、代表的に建物Ａの面Ｈ０に対応するテクスチャーＴＨ０、建物Ｃの面Ｈ２に対応するテクスチャーＴＨ２のみを図示している。
【００８９】
このように３次元表示用データベース３１８に蓄積されるテクスチャーのデータは、テクスチャーの共通化など行わず、すべて独立した画像データで構成する。これによって、３次元表示用のデータの更新の自由度が確保され、修正したい部分を自由に修正することができる。もし、テクスチャーを共通化したデータを使いたい場合は、個別のテクスチャーデータ（画像データ）すべて展開しておく。これにより３次元表示用データベースのデータサイズが大きくなるが、これは経路探索サーバ３０のデータベースに記憶されるデータなのでその記憶容量を十分に用意しておけば全く問題ない。
【００９０】
テクスチャーＴＨ０は、テクスチャーデータＡ１〜Ａ４〜ＡＰ〜Ａｎのように個々のテクスチャーデータが画像データとして３次元表示用データベース３１８に面のポリゴンデータと対応づけられて蓄積されている。端末装置２０に面Ｈ０ポリゴンが送信される場合、テクスチャー処理手段３２１は、テクスチャーＴＨ０に対して次のようなグルーピング処理を行い、繰り返しとなるテクスチャーデータがあれば、代表テクスチャーを決定して識別番号を付与し、そのグループに属するテクスチャーは該当する識別番号で表現したデータとする。
【００９１】
例えば、建物Ａの面Ｈ０のポリゴンデータが端末装置２０に送信される場合、テクスチャー処理手段３２１はテクスチャーＴＨ０のテクスチャーデータＡ１〜Ａ４〜ＡＰ〜Ａｎの先頭（図の斜め上方）から順に着目するテクスチャーデータを決め、他のテクスチャーデータと順次画像マッチングによる比較を行って同一の画像を持つテクスチャーデータがあるかを判定する。この比較は上段左から右に順次行う。画像比較におけるマッチング率に幅を持たせることによってほぼ類似の画像も同一画像として扱うことができる。
【００９２】
着目したテクスチャーデータと同一のテクスチャーがなければ、そのテクスチャーデータは画像データとして端末装置２０に配信される。同一のテクスチャーがあればそれらのテクスチャーデータはグルーピングされ、ユニークな識別番号を決定し、着目したテクスチャーデータ（画像データ）を代表データとし、その他同一のテクスチャーデータは識別番号に置き換えて端末装置２０に送信される。個々のテクスチャーデータ自体は、例えば２０ドット×２０ドット程度のイメージデータ（画像データ）であり、テクスチャーデータＡ１〜Ａｎを総当たりで画像マッチング処理してもテクスチャー処理手段３２１の処理負荷は問題になるほど大きくはない。
【００９３】
図５の場合には、建物Ａの面Ｈ０のテクスチャーＴＨ０において、テクスチャーデータＡＰのみ異なる画像（例えば、ビルの看板）で、その他のテクスチャーデータは全て同一の窓の画像である。従って、テクスチャーデータＡＰは画像データのまま、テクスチャーデータＡＰを除く他のテクスチャーデータＡ１〜Ａ４〜Ａｎはグルーピングされ、そのグループにユニークな識別番号、例えば「ＴＧ０１」が決定され、着目したテクスチャーデータＡ１が代表データ（画像データ）のまま、他のテクスチャーデータは画像データから識別番号「ＴＧ０１」に変換され、端末装置２０に送信される。
【００９４】
このようにテクスチャーをグルーピングすれば、図６に示すように、建物Ｂの面Ｈ１のポリゴンに貼るテクスチャー、例えば、左上のテクスチャーデータＴＧ０１にナンバー（ＴＧ０１）が与えられて、テクスチャーＴＧ０１の実体データ（画像データ）は１つだけ用意され、他はナンバー（ＴＧ０１）に置き換え（実体データは削除され）て、端末装置２０に送信される。端末装置２０では、実体データのＴＧ０１を用い、その他はこれを参照（コピー）するだけでポリゴンにテクスチャーデータを貼り付けて表示する。
【００９５】
これにより端末装置２０に配信されるテクスチャーのデータ量は、従来より大幅に抑制される。端末装置２０は受信した３次元表示データに従って、ポリゴン上にテクスチャーを貼り付けて表示を完成する。端末装置２０は、ソフトウエア処理で描画を行うこともできるが、最近は携帯電話にも３Ｄ描画用のグラフィックエンジン（グラフィックチップ）が搭載されるようになり、ストレス無く表示できるようになっている。
【００９６】
もしも、従来のように予めテクスチャーをグルーピングして３次元表示用データベースに蓄積していた場合、面Ｈ３のポリゴンに代表画像データを有するテクスチャーグループを他の面Ｈ１、や面Ｈ２のポリゴンでこの代表画像データを参照するようなデータ構造になっていたら、面Ｈ３のポリゴン、テクスチャーは陰面であるため端末装置２０に送信されない。このため、面Ｈ１、面Ｈ２のテクスチャーデータグルーピングされた識別番号のみ端末装置２０に送信され、代表画像データが送信されないので表示できなくなってしまう。
【００９７】
このような不都合を解消するには、陰面も含め、ポリゴン、テクスチャーを端末装置２０に送信すればよいが、それでは、端末装置２０に送信するデータ量が増大してしまい、ネットワークの通信負荷を軽減、抑制することはできなくなる。また、予めデータベース上にテクスチャーをグルーピングして用意しておくことは前述したように極めて負荷の大きい処理が要求され、また、３次元表示用データの更新の度にこの処理が必要になり、メンテナンスが困難になるという問題があり、現実的でない。
【００９８】
図７は、以上説明した本発明の実施例にかかるナビゲーションシステム１０の経路探索サーバ３０の処理手順を示すフローチャートである。経路探索サーバ３０は端末装置２０から、視点位置、視点方向に関するデータを条件として３次元表示用の表示データの要求を受信したものとする。
【００９９】
先ず、経路探索サーバ３０は、ステップＳ１０１の処理においてポリゴン選択手段３１９が端末装置２０に配信するポリゴン、すなわち、端末装置２０から見える建物の面を特定し、そのポリゴンを選択する。ポリゴンは視点位置からオブジェクトである建物の各面を見込むベクトルを作成し、各面が持つ法線ベクトルとのなす角度を計算し、両ベクトルのなす角度が直角以下の面を特定することによって選択される（図８およびその説明を参照）。次いで、ステップＳ１０２の処理において、選択されたポリゴンデータを端末装置２０に配信するデータとする。
【０１００】
次に、ステップＳ１０３の処理において、テクスチャー処理手段３２１は選択されたポリゴンに対応するテクスチャーを選択する（例えば、図５のテクスチャーＴＨ０等）。そして、ステップＳ１０４の処理において、テクスチャーのグルーピングを行う。この処理は次のように行う。例えば、図５のテクスチャーＴＨ０のテクスチャーデータＡ１〜Ａ４〜ＡＰ〜Ａｎを、先頭（図の斜め上方）から順に着目するテクスチャーデータを決め、他のテクスチャーデータと順次画像マッチングによる比較を行って同一の画像を持つテクスチャーデータがあるかを判定する。
【０１０１】
着目したテクスチャーデータと同一のテクスチャーがなければ、そのテクスチャーデータは画像データとして端末装置２０に配信するデータとする。同一のテクスチャーがあればそれらのテクスチャーデータはグルーピングされ、ユニークな識別番号を決定し、着目したテクスチャーデータ（画像データ）を代表データとし、その他同一のテクスチャーデータは識別番号に置き換えて端末装置２０に送信するデータとする。
【０１０２】
次いでテクスチャー処理手段３２１はステップＳ１０５の処理において、全てのテクスチャーデータのグルーピング処理が終了したかを判定し、処理が終了していなければステップＳ１０４のグルーピング処理を繰り返す。グルーピング処理が終了したら、ステップＳ１０６の処理に進み、グルーピング処理したテクスチャーの配信データを準備する。
【０１０３】
次に、ステップＳ１０７の処理において、配信データ編集手段３１３は、ポリゴン選択手段３１９が選択したポリゴンの配信データおよびテクスチャー処理手段３２１がグルーピングしたテクスチャーの配信データを編集して端末装置２０に送信（配信）する。端末装置２０は、経路探索サーバ３０から送信されたポリゴンおよびテクスチャーのデータを受信し３次元表示を行う。
【０１０４】
この処理によって、経路探索サーバ３０から端末装置２０に送信される３次元表示用のデータは、端末装置２０から見える面のポリゴン、当該ポリゴンに貼り付けられるテクスチャーのみであり、テクスチャーのデータは、同一のテクスチャーデータについてはグルーピングされ、グルーピングされたテクスチャーにおいては、代表テクスチャーのデータのみが画像データで送信されるから、送信データ量を大幅に軽減することができるようになる。
【産業上の利用可能性】
【０１０５】
本発明において端末装置は移動体端末装置に限ることなく、インターネットなどのネットワークを介してサーバに接続されるパーソナルコンピュータなどの端末装置であっても適用することができる。この場合、端末装置から視点位置と視点方向をサーバに送信して３次元用表示データを要求できるようにすれば、サーバから３次元表示のためのデータを送信して地図や建物を表示する場合にも適用することができる。
【図面の簡単な説明】
【０１０６】
【図１】本発明の実施例にかかるナビゲーションシステムの構成を示すブロック図である。
【図２】経路探索のための道路ネットワークデータの概念を示す模式図である。
【図３】端末装置の視点と端末装置から見ることのできる建物の面の関係を説明するための説明図である。
【図４】図３に示す建物と視点位置の位置関係を立体的に示す模式図である。
【図５】建物の面のポリゴンに対応するテクスチャーのデータの構成、グルーピング処理の概念を示す模式図である。
【図６】グルーピングしたテクスチャーと建物の面との関係を説明するための模式図である。
【図７】本発明の実施例にかかるナビゲーションシステムにおける経路探索サーバの処理手順を示すフローチャートである。
【図８】先願１の３次元地図表示におけるポリゴンデータの送信方法の概念を説明するための模式図である。
【符号の説明】
【０１０７】
１０・・・・ナビゲーションシステム
１２・・・・ネットワーク
２０・・・・端末装置
２１１・・・制御手段
２１２・・・ＧＰＳ測位手段
２１３・・・表示モード制御手段
２１４・・・視点位置検出手段
２１５・・・２次元表示制御手段
２１６・・・３次元表示制御手段
２１７・・・通信手段
２１８・・・配信要求編集手段
２１９・・・配信データ記憶手段
２２０・・・ＶＲＡＭ
２２１・・・表示手段
２２２・・・操作・入力手段
３０・・・・経路探索サーバ
３１１・・・制御手段
３１２・・・通信手段
３１３・・・配信データ編集手段
３１４・・・案内経路データ作成手段
３１５・・・地図データベース
３１６・・・経路探索手段
３１７・・・探索用ネットワークデータ
３１７Ａ・・・道路ネットワークデータ
３１７Ｂ・・・交通ネットワークデータ
３１８・・・３次元表示用データベース
３１９・・・ポリゴン選択手段
３２０・・・視点位置設定手段
３２１・・・テクスチャー処理手段
【図１】
0004812011.tif 000002
【図２】
0004812011.tif 000003
【図３】
0004812011.tif 000004
【図４】
0004812011.tif 000005
【図５】
0004812011.tif 000006
【図６】
0004812011.tif 000007
【図７】
0004812011.tif 000008
【図８】
0004812011.tif 000009