JPH03212775A - アンチエイリアス多角形の描図方法及び装置 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔産業上の利用分野〕 本発明は、全体としてラスク型グラフィックディスプレ
イサブシステム上に描かれた多角形におけるエイリアシ
ングとして知られる階段波効果を低減させるための装置
と方法に関する。ラスク多角形の辺縁をなめらかにする
ことによって階段波効果を低減することはアンチエイリ
アシングとして知られている。殊に、本発明は、多角形
をピクセルあたりに何回もサンプリングするようなアン
チエイリアシング装置と方法に関する。

〔従来の技術〕

ラスフグラフインクディスプレイサブシステム上で多角
形を走査変換する作業は、２次元ラスク格子上の多角形
内部に位置するピクセルの座標を判断することにある。

多角形を構成する線分の内側のピクセルを十分に観察す
ると多角形を近似する階段状のパターンが結果される。

多角形に対するエイリアスを回避する既知の手法は、時
間を消費すると共に、計算集約的であって、ハードウェ
ア形式で実行する場合には広範で追加的なハードウェア
による支援が必要となろう。

かかるアルゴリズムは、ラスク型グラフィックディスプ
レイサブシステムが十分に高性能のサブシステムの場合
には、十分にそれらの所期の機能を果すであろう。然し
なから、低コストのワークステーションにおいては、価
格と競合するために、ラスフグラフイックディスプレイ
処理速度について種々の妥協が必要になる。かかるワー
クステーションにおいて命令の組が少ないコンピュータ
（ＲＩ　Ｓ　Ｃ”）中央処理装置（ＣＰ　Ｕ）を使用す
ると、プロセッサ性能において必要とされる妥協の度合
いが最小限になるが、伝統的なアンチエイリアスアルゴ
リズムを使用すれば、これらのワークステージジンにお
けるグラフインク応答は緩慢になるであろう。それ故、
今日、伝統的な技法よりも高速で計算集約的でない多角
形のアンチエイリアス装置と方法が必要とされる。

〔発明の要約〕

本発明によるエイリアスを除去した多角形を描くための
装置は、ホストデータプロセッサを備える。同ホストプ
ロセッサには１本のバスによってメモリが接続される。

ディスプレイは多角形を表示するための複数のピクセル
を備える。グラフィックプロセッサとディスプレイ間に
はフレームバッファが接続される。上記グラフィックプ
ロセッサは、イメージ配列をサンプリングするためのプ
ログラムを内蔵している。上記イメージ配列は、複数の
ピクセルか、同ピクセルのうちの一つ内部の複数の位置
の何れかを備えるようにプログラムによって選択的に再
構成できる。

本発明によるエイリアスを除去した多角形を描く方法は
、イメージ配列をサンプリングするためのプログラムを
内蔵するグラフインクプロセンサを設けることを含む。

イメージ配列は、プログラムによって選択的に構成され
、複数のピクセルか、同ピクセルのうちの一つの内部の
複数の位置の何れかを備えるようになっている。上記イ
メージ配列は構成された通りにサンプリングされる。こ
れらのステップによってエイリアスが除去された多角形
がつくりだされる。

〔実施例〕

さて図面、殊に第１図について述べると、エイリアシン
グを有する三角形１０が示されている。

上記三角形１０では、その内部に上部左手隅１４を有す
るピクセル１２が明示されている。図の如く、明示され
たピクセル１２は線分１６．１８．２０により画成され
る三角形に近似的にしか対応していない。ラスク型グラ
フィックディスプレイサブシステム上で三角形１０の如
き多角形を走査変換する作業は、２次元ラスク格子２２
の三角形１０内部に位置するピクセル１２の座標を決定
することである。線分１６−２０内のとクセル１２を十
分に明示すると、三角形に近似する階段波パターン２４
が生ずることになろう。

第２図は三角形１０をエイリアスされた形で描ぐための
装置３０のブロック線図である。ＣＰＵ３２はバス３６
により、浮動小数点プロセッサ（ＦＰＵ）３４に接続さ
れる。ＣＰＵ３２は３２ビツトシステムバス３８により
、グラフィックサダシステム４５内のランダムアクセス
メモリ（ＲＡＭ）４０、キャッシュ４２、およびインタ
ーフェース４４に接続されている。インターフェース４
４はバス４６によりグラフィックプロセッサ４８に接続
されている。グラフィックプロセッサ４８は１２のビッ
トグラフィックバス５０によってフレームバッファ５２
に接続されている。フレームバッファ５２は、バス５６
によりビデオデジタル／アナログ変換器（ＤＡＣ）５４
へ接続されている。

ＤＡＣ５４は、ライン６０によりビデオディスプレイ５
８に接続されている。

局部的な参照引き数は、グラフィックプロセッサ４８が
第３図に示すようにビクセル７２の矩形配列７０中のフ
レームバッファ５２を更新すべきことを指示する。以下
のアルゴリズムの記述は、例として４ｘ４の配列を使用
しているが、実際はこれと異なっていても差支えない。

