JPH0916144A

JPH0916144A - 二次元でインターリーブされるフレームバッファを備えた、三角形ラスタ化のためのシステム及び方法

Info

Publication number: JPH0916144A
Application number: JP8147638A
Authority: JP
Inventors: Bryan G Prouty; ブライアン・ジー・プロウティー; Ronald D Larson; ロナルド・ディー・ラーソン
Original assignee: Hewlett Packard Co
Current assignee: HP Inc
Priority date: 1995-06-08
Filing date: 1996-06-10
Publication date: 1997-01-17
Also published as: US5982384A; GB2302002A; GB9611742D0; GB2302002B; FR2735267B1; DE19619288A1; FR2735267A1

Abstract

(57)【要約】【課題】本発明の目的は、処理時間を向上させるため
に、二次元でインターリーブされる、多数のフレームバ
ッファコントローラを提供することである。【解決手段】上記目的は、基本要素データを受け取り、
一連のスパンラインデータを生成する、エッジステッパ
と、前記一連のスパンラインデータを受け取り、前記一
連のうちの各スパンラインデータに基づいて、一連のサ
ブスパンデータを生成する、サブスパンステッパと、前
記一連のサブスパンデータの各々を受け取り、前記サブ
スパンデータに対応する画素データを生成する、スパン
ステッパとからなるフレームバッファコントローラによ
り達成される。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】本発明は、一般に、コンピュ
ータグラフィックスシステムにおけるラスタ化システ
ム、及び方法に関し、更に詳細には、二次元でインター
リーブされるラスタ化のためのフレームバッファに関す
る。

【０００２】

【従来の技術】コンピュータグラフィックスシステム
は、二次元表示画面上に、対象物の図的表現を表示する
ために、広く用いられる。現在のコンピュータグラフィ
ックスシステムは、非常に細かい表現を与えることが可
能であり、様々な用途に使用されている。

【０００３】通常のコンピュータグラフィックスシステ
ムでは、表示画面上に表現すべき対象物が、複数の図形
基本要素に分解される。基本要素は、図形ピクチャの基
本的な構成要素であり、点、線、ベクトル、及び三角形
等の多角形を含む。通常、二次元表示画面上で、その画
面上に表現される、１つ以上の対象物の映像を表現す
る、図形基本要素を描画するために、ハードウエア／ソ
フトウエア方式が実施される。

【０００４】通常、描画すべき三次元対象物を規定する
図形基本要素は、ホストコンピュータから与えられ、ホ
ストコンピュータは、基本要素データに関連して、各基
本要素を規定する。例えば、基本要素が三角形である場
合、ホストコンピュータは、この基本要素を、その頂点
のｘ、ｙ、ｚ座標だけでなく、各頂点のＲ、Ｇ、Ｂ色値
にも関連して規定する。ラスタ化ハードウエアは、この
基本要素データを補間して、各基本要素を表現するため
に点灯される表示画面の画素、及び各画素に対するＲ、
Ｇ、Ｂ値を計算する。

【０００５】図１は、典型的なラスタ化ハードウエアの
構成要素を示す。フレームバッファコントローラ１は、
エッジステッパ３、スパンステッパ５、及びメモリコン
トローラ７を含む。エッジステッパ３は、基本要素デー
タからの補間を通して、基本要素の各エッジに沿った画
素、及びそれに対応する色値を決定する。エッジステッ
パ３によって決定された画素は、この基本要素内の画素
ラインの端部での点を規定する。画素ラインは、スパン
と呼ばれる。スパンステッパ５は、画素ラインの各々に
対して、エッジステッパから画素データを受け取り、そ
の画素ライン内の各画素に対して、色値を決定する。画
素値、及び色値は、メモリコントローラ７に与えられ、
メモリコントローラ７は、この情報をビデオ用ランダム
・アクセス・メモリ（ＶＲＡＭ）９に書き込む。表示コ
ントローラ（図示せず）が、ＶＲＡＭの内容に基づい
て、ディスプレイを駆動する。

【０００６】

【発明が解決しようとする課題】エッジステッパ３、及
びスパンステッパ５における計算処理は複雑であるた
め、この処理は低速となり得る。２つ以上のフレームバ
ッファコントローラを並列に用いることによって、処理
速度を増大することができる。図２は、２つの並列フレ
ームバッファコントローラ１、２を示す。フレームバッ
ファコントローラ１、２は各々、エッジステッパ３、
４、スパンステッパ５、６、及びメモリコントローラ
７、８を含む。メモリコントローラ７、８は、別個のＶ
ＲＡＭ９、１０に接続されている。表示コントローラ
は、ＶＲＡＭ９、１０の両方に記憶された画素を組み
合わせて、最終的な表示を生成する。並列動作時には、
各フレームバッファコントローラは、画面の指定された
ラインに対する値（画素のスパン）を決定する。各フレ
ームバッファコントローラ１、２におけるエッジステッ
パ３、４は、未指定の画素ラインを飛び越す。図２は、
２つのフレームバッファコントローラを示すが、任意の
数が可能である。多数のフレームバッファコントローラ
を並列に使用すると、処理速度を増大することができる
が、各フレームバッファコントローラへのスパンライン
の割当ては、効率が低下する可能性がある。基本要素の
形状、及び配向に依存して、フレームバッファコントロ
ーラにおけるスパンラインに対する処理時間は、広範に
変動し得る。例えば、高さが小さく幅の広い三角形の基
本要素の場合、一方のフレームバッファコントローラ
が、この基本要素の基部での大きな部分をカバーする走
査線を有し、他方のフレームバッファコントローラは、
先端部での小さな部分しかカバーしない走査線を有す
る。基本要素は、各フレームバッファコントローラに同
時に与えられるため、システム全体に対する処理時間
は、何れかのフレームバッファコントローラのうちで、
最も長い処理時間に依存する。

【０００７】代替として、フレームバッファコントロー
ラが、異なる基本要素を処理するように割り当てられる
場合がある。しかし、基本要素は、任意の順序で処理さ
れるため、画素データを正しい位置に並べ替え、重複す
る基本要素を調整するためには、大きなＦＩＦＯメモリ
が必要である。

