JPH03212774A - 図形装置に線分を描かせる方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野コ 本発明は一般的には図形表示装置に関し、特定的には図
形表示装置に像を描かせることに関する。

［従来の技術］ 典型的な図形処理装置においては、図形（もしくはグラ
フィック）プロセッサが幾何学的及び色情報を処理して
図形表示画面上の個々の画素の発光を制御するために使
用する画素情報を作成する。

普通は図形表示画面上の各画素毎に少なくとも１つの画
素記憶素子が設けられており、その画素の発光を制御す
るのに使用する画素情報を記憶する。

例えば、第１図は典型的な従来の図形処理装置２０の例
である。装置２０は図形プロセッサ２２を含み、プロセ
ッサ２２は回線２４上の幾何学的及び色情報を受信して
図形情報を処理し、記憶装置２６へ画素情報を供給する
。記憶装置２６は記憶した画素情報をビデオディジタル
・アナログ変換器３０へ供給し、変換器３０は記憶した
画素情報をビデオ表示装置３４が使用するビデオ信号に
変換し、図形表示画面３８上に視覚像を発生させる。

図形表示装置画面３８は、ＮＸＭの画素アレイを含む二
次元格子からなり、通常は、ＮＸＭは１２８Ｄｘ　１０
２４程度である。記憶装置２６は複数の画素記憶素子（
図示せず）を含む。記憶装置２６内の各画素記憶素子は
図形表示画面３８上のそれぞれの画素に対応している。

さらに各画素記憶素子は、例えば表示画面３８上の対応
画素の発光の色を決定する色情報、又は視点からの奥行
を指示する奥行情報のような多ビットの情報を記憶する
。

以上のように、記憶装置２６の多ビツト画素記憶素子と
表示画面３８のＮＸＭの画素アレイとの間には複数対１
の対応が存在するのである。

−ｅに、線分の像を図形表示画面３８上に発生させるた
めには、描かれる線分の端点を含む表示画面３８上の画
素の（ｘ、ｙ）座標の形の幾何学的情報が、２つの端点
の色情報と共に図形プロセッサ２２へ供給される。幾何
学的及び色情報は、発光させる表示画面３８の画素に対
応する記憶装置２６の画素記憶素子内に記憶されている
画素像情報によって線分を描くように処理される。

表示画面３８の個々の画素を発光させることによって線
分を表示させる場合に屡々遭遇する問題の１つは階段効
果が現れることである。第２図は端点Ｐａ及びｐｂを有
する線分の例であり、この線分は陰影で示した画素を発
光させることによって表示される。陰影で示す画素から
線分Ｐａ　Ｐｂの階段効果が容易に理解できよう。

線分の階段効果を回避するための一方法は、実際の線分
から離れて位置している画素が線分により近い画素より
も輝かないように、線分を描くために使用する画素の明
るさを徐々に低下させることである。このようにすると
目には階段効果がないように感じられる。第３図に示す
線分は、このような漸進的なシェーディング技術を使用
したために階段効果が減少している。

階段効果を減少させる従来技術は一般的には許容される
ものではあるが、それらを使用する場合には若干の欠陥
を呈する。例えば、これらの従来技術はハードウェアに
おける高度な並列処理が容易に行えないことが多い。厖
大な数の画素に関する画素情報を迅速処理するために、
複数の画素に関する画素情報を同時に（並列に）処理し
たい場合が多い。さらに像を滑らかに動かすためには、
通常は画素を極めて高速で（典型的には毎秒１゜同程度
）周期的に更新しなければならない。並列処理はこのよ
うな高速な周期的更新に適している。

階段効果を減少させる別の方法は、画素情報を含む一組
の参照用テーブルを設けることであり、それらの情報は
画素記憶素子内へ記憶させるために取り出すことができ
るようになっている。この従来技術によれば、各画素毎
に、コンピュータソフトウェアプログラムは描（べき線
分の勾配及び線分から画素までの距離のような諸要因に
基づいて、参照用テーブルから画素情報を取り出させる
。

不幸にも多（の画素に関する画素情報を同時に処理する
べく、参照用テーブルへのアクセスと該テーブルからの
取り出しとをハードウェアで並列に実現することは困難
である。

以上のように、階段効果を呈することがなく。

且つ、高度な並列処理技術を使用して容易に実現できる
図形表示画面上に線分の像を生成する方法が待望されて
いた。

［発明の概要］ 本発明は図形表示画面上に線分の像を発生させるために
使用する画素色情報を生成する方法を提供する。本方法
はその線分を取り囲む少なくとも１つの二次元領域を表
示画面上に表示する段階を含む。この少なくとも１つの
二次元領域によって囲まれる少なくとも３つの選択され
た画素に輝度値及び色値が割り当てられる。割り当てら
れた輝度値及び割り当てられた色値に基づいて二次元領
域によって囲まれる各画素毎に最終画素色情報が補間さ
れる。

以上の如く、本方法においては図形画面の二次元領域全
体にわたって補間技術を使用することにより画面上に線
分の像を発生させることができる。

これらの補間技術は高度な並列処理及びハードウェアで
の実施に容易に適応できる。さらに、本方法は画面上の
線分の像の階段効果を最低にするために使用可能である
。

