【手続補正書】
【提出日】平成19年7月11日(2007.7.11)
【手続補正１】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【書類名】    明細書
【発明の名称】改良されたＳ−バッファのアンチエイリアシング方法
【特許請求の範囲】
【請求項１】
多角形（ポリゴン）が画素（ピクセル）のアレイ上に表示されるコンピュータ画像生成システムにおいて用いるための、多角形と画素との交点を表すデータを符号化するための方法であって、
少なくとも３個の頂点を有し、各異なった頂点対が異なったエッジを形成する表示すべき各多角形の各頂点の一組の座標を示す入力データ信号を受信する工程と、
前記多角形のエッジの、表示すべき各画素との交点があるならば、その交点を示すエッジデータ信号を、受信した頂点データ信号に応答して生成する工程とを含み、前記生成する工程が、表示すべき各画素毎に、
ｉ）その画素の各辺毎に、前記エッジデータ信号のうちの１個のエッジデータ信号の第一フィールドに、１個のフラグを、前記多角形のうちの選択された１個の多角形のエッジが前記画素の前記辺と交差する、或いは交差しないことをそれぞれ表す第１の値、或いは第２の値の何れかに設定する工程と、
ｉｉ）前記選択された多角形のエッジがその画素のいずれかの辺と交差する場合は、前記エッジデータ信号のうちの前記１個のエッジデータ信号の所定のサイズの第二フィールドに、前記多角形のエッジが前記画素の辺と交差する前記画素の辺に沿う位置の推定値を表すエッジデータを符号化し記憶する工程とを含み、前記符号化したエッジデータが未符号化エッジデータよりも少ない記憶スペースを利用し、それにより前記多角形と前記画素との交点を表すのに必要な記憶要件を減少させることを特徴とする方法。
【請求項２】
前記記憶する工程は、
前記選択された多角形のエッジが前記画素の二つの辺と交差する場合は、
ｉ）前記第二フィールドの第一サブフィールドに、前記多角形の前記エッジが前記画素の前記二つの辺のうちの第一辺と交差する、前記第一辺に沿う距離の推定値を記憶する工程と、
ｉｉ）前記第二フィールドの第二サブフィールドに、前記多角形の前記エッジが前記画素の前記二つの辺のうちの第二辺と交差する、前記第二辺に沿う距離の推定値を記憶する工程とを含む請求項１による方法。
【請求項３】
前記第二フィールドが所定数のビットロケーションから成り、
前記第一サブフィールドが前記所定数のビットロケーションの１／２から成り、そして
前記第二サブフィールドもまた、前記所定数のビットロケーションの１／２から成る請求項２による方法。
【請求項４】
前記第二フィールドが４個のビットロケーションから成り、
前記第一サブフィールドが前記４個のビットロケーションのうちの第一及び第二のビットロケーションから成り、そして
前記第二サブフィールドが前記４個のビットロケーションのうちの第三及び第四のビットロケーションから成る請求項２による方法。
【請求項５】
前記記憶する工程は、
前記選択された多角形のエッジが前記画素の３個の辺と交差する場合は、
前記第二フィールドに、前記多角形の前記エッジが前記３個の辺と交差する、前記画素の前記３個の辺に沿う距離の平均値を記憶する工程を含む請求項１による方法。
【請求項６】
前記記憶する工程は、
前記選択された多角形のエッジが前記画素の４個の辺と交差する場合は、
前記第二フィールドに、前記多角形の前記エッジが前記４個の辺と交差する、前記画素の前記４個の辺に沿う距離の平均値を記憶する工程を含む請求項１による方法。
【請求項７】
多角形が画素のアレイ上に表示されるコンピュータ画像生成システムにおいて用いるための、多角形と画素との交点を表すデータを符号化するための装置であって、
少なくとも３個の頂点を有し、各異なった頂点対が異なったエッジを形成する表示すべき各多角形の各頂点の一組の座標を示す入力データ信号を受信する手段と、
前記多角形のエッジの、表示すべき各画素との交点があるならば、その交点を示すエッジデータ信号を、受信した頂点データ信号に応答して生成する手段とを含み、前記生成する手段が、
ｉ）表示すべき各画素毎に、その画素の各辺毎に、前記エッジデータ信号のうちの１個のエッジデータ信号の第一フィールドに、１個のフラグを、前記多角形のうちの選択された１個の多角形のエッジが前記画素の前記辺と交差する、或いは交差しないことをそれぞれ表す第１の値、或いは第２の値の何れかに設定する手段と、
ｉｉ）前記エッジデータ信号のうちの前記１個のエッジデータ信号の所定のサイズの第二フィールドに、前記選択された多角形のエッジがその画素のいずれかの辺と交差する場合、前記多角形のエッジが前記画素の辺と交差する前記画素の辺に沿う位置の推定値を表すエッジデータを符号化し記憶する手段とを含み、前記符号化したエッジデータが未符号化エッジデータよりも少ない記憶スペースを利用し、それにより前記多角形と前記画素との交点を表すのに必要な記憶要件を減少させることを特徴とする装置。
【請求項８】
前記記憶する手段が、前記第二フィールドの第一および第二サブフィールドに、前記選択された多角形のエッジが前記画素の二つの辺と交差する場合、前記多角形の前記エッジが前記画素の前記二つの辺のうちの第一及び第二の辺と交差する、前記第一及び第二の辺にそれぞれ沿う距離の推定値を記憶する手段を含む請求項７による装置。
【請求項９】
前記第二フィールドが所定数のビットロケーションから成り、
前記第一サブフィールドが前記所定数のビットロケーションの１／２から成り、そして
前記第二サブフィールドもまた、前記所定数のビットロケーションの１／２から成る請求項８による装置。
【請求項１０】
前記第二フィールドが４個のビットロケーションから成り、
前記第一サブフィールドが前記４個のビットロケーションのうちの第一及び第二のビットロケーションから成り、そして
前記第二サブフィールドが前記４個のビットロケーションのうちの第三及び第四のビットロケーションから成る請求項７による装置。
【請求項１１】
前記記憶する手段は、前記第二フィールドに、前記選択された多角形のエッジが前記画素の３個の辺と交差する場合、前記多角形の前記エッジが前記３個の辺と交差する、前記画素の前記３個の辺に沿う距離の平均値を記憶する手段を含む請求項７による装置。
【請求項１２】
前記記憶する手段は、前記第二フィールドに、前記選択された多角形のエッジが前記画素の４個の辺と交差する場合、前記多角形の前記エッジが前記４個の辺と交差する、前記画素の前記４個の辺に沿う距離の平均値を記憶する手段を包含する請求項７による装置。
【発明の詳細な説明】
【０００１】
【発明の分野】
本発明はコンピュータ画像生成(CIG)システムに関し、より詳細にはディスプレイプロセッサで用いるための新規な色彩測定装置に関し、更にはリアルタイム画像システムにおいて目標物の二次元表現を表示するために目標物の面を描写する画像データを処理する新規な方法に関する。
【０００２】
【発明の背景】
リアルタイムコンピュータ画像システムは、様々なビデオグラフィックシステム、たとえばビデオゲームならびにビデオトレーニングおよびシミュレーション装置用にリアルな画像を提供するように設計されている。これらのシステムにおいては、ユーザーにビデオディスプレイ・リアリズムを提供することが非常に有利である。
【０００３】
典型的なリアルタイムコンピュータ画像生成システム、たとえばビデオゲームにおいて、画像の生成は３種類の連続的な段階、すなわちコントローラ(Contoroller)、ジョメトリープロセッサ(Geometry Processor)およびディスプレイプロセッサ(Display Processor)において行われる。これら３種類の段階あるいは区画は表示すべき３個の連続するシーンの一つあるいはそれに対応するものを描写するデータに関しそれぞれ独立に作動する。これら処理段階または区画のそれぞれはシーン上のデータまたは画像を固定時間に亘って処理するが、これはフィールド時間16.67ミリ秒またはフレーム時間33.3ミリ秒であればよく、通常は前者である。これら特有のフィールドおよびフレーム時間は典型的なＴＶフォーマットディスプレイ、すなわち毎秒30回のフレームによるフレーム当たり２回の飛び越しフィールドに相当する。
【０００４】
それぞれの時間間隔について、３台のプロセッサ全てはビジー状態なので、如何なる所定時間においてもこれらのプロセッサは３種類の別個のシーンに関して作動している。各区画は入力を処理し、そしてインターバルの間に出力を生成し、その結果データは３段階を通じてコントローラからジョメトリープロセッサへ、次いでディスプレイプロセッサへと逐次的な態様で流れる。特殊化されたプロセッサ区画の中でコンピュータ的負荷は展開されて、それらの結果が３フィールドまたはフレーム時間遅延するにしても、新しいシーンをそれぞれのフィールドまたはフレーム時間表示することが可能である。
【０００５】
たとえば、フライトシステムをシミュレートするビデオゲームにおいて、ユーザーまたはプレイヤーの入力はコントローラによって受信され、そしてコントローラ、ジョメトリープロセッサおよびディスプレイプロセッサによって逐次的に処理された後、その出力はプレイヤーによって観られているビデオディスプレイにカラーシーンとして送られる。プレイヤーによって観られているデータは環境定義により印加された簡単な制御入力としてスタートし、そして画素のビデオディスプレイ情報に変換される。コントローラにおいて、プレイヤー入力はシミュレートされた航空機の新しい位置および方位を計算するために用いられ、そしてこれから数理的交替マトリクスが計算され、これは目標物を基準座標システムからディスプレイ座標システムに転回させるために使用される。その航空機、標的の位置、また他の航空機を処理する他の情報もまた、コントローラにおいて計算される。或る種の応用例では、コントローラは多目的コンピュータである。
【０００６】
ジョメトリープロセッサはデータベースから目標物であって、そのシーンの記憶された三次元デジタル表示において潜在的に可視であるものについての記述を読出し、そして読出された目標物は、コントローラにおいて計算された転回マトリックスを用いてディスプレイ座標に転回される。このジョメトリープロセッサは三次元データを二次元ディスプレイ・ウィンドウ上に数値的に投影する。更に、ジョメトリープロセッサは（デプス（深さ）バッファを利用することによって）どの目標物が他の目標物の前方あるいは後方にあるかを計算し、そしてこの情報を優先リスト中に記憶する。
【０００７】
処理された各目標物は個々の面から構成され、ここにおいて各面は真っ直ぐなエッジによって境界を設けた多角形の形状である。優先リストはシーンにおける全ての面の順位を包含しており、第一面はリスト中で最高優先度の面である一方、リスト内の最終面は最下位の優先面として含まれている。ディスプレイ上で２個の面がオーバーラップするときは何時でもより高い優先度の面が可視であって、下位優先度の面は不明瞭となる。最後に、ジョメトリープロセッサは、二次元面に境界を設けるエッジに関してディスプレイの終点を計算し、またこれらの境界エッジを記述するライン等式の計数を計算する。
【０００８】
ディスプレイプロセッサは二次元面の記述を付加的な面関連データと共に受信し、そしてこの情報を用いて、シーン中の各画素をカラーディスプレイ上に描写する、データを出力する。システム中のカラーディスプレイは代表的に1024ラインのビデオ情報から構成され、各ラインは1024個の個別カラードットまたは画素を有している。ディスプレイプロセッサは、どの色の画素を付与すべきか各画素について、数多くの面が画素内に存在可能であること、ならびに面の或る部分を他の面によって覆い得るかという問題を解決せねばならない。これら全画素についての値は１秒の1/60において計算する必要があるので、このディスプレイプロセッサにおける処理負荷は非常に高い。マルチディスプレイシステム（単一のシステムが14台ほど多数のディスプレイを包含する）に関する映像を計算するために、このディスプレイプロセッサは１秒当たり100億回を超える演算を行わねばならない。
【０００９】
アンチエイリアシング方法において画素の色彩純度情報を処理するために、永続的な問題が存在しており、それは、その画素における誤った色彩あるいは半透明度として現れるような、望ましくないビデオデータ成分（歪み）が所望成分の同一性を取ることを阻止しながら、適切な高鮮明度のエッジ効果を可視とすることである。
【００１０】
【発明の要約】
本発明の目的は、コンピュータ画像生成システムのために改良されたアンチエイリアシング手順を提供することである。
【００１１】
本発明の他の目的は、コンピュータ画像生成システムにおけるアンチエイリアシング手順において使用するためにエッジ交差点データを符号化するための改良された方法を提供することである。
【００１２】
これらおよび他の目的は、多角形が画素のアレイ上に表示されるコンピュータ画像生成システムにおいて用いるための、多角形および画素の交差点を表すデータを符号化するための方法および装置により達成される。この方法は表示すべき各多角形の少なくとも３個の頂点のそれぞれの座標の一組を特徴づける入力データ信号を受信する工程であって、各多角形の頂点のそれぞれ異なった対がその多角形の異なったエッジを定義するものと、受信した頂点データ信号に応答して、表示すべき各画素と共に、もしあれば、多角形エッジの交差点を記述するエッジデータ信号を生成する工程とを含んで構成される。
【００１３】
この生成工程は、表示すべき各画素について、ｉ）エッジデータ信号の１個の第一フィールドにおいて、また画素の各辺について、多角形の選択された１個の、エッジが画素の上記辺と交差しているか否かを同定する工程と、ｉｉ）選択された多角形のエッジが画素のいずれかの辺と交差する場合は、上記エッジデータ信号の１個の第二のフィールドにおいて、多角形エッジが画素の辺と交差する画素の辺に沿う位置の推定値を記憶する工程とを包含するものである。
【００１４】
更に、本発明の利益と効果は添付図面を参照することによって付与される以下の詳細な説明であって、本発明の好ましい実施態様を特定し、かつ示すものを考察することから明かとなるであろう。
【００１５】
【例示的実施態様の説明】
最初に図１を参照すると、コンピュータ画像生成システム１０、たとえば航空機のコックピットシミュレーションシステムの機能的ブロック図が示されている。ここで、現存のCIG技術を参照されたい。それらの刊行物にはたとえば、Bunker他の1988年２月２３日に発行された米国特許第4,727,365号"Advanced Video Object Generator"、D. Merzの1989年４月２５日に発行された米国特許第4,825,391号"Depth Buffer Priority Processing For Real TimeComputer Image Generating Systems"およびW. SteinerおよびM.Morganに対し発行された米国特許第5,668,940号"Method and Apparatus For Anti-AliasingPolygon Edges In a Computer Imaging System"が包含される。これら３件の米国特許第4,727,365号、第4,825,391号および第5,668,940号はここに参考として引用するものとする。
【００１６】
システム１０はコントローラユニット１２、ジョメトリープロセッサユニット１４、およびディスプレイユニット１６を包含している。このディスプレイプロセッサユニット１６はディスプレイウインドウ１８に対し情報を表示して、シーン上方に航空機の動きをシミュレートする。オペレータ２０は入力制御インターフェース２２を介してコンピュータ画像生成システム１０にリンクされている。オペレータの操縦動作は入力制御インターフェース２２に供給される。入力制御インターフェースはしかるべきデータ、たとえば航空機の位置、転回、ピッチおよび横揺れ姿勢をオペレータからコントローラ１２へと変換する。
【００１７】
コントローラ１２において、オペレータの入力は航空機の新しい位置および方位を計算するために用いられ、そしてこれから数理的交替マトリクスが計算され、これは基準座標システムから目標物をディスプレイ座標システムへ転回させるために使用されるが、このことは当該技術分野では周知である。シーンを処理する他の情報、すなわち標的の位置あるいは他の航空機はコントローラにおいて計算される。一部のコンピュータ画像生成システムにおいて、コントローラユニット１２は多目的コンピュータである。
【００１８】
コントローラユニット１２は最新の航空機方位によって周期的に更新される。この方位は、入力制御インターフェース２２を経由するオペレータからコントローラ１２への航空機の転回、ピッチ、横揺れおよび位置を包含する。コントローラ１２はシーン上でフィールドまたはフレーム時間作動し、次いでデータをジョメトリープロセッサ１４に渡す。
【００１９】
ジョメトリープロセッサ１４はシーンデータベースメモリ２４から目標物の記述、たとえばタワー、道路、河川、格納庫等を読出すが、これらは記憶された地球の三次元デジタル表示において潜在的に可視である。これらの目標物はシーンデータベースから読出され、そしてコントローラ１２において計算される交替マトリクスを用いてディスプレイ座標に順送りされる。ジョメトリープロセッサ１４は全てのエッジであって、目標物空間内のビューウィンドウ境界を超えて延在するものをクリップし、そしてプロセッサ１４は三次元目標物データを二次元ディスプレイウィンドウ上に数理的に投影する。
【００２０】
物体の面であって、ディスプレイウィンドウ境界を超えて延在するものは二次元画像空間においてクリップされる。この二次元物体は点、線、閉凸多角形あるいはそれらの組合わせを含んでいる。それぞれの閉凸多角形は面として知られる。このようにして、処理された各物体は個々の面を構成し、ここにおいて各面は真っ直ぐなエッジによって境界を設けられている。ジョメトリープロセッサ１４において三次元物体から面が一度算定されると、そのデータはディスプレイプロセッサ１６に渡される。更に、ジョメトリープロセッサ１４は、知られたやり方において、どの面が他の面の前方または後方にあるかを計算し、そしてこの情報を優先リスト内に記憶する。
【００２１】
この優先リストはシーンにおける全ての面の順位を含んでおり、そこではこのリスト内の第一面が最上位の優先面であり、またリスト内の最終面は最下位の優先面である。２種類の面がオーバーラップするときは何時でも最上位の優先面が可視となり、そしてより低い優先面のオーバーラップ部分は不明瞭となる。優先リストを計算した後、ジョメトリープロセッサ１４は二次元面に境界を設けるラインセグメントのディスプレイ終点を計算し、そして境界エッジを記述するライン等式の係数を計算する。ジョメトリープロセッサ１４は各エッジの終点および各エッジの傾斜であって、境界された面を記述するものを計算する。次いで、これらのデータはディスプレイプロセッサ１６に渡される。
【００２２】
図１はビデオディスプレイ１８を駆動するために使用されるディスプレイプロセッサ１６を示している。一部のシステムでは、１台以上のディスプレイプロセッサを駆動するために、単一のコントローラ１２およびジョメトリープロセッサ１４が使用されている。ディスプレイプロセッサはビデオディスプレイ１８に表示すべき情報処理のための責任を負っている。ディスプレイプロセッサによって為される一つの独特の仕事は、ビデオディスプレイ１８内の各画素について、その画素の何色を、数多くの面であって、或る画素中に存在し得るものに、そしてまた他の面によって覆われても良い面のそれらの部分に与えるべきか、を解決することである。この機能を遂行するために、ディスプレイプロセッサ１６はこのようにして、二次元面の記述をジョメトリープロセッサ１４から面色彩および面優先度リストと共に受け、そしてこの情報を使用してシーンをカラービデオディスプレイ１８に出力する。システム中の各カラーディスプレイは1,024本以上のラインのビデオ情報から構成することが可能であり、また各ラインには典型的に1,204個の個別カラードットまたはピクセル（画素）が存在する。それぞれの画素に関して、ディスプレイは12ビットの赤データ信号、12ビットの緑データ信号、および12ビットの青データ信号を、画素の色彩を記述する純度情報のパートとして受ければよい。
【００２３】
図２に関して、観察者の両眼２０’は観察点ＶＰに存在し、そして物体の空間３０’内のビューウィンドウ中のサンプル多角形面３０を観察する。ビューラインに沿った、観察者２０’に最も近接する面３０のみが観られ、そして可視面は、当該技術分野で周知の深さバッファ技法（たとえば、上述の米国特許第4,825,391号およびその中に引用された文献を参照のこと）を用いて、観察点ＶＰおよび面３０の点Ｐｆ間の範囲距離Ｒの比較によって決定される。このようにして、可視多角形３０（ここではその頂点Ｖａ、ＶｂおよびＶｃ）によって同定される三角形面）はビューライン３２に沿う最小範囲Ｒminを有する多角形である。物体空間３０’は画像空間３４’中のディスプレイウインドウ３４内に投影され、そして多角形面３０は頂点Ｖａ、ＶｂおよびＶｃにそれぞれ対応する各頂点Ｖ１、Ｖ２およびＶ３を有するディスプレイ多角形３６として投影される。
【００２４】
ディスプレイウィンドウは、しばしば（Ｊ方向における）水平ラインに沿ってラスタ／ウィンドウの左エッジ（Ｊ＝ＪO）から右エッジ（Ｊ＝Ｊmax）へ逐次的態様で走査された各画素３８を伴うディスプレイのラスタであり、そしてラスタ／ウィンドウの頂部エッジ（Ｉ＝ＩOの場合）から底部エッジ（Ｉ＝Ｉmax）へ下降して増加する距離（Ｉ方向において）を有するラインに関している。このようにして、パスラインＬｐは第一（左側）画素Ｐｌから最終（右側）画素Ｐｒへと走査される。画素Ｐｐはウィンドウプレーン３４を通過するビューライン３２によって同定され、その結果画素ラインＬｐは多角形ポイントＰｆに投影し、かつこれに対応する画像ポイントを包含する。多角形３６は、ラインＬｐと共に左ライン位置において交差するＪLにより同定される最左方画素ＰOから右ライン位置において交差するＪRによって同定される最右方画素Ｐｑへの画素を含むことになる。
【００２５】
図２ａを参照すると、走査線３４”に沿った画素の列は、最左方画素３８ｈからスタートしてＪ方向に逐次的に走査される。その後、次の画素３８ｉが作用され、以下同様に、多角形の左エッジで、そのラインに関し、かつ多角形３６によって部分的に覆われるものに到達するまで作用される。この画素は多角形エッジの最左方交差点ＪLおよびＪライン３４”として同定される。多角形によって完全に覆われた他の画素３８を経由し、このラインに沿って続行することにより、画素３８ｒは多角形の右エッジで、かつ多角形３６によって部分的に覆われたものに到達する。この画素は、多角形エッジの最右方交差点ＪRとして同定される。Ｊライン３４”に沿う更なる行程は、最終的にその走査線の最右方画素３８Ｖに達する。
【００２６】
半透明性および最も離れた多角形からの彩度のフィードスルーを考慮しなければ、多角形３６によって完全に覆われ、従って全てが、その内部にある画素３８の属性は厳密に多角形面の属性（色彩、純度、半透明性等）を有していることが理解されよう。対照的に、多角形３６により部分的に覆われている画素（たとえば、画素３８ｌおよび３８ｒ）は、その特定の多角形の実際に覆われている画素部分についてだけ、その属性を有しているので、その画素の残部に関しては他の情報およびカラー情報の各多角形／ソースにより覆われる画素の様々な百分率によってブレンドされたものから得なければならない。
【００２７】
このことは図３ａを参照することによって理解され、この場合第一多角形３６ａは、画像空間内に観られるように、他の多角形３６ｂの前方に（周知の深さ−バッファ法のいずれかによるものとして）配列される。多角形３６は、同様に複数個の多角形エッジ３９（たとえば、図３ｂ中にエッジ３９ａ、３９ｂ、３９ｃおよび３９ｄとして示される）であって、交差点４０において画素境界を横切るものによって連結された複数個の頂点（たとえば、４個の頂点図３ｂ中のＶ１、Ｖ２、Ｖ３およびＶ４）を有する。画像スクリーンは、次の高次数字を付した（次に走査すべき）画素ラインによる各画素ラインＬ下方区分における水平エッジＥと共に水平ライン（たとえば、ラインＬ−２，Ｌ−１，Ｌ，Ｌ＋１，Ｌ＋２，．．．）と一緒に逐次的垂直行（たとえば、Ｐ−２，Ｐ−１，Ｐ，Ｐ＋１，Ｐ＋２，．．．）に整列された画素の長方形アレイを形成する。従って、各画素をその列ラインＬと行Ｐ表示によって配列することが可能である。或る画素、たとえば画素（Ｌ，Ｐ）はただ１個の多角形（多角形３６ａ）によって完全に覆われており、従ってその多角形の属性のみを有するのに対し、他の画素は複数多角形の属性の分配／ブレンドを有するものであることが理解されよう。
【００２８】
図３ｂに関して、色彩属性は全画素についての考察によって決定することが出来、たとえ上述の米国特許第4,825,391号の深さ−バッファ処理アーキテクチュアを（スパン／サブスパン処理方法論と共にあるいはそれを伴わずに）使用したとしても、各画素（またはサブピクセル）の複数個の副次部分(subportions)について色彩情報を処理する必要はない。処理される情報の各事項は電子デジタルデータの信号語(signal word)であることが理解されるべきである。一方で我々はこれらの信号を速記表示(shorthand designations)（たとえば、コーナー、エッジ、多角形等）で論じている。それにも拘わらず、我々はこれらの術語がこれらそれぞれの幾何学的概念の各々について用いられるデータ信号を意味するものとして使用している。たとえば、「コーナー」は二次元の画素コーナー配置を特定するデータ語を示し、「エッジ」は関連する多角形エッジのラインを表すデータ信号セットであり、「多角形」は特定の多角形に等しいデジタルデータ構造を意味する等である。処理の最終結果は、ビデオ信号（デジタルビデオまたはデジタルに由来するアナログビデオ）の最終シーケンスを提供するものであり、観察者２０に対し電飾および可視とすべきビデオディスプレイ手段１８の個別の画素について色彩および輝度をもたらし得るものである。
【００２９】
画素を部分的に覆っている多角形が最終画素の属性に寄与する範囲は、多角形のエッジと画素境界との交差点に基づいて決定される。この態様により画素の属性を決定する一つの手順は、上で特定した米国特許第5,668,940号中で詳細に説明されている。
【００３０】
一般的に、この手順によれば入力データ信号は、各多角形面の少なくとも３個のそれぞれのディスプレイ空間座標を特徴づけるものとして表示すべく提供される。次に、この頂点データを利用して、もしあれば、どの多角形エッジがディスプレイラスタを形成する画素のシーケンスの一つをカットするかを決定し、次いで、関連画素エッジに沿ってカットされた、その配置を決定する。各画素に影響する全ての多角形についてのエッジ交差データ信号は、その画素の何らかの部分を占める各多角形についての色彩データと共にフレームバッファ内にピクセル当たり(per-pixel)基準で記憶される。表示すべき各画素について、選択された隣接画素の配置(constellation)は、エッジ関係およびブレンド多角形の色彩純度を解決するために処理されて各ディスプレイ画素の最終的な観察可能色彩を決定する。
【００３１】
図４に関して、各画素５０は多角形をサンプリングするサンプルポイントである。多角形エッジが、隣接する画素のサンプルポイント間を横断する場所が算定される。各画素サンプルポイントについて、頂部、左方、右方および底部エッジ交差点が算定される。もし、エッジ交差点が次の画素サンプルポイントを越えていれば、そのエッジ交差点は覆われている、とフラグが立てられ、これは多角形が隣接の画素サンプルポイントを覆っているか、あるいは横たわっていることを意味する。たとえば、図４において、左下方画素サンプルポイントに関する右方交差点５２ａおよび右下方画素サンプルポイントに関する左方交差点５２ｂは覆われているものとしてフラグを立てられることになる。
【００３２】
各多角形エッジはアンチエイリアシングされているもの、あるいはアンチエイリアシングされていないものとしてフラグを立てることが出来る。更に、各多角形エッジはメッシュ・アンチエイリアシング(mesh anti-aliased)されたものとしてフラグを立てることが出来る。この態様において、画素サンプルポイントの全ての多角形エッジ交差点についてメッシュ・アンチエイリアシングが可能ならば、多角形エッジはアンチエイリアシングされ、そしてそのエッジは他の多角形によって分配されることはなく、そしてエッジはアンチエイリアシングされたものとしてフラグが立てられる。もし、メッシュ・アンチエイリアシングが不可能であれば、エッジがアンチエイリアシングされていないものとしてフラグが立てられない限り、そのエッジはアンチエイリアシングされる。
【００３３】
もし、画素が多角形よりは寧ろ画像の部分であれば、その画素は条件付きでアンチエイリアシングされたものとしてフラグが立てられる。この場合、もし多角形エッジが画像上に横たわっていれば、その多角形エッジは画像によってアンチエイリアシングされ、そうでなければ、その画像はアンチエイリアシングされない。
【００３４】
フレームバッファ（目的地）内の色彩をフレームバッファ（出所）内に加えられる色彩と共にブレンドするアルファバッファオペレーション（出所および目的地ブレンドモード）を用いると、エッジ交差点は以下のように組み合わされる。
【００３５】
すなわち、アルファバッファブレンド等式： ブレンド因子s*出所画素＋ブレンド因子d*目的地画素である。もし、ブレンド因子sがゼロであれば、出所画素はエッジ交差点を全く有していない。もしブレンド因子dがゼロであれば、目的地画素はエッジ交差点を全く有していない。もし、出所画素および目的地画素がエッジ交差点を有していなければ、何も行われない。もし、出所画素がエッジ交差点を有しており、そして目的地画素が有していなければ、出所画素エッジ交差点が使用される。もし、出所画素がエッジ交差点を有して居らず、そして目的地画素が有していれば、目的地画素エッジ交差点が使用される。もし、出所画素がエッジ交差点を有しており、また目的地画素も同様に有していれば、出所および目的地画素エッジ交差点は平均化される。
【００３６】
エッジ交差点は８乃至９ビットに圧縮することが出来、図５の表中に示すようにフレームバッファ内に収められる。
【００３７】
もし、設定されていれば、交差点フラグはエッジ交差点が存在することを示し、またもし、設定されていなければ、多角形が隣接の画素上に横たわっていることを示す。
【００３８】
もし、アンチエイリアシングが望ましければ、９ビットが必要であり、そうでなければ８ビットは必須である。メッシュフラグはフレームバッファ内の青色のＬＳＢを置換することが出来る。これは画像に対し最小の衝撃を有することになる。３による分割を近似することが可能である。エッジ交差点を、アルファ成分中のフレームバッファ内に記憶すればよい。これが、目的地アルファを用いる如何なるブレンドモードをも制限する。
【００３９】
エッジ交差点データは、出力時間の間にフレームバッファから読出される。次いで、符号化エッジ交差点データは元のエッジ交差点データに復号することが出来る。
【００４０】
図６を参照すると、４個の隣接する画素サンプルポイント５０ａ、５０ｂ、５０ｃおよび５０ｄがフレームバッファから取出される。これらの画素サンプルポイントは画素の４隅となる。各サンプルポイントは４個のエッジ交差点および数個のフラグを有している。それぞれの画素サンプルポイントからのエッジ交差点は分解されて、画素の各辺に関して単一のエッジ交差点を形成する。たとえば、左方頂部画素サンプルポイント５０ａは右方交差点を有し、また右方頂部画素サンプルポイント５０ｂは左方交差点を有している。これら２個の交差点は分解されて、画素の上部側の１個のエッジ交差点を形成する。
【００４１】
エッジ分解のルールは以下の通りである： 
もし、どれかの画素サンプルポイントについてメッシュフラグが設定されなければ、メッシュ・アンチエイリアシングは選択されない。
【００４２】
画素の各辺に関して２個のサンプルポイントを選択する。
【００４３】
ｉ）もし、１個のエッジ交差点が存在すれば、有効なエッジ交差点フラグをゼロとし、そしてそのエッジ交差点フラグをデフォルト値（．５）に設定する。
【００４４】
ｉｉ）もし、サンプルポイントＡからの１個のエッジ交差点が存在し、そして他のサンプルポイントからのエッジ交差点が存在しなければ、有効なエッジ交差点フラグを１とし、そしてサンプルポイントＡのエッジ交差点に等しいエッジ交差点を設定する。
【００４５】
ｉｉｉ）もし、２個のエッジ交差点が存在し、そしてメッシュ・アンチエイリアシングが存在しなければ、有効なエッジ交差点フラグを１とし、そしてそのエッジ交差点を２個のエッジ交差点の平均とする。
【００４６】
ｉｖ）もし、２個のエッジ交差点およびメッシュ・アンチエイリアシングが存在すれば、有効なエッジ交差点フラグをゼロとし、そしてそのエッジ交差点フラグをデフォルト値（．５）に設定する。
【００４７】
もし、画素をアンチエイリアシングすべきであれば、その画素コーナー色彩を以下のように共にブレンドせねばならない：
エッジ交差点は０から１．０まで目盛りが付され、そして左方から右方へ、また上方から下方へ数字が大きくなる。
【００４８】
ｉ）もし、左方上部画素サンプルポイントがアンチエイリアシング無しとフラグが立てられるか、または画素サンプルポイントの全てが条件付きでアンチエイリアシングされているとしてフラグが立てられるか、あるいは有効なエッジ交差点が全く存在せず、そしてメッシュ・アンチエイリアシングフラグが設定されていれば、画素の色彩は左方上部の画素サンプルポイントの色彩である。
【００４９】
ｉｉ）もし、画素中に２個の有効エッジ交差点が存在すれば、領域を以下のルールに従って算定する：
もし（頂部交差点有効および底部交差点有効）であれば、 
領域_tl＋＝領域_bl＝（頂部交差点＋底部交差点）／４
領域_tr＝領域_br＝１／２−領域_tl
もし（右方交差点有効および左方交差点有効）であれば、 
領域_tl＝領域_tr＝（右方交差点＋左方_交差点）４ 
領域_bl＝領域_br＝１／２−領域_tl
もし（頂部交差点有効および左方交差点有効）であれば、 
領域_tl＝（頂部 交差点*左方_交差点）／２ 
領域_bl＝領域_tr＝領域_br＝（１−領域_tl）／３
もし（頂部交差点有効および右方交差点有効）であれば、 
領域_tr＝（（１−頂部 交差点）*右方交差点）／２
領域_bl＝領域_tl＝領域_br＝（１−領域_br＝（１−領域_tr）／３
もし（底部交差点有効および左方交差点有効）であれば、 
領域_bl＝（底部 交差点*（１−左方 交差点））／２ 
領域_br＝領域_tr＝領域_tl＝（１−領域_bl）／３
もし（底部交差点が有効および右方交差点が有効）であれば、 
領域_br＝（底部 交差点*（１−右方 交差点））／２ 
領域_bl＝領域_tr＝領域_tl＝（１−領域_br）／３
さもなければ、 
領域_tl＝（頂部 交差点＋左方 交差点）／４ 
領域_tr＝（１−頂部 交差点＋右方 交差点）／４ 
領域_bl＝（１−頂部 交差点＋左方 交差点）／４ 
領域_br＝（２−底部 交差点＋右方 交差点）／４
最終ブレンド画素色彩は等式：
色彩＝左方頂部画素隅の色彩＊領域_tl＋右方頂部画素隅の色彩＊領域_tr＋左方底部画素隅の色彩＊領域_bl＋底部右方画素隅の色彩＊領域_br
によって決定される。
【００５０】
図７を参照すると、もし画素６０当たり２ｘ２Ｓ緩衝化サブピクセルがより良好なサンプリングについて所望されるならば、画素分解を４のファクタだけ増加させ、次にポストフィルタ６２を適用してディスプレイ分解に至るまで画素を濾過することが出来る。
【００５１】
サブピクセル１１，１２，２１および２２は表示すべき画素上に横たわるサブピクセルである。取り囲んでいる１２個のサブピクセルは取出され、次に畳み込みフィルタを用いて、等式：
画素色彩＝Ｗ（サブピクセル１１＋サブピクセル１２＋サブピクセル２１＋サブピクセル２２／４）＋（１−Ｗ）（その他全てのサブピクセル／１２）
に従って算定される。
【００５２】
もし、重量Ｗが１．０であれば、取り囲むサブピクセルは全く使用されない。もし、Ｗが．７５であれば、ピラミッド形状のフィルタが生成される。もし、Ｗが．５であれば、均一なフィルタが生成される。
【００５３】
ここに開示された発明は適切に意図されて、先に述べた目的を実現させるものであることは明白であるが、数多くの変形および実施態様が当業者によって考案され得るものであることが理解されよう、また添付された請求の範囲は、本発明の真正な精神および範囲内に入るものとして、これら全ての変形および実施態様をカバーするものであることが意図されている。
【図面の簡単な説明】
【図１】
本発明による装置および方法が実施されるコンピュータ画像生成(CIG)システムを示す概略ブロック図である。
【図２】
物体空間における物体の多角形面と、画像空間における対応する画像の多角形面と、画像の多角形面が出現するディスプレイラスタの画素（ピクセル）との関係を示す空間図である。
ａ.表示すべき所望多角形の付近における図２の画像ディスプレイの拡大部分を示す図である。
【図３】
a.一対の多角形面が映像化されるディスプレイ画素のアレイを示す図である。
b. 多角形面が配置されるディスプレイ画素のアレイであって、各種の画素エッジＥおよびエッジ距離Ｄを示し、これらは画素の色彩データを決定するために用いられるものを示す図である。
【図４】
数本の画素境界と交差する多角形を示す図である。
【図５】
信号を交差するエッジのデータビットを同定する表を示す。
【図６】
エッジの交差点を分解するための手順を示す図である。
【図７】
サブピクセル・フィルタを概略的に示す図である。
【符号の説明】
１０  コンピュータ画像生成システム 
１２  コントローラ 
１４  ジョメトリープロセッサ 
１６  ディスプレイプロセッサ 
１６ａ  色彩純度サブアセンブリ 
１８  ビデオディスプレイ 
２０  オペレータ 
２２  入力制御インターフェース
【手続補正２】
【補正対象書類名】図面
【補正対象項目名】図５
【補正方法】変更
【補正の内容】
【図５】
2003505772.tif 000001
【手続補正３】
【補正対象書類名】図面
【補正対象項目名】図６
【補正方法】変更
【補正の内容】
【図６】
2003505772.tif 000002