描画処理装置、描画処理プログラムおよび描画処理方法
【課題】地図データの構成を変えることなく高速な描画処理を実現すること。
【解決手段】描画処理装置は、画像を分割するパーセル構造１１０単位にそれぞれパーセル内に存在する描画対象図形の情報を含んだ地図データを用いて図形描画をおこなう描画処理装置であって、パーセル構造１１０をより小さな仮想サブパーセル構造１２０に分割し、分割された仮想サブパーセルからパーセル内の図形の少なくとも一部が存在する仮想サブパーセルを特定し、特定された仮想サブパーセルと、図形とを関連付ける。そして、描画処理装置は、描画環境設定から画像の表示領域の指示を受け付けると、図形データの中から、表示領域に含まれるパーセルを抽出し、さらに抽出されたパーセル表示領域に含まれる仮想サブパーセルを抽出し、抽出されたパーセルの少なくとも一部に存在する図形の中から、抽出された仮想サブパーセルと関連付けされた図形を描画する。
【解決手段】描画処理装置は、画像を分割するパーセル構造１１０単位にそれぞれパーセル内に存在する描画対象図形の情報を含んだ地図データを用いて図形描画をおこなう描画処理装置であって、パーセル構造１１０をより小さな仮想サブパーセル構造１２０に分割し、分割された仮想サブパーセルからパーセル内の図形の少なくとも一部が存在する仮想サブパーセルを特定し、特定された仮想サブパーセルと、図形とを関連付ける。そして、描画処理装置は、描画環境設定から画像の表示領域の指示を受け付けると、図形データの中から、表示領域に含まれるパーセルを抽出し、さらに抽出されたパーセル表示領域に含まれる仮想サブパーセルを抽出し、抽出されたパーセルの少なくとも一部に存在する図形の中から、抽出された仮想サブパーセルと関連付けされた図形を描画する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、２次元および３次元の地図画像の描画処理をおこなう描画処理装置、描画処理プログラムおよび描画処理方法に関する。
【背景技術】
【０００２】
従来、ナビゲーションシステムや地図表示システムでは、個別の図形データを専用のグラフィックスシステムにおいてリアルタイムに描画して地図画像を随時生成する手法が多く採用されている。これは、ナビゲーションシステムや地図表示システムでは、移動やユーザからの指示に応じて表示用の地図画像を動的に変化させる必要があるため、ビットマップのような完成された地図画像イメージを拡大縮小回転表示するよりも専用のグラフィックスシステムによって逐一生成した方が鮮明でスケーラブルな地図画像を提供できるためである。
【０００３】
また、上述のようなシステムにおいて利用される地図データは、一般的にパーセルと呼ばれる区画単位のデータの集合体として構成されている。具体的には、パーセルごとにパーセルがあらわす地図上の道路や建造物などの２次元形状データがグループ化されたデータによって構成されている。この２次元形状データは、図形の頂点座標や塗り潰し色などのリアルタイムで地図描画をおこなうために必要な描画用データを含んだ構成となっている。
【０００４】
さらに、パーセルを構成する描画用の図形データは、道路や土地利用区分や建造物の重なりを正しく処理して描画できるように最適化された順序に並べられている。したがって、たとえば、パーセルの大きさを変更するような場合にパーセル内に含まれる図形の転入／転出が生じると、図形データの並べ替えが必要になる。また、パーセルサイズの変更によって図形が隣接するパーセルの境界をまたぐような場合にも、図形をパーセル境界で切断し、切断後の図形データを各パーセルに再分配する必要がある。
【０００５】
また、パーセル単位の地図データを利用して地図描画をおこなう際は、指定された表示範囲の地図画像を表示させる。このとき、１つのパーセルの大きさはディスプレイなどの表示画面に表示される領域のサイズより大きいことも多い。すなわち、パーセルには表示画面に表示されない地図データが多数含まれることになる。また、市街地と郊外とでは地図データの密度が異なるので、パーセルサイズが均一の場合には、地図データの密度に偏りが生じる。そこで、地図データの偏りを改善してデータアクセス効率を高めるために、パーセルサイズをデータ密度に応じて可変に構築する技術も開示されている（たとえば、下記特許文献１参照。）。
【０００６】
【特許文献１】特開２００４−１７７９５９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述したようにパーセル単位によって構成された地図データから地図画像を生成する場合、地図上に配置されている図形の描画処理は、パーセル単位で実行されてしまう。たとえ表示画面に表示される画像がパーセルに含まれる図形データの一部分しか利用しない場合であっても、同一パーセルに含まれているすべての図形データが読み出され、描画処理がおこなわれてしまう。さらに、表示画面に表示される画像が複数のパーセルにまたがった図形データである場合には、表示画面に表示される割合を問わずに２パーセル〜４パーセル分の地図データすべてが読み出され、描画処理がおこなわれてしまっていた。
【０００８】
このように、従来の描画処理は、実際には表示画面への出力に反映されない処理を多分に含んでいたため、描画処理を高速化できないという問題があった。たとえ、上記特許文献１の技術を適用させ、データ密度に応じてパーセルサイズを変え、データ量の均一化を計ったとしても、地図データ読込み量の平準化は達成されるが、表示画面以外の図形部分の描画処理を抑制することはできず、描画処理速度をあげることはできなかった。
【０００９】
この発明は、上述した従来技術による問題点を解消するため、地図データの構成を変えることなく高速な描画処理を実現することのできる描画処理装置、描画処理プログラムおよび描画処理方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するため、この描画処理装置、描画処理プログラムおよび描画処理方法は、画像を分割する第１領域内に存在する図形の情報を含んだ図形データを用いて前記画像を描画する描画処理であって、前記図形データに対応する前記第１領域を前記第１領域より小さな第２領域に分割し、分割された前記第２領域から前記第１領域の図形の少なくとも一部が存在する第２領域を特定し、特定された第２領域と、前記図形とを関連付ける処理を備えることを要件とする。
【００１１】
この描画処理装置、地図描画プログラムおよび描画処理方法によれば、第１領域としてたとえば区画単位で蓄積された地図データの画像に対して第１領域ごとに仮想的な分割をおこない、第１領域より小さな第２領域群を設定する。第２領域としてはたとえば区間を分割した矩形群が挙げられる。そして、第１領域内の描画対象となる図形の少なくとも一部が存在する第２領域を特定して図形と関連付ける。したがって、地図データの構成を変更せずに、第１領域に対して描画指示を受け付けた際に、描画処理をおこなうか否かの判断基準となる情報を埋め込むことができる。
【００１２】
また、上記の描画処理装置、描画処理プログラムおよび描画処理方法において、さらに、前記第１領域単位に、前記図形の参照テーブルが含まれている場合、前記関連付け手段は、前記第２領域と、前記参照テーブルとを関連付けてもよい。
【００１３】
この描画処理装置、地図描画プログラムおよび描画処理方法によれば、描画対象図形の参照テーブルと第２領域とを関連付けるため、地図データに含まれる描画対象の図形に関する情報と第２領域とを直接関連付ける必要がなく、描画処理をおこなうか否かの判断基準となる情報を埋め込むことができる。
【００１４】
また、上記の描画処理装置、描画処理プログラムおよび描画処理方法において、さらに、前記画像の表示領域の指示を受け付けると、前記図形データの中から、前記表示領域に含まれる前記第１領域を抽出する第１の抽出と、第１の抽出によって抽出された前記第１領域および前記表示領域に含まれる前記第２領域を抽出する第２の抽出と、第１の抽出によって抽出された前記第１領域の少なくとも一部に存在する前記図形の中から、第２の抽出された前記第２領域と関連付けされた図形を描画する処理を備えてもよい。
【００１５】
この描画処理装置、描画処理プログラムおよび描画処理方法によれば、指定された表示領域の地図画像を描画するために必要となる第１領域内に存在する描画対象の図形のうち、表示領域に表示される描画対象図形のみ描画され、表示されないその他の描画対象図形の描画処理の発生を防ぐことができる。
【発明の効果】
【００１６】
この描画処理装置、描画処理プログラムおよび描画処理方法によれば、地図データの構成を変えることなく高速な描画処理を実現することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１７】
以下に添付図面を参照して、この描画処理装置、描画処理プログラムおよび描画処理方法の好適な実施の形態を詳細に説明する。
【００１８】
（本実施の形態にかかる地図描画処理の概要）
まず、本実施の形態にかかる地図描画処理の概要について説明する。図１は、本実施の形態にかかる地図描画処理の概要を示す説明図である。図１に示すように、本実施の形態では、地図データ１００は、パーセル構造１１０のデータの集合体として構成されている。個々のパーセル構造１１０は、さらに仮想的に分割され、仮想サブパーセル構造１２０になっている。
【００１９】
仮想サブパーセル構造１２０は、名前が指すように仮想的にパーセル構造をさらに小さなパーセル構造に分割するための概念である。したがって、地図データ１００に蓄積されている各パーセル構造１１０をあらわすデータ構造は、パーセル構造１１０内の図形データの並べ替えや、サブパーセル境界での図形の切断といったデータの再構成処理を必要とせず、データ列１３０に示すように、従来のパーセル構造１１０をあらわす情報によって構成されている。
【００２０】
本実施の形態にかかる描画処理の場合は、上述したような従来と同じデータ構成に、仮想サブパーセル構造１２０によって仮想的に分割された仮想サブパーセルに関する情報を埋め込み、描画処理判断に利用する。具体的には、１つのパーセル構造１１０には、データ列１３０のようにパーセル内に存在する描画対象図形（たとえば図形Ａ）のデータが含まれている。この描画対象図形が、仮想サブパーセル構造１２０のように分割した場合にどの仮想サブパーセルに位置するかをあらわすサブパーセル識別コード１３１が、データ列１３０の図形Ａに関する情報に追加して埋め込まれる。
【００２１】
上述の処理を実際の描画処理に沿って説明する。まず、描画処理のための準備処理として、まず地図データ１００に含まれるパーセル構造１１０ごとの図形データは、実際の地図画像の表示システム（たとえば、ナビゲーションシステム）用地図データベースを生成するために、描画対象図形のデータがどの仮想サブパーセル位置に収まるかを判定し、その結果に対応するサブパーセル識別コード１３１を与える。このとき、一つの仮想サブパーセルに収まりきらない場合は、複数の仮想サブパーセルによって表示されることをあらわすサブパーセル識別コード１３１を付与する。サブパーセル識別コード１３１は、図１のように図形データそのものに付与してもよいし、図形データの存在するアドレスを指す参照テーブルに付与してもよい。
【００２２】
つぎに、実際の地図描画に関する処理について説明する。実際の地図描画は、ユーザや、上位システムから表示領域１１１の指定の受け付けをトリガとして開始される。地図データ１００の各パーセルの図形データには、サブパーセル識別コード１３１が埋め込まれており、これら地図データ１００の中から指定された表示領域１１１が含まれるパーセル構造１１０部分の地図データ１００が読み出される。
【００２３】
従来は、読み出されたパーセル構造１１０の地図データ１００に含まれる描画対象図形をすべて描画していたが、本実施の形態の場合、表示領域１１１が含まれるパーセル構造１１０のうち、表示領域１１１に含まれるサブパーセルをあらわすサブパーセル識別コード１３１が埋め込まれた図形データを抽出して描画を実行する。したがって、表示領域１１１外に存在する図形に関しては、描画処理が省略される。
【００２４】
従来の描画処理の場合、パーセルサイズが表示領域、すなわち表示画面サイズより相対的に大きい状況では、表示画面に表示されない地図データがパーセルに多数含まれるため無駄な描画処理が発生し、描画速度の低下が著しかった。しかしながら、本実施の形態のような描画処理の場合、実際に表示される図形に対してのみ描画処理がおこなわれるため、描画速度が向上する。
【００２５】
また、従来の描画処理の場合、たとえば、クリッピング処理によって画面外データの描画を抑制するとしても、地図データに含まれる図形数が膨大なので、クリッピング対象になるか否かの判定処理自体負担となり、描画処理全体からみるとボトルネックになっていた。しかしながら、本実施の形態のような描画処理であれば上述のような問題も発生しない。
【００２６】
また、従来の描画処理では、表示画面外への描画を抑制するためにゲームグラフィックスで多用されるような、バウンディングボックスや境界球による事前可視性判定をおこなうといった対策も講じられていたが、地図描画という描画対象となる図形が特定の形状に限定される場合には、必ずしも効果的ではなかった。その理由としては、ゲームにおける人物やモンスターのようなキャラクターは、１体あたりの頂点数が多いため、バウンディングボックスによる頂点数削減効果が大きいが、地図データに含まれる図形は、キャラクターなどの図形類ほどは頂点数を持っていない。すなわち、一つ一つの頂点数削減効果が小さく、膨大な数のバウンディングボックスを処理しなければならず、描画速度の向上にはつながらなかった。本実施の形態の描画処理の場合、図形の種類を限定されることなく、効果を発揮することができる。
【００２７】
また、パーセルサイズを画面サイズに合わせて最適化することも可能であるが、処理負担から鑑みて現実的な描画処理とはいえない。その第１の理由は、地図縮尺に応じて拡大縮小描画する場合、パーセルサイズと画面サイズの相対比率が常に変化するためである。これは、最適なパーセルサイズは縮尺に応じて無数に存在し、たとえ、相対サイズ比のバリエーションを限定したとしても、同一詳細度の地図データを、複数のパーセルサイズとして実装してそれぞれ用意しなければならず、これらの条件を満たさなければ効果が得られないことを意味する。このような処理を実現させた場合、たとえば、ＨＤＤなどの地図データ格納容量の逼迫を引き起こす可能性もある。
【００２８】
また、第２の理由は、パーセルサイズの変更には、必ず図形データ格納順の並べ替え、パーセル境界での図形の切断と再分配のほか、場合によってはデータ量の増大といった事態が発生するためである。このような地図データベースのチューニングは、原理的・汎用的な措置ではなく、製品ごとの個別最適化に過ぎないため、地図データメーカーやカーナビゲーションシステムメーカーにとっては、大きな負担となり、採用したがらない傾向にある。
【００２９】
したがって、本実施の形態にかかる描画処理のように、地図データの構成変更を必要としないにもかかわらず、従来無駄とされていた部分の描画処理を省くことができるという特徴は、各種システムにとって適用しやすい処理であるという効果も含んでいる。したがって、以下に図１によって説明した描画処理の特徴を備えた描画処理装置を実現するための具体的な構成や処理内容について詳しく説明する。
【００３０】
（地図描画装置のハードウェア構成）
まず、本実施の形態にかかる描画処理を実現する描画処理装置のハードウェア構成について説明する。図２は、本実施の形態にかかる描画処理装置のハードウェア構成を示す説明図である。
【００３１】
図２において、描画処理装置２００は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）２０１と、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）２０２と、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）２０３と、ハードディスクドライブ２０４と、ハードディスク２０５と、光ディスクドライブ２０６と、光ディスク２０７と、ディスプレイ２０８と、Ｉ／Ｆ（インターフェース）２０９と、キーボード２１０と、マウス２１１と、スキャナ２１２と、プリンタ２１３と、を備えている。また、各構成部はバス２００によってそれぞれ接続されている。
【００３２】
ここで、ＣＰＵ２０１は、描画処理装置２００の全体の制御を司る。ＲＯＭ２０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ２０３は、ＣＰＵ２０１のワークエリアとして使用される。ハードディスクドライブ２０４は、ＣＰＵ２０１の制御にしたがってハードディスク２０５に対するデータのリード／ライトを制御する。ハードディスク２０５は、ハードディスクドライブ２０４の制御で書き込まれたデータを記憶する。
【００３３】
光ディスクドライブ２０６は、ＣＰＵ２０１の制御にしたがって光ディスク２０７に対するデータのリード／ライトを制御する。光ディスク２０７は、光ディスクドライブ２０６の制御で書き込まれたデータを記憶したり、光ディスク２０７に記憶されたデータを描画処理装置２００に読み取らせたりする。
【００３４】
また、光ディスク２０７として、ＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｋ）、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）、ＭＯ（Ｍａｇｎｅｔｏ Ｏｐｔｉｃａｌ）、メモリーカードなどを採用することができる。ディスプレイ２０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ２０８は、たとえば、ＣＲＴ（Ｃａｔｈｏｄｅ Ｒａｙ Ｔｕｂｅ）、ＴＦＴ（Ｔｈｉｎ Ｆｉｌｍ Ｔｒａｎｓｉｓｔｏｒ）液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００３５】
Ｉ／Ｆ２０９は、通信回線を通じてインターネットなどのネットワーク２１４に接続され、このネットワーク２１４を介して他の装置に接続される。そして、Ｉ／Ｆ２０９は、ネットワーク２１４と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ２０９には、たとえば、モデムやＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）アダプタなどを採用することができる。
【００３６】
キーボード２１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス２１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００３７】
スキャナ２１２は、画像を光学的に読み取り、描画処理装置２００内に画像データを取り込む。なお、スキャナ２１２は、ＯＣＲ（Ｏｐｔｉｃａｌ Ｃｈａｒａｃｔｅｒ Ｒｅａｄｅｒ）機能を持たせてもよい。また、プリンタ２１３は、画像データや文書データを印刷する。プリンタ２１３には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。
【００３８】
なお、本実施の形態にかかる描画処理装置２００の場合は、図２に例示したような単独の装置として実現する場合の他に、カーナビゲーション装置とともにカーナビゲーションシステムを実現する場合や、携帯端末装置とともに携帯端末ナビゲーションシステムを実現する場合などがある。したがって、図２の描画処理装置２００のハードウェア構成はあくまで一例であり、他の構成によって実現してもよい。なお、カーナビゲーションシステムや携帯端末ナビゲーションシステムとして実現する例については後述する。
【００３９】
（描画処理装置の機能的構成）
つぎに、描画処理装置の機能的構成について説明する。図３は、描画処理装置の機能的構成を示すブロック図である。図３において、描画処理装置２００は、分割部３０１と、特定部３０２と、関連付け部３０３と、区画抽出部３０４と、矩形抽出部３０５と、描画部３０６と、を備えている。これら各機能３０１〜３０６は、描画処理装置２００の記憶部（たとえば、図２にて説明したハードディスク２０５など）に記憶された当該機能３０１〜３０６に関するプログラムをＣＰＵに実行させることにより、または、入出力Ｉ／Ｆにより、当該機能を実現することができる。
【００４０】
描画処理装置２００は、地図を分割する区画（第１領域）単位としてパーセル単位にそれぞれ当該パーセル内に存在する描画対象図形の情報を含んだ地図データ１００を用いて地図画像を描画する。したがって、パーセル単位のデータ構造をもつ地図データ１００を用意して描画処理装置２００に読み込ませる。
【００４１】
分割部３０１は、読み込んだ地図データの中の任意のパーセルをより小さな矩形（第２領域）群、すなわち、仮想サブパーセル群に分割する。なお、本実施の形態では仮想サブパーセルとなる第２領域は矩形になるように分割しているが、区画がもれなく分割されていれば第２領域の形状は特に限定されない。分割部３０１による分割とは上述したように仮想的な分割であり、地図データ１００を分割するのではなく、分割した場合の個々の矩形である仮想サブパーセルの配置をあらわす設定情報を生成する処理をおこなう。
【００４２】
特定部３０２は、分割部３０１によって分割された仮想サブパーセル群の中からパーセル内の描画対象図形の少なくとも一部が存在する仮想サブパーセルを特定する。
【００４３】
関連付け部３０３は、特定部３０２によって特定された仮想サブパーセルと、描画対象図形とを関連付ける。仮想サブパーセルと、描画対象図形とを関連付けるとは、具体的には、描画対象図形に関する情報に特定された仮想サブパーセルの設定情報と関連付けて記録する。一例として、図１のデータ列１３０のように、描画対象図形に関する情報にサブパーセル識別コード１３１を埋め込むような手法がある。
【００４４】
なお、関連付け部３０３は、描画対象図形に関する情報の格納先をあらわす参照テーブルが含まれている場合であれば、描画対象図形ではなく、仮想サブパーセルと、参照テーブルとを関連付けてもよい。
【００４５】
さらに、上述したように、特定部３０２によって、描画対象図形が一つの仮想サブパーセルに収まらずに、描画対象図形の少なくとも一部が存在する複数の仮想サブパーセルを特定した場合、関連付け部３０３は、特定された複数の仮想サブパーセルと、描画対象図形の情報や参照テーブルとを関連付けてもよい。
【００４６】
以上説明した分割部３０１〜関連付け部３０３によって、本実施の形態にかかる描画処理をおこなうための準備が終了したことになる。つぎに、実際に地図画像を描画するための処理について説明する。この処理は、上述したように、外部からの表示領域指示に関する情報の受け付けがトリガとなる。
【００４７】
区画抽出部３０４は、描画環境設定から地図の表示領域１１１の指示を受け付けると、地図データ１００の中から、表示領域１１１に含まれるパーセルを抽出する。ここで抽出されたパーセルの情報は、矩形抽出部３０５に出力される。
【００４８】
矩形抽出部３０５は、区画抽出部３０４によって抽出されたパーセルを分割する仮想サブパーセル群から、表示領域１１１に含まれる仮想サブパーセルを抽出する。ここで抽出された仮想サブパーセルの情報は、描画部３０６に出力される。
【００４９】
描画部３０６は、区画抽出部３０４によって抽出されたパーセルに含まれた描画対象図形の情報の中から、矩形抽出部３０５によって抽出された仮想サブパーセルと関連付けされた描画対象図形の情報を用いて表示領域１１１の地図を描画する。描画部３０６によって描画された表示用データは、任意の表示機器３１０に出力される。
【００５０】
以上説明したように、描画部３０６では、表示領域１１１に含まれる仮想サブパーセルと関連付けされた描画対象図形のみが描画されるため、パーセル内に存在しながら表示領域１１１には登場しない描画対象図形は一切描画されないため、描画速度を大幅に向上させることができる。以下、上述した分割部３０１〜関連付け部３０３の処理と区画抽出部３０４〜描画部３０６までの処理について、さらに具体的な手法について説明する。
【００５１】
（パーセル単位の地図データの構成）
まず、本実施の形態にかかる描画処理装置２００によって地図画像を描画する際に利用する地図データの構成について説明する。図４は、地図データのパーセル構造と表示画面との関係を示す説明図である。図４では、地図データ４００に格納されているパーセル４０１の集合体である。
【００５２】
地図データ４００は、縦４個・横４個に並んだパーセル４０１からなり、それぞれのパーセル４０１は、パーセル幅Ｗ×パーセル高Ｈの矩形になっている。また、中央部の傾いた長方形４１１は、描画処理装置２００によって描画された地図画像を表示する画面であり、たとえば、ディスプレイ画面に表示される視野に相当する領域を表す。なお、図４の例では、地図面を垂直に見下ろした２次元正射影表示の場合を例にとっている。また、地図データ４００の中の斜線を引いた中央４個のパーセル４１０は、その一部が長方形４１１、すなわち、ユーザの視野にかかっており、描画処理の実行対象として抽出されるパーセル４０１であることをあらわしている。
【００５３】
なお、図４の例から明らかなように、画面の領域は斜線を引いた４個のパーセル４１０の領域よりもずっと小さな面積である。このような場合、斜線を引いた４個のパーセル４１０に含まれるすべての図形データに対して描画処理をおこなうと、ユーザの視野に登場する実効的な図形よりも、視野外の無駄な図形に対して多くの描画処理が費やされてしまう。したがって、この無駄を抑制するために、次に説明する仮想サブパーセルの設定がおこなわれる。
【００５４】
ここでは、まず、パーセル構造の地図データに含まれる図形データについて説明する。図５は、パーセル構造の地図データに含まれる図形データのデータフォーマットの一例を示す図表である。また、図６は、図形データの参照テーブルのデータフォーマットの一例を示す図表である。
【００５５】
図５のデータフォーマットは、従来のパーセル構造を持つ地図データと同じデータ構成である。このデータ列５００は、１個の図形のための描画属性データに対応している。この例では、図形を構成する頂点数、多角形・三角形・直線などの図形種別指定コード、図形の塗り潰し色、頂点座標値、の各データが並んだフォーマットになっている。なお、データ列５００のフォーマットはあくまで一例であり、他の属性データを追加したり、属性の並び順を変えてもよい。
【００５６】
また、実際の描画処理装置２００によって扱われるデータは数値の並びであり、最終的には０と１の二進数で実現される。しかしながら、ここでは、わかり易さを考慮し、抽象度の高い表記のまま表現する。
【００５７】
また、データ列５００の中の描画属性データは、たとえば、１ワードあたり３２ビット整数の系列として作成される。各数値の値によっては、符号無し整数としたり、１ワードあたり１６ビットにしたりしてもよい。データ列５００では、頂点数は６個、図形種別は多角形、塗り潰し色はＲＧＢＡの各８ビット４チャンネルをパックしたもの、頂点座標はｘ，ｙ各１６ビットをパックしたものを想定している。
【００５８】
また、データ列５００の中の図形種別は、典型的には直線に１を、三角形に２を、多角形に３を割り当てるような、単純なルールによって表現することができる。このような表現は、アプリケーションの都合によって依存してもよいが、一般的に、図形種類の総数はビット幅を使い尽くすほど多くはないので、ここに大きな空きビット領域があることが多い。この特徴を利用して、後述する仮想サブパーセルの識別コードの埋め込み箇所として利用できる。
【００５９】
また、図６のデータ列６００は、図５で示した図形データへの参照アドレスを保持する、図形データ参照テーブルのフォーマットをあらわしている。データ列６００には、参照オフセットアドレスだけが記録されている。また、各図形の並び順は、図形同士の重なり合いを適切に処理するために、矛盾なくソートされている。
【００６０】
（仮想サブパーセルの構成）
つぎに、仮想サブパーセルについて説明する。図１にて説明したように、本実施の形態では、パーセルをさらに、小さな矩形群に分割し、これら矩形群をサブパーセルとして設定する。
【００６１】
図７は、仮想サブパーセル構造と表示画面との関係を示す説明図である。図７は、図４に表されたパーセルのうち一部が可視である４個のパーセル４１０を拡大して、仮想サブパーセルのうち少なくとも一部が視野をあらわす長方形４１１に含まれている仮想サブパーセルを斜め格子でハッチングし仮想サブパーセル群７００としてあらわしている。後ほどおこなわれる描画処理は、仮想サブパーセル群７００の領域に限定して処理されることとなる。
【００６２】
（図形データ生成処理）
・図形データ生成における第１の手法：上位ビットを利用したパーセル分割
つぎに、描画用の図形データの生成処理についての２種類の手法について説明する。第１の手法は、上位ビットを利用して効果的にパーセル分割をおこなう。図８は、第１の手法による図形データ生成におけるパーセル上の仮想サブパーセルを示す説明図である。
【００６３】
図８のパーセル８００は、３００×３００の相対サイズからなり、００〜４４までの２５個の仮想サブパーセルに分割されている。また、仮想サブパーセルに表示した００〜４４までの２桁の数字は、そのまま仮想サブパーセルの識別コードとなる。
【００６４】
また、パーセル８００では、パーセルの相対サイズは縦横とも３００単位（３００×３００）であり、仮想サブパーセルの相対サイズは縦横とも６４単位（６４×６４）である。ただし、０４、１４、２４、３４および４０、４１、４２、４３、４４の各識別コードを持つサブパーセルは、６４で割り切れないため３００÷６４の剰余に相当する長さの辺を持っている。具体的には、仮想サブパーセル０４、１４、２４、３４は、４４×６４サイズであり、仮想サブパーセル４０、４１、４２、４３は、６４×４４サイズであり、仮想サブパーセル４４は、４４×４４サイズである。
【００６５】
また、図８では、パーセル８００に含まれる無数の図形の中から７個を代表として抜き出して例示している。図形Ａは道路を、図形Ｂ、Ｃ、Ｄは敷地境界を、図形Ｅ、Ｆ、Ｇは建物を表現している。ここで、パーセル８００における、上記７個の図形のみに着目した場合のデータ並び順すなわち描画順は、ＡＢＣＤＥＦＧの順である。実際には、図示しない多数の図形がＡからＧまでの図形と図形の間に挿入されているが、全体的にみれば描画順は適切にソートされており、重なり合いを適切に処理できるように考慮されている。
【００６６】
また、各図形の描画順は従来技術と同様にパーセル単位で最適化されている。したがって、仮想サブパーセルを仮想的な分割ではなく実際に地図データ構造そのものをサブパーセル単位に分割すると、図形Ａのように一つの仮想サブパーセルに収まらない大きな図形は、仮想サブパーセル境界で切断して図形Ａ１〜Ａ９のように複数の図形片に分割しなければならない。
【００６７】
上述のように分割された図形片は、それぞれのサブパーセルごとに新たな描画順を正しく算出し、図形データ列に挿入しなければならない。特に、図形Ｂ、Ｃ、Ｄおよび図形Ｅ、Ｆ、Ｇは、互いに離れた複数のサブパーセルに分散して入り組んでいるので、仮想サブパーセルごとにまとまったデータ並びにソートしなおさなければならない。具体的に説明すると、もともとＡＢＣＤＥＦＧの並び順だった図形データ列を、たとえば、ＢＥＡ１Ａ２Ａ３Ａ４Ａ５Ａ６Ａ７ＣＦＡ８ＤＧＡ９のような並び順に変換しなければならない。
【００６８】
しかしながら、本実施の形態では、仮想サブパーセルは、名前のとおり仮想的な概念であり、仮想サブパーセルの識別コードにしか反映されない。したがって、図形データ列の並び順はＡＢＣＤＥＦＧのままでよく、データ構造を根本的に改変する必要は無い。
【００６９】
図９は、仮想サブパーセルの識別コードを含んだ図形データのデータフォーマットの一例を示す図表である。図９のデータ列９００では、仮想サブパーセルの概念を取り入れた地図データとなっている。すなわちデータ列９００では、３２ビット幅の図形種別指定コード用ワードの空きビット領域に、仮想サブパーセルの識別コードを埋め込んでいる。たとえば、図形種別指定コードを下位１６ビットに限定し、上位１６ビットをサブパーセル識別コード用の領域とする。データ列９００において、図形種別指定コード用ワード以外のワードは、図５におけるデータ列５００のデータフォーマットと同じ構成になっている。
【００７０】
図１０は、第１の手法による図形データの生成手順を示すフローチャートである。図９によって説明したような仮想サブパーセルの設定をおこなうための手順を図１０のフローチャートにおいて説明する。まず、図形をもれなく選択するための図形数用カウンタｉと、選択した図形の頂点をもれなく選択するための頂点数用カウンタｊとをそれぞれ０にリセットし（ステップＳ１００１，Ｓ１００２）、地図素材データがストリーム的に入力される（ステップＳ１００３）。なお、図形数用カウンタｉも、頂点数用カウンタｊも、それぞれ０〜ｎ（ＥＮＤ）までをカウントする。
【００７１】
ステップＳ１００３によって入力された地図素材データを構成するデータ列の中から図形数用カウンタｉに相当する図形データを抽出し、この図形データに含まれる図形頂点座標を参照して、ｘ座標、ｙ座標を地図データベースのファイルに書き込む（ステップＳ１００４）。このステップＳ１００４の処理は、従来の描画処理と同様の処理であって、具体的には、地図素材データの書式を表示機器に適した書式へ変換するための処理に相当する。
【００７２】
また、本実施の形態では、ステップＳ１００４の処理と並列に、サブパーセル識別コードに着目した処理をおこなう。まず、ｘ座標、ｙ座標それぞれの値の上位ビットを抽出する（ステップＳ１００５）。なお、本実施の形態の場合、頂点座標フォーマットが浮動小数点型ではなく整数型であることを想定して説明すると、サブパーセルサイズが縦横６４単位である場合、０から６３までの数値を６ビットで表現できる。したがって、シフト演算により下位６ビットを除去すれば、サブパーセルのサイズと位置に関係付けられた数値が得られる。
【００７３】
たとえば、図８における図形Ｆの凹部の頂点ＡＰ１を例にあげると、この頂点座標は（ｘ，ｙ）＝（２２４，３２）である。２２４を６ビット右シフトすると３が残り、３２を６ビット右シフトすると０になる。したがって、この頂点が属する仮想サブパーセルの識別コードは３０となる。
【００７４】
図１０の説明に戻り、ステップＳ１００５によって頂点座標の上位ビットが抽出されると、つぎに、抽出された頂点の仮想サブパーセルの識別コードを変換して一時変数Ｐを生成する（ステップＳ１００６）。そして、ステップＳ１００５において読み込まれた頂点座標が図形の最初の頂点かどうか、すなわちｊ＝０か否かを判断する（ステップＳ１００７）。もしｊ＝０であり、最初の頂点であれば（ステップＳ１００７：Ｙｅｓ）、ステップＳ１００６によって生成した一時変数Ｐを、一時記憶Ｑとして保存する（ステップＳ１００８）。
【００７５】
一方、ｊ＝０ではなくステップＳ１００５によって読み込まれた頂点が最初の頂点でなければ（ステップＳ１００７：Ｎｏ）、ステップＳ１００６によって生成した一時変数Ｐと、一時記憶Ｑとを比較する（ステップＳ１００９）。
【００７６】
ステップＳ１００９における比較結果が一致すれば（ステップＳ１００９：Ｙｅｓ）、ｊ＝ｊＥＮＤかによって、すべての頂点の選択が終了したか否かを判断する（ステップＳ１０１０）。ここで、いまだに選択されていない頂点がある場合は（ステップＳ１０１０：Ｎｏ）、ｊをインクリメントし（ステップＳ１０１１）、ステップＳ１００３の処理に戻ることによって、そのまま、次の頂点数ループｊを継続する。
【００７７】
一方、ステップＳ１００９において、ＰとＱとの比較結果が一致しない場合（ステップＳ１００９：Ｎｏ）、地図データベースのファイルへの図形頂点座標の書込みに関する頂点数ループｊは継続しながら、一時変数Ｐの算出に関しては頂点数ループｊを中断し、ステップＳ１０１２の処理に移行する。
【００７８】
ステップＳ１０１２、ステップＳ１０１３では、ステップＳ１００９における一時変数Ｐと一時記憶Ｑとの比較結果に応じて、一時記憶Ｑあるいは大図形用例外コードのいずれかを、処理中の図形の仮想サブパーセルの識別コードとして採用する。具体的には、ステップＳ１０１０において、すべての頂点の選択が終了した場合（ステップＳ１０１０：Ｙｅｓ）、保存されているＱをサブパーセル識別コードに採用する（ステップＳ１０１３）。
【００７９】
また、ステップＳ１００９において、ＰとＱとの比較結果が一致しない場合（ステップＳ１００９：Ｎｏ）、大図形用例外コードをサブパーセル識別コードに採用し（ステップＳ１０１２）、ステップＳ１０１４の処理に移行する。なお、ここの大図形用例外コードとは、単独の仮想サブパーセルに収まらないような大きさおよび配置を有する図形に対して設定する識別子であり、単独に仮想サブパーセルに収まる場合をあらわすサブパーセル識別コードとは明確に区別できる。具体的には、図８では００〜４４までの１６種の仮想サブパーセルの識別コードが存在するので、これらと重複しないコードとして例えば５５を割り当てればよい。
【００８０】
そして、ステップＳ１０１２もしくはステップＳ１０１３によってサブパーセル識別コードが採用されると、採用されたコードを地図データベース中の図形データに埋め込む（ステップＳ１０１４）。その後、図形数用カウンタｉが終了したか否かを判断し（ステップＳ１０１５）、終了していなかった場合には（ステップＳ１０１５：Ｎｏ）、図形数用カウンタｉをインクリメントし（ステップＳ１０１６）、ステップＳ１００２の処理に戻る。このような処理を繰り返し、図形数用カウンタｉが終了したと判断されると（ステップＳ１０１５：Ｙｅｓ）、一連の処理を終了する。このように、すべての処理が終了すると、地図データベースのすべての図形データにサブパーセル識別コードが埋め込まれたこととなる。
【００８１】
・図形データ生成における第２の手法：パーセルを等分割
つぎに、第２の手法による図形データの生成について説明する。第２の手法では、仮想サブパーセルのサイズが等しくなるようにパーセルを分割した後、サブパーセルの識別コードを設定する。
【００８２】
図１１は、第２の手法による図形データの生成におけるパーセル上の仮想サブパーセルを示す説明図である。図１１は、一つのパーセル１１００を拡大して、第２の手法によって設定した仮想サブパーセルを重ねた状態をあらわしている。図８によって説明した第１の手法のパーセル８００との違いは、仮想サブパーセルの区切り方である。
【００８３】
第１の手法では、２のべき乗である６４を単位とすることにより、頂点座標値をシフト演算して上位ビットを取り出すだけで仮想サブパーセルの識別コードを設定していた。これに対して、図１１のように、第２の手法では、元のパーセル１１００を等分割し、仮想サブパーセルのサイズを均一化している。
【００８４】
なお、図１１では、見やすさを考慮して、図形Ｂ〜図形Ｇは仮想サブパーセルの大きさに対して実際より大きく描いており、仮想サブパーセルに収めるため配置も図８と比べてずらして表示している。現実の地図データでは、建造物の占有面積は仮想サブパーセルサイズより相対的にもっと小さいため、隣接する仮想サブパーセル境界にまたがる建造物は少数であることが多い。
【００８５】
図１２は、第２の手法による図形データの生成手順を示すフローチャートである。図１２は、図１１によって説明したような仮想サブパーセルの設定をおこなうための手順をあらわしている。なお、図１２のフローチャートには、まず図１０のフローチャートの処理のステップＳ１００１以降の処理から、ステップＳ１０１４直前の処理を示した。
【００８６】
さらに、図１０のフローチャートの処理と比較した場合に、特にステップＳ１００５〜ステップＳ１００６のみが異なる処理をおこなっている。したがって、以下、図１０のステップＳ１００５〜ステップＳ１００６との差異部分であるステップＳ１２０４〜ステップＳ１２１０の処理について詳しく説明する。
【００８７】
地図データベースのファイルに描画用図形頂点座標が書き込まれると（ステップＳ１２０３）、この処理と並列に、パーセルを仮想的に、縦にＭ分割（ステップＳ１２０４）、横にＮ分割する（ステップＳ１２０７）。このとき、ステップＳ１２０４の縦分割で得られた短冊状の領域をＨｍとする。また、ステップＳ１２０７の横分割で得られた短冊状の領域をＶｎとする。また、ｍ、ｎはそれぞれの短冊を識別する変数であり、短冊状の領域の個数はＭ個およびＮ個ある。
【００８８】
続いて、ステップＳ１２０２によって読み込まれた頂点座標ｘ，ｙが縦横それぞれどの短冊に含まれるか判断する。具体的には、短冊の境界座標値と頂点の座標値を大小比較して判定する。ｘ座標に関してはｘ∈Ｖｍか否かを判断し（ステップＳ１２０５）、ｘにＶｍが属すると判断されるまで、ｍがインクリメントされ（ステップＳ１２０６）、ループ処理がおこなわれる（ステップＳ１２０５：Ｎｏのループ）。同様に、ｙ座標に関しても、ｙ∈Ｈｎか否かを判断し（ステップＳ１２０８）、ｙにＨｎが属すると判断されるまで、ｎがインクリメントされ（ステップＳ１２０９）、ループ処理がおこなわれる（ステップＳ１２０８：Ｎｏのループ）。
【００８９】
頂点座標ｘ，ｙそれぞれに対して、頂点座標が属する短冊が見つかると（ステップＳ１２０５，Ｓ１２０８：Ｙｅｓ）、ｘ，ｙそれぞれの短冊番号をつなげてサブパーセル識別コードｍｎ（ｍｎはｍとｎとの積ではなくｍ値とｎ値を並べた値）とし、さらにｍｎを一時変数Ｐとする（ステップＳ１２１０）。一時変数Ｐ設定後の処理は、図１０のステップＳ１００７と同様であり、すべての処理が終了すると、地図データベースのすべての図形データにサブパーセル識別コードが埋め込まれたこととなる。
【００９０】
（参照テーブルに埋め込む手法）
上述した第１、第２の手法によって、それぞれサブパーセルの識別コードが設定され、対応する図形に埋め込まれるが、これらサブパーセルの識別コードを図形データに直接埋め込まずに、図形データの格納先をあらわす参照テーブルに埋め込んでもよい。
【００９１】
図１３は、仮想サブパーセルの識別コードを含んだ図形データの参照テーブルのデータフォーマットの一例を示す図表である。図１３の、データ列１３００では、上述の手法を用いて設定したサブパーセルの識別コードを、地図データへの参照テーブルに埋め込んでいる例をあらわしている。
【００９２】
地図データに含まれる図形のデータフォーマットは、図５によって例示したデータ列５００と同様である。すなわち、この手法では、サブパーセルの識別コードは図形データには埋め込まれず、外部の参照テーブル側に持たせていることになる。
【００９３】
上述した第１、第２の手法の処理と直接埋め込む際の処理との相違点は、図１０におけるステップＳ１０１４において、サブパーセル識別コードを埋め込む対象が、地図データベース中の図形データではなく、別途存在する図形データへの参照テーブルに変更される点のみである。
【００９４】
（地図描画の手順）
つぎに、描画処理装置における地図描画の手順について説明する。ここでは、車両などの移動体に搭載したナビゲーションシステムの一部として描画処理装置２００が適用された場合を例に挙げ、２種類の異なる手法を用いた地図描画の手順について説明する。第１の手法では、図９によって説明した図形データに直接サブパーセル識別コードが埋め込まれている場合について説明する。第２の手法では、図１３によって説明した参照テーブルにサブパーセル識別コードが埋め込まれている場合について説明する。
【００９５】
・地図描画の第１の手法
図１４は、第１の手法による地図描画の手順を示すフローチャートである。図１４のフローチャートにおいて、常動作中（走行中）の振る舞いをあらわしているため、本来無限ループとして表現できるが、ここでは、ユーザが走行を開始して終了するまでの一連の処理とする。
【００９６】
まず、自車位置が更新されると（ステップＳ１４０１）、地図縮尺と合わせて一般的な方法にて視野（たとえば、表示用の画面）が計算される（ステップＳ１４０２）。ステップＳ１４０２によって視野が確定すると、つぎに、少なくとも一部が視野にかかってくるようなパーセルを、所定の幾何学計算により抽出する（ステップＳ１４０３）。このステップＳ１４０３による幾何学計算は特に限定はなく、公知のものを用いる。さらに、ステップＳ１４０３と同様に、少なくとも一部が視野にかかってくるような仮想サブパーセルを抽出する（ステップＳ１４０４）。
【００９７】
そして、ステップＳ１４０３において抽出した視野にかかるパーセルに関して、図形データへの参照テーブルをメインメモリに読み込む（ステップＳ１４０５）とともに、パーセルの地図データ自体もメインメモリに読み込む（ステップＳ１４０６）。
【００９８】
さらに、ステップＳ１４０５によって読み込んだ図形データへの参照テーブルに基づいて、パーセルの地図データから図形データを読み出す（ステップＳ１４０７）。続いて、読み出した図形データから、埋め込まれたサブパーセル識別コードを抽出する（ステップＳ１４０８）。
【００９９】
そして、ステップＳ１４０８によって、抽出されたサブパーセル識別コードが、大図形用例外コードと一致するか否かを判断し（ステップＳ１４０９）、一致する場合には（ステップＳ１４０９：Ｙｅｓ）、その図形を描画する（ステップＳ１４１０）。一方、ステップＳ１４０９において、一致しないと判断された場合は（ステップＳ１４０９：Ｎｏ）、抽出されたサブパーセル識別コードがあらわす仮想サブパーセルが、ステップＳ１４０４において可視であると抽出されたか否かを判断する（ステップＳ１４１１）。
【０１００】
ステップＳ１４１１において、仮想サブパーセルがステップＳ１４０４において可視であると抽出されていた場合（ステップＳ１４１１：Ｙｅｓ）、このサブパーセル内の図形を描画して（ステップＳ１４１２）、ステップＳ１４１３の処理に移行する。一方、ステップＳ１４１１において、仮想サブパーセルがステップＳ１４０４において可視であると抽出されていなかった場合は（ステップＳ１４１１：Ｎｏ）、そのまま、ステップＳ１４１３の処理に移行する。
【０１０１】
その後、可視であると認識されたパーセルに含まれるすべての図形を処理したか判定し（ステップＳ１４１３）、まだ処理の済んでいない図形およびパーセルがあれば（ステップＳ１４１３：Ｎｏ）、ステップＳ１４０７に戻りループ処理を継続する。ステップＳ１４１３において、可視であると認識されたパーセルに含まれるすべての図形を処理したと判定された場合は（ステップＳ１４１３：Ｙｅｓ）、走行継続判断をおこない（ステップＳ１４１４）、走行継続であれば（ステップＳ１４１４：Ｙｅｓ）、ステップＳ１４０１に戻り、処理を継続させる。一方、走行終了と判断された場合には（ステップＳ１４１４：Ｎｏ）、そのまま一連の処理を終了する。
【０１０２】
・地図描画の第２の手法
図１５は、第２の手法による地図描画の手順を示すフローチャートである。図１５のフローチャートにおいて、ステップＳ１５０１〜ステップＳ１５０５までは、図１４のステップＳ１４０１〜ステップＳ１４０５の処理と同様であるため説明を省略する。
【０１０３】
そして、ステップＳ１５０５によって読み込んだ参照テーブルに埋め込まれたサブパーセル識別コードを抽出する（ステップＳ１５０６）。そして、ステップＳ１５０６によって、抽出されたサブパーセル識別コードが、大図形用例外コードと一致するか否かを判断し（ステップＳ１５０７）、一致する場合には（ステップＳ１５０７：Ｙｅｓ）、さらに、大図形用例外コードに基づいて、地図データから図形データをメインメモリに読み出し（ステップＳ１５０８）、読み出した大図形を描画する（ステップＳ１５０９）。
【０１０４】
一方、ステップＳ１５０７において、一致しないと判断された場合は（ステップＳ１５０７：Ｎｏ）、抽出されたサブパーセル識別コードがあらわす仮想サブパーセルが、ステップＳ１５０４において可視であると抽出されたか否かを判断する（ステップＳ１５１０）。ステップＳ１５１０において、仮想サブパーセルがステップＳ１５０４において可視であると抽出されていた場合（ステップＳ１５１０：Ｙｅｓ）、仮想サブパーセルについての地図データから図形データをメインメモリに読み込み（ステップＳ１５１１）、このサブパーセル内の図形を描画して（ステップＳ１５１２）、ステップＳ１５１３の処理に移行する。一方、ステップＳ１５１０において、仮想サブパーセルがステップＳ１５０４において可視であると抽出されていなかった場合は（ステップＳ１５１０：Ｎｏ）、そのまま、ステップＳ１５１３の処理に移行する。
【０１０５】
その後、可視であると認識されたパーセルに含まれるすべての図形を処理したか判定し（ステップＳ１５１３）、まだ処理の済んでいない図形およびパーセルがあれば（ステップＳ１５１３：Ｎｏ）、ステップＳ１５０６に戻りループ処理を継続する。ステップＳ１５１３において、可視であると認識されたパーセルに含まれるすべての図形を処理したと判定された場合は（ステップＳ１５１３：Ｙｅｓ）、走行継続判断をおこない（ステップＳ１５１４）、走行継続であれば（ステップＳ１５１４：Ｙｅｓ）、ステップＳ１５０１に戻り、処理を継続させる。一方、走行終了と判断された場合には（ステップＳ１５１４：Ｎｏ）、そのまま一連の処理を終了する。
【０１０６】
（各種システムへの適応例）
つぎに、上述した描画処理装置２００の各種システムへの具体的な適応例について説明する。ここでは、描画処理装置２００をカーナビゲーションシステムに適応した例と、携帯端末ナビゲーションシステムに適応した例について説明する。
【０１０７】
図１６は、カーナビゲーションシステムへの適応例を示すブロック図である。図１６では、カーナビゲーションシステムに描画処理装置２００の機能を適用させることによってカーナビゲーション装置１６００を実現している。
【０１０８】
カーナビゲーション装置１６００は、一般的な例として、ＣＰＵ１６０１と、グラフィックスＬＳＩ１６０２と、メインメモリ１６０３と、グラフィックスメモリ１６０４と、ディスプレイ１６０５と、ＩＯ（Ｉｎｐｕｔ Ｏｕｔｐｕｔ）コントローラ１６０６と、ＨＤＤユニット１６０７と、光学ディスクドライブユニット１６０８と、ジャイロセンサー１６０９と、ＧＰＳユニット１６１０とを備えた構成になっている。
【０１０９】
カーナビゲーション装置１６００では、ＩＯコントローラ１６０６を介してＣＰＵ１６０１がＨＤＤユニット１６０７のＨＤＤに格納されている地図データ１００を読み込む。読み込まれた地図データ１００は、動作や、読み込んだ地図データ１００に必要な変換を施してメインメモリ１６０３に保存する。このときの保存されるデータは、本実施の形態にて説明した仮想サブパーセルの識別コードを埋め込んだデータである。この結果、ＣＰＵ１６０１からグラフィックスＬＳＩ１６０２に描画コマンドを送る段階で、無駄なコマンドの生成が抑制され、システムの性能が向上する。
【０１１０】
図１７は、携帯端末ナビゲーションシステムへの適応例を示す説明図である。図１７のシステム１７００において、携帯電話端末１７４０のユーザからのリクエストを基地局１７３０および通信キャリア１７２０を介して受け取ったアプリケーションプロバイダ１７１０のアプリケーションサーバが、地図情報提供サービスを実行する際に、本実施の形態にて説明した、本発明が有効に機能する。
【０１１１】
具体的に説明すると、携帯電話端末１７４０の画面上で表示しようとしている視野領域の、地図空間上における位置とサイズの情報が、携帯電話端末からのリクエストパケットとして、通信キャリア１７２０を介してアプリケーションプロバイダ１７１０のアプリケーションサーバに送られる。このリクエストパケットを受けてアプリケーションプロバイダ１７１０のアプリケーションサーバは、携帯電話端末１７４０の視野領域に関与する地図データだけを仮想サブパーセルの識別コードをもとに抽出し、地図描画データに変換する。
【０１１２】
この結果、アプリケーションプロバイダ１７１０は、通信キャリア１７２０を介して、携帯電話端末１７４０の視野領域に関与する部分だけの地図描画データを送信する。このデータを用いることによって、無駄なパケットの通信が抑制され、応答性が向上する。また、図示しないが、携帯電話サービス以外の、一般的な有線のインターネットサービスとしての地図アプリケーションにも適用可能である。
【０１１３】
（ハードウェアの他の構成例）
つぎに、本実施の形態にかかる描画処理の機能を実現するためのハードウェアの他の構成例について説明する。図１８は、描画処理装置のハードウェア構成の他の例を示すブロック図である。図１８のグラフィックスＬＳＩ１８００は、サブパーセル識別コードが図形データへの参照テーブルに埋め込まれた場合の構成例を示している。
【０１１４】
従来は、視野部分のパーセルの検索はＣＰＵにておこなわれる。手順を簡単に説明すると、頂点座標は頂点シェーダーに入力されて座標変換や照光処理がおこなわれる。続いて三角形セットアップ処理を受けて、入力頂点は画面座標における三角形の頂点として解釈される。そして、ラスタライザにて走査線ごとの画素座標に変換される。その後、フラグメントシェーダーによって画素に効果色などが施され、最後に、ピクセル処理にて最終的な可視性判定や半透明処理などがおこなわれた後、フレームバッファに描画される。
【０１１５】
それに対して図１８のグラフィックスＬＳＩ１８００では、可視パーセルの検索と可視サブパーセルの検索をグラフィックスＬＳＩ１８００上のハードウェアとして実装している。可視サブパーセル検索モジュールからは、検索結果として可視と判定されたサブパーセルの識別コードが、頂点データ読込み制御モジュールに対して発行される。
【０１１６】
頂点データ読込み制御モジュールでは、可視サブパーセル検索モジュールから受け取った可視サブパーセルの識別コード（複数）と、グラフィックスＬＳＩ１８００の外部から入力されたサブパーセル識別コードとを照合する。そして、照合結果が一致した場合、もしくは大図形用例外コードが入力された場合のみ、対応する図形の頂点座標を読み込むように処理することができる。
【０１１７】
以上説明したように、本実施の形態によれば、元の地図データ構成を大幅に改変することなく、同じパーセルに含まれた図形データでありながら画面表示への地図表示に寄与しない部分の地図データの描画を抑止できる。この結果、地図データの改変に大きな制約が課せられているような条件下においても、地図描画速度の向上を図ることができる。したがって、地図データの構成を変えることなく高速な描画処理を実現することができる。
【０１１８】
なお、本実施の形態で説明した地図描画方法は、あらかじめ用意されたプログラムをパーソナル・コンピュータやワークステーションなどのコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネットなどのネットワークを介して配布することが可能な媒体であってもよい。
【０１１９】
また、本実施の形態で説明した秒が処理装置２００は、スタンダードセルやストラクチャードＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）などの特定用途向けＩＣ（以下、単に「ＡＳＩＣ」と称す。）やＦＰＧＡなどのＰＬＤ（Ｐｒｏｇｒａｍｍａｂｌｅ Ｌｏｇｉｃ Ｄｅｖｉｃｅ）によっても実現することができる。具体的には、たとえば、上述した描画処理装置２００の機能３０１〜３０６をＨＤＬ記述によって機能定義し、そのＨＤＬ記述を論理合成してＡＳＩＣやＰＬＤに与えることにより、描画処理装置２００を製造することができる。
【０１２０】
さらに、より現実的な実現方法として、本実施の形態で説明した一連の処理を、非リアルタイムに実行される前処理と、リアルタイムに実行される後処理に二分割することができる。具体的には、必ずしもリアルタイムに実行する必要が無い機能３０１〜３０３を、パーソナル・コンピュータやワークステーションなどのコンピュータで実行して、仮想サブパーセルの識別コードを伴った地図描画データベースをあらかじめ作成しておく。機能３０４〜３０６は、ナビゲーションシステムの稼動中にリアルタイムに実行される必要があるので、ＬＳＩとしてハードウェア化するか、ＣＰＵでリアルタイム実行するのが望ましい。
【０１２１】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１２２】
（付記１）画像を分割する第１領域内に存在する図形の情報を含んだ図形データを用いて前記画像を描画する描画処理装置であって、
前記図形データに対応する前記第１領域を前記第１領域より小さな第２領域に分割する分割手段と、
前記分割手段によって分割された前記第２領域から前記第１領域の図形の少なくとも一部が存在する第２領域を特定する特定手段と、
前記特定手段によって特定された第２領域と、前記図形とを関連付ける関連付け手段と、
を備えることを特徴とする描画処理装置。
【０１２３】
（付記２）前記第１領域単位に、前記図形の参照テーブルが含まれている場合、前記関連付け手段は、前記第２領域と、前記参照テーブルとを関連付けることを特徴とする付記１に記載の描画処理装置。
【０１２４】
（付記３）前記特定手段は、前記図形が前記特定された第２領域に収まらない場合、前記図形を包含する複数の第２領域を特定し、
前記関連付け手段は、前記特定手段によって特定された前記複数の第２領域と、前記図形とを関連付けることを特徴とする付記１に記載の描画処理装置。
【０１２５】
（付記４）前記特定手段は、前記図形が前記特定された第２領域に収まらない場合、前記図形の少なくとも一部が存在する複数の第２領域を特定し、
前記関連付け手段は、前記特定手段によって特定された前記複数の第２領域と、前記参照テーブルとを関連付けることを特徴とする付記２に記載の描画処理装置。
【０１２６】
（付記５）前記画像の表示領域の指示を受け付けると、前記図形データの中から、前記表示領域に含まれる前記第１領域を抽出する第１領域抽出手段と、
前記第１領域抽出手段によって抽出された前記第１領域および前記表示領域に含まれる前記第２領域を抽出する第２領域抽出手段と、
前記第１領域抽出手段によって抽出された前記第１領域の少なくとも一部に存在する前記図形の中から、前記第２領域抽出手段によって抽出された前記第２領域と関連付けされた図形を描画する描画手段と、
を備えることを特徴とする付記１〜４のいずれか一つに記載の描画処理装置。
【０１２７】
（付記６）画像を分割する第１領域内に存在する図形の情報を含んだ図形データを用いてコンピュータに前記画像を描画させる描画処理プログラムであって、
前記コンピュータを、
前記図形データに対応する前記第1領域を前記第１領域より小さな第２領域に分割する分割手段、
前記分割手段によって分割された前記第２領域の中から前記前記第１領域内の図形の少なくとも一部が存在する前記第２領域を特定する特定手段、
前記特定手段によって特定された第２領域と、前記図形とを関連付ける関連付け手段、
として機能させることを特徴とする描画処理プログラム。
【０１２８】
（付記７）前記画像の表示領域の指示を受け付けると、
前記コンピュータをさらに、
前記図形データの中から、前記表示領域に含まれる前記第１領域を抽出する第１領域抽出手段、
前記第１領域抽出手段によって抽出された前記第１領域および前記表示領域に含まれる前記第２領域を抽出する第２領域抽出手段、
前記第１領域抽出手段によって抽出された前記第１領域の少なくとも一部に存在する図形の中から、前記第２領域抽出手段によって抽出された前記第２領域と関連付けされた図形を描画する描画手段、
として機能させることを特徴とする付記６に記載の描画処理プログラム。
【０１２９】
（付記８）画像を分割する第１領域内に存在する図形の情報を含んだ図形データを用いて地図画像を描画する描画処理方法であって、
前記図形データに対応する前記第１領域を前記第１領域より小さな第２領域に分割する分割工程と、
前記分割工程によって分割された前記第２領域の中から前記第１領域内の前記図形の少なくとも一部が存在する第２領域を特定する特定工程と、
前記特定工程によって特定された第２領域と、前記図形とを関連付ける関連付け工程と、
を含むことを特徴とする描画処理方法。
【０１３０】
（付記９）前記画像の表示領域の指示を受け付けると、前記図形データの中から、前記表示領域に含まれる前記第１領域を抽出する第１領域抽出工程と、
前記第１領域抽出工程によって抽出された前記第１領域および前記表示領域に含まれる前記第２領域を抽出する第２領域抽出工程と、
前記第１領域抽出工程によって抽出された前記第１領域の少なくとも一部に存在する前記図形の中から、前記第２領域抽出工程によって抽出された前記第２領域と関連付けされた図形を描画する描画工程と、
をさらに含むことを特徴とする付記８に記載の描画処理方法。
【図面の簡単な説明】
【０１３１】
【図１】本実施の形態にかかる地図描画処理の概要を示す説明図である。
【図２】本実施の形態にかかる描画処理装置のハードウェア構成を示す説明図である。
【図３】描画処理装置の機能的構成を示すブロック図である。
【図４】地図データのパーセル構造と表示画面との関係を示す説明図である。
【図５】パーセル構造の地図データに含まれる図形データのデータフォーマットの一例を示す図表である。
【図６】図形データの参照テーブルのデータフォーマットの一例を示す図表である。
【図７】仮想サブパーセル構造と表示画面との関係を示す説明図である。
【図８】第１の手法による図形データ生成におけるパーセル上の仮想サブパーセルを示す説明図である。
【図９】仮想サブパーセルの識別コードを含んだ図形データのデータフォーマットの一例を示す図表である。
【図１０】第１の手法による図形データの生成手順を示すフローチャートである。
【図１１】第２の手法による図形データの生成におけるパーセル上の仮想サブパーセルを示す説明図である。
【図１２】第２の手法による図形データの生成手順を示すフローチャートである。
【図１３】仮想サブパーセルの識別コードを含んだ図形データの参照テーブルのデータフォーマットの一例を示す図表である。
【図１４】第１の手法による地図描画の手順を示すフローチャートである。
【図１５】第２の手法による地図描画の手順を示すフローチャートである。
【図１６】カーナビゲーションシステムへの適応例を示すブロック図である。
【図１７】携帯端末ナビゲーションシステムへの適応例を示す説明図である。
【図１８】描画処理装置のハードウェア構成の他の例を示すブロック図である。
【符号の説明】
【０１３２】
１００ 地図データ
１１０ パーセル構造
１１１ 表示領域
１２０ 仮想サブパーセル構造
２００ 描画処理装置
３０１ 分割部
３０２ 特定部
３０３ 関連付け部
３０４ 区画抽出部
３０５ 矩形抽出部
３０６ 描画部
３１０ 表示機器
１６００ カーナビゲーション装置
１６０１ ＣＰＵ
１６０２ グラフィックスＬＳＩ
１６０３ メインメモリ
１６０４ グラフィックスメモリ
１６０５ ディスプレイ
１６０６ ＩＯコントローラ
１６０７ ＨＤＤユニット
１６０８ 光学ディスクドライブユニット
１６０９ ジャイロセンサー
１６１０ ＧＰＳユニット
１７１０ アプリケーションプロバイダ
１７２０ 通信キャリア
１７３０ 基地局
１７４０ 携帯電話端末
【技術分野】
【０００１】
この発明は、２次元および３次元の地図画像の描画処理をおこなう描画処理装置、描画処理プログラムおよび描画処理方法に関する。
【背景技術】
【０００２】
従来、ナビゲーションシステムや地図表示システムでは、個別の図形データを専用のグラフィックスシステムにおいてリアルタイムに描画して地図画像を随時生成する手法が多く採用されている。これは、ナビゲーションシステムや地図表示システムでは、移動やユーザからの指示に応じて表示用の地図画像を動的に変化させる必要があるため、ビットマップのような完成された地図画像イメージを拡大縮小回転表示するよりも専用のグラフィックスシステムによって逐一生成した方が鮮明でスケーラブルな地図画像を提供できるためである。
【０００３】
また、上述のようなシステムにおいて利用される地図データは、一般的にパーセルと呼ばれる区画単位のデータの集合体として構成されている。具体的には、パーセルごとにパーセルがあらわす地図上の道路や建造物などの２次元形状データがグループ化されたデータによって構成されている。この２次元形状データは、図形の頂点座標や塗り潰し色などのリアルタイムで地図描画をおこなうために必要な描画用データを含んだ構成となっている。
【０００４】
さらに、パーセルを構成する描画用の図形データは、道路や土地利用区分や建造物の重なりを正しく処理して描画できるように最適化された順序に並べられている。したがって、たとえば、パーセルの大きさを変更するような場合にパーセル内に含まれる図形の転入／転出が生じると、図形データの並べ替えが必要になる。また、パーセルサイズの変更によって図形が隣接するパーセルの境界をまたぐような場合にも、図形をパーセル境界で切断し、切断後の図形データを各パーセルに再分配する必要がある。
【０００５】
また、パーセル単位の地図データを利用して地図描画をおこなう際は、指定された表示範囲の地図画像を表示させる。このとき、１つのパーセルの大きさはディスプレイなどの表示画面に表示される領域のサイズより大きいことも多い。すなわち、パーセルには表示画面に表示されない地図データが多数含まれることになる。また、市街地と郊外とでは地図データの密度が異なるので、パーセルサイズが均一の場合には、地図データの密度に偏りが生じる。そこで、地図データの偏りを改善してデータアクセス効率を高めるために、パーセルサイズをデータ密度に応じて可変に構築する技術も開示されている（たとえば、下記特許文献１参照。）。
【０００６】
【特許文献１】特開２００４−１７７９５９号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
しかしながら、上述したようにパーセル単位によって構成された地図データから地図画像を生成する場合、地図上に配置されている図形の描画処理は、パーセル単位で実行されてしまう。たとえ表示画面に表示される画像がパーセルに含まれる図形データの一部分しか利用しない場合であっても、同一パーセルに含まれているすべての図形データが読み出され、描画処理がおこなわれてしまう。さらに、表示画面に表示される画像が複数のパーセルにまたがった図形データである場合には、表示画面に表示される割合を問わずに２パーセル〜４パーセル分の地図データすべてが読み出され、描画処理がおこなわれてしまっていた。
【０００８】
このように、従来の描画処理は、実際には表示画面への出力に反映されない処理を多分に含んでいたため、描画処理を高速化できないという問題があった。たとえ、上記特許文献１の技術を適用させ、データ密度に応じてパーセルサイズを変え、データ量の均一化を計ったとしても、地図データ読込み量の平準化は達成されるが、表示画面以外の図形部分の描画処理を抑制することはできず、描画処理速度をあげることはできなかった。
【０００９】
この発明は、上述した従来技術による問題点を解消するため、地図データの構成を変えることなく高速な描画処理を実現することのできる描画処理装置、描画処理プログラムおよび描画処理方法を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するため、この描画処理装置、描画処理プログラムおよび描画処理方法は、画像を分割する第１領域内に存在する図形の情報を含んだ図形データを用いて前記画像を描画する描画処理であって、前記図形データに対応する前記第１領域を前記第１領域より小さな第２領域に分割し、分割された前記第２領域から前記第１領域の図形の少なくとも一部が存在する第２領域を特定し、特定された第２領域と、前記図形とを関連付ける処理を備えることを要件とする。
【００１１】
この描画処理装置、地図描画プログラムおよび描画処理方法によれば、第１領域としてたとえば区画単位で蓄積された地図データの画像に対して第１領域ごとに仮想的な分割をおこない、第１領域より小さな第２領域群を設定する。第２領域としてはたとえば区間を分割した矩形群が挙げられる。そして、第１領域内の描画対象となる図形の少なくとも一部が存在する第２領域を特定して図形と関連付ける。したがって、地図データの構成を変更せずに、第１領域に対して描画指示を受け付けた際に、描画処理をおこなうか否かの判断基準となる情報を埋め込むことができる。
【００１２】
また、上記の描画処理装置、描画処理プログラムおよび描画処理方法において、さらに、前記第１領域単位に、前記図形の参照テーブルが含まれている場合、前記関連付け手段は、前記第２領域と、前記参照テーブルとを関連付けてもよい。
【００１３】
この描画処理装置、地図描画プログラムおよび描画処理方法によれば、描画対象図形の参照テーブルと第２領域とを関連付けるため、地図データに含まれる描画対象の図形に関する情報と第２領域とを直接関連付ける必要がなく、描画処理をおこなうか否かの判断基準となる情報を埋め込むことができる。
【００１４】
また、上記の描画処理装置、描画処理プログラムおよび描画処理方法において、さらに、前記画像の表示領域の指示を受け付けると、前記図形データの中から、前記表示領域に含まれる前記第１領域を抽出する第１の抽出と、第１の抽出によって抽出された前記第１領域および前記表示領域に含まれる前記第２領域を抽出する第２の抽出と、第１の抽出によって抽出された前記第１領域の少なくとも一部に存在する前記図形の中から、第２の抽出された前記第２領域と関連付けされた図形を描画する処理を備えてもよい。
【００１５】
この描画処理装置、描画処理プログラムおよび描画処理方法によれば、指定された表示領域の地図画像を描画するために必要となる第１領域内に存在する描画対象の図形のうち、表示領域に表示される描画対象図形のみ描画され、表示されないその他の描画対象図形の描画処理の発生を防ぐことができる。
【発明の効果】
【００１６】
この描画処理装置、描画処理プログラムおよび描画処理方法によれば、地図データの構成を変えることなく高速な描画処理を実現することができるという効果を奏する。
【発明を実施するための最良の形態】
【００１７】
以下に添付図面を参照して、この描画処理装置、描画処理プログラムおよび描画処理方法の好適な実施の形態を詳細に説明する。
【００１８】
（本実施の形態にかかる地図描画処理の概要）
まず、本実施の形態にかかる地図描画処理の概要について説明する。図１は、本実施の形態にかかる地図描画処理の概要を示す説明図である。図１に示すように、本実施の形態では、地図データ１００は、パーセル構造１１０のデータの集合体として構成されている。個々のパーセル構造１１０は、さらに仮想的に分割され、仮想サブパーセル構造１２０になっている。
【００１９】
仮想サブパーセル構造１２０は、名前が指すように仮想的にパーセル構造をさらに小さなパーセル構造に分割するための概念である。したがって、地図データ１００に蓄積されている各パーセル構造１１０をあらわすデータ構造は、パーセル構造１１０内の図形データの並べ替えや、サブパーセル境界での図形の切断といったデータの再構成処理を必要とせず、データ列１３０に示すように、従来のパーセル構造１１０をあらわす情報によって構成されている。
【００２０】
本実施の形態にかかる描画処理の場合は、上述したような従来と同じデータ構成に、仮想サブパーセル構造１２０によって仮想的に分割された仮想サブパーセルに関する情報を埋め込み、描画処理判断に利用する。具体的には、１つのパーセル構造１１０には、データ列１３０のようにパーセル内に存在する描画対象図形（たとえば図形Ａ）のデータが含まれている。この描画対象図形が、仮想サブパーセル構造１２０のように分割した場合にどの仮想サブパーセルに位置するかをあらわすサブパーセル識別コード１３１が、データ列１３０の図形Ａに関する情報に追加して埋め込まれる。
【００２１】
上述の処理を実際の描画処理に沿って説明する。まず、描画処理のための準備処理として、まず地図データ１００に含まれるパーセル構造１１０ごとの図形データは、実際の地図画像の表示システム（たとえば、ナビゲーションシステム）用地図データベースを生成するために、描画対象図形のデータがどの仮想サブパーセル位置に収まるかを判定し、その結果に対応するサブパーセル識別コード１３１を与える。このとき、一つの仮想サブパーセルに収まりきらない場合は、複数の仮想サブパーセルによって表示されることをあらわすサブパーセル識別コード１３１を付与する。サブパーセル識別コード１３１は、図１のように図形データそのものに付与してもよいし、図形データの存在するアドレスを指す参照テーブルに付与してもよい。
【００２２】
つぎに、実際の地図描画に関する処理について説明する。実際の地図描画は、ユーザや、上位システムから表示領域１１１の指定の受け付けをトリガとして開始される。地図データ１００の各パーセルの図形データには、サブパーセル識別コード１３１が埋め込まれており、これら地図データ１００の中から指定された表示領域１１１が含まれるパーセル構造１１０部分の地図データ１００が読み出される。
【００２３】
従来は、読み出されたパーセル構造１１０の地図データ１００に含まれる描画対象図形をすべて描画していたが、本実施の形態の場合、表示領域１１１が含まれるパーセル構造１１０のうち、表示領域１１１に含まれるサブパーセルをあらわすサブパーセル識別コード１３１が埋め込まれた図形データを抽出して描画を実行する。したがって、表示領域１１１外に存在する図形に関しては、描画処理が省略される。
【００２４】
従来の描画処理の場合、パーセルサイズが表示領域、すなわち表示画面サイズより相対的に大きい状況では、表示画面に表示されない地図データがパーセルに多数含まれるため無駄な描画処理が発生し、描画速度の低下が著しかった。しかしながら、本実施の形態のような描画処理の場合、実際に表示される図形に対してのみ描画処理がおこなわれるため、描画速度が向上する。
【００２５】
また、従来の描画処理の場合、たとえば、クリッピング処理によって画面外データの描画を抑制するとしても、地図データに含まれる図形数が膨大なので、クリッピング対象になるか否かの判定処理自体負担となり、描画処理全体からみるとボトルネックになっていた。しかしながら、本実施の形態のような描画処理であれば上述のような問題も発生しない。
【００２６】
また、従来の描画処理では、表示画面外への描画を抑制するためにゲームグラフィックスで多用されるような、バウンディングボックスや境界球による事前可視性判定をおこなうといった対策も講じられていたが、地図描画という描画対象となる図形が特定の形状に限定される場合には、必ずしも効果的ではなかった。その理由としては、ゲームにおける人物やモンスターのようなキャラクターは、１体あたりの頂点数が多いため、バウンディングボックスによる頂点数削減効果が大きいが、地図データに含まれる図形は、キャラクターなどの図形類ほどは頂点数を持っていない。すなわち、一つ一つの頂点数削減効果が小さく、膨大な数のバウンディングボックスを処理しなければならず、描画速度の向上にはつながらなかった。本実施の形態の描画処理の場合、図形の種類を限定されることなく、効果を発揮することができる。
【００２７】
また、パーセルサイズを画面サイズに合わせて最適化することも可能であるが、処理負担から鑑みて現実的な描画処理とはいえない。その第１の理由は、地図縮尺に応じて拡大縮小描画する場合、パーセルサイズと画面サイズの相対比率が常に変化するためである。これは、最適なパーセルサイズは縮尺に応じて無数に存在し、たとえ、相対サイズ比のバリエーションを限定したとしても、同一詳細度の地図データを、複数のパーセルサイズとして実装してそれぞれ用意しなければならず、これらの条件を満たさなければ効果が得られないことを意味する。このような処理を実現させた場合、たとえば、ＨＤＤなどの地図データ格納容量の逼迫を引き起こす可能性もある。
【００２８】
また、第２の理由は、パーセルサイズの変更には、必ず図形データ格納順の並べ替え、パーセル境界での図形の切断と再分配のほか、場合によってはデータ量の増大といった事態が発生するためである。このような地図データベースのチューニングは、原理的・汎用的な措置ではなく、製品ごとの個別最適化に過ぎないため、地図データメーカーやカーナビゲーションシステムメーカーにとっては、大きな負担となり、採用したがらない傾向にある。
【００２９】
したがって、本実施の形態にかかる描画処理のように、地図データの構成変更を必要としないにもかかわらず、従来無駄とされていた部分の描画処理を省くことができるという特徴は、各種システムにとって適用しやすい処理であるという効果も含んでいる。したがって、以下に図１によって説明した描画処理の特徴を備えた描画処理装置を実現するための具体的な構成や処理内容について詳しく説明する。
【００３０】
（地図描画装置のハードウェア構成）
まず、本実施の形態にかかる描画処理を実現する描画処理装置のハードウェア構成について説明する。図２は、本実施の形態にかかる描画処理装置のハードウェア構成を示す説明図である。
【００３１】
図２において、描画処理装置２００は、ＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）２０１と、ＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）２０２と、ＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）２０３と、ハードディスクドライブ２０４と、ハードディスク２０５と、光ディスクドライブ２０６と、光ディスク２０７と、ディスプレイ２０８と、Ｉ／Ｆ（インターフェース）２０９と、キーボード２１０と、マウス２１１と、スキャナ２１２と、プリンタ２１３と、を備えている。また、各構成部はバス２００によってそれぞれ接続されている。
【００３２】
ここで、ＣＰＵ２０１は、描画処理装置２００の全体の制御を司る。ＲＯＭ２０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ２０３は、ＣＰＵ２０１のワークエリアとして使用される。ハードディスクドライブ２０４は、ＣＰＵ２０１の制御にしたがってハードディスク２０５に対するデータのリード／ライトを制御する。ハードディスク２０５は、ハードディスクドライブ２０４の制御で書き込まれたデータを記憶する。
【００３３】
光ディスクドライブ２０６は、ＣＰＵ２０１の制御にしたがって光ディスク２０７に対するデータのリード／ライトを制御する。光ディスク２０７は、光ディスクドライブ２０６の制御で書き込まれたデータを記憶したり、光ディスク２０７に記憶されたデータを描画処理装置２００に読み取らせたりする。
【００３４】
また、光ディスク２０７として、ＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｋ）、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｋ）、ＭＯ（Ｍａｇｎｅｔｏ Ｏｐｔｉｃａｌ）、メモリーカードなどを採用することができる。ディスプレイ２０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ２０８は、たとえば、ＣＲＴ（Ｃａｔｈｏｄｅ Ｒａｙ Ｔｕｂｅ）、ＴＦＴ（Ｔｈｉｎ Ｆｉｌｍ Ｔｒａｎｓｉｓｔｏｒ）液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００３５】
Ｉ／Ｆ２０９は、通信回線を通じてインターネットなどのネットワーク２１４に接続され、このネットワーク２１４を介して他の装置に接続される。そして、Ｉ／Ｆ２０９は、ネットワーク２１４と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ２０９には、たとえば、モデムやＬＡＮ（Ｌｏｃａｌ Ａｒｅａ Ｎｅｔｗｏｒｋ）アダプタなどを採用することができる。
【００３６】
キーボード２１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス２１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００３７】
スキャナ２１２は、画像を光学的に読み取り、描画処理装置２００内に画像データを取り込む。なお、スキャナ２１２は、ＯＣＲ（Ｏｐｔｉｃａｌ Ｃｈａｒａｃｔｅｒ Ｒｅａｄｅｒ）機能を持たせてもよい。また、プリンタ２１３は、画像データや文書データを印刷する。プリンタ２１３には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。
【００３８】
なお、本実施の形態にかかる描画処理装置２００の場合は、図２に例示したような単独の装置として実現する場合の他に、カーナビゲーション装置とともにカーナビゲーションシステムを実現する場合や、携帯端末装置とともに携帯端末ナビゲーションシステムを実現する場合などがある。したがって、図２の描画処理装置２００のハードウェア構成はあくまで一例であり、他の構成によって実現してもよい。なお、カーナビゲーションシステムや携帯端末ナビゲーションシステムとして実現する例については後述する。
【００３９】
（描画処理装置の機能的構成）
つぎに、描画処理装置の機能的構成について説明する。図３は、描画処理装置の機能的構成を示すブロック図である。図３において、描画処理装置２００は、分割部３０１と、特定部３０２と、関連付け部３０３と、区画抽出部３０４と、矩形抽出部３０５と、描画部３０６と、を備えている。これら各機能３０１〜３０６は、描画処理装置２００の記憶部（たとえば、図２にて説明したハードディスク２０５など）に記憶された当該機能３０１〜３０６に関するプログラムをＣＰＵに実行させることにより、または、入出力Ｉ／Ｆにより、当該機能を実現することができる。
【００４０】
描画処理装置２００は、地図を分割する区画（第１領域）単位としてパーセル単位にそれぞれ当該パーセル内に存在する描画対象図形の情報を含んだ地図データ１００を用いて地図画像を描画する。したがって、パーセル単位のデータ構造をもつ地図データ１００を用意して描画処理装置２００に読み込ませる。
【００４１】
分割部３０１は、読み込んだ地図データの中の任意のパーセルをより小さな矩形（第２領域）群、すなわち、仮想サブパーセル群に分割する。なお、本実施の形態では仮想サブパーセルとなる第２領域は矩形になるように分割しているが、区画がもれなく分割されていれば第２領域の形状は特に限定されない。分割部３０１による分割とは上述したように仮想的な分割であり、地図データ１００を分割するのではなく、分割した場合の個々の矩形である仮想サブパーセルの配置をあらわす設定情報を生成する処理をおこなう。
【００４２】
特定部３０２は、分割部３０１によって分割された仮想サブパーセル群の中からパーセル内の描画対象図形の少なくとも一部が存在する仮想サブパーセルを特定する。
【００４３】
関連付け部３０３は、特定部３０２によって特定された仮想サブパーセルと、描画対象図形とを関連付ける。仮想サブパーセルと、描画対象図形とを関連付けるとは、具体的には、描画対象図形に関する情報に特定された仮想サブパーセルの設定情報と関連付けて記録する。一例として、図１のデータ列１３０のように、描画対象図形に関する情報にサブパーセル識別コード１３１を埋め込むような手法がある。
【００４４】
なお、関連付け部３０３は、描画対象図形に関する情報の格納先をあらわす参照テーブルが含まれている場合であれば、描画対象図形ではなく、仮想サブパーセルと、参照テーブルとを関連付けてもよい。
【００４５】
さらに、上述したように、特定部３０２によって、描画対象図形が一つの仮想サブパーセルに収まらずに、描画対象図形の少なくとも一部が存在する複数の仮想サブパーセルを特定した場合、関連付け部３０３は、特定された複数の仮想サブパーセルと、描画対象図形の情報や参照テーブルとを関連付けてもよい。
【００４６】
以上説明した分割部３０１〜関連付け部３０３によって、本実施の形態にかかる描画処理をおこなうための準備が終了したことになる。つぎに、実際に地図画像を描画するための処理について説明する。この処理は、上述したように、外部からの表示領域指示に関する情報の受け付けがトリガとなる。
【００４７】
区画抽出部３０４は、描画環境設定から地図の表示領域１１１の指示を受け付けると、地図データ１００の中から、表示領域１１１に含まれるパーセルを抽出する。ここで抽出されたパーセルの情報は、矩形抽出部３０５に出力される。
【００４８】
矩形抽出部３０５は、区画抽出部３０４によって抽出されたパーセルを分割する仮想サブパーセル群から、表示領域１１１に含まれる仮想サブパーセルを抽出する。ここで抽出された仮想サブパーセルの情報は、描画部３０６に出力される。
【００４９】
描画部３０６は、区画抽出部３０４によって抽出されたパーセルに含まれた描画対象図形の情報の中から、矩形抽出部３０５によって抽出された仮想サブパーセルと関連付けされた描画対象図形の情報を用いて表示領域１１１の地図を描画する。描画部３０６によって描画された表示用データは、任意の表示機器３１０に出力される。
【００５０】
以上説明したように、描画部３０６では、表示領域１１１に含まれる仮想サブパーセルと関連付けされた描画対象図形のみが描画されるため、パーセル内に存在しながら表示領域１１１には登場しない描画対象図形は一切描画されないため、描画速度を大幅に向上させることができる。以下、上述した分割部３０１〜関連付け部３０３の処理と区画抽出部３０４〜描画部３０６までの処理について、さらに具体的な手法について説明する。
【００５１】
（パーセル単位の地図データの構成）
まず、本実施の形態にかかる描画処理装置２００によって地図画像を描画する際に利用する地図データの構成について説明する。図４は、地図データのパーセル構造と表示画面との関係を示す説明図である。図４では、地図データ４００に格納されているパーセル４０１の集合体である。
【００５２】
地図データ４００は、縦４個・横４個に並んだパーセル４０１からなり、それぞれのパーセル４０１は、パーセル幅Ｗ×パーセル高Ｈの矩形になっている。また、中央部の傾いた長方形４１１は、描画処理装置２００によって描画された地図画像を表示する画面であり、たとえば、ディスプレイ画面に表示される視野に相当する領域を表す。なお、図４の例では、地図面を垂直に見下ろした２次元正射影表示の場合を例にとっている。また、地図データ４００の中の斜線を引いた中央４個のパーセル４１０は、その一部が長方形４１１、すなわち、ユーザの視野にかかっており、描画処理の実行対象として抽出されるパーセル４０１であることをあらわしている。
【００５３】
なお、図４の例から明らかなように、画面の領域は斜線を引いた４個のパーセル４１０の領域よりもずっと小さな面積である。このような場合、斜線を引いた４個のパーセル４１０に含まれるすべての図形データに対して描画処理をおこなうと、ユーザの視野に登場する実効的な図形よりも、視野外の無駄な図形に対して多くの描画処理が費やされてしまう。したがって、この無駄を抑制するために、次に説明する仮想サブパーセルの設定がおこなわれる。
【００５４】
ここでは、まず、パーセル構造の地図データに含まれる図形データについて説明する。図５は、パーセル構造の地図データに含まれる図形データのデータフォーマットの一例を示す図表である。また、図６は、図形データの参照テーブルのデータフォーマットの一例を示す図表である。
【００５５】
図５のデータフォーマットは、従来のパーセル構造を持つ地図データと同じデータ構成である。このデータ列５００は、１個の図形のための描画属性データに対応している。この例では、図形を構成する頂点数、多角形・三角形・直線などの図形種別指定コード、図形の塗り潰し色、頂点座標値、の各データが並んだフォーマットになっている。なお、データ列５００のフォーマットはあくまで一例であり、他の属性データを追加したり、属性の並び順を変えてもよい。
【００５６】
また、実際の描画処理装置２００によって扱われるデータは数値の並びであり、最終的には０と１の二進数で実現される。しかしながら、ここでは、わかり易さを考慮し、抽象度の高い表記のまま表現する。
【００５７】
また、データ列５００の中の描画属性データは、たとえば、１ワードあたり３２ビット整数の系列として作成される。各数値の値によっては、符号無し整数としたり、１ワードあたり１６ビットにしたりしてもよい。データ列５００では、頂点数は６個、図形種別は多角形、塗り潰し色はＲＧＢＡの各８ビット４チャンネルをパックしたもの、頂点座標はｘ，ｙ各１６ビットをパックしたものを想定している。
【００５８】
また、データ列５００の中の図形種別は、典型的には直線に１を、三角形に２を、多角形に３を割り当てるような、単純なルールによって表現することができる。このような表現は、アプリケーションの都合によって依存してもよいが、一般的に、図形種類の総数はビット幅を使い尽くすほど多くはないので、ここに大きな空きビット領域があることが多い。この特徴を利用して、後述する仮想サブパーセルの識別コードの埋め込み箇所として利用できる。
【００５９】
また、図６のデータ列６００は、図５で示した図形データへの参照アドレスを保持する、図形データ参照テーブルのフォーマットをあらわしている。データ列６００には、参照オフセットアドレスだけが記録されている。また、各図形の並び順は、図形同士の重なり合いを適切に処理するために、矛盾なくソートされている。
【００６０】
（仮想サブパーセルの構成）
つぎに、仮想サブパーセルについて説明する。図１にて説明したように、本実施の形態では、パーセルをさらに、小さな矩形群に分割し、これら矩形群をサブパーセルとして設定する。
【００６１】
図７は、仮想サブパーセル構造と表示画面との関係を示す説明図である。図７は、図４に表されたパーセルのうち一部が可視である４個のパーセル４１０を拡大して、仮想サブパーセルのうち少なくとも一部が視野をあらわす長方形４１１に含まれている仮想サブパーセルを斜め格子でハッチングし仮想サブパーセル群７００としてあらわしている。後ほどおこなわれる描画処理は、仮想サブパーセル群７００の領域に限定して処理されることとなる。
【００６２】
（図形データ生成処理）
・図形データ生成における第１の手法：上位ビットを利用したパーセル分割
つぎに、描画用の図形データの生成処理についての２種類の手法について説明する。第１の手法は、上位ビットを利用して効果的にパーセル分割をおこなう。図８は、第１の手法による図形データ生成におけるパーセル上の仮想サブパーセルを示す説明図である。
【００６３】
図８のパーセル８００は、３００×３００の相対サイズからなり、００〜４４までの２５個の仮想サブパーセルに分割されている。また、仮想サブパーセルに表示した００〜４４までの２桁の数字は、そのまま仮想サブパーセルの識別コードとなる。
【００６４】
また、パーセル８００では、パーセルの相対サイズは縦横とも３００単位（３００×３００）であり、仮想サブパーセルの相対サイズは縦横とも６４単位（６４×６４）である。ただし、０４、１４、２４、３４および４０、４１、４２、４３、４４の各識別コードを持つサブパーセルは、６４で割り切れないため３００÷６４の剰余に相当する長さの辺を持っている。具体的には、仮想サブパーセル０４、１４、２４、３４は、４４×６４サイズであり、仮想サブパーセル４０、４１、４２、４３は、６４×４４サイズであり、仮想サブパーセル４４は、４４×４４サイズである。
【００６５】
また、図８では、パーセル８００に含まれる無数の図形の中から７個を代表として抜き出して例示している。図形Ａは道路を、図形Ｂ、Ｃ、Ｄは敷地境界を、図形Ｅ、Ｆ、Ｇは建物を表現している。ここで、パーセル８００における、上記７個の図形のみに着目した場合のデータ並び順すなわち描画順は、ＡＢＣＤＥＦＧの順である。実際には、図示しない多数の図形がＡからＧまでの図形と図形の間に挿入されているが、全体的にみれば描画順は適切にソートされており、重なり合いを適切に処理できるように考慮されている。
【００６６】
また、各図形の描画順は従来技術と同様にパーセル単位で最適化されている。したがって、仮想サブパーセルを仮想的な分割ではなく実際に地図データ構造そのものをサブパーセル単位に分割すると、図形Ａのように一つの仮想サブパーセルに収まらない大きな図形は、仮想サブパーセル境界で切断して図形Ａ１〜Ａ９のように複数の図形片に分割しなければならない。
【００６７】
上述のように分割された図形片は、それぞれのサブパーセルごとに新たな描画順を正しく算出し、図形データ列に挿入しなければならない。特に、図形Ｂ、Ｃ、Ｄおよび図形Ｅ、Ｆ、Ｇは、互いに離れた複数のサブパーセルに分散して入り組んでいるので、仮想サブパーセルごとにまとまったデータ並びにソートしなおさなければならない。具体的に説明すると、もともとＡＢＣＤＥＦＧの並び順だった図形データ列を、たとえば、ＢＥＡ１Ａ２Ａ３Ａ４Ａ５Ａ６Ａ７ＣＦＡ８ＤＧＡ９のような並び順に変換しなければならない。
【００６８】
しかしながら、本実施の形態では、仮想サブパーセルは、名前のとおり仮想的な概念であり、仮想サブパーセルの識別コードにしか反映されない。したがって、図形データ列の並び順はＡＢＣＤＥＦＧのままでよく、データ構造を根本的に改変する必要は無い。
【００６９】
図９は、仮想サブパーセルの識別コードを含んだ図形データのデータフォーマットの一例を示す図表である。図９のデータ列９００では、仮想サブパーセルの概念を取り入れた地図データとなっている。すなわちデータ列９００では、３２ビット幅の図形種別指定コード用ワードの空きビット領域に、仮想サブパーセルの識別コードを埋め込んでいる。たとえば、図形種別指定コードを下位１６ビットに限定し、上位１６ビットをサブパーセル識別コード用の領域とする。データ列９００において、図形種別指定コード用ワード以外のワードは、図５におけるデータ列５００のデータフォーマットと同じ構成になっている。
【００７０】
図１０は、第１の手法による図形データの生成手順を示すフローチャートである。図９によって説明したような仮想サブパーセルの設定をおこなうための手順を図１０のフローチャートにおいて説明する。まず、図形をもれなく選択するための図形数用カウンタｉと、選択した図形の頂点をもれなく選択するための頂点数用カウンタｊとをそれぞれ０にリセットし（ステップＳ１００１，Ｓ１００２）、地図素材データがストリーム的に入力される（ステップＳ１００３）。なお、図形数用カウンタｉも、頂点数用カウンタｊも、それぞれ０〜ｎ（ＥＮＤ）までをカウントする。
【００７１】
ステップＳ１００３によって入力された地図素材データを構成するデータ列の中から図形数用カウンタｉに相当する図形データを抽出し、この図形データに含まれる図形頂点座標を参照して、ｘ座標、ｙ座標を地図データベースのファイルに書き込む（ステップＳ１００４）。このステップＳ１００４の処理は、従来の描画処理と同様の処理であって、具体的には、地図素材データの書式を表示機器に適した書式へ変換するための処理に相当する。
【００７２】
また、本実施の形態では、ステップＳ１００４の処理と並列に、サブパーセル識別コードに着目した処理をおこなう。まず、ｘ座標、ｙ座標それぞれの値の上位ビットを抽出する（ステップＳ１００５）。なお、本実施の形態の場合、頂点座標フォーマットが浮動小数点型ではなく整数型であることを想定して説明すると、サブパーセルサイズが縦横６４単位である場合、０から６３までの数値を６ビットで表現できる。したがって、シフト演算により下位６ビットを除去すれば、サブパーセルのサイズと位置に関係付けられた数値が得られる。
【００７３】
たとえば、図８における図形Ｆの凹部の頂点ＡＰ１を例にあげると、この頂点座標は（ｘ，ｙ）＝（２２４，３２）である。２２４を６ビット右シフトすると３が残り、３２を６ビット右シフトすると０になる。したがって、この頂点が属する仮想サブパーセルの識別コードは３０となる。
【００７４】
図１０の説明に戻り、ステップＳ１００５によって頂点座標の上位ビットが抽出されると、つぎに、抽出された頂点の仮想サブパーセルの識別コードを変換して一時変数Ｐを生成する（ステップＳ１００６）。そして、ステップＳ１００５において読み込まれた頂点座標が図形の最初の頂点かどうか、すなわちｊ＝０か否かを判断する（ステップＳ１００７）。もしｊ＝０であり、最初の頂点であれば（ステップＳ１００７：Ｙｅｓ）、ステップＳ１００６によって生成した一時変数Ｐを、一時記憶Ｑとして保存する（ステップＳ１００８）。
【００７５】
一方、ｊ＝０ではなくステップＳ１００５によって読み込まれた頂点が最初の頂点でなければ（ステップＳ１００７：Ｎｏ）、ステップＳ１００６によって生成した一時変数Ｐと、一時記憶Ｑとを比較する（ステップＳ１００９）。
【００７６】
ステップＳ１００９における比較結果が一致すれば（ステップＳ１００９：Ｙｅｓ）、ｊ＝ｊＥＮＤかによって、すべての頂点の選択が終了したか否かを判断する（ステップＳ１０１０）。ここで、いまだに選択されていない頂点がある場合は（ステップＳ１０１０：Ｎｏ）、ｊをインクリメントし（ステップＳ１０１１）、ステップＳ１００３の処理に戻ることによって、そのまま、次の頂点数ループｊを継続する。
【００７７】
一方、ステップＳ１００９において、ＰとＱとの比較結果が一致しない場合（ステップＳ１００９：Ｎｏ）、地図データベースのファイルへの図形頂点座標の書込みに関する頂点数ループｊは継続しながら、一時変数Ｐの算出に関しては頂点数ループｊを中断し、ステップＳ１０１２の処理に移行する。
【００７８】
ステップＳ１０１２、ステップＳ１０１３では、ステップＳ１００９における一時変数Ｐと一時記憶Ｑとの比較結果に応じて、一時記憶Ｑあるいは大図形用例外コードのいずれかを、処理中の図形の仮想サブパーセルの識別コードとして採用する。具体的には、ステップＳ１０１０において、すべての頂点の選択が終了した場合（ステップＳ１０１０：Ｙｅｓ）、保存されているＱをサブパーセル識別コードに採用する（ステップＳ１０１３）。
【００７９】
また、ステップＳ１００９において、ＰとＱとの比較結果が一致しない場合（ステップＳ１００９：Ｎｏ）、大図形用例外コードをサブパーセル識別コードに採用し（ステップＳ１０１２）、ステップＳ１０１４の処理に移行する。なお、ここの大図形用例外コードとは、単独の仮想サブパーセルに収まらないような大きさおよび配置を有する図形に対して設定する識別子であり、単独に仮想サブパーセルに収まる場合をあらわすサブパーセル識別コードとは明確に区別できる。具体的には、図８では００〜４４までの１６種の仮想サブパーセルの識別コードが存在するので、これらと重複しないコードとして例えば５５を割り当てればよい。
【００８０】
そして、ステップＳ１０１２もしくはステップＳ１０１３によってサブパーセル識別コードが採用されると、採用されたコードを地図データベース中の図形データに埋め込む（ステップＳ１０１４）。その後、図形数用カウンタｉが終了したか否かを判断し（ステップＳ１０１５）、終了していなかった場合には（ステップＳ１０１５：Ｎｏ）、図形数用カウンタｉをインクリメントし（ステップＳ１０１６）、ステップＳ１００２の処理に戻る。このような処理を繰り返し、図形数用カウンタｉが終了したと判断されると（ステップＳ１０１５：Ｙｅｓ）、一連の処理を終了する。このように、すべての処理が終了すると、地図データベースのすべての図形データにサブパーセル識別コードが埋め込まれたこととなる。
【００８１】
・図形データ生成における第２の手法：パーセルを等分割
つぎに、第２の手法による図形データの生成について説明する。第２の手法では、仮想サブパーセルのサイズが等しくなるようにパーセルを分割した後、サブパーセルの識別コードを設定する。
【００８２】
図１１は、第２の手法による図形データの生成におけるパーセル上の仮想サブパーセルを示す説明図である。図１１は、一つのパーセル１１００を拡大して、第２の手法によって設定した仮想サブパーセルを重ねた状態をあらわしている。図８によって説明した第１の手法のパーセル８００との違いは、仮想サブパーセルの区切り方である。
【００８３】
第１の手法では、２のべき乗である６４を単位とすることにより、頂点座標値をシフト演算して上位ビットを取り出すだけで仮想サブパーセルの識別コードを設定していた。これに対して、図１１のように、第２の手法では、元のパーセル１１００を等分割し、仮想サブパーセルのサイズを均一化している。
【００８４】
なお、図１１では、見やすさを考慮して、図形Ｂ〜図形Ｇは仮想サブパーセルの大きさに対して実際より大きく描いており、仮想サブパーセルに収めるため配置も図８と比べてずらして表示している。現実の地図データでは、建造物の占有面積は仮想サブパーセルサイズより相対的にもっと小さいため、隣接する仮想サブパーセル境界にまたがる建造物は少数であることが多い。
【００８５】
図１２は、第２の手法による図形データの生成手順を示すフローチャートである。図１２は、図１１によって説明したような仮想サブパーセルの設定をおこなうための手順をあらわしている。なお、図１２のフローチャートには、まず図１０のフローチャートの処理のステップＳ１００１以降の処理から、ステップＳ１０１４直前の処理を示した。
【００８６】
さらに、図１０のフローチャートの処理と比較した場合に、特にステップＳ１００５〜ステップＳ１００６のみが異なる処理をおこなっている。したがって、以下、図１０のステップＳ１００５〜ステップＳ１００６との差異部分であるステップＳ１２０４〜ステップＳ１２１０の処理について詳しく説明する。
【００８７】
地図データベースのファイルに描画用図形頂点座標が書き込まれると（ステップＳ１２０３）、この処理と並列に、パーセルを仮想的に、縦にＭ分割（ステップＳ１２０４）、横にＮ分割する（ステップＳ１２０７）。このとき、ステップＳ１２０４の縦分割で得られた短冊状の領域をＨｍとする。また、ステップＳ１２０７の横分割で得られた短冊状の領域をＶｎとする。また、ｍ、ｎはそれぞれの短冊を識別する変数であり、短冊状の領域の個数はＭ個およびＮ個ある。
【００８８】
続いて、ステップＳ１２０２によって読み込まれた頂点座標ｘ，ｙが縦横それぞれどの短冊に含まれるか判断する。具体的には、短冊の境界座標値と頂点の座標値を大小比較して判定する。ｘ座標に関してはｘ∈Ｖｍか否かを判断し（ステップＳ１２０５）、ｘにＶｍが属すると判断されるまで、ｍがインクリメントされ（ステップＳ１２０６）、ループ処理がおこなわれる（ステップＳ１２０５：Ｎｏのループ）。同様に、ｙ座標に関しても、ｙ∈Ｈｎか否かを判断し（ステップＳ１２０８）、ｙにＨｎが属すると判断されるまで、ｎがインクリメントされ（ステップＳ１２０９）、ループ処理がおこなわれる（ステップＳ１２０８：Ｎｏのループ）。
【００８９】
頂点座標ｘ，ｙそれぞれに対して、頂点座標が属する短冊が見つかると（ステップＳ１２０５，Ｓ１２０８：Ｙｅｓ）、ｘ，ｙそれぞれの短冊番号をつなげてサブパーセル識別コードｍｎ（ｍｎはｍとｎとの積ではなくｍ値とｎ値を並べた値）とし、さらにｍｎを一時変数Ｐとする（ステップＳ１２１０）。一時変数Ｐ設定後の処理は、図１０のステップＳ１００７と同様であり、すべての処理が終了すると、地図データベースのすべての図形データにサブパーセル識別コードが埋め込まれたこととなる。
【００９０】
（参照テーブルに埋め込む手法）
上述した第１、第２の手法によって、それぞれサブパーセルの識別コードが設定され、対応する図形に埋め込まれるが、これらサブパーセルの識別コードを図形データに直接埋め込まずに、図形データの格納先をあらわす参照テーブルに埋め込んでもよい。
【００９１】
図１３は、仮想サブパーセルの識別コードを含んだ図形データの参照テーブルのデータフォーマットの一例を示す図表である。図１３の、データ列１３００では、上述の手法を用いて設定したサブパーセルの識別コードを、地図データへの参照テーブルに埋め込んでいる例をあらわしている。
【００９２】
地図データに含まれる図形のデータフォーマットは、図５によって例示したデータ列５００と同様である。すなわち、この手法では、サブパーセルの識別コードは図形データには埋め込まれず、外部の参照テーブル側に持たせていることになる。
【００９３】
上述した第１、第２の手法の処理と直接埋め込む際の処理との相違点は、図１０におけるステップＳ１０１４において、サブパーセル識別コードを埋め込む対象が、地図データベース中の図形データではなく、別途存在する図形データへの参照テーブルに変更される点のみである。
【００９４】
（地図描画の手順）
つぎに、描画処理装置における地図描画の手順について説明する。ここでは、車両などの移動体に搭載したナビゲーションシステムの一部として描画処理装置２００が適用された場合を例に挙げ、２種類の異なる手法を用いた地図描画の手順について説明する。第１の手法では、図９によって説明した図形データに直接サブパーセル識別コードが埋め込まれている場合について説明する。第２の手法では、図１３によって説明した参照テーブルにサブパーセル識別コードが埋め込まれている場合について説明する。
【００９５】
・地図描画の第１の手法
図１４は、第１の手法による地図描画の手順を示すフローチャートである。図１４のフローチャートにおいて、常動作中（走行中）の振る舞いをあらわしているため、本来無限ループとして表現できるが、ここでは、ユーザが走行を開始して終了するまでの一連の処理とする。
【００９６】
まず、自車位置が更新されると（ステップＳ１４０１）、地図縮尺と合わせて一般的な方法にて視野（たとえば、表示用の画面）が計算される（ステップＳ１４０２）。ステップＳ１４０２によって視野が確定すると、つぎに、少なくとも一部が視野にかかってくるようなパーセルを、所定の幾何学計算により抽出する（ステップＳ１４０３）。このステップＳ１４０３による幾何学計算は特に限定はなく、公知のものを用いる。さらに、ステップＳ１４０３と同様に、少なくとも一部が視野にかかってくるような仮想サブパーセルを抽出する（ステップＳ１４０４）。
【００９７】
そして、ステップＳ１４０３において抽出した視野にかかるパーセルに関して、図形データへの参照テーブルをメインメモリに読み込む（ステップＳ１４０５）とともに、パーセルの地図データ自体もメインメモリに読み込む（ステップＳ１４０６）。
【００９８】
さらに、ステップＳ１４０５によって読み込んだ図形データへの参照テーブルに基づいて、パーセルの地図データから図形データを読み出す（ステップＳ１４０７）。続いて、読み出した図形データから、埋め込まれたサブパーセル識別コードを抽出する（ステップＳ１４０８）。
【００９９】
そして、ステップＳ１４０８によって、抽出されたサブパーセル識別コードが、大図形用例外コードと一致するか否かを判断し（ステップＳ１４０９）、一致する場合には（ステップＳ１４０９：Ｙｅｓ）、その図形を描画する（ステップＳ１４１０）。一方、ステップＳ１４０９において、一致しないと判断された場合は（ステップＳ１４０９：Ｎｏ）、抽出されたサブパーセル識別コードがあらわす仮想サブパーセルが、ステップＳ１４０４において可視であると抽出されたか否かを判断する（ステップＳ１４１１）。
【０１００】
ステップＳ１４１１において、仮想サブパーセルがステップＳ１４０４において可視であると抽出されていた場合（ステップＳ１４１１：Ｙｅｓ）、このサブパーセル内の図形を描画して（ステップＳ１４１２）、ステップＳ１４１３の処理に移行する。一方、ステップＳ１４１１において、仮想サブパーセルがステップＳ１４０４において可視であると抽出されていなかった場合は（ステップＳ１４１１：Ｎｏ）、そのまま、ステップＳ１４１３の処理に移行する。
【０１０１】
その後、可視であると認識されたパーセルに含まれるすべての図形を処理したか判定し（ステップＳ１４１３）、まだ処理の済んでいない図形およびパーセルがあれば（ステップＳ１４１３：Ｎｏ）、ステップＳ１４０７に戻りループ処理を継続する。ステップＳ１４１３において、可視であると認識されたパーセルに含まれるすべての図形を処理したと判定された場合は（ステップＳ１４１３：Ｙｅｓ）、走行継続判断をおこない（ステップＳ１４１４）、走行継続であれば（ステップＳ１４１４：Ｙｅｓ）、ステップＳ１４０１に戻り、処理を継続させる。一方、走行終了と判断された場合には（ステップＳ１４１４：Ｎｏ）、そのまま一連の処理を終了する。
【０１０２】
・地図描画の第２の手法
図１５は、第２の手法による地図描画の手順を示すフローチャートである。図１５のフローチャートにおいて、ステップＳ１５０１〜ステップＳ１５０５までは、図１４のステップＳ１４０１〜ステップＳ１４０５の処理と同様であるため説明を省略する。
【０１０３】
そして、ステップＳ１５０５によって読み込んだ参照テーブルに埋め込まれたサブパーセル識別コードを抽出する（ステップＳ１５０６）。そして、ステップＳ１５０６によって、抽出されたサブパーセル識別コードが、大図形用例外コードと一致するか否かを判断し（ステップＳ１５０７）、一致する場合には（ステップＳ１５０７：Ｙｅｓ）、さらに、大図形用例外コードに基づいて、地図データから図形データをメインメモリに読み出し（ステップＳ１５０８）、読み出した大図形を描画する（ステップＳ１５０９）。
【０１０４】
一方、ステップＳ１５０７において、一致しないと判断された場合は（ステップＳ１５０７：Ｎｏ）、抽出されたサブパーセル識別コードがあらわす仮想サブパーセルが、ステップＳ１５０４において可視であると抽出されたか否かを判断する（ステップＳ１５１０）。ステップＳ１５１０において、仮想サブパーセルがステップＳ１５０４において可視であると抽出されていた場合（ステップＳ１５１０：Ｙｅｓ）、仮想サブパーセルについての地図データから図形データをメインメモリに読み込み（ステップＳ１５１１）、このサブパーセル内の図形を描画して（ステップＳ１５１２）、ステップＳ１５１３の処理に移行する。一方、ステップＳ１５１０において、仮想サブパーセルがステップＳ１５０４において可視であると抽出されていなかった場合は（ステップＳ１５１０：Ｎｏ）、そのまま、ステップＳ１５１３の処理に移行する。
【０１０５】
その後、可視であると認識されたパーセルに含まれるすべての図形を処理したか判定し（ステップＳ１５１３）、まだ処理の済んでいない図形およびパーセルがあれば（ステップＳ１５１３：Ｎｏ）、ステップＳ１５０６に戻りループ処理を継続する。ステップＳ１５１３において、可視であると認識されたパーセルに含まれるすべての図形を処理したと判定された場合は（ステップＳ１５１３：Ｙｅｓ）、走行継続判断をおこない（ステップＳ１５１４）、走行継続であれば（ステップＳ１５１４：Ｙｅｓ）、ステップＳ１５０１に戻り、処理を継続させる。一方、走行終了と判断された場合には（ステップＳ１５１４：Ｎｏ）、そのまま一連の処理を終了する。
【０１０６】
（各種システムへの適応例）
つぎに、上述した描画処理装置２００の各種システムへの具体的な適応例について説明する。ここでは、描画処理装置２００をカーナビゲーションシステムに適応した例と、携帯端末ナビゲーションシステムに適応した例について説明する。
【０１０７】
図１６は、カーナビゲーションシステムへの適応例を示すブロック図である。図１６では、カーナビゲーションシステムに描画処理装置２００の機能を適用させることによってカーナビゲーション装置１６００を実現している。
【０１０８】
カーナビゲーション装置１６００は、一般的な例として、ＣＰＵ１６０１と、グラフィックスＬＳＩ１６０２と、メインメモリ１６０３と、グラフィックスメモリ１６０４と、ディスプレイ１６０５と、ＩＯ（Ｉｎｐｕｔ Ｏｕｔｐｕｔ）コントローラ１６０６と、ＨＤＤユニット１６０７と、光学ディスクドライブユニット１６０８と、ジャイロセンサー１６０９と、ＧＰＳユニット１６１０とを備えた構成になっている。
【０１０９】
カーナビゲーション装置１６００では、ＩＯコントローラ１６０６を介してＣＰＵ１６０１がＨＤＤユニット１６０７のＨＤＤに格納されている地図データ１００を読み込む。読み込まれた地図データ１００は、動作や、読み込んだ地図データ１００に必要な変換を施してメインメモリ１６０３に保存する。このときの保存されるデータは、本実施の形態にて説明した仮想サブパーセルの識別コードを埋め込んだデータである。この結果、ＣＰＵ１６０１からグラフィックスＬＳＩ１６０２に描画コマンドを送る段階で、無駄なコマンドの生成が抑制され、システムの性能が向上する。
【０１１０】
図１７は、携帯端末ナビゲーションシステムへの適応例を示す説明図である。図１７のシステム１７００において、携帯電話端末１７４０のユーザからのリクエストを基地局１７３０および通信キャリア１７２０を介して受け取ったアプリケーションプロバイダ１７１０のアプリケーションサーバが、地図情報提供サービスを実行する際に、本実施の形態にて説明した、本発明が有効に機能する。
【０１１１】
具体的に説明すると、携帯電話端末１７４０の画面上で表示しようとしている視野領域の、地図空間上における位置とサイズの情報が、携帯電話端末からのリクエストパケットとして、通信キャリア１７２０を介してアプリケーションプロバイダ１７１０のアプリケーションサーバに送られる。このリクエストパケットを受けてアプリケーションプロバイダ１７１０のアプリケーションサーバは、携帯電話端末１７４０の視野領域に関与する地図データだけを仮想サブパーセルの識別コードをもとに抽出し、地図描画データに変換する。
【０１１２】
この結果、アプリケーションプロバイダ１７１０は、通信キャリア１７２０を介して、携帯電話端末１７４０の視野領域に関与する部分だけの地図描画データを送信する。このデータを用いることによって、無駄なパケットの通信が抑制され、応答性が向上する。また、図示しないが、携帯電話サービス以外の、一般的な有線のインターネットサービスとしての地図アプリケーションにも適用可能である。
【０１１３】
（ハードウェアの他の構成例）
つぎに、本実施の形態にかかる描画処理の機能を実現するためのハードウェアの他の構成例について説明する。図１８は、描画処理装置のハードウェア構成の他の例を示すブロック図である。図１８のグラフィックスＬＳＩ１８００は、サブパーセル識別コードが図形データへの参照テーブルに埋め込まれた場合の構成例を示している。
【０１１４】
従来は、視野部分のパーセルの検索はＣＰＵにておこなわれる。手順を簡単に説明すると、頂点座標は頂点シェーダーに入力されて座標変換や照光処理がおこなわれる。続いて三角形セットアップ処理を受けて、入力頂点は画面座標における三角形の頂点として解釈される。そして、ラスタライザにて走査線ごとの画素座標に変換される。その後、フラグメントシェーダーによって画素に効果色などが施され、最後に、ピクセル処理にて最終的な可視性判定や半透明処理などがおこなわれた後、フレームバッファに描画される。
【０１１５】
それに対して図１８のグラフィックスＬＳＩ１８００では、可視パーセルの検索と可視サブパーセルの検索をグラフィックスＬＳＩ１８００上のハードウェアとして実装している。可視サブパーセル検索モジュールからは、検索結果として可視と判定されたサブパーセルの識別コードが、頂点データ読込み制御モジュールに対して発行される。
【０１１６】
頂点データ読込み制御モジュールでは、可視サブパーセル検索モジュールから受け取った可視サブパーセルの識別コード（複数）と、グラフィックスＬＳＩ１８００の外部から入力されたサブパーセル識別コードとを照合する。そして、照合結果が一致した場合、もしくは大図形用例外コードが入力された場合のみ、対応する図形の頂点座標を読み込むように処理することができる。
【０１１７】
以上説明したように、本実施の形態によれば、元の地図データ構成を大幅に改変することなく、同じパーセルに含まれた図形データでありながら画面表示への地図表示に寄与しない部分の地図データの描画を抑止できる。この結果、地図データの改変に大きな制約が課せられているような条件下においても、地図描画速度の向上を図ることができる。したがって、地図データの構成を変えることなく高速な描画処理を実現することができる。
【０１１８】
なお、本実施の形態で説明した地図描画方法は、あらかじめ用意されたプログラムをパーソナル・コンピュータやワークステーションなどのコンピュータで実行することにより実現することができる。このプログラムは、ハードディスク、フレキシブルディスク、ＣＤ−ＲＯＭ、ＭＯ、ＤＶＤなどのコンピュータで読み取り可能な記録媒体に記録され、コンピュータによって記録媒体から読み出されることによって実行される。またこのプログラムは、インターネットなどのネットワークを介して配布することが可能な媒体であってもよい。
【０１１９】
また、本実施の形態で説明した秒が処理装置２００は、スタンダードセルやストラクチャードＡＳＩＣ（Ａｐｐｌｉｃａｔｉｏｎ Ｓｐｅｃｉｆｉｃ Ｉｎｔｅｇｒａｔｅｄ Ｃｉｒｃｕｉｔ）などの特定用途向けＩＣ（以下、単に「ＡＳＩＣ」と称す。）やＦＰＧＡなどのＰＬＤ（Ｐｒｏｇｒａｍｍａｂｌｅ Ｌｏｇｉｃ Ｄｅｖｉｃｅ）によっても実現することができる。具体的には、たとえば、上述した描画処理装置２００の機能３０１〜３０６をＨＤＬ記述によって機能定義し、そのＨＤＬ記述を論理合成してＡＳＩＣやＰＬＤに与えることにより、描画処理装置２００を製造することができる。
【０１２０】
さらに、より現実的な実現方法として、本実施の形態で説明した一連の処理を、非リアルタイムに実行される前処理と、リアルタイムに実行される後処理に二分割することができる。具体的には、必ずしもリアルタイムに実行する必要が無い機能３０１〜３０３を、パーソナル・コンピュータやワークステーションなどのコンピュータで実行して、仮想サブパーセルの識別コードを伴った地図描画データベースをあらかじめ作成しておく。機能３０４〜３０６は、ナビゲーションシステムの稼動中にリアルタイムに実行される必要があるので、ＬＳＩとしてハードウェア化するか、ＣＰＵでリアルタイム実行するのが望ましい。
【０１２１】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１２２】
（付記１）画像を分割する第１領域内に存在する図形の情報を含んだ図形データを用いて前記画像を描画する描画処理装置であって、
前記図形データに対応する前記第１領域を前記第１領域より小さな第２領域に分割する分割手段と、
前記分割手段によって分割された前記第２領域から前記第１領域の図形の少なくとも一部が存在する第２領域を特定する特定手段と、
前記特定手段によって特定された第２領域と、前記図形とを関連付ける関連付け手段と、
を備えることを特徴とする描画処理装置。
【０１２３】
（付記２）前記第１領域単位に、前記図形の参照テーブルが含まれている場合、前記関連付け手段は、前記第２領域と、前記参照テーブルとを関連付けることを特徴とする付記１に記載の描画処理装置。
【０１２４】
（付記３）前記特定手段は、前記図形が前記特定された第２領域に収まらない場合、前記図形を包含する複数の第２領域を特定し、
前記関連付け手段は、前記特定手段によって特定された前記複数の第２領域と、前記図形とを関連付けることを特徴とする付記１に記載の描画処理装置。
【０１２５】
（付記４）前記特定手段は、前記図形が前記特定された第２領域に収まらない場合、前記図形の少なくとも一部が存在する複数の第２領域を特定し、
前記関連付け手段は、前記特定手段によって特定された前記複数の第２領域と、前記参照テーブルとを関連付けることを特徴とする付記２に記載の描画処理装置。
【０１２６】
（付記５）前記画像の表示領域の指示を受け付けると、前記図形データの中から、前記表示領域に含まれる前記第１領域を抽出する第１領域抽出手段と、
前記第１領域抽出手段によって抽出された前記第１領域および前記表示領域に含まれる前記第２領域を抽出する第２領域抽出手段と、
前記第１領域抽出手段によって抽出された前記第１領域の少なくとも一部に存在する前記図形の中から、前記第２領域抽出手段によって抽出された前記第２領域と関連付けされた図形を描画する描画手段と、
を備えることを特徴とする付記１〜４のいずれか一つに記載の描画処理装置。
【０１２７】
（付記６）画像を分割する第１領域内に存在する図形の情報を含んだ図形データを用いてコンピュータに前記画像を描画させる描画処理プログラムであって、
前記コンピュータを、
前記図形データに対応する前記第1領域を前記第１領域より小さな第２領域に分割する分割手段、
前記分割手段によって分割された前記第２領域の中から前記前記第１領域内の図形の少なくとも一部が存在する前記第２領域を特定する特定手段、
前記特定手段によって特定された第２領域と、前記図形とを関連付ける関連付け手段、
として機能させることを特徴とする描画処理プログラム。
【０１２８】
（付記７）前記画像の表示領域の指示を受け付けると、
前記コンピュータをさらに、
前記図形データの中から、前記表示領域に含まれる前記第１領域を抽出する第１領域抽出手段、
前記第１領域抽出手段によって抽出された前記第１領域および前記表示領域に含まれる前記第２領域を抽出する第２領域抽出手段、
前記第１領域抽出手段によって抽出された前記第１領域の少なくとも一部に存在する図形の中から、前記第２領域抽出手段によって抽出された前記第２領域と関連付けされた図形を描画する描画手段、
として機能させることを特徴とする付記６に記載の描画処理プログラム。
【０１２９】
（付記８）画像を分割する第１領域内に存在する図形の情報を含んだ図形データを用いて地図画像を描画する描画処理方法であって、
前記図形データに対応する前記第１領域を前記第１領域より小さな第２領域に分割する分割工程と、
前記分割工程によって分割された前記第２領域の中から前記第１領域内の前記図形の少なくとも一部が存在する第２領域を特定する特定工程と、
前記特定工程によって特定された第２領域と、前記図形とを関連付ける関連付け工程と、
を含むことを特徴とする描画処理方法。
【０１３０】
（付記９）前記画像の表示領域の指示を受け付けると、前記図形データの中から、前記表示領域に含まれる前記第１領域を抽出する第１領域抽出工程と、
前記第１領域抽出工程によって抽出された前記第１領域および前記表示領域に含まれる前記第２領域を抽出する第２領域抽出工程と、
前記第１領域抽出工程によって抽出された前記第１領域の少なくとも一部に存在する前記図形の中から、前記第２領域抽出工程によって抽出された前記第２領域と関連付けされた図形を描画する描画工程と、
をさらに含むことを特徴とする付記８に記載の描画処理方法。
【図面の簡単な説明】
【０１３１】
【図１】本実施の形態にかかる地図描画処理の概要を示す説明図である。
【図２】本実施の形態にかかる描画処理装置のハードウェア構成を示す説明図である。
【図３】描画処理装置の機能的構成を示すブロック図である。
【図４】地図データのパーセル構造と表示画面との関係を示す説明図である。
【図５】パーセル構造の地図データに含まれる図形データのデータフォーマットの一例を示す図表である。
【図６】図形データの参照テーブルのデータフォーマットの一例を示す図表である。
【図７】仮想サブパーセル構造と表示画面との関係を示す説明図である。
【図８】第１の手法による図形データ生成におけるパーセル上の仮想サブパーセルを示す説明図である。
【図９】仮想サブパーセルの識別コードを含んだ図形データのデータフォーマットの一例を示す図表である。
【図１０】第１の手法による図形データの生成手順を示すフローチャートである。
【図１１】第２の手法による図形データの生成におけるパーセル上の仮想サブパーセルを示す説明図である。
【図１２】第２の手法による図形データの生成手順を示すフローチャートである。
【図１３】仮想サブパーセルの識別コードを含んだ図形データの参照テーブルのデータフォーマットの一例を示す図表である。
【図１４】第１の手法による地図描画の手順を示すフローチャートである。
【図１５】第２の手法による地図描画の手順を示すフローチャートである。
【図１６】カーナビゲーションシステムへの適応例を示すブロック図である。
【図１７】携帯端末ナビゲーションシステムへの適応例を示す説明図である。
【図１８】描画処理装置のハードウェア構成の他の例を示すブロック図である。
【符号の説明】
【０１３２】
１００ 地図データ
１１０ パーセル構造
１１１ 表示領域
１２０ 仮想サブパーセル構造
２００ 描画処理装置
３０１ 分割部
３０２ 特定部
３０３ 関連付け部
３０４ 区画抽出部
３０５ 矩形抽出部
３０６ 描画部
３１０ 表示機器
１６００ カーナビゲーション装置
１６０１ ＣＰＵ
１６０２ グラフィックスＬＳＩ
１６０３ メインメモリ
１６０４ グラフィックスメモリ
１６０５ ディスプレイ
１６０６ ＩＯコントローラ
１６０７ ＨＤＤユニット
１６０８ 光学ディスクドライブユニット
１６０９ ジャイロセンサー
１６１０ ＧＰＳユニット
１７１０ アプリケーションプロバイダ
１７２０ 通信キャリア
１７３０ 基地局
１７４０ 携帯電話端末
【特許請求の範囲】
【請求項１】
画像を分割する第１領域内に存在する図形の情報を含んだ図形データを用いて前記画像を描画する描画処理装置であって、
前記図形データに対応する前記第１領域を前記第１領域より小さな第２領域に分割する分割手段と、
前記分割手段によって分割された前記第２領域から前記第１領域の図形の少なくとも一部が存在する第２領域を特定する特定手段と、
前記特定手段によって特定された第２領域と、前記図形とを関連付ける関連付け手段と、
を備えることを特徴とする描画処理装置。
【請求項２】
前記第１領域単位に、前記図形の参照テーブルが含まれている場合、前記関連付け手段は、前記第２領域と、前記参照テーブルとを関連付けることを特徴とする請求項１に記載の描画処理装置。
【請求項３】
前記画像の表示領域の指示を受け付けると、前記図形データの中から、前記表示領域に含まれる前記第１領域を抽出する第１領域抽出手段と、
前記第１領域抽出手段によって抽出された前記第１領域および前記表示領域に含まれる前記第２領域を抽出する第２領域抽出手段と、
前記第１領域抽出手段によって抽出された前記第１領域の少なくとも一部に存在する前記図形の中から、前記第２領域抽出手段によって抽出された前記第２領域と関連付けされた図形を描画する描画手段と、
を備えることを特徴とする請求項１または２に記載の描画処理装置。
【請求項４】
画像を分割する第１領域内に存在する図形の情報を含んだ図形データを用いてコンピュータに前記画像を描画させる描画処理プログラムであって、
前記コンピュータを、
前記図形データに対応する前記第1領域を前記第１領域より小さな第２領域に分割する分割手段、
前記分割手段によって分割された前記第２領域の中から前記前記第１領域内の図形の少なくとも一部が存在する前記第２領域を特定する特定手段、
前記特定手段によって特定された第２領域と、前記図形とを関連付ける関連付け手段、
として機能させることを特徴とする描画処理プログラム。
【請求項５】
画像を分割する第１領域内に存在する図形の情報を含んだ図形データを用いて地図画像を描画する描画処理方法であって、
前記図形データに対応する前記第１領域を前記第１領域より小さな第２領域に分割する分割工程と、
前記分割工程によって分割された前記第２領域の中から前記第１領域内の前記図形の少なくとも一部が存在する第２領域を特定する特定工程と、
前記特定工程によって特定された第２領域と、前記図形とを関連付ける関連付け工程と、
を含むことを特徴とする描画処理方法。
【請求項１】
画像を分割する第１領域内に存在する図形の情報を含んだ図形データを用いて前記画像を描画する描画処理装置であって、
前記図形データに対応する前記第１領域を前記第１領域より小さな第２領域に分割する分割手段と、
前記分割手段によって分割された前記第２領域から前記第１領域の図形の少なくとも一部が存在する第２領域を特定する特定手段と、
前記特定手段によって特定された第２領域と、前記図形とを関連付ける関連付け手段と、
を備えることを特徴とする描画処理装置。
【請求項２】
前記第１領域単位に、前記図形の参照テーブルが含まれている場合、前記関連付け手段は、前記第２領域と、前記参照テーブルとを関連付けることを特徴とする請求項１に記載の描画処理装置。
【請求項３】
前記画像の表示領域の指示を受け付けると、前記図形データの中から、前記表示領域に含まれる前記第１領域を抽出する第１領域抽出手段と、
前記第１領域抽出手段によって抽出された前記第１領域および前記表示領域に含まれる前記第２領域を抽出する第２領域抽出手段と、
前記第１領域抽出手段によって抽出された前記第１領域の少なくとも一部に存在する前記図形の中から、前記第２領域抽出手段によって抽出された前記第２領域と関連付けされた図形を描画する描画手段と、
を備えることを特徴とする請求項１または２に記載の描画処理装置。
【請求項４】
画像を分割する第１領域内に存在する図形の情報を含んだ図形データを用いてコンピュータに前記画像を描画させる描画処理プログラムであって、
前記コンピュータを、
前記図形データに対応する前記第1領域を前記第１領域より小さな第２領域に分割する分割手段、
前記分割手段によって分割された前記第２領域の中から前記前記第１領域内の図形の少なくとも一部が存在する前記第２領域を特定する特定手段、
前記特定手段によって特定された第２領域と、前記図形とを関連付ける関連付け手段、
として機能させることを特徴とする描画処理プログラム。
【請求項５】
画像を分割する第１領域内に存在する図形の情報を含んだ図形データを用いて地図画像を描画する描画処理方法であって、
前記図形データに対応する前記第１領域を前記第１領域より小さな第２領域に分割する分割工程と、
前記分割工程によって分割された前記第２領域の中から前記第１領域内の前記図形の少なくとも一部が存在する第２領域を特定する特定工程と、
前記特定工程によって特定された第２領域と、前記図形とを関連付ける関連付け工程と、
を含むことを特徴とする描画処理方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図１８】
【公開番号】特開２００９−２１７０００（Ｐ２００９−２１７０００Ａ）
【公開日】平成２１年９月２４日（２００９．９．２４）
【国際特許分類】
【出願番号】特願２００８−６０９８５（Ｐ２００８−６０９８５）
【出願日】平成２０年３月１１日（２００８．３．１１）
【出願人】（３０８０１４３４１）富士通マイクロエレクトロニクス株式会社 (2,507)
【Ｆターム（参考）】
【公開日】平成２１年９月２４日（２００９．９．２４）
【国際特許分類】
【出願日】平成２０年３月１１日（２００８．３．１１）
【出願人】（３０８０１４３４１）富士通マイクロエレクトロニクス株式会社 (2,507)
【Ｆターム（参考）】
[ Back to top ]