JPH0812702B2 - 画素生成方法及びシステム - Google Patents

Description

【発明の詳細な説明】 A.産業上の利用分野 本発明は、連続線形関数の２次元格子へのマッピング
に関する。具体的には、所与マシン・サイクル中に複数
の画素位置を生成する方法と装置を利用して、ラスタ表
示のための格子位置を決定することに関する。

B.従来技術 多くの場合、第１のパラメータｘの連続線形関数であ
る所与のパラメータｙを表わすために、可能なｘ及びｙ
値の２次元格子中の離散した位置を選択しなければなら
ない。格子の各点は、その格子点に関連付けられたｘ及
びｙ値の交点に位置する。このようにして形成された格
子点は、しばしば「画素」と呼ばれる。この形式の２次
元格子に連続線形関数を最も正確にマップするには、そ
の関数を表すべく選定した画素が、その関数の真のｘ及
びｙ値の最も近くに位置するものでなければならない。

この種のマッピング問題の一般的な例は、２次元ラス
タ格子上に連続線を表すことである。そうするには、真
の線に最も近くに位置する画素のｘ及びｙ座標を決定し
なければならない。ただし、ｘ及びｙは整数値である。
画素の座標を決定するのに使用されるアルゴリズムは、
しばしば走査変換アルゴリズムと呼ばれる。通常、この
アルゴリズムによって決定された画素座標は、記憶装置
のラスタ格子位置に対応するアドレスに記憶される。次
に従来のラスタ走査表示技術を利用してメモリを走査
し、そこに記憶された画素位置を輝かして、得られた線
を表示することができる。

通常のラスタ表示では、使用される走査変換アルゴリ
ズムが、頻繁に、おそらくはあるイメージが表示画面上
で作成または修正される度に、数百回または数千回も繰
り返して呼び出される。したがって、使用されるアルゴ
リズムは、画素位置を満足のいくように決定することの
他に、できるだけ迅速に実行しなければならない。走査
変換アルゴリズムを選択する際、速度と画質を両天秤に
かけて考量しなければならないことがしばしばある。所
与のアルゴリズムを最も迅速に実行するために、アルゴ
リズムが繰り返される度に実行される計算の数、特に乗
算と除算の数を最小にする増分方法が利用される。

従来の大部分のラスタ表示では、連続線を同時に１画
素ずつラスタ化し、各画素を順に生成していく。それを
実行するのにおそらく最も広く使用されているアルゴリ
ズムは、ブレゼンハムの線アルゴリズムと呼ばれるもの
である。このアルゴリズムは、多くのコンピュータ・グ
ラフィックスの教科書に説明されている。たとえば、こ
のアルゴリズムの説明とその誘導方法が、J.D.フォリー
（Foley）とA.ヴァン・ダム（Van Dam）の共著「対話型
コンピュータ・グラフィックスの基礎（Fundamentals o
f Interactive Computer Graphics）」、アジソン・ウ
ェズリー出版社（1982年）、のpp431−436に出ている。
この記載を引用により本明細書に組み込む。要約する
と、真の線を表すために様々な画素位置を選択すると
き、ブレゼンハムのアルゴリズムは、現誤差項及びそれ
に適用される訂正項を決定する。初期誤差項及び各訂正
項は、その線が横切るすべてのｘ及びｙの変位から決定
される。特定の各画素について、その画素に関連する誤
差項は、その画素が真線位置からずれている量を反映す
る。すなわち、様々な画素の誤差項を利用して、どの画
素がその線に最も近いかが決定される。画素位置が順に
選ばれ、後続の画素位置を選択するためにアルゴリズム
が繰り返されるとき、以前の画素位置の選択によって生
じた誤差項の変化を補償するため、現誤差項に適切な訂
正項が加えられる。線の終端に達して、最後の画素位置
が選択されるまでこのプロセスが続けられる。

C.発明が解決しようとする問題点 ブレゼンハムのアルゴリズムは整数の計算しか使用せ
ず、したがってアルゴリズムの計算を繰り返して実行す
る増分技法に向いている。さらに、その計算には２進デ
ータの加算、減算及び左シフトしか含まれない。時間が
かかる乗算や除算は含まれていない。したがって、ブレ
ゼンハムのアルゴリズムは、線をラスタ化する効率のよ
い手段をもたらすが、生成ハードウェアのあるマシン・
サイクルで１つしか画素位置を生成しない。ラスタ表示
システムの性能を向上させるには、より迅速な走査変換
技法が必要である。さらに、生成中の画素位置は、メモ
リ・アクセス争奪が回避または解消されるような形で、
ラスタ表示装置のフレーム・バッファ・メモリに記憶す
ることができなければならない。

したがって、本発明の一目的は、あるマシン・サイク
ル中にラスタ化された線の複数の画素位置を生成する技
術を提供することである。

本発明の他の目的は、追加マシン・サイクルの必要な
く、画素の生成中にメモリ・アクセス争奪が解決できる
ような形で、複数の画素位置を生成する方法を提供する
ことにある。

本発明の他の目的は、市販のハードウェアを用いて、
画素位置の決定に必要な計算を、迅速に実行できる画素
生成システムを提供することにある。

本発明の他の目的は、あるマシン・サイクル中に所定
の数の画素を生成するように調整することができる。画
素生成システムを提供することにある。

D.問題点を解決するための手段 １つの観点によると、本発明は、所与のマシン・サイ
クルで連続する複数の画素のデータ値を並列的に生成す
る。それらのデータ値は、１つの線形関数に含まれる画
素の座標を表し、その方法は、連続する複数の画素のお
のおのに対するブレゼンハムのアルゴリズムによる誤差
項の生成を含み、連続する画素の数は所定のマシン・サ
イクルで生成する画素の数に等しくなるように選択して
いる。

また、本発明の方法では、互いに並列に設けた複数の
ベクトル生成手段を用いて、並列に複数の画素に対する
データ値を、ブレゼンハムのアルゴリズムによって計算
した初期値及び生成中の画素を考慮した初期値の増分変
化の関数として決定する。

これによって、それぞれの画素に対するデータ値を一
つ一つ生成するのではなく、所与のマシン・サイクルの
間で複数の画素に対するデータ値を並列的に生成するこ
とができる。

さらに、本発明の方法は、ベクトル生成手段によって
供給されるデータ値を線形関数を表す画素位置データに
変換する。このとき、画素に対するデータ値が所与のマ
シン・サイクルで記憶できないと、このデータ値は、次
のマシン・サイクルで記憶すべく循環されるようにする
ことができる。これによって、メモリ・アクセス争奪が
生じて、記憶されないデータ値が生じても、次のマシン
・サイクルで記憶させることができる。

本発明の画素生成システムは、画素位置のｙ座標がゼ
ロ以上又はｘ座標以下となる座標系の８分円内に画素座
標が含まれるように線形関数を定義するためのパラメー
タを正規化する手段を含む。このように定義したそれぞ
れの画素位置に対してブレゼンハムのアルゴリズムを適
用するために初期誤差項を生成する手段として、所定の
ｎ個の連続する画素位置に対する誤差項を生成する手段
を含み、また、これによって生成された初期誤差項を用
いて任意のｎ個の連続する画素位置に対する誤差項を並
列的に生成する手段を含んでいる。

