JPH06215143A

JPH06215143A - グラフィックス・オブジェクト表現方法と装置

Info

Publication number: JPH06215143A
Application number: JP28625793A
Authority: JP
Inventors: Chandrasekhar Narayanaswami; ナラヤナスワミチャンドラセカー
Original assignee: International Business Machines Corp
Current assignee: International Business Machines Corp
Priority date: 1992-11-30
Filing date: 1993-10-22
Publication date: 1994-08-05
Also published as: EP0600204A2; EP0600204A3

Abstract

(57)【要約】【目的】本発明は、グラフィックス・オブジェクトの表
現、特に複数のプロセッサを用いるグラフィックス表現
を行う方法と装置を提供する。【構成】本発明では、複数プロセッサを使用し、少くと
も１個のスパンを各プロセッサに割り当て、割り当てら
れるスパンはインターリーブされ、それらスパンの各々
に関するプリミティブの範囲内の終了点を上記各プロセ
ッサが計算し、そのプリミティブをディスプレイに表示
する方法とそれを実現する装置が提示される。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、グラフィックス・オブ
ジェクトの表現、特に複数のプロセッサを用いるグラフ
ィックス表現に関するものである。

【０００２】

【従来の技術】グラフィックス・オブジェクトを表現す
るために多くの既知の技法がある。典型的には、１つの
オブジェクトは多くのプリミティブ（基本体）に、通常
は三角形に、モザイク化される。各プリミティブは一組
のコーナー・ポイントによって定義される。これらの三
角形は、次に多段階プロセスにおいて個別に表現され
る。既知のGouraud陰影技法を使用して、各三角形の稜
線は、コーナー・ポイントから交差し、補間される。続
いて、三角形は、前に補間された三角形稜線ポイントか
らスパン内での画素の補間を行うため、複数の水平軸ス
パンに分割される。補間された画素は、表示のためフレ
ーム・バッファに記憶される。

【０００３】この表現プロセスは、計算集約的で、多量
の処理能力を必要とする。この結果、いくつかの技法
は、並列プロセッサを使用してオブジェクト表現を実行
するように開発された。

【０００４】Computer Graphics1989年7月号掲載の「プ
ロセッサ拡張メモリ使用の異質マルチプロセッサ・グラ
フィックス・システム（A Heterogeneous Multiprocess
or Graphics System Using Processor-Enhanced Memori
es)」は、各画素当たり１プロセッサを使用する並列走
査変換技法を記述している。同技法において各プロセッ
サは、三角形の境界稜線の各々を記述する一組の線形方
程式を評価する。稜線当たり１つの線形方程式を評価す
ることによって、三角形の各稜線について、画素が稜線
の左、右または線上にあるかどうかについてその画素を
類別する。プロセッサの画素が三角形の稜線の各々のオ
ブジェクト側にあるならば、その画素は、三角形の内部
にある。三角形の内部にある画素のプロセッサのみが有
効な計算を行うので、この荒っぽいアプローチのプロセ
ッサ活用度は十分ではない。残りのプロセッサは評価を
行うが、その画素が三角形の外側にあるので、結果は役
に立たない。この結果、表現される三角形の区域が小さ
くなればなるほど、このアプローチは、魅力が少なくな
る。

【０００５】Computer Graphics 1988年8月号掲載の
「多角形ラスター化のための並列アルゴリズム(Paralle
l Algorithm for Polygon Rasterization)」は、画素当
たりのプロセッサを使用せずにｚバッファリングおよび
カラー補間を使用する上記技法の適応を記述している。
表現される三角形の各水平軸スパン（列）について、そ
のスパンの中の画素は、各プロセッサに配分される。多
くの市販のラスター機構で行われているごとく、カラー
およびｚ値を並列的に補間するために別個の補間手段が
使われる。三角形の境界稜線を横切る線を引くことによ
って、そのスパンの終点が決定される。（５０画素以下
の）小さい三角形では、いくつかの画素は、三角形の境
界稜線のラスタ化される画素と水平軸スパンの画素との
間で共通である。（処理能力ベンチマークに一般に使わ
れる）５０画素三角形の Gouraud陰影では、これらの画
素が全体の計算時間の大きい割合を消費する。これらの
ケースにおいては、新しいスパンが並列して処理される
前に、１つのスパンのいくつかの画素が、順次処理さ
れ、並列処理と効率の度合が減少する。

【０００６】

【発明が解決しようとする課題】グラフィックスの表現
を行う従来技術においては、例えば、上記各画素当たり
１プロセッサを使用する並列走査変換技法では、三角形
内部の画素についての計算のみが有効なためプロセッサ
の有効活用という点で難があり、また、改良した上記
「多角形ラスター化のための並列アルゴリズム」におい
ても、処理すべき画素のかなりの部分が順次処理される
ため並列プロセッサならびに並列アルゴリズムを用いる
グラフィックス・システムの処理能力を減殺する。従っ
て、このような問題を解決する一層効率的なグラフィッ
クス・システム、特に並列処理能力を持つグラフィック
ス・システムが必要とされる。

【０００７】

【課題を解決するための手段】本発明は, 複数プロセ
ッサを用いて、各プロセッサに少くとも１つのスパンを
割り当てるステップを含め、複数スパンを持つプリミテ
ィブを表現する方法を与える。上記各プロセッサは、割
り当てられた各スパンのプリミティブの範囲内で終了点
を計算し、プリミティブを表示する。

【０００８】更に本発明は, 各プロセッサが少くとも
１つのスパンを割り当てられる複数プロセッサ、装置を
含め、複数スパンを持つプリミティブを表現する装置を
提供する。上記各プロセッサは、割り当てられた各スパ
ンのプリミティブの範囲内で終了点を計算する装置を含
める。

【０００９】

