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

Abstract

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

Description

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

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

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

次に従来のラスク走査表示技術を利用してメモリを走査
し、そこに記憶された画素位置を輝かして、得られた線
を表示することができる。

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

所与のアルゴリズムを最も迅速に実行するために、アル
ゴリズムが繰り返される度に実行される計算の数、特に
乗算と除算の数を最小にする増分方法が利用される。

従来の大部分のラスク表示では、連続線を同時に１画素
ずつラスク化し、各画素を順に生成していく。それを実
行するのにおそらく最も広く使用されているアルゴリズ
ムは、ブレゼンハムの線アルゴリズムと呼ばれるもので
ある。このアルゴリズムは、多くのコンピュータ・グラ
フィックスの教科書に説明されている。たとえば、この
アルゴリズムの説明とその誘導方法が、Ｊ、Ｄ、フォリ
ー（Ｆｏｌｅｙ）とＡ、ヴアン・ダム（Ｖａｎ　Ｄａｍ
）の共著「対話型コンピュータ・グラフィックスの基礎
（Ｆｕｎｄａｍｅｎｔａｌｓ　ｏｆ　Ｉｎｔｅｒａｃｔ
ｉｖｅ　ＣｏｍｐｕｔｅｒＧｒａｐｈｉｃｓ）　Ｊ　、
アジソン・ウニズリ−出版社（１９８２年）、のＩ）ｐ
４３１−４３８に出ている。

この記載を引用により本明細書に組み込む。要約すると
、真の線を表すために様々な画素位置を選択するとき、
ブレゼンハムのアルゴリズムは、現誤差項及びそれに適
用される訂正項を決定する。

初期誤差項及び各訂正項は、その線が横切るすべてのＸ
及びｙの変位から決定される。特定の各画素について、
その画素に関連する誤差項は、その　５　一 画素が真線位置からずれている量を反映する。すなわち
、様々な画素の誤差項を利用して、どの画素がその線に
最も近いかが決定される。画素位置が順に選ばれ、後続
の画素位置を選択するためにアルゴリズムが繰り返され
るとき、以前の画素位置の選択によって生じた誤差項の
変化を補償するため、現誤差項に適切な訂正項が加えら
れる。線の終端に達して、最後の画素位置が選択される
までこのプロセスが続けられる。

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

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

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

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

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

Ｄ０問題点を解決するための手段 １つの観点によると、本発明は、単一マシン・サイクル
で複数の画素のデータ値を生成する画素生成方法を提供
する。それらのデータ値は、少なくとも１つの画素の座
標の線形関数を表し、その方法は、連続する複数の画素
のおのおのに対するブレゼンハムのアルゴリズムによる
誤差項の生成を含む。連続する画素の数は、単一マシン
・サイクル中に生成される画素の数と等しくなるように
選択される。本発明の方法は、また複数のベクトル生成
器を用いて並列に複数の画素のデータ値を生成すること
を含む。各画素のデータ値は、ブレゼンハムのアルゴリ
ズムによって計算した初期値、及び生成中の画素を考慮
に入れた初期値の増分変化の関数として決定される。本
発明の方法は、さらにベクトル生成器によって供給され
るデータ値を線形関数を表す画素位置データに変換する
こと、及びデータが生成されるマシン・サイクル中に記
憶できなかったデータが後続のサイクルで記憶すべく循
環されるような形で、上記の変換の結果生成された画素
位置データを記憶することを含みうる。

別の観点から言えば、本発明の画素生成システムは、画
素位置のｙ座標が正またはゼロであるがＸ座標以下とな
る座標系の８分円中にその関数の画素座標が含まれるよ
うに線形関数を定義する、パラメータの正規化手段を含
む。このシステムは、マタブレゼンハムのアルゴリズム
を連続する複数の画素のおのおのに適用することによっ
て初期誤差項を生成する手段、及び初期誤差項を生成す
るのに使用された連続する複数の画素位置以外の画素位
置に対応する誤差項を、単一マシン・サイクル中に並列
に生成する手段をも含む。並列画素生成手段は、さらに
選択可能な増分を各並列画素生成器の現誤差項に加える
ように構成される。この増分は２つの可能な値をもち、
どちらの値が選択されるかは、その増分が加えられる誤
差項の符号によって決まる。好ましい実施例では、この
増分は、ラスク化された緑画素座標を含む領域の関数と
して決定される。

Ｅ、実施例 本発明の対象とする問題は、関数の真の座標に最も近い
位置にある２次元格子の離散位置を選択することによっ
て連続線形関数を表すことである。

この問題を第２図にグラフで示す。線２０は、線形関数
Ｙ＝ｘ（ｄＹ／ｄｘ）の真のＸ及びｙの値を含む。この
線形関数を図の画素格子にマツプするには、線２０の座
標の真の値に最も近い位置にある画素について、（画素
の中央に位置する）整数画素座標を決定しなければなら
ない。

直交座標系は対称なので、１つの画素座標と線形関係を
示すどの関数も、第２図に示す形に見えるように正規化
される。すなわち、座標（Ｘｌ。

