JPH03144781A - コンピュータ・グラフィック装置 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 Ａ、産業上の利用分野 本発明は、−殻内には、コンピュータ・グラフィクスに
関し、特にパラメトリック・カーブの評価とレンダリン
グを行う装置および方法に関する。

Ｂ、従来技術及び課題 ］ンピュータ技術の発展に伴い、コンピュータによって
生成されたグラフィカルな情報を表現する方法に工夫が
凝らされ、洗練された技術が生まれている。この技術は
コンピュータ・グラフィクスと呼ばれる。この数年、実
物に近いイメージに対する需要の伸びと平行して、科学
技術分野に３次元（３Ｄ）コンピュータ・グラフィクス
を用いるケースが増えている。

現在のコンピュータ・グラフィクスのデイスプレィは、
線、マーカ、多角形に加えて、パラメトリック・カーブ
など、より一般的なジオメトリツク・プリミティブをサ
ポートしている。しかし、このようなコンピュータ・グ
ラフィクス・ディスプレイ・システムでカーブの評価と
レンダリングを行う方法は、いままでは、効率が悪く、
複雑で高価な外部制御ロジックを必要とすることが多か
った。

パラメトリック・カーブは、Ｂスプライン形式で表現で
きることが知られており、他の形式も、それからカーブ
の評価とレンダリングが試みられている。たとえば従来
のＣＡＤ／ＣＡＭアプリケージ日ンでは、グラフィクス
・ワークステージーンを用いるために、ホスト・コンピ
ュータのデータベースに格納されたカーブを形作るポリ
ラインをＢスプライン・カーブとして送り込む。ホスト
・コンピュータは、このプロシージャに従って、スプラ
イン・カーブを直線ベクトルに分解し、直線ベクトルを
グラフィクス・ワークステージーンに送る。ここで従来
の処理とこれに続く表示が行われる。このプロシージャ
は効率が悪く、Ｂスプラインに特有のメリットを活かせ
ない。

米国特許第４７６０５４８号明細書は、カーブをビジュ
アルに表現する装置について説明している。ここでカー
ブ・データは、比例整変数を用いた前進差分法で求めら
れたＢスプライン式によって与えられる。ただしこの方
法にはいくつか欠点がある。サポートされるのは、広範
なＮＵＲＢＳ（ｎｏｎ−ｕｎｌｆｏｒｓ　ｒａｔｌｏｎ
ａｌ　ｂ−ｓｐ目ｎｅｓ３クラスのサブセットである　
ｕｎｉｆｏｒｍ　ｎｏｎ−ｒａｔｉｏｎａｌ　ｂ−ｓｐ
Ｈｎｅｓだけであり、円など、ある種のカーブについて
は効果的なレンダリングができない。これは初期の方法
であり、カーブを成す隣接するスパンから離れた個々の
スパンに適用され、前進差分アルゴリズムに浮動小数点
演算の場合に生じる誤差の累積を避けるために、整数演
算にたよる。ころした制限から、効率、高速性、有用性
がかなり犠牲になる。

米国特許第４８５５９３５骨切ｍ書は“Ｍｅｔｈｏｄａ
ｎｄ　　Ａｐｐａｒａｔｕｓ　　Ｆｏｒ　　Ｒｅｎｄａ
ｒｌｎｇ　　Ｖｅｃｔｏｒｓ　　ＵｓｌｎｇＢｒｅｓｅ
ｎｈａｍ　Ｐａｒａｍｅｔｅｒｓ”について説明してい
る。

この方法も、米国特許第４７６０５４８号明細書と同様
、ＮＵＲＢＳをサポートせず、前進差分アルゴリズムに
依存する度合いが高く、隣接するスパンから離れた個々
のスパンに適用され、整数演算にたよるほか、３次式に
特有のものと思われ、カーブを直接側々のビクセルに変
換する。

従来の方法には、パラメトリック・カーブの評価とレン
ダリングを行うときにＮＵＲＢＳデータを充分に活用し
ているものがない。ここから、パラメトリック・カーブ
を表すＮＵＲＢＳデータの評価とレンダリングの高効率
化、高精度化、高速化を実現する装置および方法が求め
られている。

インタラクティブな３Ｄグラフイクスの標準として提案
されているＰ　ＨＩ　Ｇ　Ｓ　（Ｐｒｏｇｒａｍｍｅｒ
’５ＨＩｅｒａｒｃｈ、Ｉｃａｌ　Ｉｎｔｅｒａｃｔｉ
ｖｅ　Ｇｒａｐｈｌｃｓ　５ｔａｎｄａｒｄ）ＰＬＵＳ
は、ＮＵＲＢＳを基にカーブの定義をサポートしている
ことから、このニーズを促進する標準となっている。

Ｃ０発明の概要及びその解決課題 本発明は、このニーズを満たし、他のメリットを実現す
るために、オーダにのマルチスパン・パラメトリック・
カーブを表すＮＵＲＢＳデータを、データ・レコードの
シーケンスとしてメモリに配置する、カーブ評価システ
ムを提供するものである。データ・レコードのシーケン
スは、連続したカーブ・スパンが、シーケンスの直前の
複数のデータ・レコードとともに、連続した個々のレコ
ードによって定義されるように配置される。

データ・レコードは、グラフィクス制御プロセッサによ
ってシーケンシャルに読み取られる。制御プロセッサは
、ＮＵＲＢＳデータとコマンドを、パイプライン型の浮
動小数点プロセッサに選択的に引き渡す。このパイプラ
インには、４個の並列プロセッサが含まれ、それぞれの
出力は次段のプロセッサの入力に接続される。並列プロ
セッサは、カーブに沿った所定のパラメータ点における
一組の同次座標（Ｗ　Ｘ１Ｗ　ＹｌＷ　Ｚｓ　　Ｗ　）
の各成分に対するＢスプライン関数を同時評価するよう
にはたらく０次段の浮動小数点プロセッサが、同次座標
をジオメトリツク座標に変換することにより、グラフィ
クス・デイスプレィ・システムのスクリーン上でカーブ
のレンダリングが行われる。

本発明では、特にグラフィクス制御プロセッサが、パラ
メトリック・カーブに関係する制御点をモデリング座標
からビュー座標に変換し、変換された制御点座標を同次
座標に変えて、パラメトリック・カーブをテッセレート
するパラメータ座標間隔を決定し、間隔をとった一連の
パラメータ点を生成する。このパラメータ点が評価に用
いられる。

本発明の実施例では、並列浮動小数点プロセッサは、評
価を行うためにＣｏｘ−ＤｅＢｏｏｒプロセスを実行す
る。並列プロセッサのいずれかは、評価されたパラメー
タ点に重み出力を与え、次段の浮動小数点プロセッサが
重みの逆数を計算して、他の３個の並列プロセッサの出
力をこの逆数に掛け、ジオメトリツク座標を得る。クリ
ッピング・プロセッサとフレーム・バッファは、次段の
浮動小数点プロセッサの出力と直列に接続することで効
果的に使用でき、プロセッサともにパイプライン動作を
行う。

本発明ではまた、ＮＵＲＢＳデータが次のようなシーケ
ンスに配置され、このデータを連続した復雑なカーブ・
スパンによって共用できる。

