JPH1049666A - 断片発生器および断片発生方法 - Google Patents

Abstract

(57)【要約】 【課題】画質を低下させることなく最小限のハードウエ
アオーバヘッドでオブジェクト/画像変換写像を行う。 【解決手段】画像データを写像する断片発生器を設け、
オブジェクトデータ配列をオブジェクト空間から画像空
間に順写像してデータ値を有するオブジェクトデータ点
ごとの画像空間アドレスからなるオブジェクトアドレス
集合を生成する。次に、画像空間内の、オブジェクトデ
ータ集合のある領域内に位置する画素を決定する。そし
て画素アドレスデータから、前記領域内の画素について
の距離を決定する。その距離を、前記データ値にたいし
て、前記画像空間から前記オブジェクト空間に逆写像す
る。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は一般的には画像処理に関
し、より詳細にはオブジェクト-画像写像中に画像デー
タの局所記憶を可能にするシステムおよび方法に関す
る。

【０００２】

【従来の技術】計算機ベースシステム上での画像処理に
おいて、画像は通常その計算機ベースシステムのグラフ
ィックスサブシステムによってレンダリングされ、ある
いは描画される。グラフィックスサブシステムによって
実行されるほとんどあらゆるタイプの画像処置には、オ
ブジェクト空間から画像空間（すなわち、画像空間中の
画素）への画像の写像および/または画像空間からオブ
ジェクト空間への画像の写像が不可欠である。これら２
つの写像操作にはいくつかの利点と問題点があり、その
うちの２、３を次に説明する。

【０００３】

【発明が解決しようとする課題】第一に、オブジェクト
空間から画像空間への写像の際に、画像空間への変換を
完了するためのオブジェクトデータ集合を１度だけの走
査にすることができる。これにはパイプライン動作に特
に適したストリームベースのアーキテクチャが可能であ
るという利点がある。当該分野では、グラフィックスサ
ブシステムの動作をパイプライン化することによって処
理の速度および効率が増大することは周知である。オブ
ジェクト空間から画像空間への写像の問題点は、人工的
な画像画素の生成にしか使用できないことである。した
がって、この方法の用途は通常画像が合成的に生成され
る３次元グラフィックスアクセラレータに限られる。そ
の結果、この方法は現在では画像あるいは２次元処理法
には用いられていない。

【０００４】第二に、画像空間からオブジェクト空間へ
の写像の際には、画像画素からオブジェクトデータへの
参照を維持して画像あるいは３次元処理の使用に適する
ものとすることができる。しかし、計算機ベースシステ
ムにおける画像空間からオブジェクト空間への写像の問
題点は、オブジェクト空間へのアドレス指定動作を支援
するために多量のハードウエアを必要とすることであ
る。たとえば、かかるシステムには比較的大容量のラン
ダムアクセスメモリ（RAM）とこのRAMに出入りするデー
タのフローを管理するためのコントローラが必要であ
る。通常、このRAMはその必要とされる量から、別のチ
ップ（すなわち集積回路）上に設け、グラフィックスサ
ブシステムに接続しなければならない。これはシステム
のコストと複雑性を大きくするため望ましいことではな
い。

【０００５】画像空間からオブジェクト空間への写像を
支援するのに要するハードウエアが大きな問題であるこ
とは明らかであるが、かかるハードウエアを最適化する
ことは可能である。ただし、この場合画質が犠牲になる
ことになる。たとえば、ハードウエアのオーバヘッドを
低減するためには、データビット数の低減、計算量の少
ない変換法の使用、あるいはオンボードメモリの量の低
減を行なうことが可能であるが、これははすべて画質の
低下につながるものである。にもかかわらず、この方法
はテクスチャデータを画像空間中の特定の画素に対応さ
せるためのハードウエアテクスチャ写像システムに広く
用いられている。

【０００６】したがって、当該分野において、画質を低
下させることなく最小限のハードウエアオーバヘッドし
か必要としないオブジェクト/画像写像システムおよび
方法が必要とされている。本発明はこれらの、また当該
分野では周知である従来技術の不備や欠点を克服するも
のである。

【０００７】

【課題を解決するための手段】上記課題を解決するた
め、画像アクセラレータ内の補間器と連動させて用いる
ことのできるオブジェクト-画像混成写像のための断片
発生器を可能とするものである。この断片発生器はハー
ドウエアオーバヘッド条件が最小限であり、したがっ
て、画像データを画像アクセラレータに対して局所的に
記憶することを可能とするものである。

【０００８】本発明の断片発生器は順写像機構と、画素
走査機構と、逆写像機構とからなる。アーキテクチャに
おいては、順写像機構、画素走査機構および逆写像機構
は好適にはこの順序でパイプライン化される。

