(57)【特許請求の範囲】
【請求項１】
ベクタ形式の図形データからラスタ形式の図形データを生成する描画装置において、
前記ベクタ形式の図形データから、三角形化した直線輪郭及び曲線輪郭の三角形データ生成手段と、
前記三角形データからステンシルデータを生成するステンシルデータ生成手段と、
前記ステンシルデータを参照してラスタ形式の図形データを生成するラスタデータ生成手段と、を具備し、
前記直線輪郭は、前記ベクタ形式の図形データに含まれる直線および曲線の始点と終点とを線分で結ぶことにより得られる多角形であり、
前記曲線輪郭は、前記ベクタ形式の図形データに含まれる曲線の始点と制御点と終点とを線分で結ぶことにより得られる三角形であり、
前記三角形データ生成手段は、前記直線輪郭を解析し、少なくとも１つの前記多角形を生成し、各々の前記多角形において、前記多角形の１つの頂点を三角形の共通の頂点として、この共通の頂点と他の全ての頂点を直線で結び、連結する２つの頂点が１つの三角形の辺となるように、前記直線輪郭を三角形化し、
前記ステンシルデータ生成手段は、前記直線輪郭の三角形の内部のピクセルの値をビット反転し、前記曲線輪郭の三角形の内部のピクセルのうち、曲線の凸領域に属するピクセルの値をビット反転することにより、前記ステンシルデータを生成することを特徴とする描画装置。
【請求項２】
請求項１に記載の描画装置において、
前記ベクタ形式の図形データを記憶するためのベクタデータ記憶手段と、
前記三角形データ生成手段によって生成された三角形データを記憶するための三角形データ記憶手段と、
前記ステンシルデータ生成手段によって生成されたステンシルデータを記憶するためのステンシルデータ記憶手段と、
前記ラスタデータ生成手段によって生成されたラスタ形式の図形データを記憶するためのラスタデータ記憶手段と、を更に具備することを特徴とする描画装置。
【請求項３】
請求項１または請求項２に記載の描画装置において、前記ラスタ形式の図形データを提示するための提示手段を更に具備することを特徴とする描画装置。
【請求項４】
請求項３に記載の描画装置において、前記ステンシルデータ生成手段は、前記複数の三角形の内部のステンシルデータ記憶手段に記憶されたピクセルの値をビット反転させ、前記曲線輪郭に基づいて生成された曲線の凸領域の属するステンシルデータ記憶手段に記憶されたピクセルの値をビット反転させることによりステンシルデータを生成することを特徴とする描画装置。
【請求項５】
請求項１から請求項４のいずれか１項に記載の描画装置において、前記曲線輪郭で定義される曲線はパラメータ曲線であることを特徴とする描画装置。
【請求項６】
請求項１から請求項５のいずれか１項に記載の描画装置において、前記ステンシルデータ生成手段は、ラスタライズされたピクセルのうち、前記ラスタ形式の図形データの解像度と同じ解像度をもつ画像データであるカバレッジデータが１より小さいピクセルのアルファ値に対して１より小さい値を割り当てることを特徴とする描画装置。
【請求項７】
請求項６に記載の描画装置において、前記ステンシルデータ生成手段から出力されたピクセルのアルファ値をカバレッジデータとして記憶するためのカバレッジデータ記憶手段を更に具備することを特徴とする描画装置。
【請求項８】
請求項７に記載の描画装置において、前記カバレッジデータ記憶手段に記憶されたカバレッジデータに基づいて、前記ラスタデータを合成するラスタデータ合成手段をさらに具備することを特徴とする描画装置。
【請求項９】
ベクタ形式の図形データからラスタ形式の図形データを生成する描画方法において、
三角形データ生成手段が、前記ベクタ形式の図形データから、三角形化した直線輪郭及び曲線輪郭の三角形データを生成し、
ステンシルデータ生成手段が、前記三角形データからステンシルデータを生成し、
ラスタデータ生成手段が、前記ステンシルデータを参照してラスタ形式の図形データを生成し、
前記直線輪郭は、前記ベクタ形式の図形データに含まれる直線および曲線の始点と終点を線分で結ぶことにより得られる多角形であり、
前記曲線輪郭は、前記ベクタ形式の図形データに含まれる曲線の始点と制御点と終点とを線分で結ぶことにより得られる三角形であり、
前記三角形データ生成手段は、前記直線輪郭の解析により、少なくとも１つの前記多角形を生成し、各々の前記多角形において、前記多角形の１つの頂点を三角形の共通の頂点として、この共通の頂点と他の全ての頂点を直線で結び、連結する２つの頂点が１つの三角形の辺となるように、前記直線輪郭を三角形化し、
前記ステンシルデータ生成手段は、前記直線輪郭の三角形の内部のピクセルの値をビット反転し、前記曲線輪郭の三角形の内部のピクセルのうち、曲線の凸領域に属するピクセルの値をビット反転することにより、前記ステンシルデータを生成することを特徴とする描画方法。
【請求項１０】
ベクタ形式の図形データからラスタ形式の図形データを生成するために、コンピュータを、
前記ベクタ形式の図形データから、三角形化した直線輪郭及び曲線輪郭の三角形データを生成する手段と、
前記三角形データからステンシルデータを生成する手段と、
前記ステンシルデータを参照してラスタ形式の図形データを生成する手段として機能させ、
前記直線輪郭は、前記ベクタ形式の図形データに含まれる直線および曲線の始点と終点を線分で結ぶことにより得られる多角形であり、
前記曲線輪郭は、前記ベクタ形式の図形データに含まれる曲線の始点と制御点と終点とを結ぶことにより得られる三角形であり、
前記三角形データを生成する手段は、前記直線輪郭の解析により、少なくとも１つの前記多角形を生成し、各々の前記多角形において、前記多角形の１つの頂点を三角形の共通の頂点として、この共通の頂点と他の全ての頂点を直線で結び、連結する２つの頂点が１つの三角形の辺となるように、前記直線輪郭を三角形化し、
前記ステンシルデータを生成する手段は、前記直線輪郭の三角形の内部のピクセルの値をビット反転し、前記曲線輪郭の三角形の内部のピクセルのうち、曲線の凸領域に属するピクセルの値をビット反転することにより、前記ステンシルデータを生成することを特徴とする描画プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、描画装置、描画方法及び描画プログラムなどの描画技術に関し、特にベクタ形式の図形データからラスタ形式の図形データを生成するための技術に関する。
【背景技術】
【０００２】
点や直線、曲線、四角形、楕円などの幾何学的な図形要素を組み合わせることによって構成される画像はベクタグラフィックスと呼ばれている。これに対し、点（ピクセルあるいはドット）の配列によって構成される画像はラスタグラフィックスと呼ばれている。
【０００３】
一般に、ディスプレイに表示される画像やプリンタで印刷される画像はラスタグラフィックスである。このため、これらの機器でベクタグラフィックスを扱う際には、ラスタグラフィクスへ変換する処理（すなわち、ラスタライズ）が必要になる。ラスタライズの処理コストは高く、複雑なベクタグラフィックスをラスタライズするためには高性能な計算機が必要とされる。
【０００４】
一方、ベクタグラフィックスは表示の都度、適切な解像度のラスタグラフィックスを生成することができるため、画像の拡大や縮小、変形によって輪郭線などの画質が損なわれることがない。そのため、イラストや図面などの輪郭線がはっきりした人工的な画像はベクタグラフィックスとして扱われることが多い。なお、写真などの自然画像はラスタグラフィックスとして扱われることが多い。
【０００５】
ベクタグラフィックスの最も身近な利用例として、フォントが知られている。初期のパーソナルコンピュータ（以下、「ＰＣ」と称する）ではＣＰＵ性能の制約からラスタ形式のフォント（ビットマップフォント）が使われていた。しかし、ビットマップフォントでは、解像度ごとにフォントデータを保持しなければならないので、多くの記憶容量を必要とする。
【０００６】
その後のＣＰＵ性能の向上に伴い、現在のＰＣでは、解像度に依存しないベクタ形式のフォント（アウトラインフォント）データを保持しておき、ディスプレイやプリンタに見合った適切な解像度のフォントをその都度生成することにより、少ない記憶容量で高品質なフォントを表示できるようになった。
【０００７】
しかし、携帯電話やカーナビゲーションシステムなどに内蔵されるＣＰＵは処理能力が比較的低い。そのため、ベクタグラフィックスのラスタライズに要する演算コストを低減することが課題になっている。
【０００８】
近年、この課題を解決するためにＧＰＵ（グラフィックスプロセッシングユニット）が活用されている。このＧＰＵを利用したラスタライズ手法では、複数の三角形を用いて曲線を近似している。このため、ラスタグラフィックスを拡大したときに、ラスタグラフィックスが粗く見えてしまう。また、ベクタグラフィックスをより滑らかにラスタライズするためには多数の三角形を用いて曲線の近似精度を上げる必要があるため、記憶容量と処理コストの増大が避けられない。ここで、例えば、ＧＰＵを利用して、ベクタグラフィックスをラスタライズするための手法が提案されている（非特許文献１参照）。非特許文献１のラスタライズ手法の処理は、ＣＰＵによる前処理とＧＰＵによる主処理との２段階の処理を含む。
【０００９】
この非特許文献１のラスタライズ手法では、ベクタグラフィックスを三角形単位ではなく、曲線近傍のピクセル単位に処理するため、解像度に依存せず常に滑らかに曲線をラスタライズすることができる。その上、記憶容量と処理コストも解像度に依存しないので、記憶容量と処理コストの増大の必要がなくなる。
【非特許文献１】C. Loop and J. Blinn, Resolution Independent Curve Rendering using Programmable Graphics Hardware, SIGGRAPH 2005.
【発明の開示】
【発明が解決しようとする課題】
【００１０】
しかし、非特許文献１のラスタライズ手法には以下の２つの問題がある。  
（１）前処理のコストが高い。前処理のコストは、図形の幾何形状が時間的に変化しない場合であれば大きな問題にはならない。一度前処理をしてしまえば、以降は再び前処理を行う必要はないからである。しかし、動的に図形の幾何形状が変化する場合は、その都度前処理をやり直さなければならないので、この前処理がラスタライズ処理全体のボトルネックになることが多い。
【００１１】
（２）アンチエイリアシングのためにアルファブレンドを用いている。「アンチエイリアシング」とは、ラスタライズされた図形の輪郭線に現れるジャギー（階段状のギザギザ）を除去する処理のことである。また、「アルファブレンド」とはアルファ値と呼ばれる係数を用いて２つのピクセル値を半透明合成する処理のことである。  
広く知られているように、アルファブレンドを用いるためにはすべての図形をデプス値でソート（デプスソート）し、奥に位置する図形から順番にラスタライズしなければならない。デプスソートは非常にコストが高い処理であり、ラスタライズ処理全体のボトルネックになることが多い。
【００１２】
本発明は、前処理コストを大幅に削減したラスタライズ技術とそれに加えてアルファブレンドを不要にしたアンチエイリアシング技術を提供することを目的とする。
【課題を解決するための手段】
【００１３】
本発明の実施の形態は、ベクタ形式の図形データからラスタ形式の図形データを生成する描画装置において、前記ベクタ形式の図形データから、三角形化した直線輪郭及び曲線輪郭の三角形データ生成手段と、前記三角形データからステンシルデータを生成するステンシルデータ生成手段と、前記ステンシルデータを参照してラスタ形式の図形データを生成するラスタデータ生成手段と、を具備することを特徴とする。更に、本発明の実施の形態は、前記ステンシルデータ生成手段から出力されたピクセルのアルファ値に基づいて、前記ラスタデータを合成するラスタデータ合成手段をさらに具備することを特徴とする。なお、本発明の実施の形態は、上記のような装置に限らず、方法或いはプログラムとしても成立する。
【発明の効果】
【００１４】
本発明によれば、動的に図形の幾何形状が変化する場合であっても高速にラスタライズすることが可能になる。また、処理コストの高いアルファブレンドを用いることなく、高速にアンチエイリアシングすることが可能になる。
【発明を実施するための最良の形態】
【００１５】
図面を参照して本発明の実施の形態を説明する。  
図１は、本発明の第１の実施形態に係る描画装置の概略構成を示すブロック図である。なお、図１には、各ブロックに対するデータの流れも示している。第１の実施形態では、前処理を不要にするラスタライズにおける凸曲線のみの処理について説明する。図１に示すように、本第１の実施形態に係る描画装置は、ベクタデータ記憶部１と、三角形データ生成部２と、三角形データ記憶部３と、ステンシルデータ生成部４と、ステンシルデータ記憶部５と、ラスタデータ生成部６と、ラスタデータ記憶部７と、提示部８を備えている。
【００１６】
上記の構成において、ベクタデータ記憶部１は、ベクタ形式の図形データを記憶する。
三角形データ生成部２は、前記ベクタデータ記憶部１に記憶されているベクタ形式の図形データを読み込んで、詳細は後述するように、三角形データを生成する。  
三角形データ記憶部３は、前記三角形データ生成部２によって生成された三角形データを記憶する。  
ステンシルデータ生成部４は、前記三角形データ記憶部３に記憶されている三角形データを読み込んで、ステンシルデータを生成する。  
ステンシルデータ記憶部５は、前記ステンシルデータ生成部４によって生成されたステンシルデータを記憶する。  
ラスタデータ生成部６は、前記ステンシルデータ記憶部５に保持されているステンシルデータを参照してラスタ形式のデータ（以下、「ラスタデータ」とも称する）を生成する。  
ラスタデータ記憶部７は、前記ラスタデータ生成部６によって生成されたラスタデータを記憶する。  
提示部８は、前記ラスタデータ記憶部７に保持されているラスタデータを提示する。
【００１７】
なお、図１では、ベクタデータ記憶部１および三角形データ記憶部３およびステンシルデータ記憶部５およびラスタデータ記憶部７を異なるブロックとして表記しているが、これらは単一のメモリ上にまとめて構成してもよいし、異なる複数のメモリ上に分割して構成してもよい。
【００１８】
以下、図２に示すようなベクタグラフィックスをラスタグラフィックスにラスタライズする場合について説明する。この場合において、本発明のラスタライズ手法を説明するに当って、理解を容易にするために、まず上記の非特許文献１に記載のラスタライズ手法についてその要点を説明する。
【００１９】
図３は、非特許文献１に記載のラスタライズ手法の処理の流れを示すフローチャートである。図３から分かるように、非特許文献１の手法の処理は、ＣＰＵによる前処理とＧＰＵによる主処理の大きく２段階の処理から成る。すなわち、最初に、ＣＰＵによってベクタ形式の図形が三角形の集まりに分解される。その後、ＧＰＵによって各三角形がラスタライズされる。この理由は、ＧＰＵの処理単位は三角形であり、図２のような直線と曲線で構成される図形を直接扱うことができないためである。
【００２０】
具体的には、まず、ＨＤＤやＲＡＭなどの記憶媒体からベクタ形式のデータ（以下、「ベクタデータ」とも称する）を読み込み、その輪郭線を解析する処理が行われる（ステップＳ１０１）。例えば、図２の図形を表すベクタ形式のデータは、図４に示すような点と直線から構成されている。図４では、図形の直線あるいはパラメータ曲線の端点を黒丸で表し、パラメータ曲線の制御点を白丸で表している。ステップＳ１０１では、このようなベクタ形式のデータを解析して、図５に示すような２種類の輪郭線データを生成する。なお、本明細書では、図５（ａ）の輪郭線データを「直線輪郭」、図５（ｂ）の輪郭線データを「曲線輪郭」と称する。
【００２１】
まず、図５（ｂ）の曲線輪郭について説明する。図２、図４および図５（ｂ）から、曲線輪郭は、パラメータ曲線の始点と終点、および制御点の３点を結ぶ三角形の集まりであることがわかる。ここで、各三角形はパラメータ曲線に外接しており、曲線は必ず三角形の内部に存在する。ここで、曲線輪郭は、図６に示すような２種類の曲線輪郭に分類される。図６（ａ）は曲線の凹領域が図形の内側にあるもの（以下、「凹曲線輪郭」と称する）であり、図６（ｂ）は曲線の凸領域が図形の内側にあるもの（以下、「凸曲線輪郭」と称する）である。
【００２２】
図５（ａ）の直線輪郭について説明する。図２、図４および図５（ａ）から、直線輪郭は、直線の始点と終点、および凸曲線輪郭の始点と終点、および凹曲線輪郭の始点と制御点と終点を、線分で結ぶことによって得られる多角形であることがわかる。凸曲線輪郭では始点と終点の２点が結ばれるのに対して、凹曲線輪郭では始点と制御点、および終点の３点が順番に結ばれる。なお、図５（ａ）から分かるように、直線輪郭を構成する多角形は１つとは限らない（この例では３つの多角形で構成される）。また、各多角形は自己交差や穴を含むことがある。
【００２３】
次に、ステップＳ１０１において、ベクタ形式のデータの輪郭線の解析が終了したら、生成された曲線輪郭に重なりがあるか調べる（ステップＳ１０２）。その結果、重なりが見つかった場合はステップＳ１０３に進み、重なっている２つの三角形のうちの面積の大きい方を細分割する処理が行われる（ステップＳ１０３）。この細分割処理の影響で直線輪郭にも変更が生じるため、直線輪郭を更新する（ステップＳ１０４）。その後、ステップＳ１０２に戻って再び重なりがあるか調べ、重なりがなければステップＳ１０５に進む。なお、曲線輪郭の重なりがなくなるまで、ステップＳ１０２〜Ｓ１０４の処理が繰り返される。  
具体的には、例えば図５（ｂ）の曲線輪郭の場合には、三角形ａとｂ、および三角形ｃとｄが重なっているので、三角形ａおよびｃが、それぞれ、図７（ｂ）に示すような２つの三角形ａ０とａ１、およびｃ０とｃ１に細分割される。そして、図７（ａ）に示すように直線輪郭が更新される。
【００２４】
次に、直線輪郭を構成する各多角形がそれぞれ複数の三角形に分割される。例えば図７（ａ）の３つの多角形は、図８に示すような三角形の集まりに分割される。
【００２５】
上記のステップＳ１０１〜Ｓ１０５の処理は、すべてＣＰＵによる前処理として実行される。
【００２６】
そして、直線輪郭を構成する三角形（図８）および曲線輪郭を構成する三角形（図７（ｂ））が、ＧＰＵによってラスタライズされる（ステップＳ１０６）。このとき、図９（ａ）に示すように、直線輪郭を構成する三角形の内側にあるすべてのピクセルがラスタライズされる。これに対して、図９（ｂ）に示すように、曲線輪郭を構成する三角形の内側にあるピクセルのうち、凹曲線輪郭の凹領域のみ、あるいは凸曲線輪郭の凸領域のみがラスタライズされる。  
上記のようにして得られた直線輪郭と曲線輪郭のラスタライズ結果は、ＧＰＵ内部のフレームバッファに併せて記憶される。例えば、図９（ａ）と図９（ｂ）に示すデータは、それぞれ図１０に示すようなラスタデータとしてフレームバッファに記憶される。
【００２７】
本発明では、ＣＰＵによる前処理を低減したことを特徴としている。以下、本発明の第１の実施形態に係る描画装置の各ブロックの詳細な動作（処理）およびブロック間を流れるデータの構造について、図面を参照して説明していく。
【００２８】
ベクタデータ記憶部１は、ラスタライズする図形のベクタデータを記憶している。ベクタデータは、図４で説明したように、図形要素の種類、および図形要素を構成する各点の座標、および各点の接続関係などから構成される。
【００２９】
例えば、図２の図形のベクタデータは、上記の説明と同様に、図４のようになる。図４では、直線あるいはパラメータ曲線の端点を黒丸で表し、パラメータ曲線の制御点を白丸で表している。
【００３０】
なお、第１の実施形態では、図４に示すようなベクタデータがあらかじめベクタデータ記憶部１に記憶されているものとする。なお、ベクタデータは上記の形式に限定されるものではなく、グラフィックスの分野において一般的に利用される他のデータを含んでもよい。
【００３１】
ベクタデータ記憶部１に保持されているベクタデータ（図４）は、三角形データ生成部２で読み込まれる。三角形データ生成部２は、読み込んだベクタデータの輪郭線を解析することによって三角形データを生成する。図１１は、三角形データ生成部２の処理の流れを示すフローチャートである。
【００３２】
まず、ベクタデータの直線輪郭が解析される。図５（ａ）に示す手法では、ベクタデータに含まれる直線の始点と終点、および凸曲線輪郭の始点と終点、および凹曲線輪郭の始点と制御点と終点を、線分で結ぶことによって得られる多角形を直線輪郭としている。  
これに対して、第１の実施形態における三角形データ生成部２では、制御点は無視して、ベクタデータに含まれる直線および曲線の始点と終点のみを線分で結ぶことによって得られる少なくとも１つの多角形を直線輪郭とする。例えば、図４のベクタデータから解析された直線輪郭として、図１２に示すような３つの多角形Ｐ０、Ｐ１、Ｐ２が得られる（以下、多角形は複数得られたものとして説明する）。
【００３３】
次に、直線輪郭の三角形化を行う（ステップＳ２０２）。具体的には、まず、ステップＳ２０１で得られた直線輪郭を構成する各多角形の複数の頂点のうち、任意の１つの頂点を選択する（本明細書では、この点を「ピボット」と称する）。そして、それぞれの多角形について、ピボットと、そのピボットを含む多角形における他の全ての頂点を直線で結び、連結する２つの頂点が１つの三角形の辺となるように、ピボットを１つの頂点とする複数の三角形を生成する。ここで連結する２つの頂点とは、多角形の辺によって結ばれている２つの頂点のことを意味する。
【００３４】
例えば、図１２において、３つの多角形Ｐ０、Ｐ１、Ｐ２について、それぞれ点０、２３、２８をピボットとして選択したものとすれば、図１３に示すような複数の三角形が生成される。図１３では、複数の三角形が互いに重なりあっており、この図だけでは三角形の形状を把握することが難しいので、便宜上、図１４に３つの多角形Ｐ０、Ｐ１、Ｐ２から生成された複数の三角形を構成する３つの頂点の番号を示す。  
しかし、図１４はあくまで説明を分かりやすくするための補足であり、三角形データそのものを表しているのではない。実際の三角形データは、各三角形を構成する３点の位置座標、およびテクスチャ座標、および接続関係などから構成される。
【００３５】
そして、ベクタデータの曲線輪郭が解析される（ステップＳ２０３）。この処理は、図５（ｂ）に示した処理と同様に、ベクタデータに含まれるパラメータ曲線の始点と終点、および制御点の３点を結ぶ三角形の集まりを曲線輪郭とする。
【００３６】
以上のような処理手順で生成された直線輪郭の三角形データ（図１３）と曲線輪郭の三角形データ（図５（ｂ））が、三角形データ生成部２から出力されて三角形データ記憶部３に記憶される。
【００３７】
なお、上記のステップＳ２０１とＳ２０２の処理を並列に進めるように構成して、直線輪郭を解析すると同時に三角形を生成しても構わない。  
上記したように、三角形データは、各三角形を構成する３点の位置座標、およびテクスチャ座標、および接続関係などから構成される。ただし、三角形データの構成はこの形式に限定されるものではなく、グラフィックスの分野において一般的に利用される他のデータを含んでもよい。
【００３８】
ステンシルデータ生成部４は、三角形データ記憶部３に保持されている三角形データを読み込み、三角形内部のピクセルをラスタライズすることによってステンシルデータを生成する。  
このステンシルデータは、最終的に提示部８に提示する解像度と同じ解像度をもつ画像データである。なお、ステンシルデータは、ステンシルデータ記憶部５に保持される。また、ステンシルデータの各ピクセルには数ビット程度の数値が割り当てられており、毎フレーム、すべての描画に先立って０に初期化される。
【００３９】
そして、ステンシルデータ生成部４は、三角形データ記憶部３から直線輪郭の三角形データ（図１３）および曲線輪郭の三角形データ（図５（ｂ））を読み込み、ラスタライズする。このとき、直線輪郭の三角形の内側にあるすべてのピクセルがラスタライズされる。ここで、ラスタライズは、図１３で示した全ての三角形について、その三角形の内部に位置するステンシルデータのピクセル値が各三角形についてビット反転される。  
例えば、図１３のすべての三角形についてビット反転描画した場合には、図１５に示すようなステンシルデータが得られる。図１５では、全ての三角形について、ビット反転処理が行われたピクセルのうち、ピクセル値が０以外である箇所を黒色で、ピクセル値が０である箇所を灰色で塗りつぶしている。図１５から分かるように、直線輪郭の内側にあるピクセル値は０以外、外側にあるピクセル値は０になっている。
【００４０】
曲線輪郭の三角形については、その三角形の内側にあるピクセルのうち、曲線の凸領域に属するピクセルのみがラスタライズされ、これらのピクセル位置に対応するステンシルデータのピクセル値がビット反転される。  
例えば、直線輪郭の三角形について図１５に示すようなステンシルデータが得られている場合に、図１６（ａ）に示すようなラスタライズされたステンシルデータが適用されて、曲線の凸領域に属するピクセル値がビット反転描画された場合に、図１６（ｂ）に示すようにステンシルデータが更新される。図１６（ｂ）から分かるように、最初に与えられた図１の図形の内側にあるピクセル値は０以外、外側にあるピクセル値は０になっている。
【００４１】
なお、三角形データをビット反転描画する処理には順序依存性はない。図１５および図１６では、最初に直線輪郭の三角形データをまとめて描画し、その後、曲線輪郭の三角形データをまとめて描画したが、すべての三角形を任意の順序で描画しても構わない。  
なお、ステンシルデータ記憶部５は、ステンシルデータ生成部４によって生成されたステンシルデータ（図１６（ｂ））を記憶する。
【００４２】
上記したように、ステンシルデータは、最終的に提示部８に提示される解像度と同じ解像度をもつ画像データである。ただし、ステンシルデータの構成はこの形式に限定されるものではなく、グラフィックスの分野において一般的に利用される他のデータを含んでもよい。
【００４３】
ラスタデータ生成部６は、ステンシルデータ記憶部５に保持されているステンシルデータを参照し、そのピクセル値が０以外である箇所（図１６（ｂ）において黒色で塗りつぶされている箇所）のみをラスタライズすることによって、ラスタデータを生成する。
【００４４】
このラスタデータは、最終的に提示部８に提示する解像度と同じ解像度をもつ画像データであり、ラスタデータ記憶部７に保持される。ラスタデータの各ピクセルには、複数の色成分（例えばＲＧＢＡ）ごとに数ビット程度の数値が割り当てられている。
【００４５】
図１７（ａ）に示すように、ラスタデータ生成部６は、図形全体を覆う２枚の三角形の内側にあるすべてのピクセルをラスタライズする。ただし、これらのピクセルのうち、実際にラスタデータ記憶部７に書き込まれるのは、対応するステンシルデータのピクセル値が０以外である箇所（図１７（ａ）において黒色で塗りつぶされている箇所）に限られる。この結果、ラスタデータ記憶部７には、図１７（ｂ）に示すようなラスタデータが書き込まれる。  
上記したように、ラスタデータは、最終的に提示部８に提示される解像度と同じ解像度をもつ画像データである。ただし、ラスタデータの構成はこの形式に限定されるものではなく、グラフィックスの分野において一般的に利用される他のデータを含んでもよい。
【００４６】
提示部８は、ラスタデータ記憶部７に保持されているラスデータをユーザに提示するためのディスプレイやプリンタなどで構成される。
【００４７】
第１の実施形態に係る描画装置によるラスタライズ手法の処理手順を図１８に示す。  
図１８に示すフローチャートを図３に示すフローチャートと比較すると、第１の実施形態に係る描画装置によれば、図３に示すようなＣＰＵによる前処理コストは、輪郭線の解析（ステップＳ３０１）のみであって、ステンシルデータの生成（ステップＳ３０２）とラスタデータの生成（ステップＳ３０３）の処理はＧＰＵで行うため、ＣＰＵによる前処理コストを大幅に削減することができる。従って、動的に図形の幾何形状が変化する場合であっても高速にラスタライズすることが可能になる。
【００４８】
次に、本発明の第２の実施形態について説明する。  
第２の実施形態に係る描画装置の構成は、図１の第１の実施形態における構成と同じであるので、図示及び詳細な説明は省略する。第２の実施形態が、第１の実施形態と異なる点は、三角形データ生成部２およびステンシルデータ生成部４の処理内容が異なることである。
【００４９】
図１２に示したように、第１の実施形態では、三角形データ生成部２は、ベクタデータに含まれる直線および曲線の始点と終点を単純に線分で結ぶことによって得られる多角形を直線輪郭としていた。  
これに対して第２の実施形態では、三角形データ生成部２は、図５（ａ）に示した手法と同様に、ベクタデータに含まれる直線の始点と終点、および凸曲線輪郭の始点と終点、および凹曲線輪郭の始点と制御点と終点を、線分で結ぶことによって得られる多角形を直線輪郭とする。
【００５０】
三角形データ生成部２は、この直線輪郭の解析による多角形に対して、第１の実施形態と同様にピボットを１つの頂点とする複数の三角形データを生成する。生成された三角形データの例を図１９に示す。  
なお、曲線輪郭の構成方法、および曲線輪郭から三角形データを生成する方法は第１の実施形態と同じである。
【００５１】
ステンシルデータ生成部４は、第１の実施形態と同様に、三角形データ記憶部３から直線輪郭の三角形データ（図１９）および曲線輪郭の三角形データ（図５（ｂ））を読み込み、ラスタライズする。このとき、直線輪郭の三角形については、各三角形の内側にあるすべてのピクセルがラスタライズされ、これらのピクセル位置に対応するステンシルデータのピクセル値がビット反転される。  
ここで、第２の実施形態では、図１９のすべての三角形をビット反転描画すると、図２０に示すようなステンシルデータが得られる。図２０では、１回以上ビット反転されたピクセルのうち、ピクセル値が０以外である箇所を黒色で、ピクセル値が０である箇所を灰色で塗りつぶしている。
【００５２】
図１６（ａ）に示したように、第１の実施形態では、ステンシルデータ生成部４は、曲線輪郭の三角形の内側にあるピクセルのうち、曲線の凸領域に属するピクセルのみがラスタライズしている。  
これに対して、第２の実施形態では、ステンシルデータ生成部４は、図２１（ａ）に示すように、曲線輪郭の三角形の内側にあるピクセルのうち、凹曲線輪郭の凹領域のみ、あるいは凸曲線輪郭の凸領域のみをラスタライズし、これらのピクセル位置に対応するステンシルデータのピクセル値をビット反転する。
【００５３】
例えば、すでに直線輪郭の三角形データがビット反転描画され、ステンシルデータが図２０のような状態になっているところに、図２１（ａ）に示すような曲線の凹領域あるいは凸領域に属するピクセル値がビット反転描画された場合、図２１（ｂ）に示すようにステンシルデータが更新される。図２１（ｂ）から分かるように、最初に与えられた図２の図形の内側にあるピクセル値は０以外、外側にあるピクセル値は０になっている。
【００５４】
なお、三角形データをビット反転描画する処理には順序依存性はない。図２０および図２１では、最初に直線輪郭の三角形データをまとめて描画し、その後、曲線輪郭の三角形データをまとめて描画したが、すべての三角形を任意の順序で描画しても構わない。
【００５５】
第２の実施形態に係る描画装置によるラスタライズ手法の処理手順は、ほぼ図１８に示す第１の実施形態のフローチャートと同じである。  
従って、第２の実施形態に係る描画装置によれば、第１の実施形態と同様に、前処理コストを大幅に削減することができるため、動的に図形の幾何形状が変化する場合であっても高速にラスタライズすることが可能になる。  
また、第２の実施形態は、第１の実施形態と直線輪郭の解析手法が異なり、図５に示す手法と同様な解析を行っているものの、図３に示すフローチャートにおける、曲線輪郭の細分割（ステップＳ１０３）と直線輪郭の更新（ステップＳ１０４）が不要になっていることは明らかであり、この点でも、前処理コストを大幅に削減することができる。
【００５６】
次に、本発明の第３の実施形態について説明する。  
図２２は、第３の実施形態に係る描画装置の概略構成を示すブロック図である。図２２から分かるように、第３の実施形態に係る描画装置は、第１の実施形態および第２の実施形態に係る描画装置に対してカバレッジデータ記憶部９およびラスタデータ合成部１０を追加している。
【００５７】
カバレッジデータ記憶部９は、ステンシルデータ生成部４から出力されたカバレッジデータを記憶する。  
このカバレッジデータは、最終的に提示部８に提示する解像度と同じ解像度をもつ画像データである。カバレッジデータの各ピクセルには数ビット程度の数値が割り当てられており、毎フレーム、すべての描画に先立って１に初期化される。
【００５８】
第３の実施形態では、ステンシルデータ生成部４は、ステンシルデータ記憶部５にビット反転描画する際に、併せて、カバレッジデータ記憶部９に保持されているカバレッジデータの対応するピクセル位置に対して、アルファ値を描画する機能を備えている。  
ステンシルデータ生成部４は、この機能を利用して、ラスタライズされたピクセルのうち、図形のエッジ近傍に位置するピクセルのアルファ値に対して１より小さい値を割り当て、そのアルファ値をカバレッジデータとしてカバレッジデータ記憶部９に出力する
ラスタデータ生成部６は、カバレッジデータ記憶部９に保持されているカバレッジデータを参照してサブピクセル精度のラスタデータを生成し、ラスタデータ記憶部７に出力する。  
そして、ラスタデータ生成部６は、カバレッジデータが１であるピクセルをラスタライズする場合、そのピクセルに含まれるすべてのサブピクセルに対して、今回ラスタライズされたピクセルのカラー値を割り当てる。
【００５９】
一方、カバレッジデータが１より小さいピクセル、すなわち、図形のエッジ近傍のピクセルをラスタライズする場合、そのピクセルに含まれるサブピクセルのうちの一部に対して、今回ラスタライズされたピクセルのカラー値を割り当て、残りのサブピクセルについては、すでに割り当てられているカラー値をそのまま保存しておくようにする。なお、カラー値を割り当てるサブピクセルは、カバレッジの大きさに基づいて選択される。
【００６０】
ラスタデータ記憶部７は、ラスタデータ生成部６によって生成されたサブピクセル精度のラスタデータ、およびラスタデータ合成部１０によって合成されたピクセル精度のラスタデータを記憶する。  
ラスタデータ合成部１０は、ラスタデータ記憶部７に保持されているサブピクセル精度のラスタデータを合成し、最終的に提示部８に提示される解像度と同じ解像度（ピクセル精度）のラスタデータに変換する。  
このように、サブピクセル精度のラスタデータが合成されることにより、ジャギーが除去された滑らかなラスタライズ結果が得られる。
【００６１】
上記したように、非特許文献１の手法ではアンチエイリアシングのためにアルファブレンドを用いていた。そのため、すべての図形をデプスソートし、奥に位置する図形から順番にラスタライズしなければならなかった。  
しかし、第３の実施形態に係る描画装置によれば、処理コストの高いアルファブレンドを用いないため、高速にアンチエイリアシングすることが可能になる。
【００６２】
第４の実施形態を説明する。  
上記の各実施形態では、基本的に、パラメータ曲線（例えば、２次ベジエ曲線）を含む図形について、ラスタライズを行う例を示している。第４の実施形態では、３次ベジエ曲線を含む図形であっても、上記のようなパラメータ曲線（例えば、２次ベジエ曲線）を含む図形と同様に扱えることを示す。なお、処理の手順は、第１の実施形態と同様であるので、図示は省略する。また、第１の実施形態と重複する説明についても、省略する。
【００６３】
図２３は、３次ベジエ曲線を含む図形の例を示す図である。図２３の図形は、図２４に示すようなベクタデータとしてベクタデータ記憶部１に記憶されているものとする。  
三角形データ生成部２は、第１の実施形態と同様に、図２４に示すベクタデータを解析して、図２５（ａ）に示す直線輪郭と、図２５（ｂ）に示す曲線輪郭を生成する。ここにおいて、図形の直線あるいはパラメータ曲線の端点を黒丸で表し、パラメータ曲線の制御点を白丸で表しているが、第４の実施形態では、パラメータ曲線の端点に対してパラメータ曲線の制御点が２点になっており、一方の制御点から対角方向に位置する端点とを結ぶように三角形が形成される。なお、曲線輪郭に対するラスタデータは、図２６（ａ）に示すような曲線によって決定されるが、図２６（ｂ）に示すような変曲点を有するような曲線で定義されるようなものであっても良い。
【００６４】
そして、三角形データ生成部２は、直線輪郭については、第１の実施形態と同様に、図２７に示すように、ピボット（図２７における０点）と、そのピボットを含む多角形における他の全ての頂点を直線で結び、連結する２つの頂点が１つの三角形の辺となるように、ピボットを１つの頂点とする複数の三角形を生成する。
【００６５】
ステンシルデータ生成部４は、三角形データ生成部２で作成した三角形データを、第１の実施形態と同様に、ラスタライズする。これにより、図２８による、ラスタライズされたステンシルデータが得られる。最終的に、ステンシルデータ生成部４は、第１の実施形態と同様に、直線輪郭による三角形データから得られたステンシルデータ（図２８）と、曲線輪郭による三角形データから得られたステンシルデータ（図２９（ａ））とにより、図２９（ｂ）に示すようなステンシルデータを生成する。そして、最終的に図３０（ａ）に示すような図形全体を覆う２枚の三角形の内側にあるすべてのピクセルをラスタライズする。ただし、これらのピクセルのうち、実際にラスタデータ記憶部7に書き込まれるのは、対応するステンシルデータのピクセル値が０以外である箇所（図３０（ａ）において黒色で塗りつぶされている箇所）に限られる。この結果、ラスタデータ記憶部７には、図３０（ｂ）に示すようなラスタデータが書き込まれる。なお、この場合の詳細な処理は、第１の実施形態と同様であるので、説明を省略する。
【００６６】
上記のように、本発明によれば、前処理コストを大幅に削減した新しいラスタライズ手法を提供している。この結果、動的に図形の幾何形状が変化する場合であっても高速にラスタライズすることが可能になった。  
さらに本発明によれば、アルファブレンドが不要な新しいアンチエイリアシング手法を提供している。この結果、処理コストの高いデプスソートが不要になり、高速にアンチエイリアシングすることが可能になった。
【００６７】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。  
例えば、上記の実施形態では、文字についてベクタ形式の図形データからラスタ形式の図形データを生成する場合を説明したが、他の図形、例えば地図データがベクタ形式で与えられている場合に、当該地図データからラスタ形式の図形データを生成する場合にももちろん適用可能である。  
また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【図面の簡単な説明】
【００６８】
【図１】本発明の第１の実施形態に係る描画装置の概略構成を示すブロック図である。
【図２】ベクタ形式の図形の一例を示す図である。
【図３】非特許文献１に記載のラスタライズ手法の処理の流れを示すフローチャートである。
【図４】ベクタデータの一例を示す図である。
【図５】直線輪郭と曲線輪郭の例を示す図である。
【図６】凸曲線輪郭と凹曲線輪郭の例を示す図である。
【図７】細分割された曲線輪郭と、それに伴い更新された直線輪郭の例を示す図である。
【図８】三角形分割された直線輪郭の例を示す図である。
【図９】ラスタライズされた直線輪郭と曲線輪郭の例を示す図である。
【図１０】生成されたラスタデータの例を示す図である。
【図１１】本発明の第１の実施形態において、三角形データ生成部２の処理手順を示すフローチャートである。
【図１２】本発明の第１の実施形態における直線輪郭の例を示す図である。
【図１３】本発明の第１の実施形態において直線輪郭から生成された三角形データの例を示す図である。
【図１４】本発明の第１の実施形態において直線輪郭から生成された三角形の点番号の例を示す図である。
【図１５】本発明の第１の実施形態において直線輪郭から生成された三角形のステンシルデータを生成する例を示す図である。
【図１６】本発明の第１の実施形態において曲線輪郭を表す三角形のステンシルデータを生成する例を示す図である。
【図１７】本発明の第１の実施形態においてラスタデータを生成する例を示す図である。
【図１８】本発明の第１の実施形態における処理手順を示すフローチャートである。
【図１９】本発明の第２の実施形態において直線輪郭から生成された三角形データの例を示す図である。
【図２０】本発明の第２の実施形態において直線輪郭から生成された三角形のステンシルデータを生成する例を示す図である。
【図２１】本発明の第２の実施形態において曲線輪郭を表す三角形のステンシルデータを生成する例を示す図である。
【図２２】本発明の第３の実施形態に係る描画装置の概略構成を示すブロック図である。
【図２３】本発明の第４の実施形態を説明するためのベクタ形式の図形の一例を示す図である。
【図２４】本発明の第４の実施形態において、直線輪郭と曲線輪郭の例を示す図である。
【図２５】本発明の第４の実施形態において、凸曲線輪郭と凹曲線輪郭の例を示す図である。
【図２６】３次のベジエ曲線における曲線輪郭の例を示す図である。
【図２７】本発明の第１の実施形態において直線輪郭から生成された三角形データの例を示す図である。
【図２８】本発明の第４の実施形態において直線輪郭から生成された三角形のステンシルデータを生成する例を示す図である。
【図２９】本発明の第４の実施形態において直線輪郭から生成された三角形のステンシルデータを生成する例を示す図である。
【図３０】本発明の第４の実施形態においてラスタデータを生成する例を示す図である。
【符号の説明】
【００６９】
１・・・ベクタデータ記憶部
２・・・三角形データ生成部
３・・・三角形データ記憶部
４・・・ステンシルデータ生成部
５・・・ステンシルデータ記憶部
６・・・ラスタデータ生成部
７・・・ラスタデータ記憶部
８・・・提示部
９・・・カバレッジデータ記憶部
１０・・・ラスタデータ合成部
【図１】
0004693660.tif 000002
【図２】
0004693660.tif 000003
【図３】
0004693660.tif 000004
【図４】
0004693660.tif 000005
【図５】
0004693660.tif 000006
【図６】
0004693660.tif 000007
【図７】
0004693660.tif 000008
【図８】
0004693660.tif 000009
【図９】
0004693660.tif 000010
【図１０】
0004693660.tif 000011
【図１１】
0004693660.tif 000012
【図１２】
0004693660.tif 000013
【図１３】
0004693660.tif 000014
【図１４】
0004693660.tif 000015
【図１５】
0004693660.tif 000016
【図１６】
0004693660.tif 000017
【図１７】
0004693660.tif 000018
【図１８】
0004693660.tif 000019
【図１９】
0004693660.tif 000020
【図２０】
0004693660.tif 000021
【図２１】
0004693660.tif 000022
【図２２】
0004693660.tif 000023
【図２３】
0004693660.tif 000024
【図２４】
0004693660.tif 000025
【図２５】
0004693660.tif 000026
【図２６】
0004693660.tif 000027
【図２７】
0004693660.tif 000028
【図２８】
0004693660.tif 000029
【図２９】
0004693660.tif 000030
【図３０】
0004693660.tif 000031