これによって、個々のマシンサイクルで一つ一つの画
素位置を示すｘ座標及びｙ座標を順に生成するのではな
く、所定のマシン・サイクルの間に任意のｎ個の連続す
る画素位置を示すｘ座標及びｙ座標を並列的に生成する
ことができる。

E.実施例 本発明の対象とする問題は、関数の真の座標に最も近
い位置にある２次元格子の離散位置を選択することによ
って連続線形関数を表すことである。この問題を第２図
にグラフで示す。線20は、線形関数ｙ＝ｘ（dy/dx）の
真のｘ及びｙの値を含む。この線形関数を図の画素格子
にマップするには、線20の座標の真の値に最も近い位置
にある画素について、（画素の中央に位置する）整数画
素座標を決定しなければならない。

直交座標系は対称なので、１つの画素座標と線形関係
を示すどの関数も、第２図に示す形に見えるように正規
化される。すなわち、座標（x1,y1）と（x2,y2）の間を
延びる線形関数について、線形関数の位置を、０≦dy≦
dx（ただし、dx＝x2−x1、dy＝y2−y1）となる座標形の
８分円内に制限することによって、当面の問題が単純化
できる。さらに、関数の１端点が座標系の原点に位置す
るとき、表される関数は一般性を失わない。というの
は、他の原点をもつ関数は座標（0,0）で始まる関数の
単なる変換にすぎないからである。

こうした点を考慮に入れた上で、連続線形関数を離散
ｘ及びｙ座標をもつ格子にマップするプロセス、たとえ
ば、線を画素格子にラスタ化するプロセスは、その画素
の所与のｘ座標値について、２つの可能なｙ座標値のど
ちらが真線により近い画素位置を提供するかを選択する
問題に帰する。したがって、第２図で、以前のステップ
すなわち（ｉ−１）番目のステップで、画素22が引こう
としている実際の線により近いと判定された場合、ｉ番
目のステップのタスクは、画素24と26のどちらが線20に
より近いかを決定することである。画素24と線20の距離
が、画素26と線20の間の距離よりも短い場合、画素24が
選ばれ、そうでない場合、画素26が選ばれる。第２図
で、画素24と線20の距離はｓで示され、画素26と線20の
距離はｔで示されている。したがって、選択すべき画素
の判定は、ｓがｔより小さいかどうかによる。言い換え
れば、（ｓ−ｔ）＜０の場合は、画素24が選ばれ、（ｓ
−ｔ）≧０の場合は、画素26が選ばれる。

ブレゼンハムのアルゴリズムは、線20が横切る画素格
子の各ｘ座標値について、２つの可能な画素位置間でこ
の選択を繰り返して行なう技術を提供する。ブレゼンハ
ムのアルゴリズムは、原点に最も近い画素から始まり、
線を表すのに必要な画素の連続する各ｘ座標値について
同時に１つずつ、各ｘ座標値に対して２つの可能なｙ座
標値のどちらを選択すべきかを順次判定する。このアル
ゴリズムは、（ｓ−ｔ）に比例する現誤差項を計算する
ことにより、この判定を行なう。誤差項は（ｓ−ｔ）に
比例するので、誤差項の符号によって、ｓがｔより小さ
いか大きいかが決まり、同時に、２つの可能なｙ座標値
のどちらかが真の線に最も近いかが決まる。

ブレゼンハムのアルゴリズムによれば、原点に最も近
い位置の画素について、2dy−dxによって定義される初
期誤差項が計算される。画素格子の次のｘ座標値につい
て、この初期誤差項の符号によって、線に最も近い画素
の正確なｙ座標値が決まる。その画素のｙ座標値のその
選択に付随する誤差を補償するため、以前の誤差項に増
分を加えることにより、新しい誤差項が計算される。追
加される増分は、以前の誤差項が負であるかそれとも正
であるかによって変わる。負の場合、増分は、2dyとし
て定義される。正の場合、２（dy−dx）と定義される。
その結果得られる新しい誤差項の符号が、次の画素の正
確なｙ座標値を決定するために使用される。

ブレゼンハムのアルゴリズムの方法を第２図に適用す
ると、ｉ番目のステップでは、画素24と26のどちらを選
択すべきかを判定するために、まず画素22の誤差項が計
算される。その結果得られる誤差項の符号が負である場
合、画素24が選ばれ、画素22について計算された誤差項
に量（2dy）が加えられる。画素22の誤差項が正の場
合、画素26が選ばれ、画素22の誤差項に量２（dy−dx）
が加えられる。その後のステップでこのアルゴリズムを
同様に適用すると、その結果、画素28と30が選ばれる。

第２図に示した選択された画素のｘ及びｙ座標の増分
変化は、２進ビットの列で表すことができる。ただし、
“0"は対応する座標値がその以前の値から変化しなかっ
たことを示し、“1"は対応する座標値が１だけ増分され
たことを示す。すなわち、画素26、28及び30のｘ座標値
は、２進ビット列“111"で表すことができる。同様に、
ｙ座標値の増分は、“101"で表すことができる。さら
に、ｘ座標値のビット列は変化しないので自明な列であ
り、画素26、28及び30のｘ及びｙ座標は、非自明な座標
のビット列、すなわち、“101"だけで正確に表すことが
できる。非自明な方向の座標値の列はしばしば、「ブレ
ゼンハム・シーケンス」と呼ばれる。その列内で、考慮
中のビットより以前に現われるビットは、履歴ビットと
呼ばれ、しばしばHmで示される。ｍは考慮中のビットに
対する履歴ビットの相対位置を識別する整数である。

本発明は、ブレゼンハムのアルゴリズムによって行わ
れるように各位置を順に生成するのではなく、同時に複
数の画素位置を生成するものである。一時にｎ個の画素
位置を生成するため、ブレゼンハム・アルゴリズムで利
用する基本概念を、高性能及び高いスループットをもた
らす並列処理技術と組み合わせる。本発明は、ブレゼン
ハムのアルゴリズムを用いて初期設定したｎ個の並列ベ
クトル生成器と、ブレゼンハム・アルゴリズムの基礎と
なる原理と同様な原理を用いて誘導した増分とを利用し
て、所与マシン・サイクルでｎ個の画素を生成するもの
である。本発明の方法では、各ベクトル生成器が、それ
自体の現誤差項を計算し、その符号を以下に示す他の情
報と一緒に使って、２つの可能な画素のどちらが表そう
としている線形関数の真の座標により近いかを判定す
る。誤差項の符号は、次のベクトル生成サイクルの準備
として、現誤差項に加えるべき適切な訂正項を選択する
ためにも使用される。