多数のグラフィックプロセッサ４８を一緒に使用して、
フレームバッファメモリ５２に対して高い帯域幅を実現
するようにすることができる。グラフィックプロセッサ
４８の各々は、フレームバッファ５２内の何れの４　ｘ
　４　領域にもアクセスすることができる。

任意の位置に配置された時、上部左隅７４は原点を表わ
し、配列内の各ビクセル７２は、（ｘ、ｙ）偏差によっ
て表わされる。配列内のビクセル７２の位置はサイトと
称される。各サイトはそれに対応するビクセル７２に関
する情報を含む。

第３図に示す配列７０の２次元的表現は、配列７０内の
サイト７２とフレームバッファ５２内のビクセルの間に
直観的な１対ｌの写像が存在するためにアルゴリズムの
形を理解するためのガイドとして有効である。これは別
に、配列７０は第４図中の７６で示すように、線形状に
表現することもできよう。線形状の表現は、グラフィッ
クプロセッサ４８のチップがそのレジスタを実際に線形
にレイアウトする際にアルゴリズムのハードウェア構成
を記述するためにより有効であることが判る。

グラフィックプロセッサ４８における基礎的幾何形状の
基本は幾何学的半空間の評価である。第５Ａ、５Ｂおよ
び５０図に示すように、一つの面内の任意の線８０は同
面を２つの半空間８２と８４に分割する。上記半空間を
評価することによって１本の線８０の何れの側に点が位
置するかが判断される。１本の線の右側に対する点は全
て一方の半空間内にある一方、左側に対する点は全て他
方の半空間内にある。

グラフィックプロセッサ４８は以下の３つの幾何学的基
本形状、即ち、三角形、凸形の四辺形、および線をサポ
ートする。これらの基本形状を選んだのは、それが幾何
学的に単純で、それ以上の複雑な形状は上記基本形状で
構成できるためである。凸形の多角形の如きより？ｊ！
雑な形状はそれ以上の一般性を与えるが、グラフィック
サブシステムの複雑さがはなはだしく増加するという代
償を払わなければならない。任意の凸形多角形は、それ
らを記述するために必要とされるデータ量が無限である
ために、一つのグラフィックチップに対するアトミック
処理のサイズもまた無限になる。

グラフインクサブシステムによってはＣＰＵに割込みを
かけて多角形を走査変換中に新たな辺縁を追加するもの
がある。この手法は複雑なだけでなく、マルチプロセッ
サ環境においては受は入れることはできない。プロセッ
サの使用を効率化するには、１つのアトミック処理のサ
イズは小さくなければならない。複雑な多角形はＣＰＵ
３２によって容易かつ効率的に複数の三角形又は四辺形
でモザイク状に配列することができる。事実、陰影をな
めらかにするには、３つの点が一つの面を形成し、４つ
以上の点は制約を超えているために、１つの多角形を数
個の三角形に分解するとより優れた結果が得られるのが
普通である。

半空間幾何学の基本的数学は単純で、そのＶＬＳＩの製
作はすこぶる規則的かつ効率的に行うことが可能である
が、それ自体では半空間は２Ｄ又は３Ｄ（次元）図形に
対する有効な基本形状を何ら提供するものではない。然
しなから、第５Ｄ図に示すような三角形９２の内部９０
を考えてみよう。

上記三角形の内部は３つの半空間８２の交差したちの以
外の何者でもない。三角形９２は頂点９４を共有する３
つの辺縁８０でモデル化される。グラフィックプロセッ
サ４８は、１つの辺縁８０の何れの側にピクセル７２が
位置することができるかを判断することができる。同プ
ロセッサ４８は一つの辺縁８０に関連して１つのピクセ
ル７２を′＋′又は′−′とじてマーキングすることが
できる。′＋′はピクセル７２が辺縁８０に関して三角
形９２の内側にある一方、　−′はそれが外側にあるこ
とを意味する。ピクセル７２が三角形全体９２に関して
内側にあることを判断するための、３つの辺縁８０に関
して内側にあることの簡単なテストが成分半空間評価の
符号ビットの論理積として実行される。この半空間幾何
学法は４つの半空間の重なりにすぎない凸形四辺形につ
いても等しく十分にあてはまることは明らかである。

さて、基本的な構成ブロックが確立された。即ち、フレ
ームバッファメモリ５２の参照単位としての配列７０と
、何れのとクセルア２が幾何学的図形内に含まれるかを
判断するための半空間評価と、内側ピクセル７２におけ
る対象の属性を判断するための平面評価とである。サポ
ートされた形の基本モデルは半空間幾何学法の形で確立
されたが、配列メモリ５２を参照してのこれらの幾何学
的モデルの具現化はこれまでまだ行われていなかった。

幾何学的図形をタイル張りするための複数の配列基準の
発生は経路追跡と称され、使用される半空間表現によっ
て容易に実現される。グラフィックプロセッサ４８のア
ルゴリズムは、それぞれの配列基準における半空間幾何
学形状をテストして、何れの方向に幾何学図形が延びる
かを判断することにより、次の配列基準がどこでなけれ
ばならないかを表示する。この配列の移動は幾何学的図
形全体がタイル張りされ終るまで続けられる。