【０００８】変動する処理時間に鑑みて、本発明の目的
は、処理時間を向上させるために、二次元でインターリ
ーブされる、多数のフレームバッファコントローラを提
供することである。

【０００９】

【課題を解決するための手段】本発明の１つの態様にお
いて、多数のフレームバッファコントローラの各々が、
表示中の各スパンラインの一部に割り当てられる。並列
処理の効率を更に向上させるために、あるフレームバッ
ファに割り当てられた、スパンラインの部分は、スパン
ラインに依存して変化させることができる。本発明の他
の態様において、表示は、タイル、又はブロックに分割
することができる。各タイル、又はブロックは、更に小
分割されるため、各フレームバッファは、基本要素デー
タを処理して、各タイル内の各スパンラインの一部に画
素を与える。

【００１０】本発明の他の態様において、各フレームバ
ッファコントローラは、２つのメモリコントローラを含
む。本発明のこの態様によれば、フレームバッファコン
トローラは、各メモリコントローラに、画素、又は画素
のグループを交互に与える。更に、各メモリコントロー
ラは、別個のＶＲＡＭに接続される。

【００１１】本発明の他の態様において、フレームバッ
ファは、エッジステッパとスパンステッパの間に、サブ
スパンステッパを含む。サブスパンステッパは、そのフ
レームバッファに割り当てられた、スパンの部分の各々
に対して、開始値、及び停止値を決定する。サブスパン
ステッパは又、スパンの各部分に対して、開始色値を決
定する。

【００１２】本発明を更に良く理解するために、添付図
面に対して参照がなされる。

【００１３】

【発明の実施の形態】

Ｉ．システム概要図３は、並列フレームバッファコントローラを含む、本
発明のグラフィックスシステムの１つの実施例のブロッ
ク図である。図示の実施態様は、基板及びチップの数、
それらの区分方法、バスの幅、及びデータ転送速度に関
して、単なる例にすぎないことを理解されたい。多数の
他の実施態様も用いることができる。図示のように、こ
のシステムは、フロントエンドボード１１、テクスチャ
マッピングボード１２、及びフレームバッファボード１
６を含む。フロントエンドボードは、５２ビットバス１
６を介して、ホストコンピュータ１５と通信する。フロ
ントエンドボードは、バス１６を介して、ホストコンピ
ュータから描画すべき基本要素を受け取る。基本要素
は、例えばそれが三角形である場合には、頂点に対する
ような、その基本要素の部分の全てに対する、ｘ、ｙ、
ｚ頂点座標データ、Ｒ、Ｇ、Ｂ色データ、及びテクスチ
ャＳ、Ｔ座標によって指定される。

【００１４】次に、三次元で基本要素を表現するデータ
が、フロントエンドボード１１により、８５ビットバス
１８を介して、テクスチャマッピングボード１２、及び
フレームバッファボード１４に与えられる。テクスチャ
マッピングボードは、基本要素を表現することになる画
面表示画素を計算するために、受信した基本要素データ
を補間して、各基本画素に対して、対応する結果として
のテクスチャデータを決定する。その結果得られたテク
スチャデータは、図の明瞭化のため単一のバスとして、
図３に示す１１ビットバス２８を介して、フレームバッ
ファボードに与えられる。テクスチャマッピングを図３
に示すが、これは本発明には必須ではない。

【００１５】フレームバッファボード１４は又、フロン
トエンドボード１１から受け取った基本要素データを補
間して、各基本要素を表現することになる、表示画面上
の画素を計算し、また各画素に対して対象物の色値を決
定する。次に、フレームバッファボードは、画素毎に基
づいて、対象物の色値を、テクスチャマッピングボード
から与えられるテクスチャデータと組み合わせて、各画
素に対して合成画像Ｒ、Ｇ、Ｂ値を生成する。各画素に
対するＲ、Ｇ、Ｂ色制御信号が、それぞれＲ、Ｇ、Ｂラ
イン２９を介して与えられ、表示画面（図示せず）の画
素が制御されて、テクスチャマッピングされた基本要素
を表現する、表示画面上の合成画像が表示される。

【００１６】フロントエンドボード１１、テクスチャマ
ッピングボード１２、及びフレームバッファボード１４
は各々、パイプライン処理され、同時に多数の基本要素
を処理する。テクスチャマッピングボード、及びフレー
ムバッファボードが、フロントエンドボードにより以前
に与えられた、基本要素を処理する間、フロントエンド
ボードは、ボード１２、及び１４のパイプラインが満た
されるまで、新たな基本要素を処理、及び与え続ける。

【００１７】フロントエンドボード１１は、ディストリ
ビュータチップ３０、３つの三次元（３−Ｄ）幾何形状
アクセレレータチップ３２Ａ、３２Ｂ、及び３２Ｃ、二
次元（２−Ｄ）幾何形状アクセレレータチップ３４、及
びコンセントレータチップ３６を含む。ディストリビュ
ータチップ３０は、ホストコンピュータからバス１６を
介して、ｘ、ｙ、ｚ座標、及び色基本要素データを受け
取り、３−Ｄ幾何形状アクセレレータチップ３２Ａ、３
２Ｂ、及び３２Ｃ間で、３−Ｄ基本要素データを均等に
分配する。このようにして、基本要素の３つのグループ
が同時に処理されるので、システム帯域幅が増大する。
データは、４０ビットバス３８Ａを介して３−Ｄ幾何形
状アクセレレータ３２Ａ、及び３２Ｂに、また４０ビッ
トバス３８Ｂを介してチップ３２Ｃに与えられる。両方
のバス３８Ａ、及び３８Ｂは、６０ＭＨｚの速度でデー
タを転送し、２つの３−Ｄ幾何形状アクセレレータチッ
プ支援するのに、充分な帯域幅を提供する。２−Ｄ基本
要素データは、４４ビットバス４０を介して、４０ＭＨ
ｚの速度で、２−Ｄ幾何形状アクセレレータチップ３４
に与えられる。

