３次元空間データ処理装置及びプログラム
【課題】平面多角形の形状を有する複数のポリゴンを用いて表現される３次元空間について、３次元空間上の線分とポリゴンとの交差を判定する技術に関し、交差判定に係る処理の負荷を軽減する。
【解決手段】候補選定部２２が、３次元空間上の背景オブジェクトのポリゴン及びキャラクタオブジェクトの移動線分を２次元平面に投影し、２次元平面上においてポリゴンの辺がキャラクタオブジェクトの移動線分と交差するポリゴンを選定して交差判定部２３に供給し、交差判定部２３が、候補選定部２２により選定されたポリゴンを対象にして、３次元空間上においてポリゴンの面がキャラクタオブジェクトの移動線分と交差するか否かを判定し、ポリゴンの面がキャラクタオブジェクトの移動線分と交差するポリゴン（キャラクタオブジェクトが衝突するポリゴン）を特定する。
【解決手段】候補選定部２２が、３次元空間上の背景オブジェクトのポリゴン及びキャラクタオブジェクトの移動線分を２次元平面に投影し、２次元平面上においてポリゴンの辺がキャラクタオブジェクトの移動線分と交差するポリゴンを選定して交差判定部２３に供給し、交差判定部２３が、候補選定部２２により選定されたポリゴンを対象にして、３次元空間上においてポリゴンの面がキャラクタオブジェクトの移動線分と交差するか否かを判定し、ポリゴンの面がキャラクタオブジェクトの移動線分と交差するポリゴン（キャラクタオブジェクトが衝突するポリゴン）を特定する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、平面多角形の形状を有する複数のポリゴンを用いて仮想的に表現される３次元空間について処理する技術に関し、特に、３次元の空間上の線分とポリゴンとの交差を判定する技術に関する。
【背景技術】
【０００２】
近年、平面多角形の形状を有する複数のポリゴンを用いて３次元の仮想的なゲーム空間を表現し、当該ゲーム空間内でゲームを展開する３Ｄゲームが実現されている。
このような３Ｄゲームでは、例えば、ゲーム空間内を移動する物体とゲーム空間内に存在する他の物体との衝突を判定し、これらの衝突が検出された場合に所定の画像や音響等の出力を行って、物体同士の衝突が発生したことをゲームのプレイヤに知らせることなどが行われている。このような衝突の判定では、例えば、移動する物体の移動元（始点）と移動先（終点）を結ぶ線分が、他の物体を形成するポリゴンの面を通過するかを判定する交差判定により当該線分と交差するポリゴンの有無を調べ、該当するポリゴンが存在する場合に衝突が発生したと判定される。
【０００３】
また、３Ｄゲームでは、例えば、ゲーム空間内を自律的に行動する自律キャラクタを用意してゲームの趣向性を高める工夫なども行われている。このような自律キャラクタの移動に係るルート探索用の技術としては、ナビゲーションメッシュ（Ｎａｖｉｇａｔｉｏｎ Ｍｅｓｈｅｓ）と呼ばれる技術が知られている。
ナビゲーションメッシュでは、例えば、背景やオブジェクト等を表現するためのポリゴンとは別に、キャラクタがゲーム内の場面（マップ等）を移動する際に利用する経路データを用意しておく。この経路データは、三角形ベースで構築された「道」であり、各三角形に対して隣の三角形との隣接情報を含めてあり、この経路データを用いてキャラクタが移動可能なルートの探索を行う。
ナビゲーションメッシュの詳細については、例えば、非特許文献１の「ＳＥＣＴＩＯＮ３ 人工知能」の「３．６ ナビゲーションメッシュによる３Ｄ移動とパスの発見の単純化」、非特許文献２の「ＳＥＣＴＩＯＮ３ 人工知能」の「３．７ 高速なナビゲーションメッシュ」、非特許文献３の「ＳＥＣＴＩＯＮ３ 人工知能」の「３．１ ナビゲーションメッシュによる自動的な退避場所探索」などに記載されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｍａｒｋ ＤｅＬｏｕｒａ 他、「Ｇａｍｅ ＰｒｏｇｒａｍｍｉｎｇＧｅｍｓ 日本語版」、株式会社ボーンデジタル、平成１３年６月２５日
【非特許文献２】Ｄａｎｔｅ Ｔｒｅｇｌｉａ 他、「Ｇａｍｅ ＰｒｏｇｒａｍｍｉｎｇＧｅｍｓ ３ 日本語版」、株式会社ボーンデジタル、平成１６年１２月２１日
【非特許文献３】Ｋｉｍ Ｐａｌｌｉｓｔｅｒ 他、「Ｇａｍｅ ＰｒｏｇｒａｍｍｉｎｇＧｅｍｓ ５ 日本語版」、株式会社ボーンデジタル、平成１８年９月１５日
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、例えば、プレイヤの操作入力に応じて自己キャラクタが行動するアクションゲームのように即時応答性（リアルタイム性）が要求される３Ｄゲームでは、交差判定などの処理に手間取って遅延（タイムラグ）が生じるとゲームとしての興趣性が損なわれかねないことから、処理の負荷を軽減させて即時応答性を高めることが求められている。
【０００６】
本発明は、上記のような従来の事情に鑑みなされたものであり、平面多角形の形状を有する複数のポリゴンを用いて表現される３次元空間について、３次元空間上の線分とポリゴンとの交差を判定する技術に関し、交差判定に係る処理の負荷を軽減することを目的としている。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本発明では、平面多角形の形状を有する複数のポリゴンを用いて表現される３次元空間について、３次元空間上の線分とポリゴンとの交差を判定する３次元空間データ処理装置において、選定手段が、３次元空間上の線分及びポリゴンを２次元平面に投影し、２次元平面上においてポリゴンの辺が前記線分と交差するポリゴンを選定し、特定手段が、前記選定手段により選定されたポリゴンを対象にして、３次元空間上においてポリゴンの面が前記線分と交差するポリゴンを特定する。
【０００８】
すなわち、本発明に係る３次元空間データ処理装置では、３次元空間内に存在する全てのポリゴンを対象にして、当該ポリゴンの面が線分と交差するかの交差判定を行うのではなく、３次元空間に比べて処理負担が少ない２次元平面上でポリゴンの選定を行い、当該選定により絞り込まれたポリゴンを対象にして３次元空間上で交差判定を行うことで、３次元空間上で実行する交差判定の回数を減少させている。
このように、本発明では、３次元空間上での交差判定の対象とするポリゴンを２次元平面上で効果的に絞り込むことで、交差判定に係る処理の全体的な負荷を軽減している。
【０００９】
また、一構成例として、始点と終点が定められた線分について、前記選定手段が、２次元平面において、前記線分の始点を内部に有するポリゴンの各辺について、前記線分と交差し且つ当該辺に対して前記線分の終点が外側にあるという条件を満たすかを判定する処理を行い、当該条件を満たす辺を共有する他のポリゴンの各辺について前記処理を行うことを、前記条件を満たす辺を有しないポリゴンが検出されるまで繰り返し、前記処理の対象となったポリゴンを選定するように構成すればよい。
【００１０】
このような構成によれば、線分とポリゴンの各辺との交差の判定を、線分の始点から終点に向かう一方向の処理を１回行うだけで済ませることができ、該当するポリゴンの選定を効率的に行うことができる。
なお、上記の構成例において、前記選定手段が、辺を共有するポリゴン同士を関連付けたリンクデータを用いて、前記条件を満たす辺を共有する他のポリゴンを特定するように構成すれば、辺を共有する他のポリゴンの特定を簡易に行うことができる。
【００１１】
また、本発明は、上記のような３次元空間データ処理装置としてではなく、当該装置をコンピュータにより実現するためのプログラム（或いは当該プログラムをコンピュータ読み取り可能に記憶した記憶媒体）としても実現することができ、当該装置やプログラムなどにより実施される方法として把握することもできる。
【発明の効果】
【００１２】
本発明によれば、３次元空間内に存在する全てのポリゴンを対象にして、当該ポリゴンの面が線分と交差するかの交差判定を行うのではなく、３次元空間に比べて処理負担が少ない２次元平面上でポリゴンの選定を行い、当該選定により絞り込まれたポリゴンを対象にして３次元空間上で交差判定を行うため、３次元空間上で実行する交差判定の回数が減少される。すなわち、３次元空間上での交差判定の対象とするポリゴンが２次元平面上で効果的に絞り込まれるので、交差判定に係る処理の全体的な負荷が軽減される。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施形態に係るゲーム装置のハードウェア構成を例示する図である。
【図２】本発明の一実施形態に係るゲーム装置の機能ブロックを例示する図である。
【図３】本発明の一実施形態に係るゲーム装置による衝突判定を説明する図である。
【図４】本発明の一実施形態に係るゲーム装置による衝突判定を説明する図である。
【図５】本発明の一実施形態に係るゲーム装置による衝突判定を説明する図である。
【図６】本発明の一実施形態に係るゲーム装置により候補選定処理の処理フローを例示する図である。
【図７】本発明の一実施形態に係るゲーム装置による候補選定処理を説明する図である。
【図８】本発明の一実施形態に係るゲーム装置におけるポリゴンのデータを例示する図である。
【発明を実施するための形態】
【００１４】
本発明の一実施形態について図面を参照して説明する。
図１には、本発明の一実施形態に係る３次元空間データ処理装置として動作するゲーム装置のハードウェア構成を例示してある。
本例のゲーム装置は、各種演算処理を行うＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｃｅｓｓｉｎｇ Ｕｎｉｔ）１１、ＣＰＵ１１の作業領域となるＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）１２、基本的な制御プログラムを記録したＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）１３、他の装置と有線又は無線により通信を行う通信部１４、プレイヤからの操作入力をキーボタン等により受け付ける操作受付部１５、ゲーム画像をディスプレイ（表示装置）により出力する画像出力部１６、ゲーム音声をスピーカ（音響装置）により出力する音声出力部１７、装置に装填された外部媒体にアクセスする外部媒体アクセス部１８、といったハードウェア資源を有している。
【００１５】
本例のゲーム装置は、ゲームプログラムを記憶した外部媒体を装置に装填した状態で起動されると、外部媒体アクセス部１８により当該外部媒体からゲームプログラムを読み出してＲＡＭ１２に展開し、これをＣＰＵ１１により演算処理させることで、ゲームプログラムを実行する。すなわち、本例のゲーム装置は、本発明の一実施形態に係るゲームプログラムを記憶した外部媒体を用いることで、本発明の一実施形態に係る３次元空間データ処理装置として動作する。
【００１６】
なお、外部媒体としては、例えば、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｃ）−ＲＯＭ、ＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｃ）−ＲＯＭ、メモリーカートリッジなどの種々の記憶媒体を用いることができ、記憶媒体に応じた形式のアクセス機構を外部媒体アクセス部１８として設ければよい。
また、外部媒体アクセス部１８により外部媒体からゲームプログラムを読み取る構成ではなく、例えば、通信部１４により外部のサーバ装置からゲームプログラムを受信し、これをＲＡＭ１２に展開してＣＰＵ１１により演算処理させるようにしてもよい。
また、本例のゲーム装置は、上記のハードウェア資源を一体的に備えた携帯型のゲーム装置であるが、例えば、装置本体とは別体に設けられたディスプレイやスピーカによりゲーム画像や音声を出力する据置型のゲーム装置としてもよい。
【００１７】
本例のゲーム装置は、一例として、平面多角形の形状を有する複数のポリゴンを用いて表現される３次元の仮想的なゲーム空間内において、プレイヤの操作入力に応じて行動する自己キャラクタとコンピュータの制御により自律的に行動する敵キャラクタとが対戦するゲームを提供するものであり、自己キャラクタや敵キャラクタ等のキャラクタオブジェクトとゲーム空間内の地形や構造物等の背景オブジェクトとの衝突を判定し、これらのオブジェクトの衝突が検出された場合に所定の画像や音響等の出力を行って、衝突が発生したことをプレイヤに知らせるようにしてある。
【００１８】
本例のゲーム装置では、このような３次元のゲーム空間内におけるオブジェクトの衝突検出を、図２に例示するような機能部により実現する。
すなわち、本例のゲーム装置は、キャラクタオブジェクトと背景オブジェクトとの衝突を検出する衝突検出部２１と、これらのオブジェクトを形成するポリゴンのデータを記憶するポリゴンデータ記憶部２４と、を備えている。
また、衝突検出部２１は、背景オブジェクトを形成する複数のポリゴンの中からキャラクタオブジェクトが衝突する候補のポリゴンを選定する候補選定処理を行う候補選定部２２と、候補選定部２２により選定された候補のポリゴンを対象にして、キャラクタオブジェクトの移動予定の経路を示す移動線分との交差を判定する交差判定処理を行い、キャラクタオブジェクトが衝突するポリゴンを特定する交差判定部２３と、を有している。
【００１９】
候補選定部２２による候補選定処理及び交差判定部２３による交差判定処理について、図３〜図５を参照して説明する。
図３には、３角形形状のポリゴンを用いて形成された背景オブジェクトを有する３次元のゲーム空間内において、キャラクタオブジェクトが位置Ｔから位置Ｔ’へ向かって移動しようとしている状況を示してある。また、キャラクタオブジェクトの移動について、移動元（始点）を位置Ｔとし且つ移動先（終点）を位置Ｔ’とした有向線分（ベクトル）である移動線分Ｌで表現している。
【００２０】
ここで、背景オブジェクトのポリゴンを成す３角形の各頂点及びキャラクタオブジェクトの移動線分Ｌの始点（位置Ｔ）並びに終点（位置Ｔ’）の各点は、３次元の座標値（ｘ，ｙ，ｚ）で表現されるものとする。なお、ｘ座標は、３次元空間における幅方向（Ｘ軸方向）の座標であり、ｙ座標は、３次元空間における高さ方向（Ｙ軸方向）の座標であり、ｚ座標は、３次元空間における奥行き方向（Ｚ軸方向）の座標である。また、各軸の方向は、所定の視点方向を基準に定められている。
【００２１】
候補選定部２２の候補選定処理では、キャラクタオブジェクトの移動予定の経路を示す移動線分のデータ及びポリゴンデータ記憶部２４に記憶された背景オブジェクトのポリゴンのデータに基づいて、交差判定部２３による交差判定処理の対象とするポリゴン（キャラクタオブジェクトが衝突する候補のポリゴン）を選定する。
具体的には、候補選定部２２は、３次元空間上の背景オブジェクトのポリゴン及びキャラクタオブジェクトの移動線分を２次元平面に投影し、２次元平面上においてポリゴンの辺がキャラクタオブジェクトの移動線分と交差するポリゴンを検索し、該当するポリゴンをキャラクタオブジェクトが衝突する候補のポリゴンに選定して交差判定部２３に供給する。例えば、ＸＺ平面において候補のポリゴンの検索を行う場合には、各点（ポリゴンの各頂点及び移動線分の各端点）を示す３次元の座標値（ｘ，ｙ，ｚ）のうちの２次元の座標値（ｘ，ｚ）を用いることでＸＺ平面への投影結果が得られるので、２次元の座標値（ｘ，ｚ）を用いてポリゴンの辺と移動線分との交差を判定すればよい。
【００２２】
図４には、ＸＺ平面においてポリゴンの検索を行った結果を例示してある。図４では、ＸＺ平面において移動線分Ｌと交差する辺を有するポリゴンに斜めハッチパターンを付してあり、背景オブジェクトを形成する多数のポリゴンのうちの１２個のポリゴンが選定されている。当該選定されたポリゴンは、３次元空間において移動線分Ｌと交差する可能性があるポリゴンであり、交差判定部２３による交差判定処理の対象となる。
【００２３】
交差判定部２３の交差判定処理では、候補選定部２２により選定されたポリゴンを対象にして、３次元空間上においてポリゴンの面がキャラクタオブジェクトの移動線分と交差するか否かを判定し、ポリゴンの面がキャラクタオブジェクトの移動線分と交差するポリゴン（キャラクタオブジェクトが衝突するポリゴン）を特定する。３次元空間におけるポリゴンの面と線分との交差は種々の公知技術を用いて判定することができ、詳細な説明については割愛する。
【００２４】
図５の例では、移動線分Ｌと交差するポリゴンとして２つのポリゴンが特定されている。なお、選定された各ポリゴンの面と移動線分Ｌとの交差判定を、移動線分Ｌの始点（位置Ｔ）から終点（位置Ｔ’）に向かう方向に沿ったポリゴン順に実行し、ポリゴンの面が移動線分Ｌに交差するポリゴンが見付かった時点で処理を終了してもよい。この場合には、キャラクタオブジェクトが最初に衝突するポリゴン（移動線分Ｌの始点（位置Ｔ）側に位置するポリゴン）のみが特定される。
【００２５】
図６には、候補選定部２２による候補選定処理の処理フローを例示してある。
候補選定処理では、２次元平面（例えば、ＸＺ平面）において、移動線分の始点を内部に有するポリゴンの各辺について、移動線分と交差し且つ当該辺に対して移動線分の終点が外側にあるという条件を満たすかを判定する（ステップＳ１１）。
ステップＳ１１において、条件を満たす辺が見付からなかった場合には処理を終了し、条件を満たす辺が見付かった場合には当該辺を共有する他のポリゴンを検索する（ステップＳ１２）。
ステップＳ１２において、他のポリゴンが検索されなかった場合には処理を終了し、他のポリゴンが検索された場合にはステップＳ１１に戻り、当該他のポリゴンについて上記の処理（ステップＳ１１、Ｓ１２）を行うことを、上記の条件を満たす辺を有しないポリゴンが検出されるまで繰り返す。
そして、これらの処理の対象となった各ポリゴンを、交差判定部２３による交差判定処理の対象に選定する。
【００２６】
上記の候補選定処理について、図７に例示する具体例を参照しつつ説明する。
図７には、ポリゴンａ、ポリゴンｂ、ポリゴンｃと、ポリゴンａの内部に始点Ａを有し且つポリゴンｃの内部に終点Ｂを有する移動線分ＡＢを示してある。なお、ポリゴンａは、頂点０，頂点１，頂点２を有しており、ポリゴンｂは、頂点０，頂点２，頂点３を有しており、ポリゴンｃは、頂点２，頂点４，頂点３を有している。
【００２７】
本例では、上記のポリゴンについて、図８に例示するようなデータをポリゴンデータ記憶部２４に記憶している。
図８（ａ）は頂点データを例示しており、ポリゴンの各頂点となる３次元空間上の点の座標値を保持している。
図８（ｂ）はポリゴンデータを例示しており、ポリゴン毎に、ポリゴンの各頂点及びその並び順を特定する情報を保持している。本例では、ポリゴンの各頂点の並びにより当該ポリゴン面の向き（表裏）も定めている。すなわち、並び順に沿って各頂点を結んでポリゴンの輪郭線を描いた場合に、反時計回りの輪郭線であれば表面（背景オブジェクトの外面側）とし、時計回りの輪郭線であれば裏面（背景オブジェクトの内面側）とする。例えば、ポリゴンａの輪郭線は、頂点０→頂点１を結ぶ外辺と、頂点１→頂点２を結ぶ外辺と、頂点２→頂点０を結ぶ外辺とで表現され、これらの外辺を繋げた輪郭線が反時計回りであれば表面と判断される。
【００２８】
図８（ｃ）はリンクデータを例示しており、ポリゴンの輪郭線を成す外辺（２つの頂点間を結ぶ線）の終点となる頂点毎に、当該終点に至る外辺の始点となる頂点と当該外辺を有するポリゴンとの組を特定する情報を保持している。このようなリンクデータを用いれば、或るポリゴンの外辺を共有する他のポリゴンの特定を簡易に行える。すなわち、例えば、ポリゴンａの各外辺のうち、頂点２→頂点０を結ぶ外辺（始点を頂点２とし且つ終点を頂点０とした外辺）を共有する他のポリゴンは、頂点０→頂点２を結ぶ外辺（始点を頂点０とし且つ終点を頂点２とした外辺）を有するポリゴンｂであることを、リンクデータの参照により特定できる。
【００２９】
候補選定処理では、まず、移動線分ＡＢの始点Ａを内部に有するポリゴンａの各外辺について、移動線分ＡＢと交差し且つ当該外辺に対して移動線分ＡＢの終点Ｂが外側にあるという条件を満たすかを判定する。この結果、頂点２→頂点０を結ぶ外辺が特定される。
次に、リンクデータを参照して、頂点２→頂点０を結ぶ外辺とは逆向きの外辺を有するポリゴンを検索する。この結果、頂点０→頂点２を結ぶ外辺を有するポリゴンｂが特定される。
次に、ポリゴンｂの各外辺について、移動線分ＡＢと交差し且つ当該外辺に対して移動線分ＡＢの終点Ｂが外側にあるという条件を満たすかを判定する。この結果、頂点２→頂点３を結ぶ外辺が特定される。
次に、リンクデータを参照して、頂点２→頂点３を結ぶ外辺とは逆向きの外辺を有するポリゴンを検索する。この結果、頂点３→頂点２を結ぶ外辺を有するポリゴンｃが特定される。
次に、ポリゴンｂの各外辺について、移動線分ＡＢと交差し且つ当該外辺に対して移動線分ＡＢの終点Ｂが外側にあるという条件を満たすかを判定する。この結果、当該条件を満たす辺が存在しないので、検索を終了する。
そして、上記の処理の対象となったポリゴンａ、ｂ、ｃを、交差判定部２３による交差判定処理の対象に選定する。
【００３０】
なお、或る外辺に対して移動線分の終点が外側にあるか否かは、移動線分と外辺との外積により判定できる。ポリゴンの輪郭線（各外辺）が反時計回りの場合に表向きとした本例では、移動線分のベクトルについて外辺のベクトルとの外積を算出した場合に、外積の符号が正であれば移動線分の終点が内側にあると判定し、外積の符号が負であれば移動線分の終点が外側にあると判定する。
【００３１】
本例では、候補選定部２２による一連の候補選定処理が終了した後に、これにより選定された複数のポリゴンを順番に対象にして、交差判定部２３による交差判定処理を行っているが、例えば、候補選定部２２によりポリゴンが選定される毎に、当該選定されたポリゴンを対象にして交差判定部２３による交差判定処理を行うようにしてもよい。
【００３２】
以上のように、本例のゲーム装置では、候補選定部２２が、３次元空間上の背景オブジェクトのポリゴン及びキャラクタオブジェクトの移動線分を２次元平面に投影し、２次元平面上においてポリゴンの辺がキャラクタオブジェクトの移動線分と交差するポリゴンを選定して交差判定部２３に供給し、交差判定部２３が、候補選定部２２により選定されたポリゴンを対象にして、３次元空間上においてポリゴンの面がキャラクタオブジェクトの移動線分と交差するか否かを判定し、ポリゴンの面がキャラクタオブジェクトの移動線分と交差するポリゴン（キャラクタオブジェクトが衝突するポリゴン）を特定している。
このように、本例のゲーム装置では、３次元空間上での交差判定の対象とするポリゴンを２次元平面上で効果的に絞り込むことで、衝突判定に係る処理負担を軽減している。
【００３３】
なお、以上の説明では、３角形形状のポリゴンを用いたが、例えば６角形形状のポリゴンなど、他の形状のポリゴンを用いるようにしてもよい。
また、本発明は、キャラクタオブジェクトと背景オブジェクトとの衝突判定以外に適用してもよく、例えば、キャラクタオブジェクト同士の衝突判定に適用してもよい。また、例えば、キャラクタオブジェクトの視線の先にある背景オブジェクトを特定するに際し、視線の向きを示す線分と背景オブジェクトのポリゴンとの交差判定に適用してもよい。
また、本発明は、ゲーム装置以外の３次元空間データ処理装置にも適用することができ、例えば、航空機やレーシングカー等の訓練を仮想的な３次元空間上で行うための装置における衝突判定などに適用してもよい。
【符号の説明】
【００３４】
１１：ＣＰＵ、 １２：ＲＡＭ、 １３：ＲＯＭ、 １４：通信部、 １５：操作受付部、 １６：画像出力部、 １７：音声出力部、 １８：外部媒体アクセス部、
２１：衝突検出部、 ２２：候補選定部、 ２３：交差判定部、 ２４：ポリゴンデータ記憶部
【技術分野】
【０００１】
本発明は、平面多角形の形状を有する複数のポリゴンを用いて仮想的に表現される３次元空間について処理する技術に関し、特に、３次元の空間上の線分とポリゴンとの交差を判定する技術に関する。
【背景技術】
【０００２】
近年、平面多角形の形状を有する複数のポリゴンを用いて３次元の仮想的なゲーム空間を表現し、当該ゲーム空間内でゲームを展開する３Ｄゲームが実現されている。
このような３Ｄゲームでは、例えば、ゲーム空間内を移動する物体とゲーム空間内に存在する他の物体との衝突を判定し、これらの衝突が検出された場合に所定の画像や音響等の出力を行って、物体同士の衝突が発生したことをゲームのプレイヤに知らせることなどが行われている。このような衝突の判定では、例えば、移動する物体の移動元（始点）と移動先（終点）を結ぶ線分が、他の物体を形成するポリゴンの面を通過するかを判定する交差判定により当該線分と交差するポリゴンの有無を調べ、該当するポリゴンが存在する場合に衝突が発生したと判定される。
【０００３】
また、３Ｄゲームでは、例えば、ゲーム空間内を自律的に行動する自律キャラクタを用意してゲームの趣向性を高める工夫なども行われている。このような自律キャラクタの移動に係るルート探索用の技術としては、ナビゲーションメッシュ（Ｎａｖｉｇａｔｉｏｎ Ｍｅｓｈｅｓ）と呼ばれる技術が知られている。
ナビゲーションメッシュでは、例えば、背景やオブジェクト等を表現するためのポリゴンとは別に、キャラクタがゲーム内の場面（マップ等）を移動する際に利用する経路データを用意しておく。この経路データは、三角形ベースで構築された「道」であり、各三角形に対して隣の三角形との隣接情報を含めてあり、この経路データを用いてキャラクタが移動可能なルートの探索を行う。
ナビゲーションメッシュの詳細については、例えば、非特許文献１の「ＳＥＣＴＩＯＮ３ 人工知能」の「３．６ ナビゲーションメッシュによる３Ｄ移動とパスの発見の単純化」、非特許文献２の「ＳＥＣＴＩＯＮ３ 人工知能」の「３．７ 高速なナビゲーションメッシュ」、非特許文献３の「ＳＥＣＴＩＯＮ３ 人工知能」の「３．１ ナビゲーションメッシュによる自動的な退避場所探索」などに記載されている。
【先行技術文献】
【非特許文献】
【０００４】
【非特許文献１】Ｍａｒｋ ＤｅＬｏｕｒａ 他、「Ｇａｍｅ ＰｒｏｇｒａｍｍｉｎｇＧｅｍｓ 日本語版」、株式会社ボーンデジタル、平成１３年６月２５日
【非特許文献２】Ｄａｎｔｅ Ｔｒｅｇｌｉａ 他、「Ｇａｍｅ ＰｒｏｇｒａｍｍｉｎｇＧｅｍｓ ３ 日本語版」、株式会社ボーンデジタル、平成１６年１２月２１日
【非特許文献３】Ｋｉｍ Ｐａｌｌｉｓｔｅｒ 他、「Ｇａｍｅ ＰｒｏｇｒａｍｍｉｎｇＧｅｍｓ ５ 日本語版」、株式会社ボーンデジタル、平成１８年９月１５日
【発明の概要】
【発明が解決しようとする課題】
【０００５】
ここで、例えば、プレイヤの操作入力に応じて自己キャラクタが行動するアクションゲームのように即時応答性（リアルタイム性）が要求される３Ｄゲームでは、交差判定などの処理に手間取って遅延（タイムラグ）が生じるとゲームとしての興趣性が損なわれかねないことから、処理の負荷を軽減させて即時応答性を高めることが求められている。
【０００６】
本発明は、上記のような従来の事情に鑑みなされたものであり、平面多角形の形状を有する複数のポリゴンを用いて表現される３次元空間について、３次元空間上の線分とポリゴンとの交差を判定する技術に関し、交差判定に係る処理の負荷を軽減することを目的としている。
【課題を解決するための手段】
【０００７】
上記目的を達成するために、本発明では、平面多角形の形状を有する複数のポリゴンを用いて表現される３次元空間について、３次元空間上の線分とポリゴンとの交差を判定する３次元空間データ処理装置において、選定手段が、３次元空間上の線分及びポリゴンを２次元平面に投影し、２次元平面上においてポリゴンの辺が前記線分と交差するポリゴンを選定し、特定手段が、前記選定手段により選定されたポリゴンを対象にして、３次元空間上においてポリゴンの面が前記線分と交差するポリゴンを特定する。
【０００８】
すなわち、本発明に係る３次元空間データ処理装置では、３次元空間内に存在する全てのポリゴンを対象にして、当該ポリゴンの面が線分と交差するかの交差判定を行うのではなく、３次元空間に比べて処理負担が少ない２次元平面上でポリゴンの選定を行い、当該選定により絞り込まれたポリゴンを対象にして３次元空間上で交差判定を行うことで、３次元空間上で実行する交差判定の回数を減少させている。
このように、本発明では、３次元空間上での交差判定の対象とするポリゴンを２次元平面上で効果的に絞り込むことで、交差判定に係る処理の全体的な負荷を軽減している。
【０００９】
また、一構成例として、始点と終点が定められた線分について、前記選定手段が、２次元平面において、前記線分の始点を内部に有するポリゴンの各辺について、前記線分と交差し且つ当該辺に対して前記線分の終点が外側にあるという条件を満たすかを判定する処理を行い、当該条件を満たす辺を共有する他のポリゴンの各辺について前記処理を行うことを、前記条件を満たす辺を有しないポリゴンが検出されるまで繰り返し、前記処理の対象となったポリゴンを選定するように構成すればよい。
【００１０】
このような構成によれば、線分とポリゴンの各辺との交差の判定を、線分の始点から終点に向かう一方向の処理を１回行うだけで済ませることができ、該当するポリゴンの選定を効率的に行うことができる。
なお、上記の構成例において、前記選定手段が、辺を共有するポリゴン同士を関連付けたリンクデータを用いて、前記条件を満たす辺を共有する他のポリゴンを特定するように構成すれば、辺を共有する他のポリゴンの特定を簡易に行うことができる。
【００１１】
また、本発明は、上記のような３次元空間データ処理装置としてではなく、当該装置をコンピュータにより実現するためのプログラム（或いは当該プログラムをコンピュータ読み取り可能に記憶した記憶媒体）としても実現することができ、当該装置やプログラムなどにより実施される方法として把握することもできる。
【発明の効果】
【００１２】
本発明によれば、３次元空間内に存在する全てのポリゴンを対象にして、当該ポリゴンの面が線分と交差するかの交差判定を行うのではなく、３次元空間に比べて処理負担が少ない２次元平面上でポリゴンの選定を行い、当該選定により絞り込まれたポリゴンを対象にして３次元空間上で交差判定を行うため、３次元空間上で実行する交差判定の回数が減少される。すなわち、３次元空間上での交差判定の対象とするポリゴンが２次元平面上で効果的に絞り込まれるので、交差判定に係る処理の全体的な負荷が軽減される。
【図面の簡単な説明】
【００１３】
【図１】本発明の一実施形態に係るゲーム装置のハードウェア構成を例示する図である。
【図２】本発明の一実施形態に係るゲーム装置の機能ブロックを例示する図である。
【図３】本発明の一実施形態に係るゲーム装置による衝突判定を説明する図である。
【図４】本発明の一実施形態に係るゲーム装置による衝突判定を説明する図である。
【図５】本発明の一実施形態に係るゲーム装置による衝突判定を説明する図である。
【図６】本発明の一実施形態に係るゲーム装置により候補選定処理の処理フローを例示する図である。
【図７】本発明の一実施形態に係るゲーム装置による候補選定処理を説明する図である。
【図８】本発明の一実施形態に係るゲーム装置におけるポリゴンのデータを例示する図である。
【発明を実施するための形態】
【００１４】
本発明の一実施形態について図面を参照して説明する。
図１には、本発明の一実施形態に係る３次元空間データ処理装置として動作するゲーム装置のハードウェア構成を例示してある。
本例のゲーム装置は、各種演算処理を行うＣＰＵ（Ｃｅｎｔｒａｌ Ｐｒｏｃｃｅｓｓｉｎｇ Ｕｎｉｔ）１１、ＣＰＵ１１の作業領域となるＲＡＭ（Ｒａｎｄｏｍ Ａｃｃｅｓｓ Ｍｅｍｏｒｙ）１２、基本的な制御プログラムを記録したＲＯＭ（Ｒｅａｄ Ｏｎｌｙ Ｍｅｍｏｒｙ）１３、他の装置と有線又は無線により通信を行う通信部１４、プレイヤからの操作入力をキーボタン等により受け付ける操作受付部１５、ゲーム画像をディスプレイ（表示装置）により出力する画像出力部１６、ゲーム音声をスピーカ（音響装置）により出力する音声出力部１７、装置に装填された外部媒体にアクセスする外部媒体アクセス部１８、といったハードウェア資源を有している。
【００１５】
本例のゲーム装置は、ゲームプログラムを記憶した外部媒体を装置に装填した状態で起動されると、外部媒体アクセス部１８により当該外部媒体からゲームプログラムを読み出してＲＡＭ１２に展開し、これをＣＰＵ１１により演算処理させることで、ゲームプログラムを実行する。すなわち、本例のゲーム装置は、本発明の一実施形態に係るゲームプログラムを記憶した外部媒体を用いることで、本発明の一実施形態に係る３次元空間データ処理装置として動作する。
【００１６】
なお、外部媒体としては、例えば、ＤＶＤ（Ｄｉｇｉｔａｌ Ｖｅｒｓａｔｉｌｅ Ｄｉｓｃ）−ＲＯＭ、ＣＤ（Ｃｏｍｐａｃｔ Ｄｉｓｃ）−ＲＯＭ、メモリーカートリッジなどの種々の記憶媒体を用いることができ、記憶媒体に応じた形式のアクセス機構を外部媒体アクセス部１８として設ければよい。
また、外部媒体アクセス部１８により外部媒体からゲームプログラムを読み取る構成ではなく、例えば、通信部１４により外部のサーバ装置からゲームプログラムを受信し、これをＲＡＭ１２に展開してＣＰＵ１１により演算処理させるようにしてもよい。
また、本例のゲーム装置は、上記のハードウェア資源を一体的に備えた携帯型のゲーム装置であるが、例えば、装置本体とは別体に設けられたディスプレイやスピーカによりゲーム画像や音声を出力する据置型のゲーム装置としてもよい。
【００１７】
本例のゲーム装置は、一例として、平面多角形の形状を有する複数のポリゴンを用いて表現される３次元の仮想的なゲーム空間内において、プレイヤの操作入力に応じて行動する自己キャラクタとコンピュータの制御により自律的に行動する敵キャラクタとが対戦するゲームを提供するものであり、自己キャラクタや敵キャラクタ等のキャラクタオブジェクトとゲーム空間内の地形や構造物等の背景オブジェクトとの衝突を判定し、これらのオブジェクトの衝突が検出された場合に所定の画像や音響等の出力を行って、衝突が発生したことをプレイヤに知らせるようにしてある。
【００１８】
本例のゲーム装置では、このような３次元のゲーム空間内におけるオブジェクトの衝突検出を、図２に例示するような機能部により実現する。
すなわち、本例のゲーム装置は、キャラクタオブジェクトと背景オブジェクトとの衝突を検出する衝突検出部２１と、これらのオブジェクトを形成するポリゴンのデータを記憶するポリゴンデータ記憶部２４と、を備えている。
また、衝突検出部２１は、背景オブジェクトを形成する複数のポリゴンの中からキャラクタオブジェクトが衝突する候補のポリゴンを選定する候補選定処理を行う候補選定部２２と、候補選定部２２により選定された候補のポリゴンを対象にして、キャラクタオブジェクトの移動予定の経路を示す移動線分との交差を判定する交差判定処理を行い、キャラクタオブジェクトが衝突するポリゴンを特定する交差判定部２３と、を有している。
【００１９】
候補選定部２２による候補選定処理及び交差判定部２３による交差判定処理について、図３〜図５を参照して説明する。
図３には、３角形形状のポリゴンを用いて形成された背景オブジェクトを有する３次元のゲーム空間内において、キャラクタオブジェクトが位置Ｔから位置Ｔ’へ向かって移動しようとしている状況を示してある。また、キャラクタオブジェクトの移動について、移動元（始点）を位置Ｔとし且つ移動先（終点）を位置Ｔ’とした有向線分（ベクトル）である移動線分Ｌで表現している。
【００２０】
ここで、背景オブジェクトのポリゴンを成す３角形の各頂点及びキャラクタオブジェクトの移動線分Ｌの始点（位置Ｔ）並びに終点（位置Ｔ’）の各点は、３次元の座標値（ｘ，ｙ，ｚ）で表現されるものとする。なお、ｘ座標は、３次元空間における幅方向（Ｘ軸方向）の座標であり、ｙ座標は、３次元空間における高さ方向（Ｙ軸方向）の座標であり、ｚ座標は、３次元空間における奥行き方向（Ｚ軸方向）の座標である。また、各軸の方向は、所定の視点方向を基準に定められている。
【００２１】
候補選定部２２の候補選定処理では、キャラクタオブジェクトの移動予定の経路を示す移動線分のデータ及びポリゴンデータ記憶部２４に記憶された背景オブジェクトのポリゴンのデータに基づいて、交差判定部２３による交差判定処理の対象とするポリゴン（キャラクタオブジェクトが衝突する候補のポリゴン）を選定する。
具体的には、候補選定部２２は、３次元空間上の背景オブジェクトのポリゴン及びキャラクタオブジェクトの移動線分を２次元平面に投影し、２次元平面上においてポリゴンの辺がキャラクタオブジェクトの移動線分と交差するポリゴンを検索し、該当するポリゴンをキャラクタオブジェクトが衝突する候補のポリゴンに選定して交差判定部２３に供給する。例えば、ＸＺ平面において候補のポリゴンの検索を行う場合には、各点（ポリゴンの各頂点及び移動線分の各端点）を示す３次元の座標値（ｘ，ｙ，ｚ）のうちの２次元の座標値（ｘ，ｚ）を用いることでＸＺ平面への投影結果が得られるので、２次元の座標値（ｘ，ｚ）を用いてポリゴンの辺と移動線分との交差を判定すればよい。
【００２２】
図４には、ＸＺ平面においてポリゴンの検索を行った結果を例示してある。図４では、ＸＺ平面において移動線分Ｌと交差する辺を有するポリゴンに斜めハッチパターンを付してあり、背景オブジェクトを形成する多数のポリゴンのうちの１２個のポリゴンが選定されている。当該選定されたポリゴンは、３次元空間において移動線分Ｌと交差する可能性があるポリゴンであり、交差判定部２３による交差判定処理の対象となる。
【００２３】
交差判定部２３の交差判定処理では、候補選定部２２により選定されたポリゴンを対象にして、３次元空間上においてポリゴンの面がキャラクタオブジェクトの移動線分と交差するか否かを判定し、ポリゴンの面がキャラクタオブジェクトの移動線分と交差するポリゴン（キャラクタオブジェクトが衝突するポリゴン）を特定する。３次元空間におけるポリゴンの面と線分との交差は種々の公知技術を用いて判定することができ、詳細な説明については割愛する。
【００２４】
図５の例では、移動線分Ｌと交差するポリゴンとして２つのポリゴンが特定されている。なお、選定された各ポリゴンの面と移動線分Ｌとの交差判定を、移動線分Ｌの始点（位置Ｔ）から終点（位置Ｔ’）に向かう方向に沿ったポリゴン順に実行し、ポリゴンの面が移動線分Ｌに交差するポリゴンが見付かった時点で処理を終了してもよい。この場合には、キャラクタオブジェクトが最初に衝突するポリゴン（移動線分Ｌの始点（位置Ｔ）側に位置するポリゴン）のみが特定される。
【００２５】
図６には、候補選定部２２による候補選定処理の処理フローを例示してある。
候補選定処理では、２次元平面（例えば、ＸＺ平面）において、移動線分の始点を内部に有するポリゴンの各辺について、移動線分と交差し且つ当該辺に対して移動線分の終点が外側にあるという条件を満たすかを判定する（ステップＳ１１）。
ステップＳ１１において、条件を満たす辺が見付からなかった場合には処理を終了し、条件を満たす辺が見付かった場合には当該辺を共有する他のポリゴンを検索する（ステップＳ１２）。
ステップＳ１２において、他のポリゴンが検索されなかった場合には処理を終了し、他のポリゴンが検索された場合にはステップＳ１１に戻り、当該他のポリゴンについて上記の処理（ステップＳ１１、Ｓ１２）を行うことを、上記の条件を満たす辺を有しないポリゴンが検出されるまで繰り返す。
そして、これらの処理の対象となった各ポリゴンを、交差判定部２３による交差判定処理の対象に選定する。
【００２６】
上記の候補選定処理について、図７に例示する具体例を参照しつつ説明する。
図７には、ポリゴンａ、ポリゴンｂ、ポリゴンｃと、ポリゴンａの内部に始点Ａを有し且つポリゴンｃの内部に終点Ｂを有する移動線分ＡＢを示してある。なお、ポリゴンａは、頂点０，頂点１，頂点２を有しており、ポリゴンｂは、頂点０，頂点２，頂点３を有しており、ポリゴンｃは、頂点２，頂点４，頂点３を有している。
【００２７】
本例では、上記のポリゴンについて、図８に例示するようなデータをポリゴンデータ記憶部２４に記憶している。
図８（ａ）は頂点データを例示しており、ポリゴンの各頂点となる３次元空間上の点の座標値を保持している。
図８（ｂ）はポリゴンデータを例示しており、ポリゴン毎に、ポリゴンの各頂点及びその並び順を特定する情報を保持している。本例では、ポリゴンの各頂点の並びにより当該ポリゴン面の向き（表裏）も定めている。すなわち、並び順に沿って各頂点を結んでポリゴンの輪郭線を描いた場合に、反時計回りの輪郭線であれば表面（背景オブジェクトの外面側）とし、時計回りの輪郭線であれば裏面（背景オブジェクトの内面側）とする。例えば、ポリゴンａの輪郭線は、頂点０→頂点１を結ぶ外辺と、頂点１→頂点２を結ぶ外辺と、頂点２→頂点０を結ぶ外辺とで表現され、これらの外辺を繋げた輪郭線が反時計回りであれば表面と判断される。
【００２８】
図８（ｃ）はリンクデータを例示しており、ポリゴンの輪郭線を成す外辺（２つの頂点間を結ぶ線）の終点となる頂点毎に、当該終点に至る外辺の始点となる頂点と当該外辺を有するポリゴンとの組を特定する情報を保持している。このようなリンクデータを用いれば、或るポリゴンの外辺を共有する他のポリゴンの特定を簡易に行える。すなわち、例えば、ポリゴンａの各外辺のうち、頂点２→頂点０を結ぶ外辺（始点を頂点２とし且つ終点を頂点０とした外辺）を共有する他のポリゴンは、頂点０→頂点２を結ぶ外辺（始点を頂点０とし且つ終点を頂点２とした外辺）を有するポリゴンｂであることを、リンクデータの参照により特定できる。
【００２９】
候補選定処理では、まず、移動線分ＡＢの始点Ａを内部に有するポリゴンａの各外辺について、移動線分ＡＢと交差し且つ当該外辺に対して移動線分ＡＢの終点Ｂが外側にあるという条件を満たすかを判定する。この結果、頂点２→頂点０を結ぶ外辺が特定される。
次に、リンクデータを参照して、頂点２→頂点０を結ぶ外辺とは逆向きの外辺を有するポリゴンを検索する。この結果、頂点０→頂点２を結ぶ外辺を有するポリゴンｂが特定される。
次に、ポリゴンｂの各外辺について、移動線分ＡＢと交差し且つ当該外辺に対して移動線分ＡＢの終点Ｂが外側にあるという条件を満たすかを判定する。この結果、頂点２→頂点３を結ぶ外辺が特定される。
次に、リンクデータを参照して、頂点２→頂点３を結ぶ外辺とは逆向きの外辺を有するポリゴンを検索する。この結果、頂点３→頂点２を結ぶ外辺を有するポリゴンｃが特定される。
次に、ポリゴンｂの各外辺について、移動線分ＡＢと交差し且つ当該外辺に対して移動線分ＡＢの終点Ｂが外側にあるという条件を満たすかを判定する。この結果、当該条件を満たす辺が存在しないので、検索を終了する。
そして、上記の処理の対象となったポリゴンａ、ｂ、ｃを、交差判定部２３による交差判定処理の対象に選定する。
【００３０】
なお、或る外辺に対して移動線分の終点が外側にあるか否かは、移動線分と外辺との外積により判定できる。ポリゴンの輪郭線（各外辺）が反時計回りの場合に表向きとした本例では、移動線分のベクトルについて外辺のベクトルとの外積を算出した場合に、外積の符号が正であれば移動線分の終点が内側にあると判定し、外積の符号が負であれば移動線分の終点が外側にあると判定する。
【００３１】
本例では、候補選定部２２による一連の候補選定処理が終了した後に、これにより選定された複数のポリゴンを順番に対象にして、交差判定部２３による交差判定処理を行っているが、例えば、候補選定部２２によりポリゴンが選定される毎に、当該選定されたポリゴンを対象にして交差判定部２３による交差判定処理を行うようにしてもよい。
【００３２】
以上のように、本例のゲーム装置では、候補選定部２２が、３次元空間上の背景オブジェクトのポリゴン及びキャラクタオブジェクトの移動線分を２次元平面に投影し、２次元平面上においてポリゴンの辺がキャラクタオブジェクトの移動線分と交差するポリゴンを選定して交差判定部２３に供給し、交差判定部２３が、候補選定部２２により選定されたポリゴンを対象にして、３次元空間上においてポリゴンの面がキャラクタオブジェクトの移動線分と交差するか否かを判定し、ポリゴンの面がキャラクタオブジェクトの移動線分と交差するポリゴン（キャラクタオブジェクトが衝突するポリゴン）を特定している。
このように、本例のゲーム装置では、３次元空間上での交差判定の対象とするポリゴンを２次元平面上で効果的に絞り込むことで、衝突判定に係る処理負担を軽減している。
【００３３】
なお、以上の説明では、３角形形状のポリゴンを用いたが、例えば６角形形状のポリゴンなど、他の形状のポリゴンを用いるようにしてもよい。
また、本発明は、キャラクタオブジェクトと背景オブジェクトとの衝突判定以外に適用してもよく、例えば、キャラクタオブジェクト同士の衝突判定に適用してもよい。また、例えば、キャラクタオブジェクトの視線の先にある背景オブジェクトを特定するに際し、視線の向きを示す線分と背景オブジェクトのポリゴンとの交差判定に適用してもよい。
また、本発明は、ゲーム装置以外の３次元空間データ処理装置にも適用することができ、例えば、航空機やレーシングカー等の訓練を仮想的な３次元空間上で行うための装置における衝突判定などに適用してもよい。
【符号の説明】
【００３４】
１１：ＣＰＵ、 １２：ＲＡＭ、 １３：ＲＯＭ、 １４：通信部、 １５：操作受付部、 １６：画像出力部、 １７：音声出力部、 １８：外部媒体アクセス部、
２１：衝突検出部、 ２２：候補選定部、 ２３：交差判定部、 ２４：ポリゴンデータ記憶部
【特許請求の範囲】
【請求項１】
平面多角形の形状を有する複数のポリゴンを用いて表現される３次元空間について、３次元空間上の線分とポリゴンとの交差を判定する３次元空間データ処理装置において、
３次元空間上の線分及びポリゴンを２次元平面に投影し、２次元平面上においてポリゴンの辺が前記線分と交差するポリゴンを選定する選定手段と、
前記選定手段により選定されたポリゴンを対象にして、３次元空間上においてポリゴンの面が前記線分と交差するポリゴンを特定する特定手段と、
を備えたことを特徴とする３次元空間データ処理装置。
【請求項２】
前記線分には始点と終点が定められており、
前記選定手段は、２次元平面において、前記線分の始点を内部に有するポリゴンの各辺について、前記線分と交差し且つ当該辺に対して前記線分の終点が外側にあるという条件を満たすかを判定する処理を行い、当該条件を満たす辺を共有する他のポリゴンの各辺について前記処理を行うことを、前記条件を満たす辺を有しないポリゴンが検出されるまで繰り返し、前記処理の対象となったポリゴンを選定する、
ことを特徴とする請求項１に記載の３次元空間データ処理装置。
【請求項３】
前記選定手段は、辺を共有するポリゴン同士を関連付けたリンクデータを用いて、前記条件を満たす辺を共有する他のポリゴンを特定する、
ことを特徴とする請求項２に記載の３次元空間データ処理装置。
【請求項４】
平面多角形の形状を有する複数のポリゴンを用いて表現される３次元空間について、３次元空間上の線分とポリゴンとの交差を判定する処理に係るプログラムであって、
コンピュータに、
３次元空間上の線分及びポリゴンを２次元平面に投影し、２次元平面上においてポリゴンの辺が前記線分と交差するポリゴンを選定する選定機能と、
前記選定機能により選定されたポリゴンを対象にして、３次元空間上においてポリゴンの面が前記線分と交差するポリゴンを特定する特定機能と、
を実現させるためのプログラム。
【請求項１】
平面多角形の形状を有する複数のポリゴンを用いて表現される３次元空間について、３次元空間上の線分とポリゴンとの交差を判定する３次元空間データ処理装置において、
３次元空間上の線分及びポリゴンを２次元平面に投影し、２次元平面上においてポリゴンの辺が前記線分と交差するポリゴンを選定する選定手段と、
前記選定手段により選定されたポリゴンを対象にして、３次元空間上においてポリゴンの面が前記線分と交差するポリゴンを特定する特定手段と、
を備えたことを特徴とする３次元空間データ処理装置。
【請求項２】
前記線分には始点と終点が定められており、
前記選定手段は、２次元平面において、前記線分の始点を内部に有するポリゴンの各辺について、前記線分と交差し且つ当該辺に対して前記線分の終点が外側にあるという条件を満たすかを判定する処理を行い、当該条件を満たす辺を共有する他のポリゴンの各辺について前記処理を行うことを、前記条件を満たす辺を有しないポリゴンが検出されるまで繰り返し、前記処理の対象となったポリゴンを選定する、
ことを特徴とする請求項１に記載の３次元空間データ処理装置。
【請求項３】
前記選定手段は、辺を共有するポリゴン同士を関連付けたリンクデータを用いて、前記条件を満たす辺を共有する他のポリゴンを特定する、
ことを特徴とする請求項２に記載の３次元空間データ処理装置。
【請求項４】
平面多角形の形状を有する複数のポリゴンを用いて表現される３次元空間について、３次元空間上の線分とポリゴンとの交差を判定する処理に係るプログラムであって、
コンピュータに、
３次元空間上の線分及びポリゴンを２次元平面に投影し、２次元平面上においてポリゴンの辺が前記線分と交差するポリゴンを選定する選定機能と、
前記選定機能により選定されたポリゴンを対象にして、３次元空間上においてポリゴンの面が前記線分と交差するポリゴンを特定する特定機能と、
を実現させるためのプログラム。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【公開番号】特開２０１２−１３３７０１（Ｐ２０１２−１３３７０１Ａ）
【公開日】平成２４年７月１２日（２０１２．７．１２）
【国際特許分類】
【出願番号】特願２０１０−２８６９９０（Ｐ２０１０−２８６９９０）
【出願日】平成２２年１２月２４日（２０１０．１２．２４）
【出願人】（５０５０６８４６８）株式会社シフト (2)
【Ｆターム（参考）】
【公開日】平成２４年７月１２日（２０１２．７．１２）
【国際特許分類】
【出願日】平成２２年１２月２４日（２０１０．１２．２４）
【出願人】（５０５０６８４６８）株式会社シフト (2)
【Ｆターム（参考）】
[ Back to top ]