第６図は三角形１００をタイル張りするために基本配列
７０がどのように使用されるかを示す。配列７０は三角
形１００の頂点１０２に位置決めさ゛れた後、線１０４
に沿って下左方向へ移動され、線１０６と交差するまで
何度も繰返し右方向へ走査される。これらの処理は線１
０８に達し、配列７０により走査されるまで繰返される
。

半空間評価器に基本的形状として与えられる幾何学的形
状の構成は幾何学的にも概念的にも魅力的である。半空
間表現はピクセル座標でサンプリングされる数学モデル
で、フレームバッファ５２に対する表現を離散的なもの
にする。概念上は、ピクセル周波数でサンプリングされ
たこの数学的表現は共通のコンピュータデータベースの
作成にとって重置でニレガントな方法を提供する。以下
の説明は、この着想上の優雅さが実施の簡易化に資する
ことによって比較的低コストで高い平行性を提供するこ
とを示す。

半空間を求めるために使用される基礎数学は次の一般的
な線形等式に基づいている。

ｙｚｍｘ十す 但し、ｍは線の勾配であり、ｂはｙの切片である。

上記等式は線の一方側のｖＡｙ＞ｍｘ＋ｂのＸとｙの値
について、他方側のｙ＜ｍｘ十すのＸとｙの値について
あてはまる。（ｘ　１．　　ｙ　１）と（ｘ２゜ｘ２）
を通過する特定の線については、線方程弐の定数は以下
の通りとなる。

、ｍ＝ｄｙ／ｄｘ ｂ＝３’　１−ｄｙ／ｄｘ　　ｘ　１ 但し、ｄｙ＝ｙ２−ｙｌ、およびｄｘ＝ｘ２−ｘｉであ
る。

これらの値は未知数ｍとｂについて次の連立方程式を解
くことによって求めることができる。

ｙｌ＝ｍｘｌ＋ｂ ｙ２＝ｍｘ２＋ｂ かくして、（ｘＬｙｌ）と（ｘ　２．　　ｙ　２）の２
点によってパラメータ化される半空間を求めるには、以
下の一次方程式を解く必要がある。

Ｖ＝ｄＶ／ｄｘ　Ｘ＋ｙｌ−ｄｙ／ｄｘ　ＸＩ　　　　
　　　（１）先の議論の数学は実数体系で提示したもの
である。然しなから、ラスタフレームバッファをアドレ
ッシングするには、Ｘとｙの実数値を離散化する必要が
ある。この離散化は第７Ａ図に示すようにサンプリング
として知られている。簡単なラスフグラフインクの目標
は離散的なピクセル７２アドレスで半空間式をサンプリ
ングしてピクセル７２あたり１つのサンプリング点を表
わすことである。このようにすると、グラフィンクプロ
セッサ４８アレイ７０内の各ピクセル７２はそれが幾何
学図形の内側にあるか、それとも外側にあるかを判断す
ることができる。

これとは別に、一定のアンチエイリアシングアルゴリズ
ムは、第７Ｂ図に示すようにスーパーサンプリングする
ことによって幾何学図形内のピクセル７２の割合ヲ判断
する。１つのビクセル７２から多数のサンプル１２０を
取り平均化すると、もしそのサンプル数が十分に大きな
ものである場合にはすこぶる良好なアンチエイリアリン
グ効果を得ることができる。サンプリング周波数は前述
の数学から独立しているために、相異なるアルゴリズム
で同一の線方程式を異なる周波数でサンプリングするこ
とができる。

端点をビクセル中心１２２にあてるとエイリアスなし画
像としては不十分な結果が生みだされる。

また、エイリアスを有する画像はサブピクセルの位置決
めにより改善されるものがあろう。但し、その改良効果
は映像の品質が低いために、それ程劇的なものではない
。端点を現在のフレームバッファのメモリコストとビデ
オ帯域幅とが可能にするよりも高度な解像度で位置決め
できるようにすることは非常に重要である。それ故、グ
ラフィックプロセッサ４８は、多角形の頂点と線の端点
については固定小数点表記法を使用している。第８図に
示すように、各とクセルア２は、（ｏ、ｏ）が上部左隅
１２４にあるような８ｘ８格子に分解される。グラフィ
ックプロセッサ４８に対して与えられる座標はピクセル
７２座標に対して付加されるサブピクセル１２０の位置
として見ることができる。座標（ｘ、ｙ）はサブピクセ
ル座標値（ｘＨｏｄ　８、ｙｍｏｄ８）を有するビクセ
ル（Ｘｄｉｖ　８．　　ｙｄｉｖ　８）に配置される。

データはサブピクセル１２０のフォーマットか基本ビク
セル７２の座標フォーマットの何れかの形態でグラフィ
ックプロセッサ４８に与えることができる。もしビクセ
ル７２の座標フォーマットが使用されるばあいには、チ
ップに入るや否や、グラフィックプロセッサ４８は内部
で即座に３ビツトだけ左へデータをシフトさせることに
なろう。

このための数学式は非常に簡単である。次の等式（１）
に戻ろう。