ｙｌ）と（ｘ２．ｙ２）の間を延びる線形関数について
、線形関数の位置を、Ｏ≦ｄｙ≦ｄｘ（ただし、ｄ　ｘ
　＝　ｘ　２　　ｘ　１　、ｄ　ｙ＝　ｙ２−ｙｌ　）
となる座標系の８分円内に制限することによって、当面
の問題が単純化できる。さらに、関数の１端点が座標系
の原点に位置するとき、表される関数は一般性を失わな
い。というのは、他の原点をもつ関数は座標（０，０）
で始まる関数の単なる変換にすぎないからである。

こうした点を考慮に入れた上で、連続線形関数を離散Ｘ
及びｙ座標をもつ格子にマツプするプロセス、たとえば
、線を画素格子にラスク化するプロセスは、その画素の
所与のＸ座標値について、２つの可能なＸ座標値のどち
らが真綿により近い画素位置を提供するかを選択する問
題に帰する。

したがって、第２図で、以前のステップすなわち（ｉ−
１）番目のステップで、画素２２が引こうとしている実
際の線により近いと判定された場合、ｉ番目のステップ
のタスクは、画素２４と２６のどちらが線２０により近
いがを決定することである。画素２４と線２０の距離が
、画素２６と線２０の間の距離よりも短い場合、画素２
４が選ばれ、そうでない場合は、画素２６が選ばれる。

第２図で、画素２４と線２ｏの距離はＳで示され、画素
２６と線２０の距離はｔで示されている。したがって、
選択すべき画素の判定は、Ｓがｔより小さいかどうかに
よる。言い換えれば、（Ｓ−ｔ）＜０の場合は、画素２
４が選ばれ、（ｓ　　ｔ）≧０の場合は、画素２６が選
ばれる。

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

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

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

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

本発明は、ブレゼンハムのアルゴリズムによって行われ
るように各位置を順に生成するのではなく、同時に複数
の画素位置を生成するものである。

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

次に、サイクルごとに現誤差項を調節する際に使用され
る増分の誘導について、概略を述べる。

第３図を参照すると、画素３２が、（ｉ−１）番目のス
テップ中に線３８の真の座標（ｘｉ、ｙｉ）により近い
画素であると判定された場合、ｉ番目のステップにおい
て、画素３４と画素３６のどちらが線３８により近いか
の判定は、画素３２の誤差項の符号によって決まる。ブ
レゼンハム・アルゴリズムと同様に、誤差項は（ｓ−ｔ
）に比例すると定義する。したがって、画素３２の誤差
項の符号が負の場合、Ｓはｔより小さく、画素３４の方
が画素３６よりも線３８に近い。逆に、画素３２の誤差
項がゼロまたは正の場合、ｔはＳ以下であり、画素３６
が選択される。

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

（ｓ−ｔ）　＝２ｓ−１（１） また引こうとしている線が任意の２点間にあり、かつ第
１の端点の方が第２の端点よりも原点に近いと仮定する
と、第３図に座標（Ｘｉ、ｙｉ）で示した点が原点にき
て、したがって（０，Ｏ）の座標値をもつように、この
線の端点をそれぞれ変換することができる。したがって
、線３８は式ｙ＝（ｄ’５’／ｄｘ）ｘによって定義さ
れる。画素３４及び３６についてはＮ　Ｘ　＝　ｐ＋　
ｎであり、したがって、Ｙ＝　（ｄ’Ｙ／ｄｘ）（ｐ＋
ｎ）である。

しかし、第３図から、Ｘ＝ｐ＋ｎの場合、ｙ＝ｑ＋ｒ＋
ｓであることは自明であり、したがって次式が得られる
。

ｑ＋ｒ十５＝（ｄｙ／ｄｘ）（Ｉ）＋ｎ）　　（２）Ｓ
について方程式（２）を解き、その結果の値を方程式（
１）に代入すると、次式が得られる。

（ｓ−ｔ）＝２ｓ−１＝２　（ｄＶ／ｄｘ）（１）＋ｎ
）−２ｑ−２ｒ−１ 方程式（３）の両辺にｄｘを掛けて、項を整理し、次に
Ｄｉ＝ｄｘ　（ｓ−ｔ）と定義すると、次式が得られる
。

Ｄ　ｉ＝２　（ｐ）（ｄｙ）　−ｑ　（ｄｘ）＋２ｎ　
（ｄｙ）　−（１＋２ｒ）ｄｘ ただし、点（ｘ　ｉ＋　Ｖ　ｉ）が格子座標系の原点に
くるように格子座標系を線３８と整合させた場合、ｐ＝
ｘｉ及びｑ＝ｙｉである。これらの値を方程式（４）に
代入すると、次式が得られる。

Ｄｉ＝２　（ｘｉ）（ｄｙ）−ｙｉ　（ｄｘ）＋２ｎ　
（ｄｙ）−（１＋２ｒ）ｄｘ となる。Ｄ（ｉ＋１）について同様の式を作り、Ｄ（ｉ
＋ｎ）の式からＤｉの式を引くと、次式が得られる。

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

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

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

