JPH10320573A - 画像処理装置及び画像処理方法 - Google Patents

Abstract

(57)【要約】 【課題】 コンピュータグラフィックシステムにおい
て、画像要素のデータの処理を効率的、かつ、高速に行
うことを可能にし、従来のものより安価で高品質の画像
を実現することを目的とする。 【解決手段】 画面を予め定められた大きさで分割し、
これら分割された領域（フラッグメント）ごとに処理を
行う画像処理装置において、画像構成要素の情報を走査
線に対し垂直方向に並びかえ（ＳＴ１）、画像構成要素
の情報を走査線に対し水平方向に並びかえ（ＳＴ２）、
並べ替えされた前記画像構成要素の情報に基づき不透明
ポリゴン、透明ピクセル付きポリゴン、半透明付きポリ
ゴンの順に画像処理を行う（ＳＴ３〜ＳＴ６）。

Description

【発明の詳細な説明】

【０００１】

【発明の属する技術分野】この発明は、コンピュータグ
ラフィックス用の画像処理装置及び画像処理方法に関す
る。

【０００２】

【従来の技術】コンピュータグラフィックスの分野にお
いて、高い画像処理能力を実現するために表示画面を寸
法が固定された小さな矩形領域（以下、フラッグメン
ト:Fragmentと呼ぶ）に分割し、このフラッグメントご
とに処理を行う方法が知られていた。

【０００３】この従来の方法について、図１４乃至図１
７を用いて説明する。従来の方法は、まず、（１）ポリ
ゴン毎にフラッグメントの枠によってポリゴンを分割
し、どのフラッグメントに含まれるか分かるように記憶
する。

【０００４】図１４の３×５に配置された１５個のフラ
ッグメントがあり、これらの上にポリゴンＡ，Ｂ，Ｃが
定義されている。ポリゴンＡについて見ると、図１５の
ように８つのフラッグメントが対応する。これらのフラ
ッグメントがその座標α、β、γ、・・・に対応して図
１６のバッファメモリに格納される。図１５のα１、α
２がバッファメモリのαのメモリ領域に格納され、β
１、β２がバッファメモリのβのメモリ領域に格納さ
れ、γ１、γ２がバッファメモリのγのメモリ領域に格
納される。以下、同様である。

【０００５】次に、（２）フラッグメントの内で現在注
目しているポリゴンによって覆われる部分を計算し、塗
りつぶしていく。例えば、図１７に示すように、フラッ
グメントδ１について、まず、ポリゴンＡに関して塗り
つぶし（図１７（ｂ））、次にポリゴンＢに関して塗り
つぶし（同（ｃ））、最後にポリゴンＣに関して塗りつ
ぶす（同（ｄ））。この作業を最後のポリゴンが処理さ
れるまで、またはフラッグメントが完全に覆われるまで
繰り返す。これをすべてのフラッグメントについて処理
する。

【０００６】従来の画像要素のデータ処理は上記（１）
（２）の手順により行われていた。

【０００７】

【発明が解決しようとする課題】しかし、このような方
法では対象となるフラッグメントごとにすべてのポリゴ
ンを分割しなければならず、このために莫大な量の計算
が必要となり、大きな処理時間が必要となっていた。

【０００８】また、分割されて生成されたポリゴンの情
報を記憶するために大容量の記憶装置を持たなくてはな
らなくなってしまう。処理を高速化するためには記憶装
置を高速なものにしなければならず、コストが高くなっ
てしまう、というような欠点を生じていた。

【０００９】また、従来は、ポリゴンがテクスチャデー
タを持っている場合には、半透明付きポリゴンの処理は
できなかった。

【００１０】この発明は上記の課題を解決するためにな
されたもので、コンピュータグラフィックシステムにお
いて、画像要素のデータの処理を効率的、かつ、高速に
行うことを可能にし、従来のものより安価で高品質の画
像を実現することを目的とする。この実現方法として、
画面を小さな領域（フラッグメント）に分割して行う方
法がある。その際に、注目している領域に含まれるポリ
ゴンを効率良く検索することを目的とする。要するに、
コンピュータグラフィックスシステムにおいて、従来の
システムより安価で高品質な画像を実現する装置及び方
法を提供する。

【００１１】

【課題を解決するための手段】この発明に係る画像処理
装置は、画面を予め定められた大きさで分割し、これら
分割された領域ごとに処理を行う画像処理装置におい
て、画像構成要素の情報を走査線に対し垂直方向に並び
かえる第１並び替え手段と、画像構成要素の情報を走査
線に対し水平方向に並びかえる第２並び替え手段と、並
べ替えされた前記画像構成要素の情報に基づき画像処理
を行う画像処理部とを備えるものである。

【００１２】この発明に係る画像処理装置は、前記第１
並び替え手段は、前記垂直方向に関する前記画像構成要
素の最小又は最大の値に基づき並び替えを行うととも
に、前記第２並び替え手段は、前記第１並び替え手段の
処理対象となっている領域の垂直座標において、前記水
平方向に関する前記画像構成要素の最小又は最大の値に
基づき並び替えを行うものである。

