(57)【要約】  隣接図形の共有辺の２度塗りを防止し、任意形状閉多角形の輪郭線を正確に描画することを目的とし、走査線上の最終塗潰し画素までの画素数を１画素増減させる手段２、描画のための走査線本数を１本増減させる手段３、手段１と手段２との制御に基づいて描画用画素データを出力する手段４を備える。また順次描画される中間段階の図形データを保持するステンシルバッファ５、バッファ５から読み出され、連続する複数の画素データを保持する手段６、手段６内のデータ値の遷移状況を検出する手段７、手段４の出力データと手段６内のデータとの論理演算結果を反転／非反転させてバッファ５に書込む手段８を備える。
2008114320.tif 000002
【特許請求の範囲】
【請求項１】
走査線上の画素の塗潰しによって図形を描画する装置であって、
前記走査線上の最終塗潰し画素までの塗潰し画素数を１画素分増減させる塗潰し画素増減制御手段と、
図形を描画するための走査線の本数を１走査線分増減させる走査線増減制御手段と、
前記塗潰し画素増減制御手段および前記走査線増減制御手段の制御に基づいて、図形を描画するための画素データを出力する画素データ出力手段とを備えることを特徴とする図形描画処理装置。
【請求項２】
前記図形描画処理装置が、描画すべき図形を複数の三角形に分割して描画する処理装置であり、
前記分割された三角形を順次描画するにあたり、新しく描画すべき三角形のどの辺を塗潰すべきかを判定する塗潰し対象辺判定手段をさらに備え、
該塗潰し対象辺判定手段の判定結果に対応して、前記塗潰し画素増減制御手段、および前記走査線増減制御手段が、塗潰し画素の増減と走査線の増減を制御することを特徴とする請求項１記載の図形描画処理装置。
【請求項３】
前記分割された三角形の辺が、前記図形描画のための走査線と平行な上辺または下辺、該走査線と交わる左辺または右辺のいずれかに分類され、
前記塗潰し対象辺判定手段が、該三角形の下辺と、前記走査線上の塗潰し画素の終点となる辺としての右辺とに対して塗潰しの可否の判定を行うことを特徴とする請求項２記載の図形描画処理装置。
【請求項４】
前記塗潰し対象辺判定手段が、前記描画すべき図形が分割された三角形の辺が、該描画すべき図形の内部の辺であるか、該図形の外部との輪郭辺であるかに対応し、かつ前記下辺または右辺であるかに対応して、塗潰しの可否を判定することを特徴とする請求項３記載の図形描画処理装置。
【請求項５】
前記塗潰し対象辺判定手段が、前記輪郭辺か内部辺かの判定に当たり、分割された三角形のすべてに共通な共通判定ルールに加えて、最初に描画すべき先頭三角形に特定のルールと、最後に描画すべき最終三角形に特定のルールとを用いることを特徴とする請求項４記載の図形描画処理装置。
【請求項６】
前記図形描画処理装置において、
最終的に描画されるべき図形に対応して、順次描画される中間段階の図形の画素データを保持するステンシルバッファと、
該ステンシルバッファから読み出され、１本の走査線上で連続する複数の画素の画素データを一時的に保持する連続画素データ保持手段と、
該連続画素データ保持手段に保持されている画素の画素データの塗潰し状態と非塗潰し状態の間での遷移状況を検出する画素データ遷移状況検出手段と、
前記順次描画の過程で新しい図形の描画のために前記描画データ出力手段によって出力される画素データと、前記連続画素データ保持手段に保持されている画素データとの論理演算を行い、前記画素データ遷移状況検出手段によって検出されたデータ遷移状況に対応して、前記論理演算結果の反転／非反転を行って、前記ステンシルバッファに書き戻す画素データ書込み手段とをさらに備えることを特徴とする請求項１記載の図形描画処理装置。
【請求項７】
前記図形描画処理装置において、
最終描画形状の図形に対応して、順次描画される中間段階の図形の画素データを保持するステンシルバッファと、
該ステンシルバッファから読み出され、１本の走査線上で連続する複数の画素の画素データを一時的に保持する連続画素データ保持手段と、
該連続画素データ保持手段に保持されている画素の画素データの塗潰し状態と非塗潰し状態の間での遷移状況を検出する画素データ遷移状況検出手段と、
前記走査線が描画すべき図形に対する最上、または最下の走査線である時、前記画素データ遷移状況検出手段の検出結果に対応して、前記連続画素データ保持手段に保持されている画素データをそのまま前記ステンシルバッファに書き戻す画素データ書込み手段とをさらに備えることを特徴とする請求項１記載の図形描画処理装置。
【請求項８】
前記連続画素データ保持手段に保持されている画素データが、前記連続する２個の画素の画素データであり、
前記画素データ遷移状況検出手段が、該２個の画素の画素データの少なくとも１つが画素の塗潰し状態を示す値であることを検出した時、前記画素データ書込み手段が前記連続画素データ保持手段に保持されている画素データをそのまま前記ステンシルバッファに書き戻すことを特徴とする請求項７記載の図形描画処理装置。
【請求項９】
走査線上の画素の塗潰しによって図形を描画する方法であって、
前記走査線上の最終塗潰し画素までの画素数を１画素分増減させるか否かを決定し、
図形を描画するための走査線を１走査線分増減させるか否かを決定し、
該塗潰し画素数の増減決定結果と走査線本数増減決定結果に対応して、図形を描画するための画素データを出力することを特徴とする図形描画処理方法。
【請求項１０】
走査線上の画素の塗潰しによって図形を描画する方法であって、
前記走査線上の最終塗潰し画素までの画素数を１画素分増減させるか否かを決定し、
図形を描画するための走査線を１走査線分増減させるか否かを決定し、
該塗潰し画素数の増減決定結果と走査線本数増減決定結果に対応して、図形を描画するための画素データを出力し、
該出力された画素データと、最終描画図形に対応して順次描画される中間段階の図形データを保持するステンシルバッファから読み出され、１本の走査線上で連続する複数の画素の画素データとの論理演算を行い、
該連続する複数の画素データの塗潰し状態、非塗潰し状態の間での遷移状況に対応して、前記論理演算の結果を反転／非反転させて前記ステンシルバッファに書き戻すことを特徴とする図形描画処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータグラフィックスを用いた図形描画方式に係り、さらに詳しくは隣接する図形の辺が重なって二重描画されることを防止し、また二重描画を防止しながら凹型形状の部分を含むような任意形状の閉多角形を描画する描画処理装置に関する。
【背景技術】
【０００２】
グラフィックシステムを用いて図形を描画する場合には、描画対象の図形が一般的に三角形の集まりに分割され、図形を構成する画素の塗潰しが行われる。図１は、このような描画方式における描画結果の説明図である。同図においては、ほぼ正方形の図形が左上側の三角形と右下側の三角形との２つに分割され、まず左上側の三角形、すなわち先行三角形を構成する画素の塗潰しが行われた後に、右下側の三角形、すなわち後続三角形を構成する画素の塗潰しが行われる。しかしながらこの場合には、２つの三角形の境界となる辺が共有されており、この辺を構成する画素に対しては２度塗りが行われ、例えば半透明の図形を描画する場合にはこの辺の色が濃くなってしまうという問題点があった。【０００３】
図２は、このような問題点を防止するための一般的な従来方式の説明図である。この第１の従来方式では、一般的に三角形の右端、および下の端に位置する辺（ここでは仮に終端辺と呼ぶことにする）に対しては塗潰しを行わない、すなわち描画を抑止することによって２度塗りの防止が行われる。すなわち図２において先行三角形の右端の辺、すなわち２つの三角形の境界となる辺を構成する画素に対しては、先行三角形の描画時に塗潰し、すなわち描画が抑止され、この辺に対しては、後続三角形の描画時に塗潰しを行うことによって２度塗りを防止することができる。しかしながら図２の方式では、後続三角形の描画時に右端の辺と下端の辺の描画が抑止され、終端辺が塗りつぶされないために描画すべき画像と厳密には一致しない画像になってしまうという問題点があった。【０００４】
図３は、共有辺の２度塗り防止方式の第２の従来例の説明図である。この従来方式では、図２の方式で各三角形を描画した後に、それぞれの三角形の輪郭線をなぞることによって、特に後続三角形の右端、および下端の辺が塗りつぶされないという問題点を解決している。すなわち先行三角形の描画の後に、描画抑止画素を含めてこの三角形の輪郭線を線分でなぞり、また後続三角形描画後に右端、および下端の辺の画素を輪郭線でなぞることによって、描画すべき図形を正確に描画することができる。【０００５】
しかしながらこの方法では輪郭線が部分的に２度塗りされるため、半透明図形に適用することはできず、また三角形の描画と線分の描画のアルゴリズムの違いや演算誤差などによって、三角形と輪郭線との間に隙間が生じたり、それを回避するために輪郭線を太くするなど、輪郭線の頂点の位置を微調整するための工夫が必要であり、さらに三角形描画後に輪郭線をなぞるために、描画データを格納するメモリへのアクセス効率が悪く、性能低下の要因になるという問題点があった。【０００６】
図４から図９は、凹型形状を含むような任意形状の閉多角形を描画するにあたって、図２で説明した第１の従来方式、すなわち右端の辺と下端の辺とを塗りつぶさない方式を用いた場合の問題点の説明図である。【０００７】
このような閉多角形を描画する方法として２つの方法が一般的に知られている。第１の方法は、閉多角形を構成するすべての頂点の座標を再帰的に検索しながら、互いに重ならない多数の三角形に分割し、描画を行うものである。しかしながらこの方法は、ハードウェアで実現することは困難であり、グラフィックスＬＳＩを用いて描画を行うようなシステムには適用できないという問題点がある。【０００８】
第２の方法は、閉多角形を構成する頂点をストリーム的なデータとして受け取り（描画すべき最終形状を知ることなく、システムの処理が行われていく）、入力される頂点を用いて順番に三角形を構築し、三角形相互の重なり合いを意識することなく、三角形の描画を順次行っていく方法である。最終三角形の描画が行われるまでは、途中の描画結果のデータはステンシルバッファに格納され、最終三角形が描かれた後にフレームバッファに色情報付で写像する方法が用いられる。ステンシルバッファへのデータ格納時には、すでに描画済みでステンシルバッファにデータが格納された画素のデータと、これから描画すべき三角形を構成する画素のデータとの間で排他的論理和演算が行われ、その結果が再びステンシルバッファに書き戻されるという手順が続けられる。グラフィックスＬＳＩでは一般的にこの方法が用いられる。【０００９】
図４は、最終的に描画されるべき閉多角形の形状を示す。この形状に対応して、グラフィックスシステムには頂点Ｖ０からＶ１、Ｖ２、Ｖ３、Ｖ４、Ｖ５、Ｖ６の順序で、頂点データがストリーム的に与えられるものとする。なお黒（四角）の部分は塗潰された画素、白（四角）の部分は塗潰されない、すなわち消去された画素を示す。【００１０】
図５は、ステップ１、すなわち最初に入力される３つの頂点Ｖ０、Ｖ１、およびＶ２によって構成される三角形の描画状態である。右端の辺、すなわちＶ０−Ｖ１とＶ１−Ｖ２の辺の画素に対しては塗潰しは行われない。なお太い実線は塗潰された輪郭、太い破線は塗潰されない（消去された）輪郭を示す。【００１１】
図６は、ステップ２、すなわち次に入力された頂点Ｖ３のデータを用いて３つの頂点Ｖ０、Ｖ２、Ｖ３を持つ三角形が描画された状態を示す。同図においてステップ１で描画された三角形と重なる部分については、前述の排他的論理和演算によって画素データが“０”となり、塗潰しの消去が行われる。この三角形の辺Ｖ０−Ｖ２上の画素も排他的論理和演算によって消去される。【００１２】
図７は、次に入力される頂点Ｖ４のデータを用いて三角形Ｖ０−Ｖ３−Ｖ４が描画された状態を示す。すなわちこのステップ３では、ストリーム的に入力される頂点のデータのうちで一番最初の頂点、すなわちＶ０と最も新しく入力された頂点Ｖ４、およびその直前に入力された頂点Ｖ３を用いて三角形が構成され、三角形の描画が行われる。図７では新たに描画された三角形内の画素のうちで、多くの画素に対するデータが排他的論理和演算によって“０”となり、消去された状態となっている。【００１３】
図８はステップ４、すなわち次に入力された頂点Ｖ５のデータを用いて三角形Ｖ０−Ｖ４−Ｖ５が描画された状態を示す。この描画によって図７で描画された形状のうち、下側の塗りつぶされた三角形を構成する画素の消去が行われている。【００１４】
図９は、最後に頂点Ｖ６のデータが入力され、三角形Ｖ０−Ｖ５−Ｖ６が描画された状態を示す。この最終描画状態では、描画すべき最終状態を示す図４と比較して、閉多角形の輪郭のうちで辺Ｖ３−Ｖ４、辺Ｖ４−Ｖ５、および辺Ｖ０−Ｖ６が消去された状態になってしまうという問題点があった。【００１５】
以上において従来技術の問題点について詳細に説明したが、このような図形描画方式に関する従来技術として特許文献１から特許文献３、および非特許文献１の技術がある。特許文献１では、多角形を複数の三角形に分割して描画を行う場合に、分割された各三角形のデータとしてそれぞれの頂点座標と、境界線か分割線のいずれであるかを表わす識別フラグが与えられ、識別フラグに基づいて各三角形の外周線を処理して描画を行うことによって、三角形の外周線データの処理を簡単化することができる外周線描画データ制御方式が開示されている。【００１６】
特許文献２には、多角形の分割によって生ずる複数の三角形の頂点情報を単純な制御方式で出力することによって、分割された各三角形を描画する際に同時に外周線を描画できるようにして、描画処理を高速化するとともに、システムを単純化できる多角形分割描画方法および装置が開示されている。【００１７】
特許文献３には、クリップベクタの個数を向き毎に数えるカウンタ回路と、ドローベクタの個数を向き毎に数えるカウンタ回路と、座標値が塗潰し区間の開始点座標か終了点座標かを判定する判定回路とを並列に設けることによって、塗潰し処理、およびクリップ処理がハードウェア構成によって実現される描画処理装置が開示されている。【００１８】
しかしながらこのような従来技術を用いても、分割された三角形の右端、および下端に位置する辺の画素の塗潰しを回避することによって、終端辺が塗りつぶされない状態となってしまうという問題点や、凹型形状を含む任意形状の閉多角形描画時に図形の輪郭線が過消去されてしまうという問題点を解決することはできなかった。【００１９】
非特許文献１には、ポリゴン（多角形）の縁や頂点を１度だけ描画し、２度描画を防ぐことが記述されているが、その方法の記述は簡単であり、輪郭線の過消去の防止への適用は困難であるという問題点があった。
【特許文献１】特開平７−１０５３９０号「外周線描画データ制御方式」
【特許文献２】特開平７−１６０８９９号「多角形分割描画方法および装置」
【特許文献３】特開２００２−２０８０１７号「描画処理装置」
【非特許文献１】“ＯｐｅｎＧＬプログラミングガイド第２版”、ＯｐｅｎＧＬ策定委員会、松田晃一訳、（株）ピアソン・エデュケーション（２００６年１２月）
【発明の開示】
【００２０】
本発明の目的は、上述の問題点に鑑み、分割三角形の描画に当たり右端、および下端の辺、すなわち終端辺を構成する画素の塗潰しを回避することによって、描画すべき画像と厳密には一致しない画像が描画されてしまうという問題点を解決することと、ステンシルバッファを用いて凹型形状を含む任意形状の閉多角形を描画するに当たって、最終的に描画すべき形状の輪郭辺が過消去されてしまうという問題点を解決することである。
【００２１】
本発明の図形描画処理装置は、走査ライン上の画素の塗潰しを行うことによって図形を描画する装置であり、すくなくとも塗潰し画素増減制御手段、走査線増減制御手段、および描画データ出力手段を備える。
【００２２】
塗潰し画素増減制御手段は、走査線上の最終塗潰し画素を１画素分増減させる制御を行うものであり、例えば１本の走査線上で左側から描画すべき図形上の画素を塗潰していく場合に、例えば三角形の右辺の画素を最終画素として、その塗潰しを行うか否かを制御するものである。
【００２３】
走査線増減制御手段は、図形を描画するための走査線を１走査線分増減させる制御行うものであり、例えば描画対象図形としての三角形の下側の辺であって、走査線と平行な辺を塗潰すか、塗潰さないかに対応して、走査線を１本分増減させる制御を行うものである。
【００２４】
描画データ出力手段は、塗潰し画素増減制御手段と走査線増減制御手段の制御に基づいて、図形を描画するための画素データ、一般に画素の塗潰しのための画素データを出力するものである。
【００２５】
また本発明の図形描画処理装置は、前述の塗潰し画素増減制御手段、走査線増減制御手段、および描画データ出力手段に加えて、さらにステンシルバッファと、連続画素データ保持手段と、画素データ遷移状況検出手段と、画素データ書込み手段とを備える。
【００２６】
ステンシルバッファは、例えば凹型形状を含むような閉多角形の描画にあたって三角形の描画を繰り返す時に、すでに描画済みの図形の画素データを保持するものであり、連続画素データ保持手段はステンシルバッファから読み出され、１本の走査線上で連続する複数の画素、例えば２個の画素の画素データを一時的に保持するものであり、例えばシフトレジスタである。
【００２７】
画素データ遷移状況検出手段は、連続画素データ保持手段に保持されている複数の画素データの塗潰し状態を示す“１”と、非塗潰し（消去）状態を示す“０”の間での画素データの遷移状況を検出するものである。
【００２８】
画素データ書込み手段は、ステンシルバッファに格納されている図形と異なる図形の描画のために描画データ出力手段によって出力される画素データと、連続画素データ保持手段に保持されている画素データとの論理演算を行い、また画素データ遷移状況検出手段によって検出されたデータ遷移状況に対応して、その論理演算の結果をさらに反転／非反転させて、ステンシルバッファに書き戻すものである。
【００２９】
以上のように本発明によれば、例えば正方形状の図形を２つの三角形に分割して描画する場合に、先行三角形の描画時にはその右辺上の画素の描画を抑止し、後続三角形の描画時には右辺、および下辺の描画を抑止しないように、塗潰し画素の増減と、走査線の増減を制御する動作が実行される。
【００３０】
また本発明においては、ステンシルバッファから読み出された画素データと、これから描画すべき図形の描画のために出力された画素データとの論理演算の結果に対して、画素データの遷移状況によっては、その結果のデータをさらに反転させてステンシルバッファに書き戻す動作が行われる。
【００３１】
本発明によれば、例えば描画対象図形を複数の三角形に分割して描画する場合に、画素の２度塗りや、塗りつぶしが行われない状態を防止することが可能となる。また本発明によれば、例えば凹型形状を含む閉多角形の描画において、ステンシルバッファの画素データと新たに描画する図形の画素データとの論理演算結果をさらに反転可能とすることによって、最終描画形状において輪郭線が過消去されることを防止することができる。
【図面の簡単な説明】
【００３２】
【図１】従来における共有辺での２度塗りの問題点の説明図である。
【図２】従来における一般的な２度塗り防止方法の説明図である。
【図３】図２の従来方式における問題点の説明図である。
【図４】凹型形状を含む閉多角形の例である。
【図５】図４の閉多角形の描画ステップ１の説明図である。
【図６】描画ステップ２の説明図である。
【図７】描画ステップ３の説明図である。
【図８】描画ステップ４の説明図である。
【図９】描画ステップ５の説明図である。
【図１０】本発明における図形描画処理装置（その１）の原理構成ブロック図である。
【図１１】本発明における図形描画処理装置（その２）の原理構成ブロック図である。
【図１２】本実施形態における図形描画処理装置の基本構成ブロック図である。
【図１３】本実施形態における三角形の辺の名称の説明図である。
【図１４】第１の実施例における基本的な三角形描画方式の説明図である。
【図１５】第１の実施例における描画対象例としてのトライアングルストリップの説明図である。
【図１６】図１５のトライアングルストリップに対する頂点投入シーケンスと輪郭辺構成頂点組合せルールの説明図である。
【図１７】第１の実施例における描画対象図形の異なる例としてのトライアングルファンの説明図である。
【図１８】図１７のトライアングルファンに対する頂点投入シーケンスと輪郭辺構成頂点組合せルールの説明図である。
【図１９】第１の実施例におけるグラフィックスＬＳＩの詳細構成ブロック図である。
【図２０】図１９におけるラスタライザと画素描画処理モジュールとの詳細構成ブロック図である。
【図２１】図１９における塗潰し対象辺判定器の基本構成ブロック図である。
【図２２】図２１における輪郭辺帰属フラグ作成部（その１）の詳細構成回路図である。
【図２３】図２１における輪郭辺帰属フラグ作成部（その２）の詳細構成回路図である。
【図２４】図２１の右辺または下辺フラグ作成部の詳細構成回路図である。
【図２５】第１の実施例を用いた場合の閉多角形描画時におけるステップ１の説明図である。
【図２６】ステップ２の説明図である。
【図２７】ステップ３の説明図である。
【図２８】ステップ４の説明図である。
【図２９】ステップ５の説明図である。
【図３０】第２の実施例における閉多角形の描画時におけるステップ１の説明図である。
【図３１】ステップ２の説明図である。
【図３２】ステップ３説明図である。
【図３３】ステップ４の説明図である。
【図３４】ステップ５の説明図である。
【図３５】第２の実施例におけるグラフィックスＬＳＩの詳細構成ブロック図である。
【図３６】第２の実施例における閉多角形描画の各ステップにおけるステンシルバッファ更新処理の詳細フローチャートである。
【図３７】ステンシルバッファ画像上への新たな三角形描画処理（その１）の説明図である。
【図３８】新たな三角形描画処理（その２）の説明図である。
【図３９】新たな三角形描画処理（その３）の説明図である。
【図４０】新たな三角形描画処理（その４）の説明図である。
【図４１】新たな三角形描画処理（その５）の説明図である。
【図４２】新たな三角形描画処理（その６）の説明図である。
【図４３】新たな三角形描画処理（その７）の説明図である。
【図４４】新たな三角形描画処理（その８）の説明図である。
【図４５】図３７から図４４の描画処理におけるステンシルバッファ画像データの更新と図３６の処理フローチャートにおける処理経路の説明図である。
【発明を実施するための最良の形態】
【００３３】
図１０、および図１１は、本発明の図形描画処理装置の原理構成ブロック図である。図１０は後述する第１の実施例に対応する図形描画処理装置の原理構成ブロック図であり、図１１は第２の実施例に対応する図形描画処理装置の原理構成ブロック図である。【００３４】
図１０において、図形描画処理装置１は塗潰し画素増減制御手段２、走査線増減制御手段３、および描画データ出力手段４を備える。塗潰し画素増減制御手段２は、図形を描画する走査線上で最終塗潰し画素を１画素分増減させる制御を行うものであり、例えば後述する塗潰しモード切替レジスタの格納内容に対応して、走査線上での画素カウンタ終了値を１画素分増減させるための画素カウンタ終了値セレクタである。【００３５】
走査線増減制御手段３は、例えば三角形の頂点座標に基づいて、三角形を描画するための走査線の本数を算出する走査線範囲算出器の出力する走査線本数ｍの値をそのまま、または１本減少させて、走査線カウンタ終了値を格納するレジスタに与える走査線カウンタ終了値セレクタである。【００３６】
描画データ出力手段４は、塗潰し画素増減制御手段２、および走査線増減制御手段３の制御に基づいて、図形を描画するための画素データ、例えば塗潰しデータを出力するものであり、例えばスパン描画器である。【００３７】
本実施形態においては図形描画処理装置１が、さらに塗潰し対象辺判定手段を備えることができる。すなわち図形描画処理装置１が描画すべき図形を三角形に分割して描画する場合に、塗潰し対象辺判定手段が新しく描画すべき三角形のどの辺を塗潰すべきかを判定し、その判定結果に対応して、塗潰し画素増減制御手段２、および走査線増減制御手段３が、塗潰し画素の増減と走査線の増減を制御することもできる。【００３８】
後述する第２の実施例に対応する図１１では、図形描画処理装置１は図１０における塗潰し画素増減制御手段２、走査線増減制御手段３、および描画データ出力手段４に加えて、ステンシルバッファ５、連続画素データ保持手段６、画素データ遷移状況検出手段７、および画素データ書込み手段８を備える。【００３９】
ステンシルバッファ５は、例えば凹型形状を含む閉多角形の描画において、順次三角形が描画される毎にその描画結果を格納するものであり、連続画素データ保持手段６はステンシルバッファ５から読み出され、図形描画のための１本の走査線上で連続する複数の画素の画素データを一時的に保持するものであり、例えば複数のフリップ・フロップ（ＦＦ）によって構成されるシフトレジスタである。【００４０】
画素データ遷移状況検出手段７は、連続画素データ保持手段６に保持されている複数の画素、例えば２個の画素の画素データの塗潰し状態、すなわち画素データ“１”と、塗潰されていない（消去）状態、すなわち画素データ“０”との間でのデータの遷移状況を検出するものであり、例えば塗潰し遷移検出器である。【００４１】
画素データ書込み手段８は、描画データ出力手段４、例えばスパン描画器によって新たな図形の描画のために出力される画素データと、連続画素データ保持手段６に保持されている画素データとの論理演算を行い、また画素データ遷移状況検出手段７によって検出された画素データの遷移状況に対応して、その論理演算の結果をさらに反転させたデータ、あるいはそのままのデータをステンシルバッファ５に書き戻すものであり、基本的には、例えば論理演算器、画素描画エフェクタ、画素反転境界位相セレクタ、および画素反転境界制御部に相当する。【００４２】
図１２は、本実施形態における描画処理装置の基本構成ブロック図である。同図において図形描画処理装置は、グラフィックスＬＳＩ１０、およびこれに接続されたＣＰＵ１１、グラフィックスメモリ１２、およびディスプレイ１３によって構成されている。ＣＰＵ１１からグラフィックスＬＳＩ１０に対しては制御コマンドと図形データが与えられ、グラフィックスＬＳＩ１０とグラフィックスメモリ１２との間では必要に応じて画素データの入出力が行われ、またグラフィックスＬＳＩ１０からディスプレイ１３に対しては画像データが出力される。【００４３】
グラフィックスＬＳＩ１０は、頂点処理（図形処理）モジュール１５、ラスタライザ１６、画素描画処理モジュール１７、およびディスプレイコントローラ１８を備えている。頂点処理（図形処理）モジュール１５は、例えば分割三角形の辺のうちで塗潰しを行うべき辺と行わない辺とを決定するものであり、ラスタライザ１６は画素単位で画素の塗潰しを行うか否かを決定するものであり、画素描画処理モジュール１７は実際に図形を描画するための画素データをグラフィックスメモリ１２に出力するものである。後述する第２の実施例では、グラフィックスメモリ１２としてのステンシルバッファから描画途中の画素データが読み出され、例えばラスタライザ１６に与えられる。さらにグラフィックスメモリとしての、例えばフレームバッファから読み出された画像データは、ディスプレイコントローラ１８を介してディスプレイ１３に与えられ、図形画像の表示が行われる。【００４４】
図２の従来技術の説明では、三角形の右端、および下端に位置する辺を終端辺と呼び、その終端辺を塗りつぶさないことによって、隣接する三角形に共有される辺の２度塗りを防止することを説明したが、本実施形態では三角形の辺の名称を図１３で示すように統一して実施形態を説明するものとする。図１３では、三角形の上部の辺であり、図形描画に際しての走査ラインの方向と平行な辺を上辺、同様に走査ラインの方向に平行で三角形の下部の辺を下辺と呼ぶことにする。他の辺については左側から図形の走査を行う場合に最初に三角形に達する辺を左辺、走査ラインが三角形から抜ける辺を右辺と呼ぶことにする。【００４５】
以下の説明においては、本発明の実施形態を大きく２つの実施例にわけて説明するものとする。第１の実施例は、図２と図３で説明した三角形の辺の２度塗りを防止するための実施例である。図１４は、この第１の実施例の基本的な考え方の説明図である。第１の実施例では、分割された三角形毎にその右辺、および下辺を塗りつぶすか、塗りつぶさないかを変更可能とすることによって、三角形に共有される辺の２度塗りや、三角形の終端辺の塗潰しもれを防止するものである。【００４６】
図１４において先行三角形を描画するに当たっては、図２と同様にその三角形の右辺の描画が抑止される。そして後続三角形の描画に当たってはその右辺、および下辺の描画抑止は行われず、右辺、及び下辺を構成する画素について塗潰しを行うことによって、先行三角形、および後続三角形の描画において２度塗りを防止するとともに、塗りつぶされない画素の存在を防止することが可能となる。なおこの方式を実現するために、第１の実施例では走査線上の最終塗潰し画素を１画素分増減させることと、図形を描画するための走査線を１本分増減させることを可能とすることによって、隣接する三角形に共有される辺の２度塗り、および終端辺が塗りつぶされない状態の発生を回避することを可能とする。【００４７】
第１の実施例における図形描画処理装置の構成を一般的に説明する前に、描画すべき図形を多数の三角形に分割し、三角形毎に描画を行って最終的に全体の図形を描画する図形の具体例として、トライアングルストリップ、およびトライアングルファンの２つを用いて、図形描画方式の具体例について説明する。【００４８】
図１５は、トライアングルストリップを示す図形の例である。全体としては平行四辺形であるが、図４から図９で説明した閉多角形の描画時と同様に、この平行四辺形を分割した三角形に対応して、三角形の頂点座標がストリーム的に与えられ、この頂点投入シーケンスに従って順次分割された三角形の描画が行われ、最終的に全体としてのトライアングルストリップの描画が行われることになる。【００４９】
図１５においてトライアングルストリップは、全部で８個の三角形、ｔ１からｔ８に分割されるが、これらの三角形の辺のうちで共有される辺、すなわち平行四辺形の輪郭となる辺以外の内部辺は２度塗りリスクのある辺であり、この内部辺とそれ以外の輪郭辺とを区別して描画を行うことによって、内部辺の２度塗りを回避することを可能とする。【００５０】
図１６は、図１５の連続三角形としてのトライアングルストリップの頂点座標がストリーム的に与えられる頂点投入シーケンスに従って、分割三角形のそれぞれに対応する頂点バッファへの頂点座標格納方式と、分割三角形における輪郭辺を構成する頂点の組合せを判定するためのルールの説明図である。【００５１】
図１６において、まず最初のサイクルで頂点ｖ１の座標が与えられ、三角形の３つの頂点に対応する頂点バッファのうちＢ１にその座標が格納され、次のサイクルで頂点ｖ２の座標が与えられ、３つの頂点バッファのうちでＢ２にその座標が格納される。【００５２】
次の３サイクル目で頂点ｖ３の座標が頂点バッファＢ３に格納されると、図１５の先頭三角形ｔ１の３つの頂点が揃ったことになる。ここで輪郭辺を構成する頂点の組合せのルールについて説明する。先頭三角形ｔ１の３つの辺のうちで頂点ｖ１とｖ２とを結ぶ辺、およびｖ１とｖ３とを結ぶ辺が輪郭辺である。頂点ｖ１の座標は、３つのバッファＢ１からＢ３に格納された３つの頂点の座標のうちで最初に格納された最も古い頂点であり、ｖ３の座標は最も新しく格納された頂点の座標であり、ｖ２の座標はこれらの中間の時点で格納された座標である。従って頂点ｖ１とｖ３を結ぶ輪郭辺は、３つの頂点のうち時間的にみて、ｏｌｄｅｓｔ対ｎｅｗｅｓｔの頂点の組み合わせとなる。この組合せは分割された三角形ｔ１からｔ８に対する共通ルールとして使用される。【００５３】
先頭三角形ｔ１には、もう１つの輪郭辺として頂点ｖ１とｖ２とを結ぶ辺が存在する。この辺は先頭三角形に対する輪郭辺構成頂点組合せの特定ルールであり、頂点バッファＢ１に格納されたｏｌｄｅｓｔの頂点とバッファＢ２に格納されたｍｉｄｄｌｅの頂点との組合せを示している。【００５４】
４サイクル目においてバッファＢ１には頂点ｖ４の座標が上書きされる。これによって三角形ｔ２に対する３つの頂点が揃ったことになるが、この三角形における輪郭辺は頂点ｖ２とｖ４とを結ぶ辺であり、この辺は共通ルールとしてのｏｌｄｅｓｔ、すなわち頂点バッファＢ２に格納されている頂点座標と、ｎｅｗｅｓｔ、すなわち頂点バッファＢ１に格納された頂点との組合せとなる。【００５５】
５サイクル目から９サイクル目ではそれぞれ１つの頂点が与えられる。例えば５サイクル目では頂点ｖ５の座標が頂点バッファＢ２に上書きされることによって、分割された三角形ｔ３からｔ７までの３つの頂点がそれぞれ頂点バッファＢ１からＢ３に格納され、それらの三角形の輪郭辺がｏｌｄｅｓｔ対ｎｅｗｅｓｔという共通ルールを用いることによって検出される。【００５６】
最後の１０サイクル目では、頂点バッファＢ１に最後の頂点ｖ１０の座標が格納されることによって最終三角形ｔ８の３つの頂点座標が揃い、共通ルールを用いた頂点ｖ８とｖ１０との組合せによる輪郭辺に加えて、最終三角形に対する特定ルール、すなわちｍｉｄｄｌｅ対ｎｅｗｅｓｔのルールによって頂点バッファＢ３に格納された頂点ｖ９と頂点バッファＢ１に格納された頂点ｖ１０とを結ぶ辺が輪郭辺として検出される。【００５７】
図１７は、連続三角形のもう１つの例としてのトライアングルファンの説明図である。このトライアングルファンでは、基本的に多角形、図１７では八角形の頂点のうち、１つの頂点ｖ１と他の頂点とを次々と結ぶことによって、多角形の連続三角形への分割が行われる。図１５のトライアングルストリップと同様に、多角形全体の輪郭の辺は２度塗りリスクのない辺であり、内部の辺は２度塗りリスクのある辺である。【００５８】
図１８は、トライアングルファンに対する頂点投入シーケンスと、輪郭辺構成頂点組合せの共通ルールと特定ルールとの説明図である。同図において３サイクル目までの頂点バッファの割り当ては図１６におけると同様である。トライアングルファンに対する輪郭辺構成頂点組合せの共通ルールとしてはｍｉｄｄｌｅ対ｎｅｗｅｓｔが用いられ、先頭三角形ｔ１の辺のうちで頂点ｖ２とｖ３が輪郭辺を構成する組合せとして検出される。先頭三角形に対しては、特定ルールとしてｏｌｄｅｓｔ対ｍｉｄｄｌｅも用いられ、頂点ｖ１とｖ２とを結ぶ辺も輪郭辺として検出される。【００５９】
４サイクル目においては頂点ｖ４の座標が与えられるが、トライアングルストリップに対する図１６と異なって、この頂点ｖ４の座標は頂点バッファＢ２に格納され、頂点Ｂ１に格納されている頂点ｖ１の座標はそのままとされる。これは図１７において６個の分割三角形の頂点の１つとしてｖ１が常に用いられるためである。そして共通ルールに対応して頂点ｖ３とｖ４とを結ぶ辺が輪郭辺として検出される。【００６０】
以後７サイクル目までは同様の動作が行われ、３つの三角形ｔ３からｔ５の頂点に対する頂点バッファの割り当てと、共通ルールに従った輪郭辺構成頂点組合せの検出が行われる。【００６１】
最後の８サイクル目において頂点ｖ８の座標が与えられ、最終三角形ｔ６の３つの頂点が揃うことになるが、この最終三角形に対する輪郭辺構成頂点組合せの共通ルールによって頂点ｖ７とｖ８とを結ぶ辺が輪郭辺として検出されるのに加えて、最終三角形に対する特定ルール、すなわちｏｌｄｅｓｔ対ｎｅｗｅｓｔによって、頂点ｖ１とｖ８とを結ぶ辺が輪郭辺として検出される。【００６２】
図１９は、第１の実施例における図形描画処理装置の主要構成部分としてのグラフィックスＬＳＩ１０の内部で、ディスプレイコントローラ１８を除く部分の詳細構成ブロック図、特に頂点処理（図形処理）モジュール１５の詳細構成ブロック図である。同図において、まず描画タイプセレクタ２０によって描画すべき連続三角形がトライアングルストリップであるか、トライアングルファンであるかが描画タイプフラグ２１として出力され、この描画タイプフラグ２１はリセット値リミッタ２２と、後述する塗潰対象辺判定器３５に与えられる。【００６３】
リセット値リミッタ２２は、３進カウンタ２３の出力するカウンタ値に制限を与えるものである。トライアングルストリップに対しては３進カウンタの出力に対する制限は与えられず、３進カウンタ２３はカウント値として１から３までのカウントを繰り返すのに対して、トライアングルファンに対しては最初は１から３までのカウントを行うが、その後はカウント値として“１”を出力せず、“２、３”の出力を繰り返す。これは図１８で説明したように、最初に３つの頂点バッファＢ１からＢ３までに頂点データが格納された後には頂点バッファＢ１の格納データは更新されず、頂点バッファＢ２とＢ３の格納データの更新が行われることに対応している。そしてこの３進カウンタ２３の出力するカウント値が、出力数列セレクタ２４によって数列、すなわちストリーム的なデータとしての頂点バッファインデックスとして頂点バッファ分配器２５に与えられる。【００６４】
リセット値リミッタ２２と頂点バッファ分配器２５に対しては、例えば図１６で説明した頂点投入シーケンスの開始と終了を示すｂｅｇｉｎ／ｅｎｄコマンド２６が与えられ、リセット値リミット動作と、頂点バッファへの頂点データの分配が行われる。また頂点バッファ分配器２５に対しては三角形頂点座標２７が与えられる。【００６５】
頂点バッファ分配器２５から３つの頂点バッファ３０１、３０２、および３０３に対して連続三角形を構成する３つの頂点の座標３２１から３２３が与えられ、また頂点歴フラグ３１１から３１３が格納される。この頂点歴フラグとは、例えば図１６において３つの頂点バッファＢ１からＢ３までのそれぞれがｏｌｄｅｓｔ、ｍｉｄｄｌｅ、またはｎｅｗｅｓｔのいずれの頂点座標を格納しているかを示すフラグである。【００６６】
３つの頂点バッファに格納されている３つの頂点の座標は辺構築器３３、および右辺・下辺判別機構３４に与えられる。辺構築器３３は、３つの頂点バッファ３０１から３０３に格納されている３つの頂点の座標に対応して、３つの辺バッファ４０１から４０３に３つの辺Ｅ１からＥ３を構成するそれぞれ２つの頂点座標４１１から４１３を出力する。【００６７】
３つの頂点の頂点歴フラグ３１１から３１３は塗潰対象辺判定器３５にも与えられる。この塗潰対象辺判定器３５は第１の実施例において最も重要な要素であり、この塗潰対象辺判定器３５には頂点バッファ分配器２５から出力される先頭三角形フラグ２８、最終三角形フラグ２９に加えて、描画タイプフラグ２１がさらに与えられるとともに、右辺・下辺判別機構３５からの右辺帰属フラグ３７、下辺帰属フラグ３８も与えられる。この右辺帰属フラグ３７、下辺帰属フラグ３８は、３つの頂点バッファ３０１から３０３に格納されている３つの頂点のそれぞれの座標に対応して、各頂点が右辺に帰属しているか否か、また下辺に帰属しているか否かを示すフラグであり、２つのフラグが３つの頂点に対応してそれぞれ塗潰対象辺判定器３５に与えられる。【００６８】
塗潰対象辺判定器３５の詳細構成、および動作については後述するが、塗潰対象変判定器３５から３つの辺バッファ４０１から４０３に対して、対応する各辺Ｅ１からＥ３のそれぞれを塗潰すべきか否かを示す辺塗潰フラグ４２１から４２３が出力される。【００６９】
そして辺バッファ４０１から４０３に格納されている３つの辺を構成するそれぞれ２つの頂点の座標４１１から４１３、各辺に対する辺塗潰フラグ４２１から４２３がラスタライザ１６に与えられ、連続三角形のそれぞれを描画するにあたり、塗潰しを行うべきか否かが画素単位に決定されて、その結果が画素描画処理モジュール１７に与えられて、図形の描画を行うためのデータ、すなわち描画データがフレームバッファに格納される。【００７０】
図２０は、図１９のラスタライザ１６、および画素描画処理モジュール１７の詳細構成ブロック図である。同図において、図１９の画素描画処理モジュール１７は基本的にはスパン描画器６１のみに相当し、その他の構成要素はラスタライザ１６を構成する要素に相当する。【００７１】
図２０において、三角形頂点座標２７は走査線範囲算出器５０に与えられる。一方塗潰しモード切替レジスタ５１には、図１９の辺バッファ４０１から４０３に格納された辺塗潰フラグ４２１から４２３のデータが与えられ、そのデータに対応して塗潰しモードの切り替えが行われる。【００７２】
塗潰しモード切替レジスタ５１の出力は、本実施例では走査線カウンタ終了値セレクタ５２と、画素カウンタ終了値セレクタ５３の切替制御のために用いられる。走査線範囲算出器５０からは、三角形を描画するために必要となる最も上の走査線から最も下の走査線までの走査線の本数ｍが出力される。そして最も下の走査線が三角形の下辺に一致しないか、下辺に一致しても塗潰しを行うべき場合には終了値としてｍが、これに対して下辺に一致し、塗潰しを行う必要がない場合にはｍ−１が、走査線カウンタ終了値レジスタ５５に出力される。【００７３】
一方走査線カウンタ開始値レジスタ５４には、走査線範囲算出器５０によって出力された走査線範囲のうちで、最も上の走査線を示す開始値が格納され、２つのレジスタ５４、５５に格納されている開始値と終了値が走査線カウンタ５６に与えられる。走査線カウンタ５６の出力する走査線のカウント値は、三角形頂点座標２７とともに三角形横断面スパン算出器５７に与えられる。走査線が三角形を横断する時のスパン、すなわち画素数ｎが算出され、その値は画素カウンタ終了値セレクタ５３に与えられる。【００７４】
画素カウンタ終了値セレクタ５３は、走査線上の画素のうちで三角形の右辺を構成する画素の塗潰しを行うべき場合には画素カウンタ終了値としてｎを、塗潰しを行うべきでない場合にはｎ−１を画素カウンタ終了値レジスタ５８に出力する。そしてこの終了値は、三角形横断面スパン算出器５７から与えられ、画素カウンタ開始値レジスタ５９に格納された開始値とともに画素カウンタ６０に与えられ、この画素カウンタ６０の出力するカウント値に従って、スパン描画器６１によって各走査線上で塗潰すべき画素に対する画素データが作成されてフレームバッファに格納される。【００７５】
図２１は、図１９の塗潰対象辺判定器３５の基本構成ブロック図である。同図において塗潰対象辺判定器３５は、基本的に輪郭辺帰属フラグ作成部６３、右辺または下辺フラグ作成部６５、および３つのＡＮＤゲート６７１から６７３によって構成される。【００７６】
輪郭辺帰属フラグ作成部６３には、図１９で説明した塗潰対象辺判定器３５への入力のうち、三角形の３つの頂点歴フラグ３１１から３１３、および先頭三角形フラグ２８、最終三角形フラグ２９が与えられる。これらのフラグの入力に対して輪郭辺帰属フラグ作成部６３は、図１９の３つの辺バッファ４０１から４０３に、それぞれ対応する３つの辺Ｅ１からＥ３が輪郭辺であるか否かを示す輪郭辺帰属フラグ６４１から６４３を出力する。【００７７】
右辺または下辺フラグ作成部６５には、図１９の右辺・下辺判別機構３４から出力される三角形の３つの頂点毎の右辺帰属フラグ３７１から３７３、下辺帰属フラグ３８１から３８３が入力され、辺バッファ４０１から４０３にそれぞれ対応する辺Ｅ１からＥ３が右辺または下辺であることを示す右辺・下辺フラグ６６１から６６３が出力される。このフラグは輪郭辺帰属フラグ６４１から６４３とともに、対応する辺毎に３つのＡＮＤゲート６７１から６７３に与えられ、これらのＡＮＤゲートの出力として辺塗潰フラグ４２１から４２３が出力される。なお輪郭辺帰属フラグ作成部６３、右辺または下辺フラグ作成部６５の詳細については後述する。【００７８】
図２２、図２３は、図２１の輪郭辺帰属フラグ作成部６３の詳細構成回路図である。図２２は図１５で説明したトライアングルストリップのデータ構造に対応する輪郭辺帰属フラグ作成部、図２３は図１７で説明したトライアングルファンのデータ構造に対する輪郭辺帰属フラグ作成部の詳細構成回路図である。【００７９】
図２２の輪郭辺帰属フラグ作成部６３の動作について、図１６で説明した輪郭辺構成頂点組合せルールに対応させ、その一部を説明する。まず先頭三角形ｔ１に対する特定ルールに基づいて、ＡＮＤゲート１００、および１０５、ＯＲゲート１１２を介して、辺Ｅ１に対する輪郭辺帰属フラグ６４１が出力される。また先頭三角形に対する共通ルールに基づいて、ＡＮＤゲート１０１、１０６、およびＯＲゲート１１３を介して、辺Ｅ３に対する輪郭辺帰属フラグ６４３が出力される。【００８０】
次の三角形ｔ２に対しては、共通ルールに基づいてＡＮＤゲート１０２、１０７、およびＯＲゲート１１２を介して、辺Ｅ１に対する輪郭辺帰属フラグ６４１が出力される。以下の三角形ｔ３からｔ８に対する動作も同様であり、その説明を省略する。【００８１】
図２３においては、図１８の先頭三角形に対する特定ルールに基づいて、ＡＮＤゲート１２０、１２５、およびＯＲゲート１３０を介して辺Ｅ１に対する輪郭辺帰属フラグ６４１が出力され、また共通ルールに基づいてＡＮＤゲート１２１、１２６、ＯＲゲート１３１を介して、辺Ｅ２に対する輪郭辺帰属フラグ６４２が出力される。以降の三角形に対する動作も同様であり、その説明を省略する。なお図１７のトライアングルファンに対しては、辺Ｅ３に対する輪郭辺帰属フラグ６４３が出力されることはない。【００８２】
図２４は、図２１の右辺または下辺フラグ作成部６５の詳細構成ブロック図である。同図において、例えばＡＮＤゲート１４０からは辺Ｅ１が右辺であることを示す信号が、ＡＮＤゲート１４１からは辺Ｅ１が下辺であることを示す信号が出力され、その結果ＯＲゲート１４６からは辺Ｅ１が右辺または下辺であることを示す右辺・下辺フラグ６６１が出力される。他のフラグ６６２、６６３の出力の動作も同様であり、その説明を省略する。【００８３】
以上において第１の実施例の説明を終わり、続いて第２の実施例について説明する。第２の実施例は、図４から図９で説明した従来技術の問題点、すなわち凹型形状を含むような任意形状の閉多角形を描画する際の問題点を解決するものである。【００８４】
第２の実施例においても第１の実施例における描画方式を基本的に適用するものとする。これによって最終形状を描画する途中の各ステップで各三角形を塗潰す段階では、三角形の輪郭を正しく塗潰すことができるはずであるが、ステンシルバッファに格納されている画素データとの排他的論理和演算を行う過程で輪郭が過消去されてしまうという問題点は残ってしまう。【００８５】
図２５から図２９はこの問題点の説明図である。最終描画形状は図４と同じであり、図２５のステップ１では三角形の輪郭を正しく塗潰すことができるが、ステップ２の図２６においては、２つの三角形の重なりあった部分の輪郭が消去されてしまっている。【００８６】
図２７のステップ３、図２８のステップ４の描画の後に、図２９のステップ５で最終描画形状に対応する描画が完成するが、従来例の図９と比較して過消去される辺の位置は異なるが、輪郭辺が過消去されてしまうという問題点を解決することはできない。【００８７】
第２の実施例は、新しい三角形を正しく塗潰すための画素データと、ステンシルバッファに格納されている画素データとの排他的論理和演算による画素データの過消去を防止するために、ステンシルバッファ内の画素データの遷移形式に対応して、輪郭付近で排他的論理和演算結果の修正を行うことによって、輪郭の過消去を防止するものである。【００８８】
図３０から図３４は、第２の実施例における閉多角形描画ステップを示す。図３０のステップ１では図２５と同様に三角形の輪郭が正しく塗潰され、図３１のステップ２では図２６で過消去された輪郭を構成する画素に対する排他的論理和演算結果の反転を行うことによって、閉多角形の輪郭を正しく塗潰すことができる。以下同様に図３２のステップ３、図３３のステップ４、図３４のステップ５（最終描画形状）において、過消去された輪郭上の画素の画素値を反転させることによって、輪郭を正しく塗潰すことが可能となる。【００８９】
図３５は、第２の実施例において、ディスプレイコントローラ１８を除くグラフィックスＬＳＩ１０の詳細構成ブロック図である。同図を図２０の構成ブロック図と比較すると、左側半分の構成要素に加えて、右側半分の構成要素が追加された形式となっている。その意味で図３５は実質的にラスタライザ１６の詳細構成を示すものであるが、図３５の構成要素のうちで最も左上の走査線範囲算出器５０、塗潰しモード切替レジスタ５１は、頂点処理（図形処理）モジュール１５に対応する要素と考えることもでき、また画素描画処理モジュール１７は最も右下の画素描画エフェクタ７７からステンシルバッファ７０に対する書き込みを行う、図示しないモジュールであると考えることもできる。【００９０】
図３５において、左側のスパン描画器６１までは図２０の構成と同じである。右側に追加された部分は、スパン描画器６１によって、例えば図３１から図３４に示したように新たな三角形を描画しようとする時、その前に描画され、ステンシルバッファ７０に格納されている描画対象画素に対する画素データと、描画しようとする画素データ、基本的には“１”との排他的論理和演算を論理演算器７６によって実行し、その結果を再びステンシルバッファ７０に書き込むための回路であり、また図２６から図２９で説明したような三角形の輪郭の過消去を防ぐためのものである。【００９１】
図３５の右側には、ステンシルバッファ７０から読み出すべき画素のアドレスを生成する画素アドレス生成器７１、ステンシルバッファ７０から走査線上で連続する２画素単位で読み出された画素データを格納するステンシルバッファ画素シフトレジスタ７２（２つのフリップ・フロップ７３、７４によって構成される）、ステンシルバッファ画素シフトレジスタ７２から出力された画素データを論理演算器７６への通常経路に出力するか、あるいは論理演算器７６によるスパン描画器６１の出力データとの論理演算をバイパスして、そのままステンシルバッファ７０に再び書き込む経路に出力する経路セレクタ７５、論理演算器７６による排他的論理和演算結果に対して、三角形の輪郭の過消去を防ぐために、一部の画素データをさらに反転する画素描画エフェクタ７７、ステンシルバッファ７０から読み出された連続する２つの画素の画素データの値によって、画素の塗潰し遷移境界を検出する塗潰し遷移検出器７８、塗潰し遷移検出器７８の出力に応じて画素反転境界（塗潰し遷移境界）を移動させるか否かを決定する画素反転境界位相セレクタ７９、画素反転境界位相セレクタ７９の出力に応じて、画素描画エフェクタ７７による論理演算器７６の出力に対する画素データの反転を制御する画素反転境界制御部８０、ステンシルバッファ７０から読み出されたデータを、経路セレクタ７５から論理演算器７６をバイパスして再びステンシルバッファ７０に書き込ませる制御を行う画素反転キャンセラ８１、画素反転キャンセラ８１に反転キャンセル信号を出力するためのＡＮＤゲート８２、および塗潰し遷移検出器７８とＡＮＤゲート８２の一方の入力との間に接続されるＯＲゲート８３を備えている。【００９２】
画素描画エフェクタ７７は、インバータ８６、３つのＦＦ８７から８９、セレクタ９０を備えている。画素反転境界制御部８０がセレクタ９０の切替を制御することによって、論理演算器７６によって出力される画素データの反転が必要であるか否かに対応して２つのＦＦ８７、８８のいずれかの出力が選択され、後段のＦＦ８９に与えられる動作が行われる。【００９３】
図３５において、ステンシルバッファ７０から１本の走査線上で連続する２画素のデータが画素を１画素ずつずらしながら、ステンシルバッファ画素シフトレジスタ７２に与えられる。説明のため、例えば画素データが“０１０１１０・・・”と並んでいるとすると、最初の読み出し時には“０１”が読み出され、その後“１０”、“０１”、“１１”、“１０”  ．．という順序で画素データが読み出され、読み出された２画素のデータのうちで右側の画素データがＦＦ７３、左側の画素データがＦＦ７４に格納される。【００９４】
塗潰し遷移検出器７８は、この２画素の値が“００”、“０１”、“１０”、“１１”のいずれであるかを検出する。ただし、ここで例えば“０１”は左画素の値が“０”であり、右画素の値が“１”であることを示す。【００９５】
画素反転境界位相セレクタ７９は、この連続する２画素の画素データと、走査線カウンタ５６から出力される最上、または最下の走査線を示すフラグの値によって、画素反転境界を１画素分進めるべきか、遅らせるべきか、あるいは反転境界を移動させることなく論理演算器７６の出力をそのままステンシルバッファに書き込むべきかを示す信号を画素反転境界制御部８０に与える。なおこの画素反転境界については詳細に後述する。【００９６】
一方塗潰し遷移検出器７８によって検出された２画素のデータが“００”でない時に限り、ＯＲゲート８３の出力が“Ｈ”となる。その結果、ＡＮＤゲート８２に対して走査線カウンタ５６から最上・最下走査線フラグが与えられている時にはＡＮＤゲート８２の出力は“Ｈ”となり、画素反転キャンセラ８１の制御によって、経路セレクタ７５はステンシルバッファ画素シフトレジスタ７２から出力される画素データをそのままステンシルバッファ７０に書き込ませるために、バイパス経路に出力する。【００９７】
第２の実施例における図形描画処理装置におけるグラフィックスＬＳＩの詳細構成ブロック図に対応して行われる処理の詳細フローチャートを図３６を用いて説明する。同図において処理が開始されると、まずステップＳ１で三角形頂点座標２７、すなわち頂点バッファの格納内容を用いて走査線範囲が算出され、ステップＳ２で画素の範囲が算出され、ステップＳ３でステンシルバッファ７０から２つの画素の画素データが取得されて、図３５のステンシルバッファ画素シフトレジスタ７２に格納される。その後ステップＳ４からＳ６でスパン描画器６１が描画しようとする画素の位置に応じて分岐した処理が行われる。この分岐は描画対象画素が最上走査線上にあるか、三角形横断面スパン算出器５７によって算出されたスパンの左端にあるか、内部にあるか、右端にあるか、あるいは最下走査線上にあるかによって行われる。【００９８】
さらに連続する２画素の値で分岐した処理が行われる。この２画素はステンシルバッファ画素シフトレジスタ７２に格納され、塗潰し遷移検出器７８によって遷移状況が検出された連続する２画素の値である。これらの画素はスパン描画器６１による描画対象画素にとっては下地の画素とも考えられるため、ここでは下地画素という言葉を用いる。下地画素の値が“００”、“０１”、“１０”、“１１”のいずれであるかによって分岐が行われ、そのまま画素の画素値を反転するか、画素値の反転境界を１画素分遅らせるか、進めるか、あるいは画素値の反転対象から除外するかのいずれかの処理が行われる。【００９９】
ここでスパン描画器６１による描画対象となる画素に対しては、画素データとして当然“１”が与えられる。ステンシルバッファ７０に格納されている同一画素の画素値が“０”であれば論理演算器７６による排他的論理和演算の結果は“１”となり、ステンシルバッファ７０に格納されている画素値が“１”であれば“０”となる。すなわちスパン描画器６１による描画の対象となる画素に対するステンシルバッファ７０の格納内容が反転されることになるが、第２の実施例ではこの反転が行われるか否かの境界を遅らせるか、進めるか、あるいは移動させないかの処理が画素描画エフェクタ７７によって行われることになる。また経路セレクタ７５が下地画素の画素データをバイパス経路に出力する場合が、画素反転対象から除外する動作となる。この画素反転境界については、具体例を用いてさらに詳細に後述する。【０１００】
図３６において続いてステップＳ７でステンシルバッファ７０への画素データの書込み、すなわち画素値の更新が行われ、ステップＳ８で１本の走査線上のすべての画素に対する処理が終了したか否かが判定され、まだ終了していない場合にはステップＳ３からの処理が繰り返される。走査線上のすべての画素に対する処理が終了したと判定されると、ステップＳ９で次の走査線に移行し、ステップＳ１０で図形描画のためのすべての走査線、すなわち最上走査線から最下走査線までのすべての走査線に対する処理が終了したか否かが判定され、終了していない場合にはステップＳ２からの処理が繰り返され、終了している場合には１つの三角形の描画によるステンシルバッファ画素データの更新処理を終了する。【０１０１】
図３５のグラフィックスＬＳＩの動作、および図３６の描画処理フローチャートによる処理について、図３７から図４４に示す動作の具体例を用いてさらに詳細に説明する。またこれらの動作例に対応するステンシルバッファからの読み出しデータ、書き戻しデータ、図３６の処理フローチャートにおける処理の経路を、図４５の画素塗潰しデータ遷移例によって説明する。【０１０２】
具体的な動作例は動作（１）から動作（２０）までの２０個があり、これらの具体例についてすべて説明すると冗長となるので、これらの２０個の動作例のうち特徴的なものを選択して説明する。【０１０３】
まず図３７に示される動作（１）では、以前に描画済みのステンシルバッファ画像に対して新たな三角形を描画するとき、新たに描画する三角形の左辺の画素が塗潰される必要はなく、以前に描画済みのステンシルバッファ画像における対応する境界が消去されるべきことは当然である。【０１０４】
図４５の一番上の段において、ステンシルバッファに格納されている５個のデータは“００＿１＿１１”であるものとする。ここでデータの“１”は塗潰しを、“０”は消去を意味し、＿で挟まれた“１”は、三角形の輪郭、あるいは以前に描画済みのステンシルバッファ画像の塗潰された側の境界となる画素を意味している。【０１０５】
ここで連続する画素のデータは、説明の便宜上５画素分としたものであり、前述のようにステンシルバッファ７０からは２画素分のデータが順次読み込まれて処理が行われる。そこで左側から２つ目と３つ目の画素の値すなわち“０１”が読み込まれた時点で、問題となる境界に達したことになる。３つ目の画素値“１”はこれから描画する三角形から切り取られるスパンの左端の画素のデータである。また２画素の値が“０１”であることから、図３６の処理フローチャートにおいてステップＳ５で経路２と経路１１、ステップＳ６で経路２６がたどられ、この“１”以降の画素のデータがそのまま反転され、ステンシルバッファに書き戻されるデータは“００＿０＿００”となる。この書き戻しデータは、ステンシルバッファに描画済みの画像データを境界以降でそのまま反転する従来例の結果と一致することは当然である。【０１０６】
次に図３８の動作（２）について説明する。同図において、これから描画する三角形の左辺の付近の５つの画素のデータは、例えば“１１＿１＿００”である。この場合の三角形の輪郭、すなわち左辺の位置はスパン左端であるが、このスパン左端に達したことによって変化がおこる２画素分のデータは“１０”であり、図４５の２場面目の段に示すように、ステップＳ５で経路２と経路１２がたどられ、さらに経路２７を経由してステップＳ６で画素反転境界を１画素分遅らせる、すなわち右にずらす動作が行われる。【０１０７】
すなわち従来例では、２画素のデータ“１０”のうちで、左画素のデータを含めてその右側のデータの反転が必要となるが、この画素データの反転を、データ“０”を持つ右画素から行うことによって、画素反転境界をこの左画素と右画素の間に１画素分遅らせる動作が行われ、これによってステンシルバッファに書き戻されるデータは“１１＿１＿１１”となる。これに対して従来例では、ステンシルバッファに書き戻されるデータは“１１＿０＿１１”である。【０１０８】
図３５において、この画素反転境界を１画素分遅らせる動作は画素描画エフェクタ７７によって行われる。この時画素反転境界位相セレクタ７９からは、反転境界を遅らせるべきことを示す値、例えば“−１”が画素反転境界制御部８０に与えられ、この値に対応して画素反転境界制御部８０がセレクタ９０の切替を制御することによって、画素反転境界を１画素分遅らせる動作が行われる。【０１０９】
この場合は、２画素分のデータ“１０”が論理演算器７９によって反転され、“０１”として画素描画エフェクタ７７に与えられるが、左画素に対応する値“０”の入力に対応してセレクタ９０はＦＦ８７側に切り替えられ、次のサイクルでＦＦ８７に格納されていたデータ“１”がＦＦ８９にシフトされる。右画素のデータ“１”の入力に対しては、セレクタ９０はＦＦ８８側に切り替えられ、その結果対応する２画素のデータとして“１１”がステンシルバッファ７０に書き戻されることになる。【０１１０】
次に図４１の動作（９）について説明する。この動作では、これから描画しようとする三角形の内部にステンシルバッファ画像の輪郭が含まれていることになる。図４５でステンシルバッファに格納されている５つの画素のデータを“００＿１＿１１”とする。【０１１１】
図３６のフローチャートでステップＳ５において経路３、経路１５がたどられ、ステップＳ６で経路２７を介して画素反転境界を１画素分遅らせる動作が行われる。すなわち従来例におけるようにこの５つの画素のデータをすべて反転させると、ステンシルバッファ画像の輪郭線が消去されてしまうことになるため、“１１＿１＿００”のデータをステンシルバッファに書き戻すことによって、反転境界を１つ右側の画素との間に移動させる動作が実行される。【０１１２】
次に図３７の動作（１３）について説明する。この動作では、これから描画しようとする三角形の最も上の頂点が最上走査線上に属することになり、この頂点が消去されないような動作が必要となる。ステンシルバッファ内のデータを、“００＿１＿１１”とする。【０１１３】
図３６においては、この頂点が最上走査線上に属することからステップＳ５で経路１と経路７とがたどられ、ステップＳ６で経路２９を介して画素反転対象から除外する動作が行われる。すなわち従来例では、この頂点に対応する画素データ、すなわち５個のデータのうちで中央の画素の画素データ“１”の反転が行われることになるが、それによって頂点が消去されてしまうことになるため、画素データの反転を行わず、ステンシルバッファから読み出されたデータを図３５の経路セレクタ７５によってバイパスし、そのままステンシルバッファ７０に書き戻すことになる。【０１１４】
次に図３８の動作（１４）について説明する。図３７と比較すると、以前に描画済みのステンシルバッファ画像自体が反転されたものとなっており、これに図３７と同一の三角形を描画する動作が行われるが、この動作においても同一の頂点の消去を防止することが必要となる。【０１１５】
ステンシルバッファ内のデータを“１１＿１＿００”とすると、図３６ではステップＳ５で経路１、経路８がたどられ、ステップＳ６で経路２９を介して画素反転対象から除外する動作が行われ、ステンシルバッファ画像の輪郭上、すなわち３個目の画素データの反転は行われず、“１”の値が維持されることになる。【０１１６】
次に図３８の動作（１８）について説明する。前述の動作（１４）と異なる点は、これから描画する三角形の最も下の頂点がステンシルバッファ画像の輪郭上にあることであり、ステンシルバッファ内のデータを“１１＿１＿００”とすると、図３６のステップＳ５で経路５と経路２４がたどられ、ステップＳ６では動作（１４）と同様に経路２９を介して画素反転対象から除外される動作が行われる。【０１１７】
最後に図４０の動作（１９）について説明する。この動作は、これから描画しようとする三角形の最も下の頂点がステンシルバッファ画像の消去領域内にある場合の動作であり、ステンシルバッファ内のデータを“００＿０＿００”とすると、図３５ではステップＳ５で経路５と経路２２がたどられ、ステップＳ６で経路２６を介して、この頂点に対応する画素データの論理演算器７６による反転結果がそのままステンシルバッファに書き戻される。
【図１】
2008114320.tif 000003
【図２】
2008114320.tif 000004
【図３】
2008114320.tif 000005
【図４】
2008114320.tif 000006
【図５】
2008114320.tif 000007
【図６】
2008114320.tif 000008
【図７】
2008114320.tif 000009
【図８】
2008114320.tif 000010
【図９】
2008114320.tif 000011
【図１０】
2008114320.tif 000012
【図１１】
2008114320.tif 000013
【図１２】
2008114320.tif 000014
【図１３】
2008114320.tif 000015
【図１４】
2008114320.tif 000016
【図１５】
2008114320.tif 000017
【図１６】
2008114320.tif 000018
【図１７】
2008114320.tif 000019
【図１８】
2008114320.tif 000020
【図１９】
2008114320.tif 000021
【図２０】
2008114320.tif 000022
【図２１】
2008114320.tif 000023
【図２２】
2008114320.tif 000024
【図２３】
2008114320.tif 000025
【図２４】
2008114320.tif 000026
【図２５】
2008114320.tif 000027
【図２６】
2008114320.tif 000028
【図２７】
2008114320.tif 000029
【図２８】
2008114320.tif 000030
【図２９】
2008114320.tif 000031
【図３０】
2008114320.tif 000032
【図３１】
2008114320.tif 000033
【図３２】
2008114320.tif 000034
【図３３】
2008114320.tif 000035
【図３４】
2008114320.tif 000036
【図３５】
2008114320.tif 000037
【図３６】
2008114320.tif 000038
【図３７】
2008114320.tif 000039
【図３８】
2008114320.tif 000040
【図３９】
2008114320.tif 000041
【図４０】
2008114320.tif 000042
【図４１】
2008114320.tif 000043
【図４２】
2008114320.tif 000044
【図４３】
2008114320.tif 000045
【図４４】
2008114320.tif 000046
【図４５】
2008114320.tif 000047
【国際調査報告】
2008114320.tif 000048
2008114320.tif 000049