以下に添付図面に基づいて本発明の特定の実施例を説明
する。

［実施例］ 本発明は図形表示画面上に線分の像を発生させる新規な
方法に関する。以下の説明は当分針に精通した人に対し
て本発明の実現及び使用を可能ならしめるためのもので
あり、また特定の応用及びその要求に鑑みてなされるも
のである。当業者ならば本発明の思想及び範囲から逸脱
することな（以下に説明する実施例への種々の変更は容
易であろうし、またこれらの原理を他の実施例又は応用
に適用することも可能であろう。それ故、本発明は図示
実施例に限定されるものではないことを理解されたい。

第４図は本発明の処理装置４０の現在では好ましい実施
例のブロック線図である。処理装置４０は主プロセツサ
４１（破線内）及び図形装置４２（別の破線内）を含む
。主プロセツサ４１は回線５６上に幾何学的及び色情報
を供給する。図形装置４２はこの幾何学的及び色情報を
処理してディジクル画素色及び画素奥行情報を作る。ビ
デオディジタル・アナログ変換器（ＤＡＣ）４３は、図
形表示画面４８上に線分ｐ、ｐ、の像のような像を描く
ために、ディジタル画素色情報を図形表示装置４７が使
用できるアナログ情報に変換する。

本発明は、図形表示画面４８上に線分の像を発生する新
規な方法を提供する。本方法の現在では好ましい形は、
線分の各端点毎に幾何学的及び色情報（ｘｙＺＲＧＢ）
を採り、この情報を該線分が三等分する平行四辺形の頂
点を表す幾何学的及び色パラメタに変換する。次いでこ
の平行四辺形に取り囲まれる（もしくは直接その上に位
置する）３つの画素の幾何学的及び色情報を用いてこの
平行四辺形によって囲まれる画素の色及び奥行情報を補
間する。この補間された色及び奥行情報を使用して線分
の像を画面上に発生させることができる。

主プロセツサ４１は中央処理装置（ＣＰＵ）４４、浮動
小数点処理装置（ＦＰＬＪ）４６、キャッシュメモリ５
０及び主記憶装置５２を含み、これらは全て３２ビツト
のバス５４に結合されている。

主プロセツサ４１は、図形装置４２が処理できる幾何学
的及び色情報を発生する応用プログラムを走らせる。

図形装置４２はインタフェース装置５８、第１及び第２
の図形プロセッサ６０．６２及び第１及び第２の記憶装
置６４．６６を含む。インタフェース装置５８は主プロ
セツサ４１から受けた幾何学的及び色情報を用いて第１
及び第２の図形プロセッサ６０．６２が使用するパラメ
タを発生する。

図形プロセッサ６０．６２はこれらのパラメタから画素
の色及び奥行情報を発生して第１及び第２の記憶装置６
４．６６内にそれぞれ記憶させる。

主プロセツサ４１は応用プログラムを走らせることによ
って、例えば複数の異なる、そして多分型なり合った像
を表示画面４８上に発生させるための幾何学的及び色情
報を得ることができる。図形装置４２はこのような異な
る各像層の情報を個々に処理し、得られた情報を記憶装
置６４．６６内に記憶させる。

異なる各像層に、インタフェース装置５８は異なる集合
のパラメタを発生する。第１及び第２の図形プロセッサ
６０．６２はインタフェース装置５８が発生したパラメ
タを使用して、像を描くには画面４８上のどの画素をど
の色で発光させるべきかを決定する。

詳述すれば、第１及び第２の記憶装置６４．６６内に記
憶させる画素色及び奥行情報を決定するためにインタフ
ェース装置５８が発生したパラメタに応答して第１及び
第２の図形プロセッサ６０゜６２は直線補間を遂行する
。さらに、像を描くにはどの画素が必要であるかを決定
するために、図形プロセッサ６０．６２は縁探索アルゴ
リズムを使用して画面４８上に描かれる像の幾何学的“
縁”を識別する。各画素色記憶素子は２４ビツトの赤、
緑、青（ＲＧＢ）色情報を含む。これらのビットは８ビ
ツトが赤に、８ビツトが緑に、そして８ビツトが青に割
り当てられる。また各画素奥行記憶素子も２４ビツトの
奥行情報を含む。第１及び第２の図形プロセッサ６０．
６２はそれぞれ１度に５画素ずつ画素情報（色又は奥行
）を処理する。

何れも１度に１２０ビツトの情報を処理するので２つの
図形プロセッサ６０．６２は１度に１０画素（２４０ビ
ツト）ずつの色又は奥行情報を同時に処理できることに
なる。

第１及び第２の記憶装置６４．６６は複数のデュアルポ
ートランダムアクセス記憶装置（ＲＡＭ）を備えている
。図形表示画面４８上の各画素は第１及び第２の記憶装
置６４．６６の何れか一方の異なる２４ビツト画素色記
憶素子に対応している。

