JPH0215384A - 補間およびデジタル微分解析の方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ［産業上の利用分野］ 本発明は、乗算器アキュムレータ（ＭＡＣ）を用いた補
間（ｉｎｔｅｒｐｏｌａｔｉｏｎ　）およびデジタル微
分解析（ｄｉｇｉｔａｌ　ｄｉｆｆｅｒｅｎｔｉａｌ　
ａｎａｌｙｓｉｓ）の方法に関するものである。

［従来の技術］ ｉ）補間の重要性 コンピュータの分野においては、値を補間することが、
しばしば必要とされる。例えば、ビットマツプされた表
示モニタの上に１本の線を引くためには、始点と終点の
間に表示された幾つかのビクセルの間に目的の線を書き
入れなければならないことがある。その場合、線を形成
するピクセルを輝かせることにより、その線が書き込ま
れる。

もう一つの例は、表示された画像の与えられた領域に、
徐々に影をつけたい場合である。この操作のための従来
の方法は、与えられたビクセルの上の影の始点シエイド
（ｓｔａｔｉｎｇｓｈａｄｅ）と終点シエイド（ｅｎｄ
ｉｎｇ　５ｈａｄｅ）の間に、影の値（ｓｈａｓｄｉｎ
ｇｖａｌｕｅ）を挿入することであった。

これらの方法は決して面倒ではない。また、実際、可能
なアプリケーションの表面を補間アルゴリズムのために
引っかくだけのものである。

−数的な問題は次のようなものである。

与えられたステップの数（Ｎ）にわたって、初期値（Ｖ
）があるｍ　（ＤＡＬＴＡ　Ｖ）ずつ徐々に変化してい
くか、ということである。

補間を行うための従来の方法のひとつは、デジタル微分
アナライザ（以下、　ＤＤＡという）の使用である。１
つのよく知られた例は、線を引くためのＤＤＡである。

典型的なシンプルなラインＤＤＡは、ラインのＸ、Ｘ要
素を整数部と分数部に分ける！ｌｌきをする。それから
、ＤＤへはＸ、Ｘ要素を分数単位で増加させる。分数部
が一杯になったときには、整数部が増加される。上記Ｄ
ＤＡは整数要素を、その出力を形成するために使用する
。コンピュータの分野で使用されているように、要素の
ひとつは堅実に一つずつ増加し、他の要素は条件付きで
増加する。

ｉｉ）単純なりＩ）八 単純なりＤＡアルゴリズムは、第１図を参照してよりよ
く理解されるであろう。例えば、表示モニタ上において
、ライン１０２を始点１０４と終点１０６の間に描く場
合を仮定する。そして、点は格子の線が交差する場所（
モニタ上のピクセルに対応している）にのみプロットす
ることができると仮定する。線の初期値（ｖ）はゼロ（
Ｘ要素の始点値）である。期待された変化（ＤＡＬＴＡ
　Ｖ）は５（Ｘ要素の終点値）であり、その値が変化（
Ｎ）するステップの数は７（Ｘ軸の方向での線の全長）
である。

次に示す例１−１に示した単純ベーシック言語ＤＤＡは
、このようなプロットをするために使用される。

例１−１ ＤＤＡプログラム Ｘ−０：Ｙ−０：Ｎ−７：ＤＥＬＴＡ　Ｖ−５Ｙ−Ｖ＋
、５ ＦＯＲ１−Ｉ　Ｔｏ　Ｎ ＰＬＯＴ（ＴＲＵＮＣ（Ｘ）、’ＴＲＵＮＣ（Ｙ）Ｙ−
Ｙ＋ＤＥＬＴＡＶ／Ｎ Ｘ−Ｘ＋１ ＥＸＴＸ Ｐｌ、ＯＴ　（ＴＲｔｌＮＣ（Ｘ）　、　ＴＲＵＮＣ（
Ｙ）ＮＤ 上の例から次のことが理解される。［ｌＤＡプログラム
はＹ値を単純に初期化し、そのラインのＹスタート座標
値プラスまるめファクタ（ｒｏｕｎｄｉｎｇｆａｃｔｏ
ｒ）　０．５とする。そしてＮ回の反復サイクルにおい
て、ＸとＹ値の整数要素における点にプロットし、Ｙ！
ＮＩの座標をラインのスロープだけ増加させ（ＤＥＬＴ
八Ｖ／へ）　、ラインのＸ要素を１だけ増加させる。最
後のプロットコマンドは、ラインの最後の点をプロット
するためのものである。

