JPH0789381B2 - ピクセル値補間表示方法 - Google Patents

Description

【発明の詳細な説明】 〔発明の技術分野〕 本発明はコンピュータ・グラフィクス等に用いることが
できる補間方法に関する。

〔従来技術およびその問題点〕

コンピュータ支援エンジニアリング（CAE）ワークステ
ーションの図形処理端末装置は技術者が設計を行なう際
に適切に支援しようとすれば物体の性質に合わせて目に
見える正確な指示を発生しなければならない。代表的な
性質には構造、形状、外観、温度勾配、および応力勾配
がある。これらの映像を理解しやすく処理しやすい形で
発生するのがCAEワークステーションの図形処理サブシ
ステムの機能である。

映像合成の大部分の方法では、映像は物体の表面を多角
形に細分し、各項点の色と明度（intensity）の値を計
算し、結果をフレーム・バッファに入れ、一方色の値を
多角形全体に補間する（グーロー・シェイディングGour
aud shading）ことによって作られる。色の情報は光源
データから計算するか、あるいは選択された性質を解析
することによって計算することができる。

各多角形上での座標および色（または明度）の値の補間
は迅速に且つ正確に行わなければならない。この操作は
多角形の辺の各量子化点（ピクセル）の座標値および色
値を補間し、それに続いて辺から辺への補間を行なうこ
とによって塗りつぶし線（fill line）を作る。Ｚバッ
ファを用いて隠面消去を行なわなければならない場合に
は、各ピクセルの深さの値（Ｚ）も計算しなければなら
ない。更に、各色の成分は表面または一組の表面上で独
立に変化し得るから、赤、緑、および青の強さに対する
値は独立に補間しなければならない。したがって、汎用
図形処理システムでは、グーロー・シェイディングおよ
び補間されたＺ値を用いて多角形を描くとき、最小６つ
の異なるピクセル値（Ｘ、Ｙ、Ｚ、赤、緑、および青）
を独立に計算しなければならない。

ピクセルとその値を発生することは昔から映像発生の隘
路であった。何故なら対話的処理用の速さで映像を作る
には毎秒数百万ピクセルを描かなければならないからで
ある。隘路を緩和するにはハードウェアで実現でき且つ
６個のパラメータを含むように拡張できる補間アルゴリ
ムズが必要である。プロセスのオーバーラップを最大に
して費用を最小にするには、パイプラインをなす多角形
のすべての要素を単一のチップに入れることが望まし
い。

次に記す開示は最大毎秒2000万ピクセルの割合で６個の
パラメータに関して補間による多角形塗りつぶしを行な
うことができる補間装置のシングル・チップVLSI構成
（多角形描画チップ（Polygon Rendering Chip）、また
はPRCと呼ぶ）の一部について述べる。PRCの入力は多角
形項点データ（16ビットの整数の形でＸ、Ｙ、Ｚ、Ｒ、
Ｇ、Ｂ）と外部のデュアル・ポートRAMから取り出した
辺接続情報から構成される。その出力は各ピクセルに対
するＸ、Ｙ、Ｚ、Ｒ、Ｇ、Ｂのデータである。PRCは200
0を越える凸辺、凹辺、および／または交差辺を持つシ
ェイディング多角形の塗りつぶしを行なうことができ、
2¹⁵×2¹⁵ピクセルのアドレス空間を備えている。PRCに
使用する補間アルゴリズムはIBM Systems Journal、vo
l.4 No.1、1965でBresenhamが説明している描線（line
−drawing）アルゴリズムに関係している。残念ながらB
resenhamのアルゴリズムには補間されるべき線の傾斜に
関して制限がある。このような制限が無く、また速さと
ハードウェアの実現しやすさのため、整数計算を使用し
ていることが、そのVLSI構成とともに、ここに述べる新
しいアルゴリズムのとりわけ顕著な特徴である。