【００１８】各３−Ｄ幾何形状アクセレレータチップ
は、受け取った基本要素を規定するｘ、ｙ、ｚ座標を、
対応する画面空間座標へと変換し、この画面空間座標に
対して、対象物のＲ、Ｇ、Ｂ値、及びテクスチャＳ、Ｔ
値を決定し、基本四角形を三角形に分解し、三角形平面
方程式を計算して、各三角形を規定する。各３−Ｄ幾何
形状アクセレレータチップは又、ビュークリッピング操
作を実行して、画面内に多数のウィンドウが表示される
場合、又は基本要素の一部が、表示画面上に表現される
ビューの量を越えて拡張する場合、結果られる画像の正
確な画面表示を保証する。３−Ｄ幾何形状アクセレレー
タチップ３２Ａ、３２Ｂ、及び３２Ｃからの出力データ
は、それぞれ４４ビットバス４２Ａ、４２Ｂ、及び４２
Ｃを介して、６０ＭＨｚの速度で、コンセントレータチ
ップ３４に与えられる。二次元幾何形状アクセレレータ
チップ３４は又、４５ＭＨｚの速度で４６ビットバス４
４を介して、コンセントレータチップ３６に出力データ
を与える。コンセントレータチップ３６は、３−Ｄ幾何
形状アクセレレータチップ３２Ａ−３２Ｃから受け取っ
た、３−Ｄ基本要素の出力データを組み合わせ、ディス
トリビュータ３０による分配の前に有していた元の順序
に、基本要素を順序付けし直し、組み合わせられた基本
要素出力データを、バス１８を介して、テクスチャマッ
ピングボード、及びフレームバッファボードに与える。

【００１９】テクスチャマッピングボード１２は、テク
スチャマッピングチップ４６、及び局部メモリ４８を含
み、局部メモリ４８は、好適には、キャッシュメモリと
して構成される。本発明の１つの好適な実施例では、こ
の局部メモリは、複数のＳＤＲＡＭ（同期式ダイナミッ
ク・ランダム・アクセス・メモリ）チップから形成され
る。局部メモリ４８は、フレームバッファボードにおい
て、描画される基本要素に関連したテクスチャＭＩＰマ
ップデータを格納する。テクスチャＭＩＰマップデータ
は、ホストコンピュータ１５のメインメモリ１７からバ
ス４０を介し、２−Ｄ幾何形状アクセレレータチップ３
４を通り、２４ビットバス２４を介してダウンロードさ
れる。

【００２０】テクスチャマッピングチップ４６は、バス
１８を介して、表示画面上に描画すべき基本要素を表現
する、基本要素データを連続的に受け取る。上述したよ
うに、３−Ｄ幾何形状アクセレレータチップ３２Ａ−３
２Ｃから与えられる基本要素は、点、線、及び三角形を
含む。テクスチャマッピングボードは、点、又は線のテ
クスチャマッピングは実行せず、三角形基本要素のみを
処理する。三角形基本要素を表現するデータは、少なく
とも１つの頂点に対するｘ、ｙ、ｚ対象物画素座標と、
この少なくとも１つの頂点の対象物色Ｒ、Ｇ、Ｂ値と、
この少なくとも１つの頂点に対応するテクスチャマップ
の部分のＳ、Ｔ座標と、この三角形の平面方程式とを含
む。テクスチャマッピングチップ４６は、対象物画素の
ｚ座標、及び対象物色Ｒ、Ｇ、Ｂ値を無視する。チップ
４６は、ｘ、ｙ座標を補間して、基本要素を表現する各
ｘ、ｙ画面表示画素に対応する、Ｓ、及びＴ座標を補間
する。各画素について、テクスチャマッピングチップ
は、キャッシュメモリから、テクスチャＭＩＰマップの
それに対応する部分にアクセスして、その画素に対する
合成テクスチャデータを計算する。このデータは、多数
のテクセルの重み付き平均を含むことができる。

【００２１】各画素に対する合成テクスチャデータは、
テクスチャマッピングチップ４６により、５つのバス２
８を介して、フレームバッファボードに与えられる。５
つのバス２８は、それぞれ、フレームバッファボードに
設けられた、５つのフレームバッファコントローラチッ
プ５０Ａ、５０Ｂ、５０Ｃ、５０Ｄ、及び５０Ｅに結合
されて、合成テクスチャデータを、並列のフレームバッ
ファコントローラチップに与える。フレームバッファコ
ントローラチップ５０Ａ−５０Ｅは、それぞれ関連した
ＶＲＡＭ（ビデオ用ランダム・アクセス・メモリ）チッ
プ５１Ａ−５１Ｅのグループに結合される。フレームバ
ッファボードは更に、４つのビデオフォーマットチップ
５２Ａ、５２Ｂ、５２Ｃ、５２Ｄ、及びＲＡＭＤＡＣ
（ランダム・アクセス・メモリ搭載デジタル／アナログ
変換器）５４を含む。フレームバッファコントローラチ
ップは、表示画面の異なる、重複しないセグメントを制
御する。各フレームバッファコントローラチップは、フ
ロントエンドボードからバス１８を介して、基本要素デ
ータを、また、テクスチャマッピングボードからバス２
８を介して、合成テクスチャマッピングデータを受け取
る。フレームバッファコントローラチップは、基本要素
データを補間して、この基本要素を表現するそれぞれの
セグメントにおいて、画面表示の画素座標を、また各画
素座標に対する対象物Ｒ、Ｇ、Ｂ色値を計算する。テク
スチャマッピングボードから、合成テクスチャデータが
与えられる、基本要素（すなわち三角形）に関して、フ
レームバッファコントローラチップが、画素毎に基づい
て、対象物色値、及び合成テクスチャデータを組み合わ
せて、表示画面上に表示すべき各画素に対して、最終的
なＲ、Ｇ、Ｂ値を生成する。