カーブのオーダにと制御点数ｎを指定する第１シーケン
ス カーブの最初の節点ないしに一１位の節点の節点値を含
む第２シーケンス 連続したに一１個のデータ・セットを含み、各データ・
セットが、座標および制御点と節点値の重みＷのほか、
カーブの最初の制御点ないしに一１位の制御点と、ｋ位
の節点ないし２ｋ一２位の節点とに対するデータを含む
第３シーケンス連続したｎ−に個のデータ・セットを含
み、データ・セットが、カーブのに位の制御点ないしｎ
位の制御点と、２ｋ一１位の節点ないしｎ十に一１位の
節点とに対するデータおよびテッセレーシロン・パラメ
ータ！ないしｎ−に＋１を含む第４シーケンス、および ｎ＋ｋ位の節点値を含む第５シーケンスＮＵＲＢＳを基
にパラメトリック・カーブの評価とレンダリングを行う
本発明の装置および方法は、高性能、高速、高精度、カ
ーブ制御性、ＰＨＩＧＳ　　ＰＬＵＳとの互換性、デー
タ冗長性の解消など様々なメリットを提供する。さらに
本発明では、コンピューターグラフィクス・デイスプレ
ィ・システムの特性および、低位のＮＵＲＢＳを用いて
複雑なカーブを形成する機能、ローカル制御、凸閉包性
（ｃｏｎｖｅｘ　ｈｕｌｌ　ｐｒｏｐｅｒｔｙ）ｓ　重
みを用いて円錐部の正確なレンダリングを行う機能、座
標変換に関する不変性、太線なデータ圧縮など、ＮＵＲ
ＢＳのメリットを活かすことができる。本発明のこのよ
うな特徴は、以下の説明から、より明確になるはずであ
る。

Ｄ、実施例 本発明は、性能向上を図り、Ｎ　Ｕ　ＲＢ　Ｓ　（ｎｏ
ｎ−ｕｎｌｆｏｒｍ　ｒａｔｉｏｎａｌ　ｂ−ｓｐＨｎ
ｅｓ）に基づき１．？イブライン型の並列プロセッサを
用いてパラメトリック・カーブを描くシステムに関する
。これに関連した用語や数学の詳細については、”Ａｎ
Ｉｎｔｒｏｄｕｃｔｉｏｎ　ｔｏ　ＳｐＨｎｅｓ　ｆｏ
ｒ　Ｕｓｅ　Ｉｎ　ＣｏｍｐｕｔｅｒＧｒｉｐｂｌｃｓ
　＆　Ｇｅｏｓｅｔｒｌｃ　Ｍｏｄｅｌ目ｎｇ”　ｂｙ
　Ｒ，Ｈ。

Ｂａｒｔｅｌｇ、　Ｊ、Ｃ，Ｂｅａｔｔｙ、　ａｎｄ　
Ｂ、Ａ、　Ｂａｒｓｋｙ（Ｍａｒｇｉｎ　Ｋａｕｆｓａ
ｎｎ、　１９８７）を参照されたい。

ＮＵＲＢＳは、簡単に言えば、パラメトリック関数の１
クラスであり、パラメトリック・カーブを表現するため
に用いられる。ＮＵＲＢＳカーブは、パラメトリック座
標（１）に依存する。パラメトリック座標は、カーブの
始点から終点への移動において単調に増加する。このパ
ラメトリック座標はジオメトリツク座標ＣＸｓ　　Ｙｌ
Ｚ）に加えられる。したがって、たとえば３Ｄカーブの
場合は次のようになる。

ｘ＝Ｘ（ｔ） Ｙ＝Ｙ（ｔ） ｚ＝Ｚ（ｔ）、 ここでＸ（ｔ）、Ｙ（ｔ）、ｚ（ｔ）はパラメトリ、り
座標ｔの関数である（ｔｌ、≦ｔ≦ｔｍｘＬ パラメトリック・カーブは、簡単な多項式によっても定
義でき、このようなパラメトリック多項式関数は、対応
するＮＵＲＢＳ関数によって正確に表現できる。

ＮＵＲＢＳカーブは有理式または非有理式で定義できる
。非有理式では、ＮＵＲＢＳカーブの各成分（ｘ、Ｙｓ
　　ｚ　）は、パラメトリック座標の多項式関数を評価
することによって求められる。

Ｘ（ｔ） Σ Ｃ１１ｊ’ １＝０ Ｙ（ｔ） Σ Ｃ。

１ ｉ＝０ Ｚ　　（ｔ）　　＝　　Σ　　　Ｃｚｌｊ’Ｉ＝Ｏ 有理式では、重みと呼ばれる関数が追加されるＷ（ｔ）
＝Σ　　　Ｃｗ＋ｊ’ １＝Ｏ この場合ジオメトリツク座標は次の多項式の比によって
求められる。

Ｘ　（ｔ）＝ＷＸ　（ｔ）／Ｗ　（ｔ）Ｙ　　（ｔ）＝
ＷＹ　　（ｔ）／Ｗ　（ｔ）Ｚ　（ｔ）＝ＷＺ　（ｔ）
／Ｗ　（ｔ）ここでＷＸ　（ｔ）、ＷＹ　（ｔ）、ＷＺ
　（ｔ）は、非有理な場合にＸ　（ｔ）、Ｙ（ｔ）、Ｚ
（ｔ）を指定する多項式と同様の多１１ｉ式である。

ＮＵＲＢＳ関数はそれぞれ、パラメトリ、り陣標の最高
ベキに対応する次数（ｍ）と、次Ｆｉｍの多項式におけ
る線形独立項の個数に対応するｍ＋１に等しいオーダ（
ｋ）によって特徴づけられる。

したがって、たとえば２次関数ａ　ｘ２＋　ｂ　ｘ　＋
　ｃは、次数２、オーダ３である。

ＮＵＲＢＳ関数は、Ｆ！ｉ数の係数の組によって表せ、
６紹は、一定範囲のパラメトリック座標に対してのみｆ
１効である。したがってカーブは、連続したスパンのン
ーケ／スに分けることができ、呂スパンはソーｉなる多
項ｊ（によって表せる。これは第１図に、二つのスパン
から成る２次元カーブＣとして示した。第１スバ／は、
ｔｏから【１におよぶパラメトリック値によって定義さ
れ、カーブのこの部分の座標は次の２珀式によって求め
られる。

Ｘ＋（ｔ）＝Σ　　　Ｃｘ１ｌｊ’ １＝０ Ｙｌ（ｔ）＝Σ　　　Ｃ＋＋ｌｌｔ’ ；：Ｏ 第２スパンは、ｊ＋からｔ２ｋおよぶノｆラメトリック
値によって定義され、カーブのこの部分の座標は次の多
項式によって求められる。

Ｘ２（ｔ）＝Σ　　Ｃｘ２＋ｊ’ Ｉ＝０ Ｙ２（ｔ）＝Σ　　　Ｃｙ２１（’ １＝Ｏ ＮＵＲＢ　Ｓは、制御点、重み、および節点ベクトルに
よって決定される。制御点は、カーブのジオメトリを制
御する主要素である。カーブにはｎ個の制御点を考える
ことができる。ここでｎはカーブのオーダ（ｋ）よりも
大きいかそれに等しい。カーブの各スパンはに個の制御
点を持つ。制御点により、カーブの一般形状が決まるが
、カーブは普通、これらの点を通過しない。第２図に、
６個の制御点を持つカーブＣを示した。

重み値は、ＮＵＲＢＳカーブの有理式を定義するために
のみ用いられる。有理式では、重み（Ｗ）は、制御点の
各座標ＣＸｓ　　Ｙ１２）に関連する。

重みと座標は結合されて同次座標（ＷＸ％　ＷＹｓｗ　
ｚｓ　　ｗ　）を成し、これが４個のパラメトリック多
項式関数ＷＸ　（ｔ　）、ＷＹ（ｔ）、ＷＺ（ｔ）、Ｗ
　（ｔ）の組に対する制御点を定義する。ころして得ら
れるジオメトリツク座標は次の比によって求められる。

ｘ　（ｔ）＝ＷＸ　（ｔ）／Ｗ　（ｔ）Ｙ　（ｔ）＝Ｗ
Ｙ　（ｔ）／Ｗ　Ｃｔ＞ｚ　（ｔ）＝ＷＺ　（ｔ）／Ｗ
（ｔ） 重みは、Ｏより大きい正の値とする必要がある。