【実施例】図１は、本発明の好ましい実施例において利
用される典型的ディジタル・コンピュータ１００のブロ
ック図である。コンピュータは、メイン・メモリ１２
０、入力装置１３０および出力装置１４０に接続したメ
イン・プロセッサ１１０を含む。メイン・プロセッサ１
１０は、１つのプロセッサまたは複数のプロセッサを含
む。入力装置１３０は、鍵盤、マウス、タブレットまた
はその他の入力装置を含む。出力装置１４０は、テキス
ト・モニタ、プロッタまたはその他の出力装置を含む。
メイン・プロセッサは、グラフィックス・アダプタ２０
０を通してグラフィックス・ディスプレイのようなグラ
フィックス出力装置１５０を接続する。グラフィックス
・アダプタ２００は、メイン・プロセッサ１１０からの
グラフィックスに関する命令をバス１６０で受け取る。
グラフィックス・アダプタは、グラフィックス・アダプ
タ・メモリ２３０に接続のグラフィックス・アダプタ・
プロセッサ２２０を使ってそれらの命令を実行する。

【００１０】図３を参照の上以下記述のように、グラフ
ィックス・プロセッサが、複数の相互接続したプロセッ
サを含むのは、本発明の好ましい実施例である。

【００１１】グラフィックス・アダプタの中のグラフィ
ックス・プロセッサは命令を実行し、それらの命令に基
づいてフレーム・バッファ２４０およびビデオルックア
ップ・テーブル（ＬＵＴ）２４５を更新する。グラフィ
ック・プロセッサ２２０は、また、特殊タイプのプリミ
ティブを表現するため、特殊グラフィック表現専用ハー
ドウェアを含める場合もある。フレーム・バッファ２４
０には、グラフィックス出力装置上に表示されるあらゆ
る画素の指標値が記憶される。

【００１２】フレーム・バッファから読み取られる指標
値は、表示される実際のカラーに関しＬＵＴ２４５を読
み取るために使われる。ＤＡＣ（ディジタル・アナログ
変換器）２５０は、ＬＵＴに記憶されたディジタル・デ
ータをグラフィックス・ディスプレイ１５０用のＲＧＢ
信号に変換し、これにより、要求されたグラフィックス
出力がメイン・プロセッサから与えられる。

【００１３】図２は、グラフィックス機能を実行するた
めにホスト計算機およびグラフィックス・アダプタによ
って典型的に利用されるプログラムの各層を図示してい
るブロック図である。ＤＯＳのようなオペレーティング
・システム３００は、ホスト計算機の主要なコントロー
ルを提供する。そのオペレーティング・システムに連係
して、オペレーティング・システム・カーネル３１０
は、オペレーティングシステムのハードウェアに特化し
た作業を提供する。オペレーティング・システム・カー
ネルは、ホスト計算機マイクロコード３２０と直接対話
する。ホスト計算機マイクロコードは、ホスト計算機プ
ロセッサによって実行される主要命令セットである。グ
ラフィックス・アプリケーション３３０および３３２
は、オペレーティング・システム３００に連結されてい
る。このグラフィックス適用業務ソフトウェアには、Si
licon Graphic社のＧＬ、ＩＢＭ社のグラフィグス(graP
HIGS)、ＭＩＴのＰＥＸ等のソフトウェア・パッケージ
等がある。これらソフトウェアは、２次元または３次元
グラフィックスの主要機能を提供する。

【００１４】グラフィックス適用業務３３０および３３
２はグラフィックス適用業務プログラム・インターフェ
ース（ＡＰＩ）３４０および３４２とそれぞれ連係して
いる。ＡＰＩは、グラフィックス処理のため多くの計算
集約的作業を提供し、適用業務ソフトウェアとグラフィ
ックス・アダプタに対するデバイスドライバのようなグ
ラフィックス・ハードウェアに近いソフトウェアとの間
のインターフェースを提供する。例えば、ＡＰＩ３４０
および３４２はＧＡＩ（グラフィックス処理適用業務イ
ンターフェース）３５０および３５２とそれぞれ対話す
ることもある。ＧＡＩは、ＡＰＩとグラフィックス・ア
ダプタ・デバイスドライバ３７０との間のインターフェ
ースを提供する。ＡＰＩがＧＡＩの機能をも実行するグ
ラフィックス・システムもある。

【００１５】グラフィックス処理適用業務、ＡＰＩおよ
びＧＡＩは、オペレーティング・システムおよびデバイ
スドライバによって単一のプロセスとみなされる。すな
わち、グラフィックス処理適用業務３３０および３３
２、ＡＰＩ３４０および３４２、ＧＡＩ３５０および３
５２は、オペレーティング・システム３００およびデバ
イスドライバ３７０によってそれぞれプロセス３６０お
よび３６２とみなされる。オペレーティング・システム
・カーネルによってプロセスに割り当てられるプロセス
ＩＤ（ＰＩＤ）によって、プロセスは、オペレーティン
グ・システムおよびデバイスドライバによって識別され
る。プロセス３６０および３６２は、２つの別々のウィ
ンドウにおける２度のプログラム実行のように、同時に
２回実行される同じコードを使用する場合もある。ＰＩ
Ｄは、同じコードの別々の実行を識別するために使われ
る。

【００１６】デバイスドライバは、オペレーティング・
システム・カーネル３１０の拡張としてのグラフィック
ス・カーネルである。グラフィックス・カーネルは、グ
ラフィックス・アダプタ３８０のマイクロコードと直接
対話する。多くのグラフィックス・システムにおいて、
ＧＡＩか、あるいはＧＡＩ層が使用されない場合はＡＰ
Ｉかが、デバイスドライバに初期要求命令を送り出すこ
とによってＧＡＩまたはＡＰＩからアダプタ・マイクロ
コードへの直接アクセスを要求することもある。加え
て、多くのグラフィックス・システムにおいて、初期要
求命令を送り出すことによって、アダプタ・マイクロコ
ードから、ＧＡＩかまたはＧＡＩが使われていない場合
ＡＰＩかいずれかへの直接アクセスをアダプタ・マイク
ロコードが要求できることもある。両方のプロセスを、
以後、ＤＭＡ（直接メモリ・アクセス）と呼ぶ。