【００１３】最小値で並べ替えをおこなっても、最大値
で並べ替えをおこなってもどちらでもよい。並べ替えを
行うキーが最大値であっても、処理の順序の向きが変わ
る（左から右→右から左／上から下→下から上）だけで
同様の処理が可能である。なお、垂直→水平の順序で
も、あるいは水平→垂直の順序でも、どちらでも同様の
処理が可能である。

【００１４】この発明に係る画像処理装置は、前記第１
並び替え手段及び第２並び替え手段は、並びかえられた
前記画像構成要素の情報の間を互いに結び付けるリンク
処理を行うものである。

【００１５】この発明に係る画像処理装置は、前記第１
並び替え手段及び第２並び替え手段は、前記画像構成要
素に対応する領域のうちで、不要な部分を無効にするリ
ンク更新処理を行うものである。

【００１６】この発明に係る画像処理装置は、前記画像
処理部は、前記分割された領域ごとの画像処理を、処理
すべき対象を不透明ポリゴン、透明ピクセル付きポリゴ
ン、及び半透明付きポリゴンに区分するとともに、前記
不透明ポリゴン、前記透明ピクセル付きポリゴン、前記
半透明付きポリゴンの順に処理をするものである。

【００１７】この発明に係る画像処理方法は、画面を予
め定められた大きさで分割し、これら分割された領域ご
とに処理を行う画像処理方法において、画像構成要素の
情報を走査線に対し垂直方向に並びかえる第１並び替え
ステップと、画像構成要素の情報を走査線に対し水平方
向に並びかえる第２並び替えステップと、並べ替えされ
た前記画像構成要素の情報に基づき画像処理を行う画像
処理ステップとを備えるものである。

【００１８】この発明に係る画像処理方法は、前記第１
並び替えステップで、前記垂直方向に関する前記画像構
成要素の最小の値に基づき並び替えを行うとともに、前
記第２並び替えステップで、前記第１並び替えステップ
の処理対象となっている領域の垂直座標において、前記
水平方向に関する前記画像構成要素の最小の値に基づき
並び替えを行うものである。

【００１９】この発明に係る画像処理方法は、前記第１
並び替えステップ及び第２並び替えステップで、並びか
えられた前記画像構成要素の情報の間を互いに結び付け
るリンク処理を行うものである。

【００２０】この発明に係る画像処理方法は、前記第１
並び替えステップ及び第２並び替えステップで、前記画
像構成要素に対応する領域のうちで、不要な部分を無効
にするリンク更新処理を行うものである。

【００２１】この発明に係る画像処理方法は、前記画像
処理ステップで、前記分割された領域ごとの画像処理
を、処理すべき対象を不透明ポリゴン、透明ピクセル付
きポリゴン、及び半透明付きポリゴンに区分するととも
に、前記不透明ポリゴン、前記透明ピクセル付きポリゴ
ン、前記半透明付きポリゴンの順に処理をするものであ
る。

【００２２】

【発明の実施の形態】

発明の実施の形態１．以下、この発明の実施の形態１の
装置及び方法について説明する。

【００２３】図１はこの発明の実施の形態１に係る画像
処理装置の概略機能ブロック図である。この図におい
て、１はＣＰＵ(central processing unit)であり、仮
想空間中の物体に対して操作を行ったり、その情報を得
たり、各種制御を行う。２はジオメトリプロセッサ（ge
ometry processor）であり、３次元コンピュータグラフ
ィックにおけるポリゴンの座標変換、クリッピング、透
視変換などの幾何変換（ベクトル演算）や輝度計算を高
速に行う。２ａはポリゴン／マテリアル／ライトバッフ
ァメモリ（polygon／material／light buffer RAM）で
あり、ジオメトリプロセッサ２が処理を行う際に、１フ
レーム分の有効なポリゴンデータ、マテリアルデータ、
ライトデータを保存するバッファである。ポリゴンと
は、仮想空間中の立体を構成する多面体のことである。
このバッファメモリ２ａに格納されるデータの内訳を示
すと次のようになる。

【００２４】ポリゴンのリンク情報、座標情報、その他
の属性情報 LINK X, LINK Y, X, Y, iz, Tx, Ty, Nx, Ny, Sign Nz,
Alpha, Light ID, Material ID・・・などである。

【００２５】マテリアルの情報 Depth enable, Depth function, Depth density, Textu
re enable, Fog enable,translucensy enable, texture
type, texture function, offset x,y, size x,y, rep
eat x,y, mirror x,y, color id, Shinines, Material
specular, Material emission, Polygon color, Textur
e mode, blend modeなどである。

【００２６】ライトの情報 Light Position, Light Direction, Light Type, Atten
uation, Cutoff, Spotexp,Light Color, Light Ambient
などである。

【００２７】３は陰面消去処理を行うフィルプロセッサ
（fill processor）である。フィルプロセッサ３は、領
域中でポリゴンの塗りつぶしを行い、各ピクセル毎に最
も手前にくるポリゴンの各情報を求める。

【００２８】４はテクスチャプロセッサ（texture proc
essor）である。テクスチャプロセッサ４は、領域内の
各ピクセルにテクスチャを貼り付ける。テクスチャマッ
ピングとは、形状が定義された物体の表面に、形状とは
別に定義された模様（テクスチャ）を貼り付け（マッピ
ング）て画像を作成する処理である。４ａはテクスチャ
メモリ（texture RAM）であり、テクスチャプロセッサ
４で処理を行うためのテクスチャマップが保存されてい
る。