【０００９】順写像機構はオブジェクトデータ配列を受
け取り、このオブジェクトデータ配列に順写像操作を実
行してこのオブジェクトデータ配列をオブジェクト空間
から画像空間に転送する。本発明の順写像機構はあらゆ
る同次アフィン変換を支援するものである。画像空間に
おいて、オブジェクトデータ配列は出力画像の画素を規
定する浮動小数点値のオブジェクトアドレス集合からな
る。さらに、順写像機構はこのオブジェクトデータ配列
からのデータ値を取り出して局所データバッファに入
れ、これが次に説明するように後に出力画像の画像空間
画素を局所オブジェクト空間に写像するのに用いられ
る。

【００１０】画素走査機構は順写像機構からオブジェク
トアドレス集合を受け取り、出力画像空間を走査して出
力画像を構成するオブジェクトアドレス集合中のすべて
の画素を位置づけるように構成されている。これを実行
するのに適した方法は多数あるが、ジャンセンサーペン
タインアルゴリズム（Jensen Serpentine algorithm)を
用いるのが好適である。出力画像の各画素について、画
素走査機構はオブジェクトアドレス集合からの基準点の
同定も行なう。

【００１１】逆写像機構は各出力画素とそれに対応する
基準点のアドレスを受け取り、それからその画素とそれ
に対応する基準点の間の距離を表わす各画素に関する１
つあるいはそれ以上の距離値“d”を決定する。次に、
逆写像機構は逆写像を実行して局所オブジェクト空間に
ついて画像空間からオブジェクト空間への距離値“d”
の変換を行なう。したがって、本発明の一特徴は、順写
像機構によって実行される順写像と逆写像機構によって
実行される逆写像とがほぼ互いに他の逆であることであ
る。これによって、距離値“d”は局所オブジェクト空
間に確実に戻される。

【００１２】距離値“d”は逆写像機構によってオブジ
ェクト空間に逆写像された後、その後の局所データバッ
ファ中のデータに実行される補間あるいは縮小等のスケ
ーリング操作に用いるスカラ係数の生成に用いられる。
スケーリング操作によってフレームバッファ中の出力画
素に写像される輝度値が生成される。したがって、断片
発生器と関連するスケーリング操作が互いに連動して最
小限の量の局所的ハードウエアによる幾何学的変換が実
行される。これは、オブジェクトデータ配列からのデー
タ量が比較的小さく、除去される前に一度しか通過しな
いためである。

【００１３】また、本発明は計算機ベースシステム上で
画像データを写像するためのオブジェクト-画像混成写
像法であって、オブジェクト空間内の、それぞれが対応
するデータ値を有する複数のオブジェクトデータ点から
なるオブジェクトデータ配列を受け取るステップと、前
記データ値を局所バッファに入れるステップと、前記オ
ブジェクトデータ配列をオブジェクト空間から画像空間
に、それぞれのオブジェクトデータ点に対する画像空間
アドレスからなるオブジェクトアドレス集合を生成する
ように順写像するステップと、前記オブジェクトアドレ
ス集合を走査して前記画像空間内の前記オブジェクトア
ドレス集合によって確定される領域内に位置する画素を
決定するステップと、前記領域内のそれぞれの画素につ
いて少なくとも１つの距離を決定するステップと、前記
局所データバッファ中の前記データ値についてそれぞれ
の距離を画像空間からオブジェクト空間に逆写像するス
テップとからなる方法を可能にするものとみることがで
きる。続いて、これらの距離値を用いて補間あるいは縮
小等のスケーリング操作に用いるスカラ係数を生成する
ことができる。スケーリング操作によって輝度値が生成
され、この輝度値はフレームバッファ中の表示される出
力画素に写像することができる。

【００１４】本発明のオブジェクト-画像混成写像シス
テムおよび方法には多くの利点があり、そのいくつかを
次に例として説明する。

【００１５】本発明のオブジェクト-画像混成写像シス
テムおよび方法の利点は、画像アクセラレータ内での画
像操作等のほとんどあらゆる従来の画像操作に対して用
いることができることである。

【００１６】本発明のオブジェクト-画像混成写像シス
テムおよび方法の他の利点は、画質を低下させることな
く、最小限の量の局所ハードウエアを用いる方法が提供
されることである。

【００１７】本発明のオブジェクト-画像混成写像シス
テムおよび方法の他の利点は、設計が簡単で、動作が効
率的で、製造コストの比較的低い断片発生器を可能とす
ることである。

【００１８】当業者には以下の図面と詳細な説明から本
発明の他の特徴および利点が明かとなるであろう。かか
る他の特徴および利点は特許請求の範囲に規定する本発
明の範囲に含まれるものである。

【００１９】