次に、サイクルごとに現誤差項を調節する際に使用さ
れる増分の誘導について、概略を述べる。第３図を参照
すると、画素32が（ｉ−１）番目のステップ中に線38の
真の座標（xi,yi）により近い画素であると判定された
場合、ｉ番目のステップにおいて、画素34と画素36のど
ちらが線38により近いかの判定は、画素32の誤差項の符
号によって決まる。ブレゼンハム・アルゴリズムと同様
に、誤差項は（ｓ−ｔ）に比例すると定義する。したが
って、画素32の誤差項の符号が負の場合、ｓはｔより小
さく、画素34の方が画素36よりも線38に近い。逆に、画
素32の誤差項がゼロまたは正の場合、ｔはｓ以下であ
り、画素36が選択される。

第３図に示す画素格子がｓ＋ｔ＝１になるように「正
規化」されていると仮定すると、ｔ＝１−ｓである。ｔ
のこの値を式ｓ−ｔに代入すると、次式が得られる。

（ｓ−ｔ）＝2s−１ （１） また引こうとしている線が任意の２点間にあり、かつ
第１の端点の方が第２の端点よりも原点に近いと仮定す
ると、第３図に座標（xi,yi）で示した点が原点にき
て、したがって（0,0）の座標値をもつように、この線
の端点をそれぞれ変換することができる。したがって、
線38は式ｙ＝（dy/dx）ｘによって定義される。画素34
及び36については、ｘ＝ｐ＋ｎであり、したがって、ｙ
＝（dy/dx）（ｐ＋ｎ）である。しかし、第３図から、
ｘ＝ｐ＋ｎの場合、ｙ＝ｑ＋ｒ＋ｓであることは自明で
あり、したがって次式が得られる。

ｑ＋ｒ＋ｓ＝（dy/dx）（ｐ＋ｎ） （２） ｓについて方程式（２）を解き、その結果の値を方程
式（１）に代入すると、次式が得られる。

（ｓ−ｔ）＝2s−１ ＝２（dy/dx）（ｐ＋ｎ）−2q−2r−１ （３） 方程式（３）の両辺にdxを掛けて、項を整理し、次に
Di＝dx（ｓ−ｔ）と定義すると、次式が得られる。

Di＝２（ｐ）（dy）−ｑ（dx） ＋2n（dy）−（１＋2r）dx （４） ただし、点（xi,yi）が格子座標系の原点にくるよう
に格子座標系を線38と整合させた場合、ｐ＝xi及びｑ＝
yiである。これらの値を方程式（４）に代入すると、次
式が得られる。

Di＝２（xi）（dy）−yi（dx） ＋2n（dy）−（１＋2r）dx （５） となる。Ｄ（ｉ＋ｎ）について同様の式を作り、Ｄ（ｉ
＋ｎ）の式からDiの式を引くと、次式が得られる。

Ｄ（ｉ＋ｎ）−Di＝2dy（ｘ）（ｉ＋ｎ−xi） −2dx（ｙ）（ｉ＋ｎ）−xi （６） 第３図から、ｘ（ｉ＋ｎ）−xi＝ｎとなることが分か
る。Diがゼロより小さい場合、ｙ（ｉ＋ｎ）−yi＝ｒと
なることも自明である。同様に、Diがゼロ以上の場合、
ｙ（ｉ＋ｎ）−yi＝ｒ＋１である。方程式（６）でこれ
らの条件を用いると、次のようになる。

Ｄ（ｉ＋ｎ）−Di＝2n（dy） −２（ｒ＋１）dx,ただし、Di≧０の場合 （７） Ｄ（ｉ＋ｎ）−Di＝2n（dy） −２（ｒ）dx,ただし、Di＜０の場合 （８） すなわち、誤差項に加えられるそれぞれの増分は、2n
（dy）−２（ｒ）dx及び2n（dy）−２（ｒ＋１）dxで表
される。これらの式で、変数ｒは、線形関数が含まれる
８分円の領域に方程式を正規化するのに使用される。変
数ｒは、０と（ｎ−１）の間の整数値をとる。この変数
の意味については後で説明する。

座標（xi,yi）で示される線38上の点は、線38上の他
の点よりも画素座標系の原点に近いと仮定されているの
で、上記の誘導は左から右に引かれる線についてのもの
である。右から左に引かれる線では、どちらの画素がそ
の線により近いかの判定は、ゼロより小さいかどうかで
はなく、Di＝０であるかどうかによって決まる。この調
節により、反対方向に引かれる線が同じ画素位置で表さ
れることになる。本発明のアルゴリズムは整数演算を使
用するので、初期誤差項から１を引きさえすれば、望ま
しい両方向対称性が確保される。

一般に逐次的性格をもつ走査変換アルゴリズムを利用
して、複数の画素を並列方式で生成しようと試みると、
多くの分野で問題が生じる。特に重要なのは、画素生成
システムの初期設定に必要な処理、結果として発生する
現誤差項の解釈とその正確な画素位置への変換、及び同
時に複数の画素位置をフレーム・バッファ・メモリに書
き込もうとする時に発生し得るメモリ・モジュール・ア
クセス衝突の解決である。本発明は、これらの問題のそ
れぞれに対する解決策を提供する。ベクトル生成器を、
ブレゼンハム・アルゴリズムにしたがって計算される誤
差項で初期設定し、サイクルごとに各ベクトル生成器に
ついて現誤差項を調節するための適切な増分を決定す
る。ベクトル生成器によって計算される現誤差項の符号
ビットは、他の関連情報に基づいて解釈され、したがっ
て変換されたデータは、離散点の２次元格子上の線形関
数のマッピングを表す。本発明はさらに、所与のサイク
ル中にいくつの変換データ・ビットが記憶できるかを判
定し、記憶されなかったデータ・ビットを再循環させて
それらを後続のサイクルで記憶できるようにする方式を
提供する。本発明のこれらの実施例については、それぞ
れ本明細書の後の部分で十分に説明する。

第１図は、本発明に基づく複数画素生成システムの関
数区分及び流れ順序の一実施例を概略的に示す構成図で
ある。第１図に示す関数をすべて提供する必要のないア
プリケーションもある。本発明によると、画素生成シス
テムの所与のマシン・サイクルで複数の画素のデータ値
を生成するのに必要な基本関数がブロック44と46に含ま
れている。ただし、データ値は少なくとも１つの画素の
座標の線形関数を表す。ブロック44は、連続する複数の
画素のおのおのについてブレゼンハム・アルゴリズムに
よって誤差項を生成し、連続する画素の数は、同じマシ
ン・サイクル中に同時に生成される画素数に等しい。ブ
ロック44は、サイクルごとに誤差項を更新するのに必要
な増分も生成する。ブロック46は、所与のマシン・サイ
クル中に複数の画素のデータ値を同時に生成するのに必
要な関数を含む。ブロック46は、互いに並列に接続さ
れ、各ベクトル生成器が複数の画素のうち関連するもの
のデータ値を提供するように配列されている、複数のベ
クトル生成器を含む。各ベクトル生成器ごとに、データ
値が、所与のサイクルで生成される画素数の関数、また
ブロック44で生成される誤差項の関数として決定され
る。