【００２９】５はシェーディングプロセッサ（shading
processor）である。シェーディングとは、ポリゴンで
構成される物体の影のような表現を、ポリゴンの法線ベ
クトル、光源の位置や色、視点の位置、視線の方向等を
考慮して行う手法である。シェーディングプロセッサ５
は、領域内の各ピクセルの輝度を求める。５ａは１画面
の画像データが記憶されるフレームバッファ（frame bu
ffer）である。フレームバッファ５ａから順次データが
読み出され、デジタルデータからアナログ信号に変換さ
れた後に、図示しないＣＲＴ、液晶表示装置、プラズマ
ディスプレイ装置等のディスプレイに供給される。

【００３０】６は、ＣＰＵ１のプログラムやグラフィッ
クプロセッサへのコマンド（ポリゴンのデータベース、
ディスプレイリストなど）を保存するプログラムワーク
／ポリゴンバッファメモリ（program work／polygon bu
ffer RAM）である。このバッファメモリ６はＣＰＵ１の
ワークメモリでもある。

【００３１】フィルプロセッサ３、テクスチャプロセッ
サ４、シェーディングプロセッサ５は、いわゆるレンダ
リングを行う。レンダリングでは、各領域は画面左上か
ら順に処理される。実際には、ジオメタリが仮想空間座
標中にオブジェクトを配置しスクリーン上に透視変換す
る。レンダリングはそのスクリーン座標上に定義された
データをもとに絵を作成する。レンダリングの処理は領
域の個数分繰り返される。

【００３２】次にこの発明の実施の形態１に係る画像処
理装置の詳細について、図２乃至図５の機能ブロック図
に基づき説明する。

【００３３】図２はジオメトリプロセッサ２の機能ブロ
ック図である。この図において、２１はデータディスパ
ッチャー（data dispatcher）であり、バッファメモリ
６からコマンドを読み出すとともに解析し、この解析結
果に基づきベクタエンジン２２、クリッピングエンジン
２４をコントロールし、処理されたデータをソートエン
ジン２７へ出力する。

【００３４】２２はベクタエンジン（vector engine）
であり、ベクトル演算を行う。扱うベクトルはベクタレ
ジスタ２３に保存される。

【００３５】２３はベクタレジスタ（vector registe
r）であり、ベクタエンジン２２で演算を行うベクトル
データを保存する。

【００３６】２４はクリッピングエンジン（clipping e
ngine）であり、クリッピングを行う。

【００３７】２５はＹソートインデックス（Y-sort IND
EX）であり、ソートエンジン２７でＹソーティングを行
うときに使うＹ指標を保存する。

【００３８】２６はＸソートインデックス（X-sort IND
EX）であり、ソートエンジン２７でＸソーティングを行
うときに使うＸ指標を保存する。

【００３９】２７はソートエンジン（sort engine）で
あり、Ｘソーティング及びＹソーティングを行うことに
より、注目しているフラグメントに入るポリゴンをバッ
ファ６から検索する。検索されたポリゴンはバッファメ
モリ２ａに格納されるとともに、フィルプロセッサ３に
送られレンダリングがなされる。また、ソートエンジン
２７はポリゴンＴＡＧ２８及びポリゴンキャッシュ３４
の制御も行う。

【００４０】２８はポリゴンＴＡＧ（polygon TAG）で
あり、ポリゴンキャッシュ３４のＴＡＧを保存するバッ
ファである。

【００４１】図３はフィルプロセッサ３の機能ブロック
図である。この図において、３１はキャッシュコントロ
ーラ（cache controller）であり、後述のマテリアルキ
ャッシュ４２、４５、５１ｂ、５２ａ、５３ａ及びライ
トキャッシュ５１ａを制御する。

【００４２】３２はマテリアルＴＡＧ（material TAG）
であり、後述のマテリアルキャッシュ４２、４５、５１
ｂ、５２ａ、５３ａ及びライトキャッシュ５１ａのＴＡ
Ｇを保存する。

【００４３】３３はライトＴＡＧ（light TAG）であ
り、後述のライトキャッシュ５１ａのＴＡＧを保存する
バッファである。

【００４４】３４はポリゴンキャッシュ（polygon cach
e）であり、ポリゴンデータのキャッシュメモリであ
る。

【００４５】３５は初期パラメータ計算機（initial pa
rameter calculator）であり、ＤＤＡの初期値を求め
る。

【００４６】３６はＺコンパレータアレー（Z comparat
or array）であり、陰面消去処理のためにポリゴン間で
Ｚ比較を行うとともに、ポリゴンＩＤ及び内分比ｔ０、
ｔ１、ｔ２を埋め込む。Ｚコンパレータアレー３６は８
×８＝６４個のＺ比較器から構成される。これらがパラ
レルに動作するので、同時に６４個のピクセルについて
処理が可能である。１つのＺ比較器にはポリゴンに関す
るデータが保存される。例えば、polygon ID, iz, t0,
t1, t2, window, stencil, shadowなどである。

【００４７】３７は頂点パラメータバッファ（vertex p
arameter buffer）であり、ポリゴンの頂点でのパラメ
ータを保存するバッファである。Ｚコンパレータアレー
３６に対応して６４ポリゴン分の大きさをもつ。