Ｖ＝Ｌｈ／ｄｘ　Ｘ＋ｙｌ−ｄｙ／ｄｘ　Ｘｉこの等式
は、ビクセル座標系に対して何ら厳格な束縛は有しない
ことに注意されたい。外面的には、等式が表出される座
標系は意味を有さない。即ち、上記数学式は依然として
有効である。かくして、ｄｘ、ｄｙ、ｘｉ、およびｙｌ
は８倍だけスケールアップされることによってサブピク
セル１２０の座標値が得られる。先の場合には、我々は
各ビクセル７２が１単位に相当する座標系内でサンプリ
ングしていたために、（０，１，２，３・・・・・・）
というＸとｙの値にのみしか関心がなかった。今度は、
各ビクセル７．２においてサンプリングするために、我
々は（０，８，１６，２４・・・・・・）という値でサ
ンプリングすることになろう。我々の新たな座標系は８
倍大きくなったために、ピクセル７２は８単位離れ、こ
の間隔はピクセルあたり１サンプルを与えることになろ
う。アドレスのサブピクセル部分が（０，０）である場
合には、サンプリングは１ピクセルの上部左隅１２４で
行われることに注意されたい。

半空間を求める上記技法が与えられた場合、次のステッ
プはこの数学式をグラフィックプロセッサ４８を介して
フレームバッファに適用することである。第９図に示す
ように、グラフィックプロセッサ４８は４　ｘ　４　領
域１３０を平行して更新できることを想起されたい。か
くして、スクリーン上の所与の４ｘ゛４ＳＭ域１３０の
何れについても、１６の座標値の各々においてｙ＝ｄｙ
／ｄｘ　Ｘ＋ｙｌ−ｄｙ／ｄｘの線形等式を平行して求
めることによって、１回の評価回数で１６のサイト７２
の各々について内側にあるかどうかが判断されることに
なろう。４ｘ４よりも大きな領域について半空間を求め
るためには、配列１３０をその領域にわたって引きずっ
て領域を完全にタイル張りする必要がある。もしその評
価時間がＶＲＡＭアクセスタイムよりも小さいか、それ
に等しくすることができれば、更新はアルゴリズムの速
度ではなくメモリアクセスによって制約される。

１ ラスク装置は本質上離散値でサンプリングするために、
１つの半空間はフレームバッファ５２内の各ピクセル７
２における線形方程式を求めることによって求めること
ができる。実際には、所望結果に近似したピクセルのみ
が求められる。概念上は簡単であるが、半空間の評価を
ＶＬＳ　Ｉによって実行することが安価かつ効率的に実
行できるということは容易には明らかでない。以下の記
述は、線形方程式を離散値で平行して求める場合の非常
に簡単かつ効率的な手法を述べたものである論理上の出
発点は以下の線形方程式である。

ｙ＝ｍｘ＋ｂ （ｘ　２．　　ｙ　２）と（ｘ　２．　　ｙ　２）間の
線分について、その定数は、 ｎ　＝　ｄ　ｙ　／　ｄ　ｘ ｂ＝ｙｌ−ｄｙ／ｄｘ　　ＸＩ、となる但し、ｔｉｙ＝
ｙ２−ｙｌ、ａ　ｘ　＝　ｘ　２−　ｘ　ｌである。

従って、ｙ　＝ｄｙ／ｄｘ　Ｘ＋ｙｌ−ｄｙ／ｄｘ　Ｘ
ｉｙ　−ｄｙ／ｄｘ　Ｘ　−（ｙｌ−ｄｙ／ｄｘ　ＸＩ
）　＝　０除算は数値上高価で精度の損失をもたらすか
ら、両辺をｄｘにより乗する。即ち、ｄｘｙ−ｄｙｘ−
ｄｘｙｌ＋ｄｙｘｌ＝０上記等式の左辺は線上の（ｘ、
ｙ）については０であり、線の一方側は正で、他方側は
負である。ｄｘ４配列内の各サイトにおける等式の符号
を求めるだけで、グラフィックプロセッサ４８は、各ピ
クセル７２における辺の内外性を判断することができる
。然しながら、ＶＬＳＩ製造上求め６れる単純さは、ｄ
ｘｙとｄｙｘの計算がまだ余りも難しく、それぞれのサ
イトにおいて２個の乗算と１個の加算を伴うことになる
ために、従来よりまだ達成されていなかった。これはダ
イの寸法と実行時間の双方において禁止的に高くする。

簡単な置換を数回実行することにより、上記乗算はピク
セルあたりの段階から半空間あたりの段階へ移行させる
ことによってピクセル評価段階には符号を比較する一回
の加算を残すだけとすることが可能である。

さて、（ｏｒｉｇｉｎｘ、　ｏｒｉｇｉｎｙ　）を領域
１３０の原点を表わすものとしよう。同様にして、（ｏ
ｆｆｓｅｔｘ。

ｏｆｆｓｅｔｙ）をその原点からの偏差であるとするこ
とによってｘ　＝ｏｒｉｇｉｎｘ　＋ｏｆｆｓｅｔｘ、
およびｙ＝ｏｒｉｇｉｎｙ＋ｏｆｆｓｅｔｙとなるよう
にする。