上記のプログラムによく似たプログラムとしてゴラウド
ーシェイディング（Ｇｏｒａｕｄ　ｓｈａｄｉｎｇ）　
に使用されるものがある。２つのプログラムの相違は、
Ｘ軸座標とＹ軸座標を変えるのと違い、シェイディング
の値（ｓｈａｄｉｎｇ　ｖａｌｕｅ）が与えられたステ
ップ数にわたって変わることである。同様に、シエイデ
ィング・プログラム（ｓｈａｄｉＢ　ｐｒｏｇｒａｍ）
では、最後のプロットコマンドは必要ない。

１ｉｉ）　　プレセンハムのアルゴリズム（Ｂｒｅｓｅ
ｎｈａｍ’　ｓＡＩｇｏｒｉｔｈｍ） 上記のような単純［ＩＤＡ操作（ｏｐｅｒｒａｔｉｏｎ
）での問題点は、分割操作（ｄｉｖｉｓｉｏｎ　ｏｐｅ
ｒａｔｉｏｎ）を必要とすることである。これにはＣＰ
Ｕタイムの点で費用がかかる過ぎるため、従来は、単純
ＤＤＡはハードウェアの実現にふされしくないとみなさ
れていた。分割を避けるための従来の一般的な方法の１
つは、プレセンハムのアルゴリズムとして知られる、別
の種類の補間方法である。

プレセンハムのアルゴリズムは、おのおのの反復毎に、
座標値をプラス１またはマイナス１するよう設計されて
いる。残りの座標値が増加されるかどうかは、アルゴリ
ズムによって保持されているエラーターム（すなわち、
プレセンハムのエラーターム）の値による。理論的に完
全なラインの正確なパスと、アドレスされて書き込まれ
た（すなわち、点として輝いている）実際のピクセルと
の間の距離を記憶させるために、このエラータームが使
用される。プレセンハムのアルゴリズム・ラインブロッ
ティング・プログラムの一例、および、ＯＤＡの他の例
は、ウィリアム、Ｍ、ニュウマン、ロバート、Ｆ、スプ
ロール、マグロ−ヒルによる°°ゼインラクチイブ・コ
ンピュータ・グラフィクスの原理パ（第２版）にみるこ
とができる。

この文献は、本明細書の一部として引用される。

プレセンハムのアルゴリズムは、分割の問題を解決して
いるにもかかわらず、多くの従来のＤＤ八へ間技術と同
じく、他の幾つかの問題にぶちあたる。

ｉｖ）非分数的スロープの問題 多くの従来から知られているＤＤ八へログラミング技術
では（プレセンハムのアルゴリズムプログラムを含めて
）、補間された値が制限付きで１つずつ増加することの
み許されている。この問題は、Ｘ軸から４５度より大き
なスロープをもつラインを考える時、よりはっきり理解
できる。これらの場合には、Ｎ（ステップの数）は、常
にＤＥＬ丁＾Ｖ（値の意図された変化）より小さい。

この状況を伴った問題が第２図に示されている。

第２図は、Ｘ軸、Ｙ軸の原点にあるスタート点から描か
れたライン２０２　と、Ｘ、Ｙ座ｍ４．７にある終点２
０６を示す。この場合、Ｎは４に等しく（すナワチ、４
−７−（ｆ−ス０　’）　、ＤＥＬＴＡ　Ｖは７（すな
わち、７マイナス０）に等しい。

当業者であれば、このような環境のもとでは、プレセン
ハムのアルゴリズムルーチンにおいては、Ｘとｙとは常
に増加するということを理解するであろう。結果は、第
２図で点に示したように、４５度のプロットである。こ
れは勿論、期待された結果ではない。

このような条件に適応するために、Ｙ方向のＤＥＬＴＡ
　Ｖステップにわたって、Ｘの値を補間するために、別
のコードが加えられなければならない。換言すれば、ス
ロープ方向が１以下の場合には、それに対応するために
プログラムを書キ換えなければならない。ラインの角度
に応じて、プレセンハムのアルゴリズムや他の従来のＤ
ＤＡプログラムを使用しているプログラムは、１セツト
のコードもしくは他のコードを入力しなければならない
。プログラマ−やプログラムは、どのセクションが実行
されているか見守らなければならない。

