JPS62297984A - 曲線イメ−ジの可視表示発生装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 ３、発明の詳細な説明 産業上の利用分野 本発明は、コンピュータ・グラフィック表示装置上に曲
線を発生させる装置に関する。

来術力点 コンピュータの技術革新によって、コンピュータにより
発生されるグラフィック情報の表示に関する技術領域が
生じてきた。この領域はコンピュータ・グラフィックと
呼ばれる。コンピュータ・グラフィックにおいて共通的
に用いられる１つの技法は、−組の点を発生しそしてこ
れらの点を結んで直線を生じる技法である。点の組合わ
せ及び直線は、通常陰極線管であるコンピュータ・グラ
フィック端末表示装置上に表示される。又、表示画面上
の成るいくつかの点に対する曲線を発生することが望ま
れている。グラフィック表示画面上におけるなめらかな
曲線の発生は、データ・ポイントのいつくかのグループ
に対して低次の多項式関数を当てはめることにより行な
われる。その結果生じる断片的につなげられた多項式関
数は連続的曲線のようになるが、特殊な場合を除き曲線
の小部分相互間の接続部において不連続性が生じる。

この技法は、雲型曲線の所望部分を用いて曲線を描く製
図と似ている。製図者はいくつかの点に合う雲量定規の
曲線を選びそしてこの部分の曲線を描く。そして製図者
は、全ての点を統合する迄この手順を繰り返して曲線を
完成する。コンピュータ・グラフィックにおいては、連
続した低次の多項式関数式をいつくかの点に当てはめて
位置座標系における曲線値を発生することにより同じ結
果を得る。

２次元空間では、しばしば曲線は、直交成分Ｘ及びｙの
関数として即ちＹ＝ｆ（ｘ）として表わされる。３次元
座標系においては、Ｘ、　ｙ及び２座標は、直交成分の
１つ若しくは２つの関数として表わされる。しかしなが
ら、このように表わすと、座標値の発生において固層が
生じる。１つの代替技法は、曲線のパラメータ値を用い
ることであり、ここで曲線上の各座標値はいくつかの共
通変数の関数として、即ち全座標成分に共通な変数とし
て表わされる。３次元系に対しては、このような変数は
、Ｏ＜ｔ＜１に対してｘ＝ｆ　　（ｘ）、ｙ＝ｇ　（ｔ
）及びｃ＝ｈ　（ｔ）を与えるｔとして説明されること
ができる。他の表わし方は、次の３次の多項式関数によ
り表わされるパラメータ立体曲線である。

ｘ＝ｆ（ｔ）＝ａｘｔ’＋ｂｘｔ”＋ｃｘｔ＋ｄｘｙ＝
ｇ（ｔ）＝ａ　ｙ　ｔ’＋ｂ　ｙ　ｔ２＋ｃ　ｙ　を十
ｄ　ｙｚ＝ｈ（ｔ）＝ａ　ｚ　ｔ’＋ｂ　ｚ　ｔ”＋ｃ
　ｚ　を十ｄ　ｚ曲線セグメントの低次式が、位置及び
傾斜の連続性を与えずそして２つの曲線成分が合う点て
傾斜及び曲率の連続性を与えないので、立体曲線は重要
である。立体曲線は又、３次元において非平面曲線を描
く低次の曲線である。

上述のＸ座標に対する式は次のマトリクス型で表わされ
ることができる。

係数ベクトル［Ｃｘ］は多くの異なる特性の曲線を生じ
るように決められ得る。最も有用なのは、Ｈｅｒｍｉｔ
ｅ型、ベライエ型及びＢ−スプライン型である。係数ベ
クトルを、列幾何学ベクトル（ｃｏｌｕｍｎａｒ　（ｅ
ｏｍｅｔｒｙ　ｖｅｃｔｏｒ）　　［ＧＭコにより乗算
された４×４の基本マトリクスのクロス積に変えること
ができる。

これらの曲線の型についての一般的理論は、１９８２年
にＡｄｄｉｓｏｎ−Ｗｅｓｌｅｙ　Ｐｕｆｌｉｓｈｉｎ
ｇ社により発刊されたＪ　、　Ｄ　、　Ｆｏｌｅｙ及び
Ａ、Ｄａｎ　ＳａｗによるＦｕｎｄａｍｅｎｔａｌｓ　
ｏｆ　Ｉｎｔｅｒａｃｔｉｖｅ　ＣｏｍｐｕｔｅｒＧｒ
ａｐｈｉｃｓ、　１９７９年にＭｃＧｒａｗ−Ｈｉｌｌ
　Ｂｏｏｋ社により発刊されたＷ　、　Ｎ　、　Ｎｅｗ
＋＋＋ａｎ及びＲ，Ｆ。

５ｐｒｏｕｌｌによるＰｒ１ｎｃｉｐｌｅｓ　ｏｆ　Ｉ
ｎｔｅｒａｃｔｉｖｅＣｏｍｐｕｔｅｒ　Ｇｒａｐｈｉ
ｃｓ第２版及び１９７４年にＡｃａｄａｍｉｃ　Ｐｒｅ
ｓｓから発刊さ九たＲ　、　Ｅ　、　Ｂａｍｈｉｌｌ及
びＲ、Ｆ　、ＲｉｅｓｅｎｆｅｌｄによるＣｏｍｐｕｔ
ｅｒ　ＡｉｄｅｄＧｅｏｍｅｔｒｉｃ　Ｄｅｓｉｇｎに
示されている。

本発明の一実施例はＢ−スプライン型から曲線を発生す
る。Ｂ−スプライン型は、　Ｆｕｎｄａｍｅｎｔａｌｓ
ｏｆ　Ｉｎｔｅｒａｃｔｉｖｅ　Ｃｏｍｐｕｔｅｒ　Ｇ
ｒａｐｈｉｃｓ、第５２１Ａ＋５２３頁に説明されてい
る。

スプラインを用いてグラフィックを発生する１つの技法
は、ＩＢＭテクニカル・ディスクロジャ・ブレティン、
第２５巻Ｎｏ、１　ｌｂの論文“ＨｉｇｈＳｐｅｅｄｓ
　ｆｏｒ　Ｇｅｎｅｒａｔｉｎｇ　ｏｒ　Ｕｐｄａｔｉ
ｎｇ　ＧｒａｐｈｉｃｓＳｐｌｉｎｅｓ　ｏｎ　ａ　５
ｃｒｅｅｎ”に示されている。この技法は、多項式関数
を評価するために正確な積分を用いるアナログ計算機に
よる具現化を示している。