普通、重みの値は１に近＜、重みがすべて等しい場合、
有理式は非有理式に縮分される。

カーブの節点ベクトルは、パラメトリック座標（１）に
対してパラメータ空間の分割を定義する。

ｎ個の制御点を持つオーダにのカーブの節点ベクトルは
、ｎ　＋　ｋ個の成分を持ち、そのうち最初と最後の成
分は決して用いられない。カーブの各スパンは、２ｍ個
の連続した節点値に依存する。ここでｍはに−１であり
、ｋはカーブのオーダである。これらの節点値は二つの
グループに分けられる。一つはスパンの前のｍ個の節点
値を持つグループであり、もう一つはスパンの後のｍ個
の節点値を持つグループである。第３図に示すとおり、
カーブＣのスパン（ｔ　３−　ｔ　４）の前には３個の
節点値（ｔｔ、ｔ２、ｔ、）、後には３個の節点値（１
，、ｔ５、ｔａ）がある。節点値は、Ｂスプラインが一
様か一様でないかを決定する。節点の各位の間隔が一様
であれば（０１１，２，３など）、結果は一様なりスプ
ラインとなる。−様でないＢスプラインでは、節点値は
不規則な間隔をとって分けられ、節点値は、節点ベクト
ル（０，０、！、　　２．　１．　５．１．　５．２．
　７．９．　０）のように反復し得る。

ここでは、ＮＵＲＢＳといつ用語は一般的な意味で用い
、非有理な（重みを１に等しく設定した）−様Ｂスプラ
イ７ンの特殊なケースを指すものとする。

以上の基本的な数学をベースに、ここで本発明の実施例
について説明する。本発明に従って構成されたカーブ評
価／レンダリング・システム（１０）は第４図に示すと
おりである。このシステムは主として次のコンポーネン
トを含ム。

（１）システム・メモリ（１２） （２）グラフィクス制御プロセッサ（１４）およびパイ
プライン方式で動作する、 （３）並列に配置された４個の浮動小数点プロセッサ（
１８ｘ１１８ｙｔ　　１８ｚ１　ｆｅｗ）のグループ（
１６） （４）Ｍ列浮動小数点プロセッサ（１６）の出力に接続
された次段の浮動小数点プロセッサ（１８） （５）クリツピング・プロセッサ（２０）（６）フレー
ム・バッファ（２２） システム・メモリ（１２）には、各パラメトリック・カ
ーブのＮＵＲＢＳデータが含まれる。

データはメモリ１２ｋ格納され、構造化された（すなわ
ち連続した）グラフィクス制御プロセッサ（１４）に転
送される。これにより、データは、連続したスパンによ
って共用され、データの冗長性がなくなる。

第５図は、シーケンスの各部ｌないし５によって示され
るデータの構造である。第１シーケンスでは、予備ヘッ
ダ情報がシステム・メモリに置かれる。ヘッダ情報には
、オーダ（ｋ）（ｋは２ないしｋｍａ　ｘの整数−−ｋ
ｍａｘは浮動小数点プロセッサによってサポートされる
最大オーダ）、制御点数（ｎ）（常に＆　ｋ　）　、カ
ーブ・タイプ・フラグ（非有理のとき１１　　有理のと
き０をとる）、カーブ・ステータス・フラグ（未定義の
テッセレーンβン・パラメータでは０、定義済みテッセ
レーションパラメータでは０をとる）、ｔｍｉｎとｔｍ
ａｘ（パラメトリック座標の範囲を指定する）が含まれ
る。テッセレーシロン・パラメータについては後述する
。

第２シーケンスでは、カーブの初めの節点工ないし接点
に−１がシステム・メモリに置かれる。

第３シーケンスでは、節点にないし節点２ｋ−２の値、
連続した制御点ｌないしに−１のＸｌｙ％２座標、およ
び制御点！ないしに−１に関連する重みがシステム・メ
モリに置かれる。このデータは縦の列に示すようにグル
ープ分けされる。第５図の縦の列はそれぞれデータ・セ
ットすなわちレコードから構成される。

第４シーケンスも上記と同様の連続したデーク◆セット
すなわちレコードを格納する。各レコードにはテッセレ
ーシｇン・パラメータ（ｄ）が付加される。第４シーケ
ンスの連続したデータ・レコードはそれぞれ、連続した
カーブ・スパンを完成する。スパンは、ｋ個の制御点と
２ｋ一２個の節点によって定義される。第２シーケンス
の節点１は、カーブ評価には用いられない。したがって
、第１スパンを完成するのは、２４ａとした、節点値２
ｋ−１を含む列すなわちデータ・レコード、制御点座標
ｘ　（ｋ）、Ｙ　（ｋ）、ｚ　（ｋ）、重みｗ（ｋ）、
およびテブセレーシずンデータｄ　（１）のほか、第３
シーケンスのデータ・レコードと、第２シーケンスの節
点２ないしに−１の節点値である。第２スパンを完成す
るのは、第４シーケンスのデータの第２のセットすなわ
ち列のほか、前の２ｋ一３個のデータ列である（すなわ
ち前のに一１個の制御点と関連する重み、および２ｋ一
３個の節点値）。後続するスパンも同様に構成される。

このように処理することで、新しいスパンのそれぞれに
、後続する第４シーケンスのデータ・セットと先に格納
された直前の２ｋ一３個のデータ・レコードが用いられ
、データの冗長性がなくなる。

第５シーケンスでは、最後の節点値ｎ＋ｋがシステム・
メモリに置かれる。ただしこの節点はカーブ評価プロセ
スには用いられない。

ここで第４図を参照する。グラフィクス制御プロセッサ
（１４）は、システム・メモリに格納されたデータを、
先に説明したシーケンスで読み込み、第４図に２方向を
指す矢印で示したように、システム・メモリにデータを
書き戻すことができる。グラフィクス制御プロセッサは
、制御点データをモデリング座標からビュー座標に変換
し、変換された制御点データを同次Ｓ標（ＷＸ％　ｗＹ
１ＷＺ％Ｗ）に変えて、パラメトリック座標間隔（ｄ　
ｔ）を求める。これによりパラメトリック座標がテブセ
レートされ、間隔をとった一連のパラメータ点（ＰＣ）
が生成される。グラフィクス制御プロセ、すはまた、コ
マンドとデータを４個の並列浮動小数点プロセッサ（１
６）に転送する。

以下これについて詳述する。プロセッサ１６Ｘ。

１８７１１８ｚ％　１６ｗはそれぞれ独立に、同期して
、各パラメータ点ＰＣの同次座標ｗｘ１　ｗｙ、ＷＺ、
ＷのそれぞれのＢスプライン関数を同時＋ｉｆ価する。

プロセッサＩＥｌｘ、１６Ｖｓ　　１８ｚｓ　　１６ｗ
の出力ｗｘ（ｔ）、ｗＹ（ｔ）、ｗｚ　（ｔ）、ｗ（ｔ
）はそれぞれ、浮動小数点プロセ、す１８に直列に供給
される。プロセッサ１８は、ｗ（ｔ）の逆数を計算し、
ｗｘ（ｔ）、ｗＹ（ｔ）、ｗｚ（１）にこの逆数を掛け
て、カーブを表すポリラインの頂点のジオメトリツク座
標Ｘ１Ｖｓ　　Ｚを求める。ポリライン座標は、クリッ
ピング・プロセッサ（２０）により従来の方法で処理さ
れ（すなわち順列頂点の各ペアによって定義されたベク
トルが現在のビュー・ウィンドウにクリップされ）、フ
レーム−バッファ２２ｋ送られる。ここでコンピュータ
・グラフィクス・デイスプレィのモニタースクリーン（
図示なし）上で従来の方法によりカーブのレンダリング
が行われる。