不運なことに、上記の方法で線描の問題は解決するが、
ボウラウド・シエイディング（Ｇｏｕｒａｕｄｓｈａｄ
ｉｎｇ）のような−次元の問題は解決しない。例えば、
表示スクリーンの左手端から始まる８ビクセルにわたり
、６０と１５５によって表される２つのシェイド（５ａ
ｄｅ）の間を補間することを考えてみる。可変ＤＥＬＴ
Ａ　Ｖは１９５　（２５５−Ｇｏ）　ニ等しく、Ｎは８
に等しい。Ｘは最初１に等しく、Ｙは最初６ｏに等しい
。

ＤＥＬＴＡ　ＶをＮで分割した結果は７．５であり、プ
レセンハムのアルゴリズム型のプログラムは各ビクセル
（すなわち、６０，８Ｌ６２，８３，８４，６５，６６
．６７）に対して、各々のシエイド値を星゛にまたり増
加するのみである。この場合のスロープを反対にすると
、無意味な結果が得られる。このことは、ＮとＸはビク
セルで定義され、これに対してＹとＤＥＬＴＡ　Ｖはシ
ェイディング・コード（ｓｈａｄｉｎｇｃｏｄｅ）で定
義されることを考えれば理解しやすい。

■）　ライン・クリッピング（Ｌｉｎｅ　Ｃ１Ｃ１１ｐ
ｐｉｎおよびサブセット・ライン（Ｓｕｂｓｅｔ　Ｌｉ
ｎｅ）の問題プレセンハムのアルゴリズムと他の多くの
補間方法に関するもうひとつの問題点は、サブセットラ
インの問題であると言われている。簡単に言えば、２次
元ラスフグラフイックにおいて、ラインを消したり繰返
したりするに際して、ラインの正しいプロット位置を決
めることが困難なことである。例えば、ラインＬｌをス
クリーン上の始点ビクセルＰＩと終点ビクセルＰ２の間
に描くとする。そして、選ばれた補間アルゴリズムはビ
クセルグループＧｌをプロットすることにより（例えば
、最初の色を輝かせることにより）、ラインを描くもの
とする。ラインの一部を消したり、上書きすることが必
要であれば、ラインＬの一部分をもう１度たどることが
必要となる（例えば、第２の色を輝かせて）。

この操作のためには、最初のビクセルグループＰ４の内
で始点ビクセルＰ４と終点ビクセルＰ５を選ぶことによ
り、新しいラインＬ２を描かなければならない。新しい
ラインＬ２はラインＬｌの一部分を消すために使用され
るのであるから、ラインＬ２を描くときにプロットされ
たビクセルのグループ（グループＧ２と呼ぶ）はＧ１の
なかのサブセットであることが重要である。

サブセットラインの問題はとるに足らない問題ではない
。もし上記の条件が満たされなければ、ラインは完全に
消されることができないし、余分なビクセルがプロット
され、その結果としてスクリーンを乱すことになる。一
般のプレセンハムのアルゴリズムは上記の条件を満足し
ていないことが理解される。著者らによフてこの問題を
迂回するためのある示唆が提示されている。１つの例は
、そこに記憶されているスクリーン上の可能なラインの
デジタイゼイションを行なうルックアップテーブルの使
用をすすめている。このような示唆は一般に非現実的で
あると考えられている。サブセットラインの問題は“ラ
スタ・グラフィックスのためのデータ・ストラクチュア
°°という本の中に詳細に述べられている。その木はり
、Ｒ，Ａ、ケセナー、　Ｆ、Ｊ、ベータース、　Ｍ、Ｌ
、Ｐ、ライン　リーロツクによって編集され、スプリン
グアー　バーログによって出版されたものである。その
内容はそフくりそのまま、本明細書の引用文献として参
照するものとする。

この木はヨーログラフィックス　セミナーズシリーズ（
Ｅｕｒｏｇｒａｐｈｉｃｓ　Ｓｅｍ１ｎａｒｓ　５ｅｒ
ｉｅｓ）の−部である。

サブセットラインの問題に関し、この木には゛準備的な
結果がでているにもかかわらず、これはやはり解決され
なければならない問題である。

良いアルゴリズムが存在するかどうかすら分かりではい
ない。勿論それが複雑であるからである。　　（ベージ
７、バラグラフ１）と述べられている。

サブセットラインの問題は重要になっている。

特に、表示されたウィンドウの境界でラインを切る場合
、その場所が重要である。この問題を第３図に図示する
。スクリーンやウィンドウに表示されたラインをそのス
クリーンやウィンドウの外側の点から計算する場合、ラ
インは切り取られなければならない。

