(57)【特許請求の範囲】
【請求項１】
描画データをラスタライズ処理して描画する描画装置であって、
前記描画データからラスタライズ処理の対象となる第１の三角形領域を特定する三角形特定手段と、
前記第１の三角形領域に含まれる画素を有する画素ブロックを特定するブロック特定手段と、
前記ブロック特定手段で特定された画素ブロックに、前記第１の三角形領域と連接する第２の三角形領域の画素が含まれるか否かを判別する判別手段と、
前記判別手段で含まれると判別されたときには、前記第１の三角形領域の画素および第２の三角形領域の画素を含む画素ブロックをラスタライズ処理して画素データを生成するラスタライズ手段と、
前記ラスタライズ手段で生成された画素ブロックの画素データをメモリに書き込む書き込み手段と、
前記メモリに書き込まれた画素データに応じた画像を表示させる表示制御手段とを備え、
前記三角形特定手段は、さらに、前記描画データからラスタライズ処理の対象となる前記第２の三角形領域を特定し、
ブロック特定手段は、さらに、前記三角形特定手段が前記第２の三角形領域を特定したときには、前記第２の三角形領域に含まれる画素を有する画素ブロックを特定し、
前記ラスタライズ手段は、さらに、前記三角形特定手段が前記第２の三角形領域を特定したときには、前記ブロック特定手段で特定された画素ブロックのうち、前記判別手段で判別された前記第１及び第２の三角形領域の画素を有する画素ブロックを、ラスタライズ処理の対象から除く
ことを特徴とする描画装置。
【請求項２】
前記判別手段は、前記ブロック特定手段で特定された画素ブロックに、前記第１の三角形領域の後に描画すべき前記第２の三角形領域の画素が含まれるか否かを判別する
ことを特徴とする請求項１記載の描画装置。
【請求項３】
前記判別手段は、前記ブロック特定手段で特定された画素ブロックに、前記第１の三角形領域の前に描画対象とされた前記第２の三角形領域の画素が含まれるか否かを判別する
ことを特徴とする請求項１記載の描画装置。
【請求項４】
前記判別手段は、
前記第１の三角形領域の一辺を共有する前記第２の三角形領域に含まれる、前記一辺の両端にある頂点以外の頂点を、前記描画データから特定したときには、
前記第１の三角形領域の一辺上にある、前記ブロック特定手段で特定された画素ブロックには、前記第２の三角形領域の画素が含まれると判別する
ことを特徴とする請求項１記載の描画装置。
【請求項５】
前記判別手段は、
前記第１の三角形領域の一辺を共有する他の三角形領域がないことを示す非共有情報を前記描画データから特定したときには、
前記非共有情報に対応する前記第１の三角形領域の一辺上にある、前記ブロック特定手段で特定された画素ブロックには、前記第２の三角形領域の画素は含まれないと判別する
ことを特徴とする請求項１記載の描画装置。
【請求項６】
前記ラスタライズ手段は、
前記判別手段で含まれると判別された画素ブロックをラスタライズ処理の対象から除き、前記画素ブロックのラスタライズ処理を前記第２の三角形領域の処理時に行なうべきことを示す除外情報を前記描画データから特定したときには、前記画素ブロックに対するラスタライズ処理を禁止する
ことを特徴とする請求項１記載の描画装置。
【請求項７】
前記描画データは三角形ストリップ形式により構成されている
ことを特徴とする請求項１記載の描画装置。
【請求項８】
前記描画データは三角形ファン形式により構成されている
ことを特徴とする請求項１記載の描画装置。
【請求項９】
前記描画データは三角形ストリップ形式と三角形ファン形式とにより構成されている
ことを特徴とする請求項１記載の描画装置。
【請求項１０】
前記描画データは三角形メッシュ形式により構成されている
ことを特徴とする請求項１記載の描画装置。
【請求項１１】
描画データをラスタライズ処理して描画する集積回路であって、
前記描画データからラスタライズ処理の対象となる第１の三角形領域を特定する三角形特定手段と、
前記第１の三角形領域に含まれる画素を有する画素ブロックを特定するブロック特定手段と、
前記ブロック特定手段で特定された画素ブロックに、前記第１の三角形領域と連接する第２の三角形領域の画素が含まれるか否かを判別する判別手段と、
前記判別手段で含まれると判別されたときには、前記第１の三角形領域の画素および第２の三角形領域の画素を含む画素ブロックをラスタライズ処理して画素データを生成するラスタライズ手段と、
前記ラスタライズ手段で生成された画素ブロックの画素データをメモリに書き込む書き込み手段と、
前記メモリに書き込まれた画素データに応じた画像を表示させる表示制御手段とを備え、
前記三角形特定手段は、さらに、前記描画データからラスタライズ処理の対象となる前記第２の三角形領域を特定し、
ブロック特定手段は、さらに、前記三角形特定手段が前記第２の三角形領域を特定したときには、前記第２の三角形領域に含まれる画素を有する画素ブロックを特定し、
前記ラスタライズ手段は、さらに、前記三角形特定手段が前記第２の三角形領域を特定したときには、前記ブロック特定手段で特定された画素ブロックのうち、前記判別手段で判別された前記第１及び第２の三角形領域の画素を有する画素ブロックを、ラスタライズ処理の対象から除く
ことを特徴とする集積回路。
【請求項１２】
描画装置が、描画データをラスタライズ処理して描画する方法であって、
前記描画装置は、三角形特定手段、ブロック特定手段、判別手段、ラスタライズ手段、書き込み手段および表示制御手段を備え、
前記三角形特定手段が、前記描画データからラスタライズ処理の対象となる第１の三角形領域を特定する三角形特定ステップと、
前記ブロック特定手段が、前記第１の三角形領域に含まれる画素を有する画素ブロックを特定するブロック特定ステップと、
前記判別手段が、前記ブロック特定ステップで特定された画素ブロックに、前記第１の三角形領域と連接する第２の三角形領域の画素が含まれるか否かを判別する判別ステップと、
前記ラスタライズ手段が、前記判別ステップで含まれると判別されたときには、前記第１の三角形領域の画素および第２の三角形領域の画素を含む画素ブロックをラスタライズ処理して画素データを生成するラスタライズステップと、
前記書き込み手段が、前記ラスタライズステップで生成された画素ブロックの画素データをメモリに書き込む書き込みステップと、
前記表示制御手段が、前記メモリに書き込まれた画素データに応じた画像を表示させる表示制御ステップとを含み、
前記三角形特定ステップでは、さらに、前記描画データからラスタライズ処理の対象となる前記第２の三角形領域を特定し、
ブロック特定ステップでは、さらに、前記三角形特定手段が前記第２の三角形領域を特定したときには、前記第２の三角形領域に含まれる画素を有する画素ブロックを特定し、
前記ラスタライズステップでは、さらに、前記三角形特定手段が前記第２の三角形領域を特定したときには、前記ブロック特定手段で特定された画素ブロックのうち、前記判別手段で判別された前記第１及び第２の三角形領域の画素を有する画素ブロックを、ラスタライズ処理の対象から除く
ことを特徴とする描画方法。
【請求項１３】
描画データをラスタライズ処理して描画するためのプログラムであって、
前記請求項１に記載の描画装置が備える三角形特定手段、ブロック特定手段、判別手段、ラスタライズ手段、書き込み手段および表示制御手段としてコンピュータを機能させるプログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピューターグラフィクスの描画処理を行なう描画装置に関する。
【背景技術】
【０００２】
従来のコンピューターグラフィクスの描画処理を行なう描画装置は、一般に、三角形ストリップ（Ｔｒｉａｎｇｌｅ  Ｓｔｒｉｐ）、三角形ファン（Ｔｒｉａｎｇｌｅ  Ｆａｎ）、それらを相互に切り替えられる仕組み（以下、スネーク（Ｔｒｉａｎｇｌｅ  Ｓｎａｋｅ）という）、および三角形メッシュ（Ｔｒｉａｎｇｌｅ  Ｍｅｓｈ）などの形式で与えられたグラフィクスデータを描画する際に、そのグラフィックスデータを個別の三角形毎にラスタライズと呼ばれる画素毎の情報に変換する処理を行なっている。
【０００３】
図１は、三角形ストリップのデータ形式を示す図である。
【０００４】
三角形ストリップのデータ形式では、頂点Ｐ0、頂点Ｐ1、頂点Ｐ2、頂点Ｐ3、…、頂点ＰNUM-1、頂点ＰNUM、および頂点ＰNUM+1に対して、例えば、頂点Ｐ0、頂点Ｐ1、および頂点Ｐ2の３頂点で三角形Ｔ0が構成され、頂点Ｐ1、頂点Ｐ2、および頂点Ｐ3の３頂点で三角形Ｔ1が構成され、頂点ＰN、頂点ＰN+1、および頂点ＰN+2の３頂点で三角形ＴNが構成される。このデータ形式の特徴は、三角形を３つの頂点の情報で表現すると、ＮＵＭ個の三角形の情報を記述するのに３×ＮＵＭ個の頂点の情報が必要になるのに対し、三角形ストリップ形式なら（ＮＵＭ＋２）個の頂点の情報だけで済み、データ量を減らせることである。
【０００５】
図２は、三角形ファンのデータ形式を示す図である。
【０００６】
三角形ファンのデータ形式では、頂点Ｐ0、頂点Ｐ1、頂点Ｐ2、頂点Ｐ3、…、頂点ＰNUM-1、頂点ＰNUM、および頂点ＰNUM+1に対して、例えば、頂点Ｐ0、頂点Ｐ1、および頂点Ｐ2の３頂点で三角形Ｔ0が構成され、頂点Ｐ0、頂点Ｐ2、および頂点Ｐ3の３頂点で三角形Ｔ1が構成され、頂点Ｐ0、頂点ＰN+1、および頂点ＰN+2の３頂点で三角形ＴNが構成される。このデータ形式も三角形ストリップと同様にデータ量を減らせるのが特徴である。
【０００７】
図３は、スネークのデータ形式を示す図である。
【０００８】
スネークは、三角形ストリップと三角形ファンの相互を途中で自由に切り替えられるデータ形式である。切り替えのポイントを示すために別途情報が必要である。データ量は三角形ストリップや三角形ファンと同様であるが、三角形ストリップや三角形ファンの場合は、三角形の接続状態が一意に決められているため、条件が整わないと連続する三角形をそれほど多くできない。これに対し、本形式では、自由度が有るため、連続する三角形をより多くすることができる可能性が高いという特徴がある。
【０００９】
図４Ａおよび図４Ｂは、三角形メッシュのデータ形式を示す図である。
【００１０】
三角形メッシュでは、三角形を構成する頂点の情報は、頂点データのインデックス／ポインタ５０１で表現される。この形式のデータは、辺を共有する三角形を示す情報を持たない場合が多いが、必要に応じてその情報を付加して使用される。
【００１１】
コンピューターグラフィクスの描画処理の途中結果や最終結果は通常、外部メモリもしくは内部メモリに配置される。この情報には、画素毎の視点からの距離情報やカラー情報、透明度などが含まれる。ラスタライズ処理された画素毎の情報をメモリ上に配置された中間結果（画素のカラー値や奥行き情報など）に反映する処理を行なう際には、現在の値をメモリから読み込み、処理した結果をメモリに書き戻す処理が必要となる。画素が不透明で、奥行き情報（Ｚ値）を無視する場合で、かつメモリ上に配置された中間結果との混ぜ合わせ処理などが無い場合には、メモリ上に配置された中間結果を読み込まなくても済む場合も有る。その場合は、読み込み処理が無くなって書き込み処理だけになり、時間が半分になるものの、本質的な処理内容は変わらない。以下、中間結果は読み込むものとして説明する。
【００１２】
一般に、１画面の処理結果を得るためには画面のサイズの何倍もの量の画素を処理しなければならず、さらにアニメーション処理の場合などには１秒に数十回も画面を更新することを要求される。そのため、非常に高速に画素のデータを読み込み、書き戻さなければならず、この速度が描画装置の速度を決めてしまうことが多い。
【００１３】
ＤＤＲ  ＳＤＲＡＭ（Double Data Rate SDRAM）に代表される最近のメモリは非常に高速にデータを出し入れできるが、最高性能を引き出すためにはある程度まとまったサイズでデータを読み書きしなければならないという制約が有る。処理速度が高速になり、取り扱うデータ量が多くなるにつれ、このサイズがかなり大きくなってきている。このため、描画装置は、１画面中の所望の１画素の情報だけを読み込んだり、書き込んだりすることはできず、システムで決まるサイズ（４画素〜２５６画素程度）の情報を画素ブロックとしてまとめて読み書きしなければならない。
【００１４】
まとめて読み書きしなければならない画素の領域（画素ブロック）は、何も工夫しなければ縦方向が１画素で横方向に長い領域になる場合がほとんどである。しかし、コンピューターグラフィクスの描画装置は、略正方形の画素ブロックを１度に読み書きするデータ単位としている。正方形とされているのは、三角形の単位でラスタライズ処理が施されて画素毎の処理が行われるからという理由と、平均すれば横長の三角形よりもそうでない三角形が多いという理由とに基づく。つまり、横長の領域よりは正方形に近い領域をまとめて取り扱う方が、三角形の領域外で必要が無いという画素の割合が低くなり、ひいては効率が良くなるからである。このことは一般的に知られている（例えば、特許文献１参照。）。
【００１５】
図５は、画素ブロックの形状が横長である場合を説明するための説明図である。
【００１６】
この図５に示すように、縦１画素×横６４画素の領域（画素ブロック）６０１には、三角形６０２と重なっている有効な画素は８画素程度しか無い。
【００１７】
つまり、描画装置が画素ブロックの画素データをメモリに書き込んでも、殆ど不用な画素データを書き込んでしまうことになる。
【００１８】
図６は、画素ブロックの形状が正方形である場合を説明するための説明図である。
【００１９】
この図６に示すように、縦８画素×横８画素の領域（画素ブロック）７０１には、図５に示す三角形６０２と同じ三角形７０２と重なっている有効な画素は３８画素もある。このように、正方形の画素ブロックの方が横長の画素ブロックに比べて明らかに有効な画素が多くなる。
【００２０】
上記特許文献１では、画素単位の情報に関してではなく、三角形に貼られるテクスチャデータに関する発明が開示されているが、８×８画素のブロック単位でデータが配置されている。これも同様の理由に基づく。
【特許文献１】特表２００１−５０７８３６号公報
【発明の開示】
【発明が解決しようとする課題】
【００２１】
しかしながら、上記特許文献１の描画装置では、メモリバスのバンド幅を無駄に使用してしまうという問題がある。その結果、広いバンド幅が必要となり、バンド幅が狭い場合には、描画処理に不具合が発生してしまう。
【００２２】
即ち、画素ブロックの形状を略正方形にしても、三角形の辺の近くでは一部のデータしか不用なのにその情報もまとめて取り扱うため、読み書きするデータ量が増大し、有効に使用可能なメモリバスバンド幅を低下させている。言い換えれば、一定時間内に読み書きできるデータの総量はメモリバスバンド幅で決まってしまうが、その中で無駄な画素のデータを一緒に読み込んだり書き込んだりしてしまうことで、総量のうち有効なデータ量を減らしていることになる。
【００２３】
図７は、不用なデータを説明するための説明図である。
【００２４】
例えば、三角形７１０が描画されるときには、三角形７１０の辺の一部を含む画素ブロックＢｋの全ての画素データがメモリに書き込まれる。しかし、その画素ブロックＢｋは、三角形７１０に含まれない領域Ｂｋａの画素データと、三角形７１０に含まれる領域Ｂｋｂの画素データとを有する。したがって、画素ブロックＢｋのうち領域Ｂｋｂの画素データだけが必要であるにも関わらず、不用な領域Ｂｋａの画素データまでメモリに書き込んでしまう。
【００２５】
図８は、三角形ストリップの場合においてメモリに不用なデータが書き込まれる様子を説明するための説明図である。
【００２６】
描画装置は、三角形Ｔ0，Ｔ1，Ｔ2，Ｔ3を順に描画しようとする場合、まず、三角形Ｔ0に含まれる画素を有する画素ブロックの画素データをメモリに書き込む。そして、次に、描画装置は、三角形Ｔ1に含まれる画素を有する画素ブロックの画素データをメモリに書き込む。
【００２７】
この場合、三角形Ｔ0と三角形Ｔ1の共有する辺を含む領域８１１では、各画素ブロックは、三角形Ｔ0の書き込み時と、三角形Ｔ1の書き込み時との２回もメモリに書き込まれることとなる。
【００２８】
例えば、領域８１１の画素ブロックＢｋ１は、三角形Ｔ0に含まれる領域Ｂｋ１ａの画素データと、三角形Ｔ1に含まれる領域Ｂｋ１ｂの画素データとを有する。したがって、三角形Ｔ0の書き込み時には、不用な領域Ｂｋ１ｂを含む画素ブロックＢｋ１の全ての画素データがメモリに書き込まれ、三角形Ｔ1の書き込み時にも、不用な領域Ｂｋ１ａを含む画素ブロックＢｋ１の全ての画素データがメモリに書き込まれる。
【００２９】
このように、描画装置は、三角形Ｔ0，Ｔ1，Ｔ2，Ｔ3を順に描画しようとする場合、領域８１１，８１２，８１３に含まれる各画素ブロックを、無駄なデータがその画素ブロックに含まれている状態で、２度もメモリに書き込んでいる。
【００３０】
また、描画装置だけがメモリを独占的に使用している場合よりも、他の装置にもそのメモリが使用される場合、例えば描画装置がシステムＬＳＩ（Large Scale Integration）の中にひとつのユニットとして入っている場合はより深刻である。このような場合は、特定のユニット（装置）がメモリバスを占有して他のユニットの動作を阻害することがないように、量的な規制などが行われることが多い。よって、場合によっては少し時間をかけてもメモリアクセス量を減らす努力をしたほうが、より多くの有効なデータにアクセスでき、描画装置の性能を向上することが可能になる場合が多い。
【００３１】
そこで、無駄なメモリアクセスを減らすために、まとめて処理する画素データのキャッシュシステムを構築することが想定される。三角形ストリップや三角形ファンはもちろん、三角形メッシュのような汎用性のあるデータ形式でも、近くに有る三角形が続けて描画される場合が多く、局所性が有るため、一般的なキャッシュシステムを構成すれば効率をかなり改善できる。
【００３２】
しかしながら、上記特許文献１の描画装置にキャッシュシステムを構築しても、キャッシュのサイズをかなり大きくしないと効果が少なく、さらに回路構成が複雑になるため、キャッシュ回路を実装するのにかなりの開発工数が必要である。キャッシュのサイズを大きくすれば回路規模が大きくなり、開発工数の問題と両方で、これを組み込んだＬＳＩや装置の価格を引き上げてしまうという課題を有する。
【００３３】
そこで、本発明は、かかる問題に鑑みてなされたものであって、高価で複雑な回路構成を有することなくメモリバスバンド幅を有効に利用することができる描画装置を提供することを目的とする。
【課題を解決するための手段】
【００３４】
上記目的を達成するために、本発明に係る描画装置は、描画データをラスタライズ処理して描画する描画装置であって、前記描画データからラスタライズ処理の対象となる第１の三角形領域を特定する三角形特定手段と、前記第１の三角形領域に含まれる画素を有する画素ブロックを特定するブロック特定手段と、前記ブロック特定手段で特定された画素ブロックに、前記第１の三角形領域と連接する第２の三角形領域の画素が含まれるか否かを判別する判別手段と、前記判別手段で含まれると判別されたときには、前記第２の三角形領域の画素を含む画素ブロックをラスタライズ処理して画素データを生成するラスタライズ手段と、前記ラスタライズ手段で生成された画素ブロックの画素データをメモリに書き込む書き込み手段と、前記メモリに書き込まれた画素データに応じた画像を表示させる表示制御手段とを備えることを特徴とする。
【００３５】
これにより、第１及び第２の三角形領域の画素を含む画素ブロックが検出されて、それらの画素を含んだ状態でその画素ブロックがラスタライズ処理されてメモリに書き込まれるため、従来例のように、第１の三角形領域の画素以外の不用なデータをメモリに書き込むことを避けることができる。その結果、大きいサイズのキャッシュメモリや多大な開発工数が必要な複雑な回路の開発および実装を行なうこと無く、画素データの書き込みの際の無駄を排除することにより、メモリバスバンド幅を有効に利用することができる。つまり、高価で複雑な回路構成を有することなく、メモリバスバンド幅を有効に利用することができる。そもそもメモリアクセス時に無駄が生じるのは三角形の辺の部分であるが、本発明では、この無駄を削減することができる。
【００３６】
例えば、三角形ストリップ形式のデータの三角形の数が充分多い場合は、個別の三角形について見ると、３個の辺のうち、２個の辺で問題が改善されるため、全体としてかなりメモリバスバンド幅を低減することができる。図８に示すように、三角形Ｔ1や三角形Ｔ3では３つの辺のうち２つの辺が共有される辺になっており、残り１辺だけについてのみ無駄が解消されないこととなる。
【００３７】
また、前記判別手段は、前記ブロック特定手段で特定された画素ブロックに、前記第１の三角形領域の後に描画すべき前記第２の三角形領域の画素が含まれるか否かを判別することを特徴としてもよい。
【００３８】
これにより、第１の三角形領域をラスタライズ処理の対象、つまり描画対象とするときには、第２の三角形領域が次に描画対象となる第１処理予定の三角形として扱われ、第１の三角形領域を描画対象とするときに、第１処理予定の三角形の画素も含めて画素ブロックがラスタライズ処理される。したがって、不用なデータの代わりに、第１処理予定の三角形の画素データをメモリに書き込むことができ、メモリバスバンド幅を有効に利用することができる。
【００３９】
また、前記判別手段は、前記ブロック特定手段で特定された画素ブロックに、前記第１の三角形領域の前に描画対象とされた前記第２の三角形領域の画素が含まれるか否かを判別することを特徴としてもよい。
【００４０】
これにより、第１の三角形領域をラスタライズ処理の対象、つまり描画対象とするときには、第２の三角形領域が直前に描画された処理済の三角形として扱われ、第１の三角形領域を描画対象とするときに、処理済の三角形の画素も含めて画素ブロックがラスタライズ処理される。したがって、不用なデータの代わりに、処理済の三角形の画素データをメモリに書き込むことができ、メモリバスバンド幅を有効に利用することができる。
【００４１】
ここで、前記三角形特定手段は、さらに、前記描画データからラスタライズ処理の対象となる前記第２の三角形領域を特定し、ブロック特定手段は、さらに、前記三角形特定手段が前記第２の三角形領域を特定したときには、前記第２の三角形領域に含まれる画素を有する画素ブロックを特定し、前記ラスタライズ手段は、さらに、前記三角形特定手段が前記第２の三角形領域を特定したときには、前記ブロック特定手段で特定された画素ブロックのうち、前記判別手段で判別された前記第１及び第２の三角形領域の画素を有する画素ブロックを、ラスタライズ処理の対象から除くことを特徴としてもよい。
【００４２】
これにより、第２の三角形領域がラスタライズ処理の対象、つまり描画対象になるときには、例えば、ブロック特定手段によって第２の三角形領域に含まれる画素を有する複数の画素ブロックが特定されると、その複数の画素ブロックのうち第１の三角形領域の画素を含む画素ブロックはラスタライズ処理の対象から除かれる。したがって、第１の三角形領域が描画対象のときに描画される画素ブロックを、第２の三角形領域が描画対象となるときにもラスタライズ処理してメモリに書き込むことを防いで、メモリバスバンド幅をさらに有効に利用することができる。
【００４３】
なお、本発明は、このような描画装置として実現することができるだけでなく、その方法やプログラム、そのプログラムを格納する記憶媒体、集積回路としても実現することができる。
【発明の効果】
【００４４】
本発明の描画装置は、無駄なメモリアクセスを減らすことができるため、高価で複雑な回路構成を有することなくメモリバスバンド幅を有効に利用することができる。
【発明を実施するための最良の形態】
【００４５】
以下本発明の実施の形態について、図面を参照しながら説明する。
【００４６】
図９は、本発明の実施の形態における描画装置の構成を示すブロック図である。
【００４７】
本実施の形態における描画装置１００は、高価で複雑な回路構成を有することなくメモリバスバンド幅を有効に利用することができるものであって、制御部１１１と、トライアングル検出部１１２と、Ａエッジ検出部１１３と、Ｂエッジ検出部１１４と、Ｃエッジ検出部１１５と、ラスタライズ部１１６と、メモリＲ／Ｗ部１１７と、画素記録モジュールたるメモリ１２０と、描画エンジン１３０とを備える。
【００４８】
このような描画装置１００は、ラスタライズ部１１６でラスタライズ処理する際に３頂点ではなく、４頂点分の情報を用い、トライアングル検出部１１２と各エッジ検出部１１３，１１４，１１５の組み合わせでブロック毎に処理内容を決定し、処理を行なう。これによって、メモリＲ／Ｗ部１１７とメモリ１２０との間のデータの読み書きの量を減らすことができる。
【００４９】
制御部１１１は、三次元で表現された描画リストを取得して、その描画リストを二次元描画データに変換する。描画リストには、三次元上における各座標や、その座標における色、法線（ｎｏｍａｌ）などが含まれている。制御部１１１は、このような描画リストを、二次元上における座標と、その座標における色などとを示す二次元描画データに変換する。
【００５０】
さらに、制御部１１１は、トライアングル検出部１１２、Ａエッジ検出部１１３、Ｂエッジ検出部１１４、およびＣエッジ検出部１１５に対して、二次元描画データを送信して、上記各部によって検出された描画対象の三角形および画素ブロックと、二次元描画データとをラスタライズ部１１６に出力する。
【００５１】
トライアングル検出部１１２は、二次元描画データから描画対象の三角形を検出するとともに、その描画対象の三角形に含まれる画素を有する画素ブロック（三角形画素ブロック）を検出する。つまり、描画対象の三角形に全て含まれる画素ブロックと、その三角形の辺の一部を含む画素ブロックとが三角形画素ブロックとして検出される。三角形の辺の一部を含む画素ブロックには、描画対象の三角形の画素が含まれると共に、その描画対象の三角形には不用な画素も含まれている。
【００５２】
Ａエッジ検出部１１３は、三角形画素ブロックのうち、描画対象の三角形に連接して直前に描画処理の対象とされた三角形（処理済の三角形）の辺上にある画素ブロックを検出する。
【００５３】
つまり、Ａエッジ検出部１１３は、三角形画素ブロックの何れかに、処理済の三角形の画素が含まれるか否かを判別し、含まれると判別された画素ブロックを検出する。ここで、Ａエッジ検出部１１３は、上述の処理済の三角形の画素を含む画素ブロックを検出するときには、描画対象の三角形の３つの頂点と、処理済の三角形の１つの頂点とを用いて検出する。処理済の三角形の１つ頂点とは、描画対象の三角形と処理済の三角形とで共有される辺上にない頂点である。以下、このように検出された画素ブロックをＡ画素ブロックという。
【００５４】
Ｂエッジ検出部１１４は、三角形画素ブロックのうち、描画対象の三角形に連接して次に描画処理される予定の三角形（第１処理予定の三角形）の辺上にある画素ブロックを検出する。
【００５５】
つまり、Ｂエッジ検出部１１４は、三角形画素ブロックの何れかに、第１処理予定の三角形の画素が含まれるか否かを判別し、含まれると判別された画素ブロックを検出する。ここで、Ｂエッジ検出部１１４は、上述の第１処理予定の三角形の画素を含む画素ブロックを検出するときには、描画対象の三角形の３つの頂点と、第１処理予定の三角形の１つの頂点とを用いて検出する。第１処理予定の三角形の１つ頂点とは、描画対象の三角形と第１処理予定の三角形とで共有される辺上にない頂点である。以下、このように検出された画素ブロックをＢ画素ブロックという。
【００５６】
Ｃエッジ検出部１１５は、第１処理予定の三角形の画素を有する画素ブロックのうち、第１処理予定の三角形に連接してその次に描画処理される予定の三角形（第２処理予定の三角形）の辺上にある画素ブロックを検出する。つまり、Ｃエッジ検出部１１５は、第１処理予定の三角形の画素を有する画素ブロックのうち、第２処理予定の三角形の画素を含む画素ブロックを検出する。以下、このように検出された画素ブロックをＣ画素ブロックという。
【００５７】
ラスタライズ部１１６は、二次元描画データと、描画対象の三角形と、その三角形画素ブロックと、Ａ画素ブロックと、Ｂ画素ブロックと、Ｃ画素ブロックとに基づいて、三角形画素ブロックのうち有効な部分に対してラスタライズ処理を行って画素データを生成する。
【００５８】
即ち、ラスタライズ部１１６は、三角形画素ブロックのうち、Ａ画素ブロックを処理対象から省く。そして、ラスタライズ部１１６は、Ａ画素ブロックが省かれた三角形画素ブロックの範囲で、描画対象の三角形と第１処理予定の三角形のそれぞれの少なくとも一部をラスタライズ処理して画素データを生成する。このとき、その三角形画素ブロックに含まれるＢ画素ブロックは、描画対象の三角形の画素と、第１処理予定の三角形の画素とが含まれた状態でラスタライズ処理される。
【００５９】
メモリＲ／Ｗ部１１７は、ラスタライズ部１１７によるラスタライズ処理によって生成された画素データを、Ａ画素ブロックを除く三角形画素ブロックの単位でメモリ１２０に書き込む。
【００６０】
描画エンジン１３０は、表示制御手段として構成されており、メモリ１２０に書き込まれた画素データに応じた画像（描画対象三角形）を表示部２００に表示させる。
【００６１】
このように本実施の形態では、描画対象の三角形の描画処理時に、第１処理予定の三角形の画素もＢ画素ブロックに含めてラスタライズ処理を行い、そのＢ画素ブロックの画素データをメモリ１２０に書き込む。一方、従来では、描画対象の三角形の描画処理時には、第１処理予定の三角形の画素がＢ画素ブロックに含められず、その代わりに不用なデータがＢ画素ブロックに含められ、そのＢ画素ブロックがメモリ１２０に書き込まれる。（なお、不用なデータの部分にはマスクがかけられ、その不用なデータが実際にメモリに書き込まれるわけではないが、そのデータ量に相当する分だけの帯域がメモリバスで使用される）。したがって、本実施の形態では、不用なデータのメモリ１２０への書き込みを防いでメモリバスバンド幅を有効に利用することができる。
【００６２】
また、第１処理予定の三角形の描画処理時には、この第１処理予定の三角形が描画対象の三角形となるため、上述のＢ画素ブロックは、この第１処理予定の三角形に対するＡ画素ブロックとなる。したがって、本実施の形態では、第１処理予定の三角形の描画処理時には、上述のＢ画素ブロックは処理対象から省かれる。一方、従来では、第１処理予定の三角形の描画処理時には、上述と同様に不用なデータを含むＢ画素ブロックがメモリ１２０に書き込まれる。したがって、本実施の形態では、さらにメモリバスバンド幅を有効に利用することができる。
【００６３】
図１０は、本発明の実施の形態における描画装置１００のアルゴリズムを示す概念図である。
【００６４】
図１０において、各三角形は、三角形ＴN-1、三角形ＴN、三角形ＴN+1、三角形ＴN+2の順に描画される。本実施の形態の描画装置１００は、三角形ＴNを描画する際に、Ｎ番目の頂点ＰN、（Ｎ＋１）番目の頂点ＰN+1、および（Ｎ＋２）番目の頂点ＰN+2の、３つの頂点の情報に対して、さらに、次に描画する三角形ＴN+1の頂点である（Ｎ＋３）番目の頂点ＰN+3の情報も加え、４頂点分の情報からラスタライズ処理を行なう。三角形ストリップ（Ｔｒｉａｎｇｌｅ  Ｓｔｒｉｐ）形式の特徴から、１頂点分の情報を加えるだけで２つの連続（連接）した三角形の情報が得られることになる。
【００６５】
図１０に示す三角形ＴNを描画対象の三角形とする場合、上述の処理済の三角形は三角形ＴN-1に相当し、第１処理予定の三角形は三角形ＴN+1に相当し、第２処理予定の三角形は三角形ＴN+2に相当する。また、この場合、トライアングル検出部１１２は、描画対象の三角形ＴNを検出すると共に、ブロック群ＧＢに含まれる各画素ブロックを上述の三角形画素ブロックとして検出する。Ａエッジ検出部１１３は、画素ブロックＢＡを上述のＡ画素ブロックとして検出し、Ｂエッジ検出部１１４は、画素ブロックＢＢを上述のＢ画素ブロックとして検出する。なお、このような画素ブロックは、例えば６４個の画素の集まりによって構成される。したがって、本実施の形態では、描画対象の三角形ＴNを描画するときには、描画対象の三角形ＴNの画素と第１処理予定の三角形ＴN+1の画素とを画素ブロックＢＢに含めて処理を行う。即ち、描画装置１００は、ブロック群ＧＢのうち画素ブロックＢＡを除く範囲で、描画対象の三角形ＴNと第１処理予定の三角形ＴN+1のそれぞれの一部をラスタライズ処理する。
【００６６】
三角形をラスタライズ処理する場合、三角形の範囲に入る画素がどれかを選択し、その画素毎のパラメータを計算することになる。伝統的な方法ではスクリーン上部からスクリーン下部に向かって、横一列に、左端から右端に向かって画素を選択し、それぞれの画素毎のパラメータを計算する。このようにすれば１画素変化した時の各パラメータの変化量を最初に計算しておけば、後はそれを加算していくだけで各パラメータの値を計算できるからである。グラフィクスシステムが開発された初期の頃は、画面全体の情報を記録しておくだけの記憶素子を準備できなかったので、画面の走査線の方向に合わせた描画も意味を持っていたが、今日では処理の方向は意味を持たなくなっている。スクリーン下部から上部に向かって処理しても良いし、右端から左端に向かって処理しても、ランダムに処理しても差し支えない。
【００６７】
メモリ１２０には、グラフィクス・システムを高速にするために、できるだけ高速に大量の情報を読み書きできることが要求される。ＤＤＲ  ＳＤＲＡＭに代表されるような最近の高速大容量メモリ素子は、連続するアドレス空間のデータを連続して読み書きした場合に、より高速に動作するようになっているため、最高性能を目指す場合はこの特徴を利用することになる。
【００６８】
たとえば１画素の情報を４バイトで管理しているグラフィクスシステムで、２５６バイト単位で読み書きした場合に性能が出せるメモリを使う場合、６４画素分の情報をまとめて読み書きすることになる。
【００６９】
背景技術でも説明したように、図５のように縦１画素×横６４画素の領域（画素ブロック）６０１と三角形６０２とでは、有効な画素（三角形６０２と重なっている画素）が８画素程度しか無い。しかし、図６のように縦８画素×横８画素の領域（画素ブロック）７０１にした場合は、図５の三角形６０２と同じ三角形７０２において有効な画素は３８画素となり、明らかに有効な画素が多くなる。
【００７０】
よって、メモリ１２０上の画素配置は縦８画素×横８画素の領域（画素ブロック）状に配置するのが良い。
【００７１】
そのため、本実施の形態では、ラスタライズ処理は単純にスクリーン上部から下部、左端から右端に向かって処理するのではなく、この縦８画素×横８画素の領域（画素ブロック）単位で処理を行なう。このようにすると効率が良いからである。なお、ブロック内の処理順は任意である。
【００７２】
三角形の内部で、領域（画素ブロック）内に三角形の辺がかかっていないものについては、画素ブロック内の画素全てが処理対象になるので特に問題は起らない。２５６バイト単位で読み込んだ画素データは全て有効に用いられ、結果として書き出される２５６バイトのデータも全て意味の有るデータである。
【００７３】
だが、三角形の周辺部で、領域（画素ブロック）内に三角形の辺がかかっているもの、つまり領域の一部が三角形の内部で描画対象となり、それ以外の部分が三角形の外部で従来手法では描画対象外となるようなブロックに関しては、２５６バイト単位で読み込んだデータのうち、三角形の外部の画素に関しては必要の無いデータである。書き戻す際にもこのデータは本来不用であり、有効なデータの割合が小さくなる。
【００７４】
描画装置１００がシステムＬＳＩの中にユニットとして組み込まれ、他のコアと協調動作しているような場合は、特定のユニットがメモリバスを占有して他のユニットの動作を阻害することがないように、メモリアクセスに対して量的な規制などが行われていることが多い。例えば、無駄なアクセスも全てアクセス量として積算され、限度を超えると一定時間アクセスができなくなるなどのペナルティが課せられる場合がある。そのため、上述の有効データの割合が少なくなるという問題は深刻である。
【００７５】
この問題を解決するため、本発明の描画装置１００では４頂点（頂点ＰN、頂点ＰN+1、頂点ＰN+2、頂点ＰN+3）の情報を利用して、領域（画素ブロック）内にある描画対象の三角形（三角形ＴN）の画素に加えて、その画素ブロック内にある、第１処理予定の三角形（三角形ＴN+1）の画素の処理も同時あるいは連続して行なう。なお、このような画素ブロックは、上述のＢ画素ブロックＢＢである。そのＢ画素ブロックＢＢを処理するタイミングは、第１処理予定の三角形ＴN+1の処理時でも良い。この場合には、描画対象の三角形ＴNの処理時に、上述のＢ画素ブロックＢＢの画素処理を行なわない。以下では前者、つまり第１処理予定の三角形ＴN+1の画素が、描画対象の三角形ＴNの画素を有する画素ブロック内に含まれていたら、描画対象の三角形ＴNの処理時に、その画素ブロック内における第１処理予定の三角形ＴN+1の画素も同時あるいは連続して処理するものとして説明する。
【００７６】
描画対象の三角形の３頂点および次に描画する予定の三角形（第１処理予定の三角形）の１頂点の４頂点の情報から、この２つの三角形のパラメータを計算することが可能である。即ち、上述のように、トライアングル検出部１１２は、画素ブロックの全部または一部が描画対象の三角形の内部であるものを上述の三角形画素ブロックとして検出する。また、Ａエッジ検出部１１３は、描画対象の三角形（三角形ＴN）と一つ前に描画した処理済の三角形（三角形ＴN-1）との間で共有される辺（頂点ＰNと頂点ＰN+1とを結ぶ辺）の少なくとも一部が三角形画素ブロック内に入っているかどうかを検出する。Ｂエッジ検出部１１４は、描画対象の三角形（三角形ＴN）と次に描画する予定の三角形（第１処理予定の三角形ＴN+1）との間で共有される辺（頂点ＰN+1と頂点ＰN+2とを結ぶ辺）の少なくとも一部が三角形画素ブロック内に入っているかどうかを検出する。そして、Ｃエッジ検出部１１５は、次に描画する予定の三角形（第１処理予定の三角形ＴN+1）とさらにその次に描画する予定の三角形（第２処理予定の三角形ＴN+2）との間で共有される辺（頂点ＰN+2と頂点ＰN+3とを結ぶ辺）の少なくとも一部が、第１処理予定の三角形ＴN+1の画素を有する画素ブロック内に入っているかどうかを検出する。
【００７７】
したがって、トライアングル検出部１１２で検出された三角形画素ブロックのうち、Ａエッジ検出部１１３で検出された画素ブロック（上述のＡ画素ブロックＢＡ）を除いたものを描画処理対象にする。これは、一つ前に描画した処理済の三角形（三角形ＴN-1）の処理時点で既にこのＡ画素ブロックＢＡは描画済みであって、２度描画するのを避けるためである。
【００７８】
上述の描画処理対象の画素ブロックのうち、Ｂエッジ検出部１１４で検出された画素ブロック（上述のＢ画素ブロックＢＢ）は、描画対象の三角形（三角形ＴN）と次に描画する三角形（第１処理予定の三角形ＴN+1）とで共有される辺上にある。このため、描画対象の三角形（三角形ＴN）に加えて次に描画する予定の三角形（第１処理予定の三角形ＴN+1）も、このＢ画素ブロックＢＢ内だけは先行して描画しておく。多くの場合、Ｂ画素ブロックＢＢ内にはこの２つの三角形しか存在せず、２つの三角形だけを描画するだけでＢ画素ブロックＢＢ全体の処理を終えることができる。そのため、無駄なメモリアクセスを減らすことができる。
【００７９】
描画処理対象の画素ブロックのうち、３つのエッジ検出部に検出されないものは、描画対象の三角形内部に含まれる画素ブロックであり、これらの画素ブロックは、従来通り描画される。
【００８０】
図１１は、本実施の形態における描画装置１００の動作を示すフローチャートである。
【００８１】
描画装置１００の制御部１１１は、まず、描画リストを取得して（ステップＳ１００）、その描画リストを二次元描画データに変換する（ステップＳ１０２）。そして、トライアングル検出部１１２は、二次元描画データから描画対象の三角形、例えば、図１０中の三角形ＴNを検出する（ステップＳ１０４）。
【００８２】
さらに、トライアングル検出部１１２は、その描画対象の三角形ＴNに含まれる画素を有する画素ブロックを、図１０のブロック群ＧＢ内にある上述の三角形画素ブロックとして検出する（ステップＳ１０６）。
【００８３】
Ａエッジ検出部１１３は、三角形画素ブロックのうち、描画対象の三角形ＴNに連接する処理済の三角形ＴN-1の画素を含む画素ブロックを、Ａ画素ブロックＢＡとして検出する（ステップＳ１０８）。
【００８４】
その結果、ラスタライズ部１１６は、描画対象の三角形ＴNに属する三角形画素ブロックのうち、Ａ画素ブロックＢＡを処理対象から省き、その残りの画素ブロックを描画処理対象に設定する（ステップＳ１１０）。
【００８５】
Ｂエッジ検出部１１４は、描画対象の三角形ＴNに連接する第１処理予定の三角形ＴN+1があるか否か、つまり、三角形画素ブロックの何れかに、第１処理予定の三角形ＴN+1の画素が含まれているか否かを判別する（ステップＳ１１２）。
【００８６】
ここで、第１処理予定の三角形ＴN+1があると判別したときには（ステップＳ１１２のＹ）、ラスタライズ部１１６は、ステップＳ１１０で設定した描画処理対象の画素ブロックの範囲で、描画対象の三角形ＴNと第１処理予定の三角形ＴN+1のそれぞれの少なくとも一部に対してラスタライズ処理を行なう（ステップＳ１１４）。つまり、ラスタライズ部１１６は、従来例と異なり、描画対象の三角形ＴNと第１処理予定の三角形ＴN+1の画素がＢ画素ブロックＢＢに含まれる形で、そのＢ画素ブロックＢＢに対してラスタライズ処理を行なう。
【００８７】
一方、第１処理予定の三角形ＴN+1がないと判別したときには（ステップＳ１１２のＮ）、ラスタライズ部１１６は、ステップＳ１１０で設定した描画処理対象の画素ブロックの範囲で、描画対象の三角形ＴNの少なくとも一部に対してラスタライズ処理を行なう（ステップＳ１１６）。
【００８８】
そして、メモリＲ／Ｗ部１１７は、ステップＳ１１４またはステップＳ１１６によるラスタライズ処理により生成された画素データを、画素ブロック単位でメモリ１２０に書き込む（ステップＳ１１８）。描画エンジン１３０は、メモリ１２０に書き込まれた画素データに応じた画像を表示部２００に表示させる（ステップＳ１２０）。
【００８９】
なお、ここまでの説明では簡単のために例外的な処理を省略したが、実際に描画装置を実装するためにはそれらも考慮しなければならない。例えば、描画対象となる最初の三角形（Ｎ＝０）には一つ前の三角形は存在しないため、最初の三角形と直前の三角形とで共有される辺は存在しない。また、最後の三角形（Ｎ＝ＮＵＭ−１）の場合には次の三角形は存在しないため、最後の三角形と直後の三角形とで共有される辺は存在しない。
【００９０】
また、頂点の画素ブロック（図１０に示す画素ブロックＢＸや画素ブロックＢＹ）には通常３個以上の三角形の画素が入るため、２個の三角形だけを用いてもその画素ブロックの全ての領域を塗り潰せない場合が多い。そこで、次に説明する処理を行なえばよい。ただし、頂点の画素ブロックは比較的簡単に検出できるため、逐次的に描画処理していく場合に２画素ブロック程度を保持してキャッシュ的にその２画素ブロックを扱った方が実装が簡単になり、性能が少し向上する可能性が有る。
【００９１】
三角形が小さい場合や、その角度が鋭い鋭角の場合は、１個の画素ブロックに３個以上の三角形の画素が入る場合がある。これは、Ａエッジ検出部１１３とＢエッジ検出部１１４、あるいはＢエッジ検出部１１４とＣエッジ検出部１１５によって同時に検出されるような領域（画素ブロック）が、上述のような３個以上の三角形の画素を含む画素ブロックに相当する。頂点が入っている画素ブロック以外でも頻度は少ないが有り得るので注意が必要である。
【００９２】
このような場合は、その画素ブロック内に関しては描画対象の三角形ＴNや、それ以前に描画した三角形ＴN-1については既に描画済みである。一方、次に描画する三角形ＴN+1の部分は、次に三角形ＴN+2を描画する際には既に描画が終わっているものとして取り扱われるため、今回描画しておかないといけない。例えば、図１に示す画素ブロックＢＹを、描画対象の三角形ＴNの描画時に、三角形N+2の一部を含めて描画しておく。このような場合には、描画装置１００は、画素ブロックＢＹ全体の処理が終わっていない中途半端な状態で、その画素ブロックＢＹを一度メモリ１２０に書き込み、またそれを読み出して続きを行なう。つまり、三角形ＴNや三角形ＴN+1のそれぞれの一部を含む画素ブロックＢＹをメモリ１２０に書き込み、またそれを読み出して三角形ＴN+2の一部をその画素ブロックＢＹに含める。このため、従来の手法と効率は変わらないことになる。このような場合専用にキャッシュシステムを導入すれば状況は改善されるが、頻度が少ない場合は改善効果があまり見込めないうえに、開発工数も大きくなるので状況に応じた総合的な判断が必要である。
【００９３】
なお、本実施の形態では、トライアングル検出部１１２、Ａエッジ検出部１１３、Ｂエッジ検出部１１４、およびＣエッジ検出部１１５を、ラスタライズ部１１６の外部に設けたが、内部に実装してもよい。また、本実施の形態では、トライアングル検出部１１２、Ａエッジ検出部１１３、Ｂエッジ検出部１１４、およびＣエッジ検出部１１５をそれぞれ分離させたが、分離させずに１つのモジュールに時分割で各画素ブロックを検出させてもよい。
【００９４】
（変形例１）
上記実施の形態では、描画対象の三角形ＴNと、次に描画予定の三角形ＴN+1とで共有される辺の一部が入っている領域（Ｂ画素ブロックＢＢ）の描画処理を、描画対象の三角形ＴNを描画している際に同時に行なった。
【００９５】
本変形例１に係る描画装置は、描画対象の三角形ＴNを描画する際には、そのＢ画素ブロックＢＢの描画処理をせずに、次に描画予定の三角形ＴN+1を描画する際に、そのＢ画素ブロックＢＢの描画処理を行なう。即ち、そのＢ画素ブロックＢＢの範囲において、両三角形の画素を同時あるいは連続して描画する。
【００９６】
また、この場合には、本変形例１に係る描画装置は、描画対象の三角形ＴNを描画する際には、トライアングル検出部１１２で検出された三角形画素ブロックの何れかに、その三角形ＴNの前に描画対象とされた三角形ＴN-1の画素が含まれているか否かを判別する。つまり、描画装置は、描画対象の三角形ＴNを描画する際に、三角形ＴN-1の画素が含まれているＡ画素ブロックＢＡを検出して、その三角形ＴNの画素と三角形ＴN-1の画素とを含むＡ画素ブロックＢＡをラスタライズ処理して描画する。
【００９７】
（変形例２）
上記実施の形態では、描画装置１００は、三角形ストリップのデータ形式の描画データをラスタライズ処理して描画した。
【００９８】
本変形例に係る描画装置は、三角形ファンのデータ形式の描画データをラスタライズ処理して描画する。このようなデータ形式であっても、上記実施の形態と同様の効果を得ることができる。
【００９９】
（変形例３）
上記実施の形態では、描画装置１００は、三角形ストリップのデータ形式の描画データをラスタライズ処理して描画した。
【０１００】
本変形例に係る描画装置は、三角形ストリップと三角形ファンとを途中で変更できる形式（所謂Ｔｒｉａｎｇｌｅ  Ｓｎａｋｅ）の描画データをラスタライズ処理して描画する。このようなデータ形式であっても、上記実施の形態と同様の効果を得ることができる。
【０１０１】
（変形例４）
上記実施の形態および変形例１では、２つの三角形に共有される辺の一部が入っている領域（画素ブロック）を、２つの三角形のうち描画順が早い方を描画している時に同時に描画したり、２つの三角形のうち描画順が遅い方を描画している時に同時に描画したりした。即ち、上記実施の形態および変形例１では、上記画素ブロックを描画するタイミングを、三角形の描画順に基づいて一意に決めた。
【０１０２】
本変形例に係る描画装置は、別途与えられた情報や乱数などに従って、上記画素ブロックを描画するタイミングを個別に決定する。
【０１０３】
なお、どちらの三角形を描画する際にも上記画素ブロックを同時には描画せず、別途、辺の一部が入っている画素ブロックだけを描画するような構成も考えられるのは言うまでもない。
【０１０４】
（変形例５）
上記実施の形態では、描画装置１００は、三角形ストリップのデータ形式の描画データをラスタライズ処理して描画した。
【０１０５】
本変形例に係る描画装置は、三角形メッシュのデータ形式の描画データをラスタライズ処理して描画する。三角形メッシュの場合は、ある三角形と辺を共有する三角形は最大三個有り、必ずしもそれらを連続して描画していくわけではないので、上記実施の形態や変形例１のように描画順だけで、上記辺上にある画素ブロックを何れの三角形の描画時に描画するかを決めるわけにはいかない。
【０１０６】
そこで、本変形例に係る描画装置は、それぞれの辺について、その辺を共有する２つの三角形のうち何れの三角形を描画する際に、その辺上にある画素ブロックを一緒に描画すべきかを示す情報を取得する。そして、描画装置は、その取得した情報に基づいて、上記辺上にある画素ブロックを何れの三角形の描画時に描画するのかを決定する。もちろん、三角形の番号などから計算で自動的に決めてもよい。
【０１０７】
（変形例６）
上記実施の形態およびその変形例１〜５では４個の頂点を扱うだけなので、同時に処理できる辺は１個だけである。大雑把に言えば、３つの辺のうち２個は共有させて処理できるが、残り１個はそのような処理ができない。
【０１０８】
この問題を解決するために、本変形例に係る描画装置は、最大で６個の頂点の情報を利用し、共有する３つの辺全てを処理する。即ち、描画装置は、上記実施の形態およびその変形例１〜５で行なってきたような処理を３つの辺でそれぞれ行なう。
【０１０９】
図１２は、本変形例に係る描画装置の処理を説明するための説明図である。
【０１１０】
この図１２に示すような三角形ストリップ（頂点Ｐ0、頂点Ｐ1、頂点Ｐ2、頂点Ｐ3、頂点Ｐ4、頂点Ｐ5、および頂点Ｐ6）を考えた時、三角形ストリップを構成する三角形（三角形Ｔ0、三角形Ｔ1、三角形Ｔ2、三角形Ｔ3、および三角形Ｔ4）の間で共有される辺ではバス帯域を無駄にする問題が回避されるが、そのままではそれ以外の辺では従来通りである。
【０１１１】
そこで本変形例に係る描画装置は、例えば頂点Ｐ0と頂点Ｐ1を結ぶ辺などの残された辺も処理するために、それらの辺を共有する三角形の頂点（頂点ＰA、頂点ＰB、頂点ＰC、頂点ＰD、頂点ＰE、頂点ＰF、および頂点ＰG）の情報を利用し、変形例５のように処理する。
【０１１２】
三角形ストリップ形式の場合、その三角形ストリップ形式のグラフィックスデータにおいて、三角形ストリップを構成する特定の三角形の頂点に対して、その三角形と共有する辺を有する他の三角形の頂点を入れておけばよい。例えば、三角形Ｔ0の頂点Ｐ0、頂点Ｐ1、および頂点Ｐ2に対して、頂点ＰAを入れておく。これにより、描画装置は頂点ＰAを指定することができるとともに、データ形式を簡単にすることができる。
【０１１３】
ここで、各三角形で共有される辺上にある画素ブロックを、どちら側の三角形を描画する際に描画するのかを示す描画情報を別途与えても良い。また、描画対象の三角形以外の他の三角形を描画しない場合は、描画対象の三角形と共有される辺を有する他の三角形の頂点の情報は不用になることを利用してもよい。即ち、描画対象の三角形の処理時に、他の三角形と共有される辺上にある画素ブロックを描画するものだけ、グラフィックスデータに他の三角形の頂点を入れておき、そうでない場合は、グラフィックスデータにダミーの頂点を入れておく。これにより、描画装置は、他の三角形の頂点やダミーの頂点を指定することができ、データ形式を簡単にすることができる。
【０１１４】
なお、ダミーの頂点に２種類を設け、「描画対象の三角形と他の三角形とで共有される辺上の画素ブロックは他の三角形を描く時に処理することを示す頂点（ＯＴＨＥＲ）」と、「この辺は共有されていないことを示す頂点（ＮＯＮＥ）」とを区別しておくべきである。つまり、頂点（ＮＯＮＥ）は、描画対象の三角形の一辺を共有する他の三角形がないことを示す非共有情報であり、頂点（ＯＴＨＥＲ）は、他の三角形の画素を含むと判別された画素ブロックをラスタライズ処理の対象から除き、その画素ブロックのラスタライズ処理を他の三角形の処理時に行なうべきことを示す除外情報である。したがって、描画装置は、ダミーの頂点が頂点（ＯＴＨＥＲ）を示す場合には、他の三角形の画素を含む画素ブロック、つまり共有される辺が入っている画素ブロックに対するラスタライズ処理を禁止し、その領域（画素ブロック）を描画しない。そして、描画装置は、ダミーの頂点が頂点（ＮＯＮＥ）を示す場合には、その頂点（ＮＯＮＥ）に対応する描画対象の三角形の一辺上にある画素ブロックには、他の三角形領域の画素は含まれないと判別し、描画対象の三角形の画素のみを含む画素ブロックを描画する。
【０１１５】
図１３は、ダミーの頂点を説明するための説明図である。
【０１１６】
描画対象の三角形Ｔ0に対してＯＴＨＥＲ頂点ＰO1がある場合、描画装置は、描画対象の三角形Ｔ0を描画するときに、頂点Ｐ0と頂点Ｐ2を結ぶ辺上にある画素ブロックを描画処理せず、ＯＴＨＥＲ頂点ＰO1を有する三角形を描画するときに、先に描画対象であった三角形Ｔ0の一部をその画素ブロックに含めて、その画素ブロックを描画処理する。
【０１１７】
また、描画対象の三角形Ｔ3に対してＮＯＮＥ頂点がある場合、描画装置は、描画対象の三角形Ｔ3を描画するときに、頂点Ｐ3と頂点Ｐ5を結ぶ辺上にある画素ブロックを描画処理する。
【０１１８】
頂点Ｐ0、頂点ＰA、頂点Ｐ1、ＯＴＨＥＲ頂点ＰO1、頂点Ｐ2、頂点ＰC、頂点Ｐ3、ＯＴＨＥＲ頂点ＰO2、頂点Ｐ4、ＮＯＮＥ頂点、頂点Ｐ5、頂点ＰF、頂点Ｐ6、および頂点ＰGを含む頂点データを可変長データとする。そして、通常の頂点（頂点Ｐ0、頂点Ｐ1、頂点Ｐ2、頂点Ｐ3、頂点Ｐ4、頂点Ｐ5、および頂点Ｐ6）、および共有する三角形の頂点（頂点ＰA、頂点ＰC、頂点ＰF、および頂点ＰG）のデータの長さと、ダミー頂点（ＯＴＨＥＲ頂点ＰO1、ＯＴＨＥＲ頂点ＰO2、およびＮＯＮＥ頂点）のデータの長さとを異なるようにすればダミー頂点のサイズを最小にすることができる。必ずしもダミー頂点が通常の頂点と同じデータサイズを持つ必要は無い。
【０１１９】
なお、本変形例では、描画データの形式として三角形ストリップを例に挙げて説明したが、三角形ファンや、Ｓｎａｋｅ、三角形メッシュなどでもよい。
【０１２０】
以上、本発明について実施の形態およびその変形例を用いて説明したが、本発明はこれらに限定されるものではない。
【０１２１】
例えば、本実施の形態およびその変形例では、全て三角形について説明したが、四角形以上の多角形でもよい。
【０１２２】
また、本実施の形態およびその変形例に係る描画装置を、専用の半導体集積回路（ＬＳＩ）やその一部として構成してもよく、トランジスタやリレー素子など別の手段で描画装置を構成してもよい。
【産業上の利用可能性】
【０１２３】
本発明の描画装置は、高価で複雑な回路構成を有することなくメモリバスバンド幅を有効に利用することができるものであって、３次元コンピューターグラフィクスの処理として有効なだけではなく、２次元の処理方法としても有用である。したがってこれらの機能を含む家電機器や、ゲーム機、パーソナルコンピュータなどの分野で利用される可能性が有る。
【図面の簡単な説明】
【０１２４】
【図１】図１は、三角形ストリップのデータ形式を視覚的に示す図である。
【図２】図２は、三角形ファンのデータ形式を視覚的に示す図である。
【図３】図３は、スネークのデータ形式を視覚的に示す図である。
【図４Ａ】図４Ａは、三角形メッシュのデータ形式を視覚的に示す図である。
【図４Ｂ】図４Ｂは、三角形メッシュのデータ形式を示す図である。
【図５】図５は、画素ブロックの形状が横長である場合を説明するための説明図である。
【図６】図６は、画素ブロックの形状が正方形である場合を説明するための説明図である。
【図７】図７は、不用なデータを説明するための説明図である。
【図８】図８は、三角形ストリップの場合においてメモリに不用なデータが書き込まれる様子を説明するための説明図である。
【図９】図９は、本発明の実施の形態における描画装置の構成を示すブロック図である。
【図１０】図１０は、本発明の実施の形態における描画装置のアルゴリズムを示す概念図である。
【図１１】図１１は、本発明の実施の形態における描画装置の動作を示すフローチャートである。
【図１２】図１２は、本発明の実施の形態における第６の変形例に係る描画装置の処理を説明するための説明図である。
【図１３】図１３は、本発明の実施の形態における第６の変形例に係るダミー頂点を説明するための説明図である。
【符号の説明】
【０１２５】
１００    描画装置
１１１    制御部
１１２    トライアングル検出部
１１３    Ａエッジ検出部
１１４    Ｂエッジ検出部
１１５    Ｃエッジ検出部
１１６    ラスタライズ部
１１７    メモリＲ／Ｗ部
１２０    メモリ
１３０    描画エンジン
２００    表示部
【図１】
0004777893.tif 000002
【図２】
0004777893.tif 000003
【図３】
0004777893.tif 000004
【図４Ａ】
0004777893.tif 000005
【図４Ｂ】
0004777893.tif 000006
【図５】
0004777893.tif 000007
【図６】
0004777893.tif 000008
【図７】
0004777893.tif 000009
【図８】
0004777893.tif 000010
【図９】
0004777893.tif 000011
【図１０】
0004777893.tif 000012
【図１１】
0004777893.tif 000013
【図１２】
0004777893.tif 000014
【図１３】
0004777893.tif 000015