ここで本発明の実施例について述べる。システム・メモ
リ１２は２ないし４Ｍバイト（またはそれ以上）のＲＡ
　Ｍ　（ｒａｎｄｏｍ　ａｃｃｅｓｓ　ｍｅｍｏｒｙ）
から構成できる。システム・メモリは、少なくとも１個
のパラメトリック・カーブのデータを格納できなければ
ならない。また代表的なシステム・メモリは、様々なグ
ラフィクス・ニレメン）　（ＮＵＲＢＳカーブを含めた
プリミティブと属性）から成るデイスプレィ・リストを
格納する。グラフィクス制御プロセッサ１４は、浮動小
数点乗算器、浮動小数点演算用、シーケンサ、少なくと
も３２ｋのデータ・メモリをアクセスする機能、３２個
の整数レジスタ、および浮動小数点演算用の３２個のレ
ジスタを備える。プロセッサ１４は、ＩＯＭＨ２のＷｅ
ｉｔｅｋチ１プ・全１ト（プログラマブル・シーケンサ
ＸＬ−８１３８、浮動小数点プロセッサ◆ユニットＸＬ
−３１３２、および整数処理ユニットが連係）によって
効果的に実現できる。

浮動小数点プロセッサ１６　Ｘ％　　１８　ｙｌｌ　８
　ｚｓｌ　８　Ｗ％　　および１８には、それぞれ３２
ビット浮動小数点演算機能を組み込んだＶＬＳ　Ｉプロ
セッサを採用できる。各プロセッサは、浮動小数点乗算
器、浮動小数点加算ＶＳ（乗算器用のアキエムレータと
しても用いられる）、簡易シーケンサ、マイクロコード
用ＲＡ　Ｍ、　　インタフェース入出力用Ｆ　Ｉ　Ｆ　
Ｏ，およびデータ格納用の８４個のレジスタを備える。

浮動小数点プロセッサは一般に知られているとおりであ
る。米国特許出願第３３１０２１号（１９８９年３月２
８日出願）では、特殊な入出力ＦＩＦＯにより、ここに
述べている並列／パイプライン接続の効果が高められる
。クリッピング・プロセッサ２０とフレーム・バブファ
２２は、性能に問題がなければ、それぞれ、複数の類似
のプロセッサを備えることができ、個数と構成は任意で
ある。

一般に、ＮＵＲＢＳカーブがメモリ１２のデイスプレィ
・リストに現れると、制御点はグラフィクス制御プロセ
ッサ１４によって変換される。変換された制御点は同次
座標（Ｗ　Ｘ、Ｗ　ＹＮ　　Ｗ　ＺＮＷ）に変えられ、
パイプライン型の並列プロセッサ１６に送られる。ここ
で各座標はプロセッサ１８ｘ％　ｔ８ｙｘ　”１６ｚ１
　ｌａｗによって保持される。グラフィクス制御プロセ
ッサ１４は次に、パラメトリック座Ｗ　（ｔ）をテッセ
レートする方ｌ去を判定し、一連のパラメータ値をパイ
プラインに送り出す。プロセッサ１６は、パラメトリッ
ク座標の各位に対してＷＸ％　Ｗ　ＶｌＷ　ＺＩ　　Ｗ
の各成分を並列に同時評価する。こうして得られた値Ｗ
Ｘ（１）、ｗＹ　（ｔ）、ＷＺ　（ｔ）、ｗ　（ｔ）は
プロセッサ１８に引き渡され、プロセッサ１８はこれら
を（Ｘ％　　ｙｓ　　ｚ）座標に変換する。各点は後に
、クリッピング・プロセッサ２０とフレーム・バッフｙ
２２ｋよって、通常のポリラインの一部であるかのよう
に処理される。メモリ１２内のＮＵＲＢＳデータの編成
と、上述のパイプライン型の装置による処理は、本発明
に多大のメリットをもたらす。

カーブ評価システム１０におけるグラフィクス制御プロ
セッサ１４の動作並びに他のプロセッサの動作は第６ａ
図ないし第６ｄ図に示した。以下これについて説明する
。

第６ａ図では、最初に、オーダ（ｋ）、制御点数（ｎ）
、カーブ・タイプ・フラグ、カーブ・ステータス◆フラ
グ、ｊｍｆｎとｔｍａ　ｘを含むヘッダ情報がシステム
・メモリに読み込まれ（３０）、グラフィクス制御プロ
セッサ１４内のレジスタに格納される。制御点が何個処
理されたかを記録しておくためにレジスタ（カウンタと
いう）が用いられ、最初はＯにセットされる。

次にグラフィクス制御プロセッサが“パラメトリック・
カーブ開始”コマンド（３４）とオーダ（ｋ）（３６）
を各浮動小数点プロセッサ（Ｉ６）へ送る。

グラフィクス制御プロセッサは次に、システム・メモリ
からに一１個の初期節点を読み出しく３８）、すべての
並列浮動小数点プロセッサ（１６）に転送する。並列浮
動小数点プロセッサに転送された節点値は、各プロセッ
サのスタック３９に保持される。スタック３９はそれぞ
れ、データ行２ｋ一２行を保持するのに充分な大きさで
あり、ＦＩＦＯ方式で動作する。このスタックの一例（
ｋ：＝４）を第７ａ図に示した。ｋ−１個の最初の節点
がスタックにブツシュされており、スタックの他の部分
の初期状態は未使用である。

次に、節点値（ｔ（ｋ））、制御点（ｘ（１）、Ｙ　（
１）、ｚ　（１）　）、重み（ｗ（１）、　　およびテ
ッセレーシ訝ン・データを含むデータ・レコードがあれ
ば、システム・メモリから読み込まれる（４０）。カウ
ンタは１だけ更新され（４２）、カーブ・タイプが１に
等しいなら（４４）、各データ・レコードに対する重み
が１にセットされる（４θ）。これは非存ＦＩＢスプラ
インを示す。

次にグラフィクス制御プロセッサは、システム−メモリ
から受信されたばかりの制御点を、モデリング座標から
ビュー座標（ＸＮ　　ｙｓ　　ｚ）に変換する。グラフ
ィクス制御プロセッサにロードされた変換マトリックス
により％　　Ｘｓ　　Ｙ％　２が従来の方法で必要に応
じて変換、回転、あるいは拡大縮小される。

変換プロセスが終わると、グラフィクス制御プロセッサ
は、節点値（１）と制御点座標（ＸｓＹｓ２）をグラフ
ィクス制御プロセッサのローカル・メモリにあるスタッ
ク４９にブツシュする。スタック４９は、制御点データ
行に行を保持するのに充分（１スパンに充分）な大きさ
であり、これもＦＩＦＯベースで動作する。このローカ
ル・メモリ・スタックの一例（ｋ＝４）を第８ａ図に示
した。データの最初の行はスタックにブツシュされてわ
り、スタックの他の部分は空である。

次に、グラフィクス制御プロセッサにおいて、システム
・メモリから読み込まれたばかりの制御点座標（Ｘ１７
１　　ｚ）に重み（ｗ）が掛けられ、重みつき座標（Ｖ
ｉｒ　Ｘｓ　　Ｗ　Ｙｓ　　Ｗ　２ｍ　　Ｗ　）が得゛
られる（５２）。

次に、グラフィクス制御プロセッサは、　′スパン開始
”コマンド（５４）を並列浮動小数点プロセッサ（１６
）のそれぞれに転送する。このコマンドには、オーダ（
ｋ）、節点値（ｔ　（ｋ）　）、および重みつき座標（
Ｗ　Ｘ１Ｗ　”！ｓ　　Ｗ　２１Ｗ　）が続＜　（５８
）。節点値は各並列浮動小数点プロセッサの節点スタッ
ク３９にブツシュされる（この値がブツシュされた後の
節点スタックについては第７ｂ図を参照）。座標セット
（ＷＸｌＷｙｌｗｚｌ　ｗ）の各成分は浮動小数点プロ
セッサ１個にのみ転送される。したがってＷＸは第ｉｆ
列浮動小数点プロセッサ（１６ｘ）へ、ｗｙｌｔｉ２ｆ
ｆｉ列浮動小数点プロ全浮動小数点プロセッサ送される
、という動作になる。各苓列プロセッサ内のスタック５
７が、　座標セラ　ト　（Ｗ　ＸＮ　　Ｗ　７％　　Ｗ
　Ｚｚ　　Ｗ　）の各成分を保持するのに用いられる。