Ｘとｙを置換すると、 ｄｘ　（ｏｒｉｇｉｎｙ　＋　ｏｆｆｓｅｔｙ）　−ｄ
ｙ　（ｏｒｉｇｉｎｘ　＋　ｏｆｆｓｅｔｘ）−ｄｘｙ
ｌ　＋ｄｙｘｌ　＝　Ｏ ｄｘｏｒｉｇｉｎｙ　＋　ｄｘｏｆ　ｆｓｅｔｙ　−ｄ
ｙｏｒｉｇｉｎｘ　−ｄｙｏｆ　ｆｓｅｔｘｄｙｙｌ　
＋　ｄｙｘｌ　＝　０ 上記等式を再編成して最終的な等式を得ると、ｄｘｏｆ
ｆｓｅｔｙ−ｄｙｏｆｆｓｅｔｘ＝ｄｘｏｒｉｇｉｎｙ
＋ｄｙｏｒｉｇｉｎｘ＋　ｄｘｙｌ　−ｄｙｘｌ ｄｘｏｆｆｓｅｔｙ−ｄｙｏｆｆｓｅｔｘ＝　　　　　
　　　（２）−ｄｘｏｒｉｇｉｎｙ＋ｄｙｏｒｉｇｉｎ
ｘ＋　　　　　　　（３）ｄｘｙｌ　−ｄｙｘｌ　　　
　　　　　　　　　（４）妥当性の持続時間と共に異な
る等式の評価が発生する時に注意されたい。

等式によっては半空間全体について一度で計算されるも
のもあれば、配列１３０の１段階毎に１度に計算される
ものもある。（即ち、配列１３０が移動した時、同等式
は求めなおす必要がある。）何れの等式もサイトあたり
１回では求められない。

かくして高次の平行性がすこぶる低コストで実現するこ
とができる。ｄｘ、ｄｙ、ｘｉ、ｙｔの値は一定の幾何
学的半空間の定義については一定であることは明らかで
、（４）が半空間あたり１度求められ、配列１３０内の
位置や配列１３０の移動によって影響を受けないことを
示す。

ｏｆｆｓｅｔｘとｏｆｆｓｅｔｙは正の整数（０１８，
１６，２４）であってチップの原点からのＸとｙの偏差
を表わし、これら値はチップ内に組込まれる。上記値が
（０，１，２，３）ではなくて（０，８，１６，２４）
であるのは、格子がサブピクセル位置決めの形をとり、
サンプリングピクセルあたり１回行われるためである。

か（して、（２）もまた線全体について一回計算される
。更に、その求め方は、その値が規則的な間隔をおいて
いるために、ｄｘとｄｙを逐次的に加算するように単純
化することができる。等式（２）は配列内の位置に依存
する値のみを含む。

配列１３０の位置によって影響を受ける唯一の表現は（
３）であり、ｄｘｏｒｉｇｉｎｙ−ｄｙｏｒｉｇｉｎｘ
である。このため、配列１３０内のサイト７２あたり２
個の乗算と１個の加算に対して、配列の一段階あたり２
個の乗算と１個の加算のみが残されることになる。

本文節は先の文節からのアルゴリズムを実行するための
簡単なＶＬＳ　１回路を記述する。次の線分方程式 ％式％ （２） （３） （４） は、配列１３０内の各サイト７２について異なる唯一つ
の開環式（２）のみを有する。この項はｏｆｆｓｅｔｘ
とｏｆｆｓｅｔｙについて許される値の１６の置換全体
について計算されなければならないから、その計算は一
見最もきつい計算であるように思われる。幸いなことに
、離散的格子１３０の規則性によって非常に効率的に実
施することが可能である。テーブル■と■は（２）の開
環式、ｄｘｏｆｆｓｅｔｙとｄｙｏｆｆｓｅｔｘに対し
て必要とされる値の規則性を示す。

テーブル■ ｄｘ ｏｆｆｓｅｔｙ ｄｘ ８ｄｘ＋８ｄｘ ８ｄｘ＋３ｄｘ＋８ｄｘ テーブル■ ｄｙ　ｏｆｆｓｅｔｘ ■ Ｂｄｙ ８ｄｙ　＋　８６ｙ ８ｄｙ　＋　Ｂｄｙ　＋８ｄｙ これらのテーブルの生成は簡単である。アレイ７０内の
各値（第１０図）は単にｄｘ又はｄｙの８倍にすぎず、
３だけ右シフトとして実行され、アレイ内の先の値に加
算される。ひとたび、これらの値が得られると、（２）
は１６個のサイト７２の各々において、−回の減算・ｄ
ｘ　ｏｆｆｓｅｔｙ−ｄｙ　ｏｆｆｓｅｔｘによって計
算される。上記サイトはすこぶる効率的な収縮配列構造
により連続的に満たされる。この減算結果は、第１０図
に示すように、１６個のサイト１４０の各々に記憶され
なければならない。

線形等式におけるその他の項は、配列内の偏差から独立
している。（３）＋　（４）の和は半空間定数と称され
る。半空間等式からの（２）が図の如くサイト１４０の
各々に記憶されると仮定した時、サイト値と半空間定数
の和の符号は線８０に対するピクセル７２の偏りを示す
ことになろう。