或る初期のいくつかの描線補間アルゴリズムについて簡
単に考察しよう。各々のアルゴリズムをPascal風のプロ
グラムとして示すことにする。他に特に注記しないかぎ
り、Ｘは主軸であり且つその値は増加すると仮定する。
（Ｘ、Ｙを交換することにより、および／またはＸ軸お
よび／またはＹ軸について鏡像をとることにより、ベク
トルはすべてこの仮定内で描くことができることがわか
る。）XsおよびYsはＸおよびＹの始めの値である。Xeお
よびYeはＸおよびＹの終りの値である。

ディジタル微分解析機 従来技術の一つはディジタル微分解析（DDA）である。D
DAはＸの各値に対して式Ｙ＝Ｍ×Ｘ＋Ｃ（乗算が必要）
を解かずに線のＹ値を計算することができる。これは線
の微分、すなわち傾斜（Ｍ）を、定数（Ye−Ys）／（Xe
−Xs）として計算することにより行われる。一旦Ｍが計
算されると、（X,Y）の点列を、Ｘを１だけ増しＭをＹ
に加えることを繰返して次々発生することができる。Ｙ
値については、すべて更に最も近い整数に丸める必要が
あるが、これは始めのＹ値に0.5を加え、得られたＹに
切捨てを施すことにより容易に達成される。線の終りを
検出するため、Xe−Xsを初期値にとるダウン・カウンタ
も必要である。上記をプログラムの形で要約すれば次の
ようになる。

PROCEDURE DDA1（Xs,Xe,Ys,Ye:INTEGER）； VAR M,Y:REAL; N,X:INTEGER; BEGIN （＊設定＊） X:＝Xs; Y:＝Ys＋0.5; M:＝（Ye−Ys）／（Xe−Xs）； N:＝（（Xe−Xs）； （＊補間＊） PLOT（X,INT（Ｙ））； WHILE N＜＞０ DO BEGIN X:＝Ｘ＋1; Y:＝Ｙ＋M; N:＝Ｎ−1; PLOT（X,INT（Ｙ））； END; END; DDAを使用するにあたっての主な困難はＭを得るために
最初に割算を行なうことと、ＭおよびＹに対して実数つ
まり小数の２進数を使用しなければならないことであ
る。割算が一般に遅いばかりでなく、このやり方では切
捨て誤差を生じやすい。ＭおよびＹの小数部の精度は、
引かれる線が終点に正しくぶつかることを保証するため
少なくとも画面精度に等しくなければならず、或る経験
的データによれば、両端点間にすべての点を正しく描く
のに必要な精度は画面精度の少なくとも２倍でなければ
ならないことがわかっている。

Bresenhamのアルゴリズム DDAは整数部と小数部に分割することができる。整数部
には、カウント値Ｎ、Ｘの値、およびＹの値の整数部が
含まれる。小数部にはＹの値の小数部だけ、および傾斜
Ｍの値全体が含まれる。最初にＸを主軸と仮定したの
で、傾斜（Ye−Ys）／（Xe−Xs）は常に１以下である。

小数値と整数値とを連絡する唯一のものはＹ小数部から
Ｙ整数部への桁上げである。傾斜ＭをＹ小数部に加える
ことにより生じた整数値がＹ整数部に移されるかぎり、
整数部と分数部とは独立に取扱うことができる。これは
Ｙ小数部から１を引き、Ｙ小数部が１以上のときはＹ整
数部に１を加えることにより行うことができる。０以上
という条件が成立するか否かについての比較をすること
（つまり符号ビットのチェック）は通常、１以上という
条件が成立するか否かについての比較をすることにより
容易であるから、始めのＹ小数部から１を引いておい
て、０との比較を行うことができる。YfがＹ小数部を表
し、YiがＹ整数部を表わすものとすれば、プログラムは
次のようになる。

