JP5883817B2 - 描画データ生成装置および描画装置 - Google Patents

Description

本発明は、グラフィックスライブラリを用いて画像を描画する描画装置、および描画のためのデータを生成する描画データ生成装置に関する。

ナビゲーション装置やコンピュータの画面等に用いられる電子地図などは、ポリゴンデータ等の形式で用意された地図データを参照して、ディスプレイ等に地図を描画する。この描画には、グラフィックスライブラリと呼ばれる描画用の関数が用いられるのが通常である。３次元での描画を行うためのグラフィックスライブラリとしては、ＯｐｅｎＧＬやＤｉｒｅｃｔＸなどが存在する。これらのグラフィックスライブラリを用いることにより、画像の描画を高速で効率的に実行することが可能となる。
一方、グラフィックスライブラリには、それぞれ利用する際の制約があり、必ずしも描画対象となるポリゴンデータが、こうした制約を満足しているとは限らない。かかる場合には、ポリゴンデータを、グラフィックスライブラリの制約に適合するように加工する必要が生じる。特許文献１は、かかる加工の一例として、グラフィックスライブラリが取り扱い可能な頂点数に上限値がある場合、ポリゴンを描画する際に、上限値に基づいてポリゴンを分割して描画する技術を開示している。
また、描画すべきポリゴンデータが、地図データのように多数のポリゴンからなる大容量のデータの場合には、描画速度を速めるため、データ量を削減する処理も行われる。特許文献２は、かかる処理の一例として、ポリゴンを描画する際に、辺間の角度が大きい場合には、頂点数を間引くことによって、ポリゴンの描画速度を速める技術を開示している。

特開２００３−１８７２５６号公報 特開２００４−３４８７０８号公報

電子地図等においても地物の形状を３次元的に表現した３次元地図が普及し、３次元での描画が要求されるようになると、描画すべきポリゴンデータの容量はますます大きくなる。また、カーナビゲーション装置に３次元地図を適用した場合には、リアルタイムに３次元地図を描画する必要があり、描画に要する時間の短縮化も要求される。このようなデータ容量の増大、描画時間の短縮という要請に十分、応えるためには、描画速度をさらに向上させることが望まれていた。
描画速度の向上は、電子地図に限った課題ではなく、画像の描画に共通の課題である。本発明は、グラフィックスライブラリを用いる場合に、画像の描画速度の向上を図ることを目的とする。

本発明は、
グラフィックスライブラリを用いて画像を描画するための描画データを生成する描画データ生成装置であって、
前記グラフィックスライブラリは、ラインデータによって指定された頂点間を順次結んでラインを描画するライン関数を有しており、
前記描画データ生成装置は、
前記描画すべき原データを格納する原データベースと、
前記原データのうち、複数の前記ラインデータを一本のラインデータに統合するラインデータ統合部とを有しており、
前記ラインデータ統合部は、
前記原データに含まれるラインデータのうち、前記ライン関数を共通の設定で用いて描画されるべき複数のラインデータを抽出し、
前記抽出された複数のラインデータを連結して一本のラインデータに統合するように、前記ラインデータの端点のうち空間的に離れている端点間を、非表示のラインで連結するデータを生成する描画データ生成装置として構成することができる。

グラフィックスライブラリを用いて描画を行う場合、ラインを１本ひくごとに、ライン関数を呼び出すことになるが、この呼び出しに少なからず処理時間を要することになる。従って、描画すべきラインデータの本数が増えるほど、ライン関数を呼び出す回数が増大し、全体の処理時間が長くなることになる。
これに対し、本発明によれば、複数のラインデータを非表示のラインで連結することで一本のラインデータに統合することができる。従って、統合化されたラインデータを描画するためには、ライン関数を１回読み出せば足りるため、描画に要する所要時間を短縮することができる。もっとも、ラインを統合する分、1回のライン関数で描画すべきラインデータを構成する頂点数は統合前よりも増大するため、処理時間を増大させる要素とはなり得る。しかし、かかる増大要素よりも、ライン関数の呼び出し回数を減らすことによる所要時間の短縮効果の方が大きいため、全体として処理時間を短縮することが可能となるのである。
グラフィックスライブラリを用いて描画を行う場合、頂点間の区間ごとにラインの表示／非表示は容易に切り換えることができる。従って、ラインデータの間を非表示のラインで連結するのは、ラインデータ間に新たなラインを定義するとともに、当該区間を非表示と設定することにより、容易に実現することができる。
統合の対象となるラインデータは、ライン関数を共通の設定で用いて描画できるものである。例えば、ラインの太さ・線種等が共通のラインなどが対象となり得る。どのようなラインが統合の対象となるかは、利用するグラフィックスライブラリに応じて定まることになる。

本発明において、
前記ライン関数が、ラインの一方の頂点に指定された第１の表示態様から、他方の頂点に指定された第２の表示態様に、表示態様を順次変化させながら該ラインを描画する機能を有している場合、
前記描画データ生成装置は、さらに、
前記統合の際に、前記非表示のラインで連結すべき端点に重ねて、新たに連結で用いるためのダミー点を追加するダミー点追加部を備え、
前記ラインデータ統合部は、前記ダミー点間を非表示のラインで連結するものとしてもよい。

グラフィックスライブラリのライン関数によっては、ブレンド機能、即ち、第１の頂点から第２の頂点にかけて、徐々に線の色などの表示態様を変化させる機能を備えているものがある。かかる機能を有するライン関数では、例えば、第１の頂点で「赤」、第２の頂点で「青」が指定されていると、その間のラインは、赤から徐々に青に変化しながら描画されることになる。
このようなライン関数の場合、原データに存在する第１のラインの端点（第１の端点と呼ぶ）と、第２のラインの端点（第２の端点と呼ぶ）とを非表示のラインで連結しようとすると、第１のライン、および第２のライン自体が、それぞれ第１の端点、第２の端点に向けて徐々に透明に描かれる自体も生じ得る。
これに対し、本発明によれば、第１の端点、第２の端点にダミー点をそれぞれ追加した上で、これらのダミー点の間を非表示のラインで連結するため、第１のライン、第２のラインは、非表示のラインの影響を受けることなく適正に描画される。