第３図において、ライン３０２はウィンドウ３０６の外
側にある点３０４から出発している。ライン３０２の一
部は、残りの部分が隠されている間、ウィンドウに表示
されなければならない。この問題を解決するために、従
来から２つの方法がとられている。

クリッピングの１つの方法は、クリップされていないサ
プラインの始点を計算し、プレセンハム型の補間を行う
ことである。この場合、補間はラインの実際の原点以外
の点から出発し、サブセットラインの問題に遭遇する。

このことは、元のラインに描かれたのとは少し違ったビ
クセルが、クリップされたラインに含まれる結果となる
。もし、クリップされないラインをたどることが必要な
場合、あるいはラインが別のウィンドウでクリップされ
た場合、プログラマ−は少しばかり違ったビクセルのセ
ットが選ばれているのを発見することになるだろう。

第２の従来の方法はサブセットラインの問題を迂回する
にあたり、ラインの始点からプレセンハム型の補間を行
ない、ウィンドウが出発する点を追跡しながら、非ウィ
ンドウ領域には書き込みを行わないで解決しようとする
ものである。この方法は正しい。しかし、ラインが非ウ
ィンドウ領域に書込まれていないことを確認するために
、余分なソフトウェアの経費と、計算時間を必要とする
。その上、ＯＤＡの総てを見えないビクセルのためにま
で行うために時間を費やす。

クリッピングと補間の技術、プレセンハムのアルゴリズ
ムを含めて、ＤＤＡとボウラウド・シエイディングにつ
いては、ウィリアム・エム・ニューマンおよびロバート
・エフ・スブロウル　マワグロウヒル（第１０版　１９
８４）による“°インテラクチイブ・コンピュータ・グ
ラフィックス”　（第２版）に述べられている。

ｖｉ）　プログラマ−のジレンマ プログラマ−は伝統的にジレンマに直面している。プロ
グラマ−は−ｎ９的に単純なりＤＡ型の方法の中から選
はなけれはならない。その方法は、費用のかかる分割を
必要とするほか、サブセットライン問題を生じ、Ｘとｙ
の増分のサイズを１に制限するプレセンハムのアルゴリ
ズムやそれに似た技術が必要とされる。

いかなる数のステップにもわたって、全ての範囲の値を
補間できる補間方法が望ましい。あらゆる範囲の値また
はあらゆる数のステップにわたり、ＤＤＡ型方決方法い
て、ボウラウド・シェイディング演算（Ｇｏｕｒａｄ　
ｓｈａｄｉｎｇ　ｏｐｅｒａｔｉｏｎ）を行ない得るこ
とが望ましい。補間された値を、各々のステップにおい
て、１よりも大きな数で増加させ得ることが望ましい。

ソフトウェアの分割を避けることか望ましい。その上、
別め°クリッピング境界でクリップされたラインに対し
て、選ばれたビクセルの正確な繰り返しを保証するため
に、速く、正確なラインクリッピングができることが特
に望ましい。

［発明の概要コ 本発明は、デジタル微分解析をハードウェア乗算器アキ
ュムレータ（ＭＡＣ）を使用して行う方法を含むもので
ある。

［実施例］ 以下、実施例に基いて本発明の詳細な説明する。

本発明は、ハードウェアー乗算器アキュムレータ（ＭＡ
Ｇ：：ｌｌ１ｕｌｔｉｐｌｉｅｒ　ａｃｃｕｍｕｌａｔ
ｏｒ）を使用して、デジタル微分解析を行う方法を含む
。この方法は、増加ステップの数が、ステップの存在す
る値の範囲よりも小さい時のプログラミングを可能にす
る。この方法はプレセンハムのアルゴリズムを使用した
クリッピングの方法と、他の従来の１）ＤＡ技術に以前
からあったいくつかの固有の問題を解決するものである
。

本発明の好適な実施例による基本ハードウェアーを第４
図と第５図に示す。第４図と第５図は乗算器アキュムレ
ータ（ＭＡＣ）のブロック図を示す。

