(57)【要約】【課題】  衝突感知装置及び方法を提供する。【解決手段】  与えられた映像に含まれたそれぞれのモデルごとにモデルを包むモデルプリミティブを生成するプリミティブ生成部と、映像を分割して複数のボクセルを生成する映像分割部と、複数のモデルプリミティブが存在するボクセルを、生成されたボクセルで検索する検索部と、検索されたボクセルごとに、モデルプリミティブ間に衝突が発生するかどうかを検査する衝突如何検査部と、検査された結果に応答してモデル間の衝突を感知する衝突感知部とを備える。【選択図】      図２
2007242022.tif 000002
【特許請求の範囲】
【請求項１】
与えられた映像に含まれたそれぞれのモデルごとに前記モデルを包むモデルプリミティブを生成するプリミティブ生成部と、
前記映像を分割して複数のボクセルを生成する映像分割部と、
複数の前記モデルプリミティブが存在するボクセルを、前記生成されたボクセルで検索する検索部と、
前記検索されたボクセルごとに、前記モデルプリミティブ間に衝突が発生するかどうかを検査する衝突如何検査部と、
前記検査された結果に応答して前記モデル間の衝突を感知する衝突感知部と、を備えることを特徴とする衝突感知装置。
【請求項２】
前記モデルは、背景または客体であることを特徴とする請求項１に記載の衝突感知装置。
【請求項３】
前記プリミティブ生成部は、前記背景を包む背景プリミティブ及び前記客体を包む客体プリミティブを生成し、
前記検索部は、前記背景プリミティブと前記客体プリミティブとが存在するボクセルを前記生成されたボクセルで検索し、
前記衝突如何検査部は、前記検索されたボクセルごとに前記背景プリミティブと前記客体プリミティブとが衝突するかどうかを検査し、
前記衝突感知部は、前記検査された結果に応答して前記客体と前記背景との衝突を感知することを特徴とする請求項２に記載の衝突感知装置。
【請求項４】
前記プリミティブ生成部は、前記客体を包む客体プリミティブを生成し、
前記検索部は、複数の前記客体プリミティブが存在するボクセルを前記生成されたボクセルで検索し、
前記衝突如何検査部は、前記検索されたボクセルごとに前記客体プリミティブ間に衝突が発生するかどうかを検査し、
前記衝突感知部は、前記検査された結果に応答して前記客体間の衝突を感知することを特徴とする請求項２に記載の衝突感知装置。
【請求項５】
前記プリミティブ生成部は、
前記モデルの体積を演算する第１体積演算部と、
第１ないし第Ｎ（ただし、Ｎは、２以上の整数）プリミティブを生成する仮想モデル生成部と、
前記第１ないし前記第Ｎプリミティブそれぞれの体積を演算する第２体積演算部と、
前記第ｎプリミティブ（ただし、ｎは、Ｎ以下の自然数）ごとに前記第１体積演算部で演算された体積と、前記第２体積演算部で演算された体積とを比較し、比較された結果に相応して、前記第ｎプリミティブを前記モデルプリミティブとして出力する体積比較部と、を備え、
前記第ｎプリミティブは、前記モデルを第ｎ所定形状に包むモデルプリミティブであることを特徴とする請求項１に記載の衝突感知装置。
【請求項６】
前記体積比較部は、
前記第ｎプリミティブごとに前記第１体積演算部で演算された体積と前記第２体積演算部で演算された体積との差を演算し、演算された値のうち最小値を持つ前記第ｎプリミティブを前記モデルプリミティブとして出力することを特徴とする請求項５に記載の衝突感知装置。
【請求項７】
前記生成されたボクセルの体積は、あらゆる前記生成されたモデルプリミティブの体積の平均値に所定分を乗算した結果であることを特徴とする請求項１に記載の衝突感知装置。
【請求項８】
前記検索されたボクセルに存在するモデルプリミティブは、前記モデルプリミティブの全部または一部であることを特徴とする請求項１に記載の衝突感知装置。
【請求項９】
前記映像は、３次元映像であることを特徴とする請求項１に記載の衝突感知装置。
【請求項１０】
前記プリミティブの形状は、ＡＡＢＢ、ＯＢＢ、カプセルまたは球であることを特徴とする請求項１に記載の衝突感知装置。
【請求項１１】
（ａ）与えられた映像に含まれたそれぞれのモデルごとに前記モデルを包むモデルプリミティブを生成し、前記映像を分割して複数のボクセルを生成するステップと、
（ｂ）複数の前記モデルプリミティブが存在するボクセルを前記生成されたボクセルで検索するステップと、
（ｃ）前記検索されたボクセルで前記モデルプリミティブ間に衝突が発生するかどうかを判断するステップと、
（ｄ）前記検索されたボクセルで前記モデルプリミティブ間に衝突が発生すると判断されれば、前記モデル間の衝突を感知するステップと、を含むことを特徴とする衝突感知方法。
【請求項１２】
前記モデルは、背景または客体であることを特徴とする請求項１１に記載の衝突感知方法。
【請求項１３】
前記（ａ）ステップは、前記背景を包む背景プリミティブ及び前記客体を包む客体プリミティブを生成し、
前記（ｂ）ステップは、前記背景プリミティブと前記客体プリミティブとが存在するボクセルを前記生成されたボクセルで検索し、
前記（ｃ）ステップは、前記検索されたボクセルで、前記背景プリミティブと前記客体プリミティブとが衝突するかどうかを判断し、
前記（ｄ）ステップは、前記検索されたボクセルで、前記背景プリミティブと前記客体プリミティブとが衝突すると判断されれば、前記客体と前記背景との衝突を感知することを特徴とする請求項１２に記載の衝突感知方法。
【請求項１４】
前記（ａ）ステップは、前記客体を包む客体プリミティブを生成し、
前記（ｂ）ステップは、複数の前記客体プリミティブが存在するボクセルを前記生成されたボクセルで検索し、
前記（ｃ）ステップは、前記検索されたボクセルで、前記客体プリミティブ間に衝突が発生するかどうかを判断し、
前記（ｄ）ステップは、前記検索されたボクセルで、前記客体プリミティブ間に衝突が発生すると判断されれば、前記客体間の衝突を感知することを特徴とする請求項１２に記載の衝突感知方法。
【請求項１５】
前記（ａ）ステップは、
（ａ１）前記モデルの体積を求めるステップと、
（ａ２）前記モデルを第ｎ所定形状に包む第ｎ（ただし、ｎは、Ｎ以下の自然数、Ｎは、２以上の整数）プリミティブを生成するステップと、
（ａ３）前記第ｎプリミティブの体積を求めるステップと、
（ａ４）前記（ａ１）ステップで求められた体積と、前記（ａ３）ステップで求められた体積との差を求めるステップと、
（ａ５）第１ないし第Ｎプリミティブが生成されたかどうかを判断し、第１ないし第Ｎプリミティブが生成されたと判断されれば、前記（ａ４）ステップで求められた値のうち、最小値を持つ前記第ｎプリミティブを前記モデルプリミティブとして出力するステップと、を含むことを特徴とする請求項１１に記載の衝突感知方法。
【請求項１６】
前記（ａ）ステップは、
（ａ６）第１ないし第Ｎプリミティブが生成されていないと判断されれば、前記（ａ２）ステップに進むステップをさらに含むことを特徴とする請求項１５に記載の衝突感知方法。
【請求項１７】
前記生成されたボクセルの体積は、あらゆる前記生成されたモデルプリミティブの体積の平均値に所定値を乗算した結果であることを特徴とする請求項１１に記載の衝突感知方法。
【請求項１８】
前記検索されたボクセルに存在するモデルプリミティブは、前記モデルプリミティブの全部または一部であることを特徴とする請求項１１に記載の衝突感知方法。
【請求項１９】
前記映像は、３次元映像であることを特徴とする請求項１１に記載の衝突感知方法。
【請求項２０】
請求項１１ないし１９のうちいずれか一項に記載の方法をコンピュータで実行させるためのプログラムを保存するコンピュータで読み取り可能な記録媒体。
【請求項２１】
映像を分割して複数のボクセルを生成するステップと、
前記生成されたボクセルのうち複数のモデルプリミティブを持つボクセルで、前記モデルプリミティブが互いに衝突するかどうかを判断するステップと、
前記モデルプリミティブが互いに衝突すると判断されれば、前記モデルプリミティブが包むモデルが互いに衝突すると感知するステップと、を含むことを特徴とする衝突感知方法。
【請求項２２】
前記モデルプリミティブは、前記映像に含まれた背景を包む背景プリミティブ、または前記映像に含まれた客体を包む客体プリミティブであることを特徴とする請求項２１に記載の衝突感知方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、衝突感知に係り、より詳細には、映像に含まれたモデル間に発生する衝突をリアルタイムで感知する衝突装置及び方法に関する。
【背景技術】
【０００２】
映像に含まれたモデルは互いに衝突でき、そのような衝突は、発生する直ちに感知されることが望ましい。例えば、３次元レーシングゲームの場合、ゲームユーザーにより操作され、運行中の自動車が他の自動車またはレース場の外の樹と衝突する場合、そのユーザーの点数は即刻調整されねばならないので、その３次元レーシングゲームを具現するシステムは、その衝突をリアルタイムで感知することが望ましい。
【０００３】
従来の衝突感知装置は、映像に含まれたモデル間に発生する衝突を感知するために、映像のあらゆる空間を探索する。結局、従来の衝突感知装置は、衝突の迅速な感知に限界があるという問題点を持つ。
【発明の開示】
【発明が解決しようとする課題】
【０００４】
本発明が解決しようとする技術的課題は、映像に含まれたモデル間に発生する衝突をリアルタイムで感知する衝突装置を提供するところにある。
【０００５】
本発明が解決しようとする他の技術的課題は、映像に含まれたモデル間に発生する衝突をリアルタイムで感知する方法を提供するところにある。
【０００６】
本発明が解決しようとするさらに他の技術的課題は、映像に含まれたモデル間に発生する衝突をリアルタイムで感知するコンピュータプログラムを保存するコンピュータで読み取り可能な記録媒体を提供するところにある。
【課題を解決するための手段】
【０００７】
前記課題を解決するために、本発明による衝突感知装置は、与えられた映像に含まれたそれぞれのモデルごとに前記モデルを包むモデルプリミティブを生成するプリミティブ生成部と、前記映像を分割して複数のボクセルを生成する映像分割部と、複数の前記モデルプリミティブが存在するボクセルを、前記生成されたボクセルで検索する検索部と、前記検索されたボクセルごとに、前記モデルプリミティブ間に衝突が発生するかどうかを検査する衝突如何検査部と、前記検査された結果に応答して前記モデル間の衝突を感知する衝突感知部と、を備えることが望ましい。
【０００８】
前記他の課題を解決するために、本発明による衝突感知方法は、与えられた映像に含まれたそれぞれのモデルごとに前記モデルを包むモデルプリミティブを生成し、前記映像を分割して複数のボクセルを生成する（ａ）ステップと、複数の前記モデルプリミティブが存在するボクセルを前記生成されたボクセルで検索する（ｂ）ステップと、前記検索されたボクセルで前記モデルプリミティブ間に衝突が発生するかどうかを判断する（ｃ）ステップと、前記検索されたボクセルで前記モデルプリミティブ間に衝突が発生すると判断されれば、前記モデル間の衝突を感知する（ｄ）ステップと、を含むことが望ましい。
【０００９】
前記さらに他の課題を解決するために、本発明によるコンピュータで読み取り可能な記録媒体は、前記の方法をコンピュータで実行させるためのコンピュータプログラムを保存することが望ましい。
【発明の効果】
【００１０】
本発明による衝突感知装置及び方法は、映像に含まれたモデル間に衝突が発生するかどうかを感知するために、映像のあらゆる空間のうち衝突の発生が予想される空間についてのみ探索するので、衝突を速かに感知できる効果、さらに衝突をリアルタイムで感知できる効果を持つ。また、本発明による衝突感知装置及び方法は、映像に含まれた背景（または、客体）及び客体間に衝突が発生しているか感知するために、背景（または、客体）及び客体の位置を比較せず、背景プリミティブ（または、客体プリミティブ）及び客体プリミティブの位置を比較するので、背景（または、客体）及び客体間の衝突をさらに迅速に感知できる効果を持つ。一方、本発明による衝突感知装置及び方法は、背景（または、客体）を包むいろいろな形状のうち、体積が実際背景（または、客体）の体積と最も近似した形状を、背景プリミティブ（または、客体プリミティブ）の形状に自動選択かつ生成できるので、背景プリミティブ（または、客体プリミティブ）の著作が容易であるという効果も持つ。
【発明を実施するための最良の形態】
【００１１】
本発明と本発明の動作上の利点及び本発明の実施によって達成される目的を十分に理解するためには、本発明の望ましい実施形態を例示する添付図面及びその添付図面を説明する内容を参照せねばならない。
【００１２】
以下、本発明による衝突感知装置及び方法を添付した図面を参照して次のように説明する。
【００１３】
図１は、ワールド１００、客体１１０、１２０、１３０、１４０、及び背景１５０を説明するための参考図である。本明細書上で、映像とは、静止映像を意味することもあるが、動画、特に、特定時点（ｔｉｍｅｐｏｉｎｔ）でのフレームが持つ映像、すなわち、ワールド１００を意味することが望ましい。一方、本明細書上で、映像は２次元映像を意味することもあり、３次元映像を意味することもある。ただし、説明の便宜上、以下、映像は３次元映像であると仮定する。
【００１４】
図示されたように、映像には客体１１０、１２０、１３０、１４０及び背景１５０が含まれうる。ここで、客体１１０、１２０、１３０、１４０とは、人間、物を含んだ任意の物体の映像を意味し、背景１５０とは、陸地（ｌａｎｄｓｃａｐｅ）、川、海、空のように客体１１０、１２０、１３０、１４０が位置する場所の映像を意味する。厳密に、背景と客体いずれも広い意味の物体であるが、本明細書上で、客体は背景を除外したあらゆる物体の映像を意味する。
【００１５】
このような客体１１０、１２０、１３０、１４０には木１１０、家１２０のような静的客体と自動車１３０、人１４０のような動的客体が含まれる。
【００１６】
衝突は、客体１１０、１２０、１３０、１４０と客体との間に発生することもあり、客体と背景１５０との間に発生することもある。以下、図２ないし図９を参照して、本発明により衝突が感知される原理を具体的で開示する。
【００１７】
図２は、本発明による衝突感知装置を説明するためのブロック図であり、プリミティブ生成部２１０、映像分割部２２０、検索部２３０、衝突如何検査部２４０及び衝突感知部２５０から形成される。
【００１８】
プリミティブ生成部２１０は、与えられた映像に含まれたそれぞれのモデルごとにそのモデルのプリミティブであるモデルプリミティブを生成する。ここで、プリミティブとは、‘包む物体’を意味する。すなわち、‘ａのプリミティブ’とは、‘ａを包む物体’を意味する。この時、プリミティブは既定の形状を持ち、‘ａのプリミティブ’は、その既定の形状にａを包む物体のうち、最小の体積を持つ物体を意味することが望ましい。
【００１９】
結局、プリミティブ生成部２１０は、与えられた映像に含まれたそれぞれのモデルごとにそのモデルを包むモデルプリミティブを生成する。ここで、モデルとは、背景を意味することもあり、客体を意味することもある。すなわち、背景を包む物体である‘背景のプリミティブ（以下、背景プリミティブ）’、客体を包む物体である‘客体のプリミティブ（以下、客体プリミティブ）’は、モデルプリミティブの一例である。一方、映像は入力端子ＩＮ
１を通じて入力されて与えられる。このようなプリミティブ生成部２１０の動作は、図３ないし図６を参照してさらに具体的に説明する。
【００２０】
映像分割部２２０は、映像を分割して複数のボクセルを生成する。これにより、映像はボクセル構造を持つ。ここで、生成されたボクセルそれぞれの大きさ及び体積はいずれも同一でありうる。この場合、映像分割部２２０は、プリミティブ生成部２１０で生成されたあらゆるモデルプリミティブの体積の平均値に所定値、例えば、４を乗算した値を体積として持つボクセルを複数生成できる。
【００２１】
一方、検索部２３０は、‘モデルプリミティブ間に衝突が発生するボクセルであると推測されるボクセル’を、その生成されたボクセル中で検索する。具体的に、検索部２３０は、複数のモデルプリミティブが存在するボクセルをその生成されたボクセル中で検索する。ここで、ボクセルに存在するモデルプリミティブとは、ボクセルに俗漢モデルプリミティブを意味することもあり、ボクセルに一部がまたがっているモデルプリミティブを意味することもある。すなわち、検索部２３０で検索されたボクセルに存在するモデルプリミティブは、モデルプリミティブの全部または一部である。
【００２２】
このような映像分割部２２０及び検索部２３０の動作は、図７Ａないし図７Ｄを参照してさらに具体的に説明する。
【００２３】
衝突如何検査部２４０は、検索部２３０で検索されたボクセルごとに、モデルプリミティブ間に衝突が発生するかどうかを検査する。衝突如何検査部２４０は、モデルプリミティブの位置情報を利用して、モデルプリミティブ間に衝突が発生するかどうかを検査できる。例えば、モデルａとモデルｂが映像に含まれ、モデルａのプリミティブであるモデルプリミティブａ’、及びモデルｂのプリミティブであるモデルプリミティブｂ’が同じボクセルに存在する場合、衝突如何検査部２４０は、モデルプリミティブａ’の位置情報とモデルプリミティブｂ’の位置情報とを利用して、モデルプリミティブａ’とモデルプリミティブｂ’とが接するか、モデルプリミティブａ’とモデルプリミティブｂ’とが重なるかを検査できる。この場合、モデルプリミティブａ’とモデルプリミティブｂ’とが接するか、または重なると検査されれば、衝突如何検査部２４０は、モデルプリミティブａ’とモデルプリミティブｂ’とが衝突すると決定する。一方、モデルプリミティブａ’とモデルプリミティブｂ’とが接することもなく、重なることもないと検査されれば、衝突如何検査部２４０は、モデルプリミティブａ’とモデルプリミティブｂ’とが衝突しないと決定する。
【００２４】
衝突感知部２５０は、衝突如何検査部２４０で検査された結果に応答してモデル間の衝突を感知する。具体的に、衝突如何検査部２４０でモデルプリミティブ間に衝突が発生しないと検査されれば、衝突感知部２５０は、‘モデル間に衝突が発生しない’と感知する。一方、衝突如何検査部２４０でモデルプリミティブ間に衝突が発生すると検査されれば、衝突感知部２５０は、‘モデル間に衝突が発生する’と感知する。
【００２５】
検索部２３０ないし衝突感知部２５０の動作について前述したところは、モデルとモデルプリミティブとの観点で開示された。これを背景（または、客体）と背景プリミティブ（または、客体プリミティブ）の観点で開示すれば、次の通りである。
【００２６】
具体的に、背景と客体との衝突感知のために、検索部２３０ないし衝突感知部２５０は次のように動作する。
【００２７】
検索部２３０は、映像分割部２２０で生成されたボクセルのうち、背景プリミティブと客体プリミティブとが存在する一つ以上のボクセルを検索できる。
【００２８】
この場合、衝突如何検査部２４０は、検索部２３０で検索されたボクセルごとに、背景プリミティブと客体プリミティブとが衝突するかどうかを検査する。また、衝突感知部２５０は、衝突如何検査部２４０で検査された結果に応答して、客体と背景との衝突を感知する。例えば、背景ｃと客体ｄが映像に含まれ、背景ｃのプリミティブである背景プリミティブｃ’、及び客体ｄのプリミティブである客体プリミティブｄ’が同じボクセルに存在する場合、衝突如何検査部２４０で背景プリミティブｃ’と客体プリミティブｄ’とが衝突すると検査されるならば、衝突感知部２５０は、‘客体ｄが背景ｃに衝突する’と感知する。
【００２９】
一方、客体と客体間の衝突感知のために、検索部２３０ないし衝突感知部２５０は次のように動作する。
【００３０】
検索部２３０は、映像分割部２２０で生成されたボクセルのうち、複数の客体プリミティブが存在する一つ以上のボクセルを検索できる。
【００３１】
この場合、衝突如何検査部２４０は、検索部２３０で検索されたボクセルごとに、客体プリミティブと客体プリミティブとが衝突するかどうかを検査する。また、衝突感知部２５０は、衝突如何検査部２４０で検査された結果に応答して、客体と客体との衝突を感知する。例えば、客体ｅと客体ｆとが映像に含まれ、客体ｅのプリミティブである客体プリミティブｅ’、及び客体ｆのプリミティブである客体プリミティブｆ’が同じボクセルに存在する場合、衝突如何検査部２４０で客体プリミティブｅ’と客体プリミティブｆ’とが衝突すると検査されるならば、衝突感知部２５０は、‘客体ｅと客体ｆとが衝突する’と感知する。
【００３２】
図３Ａないし図３Ｄは、モデルプリミティブを説明するための参考図である。具体的に、図１に図示された客体１１０、１２０、１３０、１４０それぞれの客体プリミティブ３１０、３２０、３３０、３４０を示す図である。
【００３３】
図４Ａないし図４Ｄは、モデルプリミティブが持つ形状の一例である。すなわち、モデルプリミティブは、図４Ａに示したように、ＡＡＢＢ（Ａｘｉｓ  Ａｌｉｇｎｅｄ  Ｂｏｕｎｄｉｎｇ  Ｂｏｘ）４２０の形状を持つこともあり、図４Ｂに示したように、ＯＢＢ（Ｏｒｉｅｎｔｅｄ  Ｂｏｕｎｄｉｎｇ  Ｂｏｘ）４３０の形状を持つこともあり、図４Ｃに示したように、カプセル４４０の形状を持つこともあり、図４Ｄに示したように球（ｓｐｈｅｒｅ）４５０の形状を持つこともある。
【００３４】
ここで、ＡＡＢＢとは、１２つのコーナーのうち３つのコーナーが、互いに直交（ｏｒｔｈｏｇｏｎａｌ）する３次元軸（ｘ，ｙ，ｚ）４１０の各方向と平行した六面体を意味する。この時、３次元軸の方向は、あらかじめ設定されることが望ましい。一方、ＯＢＢとは、ＡＡＢＢがその３次元軸４１０に対して所定角度ほど回転するか（または、所定角度ほど回転しつつ）所定距離ほど移動した結果を意味する。
【００３５】
図５Ａないし図５Ｃは、モデルプリミティブが持つことができる形状のうち、最も望ましい形状を説明するための参考図である。図５Ｂに図示された客体プリミティブ５２０は、図５Ｃに図示された客体プリミティブ５３０より、図５Ａに図示された客体５１０の客体プリミティブとして望ましい。このように、あるモデルの最も望ましいモデルプリミティブは、そのモデルの体積と最も近似した体積を持つモデルプリミティブである。
【００３６】
図６は、図２に図示されたプリミティブ生成部２１０についての本発明による望ましい一実施形態２１０Ａを説明するためのブロック図であり、第１体積演算部６１０、仮想モデル生成部６２０、第２体積演算部６３０及び体積比較部６４０で形成される。ここで、入力端子ＩＮ  ２は、入力端子ＩＮ  １に該当する。
【００３７】
第１体積演算部６１０は、与えられた映像に含まれたモデルの体積を演算する。
【００３８】
仮想モデル生成部６２０は、第１仮想モデル生成部６２０−１、第２仮想モデル生成部６２０−２、…、第Ｎ（ただし、Ｎは、２以上の整数）仮想モデル生成部６２０−Ｎで形成される。このような仮想モデル生成部６２０は、第１プリミティブないし第Ｎプリミティブを生成する。具体的に、第ｎ（ただし、ｎは、Ｎ以下の自然数）仮想モデル生成部６２０−Ｎは、第ｎプリミティブを生成する。ここで、第ｎプリミティブとは、モデルを第ｎ所定形状に包むモデルプリミティブを意味する。
【００３９】
一方、第ａ（ただし、ａは、Ｎ以下の自然数）仮想モデル生成部６２０−ａは、第ｂ（ただし、ｂは、Ｎ以下の自然数、ｂ≠ａ）仮想モデル生成部６２０−ｂで生成された第ｂプリミティブを利用して、第ａプリミティブを自動生成することもできる。
【００４０】
例えば、第ａプリミティブは、球形状のプリミティブであり、第ｂプリミティブは、ＡＡＢＢ形状のプリミティブであるとする時、第ａ仮想モデル生成部６２０−ａは、次のような数式を利用して第ｂプリミティブから第ａプリミティブを自動生成することもできる。
【００４１】
【数１】
2007242022.tif 000003
ここで、Ｃｓｐ、Ｖｍａｘ、Ｖｍｉｎはベクトルであり、ｒ、ｘＶｍａｘ、ｙＶｍａｘ、ｚＶｍａｘ、ｘＣｓｐ、ｙＣｓｐ、ｚＣｓｐはスカラー（ｓｃａｌａｒ）である。この時、Ｖｍａｘは、原点（すなわち、（ｘ，ｙ，ｚ）＝（０，０，０））が始点であり、（ｘ，ｙ，ｚ）＝（ｂ，０，０）、（ａ，ｃ，０）、または（ａ，０，ｄ）などが終点であるベクトルのように、ＡＡＢＢを表すベクトルのうち大きさの最も大きいベクトルを意味する。同様に、Ｖｍｉｎは、原点が始点であり、（ｘ，ｙ，ｚ）＝（ａ，０，０）が終点であるベクトルのように、ＡＡＢＢを表すベクトルのうち大きさの最も小さなベクトルを意味する。
【００４２】
一方、Ｃｓｐは、原点Ｏを始点とし、第ａプリミティブの中心を表すベクトルを意味し、ｒは、第ａプリミティブの半径を意味し、ｘＶｍａｘ、ｙＶｍａｘ、ｚＶｍａｘは、原点Ｏを始点とするＶｍａｘの終点の座標を意味し、ｘＣｓｐ、ｙＣｓｐ、ｚＣｓｐは、Ｃｓｐの終点を座標を意味する。
【００４３】
第２体積演算部６３０は、第２−１体積演算部６３０−１、第２−２体積演算部６３０−２、…、第２−Ｎ体積演算部６３０−Ｎで形成される。このような第２体積演算部６３０は、第１ないし第Ｎプリミティブそれぞれの体積を演算する。具体的に、第２−ｎ体積演算部６３０−Ｎは、第ｎ仮想モデル生成部６２０−Ｎで生成された第ｎプリミティブの体積を演算する。
【００４４】
体積比較部６４０は、仮想モデル生成部６２０で生成された第ｎプリミティブごとに、第１体積演算部６１０で演算されたモデル体積と第２体積演算部６３０で演算されたプリミティブ体積とを比較し、比較された結果に相応して第ｎプリミティブをモデルプリミティブとして出力する。
【００４５】
具体的に、体積比較部６４０は、第ｎプリミティブごとに、第１体積演算部６１０で演算されたモデル体積と第２体積演算部６３０で演算されたプリミティブ体積との差を演算し、演算された値のうち、最小値を持つ第ｎプリミティブをモデルプリミティブとして、出力端子ＯＵＴ  １を通じて出力する。
【００４６】
図７Ａないし図７Ｃは、図２に図示された映像分割部２２０及び検索部２３０の動作を説明するための参考図である。
【００４７】
図７Ａに示したように、プリミティブ生成部２１０及び映像分割部２２０に与えられた映像７１０には４つの客体が含まれ、プリミティブ生成部２１０は、その４つの客体ごとに客体プリミティブ７２０、７３０、７４０、７５０を生成し、映像分割部２２０は、映像７１０を分割して２７個のボクセルを生成した。
【００４８】
図７Ｂは、図７Ａに図示された映像７１０をＡの観点から眺めたものである。表記された０、１、２は、説明の便宜上付与されたインデックスであり、それぞれのボクセルは、そのインデックスにより座標値を持つことができる。図示されたように、識別番号７２０の客体プリミティブは、（０，１）の座標値を持つボクセルに存在し、識別番号７３０の客体プリミティブは、（０，１）の座標値を持つボクセルと、（０，２）の座標値を持つボクセルとに存在し、識別番号７４０の客体プリミティブは、（１，０）の座標値を持つボクセルと、（２，０）の座標値を持つボクセルと、（１，１）の座標値を持つボクセルと、（２，１）の座標値を持つボクセルとに存在し、識別番号７５０の客体プリミティブは、（２，２）の座標値を持つボクセルに存在する。この場合、もし、本発明が客体と客体との間に衝突が発生するかどうかを感知しようとするならば、検索部２３０は、‘複数の客体プリミティブが存在するボクセル’、すなわち、‘（０，１）の座標値を持つボクセル’を、あらゆる生成されたボクセルのうちで検索する。すなわち、本発明は、客体と客体との間に衝突が発生するかどうかを検査するに当たって、映像を構成するあらゆるボクセルを検査せず、その検索された一つ以上のボクセルに限って検査できる。
【００４９】
同様に、本発明は、背景と客体との間に衝突が発生するかどうかを検査するに当っても、映像を構成するあらゆるボクセルを検査せず、その検索された一つ以上のボクセルに限って検査することもできる。ただし、背景は、映像７１０で客体より相対的に広い領域を占めるので、背景と客体との間に衝突が発生するかどうかを検査するために、検査される対象の単位はボクセルより小さな単位であることが望ましい。すなわち、インデックスは、図７Ｂに示したように、ボクセルごとに付与されることもあり、図７Ｃに示したように、ボクセルをなす領域のうち、一部領域ごとに付与されることもある。図７Ｃによれば、もし、図７Ｂに図示された映像７１０のあらゆる領域に背景が存在し、本発明は、客体と背景との間に衝突が発生するかどうかを感知しようとする場合、検索部２３０は、‘客体プリミティブと背景プリミティブが存在するボクセル’として、‘（０，１，ａ）の座標値を持つボクセル、（０，１，ｂ）の座標値を持つボクセル、（０，２，ａ）の座標値を持つボクセル、（０，２，ｂ）の座標値を持つボクセル、（１，０，ｂ）の座標値を持つボクセル、（１，１，ａ）の座標値を持つボクセル、（１，１，ｂ）の座標値を持つボクセル、（２，１，ａ）の座標値を持つボクセル、（２，１，ｂ）の座標値を持つボクセル、（２，２，ａ）の座標値を持つボクセル、（２，２，ｂ）の座標値を持つボクセル’を、あらゆる生成されたボクセルのうちで検索する。
【００５０】
図８は、本発明による衝突感知方法を説明するための一実施形態のフローチャートであり、映像に含まれたモデル間に発生する衝突をリアルタイムで感知するステップ（第８１０〜８３０ステップ）からなる。
【００５１】
まず、プリミティブ生成部２１０は、与えられた映像に含まれたモデルごとにそれぞれのプリミティブを生成する（第８１０ステップ）。すなわち、第８１０ステップは、背景プリミティブと一つ以上の客体プリミティブとを生成する。
【００５２】
一方、映像分割部２２０は、その映像を分割して複数のボクセルを生成する（第８２０ステップ）。第８２０ステップは、第８１０ステップと同時に行われるか、または、第８１０ステップ前に行われることもある。
【００５３】
第８１０ステップ及び第８２０ステップ後に、検索部２３０は、複数のモデルプリミティブが存在するボクセルを第８２０ステップで生成されたあらゆるボクセルのうちで検索し、衝突如何検査部２４０は、モデルプリミティブ間に衝突が発生するかどうかをその検索されたボクセルごとに判断し、モデルプリミティブ間に衝突が発生すると判断されれば、衝突感知部２５０は、“衝突が発生する”と感知する（第８３０ステップ）。
【００５４】
図９は、図８に図示された第８３０ステップについての本発明による望ましい一実施形態８３０Ａのフローチャートであり、複数のモデルプリミティブが存在するボクセルごとに、そのモデルプリミティブ間に衝突が発生するかどうかを検査し、検査された結果に応答してモデルの衝突を感知するステップ（第９１０〜９６０ステップ）からなる。
【００５５】
まず、検索部９１０は、背景プリミティブと客体プリミティブとが存在するボクセルを、第８２０ステップで生成されたあらゆるボクセルのうちで検索する（第９１０ステップ）。
【００５６】
第９１０ステップ後に、衝突如何検査部２４０は、第９１０ステップで検索されたボクセルで、背景プリミティブと客体プリミティブとが衝突するかどうかを判断する（第９２０ステップ）。
【００５７】
もし、第９２０ステップで衝突しないと判断されれば、検索部９１０は、複数の客体プリミティブが存在するボクセルを、第８２０ステップで生成されたあらゆるボクセルのうちで検索する（第９３０ステップ）。
【００５８】
第９３０ステップ後に、衝突如何検査部２４０は、第９３０ステップで検索されたボクセルで客体プリミティブ間に衝突が発生するかどうかを判断する（第９４０ステップ）。
【００５９】
もし、第９４０ステップで衝突が発生すると判断されれば、衝突感知部２５０は、第９３０ステップで検索されたボクセルで‘客体間の衝突が発生する’と感知する（第９５０ステップ）。
【００６０】
一方、第９２０ステップで衝突が発生すると判断されれば、衝突感知部２５０は、第９１０ステップで検索されたボクセルで‘客体が背景に衝突する’と感知する（第９６０ステップ）。
【００６１】
本発明による衝突感知方法は、コンピュータで読み取り可能な記録媒体にコンピュータで読み取り可能なコードとして具現されうる。ここで、コンピュータで読み取り可能な記録媒体は、コンピュータシステムによって読み取られるデータが保存されるあらゆる種類の記録装置を含む。コンピュータで読み取り可能な記録媒体の例には、ＲＯＭ、ＲＡＭ、ＣＤ−ＲＯＭ、磁気テープ、フロッピー（登録商標）ディスク、光データ保存装置などがある。また、キャリアウェーブ（例えば、インターネットを通じた伝送）の形態で具現されるものも含む。また、コンピュータで読み取り可能な記録媒体は、ネットワークに連結されたコンピュータシステムに分散されて、分散方式でコンピュータで読み取り可能なコードが保存されて行われうる。
【００６２】
以上、図面と明細書で最適実施形態が開示された。ここで特定の用語が使われたが、これは単に本発明を説明するための目的で使われたものであり、意味限定や特許請求の範囲に記載された本発明の範囲を制限するために使われたものではない。したがって、当業者ならば、これより多様な変形及び均等な他の実施形態が可能であるという点を理解できるであろう。したがって、本発明の真の技術的保護範囲は、特許請求の範囲の技術的思想により定められねばならない。
【産業上の利用可能性】
【００６３】
本発明は、衝突感知装置関連の技術分野に好適に用いられる。
【図面の簡単な説明】
【００６４】
【図１】ワールド、客体、及び背景を説明するための参考図である。
【図２】本発明による衝突感知装置を説明するためのブロック図である。
【図３Ａ】モデルプリミティブを説明するための参考図である。
【図３Ｂ】モデルプリミティブを説明するための参考図である。
【図３Ｃ】モデルプリミティブを説明するための参考図である。
【図３Ｄ】モデルプリミティブを説明するための参考図である。
【図４Ａ】モデルプリミティブが持つ形状の一例を示す図である。
【図４Ｂ】モデルプリミティブが持つ形状の一例を示す図である。
【図４Ｃ】モデルプリミティブが持つ形状の一例を示す図である。
【図４Ｄ】モデルプリミティブが持つ形状の一例を示す図である。
【図５Ａ】モデルプリミティブが持つ形状のうち、最も望ましい形状を説明するための参考図である。
【図５Ｂ】モデルプリミティブが持つ形状のうち、最も望ましい形状を説明するための参考図である。
【図５Ｃ】モデルプリミティブが持つ形状のうち、最も望ましい形状を説明するための参考図である。
【図６】図２に図示されたプリミティブ生成部２１０についての本発明による望ましい一実施形態２１０Ａを説明するためのブロック図である。
【図７Ａ】図２に図示された映像分割部２２０及び検索部２３０の動作を説明するための参考図である。
【図７Ｂ】図２に図示された映像分割部２２０及び検索部２３０の動作を説明するための参考図である。
【図７Ｃ】図２に図示された映像分割部２２０及び検索部２３０の動作を説明するための参考図である。
【図８】本発明による衝突感知方法を説明するためのフローチャートである。
【図９】図８に図示された第８３０ステップについての本発明による望ましい一実施形態８３０Ａのフローチャートである。
【符号の説明】
【００６５】
２１０  プリミティブ生成部
２２０  映像分割部
２３０  検索部
２４０  衝突如何検査部
２５０  衝突感知部
３１０、３２０、３３０、３４０、５１０、５２０、５３０、７２０、７３０、７４０、７５０  客体プリミティブ
４１０  ３次元軸
４２０  ＡＡＢＢ
４３０  ＯＢＢ
４４０  カプセル
４５０  球
６１０、６３０  第１体積演算部
６２０  仮想モデル生成部
７１０  映像
【図１】
2007242022.tif 000004
【図２】
2007242022.tif 000005
【図３Ａ】
2007242022.tif 000006
【図３Ｂ】
2007242022.tif 000007
【図３Ｃ】
2007242022.tif 000008
【図３Ｄ】
2007242022.tif 000009
【図４Ａ】
2007242022.tif 000010
【図４Ｂ】
2007242022.tif 000011
【図４Ｃ】
2007242022.tif 000012
【図４Ｄ】
2007242022.tif 000013
【図５Ａ】
2007242022.tif 000014
【図５Ｂ】
2007242022.tif 000015
【図５Ｃ】
2007242022.tif 000016
【図６】
2007242022.tif 000017
【図７Ａ】
2007242022.tif 000018
【図７Ｂ】
2007242022.tif 000019
【図７Ｃ】
2007242022.tif 000020
【図８】
2007242022.tif 000021
【図９】
2007242022.tif 000022