【００１７】ＤＭＡは、大きいブロックのデータを転送
する場合典型的に使われる。ＤＭＡを設定するためのデ
バイスドライバの初期要求以外ディスプレイ・ドライバ
通過の必要を排除することによって、ＤＭＡは、ホスト
計算機とアダプタとの間のより速いデータ転送を提供す
る。いくつかの場合には、アダプタ・マイクロコード
は、文脈切り換えを用いて、アダプタ・マイクロコード
がアダプタ・マイクロコードによって利用される現在属
性を置き換えることが可能となるようにする。適応され
たマイクロコードが使用しているものとは異なる属性を
利用するグラフィックス処理適用業務からの命令をアダ
プタ・マイクロコードが受け取らねばならない場合に、
文脈切り換えが使われる。文脈切換えは、属性変化を認
識するデバイスドライバによって始動されるのが典型的
である。

【００１８】ブロック３００ー３４０は、利用されるグ
ラフィックス・アダプタの型に依存しないソフトウェア
・コード層である。ブロック３５０ー３８０は、利用さ
れるグラフィックス・アダプタの型に依存するソフトウ
ェア・コード層である。例えば、異なるグラフィックス
・アダプタがグラフィックス処理適用業務ソフトウェア
によって使われることになっているのならば、新しいＧ
ＡＩ、グラフィックス・カーネルおよびアダプタ・マイ
クロコードが、必要となるであろう。また、ブロック３
００ー３７０は、ホスト計算機におかれ、そこで実行さ
れるが、アダプタ・マイクロコード３８０は、グラフィ
ックス・アダプタにおかれ、そこで実行される。しかし
ながら、アダプタ・マイクロコードが、グラフィックス
・アダプタの初期状態設定の間にホスト計算機によって
グラフィックス・アダプタにロードされるケースもあ
る。

【００１９】典型的グラフィックス・システムでは、ユ
ーザは、そのグラフィックス処理適用業務に対し２次元
または３次元モデルからイメージを構築するよう命令す
る。ユーザは、先ず、光源の位置およびタイプを選択す
る。ユーザは、次に、適用業務ソフトウェアに一組の定
義済みまたはユーザ定義オブジェクトから、要求された
モデルを構築するよう命令する。各オブジェクトには、
そのオブジェクトを記述しているひとつ以上の同一平面
描画プリミティブが含まれる。例えば、多くの三角形の
場合のように、オブジェクトの表面を定義するために一
組の描画プリミティブが使われるかもしれない。

【００２０】次に、ユーザはそのモデルを見るためのウ
ィンドウの配景を与え、それによって要求イメージを定
義する。適用業務ソフトウェアは、オブジェクトを記述
する描画プリミティブをＡＰＩ、ＧＡＩさらにＤＭＡが
使われていない場合デバイスドライバを通してアダプタ
・マイクロコードに送り出すことによってモデルからイ
メージを表現することを開始する。アダプタ・マイクロ
コードは、ウィンドウで見えない描画プリミティブをク
リップする（すなわち使用しない）ことによってグラフ
ィックス・ディスプレイ上のイメージを表現する。アダ
プタ・マイクロコードは、残りの描画プリミティブのそ
れぞれを、ユーザによって与えられた配景を基に、見え
る画素に分解する。

【００２１】次に、それら画素は、（３次元モデルの場
合には立体バッファをしばしば使用するが）、フレーム
・バッファにロードされる。このステップは、対象とな
る描画プリミティブ、変数および画素の数が多いため、
非常に計算集約的である。結果として生成されるフレー
ム・バッファに記憶され、グラフィックス・ディスプレ
イに表示されるイメージは、その画素がどの描画プリミ
ティブまたはオブジェクトから生成されたかなどのオリ
ジナルの情報を通常は保持しない。このため、もしもウ
ィンドウ、ユーザ配景、モデル、輝度等々が修正される
場合には、イメージは、全体又は部分的に表現しなおさ
れなければならなくなる。

【００２２】本発明の好ましい実施例では、グラフィッ
クス表現の技法は、アダプタ・フレーム・バッファの近
くに存在するアダプタ・マイクロコードのような場所で
利用される。このアプローチは、また、比較的迅速にか
つ簡単に実施できるであろう。このグラフィックス表現
技法は、また、グラフィックス処理応用ソフトウェアに
適用されることもできる。この場合、イメージが表現さ
れる前か又はその後に、グラフィックス処理応用ソフト
ウェアにデータを戻すグラフィックス・アダプタによっ
て、表現されるイメージは、システム・メモリに記憶さ
れる。このアプローチは、非常に遅いが、既存のグラフ
ィックス・アダプタへのこの技法の活用を可能ならしめ
ている。表現技法は、また、グラフィックス・アダプタ
・プロセッサのハードウェアで実施できる。このアプロ
ーチは、非常に迅速ではあるが、多分特殊のハードウェ
アを必要とする。本発明の技法がホスト計算機またはグ
ラフィックス・アダプタの範囲内で種々の場所で適用さ
れる可能性があることが、通常技術を持つ当業者によっ
て認められるであろう。

【００２３】図３は、本発明の好ましい実施例の概略フ
ローチャートである。以下のプロセスは、三角形を表現
するように記述されているとはいえ、このプロセスは、
他の多角形にも適用できる。第１のステップ４００で、
表現されるべき三角形の頂点が、ｘおよびｙ座標で最初
に分類される。この分類は、三角形がどのように別々の
スパンに分断されることになっているか（すなわち、三
角形のどの稜線が、その三角形の左側にあるのか）を決
めるのに役立つ。第２のステップ４１０では、補間され
る変数のｘおよびｙに関する偏導関数が決定される。そ
の導関数は、ｘおよびｙ方向に関する各変数の傾斜を決
定するためのものである。傾斜は、下記の補間プロセス
の中で使われる。