各スタックは、データ行に行を保持でき、ＦＩＦＯ方式
で動作する。第９ａ図は、ｑｒｒ列１？動小数点プロセ
ッサ内のスタック５７　ｘ１５７５’１５７　ｚ１５７
　ｗに、初めに重みつき座標がプッンユされた様子を示
す。

次に、カウンタがｋより大きいかｋに等しいかどうかが
判定される（５８）。ｋより小さい場合、処理はライン
（６０）を介して４０（１データ・レコード読み込み）
に戻る。ｋに等しい場合、１スパンに充分なデータが浮
動小数点プロセッサに送られている。そこで各並列浮動
小数点プロセッサ内の節点スタック３９は、第７ｃ図に
示すように、節点２ないし２ｋ−１のデータを持つ。グ
ラフィクス制御プロセッサ１４内のスタック４９には、
第８ｂ図に示すように、節点にないし２ｋ−１の値と、
制御点工ないしｋの座標（ｘｉ　　ｙ、　　ｚ）が置か
れる。ここでｋは４である。並列浮動小数点フロセッサ
ｌｅ内の重みつき座標スタック５７は、第９ｂ図に示す
ように、制御点１ないしｋの重みつき座標データをｔ寺
つ（ｋ＝４）。

１スパンに充分なデータが各浮動小数点プロセッサ１６
に送られると、スパンの有効性が判定される（６２）。

スパンは次の場合に有効である。

７、　　　＜　　　　Ｔｍａｘ Ｔ２　　＞　　Ｔｍ１ｎ　　ａｎｄ Ｔ２　　＞　　ＴＩ ここでＴ、は、グラフィクス制御プロセッサ１４のスタ
ック４９にあるｆｆ１１節点硝に、Ｔ２は第２節点値に
それぞれ等しい。

スパンが無効であれば、処理はライン６４を介して再び
４０（ｌデーターレコード読み込み）に戻る。スパンが
有効で、カーブ・ステータス・フラグが０なら（Ｅ３５
）、テフセレーシ６ン・パラメータ（ｄ）がグラフィク
ス制御プロセッサによって計算され（６６）、ンステム
・メモリにセーブされる（６８）。カーブ・ステータス
−フラグがＯに等しくない場合、処理はライン６７を介
して７０（ｄｔ計算）に飛ぶ。これはテッセレーン窪ン
・パラメータがすでに計算されていることを示す。

テッセレーシｅンは、曲線をセグメントに分けるプロセ
スである。セグメントは直線で近似できる。テッセレー
シ璽ン・パラメータの計算は、スパン内の点数に依存す
る。スパンはカーブのオーダによって定義される。第１
０ａ図ないし第１０ｂ図に示すように、オーダにのカー
ブはスパン当たりに個の制御点とに一１個のセクシ茸ン
を持つ。

ｋ個の制御点は、終点２個と中間点に一２個から戚る。

したがって、ｋ＝３であれば、セフシロンは２個、中間
点信１個であり、ｄ　：：　Ｉ　ａ　Ｘ　ｌ　＋ａ７＋
＋ＩａＺｌとなる。ここでｄはベクトルａの長さ限界ｓ
　　ａＸｌ　ａｓｓ　　ａＺは弦偏差の限界である。ｋ
＝４のとき、セクシシンは３個、中間点は２個であり、
次のようになる。

ｄ＝ｌａｘｌ＋Ｉｂｘｌ＋ １ａＹＩ＋Ｉｂ５’ｌ＋ １ａｚｌ＋Ｉｂｚｌ ここでｄはベクトルａ１　ｂの長さ限界Ｎ　　ａＸｘａ
）’ｔａｚおよびｂ　ｘｓ　　ｂ　７％　　ｂ　ｚは弦
偏差の限界である。

テッセレーシ冒ン・パラメータ（ｄ）が計算されると、
バラメトリ１り座標間隔（ｄｔという）がグラフィクス
制御プロセッサ１４によって次のように計算される（７
０）。

ｄ　ｔ　＝　（Ｔ２−Ｔ、）　／ＮＳ　ｔ　ｅ　ｐここ
でＮＳ　ｔ　ｅ　ｐは次の操作によって求められる。

（ａ）スクリーン（ビクセル）座標とデータ座標の比に
等しいスケールＳを計算する。

（ｂ）ｄにＳを掛けて、ｄをピクセル・ユニット（デバ
イス座標）に変換し、ｄ′を得る。

（ｃ）ＮＳｔｅｌ）を次のように計算する。

ＮＳｔｅｐ＝Ｍａｘ（１，Ｉｎｔ ＳＱＲＴ　（ｄ’　）’） ｄｔの計算後、Ｔ、とＴ２が、境界Ｔ　ｍ　Ｉ　ａとＴ
１．８内に収まるように、次のように調整される。

Ｔ１１がＴ、１とＴ２の間にある場合は、Ｔ、はＴ　ｍ
１ｍに等しくセットされ、　Ｔ、１．がＴ１とＴ２の間
にある場合はＮ　　Ｔ２はＴ、＆、に等しくセットされ
る（７１）。次に、グラフィクス制御プロセッサは、Ｕ
パラメトリック・カーブ評価”コマンドを並列浮動小数
点プロセッサ１８に送る（７２）。並列浮動小数点プロ
セッサは、このコマンドを受け取ると、　“パラメトリ
ック・カーブ評価”コマンドを浮動小数点プロセッサ１
８に送り（７４）、　　プロセッサ１８はそこで“ポリ
ライン開始”コマンドをクリッピング・プロセッサ（２
０）へ送る（７６）。この様子は第６Ｃ図に示した。こ
れらのコマンドが送られている間、グラフィクス制御プ
ロセッサは動作を継続する。この様子は第６ｂ図にライ
ン７３で示した。グラフィクス制御プロセッサはオーダ
（ｋ）を並列浮動小数点プロセッサ１６へ送る（７８）
。次にパラメータ・ポイン）　（ＰＣ）がＴ、に初期化
される。Ｔ、はスパンの最初の節点値である。ＰＣは各
並列浮動小数点プロセッサに送られる（８２）。

並列プロセッサと後続プロセッサの内部動作は、第６ｄ
図をみれば最もよく理解できよう。これらのプロセッサ
内のタスクは、グラフィクス制御プロセッサが動作を続
けている間に実行される。この様子は第６ｂ図のライン
９９で示した。第６ｄ図で、パラメータ・ポイン）　（
ＰＣ）が各並列浮動小数点プロセッサに送られた後、各
プロセッサは、制御点座標セット（Ｗ　Ｘｓ　　Ｗ　Ｙ
ｓ　　Ｗ　ＺｌＷ　）のｌ成分についてＢスプライン関
数の評価を始める（８４）。たとえば第１並列浮動小数
点プロセッサ１８ｘは、パラメーターポイントのＸ座標
を評偏し、第２Ｍ列浮動小数点プロセッサｌａｙはＸ座
標を評価する。４個の並列浮動小数点プロセッサ１６は
すべて、座標を同時に評価する。

実施例では、Ｃｏｘ−ＤｅＢｏｏｒ　（またはＤｅＣａ
ｓｔｅｌＪａｕ）プロセスとして知られているプロセス
が評価に用いられる。このプロセスでは、制御点の成分
相互間の線形補間が行われる。各座標について浮動小数
点プロセッサへ送られたＰＣの６値に対して、合計ｋ（
ｋ−１）／２同の補間が行われる。

