(57)【特許請求の範囲】
【請求項１】
ゲーム装置を用いた仮想的な３次元ゲーム空間内のオブジェクト間のヒットチェック方法であって、
ゲーム装置が備える記憶手段に、あらかじめ基準座標系の上で複数のポリゴンから構成される基準オブジェクトの定義データを記憶し、
ゲーム装置が備える記憶手段に、前記基準座標系での前記基準オブジェクトの範囲を示す直方体を基準となる所定の大きさのブロックに分割した各ブロックに含まれる基準オブジェクトのポリゴンを記憶し、
ゲーム装置が備える処理手段が、前記基準座標系の上で定義した基準オブジェクトを座標変換して３次元ゲーム空間のワールド座標系に配置することにより、ワールド座標系上のオブジェクトを定義し、
ゲーム装置が備える処理手段が、ワールド座標系の上で第１のオブジェクトと前記基準オブジェクトから定義した第２のオブジェクトとの間でヒットチェックを行なう際、前記第１のオブジェクトの位置をワールド座標系から前記第２のオブジェクトの基準座標系へ逆変換することにより、前記第１のオブジェクトの前記基準座標系での位置を取得し、
ゲーム装置が備える処理手段が、取得した前記第１のオブジェクトの前記基準座標系での位置が、前記第２のオブジェクトに対応する基準オブジェクトの範囲を示す直方体を分割した複数のブロックのうち何れのブロックに属するかを判定し、
ゲーム装置が備える処理手段が、前記第１のオブジェクトの前記基準座標系での位置が、前記複数のブロックの何れにも属さないときは、前記第１のオブジェクトと前記第２のオブジェクトとはヒットしないと決定する
ことを特徴とするオブジェクト間のヒットチェック方法。
【請求項２】
請求項１に記載のヒットチェック方法において、
ゲーム装置が備える処理手段が、前記第１のオブジェクトの前記基準座標系での位置が前記複数のブロックの少なくとも１つに属したときに、そのブロックに含まれる前記基準オブジェクトのポリゴンに、前記第１のオブジェクトの前記基準座標系での位置がヒットするか否かを判定する処理を行うことを特徴とするオブジェクト間のヒットチェック方法。
【請求項３】
請求項２に記載のヒットチェック方法において、
ゲーム装置が備える処理手段が、前記基準オブジェクトのポリゴンに、前記第１のオブジェクトの前記基準座標系での位置がヒットするか否かを判定する際、前記第１のオブジェクトの前記基準座標系での位置が、あらかじめ前記基準オブジェクトのポリゴンに設定されている、そのポリゴンを内部に含むカリング球に含まれるか否かを判定し、該カリング球に含まれないときは、前記第１のオブジェクトと前記第２のオブジェクトとはヒットしないと決定するものであることを特徴とするオブジェクト間のヒットチェック方法。
【請求項４】
請求項３に記載のヒットチェック方法において、
前記ポリゴンに設定するカリング球は、そのポリゴンが３角形であるときは、その３角形の２番目に長い辺の１番長い辺に接しない頂点を中心とし、２番目に長い辺を半径とする球とすることを特徴とするオブジェクト間のヒットチェック方法。
【請求項５】
ゲーム処理中に仮想的な３次元ゲーム空間内のオブジェクト間のヒットチェック処理を実行するゲーム装置であって、
基準座標系の上で定義した基準オブジェクトを構成する複数のポリゴンの定義データを記憶する手段と、
前記基準座標系での前記基準オブジェクトの範囲を示す直方体を、基準となる所定の大きさのブロックに分割し、各ブロックに含まれる基準オブジェクトのポリゴンを記憶する手段と、
前記基準オブジェクトを特定する情報と、該基準オブジェクトを座標変換して３次元ゲーム空間のワールド座標系に配置しワールド座標系上のオブジェクトを定義する際の座標変換情報とを、対応させてマップ配置データとして記憶する手段と、
ワールド座標系の上で第１のオブジェクトと前記基準オブジェクトから定義した第２のオブジェクトとの間でヒットチェックを行なう際、前記第１のオブジェクトの位置をワールド座標系から前記第２のオブジェクトの基準座標系へ逆変換することにより、前記第１のオブジェクトの前記基準座標系での位置を取得する手段と、
取得した前記第１のオブジェクトの前記基準座標系での位置が、前記第２のオブジェクトに対応する基準オブジェクトの範囲を示す直方体を分割した複数のブロックのうち何れのブロックに属するかを判定する手段と、
前記第１のオブジェクトの前記基準座標系での位置が、前記複数のブロックの何れにも属さないときは、前記第１のオブジェクトと前記第２のオブジェクトとはヒットしないと決定する手段と
を備えたことを特徴とするゲーム装置。
【請求項６】
請求項５に記載のゲーム装置において、
前記第１のオブジェクトの前記基準座標系での位置が前記複数のブロックの少なくとも１つに属したとき、そのブロックに含まれる前記基準オブジェクトのポリゴンに、前記第１のオブジェクトの前記基準座標系での位置がヒットするか否かを判定する手段を、さらに備えたことを特徴とするゲーム装置。
【請求項７】
請求項６に記載のゲーム装置において、
あらかじめ各ポリゴンごとに、そのポリゴンを内部に含むカリング球を設定し、そのカリング球の中心と半径とを記憶しておく手段を、さらに備え、
前記ポリゴンに、前記第１のオブジェクトの前記基準座標系での位置がヒットするか否かを判定する手段は、前記第１のオブジェクトの前記基準座標系での位置が、前記ポリゴンに設定されているカリング球に含まれるか否かを判定し、該カリング球に含まれないときは、前記第１のオブジェクトと前記第２のオブジェクトとはヒットしないと決定するものであることを特徴とするゲーム装置。
【請求項８】
請求項７に記載のゲーム装置において、
前記ポリゴンに設定するカリング球は、そのポリゴンが３角形であるときは、その３角形の２番目に長い辺の１番長い辺に接しない頂点を中心とし、２番目に長い辺を半径とする球とすることを特徴とするゲーム装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、仮想的な３次元ゲーム空間内のオブジェクト間のヒットチェック方法および該方法を適用したゲーム装置に関する。
【０００２】
【従来の技術】
業務用や家庭用のゲーム機、あるいはパソコンのゲームなどでは、仮想３次元ゲーム空間内でオブジェクト間のヒットチェック処理が多く行なわれる。オブジェクトとは、ゲーム空間内に配置される各種の物を示し、静止しているか移動しているかを問わない。ヒットチェック処理とは、ゲーム空間（３次元の仮想的な空間）内のオブジェクト間で衝突するか否かをチェックする処理である。オブジェクトが幾つかのポリゴンデータから構成されるときは、各ポリゴンデータとヒットチェック処理を行なうことになる。
【０００３】
例えば、▲１▼仮想３次元ゲーム空間内に地面や建物や人物や木などのオブジェクトを配置した中でプレイヤキャラクタが動き回る場合に、該プレイヤキャラクタの一部分（例えば、腕や足などのヒットポイント、あるいはプレイヤが自動車やバイクをコントロールしている場合は接地するタイヤの下端部のヒットポイントなど）が他のオブジェクトのポリゴン（地面や建物や人物や木などのオブジェクトを構成するポリゴン）にあたったか否かを判定するとき、▲２▼シューティングゲームで、プレイヤキャラクタが発射した弾丸状のものが他のオブジェクトのポリゴンにあたったか否かを判定するとき、などにヒットチェック処理が行なわれる。さらに、３次元ゲーム空間内のキャラクタのオブジェクトの影を生成する場合に、仮想的な光源からの光線と地面や壁などのオブジェクトとの間でヒットチェック処理を行ない、ヒットした位置に基づいて影を作る、というようにヒットチェック処理を利用する場合もある。
【０００４】
ヒットチェック処理は、リアルタイムで正確に行なう必要があるが、３次元ゲーム空間内には多くのポリゴンからなる多くのオブジェクトが存在するため、ＣＰＵの演算負荷は大きくなる。そのため、演算負荷を少なくするために工夫したヒットチェック方法が考えられている。例えば、特開平１１−１７５７４７号公報には、固定オブジェクトを構成する各ポリゴンに外接し、オブジェクト空間を特定する座標軸の２軸に平行な外接四角形を表すポリゴン特定データと、移動オブジェクトの前記２軸の位置座標とに基づき、移動オブジェクトが属する外接四角形を特定し、特定された外接四角形に対応するポリゴンとの衝突演算（ヒットチェック）を行なう方法が開示されている。
【０００５】
【発明が解決しようとする課題】
上記特開平１１−１７５７４７号公報に記載の技術では、各オブジェクトはワールド座標系内で定義されている（すなわち、オブジェクトを構成するポリゴンの頂点などはワールド座標系の座標で持っている）ので、各オブジェクトを配置し直したりするためには、それらのデータそのものを変更し直さなければならず柔軟な対処ができないと言う不都合があった。例えば家や木などのオブジェクトは、ワールド座標系に貼り付いた形で定義されているので、その単位で配置し直したり変形したり移動させることは困難であった。さらに、ワールド座標系で定義しているのでオブジェクトの再利用が難しいという問題もあった。。
【０００６】
本発明は、上述の従来技術における問題点に鑑み、３次元ゲーム空間に配置するオブジェクトについて、オブジェクトを表すデータを再利用可能なデータ構造とし、かつそのようなデータ構造でもヒットチェック処理はリアルタイムで正確に行なうことができるようなオブジェクト間のヒットチェック方法および該方法を適用したゲーム装置を提供することを目的とする。
【０００８】
【課題を解決するための手段】
上記目的を達成するため、請求項１に係る発明は、ゲーム装置を用いた仮想的な３次元ゲーム空間内のオブジェクト間のヒットチェック方法であって、ゲーム装置が備える記憶手段に、あらかじめ基準座標系の上で複数のポリゴンから構成される基準オブジェクトの定義データを記憶し、ゲーム装置が備える記憶手段に、前記基準座標系での前記基準オブジェクトの範囲を示す直方体を基準となる所定の大きさのブロックに分割した各ブロックに含まれる基準オブジェクトのポリゴンを記憶し、ゲーム装置が備える処理手段が、前記基準座標系の上で定義した基準オブジェクトを座標変換して３次元ゲーム空間のワールド座標系に配置することにより、ワールド座標系上のオブジェクトを定義し、ゲーム装置が備える処理手段が、ワールド座標系の上で第１のオブジェクトと前記基準オブジェクトから定義した第２のオブジェクトとの間でヒットチェックを行なう際、前記第１のオブジェクトの位置をワールド座標系から前記第２のオブジェクトの基準座標系へ逆変換することにより、前記第１のオブジェクトの前記基準座標系での位置を取得し、ゲーム装置が備える処理手段が、取得した前記第１のオブジェクトの前記基準座標系での位置が、前記第２のオブジェクトに対応する基準オブジェクトの範囲を示す直方体を分割した複数のブロックのうち何れのブロックに属するかを判定し、ゲーム装置が備える処理手段が、前記第１のオブジェクトの前記基準座標系での位置が、前記複数のブロックの何れにも属さないときは、前記第１のオブジェクトと前記第２のオブジェクトとはヒットしないと決定することを特徴とする。
【０００９】
請求項２に係る発明は、請求項１に記載のヒットチェック方法において、ゲーム装置が備える処理手段が、前記第１のオブジェクトの前記基準座標系での位置が前記複数のブロックの少なくとも１つに属したときに、そのブロックに含まれる前記基準オブジェクトのポリゴンに、前記第１のオブジェクトの前記基準座標系での位置がヒットするか否かを判定する処理を行うことを特徴とする。
【００１０】
請求項３に係る発明は、請求項２に記載のヒットチェック方法において、ゲーム装置が備える処理手段が、前記基準オブジェクトのポリゴンに、前記第１のオブジェクトの前記基準座標系での位置がヒットするか否かを判定する際、前記第１のオブジェクトの前記基準座標系での位置が、あらかじめ前記基準オブジェクトのポリゴンに設定されている、そのポリゴンを内部に含むカリング球に含まれるか否かを判定し、該カリング球に含まれないときは、前記第１のオブジェクトと前記第２のオブジェクトとはヒットしないと決定するものであることを特徴とする。
【００１１】
請求項４に係る発明は、請求項３に記載のヒットチェック方法において、前記ポリゴンに設定するカリング球は、そのポリゴンが３角形であるときは、その３角形の２番目に長い辺の１番長い辺に接しない頂点を中心とし、２番目に長い辺を半径とする球とすることを特徴とする。
【００１３】
請求項５に係る発明は、ゲーム処理中に仮想的な３次元ゲーム空間内のオブジェクト間のヒットチェック処理を実行するゲーム装置であって、基準座標系の上で定義した基準オブジェクトを構成する複数のポリゴンの定義データを記憶する手段と、前記基準座標系での前記基準オブジェクトの範囲を示す直方体を、基準となる所定の大きさのブロックに分割し、各ブロックに含まれる基準オブジェクトのポリゴンを記憶する手段と、前記基準オブジェクトを特定する情報と、該基準オブジェクトを座標変換して３次元ゲーム空間のワールド座標系に配置しワールド座標系上のオブジェクトを定義する際の座標変換情報とを、対応させてマップ配置データとして記憶する手段と、ワールド座標系の上で第１のオブジェクトと前記基準オブジェクトから定義した第２のオブジェクトとの間でヒットチェックを行なう際、前記第１のオブジェクトの位置をワールド座標系から前記第２のオブジェクトの基準座標系へ逆変換することにより、前記第１のオブジェクトの前記基準座標系での位置を取得する手段と、取得した前記第１のオブジェクトの前記基準座標系での位置が、前記第２のオブジェクトに対応する基準オブジェクトの範囲を示す直方体を分割した複数のブロックのうち何れのブロックに属するかを判定する手段と、前記第１のオブジェクトの前記基準座標系での位置が、前記複数のブロックの何れにも属さないときは、前記第１のオブジェクトと前記第２のオブジェクトとはヒットしないと決定する手段とを備えたことを特徴とする。
【００１４】
請求項６に係る発明は、請求項５に記載のゲーム装置において、前記第１のオブジェクトの前記基準座標系での位置が前記複数のブロックの少なくとも１つに属したとき、そのブロックに含まれる前記基準オブジェクトのポリゴンに、前記第１のオブジェクトの前記基準座標系での位置がヒットするか否かを判定する手段を、さらに備えたことを特徴とする。
【００１５】
請求項７に係る発明は、請求項６に記載のゲーム装置において、あらかじめ各ポリゴンごとに、そのポリゴンを内部に含むカリング球を設定し、そのカリング球の中心と半径とを記憶しておく手段を、さらに備え、前記ポリゴンに、前記第１のオブジェクトの前記基準座標系での位置がヒットするか否かを判定する手段は、前記第１のオブジェクトの前記基準座標系での位置が、前記ポリゴンに設定されているカリング球に含まれるか否かを判定し、該カリング球に含まれないときは、前記第１のオブジェクトと前記第２のオブジェクトとはヒットしないと決定するものであることを特徴とする。
【００１６】
請求項８に係る発明は、請求項７に記載のゲーム装置において、前記ポリゴンに設定するカリング球は、そのポリゴンが３角形であるときは、その３角形の２番目に長い辺の１番長い辺に接しない頂点を中心とし、２番目に長い辺を半径とする球とすることを特徴とする。
【００１７】
【発明の実施の形態】
以下、図面を用いて本発明の実施の形態を説明する。
【００１８】
図１は、本発明に係るヒットチェック方法を適用したゲーム機の構成例を示す。このゲーム機は、中央処理装置（ＣＰＵ）１０１、ランダムアクセスメモリ（ＲＡＭ）１０２、リードオンリメモリ（ＲＯＭ）１０３、外部記憶装置１０４、画像生成回路１０５、ディスプレイ１０６、音生成回路１０７、音出力装置１０８、入力インタフェース（Ｉ／Ｆ）１０９、入力装置１１０、およびシステムバス１１１を備えている。ＣＰＵ１０１、ＲＡＭ１０２、ＲＯＭ１０３、外部記憶装置１０４、画像生成回路１０５、音生成回路１０７、および入力Ｉ／Ｆ１０９は、システムバス１１１に接続されている。
【００１９】
ＣＰＵ１０１は、このゲーム機の動作の全体を制御する。ＲＡＭ１０２は、ＣＰＵ１０１が動作する上で使用するプログラム実行領域やワーク領域などに使用する読み出しおよび書き込み可能なメモリである。ＲＯＭ１０３は、ＣＰＵ１０１が実行する各種の制御プログラム（ＢＩＯＳ：Basic Input/Output SystemやＯＳ：Operating Systemなど）などを格納する読み出し専用メモリである。外部記憶装置１０４は、ゲームプログラムおよび必要な各種のデータなどを記憶する記憶装置である。外部記憶装置１０４としては、例えばＣＤ−ＲＯＭやハードディスクなどが例示される。
【００２０】
画像生成回路１０５は、ＣＰＵ１０１からの指示に基づいて各種の画像（動画や静止画）を生成しディスプレイ１０６に表示する。音生成回路１０７は、ＣＰＵ１０１からの指示に基づいて各種の音（効果音やバックグラウンドミュージックなど）を音出力装置１０８に出力する。入力Ｉ／Ｆ１０９は、プレイヤが操作する入力装置１１０の操作情報を取得し、ディジタルデータに変換してＣＰＵ１０１に向けて出力する。これによりＣＰＵ１０１は、プレイヤの入力装置１１０の操作による操作情報を取得できる。
【００２１】
このゲーム機では、ＣＰＵ１０１が外部記憶装置１０４に格納されているゲームプログラムおよび必要なデータをＲＡＭ１０２にロードして実行することによりゲームがプレイできる。ゲームの画面はディスプレイ１０６に表示され、各種の音が音出力装置１０８から出力される。ゲームのプレイヤは、ディスプレイに表示されたゲーム画面を見ながら入力装置１１０によりゲームに対して各種の操作入力を行う。実行されるゲームはどのようなものでもよい。ただし、以下に説明するような、３次元ゲーム空間で本発明に係るヒットチェック処理を行なうようなゲームであるものとする。
【００２２】
図２は、図１のゲーム機によりゲームを実行した際の表示画面例である。このゲームでは３次元ゲーム空間内にいくつかのオブジェクト２０１〜２０３，２１１，２１２などを配置し、ゲーム空間内の所定の視点から見える画面をディスプレイに表示して図２のような画面を構成する。特に本実施形態では、データ量を少なくするため、あらかじめ基準となるオブジェクトを幾つか用意しておき、その基準オブジェクトを拡大・縮小・回転して３次元ゲーム空間内の所定位置に配置する。これにより、同種類のオブジェクトについては１つの基準オブジェクトのデータから生成できるので、３次元ゲーム空間に配置する全オブジェクトのデータを持つ必要がなく、データ容量を削減できる。
【００２３】
図３（ａ）は、ゲーム空間内に配置する木を表すオブジェクトの基準となる基準オブジェクトを示す。図３（ｂ）は、３次元ゲーム空間内に配置する家を表すオブジェクトの基準となる基準オブジェクトを示す。実際には、これらのオブジェクトは、基準オブジェクトを表現するための基準座標系の上に配置された複数のポリゴンデータ（ここでは３角形のポリゴンとして説明する）から構成されている。ここでは、図示したような木や家など、地形を構成するオブジェクトを例に説明するので、図３（ａ）や図３（ｂ）のような基準オブジェクトを地形データと呼ぶものとする。また、地形データの座標系を地形データ座標系と呼ぶものとする。
【００２４】
図２のオブジェクト２０１〜２０３は、それぞれ図３（ａ）の木の地形データを元にして拡大・縮小・回転して３次元ゲーム空間を表すワールド座標系の所定の位置に配置したものである。同様に、図２のオブジェクト２１１，２１２は、それぞれ図３（ｂ）の家の地形データを拡大・縮小・回転してワールド座標系の所定の位置に配置したものである。このように基準となる地形データを拡大・縮小・回転してワールド座標系に配置する（すなわち、地形データ座標系からワールド座標系への座標変換）ことにより、ゲーム空間内のいわゆるマップを作成する。
【００２５】
図３（ａ）の３０１や図３（ｂ）の３０２は、地形データ座標系における地形データの範囲を示す直方体である。地形データを構成する複数のポリゴンデータから、ｘ座標、ｙ座標、ｚ座標それぞれの最小値と最大値を取り、それらの最小値と最大値で規定される範囲が、この地形データの範囲を示す直方体となる。この直方体の頂点のうち、ｘ座標、ｙ座標、ｚ座標が最小値の頂点が地形データ座標系の原点（０，０，０）となるように、地形データを設定するものとする。例えば、図３（ａ）では位置３１１が原点、図３（ｂ）では位置３１２が原点である。このように設定することにより、地形データのポリゴンデータのｘ、ｙ、ｚ座標値がすべて正値になり、後に説明するヒットチェック時の計算が容易になる。３２１，３２２は地形データ座標系のｘｙｚ座標軸を示す。ここでは、原点３１１，３１２に合わせて座標軸を記載すると見にくくなるため、平行移動して座標軸３２１，３２２を図示した。
【００２６】
各地形データにおいては、その地形データの範囲を示す直方体３０１，３０２を所定の大きさの基準となる直方体で分割したブロックを設定しておく。図３（ｃ）は、地形データを所定の大きさのブロックに分けた様子を示す。一番外側の直方体は図３（ａ）の３０１や図３（ｂ）の３０２に示した地形データの範囲を示す直方体であり、その中にある３３１，３３２などがブロックである。ブロックのｘ、ｙ、ｚ軸方向の大きさの組データをブロックサイズと呼ぶ。また、ｘ、ｙ、ｚ軸方向でそれぞれ分割している数の組をブロック数と呼ぶ。例えば、図３（ａ）や図３（ｂ）では、図３（ｃ）に示したようにｘ、ｙ、ｚ軸方向にそれぞれ４分割しているので、（４，４，４）がブロック数である。
【００２７】
次に、３次元ゲーム空間にオブジェクトを配置して構成されるマップ、およびそのマップ内に配置されるオブジェクトの元になる地形データのデータ構造について説明する。
【００２８】
図４（ｂ）は、図３で説明したような１つの地形データのデータ構造を示す。４１１は地形データのサイズ、４１２はブロックサイズ、４１３はブロック数を示す。地形データのサイズ４１１は、地形データの大きさを示す直方体３０１や３０２のｘ、ｙ、ｚ軸方向の大きさを示す。ここでは地形データの頂点３１１，３１２を原点としているので、その原点から一番離れた頂点３１３，３１４のｘ、ｙ、ｚ座標値が地形データのサイズに等しくなる。ブロックサイズ４１２は、図３で説明したブロックの大きさである。ブロック数４１３は、図３で説明したブロック数である。地形データサイズとブロックサイズが分かれば、その地形データサイズの直方体をそのブロックサイズの直方体で分割できるので、ブロック数は求めることができる。また、地形データサイズとブロック数が分かれば、その地形データサイズの直方体をそのブロック数でｘ、ｙ、ｚ方向それぞれに分割できるので、ブロックサイズを求めることができる。
【００２９】
図４（ｂ）の４１４は、各ブロックのブロックデータを並べたものである。ブロックデータは、ｘ、ｙ、ｚ軸方向それぞれの位置を表す数を並べて特定される。例えば、ブロックデータを並べた４１４の先頭のブロックは「ブロック１−１−１」と記載しているが、これはｘ軸方向で１番目（順番はｘ座標の昇順にブロック単位で１番目、２番目、…と数える。ｙ軸方向およびｚ軸方向も同様である。）、ｙ軸方向で１番目、ｚ軸方向で１番目に位置するブロックを示している。
【００３０】
図４（ｃ）に、１つのブロックデータのデータ構造を示す。１つのブロックデータは、そのブロックに含まれるポリゴンを特定するポリゴン番号を並べたものである。例えば、図３（ａ）の木の地形データは複数の３角形のポリゴンからなるが、その複数のポリゴンのうちブロック１−１−１に一部分でも係っているポリゴンのポリゴン番号を図４（ｃ）のように並べて、図４（ｂ）のブロックデータ４１４のうちのブロック１−１−１を構成する。ブロックは地形データの大きさを示す直方体を機械的に分割したものであるので、１つのポリゴンが複数のブロックに架かる場合があるが、その場合、そのポリゴンのポリゴン番号は、それら複数のブロックのブロックデータに重複して記載しておく。
【００３１】
図４（ｄ）に、１つのポリゴンデータのデータ構造を示す。ポリゴンの形は任意だが、ここでは３角形のポリゴンを例に説明する。１つのポリゴンデータは、そのポリゴンの３角形の３つの頂点を特定する頂点データ１，２，３、その３角形の法線ベクトル４３１、そのポリゴンの色や材質などの属性を示すポリゴン属性４３２、カリング中心４３３、およびカリング半径４３４を備える。頂点データは、頂点の座標を特定する頂点番号である。カリング中心４３３はそのポリゴンの頂点の少なくとも１つに外接しそのポリゴンを含む球（カリング球と呼ぶ）の中心を特定するデータ、カリング半径はカリング球の半径である。カリング球については、後にヒットチェックの手順を説明する際に説明する。
【００３２】
図４（ｅ）は、１つの頂点データの内容を示す。頂点データは、頂点番号で特定され、その頂点の（ｘ，ｙ，ｚ）座標からなる。隣り合うポリゴンは、幾つかの頂点を共有し、同じ頂点は同じ頂点番号で表されるので、図４（ｄ）のポリゴンデータの頂点データには、別のポリゴンで同じ頂点番号を持つものがある。図４（ｅ）の頂点データは座標であり、頂点番号は自然数の番号であるので、明らかにデータ容量としては頂点番号で表現した方がデータ容量が小さい。そこで、図４（ｄ）の頂点データには、直接に頂点座標を格納するのでなく、頂点番号を格納し、別に図４（ｅ）のように頂点座標を持つようにしている。
【００３３】
以上のように、図４（ｂ）〜（ｅ）のデータ構造で、図３で説明した地形データ座標系上の地形データを表現する。
【００３４】
図４（ａ）は、ワールド座標系のマップ配置データである。上述したように、ワールド座標系に、図４（ｂ）〜（ｅ）で説明した地形データ座標系の地形データを座標変換して所定位置に配置することにより、マップを構成する。図４（ａ）の４０２は地形データ番号を示し、４０３は地形データを地形データ座標系からワールド座標系へと座標変換する変換マトリクスを示す。地形データ番号４０２は、図４（ｂ）の構造の１つの地形データを特定する番号である。例えば、１行目のレコードは、地形データ番号４０２が「４１」で、その変換マトリクス４０３が「Ｍ１」である。これは、地形データ番号が「４１」の地形データ（図４（ｂ）〜（ｅ）のデータ構造）に対し、変換マトリクスＭ１の変換を施して、ワールド座標系に配置することを示している。これにより、１つのオブジェクトがマップ上に配置されたことになる。他のオブジェクトについても、同様にして、地形データ番号４０２で地形データを特定し、変換マトリクス４０３で座標変換して、ワールド座標系に配置していく。変換マトリクス４０３は従来より知られている座標変換を行なうマトリクスであり、各座標軸に沿って独立に拡大、縮小、回転したり、座標軸方向にシフトすることを表現できるものである。図４（ａ）の４０１は、ワールド座標系に配置する１つのオブジェクトを表す図４（ａ）の１行のデータに付した番号である。この番号自体はデータとして持ってはいないが、図４（ａ）のマップ配置データ中の何番目（第０番目から開始するものとする）の行データであるかでマップ内の１つのオブジェクトが特定できるので、この番号４０１をオブジェクトＩＤとして用いている。
【００３５】
図５に、ヒットチェックを行う手順の具体例を示す。図５（ａ）において、ワールド座標系に各種の地形を構成するオブジェクト５１１，５１２などが配置されている。いま、オブジェクト５１１は図４（ａ）のマップ配置データ中のオブジェクトＩＤが「０」の行データで特定されるオブジェクトであり、オブジェクト５１２はオブジェクトＩＤが「１」の行データで特定されるオブジェクトであるものとする。ヒットチェックを行う対象である移動オブジェクト５０１（ここでは球で説明する）と地形の各オブジェクトとのヒットチェックを順番に行なう。まず、図４（ａ）のマップ配置データのオブジェクトＩＤ４０１が「０」のオブジェクト５１１とのヒットチェックを行なう。そのヒットチェックの方法は、以下のようなものである。
【００３６】
まず、チェック対象の球５０１の座標をワールド座標系からオブジェクト５１１の地形データ座標系に逆変換する。オブジェクト５１１の地形データ座標系からワールド座標系への変換マトリクスは図４（ａ）に示すとおりＭ１であるので、逆変換を行なう逆変換マトリクスＭ１’はＭ１から求められる。図５（ｂ）は、オブジェクト５１１の地形データ座標系に球５０１を逆変換した様子を示す。５２１は逆変換したヒットチェック対象の球を示す。５２２はオブジェクト５１１の元になった地形データを示す。次にチェック対象の球５２１が地形データ５２２のどのブロックに含まれるかを求める。球５２１の中心と半径は分かっており、地形データ５２２のブロックサイズは図４（ｂ）の４１２から分かるので、球５２１がどのブロックに架かるかは容易に求められる。球５２１が地形データのどのブロックにも架かっていないときは、このオブジェクト５１１にはヒットしなかったと言うことである。ここでは、球５２１が図５（ｂ）のブロック５２３に架かっていたとする。この場合は、ブロック５２３に含まれるポリゴン（図４（ｃ）のブロックデータから分かる）の１つ１つについて詳細にヒットチェックする。
【００３７】
１つのポリゴンとのヒットチェックは、以下のように行なう。まず、そのポリゴンのポリゴン番号から図４（ｄ）のポリゴンデータを取得する。各ポリゴンには、カリング球が設定されており、カリング球の中心と半径は図４（ｄ）の４３３，４３４から分かる。カリング球は、そのポリゴンの頂点の少なくとも１つに外接しそのポリゴンを含む球である。カリング球を用いることにより、ヒットチェック対象の球５２１と当該ポリゴンとのヒットチェックの際に、ヒットチェックしないことが明らかなポリゴンを容易に判定できるので、厳密にヒットチェック処理を行なうポリゴンを絞り込むことができ、ヒットチェック処理の処理負荷が軽減される。
【００３８】
なお、ここではポリゴンの頂点の少なくとも１つに外接しそのポリゴンを含む球をカリング球としたが、必ずしも外接している必要はなく、例えばポリゴンを内部に含む球をカリング球としてもよい。ただし、頂点に外接する球をカリング球とした方が上記の絞り込みの効率はよい。
【００３９】
図５（ｃ）に、チェック対象の球５２１とカリング球５３２とのヒットチェックの様子を示す。カリング球５３２は、ポリゴン５３１のカリング球である。カリング球５３２はポリゴン５３１をその球の内部に含むので、球５２１とカリング球５３１とが重ならなければ、明らかにそのポリゴン５３１と球５２１とはヒットしない。球５２１とカリング球５３１とが重なるか否かは、球５２１の中心とカリング球５３１の中心との距離を求め、その距離が球５２１の半径とカリング球５３１の半径との和より大きいか否かを判定することにより決定できる。前記距離が前記半径の和より大きいときは、それらの球は重ならないと言うことである。距離の算出はｘ、ｙ、ｚ座標のそれぞれの差を求めてそれらの２乗和を求めればよい。球５２１とカリング球５３１とが重なる場合は、より厳密に球５２１と当該ポリゴンとのヒットチェックに進む。
【００４０】
カリング球５３２は、好ましくはポリゴンの３角形５３１の３つの頂点に外接する球とするのがよい。すなわち、３角形５３１の外接円の中心を中心とし、その外接円の半径を半径とする球を、カリング球５３２とするのがよい。このようなカリング球にすれば、カリング球の大きさが最小になり、より小さなカリング球で球５２１と重なるか否かのチェックを行なえるからである。より小さなカリング球を用いることにより、球５２１と重ならないカリング球をより多く発見でき、厳密なヒットチェックを行なうべきポリゴンをより少なく絞り込める。ただし、ポリゴンの３角形の３つの頂点に外接する球をカリング球とする場合は、図４（ｄ）のカリング中心４３３の欄に、地形データ座標系の任意の位置を表現できるだけの記憶容量が必要となる。
【００４１】
従って、本実施の形態では、ポリゴンの３角形５３１の３つの頂点に外接する球をカリング球５３２とするのではなく、３角形５３１の１つの頂点を中心とし別の１つの頂点に外接する球をカリング球５３２とする。例えば、図５（ｃ）では、ポリゴンの３角形５３１の頂点Ａを中心とし頂点Ｃに外接する球を、カリング球５３２としている。３角形５３１の３つの頂点のうち、どの頂点をカリング中心としどの頂点を外接する点とするかは、以下のように定める。すなわち、３角形５３１の３辺のうち１番長い辺の反対側の頂点Ａをカリング中心とし、２番目に長い辺ＡＣを半径とする球を、カリング球５３２としている。これにより、残る頂点Ｂはカリング球５３２の内部に含まれることが保証され、カリング半径はより短くできるとともに、カリング中心を頂点番号で表現できるので、図４（ｄ）のカリング中心４３３の欄のバイト数は図４（ｅ）の頂点データを特定する頂点番号を記載できるだけのバイト数でよくなり、データ量を省ける。
【００４２】
球５２１とカリング球５３２とが重なっている場合は、対応するポリゴン５３１と球５２１との厳密なヒットチェック処理を行なう。図５（ｄ）は、その様子を示す。このヒットチェック処理は、従来より行なわれている方法で行なえばよい。
【００４３】
図６は、上述したヒットチェックの処理手順を説明するためのフローチャートである。ステップ６０１で、変数ｉを０に初期化し、さらに距離を設定する変数ＭＩＮとヒットしたオブジェクトＩＤを設定する変数ＨＩＴにそれぞれ９９９９を設定する。次にステップ６０２で、第ｉ番目のオブジェクト（すなわち、図４（ａ）のオブジェクトＩＤ４０１がｉに等しいオブジェクト）とのヒットチェックを行なう。この処理については、図７で詳しく説明する。図７のヒットチェック処理によりヒットチェック対象の球とヒットしたポリゴンまでの距離が返されるので、その距離の値を変数ｄにセットする。
【００４４】
次にステップ６０３で、返された距離値ｄと変数ＭＩＮの値とを比較する。ｄの値がＭＩＮより小さいときは、その距離値ｄを変数ＭＩＮにセットし、その時点の変数ｉの値を変数ＨＩＴにセットする。その後、ステップ６０５で、変数ｉ＋１がワールド座標系のオブジェクトの数以上になったか（すなわち、マップ内の全オブジェクトのヒットチェックが終了したか）否か判別し、まだチェックすべきオブジェクトがあるときは、ステップ６０６でｉを歩進し、ステップ６０２に戻る。ステップ６０５でマップ内の全オブジェクトについてヒットチェックが終了したときは、処理を終了する。
【００４５】
図７は、図６のステップ６０２のヒットチェック処理の詳細を示す。この処理は、図５で説明した１つのオブジェクト５１１とヒットチェック対象の球５０１とのヒットチェック処理に対応する。ステップ７０１で、ヒットチェック対象の球５０１のワールド座標系での座標を、チェック対象のオブジェクトの地形データの座標系である地形データ座標系に逆変換する（その結果は例えば図５（ｂ））。ステップ７０２で、逆変換した結果の球の座標から、地形データ内のどのブロックにチェック対象の球の座標が含まれるかを決定する。ステップ７０３で、チェック対象の球が地形データの何れかのブロックにヒットしていたときは、ステップ７０４で変数ｊをゼロクリアし、変数ＭＩＮＰＯに９９９９をセットし、変数ＨＩＴＰＯに９９９９をセットし、ステップ７０５で第ｊ番目のポリゴンに対するヒットチェック処理を行なう。この処理については、図８で詳しく説明する。図８のヒットチェック処理によりヒットチェック対象の球とヒットしたポリゴンまでの距離が返されるので、その距離の値を変数ｄｄにセットする。
【００４６】
なお、第ｊ番目のポリゴンとは、ヒットしたブロックのブロックデータ（図４（ｃ））のポリゴン番号の並びを第０番目、第１番目、…と上から数えた順番で第ｊ番目のポリゴン番号を取得し、該ポリゴン番号で特定されるポリゴンのことを言う。後述するステップ７０８や７０９から分かるように、ステップ７０５〜７０９のループは、ヒットしたブロックのブロックデータ（図４（ｃ））に含まれるすべてのポリゴン番号のポリゴンについて、順に取り出してヒットチェックを行なっているものである。
【００４７】
次にステップ７０６で、返された距離値ｄｄと変数ＭＩＮＰＯの値とを比較する。ｄｄの値がＭＩＮＰＯより小さいときは、ステップ７０７でその距離値ｄｄを変数ＭＩＮＰＯにセットし、第ｊ番目のポリゴンのポリゴン番号を図４（ｃ）で説明したブロックデータから取得して変数ＨＩＴＰＯにセットする。その後、ステップ７０８で、変数ｊ＋１が現在処理対象のブロックに含まれるポリゴン数以上になったか（すなわち、図４（ｃ）のブロック内の最後のポリゴンまでヒットチェックが終了したか）否か判別し、まだチェックすべきポリゴンがあるときは、ステップ７０９でｊを歩進し、ステップ７０５に戻る。ステップ７０８で当該ブロック内の全ポリゴンについてヒットチェックが終了したときは、処理を終了して上位にリターンする。リターンするときには、ヒットしたポリゴンがあれば、そのポリゴンまでの距離がＭＩＮＰＯに、そのポリゴンのポリゴン番号がＨＩＴＰＯに、それぞれセットされているので、その距離ＭＩＮＰＯとポリゴン番号ＨＩＴＰＯを上位に返す。なお、ヒットしたポリゴンがなければ、ＭＩＮＰＯとＨＩＴＰＯには９９９９がセットされて（これはヒットしたポリゴンがなかったことを示す）上位にリターンする。
【００４８】
図８は、図７のステップ７０５の第ｊ番目のポリゴンとのヒットチェック処理の詳細を示す。ステップ８０１で、チェック対象の球と上位から指定されている第ｊ番目のポリゴンのカリング球との距離を算出しヒットチェックを行なう。この処理は、図５（ｃ）で説明したカリング球とのヒットチェックの処理である。ステップ８０２でカリング球にヒットしたか否か判別し、ヒットしていたときは、そのカリング球に対応するポリゴンである三角形とのヒットチェック処理を行なう。三角形とヒットしていたときは、その距離を上位に返してリターンする。ステップ８０２でヒットしなかったとき、およびステップ８０４でヒットしなかったときは、距離として９９９９を上位に返して（距離が９９９９のときはヒットしなかったことを示している）リターンする。
【００４９】
以上の処理により、図６の処理終了時には、ＭＩＮおよびＨＩＴが９９９９以外であれば、何れかのオブジェクトにヒットしたことになり、その場合、ヒットしたオブジェクトまでの距離が変数ＭＩＮに格納され、ヒットしたオブジェクトのオブジェクトＩＤが変数ＨＩＴに格納され、ヒットしたポリゴンのポリゴン番号が変数ＨＩＴＰＯに格納されている。なお本例では、マップ内の全オブジェクトのそれぞれに対してステップ６０２〜６０５の処理を行ない、最小の距離ｄでヒットしたオブジェクトを探索しているが、ヒットしたすべてのオブジェクトを求めるようにしてもよい。また、ヒットしたすべてのポリゴンを求めるようにしてもよい。
【００５０】
上記実施の形態では、球と３角形とのヒットチェックを例に説明したが、これに限らず、本発明は種々のヒットチェック処理に適用できる。例えば、１つの点とポリゴンとのヒットチェック、ポリゴン同士のヒットチェックなどにも適用できる。
【００５１】
【発明の効果】
以上説明したように、本発明によれば、あらかじめ基準座標系の上で基準オブジェクトを定義し、その基準オブジェクトを座標変換して３次元ゲーム空間のワールド座標系に配置することにより、ワールド座標系上のオブジェクトを定義しているので、１つの基準オブジェクトから座標変換により幾つものオブジェクトを簡単に生成してワールド座標系の複数のオブジェクトとして配置でき、自由度の高いマップ設計を行なうことができる。また、ヒットチェックは、チェック対象のオブジェクトを基準座標系に逆変換し、基準座標系の上の基準オブジェクトに対してヒットチェックを行なうので、従来ワールド座標系のオブジェクトごとに持っていたヒットチェックのための情報は持つ必要がなく、データ量を削減できる。ヒットチェックの際、チェック対象のオブジェクトの方を逆変換して基準座標系に持っていくので、計算量も少なくて済む。マップ配置データの座標変換情報を変化させれば、ワールド座標系のオブジェクトを任意に変形したり移動することも容易に行なえる。さらに、ポリゴンとのヒットチェックにおいて、あらかじめポリゴンを含むカリング球を設定しておき、カリング球とチェック対象とのヒットチェックを行なっているので、より詳細なヒットチェックを行なうべきチェック対象を簡単に絞り込むことができる。カリング球とチェック対象とのヒットチェックは、例えば、距離の計算などの簡単な計算で行なえる。カリング球は、そのポリゴンが３角形であるときは、その３角形の１番長い辺の反対側の頂点を中心とし、２番目に長い辺を半径とする球とすれば、中心位置としてポリゴンの頂点を用いるので、頂点番号などの容量の小さなデータで表現できデータ量を削減することができる。
【図面の簡単な説明】
【図１】本発明に係るヒットチェック方法を適用したゲーム機の構成例を示す図
【図２】ゲームを実行した際の表示画面例を示す図
【図３】基準オブジェクトの例を示す図
【図４】マップ配置データや地形データのデータ構造を示す図
【図５】ヒットチェックを行う手順の具体例を示す図
【図６】ヒットチェックの処理手順を説明するためのフローチャート図
【図７】ヒットチェック処理の詳細な処理手順を示すフローチャート図
【図８】第ｊ番目のポリゴンとのヒットチェック処理の詳細を示すフローチャート図
【符号の説明】
１０１…中央処理装置（ＣＰＵ）、１０２…ランダムアクセスメモリ（ＲＡＭ）、１０３…リードオンリメモリ（ＲＯＭ）、１０４…外部記憶装置、１０５…画像生成回路、１０６…ディスプレイ、１０７…音生成回路、１０８…音出力装置、１０９…入力インタフェース（Ｉ／Ｆ）、１１０…入力装置、１１１…システムバス。
【図１】
0004510257.tif 000002
【図２】
0004510257.tif 000003
【図３】
0004510257.tif 000004
【図４】
0004510257.tif 000005
【図５】
0004510257.tif 000006
【図６】
0004510257.tif 000007
【図７】
0004510257.tif 000008
【図８】
0004510257.tif 000009