(57)【特許請求の範囲】
【請求項１】
少なくとも一つの３次元図形を含んで構成される画像から、この画像内における所定の点と特定の位置関係にある３次元図形を検出する装置において実行される方法であって、
前記３次元図形に、当該３次元図形を識別するための識別情報を付す第１の段階と、
前記３次元図形を互いに異なる複数レベルの拡大率又は縮小率のいずれかで所定の平面上に複数回射影することにより形成される複数の２次元射影像に当該３次元図形に付された識別情報に対応した識別情報を付す第２の段階と、
前記２次元射影像内に前記所定の点の射影点がある場合にその２次元射影像に付された識別情報を検出し、検出した識別情報に対応した識別情報が付された３次元図形を検出する第３の段階と、を含む、
図形検出方法。
【請求項２】
少なくとも一つの３次元図形を含んで構成される画像から、この画像内における所定の点と特定の位置関係にある３次元図形を検出する装置において実行される方法であって、
前記３次元図形に、当該３次元図形を識別するための識別情報を付す第１の段階と、
前記３次元図形を所定の平面上に互いに異なる複数レベルの拡大率又は縮小率で同時に拡大又は縮小射影することにより形成される複数の２次元射影像に当該３次元図形に付された識別情報に対応した識別情報を付す第２の段階と、
前記２次元射影像内に前記所定の点の射影点がある場合にその２次元射影像に付された識別情報を検出し、検出した識別情報に対応した識別情報が付された３次元図形を検出する第３の段階と、を含む、
図形検出方法。
【請求項３】
前記複数の２次元射影像の各々に、前記拡大率又は縮小率のレベルに変化に追随して変化する識別情報を付する、
請求項１又は２記載の図形検出方法。
【請求項４】
前記拡大率又は縮小率の変化方向とそれに追随する前記識別情報の変化方向とを同一方向にする、
請求項３記載の図形検出方法。
【請求項５】
少なくとも一つの３次元図形を含んで構成される画像から、この画像内における所定の点と特定の位置関係にある３次元図形を検出する装置において実行される方法であって、
前記３次元図形に、当該３次元図形を識別するための識別情報を付す第１の段階と、
前記３次元図形を所定の平面上に射影することにより形成される２次元射影像に当該３次元図形に付された識別情報に対応した識別情報を付し、前記３次元図形に対応した１つの前記識別情報を検出するまで前記２次元射影像を拡大又は縮小させる第２の段階と、
前記２次元射影像内に前記所定の点の射影点がある場合にその２次元射影像に付された識別情報を検出し、検出した識別情報に対応した識別情報が付された３次元図形を検出する第３の段階と、を含む、
図形検出方法。
【請求項６】
前記識別情報に前記３次元図形のサイズに応じて変化する付加情報を含めておき、
前記２次元射影像を拡大又は縮小するときにその拡大率又は縮小率のレベルに応じて前記付加情報を変更し、変更した付加情報によって当該２次元射影像と前記射影点とがどの程度近いかを検出可能にする、
請求項５記載の図形検出方法。
【請求項７】
前記識別情報が、複数の桁の数値から成り、
複数の桁の少なくとも１桁の数値が３次元図形を識別するものであり、
残りの桁の少なくとも１桁の数値が前記付加情報である、
請求項３又は６記載の図形検出方法。
【請求項８】
前記識別情報が、前記３次元図形を一意に識別するための数値から成り、この数値を前記２次元射影像の拡大率又は縮小率のレベルに応じて段階的に変化させ、この数値に基づいて当該２次元射影像と前記射影点とがどの程度近いかを検出可能にする、
請求項５記載の図形検出方法。
【請求項９】
前記画像を前記平面上に射影したときに前記２次元射影像が形成されない領域に、どの３次元図形にも付されていない識別情報を付す段階をさらに含む、
請求項１、２または５記載の図形検出方法。
【請求項１０】
前記第２の段階において、前記３次元画像を複数の異なる平面上に射影してそれぞれ複数の２次元射影像を形成すると共に、各平面上の２次元射影像に、当該３次元図形に付された識別情報に対応する識別情報を付し、
前記第３の段階において、複数の前記２次元射影像内の各々に前記射影点がある場合に、その２次元射影像に付された識別情報を検出し、検出した識別情報に基づいて３次元図形を検出する、
請求項１、２または５記載の図形検出方法。
【請求項１１】
前記第３の段階において、前記複数の２次元射影像のすべてにおいて共通に検出された識別情報が付された３次元図形を検出する、
請求項１０記載の図形検出方法。
【請求項１２】
前記複数の２次元射影像のすべてにおいて、識別情報の数値が、それぞれに付された範囲内となる３次元図形を検出する、
請求項１０記載の図形検出方法。
【請求項１３】
３次元図形を含んで構成される画像から、この画像内における所定の点と特定の位置関係にある３次元図形を検出する装置であって、
前記３次元図形に、当該図形を識別するための識別情報を付す手段と、
個々の３次元図形を互いに異なる複数レベルの拡大率又は縮小率のいずれかで所定の平面上に複数回射影することにより形成される複数の２次元射影像に当該３次元図形に付された識別情報に対応する識別情報を付す描画手段と、
前記２次元射影像内に前記所定の点の射影点がある場合にその２次元射影像に付された識別情報を検出し、検出した識別情報に対応する識別情報が付された３次元図形を検出する検出手段とを含んで構成される、
図形検出装置。
【請求項１４】
３次元図形を含んで構成される画像から、この画像内における所定の点と特定の位置関係にある３次元図形を検出する装置であって、
前記３次元図形に、当該図形を識別するための識別情報を付す手段と、
個々の３次元図形を所定の平面上に互いに異なる複数レベルの拡大率又は縮小率で同時に拡大又は縮小射影することにより形成される複数の２次元射影像に当該３次元図形に付された識別情報に対応する識別情報を付す描画手段と、
前記２次元射影像内に前記所定の点の射影点がある場合にその２次元射影像に付された識別情報を検出し、検出した識別情報に対応する識別情報が付された３次元図形を検出する検出手段とを含んで構成される、
図形検出装置。
【請求項１５】
３次元図形を含んで構成される画像から、この画像内における所定の点と特定の位置関係にある３次元図形を検出する装置であって、
前記３次元図形に、当該図形を識別するための識別情報を付す手段と、
個々の３次元図形を所定の平面上に射影することにより形成される２次元射影像に当該３次元図形に付された識別情報に対応する識別情報を付し、前記３次元図形に対応した１つの前記識別情報を検出するまで前記２次元射影像を拡大又は縮小させる描画手段と、
前記２次元射影像内に前記所定の点の射影点がある場合にその２次元射影像に付された識別情報を検出し、検出した識別情報に対応する識別情報が付された３次元図形を検出する検出手段とを含んで構成される、
図形検出装置。
【請求項１６】
３次元図形を含んで構成される画像から、この画像内における所定の点と特定の位置関係にある３次元図形を検出する半導体デバイスであって、
前記３次元図形に、当該図形を識別するための識別情報を付す手段と、
個々の３次元図形を互いに異なる複数レベルの拡大率又は縮小率のいずれかで所定の平面上に複数回射影することにより形成される複数の２次元射影像に当該３次元図形に付された識別情報に対応する識別情報を付す手段と、
前記２次元射影像内に前記所定の点の射影点がある場合にその２次元射影像に付された識別情報を検出し、検出した識別情報に対応する識別情報が付された３次元図形を検出する手段と、を含んで構成される、
半導体デバイス。
【請求項１７】
３次元図形を含んで構成される画像から、この画像内における所定の点と特定の位置関係にある３次元図形を検出する半導体デバイスであって、
前記３次元図形に、当該図形を識別するための識別情報を付す手段と、
個々の３次元図形を所定の平面上に互いに異なる複数レベルの拡大率又は縮小率で同時に拡大又は縮小射影することにより形成される複数の２次元射影像に当該３次元図形に付された識別情報に対応する識別情報を付す手段と、
前記２次元射影像内に前記所定の点の射影点がある場合にその２次元射影像に付された識別情報を検出し、検出した識別情報に対応する識別情報が付された３次元図形を検出する手段と、を含んで構成される、
半導体デバイス。
【請求項１８】
３次元図形を含んで構成される画像から、この画像内における所定の点と特定の位置関係にある３次元図形を検出する半導体デバイスであって、
前記３次元図形に、当該図形を識別するための識別情報を付す手段と、
個々の３次元図形を所定の平面上に射影することにより形成される２次元射影像に当該３次元図形に付された識別情報に対応する識別情報を付し、前記３次元図形に対応した１つの前記識別情報を検出するまで前記２次元射影像を拡大又は縮小させる手段と、
前記２次元射影像内に前記所定の点の射影点がある場合にその２次元射影像に付された識別情報を検出し、検出した識別情報に対応する識別情報が付された３次元図形を検出する手段と、を含んで構成される、
半導体デバイス。
【請求項１９】
コンピュータを、３次元図形を含んで構成される画像から、この画像内における所定の点と特定の位置関係にある３次元図形を検出する図形検出装置として動作させるためのコンピュータプログラムであって、
前記図形検出装置が、
前記３次元図形に、当該図形を識別するための識別情報を付す処理、
個々の３次元図形を互いに異なる複数レベルの拡大率又は縮小率のいずれかで所定の平面上に複数回射影することにより形成される複数の２次元射影像に当該３次元図形に付された識別情報に対応する識別情報を付す処理、
前記２次元射影像内に前記所定の点の射影点がある場合にその２次元射影像に付された識別情報を検出し、検出した識別情報に対応する識別情報が付された３次元図形を検出する処理、を実行するものである、
コンピュータプログラム。
【請求項２０】
コンピュータを、３次元図形を含んで構成される画像から、この画像内における所定の点と特定の位置関係にある３次元図形を検出する図形検出装置として動作させるためのコンピュータプログラムであって、
前記図形検出装置が、
前記３次元図形に、当該図形を識別するための識別情報を付す処理、
個々の３次元図形を所定の平面上に互いに異なる複数レベルの拡大率又は縮小率で同時に拡大又は縮小射影することにより形成される複数の２次元射影像に当該３次元図形に付された識別情報に対応する識別情報を付す処理、
前記２次元射影像内に前記所定の点の射影点がある場合にその２次元射影像に付された識別情報を検出し、検出した識別情報に対応する識別情報が付された３次元図形を検出する処理、を実行するものである、
コンピュータプログラム。
【請求項２１】
コンピュータを、３次元図形を含んで構成される画像から、この画像内における所定の点と特定の位置関係にある３次元図形を検出する図形検出装置として動作させるためのコンピュータプログラムであって、
前記図形検出装置が、
前記３次元図形に、当該図形を識別するための識別情報を付す処理、
個々の３次元図形を所定の平面上に射影することにより形成される２次元射影像に当該３次元図形に付された識別情報に対応する識別情報を付し、前記３次元図形に対応した１つの前記識別情報を検出するまで前記２次元射影像を拡大又は縮小させる処理、
前記２次元射影像内に前記所定の点の射影点がある場合にその２次元射影像に付された識別情報を検出し、検出した識別情報に対応する識別情報が付された３次元図形を検出する処理、を実行するものである、
コンピュータプログラム。
【請求項２２】
請求項１９、２０または２１に記載されたコンピュータプログラムを記録してなる、コンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、３次元図形から構成される画像において、画像中の所定の点と特定の位置関係にある３次元図形を検出する技術に関する。
【０００２】
【従来の技術】
ビデオゲーム装置などのエンタテインメント装置では、画像処理能力の向上により、より現実に近いゲーム画像の提供が可能となっている。例えば、３次元空間内で、物体やキャラクタが動きまわるような画像を表示することにより、遊戯者に、より高い臨場感を与え、ゲーム世界へ誘うようなビデオゲームは多数存在する。
【０００３】
このようなビデオゲームには、いろいろな物体で構成された３次元画像内を、人物や自動車などの、遊戯者により操作可能なキャラクタが移動して、物体に対して何らかの影響を与えるというものがある。例えば、自動車レースのゲームにおいて走行中の自動車（キャラクタ）が路上の石（物体）を跳ね飛ばしたり、人物（キャラクタ）が近くにある物体を持ち上げたり、などである。
キャラクタが、３次元画像内の物体に影響を与えることが可能となる条件として、キャラクタと物体との位置関係を用いるものがある。キャラクタと物体とが特定の位置関係になったときのみ、キャラクタが物体に影響を与えることが可能となる。
キャラクタと物体との特定の位置関係とは、例えば、Ｘ、Ｙ、Ｚ軸からなる直交座標系のＸＹ平面上に３次元画像を射影したときに、キャラクタの位置を示す点の射影点と物体の射影像（２次元射影像）とが重なりあうような位置関係（物体の上又は下にキャラクタが存する）であったり、複数の物体の中でＸＹ平面上への２次元射影像が上記射影点に最も近接するような位置関係（上空から見たときにキャラクタに最も近接する物体）などである。
【０００４】
【発明が解決しようとする課題】
画像を構成する、石や道路などの個々の物体を表す図形に関する情報は、テーブルによって管理される。
テーブルには、各図形の位置を表す位置座標、テクスチャ座標などの、図形を表示する上で必要となる情報が書き込まれており、位置座標等が変わる度に更新される。
このテーブルは、物体を作成した際の作成順で構成されており、画像内における図形の位置を表す位置座標によるソートは行われていない。例えば、テーブルは、Ｘ座標に基づいてソートした順に、図形を管理するようにはなっていない。前述のように、キャラクタが物体に影響を与えるためには、キャラクタと物体とが特定の位置関係にあるか否かを調査しなければならない。そのためには、テーブル全体をスキャンして各物体を表す図形とキャラクタとの位置関係を調査する必要がある。例えば、自動車レースのゲームで、自動車の下に物体があるかどうかを調べるには、自動車の位置座標とテーブルに記録されたすべての図形の位置座標とから、自動車と各物体とについての位置関係を調べなければならない。
【０００５】
テーブル全体のスキャンは、非常に時間がかかる処理である。これを高速化する方策として、前もって図形を位置座標についてソートすることが考えられるが、ソートした結果のテーブルと当初からのテーブルの２種類のテーブルを保持しなければならなくなり、メモリ領域を余計に使用することになる。また、画像をゲームの進行に合わせてリアルタイムに生成するようなものの場合、ソートをリアルタイムで行わなければならなくなり処理速度が低下する要因となる。
さらに、従来のキャラクタと物体との位置関係の調査は、それぞれの形状を決める点（頂点等）を用いて行われる。そのために、物体の形状によっては、特定される図形が所望の位置関係にはない場合がある。例えば、キャラクタに最も近接する物体を検出したいときに、頂点間の距離の比較では、最も近接しているとされた図形が、輪郭線まで考慮した比較を行うと、実際は、それより更に近接する位置に他の図形がある場合がある。
【０００６】
本発明の課題は、ハードウェア資源を無駄に使用することなく、また処理速度の低下を招かずに３次元画像内の特定の点、例えばキャラクタの位置を表す点と特定の位置関係にある物体を示す図形を検出する技術を提供することにある。
本発明の他の課題は、物体の形状によらず、３次元画像内の所定の点と特定の位置関係にある物体を示す図形を検出する技術を提供することにある。
【０００７】
【課題を解決するための手段】
本発明では、汎用のコンピュータやビデオゲーム装置等のエンタテインメント装置によって具現化される画像処理装置に標準的に備わる、３次元画像を所定の方向から射影して２次元画像（２次元射影像）を形成する機能を利用し、３次元画像内の所定の点と物体を表す図形との２次元射影像における位置関係から物体の図形を検出する具体的な仕組みを提案する。より具体的には、図形検出方法、図形検出装置、半導体デバイス、及びコンピュータプログラムを提供する。
【０００８】
本発明の図形検出方法は、３次元図形を含んで構成される画像から、この画像内における所定の点と特定の位置関係にある３次元図形を検出する装置において実行される方法であって、前記３次元図形に、当該３次元図形を識別するための識別情報を付す第１の段階と、個々の３次元図形を所定の平面上に射影することにより形成される２次元射影像に当該３次元図形に付された識別情報に対応する識別情報を付す第２の段階と、前記２次元射影像内に前記所定の点の射影点がある場合にその２次元射影像に付された識別情報を検出し、検出した識別情報に対応する識別情報が付された３次元図形を検出する第３の段階と、を含む。
【０００９】
所定の点は、例えばキャラクタや物体の位置を示す点である。これにより、２次元射影像の内部に射影点を含むような位置関係にある図形を検出可能となる。
前述のように、従来の画像処理装置に備わっている機能を利用して３次元図形から２次元射影像を生成するために、ハードウェア資源を余計に使うことなく図形の検出が可能となる。２次元射影像から識別情報を検出し、検出した識別情報を持つ３次元図形を検出するので、３次元図形の数に影響されることなく、速やかな図形の検出が可能である。２次元射影像に識別情報を付すために、２次元射影像の形状をも考慮に入れて、所定の点と特定の位置関係にある３次元図形を検出可能となる。
【００１０】
３次元図形を所定の平面に射影して２次元射影像を形成する際には、次の２形態のいずれかを選ぶことができる。
（１）３次元図形又は２次元射影像を拡大又は縮小せず、両者の各々を識別するための識別情報も同じものを付す。
（２）３次元図形を互いに異なる複数レベルの拡大率又は縮小率で拡大又は縮小して射影することにより形成された２次元射影像を複数重ねてグラディエーションを形成し、それぞれの２次元射影像に付すべき識別情報として、拡大率又は縮小率のレベルに応じて異なる識別情報を付す。この場合の射影は、正射影（３次元図形を拡大又は縮小する）であっても透視射影（３次元図形はそのままで射影の倍率を変える）であってもよい。
また、拡大又は縮小を徐々に行いながらグラディエーションを形成してもよく、最初から一気にグラディエーションを形成してもよい。前者は、２次元射影像についての処理時間については余裕はあるが、処理のために２次元射影像を描画するフィールド（画像メモリ等）に余裕がない場合に適した処理方法である。後者の場合は、その逆となる。グラディエーションの幅は、狭くその数が多いほど、きめ細かな表現が可能になる。
３次元図形を拡大又は縮小するときに、拡大率又は縮小率に応じてそれに付する識別情報を段階的に変化させるようにしてもよい。また、前記識別情報の変化を拡大率又は縮小率の変化に追随させ、識別情報の変化方向と拡大率又は縮小率の変化方向とを同一方向にする。この方法は、コンピュータグラフィクスを行う装置に標準的に備わるスムーズシェーディング機能を使うことで、容易に実現することができる。
また、１つの識別情報が検出されるまで２次元射影像を拡大又は縮小させるようにしてもよい。２次元射影像を拡大させることにより、射影点に、最も近接する２次元射影像を検出できるようになる。また、２次元射影像を縮小することにより、射影点に、最も中心に近い位置にある２次元射影像を検出できるようになる。
上記の（２）の方法では、前記識別情報に、その３次元図形のサイズに応じて変化する付加情報を含ませておき、前記２次元射影像を拡大又は縮小するときにその程度に応じて前記付加情報を変更し、変更した付加情報によって当該２次元射影像と前記射影点とがどの程度近いかを検出するようにする。この場合、例えば、前記識別情報を、複数の桁の数値で表しておき、複数の桁の少なくとも１桁の数値が３次元図形を識別するようにし、残りの桁の少なくとも１桁の数値が前記付加情報とすると、付加情報が変化しても、３次元図形を検出可能となる。
あるいは、３次元図形を一意に識別するための数値で前記識別情報を表し、この数値を２次元射影像の拡大率又は縮小率のレベルに応じて段階的に変化させ、この数値に基づいて当該２次元射影像と前記射影点とがどの程度近いかを検出可能にするようにしてもよい。
前記画像を前記平面上に射影したときに前記２次元射影像が形成されない領域に、どの３次元図形にも付されていない識別情報を付すようにしてもよい。このようにすると、例えば、検出した識別情報により３次元図形が射影されていない領域か否かが速やかに判断可能となる。
【００１１】
２次元射影像を複数形成して３次元図形を決めるようにしてもよい。例えば、前記第２の段階において、前記３次元画像を複数の異なる平面上に射影してそれぞれ複数の２次元射影像を形成すると共に、各平面上の２次元射影像に、当該３次元図形に付された識別情報に対応する識別情報を付し、前記第３の段階において、複数の前記２次元射影像内の各々に前記射影点がある場合に、その２次元射影像に付された識別情報を検出し、検出した識別情報に基づいて３次元図形を検出する。
このような方法では、例えば、前記第３の段階において、前記複数の２次元射影像のすべてにおいて共通に検出された識別情報が付された３次元図形を検出するようにし、あるいは、それぞれに与えられた範囲内の数値の３次元図形を検出するようにすると、３次元画像内の所定の点を内包する位置にある３次元図形の検出が容易になる。
【００１２】
本発明の図形検出装置は、３次元図形を含んで構成される画像から、この画像内における所定の点と特定の位置関係にある３次元図形を検出する装置であって、前記３次元図形に、当該図形を識別するための識別情報を付す手段と、個々の３次元図形を所定の平面上に射影することにより形成される２次元射影像に当該３次元図形に付された識別情報に対応する識別情報を付す描画手段と、前記２次元射影像内に前記所定の点の射影点がある場合にその２次元射影像に付された識別情報を検出し、検出した識別情報に対応する識別情報が付された３次元図形を検出する検出手段と、を含んで構成される図形検出装置である。
【００１３】
本発明の半導体デバイスは、３次元図形を含んで構成される画像から、この画像内における所定の点と特定の位置関係にある３次元図形を検出する半導体デバイスであって、前記３次元図形に、当該図形を識別するための識別情報を付す手段と、個々の３次元図形を所定の平面上に射影することにより系壊死される２次元射影像に当該３次元図形に付された識別情報に対応する識別情報を付す手段と、前記２次元射影像内に前記所定の点の射影点がある場合にその２次元射影像に付された識別情報を検出し、検出した識別情報に対応する識別情報が付された３次元図形を検出する手段と、を含んで構成される、半導体デバイスである。
【００１４】
また、本発明のコンピュータプログラムは、コンピュータを、３次元図形を含んで構成される画像から、この画像内における所定の点と特定の位置関係にある３次元図形を検出する図形検出装置として動作させるためのコンピュータプログラムである。図形検出装置は、前記３次元図形に、当該図形を識別するための識別情報を付す処理、個々の３次元図形を所定の平面上に射影することにより形成される２次元射影像に当該３次元図形に付された識別情報と同様の識別情報を付す処理、前記２次元射影像内に前記所定の点の射影点がある場合にその２次元射影像に付された識別情報を検出し、検出した識別情報に対応する識別情報が付された３次元図形を検出する処理、を実行するものである。
【００１５】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態を説明する。
＜エンタテインメント装置＞
図１は、本発明が適用されるエンタテインメント装置の内部構成図である。
エンタテインメント装置１は、ＣＰＵ（Central Processing Unit）１０と、ＲＡＭで構成されるメインメモリ１１と、ＤＭＡＣ（Direct Memory Access Controller）１２と、ＭＰＥＧ（Moving Picture Experts Group）デコーダ（ＭＤＥＣ）１３と、ＣＤ−ＲＯＭ又はＤＶＤ−ＲＯＭなどのメディア１５を装着するためのメディアドライブ１４と、入力部１６と、ＢＩＯＳなどのプログラムが記憶されているＲＯＭ１８と、サウンドメモリ２２に蓄積された音データを読み出してオーディオ出力として出力する音声処理装置（ＳＰＵ（Sound Processing Unit））２１と、フレームメモリ３２を有する描画処理装置（Graphic Processing Unit、以下、「ＧＰＵ」）３１と、を含んで構成される。これらは、バスＢを介して接続されている。
ＧＰＵ３１には、ビデオ出力信号を生成するＣＲＴＣ（CRT controller）３３が接続されている。このビデオ出力信号は、ＮＴＳＣ又はＰＡＬなどの規格に準拠して生成され、ＣＲＴＣ３３から図示しないディスプレイに出力されるようになっている。
【００１６】
ＣＰＵ１０は、エンタテインメント装置１の起動時に、ＲＯＭ１８から起動プログラムを読み込み、その起動プログラムを実行してオペレーティングシステムを動作させる半導体デバイスである。ＣＰＵ１０は、また、メディアドライブ１４を制御するとともに、このメディアドライブ１４に装着されたメディア１５からアプリケーションプログラムやデータを読み出し、これをメインメモリ１１に記憶させる機能を有する。さらに、メディア１５から読み出した各種データ、例えば複数の基本図形（ポリゴン）で構成された３次元図形データ（ポリゴンの頂点の座標値など）に対して、ジオメトリ処理（座標値演算処理）を行い、ジオメトリ処理によるポリゴン定義情報（使用するポリゴンの形状及びその形成位置、ポリゴンを構成する素材の種類、色、質感等の指定）をその内容とするディスプレイリストを生成する機能も有している。
【００１７】
ＧＰＵ３１は、描画コンテクスト（描画用のポリゴン素材の種類、色、質感、サイズ等）を保持し、ＣＰＵ１０から通知されるディスプレイリストに従って必要な描画コンテクストを読み出してレンダリング処理（描画処理）を行い、フレームメモリ３２にポリゴンを描画する機能を有する半導体デバイスである。フレームメモリ３２は、これをテクスチャメモリとしても使用できる。そのため、フレームメモリ３２上のピクセルイメージをテクスチャとして、描画するポリゴンに貼り付けることができる。
【００１８】
ＳＰＵ２１は、サウンドメモリ２２から読み出した音データを合成してオーディオ出力信号を生成する半導体デバイスである。ＤＭＡＣ１２は、バスＢに接続されている各回路を対象としてＤＭＡ転送制御を行う半導体デバイスであり、ＭＤＥＣ１３は、ＣＰＵ１０と並列に動作し、ＭＰＥＧ（Moving Picture Experts Group）方式あるいはＪＰＥＧ（Joint Photographic Experts Group）方式等で圧縮されたデータを伸張する機能を有する半導体デバイスである。
【００１９】
入力部１６は、操作装置２３からの入力信号が入力される接続端子１９を備えるものである。操作装置２３には、複数の操作ボタンが設けられており、遊戯者がこれらの操作ボタンを種々多様に操作することにより、画像や出力音が制御される。操作ボタンの操作により画像内のキャラクタが操作される。
【００２０】
＜図形検出装置の構成＞
以上のようなエンタテインメント装置１を本発明の図形検出装置として動作させる場合の構成例について説明する。
図形検出装置は、エンタテインメント装置１のＣＰＵ１０及びＧＰＵ３１が、ＲＯＭ１８、メディア１５その他の記録媒体に記録されている所定のコンピュータプログラムを読み込んで実行することにより実現される。
図２は、図形検出装置として動作するときのエンタテインメント装置１の機能構成図である。この実施形態では、ＣＰＵ１０とコンピュータプログラムとにより、画像制御部１０２、図形検出部１０４の機能ブロック（モジュール）をＣＰＵ１０内に形成するとともに、ＣＰＵ１０内の図示しないメモリ領域に、図形記憶部１０１を形成する。
また、ＧＰＵ３１とコンピュータプログラムとにより、ＧＰＵ３１内に描画部１０３の機能ブロック（モジュール）を形成する。
これらの各機能ブロックにより、物体を表す３次元図形により構成される３次元画像を生成する。３次元図形には、当該図形を識別するためのインデックス情報（識別情報）が付される。３次元図形を所定の平面に射影して得られる２次元射影像には、当該３次元図形に付されたインデックス情報と同じインデックス情報が付される。３次元画像内の所定の点の射影点を含む位置にある２次元射影像のインデックス情報を検出して、検出したインデックス情報と同じインデックス情報が付された３次元図形を検出する。
【００２１】
図形記憶部１０１は、３次元画像を構成する物体を表す３次元図形についての３次元図形データを保持するものである。図形記憶部１０１は、３次元図形データをテーブルとして保持する。３次元図形データには、図形の個々を識別するための識別情報としてのインデックス情報、図形の３次元空間内における位置を示す位置座標、テクスチャ座標などが含まれる。位置座標、テクスチャ座標などは、ジオメトリ処理の結果に応じて更新される。
図３は、３次元図形データについてのテーブルの例示図である。このテーブルには、図形毎に、図形名、インデックス情報、図形の位置座標、テクスチャ座標などが記録される。インデックス情報により、３次元図形を特定可能となる。
【００２２】
画像制御部１０２は、図形記憶部１０１から必要な３次元図形データを読み出して、ジオメトリ処理等の必要な処理を行い、２次元画像データを生成する。２次元画像データは、エンタテインメント装置１との関係ではディスプレイリストに相当する。生成された２次元画像データは、描画部１０３へ送られる。
本発明では、２次元画像データが２種類用意されている。
ピクセル毎に、輝度や明度、色などのディスプレイに表示される画像を形成するための表示用画像データと、ピクセル毎のインデックス情報を示しており３次元図形を検出するための画像を形成するためのインデックス用画像データとである。
表示用画像データ及びインデックス用画像データにより形成される２つの画像は、必ずしも、同じ３次元画像を同じ方向から見たものとは限らない。例えば、表示用画像データによる画像（表示用画像）を、３次元画像を水平方向から見た画像とし、インデックス用画像データによる画像（インデックス用画像）を、３次元画像を垂直方向から見た画像としてもよい。
画像制御部１０２は、図形検出部１０４からの指示により、２次元射影像の拡大、縮小を行う。拡大、縮小は、以下の２形態のいずれかの方法によって行うことができる。
第１の形態は、３次元図形からインデックス用画像データを作成する際、拡大率又は縮小率の異なる複数のインデックス用画像データを同時（同時とみなされる時間内を含む）に作成する。また、その３次元図形を識別するためのインデックス情報のほかに、その３次元図形の２次元射影像の拡大率又は縮小率に応じて異なる値となる付加情報を作成し、この付加情報をインデックス用画像データと共に描画部１０３に送出する。
第２の形態は、３次元図形からインデックス用画像データを作成する際、拡大又は縮小された２元射影像の中心からの距離に応じて付加情報を更新し、さらに、描画モードをスムーズシェーディングにするよう描画部１０３に指示した後、インデックス用画像データ等を送出する。
なお、拡大又は縮小されたときにインデックス用画像データが変化しても、それに対応する３次元図形のインデックス情報が明確である場合は、上記の付加情報は不要となる。
【００２３】
描画部１０３は、２次元画像データの入力を契機に、フレームメモリ３２に２次元画像データに基づいた画像を描画する。
表示用画像データと、インデックス用画像データとが、同じ３次元画像を同じ方向から見た画像となっている場合には、フレームメモリ３２の同じ領域に描画するようにしてもよいが、異なる方向から見た画像となっている場合には、フレームメモリ３２の異なる領域に描画されることとなる。表示用画像データによる表示用画像は、ＣＲＴＣ３３によりビデオ出力信号に変換されて出力される。インデックス用画像データによるインデックス用画像は、図形検出用に用いられる。
インデックス用画像内の、３次元図形を射影した２次元射影像には、該当する３次元図形に付されているインデックス情報が付される。なお、２次元射影像が描画されない領域には、どの３次元図形にも付されていないインデックス情報を付すようにしてもよい。
描画部１０３は、１ピクセルに２以上のインデックス情報を書き込む必要がある場合（２以上の２次元射影像が同じピクセル上に描画されるとき）には、１ピクセル分のデータが書き込まれるメモリ領域を分割して、書き込む必要のあるすべてのインデックス情報を書き込む。
【００２４】
図形検出部１０４は、フレームメモリ３２上に描画されたインデックス用画像内の、３次元画像内の所定の点の射影点のインデックス情報を検出する。所定の点とは、例えば、キャラクタの位置を示す点である。検出したインデックス情報に対応するインデックス情報が付された３次元図形を、図形記憶部１０１が保持するテーブルから検出する。
また、検出したインデックス情報の個数が０の場合には、画像制御部１０２に対してインデックス用画像内の２次元射影像の拡大を指示し、検出したインデックス情報の個数が２以上の場合には、画像制御部１０２に対して２次元射影像の縮小を指示するようにして、インデックス情報を確実に１個検出するようにしてもよい。
【００２５】
＜図形検出装置の動作＞
以上のような構成のエンタテインメント装置１により、次のような手順で、３次元画像内の所定の点と特定の位置関係にある３次元図形を検出する。
図４は、図形検出の手順を示すフローチャートである。
画像制御部１０２は、メディア１５から、３次元画像を構成する３次元図形を表す３次元図形データを読み出す（ステップＳ１０１）。そして、読み出した３次元図形データにより表される３次元図形の各々に異なるインデックス情報を付して、テーブルを作成する（ステップＳ１０２）。作成したテーブルは、図形記録部１０１に保管される。また画像制御部１０２は、３次元図形データに座標変換、透視変換、ライティングなどのジオメトリ処理を施して表示用画像データを生成する（ステップＳ１０３）。これにより、その時点における３次元画像が生成される。生成された表示用画像データは、描画部１０３へ送られる。
【００２６】
描画部１０３は、送られてきた表示用画像データに基づいてフレームメモリ３２上に表示用画像を形成する（ステップＳ１０４）。フレームメモリ３２上への描画の際には、１ピクセルのデータを表す領域に、当該ピクセルの輝度や明度、色などの情報を書き込む。
また、画像制御部１０２は、ステップＳ１０３で生成された３次元画像から、インデックス用画像データを生成する（ステップＳ１０５）。インデックス用画像データも描画部１０３へ送られて、フレームメモリ３２上の所定の領域にインデックス用画像が描画される（ステップＳ１０６）。このようにして、インデックス用画像内の２次元射影像に、該当する３次元図形に付されたインデックス情報と同じインデックス情報が付された画像が得られる。１つのピクセルに射影される３次元図形が複数ある場合には、該当する３次元図形のすべてのインデックス情報が書き込まれる。
インデックス情報が書き込まれない領域、つまり２次元射影像がない領域には、いずれの３次元図形にも付されていないインデックス情報が付される。
【００２７】
図７は、インデックス用画像データによる画像の例を示す図である。図７では、立方体、三角錐、球を表す３つの３次元図形に、それぞれインデックス情報「１」、「２」、「３」が付されており、その２次元射影像である正方形、三角形、円に、それぞれインデックス情報「１」、「２」、「３」が付されている。また、２次元射影像が形成されない領域には、インデックス情報として「０」が付されている。
【００２８】
フレームメモリ３２へのインデックス用画像の描画が終了すると、図形検出部１０４は、３次元画像内の所定の点を射影したときの点である射影点Ｐのインデックス情報を検出する（ステップＳ１０７）。３次元画像内の所定の点は、例えば３次元画像内でキャラクタが存在する点である。所定の点がキャラクタが存在する点である場合には、キャラクタの２次元射影像と物体の２次元射影像との位置関係を知ることができる。図形検出部１０４は、フレームメモリ３２上の、射影点にあたるメモリ領域に書き込まれたインデックス情報を検出する。図７では、射影点Ｐのインデックス情報として「１」が検出される。
【００２９】
図形検出部１０４は、検出したインデックス情報が「０」か否かを確認して（ステップＳ１０８）、インデックス情報が「０」のときは（ステップＳ１０８：Y）、そのまま図形の検出動作を終了する。インデックス情報「０」は、射影点がいずれの２次元射影像とも重なっていないことを示すからである。インデックス情報が「０」でないときは（ステップＳ１０８：N）、図形記憶部１０１が保持するテーブルから、検出したインデックス情報と同じインデックス情報が付された３次元図形データを検出する（ステップＳ１０９）。検出した３次元図形データにより、３次元図形を特定できる。特定した３次元図形が、３次元画像内の所定の点と特定の位置関係にある図形となる。
【００３０】
フレームメモリ３２上へ、３次元図形を射影して得られる２次元射影像を描画することは、従来のビデオゲーム装置などによる画像処理装置に備わる機能である。本発明では、この機能を用いて、インデックス情報をフレームメモリ３２上へ描画して、２次元射影点に対応するメモリ領域に書き込まれたインデックス情報を検出するだけで、所定の点を２次元射影像内に含む位置にある３次元図形を検出できる。そのために、余分なリソースを使わずに、短時間で所定の点と特定の位置関係にある３次元図形を検出することが可能となる。また、検出した３次元図形が複数あるときに、この中から所定の点に最も近い３次元図形を１つだけ選択する場合は、検出した３次元図形の座標値と所定の点の座標値との距離を測定することになるが、３次元画像内にあるすべての３次元図形に対して距離を測定する必要があった従来の方法に比べて、距離を測定する対象となる３次元図形の数が格段に少なくなることから、処理時間を大幅に短縮できる。
【００３１】
また、２次元射影像を拡大又は縮小したものを複数個重ねて描画する場合、あるいは、２次元射影像を拡大又は縮小させていく場合において、各々の２次元射影像に付加情報が付されている場合には、それを必要に応じて更新する。後者の場合には、付加情報を段階的に変化させるようにする。なお、付加情報が付されていない場合は、２次元射影像に付されているインデックス情報を変化させるようにする。このような処理は、上記のスムーズシェーディング機能を使うことにより実現できる。
これにより、所要の図形を容易に検出できるようになる。
【００３２】
図９は、２次元射影像を拡大したときに、付加情報を変更させる場合の例示図である。元の２次元射影像は、実線で囲まれる矩形及び円形であり、各々にインデックス情報として「1.0」と「2.0」が付されている。なお、１の位の数字が３次元図形を検出するための情報を表し、小数点以下の数字が付加情報を表す。例えば、１の位の数字が「１」のときは、インデックス情報が「１」の図形が検出される。
【００３３】
２次元射影像をそれぞれを２倍、４倍、６倍に拡大して、例えば矩形の２次元射影像の拡大像のインデックス情報をそれぞれ「1.2」、「1.4」、「1.6」とし、円形の２次元射影像の拡大像のインデックス情報をそれぞれ「2.2」、「2.4」、「2.6」とする。インデックス情報は、矩形の場合、実線と破線の間が「1.2」、破線と一点破線の間が「1.4」、一点破線と二点破線の間が「1.6」の領域となる。円形の場合、実線と破線の間が「2.2」、破線と一点破線の間が「2.4」、一点破線と二点破線の間が「2.6」の領域となる。
【００３４】
図９では、射影点Ｐが矩形の２次元射影像のインデックス情報「1.4」の領域、円形の２次元射影像のインデックス情報「2.6」の領域にあるために、射影点Ｐは、円形の２次元射影像より、矩形の２次元射影像の方に近い位置にあることがわかる。また、インデックス情報を拡大率に応じて変更しているので、どの程度の近さにあるかがわかる。例えば、矩形との距離で言えば、元の矩形を２倍〜４倍に拡大したときの範囲にあることが、インデックス情報「1.4」を検出することにより容易にわかる。この拡大率をさらに細かくしていき、それぞれに異なるインデックス情報を付して描画することにより、さらに細かく２次元射影像と射影点Ｐの距離がわかるようになる。
【００３５】
図５は、検出される３次元図形が１個になるようにする過程を示すフローチャートである。ここでは、図４に示す図形の検出過程に、検出されるインデックス情報が１個になるような処理が追加される。
この３次元図形の検出処理では、ステップＳ１０１〜Ｓ１０７までは図４と同じ処理手順であるので、この間の説明は省略する。この処理の説明を、図５のステップＳ２０８から行う。
なお、この処理では、インデックス用画像の３次元図形が射影されていない領域には、インデックス情報が付されていないとする。
【００３６】
図形検出部１０４は、ステップＳ１０７でインデックス情報を検出すると、検出したインデックス情報の個数が１個か否かを確認する（ステップＳ２０８）。インデックス情報の個数が１個でないときは（ステップＳ２０８：N）、検出したインデックス情報の個数が０個か否かを確認する（ステップＳ２０９）。インデックス情報の個数が０個のときは（ステップＳ２０９：Y）、画像制御部１０２へ、各２次元射影像を拡大する旨の指示を送る（ステップＳ２１０）。インデックス情報の個数が０個でないときは（ステップＳ２０９：N）、画像制御部１０２へ、フレームメモリ３２上に描画されている各２次元射影像を縮小する旨の指示を送る（ステップＳ２１１）。２次元射影像の拡大、縮小が指示されると、ステップＳ１０５に戻り、画像制御部１０２は、２次元射影像を指示通りに拡大、縮小したインデックス用画像データを生成する（ステップＳ１０５）。生成されたインデックス用画像データは、描画部１０３へ送られる。描画部１０３は、送られてきたインデックス用画像データからインデックス用画像を生成する（ステップＳ１０６）。生成されたインデックス用画像内の２次元射影像は、図形検出部１０４の指示通りに拡大、縮小されたものとなる。図形検出部１０４は、生成されたインデックス用画像から、再びインデックス情報の検出を行う（ステップＳ１０７）。
【００３７】
図８は、２次元射影像の拡大、縮小を説明する図である。図８（ａ）は、拡大する場合の例であり、ここでは各２次元射影像を１５０％に拡大する。１５０％拡大することにより、インデックス情報が描画されていなかった射影点Ｐにインデックス情報が描画されることになり、インデックス情報が検出される。
図８（ｂ）は、縮小する場合の例であり、ここでは各２次元射影像を５０％に縮小している。５０％縮小することにより、インデックス情報が３個検出されていた射影点Ｐにおいて、検出されるインデックス情報が１個になる。
２次元射影像の拡大、縮小は、検出されるインデックス情報の個数が１個になるまで繰り返し行われる。
【００３８】
インデックス情報の個数が１個であるときは（ステップＳ２０８：Y）、検出したインデックス情報と同じインデックス情報が付された３次元図形を検出する（ステップＳ２１２）。
【００３９】
２次元射影像を拡大、縮小して、検出するインデックス情報を１個にすることにより、射影点Ｐに２次元射影像が最も近接している３次元図形を検出可能となる。
【００４０】
図６は、３次元画像を複数の方向から射影して複数のインデックス用画像データを生成し、各インデックス用画像データから得られるインデックス用画像から、インデックス情報を検出する過程を示すフローチャートである。
この３次元図形の検出処理では、ステップＳ１０１〜Ｓ１０４までは図４と同じ処理手順であるので、この間の説明は省略する。この処理の説明を、図６のステップＳ３０５から行う。
【００４１】
画像制御部１０２は、３次元画像を複数の方向から射影して複数のインデックス用画像データを生成する（ステップＳ３０５）。
描画部１０３は、画像制御部１０２から送られる複数のインデックス用画像データに基づいてフレームメモリ３２上の複数領域に複数のインデックス用画像を形成する（ステップＳ３０６）。複数のインデックス用画像は、例えば、３次元画像をＸ、Ｙ、Ｚ座標軸による直交座標系のＸＹ平面、ＸＺ平面、ＹＺ平面に射影して得られた像である。図１０は、このようにして得られる３つのインデックス用画像の例を示す図である。
複数のインデックス用画像を形成すると、各インデックス用画像について射影点Ｐ１、Ｐ２、Ｐ３におけるインデックス情報を検出する（ステップＳ３０７）。各インデックス用画像から検出されるインデックス情報において、すべてのインデックス用画像で共通に検出されたインデックス情報があるか否か、あるいはそれが表す数値が与えられた範囲内となるインデックス情報があるか否かを確認する（ステップＳ３０８）。あることが確認されたときは（ステップＳ３０８：Y）、テーブルから、このインデックス情報が付された３次元図形を検出する（ステップＳ３０９）。すべてのインデックス用画像で共通に検出されたインデックス情報がないときは（ステップＳ３０８：N）、そのまま図形の検出動作を終了する。
【００４２】
図１０の例では、インデックス情報として「１」が付された直方体が、ＸＹ平面、ＸＺ平面、ＹＺ平面の各々に射影されている。点Ｐは、直方体に内包される位置にある。そのために、点Ｐの射影点Ｐ１、Ｐ２、Ｐ３で検出されるインデックス情報は、すべて「１」である。このようなときに、直方体を検出可能である。
なお、この例では、すべてのインデックス用画像で共通に検出されたインデックス情報が付された３次元図形を検出することとしているが、これには限らず、いずれか一つのインデックス用画像で検出されれば、その３次元図形を検出することとしてももちろんよい。
【００４３】
以上のような処理により、３次元画像内の所定の点を、内包する位置にある３次元図形を検出可能である。
また、各インデックス用画像において、２次元射影像を拡大、縮小することにより、どの３次元図形が最も近接した位置にあるかを検出することも可能である。
【００４４】
本実施形態では、エンタテインメント装置による例を説明したが、本発明は、エンタテインメント装置以外でも、画像処理機能を備えた汎用のコンピュータに、本発明にかかる記録媒体に記録されたプログラムコードを読み込ませて実行させて実現することも可能である。
【００４５】
【発明の効果】
以上のような本発明により、画像内の所定の点と特定の位置関係にある３次元図形を、ハードウェア資源を無駄に使用することなく、速やかに検出可能となる。また、図形の形状によらずに、画像内の所定の点の射影点に最も２次元射影像が近い３次元図形を検出することが可能となる。
【図面の簡単な説明】
【図１】本発明を適用したエンタテインメント装置の内部構成図である。
【図２】本発明に関する要部機能ブロック図である。
【図３】３次元図形データのテーブルの例示図である。
【図４】図形の検出手順を示すフローチャートである。
【図５】図形の検出手順を示すフローチャートである。
【図６】図形の検出手順を示すフローチャートである。
【図７】インデックス用画像の例示図である。
【図８】図８（ａ）は、インデックス用画像上の２次元射影像を拡大したときの例示図であり、図８（ｂ）は、インデックス用画像上の２次元射影像を縮小したときの例示図である。
【図９】拡大率に応じてインデックス情報を変化させた２次元射影像の例示図である。
【図１０】ＸＹ平面、ＸＺ平面、ＹＺ平面のそれぞれに３次元画像を射影したときの例示図である。
【符号の説明】
１      エンタテインメント装置
１０    ＣＰＵ
３１    ＧＰＵ
３２    フレームメモリ
１０１  図形記憶部
１０２  画像制御部
１０３  描画部
１０４  図形検出部
【図１】
0004673518.tif 000002
【図２】
0004673518.tif 000003
【図３】
0004673518.tif 000004
【図４】
0004673518.tif 000005
【図５】
0004673518.tif 000006
【図６】
0004673518.tif 000007
【図７】
0004673518.tif 000008
【図８】
0004673518.tif 000009
【図９】
0004673518.tif 000010
【図１０】
0004673518.tif 000011