【発明の実施例】以下に本発明を実施するための現在考
えられる最良の態様を説明する。この説明は限定的な意
味に解するべきではなく、本発明の一般的原理を説明す
る目的で行なうものにほかならない。

【００２０】I. アーキテクチャ 本発明に係る断片発生器10は、オブジェクト空間から画
像空間への画像データのオブジェクト-画像混成写像を
実行する。断片発生器10の本実施例を２次元（２-D）変
換およびアップサンプリング補間を実行するための補間
器12との関連において説明する。しかし、本発明の断片
発生器10は、当業者には明らかな通り、本発明の直接の
延長として、縮小すなわちダウンサンプリングおよび３
次元（３-D）立体レンダリングにも適していることが指
摘できる。

【００２１】図１には、本実施例の断片発生器10がコン
ピュータシステム11内の画像アクセラレータ14内に設け
られた補間器12に一体の部分として示されている。前述
したように、断片発生器10は断片発生器10からの出力に
対するスケーリング操作を実行するための縮小装置ある
いは他の同様の装置に接続することもできる。

【００２２】補間器12に加えて、アクセラレータ14の画
像は、コンボルバーあるいはウィンドウ/レベル写像装
置等の１つあるいはそれ以上の他の画像操作を含むもの
とすることができる。画像アクセラレータ14は表示装置
20上で表示するための画像の処理速度を上げるためのグ
ラフィックスサブシステム18の一部として組み込まれて
いる。一般に、画像が画像アクセラレータ14によって処
理された後、その結果得られる画像データがフレームバ
ッファ22に送られ、続いてそこから検索されて表示装置
20上で表示される。

【００２３】グラフィックスサブシステム18によって処
理される画像は通常対応するメモリサブシステム24から
検索されるか、あるいは中央処理装置（CPU）26によっ
て人為的に生成される。メモリサブシステム24、CPU 26
およびグラフィックスサブシステム18は図１に示す入出
力装置28を介して相互接続される。さらに、メモリサブ
システム24内でアクセスすることのできるものより大き
いモデルを記憶するためにメモリディスク32が設けられ
ている。

【００２４】図２には単純なパイプライン方式のアーキ
テクチュアをとる断片発生器10を含む補間器12を示す。
断片発生器10を含む補間器12はメモリサブシステム24あ
るいはCPU 26からオブジェクトデータ配列を受け取り、
それから画像画素アドレスとそれに対応するデータ値を
生成するように構成され、これらのアドレスおよびデー
タ値は表示装置20上での表示に先立ってフレームバッフ
ァ22に送られる。本発明によれば、断片発生器10は順写
像機構36、画素走査機構38および逆写像機構40からな
る。

【００２５】順写像機構36は、図３に示すように規則的
な非回転の形態の格子42として構成された入力オブジェ
クトデータ配列に対する順写像操作を実行する。この格
子の各頂点はグレースケールあるいはRGBスケールとい
った色の強度に関するなんらかのスカラ値を表わすデー
タ点のアドレスを表わす。このとき、格子42上の頂点の
アドレスは表示装置20の画面上のいかなる特定の位置に
も関係しない。ただし、各頂点をXおよびYの両方向に１
画素単位だけ離れたものと考えることが有益である。こ
の入力オブジェクトデータ配列から各頂点に関連するデ
ータが取り出され、図４に示すようにそのもとの向きが
保たれた状態で局所データバッファ46（図２）に記憶さ
れる。本実施例の目的上、局所データバッファ46は後に
詳細に説明するラインバッファ48（図２）で構成され
る。

【００２６】順写像機構36はオブジェクトデータ配列
を、一実施例における剛体変換などの3x3順行列演算に
よって各頂点のアドレスを処理することによって図３に
示すようなオブジェクト空間から図５に示すような画像
空間に変換する。しかし、本発明の断片発生器10はFore
y他が“Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ Ｐｒｉ
ｎｃｉｐｌｅｓ ａｎｄ Ｐｒａｃｔｉｃｅ”第２版、
Ａｄｄｉｓｏｎ−Ｗｅｓｌｅｙ Ｐｕｂｌｉｓｈｉｎｇ
Ｃｏ．（1990年）で説明するような同次アフィン変換
群に適合するものであることに注意しなければならな
い。本実施例の目的上、剛体変換によって変換されるオ
ブジェクトにいかなる態様の歪みも生じないようになっ
ている（すなわち、角（かど）の角度は変換の全体を通
じて一定に保たれる）。したがって、順写像機構36は以
下の変換操作を順に実行する。すなわち、（１）データ
を（0, 0）がそのデータ中の回転の中心となる点となる
ように並進移動し、（２）このデータをスケーリング
し、（３）このデータを回転し、（４）回転のの中心が
画像空間内の適当な位置に来るように並進移動する。