【００２２】対象物、及びテクスチャ色値の組合せの仕
方は、各種の方法で制御することができる。例えば、置
換モードでは、対象物色値が、テクスチャ色値により単
純に置換可能であるため、テクスチャ色値が、画素を描
画する際に用いられる。代替として、変調モードでは、
対象物、及びテクスチャ色値が、相互に乗算されて、そ
の画素に対する最終Ｒ、Ｇ、Ｂ色値が、生成可能とな
る。更に、対応するテクスチャ色値が、対象物色値と組
み合せられるべき仕方を規定する比率を指定する、色制
御ワードが、各テクセルに対して格納可能である。合成
色制御ワードが、各画素に対応する合成テクセルデータ
に対して決定されて、バス２８を介して、フレームバッ
ファコントローラチップに与えることが可能であるた
め、コントローラチップは、対応する合成制御ワードに
よって指定された比率を用いて、各画素に対して、最終
的なＲ、Ｇ、Ｂ値を決定することができる。

【００２３】フレームバッファコントローラチップ５０
Ａ−５０Ｅによって生成され、各画素に対するＲ、Ｇ、
Ｂ値を含む、最終画像ビデオデータが、対応するＶＲＡ
Ｍチップ５１Ａ−５１Ｅに格納される。ＶＲＡＭチップ
５１Ａ−５１Ｅの各グループは、８個のＶＲＡＭチップ
を含み、したがって、フレームバッファボード上には、
４０個のＶＲＡＭチップが配置される。ビデオフォーマ
ットチップ５２Ａ−５２Ｄの各々が、１０個のＶＲＡＭ
チップの異なる組に接続されて、そこからデータを受け
取る。このビデオデータは、ＶＲＡＭチップから直列に
シフト出力されて、それぞれ６４ビットバス５８Ａ、５
８Ｂ、５８Ｃ、及び５８Ｄを介して、２７ＭＨｚの速度
で、４個のビデオフォーマットチップ５２Ａ、５２Ｂ、
５２Ｃ、及び５２Ｄに与えられる。ビデオフォーマット
チップは、ビデオデータを、ＲＡＭＤＡＣが処理できる
ように書式化して、書式化されたデータを、３２ビット
バス６０Ａ、６０Ｂ、６０Ｃ、及び６０Ｄを介して、３
３ＭＨｚの速度で、ＲＡＭＤＡＣ５４に与える。ＲＡ
ＭＤＡＣ５４は、次に、このデジタル色データをアナ
ログＲ、Ｇ、Ｂ色制御信号に変換して、各画素に対する
Ｒ、Ｇ、Ｂ制御信号を、Ｒ、Ｇ、Ｂ制御ライン２９に沿
って、スクリーン表示装置（図示せず）に与える。

【００２４】本発明の１つの実施例では、テクスチャマ
ッピングボード１２、及びフレームバッファボード１４
上のハードウエアが、複製されているため、ある種の基
本要素の描画タスクが、多数の基本要素に関して並列に
実行され、それにより、システムの帯域幅を増大するこ
とが可能になる。本発明のかかる代替実施例の一例を図
４に示す。図４は、ある複製ハードウエアを有する、本
発明のコンピュータグラフィックスシステムのブロック
図である。図４のシステムは、４個の３−Ｄ幾何形状ア
クセレレータチップ３２Ａ、３２Ｂ、３２Ｃ、及び３２
Ｄと、キャッシュメモリ４８Ａ、及び４８Ｂとそれぞれ
関連した、２個のテクスチャマッピングチップ４６Ａ、
及び４６Ｂと、各々が、関連したグループのＶＲＡＭチ
ップを備えた、１０個のフレームバッファチップ５０Ａ
−５０Ｊとを含む。図４のシステムの動作は、上述した
図３に示すシステムの動作と同様である。図４の実施例
におけるハードウエアの複製によって、ある種の基本要
素の描画動作が、多数の基本要素に関して並列に実行で
きるので、増大したシステム帯域幅が可能になる。

【００２５】II．ラスタ化概要図５は、フレームバッファで実行される、基本要素に対
するラスタ化処理を示す。基本要素には、点、線、及び
三角形が含まれる。本発明のシステム全体によれば、基
本要素は三角形である。基本要素の情報は、３つの頂点
１０１、１０２、１０３によって与えられる。各頂点上
の情報は、ｘ、ｙ、ｚ座標値、及びＲ、Ｇ、Ｂ色値を含
む。３つの頂点に対する頂点情報を用いて、基本要素に
対して、平面方程式が決定される。この平面方程式か
ら、色の階調度、及びｚ軸の勾配が決定されて、画素デ
ータを決定する際に用いられる。ラスタ化処理におい
て、三角形のエッジ１１０、１２０、１３０（ｅ１、ｅ
２、ｅ３）が決定されて、最も長いｙの値１１０を有す
るエッジも又決定される。ラスタ化処理において、次
に、各エッジに沿った画素が決定される。各エッジに沿
った画素の決定には、さまざまな方法を用いることがで
きる。ある方法では、かかる画素の決定は、画素の各
列、又はスパンラインに対して、エッジ１１０に沿って
頂点１０１、１０３の間で補間を行ない、エッジ１１０
に最も近い画素を決定することによって行なわれる。他
の実施例によれば、画素は、常に基本要素の内側にある
ように選択される。これは、ｘ値、及びｙ値を補間し
て、各スパンラインにおける各エッジに対して、数学的
位置を決定することにより達成可能である。次に、画素
は、左のエッジに対するエッジ値より大きく、且つ右の
エッジに対するエッジ値より小さくなるように選択され
る。ある画素が、エッジの真上に位置する場合、それ
が、ある基本要素の内側と見なせるかどうかを判定する
には、特定の規則が必要である。エッジの内側の画素を
用いることによって、隣接する基本要素が処理される場
合に、上書きされる画素は何も存在しなくなる。

【００２６】１つ以上の画素列をスパンラインと呼ぶ。
エッジ画素１１１、１１２に対するＲ、Ｇ、Ｂ色値は
又、頂点１０１、１０３における値の補間により決定さ
れる。同様に、画素１２１、１２２が、同じスパンライ
ンに沿った基本要素の対向エッジ１２０に沿って決定さ
れる。次に、各スパンラインに沿って、画素に対する色
値が、各エッジに沿った点に対する色値に基づいて決定
される。

