JP2000516747A - 像処理方法および装置 - Google Patents

Abstract

(57)【要約】 組立多角形像プリミティブから像を発生する像処理方法および装置を述べる。描画に対する先行モデルとして、プリミティブの順序リストを確認される変質ケース（４６、４８）および廃棄される変質ケース（４４）によって組立てる。次に、変質ケースを除去した後、残りのプリミティブに一連のテスト（５２、５６、６０、６２）を施して特定のケースを識別し、これによりプリミティブのスパンおよび底部スパンの右側画素を省略する描画技術を実施して描画動作を簡単化する。

Description

【発明の詳細な説明】 像処理方法および装置発明の技術分野 本発明は像処理方法および像処理装置に関するものであり、特に像プリミティ ブとして既知の多数の個別の多角形表面から構成された像の描画に関するもので ある。発明の背景 多角形、特に取扱いの容易な三角形のメッシュとして物体をモデリングするこ とはリアルタイムコンシューマーグラフィックスにおいて普通の技術である。こ れは特に３次元像データから２次元像を得るために、３次元空間に物体表面を形 成する多角形を２次元空間に投影し、任意の必要な計算またはルックアップテー ブルの参照に次いで適宜の画素値（カラー、テクスチュア等）を投影された２次 元多角形内の画素位置に写像（マッピング）するようにした３次元物体モデリン グの場合である。３次元空間から２次元空間に多角形を変換した後の計算は表示 画素値の組を発生させるために、プロセッサパイプラインによって好適に処理さ れる。 ３次元グラフィックス表示システムに用いられ、多角形プロセッサの直列結合 されたチェーンを具えるかかるプロセッサパイプラインの例は米国特許4,855,70 3(ディーリング／シュランバーガー)に記載されている。３次元空間から２次元 空間に多角形を変換した後、多角形をこれらが現われる第１表示画素ラインの参 照（規準）によって、走査順に分類する。走査ラインの処理前に、新たに導入さ れた多角形の各々をこれらも記憶されているチェーンのプロセッサの各々にロー ドして、順次の走査ラインへの寄与をも導出する。特定の多角形によって被覆さ れない走査ライン（即ち、所謂３角形の底頂部以下の第１の明瞭なライン）に到 達すると、この多角形は、新たな多角形データ得るために、チェーンのプロセッ サから取出すことができる。１走査ラインの処理後、このラインの画素データは （陰極線管、ＣＲＴ装置のような）表示装置に直接送るか、または陰極線管のア クセス用のフレームバッファに記憶することができる。 走査ラインの処理開始前に、他の作動特にエッジスロープの計算を必要とする ２次元多角形を用意する予備処理を行ない、この予備処理によってシステムの総 合性能を制限するに充分なコンピュータ的なリソースを消耗する場合がある。こ の工程をいくぶん簡単化する技術は米国特許4,930,091(シュレッダーおよびディ ーリング／シュランバーガー)に記載されており、この技術を上記米国特許4,855 ,703のシステムに適用する。この技術には３角形分類法を用いて３角形の複数の パラメータを３角形の頂角の供給座標から計算する。次いで、これらのパラメー タを用いてパラメータの変化する組合せによりカバーされている３角形の全ての 可能な形状で、３角形の分類を含むルックアップテーブルをアドレス指定し：即 ち、ルックアップテーブルから一旦読出された３角形分類によってこの３角形を パイプラインで処理すべき手段を決めるようにする。３つの頂角全部が直線上に 位置し、（従って３角形自体が直線となるか、またはこれら頂角が互いに接近し て３角形が画素を囲まなくなり、（従って、表示画像に示されない）場合には、 ３角形が変形している場合には、続く処理は行なわない。発明の概要 像の不必要な処理のあるものを回避するこれらの変形ケースを認識しながら、 更なる節約を必要とすることを認識し、本発明はグラフィックス描画処理の効率 を改善せんとするにある。 本発明像処理方法は複数の多角形像プリミティブで構成される２次元画素像を 描画する像処理を行うに当たり、次のステップ： （ａ）像プリミティブをその完成像内の位置に関して分類するとともにこのプ リミティブの順序リストを発生し； （ｂ）１画素の最大水平寸法または最大垂直寸法を有する像プリミティブを変 質として指定するとともにこの変質プリミティブを描画前のリストから除去し； （ｃ）２画素の最大水平寸法または最大垂直寸法を有する像プリミティブを特 定として指定し、この特定プリミティブをその頂角の配列に従って分類し、且つ この特定のプリミティブを前記リスト内で識別し； （ｄ）その特定の分類に従って処理される前記ステップ（ｃ）で識別されたこ れら特定のプリミティブで像を描画し、互いのプリミティブに対しそのプリミテ ィブによって交差された各走査ラインに対し、像プリミティブにより交差された かかる各走査ラインの部分の端部画素および像プリミティブにより交差された最 上側および最下側の画素の所定のものの全ての画素に対するプリミティブ寄与を 無視する、ステップを具えることを特徴とする。 本発明によれば、観察により初期変形プリミティブ以外のある場合に、完全な 計算を必要としなくなるようにする。これらの場合を確認することにより、およ び上記ステップ（ｅ）のプリミティブ分類に従って簡単化された計算を用いるこ とにより、物体がかなりの距離で観察され、（従って、２次元スクリーンに投影 される際に各多角形が処理時間によって小さくなる）際に発生するような、およ び円滑な湾曲表面をシミュレートするために、極めて多数の小さな多角形から構 成された物体を表示するための、景色に多くの小さな多角形が存在する際の処理 時間を著しく節約し得ることを確認した。 無視すべき予備プリミティブ画素の寄与の、プリミティブによってカバーされ た各走査ライン部分の右側画素および最低部の画素を好適に選択する：これによ りプリミティブ境界における描画問題を防止する手助けをする。この特定のプリ ミティブはそれらの配列に依存する多数のカテゴリに入る。特定のカテゴリの各 クラスは請求項に記載された共通の描画技術を有し、且つ発明の以下に記載する 実施例から明らかである。 像プリミティブを分類する初期ステップは頂部のｘｙ位置以上を考慮する。例 えば、各像プリミティブが関連する深度値を有する箇所で分類のステップは更に その個別の深度値に従う像プリミティブの分類を具える。或は又、または追加的 に、各像プリミティブが関連する透明度値を有する箇所で、分類のステップは１ つ以上の不透明プリミティブによって全体的にカバーされたそのプリミティブを リストから除去することをさらに含む：斯様にして、変形または閉込プリミティ ブを描画する試みに時間の浪費がないようにする。 また、本発明は第１および第２メモリに結合されたデータプロセッサを具え、 第１メモリは処理用像プリミティブデータを保持し、第２メモリは動作プログラ ムに従って作動する際、データプロセッサの動作プログラムを保持するようにし た像処理装置において： 前記第２メモリのデータに基づき、像プリミティブをその完成像内の位置に関 して分類するとともにこのプリミティブの順序リストを発生する手段と； １画素の最大水平寸法または最大垂直寸法を有する像プリミティブを変質とし て指定するとともにこの変質プリミティブを描画前にリストから除去するように 配列された手段と； ２画素の最大水平寸法または最大垂直寸法を有する像プリミティブを特定のも のとして指定し、この特定プリミティブをその頂角の配列に従って分類するよう に配列され、且つこの特定のプリミティブを前記リスト内で識別する手段と； 前記第１メモリのデータから像を描画するように配列され、特定のものとして 識別されたこれらプリミティブはその特定の分類に従って処理され、互いのプリ ミティブに対しそのプリミティブによって交差された各走査ラインに対し、像プ リミティブにより交差されたかかる各走査ラインの部分の端部画素および像プリ ミティブにより交差された最上側および最下側の画素の所定のものの全ての画素 に対するプリミティブ寄与を無視するように構成された像描画手段と；を具える ことを特徴とする。 本発明は３角形プリミティブシステムを一例として説明したが、後述する原理 は３つ以上の頂角を有する多角形プリミティブにも同様に適用することができる 。図面の簡単な説明 図１は本発明を実施するに好適な像処理システムの構成を示すブロック該略図 である。 図２は３角形像プリミティブの画素に対する慣例の走査ライン配列を 示す説明図である。 図３−８は異なる種々の特定の場合のプリミティブの有効画素および無効画素 を示す説明図である。 図９は本発明を実施する像プリミティブ分類の処理を示すフローチャート図で ある。発明を実施するための最良の形態 像処理装置として構成されたデータ処理システムを図１に示す。このデータ処 理システムは３次元像データを処理してバーチュアル−３次元世界でモデル化さ れた物体の２次元視野表示するように配列された処理ユニットＣＰＵ１０を具え る。このＣＰＵ１０はデータ兼アドレスバス１２を経てランダムアクセスメモリ ＲＡＭ１４およびリードオンリメモリＲＯＭ１６に結合するとともに好適なイン ターフェース１８を経て他の（オフーライン）データ記憶装置ＯＬＳ２０にも接 続する。ＯＬＳ２０は好適には３次元データのソースを提供するとともに磁気デ ィスク、光学ディスク、磁気−光学ディスクその他好適な記憶媒体のような永久 記憶装置からＣＰＵ１０の作動を制御する。ＯＬＳの形態の主制約はインターフ ェース１８およびバス１２を経てＣＰＵ１０に所要速度でデータを供給し得るよ うにする点である。 また、接続されたビデオモニタＶＤＵ２４にビデオ像を発生するように配列さ れたフレームバッファ兼ディスプレイ駆動段２２を前記バスに接続する。像発生 処理に対するユーザの制御または寄与を行なうために、ユーザ入力装置インター フェース２６をキーボード２８および前記インターフェースに接続されたマウス ３０のような入力装置とともにバス１２に接続する。 ３次元データは３次元座標空間の多面体頂角の位置の規定として記憶する。Ｖ ＤＵ２４にフレーム順次に発生する３次元データの２次元視野は直線によって接 続され、正味の平坦多角形を規定する頂角を考慮することによって発生する。視 野は、可能には、背面選択等を実行した後各多角形を考慮してお考慮中特定の視 野から見えない多角形を除去するようにして描画する。その後、多角形のリスト を規定し、これにより多角形が正しい順序で描画されるようにする。 便宜上、多角形描画の慣例の技術をまず最初３角形プリミティブを示す図２に つき考察する。３角形を描画する慣例の技術では、頂部から開始し、３角形が完 了するまで”スパン”を描き、この際、１スパンはスクリーンの画素の１行（列 ）によってカバーされた３角形の部分とする。各スパンに属する画素を図２にそ のスパン番号で示す。 ３つの頂角を垂直（ｙ）方向に分類することにより処理を開始し、これら頂角 を頂部頂角Ｖ_T，中間部頂角Ｖ_M，および底部頂角Ｖ_Bとする。この処理が一旦行 なわれると、３角形は４つのカテゴリの内の１つに分類することができる。頂 部頂角および中間部頂角のｙ値が同一である場合には、頂角は平坦となり、中間 部頂角および底部頂角のｙ値が同一である場合には、底部頂角が平坦となる。３ つの頂角全部のｙ値が同一である場合には、３角形は変形し、後述するように、 描画する必要はない。残りの２つのケースは相当に大きな３角形に対し最も共通 のものであり、数個の画素のみをカバーする小さな３角形に対しては必要ではな いが、３つの頂角全部のｙ値が異なる場合の状況をカバーする。そのうちの１つ は３角形の左側が２つの端縁部に分割されその接合部に頂角ＶＭを有する左側分 割のケース（図２に示す）である。右側端縁部が分割される場合には右側分割の ケースが生じる。これら４つのケース（変形のケースは含まれない）の各々にお いて、プリミティブの全ての端縁傾斜部を計算する。平坦頂部および平坦底部を 有する３角形に対しては、２つの傾斜部を計算するが、左側／右側分割のケース に対しては３つの傾斜部が存在する。 画素が２の３角形を接合する場合の縁部の両側の１部分を含む場合には、画素 を２回描画してはならないことは重要である。この２重描画の回避を行なうには 部分的には描画時間を節約するが、特に発生し得るエラーを除去するようにする 。特に、画素が半透明で、表示画素の色／テクステュアが最前端プリミティブの 後方の１つ以上のプリミティブからの寄与を含む場合には、画素が二重であれば 、前方および重畳プリミティブの相対寄与の計算を誤るようになる。この結果、 例えば、これがそのままよりも調光の現われる画素となる。 この重畳を回避するために、各スパンの右側画素を描画しないままとするとと もに底部スパンを描画しない儘にして、２つのプリミティブの境界の画素をこれ ら２つのプリミティブの一方に対し考察するようにすることは既知である。この 処理ステップのため、上記変形ケースは何ら描画動作に必要でない。その理由は これが底部スパンであり、従って考察しない１つのスパンのみを含むからである 。 他の処理は、無視すべき考察されていないこれら画素を有する処理を簡単化し 得るこれらプリミティブを特定のケースとして認識することによって、ある画素 プリミティブの寄与を考察しないこのステップの結果として、省略することがで きる。これら特定のケースおよび各々が受信する簡単化処理を図３乃至図８の画 素レイアウトダイアグラムに示し、図中、０はプリミティブによってカバーされ 、 （上述した理由で）描画されない画素を示し、１は描画する必要のある画素を示 し、添字”max”、”mid”および”min”は３角形頂角の座標に適用された場合 に、それぞれ最大値、中間値および最小値を示す。 第１の特定のケースはこれらプリミティブが２画素の水平頂部（ｙ_maxの２つ の頂角）および垂直範囲（ｙ_max−ｙ_min）を有する。頂部幅（本例では、ｙ_max −ｙ_min）が２画素である場合には、図３に示すように、合成描画は頂角位置で 単一画素を必要とする。頂部幅が２画素以上である場合には、図４に示すように 、画素の簡単な水平ラインを必要とする。右側の画素の寄与が全ての場合にドロ ップされる場合には、高さ２画素、幅Ｎ画素の平坦頂部３角形に対する手順は左 側頂角から（Ｎ−１）画素の水平ラインを描画する必要がある。 次のケースは２画素の高さおよび任意幅の平坦な底部プリミティブ（ｙ_minに おける２つの頂角）の場合である。前のケースの逆、即ち、画素の水平ラインを プリミティブの底部ラインとし、従って描画しないが、単一頂部画素は１スパン の右側と見なす必要があり、同様に図５に示すように描画しない。従って、この 結果は描画しないケースである。 次のケースは幅が２画素で、高さが任意の平坦頂部プリミティブ（図６）およ び平坦底部プリミティブ（図７）の場合である：ここに幅とはプリミティブによ ってカバーされ、水平な範囲（ｙ_max−ｙ_min）を有さない区域を意味するものと する。また、ここにベクトル（即ち、画素の単一ライン）とは描画すべきベクト ルの長さと相俟って計算する必要のある１スロープのみで描画する必要があるこ とを意味するものとする。この場合、例えばテクスチュア値の水平スロープの計 算は必要ない。 最終ケースは、２画素の幅（再び水平範囲でない）および任意の高さを有し、 図８に示すように、平坦頂部でなく、平坦底部でもない場合である。この場合に は、３つ縁部の全てに対するスロープは計算する必要はないが、合成画素パター ンが水平スロープ計算を必要としない簡単なラインであると云う事実から節約を 行なうことができる。 プリミティブを分類する総合選択処理を図９のフローチャートに示す。スター ト４０から出発し、最初のステップ４２で、例えば、隠れた表面を除去するため に、プリミティブが閉込められているか否かを任意にテストする。閉込めの質問 は、重畳プリミティブの全または部分不透明性に依存して一層簡単なイエス／ノ ーテストとし、これが既知のｚバッファリングアルゴリズムにおける場合のよう に、これが図８の処理後に発生するも、追加のプリミティブを像に加える際に繰 返しループテストを具える用にすること明らかである。ステップ４２のテストが 閉込めるべきプリミティブがイエスであり、これを具える場合には、プリミティ ブを（ステップ４４で）廃棄し、それ以外はステップ４６に通過する。 ステッ プ４６では、垂直高さ（ｙ_max−ｙ_min）をチェックし、且つ、これが１画素に等 しい（即ち、ｙ_max＝ｙ_min）場合には、プリミティブは変形し、廃棄する。同様 に、ステップ４８で頂部（ｘ_max−ｘ_min）の最左側から最右側まで水平範囲をチ ェックし、再びこれが１画素に等しい場合には、プリミティブは変形し、廃棄さ れる。 ステップ５０では、（１画素よりも低いか、またはこれに等しいプリミティブ が変形しているものとして廃棄された場合と同様に）垂直範囲が２つの画素に等 しいかどうかをチェックする。変形である場合には、ステップ５２によってこれ が（図５に示すように）平坦底部であるかどうかをチェックし、平坦底部である 場合には、これを廃棄する。ステップ５２のチェックが平坦底部でない場合には 、（図３および４に示すように）プリミティブが平坦底部であるかどうかについ てステップ５４でさらにチェックし、平坦底部である場合には、プリミティブを 、画素の頂部左側頂角および長さ（Ｖ_T−Ｖ_M-1）から水平ラインを描く必要があ ると云う識別子とともにステップ５６で描画リストにエンターする。また、ステ ップ５４のチェックがノーである場合には、プリミティブは水平縁部を有さず、 水平スロープの計算を必要としないと云う識別子とともにステップ５８で描画リ ストにエンターする。 ステップ５０がノーである、即ち、垂直範囲が２画素よりも大きい場合には、 水平範囲をステップ６０でチェックするとともにこれが２画素よりも大きい場合 にも、プリミティブは特定のケースの一つを構成しない。従って、画素は特定の 処理を示す識別子がなくてもステップ６２で描画リストにエンターされる。 水平範囲が２画素よりも少ないかまたはこれに等しい場合には、次の２つのス テップ６４、６６によってこれが平坦頂部（図６）であるか、平坦底部（図７） であるかをそれぞれチェックする。チェックのテストがイエスの場合には、前述 したように、単一のスロープおよび長さを計算する必要派内と云う識別子ととも にプリミティブをステップ６８で描画リストにエンターする。プリミティブが平 坦頂部でもなく、平坦底部でもない場合には、特定のケースであるが水平縁部が ないものとして識別された他のプリミティブとともに前記プリミティブをステッ プ５８で描画リストにエンターする。 本発明の利点はこれらの状況で必要とされる処理数を低減することにある。従 って、左程高価でない描画システムを用いて一層現実的な／興味のある３次元モ デルを用いることができ、またはさもなければ可能である場合よりも短い距離で 多くの物体を見ることができる。 本発明は上述した例にのみ限定されるものではなく、要旨を変更しない範囲内 で種々の変形や変更が可能である。