一般に逐次的性格をもつ走査変換アルゴリズムを利用し
て、複数の画素を並列方式で生成しようと試みると、多
くの分野で問題が生じる。特に重要なのは、画素生成シ
ステムの初期設定に必要な処理、結果として発生する現
誤差項の解釈とその正確な画素位置への変換、及び同時
に複数の画素位置をフレーム・バッファ・メモリに書き
込もうとする時に発生し得るメモリ・モジュール・アク
セス衝突の解決である。本発明は、これらの問題のそれ
ぞれに対する解決策を提供する。ベクトル生成器を、ブ
レゼンハム・アルゴリズムにしたがって計算される誤差
項で初期設定し、サイクルごとに各ベクトル生成器につ
いて現誤差項を調節するための適切な増分を決定する。

ベクトル生成器によって計算される現誤差項の符号ビッ
トは、他の関連情報に基づいて解釈され、したがって変
換されたデータは、離散点の２次元格子上への線形関数
のマツピングを表す。本発明はさらに、所与のサイクル
中にいくつの変換データ・ビットが記憶できるかを判定
し、記憶されなかったデータ・ビットを再循環させてそ
れらを後続のサイクルで記憶できるようにする方式を提
供する。本発明のこれらの実施例については、それぞれ
本明細書の後の部分で十分に説明する。

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

各ベクトル生成器ごとに、データ値が、１サイクルで生
成される画素数の関数、またブロック４４で生成される
誤差項の関数として決定される。

本発明の画素生成システムはさらにブロック４２と４８
を含むことが好ましい。ブロック４８は、ベクトル生成
器によってもたらされたデータ値を、マツプされている
線形関数を表す画素位置データに変換する関数を含む。

ブロック４８は、また所与のマシン・サイクル中に同時
に生成されたデータ値を記憶する関数、及びメモリ・モ
ジュール・アクセス衝突を解決する方式も含むことがで
きる。

一実施例では、メモリ・アクセスの制約条件を満たす生
成データ値が、所与のマシン・サイクル中に記憶され、
記憶されなかったデータ値は、後のマシン・サイクルで
ベクトル生成器によって再生成される。別の実施例では
、メモリ・モジュール・アクセス規則を満たす生成デー
タ値が、所与のマシン・サイクル中に記憶され、残りの
生成データ値は、ベクトル生成器で再生成されずに後の
マシン・サイクルで記憶されるように指定される。

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

第１図に示す画素生成システム中の流れ順序は、以下の
ように要約できる。ユーザ指定パラメータｄｘ及びｄｙ
は絶対値論理ブロック４２が入力として受は取る。変数
ｄｘは、Ｘ座標の終端値と初端値の差であり、ｄｙはＸ
座標の終端値と初端値の差である。ｄｘ及びｄｙのそれ
ぞれの絶対値とそれらの絶対値の差がブロック４２で計
算され、次に増分／誤差項論理ブロック４４に送られる
。

入力ｄｘが入力ｄｙ以上であるかどうかを示すデータ信
号ＸＧＥＹもブロック４２で決定される。この比較の結
果に応じて、ｄＸの絶対値が変数ＰＤＸに割り当てられ
、ｄｙの絶対値が変数ＰＤＹに割り当てられ、またはこ
れらの変数中に記憶された絶対値データが交換される。

ブロック４２で捕捉され、ブロック４４に記憶される最
後の２つのデータは、入力ｄｘ及びｄｙの符号である。

ブロック４４は、ブロック４２からの様々なデータを使
って、ブロック４６の各並列ベクトル生成器について初
期誤差項を計算する。これらの初期誤差項は、第１図で
ＥＯ，Ｅｌ、Ｅ２及びＥ３として示されている。現誤差
項を各サイクルで生成された画素を反映するように調節
するために、ブロック４６の各並列ベクトル生成器につ
いて現誤差項に加えられる増分もブロック４４で計算さ
れる。変換／ＭＣＲ論理ブロック４８は、ブロック４６
の各ベクトル生成器の現誤差項の符号を、ラスク化線画
素位置の重要な座標の値の増分変化を表す２進ビツトの
列に変換する。メモリ争奪解決（ＭＣＲ）論理は、この
列のどのビットが現マシン・サイクルで記憶できるかを
決定する。記憶できるビットは、フレーム・バッファ・
メモリのＸ及びｙ位置カウンタを更新するのに使用でき
るｘｐｏｓとＹＰＯＳデータとして、プロ、ツク４８か
ら送り出される。

絶対値論理ブロック４２の一実施例が、第４図の構成図
によって概略的に示されている。第４図に示すシステム
で最初の処理サイクルが発生する前に、入力ｄｘがパイ
プライン・レジスタ５０中にある場合、絶対値論理ブロ
ック４２に含まれている上記の関数を、第４図の装置に
よって連続する３つの処理サイクルで実行するのが好都
合である。最初のサイクル中に、ｄＸがパイプライン・
レジスタ５０から線６４を介してマルチプレクサ５２に
送られ、そこから線６６を介して加算器５６に送られる
。加算器５６で、ｄＸの絶対値を計算するため、ｄＸが
、線８０を介して加算器５６に到来する信号と結合され
る。線７４上の入力信号も、加算器５６のｄｘの絶対値
に追加される。

最初の処理サイクルで、マルチプレクサ５４は、入力線
７２上の「０」レベル信号を選択する。その結果、入力
線７４上での信号の追加がゼロになり、加算器５６から
線６８を介してラッチ５８に転送された信号は、ｄＸの
絶対値を表す。