【００２７】図６は、ラスタ化処理を更に詳細に示すグ
ラフ図である。図６に示すように、画面表示の画素が、
対応する色値を有する点の格子を形成する。基本要素の
エッジ線１１０、１２０は、必ずしも格子と整合しな
い。したがって、格子の各スパンライン上の基本要素の
内側の画素が決定される。例えば、画素１０２、１１１
−１１３は、エッジ１１０に対する最初の４本のスパン
ラインに対応する。画素１０２は、基本要素を規定する
頂点１０１に最も近い画素である。

【００２８】エッジ間の各スパンライン上の画素１４１
−１４３は、エッジに最も近い各スパンライン上の画素
１１２、１１３、１２２、１２３に基づいて決定され
る。

【００２９】III.二次元でインターリーブされたフレー
ムバッファコントローラ本発明によれば、基本要素をラスタ化するためのフレー
ムバッファコントローラは、二次元にインターリーブさ
れた、画素格子の部分を割り当てられる、多数のフレー
ムバッファコントローラを含む。図７に示すように、画
面表示２００は、タイル２１０−２１３に分離されてい
る。本発明の１つの実施例によれば、各タイルは８画素
×８０画素である。スパンライン２２０、２３０、２４
０、２５０は各々、画面の幅を横切った各タイルの一部
分を包囲する。図３に示す実施例には、５個のフレーム
バッファコントローラが含まれる。したがって、タイル
内の各スパンラインは、５つの区画２２１−２２５に分
割される。各フレームバッファには、処理のために、そ
のタイル内の各スパンラインの一部分が割り当てられ
る。基本要素は、任意の位置、配向、及び寸法を有する
ことができるので、フレームバッファは、１つ以上のタ
イルの任意の部分をカバーできる。したがって、処理効
率を向上するために、フレームバッファコントローラに
は、各タイルを通して分散されたブロックを割り当てる
ことができる。コントローラ内の処理データの量は、い
くつかの基本要素にわたって均等化される。実際に、単
一の基本要素は、すべてのフレームバッファコントロー
ラを利用する可能性は低い。フレームバッファコントロ
ーラ内のＦＩＦＯメモリが、パイプライン処理に利用さ
れるため、フレームバッファコントローラ間の処理全体
は、ほぼ一定である。フレームバッファコントローラの
割り当ては、画面内の各タイルに適用可能である。図７
は、図３に示す実施例の５個のフレームバッファコント
ローラに対する割り当てを示す。

【００３０】図８は、図４に示すシステムの第２の実施
例に対応する、フレームバッファコントローラに対する
タイル割り当てを開示している。この実施例では、１０
個のフレームバッファが、並列性と速度を増大させるた
めに、用いられている。この実施例では、各タイル３０
０は、１６画素×８０画素であり、各々が２つの画素列
を有する、８本の走査線の部分をカバーする。各タイル
は、５つの行３２１−３２５に分割されている。各フレ
ームバッファコントローラには、タイルの１つおきのス
パンライン内のブロックが割り当てられるため、各フレ
ームバッファコントローラによって処理されるブロック
は、タイルを通して分散される。交互の列にブロックを
割り当てることによって、各エッジステッパの性能が向
上する。というのは、エッジステッパは、配置される割
当てブロックがない、ラインを飛び越すことができるた
めである。図８に、フレームバッファコントローラの割
り当てパターンの１つを示す。

【００３１】画面リフレッシュに対して帯域幅を増大さ
せるために、フレームバッファは、二次元にインターリ
ーブされている。スパンラインに沿って、メモリコント
ローラをインターリーブすることによって、メモリコン
トローラ当たりに必要とされる必要帯域幅は、（総帯域
幅）／（メモリコントローラの数）となる。また、大き
な多角形、大規模な充填領域、及びブロック転送の場
合、走査線に沿って画素を書き込むための性能は、スパ
ンライン上にインターリーブされた、フレームバッファ
コントローラのインターリーブに起因して改善される。
主としてｙ方向の小さな三角形、及びベクトルの処理の
性能は、フレームバッファをｙ方向にインターリーブす
ることによって改善される。

【００３２】IV．フレームバッファの構成と動作図１０は、本発明による、１つのフレームバッファコン
トローラのブロック図である。フレームバッファコント
ローラは、フレームバッファコントローラチップ５０Ａ
として構成され、エッジステッパ５００、サブスパンス
テッパ５１０、スパンステッパ５２０、及び２つのメモ
リコントローラ５３０、５３１を含む。メモリコントロ
ーラ５３０、５３１の各々は、次いで、ＶＲＡＭ５４
０、５４１に接続される。フレームバッファコントロー
ラに接続された２つのＶＲＡＭ５４０、５４１は、図３
に示すように、フレームバッファコントローラチップ用
のＶＲＡＭ５１Ａを構築する。上述したように、各Ｖ
ＲＡＭは、いくつかのＶＲＡＭチップを含む。２つのメ
モリコントローラ５３０、５３１は、処理速度を増大さ
せるために用いられる。処理を高速にするために、メモ
リコントローラに与えられるデータは、フレームバッフ
ァコントローラによってインターリーブされる。フレー
ムバッファコントローラは、スパンラインの第１の画素
線、次にその第２の画素線上で、各メモリコントローラ
の各々に、データの２つの隣接する画素を交互に供給す
る。図９に示すように、フレームバッファコントローラ
からの各データブロックは、２画素×１６画素である。
したがって、各データブロックに対して、最大で２×２
の画素サブブロックが、一度に１本の線、及び１画素ず
つ、交互にメモリコントローラに送られる。メモリコン
トローラに対する、２×２のサブブロック単位の画素の
割り当ては、ｚデータのアクセスに有利である。メモリ
コントローラは各々、ｚデータ用のキャッシュを含む。
ｚデータは、一般に２×２のブロック単位に構成されて
いる。ｚデータのあるブロックが、キャッシュへと読ま
れて、そのメモリコントローラに割り当てられた、後続
の画素とともに後で用いられる。もちろん、各メモリコ
ントローラに、画素を割り当てるために、他の手順も使
用可能である。