（第５Ａ−５Ｄ図）半空間定数はサイト偏差座標とは独
立であるから、同じ値がサイトの各々に加算される。か
くして、ＶＬＳ　Ｉ構造１５０（第１１図）はすこぶる
単純である。−本のｎビットバス１５２が各サイト１４
０における値を横切って走り、サイト１４０に記憶され
る値に加算される。符号ビットが唯一関心のあるビット
であるから、加算器の代わりに振幅コンパレータ１５４
を使用するだけで十分である。かくして、各サイト１４
０は振幅コンパレータ１５４とレジスタ１５６を備える
ことによってサイト１４０の値を保持する。コンパレー
タ１５４はどの半空間内に各ピクセル７２が存在するか
を判断する。第１１図は、配列内の各サイト１４０につ
いてＶＬＳ　Ｉセルのブロック線図を示す。上記レジス
タは、半空間が初期化された時にバス１５２からロード
される。

配列７０が移動する毎に、レジスタ１５６の内容はバス
１５２上の半空間定数と比較される。１６０における回
路の出力は比較結果である。

第１１図は、ＶＬＳ　Ｉ構造を構成し、配列７０内の１
６個のサイト１４０の各々で半空間の平行評価を実行す
るサイトセル１６０の集合１７０を示す。この構造は半
空間評価器又は半空間タワーと称される。バス１５２の
配線の列は一つの値（３）＋　（４）を表わし、サイト
１４０に記憶される値の各々に加算される。各サイト１
４０は、第１１図に示すようにコンパレータとレジスタ
を含む。各サイト１４０から到来する線は、どの半空間
にサイトのピクセル７２が位置するかを示すプール値で
ある。

半空間評価器に対して回路１４０が与えられているとす
ると、第１２図に示すような四辺形評価器は自明である
。同じ回路は、四辺形の各辺縁について１回ずつ、計４
回使用される。４つの半空間評価器における相当するサ
イトのプール結果は、論理積がとられ、各ピクセル７２
の内外性が判断される。もし１ピクセル７２が４つの辺
の全てについて四辺形内にあれば、それは四辺形内部に
あることになる。さもなければ、外側にあることになる
。同様にして、線評価器は、４つの半空間評価器を使用
して先に提示された線モデルを実現する。３角形モデル
には評価器のうち３つしか必要でないため、第４番目の
ものを無効とする。第１２図は、個々の半空間タワー１
７０の相互作用を示す。タワー１７０を横切って走るプ
ールワイヤ１６０は、ワイヤード論理積の演算がなされ
て最終結果がつくりだされる。

各サイトのプールワイヤ１６０とフレームバフフッ５２
内のピクセルの間に一対一の対応関係を実現するために
、ワイヤ１６０は直接、グラフィックプロセッサ４８上
のパッドへ向かい、グラフィックプロセッサ４８は今度
は個々のメモリチップに対してワイヤイネーブルとなる
。１６のピクセｉしは１６個の異なるメモリチップ内に
あるため、ワイヤはピクセルを個別的に制御することに
なる。

′１′はメモリチップをライトイネーブルとする一方、
′Ｏ′はそれをイープル不能とする。

コンピュータグラフインク分野が成長するにつれて、視
覚上の迫真性に対する要求が強まってい名。レイトレー
シング、テクスチュアマッピング、アンチエイリアシン
グ、トランスペアレンジ−およびその他の多くの技法が
効果的に使用されてリアルな映像がつくりだされている
。これらの技法は圧倒的にソフトウェア志向的であるか
、又はすこぶる高価な専用ハードウェアを使用してきた
。

グラフィックプロセッサ４８における幾何学的単純さと
豊かなフレームバンファ更新技術は、先端的な描画技法
のうちのい（つかをハードウェア内へ移行させるに十分
な機会を提供する。

連続的な幾何学的表現から離散的なピクセル表現へ幾何
学的形状を変換することに伴うサンプリングの場合、辺
縁部に刻み目がついたり詳部が失われたりするといった
欠陥が生ずる。上記問題点はエイリアシングと称され、
幾何学図形のサンプリング不足によって引き起こされる
ものである。

標準的なラスフグラフイックでは、線と多角形は離散的
な格子位置やピクセルでしかサンプリングされない。エ
イリアシングは、特に、サンプリング周波数が低い低解
像装置上に出現する。解像度が増すにつれて、エイリア
シングを発見する人間の目の能力は低下する。ディスプ
レイの解像度に係わりなく、離散的な格子位置における
サンプリングがエイリアシングを除去することは決して
ないであろう。然しなから、そのことによって我々のエ
イリアシングを検出する能力は低下するであろう。この
段落はグラフィックプロセッサ４８により使用されるア
ンチエイリアシング手法を説明する。以下の解説は三角
形のみを取扱うものであるが、同手法はサポートされた
幾何学的基本形状の全てについても効果がある。

