ノンフォトリアリスティックな３Ｄマップのためにフォトリアリスティックな３Ｄランドマークを再利用するための方法
ナビゲーションマップを表示する方法は、フォトリアリスティックな三次元データをオフラインで事前に処理する工程を含む。車両の位置は自動的にオンラインで測定される。地理的な領域内に配された物体に関連する事前に処理された三次元データの一部が特定される。地理的な領域は車両の位置を含む。ノンフォトリアリスティックな画像は、事前に処理されたデータの特定された一部に基づいてレンダリングされる。ノンフォトリアリスティックな画像は車両内のユーザーに電子的に表示される。
【発明の詳細な説明】
【技術分野】
【０００１】
１．発明の分野
本発明は電子ナビゲーションマップに関し、より具体的には、電子ナビゲーションマップ用に画像をレンダリングすることに関する。
【背景技術】
【０００２】
２．関連技術の詳細
ナビゲーションマップは、建物、地勢、および、興味のある場所（ＰＯＩ）、例えば、博物館、レストラン、公園およびショッピングセンターを含むランドマークを視覚的に強調するため、よく知らない都市を訪れる人にとって必要不可欠なリソースである。ほとんどの車載の、および、携帯性のナビゲーションデバイス（ＰＮＤ）は、二次元（２Ｄ）でこれらのランドマークを視覚化するために２Ｄのナビゲーションマップに依存しているが、三次元（３Ｄ）の車載ナビゲーションシステムが台頭しつつある。ほとんどのこれらの３Ｄナビゲーションシステムは、三次元のランドマークを視覚化するために、フォトリアリスティック（ｐｈｏｔｏｒｅａｌｉｓｔｉｃ）レンダリング技術を使用している。この視覚化体系では、正確な幾何学モデルと詳細なフォトリアリスティックの建物テクスチャが必要である。これらのシステムは、このようなレンダリングされた三次元の建物、道または他の対象の外観が、実際の建物、道または他の対象の外観と可能な限り一致することを必要とする。したがって、フロントガラス越しに実際の三次元の建物を見ると、ドライバーはフォトリアリスティックな一致（ｐｈｏｔｏｒｅａｌｉｓｔｉｃ ｍａｔｃｈ）を行うことで、三次元のランドマークを認識することができる。一方では、２Ｄナビゲーションシステムは、我々の三次元の世界の詳細をほとんどなにも視覚化しない。他方で、フォトリアリスティックな３Ｄマップに基づくナビゲーションシステムは、我々の三次元世界のあらゆる詳細を視覚化しようとするが、これは必要なくすることができる。
【０００３】
ほとんどのデータプロバイダー（例えば、Ｔｅｌｅ Ａｔｌａｓ）は、直接的なフォトリアリスティックレンダリングに適切な３Ｄマップ要素データ（例えば、３Ｄランドマーク）のみを提供する。より具体的には、ほとんどの３Ｄマップ要素データは、フォトリアリスティックなテクスチャによって取り付けられるポリゴンメッシュの形で提供される。なんの修正もなされない場合、これらのデータは直接的なフォトリアリスティックレンダリングにのみ使用することができる。したがって、これらのデータは直接的なノンフォトリアリスティックレンダリング（ｎｏｎ−ｐｈｏｔｏｒｅａｌｉｓｔｉｃ）（ＮＰＲ）には適していない。しかしながら、ＮＰＲは、ＮＰＲが、ユーザーが観察する現実視界の眺めにレンダリングを容易に一致させることができるような正確な（詳細を必要としない）方法で画像を示してもよく、ＮＰＲレンダリングをもたらすために低レベルの計算ソースしか必要とされないという点で、フォトリアリスティックレンダリング以上に有益である。
【０００４】
先行技術で開示も示唆もされていないものは、フォトリアリスティックレンダリングのために意図される従来の市販の３Ｄマップ要素データを用いることによって、ナビゲーションマップ上に、建物、ランドマーク、および、他の３Ｄ物体のＮＰＲレンダリングを提供する方法である。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、ノンフォトリアリスティック（ＮＰＲ）または表現レンダリング技術を用いることによって、ナビゲーションのために重要な詳細のみを視覚化し強調することで、伝統的な２Ｄナビゲーションマップとフォトリアリスティック３Ｄマップの間のギャップを埋める３Ｄナビゲーションシステムを提供する。本発明によれば、利用可能なフォトリアリスティック３Ｄランドマークデータは、ＮＰＲ ３Ｄナビゲーションマップでの表現に富んだ視覚化に再度使用されてもよい。より具体的には、フォトリアリスティック３Ｄランドマークデータは、最初にオフラインで処理されてもよく、その後、ノンフォトリアリスティックレンダリングは高性能を達成するためにランタイムで適用されてもよい。
【課題を解決するための手段】
【０００６】
フォトリアリスティック３Ｄランドマークデータの処理がコンピュータで集約されるため、フォトリアリスティックなデータの事前処理はオフラインで行なわれてもよい。言い換えれば、フォトリアリスティックなデータはすべて、ＮＰＲディスプレイのレンダリングよりも先に受け取られてもよい。さらに具体的に、事前処理はフォトリアリスティックなデータ上で行なわれてもよく、ＮＰＲ情報（ＮＰＲエッジおよびＮＰＲテクスチャ）を包含する事前に処理された３Ｄマップデータは、ユーザーに対する画像のレンダリングよりも先に準備されてもよい。その後、運転中に、事前に処理された３Ｄマップデータは、すでに特定されたエッジと、すでに変換されたテクスチャとを含んで受け取られてもよい。運転中に、ユーザーは、ディスク、ＣＤ、記憶装置、または、インターネットからこのデータを受け取ってもよい。もちろん、いくつかの特定のレンダリング処理は、運転手に対してＮＰＲ画像を表示するためのＮＰＲ情報を備えたデータを準備するために、リアルタイムで行なわれてもよい。
【０００７】
同様に、別の実施形態では、フォトリアリスティックデータは運転中に受け取られることが可能であり、および、ノンフォトリアリスティックデータの変換が運転中に行われることも可能である。しかしながら、フォトリアリスティックデータの処理はコンピュータで集約されるため、多くの処理ハードウェアが要求されることがある。
【０００８】
本発明は、その１つの形状において、オフラインでフォトリアリスティックな三次元データを事前に処理する工程を含む、ナビゲーションマップを表示する方法を含む。車両の位置はオンラインで自動的に測定される。地理的な領域内に配置される物体に関連する事前に処理されたフォトリアリスティックな三次元データの一部が特定される。地理的な領域は、車両の位置を含んでいる。ノンフォトリアリスティックな画像は、事前に処理されたデータの特定された一部に基づいてレンダリングされる。ノンフォトリアリスティックな画像は、車両内のユーザーに電子的に表示される。
【０００９】
本発明は、その別の形状において、車両の位置を自動的に測定する工程を含む、ナビゲーションマップを表示する方法を含む。フォトリアリスティックな三次元データが受け取られる。データは、地理的な領域内に配置される物体に関連している。地理的な領域は、車両の位置を含んでいる。フォトリアリスティックなデータ中の物体のエッジは、自動的に特定され、ノンフォトリアリスティックレンダリングされる。フォトリアリスティックなデータ中のフォトリアリスティックなテクスチャは、ノンフォトリアリスティックなテクスチャに変換される。物体のノンフォトリアリスティックな画像は、ノンフォトリアリスティックなテクスチャ、マークを付けたエッジ、データ中のエッジの各々の幅値に基づいて生成される。ノンフォトリアリスティックな画像は、車両内のユーザーに電子的に表示される。
【００１０】
本発明は、さらに別の形状で、物体に関連するフォトリアリスティックな三次元データ中の物体の透明なエッジと内部エッジを検出するとともに分割する工程を含む、３Ｄランドマークの処理方法を含む。フォトリアリスティックなデータ中の物体の透明でないエッジ、内部でないエッジ、および、分割したエッジは、完全なハーフエッジ構造（Ｃｏｍｐｌｅｔｅ Ｈａｌｆ Ｅｄｇｅ Ｓｔｒｕｃｔｕｒｅ）を構築するために使用される。完全なハーフエッジ構造における各々のエッジは、廃棄されるか、視点が独立したエッジとしてマークされるか、または、視点が依存したエッジとしてマークされる。完全なハーフエッジ構造の下部構造が特定される。下部構造の少なくとも１つのマーキングは、下部構造の種類に基づいて更新される。完全なハーフエッジ構造におけるエッジの余分なものは統合され、それによって、オンラインレンダリングのためのＮＰＲエッジの最後の組（ｆｉｎａｌ ｓｅｔ）を生成する。最後の組におけるエッジの各々について幅値が計算される。フォトリアリスティックデータ中のフォトリアリスティックなテクスチャは、ノンフォトリアリスティックなテクスチャに変換される。物体のノンフォトリアリスティックな画像は、ノンフォトリアリスティックなテクスチャと、ノンフォトリアリスティックレンダリングされるエッジの最後の組、最後の組におけるエッジの各々のマーキング、および、最後の組におけるエッジの各々の幅値に基づいて生成される。最後の組のエッジの各々は、視点が独立したエッジまたは視点が依存したエッジのいずれかとしてマークされる。
【００１１】
本発明の利点は、ＮＰＲレンダリング技術が、フォトリアリスティックレンダリング技術と比較して、より単純で、かつ、より表現に富んだ視覚化を提供することができるということである。
【００１２】
本発明の別の利点は、既存のフォトリアリスティック３Ｄナビゲーションシステムと比較して、３Ｄ車載ナビゲーション用のＮＰＲ ３Ｄマップがドライバーの方向づけ（ｄｒｉｖｅｒ ｏｒｉｅｎｔａｔｉｏｎ）とランドマークの認識を改善するということである。そもそも人は三次元世界に住んでいるため、３Ｄマップは２Ｄマップと比較してドライバーの方向づけを改善する。しかしながら、フォトリアリスティックな３Ｄレンダリングは、あまりにも多くの詳細を提供することがあり、それはナビゲーション目的に不必要な気晴らしを取り入れかねない。ＮＰＲレンダリングは、識別するために三次元物体の最も重要な特徴（例えば、形状、奥行きの手がかり（ｄｅｐｔｈ ｃｕｅ）、色の変化）を強調すること、および、些細な詳細を省略することによって、この問題を解決する。
【００１３】
本発明のさらに別の利点は、既存のフォトリアリスティック３Ｄナビゲーションシステムと比較して、３Ｄ車載ナビゲーション用のＮＰＲ ３Ｄマップは、マップの更新の必要性を減らすということである。実際の三次元世界の詳細は頻繁に変わることもある。フォトリアリスティック３Ｄマップは、このような変化と同期して一致したマップの頻繁な更新を要求する。このような更新はエンドユーザとデータプロバイダーの両方にとって負担になりかねない。ＮＰＲは三次元世界のより単純かつ表現に富んだ視覚化を提供するため、マップの更新は著しく減ることになる。
【００１４】
本発明のさらなる利点は、既存のフォトリアリスティック３Ｄナビゲーションシステムと比較して、３Ｄの車載ナビゲーション用のＮＰＲ ３Ｄマップが、「フォトリアリスティックな一致」を回避することによって、認識的負荷を軽減するということである。フォトリアリスティック３Ｄマップを使用する際、フォトリアリスティック３Ｄマップがユーザーのフォトリアリズムの期待をかきたてるため、ユーザーはレンダリングされた三次元物体の詳細すべてを実際の世界での詳細と一致させる傾向がある。フォトリアリズムの程度によっては、ユーザーが全ての詳細を一致させる（フォトリアリスティックな一致）のに長い時間がかかることもある。逆に、ＮＰＲ ３Ｄマップが使用される場合、ユーザーは「フォトリアリスティックな一致」を回避することができる。例えば、郵便局が特定の様式（例えば、特定のＮＰＲ効果）で常にレンダリングされる場合、ユーザーは、フォトリアリスティックにレンダリングされた郵便局の外観を考えたり、その外観を実際の郵便局の建物の外観と一致させたりするかわりに、その建物が郵便局であるという事実をすぐに認めて理解することができるであろう。
【００１５】
本発明のさらに別の利点は、既存のフォトリアリスティック３Ｄナビゲーションシステムと比較して、３Ｄの車載ナビゲーション用のＮＰＲ ３Ｄマップがユーザーにとってより訴求力が高いということである。様々なＮＰＲ様式によって提供される芸術的な効果を考慮すると、ＮＰＲ ３Ｄマップは非常に魅力的であるかもしれない。さらに、ユーザーが異なれば好みも異なるため、各々のユーザーは、３Ｄナビゲーションマップ用のお気に入りのレンダリング様式を選択して、それを実施することができるであろう。
【図面の簡単な説明】
【００１６】
本発明の上記および他の特徴および目的と、これらを成し遂げる手法がさらに明らかになるとともに、本発明そのものは、添付の図面と併せて取り込まれた本発明の実施形態の以下の記載を参照することによって、一層よく理解されるであろう。
【図１】本発明のオンラインでのＮＰＲレンダリング用のＮＰＲ様式の３Ｄランドマークに、フォトリアリスティックな３Ｄランドマークをオフラインで変換する１つの実施形態の２つの部品を例証するフローダイアグラムである。
【図２】本発明のアルゴリズムによって特定される異なる種類のエッジを包含している３Ｄランドマークデータの未処理の（ｒａｗ）幾何学的形状の例である。
【図３ａ】本発明の方法によって生成されるＮＰＲ ３Ｄマップレンダリングの１つの例である。
【図３ｂ】本発明の方法によって生成されるＮＰＲ ３Ｄマップレンダリングの別の例である。
【図４】本発明のＮＰＲエッジ同定アルゴリズムの１つの実施形態のフローチャートである。
【図５ａ】長方形の透明なエッジを含むポリゴンメッシュの例である。
【図５ｂ】透明なエッジがレンダリングされない図５ａのメッシュの断片的なレンダリングの例である。
【図５ｃ】透明なエッジがレンダリングされる図５ａのメッシュの断片的なレンダリングの例である。
【図６ａ】透明なエッジの例を例証する。
【図６ｂ】図６ａの透明なエッジを分割した結果を例証する。
【図７ａ】３Ｄランドマークポリゴンメッシュ中の内部エッジを例証する。
【図７ｂ】内部エッジがレンダリングされていない図７ａのメッシュの断片的なレンダリングを示す。
【図７ｃ】内部エッジが実際にレンダリングされる図７ａのメッシュの断片的なレンダリングを示す。
【図８ａ】構造の１つの面が構造の別の面によって部分的に塞がれる例を例証する。
【図８ｂ】分割前に図８ａの部分的に塞がれた面の内部エッジを例証する。
【図８ｃ】分割後に図８ａの部分的に塞がれた面の内部エッジを例証する。
【図９ａ】不規則なトポロジーを有するメッシュポリゴンの例を例証する。
【図９ｂ】図９ａの不規則なトポロジーの２つの境界エッジを例証する。
【図９ｃ】２つの面が１つのエッジを共有する規則的または理想的なトポロジーの例を例証する。
【図１０ａ】ＣＨＥＳ構築前のＣＨＥＳ構造を例証する。
【図１０ｂ】ＣＨＥＳ構築後のＣＨＥＳ構造を例証する。
【図１１ａ】ＣＨＥＳ構築での対のエッジの１つの実施例を例証する。
【図１１ｂ】ＣＨＥＳ構築での対のエッジの別の実施例を例証する。
【図１１ｃ】ＣＨＥＳ構築での対のエッジのさらに別の実施例を例証する。
【図１２】図４のＮＰＲエッジ同定アルゴリズムのマーキング段階の１つの実施形態のフローチャートである。
【図１３ａ】本発明の１つの実施形態による二面角の計算を例証する斜視図である。
【図１３ｂ】図１３ａの実施形態による二面角の計算を例証する平面図である。
【図１４】本発明の１つの実施形態によるマーキング規則の表である。
【図１５ａ】３Ｄランドマークの建物のレンダリングの実施例である。
【図１５ｂ】図１５ａのレンダリングに基づいた３Ｄランドマークのポリゴンメッシュである。
【図１５ｃ】図１５ｂのメッシュに含まれる柱の３Ｄポリゴンメッシュである。
【図１６ａ】２つの隣接したエッジの統合の実例である。
【図１６ｂ】２つの部分的に重なるエッジの統合の実例である。
【図１７】ＮＰＲエッジ用の幅と長さの関係のプロットである。
【図１８】元々の二次元のテクスチャから強化された様々なＮＰＲ様式の実例である。
【図１９】本発明の３Ｄマップレンダリング配置の１つの実施形態のブロック図である。
【図２０】本発明の３Ｄマップレンダリング方法の少なくともいくつかの実施形態で使用するのに適した、大きさを変更できるリアルタイムの３Ｄアニメーション用の漫画様式のレンダリング技術の一例である。
【図２１】本発明の３Ｄマップレンダリング方法の少なくともいくつかの実施形態で使用するのに適したペン画様式のレンダリングの一例である。
【図２２】本発明の３Ｄマップレンダリング方法の少なくともいくつかの実施形態で使用するのに適した鉛筆画風レンダリング（ｐｅｎｃｉｌ ｒｅｎｄｅｒｉｎｇ）の一例である。
【図２３】本発明の３Ｄマップレンダリング方法の少なくともいくつかの実施形態で使用するのに適した漫画様式のレンダリングの一例である。
【図２４】ナビゲーションマップを表示するための、本発明の方法の１つの実施形態のフローチャートである。
【発明を実施するための形態】
【００１７】
対応する参照文字は、複数の図にわたって対応する部分を示している。本明細書で書かれる事例は本発明の実施形態を示しており、幾つかの形状では、以下に開示される実施形態は、包括的となるよう意図されたものではなく、かつ、本発明の範囲を開示された正確な形状に制限するものとして解釈されるように意図されたものでもない。
【００１８】
本発明は、ナビゲーションマップでの三次元物体用の定型化した視覚化を含む、ＮＰＲ ３Ｄマップを使用する３Ｄナビゲーションの方法を提供する。３Ｄナビゲーションマップに表示される三次元物体は、建物、ランドマーク、ＰＯＩ、危険スポット、および、道路を含む。ＮＰＲ ３Ｄマップは、異なる方法で生成される三次元物体のデータに基づいて作成されてもよい。３Ｄデータは、フォトリアリスティックレンダリングのみに適したフォーマット（例えば、フォトリアリスティックなテクスチャを含むポリゴンメッシュ）で、データプロバイダーによって提供されてもよい。この場合、そのようなデータはＮＰＲレンダリングのために強化されてもよい。
【００１９】
ここで図面、特に図１に目を向けると、フォトリアリスティックな３Ｄランドマークを、自動車、船、飛行機などの車両内で使用される本発明のＮＰＲ様式の３Ｄランドマークに変換する方法の１つの実施形態の２つの構成要素が示されている。方法の構成要素の１つは、データ中の重要なエッジが自動的に特定されて、ＮＰＲレンダリングされる、自動的なＮＰＲエッジ特定およびレンダリングである。これはＮＰＲ様式の視覚化に必要とされてもよい。構成要素のもう１つは、データの異なるセクション間の色の対照が誇張されるおよび／または強調されるＮＰＲテクスチャの強化である。フォトリアリスティックな３Ｄランドマークデータに含まれるテクスチャは、フォトリアリズムを改善するように設計されてもよいが、ＮＰＲレンダリングに適していないこともある。画像処理アルゴリズムは、ＮＰＲ様式の外観を有するように、これらのテクスチャの外観を変えるために適用されてもよい。典型的なＮＰＲ様式は、漫画様式、ペン画様式、鉛筆画様式などを含んでもよい。
【００２０】
図２は、様々な種類のエッジ（例えば、表面エッジ、内部エッジ、境界エッジ、透明なエッジなど）を含む、３Ｄランドマークデータの未処理の幾何学的な形状を例証している。図２のこれらの種類のエッジの各々の例は、表面エッジ（３０）、内部エッジ（３２）、境界エッジ（３４）、および、透明なエッジ（３６）を含んでいる。三次元の建物について、典型的なＮＰＲレンダリング様式（ペン画、漫画様式など）は、形状の情報を伝えるために強調される三次元建物の重要なエッジまたはＮＰＲエッジを必要とする。本発明のアルゴリズムは、これらのＮＰＲエッジをうまく特定することができてもよい。ひとたびこれらのエッジが特定されると、ストロークレンダリング（ｓｔｒｏｋｅ ｒｅｎｄｅｒｉｎｇ）技術（例えば、スプライト、ビルボード）は、手描きのＮＰＲ効果を達成するために、これらのエッジをレンダリングすべく使用されてもよい。ひとたび三次元の建物の形状が例証されると、建物のテクスチャは完全なＮＰＲの外観を有するように向上される必要があってもよい。発明のアルゴリズム（「ＮＰＲテクスチャ強化」）の第２の構成要素はこのタスクを完了してもよい。
【００２１】
図３ａと３ｂでは、３Ｄランドマークの外観が本発明の使用によってノンフォトリアリスティックな３Ｄマップに関してどのように強化させられるのかという２つの例が示されている。すなわち、図３ａおよび３ｂでは、発明の方法がノンフォトリアリスティックな３Ｄマップシステムで、ＮＰＲ様式の３Ｄランドマークをレンダリングするために適用されている。同じ３Ｄランドマークは、図３ａおよび３ｂ内の２つの異なる様式でそれぞれレンダリングされる。
【００２２】
発明のＮＰＲエッジ同定アルゴリズムは、元々の未処理の３Ｄランドマークデータをオフラインで処理するために使用されてもよい。アルゴリズムの出力は、ＮＰＲ様式の強化のためにマークされたエッジを含んでもよい。とりわけ、これらのエッジは、オンラインのＮＰＲレンダリングの間に強調されてもよい。加えて、アルゴリズムは、同様に、各々がマークを付けられたＮＰＲエッジのためにいくつかの重要な属性（例えば、エッジ幅など）を事前に計算してもよい。これらの情報の断片はすべて、ランタイムにＮＰＲエッジのレンダリング工程を促進するために使用されてもよい。たとえ重要なエッジ検出（シルエットエッジ（ｓｉｌｈｏｕｅｔｔｅ ｅｄｇｅ）検出を含む）がＮＰＲレンダリングの重要なトピックであっても、三次元の幾何学的形状とトポロジーが完全に規則的な防水性の表面に、たいて焦点が置かれる。本発明のアルゴリズムは、典型的な三次元の建物用のためのこれらの重要なエッジを検知する必要があり、この場合、３Ｄメッシュ構造は通常、明瞭ではないか、規則的ではない。最初に、発明のＮＰＲエッジ同定アルゴリズムは、表面内のエッジまたは構造を備えた三次元の建物データに対処する必要がある。次に、建物の幾何学的形状は、一般的に、壁、屋根などのような別の部品によってモデル化される。結果として、建築のモデルは通常不規則なトポロジーを包含する。最後に、建物のいくつかの追加の幾何学構造は、発明のアルゴリズムにおいて特定の処理を要求する、３Ｄデータ中の分離したテクスチャクワッド（ｔｅｘｔｕｒｅ ｑｕａｄｓ）によって表されることができる。発明のＮＰＲエッジ検出アルゴリズムの別の潜在的な特徴は、ＮＰＲエッジの特定を促進するためにドメイン知識が使用されてもよいということである。例えば、発明のアルゴリズムの入力が三次元の建物に限定されるため、アルゴリズムは、自動的なＮＰＲエッジ検出を促すために建物の下部構造（例えば、柱）を自動的に特定してもよい。
【００２３】
発明のＮＰＲエッジ同定アルゴリズムの１つの実施形態の概観が図４で示される。アルゴリズムは、事前マーキング、マーキング、および、事後マーキングを含む３つの主要な段階を有してもよい。入力はフォトリアリスティックな３Ｄランドマークデータであってもよい。幾何学的形状の一部は、２つのバッファー、すなわち、頂点バッファーとインデックスバッファーに記憶可能である。頂点バッファーは、メッシュの頂点すべてを包含してもよい。インデックスバッファーはメッシュの面（三角形）を構築するために使用されてもよく、これらの面は三次元の建物モデルのトポロジーを表してもよい。事前マーキングの第一段階で、ランドマークの透明なエッジと内部エッジが検知され分割されてもよい。元々のエッジと分割されたエッジを含むランドマークのエッジはすべて、完全なハーフエッジ構造（ＣＨＥＳ）と呼ばれるデータ構造を構築する際に使用されてもよい。
【００２４】
ＣＨＥＳに基づいて、発明のＮＰＲエッジ同定アルゴリズムは、すべてのエッジを繰り返し、マーキング操作を行ってもよい。この工程では、いくつかのエッジが廃棄され、他のものは「ＴＢＤ」または「ＦＩＸ」のいずれかでマークされてもよい。「ＦＩＸ」は視点が独立したＮＰＲエッジを示してもよい。これらのエッジは観察方向に対する建物の方向づけとは無関係に、ランタイムの間にレンダリングされてもよい。「ＴＢＤ」は視点が依存したＮＰＲエッジを示してもよい。これらのエッジがレンダリングされるか否かは、観察者に対する建物の方向づけに左右されることがある。これらのエッジが視点が依存したシルエットエッジになる場合に限り、これらはレンダリングされてもよい。シルエット検査を通過したすべてのＦＩＸエッジ、および、部分的なＴＢＤエッジは、エッジがストローク様式でレンダリング可能となるように、テクスチャビルボードまたはテクスチャスプライトを用いてレンダリングされてもよい。
【００２５】
次に、発明のＮＰＲエッジ同定アルゴリズムは、事後マーキング段階に移ってもよい。この段階では、下部構造がエッジマーキングのための特別な要件を有することがあるため、アルゴリズムはマーキングのために三次元の建物からこれらの下部構造を同定してもよい。１つの実施形態において、柱状のような、および、アーチ道のような下部構造で曲面を表すパラレルエッジが同定され、これらのエッジはＴＢＤラベルを用いてマークされてもよい。最後に、最終的な出力のために余分なＮＰＲエッジを取り除くべく、統合が行われてもよい。各々の同定されたＮＰＲエッジについては、ストロークレンダリング（ｓｔｒｏｋｅ ｒｅｎｄｅｒｉｎｇ）の幅値も同様に計算されてもよい。ＮＰＲエッジ同定アルゴリズムの最終的な出力は、「ＦＩＸ」または「ＴＢＤ」および幅値のラベルでマークされた、同定されたＮＰＲエッジであってもよい。
【００２６】
図５ａ−ｃは、３Ｄランドマークのフォトリアリスティックな視覚化のために透過性を有するテクスチャの典型的な使用を例示する。より具体的に、図５ａは、長方形の透明なエッジを有するポリゴンメッシュを例示する。図５ｂは、透明なエッジがレンダリングされない場合を例示し、図５ｃは、透明なエッジが実際にレンダリングされる場合を例示する。したがって、図５ｂ−ｃは、それぞれ透明なエッジのレンダリングが可能な場合と不可能な場合の効果の比較を提供する。とりわけ、建物がバットレス、アーチ道などを有する際に、透過性を有するテクスチャは三次元の建物のレンダリングで広く使用される。透明なテクスチャは、効率を考慮するために、三角形の数を少なく維持しながら、これらの複雑な構造を示すのにとても適している。しかしながら、三次元の建物のメッシュにおけるいくつかの三角形が、テクスチャマッピングの間に透明な領域によって部分的に覆われることが可能である。その結果、これらのエッジのいくつかは完全にまたは部分的に透明になってもよく、そのようなエッジがＮＰＲエッジとしてたんに特定されるのは不適切なこともある。そうでなければ、図５ａ−ｃによって例示されるように、不正確な形状情報が伝えられてもよい。透明なエッジをマーキング段階に送る前に透明なエッジを検知し分割することは有利である。
【００２７】
透明なエッジを検知および分割するための発明のアルゴリズムの１つの実施形態は、各々のエッジについて以下の工程を含んでいる。
１．各々のセグメントについて、エッジを多くのセグメントとサンプルの高密度のテクセルに分割する。
２．テクセルがそのαチャンネルによって透明かどうかチェックする。
３．透明なテクセルの割合が予め決められた閾値よりも大きい場合、セグメントは透明であると標識される。
４．透明なセグメントをすべて廃棄する。
５．エッジ中のすべてのセグメントが透明ではないと検知された場合、エッジは次の段階へ送られる。
６．そうでない場合、すべての透明でないセグメントを１つまたは複数の新しいエッジへと統合し、それらを次の段階に送る。
【００２８】
図６ａ−ｂは発明のアルゴリズムの１つの実施形態による、透明なエッジの検知および分割を例示する。上記のように、透明なエッジの検知および分割は、事前のマーキング段階中に生じることがある。より具体的に、図６ａは、透明なエッジの例を示し、図６ｂは、図６ａの透明なエッジの分割された結果を示す。透明なエッジは廃棄され、透明でないエッジは次の段階へ送られてもよい。
【００２９】
図４に示されるように、事前のマーキング段階では、透明なエッジの検知と分割のあとに、内部エッジの検知と分割が続いてもよい。図７ａは、３Ｄランドマークメッシュ中の内部エッジを示し、図７ｂは、内部エッジがレンダリングされていない図７ａのメッシュの断片的なレンダリングを示し、図７ｃは、内部エッジが実際にレンダリングされる図７ａのメッシュの断片的なレンダリングを示す。３Ｄランドマークのメッシュは、一般的に多くの内部エッジを包含している。内部エッジがＮＰＲエッジとしてレンダリングされる場合、図７ｃは、視覚アーチファクト（ｖｉｓｕａｌｉｚａｔｉｏｎ ａｒｔｉｆａｃｔｓ）の例を示す。いずれのエッジもフォトリアリスティックな視覚化のためにレンダリングされたり、強調されたりしないため、フォトリアリスティックなレンダリングの効果は影響を受けない。しかし、定型化した視覚化のためにエッジを強調することができる場合、内部エッジはＮＰＲレンダリングに影響することがある。結果として、内部エッジを検知および分割し、目に見える部分のみをマーキング段階に送ることは有利なことがある。
【００３０】
内部エッジを検知および分割するための発明のアルゴリズムの１つの実施形態は、各々のエッジについて以下の工程を含んでいる。
１．エッジを多くのセグメントへと分割する。
２．メッシュの中心からエンドポイントまで光線を構築することによって、セグメントの各エンドポイントについて可視性をテストする。光線がエンドポイントに触れた後にメッシュの任意の面と交差する場合、エンドポイントは目に見えないものとして認識される。
３．２つのエンドポイントのいずれかが目に見えない場合、セグメントは目に見えない。
４．目に見えないセグメントをすべて廃棄する。
５．すべてのセグメントが目に見えると検知される場合、エッジは次の段階へ送られる。
６．そうでない場合、すべての目に見えるセグメントを新しいエッジに統合し、次の段階に送る。
【００３１】
図８ａ−ｃは、事前のマーキング段階で内部エッジを検知および分割した結果を示す。エッジの目に見えないセグメントは廃棄され、目に見えるセグメントは次の段階へ送られる。より具体的には、面０および面１は、レンダリングされる構造の２つの面であってもよい。図８ａで示されるように、破線によって描かれた面１の一部は面０によって塞がれる。少なくとも部分的に塞がれるか隠される図８ａ中の面１のエッジは、「内部エッジ」と呼ばれ、図８ｂでは点線で参照番号（３８ａ）として描かれる。図８ｂは分割前の内部エッジ（３８ａ）を示し、図８ｃは、分割後の内部エッジ（３８ｂ）を示す。
【００３２】
完全なハーフエッジ構造（ＣＨＥＳ）を構築する事前マーキング段階の最終段階が、図９ａ−ｃでより詳細に記載されてもよい。３Ｄモデル中の山と谷は、人々が形状情報を理解するための重要なてがかりとなることもある。ノンフォトリアリスティックレンダリングでは、山と谷にそったエッジは、通常、重要なエッジと見なされる。それらのエッジを同定するために、ほとんどの既存のアルゴリズムは、各々のエッジの２つの隣接する面の間の二面角の値をチェックする。通常の幾何学的形状の表面については、エッジの２つの隣接する面は、ハーフエッジデータ構造を構築することによって容易に見つけられる。本発明では、建物の幾何学的形状が一般的に壁、屋根、柱などを含む別の部品によってモデル化されるため、建物のトポロジーは全く不規則になることがある。図９ａ−ｃは、２つの視覚的に隣接する面が１以上のエッジを共有する例を示す。あるいは、１つのエッジは２つ以上の隣接する面を有する。その結果、従来のハーフエッジ構造はこれらのケースを扱うために拡張（ａｕｇｍｅｎｔ）されてもよく、そのような拡張したデータ構造はＣＨＥＳと呼ばれてもいい。より具体的には、図９ａは、不規則なトポロジーを有するメッシュポリゴンの例を示し、図９ｂは、図９ａの不規則なトポロジーの２つの境界エッジを示し、図９ｃは、２つの面が１つのエッジを共有する規則的または理想的なトポロジーの例を示す。
【００３３】
３ＤランドマークについてのＣＨＥＳを構築するための発明のアルゴリズムの１つの実施形態は、以下の工程を含んでいる。
Ａ．従来のハーフエッジデータ構造を構築する。
Ｂ．各々のエッジについて、
１．エッジの境界エッジペアを測定する。境界エッジは、図１０ａのエッジ（４０）またはエッジ（４２）のような、たった１つの隣接した面を有するエッジである。境界エッジペアは、図１０ａのエッジ（４０）またはエッジ（４２）のような、互いに「触れる」２つの境界エッジを包含している。境界エッジペアは下記条件を満たしてもよい。
ａ．両方の２つのエッジが境界エッジである。
ｂ．２つのエッジが互いに対して平行である。したがって、図１１ａのエッジ（４４）およびエッジ（４６）は、フィルタ処理が施される。
ｃ．２つのエッジは互いに接近している。したがって、図１１ｂで示された場合のエッジ（４８）およびエッジ（５０）はフィルタ処理が施される。
ｄ．２つのエッジは重ねられなければならない。したがって、図１１ｃで示された場合のエッジ（５２）およびエッジ（５４）はフィルタ処理が施される。
２．境界エッジの隣接する面を１つの群に統合する。エッジの１つに隣接する任意の面は両方のエッジによって参照される。
【００３４】
ひとたびＣＨＥＳが構築されると、エッジに隣接する面はすべてエッジの隣接する面の群に加えられる。図１０ａは、ＣＨＥＳを構築する前のＣＨＥＳ構造を示す。エッジ（４０）は三角形の面（５６）につなげられ、エッジ（４２）は三角形の面（５８）につなげられる。図１０ｂは、ＣＨＥＳを構築した後のＣＨＥＳ構造を示す。エッジ（４０）は両方の三角形の面（５６）、（５８）につなげられ、エッジ（４２）も両方の三角形の面（５６）および（５８）につなげられる。
【００３５】
図１２は、図４のＮＰＲエッジ同定アルゴリズムのマーキング段階を要約したフローチャートである。
ＣＨＥＳに基づいて、いくつかの試験動作が終わるまで、各々の対象エッジのラベルは測定されない（工程１２０２）。最初に、各々のエッジの隣接する面の数がチェックされる（工程１２０４）。群に１つの面しかない場合、エッジは境界エッジであり、そのラベルは「ＦＩＸ」としてマークされる（工程１２０６）。しかしながら、群に２つの隣接した面がある場合、エッジの二面角は、以下の方程式（１）を用いて、これらの２つの面の法線（ｎｏｒｍａｌ）に基づいて計算される（工程１２０８）
【００３６】
【数１】
【００３７】
図１３ａ−ｂは、２つの面に基づいた二面角を計算する方法の１つの実施形態を示す。面ｆ０およびｆ１の法線は、ｎ０とｎ１とそれぞれ表される。
【００３８】
群に２以上の面がある場合、２つの面ごとの最小の二面角は、エッジの二面角として選択される（工程１２１０）。各々のエッジの二面角および配向に基づいて、エッジのラベルは図１４の表中の規則を適用することによって測定可能である（工程１２１２）。他のエッジと比較して、三次元の建物の垂直および水平方向のエッジは、３Ｄ形状情報を伝えるのにより重要である。したがって、図１４に示されるように、特定のマーキング規則またはパラメータが異なる種類のエッジに使用されてもよい。図１４の表によれば、「ＦＩＸ」とマークされない条件と「ＴＢＤ」とマークされない条件がいずれも満たされない場合、エッジは、上記のように「ＦＩＸ」（工程１２０６）または「ＴＢＤ」（工程１２１４）として、または、「ＳＫＩＰ」（工程１２１６）として、マークされてもよい。
【００３９】
図４に示されるように、事後のマーキング段階は、マーキングの更新のために建物の下部構造を特定することを含んでもよい。図１５ａは３Ｄランドマーク建物の柱状構造のレンダリングを示す。複数の柱（６０）が示され、そのような柱は３Ｄランドマーク建物の共通の下部構造である。図１５ｂは図１５ａのレンダリングに基づいた３Ｄランドマークのポリゴンメッシュであり、図１５ｃは図１５ｂのメッシュに含まれる柱の３Ｄポリゴンメッシュである。柱中のすべての垂直エッジのなかで、現在の視点下でシルエットエッジになるもののみがレンダリング中に強調される。例えば、図１５ｃで垂直エッジ（６２ａ−ｂ）は、柱の外形を形成するシルエットエッジである。結果として、これらのエッジはすべて「ＴＢＤ」と標識される。典型的な建物の下部構造を自動的に特定し、下部構造の種類に基づいてマーキングを更新することが必要である。柱を発見するという問題は、クラスタ化問題として公式化される。Ｋ平均アルゴリズムのような典型的なクラスタ化アルゴリズムを適用するために、類似性測定基準（ａ ｓｉｍｉｌａｒｉｔｙ ｍｅｔｒｉｃ）が２つの垂直な柱エッジ間の距離を定量化すべく定義されてもよい。距離測定基準は、２つの線分の距離と長さの差を含んでもよい。クラスタ化の後、すべての３Ｄランドマークの垂直エッジは、個々のエッジまたは柱を表す異なる群にクラスタ化されてもよい。
【００４０】
統合と明瞭化は、効率の目的で事後のマーキング段階の重要な工程である。マーキング段階中に検知されるいくつかのＮＰＲエッジは、互いに対して平行かつ隣接してもよい。いくつかのＮＰＲエッジは完全にまたは部分的に互いに重複してもよい。これらのエッジについては、エッジは個々にレンダリングされるか、または、統合後に１つの単一エッジとしてレンダリングされてもよい。後者の選択の方が好ましい。というのも、レンダリングされるＮＰＲエッジの数を減らしながら、同じ視覚化効果が達成されるためである。したがって、レンダリング性能は劇的に改善される。
【００４１】
図１６ａ−ｂで例示されるように、下記条件をすべて満たすエッジが統合されてもよい。
１）エッジは「ＦＩＸ」ラベルで前もってマークされる。
２）エッジは、隣接した場合を含めて、互いに完全にまたは部分的に重なる。
【００４２】
統合の後、明瞭化が行われてもよい。ランドマークモデルの縮尺と比較して、いくつかのＮＰＲエッジは比較的短すぎてもよい。短いエッジの除去は、ＮＰＲレンダリングの視覚的な質をほとんど変更しないが、レンダリング性能を向上させることができる。したがって、１つの実施形態では、長さがその閾値 ＳＨＯＲＴ＿ＬＥＮ＿ＳＣＡＬＥ×ＭＯＤＥＬ＿ＳＣＡＬＥ より短い任意のＮＰＲエッジが取り除かれてもよく、ＳＨＯＲＴ＿ＬＥＮ＿ＳＣＡＬＥ×ＭＯＤＥＬ＿ＳＣＡＬＥ は、予め決められたパラメータであり、ＭＯＤＥＬ＿ＳＣＡＬＥは以下の式に基づいて計算される：
ＭＯＤＥＬ＿ＳＣＡＬＥ＝０．５×（（ＢＬ＋ＢＷ＋ＢＨ）−ｍｉｎ（ＢＬ、ＢＷ、ＢＨ））
式中、ＢＬ、ＢＷおよびＢＨは、モデル全体の境界ボックスの長さ、幅、および、高さを表す。
【００４３】
事後マーキング段階の次の工程はＮＰＲエッジの幅の計算であってもよい。前の段階で検知されたＮＰＲエッジは、ビルボード（テクスチャがマップされた長方形）を用いることによってレンダリングされてもよく、ビルボードの幅は計算される必要がある。この工程では、テクスチャがマップされたビルボード（ストロークを表す）は、基礎となるＮＰＲエッジのまわりで回転することを許されてもよい。ビルボードの長さが基礎となるＮＰＲエッジの長さと等しく、その一方で、ストロークの手動による線描効果が達成可能となるように、幅が注意深く計算される必要がある。ビルボードの幅は２つの観察に基づいて測定されてもよい。最初に、ビルボードの幅はその長さとともに増加しなければならない。結果として、幅を計算する関数は、長さの関数の単調な増加関数でなければならない。次に、ビルボードの幅が非線形的な手法で増大するのが望ましい。ＮＰＲエッジの長さがより短い場合、ビルボードの幅は急激に増えなければならず、ＮＰＲエッジの長さが大きい場合、ビルボードの幅は徐々に増える。結果として、短いエッジは知覚可能なストローク幅を依然として有してもよく、その一方で、長いエッジはレンダリングの間に非常に大きな幅値を割り当てられないことがある。上記の２つの観察に基づいて、二相の幅の関数が設計されてもよい。図１７のプロットは、正規化した幅と正規化した長さの関係を示しており、以下の方程式によってさらに記載される。
ＮｏｒｍａｌｉｚｅｄＬｅｎｇｔｈ＝Ｌｅｎｇｔｈ／ＭｏｄｅｌＳｃａｌｅ
ＮｏｒｍａｌｉｚｅｄＷｉｄｔｈ＝ＭｉｎｉｍａｌＮｏｒｍａｌｉｚｅｄＷｉｄｔｈ＋ＳｐａｎＦａｓｔ×（１−ｅｘｐ（−ＫＦａｓt×ＮｏｒｍａｌｉｚｅｄＬｅｎｇｔｈ））＋ＳｐａｎＳｌｏｗ×（１−ｅｘｐ（−ＫＳｌｏｗ×ＮｏｒｍａｌｉｚｅｄＬｅｎｇｔｈ）
Ｗｉｄｔｈ＝ＮｏｒｍａｌｉｚｅｄＷｉｄｔｈ×ＭｏｄｅｌＳｃａｌｅ
式中、
ＳｐａｎＦａｓｔ＝（ＭａｘＮｏｒｍａｌｉｚｅｄＷｉｄｔｈ−ＭｉｎＮｏｒｍａｌｉｚｅｄＷｉｄｔｈ）×ｐｅｒｃｅｎｔａｇｅＦａｓｔ
ＳｐａｎＳｌｏｗ＝（ＭａｘＮｏｒｍａｌｉｚｅｄＷｉｄｔｈ−ＭｉｎＮｏｒｍａｌｉｚｅｄＷｉｄｔｈ）×（１−ｐｅｒｃｅｎｔａｇｅＦａｓｔ）
ＭｉｎｉｍａｌＮｏｒｍａｌｉｚｅｄＷｉｄｔｈとＭａｘｉｍａｌＮｏｒｍａｌｉｚｅｄＷｉｄｔｈは、（ＭｏｄｅｌＳｃａｌｅに対する）ＮＰＲエッジの正規化した幅の下界と上界を制御する調整可能パラメータである。ＰｅｒｃｅｎｔａｇｅＦａｓｔは急激に増える領域と徐々に増える領域とを分離するパラメータである。ＫＦａｓｔとＫＳｌｏｗは２つの速度定数である。急激にかつ緩慢に半正規化された長さ（Ｆａｓｔ ｈａｌｄ ａｎｄ ｓｌｏｗ ｈａｌｆ ｎｏｒｍａｌｉｚｅｄ ｌｅｎｇｔｈ）は、ｌｎ（２）／Ｋとして計算されてもよい。
【００４４】
発明の方法の第１の構成要素（ＮＰＲレンダリングに関する重要なエッジの自動特定）が完了すると、第２の構成要素、ＮＰＲテクスチャの強化が行われてもよい。図１８は、元々の二次元のテクスチャから強化された異なるＮＰＲ様式を示す。ＮＰＲテクスチャの強化は、未処理のランドマークデータ中の元々のフォトリアリスティックなテクスチャを入力として受け取るために、かつ、それを異なるＮＰＲ様式のテクスチャに変換するために定義されてもよい。様々な標準的な画像処理技術はこのタスクを遂行するために使用されてもよい。第三者の画像処理ソフトウェア（例えば、Ａｄｏｂｅ（登録商標）Ｐｈｏｔｏｓｈｏｐ（登録商標））もこの目的に使用可能である。
【００４５】
上記の本発明はいくつかの新規な特徴を含んでいる。本発明は、ノンフォトリアリスティックな３Ｄマップにフォトリアリスティックな３Ｄランドマークを再使用する方法を提供してもよい。本発明は、防水表面以外の様々な構造を含む三次元の建物データからＮＰＲエッジを自動的に同定することができる（例えば、下位アルゴリズムと、データ編成方法の完全なハーフエッジ構造ＣＨＥＳとのセットからなる）アルゴリズムを提供してもよい。
【００４６】
ここで、図１９には、自動車、船、飛行機などの車両に関連する本発明の３Ｄマップレンダリング配置（１０）の１つの実施形態が示されている。すなわち、配置（１０）は車に搭載して取り付けられてもよい。
【００４７】
配置（１０）は、事前に処理された３Ｄフォトリアリスティックなマップデータソース（１４）、ＮＰＲ ３Ｄマップエンジン（１６）、および、ユーザーインタフェース（２２）を含んでもよい。フォトリアリスティックな３Ｄマップデータソース（１２）は、ＮＰＲ ３Ｄマップエンジン処理構成要素（１８）によって事前に処理され、事前に処理された３Ｄマップデータソース（１４）となる。事前に処理された３Ｄマップデータソースは、コンパクトディスク（ＣＤ）または他の記憶装置の形状であってもよい。あるいは、３Ｄマップデータは、各々がそれぞれの３Ｄマップレンダリング配置（１０）を有する多くの車両に、中央の送信機（図示せず）によって無線送信されてもよい。このような無線送信は、ＮＰＲ３Ｄマップエンジンレンダリング構成要素（２０）によって受け取られてもよい。
【００４８】
事前に処理された３Ｄマップデータソース（１４）は、リアルタイムで車両のグローバルな位置座標を測定するための全地球測位システム（ＧＰＳ）モジュール（図示せず）も含んでよい。車両の現在の位置に基づいて、車両内の人々にとって興味深い対応する３Ｄマップデータが特定され、ＮＰＲ３Ｄマップエンジン（１６）のオンラインレンダリング構成要素（２０）が提供される。
【００４９】
ＮＰＲ ３Ｄエンジン（１６）は標準的な電子工程を含み、２つの構成要素、オフライン処理構成要素（１８）とオンラインレンダリング構成要素（２０）からなる。処理構成要素（１８）は、ソース（１２）からのフォトリアリスティックな３Ｄマップデータをオフラインで事前に処理してもよい。レンダリング構成要素（２０）は、事前に処理された３Ｄマップデータソース（１４）からノンフォトリアリスティックな画像をオンラインで生成してもよい。ノンフォトリアリスティックな画像は、漫画の、鉛筆画の、ペン画の、イラストの、油絵の効果、および、他の絵画様式などの様々な様式であってもよい。ＮＰＲレンダリングは、物体の表面および物体の典型的なまたは周知の特徴を描いてもよい。
【００５０】
図２０乃至２３は、先行技術のナビゲーション領域に適用されていない様々なＮＰＲ様式を示す。図２０乃至２３のこれらの様式の各々は、本発明のＮＰＲ ３Ｄマップレンダリング方法とともに使用するのに適している。さらに具体的に、図２０は、大きさを変更できるリアルタイムの３Ｄアニメーションのための漫画様式の定型化したレンダリング技術を示し、図２１はペン画のレンダリングを示し、図２２はリアルタイムの鉛筆画風レンダリングを示し、そして、図２３は本発明によってレンダリングされるＮＰＲ ３Ｄマップの一例である漫画様式のＮＰＲ ３Ｄマップを示す。
【００５１】
１つの実施形態では、ユーザーは、図２３に描かれる画角を、地表レベルまたはそれより高い任意の視角または任意の位置に調節することができる。例えば、ユーザーは、建物のいずれかまたはすべてのまわりの３６０度のアークに沿った視界のほとんど無限の数から選んでもよい。さらに、ユーザーは、垂直面に沿った任意の下向きの視角を選んでもよい。
【００５２】
ユーザーインタフェース（２２）は、車両のダッシュボードに配置されてもよく、表示スクリーン（２４）および制御装置（２６）を含んでもよい。表示スクリーン（２４）は、スクリーンまたはモニターに表示される情報または内容を制御するためのプロセッサーとメモリを含んでもよい。一般的に、表示スクリーン（２４）は、レンダリング構成要素（２０）から受け取ったＮＰＲ ３Ｄ画像データを示すか、または、このデータを描く。
【００５３】
制御装置（２６）は、ダイヤル、ノブ、プッシュボタン一式、ジョイスティック、マイクロホン、タッチインタフェース、または、上記のものの任意の組み合わせの形状であってもよい。ユーザーは、エンジン（１６）にフィードバック（２８）を提供するために制御装置（２６）を使用してもよい。フィードバック（２８）は、別の画像データ一式（例えば、別の場面、物体、または、物体一式を描く画像データ）を作るようエンジン（１６）に指示してもよい。あるいは、フィードバック（２８）は、現在の画像データ一式が見える視角を変更するようにエンジン（１６）に指示してもよい。視角は、周囲環境の頭上の鳥瞰図から、地表レベルまたは地上レベルから建物または他のランドマークを見上げる角度まで、様々である。
【００５４】
ナビゲーションマップを表示するための本発明の方法（２４００）の実施形態が図２４で示されている。第１の工程（２４０２）において、フォトリアリスティックな三次元データが事前に処理され記憶される。
【００５５】
次の工程（２４０４）では、車両の位置が自動的に測定される。例えば、図１９の配置は、配置に関連する車両の現在の位置（それはグローバル座標で表現されてもよい）を、自動的かつ連続的に更新するＧＰＳまたは他の装置を含んでもよい。
【００５６】
次に、工程（２４０６）では、車両の地理的な領域内に配されるランドマークに関連した、事前に処理された三次元データの一部が特定される。例えば、工程（２４０４）で測定された車両位置に基づいて、車両付近に関連するマップデータがＣＤなどの記憶装置から検索されてもよい。あるいは、車両付近に関連するマップデータは、マップデータのセントラル・レポジトリから無線で受け取られてもよい。どのように受け取られ、および／または、特定されるかにかかわらず、マップデータは、車両付近内の建物と自然のランドマークの形状、寸法、色、および、窓を記載した３Ｄデータを含んでもよい。
【００５７】
次に、工程（２４０８）では、ノンフォトリアリスティックな画像は、事前に処理された３Ｄマップデータの特定された部分に基づいてレンダリングされる。図２０乃至２３は、画像がレンダリングされるノンフォトリアリスティック様式の例を示す。
【００５８】
最終的な工程（２４１０）では、ノンフォトリアリスティックな画像は、車両内のユーザーに電子的に表示される。１つの実施形態では、エンジン（１６）によってレンダリングされるＮＰＲ画像は、ユーザーインタフェース（２２）のスクリーン（２４）に表示される。
【００５９】
この発明は例示的な設計を有するものとして記載されてきたが、本発明はこの開示の精神と範囲内でさらに修正されてもよい。したがって、この出願は一般的な原則を用いて本発明の任意の変化、用途、または、適応を対象にするように意図されている。
【技術分野】
【０００１】
１．発明の分野
本発明は電子ナビゲーションマップに関し、より具体的には、電子ナビゲーションマップ用に画像をレンダリングすることに関する。
【背景技術】
【０００２】
２．関連技術の詳細
ナビゲーションマップは、建物、地勢、および、興味のある場所（ＰＯＩ）、例えば、博物館、レストラン、公園およびショッピングセンターを含むランドマークを視覚的に強調するため、よく知らない都市を訪れる人にとって必要不可欠なリソースである。ほとんどの車載の、および、携帯性のナビゲーションデバイス（ＰＮＤ）は、二次元（２Ｄ）でこれらのランドマークを視覚化するために２Ｄのナビゲーションマップに依存しているが、三次元（３Ｄ）の車載ナビゲーションシステムが台頭しつつある。ほとんどのこれらの３Ｄナビゲーションシステムは、三次元のランドマークを視覚化するために、フォトリアリスティック（ｐｈｏｔｏｒｅａｌｉｓｔｉｃ）レンダリング技術を使用している。この視覚化体系では、正確な幾何学モデルと詳細なフォトリアリスティックの建物テクスチャが必要である。これらのシステムは、このようなレンダリングされた三次元の建物、道または他の対象の外観が、実際の建物、道または他の対象の外観と可能な限り一致することを必要とする。したがって、フロントガラス越しに実際の三次元の建物を見ると、ドライバーはフォトリアリスティックな一致（ｐｈｏｔｏｒｅａｌｉｓｔｉｃ ｍａｔｃｈ）を行うことで、三次元のランドマークを認識することができる。一方では、２Ｄナビゲーションシステムは、我々の三次元の世界の詳細をほとんどなにも視覚化しない。他方で、フォトリアリスティックな３Ｄマップに基づくナビゲーションシステムは、我々の三次元世界のあらゆる詳細を視覚化しようとするが、これは必要なくすることができる。
【０００３】
ほとんどのデータプロバイダー（例えば、Ｔｅｌｅ Ａｔｌａｓ）は、直接的なフォトリアリスティックレンダリングに適切な３Ｄマップ要素データ（例えば、３Ｄランドマーク）のみを提供する。より具体的には、ほとんどの３Ｄマップ要素データは、フォトリアリスティックなテクスチャによって取り付けられるポリゴンメッシュの形で提供される。なんの修正もなされない場合、これらのデータは直接的なフォトリアリスティックレンダリングにのみ使用することができる。したがって、これらのデータは直接的なノンフォトリアリスティックレンダリング（ｎｏｎ−ｐｈｏｔｏｒｅａｌｉｓｔｉｃ）（ＮＰＲ）には適していない。しかしながら、ＮＰＲは、ＮＰＲが、ユーザーが観察する現実視界の眺めにレンダリングを容易に一致させることができるような正確な（詳細を必要としない）方法で画像を示してもよく、ＮＰＲレンダリングをもたらすために低レベルの計算ソースしか必要とされないという点で、フォトリアリスティックレンダリング以上に有益である。
【０００４】
先行技術で開示も示唆もされていないものは、フォトリアリスティックレンダリングのために意図される従来の市販の３Ｄマップ要素データを用いることによって、ナビゲーションマップ上に、建物、ランドマーク、および、他の３Ｄ物体のＮＰＲレンダリングを提供する方法である。
【発明の概要】
【発明が解決しようとする課題】
【０００５】
本発明は、ノンフォトリアリスティック（ＮＰＲ）または表現レンダリング技術を用いることによって、ナビゲーションのために重要な詳細のみを視覚化し強調することで、伝統的な２Ｄナビゲーションマップとフォトリアリスティック３Ｄマップの間のギャップを埋める３Ｄナビゲーションシステムを提供する。本発明によれば、利用可能なフォトリアリスティック３Ｄランドマークデータは、ＮＰＲ ３Ｄナビゲーションマップでの表現に富んだ視覚化に再度使用されてもよい。より具体的には、フォトリアリスティック３Ｄランドマークデータは、最初にオフラインで処理されてもよく、その後、ノンフォトリアリスティックレンダリングは高性能を達成するためにランタイムで適用されてもよい。
【課題を解決するための手段】
【０００６】
フォトリアリスティック３Ｄランドマークデータの処理がコンピュータで集約されるため、フォトリアリスティックなデータの事前処理はオフラインで行なわれてもよい。言い換えれば、フォトリアリスティックなデータはすべて、ＮＰＲディスプレイのレンダリングよりも先に受け取られてもよい。さらに具体的に、事前処理はフォトリアリスティックなデータ上で行なわれてもよく、ＮＰＲ情報（ＮＰＲエッジおよびＮＰＲテクスチャ）を包含する事前に処理された３Ｄマップデータは、ユーザーに対する画像のレンダリングよりも先に準備されてもよい。その後、運転中に、事前に処理された３Ｄマップデータは、すでに特定されたエッジと、すでに変換されたテクスチャとを含んで受け取られてもよい。運転中に、ユーザーは、ディスク、ＣＤ、記憶装置、または、インターネットからこのデータを受け取ってもよい。もちろん、いくつかの特定のレンダリング処理は、運転手に対してＮＰＲ画像を表示するためのＮＰＲ情報を備えたデータを準備するために、リアルタイムで行なわれてもよい。
【０００７】
同様に、別の実施形態では、フォトリアリスティックデータは運転中に受け取られることが可能であり、および、ノンフォトリアリスティックデータの変換が運転中に行われることも可能である。しかしながら、フォトリアリスティックデータの処理はコンピュータで集約されるため、多くの処理ハードウェアが要求されることがある。
【０００８】
本発明は、その１つの形状において、オフラインでフォトリアリスティックな三次元データを事前に処理する工程を含む、ナビゲーションマップを表示する方法を含む。車両の位置はオンラインで自動的に測定される。地理的な領域内に配置される物体に関連する事前に処理されたフォトリアリスティックな三次元データの一部が特定される。地理的な領域は、車両の位置を含んでいる。ノンフォトリアリスティックな画像は、事前に処理されたデータの特定された一部に基づいてレンダリングされる。ノンフォトリアリスティックな画像は、車両内のユーザーに電子的に表示される。
【０００９】
本発明は、その別の形状において、車両の位置を自動的に測定する工程を含む、ナビゲーションマップを表示する方法を含む。フォトリアリスティックな三次元データが受け取られる。データは、地理的な領域内に配置される物体に関連している。地理的な領域は、車両の位置を含んでいる。フォトリアリスティックなデータ中の物体のエッジは、自動的に特定され、ノンフォトリアリスティックレンダリングされる。フォトリアリスティックなデータ中のフォトリアリスティックなテクスチャは、ノンフォトリアリスティックなテクスチャに変換される。物体のノンフォトリアリスティックな画像は、ノンフォトリアリスティックなテクスチャ、マークを付けたエッジ、データ中のエッジの各々の幅値に基づいて生成される。ノンフォトリアリスティックな画像は、車両内のユーザーに電子的に表示される。
【００１０】
本発明は、さらに別の形状で、物体に関連するフォトリアリスティックな三次元データ中の物体の透明なエッジと内部エッジを検出するとともに分割する工程を含む、３Ｄランドマークの処理方法を含む。フォトリアリスティックなデータ中の物体の透明でないエッジ、内部でないエッジ、および、分割したエッジは、完全なハーフエッジ構造（Ｃｏｍｐｌｅｔｅ Ｈａｌｆ Ｅｄｇｅ Ｓｔｒｕｃｔｕｒｅ）を構築するために使用される。完全なハーフエッジ構造における各々のエッジは、廃棄されるか、視点が独立したエッジとしてマークされるか、または、視点が依存したエッジとしてマークされる。完全なハーフエッジ構造の下部構造が特定される。下部構造の少なくとも１つのマーキングは、下部構造の種類に基づいて更新される。完全なハーフエッジ構造におけるエッジの余分なものは統合され、それによって、オンラインレンダリングのためのＮＰＲエッジの最後の組（ｆｉｎａｌ ｓｅｔ）を生成する。最後の組におけるエッジの各々について幅値が計算される。フォトリアリスティックデータ中のフォトリアリスティックなテクスチャは、ノンフォトリアリスティックなテクスチャに変換される。物体のノンフォトリアリスティックな画像は、ノンフォトリアリスティックなテクスチャと、ノンフォトリアリスティックレンダリングされるエッジの最後の組、最後の組におけるエッジの各々のマーキング、および、最後の組におけるエッジの各々の幅値に基づいて生成される。最後の組のエッジの各々は、視点が独立したエッジまたは視点が依存したエッジのいずれかとしてマークされる。
【００１１】
本発明の利点は、ＮＰＲレンダリング技術が、フォトリアリスティックレンダリング技術と比較して、より単純で、かつ、より表現に富んだ視覚化を提供することができるということである。
【００１２】
本発明の別の利点は、既存のフォトリアリスティック３Ｄナビゲーションシステムと比較して、３Ｄ車載ナビゲーション用のＮＰＲ ３Ｄマップがドライバーの方向づけ（ｄｒｉｖｅｒ ｏｒｉｅｎｔａｔｉｏｎ）とランドマークの認識を改善するということである。そもそも人は三次元世界に住んでいるため、３Ｄマップは２Ｄマップと比較してドライバーの方向づけを改善する。しかしながら、フォトリアリスティックな３Ｄレンダリングは、あまりにも多くの詳細を提供することがあり、それはナビゲーション目的に不必要な気晴らしを取り入れかねない。ＮＰＲレンダリングは、識別するために三次元物体の最も重要な特徴（例えば、形状、奥行きの手がかり（ｄｅｐｔｈ ｃｕｅ）、色の変化）を強調すること、および、些細な詳細を省略することによって、この問題を解決する。
【００１３】
本発明のさらに別の利点は、既存のフォトリアリスティック３Ｄナビゲーションシステムと比較して、３Ｄ車載ナビゲーション用のＮＰＲ ３Ｄマップは、マップの更新の必要性を減らすということである。実際の三次元世界の詳細は頻繁に変わることもある。フォトリアリスティック３Ｄマップは、このような変化と同期して一致したマップの頻繁な更新を要求する。このような更新はエンドユーザとデータプロバイダーの両方にとって負担になりかねない。ＮＰＲは三次元世界のより単純かつ表現に富んだ視覚化を提供するため、マップの更新は著しく減ることになる。
【００１４】
本発明のさらなる利点は、既存のフォトリアリスティック３Ｄナビゲーションシステムと比較して、３Ｄの車載ナビゲーション用のＮＰＲ ３Ｄマップが、「フォトリアリスティックな一致」を回避することによって、認識的負荷を軽減するということである。フォトリアリスティック３Ｄマップを使用する際、フォトリアリスティック３Ｄマップがユーザーのフォトリアリズムの期待をかきたてるため、ユーザーはレンダリングされた三次元物体の詳細すべてを実際の世界での詳細と一致させる傾向がある。フォトリアリズムの程度によっては、ユーザーが全ての詳細を一致させる（フォトリアリスティックな一致）のに長い時間がかかることもある。逆に、ＮＰＲ ３Ｄマップが使用される場合、ユーザーは「フォトリアリスティックな一致」を回避することができる。例えば、郵便局が特定の様式（例えば、特定のＮＰＲ効果）で常にレンダリングされる場合、ユーザーは、フォトリアリスティックにレンダリングされた郵便局の外観を考えたり、その外観を実際の郵便局の建物の外観と一致させたりするかわりに、その建物が郵便局であるという事実をすぐに認めて理解することができるであろう。
【００１５】
本発明のさらに別の利点は、既存のフォトリアリスティック３Ｄナビゲーションシステムと比較して、３Ｄの車載ナビゲーション用のＮＰＲ ３Ｄマップがユーザーにとってより訴求力が高いということである。様々なＮＰＲ様式によって提供される芸術的な効果を考慮すると、ＮＰＲ ３Ｄマップは非常に魅力的であるかもしれない。さらに、ユーザーが異なれば好みも異なるため、各々のユーザーは、３Ｄナビゲーションマップ用のお気に入りのレンダリング様式を選択して、それを実施することができるであろう。
【図面の簡単な説明】
【００１６】
本発明の上記および他の特徴および目的と、これらを成し遂げる手法がさらに明らかになるとともに、本発明そのものは、添付の図面と併せて取り込まれた本発明の実施形態の以下の記載を参照することによって、一層よく理解されるであろう。
【図１】本発明のオンラインでのＮＰＲレンダリング用のＮＰＲ様式の３Ｄランドマークに、フォトリアリスティックな３Ｄランドマークをオフラインで変換する１つの実施形態の２つの部品を例証するフローダイアグラムである。
【図２】本発明のアルゴリズムによって特定される異なる種類のエッジを包含している３Ｄランドマークデータの未処理の（ｒａｗ）幾何学的形状の例である。
【図３ａ】本発明の方法によって生成されるＮＰＲ ３Ｄマップレンダリングの１つの例である。
【図３ｂ】本発明の方法によって生成されるＮＰＲ ３Ｄマップレンダリングの別の例である。
【図４】本発明のＮＰＲエッジ同定アルゴリズムの１つの実施形態のフローチャートである。
【図５ａ】長方形の透明なエッジを含むポリゴンメッシュの例である。
【図５ｂ】透明なエッジがレンダリングされない図５ａのメッシュの断片的なレンダリングの例である。
【図５ｃ】透明なエッジがレンダリングされる図５ａのメッシュの断片的なレンダリングの例である。
【図６ａ】透明なエッジの例を例証する。
【図６ｂ】図６ａの透明なエッジを分割した結果を例証する。
【図７ａ】３Ｄランドマークポリゴンメッシュ中の内部エッジを例証する。
【図７ｂ】内部エッジがレンダリングされていない図７ａのメッシュの断片的なレンダリングを示す。
【図７ｃ】内部エッジが実際にレンダリングされる図７ａのメッシュの断片的なレンダリングを示す。
【図８ａ】構造の１つの面が構造の別の面によって部分的に塞がれる例を例証する。
【図８ｂ】分割前に図８ａの部分的に塞がれた面の内部エッジを例証する。
【図８ｃ】分割後に図８ａの部分的に塞がれた面の内部エッジを例証する。
【図９ａ】不規則なトポロジーを有するメッシュポリゴンの例を例証する。
【図９ｂ】図９ａの不規則なトポロジーの２つの境界エッジを例証する。
【図９ｃ】２つの面が１つのエッジを共有する規則的または理想的なトポロジーの例を例証する。
【図１０ａ】ＣＨＥＳ構築前のＣＨＥＳ構造を例証する。
【図１０ｂ】ＣＨＥＳ構築後のＣＨＥＳ構造を例証する。
【図１１ａ】ＣＨＥＳ構築での対のエッジの１つの実施例を例証する。
【図１１ｂ】ＣＨＥＳ構築での対のエッジの別の実施例を例証する。
【図１１ｃ】ＣＨＥＳ構築での対のエッジのさらに別の実施例を例証する。
【図１２】図４のＮＰＲエッジ同定アルゴリズムのマーキング段階の１つの実施形態のフローチャートである。
【図１３ａ】本発明の１つの実施形態による二面角の計算を例証する斜視図である。
【図１３ｂ】図１３ａの実施形態による二面角の計算を例証する平面図である。
【図１４】本発明の１つの実施形態によるマーキング規則の表である。
【図１５ａ】３Ｄランドマークの建物のレンダリングの実施例である。
【図１５ｂ】図１５ａのレンダリングに基づいた３Ｄランドマークのポリゴンメッシュである。
【図１５ｃ】図１５ｂのメッシュに含まれる柱の３Ｄポリゴンメッシュである。
【図１６ａ】２つの隣接したエッジの統合の実例である。
【図１６ｂ】２つの部分的に重なるエッジの統合の実例である。
【図１７】ＮＰＲエッジ用の幅と長さの関係のプロットである。
【図１８】元々の二次元のテクスチャから強化された様々なＮＰＲ様式の実例である。
【図１９】本発明の３Ｄマップレンダリング配置の１つの実施形態のブロック図である。
【図２０】本発明の３Ｄマップレンダリング方法の少なくともいくつかの実施形態で使用するのに適した、大きさを変更できるリアルタイムの３Ｄアニメーション用の漫画様式のレンダリング技術の一例である。
【図２１】本発明の３Ｄマップレンダリング方法の少なくともいくつかの実施形態で使用するのに適したペン画様式のレンダリングの一例である。
【図２２】本発明の３Ｄマップレンダリング方法の少なくともいくつかの実施形態で使用するのに適した鉛筆画風レンダリング（ｐｅｎｃｉｌ ｒｅｎｄｅｒｉｎｇ）の一例である。
【図２３】本発明の３Ｄマップレンダリング方法の少なくともいくつかの実施形態で使用するのに適した漫画様式のレンダリングの一例である。
【図２４】ナビゲーションマップを表示するための、本発明の方法の１つの実施形態のフローチャートである。
【発明を実施するための形態】
【００１７】
対応する参照文字は、複数の図にわたって対応する部分を示している。本明細書で書かれる事例は本発明の実施形態を示しており、幾つかの形状では、以下に開示される実施形態は、包括的となるよう意図されたものではなく、かつ、本発明の範囲を開示された正確な形状に制限するものとして解釈されるように意図されたものでもない。
【００１８】
本発明は、ナビゲーションマップでの三次元物体用の定型化した視覚化を含む、ＮＰＲ ３Ｄマップを使用する３Ｄナビゲーションの方法を提供する。３Ｄナビゲーションマップに表示される三次元物体は、建物、ランドマーク、ＰＯＩ、危険スポット、および、道路を含む。ＮＰＲ ３Ｄマップは、異なる方法で生成される三次元物体のデータに基づいて作成されてもよい。３Ｄデータは、フォトリアリスティックレンダリングのみに適したフォーマット（例えば、フォトリアリスティックなテクスチャを含むポリゴンメッシュ）で、データプロバイダーによって提供されてもよい。この場合、そのようなデータはＮＰＲレンダリングのために強化されてもよい。
【００１９】
ここで図面、特に図１に目を向けると、フォトリアリスティックな３Ｄランドマークを、自動車、船、飛行機などの車両内で使用される本発明のＮＰＲ様式の３Ｄランドマークに変換する方法の１つの実施形態の２つの構成要素が示されている。方法の構成要素の１つは、データ中の重要なエッジが自動的に特定されて、ＮＰＲレンダリングされる、自動的なＮＰＲエッジ特定およびレンダリングである。これはＮＰＲ様式の視覚化に必要とされてもよい。構成要素のもう１つは、データの異なるセクション間の色の対照が誇張されるおよび／または強調されるＮＰＲテクスチャの強化である。フォトリアリスティックな３Ｄランドマークデータに含まれるテクスチャは、フォトリアリズムを改善するように設計されてもよいが、ＮＰＲレンダリングに適していないこともある。画像処理アルゴリズムは、ＮＰＲ様式の外観を有するように、これらのテクスチャの外観を変えるために適用されてもよい。典型的なＮＰＲ様式は、漫画様式、ペン画様式、鉛筆画様式などを含んでもよい。
【００２０】
図２は、様々な種類のエッジ（例えば、表面エッジ、内部エッジ、境界エッジ、透明なエッジなど）を含む、３Ｄランドマークデータの未処理の幾何学的な形状を例証している。図２のこれらの種類のエッジの各々の例は、表面エッジ（３０）、内部エッジ（３２）、境界エッジ（３４）、および、透明なエッジ（３６）を含んでいる。三次元の建物について、典型的なＮＰＲレンダリング様式（ペン画、漫画様式など）は、形状の情報を伝えるために強調される三次元建物の重要なエッジまたはＮＰＲエッジを必要とする。本発明のアルゴリズムは、これらのＮＰＲエッジをうまく特定することができてもよい。ひとたびこれらのエッジが特定されると、ストロークレンダリング（ｓｔｒｏｋｅ ｒｅｎｄｅｒｉｎｇ）技術（例えば、スプライト、ビルボード）は、手描きのＮＰＲ効果を達成するために、これらのエッジをレンダリングすべく使用されてもよい。ひとたび三次元の建物の形状が例証されると、建物のテクスチャは完全なＮＰＲの外観を有するように向上される必要があってもよい。発明のアルゴリズム（「ＮＰＲテクスチャ強化」）の第２の構成要素はこのタスクを完了してもよい。
【００２１】
図３ａと３ｂでは、３Ｄランドマークの外観が本発明の使用によってノンフォトリアリスティックな３Ｄマップに関してどのように強化させられるのかという２つの例が示されている。すなわち、図３ａおよび３ｂでは、発明の方法がノンフォトリアリスティックな３Ｄマップシステムで、ＮＰＲ様式の３Ｄランドマークをレンダリングするために適用されている。同じ３Ｄランドマークは、図３ａおよび３ｂ内の２つの異なる様式でそれぞれレンダリングされる。
【００２２】
発明のＮＰＲエッジ同定アルゴリズムは、元々の未処理の３Ｄランドマークデータをオフラインで処理するために使用されてもよい。アルゴリズムの出力は、ＮＰＲ様式の強化のためにマークされたエッジを含んでもよい。とりわけ、これらのエッジは、オンラインのＮＰＲレンダリングの間に強調されてもよい。加えて、アルゴリズムは、同様に、各々がマークを付けられたＮＰＲエッジのためにいくつかの重要な属性（例えば、エッジ幅など）を事前に計算してもよい。これらの情報の断片はすべて、ランタイムにＮＰＲエッジのレンダリング工程を促進するために使用されてもよい。たとえ重要なエッジ検出（シルエットエッジ（ｓｉｌｈｏｕｅｔｔｅ ｅｄｇｅ）検出を含む）がＮＰＲレンダリングの重要なトピックであっても、三次元の幾何学的形状とトポロジーが完全に規則的な防水性の表面に、たいて焦点が置かれる。本発明のアルゴリズムは、典型的な三次元の建物用のためのこれらの重要なエッジを検知する必要があり、この場合、３Ｄメッシュ構造は通常、明瞭ではないか、規則的ではない。最初に、発明のＮＰＲエッジ同定アルゴリズムは、表面内のエッジまたは構造を備えた三次元の建物データに対処する必要がある。次に、建物の幾何学的形状は、一般的に、壁、屋根などのような別の部品によってモデル化される。結果として、建築のモデルは通常不規則なトポロジーを包含する。最後に、建物のいくつかの追加の幾何学構造は、発明のアルゴリズムにおいて特定の処理を要求する、３Ｄデータ中の分離したテクスチャクワッド（ｔｅｘｔｕｒｅ ｑｕａｄｓ）によって表されることができる。発明のＮＰＲエッジ検出アルゴリズムの別の潜在的な特徴は、ＮＰＲエッジの特定を促進するためにドメイン知識が使用されてもよいということである。例えば、発明のアルゴリズムの入力が三次元の建物に限定されるため、アルゴリズムは、自動的なＮＰＲエッジ検出を促すために建物の下部構造（例えば、柱）を自動的に特定してもよい。
【００２３】
発明のＮＰＲエッジ同定アルゴリズムの１つの実施形態の概観が図４で示される。アルゴリズムは、事前マーキング、マーキング、および、事後マーキングを含む３つの主要な段階を有してもよい。入力はフォトリアリスティックな３Ｄランドマークデータであってもよい。幾何学的形状の一部は、２つのバッファー、すなわち、頂点バッファーとインデックスバッファーに記憶可能である。頂点バッファーは、メッシュの頂点すべてを包含してもよい。インデックスバッファーはメッシュの面（三角形）を構築するために使用されてもよく、これらの面は三次元の建物モデルのトポロジーを表してもよい。事前マーキングの第一段階で、ランドマークの透明なエッジと内部エッジが検知され分割されてもよい。元々のエッジと分割されたエッジを含むランドマークのエッジはすべて、完全なハーフエッジ構造（ＣＨＥＳ）と呼ばれるデータ構造を構築する際に使用されてもよい。
【００２４】
ＣＨＥＳに基づいて、発明のＮＰＲエッジ同定アルゴリズムは、すべてのエッジを繰り返し、マーキング操作を行ってもよい。この工程では、いくつかのエッジが廃棄され、他のものは「ＴＢＤ」または「ＦＩＸ」のいずれかでマークされてもよい。「ＦＩＸ」は視点が独立したＮＰＲエッジを示してもよい。これらのエッジは観察方向に対する建物の方向づけとは無関係に、ランタイムの間にレンダリングされてもよい。「ＴＢＤ」は視点が依存したＮＰＲエッジを示してもよい。これらのエッジがレンダリングされるか否かは、観察者に対する建物の方向づけに左右されることがある。これらのエッジが視点が依存したシルエットエッジになる場合に限り、これらはレンダリングされてもよい。シルエット検査を通過したすべてのＦＩＸエッジ、および、部分的なＴＢＤエッジは、エッジがストローク様式でレンダリング可能となるように、テクスチャビルボードまたはテクスチャスプライトを用いてレンダリングされてもよい。
【００２５】
次に、発明のＮＰＲエッジ同定アルゴリズムは、事後マーキング段階に移ってもよい。この段階では、下部構造がエッジマーキングのための特別な要件を有することがあるため、アルゴリズムはマーキングのために三次元の建物からこれらの下部構造を同定してもよい。１つの実施形態において、柱状のような、および、アーチ道のような下部構造で曲面を表すパラレルエッジが同定され、これらのエッジはＴＢＤラベルを用いてマークされてもよい。最後に、最終的な出力のために余分なＮＰＲエッジを取り除くべく、統合が行われてもよい。各々の同定されたＮＰＲエッジについては、ストロークレンダリング（ｓｔｒｏｋｅ ｒｅｎｄｅｒｉｎｇ）の幅値も同様に計算されてもよい。ＮＰＲエッジ同定アルゴリズムの最終的な出力は、「ＦＩＸ」または「ＴＢＤ」および幅値のラベルでマークされた、同定されたＮＰＲエッジであってもよい。
【００２６】
図５ａ−ｃは、３Ｄランドマークのフォトリアリスティックな視覚化のために透過性を有するテクスチャの典型的な使用を例示する。より具体的に、図５ａは、長方形の透明なエッジを有するポリゴンメッシュを例示する。図５ｂは、透明なエッジがレンダリングされない場合を例示し、図５ｃは、透明なエッジが実際にレンダリングされる場合を例示する。したがって、図５ｂ−ｃは、それぞれ透明なエッジのレンダリングが可能な場合と不可能な場合の効果の比較を提供する。とりわけ、建物がバットレス、アーチ道などを有する際に、透過性を有するテクスチャは三次元の建物のレンダリングで広く使用される。透明なテクスチャは、効率を考慮するために、三角形の数を少なく維持しながら、これらの複雑な構造を示すのにとても適している。しかしながら、三次元の建物のメッシュにおけるいくつかの三角形が、テクスチャマッピングの間に透明な領域によって部分的に覆われることが可能である。その結果、これらのエッジのいくつかは完全にまたは部分的に透明になってもよく、そのようなエッジがＮＰＲエッジとしてたんに特定されるのは不適切なこともある。そうでなければ、図５ａ−ｃによって例示されるように、不正確な形状情報が伝えられてもよい。透明なエッジをマーキング段階に送る前に透明なエッジを検知し分割することは有利である。
【００２７】
透明なエッジを検知および分割するための発明のアルゴリズムの１つの実施形態は、各々のエッジについて以下の工程を含んでいる。
１．各々のセグメントについて、エッジを多くのセグメントとサンプルの高密度のテクセルに分割する。
２．テクセルがそのαチャンネルによって透明かどうかチェックする。
３．透明なテクセルの割合が予め決められた閾値よりも大きい場合、セグメントは透明であると標識される。
４．透明なセグメントをすべて廃棄する。
５．エッジ中のすべてのセグメントが透明ではないと検知された場合、エッジは次の段階へ送られる。
６．そうでない場合、すべての透明でないセグメントを１つまたは複数の新しいエッジへと統合し、それらを次の段階に送る。
【００２８】
図６ａ−ｂは発明のアルゴリズムの１つの実施形態による、透明なエッジの検知および分割を例示する。上記のように、透明なエッジの検知および分割は、事前のマーキング段階中に生じることがある。より具体的に、図６ａは、透明なエッジの例を示し、図６ｂは、図６ａの透明なエッジの分割された結果を示す。透明なエッジは廃棄され、透明でないエッジは次の段階へ送られてもよい。
【００２９】
図４に示されるように、事前のマーキング段階では、透明なエッジの検知と分割のあとに、内部エッジの検知と分割が続いてもよい。図７ａは、３Ｄランドマークメッシュ中の内部エッジを示し、図７ｂは、内部エッジがレンダリングされていない図７ａのメッシュの断片的なレンダリングを示し、図７ｃは、内部エッジが実際にレンダリングされる図７ａのメッシュの断片的なレンダリングを示す。３Ｄランドマークのメッシュは、一般的に多くの内部エッジを包含している。内部エッジがＮＰＲエッジとしてレンダリングされる場合、図７ｃは、視覚アーチファクト（ｖｉｓｕａｌｉｚａｔｉｏｎ ａｒｔｉｆａｃｔｓ）の例を示す。いずれのエッジもフォトリアリスティックな視覚化のためにレンダリングされたり、強調されたりしないため、フォトリアリスティックなレンダリングの効果は影響を受けない。しかし、定型化した視覚化のためにエッジを強調することができる場合、内部エッジはＮＰＲレンダリングに影響することがある。結果として、内部エッジを検知および分割し、目に見える部分のみをマーキング段階に送ることは有利なことがある。
【００３０】
内部エッジを検知および分割するための発明のアルゴリズムの１つの実施形態は、各々のエッジについて以下の工程を含んでいる。
１．エッジを多くのセグメントへと分割する。
２．メッシュの中心からエンドポイントまで光線を構築することによって、セグメントの各エンドポイントについて可視性をテストする。光線がエンドポイントに触れた後にメッシュの任意の面と交差する場合、エンドポイントは目に見えないものとして認識される。
３．２つのエンドポイントのいずれかが目に見えない場合、セグメントは目に見えない。
４．目に見えないセグメントをすべて廃棄する。
５．すべてのセグメントが目に見えると検知される場合、エッジは次の段階へ送られる。
６．そうでない場合、すべての目に見えるセグメントを新しいエッジに統合し、次の段階に送る。
【００３１】
図８ａ−ｃは、事前のマーキング段階で内部エッジを検知および分割した結果を示す。エッジの目に見えないセグメントは廃棄され、目に見えるセグメントは次の段階へ送られる。より具体的には、面０および面１は、レンダリングされる構造の２つの面であってもよい。図８ａで示されるように、破線によって描かれた面１の一部は面０によって塞がれる。少なくとも部分的に塞がれるか隠される図８ａ中の面１のエッジは、「内部エッジ」と呼ばれ、図８ｂでは点線で参照番号（３８ａ）として描かれる。図８ｂは分割前の内部エッジ（３８ａ）を示し、図８ｃは、分割後の内部エッジ（３８ｂ）を示す。
【００３２】
完全なハーフエッジ構造（ＣＨＥＳ）を構築する事前マーキング段階の最終段階が、図９ａ−ｃでより詳細に記載されてもよい。３Ｄモデル中の山と谷は、人々が形状情報を理解するための重要なてがかりとなることもある。ノンフォトリアリスティックレンダリングでは、山と谷にそったエッジは、通常、重要なエッジと見なされる。それらのエッジを同定するために、ほとんどの既存のアルゴリズムは、各々のエッジの２つの隣接する面の間の二面角の値をチェックする。通常の幾何学的形状の表面については、エッジの２つの隣接する面は、ハーフエッジデータ構造を構築することによって容易に見つけられる。本発明では、建物の幾何学的形状が一般的に壁、屋根、柱などを含む別の部品によってモデル化されるため、建物のトポロジーは全く不規則になることがある。図９ａ−ｃは、２つの視覚的に隣接する面が１以上のエッジを共有する例を示す。あるいは、１つのエッジは２つ以上の隣接する面を有する。その結果、従来のハーフエッジ構造はこれらのケースを扱うために拡張（ａｕｇｍｅｎｔ）されてもよく、そのような拡張したデータ構造はＣＨＥＳと呼ばれてもいい。より具体的には、図９ａは、不規則なトポロジーを有するメッシュポリゴンの例を示し、図９ｂは、図９ａの不規則なトポロジーの２つの境界エッジを示し、図９ｃは、２つの面が１つのエッジを共有する規則的または理想的なトポロジーの例を示す。
【００３３】
３ＤランドマークについてのＣＨＥＳを構築するための発明のアルゴリズムの１つの実施形態は、以下の工程を含んでいる。
Ａ．従来のハーフエッジデータ構造を構築する。
Ｂ．各々のエッジについて、
１．エッジの境界エッジペアを測定する。境界エッジは、図１０ａのエッジ（４０）またはエッジ（４２）のような、たった１つの隣接した面を有するエッジである。境界エッジペアは、図１０ａのエッジ（４０）またはエッジ（４２）のような、互いに「触れる」２つの境界エッジを包含している。境界エッジペアは下記条件を満たしてもよい。
ａ．両方の２つのエッジが境界エッジである。
ｂ．２つのエッジが互いに対して平行である。したがって、図１１ａのエッジ（４４）およびエッジ（４６）は、フィルタ処理が施される。
ｃ．２つのエッジは互いに接近している。したがって、図１１ｂで示された場合のエッジ（４８）およびエッジ（５０）はフィルタ処理が施される。
ｄ．２つのエッジは重ねられなければならない。したがって、図１１ｃで示された場合のエッジ（５２）およびエッジ（５４）はフィルタ処理が施される。
２．境界エッジの隣接する面を１つの群に統合する。エッジの１つに隣接する任意の面は両方のエッジによって参照される。
【００３４】
ひとたびＣＨＥＳが構築されると、エッジに隣接する面はすべてエッジの隣接する面の群に加えられる。図１０ａは、ＣＨＥＳを構築する前のＣＨＥＳ構造を示す。エッジ（４０）は三角形の面（５６）につなげられ、エッジ（４２）は三角形の面（５８）につなげられる。図１０ｂは、ＣＨＥＳを構築した後のＣＨＥＳ構造を示す。エッジ（４０）は両方の三角形の面（５６）、（５８）につなげられ、エッジ（４２）も両方の三角形の面（５６）および（５８）につなげられる。
【００３５】
図１２は、図４のＮＰＲエッジ同定アルゴリズムのマーキング段階を要約したフローチャートである。
ＣＨＥＳに基づいて、いくつかの試験動作が終わるまで、各々の対象エッジのラベルは測定されない（工程１２０２）。最初に、各々のエッジの隣接する面の数がチェックされる（工程１２０４）。群に１つの面しかない場合、エッジは境界エッジであり、そのラベルは「ＦＩＸ」としてマークされる（工程１２０６）。しかしながら、群に２つの隣接した面がある場合、エッジの二面角は、以下の方程式（１）を用いて、これらの２つの面の法線（ｎｏｒｍａｌ）に基づいて計算される（工程１２０８）
【００３６】
【数１】
【００３７】
図１３ａ−ｂは、２つの面に基づいた二面角を計算する方法の１つの実施形態を示す。面ｆ０およびｆ１の法線は、ｎ０とｎ１とそれぞれ表される。
【００３８】
群に２以上の面がある場合、２つの面ごとの最小の二面角は、エッジの二面角として選択される（工程１２１０）。各々のエッジの二面角および配向に基づいて、エッジのラベルは図１４の表中の規則を適用することによって測定可能である（工程１２１２）。他のエッジと比較して、三次元の建物の垂直および水平方向のエッジは、３Ｄ形状情報を伝えるのにより重要である。したがって、図１４に示されるように、特定のマーキング規則またはパラメータが異なる種類のエッジに使用されてもよい。図１４の表によれば、「ＦＩＸ」とマークされない条件と「ＴＢＤ」とマークされない条件がいずれも満たされない場合、エッジは、上記のように「ＦＩＸ」（工程１２０６）または「ＴＢＤ」（工程１２１４）として、または、「ＳＫＩＰ」（工程１２１６）として、マークされてもよい。
【００３９】
図４に示されるように、事後のマーキング段階は、マーキングの更新のために建物の下部構造を特定することを含んでもよい。図１５ａは３Ｄランドマーク建物の柱状構造のレンダリングを示す。複数の柱（６０）が示され、そのような柱は３Ｄランドマーク建物の共通の下部構造である。図１５ｂは図１５ａのレンダリングに基づいた３Ｄランドマークのポリゴンメッシュであり、図１５ｃは図１５ｂのメッシュに含まれる柱の３Ｄポリゴンメッシュである。柱中のすべての垂直エッジのなかで、現在の視点下でシルエットエッジになるもののみがレンダリング中に強調される。例えば、図１５ｃで垂直エッジ（６２ａ−ｂ）は、柱の外形を形成するシルエットエッジである。結果として、これらのエッジはすべて「ＴＢＤ」と標識される。典型的な建物の下部構造を自動的に特定し、下部構造の種類に基づいてマーキングを更新することが必要である。柱を発見するという問題は、クラスタ化問題として公式化される。Ｋ平均アルゴリズムのような典型的なクラスタ化アルゴリズムを適用するために、類似性測定基準（ａ ｓｉｍｉｌａｒｉｔｙ ｍｅｔｒｉｃ）が２つの垂直な柱エッジ間の距離を定量化すべく定義されてもよい。距離測定基準は、２つの線分の距離と長さの差を含んでもよい。クラスタ化の後、すべての３Ｄランドマークの垂直エッジは、個々のエッジまたは柱を表す異なる群にクラスタ化されてもよい。
【００４０】
統合と明瞭化は、効率の目的で事後のマーキング段階の重要な工程である。マーキング段階中に検知されるいくつかのＮＰＲエッジは、互いに対して平行かつ隣接してもよい。いくつかのＮＰＲエッジは完全にまたは部分的に互いに重複してもよい。これらのエッジについては、エッジは個々にレンダリングされるか、または、統合後に１つの単一エッジとしてレンダリングされてもよい。後者の選択の方が好ましい。というのも、レンダリングされるＮＰＲエッジの数を減らしながら、同じ視覚化効果が達成されるためである。したがって、レンダリング性能は劇的に改善される。
【００４１】
図１６ａ−ｂで例示されるように、下記条件をすべて満たすエッジが統合されてもよい。
１）エッジは「ＦＩＸ」ラベルで前もってマークされる。
２）エッジは、隣接した場合を含めて、互いに完全にまたは部分的に重なる。
【００４２】
統合の後、明瞭化が行われてもよい。ランドマークモデルの縮尺と比較して、いくつかのＮＰＲエッジは比較的短すぎてもよい。短いエッジの除去は、ＮＰＲレンダリングの視覚的な質をほとんど変更しないが、レンダリング性能を向上させることができる。したがって、１つの実施形態では、長さがその閾値 ＳＨＯＲＴ＿ＬＥＮ＿ＳＣＡＬＥ×ＭＯＤＥＬ＿ＳＣＡＬＥ より短い任意のＮＰＲエッジが取り除かれてもよく、ＳＨＯＲＴ＿ＬＥＮ＿ＳＣＡＬＥ×ＭＯＤＥＬ＿ＳＣＡＬＥ は、予め決められたパラメータであり、ＭＯＤＥＬ＿ＳＣＡＬＥは以下の式に基づいて計算される：
ＭＯＤＥＬ＿ＳＣＡＬＥ＝０．５×（（ＢＬ＋ＢＷ＋ＢＨ）−ｍｉｎ（ＢＬ、ＢＷ、ＢＨ））
式中、ＢＬ、ＢＷおよびＢＨは、モデル全体の境界ボックスの長さ、幅、および、高さを表す。
【００４３】
事後マーキング段階の次の工程はＮＰＲエッジの幅の計算であってもよい。前の段階で検知されたＮＰＲエッジは、ビルボード（テクスチャがマップされた長方形）を用いることによってレンダリングされてもよく、ビルボードの幅は計算される必要がある。この工程では、テクスチャがマップされたビルボード（ストロークを表す）は、基礎となるＮＰＲエッジのまわりで回転することを許されてもよい。ビルボードの長さが基礎となるＮＰＲエッジの長さと等しく、その一方で、ストロークの手動による線描効果が達成可能となるように、幅が注意深く計算される必要がある。ビルボードの幅は２つの観察に基づいて測定されてもよい。最初に、ビルボードの幅はその長さとともに増加しなければならない。結果として、幅を計算する関数は、長さの関数の単調な増加関数でなければならない。次に、ビルボードの幅が非線形的な手法で増大するのが望ましい。ＮＰＲエッジの長さがより短い場合、ビルボードの幅は急激に増えなければならず、ＮＰＲエッジの長さが大きい場合、ビルボードの幅は徐々に増える。結果として、短いエッジは知覚可能なストローク幅を依然として有してもよく、その一方で、長いエッジはレンダリングの間に非常に大きな幅値を割り当てられないことがある。上記の２つの観察に基づいて、二相の幅の関数が設計されてもよい。図１７のプロットは、正規化した幅と正規化した長さの関係を示しており、以下の方程式によってさらに記載される。
ＮｏｒｍａｌｉｚｅｄＬｅｎｇｔｈ＝Ｌｅｎｇｔｈ／ＭｏｄｅｌＳｃａｌｅ
ＮｏｒｍａｌｉｚｅｄＷｉｄｔｈ＝ＭｉｎｉｍａｌＮｏｒｍａｌｉｚｅｄＷｉｄｔｈ＋ＳｐａｎＦａｓｔ×（１−ｅｘｐ（−ＫＦａｓt×ＮｏｒｍａｌｉｚｅｄＬｅｎｇｔｈ））＋ＳｐａｎＳｌｏｗ×（１−ｅｘｐ（−ＫＳｌｏｗ×ＮｏｒｍａｌｉｚｅｄＬｅｎｇｔｈ）
Ｗｉｄｔｈ＝ＮｏｒｍａｌｉｚｅｄＷｉｄｔｈ×ＭｏｄｅｌＳｃａｌｅ
式中、
ＳｐａｎＦａｓｔ＝（ＭａｘＮｏｒｍａｌｉｚｅｄＷｉｄｔｈ−ＭｉｎＮｏｒｍａｌｉｚｅｄＷｉｄｔｈ）×ｐｅｒｃｅｎｔａｇｅＦａｓｔ
ＳｐａｎＳｌｏｗ＝（ＭａｘＮｏｒｍａｌｉｚｅｄＷｉｄｔｈ−ＭｉｎＮｏｒｍａｌｉｚｅｄＷｉｄｔｈ）×（１−ｐｅｒｃｅｎｔａｇｅＦａｓｔ）
ＭｉｎｉｍａｌＮｏｒｍａｌｉｚｅｄＷｉｄｔｈとＭａｘｉｍａｌＮｏｒｍａｌｉｚｅｄＷｉｄｔｈは、（ＭｏｄｅｌＳｃａｌｅに対する）ＮＰＲエッジの正規化した幅の下界と上界を制御する調整可能パラメータである。ＰｅｒｃｅｎｔａｇｅＦａｓｔは急激に増える領域と徐々に増える領域とを分離するパラメータである。ＫＦａｓｔとＫＳｌｏｗは２つの速度定数である。急激にかつ緩慢に半正規化された長さ（Ｆａｓｔ ｈａｌｄ ａｎｄ ｓｌｏｗ ｈａｌｆ ｎｏｒｍａｌｉｚｅｄ ｌｅｎｇｔｈ）は、ｌｎ（２）／Ｋとして計算されてもよい。
【００４４】
発明の方法の第１の構成要素（ＮＰＲレンダリングに関する重要なエッジの自動特定）が完了すると、第２の構成要素、ＮＰＲテクスチャの強化が行われてもよい。図１８は、元々の二次元のテクスチャから強化された異なるＮＰＲ様式を示す。ＮＰＲテクスチャの強化は、未処理のランドマークデータ中の元々のフォトリアリスティックなテクスチャを入力として受け取るために、かつ、それを異なるＮＰＲ様式のテクスチャに変換するために定義されてもよい。様々な標準的な画像処理技術はこのタスクを遂行するために使用されてもよい。第三者の画像処理ソフトウェア（例えば、Ａｄｏｂｅ（登録商標）Ｐｈｏｔｏｓｈｏｐ（登録商標））もこの目的に使用可能である。
【００４５】
上記の本発明はいくつかの新規な特徴を含んでいる。本発明は、ノンフォトリアリスティックな３Ｄマップにフォトリアリスティックな３Ｄランドマークを再使用する方法を提供してもよい。本発明は、防水表面以外の様々な構造を含む三次元の建物データからＮＰＲエッジを自動的に同定することができる（例えば、下位アルゴリズムと、データ編成方法の完全なハーフエッジ構造ＣＨＥＳとのセットからなる）アルゴリズムを提供してもよい。
【００４６】
ここで、図１９には、自動車、船、飛行機などの車両に関連する本発明の３Ｄマップレンダリング配置（１０）の１つの実施形態が示されている。すなわち、配置（１０）は車に搭載して取り付けられてもよい。
【００４７】
配置（１０）は、事前に処理された３Ｄフォトリアリスティックなマップデータソース（１４）、ＮＰＲ ３Ｄマップエンジン（１６）、および、ユーザーインタフェース（２２）を含んでもよい。フォトリアリスティックな３Ｄマップデータソース（１２）は、ＮＰＲ ３Ｄマップエンジン処理構成要素（１８）によって事前に処理され、事前に処理された３Ｄマップデータソース（１４）となる。事前に処理された３Ｄマップデータソースは、コンパクトディスク（ＣＤ）または他の記憶装置の形状であってもよい。あるいは、３Ｄマップデータは、各々がそれぞれの３Ｄマップレンダリング配置（１０）を有する多くの車両に、中央の送信機（図示せず）によって無線送信されてもよい。このような無線送信は、ＮＰＲ３Ｄマップエンジンレンダリング構成要素（２０）によって受け取られてもよい。
【００４８】
事前に処理された３Ｄマップデータソース（１４）は、リアルタイムで車両のグローバルな位置座標を測定するための全地球測位システム（ＧＰＳ）モジュール（図示せず）も含んでよい。車両の現在の位置に基づいて、車両内の人々にとって興味深い対応する３Ｄマップデータが特定され、ＮＰＲ３Ｄマップエンジン（１６）のオンラインレンダリング構成要素（２０）が提供される。
【００４９】
ＮＰＲ ３Ｄエンジン（１６）は標準的な電子工程を含み、２つの構成要素、オフライン処理構成要素（１８）とオンラインレンダリング構成要素（２０）からなる。処理構成要素（１８）は、ソース（１２）からのフォトリアリスティックな３Ｄマップデータをオフラインで事前に処理してもよい。レンダリング構成要素（２０）は、事前に処理された３Ｄマップデータソース（１４）からノンフォトリアリスティックな画像をオンラインで生成してもよい。ノンフォトリアリスティックな画像は、漫画の、鉛筆画の、ペン画の、イラストの、油絵の効果、および、他の絵画様式などの様々な様式であってもよい。ＮＰＲレンダリングは、物体の表面および物体の典型的なまたは周知の特徴を描いてもよい。
【００５０】
図２０乃至２３は、先行技術のナビゲーション領域に適用されていない様々なＮＰＲ様式を示す。図２０乃至２３のこれらの様式の各々は、本発明のＮＰＲ ３Ｄマップレンダリング方法とともに使用するのに適している。さらに具体的に、図２０は、大きさを変更できるリアルタイムの３Ｄアニメーションのための漫画様式の定型化したレンダリング技術を示し、図２１はペン画のレンダリングを示し、図２２はリアルタイムの鉛筆画風レンダリングを示し、そして、図２３は本発明によってレンダリングされるＮＰＲ ３Ｄマップの一例である漫画様式のＮＰＲ ３Ｄマップを示す。
【００５１】
１つの実施形態では、ユーザーは、図２３に描かれる画角を、地表レベルまたはそれより高い任意の視角または任意の位置に調節することができる。例えば、ユーザーは、建物のいずれかまたはすべてのまわりの３６０度のアークに沿った視界のほとんど無限の数から選んでもよい。さらに、ユーザーは、垂直面に沿った任意の下向きの視角を選んでもよい。
【００５２】
ユーザーインタフェース（２２）は、車両のダッシュボードに配置されてもよく、表示スクリーン（２４）および制御装置（２６）を含んでもよい。表示スクリーン（２４）は、スクリーンまたはモニターに表示される情報または内容を制御するためのプロセッサーとメモリを含んでもよい。一般的に、表示スクリーン（２４）は、レンダリング構成要素（２０）から受け取ったＮＰＲ ３Ｄ画像データを示すか、または、このデータを描く。
【００５３】
制御装置（２６）は、ダイヤル、ノブ、プッシュボタン一式、ジョイスティック、マイクロホン、タッチインタフェース、または、上記のものの任意の組み合わせの形状であってもよい。ユーザーは、エンジン（１６）にフィードバック（２８）を提供するために制御装置（２６）を使用してもよい。フィードバック（２８）は、別の画像データ一式（例えば、別の場面、物体、または、物体一式を描く画像データ）を作るようエンジン（１６）に指示してもよい。あるいは、フィードバック（２８）は、現在の画像データ一式が見える視角を変更するようにエンジン（１６）に指示してもよい。視角は、周囲環境の頭上の鳥瞰図から、地表レベルまたは地上レベルから建物または他のランドマークを見上げる角度まで、様々である。
【００５４】
ナビゲーションマップを表示するための本発明の方法（２４００）の実施形態が図２４で示されている。第１の工程（２４０２）において、フォトリアリスティックな三次元データが事前に処理され記憶される。
【００５５】
次の工程（２４０４）では、車両の位置が自動的に測定される。例えば、図１９の配置は、配置に関連する車両の現在の位置（それはグローバル座標で表現されてもよい）を、自動的かつ連続的に更新するＧＰＳまたは他の装置を含んでもよい。
【００５６】
次に、工程（２４０６）では、車両の地理的な領域内に配されるランドマークに関連した、事前に処理された三次元データの一部が特定される。例えば、工程（２４０４）で測定された車両位置に基づいて、車両付近に関連するマップデータがＣＤなどの記憶装置から検索されてもよい。あるいは、車両付近に関連するマップデータは、マップデータのセントラル・レポジトリから無線で受け取られてもよい。どのように受け取られ、および／または、特定されるかにかかわらず、マップデータは、車両付近内の建物と自然のランドマークの形状、寸法、色、および、窓を記載した３Ｄデータを含んでもよい。
【００５７】
次に、工程（２４０８）では、ノンフォトリアリスティックな画像は、事前に処理された３Ｄマップデータの特定された部分に基づいてレンダリングされる。図２０乃至２３は、画像がレンダリングされるノンフォトリアリスティック様式の例を示す。
【００５８】
最終的な工程（２４１０）では、ノンフォトリアリスティックな画像は、車両内のユーザーに電子的に表示される。１つの実施形態では、エンジン（１６）によってレンダリングされるＮＰＲ画像は、ユーザーインタフェース（２２）のスクリーン（２４）に表示される。
【００５９】
この発明は例示的な設計を有するものとして記載されてきたが、本発明はこの開示の精神と範囲内でさらに修正されてもよい。したがって、この出願は一般的な原則を用いて本発明の任意の変化、用途、または、適応を対象にするように意図されている。
【特許請求の範囲】
【請求項１】
ナビゲーションマップを表示する方法であって、
前記方法は、
フォトリアリスティックな三次元データをオフラインで事前に処理する工程と、
車両の位置を自動的にオンラインで測定する工程と、
車両の位置を含む地理的な領域内に配された物体に関連する事前に処理された三次元データの一部を特定する工程と、
事前に処理されたデータの特定された一部に基づいて、ノンフォトリアリスティックな画像をレンダリングする工程と、
車両内のユーザーにノンフォトリアリスティックな画像を電子的に表示する工程を含むことを特徴とする方法。
【請求項２】
前記レンダリングする工程は、ノンフォトリアリスティックな画像を生成するために、物体のノンフォトリアリスティックレンダリングされたエッジと、物体のノンフォトリアリスティックなテクスチャとを組み合わせる工程を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記レンダリングする工程は、データ中のテクスチャに、視点が独立していようと依存していようとデータ中のエッジに、および、各々のエッジの幅に、依存して行われることを特徴とする請求項１に記載の方法。
【請求項４】
前記事前に処理する工程は、フォトリアリスティックデータ中の物体のエッジを分割する工程を含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記事前に処理する工程は、完全なハーフエッジ構造を構築するために、フォトリアリスティックデータ中の物体の分割されていないエッジと、フォトリアリスティックデータ中の物体の分割されたエッジとを用いる工程を含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記事前に処理する工程は、完全なハーフエッジ構造中のエッジの余分ないくつかを統合する工程を含むことを特徴とする請求項５に記載の方法。
【請求項７】
ナビゲーションマップを表示する方法であって、
前記方法は、
フォトリアリスティックな三次元データを事前に処理する工程と、
車両の位置を自動的に測定する工程と、
車両の位置を含む地理的な領域内に配された物体に関連する事前に処理された三次元データの一部を特定する工程と、
フォトリアリスティックデータ中の物体のエッジを自動的に特定するとともにノンフォトリアリスティックにレンダリングする工程と、
フォトリアリスティックデータ中のフォトリアリスティックなテクスチャをノンフォトリアリスティックなテクスチャに変換する工程と、
ノンフォトリアリスティックなテクスチャ、データ中の物体のマークされたエッジ、および、データ中の各々のエッジの幅値に基づいて、物体のノンフォトリアリスティックな画像を生成する工程と、
車両内のユーザーにノンフォトリアリスティックな画像を電子的に表示する工程を含むことを特徴とする方法。
【請求項８】
前記レンダリングする工程は、データ中のテクスチャに、視点が独立していようと依存していようとデータ中のエッジに、および、各々のエッジの幅に、依存して行われることを特徴とする請求項７に記載の方法。
【請求項９】
前記レンダリングする工程は、フォトリアリスティックデータ中の物体のエッジを分割する工程を含むことを特徴とする請求項７に記載の方法。
【請求項１０】
分割されるエッジの各々は、透明であるか、および／または、内部であることを特徴とする請求項９に記載の方法。
【請求項１１】
前記レンダリングする工程は、完全なハーフエッジ構造を構築するために、フォトリアリスティックデータ中の物体の分割されていないエッジと、フォトリアリスティックデータ中の物体の分割されたエッジとを用いる工程を含むことを特徴とする請求項９に記載の方法。
【請求項１２】
前記レンダリングする工程は、完全なハーフエッジ構造中のエッジの余分ないくつかを統合する工程を含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記統合する工程の後に、閾値長さ未満の長さを有する完全なハーフエッジ構造中のエッジのいくつかを廃棄する工程をさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記レンダリングする工程が、完全なハーフエッジ構造中の前記エッジの各々に関して、エッジを廃棄する工程と、視点が独立しているとしてエッジをマークする工程と、または、視点が依存しているとしてエッジをマークする工程を含むことを特徴とする請求項１１に記載の方法。
【請求項１５】
３Ｄのランドマークデータを処理する方法であって、
前記方法は、
三次元のフォトリアリスティックデータ中の物体の透明なエッジと内部のエッジを検知するとともに分割する工程と、
完全なハーフエッジ構造を構築するために、フォトリアリスティックデータ中の物体の非透明なエッジと、内部にないエッジと、内部のエッジとを用いる工程と、
完全なハーフエッジ構造中のエッジの各々に関して、エッジを廃棄する工程と、視点が独立しているエッジとしてエッジをマークする工程と、または、視点が依存しているエッジとしてエッジをマークする工程のいずれかの工程と、
完全なハーフエッジ構造内の複数の下部構造を特定する工程と、
下部構造の種類に基づいて、下部構造の少なくとも１つのマーキングを更新する工程と、
ノンフォトリアリスティックにレンダリングされたエッジの最後の組を生成するために、完全なハーフエッジ構造中のエッジの余分ないくつかを統合する工程と、
最後の組におけるエッジの各々に関して幅値を計算する工程と、
フォトリアリスティックデータ中のフォトリアリスティックなテクスチャを、ノンフォトリアリスティックなテクスチャに変換する工程と、
ノンフォトリアリスティックなテクスチャと、ノンフォトリアリスティックにレンダリングされたエッジの最後の組と、最後の組におけるエッジの各々のマーキングと、最後の組におけるエッジの各々についての幅値とに基づいて、物体のノンフォトリアリスティックな画像を生成する工程であって、最後の組におけるエッジの各々が、視点が独立しているエッジまたは視点が依存しているエッジのいずれかとしてマークされる工程を含むことを特徴とする方法。
【請求項１６】
完全なハーフエッジ構造の構築が隣接する境界エッジの統合を含むことを特徴とする請求項１５に記載の方法。
【請求項１７】
視点が独立しているエッジ、または、視点が依存しているエッジのいずれかとしてマークされ、かつ、１以上の隣接する面を有するエッジの各々は、エッジの配向および／または二面角に依存してマークされることを特徴とする請求項１５に記載の方法。
【請求項１８】
前記統合する工程の後、閾値長さ未満の長さを有する完全なハーフエッジ構造中のエッジのいくつかを廃棄する工程をさらに含むことを特徴とする請求項１５に記載の方法。
【請求項１９】
物体の見えるところにいる車両内のユーザーにノンフォトリアリスティックな画像を電子的に表示する工程をさらに含むことを特徴とする請求項１５に記載の方法。
【請求項２０】
車両の位置を自動的に測定する工程と、
ノンフォトリアリスティックな三次元データの集中型のプロバイダーに、車両の位置を無線送信する工程をさらに含み、
物体に関連するフォトリアリスティックな三次元データは事前に処理され、集中型のプロバイダーから車両に無線送信されることを特徴とする請求項１９に記載の方法。
【請求項１】
ナビゲーションマップを表示する方法であって、
前記方法は、
フォトリアリスティックな三次元データをオフラインで事前に処理する工程と、
車両の位置を自動的にオンラインで測定する工程と、
車両の位置を含む地理的な領域内に配された物体に関連する事前に処理された三次元データの一部を特定する工程と、
事前に処理されたデータの特定された一部に基づいて、ノンフォトリアリスティックな画像をレンダリングする工程と、
車両内のユーザーにノンフォトリアリスティックな画像を電子的に表示する工程を含むことを特徴とする方法。
【請求項２】
前記レンダリングする工程は、ノンフォトリアリスティックな画像を生成するために、物体のノンフォトリアリスティックレンダリングされたエッジと、物体のノンフォトリアリスティックなテクスチャとを組み合わせる工程を含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記レンダリングする工程は、データ中のテクスチャに、視点が独立していようと依存していようとデータ中のエッジに、および、各々のエッジの幅に、依存して行われることを特徴とする請求項１に記載の方法。
【請求項４】
前記事前に処理する工程は、フォトリアリスティックデータ中の物体のエッジを分割する工程を含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記事前に処理する工程は、完全なハーフエッジ構造を構築するために、フォトリアリスティックデータ中の物体の分割されていないエッジと、フォトリアリスティックデータ中の物体の分割されたエッジとを用いる工程を含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記事前に処理する工程は、完全なハーフエッジ構造中のエッジの余分ないくつかを統合する工程を含むことを特徴とする請求項５に記載の方法。
【請求項７】
ナビゲーションマップを表示する方法であって、
前記方法は、
フォトリアリスティックな三次元データを事前に処理する工程と、
車両の位置を自動的に測定する工程と、
車両の位置を含む地理的な領域内に配された物体に関連する事前に処理された三次元データの一部を特定する工程と、
フォトリアリスティックデータ中の物体のエッジを自動的に特定するとともにノンフォトリアリスティックにレンダリングする工程と、
フォトリアリスティックデータ中のフォトリアリスティックなテクスチャをノンフォトリアリスティックなテクスチャに変換する工程と、
ノンフォトリアリスティックなテクスチャ、データ中の物体のマークされたエッジ、および、データ中の各々のエッジの幅値に基づいて、物体のノンフォトリアリスティックな画像を生成する工程と、
車両内のユーザーにノンフォトリアリスティックな画像を電子的に表示する工程を含むことを特徴とする方法。
【請求項８】
前記レンダリングする工程は、データ中のテクスチャに、視点が独立していようと依存していようとデータ中のエッジに、および、各々のエッジの幅に、依存して行われることを特徴とする請求項７に記載の方法。
【請求項９】
前記レンダリングする工程は、フォトリアリスティックデータ中の物体のエッジを分割する工程を含むことを特徴とする請求項７に記載の方法。
【請求項１０】
分割されるエッジの各々は、透明であるか、および／または、内部であることを特徴とする請求項９に記載の方法。
【請求項１１】
前記レンダリングする工程は、完全なハーフエッジ構造を構築するために、フォトリアリスティックデータ中の物体の分割されていないエッジと、フォトリアリスティックデータ中の物体の分割されたエッジとを用いる工程を含むことを特徴とする請求項９に記載の方法。
【請求項１２】
前記レンダリングする工程は、完全なハーフエッジ構造中のエッジの余分ないくつかを統合する工程を含むことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記統合する工程の後に、閾値長さ未満の長さを有する完全なハーフエッジ構造中のエッジのいくつかを廃棄する工程をさらに含むことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記レンダリングする工程が、完全なハーフエッジ構造中の前記エッジの各々に関して、エッジを廃棄する工程と、視点が独立しているとしてエッジをマークする工程と、または、視点が依存しているとしてエッジをマークする工程を含むことを特徴とする請求項１１に記載の方法。
【請求項１５】
３Ｄのランドマークデータを処理する方法であって、
前記方法は、
三次元のフォトリアリスティックデータ中の物体の透明なエッジと内部のエッジを検知するとともに分割する工程と、
完全なハーフエッジ構造を構築するために、フォトリアリスティックデータ中の物体の非透明なエッジと、内部にないエッジと、内部のエッジとを用いる工程と、
完全なハーフエッジ構造中のエッジの各々に関して、エッジを廃棄する工程と、視点が独立しているエッジとしてエッジをマークする工程と、または、視点が依存しているエッジとしてエッジをマークする工程のいずれかの工程と、
完全なハーフエッジ構造内の複数の下部構造を特定する工程と、
下部構造の種類に基づいて、下部構造の少なくとも１つのマーキングを更新する工程と、
ノンフォトリアリスティックにレンダリングされたエッジの最後の組を生成するために、完全なハーフエッジ構造中のエッジの余分ないくつかを統合する工程と、
最後の組におけるエッジの各々に関して幅値を計算する工程と、
フォトリアリスティックデータ中のフォトリアリスティックなテクスチャを、ノンフォトリアリスティックなテクスチャに変換する工程と、
ノンフォトリアリスティックなテクスチャと、ノンフォトリアリスティックにレンダリングされたエッジの最後の組と、最後の組におけるエッジの各々のマーキングと、最後の組におけるエッジの各々についての幅値とに基づいて、物体のノンフォトリアリスティックな画像を生成する工程であって、最後の組におけるエッジの各々が、視点が独立しているエッジまたは視点が依存しているエッジのいずれかとしてマークされる工程を含むことを特徴とする方法。
【請求項１６】
完全なハーフエッジ構造の構築が隣接する境界エッジの統合を含むことを特徴とする請求項１５に記載の方法。
【請求項１７】
視点が独立しているエッジ、または、視点が依存しているエッジのいずれかとしてマークされ、かつ、１以上の隣接する面を有するエッジの各々は、エッジの配向および／または二面角に依存してマークされることを特徴とする請求項１５に記載の方法。
【請求項１８】
前記統合する工程の後、閾値長さ未満の長さを有する完全なハーフエッジ構造中のエッジのいくつかを廃棄する工程をさらに含むことを特徴とする請求項１５に記載の方法。
【請求項１９】
物体の見えるところにいる車両内のユーザーにノンフォトリアリスティックな画像を電子的に表示する工程をさらに含むことを特徴とする請求項１５に記載の方法。
【請求項２０】
車両の位置を自動的に測定する工程と、
ノンフォトリアリスティックな三次元データの集中型のプロバイダーに、車両の位置を無線送信する工程をさらに含み、
物体に関連するフォトリアリスティックな三次元データは事前に処理され、集中型のプロバイダーから車両に無線送信されることを特徴とする請求項１９に記載の方法。
【図２】
【図３ａ】
【図３ｂ】
【図４】
【図５ａ】
【図５ｂ】
【図５ｃ】
【図６ａ】
【図６ｂ】
【図７ａ】
【図７ｂ】
【図７ｃ】
【図８ｂ】
【図８ｃ】
【図９ａ−９ｃ】
【図１０ａ】
【図１０ｂ】
【図１１ａ】
【図１１ｂ】
【図１１ｃ】
【図１２】
【図１３ａ】
【図１３ｂ】
【図１４】
【図１５ａ−１５ｃ】
【図１６ａ】
【図１６ｂ】
【図１７】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図１】
【図８ａ】
【図１８】
【図３ａ】
【図３ｂ】
【図４】
【図５ａ】
【図５ｂ】
【図５ｃ】
【図６ａ】
【図６ｂ】
【図７ａ】
【図７ｂ】
【図７ｃ】
【図８ｂ】
【図８ｃ】
【図９ａ−９ｃ】
【図１０ａ】
【図１０ｂ】
【図１１ａ】
【図１１ｂ】
【図１１ｃ】
【図１２】
【図１３ａ】
【図１３ｂ】
【図１４】
【図１５ａ−１５ｃ】
【図１６ａ】
【図１６ｂ】
【図１７】
【図１９】
【図２０】
【図２１】
【図２２】
【図２３】
【図２４】
【図１】
【図８ａ】
【図１８】
【公表番号】特表２０１３−５１３９００（Ｐ２０１３−５１３９００Ａ）
【公表日】平成２５年４月２２日（２０１３．４．２２）
【国際特許分類】
【出願番号】特願２０１２−５４４７０４（Ｐ２０１２−５４４７０４）
【出願日】平成２２年１２月１４日（２０１０．１２．１４）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０６０２４７
【国際公開番号】ＷＯ２０１１／０８１９１９
【国際公開日】平成２３年７月７日（２０１１．７．７）
【出願人】（５１１１５０５７３）ロベルト ボッシュ ゲーエムベーハー (6)
【Ｆターム（参考）】
【公表日】平成２５年４月２２日（２０１３．４．２２）
【国際特許分類】
【出願日】平成２２年１２月１４日（２０１０．１２．１４）
【国際出願番号】ＰＣＴ／ＵＳ２０１０／０６０２４７
【国際公開番号】ＷＯ２０１１／０８１９１９
【国際公開日】平成２３年７月７日（２０１１．７．７）
【出願人】（５１１１５０５７３）ロベルト ボッシュ ゲーエムベーハー (6)
【Ｆターム（参考）】
[ Back to top ]