また、画面上の各画素は異なる２４ビツト画素奥行記憶
装置にも対応している。記憶した画素色情報に依存して
画面４８上に視覚像を描くために、記憶された画素色情
報は記憶装置６４．６６から読み出されビデオＤＡＣ４
３へ供給される。ＤＡＣ４３は像を描くために図形表示
装置が使用するアナログ信号を発生する。各デュアルポ
ートＲＡＭの一方のボートは図形プロセッサ６０．６２
の一方がアクセスするために使用し、他方のボートはビ
デオＤＡＣ４３がアクセスするために使用する。

画面４８上に描かれる像の動きが連続して、もしくは滑
らかに見えるようにするために、像を典型的には少なく
とも毎秒１０回程度更新する。像の各更新中、画面４８
上の全画素のための画素色記憶素子の内容が初期化され
る。各初期化中、第１及び第２の記憶装置６４．６６の
各画素色記憶素子及び各画素奥行記憶素子の内容が背景
色値に設定される。前述のように、図形装置４２は主プ
ロセツサから供給される幾何学的及び色情報を使用して
画面４８上のどの画素を背景色以外の色で発光させるの
かを決定し、またこれらの異なる色に対応する画素色情
報を記憶するために対応する各画素色記憶素子にアクセ
スする。

画素色記憶素子及び画素奥行記憶素子を初期化するプロ
セスを以下に説明する。第４ｂ図は第１の記憶装置６４
のブロック線図である。第１及び第２の記憶装置６４．
６６は実質的に同一であり、以下の説明は第２の記憶装
置６６にも適用されることを理解されたい。第１の記憶
装置６４は奥行バッファ（Ｚバッファ）８６、二重バッ
ファ８８、及び枠（もしくはフレーム）バッファ９０を
含み、これらは全て共用の１２０ビツトデータバス９２
に接続されている。第１の制御回線９４が行／読み出し
／書き込み制御信号を奥行、二重及び枠の各バッファ８
６．８８．９０へ供給する。第２の制御回線９６がこれ
ら３つの各バッファへ個別のチップ使用可能信号を供給
する。

表示画面４８上の各画素は奥行バッファ８６の２４ビツ
ト画素奥行記憶素子と、二重バッファ８８の２４ビツト
画素色記憶素子と、枠バッファ９０の別の２４ビツト画
素色記憶素子とに対応する。

以下に説明するように、３つのバッファの画素奥行記憶
素子及び画素色記憶素子は、論理的に１０画素（５×２
タイル素子）の中の５つに対応する５素子単位に編成さ
れている。他の５画素のタイル素子は第２の記憶装置６
６の画素奥行記憶素子及び画素色記憶素子に対応する。

第４ｃ図は２４ビツト画素色記憶素子の概念図である。

８ビツトが赤を表し、８ビツトが緑を表し、そして８ビ
ツトが青を表す。二重バッファ８８の各画素色記憶素子
にｌ対ｌで対応する画素色記憶素子が枠バッファ９０内
にも存在している。

第４ｄ図は２４ビツト画素奥行記憶素子の概念図である
。２４ビツトの全てを奥行を表すために使用することが
できる。

表示画面上に像を発生させるために、記憶した画素色情
報を枠バッファ９０から読み出してビデオＤＡＣ４３に
供給する。ＤＡＣ４３はこれらのディジタル値を、画面
４８上に像を描くために図形表示装置４７が使用するア
ナログ信号値に変換する。

滑らかに動く像を創るためには、少なくとも毎秒１０回
程度枠バッファ９０内の画素色情報を更新してＤＡＣ４
３に供給すべきである。枠バッファ９０の内容を更新す
るプロセスは、先ず二重バッファ８８の内容を更新し、
次いで二重バッファ８８の内容を枠バッファ９０内に複
写することを含む。変形実施例（図示せず）においては
、例えば、二重バッファの内容を更新した後に二重バッ
ファの内容を枠バッファ内に複写する代わりに、二重バ
ッファ及び枠バッファからの出力をこれら２つのバッフ
ァの役割を逆転させるように多重化（又はスイッチ）す
ることができる。この場合、２つのバッファの中で最も
新しく更新されたバッファをＤＡＣに直接接続して画素
情報を供給する。

他方のバッファは二重バッファとして働かせ、新しい画
素色情報で更新する。

二重バッファ８８の更新は、奥行バッファ８６及び二重
バッファ８８を同時に初期化することを含む。この初期
化は奥行バッファ８６の全画素奥行記憶素子に単一の２
４ビツト画素奥行値を書き込むことと、二重バッファ８
８の全画素色記憶素子に単一の２４ビツト画素色値を書
き込むこととを含む。本発明によれば、初期化中に奥行
バッファ８６及び二重バッファ８８の両方の全画素色記
憶素子に同じ２４ビツト値を書き込む。即ちこの同じ２
４ビツト値は、主プロセツサ４１上を走る応用プログラ
ムによって指定される背景色を表す２４ビツト値である
。

第１の図形プロセッサ６０は、奥行バッファ８６及び二
重バッファ８８に共用１２０ビツトバス９２からの情報
を書き込むように命令する読み出し／書き込み制御信号
を第１の制御回線９４へ供給することによってこの同時
初期化を制御する。