ディジタル・プロセッサを用いると、座標値を計算する
ためにマトリクス演算動作を計算するために浮動小数点
演算が要求される。この浮動小数点演算が要求されると
いうことは、（１）これが時間がかかるということ及び
（２）全体的に正確でないということにより不利である
。不正確性は、浮動小数点動作を反復して行なうことが
必要であることから生じる。その性質により単一不動点
動作は不正確であり小さな誤りを生じる。この小さな誤
りは、１つの浮動小数点動作の結果が次の浮動小数点動
作において用いられる毎に複合される。

従ってこの性質から、一連の浮動小数点動作の結果誤り
が累積する。

間　点を解　するための手 本発明の主な目的は、従来の浮動小数点技法におけるよ
りも正確な方法でＢ−スプラインを用いて曲線を与える
方法及び装置を提供することである。

本発明の他の目的は、Ｂ−スプライン曲線を発生するた
めの高速な方法及び装置を提供することである。

本発明に従うと、−組のコントロール・ポイント入力か
ら表示画面上に曲線イメージの可視表示を発生する方法
が実現される。−組のコントロール・ポイントは、曲線
に対する次元毎の入力である。更に、多数の間隔が指定
される。この間隔の数は、各コントロール・ポイント相
互間で計算されねばならない曲線座標値の数を規定する
。この方法は、（１）次元に対する１組の入力コントロ
ール・ポイントからそって成るスケーリング・ファクタ
から各次元毎の一組のスケールされたベクトル係数の整
数を計算するステップ、（２）各間隔に対する各次元毎
の前進差分（ｆｏｒｗａｒｄｄｉｆｆｅｒｅｎｃｅ）間
隔係数整数を間隔整数及びその次元に対するスケールさ
れたベクトル係数整数から計算するステップ、（３）各
次元に対する各間隔毎の曲線座標値をスケーリング・パ
ラメータ並びにその次元及び各間隔に対する前進差分間
隔係数整数から計算するステップ、そして（４）各次元
毎に上記計算された曲線座標値に従う曲線座標点及び上
記計算された曲線座標点を連続的に接続する複数値の直
線を表示するステップを含む。

本発明に従い曲線イメージの可視表示を発生する装置は
、曲線イメージを規定する複数個のデータ点即ち制一点
及びこれらの制御点相互間の間で行なわれる計算の数を
表わす間隔の数を受取る入力手段を有する。又、上記装
置は、各間隔に対して各次元毎の曲線座標値を発生する
処理回路を有し、そしていくつかの間隔に対する曲線座
標値の計算は同時に行なわれる。更に上記装置は、各次
元毎に上計算された曲線座標値に従う曲線座標点及びこ
れら計算された曲線座標点を連続的に接続する複数個の
直線を表示することによって、曲線イメージの可視表示
を生じる表示回路を含む。

本発明では、整数演算を用いるベクトル係数の計算が行
なわれる。整数演算は、スケールされた値を計算に用い
ることから生じる。言い代えると、元の値は、曲線座標
値を計算するのに行なわれるベクトル係数の計算及び他
の全ての計算が整数演算でなされるようにスケール（ｓ
ｃａｌｅ）される。

ここで、スケールとは、２進乗算を指しこれは左方向へ
のシフト動作により行なわれ、モしてディスケールとは
２進除算を指しこれは右方向へのシフト動作により行な
われる。このことは、計算に用いる初期パラメータをス
ケールし、そして計算プロセスの最後のステップに除算
を行なうことにより行なわれる。整数演算の使用は、計
算の速度と正確性を増大する。更に、計算は間隔につい
て行なわれるので、これらの計算は、いくつかの計算ス
テージが同時に行なわれ得るパイプライン型のいくつか
のステージにおいて行なわれ得る。

本発明において、整数演算の乗算動作は、２進のシフト
動作により行なわれる。本発明の装置において、計算を
パイプライン型で行なうように一連のレジスタと直列に
配置されている複数個の加算器により加算動作が行なわ
れる。シフト動作はレジスタ相互間を接続するパス（接
続器）において行なわれる。良好なる実施例において、
最後の計算ステージは、浮動小数点動作ではなく、２進
シフト及び加算のみを必要とする近似除算法（ａｐｐｒ
ｏｘｉｍａｔｅ　ｄｉｖｉｓｉｏｎ　ｍｅｔｈｏｄ）に
より行なわれる。２進シフト及び加算動作は、直列型に
配列されたレジスタ及び加算器にデータをシフトしてパ
イプライン動作を促進する装置により具現化される。

ヌＪＬ性９」１升 第１図には、コンピュータ・グラフィック・ユニットの
ブロック図が示されている。プロセッサには入出力母線
１０に接続されている。プロセッサには、このシステム
の中心をなし、そして入力回路１８からのユーザ入力を
変換して表示回路１６にグラフィック表示を発生させる
全ての処理動作を行なう、又、メモリ１４が入出力量Ａ
Ｉ！１０に接続され、そしてデータ及びアドレスのため
の一時記憶装置として働らき、そしてコンピュータ・グ
ラフィック・タスクを行なう場合にプロセッサ１２によ
り実行されるソフトウェア・インストラクションを記憶
する。

Ｂ−スプライン型を具現化して曲線を発生する１つの技
法は、座標点に対する一組のパラメトリック増分値を発
生することである。このような１つの技法は、Ｂ−スプ
ライン前進差分法として知られている。前進差分法は、
前記刊行物Ｐｒ１ｎｃｉｐｌｅｓ　　ｏｆ　　Ｉｎｔｅ
ｒａｃｔｉｖｅ　　Ｃｏｍｐｕｔｅｒ　　Ｇｒａｐｈｉ
ｃｓの第３２６−３２９頁において検討されている。

前進差分法は、座標値を近似化する技法である。