【００２７】この順行列演算の結果、図５に示すような
画像空間（たとえば表示装置20）内のデータ点の位置を
表わすオブジェクトアドレス集合50が得られる。オブジ
ェクトアドレス集合50は複数の原データ領域51からな
る。原データ領域は画像空間内の３つあるいはそれ以上
のオブジェクトアドレス点によって確定される特殊な部
分集合である。したがって、入力されるオブジェクトデ
ータ配列はその最も単純な形態においては三角形の原デ
ータ領域を確定するわずか３つのデータ点すなわち頂点
からなる。さらに、オブジェクトアドレス点は非整数の
値によっても表わしうることを指摘しておく。たとえ
ば、オブジェクト空間内の元のデータ位置（0, 0）が画
像空間内で（3.123, 2.987）に位置することがありう
る。したがって、図５に示すように、出力画像は（オブ
ジェクト空間座標）’で表わされるオブジェクトアドレ
ス集合によって確定される対応する原データ領域内にあ
る画素48によって生成される。

【００２８】オブジェクトデータ配列に3x3順行列演算
を実行する代わりに、CPU 26を変換された基準アドレス
およびアドレス増分を用いて順写像機構36による順写像
を実行するようにプログラムすることもできる。この構
成では、基準アドレスはオブジェクトデータ配列中の第
１のデータ点、たとえば（0, 0）点に対応する出力画像
の点を規定する。アドレス増分は、オブジェクト空間内
の１つの画素のたとえばXおよびY方向の移動に対応する
画像空間内のアドレスの変化を記述するものである。図
３にはオブジェクトデータ配列42がオブジェクト空間に
示されており、図５には変換後のこのオブジェクトデー
タ配列が図示されている。基準アドレス位置（0, 0）’
から図５のオブジェクトアドレス集合を生成するために
は、指定された方向たとえばXおよびY方向にアドレス増
分を加えることによって基準アドレスから後続の各頂点
が求められる。さらに、この変換には当該分野において
周知である並進移動および回転演算が含まれる。

【００２９】画素走査機構38はオブジェクトデータ配列
の変換後のアドレスを受け取り、オブジェクトアドレス
集合を走査して、出力画像のレンダリングのために画像
空間内のどの画素が描画されるかを決定する。かかる画
素を以下“画像画素”と呼ぶ。原オブジェクトの走査に
ついてはラスタスキャンあるいは二重ブレシュナム（Br
eshenham）線画等の周知の方法がいくつかあるが、ここ
ではジャンセンサーペンタインアルゴリズムを用いる。
簡単にいえば、ジャンセンサーペンタインアルゴリズム
はオブジェクトアドレス集合によって確定される利用可
能な領域において間接的な方法で画素を選択する。選択
される画素は常にオブジェクトアドレス集合の境界内に
あり、画像空間を可能な最大限の速度で走査できるよう
になっている。

【００３０】図6Aおよび図6Bにジャンセンサーペンタイ
ンアルゴリズムを図示する。一般的に、ジャンセンサー
ペンタインアルゴリズムの走査方法はデータが描画され
る方向に見て最後方にある画素から開始される。この方
向は線画アルゴリズムにおいて用いられる主方向として
定義される。副方向はこの主方向に対して90゜を成し、
図6Bに示すように負方向（すなわち下向き）から正方向
（すなわち上向き）に変化しうる。図6Bにおいて、描線
54は下に向かい次に上に向かう（いずれも副方向）。こ
の方法では、第１の画素52から図6Aに示すような４つの
可能な方向のうちの１つの方向にある次の画素が選ばれ
る。４つの可能な方向とは、（１）負の副方向、（２）
副方向に負であり、主方向に正である方向、（３）正の
主方向、および（４）主方向に正であり、副方向に正で
ある方向、である。この次の画素は、それがオブジェク
トアドレス集合の境界内にあるという制限の範囲で、上
記の検討順序で選択される。したがって、第１の可能な
画素がオブジェクトアドレス集合の境界の外にある場
合、次の可能な画素が検討される。同様に、その画素が
オブジェクトアドレス集合の外にある場合、第３の可能
な画素が検討され、これが以下同様に繰り返される。図
6Bに示すように、画素52から選択された２つの次画素は
最初に検討された画素であるが、次の画素は３番目に検
討された画素である。これは最初の２つの画素がオブジ
ェクトアドレス集合の境界外にあるためである。

【００３１】上述したようにこの走査方法で各画像画素
が選択されると、ある特定の原データ領域51内の対応す
る基準角（かど）のアドレスもまた各画像画素について
記述される。したがって、この構成では、画素走査機構
38は４つの原オブジェクトアドレス点（すなわち角（か
ど））によって確定されるある特定の原データ領域51内
の画像画素を発見し、その画像画素アドレスを対応する
基準点（原データ領域51の４つの角（かど）アドレスの
うちの１つ）とともに逆写像機構40に送る。