これらの書き込み信号を供給する途中で第１の図形プロ
セッサ６０は、奥行バッファ８６及び二重バッファ８８
の両方に第１の図形プロセッサ６０から共用バス９２へ
供給されるディジタル情報を同時に書き込ませるチップ
使用可能信号を第２の制御回線９６へ供給する。図形プ
ロセッサ６０は。

画素奥行記憶素子及び画素色記憶素子の全部に同じ画素
値をロードすることによってそれらを全て初期化するま
で、１度に５画素ずつ、２４ビット画素（背景）色値を
１２０ビツト共用バスへ供給する。

好ましい実施例における枠バッファ９０の更新プロセス
は、隠れ面消去技術の適用をも含む。これらの技術によ
れば、ある画面の中で複数の像が互いに重なり合ってい
る場合に、これらの像の中でより近い像だけを画面に表
示させることができる。より近い像を描かせるには、こ
れらの重なり合う像の中のより近い像の画素に関する画
素色情報を二重バッファ内に記憶させる必要がある。

隠れ面消去技術の実現には奥行バッファ８６の使用が含
まれる。第１の図形プロセッサ６０は、画面４８上に像
を表示するために包含される画素のために補間された画
素奥行と補間された画素色情報とを計算する。各画素毎
に第１の図形プロセッサ６０は、奥行バッファ８６の対
応画素奥行素子から現在記憶されている奥行値を読み出
す。第１の図形プロセッサ６０はその画素に関して現在
記憶されている奥行値とその画素のために計算された（
補間された）奥行値とを比較する。もし計算された奥行
値の方が現在記憶されている奥行値より“も近ければ、
第１の図形プロセロ０は新たに計算された奥行値を当該
画素に対応する奥行記憶素子内に書き込み、またその画
素のために新たに計算された色値な当該画素に対応する
色記憶素子内に書き込む。そうでない場合には、当該画
素に関して現在記憶されている奥行値及び色値な変化さ
せずにそのままとする。

隠れ面消去技術の適用の途中で、主プロセツサ４１上を
走る応用プログラムから与えられる０≦Ｚ≦１の範囲内
の浮動小数点奥行値が２４ビット２値奥行値に変換され
る。この変換は、奥行バッファ８６内に現在記憶されて
いる２４ビツト値との比較のために、計算された（補間
された）奥行値を計算する際に上記与えられる奥行値を
容易に使用できるように遂行されるのである。さらに、
奥行バッファの各画素記憶素子は背景色に対応する２４
ビット奥行値を用いて初期化されるので、応用プログラ
ムから与えられる変換された奥行値を位取りしてこの初
期化を補償する必要がある。

好ましい実施例では、この位取りは以下のようにして遂
行される。２値背景色値を浮動小数点値に変換する。２
２３より小さい２値背景色値の場合には変換される奥行
値を 奥行＝（背景色値１＋（（２”−１１−背景色値）＊Ｚ
とし、２２３より大きい２値背景色値の場合には変換さ
れる２値奥行値を 奥行＝背景色値＊Ｚ とする。

このような位取りをすると、隠れ面消去技術を適用する
時により広範に位取りされた奥行値を使用できる。

第１の図形プロセッサ６０が、ある画面内の複数の像に
関する画素奥行及び画素色情報を表現できることが理解
されよう。像が重なり合う場合には、上に述べた隠れ面
消去技術を使用すればより遠い像（又は像のより遠い部
分）はより近い像の背後に隠されてしまう。

次に実施例に基づいて、画面４８上に線分の像を発生さ
せる時のデータ処理装置４０の動作を説明する。この例
は、第５ａ図に示す線分Ｐ　１Ｐ　２の像を発生させる
ために画素を発光させる段階を中心としている。

図形プロセッサ６０．６２は、 Ｑ　＝−ａ／ｂ　ｘ　−ｂ／ｃ　ｙ　＋ａ／ｃ　ｘ＋＋
ｂ／ｃ　ｙ＋＋　Ｑ　＋なる形の二次元方程式を使用し
て直線補間を遂行することによって、記憶装置６４．６
６が記憶する画素色値、画素奥行値、及び画素輝度値を
発生する。但し Ｑ＋　＝Ａｘ＋　＋Ｂｙ＋　＋ｃ Ｑ２　＝Ａｘ２＋Ｂ３’ｚ　＋ｃ Ｑｓ　”ＡＸｓ　＋Ｂｙｉ　＋ｃ であり、Ｑは色補間に関しては赤、緑、又は前値を表し
、奥行補間に関してはＺ値を表し、輝度補間に関しては
α値を表す。

この実施例では直線補間を用いているが、画素色及び奥
行情報を計算する上で二次補間法のような別の方法を用
いることもできる。

