(57)【特許請求の範囲】
【請求項１】
判断変数が最上位ビット列、前記最上位ビット列よりも下位のビット列、および符号ビット（４２０）を有する、ベクトル生成における判断変数の反復生成回路であって、
一方が最終パイプライン段であり、他方が最終段の前のパイプライン段である少なくとも２つのパイプライン段と、
桁上げ入力ビットを受け取り、前記判断変数の最上位ビット列と第１定数（Ｉ１）の最上位ビット列又は第２定数（Ｉ２）の最上位ビット列のいずれか一方とを加算し、出力として前記符号ビットと反復後の判断係数の最上位ビット列とを生成する、前記最終パイプライン段内の加算器（４３２ ）と、
前記下位のビット列と前記第１定数の下位ビット列を加算して、第１の見込み桁上げ出力ビットを生成する、前記最終段の前のパイプライン段内の第１の加算器（４２２ ）と、
前記下位のビット列と前記第２定数の下位ビット列を加算して、第２の見込み桁上げ出力ビットを生成する、前記最終段の前のパイプライン段内の第２の加算器（４２４）と、
前記最終段の前のパイプライン段から生成される前記第１及び前記第２の見込み桁上げ出力ビットが入力され、前記最終パイプライン段からの前記符号ビットによって、前記第１及び前記第２の見込み桁上げ出力ビットのいずれか一方を選択して前記最終パイプライン段内の加算器に桁上げ入力ビットとして出力するマルチプレクサ（４２８）と
を有することを特徴とするベクトル生成における判断変数の反復生成回路。
【請求項２】
前記最終段の前のパイプライン段の２つの加算器（４２２、４２４）は、前記下位のビット列の見込み選択肢を２つ生成し、
次の反復に用いるため、前記最終パイプライン段からの符号ビットによって、前記下位のビット列の２つの見込み選択肢のうちの１つを選択して前記最終段の前のパイプライン段の２つの加算器に対する入力として出力するマルチプレクサ（４２６）をさらに有することを特徴とする請求項１に記載の回路。
【請求項３】
反復ベクトル生成における、符号ビット（４２０ ）、最上位ビット列およびそれより下位のビット列からなる判断変数を演算する方法であって、
最終段のパイプライン段が桁上げ入力ビットを受け取り、前記判断変数の最上位ビット列と第１定数（Ｉ１）の最上位ビット列又は第２定数（Ｉ２）の最上位ビット列のいずれか一方とを加算して、最上位ビット列と前記符号ビットとを生成するステップと、
前記最終段の前のパイプライン段において、前記下位のビット列と前記第１定数の下位ビット列を加算して第１の見込み桁上げ出力ビットを生成するとともに、前記下位のビット列と前記第２定数の下位ビット列を加算して第２の見込みの桁上げ出力ビットを生成するステップと、
前記最終段の前のパイプライン段からの前記第１および第２の見込みの桁上げ出力ビットのうち、どちらを前記最終パイプライン段での桁上げ入力とするかを決定するため、前記最終パイプライン段から出力される前記符号ビットを用いるステップと
を有することを特徴とする演算方法。
【請求項４】
請求項３に記載の演算方法において、
前記最終段の前のパイプライン段で、前記下位のビット列と前記第１の定数の下位ビット列を加算して第１の見込み選択肢を生成するとともに、前記下位のビット列と前記第２定数の下位ビット列を加算して第２の見込み選択肢を生成するステップと、
２つの見込み選択肢のうち、どちらを前記最終段の前のパイプライン段からの入力として選択して次の反復に用いるかを判定するため、前記最終パイプライン段からの前記符号ビットを用いるステップとをさらに有することを特徴とする演算方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は広義にはコンピュータグラフィックスに関し、より詳細にはベクトル発生と線形補間を行なうための特殊なハードウエアに関する。
【０００２】
【従来の技術】
線形補間とベクトル発生はコンピュータグラフィックスにおいてたとえば描線、ポリゴンエッジの計算、テクスチャ・マッピング、画像の拡大・縮小およびシェーディングに用いられる基本的な手順である。線形補間とベクトル発生の使用はコンピュータグラフィックスにおいては実に頻繁に用いられるため、速度が非常に重要になる。グラフィックスプロセッサには1965年にBresenham が発表した古典的なアルゴリズム（Bresenham, J.E, "Algorithm for Computer Control of a Digital Plotter "、IBM Systems Journal 、vol. 4、No. 1 、（1965年）25-30 ページ）を変更したものが用いられることが多い。Bresenham のアルゴリズムでは比較的低速な浮動小数点演算（特に乗算および除算機能）が不要であり、直線の計算を比較的高速な整数加算機能と整数比較機能に軽減する。基本的なBresenhamアルゴリズムでは１組の初期計算を行ない、続いてそれぞれがテスト、分岐、２つの加算命令、およびそのループのオーバヘッドを必要とするループを複数回反復しなければならない。この基本的なBresenhamアルゴリズムのソフトウエアおよびハードウエアによる実施に対する改良が多数提案されている。たとえば、ループが反復されるたびに複数の値が計算されれば、ループオーバヘッドが低減される。米国特許5,025,405 号（Swanson ）には、パイプラインの１つの段において加算の対が同時に計算され、そのパイプラインの次の段で用いられるパイルラインハードウエアシステムが開示されている。米国特許5,280,571 号には、ラインがセグメントに分割され、各セグメントがＮ個のポイントを有し、各ポイントがＮ個のプロセッサの一つにより演算されるマルチプロセッサシステムが開示されている。しかし、さらなる速度の向上が必要とされている。
【０００３】
【発明が解決しようとする課題】
本発明は上記事情に鑑みて成されたもので、線形補間及びベクトル発生の演算を高速に実行することを目的とする。
【０００４】
【課題を解決するための手段】
本発明は加算に要する時間を低減したハードウエアベクトル発生器に関する。ハードウエア加算器のビット長を短くすることによって加算時間が短縮される。加算はパイプライン処理され、最下位ビットが第１の段で計算され、それより上位のビットが下流のパイプライン段で計算される。このベクトル発生アルゴリズムは完了した加算の符号に基づく判断ステップを必要とする。この符号はパイプラインの最終段で生成されるため、パイプラインのそれより前の段が必要とするときには利用できない。したがって、最終段を除く各段では、次の段で使用すべきすべての可能な選択肢が同時に見込計算される。
【０００５】
【発明の実施の形態】
始点（Ｘ0 、Ｙ0 ）と終点（Ｘ1 、Ｙ1 ）を有するベクトルを考察する。一方向オクタントについては、基本Bresenhamアルゴリズムは次の通りである。
ｄｘ  ＝  Ｘ1−Ｘ0
ｄｙ  ＝  Ｙ1−Ｙ0
Ｉ１  ＝  ２＊ｄｙ
Ｉ２  ＝  ２＊（ｄｙ−ｄｘ）
ｄ  ＝  ２＊ｄｙ−ｄｘ
ｘ  ＝  Ｘ0
ｙ  ＝  Ｙ0
ｗｒｉｔｅ（ｘ，ｙ，ｖａｌｕｅ）
ｆｏｒ  Ｘ  ＝  Ｘ0  ｔｏＸ1
ｉｆ  ｄ＜＝０  ｔｈｅｎ  ｄ＝ｄ＋Ｉ１；  ｘ＝ｘ＋１；
ｅｌｓｅ  ｄ＝ｄ＋Ｉ２；  ｘ＝ｘ＋１；  ｙ＝ｙ＋１；
ｗｒｉｔｅ（ｘ，ｙ，ｖａｌｕｅ）
ｎｅｘｔ  Ｘ．
【０００６】
上記から、Bresenhamアルゴリズムの内側のループには方向変数"x "を増分するための簡単な加算器、方向変数"y "を条件付きで増分するための簡単な加算器、および判断変数"d "を計算するための判断能力を有する加算器が必要であることがわかる。本発明はこれらの３つの加算器のそれぞれが要する時間を低減しようとするものであり、特に判断変数"d "の計算に要する時間の低減に関する。
【０００７】
以下の説明では、最終的に得られる回路は構成単位をなす一連のより複雑性の低い回路から得られるものである。まず、図１および図２に本発明において改善しようとする基本的な時間的制約について考察するための簡単な反復加算回路を示す。次に、図３および図４にこの反復加算回路を３段パイプライン構成としたものを示して、ビット長を短くした加算器を用いた反復時間の短縮について説明する。図３および図４の回路はBresenhamアルゴリズムにおける変数"x "および"y "に用いることができる。次に、図５に判断変数"d "を計算するための反復非パイプラインベクトル発生器部を示す。図６および図７には、判断変数"d "を計算するためのパイプラインベクトル発生器部の実施例を示す。図６および図７に示す実施例は３つの段からなるパイプラインを有し、最初の２つの段で同時見込み計算を行なう。最後に、図８に完成した二次元ベクトル発生器を示す。
【０００８】
図１には簡単な反復加算回路を示す。図１において、“I ”は定数であり、“D ”は変数である。“D ”は出力であると同時に入力でもある。それぞれの立ち下がりクロックエッジにおいて、この回路はD(i+1) = D(i) + 1 を計算する。ここで、D(i)はD の古い値であり、D(i+1)はD の新しい値である。Ｎビット加算回路100 は２つの入力“I ”（102 ）およびD(i)（104 ）を有する。この加算器の出力D(i+1)（106 ）はクロックCK（110 ）の次の立ち下がりエッジでレジスタ108 にラッチされ、その後このサイクルが繰り返される。
【０００９】
図２にはクロック信号CK（110 ）のタイミング図を示す。D の１回の反復（たとえばD(i)）がT1（112 ）で完了し、次の反復D(i+1)がT2（114 ）で完了する。時間間隔T2-T1 は主としてＮ個の桁上げビットが加算器100 （図１）内をリップルするのに要する時間によって制限される。加算器100 は、それぞれが２つの入力ビットを加算し、出力ビットと桁上げビットを生成するＮ個の加算器とみなすことができる。加算器100 の全体的出力は最下位ビットの桁上げビットが最上位ビットまでリップルするまでは得られない。加算速度を上げるための設計は多数存在するが、一般には、任意の特定の設計について加算に要する時間は加算されるビットの数が増大するにつれて増大する。そこで、この加算器を細分化して各部をパイプライン処理することによって速度を向上させる方法がある。
【００１０】
図３には、３段パイプライン内の３つのＮ／３ビット加算器として実施された図１のＮビット反復加算器を示す。第１のＮ／３ビット加算器200 はI およびDのＮ／３最下位ビットを加算する。加算器200 の出力の１つは桁上げ出力ビットCO1 （202 ）であり、これはD とともにレジスタ204 によってラッチされ、ラッチされた桁上げ出力ビット206 として提供される。第２のＮ／３ビット加算器208 がこのラッチされた桁上げ出力ビット206 を桁上げ入力として受け取り、I およびD のＮ／３中位ビットとこのラッチされた桁上げ出力ビット206 を加算する。最後に、第３のＮ／３ビット加算器212 がI およびD のＮ／３最上位ビットと中間段のラッチされた桁上げ出力ビット210 を加算する。図３の回路はこのBresenhamアルゴリズムを用いたベクトル発生器において"x "および"y "を増分するための加算器に用いることができる。
【００１１】
図４には図３の回路のタイミング図を示す。以下の説明において、“i-2, i-1, i, i+1”という表記は、たとえば時刻T1（216 ）等の任意の時点を指す。時刻T1（216 ）において、加算器200 がD(i+1)の最下位ビットの計算を開始する。時刻T1（216 ）において、第１の段でラッチされた桁上げ出力ビットＣＯ1(i)（206 ）が第２段の加算器208 に与えられる。時刻T1（216 ）において、第２の段でラッチされた桁上げ出力ビットＣＯ2(i-1)が第３段の加算器212 に与えられる。したがって、T1において、加算器200 はこのパイプライン内の第１段におけるＤLSB (i+1) の計算を開始し、同時に加算器208 はこのパイプライン内の第２段におけるＤISB (i) の計算を開始し、また同時に加算器212 はこのパイプライン内の第３段におけるＤMSB (i-1) の計算を開始する。初期状態から開始する場合、加算器200 は時刻T1で加算を開始し、この加算は時刻T3前には完了しない。初期状態から２クロックサイクル後に、第３段の加算器212 はクロックCK（214 ）の各クロック中のD の新しい反復を完了する、図３および図４の最小反復サイクル時間T2（218 ）−T1（216 ）は図１および図２の最小反復サイクル時間T2−T1より短い。これは、図３の各加算器の内部桁上げリップルはＮ／３ビットに過ぎないのに対して、図１の各加算器はＮビットの内部桁上げリップルを有するためである。したがって、任意の被加算ビット総数Ｎについて、図３の加算器構成のクロック周波数は図１の加算器構成のクロック周波数より高くすることができる。
【００１２】
図５には、このBresenhamアルゴリズムにおける変数"d "の反復計算を行なうための回路の一実施例を示す。図５において、加算器300 は定数I1（302 ）あるいは定数I2（304 ）のいずれかを"d "の前の値（D(i)）に加える。D(i)の符号308 がデジタルマルチプレクサ306 を制御する。マルチプレクサ306 はD(i)の符号308 が負（論理１）である場合加算器300 にI1（302 ）を与え、符号308が正である場合I2（304 ）を与える。
【００１３】
図５の回路を図３に示すような複数段パイプラインに用いる場合を考察する。このパイプラインは初期状態から開始されるものとし、最下位ビットのみについて考察する。第１のクロックサイクルでは、D(0)がわかっており、D(0)の符号からD(1)の最下位ビットについてI1とI2のいずれが必要であるかを決定することができる。しかし、第２のクロックサイクル（図４におけるT2−T3）では、D(1)が必要であるが、D(1)の最上位ビットと符号はまだ得られていない。２段パイプラインの場合、D(1)の符号はラッチされ、第３のクロックサイクルの始めには利用可能であり、３段パイプラインの場合、D(1)の符号はラッチされ、第４のクロックサイクル（たとえば図４におけるT4（222 ））には利用可能であり、以下同様である。２段の例では、本発明によれば必要なときに符号変数が利用できないという問題は、I1およびI2の両方の最下位ビットを第１段におけるD(i-1)の最下位ビットに見込み加算して、D(i)の符号が選択可能になったときその両方の和と桁上げビットを第２段に与えることによって解決される。
【００１４】
ここで、たとえばこのパイプラインが２つより多いものであると仮定する。第３のクロックサイクルの始め（たとえば図４におけるT3（220 ））では、D(2)の符号が必要であるがD(2)はまだ得られていない。３段の場合、本発明によればI1およびI2の両方の最下位ビットを第２のクロックサイクル中の２つの見込みの計算結果のそれぞれに見込み加算し、D(2)の符号が選択可能になったときその結果得られた４つの和と桁上げビットを用いることによってこの問題を解決する。図３に示すような３段パイプラインの場合、D(1)の符号は第４のクロックサイクルの始めには利用可能であり、したがって第３のクロックサイクルにおける４つの見込みの計算結果を２つに減らすことができる（この状態でD(2)の符号が利用可能になるのを待つ）。次に、第４のクロックサイクル中に、再度４つの見込み計算が行なわれD(3)の符号が利用可能になるのを待つ。以下同様である。
【００１５】
図６には同時見込み加算を行なう３段パイプラインベクトル発生回路の第１の段を示す。図示するように、この第１の段は４つの加算器（400 、402 、404 、406 ）を有する。加算器400 の加算出力と桁上げ出力は、D(i)が負であり、D(i+1)が負である条件に対する出力である。加算器402 の加算出力と桁上げ出力は、D(i)が負であり、D(i+1)が正である条件に対する出力である。加算器404 の加算出力と桁上げ出力は、D(i)が正であり、D(i+1)が負である条件に対する出力である。加算器406 の加算出力と桁上げ出力は、D(i)が正であり、D(i+1)が正である条件に対する出力である。D(i)がラッチされ、D(i)の符号420 が得られているがD(i+1)の符号がまだ得られていないある特定の立ち下がりクロックエッジについて考察する。マルチプレクサ408 および410 はD(i)の符号420 によって制御される。D(i)が負である場合、マルチプレクサ408 は負のD(i+1)に対応する２つの加算器（加算器400 および404 ）のうち負のD(i)に対応する加算器（加算器400 ）を選択し、マルチプレクサ410 は正のD(i+1)に対応する２つの加算器（加算器402 および406 ）のうち負のD(i)に対応する加算器（加算器402 ）を選択する。D(i)が正である場合、マルチプレクサ408 は負のD(i+1)に対応する２つの加算器（加算器400 および404 ）のうち正のD(i)に対応する加算器（加算器404 ）を選択し、マルチプレクサ410 は正のD(i+1)に対応する２つの加算器（加算器402 および406 ）のうち正のD(i)に対応する加算器（加算器406 ）を選択する。同様に、D(i)の符号がマルチプレクサ412 および414 が適当な桁上げ出力ビット対（416 および418 ）を選択し、それを次のパイプライン段に与えるのに用いられる。
【００１６】
図７には、この３段パイプラインの最後の２つの段を示す。加算器422 および424 はI1およびI2の両方の中位ビットと前のパイプライン段からの見込み桁上げ出力ビットを同時に見込み加算する。ラッチされた前の状態の１つがD(i)の符号による制御のもとにマルチプレクサ426 によって選択される。同様に、桁上げビットの１つがマルチプレクサ428 によって選択され、最終パイプライン段で用いられる。最後に、最終パイプライン段のマルチプレクサ430 と加算器432 が、図５の単一段回路に桁上げ入力ビットの加算を加えたものと等価な回路構成によって最上位ビットを計算する。
【００１７】
図３、図６、および図７において、３つのパイプライン段は任意に選択したものであり、説明の目的に用いたものに過ぎない。一般に、パイプライン段の数は２からＮ（Bresenhamアルゴリズムにおける変数"d "内のビットの数）までの範囲内の任意の数とすることができる、Ｍ段のパイプラインの場合、第１段は２M-1 個の加算器を有し、第２段は２M-2 の加算器を有し、以下は同様であり、最終段は１つ（２0 ）の加算器を有することに注意しなければならない。図７は段数にかかわりなく最後の２つの段を示すことに注意しなければならない。
【００１８】
最後に、本発明によるBresenhamアルゴリズムを用いた完成されたパイプラインベクトル発生器においては、図６および図７に示すパイプライン回路を用いて、図３に示すような"x"を増分する第１の回路と図３に示すような"y "を増分する第２の回路を制御するのに用いられる符号ビットが生成される。"x "および"y "に対して、図３の定数"I "は（１つの軸に対して）値１（あるいは−１）あるいはゼロである。
【００１９】
図８には完成された二次元ベクトル発生器を示す。上述したBresenhamアルゴリズムは一方向のオクタントにのみ有効であることに注意しなければならない。図８に円502 で示す方向オクタントについては、上述したアルゴリズムはオクタント"０"についてのみ有効である。このオクタントについては、"x "はクロックサイクルごとに増分され、"y "はD(i)が正である場合にのみ増分される。その他のオクタントのためのこのアルゴリズムの変更態様を図８の504 に示す。図８の回路500 には、図６および図７に示すような複数段パイプライン回路を示す。D(i)の符号と方向オクタントによって回路508 の"ＩX "値506 と回路514 の"ＩY "値512 が決まる。回路508 および514 は図３に示すような複数段パイプライン回路である。回路508 は変数"x "の増分値（510 ）を生成する。回路514 は変数"y "の増分値（516 ）を生成する。
【００２０】
以上、本発明を図示および説明したが、開示した態様は本発明を網羅するものでも、またそれを限定するものでもなく、上記の原理に照らしてさまざまな変更が可能である。実施例は本発明の原理とその実際の応用を説明することによって、当業者がその具体的用途に適した実施態様および各種の変更態様で本発明を最もよく利用しうるべく選択および説明したものである。特許請求の範囲には、従来技術によって限定されるものを除き、本発明の他の代替実施例が含まれるものである。
【００２１】
以下、本発明を、その理解のために要約して挙げる。
１．  一方が最終パイプライン段であり、他方が最終段の前のパイプライン段である少なくとも２つのパイプライン段と、
桁上げ入力ビットを受け取り、前記判断変数の最上位ビットを加算し、出力として符号変数（420 ）を生成する、前記最終パイプライン段内の加算器（432 ）と、
前記最上位ビットより下位のビットを加算し、２つの見込み桁上げ出力ビットを生成する、前記最終段の前のパイプライン段内の２つの加算器（422 、424 ）とを有し、
前記最終パイプライン段からの前記符号変数（420 ）が、前記最終パイプライン段に対する桁上げ入力ビットとして受け取られる前記最終段の前のパイプライン段の２つの見込み桁上げ出力ビットのうちの１つを選択するのに用いられるベクトル生成における判断変数の反復生成回路。
【００２２】
２．  反復ベクトル生成における、符号ビット（420 ）、最上位ビットおよびそれより下位のビットからなる判断変数を演算する方法であって、
最終パイプライン段において前記変数の最上位ビットと前記符号ビットとを生成し、
前記最終パイプライン段において桁上げ入力ビットを受け取り、
最終段の前のパイプライン段において前記変数の前記下位のビットの見込みの選択肢を生成し、
前記最終段の前のパイプライン段において第１および第２の見込みの桁上げビットを生成し、
前記最終パイプライン段からの前記符号ビット（420 ）を用いて、前記最終パイプライン段が、前記桁上げ入力ビットとして、前記最終段の前のパイプライン段からの前記第１および第２の見込みの桁上げビットのうちのどちらを受け取るかを決定することからなる方法。
【００２３】
【発明の効果】
以上説明したように、本発明によれば、ハードウエア加算器のビット長を短くすることによって加算時間が短縮されるので、線形補間及びベクトル発生の演算を高速に実行することができる。
【図面の簡単な説明】
【図１】簡略化された反復加算回路を示すブロック図である。
【図２】図１の回路のタイミング図である。
【図３】ビット長を短くした加算器を有する３段パイプライン反復加算回路のブロック図である。
【図４】図３の回路のタイミング図である。
【図５】パイプライン処理を行なわない基本的なベクトル発生回路のブロック図である。
【図６】最初の２つの段で同時見込み加算を行なう３段パイプラインベクトル発生回路の第１段のブロック図である。
【図７】図６のパイプラインベクトル発生器の最後の２つの段のブロック図である。
【図８】完成した二次元ベクトル発生器のブロック図である。
【符号の説明】
100 ：Ｎビット加算回路
108 ：レジスタ
200 ：第１のＮ／３ビット加算器
204 ：レジスタ
208 ：第２のＮ／３ビット加算器
212 ：第３のＮ／３ビット加算器
300 ：加算器
306 ：デジタルマルチプレクサ
400 、402 、404 、406 ：加算器
408 、410 ：マルチプレクサ
412 、414 ：マルチプレクサ
422 、424 ：加算器
426 、428 、430 ：マルチプレクサ
432 ：加算器
500 ：複数段パイプライン回路
【図１】
0003732576.tif 000002
【図２】
0003732576.tif 000003
【図３】
0003732576.tif 000004
【図４】
0003732576.tif 000005
【図５】
0003732576.tif 000006
【図６】
0003732576.tif 000007
【図７】
0003732576.tif 000008
【図８】
0003732576.tif 000009