(57)【要約】（Ａ）は変形前の状態、（Ｂ）は変形後の状態を示している。変形勾配テンソル（Ｆｃij）により、影響領域（ｅｃ）は影響領域（ＥＣ）に、外接形状データ（ｓｃ）は外接形状データ（ＳＣ）に変形される。そして、変形後の外接形状データ（ＳＣ）とボックス（ｂ）とが重複するか否かが確認される。変形後の外接形状データ（ＳＣ）とボックス（ｂ）とは重複しなくなるため、ボックス（ｂ）内の粒子データ（ｐ１）〜（ｐ６）は、対象粒子データ（ｐｃ）の近傍粒子データの候補外となる。
2013042212.tif 000002
【特許請求の範囲】
【請求項１】
対象粒子の近傍に位置する近傍粒子の探索を行なう探索プログラムにおいて、
コンピュータに、
粒子データ群の各粒子データの位置情報および変形勾配テンソルを記憶する記憶装置から読み出された前記粒子データ群の中の対象粒子データの位置情報に基づいて、前記対象粒子データの影響領域に外接する外接形状データを生成させ、
前記粒子データ群のうちの少なくとも１つの粒子データが存在する領域データと、前記生成された外接形状データとのうちいずれか一方を、変形対象に設定させ、
前記設定された変形対象を、前記対象粒子データの変形勾配テンソルに基づいて変形させ、
前記変形後の変形対象と、前記外接形状データおよび前記領域データのうちの前記変形対象として設定されなかった非変形対象とが、重複するかを判断させ、
前記変形後の変形対象と前記非変形対象とが重複すると判断された場合、前記領域データ内の粒子データを、前記対象粒子データの近傍粒子データ候補に決定させ、
前記決定された決定結果を前記記憶装置に格納させることを特徴とする探索プログラム。
【請求項２】
前記変形対象の設定では、前記外接形状データを前記変形対象に設定し、
前記変形対象の変形では、前記設定によって前記変形対象に設定された外接形状データを、前記対象粒子データの変形勾配テンソルで変形させ、
前記変形後の変形対象と前記非変形対象とが重複するか否かの判断は、前記変形された外接形状データと、前記領域データとが、重複するかを判断することを特徴とする請求項１記載の探索プログラム。
【請求項３】
前記探索プログラムはさらに、
前記コンピュータに、前記近傍粒子データ候補が、前記変形により前記外接形状データの変形とともに変形された影響領域と重複するかを判断させ、
前記対象粒子データの近傍粒子データ候補の決定は、前記変形後の影響領域に重複すると判断された近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする請求項２記載の探索プログラム。
【請求項４】
前記変形対象の設定では、前記領域データを前記変形対象に設定し、
前記変形対象の変形では、前記設定によって前記変形対象に設定された領域データを、前記変形勾配テンソルの逆テンソルに基づいて変形させ、
前記変形後の変形対象と前記非変形対象とが重複するか否かの判断は、前記影響領域と、前記変形後の領域データとが重複するかを判断することを特徴とする請求項１記載の探索プログラム。
【請求項５】
前記探索プログラムはさらに、
前記コンピュータに、前記変形により前記領域データが変形された近傍粒子データ候補が、前記対象粒子データの影響領域と重複するかを判断させ、
前記対象粒子データの近傍粒子データ候補の決定は、前記判断された前記対象粒子データの影響領域と重複する近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記格納装置への格納は、前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする請求項４記載の探索プログラム。
【請求項６】
前記探索プログラムはさらに、
前記コンピュータに、
対象粒子データごとに、前記対象粒子データと前記対象粒子データに関連付けられた近傍粒子データとに基づいて、前記対象粒子データの変形勾配テンソルおよび位置情報を更新させることを特徴とする請求項１〜５のいずれか１項記載の探索プログラム。
【請求項７】
前記変形対象の設定は、所定の切替タイミングに基づいて、前記変形対象を交互に設定することを特徴とする請求項６記載の探索プログラム。
【請求項８】
前記変形対象が前記外接形状データである第１の状態と、前記変形対象が前記領域データである第２の状態のうち、前記近傍粒子データが先に決定された方の状態の変形対象を次回の変形対象に設定することを特徴とする請求項６または７記載の探索プログラム。
【請求項９】
粒子データ群の各粒子データの位置情報および変形勾配テンソルを記憶する記憶装置と、
前記記憶装置から読み出された前記粒子データ群の中の対象粒子データの位置情報に基づいて、前記対象粒子データの影響領域に外接する外接形状データを生成する生成部と、
前記粒子データ群のうち少なくとも１つが存在する領域データと前記生成部によって生成された外接形状データとのうちいずれか一方を、変形対象に設定する設定部と、
前記設定された変形対象を、前記対象粒子データの変形勾配テンソルに基づいて変形させる変形部と、
前記変形後の変形対象と、前記外接形状データおよび前記領域データのうちの非変形対象とが、重複するかを判断する判断部と、
前記判断部が、前記変形後の変形対象と前記非変形対象が重複すると判断された場合、前記領域データ内の粒子データを、前記対象粒子データの近傍粒子データ候補に決定する決定部と、
前記決定された決定結果を前記記憶装置に格納する格納部と、
を備えることを特徴とする探索装置。
【請求項１０】
前記設定部では、前記外接形状データを前記変形対象に設定し、
前記変形部では、前記設定部によって前記変形対象に設定された外接形状データを、前記対象粒子データの変形勾配テンソルで変形させ、
前記判断部は、前記変形された外接形状データと、前記領域データとが、重複するかを判断することを特徴とする請求項９記載の探索装置。
【請求項１１】
前記判断部は、前記近傍粒子データ候補が、前記変形により前記外接形状データの変形とともに変形された影響領域と重複するかを判断し、
前記決定部は、前記対象粒子データの近傍粒子データ候補の決定は、前記変形後の影響領域に重複すると判断された近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記格納部は、前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする請求項１０記載の探索装置。
【請求項１２】
前記設定部では、前記領域データを前記変形対象に設定し、
前記変形部では、前記設定部によって前記変形対象に設定された領域データを、前記変形勾配テンソルの逆テンソルに基づいて変形させ、
前記判断部は、前記影響領域と、前記変形後の領域データとが重複するかを判断することを特徴とする請求項９記載の探索装置。
【請求項１３】
前記判断部は、前記変形により前記領域データが変形された近傍粒子データ候補が、前記対象粒子データの影響領域と重複するかを判断し、
前記決定部は、前記判断された前記対象粒子データの影響領域と重複する近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記格納部は、前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする請求項１２記載の探索装置。
【請求項１４】
前記設定部は、前記変形対象が前記外接形状データである第１の状態と、前記変形対象が前記領域データである第２の状態のうち、前記近傍粒子データが先に決定された方の状態の変形対象を次回の変形対象に設定することを特徴とする請求項９記載の探索装置。
【請求項１５】
対象粒子の近傍に位置する近傍粒子の探索を行なう探索方法において、
コンピュータが、
粒子データ群の中の対象粒子データの位置情報に基づいて、前記対象粒子データの影響領域に外接する外接形状データを生成し、
前記粒子データ群の粒子データのうち少なくとも１つの粒子データが存在する領域データと前記生成処理によって生成された外接形状データとのうちいずれか一方を、変形対象に設定し、
前記設定された変形対象を、前記対象粒子データの変形勾配テンソルに基づいて変形させ、
前記変形後の変形対象と、前記外接形状データおよび前記領域データのうち変形対象として設定されなかった非変形対象とが、重複するかを判断し、
前記変形後の変形対象と前記非変形対象が重複すると判断された場合、前記領域データ内の粒子データを、前記対象粒子データの近傍粒子データ候補に決定し、
前記決定された決定結果を前記記憶装置に格納することを特徴とする探索方法。
【請求項１６】
前記変形対象の設定では、前記外接形状データを前記変形対象に設定し、
前記変形対象の変形では、前記設定によって前記変形対象に設定された外接形状データを、前記対象粒子データの変形勾配テンソルで変形させ、
前記変形後の変形対象と前記非変形対象とが重複するか否かの判断は、前記変形された外接形状データと、前記領域データとが、重複するかを判断することを特徴とする請求項１５記載の探索方法。
【請求項１７】
前記探索方法はさらに、
前記コンピュータが、前記近傍粒子データ候補が、前記変形により前記外接形状データの変形とともに変形された影響領域と重複するかを判断し、
前記対象粒子データの近傍粒子データ候補の決定は、前記変形後の影響領域に重複すると判断された近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする請求項１６記載の探索方法。
【請求項１８】
前記変形対象の設定では、前記領域データを前記変形対象に設定し、
前記変形対象の変形では、前記設定によって前記変形対象に設定された領域データを、前記変形勾配テンソルの逆テンソルに基づいて変形させ、
前記変形後の変形対象と前記非変形対象とが重複するか否かの判断は、前記影響領域と、前記変形後の領域データとが重複するかを判断することを特徴とする請求項１５記載の探索方法。
【請求項１９】
前記探索方法はさらに、
前記コンピュータが、前記変形により前記領域データが変形された近傍粒子データ候補が、前記対象粒子データの影響領域と重複するかを判断し、
前記対象粒子データの近傍粒子データ候補の決定は、前記判断された前記対象粒子データの影響領域と重複する近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記格納装置への格納は、前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする請求項１８記載の探索方法。
【請求項２０】
前記変形対象の設定では、前記変形対象が前記外接形状データである第１の状態と、前記変形対象が前記領域データである第２の状態のうち、前記近傍粒子データが先に決定された方の状態の変形対象を次回の変形対象に設定することを特徴とする請求項１５記載の探索方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、探索プログラム、探索装置、および探索方法に関する。
【背景技術】
【０００２】
従来から、数値計算を用いて水や空気の流れを調べる流体解析や、圧縮されたゴムの振る舞いを調べる弾性体解析において、連続体を粒子の分布で表現するＳｍｏｏｔｈｅｄ  Ｐａｒｔｉｃｌｅｓ  Ｈｙｄｒｏｄｙｎａｍｉｃｓ（ＳＰＨ）法やＭｏｖｉｎｇ  Ｐａｒｔｉｃｌｅｓ  Ｓｅｍｉ−ｉｍｐｌｉｃｉｔ（ＭＰＳ）法が知られている。例えば、下記特許文献１では、超弾性体の大変形をＳＰＨ法を用いて数値解析する手法が開示されている。また、下記特許文献２では、ＭＰＳ法を用いて画像変形をおこなう手法が開示されている。【０００３】
これら粒子ベースの標準的な手法においては、ある粒子に対してあらかじめ設定された領域（以下、「影響領域」と呼ぶ）の内に存在する相手粒子のみからの相互作用を計算する。そのため、数値解析の一部として影響領域内の粒子(以下、「近傍粒子」と呼ぶ)を計算領域全体の中から同定するプロセスが必要となる。標準的な粒子法のモデル化では、影響領域は球形とし各粒子には影響半径と呼ばれる数値を設定して済ませることが多い。【０００４】
しかしながら、連続体が変形しながら空間中を運動する過程を扱うためには、各粒子に変形勾配テンソルＦijを持たせ、本来の形状から一次変換によって変形された影響領域を用いて解析する手法もある。変形勾配テンソルＦijの下付き添え字ｉ，ｊは座標軸を示すインデックスである。ここで変形勾配テンソルＦijは連続体の初期位置座標をｘ，変形後の位置座標をＸとしたとき、下記式（１）で与えられるテンソル場である。【０００５】
【数１】
2013042212.tif 000003
【０００６】
近傍粒子を探索するために、すべての粒子対に対して近傍であるかどうかの判断をした場合、全粒子数の２乗に比例して判断の回数が必要になる。これは計算コストが極めて大きいため、近傍粒子の探索を高速化するための手法として、ｃｅｌｌ  ｉｎｄｅｘ法がある。【０００７】
ｃｅｌｌ  ｉｎｄｅｘ法は計算領域を影響半径の幅のセルに分割し、対象粒子ｉの近傍粒子を自身が属するのと同じセル、及びそのセルと隣接するセルのみから探索する方法である。ｃｅｌｌ  ｉｎｄｅｘ法では粒子が各セルに均等に分布している場合には（全粒子数をＮとして）、Ｏ（Ｎ）の計算量が必要であり、全粒子対を扱う直接法のＯ（Ｎ2）に比べて高速化されている。【０００８】
下記非特許文献１においては、非等方の影響領域を持つＳＰＨ法のための近傍粒子探索手法としてｃｅｌｌ  ｉｎｄｅｘ法をベースとした手法が開示されている。この手法では、各連続体粒子は、その影響領域のサイズ程度の大きさのセルに属するものとして、まず、そのセルに含まれる粒子群（以後、「粒子群ｉ」と呼ぶ。また、粒子群ｉに含まれる個別の粒子を指して「ｉ粒子」と呼ぶ）に共通の近傍粒子の候補となる粒子のリストを作成する。【０００９】
一般に、近傍粒子候補リストには、粒子群ｉが含まれることになる。このリストに含まれる粒子と粒子群ｉの各粒子とが近傍粒子であるかどうかの判断はこれらの間の全粒子対に対して、個別に判断する。つまり、粒子群ｉに含まれる粒子数をＮi、近傍粒子候補リストに含まれる粒子数をＮjとすると、セル一つ当たりＯ（ＮiＮj）の回数だけ比較が必要になる。そのため、近傍粒子候補リストに含まれる粒子数を削減することができれば、近傍粒子探索にかかるコストを減らすことができる。【００１０】
下記非特許文献１では、影響領域の変形を考慮に入れることで、作成される近傍粒子候補リストの粒子数を減らすことを提案している。具体的には次の手順をとる。【００１１】
まず、ｉ粒子の座標の最小値と最大値を調べ、ｘｉmin，ｘｉmaxと呼ぶ。これらは座標軸ごとに設定され、粒子群ｉすべてを含む最小の空間Ｓｉ（２次元の場合は矩形で、３次元の場合は立方体。）を構成する。また、ｉ粒子の（一般には変形している）影響領域の最小・最大座標を求め、ｘｉｈmin，ｘｉｈmaxとする。これらは座標軸ごとに設定される。ｘｉｈmin，ｘｉｈmaxにより、空間Ｓｈｉ（２次元の場合は矩形で、３次元の場合は直方体。）が設定される。【００１２】
空間Ｓｈｉは、空間Ｓｉを包含し、ｉ粒子の影響領域に含まれる粒子であれば必ず空間Ｓｈｉに含まれている。そこで、ある粒子ｊ1が空間Ｓｈｉに含まれていれば粒子ｊ1は近傍粒子候補リストに追加される。こうすることで、座標軸ごとに変形の度合いが異なることを考慮して、近傍粒子候補リストに含まれる粒子数が削減される。【００１３】
一方、ある粒子ｊ2が空間Ｓｈｉの外にある場合でも、粒子ｊ2の影響領域に粒子ｉを含む場合がありえる。このような場合には、粒子ｊ2の影響領域に外接する矩形（または直方体）が空間Ｓｈｉと共通領域を持つときには、粒子ｊ2も近傍粒子候補リストに追加される。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２００８−１５２４２３号公報
【特許文献２】特開２０１０−１１３４６７号公報
【非特許文献】
【００１５】
【非特許文献１】Ａｓｔｒｏｐｈｙｓｉｃａｌ  Ｊ．Ｓｕｐｐｌｅｍｅｎｔ  ｓｅｒｉｅｓ  １９９８，１１６，ｐｐ．２０８−２０９，Ｏｗｅｎ，Ｖｉｌｌｕｍｓｅｎ，Ｓｈａｐｉｒｏ，＆  Ｍａｒｔｅｌ（Ａｐｐｅｎｄｉｘ  Ｃ３）
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかしながら、上述した従来技術では、影響領域が座標軸に対して斜行する向きに大きく変形している粒子があった場合、影響領域としては重なり合っていないのに、その外接する矩形（または直方体）が重なりを持つときには近傍粒子候補リストに追加されてしまうことになる。このため、近傍粒子候補リストに必要以上の粒子を含むことになり、探索精度が低下し、またこれにより演算負荷が増大するという問題がある。【００１７】
１つの側面では、本発明は、近傍粒子探索の効率化を図ることを目的とする。
【課題を解決するための手段】
【００１８】
対象粒子の近傍に位置する近傍粒子の探索を行なうにあたり、粒子データ群の各粒子データの位置情報および変形勾配テンソルを記憶する記憶装置から読み出された前記粒子データ群の中の対象粒子データの位置情報に基づいて、前記対象粒子データの影響領域に外接する外接形状データを生成し、前記粒子データ群のうちの少なくとも１つの粒子データが存在する領域データと、前記生成された外接形状データとのうちいずれか一方を、変形対象に設定し、前記設定された変形対象を、前記対象粒子データの変形勾配テンソルに基づいて変形し、前記変形後の変形対象と、前記外接形状データおよび前記領域データのうちの前記変形対象として設定されなかった非変形対象とが、重複するかを判断し、前記変形後の変形対象と前記非変形対象とが重複すると判断された場合、前記領域データ内の粒子データを、前記対象粒子データの近傍粒子データ候補に決定し、前記決定された決定結果を前記記憶装置に格納する探索プログラム、探索装置、および探索方法が提案される。
【発明の効果】
【００１９】
一態様によれば、近傍粒子探索の効率化を図ることができる。
【図面の簡単な説明】
【００２０】
【図１−１】図１−１は、２次元空間での近傍粒子探索例（その１）を示す説明図である。
【図１−２】図１−２は、非特許文献１で提案されている手法で影響領域とボックスｂとの重複を判定する基準を示した図である。
【図２】図２は、２次元空間での近傍粒子探索例（その２）を示す説明図である。
【図３】図３は、変形勾配テンソルＦｃijによる外接形状データｓｃの変形例（その１）を示す説明図である。
【図４】図４は、変形後の影響領域ＥＣおよび外接形状データＳＣを示す説明図である。
【図５】図５は、２次元空間での近傍粒子探索例（その３）を示す説明図である。
【図６】図６は、２次元空間での近傍粒子探索例（その４）を示す説明図である。
【図７】図７は、２次元空間での近傍粒子探索例（その５）を示す説明図である。
【図８】図８は、実施の形態にかかる探索装置のハードウェア構成例を示すブロック図である。
【図９】図９は、データベース（ＤＢ）の記憶内容例を示す説明図である。
【図１０】図１０は、探索装置の機能的構成例を示すブロック図である。
【図１１】図１１は、Ｔｒｅｅ法による再帰的ボックス分割例を示す説明図である。
【図１２】図１２は、図１１に示した再帰的分割によって得られた領域データ群のツリー構造体の一例を示す説明図である。
【図１３】図１３は、探索装置１０００による探索処理手順例（その１）を示すフローチャートである。
【図１４】図１４は、図１３に示したツリー構造体生成処理（ステップＳ１３０２）の詳細な処理手順例を示すフローチャートである。
【図１５】図１５は、図１３に示した近傍粒子データ探索処理（ステップＳ１３０３）の詳細な処理手順例（その１）を示すフローチャートである。
【図１６】図１６は、ステップＳ１５０５での重複ボックスの特定例を示す説明図である。
【図１７】図１７は、図１３に示した近傍粒子データ探索処理（ステップＳ１３０３）の詳細な処理手順例（その２）を示すフローチャートである。
【図１８】図１８は、ステップＳ１７０３での重複ボックスの特定例を示す説明図である。
【図１９】図１９は、探索装置１０００による探索処理手順例（その２）を示すフローチャートである。
【発明を実施するための形態】
【００２１】
以下に添付図面を参照して、この発明にかかる探索プログラム、探索装置、および探索方法の実施の形態を詳細に説明する。
【００２２】
図１−１は、２次元空間での近傍粒子探索例（その１）を示す説明図である。図１において（Ａ）は変形前の状態、（Ｂ）は変形後の状態を示している。（Ａ）において、ボックスｂは、粒子データｐ１〜ｐ６が存在する領域データである。各粒子データｐ１〜ｐ６は、影響領域ｅ１〜ｅ６を有する。影響領域とは、粒子ごとに設定された領域であり、影響領域内に他の粒子が存在する場合、当該他の粒子との間に相互作用が生じるものとして相互作用の計算がおこなわれる。影響領域は、その初期形状があらかじめ設定されており、必要に応じて変形されるものとする。影響領域の変形の具体的な手順については後述する。また、粒子データは、たとえば、粒子の中心を示すデータである。この場合、影響領域を粒子の形状を示す領域としてもよい。
【００２３】
影響領域は、一般には複雑な形状となるため、ボックスｂと共通部分を持つかどうかの判定がそのままでは難しい。そのため、影響領域に外接する外接形状データ（２次元では平行四辺形、３次元では平行六面体）を考え、これがボックスと共通部分を持つかどうか判定する。また、自粒子データの影響領域内に存在する他粒子データを、近傍粒子データと称す。近傍粒子データを用いることで、自粒子データの変形勾配テンソルや加速度、位置情報といった物性値を更新することができる。
【００２４】
対象粒子データｐｃが持つ変形勾配テンソルＦｃij（下記式（２）を参照。）により、対象粒子データｐｃの影響領域ｅｃおよび影響領域ｅｃを含む外接形状データｓｃを変形させる。本実施の形態では、対象粒子データｐｃの変形前の影響領域ｅｃがボックスｂと重複するかどうかと関係なく、変形後の影響領域が重複を持つかどうかを判定する必要がある。
【００２５】
【数２】
2013042212.tif 000004
【００２６】
上記式（２）において、変形勾配テンソルＦijの下付き添え字ｉ，ｊは座標軸を示すインデックスである。また、ｘｃは変形前の対象粒子データｐｃの初期位置座標、Ｘｃは変形後の位置座標である。
【００２７】
（Ｂ）は、変形勾配テンソルＦｃijによる変形後の状態である。変形勾配テンソルＦｃijにより、影響領域ｅｃは影響領域ＥＣに、外接形状データｓｃは外接形状データＳＣに変形される。そして、変形後の外接形状データＳＣとボックスｂとが重複するか否かが確認される。図１の（Ｂ）の場合、変形後の外接形状データＳＣとボックスｂとは重複しないため、ボックスｂ内の粒子データｐ１〜ｐ６は、対象粒子データｐｃの近傍粒子データの候補外となる。
【００２８】
図１−２は、非特許文献１で提案されている手法で影響領域とボックスｂとの重複を判定する基準を示した図である。変形後の影響領域ｅｃに外接する矩形ｓｃ２とボックスｂが重複するので、ボックスｂ内の粒子データｐ１〜ｐ６は、対象粒子データｐｃの近傍粒子データの候補となる。
【００２９】
図２は、２次元空間での近傍粒子探索例（その２）を示す説明図である。図２において（Ａ）は変形前の状態、（Ｂ）は変形後の状態を示している。図１とは、対象粒子データｐｃの位置と変形勾配テンソルＦｃijの値が異なるものとする。図２の（Ｂ）では、変形後の外接形状データＳＣとボックスｂとは重複するため、ボックスｂ内の粒子データｐ１〜ｐ６は、対象粒子データｐｃの近傍粒子データ候補となる。そして、ボックスｂ内の粒子データｐ１〜ｐ６のうち、対象粒子データｐｃの変形後の影響領域ＥＣ内に存在する粒子データｐ６が、対象粒子データｐｃの近傍粒子データとなる。
【００３０】
図３は、変形勾配テンソルＦｃijによる外接形状データｓｃの変形例（その１）を示す説明図である。図３において、（Ａ）は上述した非特許文献１での変形例を示しており、（Ｂ）は本実施の形態での変形例（図１および図２を参照）を示している。図３の（Ａ）では、（ｂ）において、（ａ）に示した変形前の影響領域ｅｃを変形勾配テンソルＦｃijで変形して影響領域ＥＣとする。そして、（ｃ）において、影響領域ＥＣの外接形状データｓｃが生成される。
【００３１】
一方、図３の（Ｂ）では、（ｂ）において、（ａ）に示した変形前の影響領域ｅｃの外接形状データｓｃを生成する。そして、（ｃ）において、影響領域ｅｃおよびその外接形状データｓｃを変形勾配テンソルＦｃijで変形して影響領域ＥＣおよび外接形状データＳＣとする。影響領域ＥＣの外接形状データＳＣが生成される。
【００３２】
このように、図３の（Ａ）では、外接形状データｓｃが変形勾配テンソルＦｃijで変形されないのに対し、図３の（Ｂ）では、外接形状データｓｃが変形勾配テンソルＦｃijで変形されることになる。このように、外接形状データｓｃを、影響領域ｅｃとともに変形勾配テンソルＦｃijで変形させることで、変形後の外接形状データＳＣは、影響領域ＥＣの変形に追従した形状となる。このため、図３の（Ａ）の外接形状データｓｃに比べ、外接形状データＳＣ内の影響領域ＥＣ以外の領域（２次元の場合は面積、３次元の場合は体積）が小さくなる。したがって、図１−２に示したような、ボックスｂとの無駄な重複を防止することができることになる。
【００３３】
図４は、変形後の影響領域ＥＣおよび外接形状データＳＣを示す説明図である。図４の（Ａ）では、連続体粒子データ群の体積を保存する前提の下で、影響領域ＥＣおよび外接形状データＳＣが、座標軸に斜交（４５度）する向きにλ倍伸び、それと直行する方向に２次元の場合には１／λ倍、３次元の場合には１／√（λ）倍縮んでいるものとする。非特許文献１では、外接形状データｓｃの各辺がλ倍になるため、近傍粒子候補リストを含むかどうか調べる必要のある領域の大きさは初期に比べて、２次元の場合にはλ2倍、３次元の場合にはλ3倍になる。
【００３４】
粒子密度が一定であれば、近傍粒子データであるかどうかを判定する粒子データ対の数が２次元の場合にはλ2倍、３次元の場合にはλ3倍になるということを意味する。一方で、体積を保存する前提の下では、変形勾配テンソルＦｃijの作る平行四辺形、もしくは、平行六面体はその面積、及び、体積を変えないため、近傍粒子データかどうかを判定する必要のある粒子データ対の数は大きく変化することはない。一方、座標軸に沿って連続体が伸びるときには、図４の（Ｂ）に示したように、外接形状データＳＣ，ｓｃの形状（２次元の場合は平行四辺形、３次元の場合は平行六面体）は一致することになる。
【００３５】
図５は、２次元空間での近傍粒子探索例（その３）を示す説明図である。図５において（Ａ）は変形前の状態、（Ｂ）は変形後の状態を示している。図１とは、対象粒子データｐｃの位置と変形勾配テンソルＦｃijの値が異なるものとする。図５の（Ｂ）では、図１の（Ｂ）とは異なり、変形後の外接形状データＳＣとボックスｂとは重複するため、ボックスｂ内の粒子データｐ１〜ｐ６は、対象粒子データｐｃの近傍粒子データ候補となる。しかしながら、ボックスｂ内の粒子データｐ１〜ｐ６のうち、対象粒子データｐｃの変形後の影響領域ＥＣ内に存在する粒子データは存在しないため、対象粒子データｐｃの近傍粒子データはない。
【００３６】
図５の（Ｂ）のような場合、影響領域ＥＣ内に含まれていないにもかかわらず、ボックスｂは外接形状データＳＣに重複するため、本来必要とされるよりも多くのボックスに対して重複判定をしてしまう可能性がある。変形による扁平率が大きい場合、この誤判定がより多く発生する。このため、このような誤判定が継続する場合は、変形対象を、対象粒子データｐｃの影響領域ｅｃおよび外接形状データｓｃではなく、ボックスｂとする。
【００３７】
図６は、２次元空間での近傍粒子探索例（その４）を示す説明図である。図６は、図５の（Ａ）から、対象粒子データｐｃの影響領域ｅｃおよび外接形状データｓｃではなく、ボックスｂを変形させた状態を示している。図６では、ボックスｂは、対象粒子データｐｃの変形勾配テンソルＦｃijの逆テンソルＦｃij-1により変形されている。これにより、図５の（Ａ）のボックスｂは、ボックスＢに変形され、粒子データｐ１〜ｐ６の影響領域ｅ１〜ｅ６は、影響領域Ｅ１〜Ｅ６に変形される。また、粒子データｐ１〜ｐ６の位置も変更される。
【００３８】
そして、対象粒子データｐｃの影響領域ｅｃと変形後のボックスＢとは重複しないため、粒子データｐ１〜ｐ６は、対象粒子データｐｃの近傍粒子データ候補に含まれないことになる。
【００３９】
図７は、２次元空間での近傍粒子探索例（その５）を示す説明図である。図７において（Ａ）は変形前の状態、（Ｂ）は変形後の状態を示している。図５とは、対象粒子データｐｃの位置と変形勾配テンソルＦｃijの値が異なるものとする。図７の（Ｂ）では、ボックスｂは、対象粒子データｐｃの変形勾配テンソルＦｃijの逆テンソルＦｃij-1により変形されている。これにより、図７の（Ａ）のボックスｂは、ボックスＢに変形され、粒子データｐ１〜ｐ６の影響領域ｅ１〜ｅ６は、影響領域Ｅ１〜Ｅ６に変形される。また、粒子データｐ１〜ｐ６の位置も変更される。
【００４０】
この場合、図６と異なり、対象粒子データｐｃの影響領域ｅｃと変形後のボックスＢとは重複するため、粒子データｐ１〜ｐ６は、対象粒子データｐｃの近傍粒子データ候補に含まれることになる。
【００４１】
ここで、変形勾配テンソルＦｃijを下記式（３）であらわした場合、その逆テンソルＦｃij-1は、下記式（４）によりあらわされる。
【００４２】
【数３】
2013042212.tif 000005
【００４３】
【数４】
2013042212.tif 000006
【００４４】
なお、上記式（４）中、Ｊは、下記式（５）となる。
【００４５】
Ｊ＝εijkＦｃ1iＦｃ2jＦｃ3k・・・（５）
【００４６】
ただし、εijkはレビ・チビタ記号で、添え字の組（ｉ，ｊ，ｋ）が（１，２，３），（２，３，１），（３，１，２）のときはεijk＝＋１、（１，３，２），（２，１，３），（３，２，１）のときはεijk＝−１、それ以外のときは、εijk＝０となる。
【００４７】
（探索装置のハードウェア構成例）
図８は、実施の形態にかかる探索装置のハードウェア構成例を示すブロック図である。図８において、探索装置は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）８０１と、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）８０２と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）８０３と、磁気ディスクドライブ８０４と、磁気ディスク８０５と、光ディスクドライブ８０６と、光ディスク８０７と、ディスプレイ８０８と、Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）８０９と、キーボード８１０と、マウス８１１と、スキャナ７１２と、プリンタ７１３と、を備えている。また、各構成部はバス８００によってそれぞれ接続されている。
【００４８】
ここで、ＣＰＵ８０１は、探索装置の全体の制御を司る。ＲＯＭ８０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ８０３は、ＣＰＵ８０１のワークエリアとして使用される。磁気ディスクドライブ８０４は、ＣＰＵ８０１の制御にしたがって磁気ディスク８０５に対するデータのリード／ライトを制御する。磁気ディスク８０５は、磁気ディスクドライブ８０４の制御で書き込まれたデータを記憶する。
【００４９】
光ディスクドライブ８０６は、ＣＰＵ８０１の制御にしたがって光ディスク８０７に対するデータのリード／ライトを制御する。光ディスク８０７は、光ディスクドライブ８０６の制御で書き込まれたデータを記憶したり、光ディスク８０７に記憶されたデータをコンピュータに読み取らせたりする。
【００５０】
ディスプレイ８０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ８０８は、たとえば、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）、ＴＦＴ（Ｔｈｉｎ  ＦＩｌｍ  Ｔｒａｎｓｉｓｔｏｒ）液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００５１】
インターフェース（以下、「Ｉ／Ｆ」と略する。）８０９は、通信回線を通じてＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットなどのネットワーク７１４に接続され、このネットワーク８１４を介して他の装置に接続される。そして、Ｉ／Ｆ８０９は、ネットワーク７１４と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ８０９には、たとえばモデムやＬＡＮアダプタなどを採用することができる。
【００５２】
キーボード８１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス８１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００５３】
スキャナ８１２は、画像を光学的に読み取り、探索装置内に画像データを取り込む。なお、スキャナ８１２は、ＯＣＲ（Ｏｐｔｉｃａｌ  Ｃｈａｒａｃｔｅｒ  Ｒｅａｄｅｒ）機能を持たせてもよい。また、プリンタ８１３は、画像データや文書データを印刷する。プリンタ８１３には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。
【００５４】
図９は、データベース（ＤＢ）の記憶内容例を示す説明図である。ＤＢ９００は、具体的には、たとえば、図８に示したＲＯＭ８０２、ＲＡＭ８０３、磁気ディスク８０５、光ディスク８０７などの記憶装置によりその機能を実現する。ＤＢ９００は、一例として、粒子ＩＤ項目、位置座標項目、影響半径項目、変形勾配テンソル項目、速度項目、質量項目、密度項目、応力テンソル項目、温度項目、加速度項目、近傍粒子ＩＤ項目を有する。そして、ＤＢ９００は、各項目の値を粒子データごとに記憶する。
【００５５】
本実施の形態では、一例として、初期状態においては、粒子データｐｋごとに、粒子ＩＤ：ｐｋ、位置座標Ｃｋ、影響半径Ｒｋ、変形勾配テンソルＦｋij、速度ｖｋ、質量ｍｋ、密度ρｋ、応力テンソルσｋ、温度Ｔｋの各初期値が格納されている。なお、加速度ａｋは計算により求められるため、初期値はないものとする。近傍粒子ＩＤも探索により格納されるため、初期値はないものとする。また、位置座標Ｃｋ、影響半径Ｒｋ、変形勾配テンソルＦｋij、速度ｖｋ、質量ｍｋ、密度ρｋ、応力テンソルσｋ、温度Ｔｋ、加速度ａｋ、近傍粒子ＩＤは、計算ステップごとに登録される。１つ前の計算ステップでの値は、保存しておいてもよく、上書きすることとしてもよい。なお、質量ｍｋ、密度ρｋ、応力テンソルσｋ、温度Ｔｋは固定値であってもよい。
【００５６】
（探索装置の機能的構成例）
図１０は、探索装置の機能的構成例を示すブロック図である。探索装置１０００は、ＤＢ９００と、生成部１００１と、設定部１００２と、変形部１００３と、判断部１００４と、決定部１００５と、格納部１００６と、更新部１００７と、を備えている。生成部１００１〜更新部１００７は、具体的には、たとえば、図８に示したＲＯＭ８０２、ＲＡＭ８０３、磁気ディスク８０５、光ディスク８０７などの記憶装置に記憶されたプログラムをＣＰＵ８０１に実行させることにより、または、Ｉ／Ｆ８０９により、その機能を実現する。
【００５７】
生成部１００１は、粒子群データが存在する計算領域を分割して、部分領域データ群を生成する。具体的には、たとえば、Ｔｒｅｅ法により、計算領域内を再帰的にボックスに分割する。ここで、Ｔｒｅｅ法による再帰的ボックス分割例について説明する。
【００５８】
図１１は、Ｔｒｅｅ法による再帰的ボックス分割例を示す説明図である。図１１では、辺の長さが１／２となるように分割していき、分割ブロック内の粒子データ数が１個以下、または、階層ｒ＝３になるまで、再帰的に分割をおこなう場合を例に挙げて説明する。階層ｒとは分割回数を示す。
【００５９】
図１１において、（Ａ）は、分割前の計算領域Ａを示している。分割前であるため、階層ｒはｒ＝０である。計算領域Ａ内の丸い図形群は、粒子データ群である。（Ｂ）は、（Ａ）の状態からの分割例を示している。（Ｂ）では計算領域Ａが４分割されることで、階層ｒはｒ＝１となり、ブロックｂ１〜ｂ４が生成される。（Ｂ）では階層ｒ＝１となり、また、各ブロックｂ１〜ｂ４の粒子データ数はそれぞれ２個以上存在するため各ブロックｂ１〜ｂ４については、さらに再帰的に分割がおこなわれる。
【００６０】
（Ｃ）は、（Ｂ）の状態からの分割例を示している。（Ｃ）では、（Ｂ）の各ブロックｂ１〜ｂ４が４分割されることで、ブロックｂ１１〜ｂ４４が生成される。（Ｂ）では階層ｒ＝２となる。また、ブロックｂ１１〜ｂ４４のうち、ブロックｂ１１，ｂ２２，ｂ１４，ｂ２３，ｂ３３，ｂ３４，ｂ４２内の粒子データ数は１個であるため、これ以上の分割はおこなわれない。それ以外のブロックｂ１２，ｂ１３，ｂ２１，ｂ２４，ｂ３１，ｂ３２，ｂ４１，ｂ４３，ｂ４４については、さらに再帰的に分割がおこなわれる。
【００６１】
（Ｄ）は、（Ｃ）の状態からの分割例を示している。（Ｄ）では、（Ｃ）の各ブロックｂ１２，ｂ１３，ｂ２１，ｂ２４，ｂ３１，ｂ３２，ｂ４１，ｂ４３，ｂ４４が４分割されることで、ブロックｂ１２１〜ｂ４４４が生成される。（Ｄ）では階層ｒ＝３となるため、ブロック内の粒子データ数にかかわらず、分割を終了する。このように、最終的に（Ｄ）で得られたブロック群が、分割領域データ群となる。
【００６２】
図１２は、図１１に示した再帰的分割によって得られた領域データ群のツリー構造体の一例を示す説明図である。図１２に示すツリー構造体が生成されると、ブロックの頂点座標とＤＢ９００内の粒子データの位置座標とにより、ブロック内の粒子データが特定される。そして、特定された粒子データの粒子ＩＤがツリー構造体の該当するブロック内に格納される。
【００６３】
たとえば、ブロックｂ１内には、ブロックｂ１内に存在する粒子データの粒子ＩＤが格納され、ブロックｂ１２内には、ブロックｂ１２内に存在する粒子データの粒子ＩＤが格納され、ブロックｂ１２３内には、ブロックｂ１２３内に存在する粒子データの粒子ＩＤが格納される。
【００６４】
また、図１０に戻り、生成部１００１は、粒子データ群の中から順次粒子データを指定する。指定された粒子データが対象粒子データｐｃである。粒子データｐｋが指定されると、生成部１００１は、ＤＢ９００から粒子データｐｋの位置座標Ｃｋおよび影響半径Ｒｋを抽出する。そして、生成部１００１は、位置座標Ｃｋおよび影響半径Ｒｋに基づいて、影響領域ｅｋを生成する。たとえば、２次元の場合の影響領域ｅｋは半径Ｒｋの円であり、３次元の場合の影響領域ｅｋは半径Ｒｋの球である。
【００６５】
また、生成部１００１は、粒子データ群の中の対象粒子データの位置情報に基づいて、対象粒子データの影響領域に外接する外接形状データを生成する。具体的には、たとえば、生成部１００１は、ＤＢ９００を参照して、粒子データ群の中から順次粒子データの粒子ＩＤを選択し、その位置情報となる位置座標Ｃｋを取得する。粒子ＩＤが選択された粒子データｐｋが対象粒子データｐｃである。つぎに、生成部１００１は、対象粒子データｐｃの影響半径を参照することで影響領域ｅｃを生成する。そして、生成部１００１は、影響領域ｅｃの外接形状データｓｃを生成する。
【００６６】
設定部１００２は、粒子データ群のうち少なくとも１つが存在する領域データであるブロックｂと生成部１００１によって生成された外接形状データｓｃとのうちいずれか一方を、変形対象に設定する。具体的には、たとえば、初期状態では、外接形状データｓｃを変形対象とし、領域データであるブロックｂを非変形対象とする。また、初期状態では、領域データであるブロックｂを変形対象とし、外接形状データｓｃを非変形対象としてもよい。また、設定部１００２は、変形対象を外接形状データｓｃから領域データに、または、領域データであるブロックｂから外接形状データｓｃに切替設定することもできる。具体的には、設定部１００２は、所定の切替タイミング、たとえば、所定時間経過する都度、交互に切り替えることができる。
【００６７】
変形部１００３は、設定部１００２によって設定された変形対象を、対象粒子データｐｃの変形勾配テンソルＦｃijに基づいて変形させる。具体的には、たとえば、変形対象が外接形状データｓｃである場合、図３の（Ｂ）に示したように、外接形状データｓｃ（影響領域ｅｃ含む）に変形勾配テンソルＦｃijを施すことで、外接形状データｓｃ（影響領域ｅｃ含む）が変形して、外接形状データＳＣ（影響領域ＥＣ含む）が得られる。
【００６８】
一方、変形対象が領域データ（たとえば、ブロックｂ）である場合、変形勾配テンソルＦｃijの逆テンソルＦｃij-1を算出する。そして、図６に示したように、ブロックｂに逆テンソルＦｃij-1を施すことで、ブロックｂ（影響領域ｅｃを含む）が変形して、ブロックＢ（影響領域Ｅ１〜Ｅ６を含む）が得られる。
【００６９】
判断部１００４は、変形部１００３による変形後の変形対象と、外接形状データおよび領域データのうち変形対象として設定されなかった非変形対象とが、重複するか否かを判断する。具体的には、たとえば、変形対象が外接形状データｓｃである場合、変形後の外接形状データＳＣとブロックｂとの重複を判断する。たとえば、判断部１００４は、図１―１の（Ｂ）のケースでは重複していないと判断する。また、図２の（Ｂ）や図５の（Ｂ）のケースでは重複すると判断する。
【００７０】
決定部１００５は、判断部１００４によって重複すると判断された場合、領域データ内の粒子データを、対象粒子データｐｃの近傍粒子データ候補に決定する。具体的には、たとえば、図１―１の（Ｂ）のケースでは重複していないため、近傍粒子データ候補は決定されない。また、図２の（Ｂ）や図５の（Ｂ）のケースでは重複すると判断されるため、決定部１００５は、ブロックｂ内の粒子データｐ１〜ｐ６を対象粒子データｐｃの近傍粒子データ候補に決定する。
【００７１】
格納部１００６は、決定部１００５によって決定された決定結果を記憶装置に格納する。具体的には、たとえば、格納部１００６は、粒子データごとに、近傍粒子データ候補の粒子ＩＤをＤＢ９００に格納する。
【００７２】
また、判断部１００４は、変形対象が外接形状データｓｃである場合、決定部１００５によって近傍粒子データ候補が決定されたことにより、近傍粒子データ候補が、変形部１００３により外接形状データｓｃの変形とともに変形された影響領域ＥＣと重複するか否かを判断する。具体的には、たとえば、図２の（Ｂ）のケースでは、近傍粒子データ候補は粒子データｐ１〜ｐ６であり、このうち粒子データｐ６が影響領域ＥＣと重複する。一方、図５の（Ｂ）のケースでは、近傍粒子データ候補は粒子データｐ１〜ｐ６であるが、影響領域ＥＣと重複する粒子データは存在しない。
【００７３】
そして、決定部１００５は、影響領域ＥＣと重複する近傍粒子データ候補がある場合、当該近傍粒子データ候補を近傍粒子データに決定する。このあと、格納部１００６は、近傍粒子データの粒子ＩＤを、対象粒子データと関連付けて記憶する。たとえば、ＤＢ９００内の対象粒子データのレコードにおける近傍粒子ＩＤ項目に、近傍粒子ＩＤが格納される。
【００７４】
また、判断部１００４は、変形対象が領域データである場合、決定部１００５によって近傍粒子データ候補が決定されたことにより、近傍粒子データ候補が、（変形されていない）対象粒子データｐｃの影響領域ｅｃと重複するか否かを判断する。具体的には、たとえば、図６のケースでは、近傍粒子データ候補は粒子データｐ１〜ｐ６であり、影響領域ｅｃと重複する粒子データは存在しない。
【００７５】
一方、図７の（Ｂ）のケースでは、近傍粒子データ候補は粒子データｐ１〜ｐ６であり、このうち、位置が変更された粒子データｐ６が、（変形されていない）対象粒子データの影響領域ｅｃと重複する。したがって、決定部１００５は、粒子データｐ６を対象粒子データｐｃの近傍粒子データに決定することになる。なお、図７の（Ｂ）の例において、対象粒子データｐｃも、粒子データｐ６の影響領域Ｅ６と重複するとした場合、決定部１００５は、対象粒子データｐｃを粒子データｐ６の近傍粒子データに決定することができる。
【００７６】
この場合、格納部１００６は、粒子データｐ６のレコードに、対象粒子データｐｃの粒子ＩＤを格納する。このように、互いに重複しあう粒子データを近傍粒子データとして決定、格納することで、探索処理の高速化を図ることができる。このような処理は、変形対象が外接形状データｓｃである場合も同様である。
【００７７】
更新部１００７は、対象粒子データｐｃごとに、対象粒子データｐｃと対象粒子データｐｃに関連付けられた近傍粒子データとに基づいて、対象粒子データｐｃの変形勾配テンソルおよび位置情報を更新する。
【００７８】
具体的には、たとえば、更新部１００７は、あらかじめ粒子データ群に設定された物理モデルに従って、連続体粒子の運動を解く。たとえば、弾性体をモデル化した連続体粒子に対しては下記式（６）を解いて、粒子データｐｋごとに加速度ａｋを求める。なお、下記式（６）において、ａiは加速度ａｋ、ｍijは質量ｍｋ、ρijは密度ρｋ、σijは応力テンソルσｋ、Ｗはカーネル関数である。上付き添え字Ｉ（ｋに相当），Ｊは粒子のインデックス、下付き添え字ｉ，ｊは座標軸を示すインデックスであり、座標軸のインデックスｊについては縮約の規約を適用する。和の範囲Ｊは各粒子Ｉ（粒子データｐｋ）に対して、その近傍粒子データの間を渡る。
【００７９】
【数５】
2013042212.tif 000007
【００８０】
また、各粒子データｐｋの位置座標Ｃｋが変化するのに応じて粒子データｐｋごとに変形勾配テンソルＦｋijを算出する。たとえば、下記式（７）によって得られる。ここで、δijはクロネッカー・デルタ、ｄｘは粒子データｐｋの変位である。
【００８１】
【数６】
2013042212.tif 000008
【００８２】
最後に、求められた加速度ａｋを用いて粒子データｐｋごとに速度ｖｋを時間積分し、速度ｖｋを用いて粒子データｐｋごとに位置座標Ｃｋを時間積分し、時刻を時間刻みの分だけ進めると１計算ステップ分の計算が終了する。
【００８３】
【数７】
2013042212.tif 000009
【００８４】
【数８】
2013042212.tif 000010
【００８５】
上記式（８）のｖIi,newは、１計算ステップ後の粒子データｐｋの速度である。上記式（８）のｖIiは、現時刻の速度ｖｋである。上記式（９）のｘIi,newは、１計算ステップ後の粒子データｐｋの位置座標Ｃｋである。上記式（９）のｘIiは、現時刻の位置座標である。ｄｔは、１計算ステップ分の時間刻み幅である。なお、ｄｔは固定の値としてあらかじめ決めておく、たとえば、ｃsを粒子データｐｋの音速、ｈを粒子データｐｋの典型的な影響領域ｅｋのサイズとして、ｄｔ＝ｈ／ｃsとすればよい。なお、必要に応じて計算結果は外部ファイルとして出力される。該出力ファイルは、別に用意されたプログラムで必要な数値や図を画面に表示したり、紙に印刷したりするときに利用される。
【００８６】
また、設定部１００２では、変形対象が外接形状データｓｃである第１の状態と、変形対象が領域データである第２の状態のうち、近傍粒子データが先に決定された方の状態の変形対象を次回の変形対象に設定する。たとえば、第１の状態と第２の状態とで並列実行をおこなって、先に実行完了した方の変形対象を次回の変形対象とする。このようにすることで、実行時間が短いほうのデータが変形対象となるため、探索処理の高速化を図ることができる。
【００８７】
＜探索処理手順＞
図１３は、探索装置１０００による探索処理手順例（その１）を示すフローチャートである。まず、探索装置１０００は、ＤＢ９００から粒子データ群を読み込み（ステップＳ１３０１）、生成部１００１により、ツリー構造体生成処理を実行する（ステップＳ１３０２）。ツリー構造体生成処理（ステップＳ１３０２）では、図１２に示したようなツリー構造体を生成する。ツリー構造体生成処理（ステップＳ１３０２）の詳細は、図１４で説明する。
【００８８】
つぎに、探索装置１０００は、近傍粒子データ探索処理を実行する（ステップＳ１３０３）。近傍粒子データ探索処理（ステップＳ１３０３）では、粒子データｐｋごとに、近傍粒子データを探索する。近傍粒子データ探索処理（ステップＳ１３０３）の詳細は、図１５で説明する。
【００８９】
近傍粒子データ探索処理（ステップＳ１３０３）のあと、探索装置１０００は、粒子データｐｋごとに、運動量を計算する（ステップＳ１３０４）。たとえば、上記式（６）で示したように、探索装置１０００は、粒子データｐｋごとに、加速度ａｋを計算する。そして、探索装置１０００は、上記式（７）〜（９）で示したように、粒子データｐｋごとに、変形勾配テンソルＦｋijや速度ｖ、位置情報ｘｋを更新する（ステップＳ１３０５）。
【００９０】
このあと、探索装置１０００は、１計算ステップ（時間刻み幅ｄｔ）更新して（ステップＳ１３０６）、計算結果（粒子データｐｋごとの近傍粒子データ、加速度ａｋ、速度ｖｋ、位置座標Ｃｋなど）を出力する（ステップＳ１３０７）。このあと、探索装置１０００は、計算終了か否かを判断する（ステップＳ１３０８）。
【００９１】
たとえば、探索装置１０００は、所定計算ステップ数に到達したか否かを判断する。計算終了でない場合（ステップＳ１３０７：Ｎｏ）、ステップＳ１３０２に戻り、探索装置１０００は、再度ツリー構造体生成処理を実行する（ステップＳ１３０２）。これにより、更新後のＤＢ９００内の情報により、あらたにツリー構造体が生成されることとなる。一方、計算終了である場合（ステップＳ１３０８：Ｙｅｓ）、一連の探索処理を終了する。
【００９２】
図１４は、図１３に示したツリー構造体生成処理（ステップＳ１３０２）の詳細な処理手順例を示すフローチャートである。まず、探索装置１０００は、階層インデックスｒをｒ＝０に設定し（ステップＳ１４０１）、階層ｒのボックス（この場合、ｒ＝０であるため、分割されていない初期状態の領域データ）を分割する（ステップＳ１４０２）。分割は、上述したように、辺を１／２にする。これにより、２次元の場合は４分割され、３次元の場合は、８分割される。
【００９３】
つぎに、探索装置１０００は、階層ｒをインクリメントする（ステップＳ１４０３）。これにより、分割されたボックスはインクリメント後の階層ｒのボックスとなる。そして、探索装置１０００は、階層ｒの未選択ボックスがあるか否かを判断する（ステップＳ１４０４）。未選択ボックスがある場合（ステップＳ１４０４：Ｙｅｓ）、探索装置１０００は、未選択ボックスを選択し（ステップＳ１４０５）、選択ボックス内に存在する粒子データを特定する（ステップＳ１４０６）。
【００９４】
このあと、探索装置１０００は、選択ボックス内の粒子データ数がしきい値以下であるか否かを判断する（ステップＳ１４０７）。しきい値以下でない場合（ステップＳ１４０７：Ｎｏ）、さらに分割することができるため、探索装置１０００は、選択ボックスを分割対象ボックスとして保持し（ステップＳ１４０８）、ステップＳ１４０４に戻る。一方、しきい値以下である場合（ステップＳ１４０７：Ｙｅｓ）、これ以上選択ボックスを分割できないため、ステップＳ１４０４に移行する。
【００９５】
また、ステップＳ１４０４において、階層ｒの未選択ボックスがない場合（ステップＳ１４０４：Ｎｏ）、探索装置１０００は、ｒ＞Ｒであるか否かを判断する（ステップＳ１４０９）。Ｒは階層の下限値である。ｒ＞Ｒでない場合（ステップＳ１４０９：Ｎｏ）、探索装置１０００は、ステップＳ１４０８で保持された分割対象ボックスをそれぞれ分割する（ステップＳ１４１０）。そして、ステップＳ１４０３に移行する。一方、ｒ＞Ｒである場合（ステップＳ１４０９：Ｙｅｓ）、ツリー構造体が生成できたため、ツリー構造体生成処理（ステップＳ１３０２）を終了し、ステップＳ１３０３に移行する。
【００９６】
図１５は、図１３に示した近傍粒子データ探索処理（ステップＳ１３０３）の詳細な処理手順例（その１）を示すフローチャートである。図１５では、変形対象が対象粒子データの外接形状データに設定されている場合の例である。まず、探索装置１０００は、粒子データ群の中で未選択粒子データがあるか否かを判断する（ステップＳ１５０１）。未選択粒子データがあると判断された場合（ステップＳ１５０１：Ｙｅｓ）、探索装置１０００は、未選択粒子データを選択する（ステップＳ１５０２）。選択された粒子データが対象粒子データｐｃである。
【００９７】
つぎに、探索装置１０００は、生成部１００１により、対象粒子データｐｃの影響領域ｅｃおよびその外接形状データｓｃを生成する（ステップＳ１５０３）。そして、探索装置１０００は、変形部１００３により、対象粒子データｐｃの変形勾配テンソルＦｃijにより影響領域および外接形状データを変形させる（ステップＳ１５０４）。
【００９８】
そして、探索装置１０００は、変形後の外接形状データＳＣに重複するボックスを特定する（ステップＳ１５０５）。ここでは、たとえば、ｔｒｅｅ法を用いて特定することになる。このあと、探索装置１０００は、決定部１００５により、重複ボックス内の粒子データを対象粒子データｐｃの近傍粒子データ候補に決定する（ステップＳ１５０６）。
【００９９】
つぎに、探索装置１０００は、未選択の近傍粒子データ候補があるか否かを判断する（ステップＳ１５０７）。未選択の近傍粒子データ候補がある場合（ステップＳ１５０７：Ｙｅｓ）、探索装置１０００は、未選択の近傍粒子データ候補を選択し（ステップＳ１５０８）、対象粒子データの変形後の影響領域ＥＣ内か否かを判断する（ステップＳ１５０９）。このとき、さらに、対象粒子データｐｃが近傍粒子データの影響領域内か否かを判断してもよい。変形後の影響領域ＥＣ内である場合（ステップＳ１５０９：Ｙｅｓ）、探索装置１０００は、近傍粒子データ候補を、対象粒子データｐｃの近傍粒子データに決定して、近傍粒子データの粒子ＩＤを対象粒子データのレコードに追加する（ステップＳ１５１０）。
【０１００】
また、対象粒子データｐｃが近傍粒子データ候補の影響領域内か否かを判断し、影響領域内と判断された場合は、対象粒子データｐｃを、近傍粒子データ候補の近傍粒子データに決定して、対象粒子データｐｃの粒子ＩＤを近傍粒子データのレコードに追加することとしてもよい。これにより、高速探索を実現することができる。
【０１０１】
一方、ステップＳ１５０９において、変形後の影響領域ＥＣ内でない場合（ステップＳ１５０９：Ｎｏ）、ステップＳ１５０７に戻る。また、ステップＳ１５０７において、未選択の近傍粒子データ候補がない場合（ステップＳ１５０７：Ｎｏ）、ステップＳ１５０１に戻る。そして、ステップＳ１５０１において、未選択粒子データがない場合（ステップＳ１５０１：Ｎｏ）、近傍粒子データ探索処理（ステップＳ１３０３）を終了し、ステップＳ１３０４に移行する。これにより、対象粒子データｐｃごとに近傍粒子データを探索することができる。
【０１０２】
ここで、ステップＳ１５０５での重複ボックスの特定例について具体的に説明する。なお、特定前では、例として図１１の（Ｄ）のように再帰的分割が完了しており、図１２に示したツリー構造体が生成されているものとする。
【０１０３】
図１６は、ステップＳ１５０５での重複ボックスの特定例を示す説明図である。まず、（Ａ）において、対象粒子データｐｃの影響領域ｅｃおよび外接形状データｓｃが変形され、変形後の影響領域ＥＣおよび変形後の外接形状データＳＣが生成される。つぎに、（Ｂ）では、探索装置１０００は、判断部１００４により、（Ａ）の状態から第１階層（ｒ＝１）のボックスｂ１〜ｂ４のうち、外接形状データＳＣと重複するボックスの有無を判断する。この場合、ボックスｂ１、ｂ２が重複していないため、特定候補から外される。
【０１０４】
同様に、（Ｃ）では、探索装置１０００は、判断部１００４により、（Ｂ）での重複ボックスｂ３，ｂ４において、第２階層（ｒ＝２）のボックスｂ３１〜ｂ３４，ｂ４１〜ｂ４４のうち、外接形状データＳＣと重複するボックスの有無を判断する。この場合、ボックスｂ３１，ｂ３３，ｂ４２，ｂ４４が重複していないため、特定候補から外される。
【０１０５】
同様に、（Ｄ）では、探索装置１０００は、判断部１００４により、（Ｃ）での重複ボックスｂ３２，ｂ３４，ｂ４１，ｂ４３において、第３階層（ｒ＝３）のボックスｂ３２１〜ｂ３２４，ｂ４１１〜ｂ４１４，ｂ４３１〜ｂ４３４、第２階層のボックスｂ３４（第３階層がないため）のうち、外接形状データＳＣと重複するボックスの有無を判断する。この場合、ボックスｂ４１１，ｂ４１２，ｂ４１４，ｂ４３２，ｂ４３３，ｂ４３４が重複していないため、特定候補から外される。
【０１０６】
（Ｄ）では、第３階層が最下層であるため、この段階で残されているボックスｂ３２１〜ｂ３２４，ｂ３４，ｂ４１３，ｂ４３１が、外接形状データＳＣとの重複ボックスとして特定されることになる。したがって、探索装置１０００は、重複ボックスｂ３２１〜ｂ３２４，ｂ３４，ｂ４１３，ｂ４４１の各々に存在する粒子データを近傍粒子データ候補に決定することになる。また、探索装置１０００は、判断部１００４により、重複ボックスｂ３２１〜ｂ３２４，ｂ３４，ｂ４１３，ｂ４３１の各々に存在する近傍粒子データ候補が、変形後の影響領域ＥＣと重複するかを判断することになる。そして、探索装置１０００は、重複した近傍粒子データ候補については、決定部１００５により、対象粒子データの近傍粒子データに決定することになる。
【０１０７】
図１７は、図１３に示した近傍粒子データ探索処理（ステップＳ１３０３）の詳細な処理手順例（その２）を示すフローチャートである。図１７では、変形対象が領域データ、すなわち、ボックスｂに設定されている場合の例である。まず、探索装置１０００は、粒子データ群の中で未選択粒子データがあるか否かを判断する（ステップＳ１７０１）。未選択粒子データがあると判断された場合（ステップＳ１７０１：Ｙｅｓ）、探索装置１０００は、未選択粒子データを選択する（ステップＳ１７０２）。選択された粒子データが対象粒子データｐｃである。
【０１０８】
つぎに、探索装置１０００は、生成部１００１により外接形状データｓｃを生成し、探索装置１０００は、変形部１００３により、対象粒子データｐｃの変形勾配テンソルＦｃijにより影響領域および外接形状データを変形させる（ステップＳ１７０３ａ）。対象粒子データｐｃの変形後の外接形状データＳＣの各座標軸における最大最小値によって特定される矩形（もしくは直方体）に重複するボックス（以下、重複ボックスと呼ぶ）を特定する（ステップＳ１７０３ｂ）。ここでは、たとえば、ｔｒｅｅ法を用いて特定することになる。なお、この重複ボックスの特定は変形後の外接形状データＳＣに外接する矩形（もしくは直方体）との重複を調べるものであるため、平行四辺形(もしくは平行六面体)としての重複を調べる近傍粒子データ探索処理（その１）のステップＳ１５０５よりも高速に行なわれる。そして、探索装置１０００は、対象粒子データｐｃの変形勾配テンソルＦｃijをＤＢ９００から読み出して、逆テンソルＦｃij-1を算出する（ステップＳ１７０４）。そして、探索装置１０００は、逆テンソルＦｃij-1で重複ボックスを変形させる（ステップＳ１７０５）。
【０１０９】
つぎに、探索装置１０００は、逆テンソルＦｃij-1で変形された重複ボックス群の中から、対象粒子データｐｃの影響領域ｅｃに重複するボックスを再度特定する（ステップＳ１７０６）。この再特定は、重複ボックス群の中から実行されるため、逆テンソルＦｃij-1による変形処理を最小限に抑制することができる。なお、ステップＳ１７０６で特定されたボックスを再重複ボックスと称す。
【０１１０】
このあと、探索装置１０００は、決定部１００５により、再重複ボックス内の粒子データを対象粒子データｐｃの近傍粒子データ候補に決定する（ステップＳ１７０７）。つぎに、探索装置１０００は、未選択の近傍粒子データ候補があるか否かを判断する（ステップＳ１７０８）。未選択の近傍粒子データ候補がある場合（ステップＳ１７０８：Ｙｅｓ）、探索装置１０００は、未選択の近傍粒子データ候補を選択し（ステップＳ１７０９）、対象粒子データｐｃの影響領域ｅｃ内か否かを判断する（ステップＳ１７１０）。このとき、さらに、対象粒子データｐｃが近傍粒子データの影響領域内か否かを判断してもよい。
【０１１１】
影響領域ｅｃ内である場合（ステップＳ１７１０：Ｙｅｓ）、探索装置１０００は、近傍粒子データ候補を、対象粒子データｐｃの近傍粒子データに決定して、近傍粒子データの粒子ＩＤを対象粒子データｐｃのレコードに追加する（ステップＳ１７１１）。
【０１１２】
また、対象粒子データｐｃが近傍粒子データ候補の逆テンソルＦｃij-1による変形後の影響領域内か否かを判断し、変形後の影響領域内と判断された場合は、対象粒子データを、近傍粒子データ候補の近傍粒子データに決定して、対象粒子データｐｃの粒子ＩＤを近傍粒子データのレコードに追加することとしてもよい。これにより、高速探索を実現することができる。
【０１１３】
一方、ステップＳ１７１０において、影響領域ｅｃ内でない場合（ステップＳ１７１０：Ｎｏ）、ステップＳ１７０８に戻る。また、ステップＳ１７０８において、未選択の近傍粒子データ候補がない場合（ステップＳ１７０８：Ｎｏ）、ステップＳ１７０１に戻る。そして、ステップＳ１７０１において、未選択粒子データがない場合（ステップＳ１７０１：Ｎｏ）、近傍粒子データ探索処理（ステップＳ１３０３）を終了し、ステップＳ１３０４に移行する。これにより、対象粒子データｐｃごとに近傍粒子データを探索することができる。なお、図１７では、重複ボックス群について逆テンソルＦｃij-1による変形を実行したが、ツリー構造体の全ボックスについて逆テンソルＦｃij-1による変形を実行することとしてもよい。
【０１１４】
ここで、ステップＳ１７０３ａ、Ｓ１７０３ｂでの重複ボックスの特定例について具体的に説明する。なお、特定前では、例として図１１の（Ｄ）のように再帰的分割が完了しており、図１２に示したツリー構造体が生成されているものとする。
【０１１５】
図１８は、ステップＳ１７０３ａ、Ｓ１７０３ｂでの重複ボックスの特定例を示す説明図である。まず、（Ａ）において、対象粒子データｐｃの変形後の影響領域ＥＣおよび変形後の外接形状データＳＣおよび変形後の外接形状ＳＣに接する矩形ＳＣ２が生成される。つぎに、（Ｂ）では、探索装置１０００は、判断部１００４により、（Ａ）の状態から第１階層（ｒ＝１）のボックスｂ１〜ｂ４のうち、矩形ＳＣ２と重複するボックスの有無を判断する。この場合、ボックスｂ１、ｂ２が重複していないため、特定候補から外される。
【０１１６】
同様に、（Ｃ）では、探索装置１０００は、判断部１００４により、（Ｂ）での重複ボックスｂ３，ｂ４において、第２階層（ｒ＝２）のボックスｂ３１〜ｂ３４，ｂ４１〜ｂ４４のうち、矩形ＳＣ２と重複するボックスの有無を判断する。この場合、ボックスｂ３１，ｂ３３，ｂ４２，ｂ４４が重複していないため、特定候補から外される。
【０１１７】
同様に、（Ｄ）では、探索装置１０００は、判断部１００４により、（Ｃ）での重複ボックスｂ３２，ｂ３４，ｂ４１，ｂ４３において、第３階層（ｒ＝３）のボックスｂ３２１〜ｂ３２４，ｂ４１１〜ｂ４１４，ｂ４３１〜ｂ４３４、第２階層のボックスｂ３４（第３階層がないため）のうち、矩形ＳＣ２と重複するボックスの有無を判断する。この場合、ボックスｂ４１２，ｂ４１４，ｂ４３２，ｂ４３３，ｂ４３４が重複していないため、特定候補から外される。
【０１１８】
（Ｄ）では、第３階層が最下層であるため、この段階で残されているボックスｂ３２１〜ｂ３２４，ｂ３４，ｂ４１１，ｂ４１３，ｂ４４１が、矩形ＳＣ２との重複ボックスとして特定されることになる。したがって、探索装置１０００は、図６や図７の（Ｂ）に示したように、重複ボックスｂ３２１〜ｂ３２４，ｂ３４，ｂ４１１，ｂ４１３，ｂ４３１の各々を逆テンソルＦｃij-1によって変形させる。
【０１１９】
そして、探索装置１０００は、判断部１００４により、変形後のボックスの各々と対象粒子ｐｃの変形前の影響領域ｅｃとで再重複を判断することになる。また、探索装置１０００は、決定部１００５により、変形した再重複ボックスに存在する粒子データを近傍粒子データ候補に決定することになる。また、探索装置１０００は、判断部１００４により、変形した再重複ボックスの各々に存在する近傍粒子データ候補が、影響領域ｅｃと重複するかを判断することになる。そして、探索装置１０００は、重複した近傍粒子データ候補については、決定部１００５により、対象粒子データの近傍粒子データに決定することになる。
【０１２０】
図１９は、探索装置１０００による探索処理手順例（その２）を示すフローチャートである。ここでは、図１５に示した近傍粒子データ探索処理（ステップＳ１３０３）を「第１の近傍粒子データ探索処理」と称し、図１７に示した近傍粒子データ探索処理（ステップＳ１３０３）を「第２の近傍粒子データ探索処理」と称す。図１３の探索処理手順例（その１）では、第１の近傍粒子データ探索処理または第２の近傍粒子データ探索処理のうちいずれか一方の探索処理を用いた例について説明したが、図１９では、いずれか一方の近傍粒子探索処理を適宜選択しながら探索をおこなう。
【０１２１】
まず、探索装置１０００は、ＤＢ９００から粒子データ群を読み込み（ステップＳ１９０１）、所定計算ステップ数経過したか否かを判断する（ステップＳ１９０２）。経過していない場合（ステップＳ１９０２：Ｎｏ）、探索装置１０００は、生成部１００１により、ツリー構造体生成処理を実行する（ステップＳ１９０３）。ツリー構造体生成処理（ステップＳ１９０３）は、ツリー構造体生成処理（ステップＳ１３０２）と同一処理である。ツリー構造体生成処理（ステップＳ１９０３）では、図１２に示したようなツリー構造体を生成する。
【０１２２】
つぎに、探索装置１０００は、近傍粒子データ探索処理を実行する（ステップＳ１９０４）。近傍粒子データ探索処理（ステップＳ１９０４）は、第１または第２の近傍粒子データ探索処理のうちいずれか一方が設定されて実行されることになる。
【０１２３】
近傍粒子データ探索処理（ステップＳ１９０４）のあと、探索装置１０００は、粒子データｐｋごとに、運動量を計算する（ステップＳ１９０５）。たとえば、上記式（６）で示したように、探索装置１０００は、粒子データｐｋごとに、加速度ａｋを計算する。そして、探索装置１０００は、上記式（７）〜（９）で示したように、粒子データｐｋごとに、変形勾配テンソルＦｋijや速度ｖ、位置情報を更新する（ステップＳ１９０６）。
【０１２４】
このあと、探索装置１０００は、時間刻み幅ｄｔの分だけ、時刻を更新して（ステップＳ１９０７）、計算結果（粒子データｐｋごとの近傍粒子データ、加速度ａｋ、速度ｖｋ、位置座標Ｃｋなど）を出力する（ステップＳ１９０８）。このあと、探索装置１０００は、計算終了か否かを判断する（ステップＳ１９０９）。たとえば、探索装置１０００は、所定計算ステップ数に到達したか否かを判断する。計算終了である場合（ステップＳ１９０９：Ｙｅｓ）、一連の探索処理を終了する。
【０１２５】
一方、計算終了でない場合（ステップＳ１９０９：Ｎｏ）、後述するステップＳ１９１３、Ｓ１９１４で第１および第２の近傍粒子データ探索処理が並列実行されたか否かを判断する（ステップＳ１９１０）。今回の計算ステップにおいて並列実行していない場合（ステップＳ１９１０：Ｎｏ）、ステップＳ１９０２に戻る。
【０１２６】
一方、並列実行した場合（ステップＳ１９１０：Ｙｅｓ）、ステップＳ１９１５で近傍粒子データが選択された方の近傍粒子データ探索処理を選択し（ステップＳ１９１１）、ステップＳ１９０２に戻る。ステップＳ１９１１で選択された近傍粒子データ探索処理が、次の計算ステップにおいてステップＳ１９０４で実行されることになる。
【０１２７】
また、ステップＳ１９０２において、所定計算ステップ数経過した場合（ステップＳ１９０２：Ｙｅｓ）、探索装置１０００は、生成部１００１により、ツリー構造体生成処理を実行する（ステップＳ１９１２）。ツリー構造体生成処理（ステップＳ１９１２）は、ツリー構造体生成処理（ステップＳ１３０２）と同一処理である。ツリー構造体生成処理（ステップＳ１９１２）では、図１２に示したようなツリー構造体を生成する。
【０１２８】
つぎに、探索装置１０００は、第１および第２の近傍粒子データ探索処理を並列実行する（ステップＳ１９１３、Ｓ１９１４）。そして、探索装置１０００は、先に探索が完了した方の近傍粒子データを選択して（ステップＳ１９１５）、ステップＳ１９０５において運動量を計算することになる（ステップＳ１９０５）。この場合、まだ探索が完了していない方の近傍粒子データ探索処理については、探索装置１０００は、先に探索が完了した方の近傍粒子データ探索処理の実行が完了した時点で停止し、途中まで得られた近傍粒子データを消去することになる。
【０１２９】
このように、探索装置１０００による探索処理手順例（その２）によれば、処理が速いほうの近傍粒子データ探索処理を選択するため、近傍粒子データ探索の高速化を図ることができる。
【０１３０】
以上説明したように、本実施の形態によれば、近傍粒子探索の効率化を図ることができる。具体的には、ｔｒｅｅ法をベースとして、粒子データが変形した場合においてもその外接形状データにより近傍粒子探索の効率化を図ることができる。また、本実施の形態では、影響領域内にｔｒｅｅ法のボックスが含まれるかどうか判断する手法として、第１の近傍粒子データ探索処理（図１５）と第２の近傍粒子データ探索処理（図１７）がある。
【０１３１】
第１の近傍粒子データ探索処理（図１５）は、対象粒子データの外接形状データを、対象粒子データの変形勾配テンソルで変形して平行四辺形または平行六面体とすることで、対象粒子データと領域データ（ボックス）との重複判断をおこなう。このように、影響領域の外接形状データを変形することで、変形しない外接形状データを用いる場合に比べて影響領域の外にある粒子を近傍粒子データ候補として扱う機会を少なくすることができる。したがって、計算負荷の低減化を図ることができる。
【０１３２】
これに対し、第２の近傍粒子データ探索処理（図１７）は、領域データ（ボックス）を、対象粒子データの変形勾配テンソルの逆テンソルで変形して平行四辺形または平行六面体とすることで、対象粒子データとの重複判断をおこなう。この場合、ｔｒｅｅ法の（逆テンソルでの変形前の）ボックスが影響領域に含まれる場合のみを取り扱うことができる。
【０１３３】
第１の近傍粒子データ探索処理（図１５）は、第２の近傍粒子データ探索処理（図１７）に比べて、逆テンソルを算出せずに済む分だけ計算量が少なくなり、計算負荷の低減化を図ることができる。
【０１３４】
第２の近傍粒子データ探索処理（図１７）では、重複しているボックスのみを再重複対象とすることができる。換言すれば、変形前から重複していないボックス内の粒子データは近傍粒子データになる可能性が低いため、そのようなボックスを再重複対象から除外することで、探索処理の効率化を図ることができる。
【０１３５】
また、第１の近傍粒子データ探索処理（図１５）と第２の近傍粒子データ探索処理（図１７）とで効率がよい方の処理を適宜選択することで、探索処理の効率化を図るとともに、探索処理の高速化を図ることができる。
【符号の説明】
【０１３６】
１０００  探索装置
１００１  生成部
１００２  設定部
１００３  変形部
１００４  判断部
１００５  決定部
１００６  格納部
１００７  更新部
【図１−１】
2013042212.tif 000011
【図１−２】
2013042212.tif 000012
【図２】
2013042212.tif 000013
【図３】
2013042212.tif 000014
【図４】
2013042212.tif 000015
【図５】
2013042212.tif 000016
【図６】
2013042212.tif 000017
【図７】
2013042212.tif 000018
【図８】
2013042212.tif 000019
【図９】
2013042212.tif 000020
【図１０】
2013042212.tif 000021
【図１１】
2013042212.tif 000022
【図１２】
2013042212.tif 000023
【図１３】
2013042212.tif 000024
【図１４】
2013042212.tif 000025
【図１５】
2013042212.tif 000026
【図１６】
2013042212.tif 000027
【図１７】
2013042212.tif 000028
【図１８】
2013042212.tif 000029
【図１９】
2013042212.tif 000030
【手続補正書】
【提出日】平成26年3月19日(2014.3.19)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
対象粒子の近傍に位置する近傍粒子の探索を行なう探索プログラムにおいて、
コンピュータに、
粒子データ群の各粒子データの位置情報および変形勾配テンソルを記憶する記憶装置から読み出された前記粒子データ群の中の対象粒子データの位置情報に基づいて、前記対象粒子データの影響領域に外接する外接形状データを生成させ、
前記粒子データ群のうちの少なくとも１つの粒子データが存在する領域データと、前記生成された外接形状データとのうちいずれか一方を、変形対象に設定させ、
前記設定された変形対象を、前記対象粒子データの変形勾配テンソルに基づいて変形させ、
前記変形後の変形対象と、前記外接形状データおよび前記領域データのうちの前記変形対象として設定されなかった非変形対象とが、重複するかを判断させ、
前記変形後の変形対象と前記非変形対象とが重複すると判断された場合、前記領域データ内の粒子データを、前記対象粒子データの近傍粒子データ候補に決定させ、
前記決定された決定結果を前記記憶装置に格納させることを特徴とする探索プログラム。
【請求項２】
前記変形対象の設定では、前記外接形状データを前記変形対象に設定し、
前記変形対象の変形では、前記設定によって前記変形対象に設定された外接形状データを、前記対象粒子データの変形勾配テンソルで変形させ、
前記変形後の変形対象と前記非変形対象とが重複するか否かの判断は、前記変形された外接形状データと、前記領域データとが、重複するかを判断することを特徴とする請求項１記載の探索プログラム。
【請求項３】
前記探索プログラムはさらに、
前記コンピュータに、前記近傍粒子データ候補が、前記変形により前記外接形状データの変形とともに変形された影響領域と重複するかを判断させ、
前記対象粒子データの近傍粒子データ候補の決定は、前記変形後の影響領域に重複すると判断された近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする請求項２記載の探索プログラム。
【請求項４】
前記変形対象の設定では、前記領域データを前記変形対象に設定し、
前記変形対象の変形では、前記設定によって前記変形対象に設定された領域データを、前記変形勾配テンソルの逆テンソルに基づいて変形させ、
前記変形後の変形対象と前記非変形対象とが重複するか否かの判断は、前記影響領域と、前記変形後の領域データとが重複するかを判断することを特徴とする請求項１記載の探索プログラム。
【請求項５】
前記探索プログラムはさらに、
前記コンピュータに、前記変形により前記領域データが変形された近傍粒子データ候補が、前記対象粒子データの影響領域と重複するかを判断させ、
前記対象粒子データの近傍粒子データ候補の決定は、前記判断された前記対象粒子データの影響領域と重複する近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記記憶装置への格納は、前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする請求項４記載の探索プログラム。
【請求項６】
粒子データ群の各粒子データの位置情報および変形勾配テンソルを記憶する記憶装置と、
前記記憶装置から読み出された前記粒子データ群の中の対象粒子データの位置情報に基づいて、前記対象粒子データの影響領域に外接する外接形状データを生成する生成部と、
前記粒子データ群のうち少なくとも１つが存在する領域データと前記生成部によって生成された外接形状データとのうちいずれか一方を、変形対象に設定する設定部と、
前記設定された変形対象を、前記対象粒子データの変形勾配テンソルに基づいて変形させる変形部と、
前記変形後の変形対象と、前記外接形状データおよび前記領域データのうちの非変形対象とが、重複するかを判断する判断部と、
前記判断部が、前記変形後の変形対象と前記非変形対象が重複すると判断された場合、前記領域データ内の粒子データを、前記対象粒子データの近傍粒子データ候補に決定する決定部と、
前記決定された決定結果を前記記憶装置に格納する格納部と、
を備えることを特徴とする探索装置。
【請求項７】
前記設定部では、前記外接形状データを前記変形対象に設定し、
前記変形部では、前記設定部によって前記変形対象に設定された外接形状データを、前記対象粒子データの変形勾配テンソルで変形させ、
前記判断部は、前記変形された外接形状データと、前記領域データとが、重複するかを判断することを特徴とする請求項６記載の探索装置。
【請求項８】
前記判断部は、前記近傍粒子データ候補が、前記変形により前記外接形状データの変形とともに変形された影響領域と重複するかを判断し、
前記決定部は、前記対象粒子データの近傍粒子データ候補の決定は、前記変形後の影響領域に重複すると判断された近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記格納部は、前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする請求項７記載の探索装置。
【請求項９】
前記設定部では、前記領域データを前記変形対象に設定し、
前記変形部では、前記設定部によって前記変形対象に設定された領域データを、前記変形勾配テンソルの逆テンソルに基づいて変形させ、
前記判断部は、前記影響領域と、前記変形後の領域データとが重複するかを判断することを特徴とする請求項６記載の探索装置。
【請求項１０】
前記判断部は、前記変形により前記領域データが変形された近傍粒子データ候補が、前記対象粒子データの影響領域と重複するかを判断し、
前記決定部は、前記判断された前記対象粒子データの影響領域と重複する近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記格納部は、前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする請求項９記載の探索装置。
【請求項１１】
前記設定部は、前記変形対象が前記外接形状データである第１の状態と、前記変形対象が前記領域データである第２の状態のうち、近傍粒子データが先に決定された方の状態の変形対象を次回の変形対象に設定することを特徴とする請求項６記載の探索装置。
【請求項１２】
対象粒子の近傍に位置する近傍粒子の探索を行なう探索方法において、
コンピュータが、
粒子データ群の中の対象粒子データの位置情報に基づいて、前記対象粒子データの影響領域に外接する外接形状データを生成し、
前記粒子データ群の粒子データのうち少なくとも１つの粒子データが存在する領域データと前記生成処理によって生成された外接形状データとのうちいずれか一方を、変形対象に設定し、
前記設定された変形対象を、前記対象粒子データの変形勾配テンソルに基づいて変形させ、
前記変形後の変形対象と、前記外接形状データおよび前記領域データのうちの前記変形対象として設定されなかった非変形対象とが、重複するかを判断し、
前記変形後の変形対象と前記非変形対象とが重複すると判断された場合、前記領域データ内の粒子データを、前記対象粒子データの近傍粒子データ候補に決定し、
前記決定された決定結果を記憶装置に格納することを特徴とする探索方法。
【請求項１３】
前記変形対象の設定では、前記外接形状データを前記変形対象に設定し、
前記変形対象の変形では、前記設定によって前記変形対象に設定された外接形状データを、前記対象粒子データの変形勾配テンソルで変形させ、
前記変形後の変形対象と前記非変形対象とが重複するか否かの判断は、前記変形された外接形状データと、前記領域データとが、重複するかを判断することを特徴とする請求項１２記載の探索方法。
【請求項１４】
前記探索方法はさらに、
前記コンピュータが、前記近傍粒子データ候補が、前記変形により前記外接形状データの変形とともに変形された影響領域と重複するかを判断し、
前記対象粒子データの近傍粒子データ候補の決定は、前記変形後の影響領域に重複すると判断された近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする請求項１３記載の探索方法。
【請求項１５】
前記変形対象の設定では、前記領域データを前記変形対象に設定し、
前記変形対象の変形では、前記設定によって前記変形対象に設定された領域データを、前記変形勾配テンソルの逆テンソルに基づいて変形させ、
前記変形後の変形対象と前記非変形対象とが重複するか否かの判断は、前記影響領域と、前記変形後の領域データとが重複するかを判断することを特徴とする請求項１２記載の探索方法。
【請求項１６】
前記探索方法はさらに、
前記コンピュータが、前記変形により前記領域データが変形された近傍粒子データ候補が、前記対象粒子データの影響領域と重複するかを判断し、
前記対象粒子データの近傍粒子データ候補の決定は、前記判断された前記対象粒子データの影響領域と重複する近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記記憶装置への格納は、前記対象粒子データと近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする請求項１５記載の探索方法。
【請求項１７】
前記変形対象の設定では、前記変形対象が前記外接形状データである第１の状態と、前記変形対象が前記領域データである第２の状態のうち、近傍粒子データが先に決定された方の状態の変形対象を次回の変形対象に設定することを特徴とする請求項１２記載の探索方法。
【手続補正２】
【補正対象書類名】明細書
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、探索プログラム、探索装置、および探索方法に関する。
【背景技術】
【０００２】
従来から、数値計算を用いて水や空気の流れを調べる流体解析や、圧縮されたゴムの振る舞いを調べる弾性体解析において、連続体を粒子の分布で表現するＳｍｏｏｔｈｅｄ  Ｐａｒｔｉｃｌｅｓ  Ｈｙｄｒｏｄｙｎａｍｉｃｓ（ＳＰＨ）法やＭｏｖｉｎｇ  Ｐａｒｔｉｃｌｅｓ  Ｓｅｍｉ−ｉｍｐｌｉｃｉｔ（ＭＰＳ）法が知られている。例えば、下記特許文献１では、超弾性体の大変形をＳＰＨ法を用いて数値解析する手法が開示されている。また、下記特許文献２では、ＭＰＳ法を用いて画像変形をおこなう手法が開示されている。
【０００３】
これら粒子ベースの標準的な手法においては、ある粒子に対してあらかじめ設定された領域（以下、「影響領域」と呼ぶ）の内に存在する相手粒子のみからの相互作用を計算する。そのため、数値解析の一部として影響領域内の粒子(以下、「近傍粒子」と呼ぶ)を計算領域全体の中から同定するプロセスが必要となる。標準的な粒子法のモデル化では、影響領域は球形とし各粒子には影響半径と呼ばれる数値を設定して済ませることが多い。
【０００４】
しかしながら、連続体が変形しながら空間中を運動する過程を扱うためには、各粒子に変形勾配テンソルＦijを持たせ、本来の形状から一次変換によって変形された影響領域を用いて解析する手法もある。変形勾配テンソルＦijの下付き添え字ｉ，ｊは座標軸を示すインデックスである。ここで変形勾配テンソルＦijは連続体の初期位置座標をｘ，変形後の位置座標をＸとしたとき、下記式（１）で与えられるテンソル場である。
【０００５】
【数１】
2013042212.tif 000031
【０００６】
近傍粒子を探索するために、すべての粒子対に対して近傍であるかどうかの判断をした場合、全粒子数の２乗に比例して判断の回数が必要になる。これは計算コストが極めて大きいため、近傍粒子の探索を高速化するための手法として、ｃｅｌｌ  ｉｎｄｅｘ法がある。
【０００７】
ｃｅｌｌ  ｉｎｄｅｘ法は計算領域を影響半径の幅のセルに分割し、対象粒子ｉの近傍粒子を自身が属するのと同じセル、及びそのセルと隣接するセルのみから探索する方法である。ｃｅｌｌ  ｉｎｄｅｘ法では粒子が各セルに均等に分布している場合には（全粒子数をＮとして）、Ｏ（Ｎ）の計算量が必要であり、全粒子対を扱う直接法のＯ（Ｎ2）に比べて高速化されている。
【０００８】
下記非特許文献１においては、非等方の影響領域を持つＳＰＨ法のための近傍粒子探索手法としてｃｅｌｌ  ｉｎｄｅｘ法をベースとした手法が開示されている。この手法では、各連続体粒子は、その影響領域のサイズ程度の大きさのセルに属するものとして、まず、そのセルに含まれる粒子群（以後、「粒子群ｉ」と呼ぶ。また、粒子群ｉに含まれる個別の粒子を指して「ｉ粒子」と呼ぶ）に共通の近傍粒子の候補となる粒子のリストを作成する。
【０００９】
一般に、近傍粒子候補リストには、粒子群ｉが含まれることになる。このリストに含まれる粒子と粒子群ｉの各粒子とが近傍粒子であるかどうかの判断はこれらの間の全粒子対に対して、個別に判断する。つまり、粒子群ｉに含まれる粒子数をＮi、近傍粒子候補リストに含まれる粒子数をＮjとすると、セル一つ当たりＯ（ＮiＮj）の回数だけ比較が必要になる。そのため、近傍粒子候補リストに含まれる粒子数を削減することができれば、近傍粒子探索にかかるコストを減らすことができる。
【００１０】
下記非特許文献１では、影響領域の変形を考慮に入れることで、作成される近傍粒子候補リストの粒子数を減らすことを提案している。具体的には次の手順をとる。
【００１１】
まず、ｉ粒子の座標の最小値と最大値を調べ、ｘｉmin，ｘｉmaxと呼ぶ。これらは座標軸ごとに設定され、粒子群ｉすべてを含む最小の空間Ｓｉ（２次元の場合は矩形で、３次元の場合は立方体。）を構成する。また、ｉ粒子の（一般には変形している）影響領域の最小・最大座標を求め、ｘｉｈmin，ｘｉｈmaxとする。これらは座標軸ごとに設定される。ｘｉｈmin，ｘｉｈmaxにより、空間Ｓｈｉ（２次元の場合は矩形で、３次元の場合は直方体。）が設定される。
【００１２】
空間Ｓｈｉは、空間Ｓｉを包含し、ｉ粒子の影響領域に含まれる粒子であれば必ず空間Ｓｈｉに含まれている。そこで、ある粒子ｊ1が空間Ｓｈｉに含まれていれば粒子ｊ1は近傍粒子候補リストに追加される。こうすることで、座標軸ごとに変形の度合いが異なることを考慮して、近傍粒子候補リストに含まれる粒子数が削減される。
【００１３】
一方、ある粒子ｊ2が空間Ｓｈｉの外にある場合でも、粒子ｊ2の影響領域に粒子ｉを含む場合がありえる。このような場合には、粒子ｊ2の影響領域に外接する矩形（または直方体）が空間Ｓｈｉと共通領域を持つときには、粒子ｊ2も近傍粒子候補リストに追加される。
【先行技術文献】
【特許文献】
【００１４】
【特許文献１】特開２００８−１５２４２３号公報
【特許文献２】特開２０１０−１１３４６７号公報
【非特許文献】
【００１５】
【非特許文献１】Ａｓｔｒｏｐｈｙｓｉｃａｌ  Ｊ．Ｓｕｐｐｌｅｍｅｎｔ  ｓｅｒｉｅｓ  １９９８，１１６，ｐｐ．２０８−２０９，Ｏｗｅｎ，Ｖｉｌｌｕｍｓｅｎ，Ｓｈａｐｉｒｏ，＆  Ｍａｒｔｅｌ（Ａｐｐｅｎｄｉｘ  Ｃ３）
【発明の概要】
【発明が解決しようとする課題】
【００１６】
しかしながら、上述した従来技術では、影響領域が座標軸に対して斜行する向きに大きく変形している粒子があった場合、影響領域としては重なり合っていないのに、その外接する矩形（または直方体）が重なりを持つときには近傍粒子候補リストに追加されてしまうことになる。このため、近傍粒子候補リストに必要以上の粒子を含むことになり、探索精度が低下し、またこれにより演算負荷が増大するという問題がある。
【００１７】
１つの側面では、本発明は、近傍粒子探索の効率化を図ることを目的とする。
【課題を解決するための手段】
【００１８】
対象粒子の近傍に位置する近傍粒子の探索を行なうにあたり、粒子データ群の各粒子データの位置情報および変形勾配テンソルを記憶する記憶装置から読み出された前記粒子データ群の中の対象粒子データの位置情報に基づいて、前記対象粒子データの影響領域に外接する外接形状データを生成し、前記粒子データ群のうちの少なくとも１つの粒子データが存在する領域データと、前記生成された外接形状データとのうちいずれか一方を、変形対象に設定し、前記設定された変形対象を、前記対象粒子データの変形勾配テンソルに基づいて変形し、前記変形後の変形対象と、前記外接形状データおよび前記領域データのうちの前記変形対象として設定されなかった非変形対象とが、重複するかを判断し、前記変形後の変形対象と前記非変形対象とが重複すると判断された場合、前記領域データ内の粒子データを、前記対象粒子データの近傍粒子データ候補に決定し、前記決定された決定結果を前記記憶装置に格納する探索プログラム、探索装置、および探索方法が提案される。
【発明の効果】
【００１９】
一態様によれば、近傍粒子探索の効率化を図ることができる。
【図面の簡単な説明】
【００２０】
【図１−１】図１−１は、２次元空間での近傍粒子探索例（その１）を示す説明図である。
【図１−２】図１−２は、非特許文献１で提案されている手法で影響領域とボックスｂとの重複を判定する基準を示した図である。
【図２】図２は、２次元空間での近傍粒子探索例（その２）を示す説明図である。
【図３】図３は、変形勾配テンソルＦｃijによる外接形状データｓｃの変形例（その１）を示す説明図である。
【図４】図４は、変形後の影響領域ＥＣおよび外接形状データＳＣを示す説明図である。
【図５】図５は、２次元空間での近傍粒子探索例（その３）を示す説明図である。
【図６】図６は、２次元空間での近傍粒子探索例（その４）を示す説明図である。
【図７】図７は、２次元空間での近傍粒子探索例（その５）を示す説明図である。
【図８】図８は、実施の形態にかかる探索装置のハードウェア構成例を示すブロック図である。
【図９】図９は、データベース（ＤＢ）の記憶内容例を示す説明図である。
【図１０】図１０は、探索装置の機能的構成例を示すブロック図である。
【図１１】図１１は、Ｔｒｅｅ法による再帰的ボックス分割例を示す説明図である。
【図１２】図１２は、図１１に示した再帰的分割によって得られた領域データ群のツリー構造体の一例を示す説明図である。
【図１３】図１３は、探索装置１０００による探索処理手順例（その１）を示すフローチャートである。
【図１４】図１４は、図１３に示したツリー構造体生成処理（ステップＳ１３０２）の詳細な処理手順例を示すフローチャートである。
【図１５】図１５は、図１３に示した近傍粒子データ探索処理（ステップＳ１３０３）の詳細な処理手順例（その１）を示すフローチャートである。
【図１６】図１６は、ステップＳ１５０５での重複ボックスの特定例を示す説明図である。
【図１７】図１７は、図１３に示した近傍粒子データ探索処理（ステップＳ１３０３）の詳細な処理手順例（その２）を示すフローチャートである。
【図１８】図１８は、ステップＳ１７０３での重複ボックスの特定例を示す説明図である。
【図１９】図１９は、探索装置１０００による探索処理手順例（その２）を示すフローチャートである。
【発明を実施するための形態】
【００２１】
以下に添付図面を参照して、この発明にかかる探索プログラム、探索装置、および探索方法の実施の形態を詳細に説明する。
【００２２】
図１−１は、２次元空間での近傍粒子探索例（その１）を示す説明図である。図１において（Ａ）は変形前の状態、（Ｂ）は変形後の状態を示している。（Ａ）において、ボックスｂは、粒子データｐ１〜ｐ６が存在する領域データである。各粒子データｐ１〜ｐ６は、影響領域ｅ１〜ｅ６を有する。影響領域とは、粒子ごとに設定された領域であり、影響領域内に他の粒子が存在する場合、当該他の粒子との間に相互作用が生じるものとして相互作用の計算がおこなわれる。影響領域は、その初期形状があらかじめ設定されており、必要に応じて変形されるものとする。影響領域の変形の具体的な手順については後述する。また、粒子データは、たとえば、粒子の中心を示すデータである。この場合、影響領域を粒子の形状を示す領域としてもよい。
【００２３】
影響領域は、一般には複雑な形状となるため、ボックスｂと共通部分を持つかどうかの判定がそのままでは難しい。そのため、影響領域に外接する外接形状データ（２次元では平行四辺形、３次元では平行六面体）を考え、これがボックスと共通部分を持つかどうか判定する。また、自粒子データの影響領域内に存在する他粒子データを、近傍粒子データと称す。近傍粒子データを用いることで、自粒子データの変形勾配テンソルや加速度、位置情報といった物性値を更新することができる。
【００２４】
対象粒子データｐｃが持つ変形勾配テンソルＦｃij（下記式（２）を参照。）により、対象粒子データｐｃの影響領域ｅｃおよび影響領域ｅｃを含む外接形状データｓｃを変形させる。本実施の形態では、対象粒子データｐｃの変形前の影響領域ｅｃがボックスｂと重複するかどうかと関係なく、変形後の影響領域が重複を持つかどうかを判定する必要がある。
【００２５】
【数２】
2013042212.tif 000032
【００２６】
上記式（２）において、変形勾配テンソルＦijの下付き添え字ｉ，ｊは座標軸を示すインデックスである。また、ｘｃは変形前の対象粒子データｐｃの初期位置座標、Ｘｃは変形後の位置座標である。
【００２７】
（Ｂ）は、変形勾配テンソルＦｃijによる変形後の状態である。変形勾配テンソルＦｃijにより、影響領域ｅｃは影響領域ＥＣに、外接形状データｓｃは外接形状データＳＣに変形される。そして、変形後の外接形状データＳＣとボックスｂとが重複するか否かが確認される。図１の（Ｂ）の場合、変形後の外接形状データＳＣとボックスｂとは重複しないため、ボックスｂ内の粒子データｐ１〜ｐ６は、対象粒子データｐｃの近傍粒子データの候補外となる。
【００２８】
図１−２は、非特許文献１で提案されている手法で影響領域とボックスｂとの重複を判定する基準を示した図である。変形後の影響領域ｅｃに外接する矩形ｓｃ２とボックスｂが重複するので、ボックスｂ内の粒子データｐ１〜ｐ６は、対象粒子データｐｃの近傍粒子データの候補となる。
【００２９】
図２は、２次元空間での近傍粒子探索例（その２）を示す説明図である。図２において（Ａ）は変形前の状態、（Ｂ）は変形後の状態を示している。図１とは、対象粒子データｐｃの位置と変形勾配テンソルＦｃijの値が異なるものとする。図２の（Ｂ）では、変形後の外接形状データＳＣとボックスｂとは重複するため、ボックスｂ内の粒子データｐ１〜ｐ６は、対象粒子データｐｃの近傍粒子データ候補となる。そして、ボックスｂ内の粒子データｐ１〜ｐ６のうち、対象粒子データｐｃの変形後の影響領域ＥＣ内に存在する粒子データｐ６が、対象粒子データｐｃの近傍粒子データとなる。
【００３０】
図３は、変形勾配テンソルＦｃijによる外接形状データｓｃの変形例（その１）を示す説明図である。図３において、（Ａ）は上述した非特許文献１での変形例を示しており、（Ｂ）は本実施の形態での変形例（図１および図２を参照）を示している。図３の（Ａ）では、（ｂ）において、（ａ）に示した変形前の影響領域ｅｃを変形勾配テンソルＦｃijで変形して影響領域ＥＣとする。そして、（ｃ）において、影響領域ＥＣの外接形状データｓｃが生成される。
【００３１】
一方、図３の（Ｂ）では、（ｂ）において、（ａ）に示した変形前の影響領域ｅｃの外接形状データｓｃを生成する。そして、（ｃ）において、影響領域ｅｃおよびその外接形状データｓｃを変形勾配テンソルＦｃijで変形して影響領域ＥＣおよび外接形状データＳＣとする。影響領域ＥＣの外接形状データＳＣが生成される。
【００３２】
このように、図３の（Ａ）では、外接形状データｓｃが変形勾配テンソルＦｃijで変形されないのに対し、図３の（Ｂ）では、外接形状データｓｃが変形勾配テンソルＦｃijで変形されることになる。このように、外接形状データｓｃを、影響領域ｅｃとともに変形勾配テンソルＦｃijで変形させることで、変形後の外接形状データＳＣは、影響領域ＥＣの変形に追従した形状となる。このため、図３の（Ａ）の外接形状データｓｃに比べ、外接形状データＳＣ内の影響領域ＥＣ以外の領域（２次元の場合は面積、３次元の場合は体積）が小さくなる。したがって、図１−２に示したような、ボックスｂとの無駄な重複を防止することができることになる。
【００３３】
図４は、変形後の影響領域ＥＣおよび外接形状データＳＣを示す説明図である。図４の（Ａ）では、連続体粒子データ群の体積を保存する前提の下で、影響領域ＥＣおよび外接形状データＳＣが、座標軸に斜交（４５度）する向きにλ倍伸び、それと直行する方向に２次元の場合には１／λ倍、３次元の場合には１／√（λ）倍縮んでいるものとする。非特許文献１では、外接形状データｓｃの各辺がλ倍になるため、近傍粒子候補リストを含むかどうか調べる必要のある領域の大きさは初期に比べて、２次元の場合にはλ2倍、３次元の場合にはλ3倍になる。
【００３４】
粒子密度が一定であれば、近傍粒子データであるかどうかを判定する粒子データ対の数が２次元の場合にはλ2倍、３次元の場合にはλ3倍になるということを意味する。一方で、体積を保存する前提の下では、変形勾配テンソルＦｃijの作る平行四辺形、もしくは、平行六面体はその面積、及び、体積を変えないため、近傍粒子データかどうかを判定する必要のある粒子データ対の数は大きく変化することはない。一方、座標軸に沿って連続体が伸びるときには、図４の（Ｂ）に示したように、外接形状データＳＣ，ｓｃの形状（２次元の場合は平行四辺形、３次元の場合は平行六面体）は一致することになる。
【００３５】
図５は、２次元空間での近傍粒子探索例（その３）を示す説明図である。図５において（Ａ）は変形前の状態、（Ｂ）は変形後の状態を示している。図１とは、対象粒子データｐｃの位置と変形勾配テンソルＦｃijの値が異なるものとする。図５の（Ｂ）では、図１の（Ｂ）とは異なり、変形後の外接形状データＳＣとボックスｂとは重複するため、ボックスｂ内の粒子データｐ１〜ｐ６は、対象粒子データｐｃの近傍粒子データ候補となる。しかしながら、ボックスｂ内の粒子データｐ１〜ｐ６のうち、対象粒子データｐｃの変形後の影響領域ＥＣ内に存在する粒子データは存在しないため、対象粒子データｐｃの近傍粒子データはない。
【００３６】
図５の（Ｂ）のような場合、影響領域ＥＣ内に含まれていないにもかかわらず、ボックスｂは外接形状データＳＣに重複するため、本来必要とされるよりも多くのボックスに対して重複判定をしてしまう可能性がある。変形による扁平率が大きい場合、この誤判定がより多く発生する。このため、このような誤判定が継続する場合は、変形対象を、対象粒子データｐｃの影響領域ｅｃおよび外接形状データｓｃではなく、ボックスｂとする。
【００３７】
図６は、２次元空間での近傍粒子探索例（その４）を示す説明図である。図６は、図５の（Ａ）から、対象粒子データｐｃの影響領域ｅｃおよび外接形状データｓｃではなく、ボックスｂを変形させた状態を示している。図６では、ボックスｂは、対象粒子データｐｃの変形勾配テンソルＦｃijの逆テンソルＦｃij-1により変形されている。これにより、図５の（Ａ）のボックスｂは、ボックスＢに変形され、粒子データｐ１〜ｐ６の影響領域ｅ１〜ｅ６は、影響領域Ｅ１〜Ｅ６に変形される。また、粒子データｐ１〜ｐ６の位置も変更される。
【００３８】
そして、対象粒子データｐｃの影響領域ｅｃと変形後のボックスＢとは重複しないため、粒子データｐ１〜ｐ６は、対象粒子データｐｃの近傍粒子データ候補に含まれないことになる。
【００３９】
図７は、２次元空間での近傍粒子探索例（その５）を示す説明図である。図７において（Ａ）は変形前の状態、（Ｂ）は変形後の状態を示している。図５とは、対象粒子データｐｃの位置と変形勾配テンソルＦｃijの値が異なるものとする。図７の（Ｂ）では、ボックスｂは、対象粒子データｐｃの変形勾配テンソルＦｃijの逆テンソルＦｃij-1により変形されている。これにより、図７の（Ａ）のボックスｂは、ボックスＢに変形され、粒子データｐ１〜ｐ６の影響領域ｅ１〜ｅ６は、影響領域Ｅ１〜Ｅ６に変形される。また、粒子データｐ１〜ｐ６の位置も変更される。
【００４０】
この場合、図６と異なり、対象粒子データｐｃの影響領域ｅｃと変形後のボックスＢとは重複するため、粒子データｐ１〜ｐ６は、対象粒子データｐｃの近傍粒子データ候補に含まれることになる。
【００４１】
ここで、変形勾配テンソルＦｃijを下記式（３）であらわした場合、その逆テンソルＦｃij-1は、下記式（４）によりあらわされる。
【００４２】
【数３】
2013042212.tif 000033
【００４３】
【数４】
2013042212.tif 000034
【００４４】
なお、上記式（４）中、Ｊは、下記式（５）となる。
【００４５】
Ｊ＝εijkＦｃ1iＦｃ2jＦｃ3k・・・（５）
【００４６】
ただし、εijkはレビ・チビタ記号で、添え字の組（ｉ，ｊ，ｋ）が（１，２，３），（２，３，１），（３，１，２）のときはεijk＝＋１、（１，３，２），（２，１，３），（３，２，１）のときはεijk＝−１、それ以外のときは、εijk＝０となる。
【００４７】
（探索装置のハードウェア構成例）
図８は、実施の形態にかかる探索装置のハードウェア構成例を示すブロック図である。図８において、探索装置は、ＣＰＵ（Ｃｅｎｔｒａｌ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔ）８０１と、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）８０２と、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）８０３と、磁気ディスクドライブ８０４と、磁気ディスク８０５と、光ディスクドライブ８０６と、光ディスク８０７と、ディスプレイ８０８と、Ｉ／Ｆ（Ｉｎｔｅｒｆａｃｅ）８０９と、キーボード８１０と、マウス８１１と、スキャナ７１２と、プリンタ７１３と、を備えている。また、各構成部はバス８００によってそれぞれ接続されている。
【００４８】
ここで、ＣＰＵ８０１は、探索装置の全体の制御を司る。ＲＯＭ８０２は、ブートプログラムなどのプログラムを記憶している。ＲＡＭ８０３は、ＣＰＵ８０１のワークエリアとして使用される。磁気ディスクドライブ８０４は、ＣＰＵ８０１の制御にしたがって磁気ディスク８０５に対するデータのリード／ライトを制御する。磁気ディスク８０５は、磁気ディスクドライブ８０４の制御で書き込まれたデータを記憶する。
【００４９】
光ディスクドライブ８０６は、ＣＰＵ８０１の制御にしたがって光ディスク８０７に対するデータのリード／ライトを制御する。光ディスク８０７は、光ディスクドライブ８０６の制御で書き込まれたデータを記憶したり、光ディスク８０７に記憶されたデータをコンピュータに読み取らせたりする。
【００５０】
ディスプレイ８０８は、カーソル、アイコンあるいはツールボックスをはじめ、文書、画像、機能情報などのデータを表示する。このディスプレイ８０８は、たとえば、ＣＲＴ（Ｃａｔｈｏｄｅ  Ｒａｙ  Ｔｕｂｅ）、ＴＦＴ（Ｔｈｉｎ  ＦＩｌｍ  Ｔｒａｎｓｉｓｔｏｒ）液晶ディスプレイ、プラズマディスプレイなどを採用することができる。
【００５１】
インターフェース（以下、「Ｉ／Ｆ」と略する。）８０９は、通信回線を通じてＬＡＮ（Ｌｏｃａｌ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、ＷＡＮ（Ｗｉｄｅ  Ａｒｅａ  Ｎｅｔｗｏｒｋ）、インターネットなどのネットワーク７１４に接続され、このネットワーク８１４を介して他の装置に接続される。そして、Ｉ／Ｆ８０９は、ネットワーク７１４と内部のインターフェースを司り、外部装置からのデータの入出力を制御する。Ｉ／Ｆ８０９には、たとえばモデムやＬＡＮアダプタなどを採用することができる。
【００５２】
キーボード８１０は、文字、数字、各種指示などの入力のためのキーを備え、データの入力をおこなう。また、タッチパネル式の入力パッドやテンキーなどであってもよい。マウス８１１は、カーソルの移動や範囲選択、あるいはウィンドウの移動やサイズの変更などをおこなう。ポインティングデバイスとして同様に機能を備えるものであれば、トラックボールやジョイスティックなどであってもよい。
【００５３】
スキャナ８１２は、画像を光学的に読み取り、探索装置内に画像データを取り込む。なお、スキャナ８１２は、ＯＣＲ（Ｏｐｔｉｃａｌ  Ｃｈａｒａｃｔｅｒ  Ｒｅａｄｅｒ）機能を持たせてもよい。また、プリンタ８１３は、画像データや文書データを印刷する。プリンタ８１３には、たとえば、レーザプリンタやインクジェットプリンタを採用することができる。
【００５４】
図９は、データベース（ＤＢ）の記憶内容例を示す説明図である。ＤＢ９００は、具体的には、たとえば、図８に示したＲＯＭ８０２、ＲＡＭ８０３、磁気ディスク８０５、光ディスク８０７などの記憶装置によりその機能を実現する。ＤＢ９００は、一例として、粒子ＩＤ項目、位置座標項目、影響半径項目、変形勾配テンソル項目、速度項目、質量項目、密度項目、応力テンソル項目、温度項目、加速度項目、近傍粒子ＩＤ項目を有する。そして、ＤＢ９００は、各項目の値を粒子データごとに記憶する。
【００５５】
本実施の形態では、一例として、初期状態においては、粒子データｐｋごとに、粒子ＩＤ：ｐｋ、位置座標Ｃｋ、影響半径Ｒｋ、変形勾配テンソルＦｋij、速度ｖｋ、質量ｍｋ、密度ρｋ、応力テンソルσｋ、温度Ｔｋの各初期値が格納されている。なお、加速度ａｋは計算により求められるため、初期値はないものとする。近傍粒子ＩＤも探索により格納されるため、初期値はないものとする。また、位置座標Ｃｋ、影響半径Ｒｋ、変形勾配テンソルＦｋij、速度ｖｋ、質量ｍｋ、密度ρｋ、応力テンソルσｋ、温度Ｔｋ、加速度ａｋ、近傍粒子ＩＤは、計算ステップごとに登録される。１つ前の計算ステップでの値は、保存しておいてもよく、上書きすることとしてもよい。なお、質量ｍｋ、密度ρｋ、応力テンソルσｋ、温度Ｔｋは固定値であってもよい。
【００５６】
（探索装置の機能的構成例）
図１０は、探索装置の機能的構成例を示すブロック図である。探索装置１０００は、ＤＢ９００と、生成部１００１と、設定部１００２と、変形部１００３と、判断部１００４と、決定部１００５と、格納部１００６と、更新部１００７と、を備えている。生成部１００１〜更新部１００７は、具体的には、たとえば、図８に示したＲＯＭ８０２、ＲＡＭ８０３、磁気ディスク８０５、光ディスク８０７などの記憶装置に記憶されたプログラムをＣＰＵ８０１に実行させることにより、または、Ｉ／Ｆ８０９により、その機能を実現する。
【００５７】
生成部１００１は、粒子群データが存在する計算領域を分割して、部分領域データ群を生成する。具体的には、たとえば、Ｔｒｅｅ法により、計算領域内を再帰的にボックスに分割する。ここで、Ｔｒｅｅ法による再帰的ボックス分割例について説明する。
【００５８】
図１１は、Ｔｒｅｅ法による再帰的ボックス分割例を示す説明図である。図１１では、辺の長さが１／２となるように分割していき、分割ブロック内の粒子データ数が１個以下、または、階層ｒ＝３になるまで、再帰的に分割をおこなう場合を例に挙げて説明する。階層ｒとは分割回数を示す。
【００５９】
図１１において、（Ａ）は、分割前の計算領域Ａを示している。分割前であるため、階層ｒはｒ＝０である。計算領域Ａ内の丸い図形群は、粒子データ群である。（Ｂ）は、（Ａ）の状態からの分割例を示している。（Ｂ）では計算領域Ａが４分割されることで、階層ｒはｒ＝１となり、ブロックｂ１〜ｂ４が生成される。（Ｂ）では階層ｒ＝１となり、また、各ブロックｂ１〜ｂ４の粒子データ数はそれぞれ２個以上存在するため各ブロックｂ１〜ｂ４については、さらに再帰的に分割がおこなわれる。
【００６０】
（Ｃ）は、（Ｂ）の状態からの分割例を示している。（Ｃ）では、（Ｂ）の各ブロックｂ１〜ｂ４が４分割されることで、ブロックｂ１１〜ｂ４４が生成される。（Ｂ）では階層ｒ＝２となる。また、ブロックｂ１１〜ｂ４４のうち、ブロックｂ１１，ｂ２２，ｂ１４，ｂ２３，ｂ３３，ｂ３４，ｂ４２内の粒子データ数は１個であるため、これ以上の分割はおこなわれない。それ以外のブロックｂ１２，ｂ１３，ｂ２１，ｂ２４，ｂ３１，ｂ３２，ｂ４１，ｂ４３，ｂ４４については、さらに再帰的に分割がおこなわれる。
【００６１】
（Ｄ）は、（Ｃ）の状態からの分割例を示している。（Ｄ）では、（Ｃ）の各ブロックｂ１２，ｂ１３，ｂ２１，ｂ２４，ｂ３１，ｂ３２，ｂ４１，ｂ４３，ｂ４４が４分割されることで、ブロックｂ１２１〜ｂ４４４が生成される。（Ｄ）では階層ｒ＝３となるため、ブロック内の粒子データ数にかかわらず、分割を終了する。このように、最終的に（Ｄ）で得られたブロック群が、分割領域データ群となる。
【００６２】
図１２は、図１１に示した再帰的分割によって得られた領域データ群のツリー構造体の一例を示す説明図である。図１２に示すツリー構造体が生成されると、ブロックの頂点座標とＤＢ９００内の粒子データの位置座標とにより、ブロック内の粒子データが特定される。そして、特定された粒子データの粒子ＩＤがツリー構造体の該当するブロック内に格納される。
【００６３】
たとえば、ブロックｂ１内には、ブロックｂ１内に存在する粒子データの粒子ＩＤが格納され、ブロックｂ１２内には、ブロックｂ１２内に存在する粒子データの粒子ＩＤが格納され、ブロックｂ１２３内には、ブロックｂ１２３内に存在する粒子データの粒子ＩＤが格納される。
【００６４】
また、図１０に戻り、生成部１００１は、粒子データ群の中から順次粒子データを指定する。指定された粒子データが対象粒子データｐｃである。粒子データｐｋが指定されると、生成部１００１は、ＤＢ９００から粒子データｐｋの位置座標Ｃｋおよび影響半径Ｒｋを抽出する。そして、生成部１００１は、位置座標Ｃｋおよび影響半径Ｒｋに基づいて、影響領域ｅｋを生成する。たとえば、２次元の場合の影響領域ｅｋは半径Ｒｋの円であり、３次元の場合の影響領域ｅｋは半径Ｒｋの球である。
【００６５】
また、生成部１００１は、粒子データ群の中の対象粒子データの位置情報に基づいて、対象粒子データの影響領域に外接する外接形状データを生成する。具体的には、たとえば、生成部１００１は、ＤＢ９００を参照して、粒子データ群の中から順次粒子データの粒子ＩＤを選択し、その位置情報となる位置座標Ｃｋを取得する。粒子ＩＤが選択された粒子データｐｋが対象粒子データｐｃである。つぎに、生成部１００１は、対象粒子データｐｃの影響半径を参照することで影響領域ｅｃを生成する。そして、生成部１００１は、影響領域ｅｃの外接形状データｓｃを生成する。
【００６６】
設定部１００２は、粒子データ群のうち少なくとも１つが存在する領域データであるブロックｂと生成部１００１によって生成された外接形状データｓｃとのうちいずれか一方を、変形対象に設定する。具体的には、たとえば、初期状態では、外接形状データｓｃを変形対象とし、領域データであるブロックｂを非変形対象とする。また、初期状態では、領域データであるブロックｂを変形対象とし、外接形状データｓｃを非変形対象としてもよい。また、設定部１００２は、変形対象を外接形状データｓｃから領域データに、または、領域データであるブロックｂから外接形状データｓｃに切替設定することもできる。具体的には、設定部１００２は、所定の切替タイミング、たとえば、所定時間経過する都度、交互に切り替えることができる。
【００６７】
変形部１００３は、設定部１００２によって設定された変形対象を、対象粒子データｐｃの変形勾配テンソルＦｃijに基づいて変形させる。具体的には、たとえば、変形対象が外接形状データｓｃである場合、図３の（Ｂ）に示したように、外接形状データｓｃ（影響領域ｅｃ含む）に変形勾配テンソルＦｃijを施すことで、外接形状データｓｃ（影響領域ｅｃ含む）が変形して、外接形状データＳＣ（影響領域ＥＣ含む）が得られる。
【００６８】
一方、変形対象が領域データ（たとえば、ブロックｂ）である場合、変形勾配テンソルＦｃijの逆テンソルＦｃij-1を算出する。そして、図６に示したように、ブロックｂに逆テンソルＦｃij-1を施すことで、ブロックｂ（影響領域ｅｃを含む）が変形して、ブロックＢ（影響領域Ｅ１〜Ｅ６を含む）が得られる。
【００６９】
判断部１００４は、変形部１００３による変形後の変形対象と、外接形状データおよび領域データのうち変形対象として設定されなかった非変形対象とが、重複するか否かを判断する。具体的には、たとえば、変形対象が外接形状データｓｃである場合、変形後の外接形状データＳＣとブロックｂとの重複を判断する。たとえば、判断部１００４は、図１―１の（Ｂ）のケースでは重複していないと判断する。また、図２の（Ｂ）や図５の（Ｂ）のケースでは重複すると判断する。
【００７０】
決定部１００５は、判断部１００４によって重複すると判断された場合、領域データ内の粒子データを、対象粒子データｐｃの近傍粒子データ候補に決定する。具体的には、たとえば、図１―１の（Ｂ）のケースでは重複していないため、近傍粒子データ候補は決定されない。また、図２の（Ｂ）や図５の（Ｂ）のケースでは重複すると判断されるため、決定部１００５は、ブロックｂ内の粒子データｐ１〜ｐ６を対象粒子データｐｃの近傍粒子データ候補に決定する。
【００７１】
格納部１００６は、決定部１００５によって決定された決定結果を記憶装置に格納する。具体的には、たとえば、格納部１００６は、粒子データごとに、近傍粒子データ候補の粒子ＩＤをＤＢ９００に格納する。
【００７２】
また、判断部１００４は、変形対象が外接形状データｓｃである場合、決定部１００５によって近傍粒子データ候補が決定されたことにより、近傍粒子データ候補が、変形部１００３により外接形状データｓｃの変形とともに変形された影響領域ＥＣと重複するか否かを判断する。具体的には、たとえば、図２の（Ｂ）のケースでは、近傍粒子データ候補は粒子データｐ１〜ｐ６であり、このうち粒子データｐ６が影響領域ＥＣと重複する。一方、図５の（Ｂ）のケースでは、近傍粒子データ候補は粒子データｐ１〜ｐ６であるが、影響領域ＥＣと重複する粒子データは存在しない。
【００７３】
そして、決定部１００５は、影響領域ＥＣと重複する近傍粒子データ候補がある場合、当該近傍粒子データ候補を近傍粒子データに決定する。このあと、格納部１００６は、近傍粒子データの粒子ＩＤを、対象粒子データと関連付けて記憶する。たとえば、ＤＢ９００内の対象粒子データのレコードにおける近傍粒子ＩＤ項目に、近傍粒子ＩＤが格納される。
【００７４】
また、判断部１００４は、変形対象が領域データである場合、決定部１００５によって近傍粒子データ候補が決定されたことにより、近傍粒子データ候補が、（変形されていない）対象粒子データｐｃの影響領域ｅｃと重複するか否かを判断する。具体的には、たとえば、図６のケースでは、近傍粒子データ候補は粒子データｐ１〜ｐ６であり、影響領域ｅｃと重複する粒子データは存在しない。
【００７５】
一方、図７の（Ｂ）のケースでは、近傍粒子データ候補は粒子データｐ１〜ｐ６であり、このうち、位置が変更された粒子データｐ６が、（変形されていない）対象粒子データの影響領域ｅｃと重複する。したがって、決定部１００５は、粒子データｐ６を対象粒子データｐｃの近傍粒子データに決定することになる。なお、図７の（Ｂ）の例において、対象粒子データｐｃも、粒子データｐ６の影響領域Ｅ６と重複するとした場合、決定部１００５は、対象粒子データｐｃを粒子データｐ６の近傍粒子データに決定することができる。
【００７６】
この場合、格納部１００６は、粒子データｐ６のレコードに、対象粒子データｐｃの粒子ＩＤを格納する。このように、互いに重複しあう粒子データを近傍粒子データとして決定、格納することで、探索処理の高速化を図ることができる。このような処理は、変形対象が外接形状データｓｃである場合も同様である。
【００７７】
更新部１００７は、対象粒子データｐｃごとに、対象粒子データｐｃと対象粒子データｐｃに関連付けられた近傍粒子データとに基づいて、対象粒子データｐｃの変形勾配テンソルおよび位置情報を更新する。
【００７８】
具体的には、たとえば、更新部１００７は、あらかじめ粒子データ群に設定された物理モデルに従って、連続体粒子の運動を解く。たとえば、弾性体をモデル化した連続体粒子に対しては下記式（６）を解いて、粒子データｐｋごとに加速度ａｋを求める。なお、下記式（６）において、ａiは加速度ａｋ、ｍijは質量ｍｋ、ρijは密度ρｋ、σijは応力テンソルσｋ、Ｗはカーネル関数である。上付き添え字Ｉ（ｋに相当），Ｊは粒子のインデックス、下付き添え字ｉ，ｊは座標軸を示すインデックスであり、座標軸のインデックスｊについては縮約の規約を適用する。和の範囲Ｊは各粒子Ｉ（粒子データｐｋ）に対して、その近傍粒子データの間を渡る。
【００７９】
【数５】
2013042212.tif 000035
【００８０】
また、各粒子データｐｋの位置座標Ｃｋが変化するのに応じて粒子データｐｋごとに変形勾配テンソルＦｋijを算出する。たとえば、下記式（７）によって得られる。ここで、δijはクロネッカー・デルタ、ｄｘは粒子データｐｋの変位である。
【００８１】
【数６】
2013042212.tif 000036
【００８２】
最後に、求められた加速度ａｋを用いて粒子データｐｋごとに速度ｖｋを時間積分し、速度ｖｋを用いて粒子データｐｋごとに位置座標Ｃｋを時間積分し、時刻を時間刻みの分だけ進めると１計算ステップ分の計算が終了する。
【００８３】
【数７】
2013042212.tif 000037
【００８４】
【数８】
2013042212.tif 000038
【００８５】
上記式（８）のｖIi,newは、１計算ステップ後の粒子データｐｋの速度である。上記式（８）のｖIiは、現時刻の速度ｖｋである。上記式（９）のｘIi,newは、１計算ステップ後の粒子データｐｋの位置座標Ｃｋである。上記式（９）のｘIiは、現時刻の位置座標である。ｄｔは、１計算ステップ分の時間刻み幅である。なお、ｄｔは固定の値としてあらかじめ決めておく、たとえば、ｃsを粒子データｐｋの音速、ｈを粒子データｐｋの典型的な影響領域ｅｋのサイズとして、ｄｔ＝ｈ／ｃsとすればよい。なお、必要に応じて計算結果は外部ファイルとして出力される。該出力ファイルは、別に用意されたプログラムで必要な数値や図を画面に表示したり、紙に印刷したりするときに利用される。
【００８６】
また、設定部１００２では、変形対象が外接形状データｓｃである第１の状態と、変形対象が領域データである第２の状態のうち、近傍粒子データが先に決定された方の状態の変形対象を次回の変形対象に設定する。たとえば、第１の状態と第２の状態とで並列実行をおこなって、先に実行完了した方の変形対象を次回の変形対象とする。このようにすることで、実行時間が短いほうのデータが変形対象となるため、探索処理の高速化を図ることができる。
【００８７】
＜探索処理手順＞
図１３は、探索装置１０００による探索処理手順例（その１）を示すフローチャートである。まず、探索装置１０００は、ＤＢ９００から粒子データ群を読み込み（ステップＳ１３０１）、生成部１００１により、ツリー構造体生成処理を実行する（ステップＳ１３０２）。ツリー構造体生成処理（ステップＳ１３０２）では、図１２に示したようなツリー構造体を生成する。ツリー構造体生成処理（ステップＳ１３０２）の詳細は、図１４で説明する。
【００８８】
つぎに、探索装置１０００は、近傍粒子データ探索処理を実行する（ステップＳ１３０３）。近傍粒子データ探索処理（ステップＳ１３０３）では、粒子データｐｋごとに、近傍粒子データを探索する。近傍粒子データ探索処理（ステップＳ１３０３）の詳細は、図１５で説明する。
【００８９】
近傍粒子データ探索処理（ステップＳ１３０３）のあと、探索装置１０００は、粒子データｐｋごとに、運動量を計算する（ステップＳ１３０４）。たとえば、上記式（６）で示したように、探索装置１０００は、粒子データｐｋごとに、加速度ａｋを計算する。そして、探索装置１０００は、上記式（７）〜（９）で示したように、粒子データｐｋごとに、変形勾配テンソルＦｋijや速度ｖ、位置情報ｘｋを更新する（ステップＳ１３０５）。
【００９０】
このあと、探索装置１０００は、１計算ステップ（時間刻み幅ｄｔ）更新して（ステップＳ１３０６）、計算結果（粒子データｐｋごとの近傍粒子データ、加速度ａｋ、速度ｖｋ、位置座標Ｃｋなど）を出力する（ステップＳ１３０７）。このあと、探索装置１０００は、計算終了か否かを判断する（ステップＳ１３０８）。
【００９１】
たとえば、探索装置１０００は、所定計算ステップ数に到達したか否かを判断する。計算終了でない場合（ステップＳ１３０７：Ｎｏ）、ステップＳ１３０２に戻り、探索装置１０００は、再度ツリー構造体生成処理を実行する（ステップＳ１３０２）。これにより、更新後のＤＢ９００内の情報により、あらたにツリー構造体が生成されることとなる。一方、計算終了である場合（ステップＳ１３０８：Ｙｅｓ）、一連の探索処理を終了する。
【００９２】
図１４は、図１３に示したツリー構造体生成処理（ステップＳ１３０２）の詳細な処理手順例を示すフローチャートである。まず、探索装置１０００は、階層インデックスｒをｒ＝０に設定し（ステップＳ１４０１）、階層ｒのボックス（この場合、ｒ＝０であるため、分割されていない初期状態の領域データ）を分割する（ステップＳ１４０２）。分割は、上述したように、辺を１／２にする。これにより、２次元の場合は４分割され、３次元の場合は、８分割される。
【００９３】
つぎに、探索装置１０００は、階層ｒをインクリメントする（ステップＳ１４０３）。これにより、分割されたボックスはインクリメント後の階層ｒのボックスとなる。そして、探索装置１０００は、階層ｒの未選択ボックスがあるか否かを判断する（ステップＳ１４０４）。未選択ボックスがある場合（ステップＳ１４０４：Ｙｅｓ）、探索装置１０００は、未選択ボックスを選択し（ステップＳ１４０５）、選択ボックス内に存在する粒子データを特定する（ステップＳ１４０６）。
【００９４】
このあと、探索装置１０００は、選択ボックス内の粒子データ数がしきい値以下であるか否かを判断する（ステップＳ１４０７）。しきい値以下でない場合（ステップＳ１４０７：Ｎｏ）、さらに分割することができるため、探索装置１０００は、選択ボックスを分割対象ボックスとして保持し（ステップＳ１４０８）、ステップＳ１４０４に戻る。一方、しきい値以下である場合（ステップＳ１４０７：Ｙｅｓ）、これ以上選択ボックスを分割できないため、ステップＳ１４０４に移行する。
【００９５】
また、ステップＳ１４０４において、階層ｒの未選択ボックスがない場合（ステップＳ１４０４：Ｎｏ）、探索装置１０００は、ｒ＞Ｒであるか否かを判断する（ステップＳ１４０９）。Ｒは階層の下限値である。ｒ＞Ｒでない場合（ステップＳ１４０９：Ｎｏ）、探索装置１０００は、ステップＳ１４０８で保持された分割対象ボックスをそれぞれ分割する（ステップＳ１４１０）。そして、ステップＳ１４０３に移行する。一方、ｒ＞Ｒである場合（ステップＳ１４０９：Ｙｅｓ）、ツリー構造体が生成できたため、ツリー構造体生成処理（ステップＳ１３０２）を終了し、ステップＳ１３０３に移行する。
【００９６】
図１５は、図１３に示した近傍粒子データ探索処理（ステップＳ１３０３）の詳細な処理手順例（その１）を示すフローチャートである。図１５では、変形対象が対象粒子データの外接形状データに設定されている場合の例である。まず、探索装置１０００は、粒子データ群の中で未選択粒子データがあるか否かを判断する（ステップＳ１５０１）。未選択粒子データがあると判断された場合（ステップＳ１５０１：Ｙｅｓ）、探索装置１０００は、未選択粒子データを選択する（ステップＳ１５０２）。選択された粒子データが対象粒子データｐｃである。
【００９７】
つぎに、探索装置１０００は、生成部１００１により、対象粒子データｐｃの影響領域ｅｃおよびその外接形状データｓｃを生成する（ステップＳ１５０３）。そして、探索装置１０００は、変形部１００３により、対象粒子データｐｃの変形勾配テンソルＦｃijにより影響領域および外接形状データを変形させる（ステップＳ１５０４）。
【００９８】
そして、探索装置１０００は、変形後の外接形状データＳＣに重複するボックスを特定する（ステップＳ１５０５）。ここでは、たとえば、ｔｒｅｅ法を用いて特定することになる。このあと、探索装置１０００は、決定部１００５により、重複ボックス内の粒子データを対象粒子データｐｃの近傍粒子データ候補に決定する（ステップＳ１５０６）。
【００９９】
つぎに、探索装置１０００は、未選択の近傍粒子データ候補があるか否かを判断する（ステップＳ１５０７）。未選択の近傍粒子データ候補がある場合（ステップＳ１５０７：Ｙｅｓ）、探索装置１０００は、未選択の近傍粒子データ候補を選択し（ステップＳ１５０８）、対象粒子データの変形後の影響領域ＥＣ内か否かを判断する（ステップＳ１５０９）。このとき、さらに、対象粒子データｐｃが近傍粒子データの影響領域内か否かを判断してもよい。変形後の影響領域ＥＣ内である場合（ステップＳ１５０９：Ｙｅｓ）、探索装置１０００は、近傍粒子データ候補を、対象粒子データｐｃの近傍粒子データに決定して、近傍粒子データの粒子ＩＤを対象粒子データのレコードに追加する（ステップＳ１５１０）。
【０１００】
また、対象粒子データｐｃが近傍粒子データ候補の影響領域内か否かを判断し、影響領域内と判断された場合は、対象粒子データｐｃを、近傍粒子データ候補の近傍粒子データに決定して、対象粒子データｐｃの粒子ＩＤを近傍粒子データのレコードに追加することとしてもよい。これにより、高速探索を実現することができる。
【０１０１】
一方、ステップＳ１５０９において、変形後の影響領域ＥＣ内でない場合（ステップＳ１５０９：Ｎｏ）、ステップＳ１５０７に戻る。また、ステップＳ１５０７において、未選択の近傍粒子データ候補がない場合（ステップＳ１５０７：Ｎｏ）、ステップＳ１５０１に戻る。そして、ステップＳ１５０１において、未選択粒子データがない場合（ステップＳ１５０１：Ｎｏ）、近傍粒子データ探索処理（ステップＳ１３０３）を終了し、ステップＳ１３０４に移行する。これにより、対象粒子データｐｃごとに近傍粒子データを探索することができる。
【０１０２】
ここで、ステップＳ１５０５での重複ボックスの特定例について具体的に説明する。なお、特定前では、例として図１１の（Ｄ）のように再帰的分割が完了しており、図１２に示したツリー構造体が生成されているものとする。
【０１０３】
図１６は、ステップＳ１５０５での重複ボックスの特定例を示す説明図である。まず、（Ａ）において、対象粒子データｐｃの影響領域ｅｃおよび外接形状データｓｃが変形され、変形後の影響領域ＥＣおよび変形後の外接形状データＳＣが生成される。つぎに、（Ｂ）では、探索装置１０００は、判断部１００４により、（Ａ）の状態から第１階層（ｒ＝１）のボックスｂ１〜ｂ４のうち、外接形状データＳＣと重複するボックスの有無を判断する。この場合、ボックスｂ１、ｂ２が重複していないため、特定候補から外される。
【０１０４】
同様に、（Ｃ）では、探索装置１０００は、判断部１００４により、（Ｂ）での重複ボックスｂ３，ｂ４において、第２階層（ｒ＝２）のボックスｂ３１〜ｂ３４，ｂ４１〜ｂ４４のうち、外接形状データＳＣと重複するボックスの有無を判断する。この場合、ボックスｂ３１，ｂ３３，ｂ４２，ｂ４４が重複していないため、特定候補から外される。
【０１０５】
同様に、（Ｄ）では、探索装置１０００は、判断部１００４により、（Ｃ）での重複ボックスｂ３２，ｂ３４，ｂ４１，ｂ４３において、第３階層（ｒ＝３）のボックスｂ３２１〜ｂ３２４，ｂ４１１〜ｂ４１４，ｂ４３１〜ｂ４３４、第２階層のボックスｂ３４（第３階層がないため）のうち、外接形状データＳＣと重複するボックスの有無を判断する。この場合、ボックスｂ４１１，ｂ４１２，ｂ４１４，ｂ４３２，ｂ４３３，ｂ４３４が重複していないため、特定候補から外される。
【０１０６】
（Ｄ）では、第３階層が最下層であるため、この段階で残されているボックスｂ３２１〜ｂ３２４，ｂ３４，ｂ４１３，ｂ４３１が、外接形状データＳＣとの重複ボックスとして特定されることになる。したがって、探索装置１０００は、重複ボックスｂ３２１〜ｂ３２４，ｂ３４，ｂ４１３，ｂ４４１の各々に存在する粒子データを近傍粒子データ候補に決定することになる。また、探索装置１０００は、判断部１００４により、重複ボックスｂ３２１〜ｂ３２４，ｂ３４，ｂ４１３，ｂ４３１の各々に存在する近傍粒子データ候補が、変形後の影響領域ＥＣと重複するかを判断することになる。そして、探索装置１０００は、重複した近傍粒子データ候補については、決定部１００５により、対象粒子データの近傍粒子データに決定することになる。
【０１０７】
図１７は、図１３に示した近傍粒子データ探索処理（ステップＳ１３０３）の詳細な処理手順例（その２）を示すフローチャートである。図１７では、変形対象が領域データ、すなわち、ボックスｂに設定されている場合の例である。まず、探索装置１０００は、粒子データ群の中で未選択粒子データがあるか否かを判断する（ステップＳ１７０１）。未選択粒子データがあると判断された場合（ステップＳ１７０１：Ｙｅｓ）、探索装置１０００は、未選択粒子データを選択する（ステップＳ１７０２）。選択された粒子データが対象粒子データｐｃである。
【０１０８】
つぎに、探索装置１０００は、生成部１００１により外接形状データｓｃを生成し、探索装置１０００は、変形部１００３により、対象粒子データｐｃの変形勾配テンソルＦｃijにより影響領域および外接形状データを変形させる（ステップＳ１７０３ａ）。対象粒子データｐｃの変形後の外接形状データＳＣの各座標軸における最大最小値によって特定される矩形（もしくは直方体）に重複するボックス（以下、重複ボックスと呼ぶ）を特定する（ステップＳ１７０３ｂ）。ここでは、たとえば、ｔｒｅｅ法を用いて特定することになる。なお、この重複ボックスの特定は変形後の外接形状データＳＣに外接する矩形（もしくは直方体）との重複を調べるものであるため、平行四辺形(もしくは平行六面体)としての重複を調べる近傍粒子データ探索処理（その１）のステップＳ１５０５よりも高速に行なわれる。そして、探索装置１０００は、対象粒子データｐｃの変形勾配テンソルＦｃijをＤＢ９００から読み出して、逆テンソルＦｃij-1を算出する（ステップＳ１７０４）。そして、探索装置１０００は、逆テンソルＦｃij-1で重複ボックスを変形させる（ステップＳ１７０５）。
【０１０９】
つぎに、探索装置１０００は、逆テンソルＦｃij-1で変形された重複ボックス群の中から、対象粒子データｐｃの影響領域ｅｃに重複するボックスを再度特定する（ステップＳ１７０６）。この再特定は、重複ボックス群の中から実行されるため、逆テンソルＦｃij-1による変形処理を最小限に抑制することができる。なお、ステップＳ１７０６で特定されたボックスを再重複ボックスと称す。
【０１１０】
このあと、探索装置１０００は、決定部１００５により、再重複ボックス内の粒子データを対象粒子データｐｃの近傍粒子データ候補に決定する（ステップＳ１７０７）。つぎに、探索装置１０００は、未選択の近傍粒子データ候補があるか否かを判断する（ステップＳ１７０８）。未選択の近傍粒子データ候補がある場合（ステップＳ１７０８：Ｙｅｓ）、探索装置１０００は、未選択の近傍粒子データ候補を選択し（ステップＳ１７０９）、対象粒子データｐｃの影響領域ｅｃ内か否かを判断する（ステップＳ１７１０）。このとき、さらに、対象粒子データｐｃが近傍粒子データの影響領域内か否かを判断してもよい。
【０１１１】
影響領域ｅｃ内である場合（ステップＳ１７１０：Ｙｅｓ）、探索装置１０００は、近傍粒子データ候補を、対象粒子データｐｃの近傍粒子データに決定して、近傍粒子データの粒子ＩＤを対象粒子データｐｃのレコードに追加する（ステップＳ１７１１）。
【０１１２】
また、対象粒子データｐｃが近傍粒子データ候補の逆テンソルＦｃij-1による変形後の影響領域内か否かを判断し、変形後の影響領域内と判断された場合は、対象粒子データを、近傍粒子データ候補の近傍粒子データに決定して、対象粒子データｐｃの粒子ＩＤを近傍粒子データのレコードに追加することとしてもよい。これにより、高速探索を実現することができる。
【０１１３】
一方、ステップＳ１７１０において、影響領域ｅｃ内でない場合（ステップＳ１７１０：Ｎｏ）、ステップＳ１７０８に戻る。また、ステップＳ１７０８において、未選択の近傍粒子データ候補がない場合（ステップＳ１７０８：Ｎｏ）、ステップＳ１７０１に戻る。そして、ステップＳ１７０１において、未選択粒子データがない場合（ステップＳ１７０１：Ｎｏ）、近傍粒子データ探索処理（ステップＳ１３０３）を終了し、ステップＳ１３０４に移行する。これにより、対象粒子データｐｃごとに近傍粒子データを探索することができる。なお、図１７では、重複ボックス群について逆テンソルＦｃij-1による変形を実行したが、ツリー構造体の全ボックスについて逆テンソルＦｃij-1による変形を実行することとしてもよい。
【０１１４】
ここで、ステップＳ１７０３ａ、Ｓ１７０３ｂでの重複ボックスの特定例について具体的に説明する。なお、特定前では、例として図１１の（Ｄ）のように再帰的分割が完了しており、図１２に示したツリー構造体が生成されているものとする。
【０１１５】
図１８は、ステップＳ１７０３ａ、Ｓ１７０３ｂでの重複ボックスの特定例を示す説明図である。まず、（Ａ）において、対象粒子データｐｃの変形後の影響領域ＥＣおよび変形後の外接形状データＳＣおよび変形後の外接形状ＳＣに接する矩形ＳＣ２が生成される。つぎに、（Ｂ）では、探索装置１０００は、判断部１００４により、（Ａ）の状態から第１階層（ｒ＝１）のボックスｂ１〜ｂ４のうち、矩形ＳＣ２と重複するボックスの有無を判断する。この場合、ボックスｂ１、ｂ２が重複していないため、特定候補から外される。
【０１１６】
同様に、（Ｃ）では、探索装置１０００は、判断部１００４により、（Ｂ）での重複ボックスｂ３，ｂ４において、第２階層（ｒ＝２）のボックスｂ３１〜ｂ３４，ｂ４１〜ｂ４４のうち、矩形ＳＣ２と重複するボックスの有無を判断する。この場合、ボックスｂ３１，ｂ３３，ｂ４２，ｂ４４が重複していないため、特定候補から外される。
【０１１７】
同様に、（Ｄ）では、探索装置１０００は、判断部１００４により、（Ｃ）での重複ボックスｂ３２，ｂ３４，ｂ４１，ｂ４３において、第３階層（ｒ＝３）のボックスｂ３２１〜ｂ３２４，ｂ４１１〜ｂ４１４，ｂ４３１〜ｂ４３４、第２階層のボックスｂ３４（第３階層がないため）のうち、矩形ＳＣ２と重複するボックスの有無を判断する。この場合、ボックスｂ４１２，ｂ４１４，ｂ４３２，ｂ４３３，ｂ４３４が重複していないため、特定候補から外される。
【０１１８】
（Ｄ）では、第３階層が最下層であるため、この段階で残されているボックスｂ３２１〜ｂ３２４，ｂ３４，ｂ４１１，ｂ４１３，ｂ４４１が、矩形ＳＣ２との重複ボックスとして特定されることになる。したがって、探索装置１０００は、図６や図７の（Ｂ）に示したように、重複ボックスｂ３２１〜ｂ３２４，ｂ３４，ｂ４１１，ｂ４１３，ｂ４３１の各々を逆テンソルＦｃij-1によって変形させる。
【０１１９】
そして、探索装置１０００は、判断部１００４により、変形後のボックスの各々と対象粒子ｐｃの変形前の影響領域ｅｃとで再重複を判断することになる。また、探索装置１０００は、決定部１００５により、変形した再重複ボックスに存在する粒子データを近傍粒子データ候補に決定することになる。また、探索装置１０００は、判断部１００４により、変形した再重複ボックスの各々に存在する近傍粒子データ候補が、影響領域ｅｃと重複するかを判断することになる。そして、探索装置１０００は、重複した近傍粒子データ候補については、決定部１００５により、対象粒子データの近傍粒子データに決定することになる。
【０１２０】
図１９は、探索装置１０００による探索処理手順例（その２）を示すフローチャートである。ここでは、図１５に示した近傍粒子データ探索処理（ステップＳ１３０３）を「第１の近傍粒子データ探索処理」と称し、図１７に示した近傍粒子データ探索処理（ステップＳ１３０３）を「第２の近傍粒子データ探索処理」と称す。図１３の探索処理手順例（その１）では、第１の近傍粒子データ探索処理または第２の近傍粒子データ探索処理のうちいずれか一方の探索処理を用いた例について説明したが、図１９では、いずれか一方の近傍粒子探索処理を適宜選択しながら探索をおこなう。
【０１２１】
まず、探索装置１０００は、ＤＢ９００から粒子データ群を読み込み（ステップＳ１９０１）、所定計算ステップ数経過したか否かを判断する（ステップＳ１９０２）。経過していない場合（ステップＳ１９０２：Ｎｏ）、探索装置１０００は、生成部１００１により、ツリー構造体生成処理を実行する（ステップＳ１９０３）。ツリー構造体生成処理（ステップＳ１９０３）は、ツリー構造体生成処理（ステップＳ１３０２）と同一処理である。ツリー構造体生成処理（ステップＳ１９０３）では、図１２に示したようなツリー構造体を生成する。
【０１２２】
つぎに、探索装置１０００は、近傍粒子データ探索処理を実行する（ステップＳ１９０４）。近傍粒子データ探索処理（ステップＳ１９０４）は、第１または第２の近傍粒子データ探索処理のうちいずれか一方が設定されて実行されることになる。
【０１２３】
近傍粒子データ探索処理（ステップＳ１９０４）のあと、探索装置１０００は、粒子データｐｋごとに、運動量を計算する（ステップＳ１９０５）。たとえば、上記式（６）で示したように、探索装置１０００は、粒子データｐｋごとに、加速度ａｋを計算する。そして、探索装置１０００は、上記式（７）〜（９）で示したように、粒子データｐｋごとに、変形勾配テンソルＦｋijや速度ｖ、位置情報を更新する（ステップＳ１９０６）。
【０１２４】
このあと、探索装置１０００は、時間刻み幅ｄｔの分だけ、時刻を更新して（ステップＳ１９０７）、計算結果（粒子データｐｋごとの近傍粒子データ、加速度ａｋ、速度ｖｋ、位置座標Ｃｋなど）を出力する（ステップＳ１９０８）。このあと、探索装置１０００は、計算終了か否かを判断する（ステップＳ１９０９）。たとえば、探索装置１０００は、所定計算ステップ数に到達したか否かを判断する。計算終了である場合（ステップＳ１９０９：Ｙｅｓ）、一連の探索処理を終了する。
【０１２５】
一方、計算終了でない場合（ステップＳ１９０９：Ｎｏ）、後述するステップＳ１９１３、Ｓ１９１４で第１および第２の近傍粒子データ探索処理が並列実行されたか否かを判断する（ステップＳ１９１０）。今回の計算ステップにおいて並列実行していない場合（ステップＳ１９１０：Ｎｏ）、ステップＳ１９０２に戻る。
【０１２６】
一方、並列実行した場合（ステップＳ１９１０：Ｙｅｓ）、ステップＳ１９１５で近傍粒子データが選択された方の近傍粒子データ探索処理を選択し（ステップＳ１９１１）、ステップＳ１９０２に戻る。ステップＳ１９１１で選択された近傍粒子データ探索処理が、次の計算ステップにおいてステップＳ１９０４で実行されることになる。
【０１２７】
また、ステップＳ１９０２において、所定計算ステップ数経過した場合（ステップＳ１９０２：Ｙｅｓ）、探索装置１０００は、生成部１００１により、ツリー構造体生成処理を実行する（ステップＳ１９１２）。ツリー構造体生成処理（ステップＳ１９１２）は、ツリー構造体生成処理（ステップＳ１３０２）と同一処理である。ツリー構造体生成処理（ステップＳ１９１２）では、図１２に示したようなツリー構造体を生成する。
【０１２８】
つぎに、探索装置１０００は、第１および第２の近傍粒子データ探索処理を並列実行する（ステップＳ１９１３、Ｓ１９１４）。そして、探索装置１０００は、先に探索が完了した方の近傍粒子データを選択して（ステップＳ１９１５）、ステップＳ１９０５において運動量を計算することになる（ステップＳ１９０５）。この場合、まだ探索が完了していない方の近傍粒子データ探索処理については、探索装置１０００は、先に探索が完了した方の近傍粒子データ探索処理の実行が完了した時点で停止し、途中まで得られた近傍粒子データを消去することになる。
【０１２９】
このように、探索装置１０００による探索処理手順例（その２）によれば、処理が速いほうの近傍粒子データ探索処理を選択するため、近傍粒子データ探索の高速化を図ることができる。
【０１３０】
以上説明したように、本実施の形態によれば、近傍粒子探索の効率化を図ることができる。具体的には、ｔｒｅｅ法をベースとして、粒子データが変形した場合においてもその外接形状データにより近傍粒子探索の効率化を図ることができる。また、本実施の形態では、影響領域内にｔｒｅｅ法のボックスが含まれるかどうか判断する手法として、第１の近傍粒子データ探索処理（図１５）と第２の近傍粒子データ探索処理（図１７）がある。
【０１３１】
第１の近傍粒子データ探索処理（図１５）は、対象粒子データの外接形状データを、対象粒子データの変形勾配テンソルで変形して平行四辺形または平行六面体とすることで、対象粒子データと領域データ（ボックス）との重複判断をおこなう。このように、影響領域の外接形状データを変形することで、変形しない外接形状データを用いる場合に比べて影響領域の外にある粒子を近傍粒子データ候補として扱う機会を少なくすることができる。したがって、計算負荷の低減化を図ることができる。
【０１３２】
これに対し、第２の近傍粒子データ探索処理（図１７）は、領域データ（ボックス）を、対象粒子データの変形勾配テンソルの逆テンソルで変形して平行四辺形または平行六面体とすることで、対象粒子データとの重複判断をおこなう。この場合、ｔｒｅｅ法の（逆テンソルでの変形前の）ボックスが影響領域に含まれる場合のみを取り扱うことができる。
【０１３３】
第１の近傍粒子データ探索処理（図１５）は、第２の近傍粒子データ探索処理（図１７）に比べて、逆テンソルを算出せずに済む分だけ計算量が少なくなり、計算負荷の低減化を図ることができる。
【０１３４】
第２の近傍粒子データ探索処理（図１７）では、重複しているボックスのみを再重複対象とすることができる。換言すれば、変形前から重複していないボックス内の粒子データは近傍粒子データになる可能性が低いため、そのようなボックスを再重複対象から除外することで、探索処理の効率化を図ることができる。
【０１３５】
また、第１の近傍粒子データ探索処理（図１５）と第２の近傍粒子データ探索処理（図１７）とで効率がよい方の処理を適宜選択することで、探索処理の効率化を図るとともに、探索処理の高速化を図ることができる。
【０１３６】
上述した実施の形態に関し、さらに以下の付記を開示する。
【０１３７】
（付記１）対象粒子の近傍に位置する近傍粒子の探索を行なう探索プログラムにおいて、
コンピュータに、
粒子データ群の各粒子データの位置情報および変形勾配テンソルを記憶する記憶装置から読み出された前記粒子データ群の中の対象粒子データの位置情報に基づいて、前記対象粒子データの影響領域に外接する外接形状データを生成させ、
前記粒子データ群のうちの少なくとも１つの粒子データが存在する領域データと、前記生成された外接形状データとのうちいずれか一方を、変形対象に設定させ、
前記設定された変形対象を、前記対象粒子データの変形勾配テンソルに基づいて変形させ、
前記変形後の変形対象と、前記外接形状データおよび前記領域データのうちの前記変形対象として設定されなかった非変形対象とが、重複するかを判断させ、
前記変形後の変形対象と前記非変形対象とが重複すると判断された場合、前記領域データ内の粒子データを、前記対象粒子データの近傍粒子データ候補に決定させ、
前記決定された決定結果を前記記憶装置に格納させることを特徴とする探索プログラム。
【０１３８】
（付記２）前記変形対象の設定では、前記外接形状データを前記変形対象に設定し、
前記変形対象の変形では、前記設定によって前記変形対象に設定された外接形状データを、前記対象粒子データの変形勾配テンソルで変形させ、
前記変形後の変形対象と前記非変形対象とが重複するか否かの判断は、前記変形された外接形状データと、前記領域データとが、重複するかを判断することを特徴とする付記１記載の探索プログラム。
【０１３９】
（付記３）前記探索プログラムはさらに、
前記コンピュータに、前記近傍粒子データ候補が、前記変形により前記外接形状データの変形とともに変形された影響領域と重複するかを判断させ、
前記対象粒子データの近傍粒子データ候補の決定は、前記変形後の影響領域に重複すると判断された近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする付記２記載の探索プログラム。
【０１４０】
（付記４）前記変形対象の設定では、前記領域データを前記変形対象に設定し、
前記変形対象の変形では、前記設定によって前記変形対象に設定された領域データを、前記変形勾配テンソルの逆テンソルに基づいて変形させ、
前記変形後の変形対象と前記非変形対象とが重複するか否かの判断は、前記影響領域と、前記変形後の領域データとが重複するかを判断することを特徴とする付記１記載の探索プログラム。
【０１４１】
（付記５）前記探索プログラムはさらに、
前記コンピュータに、前記変形により前記領域データが変形された近傍粒子データ候補が、前記対象粒子データの影響領域と重複するかを判断させ、
前記対象粒子データの近傍粒子データ候補の決定は、前記判断された前記対象粒子データの影響領域と重複する近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記記憶装置への格納は、前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする付記４記載の探索プログラム。
【０１４２】
（付記６）前記探索プログラムはさらに、
前記コンピュータに、
対象粒子データごとに、前記対象粒子データと前記対象粒子データに関連付けられた近傍粒子データとに基づいて、前記対象粒子データの変形勾配テンソルおよび位置情報を更新させることを特徴とする付記１〜５のいずれか１項記載の探索プログラム。
【０１４３】
（付記７）前記変形対象の設定は、所定の切替タイミングに基づいて、前記変形対象を交互に設定することを特徴とする付記６記載の探索プログラム。
【０１４４】
（付記８）前記変形対象が前記外接形状データである第１の状態と、前記変形対象が前記領域データである第２の状態のうち、前記近傍粒子データが先に決定された方の状態の変形対象を次回の変形対象に設定することを特徴とする付記６または７記載の探索プログラム。
【０１４５】
（付記９）粒子データ群の各粒子データの位置情報および変形勾配テンソルを記憶する記憶装置と、
前記記憶装置から読み出された前記粒子データ群の中の対象粒子データの位置情報に基づいて、前記対象粒子データの影響領域に外接する外接形状データを生成する生成部と、
前記粒子データ群のうち少なくとも１つが存在する領域データと前記生成部によって生成された外接形状データとのうちいずれか一方を、変形対象に設定する設定部と、
前記設定された変形対象を、前記対象粒子データの変形勾配テンソルに基づいて変形させる変形部と、
前記変形後の変形対象と、前記外接形状データおよび前記領域データのうちの非変形対象とが、重複するかを判断する判断部と、
前記判断部が、前記変形後の変形対象と前記非変形対象が重複すると判断された場合、前記領域データ内の粒子データを、前記対象粒子データの近傍粒子データ候補に決定する決定部と、
前記決定された決定結果を前記記憶装置に格納する格納部と、
を備えることを特徴とする探索装置。
【０１４６】
（付記１０）前記設定部では、前記外接形状データを前記変形対象に設定し、
前記変形部では、前記設定部によって前記変形対象に設定された外接形状データを、前記対象粒子データの変形勾配テンソルで変形させ、
前記判断部は、前記変形された外接形状データと、前記領域データとが、重複するかを判断することを特徴とする付記９記載の探索装置。
【０１４７】
（付記１１）前記判断部は、前記近傍粒子データ候補が、前記変形により前記外接形状データの変形とともに変形された影響領域と重複するかを判断し、
前記決定部は、前記対象粒子データの近傍粒子データ候補の決定は、前記変形後の影響領域に重複すると判断された近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記格納部は、前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする付記１０記載の探索装置。
【０１４８】
（付記１２）前記設定部では、前記領域データを前記変形対象に設定し、
前記変形部では、前記設定部によって前記変形対象に設定された領域データを、前記変形勾配テンソルの逆テンソルに基づいて変形させ、
前記判断部は、前記影響領域と、前記変形後の領域データとが重複するかを判断することを特徴とする付記９記載の探索装置。
【０１４９】
（付記１３）前記判断部は、前記変形により前記領域データが変形された近傍粒子データ候補が、前記対象粒子データの影響領域と重複するかを判断し、
前記決定部は、前記判断された前記対象粒子データの影響領域と重複する近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記格納部は、前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする付記１２記載の探索装置。
【０１５０】
（付記１４）前記設定部は、前記変形対象が前記外接形状データである第１の状態と、前記変形対象が前記領域データである第２の状態のうち、近傍粒子データが先に決定された方の状態の変形対象を次回の変形対象に設定することを特徴とする付記９記載の探索装置。
【０１５１】
（付記１５）対象粒子の近傍に位置する近傍粒子の探索を行なう探索方法において、
コンピュータが、
粒子データ群の中の対象粒子データの位置情報に基づいて、前記対象粒子データの影響領域に外接する外接形状データを生成し、
前記粒子データ群の粒子データのうち少なくとも１つの粒子データが存在する領域データと前記生成処理によって生成された外接形状データとのうちいずれか一方を、変形対象に設定し、
前記設定された変形対象を、前記対象粒子データの変形勾配テンソルに基づいて変形させ、
前記変形後の変形対象と、前記外接形状データおよび前記領域データのうちの前記変形対象として設定されなかった非変形対象とが、重複するかを判断し、
前記変形後の変形対象と前記非変形対象とが重複すると判断された場合、前記領域データ内の粒子データを、前記対象粒子データの近傍粒子データ候補に決定し、
前記決定された決定結果を記憶装置に格納することを特徴とする探索方法。
【０１５２】
（付記１６）前記変形対象の設定では、前記外接形状データを前記変形対象に設定し、
前記変形対象の変形では、前記設定によって前記変形対象に設定された外接形状データを、前記対象粒子データの変形勾配テンソルで変形させ、
前記変形後の変形対象と前記非変形対象とが重複するか否かの判断は、前記変形された外接形状データと、前記領域データとが、重複するかを判断することを特徴とする付記１５記載の探索方法。
【０１５３】
（付記１７）前記探索方法はさらに、
前記コンピュータが、前記近傍粒子データ候補が、前記変形により前記外接形状データの変形とともに変形された影響領域と重複するかを判断し、
前記対象粒子データの近傍粒子データ候補の決定は、前記変形後の影響領域に重複すると判断された近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする付記１６記載の探索方法。
【０１５４】
（付記１８）前記変形対象の設定では、前記領域データを前記変形対象に設定し、
前記変形対象の変形では、前記設定によって前記変形対象に設定された領域データを、前記変形勾配テンソルの逆テンソルに基づいて変形させ、
前記変形後の変形対象と前記非変形対象とが重複するか否かの判断は、前記影響領域と、前記変形後の領域データとが重複するかを判断することを特徴とする付記１５記載の探索方法。
【０１５５】
（付記１９）前記探索方法はさらに、
前記コンピュータが、前記変形により前記領域データが変形された近傍粒子データ候補が、前記対象粒子データの影響領域と重複するかを判断し、
前記対象粒子データの近傍粒子データ候補の決定は、前記判断された前記対象粒子データの影響領域と重複する近傍粒子データ候補を、前記対象粒子データの近傍粒子データに決定し、
前記記憶装置への格納は、前記対象粒子データと前記近傍粒子データとを関連付けて前記記憶装置に格納することを特徴とする付記１８記載の探索方法。
【０１５６】
（付記２０）前記変形対象の設定では、前記変形対象が前記外接形状データである第１の状態と、前記変形対象が前記領域データである第２の状態のうち、近傍粒子データが先に決定された方の状態の変形対象を次回の変形対象に設定することを特徴とする付記１５記載の探索方法。
【符号の説明】
【０１５７】
１０００  探索装置
１００１  生成部
１００２  設定部
１００３  変形部
１００４  判断部
１００５  決定部
１００６  格納部
１００７  更新部
【国際調査報告】
2013042212.tif 000039
2013042212.tif 000040
2013042212.tif 000041
2013042212.tif 000042