このプロセスを説明するために、３次Ｌｌｔｌ　ｌｉｔ
の例を挙げる。第１１ａ図は、ｋ個の制御点のＸ座標（
ｋ＝４）、節点値Ｔ、を始点とし節点値Ｔ２を終点とす
るスパン（Ｔ、とＴ２はグラフィクス制御プロセッサの
スタック４９にある第１節点値と第２節点値を表すｍ−
このスタックについては第８ｂ図を参照）、パラメータ
・ポイン）　（ＰＣ）、スパンの前の３個の節点（ｉｆ
ｌｌ（ｔ、、ｔ２．１．）、およびスパンの後の３ｆ４
の節点値（１，、ｔ６、ｔ６）を示す。６個の節点値（
１，ないしｔｇ）は、各浮動小数点プロセッサのスタッ
ク３９にある節点値を表す（このスタックについては第
７ｃ図を参照）。

第ｆｉｂ図は前節点（１，、ｔ２、ｔ３）の位置づけを
示し、前節点は補間される各成分の始点を表す。第１１
ｃ図は後節点（１４、ｔｌ、１．）の位置づけを示し、
後節点は捕間される各成分の終点を表す。したがって補
間は、ｔ、とｔ４の間、ｔ２とｔ、の間、およびｔ３と
ｔ６の間で行われる。

Ｃｏｘ−ＤｅＢｏｏｒの評価プロセスでは、上述の変数
が次式に用いられる。これは３次曲線の例である。

ｆ＋＝　（（ｔ４−ＰＣ）ｘ、＋　（ＰＣｔｔ）ｘ２）
／（ｔ４−ｔ、） ｆ　２＝　　（（ｔ、−ＰＣ）ｘ２＋　　（ＰＣ−ｔ、
）Ｘ　、）／　　（ｔｓ−ｔ　２） ｒｓ＝　　（（ｔｇ−ＰＣ）Ｘ３＋　　（ＰＣ−ｔ　３
）Ｘ４）／　　（ｔｇ−ｔ、） この三つの式は、３次曲線に対する線形補間の第１段階
で用いられる。補間はｔ、とｔ４の間、ｔ、とｔ、の間
、およびｔ、とｔ６の間で行われ、３個の点が得られる
。第１ｉｄ図にこれら３個の点を、中心点を描いた円で
示した。

補間の第２段階では、節点値をもう一度位置づける必要
がある。この段階では３点しかないので、必要な節点は
ｔ２ないし【、だけである。節点ｔ２とｔ、は新しい前
節点、ｔ４とｔ、は新しい後節点である。３次曲線の場
合、線形補間のこの第２段階で次の二つの式が用いられ
る。

ｆ’＋＝　（（ｊ４　ＰＣ）ｒ、＋　（ＰＣ−ｔ２）ｆ
　２／　（ｔ４−　ｔｚ） ｆｘ＝　（（ｔｓ−ＰＣ）ｆ２＋　（ＰＣ−ｔｔ）ｆ、
／（ｔ、−ｔ、） 補間はｔ２とｔ４の間、およびｔ、とｔ、の間で行われ
、２個の点が得られる。これら２個の点を第１ｉｅ図に
、中心点を描いた円として示した。

補間の最後の段階では再び節点値の位置づけが必要であ
る。この段階では２点しかないので、必要な節点はｔ、
とｔ４だけである。３次曲線の点のＸ座標を得るには、
次式が用いられる。

ｆ　（ｔ）＝　（（ｔ、−ＰＣ）ｆ、＋　（ＰＣ−ｔｓ
）　ｆ２／　（ｔａ−ｔｓ） この点は第１１ｆ図に、中心点を描いた円として示した
。上記の評価プロセスは、同じＰＣ値と同じ節点値を用
いて、並列浮動小数点プロセッサ内の台座ｍ　Ｃｘｓ　
　７１２％　　Ｗ）に対して同時に実行される。ただし
各プロセ、すは制御点の１座標だけを処理する。第１プ
ロセツサ１１３ｘはＸ座標を処理し、第２プロセツサ１
６ｙはＸ座標を処理する、という動作になる。

ＰＣの各座標値について補間が終了すると、並列浮動小
数点プロセッサ１６は、結果の座標値（ｗｘ　（ｔ）、
Ｗｙ　（ｔ）　　ｗｚ　（ｔ）　　ｗ（ｔ））を浮動小
数点プロセッサ１８へ送るが、この転送は、座標値が直
列に受信されるように同期をとって行われる（８６）。

プロセッサ１８は、座標値の各組を受信すると、１／ｗ
（ｔ）を計算し、これに（ｗｘ　（ｔ）　　ｗＹ　（ｔ
）　　ｗｚ（ｔ）　、ｗ　（ｔ））を掛けて（８８）ジ
オメトリツク座標（Ｘ１Ｙｓ　　Ｚ）を得る。これらの
座標ハ次に、クリッピング・プロセッサ２０に送られる
（９０）。

クリッピング・プーロセブサはプロセッサ１８から送ら
れた座標を受け取り、順列座標の各組によって定義され
たベクトルを現在のビュー境界にクリップする（９２）
。クリップされたベクトルの組は、フレーム・バッフ１
２２ｋ送られ（９４）、ここで直線セグメントとして痛
画される（９６）。

第６ｄ図をみると、上記の評価プロセスとそれに続くス
テップは、Ｎ５ｔｅｐ＋１回行われ、各ＰＣは、ＰＣｉ
！；Ｔ２となるまでｄｔの値だけインクリメントされる
（９８）。ＰＣがＴ２より大きくなると（１００）、Ｐ
ＣはＴ２と等しくセットされ（１０２）、この最後の値
も、先に説明したとおり、並列浮動小数点プロセッサへ
送られる（１０４）。

ＰＣの値がすべて評価されると、カウンタは制御点数よ
り小さいかどうかが調べられる（１０６）。小さい場合
、処理はライン１０８を経て４０（１データ・レコード
読み込み）へ戻り、このプロセス全体が、ｎ回まで繰り
返される。

プロセスがｎ回実行されると、グラフィクス制御プロセ
ッサ１４は、　４カーブの終わり”コマンドを並列浮動
小数点プロセッサ１８へ送る（１１０）。

次に、ステータス・フラグが調べられ（１１２）、Ｏに
等しい場合は、１に更新される（１１４）。この変更は
次に、システム・メモリに書き戻される（１１８）。

パイプライン型の並列プロセッサを用い、ＮＵＲＢ　Ｓ
　（ｎｏｎ−ｕｎｌｆｏｒｖ　ｒａｔｉｏｎａｌ　ｂ−
ｓｐｌｉｎｅｓ）を基にパラメトリック・カーブの評価
とレンダリングを行う装置および方法について説明した
。並列／パイプライン型のプロセッサの使用方法に工夫
を凝らすことにより、カーブの評価とレンダリングをい
ままでよりもはるかに高速に実行できる。またシステム
・メモリに格納されたデータを本発明のように構成する
ことで、データの冗長性がなくなり、データの処理効率
が向上する。

その性質から、ＮＵＲＢＳには様々なメリットがある。

本発明はこれらのメリットを最大限に活用している。Ｎ
ＵＲＢＳではカーブをスパンのシーケンスに分けること
ができる。そのとき各スパン（よ一組の異なるパラメト
リック多項式によって表される。ＮＵＲＢＳカーブの隣
接したスパンを表すパラメトリック多項式は、特定の連
続性を与える。連続性の程度は、滑らかなカーブや急峻
なカーブが描けるように制御することができる。

連続スパンを特定の連続性と一致させられるので、低位
のＮＵＲＢＳを用い、多数の点を通る６ｉ雑なカーブが
得られる。この性質はきわめて有益である。通常は評価
コストが高くなり、数値が不安定になりやすい高位の関
数を避けることができるからである。