第２の処理サイクルで、ｄｙはレジスタ５０から装置を
介して送られ、ｄＸについて今説明したのと同様に、ｄ
ｙの絶対値になってラッチ６０に記憶される。第３の処
理サイクルで、ラッチ５８の出力が線７０を介してマル
チプレクサ５４に送られ、ラッチ６０の出力が線７６を
介してマルチプレクサ５２に送られる。マルチプレクサ
５４と５２はラッチ５８と６０からのこれらの出力信号
をそれぞれ線７４と６６を介して加算器５６に送る。加
算器５６へのこれらの入力は、線８０上の入力信号と組
み合わされて９、ｄＸの絶対値とｄｙの絶対値の差を表
す出力を線６８上に生成する。

この絶対値の差が、線７８を介して次の段に送られる。

加算器５６中での計算で、ｄＸ及びｄｙの大小を示す出
力信号も線８２上に生成される。この信号は、ブロック
６２の処理を制御する。変数ＸＧＥＹがゼロに等しい場
合、線８４を介してブロック６２に送られるｄｘの絶対
値が、変数ＰＤＹに割り当てられ、線８６を介してブロ
ック６２に送られるｄＹの絶対値が変数ＰＤＸに割り当
てられる。一方、ＸＧＥＹが１に等しい場合、交換は実
行されず、ｄＸ及びｄｙの絶対値がそれぞれ変数ＰＤＸ
とＰＤＹに割り当てられる。残りの変数Ｘ５ＧＮ、ｌ！
：ＹＳＧＮのデータは、レジスタ５０から線８８を介し
て得られる。

第１図に関連して上記に述べたように、増分／誤差項論
理ブロック４４は、ブロック４６の各並列ベクトル生成
器についての初期誤差項、及びサイクルごとに各ベクト
ル生成器の現誤差項を更新するのに使用される２つの増
分類を計算する。ｎ個の並列ベクトル生成器に対する初
期誤差項は、連続するｎ個の画素それぞれにブレゼンハ
ム・アルゴリズムを順次適用することによって決定され
る。すなわち、最初のｎ個の画素位置ＰＯ１Ｐ１１．．
．、Ｐ（ｎ−１）に対する誤差項は、ブレゼンハム誤差
項ＥＯ１Ｅ１１．．、、Ｅ（ｎ−１）である。ブレゼン
ハム誤差項では、連続する各誤差項Ｅ　（ｉ＋１）は、
前の誤差項Ｅｉに適切な増分を加えて計算できる。加え
られる増分値は、Ｅｉの符号によって変わる。符号が負
の場合、増分は２ｄｙである。符号が正の場合、増分は
２ｄ　　’ｙ−２ｄｘである。すなわち、ＥＯの符号が
負である場合、誤差項Ｅ１はＥＯ＋２ｄＶに等しい。

ＥＯの符号が正の場合、ＥｌはＥＯ＋２（１５’−２ｄ
ｘに等しい。ブレゼンハム・アルゴリズムではＥＯ＝２
ｄｙ−ｄｘなので、Ｅｌは４ｄ７−ｄｘまたは４ｄｙ−
３ｄｘに等しい。残りの誤差項Ｅ２ないしＥ（ｎ−１）
はそれぞれ順次同様に計算できる。こうして計算された
誤差項は、判断水を形成する。木のメンバーは、一定の
増分値によって結合されている。ｎ＝４の場合について
、その結果得られる誤差項判断水を、第５図に示す。様
々な誤差項の間でのこの増分関係が重要なのは、次の誤
差項への条件付き分岐を行なう無駄なサイクルなしに、
ハードウェアの当該段が動作できるからである。

増分／誤差項論理ブロック４４は、画素位置Ｐ（ｉ＋ｎ
）　、Ｐ　（ｉ＋２ｎ）などに対する誤差項が生成され
るとき、各並列ベクトル生成器の現誤差項を更新するの
に使用される増分をも計算する。

本発明により生成される誤差項Ｅ　（ｔ　＋ｎ）　、Ｅ
−２９＝ （ｉ＋２ｎ）などは、ブレゼンハム・アルゴリズムによ
って生成された誤差項と同様に、それぞれ、前の誤差項
に適切な増分を加えて計算できる。また、やはりブレゼ
ンハム・アルゴリズムと同様に、増分の２つの可能な値
のどちらを選択するかは、増分を加えるべき誤差項の符
号によって決まる。

増分の２つの可能な値を計算するハードウェアは、ｎ個
の並列ベクトル生成器について初期誤差項を生成するの
に使用される１つまたは複数の処理サイクル中にそれら
の増分が決定されるように構成される。そうすると、画
素生成システムの初期設定ならびにハードウェアの複雑
さを低減させるのに必要な処理サイクルの数が減少する
。

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