本発明の画素生成システムはさらにブロック42と48を
含むことが好ましい。ブロック48は、ベクトル生成器に
よってもたらされたデータ値を、マップされている線形
関数を表す画素位置データに変換する関数を含む。ブロ
ック48は、また所与のマシン・サイクル中に同時に生成
されたデータ値を記憶する関数、及びメモリ・モジュー
ル・アクセス衝突を解決する方式も含むことができる。
一実施例では、メモリ・アクセスの制約条件を満たす生
成データ値が、所与のマシン・サイクル中に記憶され、
記憶されなかったデータ値は、後のマシン・サイクルで
ベクトル生成器によって再生成される。別の実施例で
は、メモリ・モジュール・アクセス規則を満たす生成デ
ータ値が、所与のマシン・サイクル中に記憶され、残り
の生成データ値は、ベクトル生成器で再生成されずに後
のマシン・サイクルで記憶されるように指定される。

第１図のブロック42は、線形関数のパラメータを正規
化するのに必要な関数を含み、こうした関数すべてにつ
いて、その関数の画素座標が画素座標系の同じ８分円内
に含まれる。一実施例では、可能な画素座標の格子が複
数の８分円に分割され、８分円１と名付けた８分円で
は、線形関数を表す画素座標がゼロ以上であるがその線
形関数の引数として使われる画素座標以下である。次に
その線形関数のパラメータが、この第１の８分円内に含
まれるように正規化される。この第１の８分円は、領域
の数が所与マシン・サイクル中に生成される画素の数に
等しい、複数の領域に分割されることが好ましい。これ
らの領域は、さらに、線形関数を表す画素座標を含む特
定の領域がブロック44で生成された誤差項の符号の関数
として決定できるように構成される。この構成で、生成
中の画素データは、線形関数の座標を含む領域の識別デ
ータの関数である。

第１図に示す画素生成システム中の流れ順序は、以下
のように要約できる。ユーザ指定パラメータdx及びdyは
絶対値論理ブロック42が入力として受け取る。変数dx
は、ｘ座標の終端値と初端値の差であり、dyはｙ座標の
終端値と初端値の差である。dx及びdyのそれぞれの絶対
値とそれらの絶対値の差がブロック42で計算され、次に
増分／誤差項論理ブロック44に送られる。入力dxが入力
dy以上であるかどうかを示すデータ信号XGEYもブロック
42で決定される。この比較の結果に応じて、dxの絶対値
が変数PDXに割り当てられ、dyの絶対値が変数PDYに割り
当てられ、またはこれらの変数中に記憶された絶対値デ
ータが交換される。ブロック42で捕捉され、ブロック44
に記憶される最後の２つのデータは、入力dx及びdyの符
号である。ブロック44は、ブロック42からの様々なデー
タを使って、ブロック46の各並列ベクトル生成器につい
て初期誤差項を計算する。これらの初期誤差項は、第１
図でE0,E1,E2及びE3として示されている。現誤差項を各
サイクルで生成された画素を反映するように調節するた
めに、ブロック46の各並列ベクトル生成器について現誤
差項に加えられる増分もブロック44で計算される。変換
/MCR論理ブロック48は、ブロック46の各ベクトル生成器
の現誤差項の符号を、ラスタ化線画素位置の重要な座標
の値の増分変化を表す２進ビットの列に変換する。メモ
リ争奪解決（MCR）論理は、この列のどのビットが現マ
シン・サイクルで記憶できるかを決定する。記憶できる
ビットは、フレーム・バッファ・メモリのｘ及びｙ位置
カウンタを更新するのに使用できるXPOSとYPOSデータと
して、ブロック48から送り出される。

絶対値論理ブロック42の一実施例が、第４図の構成図
によって概略的に示されている。第４図に示すシステム
で最初の処理サイクルが発生する前に、入力dxがパイプ
ライン・レジスタ50中にある場合、絶対値論理ブロック
42に含まれている上記の関数を第４図の装置によって連
続する３つの処理サイクルで実行するのが好都合であ
る。最初のサイクル中に、dxがパイプライン・レジスタ
50から線64を介してマルチプレクサ52に送られ、そこか
ら線66を介して加算器56に送られる。加算器56でdxの絶
対値を計算するため、dxが、線80を介して加算器56に到
来する信号と結合される。線74上の入力信号も、加算器
56のdxの絶対値に追加される。最初の処理サイクルで、
マルチプレクサ54は、入力線72上の「０」レベル信号を
選択する。その結果、入力線74上での信号の追加がゼロ
になり、加算器56から線68を介してラッチ58に転送され
た信号は、dxの絶対値を表す。

第２の処理サイクルで、dyはレジスタ50から装置を介
して送られ、dxについて今説明したのと同様に、dyの絶
対値になってラッチ60に記憶される。第３の処理サイク
ルで、ラッチ58の出力が線70を介してマルチプレクサ54
に送られ、ラッチ60の出力が線76を介してマルチプレク
サ52に送られる。マルチプレクサ54と52はラッチ58と60
からのこれらの出力信号をそれぞれ線74と66を介して加
算器56に送る。加算器56へのこれらの入力は、線80上の
入力信号と組み合わされて、dxの絶対値とdyの絶対値の
差を表す出力を線68上に生成する。この絶対値の差が、
線78を介して次の段に送られる。加算器56中での計算
で、dx及びdyの大小を示す出力信号も線82上に生成され
る。この信号は、ブロック62の処理を制御する。変数XG
EYがゼロに等しい場合、線84を介してブロック62に送ら
れるdxの絶対値が、変数PDYに割り当てられ、線86を介
してブロック62に送られるdyの絶対値が変数PDXに割り
当てられる。一方、XGEYが１に等しい場合、交換は実行
されず、dx及びdyの絶対値がそれぞれ変数PDXとPDYに割
り当てられる。残りの変数XSGNとYSGNのデータは、レジ
スタ50から線88を介して得られる。

第１図に関連して上記に述べたように、増分／誤差項
論理ブロック44は、ブロック46の各並列ベクトル生成器
についての初期誤差項、及びサイクルごとに各ベクトル
生成器の現誤差項を更新するのに使用される２つの増分
項を計算する。ｎ個の並列ベクトル生成器に対する初期
誤差項は、連続するｎ個の画素それぞれにブレゼンハム
・アルゴリズムを順次適用することによって決定され
る。すなわち、最初のｎ個の画素位置P0、P1、...、Ｐ
（ｎ−１）に対する誤差項は、ブレンゼンハム誤差項E
0、E1、...、Ｅ（ｎ−１）である。ブレゼンハム誤差項
では、連続する各誤差項Ｅ（ｉ＋１）は、前の誤差項Ei
に適切な増分を加えて計算できる。加えられる増分値
は、Eiの符号によって変わる。符号が負の場合、増分は
2dyである。符号が正の場合、増分は2dy−2dxである。
すなわち、E0の符号が負である場合、誤差項E1はE0＋2d
yに等しい。E0の符号が正の場合、E1はE0＋2dy−2dxに
等しい。ブレゼンハム・アルゴリズムではE0＝2dy−dx
なので、E1は4dy−dxまたは4dy−3dxに等しい。残りの
誤差項E2ないしＥ（ｎ−１）はそれぞれ順次同様に計算
できる。こうして計算された誤差項は、判断木を形成す
る。木のメンバーは、一定の増分値によって結合されて
いる。ｎ＝４の場合について、その結果得られる誤差項
判断木を、第５図に示す。様々な誤差項の間でのこの増
分関係が重要なのは、次の誤差項への条件付き分岐を行
なう無駄なサイクルなしに、ハードウェアの当該段が動
作できるからである。