【００３２】逆写像機構40（図２）はこの画像画素アド
レスとそれに対応する基準点アドレスとを受け取って、
まず各画素について１つあるいはそれ以上の距離値
“d”を計算する。本実施例では、距離値“d”は各画像
画素について決定され、より詳細には、下の式（１）お
よび式（２）によってd_x値とd_y値が決定される。

【数１】 ここで、X_{ref corner}は基準点アドレスのX座標、X_pixel
は画像画素のX座標、Y_{ref corner}は基準点アドレスのY
座標、Y_pixelは画像画素のY座標であり、これらはすべ
て画像空間内にある。これらは、集積回路技術によって
簡単に実施可能な単純な算術演算である。

【００３３】これらの距離d_xおよびd_yが次に局所オブジ
ェクトデータ空間（局所データバッファ46）について、
画像空間からオブジェクト空間に逆写像される。局所オ
ブジェクトデータについて距離値をたとえば単位間隔で
オブジェクト空間に入れるためには、逆写像機構40の逆
行列演算は順写像機構36を参照して上に説明した順写像
操作のほぼ逆である。

【００３４】たとえば、本実施例では、各距離はまず局
所データ空間の（0, 0）角（かど）について並進移動さ
れる。次に、各距離値について、順写像に用いられた角
度であってその反対方向の角度の回転および順スケーリ
ングの逆数すなわち１/（順スケーリング）である係数
によるスケーリングを含む逆行列演算によって変換され
る。並進移動は逆写像での係数を生じない。これは、画
像データは局所データバッファ46の（0, 0）点に対して
回転を要するだけであるためである。したがって、この
逆行列演算は本実施例では2x2行列関数を用いて実行さ
れる。非剛体演算が用いられる場合、これは透視を含む
完全な3x3行列でなければならない。

【００３５】距離値d_xおよびd_yは局所オブジェクト空間
に逆変換された後、それぞれX係数発生器70およびY係数
発生器72に送られる。

【００３６】XおよびY係数発生器70、72はそれぞれX補
間器74およびY補間器76によって用いられる係数を生成
する。したがって、対応する補間器74および76の実行す
る補間法に応じて、X係数発生器70とY係数発生器72の動
作は多少異なる場合がある。X補間器74が３次補間を実
行し、Y補間器76が３次補間を実行する本実施例では、X
およびY係数発生器70、72はそれぞれ４つの係数C0、C
1、C2およびC3を生成する。係数C0-C3の値は画像画素位
置から近傍のオブジェクトアドレス点までの距離の３次
関数である。たとえば、図７には逆写像機構40によって
計算される距離値“d”は画像画素80から角（かど）基
準点82までの距離として示されている。さらに、画像画
素80から単一方向（たとえばXあるいはY）の他の近傍オ
ブジェクトアドレス点84もまた距離値“d”を用いて記
述される。それぞれの近傍オブジェクトアドレス点につ
いて、局所データバッファ46内のデータの補間に用いる
係数を下の式（３）にしたがって計算することができ
る。

【数２】

【００３７】式（３）において、値Aはユーザーによっ
てプログラム可能なパラメータであり、その値はGeorge
Wolbergの“Digital Image Processing”初版、ISBN0-
8186-8944-7の129-131ページに規定するように通常は-3
および0である。上述した近傍オブジェクトアドレス点
のそれぞれについて図７に示す距離値“d”を組み込む
ことによって、式（４）（以下の４本の式の総体）によ
って次の係数値C0、C1、C2およびC3を生成することがで
きる。 C0 = Ad³ - 2Ad² + Ad C1 = (A + 2)d³ - (A + 3)d² + 1 C2 = -(A + 2)d³ + (2A + 3)d² - Ad C3 = -Ad³ + Ad²

【００３８】この態様では、式（４）に示すように、X
係数発生器70およびY係数発生器72内で係数値を得るた
めに必要な乗算器の数は上の式（３）で必要な数より少
ない。さらに、XおよびY係数発生器70、72に要する加算
器の数も同様に少なくなる。これによって画像アクセラ
レータ14（図１）の性能が向上し、コストが低減され、
必要なスペースが小さくなる。