この増分技法を用いて、Ｂ−スプライン曲線の座標値を
計算することができる。このようにして１つの完成され
たＢ−スプライン曲線は一組の座標値として指定される
ことができる。座標値は、座標系内の曲線のポイントを
規定するように組合わされることができる。言い代える
とＢ−スプライン前進差分法を用いて、全ての直交成分
（例えば、ｘ、ｙ及び２）に対する座標値は計算されそ
して結果的な座標系内の曲線を表わす。

結果的な曲線がこの曲線を指定するのに用いられるポイ
ントを通過しないように位置されることがＢ−スプライ
ン型の特徴である。従って、ユーザが複数の指定ポイン
トに曲線を通過させることを望むシステムでは、補間ス
プライン技法が用いられる。この技法は、前記刊行物Ｃ
ｏｍｐｕｔｅｒ　ＡｉｄｅｄＧｅｏｍｅｔｒｉｃ　Ｄｅ
ｓｉｇｎの第３１７乃至３２６頁に説明されている。補
間スプラインを用いることにより、ユーザが入力したポ
イントは、Ｂ−スプライン曲線を規定するのに用いられ
るコントロール・ポイントに変換される。しかしながら
、本発明は、コントロール・ポイント即ち制御点として
指定されるＢ−スプライン曲線を対象とする。

前述の如く、本発明の良好な実施例は、Ｂ−スプライン
型の曲線の発生の具現化に関する。Ｂ−スプライン曲線
を形成する１つの方法は、次元（ｄｉｍｅｎｓｉｏｎａ
ｌ）座標の夫々に対して次式を用いる。

ｘ（ｔ）＝［ｔ３　ｔ”ｔ　　１１　　［１／６コパラ
メータ・ベクトルＰ この等式は各座標値毎に即ちｙ　（ｔ）そして必要なら
ばｚ　　（ｔ）毎に解かれることに注目されたい。上式
において、Ｐｉ−１、Ｐｉ−Ｐｉ＋１、及びＰｉ＋２は
、Ｂ−スプライン制御点のＸ軸の座標を表わす。Ｂ−ス
プライン制御点は、第２図で点２０．２２．２４及び２
６として示されており、これらは集合的にＢ−スプライ
ン曲線３０を規定する。前述の如く、Ｂ−スプライン曲
線３０は、制御点２０．２２．２４及び２６のどれをも
通過しない。以下の本発明についての説明では、ユーザ
が制御点を指定することにより所望のＢ−スプライン曲
線セグメントを指定するものと仮定する。しかしながら
、ユーザは、曲線を通過させたい点を指定することもで
きる。前述の如く、通過点を制御点に変換するために補
間スプライン技法を用いることができる。従って、この
ようにして、コンピュータは、製図技師が雲型定規を用
いるのと同様にして一組の点に複数の曲線を当てはめる
ことができる。

Ｂ−スプライン技法及び置型定規技法のいづれも、１つ
の曲線セグメントを規定する小数の点を用い、そしてこ
れらの点を用いて複数セグメントを接続して連続曲線を
生じるという点で、Ｂ−スプライン技法を置型定規技法
と同等に捕えることは適切である。

第１図を参照するに、ユーザは、例えばキーボードの如
き入力装置を介して制御点のアレイを入力する。これら
の制御点はメモリ１４に記憶される。次いでプロセッサ
１２は、メモリ１４に記憶されるいる一組のインストラ
クションを実行して一組の曲線座標点を発生する。これ
らの曲線座標点は次いで直線により接続されて曲線イメ
ージを発生する。そしてこの曲線イメージは、例えば陰
極線管の如き表示回路１６上に表示され、ユーザはこれ
を見ることができる。もしも制御点の数そしてこれら制
御点相互間の曲線座標値の計算を規定する繰返しの数が
非常に多いならば、ユーザは表示回路１６に表示される
曲線イメージの点を接続する直線セグメントを殆ど認識
しない。従って曲線イメージは連続的曲線として表示さ
れる。プロセッサ１２により実行されるソフトウェア・
インストラクションは第３Ａ及び３Ｂ図のフローチャー
トに示されている。第３Ａ及び３Ｂ図に示されているソ
フトウェアは、指定された複数の制御点相互間の曲線座
標値を計算する前進差分法を行なう、特に、前進差分法
に対して行なわれる演算が整数演算であるように計算は
縮められている。

後掲の補足説明Ａは、基本的な３次元Ｂ−スプライン・
マトリクス式の詳細を示し、そして浮動小数点を用いそ
して整数を用いる前進差分法について検討する。第３Ａ
図のフローチャートは、開始ステップ４０で始まり、次
いで外側ループ・カウント・ステップ４２を開始する。

次のステップは決定ステップ４４であり、現在のＩのカ
ウントが、量ＮＵＭＰＴＳ−３により小さいか否かを調
べる。

このソフトウェアにおいて、ＮＵＭＰＴＳは入力さ九終
えた制御点の数である。ソフトウェアはこれらの制御点
をアレイＰとして参照する。計算の間、４のグループ内
の制御点がＢ−スプライン・セグメントを計算するのに
用いられる。従ってステップ４８において、変数ＰいＰ
２、Ｐ、及びＰ４は、セグメントの計算のための４つの
連続する制御点に等しくセットされる。次のステップ４
９は、実際のＢ−スプライン・セグメントを計算する。

Ｂ−スプライン・セグメントの計算は、第３Ｂ図のフロ
ーチャートに示されている。Ｂ−スプライン・セグメン
トが計算され終えると、ステップ５０において外側ルー
プ・カウントＩが歩進され、そして決定ステップ４４が
実行される。■が入力制御点の数−３より大きいならば
、このプログラムは終了ステップ４６で示すように終了
する。