【００４８】３８は補間器（interpolater）であり、Ｚ
コンパレータアレー３６の計算結果ｔ０、ｔ１、ｔ２及
びｉｚと頂点パラメータバッファ３７の内容により、ピ
クセルのパラメータを補間して算出する。

【００４９】図４はテクスチャプロセッサ４の機能ブロ
ック図である。この図において、４１は濃度計算機（de
nsity calculator）であり、フォグまたはデプスキュー
イングのためのブレンド比を算出する。

【００５０】４２はマテリアルキャッシュ（material c
ache）であり、深さ情報に関するデータが保存される。

【００５１】４３はウインドウレジスタ（window regis
ter）であり、ウインドウに関する情報を保存するバッ
ファである。例えば、 kz, cz, fog function, fog density, fog end z ４４はアドレス発生器（address generator）であり、
テクスチャ座標Ｔｘ，Ｔｙ及びＬＯＤよりテクスチャマ
ップ上でのアドレスを算出する。

【００５２】４５はマテリアルキャッシュ（material c
ache）であり、材質に関するデータが保存される。

【００５３】４６は３次元補間であるトライリニアミッ
プマップ補間を行うＴＬＭＭＩ計算機（TLMMI calculat
or, TLMMI:Tri Linear MIP Map Interpolation）であ
る。ミップマップとは、テクスチャマッピングを行うと
きのアンチエイリアシング、すなわちテクスチャのジャ
ギ（ぎざぎざ）をなくすための技法である。これは次の
ような原理によるものである。本来、１画素に投影され
る物体面の色（輝度）は、対応するマッピング領域の色
の平均値としなければならない。そうしないとジャギが
目立ってしまい、テクスチャの質が極端に落ちる。一
方、いちいち平均を求める処理を行うと計算負荷が過大
となり、処理に時間がかかったり、高速プロセッサが必
要になったりする。ミップマップはこれを解決するため
のものである。ミップマップでは、１画素に対応するマ
ッピング領域の色（輝度）の集計を簡素化するために、
あらかじめ２の倍数幅のマッピングデータを複数用意す
る。１画素に対応したすべてのマッピング領域の大きさ
は、これら２の倍数倍のいずれか２つのデータの間に存
在することになる。これら２つのデータを比較すること
により対応するマッピング領域の色を求める。例えば、
１倍の画面Ａと１／２倍の画面Ｂとがあったとき、１／
１．５倍の画面Ｃの各画素と対応する画面Ａ及びＢの画
素をそれぞれ求める。このとき、画面Ｃの当該画素の色
は、画面Ａの画素と画面Ｂの画素の中間の色になる。

【００５４】４７はカラーコンバータ（color converte
r）であり、４ｂｉｔテクセル時にカラー変換を行う。

【００５５】４８はカラーパレット（color pallet）で
あり、４ｂｉｔテクセル時のカラー情報が保存される。
カラーパレット４８は、グラフィックを書くときに使う
色を格納する。カラーパレット４８の内容に対応して１
つの画素に使える色が決まる。

【００５６】図５はシェーディングプロセッサ５の機能
ブロック図である。この図において、 ５１は輝度処理
器（intensity processor）であり、テクスチャマッピ
ングされた後のポリゴンに対して輝度計算を行う。

【００５７】５１ａはライトキャッシュ（light cach
e）であり、ライト情報を格納する。

【００５８】５１ｂはマテリアルキャッシュ（material
cache）であり、材質に関する情報を格納する。Shinie
s, Material specular, material emissionなどであ
る。

【００５９】５１ｃはウインドウレジスタ（window reg
ister）であり、ウインドウに関する情報を保存する。S
creen center, Focus, Scene ambientなどである。

【００６０】５２はモジュレート処理器（modulate pro
cessor）であり、ポリゴンカラーとテクスチャカラーの
関連づけ、輝度変調、フォグ処理を行う。

【００６１】５２ａはマテリアルキャッシュ（material
cache）であり、材質に関する情報を格納する。例え
ば、Polygon color, Texture modeなどである。

【００６２】５２ｂはウインドウレジスタ（window reg
ister）であり、ウインドウに関する情報を保存するバ
ッファである。Fog colorなどである。

【００６３】５３はブレンド処理器（blend processo
r）であり、カラーバッファ５４上のデータとブレンド
を行い、カラーバッファ５４に書き込む。ブレンド処理
器５３は、プレンドレートレジスタの値に基づき、カレ
ントピクセルカラーとフレームバッファのピクセルカラ
ーとをブレンドし、ライトバンクレジスタで示されるバ
ンクのフレームバッファに書き込む。

【００６４】５３ａはマテリアルキャッシュ（material
cache）であり、材質に関する情報を格納する。blend
modeなどである。

【００６５】５４はカラーバッファ（color buffer）で
あり、フラグメントのサイズと同じ８×８の大きさのカ
ラーバッファである。ダブルバンク構造になっている。

【００６６】５５はプロット処理器（plot processor）
であり、カラーバッファ５４上のデータをフレームバッ
ファ５ａに書き込む。

【００６７】５６はビットマップ処理器（bitmap proce
ssor）であり、ビットマップ処理を行う。