【００３９】図２に戻って、X補間器74は、局所データ
バッファ46のラインバッファ48から受け取った原データ
に３次補間を実行するために、X係数発生器70からX係数
C0、C1、C2およびC3を受け取る。X補間器74は３次補間
を実行するが、本発明の混成写像法によれば、これら係
数発生器で生成される値を変更することによって線形補
間あるいは最近傍補間といった他の適当な補間法を支援
することも可能であることがわかる。たとえば、線形補
間の場合には、C0 ＝ ０、C1 ＝ 1 - d_x、C2= d_x、C3
＝ ０である。X補間器74は図８に示すように4x4x1のコ
ンボリューション核90からなる。核90のそれぞれの列に
は、局所データバッファ46のラインバッファ48から受け
取った４つのデータ点に１次補間を実行するための４つ
の核レジスタ92がある。

【００４０】X補間器74は局所データバッファ46を構成
する３つのキャッシュラインバッファ48と入力データス
トリーム線96から原データを受け取る。かかるデータ値
はオブジェクトデータ配列から順次取り出され、先入れ
先だし（FIFO）動作するラインバッファ48にシリアルに
ロードされ、ラインバッファAが最初に満たされ、ライ
ンバッファBそしてラインバッファCと続く。３つのライ
ンバッファすべてにデータがロードされると、画像処理
の開始が可能となる。バッファCからデータが出力され
ると、これはバッファBの最後ににもロードされ、バッ
ファBからバッファAに、また入力データストリームから
バッファCに同様にロードされる。ラインバッファ48は
オブジェクトデータの全ラインを保持しなければならな
いため、これらのバッファは可能な最大のオブジェクト
配列のデータと同じ長さでなければならない。この制約
はオブジェクトデータの部分集合に複数回の操作を実行
することによって克服することができる。適当な回路を
設けることによって、画像を容易に切れ目無くつない
で、非常に小さなラインバッファでそれよりはるかに大
きな画像を処理することができる。かかる重複領域の処
理にさいして速度が多少犠牲になるため、ラインバッフ
ァは可能なかぎり大きなものにすることが有益である。
本発明においては、局所データバッファ46は比較的小さ
く、したがって最小限の量のハードウエアを用いてオン
ボードRAMとして製作するのに適している。

【００４１】本発明の一特徴によれば、局所データバッ
ファ46は局所オブジェクト空間内の入力データ配列から
のデータ値を、かかるデータを補間器12によって１回で
補間しうるように記憶する。これは、補間に要するデー
タのすべてを局所データバッファ46内のデータに限定
し、出力画素値を生成するために局所データバッファ46
の外に出る必要がないために可能なことである。この利
点は局所オブジェクト空間に関係し、また局所データバ
ッファ46に保持された原データに対応する距離値“d”
を生成する断片発生器10によって可能となる。本実施例
では、ラインバッファ48は集積回路技術を用いて簡単に
構成され、わずかなスペースしか必要とせずしたがって
画像アクセラレータ14とともに基板上に製作可能なシフ
トレジスタからなる。

【００４２】図２に再度戻って、X補間器74はX係数発生
器70から係数C0、C1、C2およびC3を受け取る。図８に示
すように、C0係数はレジスタR0、R4、R8およびR12内の
各原データ値とともにX補間に用いられ、C1係数はレジ
スタR1、R5、R9およびR13内の各原データ値に対して用
いられ、C2係数はレジスタR2、R6、R10およびR14内の各
原データ値に対して用いられ、C3係数はレジスタR3、R
7、R11およびR16とともに用いられる。

【００４３】X補間器74の３次補間についていえば、当
該分野において周知の通り、適当な係数に、それに対応
する核レジスタ92（すなわちR0-R16）に保持されたデー
タ値が乗じられ、対応する各列からの値が加算されて各
列に対する１つの画素データ値が得られる。したがっ
て、X補間器74の出力は４つの画素データ値からなり、
これらがY補間器76に送られる。

【００４４】Y補間器76においては、図９に示すよう
に、X補間器72からの４つの画素データ値に対して核98
においてY係数発生器72によって生成された対応するY係
数C0、C1、C2およびC3が乗じられる。Y係数発生器72は
係数C0-C3をX補間器74とほぼ同じ式すなわち式（４）を
用いて生成するが、逆写像行列40によって供給される式
（４）への入力距離値は値d_yであることを指摘してお
く。次に、Y補間器76がこれらの係数および画素データ
値の積を加算して１つの出力画素値を求める。その結果
得られた画素値がフレームバッファ22において画素走査
機構からの適当な画素アドレスと組み合わせられる。断
片発生器から同期パルスが送出され、このパルスがかか
るデータ値をラインバッファ内でシフトされ局所データ
領域に入るデータに同期させる。