PROCEDURE DDA2（Xs,Xe,Ys,Ye:INTEGER）； VAR M,Yf:REAL; N,X,Yi:INTEGER; BEGIN （＊設定＊） X:＝Xs; Yi:＝Ys; Yf:＝−0.5; M:＝（Ye−Ys）／（Xe−Xs）； N:＝（Xe−Xs）； （＊補間＊） PLOT（X,Yi）； WHILE N＜＞０ DO BEGIN X:X＋1; Yf:＝Yf＋M; IF Yf＞＝０ THEN BEGIN Yf:＝Yf−1; Yi:＝Yi＋1; END; N:＝Ｎ−1; PLOT（X,Yi）； END; END; 小数部の値はそれ自身の方程式系の外では全く使用され
ないから、これらの値はすべて定数２＊（Xe−Xs）倍し
て整数化することができる。０以上の状態であるか否か
についての比較の理論値としての結果だけが送り出され
る。この結果最初の割算が無くなり、すべての小数変数
が整数に変換される。これは２を掛ける以外の乗算を追
加することなく行うことができ、２の乗算は左シフトに
より簡単に行うことができる。これでプログラムは次の
ようになる。

PROCEDURE BRESENHAM（Xs,Xe,Ys,Ye:INTEGER）； VAR M,Yf, N,X,Yi:INTEGER; BEGIN （＊設定＊） X:＝Xs; Yi:＝Ys; Yf:＝−（Xe−Xs）； M:＝２＊（Ye−Ys）； N:（Xe−Xs）； （＊補間＊） PLOT（X,Yi）； WHILE N＜＞０ DO BEGIN X:＝Ｘ＋1; Yf:＝Yf＋M; IF Yf＞＝０ THEN BEGIN Yf:＝Yf−２＊（Xe−Xs）； Yi:＝Yi＋1; END; N:＝Ｎ−1; PLOT（X,Yi）； END; END; 上のプログラムはBresenhamの原論文に提示された規則
と実質的に同じである。

BresenhamのアルゴリズムをＸとＹとだけに使用すると
きは、主軸は常に最大変化分（dalta）を持つ軸と定義
すべきであり、こうすれば主軸に沿う各ピクセルに対し
て点が確実にプロットされることになる。Ｚ、赤、緑ま
たは青の軸に沿って補間するときは、Ｘ（またはＹ）軸
をたとえその変化分がΔＺ、Δ赤、Δ緑、あるいはΔ青
より小さくても、主軸のままにしておくべきである。こ
れは緑がＸ−Ｙ平面に投影されているからである。たと
えば、数ピクセルだけを描くときにＺ軸に沿って数千の
ステップを行なうのは馬鹿げたことになる。このこと
は、たとえば、Ｘ−Ｚ平面内の線の傾斜が１より大きく
なることがあり、この状態ではBresenhamのアルゴリズ
ムが使用できないことを意味している。

多くの人々がＺ、赤、緑、および青の補間を実現するの
に使用した手法はDDAに戻ることであり、DDAでは傾斜が
０と１との間にあることは必要ではない。彼等はDDAか
ら生ずるＺ、赤、緑、および青の値のわずかな誤差はＸ
およびＹの誤差ほど重大ではないと主張している。

〔発明の目的〕

本発明は上述した従来技術の問題点を解消し、高速かつ
汎用性のある補間方法を提供することを目的とする。

〔発明の概要〕

本発明の一実施例によれば、補間される関数の傾斜の整
数部と小数部をともにあらかじ計算しておく。インクリ
メントすべき従属変数の出発値の小数部とインクリメン
トを生じさせる傾斜の小数値は各々整数演算ができる大
きさになるように定数倍しておく。従属変数の出発値の
この定数倍された小数部はある定数だけオフセットされ
て「０以上であるか」の比較で検出されるキャリーの発
生が起るようにされる。キャリーが発生すれば従属変数
の（定数倍されていない）整数部が傾斜の（定数倍され
ていない）整数部の大きさだけインクリメントされる。

更に、従属変数の整数部と定数倍した小数部の組につい
ての２対の同時整数加算のうちの一方が選択されて行わ
れる。これらの対の一方は定数倍した小数部からのキャ
リーが生じなかったときに選択される。他方の対はキャ
リーが生じたときに選択される。選択された加算対によ
って生じた値はパイプライン内の次の段に送られ、従属
変数の整数と定数倍した小数部を実際に更新する。

〔実施例〕

