(57)【要約】【課題】描画処理の高速化を図ることができると共に、輪郭線が曲線になる場合やシルエットの形状が変化する場合でも描画時間の増加を抑えることのできる地図描画装置を得る。【解決手段】シルエット多角形生成手段５は、三角形メッシュを構成する地表面三角形の各頂点を投影面上に投影して得られる各頂点に、更に頂点を追加して、投影面上のシルエットを包含するシルエット多角形を生成する。領域塗りつぶし手段８は、シルエット多角形に含まれる投影面上の各点に対し、対応する地表面上の点を逆投影変換手段６により求め、この点が地表面三角形の内部に含まれる場合は、投影面上の点を設定された色とする。【選択図】図１
2015095230.tif 000002
【特許請求の範囲】
【請求項１】
地表面上の点を投影面上の点へ投影する投影変換手段と、
前記地表面上の描画対象領域を三角形に分割した三角形メッシュを構成する地表面三角形の各頂点を前記投影変換手段により前記投影面上に投影して得られる各頂点に、更に頂点を追加して、前記地表面三角形の前記投影面上のシルエットを包含するシルエット多角形を生成するシルエット多角形生成手段と、
前記投影面上の点を前記地表面上の点へ逆投影する逆投影変換手段と、
前記シルエット多角形に含まれる前記投影面上の各点に対し、対応する前記地表面上の点を前記逆投影変換手段により求め、当該求めた点が前記地表面三角形の内部に含まれる場合は、前記投影面上の点を設定された色とする領域塗りつぶし手段とを備えたことを特徴とする地図描画装置。
【請求項２】
前記シルエット多角形生成手段は、前記地表面三角形の頂点間を結ぶ経路である弧を含む平面と投影する光源との位置関係に基づき前記投影面に投影された弧の向きを判定し、投影された弧の向きが、前記投影面上の前記地表面三角形の各頂点からなる三角形の外側ならば頂点を追加し、内側ならば頂点を追加しないことを特徴とする請求項１記載の地図描画装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、陸地や海域、行政区画など、境界線で囲まれた領域の内部を所定の色で塗りつぶした画像を生成する地図描画装置に関する。
【背景技術】
【０００２】
地図描画装置は、多角形の内部を塗りつぶす機能が求められる。このような塗りつぶしを行う方法として、例えば、非特許文献１には、多角形を構成する線の座標をエッジリストとして保持し、スキャンライン毎にエッジリストを参照しながら塗りつぶしの開始点と終了点を求め、順次塗りつぶしを行う方法（本明細書ではスキャンライン法と呼ぶ）が示されている。また、同文献には、多角形を三角形などの小さな領域に分割し、分割した領域ごとに塗りつぶしを行う方法（本明細書では三角形分割法と呼ぶ）が示されている。
【先行技術文献】
【非特許文献】
【０００３】
【非特許文献１】B.D.Ackland and N.H.Weste,The Edge Flag Algorithm―A Fill Method for Raster Scan Displays,IEEE Transactions on Computer,C-30,1,1981.
【発明の概要】
【発明が解決しようとする課題】
【０００４】
しかしながら、地図描画装置において、スキャンライン法は、スキャンライン毎の処理を逐次的に行うため、並列処理による高速化が難しいという問題があった。たとえば、描画処理を高速に実行するための手段として、グラフィックス処理装置（ＧＰＵ）がよく用いられる。ＧＰＵは複数の演算回路を備え、処理を並列に実行することにより処理を高速化するのに対し、スキャンライン法は処理を逐次的に行う必要がありＧＰＵによる高速化に向かなかった。
一方、三角形分割法は領域毎の処理を並列に行うことが可能であり、並列処理による高速化が見込める。ＧＰＵによる高速化にも向いているが、予め多角形を三角形領域に分割する必要があり、三角形分割の処理に時間がかかる、という問題があった。
【０００５】
ところで、地図描画装置が描画の対象とする領域は通常地表面上の領域であるから曲面を構成する。地図描画装置は、空間内に仮想的に投影面と光源を配置し、領域を投影上に投影した上で、得られたシルエットを描画する。ここで、緯線や経線で囲まれた領域を描画する場合を考える。この領域を投影面に投影する場合、投影面や光源の配置によってシルエットの輪郭線は直線になる場合と曲線になる場合がある。シルエットの輪郭線が曲線になる場合、曲線で囲まれた領域を多角形で表現するためには多角形の頂点の数を増やす必要が生じる。そうすると、スキャンライン法、三角形分割法のいずれを用いても描画処理の量が増加し、描画時間が増加する、という問題があった。
【０００６】
また、三角形分割法を用いた場合、予め行った三角形分割の結果を繰り返し利用できるのであれば良いが、投影面や光源の配置を変化させるとシルエットの形状が変わるため三角形分割をやり直す必要が生じ描画時間が長くなる、という問題があった。
【０００７】
この発明は上記のような課題を解決するためになされたもので、描画処理の高速化を図ることができると共に、輪郭線が曲線になる場合やシルエットの形状が変化する場合でも描画時間の増加を抑えることのできる地図描画装置を得ることを目的とする。
【課題を解決するための手段】
【０００８】
この発明に係る地図描画装置は、地表面上の点を投影面上の点へ投影する投影変換手段と、地表面上の描画対象領域を三角形に分割した三角形メッシュを構成する地表面三角形の各頂点を投影変換手段により投影面上に投影して得られる各頂点に、更に頂点を追加して、地表面三角形の投影面上のシルエットを包含するシルエット多角形を生成するシルエット多角形生成手段と、投影面上の点を地表面上の点へ逆投影する逆投影変換手段と、シルエット多角形に含まれる投影面上の各点に対し、対応する地表面上の点を逆投影変換手段により求め、求めた点が地表面三角形の内部に含まれる場合は、投影面上の点を設定された色とする領域塗りつぶし手段とを備えたものである。
【発明の効果】
【０００９】
この発明の地図描画装置は、投影面上に投影して得られる各頂点に、更に頂点を追加して、地表面三角形の投影面上のシルエットを包含するシルエット多角形を生成し、このシルエット多角形に含まれる各点に対し、対応する地表面上の点を求め、求めた点が地表面三角形の内部に含まれる場合に投影面上の点を設定された色とするようにしたので、並列処理による描画処理の高速化を図ることができると共に、輪郭線が曲線になる場合やシルエットの形状が変化する場合でも描画時間の増加を抑えることができる。
【図面の簡単な説明】
【００１０】
【図１】この発明の実施の形態１による地図描画装置を示す構成図である。
【図２】この発明の実施の形態１による地図描画装置を実現する地図表示システムを示す構成図である。
【図３】この発明の実施の形態１による地図描画装置の全体の動作を示すフローチャートである。
【図４】この発明の実施の形態１による地図描画装置のシルエット多角形生成処理の流れを示すフローチャートである。
【図５】この発明の実施の形態１による地図描画装置の領域塗りつぶし処理の流れを示すフローチャートである。
【図６】この発明の実施の形態１による地図描画装置の領域の輪郭情報の表現方法を示す説明図である。
【図７】この発明の実施の形態１による地図描画装置の三角形メッシュの説明図である。
【図８】この発明の実施の形態１による地図描画装置の投影変換の説明図である。
【図９】この発明の実施の形態１による地図描画装置の投影変換の一例を示す説明図である。
【図１０】この発明の実施の形態１による地図描画装置のシルエット多角形の生成を示す説明図である。
【図１１】この発明の実施の形態１による地図描画装置の弧の向きの判定を示す説明図である。
【図１２】この発明の実施の形態１による地図描画装置の頂点の追加を示す説明図である。
【図１３】この発明の実施の形態１による地図描画装置の内外判定の説明図である。
【発明を実施するための形態】
【００１１】
実施の形態１．
図１は、この発明の実施の形態１による地図描画装置を示す構成図である。
図１に示す地図描画装置は、領域記憶手段１、領域分割手段２、三角形メッシュ記憶手段３、投影変換手段４、シルエット多角形生成手段５、逆投影変換手段６、内外判定手段７、領域塗りつぶし手段８、塗りつぶし画像記憶手段９を備えている。本発明の地図描画装置は、地表面上の領域を所定の投影図法で投影面に投影し、この領域に対応するシルエットを描画する装置である。
【００１２】
領域記憶手段１は、地表面上の描画対象となる領域の輪郭情報を記憶する手段である。
領域分割手段２は、領域記憶手段１に記憶されている領域を三角形に分割し三角形メッシュを生成する手段である。三角形メッシュ記憶手段３は、領域分割手段２で生成された三角形メッシュを記憶する手段である。投影変換手段４は、地表面上の点を投影面上の点へ投影する手段である。シルエット多角形生成手段５は、三角形メッシュを構成する三角形の各頂点を投影変換手段４により投影面上に投影して得られる三角形に、更に頂点を追加して、シルエットを包含するシルエット多角形を生成する手段である。逆投影変換手段６は、投影面上の点を地表面上の点へ逆投影する手段である。内外判定手段７は、地表面上の与えられた点が、与えられた領域の内部に含まれるかどうかを判定する手段である。
領域塗りつぶし手段８は、シルエット多角形に含まれる投影面上の各点に対し、対応する地表面上の点を逆投影変換手段６により求め、その点が領域の内部に含まれるかどうかを内外判定手段７により判定した結果を用い、内部に含まれると判定した場合に投影面上の点に所定の色をつける手段である。塗りつぶし画像記憶手段９は、領域塗りつぶし手段８によって得られた画像を記憶する手段である。
【００１３】
図２は、この発明の地図描画装置を実現する地図表示システムの例を示す構成図である。
この地図表示システムはパーソナルコンピュータ（ＰＣ）を用いて構成されており、ＰＣ本体１００、補助記憶装置１１０、入力装置１２０、表示装置１３０を備えている。ＰＣ本体１００には、中央処理装置（ＣＰＵ）１０１、主記憶装置１０２、グラフィックス処理装置（ＧＰＵ）１０３を備えている。
ＣＰＵ１０１は地図描画装置として種々の制御を司るプロセッサである。主記憶装置１０２は、ＣＰＵ１０１が各種の処理を行う際の作業領域を構成すると共に、領域記憶や三角形メッシュ記憶を行うためのメモリである。ＧＰＵ１０３は、画像処理を行うためのプロセッサ（Graphics Processing Unit：グラフィックス プロセッシング ユニット）であり、一般的なＰＣに搭載されるＧＰＵ１０３には、ユーザプログラムを実行するシェーダと呼ばれる仕組みが組み込まれている。この実施の形態ではジオメトリシェーダ１０４とフラグメントシェーダ１０５を利用する。ここで、ジオメトリシェーダ１０４は描画対象となる図形要素毎にユーザプログラムを起動し、フラグメントシェーダ１０５は描画対象となる画素毎にユーザプログラムを起動する。これらのシェーダは複数の演算回路により処理を並列に実行するように構成されており、図形要素毎あるいは画素毎の繰り返し処理を高速に実行可能であるという特長がある。
【００１４】
一般に、グラフィックス処理装置（ＧＰＵ）を備えたＰＣで描画を行う場合、描画時間を短縮するためには、図形要素毎あるいは画素毎の繰り返し処理はなるべくシェーダで実行するのが有効である。その上で、描画する図形要素の数を減らせば、更に描画時間を短縮することができる。
【００１５】
補助記憶装置１１０は、描画すべき領域の輪郭情報を記憶するための記憶装置である。
地図描画装置は、この補助記憶装置１１０から領域の情報を読み出して利用する。
入力装置１２０は、マウス、キーボード等の入力装置であり、ユーザの指示を入力するためのものである。ユーザが投影図法をマウスやキーボードを用いて指定すると、システムはそれに応じて仮想的に光源や投影面の配置を設定する。ユーザはこれにより必要に応じて投影図法を変更し、見たい場所を見たい縮尺で画面に表示して見ることができる。
表示装置１３０は、地図描画装置によって得られた描画結果を画面上に表示するための表示装置である。
【００１６】
また、図１における領域記憶手段１と三角形メッシュ記憶手段３と塗りつぶし画像記憶手段９は補助記憶装置１１０または主記憶装置１０２上に構成され、領域分割手段２はＣＰＵ１０１や主記憶装置１０２によって構成されている。さらに、投影変換手段４〜領域塗りつぶし手段８は、ＧＰＵ１０３によって構成されている。
【００１７】
次に、地図描画装置の動作について説明する。図３〜図５は処理の流れを示すフローチャートであり、図３は全体の処理の流れ、図４はシルエット多角形生成処理の流れ、図５は、領域塗り潰しの処理の流れを示している。
（１）領域分割（ステップＳＴ１）
地図描画装置では、対象とする領域の輪郭情報として図６に示すような領域データ６０１と頂点データ６０２を補助記憶装置１１０から読み込み、主記憶装置１０２内の領域記憶手段１に記憶する。
図６に示すように、輪郭情報は輪郭を多角形で表現し、その頂点を反時計回りに順にたどって表にし、頂点毎に緯度・経度を登録することにより表現する。図６の場合は頂点数が５の場合である。
次に、領域分割手段２は、この領域を三角形に分割し、図７に示すような三角形メッシュ７０１を作成する。生成された三角形メッシュ７０１は、図示のような三角形データ７０２と頂点データ７０３により表現し、三角形メッシュ記憶手段３に記憶する。
この処理は、領域の輪郭情報が与えられた時に一度だけ実行し、結果を三角形メッシュ記憶手段３に記憶しておけばよい。投影図法を変更しても三角形メッシュ７０１は変更する必要は無い。このため、領域分割の処理時間は、最初の一回を除いて描画時間に影響を与えない。
【００１８】
（２）投影図法設定（ステップＳＴ２）
地図描画装置は、入力装置１２０から入力されたユーザの指示に従い光源と投影面を配置し、投影図法を設定する。
投影図法が設定されると、投影変換手段４および逆投影変換手段６により、それぞれ地表面上の点から投影面上の点への変換、および投影面上の点から地表面上の点への変換が可能となる。この処理はＧＰＵ１０３においてシェーダプログラムによって実現される。
処理は後述するステップＳＴ３のシルエット多角形生成およびステップＳＴ４の領域塗りつぶしの処理の中で呼び出されるが、ここで投影変換と逆投影変換の原理を説明する。
【００１９】
地図を描画するための投影図法には様々な図法があるが、ここでは正射投影図法を例にとって説明を行う。正射投影図法は、基準点で地表面に接するように投影面を置き、地球中心から見て基準点と反対方向の無限遠点に光源を置いたものとして投影する方法である。
以下の説明では、地球の重心を原点とし、ｘ軸をグリニッジ子午線と赤道との交点の方向、ｙ軸を東経９０度の方向、ｚ軸を北極の方向にとることにより定義される３次元空間を地球中心座標空間と呼ぶ。また、地表面上の一点を原点とし、天頂方向をＺ軸、これに直角に東方向にＸ軸、北方向にＹ軸をとることにより定義される３次元空間を地平座標空間と呼ぶ。以降、原則として小文字は地球中心座標、大文字は地平座標を表す。
【００２０】
地表面上のある点の地球中心座標空間における座標をｐ＝（ｘ，ｙ，ｚ）とする。この点が投影変換
2015095230.tif 000003
によって投影面上の点Ｑ＝（Ｘ，Ｙ，０）に投影されるものとする。
上記の点ｐを、基準点ｃを原点とする地平座標に変換して、Ｐ＝（Ｘ，Ｙ，Ｚ）を得るものとすると、回転行列Ｒと並進行列Ｔを用いて、
2015095230.tif 000004
ここで、正射投影の基準点ｃの緯度をφ0、経度をλ0とする。回転行列Ｒは、
2015095230.tif 000005
ただし、
2015095230.tif 000006
2015095230.tif 000007
によって与えられる。
【００２１】
また、並進行列は、
2015095230.tif 000008
ここで、Ｎは卯酉線曲率半径、ｅは楕円体の離心率、ａは楕円体の長半径である。
【００２２】
式（２）により、緯度、経度で与えられた地表面上の点の地球中心座標が地平座標に変換される。地平座標（Ｘ，Ｙ，Ｚ）から投影面上の座標（Ｘ，Ｙ，０）への変換は行列
2015095230.tif 000009
によって表現できるので、
2015095230.tif 000010
以上の計算により、地表面上の点ｐを投影変換して得られる投影面上の座標Ｑを求めることができる。
【００２３】
次に、投影面上の点Ｑ＝（Ｘ，Ｙ，０）から地表面上の点ｐ＝（ｘ，ｙ，ｚ）への逆投影変換
2015095230.tif 000011
について考える。
投影面上の点Ｑ＝（Ｘ，Ｙ，０）に相当する地球中心座標空間における点をｑ＝（ｘq，ｙq，ｚq）とすると
2015095230.tif 000012
となる。
【００２４】
図８に示すように、地表面上の点ｐが投影面上の点ｑに投影されるものとする。点ｐの座標は、点ｑを通る光線と地表面との交点を求めることによって計算できる。
光線方向の単位ベクトルをｒ＝（ｘr，ｙr，ｚr）とすると、定数ｋを用いて
2015095230.tif 000013
すなわち
2015095230.tif 000014
と表せる。
【００２５】
地表面は地球楕円体で近似されるものとすると、点ｐ＝（ｘ，ｙ，ｚ）が地表面上にある、という条件は、
2015095230.tif 000015
と表される。ここで、ａは、地球楕円体の長半径、ｂは、地球楕円体の短半径である。
式（１２）を式（１３）に代入し、方程式を解くと、ｋの値が得られるから、これを式（１１）に代入すると地点ｐの地球中心座標が得られる。
【００２６】
よって、投影図法によって決まる回転行列をＲ、並進行列をＴ、光線方向の単位ベクトルをｒ＝（ｘr，ｙr，ｚr）とし、
2015095230.tif 000016
2015095230.tif 000017
2015095230.tif 000018
と置くと、逆投影変換を計算する式は
2015095230.tif 000019
と表される。
【００２７】
（３）シルエット多角形生成（ステップＳＴ３）
図９は点ａ，ｂ，ｃで囲まれた領域に対応する２種類のシルエットの例を示した図である。
光源１と投影面１で規定される投影変換１によって地表面上の点ａ，ｂ，ｃはそれぞれ点Ａ1，Ｂ1，Ｃ1に投影される。この３点をむすぶと、図の破線で囲まれた三角形Ａ1Ｂ1Ｃ1が得られるが、目的とするシルエットは通常この三角形とは一致しない。領域ａｂｃは曲面となるため、シルエットは例えば図の実線で囲まれた領域のように３つの弧で囲まれた領域となる。
光源２と投影面２で規定される投影変換２によって地表面上の点ａ，ｂ，ｃはそれぞれ点Ａ2，Ｂ2，Ｃ2に投影される。この３点をむすぶと、図の破線で囲まれた三角形Ａ2Ｂ2Ｃ2が得られるが、投影変換１と同様に、目的とするシルエットは通常この三角形とは一致しない。目的とするシルエットは例えば図の実線で囲まれた領域のように３つの弧で囲まれた領域となる。
【００２８】
図９に示した投影変換１と投影変換２を比較すると、投影変換１では、投影面上に生成される弧Ａ1Ｂ1，Ｂ1Ｃ1,Ｃ1Ａ1はいずれも三角形Ａ1Ｂ1Ｃ1の外側を通る。一方、投影変換２では投影面上に生成される弧Ａ2Ｂ2，Ｃ2Ａ2は三角形Ａ2Ｂ2Ｃ2の外側を通るが、弧Ｂ2Ｃ2は三角形Ａ2Ｂ2Ｃ2の内側を通っている。このように、光源と投影面の配置によって目的とするシルエットは変化する。
シルエット多角形生成手段５は、目的とするシルエットの形状に応じて、シルエットを包含する多角形を生成する。この多角形をシルエット多角形と呼ぶ。図１０に上記の投影変換１と投影変換２で得られた三角形Ａ1Ｂ1Ｃ1と三角形Ａ2Ｂ2Ｃ2に対してシルエット多角形を生成した例を示す。投影変換１では、目的とするシルエットの３つの弧はいずれも三角形Ａ1Ｂ1Ｃ1の外側を通るので、頂点Ａ1とＢ1の間、頂点Ｂ1とＣ1の間、および頂点Ｃ1とＡ1の間にそれぞれ点Ａ1′，Ｂ1′，Ｃ1′を挿入し、６角形Ａ1Ａ1′Ｂ1Ｂ1′Ｃ1Ｃ1′を生成する。投影変換２では、目的とするシルエットの３つの弧のうち２つの弧Ａ2Ｂ2，Ｃ2Ａ2が三角形Ａ2Ｂ2Ｃ2の外側を通るので、頂点Ａ2とＢ2の間、および頂点Ｃ2とＡ2の間にそれぞれ点Ａ2′と点Ｃ2′を挿入し、５角形Ａ2Ａ2′Ｂ2Ｃ2Ｃ2′を生成する。
このシルエット多角形生成の処理を、この実施の形態ではジオメトリシェーダ１０４を用いて実行する。処理の流れを以下に説明する。
【００２９】
ＣＰＵ１０１は、先ず、三角形メッシュデータをＧＰＵ１０３に転送し、次に、領域の描画を指示する。
すると、三角形メッシュを構成する三角形毎にジオメトリシェーダ１０４がユーザプログラムを実行する。ジオメトリシェーダ１０４の処理の流れを図４のフローチャートに従って説明する。図４に示すように、三角形を構成する辺ごとに以下の処理を行う。対象とする三角形の各頂点をＡ，Ｂ，Ｃとすると、処理対象とする辺はＡＢ，ＢＣ，ＣＡの３つの辺となる。
（ｉ）投影変換（ステップＳＴ３１）
処理対象となる辺の地表面における始終点をそれぞれｖ0，ｖ1とする。また、三頂点の内、処理対象とする辺以外の点をｖ2とする。
始点ｖ0を投影変換して得られる投影面上の点Ｖ0は、次式に式（８）を適用することによって得られる。
2015095230.tif 000020
得られた座標Ｖ0をシルエット多角形の頂点座標としてリストに追加する。
【００３０】
（ｉｉ）弧の向きの判定（ステップＳＴ３２）
図１１に示すように、上記の点ｖ0と点ｖ1を結ぶ、地表面上の経路は弧を描く。この弧を含む平面を考え、これをＧとする。平面Ｇを基準として、点ｖ2と同じ側を内側、点ｖ2の反対側を外側とする。この時、光源が平面Ｇの外側にあれば、投影された弧Ｖ0Ｖ1は三角形Ｖ0Ｖ1Ｖ2に対して外側を向き、光源が平面Ｇの内側にあれば、投影された弧Ｖ0Ｖ1は三角形Ｖ0Ｖ1Ｖ2に対して内側を向く。
2015095230.tif 000021
【００３１】
2015095230.tif 000022
弧Ｖ0Ｖ1の向きが三角形に対して外向きの場合、三角形の辺Ｖ0Ｖ1の外側に頂点を追加してシルエット多角形を拡張する。具体的には下記の頂点追加の処理を行う。
【００３２】
（ｉｉｉ）頂点追加（ステップＳＴ３３）
2015095230.tif 000023
次に、シルエット多角形を生成するために追加する頂点をＶ0′とする。
2015095230.tif 000024
2015095230.tif 000025
と、置いてｋ，ｌについて解くと、頂点座標Ｖ0′が求められる。得られた頂点座標Ｖ0′をシルエット多角形の頂点としてリストに追加する。
（ｉ）〜（ｉｉｉ）の処理を三角形の３つの辺について繰り返すと、三角形メッシュの各頂点を投影した点と追加した頂点から成るシルエット多角形の頂点のリストが生成される。
【００３３】
（４）領域塗りつぶし（ステップＳＴ４）
生成されたシルエット多角形は、三角形メッシュに対応する三角形と、頂点の追加によって生成された、いくつかの三角形に分割できる。これらの三角形のそれぞれについて内部の画素毎にフラグメントシェーダ１０５が呼び出される。
フラグメントシェーダ１０５は予め登録してあるユーザプログラムを実行する。当該画素をＱとし、この点がシルエットに含まれる場合はその画素に色づけを行う。処理の流れを図５のフローチャートに沿って説明する。
【００３４】
（ｉ）逆投影変換（ステップＳＴ４１）
逆投影変換手段６により当該画素Ｑの投影面上での座標を逆投影し、地表面上の座標ｐを求める。投影面上での座標Ｑに対して式（１７）を適用することによって行う。
（ｉｉ）内外判定（ステップＳＴ４２）
内外判定手段７は、図１３に示すように、当該画素の地表面上での座標ｐを領域ａｂｃの頂点の座標と比較し、当該画素が領域に含まれるかどうかを判定する。地球中心座標空間の原点をｏとし、
2015095230.tif 000026
とおいて、ｋ，ｌ，ｍについて解き、ｋ＞０，ｌ＞０，ｍ＞０であれば直線ｏｐは領域ａｂｃの内部を通る。このとき、投影面上で点Ｑは目的とするシルエットの内部にあると判定する。それ以外の場合は、点Ｑはシルエットの外部または周上にあると判定する。
（ｉｉｉ）色づけ（ステップＳＴ４３）
上記の内外判定の結果、当該画素が目的とするシルエットの内部にあると判定されたら、領域塗りつぶし手段８は、その画素に所定の色をつける。
【００３５】
以上のように、実施の形態１では、シルエット多角形生成手段５が、目的とするシルエットを推定し、このシルエットを包含するようにシルエット多角形を生成し、領域塗りつぶし手段８が、このシルエット多角形に含まれる各点に対し、その点に対応する地表面上の点を求め、その点が領域の内部に含まれると判定した場合その点に所定の色をつけるので、シルエット多角形生成手段５の処理は三角形メッシュを構成する三角形毎に、また領域塗りつぶし手段８の処理はシルエット多角形に含まれる画素毎に並列に処理が可能で、ＧＰＵ１０３の性能を活かして描画時間を短縮することができる。
【００３６】
また、実施の形態１では、目的とするシルエットの輪郭が曲線である場合でも三角形メッシュを構成する三角形を大幅に増やすことなく、領域をなめらかに描画することができる。従って、目的とするシルエットの輪郭が曲線となる場合でも三角形メッシュを構成する三角形を細かくする場合と比べて描画時間の増加が少ないという効果がある。
【００３７】
さらに、領域分割手段２は地表面上の領域を三角形に分割して三角形メッシュを生成し、シルエット多角形生成手段５は、投影図法に応じて目的とするシルエットを推定し、三角形メッシュの各頂点を投影面上に投影して得られる三角形に、更に頂点を追加してシルエットを包含するようにシルエット多角形を生成するので、投影図法が変化しても三角形メッシュを作り直す必要がない。従って、投影図法が変化したときでも、三角形メッシュを作り直す場合と比べて描画時間の増加が少ない、という効果がある。
【００３８】
加えて、シルエット多角形生成手段５は、目的とするシルエットの輪郭を構成する弧の向きを判定し、弧が外向きの時だけ頂点を追加してシルエット多角形を生成するので、多角形の頂点の数は最小限におさえられ、その結果、シルエット多角形を構成する三角形の数も最小限となる。従って頂点を追加してシルエット多角形を生成する場合でも、全ての辺に対して頂点を挿入するよりも描画時間の増加が少ない、という効果がある。
【００３９】
以上説明したように、実施の形態１の地図描画装置によれば、地表面上の点を投影面上の点へ投影する投影変換手段と、地表面上の描画対象領域を三角形に分割した三角形メッシュを構成する地表面三角形の各頂点を投影変換手段により投影面上に投影して得られる各頂点に、更に頂点を追加して、地表面三角形の投影面上のシルエットを包含するシルエット多角形を生成するシルエット多角形生成手段と、投影面上の点を地表面上の点へ逆投影する逆投影変換手段と、シルエット多角形に含まれる投影面上の各点に対し、対応する地表面上の点を逆投影変換手段により求め、求めた点が地表面三角形の内部に含まれる場合は、投影面上の点を設定された色とする領域塗りつぶし手段とを備えたので、並列処理による描画処理の高速化を図ることができると共に、輪郭線が曲線になる場合やシルエットの形状が変化する場合でも描画時間の増加を抑えることができる。
【００４０】
また、実施の形態１の地図描画装置によれば、シルエット多角形生成手段は、地表面三角形の頂点間を結ぶ経路である弧を含む平面と投影する光源との位置関係に基づき投影面に投影された弧の向きを判定し、投影された弧の向きが、投影面上の地表面三角形の各頂点からなる三角形の外側ならば頂点を追加し、内側ならば頂点を追加しないようにしたので、輪郭線が曲線になる場合やシルエットの形状が変化する場合でも、描画時間の増加を抑え、領域をなめらかに描画することができる。
【００４１】
なお、本願発明はその発明の範囲内において、実施の形態の任意の構成要素の変形、もしくは実施の形態の任意の構成要素の省略が可能である。
【符号の説明】
【００４２】
１  領域記憶手段、２  領域分割手段、３  三角形メッシュ記憶手段、４  投影変換手段、５  シルエット多角形生成手段、６  逆投影変換手段、７  内外判定手段、８  領域塗りつぶし手段、９  塗りつぶし画像記憶手段。
【図１】
2015095230.tif 000027
【図２】
2015095230.tif 000028
【図３】
2015095230.tif 000029
【図４】
2015095230.tif 000030
【図５】
2015095230.tif 000031
【図６】
2015095230.tif 000032
【図７】
2015095230.tif 000033
【図８】
2015095230.tif 000034
【図９】
2015095230.tif 000035
【図１０】
2015095230.tif 000036
【図１１】
2015095230.tif 000037
【図１２】
2015095230.tif 000038
【図１３】
2015095230.tif 000039