増分／誤差項論理ブロック44は、画素位置Ｐ（ｉ＋
ｎ）、Ｐ（ｉ＋2n）などに対する誤差項が生成されると
き、各並列ベクトル生成器の現誤差項を更新するのに使
用される増分をも計算する。本発明により生成される誤
差項Ｅ（ｉ＋ｎ）、Ｅ（ｉ＋2n）などは、ブレゼンハム
・アルゴリズムによって生成された誤差項と同様に、そ
れぞれ、前の誤差項に適切な増分を加えて計算できる。
また、やはりブレゼンハム・アルゴリズムと同様に、増
分の２つの可能な値のどちらを選択するかは、増分を加
えるべき誤差項の符号によって決まる。増分の２つの可
能な値を計算するハードウェアは、ｎ個の並列ベクトル
生成器について初期誤差項を生成するのに使用される１
つまたは複数の処理サイクル中にそれらの増分が決定さ
れるように構成される。そうすると、画素生成システム
の初期設定ならびにハードウェアの複雑さを低減させる
のに必要な処理サイクルの数が減少する。

こうした理由から、本発明の画素生成システムの好ま
しい実施例では、最初のｎ個の画素位置についての少な
くとも数個の誤差項の符号を使って、座標系の第１の８
分円のｎ個の可能な領域のどれがマップされた関数の画
素座標を含むかを決定する。次に増分の２つの可能な値
が、その領域の関数として決定される。この領域の関数
としての増分値の１つの方程式は、第３図に関連して上
記で誘導した。したがって、好ましい一実施例では、増
分の２つの可能値は、その増分を加えるべき誤差項の符
号がそれぞれ正及び負の場合、2n（dy）−２（ｒ＋１）
（dx）及び2n（dy）−２（ｒ）（dx）である。これらの
式で、ｒは線形関数の座標を含む領域を指す。

第６図は、ｎ＝４の場合の増分／誤差項論理ブロック
44の実施例の概略図である。図の実施例では、４処理サ
イクルで４つの誤差項及び増分の２つの値をすべて計算
して、ハードウェアの次の段に送ることができる。絶対
値論理ブロック42からの出力信号はすべてパイプライン
・レジスタ90中にあると仮定する。最初のサイクルで、
ｘとｙの絶対値の差がレジスタ90から線115を介して送
られ、左桁寄せ演算の実行によりそれに２を掛け、線11
6を介して排他的論理和回路92に入力として送られる。
排他的論理和回路92の出力は、線122を介してマルチプ
レクサ96に送られる。マルチプレクサ96は線122上の信
号を選択し、それを線124を介して加算器100に送る。同
じサイクル中に、PDXがレジスタ90から線115と120を介
してマルチプレクサ98に送られる。PDXはマルチプレク
サ98によって選択され、線126を介して加算器100に送ら
れる。加算器100は線124、126及び128上の入力を結合
し、その出力を誤差項レジスタ102に送る。この最初の
サイクルでは、加算器100の出力は、第１画素位置に対
するブレゼンハム誤差項である。PDXとシステムで使用
される任意のコマンド・ワードも、この第１サイクル中
にレジスタ90から他のハードウェア段に送ることができ
る。第２のサイクル中に、E0がレジスタ102から線134を
介してマルチプレクサ104に送られ、また線132を介して
マルチプレクサ98に送られる。E0はマルチプレクサ98か
ら線126を介して加算器100に送られる。第１サイクルと
同様に、dxとdyの絶対値の差に２が掛けられて、排他的
論理和回路92に送られ、その出力がマルチプレクサ96に
送られる。PDYはレジスタ90から線115を介して送られ、
２を掛けられ、線118を介してマルチプレクサ96に入力
として送られる。誤差項E0の符号に応じて、マルチプレ
クサ96は、線118と122上に入力のどちらかを選択し、選
択された信号を加算器100に送る。線118と122上の信号
は、ブレゼンハム誤差項を計算するための増分を表す。
すなわち、線126上の入力がE0のとき、加算器100の出力
は次の誤差項E1である。E1は線130を介してレジスタ102
に送られ、また線140を介してマルチプレクサ106に送ら
れる。この第２サイクル中に、E0とE1がそれぞれマルチ
プレクサ104と106によって次のハードウェア段に送られ
る。また第２サイクル中に、E0に４が掛けられ、線142
を介してマルチプレクサ108と110に送られる。E1に２が
掛けられ、線138を介してマルチプレクサ108と110に送
られる。排他的論理和回路92の出力は加算器94に送ら
れ、加算器94の出力は2PDY−2PDXである。この式に４が
掛けられ、線144を介してマルチプレクサ108に送られ
る。PDYは、レジスタ90から線115を介して送り出される
他に、８を掛けられて、線146を介してマルチプレクサ1
10にも送られる。誤差項E0とE1の符号は、それぞれマル
チプレクサ108と110に送られ、他の入力と結合されて、
増分の２つの値I1とI2を決定する。最初の増分値はマル
チプレクサ108中で決定され、線148を介してラッチ112
に送られる。第２の増分は、マルチプレクサ110中で決
定され、同様に線150を介してラッチ114に送られる。

第３の処理サイクルでは、誤差項E1について説明した
のと同様にして、誤差項E2が生成される。E2は線136と
マルチプレクサ104を介して次のハードウェア段に送ら
れる。同じサイクルで、増分I1が線152とマルチプレク
サ106を介して次の段に送られる。最後のサイクルで
は、誤差項E1について説明したのと同様にして、誤差項
E3が生成される。E3は線136とマルチプレクサ104を介し
て装置から送り出される。この最後のサイクルで、増分
I2も、線154とマルチプレクサ106を介して次のハードウ
ェア段に送られる。

マルチプレクサ108と110で決定される増分は、E0とE1
のそれぞれの符号に応じて変わる。これらの符号ビット
は、線形関数の座標を含む領域を決定するものである。
第６図の実施例では、マルチプレクサ108によって決定
される増分は、（8PDY−8PDX）（/d）（/f）＋2E1（/
d）（ｆ）＋4E0（ｄ）（/f）＋2E1（ｄ）（ｆ）で表す
ことができる。ただし、ｄとｆはそれぞれE0とE1の符号
ビットであり、/dと/fはそれぞれ“否定d"及び“否定f"
を意味する。マルチプレクサ110で決定される増分も同
様に、2E1（/d）（/f）＋4E0（/d）（ｆ）＋2E1（ｄ）
／（/f）＋8PDY（ｄ）（ｆ）で表すことができる。ビッ
トｄとｆによって復号される領域とその様々な値に対応
する増分を第７図に示す。ビットｄとｆはそれぞれE0と
E1の符号を表すので、それらのビットは、これら２つの
誤差項が段から段に送られるとき、E0とE1の最上位ビッ
トとして後のハードウェア段に自動的に送られる。