第６図は、ｎ＝４の場合の増分／誤差項論理ブロック４
４の実施例の概略図である。図の実施例では、４処理サ
イクルで４つの誤差項及び増分の２つの値をすべて計算
して、ハードウェアの次の段に送ることができる。絶対
値論理ブロック４２からの出力信号はすべてパイプライ
ン・レジスタ９０中にあると仮定する。最初のサイクル
で、Ｘとｙの絶対値の差がレジスタ９０から線１１５を
介して送られ、人相寄せ演算の実行によりそれに２を掛
け、線１１６を介して排他的論理和回路９２に入力とし
て送られる。排他的論理和回路９２の出力は、線１２２
を介してマルチプレクサ９６に送られる。マルチプレク
サ９６は線１２２上の信号を選択し、それを線１２４を
介して加算器１００に送る。同じサイクル中に、ＰＤＸ
がレジスタ９０から線１１５と１２０を介してマルチプ
レクサ９８に送られる。ＰＤＸはマルチプレクサ９８に
よって選択され、線１２６を介して加算器１００に送ら
れる。加算器１００は線１２４．１２６及び１２８上の
入力を結合し、その出力を誤差項レジスタ１０２に送る
。この最初のサイクルでは、加算器１００の出力は、第
１画素位置に対すルブレゼンハム誤差項である。ＰＤＸ
とシステムで使用される任意のコマンド・ワードも、こ
の第１サイクル中にレジスタ９０から他のハードウェア
段に送ることができる。第２のサイクル中に、ＥＯがレ
ジスタ１０２から線１３４を介してマルチプレクサ１０
４に送られ、また線１３２を介してマルチプレクサ９８
に送られる。ＥＯはマルチプレクサ９８から線１２６を
介して加算器１００に送られる。第１サイクルと同様に
、ｄＸとｄｙの絶対値の差に２が掛けられて、排他的論
理和回路９２に送られ、その出力がマルチプレクサ９６
に送られる。ＰＤＹはレジスタ９０から線１１５を介し
て送られ、２を掛けら耗、線１１８を介してマルチプレ
クサ９６に入力として送られる。誤差項ＥＯの符号に応
じて、マルチプレクサ９６は、線１１８と１２２上の入
力のどちらかを選択し、選択された信号を加算器１００
に送る。線１１８と１２２上の信号は、ブレゼンノ１ム
誤差項を計算するための増分を表す。すなわち、線１２
６上の入力がＥＯのとき、加算器１００の出力は次の誤
差項Ｅ１である。Ｅｌは線１３０を介してレジスタ１０
２に送られ、また線１４０を介してマルチプレクサ１０
６に送られる。この第２サイクル中に、ＥＯとＥｌがそ
れぞれマルチプレクサ１０４と１０６によって次のハー
ドウェア段に送られる。

また第２サイクル中に、ＥＯに４が掛けられ、線１４２
を介してマルチプレクサ１０８と１１０に送られる。Ｅ
ｌに２が掛けられ、線１３８を介してマルチプレクサ１
０８と１１０に送られる。排他的論理和回路９２の出力
は加算器９４に送られ、加算器９４の出力は２ＰＤＹ−
２ＰＤＸである。

この式に４が掛けられ、線１４４を介してマルチプレク
サ１０８に送られる。ＰＤＹは、レジスタ９０から線１
１５を介して送り出される他に、８を掛けられて、線１
４６を介してマルチプレクサ１１０にも送られる。誤差
項ＥＯとＥｌの符号は、それぞれマルチプレクサ１０８
と１１０に送られ、他の入力と結合されて、増分の２つ
の値１１と■２を決定する。最初の増分値はマルチプレ
クサ１０８中で決定され、線１４８を介してラッチ１１
２に送られる。第２の増分は、マルチプレクサ１１０中
で決定され、同様に線１５０を介してラッチ１１４に送
られる。

第３の処理サイクルでは、誤差項Ｅ１について説明した
のと同様にして、誤差項Ｅ２が生成される。Ｅ２は線１
３６とマルチプレクサ１０４を介して次のハードウェア
段に送られる。同じサイクルで、増分■１が線１５２と
マルチプレクサ１０６を介して次の段に送られる。最後
のサイクルでは、誤差項Ｅ１について説明したのと同様
にして、誤差項Ｅ３が生成される。Ｅ３は線１３６とマ
ル＝３４− チプレクサ１０４を介して装置から送り出される。

この最後のサイクルで、増分■２も、線１５４とマルチ
プレクサ１０６を介して次のハードウェア段に送られる
。

マルチプレクサ１０８と１１０で決定される増分は、Ｅ
ＯとＥｌのそれぞれの符号に応じて変わる。これらの符
号ビットは、線形関数の座標を含む領域を決定するもの
である。第６図の実施例では、マルチプレクサ１０８に
よって決定される増分は、（８ＰＤＹ−８ＰＤＸ）（／
ｄ）（／ｆ）＋２Ｅ１　（／ｄ）（ｆ）＋４ＥＯ（ｄ）
（／ｆ）＋２Ｅ１　（ｄ）（ｆ）で表すことができる。