主プロセツサ４１’は、線分ｐ、ｐ２の端点に関する幾
何学的及び色情報Ｐ　＋（Ｘ＋Ｖ＋Ｒ＋ＧＪ＋２＋）及
びＰ　ｚ（Ｘ２Ｖ２Ｒ２ＧＪｚＺｚｌをインタフェース
装置５８に供給する。座標対（ｘｚｙ＋１及び（Ｘ２１
ｙ２　）は、図形画面４８の画素アレイ内の端点ＰＩ及
びＰ２を含む画素の位置を示す。色情報（ＲＩＧＩＢ＋
）　、及び（Ｒ２ＧＪ２）はそれぞれ端点Ｐｌ及びＰ２
の色な提供する。最後に、奥行情報２．及びｚ２は端点
の奥行（観察者からの距離）を与える。奥行情報は、例
えば、画面４８上の若干の像が画面上の他の像にかぶさ
る場合には、隠れ面消去に使用される。

このように重なっている場合には、“より近い”奥行値
を有する面が表示され、“より遠い”奥行値を有する面
は隠される。

幾何学的及び色情報に応答して、インタフェース装置５
８は、平行四辺形の座標、輝度値（α）位取り、直線補
間を遂行するのに使用される選択された開始値、及び直
線補間を遂行するのに使用される定数値のようなパラメ
タを発生する。第５ｂ図の平行四辺形（Ｐ、Ｐ４ＰｓＰ
８）は線分Ｐ、Ｐ２によって三等分され、またその平行
対辺は線分の端点Ｐ、及びＰ２を含む画素を取り囲んで
いる。この平行四辺形が表示画面４８の二次元領域を表
示していることは明白であろう。

インタフェース装置５８は輝度位取り係数αを発生する
。係数αは、線分ｐ、ｐ、から離れて垂直に変位してい
る画素が低輝度で発光するように、線分を描くために使
用する画素の発光輝度を漸進的に位取りするのに用いら
れる。即ち、表１及び第５Ｃ図に示すように平行四辺形
の左辺の輝度値はＰ３におけるα＝０．０から、Ｐ、に
おけるα＝１．０を経てＰ、におけるα＝２．０まで変
化している。同様に、平行四辺形の右辺の輝度値はＰ４
のα＝０．０からＰ２のα＝１．０を経てＰ６のα＝２
．０まで変化している。後述するように１．０乃至２．
０の範囲のαの値は、線分からの垂直距離と共に徐々に
減少するα輝度値が得られるように補間計算の途中で１
．０乃至０．０の範囲に方図される。

次の表１は第５ｃ図の平行四辺形の辺上の点に割り当て
られるα値を示す。

　３　Ｐ４ Ｐ　７　Ｐ　ｓ Ｐ、Ｐ Ｐ、、　　　Ｐ Ｐｌ、Ｐ２ ０．０ ０．２５ ０．５０ ０．７５ １．００ Ｐ、、　　　Ｐ、４　　　　　　　　　１．２５Ｐ　＋
ｓ、　　Ｐ　ＩＢｌ、５０ Ｐｌ７　　　Ｐｅａ　　　　　　　　　　　１．７５Ｐ
、Ｐ、　　　　　　　　　　　　　２．００インタフエ
ース装置５８は平行四辺形によって囲まれる（及びその
辺上にある）３つの点も選択し、平行四辺形によって囲
まれる画素の色、奥行、及び輝度情報（ＲＧＢＺα）の
補間に使用する。例えば装置５８は点ｐ、、ｐ４．及び
Ｐ、を選択できる。次いでこれらの３つの選択した点の
（ＲＧＢＺα）値を使用してインタフェース装置５８は
−ａ／ｃ　＝　ｄＱ／ｄｘ　、　　−ｂ／ｃ　＝　ｄＱ
／ｄｙを計算する。ＱはＲＧＢ、Ｚ又はαを表すことが
できる。従ってインタフェース装置５８は、ｄＲ／ｄｘ
、　ｄＲ／ｄｙ、　ｄＧ／ｄｘ、　ｄＧ／ｄｙ、　ｄＢ
／ｄｘ、　ｄＢ／ｄｙ。

ｄＺ／ｄｘ、　ｄＺ／ｄｙ、　　ｄａ　／ｄｘ及びｄａ
／ｄｙを計算する。好ましい実施例においてはａ　＝　
（ｙ４−ｙａｌ　（Ｑｓ−Ｑ４１−　（ｙｓ−ｙ４）　
（Ｑ４−０３１ｂ　＝　（ｑ４−ａｍ）　（ｘｓ−ｘ４
１−　（ａｓ−ａ４）　（ｘ４−ｘａｌＣ−（Ｘ４−Ｘ
ｌｌ　（ｙａ−ｙ４に−（ｘｌｌ−ｘ４）（ｙ４−ｙａ
）である。但し、選択した点Ｐ、、ｐ４及びＰ、ｃｔ（
ｘ、ｙ　）座標は、（ｘｓ＋ｙｓ）、（ｘ４．ｙ４）及
び（Ｘｓ、ｙｓである。

インタフェース装置５８が平行四辺形の座標壱発生し、
α値を割り当て、平行四辺形内に含まする３つの点を選
択し、そして上記定数値を計算した後、第１及び第２の
図形プロセッサ６ｏ、６２はこの情報を使用して、線分
ＰＩ　Ｐａの像を表がするためにはどの画素色記憶素子
を新画素色悄幸モで更新するのかを決定し、また更新さ
れた画素き及び奥行情報を補間する。

