(57)【特許請求の範囲】
【請求項１】
立体物に関する立体図データを用いて３次元空間を２次元表示するための３次元データ処理装置において、
各立体物の立体図データを用いて当該立体物のバウンディングボリュームを生成するバウンディングボリューム生成手段と、設定された視点に基づいてビューボリュームを設定するビューボリューム設定手段と、生成された前記バウンディングボリュームを用いて前記ビューボリューム内における描画対象となる立体物を判定するカリング処理手段とを備え、
前記バウンディングボリューム生成手段は、処理対象となる立体物の底面に平行な横断面を内包する外枠四角形を算定し、当該外枠四角形に内接する内枠四角形を算定し、当該内枠四角形を基準面として当該立体物のバウンディングボリュームを生成する３次元データ処理装置。
【請求項２】
前記内枠四角形は、ｎを自然数として、前記外枠四角形の各辺のｎ等分点を結んで得られる四角形である請求項１に記載の３次元データ処理装置。
【請求項３】
前記内枠四角形は前記外枠四角形の各辺の中点を結んで得られる四角形である請求項１に記載の３次元データ処理装置。
【請求項４】
前記外枠四角形は、設定された基準横軸と基準縦軸に平行な辺を有するように算定される請求項１から３のいずれか一項に記載の３次元データ処理装置。
【請求項５】
前記バウンディングボリューム生成手段は、処理対象となる立体物の複数の高さレベル毎に得られる前記横断面から複数の内枠四角形を求めて、前記複数の内枠四角形を基準面として当該立体物のバウンディングボリュームを生成する請求項１から４のいずれか一項に記載の３次元データ処理装置。
【請求項６】
前記カリング処理手段はオクルージョンカリング手法に基づいて立体物描画の要否を決定する請求項１から５のいずれか一項に記載の３次元データ処理装置。
【請求項７】
請求項１から６のいずれか一項に記載の３次元データ処理装置を備え、かつ
前記カリング処理手段による判定結果を参照しながら前記ビューボリュームにおける３次元画像を生成する３次元画像描画手段を備えた３次元画像生成装置。
【請求項８】
請求項７に記載の３次元画像生成装置を備えたナビゲーション装置において、
前記視点は、自車位置情報検出手段によって検出された自車位置に基づいて決定され、前記視点からの視軸は案内経路に沿うように決定されるナビゲーション装置。
【請求項９】
立体物に関する立体図データを用いて３次元空間を２次元表示するためのプログラムをコンピュータに実現させる３次元データ処理プログラムであって、
各立体物の立体図データを用いて当該立体物のバウンディングボリュームを生成するバウンディングボリューム生成機能と、設定された視点に基づいてビューボリュームを設定するビューボリューム設定機能と、生成された前記バウンディングボリュームを用いて前記ビューボリューム内における描画対象となる立体物を判定するカリング処理機能とをコンピュータに実現させ、
前記バウンディングボリューム生成機能は、データベースから読み出された各立体物の立体図データから処理対象となる立体物の底面に平行な横断面を読み取る又は算定する機能と、得られた前記平面外形輪郭に内包する外枠四角形を算定する機能と、前記外枠四角形に内接する内枠四角形を算定する機能と、前記内枠四角形を基準面として当該立体物のバウンディングボリュームを生成する機能とを有する３次元データ処理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、立体物に関する立体図データを用いて３次元空間を２次元表示するための３次元データ処理技術、この３次元データ処理技術を用いた３次元画像生成装置、及びこの３次元画像生成装置を組み込んだナビゲーション装置に関する。
【背景技術】
【０００２】
立体物に関する立体図データを用いて３次元空間を２次元表示するには、つまり３次元グラフィックスのレンダリングを行うためには、コンピュータによる演算処理が中心的な役割を果たしている。グラフィック処理機能を有するコンピュータが高性能化及び高集積化（１チップ化）されたことにより、種々の技術分野に、例えば自動車などに搭載されるナビゲーション装置などにも３次元グラフィックスのレンダリング機能が実装され、立体地図表示が実現されている。
【０００３】
このような３次元グラフィックスのレンダリングに用いられるレイトレーシング手法では、視点から立体物の方向に向かう光線を追跡し、その光線が物体と交差すればその交点における物体の光の状態を求め、それを画像面に投影させることで２次元の画像を求めている。光線と立体物との交点を求める交点計算に非常に時間がかかるため、その高速化方法が必要となる。例えば、２次元表示の対象となる３次元空間であるビューボリューム内の不要な立体物を事前にレンダリング対象から除外しておくと、レンダリング処理（３次元画像描画処理）は軽くなる。そのような除外処理は、カリング処理とも呼ばれるが、このカリング処理をさらに高速化するためバウンディングボリュームを用いる方法がある。
【０００４】
従来のバウンディングボリュームは、球体（バウンディングキューブ）や直方体（バウンディングキューブ）といった単純な形状を有し、１又は複数の立体物を内包するものである。つまり、バウンディングボリュームは、立体物全体を覆うことができる単純な形状体である。このバウンディングボリュームと光線とが交差するか否かを判定し、バウンディングボリュームと光線とが交差するバウンディングボリュームに内包している立体物のみを最終的な描画処理に送り出し、不要な立体物と光線との交点を求める演算を省略することで描画処理の高速化を図る。このようなバウンディングボリュームの種々の設定方法が以前から知られている（例えば、特許文献１、特許文献２）。
【０００５】
【特許文献１】特開平６−１６８３４０号公報（段落番号０００１−００１７）
【特許文献２】特開２００３ー２７１９８８号公報（段落番号０００２−００２２）
【発明の開示】
【発明が解決しようとする課題】
【０００６】
上述した従来のバウンディングボリュームの設定方法では、立体物を内包するようにバウンディングボリュームを設定していたので、バウンディングボリュームはどの方向からもその立体物以上の大きさとなる。従って、視点手前側に位置する前方バウンディングボリュームの後側に位置する後方バウンディングボリュームが大きく表現されすぎた前方バウンディングボリュームの陰に隠れてカリングされると、最終的にレンダリングされた３次元画像には見えるはずの立体物が見えない（描画されない）という問題が生じる。特に、地図ナビゲーションシステムなどで用いられるバウンディングボリュームとしては、一般的に東経北緯座標軸といった基準縦軸と基準横軸に平行となる辺を断面とする基準軸平行バウンディングボックスが用いられることから、バウンディングボックスは実際の立体物（立体物のポリゴン）よりかなり大きくなり、この問題は大きくなる。また、軸平行バウンディングボックスを用いた場合、視点から立体物への視軸が基準軸に対して斜めになっていると、軸平行バウンディングボックスによって遮蔽される領域が、実際の立体物によって遮蔽される領域より著しく大きくなり、先の問題がさらに大きくなる。
本発明は、上記の課題に鑑みてなされたものであり、バウンディングボリュームとして単純化された形状体を生成しながらも、最終的にレンダリングされた３次元画像における違和感を低減する３次元データ処理技術、そのような３次元データ処理技術を用いた３次元画像生成装置、及びその３次元画像生成装置を組み込んだナビゲーション装置を提供することにある。
【課題を解決するための手段】
【０００７】
上記目的を達成するための本発明に係わる、立体物に関する立体図データを用いて３次元空間を２次元表示するための３次元データ処理装置の特徴構成は、各立体物の立体図データを用いて当該立体物のバウンディングボリュームを生成するバウンディングボリューム生成手段と、設定された視点に基づいてビューボリュームを設定するビューボリューム設定手段と、生成された前記バウンディングボリュームを用いて前記ビューボリューム内における描画対象となる立体物を判定するカリング処理手段とを備え、前記バウンディングボリューム生成手段は、処理対象となる立体物の底面に平行な横断面を内包する外枠四角形を算定し、当該外枠四角形に内接する内枠四角形を算定し、当該内枠四角形を基準面として当該立体物のバウンディングボリュームを生成する点にある。
【０００８】
この特徴構成によれば、立体物の底面に平行な横断面を内包する外枠四角形に内接する内枠四角形を基準面、つまり断面（地面レベルでは底面）としてその立体物の高さ分だけ立ち上げたバウンディングボリュームが設定される。この基準面は、外枠四角形に内接する内枠四角形であるから、当然、この内枠四角形と外枠四角形とを比較するとどの方向からも内枠四角形の幅は外枠四角形の幅以下となる。従って、内包している立体物より大きく表現され過ぎたバウンディングボリュームのために不必要にカリングされる視点後方のバウンディングボリュームが多くなり、最終的にレンダリングされた３次元画像には見えるはずの立体物が見えない（描画されない）という従来の問題は低減される。また、本発明によるバウンディングボリュームの基準面となる内枠四角形は前記外枠四角形に内接しているので、当該バウンディングボリュームが実際の立体物より小さく表現され過ぎることによる弊害も抑制されたものとなる。
【０００９】
ここで、前記内枠四角形は、ｎを自然数として、前記外枠四角形の各辺のｎ等分点を結んで得られる四角形であると好適である。幾何学的手法を得られるこの内枠四角形の形状は、立体物形状を概ねカバーしながらも外枠四角形よりも小さくなるから、内枠四角形から生成されたバウンディングボリュームが実際の立体物によって遮蔽される領域より著しく大きくなるという従来の欠点を低減することができる。特に、前記内枠四角形として前記外枠四角形の各辺の中点を結んで得られる四角形が算定されると好適である。これにより、例えば、外枠四角形が長方形の場合には内枠四角形は菱形となり、内枠四角形の各頂点が外枠四角形の各辺に位置するので、その形状自体は立体物形状を概ねカバーしながらも、外枠四角形の半分となっており、生成されたバウンディングボリュームが実際の立体物によって遮蔽される領域より著しく大きくなるという従来の欠点を大幅に低減することができる。また、各辺が等しくなるので、その幾何学的演算の負荷が、一般的な多角形より低い。
【００１０】
さらに、前記外枠四角形は、設定された基準横軸と基準縦軸に平行な辺を有するように算定されると好適である。これにより全てのバウンディングボリュームは同じ向きの長方形となり、演算上の扱いが簡単となる。また、菱形形状の内枠四角形の特徴と組み合わせると、基準横軸や基準縦軸に対して斜めの視軸をもつビューボリュームにおいても、ほぼ正しくカリング処理の判定を行うことができる。なお、この３次元データ処理装置がナビゲーション装置などの地図情報システムに適用されることを考慮すると、基準横軸と基準縦軸として、緯線と経線を採用すると好都合である。
【００１１】
さらに、前記バウンディングボリューム生成手段を、処理対象となる立体物の複数の高さレベル毎に得られる前記横断面から複数の内枠四角形を求めて、前記複数の内枠四角形を基準面として当該立体物のバウンディングボリュームを生成するように構成すると好適である。この構成では、バウンディングボリューム生成手段は、所定の高さレベル毎に複数の内枠四角形を算定してサブバウンディングボリュームを生成し、これらのサブバウンディングボリュームを積み重ねて最終的なバウンディングボリュームが生成されるので、高さレベルによってその横断面の大きさが大きく異なるような立体物を扱う場合でも正確なカリング判定が可能となる。特に、建造物などでは、低層階と高層階ではその横断面が異なる場合が少なくないので、立体物が実質的に建造物である立体地図画像などの描画には適している。
【００１２】
カリング処理では、あるバウンディングボリュームが他のバウンディングボリュームによって完全に遮蔽されている時のみ、描画対象から除外するオクルージョンカリングを用いると演算速度に関して好都合である。このため、好適な実施形態の１つでは、前記カリング処理手段はオクルージョンカリング手法に基づいて立体物描画の要否を決定するように構成されている。
【００１３】
本発明は、上述した３次元データ処理装置を組み込んだ３次元画像生成装置も権利対象としている。そのような３次元画像生成装置は、上述した本発明による３次元データ処理装置の種々の特徴構成とともに、前記カリング処理手段による判定結果を参照しながら前記ビューボリュームにおける３次元画像を生成する３次元画像描画手段を備えている。
【００１４】
本発明は、上記３次元画像生成装置を組み込んだナビゲーション装置も権利対象としている。そのようなナビゲーション装置は、通常のナビゲーション装置に必須の構成要素とともに、上述した本発明による３次元画像生成装置の種々の特徴構成を備えている。その際、前記視点は、自車位置情報検出手段によって検出された自車位置に基づいて決定され、前記視点からの視軸は案内経路に沿うように決定されるように構成すると、好適である。これにより、案内経路を上述した特徴を有する３次元画像生成装置で描画された３次元地図画像として表示案内することができる。
【００１５】
さらに、本発明は、立体物に関する立体図データを用いて３次元空間を２次元表示するためのプログラムをコンピュータに実現させる３次元データ処理プログラムも権利対象としている。そのような３次元データ処理プログラムは、各立体物の立体図データを用いて当該立体物のバウンディングボリュームを生成するバウンディングボリューム生成機能と、設定された視点に基づいてビューボリュームを設定するビューボリューム設定機能と、生成された前記バウンディングボリュームを用いて前記ビューボリューム内における描画対象となる立体物を判定するカリング処理機能とをコンピュータに実現させ、前記バウンディングボリューム生成機能は、データベースから読み出された各立体物の立体図データから処理対象となる立体物の底面に平行な横断面を読み取る又は算定する機能と、得られた前記横断面を内包する外枠四角形を算定する機能と、前記外枠四角形に内接する内枠四角形を算定する機能と、前記内枠四角形を基準面として当該立体物のバウンディングボリュームを生成する機能とを有する。当然ながら、このような３次元データ処理プログラムも上述した３次元データ処理装置で述べた作用効果を得ることができ、さらにその好適な形態例として述べたいくつかの付加的技術を組み込むことも可能である。
【発明を実施するための最良の形態】
【００１６】
本発明の実施形態について図面に基づいて説明する。図１は、本実施形態における自動車用ナビゲーション装置の主要要素の構成を模式的に示すブロック図である。このナビゲーション装置は立体地図表示可能であり、そのために、本発明の対象でもある３次元画像生成装置２０と３次元データ処理装置１０とが階層的に組み込まれている。地図データベース３０には、立体物の立体図データを格納する立体図データベースとして３次元市街地データベース３１と、２次元道路データを格納する２次元道路データベース３２とが含まれている。地図データベース３０は、ＤＶＤやハードディスクなどの大容量記憶媒体で構成される。また、書き換え可能な記憶媒体を採用している場合には、適時、最新の地図データをデータ通信を通じてダウンロードすることができる。
【００１７】
３次元データ処理装置１０は、視点設定手段１１と、ビューボリューム設定手段１２と、バウンディングボリューム設定手段１３と、カリング処理手段１４と、データ処理管理装置１５とを含んでいる。３次元コンピュータグラフィックスでは、図２で模式的に示されているように、３次元空間中の任意の位置を投影中心とし、また、任意の点を含む平面を投影面とする場合の透視投影を考えた場合、その投影中心は、観察者の目の位置、つまり視点１に相当する。この視点１を設定するのが視点設定手段１１である。また、設定された視点１における３次元空間内の立体物のレンダリングを行う場合、その視点１の視軸に直交する面である前方クリップ面２と後方クリップ面３が定義される。前方クリップ面２と後方クリップ面３のそれぞれの対応する各頂点を結ぶことによって形成される、図２では四角錐台がビューボリューム４である。このビューボリューム４を設定するのがビューボリューム設定手段１２である。
【００１８】
バウンディングボリューム生成手段１３は、３次元市街図データベース３１から読み出された各立体物の立体図データを用いて当該立体物のバウンディングボリュームを生成する機能を有する。本発明によるバウンディングボリューム生成手段１３は、処理対象となる立体物の平面外形輪郭（立体物の底面に平行な横断面）を内包する外枠四角形に内接する内枠四角形を基準面として当該立体物のバウンディングボリュームを生成するが、後で詳しく説明する。カリング処理手段１４は、ビューボリューム４内に位置する各立体物をそのバウンディングボリュームを用いてビューボリューム内における描画対象（レンダリング対象）となるかどうか判定する。この実施形態では、カリング処理手段１４は、カリング手法としてオクルージョンカリング手法を用いているので、あるバウンディングボリュームが他のバウンディングボリュームによって完全に遮蔽されている（見えない位置にある）と見なされると、描画非対象と見なされる。これには、一般的に、視点１からの光線を順次設定し、各光線が他のバウンディングボリュームによって遮断されることなしに処理対象のバウンディングボリュームに達するかどうかを判定する手法が用いられる。データ処理管理装置１５は、上述した、視点設定手段１１、ビューボリューム設定手段１２、バウンディングボリューム設定手段１３、カリング処理手段１４の制御動作を管理するとともに、カリング処理手段１４によって判定された判定結果をリスト化して記録している。カリング判定結果は、ビューボリューム４内に位置する各立体物のうちで、描画対象となった立体物を識別するコード又はその立体物のデータそのものである。一時的に記憶されているカリング判定結果は、３次元画像描画（レンダリング）時に利用される。
【００１９】
３次元画像生成装置２０は上記３次元データ処理装置１０を含むとともに、描画対象となった立体物の立体図データを用いてビューボリューム４における３次元画像をよく知られたレンダリング手法等によって生成する３次元画像描画手段２１を含んでいる。
【００２０】
自動車用ナビゲーション装置は、上記３次元画像生成装置２０を組み込んでいるので、自車位置情報検出手段４１によって検出された自車位置に基づいて視点１を設定するとともに、当該視点１からの視軸は案内経路に沿うように決定することで、車両の走行予定となる案内経路を中心とした立体地図を表示する機能を有する。もちろん、通常の２次元道路地図を表示する機能も有するので、二次元画像描画手段４２も備えられている。
【００２１】
現在位置と操作入力部４３を通じてユーザが指定した地点（例えば目的地）を結ぶ最適な案内経路が経路探索手段４４によって探索され、探索された案内経路は案内経路記憶部４５に設定される。設定された案内経路と自車位置に基づいて経路案内手段４６がスピーカ４７やモニタ４８を通じてユーザに経路案内を行う。その際、２次元画像描画手段４２又は３次元画像描画手段２１あるいはその両方によって生成された画像は、表示処理手段４９に送られ、必要に応じて種々の情報やシンボルを重ね合わせる処理を施された後、モニタ４８に表示される。
【００２２】
操作入力部４３は、ユーザからの指示を受け付ける機能を有し、タッチパネル、機械的な操作ボタン、ソフトウエアボタンなどから構成される。タッチパネルやソフトウエアボタンは、表示処理手段４９との協働によりユーザグラフィックインターフェースを構築している。また、操作入力部４３は３次元データ処理装置１０に対して直接、視軸を含む視点１を指示することができ、これによりユーザの希望する視点と視軸に基づいた３次元画像をモニタ４８に表示させることができる。
【００２３】
自車位置情報検出手段４１は、自車位置すなわち自車の現在位置を示す自車位置情報を取得する。この実施形態では、自車位置情報検出手段１は、ＧＰＳ受信機５１、方位センサ５２、及び距離センサ５３と接続されている。ここで、ＧＰＳ受信機５１は、ＧＰＳ衛星からのＧＰＳ信号を受信する装置である。このＧＰＳ信号は、通常１秒おきに受信され、自車位置情報取得手段４１へ出力される。自車位置情報検出手段４１では、ＧＰＳ受信機５１で受信されたＧＰＳ衛星からの信号を解析し、自車の現在位置（緯度及び経度）、進行方位、移動速度等の情報を取得することができる。方位センサ５２は、自車の進行方位又はその進行方位の変化を検出するセンサである。この方位センサ５２は、例えば、ジャイロセンサ、地磁気センサ、ハンドルの回転部に取り付けた光学的な回転センサや回転型の抵抗ボリューム、車輪部に取り付ける角度センサ等により構成され、その検出結果を自車位置情報検出手段４１へ出力する。距離センサ５３は、自車の車速や移動距離を検出するセンサである。この距離センサ５３は、例えば、自車のドライブシャフトやホイール等が一定量回転する毎にパルス信号を出力する車速パルスセンサ、自車の加速度を検知するヨー・Ｇセンサ及び検知された加速度を積分する回路等により構成される。そして、距離センサ５３は、その検出結果としての車速及び移動距離の情報を自車位置情報検出手段４１へ出力する。
【００２４】
自車位置情報検出手段４１は、これらのＧＰＳ受信機５１、方位センサ５２及び距離センサ５３からの出力に基づいて、公知の方法により自車位置を特定する演算を行う。また、自車位置情報取得手段４１は、２次元道路データベース３２から自車位置周辺の２次元道路データを取得し、それに基づいて公知のマップマッチングを行うことにより自車位置を２次元道路データに示される道路上に合わせる補正も行う。このようにして、自車位置情報検出手段４１は、緯度及び経度で表された自車の現在位置の情報、及び自車の進行方位の情報を含む自車位置情報を取得する。
【００２５】
図３にバウンディングボリューム生成手段１３の機能要素を示すブロック図が示されている。このバウンディングボリューム生成手段１３は、立体図データ取得部９１と、立体図平面データ算定部９２と、基準軸平行外枠四角形算定部９３と、内枠四角形算定部９４と、バウンディングボリューム形状データ決定部９５と、バウンディングボリューム形状データ出力部９６とを含む。
【００２６】
立体図データ取得部９１は、３次元市街図データベース３１から読み込まれた処理対象となる立体物の立体図データをワーキングメモリに格納し、立体物ＩＤと通じて各立体図データを識別管理する。立体図平面データ算定部９２は、処理対象となる立体物の立体図データであるポリゴンデータ群からこの立体物の横断面である平面外形輪郭を規定する平面データを算定する。この平面データが底面データであり、３次元市街図データベース３１から読み込まれた立体図データにこの底面データが含まれている場合は、当該立体図データから底面データを抽出するだけでよい。底面データが含まれていない場合は、ポリゴンデータ群から底面データが算定される。また、平面データとして、立体物の最大平面外形輪郭が採用される場合などは、ポリゴンデータ群からそのような平面データが算定される。
【００２７】
基準軸平行外枠四角形算定部９３は、立体図平面データ算定部９２によって算定された平面データによって規定される平面外形輪郭を内包する外枠四角形を算定する機能を有する。この実施形態では、外枠四角形として平面外形輪郭に接する外接四角形を採用しているが、少なくとも１つの辺が平面外形輪郭と所定量の隙間をあけた外枠四角形も利用可能である。さらに、この実施形態では、算定される外枠四角形は、設定された基準横軸（例えば緯線）と基準縦軸（経線）に平行な辺を有するように規定されているので、基準横軸と基準縦軸による座標系に平面データを座標変換してから外枠四角形を算定すると好都合である。
【００２８】
内枠四角形算定部９４は、基準軸平行外枠四角形算定部９３で算定された外枠四角形に内接する内枠四角形（内接四角形）を算定する機能を有する。この実施形態では、算定される内枠四角形は前記外枠四角形の各辺の中点を結んで得られる内接四角形と規定しているが、他の形態の内接四角形を内枠四角形として採用してもよい。
【００２９】
バウンディングボリューム形状データ決定部９５は、内枠四角形を基準面として処理対象となっている立体物のバウンディングボリュームを生成するために必要な形状データ（基準軸座標系の座標位置情報を含む）を決定する機能を有する。この実施形態では、内枠四角形算定部９４で算定された内枠四角形を底面としてそこから処理対象となっている立体物の高さ分だけ立ち上げた四角柱形状体をバウンディングボリュームとしている。バウンディングボリューム形状データ決定部９５で作成されたバウンディングボリューム形状データは、バウンディングボリューム形状データ出力部９６によってカリング処理手段１４に転送される。
【００３０】
このように構成されたバウンディングボリューム生成手段１３による、立体図データからバウンディングボリュームを生成する手順を説明する。図４には、そのバウンディングボリューム生成手順が模式的に示されている。
まず、ワーキングメモリに格納されている立体物の立体図データ（ポリゴンデータ）のうち、指定された立体物の立体図データに注目する（＃０１）。この注目された立体図データから、指定された立体物の平面外形輪郭を表す平面データとして底面データ（底面ポリゴン）を読み取るか、もしくは算定する（＃０２）。得られた底面データは、互いに直交する基準縦軸（例えば経線）と基準横軸（例えば緯線）とからなる座標系に座標変換され、その座標系においてこの底面データによって規定されるポリゴンを外接するとともに各２辺が基準縦軸又は基準横軸に平行な外枠四角形が算定される（＃０３）。次に、算定された外枠四角形の各辺の中点を結んで作成される内接四角形（菱形）が内枠四角形として算定される（＃０４）。さらに、この内枠四角形を底面としてそこからステップ＃０１で指定された立体物の高さ分だけ立ち上げることで作成される四角柱形状体がこの立体物のバウンディングボリュームとして算定される（＃０５）。
【００３１】
このようにして、所定領域に位置する全ての立体物のバウンディングボリュームが生成されると、カリング処理手段１４により、オクルージョンカリング処理が行われ、ビューボリューム４内に位置するとともに、他のバウンディングボリュームによって遮蔽されない描画用バウンディングボリュームが決定される。３次元画像描画（レンダリング）では、描画用バウンディングボリュームに含まれている立体物（実際には立体物の立体図データによって規定されるポリゴン）がビューボリューム４内に配置される（図５（ａ）参照）。３次元画像描画手段２１によって描画され、モニタ４８に表示される３次元画像（立体地図画像）が図５（ｂ）に例示されている。
【００３２】
〔別実施形態〕
（１）
上述した実施形態のバウンディングボリューム生成手段１３では、内枠四角形を底面としてそこから処理対象の立体物の高さ分だけ立ち上げることで作成される四角柱形状体がこの処理対象の立体物のバウンディングボリュームとして生成していた。つまり、このバウンディングボリュームは同じ横断面を有していることになる。しかしながら、実際の建物などでは、低層階と高層階ではその横断面が異なる場合が少なくない。このことを考慮して、所定の高さレベル毎に複数の内枠四角形を算定してサブバウンディングボリュームを生成し、これらのサブバウンディングボリュームを積み重ねて最終的なバウンディングボリュームを生成するようにバウンディングボリューム生成手段１３を構成してよい。
【００３３】
そのように構成されたバウンディングボリューム生成手段１３による、立体図データからバウンディングボリュームを生成する手順を、図６によるバウンディングボリューム生成手順模式図を用いて、以下に説明する。
図４を用いて説明した先の実施形態のものと同様に、まず、ワーキングメモリに格納されている立体物の立体図データ（ポリゴンデータ）のうち、指定された立体物の立体図データに注目する（＃０１）。この注目された立体図データから、所定の複数の高さレベル、ここでは２つの高さレベル、地面レベル（底面レベル）、及び、その立体物の横断面形状が大きく変化している箇所の高さレベル（中層レベルと呼ぶことにする）における立体物の平面外形輪郭を表す平面データがそれぞれ算定される（＃１２又は＃２２）。地面レベルで得られた平面データ（底面データ）は、互いに直交する基準縦軸（例えば経線）と基準横軸（例えば緯線）とからなる座標系に座標変換され、その座標系においてこの底面データによって規定されるポリゴンを外接するとともに各２辺が基準縦軸又は基準横軸に平行な第１外枠四角形が算定される（＃１３）。同様に、中層レベルで得られた平面データも同様の座標系に座標変換され、その座標系においてこの平面データによって規定されるポリゴンを外接する第２外枠四角形が算定される（＃２３）。次に、ステップ＃１３で算定された第１外枠四角形の各辺の中点を結んで作成される内接四角形（菱形）が第１内枠四角形として算定される（＃１４）。同様に、ステップ＃２３で算定された第２外枠四角形の各辺の中点を結んで作成される内接四角形（菱形）が第２内枠四角形として算定される（＃２４）。さらに、第１内枠四角形を底面としてそこから中層レベルまでの高さ分だけ立ち上げることで第１サブバウンディングボリュームを生成する。同様に、第２内枠四角形を底面として中層レベルからこの立体物の頂点までの高さ分だけ立ち上げることで第２サブバウンディングボリュームを生成する。そして、第１サブバウンディングボリュームの上に第２サブバウンディングボリュームを積み重ねることで、最終的なバウンディングボリュームが生成される（＃３０）。
【００３４】
（２）
上述した実施形態におけるバウンディングボリューム生成手段１３の説明では、１つの立体物に対して１つのバウンディングボリュームが生成されていたが、当然、複数の立体物に対して１つのバウンディングボリュームが生成するようにしてもよい。特に立体物が込み入って配置されている場合には、複数の立体物に対して１つのバウンディングボリュームを割り当てることは、カリング精度を実質的に低下させずに処理速度を向上させることができるので、好都合である。
【００３５】
（３）
上述した実施形態における内枠四角形算定部９４は、基準軸平行外枠四角形算定部９３で算定された外枠四角形の各辺の中点を結んで得られる内接四角形を内枠四角形として算定していたが、その他の幾何学的手法で得られる他の内枠四角形を採用してもよい。例えば、外枠四角形の各辺の３等分点など、ｎ等分点を結んで得られる内接四角形を内枠四角形として算定することができる。
【００３６】
（４）
内枠四角形算定部９４は、基準軸平行外枠四角形算定部９３で算定された外枠四角形に内接する内枠四角形を算定していたが、ここでの「内接する」という語句は、数学的な厳密さを求めているわけではなく、実際に外枠四角形に内接する内接四角形より幾分小さな、好ましくは当該内接四角形に相似形の四角形も内枠四角形に含まれると解釈されるべきである。
【図面の簡単な説明】
【００３７】
【図１】本発明における自動車用ナビゲーション装置の主要要素の構成を示すブロック図
【図２】視点及びビューボリュームを説明する説明図
【図３】本発明におけるバウンディングボリューム生成手段の機能を示すブロック図
【図４】バウンディングボリューム生成手順の１つの実施形態を示す模式図フローチャート
【図５】（ａ）描画時におけるビューボリュームの一例を説明する説明図と、（ｂ）このビューボリュームを用いて描画された３次元画像のモニタ表示画面図。
【図６】バウンディングボリューム生成手順の他の実施形態を示す模式図フローチャート
【符号の説明】
【００３８】
１０：３次元データ処理装置
１１： 視点設定手段
１２：ビューボリューム設定手段
１３：バウンディングボリューム生成手段
１４：カリング処理手段
１５：データ処理管理手段
２０：３次元画像生成装置
３０：地図データベース
３１：３次元市街図データベース（立体図データベース）
４１：自車位置情報検出手段
９２：立体物平面データ算定部
９３：基準軸平行外枠四角形算定部
９４：内枠四角形算定部
９５：バウンディングボリューム形状データ決定部
【図１】
0004947376.tif 000002
【図２】
0004947376.tif 000003
【図３】
0004947376.tif 000004
【図４】
0004947376.tif 000005
【図５】
0004947376.tif 000006
【図６】
0004947376.tif 000007