ただし、ｄとｆはそれぞれＥＯとＥｌの符号ビットであ
り、／ｄと／ｆはそれぞれＶ′否定ｄ“及び”否定ｆ゛
を意味する。マルチプレクサ１１０で決定される増分も
同様に、２Ｅ１　（／ｄ）（／ｆ）＋４ＥＯ（／ｄ）（
ｆ）＋２Ｅ１　（ｄ）（／ｆ）＋８ＰＤＹ（ｄ）（ｆ）
で表すことができる。ビットｄとｆによって復号される
領域とその様々な値に対応する増分を第７図に示す。ピ
ッ）ｄとｆはそれぞれＥＯとＥｌの符号を表すのて、そ
れらのビットは、これら２つの誤差項が段から段に送ら
れるとき、ＥＯとＥｌの最上位ビットとして後のハード
ウェア段に自動的に送られる。

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

この構成では、１の２進ビツトは、対応する画素座標の
位置の上昇をも示す。

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

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

第８図に示したｎ＝４の場合、領域０に含まれるすべて
の線は、０と０．２５の間の勾配をもつ。

領域１については、勾配は０．２５から０．５の範囲で
ある。領域２では、勾配は０．５から０゜７５の範囲で
あり、領域３では、勾配は０．７５から１．０の範囲で
ある。

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

領域ＯのＰＯをｂｏで表し、領域１のＰＯをＣＯで、領
域２のＰＯをｄｏで、領域３のＰＯをｅＯで表す場合、
領域Ｏの４ビツトのブレゼンハム・シーケンスはＨ３，
Ｈ２，Ｈｌ、ｂｏとして表すことができる。ただし、Ｈ
ｌ、Ｈ２及びＨ３はｂｏの発生前の履歴ビットを表す。

他の領域のブレゼンハム・シーケンスは、領域１でｂＯ
をＣＯに、領域２でｂＯをｄｏに、領域３でｂｏをｅＯ
に置き換えることによって同様に表すことができる。」
二連の拘束条件を適用する場合、すなわち、ＳＯがＯの
ときシーケンスのｒ＋１個のビットが１でなければなら
ず、ＳＯが１のときｒ個のビットが１でなければならな
い場合、それぞれの領域に対して第９図に示した真理値
表が作成される。

領域Ｏ及び１では、２つのブレゼンハム・グループが値
が１のビットを最高１個しかもてないという追加の拘束
条件が課される。したがって、ブレゼンハム・シーケン
ス０１１０．１１００及び００１１は領域Ｏ及び１では
有効ではない。さらに、領域２及び３では、２つのブレ
ゼンハム・グループは、値が１のビットを最低１個もた
なければならない。したがって、ブレゼンハム・シーケ
ンス００１１．１００１及び１１００は領域２及び３で
は有効ではない。これらの追加の拘束条件が第９図に示
した真理値表に課される場合、それぞれの領域について
その結果書られるパラメータ値の組を、第１０図に示す
ビット・マツプに変換することができる（第９図及び第
１０図で、「Ｄ」は関連するビットについて「どちらで
もよい」状態を表し、本明細書全体を通じて誤差項ＥＯ
の符号を表すために使用するｒｄＪとは無関係なことを
了解されたい）。

第１０図に示すビット・マツプのそれぞれについて、Ｓ
ＯとＨｌ−Ｈ３によってｂＯｌｃＯｌｄＯ及びｅＯを表
すプール方程式が生成できる。すなわち、 領域Ｏでは、 ｂｏ＝／Ｈ３＆／Ｈ２＆／Ｈ１＆／Ｓｏ　；領域１では
、 ｃｏ＝／Ｈ１＆／ＳＯ＋／Ｈ３＆／Ｈ２＆／Ｈ１；領域
２では、 ｄｏ＝／Ｈ１＋／Ｈ３＆／ＳＯ＋／Ｈ２＆／Ｓｏ　；領
域３では、 ｅｏ＝／　（Ｈ３＆Ｈ２＆Ｈ１＆ＳＯ）さらに、ＰＯは
ｂｏ＋　ｃｏｔ　ｄｏｌｅｏ及び符号ビットｄとｆによ
って以下のように表すことができる。

ＰＯ＝ｂＯ＆ｄ＆ｆ＋ｃＯ＆ｄ＆／ｆ＋ｄ。

＆　／　ｄ　＆　ｆ　＋　ｅ　Ｏ＆　／　ｄ　＆　／　
ｆ　。

上記の各方程式中で、“＋”はＯＲ演算を示し、°°＆
“°はＡＮＤ動作を示し、“／“°はＮＯＴを示す。

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

この種の組み合わせたプール論理関数とカスケード論理
関数をもたらす変換論理の構成を、領域Ｏ−３のおのお
のについて第１１ａ図ないし第１ｉｄ図に示す。すべて
の領域に対する論理がどのように組み合わされるかを第
１ｉｅ図に示す。第１１ａ図ないし第１ｉｄ図のおのお
のにおいて、各論理ブロックの第２のプール方程式が、
履歴ビットを１つの位置だけシフトし、新しい履歴ビッ
トをそのブロックの第１のプール式に代入することによ
って誘導される。たとえば、ｂｌの方程式は、ｂＯの方
程式において、Ｈ３にＨ２を、Ｈ２にＨｌを、ＨｌにＳ
Ｏを、ＳＯにＳｌを代入することによって誘導される。

関連するプール代数を実行し、不必要な項を除去すると
、結果として、ｂｌの方程式が得られる。

