ナビゲーション装置用データベース、地形の三次元表示を出力する方法、およびデータベースを生成する方法
【課題】ナビゲーション装置用のデータベース(10)を提供すること。
【解決手段】上記データベースは、三次元表面を定義するデジタル標高モデルデータを含む。データベース(10)は、タイリングの複数のタイルのために、複数の不整三角網、TINの頂点の三次元座標を含む第1の配列(23)、および複数の第2の配列(24、25)を記憶する。各第2の配列(24、25)はそれぞれTINの三角面を定義し、前記それぞれのTINの三角面を定義するために頂点の複数の頂点インデックスを含む。地形の三次元表示を出力する方法、およびデータベースを生成する方法も説明される。
【解決手段】上記データベースは、三次元表面を定義するデジタル標高モデルデータを含む。データベース(10)は、タイリングの複数のタイルのために、複数の不整三角網、TINの頂点の三次元座標を含む第1の配列(23)、および複数の第2の配列(24、25)を記憶する。各第2の配列(24、25)はそれぞれTINの三角面を定義し、前記それぞれのTINの三角面を定義するために頂点の複数の頂点インデックスを含む。地形の三次元表示を出力する方法、およびデータベースを生成する方法も説明される。
【発明の詳細な説明】
【技術分野】
【0001】
本発明の実施形態は、ナビゲーション装置での高さ情報の使用に関連する方法および装置に関する。本発明の実施形態は、特に、ナビゲーション装置用データベース、地形の三次元表示を出力する方法、およびナビゲーション装置用データベースを生成する方法に関する。本発明の実施形態は、特に、高さ情報がタイリングのタイルのためにそれぞれ定義されるTINの形で記憶される、かかる装置および方法に関する。
【背景技術】
【0002】
地形の高さ情報は、ナビゲーション装置でますます幅広く使用されている。かかる高さ情報が使用され得る1つの例示的な分野が、三次元地図の出力である。光出力装置は、電子マップを出力するために使用されてよい。電子マップは小型装置および/または携帯装置の画面に表示されるので、それらは多用途且つコンパクトであるという優位点を有する。三次元(3D)マップ、つまり斜視表示は、それらの高い認識品質のために、ユーザにとって特に貴重である場合がある。つまり、従来の二次元表示に比較して、通りの交差点等の環境領域の認識は、三次元マップが出力されるときに特に容易になり得る。
【0003】
数値標高モデル(DEM)データは、不整三角網(TIN)の形で記憶されてよい。TINから地形をレンダリングするときに、良い実行時性能が達成され得る。DEMデータはタイリングに従って編成されてよく、タイリングのタイルは、地形のDEMデータがレンダリング用に使用できる領域をカバーする。矩形または台形の形状を有するタイルは、複数の三角形のパッチに分けられてよい。このパッチの各パッチに、TINが定義されてよい。したがって、複数のTINがタイリングの各タイルのためにそれぞれ定義されてよい。
【0004】
タイルのためにTINを記憶するための1つの手法では、各TINのデータは、TINを再構築するために必要とされる全情報がTINにとって別個のデータ構造で含まれるように別々に記憶される。従来の手法では、TINを説明するデータは、それぞれのTINの頂点の三次元座標(つまり、座標の3タプル)が記憶される配列と、頂点の内のどの頂点がTINの多様な三角面の角をそれぞれ形成するのかを指定するために頂点インデックスを含む別の配列と、おそらく三角面の法線ベクトルを定義するさらに別の配列とを含んでよい。
【0005】
図11は、1つのタイルに複数のTINを定義するデータ41を示す。データ41は、そのタイルの一意の識別子を示す。配列42は、タイル上に定義される第1のTINの全ての頂点の座標を定義する。配列43は頂点インデックスを含み、第1のTINの三角面を定義する。別の配列(図11では不図示)は、第1のTINの法線ベクトルに関する情報を含んでよい。配列44は、タイル上に定義される第2のTINの全ての頂点の座標を定義する。配列45は座標頂点を含み、第2のTINの三角面を定義する。別の配列(図11では不図示)は、第2のTINの法線ベクトルに関する情報を含んでよい。
【0006】
図41に関して説明された従来の手法は、冗長な情報の記憶につながる場合がある。説明のために、第1のTINおよび第2のTINが共通の頂点を有する場合、これらの頂点の三次元座標は複数回記憶されることがある。つまり、座標3タプルが、配列42と配列44の両方に含まれることがある。かかる冗長性は、記憶空間の要件の観点からは望ましくない。
【発明の概要】
【発明が解決しようとする課題】
【0007】
したがって、上述された欠点を軽減するデータベースおよび方法に対するニーズがある。特に、冗長性の問題を軽減しつつ、タイリングの各タイルに複数のTINをそれぞれ定義できるようにするデータベースおよび方法に対するニーズがある。
【課題を解決するための手段】
【0008】
このニーズは、独立請求項に詳述されるデータベースおよび方法によって対処される。従属請求項が実施形態を定義する。
【0009】
一態様によると、ナビゲーション装置用データベースが提供される。このデータベースは、地形の三次元表面を定義するデジタル標高モデル(DEM)データを含む。データベースは、タイリングの複数のタイルの内のそれぞれのタイルのために、1つの第1の配列、および複数の第2の配列を記憶する。第1の配列は、それぞれのタイルのために、複数の不整三角網、TINの頂点の三次元座標を含む。各第2の配列はそれぞれTINを定義し、それぞれのTINの三角面を定義するために頂点座標が第1の配列に記憶される頂点の複数のインデックスを含む。
【0010】
データベースでは、タイルに定義される多様なTINの頂点の三次元座標は、すべて1つの第1の配列の中に集められ得る。それによって、所望されないデータ冗長性に関連する問題は軽減され得る。複数の第2の配列は、全く同一の第1の配列を参照してよい。
【0011】
データベースは、タイリングの複数のタイルの各タイルのために、頂点の座標を含むただ1つの第1の配列をそれぞれ記憶してよい。
【0012】
頂点の内の各頂点のために、その頂点がいくつかのTINの頂点であったとしても、三次元座標は第1の配列の中に一度だけ含まれる。
【0013】
複数の第2の配列の各第2の配列は、三角形の片であってよい。それによって、TINのコンパクトな説明が提供される。記憶空間の要件は削減され得る。
【0014】
少なくとも1つの頂点のインデックスは、異なる第2の配列に含まれてよい。それによって、対応するTINが共通する1つの頂点を有するときに、第1の配列の同じ諸エントリが異なる第2の諸配列によって活用される。
【0015】
データベースは、複数のタイルの各タイルに、少なくとも2つの第2の配列を記憶してよい。これによって、タイルを2つの三角形のパッチに分割できる。
【0016】
三角形のパッチのそれぞれのパッチにTINが定義されてよい。三角形のパッチは、矩形二等辺三角形であってよい。それによって、異なる詳細レベルからのデータの組み合わせが容易になる。
【0017】
データベースは、複数のタイルの各タイルに、少なくとも6つの第2の配列を記憶してよい。これによって、地形は所与のタイルサイズについて2つの異なる詳細レベルで記憶できるようになる。第2の配列の内の少なくとも1つの配列が、同じタイルの第2の配列の別の配列によって表されるTINと部分的にまたは完全に重複するTINに対応してよい。第2の配列の内の少なくとも1つは、同じタイルの第2の配列の別の配列によって表されるTINによってカバーされる領域内に完全に包含されるTINに対応してよい。複数のタイルの各タイルのために、6つの第2の配列の内の2つがそれぞれ、タイルを二等分することによって得られる三角形のパッチ上にTINを定義してよい。他の4つの第2の配列は、それぞれ、タイルを4つの等しい大きさの矩形二等辺三角形に区切ることによって得られる三角形のパッチ上にTINを定義してよい。より小さいサイズの三角形パッチ上に定義されたTINは、それぞれ部分的にまたは完全に、大きい方のサイズの三角形パッチ上に定義されたTINと重複してよい。
【0018】
第1の配列での頂点のエントリは、頂点座標の距離メトリックに従って順序付けられてよい。第1の配列でのエントリのシーケンスは、第1の配列にエントリを有する任意の所与の頂点にとって、第1の配列の連続エントリが、所与の頂点のためのエントリに先行するエントリの内のどのエントリにも含まれず、距離メトリックに従って所与の頂点から最小の距離を有する、1つの頂点の頂点座標を含むように選択されてよい。それによって、距離メトリックに従って決定される、連続エントリの頂点座標間の距離が小さいエントリの順序が確立され得る。距離メトリックはLpメトリックまたは任意の他の適切な距離メトリックであってよい。
【0019】
第1の配列でのエントリが距離メトリックに従って順序付けられるとき、デルタ符号化が、第1の配列に記憶される頂点座標に使用されてよい。基準の絶対フレームでの、またはタイル上の特徴点を基準にした頂点座標が、第1の配列の第1のエントリに記憶されてよい。それぞれの続くエントリについては、このエントリに割り当てられる頂点の頂点座標と、直前に先行するエントリに割り当てられる頂点の頂点座標との間の座標(つまり距離ベクトル)の差異が第1の配列に記憶されてよい。エントリが距離メトリックに従って順序付けられた状態で、ゼロであるエントリの最上位ビットは省略されてよい。それによって、記憶空間の要件はさらに削減され得る。
【0020】
タイリングのいくつかまたは全てのタイルのために、データベースは、それぞれのタイルの複数のTINの頂点の三次元座標を含む一つ以上のの第1の配列を記憶してよい。この場合、第1の配列の内の少なくとも1つが、それぞれのタイルの異なる第2の配列によって参照される。
【0021】
別の態様に従って、ナビゲーション装置が提供される。ナビゲーション装置は、任意の1つの態様または実施形態のデータベース、光出力装置、および処理装置を含む。処理装置はデータベースに、および光出力装置に結合される。処理装置は、光出力装置を制御し、データベースから取り出されたデータに基づいて三次元地形の表示を出力するように構成されてよい。
【0022】
処理装置は、タイルが斜視図を生成するために複数の不整三角網、TINをレンダリングするように構成されてよい。処理装置は、それぞれのタイルのためのデータベースに記憶される全く同一の第1の配列から複数のTINの頂点の三次元座標を決定するように構成されてよい。
【0023】
別の態様に従って、三次元地形の表示が、任意の1つの態様または実施形態のデータベースを使用して生成される、三次元地形の表示を出力する方法が提供される。
【0024】
方法では、複数の不整三角網、TINがタイリングのタイルのためにレンダリングされてよい。複数のTINの頂点の頂点座標は、それぞれのファイルのためのデータベースに記憶される全く同一の第1の配列から取り出されてよい。
【0025】
別の態様に従って、ナビゲーション装置用データベースを生成する方法が提供される。方法では、以下のステップが、タイリングのタイルごとにそれぞれ実行される。それぞれのタイルに定義される、複数の不整三角網、TINの頂点の頂点座標が決定される。多様なTINのために決定された頂点座標を含む第1の配列が生成される。第2の配列は、複数のTINのそれぞれのTINにそれぞれ生成され、したがって各第2の配列は、頂点座標が第1の配列に含まれる複数の頂点のインデックスをそれぞれ含む。第2の配列は、どの頂点がそれぞれのTINの多様な三角形の方面の角に位置するのかを定義するように生成される。
【0026】
この方法では、複数の異なるTINの頂点座標が1つの第1の配列に集められる。冗長性の問題は、それによって緩和され得る。
【0027】
第1の配列は、頂点が複数のTINの頂点であったとしても、任意の頂点の三次元座標が第1の配列内に一度だけ含まれるように生成されてよい。
【0028】
複数の第2の配列の各第2の配列は、三角形の片として生成されてよい。それによって、TINのコンパクトな説明が提供される。記憶空間要件が削減され得る。
【0029】
複数の第2の配列は、少なくとも1つの頂点のインデックスが異なる第2の配列に含まれるように生成されてよい。それによって、第1の配列の同じエントリは、対応するTINが共通のそれぞれの頂点を有するときに、異なる第2の配列によって参照される。
【0030】
複数のタイルの内の各タイルのために、少なくとも2つの第2の配列が生成されてよい。複数のタイルの各タイルのために、少なくとも6つの第2の配列が生成されてよい。それによって、矩形二等辺三角形として構成される三角形のパッチが定義されてよく、そのそれぞれにTINが定義されてよい。それによって、異なる詳細レベルからデータを結合することが容易になる。
【0031】
方法は、距離メトリックに従って第1の配列内の頂点のエントリの順序を決定することを含んでよい。この目的のために、頂点が開始頂点となるように選択され、その開始頂点のために第1の配列の第1の位置にエントリが生成される手順が実行されてよい。その後、続くステップが、頂点のためのエントリを第1の配列に追加するために繰り返し実行される。第1の配列の中で最後である頂点のために、第1の配列にまだ含まれていない残りの頂点の内の、第1の配列の中で最後である頂点から最小距離を有する1つが選択される。この頂点のエントリは、次に第1の配列の最後に追加される。プロセスは、エントリが全ての頂点のための第1の配列で生成されるまで続行してよい。
【0032】
デルタ符号化は、頂点の座標の3つのタプルのために使用されてよい。頂点のためのエントリが距離メトリックに従って第1の配列で生成される場合、距離ベクトルは最も近傍の頂点が決定されると決定され得る。絶対的な座標ではなく、連続頂点間の距離ベクトルが、第1の配列に記憶されてよい。
【0033】
データベースは記憶媒体上に記憶されてよい。データベースは、ナビゲーション装置に配備されてよい。
【0034】
前述された特長、および下記に説明される特長は、示されているそれぞれの組み合わせでだけではなく、他の組み合わせで、または単独でも使用できることが理解されたい。
【0035】
実施形態の前記の特長および他の特長は、添付図に関連して読まれるときに、以下の実施形態の詳細な説明からより明らかになるだろう。図中、類似する参照番号が類似する要素を指す。
例えば、本発明は以下の項目を提供する。
(項目1)
ナビゲーション装置用データベース(10)であって、上記データベース(10)は、地形の三次元表面を定義するデジタル標高モデルデータを含み、上記データベース(10)がタイリング(8)の複数のタイル(11)の各タイル(11)のために、
−それぞれのタイル(11)のための、複数の不整三角網、TIN(18、19)の頂点(AからH)の三次元座標を含む第1の配列(23)と、
−複数の第2の配列(24、25)であって、各第2の配列(24、25)がそれぞれTIN(18、19)の三角面を定義し、上記それぞれのTIN(18、19)の三角面を定義するために上記第1の配列に頂点(AからH)座標が記憶される上記頂点(AからH)の複数のインデックスを含む、複数の第2の配列(23)と、
を記憶する、データベース。
(項目2)
上記複数の第2の配列(24、25)の各第2の配列(24、25)が三角形の片である、上記項目のいずれかに記載のデータベース(10)。
(項目3)
少なくとも1つの頂点(AからH)のインデックスが、異なる第2の配列(24、25)に含まれる、上記項目のいずれかに記載のデータベース(10)。
(項目4)
上記データベース(10)が、上記複数のタイル(11)の各タイル(11)のために、少なくとも2つの第2の配列(24、25)を記憶する、上記項目のいずれかに記載のデータベース(10)。
(項目5)
上記データベース(10)が、上記複数のタイル(11)の各タイル(11)のために、少なくとも6つの第2の配列を記憶する、上記項目のいずれかに記載のデータベース(10)。
(項目6)
上記第1の配列(23)の頂点(AからH)のためのエントリが、頂点座標のための距離メトリックに従って順序付けられ、上記第1の配列(23)が、デルタ符号化形式で上記三次元座標を含む、上記項目のいずれかに記載のデータベース(10)。
(項目7)
上記項目のいずれか1つの上記データベース(10)と、
光出力装置(4)と、
上記データベース(10)に、および上記光出力装置(4)に結合される処理装置(2)であって、上記データベース(10)から取り出されるデータに基づいて、三次元地形の表示を出力するために上記光出力装置(4)を制御するように構成される上記処理装置(2)と、
を備える、ナビゲーション装置(1)
(項目8)
上記処理装置(2)が、複数の不整三角網、TIN(18、19)をレンダリングし、上記斜視図を生成するように構成され、上記処理装置(2)が、上記データベース(10)の上記同じ第1の配列(23)から上記複数のTIN(18、19)の頂点(AからH)の三次元座標を決定するように構成される、上記項目のいずれかに記載のナビゲーション装置。
(項目9)
三次元地形の表示を出力する方法であって、上記三次元地形の上記表示が、上記項目のいずれか1つに記載のデータベース(10)を使用して生成される方法。
(項目10)
複数の不整三角網、TIN(18、19)がレンダリングされ、上記複数のTIN(18、19)の頂点(AからH)のための頂点座標が、上記データベース(10)の上記同じ第1の配列(23)から取り出される、上記項目のいずれかに記載の方法。
(項目11)
ナビゲーション装置(1)用のデータベース(10)を生成する方法であって、タイリング(8)の各タイル(11)のためにそれぞれ実行される、
−上記それぞれのタイル(8)のために定義される複数の不整三角網、TIN(18、19)の頂点(AからH)の三次元頂点座標を決定するステップと、
−上記決定された頂点座標を含む第1の配列(23)を生成するステップと、
−上記複数のTIN(18、19)の各TINのために第2の配列(24、25)を生成するステップであって、各第2の配列(24、25)が、頂点(AからH)座標が、上記それぞれのTIN(18、19)の三角面を定義するために上記第1の配列(23)に含まれる上記頂点(AからH)の複数のインデックスを含む生成するステップと、
を含む、方法。
(項目12)
上記複数の第2の配列(24、25)の各第2の配列(24、25)が三角形の片として生成される、上記項目のいずれかに記載の方法。
(項目13)
上記複数の第2の配列(24、25)が、少なくとも1つの頂点(AからH)のインデックスが異なる第2の配列(24、25)に含まれるように生成される、上記項目のいずれかに記載の方法。
(項目14)
上記複数のタイルの各タイル(11)のために、少なくとも2つの第2の配列(24、25)が生成される、上記項目のいずれかに記載の方法。
(項目15)
頂点(AからH)座標が、距離メトリックに従って上記第1の配列(23)に含まれる頂点(AからH)の順序を決定することと、
上記第1の配列(23)を生成するときに、上記三次元頂点座標をデルタ符号化することと、
をさらに含む、上記項目のいずれかに記載の方法。
摘要
ナビゲーション装置用のデータベース(10)は、三次元表面を定義するデジタル標高モデルデータを含む。データベース(10)は、タイリングの複数のタイルのために、複数の不整三角網、TINの頂点の三次元座標を含む第1の配列(23)、および複数の第2の配列(24、25)を記憶する。各第2の配列(24、25)はそれぞれTINの三角面を定義し、前記それぞれのTINの三角面を定義するために頂点の複数の頂点インデックスを含む。地形の三次元表示を出力する方法、およびデータベースを生成する方法も説明される。
【図面の簡単な説明】
【0036】
【図1】ナビゲーション装置の概略ブロック図である。
【図2】重畳タイリングで地形を示す図である。
【図3】タイリングのタイルの平面図である。
【図4】タイルの三角形のパッチのための不整三角網(TIN)を示す斜視図である。
【図5】タイルの三角形のパッチのための不整三角網(TIN)を示す斜視図である。
【図6】データベースの概略図である。
【図7】2つのTINが定義されるタイルの平面図である。
【図8】図7の2つのTINを定義するデータの概略図である。
【図9】別の詳細レベルについてタイルの区切りを示す平面図である。
【図10】データベースを生成する方法のフローチャートである。
【図11】従来のデータベースの概略図である。
【発明を実施するための形態】
【0037】
図1は、実施形態によるナビゲーション装置1を概略で示す。ナビゲーション装置1は、ナビゲーション装置1の動作を制御する処理装置2を含む。処理装置2は、例えば、1つまたは複数のマイクロプロセッサ、デジタル信号プロセッサ、または特定用途向け集積回路の形をとる中央演算処理装置を備えてよい。処理装置2は、グラフィックプロセッサも含んでよい。ナビゲーション装置1は、記憶装置3に記憶されるデータベース10をさらに含む。記憶装置3は、ランダムアクセスメモリ、フラッシュメモリ、またはハードドライブ等の多様なタイプのメモリの任意の1つ、または任意の組み合わせだけではなく、コンパクトディスク(CD)、DVD、メモリカード等のリムーバブルメモリを含んでよい。ナビゲーション装置1は、光出力装置4も含む。ナビゲーション装置1は、位置センサおよび/または無線受信機および/または入力インタフェース5等の追加の構成部品も含んでよい。
【0038】
記憶装置3は、三次元地形を定義するデータベース10を記憶する。データベース10内のデータは、鳥瞰図で、または下から見た図斜視図で、もしくは類似で三次元マップを生成するため、つまり地形を視覚化するために処理装置2によって使用されてよい。
【0039】
以下により詳細に説明されるように、データベース10の中のデータは、タイリングに従って編成される。タイリングの各タイルのために、データベース内のデータが複数のTINを定義した。各TINは、矩形二等辺三角形の形状を有する三角形のパッチ上に定義されてよい。
【0040】
タイルのために複数のTINを定義するデータは、それぞれのタイルのために定義される複数のTINの全ての頂点の三次元座標が含まれる第1の配列をそれぞれ含む。第1の配列は、多様な頂点の座標3タプルを連続して含むリストであってよい。
【0041】
各タイルのデータは、それぞれがそれぞれのタイルのための複数のTINの内の1つの三角面を定義する複数の第2の配列を含む。各第2の配列は、多様な頂点の内のどの頂点が、TINの三角面の角に位置するのかを指定する頂点インデックスの配列であってよい。それによって、TINの三角面が定義される。
【0042】
各タイルのデータは、各TINの法線ベクトルの配列をさらに含んでよい。
【0043】
図2は、タイリング8が定義される地形の概略平面図である。地形は、陰影が付けられた領域によって概略で示されるように多様な標高に広がってよい。陰影領域は、海水位等の1つの標高レベルであってよい。一方、陰影が付けられていない領域は、他の標高レベルであってよく、標高の段階的変化を示す。
【0044】
タイリング8は、タイル11等の複数のタイルを有する。タイリング8は、地形をカバーするように定義される。タイリングのタイルは基本的に矩形、特に正方形である場合もあれば、大きなサイズのタイルの球面投影の影響を考慮に入れ、わずかに台形である場合もある。
【0045】
地形の三次元の表面構造は、少なくとも優れた近似まで、各タイルに定義される複数のTINによって表されてよい。TINは、実行時に表面構造をレンダリングするときに優れた性能を示す。
【0046】
図3は、タイル11の平面図である。タイル11は三角形のパッチ12および13に二等分される。それぞれの三角形のパッチ12,13は矩形二等辺三角形である。
【0047】
三角形のパッチの定義は、交互にタイル間で変わることがある。説明のため、三角形のパッチ12はタイル11の北西部分に位置し、三角形のパッチ13は南東部分に位置する。タイル11と側面を共用するタイルは、一方の三角形のパッチがタイルの北東部分に位置し、他の三角形のパッチがタイルの南西部分に位置するように二等分されてよい。
【0048】
三角形のパッチ12、13の内の各パッチ上に、TINが定義されてよい。図4は、三角形のパッチ12上に定義されたTIN18を示す。図5は、三角形のパッチ19に定義された別のTIN19を示す。
【0049】
TIN18、19はいくつかの共通の頂点を有する。データの冗長性を削減するために、2つのTIN18よび19を定義するデータは、タイルのために、TIN18の全頂点およびTIN19の全頂点の三次元座標が含まれる頂点座標の大局的なリストを使用する。それにも関わらず、TIN18とTIN19両方の頂点である頂点の頂点座標は、頂点座標のリスト内で一度だけしか記憶されない。
【0050】
図6は、データベース10の概略図である。データベース10は、ナビゲーション装置1で使用されてよい。データベース10は、複数のタイルの各タイルに、複数のTINを定義する。
【0051】
データベース10は、第1のタイルのために複数のTINを定義するデータ21、および第2のタイルのために複数のTINを定義するデータ22を含む。より大きな数のタイルにとって、データ21およびデータ22に類似するデータは、追加の各タイルのためにデータベース10に記憶されるだろう。
【0052】
さまざまなタイルのためのデータ21、22は同じ基本構造を有する。データ21の構造だけが、見本となるようにより詳細に説明される。
【0053】
データ21は、一意のタイル識別子および複数のTINを定義するデータを含む。データ21は、タイルに定義されるTINのどれか1つに含まれる全ての頂点の三次元頂点座標の、例えばリスト等の配列23を含む。
【0054】
データ21は、1つのTINの三角形表面を説明する第2の配列24を含む。第2の配列24は、頂点インデックスの、例えばリストまたは表等の配列であってよい。第2の配列24は、第1の配列23にエントリを有する多様な頂点の内のどの頂点がTINの三角面の角を形成するのかを定義してよい。第2の配列24は、三角形の片の形をとる三角面を定義してよい。
【0055】
データ21は、別のTINの三角面を説明する第2の配列25を含む。第2の配列25も、頂点インデックスの、例えばリストまたは表等の配列であってよい。第2の配列25は、第1の配列23のエントリを有する多様な頂点の内のどの頂点が他のTINの三角面の角を形成するのかを定義してよい。第2の配列25は、三角形の片の形を取る三角面を定義してよい。
【0056】
2つ以上のTINがタイル上に定義される場合、それぞれ頂点インデックスの配列である相応してより多くの数の第2の配列が、データ21に含まれる。第1の配列23に含まれる頂点の数は、TINの数が増加するにつれて増加することがある。ただし、全ての第2の配列は、例えば6つの第2の配列等の2つを超える第2の配列が提供される場合にも同じ第1の配列23を参照する。複数のTINの頂点である任意の頂点の場合、頂点座標は、それぞれの頂点を含むTINの数とは無関係に、一度だけしか第1の配列23に記憶されない。
【0057】
第2のエントリは、TINの複数の三角面を三角形の片として記憶してよい。これは、図7および図8に関して示される。
【0058】
図7は、タイル11の平面図を示す。タイル11は、三角形のパッチ12、13に二等分される。1つのTINが、パッチ12上に定義される。別のTINは、パッチ13上に定義される。2つのTINは、共通の頂点A、B、およびEを有する。つまり頂点A、B、およびEは、パッチ12上に定義されるTINおよびパッチ13上に定義されるTINの頂点である。
【0059】
図8は、タイル11上のデジタル標高モデル(DEM)を表すデータ21の概略表示である。データ21は、頂点AからHの頂点座標が記憶される第1の配列を含む。頂点A、BおよびEの三次元座標は、第1の配列に一度しか含まれない。
【0060】
データ21は、三角形パッチ12上のTINの三角面を説明する第2の配列24を有する。第2の配列24は、多様な頂点がリストに含まれる三角形の片である。説明のため、三角形のパッチ12上のTINは、三角形の片「ACBDEFC」として定義されてよい。実行時、これは、三角形ACB、CBD、BDE、DEF、およびEFCを定義するように分解される。したがって、全ての三角面は、頂点インデックスのリストによってコンパクトに定義され得る。全ての頂点の三次元座標は、第1の配列から取り出すことができる。したがって、三角面は再構築されてよい。
【0061】
データ21は、三角形のパッチ13上のTINの三角面を説明する別の第2の配列25を有する。第2の配列25は、多様な頂点がリストの中に含まれる三角形の片である。説明のため、三角形のパッチ13上のTINは、三角形の片「AGBHE」として定義されてよい。実行時、これは三角形AGB、GBH、およびBHEを定義するように分解される。このようにして、全ての三角面が、頂点インデックスのリストによってコンパクトに定義されてよい。全ての頂点の三次元座標は、第1の配列から取り出すことができる。したがって、三角面は再構築されてよい。
【0062】
2つ以上のTINが、各タイルに定義されてよい。TINは、互いと重複してもよい。説明のため、それぞれタイルサイズの半分に等しい面積を有する三角形のパッチ上に定義される2つのTINに加えて、それぞれタイルサイズの4分の1に等しい面積を有する三角形のパッチ上に定義される4つのTINが、タイルごとに使用されてよい。
【0063】
図9は、4つの矩形二等辺三角形の三角形のパッチ14から17に区切られるタイル11を示す。パッチ14および17は、パッチ12を二等分することによって得られる。パッチ15および16は、パッチ13を二等分することによって得られる。三角形のパッチ14から17のそれぞれのパッチ上に、別のTINが定義されてよい。
【0064】
より小さい三角形のパッチ14から17に定義されるTINは、所与のタイルサイズのために、より大きな詳細のレベルで地形を示すために使用されてよい。異なる詳細のレベルが結合されてよい。説明のため、地形をレンダリングするときに、より大きな三角形のパッチ12およびその上に定義されるTINが、より小さい三角形のパッチ15、16およびその上に結合されるTINと結合されてよい。
【0065】
合計6つのTINが1つのタイルに定義されると、頂点インデックスの配列が、6つのTINの内の各TINに提供されてよい。配列は、それぞれ、図7および図8に関して説明されたように、三角形の片であってよい。頂点インデックスの配列の各配列が、三次元座標が全く同一の第1の配列に記憶される頂点を参照してよい。
【0066】
各タイルのために、複数のTINのための頂点座標を含む大局的な第1の配列があるデータベースを作成するとき、第1の配列のエントリは、距離メトリックに従って順序付けられてよい。つまり、頂点座標が第1の配列に記憶されるシーケンスは、頂点間の距離に基づいて選択されてよい。これによって、頂点座標をデルタ符号化形式で記憶できるようになる。
【0067】
図10は、ナビゲーション装置用にデータベースを生成する方法30のフローチャートである。方法は、ナビゲーション装置1のデータベース10を生成するために使用されてよい。
【0068】
31で、タイルのために定義された多様なTINの全ての頂点のセットが決定される。頂点のセットは、タイルに定義された2つまたは6つのTINの全ての頂点のセットであってよい。全ての頂点のセットはMとして示される。
【0069】
32で、頂点の内の1つが選択される。頂点は、無作為に、またはデルタ符号化チェーンの開始点を決定するアルゴリズムを使用して選択されてよい。エントリは、選択された頂点のための第1の配列で生成される。エントリは選択された頂点の頂点座標を含む。
【0070】
追加のエントリが、対話式で第1の配列に追加される。第1の反復では、第1の配列だけが32で選択される頂点エントリを有する。
【0071】
33で、選択された頂点がセットMから削除される。セットMは、第1の配列でまだエントリが生成されていない頂点だけを含むように更新される。
【0072】
34で、第1の配列の最後のエントリが以前生成された頂点から最小の距離を有するMの頂点が決定される。第1の反復では、32で選択された頂点から最小距離を有する頂点が識別される。任意の適切な距離メトリックが使用されてよい。説明のため、Lpメトリックが使用されてよい。
【0073】
35で、34で決定された頂点の頂点座標と、第1の配列の最後のエントリが以前生成された頂点の頂点座標との間の座標デルタが決定される。この座標デルタが、第1の配列の新しい最後のエントリとして第1の配列の中に書き込まれる。それによって、頂点座標のデルタ符号化が実行されてよい。デルタ符号化が実行されてはならない場合、(座標デルタよりむしろ)34で選択された頂点の座標が、第1の配列の新しい最後のエントリとして第1の配列に書き込まれてよい。
【0074】
36で、Mの中に複数の頂点があるかどうか、つまり多様なTINの全ての頂点のために、第1の配列でエントリがすでに生成されているかどうかが決定される。Mの中に複数の頂点が残されている場合、方法は33に戻り、ステップ33から36が繰り返される。それ以外の場合、方法は37に進む。
【0075】
37で、三角形の片が各TINに生成される。三角形の片は、頂点インデックスのリストとして生成されてよく、各頂点インデックスは、座標が第1の配列に登録されている頂点の内の1つを一意に識別する。
【0076】
38で、第1の配列および第2の配列はデータベースに記憶される。
【0077】
方法30は、タイリングの複数のタイルに実行されてよい。方法30は、タイリングの全タイルに実行されてよい。
【0078】
方法30を使用して生成されるデータベースは、車両ナビゲーション装置に配備されてよい。
【0079】
実施形態にかかる方法および方法が詳細に説明されてきたが、他の実施形態で修正が実施されてよい。説明のために、いくつかの実施形態では正方形のタイルのタイリングが説明されたが、他のタイルの形状も使用されてよい。
【0080】
本発明の実施形態は、それに制限されることなく三次元地形を視覚するために使用されてよい。
【技術分野】
【0001】
本発明の実施形態は、ナビゲーション装置での高さ情報の使用に関連する方法および装置に関する。本発明の実施形態は、特に、ナビゲーション装置用データベース、地形の三次元表示を出力する方法、およびナビゲーション装置用データベースを生成する方法に関する。本発明の実施形態は、特に、高さ情報がタイリングのタイルのためにそれぞれ定義されるTINの形で記憶される、かかる装置および方法に関する。
【背景技術】
【0002】
地形の高さ情報は、ナビゲーション装置でますます幅広く使用されている。かかる高さ情報が使用され得る1つの例示的な分野が、三次元地図の出力である。光出力装置は、電子マップを出力するために使用されてよい。電子マップは小型装置および/または携帯装置の画面に表示されるので、それらは多用途且つコンパクトであるという優位点を有する。三次元(3D)マップ、つまり斜視表示は、それらの高い認識品質のために、ユーザにとって特に貴重である場合がある。つまり、従来の二次元表示に比較して、通りの交差点等の環境領域の認識は、三次元マップが出力されるときに特に容易になり得る。
【0003】
数値標高モデル(DEM)データは、不整三角網(TIN)の形で記憶されてよい。TINから地形をレンダリングするときに、良い実行時性能が達成され得る。DEMデータはタイリングに従って編成されてよく、タイリングのタイルは、地形のDEMデータがレンダリング用に使用できる領域をカバーする。矩形または台形の形状を有するタイルは、複数の三角形のパッチに分けられてよい。このパッチの各パッチに、TINが定義されてよい。したがって、複数のTINがタイリングの各タイルのためにそれぞれ定義されてよい。
【0004】
タイルのためにTINを記憶するための1つの手法では、各TINのデータは、TINを再構築するために必要とされる全情報がTINにとって別個のデータ構造で含まれるように別々に記憶される。従来の手法では、TINを説明するデータは、それぞれのTINの頂点の三次元座標(つまり、座標の3タプル)が記憶される配列と、頂点の内のどの頂点がTINの多様な三角面の角をそれぞれ形成するのかを指定するために頂点インデックスを含む別の配列と、おそらく三角面の法線ベクトルを定義するさらに別の配列とを含んでよい。
【0005】
図11は、1つのタイルに複数のTINを定義するデータ41を示す。データ41は、そのタイルの一意の識別子を示す。配列42は、タイル上に定義される第1のTINの全ての頂点の座標を定義する。配列43は頂点インデックスを含み、第1のTINの三角面を定義する。別の配列(図11では不図示)は、第1のTINの法線ベクトルに関する情報を含んでよい。配列44は、タイル上に定義される第2のTINの全ての頂点の座標を定義する。配列45は座標頂点を含み、第2のTINの三角面を定義する。別の配列(図11では不図示)は、第2のTINの法線ベクトルに関する情報を含んでよい。
【0006】
図41に関して説明された従来の手法は、冗長な情報の記憶につながる場合がある。説明のために、第1のTINおよび第2のTINが共通の頂点を有する場合、これらの頂点の三次元座標は複数回記憶されることがある。つまり、座標3タプルが、配列42と配列44の両方に含まれることがある。かかる冗長性は、記憶空間の要件の観点からは望ましくない。
【発明の概要】
【発明が解決しようとする課題】
【0007】
したがって、上述された欠点を軽減するデータベースおよび方法に対するニーズがある。特に、冗長性の問題を軽減しつつ、タイリングの各タイルに複数のTINをそれぞれ定義できるようにするデータベースおよび方法に対するニーズがある。
【課題を解決するための手段】
【0008】
このニーズは、独立請求項に詳述されるデータベースおよび方法によって対処される。従属請求項が実施形態を定義する。
【0009】
一態様によると、ナビゲーション装置用データベースが提供される。このデータベースは、地形の三次元表面を定義するデジタル標高モデル(DEM)データを含む。データベースは、タイリングの複数のタイルの内のそれぞれのタイルのために、1つの第1の配列、および複数の第2の配列を記憶する。第1の配列は、それぞれのタイルのために、複数の不整三角網、TINの頂点の三次元座標を含む。各第2の配列はそれぞれTINを定義し、それぞれのTINの三角面を定義するために頂点座標が第1の配列に記憶される頂点の複数のインデックスを含む。
【0010】
データベースでは、タイルに定義される多様なTINの頂点の三次元座標は、すべて1つの第1の配列の中に集められ得る。それによって、所望されないデータ冗長性に関連する問題は軽減され得る。複数の第2の配列は、全く同一の第1の配列を参照してよい。
【0011】
データベースは、タイリングの複数のタイルの各タイルのために、頂点の座標を含むただ1つの第1の配列をそれぞれ記憶してよい。
【0012】
頂点の内の各頂点のために、その頂点がいくつかのTINの頂点であったとしても、三次元座標は第1の配列の中に一度だけ含まれる。
【0013】
複数の第2の配列の各第2の配列は、三角形の片であってよい。それによって、TINのコンパクトな説明が提供される。記憶空間の要件は削減され得る。
【0014】
少なくとも1つの頂点のインデックスは、異なる第2の配列に含まれてよい。それによって、対応するTINが共通する1つの頂点を有するときに、第1の配列の同じ諸エントリが異なる第2の諸配列によって活用される。
【0015】
データベースは、複数のタイルの各タイルに、少なくとも2つの第2の配列を記憶してよい。これによって、タイルを2つの三角形のパッチに分割できる。
【0016】
三角形のパッチのそれぞれのパッチにTINが定義されてよい。三角形のパッチは、矩形二等辺三角形であってよい。それによって、異なる詳細レベルからのデータの組み合わせが容易になる。
【0017】
データベースは、複数のタイルの各タイルに、少なくとも6つの第2の配列を記憶してよい。これによって、地形は所与のタイルサイズについて2つの異なる詳細レベルで記憶できるようになる。第2の配列の内の少なくとも1つの配列が、同じタイルの第2の配列の別の配列によって表されるTINと部分的にまたは完全に重複するTINに対応してよい。第2の配列の内の少なくとも1つは、同じタイルの第2の配列の別の配列によって表されるTINによってカバーされる領域内に完全に包含されるTINに対応してよい。複数のタイルの各タイルのために、6つの第2の配列の内の2つがそれぞれ、タイルを二等分することによって得られる三角形のパッチ上にTINを定義してよい。他の4つの第2の配列は、それぞれ、タイルを4つの等しい大きさの矩形二等辺三角形に区切ることによって得られる三角形のパッチ上にTINを定義してよい。より小さいサイズの三角形パッチ上に定義されたTINは、それぞれ部分的にまたは完全に、大きい方のサイズの三角形パッチ上に定義されたTINと重複してよい。
【0018】
第1の配列での頂点のエントリは、頂点座標の距離メトリックに従って順序付けられてよい。第1の配列でのエントリのシーケンスは、第1の配列にエントリを有する任意の所与の頂点にとって、第1の配列の連続エントリが、所与の頂点のためのエントリに先行するエントリの内のどのエントリにも含まれず、距離メトリックに従って所与の頂点から最小の距離を有する、1つの頂点の頂点座標を含むように選択されてよい。それによって、距離メトリックに従って決定される、連続エントリの頂点座標間の距離が小さいエントリの順序が確立され得る。距離メトリックはLpメトリックまたは任意の他の適切な距離メトリックであってよい。
【0019】
第1の配列でのエントリが距離メトリックに従って順序付けられるとき、デルタ符号化が、第1の配列に記憶される頂点座標に使用されてよい。基準の絶対フレームでの、またはタイル上の特徴点を基準にした頂点座標が、第1の配列の第1のエントリに記憶されてよい。それぞれの続くエントリについては、このエントリに割り当てられる頂点の頂点座標と、直前に先行するエントリに割り当てられる頂点の頂点座標との間の座標(つまり距離ベクトル)の差異が第1の配列に記憶されてよい。エントリが距離メトリックに従って順序付けられた状態で、ゼロであるエントリの最上位ビットは省略されてよい。それによって、記憶空間の要件はさらに削減され得る。
【0020】
タイリングのいくつかまたは全てのタイルのために、データベースは、それぞれのタイルの複数のTINの頂点の三次元座標を含む一つ以上のの第1の配列を記憶してよい。この場合、第1の配列の内の少なくとも1つが、それぞれのタイルの異なる第2の配列によって参照される。
【0021】
別の態様に従って、ナビゲーション装置が提供される。ナビゲーション装置は、任意の1つの態様または実施形態のデータベース、光出力装置、および処理装置を含む。処理装置はデータベースに、および光出力装置に結合される。処理装置は、光出力装置を制御し、データベースから取り出されたデータに基づいて三次元地形の表示を出力するように構成されてよい。
【0022】
処理装置は、タイルが斜視図を生成するために複数の不整三角網、TINをレンダリングするように構成されてよい。処理装置は、それぞれのタイルのためのデータベースに記憶される全く同一の第1の配列から複数のTINの頂点の三次元座標を決定するように構成されてよい。
【0023】
別の態様に従って、三次元地形の表示が、任意の1つの態様または実施形態のデータベースを使用して生成される、三次元地形の表示を出力する方法が提供される。
【0024】
方法では、複数の不整三角網、TINがタイリングのタイルのためにレンダリングされてよい。複数のTINの頂点の頂点座標は、それぞれのファイルのためのデータベースに記憶される全く同一の第1の配列から取り出されてよい。
【0025】
別の態様に従って、ナビゲーション装置用データベースを生成する方法が提供される。方法では、以下のステップが、タイリングのタイルごとにそれぞれ実行される。それぞれのタイルに定義される、複数の不整三角網、TINの頂点の頂点座標が決定される。多様なTINのために決定された頂点座標を含む第1の配列が生成される。第2の配列は、複数のTINのそれぞれのTINにそれぞれ生成され、したがって各第2の配列は、頂点座標が第1の配列に含まれる複数の頂点のインデックスをそれぞれ含む。第2の配列は、どの頂点がそれぞれのTINの多様な三角形の方面の角に位置するのかを定義するように生成される。
【0026】
この方法では、複数の異なるTINの頂点座標が1つの第1の配列に集められる。冗長性の問題は、それによって緩和され得る。
【0027】
第1の配列は、頂点が複数のTINの頂点であったとしても、任意の頂点の三次元座標が第1の配列内に一度だけ含まれるように生成されてよい。
【0028】
複数の第2の配列の各第2の配列は、三角形の片として生成されてよい。それによって、TINのコンパクトな説明が提供される。記憶空間要件が削減され得る。
【0029】
複数の第2の配列は、少なくとも1つの頂点のインデックスが異なる第2の配列に含まれるように生成されてよい。それによって、第1の配列の同じエントリは、対応するTINが共通のそれぞれの頂点を有するときに、異なる第2の配列によって参照される。
【0030】
複数のタイルの内の各タイルのために、少なくとも2つの第2の配列が生成されてよい。複数のタイルの各タイルのために、少なくとも6つの第2の配列が生成されてよい。それによって、矩形二等辺三角形として構成される三角形のパッチが定義されてよく、そのそれぞれにTINが定義されてよい。それによって、異なる詳細レベルからデータを結合することが容易になる。
【0031】
方法は、距離メトリックに従って第1の配列内の頂点のエントリの順序を決定することを含んでよい。この目的のために、頂点が開始頂点となるように選択され、その開始頂点のために第1の配列の第1の位置にエントリが生成される手順が実行されてよい。その後、続くステップが、頂点のためのエントリを第1の配列に追加するために繰り返し実行される。第1の配列の中で最後である頂点のために、第1の配列にまだ含まれていない残りの頂点の内の、第1の配列の中で最後である頂点から最小距離を有する1つが選択される。この頂点のエントリは、次に第1の配列の最後に追加される。プロセスは、エントリが全ての頂点のための第1の配列で生成されるまで続行してよい。
【0032】
デルタ符号化は、頂点の座標の3つのタプルのために使用されてよい。頂点のためのエントリが距離メトリックに従って第1の配列で生成される場合、距離ベクトルは最も近傍の頂点が決定されると決定され得る。絶対的な座標ではなく、連続頂点間の距離ベクトルが、第1の配列に記憶されてよい。
【0033】
データベースは記憶媒体上に記憶されてよい。データベースは、ナビゲーション装置に配備されてよい。
【0034】
前述された特長、および下記に説明される特長は、示されているそれぞれの組み合わせでだけではなく、他の組み合わせで、または単独でも使用できることが理解されたい。
【0035】
実施形態の前記の特長および他の特長は、添付図に関連して読まれるときに、以下の実施形態の詳細な説明からより明らかになるだろう。図中、類似する参照番号が類似する要素を指す。
例えば、本発明は以下の項目を提供する。
(項目1)
ナビゲーション装置用データベース(10)であって、上記データベース(10)は、地形の三次元表面を定義するデジタル標高モデルデータを含み、上記データベース(10)がタイリング(8)の複数のタイル(11)の各タイル(11)のために、
−それぞれのタイル(11)のための、複数の不整三角網、TIN(18、19)の頂点(AからH)の三次元座標を含む第1の配列(23)と、
−複数の第2の配列(24、25)であって、各第2の配列(24、25)がそれぞれTIN(18、19)の三角面を定義し、上記それぞれのTIN(18、19)の三角面を定義するために上記第1の配列に頂点(AからH)座標が記憶される上記頂点(AからH)の複数のインデックスを含む、複数の第2の配列(23)と、
を記憶する、データベース。
(項目2)
上記複数の第2の配列(24、25)の各第2の配列(24、25)が三角形の片である、上記項目のいずれかに記載のデータベース(10)。
(項目3)
少なくとも1つの頂点(AからH)のインデックスが、異なる第2の配列(24、25)に含まれる、上記項目のいずれかに記載のデータベース(10)。
(項目4)
上記データベース(10)が、上記複数のタイル(11)の各タイル(11)のために、少なくとも2つの第2の配列(24、25)を記憶する、上記項目のいずれかに記載のデータベース(10)。
(項目5)
上記データベース(10)が、上記複数のタイル(11)の各タイル(11)のために、少なくとも6つの第2の配列を記憶する、上記項目のいずれかに記載のデータベース(10)。
(項目6)
上記第1の配列(23)の頂点(AからH)のためのエントリが、頂点座標のための距離メトリックに従って順序付けられ、上記第1の配列(23)が、デルタ符号化形式で上記三次元座標を含む、上記項目のいずれかに記載のデータベース(10)。
(項目7)
上記項目のいずれか1つの上記データベース(10)と、
光出力装置(4)と、
上記データベース(10)に、および上記光出力装置(4)に結合される処理装置(2)であって、上記データベース(10)から取り出されるデータに基づいて、三次元地形の表示を出力するために上記光出力装置(4)を制御するように構成される上記処理装置(2)と、
を備える、ナビゲーション装置(1)
(項目8)
上記処理装置(2)が、複数の不整三角網、TIN(18、19)をレンダリングし、上記斜視図を生成するように構成され、上記処理装置(2)が、上記データベース(10)の上記同じ第1の配列(23)から上記複数のTIN(18、19)の頂点(AからH)の三次元座標を決定するように構成される、上記項目のいずれかに記載のナビゲーション装置。
(項目9)
三次元地形の表示を出力する方法であって、上記三次元地形の上記表示が、上記項目のいずれか1つに記載のデータベース(10)を使用して生成される方法。
(項目10)
複数の不整三角網、TIN(18、19)がレンダリングされ、上記複数のTIN(18、19)の頂点(AからH)のための頂点座標が、上記データベース(10)の上記同じ第1の配列(23)から取り出される、上記項目のいずれかに記載の方法。
(項目11)
ナビゲーション装置(1)用のデータベース(10)を生成する方法であって、タイリング(8)の各タイル(11)のためにそれぞれ実行される、
−上記それぞれのタイル(8)のために定義される複数の不整三角網、TIN(18、19)の頂点(AからH)の三次元頂点座標を決定するステップと、
−上記決定された頂点座標を含む第1の配列(23)を生成するステップと、
−上記複数のTIN(18、19)の各TINのために第2の配列(24、25)を生成するステップであって、各第2の配列(24、25)が、頂点(AからH)座標が、上記それぞれのTIN(18、19)の三角面を定義するために上記第1の配列(23)に含まれる上記頂点(AからH)の複数のインデックスを含む生成するステップと、
を含む、方法。
(項目12)
上記複数の第2の配列(24、25)の各第2の配列(24、25)が三角形の片として生成される、上記項目のいずれかに記載の方法。
(項目13)
上記複数の第2の配列(24、25)が、少なくとも1つの頂点(AからH)のインデックスが異なる第2の配列(24、25)に含まれるように生成される、上記項目のいずれかに記載の方法。
(項目14)
上記複数のタイルの各タイル(11)のために、少なくとも2つの第2の配列(24、25)が生成される、上記項目のいずれかに記載の方法。
(項目15)
頂点(AからH)座標が、距離メトリックに従って上記第1の配列(23)に含まれる頂点(AからH)の順序を決定することと、
上記第1の配列(23)を生成するときに、上記三次元頂点座標をデルタ符号化することと、
をさらに含む、上記項目のいずれかに記載の方法。
摘要
ナビゲーション装置用のデータベース(10)は、三次元表面を定義するデジタル標高モデルデータを含む。データベース(10)は、タイリングの複数のタイルのために、複数の不整三角網、TINの頂点の三次元座標を含む第1の配列(23)、および複数の第2の配列(24、25)を記憶する。各第2の配列(24、25)はそれぞれTINの三角面を定義し、前記それぞれのTINの三角面を定義するために頂点の複数の頂点インデックスを含む。地形の三次元表示を出力する方法、およびデータベースを生成する方法も説明される。
【図面の簡単な説明】
【0036】
【図1】ナビゲーション装置の概略ブロック図である。
【図2】重畳タイリングで地形を示す図である。
【図3】タイリングのタイルの平面図である。
【図4】タイルの三角形のパッチのための不整三角網(TIN)を示す斜視図である。
【図5】タイルの三角形のパッチのための不整三角網(TIN)を示す斜視図である。
【図6】データベースの概略図である。
【図7】2つのTINが定義されるタイルの平面図である。
【図8】図7の2つのTINを定義するデータの概略図である。
【図9】別の詳細レベルについてタイルの区切りを示す平面図である。
【図10】データベースを生成する方法のフローチャートである。
【図11】従来のデータベースの概略図である。
【発明を実施するための形態】
【0037】
図1は、実施形態によるナビゲーション装置1を概略で示す。ナビゲーション装置1は、ナビゲーション装置1の動作を制御する処理装置2を含む。処理装置2は、例えば、1つまたは複数のマイクロプロセッサ、デジタル信号プロセッサ、または特定用途向け集積回路の形をとる中央演算処理装置を備えてよい。処理装置2は、グラフィックプロセッサも含んでよい。ナビゲーション装置1は、記憶装置3に記憶されるデータベース10をさらに含む。記憶装置3は、ランダムアクセスメモリ、フラッシュメモリ、またはハードドライブ等の多様なタイプのメモリの任意の1つ、または任意の組み合わせだけではなく、コンパクトディスク(CD)、DVD、メモリカード等のリムーバブルメモリを含んでよい。ナビゲーション装置1は、光出力装置4も含む。ナビゲーション装置1は、位置センサおよび/または無線受信機および/または入力インタフェース5等の追加の構成部品も含んでよい。
【0038】
記憶装置3は、三次元地形を定義するデータベース10を記憶する。データベース10内のデータは、鳥瞰図で、または下から見た図斜視図で、もしくは類似で三次元マップを生成するため、つまり地形を視覚化するために処理装置2によって使用されてよい。
【0039】
以下により詳細に説明されるように、データベース10の中のデータは、タイリングに従って編成される。タイリングの各タイルのために、データベース内のデータが複数のTINを定義した。各TINは、矩形二等辺三角形の形状を有する三角形のパッチ上に定義されてよい。
【0040】
タイルのために複数のTINを定義するデータは、それぞれのタイルのために定義される複数のTINの全ての頂点の三次元座標が含まれる第1の配列をそれぞれ含む。第1の配列は、多様な頂点の座標3タプルを連続して含むリストであってよい。
【0041】
各タイルのデータは、それぞれがそれぞれのタイルのための複数のTINの内の1つの三角面を定義する複数の第2の配列を含む。各第2の配列は、多様な頂点の内のどの頂点が、TINの三角面の角に位置するのかを指定する頂点インデックスの配列であってよい。それによって、TINの三角面が定義される。
【0042】
各タイルのデータは、各TINの法線ベクトルの配列をさらに含んでよい。
【0043】
図2は、タイリング8が定義される地形の概略平面図である。地形は、陰影が付けられた領域によって概略で示されるように多様な標高に広がってよい。陰影領域は、海水位等の1つの標高レベルであってよい。一方、陰影が付けられていない領域は、他の標高レベルであってよく、標高の段階的変化を示す。
【0044】
タイリング8は、タイル11等の複数のタイルを有する。タイリング8は、地形をカバーするように定義される。タイリングのタイルは基本的に矩形、特に正方形である場合もあれば、大きなサイズのタイルの球面投影の影響を考慮に入れ、わずかに台形である場合もある。
【0045】
地形の三次元の表面構造は、少なくとも優れた近似まで、各タイルに定義される複数のTINによって表されてよい。TINは、実行時に表面構造をレンダリングするときに優れた性能を示す。
【0046】
図3は、タイル11の平面図である。タイル11は三角形のパッチ12および13に二等分される。それぞれの三角形のパッチ12,13は矩形二等辺三角形である。
【0047】
三角形のパッチの定義は、交互にタイル間で変わることがある。説明のため、三角形のパッチ12はタイル11の北西部分に位置し、三角形のパッチ13は南東部分に位置する。タイル11と側面を共用するタイルは、一方の三角形のパッチがタイルの北東部分に位置し、他の三角形のパッチがタイルの南西部分に位置するように二等分されてよい。
【0048】
三角形のパッチ12、13の内の各パッチ上に、TINが定義されてよい。図4は、三角形のパッチ12上に定義されたTIN18を示す。図5は、三角形のパッチ19に定義された別のTIN19を示す。
【0049】
TIN18、19はいくつかの共通の頂点を有する。データの冗長性を削減するために、2つのTIN18よび19を定義するデータは、タイルのために、TIN18の全頂点およびTIN19の全頂点の三次元座標が含まれる頂点座標の大局的なリストを使用する。それにも関わらず、TIN18とTIN19両方の頂点である頂点の頂点座標は、頂点座標のリスト内で一度だけしか記憶されない。
【0050】
図6は、データベース10の概略図である。データベース10は、ナビゲーション装置1で使用されてよい。データベース10は、複数のタイルの各タイルに、複数のTINを定義する。
【0051】
データベース10は、第1のタイルのために複数のTINを定義するデータ21、および第2のタイルのために複数のTINを定義するデータ22を含む。より大きな数のタイルにとって、データ21およびデータ22に類似するデータは、追加の各タイルのためにデータベース10に記憶されるだろう。
【0052】
さまざまなタイルのためのデータ21、22は同じ基本構造を有する。データ21の構造だけが、見本となるようにより詳細に説明される。
【0053】
データ21は、一意のタイル識別子および複数のTINを定義するデータを含む。データ21は、タイルに定義されるTINのどれか1つに含まれる全ての頂点の三次元頂点座標の、例えばリスト等の配列23を含む。
【0054】
データ21は、1つのTINの三角形表面を説明する第2の配列24を含む。第2の配列24は、頂点インデックスの、例えばリストまたは表等の配列であってよい。第2の配列24は、第1の配列23にエントリを有する多様な頂点の内のどの頂点がTINの三角面の角を形成するのかを定義してよい。第2の配列24は、三角形の片の形をとる三角面を定義してよい。
【0055】
データ21は、別のTINの三角面を説明する第2の配列25を含む。第2の配列25も、頂点インデックスの、例えばリストまたは表等の配列であってよい。第2の配列25は、第1の配列23のエントリを有する多様な頂点の内のどの頂点が他のTINの三角面の角を形成するのかを定義してよい。第2の配列25は、三角形の片の形を取る三角面を定義してよい。
【0056】
2つ以上のTINがタイル上に定義される場合、それぞれ頂点インデックスの配列である相応してより多くの数の第2の配列が、データ21に含まれる。第1の配列23に含まれる頂点の数は、TINの数が増加するにつれて増加することがある。ただし、全ての第2の配列は、例えば6つの第2の配列等の2つを超える第2の配列が提供される場合にも同じ第1の配列23を参照する。複数のTINの頂点である任意の頂点の場合、頂点座標は、それぞれの頂点を含むTINの数とは無関係に、一度だけしか第1の配列23に記憶されない。
【0057】
第2のエントリは、TINの複数の三角面を三角形の片として記憶してよい。これは、図7および図8に関して示される。
【0058】
図7は、タイル11の平面図を示す。タイル11は、三角形のパッチ12、13に二等分される。1つのTINが、パッチ12上に定義される。別のTINは、パッチ13上に定義される。2つのTINは、共通の頂点A、B、およびEを有する。つまり頂点A、B、およびEは、パッチ12上に定義されるTINおよびパッチ13上に定義されるTINの頂点である。
【0059】
図8は、タイル11上のデジタル標高モデル(DEM)を表すデータ21の概略表示である。データ21は、頂点AからHの頂点座標が記憶される第1の配列を含む。頂点A、BおよびEの三次元座標は、第1の配列に一度しか含まれない。
【0060】
データ21は、三角形パッチ12上のTINの三角面を説明する第2の配列24を有する。第2の配列24は、多様な頂点がリストに含まれる三角形の片である。説明のため、三角形のパッチ12上のTINは、三角形の片「ACBDEFC」として定義されてよい。実行時、これは、三角形ACB、CBD、BDE、DEF、およびEFCを定義するように分解される。したがって、全ての三角面は、頂点インデックスのリストによってコンパクトに定義され得る。全ての頂点の三次元座標は、第1の配列から取り出すことができる。したがって、三角面は再構築されてよい。
【0061】
データ21は、三角形のパッチ13上のTINの三角面を説明する別の第2の配列25を有する。第2の配列25は、多様な頂点がリストの中に含まれる三角形の片である。説明のため、三角形のパッチ13上のTINは、三角形の片「AGBHE」として定義されてよい。実行時、これは三角形AGB、GBH、およびBHEを定義するように分解される。このようにして、全ての三角面が、頂点インデックスのリストによってコンパクトに定義されてよい。全ての頂点の三次元座標は、第1の配列から取り出すことができる。したがって、三角面は再構築されてよい。
【0062】
2つ以上のTINが、各タイルに定義されてよい。TINは、互いと重複してもよい。説明のため、それぞれタイルサイズの半分に等しい面積を有する三角形のパッチ上に定義される2つのTINに加えて、それぞれタイルサイズの4分の1に等しい面積を有する三角形のパッチ上に定義される4つのTINが、タイルごとに使用されてよい。
【0063】
図9は、4つの矩形二等辺三角形の三角形のパッチ14から17に区切られるタイル11を示す。パッチ14および17は、パッチ12を二等分することによって得られる。パッチ15および16は、パッチ13を二等分することによって得られる。三角形のパッチ14から17のそれぞれのパッチ上に、別のTINが定義されてよい。
【0064】
より小さい三角形のパッチ14から17に定義されるTINは、所与のタイルサイズのために、より大きな詳細のレベルで地形を示すために使用されてよい。異なる詳細のレベルが結合されてよい。説明のため、地形をレンダリングするときに、より大きな三角形のパッチ12およびその上に定義されるTINが、より小さい三角形のパッチ15、16およびその上に結合されるTINと結合されてよい。
【0065】
合計6つのTINが1つのタイルに定義されると、頂点インデックスの配列が、6つのTINの内の各TINに提供されてよい。配列は、それぞれ、図7および図8に関して説明されたように、三角形の片であってよい。頂点インデックスの配列の各配列が、三次元座標が全く同一の第1の配列に記憶される頂点を参照してよい。
【0066】
各タイルのために、複数のTINのための頂点座標を含む大局的な第1の配列があるデータベースを作成するとき、第1の配列のエントリは、距離メトリックに従って順序付けられてよい。つまり、頂点座標が第1の配列に記憶されるシーケンスは、頂点間の距離に基づいて選択されてよい。これによって、頂点座標をデルタ符号化形式で記憶できるようになる。
【0067】
図10は、ナビゲーション装置用にデータベースを生成する方法30のフローチャートである。方法は、ナビゲーション装置1のデータベース10を生成するために使用されてよい。
【0068】
31で、タイルのために定義された多様なTINの全ての頂点のセットが決定される。頂点のセットは、タイルに定義された2つまたは6つのTINの全ての頂点のセットであってよい。全ての頂点のセットはMとして示される。
【0069】
32で、頂点の内の1つが選択される。頂点は、無作為に、またはデルタ符号化チェーンの開始点を決定するアルゴリズムを使用して選択されてよい。エントリは、選択された頂点のための第1の配列で生成される。エントリは選択された頂点の頂点座標を含む。
【0070】
追加のエントリが、対話式で第1の配列に追加される。第1の反復では、第1の配列だけが32で選択される頂点エントリを有する。
【0071】
33で、選択された頂点がセットMから削除される。セットMは、第1の配列でまだエントリが生成されていない頂点だけを含むように更新される。
【0072】
34で、第1の配列の最後のエントリが以前生成された頂点から最小の距離を有するMの頂点が決定される。第1の反復では、32で選択された頂点から最小距離を有する頂点が識別される。任意の適切な距離メトリックが使用されてよい。説明のため、Lpメトリックが使用されてよい。
【0073】
35で、34で決定された頂点の頂点座標と、第1の配列の最後のエントリが以前生成された頂点の頂点座標との間の座標デルタが決定される。この座標デルタが、第1の配列の新しい最後のエントリとして第1の配列の中に書き込まれる。それによって、頂点座標のデルタ符号化が実行されてよい。デルタ符号化が実行されてはならない場合、(座標デルタよりむしろ)34で選択された頂点の座標が、第1の配列の新しい最後のエントリとして第1の配列に書き込まれてよい。
【0074】
36で、Mの中に複数の頂点があるかどうか、つまり多様なTINの全ての頂点のために、第1の配列でエントリがすでに生成されているかどうかが決定される。Mの中に複数の頂点が残されている場合、方法は33に戻り、ステップ33から36が繰り返される。それ以外の場合、方法は37に進む。
【0075】
37で、三角形の片が各TINに生成される。三角形の片は、頂点インデックスのリストとして生成されてよく、各頂点インデックスは、座標が第1の配列に登録されている頂点の内の1つを一意に識別する。
【0076】
38で、第1の配列および第2の配列はデータベースに記憶される。
【0077】
方法30は、タイリングの複数のタイルに実行されてよい。方法30は、タイリングの全タイルに実行されてよい。
【0078】
方法30を使用して生成されるデータベースは、車両ナビゲーション装置に配備されてよい。
【0079】
実施形態にかかる方法および方法が詳細に説明されてきたが、他の実施形態で修正が実施されてよい。説明のために、いくつかの実施形態では正方形のタイルのタイリングが説明されたが、他のタイルの形状も使用されてよい。
【0080】
本発明の実施形態は、それに制限されることなく三次元地形を視覚するために使用されてよい。
【特許請求の範囲】
【請求項1】
ナビゲーション装置用データベース(10)であって、前記データベース(10)は、地形の三次元表面を定義するデジタル標高モデルデータを含み、前記データベース(10)がタイリング(8)の複数のタイル(11)の各タイル(11)のために、
−それぞれのタイル(11)のための、複数の不整三角網、TIN(18、19)の頂点(AからH)の三次元座標を含む第1の配列(23)と、
−複数の第2の配列(24、25)であって、各第2の配列(24、25)がそれぞれTIN(18、19)の三角面を定義し、前記それぞれのTIN(18、19)の三角面を定義するために前記第1の配列に頂点(AからH)座標が記憶される前記頂点(AからH)の複数のインデックスを含む、複数の第2の配列(23)と、
を記憶する、データベース。
【請求項2】
前記複数の第2の配列(24、25)の各第2の配列(24、25)が三角形の片である、請求項1に記載のデータベース(10)。
【請求項3】
少なくとも1つの頂点(AからH)のインデックスが、異なる第2の配列(24、25)に含まれる、請求項2に記載のデータベース(10)。
【請求項4】
前記データベース(10)が、前記複数のタイル(11)の各タイル(11)のために、少なくとも2つの第2の配列(24、25)を記憶する、請求項1に記載のデータベース(10)。
【請求項5】
前記データベース(10)が、前記複数のタイル(11)の各タイル(11)のために、少なくとも6つの第2の配列を記憶する、請求項4に記載のデータベース(10)。
【請求項6】
前記第1の配列(23)の頂点(AからH)のためのエントリが、頂点座標のための距離メトリックに従って順序付けられ、前記第1の配列(23)が、デルタ符号化形式で前記三次元座標を含む、請求項1に記載のデータベース(10)。
【請求項7】
請求項1から6のどれか1つの前記データベース(10)と、
光出力装置(4)と、
前記データベース(10)に、および前記光出力装置(4)に結合される処理装置(2)であって、前記データベース(10)から取り出されるデータに基づいて、三次元地形の表示を出力するために前記光出力装置(4)を制御するように構成される前記処理装置(2)と、
を備える、ナビゲーション装置(1)。
【請求項8】
前記処理装置(2)が、複数の不整三角網、TIN(18、19)をレンダリングし、前記斜視図を生成するように構成され、前記処理装置(2)が、前記データベース(10)の前記同じ第1の配列(23)から前記複数のTIN(18、19)の頂点(AからH)の三次元座標を決定するように構成される、請求項7に記載のナビゲーション装置。
【請求項9】
三次元地形の表示を出力する方法であって、前記三次元地形の前記表示が、請求項1から6のどれか1つに記載のデータベース(10)を使用して生成される方法。
【請求項10】
複数の不整三角網、TIN(18、19)がレンダリングされ、前記複数のTIN(18、19)の頂点(AからH)のための頂点座標が、前記データベース(10)の前記同じ第1の配列(23)から取り出される、請求項9に記載の方法。
【請求項11】
ナビゲーション装置(1)用のデータベース(10)を生成する方法であって、タイリング(8)の各タイル(11)のためにそれぞれ実行される、
−前記それぞれのタイル(8)のために定義される複数の不整三角網、TIN(18、19)の頂点(AからH)の三次元頂点座標を決定するステップと、
−前記決定された頂点座標を含む第1の配列(23)を生成するステップと、
−前記複数のTIN(18、19)の各TINのために第2の配列(24、25)を生成するステップであって、各第2の配列(24、25)が、頂点(AからH)座標が、前記それぞれのTIN(18、19)の三角面を定義するために前記第1の配列(23)に含まれる前記頂点(AからH)の複数のインデックスを含む生成するステップと、
を含む、方法。
【請求項12】
前記複数の第2の配列(24、25)の各第2の配列(24、25)が三角形の片として生成される、請求項11に記載の方法。
【請求項13】
前記複数の第2の配列(24、25)が、少なくとも1つの頂点(AからH)のインデックスが異なる第2の配列(24、25)に含まれるように生成される、請求項12に記載の方法。
【請求項14】
前記複数のタイルの各タイル(11)のために、少なくとも2つの第2の配列(24、25)が生成される、請求項11から13のどれか1つに記載の方法。
【請求項15】
頂点(AからH)座標が、距離メトリックに従って前記第1の配列(23)に含まれる頂点(AからH)の順序を決定することと、
前記第1の配列(23)を生成するときに、前記三次元頂点座標をデルタ符号化することと、
をさらに含む、請求項11から13のどれか1つに記載の方法。
【請求項1】
ナビゲーション装置用データベース(10)であって、前記データベース(10)は、地形の三次元表面を定義するデジタル標高モデルデータを含み、前記データベース(10)がタイリング(8)の複数のタイル(11)の各タイル(11)のために、
−それぞれのタイル(11)のための、複数の不整三角網、TIN(18、19)の頂点(AからH)の三次元座標を含む第1の配列(23)と、
−複数の第2の配列(24、25)であって、各第2の配列(24、25)がそれぞれTIN(18、19)の三角面を定義し、前記それぞれのTIN(18、19)の三角面を定義するために前記第1の配列に頂点(AからH)座標が記憶される前記頂点(AからH)の複数のインデックスを含む、複数の第2の配列(23)と、
を記憶する、データベース。
【請求項2】
前記複数の第2の配列(24、25)の各第2の配列(24、25)が三角形の片である、請求項1に記載のデータベース(10)。
【請求項3】
少なくとも1つの頂点(AからH)のインデックスが、異なる第2の配列(24、25)に含まれる、請求項2に記載のデータベース(10)。
【請求項4】
前記データベース(10)が、前記複数のタイル(11)の各タイル(11)のために、少なくとも2つの第2の配列(24、25)を記憶する、請求項1に記載のデータベース(10)。
【請求項5】
前記データベース(10)が、前記複数のタイル(11)の各タイル(11)のために、少なくとも6つの第2の配列を記憶する、請求項4に記載のデータベース(10)。
【請求項6】
前記第1の配列(23)の頂点(AからH)のためのエントリが、頂点座標のための距離メトリックに従って順序付けられ、前記第1の配列(23)が、デルタ符号化形式で前記三次元座標を含む、請求項1に記載のデータベース(10)。
【請求項7】
請求項1から6のどれか1つの前記データベース(10)と、
光出力装置(4)と、
前記データベース(10)に、および前記光出力装置(4)に結合される処理装置(2)であって、前記データベース(10)から取り出されるデータに基づいて、三次元地形の表示を出力するために前記光出力装置(4)を制御するように構成される前記処理装置(2)と、
を備える、ナビゲーション装置(1)。
【請求項8】
前記処理装置(2)が、複数の不整三角網、TIN(18、19)をレンダリングし、前記斜視図を生成するように構成され、前記処理装置(2)が、前記データベース(10)の前記同じ第1の配列(23)から前記複数のTIN(18、19)の頂点(AからH)の三次元座標を決定するように構成される、請求項7に記載のナビゲーション装置。
【請求項9】
三次元地形の表示を出力する方法であって、前記三次元地形の前記表示が、請求項1から6のどれか1つに記載のデータベース(10)を使用して生成される方法。
【請求項10】
複数の不整三角網、TIN(18、19)がレンダリングされ、前記複数のTIN(18、19)の頂点(AからH)のための頂点座標が、前記データベース(10)の前記同じ第1の配列(23)から取り出される、請求項9に記載の方法。
【請求項11】
ナビゲーション装置(1)用のデータベース(10)を生成する方法であって、タイリング(8)の各タイル(11)のためにそれぞれ実行される、
−前記それぞれのタイル(8)のために定義される複数の不整三角網、TIN(18、19)の頂点(AからH)の三次元頂点座標を決定するステップと、
−前記決定された頂点座標を含む第1の配列(23)を生成するステップと、
−前記複数のTIN(18、19)の各TINのために第2の配列(24、25)を生成するステップであって、各第2の配列(24、25)が、頂点(AからH)座標が、前記それぞれのTIN(18、19)の三角面を定義するために前記第1の配列(23)に含まれる前記頂点(AからH)の複数のインデックスを含む生成するステップと、
を含む、方法。
【請求項12】
前記複数の第2の配列(24、25)の各第2の配列(24、25)が三角形の片として生成される、請求項11に記載の方法。
【請求項13】
前記複数の第2の配列(24、25)が、少なくとも1つの頂点(AからH)のインデックスが異なる第2の配列(24、25)に含まれるように生成される、請求項12に記載の方法。
【請求項14】
前記複数のタイルの各タイル(11)のために、少なくとも2つの第2の配列(24、25)が生成される、請求項11から13のどれか1つに記載の方法。
【請求項15】
頂点(AからH)座標が、距離メトリックに従って前記第1の配列(23)に含まれる頂点(AからH)の順序を決定することと、
前記第1の配列(23)を生成するときに、前記三次元頂点座標をデルタ符号化することと、
をさらに含む、請求項11から13のどれか1つに記載の方法。
【図1】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【図2】
【図3】
【図4】
【図5】
【図6】
【図7】
【図8】
【図9】
【図10】
【図11】
【公開番号】特開2012−234533(P2012−234533A)
【公開日】平成24年11月29日(2012.11.29)
【国際特許分類】
【出願番号】特願2012−97078(P2012−97078)
【出願日】平成24年4月20日(2012.4.20)
【出願人】(504147933)ハーマン ベッカー オートモーティブ システムズ ゲーエムベーハー (165)
【Fターム(参考)】
【公開日】平成24年11月29日(2012.11.29)
【国際特許分類】
【出願日】平成24年4月20日(2012.4.20)
【出願人】(504147933)ハーマン ベッカー オートモーティブ システムズ ゲーエムベーハー (165)
【Fターム(参考)】
[ Back to top ]