本発明においては、
前記ラインデータ統合部は、前記空間的に離れている端点のうち、距離が近い端点同士を連結するものとしてもよい。
こうすることにより、統合したラインの全体の距離を短くすることができ、ラインの描画時間をより短縮することが可能となる。

本発明においては、
前記原データベースは、前記各ラインデータに固有の原インデックス情報が、それぞれラインデータに関連づけて格納されており、
前記ラインデータ統合部は、前記原インデックス情報とは別に、前記統合されたラインデータの形状、属性を示す固有の統合インデックス情報を生成するものとしてもよい。
ラインを統合した後でも、原データのラインと、統合化のために追加された非表示のラインとは区別可能としておく必要がある。また、原データにおいて、ラインデータごとに、色、線種などの属性が設定されていることがあり、こうした情報は、参照可能な状態で保持しておく必要がある。
上記態様によれば、ラインに関連づけられた原インデックス情報は保持されているため、原データのラインに付されていた形状や属性も参照可能となる。また、これと同時に、統合化されたライン全体のインデックス情報も生成されるため、統合化された後のライン全体としての取り扱いも容易となる利点がある。

本発明は、上述した描画データ生成装置としての態様に限らず、種々の態様で構成することができ、例えば、次に示す描画装置として構成してもよい。
グラフィックスライブラリを用いて画像を描画する描画装置であって、
前記グラフィックスライブラリは、ラインデータによって指定された頂点間を順次結んでラインを描画するライン関数を有しており、
前記描画装置は、
所定サイズのメッシュに区切って生成された前記描画すべき原データを格納する原データベースと、
前記描画の対象となるメッシュが複数あるとき、異なるメッシュに存在する前記ラインデータの端点同士を仮想的に連結して一本のラインデータに統合するライン描画データ設定部と、
前記統合されたラインデータに基づいて前記ライン関数を呼び出すことによって描画を行う描画部とを備える描画装置とする態様である。
上記描画装置によれば、メッシュ間でラインを連結して描画することにより、ライン関数の呼び出し回数を減少させることができ、描画の所要時間短縮を図ることができる。

本発明の描画装置においては、
さらに、前記メッシュごとに、該メッシュ内の複数のラインデータを統合するために、先に説明したいずれかの描画データ生成装置を備え、
前記ライン描画データ設定部は、前記メッシュごとに統合されたラインデータを対象として前記統合を行うものとしてもよい。
こうすることにより、メッシュ内のラインも統合化し、かつ、メッシュ間でも統合化することができるから、より一層、ライン関数の呼び出し回数を減少させることができる。

本発明は、上述した特徴を必ずしも全てを備えている必要はなく、適宜、その一部を省略したり、組み合わせたりしてもよい。
本発明は、さらに、コンピュータによって描画データを生成する生成方法または画像を描画する描画方法として構成してもよい。また、描画データの生成や画像の描画をコンピュータに実行させるためのコンピュータプログラムとして構成してもよい。また、かかるコンピュータプログラムを記録したコンピュータが読み取り可能な記録媒体として構成してもよい。

経路案内システムの構成を示す説明図である。 原地図データベースのデータ構造を示す説明図である。 ラインデータの統合処理の概要を示す説明図である。 ラインデータ統合処理のフローチャートである。 経路案内処理のフローチャートである。

以下、本発明を、地図を描画しつつ、経路探索・経路案内を行う経路案内システムとして構成した場合の実施例を説明する。経路案内システムのうち、グラフィックスライブラリを用いて地図を描画する部分が、本発明における描画装置に相当する。また、そのためのデータを生成する部分が、本発明における描画データ生成装置に相当する。
本発明の描画対象は、地図に限られるものではないから、本発明は、経路案内システムとしての態様に限らず、グラフィックスライブラリを用いて画像を描画する種々の描画装置に適用可能である。

Ａ．システム構成：
図１は、経路案内システムの構成を示す説明図である。経路案内システムは、サーバ２００から提供されるデータに基づいて、端末３００において地図を表示しながら、ユーザが指定した出発地から目的地までの経路を案内するシステムである。サーバ２００と端末３００とはインターネットなどのネットワークＮＥ２で接続されている。本実施例では、端末３００としては、ＣＰＵ、ＲＡＭ、ＲＯＭを備えるスマートフォンを利用したが、携帯電話、パーソナルコンピュータ、タブレット端末など、電子地図を表示可能な種々の装置を利用することができる。
図１には、さらに、地図を効率的に描画するための描画データを生成する描画データ生成装置１００も併せて示した。描画データ生成装置１００は、ＣＰＵ、ＲＡＭ、ＲＯＭを備えるパーソナルコンピュータを利用して構成されており、原地図データベース１０４から、描画用地図データベースを生成する装置である。描画データ生成装置１００は、ネットワークＮＥ１でサーバ２００に接続されており、生成された描画用地図データベースは、サーバ２００に格納される。
描画データ生成装置１００、サーバ２００、端末３００には、それぞれ図示する機能ブロックが備えられている。本実施例では、これらの機能ブロックは、それぞれの機能を実現するためのコンピュータプログラムをインストールすることによってソフトウェア的に構成したが、これらをハードウェア的に構成することも可能である。
また、本実施例で示した描画データ生成装置１００、サーバ２００、端末３００が備える機能は、一例に過ぎず、全ての機能を１台で実現するスタンドアロンの装置として構成することも可能である。また、図示したよりも多数のサーバ等からなる分散システムとして構成してもよい。
以下、各装置ごとに構成を説明する。