Bresenhamの変換と同様であって、傾斜を０と１との間
にする必要のない変換を見つけることができる。傾斜が
制限されなければ、傾斜は丁度前述のＹ値の場合のよう
に分けて処理しなければならない整数部と小数部とを備
えることになる。DDA1を修正して、次のようにする。

PROCEDURE DDA3（Xs,Xe,Zs,Ze:INTEGER） VAR Mf,Zf,:REAL; N,Mi,X,Zi:INTEGER; BEGIN （＊設定＊） X:＝Xs; Zi:＝Zs; Zf:＝−0.5; Mi:＝（Ze−Zs）DIV（Xe−Xs）； Mf:＝FRACT（（Ze−Zs）／（Xe−Xs））； N:＝（Xe−Xs）； （＊補間＊） PLOT（X,Zi）； WHILE N＜＞０ DO BEGIN X:＝Ｘ＋1; Zi:＝Zi＋Mi; Zf:＝Zf＋Mf; IF Zf＞＝０ THEN BEGIN Zf:Zf−1; Zi:Zi＋1; END; N:＝Ｎ−1; PLOT（X,Zi）； END; END; DDA2の場合のように、小数部はすべて定数２×（Xe−X
s）倍することによって整数に変えることができる。下
に示す複数軸補間（Multiple−Axis Interpolator）は
Ｘが主軸を表わし、Ｚが他の軸を表わすと仮定してい
る。

B MOD A＝Ａ＊FRACT（B/A）であることに注意するこ
と。

PROCEDURE MAI1（Xs,Xe,Zs,Ze:INTEGER） VAR Mf,Zf, N,Mi,X,Zi:INTEGER; BEGIN （＊設定＊） X:＝Xs; Zi:＝Zs; Zf:＝−（Xe−Xs）； Mi:＝（Ze−Zs）DIV（Xe−Xs）； Mf:＝２＊（（Ze−Zs）MOD（Xe−Xs））； N:＝（Xe−Xs）； （＊補間＊） PLOT（X,Zi）； WHILE N＜＞０ DO BEGIN X:X＋1; Zi:＝Zi＋Mi; Zf:＝Zf＋Mf; IF Zf＞＝０ THEN BEGIN Zf:＝Zf−２＊（Xe−Xs）； Zi:＝Zi＋1; END; N:＝Ｎ−1; PLOT（X,Zi）； END; END; 一見して、MAIはDDAに劣っているかのように見える。MA
IはDIVとMOD関数があるが、DDAには一つの加算があるだ
けである。しかしながら、MAIのDIVはDDAの実数割算よ
りはるかに簡単な整数割算である。MOD関数について
は、この値の上の行で行われたDIVから得られる単なる
剰余であるから、そのために余分なコストはかからな
い。整数剰余は捨てられないから、DDAの場合のような
切捨て誤差は存在しない。ハードウェア構成において
は、ZiおよびZfの加算に必要な加算器が必要とするビッ
ト数はDDAでの実数値Ｚに必要なビット数と同じか、少
い。

演算はすべて簡単な整数算術を使用するから、必要な分
解能を精密に指定することができる。必要な分解能は変
化分項（Xe−XsとZe−Zs）の分解能により決まるが、Ｘ
またはＺの範囲のビット数より１ビット多く必要であ
る。たとえば、所要のＸまたはＺの範囲が０から32767
までであれば、情報の損失が無いようにするため16ビッ
トの分解能が必要である。上のアルゴリズムMAI1は設定
セグメントの部分と補間ループの計算の部分を再構成し
て、定数Mf2をあらかじめ計算することにより、ハード
ウェアで構成した場合、１クロック時間あたり１ピクセ
ルをプロットするように変更することができる。