第３Ｂ図を参照するに、このプログラムは開始ステップ
６０において開始され、次いでステップ６２の初期設定
ステージが行なわれる。Ｎ２、Ｎ３及びＤＥＮＯＭが初
期設定される。Ｎ２は、Ｎ十Ｎに等しくセットされ、こ
こでＮ　＝　Ｌｏｇｚ　（Ｎ　Ｌ　）であり、そしてＮ
Ｌは、計算されるべき間隔の数である。Ｎ３はＮ２＋Ｎ
に等しい。Ｄ　Ｅ　Ｎ　ＯＭ（分母、ｄｅｎｏｍｉｎａ
ｔｏｒ）は、６をＮ３だけ左ヘシフトしたのに等しくセ
ットされる（記号くくは左シフトを示す）。ＤＥＮＯＭ
は、６による除算動作を整数スケール乗算（Ｎ３）と組
合わせるスケーリング・パラメータである。ＤＥＮＯＭ
の除算を最後のステップ迄遅らせることにより、残りの
ステップの乗算及び加算は整数演算で行なわれることが
できる０次のステップ６４は、基本マトリクス（Ｍ）及
び幾何学（ｇｅｏｍｅｔｒｙ）ベクトル（Ｇ）のクロス
積から計算される幾何学ベクトル係数ベクトルＣａ、ｂ
、ｃ及びｄ］を計算する。変数Ｐ１、Ｐ２、Ｐ３及びＰ
４は、第３Ａ図のステップ４８で入力された制御点であ
る。ステップ６４において、成る数による成る変数の左
シフトは、この数の２進乗算に等しい。ステップ６６に
おいて、初期の前進差分値が計算される。これらの値は
、Ｄｉ（第１差分）、Ｄ２（第２差分）、Ｄ３（第３差
分）及びＦ（実際のスプライン座標値の関数結果）を含
む、更に、第１曲線座標値Ｓ［０コがＦ／ＤＥＮＯＭと
して計算される。前進差分値ＦはＤＥＮＯＭパラメータ
により除算され、そしてこれは同じ動作において１６に
よる除算及びディスケール（ｄｅｓｃａｌｉｎｇ）を行
なう。この除算は、プロセッサにおける整数除算動作に
より行なわれてもよく又は、他の実施例のように除算近
似技法により近似化されることもできる。

次のステップ６８は、内側ループのカウント（計数）を
１に初期設定する。内側ループは次いでステップ７ｏに
入り、ＪがＮＬより小さいか否かが調べられ、これは実
際の入力繰返し数である。

ＮＬは、制御点相互間で行なわれるべき曲線座標値の計
算の数言い代えると内側ループで行なわれるべき計算の
数を指定する入力値であることを理解されたい、内側ル
ープはステップ７０．７４．７６及び帰還線７８より成
る。ステップ７０の後、ステップ７４が行なわれて、次
の前進差分値及び曲線座標値Ｓ　［Ｊ］を計算する。ス
テップ７６において、Ｊが歩進されそしてステップ７０
が繰り返される。この内側ループは、Ｊが繰り返しの数
に等しくなる迄実行される。次いでこのループは線７１
を介してステップ７３に進み、そしてプロセッサの動作
を第３Ａ図のステップ５０に復帰させる。

第３Ａ及び３Ｂ図のソフトウェアは、各座標即ちＸ、Ｙ
及び必要ならばＺ毎に実行されねばならないことを理解
されたい、良好なる実施例においては、行なわれるべき
繰り返しの数（Ｎ　Ｌ）は３２に等しい。又、前述の如
く、除算動作は、後掲の補足説明Ｂに示されている除算
近似技法により行なわれることができ、第３Ａ及び３Ｂ
図に示すソフトウェアのパフォーマンスに対する整数除
算動作の必要性を全体的に排除する。

第４図は本発明の他の実施例のブロック図である。第４
図において、プロセッサ８２は、メモリ８４及び入力装
置８６と共に入出力母線８０に接続されている。表示回
路９６も又線９４を介して入出力母線８０に接続されて
いる。更に、曲線発生回路９０が線８８により入出力母
線８０に接続され、そして線９．２−を介して表示回路
９６に接続されている。第４図のこの装置の通常の動作
において、ａ９４は、表示回路９６を初期設定するのに
用いられる。曲線イメージの入力は１曲線発生回路９０
から線９２を介して表示回路９６に直接入力される。第
４図の実施例は、ソフトウェア実行の多くをプロセッサ
８２から取り、動作速度を高めている。

第Ｓ図は、第４図の曲線発生回路９０のブロック図であ
る。第５図において６、シーケンサ（順序制御回路）１
０９が設けられ、これは、１１１４ｂを介して加算器１
２５をそして線１１４ａを介してシフト回路１２０を制
御する。線１１４ｂは、線１１６及び１２２からの内容
を加算するように若しくは線１２２の内容を通過するよ
うに加算器１２５を制御する。更に、シーケンサ１００
は、レジスタ・ファイル１０８を制御する。レジスタ・
ファイル１０８は、入出力母線８０に接続され、Ｄｌ、
Ｄ２、Ｄ３及びＦの初期値を受けとる。ループ・カウン
タ１０８が線８８ｂを介して入出力母線８０に接続され
そして線１０２を介してシーケンサ１００にループ・カ
ウントを送る。更に、シーケンサ１００は、市販型の描
線回路１３０に対し線１１０及び１２０を介して制御イ
ンターフェイスを与える。描線回路１３０は、ラッチ１
２４から４１１２６を介して出力を受けとる。ラッチ１
２４内の値は、加算器１２５の出力である。描線回路上
３０は、曲線を規定する各曲線座標値を受けとる。更に
、描線回路１３０は、線の値を計算し、これは曲線座標
値により規定されるこれらの曲線点を変換する。線及び
点の組合わせは、表示装置上の各画素のオン・オフ状態
を規定する。

描線回路１３０は、画素データをバッファ・メモリ１３
２へ与え、そしてこの画素データは［９２を介して表示
回路へ送られ、最終の曲線イメージを表示する。

シーケンサ１００、ループ・カウンタ１０４、レジスタ
・ファイル１０８、シフト回路１２０及び加算器１２５
は、ステップ７４で計算された前進差分値、ステップ７
４の曲線座標値（Ｓ　［Ｊ］　）並びにステップ７０及
び７６のループ・カウンタ制御関数を計算するように構
成されている。従って、プロセッサ８２は、初期幾何学
ベクトル係数及び初期前進差分値を計算することにだけ
を必要とする。入出力母線８０から線８８ａを介して初
期前進差分値をレジスタ・ファイル１０８に記憶した後
、プロセッサ８２はループ・カウンタ１０４を開始させ
、そしてシーケンサ１００は、各間隔毎の前進差分値及
び結果的な曲線座標値の計算を自動的に開始する。これ
らの値は、ｍ１２６を介して描線回路１３０への入力で
ある。線１１２はシーケンサ１００により用いられ、線
１２６上の値が入力の準備がととのったことを描線回路
１３０に合図する。描線回路１３０は、Ｉ！ｌｌＯを介
して、待ち信号をシーケンサ１００に送り、この描線回
路１３０が準備完了となる迄曲線座標値の計算を遅延す
る。この実施例では、最後の除算動作は、後掲の補足説
明Ｂに示す近似除算技法（ａｐｐｒｏｘｉｍａｔｅ　ｄ
ｉｖｉｓｉｏｒｉ　ｔｅｃｈｎｉｇｕａ）により行なわ
れる。この技法を用いるに当っては、シーケンサ１００
の制御のもとにシフト回路１２０が最終座標値を計算し
、そしてこの値が線１２６を介して描線回路１３０へ入
力する迄ラッチ１２４に記憶されることを必要とする。