描画データ生成装置１００の構成について説明する。
原地図データベース１０４は、地図で描画されるべき地物の形状等を表すポリゴンデータ、ラインデータを格納したデータベースである。本実施例では、３次元の形状を表す３次元地図データを格納するものとした。原地図データベース１０４を、そのまま用いて透視投影等によって３次元地図を描画することも可能なデータである。本実施例では、描画速度を向上させるため、描画データ生成装置１００で、加工し、描画用地図データベース１０３を生成するのである。
コマンド入力部１０１は、原地図データベース１０４に対する加工について、オペレータからの指示等を入力する。
ラインデータ統合部１０２は、上述した加工として、原地図データベース１０４に含まれる複数のラインを表すラインデータを連結し、１本のラインデータにする処理を行う。以下では、この処理を、統合化と呼ぶこともある。
ダミー点追加部１０６は、加工の対象となるラインデータの端点に重ねて、連結用にダミーの点を生成する。ダミーの点を生成する理由については、統合化の処理概要とともに後述する。
描画用地図データベース１０３は、ラインデータ統合部１０２によって加工され、描画の処理速度向上を図った描画用の地図データを格納する。
送受信部１０５は、サーバ２００との間でデータの送受信を行う。本実施例では、描画用地図データベース１０３に格納された地図データは、送受信部１０５により、ネットワークＮＥ１経由でサーバ２００に送信される。

サーバ２００の構成について説明する。
地図データベース２１０には、描画用地図データベース２１１およびネットワークデータ２１３が格納されている。描画用地図データベース２１０は、描画データ生成装置１００で生成された地図データであり、地物の形状を表すポリゴンデータ、ラインデータおよび文字データが格納されている。ネットワークデータ２１３は、道路をリンクおよびノードで表した経路探索用のデータである。
データベース管理部２０２は、地図データベース２１０のデータの入出力を管理する。本実施例では、描画データ生成装置１００で生成された描画用地図データベース２１１のアップデートを行ったり、地図表示時に必要な地図データを地図データベース２１０から読み出したりする。
経路探索部２０３は、ネットワークデータ２１３を利用して、端末３００のユーザから指定された出発地から目的地までの経路を探索する。経路探索は、ダイクストラ法など周知の方法によって行うことができる。
送受信部２０１は、ネットワークＮＥ１、ＮＥ２を介して、描画データ生成装置１００および端末３００との間で、種々のデータやコマンドの送受信を行う。

端末３００の構成について説明する。
主制御部３０４は、端末３００に備えられた各機能ブロックの動作を統合制御する。
送受信部３０１は、ネットワークＮＥ２を介してサーバ２００との間で、データやコマンドの送受信を行う。
コマンド入力部３０２は、ユーザからの経路案内等に関する指示などを入力する。指示としては、例えば、経路案内の出発地、目的地の指定、地図表示時の表示スケールの指定などが挙げられる。
位置・通行情報取得部３０３は、ＧＰＳ（Global Positioning System）等のセンサから端末３００の現在位置を取得したり、ネットワークＮＥ２経由で、交通渋滞や通行規制の情報を取得する。
地図情報記憶部３０５は、地図を表示する際に、サーバ２００から取得した描画用地図データベース２１１を一時的に記憶する。本実施例では、端末３００は、予め全ての地図データを記憶しておくのではなく、地図の表示範囲に応じて必要となる地図データを適宜、サーバ２００から取得する。地図情報記憶部３０５は、こうして取得された地図データを記憶している。また、併せて、経路探索の結果も記憶する。
表示制御部３０６は、地図情報記憶部３０５に記憶されている地図データを用いて、端末３００のディスプレイ３００ｄへの地図表示を行う。表示制御部３０６には、ポリゴンやラインを描画するためのグラフィックスライブラリが備えられており、描画は、適宜、グラフィックスライブラリの関数を呼び出すことで実行される。グラフィックスライブラリとしては、例えば、ＯｐｅｎＧＬやＤｉｒｅｃｔＸを用いることができる。
ライン描画データ設定部３０７は、表示制御部３０６による描画速度を向上させるため、地図データの加工を行う。先に説明した通り、本実施例では、地図データには、描画データ生成装置１００によって、描画速度を向上させるための加工が予め施されている。ただし、地図の表示範囲が定まっていない状態では、加工できる範囲にも制限がある。そこで、ライン描画データ設定部３０７は、地図を表示する時点で改めて実現可能な加工を施すのである。

Ｂ．データ構造：
図２は、原地図データベースのデータ構造を示す説明図である。原地図データベースは、複数のレベル、即ち詳細度に分けて格納されている。図の上側にレベルの概要を示した。レベルｎは、詳細度の高いデータであり、所定サイズの矩形形状からなるメッシュ単位でデータが格納されている。レベルｎ−１は、レベルｎよりも粗いデータであり、主要な道路、建物等のデータを格納する。レベルｎ−１もメッシュ単位でデータが格納されるが、メッシュのサイズは、レベルｎよりも広い。レベルｎ−２は、さらに粗く、広いメッシュ単位で格納された地図データである。
レベルｎのデータを例にとって、地図データの構成を説明する。