詳述すれば、第１及び第２の図形プロセッサ６０．６２
は縁探索アルゴリズムを使用して、どの画素を更新する
のかを決定する。好ましい実施＋ｌ１Ｉｊでは“タイル
”素子を用いた縁探索アルゴリズムを使用している。“
タイル”素子は、５Ｘ２画素アレイの画面上に配列され
た１組１０個の物理的に隣接する２４ビツトの画素であ
る。第６図は、°゛１”乃至“１０°゛の番号を付した
１０画素からなる５×２タイル素子を示す。

画面４８は複数のタイル素子に分割される。対応して記
憶装置６４．６６は、各タイル素子毎に、色情報を記憶
するための論理的に隣接する１０画素記憶素子が存在し
、また奥行情報を記憶するための論理的に隣接する１０
画素記憶素子が存在するように編成されてい゛る。

要約すれば、縁探索アルゴリズムは以下のように動作す
る。開始タイル素子が選択される。第７図では、このタ
イル素子を“１″で示しである。

好ましい実施例においては、この開始タイル素子は当該
幾何学的図形（この例では三角形Ｔ、　　Ｔ。

Ｔ３）の最上頂点を含むタイル素子である。アルゴリズ
ムは先ず開始タイル素子“１”の左側の何れかのタイル
素子を縁が走っているかどうかを探索する。この例では
そのようなタイル素子はない。

次に、アルゴリズムは開始タイル素子の右側の何れかの
タイル素子を縁が走っているかどうかを探索する。アル
ゴリズムは“２″番のタイル素子に縁が走っていること
を決定する。次いでアルゴリズムは“１”番の開始タイ
ル素子の直下の°゛２”番のタイル素子の座標へ移動す
る。アルゴリズムは゛３°゛番タイル素子の座標から左
側を、次いで右側を再び検索する。アルゴリズムは３″
番から“β”番までのタイル素子が全部又は一部を三角
形Ｔ、、Ｔ２．Ｔ、の縁によって囲まれていることを見
出す。アルゴリズムは三角形の底辺がタイル素子“３”
を通っていないことを決定する。

そこで“７″゛番タイル素子の座標に移ってその左側、
次いで右側を探索し、タイル素子“８””　７　”及び
“９”乃至“１４”が全部又は一部を囲まれていること
を識別する。このようにしてアルゴリズムは、最後の２
つのタイル素子が全部又は一部を囲まれていることを識
別するまで進行する。この例では、最後の２つのタイル
素子はそれぞれ“５２”及び“５３”である。上側では
縁探索アルゴリズムを三角形Ｔ　１、Ｔ２　、　Ｔｓに
適用しているが、第５ａ図〜第５ｄ図の平行四辺形にも
全（容易に適用できることは明白である。また好ましい
実施例では縁探索アルゴリズムを使用しているが、平行
四辺形によって囲まれている画素又はタイル素子を識別
するためには、より伝統的な他の方法も使用できること
を理解されたい。

第１及び第２の図形プロセッサ６ｏ、６２は、当該幾何
学的図形によって全部又は一部が囲まれていることを見
出されたタイル素子の画素に関する色、奥行、及び輝度
値を補間する。例えば第５ｄ図に示す“ｌ”乃至“１０
”番の５Ｘ２画素アレイからなるタイル素子は、縁探索
アルゴリズムの適用によって平行四辺形Ｐ、Ｐ２Ｐ、Ｐ
４によって（部分的に）囲まれていることが見出される
。

画素“ｌ”乃至“４”及び“６”乃至“９”は平行四辺
形に囲まれている。画素“５”及び“１０”は平行四辺
形の外側に位置している。このタイル素子は（部分的に
）平行四辺形に囲まれているから、タイル素子内の各画
素毎に前記二次元方程式を使用してそれぞれの画素のた
めの色（ＲＧＢ）奥行（Ｚ）及び輝度（α）値を補間す
る。

タイル素子内の各画素毎の最終的な赤、緑、及び青の色
値は、それぞれの補間された赤、緑、及び青の色値から
以下のようにして計算される。

色（最終）二色（補間済）＊α（補間済）輝度値（α）
は線分からの垂直距離と共に減少するから、線分から垂
直に離れて位置する画素は徐々にフェードアウトし、階
段効果を減少させる。

前述したように、■、０〈α≦２．０の範囲内にあるα
（１！ｉ度）値は、色（最終）を計算するために前記方
程式を適用する前に１．０〉α≧０．０の範囲に回国し
なければならない。本実施例では、第８図に概要を示す
下位けたあふれ／あふれ（Ｕｌｏ）訂正回路６８を使用
してこの回国な遂行する。

Ｕ１０回路６８は、９ビツト加算器７０の形状の計算装
置、９個の排他的ＯＲゲート７２の形状の反転回路、及
びＡＮＤゲート７４の形状の制御装置を含む。９ビツト
加算器７０は、９個の１ビット加算器７０−０乃至７０
−８からなり、これらはけた上げチェーンの形に結合さ
れている。９ビツト加算器７０の各１ビット加算器７０
−０乃至７０−８の出力は、それぞれ排他的ＯＲゲート
７２−〇乃至７２−８の第１の入力に接続されている。