第５図の回路は各座標軸毎に反復されること又は第５図
の回路における計算がこれら座標軸毎に繰り返されねば
ならないことを理解されたい。

第６Ａ及び６Ｂ図は、第４図の曲線発生回路９Ｏの第２
の実施例である。再びこの回路も、第３Ｂ図のステップ
７４で計算された前進差分値及び曲線座標値並びにステ
ップ７０及び７６のループ・カウンタ制御関数を計算す
る。第６Ａ図を参照するに、制御論理回路１５５は線１
５３を介してループ・カウンタ１５１に接続され、そし
て、ｍ１ｓ７に制御信号を発生する。線１５７は、レジ
スタ１５０．１５６．１６０及び１６６を制御する。

最初、レジスタ１５０には線８８ｃを介して値Ｄ３がつ
め込まれる。レジスタ１５６には第３のループ繰り返し
のための値Ｄ２がつめ込まれる。レジスタ１６０には、
第２のループ繰り返しのための値Ｄ１が線８８ｅを介し
てつめ込まれる。レジスタ１６６には、線８８ｆを介し
て、最初のループ繰り返しのための値Ｆがつめ込まれる
。レジスタ１６６の出力は必要ならば線８８ｇを介して
プロセッサ８２に送り返される。線１７０の出力は、補
足説明Ｂの近似除算技法を行いそしてクロック・サイク
ル毎に結果を生じる回路に送られる。　この近似除算回
路は第６Ｂ図に示されている。線１７ｏ上の値Ｆはレジ
スタ１７２及び１７４に入力される。これらは、シフト
された値を受けとるレジスタである。レジスタ１７２は
３つの２進位置だけ右にシフトされたＦの値を受けとる
。レジスタ１７４は、５つの２進位置だけ右にシフトさ
れたＦの値を受けとる。レジスタ１７４の内容は、レジ
スタ１７２の内容と共に加算器１７６につめ込まれる。

レジスタ１７４の内容は又レジスタ１８０につめ込まれ
る。加算器１７６はレジスタ１７８に出力を与え、この
レジスタはＦ／８＋Ｆ／３２の部分的な商を含む。レジ
スタ１８０の内容は右へ２つの２進位置だけシフトされ
そしてレジスタ１７８の内容と共に加算器１８２に与え
られる。加算器１８２からの結果はレジスタ１８４に与
えられ、そしてこれはＦ／８＋Ｆ／３２＋Ｆ／１２８の
部分的な商である。レジスタ１８０の内容はレジスタ１
８６に入力され、そして２つの２進位置だけ右にシフト
される。再び、レジスタ１８６の内容はレジスタ１８４
の内容と共に加算器１８８で組合わされて、レジスタ１
９０に入力され、これはＦ／８＋Ｆ／３２＋Ｆ／１２８
＋Ｆ１５１２の部分的な商である０次いで、レジスタ１
８６の内容はレジスタ１９２に入力されて右に２つの２
進位置だけシフトされる。レジスタ１９２の内容はレジ
スタ１９０の内容と共に加算器１９４に入力されスケー
ルされた商を生じる。丸めは加算器２００において行な
われ、これはレジスタ１９６内のスケールされた商の第
１５番目”のビットを取り出してそしてこれを、レジス
タ１９６の内容を右に１５の２進位置だけシフトした値
に加算する。加算器２００の出力はレジスタ２０２に入
れられる。前述のように、この曲線座標値は線２０５を
介して描線回路２０４に与えられる。次いで、描線回路
は全座標軸に対するこれら曲線座標値を組合わせて曲線
座標点及びこれらの点を結ぶ線を発生する。これらのデ
ータは、画素情報としてバッファ・メモリ２０６に送ら
れ、そしてこれはイメージ・データを線９２を介して表
示回路９６（第４図）に供給する。

本発明を、前述の特定な実施例を参照して説明したがこ
れに本発明が限定されるものではない。

凡豆曵羞果 Ｂ−スプライン曲線の発生において、整数演算を用いる
ことにより計算の速度及び正確性を増大する。

逓ｆｆ１ ３次元Ｂ−スプラインは、コンピューダグラフィックス
の断片的な多項式関数である。曲線を指定するには数多
くの方法があるが、有用な公式は、Ｊ　、［）　、　Ｆ
ｏｌｅｙ及びＡ　、　Ｖａｎ　Ｄａｍによる本“Ｆｕｎ
ｄａａ＋ｅｎｔａｌｓ　ｏｆ　　Ｉｎｔｅｒａｃｔｉｖ
ｅ　Ｃｏ＋５ｐｕｔｅｒＧｒａｐｈｉｃｓ”の第５２１
及び５２２頁に示されている。これは次のようなマトリ
クス式を生じる。

ｘ　（ｔ）＝　［ｔ３ｔ”ｔｌｌ　　［１／６］変数ｔ
はＯから１の範囲のパラメトリック変数であり、そして
変数ＰはＢ−スプライン制御点のＸ軸座標を表わす。（
１／６）の値はスカシでありマトリクス表現のどの場所
へも動かし得る。さし当り（１／６）のスカラ項を無視
して、マトリクス乗算及び項を集めると次のような３次
式が得られる。

（ｔ３）　　（−Ｐ、　　＋　３Ｐ、−３Ｐ□＋ｔ＋　
Ｐ□＋２）＋　（ｔ”）　　（３Ｐ、１−６Ｐｉ＋３Ｐ
ｉ＋１）＋（ｔ）　　（−３Ｐ□−１＋３□＋１）＋　
　　　　（ｐニー１＋４Ｐｊ十Ｐｉ＋１）煎１」しど衷 ３次元式の１１準型は次の如くである。