ラインデータは、地図中の道路、線路など線状の地物を描画するためのデータである。ラインデータは、地物単位で生成されており、固有のインデックス情報である「ＩＤ」が付されている。ラインデータの形状は、点１（ＸＬ１，ＹＬ１，ＺＬ１）、点２（ＸＬ２，ＹＬ２，ＺＬ２）のようにラインを形成する頂点の位置座標の集合で表される。これらの点の座標値は、各ラインデータ用の領域に格納されるようにしてもよいし、ラインデータとは個別の領域に格納し、ラインデータ用の領域には、その格納先を特定するポインタを記憶しておくようにしてもよい。
「属性」としては、ラインデータが表す地物の「名称」、道路種別など地物の「種別」、ラインを描画する際の「線種」、「線色」、「線幅」、および表示／非表示の指定などが設定されている。
文字データは、地図中に表示される文字を表すデータである。文字データにも、固有のインデックス情報である「ＩＤ」が付されて管理されている。「文字列」は“○○市”のように地図中に記載される文字を表し、「位置」は文字を表示すべき位置の座標値（ＸＣ，ＹＣ，ＺＣ）を表している。また、文字を表示する際のフォント、サイズ、色なども併せて指定されている。
ポリゴンデータは、建物その他の地物の形状を表すデータである。ポリゴンデータも、地物単位で生成されており、固有のインデックス情報である「ＩＤ」によって管理されている。ポリゴン形状は、頂点１（ＸＰ１，ＹＰ１，ＺＰ１）、点２（ＸＰ２，ＹＰ２，ＺＰ２）のように、ポリゴンを規定する頂点の座標の集合で表される。「属性」としては、ポリゴンが表す地物の「名称」、建物や池などの「種別」等が指定されている。
図２では、原地図データベースのデータ構造を例示したが、描画用地図データベースの構造も同様である。本実施例における描画用地図データベースは、データ構造自体を大きく変更するものではなく、ラインデータに対して、付加的な情報を付すことによって、描画処理速度の向上を図るものである。

Ｃ．描画用データの生成：
図３は、ラインデータの統合処理の概要を示す説明図である。図３（ａ）に、統合化前のラインデータの様子を示した。図の例では、地図中には、街中の細い道路のように細線で描かれるラインＬ１、Ｌ３と、国道などの主要な道路のように太線で描かれるラインＬ２、Ｌ４、Ｌ５がある。図の右側には、これらのラインに対応するラインデータの格納状況を示した。この例では、各ラインを構成する頂点は、ラインデータ（図２）におけるＩＤや属性とは別のメモリ領域にまとめて格納されているものとする。ラインデータには、頂点の座標列として、頂点が格納されたメモリ領域を特定するポインタが格納されることになる。
頂点記憶用のメモリ領域には、ラインＬ１については頂点Ｐ１１、Ｐ１２が記憶される。次に、ラインＬ２を構成する頂点Ｐ２１、Ｐ２２が記憶される。同様に、ラインＬ３、Ｌ４、Ｌ５を構成する頂点Ｐ３１〜Ｐ３３、Ｐ４１〜Ｐ４２、Ｐ５１〜Ｐ５２がそれぞれ記憶される。このように、ラインデータ内では、各ラインＬ１〜Ｌ５は個別のものとして扱われているため、頂点もラインごとに格納されている。

図３（ｂ）は、統合化の様子を示している。統合化とは、グラフィックスライブラリを共通の設定で用いることができるライン同士を連結する処理であり、この実施例では、線の太さが同じライン同士を連結する。以下の説明では、ラインを構成する頂点のうち、ラインの端に位置するものを「端点」と呼ぶ。
細線で描かれるラインＬ１、Ｌ３を統合化する場合、ラインＬ１の一方の端点Ｐ１２と、ラインＬ３の一方の端点Ｐ３１を非表示のラインＬＡ１で連結する。非表示のラインＬＡ１の線の太さは、ラインＬ１、Ｌ３と同じである。
非表示のラインＬＡ１は、ラインＬ１の端点Ｐ１１、Ｐ１２、およびラインＬ３の端点Ｐ３１，Ｐ３３のいずれの間を連結してもよいが、本実施例では、連結の距離が最も短くなるよう端点Ｐ１２と端点Ｐ３１という組み合わせを選択した。ラインＬＡ１は、端点Ｐ１２と端点Ｐ３１とを直接、連結するものとしてもよいが、本実施例では、端点Ｐ１２に重ねてダミー点ＰＡ１１、端点Ｐ３１に重ねてダミー点ＰＡ１２を生成し、ダミー点ＰＡ１１、ＰＡ１２を連結して非表示ラインＬＡ１を定義した。
ダミー点ＰＡ１１、ＰＡ１２を設ける理由は、次の通りである。

グラフィックスライブラリのライン関数では、ブレンド機能、即ち、第１の頂点から第２の頂点にかけて、徐々に線の色などの表示態様を変化させる機能が備えられている。従って、頂点Ｐ１２、頂点Ｐ３１を直接にラインＬＡ１で連結しつつ、この区間を非表示に設定すると、ブレンド機能によって、ラインＬ１は頂点Ｐ１１から頂点Ｐ１２に向けて徐々に透明度が高くなるよう描画される現象が請じる。同様に、ラインＬ３は頂点Ｐ３２ら頂点Ｐ３１に向けて徐々に透明度が高くなるよう描画される。
これに対し、ダミー点ＰＡ１１、ＰＡ１２を追加しておけば、ラインＬＡ１を非表示にする場合でも、頂点Ｐ１１、Ｐ１２の間、および頂点Ｐ３１、Ｐ３２の間は、その影響を受けることなく適正に描画される。厳密な意味では、頂点Ｐ１２からダミー点ＰＡ１１に向けてブレンドが行われることになるが、両者は同一の位置にある点なので、ブレンドの結果は、描画されたラインで視認することはできない。