ＭＡＣ４００は２個の入力レジスタ４０２，４０４　、
乗算器アレイ４０６、加算器４０８　、３個の出力レジ
スタ４１０゜４１２、４１４を含んでいる。１．５Ｐ（
ｌｅａｓｔ　５１ｇｎ１ｆｉｃａｎｔｐｒｏｄｕｃｔ）
レジスタは、乗算の結果の分数部を記憶し累積する。Ｍ
ＳＰ（ｍｏｓｔ　５１ｇｎ１ｆｉｃ　ａｎｔ　ｐｒｏｄ
ｕｃｔ）レジスタは、結果の整数部を記憶し累積するた
めに使用される。ＸＴＰ（ｅｘｔｅｎｄｅｄ　ｐｒｏｄ
ｕｃｔ）　　レジスタは、オーバーフローしたものを記
憶し累積するために使用される。

ＭＡＣ４００は、出力レジスタ４１０，４１２，４１４
　をプリロードする機能をもち、少なくとも乗算モード
および乗算・累積モードで動作可能なことが好ましい。

好適な乗算器アキュムレータ（ＭＡＣ）は、ＩＤＴ７２
１０１６ｘ　１６並列乗算器アキュムレータであり、カ
リフォルニア　サンタモニカ　インテグｌ／イテド　デ
バイス　テクノロジー　社から人手できる。ＴＤＴ７２
１０の構造と動作は、同社の“旧ＧＨＰＥＲＦＯＲＭＡ
ＮＣＥ　ＣＭＯ５ＤＡＴＡ　ＨΔＮＤ［１ＯＯＫ　”に
書かれている。

第５図は、本発明の他の実施例を示す。本実施例は６４
ｋＸＩ６９−ドオンリーメそり（ＲＯＭ）ルックアップ
テーブル５０２を含んだハードウェアーである。ルック
アップテーブル５０２は、そのアドレス入力に現われる
全ての値の逆数を求めるために使用される。

次に、第６図を参照して本実施例の動作を説明する。ま
ず、ＭＡＣの出力レジスタが最初にプリロードされる。

−木のラインを描く場合を考えてみよう。ＬＳＰレジス
タにはまず、初期まるめ値（例えば０．５）がロードさ
れる。一つの座標ｉ＋ｈ　（例えは、Ｙ　Ｉｔｌｌ　）
の最初の値Ｖは、初め、ＭＳＰにロードされる。ＭＡＧ
は入力がロードされる時には“乗算アキュムレートモー
ドに設定されなければならない。

次に、ＤＥＬＴ八Ｖのへは、第１入力レジスタ４０２の
アドレス入力で記憶される。同時に、Ｎの値は、ＲＯＭ
ルックアップテーブル５０２のアドレス入力で記憶され
、ｌ／Ｎが現れ、第１入力レジスタ４０２．４０４で安
定するまで保持される。それらは、クロックに同期して
第１および第２入力レジスタ４０２．４０４にそれぞれ
入力される。

また、ＤＥＬＴＡ　Ｖの値は、それが、ＭＡＧ入力で安
定するとすぐに、クロックに同期して第１入力レジスタ
に入力される。そして、Ｎ値の逆数は、それが安定した
時、クロックに同期して第２入力レジスタに入力される
。ＭへＧ入力でのデータの安定性は、ＲＯＭアクセス時
間を考慮にいれた適切なりロッキング機構の採用により
容易に確保される。

乗算−アキュムレートモードに設定されているため、Ｍ
ＡＣは１／ＮにＤＥＬ丁Ｅ　Ｖを乗する。この結果は出
力レジスタ４１０，４１２，４１４の最初の内容に加え
られる。累積された値は、クロックに同期して出力レジ
スタ４１０．４１２．４１．４に入力される。つぎに、
乗算の結果は再クロックされ、出力レジスタ値と共に累
積される。このプロセスは、補間がなされるべきステッ
プの総数だけ繰り返し続けられる。

このことは、単に、ＭＡＣ出力レジスタ４１０，４１２
゜４１４をＤＥＬＴＡ　Ｖ値を変化させるべきステップ
の数に等しい回数だけクロックキングさせることが必要
になる。

Ｘ、Ｙの値を正しくプロットするために、ある値をプロ
ットするＹが各クロックサイクル毎にＭＳＰ　レジスタ
４１２に格納されいる間、Ｘは各クロックサイクル毎に
１ずつ増加する。Ｙが零以外の初期値を持つ時、初期設
定の間、ＭＳＰレジスタ４１２はその値（ＹＯ）にプリ
ロードされる。初期Ｙ値をロードする機能は、ラインク
リッピング操作において、大きな意味がある。