ａ　ｔ”＝ｂ　ｔ”＋ｃ　ｔ＋ｄ＝０ Ｗ、　Ｍ、　Ｎｅｓ＋＋＋＋ａｎ及びＲ，Ｆ、５ｒｏｕ
ｌｌによる本“Ｐｒ１ｎｃｉｐａｌｅｓ　ｏｆ　Ｉｎｔ
ｅｒａｃｔｉｖｅ　Ｃｏｍｐｕｔｅｒにｒａｐｈｉｃｓ
”第２版には、３次元多項式関数を前進差分するための
次の方法が検討されている。ｔの間隔（インターバル）
の寸法が等しいものとし、そして評価が１＝０で開始す
るものとすると、その次の点はわずか３回の加算を伴な
うだけで求められることができる。このことは周知であ
るが、前進差分法が浮動小数点の計算を必要とするため
に余り用いられない、しかしながら、前進差分法は、ス
ケールされた整数に拡張されることができる。これは、
浮動小数点の前進差分法が累積的な丸めの誤差のために
数字的に不安定な計算を引き起こすという欠陥を除去す
る。前記Ｎｅｗ＋ｏａｎ及び５ｐｒｏａｌｌの本の第３
２７及び３２８頁によると、初期条件は次の如くである
。

ｐ＝ｄ α１＝ａδ’＋ｂδ”＋ｃδ αよ＝６ａδ’＋２ｂ５” α、＝６ａ８３ 反復関係は次の通りである。

ｐ＝ｐ＋α１ α□＝α、＋α２ α２＝α２＋α３ 変数δは１　／　ｎであり、ここでｎはｔにおける間隔
の数である。Ｂ−スプライン曲線上の点のＸ軸座標に対
する計算がなされ、そして次いで対応するＸ軸座標に対
してなされる。例えば、次の値が制御点のＸ軸座標に対
して選択される。

Ｐ　ｉ　−１＝　１０　；　Ｐ　ｉ　＝　５、Ｐｉ＋１
＝９　；Ｐｉ２＝２０ １＝０の時、ｘ　（ｔ　）　＝　３９　／　６　＝　６
　、５ｔ＝ｏ、ｌの時、Ｘ　（ｔ）＝３８．９６８／６
＝：６．４９５ 前進差分法において６で除算する計算は最後に行なわれ
、従って前進差分された多項式関数の結果値は６倍とな
り大きくなる。

２動小数伝前進差　法 浮動小数点前進差分法を次式の多項式関数の結果に適用
すると、 Ｐ＝３９ 実際の点はＣＰ／６）即ち（３９／６）＝６．５α、＝
＝　（−２）（，１３）＋　（２７）（，１”）＋　（
−３）（，１）＝−０，０３２ α、＝　（６）（−２）（，１’）＋　（２）（２７）
（，１”）＝０．５２８ α、＝（６）（二２）　　（，１３）＝−０，０１２ｔ
＝０．１に対する反復関係は次を生じる。

Ｐ＝３９＋（−０，０３２）＝３８．９６８実際の点は
（３８，９６８／６）区６・、４９５α、＝　（−０，
０３２）＋　（０，５２８）＝０．４９６ αｚ＝　（０−５２８）＋　（０，０４２）＝０．５１
６ 多項式関数の次の点はｔ＝０．２においてでありそして
結果は次の如くである。

Ｐ＝３８．９６８＋（０，４９６） ＝３９．４６４ 実際の点は（３９，４６４／６）徨６．５７７α１＝　
（０，４９６）＋　（０，５１６）＝、１．０１２ α、＝　（０，５１６）＋　（−０，０１２）＝０．５
０４ スケールされた綻゛差分法 スケールされた前進差分法式の適用は、浮動小数点前進
差分法への簡単な拡張である。スケールされた前進差分
は、下記のようにすると、ｅ＝　［（０，１）（１０）
］　”＝１ｆ＝　［（０，１）（１０）］”　（１０）
＝１０ｇ＝　　［（０，１）　　　（１０）　　コ　　
（１０）”＝１００次のようになる。

ｐ＝［（３９）　　　（１０’）　　コ／［（６）　　
　（１ｏ３）　　］＝６．５ ａｌ−（２）（ｅ）＋　（２７）（ｆ）＋（−３）（ｇ
）＝−３２ α、＝　（６）（−２）（ｅ）＋　（２）（２７）（ｆ
）＝５２８ α３＝　（６）（２）（ｅ）＝　　１２ｅ、ｆ及びｇの
値は、スケールされた整数前進差分に対するキーである
。もしもｎが間隔の数であるならば次のようになる。

ｅ＝１ ｆ＝ｎ ｇ＝　ｎｚ 共通分数はｎ３である。

これは全体の表現に対する共通な分母を得る簡単な方法
であり、従って各点が計算されるにつれて、これは１つ
の値で除算することによりスケールを戻される。例示の
場合には、共通項は１０００である。これは間隔の数即
ちｎの３乗であり、そしてこの例の場合にはｎの値は１
０である。６による除算は、元のマトリクス表現のスカ
シを説明し、そしてこの除算動作は、ｘ　（ｔ）の正し
い値が計算されるように行なわれねばならない。

ｔ＝０．１に対する反復関係は次を生じる。

ｐ＝　（３９０００−３２）＝３８９６８実際の点は（
３８９６８／６０００）凶６．４９５α、＝　（−３２
）＋　（５２８）＝４９６α、＝　（５２８）＋　（−
１２）＝５１６除算が最後の動作で行なわれるのでスカ
シはスケールされねばならないことに注目されたい。

多項式関数の次の点はｔ＝０．２においてでありそして
次のスケールされた前進差分式を生じる。

Ｐ＝［３８９６８＋（４９６）コニ３９４６４実際の点
は（３９４６４／６０００）　　６．５７７α１＝　（
４９６）＋　（５１６）＝１０１２α、＝　　（５１６
）＋　　（−１２）＝５０４スケーリングに対して任意
の基数が選択されることができる。スケーリングが一連
のシフトにより行なわれるように２のべきが適切である
。６による最後の除算が遅らされるので、２のべきによ
るスケーリングは前進差分の前に行なわれる。各点Ｐが
計算されるにつれて、これは右にシフトされることによ
り収縮される０次いで、Ｐの小さな値に対して６による
除算が行なわれることができる。このようなセービング
はパーソナル・コンピュータの如きＲＩＳＣアーキテク
チュの機械では魅力的である。実際、６による除算は補
足説明Ｂで示すように一連のシフト及び加算により近似
化されることがてきる。スケールされた場合における全
ての動作は整数動作である。