第１２図の構成図は、画素生成ブロック４６と第１図に
示した変換／ＭＣＲ論理ブロック４８を組み合わせるた
めの１つの構成の概略図である。

並列ベクトル生成器１６０はそれぞれ、増分の２つの可
能な値の１つを選択するためのマルチプレクサ１６２を
含む。その値はレジスタ１６４と１６６に記憶されてい
る。加算器１７０中で、各ベクトル生成器についてマル
チプレクサ１６２によって選ばれた増分が、その生成器
の現誤差項に加えられる。現誤差項はレジスタ１６８に
記憶されている。レジスタ１６８に記憶された誤差項の
符号ビットはｎビット信号として変換論理回路１７２に
送られ、そこで、その信号はレジスタ／マルチプレクサ
１７４からの（ｎ−１）ビット履歴信号及びレジスタ１
７６からの２ビット領域信号と組み合わされる。変換論
理回路１７２中でこれらの信号を組み合わせて得られた
真のブレゼンハム・シーケンスが、メモリ争奪解決論理
回路１７８に送られる。この論理回路の機能については
後で説明する。変換論理回路１７２に必要な履歴ビット
は、Ｈ１＝／ｄ１）（２＝／ｆ１及びＨ３＝／ｄとなる
ようにレジスタ／マルチプレクサ１７４によって初期設
定される。このようにして、履歴ビットＨ１−Ｈ３は、
変換論理回路１７２内の論理関数が実行されるとき正確
な最初の４つの画素を与えるように初期設定される。初
期サイクルの後、更新された履歴ビットは、履歴ビット
経路指定論理回路１８０からレジスタ１７４を介して変
換論理回路１７２が受は取る。

ＭＣＲ論理回路１７８の機能は、単一マシン・サイクル
中に複数の画素をメモリ・デバイスに書き込まなければ
ならないときに発生するメモリ争奪問題を解決すること
である。メモリ争奪は通常、フレーム・バッファ制限の
状況で起こる。メモリ争奪が起こるのは、２つ以上の画
素をフレーム・バッファに書き込むために、またはフレ
ーム・バッファのメモリ構成及びメモリ・アドレスにア
クセスするための規則からメモリ・アクセス衝突が発生
したために、複数のメモリ・モジュールにアクセスする
ことが必要になるためである。ＭＣＲ論理回路１７８は
、生成された画素を特定のサイクル中に衝突なしにいく
つ書き込めるかを決定し、書き込めない画素を再循環さ
せることによって、メモリ争奪を解決する。特定のサイ
クルで記憶できない画素の情報を循環させることにより
、メモリ争奪問題が、各処理サイクルごとに「オン・ザ
・フライ方式」で解決される。したがって、任意の所与
のサイクル中に記憶できる画素の最大数が生成され、画
素生成システムによって記憶される。

さらに、そのように構成されたＭＣＲＣ上メモ路を用い
ると、画素生成システムの動作を画素記憶システムの動
作と調整するために追加の制御ハードウェアが必要でな
くなる。ＭＣＲ論理回路１７８は、任意の所与のサイク
ルでＯないしｎ個の画素がデータ・フローまたはデータ
保全性を乱さずに生成されるように、画素生成の自己最
適化を行なう。各サイクル中に記憶される画素の実際の
数が、制御機構１８２に含まれる長さカウンタから差し
引かれ、長さカウンタの値がゼロになるまで４６一 その処理が継続される。

第１２図に示す実施例では、メモリ・デバイスのアクセ
ス規則を満たす生成画素位置は、それらが生成される処
理サイクル中にそこに記憶される。

記憶できない画素は、以後の処理サイクルで再生成され
、そうしてもメモリ・アクセス衝突が起こらないときに
、メモリ・デバイスに記憶される。

第１２図で、記憶できる画素は、画素ＰＯ−ＭとしてＭ
ＣＲ論理回路１７８から送り出される。ただし、Ｍ＋１
は記憶されている画素の数に等しい。

所与のマシン・サイクル中に記憶できない画素について
は、関連する誤差項が、誤差項経路指定論理回路１８４
を介して対応するベクトル生成器の現誤差項レジスタ１
６８に戻る。次の処理サイクルで、その誤差項は、他の
レジスタ１６８中の誤差項と共に再処理される。歴史ビ
ット経路指定論理回路１８０は記憶されていない画素の
履歴ビットも再循環させる。ＭＣＲ論理回路１７８から
の当該の制御信号が、誤差項経路指定論理回路１８４と
履歴ビット経路指定論理回路１８０に、次の処理サイク
ルで古いデータと新しいデータのどちらを使用すべきか
を示す。次の処理サイクルで使用される誤差項及び履歴
ビットを、現処理サイクル中に記憶できる画素の数の関
数として、第１３図に示す。したがって、第１３図は、
未記憶データがどのように再生成されて後のサイクルで
記憶されるかを示す。

第１２図に示す実施例に代わる別の実施例では、変換論
理に必要な情報だけがサイクルごとにシャツフルされる
。したがって、誤差項自体ではなく、誤差項の符号ビッ
トだけが送られる。歴史ビットは第１２図に示したのと
同じ方式で再循環される。

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