第１図に示すブロック46の並列ベクトル生成器が第１
の連続するｎ個の画素位置に対する誤差項を計算するこ
とによって所定設定されると、単一マシン・サイクル中
にｎ個の誤差項がベクトル生成器によって一時に並列に
生成される。このｎ個の誤差項は、前のサイクルで生成
された位置に続く次のｎ個の画素位置に対応する。後続
のｎ個の現誤差項は、それぞれ、ブロック44で決定され
る増分の２つの可能な値の１つを、当該のベクトル生成
器の現誤差項に加えることにより決定される。生成され
た誤差項を表す２進ビットの流れを形成するために、誤
差項の符号に応じて１または０の２進ビットが、生成さ
れた各誤差項に指定される。一実施例では、誤差項符号
が負のとき０が指定され、そうでないときは１が指定さ
れる。この構成では、１の２進ビットは、対応する画素
座標の位置の上昇をも示す。

しかし、ｎ個の複数のベクトル生成器のデータが並列
に処理されるので、上記の規則を用いて得られるデータ
・ビットの流れは、必ずしもラスタ化線の「真」のブレ
ゼンハム・シーケンスを反映しない。したがって、第１
図の変換/MCR論理ブロック48に含まれる関数の１つは、
並列生成器からラスタ化線または他のマップ化線形関数
の画素位置にデータを変換する。一実施例では、ラスタ
化関数を表すブレゼンハム・シーケンスの２進ビット
は、少なくとも部分的には、ビット列中に以前に現れた
履歴ビットの関数として、またラスタ化関数の画素座標
を含む領域の関数として決定される。これらの領域のお
のおのについて、変換データが、その特定の領域で満足
しなければならない条件によって部分的に指定される。

サイクルごとにｎ個の画素を生成するのに使用される
ｎ個の領域のおのおのに固有の条件のうちには、各領域
で許されるｙ座標値の増分の最小数及び最大数がある。
ここで第８図を参照すると、ｎ個の画素を同時に生成す
るのに使用される８分円をｎ個の領域に分割した場合、
領域ｒ内に含まれる線は、０とｎ−１の間のｒのすべて
の値に対してr/nと（ｒ＋１）/nの間の勾配をもつ。第
８図に示したｎ＝４の場合、領域０に含まれるすべての
線は、０と0.25の間の勾配をもつ。領域１については、
勾配は0.25から0.5の範囲である。領域２では、勾配は
0.5から0.75の範囲であり、領域３では、勾配は0.75か
ら1.0の範囲である。

さらに、所与の任意の領域ｒについて、画素位置Ｓか
ら位置A,B,C,DまたはＦのうち当該の位置までのｙ座標
値の変化がｒとｒ＋１の間になければならない。すなわ
ち、所与の任意の領域ｒについて、ｎ個のビットのブレ
ゼンハム・グループは、１の値をもつビットをｒまたは
ｒ＋１個もつ。たとえば、領域０では、複数の画素生成
アルゴリズムは画素ＤとＦのどちらかを選択し、４ビッ
トのブレゼンハム・グループは、それぞれ１の値をもつ
ビットを０または１個含む。領域１では、選択は画素Ｃ
とＤの間で行なわれる。領域２では、選択は画素ＢとＣ
の間で行なわれる。領域３では、選択は画素ＡとＢの間
で行なわれる。第７図から、ｎ＝４の場合、ビットｄと
ｆは復号されると４つの領域の１つを識別することを思
い起こし、ｄとｆは誤差項E0とE1の符号ビットであるこ
とを思い起こすと、この領域情報と履歴ビットを組み合
わせて生成中の画素の真のブレゼンハム・シーケンスが
決定できることは明らかである。S0がE0の符号を指定
し、かつE0が負のとき及びSOが２進数の１で表されるな
らば、S0＝１のとき、４つのブレゼンハム・グループの
ｒ個のビットだけが１となり得る。逆に、S0＝０の場
合、ブレゼンハム・グループのｒ＋１個のビットが１で
なければならない。

領域０のP0をb0で表し、領域１のP0をc0で、領域２の
P0をd0で、領域３のP0をe0で表す場合、領域０の４ビッ
トのブレゼンハム・シーケンスはH3,H2,H1、b0として表
すことができる。ただし、H1,H2及びH3はb0の発生前の
履歴ビットを表す。他の領域のブレゼンハム・シーケン
スは、領域１でb0をc0に、領域２でb0をd0に、領域３で
b0をe0に置き換えることによって同様に表すことができ
る。上述の拘束条件を適用する場合、すなわち、S0が０
のときシーケンスのｒ＋１個のビットが１でなければな
らず、S0が１のときｒ個のビットが１でなければならな
い場合、それぞれの領域に対して第９図に示した真理値
表が作成される。領域０及び１では、２つのブレゼンハ
ム・グループが値が１のビットを最高１個しかもてない
という追加の拘束条件が課される。したがって、ブレン
ゼンハム・シーケンス0110、1100及び0011は領域０及び
１で有効ではない。さらに、領域２及び３では、２つの
ブレゼンハム・グループは、値が１のビットを最低１個
もたなければならない。したがって、ブレゼンハム・シ
ーケンス0011、1001及び1100は領域２及び３では有効で
はない。これらの追加の拘束条件が第９図に示した真理
値表に課される場合、それぞれの領域についてその結果
得られるパラメータ値の組を第10図に示すビット・マッ
プに変換することができる（第９図及び第10図で、
「Ｄ」は関連するビットについて「どちらでもよい」状
態を表し、本明細書全体を通じて誤差項E0の符号を表す
ために使用する「ｄ」とは無関係なことを了解された
い）。

第10図に示すビット・マップのそれぞれについて、S0
とH1−H3によってb0、c0、d0及びe0を表すブール方程式
が生成できる。すなわち、 領域０では、 b0＝/H3＆/H2＆/H1＆/S0; 領域１では、 c0＝/H1＆/S0＋/H3＆/H2＆/H1; 領域２では、 d0＝/H1＋/H3＆/S0＋/H2＆/S0; 領域３では、 e0＝／（H3＆H2＆H1＆S0） さらに、P0はb0,c0,d0、e0及び符号ビットｄとｆによ
って以下のように表すことができる。

P0=b0&d&f+c0&d&/f+d0&/d&f+e0&/d&/f. 上記の各方程式中で、“＋”はOR演算を示し、“＆”
はAND動作を示し、“/"はNOTを示す。

一実施例では、後続の画素P1,P2及びP3（ｎ＝４の場
合）は、上記のブール式をほぼ複製する３つの追加論理
段をカスケード化することによって決定される。別法と
して、ブール代入及び約分によりP1、P2及びP3の方程式
を誘導することもできる。画素P1−P3を決定する最初の
方法は、必要なブール式が減少するが、信号が追加論理
段を通過するのに余分な伝播時間が必要である。第２の
方法は、遅延時間が減少するが、ゲート・カウントは増
加する。本発明の好ましい実施例によると、変換論理
は、カスケード論理要素とブール論理要素の組合せを含
む。ｎ＝４の場合、論理はそれぞれ２ビットの「スライ
ス」にまとめることができ、この２つのスライスがカス
ケード化される。この実施例では、各スライスは２つの
ブレンゼンハム・ビットを生成する。変換論理をこのよ
うに構成すると、ゲート・カウント、信号ファンアウト
及び方程式の複雑さが減少し、わずか６つのNANDゲート
・レベルしか必要でない。