PROCEDURE MAI2（Xs,Xe,Zs,Ze:INTEGER）； VAR Mf,Zf, N,Mi,X,Zi:INTEGER; BEGIN （＊設定＊） X:＝Xs; Zi:＝Zs; Mi:＝（Ze−Zs）DIV（Xe−Xs）； Mf:＝２＊（（Ze−Zs）MOD（Xe−Xs））； Mf2:＝Mf−２＊（Xe−Xs）； Zf:＝−（Xe−Xs）＋Mf; N:＝（Xe−Xs）； （＊補間＊） PLOT（X,Zi）； WHILE N＜＞０ DO BEGIN X:X＋1; IF Zf＞＝０ THEN BEGIN Zf:＝Zf＋Mf2; Zi:＝Zi＋Mi＋1; END ELSE BEGIN Zf:＝Zf＋Mf; Zi:＝Zi＋Mi; END; N:＝Ｎ−1; PLOT（X,Zi）； END; END; これにより補間ループは１軸あたり、一つはZf用、一つ
はZi用の二つの加算器を使用すれば、１クロックにつき
１ピクセルの割合で数値を発生することができる。設定
から補間ループまでのデータ・フローは一方向であるか
ら、別々の回路群を用いることにより二つのルーチンを
容易にパイプライン化することができる。設定手順全体
は、パラメータあたり一つの加算器を用いシフト・アン
ド・アド形式の除算を行うことによって20〜34クロック
で行うことができる。各種データによれば、典型的な塗
りつぶし（fill）ベクトル長は約30ピクセルであるか
ら、セットアップとピクセル描画との速さは良くつり合
っている。したがって特別な除算ハードウェアの必要性
はほとんど無い。補間に必要なある関係の数値（「短期
定数」）はPRCの設定機械で計算される。ピクセル描画
は補間機械で行われる。

PRCでは６個の補間機械が使用される。ＸまたはＹの一
つは常にアップダウン・カウンタを用いて処理すること
ができるが、どのパラメータがどこにあるかを常に知っ
ておくのに余分の情報記録が必要となり、チップのルー
ティングが一層複雑になる。他の軸と平行して走る補間
機械のコピーをもう一つ追加するのがはるかに簡単な解
決策である。

多角形塗りつぶし機能 今度は第１図を参照すると、PRCは外部のデュアル重ポ
ートRAM1からの指令とポインタを読み取って多角形塗り
つぶし（fill）プロセスを始める。指令はどんな形式の
図形（多角形またはベクトル）を描くべきか、およびラ
インタイプ・パターン（linetype pattern）を使用すべ
きかを指示する。ポインタは多角形の最初の辺データ・
パケットのロケーションを指示する。各パケットには次
のパケットを指すポインタが含まれている。

最初のポインタは辺機械２に送られる。辺機械２は有効
（active edge）の順序リストを（使用する順序で）作
り上げ、描くべき最初の二つの辺のデータ・パケットを
読み取る。これらは読み取られて、設定機械３に送ら
れ、次いで補間機械４に送られる。補間機械４が各辺の
１走査線を終了すると、パケットは辺機械２に送り返さ
れる。

有効辺が二つしか存在しない場合には、二つとも辺機械
内のレジスタに格納される。二つよりも多くの有効辺が
存在する場合には、辺機械は外部のデュアルポートRAM
と適切な辺をスワッピングする。辺機械はまた有効辺リ
ストを動的に維持する。つまり現走査線が新たな辺に到
達するとこれらを追加し、ある辺について完了するとこ
れらを削除する。辺機械はまた二つの辺が交差するとき
は有効辺の順序を再びソースする。これにより穴があい
ていることがある非平面の、くぼんだ、よじれた多角形
を描くことができる。

補間機械４が各辺に沿ってステップ動作を行なうにつれ
て、その出力が塗りつぶし機械５によってサンプルされ
る。塗りつぶし機械は各辺の走査線への寄与の始まりの
点と終りの点をセーブする。これらから、塗りつぶしベ
クトルを作り、設定機械に送る。塗りつぶし機械はまた
頂点を適切に処理するため、各辺が丁度始まったところ
なのかそれとも終りであるかを常に把握している必要が
ある。辺機械、塗りつぶし機械、補間機械および設定機
械はすべてパイプラインになっているから、塗りつぶし
ベクトルの設定は次の辺セグメントの補間と平行して行
われることになる。