残りの疑問は、パラメータ空間ｔに対して幾つの間隔が
適切であるかである。これの答は、パラメータ空間ｔに
対する間隔の数及び制御点Ｐのサイズに依存する。

制御点の値Ｐのレンジを表わすビットの数をｇとし、そ
してパラメトリック変数ｔが除算される間隔の数ｎを表
わすビットの数をｒとすると、ｇ　＝　［ｌｏｇ’　Ｐ
　］そして ｒ　＝　　［ｌｏｇ”　ｎコ 従ってｇ及びｒはこれらの対数表現の限界である。

正の値のレンジは次の中に含まれる。

（３）（ｒ）＋　（２＋ｇ）＋１ビツトそして負の値の
レンジは次の中に含まれる。

（３）（ｒ）＋　（２＋ｇ）＋２ビット従ってこれらの
値のレンジを表わす組合わされたビットの数は、次の如
くである。

（３）（ｒ）＋　（２＋ｇ）＋２ビツト例として、もし
も制御点の座標が１０ビツトで表わされ、そして整数は
３２ビツトの整数であるならば、パラメトリック空間ｔ
に最大６４の間隔を有する。これは次に基づく。

２”＝６４、従ってｒ＝６及びｇ＝１０次いで、ビット
の数は （３）　　（６）＋　（２＋１０）＋２＝３２ビツト。

６による除算は、一連のシフト及び加算により近似され
る。説明する方法は、３１７２画素×３１７２画素のビ
ット・マツプに対して適切なものであるが、１０２４画
素Ｘ１０２４画素の場合にも同じ数のステップが必要と
なる。最小スケーリングファクタが２１３であることに
注目されたい。

曲線の描画の歩進の数に関してハードウェアは、セクシ
ョン当り描かれるべき間隔を少なくとも２５即ち３２必
要とする。６による除算は、次の級数により必要な精度
に近づけられる。

８　３２　１２８　５１２　２．０４ｇこの数はｎ３＝
ｎ”（これは他のシフト動作である）によりディスケー
ルされねばならない。この級数と１／６の実際の値の間
の近似誤差は約０゜０００１６２７６即ち６１４４では
約１である。

もしも誤りが１画素の半分を超えないようにされるとす
れば、これは３０７２画素Ｘ３０７２画素のビット・マ
ツプに対して十分である。

６による除　の 例として、１７７．５／６が曲線上の１点に対するスク
リーン座標であるとする０曲線の各セクション毎のライ
ン・セグメント間隔の数が３２即ち２５であるとする。

このことはスケーリング・ファクタが２　ｘｓ即ち３２
７６８であることを意味する。以下において、１６進数
は下側に記したｈｅＸで表わし、そして２進数はｂｉｎ
ａｒｙで表わす。他の全ての数は基数１０であり下側説
明文字を附していない、スケールされた前進差分法から
生じる数は次の如くである。

（６）　（１７７，５／６）　（２”　）＝（１７７，
５）　（３２，７６８）＝５，８１６，３２０＝５８Ｃ
ＯＯＯｈｅｘ近似除算は２つのレジスタＲ０及びＲ１を
必要とする。スケールされる数をλで示すと、初期状態
は、次の通りである。

これらは元のスケールされる値λを右に３ビツトそして
５ビツト夫々シフトされている。この例における元の値
は次の通りである。

５８ＣＯＯＯｈｅｘ、ｏｒｏｌｏｌ　１０００１１００
００００００００００００６による除算は次の５ステツ
プで近似されそして最後のディスケーリング及び丸めは
第６番目のステップで行なわれる。

ステップＩ Ｒ６の初期値は次の通りである。

これは上記２進値を右に３ビツトだけシフトしたのに等
しく、従って、 Ｒ１１＝１０１１０００１１０００００００００００　
ｂｉｎａｒｙステップ２ Ｒ１の初期値は次の通りである。

５８　Ｃ０００ｈｅｘ Ｒ，＝　　　　　　　　　＝２Ｃ６００ｈｅｘこれは上
記２進値を右に５ビツトだけシフトしたのに等しく、従
って、 Ｒ，＝ＱＯ１０１１０００１１０００００００００ｂｉ
ｎａｒｙステップ２の最後とＲ１の内容はＲｏに加算さ
れ従ってステップ２の最後のレジスタの内容は次の如く
である。

Ｒ０＝　Ｂ　１８００ｈｅｘ＋　２　Ｃ６００ｈｅｘ＝
　Ｄ　Ｄ　Ｅ　００ｈｅｘ、ａｎｄ　Ｒ，＝　２　Ｃ６
００ｈｅｘ ステツプ３ ステップ３において、Ｒ工の内容は２ビツトだけ右にシ
フトされる。Ｒ工の以前の値は（λ／３２）なので、こ
のシフト後のＲ１の値は（λ／１２８）に等しい、この
例の場合は、値は次の通りである。

Ｒ、＝　８１８０ｈｅｘ 次いでこの値はＲｏの値に加算され、従ってステップ３
の最後におけるレジスタの内容は次の通りである。

Ｒ，＝ＤＤＥ００ｈｅｘ＋Ｂ１８０ｈｅｘ＝Ｅ８Ｆ８０
ｈｅｘ、そしてＲｉ＝　Ｂ　１８０ｈｅｘ ステツプ４ Ｒ１の内容は再び２ビツトだけ右にシフトされる。Ｒ工
の以前の値は（λ／１２８）であるので、シフト後のＲ
□の値は（Ｒ１５１２）に等しくこの例の場合、値は次
の通りである６ Ｒ，＝２Ｃ６０ｈｅｘ 次いでこの値はＲ１の値に加算され、従ってステップ４
の最後におけるレジスタの内容は次の通りである。

