JP2013190849A

JP2013190849A - オブジェクト検索装置およびその方法

Info

Publication number: JP2013190849A
Application number: JP2012054766A
Authority: JP
Inventors: Yusuke Endo; 藤侑介遠; Hiromasa Shin; 博正進; Yoshiro Hasegawa; 義朗長谷川
Original assignee: Toshiba Corp
Current assignee: Toshiba Corp
Priority date: 2012-03-12
Filing date: 2012-03-12
Publication date: 2013-09-26
Anticipated expiration: 2032-03-12
Also published as: JP5597664B2; US20130238541A1; EP2639711A1; US9262717B2

Abstract

【課題】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

Description

本実施形態は、オブジェクト検索装置およびその方法に関し、たとえば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)と交差するかどうかを判定する。

まずx軸に注目し、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と二次曲面は交差することがわかる。

［実施例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軸に並行な直方体同士の交差判定は、各軸ごとに交差を持つかどうかを独立して判定し、すべてで交差する場合に直方体同士が交差すると判定できる。このため、当該判定は、計算量的に簡単である。

以上から、二次曲面クエリ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と二次曲面は交差することがわかる。

［実施例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)と交差するかどうかを判定する。

まず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であるような球を表す二次曲面をクエリとして与える。このときの各部の挙動の例を説明する。

［実施例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)と交差するかどうかを判定する。

以上から、二次曲面クエリMBBはオブジェクトMBBと交差する。よって、このオブジェクトを、衝突判定部107に出力する。

［実施例Fにおける衝突判定部107の動作］
二次曲面クエリの二次曲面が、オブジェクトMBBである(0,0,0)-(1,1,1)と交差するかどうかを判定する。

本実施例では図3のフローに従って、C0テストからC3テストまでのStep1から27を並列に実行する。いずれかが交差すると判定した時点で交差すると判定し、いずれも交差しないと判定した場合は、交差しないと判定する。

実行順序に関わらず、Step19で交差していることが判定されるため、衝突判定部107はこのMBBは二次曲面と交差すると判定する。

［実施例Fの効果］
オブジェクトの集合に対し、二次曲面で指定したクエリと交差を持つオブジェクトの部分集合を高速に得ることができる。

（実施例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であるような球を表す二次曲面をクエリとして与える。このときの各部の挙動の例を説明する。

［実施例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の効果］
オブジェクトの集合に対し、二次曲面を検索範囲として指定したクエリと交差を持つオブジェクトの部分集合を高速に得ることができる。

なお、以上に説明した本実施形態におけるオブジェクト検索装置は、例えば、汎用のコンピュータ装置を基本ハードウェアとして用いることで実現することが可能である。すなわち、オブジェクト検索装置の各処理部は、上記のコンピュータ装置に搭載されたプロセッサにプログラムを実行させることにより実現することができる。このとき、オブジェクト検索装置は、上記のプログラムをコンピュータ装置にあらかじめインストールすることで実現してもよいし、CD-ROMなどの記憶媒体に記憶して、あるいはネットワークを介して上記のプログラムを配布して、このプログラムをコンピュータ装置に適宜インストールすることで実現してもよい。また、オブジェクト検索装置内の各格納部は、装置内もしくは外付けのメモリ装置およびハードディスク、あるいは、CD-R, CD-RW, DVD-RAM, DVD-R 等の記録媒体によって構成されてもよい。

Claims