ピクセルの補間 第１図のブロック図はPRC内で行われる幾つかの下位機
能の間の関係を示している。本発明の方法は主として設
定機械３と補間機械４に入っている。実際の一つの具体
例では、PRCは各機械ごとに、Ｘ、Ｙ、Ｚ、赤、緑、お
よび青のそれぞれに対して１個ずつ、計６個設けられて
いる。動作時、PRCは主軸を決めるにあたり（Xe−Xs）
と（Ye−Ys）のうちの大きい方を選ぶ。説明のため、今
は主軸としてＸが選ばれたと仮定する。PRCの６個の補
間機械とこれらに関連した設定機械は次に、XsからXeへ
と増加あるいは減少するＸの値に対して残りのパラメー
タを補間する。これからこれらのパラメータがＸの関数
としてどう変化するかがわかる。これらのパラメータの
中にＹがある。Ｘの系列およびその各々の値から得られ
たＹの系列は最終的にはＺの補間値と色の補間値を格納
するフレーム・バッファのアドレスとして使用される。
ＸとＸの組合せも使用されるが、これは実効的には、主
軸（Ｘであると仮定している）方向に横切るのに使用さ
れるカウンタになっている。（Ｙが主軸であれば、Ｙと
Ｙとの組合せがＹ方向に横切るカウンタとして役立
つ。）次の説明を更に簡単にすることができるように、
Ｚ値をＸの関数として見つける設定機械と補間機械に我
々の注意を限定する。他のパラメータ用の対応する機械
はそれぞれの動作が同じである。

要約すれば、ＸとＹとの組合せはＸの値をインクリメン
トまたはデクリメントして主軸方向に横切る。得られた
Ｘの新しい値のそれぞれについて関連するＺ（および
Ｙ、および赤など）を見つけたいわけである。Ｚ設定機
械はＺ補間機械とともに動作して必要な一連のＺ値を発
生する。各種パラメータ用の機械はすべてＸ機と同期し
て動作し、以後の同時対（X,Z）、（X,Y）、（X,赤）等
々を与える。ＺがＸの関数としてどのように補間されて
いるかを調べるには、従って幾つかの「Ｘ−Ｚ」機械で
はなく、Ｚ機械を調べるだけでよい。

今度は第２図を参照すると、第１図の設定機械３の簡略
ブロック図が示されている。以下に説明する第２図のブ
ロック図は上に示した手順MAI2の（＊設定＊）部分を構
成している。この目的で、第２図はレジスタSEV6、SEP
7、SEM8、SEE9、およびCOUNT10を備えている。またアキ
ュムレータADDS11およびシフトレジスタSEI12を備えて
いる。

設定機械が行うべき機能全体を示す目的で図の各種要素
間の幾つかの接続を簡略化して示してある。多数の指令
や相互接続のバスが関与しているが、全部は示していな
い。これらの厳密な性質については以下に更に詳しく説
明することにする。

ここでは設定機械のＺ用のものへの入力はＺ辺機械から
到来し、次のように処理されるということを述べること
で充分である。値Zs（Ｚの出発値）はSEVにロードさ
れ、ZsとZe（Ｚの出発値と最終値）は各々アキュムレー
タADDS11に送られ、ここでその差が求められる。設定機
械から得られる出力は図に示されているとうりである。

レジスタSEI12とCOUNTS10は、アキュムレータADDS11と
ともに、すべてDIVと記した他の中に示してあるが、MAI
2中の（＊設定＊）と記されたセグメントのDIVとMODの
演算を行う。これは従来のシフト・アンド・アド（また
は減算）形式の除算アルゴリズムを用いて行われる。

今度は第３図を参照すると、Ｚ設定機械を通るデータの
正確なデータ・フローを示してある。この図は第６図に
示す状態機構の状態を参照しているとともに、本発明の
方法のMAI2の記述に使用する各種の名称を参照してい
る。なお同図で丸かっこ内はコメントであるが、Ａ
〔Ｂ〕という記法は「Ｂを有しているＡ」という意味で
ある。

今度は第４図を参照すると、第１図の補間機械４が第２
図の設定機械の出力に基いてどのように動作し、手順MA
I2中の（＊補間＊）と記されたセグメントを実行してい
るかがわかる。第２図の場合のように、簡単な相互接続
と指令の情報だけを示してある。これらの論題に関する
一層の詳細は第７図に示してある。第７図では補間機械
を制御する状態機械自身について記してある。