【００６８】５７はディスプレイ制御器（display cont
roller）であり、フレームバッファ５ａのデータを読み
出して、ＤＡＣ（Digital to Analogue Converter：デ
ジタル−アナログ変換器）に供給し、図示しないディス
プレイに表示する。

【００６９】ところで、本発明の実施の形態１では、ポ
リゴンをフラッグメントごとに分割することをせずに、
代わりに走査線に対し垂直方向（以下、Ｙ方向）及び水
平方向（以下、Ｘ方向）にポリゴンを並べかえる処理を
することで、フラッグメントごとに含まれるポリゴンを
検索できるようする。そして、この情報を使用して現在
注目しているフラッグメントごとにポリゴンを処理する
ことで、ポリゴンを分割する処理を行わないでも処理す
ることが可能になる。よって、処理時間を短縮し、か
つ、記憶装置の容量が小さい装置で処理を実現すること
が可能になる。

【００７０】また、レンダリングにおいては、ポリゴン
を不透明ポリゴン、半透明付きポリゴン及び透明ピクセ
ル付きポリゴンに分け、かつ、半透明付きポリゴンを最
後に処理することで半透明付きポリゴンの処理を可能に
した。

【００７１】本発明の実施の形態１の全体の処理フロー
を図６に示す。

【００７２】レンダリング部に送るポリゴンデータをポ
リゴンの最小Ｙ座標値で並び替えバッファに書き込む
（ＳＴ１）。

【００７３】現在注目しているフラッグメントのＹ座標
値と一致するポリゴンデータをポリゴンの注目Ｙ領域の
最小Ｘ座標値で並び替える（ＳＴ２）。

【００７４】現在注目しているフラッグメントのＸＹ座
標と一致するすべての不透明ポリゴンをレンダリングす
る（ＳＴ３）。

【００７５】現在注目しているフラッグメントのＸＹ座
標と一致するすべての透明ピクセル付きポリゴンをレン
ダリングする（ＳＴ４）。

【００７６】バッファ内のデータに従ってテクスチャを
貼り付け、シェーディングを行いカラーデータに変換す
る（ＳＴ５）。

【００７７】なお、ＳＴ４とＳＴ５の順番は逆でもよ
い。むしろＳＴ５、ＳＴ４の順序の方がより現実的とい
える。

【００７８】現在注目しているフラッグメントのＸＹ座
標と一致する半透明付きポリゴンをＺ座標値順にレンダ
リングする（ＳＴ６）。

【００７９】バッファ内のカラーデータをフレームバッ
ファに書き出す（ＳＴ７）。

【００８０】図６のように、ポリゴンデータはまずＹで
並び変えられ、次にこの並び変えられたデータは、今度
は各行の処理の前に注目領域ＹのＸの最小値で並びかえ
られる。この結果によって、ポリゴンの最初に処理され
るフラッグメントの位置が判る。これによって、ポリゴ
ンが最初にどのフラッグメントに含まれるか判る。ま
た、各ポリゴンは最初に含まれるフラッグメントでの処
理終了後にリンク更新処理（後述）が行われ、次のフラ
ッグメント以降で不要なポリゴンはリンクから外され、
必要なポリゴンは次のフラッグメントに含まれるポリゴ
ンの情報にも含まれるようになる。したがって、それま
でのリンクをすべてたどればフラッグメントの内に入る
すべてのポリゴンを検索することができる。各フラッグ
メントごとにポリゴンを分割して新しくポリゴンを作成
し、処理することを行わなくてもフラッグメントごとに
含まれるポリゴンの情報を読み出すことができ、処理を
行えるようになる。

【００８１】また、リンク更新処理とは、現在注目して
いるフラッグメントでポリゴン処理終了後、そのポリゴ
ンが次のフラッグメント以降で無効になるかどうか調
べ、無効になる場合はポリゴンをリンクから外す処理で
ある。

【００８２】レンダリングの処理部について、以下に説
明する。

【００８３】（１）まず、ポリゴンを不透明ポリゴン、
透明ピクセル付きポリゴン、及び半透明付きポリゴンに
分ける。

【００８４】（２）次に、不透明ポリゴンの処理を行
う。これはテクスチャデータによらず重ね書きされ、最
終的に残ったピクセルのみが有効となる。そこで、Ｚ比
較のみを高速で行う。

【００８５】（３）上記（１）（２）を終了すると、フ
ラッグメントバッファ内のデータはすべて有効なデータ
となる。そこで、この時点でフラッグメントバッファ内
のデータを元にテクスチャデータを読み出し、色データ
の変換を行う。

【００８６】（４）次に、透明ピクセル付きポリゴンを
レンダリングする。これは、そのテクセルが透明か否か
によってそのピクセルを描くか否かを決定する必要があ
る。従って、レンダリング時に透明テクセルの情報を読
みながら塗りつぶしを行う。これ以外は不透明ポリゴン
の処理と同じである。なお、この（３）（４）の順序の
方が、逆の順序よりも好ましい。レンダリング時に透明
テクセルの情報を読むことが難しいからである。

【００８７】（５）次に、半透明付きポリゴンの処理を
行うが、この場合、Ｚ値比較をパスしたすべてのピクセ
ルのデータが有効となる。したがって、ピクセル毎にテ
クスチャデータを読み出し、色データへ変換しながら塗
りつぶし（ブレンディング）を行う。また、ブレンディ
ングではポリゴンを描く順番が問題となるので、何等か
の手法によりＺでソートしておく。