ラインクリッピングを行う場合には、ＭＡＣはラインの
生成と同様なプログラムが施される。初期の乗算・アキ
ュムレート動作において、第１入力レジスタ４０２につ
いては、ラインの見え得る部分に達するステップ数がロ
ードされていることを除いて（すなわちｎ＊ＤＥＬＴＡ
　Ｖ）　、木質的な初期設定は同じである。

最初の乗算・アキュムレート動作は、あたかもｎステッ
プが、１６ビツトの小数のエラータームを含めて、この
設定を達成するために取入れられているかのように（す
なわち、その結果はｎ◆ＤＥＬＴＡＶ／Ｎ）、出力レジ
スタをセットアツプする。かくして、最初の点がプロッ
トされる。

次に、標準のライン・トロウィング・ルーチーンとして
、第１入力レジスタにはＤＥＬＴＡ　Ｖがロードされる
。そして、通常ラインの終りに達するまで、或いは、ラ
インがウィンドウと交差するまで、そのアルゴリズヌは
進行する。ＭＡＣはｎ＊ＤＥＬＴＡ　Ｖの初期計算に使
用される。

本発明方法の好適な実施例において、ＮとＤＥＬＴＡ　
Ｖは１６ビツト２進数として表される。ＲＯＭルックア
ップテーブル５０２は、各々のアドレス領域における各
々のアドレスの逆数で、できれば、無記号の分数表示で
プログラムされる。

言い替えれば、２は１６進数８０００をもたねばならな
い。アドレス４は、４０００もたなければならない。ア
ドレス１と０は特別なケースであって、ＭＡＣプログラ
ミング・アルゴリズム（第５図参照）が零の場合を考え
なければならない。ＭへＣ動作はただ一つの点、をプロ
ットする場合には必要とされない。それはソフトウェア
−で十分処理出来るからである。

都合の良い事に、マイナスのスロープの値は必要でない
。ゴウラウト・シェイディングにおいて、ＤＤＡは常に
数字的に低位のシェイドから出発し、上位にあがってゆ
く。ラインを描く場合、ＤＤＡは常に終点が結果的に正
のスロープになるようなところから進行する。−たびプ
ログラムされると、ルックアップテーブルＲｆ）Ｍの出
力からは、アドレス入力で保持されているＮ値の逆数が
当然に生じる。

都合の良い事に、ＭＡＣへの各入力は分離されたバス上
にあり、従って、二つの入力は一緒にまたは別個にロー
ドされる。同様に、出力レジスタは、入力レジスタとは
別個にクロックされる。そのため、ラインを描いたりラ
インをシエイト（５ｈａｄｅ）するために、−度だけク
ロックされればよく、また、与えられた領域に対してク
リップするために、入力レジスタは二度だけクロックさ
れればよい。

結　論 本発明を実施することにより、当業者は多くの改良をな
しとげることができる。例えば、より大きな（つまり、
１６ビツト以上）　ＭＡＣは、正確さを改良するために
使用されることができる。マルチプレクサは、出力レジ
スタのどの部分が使用されるかを選択するために、出力
側に置くことができる。このことは、様々なアプリケー
ションに対して、整数および分数サイズの様々な混合を
可能にする。

本発明によるシステムおよび方法は、アルゴリズムの最
初においてアキュムレータと共にＮＩＤＥＬＴＡ　Ｖを
ひとたび計算するために、内部計算ループのみで加算器
を使用するよう変更することができる。このことは、高
度の正確性が求められるならば、特に有用である。

本発明による方法は、ＯＤＡの設定されたステップの数
を変えるために、同じハードウェアを使用して容易に変
更することができる。このことは並列プロセッサを使用
する時、非常に有用である。

すなわち、あるラインに沿ってビクセルのシェイディン
グを計算するプロセッサが一つ以上ある場合に、有用で
ある。例えば、あるグラフィック・システムがＸ方向に
５つのプロセッサを持っている場合（各々が５つのグル
ープの中の一つのピクセルを担当する）、−ステップで
５つのシェイディング値を計算する必要がある。本発明
のシステムおよび方法は、各サイクル毎に５つのステッ
プを実行するよう各プロセッサのＭＡＣをセットアツプ
することにより、このことを容易に行うことができる。

従りて、上述した好適な実施例は本発明の典型的な一例
として記述されたものであり、本発明の要旨を逸脱しな
い範囲の変更・修正が可能である。

