(57)【要約】【課題】  ポリゴンのソートを高速に行うことができる３次元画像描画装置およびソート処理方法を提供する。【解決手段】  ３次元画像描画装置は、ポリゴンについて画面奥行きの関数であるデプス値を含むソート用データを記憶するメモリ３０と、リード開始アドレス値用バッファ１４０に保持された開始アドレスとリード終了アドレス値用バッファ１５０に保持された終了アドレスに従い、メモリ３０からソート用データを読み出すソート用データリード制御回路１００と、読み出されたソート用データのデプス値を基準デプス値と比較するデプス値比較回路１２０と、メモリ３０から繰り返しソート用データが読み出されるとき、描画順序が決定されたソート用データに応じて、リード開始アドレスおよびリード終了アドレスを制御するリード開始アドレス判断回路１６０およびリード終了アドレス判断回路１７０とを有する。【選択図】    図６
2006285372.tif 000002
【特許請求の範囲】
【請求項１】
ポリゴンを画面奥側から画面手前または画面手前から画面奥側に向けてソートする機能を備えた３次元画像描画装置であって、
ポリゴンについて画面奥行きの関数であるデプス値を含むソート用データを記憶する記憶手段と、
記憶手段からソート用データを読み出す読み出し手段と、
読み出し手段により読み出されたソート用データのデプス値を基準デプス値と比較して描画順序を決定する比較手段と、
読み出し手段により繰り返しソート用データが読み出されるとき、描画順序が決定されたソート用データに応じて、ソート用データの読出しを制御する読み出し制御手段と、
を有する３次元画像描画装置。
【請求項２】
読み出し制御手段は、ソート用データの描画順序が決定されたソート用データを読み出し対象から除外するように読み出し手段を制御する、請求項１に記載の３次元画像描画装置。
【請求項３】
読み出し制御手段は、ソート用データの読み出し開始アドレスおよび読み出し終了アドレスを読み出し手段に供給する、請求項１または２に記載の３次元画像描画装置。
【請求項４】
読み出し制御手段は、描画順序が決定されたソート用データに応じて、読み出し開始アドレスおよび読み出し終了アドレスの少なくとも一方を更新する、請求項３に記載の３次元画像描画装置。
【請求項５】
読み出し手段は、ソート用データをブロック単位で読み出し、読み出し制御手段は、ブロック内に含まれるすべてのソート用データの描画順序が決定された場合に、当該ブロックを読み出し対象から除外するように読み出し手段を制御する、請求項１ないし４いずれか１つに記載の３次元画像描画装置。
【請求項６】
読み出し制御手段は、ブロックに含まれるすべてのソート用データの描画順序が決定されたか否かを判別するためのフラグ情報を保持し、当該フラグ情報に基づき読み出し手段の読み出しアドレスを制御する、請求項５に記載の３次元画像描画装置。
【請求項７】
記憶手段は、バースト読み出しが可能なメモリを含む、請求項１ないし６いずれか１つに記載の３次元画像描画装置。
【請求項８】
ポリゴンは、半透明ポリゴンである、請求項１ないし７いずれか１つに記載の３次元画像描画装置。
【請求項９】
ポリゴンを画面奥側から画面手前または画面手前から画面奥側に向けてソートするポリゴンのソート処理方法であって、
描画オブジェクトであるポリゴンについての画面奥行きの関数であるデプス値を含むソート用データを記憶装置に記憶するステップと、
記憶装置からソート用データを読み出すステップと、
読み出されたソート用データのデプス値を基準デプス値と比較して描画順序を決定するステップと、
記憶装置からソート用データを繰り返し読み出すとき、描画順序が決定されたソート用データに応じて、ソート用データの読み出しを制御するステップと、
を有するソート処理方法。
【請求項１０】
制御するステップは、記憶装置の読み出しアドレスを更新する、請求項９に記載のソート処理方法。
【請求項１１】
ソート用データはブロック単位で読み出され、ブロック内のすべてのソート用データの描画順序が決定されている場合には、当該ブロックが読み出し対象から除外されるように読み出しを制御する、請求項９に記載のソート処理方法。
【請求項１２】
読み出すステップは、読み出し開始アドレスから読み出し終了アドレスに従いソート用データを読み出し、制御するステップは、開始アドレスおよび終了アドレスの少なくとも一方を更新する、請求項１０ないし１１いずれか１つに記載のソート処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元画像を描画する３次元画像描画装置に関し、特に、半透明描画データ（半透明ポリゴン）をＺ方向にソートするＺソート処理技術に関する。
【０００２】
３Ｄグラフィックスで使用される「モデル」と呼ばれる立体物は、ポリゴンと呼ばれる複数の三角形で構成され、各頂点の３次元座標値(ｘ，ｙ,ｚ)により立体物と表される。一般に、図８に示すように、このモデルデータを構成する頂点の座標空間を「モデル座標」、モデルを配置する座標空間を「ワールド座標」、モニタに表示される絵を写すためのカメラを基準にした座標空間を「カメラ座標」、最終的なモニタ画面での座標空間を「スクリーン座標」と呼ぶ。
【０００３】
３次元空間上に配置されたモデルデータを、モニタ等の２次元画面に表示する際の基本的な３Ｄグラフィックス処理は、次のような順番で行われる。
１）モデルとカメラをワールド座標空間に配置する。
２）モデルデータの各頂点データ（モデル座標）をワールド座標に変換し、更にそれをカメラ座標に変換して、各頂点座標値がカメラから見た際の座標値になるようにする。
３）ワールド座標空間に設定された「ライト（光源）」の方向や色などにしたがって、モデル各頂点のライティング計算（明るさや色味の計算）を行う。
４）カメラ座標での各頂点座標をスクリーン座標に透視変換して、その座標値を描画回路に入力して描画処理を行う。
【０００４】
また、３次元グラフィックスでは、色付きガラスなどの向こう側が透けて見えるような物体を描画することがある。これを一般に、半透明描画と呼んでいる。半透明描画処理は、ガラスを描画する位置に、既にフレームバッファに格納されている背景の各ピクセルカラーデータを読み出し、その背景カラーとガラスカラーとを演算し、演算したカラーデータをフレームバッファに格納すれば良い。半透明の描画処理では、例えば、加算結果を１／２倍にする。ちなみに、半透明と呼ぶのは言葉的に判りやすいからで、実際のカラー演算割合は自由に指定することが可能であり、グラフィックス用語としては、「αブレンディング」（カラー演算割合パラメータをα値と呼ぶことから）と呼ばれる。
【０００５】
１つの画面の中で、背景のような「不透明描画」とガラスのような「半透明描画」を混合して行う場合は、最初に不透明なものだけを全て描画し、その描画終了後に半透明なものを画面奥側にあるものから順番に半透明処理しながら描画することになる。例えば、図９（ａ）に示すように、最初に山や太陽などの全ての不透明な背景を描画し、次に、図９（ｂ）、（ｃ）に示すように、画面の奥側から半透明ガラスをＡ、Ｃ、Ｂの順番で描画する。
【０００６】
上記のように、半透明描画処理では画面奥側にある描画オブジェクトから画面手前側に向かって順番に描画する必要があるため、描画処理する前に半透明描画オブジェクトを画面奥側から順番に並べ替えておく必要がある。上記の例では、半透明ガラスをＡ→Ｃ→Ｂの順に並べる。この処理は、画面に垂直な座標軸に当たるＺ座標値でソートすることから、通常「Ｚソート処理」と呼ばれている。
【０００７】
３Ｄグラフィックスにおける半透明オブジェクトは、上記のガラスのような平面物に限らず、図１０のような立体物となる。この立方体を半透明描画する場合は、ポリゴン単位でＺソート処理を行い、画面奥側のポリゴンから順番に半透明描画処理を行うことになる。
【０００８】
Ｚソート処理について、いくつかの技術が報告されている。特許文献１は、ポリゴン識別部で不透明ポリゴンデータと半透明ポリゴンデータとの識別を行い、Ｚソートされた半透明ポリゴンデータの描画に要する描画予想時間を演算し、描画予想時間から不透明ポリゴンと半透明ポリゴンとの描画の切り換え時間を演算し、不透明ポリゴンデータから透明ポリゴンデータへの切り替えを可能にしている。これにより、プログラム開発時間の短縮化を期し、１フレーム期間中で描画すべき半透明ポリゴンデータを欠落なく描画できる半透明描画生成装置を提供している。
【０００９】
特許文献２は、画像を構成するポリゴンを半透明なものと不透明なものとに区別し、不透明なポリゴンすべての描画が終了すると、半透明なポリゴンが奥方向から手前方向に向かう順番でＺバッファを使用して描画される。これにより、不透明なポリゴンと半透明なポリゴンとを含む画像の描画を高速化している。
【００１０】
特許文献３は、物陰に隠れて見えなくなるポリゴンを描画する無駄を省くために、各視点別に複数のポリゴンそれぞれについて見えるか否かを示した情報を用意し、描画処理時に、この情報を利用して、見えるポリゴンについてのみ描画するようにしている。
【００１１】
特許文献４は、オブジェクトデータから、視点位置を基準として定められる視界内に位置するオブジェクトデータを選定し、選定したオブジェクトデータをスクリーン上の投影画像となる画像データに透視変換し、変換された画像データをＺソートし、Ｚソートされた画像データ中、視点位置から所定距離以上離れた画像データを抽出し、数ドットずらした半透明な画像をテクスチャとする半透明ダミーポリゴンを生成し、半透明ダミーポリゴンを含む画像データにしたがって不鮮明なぼやけた状態の画像を描画する。これにより、３次元画像データを現実感のある画像として表示している。
【００１２】
特許文献５は、画像を構成しているオブジェクト毎に割り当てたメモインメモリ上の複数の順序テーブルに画像を複数に分割した各ブロックのＺ方向の情報をアドレスとして各ブロックの処理順序を示す順序データを書き込み、ＤＭＡコントローラにより複数の順序テーブル同士を段階的にＺソートすることによって描画データを作成する。これにより、物理的に分かれたオブジェクトが近い深さにあった場合にも、ポリゴン単位の干渉を排除して、画質の良好な描画データを生成することを可能にしている。
【００１３】
【特許文献１】特開２０００−２６８１９０号
【特許文献２】特開平１０−１１６１０号
【特許文献３】特開平９−４４６９７号
【特許文献４】特開２０００−９３６５４号
【特許文献５】特開平７−１１４６５４号
【発明の開示】
【発明が解決しようとする課題】
【００１４】
従来の３次元画像描画装置では、ソフトウエアまたはハードウエアを用いてＺソート処理を行っている。ソフトウエアによりＺソートを行う場合、描画内容に最も適したＺソート処理方法を提供できる自由度があるが、その反面、処理の最適化を図るアルゴリズムの設計には大きなコストを要する。また、演算結果を格納する比較的大きなメモリ容量を必要とし、かつメモリへのアクセス頻度も増加するため、Ｚソート処理時間の高速化には限界がある。
【００１５】
一方、ハードウエアによるＺソート専用回路を搭載した場合、頂点座標演算から描画処理までの処理を全てハードウエア処理で実行できるため、シンプルな構成を実現することが可能であり、かつＣＰＵ負荷を軽減することができ、システムの処理性能が向上する。しかし、ポリゴン毎のＺ座標値を1つずつ比較してソートする方法のＺソート回路とした場合、どのような描画内容にも対応可能であり、かつソート回路規模を小さくできる利点がある一方で、ソートするポリゴン数が増加すると、その二乗の回数でＺ座標値比較を行うこととなり、ソート処理に多くの時間を要してしまい、Ｚソート処理を高速化することが難しいという課題がある。
【００１６】
本発明は、上記従来の課題を解決するために成されたもので、ポリゴンのソートを高速に行うことができる３次元画像描画装置およびソート処理方法を提供することを目的とする。
さらに本発明は、ハードウエアによるＺソート処理回路を設けることで、頂点座標演算から描画処理までをハードウエアにより処理することができる３次元画像描画装置を提供することを目的とする。
さらに本発明は、Ｚソート処理回路を設けることで、他のハードウエア資源への負担を軽減し、３次元グラフィックスの高速描画を可能とする３次元画像描画装置を提供することを目的とする。
【課題を解決するための手段】
【００１７】
本発明に係る３次元画像描画装置は、ポリゴンを画面奥側から画面手前または画面手前から画面奥側に向けてソートする機能を備えた、以下の構成を含む。ポリゴンについて画面奥行きの関数であるデプス値を含むソート用データを記憶する記憶手段と、記憶手段からソート用データを読み出す読み出し手段と、読み出し手段により読み出されたソート用データのデプス値を基準デプス値と比較して描画順序を決定する比較手段と、読み出し手段により繰り返しソート用データが読み出されるとき、描画順序が決定されたソート用データに応じて、ソート用データの読出しを制御する読み出し制御手段とを含む。
【００１８】
好ましくは読み出し制御手段は、ソート用データの描画順序が決定されたソート用データを読み出し対象から除外するように読み出し手段を制御する。好ましくは読み出し制御手段は、ソート用データの読み出し開始アドレスおよび読み出し終了アドレスを読み出し手段に供給し、描画順序が決定されたソート用データに応じて、読み出し開始アドレスおよび読み出し終了アドレスの少なくとも一方を更新する。
【００１９】
さらに読み出し手段は、ソート用データをブロック単位で読み出し、読み出し制御手段は、ブロック内に含まれるすべてのソート用データの描画順序が決定された場合に、当該ブロックを読み出し対象から除外するように読み出し手段を制御する。また読み出し制御手段は、ブロックに含まれるすべてのソート用データの描画順序が決定されたか否かを判別するためのフラグ情報を保持し、当該フラグ情報に基づき読み出し手段の読み出しアドレスを制御するようにしてもよい。
【００２０】
好ましくは、ソートされるポリゴンは、半透明ポリゴンである。また、ソートをより高速に行うために、記憶手段には同期型メモリ、例えばＤＤＲ−ＳＤＲＡＭが用い、バーストリードによりソート用データブロックの読み出しが行われる。また、ポリゴンのデプス値は、ポリゴンの頂点座標のＺ軸方向の平均値、最小値または最大値などを用いることができ、基準デプス値は、比較される複数のポリゴンの中から選択されたポリゴンのデプス値である。
【００２１】
さらに本発明に係るポリゴンを画面奥側から画面手前または画面手前から画面奥側に向けてソートするポリゴンのソート処理方法は、描画オブジェクトであるポリゴンについての画面奥行きの関数であるデプス値を含むソート用データを記憶装置に記憶するステップと、記憶装置からソート用データを読み出すステップと、読み出されたソート用データのデプス値を基準デプス値と比較して描画順序を決定するステップと、記憶装置からソート用データを繰り返し読み出すとき、描画順序が決定されたソート用データに応じて、ソート用データの読み出しを制御するステップとを有する。
【００２２】
好ましくは、ソート用データはブロック単位で読み出され、ブロック内のすべてのソート用データの描画順序が決定されている場合には、当該ブロックが読み出し対象から除外されるように読み出しを制御する。さらに好ましくは読み出すステップは、開始アドレスから終了アドレスに従いソート用データを読み出し、制御するステップは、開始アドレスおよび終了アドレスの少なくとも一方を制御する。
【発明の効果】
【００２３】
本発明に係る３次元画像描画装置によれば、記憶手段に記憶されたソート用データを繰り返し読み出すとき、描画順序が決定されたソート用データに応じて、ソート用データを読み出すアドレスを制御するようにしたので、効率よくソート用データを読み出し、ソート用データの比較および描画順序を決定することが可能となり、ポリゴンのソート処理の高速化を図ることができる。
【発明を実施するための最良の形態】
【００２４】
本発明に係る３次元画像描画装置について図面を参照して詳細に説明する。
【実施例】
【００２５】
図１は、本発明の実施例に係る３次元画像描画装置のシステム構成を示すブロック図である。３次元画像描画装置１は、システム全体を制御するＣＰＵ１０、２次元または３次元のグラフィック描画を制御する描画用回路２０、プログラムや画像データ等を格納するメモリ３０、メモリ３０へのアクセスを制御するメモリコントローラ４０、メモリに格納された画像データをモニタに出力する画像表示用回路５０、外部ポートに接続されプログラム等のデータを格納する外部メモリ６０、内部バスや外部ポート（シリアルＩ／Ｆ）の制御を行う周辺制御回路７０、画像表示用回路５０から出力された画像データを表示するモニタ８０を含んで構成される。
【００２６】
描画用回路２０はさらに、モデルの各頂点座標値の３次元演算（回転、拡張、移動など）や光源計算などを行って、スクリーン座標空間での頂点データを求めるジオメトリ回路２２と、描画最小単位である三角形や四角形のポリゴンデータのＺソート処理やクリッピング処理を行うＺソート処理回路２４と、描画リストにしたがってグラフィック描画を行うレンダリング回路２６を含んでいる。本実施例では、描画用回路２０をハードウエアにより構成することで、モデルの座標演算、Ｚソート処理、および描画処理をハードウエアにより実現することができる。
【００２７】
図２は、３次元画像描画装置における描画処理の基本的なフローを示す図である。ＣＰＵ１０は、メモリ３０内のプログラムデータ３１および３次元モデルデータ３２等にしたがって、モデルの回転や移動などの基となる各パラメータを計算する（ステップａ）。ＣＰＵ１０は、計算したモデルデータの各パラメータにしたがって、ジオメトリ回路２２が受け付ける形式のジオメトリ回路用描画リストデータ３３を生成し、これをメモリ内に格納する（ステップｂ）。
【００２８】
ジオメトリ回路２２は、メモリ内のジオメトリ回路用描画リストデータ３３を読み込みながら決められた頂点演算処理を行い、その結果をソート処理回路２４に送る（ステップｃ）。
【００２９】
ソート処理回路２４は、ジオメトリ回路２２から受け取った頂点演算された描画リストデータ３３にしたがって、Ｚソート処理やクリッピング処理を行い、そしてレンダリング回路２６が受け付ける形式のレンダリング回路用描画リストデータ３４を生成し、これをメモリ内に格納する（ステップｄ）。
【００３０】
レンダリング回路２６は、メモリ内のレンダリング回路用描画リストデータ３４を読み込みながら描画処理用ピクセルパラメータを計算する（ステップｅ）。描画処理用ピクセルパラメータとは、描画ピクセルのテクスチャ座標値、描画ピクセルのデプス値（すなわち画面奥行き方向座標値：Ｚ値）、および描画ピクセルのフレームバッファ座標値などのピクセル描画に必要なパラメータである。
【００３１】
レンダリング回路２６は、描画ピクセルのテクスチャ座標値にしたがって各ピクセルに対応したテクスチャデータ３５をメモリから読み込んで処理し、描画ピクセルのカラーデータを求め（ステップｆ）、さらに、描画ピクセルのデプス値とデプスバッファ３６から読み込んだデプス値の比較結果にしたがってピクセル描画を行うかどうか判断する（ステップｇ）。
【００３２】
レンダリング回路２６はさらに、αブレンディング処理指定にしたがって描画ピクセルのカラーデータを計算し、描画ピクセルのフレームバッファ３７の座標位置にデータを格納する（ステップｈ）。
【００３３】
次に、本実施例のソート処理回路２４の詳細について説明する。立体物を構成するポリゴンをＺソートする際に比較するＺ座標値は、ポリゴン各頂点（三角形の場合は３頂点）のＺ座標値の「平均値」を用いることができる。但し、ポリゴンのＺ座標値の最小値または最大値を用いてもよい。
【００３４】
比較に使用する値は、画面に垂直な座標軸に関連する奥行き方向の値であれば良く、「Ｚ座標値」には限らない。そこで、本明細書では、以降の説明において、比較に使用する値を総称として「デプス値」と呼ぶことにする。
【００３５】
ソート処理回路２４におけるＺソート処理の概要は、次の通りである。
１）入力された半透明描画オブジェクトをポリゴン単位に分割し、各ポリゴンのデプス平均値を求める。
２）各ポリゴンのデプス平均値を大小比較して、画面奥側から順番に並べ替える。デプス平均値が等しい場合は、予め決められた法則に則って順番を決める。通常は、処理する順番が早い方を画面奥側となるようにする。
【００３６】
一般に、頂点ｘｙｚ座標値やデプス値は、「１６ｂｉｔ／３２ｂｉｔ固定小数点数」または「３２ｂｉｔ浮動小数点数」を用いて表される。最近の３次元コンピュータグラフィックスでは、数値としての表現可能範囲が大きい３２ビット浮動小数点数が使用されることが多い。以下の表は、ＩＥＥＥによる国際標準規格により定められた３２ビット浮動小数点数のデータ構成を示している。
【００３７】
【表１】
2006285372.tif 000003
【００３８】
図３は、Ｚソート処理のフローを示す図である。ここでは、デプス値を画面手前より画面奥側の方が小さい値とする。始めに、ソート処理回路２４は、最小保持デプス値に予め定められた最大数の値をセットする(ステップＳ１０１)。最小保持デプス値とは、全ての半透明描画ポリゴンの中で最も画面奥側（言い換えれば、デプス値が最小値）となるポリゴンのデプス平均値である。最小保持デプス値は、例えばメモリ３０またはレジスタ等に記憶される。
【００３９】
ソート処理回路２４は、入力された順に、３次元演算後の頂点座標を持つ、スクリーン座標投影処理後の半透明描画オブジェクトを三角形ポリゴン単位に分割し、これをポリゴンデータとしてメモリ３０に格納する（ステップＳ１０２）。
【００４０】
ソート処理回路２４は、入力された順に三角形ポリゴンの３頂点分のデプス平均値を計算し、この平均値は、メモリ３０に格納されたポリゴンデータの先頭アドレスと一緒にソート用データとしてメモリ３０に格納される（ステップＳ１０３）。
【００４１】
図４は、ポリゴンデータとソート用データのメモリ３０への格納状態を示している。同図に示すように、ソート処理回路２４は、入力された順に、ポリゴンデータ０、１、２・・・をメモリ３０に格納する。各ポリゴンデータは、３頂点分のｘｙｚ座標値、テクスチャ座標値およびシェーディングカラー等を含んでいる。またソート処理回路２４は、ポリゴンデータ０、１、２・・・に対応するソート用データ０、１、２・・・をメモリ３０に格納する。各ソート用データは、対応するポリゴンデータの先頭アドレスとデプス平均値とを含んでいる。例えば、ソート用データ０は、ポリゴンデータ０の先頭アドレスとそのデプス平均値を含んでいる。
【００４２】
ソート処理回路２４は、ポリゴンのデプス平均値と最小保持デプス値を比較し、値の小さい方を最小保持デプス値としてレジスタに保持する（ステップＳ１０４）。全ての半透明描画オブジェクトのポリゴンデータとソート用データをメモリ３０に格納し終えるまで、上記ステップＳ１０２からＳ１０４までの処理が繰り返される。
【００４３】
次に、ソート処理が開始される。ソート処理回路２４は、最初のソート用データ（図４のソート用データ“０”）のデプス平均値を一時保持デプス値としてレジスタにセットする（ステップＳ１０６）。ソート処理回路２４は、メモリ３０からソート用データを順番に読出し、デプス平均値と最小保持デプス値を大小比較する（ステップＳ１０７）。
【００４４】
デプス値の比較を行った結果（ステップＳ１０８）、ソート用データのデプス平均値が最小保持デプス値よりも大きい場合には、さらにソート用データのデプス平均値と一時保持デプス値とを比較する。ソート用データのデプス平均値が一時保持デプス値よりも小さいとき（デプス平均値＜一次保持デプス値）、一時保持デプス値をソート用データのデプス平均値に更新する（ステップＳ１０９）。
【００４５】
ソート用データのデプス平均値と最小保持デプス値とが等しい場合には、ソート用データ内のポリゴンデータ先頭アドレス値を「ポリゴン描画順番用データ」としてメモリ３０に格納する（ステップＳ１１０）。
【００４６】
デプス平均値が最小保持デプス値よりも小さい場合には、その比較結果に対する処理は行われない。こうして、全てのソート用データについての比較処理が行われると、画面奥側の最初に描画すべき半透明描画オブジェクトの半透明ポリゴンが検出されたことになる（ステップＳ１１１）。また、一時保持デプス値には、最小保持デプス値の次に大きいデプス値（２番目のデプス値）が格納されることになるので、最小保持デプス値を一時保持デプス値に更新する（ステップＳ１１２）。次のソート処理では、２番目に小さなデプス平均値をもつ半透明ポリゴンが検出される。
【００４７】
以上の処理を、全てのポリゴン分の「ポリゴン描画順番用データ」が完成するまで繰り返すことで(ステップＳ１１３)、Ｚソート処理が終了する（ステップＳ１１４）。ポリゴン描画順番用データは、描画リストデータ３４としてメモリ３０に格納される。
【００４８】
図５は、ポリゴン描画順番用データの格納状態を示す図である。同図に示すように、ソート処理を行った結果、ポリゴン描画順番用データの先頭アドレス（ポリゴン先頭アドレス“０”）には、１番目に描画するポリゴンデータの先頭アドレス値が格納され、次のアドレスには、２番目に描画するポリゴンデータの先頭アドレス値が格納される。ポリゴン描画順番用データの先頭アドレスから順にその内容を参照することで、半透明ポリゴンデータを読み出すことができる。
【００４９】
ポリゴンデータのデプス平均値を比較することによって、ポリゴンの描画順番を決定する場合、全て異なるデプス平均値を持ったＮ個の三角形ポリゴンがあれば、Ｎ個×Ｎ回の比較処理を実行することになる。つまり、最大で半透明描画ポリゴン数の２乗もの回数のデプス値比較処理を行わなければならない。
【００５０】
本実施例では、ポリゴン描画順番用データを作成するために、メモリ３０からソート用データを読み出す際において、既にソート処理されたポリゴンのソート用データの読み出しを制御することでＺソート処理を高速化させている。
【００５１】
図６は、ソート処理回路の内部構成を示すブロック図である。ソート処理回路２４は、ソート用データの読出しを制御するソート用データリード制御回路１００と、メモリコントローラ４０を介してメモリ３０から読み出したソート用データを一時記憶するソート用データバッファ１１０と、ソート用データのデプス平均値を比較する浮動小数点デプス値比較回路１２０と、比較回路１２０による比較結果に基づき最小保持デプス値と一致したポリゴンの描画順番を書き込む描画順番用データライト制御回路１３０と、ソート用データのリード開始アドレスを記憶し、これをソート用データリード制御回路１００へ供給するリード開始アドレス値用バッファ１４０と、ソート用データのリード終了アドレスを記憶し、これをソート用データリード制御回路１００へ供給するリード終了アドレス値用バッファ１５０と、リード開始アドレス値用バッファ１４０の内容を更新するリード開始アドレス判断回路１６０と、リードアドレス一時バッファ１８０の内容を更新するリード終了アドレス判断回路１７０を含んでいる。
【００５２】
好ましくは、ポリゴンデータおよびソート用データを格納するメモリ３０は、バーストリードおよびバーストライトが可能なＤＤＲ−ＳＤＲＡＭ(Double Data Rate Synchronous Dynamic RAM)を用いる。あるいは、ＳＤＲＡＭ、ＤＲＡＭ、同期型ＳＲＡＭであってもよい。バーストリードによって、例えば８個単位または１６個単位のブロックでソート用データの読み出しを可能とする。
【００５３】
ソート用データリード制御回路１００は、リード開始アドレス値用バッファ１４０に保持されたリード開始アドレスに従いバーストモードにより、ソート用データブロックを読み出し、リード終了アドレス値用バッファ１５０に保持されたリード終了アドレスに従いソート用データブロックのリードを終了する。
【００５４】
リード開始アドレス値用バッファ１４０には、Ｚソート処理開始時に、ソート用データの格納先頭アドレス値がセットされる。また、リード終了アドレス値用バッファ１５０には、Ｚソート処理開始時に、ブロック単位での最終ソート用データ格納アドレス値がセットされる。これらのバッファのアドレス値は、ポリゴンデータおよびソート用データをメモリ３０に格納するときに保持される。
【００５５】
リード開始アドレス判断回路１６０は、読み出したブロック内のソート用データによるデプス値比較結果が、一度も「デプス平均値＞最小保持デプス値」とならなかった場合に、言い換えれば、ブロック内のソート用データのすべてが既に最小保持デプス値と一致し、かつ描画順序が決定されている場合に、リード開始アドレスを更新する必要があると判断し、その次のブロックの先頭アドレス値をリード開始アドレス値にセットする。
【００５６】
リードアドレス一時バッファ１８０は、読み出されたブロックの先頭アドレス値を格納し、このアドレス値は、リード最終アドレス判断回路１７０によって更新される。リード最終アドレス判断回路１７０は、ブロック内のソート用データによるデプス値比較結果が、一度も「デプス平均値＞最小保持デプス値」とならなかった場合は、その値を保持し続け、一度でも「デプス平均値＞最小保持デプス値」となった場合は、次のソート用データリードにより読み出されたブロックの先頭アドレス値に更新する。
【００５７】
また、リード最終アドレス判断回路１７０は、読み出したブロックのリードアドレス値がリード最終アドレス値に一致する場合は、そのブロック内に最終ソート用データがあると判断し、最終ソート用データによるデプス値比較処理を終了したら、リードアドレス一時バッファ１８０に保持していたアドレス値をリード終了アドレス値にセットする。
【００５８】
次に、ソート処理回路の動作を、図７の例を参照して説明する。図７のソート用データは、データ０〜データ２１と２つの無効データ（図中、灰色で示す）を含んでいる。無効データは、例えばデータ内にフラグを設けることで識別される。ソート用データの括弧内の値は、デプス平均値である。ソート処理として、バーストリードにより８個のソート用データがブロック単位で読み出されるものとする。
【００５９】
ソート用データリード制御回路１００は、図３のフローチャートのステップＳ１０７で示されるように、Ｚソート処理を開始する。リード開始アドレス値用バッファ１４０には、データ０に相当するアドレスが保持され、リード終了アドレス値用バッファ１５０には、データ２１に相当するアドレスが保持される。ソート用データリード制御回路１００は、リード開始アドレスに基づき、最初のブロック、すなわちデータ０〜データ７までのソート用データブロックを読み出す。
【００６０】
ソート用データリード制御回路１００は、ブロックのリードに伴い、ブロックの先頭アドレス（「データ０」のアドレス）をリードアドレス一時バッファ１８０に保持する。また、読み出されたソート用データブロックは、ソート用データバッファ１１０に一旦格納された後、デプス値比較回路１２０において最小保持デプス値と比較される。
【００６１】
１回目のＺソート処理において、最小保持デプス値は「０．２」である。このデプス値比較処理において、「データ０」と「データ３」のデプス平均値が「０．２」であり、「データ０」と「データ３」に対応するポリゴンの描画順序が決定される。「データ０」と「データ３」のいずれかを最初に描画するかは、例えば、ポリゴンデータが入力された順にすることができる。その場合、「データ０」、「データ３」の順序となる、この結果に基づき、描画順番用データライト制御回路１３０は、描画順序データを書き込む。
【００６２】
リード開始アドレス判断回路１６０は、デプス平均値＞最小保持デプス値が存在するので、リード開始アドレス値用バッファ１４０の更新は行わない。また、リード終了アドレス判断回路１７０は、デプス平均値＞最小保持デプス値が存在するので、次のブロックの読み出しのときにリードアドレス一時バッファ１８０を、次のブロックの先頭アドレス、つまり「データ８」のアドレスに更新する。
【００６３】
最初のブロックのソート処理が終了すると、ソート用データリード制御回路１００は、２番目のブロックのソート用データ（「データ８」〜「データ１５」）のリードを行う。２番目のブロックにおいて、最小保持デプス値と等しいソート用データは存在せず、すなわちデプス平均値＞最小保持デプス値が存在するため、リード開始アドレス値用バッファ１４０は更新されない。また、リードアドレス一時バッファ１８０は、次のブロックの読み出しのときに当該ブロックの先頭アドレス、すなわち「データ１６」のアドレスに更新される。
【００６４】
２番目のブロックのソート処理が終了すると、ソート用データリード制御回路１００は、３番目のブロックのソート用データ（「データ１６」〜「データ２１」）のリードを行う。３番目のブロックにおいて、「データ２１」のアドレスが、リード終了アドレス値用バッファ１５０に保持されたアドレスと一致するため、ソート用データリード制御回路１００は、このブロックが最後の読み出しブロックであると判断し、リードアドレス一時バッファ１８０に保持されたアドレス値をリード終了アドレス値用バッファ１５０にセットする。すなわち、３番目のブロックの先頭アドレスである「データ１６」のアドレスがセットされる。
【００６５】
２回目のソート処理において、最小保持デプス値が「０．３」に更新される。最初のブロックにおいて、「データ１」、「データ５」、および「データ６」が最小保持デプス値に一致し、これらの描画順序が決定される。２番目のブロック（「データ８」〜「データ１５」）において、最小保持デプス値に一致するソート用データはなく、３番目のブロックにおいて、「データ１８」と「データ２０」が最小保持デプス値に一致し、これらの描画順序が決定される。
【００６６】
リード開始アドレス判断回路１６０は、２回目のソートにおいて、デプス平均値＞最小保持デプス値が存在するので、リード開始アドレス値用バッファ１４０に保持された開始アドレスを更新しない。また、リード終了アドレス値用バッファ１５０の終了アドレスも更新されない。
【００６７】
第３回目のソートにおいて、最小保持デプス値が「０．４」に更新される。最初のブロックにおいて、「データ２」、「データ４」および「データ７」が最小保持デプス値と一致し、これらの描画順序が決定される。２番目のブロックでは、「データ１０」が最小保持デプス値と一致し、３番目のブロックでは、「データ１６」が最小保持デプス値と一致し、これらの描画順序が決定される。
【００６８】
リード開始アドレス判断回路１６０は、最初のブロックに含まれるすべてのソート用データにおいて、デプス値比較結果が一度も、デプス平均値＞最小保持デプス値とならないと判断し、リード開始アドレス値用バッファ１４０の開始アドレスを２番目のブロックの先頭アドレス値にセットする。すなわち、「データ８」のアドレス値がリード開始アドレス値にセットされる。
【００６９】
４回目のソートにおいて、ソート用データリード制御回路１００は、リード開始アドレス値用バッファ１４０の開始アドレスに従い、「データ８」を先頭アドレスにもつブロックをバーストリードする。４回目のソートでは、最小保持デプス値は、「０．５」に更新され、最初のブロックにおいて、「データ９」が最小保持デプス値に一致し、２番目のブロックにおいて「データ１７」、「データ１９」が最小保持デプス値に一致し、これらの描画順序が決定される。
【００７０】
５回目のソートにおいて、最小保持デプス値が「０．６」に更新される。最初のブロックにおいて、「データ８」と「データ１１」が最小保持デプス値と一致し、２番目のブロックにおいて「データ２１」が最小保持デプス値と一致し、これらの描画順序が決定される。
【００７１】
リード終了アドレス判断回路１７０は、２番目のブロックにおいて、デプス値＞最小保持デプス値が一度も発生しないと判断し、リードアドレス一時バッファ１８０を前のブロックの先頭アドレスに更新し、リード終了アドレス値用バッファ１５０をその先頭アドレスに更新する。
【００７２】
６回目のソートでは、最小保持デプス値が「０．７」に更新され、ソート用データリード制御回路１００は、「データ８」から「データ１５」を含むブロックのみを読み出し、これらのデプス値比較処理を行う。
【００７３】
こうして、ポリゴン描画順番用データが完成されるまで、言い換えれば、デプス値比較結果が一度も「デプス平均値＞最小保持デプス値」とならなくなるまで、ソート用データの読み出しおよびデプス値比較処理が繰り返される。この複数回繰り返されるソート用データ読み出し時に、既にブロック内の全てのポリゴンのソート処理が終了した（ブロック内のデプス値比較結果が一度も「デプス平均値＞最小保持デプス値」とならなかった）ソート用データは、再び読み出されないように制御されるので、Ｚソート処理終了時までに読み出されるソート用データ数が低減され、Ｚソート処理を高速化させることができる。
【００７４】
本実施例によるソート処理回路では、リード開始アドレスおよび終了アドレス値を制御することで、ソート用データの読み出しが複数回繰り返される間に、ソート用データのリード数が少しずつ減少される。図６に示す構成において、リード開始アドレス判断回路１６０、リード終了アドレス判断回路１７０、およびリードアドレス一時バッファ１８０の３つ以外は、通常のデプス値比較処理において必要な回路であり、この３つの簡単な回路を付加することで、Ｚソート処理を高速化させることができる。
【００７５】
勿論、最初のソート用データブロック内に、最も画面手前となるポリゴンがあった場合は、リード開始アドレス値によるリード数を低減することができない。また、最後のソート用データブロック内に最も画面奥側となるポリゴンがあった場合も、リード終了アドレス値によるリード数を低減することができない。しかしこれらは、半透明描画オブジェクト単位などで画面奥行き方向のソート処理をソフトウエアで行うなどして、ソートアクセラレータへのオブジェクト入力を画面奥側オブジェクトから順番に行うようにする（つまり、ソート用データは画面奥側から順番に格納される）ことで回避でき、確実にソート用データリード数を低減することができる。
【００７６】
さらに上記実施例の方法では、リード開始アドレス値とリード終了アドレス値の間にあるブロックは、既にブロック内全てのポリゴンのソート処理が終了していてもリードされてしまうことになる。これを回避するためには、ソート用データブロックの最大数分のブロック処理終了フラグ回路（ブロック最大数×１bit分）を追加し、そのフラグ値に従ってリードするブロックを制御すれば良い。この場合のブロック処理終了フラグ制御は、次のように行うことができる。
【００７７】
１）Ｚソート処理開始時は、ブロック処理終了フラグを全て”０”にクリアする。
２）読み出したブロック内のソート用データによるデプス値比較結果が、一度も「デプス平均値＞最小保持デプス値」とならなかった場合、そのブロックに対応したブロック処理終了フラグを”１”にする。
３）リード開始アドレス値とリード終了アドレス値の間にあるブロックに対応したブロック処理終了フラグが”１”のブロックは、リード処理しないようにする。こうすることで、さらに効率のよいソート用データブロックのリード制御を行うことができる。
【００７８】
さらに上記実施例では、リード開始アドレス値と終了アドレス値をブロック単位の先頭アドレス値としているが、もちろん１データ単位アドレス値でもって制御しても構わない。さらに、ソート用データは、メモリ内に全てが連続して格納されていなくても構わない。例えば、ソート用データをメモリ格納する際、ブロック単位の最後のデータに、次のブロックデータを格納するアドレス値を入れておき、ソート用データを読み出す際には、そのアドレス値に従って順番にブロック単位でリードすることも可能である。
【００７９】
さらに上記実施例に係るＺソート処理回路は、半透明ポリゴンについてのＺソートの例を示したが、これに限らず、不透明描画オブジェクトのポリゴンのＺソートを行うことができる。特に、Ｚバッファを用いずに、不透明ポリゴンを画面奥側から画面手前または画面手前から画面奥側にＺソートして描画する場合に、本発明を適用することができる。
【００８０】
本発明の好ましい実施の形態について詳述したが、本発明は係る特定の実施形態に限定されるものではなく、特許請求の範囲に記載された本発明の要旨の範囲内において、種々の変形、変更が可能である。
【産業上の利用可能性】
【００８１】
本発明に係る３次元画像描画装置およびＺソート処理方法は、３次元グラフィックスコンピュータ、ビデオゲーム機、遊技機、およびその他の映像装置などにおいて利用される。
【図面の簡単な説明】
【００８２】
【図１】本発明の実施例に係る三次元画像描画装置のシステム構成を示すブロック図である。
【図２】描画用回路の基本的な処理を示す図である。
【図３】Ｚソート処理のフローを示す図である。
【図４】ポリゴンデータとソート用データの格納状態を示す図である。
【図５】ポリゴン描画順番用データの格納状態を示す図である。
【図６】本実施例のソート処理回路の構成を示すブロック図である。
【図７】本実施例のソート処理例を示す図である。
【図８】モデルデータの座標空間を示す図である。
【図９】半透明描画を説明する図である。
【図１０】立体物の半透明オブジェクトの例を示す図である。
【符号の説明】
【００８３】
１：３次元画像描画装置
１０：ＣＰＵ
２０：描画用回路
３０：メモリ
４０：メモリコントローラ
５０：画像表示用回路
１００：ソート用データリード制御回路
１１０：ソート用データバッファ
１２０：デプス値比較回路
１３０：描画順番用データライト制御回路
１４０：リード開始アドレス値用バッファ
１５０：リード終了アドレス値用バッファ
１６０：リード開始アドレス判断回路
１７０：リード終了アドレス判断回路
１８０：リードアドレス一時バッファ
【図１】
2006285372.tif 000004
【図２】
2006285372.tif 000005
【図３】
2006285372.tif 000006
【図４】
2006285372.tif 000007
【図５】
2006285372.tif 000008
【図６】
2006285372.tif 000009
【図７】
2006285372.tif 000010
【図８】
2006285372.tif 000011
【図９】
2006285372.tif 000012
【図１０】
2006285372.tif 000013