この種の組み合わせたブール論理関数とカスケード論
理関数をもたらす変換論理の構成を、領域０−３のおの
おのについて第11a図ないし第11d図に示す。すべての領
域に対する論理がどのように組み合わされるかを第11e
図に示す。第11a図ないし第11d図のおのおのにおいて、
各論理ブロックの第２のブール方程式が、履歴ビットを
１つの位置だけシフトし、新しい履歴ビットをそのブロ
ックの第１のブール式に代入することによって誘導され
る。たとえば、b1の方程式は、b0の方程式において、H3
にH2を、H2にH1を、H1にS0を、S0にS1を代入することに
よって誘導される。関連するブール代数を実行し、不必
要な項を除去すると、結果として、b1の方程式が得られ
る。

第12図の構成図は、画素生成ブロック46と第１図に示
した変換/MCR論理ブロック48を組み合わせるための１つ
の構成の概略図である。並列ベクトル生成器160はそれ
ぞれ、増分の２つの可能な値の１つを選択するためのマ
ルチプレクサ162を含む。その値はレジスタ164と166に
記憶されている。加算器170中で、各ベクトル生成器に
ついてマルチプレクサ162によって選ばれた増分が、そ
の生成器の現誤差項に加えられる。現誤差項はレジスタ
168に記憶されている。レジスタ168に記憶された誤差項
の符号ビットはｎビット信号として変換論理回路172に
送られ、そこで、その信号はレジスタ／マルチプレクサ
174からの（ｎ−１）ビット履歴信号及びレジスタ176か
らの２ビット領域信号と組み合わされる。変換論理回路
172中でこれらの信号を組み合わせて得られた真のブレ
ゼンハム・シーケンスが、メモリ争奪解決論理回路178
に送られる。この論理回路の機能については後で説明す
る。変換論理回路172に必要な履歴ビットは、H1＝/d、H
2＝/f、及びH3＝/dとなるようにレジスタ／マルチプレ
クサ174によって初期設定される。このようにして、履
歴ビットH1−H3は、変換論理回路172内の論理関数が実
行されるとき正確な最初の４つの画素を与えるように初
期設定される。初期サイクルの後、更新された履歴ビッ
トは、履歴ビット経路指定論理回路180からレジスタ174
を介して変換論理回路172が受け取る。

MCR論理回路178の機能は、所与マシン・サイクル中に
複数の画素をメモリ・デバイスに書き込まなければなら
ないときに発生するメモリ争奪問題を解決することであ
る。メモリ争奪は通常、フレーム・バッファ制限の状況
で起こる。メモリ争奪が起こるのは、２つ以上の画素を
フレーム・バッファに書き込むために、またはフレーム
・バッファのメモリ構成及びメモリ・アドレスにアクセ
スするための規則からメモリ・アクセス衝突が発生した
ために、複数のメモリ・モジュールにアクセスすること
が必要になるためである。MCR論理回路178は、生成され
た画素を特定のサイクル中に衝突なしにいくつ書き込め
るかを決定し、書き込めない画素を再循環させることに
よって、メモリ争奪を解決する。特定のサイクルで記憶
できない画素の情報を循環させることにより、メモリ争
奪問題が、各処理サイクルごとに「オン・ザ・フライ方
式」で解決される。したがって、任意の所与のサイクル
中に記憶できる画素の最大数が生成され、画素生成シス
テムによって記憶される。さらに、そのように構成され
たMCRメモリ回路を用いると、画素生成システムの動作
を画素記憶システムの動作と調整するために追加の制御
ハードウェアが必要でなくなる。MCR論理回路178は、任
意の所与のサイクルで０ないしｎ個の画素がデータ・フ
ローまたはデータ保全性を乱さずに生成されるように、
画素生成の自己最適化を行なう。各サイクル中に記憶さ
れる画素の実際の数が、制御機構182に含まれる長さカ
ウンタから差し引かれ、長さカウンタの値がゼロになる
までその処理が継続される。

第12図に示す実施例では、メモリ・デバイスのアクセ
ス規則を満たす生成画素位置は、それらが生成される処
理サイクル中にそこに記憶される。記憶できない画素
は、以後の処理サイクルで再生成され、そうしてもメモ
リ・アクセス衝突が起こらないときに、メモリ・デバイ
スに記憶される。第12図で、記憶できる画素は、画素P0
−ＭとしてMCR論理回路178から送り出される。ただし、
Ｍ＋１は記憶されている画素の数に等しい。所与のマシ
ン・サイクル中に記憶できない画素については、関連す
る誤差項が、誤差項経路指定論理回路184を介して対応
するベクトル生成器の現誤差項レジスタ168に戻る。次
の処理サイクルで、その誤差項は、他のレジスタ168中
の誤差項と共に再処理される。履歴ビット経路指定論理
回路180は記憶されていない画素の履歴ビットも再循環
させる。MCR論理回路178からの当該の制御信号が、誤差
項経路指定論理回路184と履歴ビット経路指定論理回路1
80に、次の処理サイクルで古いデータと新しいデータの
どちらを使用すべきかを示す。次の処理サイクルで使用
される誤差項及び履歴ビットを、現処理サイクル中に記
憶できる画素の数の関数として、第13図に示す。したが
って、第13図は、未記憶データがどのように再生成され
て後のサイクルで記憶されるかを示す。

第12図に示す実施例に代わる別の実施例では、変換論
理に必要な情報だけがサイクルごとにシャッフルされ
る。したがって、誤差項自体ではなく、誤差項の符号ビ
ットだけが送られる。履歴ビットは第12図に示したのと
同じ方式で再循環される。この別の実施例では、２ビッ
トのポインタによって次の処理サイクルの最初の画素の
誤差項を計算するベクトル生成器を識別する。ポインタ
の位置は、生成され記憶される画素の数に応じてサイク
ルごとに変化する。すなわち、マルチプレクサ選択論理
は、所期の画素生成速度と誤差項ポインタの両方の関数
である。ただし、経路指定マルチプレクサの幅は、誤差
項の符号ビットだけが送られるとき縮小できるので、こ
の関数を実行するのに必要なハードウェアの量が減少す
る。

２ビット・ポインタの10進値によって、次の処理サイ
クルでどのベクトル生成器が誤差項E0を計算するかが決
まる。たとえば、ポインタが２進数01（10進数１）に設
定されている場合、ベクトル生成器No.1が次のサイクル
で誤差項E0を計算する。したがって、ベクトル生成器N
o.1の誤差項の符号ビットが、S0として変換論理に送ら
れ、ベクトル生成器No.2の符号ビットがS1として送ら
れ、ベクトル生成器No.3の符号ビットがS2として送ら
れ、ベクトル生成器No.0の符号ビットがS3として送られ
る。第14図に、ポインタの様々な値に対してS0−S3のそ
れぞれにどの生成器の符号ビットが指定されるかを示
す。