【００４５】II. 操作方法 また、本発明は図10に示すように、以下のステップから
なる画像データを写像するオブジェクト-画像混成写像
法を提供するものである。まず、ブロック102におい
て、あるオブジェクトデータ配列に関連するデータ値が
局所データバッファ46に入れられる。次に、ブロック10
4に示すように、このデータ配列がオブジェクト空間か
ら画像空間に順写像されてオブジェクトアドレス集合が
生成される。この順写像操作は、透視を含む同次アフィ
ン変換群の任意の１つとすることができる。しかし、本
実施例では、順写像は剛体変換である。

【００４６】次に、ブロック106に示すように、画像空
間内のどの画素がオブジェクトアドレス集合中にあるの
かを決定するためにオブジェクトアドレス集合の走査が
行なわれる。上述したように、ラスタスキャンあるいは
二重Breshenham等使用可能な適当な走査方法は多数存在
するが、ここでは上に詳述したジャンセンサーペンタイ
ンアルゴリズムを用いる。

【００４７】次に、ブロック108に示すように、オブジ
ェクトアドレス集合内の基準点からの距離を表わす少な
くとも２つの距離が各画素について決定される。かかる
距離値は後続のスケーリング操作において局所データバ
ッファ46中のデータ値に適用される重み付け係数となる
ものである。

【００４８】最後に、ブロック110に示すように、これ
らの距離のそれぞれが局所データ空間内のデータ値につ
いて画像空間からオブジェクト空間に逆写像される。本
発明の一特徴によれば、順写像操作と逆写像操作とは互
いの逆を成すものである。これによって、逆写像によっ
て距離値が局所オブジェクト空間に設定されることを確
実にする。

【００４９】上述したステップが完了すると、局所デー
タバッファ中のデータ値と距離値は、当該分野で周知の
補間（すなわち、倍率≧１であるアップスケーリング）
あるいは縮小（すなわち倍率＜１であるダウンスケーリ
ング）等のスケーリング走査によってさらに処理できる
状態にある。基本的には、上述したステップによって、
データ値と生成された距離とは、データ値のスケーリン
グを最小限の量のハードウエアで画質を犠牲にすること
なく容易に行ないうる態様で効率的に用意される。

【００５０】後続のスケーリング操作についていえば、
局所データバッファ中のデータ値は本実施例では局所オ
ブジェクト空間に写像された距離値を用いて補間され
る。この補間においては、良好な結果が得られるという
理由から双３次補間が用いられるが、双線形補間、最近
傍補間および他の多くの補間法を用いることができる。
この補間によって画像画素値が生成され、これがフレー
ムバッファに送られて、表示装置上での表示が行なわれ
る。

【００５１】この詳細な説明を終えるにあたって、当業
者には本発明の原理から実質的に逸脱することなく、本
実施例に対して多くの変更や改造を加えうるであろうこ
とを指摘しておく。かかる変更および改造はすべて特許
請求の範囲に記るす本発明の範囲に含まれるものであ
る。さらに、特許請求の範囲において、対応する構造、
材料、動作およびすべての手段あるいは追加機能要素の
均等物には、具体的に特許請求される他の被請求要素と
の組み合わせにおいてその機能を実行するあらゆる構
造、材料あるいは動作が含まれるものである。以下に本
発明の実施態様を例示する。

【００５２】（実施態様１）画像データを写像するため
の断片発生器（10）であって、オブジェクトデータ配列
をオブジェクト空間から画像空間に順写像して、前記オ
ブジェクトデータ配列に含まれデータ値を有するオブジ
ェクトデータ点のそれぞれの画像空間アドレスからなる
オブジェクトアドレス集合を生成する順写像機構（36）
と、前記オブジェクトアドレス集合を受け取りこれを走
査して、前記画像空間内の、前記オブジェクトデータ集
合のある領域内に位置する画素を決定する画素走査機構
（38）と、画素アドレスデータを受け取り、前記領域内
の前記画素のそれぞれについて少なくとも１つの距離を
決定し、前記距離のそれぞれを前記データ値に対して前
記画像空間から前記オブジェクト空間に逆写像する逆写
像機構（40）とからなることを特徴とする断片発生器
（10）。

【００５３】（実施態様２）実施態様１に記載の断片発
生器であって、前記画素走査機構はジャンセンサーペン
タインアルゴリズムを実行する手段からなることを特徴
とする断片発生器。 （実施態様３）実施態様１に記載の断片発生器であっ
て、前記順写像機構（36）および前記逆写像機構（40）
はほぼ逆の操作を実行することを特徴とする断片発生
器。 （実施態様４）実施態様１に記載の断片発生器であっ
て、前記順写像機構（36）は剛体座標変換を実行するこ
とを特徴とする断片発生器。 （実施態様５）実施態様１に記載の断片発生器であっ
て、さらに前記オブジェクトデータ点に関連するデータ
値を記憶するための局所データバッファ（46）を有する
ことを特徴とする断片発生器。

