描画装置および方法
【課題】高速に描画処理を行う。
【解決手段】ベクタデータを輪郭線解析することにより直線輪郭および曲線輪郭のいずれか１以上に対応するデータを含むプリミティブデータを、曲面モデルが定義される空間と独立して図形を定義するとともに出力するラスタデータのピクセルの属性値を決定するために参照されるベクタ定義空間に生成する第１生成手段１０５と、曲面モデルに含まれる要素ごとに要素がベクタ定義空間のどの位置になるかを算出し、ベクタ定義空間で曲面モデルと図形に対応するデータとの関係を判定する第１判定手段１０２と、要素ごとに判定結果により、複数の要素から採用する要素を決定し、採用する要素を含む再定義曲面モデルを生成する第２生成手段１０３と、再定義曲面モデルとプリミティブデータとにより、出力するラスタデータのピクセルの属性値を生成する第３生成手段１０７と、を具備する。
【解決手段】ベクタデータを輪郭線解析することにより直線輪郭および曲線輪郭のいずれか１以上に対応するデータを含むプリミティブデータを、曲面モデルが定義される空間と独立して図形を定義するとともに出力するラスタデータのピクセルの属性値を決定するために参照されるベクタ定義空間に生成する第１生成手段１０５と、曲面モデルに含まれる要素ごとに要素がベクタ定義空間のどの位置になるかを算出し、ベクタ定義空間で曲面モデルと図形に対応するデータとの関係を判定する第１判定手段１０２と、要素ごとに判定結果により、複数の要素から採用する要素を決定し、採用する要素を含む再定義曲面モデルを生成する第２生成手段１０３と、再定義曲面モデルとプリミティブデータとにより、出力するラスタデータのピクセルの属性値を生成する第３生成手段１０７と、を具備する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、本発明はベクタ図形を描画する描画装置および方法に関する。
【背景技術】
【０００２】
点や直線、曲線、四角形、楕円などの幾何学的な図形要素を組み合わせることによって構成される画像のことをベクタグラフィックスと呼ぶ。これに対し、点（ピクセルあるいはドット）の配列によって構成される画像のことをラスタグラフィックスと呼ぶ。
【０００３】
一般に、ディスプレイに表示される画像やプリンタで印刷される画像はラスタグラフィックスである。これらの機器でベクタグラフィックスを扱う際には、これをラスタグラフィクスへ変換する処理（ラスタライズ）が必要になる。ラスタライズの処理コストは高く、複雑なベクタグラフィックスを高速にラスタライズするためには高性能な計算機が必要とされる。その反面、ベクタグラフィックスは表示の都度、適切な解像度のラスタグラフィックスを生成することができるため、画像の拡大や縮小、変形によって輪郭線などの画質が損なわれることがない。そのため、イラストや図面などの輪郭線が明瞭な人工的な画像はベクタグラフィックスとして扱われることが多い。一方、写真などの自然画像はラスタグラフィックスとして扱われることが多い。
【０００４】
ベクタグラフィックスの最も身近な利用例はフォントである。初期の計算機ではＣＰＵ性能の制約からラスタ形式のフォント（ビットマップフォント）が使われているが、解像度ごとにフォントデータを保持しなければならなかったため多くの記憶容量を必要としている。その後のＣＰＵ性能の向上に伴い、現在の計算機では、解像度に依存しないベクタ形式のフォント（アウトラインフォント）データを保持しておき、ディスプレイやプリンタに見合った適切な解像度のフォントをその都度生成することにより、少ない記憶容量で常に高品質なフォントを表示できる。しかし現在でも、携帯電話やカーナビゲーションシステムなどに内蔵されるＣＰＵは処理能力が比較的低く、ベクタグラフィックスのラスタライズに要する演算コストを低減することが課題になっている。
【０００５】
近年、この課題を解決するためにＧＰＵ（グラフィックスプロセッサユニット）が活用されている。ＧＰＵを利用し、直線と曲線で構成される図形をラスタライズするための手法が既に提案されている（例えば、特許文献１参照）。
【０００６】
また、図形の幾何形状が動的に変化しても高速にラスタライズが可能な手法も公知である（例えば、特許文献２参照）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００６−１０６７０５号公報
【特許文献２】特開２００７−２４１８７８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、ベクタ図形を曲面上に描画する場合には、処理の負担が増大し高速に描画処理を行うことができない問題がある。
本発明は、ベクタ図形を曲面上に描画する場合であっても、再分割処理等による処理負担の増加を低減し高速に描画処理を行うことのできる描画装置および方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述の課題を解決するため、本発明に係る描画装置は、ベクタ形式の図形に対応するベクタデータを記憶している第１記憶手段と、前記図形を描画するガイドとしての曲面モデルと、該曲面モデルに対応する、前記ベクタデータがレンダリングされることが可能な領域を示すベクタデータ定義位置とを記憶する第２記憶手段と、前記ベクタデータを輪郭線解析することにより直線輪郭および曲線輪郭のいずれか１以上に対応するデータを含むプリミティブデータを、前記曲面モデルが定義される空間と独立して前記図形を定義するとともに出力するラスタデータのピクセルの属性値を決定するために参照されるベクタ定義空間に生成する第１生成手段と、前記曲面モデルに含まれる要素ごとに、該要素が前記ベクタ定義空間のどの位置になるかを算出し、ベクタ定義空間で曲面モデルと前記図形に対応するデータとの関係を判定する第１判定手段と、前記要素ごとに前記第１判定手段の判定結果を参照して、前記複数の要素から採用する要素を決定し、採用する要素を含む再定義曲面モデルを生成する第２生成手段と、前記再定義曲面モデルと前記プリミティブデータとを参照して、出力するラスタデータのピクセルの属性値を生成する第３生成手段と、を具備することを特徴とする。
【発明の効果】
【００１０】
本発明の描画装置および方法によれば、再分割処理等による処理負担の増加を低減し高速に描画処理を行うことができる。
【図面の簡単な説明】
【００１１】
【図１】本実施形態に係る描画装置を示すブロック図。
【図２】ベクタ図形の一例を示す図。
【図３】ベクタデータ図形の一例を示す図。
【図４】三角形のうち、凸領域が図形を表す場合（（ａ））と、凹領域が図形を表す場合（（ｂ））を示す図。
【図５】直線輪郭（（ａ））と曲線輪郭から定義される三角形の集合（（ｂ））の一例を示す図。
【図６】描画制御用プリミティブの１つがある曲面モデル要素と交差している状態（（ａ））、またはある曲面モデル要素がある描画制御用プリミティブに含まれている状態（（ｂ））を示す図。
【図７】図１の出力ラスタデータ生成部を示すブロック図。
【図８】図１のモデル制御情報算出部の動作の一例を示すフローチャート。
【図９Ａ】図１の入力モデル制御部の処理前の文字のイメージを示す図。
【図９Ｂ】図１の入力モデル制御部の処理後の文字のイメージの一例を示す図。
【図９Ｃ】図１の入力モデル制御部の処理後の文字のイメージの別例を示す図。
【図１０】比較例におけるラスタライズの処理手順を示すフローチャート。
【図１１】細分割された曲線輪郭から定義される三角形の集合（（ｂ））と、それに伴い更新された直線輪郭（（ａ））の一例を示す図。
【図１２】三角形分割された直線輪郭の一例を示す図。
【図１３】比較例におけるラスタライズされた直線輪郭（（ａ））および曲線輪郭から定義される三角形の集合（（ｂ））の一例を示す図。
【図１４】比較例における生成されたラスタデータの一例を示す図。
【図１５】直線輪郭の一例を示す図。
【図１６】比較例における直線輪郭から生成された三角形データの一例を示す図。
【図１７】比較例における直線輪郭から生成された三角形の点番号の一例を示す図。
【発明を実施するための形態】
【００１２】
以下、図面を参照しながら本発明の実施形態に係る描画装置および方法について詳細に説明する。
本実施形態に係る描画装置の構成について図１を参照して詳細に説明する。
本実施形態に係る描画装置１００は、モデル記憶部１０１、モデル制御情報算出部１０２、入力モデル制御部１０３、ベクタデータ記憶部１０４、描画制御用プリミティブ生成部１０５、描画制御用プリミティブ記憶部１０６、出力ラスタデータ生成部１０７、および提示部１０８を含む。
ベクタデータ記憶部１０４は、任意の図形を表すベクタ形式の図形データであるベクタデータを記憶している。描画制御用プリミティブ生成部１０５は、所望のベクタ図形に対応するベクタデータを読み込み、ベクタデータを描画するために利用する描画制御用プリミティブデータをベクタ定義空間に生成し、描画制御用プリミティブデータを描画制御用プリミティブ記憶部１０６に記憶する。
【００１３】
モデル記憶部１０１は、曲面モデル（複数の曲面モデル要素）とベクタデータ定義位置とを対応付けて記憶している。モデル制御情報算出部１０２は、モデル記憶部１０１から所望の曲面モデルを抽出し、描画制御用プリミティブ記憶部１０６から所望の描画制御用プリミティブデータを抽出し、曲面モデル要素ごとに出力ラスタデータ生成部１０７へ描画制御用プリミティブデータを出力するかどうかの判定結果を示すモデル制御情報を算出する。入力モデル制御部１０３は、モデル制御情報と、モデル制御情報算出部１０２が受け取ったものと同じ曲面モデルおよびベクタデータ定義位置とを受け取り、出力ラスタデータ生成部１０７へ出力してレンダリングする曲面モデルを再定義曲面モデルと再定義する。ここで、要素とは曲面モデルを構成する多角形を指し、例えば三角形や長方形を用いる事ができる。
【００１４】
出力ラスタデータ生成部１０７は、入力モデル制御部１０３から取得した再定義曲面モデルに対応する描画制御用プリミティブデータを受け取り、入力モデル制御部１０３から再定義曲面モデルを受け取り、再定義曲面モデルと描画制御用プリミティブデータとから最終的な出力とするラスタデータを生成して提示部１０８へ送る。提示部１０８は受け取ったラスタデータをスクリーンに表示する。
【００１５】
［ベクタデータ記憶部１０４］
ベクタデータ記憶部１０４は、１種類以上のベクタ図形に対応する１以上のベクタデータを記憶している。ベクタデータは、ラスタライズされる任意のベクタ形式の図形（ベクタ図形と呼ぶ。ベクタ図形の一例を図２に示す）を表すベクタ形式の図形データであり、ラスタライズされる領域を含む任意の図形を示す、始点、制御点、および終点の座標と、ベクタ図形の種類（例えばフォント、絵）と、ベクタ図形を構成する各点（始点、制御点、および終点）の接続関係内部のラスタライズされる領域を示す情報とを含む。また、直線および曲線のどちら側を図形の内部とするかの情報を直線および曲線ごと定義していなくとも、直線および曲線のどちら側を内部領域とするかをあらかじめ決めておけばベクタデータの輪郭線解析と同時に内部領域を定義することができる。ベクタ図形の一例を図２に示し、図２のベクタ図形に対応するベクタデータに含まれる各点と各点との接続関係を図３に示す。
なお、ベクタデータは上記の形式に限定されるものではなく、色情報やアルファ値などのグラフィックスの分野において一般的に利用される他のデータを含んでもよい。
【００１６】
［描画制御用プリミティブ生成部１０５］
描画制御用プリミティブ生成部１０５は、ベクタデータ記憶部１０４に記憶されているベクタデータを参照して、描画を行うベクタデータを抽出し、抽出したベクタデータから描画制御用プリミティブデータをベクタ定義空間に少なくとも１つ生成する。ベクタ定義空間は、曲面モデルが定義される空間とは独立した空間であって、独自の位置座標（またはテクスチャ座標）などでレンダリング対象のベクタデータが定義される空間のうちのある範囲で定義されるものである。ベクタ定義空間は、例えば各軸が０から１までの範囲で定義される２次元空間である。また、ベクタ定義空間は、後述する出力ラスタデータ生成部１０７が出力するラスタデータのピクセルの属性値を決定するために参照される空間である。ピクセルの属性値とは、ベクタ定義空間での位置座標、各ピクセルの色情報、および透明度などを示す通常複数の値である。ラスタデータは、最終的に提示部１０８に提示される画像の解像度と同じ解像度をもつ画像データである。曲面モデルについては後述のモデル記憶部１０１において詳細に説明する。
描画制御用プリミティブデータとは、ベクタデータを曲面モデルに描画するために利用するデータであり、例えば三角形、凸多角形を形成する点座標およびある点座標を結ぶ線を含むデータである。また、描画制御用プリミティブデータが表す描画制御用プリミティブは、ベクタデータの始点、制御点、および終点を解析することによって生成される図形であり、例えば三角形群が挙げられるが、他にも凸多角形群を含む場合もある。なお、本実施形態では描画制御用プリミティブが三角形群と多角形群を含んでいる場合を例に説明を行う。図３では、図形の直線あるいはパラメトリック曲線の端点を黒丸で表し、パラメトリック曲線の制御点を白丸で表している。
描画制御用プリミティブ生成部１０５は、ベクタデータを輪郭線解析した結果、曲線輪郭（例えば図５（ｂ））と直線輪郭（例えば図１５）とに対応するデータを含む描画制御用プリミティブデータを生成する。描画制御用プリミティブデータは、ベクタ図形を再現する上でベクタデータと等価である。曲線輪郭から生成される描画制御用プリミティブは、曲線輪郭のパラメトリック曲線の始点と終点、および制御点の３点を結んで定義される多角形（ここでは三角形）の集合である。各三角形はパラメトリック曲線に外接しており、曲線は必ず三角形の内部に存在する。図３の例では、図３に含まれる始点と終点、および制御点の３点を結んで定義される三角形の集合である。また、曲線輪郭から定義される三角形は、図４（ｂ）に示すように内部に定義されている曲線の凸領域を表すもの（凸曲線輪郭と称する）と、図４（ａ）に示すように凹領域を表すもの（凹曲線輪郭と称する）の２種類で構成される。なお、曲線輪郭から定義される三角形については、三角形の内側にあるピクセルのうち、曲線の凸領域に属するピクセルのみがラスタライズされる。
【００１７】
直線輪郭は、制御点を無視してベクタデータに含まれる直線および曲線の始点と終点を線分で結ぶことによって得られる多角形と定義される。この直線輪郭は、例えば具体的には後述する図１５に示す図形となる。さらにこの直線輪郭について三角化を行う。具体的には直線輪郭を構成する多角形の複数の頂点のうち、任意の１つの頂点（ピボットという）を選択する。そして、ピボットと他の全ての頂点を直線で結び、連結する２つの頂点が１つの三角形の辺となるように、ピボットを１つの頂点とする複数の三角形を生成する。これら複数の三角形を直線輪郭から生成される描画制御用プリミティブとする。ここで連結する２つの頂点とは、多角形の辺によって結ばれている２つの頂点のことを意味する。
このようにベクタデータから描画制御用プリミティブデータを生成するより詳しい方法は例えば上記特開２００７−２４１８７８号公報で示されているため、ここでの詳細な説明は省略する。
【００１８】
しかしながら、描画制御用プリミティブデータの生成方法はこれに限定されるものではなく、例えば、曲線輪郭から定義される三角形は、上述したように凹曲線輪郭と、凸曲線輪郭の２種類で構成される。直線輪郭は、例えばこの２種類の曲線輪郭に応じて定義されてもよい。この場合、直線輪郭は、凸曲線輪郭では制御点を無視して始点と終点との２点を結び、凹曲線輪郭では始点と制御点と終点との３点をこの順番に結び、これらの線分を連結して得られる多角形の輪郭の集合である。このように結んだ直線輪郭の例としては、図５（ａ）が挙げられる。図５（ａ）から分かるように、直線輪郭を構成する多角形は１つとは限らない（この例では３つの多角形で構成される）。また、各多角形は自己交差や穴を含むことがある。
この場合、図形（例えば三角形）の内部のラスタライズされる領域を示す情報は、例えば２種類の上述した曲線輪郭で決定される。この２種類の曲線輪郭によって、始点、制御点、および終点で決まる曲線で区切られる、三角形内部の領域のうち、どちらの領域がラスタライズされる領域であるかを示すことができる。
【００１９】
描画制御用プリミティブデータは、上述したように、ベクタ定義空間に定義される。この場合、描画制御用プリミティブデータがベクタ定義空間が定義される範囲に全て含まれ、かつ三角形群を覆う最小の矩形が最も大きくなるように三角形の正規化を行う。具体的には、矩形が描画制御用プリミティブを全て覆う最小の長方形であり、各辺がベクタ定義空間のいずれかの軸と平行で、なおかつ２辺が垂直に交差している長方形であって、その長方形の２辺のうち長い方の辺がベクタ定義空間に収まる最も長い長さになるように拡大するさいの倍率を決定したうえで、その長方形の縦横比を維持したまま拡大し、正規化することができる。この手法とは異なり、例えば、描画制御用プリミティブ生成部１０５で生成された描画制御用プリミティブデータがベクタ定義空間に全て含まれ、かつ矩形の各辺がベクタ定義空間のいずれかの軸と平行な最小の長方形を考え、その長方形の縦横比を維持したまま、その長方形をベクタ定義空間に含まれる範囲で拡大した際の倍率で正規化することもできる。しかしながらこの方法に限定するものではなく、グラフィックスの分野で一般的な他の正規化方法を用いてもよい。
【００２０】
［描画制御用プリミティブ記憶部１０６］
描画制御用プリミティブ記憶部１０６は、描画制御用プリミティブ生成部１０５から描画制御用プリミティブデータを受け取って記憶する。
【００２１】
［モデル記憶部１０１］
モデル記憶部１０１は、各頂点にパラメータを含む複数の曲面モデル要素を含む曲面モデルと、この曲面モデルに対応するベクタデータ定義位置とを記憶している。曲面モデル要素は、辺の数が３以上で構成される多角形で示され、例えば三角形である。複数の曲面モデル要素の集合によって曲面モデルを表現する。ベクタデータ定義位置は、プリミティブデータに基づいてベクタ図形を再現するために曲面モデルのどの位置にベクタデータをレンダリングするかを示す。すなわち、ベクタデータ定義位置は、ベクタ定義空間で定義された領域が曲面モデルのどの領域にレンダリングされるかを示す。ここでの曲面モデルは、ベクタ図形を描画するガイドとして使用される。また、モデル記憶部１０１には、曲面モデル要素により構成される曲面モデルが複数記憶されていてもよい。
【００２２】
この曲面モデル要素の各頂点には、ベクタ定義空間での対応位置を示すパラメータが定義されているものとする。このパラメータは例えば、テクスチャ座標の利用が考えられる。このパラメータにより、曲面が表される空間における曲面モデル要素の位置座標と、ベクタ定義空間におけるベクタデータ定義位置とが対応しているため、ベクタ定義空間における曲面モデル要素（ここでは三角形）を定義することができ、ベクタ定義空間にあるレンダリング対象のベクタデータと曲面モデル要素とのベクタ定義空間での位置関係を容易に判定することができる。さらに、曲面モデル要素が三角形の場合には、三角形を生成する３頂点によってある曲面モデル要素の法線ベクトルを決定することができる。
【００２３】
なお、保存されるデータはこれらのみに限定されない。レンダリングの際の視点の位置や視線方向を表すカメラパラメータや並行投影または投視投影のどちらで投影するかなど、グラフィックスの分野でレンダリングの際に一般的に用いられる他の情報がモデル記憶部１０１に記憶されていてもよい。この場合、曲面モデルが表される空間における曲面モデル要素ごとの、透明度、色を含む情報も上述したパラメータに含まれる。
本実施形態では、曲面モデル要素が三角形で構成されている場合を例に説明する。これを一般的な多角形に適用する場合には、例えば、多角形を三角形の集合に分割する方法がある。分割方法については、例えば“Ｍ．ドバーグ、Ｍ．ファン．クリベルド、Ｍ．オーバマーズ、Ｏ．シュワルツコップ 共著、浅野哲夫 訳：コンピュータ・ジオメトリ 計算機科学：アルゴリズムと応用、近代科学社”に記載の方法を用いることが可能である。
【００２４】
［モデル制御情報算出部１０２］
モデル制御情報算出部１０２は、モデル記憶部１０１から所望の曲面モデルおよびベクタデータ定義位置を抽出し、描画制御用プリミティブ記憶部１０６から所望の描画制御用プリミティブデータを抽出し、曲面モデル要素ごとに最終的な入力曲面モデル要素とするかどうかを判定して、曲面モデル要素ごとにベクタ図形との関係を示す判定結果であるモデル制御情報を算出する。
ここで、モデル制御情報の判定方法について図６を用いて詳細に説明する。
モデル記憶部１０１に記憶されている曲面モデル要素（ここでは、三角形である多角形２の内部領域６０１）と、描画制御用プリミティブ記憶部１０６に記憶されている描画制御用プリミティブデータが表す描画制御用プリミティブに含まれる任意の図形（ここでは、三角形である多角形１の内部領域６０２）とについて、ベクタデータ定義位置にある曲面モデル要素ごとに以下の判定を行う。
（ａ）互いの三角形が交差している状態であるかどうか
（ｂ）一方の三角形がもう一方の三角形の内部領域に完全に含まれる状態であるかどうか（例えば、図６では多角形２の内部領域６０３が多角形１の内部領域６０４に完全に含まれている）
上記２点をそれぞれの三角形について個別に判定する。この判定手法は、例えば“中前栄八郎、西田友是：３次元コンピュータグラフィックス、ｐｐ６３−７２、昭晃堂”に記載の手法を用いることができるため、ここでの詳細な説明は省略する。また、このときの判定はベクタ定義空間でおこなわれる。判定を行うには、曲面モデルを構成する三角形がベクタ定義空間でどの様に定義されるかを調べる。曲面モデル要素ごとの頂点はベクタ定義空間での対応位置を示すパラメータを保持しているため、ベクタ定義空間での曲面モデル要素をそれぞれ定義することができる。なお、このときのベクタ定義空間は２次元の空間である。
以上の判定の結果、互いの三角形が交差したか、または一方の三角形がもう一方の三角形の内部領域に完全に含まれる場合には最終的な判定結果を「真」として、それ以外の場合は「偽」として、ベクタデータ定義位置にある曲面モデル要素ごとにこの「真」「偽」の判定結果がモデル制御情報として入力モデル制御部１０３に出力される。つまり、モデル制御情報が「真」の曲面モデル要素は、ベクタデータが描かれる領域を含む曲面モデル要素であるといえるため、これを最終的な入力曲面モデル要素とする。このモデル制御情報は、例えば曲面モデル要素ごとの「真」「偽」の判定を、フラグを用いて示して、曲面モデル要素ごとのフラグを入力モデル制御部１０３に出力してもよい。
なお、判定は必ずしも以上に挙げた手順である必要はなく、曲面モデル要素（多角形２の内部領域６０１、６０３）が描画制御用プリミティブに含まれる任意の図形（多角形１の内部領域６０２、６０４）と交差するか、または曲面モデル要素と描画制御用プリミティブに含まれる任意の図形のどちらか一方が、もう一方の内部領域に完全に含まれる状態になっているかの判定ができればよい。すなわち、モデル制御情報算出部１０２は、ベクタ定義空間での曲面モデル要素の占める領域と描画制御用プリミティブが占める領域とが重なっているかどうかの判定ができればよい。また、用途によっては簡易な判定で置き換えてもよい。例えば、曲面モデル要素ごとの頂点が描画制御用プリミティブに含まれる任意の図形の内部領域に含まれるかどうかを調べる。これにより曲面モデル要素と描画制御用プリミティブとの位置関係の判定を、通常の判定に比べて高速に判定することが可能になる。
なお、モデル制御情報算出部１０２で判定に用いた、モデル記憶部１０１に格納されている曲面モデルについては書き換えをおこなわない。
また、モデル制御情報算出部１０２は、モデル記憶部１０１から所望の曲面モデルおよびベクタデータ定義位置を受け取るときに、受け取った曲面モデルおよびベクタデータ定義位置と同じデータを入力モデル制御部１０３へ送るように、モデル記憶部１０１へ指示する。
【００２５】
［入力モデル制御部１０３］
入力モデル制御部１０３は、モデル制御情報算出部１０２から曲面モデル要素ごとの判定結果を示すモデル制御情報を受け取り、モデル記憶部１０１から、モデル制御情報算出部１０２が受け取ったものと同じ曲面モデルおよびベクタデータ定義位置を受け取り、モデル制御情報に含まれる判定結果が「真」である曲面モデル要素を含む新たな曲面モデルを再定義する。再定義された曲面モデル（以下、再定義曲面モデルという）の要素（以下、再定義曲面モデル要素という）は、モデル記憶部１０１から受け取った曲面モデルのうち、モデル制御情報に含まれる判定結果が「真」である曲面モデル要素を抽出して曲面を構成したものであるので、再定義曲面モデル要素を次のレンダリング処理への入力とする。よって、モデル制御情報算出部１０２で算出されたモデル制御情報に含まれる判定結果が「偽」の曲面モデル要素については以降の処理がおこなわれなくなる。すなわち、入力モデル制御部１０３は判定結果が「真」である曲面モデル要素を再定義曲面モデル要素とする。
【００２６】
［出力ラスタデータ生成部１０７］
出力ラスタデータ生成部１０７は、描画制御用プリミティブ記憶部１０６から描画制御用プリミティブデータを受け取り、入力モデル制御部１０３から、再定義曲面モデルを受け取り、再定義曲面モデルと描画制御用プリミティブデータとから最終的な出力とするラスタデータのピクセルの属性値を生成して提示部１０８へ送る。出力ラスタデータ生成部１０７が描画制御用プリミティブ記憶部１０６から受け取る描画制御用プリミティブデータついては、例えばモデル制御情報算出部１０２が描画制御用プリミティブ記憶部１０６から描画制御用プリミティブデータを抽出する際に、描画制御用プリミティブ記憶部１０６が同じ描画制御用プリミティブデータを出力ラスタデータ生成部１０７へ渡す。他の例として、モデル制御情報算出部１０２が直接、描画制御用プリミティブ記憶部１０６から抽出した描画制御用プリミティブデータを出力ラスタデータ生成部１０７に渡してもよい。
【００２７】
次に、出力ラスタデータ生成部１０７に含まれる各ブロックの動作について詳細に説明する。
出力ラスタデータ生成部１０７は、図７の左側の図に示すように描画用パラメータ算出部７０１、描画属性制御情報算出部２０２、ラスタデータ生成部７０３、およびラスタデータ記憶部７０４を含む。
【００２８】
［描画用パラメータ算出部７０１］
描画用パラメータ算出部７０１は、入力モデル制御部１０３から、再定義曲面モデルを受け取り、後述する手法で描画用パラメータを算出する。描画用パラメータとは、曲面モデル（ここでは再定義曲面モデル）をスクリーンに投影した際にそれぞれの曲面モデル要素（ここでは再定義曲面モデル要素）が占めるピクセルごとに、ベクタ定義空間における位置座標、色情報および透明度を含む情報を示すパラメータである。
描画用パラメータ算出部７０１は、再定義曲面モデルに加え、さらに必要であればカメラパラメータや投影方法を読み込む。この場合、描画用パラメータ算出部７０１は、後述のラスタデータ生成部７０３で生成されるラスタデータの各ピクセルが、ベクタ定義空間のどの位置に対応するかを表すパラメータ、およびどのような色が定義されていればよいかを算出する。これにより、各ピクセルのベクタ定義空間での位置座標（以下、対応位置という）、各ピクセルの色情報、および透明度などのピクセルの属性情報（以下、ピクセル属性情報という）が決定され、これを描画用パラメータとする。すなわち、描画用パラメータ算出部７０１はピクセルごとに描画用パラメータを算出する。
【００２９】
なお本実施形態では、ベクタ定義空間における独自の位置座標として例えばテクスチャ座標を用いる。テクスチャ座標を利用する場合、描画用パラメータ算出部７０１は、グラフィックスの分野で一般的に用いられるテクスチャマッピングの手法を用いて曲面モデルとベクタ定義空間との対応を計算し、ベクタ定義空間での位置を算出できる。
各ピクセルの対応位置（例えばテクスチャ座標）、各ピクセルの色情報、および透明度をどのようにして算出するかについては、曲面モデルをレンダリングする際のレンダリング方法と同様の方法で行うことができる。例えば、曲面モデルを微細な三角形面の集合で近似し、各ピクセル属性情報がどの三角形面で決定されるかを計算することで求めることが可能である。この計算方法は三角形面をレンダリングする際のピクセル属性情報の決定方法と同じであり、グラフィックスの分野では一般的な方法であるため説明は省略する。また、曲面モデルからのピクセル属性情報の決定方法はこれに限るものではない。例えば、各ピクセルから、レンダリングする際の視線の方向に半直線を延ばし、曲面モデルと半直線の交点部分の対応位置（例えばテクスチャ座標）、色情報、透明度などをピクセル属性情報とする。また、この方法に限定するものでもなく、ピクセルごとにピクセル属性情報が算出可能な他の方法を用いてもよい。
またベクタ定義空間に対応する描画用パラメータは、上記の形式に限定されるものではなく、グラフィックスの分野において一般的に利用される他のデータを用いるか、あるいは含んでもよい。また、例えば、あらかじめ決定される式にパラメータとして代入されるような、独自に定義した値であってもよい。また、曲率など曲面モデルから算出されるパラメータを利用してこのパラメータを変更したものを含んでもよい。
【００３０】
［描画判定情報算出部７０２］
描画判定情報算出部７０２は、描画制御用プリミティブ記憶部１０６から描画制御用プリミティブデータを受け取り、描画用パラメータ算出部７０１から描画用パラメータを受け取り、描画判定情報を算出する。描画判定情報とは、ベクタデータが形成する閉領域に各ピクセルの対応位置が含まれるかどうかを判定するための情報であり、ここでは後述する描画判定変数である。この対応位置の判定方法としては、例えば、以下の方法が挙げられる。
【００３１】
１）描画制御用プリミティブデータに含まれる任意の図形データ（ここでは三角形とする）を１つ読み込む。
２）この図形データ、またはこの図形データの一部分が、描画用パラメータ算出部７０１で算出された各ピクセルの対応位置を含むかどうかを調べる。
３）対応位置がこの図形データの内部領域に含まれれば描画判定変数を１とする。
ここで、描画判定変数とは、出力用のラスタデータにピクセルを書き込むかどうかを判定する変数である。また、読み込んだ描画制御用プリミティブが、直線輪郭から生成された三角形の場合と曲線輪郭から生成された三角形の場合とで判定の処理が異なる。
直線輪郭から生成された三角形の場合は、各ピクセルの対応位置が三角形の内部に含まれていれば描画判定変数に１を加算する。
一方、曲線輪郭から生成された三角形の場合、描画制御用プリミティブ生成部１０５での生成ルールによって処理が異なる。第１の条件は、各ピクセルの対応位置が三角形の内部に含まれていれば「真」というものであり、生成ルールによらず共通の条件である。第２の条件は描画制御用プリミティブデータの生成ルールによって異なる。直線輪郭が、制御点を無視してベクタデータに含まれる直線および曲線の始点と終点を線分で結ぶことにより生成される場合、曲線の凸領域内に各ピクセルの対応位置が含まれていれば「真」となる。また、２種類の曲線輪郭により、直線輪郭の生成の際に制御点を含むかどうか切り替える場合、すなわち凸曲線輪郭では制御点を無視して始点と終点との２点を結び、凹曲線輪郭では始点と制御点と終点との３点をこの順番に結び、これらの線分を連結して直線輪郭を生成する場合、凸曲線（曲線の凸領域が図形を表す曲線）の凸領域、あるいは凹曲線（曲線の凹領域が図形を表す曲線）の凹領域の、どちらかに含まれていれば三角形の一部に含まれるものとして「真」となる。これらの２つの条件が「真」である場合に、描画判定変数に１を加算する。なお、ここでは１を加算しているが、奇数であれば１でなくてもよい。
上記１）から３）を、全ての描画制御用プリミティブデータに含まれる全ての図形データ（ここでは三角形）について判定されるまで繰り返すことにより、各ピクセルの対応位置が、描画制御用プリミティブまたは描画制御用プリミティブの一部に含まれると判定された回数が得られる。本実施形態ではこの描画判定変数を描画判定情報とする。
例えば、描画制御用プリミティブが３つの直線輪郭から生成された三角形で構成されており、各ピクセルの対応位置がそのうちの２つの三角形の内部に相当する場合、描画判定変数は２となる。また、ベクタデータが色情報やアルファ値などの情報を保持しており、必要であれば、併せて各ピクセルの対応位置での色情報やアルファ値を算出してもよい。
【００３２】
［ラスタデータ生成部７０３］
ラスタデータ生成部７０３は、描画判定情報算出部７０２から描画判定情報（描画判定変数）および描画用パラメータを受け取り、ピクセル属性情報を用いて画面表示用のラスタデータに書き込みを行うかどうか、すなわち描画するかどうかをピクセルごとに決定して、ラスタデータを生成する。ラスタデータ生成部７０３は、ピクセルの描画判定変数が奇数である場合に、対応位置に対応するピクセルの属性値を描画用パラメータに基づいて生成し、ラスタデータにピクセルを書き込む。このとき、ベクタデータから算出された色情報やアルファ値があれば、すでに算出されているピクセル属性情報の色情報やアルファ値などの該当する部分をベクタデータから算出された値で置き換える、またはすでに算出されているピクセル属性情報の色情報やアルファ値とブレンドするなどの処理を行ってもよい。描画判定変数が奇数であるとは、直線輪郭から生成された描画制御用プリミティブデータ、および曲線輪郭から生成された描画制御用プリミティブデータに定義されている曲線の図形内部側の領域を全てラスタライズした場合に、そのピクセルが奇数回書き込まれるということと等しくなる。これを上記特開２００７−２４１８７８号公報で示されているステンシルデータの生成に置き換えて考えると、ステンシルデータのビット反転が奇数回おこなわれ、０以外の値となり、図形内部と判定されることと等しくなる。これは、上記特開２００７−２４１８７８号公報のステンシルデータと同様の結果を得ることができる。
【００３３】
［ラスタデータ記憶部７０４］
ラスタデータ記憶部７０４は、ラスタデータ生成部７０３からラスタデータを受け取って記憶し、提示部１０８へ送る。ただし、ラスタデータの構成はこの形式に限定されるものではなく、グラフィックスの分野において一般的に利用される他のデータを含んでもよい。
【００３４】
［提示部１０８］
提示部１０８は、出力ラスタデータ生成部１０７からラスタデータを受け取り、必要に応じてスクリーンに表示を行う。
【００３５】
なお、出力ラスタデータ生成部１０７で出力される結果は、ビットマップやＪＰＥＧ、ＧＩＦなどのグラフィックス分野で一般的に用いられる画像形式でラスタデータ記憶部７０４に保存されてもよいし、ネットワークを通じて出力結果、あるいは保存されたデータが転送されてもよい。
さらに図１では、モデル記憶部１０１とベクタデータ記憶部１０４および描画制御用プリミティブ記憶部１０６を異なるブロックとして表記しているが、これらは単一のメモリ上にまとめて構成してもよいし、異なる複数のメモリ上に分割して構成してもよい。
また本実施形態では、ベクタ定義空間は例えば各軸が０から１までの範囲で定義される二次元の空間であるとするが、ベクタ定義空間はこの形式に限定されるものではない。各軸が０から１以外の範囲で定義されてもよい。
以上に示した実施形態によれば、ベクタデータをレンダリングする際に、曲面モデルに含まれる曲面モデル要素のうち、ベクタデータを表現する可能性のある曲面モデル要素を算出して、レンダリングされる曲面モデルとして入力される曲面モデル要素数を削減することにより、ベクタデータを曲面モデル上にレンダリングする際の処理を高速化することができる。
【００３６】
（第１の変形例）
本変形例では、モデル制御情報算出部１０２において三角形が交差、および一方の三角形がもう一方の三角形の内部領域に完全に含まれる状態になっているかを判定する際に、曲面モデル要素とベクタデータとで判定を行うことが上記実施形態とは異なる。上記実施形態では曲面モデル要素に対し描画制御用プリミティブを判定対象としているため、ベクタデータ単位でレンダリング方法を選択する場合にベクタデータの形状によっては余分な領域が判定対象となることがある。本変形例では、曲面モデル要素に対しベクタ図形の輪郭線を判定対象としているので、ベクタデータにあわせて三角形を選択することができる。以下に、上記実施形態とは異なる動作を行うブロックのみ説明する。
【００３７】
描画制御用プリミティブ生成部１０５は、描画制御用プリミティブデータとともにベクタデータを描画制御用プリミティブ記憶部１０６へ送る。
描画制御用プリミティブ記憶部１０６は、描画制御用プリミティブ生成部１０５から受け取った描画制御用プリミティブデータおよびベクタデータを記憶する。
【００３８】
モデル制御情報算出部１０２は、モデル記憶部１０１から所望の曲面モデルおよびベクタデータ定義位置を抽出し、描画制御用プリミティブ記憶部１０６から所望のベクタデータを抽出し、曲面モデル要素ごとに判定をおこない、曲面モデル要素ごとの判定結果を示すモデル制御情報を入力モデル制御部１０３へ送る。なお、モデル制御情報算出部１０２は、ベクタデータ記憶部１０４からベクタデータを受け取ってもよい。
判定方法としては、ベクタデータに含まれる制御点、始点、および終点の接続関係を示すベクタデータ図形（例えば図３）の輪郭線を追跡した場合に出現する、制御点を含む全ての点で構成される多角形と曲面モデル要素とが交差しているかどうか、または、この多角形と曲面モデル要素とについて、一方がもう一方の内部領域に完全に含まれる状態になっているかどうかを判定する。なお、描画制御用プリミティブ記憶部１０６からこの多角形を得てもよい。例えば、曲線輪郭から定義される描画制御用プリミティブ（三角形）と直線輪郭で示される描画制御用プリミティブ（多角形）を上述した判定に用いる多角形として同様の判定を行ってもよい。上述した判定の具体的な判定方法については、例えば“中前栄八郎、西田友是：３次元コンピュータグラフィックス、ｐｐ６３−７２、昭晃堂”に記載されている方法を用いることができるため、ここでの詳細な説明は省略する。
しかしながら、判定方法はこれに限定されるものではなく、曲面モデルがベクタ定義空間に占める領域が、ベクタ図形（例えば図２の図形）が占める領域と重なるかどうかを調べることができればよい。互いに交差している場合と、ベクタデータ図形（例えば図３の図形）の輪郭線を追跡してできる多角形または曲面モデル要素のどちらか一方が、もう一方に含まれている場合とを区別する必要は無く、また描画制御用プリミティブデータが定義されているため、例えば図８に示すフローチャートのような方法でも判定が可能である。
【００３９】
はじめにステップＳ８０１では、曲面モデルからまだ判定がおこなわれていない曲面モデル要素（一般には多角形。例えば三角形。）を選択する。次に、ステップＳ８０２では、曲面モデル要素の各頂点のベクタ定義空間での位置を描画判定情報算出部７０２の対応位置として、上記の描画判定情報算出部７０２の説明と同様の手順で描画判定変数を算出する。描画判定変数が奇数であれば曲面モデル要素の一部は必ずベクタデータ図形の内部領域にあるため、モデル制御情報は「真」となりステップＳ８０６に進む。描画判定変数が偶数の場合は、ステップＳ８０３に進む。
ステップＳ８０３では、ベクタデータ図形の各頂点、制御点のいずれかが曲面モデル要素の内部領域に１つでも含まれるかどうかを調べる。ベクタデータ図形の各頂点、制御点のいずれかが曲面モデル要素の内部領域に１つでも含まれていればモデル制御情報は「真」となりステップＳ８０６に進む。ベクタデータ図形の各頂点、制御点のいずれも曲面モデル要素の内部領域に含まれていない場合は、ステップＳ８０４に進む。ステップＳ８０４では、曲線輪郭から定義される三角形を構成する各稜線または直線輪郭を構成する各稜線と、曲面モデル要素を構成する稜線とが交差しているかどうかを調べる。交差していればモデル制御情報は「真」となりステップＳ８０６に進む。それ以外の場合はステップＳ８０５に進み、モデル制御情報は「偽」となる。
ステップＳ８０７では、曲面モデルに含まれる全ての曲面モデル要素について判定をおこなったかどうかを調べ、全ての曲面モデル要素について判定をおこなったのであれば終了し、まだ判定されていない曲面モデルが存在するのであれば、ステップＳ８０１に戻り、上述した処理を同様に行う。
【００４０】
以上の処理により、入力モデル制御部１０３において本実施形態および第１の変形例を適用したイメージについて図９Ａから図９Ｃを参照して説明する。
図９Ａは「次」という文字に対しレンダリング処理を行う前の、制御処理をおこなっていない状態を示し、図９Ｂおよび図９Ｃはそれぞれ、実施形態適用後および第１の変形例適用後の制御処理をおこなった状態を示す。図９Ａに示す制御処理前の状態よりも図９Ｂに示す実施形態適用後のほうがレンダリングを行うデータが削減されていることがわかる。さらに、図９Ｃに示す第１の変形例適用後はベクタ図形の輪郭線と曲線輪郭から生成された描画制御用プリミティブの稜線を判定対象としているため、「次」の文字を構成するベクタデータに合わせてレンダリングを行うことができ、大幅なデータ削減が可能である。
【００４１】
また、より処理コストと削減される三角形とのバランスを考慮する場合は、Ｓ８０２、およびＳ８０４の処理を変更できる。Ｓ８０２では、曲面モデル要素の各頂点のベクタ定義空間での位置を描画判定情報算出部７０２の対応位置として、上記の描画判定情報算出部７０２の説明と同様の手順で描画判定変数を算出する。ただし、この時の判定には直線輪郭から生成された描画制御用プリミティブを用いる。描画判定変数が奇数であれば曲面モデルの一部は必ず直線輪郭で囲まれた多角形の内部にあるため、モデル制御情報は「真」となる。描画判定変数が偶数の場合、さらに、対応位置が曲線輪郭から生成された描画制御用プリミティブの内部に１つでも含まれるかを調べる。含まれている場合、モデル制御情報は「真」となる。モデル制御情報が「真」の場合にはステップＳ８０６に進む。モデル制御情報が「偽」の場合にはステップＳ８０３に進む。それ以外の場合は「偽」となる。Ｓ８０３は前記した処理と同様の処理を行う。Ｓ８０４では、描画制御用プリミティブの各稜線と曲面モデルを構成する稜線とが交差しているかどうかを調べる。交差していればモデル制御情報は「真」となりステップＳ８０６に進む。それ以外の場合はステップＳ８０５に進み、モデル制御情報は「偽」となる。
【００４２】
以上に示した第１の変形例によれば、上記の実施形態では描画制御用プリミティブを判定対象としていたためベクタデータに凹となる部分がある場合に余分な曲面モデル（三角形）を削減し切れなかったが、本変形例によれば、ベクタデータ図形の輪郭線を判定対象としているため、よりベクタデータにあわせて曲面モデルを削減することができる。
【００４３】
（比較例）
以下、本発明の実施形態との比較例として、特開２００６−１０６７０５号公報および特開２００７−２４１８７８号公報に記載された技術について説明する。
ベクタグラフィックスのラスタライズに要する演算コストを低減するため、ＧＰＵ（グラフィックスプロセッサユニット）が活用されていることについては既に述べた。ＧＰＵを利用して、図２に示すような、直線と曲線で構成されるベクタ図形をラスタライズするための上記特開２００６−１０６７０５号公報の手法をまず説明する。
【００４４】
このラスタライズ手法のフローチャートを図１０に示す。この図から分かるように、上記特開２００６−１０６７０５号公報の手法の処理は、ＣＰＵによる前処理とＧＰＵによる主処理の大きく２段階の処理から成る。最初に、ＣＰＵによってベクタ形式の図形が三角形の集まりに分解され、その後、ＧＰＵによって各三角形がラスタライズされる。ＧＰＵの処理単位は三角形であり、図２のような直線と曲線で構成されるベクタ図形を直接扱うことができないため、このような２段階の処理に分かれている。
最初のステップＳ１００１では、ＨＤＤやＲＡＭなどの記憶媒体からベクタデータを読み込み、その輪郭線を解析する処理がおこなわれる。例えば、図２のベクタ図形を表すベクタ形式のデータは、図３に示すベクタデータ図形に示されるような点と直線を含む。この図３では、図形の直線あるいはパラメトリック曲線の端点を黒丸で表し、パラメトリック曲線の制御点を白丸で表している。ステップＳ１００１では、このようなベクタデータ図形を解析して、図５に示すような２種類の輪郭線データを生成する。
本明細書では、上述したように、図５（ａ）の輪郭線データを「直線輪郭」と表記し、図５（ｂ）の輪郭線データを「曲線輪郭から定義される三角形」と表記している。また、以下では描画制御用プリミティブデータを三角形データ、描画制御用プリミティブを三角形として説明する。
図１０のフローチャートの説明に戻る。ステップＳ１００２では、前のステップで生成された曲線輪郭から定義される三角形に重なりがあるか調べる処理がおこなわれる。その結果、重なりが見つかった場合はステップＳ１００３に進み、重なっている２つの三角形のうちの面積の大きい方を細分割する処理がおこなわれる。
この処理の影響で直線輪郭にも変更が生じるため、次のステップＳ１００４では、直線輪郭を更新する処理がおこなわれる。その後、ステップＳ１００２に戻って再び重なりがあるか調べ、重なりがなければステップＳ１００５に進む。曲線輪郭から定義される三角形に重なりが残っている限り、ステップＳ１００２からＳ１００４の処理が繰り返される。
【００４５】
例えば図５（ｂ）に示す曲線輪郭から定義される三角形の集合の場合、ステップＳ１００２において三角形ａとｂ、および三角形ｃとｄが重なっていることが分かる。ステップＳ１００３では、三角形ａおよびｃが、それぞれ、図１１（ｂ）に示すような２つの三角形ａ０とａ１、およびｃ０とｃ１に細分割される。そしてステップＳ１００４では、図１１（ａ）に示すように直線輪郭を更新する処理がおこなわれる。
ステップＳ１００５では、直線輪郭を構成する各多角形を三角形に分割する処理がおこなわれる。例えば図１１（ａ）の３つの多角形は、図１２に示すような三角形の集まりに分割される。
以上（ステップＳ１００１からＳ１００５）の処理は、全てＣＰＵによる前処理として実行される。
ステップＳ１００６では、直線輪郭を構成する三角形（図１２）および曲線輪郭から定義される三角形を構成する三角形（図１３（ｂ））が、ＧＰＵによってラスタライズされる。このとき、直線輪郭を構成する三角形については、図１３（ａ）に示すように、その三角形の内側にある全てのピクセルがラスタライズされる。
これに対して曲線輪郭から定義される三角形については、図１３（ｂ）に示すように、その三角形の内側にあるピクセルのうち、凹曲線輪郭の凹領域、あるいは凸曲線輪郭の凸領域がラスタライズされる。
このようにして得られた直線輪郭と曲線輪郭から定義される三角形のラスタライズ結果は、ＧＰＵ内部のフレームバッファに併せて記憶される。例えば、図１３（ａ）と図１３（ｂ）は、図１４に示すようなラスタデータとしてフレームバッファに記憶される。
【００４６】
従来のＧＰＵを利用したラスタライズ手法では、複数の三角形を用いて曲線を近似していたため、拡大したときに粗く見えてしまう問題があった。また、より滑らかにラスタライズするためには多数の三角形を用いて曲線の近似精度を上げるしかなく、記憶容量と処理コストの増大が避けられなかった。これに対して上記特開２００６−１０６７０５号公報の手法では、三角形単位ではなく、曲線近傍のピクセル単位に処理するため、解像度に依存せず常に滑らかに曲線をラスタライズすることができる。その上、記憶容量と処理コストも解像度に依存せず、常に少なくて済む。
【００４７】
しかし、上記特開２００６−１０６７０５号公報のラスタライズ手法には以下の２つの問題がある。
１つ目の問題は前処理のコストが高いことである。特に、図１０のステップＳ１００２の曲線輪郭から定義される三角形の重複判定と、ステップＳ１００５の直線輪郭の三角形分割のコストが高い。
前処理のコストは、図形の幾何形状が時間的に変化しない場合であれば大きな問題にはならない。一度前処理をしてしまえば、以降は再び前処理を行う必要はないからである。しかし、動的に図形の幾何形状が変化する場合は、その都度、前処理をやり直さなければならず、ラスタライズ処理全体のボトルネックになることが多い。
２つ目の問題は、アンチエイリアシングのためにアルファブレンドを用いていることである。ここでアンチエイリアシングとは、ラスタライズされた図形の輪郭線に現れるジャギー（階段状のギザギザ）を除去する処理のことである。また、アルファブレンドとはアルファ値と呼ばれる係数を用いて２つのピクセル値を半透明合成する処理のことである。
広く知られているように、アルファブレンドを用いるためには全ての図形をデプス値でソート（デプスソート）し、奥に位置する図形から順番にラスタライズしなければならない。デプスソートは非常にコストが高い処理であり、ラスタライズ処理全体のボトルネックになることが多い。
【００４８】
上記特開２００７−２４１８７８号公報ではこれら２つの問題を解決する方法を提案している。
上記特開２００７−２４１８７８号公報では、ベクタデータに含まれる直線および曲線の始点と終点を単純に線分で結ぶことによって得られる多角形を直線輪郭としている。例えば、図３のベクタデータ図形から解析された直線輪郭は、図１５に示すような３つの多角形Ｐ０、Ｐ１、Ｐ２になる。曲線輪郭から定義される三角形については、上記特開２００６−１０６７０５号公報と同様のものを用いている。
得られた直線輪郭を構成する各多角形について、任意の１点（ピボット）が選択される。そして次に、ピボットと、ピボットを含まない全ての連結する２点を結ぶ三角形を生成する。ここで連結する２点とは、多角形の辺によって結ばれている２つの点のことを意味する。
例えば、図１５の３つの多角形Ｐ０、Ｐ１、Ｐ２において、それぞれ点０、２３、２８がピボットとして選択された場合、図１６に示すような三角形が生成される。三角形が重なっており、この図だけでは三角形の形状を把握することが難しいため、図１７に３つの多角形Ｐ０、Ｐ１、Ｐ２から生成された三角形を構成する３つの点の番号を示す。
なお、図１７はあくまで説明を分かりやすくするための補足であり、三角形データそのものを表しているのではないことに注意する。実際の三角形データは、各三角形を構成する３点の位置座標、およびテクスチャ座標、および接続関係などから構成される。
【００４９】
次に、三角形内部のピクセルをラスタライズすることによってステンシルデータを生成する処理がおこなわれる。なお、ステンシルデータは、最終的に提示する解像度と同じ解像度をもつ画像データである。
まず、直線輪郭から生成される三角形データおよび曲線輪郭から生成される三角形データを読み込み、ラスタライズする。このとき、直線輪郭の三角形については、その三角形の内側にある全てのピクセルがラスタライズされ、これらのピクセル位置に対応するステンシルデータのピクセル値がビット反転される。
一方、曲線輪郭から定義される三角形については、その三角形の内側にあるピクセルのうち、曲線の凸領域に属するピクセルがラスタライズされ、これらのピクセル位置に対応するステンシルデータのピクセル値がビット反転される。
結果として、図形の内部は奇数回ピクセル値がビット反転され、図形の外部は偶数回ピクセル値がビット反転される。
【００５０】
上記の処理によって塗りつぶすピクセルが判断できるため、描画用のラスタデータの対応するピクセルを塗りつぶすことで描画結果を生成することができる。
上記特開２００７−２４１８７８号公報では、直線輪郭の三角形分割などをおこなわないため、ベクタデータの頂点を移動しても三角形データの接続関係が変化しなければ三角形データの対応する頂点座標を書き換えるだけでよく、再度三角形データを作り直す必要はない。そのため、図形の幾何形状が動的に変化しても高速にラスタライズが可能である。
また、描画用のラスタデータのサブピクセル精度の画像を用意し、カバレッジデータをもとにサブピクセルの一部に図形の色を割り当て、最終的な描画用のラスタデータを生成する際に合成することでアルファブレンドが不要なアンチエイリアシングを可能としている。
【００５１】
しかし、上記特開２００６−１０６７０５号公報および特開２００７−２４１８７８号公報に記載された技術では、図形を曲面上にレンダリングしたい場合にそのまま適用することができない。
一般に、多角形データを曲面上にレンダリングする場合、多角形データを微細な多角形データ群に分割することで元の多角形データ内に頂点を追加し、その頂点を移動することによって実現する。上記特開２００７−２４１８７８号公報の方法を利用してベクタデータを曲面上にレンダリングする場合にも、上記特開２００７−２４１８７８号公報で示される方法で生成された三角形データを再分割する必要がある。
三角形データの再分割には様々な方法があるが、十分に曲面に沿っている、つまり曲面上にレンダリングされているといえる描画結果が得られるように再分割する方法の処理コストは高い。
ベクタデータを描画するための三角形データを再分割してしまうため、図形の幾何形状が変化する場合には、その都度、再分割処理をやり直す必要がある。このため、上記特開２００６−１０６７０５号公報の問題点であり、上記特開２００７−２４１８７８号公報の利点である、動的な図形の幾何形状の変化への対応も不可能となる。
【００５２】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【符号の説明】
【００５３】
１００・・・描画装置、１０１・・・モデル記憶部、１０２・・・モデル制御情報算出部、１０３・・・入力モデル制御部、１０４・・・ベクタデータ記憶部、１０５・・・描画制御用プリミティブ生成部、１０６・・・描画制御用プリミティブ記憶部、１０７・・・出力ラスタデータ生成部、１０８・・・提示部、６０１、６０３・・・多角形２の内部領域、６０２、６０４・・・多角形１の内部領域、７０１・・描画用パラメータ算出部、７０２・・・描画判定情報算出部、７０３・・・ラスタデータ生成部、７０４・・・ラスタデータ記憶部。
【技術分野】
【０００１】
本発明は、本発明はベクタ図形を描画する描画装置および方法に関する。
【背景技術】
【０００２】
点や直線、曲線、四角形、楕円などの幾何学的な図形要素を組み合わせることによって構成される画像のことをベクタグラフィックスと呼ぶ。これに対し、点（ピクセルあるいはドット）の配列によって構成される画像のことをラスタグラフィックスと呼ぶ。
【０００３】
一般に、ディスプレイに表示される画像やプリンタで印刷される画像はラスタグラフィックスである。これらの機器でベクタグラフィックスを扱う際には、これをラスタグラフィクスへ変換する処理（ラスタライズ）が必要になる。ラスタライズの処理コストは高く、複雑なベクタグラフィックスを高速にラスタライズするためには高性能な計算機が必要とされる。その反面、ベクタグラフィックスは表示の都度、適切な解像度のラスタグラフィックスを生成することができるため、画像の拡大や縮小、変形によって輪郭線などの画質が損なわれることがない。そのため、イラストや図面などの輪郭線が明瞭な人工的な画像はベクタグラフィックスとして扱われることが多い。一方、写真などの自然画像はラスタグラフィックスとして扱われることが多い。
【０００４】
ベクタグラフィックスの最も身近な利用例はフォントである。初期の計算機ではＣＰＵ性能の制約からラスタ形式のフォント（ビットマップフォント）が使われているが、解像度ごとにフォントデータを保持しなければならなかったため多くの記憶容量を必要としている。その後のＣＰＵ性能の向上に伴い、現在の計算機では、解像度に依存しないベクタ形式のフォント（アウトラインフォント）データを保持しておき、ディスプレイやプリンタに見合った適切な解像度のフォントをその都度生成することにより、少ない記憶容量で常に高品質なフォントを表示できる。しかし現在でも、携帯電話やカーナビゲーションシステムなどに内蔵されるＣＰＵは処理能力が比較的低く、ベクタグラフィックスのラスタライズに要する演算コストを低減することが課題になっている。
【０００５】
近年、この課題を解決するためにＧＰＵ（グラフィックスプロセッサユニット）が活用されている。ＧＰＵを利用し、直線と曲線で構成される図形をラスタライズするための手法が既に提案されている（例えば、特許文献１参照）。
【０００６】
また、図形の幾何形状が動的に変化しても高速にラスタライズが可能な手法も公知である（例えば、特許文献２参照）。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２００６−１０６７０５号公報
【特許文献２】特開２００７−２４１８７８号公報
【発明の概要】
【発明が解決しようとする課題】
【０００８】
しかしながら、ベクタ図形を曲面上に描画する場合には、処理の負担が増大し高速に描画処理を行うことができない問題がある。
本発明は、ベクタ図形を曲面上に描画する場合であっても、再分割処理等による処理負担の増加を低減し高速に描画処理を行うことのできる描画装置および方法を提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述の課題を解決するため、本発明に係る描画装置は、ベクタ形式の図形に対応するベクタデータを記憶している第１記憶手段と、前記図形を描画するガイドとしての曲面モデルと、該曲面モデルに対応する、前記ベクタデータがレンダリングされることが可能な領域を示すベクタデータ定義位置とを記憶する第２記憶手段と、前記ベクタデータを輪郭線解析することにより直線輪郭および曲線輪郭のいずれか１以上に対応するデータを含むプリミティブデータを、前記曲面モデルが定義される空間と独立して前記図形を定義するとともに出力するラスタデータのピクセルの属性値を決定するために参照されるベクタ定義空間に生成する第１生成手段と、前記曲面モデルに含まれる要素ごとに、該要素が前記ベクタ定義空間のどの位置になるかを算出し、ベクタ定義空間で曲面モデルと前記図形に対応するデータとの関係を判定する第１判定手段と、前記要素ごとに前記第１判定手段の判定結果を参照して、前記複数の要素から採用する要素を決定し、採用する要素を含む再定義曲面モデルを生成する第２生成手段と、前記再定義曲面モデルと前記プリミティブデータとを参照して、出力するラスタデータのピクセルの属性値を生成する第３生成手段と、を具備することを特徴とする。
【発明の効果】
【００１０】
本発明の描画装置および方法によれば、再分割処理等による処理負担の増加を低減し高速に描画処理を行うことができる。
【図面の簡単な説明】
【００１１】
【図１】本実施形態に係る描画装置を示すブロック図。
【図２】ベクタ図形の一例を示す図。
【図３】ベクタデータ図形の一例を示す図。
【図４】三角形のうち、凸領域が図形を表す場合（（ａ））と、凹領域が図形を表す場合（（ｂ））を示す図。
【図５】直線輪郭（（ａ））と曲線輪郭から定義される三角形の集合（（ｂ））の一例を示す図。
【図６】描画制御用プリミティブの１つがある曲面モデル要素と交差している状態（（ａ））、またはある曲面モデル要素がある描画制御用プリミティブに含まれている状態（（ｂ））を示す図。
【図７】図１の出力ラスタデータ生成部を示すブロック図。
【図８】図１のモデル制御情報算出部の動作の一例を示すフローチャート。
【図９Ａ】図１の入力モデル制御部の処理前の文字のイメージを示す図。
【図９Ｂ】図１の入力モデル制御部の処理後の文字のイメージの一例を示す図。
【図９Ｃ】図１の入力モデル制御部の処理後の文字のイメージの別例を示す図。
【図１０】比較例におけるラスタライズの処理手順を示すフローチャート。
【図１１】細分割された曲線輪郭から定義される三角形の集合（（ｂ））と、それに伴い更新された直線輪郭（（ａ））の一例を示す図。
【図１２】三角形分割された直線輪郭の一例を示す図。
【図１３】比較例におけるラスタライズされた直線輪郭（（ａ））および曲線輪郭から定義される三角形の集合（（ｂ））の一例を示す図。
【図１４】比較例における生成されたラスタデータの一例を示す図。
【図１５】直線輪郭の一例を示す図。
【図１６】比較例における直線輪郭から生成された三角形データの一例を示す図。
【図１７】比較例における直線輪郭から生成された三角形の点番号の一例を示す図。
【発明を実施するための形態】
【００１２】
以下、図面を参照しながら本発明の実施形態に係る描画装置および方法について詳細に説明する。
本実施形態に係る描画装置の構成について図１を参照して詳細に説明する。
本実施形態に係る描画装置１００は、モデル記憶部１０１、モデル制御情報算出部１０２、入力モデル制御部１０３、ベクタデータ記憶部１０４、描画制御用プリミティブ生成部１０５、描画制御用プリミティブ記憶部１０６、出力ラスタデータ生成部１０７、および提示部１０８を含む。
ベクタデータ記憶部１０４は、任意の図形を表すベクタ形式の図形データであるベクタデータを記憶している。描画制御用プリミティブ生成部１０５は、所望のベクタ図形に対応するベクタデータを読み込み、ベクタデータを描画するために利用する描画制御用プリミティブデータをベクタ定義空間に生成し、描画制御用プリミティブデータを描画制御用プリミティブ記憶部１０６に記憶する。
【００１３】
モデル記憶部１０１は、曲面モデル（複数の曲面モデル要素）とベクタデータ定義位置とを対応付けて記憶している。モデル制御情報算出部１０２は、モデル記憶部１０１から所望の曲面モデルを抽出し、描画制御用プリミティブ記憶部１０６から所望の描画制御用プリミティブデータを抽出し、曲面モデル要素ごとに出力ラスタデータ生成部１０７へ描画制御用プリミティブデータを出力するかどうかの判定結果を示すモデル制御情報を算出する。入力モデル制御部１０３は、モデル制御情報と、モデル制御情報算出部１０２が受け取ったものと同じ曲面モデルおよびベクタデータ定義位置とを受け取り、出力ラスタデータ生成部１０７へ出力してレンダリングする曲面モデルを再定義曲面モデルと再定義する。ここで、要素とは曲面モデルを構成する多角形を指し、例えば三角形や長方形を用いる事ができる。
【００１４】
出力ラスタデータ生成部１０７は、入力モデル制御部１０３から取得した再定義曲面モデルに対応する描画制御用プリミティブデータを受け取り、入力モデル制御部１０３から再定義曲面モデルを受け取り、再定義曲面モデルと描画制御用プリミティブデータとから最終的な出力とするラスタデータを生成して提示部１０８へ送る。提示部１０８は受け取ったラスタデータをスクリーンに表示する。
【００１５】
［ベクタデータ記憶部１０４］
ベクタデータ記憶部１０４は、１種類以上のベクタ図形に対応する１以上のベクタデータを記憶している。ベクタデータは、ラスタライズされる任意のベクタ形式の図形（ベクタ図形と呼ぶ。ベクタ図形の一例を図２に示す）を表すベクタ形式の図形データであり、ラスタライズされる領域を含む任意の図形を示す、始点、制御点、および終点の座標と、ベクタ図形の種類（例えばフォント、絵）と、ベクタ図形を構成する各点（始点、制御点、および終点）の接続関係内部のラスタライズされる領域を示す情報とを含む。また、直線および曲線のどちら側を図形の内部とするかの情報を直線および曲線ごと定義していなくとも、直線および曲線のどちら側を内部領域とするかをあらかじめ決めておけばベクタデータの輪郭線解析と同時に内部領域を定義することができる。ベクタ図形の一例を図２に示し、図２のベクタ図形に対応するベクタデータに含まれる各点と各点との接続関係を図３に示す。
なお、ベクタデータは上記の形式に限定されるものではなく、色情報やアルファ値などのグラフィックスの分野において一般的に利用される他のデータを含んでもよい。
【００１６】
［描画制御用プリミティブ生成部１０５］
描画制御用プリミティブ生成部１０５は、ベクタデータ記憶部１０４に記憶されているベクタデータを参照して、描画を行うベクタデータを抽出し、抽出したベクタデータから描画制御用プリミティブデータをベクタ定義空間に少なくとも１つ生成する。ベクタ定義空間は、曲面モデルが定義される空間とは独立した空間であって、独自の位置座標（またはテクスチャ座標）などでレンダリング対象のベクタデータが定義される空間のうちのある範囲で定義されるものである。ベクタ定義空間は、例えば各軸が０から１までの範囲で定義される２次元空間である。また、ベクタ定義空間は、後述する出力ラスタデータ生成部１０７が出力するラスタデータのピクセルの属性値を決定するために参照される空間である。ピクセルの属性値とは、ベクタ定義空間での位置座標、各ピクセルの色情報、および透明度などを示す通常複数の値である。ラスタデータは、最終的に提示部１０８に提示される画像の解像度と同じ解像度をもつ画像データである。曲面モデルについては後述のモデル記憶部１０１において詳細に説明する。
描画制御用プリミティブデータとは、ベクタデータを曲面モデルに描画するために利用するデータであり、例えば三角形、凸多角形を形成する点座標およびある点座標を結ぶ線を含むデータである。また、描画制御用プリミティブデータが表す描画制御用プリミティブは、ベクタデータの始点、制御点、および終点を解析することによって生成される図形であり、例えば三角形群が挙げられるが、他にも凸多角形群を含む場合もある。なお、本実施形態では描画制御用プリミティブが三角形群と多角形群を含んでいる場合を例に説明を行う。図３では、図形の直線あるいはパラメトリック曲線の端点を黒丸で表し、パラメトリック曲線の制御点を白丸で表している。
描画制御用プリミティブ生成部１０５は、ベクタデータを輪郭線解析した結果、曲線輪郭（例えば図５（ｂ））と直線輪郭（例えば図１５）とに対応するデータを含む描画制御用プリミティブデータを生成する。描画制御用プリミティブデータは、ベクタ図形を再現する上でベクタデータと等価である。曲線輪郭から生成される描画制御用プリミティブは、曲線輪郭のパラメトリック曲線の始点と終点、および制御点の３点を結んで定義される多角形（ここでは三角形）の集合である。各三角形はパラメトリック曲線に外接しており、曲線は必ず三角形の内部に存在する。図３の例では、図３に含まれる始点と終点、および制御点の３点を結んで定義される三角形の集合である。また、曲線輪郭から定義される三角形は、図４（ｂ）に示すように内部に定義されている曲線の凸領域を表すもの（凸曲線輪郭と称する）と、図４（ａ）に示すように凹領域を表すもの（凹曲線輪郭と称する）の２種類で構成される。なお、曲線輪郭から定義される三角形については、三角形の内側にあるピクセルのうち、曲線の凸領域に属するピクセルのみがラスタライズされる。
【００１７】
直線輪郭は、制御点を無視してベクタデータに含まれる直線および曲線の始点と終点を線分で結ぶことによって得られる多角形と定義される。この直線輪郭は、例えば具体的には後述する図１５に示す図形となる。さらにこの直線輪郭について三角化を行う。具体的には直線輪郭を構成する多角形の複数の頂点のうち、任意の１つの頂点（ピボットという）を選択する。そして、ピボットと他の全ての頂点を直線で結び、連結する２つの頂点が１つの三角形の辺となるように、ピボットを１つの頂点とする複数の三角形を生成する。これら複数の三角形を直線輪郭から生成される描画制御用プリミティブとする。ここで連結する２つの頂点とは、多角形の辺によって結ばれている２つの頂点のことを意味する。
このようにベクタデータから描画制御用プリミティブデータを生成するより詳しい方法は例えば上記特開２００７−２４１８７８号公報で示されているため、ここでの詳細な説明は省略する。
【００１８】
しかしながら、描画制御用プリミティブデータの生成方法はこれに限定されるものではなく、例えば、曲線輪郭から定義される三角形は、上述したように凹曲線輪郭と、凸曲線輪郭の２種類で構成される。直線輪郭は、例えばこの２種類の曲線輪郭に応じて定義されてもよい。この場合、直線輪郭は、凸曲線輪郭では制御点を無視して始点と終点との２点を結び、凹曲線輪郭では始点と制御点と終点との３点をこの順番に結び、これらの線分を連結して得られる多角形の輪郭の集合である。このように結んだ直線輪郭の例としては、図５（ａ）が挙げられる。図５（ａ）から分かるように、直線輪郭を構成する多角形は１つとは限らない（この例では３つの多角形で構成される）。また、各多角形は自己交差や穴を含むことがある。
この場合、図形（例えば三角形）の内部のラスタライズされる領域を示す情報は、例えば２種類の上述した曲線輪郭で決定される。この２種類の曲線輪郭によって、始点、制御点、および終点で決まる曲線で区切られる、三角形内部の領域のうち、どちらの領域がラスタライズされる領域であるかを示すことができる。
【００１９】
描画制御用プリミティブデータは、上述したように、ベクタ定義空間に定義される。この場合、描画制御用プリミティブデータがベクタ定義空間が定義される範囲に全て含まれ、かつ三角形群を覆う最小の矩形が最も大きくなるように三角形の正規化を行う。具体的には、矩形が描画制御用プリミティブを全て覆う最小の長方形であり、各辺がベクタ定義空間のいずれかの軸と平行で、なおかつ２辺が垂直に交差している長方形であって、その長方形の２辺のうち長い方の辺がベクタ定義空間に収まる最も長い長さになるように拡大するさいの倍率を決定したうえで、その長方形の縦横比を維持したまま拡大し、正規化することができる。この手法とは異なり、例えば、描画制御用プリミティブ生成部１０５で生成された描画制御用プリミティブデータがベクタ定義空間に全て含まれ、かつ矩形の各辺がベクタ定義空間のいずれかの軸と平行な最小の長方形を考え、その長方形の縦横比を維持したまま、その長方形をベクタ定義空間に含まれる範囲で拡大した際の倍率で正規化することもできる。しかしながらこの方法に限定するものではなく、グラフィックスの分野で一般的な他の正規化方法を用いてもよい。
【００２０】
［描画制御用プリミティブ記憶部１０６］
描画制御用プリミティブ記憶部１０６は、描画制御用プリミティブ生成部１０５から描画制御用プリミティブデータを受け取って記憶する。
【００２１】
［モデル記憶部１０１］
モデル記憶部１０１は、各頂点にパラメータを含む複数の曲面モデル要素を含む曲面モデルと、この曲面モデルに対応するベクタデータ定義位置とを記憶している。曲面モデル要素は、辺の数が３以上で構成される多角形で示され、例えば三角形である。複数の曲面モデル要素の集合によって曲面モデルを表現する。ベクタデータ定義位置は、プリミティブデータに基づいてベクタ図形を再現するために曲面モデルのどの位置にベクタデータをレンダリングするかを示す。すなわち、ベクタデータ定義位置は、ベクタ定義空間で定義された領域が曲面モデルのどの領域にレンダリングされるかを示す。ここでの曲面モデルは、ベクタ図形を描画するガイドとして使用される。また、モデル記憶部１０１には、曲面モデル要素により構成される曲面モデルが複数記憶されていてもよい。
【００２２】
この曲面モデル要素の各頂点には、ベクタ定義空間での対応位置を示すパラメータが定義されているものとする。このパラメータは例えば、テクスチャ座標の利用が考えられる。このパラメータにより、曲面が表される空間における曲面モデル要素の位置座標と、ベクタ定義空間におけるベクタデータ定義位置とが対応しているため、ベクタ定義空間における曲面モデル要素（ここでは三角形）を定義することができ、ベクタ定義空間にあるレンダリング対象のベクタデータと曲面モデル要素とのベクタ定義空間での位置関係を容易に判定することができる。さらに、曲面モデル要素が三角形の場合には、三角形を生成する３頂点によってある曲面モデル要素の法線ベクトルを決定することができる。
【００２３】
なお、保存されるデータはこれらのみに限定されない。レンダリングの際の視点の位置や視線方向を表すカメラパラメータや並行投影または投視投影のどちらで投影するかなど、グラフィックスの分野でレンダリングの際に一般的に用いられる他の情報がモデル記憶部１０１に記憶されていてもよい。この場合、曲面モデルが表される空間における曲面モデル要素ごとの、透明度、色を含む情報も上述したパラメータに含まれる。
本実施形態では、曲面モデル要素が三角形で構成されている場合を例に説明する。これを一般的な多角形に適用する場合には、例えば、多角形を三角形の集合に分割する方法がある。分割方法については、例えば“Ｍ．ドバーグ、Ｍ．ファン．クリベルド、Ｍ．オーバマーズ、Ｏ．シュワルツコップ 共著、浅野哲夫 訳：コンピュータ・ジオメトリ 計算機科学：アルゴリズムと応用、近代科学社”に記載の方法を用いることが可能である。
【００２４】
［モデル制御情報算出部１０２］
モデル制御情報算出部１０２は、モデル記憶部１０１から所望の曲面モデルおよびベクタデータ定義位置を抽出し、描画制御用プリミティブ記憶部１０６から所望の描画制御用プリミティブデータを抽出し、曲面モデル要素ごとに最終的な入力曲面モデル要素とするかどうかを判定して、曲面モデル要素ごとにベクタ図形との関係を示す判定結果であるモデル制御情報を算出する。
ここで、モデル制御情報の判定方法について図６を用いて詳細に説明する。
モデル記憶部１０１に記憶されている曲面モデル要素（ここでは、三角形である多角形２の内部領域６０１）と、描画制御用プリミティブ記憶部１０６に記憶されている描画制御用プリミティブデータが表す描画制御用プリミティブに含まれる任意の図形（ここでは、三角形である多角形１の内部領域６０２）とについて、ベクタデータ定義位置にある曲面モデル要素ごとに以下の判定を行う。
（ａ）互いの三角形が交差している状態であるかどうか
（ｂ）一方の三角形がもう一方の三角形の内部領域に完全に含まれる状態であるかどうか（例えば、図６では多角形２の内部領域６０３が多角形１の内部領域６０４に完全に含まれている）
上記２点をそれぞれの三角形について個別に判定する。この判定手法は、例えば“中前栄八郎、西田友是：３次元コンピュータグラフィックス、ｐｐ６３−７２、昭晃堂”に記載の手法を用いることができるため、ここでの詳細な説明は省略する。また、このときの判定はベクタ定義空間でおこなわれる。判定を行うには、曲面モデルを構成する三角形がベクタ定義空間でどの様に定義されるかを調べる。曲面モデル要素ごとの頂点はベクタ定義空間での対応位置を示すパラメータを保持しているため、ベクタ定義空間での曲面モデル要素をそれぞれ定義することができる。なお、このときのベクタ定義空間は２次元の空間である。
以上の判定の結果、互いの三角形が交差したか、または一方の三角形がもう一方の三角形の内部領域に完全に含まれる場合には最終的な判定結果を「真」として、それ以外の場合は「偽」として、ベクタデータ定義位置にある曲面モデル要素ごとにこの「真」「偽」の判定結果がモデル制御情報として入力モデル制御部１０３に出力される。つまり、モデル制御情報が「真」の曲面モデル要素は、ベクタデータが描かれる領域を含む曲面モデル要素であるといえるため、これを最終的な入力曲面モデル要素とする。このモデル制御情報は、例えば曲面モデル要素ごとの「真」「偽」の判定を、フラグを用いて示して、曲面モデル要素ごとのフラグを入力モデル制御部１０３に出力してもよい。
なお、判定は必ずしも以上に挙げた手順である必要はなく、曲面モデル要素（多角形２の内部領域６０１、６０３）が描画制御用プリミティブに含まれる任意の図形（多角形１の内部領域６０２、６０４）と交差するか、または曲面モデル要素と描画制御用プリミティブに含まれる任意の図形のどちらか一方が、もう一方の内部領域に完全に含まれる状態になっているかの判定ができればよい。すなわち、モデル制御情報算出部１０２は、ベクタ定義空間での曲面モデル要素の占める領域と描画制御用プリミティブが占める領域とが重なっているかどうかの判定ができればよい。また、用途によっては簡易な判定で置き換えてもよい。例えば、曲面モデル要素ごとの頂点が描画制御用プリミティブに含まれる任意の図形の内部領域に含まれるかどうかを調べる。これにより曲面モデル要素と描画制御用プリミティブとの位置関係の判定を、通常の判定に比べて高速に判定することが可能になる。
なお、モデル制御情報算出部１０２で判定に用いた、モデル記憶部１０１に格納されている曲面モデルについては書き換えをおこなわない。
また、モデル制御情報算出部１０２は、モデル記憶部１０１から所望の曲面モデルおよびベクタデータ定義位置を受け取るときに、受け取った曲面モデルおよびベクタデータ定義位置と同じデータを入力モデル制御部１０３へ送るように、モデル記憶部１０１へ指示する。
【００２５】
［入力モデル制御部１０３］
入力モデル制御部１０３は、モデル制御情報算出部１０２から曲面モデル要素ごとの判定結果を示すモデル制御情報を受け取り、モデル記憶部１０１から、モデル制御情報算出部１０２が受け取ったものと同じ曲面モデルおよびベクタデータ定義位置を受け取り、モデル制御情報に含まれる判定結果が「真」である曲面モデル要素を含む新たな曲面モデルを再定義する。再定義された曲面モデル（以下、再定義曲面モデルという）の要素（以下、再定義曲面モデル要素という）は、モデル記憶部１０１から受け取った曲面モデルのうち、モデル制御情報に含まれる判定結果が「真」である曲面モデル要素を抽出して曲面を構成したものであるので、再定義曲面モデル要素を次のレンダリング処理への入力とする。よって、モデル制御情報算出部１０２で算出されたモデル制御情報に含まれる判定結果が「偽」の曲面モデル要素については以降の処理がおこなわれなくなる。すなわち、入力モデル制御部１０３は判定結果が「真」である曲面モデル要素を再定義曲面モデル要素とする。
【００２６】
［出力ラスタデータ生成部１０７］
出力ラスタデータ生成部１０７は、描画制御用プリミティブ記憶部１０６から描画制御用プリミティブデータを受け取り、入力モデル制御部１０３から、再定義曲面モデルを受け取り、再定義曲面モデルと描画制御用プリミティブデータとから最終的な出力とするラスタデータのピクセルの属性値を生成して提示部１０８へ送る。出力ラスタデータ生成部１０７が描画制御用プリミティブ記憶部１０６から受け取る描画制御用プリミティブデータついては、例えばモデル制御情報算出部１０２が描画制御用プリミティブ記憶部１０６から描画制御用プリミティブデータを抽出する際に、描画制御用プリミティブ記憶部１０６が同じ描画制御用プリミティブデータを出力ラスタデータ生成部１０７へ渡す。他の例として、モデル制御情報算出部１０２が直接、描画制御用プリミティブ記憶部１０６から抽出した描画制御用プリミティブデータを出力ラスタデータ生成部１０７に渡してもよい。
【００２７】
次に、出力ラスタデータ生成部１０７に含まれる各ブロックの動作について詳細に説明する。
出力ラスタデータ生成部１０７は、図７の左側の図に示すように描画用パラメータ算出部７０１、描画属性制御情報算出部２０２、ラスタデータ生成部７０３、およびラスタデータ記憶部７０４を含む。
【００２８】
［描画用パラメータ算出部７０１］
描画用パラメータ算出部７０１は、入力モデル制御部１０３から、再定義曲面モデルを受け取り、後述する手法で描画用パラメータを算出する。描画用パラメータとは、曲面モデル（ここでは再定義曲面モデル）をスクリーンに投影した際にそれぞれの曲面モデル要素（ここでは再定義曲面モデル要素）が占めるピクセルごとに、ベクタ定義空間における位置座標、色情報および透明度を含む情報を示すパラメータである。
描画用パラメータ算出部７０１は、再定義曲面モデルに加え、さらに必要であればカメラパラメータや投影方法を読み込む。この場合、描画用パラメータ算出部７０１は、後述のラスタデータ生成部７０３で生成されるラスタデータの各ピクセルが、ベクタ定義空間のどの位置に対応するかを表すパラメータ、およびどのような色が定義されていればよいかを算出する。これにより、各ピクセルのベクタ定義空間での位置座標（以下、対応位置という）、各ピクセルの色情報、および透明度などのピクセルの属性情報（以下、ピクセル属性情報という）が決定され、これを描画用パラメータとする。すなわち、描画用パラメータ算出部７０１はピクセルごとに描画用パラメータを算出する。
【００２９】
なお本実施形態では、ベクタ定義空間における独自の位置座標として例えばテクスチャ座標を用いる。テクスチャ座標を利用する場合、描画用パラメータ算出部７０１は、グラフィックスの分野で一般的に用いられるテクスチャマッピングの手法を用いて曲面モデルとベクタ定義空間との対応を計算し、ベクタ定義空間での位置を算出できる。
各ピクセルの対応位置（例えばテクスチャ座標）、各ピクセルの色情報、および透明度をどのようにして算出するかについては、曲面モデルをレンダリングする際のレンダリング方法と同様の方法で行うことができる。例えば、曲面モデルを微細な三角形面の集合で近似し、各ピクセル属性情報がどの三角形面で決定されるかを計算することで求めることが可能である。この計算方法は三角形面をレンダリングする際のピクセル属性情報の決定方法と同じであり、グラフィックスの分野では一般的な方法であるため説明は省略する。また、曲面モデルからのピクセル属性情報の決定方法はこれに限るものではない。例えば、各ピクセルから、レンダリングする際の視線の方向に半直線を延ばし、曲面モデルと半直線の交点部分の対応位置（例えばテクスチャ座標）、色情報、透明度などをピクセル属性情報とする。また、この方法に限定するものでもなく、ピクセルごとにピクセル属性情報が算出可能な他の方法を用いてもよい。
またベクタ定義空間に対応する描画用パラメータは、上記の形式に限定されるものではなく、グラフィックスの分野において一般的に利用される他のデータを用いるか、あるいは含んでもよい。また、例えば、あらかじめ決定される式にパラメータとして代入されるような、独自に定義した値であってもよい。また、曲率など曲面モデルから算出されるパラメータを利用してこのパラメータを変更したものを含んでもよい。
【００３０】
［描画判定情報算出部７０２］
描画判定情報算出部７０２は、描画制御用プリミティブ記憶部１０６から描画制御用プリミティブデータを受け取り、描画用パラメータ算出部７０１から描画用パラメータを受け取り、描画判定情報を算出する。描画判定情報とは、ベクタデータが形成する閉領域に各ピクセルの対応位置が含まれるかどうかを判定するための情報であり、ここでは後述する描画判定変数である。この対応位置の判定方法としては、例えば、以下の方法が挙げられる。
【００３１】
１）描画制御用プリミティブデータに含まれる任意の図形データ（ここでは三角形とする）を１つ読み込む。
２）この図形データ、またはこの図形データの一部分が、描画用パラメータ算出部７０１で算出された各ピクセルの対応位置を含むかどうかを調べる。
３）対応位置がこの図形データの内部領域に含まれれば描画判定変数を１とする。
ここで、描画判定変数とは、出力用のラスタデータにピクセルを書き込むかどうかを判定する変数である。また、読み込んだ描画制御用プリミティブが、直線輪郭から生成された三角形の場合と曲線輪郭から生成された三角形の場合とで判定の処理が異なる。
直線輪郭から生成された三角形の場合は、各ピクセルの対応位置が三角形の内部に含まれていれば描画判定変数に１を加算する。
一方、曲線輪郭から生成された三角形の場合、描画制御用プリミティブ生成部１０５での生成ルールによって処理が異なる。第１の条件は、各ピクセルの対応位置が三角形の内部に含まれていれば「真」というものであり、生成ルールによらず共通の条件である。第２の条件は描画制御用プリミティブデータの生成ルールによって異なる。直線輪郭が、制御点を無視してベクタデータに含まれる直線および曲線の始点と終点を線分で結ぶことにより生成される場合、曲線の凸領域内に各ピクセルの対応位置が含まれていれば「真」となる。また、２種類の曲線輪郭により、直線輪郭の生成の際に制御点を含むかどうか切り替える場合、すなわち凸曲線輪郭では制御点を無視して始点と終点との２点を結び、凹曲線輪郭では始点と制御点と終点との３点をこの順番に結び、これらの線分を連結して直線輪郭を生成する場合、凸曲線（曲線の凸領域が図形を表す曲線）の凸領域、あるいは凹曲線（曲線の凹領域が図形を表す曲線）の凹領域の、どちらかに含まれていれば三角形の一部に含まれるものとして「真」となる。これらの２つの条件が「真」である場合に、描画判定変数に１を加算する。なお、ここでは１を加算しているが、奇数であれば１でなくてもよい。
上記１）から３）を、全ての描画制御用プリミティブデータに含まれる全ての図形データ（ここでは三角形）について判定されるまで繰り返すことにより、各ピクセルの対応位置が、描画制御用プリミティブまたは描画制御用プリミティブの一部に含まれると判定された回数が得られる。本実施形態ではこの描画判定変数を描画判定情報とする。
例えば、描画制御用プリミティブが３つの直線輪郭から生成された三角形で構成されており、各ピクセルの対応位置がそのうちの２つの三角形の内部に相当する場合、描画判定変数は２となる。また、ベクタデータが色情報やアルファ値などの情報を保持しており、必要であれば、併せて各ピクセルの対応位置での色情報やアルファ値を算出してもよい。
【００３２】
［ラスタデータ生成部７０３］
ラスタデータ生成部７０３は、描画判定情報算出部７０２から描画判定情報（描画判定変数）および描画用パラメータを受け取り、ピクセル属性情報を用いて画面表示用のラスタデータに書き込みを行うかどうか、すなわち描画するかどうかをピクセルごとに決定して、ラスタデータを生成する。ラスタデータ生成部７０３は、ピクセルの描画判定変数が奇数である場合に、対応位置に対応するピクセルの属性値を描画用パラメータに基づいて生成し、ラスタデータにピクセルを書き込む。このとき、ベクタデータから算出された色情報やアルファ値があれば、すでに算出されているピクセル属性情報の色情報やアルファ値などの該当する部分をベクタデータから算出された値で置き換える、またはすでに算出されているピクセル属性情報の色情報やアルファ値とブレンドするなどの処理を行ってもよい。描画判定変数が奇数であるとは、直線輪郭から生成された描画制御用プリミティブデータ、および曲線輪郭から生成された描画制御用プリミティブデータに定義されている曲線の図形内部側の領域を全てラスタライズした場合に、そのピクセルが奇数回書き込まれるということと等しくなる。これを上記特開２００７−２４１８７８号公報で示されているステンシルデータの生成に置き換えて考えると、ステンシルデータのビット反転が奇数回おこなわれ、０以外の値となり、図形内部と判定されることと等しくなる。これは、上記特開２００７−２４１８７８号公報のステンシルデータと同様の結果を得ることができる。
【００３３】
［ラスタデータ記憶部７０４］
ラスタデータ記憶部７０４は、ラスタデータ生成部７０３からラスタデータを受け取って記憶し、提示部１０８へ送る。ただし、ラスタデータの構成はこの形式に限定されるものではなく、グラフィックスの分野において一般的に利用される他のデータを含んでもよい。
【００３４】
［提示部１０８］
提示部１０８は、出力ラスタデータ生成部１０７からラスタデータを受け取り、必要に応じてスクリーンに表示を行う。
【００３５】
なお、出力ラスタデータ生成部１０７で出力される結果は、ビットマップやＪＰＥＧ、ＧＩＦなどのグラフィックス分野で一般的に用いられる画像形式でラスタデータ記憶部７０４に保存されてもよいし、ネットワークを通じて出力結果、あるいは保存されたデータが転送されてもよい。
さらに図１では、モデル記憶部１０１とベクタデータ記憶部１０４および描画制御用プリミティブ記憶部１０６を異なるブロックとして表記しているが、これらは単一のメモリ上にまとめて構成してもよいし、異なる複数のメモリ上に分割して構成してもよい。
また本実施形態では、ベクタ定義空間は例えば各軸が０から１までの範囲で定義される二次元の空間であるとするが、ベクタ定義空間はこの形式に限定されるものではない。各軸が０から１以外の範囲で定義されてもよい。
以上に示した実施形態によれば、ベクタデータをレンダリングする際に、曲面モデルに含まれる曲面モデル要素のうち、ベクタデータを表現する可能性のある曲面モデル要素を算出して、レンダリングされる曲面モデルとして入力される曲面モデル要素数を削減することにより、ベクタデータを曲面モデル上にレンダリングする際の処理を高速化することができる。
【００３６】
（第１の変形例）
本変形例では、モデル制御情報算出部１０２において三角形が交差、および一方の三角形がもう一方の三角形の内部領域に完全に含まれる状態になっているかを判定する際に、曲面モデル要素とベクタデータとで判定を行うことが上記実施形態とは異なる。上記実施形態では曲面モデル要素に対し描画制御用プリミティブを判定対象としているため、ベクタデータ単位でレンダリング方法を選択する場合にベクタデータの形状によっては余分な領域が判定対象となることがある。本変形例では、曲面モデル要素に対しベクタ図形の輪郭線を判定対象としているので、ベクタデータにあわせて三角形を選択することができる。以下に、上記実施形態とは異なる動作を行うブロックのみ説明する。
【００３７】
描画制御用プリミティブ生成部１０５は、描画制御用プリミティブデータとともにベクタデータを描画制御用プリミティブ記憶部１０６へ送る。
描画制御用プリミティブ記憶部１０６は、描画制御用プリミティブ生成部１０５から受け取った描画制御用プリミティブデータおよびベクタデータを記憶する。
【００３８】
モデル制御情報算出部１０２は、モデル記憶部１０１から所望の曲面モデルおよびベクタデータ定義位置を抽出し、描画制御用プリミティブ記憶部１０６から所望のベクタデータを抽出し、曲面モデル要素ごとに判定をおこない、曲面モデル要素ごとの判定結果を示すモデル制御情報を入力モデル制御部１０３へ送る。なお、モデル制御情報算出部１０２は、ベクタデータ記憶部１０４からベクタデータを受け取ってもよい。
判定方法としては、ベクタデータに含まれる制御点、始点、および終点の接続関係を示すベクタデータ図形（例えば図３）の輪郭線を追跡した場合に出現する、制御点を含む全ての点で構成される多角形と曲面モデル要素とが交差しているかどうか、または、この多角形と曲面モデル要素とについて、一方がもう一方の内部領域に完全に含まれる状態になっているかどうかを判定する。なお、描画制御用プリミティブ記憶部１０６からこの多角形を得てもよい。例えば、曲線輪郭から定義される描画制御用プリミティブ（三角形）と直線輪郭で示される描画制御用プリミティブ（多角形）を上述した判定に用いる多角形として同様の判定を行ってもよい。上述した判定の具体的な判定方法については、例えば“中前栄八郎、西田友是：３次元コンピュータグラフィックス、ｐｐ６３−７２、昭晃堂”に記載されている方法を用いることができるため、ここでの詳細な説明は省略する。
しかしながら、判定方法はこれに限定されるものではなく、曲面モデルがベクタ定義空間に占める領域が、ベクタ図形（例えば図２の図形）が占める領域と重なるかどうかを調べることができればよい。互いに交差している場合と、ベクタデータ図形（例えば図３の図形）の輪郭線を追跡してできる多角形または曲面モデル要素のどちらか一方が、もう一方に含まれている場合とを区別する必要は無く、また描画制御用プリミティブデータが定義されているため、例えば図８に示すフローチャートのような方法でも判定が可能である。
【００３９】
はじめにステップＳ８０１では、曲面モデルからまだ判定がおこなわれていない曲面モデル要素（一般には多角形。例えば三角形。）を選択する。次に、ステップＳ８０２では、曲面モデル要素の各頂点のベクタ定義空間での位置を描画判定情報算出部７０２の対応位置として、上記の描画判定情報算出部７０２の説明と同様の手順で描画判定変数を算出する。描画判定変数が奇数であれば曲面モデル要素の一部は必ずベクタデータ図形の内部領域にあるため、モデル制御情報は「真」となりステップＳ８０６に進む。描画判定変数が偶数の場合は、ステップＳ８０３に進む。
ステップＳ８０３では、ベクタデータ図形の各頂点、制御点のいずれかが曲面モデル要素の内部領域に１つでも含まれるかどうかを調べる。ベクタデータ図形の各頂点、制御点のいずれかが曲面モデル要素の内部領域に１つでも含まれていればモデル制御情報は「真」となりステップＳ８０６に進む。ベクタデータ図形の各頂点、制御点のいずれも曲面モデル要素の内部領域に含まれていない場合は、ステップＳ８０４に進む。ステップＳ８０４では、曲線輪郭から定義される三角形を構成する各稜線または直線輪郭を構成する各稜線と、曲面モデル要素を構成する稜線とが交差しているかどうかを調べる。交差していればモデル制御情報は「真」となりステップＳ８０６に進む。それ以外の場合はステップＳ８０５に進み、モデル制御情報は「偽」となる。
ステップＳ８０７では、曲面モデルに含まれる全ての曲面モデル要素について判定をおこなったかどうかを調べ、全ての曲面モデル要素について判定をおこなったのであれば終了し、まだ判定されていない曲面モデルが存在するのであれば、ステップＳ８０１に戻り、上述した処理を同様に行う。
【００４０】
以上の処理により、入力モデル制御部１０３において本実施形態および第１の変形例を適用したイメージについて図９Ａから図９Ｃを参照して説明する。
図９Ａは「次」という文字に対しレンダリング処理を行う前の、制御処理をおこなっていない状態を示し、図９Ｂおよび図９Ｃはそれぞれ、実施形態適用後および第１の変形例適用後の制御処理をおこなった状態を示す。図９Ａに示す制御処理前の状態よりも図９Ｂに示す実施形態適用後のほうがレンダリングを行うデータが削減されていることがわかる。さらに、図９Ｃに示す第１の変形例適用後はベクタ図形の輪郭線と曲線輪郭から生成された描画制御用プリミティブの稜線を判定対象としているため、「次」の文字を構成するベクタデータに合わせてレンダリングを行うことができ、大幅なデータ削減が可能である。
【００４１】
また、より処理コストと削減される三角形とのバランスを考慮する場合は、Ｓ８０２、およびＳ８０４の処理を変更できる。Ｓ８０２では、曲面モデル要素の各頂点のベクタ定義空間での位置を描画判定情報算出部７０２の対応位置として、上記の描画判定情報算出部７０２の説明と同様の手順で描画判定変数を算出する。ただし、この時の判定には直線輪郭から生成された描画制御用プリミティブを用いる。描画判定変数が奇数であれば曲面モデルの一部は必ず直線輪郭で囲まれた多角形の内部にあるため、モデル制御情報は「真」となる。描画判定変数が偶数の場合、さらに、対応位置が曲線輪郭から生成された描画制御用プリミティブの内部に１つでも含まれるかを調べる。含まれている場合、モデル制御情報は「真」となる。モデル制御情報が「真」の場合にはステップＳ８０６に進む。モデル制御情報が「偽」の場合にはステップＳ８０３に進む。それ以外の場合は「偽」となる。Ｓ８０３は前記した処理と同様の処理を行う。Ｓ８０４では、描画制御用プリミティブの各稜線と曲面モデルを構成する稜線とが交差しているかどうかを調べる。交差していればモデル制御情報は「真」となりステップＳ８０６に進む。それ以外の場合はステップＳ８０５に進み、モデル制御情報は「偽」となる。
【００４２】
以上に示した第１の変形例によれば、上記の実施形態では描画制御用プリミティブを判定対象としていたためベクタデータに凹となる部分がある場合に余分な曲面モデル（三角形）を削減し切れなかったが、本変形例によれば、ベクタデータ図形の輪郭線を判定対象としているため、よりベクタデータにあわせて曲面モデルを削減することができる。
【００４３】
（比較例）
以下、本発明の実施形態との比較例として、特開２００６−１０６７０５号公報および特開２００７−２４１８７８号公報に記載された技術について説明する。
ベクタグラフィックスのラスタライズに要する演算コストを低減するため、ＧＰＵ（グラフィックスプロセッサユニット）が活用されていることについては既に述べた。ＧＰＵを利用して、図２に示すような、直線と曲線で構成されるベクタ図形をラスタライズするための上記特開２００６−１０６７０５号公報の手法をまず説明する。
【００４４】
このラスタライズ手法のフローチャートを図１０に示す。この図から分かるように、上記特開２００６−１０６７０５号公報の手法の処理は、ＣＰＵによる前処理とＧＰＵによる主処理の大きく２段階の処理から成る。最初に、ＣＰＵによってベクタ形式の図形が三角形の集まりに分解され、その後、ＧＰＵによって各三角形がラスタライズされる。ＧＰＵの処理単位は三角形であり、図２のような直線と曲線で構成されるベクタ図形を直接扱うことができないため、このような２段階の処理に分かれている。
最初のステップＳ１００１では、ＨＤＤやＲＡＭなどの記憶媒体からベクタデータを読み込み、その輪郭線を解析する処理がおこなわれる。例えば、図２のベクタ図形を表すベクタ形式のデータは、図３に示すベクタデータ図形に示されるような点と直線を含む。この図３では、図形の直線あるいはパラメトリック曲線の端点を黒丸で表し、パラメトリック曲線の制御点を白丸で表している。ステップＳ１００１では、このようなベクタデータ図形を解析して、図５に示すような２種類の輪郭線データを生成する。
本明細書では、上述したように、図５（ａ）の輪郭線データを「直線輪郭」と表記し、図５（ｂ）の輪郭線データを「曲線輪郭から定義される三角形」と表記している。また、以下では描画制御用プリミティブデータを三角形データ、描画制御用プリミティブを三角形として説明する。
図１０のフローチャートの説明に戻る。ステップＳ１００２では、前のステップで生成された曲線輪郭から定義される三角形に重なりがあるか調べる処理がおこなわれる。その結果、重なりが見つかった場合はステップＳ１００３に進み、重なっている２つの三角形のうちの面積の大きい方を細分割する処理がおこなわれる。
この処理の影響で直線輪郭にも変更が生じるため、次のステップＳ１００４では、直線輪郭を更新する処理がおこなわれる。その後、ステップＳ１００２に戻って再び重なりがあるか調べ、重なりがなければステップＳ１００５に進む。曲線輪郭から定義される三角形に重なりが残っている限り、ステップＳ１００２からＳ１００４の処理が繰り返される。
【００４５】
例えば図５（ｂ）に示す曲線輪郭から定義される三角形の集合の場合、ステップＳ１００２において三角形ａとｂ、および三角形ｃとｄが重なっていることが分かる。ステップＳ１００３では、三角形ａおよびｃが、それぞれ、図１１（ｂ）に示すような２つの三角形ａ０とａ１、およびｃ０とｃ１に細分割される。そしてステップＳ１００４では、図１１（ａ）に示すように直線輪郭を更新する処理がおこなわれる。
ステップＳ１００５では、直線輪郭を構成する各多角形を三角形に分割する処理がおこなわれる。例えば図１１（ａ）の３つの多角形は、図１２に示すような三角形の集まりに分割される。
以上（ステップＳ１００１からＳ１００５）の処理は、全てＣＰＵによる前処理として実行される。
ステップＳ１００６では、直線輪郭を構成する三角形（図１２）および曲線輪郭から定義される三角形を構成する三角形（図１３（ｂ））が、ＧＰＵによってラスタライズされる。このとき、直線輪郭を構成する三角形については、図１３（ａ）に示すように、その三角形の内側にある全てのピクセルがラスタライズされる。
これに対して曲線輪郭から定義される三角形については、図１３（ｂ）に示すように、その三角形の内側にあるピクセルのうち、凹曲線輪郭の凹領域、あるいは凸曲線輪郭の凸領域がラスタライズされる。
このようにして得られた直線輪郭と曲線輪郭から定義される三角形のラスタライズ結果は、ＧＰＵ内部のフレームバッファに併せて記憶される。例えば、図１３（ａ）と図１３（ｂ）は、図１４に示すようなラスタデータとしてフレームバッファに記憶される。
【００４６】
従来のＧＰＵを利用したラスタライズ手法では、複数の三角形を用いて曲線を近似していたため、拡大したときに粗く見えてしまう問題があった。また、より滑らかにラスタライズするためには多数の三角形を用いて曲線の近似精度を上げるしかなく、記憶容量と処理コストの増大が避けられなかった。これに対して上記特開２００６−１０６７０５号公報の手法では、三角形単位ではなく、曲線近傍のピクセル単位に処理するため、解像度に依存せず常に滑らかに曲線をラスタライズすることができる。その上、記憶容量と処理コストも解像度に依存せず、常に少なくて済む。
【００４７】
しかし、上記特開２００６−１０６７０５号公報のラスタライズ手法には以下の２つの問題がある。
１つ目の問題は前処理のコストが高いことである。特に、図１０のステップＳ１００２の曲線輪郭から定義される三角形の重複判定と、ステップＳ１００５の直線輪郭の三角形分割のコストが高い。
前処理のコストは、図形の幾何形状が時間的に変化しない場合であれば大きな問題にはならない。一度前処理をしてしまえば、以降は再び前処理を行う必要はないからである。しかし、動的に図形の幾何形状が変化する場合は、その都度、前処理をやり直さなければならず、ラスタライズ処理全体のボトルネックになることが多い。
２つ目の問題は、アンチエイリアシングのためにアルファブレンドを用いていることである。ここでアンチエイリアシングとは、ラスタライズされた図形の輪郭線に現れるジャギー（階段状のギザギザ）を除去する処理のことである。また、アルファブレンドとはアルファ値と呼ばれる係数を用いて２つのピクセル値を半透明合成する処理のことである。
広く知られているように、アルファブレンドを用いるためには全ての図形をデプス値でソート（デプスソート）し、奥に位置する図形から順番にラスタライズしなければならない。デプスソートは非常にコストが高い処理であり、ラスタライズ処理全体のボトルネックになることが多い。
【００４８】
上記特開２００７−２４１８７８号公報ではこれら２つの問題を解決する方法を提案している。
上記特開２００７−２４１８７８号公報では、ベクタデータに含まれる直線および曲線の始点と終点を単純に線分で結ぶことによって得られる多角形を直線輪郭としている。例えば、図３のベクタデータ図形から解析された直線輪郭は、図１５に示すような３つの多角形Ｐ０、Ｐ１、Ｐ２になる。曲線輪郭から定義される三角形については、上記特開２００６−１０６７０５号公報と同様のものを用いている。
得られた直線輪郭を構成する各多角形について、任意の１点（ピボット）が選択される。そして次に、ピボットと、ピボットを含まない全ての連結する２点を結ぶ三角形を生成する。ここで連結する２点とは、多角形の辺によって結ばれている２つの点のことを意味する。
例えば、図１５の３つの多角形Ｐ０、Ｐ１、Ｐ２において、それぞれ点０、２３、２８がピボットとして選択された場合、図１６に示すような三角形が生成される。三角形が重なっており、この図だけでは三角形の形状を把握することが難しいため、図１７に３つの多角形Ｐ０、Ｐ１、Ｐ２から生成された三角形を構成する３つの点の番号を示す。
なお、図１７はあくまで説明を分かりやすくするための補足であり、三角形データそのものを表しているのではないことに注意する。実際の三角形データは、各三角形を構成する３点の位置座標、およびテクスチャ座標、および接続関係などから構成される。
【００４９】
次に、三角形内部のピクセルをラスタライズすることによってステンシルデータを生成する処理がおこなわれる。なお、ステンシルデータは、最終的に提示する解像度と同じ解像度をもつ画像データである。
まず、直線輪郭から生成される三角形データおよび曲線輪郭から生成される三角形データを読み込み、ラスタライズする。このとき、直線輪郭の三角形については、その三角形の内側にある全てのピクセルがラスタライズされ、これらのピクセル位置に対応するステンシルデータのピクセル値がビット反転される。
一方、曲線輪郭から定義される三角形については、その三角形の内側にあるピクセルのうち、曲線の凸領域に属するピクセルがラスタライズされ、これらのピクセル位置に対応するステンシルデータのピクセル値がビット反転される。
結果として、図形の内部は奇数回ピクセル値がビット反転され、図形の外部は偶数回ピクセル値がビット反転される。
【００５０】
上記の処理によって塗りつぶすピクセルが判断できるため、描画用のラスタデータの対応するピクセルを塗りつぶすことで描画結果を生成することができる。
上記特開２００７−２４１８７８号公報では、直線輪郭の三角形分割などをおこなわないため、ベクタデータの頂点を移動しても三角形データの接続関係が変化しなければ三角形データの対応する頂点座標を書き換えるだけでよく、再度三角形データを作り直す必要はない。そのため、図形の幾何形状が動的に変化しても高速にラスタライズが可能である。
また、描画用のラスタデータのサブピクセル精度の画像を用意し、カバレッジデータをもとにサブピクセルの一部に図形の色を割り当て、最終的な描画用のラスタデータを生成する際に合成することでアルファブレンドが不要なアンチエイリアシングを可能としている。
【００５１】
しかし、上記特開２００６−１０６７０５号公報および特開２００７−２４１８７８号公報に記載された技術では、図形を曲面上にレンダリングしたい場合にそのまま適用することができない。
一般に、多角形データを曲面上にレンダリングする場合、多角形データを微細な多角形データ群に分割することで元の多角形データ内に頂点を追加し、その頂点を移動することによって実現する。上記特開２００７−２４１８７８号公報の方法を利用してベクタデータを曲面上にレンダリングする場合にも、上記特開２００７−２４１８７８号公報で示される方法で生成された三角形データを再分割する必要がある。
三角形データの再分割には様々な方法があるが、十分に曲面に沿っている、つまり曲面上にレンダリングされているといえる描画結果が得られるように再分割する方法の処理コストは高い。
ベクタデータを描画するための三角形データを再分割してしまうため、図形の幾何形状が変化する場合には、その都度、再分割処理をやり直す必要がある。このため、上記特開２００６−１０６７０５号公報の問題点であり、上記特開２００７−２４１８７８号公報の利点である、動的な図形の幾何形状の変化への対応も不可能となる。
【００５２】
なお、本発明は上記実施形態そのままに限定されるものではなく、実施段階ではその要旨を逸脱しない範囲で構成要素を変形して具体化できる。また、上記実施形態に開示されている複数の構成要素の適宜な組み合わせにより、種々の発明を形成できる。例えば、実施形態に示される全構成要素から幾つかの構成要素を削除してもよい。さらに、異なる実施形態にわたる構成要素を適宜組み合わせてもよい。
【符号の説明】
【００５３】
１００・・・描画装置、１０１・・・モデル記憶部、１０２・・・モデル制御情報算出部、１０３・・・入力モデル制御部、１０４・・・ベクタデータ記憶部、１０５・・・描画制御用プリミティブ生成部、１０６・・・描画制御用プリミティブ記憶部、１０７・・・出力ラスタデータ生成部、１０８・・・提示部、６０１、６０３・・・多角形２の内部領域、６０２、６０４・・・多角形１の内部領域、７０１・・描画用パラメータ算出部、７０２・・・描画判定情報算出部、７０３・・・ラスタデータ生成部、７０４・・・ラスタデータ記憶部。
【特許請求の範囲】
【請求項１】
ベクタ形式の図形に対応するベクタデータを記憶している第１記憶手段と、
前記図形を描画するガイドとしての曲面モデルと、該曲面モデルに対応する、前記ベクタデータがレンダリングされることが可能な領域を示すベクタデータ定義位置とを記憶する第２記憶手段と、
前記ベクタデータを輪郭線解析することにより直線輪郭および曲線輪郭のいずれか１以上に対応するデータを含むプリミティブデータを、前記曲面モデルが定義される空間と独立して前記図形を定義するとともに出力するラスタデータのピクセルの属性値を決定するために参照されるベクタ定義空間に生成する第１生成手段と、
前記曲面モデルに含まれる要素ごとに、該要素が前記ベクタ定義空間のどの位置になるかを算出し、ベクタ定義空間で曲面モデルと前記図形に対応するデータとの関係を判定する第１判定手段と、
前記要素ごとに前記第１判定手段の判定結果を参照して、前記複数の要素から採用する要素を決定し、採用する要素を含む再定義曲面モデルを生成する第２生成手段と、
前記再定義曲面モデルと前記プリミティブデータとを参照して、出力するラスタデータのピクセルの属性値を生成する第３生成手段と、を具備することを特徴とする描画装置。
【請求項２】
前記第１判定手段は、前記要素と前記ベクタデータとの関係を判定することを特徴とする請求項１に記載の描画装置。
【請求項３】
前記第１判定手段は、前記ベクタ定義空間での前記要素の占める領域とベクタデータが示す図形が占める領域が重なっているかどうかを判定すること特徴とする請求項２に記載の描画装置。
【請求項４】
前記第１判定手段は、前記要素と前記プリミティブデータとの関係を判定することを特徴とする請求項１に記載の描画装置。
【請求項５】
前記第１判定手段は、前記ベクタ定義空間での前記要素の占める領域と前記プリミティブデータが表すプリミティブが占める領域とが重なっているかを判定することを特徴とする請求項４に記載の描画装置。
【請求項６】
前記第３生成手段は、
前記再定義曲面モデルをスクリーンに投影した際に該再定義曲面モデルの要素が占めるピクセルごとに、ベクタ定義空間における対応位置、色情報、および透明度を含む描画用パラメータを算出する算出手段と、
前記プリミティブデータについて前記対応位置を含むかどうかを判定し、前記対応位置を含むプリミティブデータが前記直線輪郭から生成されたプリミティブデータであれば前記対応位置の描画判定変数に第１値を加算し、前記対応位置を含むプリミティブデータが前記曲線輪郭から生成されたプリミティブデータであり、かつ該対応位置が曲線輪郭の凸領域に含まれるならば、前記描画判定変数に前記第１値を加算する第２判定手段と、
前記描画判定変数が奇数であるならば、前記対応位置に対応するピクセルの属性値を前記描画用パラメータに基づいて生成する第４生成手段と、を含むことを特徴とする請求項１から請求項５のいずれか１項に記載の描画装置。
【請求項７】
前記第３生成手段は、
前記再定義曲面モデルをスクリーンに投影した際に該再定義曲面モデルの要素が占めるピクセルごとに、ベクタ定義空間における対応位置、色情報、および透明度を含む描画用パラメータを算出する算出手段と、
前記プリミティブデータについて前記対応位置を含むかどうかを判定し、前記対応位置を含むプリミティブデータが前記直線輪郭から生成されたプリミティブデータであれば前記対応位置の描画判定変数に第１値を加算し、前記対応位置を含むプリミティブデータが前記曲線輪郭から生成されたプリミティブデータであり、かつ該対応位置が曲線輪郭の凸領域および凹領域のいずれか一方に含まれるならば、前記描画判定変数に前記第１値を加算する第２判定手段と、
前記描画判定変数が奇数であるならば、前記対応位置に対応するピクセルの属性値を前記描画用パラメータに基づいて生成する第４生成手段と、を含むことを特徴とする請求項１から請求項５のいずれか１項に記載の描画装置。
【請求項８】
ベクタ形式の図形に対応するベクタデータを記憶している第１記憶手段を用意し、
前記図形を描画するガイドとしての曲面モデルと、該曲面モデルに対応する、前記ベクタデータがレンダリングされることが可能な領域を示すベクタデータ定義位置とを記憶する第２記憶手段を用意し、
前記ベクタデータを輪郭線解析することにより直線輪郭および曲線輪郭のいずれか１以上に対応するデータを含むプリミティブデータを、前記曲面モデルが定義される空間と独立して前記図形を定義するとともに出力するラスタデータのピクセルの属性値を決定するために参照されるベクタ定義空間に生成し、
前記曲面モデルに含まれる要素ごとに、該要素が前記ベクタ定義空間のどの位置になるかを算出し、ベクタ定義空間で曲面モデルと前記図形に対応するデータとの関係を判定し、
前記要素ごとに判定結果を参照して、前記複数の要素から採用する要素を決定し、採用する要素を含む再定義曲面モデルを生成し、
前記再定義曲面モデルと前記プリミティブデータとを参照して、出力するラスタデータのピクセルの属性値を生成することを特徴とする描画方法。
【請求項１】
ベクタ形式の図形に対応するベクタデータを記憶している第１記憶手段と、
前記図形を描画するガイドとしての曲面モデルと、該曲面モデルに対応する、前記ベクタデータがレンダリングされることが可能な領域を示すベクタデータ定義位置とを記憶する第２記憶手段と、
前記ベクタデータを輪郭線解析することにより直線輪郭および曲線輪郭のいずれか１以上に対応するデータを含むプリミティブデータを、前記曲面モデルが定義される空間と独立して前記図形を定義するとともに出力するラスタデータのピクセルの属性値を決定するために参照されるベクタ定義空間に生成する第１生成手段と、
前記曲面モデルに含まれる要素ごとに、該要素が前記ベクタ定義空間のどの位置になるかを算出し、ベクタ定義空間で曲面モデルと前記図形に対応するデータとの関係を判定する第１判定手段と、
前記要素ごとに前記第１判定手段の判定結果を参照して、前記複数の要素から採用する要素を決定し、採用する要素を含む再定義曲面モデルを生成する第２生成手段と、
前記再定義曲面モデルと前記プリミティブデータとを参照して、出力するラスタデータのピクセルの属性値を生成する第３生成手段と、を具備することを特徴とする描画装置。
【請求項２】
前記第１判定手段は、前記要素と前記ベクタデータとの関係を判定することを特徴とする請求項１に記載の描画装置。
【請求項３】
前記第１判定手段は、前記ベクタ定義空間での前記要素の占める領域とベクタデータが示す図形が占める領域が重なっているかどうかを判定すること特徴とする請求項２に記載の描画装置。
【請求項４】
前記第１判定手段は、前記要素と前記プリミティブデータとの関係を判定することを特徴とする請求項１に記載の描画装置。
【請求項５】
前記第１判定手段は、前記ベクタ定義空間での前記要素の占める領域と前記プリミティブデータが表すプリミティブが占める領域とが重なっているかを判定することを特徴とする請求項４に記載の描画装置。
【請求項６】
前記第３生成手段は、
前記再定義曲面モデルをスクリーンに投影した際に該再定義曲面モデルの要素が占めるピクセルごとに、ベクタ定義空間における対応位置、色情報、および透明度を含む描画用パラメータを算出する算出手段と、
前記プリミティブデータについて前記対応位置を含むかどうかを判定し、前記対応位置を含むプリミティブデータが前記直線輪郭から生成されたプリミティブデータであれば前記対応位置の描画判定変数に第１値を加算し、前記対応位置を含むプリミティブデータが前記曲線輪郭から生成されたプリミティブデータであり、かつ該対応位置が曲線輪郭の凸領域に含まれるならば、前記描画判定変数に前記第１値を加算する第２判定手段と、
前記描画判定変数が奇数であるならば、前記対応位置に対応するピクセルの属性値を前記描画用パラメータに基づいて生成する第４生成手段と、を含むことを特徴とする請求項１から請求項５のいずれか１項に記載の描画装置。
【請求項７】
前記第３生成手段は、
前記再定義曲面モデルをスクリーンに投影した際に該再定義曲面モデルの要素が占めるピクセルごとに、ベクタ定義空間における対応位置、色情報、および透明度を含む描画用パラメータを算出する算出手段と、
前記プリミティブデータについて前記対応位置を含むかどうかを判定し、前記対応位置を含むプリミティブデータが前記直線輪郭から生成されたプリミティブデータであれば前記対応位置の描画判定変数に第１値を加算し、前記対応位置を含むプリミティブデータが前記曲線輪郭から生成されたプリミティブデータであり、かつ該対応位置が曲線輪郭の凸領域および凹領域のいずれか一方に含まれるならば、前記描画判定変数に前記第１値を加算する第２判定手段と、
前記描画判定変数が奇数であるならば、前記対応位置に対応するピクセルの属性値を前記描画用パラメータに基づいて生成する第４生成手段と、を含むことを特徴とする請求項１から請求項５のいずれか１項に記載の描画装置。
【請求項８】
ベクタ形式の図形に対応するベクタデータを記憶している第１記憶手段を用意し、
前記図形を描画するガイドとしての曲面モデルと、該曲面モデルに対応する、前記ベクタデータがレンダリングされることが可能な領域を示すベクタデータ定義位置とを記憶する第２記憶手段を用意し、
前記ベクタデータを輪郭線解析することにより直線輪郭および曲線輪郭のいずれか１以上に対応するデータを含むプリミティブデータを、前記曲面モデルが定義される空間と独立して前記図形を定義するとともに出力するラスタデータのピクセルの属性値を決定するために参照されるベクタ定義空間に生成し、
前記曲面モデルに含まれる要素ごとに、該要素が前記ベクタ定義空間のどの位置になるかを算出し、ベクタ定義空間で曲面モデルと前記図形に対応するデータとの関係を判定し、
前記要素ごとに判定結果を参照して、前記複数の要素から採用する要素を決定し、採用する要素を含む再定義曲面モデルを生成し、
前記再定義曲面モデルと前記プリミティブデータとを参照して、出力するラスタデータのピクセルの属性値を生成することを特徴とする描画方法。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９Ａ】
【図９Ｂ】
【図９Ｃ】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９Ａ】
【図９Ｂ】
【図９Ｃ】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図１５】
【図１６】
【図１７】
【公開番号】特開２０１０−２５６９８６（Ｐ２０１０−２５６９８６Ａ）
【公開日】平成２２年１１月１１日（２０１０．１１．１１）
【国際特許分類】
【出願番号】特願２００９−１０３１３６（Ｐ２００９−１０３１３６）
【出願日】平成２１年４月２１日（２００９．４．２１）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
【公開日】平成２２年１１月１１日（２０１０．１１．１１）
【国際特許分類】
【出願日】平成２１年４月２１日（２００９．４．２１）
【出願人】（０００００３０７８）株式会社東芝 (54,554)
【Ｆターム（参考）】
[ Back to top ]