【００８８】次に、図７〜図１３を用いてこの発明の実
施の形態１のフラッグメント ＣＧシステムについて更
に詳細に説明する。

【００８９】まず、Ｙ方向の並び替えの動きを説明す
る。図７はＹインデックスバッファ（Ｙ ＩＮＤＥＸ
ｂｕｆｆｅｒ）とＹソートバッファ（Ｙ ｓｏｒｔ ｂ
ｕｆｆｅｒ）の構造を示す。Ｙインデックスバッファに
は、各フラッグメント行にＹ座標値の最小値Ｙｍｉｎが
入るポリゴンリストのリンクの先頭アドレスが格納され
る。Ｙソートバッファには入力された順にポリゴンデー
タが格納される。Ｙソートバッファ内のＬＩＮＫ Ｙパ
ラメータは、同じ行に入る次のポリゴンのアドレスが格
納される。

【００９０】従って、指定された行に入るポリゴンを知
りたければ、対応するＹ ＩＮＤＥＸのアドレスからＬ
ＩＮＫ ＹがＥＮＤであるポリゴンまでリンクをたどっ
ていけばよい。

【００９１】図７の例について説明する。最も上のフラ
ッグメント行についてＹインデックスバッファのアドレ
ス０を見るとこの内容は「ＥＭＰＴＹ」であり、ポリゴ
ンがないことがわかる。２番目の行についても同様であ
る。３番目の行についてＹインデックスバッファのアド
レス２を見るとこれらの内容は「ＡＤＲ８」「ＥＭＰＴ
Ｙ」である。そこで、ＹソートバッファのＡＤＲ８をア
クセスすると、そのＬＩＮＫ Ｙの内容は「ＡＤＲ５」
である。そこで次はＡＤＲ５をアクセスする。以下同様
に、順番にＡＤＲ３、ＡＤＲ１とアクセスされる。そし
て、ＡＤＲ１のＬＩＮＫ Ｙの内容が「ＥＮＤ」である
ので、これでリンクは終わる。以下、すべてのフラッグ
メント行について処理が行われる。

【００９２】次に、ポリゴンデータを格納するときの動
きを説明する。

【００９３】図７の状態の時にＹｍｉｎがＹ ＩＮＤＥ
Ｘ＝５となるポリゴンデータが入力されたとする。Ｙイ
ンデックスバッファの第５番目の内容は「ＥＭＰＴＹ」
であるのでポリゴンデータのＬＩＮＫ Ｙは「ＥＮＤ」
とする。このポリゴンデータはＹソートバッファのＡＤ
Ｒ１０に格納されるとともに、Ｙインデックスバッファ
の第５番目には、今書き込んだポリゴンデータのアドレ
スである「ＡＤＲ１０」が書き込まれる。この状態を図
８に示す。

【００９４】次に、図８の状態の時にＹｍｉｎがＹ Ｉ
ＮＤＥＸ＝２となるポリゴンデータが入力された時の動
作について考える。Ｙインデックスバッファの第２番目
にはすでにポリゴンデータへのアドレスが入っている
（図８では「ＡＤＲ８」）ので、そのデータは今から書
き込むポリゴンの後ろにつけるようにする。したがっ
て、ポリゴンデータのＬＩＮＫ Ｙは元のＹ ＩＮＤＥ
Ｘの値である「ＡＤＲ８」とするとともに、Ｙインデッ
クスバッファの第２番目には、今書き込んだポリゴンデ
ータのアドレスである「ＡＤＲ１１」が書き込まれる。
この状態を図９に示す。

【００９５】図１０は、Ｘ方向についての並び替えを説
明するための図である。Ｘ方向の並び替えの処理もＹ方
向の場合と同様であり、その行におけるＸｍｉｎを求
め、その値を用いて並び替えを行う。

【００９６】以上のように、Ｘ方向の並び替え、及び、
Ｙ方向の並び替えを行うとポリゴンが最初に有効になる
フラッグメント、すなわち注目しているフラッグメント
が最初に有効になるポリゴンが判る。例えば、図１１に
示すように、各ポリゴンにおいてＹ座標値が最も小さい
もののうちでＸ座標値が最も小さなフラッグメントが選
択される。

【００９７】なお、並び替えた結果を参照するときは、
０〜注目行（列）をすべて有効とみなすので、あるポリ
ゴンに注目するとそのポリゴンが有効である範囲は図１
２のようになる。これでは不要な部分までポリゴンが有
効になってしまうので、以下で説明するようにリンク更
新を行う。

【００９８】まず、ポリゴン処理終了後、次のフラッグ
メント以降で無効になるポリゴンをリンクから外す。図
１３（ａ）の例では、Ｆ１〜Ｆ７について、レンダリン
グ後にＸ ＬＩＮＫから削除する。また、Ｆ７について
は、レンダリング後Ｙ ＬＩＮＫからも削除する。リン
ク更新を行った場合のポリゴン有効範囲を図１１（ｂ）
に示す。

【００９９】以下、図１３をもとにＸ方向のリンクにつ
いてのステップを記す。

