(57)【特許請求の範囲】
【請求項１】
第１の方向と、前記第１の方向に略直交する第２の方向にそれぞれ並ぶポリゴンに対応する画素に関するデータである画素データを記憶させる画像処理装置において、
前記第１の方向に並ぶ所定の数のポリゴンを、前記第２の方向に並ぶ順に対象ブロックとし、前記対象ブロックごとに、前記対象ブロックを構成するポリゴンの頂点に関するデータである頂点データを生成する生成手段と、
前記頂点データを、前記画素データに変換する画素データ変換手段と、
複数の前記画素データから構成されるデータブロック単位で、前記画素データを一時的に記憶する一時記憶手段と、
前記画素データ変換手段により変換された画素データと、前記一時記憶手段に記憶されている画素データとを比較する比較手段と
を備え、
前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数は、前記対象ブロックの直前の対象ブロックを構成するポリゴンのうち、前記対象ブロックとの境界部分に位置するポリゴンに対応する画素データが、前記一時記憶手段に記憶されているように決定される
画像処理装置。
【請求項２】
前記画素データを記憶する記憶手段
をさらに備え、
前記一時記憶手段は、前記記憶手段から読み出された画像データを一時的に記憶する
請求項１に記載の画像処理装置。
【請求項３】
前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数は、前記データブロックを構成する画素データの数、前記一時記憶手段に記憶可能な前記データブロックの数、および前記ポリゴンの長さに基づいて、決定される
請求項１に記載の画像処理装置。
【請求項４】
前記生成手段により生成された頂点データに対して、その頂点データに対応する頂点が構成するポリゴンを拡大または縮小するように、変換を行う頂点データ変換手段
をさらに備え、
前記画素データ変換手段は、前記頂点データ変換手段により変換される頂点データを、前記画素データに変換し、
前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数は、前記データブロックを構成する画素データの数、前記一時記憶手段に記憶可能な前記データブロックの数、前記ポリゴンの長さ、および前記拡大または縮小の倍率の逆数に基づいて、決定される
請求項１に記載の画像処理装置。
【請求項５】
前記画素データは、前記画素のｚデータを含み、
前記比較手段は、前記画素データ変換手段により変換された画素データに含まれるｚデータと、前記一時記憶手段に記憶されている、その画素データに対応する画素の画素データに含まれるｚデータとを比較する
請求項１に記載の画像処理装置。
【請求項６】
前記一時記憶手段は、前記画素データ変換手段により変換された画素データに対応する画素の画素データを記憶していない場合、前記記憶手段から、その画素データを含むデータブロック単位の画素データを読み出して、一時的に記憶する
請求項２に記載の画像処理装置。
【請求項７】
第１の方向と、前記第１の方向に略直交する第２の方向にそれぞれ並ぶポリゴンに対応する画素に関するデータである画素データを記憶させる画像処理装置の画像処理方法において、
前記第１の方向に並ぶ所定の数のポリゴンを、前記第２の方向に並ぶ順に対象ブロックとし、前記対象ブロックごとに、前記対象ブロックを構成するポリゴンの頂点に関するデータである頂点データを生成し、
前記頂点データを、前記画素データに変換し、
複数の前記画素データから構成されるデータブロック単位で、前記画素データを一時記憶手段に一時的に記憶させ、
変換された画素データと、前記一時記憶手段に記憶されている画素データとを比較するステップを含み、
前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数は、前記対象ブロックの直前の対象ブロックを構成するポリゴンのうち、前記対象ブロックとの境界部分に位置するポリゴンに対応する画素データが、前記一時記憶手段に記憶されているように決定される
画像処理方法。
【請求項８】
第１の方向と、前記第１の方向に略直交する第２の方向にそれぞれ並ぶポリゴンに対応する画素に関するデータである画素データを記憶させる処理を、コンピュータに行わせるプログラムにおいて、
前記第１の方向に並ぶ所定の数のポリゴンを、前記第２の方向に並ぶ順に対象ブロックとし、前記対象ブロックごとに、前記対象ブロックを構成するポリゴンの頂点に関するデータである頂点データを生成し、
前記頂点データを、前記画素データに変換し、
複数の前記画素データから構成されるデータブロック単位で、前記画素データを一時記憶手段に一時的に記憶させ、
変換された画素データと、前記一時記憶手段に記憶されている画素データとを比較するステップを含み、
前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数は、前記対象ブロックの直前の対象ブロックを構成するポリゴンのうち、前記対象ブロックとの境界部分に位置するポリゴンに対応する画素データが、前記一時記憶手段に記憶されているように決定される
プログラム。
【請求項９】
第１の方向に並ぶ所定の数のポリゴンを、前記第１の方向に略直交する第２の方向に並ぶ順に対象ブロックとし、前記対象ブロックごとに、前記対象ブロックを構成するポリゴンの頂点に関するデータである頂点データを生成する生成手段と、
前記対象ブロックの直前の対象ブロックを構成するポリゴンのうち、前記対象ブロックとの境界部分に位置するポリゴンに対応する、画素に関するデータである画素データが記憶手段に記憶されているように、前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数を設定する設定手段と
を備える画像処理装置。
【請求項１０】
ポリゴンの頂点に関するデータである頂点データを生成する画像処理装置の画像処理方法において、
第１の方向に並ぶ所定の数のポリゴンを、前記第１の方向に略直交する第２の方向に並ぶ順に対象ブロックとし、前記対象ブロックごとに、前記対象ブロックを構成するポリゴンの前記頂点データを生成し、
前記対象ブロックの直前の対象ブロックを構成するポリゴンのうち、前記対象ブロックとの境界部分に位置するポリゴンに対応する、画素に関するデータである画素データが記憶手段に記憶されているように、前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数を設定する
ステップを含む画像処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、画像処理装置および画像処理方法、並びにプログラムに関し、特に、メモリに対するアクセス効率を向上させることにより、低消費電力で、高精度の画像の変形を行うことができるようにした画像処理装置および画像処理方法、並びにプログラムに関する。
【背景技術】
【０００２】
従来、仮想３次元空間上における画像の変形を行う画像変形装置は、３角形などの多角形からなるポリゴンの組み合わせで構成される物体形状のモデルを作成し、そのモデルに画像を貼り付けるテクスチャマッピングを行うことにより、画像の変形を行う(例えば、特許文献１参照)。
【０００３】
このような画像変形装置は、テクスチャマッピングのために、最終的に出力される変形後の画像の各画素に表示される画像の、テクスチャマッピングにおいて貼り付けられる画像上の位置を表すテクスチャアドレスを、その画素に対応するポリゴン単位で生成し、画素ごとにメモリに記憶する。このとき、画像変形装置は、テクスチャアドレスを、そのテクスチャアドレスに対応する画素の、スクリーン上の位置に対応するアドレスに記憶する。
【０００４】
ここで、ポリゴンの集合体であるメッシュの例を、図１Ａと図１Ｂ、並びに図２Ａと図２Ｂに示す。
【０００５】
図１Ａは、正方格子状のメッシュ１を示している。即ち、メッシュ１は、ポリゴン１Ａとポリゴン１Ｂから構成される正方形１Ｃが、水平方向と、その水平方向に対して直交する垂直方向に格子状にそれぞれ並べられることにより、構成されている。このメッシュ１は、ページターンやウェーブなどの一定方向の変形を行うときのモデルに用いられる。例えば、図１Ａに示したメッシュ１に対してページターンが行われると、メッシュ１は、図１Ｂに示すようになる。
【０００６】
図２Ａは、同心円状のメッシュ２を示している。即ち、メッシュ２は、ポリゴン２Ａとポリゴン２Ｂから構成される四角形２Ｃが、放射方向と、その放射方向に対して略直交する円周方向に同心円状にそれぞれ並べられることにより、構成されている。このメッシュ２は、リップルなど同心円状に変形を行うときのモデルに用いられる。例えば、図２Ａに示したメッシュ２に対してリップルが行われると、メッシュ２は、図２Ｂに示すようになる。
【０００７】
画像変形装置は、このようなメッシュ１やメッシュ２を用いて変形後のモデルを作成した後、そのモデルを構成する各ポリゴンの頂点に関するデータ（以下、頂点データという）に基づいて、ポリゴン単位で、平行移動、拡大縮小、回転などのモデリング変換、クリッピング、スクリーンへの投影を行う透視投影変換などの頂点演算を行い、その結果得られるポリゴン単位の頂点データを、画素に関するデータ（以下、画素データという）に変換するラスタライズ、デプステスト(深度テスト)、テクスチャマッピングなどを行い、その結果得られる画像を、変形後の画像として出力する。
【０００８】
なお、頂点データは、例えば、モデリング座標上の頂点の座標値、テクスチャアドレス、ライティング係数などの頂点単位のデータにより構成される。また、画素データは、仮想視点とスクリーン上の画素を結ぶ直線が面と交わる点のｚ座標を表すｚデータ、テクスチャアドレス、ライティング係数、出力画像上の画素の位置を表すデータ(以下、位置データという)などの画素単位のデータにより構成される。
【０００９】
画像変形装置が、高精度の変形を行うためには、ポリゴンを小さくする必要があるが、例えば、デプステスト時に画素データに含まれるｚデータを、キャッシュを用いてメモリに記憶する場合、キャッシュのヒット率が低下し、メモリへのアクセスが増大してしまうという問題がある。
【００１０】
この問題について、図３乃至図５を参照して説明する。
【００１１】
なお、図３乃至図５では、説明の便宜上、画像の変形が行われないものとして説明する。また、図３乃至図５では、水平方向と垂直方向にそれぞれ４画素並ぶ４×４画素のｚデータを、キャッシュの記憶単位であるキャッシュブロック（キャッシュライン）とするキャッシュが用いられるものとする。
【００１２】
図３は、ポリゴン１１1，１１2，１１3，１１4，１１5，・・・，１１n1，１１n1+1，・・・，１１2n1，１１2n1+1，・・・，１１3n1，・・・からなる正方格子状のメッシュを用いたモデル１０を示している。なお、各ポリゴンを区別する必要がない場合、各ポリゴンをまとめてポリゴン１１という。
【００１３】
なお、図３において、白丸と黒丸からなる丸は画素を表し、丸の色である白と黒は、キャッシュブロックの境界を表している。即ち、白丸で表される画素と黒丸で表される画素のｚデータは、それぞれ異なるキャッシュブロックとされ、また隣接しない白丸同士と黒丸同士で表される画素のｚデータも異なるキャッシュブロックとされる。
【００１４】
例えば、図３において、正方形１２で囲まれた１６個の黒丸で表される画素１５1乃至１５4，１５m1+1乃至１５m1+4，１５2m1+1乃至１５2m1+4、および１５3m1+1乃至１５3m1+4のｚデータ、正方形１３で囲まれた１６個の白丸で表される画素１５5乃至１５8，１５m1+5乃至１５m1+8，１５2m1+5乃至１５2m1+8、および１５3m1+5乃至１５3m1+8のｚデータ、正方形１４で囲まれた１６個の黒丸で表される画素１５9乃至１５12，１５m1+9乃至１５m1+12，１５2m1+9乃至１５2m1+12、および１５3m1+9乃至１５3m1+12のｚデータは、それぞれ異なるキャッシュブロックとされる。なお、以下では、各画素を区別する必要がない場合、各画素をまとめて画素１５という。
【００１５】
画像変形装置は、図３のモデル１０を構成するポリゴン１１に対して、そのポリゴン１１が配置される水平方向の順に、即ち図中Ａ方向に並ぶ順に頂点データを生成する。
【００１６】
即ち、画像変形装置は、垂直方向の最上段目に並ぶｎ１個のポリゴン１１1乃至１１n1を、水平方向に並ぶ順であるポリゴン１１1，１１2，１１3，１１4，１１5，・・・，１１n1の順に、ポリゴン１１単位で頂点データを生成する。次に、画像変形装置は、垂直方向の第２段目に並ぶｎ１個のポリゴン１１n1+1乃至１１2n1を、水平方向に並ぶ順であるポリゴン１１n1+1，・・・，１１2n1の順に、ポリゴン１１単位で頂点データを生成し、その後、垂直方向の第３段目に並ぶｎ１個のポリゴン１１2n1+1乃至１１3n1を、水平方向に並ぶ順であるポリゴン１１2n1+1，・・・，１１3n1の順に、ポリゴン１１単位で頂点データを生成する。以降同様にして、第４段目以降のポリゴン１１の頂点データが生成される。
【００１７】
また、画像変形装置は、生成された頂点データに対して頂点演算を行い、その結果得られた順に、頂点データに対してラスタライズを行い、画素データを得る。
【００１８】
即ち、画像変形装置は、ポリゴン１１1，１１2，１１3，１１4，１１5，・・・，１１n1，１１n1+1，・・・，１１2n1，１１2n1+1，・・・，１１3n1，・・・の順に、ポリゴン１１の頂点データの頂点演算の結果を得て、その順にラスタライズを行う。その結果、ポリゴン１１1，１１2，１１3，１１4，１１5，・・・，１１n1，１１n1+1，・・・，１１2n1，１１2n1+1，・・・，１１3n1，・・・に対応する画素１５1，１５2，１５3，１５4，・・・，１５m1，１５m1+1，１５m1+2，１５2m1+1，１５2m1+2，１５m1+3，・・・，１５2m1，１５3m1-1，１５3m1，１５3m1+1，・・・，１５4m1の順に、画素１５の画素データが得られる。
【００１９】
さらに、画像変形装置は、ラスタライズの結果得られる画素データに対して、得られた順に、メモリに記憶されているzデータを用いてデプステストを行う。
【００２０】
具体的には、画像変形装置は、まず最初に、メモリから、正方形１２に囲まれた画素１５1乃至１５4，１５m1+1乃至１５m1+4，１５2m1+1乃至１５2m1+4、および１５3m1+1乃至１５3m1+4のｚデータをキャッシュブロックとして読み出し、その画素１５1乃至１５4のｚデータと、ラスタライズの結果得られた画素１５1乃至１５4の画素データに含まれるｚデータとを、それぞれ順に比較することにより、デプステストを行う。
【００２１】
次に、画像変形装置は、メモリから、正方形１３に囲まれた画素１５5乃至１５8，１５m1+5乃至１５m1+8，１５2m1+5乃至１５2m1+8、および１５3m1+5乃至１５3m1+8のｚデータをキャッシュブロックとして読み出し、その画素１５5乃至１５8のｚデータと、ラスタライズの結果得られた画素１５5乃至１５8の画素データに含まれるｚデータを、それぞれ順に比較することにより、デプステストを行う。以降同様にして、画素１５9乃至１５m1のｚデータが比較されることにより、デプステストが行われる。
【００２２】
このとき、キャッシュに記憶可能なキャッシュブロックの数には限りがあるため、画像変形装置は、新しいキャッシュブロックを読み出す場合、必要に応じて、キャッシュブロックを古い順に追い出す。
【００２３】
従って、画像変形装置が、画素１５9乃至１５m1の画素データに対するデプステスト後に、画素１５m1+1に対するデプステストを行うときには、画素１５1乃至１５4に対するデプステストを行ったときに、メモリからキャッシュブロックとして読み出された正方形１２に含まれる１６個の画素１５のｚデータが、通常、キャッシュから追い出されている。
【００２４】
そこで、画素１５m1+1に対するデプステストを行う場合、画像変形装置は、正方形１２に含まれる１６個の画素１５のキャッシュブロックを再度読み出す必要がある。同様に、画素１５3m1+1に対するデプステストを行う場合も、画像変形装置は、正方形１２に対応するキャッシュブロックを再度読み出す必要がある。即ち、画像変形装置は、各キャッシュブロックを３回読み出す必要がある。
【００２５】
図４は、ポリゴン２１からなる同心円状のメッシュを用いたモデル２０を示しており、図５は、ポリゴン３１からなる同心円状のメッシュを用いたモデル３０を示している。
【００２６】
図４においては、画像変形装置は、モデル２０を構成するポリゴン２１に対して、そのポリゴン２１が配置される放射方向の順に、頂点データを生成し、頂点演算およびラスタライズを行い、画素データを得る。
【００２７】
即ち、画像変形装置は、放射方向Ｂ１に並ぶポリゴン２１に対して、モデル２０の中心Ｏ付近に位置するポリゴン２１から順に、頂点データを生成し、頂点演算およびラスタライズを行う。次に、画像変形装置は、このポリゴン２１の右隣の、放射方向Ｂ２に並ぶポリゴン２１に対して、中心Ｏに位置するポリゴン２１から順に、頂点データを生成し、頂点演算およびラスタライズを行う。以降同様にして、ポリゴン２１の頂点データが生成され、頂点演算およびラスタライズが行われる。
【００２８】
その結果、画像変換装置は、例えば、正方形２２に含まれる画素のｚデータをキャッシュブロックとして、その画素に対応する、射影方向Ｂ１とＢ２の各方向に並ぶポリゴン２１に対応する画素データのデプステストを行うごとに、メモリから読み出す必要がある。即ち、画像変形装置は、各キャッシュブロックを２回読み出す必要がある。
【００２９】
また、図５においては、画像変形装置は、図５のモデル３０を構成するポリゴン３１に対して、そのポリゴン３１が配置される同心円状の順に、頂点データを生成し、頂点演算およびラスタライズを行い、画素データを得る。
【００３０】
即ち、画像変形装置は、円周方向Ｃ１に同心円状に並ぶポリゴン３１に対して、ポリゴン３１が円周方向Ｃ１に並ぶ順に、頂点データを生成し、頂点演算およびラスタライズを行う。次に、画像変形装置は、このポリゴン３１の外側に隣接する、矢印Ｃ２方向に同心円状に並ぶポリゴン３１に対して、ポリゴン３１が矢印Ｃ２方向に並ぶ順に、頂点データを生成し、頂点演算およびラスタライズを行う。以降同様にして、ポリゴン３１の頂点データが生成され、頂点演算およびラスタライズが行われる。
【００３１】
その結果、画像変換装置は、例えば、正方形３２に含まれる画素のｚデータをキャッシュブロックとして、その画素に対応する、円周方向Ｃ１乃至Ｃ４の各方向に並ぶポリゴン３１に対応する画素データのデプステストを行うごとに、メモリから読み出す必要がある。即ち、画像変形装置は、各キャッシュブロックを４回読み出す必要がある。
【００３２】
【特許文献１】特開２００２−８３３１６号公報
【発明の開示】
【発明が解決しようとする課題】
【００３３】
以上のように、ポリゴンが小さく、キャッシュブロックとされるｚデータに対応するポリゴンが、頂点データの生成順に対応する方向とは異なる方向に複数個並べられている場合、通常、追い出しの発生により、各キャッシュブロックを複数回読み出す必要がある。即ち、キャッシュのヒット効率が悪い。
【００３４】
その結果、高精度の変形を行うために、ポリゴンを小さくする場合、メモリの帯域幅を大きくしなければならず、消費電力が増加したり、製造コストが増加する。
【００３５】
本発明は、このような状況に鑑みてなされたものであり、メモリに対するアクセス効率を向上させることにより、低消費電力で、高精度の画像の変形を行うことができるようにするものである。
【課題を解決するための手段】
【００３６】
本発明の第１の側面の画像処理装置は、第１の方向と、前記第１の方向に略直交する第２の方向にそれぞれ並ぶポリゴンに対応する画素に関するデータである画素データを記憶させる画像処理装置において、前記第１の方向に並ぶ所定の数のポリゴンを、前記第２の方向に並ぶ順に対象ブロックとし、前記対象ブロックごとに、前記対象ブロックを構成するポリゴンの頂点に関するデータである頂点データを生成する生成手段と、前記頂点データを、前記画素データに変換する画素データ変換手段と、複数の前記画素データから構成されるデータブロック単位で、前記画素データを一時的に記憶する一時記憶手段と、前記画素データ変換手段により変換された画素データと、前記一時記憶手段に記憶されている画素データとを比較する比較手段とを備え、前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数は、前記対象ブロックの直前の対象ブロックを構成するポリゴンのうち、前記対象ブロックとの境界部分に位置するポリゴンに対応する画素データが、前記一時記憶手段に記憶されているように決定される。
【００３７】
前記画像処理装置は、前記画素データを記憶する記憶手段をさらに設け、前記一時記憶手段は、前記記憶手段から読み出された画像データを一時的に記憶する。
前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数は、前記データブロックを構成する画素データの数、前記一時記憶手段に記憶可能な前記データブロックの数、および前記ポリゴンの長さに基づいて、決定される。
【００３８】
前記画像処理装置は、前記生成手段により生成された頂点データに対して、その頂点データに対応する頂点が構成するポリゴンを拡大または縮小するように、変換を行う頂点データ変換手段をさらに設け、前記画素データ変換手段は、前記頂点データ変換手段により変換される頂点データを、前記画素データに変換し、前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数は、前記データブロックを構成する画素データの数、前記一時記憶手段に記憶可能な前記データブロックの数、前記ポリゴンの長さ、および前記拡大または縮小の倍率の逆数に基づいて、決定される。
【００３９】
前記画素データは、前記画素のｚデータを含み、前記比較手段は、前記画素データ変換手段により変換された画素データに含まれるｚデータと、前記一時記憶手段に記憶されている、その画素データに対応する画素の画素データに含まれるｚデータとを比較することにより、陰面消去の処理を行う。
【００４０】
前記一時記憶手段は、前記画素データ変換手段により変換された画素データに対応する画素の画素データを記憶していない場合、前記記憶手段から、その画素データを含むデータブロック単位の画素データを読み出して、一時的に記憶する。
【００４１】
本発明の第１の側面の画像処理方法は、第１の方向と、前記第１の方向に略直交する第２の方向にそれぞれ並ぶポリゴンに対応する画素に関するデータである画素データを記憶させる画像処理装置の画像処理方法において、前記第１の方向に並ぶ所定の数のポリゴンを、前記第２の方向に並ぶ順に対象ブロックとし、前記対象ブロックごとに、前記対象ブロックを構成するポリゴンの頂点に関するデータである頂点データを生成し、前記頂点データを、前記画素データに変換し、複数の前記画素データから構成されるデータブロック単位で、前記画素データを一時記憶手段に一時的に記憶させ、変換された画素データと、前記一時記憶手段に記憶されている画素データとを比較するステップを含み、前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数は、前記対象ブロックの直前の対象ブロックを構成するポリゴンのうち、前記対象ブロックとの境界部分に位置するポリゴンに対応する画素データが、前記一時記憶手段に記憶されているように決定される。
【００４２】
本発明の第１の側面のプログラムは、第１の方向と、前記第１の方向に略直交する第２の方向にそれぞれ並ぶポリゴンに対応する画素に関するデータである画素データを記憶させる処理を、コンピュータに行わせるプログラムにおいて、前記第１の方向に並ぶ所定の数のポリゴンを、前記第２の方向に並ぶ順に対象ブロックとし、前記対象ブロックごとに、前記対象ブロックを構成するポリゴンの頂点に関するデータである頂点データを生成し、前記頂点データを、前記画素データに変換し、複数の前記画素データから構成されるデータブロック単位で、前記画素データを一時記憶手段に一時的に記憶させ、変換された画素データと、前記一時記憶手段に記憶されている画素データとを比較するステップを含み、前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数は、前記対象ブロックの直前の対象ブロックを構成するポリゴンのうち、前記対象ブロックとの境界部分に位置するポリゴンに対応する画素データが、前記一時記憶手段に記憶されているように決定される。
本発明の第２の側面の画像処理装置は、第１の方向に並ぶ所定の数のポリゴンを、前記第１の方向に略直交する第２の方向に並ぶ順に対象ブロックとし、前記対象ブロックごとに、前記対象ブロックを構成するポリゴンの頂点に関するデータである頂点データを生成する生成手段と、前記対象ブロックの直前の対象ブロックを構成するポリゴンのうち、前記対象ブロックとの境界部分に位置するポリゴンに対応する、画素に関するデータである画素データが記憶手段に記憶されているように、前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数を設定する設定手段とを備える。
本発明の第２の側面の画像処理方法は、ポリゴンの頂点に関するデータである頂点データを生成する画像処理装置の画像処理方法において、第１の方向に並ぶ所定の数のポリゴンを、前記第１の方向に略直交する第２の方向に並ぶ順に対象ブロックとし、前記対象ブロックごとに、前記対象ブロックを構成するポリゴンの前記頂点データを生成し、前記対象ブロックの直前の対象ブロックを構成するポリゴンのうち、前記対象ブロックとの境界部分に位置するポリゴンに対応する、画素に関するデータである画素データが記憶手段に記憶されているように、前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数を設定するステップを含む。
【００４３】
本発明の第１の側面においては、ポリゴンが、第１の方向と、第１の方向に略直交する第２の方向にそれぞれ並んでおり、第１の方向に並ぶ所定の数のポリゴンが、第２の方向に並ぶ順に対象ブロックとされ、対象ブロックごとに、対象ブロックを構成するポリゴンの頂点に関するデータである頂点データが生成され、頂点データが、画素データに変換され、複数の画素データから構成されるデータブロック単位で、画素データが一時記憶手段に一時的に記憶される。また、変換された画素データと、一時記憶手段に記憶されている画素データとが比較される。なお、対象ブロックを構成する第１の方向に並ぶポリゴンの数は、対象ブロックの直前の対象ブロックを構成するポリゴンのうち、対象ブロックとの境界部分に位置するポリゴンに対応する画素データが、一時記憶手段に記憶されているように決定される。
本発明の第２の側面においては、第１の方向に並ぶ所定の数のポリゴンが、第１の方向に略直交する第２の方向に並ぶ順に対象ブロックとされ、対象ブロックごとに、対象ブロックを構成するポリゴンの頂点に関するデータである頂点データが生成され、対象ブロックの直前の対象ブロックを構成するポリゴンのうち、対象ブロックとの境界部分に位置するポリゴンに対応する、画素に関するデータである画素データが記憶手段に記憶されているように、対象ブロックを構成する第１の方向に並ぶポリゴンの数が設定される。
【発明の効果】
【００４４】
以上のように、本発明によれば、画像を変形することができる。
【００４５】
また、本発明によれば、メモリに対するアクセス効率を向上させることにより、低消費電力で、高精度の画像の変形を行うことができる。
【発明を実施するための最良の形態】
【００４６】
以下に本発明の実施の形態を説明するが、本発明の構成要件と、明細書又は図面に記載の実施の形態との対応関係を例示すると、次のようになる。この記載は、本発明をサポートする実施の形態が、明細書又は図面に記載されていることを確認するためのものである。従って、明細書又は図面中には記載されているが、本発明の構成要件に対応する実施の形態として、ここには記載されていない実施の形態があったとしても、そのことは、その実施の形態が、その構成要件に対応するものではないことを意味するものではない。逆に、実施の形態が構成要件に対応するものとしてここに記載されていたとしても、そのことは、その実施の形態が、その構成要件以外の構成要件には対応しないものであることを意味するものでもない。
【００４７】
本発明の第１の側面の画像処理装置は、第１に、
第１の方向(例えば、垂直方向)と、前記第１の方向に略直交する第２の方向(例えば水平方向)にそれぞれ並ぶポリゴンに対応する画素に関するデータである画素データを記憶させる画像処理装置（例えば、図６の画像処理システム５１）において、
前記第１の方向に並ぶ所定の数のポリゴンを、前記第２の方向に並ぶ順に対象ブロックとし、前記対象ブロックごとに、前記対象ブロックを構成するポリゴンの頂点に関するデータである頂点データを生成する生成手段(例えば、図８のCPU１２１)と、
前記頂点データを、前記画素データに変換する画素データ変換手段（例えば、図８のDD
A１２４）と、
複数の前記画素データから構成されるデータブロック単位で、前記画素データを一時的に記憶する一時記憶手段(例えば、図８のｚデータキャッシュ１２６)と、
前記画素データ変換手段により変換された画素データと、前記一時記憶手段に記憶されている画素データとを比較する比較手段（例えば、デプステスト部１２５）と
を備え、
前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数は、前記対象ブロックの直前の対象ブロックを構成するポリゴンのうち、前記対象ブロックとの境界部分に位置するポリゴンに対応する画素データが、前記一時記憶手段に記憶されているように決定される。
【００４８】
本発明の第１の側面の画像処理装置は、第２に、
前記生成手段により生成された頂点データに対して、その頂点データに対応する頂点が構成するポリゴンを拡大または縮小するように、変換を行う頂点データ変換手段(例えば、図８の頂点演算部１２２)
をさらに備え、
前記画素データ変換手段は、前記頂点データ変換手段により変換される頂点データを、前記画素データに変換し（例えば、図９のステップＳ３４の処理）、
前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数は、前記データブロックを構成する画素データの数、前記一時記憶手段に記憶可能な前記データブロックの数、前記ポリゴンの長さ、および前記拡大または縮小の倍率の逆数に基づいて、決定される。
【００４９】
本発明の第１の側面の画像処理装置は、
前記画素データは、前記画素のｚデータを含み、
前記比較手段は、前記画素データ変換手段により変換された画素データに含まれるｚデータと、前記一時記憶手段に記憶されている、その画素データに対応する画素の画素データに含まれるｚデータとを比較する(例えば、図９のステップＳ３６乃至Ｓ３９の処理)。
【００５０】
本発明の第１の側面の画像処理方法は、
第１の方向（例えば、垂直方向）と、前記第１の方向に略直交する第２の方向(例えば、水平方向)にそれぞれ並ぶポリゴン（例えば、ポリゴン１１1）に対応する画素に関するデータである画素データを記憶させる画像処理装置(例えば、図６の画像処理システム５１)の画像処理方法において、
前記第１の方向に並ぶ所定の数のポリゴンを、前記第２の方向に並ぶ順に対象ブロック(例えば、図１０の処理対象ブロック１５０)とし、前記対象ブロックごとに、前記対象ブロックを構成するポリゴンの頂点に関するデータである頂点データを生成し（例えば、図１３のステップＳ５３）、
前記頂点データを、前記画素データに変換し（例えば、図９のステップＳ３４）、
複数の前記画素データから構成されるデータブロック単位で、前記画素データを一時記憶手段に一時的に記憶させ(例えば、図９のステップＳ３５)、
変換された画素データと、前記一時記憶手段に記憶されている画素データとを比較するステップ(例えば、図９のステップＳ３６)を含み、
前記対象ブロックを構成する前記第１の方向に並ぶポリゴンの数は、前記対象ブロックの直前の対象ブロックを構成するポリゴンのうち、前記対象ブロックとの境界部分に位置するポリゴンに対応する画素データが、前記一時記憶手段に記憶されているように決定される。
【００５１】
図６は、本発明を適用した画像処理システム５１の構成例を示すブロック図である。
【００５２】
図６の画像処理システム５１は、デジタル画像特殊効果装置(Digital Multi Effects（DME）)６１、外部メモリ６２、および外部メモリ６３から構成される。画像処理システム５１は、入力されたフィールド単位の画像である入力画像を縮小、拡大、型の変更、回転、左右反転もしくは上下反転、または移動させたり、入力画像に特殊効果(例えば、モザイク、ポスタリゼーション、ネガポジ反転、水平方向または垂直方向のデフォーカスなど)を施すことにより、入力画像を変形し、変形後のフレーム単位の画像を出力する。
【００５３】
なお、入力画像は、各画素の輝度信号、色差信号、およびキーイングに用いられるキー信号を表す値である画素値から構成される。また、画像処理システム５１の各部は、外部メモリ６３に記憶されているプログラムにしたがって、各種の処理を実行する。
【００５４】
DME６１は、例えばIC（Integrated Circuit）やLSIなどにより構成される。DME６１は、前処理部７１、水平フィルタ７２、垂直フィルタ７３、ＩＰ（Interlace Progressive）変換部７４、RAM（Random Access Memory）モジュール７５、補間演算部７６、付加部７７、メモリ制御部７８、およびアドレス生成部７９から構成される。
【００５５】
DME６１には、テクスチャマッピングにおいて貼り付けられる画像である入力画像とタイミング信号が供給される。入力画像は、前処理部７１に供給される。タイミング信号は、DME６１の各部に供給され、各部はタイミング信号に応じて処理を行う。
【００５６】
前処理部７１は、アドレス生成部７９から供給される指示信号に応じて、入力画像に対して、モザイク、ポスタリゼーション、ネガポジ反転などの特殊効果を施す。具体的には、前処理部７１は、入力画像を構成する画素のうちの、所定の画素に対して画素単位でフィルタ処理を行うことにより、入力画像にモザイクを施す。また、前処理部７１は、入力画像を構成する各画素の画素値の階調数を変更することにより、入力画像にポスタリゼーションを施す。さらに、前処理部７１は、入力画像を構成する各画素の画素値の階調を反転することにより、入力画像にネガポジ反転を施す。前処理部７１は、特殊効果を施した結果得られる、フィールド単位の画像を、水平フィルタ７２に供給する。
【００５７】
水平フィルタ７２は、アドレス生成部７９から供給される水平方向の縮小率に応じて、画像を縮小する場合に生じる水平方向のエリアシング成分を除去するために、前処理部７１からのフィールド単位の画像に対して、水平方向の縮小率に対応するフィルタ処理を行う。また、水平フィルタ７２は、アドレス生成部７９から供給される指示信号に応じて、特殊効果として、水平方向のデフォーカスを施す。水平フィルタ７２は、フィルタ処理や水平方向のデフォーカスを施した結果得られる、フィールド単位の画像を、メモリ制御部７８を介して、外部メモリ６２に供給させ、記憶させる。
【００５８】
垂直フィルタ７３は、アドレス生成部７９から供給される垂直方向の縮小率に応じて、画像を縮小する場合に生じる垂直方向のエリアシング成分を除去するために、メモリ制御部７８から供給される、外部メモリ６２から垂直方向に読み出されたフィールド単位の画像に対して、垂直方向の縮小率に対応するフィルタ処理を行う。また、垂直フィルタ７３は、アドレス生成部７９から供給される指示信号に応じて、特殊効果として、垂直方向のデフォーカスを施す。垂直フィルタ７３は、フィルタ処理や垂直方向のデフォーカスを施した結果得られる、フィールド単位の画像を、ＩＰ変換部７４に供給するとともに、メモリ制御部７８を介して外部メモリ６２に供給させ、記憶させる。
【００５９】
ＩＰ変換部７４は、垂直フィルタ７３から供給される、フィールド単位の画像(インタレース画像)を、メモリ制御部７８から供給される、その画像の直前のフィールド単位の画像と、直前の前のフィールド単位の画像とを参照してＩＰ変換する。ＩＰ変換部７４は、ＩＰ変換の結果得られるフレーム単位の画像（プログレッシブ画像）を、RAMモジュール７５に供給する。
【００６０】
RAMモジュール７５は、ＩＰ変換部７４からのフレーム単位の画像を記憶する。また、RAMモジュール７５は、アドレス生成部７９から供給される、テクスチャアドレスの整数部、即ち補間演算部７６による補間演算の対象とする画素(以下、補間画素という)の入力画像上の座標における水平方向の座標値の整数部および垂直方向の座標値の整数部に基づいて、既に記憶されているフレーム単位の画像を構成する各画素の画素値から、補間画素の補間に用いる複数の画素の画素値、例えば補間画素の周辺の６４個の画素の画素値を画素値群として読み出し、補間演算部７６に供給する。
【００６１】
なお、入力画像上の座標において、入力画像を構成する画素の水平方向および垂直方向の座標値は、整数値となるようになっている。
【００６２】
補間演算部７６は、アドレス生成部７９から供給される、テクスチャアドレスの小数部、即ち補間画素の入力画像上の座標における水平方向および垂直方向の座標値の小数部と、RAMモジュール７５から供給される画素値群とに基づいて、補間演算を行い、補間画素の画素値を補間することにより、テクスチャマッピングを行う。補間演算部７６は、補間後のフレーム単位の画像を、メモリ制御部７８を介して外部メモリ６２に供給させ、記憶させる。
【００６３】
付加部７７は、アドレス生成部７９から供給されるライティング係数を用いて陰影を付加し、付加後の画像を変形後の画像として出力する。
【００６４】
メモリ制御部７８は、外部メモリ６２に対する書き込みおよび読み出しを制御する。具体的には、メモリ制御部７８は、外部メモリ６２への書き込みを制御するための制御信号を外部メモリ６２に供給するとともに、水平フィルタ７２、垂直フィルタ７３、または補間演算部７６から供給される画像を外部メモリ６２に供給し、その画像を外部メモリ６２に書き込ませる。
【００６５】
また、メモリ制御部７８は、外部メモリ６２からの画像の読み出しを制御するための制御信号を外部メモリ６２に供給することにより読み出しを制御し、これにより外部メモリ６２から読み出された画像を、垂直フィルタ７３、ＩＰ変換部７４、および付加部７７に供給する。
【００６６】
アドレス生成部７９は、ユーザからの指令に応じて、各部を制御し、入力画像を変形する。また、アドレス生成部７９は、外部メモリ６３に対する書き込みおよび読み出しを制御する。
【００６７】
具体的には、アドレス生成部７９は、外部メモリ６３への書き込みを制御するための制御信号とともに、処理の途中結果や処理結果を外部メモリ６３に供給し、記憶させる。また、アドレス生成部７９は、外部メモリ６３からの処理の途中結果や処理結果の読み出しを制御するための制御信号を、外部メモリ６３に供給することにより、読み出しを制御し、外部メモリ６３から処理の途中結果や処理結果を読み出す。アドレス生成部７９の詳細は、図８を参照して後述する。
【００６８】
次に、図７を参照して、図６の画像処理システム５１が入力画像を変形する画像変形処理について説明する。この画像変形処理は、例えば、画像処理システム５１に入力画像が入力されたとき開始される。
【００６９】
ステップＳ１において、前処理部７１は、アドレス生成部７９から供給される指示信号に応じて、入力画像に対して、モザイク、ポスタリゼーション、またはネガポジ反転を施す。そして、前処理部７１は、その結果得られるフィールド単位の画像を水平フィルタ７２に供給し、ステップＳ２に進む。なお、アドレス生成部７９から指令信号が供給されない場合、処理はステップＳ１をスキップして、ステップＳ２に進む。
【００７０】
ステップＳ２において、水平フィルタ７２は、アドレス生成部７９から供給される水平方向の縮小率に応じて、前処理部７１からのフィールド単位の画像に対して、水平方向の縮小率に対応するフィルタ処理を行う。また、水平フィルタ７２は、アドレス生成部７９から供給される指示信号に応じて、特殊効果として、水平方向のデフォーカスを施す。そして、水平フィルタ７２は、フィルタ処理や水平方向のデフォーカスを施した結果得られる、フィールド単位の画像を、メモリ制御部７８に供給する。
【００７１】
ステップＳ２の処理後は、ステップＳ３に進み、メモリ制御部７８は、外部メモリ６２への書き込みを制御するための制御信号とともに、水平フィルタ７２から供給されるフィールド単位の画像を、外部メモリ６２に供給し、その画像を記憶させる。ステップＳ３の処理後は、ステップＳ４に進み、メモリ制御部７８は、外部メモリ６２からの画像の読み出しを制御するための制御信号を外部メモリ６２に供給することにより、ステップＳ３で記憶されるフィールド単位の画像を垂直方向に、外部メモリ６２から読み出し、垂直フィルタ７３に供給する。
【００７２】
ステップＳ４の処理後は、ステップＳ５に進み、垂直フィルタ７３は、アドレス生成部７９から供給される垂直方向の縮小率に応じて、メモリ制御部７８から供給されるフィールド単位の画像に対して、垂直方向の縮小率に対応するフィルタ処理を行う。また、垂直フィルタ７３は、アドレス生成部７９から供給される指示信号に応じて、特殊効果として、垂直方向のデフォーカスを施す。そして、垂直フィルタ７３は、フィルタ処理や垂直方向のデフォーカスを施した結果得られる、フィールド単位の画像をＩＰ変換部７４に供給するとともに、メモリ制御部７８に供給する。
【００７３】
ステップＳ５の処理後は、ステップＳ６に進み、メモリ制御部７８は、外部メモリ６２への書き込みを制御するための制御信号とともに、垂直フィルタ７３から供給されるフィールド単位の画像を、外部メモリ６２に供給し、その画像を記憶させる。ステップＳ６の処理後は、ステップＳ７に進み、メモリ制御部７８は、外部メモリ６２からの画像の読み出しを制御するための制御信号を外部メモリ６２に供給することにより、直前のステップＳ６の処理で記憶させたフィールド単位の画像の直前のフィールド単位の画像と、直前の前のフィールド単位の画像を、外部メモリ６２から読み出し、ＩＰ変換部７４に供給する。
【００７４】
ステップＳ７の処理後は、ステップＳ８に進み、ＩＰ変換部７４は、ステップＳ５で垂直フィルタ７３から供給されるフィールド単位の画像を、ステップＳ７でメモリ制御部７８から供給される２枚の画像を参照してＩＰ変換する。そして、ＩＰ変換部７４は、ＩＰ変換の結果得られるフレーム単位の画像を、RAMモジュール７５に供給する。
【００７５】
ステップＳ９において、RAMモジュール７５は、ＩＰ変換部７４からのフレーム単位の画像を記憶し、ステップＳ１０に進む。
【００７６】
ステップＳ１０において、RAMモジュール７５は、アドレス生成部７９から供給されるテクスチャアドレスの整数部に基づいて、既に記憶されているフレーム単位の画像を構成する各画素の画素値から、補間画素の補間に用いる複数の画素の画素値を画素値群として読み出し、補間演算部７６に供給する。
【００７７】
ステップＳ１０の処理後は、ステップＳ１１に進み、補間演算部７６は、アドレス生成部７９から供給されるテクスチャアドレスの小数部と、RAMモジュール７５から供給される画素値群とに基づいて、補間演算を行い、補間画素の画素値を補間する。そして、補間演算部７６は、補間後の画像をメモリ制御部７８に供給する。
【００７８】
ステップＳ１１の処理後は、ステップＳ１２に進み、メモリ制御部７８は、外部メモリ６２への書き込みを制御するための制御信号とともに、補間演算部７６からの画像を外部メモリ６２に供給し、その画像を記憶させる。ステップＳ１２の処理後は、ステップＳ１３に進み、メモリ制御部７８は、外部メモリ６２からの画像の読み出しを制御するための制御信号を外部メモリ６２に供給することにより、ステップＳ１２で記憶される画像を読み出し、ステップＳ１４に進む。
【００７９】
ステップＳ１４において、付加部７７は、アドレス生成部７９から供給されるライティング係数を用いて陰影を付加する。そして、付加部７７は、付加後の画像を変形後の画像として出力し、処理は終了する。
【００８０】
なお、上述した図７の画像変形処理のステップＳ１乃至Ｓ９の処理は、補間前の画素単位で行われ、ステップＳ１０乃至Ｓ１４の処理は、補間画素単位で行われる。
【００８１】
図８は、図６の外部メモリ６３とアドレス生成部７９の詳細構成例を示すブロック図である。
【００８２】
図８の外部メモリ６３は、メモリ１０１、ｚデータメモリ１０２、ｚデータメモリ１０３、およびアドレスメモリ１０４により構成される。
【００８３】
また、アドレス生成部７９は、CPU(Central Processing Unit)１２１、頂点演算部１２２、DDA(Digital Differential Analyzer)設定部１２３、DDA１２４、デプステスト部１２５、ｚデータキャッシュ１２６、切替部１２７、アドレスキャッシュ１２８、メモリ制御部１２９、および出力部１３０により構成される。
【００８４】
CPU１２１は、外部メモリ６３のメモリ１０１に記憶されているプログラムにしたがって、画像処理システム５１の各部を制御する。
【００８５】
例えば、CPU１２１は、ユーザの指示に応じて、モザイク、ポスタリゼーション、またはネガポジ反転を指示するための指示信号を、前処理部７１に供給する。また、CPU１２１は、ユーザの指示に応じて、水平方向のデフォーカスを指示するための指示信号を水平フィルタ７２に供給したり、垂直方向のデフォーカスを指示するための指示信号を垂直フィルタ７３に供給する。
【００８６】
また、CPU１２１は、ユーザの指示に応じて、水平方向の縮小率を水平フィルタ７２に供給するとともに、垂直方向の縮小率を垂直フィルタ７３に供給する。さらに、CPU１２１は、ユーザのモデリングの作業に応じて、変形後のフレーム単位の画像に対応するモデルを構成する各ポリゴンの頂点に関するデータ（以下、頂点データという）を、所定の順序で、ポリゴン単位で生成し、頂点演算部１２２に供給する。頂点データの生成順序については、図１０乃至図１３を参照して後述する。
【００８７】
さらに、CPU１２１は、メモリ１０１に対する書き込みおよび読み出しを制御する。例えば、CPU１２１は、メモリ１０１への書き込みを制御する制御信号とともに、処理の途中結果や処理結果をメモリ１０１に供給し、処理の途中結果や処理結果をメモリ１０１に記憶させる。また、CPU１２１は、メモリ１０１からの読み出しを制御する制御信号を供給することにより、メモリ１０１から処理の途中結果や処理結果を読み出し、上述した各種の処理を行う。
【００８８】
頂点演算部１２２は、CPU１２１から供給される頂点データに基づいて、ポリゴン単位で頂点演算を行い、その結果得られるポリゴン単位の頂点データを、DDA設定部１２３に供給する。DDA設定部１２３は、頂点演算部１２２からのポリゴン単位の頂点データに基づいて、例えば、スクリーン上の位置の変化に応じたテクスチャアドレスの変化分などの、DDA１２４に必要なパラメータを計算する。DDA設定部１２３は、ポリゴン単位の頂点データとパラメータをDDA１２４に供給する。
【００８９】
DDA１２４は、DDA設定部１２３から供給されるパラメータに基づいて、ポリゴン単位の頂点データを、画素データに変換する。DDA１２４は、変換の結果得られた画素データを、デプステスト部１２５に供給する。デプステスト部１２５は、DDA１２４からの画素データと、ｚデータキャッシュ１２６に記憶されている、その画素データに対応する画素の画素データとを用いて、陰面消去の処理を行う。
【００９０】
具体的には、デプステスト部１２５は、DDA１２４からの画素データに含まれる位置データに対応する画素単位のアドレス(以下、ｚデータ画素単位アドレスという)に対応付けて記憶されているｚデータの読出を、ｚデータキャッシュ１２６に要求し、その要求に応じて読み出されたｚデータを取得する。
【００９１】
そして、デプステスト部１２５は、そのｚデータと、DDA１２４からの画素データに含まれるｚデータとを比較することにより、DDA１２４からの画素データに対応するポリゴン（以下、適宜、新ポリゴンという）が、既にｚデータキャッシュ１２６に記憶されているｚデータに対応するポリゴン（以下、適宜、古ポリゴンという）よりも仮想視点側に位置するかどうかを判定するデプステストを行う。
【００９２】
デプステスト部１２５は、デプステストの結果に応じて、古ポリゴンよりも仮想視点側に位置する新ポリゴンの画素データに含まれるｚデータとライティング係数を、その画素データに対応するｚデータ画素単位アドレスとともに、ｚデータキャッシュ１２６に供給する。その結果、ｚデータキャッシュ１２６は、デプステスト部１２５からのｚデータ画素単位アドレスに対応付けて記憶されている古ポリゴンのｚデータとライティング係数を、新ポリゴンのｚデータとライティング係数に更新する。
【００９３】
また、デプステスト部１２５は、古ポリゴンよりも仮想視点側に位置する新ポリゴンの画素データに含まれるテクスチャアドレスを、その画素データに含まれる位置データに対応する画素単位のアドレス(以下、テクスチャ画素単位アドレスという)とともに、アドレスキャッシュ１２８に出力する。
【００９４】
ｚデータキャッシュ１２６は、キャッシュブロック単位のｚデータとライティング係数を、キャッシュブロックとして、それらが記憶されるｚデータメモリ１０２または１０３上のキャッシュブロック単位のアドレス(以下、ｚデータキャッシュブロック単位アドレスという)に対応付けて、キャッシュブロックサイズの領域(以下、キャッシュブロック領域という)に一時的に記憶する。
【００９５】
また、ｚデータキャッシュ１２６は、デプステスト部１２５から供給されるｚデータ画素単位アドレスに基づいて、既に記憶しているｚデータから、デプステスト部１２５から読出が要求された、そのｚデータ画素単位アドレスに対応するｚデータを検索する。即ち、ｚデータキャッシュ１２６は、デプステスト部１２５からのｚデータ画素単位アドレスに対応するｚデータキャッシュブロック単位アドレスに対応付けて記憶されている、要求対象のｚデータを含むキャッシュブロックを検索し、そのうちの要求対象のｚデータを検索結果とする。
【００９６】
要求対象のｚデータが検索された場合、ｚデータキャッシュ１２６は、検索結果であるｚデータと、対応するライティング係数とを、デプステスト部１２５に供給する。要求対象のｚデータが検索されない場合、即ち要求対象のｚデータを含むキャッシュブロックが記憶されていない場合、ｚデータキャッシュ１２６は、そのzデータとともにデプステスト部１２５から供給されたｚデータ画素単位アドレスに対応するｚデータキャッシュブロック単位アドレスを、切替部１２７に送信することにより、要求対象のｚデータと、対応するライティング係数の読出を切替部１２７に要求し、ｚデータメモリ１０２または１０３から、ｚデータとライティング係数をキャッシュブロック単位で読み出す。
【００９７】
ｚデータキャッシュ１２６はまた、要求に応じて切替部１２７から供給されてくる、キャッシュブロック単位のｚデータとライティング係数を、キャッシュブロックとして、要求時に切替部１２７に送信したｚデータキャッシュブロック単位アドレスに対応付けてキャッシュブロック領域に一時的に記憶し、そのｚデータをデプステスト部１２５に供給する。
【００９８】
また、ｚデータキャッシュ１２６は、記憶可能なキャッシュブロック領域がない場合、キャッシュブロックの追い出しを行う。具体的には、ｚデータキャッシュ１２６は、追い出しの対象となるキャッシュブロックを決定し、そのキャッシュブロック、並びに、それに対応付けられているｚデータキャッシュブロック単位アドレスを読み出し、追い出しの要求とともに切替部１２７に供給する。
【００９９】
切替部１２７は、ｚデータメモリ１０２と１０３に対する書き込みおよび読み出しを制御する。具体的には、切替部１２７は、ｚデータキャッシュ１２６の要求または出力部１３０の要求に応じて、制御するｚデータメモリを、外部メモリ６３のｚデータメモリ１０２および１０３の一方から他方に切り換える。例えば、切替部１２７は、ｚデータキャッシュ１２６からの読出の要求に応じて、ｚデータメモリ１０２および１０３の一方から、ｚデータキャッシュ１２６からのｚデータキャッシュブロック単位アドレスに記憶されている、キャッシュブロック単位のzデータとライティング係数を読み出し、ｚデータキャッシュ１２６に供給する。
【０１００】
また、切替部１２７は、ｚデータキャッシュ１２６からの追い出しの要求に応じて、ｚデータメモリ１０２および１０３の一方の、ｚデータキャッシュ１２６から供給されるｚデータキャッシュブロック単位アドレスに、キャッシュブロックとして供給されたｚデータとライティング係数を記憶させる。
【０１０１】
さらに、切替部１２７は、出力部１３０からの要求に応じて、ｚデータメモリ１０２および１０３の他方から、ｚデータとライティング係数を読み出し、出力部１３０に供給する。その後、切替部１２７は、ｚデータメモリ１０２および１０３の他方に記憶されている、読み出されたｚデータとライティング係数をクリアする。
【０１０２】
以上のように、ｚデータメモリ１０２およびｚデータメモリ１０３の一方は、デプステスト部１２５における比較用のｚデータと対応するライティング係数とを記憶し、他方は、出力部１３０を介して出力されるデプステスト終了後のｚデータとライティング係数とを記憶する。
【０１０３】
即ち、切替部１２７は、１フレーム分のモデルに対応する画素データがデプステスト部１２５に供給されるごとに切替を行う。
【０１０４】
アドレスキャッシュ１２８は、キャッシュブロック単位のテクスチャアドレスを、キャッシュブロックとして、それが記憶されるアドレスメモリ１０４上のキャッシュブロック単位のアドレス(以下、テクスチャキャッシュブロック単位アドレスという)に対応付けて、キャッシュブロック領域に一時的に記憶する。デプステスト部１２５からのテクスチャ画素単位アドレスに基づいて、それとともに出力されるテクスチャアドレスを含むキャッシュブロック単位のテクスチャアドレスを、キャッシュブロックとして、それが記憶されるアドレスメモリ１０４上のキャッシュブロック単位のアドレス(以下、テクスチャキャッシュブロック単位アドレスという)に対応付けて、キャッシュブロック領域に一時的に記憶する。
【０１０５】
また、アドレスキャッシュ１２８は、デプステスト部１２５から供給されるテクスチャ画素単位アドレスに基づいて、既に記憶しているテクスチャアドレスから、そのテクスチャ画素単位アドレスに対応するテクスチャを検索する。即ち、アドレスキャッシュ１２８は、デプステスト部１２５からのテクスチャ画素単位アドレスに対応するテクスチャキャッシュブロック単位アドレスに対応付けて記憶されている、そのテクスチャ画素単位アドレスに対応するテクスチャアドレスを含むキャッシュブロックを検索し、そのテクスチャアドレスを検索結果とする。
【０１０６】
テクスチャアドレスが検索された場合、アドレスキャッシュ１２８は、検索結果であるテクスチャアドレスを、デプステスト部１２５からのテクスチャアドレスに更新する。テクスチャアドレスが検索されない場合、アドレスキャッシュ１２８は、そのテクスチャとともにデプステスト部１２５から供給されたテクスチャ画素単位アドレスに対応するテクスチャキャッシュブロック単位アドレスを、メモリ制御部１２９に送信することにより、そのテクスチャ画素単位アドレスに対応するテクスチャアドレスの読出をメモリ制御部１２９に要求し、アドレスメモリ１０４から、テクスチャアドレスをキャッシュブロック単位で読み出す。
【０１０７】
アドレスキャッシュ１２８はまた、要求に応じてメモリ制御部１２９から供給されてくる、キャッシュブロック単位のテクスチャアドレスを、キャッシュブロックとして、要求時にメモリ制御部１２９に送信したテクスチャキャッシュブロック単位アドレスに対応付けてキャッシュブロック領域に一時的に記憶する。
【０１０８】
また、アドレスキャッシュ１２８は、記憶可能なキャッシュブロック領域がない場合、キャッシュブロックの追い出しを行う。具体的には、アドレスキャッシュ１２８は、追い出しの対象となるキャッシュブロックを決定し、そのキャッシュブロック、それに対応付けられているテクスチャキャッシュブロック単位アドレスを読み出し、追い出しの要求とともにメモリ制御部１２９に供給する。
【０１０９】
メモリ制御部１２９は、SDRAMなどにより構成されるアドレスメモリ１０４に対する書き込みおよび読み出しを制御する。具体的には、メモリ制御部１２９は、アドレスキャッシュ１２８からの読出の要求に応じて、アドレスメモリ１０４から、アドレスキャッシュ１２８からのテクスチャキャッシュブロック単位アドレスに記憶されている、キャッシュブロック単位のテクスチャアドレスを読み出し、アドレスキャッシュ１２８に供給する。
【０１１０】
また、メモリ制御部１２９は、アドレスキャッシュ１２８からの追い出しの要求に応じて、アドレスキャッシュ１２８からキャッシュブロックとして供給されるキャッシュブロック単位のテクスチャアドレスを、アドレスメモリ１０４の、そのキャッシュブロックとともに供給されるテクスチャキャッシュブロック単位アドレスに、キャッシュブロック単位で記憶させることにより、アドレスメモリ１０４に記憶されているテクスチャアドレスを修正する。
【０１１１】
さらに、メモリ制御部１２９は、出力部１３０からの要求に応じて、アドレスメモリ１０４から、テクスチャアドレスを読み出し、出力部１３０に供給する。その後、メモリ制御部１２９は、アドレスメモリ１０４に記憶されている、読み出されたテクスチャアドレスをクリアする。
【０１１２】
出力部１３０は、付加部７７から出力する変形後の画素の順に、その画素のｚデータとライティング係数の読出を切替部１２７に要求するとともに、テクスチャアドレスの読出をメモリ制御部１２９に要求する。出力部１３０は、要求に応じて切替部１２７から供給されるｚデータとライティング係数のうち、ｚデータを他のDMEなどに出力するとともに、ライティング係数を付加部７７に供給する。また、出力部１３０は、要求に応じてメモリ制御部１２９から供給されるテクスチャアドレスのうちの整数部をRAMモジュール７５に供給するとともに、小数部を補間演算部７６に供給する。
【０１１３】
次に、図９を参照して、アドレス生成部７９がテクスチャアドレスを生成するアドレス生成処理について説明する。このアドレス生成処理は、例えばユーザがモデリングの作業を行ったとき、開始される。なお、図９のアドレス生成処理は、変形後のフレーム単位の画像に対応するモデルごとに行われる。
【０１１４】
ステップＳ３１において、CPU１２１は、ユーザのモデリングの作業に応じて、変形後の画像に対応するモデルを構成する各ポリゴンの頂点データを、所定の順序で生成し、頂点演算部１２２に供給する。
【０１１５】
ステップＳ３１の処理後は、ステップＳ３２に進み、頂点演算部１２２は、CPU１２１から供給される頂点データに基づいて、ポリゴンごとに頂点演算を行う。頂点演算部１２２は、頂点演算の結果得られる、ポリゴン単位の頂点データを、DDA設定部１２３に供給する。
【０１１６】
ステップＳ３２の処理後は、ステップＳ３３に進み、DDA設定部１２３は、頂点演算部１２２からのポリゴン単位の頂点データに基づいて、DDA１２４に必要なパラメータを計算する。DDA設定部１２３は、ポリゴン単位の頂点データとパラメータをDDA１２４に供給する。
【０１１７】
ステップＳ３３の処理後は、ステップＳ３４に進み、DDA１２４は、DDA設定部１２３から供給されるパラメータに基づいて、ポリゴン単位の頂点データを、画素データに変換し、デプステスト部１２５に供給する。
【０１１８】
ステップＳ３４の処理後は、ステップＳ３５に進み、デプステスト部１２５は、ｚデータキャッシュ１２６に、DDA１２４からの画素データに対応する画素のｚデータの読出を要求し、その要求に応じて読み出されたｚデータを取得する。
【０１１９】
ステップＳ３５の処理後は、ステップＳ３６に進み、デプステスト部１２５は、ステップＳ３５で取得されたｚデータと、DDA１２４からの画素データに含まれるｚデータとを比較することにより、新ポリゴンが、古ポリゴンよりも仮想視点側に位置するかどうかを判定するデプステストを行う。
【０１２０】
ステップＳ３６の処理後は、ステップＳ３７に進み、デプステスト部１２５は、デプステストの結果に応じて、新ポリゴンが古ポリゴンよりも仮想視点側に位置するかどうかを判定する。
【０１２１】
ステップＳ３７において、新ポリゴンが古ポリゴンよりも仮想視点側に位置すると判定された場合、デプステスト部１２５は、その新ポリゴンに対応する画素データに含まれるｚデータおよびライティング係数と、ｚデータ画素単位アドレスとを、ｚデータキャッシュ１２６に供給するとともに、テクスチャアドレスとテクスチャ画素単位アドレスを、アドレスキャッシュ１２８に供給する。
【０１２２】
その後、ステップＳ３８において、ｚデータキャッシュ１２６は、デプステスト部１２５からのｚデータとライティング係数を、ｚデータ画素単位アドレスに対応付けて記憶することにより、古ポリゴンのｚデータとライティング係数を、新ポリゴンのｚデータとライティング係数に更新する。
【０１２３】
ステップＳ３８の処理後は、ステップＳ３９に進み、アドレスキャッシュ１２８は、テクスチャアドレスを、テクスチャ画素単位アドレスに対応付けて記憶する。
【０１２４】
ステップＳ３７において、新ポリゴンが古ポリゴンよりも仮想視点側に位置しない、即ち古ポリゴンが新ポリゴンよりも仮想視点側に位置すると判定された場合、またはステップＳ３９の処理後は、ステップＳ４０に進み、デプステスト部１２５は、DDA１２４から供給される、１フレーム分のモデルに対応するすべてのｚデータについて、デプステストを行ったかどうかを判定し、すべてのｚデータについてデプステストを行ってないと判定した場合、ステップＳ３５に戻り、以降の処理を同様に行う。
【０１２５】
また、ステップＳ４０において、すべてのｚデータについてデプステストを行ったと判定された場合、ステップＳ４１に進み、ｚデータキャッシュ１２６とアドレスキャッシュ１２８は、キャッシュブロックの追い出しを行う。
【０１２６】
即ち、ｚデータキャッシュ１２６は、キャッシュブロック領域に記憶されているキャッシュブロック、および、それに対応付けて記憶されているｚデータキャッシュブロック単位アドレスを、切替部１２７を介してｚデータメモリ１０２または１０３に供給する。
【０１２７】
また、アドレスキャッシュ１２８は、キャッシュブロック領域に記憶されているキャッシュブロック、およびそれに対応付けて記憶されているテクスチャキャッシュブロック単位アドレスを、メモリ制御部１２９を介してアドレスメモリ１０４に供給する。
【０１２８】
なお、このとき、ｚデータキャッシュ１２６とアドレスキャッシュ１２８は、すべてのキャッシュブロックの追い出しを行ってもよいし、更新が行われたキャッシュブロックの追い出しだけを行うようにしてもよい。
【０１２９】
図９のアドレス生成処理の後、出力部１３０は、付加部７７から出力する画素の順に、その画素のｚデータとライティング係数を切替部１２７から取得し、ｚデータを他のDMEなどに出力するとともに、ライティング係数を付加部７７に供給する。また、出力部１３０は、その画素のテクスチャアドレスをメモリ制御部１２９から取得し、そのテクスチャアドレスのうちの整数部をRAMモジュール７５に供給するとともに、小数部を補間演算部７６に供給する。
【０１３０】
次に、図１０乃至図１２を参照して、図８のCPU１２１が各ポリゴンの頂点データを生成する順について説明する。
【０１３１】
図１０は、図３と同一の正方格子状のメッシュを用いたモデル１０を示している。
【０１３２】
なお、図１０において、キャッシュブロックとするｚデータおよびライティング係数は、４×４個の画素のｚデータおよびライティング係数である。このことは、後述する図１１においても同様である。また、図１０では、画像の変形が行われないものとして説明する。なお、図３と同一のものには、同一の符号を付してあり、説明は繰り返しになるので省略する。
【０１３３】
図１０では、CPU１２１は、垂直方向に並ぶ１２個のポリゴンから構成されるポリゴン群を、そのポリゴン群が水平方向に並ぶ順に、頂点データを生成する生成処理の対象とするブロック(以下、処理対象ブロックという)とし、その処理対象ブロックを構成する各ポリゴンの頂点データを、垂直方向に並ぶ順に、ポリゴン単位で生成する。
【０１３４】
なお、以下では、適宜、処理対象ブロックとされるポリゴン群の順番に対応する方向（図１０の例では水平方向）のラインを基本移動ラインといい、処理対象ブロック内の生成処理の対象とされるポリゴンの順番に対応する方向（図１０の例では、垂直方向）を移動方向という。
【０１３５】
また、ここで、処理対象ブロックを構成するポリゴンの数(以下、移動量という)は、処理対象ブロックを対象とした生成処理が行われるとき、いまの処理対象ブロックと、直前の処理対象ブロックの境界に位置する、直前の処理対象ブロック内のポリゴンに対応する画素データが、ｚデータキャッシュ１２６に残っている、即ちｚデータキャッシュ１２６から追い出されないように、決定される。
【０１３６】
具体的には、例えば、キャッシュブロックが、水平方向および垂直方向にそれぞれｘ個並んだ合計ｘ×ｘ個の画素のｚデータおよびライティング係数であり、ｚデータキャッシュ１２６に記憶可能なキャッシュブロックがN個である場合、モデリング座標系とスクリーン座標系における各画素の水平方向および垂直方向の長さを１とすると、移動量の最大値Mは、以下の式（１）で表される。
【０１３７】
M=floor((x×N-Margin)/Mesh_Size)
・・・・（１）
【０１３８】
なお、式（１）において、関数floor（）は、（）内の値を超えない最大の整数を表し、Mesh_Sizeは、モデル１０の垂直方向の間隔、即ちポリゴン１１の垂直方向の長さを表す。Marginは、画像の変形が行われた場合であっても、いまの処理対象ブロックと、直前の処理対象ブロックの境界に位置するポリゴンに対応する画素データが、ｚデータキャッシュ１２６から追い出されないようにするために、予め決定された値である。
【０１３９】
即ち、式（１）では、画像の変形が行われない場合を基に最大値Mが求められおり、画像の変形が行われる場合を考慮して、Margin分が減算されている。
【０１４０】
以上のようにして求められた最大値M以下の数が、移動量として決定される。なお、移動量が大きい方が、キャッシュのヒット効率は良くなる。
【０１４１】
図１０では、この最大値Mが１２個であり、上述したように移動量が１２となっている。
【０１４２】
この場合、CPU１２１は、まず最初に、垂直方向に１２個並ぶ合計１２個のポリゴン１１1，１１2，１１n1+1，１１n1+2，１１2n1+1，１１2n1+2，１１3n1+1，１１3n1+2，１１4n1+1，１１4n1+2，１１5n1+1，１１5n1+2，１１6n1+1，１１6n1+2からなるポリゴン群を、処理対象ブロック１５０とし、この順に、ポリゴン１１単位で生成処理を行う。
【０１４３】
ここで、頂点演算部１２２、DDA設定部１２３、およびDDA１２４は、CPU１２１の生成処理によって生成され、出力された頂点データを、パイプライン式に順に処理するので、デプステスト部１２５には、ポリゴン１１1，１１2，１１n1+1，１１n1+2，１１2n1+1，１１2n1+2，１１3n1+1，１１3n1+2，１１4n1+1，１１4n1+2，１１5n1+1，１１5n1+2，１１6n1+1，１１6n1+2の順に、そのポリゴン１１に対応する画素データが供給される。
【０１４４】
即ち、デプステスト部１２５には、画素１５1，１５2，１５m1+1，１５m1+2，１５2m1+1，１５2m1+2，１５3m1+1，１５3m1+2，１５4m1+1，１５4m1+2，１５5m1+1，１５5m1+2，１５6m1+1，１５6m1+2，１５7m1+1，１５7m1+2の順に、その画素データが供給される。従って、デプステスト部１２５は、その順に、画素１５のｚデータを、ｚデータキャッシュ１２６から読み出し、デプステストを行う。
【０１４５】
この場合、ｚデータキャッシュ１２６は、まず最初に、ｚデータメモリ１０２または１０３から、切替部１２７を介して、正方形１２に囲まれた画素１５1乃至１５4，１５m1+1乃至１５m1+4，１５2m1+1乃至１５2m1+4、および１５3m1+1乃至１５3m1+4のｚデータをキャッシュブロックとして読み出して記憶し、デプステスト部１２５が、そのうちの、画素１５1，１５2，１５m1+1，１５m1+2，１５2m1+1，１５2m1+2，１５3m1+1，１５3m1+2のｚデータと、DDA１２４から供給される画素１５1，１５2，１５m1+1，１５m1+2，１５2m1+1，１５2m1+2，１５3m1+1，１５3m1+2の画素データに含まれるｚデータとを、それぞれ順に比較することにより、デプステストを行う。
【０１４６】
次に、ｚデータキャッシュ１２６は、ｚデータメモリ１０２または１０３から、正方形１６１に囲まれた画素１５4m1+1乃至１５4m1+4，１５5m1+1乃至１５5m1+4，１５6m1+1乃至１５6m1+4、および１５7m1+1乃至１５7m1+4のｚデータをキャッシュブロックとして読み出して記憶し、デプステスト部１２５が、そのうちの、１５4m1+1，１５4m1+2，１５5m1+1，１５5m1+2，１５6m1+1，１５6m1+2，１５7m1+1，１５7m1+2のｚデータと、DDA１２４からの１５4m1+1，１５4m1+2，１５5m1+1，１５5m1+2，１５6m1+1，１５6m1+2，１５7m1+1，１５7m1+2の画素データに含まれるｚデータを、それぞれ順に比較することにより、デプステストを行う。
【０１４７】
この後、デプステスト部１２５は、処理対象ブロック１５０と水平方向に隣接する処理対象ブロック１５１を対象とした生成処理により生成された頂点データに対応する画素データを用いて、デプステストを行うが、上述したように、いまの処理対象ブロック１５１と、直前の処理対象ブロック１５０の境界に位置するポリゴン１１2，１１n1+2，１１2n1+2，１１3n1+2，１１4n1+2，１１5n1+2，１１6n1+2に対応する画素データが、ｚデータキャッシュ１２６から追い出されないように、即ち正方形１２と１６１に対応するキャッシュブロックが追い出されないように、移動量が決定されているので、ｚデータキャッシュ１２６は、その２個のキャッシュブロックを用いてデプステストを行えばよく、新たなキャッシュブロックを読み出す必要はない。
【０１４８】
また、次に、デプステスト部１２５は、処理対象ブロック１５１と水平方向に隣接する処理対象ブロック１５２を対象とした生成処理により生成された頂点データに対応する画素データを用いて、デプステストを行うが、上述したように、いまの処理対象ブロック１５２と、直前の処理対象ブロック１５１の境界に位置するポリゴン１１に対応する画素データが、ｚデータキャッシュ１２６から追い出されないように、移動量が決定されているので、ｚデータキャッシュ１２６は、新たに正方形１３と１６２に囲まれた画素１５のｚデータとライティング係数を、それぞれ、キャッシュブロックとして読み出すだけで、正方形１２と１６１に囲まれた画素１５のzデータとライティング係数を、それぞれキャッシュブロックとして読み出す必要はない。
【０１４９】
以上のように、CPU１２１が、垂直方向に並ぶ１２個のポリゴンから構成されるポリゴン群を、そのポリゴン群が水平方向に並ぶ順に、処理対象ブロックとし、その処理対象ブロックを構成する各ポリゴンの頂点データを、垂直方向に並ぶ順に、ポリゴン単位で生成することにより、ｚデータキャッシュ１２６は、各キャッシュブロックを複数回読み出す必要はなくなる。即ち、ｚデータキャッシュ１２６のヒット効率が向上する。
【０１５０】
その結果、画像処理システム５１は、高精度の変形を行うために、ポリゴンを小さくする場合においても、ｚデータメモリ１０２および１０３の帯域幅を大きくする必要がなく、消費電力や製造コストの増加を抑制しつつ、高精度の変形を行うことができる。
【０１５１】
図１１は、画像処理システム５１が、図１０のモデル１０で表される画像に対して、時計回りに回転する変形を行うときの、変形後の画像を表すモデル１７０を示している。
【０１５２】
図１１では、CPU１２１は、図中ｂ方向に並ぶ１２個のポリゴンから構成されるポリゴン群を、そのポリゴン群が、図中ｂ方向に対して直交する図中ａ方向に並ぶ順に、処理対象ブロックとし、その処理対象ブロックを構成する各ポリゴンの頂点データを、ｂ方向に並ぶ順に、ポリゴン単位で生成する。即ち、図１１では、基本移動ラインはａ方向のラインであり、移動方向はｂ方向である。
【０１５３】
ここで、図１１における移動量は、式（１）で求められた最大値Mであるものとする。なお、この場合、式（１）のMesh_Sizeは、モデル１７０のｂ方向の間隔、即ちポリゴン１７１のｂ方向の長さとする。
【０１５４】
この場合、CPU１２１は、まず最初に、垂直方向に１２個並ぶ合計１２個のポリゴン１７１1，１７１2，１７１n6+1，１７１n6+2，１７１2n6+1，１７１2n6+2，１７１3n6+1，１７１3n6+2，１７１4n6+1，１７１4n6+2，１７１5n6+1，１７１5n6+2からなるポリゴンを、処理対象ブロック１８０とし、この順に、ポリゴン１７１単位で生成処理を行うが、頂点演算部１２２はクリッピングを行うので、DDA１２４には、ポリゴン１７１n6+2，１７１2n6+1，１７１2n6+2，１７１3n6+1，１７１3n6+2，１７１4n6+1，１７１4n6+2，１７１5n6+1，１７１5n6+2の順に、ポリゴン１７１に対応する頂点データが供給される。
【０１５５】
従って、DDA１２４は、ポリゴン１７１n6+2，１７１2n6+1，１７１2n6+2，１７１3n6+1，１７１3n6+2，１７１4n6+1，１７１4n6+2，１７１5n6+1，１７１5n6+2の順に、対応する画素１７２3，１７２4，１７２m2+3，１７２2m2+2，１７２2m2+3，１７２3m2+2，１７２3m2+3，１７２4m2+2，１７２5m2+1，１７２5m2+2の画素データに変換し、デプステスト部１２５に供給する。
【０１５６】
デプステスト部１２５は、DDA１２４から供給される順に、画素１７２のｚデータを、ｚデータキャッシュ１２６から読み出し、デプステストを行う。
【０１５７】
このとき、ｚデータキャッシュ１２６は、まず最初に、ｚデータメモリ１０２または１０３から、切替部１２７を介して、正方形１７３に囲まれた画素１７２1乃至１７２4，１７２m2+1乃至１７２m2+4，１７２2m2+1乃至１７２2m2+4、および１７２3m2+1乃至１７２3m2+4のｚデータをキャッシュブロックとして読み出して記憶し、デプステスト部１２５が、そのうちの、画素１７２3，１７２4，１７２m2+3，１７２2m2+2，１７２2m2+3，１７２3m2+2，１７２3m2+3のｚデータと、DDA１２４から供給される画素１７２3，１７２4，１７２m2+3，１７２2m2+2，１７２2m2+3，１７２3m2+2，１７２3m2+3の画素データに含まれるｚデータとを、それぞれ順に比較することにより、デプステストを行う。
【０１５８】
次に、ｚデータキャッシュ１２６は、ｚデータメモリ１０２または１０３から、正方形１７４に囲まれた画素１７２4m2+1乃至１７２4m2+4，１７２5m2+1乃至１７２5m2+4，１７２6m2+1乃至１７２6m2+4、および１７２7m2+1乃至１７２7m2+4のｚデータをキャッシュブロックとして読み出して記憶し、デプステスト部１２５が、そのうちの、１７２4m2+2，１７２5m2+1，１７２5m2+2のｚデータと、DDA１２４からの１７２4m2+2，１７２5m2+1，１７２5m2+2の画素データに含まれるｚデータを、それぞれ順に比較することにより、デプステストを行う。
【０１５９】
この後、デプステスト部１２５は、処理対象ブロック１８０にａ方向に隣接する処理対象ブロック１８１を対象とした生成処理により生成された、頂点データに対応する画素データを用いて、デプステストを行うが、いまの処理対象ブロック１８１と、直前の処理対象ブロック１８２の境界に位置するポリゴン１７１に対応する画素データが、ｚデータキャッシュ１２６から追い出されないように、移動量が決定されているので、ｚデータキャッシュ１２６は、新たに正方形１７５と１７６に囲まれた画素１７２のｚデータとライティング係数を、それぞれ、キャッシュブロックとして読み出すだけで、正方形１７３と１７４に囲まれた画素１７２のzデータとライティング係数を、それぞれキャッシュブロックとして読み出す必要はない。
【０１６０】
以上のように、画像処理システム５１が画像の変形を行う場合においても、CPU１２１が、ｂ方向に並ぶ１２個のポリゴンから構成されるポリゴン群を、そのポリゴン群がａ方向に並ぶ順に、処理対象ブロックとし、その処理対象ブロックを構成する各ポリゴンの頂点データを、ｂ方向に並ぶ順に、ポリゴン単位で生成することにより、ｚデータキャッシュ１２６のヒット効率が向上する。
【０１６１】
図１２は、ポリゴン２０１からなる同心円状のメッシュを用いたモデル２００を示している。
【０１６２】
図１２においては、CPU１２１は、放射方向に並ぶ５個のポリゴン２０１から構成されるポリゴン群を、そのポリゴン群が円周方向に並ぶ順に、処理対象ブロックとし、その処理対象ブロックを構成する各ポリゴンの頂点データを、放射方向に並ぶ順に、ポリゴン単位で生成する。即ち、図１２では、基本移動ラインは円周方向のラインであり、移動方向は放射方向である。
【０１６３】
ここで、図１２における移動量は、式（１）で求められた最大値Mであるものとする。なお、この場合、式（１）のMesh_Sizeは、モデル２００の射影方向の間隔、即ちポリゴン２０１の射影方向の長さとする。
【０１６４】
CPU１２１は、まず最初に、射影方向に並ぶ５個のポリゴン２０１からなるポリゴン群を、処理対象ブロック２０２とし、射影方向に並ぶ順に、ポリゴン２０１単位で生成処理を行う。
【０１６５】
その結果、デプステスト部１２５には、処理対象ブロック２０２を構成するポリゴン２０１の射影方向に並ぶ順に、そのポリゴン２０１に対応する画素データが供給される。デプステスト部１２５は、DDA１２４から供給される順に、画素データに含まれるｚデータを、ｚデータキャッシュ１２６から読み出し、デプステストを行う。
【０１６６】
このとき、ｚデータキャッシュ１２６は、まず最初に、ｚデータメモリ１０２または１０３から、切替部１２７を介して、正方形２１０に囲まれた画素のｚデータをキャッシュブロックとして読み出して記憶し、デプステスト部１２５が、そのうちの、DDA１２４から供給される画素データに対応する画素のｚデータと、DDA１２４からの画素データに含まれるｚデータとを、それぞれ順に比較することにより、デプステストを行う。
【０１６７】
次に、ｚデータキャッシュ１２６は、ｚデータメモリ１０２または１０３から、正方形２１１に囲まれた画素のｚデータをキャッシュブロックとして読み出して記憶し、デプステスト部１２５が、そのうちの、DDA１２４から供給される画素データに対応する画素のｚデータと、DDA１２４からの画素データに含まれるｚデータとを、それぞれ順に比較することにより、デプステストを行う。
【０１６８】
この後、デプステスト部１２５は、処理対象ブロック２０２と円周方向に隣接する処理対象ブロック２０３を対象とした生成処理により生成された頂点データに対応する画素データを用いて、デプステストを行うが、いまの処理対象ブロック２０３と、直前の処理対象ブロック２０２の境界に位置するポリゴン２０１に対応する画素データが、ｚデータキャッシュ１２６から追い出されないように、移動量が決定されているので、ｚデータキャッシュ１２６は、新たに正方形２１０と２１１に囲まれた画素のｚデータとライティング係数を、それぞれ、キャッシュブロックとして読み出す必要はない。
【０１６９】
以上のように、モデルが同心円状のメッシュにより構成される場合であっても、CPU１２１が、射影方向に並ぶ５個のポリゴンから構成されるポリゴン群を、そのポリゴン群が円周方向に並ぶ順に、処理対象ブロックとし、その処理対象ブロックを構成する各ポリゴンの頂点データを、射影方向に並ぶ順に、ポリゴン単位で生成することにより、ｚデータキャッシュ１２６のヒット効率が向上する。
【０１７０】
なお、上述した図１０乃至図１２において、デプステストにおける、ｚデータキャッシュ１２６のヒット効率について説明したが、テクスチャアドレスの記憶における、アドレスキャッシュ１２８のヒット効率も同様に向上する。
【０１７１】
また、式（１）では、上述したように、画像の変形が行われない場合を基に最大値Mが求められているので、頂点演算部１２２におけるモデリング変換で拡大や縮小を行う場合には、補正をする必要がある。即ち、拡大を行う場合には、移動量を小さくする必要があり、縮小を行う場合には、移動量を大きくする必要がある。
【０１７２】
従って、拡大縮小率をSとすると、移動量の最大値Mは、拡大縮小率の逆数を掛けることにより、以下の式（２）で表すことができる。
【０１７３】
M=follr((x×N-Margin)/Mesh_Size/S)
・・・（２）
【０１７４】
なお、式（２）において、拡大や縮小を行わない場合、拡大縮小率Sは１であるので、式（１）となり、拡大や縮小を行わない場合であっても、最大値Mは式（２）を満たす。即ち、拡大や縮小を行うかどうかにかかわらず、最大値Mは式（２）で表すことができる。
【０１７５】
次に、図１３を参照して、CPU１２１が頂点データを頂点演算部１２２に出力する出力処理について説明する。この出力処理は、図９のステップＳ３１に対応している。
【０１７６】
ステップＳ５１において、CPU１２１は、最初の基本移動ライン上の最初のポリゴン群を、処理対象ブロックとして決定し、ステップＳ５２に進む。
【０１７７】
ステップＳ５２において、CPU１２１は、処理対象ブロック内のポリゴンのうち、移動方向の最初のポリゴンを処理対象とし、ステップＳ５３に進む。
【０１７８】
ステップＳ５３において、CPU１２１は、処理対象であるポリゴンの頂点データをポリゴン単位で生成する生成処理を行い、その結果生成される頂点データを頂点演算部１２２に供給する。この頂点データは、図９のステップＳ３２における頂点演算に用いられる。
【０１７９】
ステップＳ５３の処理後は、ステップＳ５４に進み、CPU１２１は、現在の処理対象ブロックに対する生成処理が終了したかどうか、即ち現在の処理対象ブロックのすべてのポリゴンの頂点データを生成したかどうかを判定し、まだ現在の処理対象ブロックに対する生成処理が終了していないと判定した場合、ステップＳ５５に進む。
【０１８０】
ステップＳ５５において、CPU１２１は、現在の処理対象ブロック内のポリゴンのうち、移動方向において、いまの処理対象の次のポリゴンを処理対象とし、ステップＳ５３に戻り、上述した処理を繰り返す。
【０１８１】
一方、ステップＳ５４において、現在の処理対象ブロックに対する生成処理が終了したと判定された場合、即ちいまの処理対象が処理対象ブロック内の移動方向の最後のポリゴンである場合、ステップＳ５６に進み、CPU１２１は、現在の処理対象ブロックが、現在の基本移動ライン上の最後の処理対象ブロックであるかどうかを判定する。
【０１８２】
ステップＳ５６において、現在の処理対象ブロックが、現在の基本移動ライン上の最後の処理対象ブロックではないと判定された場合、ステップＳ５７に進み、現在の基本移動ライン上の次のポリゴン群を処理対象ブロックに決定し、ステップＳ５３に戻る。
【０１８３】
また、ステップＳ５６において、現在の処理対象ブロックが、現在の基本移動ライン上の最後の処理対象ブロックであると判定された場合、ステップＳ５８に進み、現在の基本移動ラインが、最後の基本移動ラインであるかどうかを判定する。
【０１８４】
ステップＳ５８において、現在の基本移動ラインが、最後の基本移動ラインではないと判定された場合、ステップＳ５９に進み、次の基本移動ラインの最初のポリゴン群を処理対象ブロックに決定する。
【０１８５】
一方、ステップＳ５８において、現在の基本移動ラインが、最後の基本移動ラインであると判定された場合、処理は終了する。
【０１８６】
次に、図１４を参照して、DME１１が組み込まれた画像処理装置２５０の例について説明する。
【０１８７】
図１４のCPU（Central Processing Unit）２５１とDME１１は、ROM（Read Only Memory）２５２、または記録部２５８に記録されているプログラムにしたがって各種の処理を実行する。RAM（Random Access Memory）２５３には、CPU２５１が実行するプログラムやデータなどが適宜記憶される。これらのDME１１、CPU２５１、ROM２５２、およびRAM２５３は、バス２５４により相互に接続されている。
【０１８８】
CPU２５１にはまた、バス２５４を介して入出力インターフェース２５５が接続されている。入出力インターフェース２５５には、キーボード、マウス、マイクロホン、図示せぬリモートコントローラから送信されてくる指令を受信する受信部などよりなる入力部２５６、ディスプレイ、スピーカなどよりなる出力部２５７が接続されている。CPU２５１は、入力部２５６から入力される指令に対応して各種の処理を実行する。そして、CPU２５１は、処理の結果を出力部２５７に出力する。
【０１８９】
例えば、CPU２５１は、入力部２５６から入力される指令に対応して、DME１１を制御し、入力画像を縮小、拡大、型の変更、回転、左右反転もしくは上下反転、または移動させたり、入力画像に特殊効果を施す。そして、CPU２５１は、DME１１から出力される画像に基づいて、画像を出力部２５７に表示させる。
【０１９０】
入出力インターフェース２５５に接続されている記録部２５８は、例えばハードディスクからなり、CPU２５１が実行するプログラムや各種のデータを記憶する。通信部２５９は、インターネットやローカルエリアネットワークなどのネットワークを介して外部の装置と通信する。なお、記録部２５８に記録されるプログラムは、通信部２５９を介して取得されるようにしてもよい。
【０１９１】
入出力インターフェース２５５に接続されているドライブ２６０は、磁気ディスク、光ディスク、光磁気ディスク、あるいは半導体メモリなどのリムーバブルメディア２６１が装着されたとき、それらを駆動し、そこに記録されているプログラムやデータなどを取得する。取得されたプログラムやデータは、必要に応じて記録部２５８に転送され、記録される。
【０１９２】
次に、図１５を参照して、DME１１が組み込まれた記録再生装置３００の例について説明する。
【０１９３】
図１５のCPU３０１とDME１１は、ROM３０６または記録部３０５に記録されているプログラムにしたがって各種の処理を実行する。RAM３０７には、CPU３０１が実行するプログラムやデータなどが適宜記憶される。これらのDME１１、CPU３０１、ROM３０６、およびRAM３０７は、バスにより相互に接続されている。
【０１９４】
CPU３０１にはまた、バスを介して入力I/F（Interface）３０９と出力制御部３１０が接続されている。入力I/F３０９には、キーボード、マウス、マイクロホン、図示せぬリモートコントローラから送信されてくる指令を受信する受信部、被写体を撮像する撮像部などよりなる入力部３０８が接続され、出力制御部３１０には、ディスプレイ、スピーカなどよりなる出力部３１１が接続されている。CPU３０１は、入力部３０８から入力I/F３０９を介して入力される指令に対応して、各種の処理を実行する。そして、CPU３０１は、処理の結果を、出力制御部３１０を介して出力部３１１に出力する。
【０１９５】
例えば、CPU３０１は、入力部３０８から入力される指令に対応して、DME１１を制御し、入力画像を縮小、拡大、型の変更、回転、左右反転もしくは上下反転、または移動させたり、入力画像に特殊効果を施す。そして、CPU３０１は、DME１１から出力される画像に基づいて、画像を出力制御部３１０を介して、出力部３１１に表示させる。
【０１９６】
さらに、CPU３０１には、バスを介して、符号化/復号回路３０２と記録再生制御部３０４が接続されている。符号化/復号回路３０２は、CPU３０１の制御により、例えば入力部３０８により撮像された結果得られる画像を、必要に応じて、バッファメモリ３０３に保持させながら、JPEG（Joint Photographic Experts Group）、MPEG(Moving Picture Experts Group)などの所定の符号化方式で符号化する。そして、符号化/復号回路３０２は、符号化の結果得られる画像を、記録再生制御部３０４を介して、記録部３０５に記録させる。
【０１９７】
記録再生制御部３０４は、CPU３０１の制御により、記録部３０５に対する記録と再生を制御する。即ち、記録再生制御部３０４は、符号化/復号回路３０２から供給される画像を記録部３０５に記録させたり、記録部３０５から読み出した画像を、符号化/復号回路３０２に供給する。符号化/復号回路３０２は、CPU３０１の制御により、記録再生制御部３０４からの画像を復号し、その結果得られる画像を、例えば入力画像としてDME１１に供給する。
【０１９８】
本発明は、例えばGPU（Graphics Processing Unit）に適用することができる。
【０１９９】
なお、本明細書において、プログラム記録媒体に格納されるプログラムを記述するステップは、記載された順序に沿って時系列的に行われる処理はもちろん、必ずしも時系列的に処理されなくとも、並列的あるいは個別に実行される処理をも含むものである。
【０２００】
また、本明細書において、システムとは、複数の装置により構成される装置全体を表すものである。
【０２０１】
なお、本発明の実施の形態は、上述した実施の形態に限定されるものではなく、本発明の要旨を逸脱しない範囲において種々の変更が可能である。
【図面の簡単な説明】
【０２０２】
【図１】正方格子状のメッシュの例を示す図である。
【図２】同心円状のメッシュの例を示す図である。
【図３】従来の頂点データの生成順の一例を説明する図である。
【図４】従来の頂点データの生成順の他の一例を説明する図である。
【図５】従来の頂点データの生成順の、さらに他の一例を説明する図である。
【図６】本発明を適用した画像処理システムの一実施の形態の構成例を示すブロック図である。
【図７】画像変形処理を説明するフローチャートである。
【図８】外部メモリとアドレス生成部の詳細構成例を示すブロック図である。
【図９】アドレス生成処理を説明するフローチャートである。
【図１０】頂点データの生成順を説明する図である。
【図１１】頂点データの他の生成順を説明する図である。
【図１２】頂点データのさらに他の生成順を説明する図である。
【図１３】出力処理を説明するフローチャートである。
【図１４】画像処理装置の構成例を示すブロック図である。
【図１５】記録再生装置の構成例を示すブロック図である。
【符号の説明】
【０２０３】
５１  画像処理システム,  １０２,１０３  ｚデータメモリ,  １２１  CPU,  １２２  頂点演算部,  １２４  DDA,  １２５  デプステスト部,  １２６  ｚデータキャッシュ
【図１】
0004492567.tif 000002
【図２】
0004492567.tif 000003
【図３】
0004492567.tif 000004
【図４】
0004492567.tif 000005
【図５】
0004492567.tif 000006
【図６】
0004492567.tif 000007
【図７】
0004492567.tif 000008
【図８】
0004492567.tif 000009
【図９】
0004492567.tif 000010
【図１０】
0004492567.tif 000011
【図１１】
0004492567.tif 000012
【図１２】
0004492567.tif 000013
【図１３】
0004492567.tif 000014
【図１４】
0004492567.tif 000015
【図１５】
0004492567.tif 000016