２ビツト・ポインタの１０進値によって、次の処理サイ
クルでどのベクトル生成器が誤差項ＥＯを計算するかが
決まる。たとえば、ポインタが２進数０１（１０進数１
）に設定されている場合、ベクトル生成器Ｎｏ、１が次
のサイクルで誤差項ＥＯを計算する。したがって、ベク
トル生成器Ｎｏ、１の誤差項の符号ビットが、ＳＯとし
て変換論理に送られ、ベクトル生成器Ｎｏ、２の符号ビ
ットが８１として送られ、ベクトル生成器Ｎｏ。

３の符号ビットが８２として送られ、ベクトル生成器Ｎ
ｏ、Ｏの符号ビットが８３として送られる。

第１４図に、ポインタの様々な値に対してＳＯ−８３の
それぞれにどの生成器の符号ビットが指定されるかを示
す。

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

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

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

【図面の簡単な説明】

第１図は、本発明による複数画素生成システムの一実施
例の概略構成図である。 第２図は、離散点の２次元格子上に連続線形関数を表す
問題を示すグラフである。 第３図は、本発明の方法で使用される増分の値を誘導す
るための第２図と同様なグラフである。 第４図は、第１図の絶対値論理の一実施例の概略構成図
である。 第５図は、最初の４画素位置について、ブレゼンハム・
アルゴリズムによる順次計算によって形成される誤差項
判断水の図である。 第６図は、第１図に示した増分／誤差項論理の一実施例
の概略構成図である。 第７図は、誤差項を当該の線形関数の座標を含む領域の
関数として計算する、本発明で使用する増分の値を示す
図である。 第８図は、生成中の画素データを当該の領域の関数とし
て表す、ブレゼンハム・シーケンスに課される拘束条件
を示す図である。 第９図は、第８図に示した拘束条件から生じる真理値表
である。 第１０図は、第９図に示した真理値表のビット・マツプ
である。 第１１ａ図ないし第１１ｅ図は、第１図に示した変換論
理の一実施例の概略図である。 第１２図は、第１図に示したＭＣＲ論理の一実施例の概
略構成図である。 第１３図は、第１２図に示したＭＣＲ論理によって生成
される誤差項及び履歴ビットのシフトを、あるサイクル
中に記憶できる生成画素の数の関数として示した図であ
る。 第１４図は、ＭＣＲ論理の別の実施例に基づく、誤差項
ポインタの様々な値について、ベクトル生成器と変換論
理に送られるデータとの間の割当て関係を示す図である
。 第１５ａ図ないし第１５ｄ図は、ＭＣＲ論理の一実施例
に基づく、誤差項ポインタの様々な値にツイテ、特定の
マシン・サイクル中に記憶サレナかったデータが後続の
サイクルでどのように使用されるかを示す図である。 ４２・・・・絶対値論理ブロック、４４・・・・増分／
誤差項論理ブロック、４６・・・・画素生成論理プロ・
ツク、４８・・・・変換／ＭＣＲ論理プロ・ツク。 出願人　　インターナショナル・ビジネス・マシーンズ
・コーポレーション 代理人　　弁理士　　山　　本　　仁　　朗（外１名） ＝５４− 篤　１　口 Ｘ、Ｙ佐置災耕 笛２　口 斌３０ ○　　　　−〜　　　　０ Ｌｌ　　　　　　ｕＪ　　　　　　Ｌｌ　　　　　　ｕ
Ｊ領殊゛Ｏ＠珠　１ ′応１１０図 篤１１ｃ圀 第　１１ｄ口

Claims (3)

【特許請求の範囲】
1. （１）単一マシン・サイクル中に生成すべき一連の画素
   の各々について、ブレゼンハムのアルゴリズムに従って
   誤差項を生じ、上記一連の画素にそれぞれ対応づけられ
   ていて並列的に接続された複数のベクトル生成手段によ
   って、上記一連の画素の数及び上記誤差項の関数として
   定められるデータ値を個々の画素に関して生じることを
   特徴とする画素生成方法。
2. （２）上記一連の画素に関するデータ値を、少なくとも
   １つの画素の線形関数を表わす画素位置データに変換す
   ることを含む特許請求の範囲第（１）項記載の画素生成
   方法。
3. （３）ラスター化される線のｎ個（ｎは２以上の整数）
   の画素位置について、第１の８分円において各画素位置
   のｙ座標が０以上でかつｘ座標以下になるように、可能
   な画素座標の格子を複数の８分円に分割すると共に、上
   記第１の８分円をｎ個の領域に分割する手段と、 上記線の画素座標が上記第１の８分円に含まれるように
   、上記線を定めるパラメータを正規化する手段と、 一連のｎ個の画素の各々にブレゼンハムのアルゴリズム
   を適用して、最初のｎ個の画素位置に関する誤差項を生
   じる手段と、 単一マシン・サイクル中に、上記最初のｎ個の画素位置
   に関する誤差項の各々に、それらの符号に応じて２つの
   可能な値のうちから選択される一方の値を有する増分を
   加えて、上記最初のｎ個の画素位置以外の画素位置に関
   するｎ個の誤差項を並列的に生じる手段と、 を有し、上記ｎ個の画素位置のｘ及びｙ座標を生じる画
   素生成システム。