【０１００】（１）ポリゴンのエッジとフラッグメント
のＸ方向に対して水平の境界の交点のうち、Ｘ座標値の
大きい方の点（Ｐ２）を調べる。

【０１０１】（２）（１）で調べた点のＸ座標値と現在
注目している行のフラッグメントのＸ座標に対し垂直の
境界のうち、Ｘ座標値の大きい方の境界（境界１〜３）
のＸ座標値とを比較する。

【０１０２】（３）小さい場合（境界１、２）にはリン
クし、次のフラッグメントでも有効とする。

【０１０３】（４）大きくなった場合には、レンダリン
グ後リンクから外し、次のフラッグメントからは無効に
する（境界３）。

【０１０４】Ｙ方向のリンクについてもＹ方向に対して
同様の手順で行われる。

【０１０５】以上のように、この発明の実施の形態１で
は、ポリゴンをフラッグメントごとに分割することをせ
ずに、代わりに走査線に対し垂直方向及び水平方向にポ
リゴンを並べかえる処理をすることで、フラッグメント
ごとに含まれるポリゴンを検索できるようになった。こ
の情報を使用し現在注目しているフラッグメントごとに
ポリゴンを分割し、新しいポリゴンを作成しなくても、
各フラッグメントごとに含まれるポリゴンを読み出し処
理することを行うことが可能になった。これにより、従
来の技術のように対象となるフラッグメントごとにすべ
てのポリゴンを分割するために必要な膨大な量の計算が
必要でなくなり、かつ、分割されて生成されたポリゴン
の情報を記憶するために必要となっていた大容量の記憶
装置を持つ必要もなくなる。この結果として処理時間を
短縮し、かつ、記憶装置の容量が小さくてもよい装置を
実現することが可能になった。つまり、安価で高性能な
装置が実現できる。

【０１０６】また、ポリゴンの半透明の処理がポリゴン
を不透明ポリゴン、半透明付きポリゴン及び透明付きポ
リゴンに分け、かつ、半透明付きポリゴンを最後に処理
することで可能となった。

【０１０７】

【発明の効果】以上のように、この発明によれば、画面
を予め定められた大きさで分割し、これら分割された領
域ごとに処理を行う画像処理装置において、画像構成要
素の情報を走査線に対し垂直方向に並びかえるととも
に、画像構成要素の情報を走査線に対し水平方向に並び
かえ、並べ替えされた前記画像構成要素の情報に基づき
画像処理を行うので、領域ごとに含まれるポリゴンを検
索することができる。そして、この情報を使用し現在注
目している領域ごとにポリゴンを分割することにより、
新しいポリゴンを作成しなくても、各領域ごとに含まれ
るポリゴンを読み出して処理することが可能になった。
従って、処理時間を短縮するとともに、記憶装置の容量
を小さくできる。

【０１０８】また、この発明によれば、前記分割された
領域ごとの画像処理を、処理すべき対象を不透明ポリゴ
ン、透明ピクセル付きポリゴン、及び半透明付きポリゴ
ンに区分するとともに、前記不透明ポリゴン、前記透明
ピクセル付きポリゴン、前記半透明付きポリゴンの順に
処理するので、ポリゴンがテクスチャデータを持ってい
るときでも、半透明付きポリゴンの処理ができる。

【図面の簡単な説明】

【図１】この発明の実施の形態１に係る画像処理装置の
概略機能ブロック図である。

【図２】この発明の実施の形態１に係る画像処理装置の
ジオメトリプロセッサの機能ブロック図である。

【図３】この発明の実施の形態１に係る画像処理装置の
フィルプロセッサの機能ブロック図である。

【図４】この発明の実施の形態１に係る画像処理装置の
テクスチャプロセッサの機能ブロック図である。

【図５】この発明の実施の形態１に係る画像処理装置の
シェーディングプロセッサの機能ブロック図である。

【図６】この発明の実施の形態１の全体の処理を示すフ
ローチャートである。

【図７】この発明の実施の形態１のＹインデックスバッ
ファとＹソートバッファに関する処理の説明図である。

【図８】この発明の実施の形態１のＹインデックスバッ
ファとＹソートバッファに関する処理の説明図である。

【図９】この発明の実施の形態１のＹインデックスバッ
ファとＹソートバッファに関する処理の説明図である。

【図１０】この発明の実施の形態１のＹインデックスバ
ッファとＹソートバッファに関する処理の説明図であ
る。

【図１１】この発明の実施の形態１の各ポリゴンで最初
に有効になるフラッグメントの例を示す図である。

【図１２】この発明の実施の形態１のリンク更新処理の
説明図である。

【図１３】この発明の実施の形態１のリンク更新処理の
説明図である。

【図１４】従来の処理を説明するための、フラッグメン
トとポリゴンＡ，Ｂ，Ｃの関係を示す図である。

【図１５】従来の処理を説明するための、ポリゴンＡに
対応するフラッグメントを示す図である。

【図１６】従来の処理を説明するための、バッファメモ
リの内容を示す図である。

【図１７】従来の処理の塗りつぶし処理の説明図であ
る。

【符号の説明】

