(57)【特許請求の範囲】
【請求項１】
N（Nは3以上の整数）次元空間上におけるN-1次曲面を指定した検索クエリを受け取るクエリ受取部と、
前記検索クエリによって指定されるN-1次曲面が、前記N次元空間上に配置されたN次元直方体と交差するかを判定する衝突判定部と、
を備え、
前記衝突判定部は、前記N次元直方体のX（Xは0以上N-1以下のすべての整数）次元面の少なくともいずれかの少なくとも一部が、前記N-1次曲面に含まれるかを判定する、第0次元〜第N-1次元にそれぞれ対応する第0〜第N-1判定機能を含む複数の判定機能を備え、前記複数の判定機能を用いて前記N次元直方体と交差するかの判定を行い、
前記衝突判定部は、前記複数の判定機能を、１つの判定機能での判定が得られたら次の判定機能を実行するように、前記第0の判定機能から番号の小さい順に実行し、交差するとの判定が得られたら、当該交差するとの判定が得られた判定機能より後の番号の判定機能の実行を省略する
オブジェクト検索装置。
【請求項２】
N（Nは3以上の整数）次元空間上におけるN-1次曲面を指定した検索クエリを受け取るクエリ受取部と、
前記検索クエリによって指定されるN-1次曲面が、前記N次元空間上に配置されたN次元直方体と交差するかを判定する衝突判定部と、
を備え、
前記衝突判定部は、前記N次元直方体のX（Xは0以上N-1以下のすべての整数）次元面の少なくともいずれかの少なくとも一部が、前記N-1次曲面に含まれるかを判定する第0〜第N-1判定機能を含む複数の判定機能を備え、前記複数の判定機能を用いて前記N次元直方体と交差するかの判定を実行し、
前記衝突判定部は、前記複数の判定機能を並列して実行し、いずれか1つの判定機能で交差するとの判定が得られたら、前記いずれか1つの判定機能以外の他の判定機能の実行を停止する
オブジェクト検索装置。
【請求項３】
前記複数の判定機能は、前記N次元直方体に前記N-1次曲面が包含されるかを判定する第Nの判定機能を含む請求項1または2に記載のオブジェクト検索装置。
【請求項４】
前記衝突判定部は、前記N-1次曲面が、前記N次元空間上に配置された複数のN次元直方体と交差するかの判定を並行して行う
請求項1ないし3のいずれか一項に記載のオブジェクト検索装置。
【請求項５】
前記N-1次曲面の最小外包N次直方体を計算する計算部と、
前記N-1次曲面の最小外包N次直方体と、前記N次元直方体が交差するかを判定する初期フィルタリング部をさらに備え、
前記衝突判定部は、前記初期フィルタリング部で前記最小外包N次直方体と交差すると判定されたN次元直方体のみを交差判定の対象とする
請求項1ないし4のいずれか一項に記載のオブジェクト検索装置。
【請求項６】
前記N次元直方体は、前記N次元空間に配置されたオブジェクトの最小外包N次元直方体である
請求項1ないし5のいずれか一項に記載のオブジェクト検索装置。
【請求項７】
前記Nは３である
請求項1ないし6のいずれか一項に記載のオブジェクト検索装置。
【請求項８】
コンピュータが、
N（Nは3以上の整数）次元空間上におけるN-1次曲面を指定した検索クエリを受け取るクエリ受取ステップと、
前記検索クエリによって指定されるN-1次曲面が、前記N次元空間上に配置されたN次元直方体と交差するかを判定する衝突判定ステップと、
を備え、
前記衝突判定ステップは、
前記N次元直方体のX（Xは0以上N-1以下のすべての整数）次元面の少なくともいずれかの少なくとも一部が、前記N-1次曲面に含まれるかを判定する、第0次元〜第N-1次元にそれぞれ対応する第0〜第N-1判定機能を含む複数の判定機能を、１つの判定機能での判定が得られたら次の判定機能を実行するように、前記第0の判定機能から番号の小さい順に実行し、交差するとの判定が得られたら、当該交差するとの判定が得られた判定機能より後の番号の判定機能の実行を省略するオブジェクト検索方法。
【請求項９】
コンピュータが、
N（Nは3以上の整数）次元空間上におけるN-1次曲面を指定した検索クエリを受け取るクエリ受取ステップと、
前記検索クエリによって指定されるN-1次曲面が、前記N次元空間上に配置されたN次元直方体と交差するかを判定する衝突判定ステップと、
を備え、
前記衝突判定ステップは、
前記N次元直方体のX（Xは0以上N-1以下のすべての整数）次元面の少なくともいずれかの少なくとも一部が、前記N-1次曲面に含まれるかを判定する第0〜第N-1判定機能を含む複数の判定機能を並列して実行し、いずれか1つの判定機能で交差するとの判定が得られたら、前記いずれか1つの判定機能以外の他の判定機能の実行を停止するオブジェクト検索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本実施形態は、オブジェクト検索装置およびその方法に関し、たとえばGIS や CAD 等のアプリケーションの3次元（3D）オブジェクトを管理する方法に関する。
【背景技術】
【０００２】
3Dデータベースは、時空間上に配置されたオブジェクトの集合を管理する。範囲を指定したクエリを受け取り、その範囲にあるオブジェクト一覧を返す機能を持つ。ベースとなるデータ構造・インデクスとしては、R-tree、Quad-treeやその拡張が用いられている。
【０００３】
従来、二次曲面を利用した干渉・衝突判定の機能が知られている。これは多面体として表現されたオブジェクトを近似する二次曲面を生成し、二次曲面によって衝突判定を簡単にしようとするものである。これは、多くて 10000 個程度の部品が密に詰まった機械の部品同士の衝突判定を行う。そのため、近似の正確さは重要視しておらず、最小包含直方体で非常に荒く近似している。一方で、指定した二次曲面との交差判定を高速化するために判定手順を細かく制御している。
【０００４】
また、論文としての関連は、R-tree (Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47-57. ISBN 0-89791-128-8) や Quad-tree (Raphael Finkel and J.L. Bentley (1974年). “Quad Trees: A Data Structure for Retrieval on Composite Keys”. Acta Informatica 4 (1): 1?9. doi:10.1007/BF00288933) が知られている。これらは、100 万個程度の大量のオブジェクトを扱うことを目的としたデータ構造であるが、これらはクエリで指定する範囲も長方形としているため、二次曲面による細かいクエリ制御は行えない。
【先行技術文献】
【特許文献】
【０００５】
【特許文献１】特許第3854033号
【発明の概要】
【発明が解決しようとする課題】
【０００６】
R-treeやQuad-treeは、各オブジェクトを、それを取り囲む最小の直方体（MBB）の単位で管理し、クエリで指定できる範囲も直方体である。
【０００７】
しかし太陽光発電（PV：Photovoltaic power generation）装置の配置を管理する3Dデータベースでは、ビルの影に入るオブジェクト（PV）の一覧や、ある視点からの視界内に入るオブジェクトの一覧、指定した地点からの半径n km以内にあるオブジェクト一覧などのクエリが頻繁に発生する。
【０００８】
本発明の一側面は、N次元空間上のN-1次曲面と、N次元直方体との交差判定を高速に行うことを目的とする。
【課題を解決するための手段】
【０００９】
本発明の一態様としてのオブジェクト検索装置は、クエリ受取部と、衝突判定部と、を備える。
【００１０】
前記クエリ受取部は、N（Nは3以上の整数）次元空間上におけるN-1次曲面を指定した検索クエリを受け取る
前記衝突判定部は、前記検索クエリによって指定されるN-1次曲面が、前記N次元空間上に配置されたN次元直方体と交差するかを判定する。
【００１１】
前記衝突判定部は、前記N次元直方体のX（Xは0以上N-1以下のすべての整数）次元面の少なくともいずれかの少なくとも一部が、前記N-1次曲面に含まれるかを判定する第0〜第N-1判定機能を含む複数の判定機能を備え、前記複数の判定機能を用いて前記N次元直方体と交差するかの判定を行う。
【図面の簡単な説明】
【００１２】
【図１】本発明の実施形態にかかるオブジェクト検索装置を示す。
【図２】図1の装置の第一の動作例のフローチャートを示す。
【図３】図1の装置の第二の動作例のフローチャートを示す。
【図４】葉が1つの木の例を示す。
【図５】ベクトル積の値の一例を示す。
【図６】実施例Aに係る手続きの例を示す。
【図７】実施例Aに係る衝突判定結果を示す。
【図８】実施例Bに係る手続きの例を示す。
【図９】実施例Bに係る衝突判定結果を示す。
【図１０】実施例Cに係る手続きの例を示す。
【図１１】実施例Cに係る衝突判定結果を示す。
【図１２】実施例Dに係る手続きの例を示す。
【図１３】実施例Dに係る衝突判定結果を示す。
【図１４】実施例Eに係る手続きの例を示す。
【図１５】実施例Eに係る衝突判定結果を示す。
【図１６】3つの葉の木の例を示す。
【図１７】ベクトル積の値の他の例を示す。
【発明を実施するための形態】
【００１３】
本発明の実施形態は、二次曲面（円錐や円柱、球など）を指定したクエリを受け取り、その二次曲面と重なり（交差）を持つ、最小外包直方体（MBB）の一覧を効率的に計算する。二次曲面と直方体（MBB）の衝突判定はそのままでは非効率なため、二次曲面のMBBと衝突するオブジェクトMBBだけをあらかじめ抽出することで、判定対象の候補を減らす工夫を行う。また、 計算の簡単な低次元での衝突判定を先に行い、それで衝突しないと判定されたものだけ高次元での衝突判定を行うという工夫も行う。また、各次元での衝突判定での計算量を低減するため、MBBごとに、頂点のベクトルの積の値を事前に計算し、キャッシュしておくことも行う。
【００１４】
このような工夫により、指定した二次曲面と衝突するオブジェクトMBBの一覧を効率的に得られる。太陽光発電（PV：Photovoltaic power generation）装置の場合は、ビル等の物陰になるかどうかを考慮したPV装置の配置の検討が可能になる。また、高速な3Dレンダリングが可能になる。機械の部品配置や建物の設計等、CAD一般への応用も可能である。
【００１５】
本実施形態を用いることで、100 万個以上のオブジェクトが疎に配置された空間に、指定した二次曲面に含まれうるオブジェクトの一覧を、高速に得ることが可能である。
【００１６】
以下、図面を参照しながら、本実施形態を詳細に説明する。
【００１７】
図1に、本発明の実施形態にかかる3D データベースのオブジェクト検索装置を示す。
【００１８】
オブジェクト階層構造構成部101は、外部から与えられたオブジェクトの最小外包直方体（MBB）を計算する。また、空間的に距離の近いオブジェクトをまとめて、まとめたものの最小外包直方体（MBB）を計算する。これを繰り返すことで、オブジェクトMBBの階層構造を生成する。
【００１９】
オブジェクトMBBツリー格納部102は、オブジェクト階層構造構成部101が出力した階層構造を記憶する。
【００２０】
ベクトル積事前計算部103は、各オブジェクトのMBBのそれぞれにつき、各軸のベクトル積を計算する。
【００２１】
MBBベクトル積キャッシュ部104は、ベクトル積事前計算部103が出力したベクトル積を記憶する。
【００２２】
二次曲面MBB計算部105は、検索の対象範囲を表す二次曲面の係数を含む二次曲面クエリを受け取り、二次曲面のMBBを計算する。
【００２３】
初期フィルタリング部106は、オブジェクトMBBツリー格納部102の各階層から、二次曲面のMBBと共通部分を持つ（交差する）部分木のみを列挙する。
【００２４】
衝突判定部（低次元優先衝突判定部）107は、初期フィルタリング部106が列挙した部分木から、二次曲面クエリの二次曲面と共通部分を持つ要素のみを抽出する。
【００２５】
以下、各部の詳細を説明する。
【００２６】
（オブジェクト階層構造構成部101）
オブジェクト階層構造構成部101は、オブジェクトごとに、最小外包直方体 (Minimum Bounded Box; MBB) を計算する。最小外包直方体は、各辺が x 軸、y 軸、z 軸のいずれかに平行である。なお、本実施形態は、オブジェクトのMBBに限定されず、一般に３次元空間に配置された直方体に対して、二次曲面との交差判定に適用可能である。また、交差判定の対象とする直方体は、x 軸、y 軸、z 軸に平行でなくてもかまわない。
【００２７】
次に MBB が近接するオブジェクト同士を1 かたまりとし、そのかたまりとしての MBB を計算する。かたまりをノードとし、個々のオブジェクトを葉として、さらにかたまり同士をノードとすることを繰り返して、バランスされた木構造で表現される階層構造を表現していく。また、オブジェクトの挿入や削除が発生した場合にも、特性を維持するように木構造を変更していく。
【００２８】
この部は既存手法である R-tree (Antonin Guttman: R-Trees: A Dynamic Index Structure for Spatial Searching, Proc. 1984 ACM SIGMOD International Conference on Management of Data, pp. 47-57. ISBN 0-89791-128-8) や Quad-tree と同じであるため、詳しくは当該文献を参照されたい。
【００２９】
（オブジェクトMBBツリー格納部102）
オブジェクトMBBツリー格納部102は、オブジェクト階層構造構成部101が生成した階層構造を、オブジェクトのMBBごとに、内部に記憶する。
【００３０】
（ベクトル積事前計算部103）
ベクトル積事前計算部103は、MBBの頂点ごとのベクトル積を計算する。本実施形態でベクトル積とは、ある代表の頂点を (x0, y0, z0) とし、その頂点と正反対の位置にある頂点を (x1, y1, z1) とした時、以下の18個の値（積）のことである。
x0x0 x0y0 x0y1 x0z0 x0z1
x1x1 x1y0 x1y1 x1z0 x1z1
y0y0 y0z0 y0z1
y1y1 y1z0 y1z1
z0z0
z1z1
【００３１】
（MBBベクトル積キャッシュ部104）
MBBベクトル積キャッシュ部104は、ベクトル積事前計算部103が計算したベクトル積を記憶する。
【００３２】
（二次曲面MBB計算部105）
二次曲面MBB計算部105は、検索の対象範囲を表す二次曲面の係数を含む二次曲面クエリを受け取り、二次曲面のMBBを計算する。このMBBは、二次曲面が有限(球または楕円体)の時のみ定義される。そうでない場合には、二次曲面MBB計算部105は、無限領域を示すMBB(すなわち、ある頂点が(-∞,-∞,-∞)であり、その正反対の位置にある頂点が(∞,∞,∞)であるようなMBB)を返す。
【００３３】
（初期フィルタリング部106）
初期フィルタリング部106は、オブジェクトMBBツリー格納部102の各階層から、二次曲面のMBB(以下クエリMBBと呼ぶ)と共通部分を持つ部分木またはオブジェクトを列挙する。
【００３４】
具体的には、オブジェクトの集合を表現する木構造の最上位のノードのMBBと、クエリMBBとの交差判定を行い、交差する場合にはそのノードの各子ノードとクエリMBBとの交差判定を行う。
【００３５】
クエリMBBと交差を持つ子ノードを発見したら、その子ノードを衝突判定部107に出力し、二次曲面と正確に交差を持つか判定する。交差をもつ場合は、その子ノードに対してさらに再帰的に、クエリMBBとの交差判定を繰り返していく。
【００３６】
（衝突判定部107）
衝突判定部107は、二次曲面クエリと、初期フィルタリング部106が列挙した部分木またはオブジェクトのMBBとを受け取り、交差判定を行う。
【００３７】
交差判定はMBBの次元ごとに行う。
すなわち、
・0次元である点(MBBの頂点)を8個列挙し、いずれかが二次曲面クエリの二次曲面に含まれているかどうかを判定することと（C0テスト）、
・1次元である線分(MBBの辺)を12個列挙し、いずれかの少なくとも一部が二次曲面クエリの二次曲面に含まれているかどうかを判定することと（C1テスト）、
・2次元である長方形(MBBの面)を6個列挙し、いずれかの少なくとも一部が、二次曲面クエリの二次曲面に含まれているかどうかを判定することと（C2テスト）、
・3次元である体(MBBの体)に、二次曲面クエリの二次曲面が包含されているかどうかを判定すること（C3テスト）、
の4種類、計27個の判定を行う。
【００３８】
衝突判定部107は、C0テストを行う判定機能（判定部）、C1テストを行う判定機能、C2テストを行う判定機能、C3テストを行う判定機能を備える。
【００３９】
いずれかの判定で、含まれる（交差有り）と判定された場合は、MBBは、全体として二次曲面と交差を持つことが分かる。
【００４０】
交差を持つとわかった場合、初期フィルタリング部106から部分木を受け取った場合は、初期フィルタリング部106に「交差あり」の判定結果を返す。オブジェクトを受け取った場合は、当該オブジェクトを、衝突オブジェクトとして出力する。
【００４１】
衝突判定部107の第一の動作例として、低次元の判定から優先的に行い、低次元の判定のいずれかで交差すると判定された場合は「交差あり」として、より上位次元での判定を行わないようにする。
【００４２】
衝突判定部107は、第二の動作例として、低次元での判定と高次元での判定を並列して進め、低次元で衝突すると判定された場合はその時点で終了し、低次元の判定で衝突しないと判定された場合は、高次元での比較の結果を待つようにする。
【００４３】
図2に第一の動作例のフローチャートを示す。
【００４４】
二次曲面クエリを読み込み（S11）、オブジェクトMBBごとに、ステップS12からS21を繰り返す。ベクトル積キャッシュを読み込み（S12）、C0テストを行う（S13）。C0テストで交差ありの判定が得られたら（S14のYES）、オブジェクトIDを出力し（S21）、そうでなければ（S14のNO）、C1テストを行う（S15）。C1テストで交差ありの判定が得られたら（S16のYES）、オブジェクトIDを出力し（S21）、そうでなければ（S16のNO）、C2テストを行う（S17）。C2テストで交差ありの判定が得られたら（S18のYES）、オブジェクトIDを出力し（S21）、そうでなければ（S18のNO）、C3テストを行う（S19）。C3テストで交差ありの判定が得られたら（S20のYES）、オブジェクトIDを出力し（S21）、そうでなければ（S20のNO）、当該オブジェクトMBBに対し、最終的に交差なしの判定を下す。
【００４５】
図3に第二の動作例のフローチャートを示す。
【００４６】
二次曲面クエリを読み込み（S31）、オブジェクトMBBごとに、ステップS32からS43を繰り返す。ベクトル積キャッシュを読み込み（S32）、C0テスト、C1テスト、C2テスト、C3テストを並行して行う（S34、S35、S36、S37）。これは、たとえば各テストをそれぞれ別個の演算装置（装置能力はそれぞれ異なっていても同じでもよい）を使って行う。いずれかのテストで交差ありの判定が得られたかを検査する（S38、S39、S40、S41）。いずれかのテストで交差ありの判定が得られたら、オブジェクトIDを出力し（S42）、その他の継続中のテストを終了する。いずれのテストでも交差ありの判定が得られなかったら、最終的に交差なし（衝突無し）の判定を下す。なお、ステップS33のブロック内に記述された“fork”は並列処理の分岐開始を表し、ステップS43のブロック内に記述された“join”は並列処理の同期(バリア同期)を表す。
【００４７】
ここで衝突判定部は、上記C0、C1、C2、C3の判定機能をすべて搭載することは必須ではない。たとえば二次曲面がオブジェクトのMBBに包含されないことが事前に分かっている場合、またはそのような検査が不要な場合は、C0、C1、C2の判定機能のみを備えればよい。
【００４８】
本実施形態では、3次元空間の場合を説明するが、一般にN（Nは3以上の整数）次元空間に拡張することも可能である。この場合は、上記2次曲面をN-1次曲面と読み替えればよい。また、上記最小外包直方体または外包直方体を、最小外包N次元直方体または外包N次元直方体と読み替えればよい。また、点、線および面等を、X（Xは0以上N-1以下の整数）次元面と読み替えればよい。
【００４９】
（実施例A）
本実施例では、オブジェクトとして単位立方体(すなわち、ある頂点が(0,0,0)であり、その正反対の位置の頂点が(1,1,1)であるような立方体)が、ただ1つある場合を想定する。この場合に、(1,0,1)が中心であり半径1/4であるような球を表す二次曲面をクエリとして与える。以下、このときの各部の挙動の例を説明する。
【００５０】
このクエリの式は以下のようになる。
0>=z^2-2*z+y^2+x^2-2*x+31/16
【００５１】
［実施例Aにおけるオブジェクト階層構造構成部101の動作］
唯一の立方体を受け取り、そのMBBを計算する。この場合、MBBは、元の立方体と一致する。扱うオブジェクトがただ1つであるため、図4に示すように、葉が1つの木が生成される。
【００５２】
［実施例AにおけるオブジェクトMBBツリー格納部102の動作］
オブジェクト階層構造構成部101により生成された、葉が1つの木（図4）を記憶する。
【００５３】
［実施例Aにおけるベクトル積事前計算部103の動作］
代表の頂点(0,0,0)と、その正反対の位置の点(1,1,1)に対して、前述の積の値（18個）を計算する。
【００５４】
［実施例AにおけるMBBベクトル積キャッシュ部104の動作］
ベクトル積事前計算部103により計算された積の値を、図5に示すようなテーブルの形式で、記憶する。
【００５５】
［実施例Aにおける二次曲面MBB計算部105の動作］
本実施例での二次曲面クエリの二次曲面は球であるため、(3/4,3/4,3/4)-(5/4,5/4,5/4)がMBBとして計算される。
【００５６】
［実施例Aにおける初期フィルタリング部106の動作］
二次曲面クエリのMBBである(3/4,3/4,3/4)-(5/4,5/4,5/4)と、オブジェクトMBBである(0,0,0)-(1,1,1)が交差するかどうかを判定する。
【００５７】
x軸、y軸、z軸に並行な直方体同士の交差判定は、軸ごとに交差を持つかどうかを独立して判定し、すべてで交差する場合に直方体同士が交差すると判定できる。このため、この判定は、計算量的に簡単である。
【００５８】
まずx軸に注目し、0から1の範囲と、3/4から5/4の範囲が交差を持つかどうかを判定する。この場合は、3/4から1の範囲が交差する。
【００５９】
次にy軸に注目し、0から1の範囲と、3/4から5/4の範囲が交差を持つかどうかを判定する。この場合は、3/4から1の範囲が交差する。
【００６０】
次にz軸に注目し、0から1の範囲と、3/4から5/4の範囲が交差を持つかどうかを判定する。この場合は、3/4から1の範囲が交差する。
【００６１】
以上から、二次曲面クエリMBBは、オブジェクトMBBと交差する。よって、このオブジェクトを、衝突判定部107に出力する。
【００６２】
［実施例Aにおける衝突判定部107の動作］
二次曲面クエリの二次曲面と、オブジェクトMBBである(0,0,0)-(1,1,1)が交差するかどうかを判定する。
【００６３】
まず、C0テストとして、8つの頂点のいずれかが二次曲面に含まれているかどうかを判定する。
【００６４】
C0テストでは、頂点の値を二次曲面の式(以下二次形式という)に代入し、その値が0以下であるかどうかを見ればよい。二次形式は、上記した0>=z^2-2*z+y^2+x^2-2*x+31/16である。
【００６５】
まず、代表の頂点である(0,0,0)を二次形式に代入すると、31/16となる。この値は0より大きいため、この点は二次曲面に含まれないことが分かる。
【００６６】
次に、代表の頂点である(0,0,1)を二次形式に代入すると、15/16となる。この値は0より大きいため、この点は二次曲面に含まれないことが分かる。
【００６７】
次に、代表の頂点である(0,1,0)を二次形式に代入すると、47/16となる。この値は0より大きいため、この点は二次曲面に含まれないことが分かる。
【００６８】
次に、代表の頂点である(0,1,1)を二次形式に代入すると、31/16となる。この値は0より大きいため、この点は二次曲面に含まれないことが分かる。
【００６９】
次に、代表の頂点である(1,0,0)を二次形式に代入すると、15/16となる。この値は0より大きいため、この点は二次曲面に含まれないことが分かる。
【００７０】
次に、代表の頂点である(1,0,1)を二次形式に代入すると、-1/16となる。この値は0以下であるため、この点は二次曲面に含まれることが分かる。
【００７１】
ある点が二次曲面に含まれるという事は、このMBBは二次曲面と交差を持つということになる。
【００７２】
以上の計算をする際には、z^2、y^2、x^2の値が頻繁に必要になるため、この値はMBBベクトル積キャッシュ部104に記憶したベクトル積キャッシュを参照することで、高速化する。
【００７３】
このMBBはオブジェクトのMBBであるため、衝突判定部107は、このオブジェクトのIDを出力する。
【００７４】
図6に、以上の手続きを表にしたものを示す。
【００７５】
［実施例Aの効果］
オブジェクトの集合に対し、二次曲面を検索範囲として指定したクエリと交差を持つオブジェクトの部分集合を高速に得ることができる。
【００７６】
今回のオブジェクトとクエリは、図7に示すように実際に交差を持つので、正しく判定できていることがわかる。なお、図7は、Maximaにより描いたものである。
【００７７】
（実施例B）
本実施例では、オブジェクトとして単位立方体(すなわち、ある頂点が(0,0,0)であり、その正反対の位置の頂点が(1,1,1)であるような立方体)がただ1つある場合を想定する。この場合に、 (1,0,2/3)が中心であり半径1/4であるような球を表す二次曲面をクエリとして与える。以下、このときの各部の挙動の例を説明する。
【００７８】
このクエリの式は以下のようになる。
0>=z^2-4*z/3+y^2+x^2-2*x+199/144
【００７９】
［実施例Bにおけるオブジェクト階層構造構成部101の動作］
実施例Aと全く同じであるため説明を省略する。
【００８０】
［実施例BにおけるオブジェクトMBBツリー格納部102の動作］
実施例Aと全く同じであるため説明を省略する。
【００８１】
［実施例Bにおけるベクトル積事前計算部103の動作］
実施例Aと全く同じであるため説明を省略する。
【００８２】
［実施例BにおけるMBBベクトル積キャッシュ部104の動作］
実施例Aと全く同じであるため説明を省略する。
【００８３】
［実施例Bにおける二次曲面MBB計算部105の動作］
本実施例での二次曲面クエリの二次曲面は球であるため、 (3/4,3/4,5/12)-(5/4,5/4,11/12)がMBBとして計算される。
【００８４】
［実施例Bにおける初期フィルタリング部106の動作］
二次曲面クエリのMBBである(3/4,3/4,5/12)-(5/4,5/4,11/12)と、オブジェクトMBBである(0,0,0)-(1,1,1)が交差するかどうかを判定する。
【００８５】
実施例Aで述べたように、x軸、y軸、z軸に並行な直方体同士の交差判定は、各軸ごとに交差を持つかどうかを独立して判定し、すべてで交差する場合に直方体同士が交差すると判定できる。このため、この判定は、計算量的に簡単である。
【００８６】
まずx軸に注目し、0から1の範囲と3/4から5/4の範囲が交差を持つかどうかを判定する。この場合は、3/4から1の範囲が交差する。
【００８７】
次にy軸に注目し、0から1の範囲と3/4から5/4の範囲が交差を持つかどうかを判定する。この場合は、3/4から1の範囲が交差する。
【００８８】
次にy軸に注目し、0から1の範囲と5/12から11/12の範囲が交差を持つかどうかを判定する。この場合は、5/12から11/12の範囲が交差する。
【００８９】
以上から、二次曲面クエリMBBはオブジェクトMBBと交差する。よって、このオブジェクトを衝突判定部107に出力する。
【００９０】
［実施例Bにおける衝突判定部107の動作］
二次曲面クエリの二次曲面と、オブジェクトMBBである(0,0,0)-(1,1,1)が交差するかどうかを判定する。
【００９１】
まず、C0のテストとして、8つの頂点のいずれかが二次曲面に含まれているかどうかを判定する。
【００９２】
C0テストでは、頂点の値を二次形式に代入し、その値が0以下であるかどうかを見ればよい。本実施例の二次形式は、上記した0>=z^2-4*z/3+y^2+x^2-2*x+199/144である。
【００９３】
図8に本実施例の手続きを示す。
【００９４】
C0テストであるStep1からStep8までで、いずれの頂点も二次曲面に含まれないことが判定される。
【００９５】
そこで、次にC1のテストとして、12個の辺のいずれかが二次曲面に含まれているかどうかを判定する。
【００９６】
C1テストでは、各辺を通る直線の式を二次形式に代入し、その最小値を示す点と最小値を見ればよい。なぜならば、両端の頂点が二次形式に含まれていないことがわかっているため、交差しているとしたら二次曲線の凸部分が辺の範囲に入っており、かつその二次曲線の最小値が0以下になっている場合だけであるからである。
【００９７】
Step9では、MBBの(0,0,0)-(1,0,0)の辺が二次曲面と交差するかどうかを判定する。(x,y,z)=(u,0,0)を代入し、u^2-2*u+199/144という式を得る。この二次曲線はu=1の時に最小となる。u=1は辺の端点(すなわちMBBの頂点)であるため、C0テストで交差しないことが判定済みである。よってこの辺と二次曲面は交差しない。
【００９８】
Step10からStep16も同様に交差しないと判定される。
【００９９】
Step17では、MBBの(0,0,0)-(0,0,1)の辺が二次曲面と交差するかどうかを判定する。(x,y,z)=(0,0,w)を代入し、w^2-4*w/3+199/144という式を得る。この二次曲線はu=2/3の時に最小となる。この点は辺の範囲(0から1)に収まっており、かつ頂点でもない。二次曲線の最小値を求めるには、w=2/3を代入すればよい。その結果、15/16であるため、0より大きく、最小の点でも交差しないことがわかる。
【０１００】
Step18も同様に交差しないと判定される。
【０１０１】
Step19では、w=2/3の時最小であり、この点での二次曲線の最小値が-1/16で0以下であるため、交差することがわかる。
【０１０２】
よって、このMBBは二次曲面と交差することがわかる。
【０１０３】
このMBBはオブジェクトのMBBであるため、衝突判定部107はこのオブジェクトのIDを出力する。
【０１０４】
［実施例Bの効果］
オブジェクトの集合に対し、二次曲面を検索範囲として指定したクエリと交差を持つオブジェクトの部分集合を高速に得ることができる。
【０１０５】
今回のオブジェクトとクエリは、図9に示すように実際に交差を持つので、正しく判定できていることがわかる。
【０１０６】
（実施例C）
本実施例では、オブジェクトとして単位立方体(すなわち、ある頂点が(0,0,0)であり、その正反対の位置の頂点が(1,1,1)であるような立方体)がただ1つある場合を想定する。この場に、(2/3,0,2/3)が中心であり半径1/4であるような球を表す二次曲面をクエリとして与える。このときの各部の挙動を説明する。
【０１０７】
このクエリの式は以下のようになる。
0>=z^2-4*z/3+y^2+x^2-4*x/3+119/144
【０１０８】
［実施例Cにおけるオブジェクト階層構造構成部101の動作］
実施例Aと全く同じであるため、説明を省略する。
【０１０９】
［実施例CにおけるオブジェクトMBBツリー格納部102の動作］
実施例Aと全く同じであるため、説明を省略する。
【０１１０】
［実施例Cにおけるベクトル積事前計算部103の動作］
実施例Aと全く同じであるため、説明を省略する。
【０１１１】
［実施例CにおけるMBBベクトル積キャッシュ部104の動作］
実施例Aと全く同じであるため、説明を省略する。
【０１１２】
［実施例Cにおける二次曲面MBB計算部105の動作］
本実施例での二次曲面クエリの二次曲面は球であるため、(5/12,3/4,5/12)-(11/12,5/4,11/12)がMBBとして計算される。
【０１１３】
［実施例Cにおける初期フィルタリング部106の動作］
二次曲面クエリのMBBである(5/12,3/4,5/12)-(11/12,5/4,11/12)が、オブジェクトMBBである(0,0,0)-(1,1,1)と交差するかどうかを判定する。
【０１１４】
実施例Aで述べたように、x軸、y軸、z軸に並行な直方体同士の交差判定は、各軸ごとに交差を持つかどうかを独立して判定し、すべてで交差する場合に直方体同士が交差すると判定できる。このため、この判定は、計算量的に簡単である。
【０１１５】
まずx軸に注目し、0から1の範囲と5/12から11/12の範囲が交差を持つかどうかを判定する。この場合は、5/12から11/12の範囲が交差する。
【０１１６】
次にy軸に注目し、0から1の範囲と3/4から5/4の範囲が交差を持つかどうかを判定する。この場合は、3/4から1の範囲が交差する。
【０１１７】
次にy軸に注目し、0から1の範囲と5/12から11/12の範囲が交差を持つかどうかを判定する。この場合は、5/12から11/12の範囲が交差する。
【０１１８】
以上から、二次曲面クエリMBBはオブジェクトMBBと交差する。よって、このオブジェクトを出力する。
【０１１９】
［実施例Cにおける衝突判定部107の動作］
二次曲面クエリの二次曲面が、オブジェクトMBBである(0,0,0)-(1,1,1)と交差するかどうかを判定する。
【０１２０】
図10に、本実施例に係る手続きを示す。
【０１２１】
C0テスト(Step1から8)と、C1テスト(Step9から20)は、実施例A、Bと同様である。これらのテストでは、いずれの頂点、辺も二次曲面と交差しないと判定される。
【０１２２】
そこで次にC2テストとして、面と二次曲面との交差を判定する。
【０１２３】
C2テストでは、各面を通る平面の式を二次形式に代入し、その最小値を示す点と最小値を見ればよい。なぜならば、面の頂点も辺も二次形式に含まれていないことがわかっているため、交差しているとしたら二次曲線の凸部分が面の範囲に入っており、かつその二次曲線の最小値が0以下になっている場合だけであるからである。
【０１２４】
Step21では、MBBの(0,0,0)-(0,1,1)の面が二次曲面と交差するかどうかを判定する。(x,y,z)=(0,v,w)を代入し、w^2-4*w/3+v^2+119/144という式を得る。この二次曲線は(v,w)=(0,2/3)の時に最小となる。この点はMBBの辺上である。辺と二次曲面が交差しないことはC1テストで判定済みであるため、この面と二次曲面は交差しない。
【０１２５】
Step22も同様に交差しないと判定される。
【０１２６】
Step23では、(v,w)=(2/3,2/3)の時に最小となる。この点は面の範囲((0,0)から(1,1))に収まっており、かつ頂点でも辺でもない。二次曲線の最小値を求めるには、(v,w)=(2/3,2/3)を代入すればよい。その結果、-1/16であるため、0以下であり、交差することがわかる。
【０１２７】
よって、このMBBと二次曲面は交差することがわかる。
【０１２８】
このMBBはオブジェクトのMBBであるため、衝突判定部107はこのオブジェクトのIDを出力する。
【０１２９】
［実施例Cの効果］
オブジェクトの集合に対し、二次曲面を検索範囲として指定したクエリと交差を持つオブジェクトの部分集合を高速に得ることができる。
【０１３０】
今回のオブジェクトとクエリは、図11に示すように実際に交差を持つので、正しく判定できていることがわかる。
【０１３１】
（実施例D）
本実施例では、オブジェクトとして単位立方体(すなわち、ある頂点が(0,0,0)であり、その正反対の位置の頂点が(1,1,1)であるような立方体)がただ1つある場合を想定する。この場合に、 (2/3,2/3,2/3)が中心であり半径1/4であるような球を表す二次曲面をクエリとして与える。このときの各部の挙動の例を説明する。
【０１３２】
このクエリの式は以下のようになる。
0>=z^2-4*z/3+y^2-4*y/3+x^2-4*x/3+61/48
【０１３３】
［実施例Dにおけるオブジェクト階層構造構成部101の動作］
実施例Aと全く同じであるため、説明を省略する。
【０１３４】
［実施例DにおけるオブジェクトMBBツリー格納部102の動作］
実施例Aと全く同じであるため、説明を省略する。
【０１３５】
［実施例Dにおけるベクトル積事前計算部103の動作］
実施例Aと全く同じであるため、説明を省略する。
【０１３６】
［実施例DにおけるMBBベクトル積キャッシュ部104の動作］
実施例Aと全く同じであるため、説明を省略する。
【０１３７】
［実施例Dにおける二次曲面MBB計算部105の動作］
本実施例での二次曲面クエリの二次曲面は球であるため、(5/12,5/12,5/12)-(11/12,11/12,11/12)がMBBとして計算される。
【０１３８】
［実施例Dにおける初期フィルタリング部106の動作］
二次曲面クエリのMBBである(5/12,5/12,5/12)-(11/12,11/12,11/12)が、オブジェクトMBBである(0,0,0)-(1,1,1)と交差するかどうかを判定する。
【０１３９】
実施例Aで述べたように、x軸、y軸、z軸に並行な直方体同士の交差判定は、各軸ごとに交差を持つかどうかを独立して判定し、すべてで交差する場合に直方体同士が交差すると判定できる。このため、当該判定は、計算量的に簡単である。
【０１４０】
まずx軸に注目し、0から1の範囲と5/12から11/12の範囲が交差を持つかどうかを判定する。この場合は、5/12から11/12の範囲が交差する。
【０１４１】
次にy軸に注目し、0から1の範囲と5/12から11/12の範囲が交差を持つかどうかを判定する。この場合は、5/12から11/12の範囲が交差する。
【０１４２】
次にy軸に注目し、0から1の範囲と5/12から11/12の範囲が交差を持つかどうかを判定する。この場合は、5/12から11/12の範囲が交差する。
【０１４３】
以上から、二次曲面クエリMBBとオブジェクトMBBは交差する。よって、このオブジェクトを衝突判定部107に出力する。
【０１４４】
［実施例Dにおける衝突判定部107の動作］
二次曲面クエリの二次曲面が、オブジェクトMBBである(0,0,0)-(1,1,1)と交差するかどうかを判定する。
【０１４５】
図12に本実施例に係る手続きを示す。
【０１４６】
C0テスト(Step1から8)とC1テスト(Step9から20)、C2テスト(Step21から26)は、実施例A、B、Cと同様であり、これらのテストでは、いずれの頂点、辺、面も二次曲面と交差しないと判定される。
【０１４７】
そこで、次にC3テストで、体と二次曲面との交差を判定する。
【０１４８】
C3テストでは、二次形式の最小値を求め、その最小値がMBBに含まれているかどうかをみればよい。なぜならば、面の頂点も辺も面も二次形式に含まれていないことがわかっているため、交差しているとしたら二次曲面がMBBの中に収まっている場合だけであるからである。
【０１４９】
Step27では、(x,y,z)=(u,v,w)を代入し、w^2-4*w/3+v^2-4*v/3+u^2-4*u/3+61/48という式を得る。この二次曲面は(u,v,w)=(2/3,2/3,2/3)の時に最小となる。この点はMBBの内部である。二次曲面がMBBの内部空間に存在するかどうかを確かめるために、(u,v,w)=(2/3,2/3,2/3)を実際に代入すると、-1/16となり、0以下であり、交差することがわかる。
【０１５０】
よって、このMBBと二次曲面は交差することがわかる。
【０１５１】
このMBBはオブジェクトのMBBであるため、衝突判定部107はこのオブジェクトのIDを出力する。
【０１５２】
［実施例Dの効果］
オブジェクトの集合に対し、二次曲面を検索範囲として指定したクエリと交差を持つオブジェクトの部分集合を高速に得ることができている。
【０１５３】
今回のオブジェクトとクエリは、図13に示すように実際に交差を持つので、正しく判定できていることがわかる。
【０１５４】
（実施例E）
本実施例では、オブジェクトとして単位立方体(すなわち、ある頂点が(0,0,0)であり、その正反対の位置の頂点が(1,1,1)であるような立方体)がただ1つある場合を想定する。この場合に、(3/2,3/2,1/2)が中心であり半径1/4であるような球を表す二次曲面をクエリとして与える。このときの各部の挙動の例を説明する。
【０１５５】
このクエリの式は以下のようになる。
0>=z^2-z+y^2-3*y+x^2-3*x+75/16
【０１５６】
［実施例Eにおけるオブジェクト階層構造構成部101の動作］
実施例Aと全く同じであるため、説明を省略する。
【０１５７】
［実施例EにおけるオブジェクトMBBツリー格納部102の動作］
実施例Aと全く同じであるため、説明を省略する。
【０１５８】
［実施例Eにおけるベクトル積事前計算部103の動作］
実施例Aと全く同じであるため、説明を省略する。
【０１５９】
［実施例EにおけるMBBベクトル積キャッシュ部104の動作］
実施例Aと全く同じであるため、説明を省略する。
【０１６０】
［実施例Eにおける二次曲面MBB計算部105の動作］
本実施例での二次曲面クエリの二次曲面は球であるため、(5/4,5/4,1/4)-(7/4,7/4,3/4)がMBBとして計算される。
【０１６１】
［実施例Eにおける初期フィルタリング部106の動作］
二次曲面クエリのMBBである(5/4,5/4,1/4)-(7/4,7/4,3/4)が、オブジェクトMBBである(0,0,0)-(1,1,1)と交差するかどうかを判定する。
【０１６２】
実施例Aで述べたように、x軸、y軸、z軸に並行な直方体同士の交差判定は、各軸ごとに交差を持つかどうかを独立して判定し、すべてで交差する場合に直方体同士が交差すると判定できる。このため、当該判定は、計算量的に簡単である。
【０１６３】
まずx軸に注目し、0から1の範囲と5/4から7/4の範囲が交差を持つかどうかを判定する。この場合は交差しない。
【０１６４】
よって、二次曲面クエリMBBはオブジェクトMBBと交差しない。従って、このオブジェクトを衝突判定部107に出力しない。
【０１６５】
［実施例Eにおける衝突判定部107の動作］
初期フィルタリング部106がオブジェクトを出力しないため、本実施例では衝突判定部107は動作しない。
【０１６６】
ただし、仮に動作したとしても、無駄な計算が発生するだけで本発明としての動作は変わらない。動作したとした場合の手続きを図14に示す。C0テストからC3テストのいずれでも交差しないと判定されるため、このオブジェクトと二次曲面は交差しないと判定される。
【０１６７】
［実施例Eの効果］
オブジェクトの集合に対し、二次曲面を検索範囲として指定したクエリと交差を持つオブジェクトの部分集合を高速に得ることができる。
【０１６８】
今回のオブジェクトとクエリは、図15に示すように実際に交差を持たないので、正しく判定できていることがわかる。
【０１６９】
（実施例F）
本実施例では、オブジェクトとして単位立方体(すなわち、ある頂点が(0,0,0)であり、その正反対の位置の頂点が(1,1,1)であるような立方体)がただ1つある場合を想定する。この場合に、(1,0,2/3)が中心であり半径1/4であるような球を表す二次曲面をクエリとして与える。このときの各部の挙動の例を説明する。
【０１７０】
このクエリの式は以下のようになる。
0>=z^2-4*z/3+y^2+x^2-2*x+199/144
【０１７１】
［実施例Fにおけるオブジェクト階層構造構成部101の動作］
実施例Aと全く同じであるため、説明を省略する。
【０１７２】
［実施例FにおけるオブジェクトMBBツリー格納部102の動作］
実施例Aと全く同じであるため、説明を省略する。
【０１７３】
［実施例Fにおけるベクトル積事前計算部103の動作］
実施例Aと全く同じであるため、説明を省略する。
【０１７４】
［実施例FにおけるMBBベクトル積キャッシュ部104の動作］
実施例Aと全く同じであるため、説明を省略する。
【０１７５】
［実施例Fにおける二次曲面MBB計算部105の動作］
本実施例での二次曲面クエリの二次曲面は球であるため、(3/4,3/4,5/12)-(5/4,5/4,11/12)がMBBとして計算される。
【０１７６】
［実施例Fにおける初期フィルタリング部106の動作］
二次曲面クエリのMBBである(3/4,3/4,5/12)-(5/4,5/4,11/12)が、オブジェクトMBBである(0,0,0)-(1,1,1)と交差するかどうかを判定する。
【０１７７】
実施例Aで述べたように、x軸、y軸、z軸に並行な直方体同士の交差判定は、各軸ごとに交差を持つかどうかを独立して判定し、すべてで交差する場合に直方体同士が交差すると判定できる。このため、当該判定は、計算量的に簡単である。
【０１７８】
まずx軸に注目し、0から1の範囲と3/4から5/4の範囲が交差を持つかどうかを判定する。この場合は、3/4から1の範囲が交差する。
【０１７９】
次にy軸に注目し、0から1の範囲と3/4から5/4の範囲が交差を持つかどうかを判定する。この場合は、3/4から1の範囲が交差する。
【０１８０】
次にy軸に注目し、0から1の範囲と5/12から11/12の範囲が交差を持つかどうかを判定する。この場合は、5/12から11/12の範囲が交差する。
【０１８１】
以上から、二次曲面クエリMBBはオブジェクトMBBと交差する。よって、このオブジェクトを、衝突判定部107に出力する。
【０１８２】
［実施例Fにおける衝突判定部107の動作］
二次曲面クエリの二次曲面が、オブジェクトMBBである(0,0,0)-(1,1,1)と交差するかどうかを判定する。
【０１８３】
本実施例では図3のフローに従って、C0テストからC3テストまでのStep1から27を並列に実行する。いずれかが交差すると判定した時点で交差すると判定し、いずれも交差しないと判定した場合は、交差しないと判定する。
【０１８４】
実行順序に関わらず、Step19で交差していることが判定されるため、衝突判定部107はこのMBBは二次曲面と交差すると判定する。
【０１８５】
このMBBはオブジェクトのMBBであるため、衝突判定部107はこのオブジェクトのIDを出力する。
【０１８６】
［実施例Fの効果］
オブジェクトの集合に対し、二次曲面で指定したクエリと交差を持つオブジェクトの部分集合を高速に得ることができる。
【０１８７】
今回のオブジェクトとクエリは、図9に示すように実際に交差を持つので、正しく判定できていることがわかる。
【０１８８】
（実施例G）
本実施例では、オブジェクトとして以下の3つの立方体を扱う。
1.(0,0,0)-(1,1,1)
2,(10,0,0)-(11,1,1)
3.(20,0,0)-(21,1,1)
【０１８９】
また、クエリとして(1,0,2/3)が中心であり半径1/4であるような球を表す二次曲面をクエリとして与える。このときの各部の挙動の例を説明する。
【０１９０】
このクエリの式は以下のようになる。
0>=z^2-4*z/3+y^2+x^2-2*x+199/144
【０１９１】
［実施例Gにおけるオブジェクト階層構造構成部101の動作］
3つの立方体を受け取り、それぞれのMBBを計算する。この場合、MBBと元の立方体はいずれも一致する。
【０１９２】
本実施例では、扱うオブジェクトをすべて同じノードの子ノードとするような木を構成する。具体的に、図16に示すような3つの葉の木が構成される。
【０１９３】
［実施例GにおけるオブジェクトMBBツリー格納部102の動作］
オブジェクト階層構造構成部101により構成された3つの葉の木（図16）を記憶する。
【０１９４】
［実施例Gにおけるベクトル積事前計算部103の動作］
各MBBに対して、前述のベクトル積（積の値の集合）をそれぞれ計算する。
【０１９５】
［実施例GにおけるMBBベクトル積キャッシュ部104の動作］
ベクトル積事前計算部103により計算されたベクトル積を、図17に示すようにテーブルの形式で記憶する。
【０１９６】
［実施例Gにおける二次曲面MBB計算部105の動作］
本実施例での二次曲面クエリの二次曲面は球であるため、(3/4,3/4,3/4)-(5/4,5/4,5/4)がMBBとなる。
【０１９７】
［実施例Gにおける初期フィルタリング部106の動作］
各オブジェクトに対して並列処理で交差判定を行う。
【０１９８】
すなわち、オブジェクト1と二次曲面の交差判定、オブジェクト2と二次曲面の交差判定、オブジェクト3と二次曲面の交差判定、を並行して行う。
【０１９９】
オブジェクト1と二次曲面の交差判定は、実施例Bとまったく同じである。
【０２００】
オブジェクト2と二次曲面の交差判定は、(10,0,0)-(11,1,1)と、二次曲面クエリのMBBである(3/4,3/4,3/4)-(5/4,5/4,5/4)との交差判定となる。この判定はx軸に注目し、10から11の範囲と、3/4から5/4の範囲が交差を持つかを判断する。交差しないと判定されるため、初期フィルタリング部106は、オブジェクト2を衝突判定部107に出力しない。
【０２０１】
オブジェクト3と二次曲面の交差判定は、(20,0,0)-(21,1,1)と、二次曲面クエリのMBBである(3/4,3/4,3/4)-(5/4,5/4,5/4)との交差判定となる。この判定はx軸に注目し、20から21の範囲と、3/4から5/4の範囲が交差を持つかを判断する。交差しないと判定されるため、初期フィルタリング部106は、オブジェクト3を衝突判定部107に出力しない。
【０２０２】
以上から、二次曲面クエリMBBと交差するオブジェクトはオブジェクト1だけである。よって、このオブジェクトを出力する。この出力処理もオブジェクト間で並列して動作されうることに注意する。
【０２０３】
［実施例Gにおける衝突判定部107の動作］
初期フィルタリング部106がオブジェクト1のみを出力してくるため、この時の動作は実施例Bとまったく同じになる。
【０２０４】
［実施例Gの効果］
オブジェクトの集合に対し、二次曲面を検索範囲として指定したクエリと交差を持つオブジェクトの部分集合を高速に得ることができる。
【０２０５】
今回のオブジェクトとクエリは、図9に示すように実際に交差を持つので、正しく判定できていることがわかる。
【０２０６】
なお、以上に説明した本実施形態におけるオブジェクト検索装置は、例えば、汎用のコンピュータ装置を基本ハードウェアとして用いることで実現することが可能である。すなわち、オブジェクト検索装置の各処理部は、上記のコンピュータ装置に搭載されたプロセッサにプログラムを実行させることにより実現することができる。このとき、オブジェクト検索装置は、上記のプログラムをコンピュータ装置にあらかじめインストールすることで実現してもよいし、CD-ROMなどの記憶媒体に記憶して、あるいはネットワークを介して上記のプログラムを配布して、このプログラムをコンピュータ装置に適宜インストールすることで実現してもよい。また、オブジェクト検索装置内の各格納部は、装置内もしくは外付けのメモリ装置およびハードディスク、あるいは、CD-R, CD-RW, DVD-RAM, DVD-R 等の記録媒体によって構成されてもよい。
【図１】
0005597664.tif 000002
【図２】
0005597664.tif 000003
【図３】
0005597664.tif 000004
【図４】
0005597664.tif 000005
【図５】
0005597664.tif 000006
【図６】
0005597664.tif 000007
【図７】
0005597664.tif 000008
【図８】
0005597664.tif 000009
【図９】
0005597664.tif 000010
【図１０】
0005597664.tif 000011
【図１１】
0005597664.tif 000012
【図１２】
0005597664.tif 000013
【図１３】
0005597664.tif 000014
【図１４】
0005597664.tif 000015
【図１５】
0005597664.tif 000016
【図１６】
0005597664.tif 000017
【図１７】
0005597664.tif 000018