同様に、太線で描かれるラインＬ２、Ｌ４、Ｌ５を統合化する場合、ラインＬ２の一方の端点Ｐ２２と、ラインＬ４の一方の端点Ｐ４１とを非表示のラインＬＡ２で連結し、さらに、ラインＬ４の端点Ｐ４２とラインＬ５の端点Ｐ５１とを非表示のラインＬＡ３で連結する。非表示のラインＬＡ２、ＬＡ３の線の太さは、ラインＬ２，Ｌ４、Ｌ５と同じである。ラインＬ２、Ｌ４、Ｌ５についても、いずれの端点同士を連結してもよい。また、非表示のラインＬＡ２、ＬＡ３は、それぞれ端点Ｐ２２、Ｐ４１、Ｐ４２、Ｐ５１に重ねてダミー点ＰＡ２１、ＰＡ２２、ＰＡ３１、ＰＡ３２を生成した上で、これらのダミー点同士を連結するようにした。

このように統合化処理を行うことにより、細線で描かれるラインＬ１、Ｌ３は、非表示のラインＬＡ１を介して１本のラインに統合化される。また、太線で描かれるラインＬ２、Ｌ４、Ｌ５は、非表示のラインＬＡ２、ＬＡ３を介して１本のラインに統合化される。
この結果、統合化の前は、ラインＬ１〜Ｌ５を描くために、ライン関数を５回、呼び出す必要があるのに対し、統合化の後は、細線を描くために１回、太線を描くために１回の合計２回、ライン関数を呼び出せば済むこととなり、ライン関数の呼び出し回数を減少させることができ、処理時間の短縮を図ることができる。
ライン関数においては、区間ごとにラインの表示／非表示を制御できるから、それぞれ非表示ラインＬＡ１、ＬＡ２、ＬＡ３を非表示として描画することにより、ラインＬ１〜Ｌ５を個別に描画する場合と同じ描画結果を得ることができるのである。

図３（ｃ）は、ラインの統合化処理をした後のデータの様子を示している。ラインデータは、統合化前は、図３（ａ）に示したように、ラインＬ１〜Ｌ５のそれぞれで、まとめて頂点を格納していた。この時点では、細線のラインＬ１、Ｌ３と、太線のラインＬ２、Ｌ４、Ｌ５は、分類されず、両者が混在する形でデータが格納されている。
統合化した後は、図３（ｃ）に示すように、細線のラインについては、これを１つのライン関数で描画するためには、ラインＬ１の頂点、非表示のラインＬＡ３の頂点、ラインＬ３の頂点というようにまとめて格納しておくことが好ましい。また、太線のラインについては、１つのライン関数で描画するため、ラインＬ２の頂点、非表示のラインＬＡ２の頂点、ラインＬ４の頂点、非表示のラインＬＡ３の頂点、ラインＬ５の頂点というようにまとめて格納しておくことが好ましい。
しかし、統合化処理において、このようにデータの格納先を変更していては、処理負荷が多大となる。そこで、本実施例では、図示する通り、頂点の格納先を示すポインタ等を利用するものとした。

図の左側には、各ラインＬ１〜Ｌ３の個別インデックスを示した。インデックスとは、図２で示したラインデータの一形式であり、頂点の位置座標を格納するのではなく、頂点を格納するメモリ領域を特定するポインタを格納した形式を言う。例えば、ラインＬ１については、その頂点Ｐ１１のメモリ領域を特定するポインタが格納されることになる。同様に、ラインＬ２については頂点Ｐ２１、ラインＬ３については頂点Ｐ３１のメモリ領域を表すポインタが格納される。
図の右側には、統合化した後のラインの線種別インデックスを示した。実施例では、細線で描画されるライン、太線で描画されるラインをそれぞれ統合化したため、２種類の線種別インデックスが生成されることになる。

線種別インデックスの構造は、個別インデックスと同様である。
まず、統合化されたラインに固有の「ＩＤ」が付される。
その後、統合化されたラインの形状がポインタによって指示される。細線の場合には、まず、端点となる頂点Ｐ１１のポインタが格納される。データ点数は、格納されたポインタから連続して読み出すべき頂点数を表す。例えば、細線を形成するラインＬ１、ＬＡ１、Ｌ３のデータが連続した領域に格納されている場合には、頂点Ｐ１１から、７つの頂点を読み出せばよいから、データ点数として７が格納されることになる。
一方、非表示のラインＬＡ１、ラインＬ３の頂点が、ラインＬ１の頂点Ｐ１１、Ｐ１２と連続した領域と異なる領域に格納されている場合には、それぞれ非表示のラインＬＡ１の頂点ＰＡ１１を表すポインタ、ラインＬ３の頂点Ｐ３１を表すポインタも格納されることになる。
太線の場合も同様に、「ＩＤ」に対し、太線の端点となる頂点Ｐ２１のポインタおよびデータ点数が格納される。太線を構成するラインＬ２、ＬＡ２、Ｌ４、Ｌ５の頂点が連続していない領域に格納されている場合には、それぞれの頂点を表すポインタも併せて格納されることになる。

このように個別インデックスと、線種別インデックスの双方を用意することには、次の利点がある。個別インデックスを参照することによって、それぞれの頂点およびラインを、統合化される前の分離された個別のライン等として把握することができる。また、線種別インデックスを参照することによって、各頂点およびラインを、統合化された一本のラインとして把握することができる。このように個別インデックスと線種別インデックスの双方を用意しておくことにより、頂点およびラインを、個別のラインおよび統合化されたラインという２通りの方法で活用することが可能となる。

図３で示した統合化を行うための処理内容について説明する。
図４は、ラインデータ統合処理のフローチャートである。描画データ生成装置１００のラインデータ統合部１０２、およびダミー点追加部１０６が実行する処理であり、ハードウェア的には、描画データ生成装置１００のＣＰＵが実行する処理である。
図４（ａ）にはフローチャートを示し，図４（ｂ）には処理の例を示した。ここでは、統合化前の原データに存在するラインを実線で表し、統合化する過程で生成される非表示のラインを破線で表している。

