(57)【特許請求の範囲】
【請求項１】
データ群により特定される表現対象物をコンピュータグラフィックスにより表現するために、当該データ群のうち複数のデータについて、２次元平面上に投写した場合の位置成分と描画形状を特定するその他の成分とを抽出し、各データの位置成分を頂点とする多角形を、当該画像平面上に当該データについての描画形状を特定するその他の成分に応じて定められている描画形状で、複数描画する画像描画装置であって、
２次元平面上の各画素の画素データ値を格納するためのフレームメモリと、
画像を描画するために画素データを前記フレームメモリに書き込む機能を有し、フレームメモリを先頭から所定画素数毎に区分した場合における１区分であって、１ラインからなる１区分に対しての書き込みを一括して行う書込み手段と、
前記各区分のうちいずれかの先頭画素又は最終画素を前記多角形の少なくとも１つの頂点とするように前記複数のデータを選出するデータ選出手段とを備える
ことを特徴とする画像描画装置。
【請求項２】
前記画像描画装置は、更に、前記区分の先頭画素または最終画素に関わりなく多角形の頂点のデータを選出する初期データ選出手段を備え、
前記データ選出手段は、前記初期データ選出手段が選出したデータによって形成される元の多角形を２以上の小型の多角形で構成するためにデータを選出する場合に、前記小型の多角形それぞれを構成する頂点の少なくとも１つが、前記各区分の先頭画素又は最終画素となるように、且つ、前記元の多角形を構成する辺上にあるように前記小型の多角形の頂点のデータを選出する
ことを特徴とする請求項１記載の画像描画装置。
【請求項３】
前記データ選出手段は、頂点の１つが互いに接している２つの小型の多角形の当該各頂点が、隣接する区分の最終画素と先頭画素となるように各頂点のデータを選出する
ことを特徴とする請求項２記載の画像描画装置。
【請求項４】
前記データ選出手段は、前記小型の多角形それぞれの頂点の１つが、当該頂点が存在する前記元の多角形を構成する辺の、中点近傍の点であるように当該頂点のデータを選出する
ことを特徴とする請求項２記載の画像描画装置。
【請求項５】
前記データ選出手段は、選出する頂点のデータのうち少なくとも２個の頂点両方が前記各区分の先頭画素または最終画素のどちらかとなるように、かつ当該２個の頂点によって形成される線分上の全ての画素が、前記２個の頂点が先頭画素にある場合には先頭画素となるように、前記２個の頂点が最終画素にある場合には最終画素となるようにデータを選出する
ことを特徴とする請求項２記載の画像描画装置。
【請求項６】
前記元の多角形は三角形であり、前記データ選出手段は、前記元の多角形が三角形である場合に、当該三角形を構成する各辺上の１点計三点のデータを選出し、当該三点のうち２点を結んで形成される線分で前記元の三角形を分割し、前記元の三角形を分割して生成された４つの三角形で構成する
ことを特徴とする請求項２又は４記載の画像描画装置。
【請求項７】
前記元の多角形は四角形であり、前記データ選出手段は、前記元の多角形が四角形である場合に、元の四角形を構成する各辺上の１点計４点と前記元の四角形内の１点とのデータを選出し、当該１点と前記４点を結ぶ線分によって前記元の四角形を分割し、前記元の四角形を分割されて生成された４つの四角形で構成する
ことを特徴とする請求項２又は４記載の画像描画装置。
【請求項８】
前記所定画素数は、前記フレームメモリに接続されるデータ入出力に用いる信号線の数を、１画素を構成するデータのビット数で除算して得る
ことを特徴とする請求項１記載の画像描画装置。
【請求項９】
前記所定画素数は、前記フレームメモリへの書込みをバースト転送により行う場合に、バースト転送で転送されるデータ単位のビット数を画素のビット数で除算して得る
ことを特徴とする請求項１記載の画像描画装置。
【請求項１０】
データ群により特定される表現対象物をコンピュータグラフィックスにより表現するために、当該データ群のうち複数のデータについて、２次元平面上に投写した場合の位置成分と描画形状を特定するその他の成分とを抽出し、各データの位置成分を頂点とする多角形を、当該画像平面上に当該データについての描画形状を特定するその他の成分に応じて定められている描画形状で、複数描画する画像描画装置における多角形の頂点選出方法であって、
ここで前記画像描画装置は、２次元平面上の各画素の画素データ値を格納するためのフレームメモリと、画像を描画するために画素データを前記フレームメモリに書き込む機能を有し、フレームメモリを先頭から所定画素数毎に区分した場合における１区分であって、１ラインからなる１区分に対しての書き込みを一括して行う書込み手段とを備える画像描画装置であり、
前記頂点選出方法は、前記各区分のうちいずれかの先頭画素又は最終画素を前記多角形の少なくとも１つの頂点とするように前記複数のデータを選出するデータ選出ステップを含む
ことを特徴とする頂点選出方法。
【請求項１１】
データ群により特定される表現対象物をコンピュータグラフィックスにより表現するために、当該データ群のうち複数のデータについて、２次元平面上に投写した場合の位置成分と描画形状を特定するその他の成分とを抽出し、各データの位置成分を頂点とする多角形を、当該画像平面上に当該データについての描画形状を特定するその他の成分に応じて定められている描画形状で、複数描画する画像描画装置のコンピュータに実行させるプログラムであって、
ここで前記画像描画装置は、２次元平面上の各画素の画素データ値を格納するためのフレームメモリと、画像を描画するために画素データを前記フレームメモリに書き込む機能を有し、フレームメモリを先頭から所定画素数毎に区分した場合における１区分であって、１ラインからなる１区分に対しての書き込みを一括して行う書込み手段とを備える画像描画装置であり、
前記プログラムにおける頂点選出手順は、前記各区分のうちいずれかの先頭画素又は最終画素を前記多角形の少なくとも１つの頂点とするように前記複数のデータを選出するデータ選出ステップを含むこと
ことを特徴とする頂点選出プログラム。
【請求項１２】
データ群により特定される表現対象物をコンピュータグラフィックスにより表現するために、当該データ群のうち複数のデータについて、２次元平面上に投写した場合の位置成分と描画形状を特定するその他の成分とを抽出し、各データの位置成分を頂点とする多角形を、当該画像平面上に当該データについての描画形状を特定するその他の成分に応じて定められている描画形状で、複数描画する集積回路であって、
２次元平面上の各画素の画素データ値を格納するためのフレームメモリと、
画像を描画するために画素データを前記フレームメモリに書き込む機能を有し、フレームメモリを先頭から所定画素数毎に区分した場合における１区分であって、１ラインからなる１区分に対しての書き込みを一括して行う書込み手段と、
前記各区分のうちいずれかの先頭画素又は最終画素を前記多角形の少なくとも１つの頂点とするように前記複数のデータを選出するデータ選出手段とを備える
ことを特徴とする集積回路。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、３次元ポリゴン画像を表示する画像描画装置に関し、特に再分割多角形を用いて画像を表示する技術に関する。
【背景技術】
【０００２】
近年、リアルタイム３ＤＣＧ（3-Dimension Computer Graphics）技術を用いた画像描画装置において、表示ポリゴン数や、表現力の著しい向上が図られている。ポリゴンとは、基本的に多角形のことであるが、３ＤＣＧの世界においては三角形あるいは四角形であることが多い。３ＤＣＧでは、無数のポリゴンを組み合わせることで物体形状を表現する。このポリゴンが細かければ細かいほど、即ち、表示ポリゴン数が多ければ多いほどより滑らかで詳細な三次元画像を表現できるようになる。
【０００３】
ところで、３ＤＣＧ技術を用いた画像描画装置では、基本的にＣＰＵ（Central Processing Unit）の指示によってＧＥ（GraphicsEngine）が実際にディスプレイに表示する画像のデータを作成する。ＧＥに画像データの作成を行わせるのは、ＣＰＵがアニメーションなどによって変化する画像の演算を行ってＧＥに指示を出したりするとＣＰＵからＧＥへのどの位置のどの画素は何色でといったデータを送ることになるのでデータ転送量の増大を招くために表示が遅れる可能性が出てくるからである。
【０００４】
そこで、ＣＰＵは、例えば物体表面の３点Ａ、Ｂ、Ｃを結ぶ三角形部分を赤色で描けといった簡単な指示のみをＧＥに出す。そしてＧＥは、三角形内の各画素データを演算で求め、三角形内部に相当するフレームメモリ内の各画素位置に、赤色の各画素データを格納する。処理をＣＰＵとＧＥに分散することで、表示の遅れを極力、回避する。このときＧＥは、三角形ＡＢＣが実は曲面だったりすることもあるので、このような場合には、滑らかさを表現するために与えられた三角形を分割し、複数の三角形にして、それぞれの三角形についてその画素データを生成することがある。この分割の技術にはSubdivisionSurfaceと呼ばれるものがあり、分割して生成された多角形を用いて元の多角形をより細やかに表現する。
【０００５】
どのように分割するかの分割方法に関しては、特許文献１に記されたものがあり、もとの多角形の形状に基づいて多角形を分割するための補間点を選出する技術が開示されている。例えば、多角形を構成する辺の中点を選出し、その中点を結んで形成される線分によって分割する。
ＧＥは、分割された多角形ごとにその画素データをフレームメモリに書き込み、そのフレームメモリのデータを読み出してディスプレイは画像を表示する。このフレームメモリへの書込みは所定画素数の単位で行われる。また、画像の再描画においては、各多角形ごとに行われるので、変化がある部分だけの書き換えだけで再描画を行える。
【特許文献１】
日本国特許公開２００１−６７４９１号公報
【発明の開示】
【発明が解決しようとする課題】
【０００６】
従来においては、上記特許文献１に示すように分割点を元の多角形の形状に基づいて決定しており、分割点を容易に決定することができるという長所を有するが、フレームメモリへのアクセス効率を考慮せずに分割していたために描画性能、特に描画速度が低下する恐れがある。
そこで、本発明においては、描画性能の低下を抑えるように分割点を決定できる画像描画装置を提供することを目的とする。
【０００７】
【課題を解決するための手段】
本発明に係る画像描画装置は、データ群により特定される表現対象物をコンピュータグラフィックスにより表現するために、当該データ群のうち複数のデータについて、２次元平面上に投写した場合の位置成分と描画態様を特定するその他の成分とを抽出し、各データの位置成分を頂点とする多角形を、当該画像平面上に当該データについての描画態様を特定するその他の成分に応じて定められている描画態様で、複数描画する画像描画装置であって、２次元平面上の各画素の画素データ値を格納するためのフレームメモリと、画像を描画するために画素データを前記フレームメモリに書き込む機能を有し、フレームメモリを先頭から所定画素数毎に区分した場合における１区分に対しての書き込みを一括して行う書込み手段と、前記各区分の先頭画素又は最終画素を前記多角形の少なくとも１つの頂点とするように前記複数のデータを選出するデータ選出手段とを備えることを特徴としている。
【０００８】
ここでいうその他の成分とは、２次元の位置成分以外の成分のことであり、例えば、３次元即ち高さの位置成分であったり、あるいは色の成分であったりする。
【発明の効果】
これにより、画像描画装置は、多角形の頂点の少なくとも１点をフレームメモリへの一括して書き込める連続した画素の先頭画素、もしくは最終画素とすることができる。よって、描画速度の低下を抑えることができる。というのも、フレームメモリへの書込みが所定画素単位で行われるために、頂点がその書込み単位の中ほどにあった場合、通常その頂点は複数のポリゴンで共有されているため、その頂点が含まれている書込み画素の領域においてはその点を頂点としているポリゴンごとに書込みが行われるためフレームメモリへのアクセスが当該領域において重複することになる。この重複をなるべく抑えることでフレームメモリへのアクセス回数を減らし描画性能の低下を抑えることができる。
【０００９】
また、前記画像描画装置は、更に、前記区分の先頭画素または最終画素に関わりなく多角形の頂点のデータを選出する初期データ選出手段を備え、前記データ選出手段は、前記初期データ選出手段が選出したデータによって形成される元の多角形を２以上の小型の多角形で構成するためにデータを選出する場合に、前記小型の多角形それぞれを構成する頂点の少なくとも１つが、前記各区分の先頭画素又は最終画素となるように、且つ、前記元の多角形を構成する辺上にあるように前記小型の多角形の頂点のデータを選出することとしてよい。
【００１０】
これにより、画像描画装置は、元の多角形を分割して、複数の多角形で元の多角形を表現することができるので、元の多角形をより滑らかに表示することができるようになる。また、複数の多角形は少なくともその頂点の一つを元の多角形の辺上にあるように構成するので、頂点の画素位置を容易に決定することができる。
また、前記データ選出手段は、頂点の１つが互いに接している２つの小型の多角形の当該各頂点が、隣接する区分の最終画素と先頭画素となるように各頂点のデータを選出することとしてよい。
【００１１】
これにより、例えば隣接する小型の多角形において頂点を共有することによって片側の小型の多角形においてアクセス効率が低下しないようにすることができる。
また、前記データ選出手段は、前記小型の多角形それぞれの頂点の１つが、当該頂点が存在する前記元の多角形を構成する辺の、中点近傍の点であるように当該頂点のデータを選出することとしてよい。
【００１２】
これにより、画像描画装置は、分割されて生成される多角形の頂点の一つを元の多角形の中点近傍の点とすることで、分割の仕方がなるべく均等になるようにすることができ、生成される画像もまたなるべく均等で滑らかにすることができる。
また、前記データ選出手段は、選出する頂点のデータのうち少なくとも２個の頂点両方が前記各区分の先頭画素または最終画素のどちらかとなるように、かつ当該２個の頂点によって形成される線分上の全ての画素が、前記２個の頂点が先頭画素にある場合には先頭画素となるように、前記２個の頂点が最終画素にある場合には最終画素となるようにデータを選出することとしてよい。
【００１３】
これにより、ＧＥからフレームメモリへのアクセス効率においてさらに効率よくなるように、頂点を決定することができる。アクセス効率が上がることによって更なる描画速度の向上を望める。
また、前記元の多角形は三角形であり、前記データ選出手段は、前記元の多角形が三角形である場合に、当該三角形を構成する各辺上の１点計三点のデータを選出し、当該三点のうち２点を結んで形成される線分で前記元の三角形を分割し、前記元の三角形を分割して生成された４つの三角形で構成することとしてよい。
【００１４】
これにより、画像描画装置は、３ＤＣＧにおいてその主制御形状の一つである三角形を制御形状として扱うことができ、元の三角形のそれぞれの辺上の点を新たな分割された三角形の頂点として画像を描画することができる。それぞれの辺上の点を分割点とするので分割がしやすく、また描画の扱いも容易になる。従来においても三角形を制御形状とすることが多く本構成を備えることによって、従来の機器にも対応しやすくなる。
【００１５】
また、前記元の多角形は四角形であり、前記データ選出手段は、前記元の多角形が四角形である場合に、元の四角形を構成する各辺上の１点計４点と前記元の四角形内の１点とのデータを選出し、当該１点と前記４点を結ぶ線分によって前記元の四角形を分割し、前記元の四角形を分割されて生成された４つの四角形で構成することとしてよい。
これにより、画像描画装置は、３ＤＣＧにおいてその主制御形状の一つである四角形を制御形状として扱うことができ、元の四角形のそれぞれの辺上の点と四角形内部の１点を新たな四角形の頂点として制御することが可能となる。四角形の辺上に頂点を有することで分割がしやすく、また形状としても扱いやすくなる。ポリゴンが三角形の場合と同様に四角形も従来より制御形状とすることが多く本構成を備えることによって、従来の機器にも容易に対応しやすくなる。
【００１６】
また、前記所定画素数は、前記フレームメモリに接続されるデータ入出力に用いる信号線の数を、１画素を構成するデータのビット数で除算して得ることとしてよい。
これにより、所定画素数を、画像描画装置のＧＥからフレームメモリへの信号線の数と１画素のデータ数によって決定することができるので、それに基づいて、１区分の先頭画素もしくは、最終画素の位置を算出できるようになる。
【００１７】
また、前記所定画素数は、前記フレームメモリへの書込みをバースト転送により行う場合に、バースト転送で転送されるデータ単位のビット数を画素のビット数で除算して得ることとしてよい。
これにより、所定画素数を、バースト転送の際に一時にバースト転送されるバースト転送量を１画素を転送するのに必要なデータ量で除算したものに決定することができるので、それに基づいて、１区分の先頭画素もしくは、最終画素の位置を算出できるようになる。
【００１８】
また、本発明に係る画像描画装置における頂点の選出方法は、データ群により特定される表現対象物をコンピュータグラフィックスにより表現するために、当該データ群のうち複数のデータについて、２次元平面上に投写した場合の位置成分と描画態様を特定するその他の成分とを抽出し、各データの位置成分を頂点とする多角形を、当該画像平面上に当該データについての描画態様を特定するその他の成分に応じて定められている描画態様で、複数描画する画像描画装置における多角形の頂点選出方法であって、ここで前記画像描画装置は、２次元平面上の各画素の画素データ値を格納するためのフレームメモリと、画像を描画するために画素データを前記フレームメモリに書き込む機能を有し、フレームメモリを先頭から所定画素数毎に区分した場合における１区分に対しての書き込みを一括して行う書込み手段とを備える画像描画装置であり、前記頂点選出方法は、前記各区分の先頭画素又は最終画素を前記多角形の少なくとも１つの頂点とするように前記複数のデータを選出するデータ選出ステップを含むことを特徴とする。
【００１９】
この方法をもって、画像描画装置は、多角形の頂点の１つを決定することができる。
また、本発明に係る画像描画装置に搭載のＣＰＵが実行する頂点を選出するためのプログラムは、データ群により特定される表現対象物をコンピュータグラフィックスにより表現するために、当該データ群のうち複数のデータについて、２次元平面上に投写した場合の位置成分と描画態様を特定するその他の成分とを抽出し、各データの位置成分を頂点とする多角形を、当該画像平面上に当該データについての描画態様を特定するその他の成分に応じて定められている描画態様で、複数描画する画像描画装置のコンピュータに実行させるプログラムであって、ここで前記画像描画装置は、２次元平面上の各画素の画素データ値を格納するためのフレームメモリと、画像を描画するために画素データを前記フレームメモリに書き込む機能を有し、フレームメモリを先頭から所定画素数毎に区分した場合における１区分に対しての書き込みを一括して行う書込み手段とを備える画像描画装置であり、前記プログラムにおける前記頂点選出手順は、前記各区分の先頭画素又は最終画素を前記多角形の少なくとも１つの頂点とするように前記複数のデータを選出するデータ選出ステップを含むことを特徴とする。
【００２０】
画像描画装置のＣＰＵは、このプログラムを読み込んで実行することで、多角形の頂点の１つを決定することができる。
また、本発明に係る頂点を選出するための集積回路はデータ群により特定される表現対象物をコンピュータグラフィックスにより表現するために、当該データ群のうち複数のデータについて、２次元平面上に投写した場合の位置成分と描画態様を特定するその他の成分とを抽出し、各データの位置成分を頂点とする多角形を、当該画像平面上に当該データについての描画態様を特定するその他の成分に応じて定められている描画態様で、複数描画する集積回路であって、２次元平面上の各画素の画素データ値を格納するためのフレームメモリと、画像を描画するために画素データを前記フレームメモリに書き込む機能を有し、フレームメモリを先頭から所定画素数毎に区分した場合における１区分に対しての書き込みを一括して行う書込み手段と、前記各区分の先頭画素又は最終画素を前記多角形の少なくとも１つの頂点とするように前記複数のデータを選出するデータ選出手段とを備えることを特徴とする。
【００２１】
この集積回路を搭載した画像描画装置は、多角形の頂点の１つを決定することができる。
【発明を実施するための最良の形態】
【００２２】
＜実施の形態＞
以下、本発明に係る画像描画装置について図面を用いながら説明していく。
＜構成＞
図１は、本発明に係る画像描画装置１００の機能構成を示した機能ブロック図である。
図１に示すように、画像描画装置１００は、ＣＰＵ１１０と、ＧＥ１２０と、フレームメモリ１３０と、ディスプレイ１４０を含んで構成される。
【００２３】
ＣＰＵ１１０は、ＧＥに対して表示すべき画像の主なデータを伝達する機能を有する。
ＧＥ１２０は、ＣＰＵ１１０から受け取った指示に基づき、描画すべき画像の画素データを求める演算を行い、画素データをフレームメモリ１３０に書き込む機能を有し、従来からあるグラフィックスエンジンと同等の性能を有する。フレームメモリ１３０への書込みの仕方は、定められた画素数の単位で書き込む。ここでは８画素とするが、この画素数は、ＧＥ１２０とフレームメモリ１３０とをつなぐバス線の本数と１画素のデータ数によって決定される。例えばバス線が６４本あって、１画素のデータ数が８bitだった場合に、１度に書き込める画素数は８画素となる。フレームメモリ１３０についての詳細は後述する。
【００２４】
また、ＧＥ１２０は、表示する物体をより細やかに表現するためにＣＰＵ１１０から与えられたポリゴンをより細かいポリゴンに分割する場合、分割されて生成される新たなポリゴンの各頂点を決定する機能も有する。本発明において、従来のＧＥと異なる点が、この分割されて生成されるポリゴンの頂点の決定方法にある。なお、頂点の決定方法については、画像描画装置１００の動作として後述する。
【００２５】
ＧＥ１２０は、上述したように、従来からあるＧＥが行っているような演算を行う機能も有している。ＧＥ１２０が行っているそれらの演算は多岐に渡る。その演算の主な内容には、回転／移動による座標の変換、ライティング、視点変換、クリッピング、ラスタ変換、陰面処理、テクスチャ・マッピング、フィルタリングなどがある。通常、回転／移動による座標の変換と、ライティングと、視点変換と、クリッピングとを含んでジオメトリ演算と呼び、ラスタ変換と、陰面処理と、テクスチャ・マッピングと、フィルタリングとを含んでレンダリングと呼ぶことが多い。
【００２６】
以下、各演算の内容を簡単に述べる。
ライティングとは、光りの当たり具合によって変化する色を決定することである。
視点変換とは、表示しようとする物を外部の点から眺めた場合における歪みを算出することである。
クリッピングとは、表示される画面上において、視野に入らない部分についてのデータを削除することである。
【００２７】
ラスタ変換とは、３次元ポリゴンを２次元平面に投影する演算を行うことである。
陰面処理とは、物体の前面に隠れて見えない部分を取り除く演算を行うことである。
テクスチャ・マッピングとは、物体表面に模様を表す画像データを貼り付けることである。
フィルタリングとは、ぎざぎざになっているポリゴンの輪郭を滑らかにする演算を行うことである。
【００２８】
フレームメモリ１３０は、表示する画像の画素データを記憶しておく機能を有する。フレームメモリ１３０に記憶されている画素データを用いて画像の表示が行われる。このフレームメモリ１３０に対しては基本的にＧＥ１２０は所定の画素数ごとに書き込んでいく。ここでは所定の画素数は、前述したように８画素である。
図２にフレームメモリ１３０のデータ格納領域のイメージ図を示した。図２にあるように、フレームメモリ１３０は、２次元配列で画素データを記憶するＲＡＭ（RandomAccess Memory）であり、具体的にはＳＤＲＡＭ（Synchronous Dynamic Random Access Memory）で構成する。
【００２９】
フレームメモリ１３０は、ディスプレイ１４０の表示位置と対応するようにその座標系が設定されている。ここではフレームメモリ１３０は、６４０×４８０の画素を記憶できるものとする。その先頭画素の座標は、（横方向の位置、縦方向の位置）で表すと、画素Ｐ０（０、０）となっている。その次の画素は画素Ｐ１（１、０）、そしてその次の画素がＰ２（２、０）であり、一列目の最終画素はＰ６３９（６３９、０）になる。
【００３０】
また、２列目の先頭になる画素はＰ６４０（０、１）である。以下、順に画素が並んでおり、最終列の先頭画素は、Ｐ３０６５６０（０、４７９）、その次の画素はＰ３０５４５１（１、４７９）となっている。そしてフレームメモリ１３０の最終画素は、Ｐ３０７１９９（６３９、４７９）となる。このように、左から右、上から下への順序で画素データは格納されており、その座標は、表示装置１４０の表示位置の座標と対応している。
【００３１】
フレームメモリ１３０にはＧＥ１２０によって、画素データの書き換えが逐次行われる。書込みは８画素ごとに行われるが、それは斜線部分２１０に示すように横方向に８画素分が一度に書き込まれる。つまり、フレームメモリ１３０へのアクセスは、[Ｐ０（０、０）、Ｐ１（１、０）、…、Ｐ６（６、０）、Ｐ７（７、０）]、[Ｐ８（８、０）、Ｐ９（９、０）、…、Ｐ１４（１４、０）、Ｐ１５（１５、０）]、[Ｐ６３２（６３２、０）、Ｐ６３３（６３３、０）、…、Ｐ６３８（６３８、０）、Ｐ６３９（６３９、０）]、[Ｐ６４０（０、１）、Ｐ６４１（１、１）、…、Ｐ６４６（６、１）、Ｐ６４７（７、１）]、…、[Ｐ１２７２（６３２、１）、Ｐ１２７３（６３３、１）、…、Ｐ１２７８（６３８、１）、Ｐ１２７９（６３９、１）]、…、[Ｐ３０５９２０（０、４７８）、Ｐ３０５９２１（１、４７８）、…、Ｐ３０５９２６（６、４７８）、Ｐ３０５９２７（７、４７８）]、…、[Ｐ３０６５６０（０、４７９）、Ｐ３０６５６１（１、４７９）、…、Ｐ３０６５６６（６、４７９）、Ｐ３０６５６７（７、４７９）]、…、[Ｐ３０７１９２（６３２、４７８）、Ｐ３０７１９３（６３３、４７８）、…、Ｐ３０７１９８（６３８、４７８）、Ｐ３０７１９９（６３９、４７８）]というように、横方向に８画素の単位で行われる。[]で囲まれた範囲内の画素が８画素になっている。この８画素で書き込まれることによって、フレームメモリ１３０において８画素間の境界となる線分が形成されるが、以降これを境界という。図２においては、太線２２０、２２１、２２２がその境界に当たる。
【００３２】
ディスプレイ１４０は、フレームメモリ１３０のデータを逐次読み出して、その内容を画像として表示する機能を有し、例えばＬＣＤ（Liquid CrystalDisplay）や、プラズマディスプレイなどで実現される。
＜データ＞
ここでは、画像描画装置１００が扱うデータについて説明する。
【００３３】
まず、図３に、画像描画装置１００が描画することになる元のデータを３次元的に表現した一例を示した。このような３次元の構造物を３次元から２次元平面に投写してディスプレイに表示する。
図３には、３次元図の一例として地形のようなものを示してある。図３においては、この地形の表面のデータのうち、３点Ａ０、Ｂ０、Ｃ０の座標で示されるデータによって形成される図形Ａ０Ｂ０Ｃ０は、２次元平面に投写されると、三角形Ａ１Ｂ１Ｃ１になることを示している。２次元平面に投射されたものが表示装置において表示されることになる。
【００３４】
図３に示すようなデータは、実際には図４に示すような、座標のデータの集合である。図４に示す座標表４００は、ｘ軸データ４０１と、ｙ軸データ４０２と、ｚ軸データ４０３とを含む。ｘ軸データ４０１、ｙ軸データ４０２、ｚ軸データ４０３それぞれは、それぞれの座標成分を示すデータを意味している。
ここでは、ｘ、ｙ、ｚ軸それぞれの座標のみのデータを記しているが、これ以外にも更に、色のデータ、模様のデータ、光源のデータなど、様々なデータを保持していてもよい。
＜動作＞
ここから、画像描画装置１００の動作について説明していく。
【００３５】
図５に示すようなＣＰＵ１１０がＧＥ１２０に対して与えるポリゴンを図６のように分割するための一般的な動作を図９及び図１０に示すフローチャートを用いて説明する。なお、図７には、比較のために従来のように分割した場合の例を示しており、図８は、アクセス単位を説明するための図である。図９及び図１０を用いて一般的な動作を説明した後に、図５〜図８を用いて具体的な分割の動作と従来との差を説明する。
【００３６】
画像描画装置１００において３次元画像を描画する方法については、従来の３次元画像を描画する描画装置に準拠するものとして説明を割愛し、ここでは本願の特徴である分割されて生成されるポリゴンの頂点の決定方法について、画像描画装置１００の動作を説明する。
図９は、本発明に係る画像描画装置１００のＧＥ１２０の動作を示すフローチャートである。
【００３７】
図９に示すように、ＧＥ１２０は、まずＣＰＵ１１０から、図４に示すようなデータ群からピックアップされたデータに基づく描画指示を受け付ける（ステップＳ９０１）。受け付けた描画指示に基づいて、ポリゴンデータに基づいて当該ポリゴンを分割するための分割点を算出する（ステップＳ９０３）。このステップＳ９０３における、分割点の算出方法については、その詳細を図１０を用いて後述する。
【００３８】
算出された分割点をつないだ線分で元のポリゴンを分割する（ステップＳ９０５）。このとき、元のポリゴンを形成する辺と境界の交点の左右の画素が分割点となるので、その左右の画素のどちらを分割点とするかを選出する必要がある。よって、分割されて生成されるポリゴンの頂点が境界をなるべく跨がないように分割する。つまり、分割されて生成されるポリゴンの頂点のうち、分割前のポリゴンと同じ頂点に近くなるように頂点を選出して分割する。
【００３９】
分割して生成されたポリゴンごとにＧＥ１２０は、補間すべき画素データを算出し、その画素データをフレームメモリ１３０に格納する。フレームメモリ１３０に格納されている画素データは、表示装置１４０に読み出されて表示される。
図１０は、図９におけるステップＳ９０３の分割点を求める画像描画装置１００におけるＧＥ１２０の動作を示した。
【００４０】
図１０に示すように、ＧＥ１２０は、ＣＰＵ１１０から与えられた座標から２点を結ぶ線分を算出する（ステップＳ１００１）。そしてその線分の中点となる座標を求める（ステップＳ１００３）。中点の座標が画素と画素の境目に来る場合には、その右側、下側の座標を中点の座標とする。
そして中点の座標が、（８ｎ、Ｙ）か（８ｎ＋７、Ｙ）に該当するかどうかを判断する（ステップＳ１００５）。なお、ｎは０以上の整数、Ｘは任意の自然数である。中点の座標がその座標に該当しない場合に（ステップＳ１００５のＮＯ）、算出した線分上の画素において、（８ｎ、Ｙ）か（８ｎ＋７、Ｙ）に該当する画素があるかどうかを判断する（ステップＳ１００７）。該当する画素がない場合には（ステップＳ１００７のＮＯ）、中点の座標に位置する画素を分割点の一つとして終了する。
【００４１】
ステップＳ１００７において、該当する画素があった場合には（ステップＳ１００７のＹＥＳ）、該当する画素が複数ある場合には、中点に近い画素を分割点に決定して（ステップＳ１００９）終了する。ここで選択される画素は基本的には２つである。例えば、図６の三角形で辺Ｄ０Ｅ０上の点で分割点となるのは点Ｄ１か点Ｄ２となる。ここで、図９のステップＳ９０５の分割点の選択についてこの例で説明しておくと、図６では、頂点Ｄ０を含む新たな三角形は三角形Ｄ０Ｄ２Ｆ１となるように分割点を選出する。点Ｄ１あるいは点Ｆ２も、元の三角形Ｄ０Ｅ０Ｆ０の辺上の点で、境界の左右の画素という条件を満たすが、点Ｄ０を頂点の一つとする三角形を形成する場合には、点Ｄ２の代りに点Ｄ１に、あるいは点Ｆ１の代りに点Ｆ２を選出しない。点Ｄ１あるいは点Ｆ１を選出すると、境界を跨いでしまうために、ＧＥ１２０からフレームメモリ１３０へのアクセス量が増加してしまうためである。
【００４２】
ここで点Ｄ１と点Ｄ２の関係について説明しておく。点Ｄ１及び点Ｄ２はともに境界に隣接し、分割点として選出される画素である。しかし、両方が分割点として必ずしも使用されるわけではなく、分割されて生成される新たな三角形の形状に基づく。つまり、この場合においては、点Ｄ１、点Ｄ２の両方の画素が分割点として選出されるが、点Ｄ１は、三角形Ｄ１Ｅ０Ｅ１の画素データをフレームメモリに書き込むのに用いられ、点Ｄ２は使用しない。一方、点Ｄ２は三角形Ｄ０Ｄ２Ｆ１の画素データをフレームメモリに書き込むのに用いられ、点Ｄ１は使用されない。
【００４３】
ここから、図５の三角形を図７のように分割する際の分割点の決定について図面を用いて具体的に説明する。
まず、ＣＰＵ１１０からＧＥ１２０に三点Ｄ０Ｅ０Ｆ０を結ぶ三角形を赤色で描けという指示が下ったとする。
するとＧＥ１２０は、２点Ｄ０Ｅ０を結ぶ線分を算出する。そしてその線分がフレームメモリ１３０は、（８ｎ、Ｙ）もしくは（８ｎ＋１，Ｙ）となる画素がないかどうか、即ち境界との交点があるかどうかを判断する。この場合、境界６１０、６１１と交差することになるが、より中点に近い２点Ｄ１、Ｄ２がその交点になる。
【００４４】
次に、線分Ｅ０Ｆ０が、境界と交差するかどうかを判断する。この場合、境界６１０、６１１、６１２の３つの境界と交差するが、より中点に近い２点Ｅ１、Ｅ２を分割点として選出する。
そして最後に線分Ｆ０Ｄ０が境界と交差するかどうかを判断する。ここでは境界６１２としか交差しないため、その交差点である２点Ｆ１、Ｆ２を分割点とする。
【００４５】
結果、それぞれ選出された分割点を結ぶ線分で元の三角形Ｄ０Ｅ０Ｆ０を４つの三角形、三角形Ｄ０Ｄ２Ｆ１、三角形Ｄ１Ｅ０Ｅ１、三角形Ｄ２Ｅ２Ｆ１、三角形Ｆ２Ｅ２Ｆ０に分割することになる。
＜考察＞
ここでは、上記のように、三角形を分割した場合について、従来の方法で分割した場合とそのアクセス回数において差が出ることを具体例をあげて示しておく。
【００４６】
アクセス回数の差については、図５〜８を用いて説明する。
まず、アクセス回数をどのように換算するかについて図８を用いて説明する。
図８（ａ）は、本願発明による方法に基づいて、図５の元の三角形Ｄ０Ｅ０Ｆ０を、図６のように分割して生成された複数の三角形のうち、真ん中の三角形Ｄ２Ｅ２Ｆ１を示している。図８（ａ）にあるように、ＧＥ１２０は、８画素ごとにフレームメモリ１３０に書き込むことになるので、三角形Ｄ２Ｅ２Ｆ１を構成する画素をフレームメモリ１３０に書き込むのに都合７回ほどフレームメモリ１３０にアクセスすることになる。
【００４７】
図８（ｂ）は、従来の方法に基づいて、図５の元の三角形Ｄ０Ｅ０Ｆ０を、図７のように分割して生成された三角形のうち、真ん中の三角形Ｄ３Ｅ３Ｆ３を示している。この場合においては、この三角形Ｄ３Ｅ３Ｆ３をフレームメモリ１３０に書き込むために都合１２回アクセスすることになる。
このようにしてアクセス回数を求めた場合、図６のように本願発明に基づいて分割した場合には、生成された三角形におけるそれぞれをフレームメモリ１３０に書き込むために発生するアクセス回数は、次のようになる。
・  三角形Ｄ０Ｄ２Ｆ１：４回
・  三角形Ｄ２Ｅ２Ｆ１：８回
・  三角形Ｄ１Ｅ０Ｅ１：１３回
・  三角形Ｆ１Ｅ２Ｆ０：１５回
となる。よって三角形Ｄ０Ｅ０Ｆ０全体では、ＧＥ１２０からフレームメモリ１３０に対して、計４０回のアクセスが発生したことになる。
【００４８】
一方、図７のように従来の方式に基づいて中点で分割した場合には、分割して生成された各三角形をフレームメモリに書き込むために発生するそれぞれのアクセス回数は、以下の通りである。
・  三角形Ｄ０Ｄ３Ｆ３：１２回
・  三角形Ｄ３Ｅ３Ｆ３：１３回
・  三角形Ｄ３Ｅ０Ｅ３：１２回
・  三角形Ｆ３Ｅ３Ｆ０：１２回
となる。よって三角形Ｄ０Ｅ０Ｆ０全体では、ＧＥ１２０からフレームメモリ１３０に対して、計４９回のアクセスが発生したことになる。
【００４９】
上記のように、２つの差を比べると分かるが、この三角形Ｄ０Ｅ０Ｆ０において、本発明に従って分割した方が、従来どおりに分割した場合に比べて、１０回もアクセス回数が少ないことになる。この三角形Ｄ０Ｅ０Ｆ０事自体は表現したい物体の小さな１ピースにしか過ぎず、実際にはもっと多くの三角形で表現することになる。よってそれぞれの三角形でアクセス回数で発生することになり、総合的に見ると本願発明と従来発明との差が更にでることは明らかである。当然ながら画像の表示を早くするのには、アクセス回数が少ない方が良い。
【００５０】
ここにあげたのは一例に過ぎないが、その他の形の三角形であっても、そのアクセス回数において大小はあるにせよ、本発明による分割と従来の分割とでは差が出てくることが多い。
＜補足＞
上記実施の形態に基づいて、本発明に係る画像描画装置について説明してきたが、画像描画装置の実施の形態はこれに限られないことは勿論である。以下、その変形例について説明していく。
（１）上記実施の形態においては３角形を例にとって説明したが、ポリゴンは別に３角形でなくてもよく、例えば４角形などでもよい。前述したように３ＤＣＧの世界においては、ポリゴンは３角形か４角形のいずれかであることが多い。
【００５１】
四角形の分割の仕方について、図１１〜１３を例に簡単に説明する。
図１１は、ＣＰＵからＧＥに対して描画することを指示した四角形の形状をしたポリゴンをフレームメモリに格納した状態を示している。
この図１１に示したような四角形を分割する際には、従来においては図１３に示すように、その相対する辺の中点を結ぶ線分によって略４分の１の四角形に分割していた。しかし、本発明において、フレームメモリへの書込みの境目に分割点が来るように分割することで効果を得るので、図１２のように分割する。
【００５２】
各辺上の点で、フレームメモリへの書込み単位の境目にある画素をそれぞれの辺上の分割点とする。また、元の四角形の重心近傍の点でフレームメモリへの書込み単位の境目にある画素を最後の分割点とする。この最後の分割点は重心までの距離が最短になるように選出するが、簡単に選出するために、横方向の辺上の２点の分割点を結ぶ線分の中点を最後の分割点としてもよい。当該分割点と各辺上の分割点を結んで新たな四角形を４つ形成する。形成された４つの新たな四角形で元の四角形を表現する。
【００５３】
図１２においては、図１１に示した元の四角形Ｈ０Ｉ０Ｊ０Ｋ０は、分割された４つ四角形、四角形Ｈ０Ｈ２Ｌ０Ｋ１と、四角形Ｈ１Ｉ０Ｉ１Ｌ０と、四角形Ｌ１Ｉ２Ｊ０Ｊ２と、四角形Ｋ２Ｌ１Ｊ２Ｋ０とで構成していることを示している。この場合におけるフレームメモリへのアクセス回数は、四角形Ｈ０Ｉ０Ｊ０Ｋ０全体で、３９回になる。
図１３には、図１１に示した元の四角形Ｈ０Ｉ０Ｊ０Ｋ０を中点で分割した場合の図を示した。図１３に示すように元の四角形Ｈ０Ｉ０Ｊ０Ｋ０は、４つの四角形、四角形Ｈ０Ｈ３Ｌ３Ｋ３と、四角形Ｈ３Ｉ０Ｉ３Ｌ４と、四角形Ｌ４Ｉ３Ｊ０Ｊ３と、四角形Ｋ３Ｌ３Ｊ３Ｋ０とで構成されている。この場合におけるフレームメモリへのアクセス回数は、四角形Ｈ０Ｉ０Ｊ０Ｋ０全体で、５０回になる。
【００５４】
このように四角形においてもアクセス回数に差が発生するので、四角形の場合においても、三角形と同様に元の四角形を分割して書き込む場合に、アクセス回数を軽減する効果を期待できる。アクセス回数が減ることによって描画も早まるので、ディスプレイ上において表示が遅れることも少なくなる。
（２）上記実施の形態においては１回だけ分割して見せたが、別にこれは１回である必要はなく、更に分割してもよい。例えば予め定められた回数だけ分割してもよいし、あるいは縮尺によって分割回数を変えてもよいし、あるいは全てのポリゴンが８画素の単位を跨がなくなるまで分割することとしてもよい。
【００５５】
図１４にその一例を示した。図１４は、図６に示した三角形Ｄ０Ｅ０Ｆ０を更に分割した。
図６において、三角形Ｄ１Ｅ０Ｅ１、及び三角形Ｆ２Ｅ２Ｆ０は共に８画素を跨ってフレームメモリにデータが格納されるので、書込みの際に無駄が発生するのでさらに分割する。辺Ｄ１Ｅ０と辺Ｅ０Ｅ１はそれぞれ、書込み画素の境界線と交わるので、その点を分割点とする。三角形Ｄ１Ｅ０Ｅ１を、三角形Ｄ４Ｅ０Ｅ４と、三角形Ｄ５Ｅ５Ｅ１と、三角形Ｄ１Ｄ５Ｅ１の３つの三角形に分割する。一方三角形Ｆ２Ｅ２Ｆ０の方は、三角形Ｆ１Ｅ２Ｅ６と三角形Ｆ２Ｅ７Ｆ０に分割するようにしてもよい。分割することでより滑らかな画像を描画できるようになる。また、分割されて生成された三角形それぞれは、その頂点の少なくとも１つが、書込み画素の先頭画素または最終画素になっているので書込みにおいて無駄が発生することがない。
【００５６】
また、更に分割の回数を、表現したい滑らかさの度合いによって決定しても良い。通常、視点に近いものの方が細かく見え、遠いものの方が荒く見えることを踏まえて、視点に近い部分については分割回数を多くし、遠い部分については分割回数を少なくしてもよい。これにより近い部分を滑らかに表現しつつ、遠い部分の分割回数を減らすことでＧＥの負担を軽減することができる。
（３）上記実施の形態においてはフレームメモリは、６４０×４８０の画素を格納するものとしたが、別にこれは６４０×４８０である必要はなく、例えば、１２８０×９６０の画素、あるいは１０２４×７６８の画素を格納できるメモリであってもよい。
【００５７】
また、携帯電話機のディスプレイに対応できるように、２４０×３２０の画素を格納できるメモリであってもよい。
また、予め容量の大きいメモリ（例えば１６００×１２００の解像度に対応できるメモリ）を用意し、ディスプレイの解像度にあわせてその使用領域を変えて各種ディスプレイに対応できるようにしてもよい。
（４）上記実施の形態に示される画像描画装置を構成する各部は、ＬＳＩ（Large Scale Integration）、ＶＬＳＩ（Very LargeScale Integration）等の一部又は全部として実現されてもよく、複数のＬＳＩ等で実現されてもよく、一又は複数のＬＳＩ等と他の回路の組み合わせとにより実現されてもよい。
（５）上記実施の形態においては、ＧＥが分割を行っていたが、プログラム的にポリゴンの分割を処理しても良い。例えば、上記画像描画装置は、具体的には、マイクロプロセッサ、ＲＯＭ、ＲＡＭ、ハードディスクユニット、ディスプレィユニット、キーボード、マウスなどから構成されるコンピュータシステムである。前記ＲＡＭ又は前記ハードディスクユニットには、コンピュータプログラムが記憶されている。前記マイクロプロセッサが、前記コンピュータプログラムに従って動作することにより、前記装置は、その機能を達成する。
（６）上記実施の形態においては、一度に書き込まれる書込みの画素数は、ＧＥとフレームメモリ間のバス線の数によって決定されるとしたが、これはその限りでない。例えば、連続したデータをアドレスの指定などなしに転送するデータの高速転送方法であるバースト転送の、一度のバースト転送で転送できるデータ量を１画素のデータ数によって減算したものが一度に書き込まれる画素数になることもある。
（７）上記実施の形態においては、三点Ｄ０Ｅ０Ｆ０によって形成される三角形を赤色で描けという単純なものについて説明したが、例えば各３点は、それぞれに色の情報を持っていて当該３点によって形成される三角形は、３点の色の平均色で描く仕様にしてもよいし、そこに更に光源の位置によって色合いを変えるようにしても良い。これらの機能については、従来からあるＧＥにおいても実行されている内容である。
（８）上記実施の形態においては、ＧＥ１２０は、フレームメモリ１３０へ一括して８画素の単位で書き込む機能を有していたが、さらに、１画素のみの書込みを行う機能も備えていても良い。
（９）上記実施の形態においては、描画する元のデータの一例として、図４に示すように座標のデータを示したが、元の物体を表現する演算式などで表現されていてもよい。
（１０）上記実施の形態において一連の動作は、一のプログラムあるいは複数のプログラムを実行し、連動させることによって実現することとしても良い。
【産業上の利用可能性】
【００５８】
本発明に係る画像描画装置は、３Ｄ画像を表示する装置として、ゲーム機などに利用することができる。
【図面の簡単な説明】
【００５９】
【図１】本発明に係る画像描画装置の機能構成を示したブロック図である。
【図２】本発明に係る画像描画装置のフレームメモリの記憶領域の概念図である。
【図３】３次元の物体を２次元に投写することを示した概念図である。
【図４】３次元のデータについて示した図である。
【図５】ＣＰＵがＧＥに対して描画するポリゴンのデータをフレームメモリに格納した模式図である。
【図６】本発明の分割方法に従ってポリゴンを分割した図である。
【図７】従来の分割方法に従ってポリゴンを分割した図である。
【図８】分割された三角形について、フレームメモリへのアクセス量を示した図である。
【図９】本発明に係る画像描画装置の動作を示したフローチャートである。
【図１０】分割点の位置を示した図である。
【図１１】分割元となる四角形を示した図である。
【図１２】四角形を本発明の画像描画装置が分割した場合の分割図である。
【図１３】四角形を従来の技法で分割した場合の分割図である。
【図１４】三角形を更に分割する場合の例を示した分割図である。
【符号の説明】
【００６０】
１００  画像描画装置
１１０  ＣＰＵ
１２０  ＰＥ
１３０  フレームメモリ
１４０  表示装置
２２０、２２１、２２２  境界
４００  データ表
【図１】
0004691494.tif 000002
【図２】
0004691494.tif 000003
【図３】
0004691494.tif 000004
【図４】
0004691494.tif 000005
【図５】
0004691494.tif 000006
【図６】
0004691494.tif 000007
【図７】
0004691494.tif 000008
【図８】
0004691494.tif 000009
【図９】
0004691494.tif 000010
【図１０】
0004691494.tif 000011
【図１１】
0004691494.tif 000012
【図１２】
0004691494.tif 000013
【図１３】
0004691494.tif 000014
【図１４】
0004691494.tif 000015