(57)【特許請求の範囲】
【請求項１】
描画すべきプリミティブに関する情報に基づいてピクセルデータを発生し、複数ピクセルのブロック単位で処理可能なブロック処理モードを有する画像処理装置であって、
グラフィックスメモリと、
上記ブロック処理モードに対応して、一つのブロックを一つのベクトルとしてみなし、複数のブロックをマトリクス状に配列した画像データを複数領域に分割し、各分割領域に対する複数のコードブックを、分割領域の境界付近で使用するエントリは隣接領域のコードブックにも持たせるように生成し、かつ、各コードブックの要素を指したインデックスマップを生成し、生成したコードブックデータおよびインデックスマップデータを上記グラフィックスメモリに格納する処理回路と
を有する画像処理装置。
【請求項２】
上記処理回路は、各分割領域で合計ｎエントリを使い、そのうち、４つの隣接分割領域の境界領域のＡ部分でａエントリ、２つの隣接分割領域の境界領域の少なくとも２つのＢ部分でｂエントリを使うとすると、Ａ部分をａエントリでエンコードし、生成したａエントリを隣接するＢ部分のコードブックにコピーし、Ｂ部分をｂエントリでエンコードし、生成したｂエントリを隣接する対象分割領域の残りのＣ部分のコードブックにコピーし、Ｃ部分をｎエントリでエンコードする
請求項１記載の画像処理装置。
【請求項３】
各コードブックに対するインデックスは、上記Ａ部分については、各コードブックに対応して付与し、上記Ｂ部分については上記Ａ部分からコピーしたエントリを用いてＡ部分と共通部分は共通のインデックスを付与するとともに追加したコードブックに対して新たなインデックスを付与し、上記Ｃ部分については上記Ｂ部分からコピーしたエントリを用いてＡおよびＢ部分と共通部分は共通のインデックスを付与するとともに追加したコードブックに対して新たなインデックスを付与する
請求項２記載の画像処理装置。
【請求項４】
描画すべきプリミティブに関する情報に基づいてピクセルデータを発生し、複数ピクセルのブロック単位で処理可能なブロック処理モードを有する画像処理装置であって、
少なくともテクスチャに関するデータを記憶するグラフィックスメモリと、
上記ブロック処理モードに対応して、一つのブロックを一つのベクトルとしてみなし、複数のブロックをマトリクス状に配列した画像データを複数領域に分割し、各分割領域に対する複数のコードブックを、分割領域の境界付近で使用するエントリは隣接領域のコードブックにも持たせるように生成し、かつ、各コードブックの要素を指したインデックスマップを生成し、生成したコードブックデータおよびインデックスマップデータを上記グラフィックスメモリに格納する第１の処理回路と、
上記ブロック処理モード時に、上記テクスチャ座標から領域ＩＤ、ブロックＩＤ、およびオフセットを算出し、算出したＩＤデータに応じて必要なコードブックを上記グラフィックスメモリから読み出し、算出した領域ＩＤ、ブロックＩＤに対応するインデックスデータを選択し、コードブックから選択したインデックスに対応するブロックを抽出し、ブロックから１テクセルを切り出す第２の処理回路と
を有する画像処理装置。
【請求項５】
上記第２の処理回路は、上記テクスチャ座標から領域ＩＤ、ブロックＩＤ、およびオフセットを算出するＩＤ算出回路と、
上記ブロック処理モード時に、上記グラフィックスメモリからインデックスマップデータが読み込まれ、上記ＩＤ算出回路によるＩＤデータに対応するインデックスデータを選択するインデックスキャッシュと、
上記グラフィックスメモリから所定領域のコードブックを保持し、上記インデックスキャッシュで選択されたインデックスに対応するブロックを抽出するコードブックバッファと、
上記ＩＤ算出回路によるＩＤデータを受けて、上記コードブックバッファに必要なコードブックが読み込まれているか否かの判別を行い、読み込まれていない場合には、コードブック読み込みリクエストを出して上記グラフィックスメモリから必要なコードブックを上記コードブックバッファに読み込ませるコードブック設定回路と
を含む請求項４記載の画像処理装置。
【請求項６】
上記処理回路は、各分割領域で合計ｎエントリを使い、そのうち、４つの隣接分割領域の境界領域のＡ部分でａエントリ、２つの隣接分割領域の境界領域の少なくとも２つのＢ部分でｂエントリを使うとすると、Ａ部分をａエントリでエンコードし、生成したａエントリを隣接するＢ部分のコードブックにコピーし、Ｂ部分をｂエントリでエンコードし、生成したｂエントリを隣接する対象分割領域の残りのＣ部分のコードブックにコピーし、Ｃ部分をｎエントリでエンコードする
請求項４記載の画像処理装置。
【請求項７】
各コードブックに対するインデックスは、上記Ａ部分については、各コードブックに対応して付与し、上記Ｂ部分については上記Ａ部分からコピーしたエントリを用いてＡ部分と共通部分は共通のインデックスを付与するとともに追加したコードブックに対して新たなインデックスを付与し、上記Ｃ部分については上記Ｂ部分からコピーしたエントリを用いてＡおよびＢ部分と共通部分は共通のインデックスを付与するとともに追加したコードブックに対して新たなインデックスを付与する
請求項６記載の画像処理装置。
【請求項８】
描画すべきプリミティブに関する情報に基づいてピクセルデータを発生し、複数ピクセルのブロック単位で処理可能なブロック処理モードを有する画像処理方法であって、
上記ブロック処理モードに対応して、一つのブロックを一つのベクトルとしてみなし、複数のブロックをマトリクス状に配列した画像データを複数領域に分割する第１のステップと、
各分割領域に対する複数のコードブックを、分割領域の境界付近で使用するエントリは隣接領域のコードブックにも持たせるように生成する第２のステップと、
各コードブックの要素を指したインデックスマップを生成する第３のステップと、
生成したコードブックデータおよびインデックスマップデータをグラフィックスメモリに格納する第４のステップと
を有する画像処理方法。
【請求項９】
上記第２および第３のステップでは、各分割領域で合計ｎエントリを使い、そのうち、４つの隣接分割領域の境界領域のＡ部分でａエントリ、２つの隣接分割領域の境界領域の少なくとも２つのＢ部分でｂエントリを使うとすると、
Ａ部分をａエントリでエンコードし、
生成したａエントリを隣接するＢ部分のコードブックにコピーし、
Ｂ部分をｂエントリでエンコードし、
生成したｂエントリを隣接する対象分割領域の残りのＣ部分のコードブックにコピーし、Ｃ部分をｎエントリでエンコードする
請求項８記載の画像処理方法。
【請求項１０】
各コードブックに対するインデックスは、上記Ａ部分については、各コードブックに対応して付与し、上記Ｂ部分については上記Ａ部分からコピーしたエントリを用いてＡ部分と共通部分は共通のインデックスを付与するとともに追加したコードブックに対して新たなインデックスを付与し、上記Ｃ部分については上記Ｂ部分からコピーしたエントリを用いてＡおよびＢ部分と共通部分は共通のインデックスを付与するとともに追加したコードブックに対して新たなインデックスを付与する
請求項９記載の画像処理方法。
【請求項１１】
描画すべきプリミティブに関する情報に基づいてピクセルデータを発生し、複数ピクセルのブロック単位で処理可能なブロック処理モードを有する画像処理方法であって、
上記ブロック処理モードに対応して、一つのブロックを一つのベクトルとしてみなし、複数のブロックをマトリクス状に配列した画像データを複数領域に分割する第１のステップと、
各分割領域に対する複数のコードブックを、分割領域の境界付近で使用するエントリは隣接領域のコードブックにも持たせるように生成する第２のステップと、
各コードブックの要素を指したインデックスマップを生成する第３のステップと、
生成したコードブックデータおよびインデックスマップデータをグラフィックスメモリに格納する第４のステップと、
上記ブロック処理モード時に、テクスチャ座標から領域ＩＤ、ブロックＩＤ、およびオフセットを算出する第５のステップと、
算出したＩＤデータに応じて必要なコードブックを上記グラフィックスメモリから読み出し、算出した領域ＩＤ、ブロックＩＤに対応するインデックスデータを選択する第６のステップと、
コードブックから選択したインデックスに対応するブロックを抽出する第７のステップと、
抽出ブロックから１テクセルを切り出す第８のステップと
を有する画像処理方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、プリミティブを単位図形の組み合わせによって表現し、スクリーン座標系の描画対象領域内に、ピクセルを発生し、３次元グラフィックス描画を実現する画像処理装置およびその方法に関するものである。
【０００２】
【従来の技術】
昨今のコンピュータシステムにおける演算速度の向上や描画機能の強化とも相俟って、コンピュータ資源を用いて図形や画像の作成や処理を行う「コンピュータ・グラフィックス（ＣＧ）」技術が盛んに研究・開発され、さらに実用化されている。
【０００３】
たとえば、３次元グラフィックスは、３次元オブジェクトが所定の光源によって照らされたときの光学現象を数学モデルで表現して、このモデルに基づいてオブジェクト表面に陰影や濃淡を付けたり、さらには模様を貼り付けたりして、よりリアルで３次元的な２次元高精細画像を生成するものである。
このようなコンピュータ・グラフィックスは、科学、工学、製造などの開発分野でのＣＡＤ／ＣＡＭ、その他の各種応用分野においてますます盛んに利用されるようになってきている。
【０００４】
３次元グラフィックスは、一般には、フロントエンドとして位置づけられる「ジオメトリ・サブシステム」と、バックエンドとして位置づけられる「ラスタ・サブシステム」とにより構成される。
【０００５】
ジオメトリ・サブシステムとは、ディスプレイ・スクリーン上に表示する３次元オブジェクトの位置や姿勢などの幾何学的な演算処理を行う過程のことである。
ジオメトリ・サブシステムでは、一般にオブジェクトは多数のポリゴンの集合体として扱われ、ポリゴン単位で、「座標変換」、「クリッピング」、「光源計算」などの幾何学的な演算処理が行われる。
【０００６】
一方、ラスタ・サブシステムは、オブジェクトを構成する各ピクセル（ｐｉｘｅｌ）を塗りつぶす過程のことである。
ラスタライズ処理は、たとえばポリゴン（Ｐｏｌｙｇｏｎ）の頂点毎に求められた画像パラメータを基にして、ポリゴン内部に含まれるすべてのピクセルの画像パラメータを補間することによって実現される。
ここで言う画像パラメータには、いわゆるＲＧＢ形式などで表されるカラー（描画カラー）データ、奥行き方向の距離を表すｚ値などがある。
また、最近の高精細な３次元グラフィックス処理では、遠近感を醸し出すためのｆ（ｆｏｇ：霧）や、物体表面の素材感や模様を表現してリアリティを与えるテクスチャ（ｔｅｘｔｕｒｅ）なども、画像パラメータの１つとして含まれている。
【０００７】
ここで、ポリゴンの頂点情報からポリゴン内部のピクセルを発生する処理では、よくＤＤＡ（Ｄｉｇｉｔａｌ  Ｄｉｆｆｅｒｅｎｔｉａｌ  Ａｎａｌｙｚｅｒ）と呼ばれる線形補間手法を用いて実行される。
ＤＤＡプロセスでは、頂点情報からポリゴンの辺方向へのデータの傾きを求め、この傾きを用いて辺上のデータを算出した後、続いてラスタ走査方向（Ｘ方向）の傾きを算出し、この傾きから求めたパラメータの変化分を走査の開始点のパラメータ値に加えていくことで、内部のピクセルを発生していく。
【０００８】
そして、３次元コンピュータグラフィックスでは、各ピクセルに対応するカラーを決定するときに、各ピクセルのカラーの値を計算し、この計算したカラーの値を、当該ピクセルに対応するディスプレイバッファ（フレームバッファ）の所定アドレスに書き込むレンダリング（Ｒｅｎｄｅｒｉｎｇ）処理を行う。
【０００９】
レンダリング処理の手法の一つに、ポリゴンレンダリングがある。
この手法では、立体モデル（プリミティブ）の三角形の単位図形（ポリゴン）の組み合わせとして表現しておき、このポリゴンを単位として描画を行うことで、表示画面のカラーを決定する。
【００１０】
ポリゴンレンダリングでは、物理座標系における三角形の各頂点についての、座標（ｘ，ｙ，ｚ）と、カラーデータ（Ｒ，Ｇ，Ｂ，α）と、張り合わせのイメージパターンを示すテクスチャデータの同次座標（ｓ，ｔ）および同次項ｑの値とを入力とし、これらの値を三角形の内部で補間する処理が行われる。
ここで、同次項ｑは、簡単にいうと、拡大縮小率のようなもので、実際のテクスチャバッファのＵＶ座標系における座標、すなわち、テクスチャ座標データ（ｕ，ｖ）は、同次座標（ｓ，ｔ）を同次項ｑで除算した「ｓ／ｑ」および「ｔ／ｑ」に、それぞれテクスチャサイズＵＳＩＺＥおよびＶＳＩＺＥを乗じたものとなる。
【００１１】
また、画像データを描画するにあたっては、必要に応じて、現画像データに含まれる（Ｒ，Ｇ，Ｂ）データと、既にフレームバッファに記憶されている（Ｒ，Ｇ，Ｂ）データとが、現画像データに対応するαデータを示す混合値で混合されるαブレンディング処理が行われる。
さらに、αブレンディング後の画像データをフレームバッファの容量等を考慮して、データを間引くディザ（ｄｉｔｈｅｒ）処理が行われて、ディザ処理後の（Ｒ，Ｇ，Ｂ）データがフレームバッファに書き戻される。
【００１２】
換言すれば、αブレンディング処理は、２つの色を線形補間して間に色を付ける処理である。
ディザ処理は、αブレンディング処理を受けたデータに雑音データを加え、その後にデータを間引いて、少ない色数で多くの色に見えるようにするための処理である。
【００１３】
【発明が解決しようとする課題】
ところで、３次元グラフィックスに対応した画像処理装置では、通常は、Ｒ，Ｇ，Ｂそれぞれ８ビットの合計２４ビットでテクスチャ要素を表現するが、それではデータ量が膨らむ。
そのため、３次元グラフィックスに対応した画像処理装置では、グラフィックスメモリにより多くのテクスチャデータを格納するために、インデックスカラーにおけるインデックスと、そのためのカラールックアップテーブル（ＣＬＵＴ）値をグラフィックスメモリに格納しておく。
そして、あらかじめ選んでおいたたとえば２５６色等の中から一つの色を選んで、そのデータをテクスチャ処理に使うことで、２５６色あればそれぞれのテクスチャ要素は８ビットで表現できることになる。
これにより、よいコンパクトなテクスチャデータとしてグラフィックスメモリに格納するデータ量を削減している。
【００１４】
ところが、最近の画像処理装置は、３次元グラフィックスに対応した機能はもとより、さらにより多くの機能を搭載する傾向にあり、グラフィックスメモリの容量には制約を受けることもある。
したがって、単にＣＬＵＴを用いてデータを圧縮するだけでなく、グラフィックスメモリをより効率的に活用する必要が生じてきている。
【００１５】
各種機能を効率的に処理し、グラフィックスメモリをより効率的に活用するために、２次的なキャッシュメモリがよく用いられる。
しかしながら、キャッシュメモリの容量は、一般的に必要なデータを選択的に格納できる程度に設定されるため、単にＣＬＵＴを用いて圧縮するだけでなく、テクスチャデータ等をさらに効率的に圧縮する必要がある。
【００１６】
本発明は、かかる事情に鑑みてなされたものであり、その目的は、テクスチャデータを効率的に圧縮することができ、ひいてはグラフィックスメモリの効率的な活用を実現することができる画像処理装置およびその方法を提供することにある。
【００１７】
【課題を解決するための手段】
上記目的を達成するため、本発明の第１の観点は、描画すべきプリミティブに関する情報に基づいてピクセルデータを発生し、複数ピクセルのブロック単位で処理可能なブロック処理モードを有する画像処理装置であって、グラフィックスメモリと、上記ブロック処理モードに対応して、一つのブロックを一つのベクトルとしてみなし、複数のブロックをマトリクス状に配列した画像データを複数領域に分割し、各分割領域に対する複数のコードブックを、分割領域の境界付近で使用するエントリは隣接領域のコードブックにも持たせるように生成し、かつ、各コードブックの要素を指したインデックスマップを生成し、生成したコードブックデータおよびインデックスマップデータを上記グラフィックスメモリに格納する処理回路とを有する。
【００１８】
本発明では、上記処理回路は、各分割領域で合計ｎエントリを使い、そのうち、４つの隣接分割領域の境界領域のＡ部分でａエントリ、２つの隣接分割領域の境界領域の少なくとも２つのＢ部分でｂエントリを使うとすると、Ａ部分をａエントリでエンコードし、生成したａエントリを隣接するＢ部分のコードブックにコピーし、Ｂ部分をｂエントリでエンコードし、生成したｂエントリを隣接する対象分割領域の残りのＣ部分のコードブックにコピーし、Ｃ部分をｎエントリでエンコードする。
【００１９】
好適には、各コードブックに対するインデックスは、上記Ａ部分については、各コードブックに対応して付与し、上記Ｂ部分については上記Ａ部分からコピーしたエントリを用いてＡ部分と共通部分は共通のインデックスを付与するとともに追加したコードブックに対して新たなインデックスを付与し、上記Ｃ部分については上記Ｂ部分からコピーしたエントリを用いてＡおよびＢ部分と共通部分は共通のインデックスを付与するとともに追加したコードブックに対して新たなインデックスを付与する。
【００２０】
本発明の第２の観点は、描画すべきプリミティブに関する情報に基づいてピクセルデータを発生し、複数ピクセルのブロック単位で処理可能なブロック処理モードを有する画像処理装置であって、少なくともテクスチャに関するデータを記憶するグラフィックスメモリと、上記ブロック処理モードに対応して、一つのブロックを一つのベクトルとしてみなし、複数のブロックをマトリクス状に配列した画像データを複数領域に分割し、各分割領域に対する複数のコードブックを、分割領域の境界付近で使用するエントリは隣接領域のコードブックにも持たせるように生成し、かつ、各コードブックの要素を指したインデックスマップを生成し、生成したコードブックデータおよびインデックスマップデータを上記グラフィックスメモリに格納する第１の処理回路と、上記ブロック処理モード時に、上記テクスチャ座標から領域ＩＤ、ブロックＩＤ、およびオフセットを算出し、算出したＩＤデータに応じて必要なコードブックを上記グラフィックスメモリから読み出し、算出した領域ＩＤ、ブロックＩＤに対応するインデックスデータを選択し、コードブックから選択したインデックスに対応するブロックを抽出し、ブロックから１テクセルを切り出す第２の処理回路とを有する。
【００２１】
本発明では、上記第２の処理回路は、上記テクスチャ座標から領域ＩＤ、ブロックＩＤ、およびオフセットを算出するＩＤ算出回路と、上記ブロック処理モード時に、上記グラフィックスメモリからインデックスマップデータが読み込まれ、上記ＩＤ算出回路によるＩＤデータに対応するインデックスデータを選択するインデックスキャッシュと、上記グラフィックスメモリから所定領域のコードブックを保持し、上記インデックスキャッシュで選択されたインデックスに対応するブロックを抽出するコードブックバッファと、上記ＩＤ算出回路によるＩＤデータを受けて、上記コードブックバッファに必要なコードブックが読み込まれているか否かの判別を行い、読み込まれていない場合には、コードブック読み込みリクエストを出して上記グラフィックスメモリから必要なコードブックを上記コードブックバッファに読み込ませるコードブック設定回路とを含む。
【００２２】
本発明の第３の観点は、描画すべきプリミティブに関する情報に基づいてピクセルデータを発生し、複数ピクセルのブロック単位で処理可能なブロック処理モードを有する画像処理方法であって、上記ブロック処理モードに対応して、一つのブロックを一つのベクトルとしてみなし、複数のブロックをマトリクス状に配列した画像データを複数領域に分割する第１のステップと、各分割領域に対する複数のコードブックを、分割領域の境界付近で使用するエントリは隣接領域のコードブックにも持たせるように生成する第２のステップと、各コードブックの要素を指したインデックスマップを生成する第３のステップと、生成したコードブックデータおよびインデックスマップデータをグラフィックスメモリに格納する第４のステップとを有する。
【００２３】
本発明の第４の観点は、描画すべきプリミティブに関する情報に基づいてピクセルデータを発生し、複数ピクセルのブロック単位で処理可能なブロック処理モードを有する画像処理方法であって、上記ブロック処理モードに対応して、一つのブロックを一つのベクトルとしてみなし、複数のブロックをマトリクス状に配列した画像データを複数領域に分割する第１のステップと、各分割領域に対する複数のコードブックを、分割領域の境界付近で使用するエントリは隣接領域のコードブックにも持たせるように生成する第２のステップと、各コードブックの要素を指したインデックスマップを生成する第３のステップと、生成したコードブックデータおよびインデックスマップデータをグラフィックスメモリに格納する第４のステップと、上記ブロック処理モード時に、テクスチャ座標から領域ＩＤ、ブロックＩＤ、およびオフセットを算出する第５のステップと、算出したＩＤデータに応じて必要なコードブックを上記グラフィックスメモリから読み出し、算出した領域ＩＤ、ブロックＩＤに対応するインデックスデータを選択する第６のステップと、コードブックから選択したインデックスに対応するブロックを抽出する第７のステップと、抽出ブロックから１テクセルを切り出す第８のステップとを有する。
【００２４】
本発明によれば、たとえば第１の処理回路において、ブロック処理モードの前処理として一つのテクスチャを複数領域に分割してエンコードが行われる。そして、各分割領域に対するコードブックが生成される。このコードブックの生成は、分割領域の境界付近で使用するエントリは隣接領域のコードブックにも持たせるようにエンコードされる。
次いで、全てのコードブックが生成された後、対象領域を構成する各ブロックについても最も距離の小さいコードブックエントリが求られて、インデックスマップが生成される。
これら生成されたコードブックデータおよびインデックスマップデータは、メグラフィックスメモリに格納される。
【００２５】
次に、ブロック処理モード時には、ＩＤ算出回路において、テクスチャ座標から領域ＩＤ、ブロックＩＤ、およびオフセットが算出され、ＩＤデータがコードブック設定回路およびインデックスキャッシュに出力される。
コードブック設定回路において、必要なコードブックが読み込まれているか否かの判別が行われ、読み込まれていなければ、たとえばコードブック読み込みリクエストが出力されて、グラフィックスメモリから読み出されたコードブックがコードブックバッファに読み込まれる。
そして、インデックスキャッシュにおいて、ＩＤ算出回路によるＩＤデータが示す領域ＩＤ、ブロックＩＤに対応するインデックスデータが選択され、コードブックバッファに出力される。
コードブックバッファにおいて、インデックスに対応するブロックが抽出され、出力回路において、ブロックから１テクセルを切り出して出力される。
【００２６】
【発明の実施の形態】
以下、本実施形態においては、パーソナルコンピュータなどに適用される、任意の３次元物体モデルに対する所望の３次元画像をＣＲＴ(Cathode Ray Tube)などのディスプレイ上に高速に表示する３次元コンピュータグラフィックスシステムについて説明する。
【００２７】
図１は、本発明に係る画像処理装置としての３次元コンピュータグラフィックスシステム１０のシステム構成図である。
【００２８】
３次元コンピュータグラフィックスシステム１０は、立体モデルを単位図形である三角形（ポリゴン）の組み合わせとして表現し、このポリゴンを描画することで表示画面の各画素のカラーを決定し、ディスプレイに表示するポリゴンレンダリング処理を行うシステムである。
また、３次元コンピュータグラフィックスシステム１０では、平面上の位置を表現する（ｘ，ｙ）座標の他に、奥行きを表すｚ座標を用いて３次元物体を表し、この（ｘ，ｙ，ｚ）の３つの座標で３次元空間の任意の一点を特定する。
【００２９】
図１に示すように、３次元コンピュータグラフィックスシステム１０は、メインプロセッサ１１、メインメモリ１２、Ｉ／Ｏインタフェース回路１３、およびレンダリング回路１４が、メインバス１５を介して接続されている。
以下、各構成要素の機能について説明する。
【００３０】
メインプロセッサ１１は、たとえば、アプリケーションの進行状況などに応じて、メインメモリ１２から必要なグラフィックデータを読み出し、このグラフィックデータに対して、座標変換、クリッピング(Clipping)処理、ライティング(Lighting)処理などのジオメトリ(Geometry)処理などを行い、ポリゴンレンダリングデータを生成する。
メインプロセッサ１１は、ポリゴンレンダリングデータＳ１１を、メインバス１５を介してレンダリング回路１４に出力する。
【００３１】
Ｉ／Ｏインタフェース回路１３は、必要に応じて、外部から動きの制御情報またはポリゴンレンダリングデータなどを入力し、これをメインバス１５を介してレンダリング回路１４に出力する。
【００３２】
レンダリング回路１４に入力されるポリゴンレンダリングデータは、ポリゴンの各３頂点の（ｘ，ｙ，ｚ，Ｒ，Ｇ，Ｂ，α，ｓ，ｔ，ｑ，Ｆ）のデータを含んでいる。
ここで、（ｘ，ｙ，ｚ）データは、ポリゴンの頂点の３次元座標を示し、（Ｒ，Ｇ，Ｂ）データは、それぞれ当該３次元座標における赤、緑、青の輝度値を示している。
データαは、これから描画するピクセルと、レンダリング回路１４のグラフィックスメモリ（ディスプレイバッファ）に既に記憶されているピクセルとのＲ，Ｇ，Ｂデータのブレンド（混合）係数を示している。
（ｓ，ｔ，ｑ）データのうち、（ｓ，ｔ）は、対応するテクスチャの同次座標を示しており、ｑは同次項を示している。ここで、「ｓ／ｑ」および「ｔ／ｑ」に、それぞれテクスチャサイズＵＳＩＺＥおよびＶＳＩＺＥを乗じて、実際のテクスチャ座標データ（ｕ，ｖ）が得られる。
レンダリング回路１４のグラフィックスメモリ（具体的にはテクスチャバッファ）に記憶されたテクスチャデータへのアクセスは、テクスチャ座標データ（ｕ，ｖ）を用いて行われる。
Ｆデータは、フォグのα値を示している。
すなわち、ポリゴンレンダリングデータは、三角形の各頂点の物理座標値と、それぞれの頂点のカラーとテクスチャデータである。
【００３３】
以下、レンダリング回路１４について詳細に説明する。
【００３４】
図１に示すように、レンダリング回路１４は、線形補間演算のための初期設定演算ブロックとしてのＤＤＡ(Digital Differential Analyzer) セットアップ回路１４１、線形補間処理ブロックとしてのトライアングルＤＤＡ回路１４２、テクスチャエンジン回路１４３、ベクトル量子化（ＶＱ;Vector Quantization）回路１４４、メモリインタフェース（Ｉ／Ｆ）回路１４４、フィルタ回路１４５、たとえばＤＲＡＭからなるグラフィックスメモリ１４６、およびＣＲＴコントロール回路１４７を有している。そして、テクスチャエンジン回路１４３、ＶＱ回路１４４、およびメモリインタフェース（Ｉ／Ｆ）回路１４５により第１および第２の処理回路が構成される。
【００３５】
以下、レンダリング回路１４の各ブロックの構成および機能について、図面に関連付けて順を追って説明する。
【００３６】
ＤＤＡセットアップ回路１４１は、後段のトライアングルＤＤＡ回路１４２において物理座標系上の三角形の各頂点の値を線形補間して、三角形の内部の各画素（ピクセル）のカラーと奥行き情報（深さ情報）を求めるに先立ち、ポリゴンレンダリングデータＳ１１が示す（ｚ，Ｒ，Ｇ，Ｂ，α，ｓ，ｔ，ｑ，Ｆ）データについて、三角形の辺と水平方向の差分などを求めるセットアップ演算を行う。
このセットアップ演算は、具体的には、開始点の値と終点の値と、開始点と終点との距離を用いて、単位長さ移動した場合における、求めようとしている値の変分を算出する。
ＤＤＡセットアップ回路１４１は、算出した変分データを含むプリミティブに関する情報としてのセットアップデータＳ１４１をトライアングルＤＤＡ回路１４２に出力する。
【００３７】
ＤＤＡセットアップ回路１４１の機能について図２に関連付けてさらに説明する。
上述したように、ＤＤＡセットアップ回路１４１の主な処理は、前段のジオメトリ処理を経て物理座標にまで落ちてきた各頂点における各種情報（カラー、テクスチャ座標）の与えられた三頂点Ｐ０（ｘ０，ｙ０）、Ｐ１（ｘ１，ｙ１）、Ｐ２（ｘ２，ｙ２）により構成される三角形内部で変分を求めて、後段の線形補間処理の基礎デ−タを算出することである。
三角形の描画はひとつひとつのピクセルの描画に集約されるが、そのために描画開始点における最初の値を求める必要がある。
最初の描画点における各種情報は、頂点からその最初の描画点までの水平距離に水平方向の変分を掛けた値と、垂直距離に垂直方向の変分を掛けた値を足し合わせたものとなる。いったん目的の三角形の内部の一つの整数格子上の値が求まれば、対象の三角形内部のその他の格子点における値は変分の整数倍で求めることが可能となる。
【００３８】
三角形の各頂点データは、たとえばｘ，ｙ座標が１６ビット、ｚ座標が２４ビット、ＲＧＢカラー値が各１２ビット（＝８＋４）、ｓ，ｔ，ｑテクスチャ座標は各３２ビット浮動少数値（ＩＥＥＥフォーマット）等で構成される。
【００３９】
なお、このＤＤＡセットアップ回路１４１は、従来のようにＤＳＰ構造ではなく、ＡＳＩＣ手法により実装している。
具体的には、図３に示すように、多段に配置したレジスタ（ＲＥＧ）１４１１−１〜１４１３間に複数の演算ユニットを並列に配置した演算ユニット群１４１２−１〜１４１２−３を挿入したフルデータパスロジック、換言すれば、同期パイプライン方式の時間並列構造として構成されている。
【００４０】
トライアングルＤＤＡ回路１４２は、ＤＤＡセットアップ回路１４１から入力した変分データを含むプリミティブに関する情報としてのセットアップデータＳ１４１を基に、三角形内部の各画素における線形補間された（ｚ，Ｒ，Ｇ，Ｂ，α，ｓ，ｔ，ｑ，Ｆ）データを算出する。
トライアングルＤＤＡ回路１４２は、各ピクセルの（ｘ，ｙ）データと、当該（ｘ，ｙ）座標における（ｚ，Ｒ，Ｇ，Ｂ，α，ｓ，ｔ，ｑ，Ｆ）データとを、ＤＤＡデータ（補間データ）Ｓ１４２としてテクスチャエンジン回路１４３に出力する。
たとえば、トライアングルＤＤＡ回路１４２は、並行して処理を行う矩形内に位置する８（２×４）ピクセル分のＤＤＡデータＳ１４２をテクスチャエンジン回路１４３に出力する。
【００４１】
すなわち、トライアングルＤＤＡ回路１４２は、ポリゴンの頂点毎に求められた画像パラメータに基づいてポリゴン内部に含まれるすべてのピクセルの画像パラメータを補間するラスタライズ処理（ラスタライゼーション：Ｒａｓｔｅｒｉｚａｔｉｏｎ）を行う。
具体的には、トライアングルＤＤＡ回路１４２は、各種データ（ｚ，テクスチャ座標、カラーなど）をラスタライズする。
【００４２】
テクスチャエンジン回路１４３は、「ｓ／ｑ」および「ｔ／ｑ」の算出処理、テクスチャ座標データ（ｕ，ｖ）の算出処理、グラフィックスメモリ１４６からの（Ｒ，Ｇ，Ｂ）データの読み出し処理、および混合処理（αブレンディング処理）を順にパイプライン方式で行う。
なお、テクスチャエンジン回路１４３は、たとえば所定の矩形内に位置する複数（たとえば４あるいは８）ピクセルについての処理を同時に並行して行う。
【００４３】
テクスチャエンジン回路１４３は、ＤＤＡデータＳ１４２が示す（ｓ，ｔ，ｑ）データについて、ｓデータをｑデータで除算する演算と、ｔデータをｑデータで除算する演算とを行う。
テクスチャエンジン回路１４３には、たとえば図示しない除算回路が並列処理するピクセル数分だけ（たとえば８個）設けられており、８ピクセルについての除算「ｓ／ｑ」および「ｔ／ｑ」が同時に行われる。また、８ピクセルのうち代表点からの補間演算処理を行うように実装することも可能である。
【００４４】
また、テクスチャエンジン回路１４３は、除算結果である「ｓ／ｑ」および「ｔ／ｑ」に、それぞれテクスチャサイズＵＳＩＺＥおよびＶＳＩＺＥを乗じて、テクスチャ座標データ（ｕ，ｖ）を生成する。
また、テクスチャエンジン回路１４３は、メモリＩ／Ｆ回路１４５を介して、グラフィックスメモリ１４６に、生成したテクスチャ座標データ（ｕ，ｖ）を含む読み出し要求を出力し、メモリＩ／Ｆ回路１４５を介して、グラフィックスメモリ１４６に含まれるテクスチャバッファに記憶されているテクスチャデータを読み出すことで、（ｓ，ｔ）データに対応したテクスチャアドレスに記憶された（Ｒ，Ｇ，Ｂ，α）データを得る。
テクスチャエンジン回路１４３は、読み出した（Ｒ，Ｇ，Ｂ，α）データの（Ｒ，Ｇ，Ｂ）データと、前段のトライアングルＤＤＡ回路１４２からのＤＤＡデータＳ１４２に含まれる（Ｒ，Ｇ，Ｂ）データとを、読み出したαデータが示す割合で混合し（それぞれ掛け合わせるなどして）、ピクセルデータＳ１４３を生成する。
テクスチャエンジン回路１４３は、このピクセルデータをピクセルのカラー値としてＶＱ回路１４４に出力する。
【００４５】
なお、グラフィックスメモリ１４６に含まれるテクスチャバッファには、ＭＩＰＭＡＰ（複数解像度テクスチャ）などの複数の縮小率に対応したテクスチャデータが記憶されている。ここで、何れの縮小率のテクスチャデータを用いるかは、所定のアルゴリズムを用いて、前記三角形単位で決定される。
【００４６】
テクスチャエンジン回路１４３は、フルカラー方式の場合には、テクスチャバッファから読み出された（Ｒ，Ｇ，Ｂ，α）データを直接用いる。
一方、テクスチャエンジン回路１４３は、インデックスカラー方式の場合には、あらかじめ作成しておいたカラーインデックステーブルのデータを、テクスチャカラールックアップテーブル（ＣＬＵＴ）バッファより内蔵するＳＲＡＭ等で構成した一時保管バッファに転送しておいて、このカラールックアップテーブルを用いて、テクスチャバッファから読み出したカラーインデックスに対応する（Ｒ，Ｇ，Ｂ）データを得る。
たとえばカラールックアップテーブルがＳＲＡＭで構成された場合、カラーインデックスをＳＲＡＭのアドレスに入力すると、その出力には実際の（Ｒ，Ｇ，Ｂ）データが出てくるといった使い方となる。
【００４７】
ここで、いわゆるテクスチャマッピング処理について、図４および図５に関連付けてさらに説明する。
図４は、テクスチャエンジン回路１４３におけるテクスチャマッピング処理回路の構成例を示すブロック図であり、図５は、実際のテクスチャマッピング処理をイメージ的に示す図である。
【００４８】
このテクスチャマッピング処理回路は、ＤＤＡ回路１４３１，１４３２、テクスチャ座標算出回路（Ｄｉｖ）１４３３、ＭＩＰＭＡＰレベル算出回路１４３４、フィルタ回路１４３５、第１の合成回路（ＦＵＮＣ）１４３６、および第２の合成回路（ＦＯＧ）１４３７を有している。
【００４９】
このテクスチャマッピング処理回路においては、図５（Ａ）に示すように、ＤＤＡ回路１４３１，１４３２において、三角形の内部で線形補間されたテクスチャの同時座標ｓ、ｔ、ｑを用いて、デカルト座標でのテクスチャの実際のアドレスに変換する（ｑでの除算）。
さらにＭＩＰＭＡＰ等を行う場合は、ＭＩＰＭＡＰレベル算出回路１４３４においてＭＩＰＭＡＰのレベルの算出を行う。そして、図５（Ｂ）に示すように、テクスチャ座標算出回路１４３３においてテクスチャ座標の算出を行う。
また、フィルタ回路１４３５において、グラフィックスメモリ１４６に含まれるテクスチャバッファからそれぞれのレベルのテクスチャデータを読み出し、そのまま使うポイントサンプリング（Point Sampling）または、bi-Linea（４近傍）補間、Tri-Linea 補間等を行う。
そこで得られたテクスチャカラーに対して次の処理を行う。すなわち、第１の合成回路１４３６において、入力された物体カラーとテクスチャカラーを合成し、さらに第２の合成回路１４３７でそれにフォグカラーを合成して、最終的に描画するピクセルのカラーを決定する。
【００５０】
ＶＱ（ベクトル量子化）回路１４４は、通常の処理モードの場合には、テクスチャエンジン回路１４３によるピクセルデータＳ１４３をメモリＩ／Ｆ回路１３５に供給し、メモリＩ／Ｆ回路１４５によりグラフィックスメモリ１４６から読み出された（Ｒ，Ｇ，Ｂ，α）データ等をテクスチャエンジン回路１４３に供給する。
【００５１】
ＶＱ回路１４４は、ＶＱ圧縮テクスチャを使うブロック処理モードとしてのＶＱモードに対応すべく、まず、前処理として、たとえば上位装置側で用意されたテクスチャ用の画像を、処理単位が複数ピクセルのブロック（たとえば２×２、４×４）を一つのベクトルとみなして、後で詳述するようなエンコード処理を行って圧縮し、メモリＩ／Ｆ回路１４５を介してグラフィックスメモリ１４６に格納する。
エンコード処理の構成要素としては、ルックアップテーブルに相当するコードブック、およびコードブックの要素を指したブロック毎に設定されるインデックスを含み、ＶＱ回路１４４は、コードブックおよびインデックスデータを含む圧縮データをメモリＩ／Ｆ回路１４５を介してグラフィックスメモリ１４６に格納する。
【００５２】
そして、ＶＱ回路１４４は、キャッシュメモリを含み、ＶＱモード時に、メモリＩ／Ｆ回路１４５を介してＶＱ圧縮テクスチャデータを読み出して、以下に詳述するデコード処理を行って、デコード後のテクスチャデータに基づき、グラフィックス処理を行う。
すなわち、（ｓ，ｔ）データに対応したテクスチャアドレスに記憶された（Ｒ，Ｇ，Ｂ，α）データを得、読み出した（Ｒ，Ｇ，Ｂ，α）データの（Ｒ，Ｇ，Ｂ）データと、前段のトライアングルＤＤＡ回路１４２からのＤＤＡデータＳ１４２に含まれる（Ｒ，Ｇ，Ｂ）データとを、読み出したαデータが示す割合で混合し（それぞれ掛け合わせるなどして）、ピクセルデータ（テクセルデータ）Ｓ１４４を生成する。
ＶＱ回路１４４は、このピクセルデータＳ１４４をピクセルのカラー値としてメモリＩ／Ｆ回路回路１４５に出力する。
【００５３】
ここで、まずＶＱ圧縮テクスチャを使うＶＱモードに対応したエンコード処理の基本概念および具体的な処理について説明する。
【００５４】
画像データのエンコードは、デコード時にコードブックがキャッシュ内に収まっている必要があることから、コードブックの容量が大きいことは好ましくない。
そこで、本実施形態では、基本的には一つのテクスチャを複数領域に分割してエンコードする。これにより、一つの領域当たりのコードブックは小さくできる。
しかし、境界付近でバイリニアフィルタ（４近傍フィルタ）をかけると、最悪で４領域のコードブックが必要となってしまう。
これでは、分割した意味がないことから、境界付近で使用するエントリは隣接領域のコードブックにも持たせるようにエンコードする。
【００５５】
次に、具体的なエンコード処理について説明する。
【００５６】
図６は、一つのテクスチャを複数領域に分割してエンコードする場合のコードブックの持ち方、およびエンコードの手順を説明するための図である。
図６の例では、一つのテクスチャを３×３の９個の領域ＤＶ１〜ＤＶ９に分割した場合である。
【００５７】
コードブックは、破線で分割した９個の各分割領域ＤＶ１〜ＤＶ９単位で保持する。
そして、４つの分割領域でコードブックエントリが共有されるＡ部（右上がりのハッチングを施した部分）ＲＧＮＡ１〜ＲＧＮＡ４、２つの分割領域でコードブックエントリが共有されるＢ部（左上がりのハッチングを施した部分）ＲＧＮＢ１〜ＲＧＮＢ１２および残りのＣ部（空白の部分）に区分けされている。
【００５８】
最小で４ブロックのＡ部ＲＧＮＡ１で使われているエントリは、隣接した４つの分割領域ＤＶ１，ＤＶ２，ＤＶ４，ＤＶ５で共有されている。
Ａ部ＲＧＮＡ２で使われているエントリは、隣接した４つの分割領域ＤＶ３，ＤＶ３，ＤＶ５，ＤＶ６で共有されている。
Ａ部ＲＧＮＡ３で使われているエントリは、隣接した４つの分割領域ＤＶ４，ＤＶ５，ＤＶ７，ＤＶ８で共有されている。
Ａ部ＲＧＮＡ４で使われているエントリは、隣接した４つの分割領域ＤＶ５，ＤＶ６，ＤＶ８，ＤＶ９で共有されている。
【００５９】
Ｂ部ＲＧＮＢ１で使われているエントリは、隣接した２つの分割領域ＤＶ１とＤＶ２で共有されている。
Ｂ部ＲＧＮＢ２で使われているエントリは、隣接した２つの分割領域ＤＶ２とＤＶ３で共有されている。
Ｂ部ＲＧＮＢ３で使われているエントリは、隣接した２つの分割領域ＤＶ４とＤＶ５で共有されている。
Ｂ部ＲＧＮＢ４で使われているエントリは、隣接した２つの分割領域ＤＶ５とＤＶ６で共有されている。
Ｂ部ＲＧＮＢ５で使われているエントリは、隣接した２つの分割領域ＤＶ７とＤＶ８で共有されている。
Ｂ部ＲＧＮＢ６で使われているエントリは、隣接した２つの分割領域ＤＶ８とＤＶ９で共有されている。
Ｂ部ＲＧＮＢ７で使われているエントリは、隣接した２つの分割領域ＤＶ１とＤＶ４で共有されている。
Ｂ部ＲＧＮＢ８で使われているエントリは、隣接した２つの分割領域ＤＶ２とＤＶ５で共有されている。
Ｂ部ＲＧＮＢ９で使われているエントリは、隣接した２つの分割領域ＤＶ３とＤＶ６で共有されている。
Ｂ部ＲＧＮＢ１０で使われているエントリは、隣接した２つの分割領域ＤＶ４とＤＶ７で共有されている。
Ｂ部ＲＧＮＢ１１で使われているエントリは、隣接した２つの分割領域ＤＶ５とＤＶ８で共有されている。
Ｂ部ＲＧＮＢ１２で使われているエントリは、隣接した２つの分割領域ＤＶ６とＤＶ９で共有されている。
【００６０】
ここで、エンコードに際しては、各分割領域ＤＶ１〜ＤＶ９で合計ｎエントリを使い、そのうち、Ａ部分でａエントリ、Ｂ部分でｂエントリを使うとする。
【００６１】
図７は、本実施形態に係るエンコード処理を説明するためのフローチャートである。
【００６２】
まず、ステップＳＴ１において、Ａ部分をａエントリでエンコード（圧縮）する）。
ステップＳＴ２において、生成したａエントリを隣接するＢ部分のコードブックにコピーする。
次に、ステップＳＴ３において、Ｂ部分をｂエントリでエンコード（圧縮）する。この内訳は、ａ×（隣接しているＡ部分の数、図６の例では１〜２）＋α（新エントリ）である。
ステップＳＴ４において、生成したｂエントリを隣接するＣ部分のコードブックにコピーする。
次に、ステップＳＴ５において、Ｃ部分をｎエントリでエンコード（圧縮）する。この内訳は、ｂ×（隣接しているＢ部分の数、図６の例では２〜４）−ａ×（隣接しているＡ部分の数、図６の例では１〜４）＋α（新エントリ）である。
【００６３】
なお、各部のエンコード方式として、階層型クラスタリング、再起分割、ＬＢＧ等、任意の方式を採用可能である。
【００６４】
図８は、階層型クラスタリングの処理のフローチャートを示す図である。
ここでは、たとえば一つのブロックを一つのベクトルとみなす。複数ピクセル（たとえば４個）の２×２のブロックでそれぞれＲＧＢαの４要素を持つ場合、１６次元のベクトルとなる。
【００６５】
本階層型クラスタリングにおいては、コードブックを生成し、インデックスマップを生成する。
なお、インデックスマップとは、各ブロックがコードブックのどのエントリを参照しているかを示すインデックスである。
【００６６】
まず、コードブックを生成するに当たって、ステップＳＴ１１において、要素ｉを定義済みエントリの数に設定する。
なお、ベクトルの集合の初期値は、対象領域を構成する各ブロック＋定義済みのベクトルである。
定義済みベクトルは、変更不可のベクトルで、共有部分用として前のフェーズで定義したベクトルをいう。
【００６７】
次に、ステップＳＴ１２において、ベクトルを一つ減らし、ステップＳＴ１３で処理要素を一つ進める。
次に、ステップＳＴ１４において、処理要素ｉがエントリ数以下であるか否かの判別を行う。
以上の処理を、ステップＳＴ１４において、処理要素ｉがエントリ数に達したと判別されるまで、繰り返し行って、上述各分割領域ＤＶ１〜ＤＶ９に対するコードブックを生成する。
全てのコードブックを生成した後、ステップＳＴ１５において、対象領域を構成する各ブロックについても最も距離の小さいコードブックエントリを求め、インデックスマップを生成する。
【００６８】
なお、ベクトルの距離は、各要素の差の２乗の和の平方根により求まる。
実際には、順番さえ分かっていればよいことから、次式のように平方根は省略して、各ベクトルの距離の大小を比較する。この値の誤差を２乗和という。
【００６９】
【数１】
Σ（Ｖ１〔ｉ〕−Ｖ２〔ｉ〕）2                     …（１）
【００７０】
本実施形態に係るエンコード処理において、ベクトルを削除していくことによりＶＱ圧縮処理を行う。
【００７１】
図９は、本実施形態に係るエンコード処理においてＶＱ圧縮処理を行うためにベクトルを削除する手順を説明するためのフローチャートである。
なお、ｖｅｃ〔ｉ〕は置換前のベクトル１の処理要素、ｖｅｃ〔ｊ〕は置換前のベクトル２の処理要素をそれぞれ示している。
【００７２】
ステップＳＴ２１において、処理要素ｉ，ｊをそれぞれ０に初期化する。
ステップＳＴ２１において、ｖｅｃ〔ｉ〕を置換前のベクトル１、ｖｅｃ〔ｊ〕を置換前のベクトル２とする。
そして、ステップＳＴ２３において、ベクトル１およびベクトル２の両方が定義済みベクトルであるか否かの判別を行う。
ステップＳＴ２３において、両方が定義済みベクトルであると判別した場合には、ステップＳＴ２４において、要素ｊがＮ−１以下であるか否かの判別を行う。
ステップＳＴ２３において、ｊがＮ−１以下であると判別した場合には、ステップＳＴ２５において処理要素ｊを一つ進めて、ｉとｊが等しくなるまで（ＳＴ２６）、ステップＳＴ２４，ＳＴ２５の処理を繰り返す。
そして、ステップＳＴ２６において、ｉとｊが等しくなったと判別した場合には、ステップＳＴ２２の処理に戻る。
【００７３】
一方、ステップＳＴ２４において、ｊがＮ−１以上であると判別した場合には、ステップＳＴ２７において、要素ｉがＮ−１以下であるか否かの判別を行う。
ステップＳＴ２７において、ｉがＮ−１以下であると判別した場合には、ステップＳＴ２８において処理要素ｊを一つ進めて、ｊを０にリセットとして、ステップＳＴ２２の処理に戻る。
【００７４】
ステップＳＴ２３において、ベクトル１およびベクトル２の両方が定義済みベクトルでないと判別した場合には、ステップＳＴ２９において、片方が定義済みベクトルであるか否かの判別を行う。
ステップＳＴ２９において、片方が定義済みベクトルであると判別した場合には、ステップＳＴ３０において、定義済みでない方のベクトルが置換後のベクトル置換による誤差の２乗和を計算し、ステップＳＴ２４の処理に移行する。
【００７５】
一方、ステップＳＴ２９において、片方が定義済みベクトルでないと判別した場合には、ステップＳＴ３１において、ペアの重心ベクトルが置換後のベクトル置換による誤差の２乗和を計算し、ステップＳＴ２４の処理に移行する。
ここで、重心ベクトルとは入力ベクトルの平均である。ただし、元からあったベクトルでななく、ペアを置き換えたベクトルであった場合、元になったベクトルの個数分重み付けする。
たとえば、ＲがＰ，Ｑの重心ベクトル、ＳがＰ，Ｒの重心ベクトルであるとすると、Ｒ，Ｓは次式のように求められる。
【００７６】
【数２】
Ｒ＝（Ｐ＋Ｑ）／２
Ｓ＝（Ｐ＋２Ｒ）／３＝（２Ｐ＋Ｑ）／３
【００７７】
そして、ステップＳＴ２７において、ｉがＮ−１以上になったと判別した場合、ステップＳＴ３２において、置換による誤差の２乗和が最も小さくなるペアの置換を行う。
以上のようにして、ベクトルの削減を行う。
【００７８】
次に、具体的なエンコード例を図１０〜図１４に関連付けて説明する。
この例では、図１０に示すように、１６×１６テクスチャで３２ビットカラー、縦横２×２のそれぞれ２つのブロック（分割領域）ＤＶ１１，ＤＶ１２，ＤＶ１３，ＤＶ１４に分割している場合である。
ここでは、分割領域ＤＶ１１を例に挙げて説明する。
【００７９】
まず、Ａ部については、図１１に示すように、元画像ＩＭＡ１〜ＩＭＡ４について４エントリのまま圧縮をしない。したがって、コードブックＣＢに対してそのままインデックスＩＤＸ１，２，３，４が付与される。
【００８０】
Ｂ部については、図１２に示すように、分割領域ＤＶ１１とＤＶ１２との隣接領域ＲＧＮＢ１１の６つの元画像ＩＭＢ１〜ＩＭＢ６について１エントリ追加して６つのコードブックを生成し、それぞれにインデックスＩＤＸ１〜６が付与される。
また、分割領域ＤＶ１１とＤＶ１２との隣接領域ＲＧＮＢ１１の６つの元画像ＩＭＢについて１エントリ追加して、５つのコードブックＣＢを生成する。生成したコードブックのうち４つは、隣接領域ＲＧＮＢ１１の場合と同様のコードブックが生成され、これら４つのコードブックＣＢに対してはそれぞれにインデックスＩＤＸ１〜４が付与され、残りの一つのコードブックＣＢにインデックスＩＤＸ６が付与される。
すなわち、Ｂ部については、インデックスＩＤＸ１〜４はＡ部のインデックスと共用し、インデックスＩＤＸ５を隣接領域ＲＧＮＢ１１用に生成し、インデックスＩＤＸ６を隣接領域ＲＧＮＢ１２用に生成する。
【００８１】
Ｃ部については、図１３に示すように、９つの元画像ＩＭＣ１〜ＩＭＣ９についえ２エントリ追加して、８つのコードブックを生成し、それぞれにインデックスＩＤＸ１〜８が付与される。
すなわち、Ｃ部については、インデックスＩＤＸ１〜４はＡ部のインデックスと共用し、インデックスＩＤＸ５を隣接領域ＲＧＮＢ１１と共用し、インデックスＩＤＸ６を隣接領域ＲＧＮＢ１２と共用し、インデックスＩＤＸ７，８をＣ部用に生成する。
【００８２】
以上の処理により分割領域ＤＶ１１は、１６ブロックから８ブロック＋インデックスに圧縮される。
インデックスが１バイトであるとすると、２５６（８×８×４）バイトから１４４（８×４×４＋４×４）バイトに圧縮される。
以上のエンコード、すなわち圧縮の結果、図１４（Ａ）に示すようなデータが図１４（Ｂ）に示すようになる。
なお、この例では、テクスチャが小さいため圧縮率が小さいが、さらに大きなテクスチャであるならば圧縮率がさらに大きくなる。
【００８３】
次に、ＶＱ圧縮テクスチャに対するデコード処理について説明する。
このデコード処理に必要なものは、コードブック、インデックスマップ、領域ＩＤ、ブロックＩＤ、およびブロック内オフセットである。
コードブックに関しては、アクセスパターンに規則性がないため、全て読み込んでおく必要がある。
インデックスマップは、上述したように、各ブロックがコードブックのどのエントリを参照しているかを示すインデックスであり、アクセスパターンは通常のテクスチャとほぼ同様である。ブロック単位になっている分、より再利用性が高い。また、インデックスマップは、キャッシュを使ってアクセスする。このキャッシュは、非圧縮時は通常の処理用キャッシュとして使用することが可能である。
また、本実施形態では、領域ＩＤ、ブロックＩＤ、およびブロック内オフセットはテクスチャ座標から算出する。
【００８４】
次に、ＶＱ回路１４４におけるＶＱデコード回路の具体的な構成および機能についてさらに詳細に説明する。
【００８５】
図１５は、本実施形態に係るＶＱデコード回路の具体的な構成例を示すブロック図である。
【００８６】
本ＶＱデコード回路１４４Ａは、図１５に示すように、インタフェース（Ｉ／Ｆ）回路１４４１、ＩＤ算出回路１４４２、コードブック設定回路１４４３、インデックスキャッシュ１４４４、コードブックバッファ１４４５、およびテクセル出力回路１４４６を有している。
【００８７】
Ｉ／Ｆ回路１４４１は、メモリＩ／Ｆ回路１４５とのデータの授受、具体的に、メモリＩ／Ｆ回路１４５を介してグラフィックスメモリ１４６からデコード処理のためのテクスチャ座標（ｕ，ｖ）をＩＤ算出回路１４４２に供給し、インデックスデータをインデックスキャッシュ１４４３に供給し、コードブックデータをコードブックバッファ１４４５に供給し、コードブック設定回路１４４３のコードブック読み込みリクエスト、あるいはテクセル出力回路１４４６によるテクセルをメモリＩ／Ｆ回路１４５に出力する。
【００８８】
ＩＤ算出回路１４４２は、Ｉ／Ｆ回路１４４１を介してメモリＩ／Ｆ回路１４５によりグラフィックスメモリ１４６から読み出されたテクスチャ座標（ｕ，ｖ）、１領域当たりのブロック数、ブロックサイズに基づいて、領域ＩＤ、ブロックＩＤ、およびブロック内オフセットを算出し、算出した各ＩＤデータＳ１４４２をコードブック設定回路１４４３およびインデックスキャッシュ１４４４に出力する。
【００８９】
図１６は、ＩＤ算出回路１４４２の具体的な処理を説明するためのフローチャートである。
図１６において、ｕ’，ｖ’はブロックの数、ａｒｅａ ｕ，ａｒｅａ ｖは領域ＩＤ、ｂｌｏｃｋ ｕ，ｂｌｏｃｋ ｖはブロックＩＤ、ｏｆｆｓｅｔ ｕ，ｏｆｆｓｅｔ ｖはオフセットをそれぞれ示している。
また、演算は全て整数演算であり、％は剰余を示している。
【００９０】
ＩＤ算出回路１４４２は、まず、ステップＳＴ３１において、テクスチャ座標（ｕ，ｖ）、１領域当たりのブロック数（横：ａｗ，縦：ａｈ）、ブロックサイズ（横：ｂｗ，縦：ｂｈ）を入力する。
【００９１】
次に、ステップＳ３２において、テクスチャ座標ｕを横方向のブロックサイズｂｗで除算することにより、横方向のブロックの数ｕ’を求める。同様に、テクスチャ座標ｖを縦方向のブロックサイズｂｈで除算することにより、縦方向のブロックの数ｖ’を求める。
また、テクスチャ座標ｕを横方向のブロックサイズｂｗで除算し、商をｕ’，余りを横方向のオフセットｏｆｆｓｅｔ ｕとする。同様に、テクスチャ座標ｖを縦方向のブロックサイズｂｈで除算し、商をｖ’，余りを横方向のオフセットｏｆｆｓｅｔ ｖとする。
【００９２】
次に、ステップＳＴ３３において、ステップＳＴ３２で求めた横方向のブロック数ｕ’を横方向の１領域当たりのブロック数ａｗで除算し、その商として、横方向の領域ＩＤであるａｒｅａ ｕを求める。同様に、ステップＳＴ３２で求めた縦方向のブロック数ｖ’を縦方向の１領域当たりのブロック数ａｈで除算し、その商として、縦方向の領域ＩＤであるａｒｅａ ｖを求める。
また、ステップＳＴ３２で求めた横方向のブロック数ｕ’を横方向の１領域当たりのブロック数ａｗで除算し、その余りを横方向のブロックＩＤであるｂｌｏｃｋ ｕとする。同様に、ステップＳＴ３２で求めた縦方向のブロック数ｖ’を縦方向の１領域当たりのブロック数ａｈで除算し、その余りを縦方向のブロックＩＤであるｂｌｏｃｋ ｖとする。
【００９３】
たとえば、１領域当たりのブロック数ａｗ＝ａｈ＝１２８、ブロックサイズｂｗ＝ｂｈ＝２の場合、座標の下位１ビットがオフセット、次の７ビットがブロックＩＤ、それより上位のビットが領域ＩＤとなる。
【００９４】
なお、１領域当たりのブロック数とブロックサイズが共に２のべき乗の場合、除算や剰余算がビットマスクで済むので、実際には、それに対応した制限を設けることが望ましい。
【００９５】
コードブック設定回路１４４３は、ＩＤ算出回路１４４２による各ＩＤデータＳ１４４２を受けて、コードブックバッファ１４４５に必要なコードブックが読み込まれているか否かの判別を行い、読み込まれていない場合には、コードブック読み込みリクエストＣＲＲＱをＩ／Ｆ回路１４４１を介してメモリＩ／Ｆ回路１４５に出力する。
【００９６】
図１７は、コードブック設定回路１４４３の具体的な処理を説明するためのフローチャートである。
【００９７】
コードブック設定回路１４４３は、ＩＤ算出回路１４４２による各ＩＤデータＳ１４４２を受けて、まず、ステップＳＴ４１において、領域（ａｒｅａ ｕ，ａｒｅａ ｖ）のコードブックがコードブックバッファ１４４５に読み込まれているか否かの判別を行う。
ステップＳＴ４１において、読み込まれていると判別した場合には、コードブック読み込みリクエストＣＲＲＱの出力は行わない（何もしない）。
【００９８】
一方、ステップＳＴ４１において、読み込まれていないと判別した場合には、ステップＳＴ４２において、隣接領域のコードブックが読み込まれているか否かの判別を行う。
ステップＳＴ４２において、隣接領域のコードブックが読み込まれていると判別した場合には、ステップＳＴ４３において、ブロック（ｂｌｏｃｋ ｕ，ｂｌｏｃｋ ｖ）が領域（ａｒｅａ ｕ，ａｒｅａ ｖ）と共有されているか否かの判別を行う。
ステップＳＴ４３において、共有されていると判別した場合には、コードブック読み込みリクエストＣＲＲＱの出力は行わない（何もしない）。
【００９９】
一方、ステップＳＴ４２において隣接領域のコードブックが読み込まれていないと判別した場合、あるいはブロック（ｂｌｏｃｋ ｕ，ｂｌｏｃｋ ｖ）が領域（ａｒｅａ ｕ，ａｒｅａ ｖ）と共有されていないと判別した場合には、領域（ａｒｅａ ｕ，ａｒｅａ ｖ）のコードブックをコードブックバッファ１４４５に読み込むため、コードブック読み込みリクエストＣＲＲＱを出力する。
【０１００】
インデックスキャッシュ１４４４は、インデックスマップを保持しており、ＩＤ算出回路１４４２によるＩＤデータＳ１４４２が示す領域ＩＤ、ブロックＩＤに対応するインデックスデータＳ１４４４をコードブックバッファ１４４５に出力する。
なお、非圧縮テクスチャ処理の場合には、たとえばインデックスキャッシュ１４４４にテクセルがそのまま入力され、他の回路は素通りする。
【０１０１】
コードブックバッファ１４４５は、１領域分のコードブックを保持し、コードブック設定回路１４４３のコードブック読み出しリクエストＣＲＲＱに応答したメモリＩ／Ｆ回路１４５から転送された１領域分のコードブックで更新される。
コードブックバッファ１４４５は、インデックスキャッシュ１４４４によるインデックスデータＳ１４４４に対応するコードブックデータＳ１４４５をテクセル出力回路１４４６に出力する。
【０１０２】
テクセル出力回路１４４６は、コードブックバッファ１４４５によるコードブックデータＳ１４４５を受けて１ブロック分の出たを取得し、このブロックから１テクセルを抽出して、テクセルデータＳ１４４６をＩ／Ｆ回路１４４１を介してメモリＩ／Ｆ回路１４５に出力する。
【０１０３】
図１８は、テクセル出力回路１４４６の具体的な処理を説明するためのフローチャートである。
【０１０４】
テクセル出力回路１４４６は、コードブックバッファ１４４５によるコードブックデータＳ１４４５を受けて、まず、ステップＳＴ５１において、コードブックから１ブロック分のデータを取得する。
次に、ステップＳＴ５２において、ブロックのオフセット（ｏｆｆｓｅｔ ｕ，ｏｆｆｓｅｔ ｖ）を出力する。
【０１０５】
以下に、上述した構成を有するＶＱデコード回路の動作を、図１９のフローチャートに関連付けて説明する。
【０１０６】
まず、ＩＤ算出回路１４４２において、テクスチャ座標（ｕ，ｖ）から領域ＩＤ、ブロックＩＤ、およびオフセットを算出する（ＳＴ６１）。
次に、コードブック設定回路１４４３において、必要なコードブックが読み込まれていなければ、コードブック読み込みリクエストＣＲＲＱを出力して、必要なコードブックをコードブックバッファ１４４５に読み込ませる（ＳＴ６２）。
そして、インデックスキャッシュ１４４４において、ＩＤ算出回路１４４２によるＩＤデータＳ１４４２が示す領域ＩＤ、ブロックＩＤに対応するインデックスデータＳ１４４４をコードブックバッファ１４４５に出力する（ＳＴ６３）。
次に、コードブックバッファ１４４５において、インデックスに対応するブロックをテクセル出力回路１４４６に出力し（ＳＴ６４）、テクセル出力回路１４４６に出力において、ブロックから１テクセルを切り出して出力する（ＳＴ６５）。
【０１０７】
次に、具体的なデコード例を図２０に関連付けて説明する。
【０１０８】
たとえば、テクスチャ座標（７，１）でフィルタリング処理が無い場合、図２０（Ｂ）に示すようになる。
すなわち、横方向のテクスチャ座標（７）は２進数で表して「０１１１」となり、これは（０，３，１）となる。
同様に、縦方向のテクスチャ座標（１）は２進数で表して「０００１」となり、これは（０，０，１）となる。
そして、最上位１ビットが領域ＩＤ（０，０）となる。中間の２ビットがブロックＩＤ（３，０）となり、最下位１ビットがオフセット（１，１）となる。
【０１０９】
また、テクスチャ座標（７．３，７．６）でバイリニアフィルタリング処理を行う場合、図２０（Ｃ）に示すようになる。
すなわち、（７，７）、（７，８）、（８，７）、（８，８）の４点を補間する。ここで７は２進数で「０１１１」→（０，３，１）、８は２進数で「１０００」→（１，０，０）となる。
この場合、図２０（Ｃ）中に、Ｔ１〜Ｔ４で示すような４近傍のテクセルが必要となる。
したがって、４つの分割領域のどれかのコードブックがあれば４テクセルともデコードできる。
【０１１０】
メモリＩ／Ｆ回路１４５は、ＶＱ回路１４４を介してテクスチャエンジン回路１４３から入力したピクセルデータＳ１４３に対応するｚデータと、グラフィックスメモリ１４６に含まれるｚバッファに記憶されているｚデータとの比較を行い、入力したピクセルデータによって描画される画像が、前回、グラフィックスメモリ１４６（ディスプレイバッファ）に書き込まれた画像より、手前（視点側）に位置するか否かを判断し、手前に位置する場合には、画像データに対応するｚデータでｚバッファに記憶されたｚデータを更新する。
また、メモリＩ／Ｆ回路１４５は、（Ｒ，Ｇ，Ｂ）データをグラフィックスメモリ（ディスプレイバッファ）１４６に書き込む。
【０１１１】
さらに、メモリＩ／Ｆ回路１４５は、今から描画しようとしているピクセルにおけるテクスチャアドレスに対応したテクスチャデータを格納しているグラフィックスメモリ１４６のメモリブロックをそのテクスチャアドレスより算出し、そのメモリブロックにのみ読み出し要求を出すことにより、テクスチャデータを読み出し、ＶＱ回路１４４に出力する。
この場合、該当するテクスチャデータを保持していないメモリブロックにおいては、テクスチャデータの読み出しのためのアクセスが行われないため、描画により多くのアクセス時間を提供することが可能となっている。
【０１１２】
メモリＩ／Ｆ回路１４５は、描画においても同様に、今から描画しようとしているピクセルアドレスに対応するピクセルデータを格納しているグラフィックスメモリ１４６のメモリブロックに対して、該当アドレスからピクセルデータをモディファイ書き込みをするために読み出し、モディファイ後同じアドレスへ書き戻す。
隠れ面処理を行う場合には、やはり同じように今から描画しようとしているピクセルアドレスに対応する奥行きデータを格納しているメモリブロックに対して、該当アドレスから奥行きデータをモディファイ書き込みするため読み出し、必要ならばモディファイ後同じアドレスへ書き戻す。
【０１１３】
また、メモリＩ／Ｆ回路１４５は、テクスチャエンジン回路１４３あるいはＶＡ回路１４４からグラフィックスメモリ１４６に対する、生成されたテクスチャ座標データ（ｕ，ｖ）を含む読み出し要求を受けた場合には、グラフィックスメモリ１４６に記憶された（Ｒ，Ｇ，Ｂ）データを読み出す。
また、メモリＩ／Ｆ回路１４５は、ＣＲＴコントロール回路１４７から表示データを読み出す要求を受けた場合には、この要求に応じて、グラフィックスメモリ１４６（ディスプレイバッファ）から一定の固まり、たとえば８ピクセルあるいは１６ピクセル単位で表示データを読み出す。
【０１１４】
また、メモリＩ／Ｆ回路１４５は、たとえばＶＱ回路１４４からコードブック読み出しリクエストＣＲＲＱを受けた場合には、グラフィックスメモリ１４６から対応する１領域分のコードブックを読み出し、ＶＱ回路１４４に出力する。
そして、メモリＩ／Ｆ回路１４５は、たとえばＶＱモード時には、グラフィックスメモリ１４６からインデックスマップを読み出し、ＶＱ回路１４４のインデックスキャッシュ１４４４に出力する。
【０１１５】
メモリＩ／Ｆ回路１４５は、グラフィックスメモリ１４６へのアクセス（書き込みまたは読み出し）を行うが、書き込み経路と読み出し経路とが別経路として構成されている。
すなわち、書き込みの場合には書き込みアドレスＡＤＲＷと書き込みデータＤＴＷを書き込み系回路で処理されてグラフィックスメモリ１４６に書き込み、読み出しの場合には読み出し系回路で処理されてグラフィックスメモリ１４６から読み出す。
そして、メモリＩ／Ｆ回路１４５は、所定のインターリーブ方式のアドレッシングに基づいてグラフィックスメモリ１４６へのアクセスを、たとえば１６ピクセル単位で行う。
【０１１６】
このようなメモリとのデータのやりとりにおいては、それまでの処理を複数並行処理することで、描画性能を向上させることができる。
特に、トライアングルＤＤＡ部分とテクスチャエンジン部分を並列実効形式で、同じ回路を設ける（空間並列）か、または、パイプラインを細かく挿入する（時間並列）ことで、複数ピクセルの同時算出を行っている。
グラフィックスメモリ１４６のメモリブロックは表示領域において隣接した部分は、後述するように異なるメモリブロックとなるように配置してあるので、三角形のような平面を描画する場合には面で同時に処理できることになるため、それぞれのメモリブロックの動作確率は非常に高くなっている。
【０１１７】
グラフィックスメモリ１４６は、テクスチャバッファ、ディスプレイバッファ、ｚバッファおよびテクスチャＣＬＵＴ(Color Look Up Table) バッファとして機能する。
また、グラフィックスメモリ１４６は、同一機能を有する複数、たとえば４個のモジュールに分割されている。
【０１１８】
また、グラフィックスメモリ１４６には、より多くのテクスチャデータを格納するために、インデックスカラーにおけるインデックスと、そのためのカラールックアップテーブル値が、テクスチャＣＬＵＴバッファに格納されている。
インデックスおよびカラールックアップテーブル値は、上述したように、テクスチャ処理に使われる。
すなわち、通常はＲ，Ｇ，Ｂそれぞれ８ビットの合計２４ビットでテクスチャ要素を表現するが、それではデータ量が膨らむため、あらかじめ選んでおいたたとえば２５６色等の中から一つの色を選んで、そのデータをテクスチャ処理に使う。このことで２５６色であればそれぞれのテクスチャ要素は８ビットで表現できることになる。インデックスから実際のカラーへの変換テーブルは必要になるが、テクスチャの解像度が高くなるほど、よりコンパクトなテクスチャデータとすることが可能となる。
これにより、テクスチャデータの圧縮が可能となり、内蔵メモリの効率良い利用が可能となる。
【０１１９】
さらに、グラフィックスメモリ１４６には、描画と同時並行的に隠れ面処理を行うため、描画しようとしている物体の奥行き情報が格納されている。
なお、表示データと奥行きデータおよびテクスチャデータの格納方法としては、たとえばメモリブロックの所定の位置、たとえば先頭から連続して表示データが格納され、次に奥行きデータが格納され、残りの空いた領域に、テクスチャの種類毎に連続したアドレス空間でテクスチャデータが格納される。
図面に関連付けて概念的に説明すると、図２１（Ａ）〜（Ｃ）に示すように、いわゆるベースポインタ（ＢＰ）で示された位置から図中ＦＢで示す領域に、たとえば２４ビット幅で表示データと奥行きデータが格納され、残りの空いた領域である８ビット幅の領域に図中ＴＢで示すようにテクスチャデータが格納される。これらは表示データとテクスチャデータのユニファイドメモリ（Unified Memory）化ということになる。
これにより、テクスチャデータを効率よく格納できることになる。
【０１２０】
以上のように、ＤＤＡセットアップ回路１４１、トライアングルＤＤＡ回路１４２、テクスチャエンジン回路１４３、ＶＱ回路１４４、メモリＩ／Ｆ回路１４５等における所定を経て、最終的なメモリアクセスがピクセル(Pixel；PictureCell Element) という描画ピクセル単位になる。
【０１２１】
ＣＲＴコントロール回路１４７は、与えられた水平および垂直同期信号に同期して、図示しないＣＲＴに表示する表示アドレスを発生し、グラフィックスメモリ１４６に含まれるディスプレイバッファから表示データを読み出す要求をメモリＩ／Ｆ回路１４５に出力する。
この要求に応じて、メモリＩ／Ｆ回路１４５は、グラフィックスメモリ１４６（ディスプレイバッファ）から一定の固まりで表示データを読み出す。
ＣＲＴコントロール回路１４７は、グラフィックスメモリ１４６から読み出した表示データを記憶するたとえばＦＩＦＯ回路を内蔵し、一定の時間間隔で、ＲＧＢのインデックス値を発生する。
ＣＲＴコントロール回路１４７は、各インデックス値に対応するＲ，Ｇ，Ｂデータを記憶しており、発生したＲＧＢのインデックス値に対応するデジタル形式のＲ，Ｇ，Ｂデータを、図示しないＤ／Ａコンバータ(Digital/Analog Converter)に転送し、アナログ形式のＲ，Ｇ，Ｂデータを生成する。
ＣＲＴコントロール回路１４７は、この生成されたＲ，Ｇ，Ｂデータを図示しないＣＲＴに出力する。
【０１２２】
次に、図１の３次元グラフィックスシステムの上記構成による動作を、図２２のフローチャートに関連付けて説明する。
【０１２３】
３次元コンピュータグラフィックスシステム１０においては、グラフィックス描画等のデータは、メインプロセッサ１１のメインメモリ１２、あるいは外部からのグラフィックスデータを受けるＩ／Ｏインタフェース回路１３からメインバス１５を介してレンダリング回路１４に与えられる。
なお、必要に応じて、グラフィックス描画等のデータは、メインプロセッサ１１等において、座標変換、クリップ処理、ライティング処理等のジオメトリ処理が行われる（ＳＴ７１〜ＳＴ７３）。
ジオメトリ処理が終わったグラフィックスデータは、三角形の各３頂点の頂点座標ｘ，ｙ，ｚ、輝度値Ｒ，Ｇ，Ｂ、描画しようとしているピクセルと対応するテクスチャ座標ｓ，ｔ，ｑとからなるポリゴンレンダリングデータＳ１１となる。
このポリゴンレンダリングデータＳ１１は、レンダリング回路１４のＤＤＡセットアップ回路１４１に順々に転送される。
【０１２４】
ＤＤＡセットアップ回路１４１においては、ポリゴンレンダリングデータＳ１１に基づいて、三角形の辺と水平方向の差分などを示す変分データが生成される。
具体的には、開始点の値と終点の値、並びに、その間の距離を用いて、単位長さ移動した場合における、求めようとしている値の変化分である変分が算出され、変分データを含むセットアップデータＳ１４１としてトライアングルＤＤＡ回路１４２に出力される（ＳＴ７４）。
【０１２５】
トライアングルＤＤＡ回路１４２においては、変分データを含むセットアップデータＳ１４１を用いて、三角形内部の各ピクセルにおける線形補間された（ｚ，Ｒ，Ｇ，Ｂ，α，ｓ，ｔ，ｑ，Ｆ）データが算出される。
そして、この算出された（ｚ，Ｒ，Ｇ，Ｂ，α，ｓ，ｔ，ｑ，Ｆ）データと、三角形の各頂点の（ｘ，ｙ）データとが、ＤＤＡデータＳ１４２として、トライアングルＤＤＡ回路１４２からテクスチャエンジン回路１４３に出力される。
すなわち、トライアングルＤＤＡ１４２においては、ポリゴンの頂点毎に求められた画像パラメータに基づいてポリゴン内部に含まれるすべてのピクセルの画像パラメータ（ｚ，テクスチャ座標、カラーなど）を補間するラスタライズ処理が行われる（ＳＴ７５）。
そして、トライアングルＤＤＡ回路１４２において、各種データ（ｚ，テクスチャ座標、カラーなど）がラスタライズされた、ＤＤＡデータＳ１４２としてテクスチャエンジン回路１４３に出力される。
【０１２６】
テクスチャエンジン回路１４３においては、ＤＤＡデータＳ１４２が示す（ｓ，ｔ，ｑ）データについて、ｓデータをｑデータで除算する演算と、ｔデータをｑデータで除算する演算とが行われる。そして、除算結果「ｓ／ｑ」および「ｔ／ｑ」に、それぞれテクスチャサイズＵＳＩＺＥおよびＶＳＩＺＥが乗算され、テクスチャ座標データ（ｕ，ｖ）が生成される。
【０１２７】
次に、テクスチャエンジン回路１４３からメモリＩ／Ｆ回路１４５に対して生成されたテクスチャ座標データ（ｕ，ｖ）を含む読み出し要求が出力され、メモリＩ／Ｆ回路１４５を介して、グラフィックスメモリ１４６に記憶された（Ｒ，Ｇ，Ｂ，α）データが読み出される。
次に、テクスチャエンジン回路１４３において、読み出した（Ｒ，Ｇ，Ｂ）データの（Ｒ，Ｇ，Ｂ）データと、前段のトライアングルＤＤＡ回路１４２からのＤＤＡデータＳ１４２に含まれる（Ｒ，Ｇ，Ｂ）データとがαデータが示す割合で掛け合わされ、ピクセルデータとして生成される。
テクスチャマッピング処理後のピクセルデータは、テクスチャエンジン回路１４３からＶＱ回路１４４を介してメモリＩ／Ｆ回路１４５に出力される（ＳＴ７６）。
【０１２８】
そして、メモリＩ／Ｆ回路１４５において、テクスチャエンジン回路１４３から入力したピクセルデータに対応するｚデータと、ｚバッファに記憶されているｚデータとの比較が行われ、入力したピクセルデータＳ１４５によって描画される画像が、前回、ディスプレイバッファに書き込まれた画像より、手前（視点側）に位置するか否かが判断される。
判断の結果、手前に位置する場合には、画像データに対応するｚデータでｚバッファに記憶されたｚデータが更新される。
【０１２９】
次に、メモリＩ／Ｆ回路１４５において、（Ｒ，Ｇ，Ｂ）データがグラフィックスメモリ１４６のディスプレイバッファに書き込まれる。
これら書き込む（更新も含む）べきデータは、書き込み系回路を介し所定のメモリに対して並列的に書き込まれる（ＳＴ７７）。
【０１３０】
メモリＩ／Ｆ回路１４５においては、今から描画しようとしているピクセルにおけるテクスチャアドレスに対応したテクスチャを格納しているグラフィックスメモリ１４６のメモリブロックがそのテクスチャアドレスにより算出され、そのメモリブロックにのみ読みだし要求が出され、テクスチャデータが読み出される。
この場合、該当するテクスチャデータを保持していないメモリブロックにおいては、テクスチャ読み出しのためのアクセスが行われないため、描画により多くのアクセス時間を提供することが可能となっている。
【０１３１】
描画においても同様に、今から描画しようとしているピクセルアドレスに対応するピクセルデータを格納しているメモリブロックに対して、該当アドレスからピクセルデータがモディファイ書き込み(Modify Write)を行うために読み出され、モディファイ後、同じアドレスへ書き戻される。
【０１３２】
隠れ面処理を行う場合には、やはり同じように今から描画しようとしているピクセルアドレスに対応する奥行きデータを格納しているメモリブロックに対して、該当アドレスから奥行きデータがモディファイ書き込み(Modify Write)を行うために読み出され、必要ならばモディファイ後、同じアドレスへ書き戻される。
【０１３３】
そして、図示しないＣＲＴに画像を表示する場合には、メモリＩ／Ｆ回路１４５によりＣＲＴコントロール回路１４７から表示データが読み出される。
そして、ＣＲＴコントロール回路１４７において、与えられた水平垂直同期周波数に同期して、表示アドレスが発生され、メモリＩ／Ｆ回路１４５へ表示データ転送の要求が出される。
メモリＩ／Ｆ回路１４５では、その要求に従い、一定のまとまった固まりで、表示データがＣＲＴコントロール回路１４７に転送される。
ＣＲＴコントロール回路１４７では、図示しないディスプレイ用ＦＩＦＯ等にその表示データが貯えられ、一定の間隔でＲＧＢのインデックス値が生成される。
ＣＲＴコントロール回路１４７においては、内部にＲＧＢのインデックスに対するＲＧＢ値が記憶されていて、インデックス値に対するＲＧＢ値が図示しないＤ／Ａコンバータへ転送される。
そして、Ｄ／Ａコンバータでアナログ信号に変換されたＲＧＢ信号がＣＲＴへ転送される（ＳＴ７８）。
【０１３４】
以上の処理は非圧縮テクスチャ処理の場合であるが、ＶＱ圧縮テクスチャを行うＶＱモードの場合には、ステップＳＴ７６，ＳＴ７７の処理が以下のように行われる。
すなわち、ＶＱモード時には、前処理として一つのテクスチャを複数領域に分割してエンコードが行われる。そして、各分割領域に対するコードブックが生成される。このコードブックの生成は、分割領域の境界付近で使用するエントリは隣接領域のコードブックにも持たせるようにエンコードされる。
次いで、全てのコードブックが生成された後、対象領域を構成する各ブロックについても最も距離の小さいコードブックエントリが求られて、インデックスマップが生成される。
これら生成されたコードブックデータおよびインデックスマップデータは、メモリＩ／Ｆ回路１４５によりグラフィックスメモリ１４６に格納される。
【０１３５】
次に、ＶＱモード時には、ＩＤ算出回路１４４２において、テクスチャ座標（ｕ，ｖ）から領域ＩＤ、ブロックＩＤ、およびオフセットが算出され、ＩＤデータＳ１４４２がコードブック設定回路１４４３およびインデックスキャッシュ１４４４に出力される。
コードブック設定回路１４４３において、必要なコードブックが読み込まれているか否かの判別が行われ、読み込まれていなければ、コードブック読み込みリクエストＣＲＲＱが出力されて、メモリＩ／Ｆ回路１４５によるグラフィックスメモリ１４６から読み出されたコードブックがコードブックバッファ１４４５に読み込まれる。
そして、インデックスキャッシュ１４４４において、ＩＤ算出回路１４４２によるＩＤデータＳ１４４２が示す領域ＩＤ、ブロックＩＤに対応するインデックスデータＳ１４４４がコードブックバッファ１４４５に出力される。
コードブックバッファ１４４５において、インデックスに対応するブロックがテクセル出力回路１４４６に出力され、テクセル出力回路１４４６において、ブロックから１テクセルを切り出して出力される。
【０１３６】
以上説明したように、本実施形態によれば、前処理として一つのテクスチャを複数領域に分割し、各分割領域に対するコードブックを、分割領域の境界付近で使用するエントリは隣接領域のコードブックにも持たせるようにエンコードし、コードブックを生成した後、対象領域を構成する各ブロックについても最も距離の小さいコードブックエントリを求めて、インデックスマップを生成し、コードブックデータおよびインデックスマップデータを、メモリＩ／Ｆ回路１４５によりグラフィックスメモリ１４６に格納し、また、ＶＱモード時には、テクスチャ座標（ｕ，ｖ）から領域ＩＤ、ブロックＩＤ、およびオフセットを算出し、必要なコードブックが読み込まれていなければ、コードブック読み込みリクエストＣＲＲＱを出力して必要なコードブックを読み込み、算出した領域ＩＤ、ブロックＩＤに対応するインデックスデータを選択し、コードブックから選択したインデックスに対応するブロックを抽出し、ブロックから１テクセルを切り出すＶＱ回路１４４を設けたので、テクスチャデータを効率的に圧縮することができ、かつ、効率的に圧縮されたデータを効率的にデコードすることができ、ひいてはグラフィックスメモリの効率的な活用を実現することができる利点がある。
【０１３７】
なお、本実施形態では、ＶＱ回路１４４はテクスチャエンジン回路１４３と別個のものとして説明したが、ＶＱ回路１４４をテクスチャエンジン回路１４３に内蔵することも可能である。
【０１３８】
また、図１に示す３次元コンピュータグラフィックスシステム１０では、ポリゴンレンダリングデータを生成するジオメトリ処理を、メインプロセッサ１１で行う場合を例示したが、レンダリング回路１４で行う構成にしてもよい。
【０１３９】
【発明の効果】
以上説明したように、本発明によれば、テクスチャデータを効率的に圧縮することができ、かつ、効率的に圧縮されたデータを効率的にデコードすることができ、ひいてはグラフィックスメモリの効率的な活用を実現することができる利点がある。
【図面の簡単な説明】
【図１】本発明に係る画像処理装置としての３次元コンピュータグラフィックスシステムのシステム構成図である。
【図２】本実施形態に係るＤＤＡセットアップ回路の機能を説明するための図である。
【図３】本実施形態に係るＤＤＡセットアップ回路の構成例を示す図である。
【図４】本実施形態に係るテクスチャエンジン回路におけるテクスチャマッピング処理回路の構成例を示すブロック図である。
【図５】本実施形態に係るテクスチャエンジン回路における実際のテクスチャマッピング処理をイメージ的に示す図である。
【図６】一つのテクスチャを複数領域に分割してエンコードする場合のコードブックの持ち方、およびエンコードの手順を説明するための図である。
【図７】本実施形態に係るエンコード処理を説明するためのフローチャートである。
【図８】階層型クラスタリングの処理のフローチャートを示す図である。
【図９】本実施形態に係るエンコード処理においてＶＱ圧縮処理を行うためにベクトルを削除する手順を説明するためのフローチャートである。
【図１０】具体的なエンコード例を説明するための図である。
【図１１】４領域隣接のＡ部の具体的なエンコード例を説明するための図である。
【図１２】２領域隣接のＢ部の具体的なエンコード例を説明するための図である。
【図１３】Ｃ部の具体的なエンコード例を説明するための図である。
【図１４】エンコード結果を示す図である。
【図１５】本実施形態に係るＶＱデコード回路の具体的な構成例を示すブロック図である。
【図１６】図１５のＩＤ算出回路の具体的な処理を説明するためのフローチャートである。
【図１７】図１５のコードブック設定回路の具体的な処理を説明するためのフローチャートである。
【図１８】図１５のテクセル出力回路の具体的な処理を説明するためのフローチャートである。
【図１９】本実施形態に係るＶＱデコード回路の一連の処理手順を説明するためのフローチャートである。
【図２０】本実施形態に係るＶＱデコード回路の具体的なデコード例を説明するための図である。
【図２１】本実施形態に係るグラフィックスメモリへの表示データと奥行きデータおよびテクスチャデータの格納方法を概念的に説明するための図である。
【図２２】図１の３次元コンピュータグラフィックスシステムの全体の動作を説明するためのフローチャートである。
【符号の説明】
１０…３次元コンピュータグラフィックスシステム（画像処理装置）、１１…メインプロセッサ、１２…メインメモリ、１３…Ｉ／Ｏインタフェース回路、１４…レンダリング回路、１４１…ＤＤＡセットアップ回路、１４２…トライアングルＤＤＡ回路、１４３…テクスチャエンジン回路、１４４…ベクトル量子化（ＶＱ）回路、１４４Ａ…ＶＱデコード回路、１４４１…インタフェース（Ｉ／Ｆ）回路、１４４２…ＩＤ算出回路、１４４３…コードブック設定回路、１４４４…インデックスキャッシュ、１４４５…コードブックバッファ、１４４６…テクセル出力回路、１４５…メモリインタフェース（Ｉ／Ｆ）回路、１４６…グラフィックスメモリ、１４７…ＣＲＴコントロール回路。
【図１】
0004042462.tif 000002
【図２】
0004042462.tif 000003
【図３】
0004042462.tif 000004
【図４】
0004042462.tif 000005
【図５】
0004042462.tif 000006
【図６】
0004042462.tif 000007
【図７】
0004042462.tif 000008
【図８】
0004042462.tif 000009
【図９】
0004042462.tif 000010
【図１０】
0004042462.tif 000011
【図１１】
0004042462.tif 000012
【図１２】
0004042462.tif 000013
【図１３】
0004042462.tif 000014
【図１４】
0004042462.tif 000015
【図１５】
0004042462.tif 000016
【図１６】
0004042462.tif 000017
【図１７】
0004042462.tif 000018
【図１８】
0004042462.tif 000019
【図１９】
0004042462.tif 000020
【図２０】
0004042462.tif 000021
【図２１】
0004042462.tif 000022
【図２２】
0004042462.tif 000023