１ ＣＰＵ ２ ジオメトリプロセッサ ２ａ ポリゴン・マテリアル・ライトバッファメモリ ３ フィルプロセッサ ４ テクスチャプロセッサ ４ａ テクスチャメモリ ５ シェーディングプロセッサ ５ａ フレームバッファ ６ プログラム・ワークポリゴンバッファメモリ ２１ データディスパッチャー ２２ ベクタエンジン ２３ ベクタレジスタ ２４ クリッピングエンジン ２５ Ｙソートインデックス ２６ Ｘソートインデックス ２７ ソートエンジン ２８ ポリゴンＴＡＧ ３１ キャッシュコントローラ ３２ マテリアルＴＡＧ ３３ ライトＴＡＧ ３４ ポリゴンキャッシュ ３５ 初期パラメータ計算機 ３６ Ｚコンパレータアレー ３７ 頂点パラメータバッファ ３８ 補間器 ４１ 濃度計算機 ４２ マテリアルキャッシュ ４３ ウインドウレジスタ ４４ アドレス発生器 ４５ マテリアルキャッシュ ４６ ＴＬＭＭＩ計算機 ４７ カラーコンパレータ ４８ カラーパレット ５１ 輝度処理器 ５１ａ ライトキャッシュ ５１ｂ マテリアルキャッシュ ５１ｃ ウインドウレジスタ ５２ モジュレート処理器 ５２ａ マテリアルキャッシュ ５２ｂ ウインドウレジスタ ５３ ブレンド処理器 ５３ａ マテリアルキャッシュ ５４ カラーバッファ ５５ プロット処理器 ５６ ビットマップ処理器 ５７ ディスプレイ制御器

Claims (10)

【特許請求の範囲】
1. 【請求項１】 画面を予め定められた大きさで分割し、
   これら分割された領域ごとに処理を行う画像処理装置に
   おいて、画像構成要素の情報を走査線に対し垂直方向に
   並びかえる第１並び替え手段と、画像構成要素の情報を
   走査線に対し水平方向に並びかえる第２並び替え手段
   と、並べ替えされた前記画像構成要素の情報に基づき画
   像処理を行う画像処理部とを備えることを特徴とする画
   像処理装置。
2. 【請求項２】 前記第１並び替え手段は、前記垂直方向
   に関する前記画像構成要素の最小又は最大の値に基づき
   並び替えを行うとともに、前記第２並び替え手段は、前
   記第１並び替え手段の処理対象となっている領域の垂直
   座標において、前記水平方向に関する前記画像構成要素
   の最小又は最大の値に基づき並び替えを行うことを特徴
   とする請求項１記載の画像処理装置。
3. 【請求項３】 前記第１並び替え手段及び第２並び替え
   手段は、並びかえられた前記画像構成要素の情報の間を
   互いに結び付けるリンク処理を行うことを特徴とする請
   求項２記載の画像処理装置。
4. 【請求項４】 前記第１並び替え手段及び第２並び替え
   手段は、前記画像構成要素に対応する領域のうちで、不
   要な部分を無効にするリンク更新処理を行うことを特徴
   とする請求項３記載の画像処理装置。
5. 【請求項５】 前記画像処理部は、前記分割された領域
   ごとの画像処理を、処理すべき対象を不透明ポリゴン、
   透明ピクセル付きポリゴン、及び半透明付きポリゴンに
   区分するとともに、前記不透明ポリゴン、前記透明ピク
   セル付きポリゴン、前記半透明付きポリゴンの順に処理
   をすることを特徴とする請求項１乃至請求項４いずれか
   に記載の画像処理装置。
6. 【請求項６】 画面を予め定められた大きさで分割し、
   これら分割された領域ごとに処理を行う画像処理方法に
   おいて、画像構成要素の情報を走査線に対し垂直方向に
   並びかえる第１並び替えステップと、画像構成要素の情
   報を走査線に対し水平方向に並びかえる第２並び替えス
   テップと、並べ替えされた前記画像構成要素の情報に基
   づき画像処理を行う画像処理ステップとを備えることを
   特徴とする画像処理方法。
7. 【請求項７】 前記第１並び替えステップで、前記垂直
   方向に関する前記画像構成要素の最小の値に基づき並び
   替えを行うとともに、前記第２並び替えステップで、前
   記第１並び替えステップの処理対象となっている領域の
   垂直座標において、前記水平方向に関する前記画像構成
   要素の最小の値に基づき並び替えを行うことを特徴とす
   る請求項６記載の画像処理方法。
8. 【請求項８】 前記第１並び替えステップ及び第２並び
   替えステップで、並びかえられた前記画像構成要素の情
   報の間を互いに結び付けるリンク処理を行うことを特徴
   とする請求項７記載の画像処理方法。
9. 【請求項９】 前記第１並び替えステップ及び第２並び
   替えステップで、前記画像構成要素に対応する領域のう
   ちで、不要な部分を無効にするリンク更新処理を行うこ
   とを特徴とする請求項３記載の画像処理方法。
10. 【請求項１０】 前記画像処理ステップで、前記分割さ
    れた領域ごとの画像処理を、処理すべき対象を不透明ポ
    リゴン、透明ピクセル付きポリゴン、及び半透明付きポ
    リゴンに区分するとともに、前記不透明ポリゴン、前記
    透明ピクセル付きポリゴン、前記半透明付きポリゴンの
    順に処理をすることを特徴とする請求項６乃至請求項９
    いずれかに記載の画像処理方法。