ＡＮＤゲート７４の出カフ３は排他的ＯＲゲート７２−
０乃至７２−８の第２の入力に接続されている。ＡＮＤ
ゲート７４の第１の入力８０はけた上げチェーン内の最
高位にある９番目の１ビット加算器７０−８の出力に接
続されている。ＡＮＤゲート７４の第２の入力８０は制
御信号を受ける。

Ｕ１０回路６８は、次の輝度値α。を補間することがで
き、また補間された輝度値を１．０＜α≦２．０の範囲
から１．０〉α≧０．０の範囲に回国することができる
。詳述すれば、９ビツト加算器７０の°Ａ”入力は、９
ビツトの予め補間された輝度値α３．（αい。〜α、８
）を受ける。９ビツト加算器７０の“Ｂ”入力は、例え
ば９ビツトのｄα＋／ｄｘ（ｄａ　ｏ／ｄｘ−ｄａ　ｓ
／ｄｘ）からなる定数値ｄａ／ｄｘを受ける。最低位の
予め補間された輝度値ビットαｐｏ　　及び定数ビット
ｄα。／ｄｘは１ビット加算器７０−０に供給される。

最高位の予め補間された輝度値ビットαｐ８及び定数ビ
ットｄαａ／ｄｘは１ビット加算器７０−８に供給され
る。以下の説明はｄα／ｄｙの計算にも適用できる。

Ｕ１０回路６８は９ビツトαｎ＋（α。。乃至αｒ＋８
）からなる９ビツトの次の輝度値を補間する。次の輝度
値α。の実数値が０．０≦α。≦１．０の範囲内にある
限り、次の最高位輝度ビットαｎ８の値は論理“０”で
ある。もし最高位輝度値α。の実数値が１，０〈α。≦
２．０の範囲内にあれば、次の最高位輝度ビットα。８
の値は論理“１”である。

ＡＮＤゲート７４の第２の入力８２へ論理″１”を供給
することによってＡＮＤゲート７４は、最高位輝度ビッ
トαｎ８が論理“ｌ”である場合だけ論理”１”信号を
回線７３上に出力する。回線７３上の論理“１”信号に
よって排他的ＯＲゲート７２−０乃至７２−７は、それ
ぞれ１ビット加算器７０−０乃至７０−７から供給され
るビットを反転する。この反転は、表２に示すように１
．０〈α。≦２．０の範囲内の輝度値を０．０≦α。≦
１．０の範囲に回国するために使用することができる。

聚−１ α割り当て済　α割り当て済　回国されるα割り当−１
１土ｌ羞　−ユし皇１−−二ｌｉ至ｌ−ｏ、ｏ　　　　
　　　　　　　ｏｘｏ。

０．２５　　　　　　　　　０Ｘ４０ ０．５０　　　　　　　　　０Ｘ８０ １．０　　　　　０ＸＦＦ １、５　　　　　０Ｘ１８０　　　　　０Ｘ７Ｆ１、７
５　　　　　０ＸＩＣＯ０Ｘ３Ｆ２、０　　　　　０Ｘ
ＩＦＦ　　　　　　ＯＸＯ第５ｃ図、表１及び表２から
、Ｕ１０回路６８を使用すれば次の輝度値を１．０＜α
。≦２．０の範囲から０．０≦α。≦１．０の範囲へ１
６進数の形で回国できることが解る。さらにＵ１０回路
６８は、次に補間される画素の輝度値α。を線分からの
画素の垂直距離の増加と共に減少させるように、この回
国を遂行することも解る。またこのような減少は、線分
Ｐ　１Ｐ　２の下方に横たわる画素とほぼ同じ割合で、
上方に横たわる画素にも発生する。

第９図は、水平の対向辺に沿う点に輝度値（α）が割り
当てられている平行四辺形を示す。第９図の平行四辺形
のための輝度値位取りを表３に示す。

Ｐ、ＰＯｏＰＰ、ＰＱ　　　　　　　Ｏ，ＯＰ、Ｐ、、
ＰＴ、ＰＵ　　　　　　Ｏ，５ＰＬ　Ｐ、、　　　　　
　　　　　　　　１．０第９図の平行四辺形の場合には
、図形装置４２は、線分ｐＬｐ、によって三等分されて
いる２つの平行四辺影領域Ｐ、Ｐｃ、ＰＬＰＭ及びＰＬ
ＰＭＰＰＰＱにおける色、奥行及び輝度の補間を遂行す
る。輝度値（α）は既に適切に位取りされているから、
輝度値の方図のためにはＵ１０回路６８は使用されない
。

以上、本発明の７実施例を説明したが、この好ましい実
施例には本発明の範囲から逸脱することなく種々の変更
を施し得ることは明白である。従って以上の説明は本発
明を限定するものではないことを理解されたい。

【図面の簡単な説明】