ＮＵＲＢＳにはローカル制御という特性もある。

ＮＵＲＢＳは制御点、重み、および節点ベクトルによっ
て決まるので、カーブ全体に影響を与えずに、制御点を
移動させることによって、カーブのスパンを変更するこ
とができる。

凸閉包性のメリットも見逃せない。ＮＵＲＢＳカーブは
、その制御点の凸閉包内に含まれる。凸閉包は、所定数
の点を含む最小の凸多角形（２次元のとき）または最小
の凸条面体（３次元のとき）である。カーブの各スパン
は、そのスパンを決定するに個の制御点の凸閉包内に存
在しなければならない。この特性から、点を評価するこ
となく、ＮＵＲＢＳカーブの大きさと位置を予測し、そ
れぞれの境界を設定することができる。これは特に自明
な棄却テストで重要である。いいかえれば、凸閉包が現
在のスクリーンとオーバラップしない場合、カーブは評
価されずに棄却される。カーブが棄却されない場合、凸
閉包を用いて、カーブが評価される点を決定できる。

制御点に関連する重みは、円と楕円を含む円錐セフシー
ンに正確な表現を与える。これは、円形を必要とするオ
ブジェクトが多いので、特に重要なメ　リ　ッ　トであ
る。

本発明のメリットはさらに、変換が、頂点ではなく制御
点を用いて行われるということである。

通常、制御点は頂点よりも少ないため、この方法はより
経済的である。

本発明に採用した評価方法は、制御点を直を変向に用い
ることで、セットアツプ・コストを抑えるものである。

補間式は、ＮＵＲＢＳ関数の数値安定性を保つので、ス
パンに対して演算を進めるとき累積誤差が生じない。

ＮＵＲＢＳカーブは、非常にコンパクトなデータ構造を
つくるので、従来のポリライン・データと比較した場合
、データ転送率が大幅に向上し、システム資源の利用効
率が上がり、より複雑なグラフィクスもサポートできる
。このようなメリットは、ＮＵＲＢＳデータをその本来
の形式で処理することによって保たれ、本発明のスパン
共用データ・ンーケンシ／グ法によって高度化される。

上述の内容から明らかなように、ＮＵＲＢＳに基づいて
パラメトリックカーブの評価とレンダリングを行う装置
および方法には、高性能、数値安定性、対コスト効果、
高速、高精度、カーブ制御性、３Ｄグラフイクスの標準
として提案されているＰＨＩＧＳ　　ＰＬＵＳとの互換
性、データ冗長性の解消など、数々のメリットがある。

Ｅ０発明の効果 上述のごとく本発明によれば、ＮＵＲＢＳデータの評価
とレンダリングの高効率化、高精度化、高速化が実現さ
れる。

【図面の簡単な説明】

第１図は、異なる多項式の組によって表される三つの連
続スパンから成る２次元カーブの図である。 第２図は、ＮＵＲＢＳカーブＣとその６個の制御点の図
である。 第３図は、２次元座標空間におけるカーブＣのスパン（
ｔ＊−ｔ４）と、パラメータ空間におけるそのスパン、
その前の３個の節点［（ｔ＋、ｔ７．１、）およびその
後の３個の節点値Ｃｔａ、（６，１、）の図である。 第４図は、本発明に従って構成されたカーブ評価／レン
ダリング装置のコンポーネントと相互接続を示すブロッ
ク図である。 第５図は、３次元ＮＵＲＢＳカーブがシステム・メモリ
に格納されたときのデータ構造を示す図である。 第６ａ図と第６ｂ図は、本発明によるカーブ評価システ
ムの動作のフローチャートである。 第６ｃ図は、パイプライン型の並列浮動小数点プロセッ
サと次段のプロセッサによって送られたコマンドのフロ
ーチャートである。 第６ｄ図は、本発明による、並列浮動小数点プロセッサ
と後続のプロセッサ内の動作を示すフローチャートであ
る。 第７ａ図ないし第７Ｃ図は、動作の各段階における並列
浮動小数点プロセッサ内の節点スタックを示す図である
。 第８ａ図と第８ｂ図は、動作の各段階におけるグラフィ
クス制御プロセッサ内のスタックを示す図である。 第９ａ図と第９ｂ図は、各段階における各並列浮動小数
点プロセッサ内の制御点スタックを示す図である。 第１０ａ図と第１０ｂ図は、本発明に用いられるテフセ
レーシロン・パラメータの計算方法のｆ１１ｉ解に役立
つ図である。 第１１ａ図ないし第ｉｆｆ図は、本発明に用いるのが望
まれるＣｏｘ−ＤｅＢｏｏｒの評価法を示す図である。

Claims (20)

【特許請求の範囲】
1. （１）コンピュータ・グラフィクス・ディスプレイ・シ
   ステムのスクリーンにレンダリングするために、連続し
   たスパンから構成されたパラメトリック・カーブを表す
   ＮＵＲＢＳ（ノン・ユニフォーム・レイショナル・Ｂス
   プライン）データを、ポリラインの頂点のジオメトリッ
   ク座標に変換する方法であって、 上記カーブの第１スパンがデータ・レコードのシーケン
   スの第１サブセットによって定義されるとき、ＮＵＲＢ
   Ｓデータを該シーケンスとして先のデータ・レコードと
   ともにメモリ内に配置して、該カーブの対応する連続ス
   パンを定義するステップと、 上記シーケンス内のデータ・レコードの上記第１サブセ
   ットを読み取り、該サブセットを用いて、上記カーブの
   第１スパンに沿った所定のパラメータ点の座標を評価す
   るステップと、 上記シーケンスの連続した個々のデータ・レコードを読
   み取り、上記対応する連続スパンに沿った所定のパラメ
   ータ点の座標を評価するステップとを含む、方法。
2. （２）請求項（１）に記載の方法であって、パラメトリ
   ック・カーブのオーダをｋとしたとき、対応する連続ス
   パンに沿った点の評価に、連続した個別データ・レコー
   ドと２ｋ−３個の直前のデータ・レコードを用いる方法
   。
3. （３）請求項（２）に記載の方法であって、ＮＵＲＢＳ
   データがスパン当たりｋ個の制御点から構成され、評価
   の前に、該制御点をモデリング座標からビュー座標へ変
   換するステップと含む、方法。
4. （４）請求項（３）に記載の方法であって、重みをｗと
   したとき、変換された制御点座標を同次座標セットｗｘ
   、ｗｙ、ｗｚ、ｗに変換するステップを含み、上記評価
   ステップに、上記カーブに沿った所定パラメータ点に対
   する該座標セットの各成分のＢスプライン関数の同時評
   価が含まれ、パラメータ点のパラメトリック値をｔとし
   たとき、ｗｘ（ｔ）、ｗｙ（ｔ）、ｗｚ（ｔ）、ｗ（ｔ
   ）の各値が得られ、さらに、ｗｘ（ｔ）、ｗｙ（ｔ）、
   およびｗｚ（ｔ）の比を計算することによって、各パラ
   メータ点のジオメトリック座標を決定するステップを含
   む、方法。
5. （５）請求項（４）に記載の方法であって、上記評価が
   、（ａ）Ｃｏｘ−ＤｅＢｏｏｒプロセスに従い、（ｂ）
   上記座標セットの異なる成分を同時評価する複数の並列
   浮動小数点プロセッサによって実行される方法。