【００５４】（実施態様６）実施態様５に記載の断片発
生器であって、さらに前記局所データバッファ（46）中
の前記データ値を前記画像空間内の距離で補間して前記
オブジェクトデータ集合の前記領域内の前記画素のそれ
ぞれの輝度値を生成する補間器（12）を有することを特
徴とする断片発生器。 （実施態様７）実施態様５に記載の断片発生器であっ
て、前記局所データバッファ（46）は前記データオブジ
ェクト配列の幅にほぼ等しい長さのキャッシュラインか
らなることを特徴とする断片発生器。 （実施態様８）実施態様６に記載の断片発生器であっ
て、前記補間器（12）は前記距離と双３次コンボリュー
ション核とから補間係数を生成するように構成された係
数発生器（70、72）からなることを特徴とする断片発生
器。

【００５５】（実施態様９）画像データを写像するため
の方法であって、データ値を有するオブジェクトデータ
配列をオブジェクト空間から画像空間に順写像して少な
くとも２つのエッジを有するオブジェクトアドレス集合
を生成するステップ（104）と、前記オブジェクトアド
レス集合を走査して、前記画像空間内の、前記オブジェ
クトデータ集合のある領域内に位置する画素を決定する
ステップ（106）と、前記領域内の前記画素のそれぞれ
について、前記オブジェクトアドレス集合の第１のエッ
ジからの第１の距離と前記オブジェクトアドレス集合の
第２のエッジからの第２の距離とを決定するステップ
（108）と、前記第１および第２の距離のそれぞれを、
前記データ値に対して前記画像空間から前記オブジェク
ト空間に逆写像するステップ（110）とからなることを
特徴とする方法。 （実施態様10）実施態様９に記載の方法であって、前記
順写像ステップと前記逆写像ステップとはほぼ逆の操作
であることを特徴とする方法。

【図面の簡単な説明】

【図１】計算機ベースシステム内で実施された本発明の
断片発生器を示すブロック図である。

【図２】図１の断片発生器および補間プログラムのアー
キテクチャおよび機能を示すブロック図である。

【図３】オブジェクトデータ配列を示す図である。

【図４】図３のオブジェクトデータ配列から取り出され
局所データバッファに記憶されたデータ点の概略図であ
る。

【図５】図３のオブジェクトデータ配列の画像空間表現
の図である。

【図６Ａ】ジャンセンサーペンタインアルゴリズムの概
略図である。

【図６Ｂ】ジャンセンサーペンタインアルゴリズムの概
略図である。

【図７】距離値“d”を規定する座標関係の概略図であ
る。

【図８】図２のX補間プログラムに用いられる4x4x1の３
次元コンボリューション核の概略図である。

【図９】図２のＹ補間プログラムに用いられる1x4x1の
３次元コンボリューション核の概略図である。

【図１０】本発明に係るオブジェクト-画像混成写像を
実行する図１の断片発生器の動作のフローチャートであ
る。

【符号の説明】

10：断片発生器 11：コンピュータシステム 12：補間器 14：画像アクセラレータ 18：グラフィックスサブシステム 20：表示装置 22：フレームバッファ 24：メモリサブシステム 26：中央処理装置（CPU） 28：入出力装置 36：順写像機構 38：画素走査機構 40：逆写像機構 42：格子 46：局所データバッファ 48：ラインバッファ 50：オブジェクトアドレス集合 51：原データ領域 52：第１の画素 54：描線 70：X係数発生器 72：Y係数発生器 74：X補間器 76：Y補間器 80：画像画素 82：角（かど）基準点 84：近傍オブジェクトアドレス点 90：コンボリューション核 92：核レジスタ 96：入力データストリーム線 98：核 102、104、106、108、110：写像ステップ A、B、C、：ラインバッファ C0、C1、C2、C3：補間係数 d：距離 R0-R16：レジスタ

Claims (1)

【特許請求の範囲】
1. 【請求項１】 画像データを写像するための断片発生器
   であって、 オブジェクトデータ配列をオブジェクト空間から画像空
   間に順写像して、前記オブジェクトデータ配列に含まれ
   データ値を有するオブジェクトデータ点のそれぞれの画
   像空間アドレスからなるオブジェクトアドレス集合を生
   成する順写像機構と、 前記オブジェクトアドレス集合を受け取りこれを走査し
   て、前記画像空間内の、前記オブジェクトデータ集合の
   ある領域内に位置する画素を決定する画素走査機構と、 画素アドレスデータを受け取り、前記領域内の前記画素
   のそれぞれについて少なくとも１つの距離を決定し、前
   記距離のそれぞれを前記データ値に対して前記画像空間
   から前記オブジェクト空間に逆写像する逆写像機構とか
   らなることを特徴とする断片発生器。