［発明の効果］ 本発明の方法によれば、プログラマ−は線形補間の最良
の方法を得ることができる。ＭＡＣハードウェアは、単
純ＤＤＡに固有な分割なしで、プレセンハムのアルゴリ
ズムに関連したサブセットラインの問題なしで、ざらに
増加ステップの数がステップの見いだされる値の範囲よ
りも小さい場合を扱うためにしばしば要求される付加コ
ードを要求することなく、ＤＤＡが迅速に実行されるこ
とが可能になる。

ハードウェアを使用してＤＤＡを実行することにより、
線形補間に関する多くの問題は解決される。例えばひと
つの実施例として、ラインクリッピングが′簡単かつ正
確に行えることである。　ＭＡＣを適当に初期化するこ
とにより、いかなるピッチのラインもウィンドウの境界
線ですばやくクリップされる。ＭＡＣ入力の１つに、ハ
ードウェア・ルックアップ・テーブルを加えることによ
り、システムのオペレーションを分割する必要がなくな
り、従ってプレセンハム型アルゴリズムの必要がなくな
る。このシステムと方法は、サブセットラインに関して
長い間解決されなかった問題を解決する。

その上、木発明の方法はいかなる値の範囲、または、い
かなるステップ数を補間する場合にも使用できる。Ｎと
ＤＥＬＴ八Ｖのへの相対的なサイズは、この方法に少し
も影晋を与えるものではない。本発明によれは余分なコ
ードの必要をなくす。また、本発明によれは、補間が行
われるチップにわたり、ステップの数より値の範囲が大
きいという１次元的問題を解決するために、ＯＤＡを実
行させることができる。

ある実施例において、この方法はラインのボウラウド・
シェイデイングに使用される。ＭＭＣ入力の１つは、デ
ルタ色（色の量はラインに沿って変わる）でロードされ
、他の入力はラインの長さの逆数によってロードされる
。ＭへＧ結果レジスタの高位の部分（ＭＳＣ）は、スタ
タート色で前もってロードされている。ＩｔＯＭルック
アップテーブルを使用することにより、ラインの長さの
逆数はプログラムを使って計算する必要がない。プログ
ラムはルックアップテーブルの入力の時に、実際のライ
ンの長さを単純に把握している。そして、その逆数は自
動的に生成され、ソフトウェアの計算は必要とされない
。ピクセルが描かれる時はいつもＭＡＣの２つの入力は
乗算され、最初の結果に加えられる。結果の高位の部分
は、各々のピクセルの色として使用される。そして、結
果の累積された低位の部分がオーバーフローを起こした
時、自動的に変化する。

本発明の方法により、各々のピクセルの変化のユは、ラ
インの長さによって分割されたデルタの色となる。それ
故、最後の色は、最初の色プラスデルタの色である。

都合の良いことに、この方法は、ビット・スライス・プ
ロセッサとマイクロプロセッサを実装した多くのＣＰＵ
ですでに使用可能な、単純なＭＡＣハードウェアを使用
することがてきる。ＭＡＣ集積回路は、それをまだ使用
していないシステムに、安価で実装することができる。

本発明による方法の一つの実施例では、ＭＡＣによる処
理のためにデータが提供されている時、自動的に逆数演
算を行うルックアップテーブルを使用することかできる
。このルックアップテーブルを使用すれば、時間のかか
る分割操作（ｄｉｖｉｄｅ　ｏｐｅｒａｔｉｏｎ）の必
要がなくなり、ＣＰＵの費用を軽減することができる。

それ故、本発明の方法は、分割操作を行うアルゴリズム
を避けるために、従来必要とされたものを必要としない
。

本発明の方法は多くの補間の問題を解決するために使用
されることができる。そして、多くの場合費用がかから
ない。

【図面の簡単な説明】

第１図は典型的なライン補間問題を示す図、第２図はＸ
釉から４５度以上で描かれたラインの補間の問題を示す
図、 第３図はクリッピングに関する問題を示す図、第４図は
本発明の一実施例による乗算器アキュムレータを示すブ
ロック図、 第５図は木発明のその他の実施例による乗算器アキュム
レータおよびルックアップ・テーブル・メモリを示すブ
ロック図、 第６図は本発明の一実施例によるＯＤＡの処理手順を示
すフローチャートである。 Ｙ卸 Ｆｉｇｕｒｅ　１ Ｙ軸 Ｆｉｇｕｒｅ　２

Claims (1)

