(57)【要約】      （修正有）【課題】交差領域の頂点列算出と重心計算の高速アルゴリズムと、その論理回路化を提供する。【解決手段】任意角数の多角形の重心点を求めるため外郭線とグリッド辺との交点座標値と外郭線の傾きをアドレスとするメモリを用い、メモリには予めあらゆる交差条件を記憶して、前記領域の頂点列を出力する手段と、外郭線の頂点がグリッド内に位置する場合の直線の交点を計算する手段とを合わせて、任意角数の多角形頂点列を得る手段と、この頂点列を逐次受けて、パイプライン並列構造により、テキスチャーマッピング座標値、面法線、光源入射ベクトル、視線ベクトルなどのポリゴン頂点定義情報を含む重心点での値を高速に求めるそれぞれの手段をもって前記課題を解決する。【選択図】図４
2008152742.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータグラフィックス描画において、ポリゴン境界上にある画素の輝度を決定するための手段として、前記画素を正方形（以下グリッドという）と見なし、ポリゴン外郭線が前記グリッドと交差し、外郭線とグリッド辺とで囲まれた領域（以下交差領域という）の重心を輝度決定のための参照点とする手段と、前記重心を求める手段として、前記外郭線とグリッド辺との交点座標値、外郭線の傾きおよび外郭線の左右辺をそれぞれアドレスとしたメモリを設け、前記メモリには、予め前記アドレス値を用いた外郭線全てのグリッド辺との交差条件を求め、グリッド辺との交点座標値および交差領域内のグリッド頂点列を記憶する手段と、前記交点座標値および頂点列を受けて、ポリゴン内挿補間の歩進毎に逐次グリッド内の重心を求めるそれぞれの手段からなるポリゴン輝度参照点決定回路。
【請求項２】
請求項１の回路において、前記メモリ出力にはグリッド頂点が交差領域に含まれるか否かを示すグリッド頂点それぞれのフラグビットを設け、複数の外郭線がグリッドに交差する場合、外郭線毎に前記メモリをアクセスして前記フラグを比較し、すべての外郭線でフラグが交差領域内であることを示すグリッド頂点が、複数の外郭線とグリッド辺とが成す交差領域に含まれるものとするポリゴン輝度参照点決定回路。
【請求項３】
請求項１の回路においてポリゴン頂点に定義されるテキスチャーマッピング座標値、面法線、光源入射ベクトル、視線ベクトルについても交差領域のそれぞれの頂点における前記それぞれの値を求め、さらにそれら頂点列から重心計算によって得た値を輝度決定に用いるポリゴン輝度参照点決定回路。
【請求項４】
請求項１の回路において、ポリゴン頂点に定義されるテキスチャーマッピング座標値、面法線、光源入射ベクトル、視線ベクトル等の属性値に関し、ｘおよびｙ座標値の変移量に対する前記それぞれの属性値の変移量を内挿補間時に求め、ｘおよびｙの重心座標値を求めた後、グリッド原点から重心まで変差値を前記それぞれの属性変移量に乗算して、それぞれの属性値の重心点における値を求めるポリゴン輝度参照点決定回路。
【請求項５】
請求項１から４までに記載のポリゴン輝度参照点決定回路を用いたコンピュータグラフィックス画像装置。
【発明の詳細な説明】
【技術分野】
【００１】  この発明は、コンピュータグラフィックスの描画技術に関し、ポリゴンの外郭線が通過する画素領域内におけるポリゴン面の輝度参照点を決定するための論理回路およびその回路を搭載した装置の分野に属する。
【背景技術】
【００２】  ポリゴンの塗りつぶしにおいて、外郭線や頂点を含むポリゴン境界上の画素（以下グリッドという）の輝度を決定するための処理は、エイリアスを軽減する重要な課題である。外郭線（シルエットライン）のアンチエイリアス技術として特願２００５−３３６１２や特願２００５−３５９５６８があり、また従来からのアンチエイリアス技術としてスーパーサンプリング、Ａ−Ｂｕｆｆｅｒ、バウンダリーエッジ法などが知られている。ポリゴンの外郭線や境界をもつグリッドの輝度（カラー値）を決定する手段として、いずれもグリッド内に占めるポリゴンや背景となる領域の面積を求め、これらの面積比に比例して、それぞれの領域が持つ輝度をブレンディングする方法でエイリアスを軽減した。面積を算出する方法として、スーパーサンプリングのように、画素を細分（サブピクセル）化し解像度を高める方法、また外郭線や面が互いに交差するグリッドに対してのみ、グリッド空間をフラグメント化やサブピクセル細分化した方法等が過去に示されているが、ポリゴン外郭線とグリッド辺に囲まれた領域内（以下交差領域という）のどの点をその領域を代表する輝度とするかは明確ではない。輝度を決定する主な情報はｘ、ｙ、ｚ座標値だけではなく、頂点に定義した属性があり、その属性にはテキスチャー座標値、面法線、光源入射角、視線角、面接線などが含まれる。一般にポリゴン面の輝度は、テキスチャーマッピングされた色と、前記それぞれの頂点定義属性値から導かれる反射光に支配される。ポリゴン境界では、ポリゴン外郭線とグリッド辺に囲まれた領域の大小に関りなく、その領域内で顕著な色変化をもつ場合にはエイリアスが発生する。テキスチャーマッピングはポリゴンのそれぞれの頂点にテキスチャー座標値を定義し、この座標値を線形に内挿補間してポリゴン内部の点を決定する。この際、テキスチャー座標値はｘあるいはｙ座標との直線式として補間され、通常テキスチャー座標値はグリッド原点（グリッドの中央あるいはグリッドの頂点の一つ）に丸められる。この結果、グリッド原点が交差するポリゴンの外郭線の外側となる場合、丸められたテキスチャー座標値はポリゴン外部の座標点となり、テキスチャーパターンの記憶されたメモリからは誤った情報を読み出すことになる。外郭線がグリッドに交差する様態は、（１）グリッド原点、（２）外郭線のグリッド入力点（外郭線がグリッド辺と交わる点）、（３）外郭線のグリッド出力点（外郭線がグリッド辺と交わる点）、（４）外郭線とグリッド辺に囲まれた領域の内にあるグリッド頂点の一つ、などがあり、参照点としてそれらの一つが決定される。線形補間以外に特別な計算処理なくして、テキスチャー座標点を得るには前記（１）あるいは（２）となるが、この点を参照点に固定すると、前記の外郭線とグリッド辺で囲まれた領域外部の点となることがある。（２）および（３）による座標値は直線補間式から容易に導出できるが、その点がグリッド内領域の正しい参照点である保証はない。また（２）および（３）のそれぞれの点を結ぶ中点を参照点とすることもその領域の輝度を決定する座標点として正しいとは言えない。（４）は参照点が必ずポリゴン内部となる意味で、ポリゴン外部の輝度を参照してしま���誤りは回避できるが、その点が常に正確な参照点であるとは言えない。すなわち領域の輝度を１点の参照点から決定する限り、常に誤りあるいは誤差を含む。
一方、テキスチャーパターン座標値だけでなく、ポリゴン頂点に定義された前記属性値についても、その参照点をどこにするのかは高品質な映像を描画するためには重要となる。
【発明の開示】
【発明が解決しようとする課題】
【００３】  本発明は、交差領域の参照点を、交差領域の重心と定める。重心は確率的に誤差の少ない多角形内の参照点となることと、常に多角形内部の点となり、前記の問題点の一部を解決する。３角形ポリゴンでは頂点を含む外郭線がグリッド辺と交差し、その結果グリッド内の多角形領域は、交差条件により３角形から最大７角形（頂点）までとなる。本発明では、このグリッド辺との交差条件により変化する頂点列の算出と、その頂点列に基づいて重心を求めるが、重心計算は、ポリゴン内挿補間から輝度決定までの間で、グリッド毎に行う必要があり、実時間システムでは高速なアルゴリズムが要求される。本発明ではこれら交差領域の頂点列算出と重心計算の高速アルゴリズムと、その論理回路化を課題とする。
【課題を解決するための手段】
【００４】  外郭線とグリッド辺との交差領域の輝度を決定する方法として、領域のそれぞれの頂点における輝度を求め、その平均値を取る方法が好ましい。しかしこの方法は計算負荷が重く、実時間性が困難となるか、あるいはハードウエアコストの増大が避けられない。本発明では輝度決定の参照点は領域内で１点とし、その参照点を交差領域の重心と定め、重心（ｘｇ、ｙｇ）をｎ多角形の頂点列から式（１）により求める。
2008152742.tif 000003
（１）式でｘｉ、ｙｉ、ｘｉ＋１，ｙｉ＋１は連続する頂点座標値を示す。ポリゴン（３角形）外郭線とグリッド辺との交差では３角形から最大７角形までの多角形が生じるため（１）式のｎは最大７となる。グリッドの外郭線や領域は３次元座標系で与えられるが、交差領域の重心は視点座標に投影された２次元空間に設定しｘｙ座標上で求めるものとする。【００５】  本発明では交差領域の頂点列を、下記の（１）−（４）に示すそれぞれの手段で求める。内挿補間を行う段階のポリゴンは３角形とし、外郭線は３角形のｙ軸最小値から左右両外郭線に沿って頂点間を補間し、その後水平軸と交わる外郭線両端点間を補間して３角形の内部を塗りつぶすものとする。
（１）外郭線情報は少なくとも、外郭線とグリッド辺との交点座標値、外郭線傾き、および外郭線の左右辺のそれぞれとする。前記交点座標値は、交差するグリッド辺上の座標値（例えば４ビット）と、グリッド４辺を示す２ビットで表す。交点座標値と外郭線の傾きの精度は、通常４ビット程度で十分なアンチエイリアスが得られる。この結果、外郭線１本当たりの外郭線交差情報は１１ビット程度とする。ただしこのビット数はより高い解像度が必要な場合は増加する。
（２）外郭線情報から、交差領域に含まれる頂点列を求める手段として、本発明では外郭線情報をアドレスとするテーブルを設ける。このテーブルには予め、外郭線に対する全てのグリッド辺との交点座標値と、交差領域に含まれるグリッド頂点を示す情報を記憶する。外郭線情報が１１ビットの場合、２Ｋワードの容量からなるメモリに、外郭線の全ての傾きとグリッドへの侵入交点座標値から出力交点座標値と、ポリゴン領域内となるグリッド頂点を予め計算して記憶させ、外郭線毎に、このテーブルを参照して、それぞれの外郭線の内側方向に含まれる頂点列（交点とグリッド頂点）を読み出す。出力される頂点列は１本の外郭線とグリッド辺とが成す交差領域内に含まれるものであり、複数の外郭線からなる場合は、外郭線毎に独立して領域内頂点を求め、その後下記の手段によってすべての外郭線とグリッド辺に囲まれた頂点列を得る。
（３）テーブルから出力されるグリッド頂点情報についてはグリッド頂点は４つであり、１頂点１ビットとして内側であれば１、外側であれば０として表現できる。これを外郭線毎に読み出して例えばＡＮＤ（論理演算）を取り、１となった頂点が交差領域内のものとなる。外郭線がグリッド辺と交わる点は、それぞれの交差領域の内部に位置する。また３角形の頂点がグリッド内に含まれる場合は、外郭線それぞれの直線式の連立方程式を解くことで交点は求まる。この２直線の交点計算の有無は、外郭線補間段階において３角形頂点を含むグリッドとして外郭線情報の一つに頂点の有無を記憶しておくことで、グリッド内に頂点があるか否かの判断が容易となる。直線どうしの交点のグリッド内外判定はグリッド境界が０か１しかないため容易に比較することができる。さらに直線の交点計算は、グリッド内の外郭線の精度が４ビット程度であり、テーブル、乗算器および加減算器を用いたとしてもそれらのビット数は低くてよく、ハードウエアコストは小さい。
以上の処理から交差領域（多角形）の頂点列が求まり、前記（１）式の演算処理に移ることになる。（１）から（３）までの処理はパイプラインで逐次処理が可能である。【００６】  交差領域の頂点数は３から７まで取り得るが、本発明では前記［００５］の処理によって得た頂点列をレジスタに記憶し、これを逐次読み出して（１）式を解くための論理回路に加える。本発明の論理回路は、後記の実施例に示すように四則演算器のパイプライン処理と並列動作が可能な構造となる。この結果、要求されるクロックサイクル内での処理に対応して並列度を設定する。いずれもグリッド内座標での演算精度は通常、ダイナミックレンジを考慮しても８ビット程度であり、四則演算器が複数組み合わさっても回路規模は極めて小さいものとなる。【００７】  前記では交差領域の頂点をｘ、ｙ座標値として扱ったが、ポリゴンの頂点にはｘ、ｙ、ｚ座標値以外にテキスチャー座標値、面法線、視線ベクトル、光源入射ベクトル、面接線などのポリゴン面のテキスチャーや輝度を決定するための属性変数も同時に定義され、これらも外郭線補間およびポリゴン内挿補間の対象となる。本発明では、前記のグリッド内交差領域の頂点列からその重心を求めて参照点としたが、この参照点は前記の頂点属性の全てに適用することが好ましい。例えばテキスチャー座標値（ｕ，ｖ）の補間式は（２）式で与えられる。
2008152742.tif 000004
（２）式は外郭線がｘ軸を長軸（ｘ軸により傾いている）の場合を表す。添え字０および１は外郭線の始点と終点を示す。（２）式によって得られた（ｕ，ｖ）座標値もグリッド辺との交点での値、および傾きｄｕ／ｄｘあるいはｄｖ／ｄｘをもつ。よってｘｙ座標と同様な手段で交差領域のそれぞれの頂点での（ｕ，ｖ）座標列を得ることができる。但し、グリッド頂点での（ｕ，ｖ）値はグリッド原点からの距離１の値ではなく（ｄｕ，ｄｖ）値となる。このため、頂点フラグで示された内部頂点に対して（ｄｕ，ｄｖ）を求める。
この結果本発明では、交差領域頂点でのそれぞれの属性もまた（２）式と同様な方法でそれぞれ求め、前記（１）式により重心点における属性値を得るものとし、この値をテキスチャーパターンや輝度決定に用いる。【００８】  一方、属性の重心点での値に関しては、ｘｙ座標値と同様な手段で属性値の頂点列から重心計算で求めるのではなく、ｘｙ重心座標値から直接求める方法がある。すなわち、ポリゴンの外郭線補間段階で、ｘおよびｙ軸それぞれの１画素歩進時（距離１）に、属性の変移量を求めておき、ｘｙ座標の重心が求まれば、ｘｙグリッド原点からその重心までの変差量と、先に求めた属性の変移量をそれぞれ乗算して得た値を、属性のグリッド原点における値に加算して重心点の属性値を得ることができる。
以上から本発明では、交差領域の重心を求めるに当たって、通常では交差領域の頂点列を得る処理にテーブルを用いハードウエアを簡素化して計算負荷を軽減すると共に、重心計算はパイプライン逐次演算処理を用いて、実時間描画に適した構造とした。
これら技術をＬＳＩに実装し、コンピュータグラフィックスあるいは画像処理回路に組み込むことで、高品質な映像装置が得られることになる。
【発明の効果】
【００９】  本発明により、多角形が複雑に交差する周辺画素でのエイリアスを軽減し、高品質な画質を得る。
【発明を実施するための最良の形態】
【０１０】  本発明の技術はＬＳＩ、プログラマブル論理回路等への実装あるいはＩＰ（Ｉｎｔｅｌｌｉｇｅｎｔ  Ｐｒｏｐｅｒｔｙ）の形態で実施され、コンピュータグラフィックスプロセッサに応用される。
【実施例】
【０１１】  図１は本発明に係わるグリッドと交差する外郭線Ａの交差様態を示す。図１（ａ）は１本の外郭線がグリッドに交差しており、外郭線が左辺であるとすると、交差領域の頂点列はａ０、ａ１、ａ２となる。図１（ｂ）は３角形頂点を含まない２つの外郭線の左辺Ａと右辺Ｂがそれぞれ交差する場合で、外郭線Ａによって判定するポリゴン内面の（メモリに記憶された）頂点列はａ０、ａ１、ａ２、ａ３、ａ４、となり、外郭線の交差点ａ０、ａ１と、グリッド頂点ａ２、ａ３、ａ４が含まれる。一方外郭線Ｂによる内面頂点列はｂ０、ｂ１、ｂ２、ｂ３となり、外郭線交差点はｂ０、ｂ３、グリッド頂点はｂ１、ｂ２となる。ここで共有するグリッド頂点はａ４／ｂ１のみであり、前記〔００５〕の手段により、交差領域はａ０、ａ１、ｂ３、ｂ０、ａ４あるいはｂ１となる。また図１（ｃ）は３角形頂点を含む外郭線交差様態を示す。前記同様に外郭線ＡとＢそれぞれの内部領域となるグリッド頂点の内、共有頂点はａ１／ｂ２およびａ２／ｂ３であり、外郭線の一方のグリッド辺との交点ａ３およびｂ１は他方の外郭線の外側となって、交差領域頂点から削除される。また２つの外郭線の交点をｓ０とし、これは両外郭線が共有する点であるため、交差領域に含まれる。この結果、交差領域頂点列はｓ０、ａ０、ａ１／ｂ２、ａ２／ｂ３、ｂ０の５角形となる。図１（ｄ）は３角形のそれぞれの辺Ａ、Ｂ、Ｃがグリッドに交差する様態を示す。外郭線どうしのそれぞれの交点のうち、ｓ０がグリッド内部であり他はグリッド領域外で削除される。いずれも３つの外郭線すべてに共有するグリッド頂点はないため、グリッド頂点は交差領域に含まれない。それぞれａ０、ｂ０、ｂ１、ｃ０、ｓ０はすべての外郭線の内側か、その線上で共有し、これが交差領域の頂点列となる。【０１２】  図２は、外郭線のグリッド交点座標値と、３角形の内側となるグリッド頂点を演算処理を行わないで求めるための本発明の交差領域頂点列記憶回路を示す。図２の回路においてメモリ２０はＲＡＭあるいはＲＯＭいずれでも良い。グリッド内の外郭線全ての交差様態を得るには、入力情報として（１）外郭線がグリッド辺に侵入する交点座標値、（２）外郭線の傾き、および（３）外郭線の左右辺のそれぞれの情報が必要である。メモリ２０には前記（１）−（３）の情報をアドレスとして、予めグリッド交差様態を全て記憶する。グリッドとの交点座標値は、図１（ａ）では、交差点ａ０のｘ軸座標値とｙ軸０となる（グリッド原点を左下頂点とした場合）。また左右辺から（図１（ａ）では左辺）交差領域に含まれるグリッド頂点はａ２となる。一方、グリッドとの交点の片軸座標値は常に０か１である。この結果、１例として、交点座標値は片軸の座標値を４ビットで表し、交差軸がｘかｙかを示す１ビットと、その値が０か１かを示す情報１ビットを組み合わせた２ビットの、計６ビットで構成可能である。よって図２においてアドレス入力Ａ０には交点座標値と前記、グリッドの交差軸情報からなる６ビットを入力する。また外郭線の符号付傾きを４ビットとしてＡ１入力に、左右辺を示す１ビットを入力Ａ２に加え、結果、全入力ビットは１１ビットとなり、これをメモリ２０のアドレスとすれば、メモリ２０は２Ｋ��ードの容量となる。この容量はグリッド内の精度と関係する。メモリ２０の出力ではグリッド４頂点に対応したそれぞれ１ビットの信号をＢ０、Ｂ１、Ｂ２、Ｂ３（例えばＢ０は左下、Ｂ１は左上など）に出力する。この信号が例えば０であれば、グリッド頂点は外郭線の外側、１であれば内側とする。よって４つの信号ラインで所定の外郭線の内側となるグリッド頂点が判断できる。また出力Ｂ４とＢ５には外郭線とグリッド辺との交点座標値４ビットと、その交点がどのグリッド辺と交わるか辺を示す２ビットの計６ビットの信号をそれぞれ出力する。交点座標値は前記入力Ａ０と同様に、交差辺情報を含めば片軸の座標値のみでよい。以上からメモリ２０は少なくとも２Ｋのワード数とワード当たり１６ビットの出力ラインで構成できる。交点座標値の精度は３ビットからでもよく、５ビット程度までが実用的な範囲である。出力された前記情報はレジスタ２１に一括記憶する。もし、グリッドと交差する外郭線が１本の場合は、メモリ出力でそのまま交差領域の頂点列が得られる。２本の場合は、前記同様に２本目の外郭線をメモリ２０に加え、同様に出力を得る。レジスタ２１には前の外郭線の交差領域情報が記憶され、後の外郭線の情報がメモリ２０に出力される。グリッド内に３角形頂点を含まない場合で２本の外郭線交差する場合、先にレジスタ２１に記憶したグリッド頂点ビットと、２本目の外郭線のメモリ出力（Ｂ０−Ｂ３）となるグリッド頂点ビットとをそれぞれ一致判定回路（ＡＮＤ回路でよい）２２で比較し、共に１であれば、そのグリッド頂点は交差領域の頂点の一つとする。０となれば、いずれかの外郭線の外側となっていることから、これは交差領域外の点と見なす。３本目の外郭線がある場合にはすでに１と２本目で一致したグリッド頂点と、さらにメモリ出力とを一致判定回路２２で比較し、いずれも共通頂点を有する場合を交差領域頂点とする。【０１３】  グリッド内に３角形頂点を含む２本の外郭線が交差する場合（図１（ｃ）の例）、外郭線どうしの交点計算が必要となる。この交点計算の有無は、外郭線情報として、外郭線補間段階で予め頂点の有無を示すフラグを交差グリッド毎に記憶しておく。２直線の交点は２つの直線式の連立方程式を解くことで求まる。すでにそれぞれの直線の傾きおよび始点（グリッドと交差する座標値）が既知であり、交点は小規模な回路に求めることができる。とくに傾き、始点座標値それぞれの精度は４ビット程度であり、交点計算のハードウエアは計算過程のダイナミックレンジを考慮しても８ビット程度の四則演算回路で構成できる。その他の頂点判定は〔０１１〕と同様な処理となる。【０１４】  交点をグリッド内にもつ外郭線が３本グリッドに交差する（図１（ｄ））場合は、外郭線の交点の一つはグリッド内部にあることは前記頂点有無フラグで既知であるが、それ以外の交点がグリッド内にあるか否かの検証が必要であり、それぞれの外郭線に対して交点計算を行う。２直線の交点計算は〔０１２〕と同様であるが、その点が負あるいは１以上であれば、グリッド外部となる。【０１５】  図３に〔０１２〕〔０１３〕の処理を行う本発明の交差領域座標列全体回路構成を示す。図３において、２０−２２は図２と同じ機能のもので��る。外郭線情報は外郭線情報バッファ（図３には示していない）から逐次、図３の回路に与えられるが、その中には交差条件が図１のどの様態となるかを判断する情報（外郭線数、頂点の有無など）のも含まれる。１本から３本までの頂点を含まない外郭線の場合は、メモリ２０、レジスタ２１および一致判定回路２２で、交差領域の頂点列は検出でき、時計あるいは反時計方向の順序で、頂点列を配列変換回路３３で配列変換した後、重心を求める回路に出力する。一方、頂点を含み、２直線の交点を求める場合は直線交点計算回路３０で交点座標値を求める。直線交点計算回路は、２つの外郭線情報から交点計算に必要な傾き、およびグリッド交差点座標値を受けて四則演算回路で交点計算を行う。２本の外郭線と、一つの頂点の場合は、その結果をそのまま配列変換回路２２へ出力するが、頂点を含む３本の外郭線がグリッドと交差する場合は外郭線の交点がグリッド内に含まれるか否かの判定が必要となり、交点座標値を後段の領域判定回路３１で判定する。領域判定回路は交点座標値が負か、１以上の値の場合を領域外とする比較器（減算器）から成る。領域内となる場合は、その交点座標値を配列変換回路３３に出力する。以上のようにグリッドに交差する外郭線の数、グリッド内の頂点の有無によって、計算処理が異なるため、配列変換回路入力においての選択、それぞれの回路での演算遅延調整、また配列のための情報は、シークエンサ３２のクロックと信号で制御する。シークエンサは外郭線情報の中の頂点有無、外郭線の左右辺また外郭線本数などを受けて、図３に示すそれぞれの演算回路のためのシークエンスと制御信号をクロック、シフトレジスタまたゲートを用いて生成する。【０１６】  図４には本発明の重心回路を示す。図４において交差領域の頂点列は図３から図４の４Ｄおよび４Ｅのレジスタに逐次与えられる。これら座標値（Ｘｉ，Ｙｉ）（Ｘｉ＋１，Ｙｉ＋１）は乗算器４０と４１、また加算器４２と４３にそれぞれ入力する。図４の回路は前記（１）式を計算するためのもので、前記乗算器に加え、減算器４４、乗算器４５、４６、４Ｆ、４Ｇ、加算器４７−４９、４Ｈ、４Ｉ、レジスタ４Ａ−４Ｃ、また面積値の除算を行うための除算器４Ｊのそれぞれで構成する。入力から４Ｆ、４Ｇまでの回路はグリッド内座標値の精度で良いため４ビットが保障されれば良い。よって計算のダイナミックレンジは整数処理の８ビット程度となり、回路の四則演算器は回路ゲート規模の小さいものとなる。重心計算回路は図４に示すようにパイプライン構造とすると、頂点毎に座標値が逐次入力する場合は、１本の外郭線とグリッド頂点１つの３角形交差領域ではスループットとしては、３クロックサイクルで重心を求めることができる。高速化のためこれを所定のサイクル以内で実行する必要がある場合は、図４の回路を並列化し、２頂点間隔ではなく、それ以上の頂点数を並列に処理する。例えば（Ｘｉ，Ｙｉ）（Ｘｉ＋１，Ｙｉ＋１）と（Ｘｉ＋１，Ｙｉ＋１）（Ｘｉ＋２，Ｙｉ＋２）を同時処理し、その結果を加算すれば３点の重心は１クロックサイクルで求めることができる。最終的（描画空間全域に対する）な重心座標は、グリッドの原点座標値と、グリッド内座標値とを加算器４Ｈと４Ｉにおいて加算して得られる。最終段階における演算精度のみ１１あるいは１２ビットの座標精度となる。【０１７】  ポリゴンの頂点にはｘ、ｙ座標値だけでなく、テキスチャー、面法線等の多数の属性変数が定義され、これらが同時に頂点間で補間される。外郭線交差グリッド内での適切な参照点の選択は、これらすべての頂点定義属性に対して共通の課題であり、本発明ではこれら属性も含めて重心点における値を求める。よって回路３および４は頂点属性毎に実行する。高速化を図る描画システムでは、それだけの並列度（回路の並列化）を上げることになる。
以上から本発明は、アンチエイリアス技術として、グリッドにポリゴン境界（外郭線）が含まれる画素での輝度決定手段として、グリッド内に占めるポリゴンの面積比を求め、それぞれのポリゴンが持つ輝度を面積比に応じて比例配分するにあたり、グリッド内ポリゴン（交差領域）の、輝度決定のための参照点を算出するための手段として、高速且つ低ハードウエアコストで実装する回路を提供するものである。また、これら技術をＬＳＩに実装し、コンピュータグラフィックス等また画像処理回路に組み込むことで、高品質な映像装置が得られることになる。
【産業上の利用可能性】
【０１８】  本発明の回路をＩＰ（Ｉｎｔｅｌｌｉｇｅｎｔ  Ｐｒｏｐｅｒｔｙ）として、あるいはグラフィックスプロセッサＬＳＩチップに実装することによって映像製作、ＣＧゲーム等のシステムにおいて実時間描画を可能とする。
【図面の簡単な説明】
【０１９】
【図１】「本発明に係わる、外郭線とグリッドとの交差様態を示す。」
【図２】「本発明の交差領域頂点列記憶回路を示す。」
【図３】「本発明の交差領域座標列演算全体回路を示す。」
【図４】「本発明の多角形重心計算回路を示す。」
【符号の説明】
図１
（ａ）単一外郭線交差様態
（ｂ）頂点なし２本外郭線交差様態
（ｃ）頂点あり２本外郭線交差様態
（ｄ）３本外郭線交差様態
図２
２０  メモリ
２１  レジスタ
２２  一致判定回路
図３
３０  直線交点計算回路
３１  領域判定回路
３２  シークエンサ
３３  配列変換回路
図４
４０−４１  乗算器
４２−４３  加算器
４４  減算器
４５−４６  乗算器
４７−４９  加算器
４Ａ−４Ｅ  レジスタ
４Ｆ−４Ｇ  乗算器
４Ｈ−４Ｉ  加算器
【図１】
2008152742.tif 000005
【図２】
2008152742.tif 000006
【図３】
2008152742.tif 000007
【図４】
2008152742.tif 000008