特に、コード行「Zf:＝Zf＋Mf2」と「Zf:＝Zf＋Mf」
は、アキュムレータBRE14、レジスタBRP15、およびBRM1
6により、アキュムレータBRE14の最上位ビット（MSB）
を表わす信号SELECT18により制御されるセレクタ17と協
同で、実行される。これらコード行はTHENおよびELSE節
の一部として現われるので、一度に一方の行だけが実行
されることになる。どちらの行が実行されるかはアキュ
ムレータBRE14のMSBによって決まる。これに留意すれ
ば、図を調べることにより、BRE14は自身の内容をBRM16
またはBRP15の内容に加算し、その和を次のこのような
加算のために自身の内部に残すことがわかる。BREのMSB
はMAI2の「IF Zf＞＝０」に対応する。MSBが１であれ
ば「ELSE」側を行い、MSBが０であれば「THEN」側を行
う。

これら一連の加算に対してZf、Mf、およびMf2は補間す
べき各ベクトルにつき１回ロードされる初期値である。
これに関連するＮの値も各ベクトルの補間の始めにCOUN
T B19に初期ロードされる。COUNT BはアキュムレータBR
E14が新しい和を発生するごとに１回その値をデクリメ
ントする。上記の加算動作はCOUNT B19のカウントが０
に等しくなるまで、これらの初期値に基づいて繰返し続
く。

MAI2を調べることにより、Mf2がZfに加えられる際には
「Zi:＝Zi＋Mi＋１」も実行しなければならないし、そ
うでなければ「Zi:＝Zi＋Mi」だけを実行しなければな
らないことがわかる。これはその内容（Mi）をアキュム
レータBRV20（その初期内容はZsつまりZiの出発値であ
った）に結合しているレジスタBRI21により行われる。
二つの場合の相違はBRVアキュムレータ20へのキャリー
があるか無いかによって生ずるものであり、これはアキ
ュムレータBRE14のMSB18によって制御される。MSB18の
値は「IF Zf＞＝０」の条件に対応し、これは「＋１」
を追加すべきか否かを選択するものであることを思い出
して欲しい。前のように、これら繰返し加算はCOUNT B1
9の内容が０になるまで続く。

上述の一連の事象はまた第５図のデータ・フロー図に一
層記号化した形で示されている。

今度は第8A図ないし第8C図、第9A図および第9B図を参照
する。いくらか様式化されているが、それにもかかわら
ず、これは第２図および第４図の各種レジスタおよびア
キュムレータがこの方法の好ましい一実施例において実
際にどのように接続されているかの完全な説明である。

第8A図ないし第8C図、第9A図および第9B図は可能なデー
タ・フローの経路を記すハードウェア接続図である。こ
れらの図はどんな命令が存在するかを示していないし、
命令が発せられる順序も示していない。しかし、非常に
多くの事例では、命令の存在は接続の性質から容易に推
論することができる。たとえば、レジスタSEMがバスNSE
TUP9によりセットすることができるとすれば、「Set SE
M from NSETUP（NSETUPからSEMをセットせよ）」なる命
令が存在しなければならない。

第8A図ないし第8C図は６組の辺機械、設定機械、補間機
械、塗りつぶし機械、およびラインタイプ／フォーマッ
ト機械の内部の内部接続を記している。すなわち、第８
図で説明した接続あるいは能力は６つ、つまりリスト:
X、Ｙ、Ｚ、赤、緑、および青、のハードウェアの各組
について一つずつ存在するものとして理解すべきであ
る。対照的に、第9A図および第9B図はほとんど全体の制
御と帳薄づけに関係しており、１つだけ存在している。