【００３３】エッジステッパ５００、サブスパンステッ
パ５１０、及びスパンステッパ５２０は、到来する基本
要素データを、出力画素データに変換する。上述したよ
うに、基本要素データには、三角形の３つの頂点に対す
る値、及び同じ３つの頂点に対するＲ、Ｇ、Ｂ色値が含
まれる。エッジステッパ５００は、図１に示すような慣
用的なフレームバッファのエッジステッパと同様に動作
する。補間を通して、エッジステッパ５００は、基本要
素のエッジを規定する、各画素線上の画素を決定する。
図３に示す５個のフレームバッファコントローラのシス
テムの場合、各フレームバッファコントローラは、各ス
パンラインに対してデータを処理し、対応する各エッジ
ステッパは、非並列処理フレームバッファコントローラ
（図１）のエッジステッパと同様に動作する。図４の実
施例に示すように、１０個のフレームバッファコントロ
ーラが用いられる場合、各フレームバッファコントロー
ラは、図８に示すように、交互のスパンライン上のデー
タを処理する。この場合、フレームバッファコントロー
ラのエッジステッパ５００は、図２に示すように、慣用
的な並列処理フレームバッファコントローラのエッジス
テッパと同様に動作する。各エッジステッパ５００は、
２画素の交互のスパンライン内のエッジに沿った点に対
して、画素データを与える。

【００３４】エッジステッパ５００は、サブスパンステ
ッパ５１０に、エッジ画素データを与える。エッジ画素
情報には、スパンラインのｙ値、各エッジのｘ値、第１
のエッジのＲ、Ｇ、Ｂ色値、及びスパンに対する色の階
調度が含まれる。サブスパンステッパ５１０は、スパン
ラインに沿った各タイル内のそのフレームバッファコン
トローラに割り当てられたブロックに対して、開始値、
停止値、及びジャンプ値を特定する。開始値、及び停止
値は、そのフレームバッファコントローラに割り当てら
れた、対応するブロックの基本要素内の画素値を指示す
る。図１３は、サブスパンに対する開始値と停止値の間
の関係を示す。フレームバッファコントローラに割り当
てられた、スパンラインのあるブロックが、完全に基本
要素内にある場合（ＦＢ３）、開始値、及び停止値は、
そのブロックの境界である。基本要素のエッジが、フレ
ームバッファコントローラに割り当てられた、スパンラ
インのあるブロックを通過する場合（ＦＢ２、ＦＢ
４）、開始値、又は停止値は、そのブロック内のエッジ
の位置にも関係する。ジャンプ値は、あるブロックの始
点と開始エッジの間の距離を表わし、そのブロックの開
始位置での画素に対応する色を決定するのに用いること
ができる。

【００３５】開始値、停止値、及びジャンプ値は、画素
データを生成する、スパンステッパ５２０に与えられ
る。ＦＩＦＯメモリ（図示せず）を、サブスパンステッ
パとスパンステッパの間に含めることもできる。このＦ
ＩＦＯメモリは、結果として基本要素のパイプライン処
理となり、これによって、フレームバッファコントロー
ラに対して、処理時間が均等化される。開始値、停止
値、及びジャンプ値に基づいて、スパンステッパ５２０
は、そのフレームバッファコントローラに割り当てられ
た、スパンラインのブロックの全てにおいて、画素の全
てを決定する。スパンステッパ５２０は、画素データを
メモリコントローラ５３０、５３１に、一度に１画素ず
つ出力する。

【００３６】フレームバッファコントローラの動作が、
図１１のブロックフロー図に示されている。ステップ６
０２において、基本要素データが受け取られる。この基
本要素データに基づいて、ステップ６０４で、エッジｅ
₁、ｅ₂、ｅ₃が決定される。これらのエッジは、第１
のエッジｅ₁が、最も大きいｙ範囲に及ぶ基本要素のエ
ッジになるように決定される。ステップ６０６で、エッ
ジに沿ったステッピングを行なうために、座標データ、
及び色データが決定される。この座標データ、及び色デ
ータには、エッジｅ₁の一番上の頂点（図５の１０１）
のｙ値、エッジｅ₁の一番下の頂点（図５の１０３）の
ｙ値、できるだけ一番上の頂点のｘ値、ｅ₁のｘの傾
斜、ｅ₂、又はｅ₃に対するｘ値と傾斜、できるだけ一
番上の頂点のＲ、Ｇ、Ｂ色値、ｅ₁に沿った色階調、及
び各スパンラインに対するスパン色階調が含まれる。ｅ
₁に沿ってステッピングを行なうために、エッジステッ
パは、ｅ₁のｘ値（ステップ６１２）、スパンラインに
依存した、ｅ₂、又はｅ₃のｘ値（ステップ６１６）、
スパンラインのｙ値（ステップ６０２）、及びスパン開
始色（ステップ６１６）を反復的に決定する。ｙ値は、
スパンラインを規定し、ｘ値は、そのスパンラインにお
ける基本要素の開始値、及び停止値を規定し、色値は、
そのスパンラインに対する開始色を規定する。また、ス
パン色階調が決定される（ステップ６２７）。このスパ
ン色階調は、各ブロックの始点での色、及びブロック内
の各画素に対する色の決定に用いられる。各反復におい
て、ｙ値が、その前のｙ値と比較され（ステップ６２
１）、エッジステッピングを停止するかどうかが決定さ
れる（ステップ６２２）。

【００３７】サブスパンステッパは、ｅ₁、ｅ₂、及び
ｅ₃に対するｘ値を受け取り、そのフレームバッファコ
ントローラに割り当てられた、スパンラインの各ブロッ
クに対して、開始値、停止値、及びジャンプ値を生成す
る（ステップ７００）。ジャンプ値が、スパン色階調に
より乗算され（ステップ６４０）、開始色６３３に加算
されて（ステップ６４２）、スパンラインの各ブロック
に対して、開始色値が与えられる。開始値、停止値、及
び開始色値は、スパンステッパに与えられ、スパンステ
ッパは、次に、初期の色、及びスパン色階調を用いて、
開始値と停止値の間の画素データを生成して、それらの
値と色を決定する。

