(57)【要約】【課題】ベクタグラフィックスにおける閉領域図形の塗潰し処理を行う際に、輪郭線と走査線との交差位置のソートを行う必要が無く、かつ、走査開始位置から最初の交差位置までは塗潰し判定や余分な領域の書換えを行う必要が無くなる塗潰し処理装置を得る。【解決手段】走査線と輪郭線との交差位置と当該交差位置での輪郭線のベクトル方向とを記憶するテーブル４と、走査線毎にテーブル４に記憶されている輪郭線のベクトル方向の異なる一組の交差位置の位置関係および輪郭線のベクトル方向に基づいて塗潰し領域として書換えるか否かを判定した結果を保持する塗潰し判定保持手段７とを備える。これにより、塗潰し処理を行う際に、輪郭線と走査線との交差位置のソートを行う必要が無く、かつ、走査開始位置から最初の交差位置までは塗潰し判定や余分な領域の書換えを行う必要が無くなるので、処理を容易にすることができる。【選択図】        図２
2007248647.tif 000002
【特許請求の範囲】
【請求項１】
ベクタグラフィックスにおける閉領域図形を囲む輪郭線と走査線との交差位置を判定する交差位置判定手段と、
この交差位置判定手段で判定された前記交差位置での前記輪郭線のベクトル方向を判定する輪郭向き判定手段と、
前記交差位置判定手段で判定された前記走査線と前記輪郭線との交差位置と、前記輪郭向き判定手段で判定された前記交差位置での前記輪郭線のベクトル方向とを前記走査線毎にテーブルとして記憶するテーブル記憶手段と、
このテーブル記憶手段によって前記走査線毎に前記テーブルに記憶されている前記輪郭線のベクトル方向の異なる一組の前記交差位置を１つずつ取り出すペア選択手段と、
このペア選択手段により取り出した一組の前記交差位置の間を、当該各交差位置の位置関係および前記輪郭線のベクトル方向に基づいて塗潰し領域として書換えるか否かを判定する書換え処理判定手段と、
この書換え処理判定手段による判定結果を保持する塗潰し判定保持手段と、
この塗潰し判定保持手段に保持された判定結果を予め決められた塗潰し条件と比較して、塗潰し領域を決定する塗潰し条件比較手段と、
この塗潰し条件比較手段により決定された前記塗潰し領域について塗潰し処理を行う塗潰し生成手段と、
を備えることを特徴とする塗潰し処理装置。
【請求項２】
前記書換え処理判定手段は、前記交差位置における前記輪郭線のベクトル方向に応じて１加算するか１減算するかを判定する、
ことを特徴とする請求項１記載の塗潰し処理装置。
【請求項３】
前記テーブルに記憶される前記走査線と前記輪郭線との交差位置の数が多くなり、当該テーブルのサイズを超えてしまい対応できない場合には、塗潰し描画面を分割して前記走査線数を減少させた分をテーブルサイズに割り当てる、
ことを特徴とする請求項１または２記載の塗潰し処理装置。
【請求項４】
表示器と、
ベクタグラフィックスにおける閉領域図形を囲む輪郭線と走査線との交差位置を判定する交差位置判定手段と、
この交差位置判定手段で判定された前記交差位置での前記輪郭線のベクトル方向を判定する輪郭向き判定手段と、
前記交差位置判定手段で判定された前記走査線と前記輪郭線との交差位置と、前記輪郭向き判定手段で判定された前記交差位置での前記輪郭線のベクトル方向とを前記走査線毎にテーブルとして記憶するテーブル記憶手段と、
このテーブル記憶手段によって前記走査線毎に前記テーブルに記憶されている前記輪郭線のベクトル方向の異なる一組の前記交差位置を１つずつ取り出すペア選択手段と、
このペア選択手段により取り出した一組の前記交差位置の間を、当該各交差位置の位置関係および前記輪郭線のベクトル方向に基づいて塗潰し領域として書換えるか否かを判定する書換え処理判定手段と、
この書換え処理判定手段による判定結果を保持する塗潰し判定保持手段と、
この塗潰し判定保持手段に保持された判定結果を予め決められた塗潰し条件と比較して、塗潰し領域を決定する塗潰し条件比較手段と、
この塗潰し条件比較手段により決定された前記塗潰し領域について塗潰し処理を行う塗潰し生成手段と、
この塗潰し生成手段により塗潰し処理が施された前記閉領域図形を前記表示器に表示する表示手段と、
を備えることを特徴とする図形表示装置。
【請求項５】
ベクタグラフィックスにおける閉領域図形を囲む輪郭線と走査線との交差位置を判定する交差位置判定工程と、
この交差位置判定工程で判定された前記交差位置での前記輪郭線のベクトル方向を判定する輪郭向き判定工程と、
前記交差位置判定工程で判定された前記走査線と前記輪郭線との交差位置と、前記輪郭向き判定工程で判定された前記交差位置での前記輪郭線のベクトル方向とを前記走査線毎にテーブルとして記憶するテーブル記憶工程と、
このテーブル記憶工程によって前記走査線毎に前記テーブルに記憶されている前記輪郭線のベクトル方向の異なる一組の前記交差位置を１つずつ取り出すペア選択工程と、
このペア選択工程により取り出した一組の前記交差位置の間を、当該各交差位置の位置関係および前記輪郭線のベクトル方向に基づいて塗潰し領域として書換えるか否かを判定する書換え処理判定工程と、
この書換え処理判定工程による判定結果を保持する塗潰し判定保持工程と、
この塗潰し判定保持工程に保持された判定結果を予め決められた塗潰し条件と比較して、塗潰し領域を決定する塗潰し条件比較工程と、
この塗潰し条件比較工程により決定された前記塗潰し領域について塗潰し処理を行う塗潰し生成工程と、
を含むことを特徴とする塗潰し処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ベクタグラフィックスにおける閉領域図形に対して塗潰し処理を実行する塗潰し処理装置、図形表示装置および塗潰し処理方法に関するものである。
【背景技術】
【０００２】
コンピュータ図形処理のベクタグラフィックスにおける閉領域図形の塗潰しの第１の方法としては、走査線に交差する輪郭線を抽出し、この交差する位置を走査方向にソートして、交差する順番に走査線を辿り、交差位置に辿り着いた場合に、輪郭線のベクトル方向によって加算器に＋１（または−１）し、加算結果に従って走査線方向に向かって塗潰しを行うものがある。
【０００３】
一方、ソートしない第２の方法としては、走査線の開始位置から輪郭線までの領域を輪郭線のベクトル方向によって＋−（またはXOR）で判定バッファを書換える処理を走査線と交差する数だけ実行し、その結果得られた判定バッファの内容に従って塗潰しを行うものもある。
【０００４】
また、特許文献１記載の塗潰し方法によれば、描画面分のマークバッファ（判定バッファ）を用意し、輪郭線に沿って隣接する三角形に分割し、三角形の頂点の向きによってマークバッファ（判定バッファ）の内容を＋、−（ｅ、０）に書き換え、図形の塗潰し領域を判定するようにしている。
【０００５】
【特許文献１】特公平０７−０６０４６５号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、上記第１の塗潰し方法は、輪郭線との交点を走査線毎に毎回抽出し、その交点を走査方向にソートしなければならなく、この処理に大きく処理時間を割いてしまうという問題がある。
【０００７】
また、ソートしない第２の方法としては、描画する領域と同じサイズの判定バッファを用意し、輪郭線分割した１辺を三角形とする領域を判定バッファに反映させ、塗潰し判定を行うが、この場合、描画しない領域に対しても判定バッファの書き換えを行う必要があり、余分な処理をしなければならないという問題がある。
【０００８】
さらに、特許文献１に記載の塗潰し方法においては、マークバッファ（判定バッファ）を描画面分持たなければならないという問題がある。
【０００９】
本発明は、上記に鑑みてなされたものであって、ベクタグラフィックスにおける閉領域図形の塗潰し処理を行う際に、輪郭線と走査線との交差位置のソートを行う必要が無く、かつ、走査開始位置から最初の交差位置までは塗潰し判定や余分な領域の書換えを行う必要が無くなる塗潰し処理装置、図形表示装置および塗潰し処理方法を得ることを目的とする。
【課題を解決するための手段】
【００１０】
上述した課題を解決し、目的を達成するために、本発明は、ベクタグラフィックスにおける閉領域図形を囲む輪郭線と走査線との交差位置を判定する交差位置判定手段と、この交差位置判定手段で判定された前記交差位置での前記輪郭線のベクトル方向を判定する輪郭向き判定手段と、前記交差位置判定手段で判定された前記走査線と前記輪郭線との交差位置と、前記輪郭向き判定手段で判定された前記交差位置での前記輪郭線のベクトル方向とを前記走査線毎にテーブルとして記憶するテーブル記憶手段と、このテーブル記憶手段によって前記走査線毎に前記テーブルに記憶されている前記輪郭線のベクトル方向の異なる一組の前記交差位置を１つずつ取り出すペア選択手段と、このペア選択手段により取り出した一組の前記交差位置の間を、当該各交差位置の位置関係および前記輪郭線のベクトル方向に基づいて塗潰し領域として書換えるか否かを判定する書換え処理判定手段と、この書換え処理判定手段による判定結果を保持する塗潰し判定保持手段と、この塗潰し判定保持手段に保持された判定結果を予め決められた塗潰し条件と比較して、塗潰し領域を決定する塗潰し条件比較手段と、この塗潰し条件比較手段により決定された前記塗潰し領域について塗潰し処理を行う塗潰し生成手段と、を備えることを特徴とする。
【発明の効果】
【００１１】
この発明によれば、走査線と輪郭線との交差位置と当該交差位置での輪郭線のベクトル方向とを記憶するテーブルと、走査線毎にテーブルに記憶されている輪郭線のベクトル方向の異なる一組の交差位置の位置関係および輪郭線のベクトル方向に基づいて塗潰し領域として書換えるか否かを判定した結果を保持する塗潰し判定保持手段とを備えることにより、塗潰し判定保持手段に保持された判定結果に従って描画領域を塗潰すことで、塗潰し処理を行う際に、輪郭線と走査線との交差位置のソートを行う必要が無く、かつ、テーブルに交差位置と当該交差位置での輪郭線のベクトル方向とを記憶しておくことで、走査開始位置から最初の交差位置までは塗潰し判定や余分な領域の書換えを行う必要が無くなるので、処理を容易にすることができる、という効果を奏する。
【発明を実施するための最良の形態】
【００１２】
以下に添付図面を参照して、この発明にかかる塗潰し処理装置、図形表示装置および塗潰し処理方法の最良な実施の形態を詳細に説明する。なお、この実施の形態によりこの発明が限定されるものではない。
【００１３】
本発明の実施の一形態を図１ないし図４に基づいて説明する。図１は、本実施の形態にかかる図形表示装置の構成図である。図１に示すように、ＣＰＵ（Central Processing Unit）１０は装置全体の制御を行うと共に、表示器５１に図形を表示するためのプログラムを実行する。主メモリ１１は、ＣＰＵ１０が処理するデータやプログラムを記憶する。ＣＤ−ＲＯＭコントローラ１２はＣＤ−ＲＯＭの図形情報をアクセスし、通信コントローラ１３は図示しない他の装置との情報を送受する。
【００１４】
グラフィックスプロセッサ２０は、グラフィックスメモリ４０内の表示領域に図形を描画し、さらに描画したデータを読み出して表示器５１に図形を表示する（表示手段）。ＤＡＣ（Digital to Analog Converter）１０は、グラフィックスプロセッサ２０が出力するディジタル形式の表示データをアナログデータに変換する。
【００１５】
グラフィックスメモリ４０を構成する素子としては、ＤＲＡＭを用いるのが望ましい。ＤＲＡＭは他のメモリに比べて、チップ面積に対するトランジスタの集積度が高いためである。また、高速ページモードアクセスというアクセス方式を持っており、アドレスの上位部分（例えばビット９以上）が一致している場合の連続アクセスでは、高速なアクセスが可能になる。
【００１６】
次に、グラフィックスプロセッサ２０の構成と動作の概略を説明する。ＣＰＵＩ／Ｆ２１は、ＣＰＵ１０がシステム制御レジスタ３２等のレジスタ類やグラフィックスメモリ４０をアクセスするための制御を行う。描画ユニット２３は、グラフィックスメモリ４０内のディスプレイリストをフェッチし、そのリストに示されるコマンドに従って描画を行う。パラメータ変換部２２は、必要に応じてコマンドのパラメータを変換する。表示コントローラ２４は、描画ユニット２３が描画したデータを表示するための制御を行なう。
【００１７】
このように、グラフィックスプロセッサ２０はその各要素が何らかの処理を行う度にグラフィックスメモリ４０をアクセスするため、グラフィックスメモリ４０のアクセス効率を高めることが処理速度の向上につながる。そこで、グラフィックスプロセッサ２０は、アクセス要求単位にキャッシュやＦＩＦＯを持つことでアクセス効率を高める。
【００１８】
ＣＰＵ ＦＩＦＯ２５は、ＣＰＵ１０によるグラフィックスメモリ４０のアクセスを高速化する。キャッシュ２６はコマンド専用、キャッシュ２７はテクスチャ専用、キャッシュ２８は描画専用である。また、表示データ用に表示バッファ２９を持つ。
【００１９】
メモリコントローラ３０は、キャッシュ２６〜２８やＣＰＵ ＦＩＦＯ２５等から、グラフィックスメモリ４０に対するアクセス要求を受け付け、その優先順位を決定し、アクセスを制御する。メモリコントローラ３０は表示コントローラ２４からのアクセスを最優先する。しかし、ＣＰＵ１０や描画ユニット２３からのアクセスが行なわれている間は、それらは中断されずに表示コントローラからのアクセスが待たされる。
【００２０】
システム制御レジスタ３２は、グラフィックスプロセッサ２０の動作モードを指定するレジスタである。レジスタ３２は、ＣＰＵ１０のキャッシュモードを指定するＣＡＭ（CPU Access Mode）３２０を有している。
【００２１】
次に、グラフィックスプロセッサ２０およびグラフィックスメモリ４０により構成される塗潰し処理装置における特徴的な機能であるベクタグラフィックスにおける閉領域図形の塗潰し処理について説明する。
【００２２】
ここで、図２は塗潰し処理を実行する塗潰し処理装置の機能構成を示すブロック図である。図２に示すように、塗潰し処理装置は、交差判定器１と、交差位置判定器２と、輪郭向き判定器３と、テーブル４と、ペア選択器５と、書換え処理判定器６と、塗潰し判定バッファ７と、塗潰し条件比較器８と、塗潰し生成器９とから構成されている。
【００２３】
交差判定器１は、走査線と閉領域図形を囲む輪郭線との交差を判定するものである。交差位置判定器２は、走査線と輪郭線の交点の位置（交差位置）を判定する交差位置判定手段として機能するものである。輪郭向き判定器３は、交差位置での輪郭線のベクトル方向を判定する輪郭向き判定手段として機能するものである。そして、テーブル４は、交差位置判定器２および輪郭向き判定器３にて判定された走査線と輪郭線の交点の位置（交差位置）と、交差位置での輪郭線のベクトル方向を走査線毎に記憶する（テーブル記憶手段）。
【００２４】
ペア選択器５は、テーブル４から走査線毎に記憶されている輪郭線のベクトル方向の異なる一組の交差位置を１つずつ取り出すペア選択手段として機能するものである。書換え処理判定器６は、ペア選択器５で取り出した一組の交差位置の間を、当該各交差位置の位置関係および前記輪郭線のベクトル方向に基づいて塗潰し領域として書換えるか否かを判定する書換え処理判定手段として機能するものである。ここでは、交差位置における輪郭線のベクトル方向に応じて１加算するか１減算するかを判定するものである。そして、塗潰し判定バッファ７は、書換え処理判定器６で判定した加減結果を保持する塗潰し判定保持手段として機能する。なお、塗潰し判定バッファ７は、描画するピクセルと同じ数あり、処理前は全て０で初期化されている。
【００２５】
塗潰し条件比較器８は、塗潰し判定バッファ７に保持されている判定結果を予め決められた塗潰し条件と比較して塗潰し領域を決定する塗潰し条件比較手段として機能するものである。塗潰し生成器９は、塗潰し条件比較器８から出力される制御信号によって塗潰し処理を行う塗潰し生成手段として機能するものである。
【００２６】
次に、塗潰し処理装置における動作について説明する。
【００２７】
直線や曲線の組み合わせで描いた図形の輪郭線などのデータを記録しているベクタグラフィックスにおいて、図３に示すように、閉領域を示す輪郭線の終了位置は開始位置と同じ位置となる。開始位置から輪郭線の向きに辿って、交差判定器１で走査線と輪郭線との交差を判定する毎に、その交点の位置と交差位置での輪郭線のベクトル方向をテーブル４に記憶する。
【００２８】
ここで、図４はテーブル４の一例を示す模式図である。図４に示すテーブル４は、交差位置判定器２によって判定した走査線と輪郭線との交点の位置と輪郭向き判定器３によって判定した交差位置での輪郭線のベクトル方向を記憶している。より具体的には、図３で示す閉領域の輪郭線に対して、走査線Ａ、走査線Ｂ、走査線Ｃについてテーブル４に保持される内容を図４に示している。以下において、詳述する。
【００２９】
輪郭線の開始位置（図３参照）から輪郭線の向き（図中、→で示す）に辿り、走査線Ｂに対する交差位置１０８が交差位置判定器２によって判定されるとともに、輪郭向き判定器３によって交差位置での輪郭線のベクトル方向が下から上方向であると判定される。次に、走査線Ａに対する交差位置１０４が交差位置判定器２によって判定されるとともに、輪郭向き判定器３によって交差位置での輪郭線のベクトル方向が下から上方向であると判定される。次に、走査線Ａに対する交差位置１０１が交差位置判定器２によって判定されるとともに、輪郭向き判定器３によって交差位置での輪郭線のベクトル方向が上から下方向であると判定される。このようにして開始位置に戻るまで、交点の位置と交差位置での輪郭線のベクトル方向が判定され、テーブル４に記憶される。すなわち、図３では輪郭線に沿って走査線Ａ，Ｂ，Ｃに交差した順番で、１０８，１０４，１０１，１０６，１０７，１０３，１０２，１０５，１１０，１０９の順でテーブル４に記憶される。
【００３０】
続いて、輪郭線のベクトル方向が異なる一組の交差位置が、ペア選択器５によってテーブル４からペアとして選択される。例えば、図３に示す走査線Ａでは、交差位置１０４と１０１、１０３と１０２の２つのペアがある。
【００３１】
次に、書換え処理判定器６では、ペア選択器５によって選択されたペアの位置（輪郭線のベクトル方向が異なる一組の交差位置）を比較し、下から上方向の位置が大きい場合はその領域の塗潰し判定バッファ７の内容を１加算し、上から下方向の位置が大きい場合は塗潰し判定バッファ７の内容を１減算する。
【００３２】
例えば、図３に示す走査線Ａの交差位置１０４と１０１の領域では、下から上方向の１０４の方の交差位置が大きいことから、この領域については塗潰し判定バッファ７において１加算し、交差位置１０３と１０２では下から上方向の１０３方の交差位置が１０２よりも大きいことから、この領域については塗潰し判定バッファ７において１加算する。この結果、走査線Ａの塗潰し判定バッファ７の内容は、１０１から１０２の領域は＋１、１０２から１０３の領域は＋２、１０３から１０４の領域は＋１となる。
【００３３】
走査線Ｂでは、交差位置１０８と１０６、１０５と１０７の２つのペアがある。交差位置１０８と１０６の領域では、下から上方向の１０８の方の交差位置が大きいことから、この領域の塗潰し判定バッファ７の内容を１加算し、交差位置１０５と１０７では下から上方向の１０７の位置が１０５よりも大きいことから、この領域の塗潰し判定バッファ７の内容を１加算する。この結果、走査線Ｂの塗潰し判定バッファの内容は、１０５から１０６の領域は＋１、１０６から１０７の領域は＋２、１０７から１０８の領域は＋１となる。
【００３４】
走査線Ｃでは、交差位置１１０と１０９の１つのペアがある。交差位置１１０と１０９の領域では、下から上方向の１０９の方の交差位置が小さいことから、この領域の塗潰し判定バッファ７の内容を１減算する。この結果、走査線Ｃの塗潰し判定バッファ７の内容は、１０９から１１０の領域は−１となる。
【００３５】
このような塗潰し判定バッファ７の判定結果を予め決められた塗潰し条件と塗潰し条件比較器８で比較して、塗潰し領域を決定する。塗潰し条件としては、ノン・ゼロ・ワインディグ方式である本実施の形態の場合には、０以外の領域を塗潰すことになる。なお、イーブン・オッド方式を採用している場合には、奇数領域を塗潰すことになる。塗潰し条件比較器８は、塗潰し領域を決定した場合には、その塗潰し領域に対する塗潰し制御信号を塗潰し生成器９に出力し、ピクセルの塗潰しを実施する。このような塗潰し処理を走査線全てに実行することにより、閉領域の塗潰すことができる。
【００３６】
このように本実施の形態によれば、走査線と輪郭線との交差位置と当該交差位置での輪郭線のベクトル方向とを記憶するテーブル４と、走査線毎にテーブル４に記憶されている輪郭線のベクトル方向の異なる一組の交差位置の位置関係および輪郭線のベクトル方向に基づいて塗潰し領域として書換えるか否かを判定した結果を保持する塗潰し判定バッファ７とを備えることにより、塗潰し判定バッファ７に保持された判定結果に従って描画領域を塗潰すことで、塗潰し処理を行う際に輪郭線と走査線との交差位置のソートを行う必要が無く、かつ、テーブル４に交差位置と当該交差位置での輪郭線のベクトル方向とを記憶しておくことで、走査開始位置から最初の交差位置までは塗潰し判定や余分な領域の書換えを行う必要が無くなるので、処理を容易にすることができる。
【００３７】
また、書換え処理判定手段は、走査線と輪郭線との交差位置のベクトル方向を求め、このベクトル方向に応じて１加算するか１減算するかを判定することにより、輪郭線同士が交差していても、輪郭線内の塗り残しが生じない。
【００３８】
なお、テーブル４に記憶される走査線と輪郭線の交点の位置（交差位置）の数は、図形によって数が変わる。また、走査線と輪郭線の交点の位置（交差位置）と交差位置での輪郭線のベクトル方向を記憶するテーブル４の領域は有限であることが多い。したがって、複雑な図形の場合には、走査線と輪郭線の交点の位置（交差位置）の数が多くなり、テーブル４のサイズを超えてしまい対応できないことが考えられる。
【００３９】
そこで、このような場合には、塗潰し描画面を分割することにより、走査線数を減少させた分を有限であるテーブルサイズに割り当てることで、複雑な図形に対応することができる。
【産業上の利用可能性】
【００４０】
以上のように、本発明にかかる塗潰し処理装置、図形表示装置および塗潰し処理方法は、グラフィックスプロセッサにおけるベクタグラフィックスの高速化に適している。
【図面の簡単な説明】
【００４１】
【図１】本実施の形態にかかる図形表示装置の構成図である。
【図２】塗潰し処理を実行する塗潰し処理装置の機能構成を示すブロック図である。
【図３】閉領域を示す輪郭線と走査線との交差を示す模式図である。
【図４】テーブルの一例を示す模式図である。
【符号の説明】
【００４２】
２      交差位置判定手段
３      輪郭向き判定手段
４      テーブル
５      ペア選択手段
６      書換え処理判定手段
７      塗潰し判定保持手段
８      塗潰し条件比較手段
９      塗潰し生成手段
５１      表示器
【図１】
2007248647.tif 000003
【図２】
2007248647.tif 000004
【図３】
2007248647.tif 000005
【図４】
2007248647.tif 000006