【００２４】ステップ４２０では、サブステップ４２０
Ａで並列制約的稜線交差技法を使用することによって、
当該三角形は、一組の水平軸スパンに効率的に分断さ
れ、サブステップ４２０Ｂで、それらスパンは補間さ
れ、サブステップ４２０Ｃで、フレーム・バッファが更
新される。このプロセスは、一般的に走査変換と呼ばれ
る。下記に示されるように、好ましい制約的稜線交差技
法によれば、各スパンについて唯一１個の共通の画素が
三角形の境界稜線のラスタ表示とスパンとの間に存在す
る。これは、稜線でよりもむしろスパンにおいて処理さ
れる画素の数を増加させる。これらスパンは、負荷がう
まく平準化するインターリーブ方式のプロセッサによっ
て処理されることが本発明の実施例として好ましい。こ
の好ましいプロセスは、下記に詳細に記述される。

【００２５】図４は、本発明の好ましい実施例によって
利用されるグラフィックス・プロセッサのブロック図で
ある。第１のプロセッサ２２２は、三角形のような多角
形を表現するためにバス１６０上の入力を受け取る。プ
ロセッサ２２２は、次に、ｘおよびｙ座標で頂点を分類
することによって、上記のステップ４００を実行し、デ
ータライン２２３上のプロセッサ２２４へこの情報を渡
す。プロセッサ２２４は、次に、補間されるべき変数の
傾斜を計算することによって、上記のステップ４１０を
実行する。

【００２６】本発明の代替的実施例では、プロセッサ２
２４は、並列して傾斜計算を実行するためにいくつかの
並列プロセッサを含むこともできる。プロセッサ２２４
は、データライン２２５Ａから２２５Ｎのプロセッサ２
２６にこの情報を渡す。代替実施例では、種々のプロセ
ッサにデータを発信し割り当てるために発信回路または
プロセッサが、プロセッサ２２４およびプロセッサ群２
２６の間に使用される場合もある。プロセッサ２２６
は、次に、稜線交差および画素補間を並列的に実行する
ことによって、上記ステップ４２０を実行する。本発明
の実施例のソフトウェア実施のためのプロセッサ２２６
の好ましいプロセッサ数は、３から５の範囲にある。し
かし、ハードウェア実施面で、コストを減らすために、
ある特定の局面でより少ないプロセッサの使用が選択さ
れる場合がある。同様に、３個の頂点からいくつかの画
素に変換を行う時発生するデータ展開のため一層多くの
プロセッサ(５から２０台)の使用を選択する場合もあ
る。また、プロセッサの各々は、代替的実施例におい
て、いくつかのパイプライン化されたまたは並列的プロ
セッサを含むかもしれない。プロセッサ２２６Ａー２２
６Ｎは、ついで、補間された画素をデータライン２４０
Ａー２４０Ｎ上のフレーム・バッファへ転送する。

【００２７】図５は、分類および傾斜計算ステップを詳
述しているフロー・チャートである。分類および傾斜計
算は、並列的に実行されることができる。ステップの間
唯一依存する点は、傾斜の正負符号が分類技法の結果に
基づいて逆にされる必要があるかもしれないことであ
る。これは、三角形の幾何図形的配列に基づいて三角形
の頂点のためのラベルを作成する。これはまた、三角形
の走査変換の結果がこの技法で頂点を指定する順序と無
関係であることを保証し、このことによって走査変換プ
ロセスが単純化される。

【００２８】図６で図示される三角形を参照しながら、
本発明の好ましい実施例をこれから説明する。このプロ
セスで、最大離隔距離ｙをもつ稜線Ｑ０Ｑ１が決定され
る。Ｑ０は、最大ｙ座標をもつ頂点である。頂点と頂点
の間の結合線は、ｘ座標に基づいて一貫した方法で分割
される。この稜線は、三角形の補間稜線として、また水
平軸スパンを作成するために、使われる。カラーおよび
ｚ値は、この稜線に沿って補間される。他の２つの稜線
は、スパンの反対側の終点を決定するために使われるだ
けである。

【００２９】このプロセスは、単一プロセッサで順次
に、または並列プロセッサによって実行されることがで
きる。並列的にこの分類を行うためには、３つのプロセ
ッサが、上記図４に述べられたプロセッサ２２２で並列
的に使われる。第１のステップ５００で、すべての３個
の頂点の座標を比較することによって、第１のプロセッ
サは、最大ｙ座標をもつ頂点を決定する。ステップ５０
０と並列に実行されるかもしれないが、第２のステップ
５１０で、すべての３個の頂点の座標を比較することに
よって、第２のプロセッサは、最小のｙ座標をもつ頂点
を決定する。ステップ５００と５１０と並列に実行され
るかもしれないが、３番目のステップ５２０で、３番目
のプロセッサは、他の2個のプロセッサによって決定さ
れた頂点と合致しない頂点を決定する。ステップ５３０
で、ベクトル（Ｑ０Ｑ１）とベクトル（Ｑ０Ｑ２）の外
積のｚ構成要素を評価することによって、Ｑ２がＱ０Ｑ
１の左側にあるか右側にあるかの決定が行われる。

【００３０】増分法を使用して三角形にわたる変数ｚ
（典型的には３次元のグラフィックス適用業務での深
さ）を線形に補間するために、ｘおよびｙに関するｚの
変化率が、ステップ５４０0および５５０で計算され
る。すなわち、ｘに対するｚの偏導関数（以下（∂ｚ／
∂ｘ）と記述する）およびｙに対するｚの偏導関数（以
下（∂ｚ／∂ｙ）と記述する）が、ステップ５５０およ
び５６０で計算される。

【００３１】かくして、ｚ(ｘ,ｙ)＝ｚ(０,０) + ［ｘ
× （∂ｚ／∂ｘ）］＋［ｙ × （∂ｚ／∂ｙ）］であ
る。ステップ５６０から６１０で、カラー要素ｒ、ｇお
よびｂに対して、同様の用語が決定される必要がある。

