(57)【特許請求の範囲】
【請求項１】
ハードウエアテッセレーションを用いた道路区間のグラフィック表示方法であって、
前記道路区間の少なくとも一つの２次元又は３次元の道路輪郭を表す地図製作データが各々の道路区間に割り当てられ、前記方法は、
一つの道路区間の前記道路輪郭を表すためのパラメータ化を定める工程と、
パラメータ化された道路区間を相互に独立した複数の曲線区間に区分的に分割する工程と、
各々の曲線区間について、前記各々の曲線区間が前記道路輪郭の方向に何個の細分区間に細分されるかを指定する、少なくとも一つのテッセレーション要素を定める工程と、
前記少なくとも一つのテッセレーション要素に基づく各々の曲線区間についてのテッセレーションパターンを生成する工程と、
前記生成されたテッセレーションパターンと前記パラメータ化された道路輪郭に基づいて、スクリーン（１０３０）に表示されることができる複数の基本要素を生成する工程を有することを特徴とする方法。
【請求項２】
一つの道路区間が、前記複数の曲線区間について生成された前記複数の基本要素から構成され、グラフィック表示されることを特徴とする請求項１に記載の方法。
【請求項３】
前記各々の曲線区間の曲線輪郭が、前記生成された複数の基本要素によって直線的に補間されることを特徴とする請求項１又は請求項２に記載の方法。
【請求項４】
前記道路輪郭に割り当てられた一つのテッセレーション要素が、少なくとも前記曲線区間の一つの曲線輪郭に基づいて計算されることを特徴とする請求項１から請求項３のいずれか一項に記載の方法。
【請求項５】
前記道路輪郭に割り当てられた前記テッセレーション要素を計算するために、スクリーン（１０３０）に表示される、前記曲線区間の曲線輪郭を用いることを特徴とする請求項４に記載の方法。
【請求項６】
一つのパラメータ区間［ｔｉ，ｔｉ＋１］内でパラメータ化された一つの曲線区間
0006009039.tif 000097
についての前記道路輪郭へ割り当てられた一つのテッセレーション要素は、式ｕｔｅｓｓ＝２×ｌｏｇ（δ）／ｌｏｇ（ε０）に従って計算され、ｕｔｅｓｓはテッセレーション要素を示し、δは所定の精度値を指定し、ε０はパラメータ化された
0006009039.tif 000098
の始点
0006009039.tif 000099
、終点
0006009039.tif 000100
、及び点
0006009039.tif 000101
を用いて、始点
0006009039.tif 000102
と終点
0006009039.tif 000103
を結ぶ直線から点
0006009039.tif 000104
までの距離を計算することによって、求められることを特徴とする請求項４又は請求項５に記載の方法。
【請求項７】
前記道路輪郭に割り当てられたテッセレーション要素は、さらに、表示される前記複数の曲線区間に対する視野に基づいて計算されることを特徴とする請求項１から請求項６のいずれか一項に記載の方法。
【請求項８】
前記方法は、さらに、前記道路輪郭の方向に垂直な道路幅に割り当てられた、さらに一つのテッセレーション要素を定める工程を有することを特徴とする請求項１から請求項７のいずれか一項に記載の方法。
【請求項９】
前記道路幅に割り当てられたテッセレーション要素を一定値とすることを特徴とする請求項８に記載の方法。
【請求項１０】
前記一つのテッセレーションパターンを生成する工程は、前記定められた少なくとも一つのテッセレーション要素に基づいて、前記道路輪郭に沿った曲線区間の細分の程度を指定する複数の走査点を生成する工程を有することを特徴とする請求項１から請求項９のいずれか一項に記載の方法。
【請求項１１】
前記表示されることができる複数の基本要素を生成する工程は、
前記パラメータ化された道路輪郭を前記スクリーンの空間の複数の座標にマッピングする座標変換を実施する工程と、
前記道路輪郭に沿った複数の走査点において、前記変換後のパラメータ化された道路輪郭を評価することによって、複数の頂点を計算する工程と、
前記生成された複数の頂点に基づいて、グラフィック表示されることができる、複数の基本要素を生成する工程を有することを特徴とする請求項１０に記載の方法。
【請求項１２】
前記複数の頂点を計算する工程は、
さらに、前記道路輪郭に沿った複数の走査点において、前記変換後のパラメータ化された道路輪郭を評価することによって、及び、スクリーン面内にあり、前記道路輪郭に垂直である法線ベクトルに沿った道路幅に対して定められた複数の頂点を評価することによって、前記複数の頂点を計算する工程を有することを特徴とする請求項１１に記載の方法。
【請求項１３】
前記パラメータ化は、前記道路輪郭を表す、予め保存された複数の形状点に基づいて計算されることを特徴とする請求項１から請求項１２のいずれか一項に記載の方法。
【請求項１４】
前記パラメータ化は、前記パラメータ化された曲線が前記複数の形状点を補間するように、前記複数の形状点に基づいて行われることを特徴とする請求項１３に記載の方法。
【請求項１５】
前記パラメータ化は、前記複数の形状点に基づいて動的に計算されることを特徴とする請求項１３又は請求項１４に記載の方法。
【請求項１６】
前記各々の道路区間の道路輪郭が、非一様に分布させられた複数の節点と複数のｄｅ  Ｂｏｏｒ点を通して記述される２次のＢ−スプラインよってパラメラータ化されることを特徴とする請求項１から請求項１５のいずれか一項に記載の方法。
【請求項１７】
一つの道路区間の各々の非一様なＢ−スプラインは、相互に独立した複数の２次の多項式に分割され、各々の多項式は一つの節点間隔Ｉｉ＝［ｔｉ；ｔｉ＋１］に対して定義され、一つの節点ベクトル
0006009039.tif 000105
と三つのｄｅ  Ｂｏｏｒ点
0006009039.tif 000106
によって記述されることを特徴とする請求項１６に記載の方法。
【請求項１８】
一つの道路区間の各々の非一様なＢ−スプラインは、索引配列と、前記複数の節点ベクトルと複数のｄｅ  Ｂｏｏｒ点を含む頂点属性の列を用いて記述されることを特徴とする請求項１７に記載の方法。
【請求項１９】
前記頂点属性の列は、ｎを節点の数とし、以下の配列
0006009039.tif 000107
に従って、複数の節点ベクトルと複数のｄｅ  Ｂｏｏｒ点の帰納的な繰り返しなしに表示される前記道路区間の全ての２次の多項式についての複数の節点ベクトルと複数のｄｅ  Ｂｏｏｒ点を含むことを特徴とする請求項１８に記載の方法。
【請求項２０】
前記索引配列は、ｎを節点の数とし、以下の配列
Ｉ＝［（０，１，２，３）；（１，２，４，５）；（２，４，６，７）；（４，６，８，９）；・・・，（２ｎ−６，２ｎ−４，２ｎ−２，２ｎ−１）］
に応じて、前記頂点属性列の複数のエントリの複数の索引を含むことを特徴とする請求項１８に記載の方法。
【請求項２１】
請求項１から請求項２０のいずれか一項に記載の方法を実行するためのプログラムコードを有し、コンピュータ装置で実行されるコンピュータプログラム製品。
【請求項２２】
コンピュータで読み取り可能な記録媒体に格納された請求項２１に記載のコンピュータプログラム製品。
【請求項２３】
ハードウエアテッセレーションを用いた道路区間のグラフィック表示用のグラフィックモジュールであって、
各々の道路区間の少なくとも一つの２次元又は３次元の道路輪郭を表す地図製作データが各々の道路区間に割り当てられ、前記グラフィックモジュールは、
一つの道路区間の前記道路輪郭を表すためのパラメータ化を定めるように構成されるユニット（１０１１）と、
パラメータ化された道路区間を相互に独立した複数の曲線区間に分割するように構成されるユニット（１０１２）と、
各々の曲線区間について、前記各々の曲線区間が前記道路輪郭の方向に何個の細分区間に細分されるかを指定する、少なくとも一つのテッセレーション要素を定めるように構成されるユニット（１０２２）と、
前記少なくとも一つのテッセレーション要素に基づく各々の曲線区間についての一つのテッセレーションパターンを生成するように構成されるテッセレーションユニット（１０２３）と、
前記生成されたテッセレーションパターンと前記パラメータ化された道路輪郭に基づいて、スクリーン（１０３０）に表示されることができる複数の基本要素を生成するように構成されるユニット（１０２４）を有することを特徴とするグラフィックモジュール。
【請求項２４】
前記グラフィックモジュールは、さらに、少なくとも一つの、索引配列及び頂点属性の列を保存するように構成されるメモリユニット（１０２０ａ）を有し、前記頂点属性の列は一つのパラメータ化された道路区間についてのパラメータデータを含むことを特徴とする請求項２３に記載のグラフィックモジュール。
【請求項２５】
請求項２３又は請求項２４に記載のグラフィックモジュールと、
前記生成された複数の基本要素を表示するように構成されるスクリーン（１０３０）を有することを特徴とするナビゲーション装置（１０００）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ハードウエアテッセレーションを用いた地図製作データの表示に関する。具体的には、道路区間の少なくとも一つの２次元又は３次元の道路輪郭を表す地図製作データに基づいて、道路区間をグラフィック表示する課題解決法に関する。
【背景技術】
【０００２】
一般的に、デジタル地図データは、道路ネットワークを再現するために、道路端部データと道路交点データを含んでいる。道路端部は、道路ネットワーク内で、二つの連続する交差点又は合流点の間の道路区間を表している。一つの道路交点は、道路ネットワーク内の一つの交差点又は合流点を表す。
【０００３】
道路ネットワークのグラフィック表示は、実質的に、道路ネットワーク内の個々の道路の道路輪郭の具体的な視覚による再現により構成される。同様のことが、計算された経路の道路輪郭を（全体的に、又は、区分的に）表示する経路計算機能の中で計算された経路の表示に適用される。道路輪郭は、地図製作座標系内の複数の道路の曲線輪郭、複数の道路区間、又は、複数の経路を表す。
【０００４】
道路輪郭を表すために、いわゆる形状点がデジタル地図データの中に保存される。この場合、各々の道路区間（又は各々の道路端部）は、道路区間の曲線輪郭を表す一連の形状点に関連付けられる。各々の形状点は、地図製作座標系に関して、一つの位置（例えば、地理上の経度及び地理上の緯度）を表している。
【０００５】
現在の表示方法においては、複数の道路区間、又は、複数の経路のグラフィック表示のために、複数の道路区間、又は、複数の経路に割り当てられた複数の形状点が用いられる。道路輪郭は、複数の形状点の位置に対応して表示され、その道路輪郭では各々隣接する形状点の間が直線的に補間される。
【０００６】
隣接する形状点間の直線補間による複数の道路区間のそのようなグラフィック表示の一例が、図１Ａ及び図１Ｂに示される。図１Ａは、交点６２で各々終端する、道路区間６０、６３、６４から構成される道路ネットワークの詳細を示している。それら複数の道路区間は強い湾曲を示すので、形状点６０ａ、６０ｂ、６３ａ、６３ｂ、６４ａ及び交点６２の間で直線的に補間された複数の曲線輪郭は、角度があり、滑らかでない変わり目を生ずる。図１Ａに示された右手側の表示からすぐに明らかになるように、実際の曲線輪郭を大きくゆがんで表示する複数の目立った変わり目が、点６０ｂ、６２、６３ａ、６４ａで生じる。
【０００７】
曲線輪郭をより平滑にさせる一つの実現可能な方法は、図１Ｂの左手側の図に模式的に示されるように、隣接する形状点の間隔をより縮小するために、より多くの形状点を提供することを含む。この関連において、（小さな円で表される）追加の形状点が、既存の形状点６０ａ、６０ｂ、６３ａ、６３ｂ、６４ａ、６４ｂの間に挿入された。曲線輪郭は、図１Ｂの右手側の表示からすぐに明らかになるように、実際に、より滑らかに、かつ、その結果、より現実的に表されることができる。
【０００８】
しかしながら、そのような方式の解決法の問題点は、地図データの中に提供される情報がさらに増加することであり、その結果、より大量のメモリ空間が必要とされる。さらに、グラフィック表示している間に各々の形状点は分離して処理されなければならないので、形状点の数の増加につれて、表示される一画面当たりの処理時間が増加する。これにより、グラフィック表示の速度の損失が発生する。しかしながら、滑らかな表示のためには、地図データはたいてい１秒当たり数回の画面更新が行われるものでなければならないので、低速のグラフィック表示は望ましくない。従って、性能上の理由で、より少ない数の形状点が選択され、その結果、地図データのグラフィック表示における低い品質が受け入れられる。
【発明の概要】
【発明が解決しようとする課題】
【０００９】
本発明の目的は、従って、特に、道路と経路の表示を更に改善する、改善されたグラフィック表示方法を提供することである。
【課題を解決するための手段】
【００１０】
本発明の第一の態様によれば、コンピュータで実行される、ハードウエアテッセレーションを用いた道路区間のグラフィック表示方法が提供され、道路区間の少なくとも一つの２次元又は３次元の道路輪郭を表す地図製作データが各々の道路区間に割り当てられる。その方法は、この関連において、一つの道路区間の道路輪郭を表すためのパラメータ化を定める工程と、パラメータ化された道路区間を相互に独立した複数の曲線区間に区分的に分割する工程と、各々の曲線区間について、各々の曲線区間が道路輪郭の方向に何個の細分区間に細分されるかを指定する、少なくとも一つのテッセレーション要素を定める工程と、少なくとも一つのテッセレーション要素に基づく各々の曲線区間についてのテッセレーションパターンを生成する工程と、生成されたテッセレーションパターンとパラメータ化された道路輪郭に基づいて、スクリーンに表示されることができる複数の基本要素を生成する工程を有する。
【００１１】
一つの道路区間が、道路ネットワーク内の二つの連続する交差点又は合流点の間の道路の一区分又は経路の一区分を表してもよい。その結果、道路ネットワーク又は経路が、道路ネットワーク又は経路に属する複数の道路区間のグラフィック表示によって、図画的に表されることができる。
【００１２】
道路輪郭は、所定の地図製作の座標系に関連して、道路区間又は道路の曲線輪郭（例えば、地理上の形状）を表してもよい。換言すれば、道路輪郭は、道路区間の曲がり具合（ｃｕｒｖｉｎｅｓｓ）を再現してもよい。一つの変形態様においては、道路区間の曲がり具合は、その道路区間の長さに対する道路区間の角度の変化から構成される比率を表す。地図データにおいて地形が考慮されるときは、道路輪郭は３次元であってもよい。各々の道路区間の曲線輪郭は、地図製作データの中に保存された複数の形状点によって表されることができる。具体的には、各々の道路区間は、一連の形状点から構成されるものとして表されることができる。各々の形状点は、地図製作座標系内の、その地理上の位置（経度、緯度、及び、適切なもの、標高）によって表される。
【００１３】
複数の道路区間又は道路のグラフィック表示は、ベクタ形式に基づいて行われてよい。この関連において、各々の道路区間は、複数の基本要素を用いてグラフィック表示されることができる。換言すれば、各々の道路区間は、複数の基本要素から構成され、又は組み立てられる。複数の「基本要素」により、複数の初歩的な図画的要素が点、線、三角形、矩形、及び／又は、多角形から構成されることが理解される。表示されるどのような領域（面）も三角形で構成されるものとして表されることができるので、グラフィック表示のために、特に、三角形が基本要素として用いられることができる。さらに、グラフィックプロセッサ（グラフィック処理ユニット、又は、ＧＰＵ）は、しばしば、三角形の基本要素の表示のために最適化されている。三角形の代わりに、例えば矩形のような他の基本要素も、道路区間のグラフィック表示のために用いられてもよいということが理解されるだろう。
【００１４】
各々の道路区間が、複数の曲線区間について生成された複数の基本要素から構成され、グラフィック表示されることができる。道路区間のグラフィック表示のための複数の基本要素の生成は、この関連において、生成されたテッセレーションパターンに依存する。テッセレーションパターンは、一つのパラメータ化された道路区間（曲線区間）が何個の基本要素に分割されるべきかを指定してもよい。そのパターンはまた、どの基本要素（例えば、三角形）が分割に用いられるべきかを指定してもよい。その結果、テッセレーションパターンは、分割の程度（多数の基本要素に伴う目の細かい分割、又は、少ない基本要素に伴う目の粗い分割）と分割の形式（矩形、三角形等）を定めることができる。
【００１５】
各々の曲線区間の曲線輪郭が、その結果、生成された複数の基本要素によって、直線的に補間されることができる。補間の品質は、この関連において、曲線輪郭の方向に生成される基本要素の数に依存するかもしれない。曲線区間の曲線輪郭の方向の基本要素の数は、この場合、道路輪郭に割り当てられたテッセレーション要素によって定められることができる。
【００１６】
道路輪郭に割り当てられた一つのテッセレーション要素が、各々の曲線区間に対して動的に計算されることができる。この関連において、その一つのテッセレーション要素は、少なくとも曲線区間の一つの曲線輪郭に基づいて（個々に）計算されることができる。そのテッセレーション要素は、より大きなテッセレーション要素が、軽度の曲がり具合の複数の曲線区間よりも、重度の曲がり具合の複数の曲線区間に対して定められるように計算されることができる。結果として、重度の曲がり具合の複数の曲線区間は、道路輪郭の方向に数多くの基本要素によって表され、一方、軽度の曲がり具合の複数の曲線区間は、数少ない基本要素を用いてグラフィック表示されることを確実にすることができる。大きなテッセレーション要素の使用（及び、それによる目の細かいテッセレーションの使用）を通して、重度の曲がり具合の複数の曲線区間について、複数の基本要素によるグラフィック表示が曲線区間の実際の曲線輪郭を最適に補間し、曲線の滑らかなグラフィック表示が保証されることが確実にされることができる。他方、軽度の曲がり具合の複数の曲線区間又はほとんど直線の輪郭は、曲線の滑らかなグラフィック表示を得るために、数少ない基本要素のみを必要とする。その結果、曲線輪郭に割り当てられたテッセレーション要素の曲線区間に依存した生成によって、各々の曲線区間がどれくらいの細部の正確さでグラフィック表示されることができるかを定めることができる。
【００１７】
道路輪郭に割り当てられたテッセレーション要素を計算するために、スクリーン（又はいくつかの他の光学的な出力媒体）に表示される曲線区間の曲線輪郭を用いてもよい。表示された曲線輪郭は、見る角度に依存して、道路区間の実際の道路輪郭と異なっていてもよい。例えば、横方向から見るモードにおいて重度の実際の曲がり具合の曲線区間は、スクリーン上ではほぼ直線的に表されることができる。そのような形式の区間については、グラフィック表示の細部の高い精度は必要とされず、道路輪郭に沿った小さなテッセレーション要素が定められることができる。
【００１８】
一つの実施形態によれば、道路輪郭へ割り当てられたテッセレーション要素が、一つのパラメータ区間［ｔｉ，ｔｉ＋１］内でパラメータ化された一つの曲線区間
0006009039.tif 000002
について、式ｕｔｅｓｓ＝２×ｌｏｇ（δ）／ｌｏｇ（ε０）に従って計算され、ここで、ｕｔｅｓｓはテッセレーション要素を示し、δは所定の精度値を指定し、ε０はパラメータ化された
0006009039.tif 000003
の始点
0006009039.tif 000004
、終点
0006009039.tif 000005
、及び点
0006009039.tif 000006
を用いて、始点
0006009039.tif 000007
と終点
0006009039.tif 000008
を結ぶ直線から点
0006009039.tif 000009
までの距離を計算することによって、求められる。この関連において、
0006009039.tif 000010
はスクリーン座標に表示されるパラメータ曲線の複数の値であってもよい。さらに、所定の精度値δは複数のピクセルに指定されてもよい。その値は、１ピクセルの端数に設定されてもよい（例えば、ピクセルの半分）。所定の精度値は他の値（例えば、１ピクセル）をとってもよいことが理解される。
【００１９】
曲線輪郭に依存した計算の代わりに、又はそれに加えて、道路輪郭に割り当てられたテッセレーション要素はまた、表示される複数の曲線輪郭に対する視野に基づいて計算されてもよい。例えば、見る人から見てより遠方に位置する曲線区間は、見る人にすぐに近接する曲線区間よりも粗く表示（テッセレーション）されることができる（及び、それにより、細部が低い精度でグラフィック表示されることができる）。
【００２０】
道路と経路は、１次元の直線としてだけではなく、むしろある（可変の）道路幅を持つ２次元のグラフィック対象物としてスクリーンに表示されるので、道路輪郭に垂直な方向（すなわち道路幅に沿って）についてのさらなるテッセレーション要素を定めることができる。道路幅に割り当てられたテッセレーション要素を、この関連において、一定値としてもよい。例えば、テッセレーション要素は、１の値をとってもよい。この場合、道路幅の方向にテッセレーションは行われない（すなわち、さらに、基本要素に分割しない）。もちろん、選択的な変形態様により、テッセレーション要素は、道路幅の方向に他の値をとってもよい。両方の場合において、道路幅の方向のテッセレーション要素は、複数の曲線区間の曲線輪郭には依存しない。
【００２１】
テッセレーションパターンを生成する工程は、定められた少なくとも一つのテッセレーション要素に基づいて、道路輪郭に沿った曲線区間の細分の程度を指定する複数の走査点を生成する工程を含んでもよい。前記生成する工程は、さらに、曲線区間の幅の細分の程度を指定する、道路幅に割り当てられたテッセレーション要素に基づいた複数の走査点を生成する工程を含んでもよい。前記生成する工程は、さらに、複数の走査点に基づいて２次元パターンを生成する工程を含んでよい。テッセレーションパターンは、三角形パターンの頂点を形成する複数の走査点を備える、複数の三角形から構成されてもよい。
【００２２】
表示されることができる複数の基本要素を生成する工程は、パラメータ化された道路輪郭をスクリーンの空間の複数の座標にマッピングする座標変換を実施する工程と、道路輪郭に沿った複数の走査点において、変換後のパラメータ化された道路輪郭を評価することによって、複数の頂点を計算する工程と、生成された複数の頂点に基づいて、グラフィック表示されることができる、複数の基本要素を生成する工程を含んでもよい。
【００２３】
複数の頂点を計算する工程は、さらに、道路輪郭に沿った複数の走査点において、変換後のパラメータ化された道路輪郭を評価することによって、及び、スクリーン面内にあり、道路輪郭に垂直である法線ベクトルに沿った道路幅に対して定められた複数の頂点を評価することによって、複数の頂点を計算する工程を有してもよい。
【００２４】
道路区間についての道路輪郭を表すためのパラメータ化を定める工程は、道路輪郭を表す、予め保存された複数の形状点に基づいて、道路区間についてのパラメータ化を計算する工程を含んでよい。この場合、パラメータ化は、パラメータ化された曲線が複数の形状点を補間するように計算されてもよい。パラメータ化は、動的に（すなわち、グラフィック表示の間に）計算されてもよい。しかし、パラメータ化は地図データの編集の間に生成され、地図データ内に保存されることも考えられる。
【００２５】
これに代わり、複数のパラメータ化された道路区間はまた、地図のサプライヤによって提供されてもよい。この場合、パラメータ化を定める工程は、複数のパラメータ化された道路区間を読み出し、さらに処理を行うために、ワーキングメモリの中に、又は、グラフィックメモリの中にアップロードする工程を含む。
【００２６】
一つの変形態様によれば、パラメータ化は、非一様に分布させられた複数の節点と検査（照合）点、いわゆるｄｅ  Ｂｏｏｒ点を通して記述される２次のＢ−スプライン（以下では、「２次のＮＵＢＳ」と呼ばれる）を用いて実行されることができる。ＮＵＢＳによる道路区間の道路輪郭のパラメータ化は、上述したように、道路区間に対して提供される複数の形状点に基づいて実行される。これの代わりに、曲線のパラメータ化はまた、複数のベジエ曲線、３次元のＮＵＢＳ、又は、その他の方法により実行されることができる。
【００２７】
パラメータ化された道路区間を相互に独立した複数の道路区間に区分的に分割する工程は、道路区間の道路輪郭を表すＮＵＢＳを相互に独立した複数の２次元の多項式に分割する工程を含んでもよい。この関連において、各々の多項式は、道路区間を表すＮＵＢＳが構成される最小の単位を形成してもよい。例えば、各々の多項式は、連続的に隣接する節点による一つの節点間隔Ｉｉ＝［ｔｉ，ｔｉ＋１］に対して定義される。その多項式は、二つの連続する交点の間の局所的な曲線輪郭を表してもよい。この関連において、間隔Ｉｉにおける各々の多項式は、
四つの節点を含む一つの節点ベクトル
0006009039.tif 000011
と、三つのｄｅ  Ｂｏｏｒ点
0006009039.tif 000012
だけを用いて、完全にかつ独自に記述されてもよい。ＮＵＢＳを区分的に複数の２次の多項式に分割する利点は、各々の節点間隔Ｉｉについて、Ｂ−スプラインの局所的な表示が可能で、各々の分割部分が隣接する分割部分とは独立してテッセレーションされることができることである。テッセレーション、及び、特にテッセレーションの程度は、この関連において、曲がり具合に応じて各々の区間に対して異なっていてもよい。この関連において、多項式の曲がり具合への適合が上述のように行われてもよい。特に、Ｂ−スプラインの区分的な分割は、テッセレーションに対するハードウエアの制約による上限の理由により、長い道路区間又は経路区間のテッセレーションが不適切に細かくなるのを防ぐ。
【００２８】
他方、各々の道路区間は、テッセレーションのために定められた複数の２次の多項式によって連続的に構成されることができる。一つの道路区間の各々の２次の多項式に割り当てられることができるｄｅ  Ｂｏｏｒ点
0006009039.tif 000013
と節点ベクトル
0006009039.tif 000014
が、この目的のために、ワーキングメモリ、グラフィックメモリ、又はその他のものの内部に、さらなるグラフィック処理（すなわち、テッセレーションとグラフィック表示されることができる複数の基本要素の生成）のために一時的に保存されてもよい。その保存は、頂点属性の列と索引配列によって行われることができる。頂点属性の列は、表示対象の道路区間の全ての２次の多項式についての複数の節点ベクトルと複数のｄｅ  Ｂｏｏｒ点を構成してもよい。この関連において、頂点属性の列に、配列
0006009039.tif 000015
に従って、複数の節点ベクトルと複数のｄｅ  Ｂｏｏｒ点を保存してもよい。ここで、ｎは節点の数である。さらに、索引属性の列は、配列Ｉ＝［（０，１，２，３）；（１，２，４，５）；（２，４，６，７）；（４，６，８，９）；・・・，（２ｎ−６，２ｎ−４，２ｎ−２，２ｎ−１）］に従って、頂点属性列のエントリ（項目）を参照する複数の索引を含んでいてもよい。ここで、ｎは節点の数である。隣接する複数の多項式を記述するために部分的に繰り返し用いられる節点ベクトルとｄｅ  Ｂｏｏｒ点が、一度保存されなければならないだけであり、その結果、メモリ空間が維持されるので、現在の保存法は有利である。
【００２９】
第二の態様によれば、上述の方法を実行するためのプログラムコードを有し、コンピュータ装置で実行されるコンピュータプログラム製品が提供される。この関連において、そのコンピュータプログラム製品は、コンピュータで読み取り可能な記録媒体に格納されてもよい。
【００３０】
第三の態様によれば、ハードウエアテッセレーションを用いた道路区間のグラフィック表示用のグラフィックモジュールが提供され、
各々の道路区間の少なくとも一つの２次元又は３次元の道路輪郭を表す地図製作データが各々の道路区間に割り当てられ、そのグラフィックモジュールは、
一つの道路区間の道路輪郭を表すためのパラメータ化を定めるように構成されるユニットと、
パラメータ化された道路区間を相互に独立した複数の曲線区間に分割するように構成されるユニットと、
各々の曲線区間について、各々の曲線区間が道路輪郭の方向に何個の細分区間に細分されるかを指定する、少なくとも一つのテッセレーション要素を定めるように構成されるユニットと、
少なくとも一つのテッセレーション要素に基づく各々の曲線区間についての一つのテッセレーションパターンを生成するように構成されるテッセレーションユニットと、
生成されたテッセレーションパターンとパラメータ化された道路輪郭に基づいて、スクリーンに表示されることができる複数の基本要素を生成するように構成されるユニットを有する。
【００３１】
グラフィックモジュールは、さらに、少なくとも一つの、索引配列及び頂点属性の列を保存するように構成されるメモリユニットを有し、頂点属性の列は一つのパラメータ化された道路区間についての複数の頂点属性を含む。
【００３２】
第四の態様によれば、上述のグラフィックモジュールと、生成された複数の基本要素を表示するように構成されるスクリーンを有するナビゲーション装置が提供される。
【図面の簡単な説明】
【００３３】
本発明のさらなる態様、利点、及び詳細が図面を参照して、以下の実施態様の記述から明らかになる。
【００３４】
【図１Ａ】道路区間及び経路区間のグラフィック表示を示す概略図である。
【図１Ｂ】道路区間及び経路区間の他のグラフィック表示を示す概略図である。
【図２】実施態様により地図製作データをグラフィック表示する方法を実行する装置を示すブロック図である。
【図３】グラフィックパイプライン内でハードウエアテッセレーション機能を実行することを示す他のブロック図である。
【図４】さらに他の実施態様により、ハードウエアテッセレーション機能を用いて道路区間をグラフィク表示する方法を示すフロー図である。
【図５】さらに他の実施態様により道路区間の分割を示す概略図である。
【図６】道路区間のグラフィック表示のためのパラメータ化の方法の実施態様を示す図である。
【図７】さらに他の実施態様によりテッセレーション要素を計算するモデルを示す概略図である。
【発明を実施するための形態】
【００３５】
本発明は、概要ブロック図及びフロー図を参照して明らかにされるであろう。これらの図の基礎となる技術的な教示は、ハードウエアとソフトウエアの両方で、又はハードウエアとソフトウエアの組み合わせにおいて実行されることができる。そのような実行にはまた、デジタルシグナルプロセッサ（ＤＳＰ）、特定用途向けＩＣ（ＡＳＩＣ）、及び他のスイッチ又はコンピュータ部品を含む。
【００３６】
地図データ、特に、道路区間のグラフィック表示に関する本発明は、例として、Ｋｈｒｏｎｏｓ  Ｇｒｏｕｐによって考案されたＯｐｅｎＧＬ標準の範囲内でより詳細に記述される。ＯｐｅｎＧＬ（Ｏｐｅｎ  Ｇｒａｐｈｉｃｓ  Ｌｉｂｒａｒｙ）は、グラフィックモジュール（例えば、グラフィックカード又はグラフィックチップ）を用いて、複雑な２次元及び３次元の対象物をグラフィック表示するために提供される、プラットホームから独立し、プログラミング言語から独立したグラフィックプログラミングインターフェース（アプリケーションプログラミングインターフェース、すなわち、略してＡＰＩ）である。すなわち、これはアプリケーションプログラムとグラフィックモジュールの間に抽象化レイヤーとして存在し、プリケーションプログラムのグラフィックモジュールへのリンクをサポートする、ソフトウエアグラフィックインターフェースに関するものである。
【００３７】
従って、本発明を明らかにするために、以下では部分的にＯｐｅｎＧＬの術語に頼る。本発明は、使用されるグラフィックインターフェースの詳細に依存しないことが理解されるであろう。例えば、ＤｉｒｅｃｔＸ（より正確には、ＤｉｒｅｃｔＤｒａｗ、又は、Ｄｉｒｅｃｔ３Ｄ）又はＱｕａｒｔｚがソフトウエアグラフィックインターフェースとして用いられることも考えられる。
【００３８】
図２は、ブロック図の形式で、地図データ、特に、道路区間のグラフィック表示のためにここで記述される方法を実行する装置１０００の実施態様を示している。装置１０００は、ナビゲーション装置（例えば、携帯用ナビゲーション装置（ＰＮＤ）、又は自動車内に固定的に搭載されたナビゲーション装置）、ルートプランナー、スマートフォン、携帯情報端末（ＰＤＡ）、パーソナルコンピュータ（ＰＣ）、ノートブック、又は、携帯可能な、又は機械（例えば、自動車）の中で実行されることができる他の電子機器の一部分であってよい。
【００３９】
装置１０００は、中央データ処理部（中央処理ユニット、ＣＰＵ）の形式の、及び／又はソフトウエアモジュール（ＳＷモジュール）の形式のコア機能部１０１０、パラメータ化を行うユニット１０１１、パラメータ化された道路区間を分割するユニット１０１２、グラフィックプロセッサユニット１０２０（今後は、「ＧＰＵ」と呼ぶ）、グラフィックメモリ１０２０ａ、スクリーン１０３０、ワーキングメモリ１０４０、及び、データメモリ１０５０を含む。装置１０００は、センサーユニット１０６０、入力ユニット１０７０、及び、コミュニケーションインターフェース１０８０も選択的に含んでよい。装置１０００のこれら選択的な構成部分は、図２において破線で示されている。
【００４０】
ユニット１０１１及びユニット１０１２、ＧＰＵ１０２０、グラフィックメモリ１０２０ａ、ワーキングメモリ１０４０、データメモリ１０５０、センサーユニット１０６０、入力ユニット１０７０、コミュニケーションインターフェース１０８０、及び、コア機能部１０１０は、処理されるデータと処理済みのデータを相互に交換するために、通信可能に相互接続されている。
【００４１】
コミュニケーションインターフェース１０８０は、コミュニケーションネットワークの外部装置に有線、及び／又は、無線（例えば、ＬＴＥ又はＧＰＲＳを経由して）で接続されるように構成される。装置１０００は、コミュニケーションインターフェース１０８０を通して任意の外部装置と（双方向に）データ交換を行ってもよい。例えば、コミュニケーションインターフェース１０８０を通して更新された地図データは、装置１０００内に保存された地図データを更新する目的で地図データサーバーから検索されることができる。しかし、コミュニケーションインターフェース１０８０を通して受信した地図データが、グラフィック表示のために即座に処理されることも考えられる。
【００４２】
入力装置１０７０は、ユーザーと装置１０００の対話の間にユーザー入力を受け取るように構成される。ユーザー入力は、例えば、出発点、目的点、又は、途中停止地の入力のような複数のデータ入力であってよい。しかし、ユーザー入力はまた、選択操作（例えば、表示されるアイコン、メニュー、又はサブメニューの選択）、及び、例えば、地図製作データがスクリーン１０３０にどのように表示されるか（例えば、ズーム命令、又は、グラフィック表示の図法が変更される命令）を指定する制御命令であってもよい。この関連において、入力は、入力キーを作動させることにより、スクリーンにタッチすることにより、及び／又は、音声に基づく方法で実行されてもよい。それらに対応して、入力ユニットは、タッチ感応画面、キーボード、マウス、ジョイスティック、及び／又は、音声入力を理解し、それを対応する制御命令に変換することができる音声認識ユニットを含んでよい。
【００４３】
センサー装置１０６０は、装置１０００の現在の地理上の位置を決定するために、衛星に基づく位置センサー（例えば、ＧＰＳ信号、Ｇａｌｉｌｅｏ信号、及び／又は、Ｇｌｏｎａｓｓ信号を受信するセンサー）を含んでよい。これに加えて、又は、これに代わって、センサー装置１０６０は、装置１０００の位置を決定するために、例えば、走行距離計及びジャイロスコープのような相対的な位置センサーを含んでいてもよい。相対的な位置センサーが使用される場合、装置の絶対的な位置は、推測航法の原理によって決定される。現在位置は、例えば、ナビゲーションの間に必要とされる。
【００４４】
データメモリ１０５０は、地図製作データをデジタル形式で保存するように構成される。デジタル形式で提供される地図製作データは、この関連において、所定のフォーマットに対応してデータベース中に組織化され体系化される。例えば、地図データフォーマットとして、Ｎａｖｉｇａｔｉｏｎ  Ｄａｔａ  Ｓｔａｎｄａｒｄ地図データフォーマット（略して、ＮＤＳ地図データフォーマット）が使われてもよい。これに代わって、他の地図データフォーマットも用いられてよい。本発明の解決法は、地図データフォーマットの詳細に依存しない。
【００４５】
保存された地図製作データは、少なくとも道路端部データと道路交点データを含む。道路端部データは、隣接する交差点又は合流点の間の、道路ネットワークの実際の道路区間を表す。道路交点データは、導入部で述べたように交差点又は合流点を表す。道路端部データと道路交点データには、例えば、車線の数、道路の幅、交差点のトポロジー（例えば、環状交差路、Ｔ字路、くぐり抜け道路（アンダーパス）、高架路（オーバーパス）等）、及び交差点で交わる道路の数を再現する一連の属性が提供されてもよい。そのような形式の属性情報は、現実的なグラフィック表示を生成するために、道路ネットワーク、個々の道路、又は交差のグラフィック表示の間に得られてもよい。
【００４６】
さらに、地図製作データは、道路端部に割り当てられた複数の形状点を含む。導入部で述べたように、複数の形状点は、道路区間の道路輪郭（例えば、曲線輪郭）を定めるために提供される。このため、地理上の座標系に関連して道路区間の曲線輪郭（すなわち、幾何学的な形状）を指定する一連の形状点が、道路区間を表す各々の道路端部へ割り当てられる。換言すれば、各々の道路区間の道路輪郭は、道路区間に割り当てられた一連の形状点によってパラメータ化される。複数の形状点に代わり、又は、それらに加えて、地図製作データは、各々の道路区間の道路輪郭を表す具体的なパラメータ化された曲線を含んでもよい。そのような場合には、複数の形状点に代わり、複数のパラメータ曲線がデータメモリから読みだされ、処理され、そして、スクリーン１０３０でのグラフィック表示のためにＧＰＵ１０２０へ送られてもよい。
【００４７】
スクリーン１０３０は、地図製作データがユーザーに視認できるように構成される。具体的には、スクリーン１０３０は、ＧＰＵ１０２０によって処理された地図製作データを表示する。スクリーン１０３０は、タッチ感応スクリーンの形式をとってもよい。スクリーン１０３０に加えて、又は、それに代えて、ＧＰＵ１０２０によって利用可能とされた画像データを出力するプロジェクタが提供されてもよい。
【００４８】
ユニット１０１１は、保存された道路端部データ（及び、道路交点データ）に基づいて、道路区間又は計算された経路に対するパラメータ化された曲線を生成するように構成される。ユニット１０１１は、この関連において、２次元又は３次元のパラメータ曲線を生成することができる。一つの変形態様によれば、ユニット１０１１は、道路区間に割り当てられることができる、保存された複数の形状点に基づいて、複数の道路区間に対して一つのパラメータ化された曲線を生成するように構成される。この関連において、各々のパラメータ化された曲線は、一つの道路区間の道路輪郭（又は曲がり具合）を再現する。複数の形状点に基づいてユニット１０１１で実行されるパラメータ化の方法が、図４及び図５を参照して以下でより詳細に示される。
【００４９】
一つの実施態様によれば、道路区間のパラメータ化はまた、地図製作データが既に道路区間のグラフィック表示用に適切にパラメータ化されているという条件のもとで省略されてもよい。この場合、各々のパラメータ化された道路区間は、データメモリ１０５０から直接読みだされ、さらなる処理のために分割ユニット１０１２へ送られることができる。
【００５０】
ユニット１０１２は、ユニット１０１１によって生成されたパラメータ化された曲線（又は、地図製作データ内に保存され、読みだされたパラメータ化された曲線）を、複数の相互に独立した曲線区間に分割するように構成される。パラメータ化された曲線の分割については、図４及び図５を参照して以下でさらに詳細に議論される。その後、分割された複数の曲線は、グラフィック表示のためにＧＰＵ１０２０へ送られる。
【００５１】
ユニット１０１１とユニット１０１２は、スタンドアロンユニットの形式をとってもよい。しかし、それらは、図２の破線によって示されるように、コア機能部１０１０の一部分でもよい。さらに、コア機能部は、例えば、ＰＯＩ、３次元都市モデル等のようなグラフィック（表示）対象物が、道路区間又は経路とともにスクリーン１０３０に表示されるならば（及び、地図製作データがそのような形式の情報を含むならば）、グラフィック（表示）対象物の画像計算のために提供されてもよい。コア機能部１０１０は、表示される対象物の複数の頂点を計算し、それらをグラフィック表示のためにＧＰＵ１０２０へ送る。コンピュータグラフィックスにおいては、表示される対象物の点は、頂点と呼ばれる。この点は、例えば、（所定の地球的座標系に関連した）位置情報、法線ベクトル情報、テクスチャ情報等を含む一組の属性に関連付けられてもよい。
【００５２】
グラフィックメモリ１０２０ａは、ワーキングメモリ１０４０から独立したスタンドアロンメモリとして構成される。そのメモリは、表示されるグラフィックデータ（グラフィックフレーム）をバッファーに保留するために、及び／又は、コア機能部１０１０、及び／又は、ユニット１０１２によって提供される頂点のデータをバッファーに保留するために、提供される。一つの選択的な構成においては、グラフィックメモリ１０２０ａはワーキングメモリ１０４０の一部分でもよい。
【００５３】
ＧＰＵ１０２０は、スクリーン１０３０への地図製作データのグラフィック出力を制御するように構成される。具体的には、ＧＰＵ１０２０は、コア機能部１０１０、及び／又は、ユニット１０１２によって提供される画像データ（頂点データ）に基づいて、スクリーンへの出力を計算するように構成される。このため、ＧＰＵ１０２０は、対象物のグラフィック表示のために必要とされ、図３に関連してより詳細に記述される、複数のグラフィック機能を実行する。さらに、ＧＰＵ１０２０は、標準ＯｐｅｎＧＬ  ４．０（又は、より高いバージョン）、又は、例えば、Ｄｉｒｅｃｔ３Ｄ  １１のような類似のグラフィックＡＰＩによって指定されるテッセレーション機能を実行するように構成されるテッセレーションユニットを含む。
【００５４】
ＧＰＵ１０２０の動作様式が、図３とそこに示されたグラフィックパイプラインに基づいてより詳細に明らかにされる。コンピュータグラフィックスの分野の（しばしば、「レンダリングパイプライン」とも呼ばれる）「グラフィックパイプライン」によって、グラフィック（表示）対象物をスクリーン１０３０に、又は、他の視覚による出力媒体にグラフィック表示するために、グラフィックプロセッサ内部で実行されるグラフィック機能を実施する、又は、処理する、一連のグラフィック処理工程が理解される。
【００５５】
図３の簡略化されたグラフィックパイプラインの表示から明らかなように、ＧＰＵ１０２０は、幾つかのシェーダーと一つのテッセレーションユニットを動作させる。シェーダーとは、グラフィックパイプラインの内部でグラフィック表示の、ある機能又は効果（レンダリング効果）を実行するプログラム可能なハードウエアモジュール、又は、ソフトウエアモジュールである。例えば、シェーダーは３Ｄ効果を生成するためにプログラムされることができる。この関連において、個々のシェーダーの適合と駆動が、ＧＰＵ１０２０とアプリケーションプログラムの間の抽象化レイヤーを表すグラフィックプログラミングインターフェース（例えば、ＯｐｅｎＧＬのようなグラフィックＡＰＩ）によって行われる。
【００５６】
具体的には、グラフィックパイプラインは、頂点シェーダー１０２１、クリッピング及びラスタ化ステージ１０２５、任意で提供されるジオメトリシェーダー１０２６とフラグメントシェーダー１０２７を備える。さらに、ＧＰＵ１０２０は、テッセレーション機能を実行するために提供されるテッセレーションユニット１０２３、テッセレーション制御シェーダー１０２２及びテッセレーション評価シェーダー１０２４を含む。
【００５７】
頂点シェーダー１０２１（例えば、個々の頂点の座標変換）、クリッピング及びラスタ化ステージ１０２５、ジオメトリシェーダー１０２６、及びフラグメントシェーダー１０２７の機能は、初期のＯｐｅｎＧＬのバージョンのグラフィックパイプラインの、対応するシェーダーの機能にそれぞれ一致し、当業者には十分公知である。従って、それらをこれ以上説明はしない。ＯｐｅｎＧＬ  ４．０（及び、より高いバージョン）では、テッセレーション制御シェーダー１０２２、テッセレーションユニット１０２３、及び、テッセレーション評価シェーダー１０２４が、新規にＯｐｅｎＧＬグラフィックパイプラインの中に導入されている。それらの機能は、以下でより詳細に記述される。
【００５８】
プログラム可能なテッセレーション制御シェーダー１０２２が、グラフィックパイプライン内で、頂点シェーダー１０２１とテッセレーションユニット１０２３の間に配置される。テッセレーション制御シェーダー１０２２は、一つのパッチに対して一つのテッセレーション要素を定めるように設計される。この関連において、「パッチ」とは、テッセレーション機能の実行に関連してグラフィックパイプラインに導入された、新しい形式の基本要素を意味する。「パッチ」は、（頂点シェーダーによって提供される）グラフィック表示の要素を表す複数の頂点の集合を意味する。シェーダー１０２２によって定められるテッセレーション要素は、一つのパッチが下流側のテッセレーションユニット１０２３によって何個のサブユニット（細分区間）に分割されるべきかを指定する。
【００５９】
テッセレーション制御シェーダー１０２２において、テッセレーション要素に加えて、さらに、例えば、テッセレーションの形式（例えば、パッチを三角形の基本要素、又は、矩形の基本要素に分割すること）及びテッセレーションのための（２次元の）領域を定めるテッセレーションパラメータが利用可能にされ、それにより、領域は矩形又は三角形（重心座標系）でよい。特定の領域の選択を通して、テッセレーションに対する座標系が定められ、外部のテッセレーション要素が各々の座標に提供される。さらに、領域が内側の区域の中でどのようにテッセレーションされるか指定する内部テッセレーション要素がその領域に対して定められることができる。
【００６０】
本発明に対応する曲線区間のテッセレーションについては、三角形の領域が選択され、内部テッセレーション要素が、外部テッセレーション要素と同等とみなされる（以下では、単に「テッセレーション要素」と呼ぶ）。曲線区間依存のテッセレーション要素についての規定が、図７との関係において、以下でより詳細に記述される。
【００６１】
プログラム不可のテッセレーションユニット１０２３は、テッセレーション制御シェーダー１０２２において定められたテッセレーション要素とテッセレーションパラメータに基づいて、テッセレーションパターンを生成するように構成される。具体的には、テッセレーションユニット１０２３は、複数の走査点を生成し、テッセレーションパターンを生成するために、複数の走査点が相互にどのように連結されるかを定める。
【００６２】
プログラム可能なテッセレーション評価シェーダー１０２４は、テッセレーションユニット１０２３によって定められたテッセレーションパターン（すなわち、走査点と走査点の連結の方式）に基づいて、及び、パッチの属性（位置座標、法線ベクトル等）に基づいて、複数の走査点に対しての複数の頂点位置を計算するように構成される。特に、テッセレーション評価シェーダー１０２４は、頂点位置に対して補間された属性を定めるようにも構成される。
【００６３】
図４を参照して、上述のハードウエアテッセレーションを用いた道路区間のグラフィック表示方法の実施態様がより詳細に明らかにされる。
【００６４】
第一の工程Ｓ１００によれば、ユニット１０１１によって、スクリーン１０３０に表示される道路区間の道路輪郭を表すためのパラメータ化が定められる。パラメータ化された曲線は、道路区間の実際の道路輪郭（すなわち、曲線輪郭）を再現する。その定める工程は、道路区間に割り当てられた複数の形状点に基づいて（及び、道路区間に割り当てられることができる道路交点データに基づいて）、グラフィック表示される適切なパラメータ化された道路区間を生成する工程を有する。パラメータ化の計算は、複数の形状点が（ワーキングメモリ１０４０内に）ロードされた後すぐに（すなわち、動的に）、各々の道路区間に対して行われることができる。グラフィック表示方法の中で実行されることができる、適切で、リソースを節約するパラメータ化について、図５を参照してより詳細に記述される。
【００６５】
これに代わり、パラメータ化された道路輪郭が、予め、地図データサプライヤによって提供されてもよい。この場合、前記定める工程は、単に、パラメータ化された道路輪郭（又は、パラメータ化を表すパラメータ）を読みだし、ワーキングメモリ１０４０にロードする工程を有する。そして、ワーキングメモリ１０４０内に一時的に保存されたデータは、さらなる処理のために、分割ユニット１０１２へ供給されることができる。
【００６６】
次の工程Ｓ１１０において、ユニット１０１２によって、道路区間のパラメータ化された道路輪郭が、相互に独立した複数の曲線区間に分割される。この関連において、その分割は、道路区間に沿ったパラメータ化された道路輪郭の関数として行われることができる。具体的には、一つの道路区間のパラメータ化された道路輪郭の分割は、所定のパラメータ区間内の道路区間の局所的な道路輪郭が、各々の曲線区間に一致するように行われることができる。所定のパラメータ区間は、二つの連続するパラメータ節点を通してそれぞれ定められてもよい。
【００６７】
続く第三の工程Ｓ１２０において、少なくとも一つのテッセレーション要素が、テッセレーション制御シェーダー１０２２によって、各々の曲線区間に対して定められる。少なくとも一つのテッセレーション要素は、各々の曲線区間が道路輪郭の方向に何個の細分区間に細分されるべきか（テッセレーションされるべきか）を指定する。テッセレーション要素を定めることは、各々の曲線区間の曲がり具合の関数として、テッセレーション制御シェーダー１０２２内でテッセレーション要素を計算することを含む。その結果、テッセレーション要素を定めることは、各々の分割された曲線区間の湾曲の程度に依存し、道路区間内の隣接する複数の曲線区間の間で変化してもよい。例えば、もし、ある曲線区間が強い湾曲の程度（重度の曲がり具合）を示すならば、その時は定められたテッセレーション要素はより大きくなり、このことは道路輪郭の方向に曲線区間をより細かく細分することに関連する。換言すれば、より大きなテッセレーション要素により、曲線区間のより細かいテッセレーションが得られ、そのことによって、曲線輪郭がスクリーン上により精細に（すなわち、より高い細部の正確さで）グラフィック表示されることができる。各々の曲線区間の曲がり具合の関数としてテッセレーション要素を動的に計算することが、図６に関連して詳細に記述される。
【００６８】
次の工程Ｓ１３０において、テッセレーションパターンが、定められたテッセレーション要素（及び、さらに、上述のテッセレーションパラメータ）に基づいて、テッセレーションユニット１０２３によって生成される。テッセレーションをパラメータ化するために、テッセレーション要素の関数として複数の三角形に分割される矩形の単位領域が、選択される。ＧＰＵ１０２０は、三角形の表示に対して最適化され、グラフィック（表示）対象物の、表示される任意の領域が、三角形によって最適に表されることができるので、三角形への分割が保証される。
【００６９】
続く工程Ｓ１４０において、スクリーン１０３０に表示されることができる複数の基本要素が、生成されたテッセレーションパターンとパラメータ化された道路輪郭に基づいて生成される。もしテッセレーションパターンが複数の三角形の網目組織で構成されるならば、三角形の基本要素の頂点は、スクリーン１０３０にグラフィック表示される曲線区間を用いて、パラメータ化とパターンに基づいて計算される。その結果、スクリーン１０３０に表示される各々の曲線区間は、複数の三角形の基本要素から構成され、使用される三角形の数が曲線を再現する精細さを決定し、テッセレーション要素によって決定される。
【００７０】
以下では、道路区間の道路輪郭のパラメータ化を定める方法が詳細に記述される。パラメータ化は、各々の道路区間についての地図製作データ内で定められた複数の形状点に基づいて行われる。そのパラメータ化の方法は、図４に示された方法に関連して実行されることができる。
【００７１】
利用可能な形状点に基づく道路輪郭のパラメータ化（パラメータ曲線の生成）に対して、非一様に分布させられた節点ｔｉを有する２次のＢ−スプライン（以下では、「２次の非一様なＢ−スプライン」又は「２次のＮＵＢＳ」と呼ぶ）が典型的な方法で使用される。この関連において、２次のＮＵＢＳの曲線輪郭は、ｔ０≦ｔ１≦・・・≦ｔｎ＋２の条件が満足される時に、ｎ個のチェック点
0006009039.tif 000016
（ｉ＝０，・・・，ｎ−１）、いわゆるｄｅ  Ｂｏｏｒ点、及び、ｎ＋３個の節点を用いて表されることができる。このとき、２次のＮＵＢＳは、節点によって予め決定された１次元のパラメータ空間［ｔ２，ｔｎ］からパラメータ値ｕを２次元又は３次元空間Ｒｋ（ｋは空間の次数を示す）の中に配列の規則、
0006009039.tif 000017
に従ってマッピングする、１次元パラメータ空間［ｔ２，ｔｎ］内で定義されたパラメータ曲線
0006009039.tif 000018
である。ここで、
0006009039.tif 000019
は以下の式に従って節点間隔に対して定義される、パラメータ化の基底関数を表す。
0006009039.tif 000020
【００７２】
２次のＮＵＢＳの第一の導関数は線形（１次）のＮＵＢＳであり、以下のように定義される。
0006009039.tif 000021
【００７３】
以下では、一連の形状点からのＮＵＢＳの計算が記述される。形状点からの２次のＮＵＢＳの計算に関連して、パラメータ化された曲線が一連の形状点を補間することが仮定される。この関連において、「補間」はパラメータ曲線が複数の形状点を正確に通過することを意味し、単にそれらに近づくことを意味していない。しかし、パラメータ曲線が単に複数の形状点に近づくように、パラメータ曲線を計算することも考えうる。
【００７４】
複数の形状点からｄｅ  Ｂｏｏｒ点
0006009039.tif 000022
と節点ｔｉを計算するために、弦パラメータ化と平均節点ベクトルによるＢ−スプライン補間技術が用いられる。０＜ｊ＜ｎ−２であるときに、弦パラメータ化を用いて、一つの道路区間がｎ−２個の形状点
0006009039.tif 000023
で構成されるという仮定に基づき、まず第一に、パラメータ値ｕｉは以下の式に従って決定される。
0006009039.tif 000024
【００７５】
そして、パラメータ値ｕｉから、パラメータ化の節点ｔｉが以下の式に従って計算される。
0006009039.tif 000025
【００７６】
節点の列（ｔ０，・・・，ｔｎ＋２）も節点ベクトルと呼ばれる。上式に従って計算された節点ベクトルは、文献においては、平均節点ベクトルとして知られている。
【００７７】
そして、節点ベクトルを用いて、０＜ｊ＜ｎ−２として、ｄｅ  Ｂｏｏｒ点
0006009039.tif 000026
を計算するための１次元の式体系、
0006009039.tif 000027
を提示することができる。
【００７８】
ただちに明らかなように、この１次元の式体系は、ｎ−２個の式とｎ個の未知のｄｅ  Ｂｏｏｒ点
0006009039.tif 000028
を有している。このことは、１次元の式体系が劣決定であり、その結果、唯一の解を持たないことを意味している。
【００７９】
その式体系は、一つ以上の境界条件を設定することによって、より詳細に決定されることができる。境界条件を通して、始点と終点でのパラメータ化の第一の導関数は、式
0006009039.tif 000029
を満足し、その結果として、隣接する区間の間の滑らかな変化（変わり目）が得られる。前述の式体系に境界条件を含めることによって、以下の行列−ベクトル表記法で記述されることができる式体系が得られる。
0006009039.tif 000030
【００８０】
基底関数
0006009039.tif 000031
は各々部分的に定義され、多くのパラメータ値ｕｉに対して零の値を取るので（（２）式を参照）、行列の多くの（対角線以外の）エントリ（項目）は零である。その結果、
0006009039.tif 000032
は標準的な方法で適切に解かれることができる、まばらに埋められた行列を表す。上記の式体系を解くことによって、ｄｅ  Ｂｏｏｒ点
0006009039.tif 000033
が確認されることができる。
【００８１】
結局、ここに記載されたパラメータ化の方法は、ナビゲーション装置の動作中に（すなわち、地図データベースから複数の形状点をアップロードした後に）実行されることができる、非常に効率的で、リソースを節約する方法を構成する。提示されたパラメータ化の方法は、地図データの編集の間に、ＮＵＢＳを用いて作動させることに対しても適切であることが、理解されるだろう。そして、パラメータ化（ｄｅ  Ｂｏｏｒ点及び節点ベクトル）が直接地図データベース内に保存され、その後のグラフィック表示の目的で検索されることができる。
【００８２】
図５を参照して、一つの道路区間について定められたパラメータ曲線の複数の曲線区間の区分的な分割が、さらに明らかにされる。
【００８３】
２次のＮＵＢＳを用いてここで使用されるパラメータ化の利点は、各々の２次のＮＵＢＳが複数の２次の多項式に区分的に分割されることができることである。具体的には、（ｎ−２個の形状点を有する）各々の道路区間のパラメータ化されたＮＵＢＳは、ｎ−２個のＢ−スプライン区間（すなわち、曲線区間）に分割されることができ、間隔［ｔｉ，ｔｉ＋１］内の曲線区間は以下の表記に従って、一つの２次の多項式として解釈されることができる。
0006009039.tif 000034
【００８４】
この関連において、関係する基底関数
0006009039.tif 000035
は、２≦ｉ≦ｎ＋１として、以下の形式
0006009039.tif 000036
で表されることができる。上述した式による２次の多項式の区分的な表記は、（２）式の表記に一致することが注意されるべきである。
【００８５】
図５により、一つのパラメータ曲線８０を複数の２次の多項式に区分的に分割する工程が典型的な方法で明らかにされる。図５に示された曲線８０は、相互に独立した３つの曲線区間８１、８２、８３に分割されることができる道路区間のパラメータ化されたＮＵＢＳの詳細を示している。３つの区間８１、８２、８３の各々は、パラメータ曲線の特別な部分的曲線輪郭を表している。区間８１が凹形状の曲線輪郭を表す一方、区間８２及び８３は凸形状の曲線輪郭を示す。
【００８６】
図５に示された、曲線８０の下のグラフ９０は、節点値ｔｉの関数として曲線区間８１、８２、８３に対してそれぞれ必要とされる基底関数Ｎｉを示している。区間８１は、（バー９２ａで示される）パラメータ区間［ｔ２，ｔ３］の曲線輪郭を表し、ｄｅ  Ｂｏｏｒ点
0006009039.tif 000037
とバー７１ａによって示される４つの節点値（ｔ１，ｔ２，ｔ３，ｔ４）を用いて完全に記述される２次の多項式によって表される。同様に、パラメータ区間［ｔ３，ｔ４］と［ｔ４，ｔ５］（グラフ９０のバー９２ｂ、９２ｃを参照）で定義される曲線区間８２と８３は、それぞれ、ｄｅ  Ｂｏｏｒ点
0006009039.tif 000038
と
0006009039.tif 000039
、及び節点値（ｔ２、ｔ３、ｔ４、ｔ５）と（ｔ３、ｔ４、ｔ５、ｔ６）（バー７１ｂ、７１ｃ）によって表される。この図から、より一般的に、ｎ−２個の形状点に基づいてパラメータ化された曲線が、ｉ番目の節点区間［ｔｉ，ｔｉ＋１］に対して、単に３つのｄｅ  Ｂｏｏｒ点
0006009039.tif 000040
と４つのエントリ（項目）を有する節点ベクトル
0006009039.tif 000041
よって完全に表されることができる、ｎ−２個の相互に独立した２次の多項式に分割されることができるということになる。例えば、３次のＢ−スプライン又はベジエ曲線のような他のパラメータ化された曲線は、区間ごとの表示に対して、実質的により大きなパラメータセットを必要とし、それによって、処理の間に、実質的により多くのプロセッサリソースとメモリリソースを必要とするので、これら他のパラメータ化された曲線に比較して、ここで用いられる２次のパラメータ化の利点が、明らかになる。
【００８７】
ここに示される、パラメータ化した後の分割のさらなる利点は、テッセレーション（特に、テッセレーションの程度）が個々の曲線区間の曲がり具合に個別に適応されることができるという事実にある。
【００８８】
各々の曲線区間の個々のテッセレーションとグラフィック表示のために、各々の曲線区間を表す３つのｄｅ  Ｂｏｏｒ点
0006009039.tif 000042
と節点ベクトル
0006009039.tif 000043
が頂点属性としてパッチへ割り当てられる。換言すれば、パッチは各々の場合において、分割された曲線区間を表している。各々のパッチの頂点属性は、テッセレーションのために、グラフィックメモリ１０２０ａ内にロードされる。図５に示された分割から明らかなように、連続する曲線区間を表すパッチの頂点属性は、部分的に繰り返される。例えば、区間８１、８２、８３の処理のために、節点ベクトル
0006009039.tif 000044
とｄｅ  Ｂｏｏｒ点
0006009039.tif 000045
がＧＰＵ１０２０内へロードされなければならない。より一般的に定式化すると、ｎ−２個の曲線区間（パッチ）に分割された道路区間のグラフィック表示のために、以下の形式の頂点属性列Ｖ´
0006009039.tif 000046
がＧＰＵメモリ１０２０ａ内に保存される。ベクトル
0006009039.tif 000047
は次元が異なることが注意されるべきである。
0006009039.tif 000048
が４次元のベクトルを表すのに対して、ｄｅ  Ｂｏｏｒ点
0006009039.tif 000049
は単に２次元又は３次元のベクトルを形成する（３Ｄのパラメータ化の場合）。パッチの全ての頂点属性は同じ次元を持たなければならないので、ｄｅ  Ｂｏｏｒ点
0006009039.tif 000050
の次元は、２次元又は３次元のｄｅ  Ｂｏｏｒ点
0006009039.tif 000051
を頂点属性列Ｖ´内にコピーし、欠けているエントリ（項目）を零で埋めることによって節点ベクトル
0006009039.tif 000052
の次元に適応される。
【００８９】
（１１）式から推論されるように、頂点属性列内のｄｅ  Ｂｏｏｒ点
0006009039.tif 000053
と節点値は部分的に３回繰り返される。グラフィックメモリ１０２０ａの不必要な要求と浪費を避けるために、各々のＮＵＢＳは後述する頂点属性列Ｖと索引配列Ｉを用いて表される。
【００９０】
頂点属性列Ｖにおいて、一つの道路区間の複数の曲線区間のｄｅ  Ｂｏｏｒ点
0006009039.tif 000054
と節点ベクトル
0006009039.tif 000055
は、以下の表記に従ってネストされ、
0006009039.tif 000056
頂点属性列内の複数の属性の割り当ては、以下の帰納的な割り当て規則に従う。
0006009039.tif 000057
【００９１】
このようにして得られた頂点属性列においては、各々の属性は一度だけ保存され、その結果、ＧＰＵメモリリソースは著しく節約されることができることが注意されるべきである。
【００９２】
他方、頂点属性列Ｖから個々の曲線区間の頂点属性を獲得するために、頂点属性列Ｖ内の正確なエントリがアクセスされねばならない。そのアクセスは索引配列Ｉによって定められる。上記の頂点属性列の表記Ｖによれば、列エントリＶ［０］、Ｖ［１］、Ｖ［２］及びＶ［３］はＮＵＢＳの第一の曲線区間を定義し、エントリＶ［１］、Ｖ［２］、Ｖ［４］及びＶ［５］はそれに続く第二の曲線区間を定義し、２≦ｉ＜ｎ−１のとき、エントリＶ［２（ｉ−１）］、Ｖ［２ｉ］、Ｖ［２（ｉ＋１）］及びＶ［２（ｉ＋１）＋１］は各々のさらに他の区間を定義する。
【００９３】
このようにして得られる一連の索引は、以下の索引配列内に保存され、
0006009039.tif 000058
ここで、括弧は個々のパッチ（又は曲線区間）を区別するためだけに用いられる。これから、頂点属性列Ｖを示すための複数の索引が得られることができ、第一のパッチを起源として、下式が適用される。
0006009039.tif 000059
【００９４】
図６及び図７を参照して、ＧＰＵ１０２０内で実行されるテッセレーション機能を用いたＮＵＢＳのグラフィック表示が、より詳細に記述される。
【００９５】
テッセレーション機能は、図６に示され、図３との関連で簡単に議論された、プログラム可能なテッセレーション制御シェーダー１０２２、テッセレーションユニット１０２３、及びテッセレーション評価シェーダー１０２４に基づいて実行される。
【００９６】
プログラム可能なテッセレーション制御シェーダー１０２２の主要なタスクは、テッセレーションユニット１０２３に対して少なくとも一つのテッセレーション要素を準備することである。さらに、シェーダー１０２２内で、テッセレーションの形式とテッセレーションのための領域が定められる。（ｕ，ｖ）座標を用いて表され、ｕ座標とｖ座標に沿ってそれぞれ０から１まで延伸する端部を備える、矩形の単位領域３５が定められる。この関連において、ｕ座標は、パラメータ化された曲線区間の道路輪郭の方向を示し、一方、ｕ座標に垂直なｖ座標は、道路幅の方向を示す（ＯｐｅｎＧＬに従って、座標はｕとｖで示される；座標が他のものでも示しうることが理解されるだろう。）。座標ｕ、ｖについて、テッセレーション要素がそれぞれ定められる。
【００９７】
以下では、座標ｕとｖについてのテッセレーション要素の準備について、より詳細に記述される。この関連において、道路輪郭及び道路幅を備える２次元の対象物としての道路と経路のグラフィック表示が、主に道路輪郭（すなわち、与えられた曲線輪郭）によって決定されることが、もう一度参照される。道路の幅は、道路輪郭に沿って一定であるという近似によって仮定されることができる。それに対応して、一定の値が幅（ｖ方向のテッセレーション要素）に関連したテッセレーション要素に割り当てられる。選択的に、ｖ方向のテッセレーション要素として、１の値が固定され、それによりテッセレーションユニット１０２３は、ｖ方向に２つの走査点だけを生成する。その結果、一定のテッセレーションがｖ方向に実行される。
【００９８】
道路輪郭の方向において、すなわち、ｕ方向において、テッセレーション要素の準備は、各々の曲線区間の曲がり具合の関数として行われる。換言すれば、その準備は各々のパッチに対するテッセレーション要素の個々の計算を含んでいる。図６に示されるように（矢印を参照）、各々のパッチはそれぞれ、パラメータ化されたＮＵＢＳの、可能な限り最小の独立した抽出を表し、３つのｄｅ  Ｂｏｏｒ点
0006009039.tif 000060
と節点ベクトル
0006009039.tif 000061
によって独自に表されることができ、シェーダー１０２２へ送られる。
【００９９】
テッセレーション要素の計算が、図７の模式図を参照して明らかにされる。図７は、道路区間５０のパラメータ化されたｉ番目のパッチ５０ａを典型的な方法で示しており、ｉ番目のパッチ５０ａはパラメータ区間［ｔｉ，ｔｉ＋１］に対する曲線輪郭を表している。さらに、図７は、テッセレーション要素の計算のために必要とされる点
0006009039.tif 000062
を示しており、それらはパラメータ値ｔｉ、（１／２）×（ｔｉ＋ｔｉ＋１）、及びｔｉ＋１でのパラメータ化されたＦｉを評価することによって得られる。
【０１００】
図７に示され、テッセレーション要素の計算に用いられる点
0006009039.tif 000063
は、スクリーン空間座標内にあることが注意されるべきである。点
0006009039.tif 000064
を計算するために、パラメータ曲線Ｆｉは最初に視覚空間の座標に変換され、次に、曲線の始点ｔｉで、半区間の距離で（すなわち、（１／２）×（ｔｉ＋ｔｉ＋１）で）、及び曲線の終点ｔｉ＋１で以下の式に従って、評価される。
0006009039.tif 000065
【０１０１】
そして、パラメータ曲線上にある点
0006009039.tif 000066
は、２次元のスクリーン空間座標
0006009039.tif 000067
に表示される。もし、３次元のパラメータ化が得られるなら、表示は以下の式に従って実行される。
0006009039.tif 000068
ここで、Ｐは４×４の射影行列を表し、ｎｉ，ｗはベクトル
0006009039.tif 000069
の４番目の成分を示し、ｗとｈはスクリーン幅とスクリーン高さを指定する。索引ｉは、（１６）式の値（０，１，２）、すなわち、表示される点
0006009039.tif 000070
の索引値を仮定する。ついでながら、「Ｔ」は「転置行列」を表している。
【０１０２】
計算された点
0006009039.tif 000071
を参照して、始点
0006009039.tif 000072
と終点
0006009039.tif 000073
を結ぶ直線ｇｉから垂直な中点
0006009039.tif 000074
までの距離ε０が計算される（図７を参照）。確認された距離ε０はピクセルで測定される。この関連において、もし、
0006009039.tif 000075
によってパラメータ化された曲線区間が始点
0006009039.tif 000076
と終点
0006009039.tif 000077
を通過する直線ｇによって近似されるならば、ε０は誤差の測定値である。
【０１０３】
公知のＮＵＢＳ細分アルゴリズムを適用し、パラメータ区間［ｔｉ，ｔｉ＋１］内で、曲線区間Ｆｉを適切にさらに細分することによって、誤差が連続的に減少し、ｍ個の細分後に、テッセレーションされた曲線のそれ（逸脱）の誤差値は以下の式に従って見積もられることができる。
0006009039.tif 000078
【０１０４】
この場合、曲線区間
0006009039.tif 000079
は所定の誤差δに達しなくなるときまで、すなわち、不等式
0006009039.tif 000080
が満足されるまで、細分される。ここで、δはピクセル値を表す。例えば、δの値は、スクリーン空間における半ピクセルに一致してもよい。
【０１０５】
ｍ個の細分の後、パッチに対して、道路輪郭（すなわち、ｕ座標に対して）の方向に合計２２ｍ＋１＋１個の走査点が生成される。さらに、曲線輪郭の方向に、以下の細分
0006009039.tif 000081
が生成される。この関連において、ｕｔｅｓｓがテッセレーション要素と呼ばれ、検討中の曲線区間
0006009039.tif 000082
に対して曲線輪郭の方向の細分の数を指定する。
【０１０６】
（１９）式の対数をとることによって、次式になる。
0006009039.tif 000083
【０１０７】
（２０）式を参照して、（１８）式にｍを代入することによって、以下の式
0006009039.tif 000084
に従って、テッセレーション要素ｕｔｅｓｓについての見積もりが得られることができる。（２１）式によれば、テッセレーション要素は、有理な値と考えてもよい。最近のＧＰＵは有理のテッセレーション要素もサポートしているので、そのような値がテッセレーションのために求められることができ、そのことによって、連続するパッチのテッセレーション要素の間の継ぎ目のない変化が可能になる。
【０１０８】
結局、（２１）式によって、各々の曲線区間についてのテッセレーション要素が、２つのパラメータε０とδから個々に見積もられることができ、ここでδは不変の規定値を表し、ε０は３つの、評価され変換された点
0006009039.tif 000085
から計算される。（２１）式で与えられる見積もりにより、各々の曲線区間についてのテッセレーション要素が、この目的で個々に実行されなければならない各々のパッチに対する、リソースを消費する繰り返し計算方法を用いることなしに、動的に決定されることができる。
【０１０９】
図６に戻り、いったん、単位領域の二つの座標（ｕ，ｖ）についてのテッセレーション要素がテッセレーション制御シェーダー１０２２によって定められると、それらの要素はテッセレーションユニット１０２３へ供給される。図６に示されるように、テッセレーション要素Ｖｔｅｓｓ＝１に対応するｖ方向の２つの走査点が提供された単位領域について定められ、一方、ｕ方向において、テッセレーション要素ｕｔｅｓｓ＝２２ｍ＋１に対応する２２ｍ＋１個の走査点が生成される。
【０１１０】
図５に示されるテッセレーションパターンにおいて、複数の走査点が２つの座標（ｕ，ｖ）に沿った節点として表される。単位領域が複数の三角形にテッセレーションされる（これは複数のテッセレーションパラメータによって定められることができる）という条件のもとで、複数の節点を参照して、単位領域を表すテッセレーションパターンが２２ｍ＋１個の三角形の網状集合体（網状組織）として生成されることができる。図６に示される典型的な場合では、テッセレーション要素はｕｔｅｓｓ＝６であり、矩形の単位領域はｕ方向に６つの細分区間に細分され、合計で１２個の三角形から構成される。
【０１１１】
最後に、プログラム可能なテッセレーション評価シェーダー１０２４は、各々のパッチに対して、定められたテッセレーションパターンに基づいて（すなわち、計算された複数の走査点とそれらの走査点を連結する形式に基づいて）、及びパッチに含まれる頂点属性（すなわち、複数のｄｅ  Ｂｏｏｒ点、節点ベクトル）に基づいて、スクリーン１０３０に表示されることができる各々のパッチの曲線輪郭を参照して、グラフィック表示されることができる複数の基本要素を生成するように構成される。
【０１１２】
グラフィック表示されることができる複数の基本要素（現在の場合、三角形）を生成するために、基本要素の頂点位置が計算されねばならない。パラメータ領域［ｔｉ，ｔｉ＋１］内での（変換された）パラメータ関数Ｆｉを参照して一つの道路区間の道路輪郭を定義するパッチ５０ａについて、曲線輪郭の方向に沿った三角形の基本要素頂点位置を生成するために、以下のパラメータ値
0006009039.tif 000086
を有するパラメータ化された
0006009039.tif 000087
が評価され、ｕ０はテッセレーションパターン内に提供される、区間［０，１］内の複数の走査点を仮定することができる。その結果、区間［ｔｉ，ｔｉ＋１］内で、テッセレーションパターン内で予め定められた細分の単位を有するパラメータ化された
0006009039.tif 000088
が評価される。これは、多くの走査点ｕ０を持つ高いテッセレーション要素に対して、区間［ｔｉ，ｔｉ＋１］内の多くの頂点
0006009039.tif 000089
が計算されることを意味する。頂点
0006009039.tif 000090
は生成される三角形の基本要素の頂点を表わし、三角形の辺は隣接する頂点を直線的に結ぶ直線（隣接する頂点の間の直線補間）によって表されるので、大きな曲がり具合を有する曲線区間が、区間［ｔｉ，ｔｉ＋１］内の曲線輪郭の方向に沿って定められる複数の頂点が相互にできるだけ近接して続くときにだけ、複数の三角形の基本要素を用いて十分良好に表示されることができることが明らかになる。これは高いテッセレーション要素によって得られる。
【０１１３】
さらに、道路は単に１次元の曲線としてではなく、２次元のグラフィック（表示）対象物としてスクリーン１０３０に表示されるので、各々のパラメータ値
0006009039.tif 000091
に対して、下式
0006009039.tif 000092
に従い、
0006009039.tif 000093
に垂直な法線単位ベクトル
0006009039.tif 000094
に沿った頂点
0006009039.tif 000095
に関連して配置される一つの頂点も生成される。
【０１１４】
この関連において、ｖ０は０又は１の値をとる。λは、大きさの比率を変更可能な、道路又は経路の、表示される密集（度）を参照して、動的に適応できるパラメータである。法線ベクトルｂは、公知の方法で、以下のグラジエント（勾配）に従って計算される。
0006009039.tif 000096
【０１１５】
道路輪郭の方向と道路輪郭に垂直な方向に、テッセレーション評価シェーダー１０２４によって出力される複数の頂点は、その結果、（２３）式に従って生ずる。そして、その頂点から、グラフィック表示されることができる複数の三角形の基本要素が、図６に示したように、パッチ５０ａに対して構成される。
【０１１６】
その結果、各々の曲線区間は、一組の三角形によって、スクリーン１０３０にグラフィック表示されることができる。すなわち、換言すると、各々の曲線区間は表示されることができる一組の三角形の基本要素に分割されることができる。特に、各々の曲線区間の分割は個々に設定されることができ、曲がり具合（及び／又は見る角度）に応じて各々の曲線区間に対して適応されることができる。強い湾曲を持ち、スクリーン１０３０に表示される曲線区間は、より強くテッセレーションされ、その結果、三角形の基本要素によるより細かい網状組織に分割され、一方、弱い湾曲を持つ曲線区間に対しては、より粗いテッセレーションが定められることができる。このように、各々の曲線区間がスクリーン１０３０に、その曲がり具合に関係なく、できるだけ滑らかな曲線として現れることが確実にされ、その結果、スクリーン１０３０上の道路区間、道路ネットワーク、及び経路の表示が実質的に改善される。特に、テッセレーションの動的な適応を通して、できるだけ最適かつ効率的なグラフィック表示が得られることが確実にされる。特に、道路区間の現実的な表示が、この目的で多数の形状点を評価しなければならないということなしに、得られることができる。
【０１１７】
さらに、パラメータ化、道路輪郭の分割、及びグラフィックメモリ内のデータの系統化、ここに記載されたすべてによって、コンピュータのリソースとメモリのリソースが、できるだけ効率的かつ節約的に使われることが確実にされる。特に、ここに記述されたパラメータ化により、複数の形状点に基づき複数の道路区間をパラメータ化することがグラフィック表示の際に（動的に）可能である。
【図１Ａ】
0006009039.tif 000108
【図１Ｂ】
0006009039.tif 000109
【図２】
0006009039.tif 000110
【図３】
0006009039.tif 000111
【図４】
0006009039.tif 000112
【図５】
0006009039.tif 000113
【図６】
0006009039.tif 000114
【図７】
0006009039.tif 000115