(57)【要約】【課題】オブジェクト同士のヒット時のめりこみによる不自然な画像が生成されるのを防止すること。【解決手段】本画像生成システムは、第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの代表点を結ぶ方向ベクトルをもとめ、第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの重複距離にもとづいて、両オブジェクトを引き離すために使用する補正距離を求め、前記補正距離及び前記方向ベクトルにもとづきオブジェクト空間における第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を補正する位置補正手段１１６と、補正された位置に基づいて第１のオブジェクトと第２のオブジェクトの画像を生成する画像生成手段１３０とを含む。【選択図】        図２０
2004334802.tif 000002
【特許請求の範囲】
【請求項１】
画像生成を行う画像生成システムであって、
第１のオブジェクトと第２のオブジェクトが交差している場合に、第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの代表点を結ぶ方向ベクトルをもとめ、第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの重複エリアに基づき、第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの重複距離を決定し、決定した重複距離にもとづいて、両オブジェクトを引き離すために使用する補正距離を求め、前記補正距離及び前記方向ベクトルにもとづきオブジェクト空間における第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を補正する位置補正手段と、
補正された位置に基づいて第１のオブジェクトと第２のオブジェクトの画像を生成する画像生成手段と、
を含むことを特徴とする画像生成システム。
【請求項２】
請求項１において、
第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの各辺について線分交差判定を行い、判定結果に基づき、第１のオブジェクトと第２のオブジェクトの交差の有無を判定する交差判定手段と、
をさらに含むことを特徴とする画像生成システム。
【請求項３】
請求項１乃至２のいずれかにおいて、
前記位置補正手段が、
前記第１のオブジェクトの２次元近似オブジェクトの頂点から前記方向ベクトルに平行な直線を引いて、前記第１のオブジェクトの２次元近似オブジェクトの内部において前記第２のオブジェクトの２次元近似オブジェクトを構成する辺と交わる交点を求め当該交点と頂点の距離と、前記第２のオブジェクトの２次元近似オブジェクトの頂点から前記方向ベクトルに平行な直線を引いて、第２のオブジェクトの２次元近似オブジェクトの内部において第１のオブジェクトの２次元近似オブジェクトを構成する辺と交わる交点とをもとめ当該交点と頂点の距離とをもとめ、最も長い距離に基づき前記重複距離を決定することを特徴とする画像生成システム。
【請求項４】
画像生成を行う画像生成システムであって、
時刻ｔからｔ＋Δｔにおける第１のオブジェクトの２次元近似オブジェクトの各頂点の移動軌跡と第２のオブジェクトの２次元近似オブジェクトが交差している場合に、交点から時刻ｔ＋Δｔの第１のオブジェクトの２次元近似オブジェクトの頂点までの距離である重複距離にもとづいて、両オブジェクトを引き離すために使用する補正距離を求め、前記補正距離及び前記移動軌跡にもとづきオブジェクト空間における第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を補正する手段と、
補正された位置に基づいて第１のオブジェクトと第２のオブジェクトの画像を生成する画像生成手段と、
を含むことを特徴とする画像生成システム。
【請求項５】
請求項４において、
第１のオブジェクトの２次元近似オブジェクトの各頂点の移動軌跡と第２のオブジェクトの２次元近似オブジェクトの辺について線分交差判定を行い、判定結果に基づき、第１のオブジェクトと第２のオブジェクトの交差の有無を判定する手段と、をさらに含むことを特徴とする画像生成システム。
【請求項６】
請求項４乃至５のいずれかにおいて、
前記補正距離に基づき補正された位置に配置された第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの各辺について線分交差判定を行い、交差している場合には、交差している第２のオブジェクトの２次元近似オブジェクトの頂点を特定し、当該頂点と第１のオブジェクトの２次元近似オブジェクトの距離に基づき、両オブジェクトを引き離すために使用する再補正距離を求め、当該再補正距離にもとづきオブジェクト空間における第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を再度補正する再補正処理手段と、をさらに含み、
前記画像生成手段は、
前記再補正距離にもとづき再度補正された位置に基づいて第１のオブジェクトと第２のオブジェクトの画像を生成することを特徴とする画像生成システム。
【請求項７】
請求項１乃至６のいずれかにおいて、
オブジェクト空間における第１のオブジェクトと第２のオブジェクトを２次元平面に投影し、投影された第１のオブジェクト及び第２のオブジェクトをそれぞれ多角形で近似して第１のオブジェクト及び第２のオブジェクトの２次元近似オブジェクトを生成する２次元近似オブジェクト生成手段を、含むことを特徴とする画像生成システム。
【請求項８】
画像生成を行う画像生成システムであって、
オブジェクト空間における第１のオブジェクトと第２のオブジェクトを２次元平面に投影し、投影された第１のオブジェクト及び第２のオブジェクトをそれぞれ多角形で近似して第１のオブジェクト及び第２のオブジェクトの２次元近似オブジェクトを生成する２次元近似オブジェクト生成手段と、
第１のオブジェクト及び第２のオブジェクトの２次元近似オブジェクトに基づいて、両オブジェクトを引き離すために使用する補正距離を求め、前記補正距離にもとづきオブジェクト空間における第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を補正する手段と、
補正された位置に基づいて第１のオブジェクトと第２のオブジェクトの画像を生成する画像生成手段と、
を含むことを特徴とする画像生成システム。
【請求項９】
画像生成を行う画像生成システムであって、
オブジェクト空間における第１のオブジェクトと第２のオブジェクトを２次元平面に投影し、投影された第１のオブジェクト及び第２のオブジェクトをそれぞれ多角形で近似して第１のオブジェクト及び第２のオブジェクトの２次元近似オブジェクトを生成する２次元近似オブジェクト生成手段と、
第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの各辺について線分交差判定を行い、又は第１のオブジェクトの２次元近似オブジェクトの各頂点の移動軌跡と第２のオブジェクトの２次元近似オブジェクトの辺について線分交差判定を行い、いずれかの判定結果に基づき、第１のオブジェクトと第２のオブジェクトの交差の有無を判定する手段と、
を含むことを特徴とする画像生成システム。
【請求項１０】
請求項１乃至９のいずれかにおいて、
ゲーム状況に応じて、第１のオブジェクト及び第２のオブジェクトの少なくとも一方の２次元近似オブジェクトの頂点数を変化させる２次元近似オブジェクト変更手段を含むことを特徴とする画像生成システム。
【請求項１１】
請求項１乃至１０のいずれかにおいて、
前記２次元近似オブジェクト変更手段が、
第１のオブジェクト又は第２のオブジェクトと仮想カメラ又はプレーヤキャラクタとの距離に応じて第１のオブジェクト又は第２のオブジェクトの２次元近似オブジェクトの頂点数を変化させることを特徴とする画像生成システム。
【請求項１２】
請求項１乃至１１のいずれかにおいて、
前記２次元近似オブジェクト変更手段が、
オブジェクト空間の天候や視界状況又は応じて前記２次元近似オブジェクトの頂点数を変化させることを特徴とする画像生成システム。
【請求項１３】
請求項１乃至１２のいずれかにおいて、
前記２次元近似オブジェクト変更手段が、
第１のオブジェクト又は第２のオブジェクトの視認性に応じて前記２次元近似オブジェクトの頂点数を変化させることを特徴とする画像生成システム。
【請求項１４】
コンピュータを、
第１のオブジェクトと第２のオブジェクトが交差している場合に、第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの代表点を結ぶ方向ベクトルをもとめ、第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの重複エリアに基づき、第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの重複距離を決定し、決定した重複距離にもとづいて、両オブジェクトを引き離すために使用する補正距離を求め、前記補正距離及び前記方向ベクトルにもとづきオブジェクト空間における第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を補正する手段と、
補正された位置に基づいて第１のオブジェクトと第２のオブジェクトの画像を生成する画像生成手段と、
して機能させることを特徴とするプログラム。
【請求項１５】
請求項１４において、
第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの各辺について線分交差判定を行い、判定結果に基づき、第１のオブジェクトと第２のオブジェクトの交差の有無を判定する交差判定手段と、
して機能させることを特徴とするプログラム。
【請求項１６】
請求項１４乃至１５のいずれかにおいて、
前記補正距離算出手段が、
前記第１のオブジェクトの２次元近似オブジェクトの頂点から前記方向ベクトルに平行な直線を引いて、前記第１のオブジェクトの２次元近似オブジェクトの内部において前記第２のオブジェクトの２次元近似オブジェクトを構成する辺と交わる交点を求め当該交点と頂点の距離と、前記第２のオブジェクトの２次元近似オブジェクトの頂点から前記方向ベクトルに平行な直線を引いて、第２のオブジェクトの２次元近似オブジェクトの内部において第１のオブジェクトの２次元近似オブジェクトを構成する辺と交わる交点とをもとめ当該交点と頂点の距離とをもとめ、最も長い距離に基づき前記重複距離を決定することを特徴とするプログラム。
【請求項１７】
コンピュータを、
時刻ｔからｔ＋Δｔにおける第１のオブジェクトの２次元近似オブジェクトの各頂点の移動軌跡と第２のオブジェクトの２次元近似オブジェクトが交差している場合には、交点から時刻ｔ＋Δｔの第１のオブジェクトの２次元近似オブジェクトの頂点までの距離である重複距離にもとづいて、両オブジェクトを引き離すために使用する補正距離を求め、前記補正距離及び前記移動軌跡にもとづきオブジェクト空間における第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を補正する手段と、
補正された位置に基づいて第１のオブジェクトと第２のオブジェクトの画像を生成する画像生成手段と、
して機能させることを特徴とするプログラム。
【請求項１８】
請求項１７において、
第１のオブジェクトの２次元近似オブジェクトの各頂点の移動軌跡と第２のオブジェクトの２次元近似オブジェクトの辺について線分交差判定を行い、判定結果に基づき、第１のオブジェクトと第２のオブジェクトの交差の有無を判定する手段として機能させることを特徴とするプログラム。
【請求項１９】
請求項１７乃至１８のいずれかにおいて、
前記補正距離に基づき補正された位置に配置された第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの各辺について線分交差判定を行い、交差している場合には、交差している第２のオブジェクトの２次元近似オブジェクトの頂点を特定し、当該頂点と第１のオブジェクトの２次元近似オブジェクトの距離に基づき、両オブジェクトを引き離すために使用する再補正距離を求め、当該再補正距離にもとづきオブジェクト空間における第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を再度補正する再補正処理手段として機能させ、
前記画像生成手段が、
前記再補正距離にもとづき再度補正された位置に基づいて第１のオブジェクトと第２のオブジェクトの画像を生成することを特徴とするプログラム。
【請求項２０】
請求項１４乃至１９のいずれかにおいて、
オブジェクト空間における第１のオブジェクトと第２のオブジェクトを２次元平面に投影し、投影された第１のオブジェクト及び第２のオブジェクトをそれぞれ多角形で近似して第１のオブジェクト及び第２のオブジェクトの２次元近似オブジェクトを生成する２次元近似オブジェクト生成手段として機能させることを特徴とするプログラム。
【請求項２１】
コンピュータを、
オブジェクト空間における第１のオブジェクトと第２のオブジェクトを２次元平面に投影し、投影された第１のオブジェクト及び第２のオブジェクトをそれぞれ多角形で近似して第１のオブジェクト及び第２のオブジェクトの２次元近似オブジェクトを生成する２次元近似オブジェクト生成手段と、
第１のオブジェクト及び第２のオブジェクトの２次元近似オブジェクトに基づいて、両オブジェクトを引き離すために使用する補正距離を求め、前記補正距離にもとづきオブジェクト空間における第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を補正する手段と、
補正された位置に基づいて第１のオブジェクトと第２のオブジェクトの画像を生成する画像生成手段と、
して機能させることを特徴とするプログラム。
【請求項２２】
コンピュータを、
オブジェクト空間における第１のオブジェクトと第２のオブジェクトを２次元平面に投影し、投影された第１のオブジェクト及び第２のオブジェクトをそれぞれ多角形で近似して第１のオブジェクト及び第２のオブジェクトの２次元近似オブジェクトを生成する２次元近似オブジェクト生成手段と、
第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの各辺について線分交差判定を行い、又は第１のオブジェクトの２次元近似オブジェクトの各頂点の移動軌跡と第２のオブジェクトの２次元近似オブジェクトの辺について線分交差判定を行い、いずれかの判定結果に基づき、第１のオブジェクトと第２のオブジェクトの交差の有無を判定する手段と、
して機能させることを特徴とするプログラム。
【請求項２３】
請求項１４乃至２２のいずれかにおいて、
ゲーム状況に応じて、第１のオブジェクト及び第２のオブジェクトの少なくとも一方の２次元近似オブジェクトの頂点数を変化させる２次元近似オブジェクト変更手段として機能させることを特徴とするプログラム。
【請求項２４】
請求項１４乃至２３のいずれかにおいて、
前記２次元近似オブジェクト変更手段が、
第１のオブジェクト又は第２のオブジェクトと仮想カメラ又はプレーヤキャラクタとの距離に応じて第１のオブジェクト又は第２のオブジェクトの２次元近似オブジェクトの頂点数を変化させることを特徴とするプログラム。
【請求項２５】
請求項１４乃至２４のいずれかにおいて、
前記２次元近似オブジェクト変更手段が
オブジェクト空間の天候や視界状況又は応じて前記２次元近似オブジェクトの頂点数を変化させることを特徴とするプログラム。
【請求項２６】
請求項１４乃至２５のいずれかにおいて、
前記２次元近似オブジェクト変更手段が、
第１のオブジェクト又は第２のオブジェクトの視認性に応じて前記２次元近似オブジェクトの頂点数を変化させることを特徴とするプログラム。
【請求項２７】
コンピュータにより読みとり可能な情報記憶媒体であって、請求項１４乃至２６のいずれかに記載のプログラムを記憶することを特徴とする情報記憶媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、画像生成システム、プログラム及び情報記憶媒体に関する。
【０００２】
【背景技術】
従来より、仮想的な３次元空間であるオブジェクト空間内において仮想カメラ（所与の視点）から見える画像を生成する画像生成システム（例えばゲームシステム）が知られており、いわゆる仮想現実を体験できるものとして人気が高い。
【０００３】
このような画像生成システムを用いて例えばシューティングゲームやレースゲーム等の様々なゲームシステムを構築する場合、様々な場面でオブジェクト空間内のオブジェクト間のヒットチェックや交差位置の判定が必要となる場合がある。かかる場合従来は代表点によるヒットチェックや、単純なヒットチェックボックスを用いたヒットチェックを行っていた。
【０００４】
【特許文献１】
特開平１１−１７５７４７号
【０００５】
【発明が解決しようとする課題】
しかし代表点によるヒットチェックや単純なヒットチェックボックスを用いたヒットチェックを行うだけだと、現実世界ではあり得ないオブジェクト同士のめりこみが発生するという不具合があった。
【０００６】
本発明は、以上のような課題に鑑みてなされたものであり、その目的とするところは、オブジェクト同士のヒット時のめりこみによる不自然な画像が生成されるのを防止することが可能な画像生成システム、プログラム及び情報記憶媒体を提供することにある。
【０００７】
【課題を解決するための手段】
（１）本発明は、画像生成を行う画像生成システムであって、
第１のオブジェクトと第２のオブジェクトが交差している場合に、
第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの代表点を結ぶ方向ベクトルをもとめ、第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの重複エリアに基づき、第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの重複距離を決定し、決定した重複距離にもとづいて、両オブジェクトを引き離すために使用する補正距離を求め、前記補正距離及び前記方向ベクトルにもとづきオブジェクト空間における第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を補正する位置補正手段と、
補正された位置に基づいて第１のオブジェクトと第２のオブジェクトの画像を生成する画像生成手段と、を含むことを特徴とする。
【０００８】
また本発明に係るプログラムは、コンピュータにより実行可能なプログラム（情報記憶媒体又は搬送波に具現化されるプログラム）であって、上記手段をコンピュータに実現させる（上記手段としてコンピュータを機能させる）ことを特徴とする。また本発明に係る情報記憶媒体は、コンピュータにより読み取り可能（使用可能）な情報記憶媒体であって、上記手段をコンピュータに実現させる（上記手段としてコンピュータを機能させる）ためのプログラムを含むことを特徴としている。
【０００９】
ここで第１のオブジェクト又は第２のオブジェクトの２次元近似オブジェクトは閉じた多角形でもよいし、開いた多角形でもよい。
【００１０】
２次元近似オブジェクトの代表点とは、例えば２次元近似オブジェクトの重心でもよい。
【００１１】
また例えば重複エリアの方向ベクトルの最も長い距離を重複距離として決定するようにしてもよい。
【００１２】
補正距離に基づく補正は例えば第１のオブジェクト又は第２のオブジェクトのいずれか一方を前記方向ベクトルの方向に移動させるようにしてもよいし、第１のオブジェクト及び第２のオブジェクトを両方移動させて、補正距離だけ前記方向ベクトルの方向に引きはなすようにしてもよい。
【００１３】
本発明によれば、第１のオブジェクト及び第２のオブジェクトがヒットした場合に、現実世界ではあり得ないオブジェクト同士のめりこみが発生し、不自然な画像が生成されるのを防止することが出来る。
【００１４】
（２）また本発明に係る画像生成システム、プログラム及び情報記憶媒体は、
第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの各辺について線分交差判定を行い、判定結果に基づき、第１のオブジェクトと第２のオブジェクトの交差の有無を判定する交差判定手段と、
をさらに含むことを特徴とする。
【００１５】
（３）また本発明に係る画像生成システム、プログラム及び情報記憶媒体は、
前記位置補正手段が、
前記第１のオブジェクトの２次元近似オブジェクトの頂点から前記方向ベクトルに平行な直線を引いて、前記第１のオブジェクトの２次元近似オブジェクトの内部において前記第２のオブジェクトの２次元近似オブジェクトを構成する辺と交わる交点を求め当該交点と頂点の距離と、前記第２のオブジェクトの２次元近似オブジェクトの頂点から前記方向ベクトルに平行な直線を引いて、第２のオブジェクトの２次元近似オブジェクトの内部において第１のオブジェクトの２次元近似オブジェクトを構成する辺と交わる交点とをもとめ当該交点と頂点の距離とをもとめ、最も長い距離に基づき前記重複距離を決定することを特徴とする。
【００１６】
（４）また本発明は、画像生成を行う画像生成システムであって、
時刻ｔからｔ＋Δｔにおける第１のオブジェクトの２次元近似オブジェクトの各頂点の移動軌跡と第２のオブジェクトの２次元近似オブジェクトが交差している場合に、交点から時刻ｔ＋Δｔの第１のオブジェクトの２次元近似オブジェクトの頂点までの距離である重複距離にもとづいて、両オブジェクトを引き離すために使用する補正距離を求め、前記補正距離及び前記移動軌跡にもとづきオブジェクト空間における第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を補正する手段と、
補正された位置に基づいて第１のオブジェクトと第２のオブジェクトの画像を生成する画像生成手段と、を含むことを特徴とする。
【００１７】
また本発明に係るプログラムは、コンピュータにより実行可能なプログラム（情報記憶媒体又は搬送波に具現化されるプログラム）であって、上記手段をコンピュータに実現させる（上記手段としてコンピュータを機能させる）ことを特徴とする。また本発明に係る情報記憶媒体は、コンピュータにより読み取り可能（使用可能）な情報記憶媒体であって、上記手段をコンピュータに実現させる（上記手段としてコンピュータを機能させる）ためのプログラムを含むことを特徴としている。
【００１８】
ここで移動しているものを第１のオブジェクトとし、静止しているものを第２のオブジェクトとしてもよい。また第１のオブジェクトも第２のオブジェクトも移動している場合でもよい。
【００１９】
また第１のオブジェクト又は第２のオブジェクトの２次元近似オブジェクトは閉じた多角形でもよいし、開いた多角形でもよい
２次元近似オブジェクトの代表点とは、例えば２次元近似オブジェクトの重心でもよい。
【００２０】
また交点から時刻ｔ＋Δｔの第１のオブジェクトの２次元近似オブジェクトの頂点までの最も長い重複距離を補正距離として決定するようにしてもよい。
【００２１】
補正距離に基づく補正は例えば第１のオブジェクト又は第２のオブジェクトのいずれか一方を前記方向ベクトルの方向に移動させるようにしてもよいし、第１のオブジェクト及び第２のオブジェクトを両方移動させて、補正距離だけ前記方向ベクトルの方向に引きはなすようにしてもよい。
【００２２】
本発明によれば、第１のオブジェクトの２次元近似オブジェクトの頂点の移動軌跡（移動ベクトル）を用いて第２のオブジェクトの２次元近似オブジェクトとの交差を判定するので、フレーム間でオブジェクトのすり抜けが発生するのを防止することが出来る。
【００２３】
また本発明によれば、第１のオブジェクト及び第２のオブジェクトがオブジェクトがヒットした場合に、現実世界ではあり得ないオブジェクト同士のめりこみが発生し、不自然な画像が生成されるのを防止することが出来る。
【００２４】
なおまず最初にオブジェクト同士でヒットチェックを行ったあとに、さらにフレーム間のすり抜けを防止するために、第１のオブジェクトの２次元近似オブジェクトの頂点の移動軌跡（移動ベクトル）を用いて第２のオブジェクトの２次元近似オブジェクトとの交差を判定するようにしてもよい。
【００２５】
（５）また本発明に係る画像生成システム、プログラム及び情報記憶媒体は、
第１のオブジェクトの２次元近似オブジェクトの各頂点の移動軌跡と第２のオブジェクトの２次元近似オブジェクトの辺について線分交差判定を行い、判定結果に基づき、第１のオブジェクトと第２のオブジェクトの交差の有無を判定する手段と、をさらに含むことを特徴とする。
【００２６】
（６）また本発明に係る画像生成システム、プログラム及び情報記憶媒体は、
前記補正距離に基づき補正された位置に配置された第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの各辺について線分交差判定を行い、交差している場合には、交差している第２のオブジェクトの２次元近似オブジェクトの頂点を特定し、当該頂点と第１のオブジェクトの２次元近似オブジェクトの距離に基づき、両オブジェクトを引き離すために使用する再補正距離を求め、当該再補正距離にもとづきオブジェクト空間における第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を再度補正する再補正処理手段と、をさらに含み、
前記画像生成手段は、
前記再補正距離にもとづき再度補正された位置に基づいて第１のオブジェクトと第２のオブジェクトの画像を生成することを特徴とする。
【００２７】
例えば、前記再補正処理手段が、
交差している第２のオブジェクトの２次元近似オブジェクトの頂点から第１のオブジェクトの移動ベクトル方向に平行な直線を引いて、第１のオブジェクトの２次元近似オブジェクトの辺と交わる交点とをもとめ当該交点から頂点までの距離であるにもとづいて（例えば最も長い距離に基づいて）、両オブジェクトを引き離すための再補正距離を求めるようにしてもよい。
【００２８】
本発明によれば、例えば第２のオブジェクトの２次元近似オブジェクトの頂点が第１のオブジェクトの２次元近似オブジェクトの辺に接触した場合の補正漏れ等を防止することが出来る。
【００２９】
（７）また本発明に係る画像生成システム、プログラム及び情報記憶媒体は、
オブジェクト空間における第１のオブジェクトと第２のオブジェクトを２次元平面に投影し、投影された第１のオブジェクト及び第２のオブジェクトをそれぞれ多角形で近似して第１のオブジェクト及び第２のオブジェクトの２次元近似オブジェクトを生成する２次元近似オブジェクト生成手段を含むことを特徴とする。
【００３０】
（８）また本発明は、オブジェクト空間における第１のオブジェクトと第２のオブジェクトを２次元平面に投影し、投影された第１のオブジェクト及び第２のオブジェクトをそれぞれ多角形で近似して第１のオブジェクト及び第２のオブジェクトの２次元近似オブジェクトを生成する２次元近似オブジェクト生成手段と、第１のオブジェクト及び第２のオブジェクトの２次元近似オブジェクトに基づいて、両オブジェクトを引き離すために使用する補正距離を求め、前記補正距離にもとづきオブジェクト空間における第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を補正する手段と、
補正された位置に基づいて第１のオブジェクトと第２のオブジェクトの画像を生成する画像生成手段とを含むことを特徴とする。
【００３１】
また本発明に係るプログラムは、コンピュータにより実行可能なプログラム（情報記憶媒体又は搬送波に具現化されるプログラム）であって、上記手段をコンピュータに実現させる（上記手段としてコンピュータを機能させる）ことを特徴とする。また本発明に係る情報記憶媒体は、コンピュータにより読み取り可能（使用可能）な情報記憶媒体であって、上記手段をコンピュータに実現させる（上記手段としてコンピュータを機能させる）ためのプログラムを含むことを特徴としている。
【００３２】
（９）また本発明は、画像生成を行う画像生成システムであって、
オブジェクト空間における第１のオブジェクトと第２のオブジェクトを２次元平面に投影し、投影された第１のオブジェクト及び第２のオブジェクトをそれぞれ多角形で近似して第１のオブジェクト及び第２のオブジェクトの２次元近似オブジェクトを生成する２次元近似オブジェクト生成手段と、
第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの各辺について線分交差判定を行い、又は第１のオブジェクトの２次元近似オブジェクトの各頂点の移動軌跡と第２のオブジェクトの２次元近似オブジェクトの辺について線分交差判定を行い、いずれかの判定結果に基づき、第１のオブジェクトと第２のオブジェクトの交差の有無を判定する手段とを含むことを特徴とする。
【００３３】
また本発明に係るプログラムは、コンピュータにより実行可能なプログラム（情報記憶媒体又は搬送波に具現化されるプログラム）であって、上記手段をコンピュータに実現させる（上記手段としてコンピュータを機能させる）ことを特徴とする。また本発明に係る情報記憶媒体は、コンピュータにより読み取り可能（使用可能）な情報記憶媒体であって、上記手段をコンピュータに実現させる（上記手段としてコンピュータを機能させる）ためのプログラムを含むことを特徴としている。
【００３４】
（１０）また本発明に係る画像生成システム、プログラム及び情報記憶媒体は、ゲーム状況に応じて、第１のオブジェクト及び第２のオブジェクトの少なくとも一方の２次元近似オブジェクトの頂点数を変化させる２次元近似オブジェクト変更手段を含むことを特徴とする。
【００３５】
ヒットを取る相手方に応じて２次元近似オブジェクトの頂点数を変化させるようにしてもよい。例えばプレーヤ移動体とヒットをとる場合には２次元近似オブジェクトの頂点数を増やし、高精度の判定を行うようにしてもよい。
【００３６】
本発明によればゲーム状況に応じて２次元近似オブジェクトの頂点数を変化させることで、ゲーム状況に応じて補正の精度を調節することが出来る。
【００３７】
（１１）また本発明に係る画像生成システム、プログラム及び情報記憶媒体は、
前記２次元近似オブジェクト変更手段が、
第１のオブジェクト又は第２のオブジェクトと仮想カメラ又はプレーヤキャラクタとの距離に応じて第１のオブジェクト又は第２のオブジェクトの２次元近似オブジェクトの頂点数を変化させることを特徴とする。
【００３８】
（１２）また本発明に係る画像生成システム、プログラム及び情報記憶媒体は、
前記２次元近似オブジェクト変更手段が、
オブジェクト空間の天候（雨、霧、もや）や視界状況又は応じて前記２次元近似オブジェクトの頂点数を変化させることを特徴とする。
【００３９】
ここにおいてオブジェクト空間の天候とは、例えば晴れ、雨、霧、もや等であり、天候が悪い場合には前記２次元近似オブジェクトの頂点数を減らして、簡易な補正やヒットチェックを行うようにしてもよい。
【００４０】
（１３）また本発明に係る画像生成システム、プログラム及び情報記憶媒体は、
前記２次元近似オブジェクト変更手段が、
第１のオブジェクト又は第２のオブジェクトの視認性に応じて前記２次元近似オブジェクトの頂点数を変化させることを特徴とする。
【００４１】
【発明の実施の形態】
以下、本発明の好適な実施形態について図面を用いて説明する。
【００４２】
なお、以下に説明する本実施形態は、特許請求の範囲に記載された本発明の内容を何ら限定するものではない。また本実施形態で説明される構成の全てが本発明の解決手段として必須であるとは限らない。
【００４３】
１．  構成
図１に、本実施形態の画像生成システム（例えばゲームシステム）の機能ブロック図の一例を示す。
【００４４】
なお同図において本実施形態は、少なくとも処理部１００を含めばよく（或いは処理部１００と記憶部１７０、或いは処理部１００と記憶部１７０と情報記憶媒体１８０を含めばよく）、それ以外のブロック（例えば操作部１６０、表示部１９０、音出力部１９２、携帯型情報記憶装置１９４、通信部１９６）については、任意の構成要素とすることができる。
【００４５】
ここで処理部１００は、システム全体の制御、システム内の各ブロックへの命令の指示、ゲーム処理、画像処理、又は音処理などの各種の処理を行うものであり、その機能は、各種プロセッサ（ＣＰＵ、ＤＳＰ等）、或いはＡＳＩＣ（ゲートアレイ等）などのハードウェアや、所与のプログラム（ゲームプログラム）により実現できる。
【００４６】
操作部１６０は、プレーヤが操作データを入力するためのものであり、その機能は、レバー、ボタン、筐体などのハードウェアにより実現できる。
【００４７】
記憶部１７０は、メインメモリ（主記憶部等）１７２やフレームバッファ（描画バッファ等）１７４等を含み、処理部１００や通信部１９６などのワーク領域となるもので、その機能はＲＡＭなどのハードウェアにより実現できる。
【００４８】
情報記憶媒体（コンピュータにより使用可能な記憶媒体）１８０は、プログラムやデータなどの情報を格納するものであり、その機能は、光ディスク（ＣＤ、ＤＶＤ）、光磁気ディスク（ＭＯ）、磁気ディスク、ハードディスク、磁気テープ、或いはメモリ（ＲＯＭ）などのハードウェアにより実現できる。処理部１００は、この情報記憶媒体１８０に格納される情報に基づいて本発明（本実施形態）の種々の処理を行う。即ち情報記憶媒体１８０には、本発明（本実施形態）の手段（特に処理部１００に含まれるブロック）を実行するための情報（プログラム或いはデータ）が格納される。
【００４９】
なお、情報記憶媒体１８０に格納される情報の一部又は全部は、システムへの電源投入時等に記憶部１７０に転送されることになる。また情報記憶媒体１８０に記憶される情報は、本発明の処理を行うためのプログラム、画像データ、音データ、表示物の形状データ、テーブルデータ、リストデータ、本発明の処理を指示するための情報、その指示に従って処理を行うための情報等の少なくとも１つを含むものである。
【００５０】
表示部１９０は、本実施形態により生成された画像を出力するものであり、その機能は、ＣＲＴ、ＬＣＤ、或いはＨＭＤ（ヘッドマウントディスプレイ）などのハードウェアにより実現できる。
【００５１】
音出力部１９２は、本実施形態により生成された音を出力するものであり、その機能は、スピーカなどのハードウェアにより実現できる。
【００５２】
携帯型情報記憶装置１９４は、プレーヤの個人データやセーブデータなどが記憶されるものであり、この携帯型情報記憶装置１９４としては、メモリカードや携帯型ゲーム装置などを考えることができる。
【００５３】
通信部１９６は、外部（例えばホスト装置や他の画像生成システム）との間で通信を行うための各種の制御を行うものであり、その機能は、各種プロセッサ、或いは通信用ＡＳＩＣなどのハードウェアや、プログラムなどにより実現できる。
【００５４】
なお本発明（本実施形態）の手段を実行するためのプログラム或いはデータは、ホスト装置（サーバ）が有する情報記憶媒体からネットワーク及び通信部１９６を介して情報記憶媒体１８０に配信するようにしてもよい。このようなホスト装置（サーバ）の情報記憶媒体の使用も本発明の範囲内に含まれる。
【００５５】
処理部１００は、ゲーム処理部１１０、交差部分検出処理部（シャドーボリューム処理部）１２０、画像生成部１３０、音生成部１５０を含む。
【００５６】
ここでゲーム処理部１１０は、コイン（代価）の受け付け処理、各種モードの設定処理、ゲームの進行処理、選択画面の設定処理、オブジェクト（１又は複数のプリミティブ面）の位置や回転角度（Ｘ、Ｙ又はＺ軸回りの回転角度）を求める処理、オブジェクトを動作させる処理（モーション処理）、視点の位置（仮想カメラの位置）や視線角度（仮想カメラの回転角度）を求める処理、マップオブジェクトなどのオブジェクトをオブジェクト空間へ配置する処理、ヒットチェック処理、ゲーム結果（成果、成績）を演算する処理、複数のプレーヤが共通のゲーム空間でプレイするための処理、或いはゲームオーバ処理などの種々のゲーム処理を、操作部１６０からの操作データや、携帯型情報記憶装置１９４からの個人データ、保存データや、ゲームプログラムなどに基づいて行う。
【００５７】
ゲーム処理部１１０は、２次元オブジェクト生成部１１２，線分交差判定処理部１１４、第１の位置補正処理部１１６、第２の位置補正処理部１２０、位置再補正処理部１２２、２次元オブジェクト変更処理部１２４、最終位置補正処理部１２６とを含む。
【００５８】
２次元オブジェクト生成部１１２は，オブジェクト空間における第１のオブジェクトと第２のオブジェクトを２次元平面に投影し、投影された第１のオブジェクト及び第２のオブジェクトをそれぞれ多角形で近似して第１のオブジェクト及び第２のオブジェクトの２次元近似オブジェクトを生成する処理を行う。
【００５９】
線分交差判定処理部１１４は、第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの各辺について線分交差判定を行い、判定結果に基づき、第１のオブジェクトと第２のオブジェクトの交差の有無を判定する処理を行うようにしてもよい。
【００６０】
また第１のオブジェクトの２次元近似オブジェクトの各頂点の移動軌跡と第２のオブジェクトの２次元近似オブジェクトの辺について線分交差判定を行い、判定結果に基づき、第１のオブジェクトと第２のオブジェクトの交差の有無を判定する処理を行うようにしてもよい。
【００６１】
第１の位置補正処理部１１６は、第１のオブジェクトと第２のオブジェクトが交差している場合に、第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの代表点を結ぶ方向ベクトルをもとめ、第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの重複エリアに基づき、第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの重複距離を決定し、決定した重複距離にもとづいて、両オブジェクトを引き離すために使用する補正距離を求め、前記補正距離及び前記方向ベクトルにもとづきオブジェクト空間における第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を補正する処理を行う。
【００６２】
また前記第１のオブジェクトの２次元近似オブジェクトの頂点から前記方向ベクトルに平行な直線を引いて、前記第１のオブジェクトの２次元近似オブジェクトの内部において前記第２のオブジェクトの２次元近似オブジェクトを構成する辺と交わる交点を求め当該交点と頂点の距離と、前記第２のオブジェクトの２次元近似オブジェクトの頂点から前記方向ベクトルに平行な直線を引いて、第２のオブジェクトの２次元近似オブジェクトの内部において第１のオブジェクトの２次元近似オブジェクトを構成する辺と交わる交点とをもとめ当該交点と頂点の距離とをもとめ、最も長い距離に基づき前記重複距離を決定するようにしてもよい。
【００６３】
第２の位置補正処理部１２０は、時刻ｔからｔ＋Δｔにおける第１のオブジェクトの２次元近似オブジェクトの各頂点の移動軌跡と第２のオブジェクトの２次元近似オブジェクトが交差している場合に、交点から時刻ｔ＋Δｔの第１のオブジェクトの２次元近似オブジェクトの頂点までの距離である重複距離にもとづいて、両オブジェクトを引き離すために使用する補正距離を求め、前記補正距離及び前記移動軌跡にもとづきオブジェクト空間における第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を補正する処理を行う。
【００６４】
位置再補正処理部１２２は、前記補正距離に基づき補正された位置に配置された第１のオブジェクトの２次元近似オブジェクトと第２のオブジェクトの２次元近似オブジェクトの各辺について線分交差判定を行い、交差している場合には、交差している第２のオブジェクトの２次元近似オブジェクトの頂点を特定し、当該頂点と第１のオブジェクトの２次元近似オブジェクトの距離に基づき、両オブジェクトを引き離すために使用する再補正距離を求め、当該再補正距離にもとづきオブジェクト空間における第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を再度補正する処理を行う。
【００６５】
２次元オブジェクト変更処理部１２４は、ゲーム状況に応じて、第１のオブジェクト及び第２のオブジェクトの少なくとも一方の２次元近似オブジェクトの頂点数を変化させる処理を行う。
【００６６】
また第１のオブジェクト又は第２のオブジェクトと仮想カメラ又はプレーヤキャラクタとの距離に応じて第１のオブジェクト又は第２のオブジェクトの２次元近似オブジェクトの頂点数を変化させるようにしてもよい。
【００６７】
またオブジェクト空間の天候や視界状況又は応じて前記２次元近似オブジェクトの頂点数を変化させるようにしてもよい。
【００６８】
また第１のオブジェクト又は第２のオブジェクトの視認性に応じて前記２次元近似オブジェクトの頂点数を変化させるようにしてもよい。
【００６９】
最終位置補正処理部１２６は、位置再補正処理後の第１のオブジェクトの２次元オブジェクトと第２のオブジェクトの２次元オブジェクトとの交差判定を行い、どれか１点でも交差すれば、第２のオブジェクトの２次元オブジェクトの法線方向について第１のオブジェクトの２次元オブジェクトとの距離を計算し、当該距離に基づいて再度第１のオブジェクト及び第２のオブジェクトの少なくとも一方の位置を補正する。
【００７０】
画像生成部１３０は、ゲーム処理部１１０からの指示等にしたがって各種の画像処理を行い、例えばオブジェクト空間内で仮想カメラ（視点）から見える画像を生成して、表示部１９０に出力する。
【００７１】
音生成部１５０は、ゲーム処理部１１０からの指示等にしたがって各種の音処理を行い、ＢＧＭ、効果音、又は音声などの音を生成し、音出力部１９２に出力する。
【００７２】
なお、ゲーム処理部１１０、画像生成部１３０、音生成部１５０の機能は、その全てをハードウェアにより実現してもよいし、その全てをプログラムにより実現してもよい。或いは、ハードウェアとプログラムの両方により実現してもよい。
【００７３】
画像生成部１３０は、ジオメトリ処理部（３次元演算部）１３２、描画部（レンダリング部）１４０を含む。
【００７４】
ここで、ジオメトリ処理部１３２は、座標変換、クリッピング処理、透視変換、或いは光源計算などの種々のジオメトリ処理（３次元演算）を行う。そして、本実施形態では、ジオメトリ処理後（透視変換後）のオブジェクトデータ（オブジェクトの頂点座標、頂点テクスチャ座標、或いは輝度データ等）は、記憶部１７０の主記憶部１７２に格納されて、保存される。
【００７５】
描画部１４０は、ジオメトリ処理後（透視変換後）のオブジェクトデータと、記憶部１７０に記憶されるテクスチャとに基づいて、オブジェクトを描画バッファ１７４に描画する。これにより、オブジェクトが移動するオブジェクト空間において、仮想カメラ（視点）から見える画像が描画（生成）されるようになる。
【００７６】
なお、本実施形態の画像生成システムは、１人のプレーヤのみがプレイできるシングルプレーヤモード専用のシステムにしてもよいし、このようなシングルプレーヤモードのみならず、複数のプレーヤがプレイできるマルチプレーヤモードも備えるシステムにしてもよい。
【００７７】
また複数のプレーヤがプレイする場合に、これらの複数のプレーヤに提供するゲーム画像やゲーム音を、１つの端末を用いて生成してもよいし、ネットワーク（伝送ライン、通信回線）などで接続された複数の端末を用いて生成してもよい。
【００７８】
２．  本実施の形態の適用例
２．１  車体ヒットチェックルーチンの概要
以下、第１のオブジェクト及び第２のオブジェクトが車（移動オブジェクトの一例）や壁（静止オブジェクトの一例）である場合を例にとり説明するがこれに限られない。
【００７９】
図２は、本実施の形態のヒットチェックの概要について説明するための図である。
【００８０】
本実施の形態では第１のオブジェクト（例えばプレーヤカー）と第２のオブジェクト（例えば敵車）が衝突したかどうかを判定し、衝突していたなら重複している部分を押し戻す補正（衝突後の動きを表すリアクションデータの計算）を行う。
【００８１】
まずヒットチェックにかかるオブジェクトの外形線分データ（オブジェクトの２次元オブジェクトに関するデータ）を取得する（ステップＳ１０）。
【００８２】
次に取得したオブジェクトの外形線分データを用いて第１のオブジェクト（例えばプレーヤカー）と第２のオブジェクト（例えば敵車）の簡易ヒットチェックを行う（ステップＳ２０）。
【００８３】
簡易ヒットチェックでヒットが検出された場合には、取得したオブジェクトの外形線分データを用いて第１のオブジェクト（例えばプレーヤカー）と第２のオブジェクト（例えば敵車）のヒットチェックを行う（ステップＳ３０）。
【００８４】
ヒットしたかどうかの判定については簡易ヒットチェック及び通常のヒットチェックの２種類実行し、ヒットしないことを確認した時点で終了する。
【００８５】
ここで例えば第１のオブジェクト又は第２のオブジェクトである車の１フレーム間の移動量が車体の大きさを超えてしまうと、車体をすり抜けてしまい正しく判定できない場合があるので、速度をチェックし、速すぎる場合はチェックポイントを複数に分けてすり抜けが起こらないようにすることが好ましい。
【００８６】
そしてヒットチェックでヒットが検出された場合には、ヒット点を特定し（ステップＳ４０）、リアクションデータを作成する（ステップＳ５０）。
【００８７】
２．２  ２次元オブジェクト（外形線分データ）の生成処理
２次元オブジェクト生成部が行う２次元オブジェクト（外形線分データ）の生成の処理の一例について説明する。
【００８８】
本実施の形態では複雑な形状の車体を、２次元平面に投影して凸型多角形に形状を近似した２次元オブジェクトを用いてヒットチェックを行う。本実施の形態ではヒットチェックはｘｚ平面上で行うので、ｙ座標は必要ない。また２次元オブジェクトは例えば８角形等の長方形（正方形も含む）以外の多角形にしてもよい。オブジェクトの種類（例えば車種）に応じて適当な多角形の２次元オブジェクトを生成するようにしてもよい。
【００８９】
また同じオブジェクトについても、ゲーム状況に応じて生成する２次元オブジェクトの頂点数（角数）を変更するようにしてもよい。
【００９０】
図３（Ａ）（Ｂ）は、オブジェクトの２次元オブジェクト（外形線分データ）の一例を示した図である。
【００９１】
図３（Ａ）は車などのオブジェクトの２次元オブジェクト（外形線分データ）を示したものである。２０２は車などのオブジェクトを２次元平面に投影したときの形状であり、２０４は、当該オブジェクト２０２の２次元オブジェクト（外形線分データ）である。
【００９２】
図３（Ｂ）は壁などの凹凸のあるオブジェクトの２次元オブジェクト（外形線分データ）を示したものである。２０６は壁などのオブジェクトを２次元平面に投影したときの形状であり、２０８は、当該オブジェクト２０６の２次元オブジェクト（外形線分データ）である。
【００９３】
このように本実施の形態では、オブジェクトを２次元平面に投影したときの形状に近似する多角形を２次元近似オブジェクトとして生成する。なお２次元近似オブジェクトは閉じた多角形でもよいし、開いた多角形でもよい。
【００９４】
また２次元近似オブジェクトを閉じた多角形として生成して、その一部の辺についてのみ使用するようにしてもよい。
【００９５】
図４は、オブジェクトの２次元オブジェクト（外形線分データ）のデータの内容について説明するための図である。
【００９６】
オブジェクトの２次元オブジェクトとして、オブジェクトのモデル作成の際に２次元平面に投影したオブジェクト（例えば車体形状）を近似した多角形を作成する。ここで頂点Ｖ０〜Ｖ７を順番に繋げば多角形が形成されるように作成するとよい（頂点は左回りに配置）。
【００９７】
２次元オブジェクトを特定するために必要なデータ（外形線分データ）は、例えば、頂点数、頂点座標（例えば外接円の中心（又は車体の重心）からの相対座標）、頂点の成す角度θ、重心Ｇから最も遠い点までの距離ｌ（簡易ヒットチェックに使用）等である。
【００９８】
なおプレーヤカーのヒットチェックは、細かな形状の違いやリアクションに変化を持たせるために２次元オブジェクトの頂点数（角数）をおおくするようにしてもよいし、コンピュータカー同士のヒットチェックや、コンピュータカーと壁とのヒットチェックに精度はそれほど要求されないので２次元オブジェクトの頂点数（角数）を減らすようにしても良い。
【００９９】
このように、プレーヤカーの関わらないヒットチェック用として、新たに頂点数のより少ない２次元オブジェクト（長方形など）を用意することにより処理を軽量化することが出来る。ヒットチェックは車体線分データの各線分ごとに行っているので、頂点数が減少すればその分処理は軽くなるからである。
【０１００】
また１つのオブジェクトについても、ゲーム状況に応じて２次元オブジェクトの頂点数を変化させて、ゲーム状況に応じた処理負荷の調整を行うようにしてもよい。
【０１０１】
頂点のなす角度θは、頂点の両端の線分が成す角度であり、角度生成の方法としては、例えば頂点の座標データをもとに角度を計算（コンバート時に生成）するようにしてもよい。
【０１０２】
頂点の成す角度θは、衝突後のリアクションデータを生成するために用いる。頂点ｉの角度θｉは、例えば図５に示すように、ｉ番目とｉ−１番目の頂点を結んだ線分を基準として、ｉ番目とｉ＋１番目を結んだ線分との成す角度を求めるようにしてもよい。
この角度は「どれだけその頂点が鋭角か？」を表すデータで、０°〜１８０°（０〜π）までの値をとる。
【０１０３】
２．３  簡易ヒットチェック
全ての敵車に対して厳密なヒットチェックを行っていては処理に時間がかかってしまうので、簡単なチェックによりヒットチェックを取る敵車を限定することが望ましい。
【０１０４】
例えば自車、敵車の重心より一番遠い部分の距離の和を計算し、２車の重心間の距離がそれより大きなものは絶対にヒットしないので除外し、それ以外の敵車に対して厳密なヒットチェックを行うようにしてもよい。車の重心からの最大距離は、あらかじめデータ化しておくようにしてもよい。
【０１０５】
２．４  ２次元オブジェクトを用いたヒットチェック
オブジェクト（例えば車体）の形状を近似した２次元オブジェクト（外形線分データ）を設定し、それを用いて２つのオブジェクト（２車）がヒットしたかどうかをチェックする処理について説明する。
【０１０６】
２次元オブジェクトの外形線分データとして、２次元オブジェクトの各頂点の座標、鋭角度情報（リアクションデータを生成するときに使用）などのパラメータも持つ。
【０１０７】
そして２車の外形線分データの線分毎に交差チェックを行い、１組でも交わるものがあればヒットしたとみなす。ヒットした場合は各頂点について２次元オブジェクトのめり込んだ距離を算出し（詳細は後述）、もっとも距離の長かった頂点をヒット点とする。２車の外形線分データの線分の全ての組み合わせについてチェックし、最終的に求めたヒット点に基づき位置を補正する。
【０１０８】
２．５  線分交差判定処理
ここで線分交差判定処理部が行う線分交差判定処理の一例について説明する。
【０１０９】
２本の線分が交差するかどうかの判別方法として、図６（Ａ）に示すように線分ＡＢの頂点Ａ，Ｂが、線分ＣＤの両側に位置し、かつ線分ＣＤの頂点Ｃ，Ｄが、線分Ａ，Ｂの両側に位置するとき２本の線分は交差するが、図６（Ｂ）（Ｃ）のような場合には２本の線分は交差しない。言い換えれば点Ａ，Ｂが、点Ｃ，Ｄを通る直線を境界とした領域の両側に位置し，かつ点Ｃ，Ｄが点Ａ，Ｂを通る直線を境界とした領域の両側に位置するとき、２本の線分は交差する。
【０１１０】
ここで点Ａ，Ｂを通る直線（境界線Ｌ１）をｙ＝ａｘ＋ｂとすると、それぞれの領域をｙ＜ａｘ＋ｂ、ｙ＞ａｘ＋ｂと表すことができ、境界線の方程式にＸ，Ｙを代入したときの値が正か負かによって領域を判別することができる。従って点Ｃ，Ｄの座標値を代入し、得られた答えの積が０または負の値（０のとき頂点は線上に存在する）であれば２線分は交差するといえる．
Ａ，Ｂ，Ｃ，Ｄの座標値をそれぞれＡ（ｘ１，ｙ１）、Ｂ（ｘ２，ｙ２）、Ｃ（ｘ３，ｙ３）、Ｄ（ｘ４，ｙ４）、線分ＡＢを通る直線をｙ＝ａｘ＋ｂとする。
ここで、ａは傾きなので、以下の式が成り立つ。
【０１１１】
【数１】
2004334802.tif 000003
また、ｂは直線のｙ軸との交点なので、以下の式が成り立つ。
【０１１２】
【数２】
2004334802.tif 000004
従って点Ａ，Ｂを通る直線（境界線Ｌ１）をｙ＝ａｘ＋ｂは以下の式で表すことが出来る。
【０１１３】
【数３】
2004334802.tif 000005
ここで除算は誤差の原因となるので両辺に（ｘ１−ｘ２）をかけ、さらにまとめると以下の式となる。
【０１１４】
【数４】
2004334802.tif 000006
この式に、頂点Ｃ，Ｄの値を代入することにより頂点Ｃ，Ｄが存在する領域を調べることができる。
【０１１５】
【数５】
2004334802.tif 000007
【０１１６】
ここで、ｔｃ×ｔｄ≦０であればＣ，Ｄが異なる領域に存在しているといえるので、線分ＡＢと線分ＣＤは交差しているといえる。
【０１１７】
同様に頂点Ｃ，Ｄを通る直線の式に頂点Ａ，Ｂの値を代入し、得られた値の積が０以下であれば、線分ＡＢと線分ＣＤは交差しているといえる。
【０１１８】
次に車体の内包チェックについて説明する。
【０１１９】
線分毎の交差チェックでは、図８に示すように一方の２次元オブジェクト２６０に他方の２次元オブジェクト２５０が入り込んだ場合に検知できない。このため、線分毎の交差チェックでヒットしなかった場合は各線分と重心を用いて内包チェックを行う必要がある。
【０１２０】
例えば各線分ベクトルと重心までのベクトルについて内積を求め、全ての計算結果が正ならば他方に２次元オブジェクトの重心が一方の２次元オブジェクトの内側にあると判定でき、この場合一方の２次元オブジェクトが他方の２次元オブジェクトを内包しているといえる。
【０１２１】
この計算方法を使う場合、全ての２次元オブジェクト（外形線分データ）の頂点リストの順番を、ベクトルが右（左）周りに繋がるように作成しておくとよい。
【０１２２】
図９は内包判定の簡易チェック方法について説明するための図である。２７０は第１のオブジェクトの２次元オブジェクトであり、２７２は第１のオブジェクトの２次元オブジェクトの重心であり、２７４は第１のオブジェクトの２次元オブジェクトの外接円（重心を中心として重心から最も遠い頂点までの距離を半径とする円）である。また２８０は第２のオブジェクトの２次元オブジェクトであり、２８２は第２のオブジェクトの２次元オブジェクトの重心である。また２９０は第３のオブジェクトの２次元オブジェクトであり、２９２は第３のオブジェクトの２次元オブジェクトの重心である。
【０１２３】
またｄ１は第１のオブジェクトの２次元オブジェクトの重心２７２と第２のオブジェクトの２次元オブジェクトの重心２８２の距離を示しており、ｄ２は第１のオブジェクトの２次元オブジェクトの重心２７２と第３のオブジェクトの２次元オブジェクトの重心２９２の距離を示している。
【０１２４】
内包判定の簡易チェック方法としては、重心間の距離（図９ではｄ１，ｄ２）が内包するオブジェクトの２次元オブジェクト（図９では、２７０）の最長距離（図９では第１のオブジェクト２７０の外接円２７４の半径）よりも大きい場合（図９ではｄ２のケース）は、内包している可能性がないとして内包チェックの対象外として、チェック対象を限定する。
【０１２５】
図１０は、線分交差判定処理に関するフローチャート図である。
【０１２６】
まず敵車（第２のオブジェクト）の２次元オブジェクトの頂点データを自車（第１のオブジェクト）の座標系に変換する（ステップＳ１１０）。
【０１２７】
自車（第１のオブジェクト）及び敵車（第２のオブジェクト）の２次元オブジェクトの頂点データより自車（第１のオブジェクト）及び敵車（第２のオブジェクト）の２次元オブジェクトの線分データを算出する（ステップＳ１２０）。ここで２次元オブジェクトの線分データとは２次元オブジェクトの各辺の頂点座標等の線分公差判定に必要な情報を含む。
【０１２８】
次に自車（第１のオブジェクト）の２次元オブジェクトの線分に対する敵車（第２のオブジェクト）の２次元オブジェクトの頂点の領域を調べる（ステップＳ１３０）。
【０１２９】
図７（Ａ）（Ｂ）で説明したように、自車（第１のオブジェクト）の２次元オブジェクトの２頂点Ａ（ｘ１’，ｙ１’）、Ｂ（ｘ２’，ｙ２’）を通る直線で２領域に分割し、敵車（第２のオブジェクト）の２次元オブジェクトの線分の２頂点Ｃ（ｘ３’，ｙ３’）、Ｄ（ｘ４’，ｙ４’）がいずれの領域に存在するか調べる。例えば前記（５−Ａ）（５−Ｂ）式のＡ（ｘ１，ｙ１）、Ｂ（ｘ２，ｙ２）に自車（第１のオブジェクト）の２次元オブジェクトの２頂点Ａ（ｘ１’，ｙ１’）、Ｂ（ｘ２’，ｙ２’）のデータを代入して、前記（５−Ａ）（５−Ｂ）式のＣ（ｘ３，ｙ３）、Ｄ（ｘ４，ｙ４）に、及び敵車（第２のオブジェクト）の２次元オブジェクトの線分の２頂点Ｃ（ｘ３’，ｙ３’）、Ｄ（ｘ４’，ｙ４’）のデータを代入して、ｔｃ×ｔｄ≦０であるか否か調べるようにしてもよい。
【０１３０】
そして敵車（第２のオブジェクト）の２次元オブジェクトの線分の２頂点が別々の領域に存在する場合には、敵車（第２のオブジェクト）の２次元オブジェクトの線分に対する自車（第１のオブジェクト）の２次元オブジェクトの頂点の領域を調べる（ステップＳ１５０，Ｓ１６０）。図７（Ａ）（Ｂ）で説明したように、敵車（第２のオブジェクト）の２次元オブジェクトの線分の２頂点Ｃ（ｘ３，ｙ３）、Ｄ（ｘ４，ｙ４）を通る直線で２領域に分割し、自車（第１のオブジェクト）の２次元オブジェクトの２頂点Ａ（ｘ１，ｙ１）、Ｂ（ｘ２，ｙ２）がいずれの領域に存在するか調べる。例えば前記（５−Ａ）（５−Ｂ）式のＡ（ｘ１，ｙ１）、Ｂ（ｘ２，ｙ２）、に敵車（第２のオブジェクト）の２次元オブジェクトの線分の２頂点Ｃ（ｘ３’，ｙ３’）、Ｄ（ｘ４’，ｙ４’）のデータを代入して、前記（５−Ａ）（５−Ｂ）式のＣ（ｘ３，ｙ３）、Ｄ（ｘ４，ｙ４）に、自車（第１のオブジェクト）の２次元オブジェクトの２頂点Ａ（ｘ１’，ｙ１’）、Ｂ（ｘ２’，ｙ２’）のデータを代入して、ｔｃ×ｔｄ≦０であるか否か調べるようにしてもよい。
【０１３１】
そして自車（第１のオブジェクト）の２次元オブジェクトの２頂点が別々の領域に存在する場合にはヒットしたと判断する（ステップＳ１６０，Ｓ１７０）。
【０１３２】
敵車（第２のオブジェクト）の２次元オブジェクトの線分の２頂点が同じ領域に存在する場合又は自車（第１のオブジェクト）の２次元オブジェクトの線分の２頂点が同じ領域に存在する場合には、すべての線分について処理を終わっていない場合には、ステップＳ１３０に戻り自車（第１のオブジェクト）の次の線分についてステップＳ１３０〜Ｓ１８０の処理を繰り返す（ステップＳ１４０、Ｓ１６０，Ｓ１８０）。
【０１３３】
すべての線分について処理を終わっていない場合には、内包チェックを行う（ステップＳ１９０）。内包チェックは、例えば図８、図９で説明した処理を行うようにしてもよい。
【０１３４】
そして内包チェックにより内包状態を検出した場合には、ヒットしたと判断する（ステップＳ１９０、Ｓ１７０）。
【０１３５】
また内包チェックにより内包状態を検出しなかった場合には、ヒットしていないと判断する（ステップＳ１９０、Ｓ２００）。
【０１３６】
２．６  第１の位置補正処理
次に第１の位置補正処理部が行う第１の位置補正処理の一例について説明する。
【０１３７】
まずにヒット点の特定について説明する。本実施の形態では、めり込んだ車体（オブジェクト）の押し戻し補正やリアクションデータの計算を行うため、車体（オブジェクト）の衝突した点を特定する。
【０１３８】
図１１はヒット点の特定について説明するための図である。
【０１３９】
まず第１のオブジェクト（自車）の２次元オブジェクト３１０と第２のオブジェクト（敵車）の２次元オブジェクト３２０を、第１のオブジェクトの２次元オブジェクト３１０の重心３１２と第２のオブジェクトの２次元オブジェクト３２０の重心３２２を結んだ線３３０を座標軸（方向ベクトルに相当）とする空間に変換する。
【０１４０】
次に変化後の第１のオブジェクト（自車）の２次元オブジェクト３１０’と第２のオブジェクト（敵車）の２次元オブジェクト３２０’について、第１のオブジェクト（自車）の２次元オブジェクトの各頂点（例えば３１４’）より重心を結んだ線３３０’に平行な直線（例えば３１６’）を引き、第２のオブジェクト（敵車）の２次元オブジェクト３２０’と交差する点３１８’を割り出す。
【０１４１】
次に第２のオブジェクト（敵車）の２次元オブジェクト３２０’の頂点についても、同様の処理を行う。すなわち第２のオブジェクト（敵車）の２次元オブジェクトの各頂点（例えば３２４’）より重心を結んだ線３３０’に平行な直線（例えば３２６’）を引き、  第１のオブジェクト（自車）の２次元オブジェクト３１０’と交差する点３２８’を割り出す。
【０１４２】
次に頂点と線分の交点との距離が最も遠い点をヒット点とする。例えば線分３１６’が最も長い場合には３１４’と３１８’をヒット点とする。このヒット点間の距離が重複距離に相当する。
【０１４３】
頂点からの平行線（ｚ＝ａ）と線分の交差判定については以下のようにして行うようにしてもよい。
【０１４４】
重心を結ぶ線をｘ軸（ｚ＝０）として座標変換した場合、まず２次元オブジェクトの頂点のｚ座標を調べ、線分の両端のＺ座標間に、ａがなければ平行線ｚ＝ａと交わらないのでチェックしない。  交わることが分かったものについては、平行線のｚ座標は一定なので、線分の傾きによって交点を求めることができる。
【０１４５】
図１２はヒット点特定処理の流れについて説明するためのフローチャート図である。ここで第１のオブジェクトの２次元オブジェクトの外形線分データと第２のオブジェクトの２次元オブジェクトの外形線分データが入力され、ヒット点座標と位置補正データが出力される。
【０１４６】
まず第１のオブジェクトの２次元オブジェクトの重心と第２のオブジェクト（敵車）の２次元オブジェクトと重心を結ぶ直線の角度を求める（ステップＳ２１０）。
【０１４７】
次に第１のオブジェクト（自車）の２次元オブジェクトの重心と第２のオブジェクト（敵車）の２次元オブジェクトを第１のオブジェクトの２次元オブジェクトの重心と第２のオブジェクトの２次元オブジェクトの重心を結んだ線を座標軸（Ｚ軸）とする空間に変換する（ステップＳ２２０）。
【０１４８】
次に第１のオブジェクトの２次元オブジェクトの頂点が、第２のオブジェクトの２次元オブジェクトの線分の範囲に入っているか否か調べる（ステップＳ２３０）。例えば第１のオブジェクトの２次元オブジェクトの頂点について頂点（ｉ）のＺ座標が、第２のオブジェクトの２次元オブジェクトの線分（ｊ）の両端のＺ座標の範囲に入っているか否か調べる。
【０１４９】
そして頂点が線分の範囲に入っていない場合には、ｊをインクリメントして第２のオブジェクトの２次元オブジェクトの次の線分（ｊ）についてステップＳ２２０の処理を行う。また第１のオブジェクトの２次元オブジェクトの頂点（ｉ）について、第２のオブジェクトの２次元オブジェクトのすべての線分についてステップＳ２３０の処理が終わった場合には、ｉをインクリメントして第１のオブジェクトの２次元オブジェクトの次の頂点（ｉ）についてステップＳ２３０の処理を行う。
【０１５０】
そして第１のオブジェクトの２次元オブジェクトの頂点が、第２のオブジェクトの２次元オブジェクトの線分の範囲に入っている場合には、線分の傾きから頂点からの平行線と線分の交点の座標を求める（ステップＳ２４０）。
【０１５１】
求めた線分の交点と頂点の距離を求め、２点の距離と重複距離データを比較し、２点の距離が最長距離データより長い場合には、２点の距離で重複距離データを更新する（ステップＳ２５０、Ｓ２６０）。
【０１５２】
第１のオブジェクトの２次元オブジェクトの頂点からの平行線と、第２のオブジェクトの２次元オブジェクトの頂点からの平行線と他方のオブジェクトの線分とについて線分交差判定が終了したら（例えばステップＳ２３０の処理）、重複距離データに基づき車両位置補正データを計算する（ステップＳ２９０）。
【０１５３】
２．７  第２の位置補正処理
次に第２の位置補正処理部が行う第２の位置補正処理の一例について説明する第１のオブジェクトが移動体（例えば車）で、第２のオブジェクトが静止物（例えば壁）である場合を例にとり、第２の位置補正処理について説明する。
【０１５４】
第１のオブジェクトの２次元オブジェクトと第２のオブジェクトである走行領域両端の壁の形状を近似した２次元オブジェクト（開いた多角形である）とのヒットチェックを行う。
【０１５５】
基本的なヒットは第１のヒットチェック処理と同様、２次元オブジェクトの線分データを用いてチェックする。それに加えて、各頂点の移動ベクトルともチェックをかけることにより、壁のすり抜けを防止する。
【０１５６】
正確、かつ確実に位置補正を行うため、段階的に補正処理を行うとよい。
【０１５７】
まず第１のオブジェクトの２次元オブジェクトの各頂点の移動ベクトルと第２のオブジェクトの２次元オブジェクトとの線分交差判定によるヒットチェックを行う。
【０１５８】
次に第１のオブジェクトの２次元オブジェクトと第２のオブジェクトの２次元オブジェクトの線分交差判定と第２のオブジェクトの２次元オブジェクトの頂点方向への押し出しを行う。
【０１５９】
次に第１のオブジェクトの２次元オブジェクトと第２のオブジェクトの２次元オブジェクトの線分交差判定と壁線分の法線方向への押し出しを行う。
【０１６０】
以上の３項目を順に適用することにより、確実に位置を補正することが出来る。
【０１６１】
図１３は、第１のオブジェクトの２次元オブジェクトの各頂点の移動ベクトルと第２のオブジェクトの２次元オブジェクトとの線分交差判定によるヒットチェックについて説明するための図である。
【０１６２】
４１０、４１０’は時刻ｔ及び時刻ｔ＋Δｔにおける第１のオブジェクトの２次元オブジェクトであり、４１１〜４１８、４１１’〜４１８’は時刻ｔ及び時刻ｔ＋Δｔにおける第１のオブジェクトの２次元オブジェクトの各頂点であり、４２１〜４２８は第１のオブジェクトの２次元オブジェクトの移動ベクトルである。４３０は第２のオブジェクトの２次元オブジェクトである。
【０１６３】
本実施の形態の第２の交差判定処理では、第１のオブジェクトの２次元オブジェクトの各頂点の移動ベクトル４２１〜４２８と第２のオブジェクトの２次元オブジェクト４３０との線分交差判定を行う。そして交差しているすべての交点について、交点から移動後の頂点までの距離（重複距離）を調べる。
【０１６４】
図１４は、重複距離について説明するための図である。
【０１６５】
移動ベクトル４２３、４２４，４２５，４２６、４２７が、第２のオブジェクトの２次元オブジェクト４３０と交差しているので、その交点４４３、４４４，４４５，４４６、４４７と、交点から移動後の頂点までの距離（重複距離）４５３、４５４，４５５，４５６、４５７を調べ、この重複距離が最も長いものをヒットした点とする。例えば図１４では重複距離４５４，４５５が最も長いのでこの重複距離に基づき位置補正を行う。
【０１６６】
２．８  位置再補正処理
次に位置再補正処理部が行う位置再補正処理の一例について説明する。
【０１６７】
図１５は位置補正処理を行った後さらに再補正が必要な場合について説明するための図である。
【０１６８】
例えば時刻ｔにおける第１のオブジェクトの２次元オブジェクト５１０が、時刻ｔ＋Δｔにおいて５２０まで移動したときに、移動ベクトル５４０と交点５４２に基づき算出された重複距離５４４が最も長い重複距離であった場合に、この重複距離に基づき、移動後の第１のオブジェクトの２次元オブジェクトを５３０の位置まで補正したとする。
【０１６９】
この場合、補正後もなお第１のオブジェクトの２次元オブジェクト５３０は、第２のオブジェクトの２次元オブジェクトにめり込んだ状態にあるため、さらに補正を施すこと（位置再補正処理）が好ましい。
【０１７０】
位置再補正処理は、第２の補正処理による補正後の各オブジェクトの２次元オブジェクトについて交差判定を行い、第２のオブジェクトの衝突した頂点を特定し、補正を行う。
【０１７１】
図１６は、位置再補正処理について説明するための図である。
【０１７２】
まず第１のオブジェクトの２次元オブジェクト５２０の交差した辺５２２の両端の移動ベクトル５４０，５６０を補間して補正方向５７０を求める。ここで補間の割合は第１のオブジェクトの２次元オブジェクト５２０の交点からの左右の距離の割合とする。
【０１７３】
次に第２のオブジェクトの２次元オブジェクト５５０の頂点５５２から求めた補正方向５７０に線を延ばし、第１のオブジェクトの２次元オブジェクト５２０との交点５５４までの距離を求める
第２のオブジェクトの２次元オブジェクトの全てについてチェックし、最も距離の遠かった点（ヒット点）について、求めた方向・距離（例えばベクトル５７２）に基づき各オブジェクトの位置を補正する。例えば第１のオブジェクトの２次元オブジェクト５２０を、ベクトル５７２の大きさ、向きに押し戻すようにしてもよい。
【０１７４】
さらに以下に説明する最終位置補正処理を行うようにしてもよい。
【０１７５】
２．９  最終位置補正処理
次に最終位置補正処理部が行う最終位置補正処理の一例について説明する。
【０１７６】
図１７は最終位置補正処理について説明するための図である。
【０１７７】
まず、位置再補正処理後の第１のオブジェクトの２次元オブジェクト６１０と第２のオブジェクトの２次元オブジェクト６２０との交差判定を行う。
【０１７８】
そしてどれか１点でも交差すれば、第２のオブジェクトの２次元オブジェクトの法線方向６２２について第１のオブジェクトの２次元オブジェクトとの距離を計算する。
【０１７９】
そして最も距離の遠かったものをヒット点とし、位置を補正する。
【０１８０】
上記処理を第２のオブジェクトの２次元オブジェクトの全てについて行う。
【０１８１】
なお第１のオブジェクトの移動ベクトルの隙間に入り込むぐらい小さい第２のオブジェクトはさけるようにすることが好ましい。
【０１８２】
図１８は第１のオブジェクトの移動ベクトルと第２のオブジェクトのヒットチェック処理の一例について説明するためのフローチャート図である。
【０１８３】
まず第２の位置補正処理を行う（ステップＳ３１０）。
【０１８４】
次に位置再補正処理を行う（ステップＳ３２０）。
【０１８５】
第２の位置補正処理又は位置再補正処理でヒットした場合には最終位置補正処理を行う（ステップＳ３３０、Ｓ３４０）。
【０１８６】
図１９は第２の位置補正処理の一例について説明するためのフローチャート図である。
【０１８７】
まず第１のオブジェクトの２次元オブジェクトの移動ベクトルを計算する（ステップＳ４１０）。そして第１のオブジェクトの２次元オブジェクトの移動ベクトル（ｉ）と第２のオブジェクトの２次元オブジェクト（ｊ）について線分交差判定を行う（ステップＳ４２０）。
【０１８８】
ヒットしている場合には、第１のオブジェクトの２次元オブジェクトの移動ベクトル（ｉ）と第２のオブジェクトの２次元オブジェクト（ｊ）の交点から第１のオブジェクトの２次元オブジェクトの頂点までの距離を演算する（ステップＳ４２０，Ｓ４３０）。
【０１８９】
第２のオブジェクトの２次元オブジェクト（ｊ）について、第１のオブジェクトの２次元オブジェクトの移動ベクトル（ｉ）のすべてとステップＳ４２０〜Ｓ４３０の処理を終了していない場合には、ｉをインクリメントして次の移動ベクトル（ｉ）についてステップＳ４２０〜Ｓ４４０の処理を行う（ステップＳ４４０，Ｓ４５０）。
【０１９０】
また第２のオブジェクトの２次元オブジェクト（ｊ）について、第１のオブジェクトの２次元オブジェクトの移動ベクトル（ｉ）のすべてについてステップＳ４２０〜Ｓ４３０の処理を終了した場合であって、第２のオブジェクトの２次元オブジェクト（ｊ）のすべてについてステップＳ４２０〜Ｓ４４０の処理が終了していない場合には、ｊをインクリメントして次の２次元オブジェクト（ｊ）についてステップＳ４２０〜Ｓ４６０の処理を行う（ステップＳ４６０，Ｓ４７０）。
【０１９１】
また第１のオブジェクトの２次元オブジェクトの移動ベクトル（ｉ）と第２のオブジェクトの２次元オブジェクト（ｊ）のすべてについてステップＳ４２０〜Ｓ４６０の処理が終了した場合には、交点から第１のオブジェクトの２次元オブジェクトの頂点までの距離がマットも長かった頂点をヒット点として位置を補正する（ステップＳ４６０、Ｓ４８０）。
【０１９２】
図２０は、位置再補正処理の一例について説明するためのフローチャート図である。
【０１９３】
まず第１のオブジェクトの２次元オブジェクトの線分（ｉ）と第２のオブジェクトの２次元オブジェクトの線分（ｊ）について線分交差判定を行う（ステップＳ５１０）。
【０１９４】
ヒットしている場合には、第１のオブジェクトの２次元オブジェクト（ｉ）にめり込んでいる第２のオブジェクトの２次元オブジェクト（ｊ）の頂点を判定する（ステップＳ５２０）。
【０１９５】
次に第２のオブジェクトの２次元オブジェクト（ｊ）の両端の移動ベクトルと交点の位置から補正方向を決定する（ステップＳ５３０）。
【０１９６】
求めた補正方向について、第２のオブジェクトの２次元オブジェクト（ｊ）と第１のオブジェクトの２次元オブジェクトの線分（ｉ）の距離を求める（ステップＳ５４０）。
【０１９７】
第２のオブジェクトの２次元オブジェクト（ｊ）について、第１のオブジェクトの２次元オブジェクトの線分（ｉ）のすべてとステップＳ５１０〜Ｓ５４０の処理を終了していない場合には、ｉをインクリメントして次の第１のオブジェクトの２次元オブジェクトの線分（ｉ）についてステップＳ５１０〜Ｓ５４０の処理を行う（ステップＳ５５０、Ｓ５６０）。
【０１９８】
また第２のオブジェクトの２次元オブジェクト（ｊ）について、第１のオブジェクトの２次元オブジェクトの線分（ｉ）のすべてについてステップＳ５１０〜Ｓ５４０の処理を終了した場合であって、第２のオブジェクトの２次元オブジェクト（ｊ）のすべてについてステップＳ５１０〜Ｓ５５０の処理が終了していない場合には、ｊをインクリメントして次の２次元オブジェクト（ｊ）についてステップＳ５１０〜Ｓ５７０の処理を行う（ステップＳ５７０，Ｓ５８０）。
【０１９９】
また第１のオブジェクトの２次元オブジェクトの線分（ｉ）と第２のオブジェクトの２次元オブジェクト（ｊ）のすべてについてステップＳ５１０〜Ｓ５８０の処理が終了した場合には、交点から第１のオブジェクトの２次元オブジェクトの頂点までの距離がもットも長かった頂点をヒット点として位置を補正する（ステップＳ５７０、Ｓ５９０）。
【０２００】
図２１は、最終補正処理の一例について説明するためのフローチャート図である。
【０２０１】
まず第１のオブジェクトの２次元オブジェクトの線分（ｉ）と第２のオブジェクトの２次元オブジェクトの線分（ｊ）について線分交差判定を行う（ステップＳ６１０）。
【０２０２】
ヒットしている場合には、第２のオブジェクトの２次元オブジェクトの線分（ｊ）と、すべての第１のオブジェクトの２次元オブジェクトの線分（ｉ）について、第２のオブジェクトの２次元オブジェクトの線分（ｊ）の法線方向の距離を算出し（ステップＳ６４０）、最も距離の長かった頂点をヒット点として位置を補正する（ステップＳ６５０）。
【０２０３】
ヒットしていない場合、第１のオブジェクトの２次元オブジェクトの線分（ｉ）すべてについてステップＳ６１０の処理を終えるまで、ｉをインクリメントしてステップＳ６１０を行う。
【０２０４】
２次元オブジェクトの線分（ｉ）すべてについて、ステップＳ６１０の処理を終えた場合又は第２のオブジェクトの２次元オブジェクトの線分（ｊ）についてヒットがあった場合には、第２のオブジェクトの２次元オブジェクトの線分（ｊ）すべてについてステップＳ６１０〜Ｓ６３０の処理を終えるまで、ｊをインクリメントしてステップＳ６１０に戻る。
【０２０５】
４．  ハードウェア構成
次に、本実施形態を実現できるハードウェアの構成の一例について図２２を用いて説明する。
【０２０６】
メインプロセッサ９００は、ＣＤ９８２（情報記憶媒体）に格納されたプログラム、通信インターフェース９９０を介して転送されたプログラム、或いはＲＯＭ９５０（情報記憶媒体の１つ）に格納されたプログラムなどに基づき動作し、ゲーム処理、画像処理、音処理などの種々の処理を実行する。
【０２０７】
コプロセッサ９０２は、メインプロセッサ９００の処理を補助するものであり、高速並列演算が可能な積和算器や除算器を有し、マトリクス演算（ベクトル演算）を高速に実行する。例えば、オブジェクトを移動させたり動作（モーション）させるための物理シミュレーションに、マトリクス演算などの処理が必要な場合には、メインプロセッサ９００上で動作するプログラムが、その処理をコプロセッサ９０２に指示（依頼）する。
【０２０８】
ジオメトリプロセッサ９０４は、座標変換、透視変換、光源計算、曲面生成などのジオメトリ処理を行うものであり、高速並列演算が可能な積和算器や除算器を有し、マトリクス演算（ベクトル演算）を高速に実行する。例えば、座標変換、透視変換、光源計算などの処理を行う場合には、メインプロセッサ９００で動作するプログラムが、その処理をジオメトリプロセッサ９０４に指示する。
【０２０９】
データ伸張プロセッサ９０６は、圧縮された画像データや音データを伸張するデコード処理を行ったり、メインプロセッサ９００のデコード処理をアクセレートする処理を行う。これにより、オープニング画面、インターミッション画面、エンディング画面、或いはゲーム画面などにおいて、ＭＰＥＧ方式等で圧縮された動画像を表示できるようになる。なお、デコード処理の対象となる画像データや音データは、ＲＯＭ９５０、ＣＤ９８２に格納されたり、或いは通信インターフェース９９０を介して外部から転送される。
【０２１０】
描画プロセッサ９１０は、ポリゴンや曲面などのプリミティブ（プリミティブ面）で構成されるオブジェクトの描画（レンダリング）処理を高速に実行するものである。オブジェクトの描画の際には、メインプロセッサ９００は、ＤＭＡコントローラ９７０の機能を利用して、オブジェクトデータを描画プロセッサ９１０に渡すとともに、必要であればテクスチャ記憶部９２４にテクスチャを転送する。すると、描画プロセッサ９１０は、これらのオブジェクトデータやテクスチャに基づいて、Ｚバッファなどを利用した隠面消去を行いながら、オブジェクトをフレームバッファ９２２に高速に描画する。また、描画プロセッサ９１０は、αブレンディング（半透明処理）、デプスキューイング、ミップマッピング、フォグ処理、バイリニア・フィルタリング、トライリニア・フィルタリング、アンチエリアシング、シェーディング処理なども行うことができる。そして、１フレーム分の画像がフレームバッファ９２２に書き込まれると、その画像はディスプレイ９１２に表示される。
【０２１１】
サウンドプロセッサ９３０は、多チャンネルのＡＤＰＣＭ音源などを内蔵し、ＢＧＭ、効果音、音声などの高品位のゲーム音を生成する。生成されたゲーム音は、スピーカ９３２から出力される。
【０２１２】
ゲームコントローラ９４２（レバー、ボタン、筺体、パッド型コントローラ又はガン型コントローラ等）からの操作データや、メモリカード９４４からのセーブデータ、個人データは、シリアルインターフェース９４０を介してデータ転送される。
【０２１３】
ＲＯＭ９５０にはシステムプログラムなどが格納される。なお、業務用ゲームシステムの場合には、ＲＯＭ９５０が情報記憶媒体として機能し、ＲＯＭ９５０に各種プログラムが格納されることになる。なお、ＲＯＭ９５０の代わりにハードディスクを利用するようにしてもよい。
【０２１４】
ＲＡＭ９６０は、各種プロセッサの作業領域として用いられる。
【０２１５】
ＤＭＡコントローラ９７０は、プロセッサ、メモリ（ＲＡＭ、ＶＲＡＭ、ＲＯＭ等）間でのＤＭＡ転送を制御するものである。
【０２１６】
ＣＤドライブ９８０は、プログラム、画像データ、或いは音データなどが格納されるＣＤ９８２（情報記憶媒体）を駆動し、これらのプログラム、データへのアクセスを可能にする。
【０２１７】
通信インターフェース９９０は、ネットワークを介して外部との間でデータ転送を行うためのインターフェースである。この場合に、通信インターフェース９９０に接続されるネットワークとしては、通信回線（アナログ電話回線、ＩＳＤＮ）、高速シリアルバスなどを考えることができる。そして、通信回線を利用することでインターネットを介したデータ転送が可能になる。また、高速シリアルバスを利用することで、他の画像生成システムとの間でのデータ転送が可能になる。
【０２１８】
なお、本発明の各手段は、その全てを、ハードウェアのみにより実現（実行）してもよいし、情報記憶媒体に格納されるプログラムや通信インターフェースを介して配信されるプログラムのみにより実現してもよい。或いは、ハードウェアとプログラムの両方により実現してもよい。
【０２１９】
そして、本発明の各手段をハードウェアとプログラムの両方により実現する場合には、情報記憶媒体には、本発明の各手段をハードウェアを利用して実現するためのプログラムが格納されることになる。より具体的には、上記プログラムが、ハードウェアである各プロセッサ９０２、９０４、９０６、９１０、９３０等に処理を指示するとともに、必要であればデータを渡す。そして、各プロセッサ９０２、９０４、９０６、９１０、９３０等は、その指示と渡されたデータとに基づいて、本発明の各手段を実現することになる。
【０２２０】
図２３（Ａ）に、本実施形態を業務用ゲームシステムに適用した場合の例を示す。プレーヤは、ディスプレイ１１００上に映し出されたゲーム画像を見ながら、レバー１１０２、ボタン１１０４等を操作してゲームを楽しむ。内蔵されるシステムボード（サーキットボード）１１０６には、各種プロセッサ、各種メモリなどが実装される。そして、本発明の各手段を実行するための情報（プログラム或いはデータ）は、システムボード１１０６上の情報記憶媒体であるメモリ１１０８に格納される。以下、この情報を格納情報と呼ぶ。
【０２２１】
図２３（Ｂ）に、本実施形態を家庭用のゲームシステムに適用した場合の例を示す。プレーヤはディスプレイ１２００に映し出されたゲーム画像を見ながら、ゲームコントローラ１２０２、１２０４を操作してゲームを楽しむ。この場合、上記格納情報は、本体システムに着脱自在な情報記憶媒体であるＣＤ１２０６、或いはメモリカード１２０８、１２０９等に格納されている。
【０２２２】
図２３（Ｃ）に、ホスト装置１３００と、このホスト装置１３００とネットワーク１３０２（ＬＡＮのような小規模ネットワークや、インターネットのような広域ネットワーク）を介して接続される端末１３０４−１〜１３０４−ｎとを含むシステムに本実施形態を適用した場合の例を示す。この場合、上記格納情報は、例えばホスト装置１３００が制御可能な磁気ディスク装置、磁気テープ装置、メモリ等の情報記憶媒体１３０６に格納されている。端末１３０４−１〜１３０４−ｎが、スタンドアロンでゲーム画像、ゲーム音を生成できるものである場合には、ホスト装置１３００からは、ゲーム画像、ゲーム音を生成するためのゲームプログラム等が端末１３０４−１〜１３０４−ｎに配送される。一方、スタンドアロンで生成できない場合には、ホスト装置１３００がゲーム画像、ゲーム音を生成し、これを端末１３０４−１〜１３０４−ｎに伝送し端末において出力することになる。
【０２２３】
なお、図２３（Ｃ）の構成の場合に、本発明の各手段を、ホスト装置（サーバ）と端末とで分散して実行するようにしてもよい。また、本発明の各手段を実行するための上記格納情報を、ホスト装置（サーバ）の情報記憶媒体と端末の情報記憶媒体に分散して格納するようにしてもよい。
【０２２４】
またネットワークに接続する端末は、家庭用ゲームシステムであってもよいし業務用ゲームシステムであってもよい。そして、業務用ゲームシステムをネットワークに接続する場合には、業務用ゲームシステムとの間で情報のやり取りが可能であるとともに家庭用ゲームシステムとの間でも情報のやり取りが可能な携帯型情報記憶装置（メモリカード、携帯型ゲーム装置）を用いることが望ましい。
【０２２５】
なお本発明は、上記実施形態で説明したものに限らず、種々の変形実施が可能である。
【０２２６】
また、本発明のうち従属請求項に係る発明においては、従属先の請求項の構成要件の一部を省略する構成とすることもできる。また、本発明の１の独立請求項に係る発明の要部を、他の独立請求項に従属させることもできる。
【０２２７】
たとえは、本実施の形態では第１のオブジェクトが移動オブジェクト、第２のオブジェクトが地形オブジェクトで有る場合を例にとり説明したがこれに限られない。第１のオブジェクトと第２のオブジェクトの両方が移動するオブジェクトである場合でもよい。
【０２２８】
また、本発明は種々のゲーム（格闘ゲーム、シューティングゲーム、ロボット対戦ゲーム、スポーツゲーム、競争ゲーム、ロールプレイングゲーム、音楽演奏ゲーム、ダンスゲーム等）に適用できる。
【０２２９】
また本発明は、業務用ゲームシステム、家庭用ゲームシステム、多数のプレーヤが参加する大型アトラクションシステム、シミュレータ、マルチメディア端末、ゲーム画像を生成するシステムボード等の種々の画像生成システム（ゲームシステム）に適用できる。
【図面の簡単な説明】
【図１】本実施形態の画像生成システム（例えばゲームシステム）の機能ブロック図の一例である。
【図２】本実施の形態のヒットチェックの概要について説明するための図である。
【図３】図３（Ａ）（Ｂ）は、オブジェクトの２次元オブジェクト（外形線分データ）の一例を示した図である。
【図４】オブジェクトの２次元オブジェクト（外形線分データ）のデータの内容について説明するための図である。
【図５】オブジェクトの２次元オブジェクト（外形線分データ）の頂点の成す角度θについて説明するための図である。
【図６】線分交差判定処理について説明するための図である。
【図７】線分交差判定処理について説明するための図である。
【図８】車体の内包チェックについて説明するための図である。
【図９】内包判定の簡易チェック方法について説明するための図である。
【図１０】線分交差判定処理に関するフローチャート図である。
【図１１】ヒット点の特定について説明するための図である。
【図１２】ヒット点特定処理の流れについて説明するためのフローチャート図である。
【図１３】第１のオブジェクトの２次元オブジェクトの各頂点の移動ベクトルと第２のオブジェクトの２次元オブジェクトとの線分交差判定によるヒットチェックについて説明するための図である。
【図１４】重複距離について説明するための図である。
【図１５】位置補正処理を行った後さらに再補正が必要な場合について説明するための図である。
【図１６】位置再補正処理について説明するための図である。
【図１７】最終位置補正処理について説明するための図である。
【図１８】第１のオブジェクトの移動ベクトルと第２のオブジェクトのヒットチェック処理の一例について説明するためのフローチャート図である。
【図１９】第２の位置補正処理の一例について説明するためのフローチャート図である。
【図２０】位置再補正処理の一例について説明するためのフローチャート図である。
【図２１】最終補正処理の一例について説明するためのフローチャート図である。
【図２２】本実施形態を実現できるハードウェアの構成の一例を示す図である。
【図２３】図２３（Ａ）、（Ｂ）、（Ｃ）は、本実施形態が適用される種々の形態のシステムの例を示す図である。
【符号の説明】
１００  処理部
１１０  ゲーム処理部
１１２  ２次元オブジェクト生成部
１１４  線分交差判定部
１１６  第１の位置補正処理部
１２０  第２の位置補正処理部
１２２  位置再補正処理部
１２４  ２次元オブジェクト変更部
１２６  最終位置補正処理部
１３０  画像生成部
１３２  ジオメトリ処理部
１４０  描画部
１５０  音生成部
１６０  操作部
１７０  記憶部
１７２  メインメモリ（主記憶部）
１７４  フレームバッファ（描画バッファ）
１８０  情報記憶媒体
１９０  表示部
１９２  音出力部
１９４  携帯型情報記憶装置
１９６  通信部
【図１】
2004334802.tif 000008
【図２】
2004334802.tif 000009
【図３】
2004334802.tif 000010
【図４】
2004334802.tif 000011
【図５】
2004334802.tif 000012
【図６】
2004334802.tif 000013
【図７】
2004334802.tif 000014
【図８】
2004334802.tif 000015
【図９】
2004334802.tif 000016
【図１０】
2004334802.tif 000017
【図１１】
2004334802.tif 000018
【図１２】
2004334802.tif 000019
【図１３】
2004334802.tif 000020
【図１４】
2004334802.tif 000021
【図１５】
2004334802.tif 000022
【図１６】
2004334802.tif 000023
【図１７】
2004334802.tif 000024
【図１８】
2004334802.tif 000025
【図１９】
2004334802.tif 000026
【図２０】
2004334802.tif 000027
【図２１】
2004334802.tif 000028
【図２２】
2004334802.tif 000029
【図２３】
2004334802.tif 000030