本開示をしめくくるにあたり、第6A図ないし第6K図はPR
C中の６個の設定機械を制御する状態機械（図示せず）
の詳細な状態図である。一つの状態機械は６個の設定機
械すべてを制御する。第7A図ないし第7I図はPRC中の６
個の補間機械に対する同様な状態図である。これらの図
は本方法の開示の周辺的な動作について多くの細目を含
んでいるが、その方法とそのハードウェア構成はこれら
の状態図で完全に説明されている。使用した記号は第２
図〜第５図、第８図および第９図の記号と一貫してい
る。たとえば、第6A図の状態STSIDLEの「LD_SETUP_ADD
S」は「load ADDS from the bus NSETUP（バスNSETUPか
らADDSをロードせよ）」を意味している。バスの名称は
省略したこともあるが、レジスタの名称は省略していな
い。

〔発明の効果〕

以上説明したように、本発明によれば高速、高精度の補
間を行うことができ、コンピュータ・グラフィクス分野
等に用いるのに好適である。

【図面の簡単な説明】

第１図は本発明の一実施例を実行するためのハードウェ
ア構成例を示すブロック図、第２図は第１図中で用いら
れている設定機械のブロック図、第３図は第２図の設定
機械のデータ・フローを説明する図、第４図は第１図中
で用いられる補間機械のブロック図、第５図は第４図の
補間機械のデータ・フローを説明する図、第6A図ないし
第6K図は第２図の設定機械の動作を制御する状態機械の
状態図、第６図は第6A図ないし第6K図の接続関係を示す
図、第7A図ないし第7I図は第４図の補間機械の動作を制
御する状態機械の状態図、第７図は第7A図ないし第7I図
の接続関係を示す図、第8A図ないし第8C図、第9A図およ
び第9B図は可能なデータ・フローの経路を示すハード・
ウェア接続図である。 1:デュアルポートRAM、 2:辺機械、 3:設定機械、 4:補間機械、 5:塗りつぶし機械。

Claims (2)

【特許請求の範囲】
1. 【請求項１】下記の（ａ）ないし（ｑ）のステップを有
   し、ピクセルの第１のピクセル値を表す独立変数Ｘが走
   査線に沿ってXsで始まりXeで終わる整数の順序付けられ
   た系列に従って変化するにつれて、所与の出発値Zsから
   所与の終了値Zeまでの範囲をとる前記ピクセルの第２の
   ピクセル値を表す従属変数の整数値Ｚを線型補間し、も
   って対（X,Z）の系列に応じて前記ピクセルを表示する
   ピクセル値補間表示方法： （ａ）差ΔＺ＝Ze−ZsおよびΔＸ＝Xe−Xsを求める； （ｂ）ΔＺをΔＸで除算することにより整数の商Miおよ
   び剰余Ｒを求める； （ｃ）剰余Ｒの値に２を乗算することによりスケーリン
   グされた少数部Mfをもとめる； （ｄ）Mf−ΔＸの値を項Zfに、かつZsを項Ziに割り当て
   る； （ｅ）Xsの値を項Ｘに割り当てる； （ｆ）（Xs,Zs）を対（X,Z）の系列中の最初のものとす
   る； （ｇ）項Ｘの値を前記整数の順序付けられた系列中の次
   の値で置換える； （ｈ）Zfの値が０以上か否か判定する； （ｉ）ステップ（ｈ）の結果、Zfの値が０以上であった
   なら、下記のステップ（ｊ）および（ｋ）を行う； （ｊ）Mi＋１をZiに加算する；および （ｋ）Mf−２ΔＸをZfに加算する； （ｌ）ステップ（ｈ）の結果、Zfの値が０未満であった
   なら、下記のステップ（ｍ）および（ｎ）を行う； （ｍ）MiをZiに加算する；および （ｎ）MfをZfに加算する； （ｏ）（X,Zi）を対（X,Z）の系列中の次のものとす
   る； （ｐ）ステップ（ｇ）ないし（ｏ）を、これらステップ
   がＸ＝Xeについて行われるまで繰り返す；および （ｑ）前記対（X,Z）で定められるピクセル値を有する
   ピクセルからなる走査線を発生する。
2. 【請求項２】前記第１のピクセル値がピクセルの位置を
   表し、前記第２のピクセル値がピクセルの深さを表す特
   許請求の範囲第１項記載のピクセル値補間表示方法。