1. 【特許請求の範囲】 １）所定長さのラインにわたって線型補間を行う方法で
   あって、 （ａ）乗算器アキュムレータの出力レジスタのいずれを
   も予め定めた初期値で初期化するステップと、 （ｂ）前記乗算器アキュムレータの第１入力レジスタを
   前記ラインの前記長さにわたる出力値の増分変化に等し
   い値でロードするステップと、 （ｃ）前記乗算器アキュムレータの第２入力レジスタを
   前記ラインの長さの逆数に等しい値でロードするステッ
   プと、 （ｄ）前記乗算器アキュムレータによりその第１および
   第２入力の値を乗算するステップと、 （ｅ）ステップ（ｄ）の結果の分数部分を第１出力レジ
   スタに累積するステップと、 （ｆ）ステップ（ｄ）の結果の整数部分を前記第１出力
   レジスタのオーバーフローと加算して第２出力レジスタ
   に累積して累積された結果を形成するステップと を備えたことを特徴とする線型補間法。 ２）ゴウラウド・シェーディングを生成するために、前
   記第２出力レジスタを初期化するのに用いられる予め定
   めた値は出発シェードを表わし、前記増分変化は前記ラ
   インの長さにわたってのシェードの変化を表わし、累算
   された結果は所定ディスプレイ区域に対するシェード値
   を表わすことを特徴とする方法。 ３）メモリにストアされたルックアップ・テーブルを使
   用して前記ラインの長さの逆数を決定するステップをさ
   らに備えたことを特徴とする請求項１に記載の方法。 ４）前記ルックアップ・テーブルの出力を前記第２入力
   レジスタに直接にロードすることを特徴とする請求項３
   に記載の方法。 ５）前記ステップ（ｄ）、（ｅ）および（ｆ）を、色の
   変化が起こるはずのディスプレイ区域の個数に等しい予
   め定めた回数だけ繰返すステップをさらに備えたことを
   特徴とする請求項２に記載の方法。 ６）前記ディスプレイ区域の各々はピクセルであること
   を特徴とする請求項５に記載の方法。 ７）前記ディスプレイ区域の各々はパッチであることを
   特徴とする請求項５に記載の方法。 ８）２つの方向性成分をもち、所定の長さをもつライン
   をクリップして、そのラインのうちの予め定めたセグメ
   ントのみを表示する方法であって、 （ａ）乗算器アキュムレータの出力レジスタのいず　れ
   をも予め定めた初期値で初期化するステップと、 （ｂ）前記乗算器アキュムレータの第１入力レジスタを
   前記ラインの一方の方向性成分の長さに等しい値でロー
   ドするステップと、 （ｃ）前記乗算器アキュムレータの第２入力レジスタを
   前記ラインの長さの他方の方向性成分の長さの逆数に等
   しい値でロードするステップと、 （ｄ）前記乗算器アキュムレータによりその第１および
   第２入力レジスタにおける値を乗算するステップと、 （ｅ）ステップ（ｄ）の結果の分数部分を第１出力レジ
   スタに累積するステップと、 （ｆ）第２出力レジスタにおける前記第１出力レジスタ
   のオーバーフローを累積するステップと、 （ｇ）ステップ（ｄ）の結果の整数部分を前記第２出力
   レジスタに累積するステップと、（ｈ）第２出力レジス
   タにおける値が変化する度毎に、点をディスプレイ装置
   のピクセル上に描かせ、ピクセルは前記第２出力レジス
   タにストアされている値に応じて決定される少なくとも
   ひとつの座標値を有するステップと を備えたことを特徴とする方法。 ９）前記第２出力レジスタを初期化するのに用いられる
   予め定めた値は前記ラインの予め定めたセグメントのス
   タート点を表わすことを特徴とする請求項８に記載の方
   法。 １０）メモリにストアされたルックアップ・テーブルを
   使用して前記ラインの長さの逆数を決定するステップを
   さらに具えたことを特徴とする請求項８に記載の方法。 １１）前記ルックアップ・テーブルの出力を前記第２入
   力レジスタに直接にロードするステップをさらに備えた
   ことを特徴とする請求項１０に記載の方法。 １２）前記ステップ　（ｄ）、（ｅ）、（ｆ）、（ｇ）
   および（ｈ）を、ライン長の変化が起こるはずの点の個
   数に等しい予め定めた回数だけ繰り返すステップをさら
   に備えたことを特徴とする請求項８〜１１のいずれかの
   項に記載の方法。 １３）前記点の各々はピクセルであることを特徴とする
   請求項１２に記載の方法。 １４）前記点の各々はパッチであることを特徴とする請
   求項１２に記載の方法。