グラフィックプロセッサ４８は、エイリアシング効果を
駆逐するためにスーパーサンプリングとして知られる技
法を使用する。スーパーサンプリングとはディスプレイ
ハードウェアがサポートするよりも高解像度でサンプリ
ングしてピクセル解像度にまで平均化することを意味す
る。フレームバッファ５２のメモリは貴重な商品である
。から、シーン全体をスーパーサンプリングした後に平
均化することは誤りであろう。ディスプレイ解像度の１
６倍でサンプリングするにはフレームバッファメモリ５
２の１６倍が必要となるであろう。より費用効果的な方
法は、ｌピクセル７２中に１６個のサンプルをとり（第
１３図）、一方、多角形をラスター化して、１６サンプ
ルを平均化した後、フレームバッファに書込むことであ
る。正規（エイリアス化）モードでは、グラフィックプ
ロセッサ４８はチップ内の１６のサイトを使用して１６
個のビクセル７２をサンプリングする。アンチエイリア
スモードで三角形や線を描く場合には、グラフィックプ
ロセッサ４８は１６サイトを使用して、１個のピクセル
７２内の１６個の位置１２０でサンプリングする。メモ
リ帯域幅全部は実現できないのでその性能はアンチエイ
リアシングには十分でないことに注意されたい。

これは既に提示したアルゴリズムとすこぶる容易に適合
する。アンチエイリアシング用アルゴリズムは、我々が
以前に提示した同じ辺等式を使用する。即ち、 ｄｘ　ｏｆｆｓｅｔｙ−ｄｙ　ｏｆｆｓｅｔｘ＝　−ｄ
ｘ　ｏｒｉｇｉｎｙ＋ｄｙ　ｏｒｉｇｎｘ＋ｄｘ　ｙｌ
−ｄｙ　ｘｉｄｘ　ｏｆｆｓｅｔｙ−ｄｙ　ｏｆｆｓｅ
ｔｘ　−−ｄｘ　ｏｒｉｇｉｎｙ＋ｄｙ　ｏｒｉｇｉｎ
ｘ＋ｄｘｙｌ−ｄｙｘｌ 座標はビクセル解像度から８だけスケールアップされる
ため、この等式を（０１２，４，６）のｏｆｆｓｅｔｘ
とｏｆｆｓｅｔｙの値で計算すると、一つのビクセル７
２内に１６の等間隔のサンプルが得られることになろう
。上記ビクセル７２におけるカラー値は、多角形内部の
サンプル点におけるカラー値の和を採用したサンプル総
数（１６）によって除したものである。サンプル総数は
２の累乗であるから、除算は演算シフトに帰する。かく
して、アンチエイリアスビクセル値の計算公式は以下の
通りになる。

６ 上記のアンチエイリアス処理は三角形が１個の場合には
効果があるが、１辺を共有する２つの３角形の場合につ
いて考えてみよう。最初の三角形はアンチエイリアス処
理され、フレームバッファ５２内へ配置され、その後、
第２の三角形がアンチエイリアス処理されてフレームバ
・７フア５２内へ配置される。両方の三角形内にあった
辺に沿うビクセルは第２の三角形の値のみを有すること
になろう。然しなから、第１の三角形からのカラー値は
残存なし、第２の三角形からのカラー値と混合されなけ
ればならない。しかし、第２の三角形を描く場合、その
カラー混合を適当に処理するにはまだ十分な情報が存在
しない。第１４図は、２個の三角形１８０と１８２が隣
接し、ビクセル７２が′＋′とマーキングした共通の辺
１８４に沿って存在する様子を示す。

遮蔽されるビクセルの割合を表示する別のビクセル情報
を維持する必要がある。これは一般にα又は遮蔽チャネ
ルと呼ばれてきた。グラフィックプロセッサ４８は８ビ
ツトのαチャネルを維持することになろう。１ピクセル
におけるαチャネル中の０はビクセルが空であることを
示す。αチャネル中の２５５はビクセルが完全に遮蔽さ
れたことを示す。多角形の境界上のビクセルはＯと２５
５の間の何れかの値をとり、それらが一部遮蔽されたこ
とを示すのが普通であろう。１つの三角形における１ピ
クセルのα値は、採用されたサブピクセルサンプルの総
数により除せられた三角形内部のサブピクセルサンプル
数によって判断される。これは０と１の範囲内の数であ
って、その後Ｏ〜２５５の範囲にスケーリングされる。

αの実際の計算値はちょうど三角形内部のサンプル数に
１６を乗じたもので、その値は２５５でクランピングさ
れる。上記値をクランプしなければならないのは、もし
１６個のサンプルが全て三角形内部にあると、工６を乗
じても固定小数点数系で１が２重に表示されるために２
５６が得られることになるためである。

アンチエイリアス三角形は前後にソートしてその順序に
描かれる必要がある。その基本的典型例はブロックが一
杯になるまで１ピクセルを増加することであり、他の三
角形は全てそのビクセルに隠れてフレームバッファ５２
には加えられないということを意味する。かくして、Ｘ
ソートと共に、αチャネルは隠れた表面を解像する。フ
レームバッファ５２を増加する場合、次の公式が使用さ
れる。