N（Nは3以上の整数）次元空間上におけるN-1次曲面を指定した検索クエリを受け取るクエリ受取部と、
前記検索クエリによって指定されるN-1次曲面が、前記N次元空間上に配置されたN次元直方体と交差するかを判定する衝突判定部と、
を備え、
前記衝突判定部は、前記N次元直方体のX（Xは0以上N-1以下のすべての整数）次元面の少なくともいずれかの少なくとも一部が、前記N-1次曲面に含まれるかを判定する第0〜第N-1判定機能を含む複数の判定機能を備え、前記複数の判定機能を用いて前記N次元直方体と交差するかの判定を行う、オブジェクト検索装置。
前記複数の判定機能は、前記N次元直方体に前記N-1次曲面が包含されるかを判定する第Nの判定機能を含む請求項1に記載のオブジェクト検索装置。
前記衝突判定部は、前記複数の判定機能を前記第0の判定機能から番号の小さい順に実行し、交差するとの判定が得られたら、当該交差するとの判定が得られた判定機能より後の番号の判定機能の実行を省略する
請求項1または2に記載のオブジェクト検索装置。
前記衝突判定部は、前記複数の判定機能を並列して行い、いずれか1つの判定機能で交差するとの判定が得られたら、前記いずれか1つの判定機能以外の他の判定機能の実行を停止する
請求項1または2に記載のオブジェクト検索装置。
前記衝突判定部は、前記N-1次曲面が、前記N次元空間上に配置された複数のN次元直方体と交差するかの判定を並行して行う
請求項1ないし4のいずれか一項に記載のオブジェクト検索装置。
前記N-1次曲面の最小外包N次直方体を計算する計算部と、
前記N-1次曲面の最小外包N次直方体と、前記N次元直方体が交差するかを判定する初期フィルタリング部をさらに備え、
前記衝突判定部は、前記初期フィルタリング部で前記最小外包N次直方体と交差すると判定されたN次元直方体のみを交差判定の対象とする
請求項1ないし5のいずれか一項に記載のオブジェクト検索装置。
前記N次元直方体は、前記N次元空間に配置されたオブジェクトの最小外包N次元直方体である
請求項1ないし6のいずれか一項に記載のオブジェクト検索装置。
3次元空間上で二次曲面を指定した検索クエリを受け取るクエリ受取部と、
前記検索クエリに指定される二次曲面が、前記3次元空間上に配置された直方体と交差するかを判定する衝突判定部と、
を備え、
前記衝突判定部は、
前記直方体の頂点の少なくともいずれかが前記二次曲面に含まれるかを判断する第0判定機能と、
前記直方体の辺の少なくともいずれかの少なくとも一部が、前記二次曲面に含まれるかを判断する、第1定機能と、
前記直方体の面の少なくともいずれかの少なくとも一部が、前記二次曲面に含まれるかを判断する第2定機能と、
を含む複数の判定機能を備え、前記複数の判定機能を用いて前記N次元直方体と交差するかの判定を行う、オブジェクト検索装置。
前記複数の判定機能は、前記直方体に前記二次曲面が包含されるかを判定する第3定機能を含むことを特徴とする請求項8に記載のオブジェクト検索装置。
前記衝突判定部は、前記複数の判定機能を前記第0の判定機能から番号の小さい順に実行し、交差するとの判定が得られたら、当該交差するとの判定が得られた判定機能より後の番号の判定機能の実行を省略する
請求項8または9に記載のオブジェクト検索装置。
前記衝突判定部は、前記複数の判定機能を並列して行い、いずれか1つの判定機能で交差するとの判定が得られたら、前記いずれか1つの判定機能以外の他の判定機能の実行を停止する
請求項8または9に記載のオブジェクト検索装置。
前記衝突判定部は、前記二次曲面が、前記3次元空間上に配置された複数の直方体と交差するかの判定を並行して行う
請求項8ないし11のいずれか一項に記載のオブジェクト検索装置。
前記二次曲面の最小外方直方体を計算する計算部と、
前記二次曲面の最小外包直方体と、前記直方体が交差するかを判定する初期フィルタリング部をさらに備え、
前記衝突判定部は、前記初期フィルタリング部で前記二次曲面の最小外包直方体と交差すると判定された直方体のみを交差判定の対象とする
請求項8ないし12のいずれか一項に記載のオブジェクト検索装置。
前記直方体は、前記３次元空間に配置されたオブジェクトの最小外包直方体である
請求項8ないし13のいずれか一項に記載のオブジェクト検索装置。
コンピュータが、
（Nは3以上の整数）次元空間上におけるN-1次曲面を指定した検索クエリを受け取るクエリ受取ステップと、
前記検索クエリによって指定されるN-1次曲面が、前記N次元空間上に配置されたN次元直方体と交差するかを判定する衝突判定ステップと、
を備え、
前記衝突判定ステップは、
前記N次元直方体のX（Xは0以上N-1以下のすべての整数）次元面の少なくともいずれかの少なくとも一部が、前記N-1次曲面に含まれるかを判定する、第0〜第N-1判定機能を含む複数の判定機能を用いて、判定を行う、オブジェクト検索方法。