(57)【要約】【課題】三次元グラフィック環境での二次元高架道路データの三次元変換方法及び装置、そしてこれを利用した三次元グラフィック環境での二次元高架道路データの三次元視覚化方法及び装置を提供する。【解決手段】重畳領域分離部１００、三角化処理部２００、高さ座標追加部３００、及び視覚化処理部４００を備える三次元グラフィック環境での二次元高架道路データ１０の三次元視覚化装置等である。これにより、分離ラインを選択的に適用して多角形の重畳部分を分離し、イヤカットアルゴリズムを適用して多角形を三角化処理し、生成された高架道路データの各部分別に多様な視覚化処理を行うことにより、二次元高架道路データ１０を効果的に三次元高架道路データ１６に変換でき、高架道路の多様な外観を表現できる。【選択図】図２
2006209767.tif 000002
【特許請求の範囲】
【請求項１】
三次元グラフィック環境での二次元高架道路データの三次元変換装置を用いた三次元変換方法であって、
（ａ）前記三次元変換装置の分離ラインリスト生成部が、前記二次元高架道路データを構成する多角形を２つの領域に分離する分離ラインを一つ以上含む分離ラインリストを生成するステップと、
（ｂ）前記三次元変換装置の分離ライン選択部が、前記分離ラインリストに含まれた分離ラインのうち、前記多角形を分離する場合に前記多角形の重畳部分の数が減少する分離ラインを選択するステップと、
（ｃ）前記三次元変換装置の分離ライン適用部が、前記選択された分離ラインを適用し、前記多角形を分離するステップとを含むことを特徴とする三次元グラフィック環境での二次元高架道路データの三次元変換方法。
【請求項２】
前記（ａ）ステップは、
（ａ１）前記分離ラインリスト生成部の頂点選択部が、前記多角形の頂点のうち二頂点を選択するステップと、
（ａ２）前記分離ラインリスト生成部の分離ライン追加部が、前記選択された二頂点を連結するラインが前記多角形を構成する辺と交差せずに、前記多角形の内部にだけ存在する場合、前記ラインを前記分離ラインリストに追加するステップとを含むことを特徴とする請求項１に記載の三次元グラフィック環境での二次元高架道路データの三次元変換方法。
【請求項３】
（ｄ）前記三次元変換装置の三角化処理部が、前記多角形の分離された部分それぞれを一つ以上の三角形に分割するステップをさらに含むことを特徴とする請求項１に記載の三次元グラフィック環境での二次元高架道路データの三次元変換方法。
【請求項４】
前記（ｄ）ステップは、
（ｄ１）前記三角化処理部のイヤリスト生成部が、前記多角形の分離された部分の頂点のうちからイヤであるものを探してイヤリストを生成するステップと、
（ｄ２）前記三角化処理部のイヤ選択部が、前記イヤリストに含まれた頂点のうちから内部角が９０°に最も近いものを選択するステップと、
（ｄ３）前記三角化処理部の三角形分離部が、前記選択された頂点及びその両側辺からなる三角形を前記多角形の分離された部分で分離するステップとを含むことを特徴とする請求項３に記載の三次元グラフィック環境での二次元高架道路データの三次元変換方法。
【請求項５】
前記（ｄ１）ステップは、
前記イヤリスト生成部の候補頂点選択部が、前記多角形の分離された部分の頂点のうち一つを選択するステップと、
前記イヤリスト生成部の隣接頂点選択部が、前記多角形の分離された部分上で前記選択された頂点に隣接した両側頂点を選択するステップと、
前記イヤリスト生成部のイヤ追加部が、前記両側頂点を連結する線分が前記多角形の分離された部分を構成する辺と交差せずに、前記多角形の分離された部分の内部にだけ存在する場合、前記選択された頂点を前記イヤリストに追加するステップとを含むことを特徴とする請求項４に記載の三次元グラフィック環境での二次元高架道路データの三次元変換方法。
【請求項６】
二次元高架道路データを構成する多角形を２つの領域に分離する分離ラインを一つ以上含む分離ラインリストを生成する分離ラインリスト生成部と、
前記分離ラインリストに含まれた分離ラインのうち、前記多角形を分離する場合に前記多角形の重畳部分の数が減少する分離ラインを選択する分離ライン選択部と、
前記選択された分離ラインを適用し、前記多角形を分離する分離ライン適用部とを備えることを特徴とする三次元グラフィック環境での二次元高架道路データの三次元変換装置。
【請求項７】
前記分離ラインリスト生成部は、
前記多角形の頂点のうち二頂点を選択する頂点選択部と、
前記選択された二頂点を連結するラインが前記多角形を構成する辺と交差せずに、前記多角形の内部にだけ存在する場合、前記ラインを前記分離ラインリストに追加する分離ライン追加部とを備えることを特徴とする請求項６に記載の三次元グラフィック環境での二次元高架道路データの三次元変換装置。
【請求項８】
前記多角形の分離された部分それぞれを一つ以上の三角形に分割する三角化処理部をさらに備えることを特徴とする請求項６に記載の三次元グラフィック環境での二次元高架道路データの三次元変換装置。
【請求項９】
前記三角化処理部は、
前記多角形の分離された部分の頂点のうちからイヤであるものを探してイヤリストを生成するイヤリスト生成部と、
前記イヤリストに含まれた頂点のうちから内部角が９０°に最も近いものを選択するイヤ選択部と、
前記選択された頂点及びその両側辺からなる三角形を前記多角形の分離された部分で分離する三角形分離部とを備えることを特徴とする請求項８に記載の三次元グラフィック環境での二次元高架道路データの三次元変換装置。
【請求項１０】
前記イヤリスト生成部は、
前記多角形の分離された部分の頂点のうち一つを選択する候補頂点選択部と、
前記多角形の分離された部分上で前記選択された頂点に隣接した両側頂点を選択する隣接頂点選択部と、
前記両側頂点を連結する線分が前記多角形の分離された部分を構成する辺と交差せずに、前記多角形の分離された部分の内部にだけ存在する場合、前記選択された頂点を前記イヤリストに追加するイヤ追加部とを備えることを特徴とする請求項９に記載の三次元グラフィック環境での二次元高架道路データの三次元変換装置。
【請求項１１】
三次元グラフィック環境での二次元高架道路データの三次元視覚化装置を用いた三次元視覚化方法であって、
（ａ）前記三次元視覚化装置の重畳領域分離処理部が、二次元高架道路データを構成する多角形の重畳部分をそれぞれ分離するステップと、
（ｂ）前記三次元視覚化装置の三角化処理部が、前記多角形の分離された部分それぞれを一つ以上の三角形に分割するステップと、
（ｃ）前記三次元視覚化装置の高さ座標追加部が、前記分割された三角形の頂点それぞれに高さ座標を付加して三次元高架道路データを生成するステップと、
（ｄ）前記三次元視覚化装置の視覚化処理部が、前記生成された三次元高架道路データを視覚化するステップとを含むことを特徴とする三次元グラフィック環境での二次元高架道路データの三次元視覚化方法。
【請求項１２】
前記（ａ）ステップは、
（ａ１）前記重畳領域分離処理部の分離ラインリスト生成部が、前記二次元高架道路データを構成する多角形を２つの領域に分離する分離ラインを一つ以上含む分離ラインリストを生成するステップと、
（ａ２）前記重畳領域分離処理部の分離ライン選択部が、前記分離ラインリストに含まれた分離ラインのうち、前記多角形を分離する場合に前記多角形の重畳部分の数が減少する分離ラインを選択するステップと、
（ａ３）前記重畳領域分離処理部の分離ライン適用部が、前記選択された分離ラインを適用し、前記多角形を分離するステップとを含むことを特徴とする請求項１１に記載の三次元グラフィック環境での二次元高架道路データの三次元視覚化方法。
【請求項１３】
前記（ａ１）ステップは、
前記分離ラインリスト生成部の頂点選択部が、前記多角形の頂点のうち二頂点を選択するステップと、
前記分離ラインリスト生成部の分離ライン追加部が、前記選択された二頂点を連結するラインが前記多角形を構成する辺と交差せずに、前記多角形の内部にだけ存在する場合、前記ラインを前記分離ラインリストに追加するステップとを含むことを特徴とする請求項１２に記載の三次元グラフィック環境での二次元高架道路データの三次元視覚化方法。
【請求項１４】
前記（ｂ）ステップは、
（ｂ１）前記三角化処理部のイヤリスト生成部が、前記多角形の分離された部分の頂点のうちからイヤであるものを探してイヤリストを生成するステップと、
（ｂ２）前記三角化処理部のイヤ選択部が、前記イヤリストに含まれた頂点のうちから内部角が９０°に最も近いものを選択するステップと、
（ｂ３）前記三角化処理部の三角形分離部が、前記選択された頂点及びその両側辺からなる三角形を前記多角形の分離された部分で分離するステップとを含むことを特徴とする請求項１１に記載の三次元グラフィック環境での二次元高架道路データの三次元視覚化方法。
【請求項１５】
前記（ｂ１）ステップは、
前記イヤリスト生成部の候補頂点選択部が、前記多角形の分離された部分の頂点のうち一つを選択するステップと、
前記イヤリスト生成部の隣接頂点選択部が、前記多角形の分離された部分上で前記選択された頂点に隣接した両側頂点を選択するステップと、
前記イヤリスト生成部のイヤ追加部が、前記両側頂点を連結する線分が前記多角形の分離された部分を構成する辺と交差せずに、前記多角形の分離された部分の内部にだけ存在する場合、前記選択された頂点を前記イヤリストに追加するステップとを含むことを特徴とする請求項１４に記載の三次元グラフィック環境での二次元高架道路データの三次元視覚化方法。
【請求項１６】
前記（ｄ）ステップは、
（ｄ１）前記視覚化処理部の影視覚化部が、前記高架道路の影をレンダリングするステップと、
（ｄ２）前記視覚化処理部の高架道路本体視覚化部が、前記高架道路の上面、下面及びガードレールをレンダリングするステップとを含むことを特徴とする請求項１１に記載の三次元グラフィック環境での二次元高架道路データの三次元視覚化方法。
【請求項１７】
前記（ｄ１）ステップは、
前記影視覚化部の透明処理機能セット部が、前記高架道路の影をレンダリングする前に、レンダリング装置上の透明処理機能をセットし、ｚテスト機能を停止するステップと、
前記影視覚化部のｚテスト機能処理部が、前記高架道路の影をレンダリングした後、前記ｚテスト機能を再び始めるステップとを含むことを特徴とする請求項１６に記載の三次元グラフィック環境での二次元高架道路データの三次元視覚化方法。
【請求項１８】
前記（ｄ２）ステップは、
前記高架道路本体視覚化部の背面処理機能セット部が、レンダリング装置上の背面処理機能をセットするステップを含むことを特徴とする請求項１６に記載の三次元グラフィック環境での二次元高架道路データの三次元視覚化方法。
【請求項１９】
前記（ｄ２）ステップは、
前記高架道路本体視覚化部のテクスチャ適用部が、前記高架道路の上面にテクスチャを適用してレンダリングするステップを含むことを特徴とする請求項１６に記載の三次元グラフィック環境での二次元高架道路データの三次元視覚化方法。
【請求項２０】
二次元高架道路データを構成する多角形の重畳部分をそれぞれ分離する重畳領域分離処理部と、
前記多角形の分離された部分それぞれを一つ以上の三角形に分割する三角化処理部と、
前記分割された三角形の頂点それぞれに高さ座標を付加して三次元高架道路データを生成する高さ座標追加部と、
前記生成された三次元高架道路データを視覚化する視覚化処理部とを備えることを特徴とする三次元グラフィック環境での二次元高架道路データの三次元視覚化装置。
【請求項２１】
前記重畳領域分離処理部は、
前記二次元高架道路データを構成する多角形を２つの領域に分離する分離ラインを一つ以上含む分離ラインリストを生成する分離ラインリスト生成部と、
前記分離ラインリストに含まれた分離ラインのうち、前記多角形を分離する場合に前記多角形の重畳部分の数が減少する分離ラインを選択する分離ライン選択部と、
前記選択された分離ラインを適用し、前記多角形を分離する分離ライン適用部とを備えることを特徴とする請求項２０に記載の三次元グラフィック環境での二次元高架道路データの三次元視覚化装置。
【請求項２２】
前記分離ラインリスト生成部は、
前記多角形の頂点のうち二頂点を選択する頂点選択部と、
前記選択された二頂点を連結するラインが前記多角形を構成する辺と交差せずに、前記多角形の内部にだけ存在する場合、前記ラインを前記分離ラインリストに追加する分離ライン追加部とを備えることを特徴とする請求項２１に記載の三次元グラフィック環境での二次元高架道路データの三次元視覚化装置。
【請求項２３】
前記三角化処理部は、
前記多角形の分離された部分の頂点のうちからイヤであるものを探してイヤリストを生成するイヤリスト生成部と、
前記イヤリストに含まれた頂点のうちから内部角が９０°に最も近いものを選択するイヤ選択部と、
前記選択された頂点及びその両側辺からなる三角形を前記多角形の分離された部分で分離する三角形分離部とを備えることを特徴とする請求項２０に記載の三次元グラフィック環境での二次元高架道路データの三次元視覚化装置。
【請求項２４】
前記イヤリスト生成部は、
前記多角形の分離された部分の頂点のうち一つを選択する候補頂点選択部と、
前記多角形の分離された部分上で前記選択された頂点に隣接した両側頂点を選択する隣接頂点選択部と、
前記両側頂点を連結する線分が前記多角形の分離された部分を構成する辺と交差せずに、前記多角形の分離された部分の内部にだけ存在する場合、前記選択された頂点を前記イヤリストに追加するイヤ追加部とを備えることを特徴とする請求項２２に記載の三次元グラフィック環境での二次元高架道路データの三次元視覚化装置。
【請求項２５】
前記視覚化処理部は、
前記高架道路の影をレンダリングする影視覚化部と、
前記高架道路の上面、下面及びガードレールをレンダリングする高架道路本体視覚化部とを備えることを特徴とする請求項２０に記載の三次元グラフィック環境での二次元高架道路データの三次元視覚化装置。
【請求項２６】
前記影視覚化部は、
前記高架道路の影をレンダリングする前にレンダリング装置上の透明処理機能をセットする透明処理機能セット部と、
前記高架道路の影をレンダリングする前後に、前記レンダリング装置上のｚテスト機能を停止して再び始めるｚテスト機能処理部とを備えることを特徴とする請求項２５に記載の三次元グラフィック環境での二次元高架道路データの三次元視覚化装置。
【請求項２７】
前記高架道路本体視覚化部は、レンダリング装置上の背面処理機能をセットする背面処理機能セット部を備えることを特徴とする請求項２５に記載の三次元グラフィック環境での二次元高架道路データの三次元視覚化装置。
【請求項２８】
前記高架道路本体視覚化部は、
前記高架道路の上面にテクスチャを適用してレンダリングするテクスチャ適用部を備えることを特徴とする請求項２５に記載の三次元グラフィック環境での二次元高架道路データの三次元視覚化装置。
【請求項２９】
二次元高架道路データを構成する多角形を２つの領域に分離する分離ラインを一つ以上含む分離ラインリストを生成するステップと、
前記分離ラインリストに含まれた分離ラインのうち、前記多角形を分離する場合に前記多角形の重畳部分の数が減少する分離ラインを選択するステップと、
前記選択された分離ラインを適用し、前記多角形を分離するステップとをコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項３０】
二次元高架道路データを構成する多角形の重畳部分をそれぞれ分離するステップと、
前記多角形の分離された部分それぞれを一つ以上の三角形に分割するステップと、
前記分割された三角形の頂点それぞれに高さ座標を付加して三次元高架道路データを生成するステップと、
前記生成された三次元高架道路データを視覚化するステップとをコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体。
【請求項３１】
二次元高架道路データを構成する多角形を２つの領域に分離する分離ラインのうち、前記多角形の重なる部分の数が減少する分離ラインを選択するステップと、
前記選択された分離ラインを適用し、前記多角形を分離するステップとを含むことを特徴とする三次元グラフィック環境での二次元高架道路データの三次元視覚化方法。
【請求項３２】
二次元高架道路データを構成する多角形を２つの領域に分離する分離ラインのうち、前記多角形の重なる部分の数が減少する分離ラインを選択するステップと、
前記選択された分離ラインを適用し、前記多角形を分離するステップとを含むことを特徴とする三次元グラフィック環境での二次元高架道路データの三次元視覚化方法を実行するコンピュータプログラムを記録したコンピュータで読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、車両ナビゲーションに係り、特に三次元グラフィック環境での二次元高架道路データの三次元変換方法、装置及びプログラムを記録した記録媒体、ならびに、三次元グラフィック環境での二次元高架道路データの三次元視覚化方法、装置及びプログラムを記録した記録媒体に関する。
【背景技術】
【０００２】
最近、道路上の車両増加は、過度の交通渋滞を引き起こしている。かかる交通渋滞を解決するために、車両航法システム、すなわちナビゲーションが開発されている。かかるナビゲーションシステムの基本的な機能は、運行中である車両の位置を追跡し、道路地図上に正確に表示することであり、付随的な機能として、他の道路の交通状況を把握したり、または、ガソリンスタンド等についての情報を提供したりすることができる。
【０００３】
そして、ナビゲーションシステムにおいて地図がよく視覚化されていると、ユーザは所望する位置を迅速に探すことができる。さらに、車両が高速で運行している場合には、平面的よりも三次元的に視覚化（三次元視覚化）されているほうが、ユーザは便利さと安全性とを、より享受することができる。例えば、周囲の建物や地形等の、地物や地形が三次元状に描写されていると、ユーザは直観的にこれを認識できるために、便利さと安全性とを、より享受することができる。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
しかしながら、現在提供されているナビゲーションシステムは、二次元データを有しているだけであり、これを二次元的に視覚化（二次元視覚化）しているだけである。特に高架道路のような複雑な構造を有した立体物が二次元に視覚化されることによって、ユーザは混乱することもある。
【０００５】
図１Ａ及び図１Ｂは、二次元高架道路データを既存の方法で三次元視覚化した場合を表した図である。図１Ａにおいては、高さが相異なる二筋の道路が符号１で重なって高架となっている。もし、この高架を二次元で視覚化した場合には、二筋の道路が同一の平面上で互いに出合うように見える。これは、ユーザに道路の状況を正確に表示していないのである。
また、図１Ｂに示すように、二次元高架道路データが、前記二次元高架道路データを構成する多角形の各頂点の配列順に従って表示されることによって、ユーザに道路の形態を誤って提示してしまうこともある。
【０００６】
三次元グラフィック環境において、物体を表すデータが同一平面上に存在しない場合（これを、ｎｏｎ−ｃｏｐｌａｎａｒであるという）、または二次元平面への投影（ｐｒｏｊｅｃｔｉｏｎ）が交差する場合（これを、ｓｅｌｆ−ｉｎｔｅｒｓｅｃｔｉｏｎを有するという）には、正確に視覚化されないこともある。
そして、二次元高架道路データは、いずれの条件にも該当するので、二次元高架道路データに特別の処理を施すことによって、三次元高架道路データへと変換する必要が生じる。
【０００７】
そこで、本発明は、三次元グラフィック環境で二次元高架道路データを三次元に変換する方法及び装置、そしてかかる変換方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体を提供することを目的とする。
【０００８】
さらに、本発明は、前記変換方法を利用して三次元グラフィック環境で二次元高架道路データを三次元に視覚化する方法及び装置、そしてかかる視覚化方法をコンピュータで実行させるためのプログラムを記録したコンピュータで読み取り可能な記録媒体を提供することを目的とする。
【課題を解決するための手段】
【０００９】
前記技術的課題を解決するために、本発明に係る三次元グラフィック環境での二次元高架道路データの三次元変換方法は、二次元高架道路データを構成する多角形を２つの領域に分離する分離ラインを一つ以上含む分離ラインリストを生成するステップと、前記分離ラインリストに含まれた分離ラインのうち、前記多角形を分離する場合に前記多角形の重畳部分の数が減少する分離ラインを選択するステップと、前記選択された分離ラインを適用し、前記多角形を分離するステップとを含むことが望ましい。
【００１０】
前記技術的課題を解決するために、本発明に係る三次元グラフィック環境での二次元高架道路データの三次元変換装置は、二次元高架道路データを構成する多角形を２つの領域に分離する分離ラインを一つ以上含む分離ラインリストを生成する分離ラインリスト生成部と、前記分離ラインリストに含まれた分離ラインのうち、前記多角形を分離する場合に前記多角形の重畳部分の数が減少する分離ラインを選択する分離ライン選択部と、前記選択された分離ラインを適用し、前記多角形を分離する分離ライン適用部とを備えることが望ましい。
【００１１】
前記他の技術的課題を解決するために、本発明に係る三次元グラフィック環境での二次元高架道路データの三次元視覚化方法は、二次元高架道路データを構成する多角形の重畳部分をそれぞれ分離するステップと、前記多角形の分離された部分それぞれを一つ以上の三角形に分割するステップと、前記分割された三角形の頂点それぞれに高さ座標を付加して三次元高架道路データを生成するステップと、前記生成された三次元高架道路データを視覚化するステップとを含むことが望ましい。
【００１２】
前記他の技術的課題を解決するために、本発明に係る三次元グラフィック環境での二次元高架道路データの三次元視覚化装置は、二次元高架道路データを構成する多角形の重畳部分をそれぞれ分離する重畳領域分離部と、前記多角形の分離された部分それぞれを一つ以上の三角形に分割する三角化処理部と、前記分割された三角形の頂点それぞれに高さ座標を付加して三次元高架道路データを生成する高さ座標追加部と、前記生成された三次元高架道路データを視覚化する視覚化処理部とを備えることが望ましい。
【発明の効果】
【００１３】
本発明に係る三次元グラフィック環境での二次元高架道路データの三次元変換方法及び装置、そしてこれを利用した三次元グラフィック環境での二次元高架道路データの三次元視覚化方法及び装置によれば、分離ラインを選択的に適用して多角形の重畳部分を分離し、イヤ（ｅａｒ）カットアルゴリズムを適用して多角形を三角化処理し、生成された高架道路データの各部分別に多様な視覚化処理を行うことにより、二次元高架道路データを効果的に三次元高架道路データに変換でき、高架道路の多様な外観を表現できる。これにより、ユーザが高架道路の形態と位置とを直観的に認識できるので、ユーザに便利さと安全性とを提供できる。
【発明を実施するための最良の形態】
【００１４】
以下、添付された図面を参照し、本実施形態に係る三次元グラフィック環境での二次元高架道路データの三次元変換方法及び装置、そしてこれを利用した三次元グラフィック環境での二次元高架道路データの三次元視覚化方法及び装置について詳細に説明する。
【００１５】
図２は、本実施形態に係る二次元高架道路データの三次元視覚化装置の構成を表したブロック図である。図２に示すように、本実施形態に係る二次元高架道路データの三次元視覚化装置は、重畳領域分離処理部１００、三角化処理部２００、高さ座標追加部３００、及び視覚化処理部４００を備えることが望ましい。
【００１６】
重畳領域分離処理部１００は、二次元高架道路データ１０を構成する多角形の重畳部分をそれぞれ分離するものである。
三角化処理部２００は、多角形の分離された部分１２それぞれを一つ以上の三角形１４に分割するものである。
高さ座標追加部３００は、分割された三角形１４の頂点それぞれに高さ座標を付加し、三次元高架道路データ１６を生成するものである。
視覚化処理部４００は、三次元高架道路データ１６を視覚化するものである。
【００１７】
図３は、図２で示した三次元視覚化装置で行われる二次元高架道路データの三次元視覚化方法の各ステップを表したフローチャートである。
まず、重畳領域分離処理部１００は、二次元高架道路データ１０を構成する多角形の重畳部分をそれぞれ分離する（Ｓ１００）。多角形の重畳部分、すなわち交差（ｉｎｔｅｒｓｅｃｔｉｏｎ）は、二次元高架道路データ１０の視覚化において問題が発生する部分である。従って、データを正確に視覚化するためには、１つの多角形内に重畳部分があってはならない。
【００１８】
多角形の重畳部分がそれぞれ分離された後、三角化処理部２００は、分離された部分１２それぞれを一つ以上の三角形に分割する（Ｓ２００）。グラフィックシステムで最も処理しやすいデータ形態は、三角形である。従って、複雑な多角形を三角形に分割する。本実施形態に係る三角化処理部２００では、イヤカットアルゴリズムを使用する。
【００１９】
分離された部分１２のそれぞれを一つ以上の三角形に分割した後、高さ座標追加部３００は、分割された三角形１４の頂点それぞれに高さ座標を付加する（Ｓ３００）。これにより、三次元高架道路データ１６が生成される。
【００２０】
視覚化処理部４００は、生成された三次元高架道路データ１６を視覚化する（Ｓ４００）。
【００２１】
図４は、図２で示した重畳領域分離処理部１００の構成を表したブロック図である。図４に示すように、本実施形態に係る重畳領域分離処理部１００は、分離ラインリスト生成部１１０、分離ライン選択部１２０、及び分離ライン適用部１３０を備えることが望ましい。
分離ラインリスト生成部１１０は、分離ラインリスト２０を生成するものである。ここで、分離ラインリスト２０とは、分離ラインを一つ以上含むリストをいう。分離ラインとは、二次元高架道路データ１８を構成する多角形を二つ以上の領域に分離するラインをいう。
分離ライン選択部１２０は、分離ラインリスト２０に含まれた分離ラインの中から、多角形を分離するために適用した場合に、多角形の重畳部分、すなわち交差の数が減少する分離ライン２２を選択するものである。
分離ライン適用部１３０は、分離ライン選択部１２０で選択した分離ライン２２を適用して多角形を分離するものである。
【００２２】
図５は、図３で示した多角形の重畳部分の分離方法（Ｓ１００ステップ）の詳細な各ステップを表したフローチャートである。図５に示すように、本実施形態に係る重畳部分の分離方法（Ｓ１００）は、前記説明された分離ラインリスト２０の生成ステップ（Ｓ１２０）、分離ライン２２の選択ステップ（Ｓ１３０）、及び分離ライン２２の適用ステップ（Ｓ１４０）を多角形内に交差がなくなるまで反復することが望ましい。すなわち、分離しようとする多角形内に交差が存在しているか否かを判断し（Ｓ１１０）、交差がないと判断した場合には（Ｓ１１０で「いいえ」）、処理を終了するが、交差が存在すると判断した場合には（Ｓ１１０で「はい」）、前記Ｓ１２０ないしＳ１４０ステップを反復する。
【００２３】
前記したように、分離ラインは、多角形を二つ以上の領域に分離するラインをいう。そして、分離ラインは、多角形を構成する頂点のうち２つの頂点を連結し、多角形を構成する辺と交差せず、多角形の内部にだけ存在する性質を有するものである。従って、分離ラインを探し出すためには、まず、多角形の頂点のうち二頂点を選択し、次に、選択された二頂点を連結するラインが多角形を構成する辺と交差しているか否かを判断し、このラインが多角形の内部にだけ存在しているか否かを検査する処理が必要となる。このような処理を経て条件が満たされたラインが、分離ラインになる。探し出された分離ラインは分離ラインリスト２０に追加される。
【００２４】
２本のラインが互いに交差しているか否かを検査するために、ベクトルの外積を利用する交差検査方法を用いることができる。図６Ａないし図６Ｃ、および、図７Ａないし図７Ｃを参照し、ベクトルの外積を利用した２本のラインの交差検査方法を説明する。
【００２５】
図６Ａないし図６Ｃは、ベクトルの外積を利用した交差検査方法を用いて、２本のラインが互いに交差しない場合を説明するための図である。図６Ａにおいて、Ｐ１とＰ２とが１つのラインをなしており、Ｐ３とＰ４とが１つのラインをなしている。図６Ａに示すように、２本のラインは、互いに交差していない。そして、図６Ｂに示すように、Ｐ１を開始点とし、Ｐ２を終了点とするベクトルを設定する。このベクトルと、Ｐ１を開始点としてＰ３を終了点とするベクトルとの外積を計算する。また、図６Ｃに示すように、Ｐ１を開始点とし、Ｐ２を終了点とするベクトルと、Ｐ１を開始点としてＰ４を終了点とするベクトルとの外積を計算する。２つの外積が同じ符号を有する場合、最初のベクトル（Ｐ１を開始点とし、Ｐ２を終了点とするベクトル）に対してＰ３とＰ４とが同じ方向に位置するので、２本のラインは互いに交差していないといえる。
【００２６】
図７Ａないし図７Ｃは、ベクトルの外積を利用した交差検査方法を用いて、２本のラインが互いに交差する場合を説明するための図である。図６Ａないし図６Ｃを参照して説明した前記交差検査方法と同様に、２つの外積を求める。図７Ａないし図７Ｃは、図６Ａないし図６Ｃとは異なり、Ｐ３とＰ４とが相異なる方向に位置するので、２つの外積が相異なる符号を有する。従って、２本のラインは互いに交差しているといえる。
このように、与えられたラインを構成する頂点で適切にベクトルを生成した後、それぞれの外積を求める交差検査方法により、２本のラインが交差しているか否かを容易に判断できる。
【００２７】
図８は、任意に与えられた多角形について、各頂点を連結するラインが分離ラインであるか否かを調べるための一例を表す図である。図８に示すように、ラインＥ１は、多角形の外部にあるので分離ラインではない。すなわち、ラインＥ１は、これを適用しても多角形を２つの領域に分離できない。また、ラインＥ３は、多角形をなす線分と互いに交差するので、分離ラインではない。
ラインＥ２は、多角形をなす線分と交差せず、また、多角形の内部に存在する。従って、ラインＥ２は、分離ラインである。従って、ラインＥ２を用いて、図８に示した多角形の元の頂点をそれぞれの頂点として含む２つの多角形に分離する。
【００２８】
分離ラインリスト２０が生成された後には、分離ラインリスト２０に含まれる分離ラインのうちから多角形の交差の数を減少させる分離ライン２２を選択する。
図９Ａないし図９Ｃは、交差の数を減少させる分離ライン２２を選択する場合及び交差の数を減少させない分離ラインを選択する場合をそれぞれ説明するための図である。図９Ａは元の多角形を示す図であって、元の多角形は、４個の交差を有している。図９Ａに示す分離ラインＳ１と分離ラインＳ２とを選択して比較する。
【００２９】
図９Ｂは、元の多角形から分離ラインＳ１を選択して多角形を分離した場合を説明するための図である。図９Ｂに示すように、分離ラインＳ１の適用により、元の多角形は、多角形Ｐ１と多角形Ｐ２とに分離される。多角形を分離した後において、２つの多角形Ｐ１，Ｐ２は、いずれも交差を有していない。従って、分離ラインＳ１の適用により、交差の数は、４個から０個に減少する。従って、分離ライン選択部１２０は、分離ラインリスト２０に含まれる分離ラインのうちから、分離ラインＳ１を選択する。
図９Ｃは、元の多角形から分離ラインＳ２を選択して多角形を分離した場合を説明するための図である。図９Ｃに示すように、分離ラインＳ２の適用により、元の多角形は、多角形Ｐ３と多角形Ｐ４とに分離される。多角形を分離した後において、多角形Ｐ３は、相変らず４個の交差を有する。従って、分離ラインＳ２の適用によっても交差の数は減少しない。従って、分離ライン選択部１２０は、分離ラインリスト２０に含まれる分離ラインのうちから、分離ラインＳ２を選択しない。
【００３０】
図１０Ａは、高架道路データの一例を表した図であって、多角形の分離前の様子を表した図である。
前記したように、分離ライン２２を選択し、適用することによって、図１０Ａに図示された多角形の重畳部分をいずれも分離できる。
図１０Ｂは、図１０Ａで示した高架道路データについて、多角形の分離後の様子を表した図である。
図１０Ｂに示すように、分離ラインＳＬ０１ないしＳＬ０６を多角形の分離に適用することによって、図１０Ａの多角形は、重畳部分のない部分に分けられる。
【００３１】
図１１は、図２に示された三角化処理部２００の構成を表したブロック図である。図１１に示すように、本実施形態に係る三角化処理部２００は、イヤリスト生成部２１０、イヤ選択部２２０、及び三角形分離部２３０を備えることが望ましい。
【００３２】
図１２は、図１１に示した三角化処理部２００で行われる三角化処理方法の詳細な各ステップを表したフローチャートである。
イヤリスト生成部２１０は、多角形の分離された部分２６の頂点のうちからイヤであるものを探してイヤリスト２８を生成する（Ｓ２２０）。ここで、「イヤ」とは、多角形の頂点のうちから隣接した両側頂点を連結した線分が多角形の分離された部分２６を構成する辺と交差せず、多角形の分離された部分２６の内部にだけ存在するものをいう。
このために、イヤリスト生成部２１０は、多角形の分離された部分２６の頂点のうち一つを選択し、多角形の分離された部分２６上で選択された頂点に隣接した両側頂点を選択し、両側頂点を連結する線分が多角形の分離された部分２６を構成する辺と交差せず、多角形の分離された部分２６の内部にだけ存在しているか否かを判断する処理を行う。そして、イヤリスト生成部２１０は、このような処理を経て条件が満たされた頂点をイヤリスト２８に追加する。
【００３３】
イヤ選択部２２０は、イヤリスト２８に含まれた頂点のうちから内部角が９０°に最も近いもの（選択された頂点）３０を選択する（Ｓ２３０）。これは、三角化された結果が選択された頂点３０を直角にする直角三角形に近いものとするためのものである。このように三角化することにより、頂点の属する線分と、この頂点と異なる頂点から構成される線分とが直角近くに連結されて自然な道路を構成できるようになる。
【００３４】
三角形分離部２３０は、多角形の分離された部分２６から、選択された頂点３０及びその両側辺からなる三角形を分離する（Ｓ２４０）。
【００３５】
三角化処理部２００は、三角形を分離した残りの部分が三角形であるか否かを判断する（Ｓ２１０）。もし残った部分が三角形ならば（Ｓ２１０で「はい」）、三角化処理が完了したわけであるので、終了する。しかし、残った部分が三角形でなければ（Ｓ２１０で「いいえ」）、三角化処理を完了するために、Ｓ２２０ステップないしＳ２４０ステップを反復する。
【００３６】
図１３Ａないし図１３Ｃは、多角形を三角化処理する一例を表した図である。図１３Ａは、任意に与えられた多角形に対してイヤを求めたものを表した図である。図１３Ａに示すように、頂点Ｖ１ないしＶ７のうち、イヤは、Ｖ１、Ｖ３及びＶ６の３個である。
例えば、頂点Ｖ１の場合、頂点Ｖ１に隣接した両側頂点は、Ｖ２及びＶ９であり、両側頂点を連結した線分Ｅ１は、与えられた多角形の辺と交差せず、多角形の内部にだけ存在する。従って、頂点Ｖ１は、イヤである。
例えば、頂点Ｖ２の場合、隣接した両側頂点は、Ｖ１及びＶ３である。両側頂点を連結した線分は、多角形外部に存在するので、頂点Ｖ２はイヤではない。
【００３７】
例えば、頂点Ｖ３の場合、隣接した両側頂点を連結した線分Ｅ３は、与えられた多角形の辺と交差せず、多角形の内部にだけ存在する。従って、頂点Ｖ３は、イヤである。
例えば、頂点Ｖ７の場合、隣接した両側頂点Ｖ６及びＶ８を連結した線分Ｅ７は、多角形の辺と交差する。従って、頂点Ｖ７はイヤではない。
【００３８】
かかる判断過程を介し、イヤリスト２８に頂点Ｖ１、Ｖ３及びＶ６が追加される。
イヤ選択部２２０では、イヤのうちから内部角が９０°に最も近いものを選択するが、図１３Ａに示すように、三頂点Ｖ１、Ｖ３及びＶ６のうちから対応する内部角が最も９０°に近いものは頂点Ｖ３である。
【００３９】
図１３Ｂは、頂点Ｖ３及び両側辺からなる三角形を分離した後の様子を表した図である。１つの三角形を分離した後、残った図形がまだ三角形でないので、三角化処理を反復しなければならない。
【００４０】
図１３Ｃは、かかる三角化処理を反復し、多角形が複数の三角形に分割されたものを表した図である。
【００４１】
次に、図２に示した重畳領域処理部１００、三角化処理部２００、及び高さ座標追加部３００は、本実施形態に係る二次元高架道路データの三次元変換装置を構成する。本実施形態に係る二次元高架道路データの三次元視覚化装置は、これらを利用する。
視覚化処理部４００は、重畳領域処理部１００、三角化処理部２００、及び高さ座標追加部３００によって三次元変換された三次元高架道路データ１６を視覚化処理する処理部である。視覚化処理部４００は、生成された三次元高架道路データ１６を構成部分別に分けて他の処理方式を適用する。
【００４２】
視覚化処理部４００は、まず高架道路の影部分を視覚化する。影は、高度を０として底に視覚化する。また、輝く効果を出すために透明処理を施す。このために、レンダリング装置上の透明処理機能をセットする。
影を視覚化する場合、底とのｚ−ファイティング現象を防止するために、レンダリング装置上のｚテスト機能を停止しなければならない（ｚ−ｔｅｓｔ  ｏｆｆ）。その後、底をレンダリングし、高架道路の影をレンダリングする。影のレンダリングが終わった後には、ｚテスト機能を再び始める（ｚ−ｔｅｓｔ  ｏｎ）。
【００４３】
影をレンダリングした後には、高架道路の上面、下面、そしてガードレール部分をそれぞれレンダリングする。このために、まず、レンダリング装置上の背面処理（ｂａｃｋｆａｃｅ  ｃｕｌｌｉｎｇ）機能をセットする。高架道路の上面は、テクスチャマッピング（ｔｅｘｔｕｒｅ  ｍａｐｐｉｎｇ）を行い、単面レンダリングを行う。高架道路の下面は、それぞれの三角形に色を代入する方式、すなわちカラードポリゴン（ｃｏｌｏｒｅｄ  ｐｏｌｙｇｏｎ）方式を利用し、単面レンダリングを行う。高架道路のガードレール部分は、下面のようにカラードポリゴン方式を利用し、両面レンダリングを行う。
【００４４】
図１４Ａないし図１４Ｃは、高架道路の上面にテクスチャをマッピングする方法の一例を表した図である。図１４Ａは、基本テクスチャの様子を表した図である。図１４Ａのテクスチャを図１４Ｂに示した高架道路多角形にマッピングするためには、テクスチャ座標を計算しなければならない。これは、実際の座標をレングス定数で割る方式で求める。
図１４Ｃは、テクスチャマッピングのためのレングス定数が２である場合を表した図である。実際座標であるｘ座標値を２で割った値がテクスチャ座標のｕ座標値になる。
【００４５】
図１５は、かかる視覚化方法を適用して生成された高架道路の映像の一例を表した図である。図１５に示すように、高架道路の上面４４は、テクスチャをマッピングし、高架道路の下面４６は、カラードマッピング方式の単面レンダリングを適用した。また、高架道路の影４２は、底に視覚化されており、高架道路のガードレール４８は、カラードマッピング方式の両面レンダリングを適用したことが分かる。
【００４６】
本実施形態は、コンピュータで読み取り可能な記録媒体にコンピュータ（情報処理機能を有する装置をいずれも含む）で読み取り可能なコードとして具現することが可能である。コンピュータで読み取り可能な記録媒体は、コンピュータシステムによって読み取り可能なデータが記録されるあらゆる種類の記録装置を含む。コンピュータで読み取り可能な記録装置の例としては、ＲＯＭ（Ｒｅａｎ−Ｏｎｌｙ  Ｍｅｍｏｒｙ）、ＲＡＭ（Ｒａｎｄｏｍ−Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＣＤ−ＲＯＭ、磁気テープ、フレキシブルディスク、光データ記録装置等がある。
【００４７】
たとえ、前記実施形態において、本発明の新規な特徴に焦点を合わせて説明しているにしても、本技術分野で当業者は、本発明の範囲を外れずに前記実施形態で説明された装置及び方法の形態及び細部事項について、多様な削除、代替、及び変更が可能であるということが理解できるであろう。従って、本発明の範囲は、前記実施形態ではなく、特許請求の範囲により定義される。特許請求の範囲の均等範囲中のあらゆる変形は、本発明の範囲に包摂される。
【産業上の利用可能性】
【００４８】
本発明に係る三次元グラフィック環境での二次元高架道路データの三次元変換方法及び装置、そしてこれを利用した三次元グラフィック環境での二次元高架道路データの三次元視覚化方法及び装置は、例えばナビゲーション関連技術に効果的に適用可能である。
【図面の簡単な説明】
【００４９】
【図１Ａ】高架道路データを既存の方法で三次元視覚化した場合を表した図である。
【図１Ｂ】高架道路データを既存の方法で三次元視覚化した場合を表した図である。
【図２】本実施形態に係る二次元高架道路データの三次元視覚化装置の構成を表したブロック図である。
【図３】本実施形態に係る二次元高架道路データの三次元視覚化方法の各ステップを表したフローチャートである。
【図４】本実施形態に係る重畳領域分離処理部の構成を表したブロック図である。
【図５】本実施形態に係る多角形の重畳部分の分離方法の詳細な各ステップを表したフローチャートである。
【図６Ａ】ベクトルの外積を利用した交差検査方法を用いて、２本のラインが互いに交差しない場合を説明するための図である。
【図６Ｂ】ベクトルの外積を利用した交差検査方法を用いて、２本のラインが互いに交差しない場合を説明するための図である。
【図６Ｃ】ベクトルの外積を利用した交差検査方法を用いて、２本のラインが互いに交差しない場合を説明するための図である。
【図７Ａ】ベクトルの外積を利用した交差検査方法を用いて、２本のラインが互いに交差する場合を説明するための図である。
【図７Ｂ】ベクトルの外積を利用した交差検査方法を用いて、２本のラインが互いに交差する場合を説明するための図である。
【図７Ｃ】ベクトルの外積を利用した交差検査方法を用いて、２本のラインが互いに交差する場合を説明するための図である。
【図８】任意に与えられた多角形について、各頂点を連結するラインが分離ラインであるか否かを調べるための一例を表す図である。
【図９Ａ】交差の数が減少する分離ラインを選択する場合及び交差の数が減少しない分離ラインを選択する場合を説明するための図である。
【図９Ｂ】交差の数が減少する分離ラインを選択する場合及び交差の数が減少しない分離ラインを選択する場合を説明するための図である。
【図９Ｃ】交差の数が減少する分離ラインを選択する場合及び交差の数が減少しない分離ラインを選択する場合を説明するための図である。
【図１０Ａ】高架道路データの一例を表した図であって、多角形の分離前の様子を表した図である。
【図１０Ｂ】高架道路データの一例を表した図であって、多角形の分離後の様子を表した図である。
【図１１】本実施形態に係る三角化処理部の構成を表したブロック図である。
【図１２】本実施形態に係る三角化処理方法の詳細な各ステップを表したフローチャートである。
【図１３Ａ】多角形を三角化処理する一例を表した図である。
【図１３Ｂ】多角形を三角化処理する一例を表した図である。
【図１３Ｃ】多角形を三角化処理する一例を表した図である。
【図１４Ａ】高架道路の上面にテクスチャをマッピングする方法の一例を表した図である。
【図１４Ｂ】高架道路の上面にテクスチャをマッピングする方法の一例を表した図である。
【図１４Ｃ】高架道路の上面にテクスチャをマッピングする方法の一例を表した図である。
【図１５】本実施形態に係る視覚化方法を適用して生成された高架道路の映像の一例を表した図である。
【符号の説明】
【００５０】
１０    二次元高架道路データ
１２    多角形の分離された部分
１４    一つ以上の三角形
１６    三次元高架道路データ
１００  重畳領域分離処理部
２００  三角化処理部
３００  高さ座標追加部
４００  視覚化処理部
【図１Ａ】
2006209767.tif 000003
【図１Ｂ】
2006209767.tif 000004
【図２】
2006209767.tif 000005
【図３】
2006209767.tif 000006
【図４】
2006209767.tif 000007
【図５】
2006209767.tif 000008
【図６Ａ】
2006209767.tif 000009
【図６Ｂ】
2006209767.tif 000010
【図６Ｃ】
2006209767.tif 000011
【図７Ａ】
2006209767.tif 000012
【図７Ｂ】
2006209767.tif 000013
【図７Ｃ】
2006209767.tif 000014
【図８】
2006209767.tif 000015
【図９Ａ】
2006209767.tif 000016
【図９Ｂ】
2006209767.tif 000017
【図９Ｃ】
2006209767.tif 000018
【図１０Ａ】
2006209767.tif 000019
【図１０Ｂ】
2006209767.tif 000020
【図１１】
2006209767.tif 000021
【図１２】
2006209767.tif 000022
【図１３Ａ】
2006209767.tif 000023
【図１３Ｂ】
2006209767.tif 000024
【図１３Ｃ】
2006209767.tif 000025
【図１４Ａ】
2006209767.tif 000026
【図１４Ｂ】
2006209767.tif 000027
【図１４Ｃ】
2006209767.tif 000028
【図１５】
2006209767.tif 000029