Claims (1)

1. 【特許請求の範囲】 １．複数の多角形像プリミティブで構成される２次元画素像を描画する像処理を 行うに当たり、次のステップ： （ａ）像プリミティブをその完成像内の位置に関して分類するとともにこの プリミティブの順序リストを発生し； （ｂ）１画素の最大水平寸法または最大垂直寸法を有する像プリミティブを 変質として指定するとともにこの変質プリミティブを描画前のリストから除去 し； （ｃ）２画素の最大水平寸法または最大垂直寸法を有する像プリミティブを 特定として指定し、この特定プリミティブをその頂角の配列に従って分類し、 且つこの特定のプリミティブを前記リスト内で識別し； （ｄ）その特定の分類に従って処理される前記ステップ（ｃ）で識別された これら特定のプリミティブで像を描画し、互いのプリミティブに対しそのプリ ミティブによって交差された各走査ラインに対し、像プリミティブにより交差 されたかかる各走査ラインの部分の端部画素および像プリミティブにより交差 された最上側および最下側の画素の所定のものの全ての画素に対するプリミテ ィブ寄与を無視する、ステップを具えることを特徴とする像処理方法。 ２．プリミティブによりカバーされた各走査ラインの部分の右側画素および最低 側画素ラインは、前記ステップ（ｄ）で無視された各プリミティブ寄与を有す ることを特徴とする請求項１に記載の像処理方法。 ３．２つの画素の垂直範囲および幅Ｎ画素の水平上側端部を有するものとして前 記ステップ（ｃ）で分類された特定のプリミティブを、幅Ｎ−１画素の単一画 素ラインとして描画するようにしたことを特徴とする請求項１または２に記載 の像処理方法。 ４．２つの画素の垂直範囲および水平低側端部を有するものとして前記ステップ （ｃ）で分類された特定のプリミティブを無視しないようにしたことを特徴と する請求項１または２に記載の像処理方法。 ５．２画素の最大水平範囲および２画素よりも大きな垂直範囲を有するものとし て前記ステップ（ｃ）で分類された特定のプリミティブを、幅１画素の傾斜ラ インとして描画するようにしたことを特徴とする請求項１または２に記載の像 処理方法。 ６．各像プリミティブは関連する深度値を有するとともに前記ステップ（ａ）は 各深度値に従って像プリミティブを分類することをさらに具えることを特徴と する請求項１〜５の何れかの項に記載の像処理方法。 ７．各像プリミティブは関連する透明値を有するとともに前記ステップ（ａ）は １つ以上の不透明プリミティブにより全体的にカバーされたこれらプリミティ ブを前記リストから除去することをさらに具えることを特徴とする請求項６に 記載の像処理方法。 ８．第１および第２メモリに結合されたデータプロセッサを具え、第１メモリは 処理用像プリミティブデータを保持し、第２メモリは動作プログラムに従って 作動する際、データプロセッサの動作プログラムを保持するようにした像処理 装置において： 前記第２メモリのデータに基づき、像プリミティブをその完成像内の位置に 関して分類するとともにこのプリミティブの順序リストを発生する手段と； １画素の最大水平寸法または最大垂直寸法を有する像プリミティブを変質と して指定するとともにこの変質プリミティブを描画前にリストから除去するよ うに配列された手段と； ２画素の最大水平寸法または最大垂直寸法を有する像プリミティブを特定の ものとして指定し、この特定プリミティブをその頂角の配列に従って分類する ように配列され、且つこの特定のプリミティブを前記リスト内で識別する手段 と； 前記第１メモリのデータから像を描画するように配列され、特定のものとし て識別されたこれらプリミティブはその特定の分類に従って処理され、互いの プリミティブに対しそのプリミティブによって交差された各走査ラインに対し 、像プリミティブにより交差されたかかる各走査ラインの部分の端部画素およ び像プリミティブにより交差された最上側および最下側の画素の所定のものの 全ての画素に対するプリミティブ寄与を無視するように構成された像描画手段 と； を具えることを特徴とする像処理装置。 ９．前記像プロセッサから描画された像を規定するデータを受けるように結合さ れ、規定された像を表示するように配列されたディスプレイ装置をさらに具え ることを特徴とする請求項８に記載の像処理装置。