【００３２】Ｑ０＝(ｘ０、ｙ０、ｚ０）、Ｑ１＝(ｘ
１、ｙ１、ｚ１）、およびＱ２＝（ｘ２、ｙ２、ｚ
２）を分類プロセスの後での三角形の頂点を表わすとす
る。三角形Ｑ０Ｑ１Ｑ２が存在する平面の方程式は、Ａ
ｘ＋Ｂｙ＋Ｃｚ＋Ｄ＝０である。これは、次のように書
くことができる:

【００３３】

【数１】次に、平面に関する方向コサイン（正規化され
ない）は、以下の方程式によって与えられる: A = (z1-zO)(y1-y2) - (z1-z2)(y1-yO) B = (z1-z2)(x1-xO) - (z1-zO)(x1-x2) C = (x1-xO)(y1-y2) - (x1-x2)(y1-yO) 注：Ｄが本技法で評価される必要はない。傾斜は、次のように与えられる：（∂ｚ／∂ｘ）＝ −Ａ／Ｃ（∂ｚ／∂ｙ）＝ −Ｂ／Ｃｒ、ｇ、ｂ値のような他のパラメータに対する傾斜計算
も、同様である。注：Ｃの値はｚ、ｒ、ｇ、ｂ
の傾斜計算のためには同じである。

【００３４】十分な精度のビットが、傾斜の中で維持さ
れるので、補間に累算される誤差は問題とならない。例
えば、４Ｋ × ４Ｋのスクリーンに対し１７ビットで十
分である。Gonzalez-Liang技法とは対照的に、本発明の
好ましい実施例は、カラーおよびｚ補間のためにBresen
ham型補間を使わない。これにより、同じレベルの正確
度を維持しながら、かつ、必要なハードウェアを単純化
する。

【００３５】上述の計算を並列化するするいくつかの単
純な方法がある。１つは、ｚ、ｒ、ｇおよびｂの計算を
複数プロセッサに配分するものである。もうひとつのア
プローチは、ＡおよびＢの計算を複数プロセッサに配分
するものである。ＡとＢの計算（加算と乗算）にかかる
時間と、傾斜の計算（割り算）にかかる時間次第では、
計算のパイプライン化は、魅力的な代替方法であるかも
しれない。３から５台のプロセッサを用いれば、これら
代替的計算方法の各々について統一的負荷平準化が達成
される。

【００３６】走査変換プロセスに３つの主なステップが
ある。それらは、稜線交差、スパン補間およびフレーム
・バッファ更新である。中央が隣接三角形の稜線上に丁
度ある画素が加法（累算バッファ）または混合（混合ア
ルファ）モードで２度（三角形各々については１度）描
出される場合、望ましくない結果が起こるかもしれな
い。そのような画素を２回処理することを避けるため
に、そのような画素の所有権を隣接三角形の間で相互に
排他的とするための一貫したプロシージャが使われるこ
ともある。

【００３７】そのようなプロシージャの１つは、その画
素が三角形の左の稜線上にあるならば（稜線が左右に分
類できない場合は底辺上にあるならば）、それは描出さ
れる。効率的にするために、三角形の画素の計算を複数
プロセッサに均等に配分することが好ましい。

【００３８】Δ(最大)ｙ＝Ｑ０(ｙ)ーＱ１(ｙ)、すなわ
ちは、三角形における走査線の数と定義し、また、ｐを
プロセッサの数と定義する。１つの代替方法では、三角
形をｐ個の水平片に分断する。それら断片は、並列計算
のためプロセッサに配分される。しかし、あるプロセッ
サが他のプロセッサより長い断片を受け取ることもある
ので、このアプローチは、必ずしも負荷を均一に分配し
ない。

【００３９】各々が１画素の高さの、Δ(最大)ｙ個の断
片に三角形を分断しインターリーブ形態のｐ個のプロセ
ッサ間にそれらを配分する本発明にとって好ましいアプ
ローチが図６に示されている。（図６で、三角形は１０
の画素分の高さであり、スパンは、三角形の各スパン側
に示される５個のプロセッサの間でインターリーブされ
ている。）注：ｐ＞ Δ(最大)ｙならば、上記２つの
アプローチは同じとなる。しかし、ハードウェアのコス
トのために、しばしば、Δ(最大)ｙは、プロセッサの
数より小さい。三角形のサイズが増大するにつれて、プ
ロセッサへのスパンのインターリーブされた配分の負荷
平準化は良くなる。大きい右の三角形は、インターリー
ブ・アプローチが非常に効果的なよい例である。

【００４０】制約的稜線交差は、並列計算機構に割り付
けのため高さ１画素の断片に三角形を分断する並列技法
である。上記の制約とは、三角形の境界稜線を計算して
いる間、隣接する画素の各々は、ｙ座標軸１単位違わな
ければならないということである。そうすることによっ
て、各スパンの左右の境界稜線上の画素について、ｙ座
標は同じであることが保証され、それによって同期化さ
れた形でスパンが生成される。図７は、稜線Ｑ０Ｑ１お
よびＱ０Ｑ２に関し制約的稜線交差法によって取り扱わ
れる画素を図示する。o と x は、稜線Ｑ０Ｑ１によっ
て扱われる画素を示す。o と a は、稜線Ｑ０Ｑ２によ
って扱われる画素を示す。o は、両稜線の間で共通の画
素である。

【００４１】制約的稜線交差技法には、下記のような付
加的利益がある。典型的 BresenhamまたはＤＤＡ技法
は、三角形の外側の画素を計算する。Bresenham および
ＤＤＡ技法は、多次元プリミティブを表現することより
も線に最も適合するように意図されている。これは、計
算される画素の数を増やし、また、三角形を表現するた
めに必要でない画素を計算する。しかしながら、制約的
技法では、Ｑ１およびＱ２のみを取り扱い、三角形の外
側の画素を取り扱うことはしない。一般的には、Bresen
ham またはＤＤＡ技法は、ポイント（xO、yO）から（x
1、y1）を扱う場合、最大（ | x1−xO |、| y1−yO |
）個の画素を処理し、１画素あたりＴ時間の（ | x1−
xO |、| y1−yO | ）倍の時間を要する。従って、所要
時間は、ｘおよびｙ各々の線の投影の長さに依存する。
制約的技法は、（ | y1−yO | ）個の画素のみを処理
し、、画素当たりＴ時間の（ | y1-y01 | ）倍の時間を
要し、したがって,１よりも小さい傾斜の線に関し（ |x
1−xO| − |y1−yO| ）個という少ない画素を処理す
る。１より小さい傾斜の線に関して、その他の (|x1−x
O|−|y1−yO|）個の画素のいくつかは、スパンで処理さ
れるが、残りの画素は処理されない。

【００４２】図８は、稜線交差を記述しているフロー・
チャートである。第１のステップ７００で、スパンはイ
ンターリーブ形態のプロセッサに割り当てられる。すな
わち、Ｎ個のプロセッサに関し、各プロセッサは、他の
プロセッサに割り当てられるスパンから、Ｎ番目スパン
毎に割り当てられる。この図の残りのステップは、プロ
セッサに割り当てられるスパンに関し、各プロセッサに
よって並列的に処理される。ステップ７１０と７２０
で、スパンに対する開始点が、頂点、当該プロセッサに
よって計算された以前の開始点およびエラー条件を使用
して計算される。この開始点は、プリミティブの境界の
範囲内にあるよう制約されるのが好ましい。

【００４３】ステップ７３０で、エラー条件およびカラ
ー値は、このスパンの開始点の計算を反映して更新され
る。ステップ７４０と７５０で、頂点と、当該プロセッ
サによって計算された以前の終了点と、エラー条件とを
使用してスパンに対する終了点が、計算される。この終
了点は、また、プリミティブの境界の範囲内にあるよう
制約されるのが好ましい。ステップ７６０で、エラー条
件およびカラー値は、このスパンの終了点の計算を反映
して更新される。ステップ７７０で、このプロセッサに
関し、当該スパンが計算されるべき最後のスパンか否か
が判定される。最後でなければ、処理は次のスパンのた
めにステップ７１０に戻る。最後ならば、処理は補間と
フレーム・バッファの更新に進む。

【００４４】以下の定義が、本発明の記述の中で使われ
る。すべての算術演算および変数は、整数（固定小数
点）であることが好ましい。ｐ＝（プロセッサの数）（xO、yO）＝（線の開始点）（x1、y1）＝（線の終了点） Δx = x1 - x0 >= 0 (他のケースへの解は下記記述） Δy = y1 - y0 > 0 (他のケースへの解は下記記述）図９は、（xO、yO）と（x1、y1）を通るラスタ線を図示
する。この線の方程式は、以下のとおりである。 (y - yO)/(x - xO) = (Δy/Δx) よって x = F(y) = y X (Δx/Δy) + xO - yO X (Δx/Δy) x_j(i)およびy_j(i)は、ｊ番目の繰返しの中でｉ番目のプ
ロセッサのためのｘおよびｙ座標を示す。繰返しの開始
は、０番目の繰返しである。

【００４５】線上または線の右側にある画素を生成する
ために、以下の方程式が、好ましくは、使われる。 y_j(i) = y0 + pj +i x_j(i) = 端数切り捨て[f(y_j(i))] + 1 剰余 > 0 なら
ば = x0 + [((pj + i)Δx)/(Δy)] 線上または線の左側にある画素を生成するために、以下
の方程式が、好ましくは、使われる。 y_j(i) = y0 + pj + i x_j(i) = 端数切り捨て[f(y_j(i))] = x0 + ((pj + i)Δx)/(Δy) 画素は、その線上にまたは右側に生成される。下記のよ
うに、比較ルーチンの値が、画素が左側にあるのかまた
は線上なのか等々を示すために使われる。 b >= 0 の場合 p(Δx) = a(Δy) + b とし、 d(i) >= 0 の場合 i(Δx) = c(i)(Δy) + d(i) とす
る。従って、 ((pj + i)(Δx))/(Δy) = (pj(Δx))/(Δy) + (i(Δ x))/(Δ y) = aj + (bj)/(Δy) + c(i) + (d(i))/(Δy) = aj + c(i) + (bj)/(Δy) + (d(i))/(Δy) = aj + c(i) + (bj+d(i))/(Δy) 従って、 y_j(i) = y0 + pj +i x_j(i) = xO + aj + c(i) + (bj + d(i))/(Δy) 分数 (bj+d(i))/(Δy)を連続繰返し（ｊは変わる）計算
するために、コンピュータ・グラフィックスの順次線描
に関する標準アプローチが、利用される。この技法は、
整数および分数部として結果を維持する。その分数部
は、分子および分母を持つ。初期値として、分子は、ゼ
ロまたはそれ以下である。次の繰返しにおける結果を計
算するために、ｂは先ずその分数部の分子に加えられ
る。次いで、その分子は、ゼロと比較される。もしもそ
の分子がなおゼロに等しいかまたはそれより小であれ
ば、何も行われない。もしも分子がゼロより大であれ
ば、その整数部は、１加算され、分子から分母(Δy)が
引かれる。このように、分子は、常にゼロ未満である。
連続した繰返しの中で分数[(bj+d(i))/(Δy)]の計算
は、上記と同様であるが、この場合、その分子は、初期
的に、ゼロと分母(Δy)との間の値であり、比較は、上
述のゼロの代わりに分母(Δy)と行われる。

【００４６】e₍₀₎(i) = d(i)とする。定義により、 0 <
= e₍₀₎(i) < Δy である。０番目の繰返しの中でｉ番目
のプロセッサによって処理される画素は、次のように与
えられる。 yO(i) = yO + i xO(i) = xO + c(i) + n1 但し e₍₀₎(i) > 0 なら n1 = 1 または e₍₀₎(i) <= 0 なら n1 = 0 以下の再帰関係を、ｊ > ０のためにここで定義するこ
とができる. y_j(i) = y_(j-1)(i) + P x_j(i) = x_(j-1)(i) + a + (bj + d(i))/(Δy) - (b(j-1) + d(i))/(Δy) = x_(j-1)(i) + a + n2 但し (e_(j-1)(i) + b) > 0 なら n2 = 1 または (e_(j-1)(i) + b) <= 0 なら n2 = 0 e_j(i) = e_(j-1)(i) + b - n3 但し (e_(j-1)(i) + b) > 0 なら n3 = Δy (e_(j-1)(i) + b) <= 0 なら n3 = 0 どの線についても、各プロセッサは、（(Δy + 1) /
p）個か（(Δy + 1 +p)/ p）個かいずれかの数の画素
を処理する。いずれの２個のプロセッサによって処理さ
れる画素の数の間の差も１であるので、作業負荷は、そ
れらプロセッサ間で均一に平準化される。

【００４７】ひとたび２つのスパン開始点とそれらスパ
ンの終了点におけるカラーおよびｚの値がわかれば、当
該スパンの画素に対するカラーおよびｚの値は単純な補
間によって決定されねばならない。このフェーズを並列
化できる２つの単純な方法がある。１つのオプションで
は、垂直に連続するスパンが別々のプロセッサによって
取り扱われるというようなインターリーブ形態のプロセ
ッサにスパンを配分する（図６参照）。もうひとつのオ
プションでは、水平に連続する画素が別々のプロセッサ
によって取り扱われるというようなインターリーブ形態
のプロセッサに画素を配分する。両者いずれかの選択
は、メモリがどのように構成されているか、すなわち、
空間的に連続した画素が異なるメモリ・モジュールにあ
るのかまたはこの段階で使用可能な多くのプロセッサ上
にあるのかに、依存する。もしも利用されるプロセッサ
数が少なければ、最初のオプションが、好ましい。プロ
セッサの数が十分であれば、両方の方法を組み合わせる
か、または、第２の方法を使うこともできる。

【００４８】グラフィックス・フレーム・バッファ・メ
モリは、隣接する画素ブロックの同時アクセスを容易に
するように構成される。使用可能メモリを有効利用する
ため、本発明にとって好ましい（たとえば、８ビット・
モードでの）グラフィックス・アダプタおよび適用業務
は、ｒ，ｇ，ｂの値を同じメモリ・バンクに記憶し、ｘ
ｙ空間の隣接画素を異なるバンクに記憶する。この構成
は、ｘｙ空間の隣接画素を並列的に書き込むことを可能
にする。プロセッサの間にｘｙ空間を分割することによ
って、本発明のアプローチは、いくつかの隣接画素を１
度に生成する。従って、プロセッサによって生成される
いくつかの画素は、並列的にフレーム・バッファに書か
れる。

【００４９】表１から４は、陰影を含む三角形を表現す
るための疑似コードを示す。この疑似コードは、単一の
プロセッサによって実行されることもできるが、複数の
プロセッサによって実行されるよう意図して書かれてい
る。更に、他の多角形またはプリミティブがこれらの技
法を使用して表現されるかもしれないが、この疑似コー
ドは、三角形を表現するために書かれている。表１は、
三角形が陰影をつけられ表現される高いレベルの処理に
関するものである。特定の変数は、初期化されている。
本発明で述べられているように三角形の頂点が獲得され
分類される。種々の傾斜が、陰影のためｘおよびｙに関
して計算される。

【００５０】三角形の各稜線に対する変数が、次に計算
される。このステップは、別々のプロセッサによって実
行されることができる。疑似コードは、ΔＹよりΔＸが
より大きいと仮定する。そうでないならば、下記疑似コ
ードのために変数を入れ替えることがある。次に、各プ
ロセッサについての変数が計算される。このステップ
は、また、各プロセッサによって個別に実行されること
ができる。各スパンに対する終了点が、次に計算され
る。このステップは、複数のプロセッサによって実行さ
れることができる。最後に、スパンの範囲内の画素は、
補間され、フレーム・バッファにロードされる。

【００５１】表１三角形処理に関する疑似コード: NBR_PROCS ＝ (多角形を扱うプロセッサの数) にセット走査変換； PID ＝｛０から(NBR_PROCS-1)までの各プロセッサの識別番号｝にセット；深さおよびカラー情報を含め三角形の頂点を獲得する；Ｙの最大値およびＹの最小値をもつ頂点を決定するため頂点を分類する；ＸおよびＹに関して補間されるべき各変数の傾斜計算を行なう； for J = I to 3 initialize_triangle_edge_variables（稜線が (XO(J),YO(J)) から (X1(J),Y1(J)) の間三角形のＪ番目の稜線について）; next J; For K = 0 to NBR_PROCS - 1 setup_processor_variables（Ｋ番目のプロセッサに関し）; next K; while more spans for processor（当プロセッサのためのスパンがまだある間） LR = （1 から 3 の左側稜線の値）にセット; get_edge_of_span (X(LR), Y(LR)); LR = （1 から 3 の右側稜線の値）にセット; get_edge_of_span (X(LR), Y(LR)); 補間のためスパン用プロセッサへ左右の稜線を送出；フレーム・バッファ更新; end processing; 表２は、各三角形稜線のための変数を初期化するための
疑似コードである。各稜線について垂直および水平差
が、それらの差の方向とともに、決定される。方向は、
その線がどの方向かを記述するＣＶＡＬと呼ばれる値を
決定するため、使われる。もちろん、種々の方向の稜線
を扱うための代替的方式を利用することはできる。複数
スパンのインタリービングのため各プロセッサの前のス
パンからジャンプする場合に、変数ＡおよびＢは、スパ
ンのためのＸおよびＹ方向での軌道運動に用いられる。
以下に使われる符号関数は、、ゼロまたは正の入力に関
し、その関数に、負ー１、０または＋１を与えるもので
ある。

【００５２】表２三角形変数の初期値設定のための疑似コード: initialize_triangle_edge_variables: DELTA_X(J) = |X1(J)-XO(J)|; SIGN_DELTA_X(J) = sign (X1(J)-XO(J)); DELTA_Y(J) = |Y1(J)-YO(J)|; SIGN_DELTA_X(J) = sign (Y1(J)-YO(J)); if SIGN_DELTA_X(J) <> 0 A(J) = [NBR_PROCS*DELTA_X(J)] / DELTA_Y(J) B(J) = [NBR_PROCS*DELTA_X(J)] - [A(J)*DELTA_Y(J)]; if edge = left edge if (SIGN_DELTA_X(J) > 0) CVAL(J) = DELTA_Y(J) - 1 else CVAL(J) = 0 else if SIGN_DELTA_X(J) > 0 CVAL(J) = 0 else CVAL(J) = DELTA_Y(J) -1; return; 表３は、エラー条件および開始点を含め各プロセッサの
ための変数を初期状態にするためのものである。

【００５３】表３プロセッサ変数の設定のための疑似コード: setup_processor_variables: for L= 1 to 3; C(K,L) = (K * DELTA_X(L))/DELTA_Y(L); D(K,L) = (K * DELTA_X(L)) - (C(K,L) * DELTA_Y(L)); E(K,L) = D(K,L); X_START(K,L) = XO(L) + SIGN_DELTA_X(L) * C(K,L); if E(K,L) > CVAL(L) X_START(K,L) = X_START(K,L) + SIGN_DELTA_X(L) E(K,L) = E(K,L) - DELTA_Y(L); Y_START(K,L) = YO(L) + SIGN_DELTA_Y(L) * K; next L; return; 表４は、各スパンの稜線値を計算するためのものであ
る。

【００５４】表４プリミティブ処理のための疑似コード: get_edge_of_span: if first time for this edge（当稜線が最初ならば） X(PID,LR) = X_START(PID,LR) Y(PID,I,R) = Y_START(PID,LR) I(PID,LR) = DELTA_Y(LR); if I(PID,LR) < DELTA_Y(LR) INCR = SIGN_DFLTA_X(LR) * A(LR) E(PID,LR) = E(PID,LR) + B(LR) if (E(PID,LR) > CVAL(LR) INCR = INCR + SIGN_DELTA_X(LR) E(PID,LR) = E(PID,LR) - DELTA_Y(LR) X(PID,LR) = X(PID,LR) + INCR Y(PID,LR) = Y(PID,LR)+(SIGN_DELTA_Y(LR)*NBR_PROCS) I(PID,LR) = I(PID,LR) + NBR_PROCS < if 稜線LR = 稜線QOQ1, update color values（カラー値更新）; else LR = （当該スパンに接する新たな稜線）にセット; return; 三角形上の変数の線形補間に対する効率的並列技法を以
上記述した。初期の解決策にはなかった付加的並列法を
導入するための制約的稜線交差技法を以上記述した。

【００５５】当技法は、分子および分母が線形に補間さ
れる必要がある場合の有理数線形補間へ拡張できる。Go
uraud 陰影のみが本書の記述の中で検討されたが、本発
明の技法の結果はテクスチャ・マッピング(TEXTURE MAP
PING)やアルファ混合(ALPHABLENDING)等にも使われるこ
とができる。同様に、三角形の頂点の下位（サブ）の
画素位置決めの問題を扱うことも可能である。

【００５６】

【発明の効果】グラフィックスのプリミティブを表現す
る場合従来技術において不十分であったプロセッサ、特
に複数並列プロセッサの有効活用が本発明によって改善
され、これによりグラフィックス処理システムの処理能
力の向上が図れる。

【図面の簡単な説明】

【図１】本発明の好ましい実施例において利用される典
型的ディジタル・コンピュータのブロック図である。

【図２】グラフィックス機能を実行するためにホスト計
算機およびグラフィックス・アダプタによって典型的に
利用されるプログラムの各層を図示しているブロック図
である。

【図３】本発明の好ましい実施例の概略フローチャート
である。

【図４】本発明の好ましい実施例によって利用されるグ
ラフィックス・プロセッサのブロック図である。

【図５】分類および傾斜計算ステップを詳述しているフ
ロー・チャートである。

【図６】本発明の好ましい実施例によって表現される三
角形の図解である。

【図７】制約的稜線交差プロセスによって横切られた稜
線画素を図示する。

【図８】稜線交差を記述するフロー・チャートである。

【図９】２個のポイントを通るラスタ線を図示する。

【符号の説明】

１００ディジタル・コンピュータ１１０メイン・プロセッサ１２０メイン・メモリ２２０グラフィック・アダプタ・プロセッサ２３０グラフィック・アダプタ・メモリ２４０フレーム・バッファ２４５ＬＵＴ（ルックアップ・テーブル）２５０ＤＡＣ（ディジタル・アナログ変換器）３３０、３３２グラフィックス適用業務ソフトウエア３４０、３４２ＡＰＩ３５０、３５２ＧＡＩ３７０グラフィックス・カーネル３８０アダプタ・マイクロコード２２６並列プロセッサ

Claims

【特許請求の範囲】

【請求項１】少くとも１個のスパンを各プロセッサに割
り当てるステップと、割り当てられるスパンの各々に関するプリミティブの範
囲内の終了点を上記各プロセッサが計算するステップ
と、上記プリミティブを表示するステップと、からなる、複
数プロセッサを使用し、複数スパンを持つプリミティブ
を表現する方法。
【請求項２】上記複数プロセッサに割り当てられるスパ
ンをインターリーブするステップを含む請求項１記載の
方法。
【請求項３】複数のプロセッサと、各プロセッサに少くとも１個のスパンを割り当てる手段
と、割り当てられるスパン各々のプリミティブの範囲内の終
了点を上記各プロセッサが計算する手段と、を備え持つ、複数スパンを持つプリミティブを表現する
ための装置。
【請求項４】上記複数プロセッサに割り当てられるスパ
ンをインターリーブする手段を備え持つ請求項３記載の
装置。
【請求項５】データを処理するプロセッサと、処理されるデータを記憶するためのメモリと、グラフィックス機能を実行するためのプロセッサとメモ
リに接続され、該スパン各々のプリミティブの範囲内の
終了点を計算する手段を各々が備え持つ複数グラフィッ
クス・プロセッサと、上記グラフィックス・プロセッサ
の各々に少なくとも１個のスパンを割り当てる手段とを
備え持つアダプタと、からなる、複数スパンを持つプリミティブを表現するた
めのデータ処理装置。