(57)【要約】【課題】ベクタ図形を曲面上に描画する場合であっても、再分割処理等による処理負担が増加することなく高速に描画処理を行うことのできる描画装置及び方法を提供する。【解決手段】曲面モデルをスクリーンに投影した際に該曲面モデルが占めるピクセルごとに、ベクタ定義空間における位置座標、色情報及び透明度を含む描画用パラメータを算出する。ベクタデータから複数のプリミティブデータを生成して記憶する。複数のプリミティブデータに前記位置座標を含むか否かを判定して描画判定変数を求め、描画判定変数を加算した回数が奇数であるならば、前記位置座標に対応するピクセルのラスタデータを前記描画用パラメータに基づいて生成する。【選択図】図１
2009301284.tif 000002
【特許請求の範囲】
【請求項１】
任意の図形を表すベクタデータを記憶する第１の記憶部と、
前記図形を描画するガイドとしての曲面モデルを記憶する第２の記憶部と、
前記曲面モデルをスクリーンに投影した際に該曲面モデルが占めるピクセルごとに、前記曲面モデルとは独立して前記図形を定義するとともに該ピクセルの属性値を決定するために参照されるベクタ定義空間における位置座標、色情報及び透明度を含む描画用パラメータを算出する第１の算出部と、
前記ベクタデータを輪郭線解析することにより直線輪郭または曲線輪郭のいずれかに基づく複数のプリミティブデータを生成する第１の生成部と、
前記ベクタ定義空間における前記複数のプリミティブデータを記憶する第３の記憶部と、
前記複数のプリミティブデータに前記位置座標を含むか否かを判定し、前記位置座標を含むプリミティブデータが前記直線輪郭のプリミティブデータであれば前記位置座標の描画判定変数を加算し、前記位置座標を含むプリミティブデータが前記曲線輪郭のプリミティブデータであれば、該位置座標が曲線輪郭の凸領域に含まれるならば前記描画判定変数を加算する判定部と、
前記描画判定変数を加算した回数が奇数であるならば、前記位置座標に対応するピクセルの属性値を前記描画用パラメータに基づいて生成する第２の生成部と、を具備する描画装置。
【請求項２】
前記ベクタ定義空間は二次元の空間である請求項１記載の装置。
【請求項３】
前記プリミィティブデータは、三角形データである請求項１記載の装置。
【請求項４】
前記プリミィティブデータは、四点以上で構成される凸多角形データである請求項１記載の装置。
【請求項５】
前記位置座標と前記プリミティブとの間の最短距離を算出する第２の算出部と、
前記最短距離をパラメータとしてぼかし処理または透過処理を含む画像処理を前記属性値に対して行う画像処理部とをさらに具備する請求項１記載の装置。
【請求項６】
前記第３の記憶部に記憶されたプリミティブデータに対し、補正用パラメータに従ってアフィン変換による変形を施して補正後のプリミティブデータを求める補正部をさらに具備し、
前記判定部は、前記補正後のプリミティブデータを用いて前記位置座標を含むか否かの判定を行う請求項１記載の装置。
【請求項７】
ユーザ操作を受け付けて入力値を出力する入力デバイスをさらに具備し、
前記補正部は、前記入力値を加工することにより前記補正用パラメータを求める請求項６記載の装置。
【請求項８】
ピクセル毎に、前記位置座標が前記プリミティブデータに含まれるか否かの判定結果及び前記位置座標を記憶する第４の記憶部と、
前記第４の記憶部の判定情報を参照して描画結果画像のエッジとなるピクセルを特定し、該ピクセルに対応する位置座標を参照し、エッジピクセルをサブピクセルに分割した際のサブピクセルごとの対応位置を算出する第４の算出部と、
前記サブピクセルの対応位置の描画可否を判定するとともに、該サブピクセルの分割元であるピクセルがどの程度の割合で描画可となっているかを示すカバレッジデータを算出する第５の算出部と、をさらに具備し、
前記第２の生成部は、前記カバレッジデータがより大きいほど元ピクセルの色情報を利用するサブピクセルが多くなるようにサブピクセル精度の画像を生成し、該サブピクセル画像を合成して前記属性値を生成する請求項１記載の装置。
【請求項９】
任意の図形を表すベクタデータを第１の記憶部に記憶するステップと、
前記図形を描画するガイドとしての曲面モデルを第２の記憶部に記憶するステップと、
前記曲面モデルをスクリーンに投影した際に該曲面モデルが占めるピクセルごとに、前記曲面モデルとは独立して前記図形を定義するとともに該ピクセルの属性値を決定するために参照されるベクタ定義空間における位置座標、色情報及び透明度を含む描画用パラメータを第１の算出部により算出するステップと、
前記ベクタデータを輪郭線解析することにより直線輪郭または曲線輪郭のいずれかに基づく複数のプリミティブデータを第１の生成部により生成するステップと、
前記ベクタ定義空間における前記複数のプリミティブデータを第３の記憶部に記憶するステップと、
判定部が、前記複数のプリミティブデータに前記位置座標を含むか否かを判定し、前記位置座標を含むプリミティブデータが前記直線輪郭のプリミティブデータであれば前記位置座標の描画判定変数を加算し、前記位置座標を含むプリミティブデータが前記曲線輪郭のプリミティブデータであれば、該位置座標が曲線輪郭の凸領域に含まれるならば前記描画判定変数を加算するステップと、
前記描画判定変数を加算した回数が奇数であるならば、前記位置座標に対応するピクセルの属性値を前記描画用パラメータに基づいて第２の生成部が生成するステップと、を有する描画方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はベクトル図形を描画する描画装置および描画方法に関する。
【背景技術】
【０００２】
点や直線、曲線、四角形、楕円などの幾何学的な図形要素を組み合わせることによって構成される画像のことをベクタグラフィックスと呼ぶ。これに対し、点（ピクセルあるいはドット）の配列によって構成される画像のことをラスタグラフィックスと呼ぶ。
【０００３】
一般に、ディスプレイに表示される画像やプリンタで印刷される画像はラスタグラフィックスである。これらの機器でベクタグラフィックスを扱う際には、これをラスタグラフィクスへ変換する処理（ラスタライズ）が必要になる。ラスタライズの処理コストは高く、複雑なベクタグラフィックスをラスタライズするためには高性能な計算機が必要とされる。その反面、ベクタグラフィックスは表示の都度、適切な解像度のラスタグラフィックスを生成することができるため、画像の拡大や縮小、変形によって輪郭線などの画質が損なわれることがない。そのため、イラストや図面などの輪郭線が明瞭な人工的な画像はベクタグラフィックスとして扱われることが多い。一方、写真などの自然画像はラスタグラフィックスとして扱われることが多い。
【０００４】
ベクタグラフィックスの最も身近な利用例はフォントである。初期の計算機ではＣＰＵ性能の制約からラスタ形式のフォント（ビットマップフォント）が使われていたが、解像度ごとにフォントデータを保持しなければならなかったため多くの記憶容量を必要とした。その後のＣＰＵ性能の向上に伴い、現在の計算機では、解像度に依存しないベクタ形式のフォント（アウトラインフォント）データを保持しておき、ディスプレイやプリンタに見合った適切な解像度のフォントをその都度生成することにより、少ない記憶容量で常に高品質なフォントを表示できるようになった。しかし現在でも、携帯電話やカーナビゲーションシステムなどに内蔵されるＣＰＵは処理能力が比較的低く、ベクタグラフィックスのラスタライズに要する演算コストを低減することが課題になっている。
【０００５】
近年、この課題を解決するためにＧＰＵ（グラフィックスプロセッサユニット）が活用されている。ＧＰＵを利用し、直線と曲線で構成される図形をラスタライズするための手法が既に提案されている（例えば下記特許文献１参照。）。
【０００６】
また、図形の幾何形状が動的に変化しても高速にラスタライズが可能な手法も公知である（例えば下記特許文献２参照。）。
【特許文献１】特開２００６−１０６７０５号公報
【特許文献２】特開２００７−３０４８７１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００７】
本発明は、ベクタ図形を曲面上に描画する場合であっても、再分割処理等による処理負担が増加することなく高速に描画処理を行うことのできる描画装置及び方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
本発明の一観点に係る描画装置は、任意の図形を表すベクタデータを記憶する第１の記憶部と、前記図形を描画するガイドとしての曲面モデルを記憶する第２の記憶部と、前記曲面モデルをスクリーンに投影した際に該曲面モデルが占めるピクセルごとに、前記曲面モデルとは独立して前記図形を定義するとともに該ピクセルの属性値を決定するために参照されるベクタ定義空間における位置座標、色情報及び透明度を含む描画用パラメータを算出する第１の算出部と、前記ベクタデータを輪郭線解析することにより直線輪郭または曲線輪郭のいずれかに基づく複数のプリミティブデータを生成する第１の生成部と、前記ベクタ定義空間における前記複数のプリミティブデータを記憶する第３の記憶部と、前記複数のプリミティブデータに前記位置座標を含むか否かを判定し、前記位置座標を含むプリミティブデータが前記直線輪郭のプリミティブデータであれば前記位置座標の描画判定変数を加算し、前記位置座標を含むプリミティブデータが前記曲線輪郭のプリミティブデータであれば、該位置座標が曲線輪郭の凸領域に含まれるならば前記描画判定変数を加算する判定部と、前記描画判定変数を加算した回数が奇数であるならば、前記位置座標に対応するピクセルの属性値を前記描画用パラメータに基づいて生成する第２の生成部と、を具備する。
【発明の効果】
【０００９】
本発明によれば、ベクタ図形を曲面上に描画する場合であっても、再分割処理等による処理負担が増加することなく高速に描画処理を行うことのできる描画装置及び方法を提供することができる。
【発明を実施するための最良の形態】
【００１０】
以下、図面を参照して本発明の実施形態について説明する。
【００１１】
（第１実施形態）「前処理や再分割が不要な曲面レンダリング」
図１に示すように、第１実施形態に係る描画装置は、ベクタ図形を描画するガイドとして用いられ、その上にベクタデータがレンダリングされる曲面モデル（以下、「曲面」という。）、及びベクタデータをレンダリングする位置であるベクタデータ定義位置を記憶するモデル記憶部１と、任意の図形を表すベクタ形式の図形データ（以下、「ベクタデータ」という）を記憶するベクタデータ記憶部５と、モデル記憶部１から曲面及びベクタデータ定義位置のデータを入力し、描画結果を構成する各ピクセルに対応する、曲面上での位置座標（例えばテクスチャ座標でもよい）などの描画用パラメータを算出する描画用パラメータ算出部２と、ベクタデータ記憶部５に保持されているベクタデータを読み込んで、ベクタデータを描画するために利用する、三角形や凸多角形に代表されるプリミティブデータを、曲面が定義される空間とは独立した空間であって独自の位置座標（またはテクスチャ座標）などでレンダリング対象のベクタデータが定義される空間であるベクタ定義空間に生成する三角形データ生成部（描画制御用プリミティブ生成部）３と、三角形データ生成部３によって生成された三角形データを記憶するための三角形データ記憶部（描画制御用プリミティブ記憶部）４と、描画用パラメータ算出部２で得られた対応位置と、三角形データ記憶部４に記憶されたプリミティブ（例えば三角形）とを用いて、要求される出力データの詳細度に応じて決定される解像度のラスタデータの各ピクセルが、どのようにレンダリングされるべきかを判定するための判定情報を算出する描画属性制御情報算出部７と、描画属性制御情報算出部７によって得られた判定情報を用いて、そのピクセルを描画するかどうかを判定し、色情報、アルファ値を決定してラスタデータを出力するラスタデータ生成部８とを有する。
【００１２】
ラスタデータ生成部８で出力される結果は、ビットマップやＪＰＥＧ、ＧＩＦなどのグラフィックス分野で一般的に用いられる画像形式でラスタデータ記憶部９に保存されてもよいし、ディスプレイやプリンタなどの提示部１０に出力されてもよい。また、ネットワークを通じて出力結果、あるいは保存されたデータが転送されてもよい。
【００１３】
なお図１では、モデル記憶部１とベクタデータ記憶部５および三角形データ記憶部４を異なるブロックとして表記しているが、これらは単一のメモリ上にまとめて構成してもよいし、異なる複数のメモリ上に分割して構成してもよい。
【００１４】
また本実施形態では、ベクタ定義空間は例えば各軸が０〜１までの範囲で定義される二次元の空間であるとするが、ベクタ定義空間はこの形式に限定されるものではない。各軸が０〜１以外の範囲で定義されてもよいし、三次元の空間であってもよい。
【００１５】
本実施形態では、まず図１に従い描画制御用プリミティブを三角形とした場合を例に説明を行う。描画制御用プリミティブを三角形ではなく他の図形とする場合については後述する。
【００１６】
以下、図１の描画装置の各ブロックの詳細な動作およびブロック間を流れるデータの構造について、図面を参照して説明していく。
【００１７】
［モデル記憶部１］
モデル記憶部１には、ベクタデータ記憶部５に保存されているベクタデータをレンダリングしたい曲面と、曲面のどの位置にレンダリングしたいかを表す位置（ベクタデータ定義位置）とが保存されている。なお、保存されるデータはこれらのみに限定されない。レンダリングの際の視点の位置や視線方向を表すカメラパラメータや並行投影・投視投影のどちらで投影するかなど、グラフィックスの分野でレンダリングの際に一般的に用いられる他の情報がモデル記憶部１に格納されていてもよい。
【００１８】
［ベクタデータ記憶部５］
ベクタデータ記憶部５では、ラスタライズする図形のベクタデータが記憶されている。ベクタデータは、図形要素の種類、および図形要素を構成する各点の座標、および各点の接続関係などを有する。例えば、図２の図形のベクタデータは図３のようになる。図３では、直線あるいはパラメータ曲線の端点を黒丸で表し、パラメータ曲線の制御点を白丸で表している。本実施形態では、このようなベクタデータがあらかじめベクタデータ記憶部５に記憶されているものとする。
【００１９】
なお、ベクタデータは上記の形式に限定されるものではなく、色情報やアルファ値などのグラフィックスの分野において一般的に利用される他のデータを含んでもよい。
【００２０】
［描画用パラメータ算出部２］
描画用パラメータ算出部２は、曲面をスクリーンに投影した際に該曲面モデルが占めるピクセルごとに、ベクタ定義空間における位置座標、色情報及び透明度を含む描画用パラメータを算出する。ベクタ定義空間は、曲面とは独立してレンダリング対象のベクタデータを定義するとともにピクセルの属性値を決定するために参照される。
【００２１】
具体的には、描画用パラメータ算出部２では、ベクタデータ記憶部５に保存されているベクタデータをレンダリングする際に、モデル記憶部１から、曲面のデータ及びベクタデータをレンダリングする位置であるベクタデータ定義位置、さらに必要であればカメラパラメータや投影方法を読み込み、ラスタデータ生成部８で出力されるラスタデータの各ピクセルがベクタ定義空間のどの位置に対応するかを表すパラメータ、およびどのような色が定義されているかを算出する。これにより、各ピクセルのベクタ定義空間での位置座標（「対応位置」という）、各ピクセルの色情報、透明度などのピクセル属性情報が決定される。
【００２２】
なお本実施形態では、ベクタ定義空間との対応パラメータとして例えばテクスチャ座標を用いる。テクスチャ座標を利用する場合、グラフィックスの分野で一般的に用いられるテクスチャマッピングの手法を用いてベクタ定義空間との対応を計算し、ベクタ定義空間での位置を算出できる。
【００２３】
対応位置（例えばテクスチャ座標）、各ピクセルの色情報、および透明度をどのようにして算出するかについては、曲面をレンダリングする際のレンダリング方法と同様の方法で行うことができる。例えば、曲面を微細な三角形面の集合で近似し、各ピクセルの属性情報がどの三角形面で決定されるかを計算することで求めることが可能である。この計算方法は三角形面をレンダリングする際のピクセル属性情報の決定方法と同じであり、グラフィックスの分野では一般的な方法であるため説明は省略する。また、曲面からのピクセル属性情報の決定方法はこれに限るものではない。例えば、各ピクセルから、レンダリングする際の視線の方向に半直線を延ばし、曲面と半直線の交点部分の対応位置（例えばテクスチャ座標）、色情報、透明度などをピクセル属性情報とする方法も考えられる。また、この方法に限定するものでもなく、ピクセルごとにピクセル属性情報が算出可能な他の方法を用いてもよい。
【００２４】
またベクタ定義空間との対応情報は上記の形式に限定されるものではなく、グラフィックスの分野において一般的に利用される他のデータを用いるか、あるいは含んでもよい。また、例えば、あらかじめ決定される式にパラメータとして代入されるような、独自に定義した値であってもよい。また、曲率など曲面から算出されるパラメータを利用してこのパラメータを変更したものを含んでもよい。
【００２５】
［三角形データ生成部３］
三角形データ生成部３では、ベクタデータ記憶部１に保持されているベクタデータ（図３）が読み込まれ、その輪郭線を解析することによって三角形データを生成する処理が行われる。輪郭線解析の結果曲線と見なされた部分（以下、「曲線輪郭」とよぶ）は、始点・制御点・終点で三角形を生成する。なおこの時には、図１５（ｂ）の黒で塗りつぶされている領域にしめすように、三角形内部に定義されている曲線の凸領域のみが図形を構成する。また、ベクトルデータの輪郭線を追跡して制御点を除く点を出現順につないだ場合に出来る直線のみで構成される輪郭（以下、「直線輪郭」とよぶ）で定義される多角形から、その多角形の任意の１点を選択し、その１点と多角形の稜線で構成される三角形群を生成する。ベクタデータから三角形データを生成する方法については例えば上記特許文献２で示されている方法を用いることができる。しかしながら三角形データの生成方法はこれに限定される物ではなく、曲線輪郭は始点・制御点・終点で三角形を生成し、それと併せて、制御点を含むすべての点で定義される多角形から、その多角形の任意の１点を選択し、その１点と多角形の稜線で構成される三角形群を生成してもよい。この場合、曲線輪郭から構成される三角形は、図１５（ｂ）に示すように内部に定義されている曲線の凸領域が図形を表すものと、図１５（ａ）に示すように凹領域が図形を表すものの２種類で構成される。またこの場合、直線輪郭はベクトルデータの輪郭線を追跡してすべての点を出現順につないだ物と定義される。この時には、例えば上記特許文献１の方法を用いて生成することが出来る。三角形データは、上述したように、曲面が定義される空間とは独立した空間であって、独自の位置座標（本例ではテクスチャ座標）などでレンダリング対象のベクタデータが定義される空間であるベクタ定義空間に定義される。この場合、三角形データがベクタ定義空間にすべて含まれ、かつ個々の三角形が最も大きくなるように正規化を行う。例えば、三角形データ生成部３で生成された三角形データ群がすべて含まれ、かつ各辺がベクタ定義空間のいずれかの軸と平行な最小の長方形を考え、その長方形の縦横比を維持したまま、その長方形をベクタ定義空間に含まれる範囲で拡大した際の倍率で正規化する方法が考えられる。しかしながらこの方法に限定するものではなく、グラフィックスの分野で一般的な他の正規化方法を用いてもよい。
【００２６】
［三角形データ記憶部４］
三角形データ記憶部４には、三角形データ生成部３によって生成された三角形データが記憶される。
【００２７】
［描画属性制御情報算出部７］
描画属性制御情報算出部７は、三角形データ記憶部４に記憶された三角形データと、描画用パラメータ算出部２で算出された結果を参照し、ベクタデータが形成する閉領域に対応位置が含まれるかどうかを判断するための情報を算出する。この処理の流れを図４に示す。
【００２８】
最初のステップＳ２０１では、三角形データ生成部３で生成された、直線輪郭および曲線輪郭から生成される複数の三角形の集合である三角形データの中から、Ｓ２０１で一度も読み込まれていない三角形を１つ読み込む。次のステップＳ２０２では三角形データ、または三角形データの一部分が、描画用パラメータ算出部２で算出された対応位置を含むかを調べる。ここで、Ｓ２０１で読み込んだ三角形が直線輪郭から生成された三角形の場合、対応位置が三角形の内部に含まれていれば描画判定変数に１を加算する。一方、曲線輪郭から生成された三角形の場合、三角形データ生成部３での生成ルールによって処理が異なる。
【００２９】
第一の条件は、対応位置が三角形の内部に含まれていれば真というものであり、生成ルールによらず共通の条件である。
【００３０】
第二の条件は三角形データの生成ルールによって異なる。図１５（ｂ）に示すような、曲線の凸領域のみが図形を表すように構成された三角形の場合、曲線の凸領域に含まれていれば真となる。また、図１５（ｂ）に示すように内部に定義されている曲線の凸領域が図形を表すものと、図１５（ａ）に示すように凹領域が図形を表すものの2種類で構成されている場合、凸曲線（曲線の凸領域が図形を表す曲線）の凸領域、あるいは凹曲線（曲線の凹領域が図形を表す曲線）の凹領域に含まれていれば真となる。Ｓ２０３では、これらの２つの条件が真である場合に、描画判定変数に１を加算する。
【００３１】
Ｓ２０１〜Ｓ２０３を、三角形データがすべて判定されるまで繰り返すことにより、対応位置が、三角形データ、あるいは三角形データの一部に含まれると判定された回数が得られる。本実施形態では、これを描画判定変数とする。
【００３２】
例えば、三角形データが３つの直線輪郭から生成された三角形で構成されており、対応位置がそのうちの２つの三角形の内部に相当する場合、描画判定変数は２となる。また、ベクタデータが色情報やアルファ値などの情報を保持しており、必要であれば、併せて対応位置での色情報やアルファ値を算出してもよい。
【００３３】
［ラスタデータ生成部８］
ラスタデータ生成部８は、描画属性制御情報算出部７で算出された描画判定変数を参照し、すでに算出されているピクセル属性情報を用いて画面表示用のラスタデータに書き込みを行うかどうか、すなわち描画するか否かをピクセルごとに決定して出力する。描画判定変数が奇数である場合にのみ、ラスタデータにピクセルを書き込む。このとき、ベクタデータから算出された色情報やアルファ値があれば、すでに算出されているピクセル属性情報の色情報やアルファ値などの該当する部分をベクトルデータから算出された値で置き換える、またはすでに算出されているピクセル属性情報の色情報やアルファ値とブレンドするなどの処理を行ってもよい。描画判定変数が奇数であるとは、直線輪郭から生成された三角形データ、および曲線輪郭から生成された三角形データに定義されている曲線の図形内部側の領域をすべてラスタライズした場合に、そのピクセルが奇数回書き込まれるということと等しくなる。これを上記特許文献２で示されている、ステンシルデータの生成に置き換えて考えると、ステンシルデータのビット反転が奇数回行われ、０以外の値となり、図形内部と判定されることと等しくなる。図５の灰色部分（ハッチングにより示す）は偶数回書かれた部分であり、黒部分は奇数回書かれた部分となる。つまり、上記特許文献２のステンシルデータと同様の結果を得ることができる。
【００３４】
［ラスタデータ記憶部９］
ラスタデータ記憶部９には、ラスタデータ生成部８によって生成されたラスタデータが記憶される。
【００３５】
ラスタデータは、最終的に提示部１０に提示される解像度と同じ解像度をもつ画像データである。ただし、ラスタデータの構成はこの形式に限定されるものではなく、グラフィックスの分野において一般的に利用される他のデータを含んでもよい。
【００３６】
［提示部１０］
提示部１０は、ラスタデータ記憶部９に保持されているラスタデータをユーザに提示するためのディスプレイやプリンタなどで構成される。
【００３７】
［まとめ］
本実施形態における描画装置によれば、ベクタデータで表現された図形を曲面上に描画することができる。描画処理においては、図形を描画するために利用する三角形データをベクタ定義空間に維持する構成であることから、動的に図形の幾何形状が変化する場合であっても三角形データを作り直す必要がなく、高速に描画が行える。
【００３８】
（第１実施形態の変形例１）
第１実施形態ではベクタデータを三角形データに分割したが、三角形データ生成部３、三角形データ記憶部４を、それぞれ凸多角形データ生成部、凸多角形データ記憶部に変更して複数の異なる多角形（四点以上で構成される凸多角形データ）に分割してもよい。
【００３９】
［凸多角形データ生成部］
凸多角形データ生成部は、ベクタデータ記憶部５に保存されているベクタデータを、重なりを許し、三角形データ生成部３で生成される三角形群を構成する三角形の辺の数の合計よりも合計の辺の数が少なくなるような凸多角形群に分割する。例えば、三角形データ生成部３で生成された三角形群であり直線輪郭から生成されたいずれかの三角形のうち、同一平面上にあって、三角形を構成する稜線を共有し、かつマージしても凹多角形にならない三角形同士をマージ（併合）する。これにより生成される凸多角形に対し、上記の条件を満たす限りにおいてさらに別の三角形をマージする。同様に、凸多角形の組み合わせであっても上記条件を満たすならば、両者をマージする。
【００４０】
同一平面上にあるかどうかの判定は、マージできるかを判定する三角形同士、または凸多角形同士、または三角形と凸多角形の組み合わせの法線が同一の向きを指しているかで判断することができる。なお、法線は三角形または凸多角形を構成する任意の頂点を１点選び、その点から反時計回りに３点選んで、その三点で構成される２本の稜線を特定し、その２本の稜線の外積を計算することで求めることが可能である。また凹多角形であるかどうかは、例えば多角形内部側の角度がすべての角で１８０度未満であるかを調べればよい。この時の角度の求め方はグラフィックス分野で一般的な処理なので説明を省略する。しかし分割方法、同一平面にあるかどうかの判定方法、あるいは凹多角形であるかどうかの判定方法はこれに限定するものではなく、その他のグラフィックス分野で一般的な方法を用いてもよい。
【００４１】
［凸多角形データ記憶部］
凸多角形データ記憶部は、凸多角形データ生成部で生成された凸多角形データを記憶する。
【００４２】
変形例１の場合、描画属性制御情報算出部７では対応位置が多角形データの内部に含まれるかを調べることになる。典型的には、ある位置座標が三角形以上の凸多角形の内部に含まれるかどうかは、多角形の稜線と位置座標との外積を計算し、算出結果の値の符号を調べることで決定される。凸多角形に分割した場合、生成される凸多角形群の稜線数が三角形データの場合に比べて少なくなるため、描画属性制御情報算出部７の内外判定の処理コストが低くなる。しかし、図形の動的な変形によって多角形が凹多角形となった場合に、その多角形を凸多角形になるまで分割する必要がある。
【００４３】
［まとめ］
本変形例によれば、ベクタ図形を曲面上に描画する際に、第１実施形態よりもさらに高速にラスタライズを行うことができる。ただし、図形の動的な変形を行う場合には凸多角形データの修正が必要な場合がある。そのため、図形の動的な変形が必要な場合には第１実施形態の方法を用いるべきである。
【００４４】
（第１実施形態の変形例２）
第１実施形態では、描画属性制御情報算出部７で三角形データと対応位置との内外判定を行い、ラスタデータ生成部８で各ピクセルをラスタデータに書き込むかのみを判定してラスタデータを生成した。変形例２では、描画属性制御情報算出部７で内外判定の結果以外の情報をも同時に算出して出力し、ラスタデータ生成部８で書き込むと判定されたピクセルに対して、描画属性制御情報算出部７で算出した内外判定の結果以外の情報を用いて処理を加える部分が異なる。
【００４５】
［描画属性制御情報算出部７］
本変形例における描画属性制御情報算出部７では、描画判定変数の他に、ラスタデータ生成部８で処理を加えるための追加情報を算出する部分が異なる。
【００４６】
例えば、三角形データ記憶部４に保存されている三角形データを構成する稜線のうち、元のベクタデータの稜線を共有しているもの、または曲線を定義している三角形データの曲線から対応位置までの最短距離を求める。この処理は最短距離を算出することに限定されるものではなく、距離以外のグラフィックスの分野で利用されるパラメータを含んでもよい。また、必ず最短距離を求める必要があるわけではなく、最短距離以外のパラメータを最短距離に代えて利用してもよい。
【００４７】
［ラスタデータ生成部８］
本変形例におけるラスタデータ生成部８は、第１実施形態のラスタデータ生成部８の機能に加えて、描画属性制御情報算出部７で算出した追加情報をパラメータをとして、画像処理を加える部分を備える。例えば、描画属性制御情報算出部７で算出した最短距離が一定の値以下のピクセルのアルファ値に対して、０〜１の範囲に正規化した最短距離を保存する。なお、必ずしも０〜１に正規化する必要はない。また、前記したとおり追加情報は必ずしも最短距離である必要はない。
【００４８】
［まとめ］
本変形例によれば、正確なデータであるベクタデータを利用して、描画用のラスタデータに対して、図形のエッジ部分をぼかす、エッジに近づくにつれて色をブレンドする、などの効果を与えることができる。
【００４９】
（第２実施形態）「動的にベクタデータの変形が可能なレンダリング」
次に本発明の第２実施形態について説明する。
【００５０】
図６に第２実施形態における描画装置のブロック図を示す。この図からわかるように本実施形態の特徴は、第１実施形態の構成に対して、描画制御用プリミティブ補正部６を追加したことにある。
【００５１】
以下、第１実施形態と同様に描画制御用プリミティブが例えば三角形であるとして説明する。
【００５２】
第１実施形態では、三角形データ生成部３での生成を行う際に、ベクタ定義空間に三角形データができるだけ大きく定義されるように正規化を行った。第２実施形態では、これを描画制御用プリミティブ補正部６で補正することで、三角形データ記憶部４に記憶されているデータを変更することなく、動的な変形を可能とする。例えば、制御用プリミティブ補正部６が三角形データを縮小することにより、モデル記憶部１に保存されているベクタ定義位置を変更することなく、出力されるベクタデータを縮小させることができる。これは、三角形データ記憶部４を参照することで得られる三角形データに対してアフィン変換を行うことで可能である。また、回転や移動を行うことにより、それぞれベクタデータを回転、移動することもできる。これもグラフィックス分野で一般的であるアフィン変換を行うことで可能である。さらに、頂点単位での補正も同様に頂点を対象としたアフィン変換によって可能である。頂点単位での補正を行うことにより、モデル記憶部１に保存されているベクタ定義位置を変更することなく、ベクタデータを波打たせるなどといったエフェクトが可能となる。また、上記の変形を組み合わせて補正することも可能であるし、補正は上記の変形に限定されるものではなく、位相構造を崩さない限り、グラフィックス分野で一般的なベクタデータへの変形操作を行うことも可能である。
【００５３】
これらの補正を行うための拡大率や回転角度、移動量などのパラメータはモデルに付加されていてもよいし、マウスの移動量や数値による入力などによる外部からの入力であってもよい。また、別途補正用パラメータのみがデータとして与えられても良い。
【００５４】
第１実施形態の変形例１に示した凸多角形の場合にも補正の結果が凸多角形データである限り同様の処理が適用できる。
【００５５】
補正の結果、凹多角形になった場合、その凹多角形を凸多角形になるまで分割すればよい。例としては、凸多角形をいったん三角形の組に分割し、凸多角形データ生成部と同様の方法で凸多角形群にする方法がある。しかし凹多角形の凸多角形群への分割方法はこれに限定するものではなく、グラフィックス分野で一般的な他の方法を用いてもよい。
【００５６】
［まとめ］
本実施形態によれば、三角形データ記憶部に保存されているプリミティブを改編しないため、描画制御用プリミティブを再生成することなくベクタデータを変形させることができる。したがって処理が高速である。
【００５７】
（第２実施形態の変形例１）
図７は第２実施形態の変形例１のブロック図を示したものである。この図からわかるように、本変形例は第２実施形態に補正情報入力部１４を備えた部分が異なる。第２実施形態では、あらかじめ描画制御用プリミティブ補正部６に補正用のパラメータを与えていた。本変形例では、補正情報入力部１４によって外部から動的に入力が与えられ、そのつど補正が行われる。
【００５８】
［補正情報入力部１４］
補正情報入力部１４は、ユーザ操作による入力を常時または一定のサンプリング間隔で受け付けて、それらの入力値を補正用パラメータとして加工し、描画制御用プリミティブ補正部６に出力する。例えば、マウスの直前の位置と現在の位置との差分を計算し、それをあらかじめ決められた倍率と掛け合わせ、それを描画制御用プリミティブ補正部６で用いる拡大率とする。乗算する値を倍率ではなく角度とすれば回転角度にもなるし、任意の値を乗算することで移動量と考えることもできる。入力デバイスはマウスに限定するものでもないし、パラメータの利用方法も上記の物に限定するものではない。また、拡大率、回転角度、移動量の算出方法も上記の方法に限定するものではない。
【００５９】
［まとめ］
本変形例によれば、ユーザの入力に応じて、高速に変形したベクタデータを曲面上にレンダリングすることができる。
【００６０】
（第３実施形態）「アルファブレンド不要のアンチエイリアシング」
次に本発明の第３実施形態について説明する。
【００６１】
図８に第３実施形態に係る描画装置のブロック図を示す。この図からわかるように、本実施形態の特徴は、第２実施形態の構成に対して、描画属性制御情報一次記憶部１１、サンプリング点計算部１２、描画属性制御情報再計算部１３を追加したことにある。
【００６２】
図９に第３実施形態における処理の概略を示す。ステップＳ３０１およびＳ３０２は第１実施形態の方法と同じであり、描画属性制御情報算出部７で算出される描画判定変数をもとに、ラスタデータ生成部８で行われる描画可否の判定と同様の処理でピクセル単位の描画可否を判定する。Ｓ３０２以降が第１実施形態と異なり、第２実施形態では、Ｓ３０２の結果とＳ３０１の対応位置をもとにＳ３０４でサブピクセル精度の画像を生成し、これをＳ３０５でピクセル精度の画像になるように処理して提示部１０に出力する。このとき、Ｓ３０４でのサブピクセル精度の画像の生成方法と、Ｓ３０５の処理方法にＺソートなどの順序に依存するアルゴリズムを用いないで処理を行うことにより、アルファブレンド不要のアンチエイリアシングを実現する。
【００６３】
なお図８では、モデル記憶部１、ベクタデータ記憶部５、三角形データ記憶部４、描画属性制御情報一次記憶部１１を異なるブロックとして表記しているが、これらは単一のメモリ上にまとめて構成してもよいし、異なる複数のメモリ上に分割して構成してもよい。
【００６４】
［描画属性制御情報算出部７］
本実施形態の描画属性制御情報算出部７では、第１実施形態での描画属性制御情報算出部７の処理に加えて、算出された描画判定変数を参照し、ピクセルごとにそのピクセルが描画用のラスタデータに書き込まれるべきピクセルかどうかを判定する処理が行われる。判定方法は第１実施形態のラスタデータ生成部８で行っているものと同様であるが、これをそのまま出力用のラスタデータに書き込まず、さらにアンチエイリアシングの処理を行う点に特徴がある。
【００６５】
［描画属性制御情報一次記憶部１１］
描画属性制御情報一次記憶部１１では、描画属性制御情報算出部７で算出した描画の可否とその判定に用いた対応位置を、ピクセルを基準としてアクセス可能な形式で保存する。例えば、画像の色を保存するＲＧＢＡのいずれか、または複数の要素にまたがった形で保存する方法が考えられる。しかし、保存方法についてはこれに限定するものではない。他にも、画像の縦あるいは横を指定するインデックスと描画可否、対応位置をセットにして記憶する方法もある。また、この方法によらず、ピクセルを基準として描画可否、対応位置が一意に決まる方法であればよい。
【００６６】
［サンプリング点計算部１２］
図１０に示すように、描画属性制御情報一次記憶部１１に保存された描画の可否と対応位置を参照して、図形のエッジを表現するピクセルのサブピクセルに対し、サブピクセル精度で描画可否を決定するための対応位置を算出する。
【００６７】
まずステップＳ６０１では、描画属性制御情報一次記憶部１１に保存されている描画可否を参照し、そのピクセルが図形のエッジを表現しているかどうかを判定する。エッジを表現している場合にはサブピクセルに対応する対応位置を算出するＳ６０２へ遷移する。そうでない場合には、Ｓ６０３へ遷移し、サブピクセルの対応位置は元のピクセルの対応位置と同じ位置とする。
【００６８】
Ｓ６０１は描画属性制御情報再計算部１３での計算量を削減するためのものであり、必ずＳ６０１の判定を行う必要はない。判定を行わない場合には、すべての場合でＳ６０２に遷移させればよい。
【００６９】
本実施形態では、Ｓ６０２でのサブピクセルの対応位置は、隣接するピクセルに対応する対応位置と、図形のエッジを表現するピクセルに対応する対応位置との、対応位置の補間計算によって算出する。補間方法の一例としては、隣接するピクセルの対応位置との線形補間によって求める方法がある。しかしこの方法に限定するものではなく、曲面の曲率などを用いて非線形な補間を行ってもよいし、その他のグラフィックス分野で一般的な補間方法を用いてもよい。
【００７０】
［描画属性制御情報再計算部１３］
図１１に示すように、サンプリング点計算部１２で算出したサブピクセルごとの対応位置における描画可否を判定し、サブピクセル精度での描画可否を決定する。描画可否は、第１実施形態のラスタデータ生成部８で行っている、描画可否の判定をサブピクセル単位に行う方法で算出している。
【００７１】
入力は前記サンプリング点計算部１２で出力される、サブピクセルごとの対応位置である。Ｓ４０１では、各サブピクセルの対応位置を入力としてサブピクセルごとの描画判定変数を算出する。Ｓ４０２では、その結果をもとにサブピクセルの分割元のピクセルのどの程度が描画可になっているかを表すカバレッジデータを算出する。カバレッジデータは、そのピクセルに対応するサブピクセルの数と、書き込まれると判定されたサブピクセルの割合で決定される。図１２はＳ４０１、およびＳ４０２をより詳細にした図である。Ｓ４０１はＳ５０１〜Ｓ５０７までに対応し、Ｓ４０２はＳ５０８に対応する。
【００７２】
ただし、そのピクセルが図形のエッジを表現するピクセルではない場合は、サブピクセルごとの描画判定変数を算出する処理は行わず、そのピクセルのカバレッジデータは１とする。
【００７３】
［ラスタデータ生成部８］
本実施形態におけるラスタデータ生成部８では、描画属性制御情報再計算部１３で算出されたカバレッジデータと描画用パラメータ算出部２で算出したピクセル属性情報を入力としてサブピクセル精度のラスタデータを生成し、それを合成してピクセル精度のラスタデータを生成してラスタデータ記憶部９に保存する。カバレッジデータが１であるピクセルをラスタライズする場合、そのピクセルに含まれるすべてのサブピクセルに対して、今回ラスタライズされたピクセルのカラー値を割り当てる。一方、カバレッジデータが１より小さいピクセル、すなわち、図形のエッジ近傍のピクセルをラスタライズする場合、そのピクセルに含まれるサブピクセルのうちの一部に対して、今回ラスタライズされたピクセルのカラー値を割り当て、残りのサブピクセルについては、すでに割り当てられているカラー値をそのまま保存しておくようにする。なお、カラー値を割り当てるサブピクセルは、カバレッジの大きさに基づいて選択される。
【００７４】
サブピクセル精度のラスタデータが合成されることにより、ジャギーが除去された滑らかなラスタライズ結果が得られる。
【００７５】
［まとめ］
後述するように例えば上記特許文献１では、アンチエイリアシングのためにアルファブレンドを用いており、そのため、すべての図形をデプスソートし、奥に位置する図形から順番にラスタライズしなければならない。これに対し本実施形態の描画装置では処理コストの高いアルファブレンドを用いない構成であり高速にアンチエイリアシングすることが可能になる。
【００７６】
（第３実施形態の変形例１）
第３実施形態では、ラスタライズ後の図形のエッジ部分をサブピクセル精度で解析してカバレッジデータを生成し、それを用いてアンチエイリアシングを実現している。本変形例はカバレッジデータの生成方法が第３実施形態と異なる。具体的には、第１実施形態の変形例２の描画属性制御情報算出部７で求めた追加情報を、第３実施形態の描画属性制御情報再計算部１３で算出するカバレッジデータとして利用する部分が異なる。
【００７７】
ブロック図は第１実施形態の変形例２と第３実施形態のブロック図を組み合わせたものとなり、描画属性制御情報算出部７までが第１実施形態の変形例２のブロック図となり、それ以降に第２実施形態のブロック図の描画属性制御情報再計算部１３以降がつながる形となる。つまり、第１実施形態の変形例２のラスタデータ生成部８の前に、第３実施形態の描画属性制御情報再計算部１３を具備することを特徴とする。以下に、追加された第３実施形態の機能ブロックのうち、第３実施形態と機能の異なるものについて説明する。
【００７８】
［描画属性制御情報再計算部１３］
第１実施形態の変形例２の描画属性制御情報算出部７で算出された追加情報のうちある閾値以下の値を０〜１に正規化して出力する。閾値を超える場合は１として出力する。
【００７９】
［まとめ］
本変形例は第３実施形態のカバレッジデータ算出の方法が異なるものであり、第３実施形態と同様に、処理コストの高いアルファブレンドを用いないため、高速にアンチエイリアシングすることが可能になる。また、カバレッジデータの算出に正確なベクタデータを用いるため、より正確な結果が得られるが、描画属性制御情報算出部７で算出する追加情報の種類によっては、第３実施形態より処理コストが高くなる可能性がある。
【００８０】
以上説明したように、本発明の実施形態に係る描画装置によれば、曲面上に、図形を変形して描画したい場合でも、高速にラスタライズすることが可能になる。また、動的に図形の幾何形状が変化する場合であっても高速にラスタライズすることが可能になる。さらに、処理コストの高いアルファブレンドを用いることなく、高速にアンチエイリアシングすることが可能になる。
【００８１】
（比較例）
以下、本発明の実施形態との比較例として、特許文献１、２に記載された技術について説明する。
【００８２】
ベクタグラフィックスのラスタライズに要する演算コストを低減するため、ＧＰＵ（グラフィックスプロセッサユニット）が活用されていることについては既に述べた。ＧＰＵを利用して、図２に示すような、直線と曲線で構成される図形をラスタライズするための上記特許文献１の手法をまず説明する。
【００８３】
このラスタライズ手法のフローチャートを図１３に示す。この図から分かるように、上記特許文献１の手法の処理は、ＣＰＵによる前処理とＧＰＵによる主処理の大きく２段階の処理に分かれている。最初に、ＣＰＵによってベクタ形式の図形が三角形の集まりに分解され、その後、ＧＰＵによって各三角形がラスタライズされる。ＧＰＵの処理単位は三角形であり、図２のような直線と曲線を有する図形を直接扱うことができないため、このような２段階の処理に分かれている。
【００８４】
最初のステップＳ１０１では、ＨＤＤやＲＡＭなどの記憶媒体からベクタ形式のデータを読み込み、その輪郭線を解析する処理が行われる。例えば、図２の図形を表すベクタ形式のデータは、図３に示すような点と直線から構成されている。この図では、図形の直線あるいはパラメータ曲線の端点を黒丸で表し、パラメータ曲線の制御点を白丸で表している。ステップＳ１０１では、このようなベクタ形式のデータを解析して、図１４に示すような２種類の輪郭線データを生成する。
【００８５】
この比較例では、図１４（ａ）の輪郭線データを「直線輪郭」と表記し、図１４（ｂ）の輪郭線データを「曲線輪郭」と表記する。説明を分かりやすくするため、最初に図１４（ｂ）の曲線輪郭について説明する。
【００８６】
図２と図３、および図１４（ｂ）を見比べると分かるように、曲線輪郭は、パラメータ曲線の始点と終点、および制御点の３点を結ぶ三角形の集まりである。各三角形はパラメータ曲線に外接しており、曲線は必ず三角形の内部に存在する。
【００８７】
曲線輪郭は、図１５に示すような２種類に分類される。図１５（ａ）は曲線の凹領域が図形の内側にあるものであり、図１５（ｂ）は曲線の凸領域が図形の内側にあるものである。本明細書では、前者を「凹曲線輪郭」、後者を「凸曲線輪郭」と表記する。
【００８８】
次に図１４（ａ）の直線輪郭について説明する。図２と図３、および図１４（ａ）を見比べると分かるように、直線輪郭は、直線の始点と終点、および凸曲線輪郭の始点と終点、および凹曲線輪郭の始点と制御点と終点を、線分で結ぶことによって得られる多角形である。凸曲線輪郭では始点と終点の２点が結ばれるのに対して、凹曲線輪郭では始点と制御点、および終点の３点が順番に結ばれることに注意する。
【００８９】
図１４（ａ）から分かるように、直線輪郭を構成する多角形は１つとは限らない（この例では３つの多角形で構成される）。また、各多角形は自己交差や穴を含むことがある。
【００９０】
図１３のフローチャートの説明に戻る。ステップＳ１０２では、前のステップで生成された曲線輪郭に重なりがあるか調べる処理が行われる。その結果、重なりが見つかった場合はステップＳ１０３に進み、重なっている２つの三角形のうちの面積の大きい方を細分割する処理が行われる。
【００９１】
この処理の影響で直線輪郭にも変更が生じるため、次のステップＳ１０４では、直線輪郭を更新する処理が行われる。その後、ステップＳ１０２に戻って再び重なりがあるか調べ、重なりがなければステップＳ１０５に進む。曲線輪郭に重なりが残っている限り、ステップＳ１０２〜Ｓ１０４の処理が繰り返される。
【００９２】
例えば図１４（ｂ）の曲線輪郭の場合、ステップＳ１０２において三角形ａとｂ、および三角形ｃとｄが重なっていることが分かる。ステップＳ１０３では、三角形ａおよびｃが、それぞれ、図１６（ｂ）に示すような２つの三角形ａ０とａ１、およびｃ０とｃ１に細分割される。そしてステップＳ１０４では、図１６（ａ）に示すように直線輪郭を更新する処理が行われる。
【００９３】
ステップＳ１０５では、直線輪郭を構成する各多角形を三角形に分割する処理が行われる。例えば図１６（ａ）の３つの多角形は、図１７に示すような三角形の集まりに分割される。
【００９４】
以上（ステップＳ１０１〜Ｓ１０５）の処理は、すべてＣＰＵによる前処理として実行される。
【００９５】
ステップＳ１０６では、直線輪郭を構成する三角形（図１７）および曲線輪郭を構成する三角形（６（ｂ））が、ＧＰＵによってラスタライズされる。このとき、直線輪郭を構成する三角形については、図１８（ａ）に示すように、その三角形の内側にあるすべてのピクセルがラスタライズされる。
【００９６】
これに対して曲線輪郭を構成する三角形については、図１８（ｂ）に示すように、その三角形の内側にあるピクセルのうち、凹曲線輪郭の凹領域のみ、あるいは凸曲線輪郭の凸領域のみがラスタライズされる。
【００９７】
このようにして得られた直線輪郭と曲線輪郭のラスタライズ結果は、ＧＰＵ内部のフレームバッファに併せて記憶される。例えば、図１８（ａ）と図１８（ｂ）は、図１９に示すようなラスタデータとしてフレームバッファに記憶される。
【００９８】
従来のＧＰＵを利用したラスタライズ手法では、複数の三角形を用いて曲線を近似していたため、拡大したときに粗く見えてしまう問題があった。また、より滑らかにラスタライズするためには多数の三角形を用いて曲線の近似精度を上げるしかなく、記憶容量と処理コストの増大が避けられなかった。これに対して上記特許文献１の手法では、三角形単位ではなく、曲線近傍のピクセル単位に処理するため、解像度に依存せず常に滑らかに曲線をラスタライズすることができる。その上、記憶容量と処理コストも解像度に依存せず、常に少なくて済む。
【００９９】
しかし、上記特許文献１のラスタライズ手法には以下の２つの問題がある。
【０１００】
１つ目の問題は前処理のコストが高いことである。特に、図１３のステップＳ１０２の曲線輪郭の重複判定と、ステップＳ１０５の直線輪郭の三角形分割のコストが高い。
【０１０１】
前処理のコストは、図形の幾何形状が時間的に変化しない場合であれば大きな問題にはならない。一度前処理をしてしまえば、以降は再び前処理を行う必要はないからである。しかし、動的に図形の幾何形状が変化する場合は、その都度前処理をやり直さなければならず、ラスタライズ処理全体のボトルネックになることが多い。
【０１０２】
２つ目の問題は、アンチエイリアシングのためにアルファブレンドを用いていることである。ここでアンチエイリアシングとは、ラスタライズされた図形の輪郭線に現れるジャギー（階段状のギザギザ）を除去する処理のことである。また、アルファブレンドとはアルファ値と呼ばれる係数を用いて２つのピクセル値を半透明合成する処理のことである。
【０１０３】
広く知られているように、アルファブレンドを用いるためにはすべての図形をデプス値でソート（デプスソート）し、奥に位置する図形から順番にラスタライズしなければならない。デプスソートは非常にコストが高い処理であり、ラスタライズ処理全体のボトルネックになることが多い。
【０１０４】
上記特許文献２ではこれら２つの問題を解決する方法を提案している。
【０１０５】
上記特許文献２では、ベクタデータに含まれる直線および曲線の始点と終点を単純に線分で結ぶことによって得られる多角形を直線輪郭としている。例えば、図３のベクタデータから解析された直線輪郭は、図２０に示すような３つの多角形Ｐ０、Ｐ１、Ｐ２になる。曲線輪郭については、上記特許文献１と同様のものを用いている。
【０１０６】
得られた直線輪郭を構成する各多角形について、任意の１点が選択される。本明細書ではこの点を「ピボット」と表記する。そして次に、ピボットと、ピボットを含まないすべての連結する２点を結ぶ三角形を生成する。ここで連結する２点とは、多角形の辺によって結ばれている２つの点のことを意味する。
【０１０７】
例えば、図２０の３つの多角形Ｐ０、Ｐ１、Ｐ２において、それぞれ点０、２３、２８がピボットとして選択された場合、図２１に示すような三角形が生成される。三角形が重なっており、この図だけでは三角形の形状を把握することが難しいため、図２２に３つの多角形Ｐ０、Ｐ１、Ｐ２から生成された三角形を構成する３つの点の番号を示す。
【０１０８】
なお、図２２はあくまで説明を分かりやすくするための補足であり、三角形データそのものを表しているのではないことに注意する。実際の三角形データは、各三角形を構成する３点の位置座標、およびテクスチャ座標、および接続関係などを有する。
【０１０９】
次に、三角形内部のピクセルをラスタライズすることによってステンシルデータを生成する処理が行われる。なお、ステンシルデータは、最終的に提示する解像度と同じ解像度をもつ画像データである。
【０１１０】
まず、直線輪郭の三角形データおよび曲線輪郭の三角形データを読み込み、ラスタライズする。このとき、直線輪郭の三角形については、その三角形の内側にあるすべてのピクセルがラスタライズされ、これらのピクセル位置に対応するステンシルデータのピクセル値がビット反転される。
【０１１１】
一方、曲線輪郭の三角形については、その三角形の内側にあるピクセルのうち、曲線の凸領域に属するピクセルのみがラスタライズされ、これらのピクセル位置に対応するステンシルデータのピクセル値がビット反転される。
【０１１２】
結果として、図形の内部は奇数回ピクセル値がビット反転され、図形の外部は偶数回ピクセル値がビット反転される。
【０１１３】
上記の処理によって塗りつぶすピクセルが判断できるため、描画用のラスタデータの対応するピクセルを塗りつぶすことで描画結果を生成することができる。
【０１１４】
上記特許文献２では、直線輪郭の三角形分割などを行わないため、ベクタデータの頂点を移動しても三角形データの接続関係が変化しなければ三角形データの対応する頂点座標を書き換えるだけでよく、再度三角形データを作り直す必要はない。そのため、図形の幾何形状が動的に変化しても高速にラスタライズが可能である。
【０１１５】
また、描画用のラスタデータのサブピクセル精度の画像を用意し、カバレッジデータをもとにサブピクセルの一部に図形の色を割り当て、最終的な描画用のラスタデータを生成する際に合成することでアルファブレンドが不要なアンチエイリアシングを可能としている。
【０１１６】
しかし、上記特許文献１、２に記載された技術では、図形を曲面上にレンダリングしたい場合にそのまま適用することができない。
【０１１７】
一般に、多角形データを曲面上にレンダリングする場合、多角形データを微細な多角形データ群に分割することで元の多角形データ内に頂点を追加し、その頂点を移動することによって実現する。上記特許文献２の方法を利用してベクタデータを曲面上にレンダリングする場合にも、上記特許文献２で示される方法で生成された三角形データを再分割する必要がある。
【０１１８】
三角形データの再分割には様々な方法があるが、十分に曲面に沿っている、つまり曲面上にレンダリングされているといえる描画結果が得られるように再分割する方法の処理コストは高い。
【０１１９】
ベクタデータを描画するための三角形データを再分割してしまうため、図形の幾何形状が変化する場合には、その都度再分割処理をやり直す必要がある。このため、上記特許文献１の問題点であり、上記特許文献２の利点である、動的な図形の幾何形状の変化への対応も不可能となる。
【０１２０】
上述した本発明の実施形態によれば、上記の問題を回避し、ベクタ図形をラスタライズして曲面上に描画する場合であっても、再分割処理等による処理負担が増加することなく高速に描画処理を行うことのできる描画装置及び方法を提供できる。
【０１２１】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【０１２２】
【図１】描画制御用プリミティブを三角形データとした場合の第１実施形態に係る描画装置を示すブロック図
【図２】ベクタ形式の図形の例を示す図
【図３】ベクタデータの例を示す図
【図４】第１実施形態における描画属性制御情報算出部の処理手順を示すフローチャート
【図５】描画判定変数をもとに生成された領域の例を示す図
【図６】本発明の第２実施形態に係る描画装置を示すブロック図
【図７】本発明の第２実施形態の変形例１に係る描画装置を示すブロック図
【図８】第３実施形態に係る描画装置を示すブロック図
【図９】第３実施形態の処理の概要を示すフローチャート
【図１０】第３実施形態におけるサンプリング点計算部の処理手順を示すフローチャート
【図１１】第３実施形態における描画属性制御情報再計算部の処理手順を示すフローチャート
【図１２】第３実施形態における描画属性制御情報再計算部の処理手順の詳細を示すフローチャート
【図１３】比較例に係るラスタライズの処理手順を示すフローチャート
【図１４】直線輪郭と曲線輪郭の例を示す図
【図１５】曲線輪郭から生成される三角形と曲線輪郭で構成される図形の例を示す図
【図１６】細分割された曲線輪郭と、それに伴い更新された直線輪郭の例を示す図
【図１７】三角形分割された直線輪郭の例を示す図
【図１８】比較例によってラスタライズされた直線輪郭と曲線輪郭の例を示す図
【図１９】比較例によって生成されたラスタデータの例を示す図
【図２０】直線輪郭の例を示す図
【図２１】比較例によって直線輪郭から生成された三角形データの例を示す図
【図２２】比較例によって直線輪郭から生成された三角形の点番号の例を示す図
【符号の説明】
【０１２３】
１・・・モデル記憶部；
２・・・描画用パラメータ算出部；
３・・・三角形データ生成部；
４・・・三角形データ記憶部；
５・・・ベクタデータ記憶部；
６・・・描画制御用プリミティブ補正部；
７・・・描画属性制御情報算出部；
８・・・ラスタデータ生成部；
９・・・ラスタデータ記憶部；
１０・・・提示部；
１１・・・描画属性制御情報一次記憶部；
１２・・・サンプリング点計算部；
１３・・・描画属性制御情報再計算部；
１４・・・補正情報入力部
【図１】
2009301284.tif 000003
【図２】
2009301284.tif 000004
【図３】
2009301284.tif 000005
【図４】
2009301284.tif 000006
【図５】
2009301284.tif 000007
【図６】
2009301284.tif 000008
【図７】
2009301284.tif 000009
【図８】
2009301284.tif 000010
【図９】
2009301284.tif 000011
【図１０】
2009301284.tif 000012
【図１１】
2009301284.tif 000013
【図１２】
2009301284.tif 000014
【図１３】
2009301284.tif 000015
【図１４】
2009301284.tif 000016
【図１５】
2009301284.tif 000017
【図１６】
2009301284.tif 000018
【図１７】
2009301284.tif 000019
【図１８】
2009301284.tif 000020
【図１９】
2009301284.tif 000021
【図２０】
2009301284.tif 000022
【図２１】
2009301284.tif 000023
【図２２】
2009301284.tif 000024
【手続補正書】
【提出日】平成21年3月18日(2009.3.18)
【手続補正１】
【補正対象書類名】図面
【補正対象項目名】図１
【補正方法】変更
【補正の内容】
【図１】
2009301284.tif 000025