6. （６）請求項（５）に記載の方法であって、上記カーブ
   の各スパンが、ｋ個の制御点と２ｋ−２個の節点値によ
   って定義され、上記シーケンスが、カーブのオーダｋと
   制御点数ｎを指定する第１シーケンスと、 カーブの初期節点ないしｋ−１の節点に対する節点値を
   含む第２シーケンスと、 ｋ−１個の連続したデータ・セットから成り、各セット
   が、制御点と節点値の座標と関連する重みｗとから成り
   、該データ・セットがカーブの初期制御点ないしｋ−１
   の制御点およびｋないし２ｋ−２の節点に対するデータ
   を含む、第３シーケンスと、 ｎ−ｋ＋１個の連続したデータ・セットから成り、該デ
   ータ・セットが、カーブのｋないしｎの制御点および２
   ｋ−１ないしｎ＋ｋ−１の節点に対するデータを含む、
   第４シーケンスと、 ｎ＋ｋ個の節点値を含む第５シーケンスとを含む、方法
   。
7. （７）請求項（６）に記載の方法であって、上記第４の
   各データ・セットがテッセレーション・パラメータを含
   む方法。
8. （８）請求項（７）に記載の方法であって、テッセレー
   ション・パラメータを基にパラメトリック座標間隔を求
   めるステップと、 上記パラメトリック座標間隔がとられた所定のパラメー
   タ点の組を生成するステップとを含む、方法。
9. （９）請求項（８）に記載の方法であって、上記パラメ
   トリック・カーブが非有理式を持ち、重みｗを１に等し
   くセットするステップを含む、方法。
10. （１０）コンピュータ・グラフィクス・ディスプレイ・
    システムのスクリーンにおいて、オーダｋのパラメトリ
    ック・カーブの評価とレンダリングを行う方法であって
    、該カーブが、ＮＵＲＢＳデータによって表され、連続
    スパンから構成されて、各スパンが、ｋ個の制御点と２
    ｋ−２個の節点値によって定義されるとき、 制御点のモデリング座標および関連する重みと節点値を
    含むＮＵＲＢＳデータをデータ・レコードのシーケンス
    としてメモリに配置することにより、上記パラメトリッ
    ク・カーブの連続スパンが、シーケンスの直前の２ｋ−
    ３個のデータ・レコードとともに連続した個々のデータ
    ・レコードによって定義されるステップと、 上記データ・レコードをメモリから上記シーケンスで読
    み取るステップと、 上記制御点モデリング座標をビュー座標に変換するステ
    ップと、 変換された制御点座標に、関連する重みを掛けて、各制
    御点に対する同次座標セットｗｘ、ｗｙ、ｗｚ、ｗを得
    るステップと、 パラメトリック座標間隔を計算し、該間隔がとられたパ
    ラメータ点の組を生成するステップと、並列浮動小数点
    プロセッサが、上記組の各パラメータ点の座標セットの
    各成分に対するＢスプライン関数を同時評価するステッ
    プと、 上記評価ステップの結果から重みを消去して、上記パラ
    メータ点の組のジオメトリック座標を得るステップと、 ジオメトリック座標の順列点の各組によって定義された
    ベクトルを現在のビュー・ウィンドウにクリップするス
    テップと、 クリップされたベクトルを直線セグメントとしてコンピ
    ュータ・グラフィクス・ディスプレイ・システムのスク
    リーンに描き、よってパラメトリック・カーブのレンダ
    リングを行うステップとを含む、方法。
11. （１１）請求項（１０）に記載の方法であって、計算ス
    テップに続く全ステップがパイプライン方式で実行され
    る方法。
12. （１２）請求項（１１）に記載の方法であって、上記Ｎ
    ＵＲＢＳデータが配置されるシーケンスが、上記カーブ
    のオーダｋと制御点数ｎを指定する予備データと、 上記カーブの初期節点値と、 後節点および制御点のモデリング座標と重みから成り、
    上記カーブの第１スパンに関連するデータ・セットの組
    と、 上記カーブの連続スパンを完成し、連続した節点値、連
    続した制御点のモデリング座標と重み、およびテッセレ
    ーション・パラメータから成る、個別付加データ・セッ
    トの組と、 上記カーブの最終節点値とを含む、方法。
13. （１３）コンピュータ・グラフィクス・ディスプレイ・
    システムのスクリーンにおいてレンダリングを行うため
    に、オーダｋのパラメトリック・カーブを表すＮＵＲＢ
    Ｓデータをポリラインの頂点のジオメトリック座標に変
    換する装置であって、該カーブが、連続したスパンから
    成り、各スパンが、ｋ個の制御点と２ｋ−２個の節点値
    によって定義されるとき、 上記カーブのＮＵＲＢＳデータをデータ・レコードのシ
    ーケンスとして格納することにより、該カーブの連続ス
    パンが、該シーケンスの直前の複数のデータ・レコード
    とともに連続した個別データ・レコードによって定義さ
    れるメモリ手段と、 上記データ・レコードを上記メモリ手段から上記シーケ
    ンスで読み取り、制御点座標を一組の同次座標に変換す
    るグラフィクス制御プロセッサ手段と、 上記グラフィクス制御プロセッサ手段からデータを受け
    取り、上記カーブに沿った一組のパラメータ点の各点に
    おける上記一組の同次座標の各座標のＢスプライン関数
    を同時評価する複数の並列浮動小数点プロセッサと、 上記コンピュータ・グラフィクス・ディスプレイ・シス
    テムのスクリーンにおいて上記カーブのレンダリングを
    行うために、上記並列浮動小数点プロセッサの出力を受
    け取り、該出力を上記パラメータ点のジオメトリック座
    標に変換する次段の浮動小数点プロセッサとを含む、装
    置。
14. （１４）請求項（１３）に記載の装置であって、上記グ
    ラフィクス制御プロセッサ手段、複数の浮動小数点プロ
    セッサ、および次段の浮動小数点プロセッサがパイプラ
    イン方式で動作する装置。
15. （１５）請求項（１４）に記載の装置であって、上記複
    数の浮動小数点プロセッサが、 上記パラメータ点のそれぞれの重みを表す出力を与える
    プロセッサ１個を含めた４個のプロセッサから成り、 上記次段の浮動小数点プロセッサが上記並列浮動小数点
    プロセッサの他のプロセッサの出力に、上記１個の浮動
    小数点プロセッサの出力の逆数を掛ける、装置。
16. （１６）請求項（１５）に記載の装置であって、上記並
    列浮動小数点プロセッサが、Ｃｏｘ−ＤｅＢｏｏｒプロ
    セスを用いて評価を行い、上記複数の浮動小数点プロセ
    ッサの出力が上記次段の浮動小数点プロセッサへシーケ
    ンシャルに供給される、装置。
17. （１７）請求項（１６）に記載の装置であって、上記シ
    ーケンスが、 上記カーブのオーダｋと制御点数ｎを指定する予備デー
    タと、 上記カーブの初期節点値と、 後節点および制御点のモデリング座標と重みから成り、
    上記カーブの第１スパンに関連するデータ・セットの組
    と、 上記カーブの連続スパンを完成し、連続した節点値、連
    続した制御点のモデリング座標と重み、およびテッセレ
    ーション・パラメータから成る、個別付加データ・セッ
    トの組と、 上記カーブの最終節点値とを含む、装置。
18. （１８）請求項（１７）に記載の装置であって、上記グ
    ラフィクス制御プロセッサ手段が、 最初に制御点のモデリング座標をビュー座標に変換し、
    次に、変換された座標を上記一組の同次座標に変換し、 パラメトリック座標間隔を決定して上記パラメトリック
    ・カーブのテッセレーションを行い、間隔をとった一組
    のパラメータ点を生成して、上記複数の並列浮動小数点
    プロセッサに供給する、装置。
19. （１９）請求項（１８）に記載の装置であって、上記グ
    ラフィクス制御プロセッサ手段が、上記付加データ・セ
    ットのテッセレーション・パラメータに基づいて上記カ
    ーブの連続スパンのパラメトリック座標間隔を決定する
    装置。
20. （２０）請求項（１９）に記載の装置であって、上記次
    段の浮動小数点プロセッサの出力に直列に接続され、該
    プロセッサとパイプライン方式で動作するクリッピング
    ・プロセッサとフレーム・バッファとを含む装置。