第１図は従来の典型的な処理装置のブロック線図であり
、 第２図は第１図の処理装置の図形画面上の線分の例であ
って階段効果を示し、 第３図は第２図の線分の階段効果が減少している様を示
し、 第４ａ図は本発明の好ましい実施例による処理装置のブ
ロック線図であり、 第４ｂ図は第４ａ図の装置の第１の記憶装置の詳細を示
すブロック線図であり、 第４ｃ図は第４ｂ図の第１の記憶装置の枠バッファ（又
は二重バッファ）の画素色素子の概念図であり、 第４ｄ図は第４ｂ図の第１の記憶装置の奥行バッファの
画素奥行素子の概念図であり、第５ａ図は第４ａ図の好
ましい実施例の図形画面上の線分の例であり、 第５ｂ図は第４ａ図の装置のインタフェース装置によっ
て発生される平行四辺形を示し、第５ｃ図は第５ｂ図の
平行四辺形の対向する垂直縁に沿って異なる輝度が割り
当てられる個々の画素を示し、 第５ｄ図は第５ｂ図の平行四辺形及びタイル素子を示し
、 第６図は第４ａ図の装置の表示画面のタイル素子を示し
。 第７図は幾何学的図形によって取り囲まれている画素を
識別するための縁探索アルゴリズムの適用を説明する図
であり、 第８図は第４ａ図の図形処理装置の下位けたあふれ／あ
ふれ訂正回路の回路図であり、第９図は輝度値が対向す
る水平縁に沿って割り当てられる変形平行四辺形を示す
。 ２０．４０・・図形処理装置、 ２２．４１・・図形プロセッサ、 ２６・・記憶装置、 ３０．４３・・ビデオディジタル・アナログ変換器。 ３４．４７・・図形表示装置、 ３８． ４２　・ ４４　・ ４６　・ ５０　・ ５２　・ ５８　・ ６０． ６４． ６８　・ ７０　・ ７２　・ ７４　・ ８６　・ ８８　・ ９０　・ ９２　・ ９４． ４８・・図形表示画面、 ・図形装置、 ・中央処理装置（ＣＰＵ） ・浮動小数点処理装置（ＦＰＵ） ・キャッシュメモリ、 ・主記憶装置、 ・インタフェース装置、 ６２・・図形プロセッサ、 ６６・・記憶装置、 ・下位けたあふれ／あふれ訂正回路、 ・加算器、 ・排他的ＯＲゲート、 ・ＡＮＤゲート、 ・奥行バッファ、 二重バッファ、 ・枠バッファ、 ・共用データバス、 ９６・・制御回線。

Claims (3)

【特許請求の範囲】
1. （１）図形表示装置画面上に線分の像を発生させるため
   に使用する画素色情報を生成する方法であって、 その線分を取り囲む少なくとも１つの二次元領域を表示
   画面上に表示させ、 この少なくとも１つの二次元領域によって囲まれる少な
   くとも３つの選択された画素にそれぞれの輝度値を割り
   当て、 これらの少なくとも３つの選択された画素にそれぞれの
   色値を割り当て、 それぞれの割り当てられた輝度値及びそれぞれの割り当
   てられた色値に基づいて前記少なくとも１つの二次元領
   域によって囲まれる各画素毎にそれぞれの最終色値を補
   間する 諸段階を具備する方法。
2. （２）図形表示装置の画面上に線分の像を発生させるた
   めに使用する画素色情報を生成する方法であって、 その線分を取り囲む少なくとも１つの二次元領域を表示
   画面上に表示させ、 この少なくとも１つの二次元領域によって囲まれる少な
   くとも３つの選択された画素にそれぞれの輝度値を割り
   当て、 これらの少なくとも３つの選択された画素にそれぞれの
   色値を割り当て、 割り当てられた輝度値に基づいて前記少なくとも１つの
   二次元領域によって囲まれる各画素毎にそれぞれの輝度
   値を補間し、 少なくとも１つの色値に基づいて前記少なくとも１つの
   二次元領域よってに囲まれる各画素毎にそれぞれの色値
   を補間し、 それぞれの補間された輝度値及びそれぞれの補間された
   色値に基づいて前記少なくとも１つの二次元領域によっ
   て囲まれる各画素毎にそれぞれの最終色値を計算する 諸段階を具備する方法。
3. （３）図形表示装置の画面上に線分の像を発生させるた
   めに使用する画素色情報を生成する方法であって、 その線分を取り囲む少なくとも１つの平行四辺形の形の
   二次元領域を表示画面上に表示させ、この少なくとも１
   つの二次元領域によって囲まれる少なくとも３つの選択
   された画素にそれぞれの輝度値を割り当て、 これらの少なくとも３つの選択された画素にそれぞれの
   色値を割り当て、 縁探索アルゴリズムを使用して実質的に前記少なくとも
   １つの二次元領域によって囲まれる画素を識別し、 割り当てられた輝度値に基づいて前記少なくとも１つの
   二次元領域によって囲まれる各画素毎にそれぞれの輝度
   値を直線補間し、 割り当てられた色値に基づいて前記少なくとも１つの二
   次元領域によって囲まれる各画素毎にそれぞれの色値を
   直線補間し、 それぞれの補間された輝度値及びそれぞれの補間された
   色値に基づいて前記少なくとも１つの二次元領域によっ
   て囲まれる各画素毎にそれぞれの最終色値を計算する 諸段階を具備する方法。