(57)【要約】【課題】  頂点参照データ形式においても高速にポリゴンデコードを行うことが可能な３次元画像描画装置を提供する。【解決手段】  ３次元画像の表面を表す複数のポリゴンの各頂点情報を含む頂点リスト、及び複数のポリゴンの各々ごとに各頂点を連結する情報を含むポリゴンリストをあらかじめ記憶する記憶部１１から、描画対象のポリゴンのポリゴンリストを読み出し、読み出したポリゴンリストに基づいて頂点リストを読み出して頂点レジスタ１６に転送し、頂点レジスタに転送された頂点リストに基づいて描画対象のポリゴンを描画することにより３次元画像を描画する際、読み出しアドレス及びその周辺アドレスのポリゴンリストを記憶するポリゴンリストキャッシュ２１を備える。また、ポリゴンリストキャッシュに加えて、読み出しアドレス及びその周辺アドレスの頂点リストを記憶する頂点キャッシュ２２を備える。【選択図】  図１
2006209695.tif 000002
【特許請求の範囲】
【請求項１】
３次元画像の表面を表す複数のポリゴンの各頂点情報を含む頂点リスト、及び前記複数のポリゴンの各々ごとに各頂点を連結する情報を含むポリゴンリストをあらかじめ記憶する記憶部から、描画対象のポリゴンのポリゴンリストを読み出し、前記読み出したポリゴンリストに基づいて頂点リストを読み出して頂点リストレジスタに転送し、前記頂点リストレジスタに転送された頂点リストに基づいて前記描画対象のポリゴンを描画することにより３次元画像を描画する３次元画像描画装置において、
前記記憶部に記憶されたポリゴンリストの読み出しアドレスをポリゴンごとに更新して保持するポリゴンリストアドレスレジスタと、
前記ポリゴンリストアドレスレジスタに保持された読み出しアドレスのポリゴンリストを保持するためのポリゴンリストレジスタと、
前記記憶部と前記ポリゴンリストレジスタの間に設けられ、前記ポリゴンリストアドレスレジスタに保持された読み出しアドレス、及びその周辺アドレスのポリゴンリストを記憶するためのポリゴンリストキャッシュと、
前記ポリゴンリストアドレスレジスタに保持された読み出しアドレスのポリゴンリストが前記ポリゴンリストキャッシュに存在する場合には、それを前記ポリゴンリストキャッシュから読み出し、存在しない場合には、それを前記記憶部から前記ポリゴンリストキャッシュに読み出した後に前記ポリゴンリストレジスタに転送する手段と、
前記ポリゴンリストレジスタに保持されたポリゴンリストに基づいて前記記憶部から頂点リストを読み出して前記頂点リストレジスタに転送する手段とを備え、
前記頂点リストレジスタに転送された頂点リストに基づいて前記描画対象のポリゴンを描画することにより３次元画像を描画することを特徴とする３次元画像描画装置。
【請求項２】
請求項１に記載の３次元画像描画装置において、
前記記憶部に記憶された頂点リストの先頭アドレスを保持する頂点リスト先頭アドレスレジスタと、
前記ポリゴンリストレジスタに保持されたポリゴンリスト、及び前記頂点リスト先頭アドレスレジスタに保持された頂点リストの先頭アドレスから読み出すべき頂点の読み出しアドレスを算出する頂点アドレス算出手段と、
前記記憶部と前記頂点リストレジスタの間に設けられ、前記頂点アドレス算出手段により算出された読み出しアドレス、及びその周辺アドレスの頂点リストを記憶するための頂点リストキャッシュと、
前記頂点アドレス算出手段により算出された読み出しアドレスの頂点リストが前記頂点リストキャッシュに存在する場合には、それを前記頂点リストキャッシュから読み出し、存在しない場合には、前記記憶部から前記頂点リストキャッシュに読み出した後に前記頂点リストレジスタに転送する手段とを更に備えたことを特徴とする３次元画像描画装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ポリゴンで形成される３次元シーンを描画する際にポリゴンデコードを行う３次元画像描画装置に関する。
【背景技術】
【０００２】
３次元画像描画装置における入力データは、通常、３次元画像の表面を複数の多角形（ポリゴン）で表すに際し、各ポリゴンの各頂点の座標、色を用いて表すため、頂点データの個数はおおよそ（ポリゴン数）×（１ポリゴンの平均頂点数）となる。ところが、一般的に３次元モデルを複数のポリゴンで表す場合、隣り合うポリゴン同士で頂点を共有する場合が多く、上述のデータ形式では重複する頂点データを多数含むことになり、効率的ではない。そこで、入力データをオブジェクト単位にグループ分けし、そのオブジェクトに含まれる頂点データ列である頂点リストと、各ポリゴンの頂点を頂点リストから参照するためのインデックス情報列であるポリゴンリストとからなる頂点参照データ形式を用いる方法がある（例えば下記の特許文献１参照）。
【０００３】
図５（ａ）、（ｂ）にそれぞれ頂点リスト及びポリゴンリストの一例を示す。頂点リストは頂点インデックスｉ（ｉ＝０，１，２〜）ごとに座標（ｘi，ｙi，ｚi，ｗi）及び色（ｒi，ｇi ，ｂi，ａi）の頂点情報により構成され、ポリゴンリストはポリゴン番号ｋ（ｋ＝０，１，２〜）ごとに各頂点を連結する辺を示すインデックス連結情報により構成されている。ここで、例えば３次元画像が立方体（＝６面体）の場合、頂点インデックス数＝８、ポリゴン数＝６となる。この頂点参照データ形式を用いることにより、重複する頂点データを無くし、入力データ量を削減することができる。この頂点参照データ形式のデータから描画処理を行う際には、図５（ｂ）に示すポリゴンリス卜のインデックス連結情報から、ポリゴンを形成する複数の頂点情報を図５（ａ）に示す頂点リストから読み出す必要があり、この処理をポリゴンデコードと呼ぶこととする。
【０００４】
また、従来は３次元画像描画の高速化を図るために固定ハードウエアによる定型処理によってポリゴンデータからフレームバッファヘの描画を行う３次元画像描画装置が一般的であったが、多様な描画方式を実現するためにプロセッサ部を備えてプログラマブルな構成の汎用装置が増加している。このような３次元画像描画装置において、ポリゴンデコードを行う従来の３次元画像描画装置の一例を図６に示す。この３次元画像描画装置は各種命令を実行することによってポリゴンデコードや描画処理を行うことができるプログラマブルな装置であり、各種データを記憶しておく記憶部１１と、記憶部１１のデータの読み書きに用いるデータキャッシュ１２と、命令のフェッチ、デコードや記憶部１１の制御を行う制御部１３と、各種演算を行う汎用演算部１４と、汎用演算部１４や記憶部１１とデータの入出力に用いる複数のレジスタを備える汎用レジスタ１５と、ポリゴンを形成する頂点情報を格納する頂点レジスタ１６と、頂点レジスタ１６の頂点情報から各ポリゴンの描画処理を行い、各ポリゴンを合成することにより３次元画像描画を行う描画処理部１７から構成されている。
【０００５】
この従来の３次元画像描画装置は、少なくとも、
（１）汎用レジスタ１５同士の加算命令ＡＤＤ（以下ＡＤＤ命令と記すこともある）と、
（２）指定されたアドレスのデータを記憶部１１から汎用レジスタ１５ヘ読み出すＬＤＭ命令と、
（３）汎用レジスタ１５の値を頂点レジスタ１６に転送するＳＴＶ命令
を備えていることとする。ある１つの三角形ポリゴンのデコードを行う場合、まずＬＤＭ命令によって記憶部１１から対象ポリゴンリストの１頂点目のインデックス値を汎用レジスタ１５に読み出す。次に読み出したインデックス値が示す頂点データのアドレスをＡＤＤ命令などによって計算する。そして、記憶部１１の計算されたアドレスのエリアから頂点データを読み出す。
【０００６】
次に、２頂点目のインデックス値のアドレスをＡＤＤ命令などによって計算し、１頂点目と同様の処理を行って２頂点目の頂点データを読み出す。３頂点目も同様の処理を行うことによって、３頂点すべての頂点データを汎用レジスタ１５に格納する。こうして汎用レジスタ１５に格納された頂点データを、ＳＴＶ命令によって頂点レジスタ１６に転送し、頂点レジスタ１６から描画処理部１７に入力されて三角形ポリゴンの描画処理が行われる。
【０００７】
この間の記憶部１１から汎用レジスタ１５ヘの読み出しにはすべてＬＤＭ命令が用いられているため、データキャッシュ１２を介している。記憶部１１は一般的に、連続したアドレスのデータを一度に読み書きするよりも、少量のデータを頻繁に読み書きする方が低速であるため、記憶部１１よりも高速なデータキャッシュ１２を介したデータアクセス方法が用いられる。データキャッシュ１２にアクセスすべきアドレスのデータがある場合は「キャッシュヒット」と言い、そのままデータキャッシュ１２からデータを読み出す。データキャッシュ１２に無い場合は「キャッシュミス」と言い、記憶部１１から当該アドレスと周辺アドレスのデータを一定量データキャッシュ１２に読み出してから、当該アドレスのデータをデータキャッシュ１２から読み出す。このようにデータキャッシュ１２を用いれば、特に局所性のあるアクセスを高速にすることができる。
【特許文献１】特開２０００−３４８２０９号公報（段落０００２）
【発明の開示】
【発明が解決しようとする課題】
【０００８】
しかしながら、頂点リストとポリゴンリストの間には、記憶部１１中の格納アドレスに局所性は無いため、キャッシュミスを引き起こす確率が高く、処理の低速化を招いてしまうことが課題であった。
【０００９】
そこで本発明は、頂点参照データ形式においても高速にポリゴンデコードを行うことが可能な３次元画像描画装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
本発明は上記目的を達成するために、
３次元画像の表面を表す複数のポリゴンの各頂点情報を含む頂点リスト、及び前記複数のポリゴンの各々ごとに各頂点を連結する情報を含むポリゴンリストをあらかじめ記憶する記憶部から、描画対象のポリゴンのポリゴンリストを読み出し、前記読み出したポリゴンリストに基づいて頂点リストを読み出して頂点リストレジスタに転送し、前記頂点リストレジスタに転送された頂点リストに基づいて前記描画対象のポリゴンを描画することにより３次元画像を描画する３次元画像描画装置において、
前記記憶部に記憶されたポリゴンリストの読み出しアドレスをポリゴンごとに更新して保持するポリゴンリストアドレスレジスタと、
前記ポリゴンリストアドレスレジスタに保持された読み出しアドレスのポリゴンリストを保持するためのポリゴンリストレジスタと、
前記記憶部と前記ポリゴンリストレジスタの間に設けられ、前記ポリゴンリストアドレスレジスタに保持された読み出しアドレス、及びその周辺アドレスのポリゴンリストを記憶するためのポリゴンリストキャッシュと、
前記ポリゴンリストアドレスレジスタに保持された読み出しアドレスのポリゴンリストが前記ポリゴンリストキャッシュに存在する場合には、それを前記ポリゴンリストキャッシュから読み出し、存在しない場合には、それを前記記憶部から前記ポリゴンリストキャッシュに読み出した後に前記ポリゴンリストレジスタに転送する手段と、
前記ポリゴンリストレジスタに保持されたポリゴンリストに基づいて前記記憶部から頂点リストを読み出して前記頂点リストレジスタに転送する手段とを備え、
前記頂点リストレジスタに転送された頂点リストに基づいて前記描画対象のポリゴンを描画することにより３次元画像を描画することを特徴とする。
【００１１】
また、本発明は上記目的を達成するために、請求項１に記載の３次元画像描画装置において、
前記記憶部に記憶された頂点リストの先頭アドレスを保持する頂点リスト先頭アドレスレジスタと、
前記ポリゴンリストレジスタに保持されたポリゴンリスト、及び前記頂点リスト先頭アドレスレジスタに保持された頂点リストの先頭アドレスから読み出すべき頂点の読み出しアドレスを算出する頂点アドレス算出手段と、
前記記憶部と前記頂点リストレジスタの間に設けられ、前記頂点アドレス算出手段により算出された読み出しアドレス、及びその周辺アドレスの頂点リストを記憶するための頂点リストキャッシュと、
前記頂点アドレス算出手段により算出された読み出しアドレスの頂点リストが前記頂点リストキャッシュに存在する場合には、それを前記頂点リストキャッシュから読み出し、存在しない場合には、前記記憶部から前記頂点リストキャッシュに読み出した後に前記頂点リストレジスタに転送する手段とを更に備えたことを特徴とする。
【発明の効果】
【００１２】
本発明によれば、読み出しアドレス及びその周辺アドレスのポリゴンリストを記憶するポリゴンリストキャッシュを備えているので、ポリゴンリストのキャッシュミスの回数を大幅に減らすことができ、高速な処理を実現することができる。
また、本発明によれば、読み出しアドレス及びその周辺アドレスのポリゴンリストを記憶するポリゴンリストキャッシュと、読み出しアドレス及びその周辺アドレスの頂点リストを記憶する頂点リストキャッシュを備えているので、ポリゴンリストと頂点リストのキャッシュミスの回数を大幅に減らすことができ、高速な処理を実現することができる。
【発明を実施するための最良の形態】
【００１３】
以下、図面を参照して本発明の実施の形態について説明する。
＜第１の実施の形態＞
図１は本発明に係る３次元画像描画装置の第１の実施の形態を示すブロック図、図２は図１の３次元画像描画装置のポリゴンデコード処理を説明するためのフローチャートである。
【００１４】
第１の実施の形態は、頂点参照データ形式のポリゴンデータにおいても高速なポリゴンデコードを行うという目的を、図１に示すようにポリゴンリストキャッシュ２１を用いることにより実現した。図１に示す３次元画像描画装置は図６の従来の汎用の３次元画像描画装置に加え、記憶部１１から図５（ｂ）に示すようなポリゴンリストを読み出すためのポリゴンリストキャッシュ２１と、ポリゴンリストデータを格納するポリゴンリストレジスタ２３と、デコードするポリゴンリストのアドレスを保持するポリゴンリストアドレスレジスタ２４を備えている。
【００１５】
また、制御部１３には従来の汎用命令である、
（１）汎用レジスタ１５同士の加算命令ＡＤＤと、
（２）指定されたアドレスのデータを記憶部１１から汎用レジスタ１５ヘ読み出すＬＤＭ命令と、
（３）汎用レジスタ１５の値を頂点レジスタ１６に転送するＳＴＶ命令
に加え、
（４）ポリゴンリストアドレスレジスタ２４を設定するＳＴＰＡ命令と、
（５）ポリゴンリストを読み出すためのＬＤＰＬ命令
を実行するための手段が備えられている。記憶部１１には、あるオブジェクトのポリゴンリストデータ、頂点リストデータが記憶されており、このデータをデコードする場合、まず初期設定としてＳＴＰＡ命令によってポリゴンリストアドレスレジスタ２４に記憶部１１中のポリゴンリストデータのアドレスを設定する。
【００１６】
この設定をした後、ポリゴンデコードが行われるまでの処理の流れを図２に示す。図２は３頂点ａ、ｂ、ｃから構成される三角形ポリゴンをデコードする例である。まず、ポリゴンリスト読み出すためのＬＤＰＬ命令が発行され、ポリゴンリストアドレスレジスタ２４が指し示すアドレスのデータを記憶部１１からポリゴンリストキャッシュ２１に読み出し、さらにポリゴンリストレジスタ２３に読み出す（ステップＳ１）。読み出しが終わった状態では、ポリゴンリストレジスタ２３には頂点ａ、ｂ、ｃのインデックス値Ｉａ、Ｉｂ、Ｉｃが格納されている。
【００１７】
読み出しが完了すると、加算命令ＡＤＤなどの汎用命令を用いて頂点リスト先頭アドレスとポリゴンリストレジスタ２３内のインデックス値Ｉａから頂点ａの頂点データアドレスを算出する（ステップＳ２）。続いてＬＤＭ命令で、記憶部１１中の算出された頂点データアドレスから頂点ａの頂点データをデータキャッシュ１２に読み出し、更に汎用レジスタ１５に格納する（ステップＳ３）。
【００１８】
頂点ｂ、ｃについてもステップＳ２、ステップＳ３と同様の処理を行い、頂点データを記憶部１１から汎用レジスタ１５に読み出す（ステップＳ４〜Ｓ７）。３頂点ａ、ｂ、ｃのすべての頂点データが汎用レジスタ１５に読み出された後に、ＳＴＶ命令によって頂点データを汎用レジスタ１５から頂点レジスタ１６に転送してポリゴンデコードが完了する（ステップＳ８）。
【００１９】
２回目以降のポリゴンデコード命令ＬＤＰＬが発行された場合、ポリゴンリストキャッシュ２１には前の命令で読み出したアドレスと周辺アドレスのポリゴンリストのデータが既に格納されている。ポリゴンリストのデータは連続的に並んでおり、なおかつ連続的に読み出すため非常に局所性が強い。一方、頂点データは連続的に並んでいるが、読み出し順はポリゴンリストデータに依存するため、連続ではなくポリゴンリストデータより局所性が低い。よって２回目以降のポリゴンデコード命令によるポリゴンリストは、ポリゴンリストキャッシュ２１内に存在する確率が高く、ポリゴンリストキャッシュ２１から直接読み出すことによって記憶部１１ヘのアクセス回数を減らすことができる。この例は三角形ポリゴンの場合であるが、四角形やそれ以上の多角形においても適用できる。
【００２０】
また、ポリゴンリスト読み出し命令実行後にポリゴンリストアドレスレジスタ２４のアドレス値をインクリメントして次のポリゴンリストのアドレスを設定しておく手段を備えることによって、ポリゴンリストのアドレス計算時間を短縮することが可能になる。
【００２１】
＜第２の実施の形態＞
本発明の第２の実施の形態は、頂点参照データ形式のポリゴンデータにおいても高速なポリゴンデコードを行うという目的を、図３に示すように頂点キャッシュ２２とポリゴンリストキャッシュ２１を用いることにより実現した。図３に示す３次元画像描画装置は図６の従来の汎用の３次元画像描画装置に加え、記憶部１１から図５（ｂ）に示すようなポリゴンリストを読み出すためのポリゴンリストキャッシュ２１と、図５（ａ）に示すような頂点リストのデータを読み出すための頂点キャッシュ２２と、ポリゴンリストキャッシュ２１からのポリゴンリストデータを格納するポリゴンリストレジスタ２３と、デコードするポリゴンリストのアドレスを保持するポリゴンリストアドレスレジスタ２４と、頂点リストの先頭アドレスを保持する頂点リスト先頭アドレスレジスタ２５と、頂点アドレスを算出する頂点アドレス算出部２６を備えている。ここで、図３に示したデータキャッシュ１２、汎用レジスタ１５及び汎用演算部１４は、第２の実施の形態には関係なく、他の演算目的に用いる。
【００２２】
また、制御部１３には従来の汎用命令である、
（１）汎用レジスタ１５同士の加算命令ＡＤＤと、
（２）指定されたアドレスのデータを記憶部１１から汎用レジスタ１５ヘ読み出すＬＤＭ命令と、
（３）汎用レジスタ１５の値を頂点レジスタ１６に転送するＳＴＶ命令
に加え、
（４）ポリゴンリストアドレスレジスタ２４を設定するＳＴＰＡ命令と、
（５）頂点リスト先頭アドレスレジスタ２５を設定するＳＴＶＡ命令と、
（６）ポリゴンデコードを行うためのＰＤＥＣ命令
を実行するための手段が備えられている。
【００２３】
記憶部１１には、あるオブジェクトのポリゴンリストデータ、頂点リストデータが記憶されており、このデータをデコードする場合、まず初期設定としてＳＴＰＡ命令によってポリゴンリストアドレスレジスタ２４に記憶部１１中のポリゴンリストデータのアドレスを設定するとともに、ＳＴＶＡ命令によって頂点リスト先頭アドレスレジスタ２５に頂点リスト先頭アドレスを設定する。これらの設定をした後、ＰＤＥＣ命令が発行され、ポリゴンデコードが行われる。
【００２４】
図３の３次元画像描画装置でポリゴンデコードが行われるまでの処理の流れを図４に示す。図４は３頂点ａ、ｂ、ｃから構成される三角形ポリゴンをデコードする例を示す。まず、ＰＤＥＣ命令が発行されると、ポリゴンリストアドレスレジスタ２４が指し示すアドレスのデータを、記憶部１１からポリゴンリストキャッシュ２１に読み出し、さらにポリゴンリストレジスタ２３に読み出す（ステップＳ１１）。読み出しが終わった状態では、ポリゴンリストレジスタ２３には頂点ａ、ｂ、ｃのインデックス値Ｉａ、Ｉｂ、Ｉｃが格納されている。
【００２５】
読み出しが完了すると、頂点アドレス算出部２６において頂点リスト先頭アドレスレジスタ２５のアドレス値とポリゴンリストレジスタ２３内のインデックス値Ｉａを加算して頂点ａの頂点データアドレスを算出する（ステップＳ１２）。記憶部１１中の算出された頂点データアドレスから頂点データａを頂点キャッシュ２２に読み出し、さらに頂点レジスタ１６に格納する（ステップＳ１３）。
【００２６】
次に頂点アドレス算出部２６において頂点リスト先頭アドレスレジスタ２５のアドレス値とポリゴンリストレジスタ２３内のインデックス値Ｉｂを加算して頂点ｂの頂点データアドレスを算出する（ステップＳ１４）。記憶部１１中の算出された頂点データアドレスから頂点データを読み出し、頂点レジスタ１６に格納する（ステップＳ１５）。同様にして頂点ｃの頂点データを記憶部１１から頂点レジスタ１６に読み出し（ステップＳ１６、Ｓ１７）、ポリゴンデコードが完了する。
【００２７】
２回目以降のＰＤＥＣ命令が発行された場合、ポリゴンリストキャッシュ２１、頂点キャッシュ２２には前の命令で読み出したアドレスと周辺アドレスのデータが既に格納されている。ポリゴンリストデータは連続的に並んでおり、なおかつ連続的に読み出すため非常に局所性が強い。また、頂点データは連続的に並んでいるが、読み出し順はポリゴンリストデータに依存するため、連続ではない。しかし、一般的なポリゴンリストでは、頂点の読み出し順に局所性が強い傾向がある。よって２回目以降のＰＤＥＣ命令によるポリゴンリスト、頂点リストの読み出し時は、それぞれポリゴンリストキャッシュ２１、頂点キャッシュ２２から読み出すことによって記憶部１１ヘのアクセス回数を減らすことができる。この例は三角形ポリゴンの場合であるが、四角形やそれ以上の多角形においても適用できる。
【００２８】
また、ＰＤＥＣ命令実行時のポリゴンリスト読み出し後にポリゴンリストアドレスレジスタ２４のアドレス値をインクリメントして次のポリゴンリストのアドレスを設定しておく手段を備えることによって、ポリゴンリストのアドレス計算時間を短縮することが可能になる。
【図面の簡単な説明】
【００２９】
【図１】本発明に係る３次元画像描画装置の第１の実施の形態を示すブロック図である。
【図２】図１の３次元画像描画装置のポリゴンデコード処理を説明するためのフローチャートである。
【図３】本発明に係る３次元画像描画装置の第２の実施の形態を示すブロック図である。
【図４】図３の３次元画像描画装置のポリゴンデコード処理を説明するためのフローチャートである。
【図５】本発明及び従来の技術に係る頂点リスト及びポリゴンリストを示す説明図である。
【図６】従来の３次元画像描画装置を示すブロック図である。
【符号の説明】
【００３０】
１１  記憶部
１２  データキャッシュ
１３  制御部
１４  汎用演算部
１５  汎用レジスタ
１６  頂点レジスタ
１７  描画処理部
２１  ポリゴンリストキャッシュ
２２  頂点キャッシュ
２３  ポリゴンリストレジスタ
２４  ポリゴンリストアドレスレジスタ
２５  頂点リスト先頭アドレスレジスタ
２６  頂点アドレス算出部
【図１】
2006209695.tif 000003
【図２】
2006209695.tif 000004
【図３】
2006209695.tif 000005
【図４】
2006209695.tif 000006
【図５】
2006209695.tif 000007
【図６】
2006209695.tif 000008