【００３８】サブスパン発生器の動作が、図１２のブロ
ックフロー図に示されている。ｅ₁、ｅ₂、及びｅ₃に
対するｘ値が、ステップ７１０で比較されて、そのスパ
ン内でのステッピングの方向が決定される。スパンステ
ッパは、常にｅ₁からｅ₂、又はｅ₃に向かってステッ
ピングを行なう。ｅ₁に対するｘ値が、ｅ₂、ｅ₃に対
するｘ値より大きい場合、サブスパン開始値と停止値、
及びステッピング方向は、後方に調整される（ステップ
７１５）。ｅ₁のｘ値は、そのスパンラインにおける基
本要素に対して、スパンライン開始位置７１１に、
ｅ₂、ｅ₃のｘ値は、スパンライン停止位置７１２にな
る。

【００３９】次に、ステップ７２０で、このスパンライ
ン開始値が変調されて、そのスパンライン開始位置に対
して、タイル番号、ブロック、及びオフセットが決定さ
れる。このタイルは、スパンライン開始値が位置する、
スパンラインの列内のタイルである。ブロックは、スパ
ンライン開始値が位置する、タイル内の行２２１−２２
５である。オフセット値は、スパンライン開始値が位置
する、ブロックの１６画素内の画素位置である。実際に
は、開始位置は、デジタルの２進値である。したがっ
て、開始値の最下位４ビットは、オフセットとみなすこ
とができる。残りのビットは、４ビットだけ左にシフト
され、それにより、開始値が１６（ブロックの幅）で割
られる。次に、ＭＯＤ関数が、５のオペランド（タイル
内のブロックの数）を用いて、シフトされたビットに適
用される。このＭＯＤ関数は、演算結果と剰余を与え
る。この演算結果は、タイル番号を表わし、剰余は、ブ
ロック番号を表わす。

【００４０】フレームバッファコントローラに割り当て
られた第１のブロックに対して、サブスパン開始値を決
定するために、ステップ７２５において、このブロック
が、（図７、及び図８のパターンにしたがって設定され
た）その走査線におけるフレームバッファコントローラ
に対する、割当てブロックと比較される。開始値のブロ
ックが、この割当てブロックより小さい場合、割当てブ
ロックは、完全に基本要素内にあり（図１３のＦＢ
１）、それは、次のステップに出力される。このブロッ
クが、割当てブロックより大きい場合、割当てブロック
は、基本要素の完全に外側にあり（図１３のＦＢ１）、
タイル番号が１だけ増分される（ステップ７２６）。こ
のブロックが、割当てブロックに等しい場合、エッジ
は、割当てブロック内にあり（図１３のＦＢ２）、オフ
セット値は、次のステップに送られる（ステップ７２
４）。ステップ７５０において、第１のサブスパンの始
点が、調整されたタイル番号、割当てブロック、及びオ
フセットに基づいて決定される。８０画素の幅のタイル
と、１６画素の幅のフレームバッファ位置を有する、開
示の実施例では、開始値は次の式に等しくなる。

【００４１】タイル×８０＋ブロック×１６＋オフセット（１）このサブスパンに対する停止値は、開始値に１５（ブロ
ックの幅）を加えることによって決定される。ｅ₁が、
ｅ₂、ｅ₃より大きい場合（ステップ７１５）、停止値
は、開始値から１５を引くことによって決定される。

【００４２】同じ処理を用いて、最後のサブスパンに対
する停止値が決定される（ステップ７３０、７３４、７
３５、７３６、７５１）。スパン停止値が変調されて、
停止位置に対するタイル、ブロック、及びオフセットが
決定される。次に、このブロックが、割当てブロックと
比較されて、タイル値、及びオフセット値が、適宜調整
される。

【００４３】スパンライン内の各サブスパンは、初期の
開始値（ステップ７６０）、及び停止値（ステップ７６
５）に、８０（タイルの幅）を反復的に加えることによ
って決定される。ｅ₁が、ｅ₂、ｅ₃より大きい場合、
初期の開始値から８０が減算されて、後方のステッピン
グが行なわれる。もちろん、エッジが、割当てブロック
を通過したために、オフセット値が、初期に用いられた
場合、このオフセット値は、サブスパンを決定するため
の、後続の反復においては無視されることになる。開始
値に対して、８０を加算（あるいは減算）し、またオフ
セット値がある場合には、これを減算するのではなく、
後続のサブスパン開始値は、タイル番号を増分（あるい
は減分）し、オフセット値を０に設定して、式（１）に
従って、開始値を再計算することによって決定すること
もできる。

【００４４】スパンライン内の最後のサブスパンを判定
するために、各反復におけるサブスパンの停止値が、最
後の停止値と比較される。ジャンプ値は、サブスパンの
開始値と、基本要素に対するスパンの始点における、初
期のｘ値との間の差として決定される（ステップ７７
０）。

【００４５】図２、及び図３に示すように、本発明のグ
ラフィックスシステムは、テクスチャマッピング情報を
フレームバッファに送る。画素に対するＲ、Ｇ、Ｂ値、
及び文字値を含むテクセルデータが、テクスチャマッピ
ングボード１２から、すべてのフレームバッファコント
ローラ５０Ａ−５０Ｅに送られる。画素あたりのテクセ
ルデータが与えられるため、このテクセルデータは、エ
ッジステッパ５００、サブスパンステッパ５１０、又は
スパンステッパ５２０を通過する必要はなく、画素デー
タと組み合わされて、メモリコントローラに供給するこ
とができる。上述したように、様々な方法を用いて、基
本要素の画素データ、及びテクセルデータの組み合わせ
が可能となる。

【００４６】本明細書において図示、及び説明した回路
は、例として掲げたものにすぎない。この回路は、好適
には、例えばSynopsysから市販されている、論理合成ソ
フトウエアを用いた大規模専用集積回路で実施される。
この論理合成ソフトウエアは、Veralog 等の高水準言語
で書かれた回路記述を最適化し、これを論理ゲートに変
換する。この回路は、５ボルトで動作する１ミクロンＦ
ＥＴを生成するＣＭＯＳプロセス、３．３ボルトで動作
する０．６ミクロン延伸ゲート長素子を生成するＣＭＯ
Ｓプロセス、又はデジタル回路を実施するための、他の
任意の適当なプロセスを用いて実施することができる。
この論理合成ソフトウエアへの入力は、構造的ではな
く、機能的なものであるため、この論理合成ソフトウエ
アによって生成される実際の回路は、本明細書に開示し
たものとは異なる場合がある。