処理を開始すると、ＣＰＵは、処理対象メッシュからラインデータを読み込む（ステップＳ１０）。図２で説明した通り、実施例の原地図データベース１０４は、メッシュ単位で地図データを格納しているため、統合化処理もメッシュ単位で行うからである。処理対象メッシュは、オペレータが手動で指示してもよいし、予め設定したシーケンスに従うなどの方法で自動的に設定するものとしてもよい。

ＣＰＵは、読み込んだラインデータを、線種、線幅ごとにグループ化する（ステップＳ１１）。線種、線幅が同じライン同士が統合化の対象となるからである。グループ化の対象は、グラフィックスライブラリのライン関数における描画上の制約に応じて定まる。本実施例では、ライン関数は、線種および線幅の一方または双方が異なるラインは、一度に描くことができないという制約があるため、線種、線幅に基づいてグループ化を行うものとした。例えば、線種が同一であるラインならば線幅が異なっていても一度に描くことができるライン関数を用いる場合には、線種が同じラインをグループ化すればよい。

ＣＰＵは、生成されたグループのいずれかを処理対象として選択し、処理対象のグループからスタートポイントを選択する（ステップＳ１２）。スタートポイントとは、統合化後のラインの端点となる頂点である。スタートポイントは、処理対象のグループに含まれるラインの端点から任意に選択することができる。本実施例では、メッシュの境界上にある端点を優先的に選択するものとした。メッシュの境界にあるラインから順に連結することにより、統合化したライン全体の長さを抑えやすくなるからである。また、統合化したラインの端点がメッシュの境界にあることにより、後述するメッシュ間の統合化を行いやすくなるという利点もある。
図４（ｂ）の例では、メッシュ境界上の頂点Ｐ１がスタートポイントとして選択されている。

ＣＰＵは、選択したスタートポイントからラインデータをたどり、端点を特定する。そして、こうして特定されたラインデータの端点から最短距離にある端点を検索する（ステップＳ１３）。
図４（ｂ）の例では、スタートポイントＰ１からラインデータをたどり、端点Ｐ２が特定される。端点Ｐ２の近傍にある他の端点としては、端点Ｐ３，Ｐ５、Ｐ６が存在する。ＣＰＵは、端点Ｐ２と端点Ｐ３、Ｐ５、Ｐ６との距離をそれぞれ計算し、端点Ｐ２から最短の距離にある端点Ｐ３を選択する。この端点Ｐ３が非表示のラインで結合すべき端点となる。

こうして結合すべき端点が見いだされると、ＣＰＵは、結合すべき双方の端点にダミー点を追加し、これらを非表示ラインで結合する（ステップＳ１４）。
図４（ｂ）の例では、端点Ｐ２にダミー点ＰＡ１、端点Ｐ３にダミー点ＰＡ２を追加し、両者間を破線で示した非表示ラインで連結している。

ＣＰＵは、以上のステップＳ１３，Ｓ１４の処理を全ラインが結合されるまで（ステップＳ１５）、繰り返し実行する。
図４（ｂ）の例では、ＣＰＵは、端点Ｐ３からラインデータをたどり端点Ｐ５にたどり着くと、端点Ｐ５から最短距離にある端点Ｐ６を選択する（ステップＳ１３）。そして、端点Ｐ５にダミー点ＰＡ３、端点Ｐ６にダミー点Ｐ４を追加し、両者間を非表示のラインで結合する。
さらに、ＣＰＵは、端点Ｐ６からラインデータをたどり端点Ｐ７にたどり着くと、端点Ｐ７から最短距離にある端点Ｐ８を選択する（ステップＳ１３）。そして、端点Ｐ７にダミー点ＰＡ５、端点Ｐ８にダミー点ＰＡ６を追加し、両者間を非表示のラインで結合する。この結果、全ラインが１つに結合されたことになるから、ステップＳ１５までの処理が完了することになる。

ＣＰＵは、グループごとに、以上の処理を繰り返し実行し（ステップＳ１６）、得られた結果を、描画用地図データベース１０３に格納するとともに、インデックスを生成する（ステップＳ１７）。インデックスの内容は、図３で説明した通りである。
こうして、ラインデータについては、メッシュ内で、線種、線幅ごとに、一本のラインに統合化されており、ライン関数を線種、線幅ごとに１回読み出すだけで描画できる状態となっている。

Ｄ．経路案内処理：
次に、描画用地図データを活用して地図表示を行う例として、経路案内処理について示す。経路案内処理は、経路探索によって得られた経路を地図表示しながら案内する処理である。経路探索は、経路案内に先立ってサーバ２００においてなされている。
図５は、経路案内処理のフローチャートである。これは、主として端末３００の表示制御部３０６、ライン描画データ設定部３０７によって行われる処理であり、ハードウェア的には端末３００のＣＰＵによって行われる処理である。
処理を開始すると、端末３００は、経路探索結果、現在位置、渋滞情報、地図表示サイズを入力する（ステップＳ２０）。経路探索結果は、サーバ２００から取得することができる。現在位置は、ＧＰＳなどのセンサを利用して検出することができる。渋滞情報は、インターネット等を介して取得できる。地図表示サイズは、ユーザからの指定を受け付ける。
そして、端末３００は、地図表示に必要となる地図データを読み込む（ステップＳ２１）。本実施例では、端末３００は、まず地図情報記憶部３０５に格納されているデータを読み込む、そして地図を表示するために地図データが不足している場合には、不足分をサーバ２００から取得する。