ｔ　ｈａｗ＝　ｌ　ｔｂ　十ＭＩＮ（１−αｔｂ＋　　
αｊｒｉ　　）ｌｔｒ＝α、１．１−αｒｂ＋ＭＩＮ（
１−αｆｂ＋　　αｔ１、）但し、 αｆｂ＝フレームバンファ内の現在のα値１ｔｂ＝フレ
ームバツフア内の現在の強度値αｔｒｉ＝（三角形内部
のサブビクセルサンプル数にもとづく）新たな三角形か
らの α値 ｉ、□＝新たな三角形からの強度値 αｎｅｗ　＝フレームバッファ内へ入力されるα値ｉ□
、＝フレームバッファ内へ入力される強度イｄ蔓 上記公式は、０〜ｌの範囲内の正規化されたα値を使用
する。

この方法はルーカスフィルムで使用されるＡバッファア
ンチエイリアス隠面アルゴリズム程確実ではないが、大
きな規模用途で十分効果があり、ハードウェア内で実施
することがずっと容易である。グラフィックプロセッサ
４８のアルゴリズムは簡単で、メモリ要求条件はずっと
少なく、ルーカスフィルムＡバッファにより必要とされ
るメモリは、フレームバッファの大きさと共にシーンの
複雑さにより制約を受ける。グラフィックプロセッサ４
８のメモリ要求条件は、フレームバッファ５２のサイズ
によってのみ制約される。Ａバッファに対するその制約
は、１ピクセルのどの部分が以前遮蔽されたかをＡバッ
ファが認識できず、Ｚでオーバーラツプする多角形どう
しの間の隠面問題を解決できないことである。これらは
、アンチエイリアス多角形から得ることのできる多数の
用途にとっては程良く小さな制約であると考えられる。

【図面の簡単な説明】

第１図は本発明の理解に有効なエイリアス多角形図、 第２図は本発明によりアンチエイリアスな多角形を描く
ためのシステムの概略ブロック線図、第３図は第２図の
システムに使用されるような２次元ピクセルアレイ図、 第４図は、第３図の２次元アレイがどのように線形アレ
イに変換されるかを示す線図、第５Ａ〜５Ｄ図はどのよ
うにして多角形が第２図のシステム内に表現されるかを
示す図、第６図は本発明の方法の一部を示す線図、第７
Ａ図と第７Ｂ図は、本発明の方法のもう一つの部分を示
す２次元ピクセルアレイ図、第８〜９図は、更に、本発
明の方法の追加的部分を示す２次元ピクセルアレイ図、 第１０図は、第４図のものと同様な線図で、本発明の方
法を理解するために有効な一定の数学的表現を備えたも
の、 第１１図は第２図のシステムの一部の詳細ブロック線図
、 第１２図は第２図のシステムのそれ以上の部分を示すも
う一つの詳細ブロック線図、 第１３図は本発明の方法を理解するに有効な２次元ピク
セルサブアレイ図、 第１４図は本発明の方法の一部の動作を示す２次元ピク
セルアレイ図。 １０・・・・・・三角形、１４・・・・・・上部左手隅
、１２・・・・・・ビクセル、１６．１８．２０・・・
・・・線分、２２・・・・・・２次元ラスク格子、２４
・・・・・・階段波パターン、３６・・・・・・バス、
３４・・・・・・浮動小数点プロセッサ、３２・・・・
・・ＣＰＵ、４Ｂ・旧・・グラフィックプロセッサ、５
０・・・・・・１２０ビツトグラフイツクバス、５２・
・・・・・フレームバッファ、５４・・・・・・ビデオ
デジタルアナログ変換器。 手 続 補 正 書（方式） ％式％ １、事件の表示 平成２年特許願第３１１２２３号 ３、補正をする者 事件との関係 出 願人 ４、代 理 人 ５、補正命令の日付 平成３年２月１２日

Claims (1)

1. 【特許請求の範囲】 １、ホストデータプロセッサと、同プロセッサに対して
   １本のバスで接続されるメモリと、同バスに接続される
   グラフィックプロセッサと、複数のピクセルを備え多角
   形を表示するディスプレイと、上記グラフィックプロセ
   ッサとディスプレイ間に接続されるフレームバッファと
   、から成り、上記グラフィックプロセッサが一つのイメ
   ージ配列をサンプリングするプログラムを内蔵し、上記
   イメージアレイが上記プログラムにより選択的に再構成
   でき、複数のピクセル又は同ピクセルの一つ内に複数の
   ロケーションの何れかを備えるアンチエイリアス多角形
   の描図方法。 ２、イメージ配列をサンプリングするためのプログラム
   を内蔵するグラフィックプロセッサを有するアンチエイ
   リアス多角形の描図装置において、上記イメージアレイ
   が上記プログラムによりサンプリングすべく選択的に再
   構成可能であって、複数のピクセル又は同ピクセルの一
   つ内に複数のロケーションの何れかを備える前記装置。 ３、イメージ配列をサンプリングするためのプログラム
   を内蔵するグラフィックプロセッサを設け、上記イメー
   ジ配列を上記プログラムにより選択的に構成して複数の
   ピクセル又は同ピクセルの一つ内に複数のロケーション
   を構成し、上記の如く構成されたイメージ配列をサンプ
   リングして多角形をアンチエイリアス処理するアンチエ
   イリアス多角形の描図方法。