(57)【要約】【課題】少ない演算負荷で高速に輪郭を抽出可能な画像生成システム、プログラム及び情報記憶媒体を提供すること。【解決手段】所与のオブジェクトを構成する各辺について、辺の両端の２頂点のいずれかを共有する他の辺である隣接辺の情報を含む辺情報を記憶し、前記隣接辺の情報に基づき、前記所与のオブジェクトを構成する各辺が、前記所与のオブジェクトの光源に対する輪郭を構成するエッジであるか否かのエッジ判定処理の対象となる辺を抽出し、抽出した辺についてエッジ判定処理を行う。所与のオブジェクトを構成する辺についてエッジ判定処理を行い、判定結果に基づき１つのエッジを抽出し、抽出されたエッジの隣接辺の情報を、隣接辺についてエッジ判定処理を行い、判定結果に基づき、抽出されたエッジの一方の頂点を共有する次のエッジを抽出する処理を、少なくとも最初に抽出した１つのエッジの他方の頂点を共有するエッジが抽出されるまで順次繰り返し行う。【選択図】        図１０
2004341571.tif 000002
【特許請求の範囲】
【請求項１】
画像生成を行うシステムであって、
所与のオブジェクトを構成する各辺について、辺の両端の２頂点のいずれかを共有する他の辺である隣接辺の情報を含む辺情報を記憶する辺情報記憶手段と、
前記隣接辺の情報に基づき、前記所与のオブジェクトを構成する各辺が、前記所与のオブジェクトの光源に対する輪郭を構成するエッジであるか否かのエッジ判定処理の対象となる辺を抽出し、抽出した辺についてエッジ判定処理を行い、前記所与のオブジェクトの光源に対するエッジを検出するエッジ検出手段と、
検出されたエッジに基づき所与のオブジェクトが配置された仮想３次元空間を仮想カメラから見た画像を生成する画像生成手段とを含み、
前記エッジ検出手段は、
所与のオブジェクトを構成する辺についてエッジ判定処理を行い、判定結果に基づき１つのエッジを抽出する手段と、
抽出されたエッジの隣接辺の情報を前記辺情報記憶手段から読み出して、隣接辺についてエッジ判定処理を行い、判定結果に基づき、抽出されたエッジの一方の頂点を共有する次のエッジを抽出する処理を、少なくとも最初に抽出した１つのエッジの他方の頂点を共有するエッジが抽出されるまで順次繰り返し行う手段と、を含むことを特徴とする画像生成システム。
【請求項２】
請求項１において、
抽出されたエッジを構成する頂点から光源ベクトルの方向に所与の距離離れた点に新たな頂点を生成し、前記エッジを構成する頂点と新たに生成した頂点に基づきシャドウボリュームを生成する手段と、を含むことを特徴とする画像生成システム。
【請求項３】
画像生成を行うシステムであって、
所与のオブジェクトを構成する各辺について、辺の両端の２頂点のいずれかを共有する他の辺である隣接辺の情報を含む辺情報を記憶する辺情報記憶手段と、
前記隣接辺の情報に基づき、前記所与のオブジェクトを構成する各辺が、前記所与のオブジェクトを視点からみた場合の輪郭を構成するエッジであるか否かのエッジ判定処理の対象となる辺を抽出し、抽出した辺についてエッジ判定処理を行い、前記所与のオブジェクトを視点から見たエッジを検出するエッジ検出手段と、
検出されたエッジに基づき所与のオブジェクトが配置された仮想３次元空間を仮想カメラから見た画像を生成する画像生成手段とを含み、
前記エッジ検出手段は、
所与のオブジェクトを構成する辺についてエッジ判定処理を行い、判定結果に基づき１つのエッジを抽出する手段と、
抽出されたエッジの隣接辺の情報を前記辺情報記憶手段から読み出して、隣接辺についてエッジ判定処理を行い、判定結果に基づき、抽出されたエッジの一方の頂点を共有する次のエッジを抽出する処理を、少なくとも最初に抽出した１つのエッジの他方の頂点を共有するエッジが抽出されるまで順次繰り返し行う手段と、を含むことを特徴とする画像生成システム。
【請求項４】
請求項１乃至５のいずれかにおいて、
前記隣接辺の情報は、
所与のオブジェクトを構成する辺のうち、辺を共有する２枚のプリミティブの法線ベクトルが平行な関係にある辺又は辺を共有する２枚のプリミティブの法線ベクトルが交差する関係にある辺については除外して生成されていることを特徴とする画像生成システム。
【請求項５】
請求項１乃至６のいずれかにおいて、
前記辺情報は、
所与のオブジェクトを構成する各辺について、辺の両端の頂点座標、辺を含む２のプリミティブの法線情報を含み、
前記エッジ検出手段が、
エッジ判定処理の対象となる辺の法線情報と、視点ベクトル又は光源ベクトルとに基づきエッジ判定を行うことを特徴とする画像生成システム。
【請求項６】
コンピュータを、
所与のオブジェクトを構成する各辺について、辺の両端の２頂点のいずれかを共有する他の辺である隣接辺の情報を含む辺情報を記憶する辺情報記憶手段と、
前記隣接辺の情報に基づき、前記所与のオブジェクトを構成する各辺が、前記所与のオブジェクトの光源に対する輪郭を構成するエッジであるか否かのエッジ判定処理の対象となる辺を抽出し、抽出した辺についてエッジ判定処理を行い、前記所与のオブジェクトの光源に対するエッジを検出するエッジ検出手段と、
検出されたエッジに基づき所与のオブジェクトが配置された仮想３次元空間を仮想カメラから見た画像を生成する画像生成手段として機能させるプログラムであって、
前記エッジ検出手段が、
所与のオブジェクトを構成する辺についてエッジ判定処理を行い、判定結果に基づき１つのエッジを抽出し、
抽出されたエッジの隣接辺の情報を前記辺情報記憶手段から読み出して、隣接辺についてエッジ判定処理を行い、判定結果に基づき、抽出されたエッジの一方の頂点を共有する次のエッジを抽出する処理を、少なくとも最初に抽出した１つのエッジの他方の頂点を共有するエッジが抽出されるまで順次繰り返し行うことを特徴とするプログラム。
【請求項７】
請求項６において、
抽出されたエッジを構成する頂点から光源ベクトルの方向に所与の距離離れた点に新たな頂点を生成し、前記エッジを構成する頂点と新たに生成した頂点に基づきシャドウボリュームを生成する手段としてコンピュータを機能させることを特徴とするプログラム。
【請求項８】
コンピュータを、
所与のオブジェクトを構成する各辺について、辺の両端の２頂点のいずれかを共有する他の辺である隣接辺の情報を含む辺情報を記憶する辺情報記憶手段と、
前記隣接辺の情報に基づき、前記所与のオブジェクトを構成する各辺が、前記所与のオブジェクトを視点からみた場合の輪郭を構成するエッジであるか否かのエッジ判定処理の対象となる辺を抽出し、抽出した辺についてエッジ判定処理を行い、前記所与のオブジェクトを視点から見たエッジを検出するエッジ検出手段と、
検出されたエッジに基づき所与のオブジェクトが配置された仮想３次元空間を仮想カメラから見た画像を生成する画像生成手段として機能させるプログラムであって、
前記エッジ検出手段が、
所与のオブジェクトを構成する辺についてエッジ判定処理を行い、判定結果に基づき１つのエッジを抽出し、
抽出されたエッジの隣接辺の情報を前記辺情報記憶手段から読み出して、隣接辺についてエッジ判定処理を行い、判定結果に基づき、抽出されたエッジの一方の頂点を共有する次のエッジを抽出する処理を、少なくとも最初に抽出した１つのエッジの他方の頂点を共有するエッジが抽出されるまで順次繰り返し行うことを特徴とするプログラム。
【請求項９】
請求項６乃至８のいずれかにおいて、
前記隣接辺の情報は、
所与のオブジェクトを構成する辺のうち、辺を共有する２枚のプリミティブの法線ベクトルが平行な関係にある辺又は辺を共有する２枚のプリミティブの法線ベクトルが交差する関係にある辺については除外して生成されていることを特徴とするプログラム。
【請求項１０】
請求項６乃至９のいずれかにおいて、
前記辺情報は、
所与のオブジェクトを構成する各辺について、辺の両端の頂点座標、辺を含む２のプリミティブの法線情報を含み、
前記エッジ検出手段が、
エッジ判定処理の対象となる辺の法線情報と、視点ベクトル又は光源ベクトルとに基づきエッジ判定を行うことを特徴とするプログラム。
【請求項１１】
コンピュータにより読みとり可能な情報記憶媒体であって、請求項６乃至１０のいずれかに記載のプログラムを記憶することを特徴とする情報記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像生成システム、プログラム及び情報記憶媒体に関する。
【０００２】
【背景技術】
従来より、仮想的な３次元空間であるオブジェクト空間内において仮想カメラ（所与の視点）から見える画像を生成する画像生成システム（例えばゲームシステム）が知られており、いわゆる仮想現実を体験できるものとして人気が高い。
【０００３】
このような画像生成システムでは、プレーヤの仮想現実感の向上のために、よりリアルな画像を生成することが重要な課題になっている。
【０００４】
例えば所与のオブジェクトがおとす影等の画像についても、よりリアルに表現されていることが望まれる。オブジェクトに影画像を生成する手法としては、シャドーボリュームを用いる手法等が知られている。
【０００５】
【特許文献１】
特開２００２−３１９０３１号
【０００６】
【発明が解決しようとする課題】
ここで本願発明者は、所与のオブジェクトの光源に対する輪郭を検出して、当該オブジェクトのシャドーボリュームを生成し所与のオブジェクトの影画像を生成する手法を開発している。ここでリアルタイム処理を行うためには、少ない演算負荷で輪郭を高速に抽出することが必要になってきている。
【０００７】
本発明は、以上のような課題に鑑みてなされたものであり、その目的とするところは、少ない演算負荷で高速に輪郭を抽出可能な画像生成システム、プログラム及び情報記憶媒体を提供することである。
【０００８】
【課題を解決するための手段】
（１）本発明は、画像生成を行うシステムであって、
所与のオブジェクトを構成する各辺について、辺の両端の２頂点のいずれかを共有する他の辺である隣接辺の情報を含む辺情報を記憶する辺情報記憶手段と、
前記隣接辺の情報に基づき、前記所与のオブジェクトを構成する各辺が、前記所与のオブジェクトの光源に対する輪郭を構成するエッジであるか否かのエッジ判定処理の対象となる辺を抽出し、抽出した辺についてエッジ判定処理を行い、前記所与のオブジェクトの光源に対するエッジを検出するエッジ検出手段と、
検出されたエッジに基づき所与のオブジェクトが配置された仮想３次元空間を仮想カメラから見た画像を生成する画像生成手段とを含み、
前記エッジ検出手段は、
所与のオブジェクトを構成する辺についてエッジ判定処理を行い、判定結果に基づき１つのエッジを抽出する手段と、
抽出されたエッジの隣接辺の情報を前記辺情報記憶手段から読み出して、隣接辺についてエッジ判定処理を行い、判定結果に基づき、抽出されたエッジの一方の頂点を共有する次のエッジを抽出する処理を、少なくとも最初に抽出した１つのエッジの他方の頂点を共有するエッジが抽出されるまで順次繰り返し行う手段と、を含むことを特徴とする。
【０００９】
また本発明に係るプログラムは、コンピュータにより実行可能なプログラム（情報記憶媒体又は搬送波に具現化されるプログラム）であって、上記手段をコンピュータに実現させる（上記手段としてコンピュータを機能させる）ことを特徴とする。また本発明に係る情報記憶媒体は、コンピュータにより読み取り可能（使用可能）な情報記憶媒体であって、上記手段をコンピュータに実現させる（上記手段としてコンピュータを機能させる）ためのプログラムを含むことを特徴としている。
【００１０】
ここで隣接辺の情報を含む辺情報は、事前に作成して記憶手段に記憶させておくことができる。
【００１１】
またここで光源に対する輪郭とは点光源に対する輪郭でもよいし平行光源に対する輪郭でもよい。
【００１２】
閉じた凸型のオブジェクトの光源に対する輪郭線は必ず連続して閉じた線となる。従って本発明では、まず所与のオブジェクトを構成する辺についてエッジ判定処理を行い、判定結果に基づき１つのエッジを抽出する。一番最初に見つかったエッジを１つのエッジとして抽出すると良い。
【００１３】
またエッジ判定処理は、例えば判定対象となる辺の法線ベクトルと光源ベクトルと内積をとり内積の符号が逆（２の内積が正と負）であればエッジであると判定するようにしても良い。
【００１４】
ここで光源が平行光源で有る場合はエッジ判定を行う際の頂点位置に関わらず平行なベクトルを光源ベクトルを用い、光源が点光源である場合には光源と辺の頂点を結ぶベクトルを光源ベクトルとして用いる。
【００１５】
また本発明によれば、抽出されたエッジの各隣接辺についてエッジ判定処理を行い、判定結果に基づき、抽出されたエッジの一方の頂点を共有する次のエッジを抽出する処理を、少なくとも最初に抽出した１つのエッジの他方の頂点を共有するエッジが抽出されるまで順次繰り返し行う。
【００１６】
かかる処理を最初に抽出した１つのエッジに接続されるエッジを抽出するまで繰り返すと、輪郭線を構成するすべての辺（エッジ）を抽出することができる。
【００１７】
本発明によれば抽出されたエッジについて、予め登録されている隣接辺についてのみエッジ判定処理を行えばよいの、輪郭線に沿った最短ルートで光源に対するエッジを検出することができる。
【００１８】
したがって、少ない演算負荷で高速に輪郭を抽出可能な画像生成システム、プログラム及び情報記憶媒体を提供することができる。
【００１９】
しかも検出されたエッジを、輪郭線に沿って繋がれる順にソートされた形式で得ることができるので、ボリューム作成やシザリング等の処理を行う上で都合が良い。
【００２０】
（２）また本発明に係る画像生成システム、プログラム及び情報記憶媒体は、抽出されたエッジを構成する頂点から光源ベクトルの方向に所与の距離離れた点に新たな頂点を生成し、前記エッジを構成する頂点と新たに生成した頂点に基づきシャドウボリュームを生成する手段と、
を含むことを特徴とする。
【００２１】
本実施の形態では輪郭線を構成する頂点を輪郭線に沿って繋がれる順にソートされた形式で得ることができるので、ハードウエアが有するトライアングルストリップの機能やトライアングルファンの機能を使用することにより、簡単にシャドーボリュームを生成することができる
（３）本発明は、画像生成を行うシステムであって、
所与のオブジェクトを構成する各辺について、辺の両端の２頂点のいずれかを共有する他の辺である隣接辺の情報を含む辺情報を記憶する辺情報記憶手段と、
前記隣接辺の情報に基づき、前記所与のオブジェクトを構成する各辺が、前記所与のオブジェクトを視点からみた場合の輪郭を構成するエッジであるか否かのエッジ判定処理の対象となる辺を抽出し、抽出した辺についてエッジ判定処理を行い、前記所与のオブジェクトを視点から見たエッジを検出するエッジ検出手段と、
検出されたエッジに基づき所与のオブジェクトが配置された仮想３次元空間を仮想カメラから見た画像を生成する画像生成手段とを含み、
前記エッジ検出手段は、
所与のオブジェクトを構成する辺についてエッジ判定処理を行い、判定結果に基づき１つのエッジを抽出する手段と、
抽出されたエッジの隣接辺の情報を前記辺情報記憶手段から読み出して、隣接辺についてエッジ判定処理を行い、判定結果に基づき、抽出されたエッジの一方の頂点を共有する次のエッジを抽出する処理を、少なくとも最初に抽出した１つのエッジの他方の頂点を共有するエッジが抽出されるまで順次繰り返し行う手段と、を含むことを特徴とする。
【００２２】
また本発明に係るプログラムは、コンピュータにより実行可能なプログラム（情報記憶媒体又は搬送波に具現化されるプログラム）であって、上記手段をコンピュータに実現させる（上記手段としてコンピュータを機能させる）ことを特徴とする。また本発明に係る情報記憶媒体は、コンピュータにより読み取り可能（使用可能）な情報記憶媒体であって、上記手段をコンピュータに実現させる（上記手段としてコンピュータを機能させる）ためのプログラムを含むことを特徴としている。
【００２３】
ここで隣接辺の情報を含む辺情報は、事前に作成して記憶手段に記憶させておくことができる。
【００２４】
所与のオブジェクトを視点からみた場合の輪郭線は必ず連続して閉じた線となる。従って本発明では、まず所与のオブジェクトを構成する辺についてエッジ判定処理を行い、判定結果に基づき１つのエッジを抽出する。一番最初に見つかったエッジを１つのエッジとして抽出すると良い。
【００２５】
またエッジ判定処理は、例えば判定対象となる辺の法線ベクトルと視点ベクトル（視点と頂点を結ぶベクトル）と内積をとり内積の符号が逆（２の内積が正と負）であればエッジであると判定するようにしても良い。
【００２６】
また本発明によれば、抽出されたエッジの各隣接辺についてエッジ判定処理を行い、判定結果に基づき、抽出されたエッジの一方の頂点を共有する次のエッジを抽出する処理を、少なくとも最初に抽出した１つのエッジの他方の頂点を共有するエッジが抽出されるまで順次繰り返し行う。
【００２７】
かかる処理を最初に抽出した１つのエッジに接続されるエッジを抽出するまで繰り返すと、輪郭線を構成するすべての辺（エッジ）を抽出することができる。
【００２８】
本発明によれば抽出されたエッジについて、予め登録されている隣接辺についてのみエッジ判定処理を行えばよいの、輪郭線に沿った最短ルートで所与のオブジェクトを視点からみた場合のエッジを検出することができる。
【００２９】
したがって、少ない演算負荷で高速に輪郭を抽出可能な画像生成システム、プログラム及び情報記憶媒体を提供することができる。
【００３０】
しかも検出されたエッジを、輪郭線に沿って繋がれる順にソートされた形式で得ることができるので、ボリューム作成やシザリング等の処理を行う上で都合が良い。
【００３１】
（４）また本発明に係る画像生成システム、プログラム及び情報記憶媒体は、
前記隣接辺の情報は、
所与のオブジェクトを構成する辺のうち、辺を共有する２枚のプリミティブの法線ベクトルが平行な関係にある辺又は辺を共有する２枚のプリミティブの法線ベクトルが交差する関係にある辺については除外して生成されていることを特徴とする。
【００３２】
本発明によればエッジとなり得ない辺については予め省いてエッジリストを作成しておくことができるので、隣接辺情報のデータ量を削減することができる。
【００３３】
（５）また本発明に係る画像生成システム、プログラム及び情報記憶媒体は、
前記辺情報が、
所与のオブジェクトを構成する各辺について、辺の両端の頂点座標、辺を含む２のプリミティブの法線情報を含み、
前記エッジ検出手段が、
エッジ判定処理の対象となる辺の法線情報と、視点ベクトル又は光源ベクトルとに基づきエッジ判定を行うことを特徴とする。
【００３４】
【発明の実施の形態】
以下、本発明の好適な実施形態について図面を用いて説明する。
【００３５】
なお、以下に説明する本実施形態は、特許請求の範囲に記載された本発明の内容を何ら限定するものではない。また本実施形態で説明される構成の全てが本発明の解決手段として必須であるとは限らない。
【００３６】
１．構成
図１に、本実施形態の画像生成システム（例えばゲームシステム）１０の機能ブロック図の一例を示す。
【００３７】
なお同図において本実施形態は、少なくとも処理部１００を含めばよく（或いは処理部１００と記憶部１７０、或いは処理部１００と記憶部１７０と情報記憶媒体１８０を含めばよく）、それ以外のブロック（例えば操作部１６０、表示部１９０、音出力部１９２、携帯型情報記憶装置１９４、通信部１９６）については、任意の構成要素とすることができる。
【００３８】
ここで処理部１００は、システム全体の制御、システム内の各ブロックへの命令の指示、ゲーム処理、画像処理、又は音処理などの各種の処理を行うものであり、その機能は、各種プロセッサ（ＣＰＵ、ＤＳＰ等）、或いはＡＳＩＣ（ゲートアレイ等）などのハードウェアや、所与のプログラム（ゲームプログラム）により実現できる。
【００３９】
操作部１６０は、プレーヤが操作データを入力するためのものであり、その機能は、レバー、ボタン、筐体などのハードウェアにより実現できる。
【００４０】
記憶部１７０は、メインメモリ（主記憶部等）１７２やフレームバッファ（描画バッファ等）１７４等を含み、処理部１００や通信部１９６などのワーク領域となるもので、その機能はＲＡＭなどのハードウェアにより実現できる。
【００４１】
情報記憶媒体（コンピュータにより使用可能な記憶媒体）１８０は、プログラムやデータなどの情報を格納するものであり、その機能は、光ディスク（ＣＤ、ＤＶＤ）、光磁気ディスク（ＭＯ）、磁気ディスク、ハードディスク、磁気テープ、或いはメモリ（ＲＯＭ）などのハードウェアにより実現できる。処理部１００は、この情報記憶媒体１８０に格納される情報に基づいて本発明（本実施形態）の種々の処理を行う。即ち情報記憶媒体１８０には、本発明（本実施形態）の手段（特に処理部１００に含まれるブロック）を実行するための情報（プログラム或いはデータ）が格納される。
【００４２】
なお、情報記憶媒体１８０に格納される情報の一部又は全部は、システムへの電源投入時等に記憶部１７０に転送されることになる。また情報記憶媒体１８０に記憶される情報は、本発明の処理を行うためのプログラム、画像データ、音データ、表示物の形状データ、テーブルデータ、リストデータ、本発明の処理を指示するための情報、その指示に従って処理を行うための情報等の少なくとも１つを含むものである。
【００４３】
また情報記憶媒体１８０は、辺情報記憶部１８２を含む。
【００４４】
辺情報記憶部１８２は、所与のオブジェクトを構成する各辺について、辺の両端の２頂点のいずれかを共有する他の辺である隣接辺の情報を含む辺情報を記憶する。ここで前記隣接辺の情報は、所与のオブジェクトを構成する辺のうち、辺を共有する２枚のプリミティブの法線ベクトルが平行な関係にある辺又は辺を共有する２枚のプリミティブの法線ベクトルが交差する関係にある辺については除外して生成されている場合でもよい。
【００４５】
また前記辺情報は、所与のオブジェクトを構成する各辺について、辺の両端の頂点座標、辺を含む２のプリミティブの法線情報を含むようにしてもよい。
【００４６】
表示部１９０は、本実施形態により生成された画像を出力するものであり、その機能は、ＣＲＴ、ＬＣＤ、或いはＨＭＤ（ヘッドマウントディスプレイ）などのハードウェアにより実現できる。
【００４７】
音出力部１９２は、本実施形態により生成された音を出力するものであり、その機能は、スピーカなどのハードウェアにより実現できる。
【００４８】
携帯型情報記憶装置１９４は、プレーヤの個人データやセーブデータなどが記憶されるものであり、この携帯型情報記憶装置１９４としては、メモリカードや携帯型ゲーム装置などを考えることができる。
【００４９】
通信部１９６は、外部（例えばホスト装置や他の画像生成システム）との間で通信を行うための各種の制御を行うものであり、その機能は、各種プロセッサ、或いは通信用ＡＳＩＣなどのハードウェアや、プログラムなどにより実現できる。
【００５０】
なお本発明（本実施形態）の手段を実行するためのプログラム或いはデータは、ホスト装置（サーバ）が有する情報記憶媒体からネットワーク及び通信部１９６を介して情報記憶媒体１８０に配信するようにしてもよい。このようなホスト装置（サーバ）の情報記憶媒体の使用も本発明の範囲内に含まれる。
【００５１】
処理部１００は、ゲーム処理部１１０、画像生成部１３０、音生成部１５０を含む。
【００５２】
ここでゲーム処理部１１０は、コイン（代価）の受け付け処理、各種モードの設定処理、ゲームの進行処理、選択画面の設定処理、オブジェクト（１又は複数のプリミティブ面）の位置や回転角度（Ｘ、Ｙ又はＺ軸回りの回転角度）を求める処理、オブジェクトを動作させる処理（モーション処理）、視点の位置（仮想カメラの位置）や視線角度（仮想カメラの回転角度）を求める処理、マップオブジェクトなどのオブジェクトをオブジェクト空間へ配置する処理、ヒットチェック処理、ゲーム結果（成果、成績）を演算する処理、複数のプレーヤが共通のゲーム空間でプレイするための処理、或いはゲームオーバ処理などの種々のゲーム処理を、操作部１６０からの操作データや、携帯型情報記憶装置１９４からの個人データ、保存データや、ゲームプログラムなどに基づいて行う。
【００５３】
ゲーム処理部は物理シミュレーション演算処理部１２０を含む。
【００５４】
画像生成部１３０は、ゲーム処理部１１０からの指示等にしたがって各種の画像処理を行い、例えばオブジェクト空間内で仮想カメラ（視点）から見える画像を生成して、表示部１９０に出力する。
【００５５】
画像生成部１３０は、エッジ検出処理部１２０、シャドーボリューム生成処理部１２２、ジオメトリ処理部（３次元演算部）１３２、描画部（レンダリング部）１４０を含む。
【００５６】
エッジ検出処理部１２０は、前記隣接辺の情報に基づき、前記所与のオブジェクトを構成する各辺が、前記所与のオブジェクトの光源に対する輪郭を構成するエッジであるか否かのエッジ判定処理の対象となる辺を抽出し、抽出した辺についてエッジ判定処理を行う。
【００５７】
所与のオブジェクトを構成する辺についてエッジ判定処理を行い、判定結果に基づき１つのエッジを抽出し、抽出されたエッジの隣接辺の情報を前記辺情報記憶手段から読み出して、隣接辺についてエッジ判定処理を行い、判定結果に基づき、抽出されたエッジの一方の頂点を共有する次のエッジを抽出する処理を、少なくとも最初に抽出した１つのエッジの他方の頂点を共有するエッジが抽出されるまで順次繰り返し行うようにしてもよい。
【００５８】
また前記隣接辺の情報に基づき、前記所与のオブジェクトを構成する各辺が、前記所与のオブジェクトを視点からみた場合の輪郭を構成するエッジであるか否かのエッジ判定処理の対象となる辺を抽出し、抽出した辺についてエッジ判定処理を行う。
【００５９】
所与のオブジェクトを構成する辺についてエッジ判定処理を行い、判定結果に基づき１つのエッジを抽出し、抽出されたエッジの隣接辺の情報を前記辺情報記憶手段から読み出して、隣接辺についてエッジ判定処理を行い、判定結果に基づき、抽出されたエッジの一方の頂点を共有する次のエッジを抽出する処理を、少なくとも最初に抽出した１つのエッジの他方の頂点を共有するエッジが抽出されるまで順次繰り返し行うようにしてもよい。
【００６０】
ここでエッジ判定処理の対象となる辺の法線情報と、視点ベクトル又は光源ベクトルとに基づきエッジ判定を行うようにしてもよい。
【００６１】
シャドーボリューム生成処理部１２２は、抽出されたエッジを構成する頂点から光源ベクトルの方向に所与の距離離れた点に新たな頂点を生成し、前記エッジを構成する頂点と新たに生成した頂点に基づきシャドウボリュームを生成する処理を行う。
【００６２】
ここで、ジオメトリ処理部１３２は、座標変換、クリッピング処理、透視変換、或いは光源計算などの種々のジオメトリ処理（３次元演算）を行う。そして、本実施形態では、ジオメトリ処理後（透視変換後）のオブジェクトデータ（オブジェクトの頂点座標、頂点テクスチャ座標、或いは輝度データ等）は、記憶部１７０の主記憶部１７２に格納されて、保存される。
【００６３】
描画部１４０は、ジオメトリ処理後（透視変換後）のオブジェクトデータと、記憶部１７０に記憶されるテクスチャとに基づいて、オブジェクトを描画バッファ１７４に描画する。これにより、オブジェクトが移動するオブジェクト空間において、仮想カメラ（視点）から見える画像が描画（生成）されるようになる。
【００６４】
音生成部１５０は、ゲーム処理部１１０からの指示等にしたがって各種の音処理を行い、ＢＧＭ、効果音、又は音声などの音を生成し、音出力部１９２に出力する。
【００６５】
なお、ゲーム処理部１１０、仮想オブジェクト配置処理部１２０、画像生成部１３０、音生成部１５０の機能は、その全てをハードウェアにより実現してもよいし、その全てをプログラムにより実現してもよい。或いは、ハードウェアとプログラムの両方により実現してもよい。
【００６６】
なお、本実施形態の画像生成システムは、１人のプレーヤのみがプレイできるシングルプレーヤモード専用のシステムにしてもよいし、このようなシングルプレーヤモードのみならず、複数のプレーヤがプレイできるマルチプレーヤモードも備えるシステムにしてもよい。
【００６７】
また複数のプレーヤがプレイする場合に、これらの複数のプレーヤに提供するゲーム画像やゲーム音を、１つの端末を用いて生成してもよいし、ネットワーク（伝送ライン、通信回線）などで接続された複数の端末を用いて生成してもよい。
【００６８】
２．本実施形態の特徴と処理
本実施の形態の特徴と処理を図面を用いて説明する。
【００６９】
本実施の形態では、所与のオブジェクトを構成する各辺について、辺の両端の２頂点のいずれかを共有する他の辺である隣接辺の情報を含む辺情報を記憶する。
【００７０】
図２〜図６を用いて本実施の形態の辺情報について説明する。
【００７１】
図２は、所与オブジェクトの一例である。
【００７２】
所与のオブジェクト２１０は、同図に示すように頂点ｖ１〜ｖ１２、辺ｌ１〜１２を有する立方体オブジェクトである。
【００７３】
図３は、本実施の形態の隣接辺の情報について説明するための図である。
【００７４】
本実施の形態では所与のオブジェクトの各辺について、予め隣接辺についての情報を調べて、図３に示すような隣接辺リスト２２０を作成し、記憶手段に記憶させておく。
【００７５】
隣接辺リスト２２０は、所与のオブジェクトの各辺２３０に関連付けて、各辺の隣接辺情報２４０を記憶する。隣接辺とは、所与の辺の両端の頂点のいずれかを共有する辺である。
【００７６】
例えば図２の辺ｌ１の辺の両端の頂点はｖ１、ｖ２である。ここで辺ｌ１は辺ｌ４、ｌ５と頂点ｖ１を共有し、辺ｌ２、ｌ６と頂点ｖ２を共有する。従って辺ｌ１に関連づけて、辺ｌ４、ｌ５、ｌ２、ｌ６が隣接辺情報として記憶されている（２５０参照）。
【００７７】
また各辺の隣接辺情報は、各辺の両端の頂点のいずれの頂点を共有しているかについての情報を有している。ここで各辺について、両端の頂点を便宜的にＶ１、Ｖ２に分類する。例えば辺ｌ１についてｖ１をＶ１、ｖ２をＶ２とする。２５２のｌ４（１）は、辺ｌ４が頂点Ｖ１（ここではｖ１）を共有する隣接辺であることを示している。また２５４のｌ２（０）は、辺ｌ２が頂点Ｖ２（ここではｖ２）を共有する隣接辺であることを示している。
【００７８】
例えば２４２、２４４に示すように各辺の隣接辺についていずれの頂点を共有しているかによって、２つのテーブル（ジャンプテーブル１、ジャンプテーブル２）に分類して記憶させるようにしてもよい。
【００７９】
図４は、隣接辺情報の構成の一例について説明するための図である。例えば図４に示すように８ビットのエリアに１つの隣接辺情報を記憶させる場合、１ビット目に頂点種別２７２を２から８ビット目に辺インデックス２７４を記憶させるようにしてもよい。
【００８０】
頂点種別２７２とは共有する頂点がＶ１であるのかＶ２であるのかを示す分類である。例えば頂点Ｖ１を共有する場合にはビット’０’が、頂点Ｖ２を共有する場合にはビット’１’が格納されている。
【００８１】
ここでＶ１、Ｖ２は辺を構成する２つの頂点を便宜的に分類したものであり、例えば図６の辺リストにおいて各辺について頂点Ｖ１として記憶されている頂点（図６の３３０参照）を共有している場合には共有する頂点はＶ１であり、各辺について頂点Ｖ２として記憶されている頂点（図６の３４０参照）を共有している場合には共有する頂点はＶ２である。
【００８２】
辺インデックス２７２には例えば、図３の隣接辺リストや図５の辺リストの各辺を特定するためのインデックス番号（リストの何番目二等録されているかを示す番号）を格納するようにしてもよい。またインデックス番号に限れず、対応する辺の隣接辺情報や辺情報をアクセス可能な他の情報でもよい。
【００８３】
ここで所与のオブジェクトを構成する辺のうち、辺を共有する２枚のプリミティブの法線ベクトルが平行な関係にある辺又は辺を共有する２枚のプリミティブの法線ベクトルが交差する関係にある辺については除外して隣接辺の情報を生成するようにしてもよい。
【００８４】
図５（Ａ）（Ｂ）（Ｃ）は辺を共有する２枚のプリミティブの法線ベクトルについて説明するための図である。図５（Ａ）に示すように辺ｌ１は２つのポリゴン（プリミティブの一例）ＰＡ、ＰＢに共有されている。ここでポリゴンＰＡの法線ベクトルをＮＡ１、ポリゴンＰＢの法線ベクトルをＮＢ１とする。
【００８５】
ここで例えば図５（Ｂ）に示すようにポリゴンＰＡの法線ベクトルをＮＡ１とポリゴンＰＢの法線ベクトルＮＢ１が平行な関係にある場合には、エッジ（輪郭を構成する辺）となり得ない。
【００８６】
エッジとなり得るか否かは、例えばＮＡとＮＢの内積をとって調べるようにしても良い。すなわち辺を共有するポリゴンの法線ベクトルＮＡとＮＢの内積が１（多少の誤差範囲は含む）である場合にはエッジになりえない。
【００８７】
また例えば図５（Ｃ）に示すようにポリゴンＰＡの法線ベクトルをＮＡ１とポリゴンＰＢの法線ベクトルＮＢ１が交差する行な関係にある場合には、ポリゴンＰＡとポリゴンＰＢは光源や視点に対して凹形状をなしており（ポリゴンＰＡとＰＢが向き合っている）、エッジ（輪郭を構成する辺）となり得ない。
【００８８】
このようなエッジとなり得ない辺については、隣接辺情報を作成しなくてもよい。すなわちこのようなエッジとなり得ない辺については予め省いてエッジリストを作成しておくと隣接辺情報（エッジリスト）のデータ量を削減することができる。
【００８９】
なお図２及び図５では説明を簡単にするためにポリゴン４角形としているが、３角形のポリゴンでもよい。（実際のハードウエア上では３角形のポリゴンとして扱う場合がおおい）。
【００９０】
図６は、本実施の形態の辺情報について説明するための図である。
【００９１】
本実施の形態では所与のオブジェクトの各辺について、予め辺についての情報（辺情報）を調べて、図６に示すような辺リスト３１０を作成し、記憶手段に記憶させておく。辺情報として例えば、所与のオブジェクトを構成する各辺３２０について、辺の両端の頂点座標（頂点Ｖ１（３３０）、頂点Ｖ２（３４０））辺を含む２のプリミティブの法線情報（法線ＮＡ（３５０）、ＮＢ（３６０）を含むようにしてもよい。また図２で説明した隣接辺情報６７０も辺情報としてもたせるようにしてもよい。
【００９２】
ここで頂点Ｖ１（３３０）、Ｖ２（３４０）は辺を構成する２つの頂点を便宜的に分類したものであり、辺を構成する２つの頂点の頂点座標（仮想３次元空間（例えばワールド座標系）におけるｘｙｚ座標）が記憶されている。
また法線ＮＡ（３５０）、法線ＮＢ（３６０）は辺を共有する２つのポリゴンの法線情報を便宜的に分類したものであり、２つのポリゴンの法線ベクトルのｘｙｚ成分等が記憶されている。
【００９３】
例えば図２の辺ｌ１の辺の頂点Ｖ１（３３０）にはｖ１の座標、頂点Ｖ２（３４０）にはｖ２の座標、法線ＮＡ（３５０）にはポリゴンＰＡの法線ベクトルＮＡのｘｙｚ成分、法線ＮＢ（３６０）にはポリゴンＰＡの法線ベクトルＮＢのｘｙｚ成分、隣接辺情報（３７０）には図３の２５０に示す隣接辺情報が辺情報として記憶されている（３８０参照）。
【００９４】
なお辺の両端の頂点座標はリアルタイムに変化する場合には、リアルタイムにセットされるようにしてもよい。また法線ベクトルや隣接辺の情報のように変化しない情報については、予め設定しておくことができる。
【００９５】
次に本実施の形態のエッジ検出処理の第１の実施形態について説明する。
【００９６】
第１の実施形態では、前記隣接辺の情報に基づき、前記所与のオブジェクトを構成する各辺が、前記所与のオブジェクトの光源に対する輪郭を構成するエッジであるか否かのエッジ判定処理の対象となる辺を抽出し、抽出した辺についてエッジ判定処理を行い、前記所与のオブジェクトの光源に対するエッジを検出する処置を行う。
【００９７】
ここで光源に対する輪郭とは点光源に対する輪郭でもよいし平行光源に対する輪郭でもよい。
【００９８】
図７は所与のオブジェクトの光源にたいする輪郭を構成するエッジについて説明するための図である。所与のオブジェクト４３０の光源４１０に対する輪郭とは光源からみえる面の輪郭を構成する辺である。ここで光源からみえる面（ポリゴン）Ｐ１、Ｐ２とすると、Ｐ１、Ｐ２の輪郭を構成する辺ｌ１、ｌ６、ｌ１０、ｌ７、ｌ３，ｌ４が光源にたいする輪郭を構成するエッジとなる。
【００９９】
このように輪郭線は必ず連続して閉じた線となる。従って本実施の形態では、まず、所与のオブジェクト３０を構成する辺についてエッジ判定処理を行い、判定結果に基づき１つのエッジを抽出する。すなわち例えば図６に示す辺リストの辺を所定の順番で読み出してエッジ判定処理を行い、１つのエッジを抽出する。一番最初に見つかったエッジを１つのエッジとして抽出すると良い。
【０１００】
エッジ判定処理は、例えば判定対象となる辺の法線ベクトルＮＡ、ＮＢを辺情報から読み出してと光源ベクトルと内積をとり内積の符号が逆（２の内積が正と負）であればエッジであると判定するようにしても良い。
【０１０１】
ここで光源が平行光源で有る場合はエッジ判定を行う際の頂点位置に関わらず平行なベクトルを光源ベクトル４２０として用いる。また光源が点光源である場合には光源と辺の頂点を結ぶベクトルを光源ベクトルとして用いる。
【０１０２】
次に、抽出されたエッジの隣接辺の情報を前記辺情報記憶手段から読み出して、隣接辺についてエッジ判定処理を行い、判定結果に基づき、抽出されたエッジの一方の頂点を共有する次のエッジを抽出する処理を、少なくとも最初に抽出した１つのエッジの他方の頂点を共有するエッジが抽出されるまで順次繰り返し行う。  例えば辺リストの辺について最初から順にエッジ判定を行うと、辺ｌ１が一番最初に抽出されたエッジとなる。ここで辺ｌ１の頂点ｖ１（Ｖ１とする）を頂点リスト４９０に登録しておくとよい（４９１参照）。頂点リスト４９０とは輪郭線を構成するエッジの頂点を接続順に（輪郭線を辺の接続順に一筆書きでかく場合の順番で）記憶したものである。
【０１０３】
この場合ｌ１についての隣接辺情報を読み出し、読み出した隣接辺についてエッジ判定処理を行い、次のエッジを検出する。輪郭線は必ず連続して閉じた線となるので、辺の両端の各頂点を辺（隣接辺）の中に次のエッジとなる辺があるはずだからである。
【０１０４】
そこで例えば辺の両端の頂点ｖ１（Ｖ１とする）、ｖ２（Ｖ２とする）のいずれの頂点に接続されるエッジを抽出するのか決定して、ジャンプテーブル１又はジャンプテーブル２を使用して辺情報を読み出してエッジ判定を行う。例えば頂点ｖ２（Ｖ２とする）に接続されるエッジを抽出する場合には辺ｌ１のジャンプテーブル２を参照する。ここで辺ｌ１のジャンプテーブル２には辺ｌ２と辺ｌ６が記憶されているので（図２参照）、辺ｌ２及び辺ｌ６について辺リストから辺情報を読み出してエッジ判定処理を行う。すると辺ｌ６が次にエッジとして抽出される。
【０１０５】
ここで頂点ｖ２をエッジを構成する頂点として頂点リスト４９０に登録しておくとよい（４９２参照）
辺ｌ６の両端の頂点はｖ２とｖ６である。ここでｖ２についてはすでに頂点リスト４９０に登録されているので、ｖ６に接続される隣接辺の情報を読み出して、エッジ判定処理を行い、ｖ６に接続される次の辺（エッジ）を抽出し、頂点ｖ６をエッジを構成する頂点として頂点リスト４９０に登録しておくとよい（４９３参照）。
【０１０６】
このようにして、エッジとした抽出した辺について、頂点リストに登録していない方の頂点に接続される隣接辺についてエッジ判定処理を行い次のエッジを検出する処理を、最初に抽出した１つのエッジ（ここでは辺ｌ１）に接続されるエッジ（ここでは辺ｌ４）を抽出するまで繰り返すと、輪郭線を構成するすべての辺（エッジ）を抽出することができる。
【０１０７】
このように本実施の形態によれば閉じた凸型オブジェクトのエッジを最短ルートで検出することができる。そして検出されたエッジを、輪郭線に沿って繋がれる順にソートされた形式で得ることができる。
【０１０８】
また頂点リストとして、輪郭線上の頂点を接続順にソートされた形式で得ることができる。
【０１０９】
本実施の形態では、抽出されたエッジを構成する頂点から光源ベクトルの方向に所与の距離離れた点に新たな頂点を生成し、前記エッジを構成する頂点と新たに生成した頂点に基づきシャドウボリュームを生成する処理を行う。
【０１１０】
図８は、本実施の形態のシャドーボリューム生成処理の一例について説明するための図である。
【０１１１】
ここで光源５１０に対し、輪郭線５１０として抽出されたエッジを構成する頂点は、ｖ１，ｖ２，ｖ６、ｖ７，ｖ３，ｖ４である。これらの各頂点から光源ベクトルの方向（例えば頂点ｖ１の場合４２０−１、頂点ｖ２の場合４２０−２頂点ｖ６の場合４２０−３、頂点ｖ７の場合４２０−４、頂点ｖ３の場合４２０−５、頂点ｖ４の場合４２０−６）に所与の距離離れた点に新たな頂点ｖ１’，ｖ２’，ｖ６’、ｖ７’，ｖ３’，ｖ４’を生成する。
【０１１２】
図９（Ａ）（Ｂ）（Ｃ）はトライアングルストリップ及びトライアングルファンを用いてシャドーボリュームを生成する処理について説明するための図である。
【０１１３】
トライアングルストリップはハードウエアが有する機能であり、例えば図９（Ａ）に示すように、頂点がＶ１、Ｖ２、Ｖ３、Ｖ４、ＶＢ５の順で置かれた場合に、頂点Ｖ１，Ｖ３，Ｖ３からなるポリゴンＰ１、頂点Ｖ２，Ｖ３，Ｖ４からなるポリゴンＰ２、頂点Ｖ３，Ｖ４，Ｖ５からなるポリゴンＰ３を順次生成する機能である。
【０１１４】
トライアングルファンはハードウエアが有する機能であり、例えば図９（Ｂ）に示すように、頂点がＶ１、Ｖ２、Ｖ３、Ｖ４、ＶＢ５の順で置かれた場合に、頂点Ｖ１，Ｖ３，Ｖ３からなるポリゴンＰ１、頂点Ｖ３，Ｖ１，Ｖ４からなるポリゴンＰ２、頂点Ｖ４，Ｖ１，Ｖ５からなるポリゴンＰ３を順次生成する機能である。
【０１１５】
ここで例えば図９（Ｃ）に示すように、頂点をｖ１，ｖ１’，ｖ２，ｖ２’，ｖ６、ｖ６’、ｖ７、ｖ７’，ｖ３、ｖ３’，ｖ４、ｖ４’とおいていくことで、ハードウエアが有するトライアングルストリップの機能により、頂点ｖ１，ｖ’１、ｖ２からなるポリゴンＰ１、頂点ｖ’１、ｖ２，ｖ’２からなるポリゴン、頂点ｖ２，ｖ’２，ｖ６からなるポリゴンＰ３、・・・が生成される。
【０１１６】
またハードウエアが有するトライアングルファンの機能により、頂点ｖ１，ｖ４、ｖ２からなるポリゴンＰ１２、頂点ｖ２、ｖ４，ｖ３からなるポリゴンＰ１２、頂点ｖ３，ｖ２，ｖ７からなるポリゴンＰ１３、・・・が生成される。
【０１１７】
本実施の形態では輪郭線を構成する頂点を輪郭線に沿って繋がれる順にソートされた形式で得ることができるので、ハードウエアが有するトライアングルストリップの機能やトライアングルファンの機能を使用することにより、頂点をｖ１，ｖ１’，ｖ２，ｖ２’，ｖ６、ｖ６’、ｖ７、ｖ７’，ｖ３、ｖ３’，ｖ４、ｖ４’により構成されるをシャドーボリュームを生成することができる
図１０、図１１は第１の実施形態のエッジ検出処理について説明するためのフローチャート図である。
【０１１８】
まずインデックスカウンタｉに初期値０を設定する（ステップＳ１０）。インデックスカウンタｉは、辺情報（辺リスト）を読み出す際のインデックスとして使用するカウンタであり、最初のエッジを抽出する時の辺情報（辺リスト）読み出しに使用する。
【０１１９】
次に辺情報（ｉ）の法線ＮＡ（ｉ）、ＮＢ（ｉ）を読み出し、光源ベクトルとの内積を取る（ステップＳ２０）。
【０１２０】
そして光源ベクトルと法線ＮＡ、ＮＢそれぞれとの内積の符号が異なるか否かのエッジ判定を行い、符号が同じ場合にはインデックスカウンタｉをインクリメントして（ステップＳ４０）、再びステップＳ２０に戻ってＳ２０〜Ｓ３０の処理を繰り返す（ステップＳ３０）。
【０１２１】
次に法線ＮＡ（ｉ）と光源ベクトルの内積が正か負か判断し、法線ＮＡ（ｉ）と光源ベクトルの内積が負である場合にはＶ１を頂点リストに代入し、スタートインデックスＳＩに０を代入する（ステップＳ５０，Ｓ６０）。
【０１２２】
また法線ＮＡ（ｉ）と光源ベクトルの内積が正である場合にはＶ２を頂点リストに代入し、スタートインデックスＳＩに１を代入する（ステップＳ５０，Ｓ７０）。
【０１２３】
ここでスタートインデックスとは検出した頂点が視点であるか終点であるかをしめす変数である。第１のエッジ（頂点ｖ１、ｖ２）のｖ２につながる第２のエッジ（頂点ｖ１’、ｖ２’）を検出する場合、第１のエッジのｖ２は第２のエッジのｖ１’とｖ２’のどちらを共有するかをスタートインデックスを用いて把握する。
【０１２４】
次にスタートインデックスＳＩが１である場合にはＶ１を頂点リスト代入し、ＪＴにジャンプテーブル１を代入する（ステップＳ８０，Ｓ９０）。
【０１２５】
またスタートインデックスＳＩが０である場合にはＶ２を頂点リスト代入し、ＪＴにジャンプテーブル２を代入する（ステップＳ８０，Ｓ１００）。
【０１２６】
次にインデックスカウンタｊに初期値０を設定する（ステップＳ１１０）。インデックスカウンタｊは、ジャンプテーブルＪＴを読み出す際のインデックスとして使用するカウンタである。
【０１２７】
次にインデックスカウンタｊをインクリメントする（ステップＳ１２０）。
【０１２８】
次にジャンプテーブルＪＴ（ｊ）を使い、隣接辺の辺情報を読み出しす（ステップＳ１３０）。
【０１２９】
次に読み出した辺情報の法線ＮＡ、ＮＢと、光源ベクトルと内積を取る（ステップＳ１４０）。
【０１３０】
次に光源ベクトルと法線ＮＡ、ＮＢそれぞれとの内積の符号が異なるか否かのエッジ判定を行い、符号が同じ場合には再びステップＳ１２０に戻ってＳ１２０〜Ｓ１５０の処理を繰り返す（ステップＳ１５０）。
【０１３１】
符号が異なる場合、にジャンプテーブルの最上位ビットをスタートインデックスに代入する（ステップＳ１５０，Ｓ１６０）。
【０１３２】
そして辺情報が最初に抽出したエッジでなければ再びステップＳ８０に戻ってステップＳ８０〜Ｓ１７０の処理を繰り返す（ステップＳ１７０）。
【０１３３】
次に本実施の形態のエッジ検出処理の第２の実施形態について説明する。
【０１３４】
第２の実施形態では、前記隣接辺の情報に基づき、前記所与のオブジェクトを構成する各辺が、前記所与のオブジェクトを視点から見た場合の輪郭を構成するエッジであるか否かのエッジ判定処理の対象となる辺を抽出し、抽出した辺についてエッジ判定処理を行い、前記所与のオブジェクトの光源に対するエッジを検出する処置を行う。
【０１３５】
図１２は所与のオブジェクトを視点から見た場合の輪郭を構成するエッジについて説明するための図である。所与のオブジェクト６３０の視点６１０に対する輪郭とは視点からみえる面の輪郭を構成する辺である。ここで視点からみえる面（ポリゴン）Ｐ１、Ｐ２とすると、Ｐ１、Ｐ２の輪郭を構成する辺ｌ１、ｌ６、ｌ１０、ｌ７、ｌ３，ｌ４が視点から見た場合の輪郭を構成するエッジとなる。
【０１３６】
このように輪郭線は必ず連続して閉じた線となる。従って本実施の形態では、まず、所与のオブジェクト３０を構成する辺についてエッジ判定処理を行い、判定結果に基づき１つのエッジを抽出する。すなわち例えば図６に示す辺リストの辺を所定の順番で読み出してエッジ判定処理を行い、１つのエッジを抽出する。一番最初に見つかったエッジを１つのエッジとして抽出すると良い。
【０１３７】
エッジ判定処理は、例えば判定対象となる辺の法線ベクトルＮＡ、ＮＢを辺情報から読み出してと視点ベクトルと内積をとり内積の符号が逆（２の内積が正と負）であればエッジであると判定するようにしても良い。
【０１３８】
ここで視点ベクトルは、視点と辺の頂点を結ぶベクトルである。
【０１３９】
次に、抽出されたエッジの隣接辺の情報を前記辺情報記憶手段から読み出して、隣接辺についてエッジ判定処理を行い、判定結果に基づき、抽出されたエッジの一方の頂点を共有する次のエッジを抽出する処理を、少なくとも最初に抽出した１つのエッジの他方の頂点を共有するエッジが抽出されるまで順次繰り返し行う。
【０１４０】
例えば辺リストの辺について最初から順にエッジ判定を行うと、辺ｌ１が一番最初に抽出されたエッジとなる。ここで辺ｌ１の頂点ｖ１（Ｖ１とする）を頂点リスト６９０に登録しておくとよい（６９１参照）。頂点リスト６９０とは輪郭線を構成するエッジの頂点を接続順に（輪郭線を辺の接続順に一筆書きでかく場合の順番で）記憶したものである。
【０１４１】
この場合ｌ１についての隣接辺情報を読み出し、読み出した隣接辺についてエッジ判定処理を行い、次のエッジを検出する。輪郭線は必ず連続して閉じた線となるので、辺の両端の各頂点を辺（隣接辺）の中に次のエッジとなる辺があるはずだからである。
【０１４２】
そこで例えば辺の両端の頂点ｖ１（Ｖ１とする）、ｖ２（Ｖ２とする）のいずれの頂点に接続されるエッジを抽出するのか決定して、ジャンプテーブル１又はジャンプテーブル２を使用して辺情報を読み出してエッジ判定を行う。例えば頂点ｖ２（Ｖ２とする）に接続されるエッジを抽出する場合には辺ｌ１のジャンプテーブル２を参照する。ここで辺ｌ１のジャンプテーブル２には辺ｌ２と辺ｌ６が記憶されているので（図２参照）、辺ｌ２及び辺ｌ６について辺リストから辺情報を読み出してエッジ判定処理を行う。すると辺ｌ６が次にエッジとして抽出される。
【０１４３】
ここで頂点ｖ２をエッジを構成する頂点として頂点リスト６９０に登録しておくとよい（６９２参照）
辺ｌ６の両端の頂点はｖ２とｖ６である。ここでｖ２についてはすでに頂点リスト６９０に登録されているので、ｖ６に接続される隣接辺の情報を読み出して、エッジ判定処理を行い、ｖ６に接続される次の辺（エッジ）を抽出し、頂点ｖ６をエッジを構成する頂点として頂点リスト４９０に登録しておくとよい（６９３参照）。
【０１４４】
このようにして、エッジとした抽出した辺について、頂点リストに登録していない方の頂点に接続される隣接辺についてエッジ判定処理を行い次のエッジを検出する処理を、最初に抽出した１つのエッジ（ここでは辺ｌ１）に接続されるエッジ（ここでは辺ｌ４）を抽出するまで繰り返すと、輪郭線を構成するすべての辺（エッジ）を抽出することができる。
【０１４５】
このように本実施の形態によれば閉じた凸型オブジェクトのエッジを最短ルートで検出することができる。そして検出されたエッジを、輪郭線に沿って繋がれる順にソートされた形式で得ることができる。
【０１４６】
また頂点リストとして、輪郭線上の頂点を接続順にソートされた形式で得ることができる。
【０１４７】
図１３、図１４は第２の実施形態のエッジ検出処理について説明するためのフローチャート図である。
【０１４８】
まずインデックスカウンタｉに初期値０を設定する（ステップＳ２１０）。インデックスカウンタｉは、辺情報（辺リスト）を読み出す際のインデックスとして使用するカウンタであり、最初のエッジを抽出する時の辺情報（辺リスト）読み出しに使用する。
【０１４９】
次に辺情報（ｉ）の法線ＮＡ（ｉ）、ＮＢ（ｉ）を読み出し、視点ベクトルとの内積を取る（ステップＳ２２０）。
【０１５０】
そして視点ベクトルと法線ＮＡ、ＮＢそれぞれとの内積の符号が異なるか否かのエッジ判定を行い、符号が同じ場合にはインデックスカウンタｉをインクリメントして（ステップＳ２４０）、再びステップＳ２２０に戻ってＳ２２０〜Ｓ２３０の処理を繰り返す（ステップＳ２３０）。
【０１５１】
次に法線ＮＡ（ｉ）と視点ベクトルの内積が正か負か判断し、法線ＮＡ（ｉ）と視点ベクトルの内積が負である場合にはＶ１を頂点リストに代入し、スタートインデックスＳＩに０を代入する（ステップＳ２５０，Ｓ２６０）。
【０１５２】
また法線ＮＡ（ｉ）と視点ベクトルの内積が正である場合にはＶ２を頂点リストに代入し、スタートインデックスＳＩに１を代入する（ステップＳ２５０，Ｓ２７０）。
【０１５３】
ここでスタートインデックスとは検出した頂点が視点であるか終点であるかをしめす変数である。第１のエッジ（頂点ｖ１、ｖ２）のｖ２につながる第２のエッジ（頂点ｖ１’、ｖ２’）を検出する場合、第１のエッジのｖ２は第２のエッジのｖ１’とｖ２’のどちらを共有するかをスタートインデックスを用いて把握する。
【０１５４】
次にスタートインデックスＳＩが１である場合にはＶ１を頂点リスト代入し、ＪＴにジャンプテーブル１を代入する（ステップＳ２８０，Ｓ２９０）。
【０１５５】
またスタートインデックスＳＩが０である場合にはＶ２を頂点リスト代入し、ＪＴにジャンプテーブル２を代入する（ステップＳ２８０，Ｓ３００）。
【０１５６】
次にインデックスカウンタｊに初期値０を設定する（ステップＳ３１０）。インデックスカウンタｊは、ジャンプテーブルＪＴを読み出す際のインデックスとして使用するカウンタである。
【０１５７】
次にインデックスカウンタｊをインクリメントする（ステップＳ３２０）。
【０１５８】
次にジャンプテーブルＪＴ（ｊ）を使い、隣接辺の辺情報を読み出しす（ステップＳ３３０）。
【０１５９】
次に読み出した辺情報の法線ＮＡ、ＮＢと、視点ベクトルと内積を取る（ステップＳ３４０）。
【０１６０】
次に視点ベクトルと法線ＮＡ、ＮＢそれぞれとの内積の符号が異なるか否かのエッジ判定を行い、符号が同じ場合には再びステップＳ３２０に戻ってＳ３２０〜Ｓ３５０の処理を繰り返す（ステップＳ３５０）。
【０１６１】
符号が異なる場合、にジャンプテーブルの最上位ビットをスタートインデックスに代入する（ステップＳ３５０，Ｓ３６０）。
【０１６２】
そして辺情報が最初に抽出したエッジでなければ再びステップＳ２８０に戻ってステップＳ２８０〜Ｓ３７０の処理を繰り返す（ステップＳ３７０）。
【０１６３】
３．ハードウェア構成
次に、本実施形態を実現できるハードウェアの構成の一例について図１５を用いて説明する。
【０１６４】
メインプロセッサ９００は、ＣＤ９８２（情報記憶媒体）に格納されたプログラム、通信インターフェース９９０を介して転送されたプログラム、或いはＲＯＭ９５０（情報記憶媒体の１つ）に格納されたプログラムなどに基づき動作し、ゲーム処理、画像処理、音処理などの種々の処理を実行する。
【０１６５】
コプロセッサ９０２は、メインプロセッサ９００の処理を補助するものであり、高速並列演算が可能な積和算器や除算器を有し、マトリクス演算（ベクトル演算）を高速に実行する。例えば、オブジェクトを移動させたり動作（モーション）させるための物理シミュレーションに、マトリクス演算などの処理が必要な場合には、メインプロセッサ９００上で動作するプログラムが、その処理をコプロセッサ９０２に指示（依頼）する。
【０１６６】
ジオメトリプロセッサ９０４は、座標変換、透視変換、光源計算、曲面生成などのジオメトリ処理を行うものであり、高速並列演算が可能な積和算器や除算器を有し、マトリクス演算（ベクトル演算）を高速に実行する。例えば、座標変換、透視変換、光源計算などの処理を行う場合には、メインプロセッサ９００で動作するプログラムが、その処理をジオメトリプロセッサ９０４に指示する。
【０１６７】
データ伸張プロセッサ９０６は、圧縮された画像データや音データを伸張するデコード処理を行ったり、メインプロセッサ９００のデコード処理をアクセレートする処理を行う。これにより、オープニング画面、インターミッション画面、エンディング画面、或いはゲーム画面などにおいて、所与の画像圧縮方式で圧縮された動画像を表示できるようになる。なお、デコード処理の対象となる画像データや音データは、ＲＯＭ９５０、ＣＤ９８２に格納されたり、或いは通信インターフェース９９０を介して外部から転送される。
【０１６８】
描画プロセッサ９１０は、ポリゴンや曲面などのプリミティブ面で構成されるオブジェクトの描画（レンダリング）処理を高速に実行するものである。オブジェクトの描画の際には、メインプロセッサ９００は、ＤＭＡコントローラ９７０の機能を利用して、オブジェクトデータを描画プロセッサ９１０に渡すと共に、必要であればテクスチャ記憶部９２４にテクスチャを転送する。すると、描画プロセッサ９１０は、これらのオブジェクトデータやテクスチャに基づいて、Ｚバッファなどを利用した陰面消去を行いながら、オブジェクトをフレームバッファ９２２に高速に描画する。また、描画プロセッサ９１０は、αブレンディング（半透明処理）、デプスキューイング、ミップマッピング、フォグ処理、バイリニア・フィルタリング、トライリニア・フィルタリング、アンチエリアシング、シェーディング処理なども行うことができる。そして、１フレーム分の画像がフレームバッファ９２２に書き込まれると、その画像はディスプレイ９１２に表示される。
【０１６９】
サウンドプロセッサ９３０は、多チャンネルのＡＤＰＣＭ音源などを内蔵し、ＢＧＭ、効果音、音声などの高品位のゲーム音を生成する。生成されたゲーム音は、スピーカ９３２から出力される。
【０１７０】
ゲームコントローラ９４２からの操作データや、メモリカード９４４からのセーブデータ、個人データは、シリアルインターフェース９４０を介してデータ転送される。
【０１７１】
ＲＯＭ９５０にはシステムプログラムなどが格納される。なお、業務用ゲームシステムの場合には、ＲＯＭ９５０が情報記憶媒体として機能し、ＲＯＭ９５０に各種プログラムが格納されることになる。なお、ＲＯＭ９５０の代わりにハードディスクを利用するようにしてもよい。
【０１７２】
ＲＡＭ９６０は、各種プロセッサの作業領域として用いられる。
【０１７３】
ＤＭＡコントローラ９７０は、プロセッサ、メモリ（ＲＡＭ、ＶＲＡＭ、ＲＯＭ等）間でのＤＭＡ転送を制御するものである。
【０１７４】
ＣＤドライブ９８０は、プログラム、画像データ、或いは音データなどが格納されるＣＤ９８２（情報記憶媒体）を駆動し、これらのプログラム、データへのアクセスを可能にする。
【０１７５】
通信インターフェース９９０は、ネットワークを介して外部との間でデータ転送を行うためのインターフェースである。この場合に、通信インターフェース９９０に接続されるネットワークとしては、通信回線（アナログ電話回線、ＩＳＤＮ）、高速シリアルバスなどを考えることができる。そして、通信回線を利用することでインターネットを介したデータ転送が可能になる。また、高速シリアルバスを利用することで、他のゲームシステム、他のゲームシステムとの間でのデータ転送が可能になる。
【０１７６】
なお、本発明の各手段は、その全てを、ハードウェアのみにより実行してもよいし、情報記憶媒体に格納されるプログラムや通信インターフェースを介して配信されるプログラムのみにより実行してもよい。或いは、ハードウェアとプログラムの両方により実行してもよい。
【０１７７】
そして、本発明の各手段をハードウェアとプログラムの両方により実行する場合には、情報記憶媒体には、本発明の各手段をハードウェアを利用して実行するためのプログラムが格納されることになる。より具体的には、上記プログラムが、ハードウェアである各プロセッサ９０２、９０４、９０６、９１０、９３０等に処理を指示すると共に、必要であればデータを渡す。そして、各プロセッサ９０２、９０４、９０６、９１０、９３０等は、その指示と渡されたデータとに基づいて、本発明の各手段を実行することになる。
【０１７８】
図１６（Ａ）に、本実施形態を業務用ゲームシステムに適用した場合の例を示す。プレーヤは、ディスプレイ１１００上に映し出されたゲーム画像を見ながら、レバー１１０２、ボタン１１０４等を操作してゲームを楽しむ。内蔵されるシステムボード（サーキットボード）１１０６には、各種プロセッサ、各種メモリなどが実装される。そして、本発明の各手段を実行するための情報（プログラム又はデータ）は、システムボード１１０６上の情報記憶媒体であるメモリ１１０８に格納される。以下、この情報を格納情報と呼ぶ。
【０１７９】
図１６（Ｂ）に、本実施形態を家庭用のゲームシステムに適用した場合の例を示す。プレーヤはディスプレイ１２００に映し出されたゲーム画像を見ながら、ゲームコントローラ１２０２、１２０４を操作してゲームを楽しむ。この場合、上記格納情報は、本体システムに着脱自在な情報記憶媒体であるＣＤ１２０６、或いはメモリカード１２０８、１２０９等に格納されている。
【０１８０】
図１６（Ｃ）に、ホスト装置１３００と、このホスト装置１３００とネットワーク１３０２（ＬＡＮのような小規模ネットワークや、インターネットのような広域ネットワーク）を介して接続される端末１３０４−１〜１３０４−ｎとを含むシステムに本実施形態を適用した場合の例を示す。この場合、上記格納情報は、例えばホスト装置１３００が制御可能な磁気ディスク装置、磁気テープ装置、メモリ等の情報記憶媒体１３０６に格納されている。端末１３０４−１〜１３０４−ｎが、スタンドアロンでゲーム画像、ゲーム音を生成できるものである場合には、ホスト装置１３００からは、ゲーム画像、ゲーム音を生成するためのゲームプログラム等が端末１３０４−１〜１３０４−ｎに配送される。一方、スタンドアロンで生成できない場合には、ホスト装置１３００がゲーム画像、ゲーム音を生成し、これを端末１３０４−１〜１３０４−ｎに伝送し端末において出力することになる。
【０１８１】
なお、図１６（Ｃ）の構成の場合に、本発明の各手段を、ホスト装置（サーバー）と端末とで分散して実行するようにしてもよい。また、本発明の各手段を実行するための上記格納情報を、ホスト装置（サーバー）の情報記憶媒体と端末の情報記憶媒体に分散して格納するようにしてもよい。
【０１８２】
またネットワークに接続する端末は、家庭用ゲームシステムであってもよいし業務用ゲームシステムであってもよい。そして、業務用ゲームシステムをネットワークに接続する場合には、業務用ゲームシステムとの間で情報のやり取りが可能であると共に家庭用ゲームシステムとの間でも情報のやり取りが可能なセーブ用情報記憶装置（メモリカード、携帯型ゲーム装置）を用いることが望ましい。
【０１８３】
なお本発明は、上記実施形態で説明したものに限らず、種々の変形実施が可能である。
【０１８４】
たとえば本実施の形態では、判定対象となる辺の法線ベクトルＮＡ、ＮＢを用いて光源ベクトルや視点ベクトル内積をとりエッジ判定を行う場合を例似鳥説明したがこれに限れない。例えば他の方法でエッジ判定を行う場合でもよい。
【０１８５】
例えば、本発明のうち従属請求項に係る発明においては、従属先の請求項の構成要件の一部を省略する構成とすることもできる。また、本発明の１の独立請求項に係る発明の要部を、他の独立請求項に従属させることもできる。
【０１８６】
また、本発明は種々のゲーム（格闘ゲーム、シューティングゲーム、ロボット対戦ゲーム、スポーツゲーム、競争ゲーム、ロールプレイングゲーム、音楽演奏ゲーム、ダンスゲーム等）に適用できる。
【０１８７】
また本発明は、業務用ゲームシステム、家庭用ゲームシステム、多数のプレーヤが参加する大型アトラクションシステム、シミュレータ、マルチメディア端末、ゲーム画像を生成するシステムボード等の種々のゲームシステムに適用できる。
【図面の簡単な説明】
【図１】本実施形態の画像生成システム（例えばゲームシステム）の機能ブロック図の一例である。
【図２】所与オブジェクトの一例である。
【図３】本実施の形態の隣接辺の情報について説明するための図である。
【図４】隣接辺情報の構成の一例について説明するための図である。
【図５】図５（Ａ）（Ｂ）（Ｃ）は辺を共有する２枚のプリミティブの法線ベクトルについて説明するための図である。
【図６】本実施の形態の辺情報について説明するための図である。
【図７】所与のオブジェクトの光源にたいする輪郭を構成するエッジについて説明するための図である。
【図８】本実施の形態のシャドーボリューム生成処理の一例について説明するための図である。
【図９】図９（Ａ）（Ｂ）（Ｃ）はトライアングルストリップ及びトライアングルファンを用いてシャドーボリュームを生成する処理について説明するための図である。
【図１０】第１の実施形態のエッジ検出処理について説明するためのフローチャート図である。
【図１１】図１０に続いて、第１の実施形態のエッジ検出処理について説明するためのフローチャート図である。
【図１２】所与のオブジェクトを視点から見た場合の輪郭を構成するエッジについて説明するための図である。
【図１３】第２の実施形態のエッジ検出処理について説明するためのフローチャート図である。
【図１４】図１３に続いて第２の実施形態のエッジ検出処理について説明するためのフローチャート図である。
【図１５】本実施形態を実現できるハードウェアの構成の一例を示す図である。
【図１６】図１６（Ａ）、（Ｂ）、（Ｃ）は、本実施形態が適用される種々の形態のシステムの例を示す図である。
【符号の説明】
１０    画像生成システム
１００  処理部
１１０  ゲーム処理部
１２０  エッジ検出処理部
１２２  シャドーボリューム生成処理部
１３０  画像生成部
１５０  音生成部
１６０  操作部
１７０  記憶部
１７２  メインメモリ
１７４  フレームバッファ
１８０  情報記憶媒体
１９０  表示部
１９２  音出力部
１９４  携帯型情報記憶装置
１９６  通信部
【図１】
2004341571.tif 000003
【図２】
2004341571.tif 000004
【図３】
2004341571.tif 000005
【図４】
2004341571.tif 000006
【図５】
2004341571.tif 000007
【図６】
2004341571.tif 000008
【図７】
2004341571.tif 000009
【図８】
2004341571.tif 000010
【図９】
2004341571.tif 000011
【図１０】
2004341571.tif 000012
【図１１】
2004341571.tif 000013
【図１２】
2004341571.tif 000014
【図１３】
2004341571.tif 000015
【図１４】
2004341571.tif 000016
【図１５】
2004341571.tif 000017
【図１６】
2004341571.tif 000018