次に、端末３００は、経路探索結果、現在位置、渋滞情報に基づき、ダミー点の追加および表示色の設定を行う（ステップＳ２２）。探索された経路や渋滞している道路を、通常の道路とは異なる色で表示するための処理である。
図中に処理の概要を示した。頂点Ｐ１、Ｐ２、Ｐ３を通る道路において、頂点Ｐ１、Ｐ２の間が、探索された経路または渋滞している道路に該当し、色を変更する必要があるものとする。
中段には、ダミー点を追加せずに色の設定を行った場合を例示した。ライン関数のブレンド機能により、頂点Ｐ１、Ｐ２に表示色を設定すると、頂点Ｐ２、Ｐ３の間でグラデーションがかかった表示となってしまうのである。例えば、本来、頂点Ｐ１、Ｐ２、Ｐ３を通る道路が赤で表示されるべき道路である場合において、探索された経路であることを表すために、頂点Ｐ１、Ｐ２間を青に設定したとする。この場合、頂点Ｐ１、Ｐ２間が青で表示されるのに伴い、頂点Ｐ２、Ｐ３間では、頂点Ｐ２から頂点Ｐ３に向けて青から徐々に赤になるように表示されてしまう。
下段には、ダミー点を追加した状態を例示した。原データの頂点Ｐ２と同じ位置にダミー点ＰＡを追加し、色の設定を行う。例えば、頂点Ｐ１、Ｐ２間は青で、頂点ＰＡ，Ｐ３間は赤で表示するように設定する。こうすることにより、頂点Ｐ１、Ｐ２間の表示色の影響を受けることなく、頂点ＰＡ、Ｐ３間を表示することができる。厳密に言えば、頂点Ｐ２、ＰＡ間でブレンドが行われることになるが、両者は同一の位置にある点であるため、このブレンドは視認されないのである。

こうして色の設定を終えると、端末３００は、メッシュ間でラインデータを結合する（ステップＳ２３）。
図中に処理の概要を示した。ラインデータ統合処理（図４）によって、各メッシュ内では、線種、線幅が同じラインは、一本に統合化されている。メッシュ１、２内の各ラインは、それぞれメッシュ内で統合化された結果を表している。統合化されたラインには、線種別インデックス１，２が用意され、ラインを構成する頂点は、ポインタによって特定されている。
地図を表示する際には、メッシュをまたがって地図データを利用する場合がある。本実施例では、このような場合に、さらに描画の高速化を図るため、メッシュ間で線種、線幅が共通のライン同士を結合するのである。この処理は、メッシュ内の統合化と同様の方法によって行うことができる。即ち、異なるメッシュに存在する統合化されたラインを線種、線幅に基づいてグループ化し、これらの端点のうち、最短距離にあるもの同士を非表示のラインで結合するのである。
連結する端点同士の位置座標が異なる場合には、ブレンド機能による影響を回避するため、各端点にダミー点を追加した上で結合する。端点同士の位置座標が同一の場合には、ブレンド機能による影響は視認できないから、ダミー点の追加を省略してもよい。

以上の前処理を終えると、端末３００はディスプレイ３００ｄに地図を表示する（ステップＳ２４）。地図の表示には、グラフィックスライブラリが用いられる。ラインデータを表示する際には、ライン関数を呼び出すことになる。本実施例によれば、メッシュ内のラインが統合化されているだけでなく、さらに、メッシュ間のラインを結合するため、より一層、ライン関数の呼び出し回数を減少させることができ、描画の高速化を図ることができる。

Ｅ．効果および変形例：
以上で説明した実施例によれば、地図を表示する際に、線種、線幅が共通のラインを統合化することによって、グラフィックスライブラリに備えられたライン関数の呼び出し回数を減らすことができ、表示処理に要する時間を短縮することができる。グラフィックスライブラリを用いて描画を行う場合、ライン関数の呼び出しに少なからず処理時間を要するため、呼び出し回数の減少による処理時間の短縮効果は大きいからである。
本実施例では、統合化の処理を静的処理／動的処理の２段階で行っている。静的処理とは、予めメッシュ単位で統合化処理を行って描画用地図データベースを生成する処理（図４）を意味する。こうすることにより、メッシュ単位の描画速度を速めることができる。動的処理とは、端末３００で地図表示時に行う、メッシュ間でのラインデータの結合処理である（図５）。こうすることにより、複数のメッシュにまたがって地図を表示する場合、さらなる描画速度の高速化を図ることができる。

以上、本発明の実施例について説明した。本発明は、必ずしも上述した実施例の全ての機能を備えている必要はなく、一部のみを実現するようにしてもよい。また、上述した内容に追加の機能を設けてもよい。
実施例では、経路案内システムを例示したが、本発明は、経路案内と無関係に地図を表示するシステムとして構成することも可能である。また、本発明は、地図に限らず、グラフィックスライブラリを利用して画像を描画する描画装置一般に利用可能である。
本発明は上述の実施例に限定されず、その趣旨を逸脱しない範囲で種々の構成を採ることができることはいうまでもない。例えば、実施例においてハードウェア的に構成されている部分は、ソフトウェア的に構成することもでき、その逆も可能である。

本発明は、グラフィックスライブラリを用いた画像の描画速度を向上させるために利用可能である。

１００…描画データ生成装置
１０１…コマンド入力部
１０２…ラインデータ統合部
１０３…描画用地図データベース
１０４…原地図データベース
１０５…送受信部
１０６…ダミー点追加部
２００…サーバ
２０１…送受信部
２０２…データベース管理部
２０３…経路探索部
２１０…地図データベース
２１１…描画用地図データベース
２１３…ネットワークデータ
３００…端末
３００ｄ…ディスプレイ
３０１…送受信部
３０２…コマンド入力部
３０３…位置・通行情報取得部
３０４…主制御部
３０５…地図情報記憶部
３０６…表示制御部
３０７…ライン描画データ設定部

Claims (10)