Ｒ，＝　Ｅ８Ｆ８０ｈｅｘ＋２Ｃ６０ｈｅｘ　＝　Ｅ　
Ｂ　Ｂ　ＥＯｈｅｘ、そしてＲ，＝２Ｃ６０ｈｅｘ ステップ５ Ｒ工の内容は再び２ビツトだけ右にシフトされる。Ｒ□
の以前の値は（Ｒ１５１２）であるので、シフト後のＲ
工の値は（λ／２０４８）に等しく。

そしてこの値の場合、値は次の通りである。

Ｒ，＝　８１８ｈｅｘ この値は次いでＲｏの値に加算さ九、従ってステップ５
の最後におけるレジスタの内容は次の通りである。

Ｒ，＝　Ｅ　Ｂ　Ｂ　ＥＯｈｅｘ＋Ｂ　１８ｈｅｘ＝　
Ｅ　Ｃ６Ｆ８ｈｅｘ、そしてＲ，＝　Ｂ　１８ｈｅｘ ステップに の最後のステップは値をディスケール及び丸める。これ
は、曲線上に存在するスクリーン座標の正しく丸めた値
を生じる。この例におけるスケーリングは２１ｓである
ので、上記結果は同じ量だけディスケールされる。スケ
ーリングは２のべきだけなされたので、ディスケーリン
グは適切なビット数だけ右にシフトして行なわれる。ス
テップ５から生じる数はＥ　Ｃ６Ｆ　８ｈｅｘ　（Ｒ，
の値）であり、これを２進数で表わすと次の通りである
。

この数は右に１５ビツトだけシフトされ、そしてこのこ
とは２”＝３２７６８で除算したことに等しい。これは
、正しく切り捨てられた結果を生じるが、丸めは、切り
捨てられるべき最後のビットが１若しくは０であるかを
検出することにより行なわれることができる。もしもこ
れが０であるからば、切り捨てられた結果は正しく丸め
られる。

もしもこれが１であるならば、切り捨ての結果に１が加
えられねばならない。１６進で表わすと次の通りである
。

８０００ｈｅｘ シフトの後、次の２進値の端数が得られここで点は基数
点の結果を示す。基数点の左は整数であり、基数点の右
は端数である。

１ｎａｒｙ 切り捨てられるべき最後のビットは１であり、そして１
がＩＤｈｅｘの結果に加えられ、ＩＥｈｅｘを生じる。

元の座標数の１０進値は次の通りである。

正しく丸められた結果は３０でありそして次に示すよう
にこれはこの高速で且つ効率的な方法の結果である。

Ｌ　Ｅ　ｈｅｘ　＝　３０

【図面の簡単な説明】

第１図はコンピュータ・グラフィック・システムを示す
図、第２図はＢ−スプライン曲線及び制御点を示す図、
第３Ａ図は曲線座標値を発生するフローチャートを示す
図、第３Ｂ図はＢ−スプライン・セグメント値を計算す
るのに用いられるフローチャートを示す図、第４図は本
発明の実施例を用いるコンピュータ・グラフィック・シ
ステムを示す図、第５図は曲線発生回路の第１の実施例
のブロックを示す図、第６Ａ図及び第６Ｂ図は曲線発生
回路の第２の実施例のブロック図を示す図。 １０．８０・・・・入出力母線、１２．８２・・・・プ
ロセッサ、１４．８４・・・・メモリ、１６．９６・・
・・表示回路、１８．８６・・・・入力回路、９０・・
・・曲線発生回路、１００・・・・シーケンサ、１０４
．１５１・・・・ループ・カウンタ、１０８・・・・レ
ジスタ・ファイル、１２０・・・・シフト回路、１２５
・・・・加算回路、１２４・・・・ラッチ、１３０，２
０４・・・・描線回路、１３２．２０６・・・・バッフ
ァ・メモリ、１５５・・・・制御論理回路。 出願人　インターナショナル・ビジネスマシーンズ・コ
ーポレーション 代理人　弁理士　　岡　　１）　次　　生（外１名） ＦＩＧ、　　２

Claims (6)

【特許請求の範囲】
1. （１）曲線イメージを規定する複数個のデータ点及び上
   記データ点相互間で行なわれるべき間隔の計算の数を受
   けとる入力手段と、 各間隔毎の各次元に対する曲線座標値を複数値の間隔に
   対して同時にパイプライン型で計算するディジタル処理
   手段と、 各次元に対する上記計算された曲線座標値に従う曲線座
   標点及び上記曲線座標点を連続的に接続する複数の直線
   を発生することにより上記曲線イメージの可視表示を生
   じる表示手段とを備える、曲線イメージの可視表示発生
   装置。
2. （２）上記ディジタル処理手段は、上記曲線座標値を計
   算する整数演算手段を含むことを特徴とする特許請求の
   範囲第（１）項記載の曲線イメージの可視表示発生装置
   。
3. （３）上記整数演算手段は、整数演算を行なう複数の演
   算ステージ及び整数除算動作を行なう最終ステージを有
   することを特徴とする特許請求の範囲第（２）項記載の
   曲線イメージの可視表示発生装置。
4. （４）上記整数演算手段の演算ステージは、２進シフト
   及び加算動作により乗算動作を行うことを特徴とする特
   許請求の範囲第（３）項記載の曲線イメージの可視表示
   発生装置。
5. （５）上記整数除算動作を行なう上記最終ステージは２
   進シフト及び加算動作を行なうことを特徴とする特許請
   求の範囲第（３）項記載の曲線イメージの可視表示発生
   装置。
6. （６）曲線を規定する複数の制御点及び該制御点相互間
   の計算の回数を表わす間隔の数を受けとる入力手段と、 次元毎の一組のスケールされたベクトル係数の整数を、
   次元毎に上記複数の制御点及びスケーリング・パラメー
   タから計算し、間隔毎の且つ次元毎の前進差分間隔係数
   の整数を、次元毎のスケールされたベクトル係数の整数
   及び間隔の整数から計算し、次元毎の且つ間隔毎の曲線
   座標値を、間隔毎の且つ次元毎の上記前進差分間隔係数
   の整数及び上記スケーリング・パラメータから計算する
   ディジタル処理手段と、 次元毎の上記計算された曲線座標値に従う曲線座標点及
   び該曲線座標点を連続的に接続する複数の直線を表示す
   ることにより上記曲線を表示する手段とを備える曲線イ
   メージの可視表示発生装置。