生成された画素のすべてが所与のサイクル中にフレー
ム・バッファに書き込めるのではない場合、ポインタ値
は、次のサイクルで誤差項E0を計算するために使用され
る新しいベクトル生成器番号を示すように変化する。た
とえば、ポインタが０に等しく、３つの画素しか書き込
めない場合、次のポインタ値は３である。さらに、ベク
トル生成器No.3のレジスタ168の現誤差項に、そのベク
トル生成器の現誤差項の新しい値が重ね書きされること
はない。したがって、次の処理サイクル中に、ベクトル
生成器No.3の誤差項の古い値が新しいE0として設定され
る。このようにして、ある誤差項が特定のサイクルで使
用されない場合、それは以後のサイクルで使用される。
ポインタの様々な値に対して、所与のサイクルで３つ以
下の画素を記憶することの誤差項生成に対する効果をそ
れぞれ、第15図ａ図ないし第15d図に示す。

本発明をそのいくつかの好ましい実施例に基づいて詳
細に説明してきたが、当分野の技術者なら多くの修正と
変更を加えることができる。たとえば、図面とそれに関
連する説明の多くでは、一時に４つの画素を生成するシ
ステムを記載したが、本発明の方法と装置を利用して同
時に他の数の画素を生成することもできる。また、いく
つかの実施例では、複数の処理サイクルにわたって変数
を多重化することにより、データ値を段相互間でパスす
る。ただし、追加のハードウェアを利用する場合、段間
でパスされるデータ値はすべて１つの処理サイクルで送
ることができる。

F.発明の効果 本発明による画素生成方法及びシステムは、所与のマ
シン・サイクルごとにほぼ任意の数の画素を同時に生成
するように一般化できる柔軟性を備えている。この画素
生成システムは、任意のマシン・サイクル中に所与の数
の画素を生成するように修正することができ、生成され
る画素の数が同じサイクル中に記憶できる数に合致する
ように構成することもできる。本発明は、必要な計算が
容易かつ迅速に実行される、画素を生成する方法を提供
する。また、本発明の画素生成システムは、高性能かつ
比較的低コストのハードウェアを提供する上に、画素が
生成されるのと同じサイクル中にメモリ・アクセス衝突
を解決する。さらに、本発明は、未記憶データを循環さ
せて後続の処理サイクルで記憶させる手段を提供するの
で、未記憶データが後のサイクルで記憶できるようにな
るまでそれらのデータの値を記憶するバッファとして働
く追加ハードウェアの必要性が軽減される。

【図面の簡単な説明】

第１図は、本発明による複数画素生成システムの一実施
例の概略構成図である。 第２図は、離散点の２次元格子上に連続線形関数を表す
問題を示すグラフである。 第３図は、本発明の方法で使用される増分の値を誘導す
るための第２図と同様なグラフである。 第４図は、第１図の絶対値論理の一実施例の概略構成図
である。 第５図は、最初の４画素位置について、ブレゼンハム・
アルゴリズムによる順次計算によって形成される誤差項
判断木の図である。 第６図は、第１図に示した増分／誤差項論理の一実施例
の概略構成図である。 第７図は、誤差項を当該の線形関数の座標を含む領域の
関数として計算する、本発明で使用する増分の値を示す
図である。 第８図は、生成中の画素データを当該の領域の関数とし
て表す、ブレゼンハム・シーケンスに課される拘束条件
を示す図である。 第９図は、第８図に示した拘束条件から生じる真理値表
である。 第10図は、第９図に示した真理値表のビット・マップで
ある。 第11a図ないし第11e図は、第１図に示した変換論理の一
実施例の概略図である。 第12図は、第１図に示したMCR論理の一実施例の概略構
成図である。 第13図は、第12図に示したMCR論理によって生成される
誤差項及び履歴ビットのシフトを、あるサイクル中に記
憶できる生成画素の数の関数として示した図である。 第14図は、MCR論理の別の実施例に基づく、誤差項ポイ
ンタの様々な値について、ベクトル生成器と変換論理に
送られるデータとの間の割当て関係を示す図である。 第15a図ないし第15d図は、MCR論理の一実施例に基づ
く、誤差項ポインタの様々な値について、特定のマシン
・サイクル中に記憶されなかったデータが後続のサイク
ルでどのように使用されるかを示す図である。 42……絶対値論理ブロック、44……増分／誤差項論理ブ
ロック、46……画素生成論理ブロック、48……変換/MCR
論理ブロック。

───────────────────────────────────────────────────── フロントページの続き (72)発明者 ヨシオ・イイダ アメリカ合衆国ニユーヨーク州レーク・カ トリン、レーク・カトリン・アパートメン ツ10‐シイー番地 (72)発明者 テレンス・ワーレス・リンドグレン アメリカ合衆国ニユーヨーク州ローゼンダ ーレ、ルート213、ボツクス120、アール・ デイー１番地 (72)発明者 タガート・ハース・ロバートソン アメリカ合衆国ニユーヨーク州アールト ン、パテイツク・マウンテン・ロード、ボ ツクス９、アール・デイー１番地

Claims (2)

【特許請求の範囲】
1. 【請求項１】画素生成システムにおいて、線形関数を定
   義しうる値の入力により、前記線形関数を近似する一連
   の画素位置データ値を所与のマシン・サイクル中に生成
   する方法であって、 前記所与のマシン・サイクルで生成しようとする画素の
   数に等しい数に設けられ、それぞれ前記マシン・サイク
   ルで生成しようとする画素のうち対応する一つの画素に
   対するデータ値を提供するベクトル生成手段に対し、ブ
   レゼンハムのアルゴリズムに従って、前記所与のマシン
   ・サイクル中で生成しようとする画素数に対応する誤差
   項を生成し、初期設定する段階と、 前記ベクトル生成手段によって、前記所与のマシン・サ
   イクル中で生成しようとする画素の数及び前記誤差項の
   符号により定められる前記誤差項に加えられる増分を算
   出することにより、前記一連の画素位置データ値を生成
   する段階と を含むことを特徴とする画素生成方法。
2. 【請求項２】ラスタ化された線に含まれる多数の画素位
   置のｘ座標及びｙ座標を前記線を定義しうる値の入力に
   より、生成する画素生成システムであって、 前記ラスタ化された線のｎ個の連続する画素のそれぞれ
   のｙ座標がゼロ以上でかつｘ座標値以下となる８分円内
   に含まれるようにラスタ化された線を定めるパラメータ
   を正規化する手段と、 ブレゼンハムのアルゴリズムに従って、前記ｎ個の連続
   する画素位置に対する誤差項を生成する手段と、 二つの値を有する増分を前記誤差項へ前記誤差項の符号
   に応じて選択して加算することにより、前記ｎ個の連続
   する画素位置に後続する画素位置をｎ個づつ並列的に生
   成する手段と、 を含む画素生成システム。