1. グラフィックスライブラリを用いて画像を描画するための描画データを生成する描画データ生成装置であって、
   前記グラフィックスライブラリは、ラインデータによって指定された頂点間を順次結んでラインを描画するライン関数を有しており、
   前記描画データ生成装置は、
   前記描画すべき原データを格納する原データベースと、
   前記原データのうち、複数の前記ラインデータを一本のラインデータに統合するラインデータ統合部とを有しており、
   前記ラインデータ統合部は、
   前記原データに含まれるラインデータのうち、前記ライン関数を共通の設定で用いて描画されるべき複数のラインデータを抽出し、
   前記抽出された複数のラインデータを連結して一本のラインデータに統合するように、前記ラインデータの端点のうち空間的に離れている端点間を、非表示のラインで連結するデータを生成する描画データ生成装置。
2. 請求項１記載の描画データ生成装置であって、
   前記ライン関数は、ラインの一方の頂点に指定された第１の表示態様から、他方の頂点に指定された第２の表示態様に、表示態様を順次変化させながら該ラインを描画する機能を有しており、
   前記描画データ生成装置は、さらに、
   前記統合の際に、前記非表示のラインで連結すべき端点に重ねて、新たに連結で用いるためのダミー点を追加するダミー点追加部を備え、
   前記ラインデータ統合部は、前記ダミー点間を非表示のラインで連結する描画データ生成装置。
3. 請求項１または２記載の描画データ生成装置であって、
   前記ラインデータ統合部は、前記空間的に離れている端点のうち、距離が近い端点同士を連結する描画データ生成装置。
4. 請求項１〜３いずれか記載の描画データ生成装置であって、
   前記原データベースは、前記各ラインデータの形状、属性を示す固有の原インデックス情報が、それぞれラインデータに関連づけて格納されており、
   前記ラインデータ統合部は、前記原インデックス情報とは別に、前記統合されたラインデータの形状、属性を示す固有の統合インデックス情報を生成する描画データ生成装置。
5. グラフィックスライブラリを用いて画像を描画する描画装置であって、
   前記グラフィックスライブラリは、ラインデータによって指定された頂点間を順次結んでラインを描画するライン関数を有しており、
   前記描画装置は、
   所定サイズのメッシュに区切って生成された前記描画すべき原データを格納する原データベースと、
   前記描画の対象となるメッシュが複数あるとき、異なるメッシュに存在する前記ラインデータの端点同士を仮想的に連結して一本のラインデータに統合するライン描画データ設定部と、
   前記統合されたラインデータに基づいて前記ライン関数を呼び出すことによって描画を行う描画部とを備える描画装置。
6. 請求項５記載の描画装置であって、
   さらに、前記メッシュごとに、該メッシュ内の複数のラインデータを統合する請求項１〜４いずれか記載の描画データ生成装置を備え、
   前記ライン描画データ設定部は、前記メッシュごとに統合されたラインデータを対象として前記統合を行う描画装置。
7. グラフィックスライブラリを用いて画像を描画するための描画データを、コンピュータによって生成する描画データ生成方法であって、
   前記グラフィックスライブラリは、ラインデータによって指定された頂点間を順次結んでラインを描画するライン関数を有しており、
   前記コンピュータが実行するステップとして、
   前記描画すべき原データを格納する原データベースから前記原データを読み出すステップと、
   前記原データのうち、複数の前記ラインデータを一本のラインデータに統合するラインデータ統合ステップとを有しており、
   前記ラインデータ統合ステップは、
   前記原データに含まれるラインデータのうち、前記ライン関数を共通の設定で用いて描画されるべき複数のラインデータを抽出し、
   前記抽出された複数のラインデータを連結して一本のラインデータに統合するように、前記ラインデータの端点のうち空間的に離れている端点間を、非表示のラインで連結するデータを生成する描画データ生成方法。
8. グラフィックスライブラリを用いて画像を描画するための描画データを生成するためのコンピュータプログラムであって、
   前記グラフィックスライブラリは、ラインデータによって指定された頂点間を順次結んでラインを描画するライン関数を有しており、
   前記コンピュータプログラムは、
   前記描画すべき原データを格納する原データベースから前記原データを読み出す機能と、
   前記原データのうち、複数の前記ラインデータを一本のラインデータに統合するラインデータ統合機能とをコンピュータに実現させるコンピュータプログラムであり、
   前記ラインデータ統合機能は、
   前記原データに含まれるラインデータのうち、前記ライン関数を共通の設定で用いて描画されるべき複数のラインデータを抽出し、
   前記抽出された複数のラインデータを連結して一本のラインデータに統合するように、前記ラインデータの端点のうち空間的に離れている端点間を、非表示のラインで連結するデータを生成する機能であるコンピュータプログラム。
9. グラフィックスライブラリを用いてコンピュータにより画像を描画する描画方法であって、
   前記グラフィックスライブラリは、ラインデータによって指定された頂点間を順次結んでラインを描画するライン関数を有しており、
   前記コンピュータが実行するステップとして、
   所定サイズのメッシュに区切って生成された前記描画すべき原データを格納する原データベースから原データを読み出すステップと、
   前記描画の対象となるメッシュが複数あるとき、異なるメッシュに存在する前記ラインデータの端点同士を仮想的に連結して一本のラインデータに統合するライン描画データ設定ステップと、
   前記統合されたラインデータに基づいて前記ライン関数を呼び出すことによって描画を行う描画ステップとを備える描画方法。
10. グラフィックスライブラリを用いて画像を描画するためのコンピュータプログラムであって、
    前記グラフィックスライブラリは、ラインデータによって指定された頂点間を順次結んでラインを描画するライン関数を有しており、
    前記コンピュータプログラムは、
    所定サイズのメッシュに区切って生成された前記描画すべき原データを格納する原データベースから原データを読み出す機能と、
    前記描画の対象となるメッシュが複数あるとき、異なるメッシュに存在する前記ラインデータの端点同士を仮想的に連結して一本のラインデータに統合するライン描画データ設定機能と、
    前記統合されたラインデータに基づいて前記ライン関数を呼び出すことによって描画を行う描画機能とをコンピュータに実現させるためのコンピュータプログラム。
    
    

Images