【００４７】以上、本発明の少なくとも１つの例示的な
実施例を説明したが、様々な変更、修正、及び改良は、
当業者には容易に想到されるであろう。かかる変更、修
正、及び改良は、本発明の精神、及び範囲内にあること
が意図される。したがって、以上の説明は、例示に過ぎ
ず、限定として意図されるものではない。本発明は、特
許請求の範囲に規定されるようにしか、及びその同等物
にしか限定されない。

【００４８】以下に、本発明の実施態様を列挙する。

【００４９】１．フレームバッファコントローラにおい
て、基本要素データを受け取り、一連のスパンラインデ
ータを生成する、エッジステッパと、前記一連のスパン
ラインデータを受け取り、前記一連のうちの各スパンラ
インデータに基づいて、一連のサブスパンデータを生成
する、サブスパンステッパと、前記一連のサブスパンデ
ータの各々を受け取り、前記サブスパンデータに対応す
る画素データを生成する、スパンステッパと、からなる
フレームバッファコントローラ。

【００５０】２．前記サブスパンデータは、スパンライ
ンの部分に対する開始値、停止値、及び色開始値を含
み、前記サブスパンデータによって規定される、スパン
ラインの前記部分は、前記スパンラインに基づいて変化
する、前項１に記載のフレームバッファコントローラ。

【００５１】３．前記スパンラインの前記部分は、各ス
パンラインに対して予め決定される、前項３に記載のフ
レームバッファコントローラ。

【００５２】４．画素データを格納するための少なくと
も１つのメモリと、前記スパンステッパから前記画素デ
ータを受け取り、内部に画素データを格納する、少なく
とも１つのメモリコントローラと、から更になる、前項
１に記載のフレームバッファコントローラ。

【００５３】５．コンピュータグラフィックスシステム
のためのフレームバッファシステムであって、コンピュ
ータグラフィックスシステムから、基本要素データを受
け取る、複数のフレームバッファコントローラからな
り、各フレームバッファコントローラは、基本要素のあ
るエッジのスパンラインに沿ってステッピングを行な
い、スパンラインに対応するスパンラインデータを生成
する、エッジステッパと、各スパンラインに対応するス
パンラインデータを受け取り、スパンラインデータに対
応するスパンラインの部分を表わす、一連のサブスパン
データを生成する、サブスパンステッパと、前記一連の
サブスパンデータを受け取り、前記サブスパンデータに
よって表わされる、前記スパンラインの前記部分におけ
る基本要素に対して、画素データを生成する、スパンス
テッパと、を含む、フレームバッファシステム。

【００５４】６．各フレームバッファコントローラのエ
ッジステッパは、所定のスパンラインに対応するスパン
ラインデータを生成する、前項５に記載のフレームバッ
ファシステム。

【００５５】７．前記画素データを格納するための、少
なくとも１つのメモリから更になり、各フレームバッフ
ァコントローラは、前記少なくとも１つのメモリに、画
素データを書き込むための少なくとも１つのメモリコン
トローラを含む、前項５に記載のフレームバッファシス
テム。

【００５６】８．前記少なくとも１つのメモリは、前記
複数のフレームバッファコントローラに対応する複数の
メモリからなる、前項７に記載のフレームバッファシス
テム。

【００５７】９．フレームバッファコントローラを動作
させる方法において、基本要素データを、基本要素内の
各スパンラインに対する、スパン開始値、及びスパン停
止値へと変換するステップと、前記スパン開始値とスパ
ン停止値の間の各スパンラインを、複数のサブスパン部
分に分割するステップと、各スパンラインにおいて、前
記サブスパン部分の少なくとも１つに対応する、画素デ
ータを生成するステップと、を含む方法。

【００５８】１０．前記スパンラインに基づいて、前記
複数のサブスパン部分を決定するステップを更に含む、
前項９に記載の方法。

【００５９】

【発明の効果】本発明は上述のように、各フレームバッ
ファコントローラが、到来する基本要素データを、出力
画素データに変換する、エッジステッパ、サブスパンス
テッパ、及びスパンステッパから構成され、多数のフレ
ームバッファコントローラの各々が、表示中の各スパン
ラインの一部に割り当てられて、あるフレームバッファ
に割り当てられた、スパンラインの部分は、スパンライ
ンに依存して変化可能であるので、並列処理の時間効率
を更に向上させることが可能になる、という効果があ
る。

【図面の簡単な説明】

【図１】慣用的なフレームバッファコントローラのブロ
ック図である。

【図２】慣用的な並列フレームバッファコントローラの
ブロック図である。

【図３】本発明のコンピュータグラフィックスシステム
全体の１つの実施例のブロック図である。

【図４】本発明のコンピュータグラフィックスシステム
全体の他の実施例のブロック図である。

【図５】基本要素をラスタ化する図形表現である。

【図６】基本要素をラスタ化する他の図形表現である。

【図７】インターリーブされたフレームバッファコント
ローラを示す図である。

【図８】インターリーブされたフレームバッファコント
ローラを示す他の図である。

【図９】インターリーブされたメモリコントローラを示
す図である。

【図１０】本発明によるフレームバッファコントローラ
の１つの実施例のブロック図である。

【図１１】本発明のフレームバッファコントローラの動
作のブロックフロー図である。

【図１２】本発明のサブスパンステッパの動作のブロッ
クフロー図である。

【図１３】サブスパン開始値、停止値、およびジャンプ
値を示す図である。

【符号の説明】

５０フレームバッファコントローラ５００エッジステッパ５１０サブスパンステッパ５２０スパンステッパ

Claims

【特許請求の範囲】

【請求項１】フレームバッファコントローラにおい
て、基本要素データを受け取り、一連のスパンラインデータ
を生成する、エッジステッパと、前記一連のスパンラインデータを受け取り、前記一連の
うちの各スパンラインデータに基づいて、一連のサブス
パンデータを生成する、サブスパンステッパと、前記一連のサブスパンデータの各々を受け取り、前記サ
ブスパンデータに対応する画素データを生成する、スパ
ンステッパと、からなるフレームバッファコントロー
ラ。