(57)【要約】      （修正有）【課題】コンピュータ支援工学解析における近傍判定のための改善された方法およびシステムを提供する。【解決手段】一の面では、近傍エレメントのリストが、構造体あるいは工業製品を表わすグリッドモデルのベースエレメントに対して生成される。代表ノードのベースエレメントの座標はベースエレメントのコーナーノードを用いて演算される。特性長さがベースエレメントに割り当てられる。特性長さおよび代表ノードは、合わせて、グリッドモデルにおけるエレメントを２つのグループへと分割する面境界を定義する。第１グループは潜在的な近傍を含む。一方、第２グループは近傍以外を含んでいる。第１グループにおけるエレメントのみが、一般的なプロシージャを用いてさらに処理され、これにより、第１グループにおけるエレメントのそれぞれが近傍判定基準のうちの１つに応じて確かな近傍エレメントであるか否かを決定する。【選択図】図２Ａ
2010262644.tif 000002
【特許請求の範囲】
【請求項１】
ユーザが工業製品設計を改善するのを支援するためにコンピュータ支援工学解析において用いられるグリッドモデルにおけるあるエレメントの近傍エレメントのリストを決定する方法であって、
コンピュータシステムにおいて複数のエレメントによって接続された複数のノードを有するグリッドモデルを受け取るステップと、
エレメントのうちの１つをベースエレメントとして指定するステップと、
ベースエレメントに対する潜在的な近傍を含む領域を定義するステップであって、該領域が空間であってその空間のそれぞれの次元におけるそれぞれのセットの上下限によって特徴づけられた空間を備えており、個々のセットの上下限が前記ベースエレメントの代表ノードを中心とする特性長さと相関があるよう構成されているステップと、
領域内に位置するエレメントを含めることによって前記ベースエレメントの潜在的な近傍のグループを生成するステップと、
潜在的な近傍のグループから予め定義された近傍定義に適うエレメントのみを含めることによって近傍エレメントのリストを決定するステップであって、これにより、前記ベースエレメントの近傍エレメントのリストのユーザが工業製品設計を改善するのを支援するためのコンピュータ支援工学解析においてグリッドモデルと組み合わせて用いられるステップと、
を備える方法。
【請求項２】
請求項１に記載の方法であって、特性長さはユーザによって割り当てられる方法。
【請求項３】
請求項１に記載の方法であって、特性長さはグリッドモデルの特定の計量として推定される方法。
【請求項４】
請求項３に記載の方法であって、特定の計量はグリッドモデルにおけるエレメントのすべての平均サイズの所定の倍数である方法。
【請求項５】
請求項３に記載の方法であって、特定の計量はグリッドモデルのサイズの分数である方法。
【請求項６】
請求項１に記載の方法であって、ベースエレメントに対する潜在的な近傍を含む領域を定義する前記ステップは、さらに、特性長さを前記ベースエレメントに割り当てるステップであって、特性長さはユーザによって定義されるとともに潜在的な近傍の領域の制定のために用いられるステップを備えている方法。
【請求項７】
請求項１に記載の方法であって、前記ベースエレメントは複数のコーナーノードを備えており、代表ノードが複数のコーナーノードから導き出される方法。
【請求項８】
請求項７に記載の方法であって、代表ノードは空間において測定される１セットの座標によって定義される方法。
【請求項９】
請求項８に記載の方法であって、個々のセットの上下限は、特性長さを代表ノードの各座標に加減算することによって定義される方法。
【請求項１０】
請求項１に記載の方法であって、潜在的な近傍のグループを生成する前記ステップは、さらに、空間の各次元のうちの１つ毎にエレメントを複数の順序よく並べられたリストへとソートするステップと、順序よく並べられたリストのそれぞれにおいて上下限に対応する特定のエレメントを見つけるステップであってこれにより潜在的な近傍と近傍以外との間の境界を決定するステップと、を備えている方法。
【請求項１１】
請求項１に記載の方法であって、上下限に対応する特定のエレメントを見つける前記ステップは、順序よく並べられたリストのそれぞれにおいてベースエレメントと特定の一のエレメントとの間の距離を演算することなく行われる方法。
【請求項１２】
請求項１に記載の方法であって、前記予め定義された近傍定義は、ベースエレメントの代表ノードと近傍エレメントのそれぞれの代表ノードとが特性長さよりも離れていないことを備えている方法。
【請求項１３】
請求項１に記載の方法であって、代表ノードはベースエレメントの重心である方法。
【請求項１４】
ユーザが工業製品設計を改善するのを支援するためにコンピュータ支援工学解析において用いられるグリッドモデルにおけるあるエレメントの近傍エレメントのリストを決定するシステムであって、
アプリケーションモジュールに対するコンピュータ可読コードを記憶するメインメモリと、
メインメモリに連結される少なくとも１つのプロセッサと、を備えるシステムであって、前記少なくとも１つのプロセッサがメインメモリにおけるコンピュータ可読コードを実行してアプリケーションモジュールに方法に基づくオペレーションを行わせるシステムであり、その方法は、
コンピュータシステムにおいて複数のエレメントによって接続された複数のノードを有するグリッドモデルを受け取るステップと、
エレメントのうちの１つをベースエレメントとして指定するステップと、
ベースエレメントに対する潜在的な近傍を含む領域を定義するステップであって、該領域が空間であってその空間のそれぞれの次元におけるそれぞれのセットの上下限によって特徴づけられた空間を備えており、個々のセットの上下限が前記ベースエレメントの代表ノードを中心とする特性長さと相関があるよう構成されているステップと、
領域内に位置するエレメントを含めることによって前記ベースエレメントの潜在的な近傍のグループを生成するステップと、
潜在的な近傍のグループから予め定義された近傍定義に適うエレメントのみを含めることによって近傍エレメントのリストを決定するステップであって、これにより、前記ベースエレメントの近傍エレメントのリストがユーザが工業製品設計を改善するのを支援するためのコンピュータ支援工学解析においてグリッドモデルと組み合わせて用いられるステップと、
を備えているシステム。
【請求項１５】
方法に基づいて、ユーザが工業製品設計を改善するのを支援するためにコンピュータ支援工学解析において用いられるグリッドモデルにおけるあるエレメントの近傍エレメントのリストを決定するコンピュータシステムを制御する命令を有するコンピュータ記録可能な記憶媒体であって、その方法が、
コンピュータシステムにおいて複数のエレメントによって接続された複数のノードを有するグリッドモデルを受け取るステップと、
エレメントのうちの１つをベースエレメントとして指定するステップと、
ベースエレメントに対する潜在的な近傍を含む領域を定義するステップであって、該領域が空間であってその空間のそれぞれの次元におけるそれぞれのセットの上下限によって特徴づけられた空間を備えており、個々のセットの上下限が前記ベースエレメントの代表ノードを中心とする特性長さと相関があるよう構成されているステップと、
領域内に位置するエレメントを含めることによって前記ベースエレメントの潜在的な近傍のグループを生成するステップと、
潜在的な近傍のグループから予め定義された近傍定義に適うエレメントのみを含めることによって近傍エレメントのリストを決定するステップであって、これにより、前記ベースエレメントの近傍エレメントのリストがユーザが工業製品設計を改善するのを支援するためのコンピュータ支援工学解析においてグリッドモデルと組み合わせて用いられるステップと、
を備えているコンピュータ記録可能な記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、概して、コンピュータ支援工学解析（例えば有限要素解析法、トポロジー最適化など）に関し、特に、コンピュータ支援工学解析において用いられるグリッドモデル（例えば有限要素メッシュ）における近傍判定方法（neighborhood determination methods）およびシステムの改善に関する。
【背景技術】
【０００２】
今日、コンピュータ支援工学（ＣＡＥ）は、解析、シミュレーション、設計、製造などの分野において技術者を支援するために用いられている。従来の技術設計プロシージャにおいて、ＣＡＥ解析（例えば有限要素解析法（ＦＥＡ）、有限差分解析（ｆｉｎｉｔｅ  ｄｉｆｆｅｒｅｎｃｅ  ａｎａｌｙｓｉｓ）、計算流体力学（ｃｏｍｐｕｔａｔｉｏｎａｌ  ｆｌｕｉｄ  ｄｙｎａｍｉｃｓ  （ＣＦＤ））解析、ノイズ振動粗さ（ｎｏｉｓｅ−ｖｉｂｒａｔｉｏｎ−ｈａｒｓｈｎｅｓｓ  （ＮＶＨ））を低減するためモード解析等）が、応答（例えば応力、変位等）を評価するために用いられている。概して、ボデイあるいは構造体（つまり工業製品）は、コンピュータ支援工学解析でのジョイントあるいはノードにおいて相互接続されたエレメント（例えば有限要素）と呼ばれる細分の集合体によって表わされる。有限要素および相互接続されたノードは集合的にグリッドモデルと呼ばれる。
【発明の概要】
【発明が解決しようとする課題】
【０００３】
設計最適化を行なうため、ＣＡＥを具体化する自動コンピュータ実行プロシージャがまたさらに一般的となっている。概念設計において、トポロジー最適化は非常に一般的なエンジニアリング最適化方法である。トポロジー最適化は、負荷・境界条件、材料モデル、ジオメトリ（幾何学的配置）および設計コンポーネントのグリッドモデル（例えば有限要素メッシュ）間の複雑な相互作用を必要とする。これらの相互作用は、ときに、特に最適化される工業製品の非線形的な構造挙動が存在する状態において、エンジニアリングシミュレーション（つまりコンピュータ支援工学解析）を不安定にすることがある。その問題のうちの１つは、材料分配の相当大きな突然の変化がトポロジー最適化において数値的な不安定性を引き起こすおそれがあるということにある。この不安定性を低減するために、設計変数の局所的平均化が、材料分配および／または再分配における突然の変化から守るために用いられる。
【０００４】
一般に、局所的平均化は、一のエレメント（要素）の近傍内の近傍エレメントのグループの結果を平均化することによって行なわれる。大規模な複雑なグリッドモデルにおけるそれぞれのエレメントの近傍の特定は、現時点における最高技術水準のマルチプロセッサコンピュータシステムでさえ時間のかかるタスクであろう。通常、エレメントの近傍は、１ペアのエレメントのすべてのノードの点を比較して共有されるノードがあるか否かを判定することによって、あるいは２つのエレメントの距離を演算して閾値内にあるか否かを判定することによって、特定される。これらの従来技術アプローチはどちらも相当大量の演算を必要とする。例えば、１つのエレメントのそれぞれのノードを他のエレメントのすべてのノードと比較することは、ノードの数の２乗のオーダーの比較オペレーションを必要とする。一方、２つのエレメントの空間的距離の演算は、それぞれのペアの平方根の演算を必要とする。グリッドモデルが多数（例えば１００万以上）のエレメントを有する場合、近傍を見つける従来技術アプローチは、時間およびコストの点でひどく高価となる（つまり、何時間もかかることもある）。したがって、コンピュータ支援工学解析における近傍判定方法およびシステムの改善が望まれよう。
【課題を解決するための手段】
【０００５】
このセクションは、本発明のいくつかの面を要約するためのものであり、また、いくつかの好ましい態様を簡潔に取り上げるものである。このセクションにおいては簡略化あるいは省略が、要約およびタイトルと同様に、セクションの目的を分かりにくくしないようになされる場合がある。そのような簡略化あるいは省略は、本発明の範囲の制限を意図するものではない。
【０００６】
本発明は、コンピュータ支援工学解析において用いられるグリッドモデルのエレメントの近傍判定のための改善された方法およびシステムを開示する。近傍判定方法は、グリッドモデルのそれぞれのエレメントに対して同じである。より明瞭で混同しないように方法を説明するために、用語ベースエレメントを、ここでは、方法が適用される特定のエレメントと関係づけるよう用いる。本発明の一の面では、近傍エレメントのリストが、構造体あるいは工業製品を表わすグリッドモデルにおけるベースエレメントに対して生成される。まず、代表ノードの（例えば重心の）ベースエレメントの座標が、３次元座標系（例えばデカルト座標系）においてベースエレメントのコーナーノードを用いて演算される。特性長さがベースエレメントに割り当てられる。特性長さを、コンピュータ支援解析のユーザによって決定することができ、またあるいは、ベースエレメントのジオメトリ（例えばエレメントのサイズ）あるいはグリッドモデルのある計量（例えば寸法）を用いて演算することもできる。特性長さおよび重心は、合わせて、潜在的な近傍の（近傍の可能性のある）領域を定義する。潜在的な近傍の領域は、例えば、ベースエレメントの重心を中心とする立体的空間であってその側面の寸法が特性長さである立体的空間であり、あるいは、球体であってその半径が特性長さでありベースエレメントの重心を中心とする球体である。面境界は、グリッドモデルにおけるエレメントを第１および第２グループへと分割する。第１グループは面境界内に位置するエレメントを潜在的な近傍として含んでおり、第２グループは外側のエレメントを近傍以外として含んでいる。第１グループにおけるエレメントのみが、一般的なプロシージャを用いて、第１グループにおけるエレメントのそれぞれが近傍判定基準の１つに応じて、確かな近傍エレメントか否かを判定するようさらに処理される。一般的なプロシージャは、例えば、第１グループにおけるエレメントのそれぞれが少なくとも１つの共通なノードをベースエレメントと共有すること、あるいはベースエレメントの重心から閾値距離内に位置すること、である。グリッドモデルにおけるエレメントを第１および第２グループへと分割することは、すべてのエレメントの重心の座標をそれぞれの次元におけるそれぞれの上下限（例えば２次元では２つ、３次元では３つ）と比較することによって達成される。上下限は、特性長さをベースエレメントの重心座標に加減算することによって制定することができる。
【０００７】
さらに他の面では、グリッドモデルにおけるエレメントは各次元において３つの順序よく並べられたリストへソートされ、これにより、第１および第２グループの分割は、あらかじめソートされたすなわちあるいは順序よく並べられたリストを調査することと、座標が上下限に対応するエレメントを見つけることと、によって効率的に達成することができる。
【０００８】
本発明の他の目的、特徴および利点は、添付の図面を参照した以下の実施形態の詳細な説明を考察することで明らかになるであろう。
【０００９】
本発明のこれらおよび他の特徴、面および利点は、以下の説明、添付した特許請求の範囲および以下の添付図面との関連から一層よく理解されるであろう。
【図面の簡単な説明】
【００１０】
【図１】図１は、例示的なグリッドモデルであって、そのグリッドモデルに含まれているエレメントの近傍の決定のために本発明の一の実施形態を用いることができるグリッドモデルを示す図である。
【図２Ａ】図２Ａは、本発明の実施形態にかかる、グリッドモデルにおけるベースエレメントの近傍エレメントのリストを決定する例示的なプロセスを集合的に示すフローチャートである。
【図２Ｂ】図２Ｂは、本発明の実施形態にかかる、グリッドモデルにおけるベースエレメントの近傍エレメントのリストを決定する例示的なプロセスを集合的に示すフローチャートである。
【図３Ａ】図３Ａは、本発明の実施形態にかかる、エレメントと、潜在的な近傍の領域を定義するそのエレメントに関連する例示的な特性長さと、を示す２次元図である。
【図３Ｂ】図３Ｂは、本発明の他の実施形態にかかる、他のエレメントと、潜在的な近傍の領域を定義するそのエレメントに関連する例示的な特性長さと、を示す２次元図である。
【図４Ａ】図４Ａは、本発明の実施形態にかかる、例示的なベースエレメントと、その特性長さおよび近傍と、を示す２つの詳細な２次元図である。
【図４Ｂ】図４Ｂは、本発明の実施形態にかかる、例示的なベースエレメントと、その特性長さおよび近傍と、を示す２つの詳細な２次元図である。
【図５Ａ】図５Ａは、本発明の実施形態にかかる、例示的なベースエレメントと、その特性長さおよび近傍と、を示す２つの展開３次元斜視図である。
【図５Ｂ】図５Ｂは、本発明の実施形態にかかる、例示的なベースエレメントと、その特性長さおよび近傍と、を示す２つの展開３次元斜視図である。
【図６】図６は、本発明の実施形態にかかる、ベースエレメントの近傍以外から潜在的な近傍を分離するための、各上下限を有するエレメントの３つの順序よく並べられたリストを示す図である。
【図７】図７は、本発明の実施形態が構築された演算デバイスの主要なコンポーネントを示す機能図である。
【発明を実施するための形態】
【００１１】
本発明の実施形態を、図１乃至図７を参照してここに説明する。しかしながら、これらの図を参照してここで与える詳細な説明は例示の目的であって、発明がこれらの限定的な実施形態を越えて広がっていることは、当業者には容易に理解されよう。
【００１２】
例示的なグリッドモデル１００を図１に示す。グリッドモデル１００は、概して、座標系（例えばデカルト座標系１１０）において定義されている。グリッドモデル１００は複数のエレメント１０２を備える。それぞれのエレメントはその近傍エレメントとともに、近傍１０４を形成する。本発明は、このような近傍を効率的に決定する改善された方法およびシステムに対してなされたものである。このことは、非常に複雑な構造体あるいはボデイ（例えば自動車、飛行機あるいはそれらの複雑なコンポーネント）を表わす、相当に大規模なグリッドモデル（例えば１，０００，０００以上のエレメント）において重要である。
【００１３】
本発明の一の実施形態にかかる、グリッドモデルのベースエレメントの近傍エレメントのリストを決定する例示的なプロセス２００を、図２Ａ乃至図２Ｂに集合的に示す。プロセス２００は、ソフトウェアにおいて好ましくは実行され、以下の図面、特に図３Ａ乃至図６とともに理解されよう。ユーザ（つまり技術者と科学者）が工学構造あるいは製品設計を改善する（例えば、工学構造応答を数値的にシミュレートし近似する以外には工学構造応答を得ることがほとんど非現実的な場合）ことを支援するために、グリッドモデルをそれぞれのエレメントの近傍情報とともにエンジニアリングシミュレーション（例えばコンピュータ支援工学解析）において用いられる。
【００１４】
プロセス２００は、ステップ２０２においてコンピュータシステムに工業製品の定義を受け取ることによってスタートする。定義は、コンピュータ支援工学解析モデル、例えば、複数のエレメント（例えば工業製品を表わす有限要素メッシュ）を備えるグリッドモデルを含んでいる。
【００１５】
次に、ステップ２０４において、それぞれのエレメント（例えばベースエレメント）の代表ノード（例えば重心）の座標が演算される。代表ノードの座標を、そのコーナーノードから導き出すことができる。例えば、６面体のエレメント（つまりブリック（煉瓦状）エレメントすなわちソリッドエレメント）の重心の座標は、すべての８つのコーナーノードの座標の単純平均として演算される。また、ステップ２０６において、それぞれのエレメントに、ユーザ定義あるいは自動演算プロシージャのいずれかによって決定することができる特性長さが割り当てられる。自動演算プロシージャは、特性長さを、グリッドモデルの特定の計量の倍数／分数、例えばグリッドモデルにおけるエレメントの平均サイズ、グリッドモデルの寸法の合計の分数など、として推定することを備える。一の実施形態において、演算プロシージャは、平均エレメントサイズをそのジオメトリ（つまりコーナーノード）から演算し、そして、平均エレメントサイズの倍数（例えば２倍）を特性長さとして割り当てる。特性長さは、それぞれのエレメントに対する近傍以外から潜在的な近傍を分離する面境界を定義するように構成される。近傍判定方法は、グリッドモデルにおけるそれぞれのエレメントに対して同じである。
【００１６】
ステップ２０８においては、潜在的な近傍空間が制定される。潜在的な近傍空間は、一例において、図３Ａに示すベースエレメントの重心を中心とする、それぞれの側面が特性長さの２倍と等しい立体的空間である。潜在的な近傍空間を、図３Ｂに示すベースエレメントの重心を中心とする、半径が特性長さと等しい球体とすることもできる。図示の簡略化のため、図３Ａおよび図３Ｂの両方を２次元で示している。
【００１７】
次に図３Ａを参照して、２つの領域３２０〜３２２に分割されたグリッドモデル（長方形領域３００として図示し、エレメントの詳細は図示せず）を示す。グリッドモデルは、長方形３１４によって−ベースエレメント３１０の重心３１６（つまり代表ノード）を中心とする立体的空間によって定義された面境界の射影によって２つの領域３２０〜３２２に分割されている。特性長さを、次元のそれぞれの２つのペアの範囲３１２ａ〜ｂ，３１３ａ〜ｂによって表わすことができる。長方形３１４（つまり立体的空間の断面）内の領域は、潜在的な近傍空間３２２であり、一方、領域（長方形３１４の外側）は近傍以外の空間３２０である。
【００１８】
同じく、図３Ｂは、２つの領域３５０〜３５２に分割されたグリッドモデル（長方形領域３３０として図示し、エレメントの詳細は図示せず）を示す。グリッドモデルは、円３４４によって−ベースエレメント３４０の重心３４６を中心とする半径３４２の球体によって定義された面境界の射影によって２つの領域３５０〜３５２に分割されている。半径３４２は特性長さである。円３４４（つまり球体の断面）内の領域は、潜在的な近傍空間３５２であり、一方、領域（円３４４の外側）は近傍以外の空間３５０である。
【００１９】
さらなる詳細を図４Ａ乃至図４Ｂに示す。図４Ａにおいて、ベースエレメント４１０の重心４１６が特性長さ（例えば辺長の２分の１）とともに、境界４１４を定義する。潜在的な近傍エレメント４０４（点線において示される）は、ベースエレメント４１０を取り囲んでいるこれらのエレメントである。図４Ｂは、境界４４４によって決定されるより多くの潜在的な近傍４２４（点線）があること以外は図４Ａに示した例と同様である他の例を示している。
【００２０】
図示の簡略化と見易さのため、図３Ａ乃至図３Ｂおよび図４Ａ乃至図４Ｂの両方を２次元で示している。図３Ａ乃至図３Ｂおよび図４Ａ乃至図４Ｂに示した例を図５Ａ乃至図５Ｂに示す３次元に拡張できることは、当業者にはわかるであろう。ベースエレメント５１０（白色あるいはより明るい色で示す）の近傍５００の２つの展開斜視図を示す。ベースエレメント５１０は、重心５１６（代表ノード）を有し、特性長さが割り当てられ、これにより、面境界５１４（つまり代表ノードおよび特性長さによって定義される立体的空間の面）を形成する。近傍エレメント５２０（より暗い色で示す）は、ベースエレメント５１０を取り囲んでいるこれらのエレメントである。
【００２１】
また図２Ａを参照して、プロセス２００は、ベースエレメントに対する潜在的な近傍エレメントのグループを制定するステップ２１０に移行する。これは、それぞれのエレメントとベースエレメントとの間の距離を演算することなく、重心が潜在的な近傍空間の外側にあるエレメントを排除することによって行うことができる。２つのエレメントの距離の計算がコンピュータリソースの点から高価であることを付言しておく。ステップ２１０のさらなる詳細を図２Ｂに図示するとともに、関連する説明を以下に行う。
【００２２】
次に、ステップ２１２において、プロセス２００は、潜在的な近傍エレメントのグループにおけるどのエレメントが近傍定義基準に照らしてベースエレメントへの確かな近傍エレメントであるかを決定する。一例において、あるエレメントとベースエレメントとの間に少なくとも１つの共有されるノードがある場合、そのエレメントはベースエレメントの近傍エレメントである。他の例において、あるエレメントとベースエレメントの２つのエレメントの距離（例えば重心から重心の距離）が特性長さ未満である場合、そのエレメントは近傍エレメントである。最後に、ステップ２１４において、コンピュータ支援工学解析は、グリッドモデルを決定された近傍情報（つまりそれぞれのベースエレメントに対する近傍エレメントのリスト）とともに用いて、構造挙動をシミュレートすることができる。エンジニアリングシミュレーション結果（つまり構造挙動すなわち応答）を、ユーザが工学構造／製品設計の改善の判定を行うことを支援するよう用いることができる。そしてプロセス２００が終了する。
【００２３】
一の実施形態に関し、プロセス２００のステップ２１０のさらなる詳細を図２Ｂに示す。まずステップ２１０ａにおいて、グリッドモデルにおけるすべてのエレメントの順序よく並べられたリストが、座標系のそれぞれの次元においてエレメントをソートすることによって生成される。このような例示的な３つのリスト６１０ａ〜ｃが、３次元座標系（例えば図１のデカルト座標系１１０）の各次元（つまり、ｘ次元、ｙ次元およびｚ次元）に対して、生成される。３つのリスト６１０ａ〜ｃを図６に示す。リスト６１０ａ〜ｃのそれぞれは２つの欄を有する。１つがエレメントＩＤ６１１ａであり、もう１つがｘ座標、ｙ座標あるいはｚ座標６１２ａ〜ｃのそれぞれである。リスト６１０ａ〜ｃは、座標のそれぞれにおいて昇順（図示にように）あるいは降順のいずれかでソートすることができる。そして、それぞれの座標における、上限６２２ａ〜ｃおよび下限６２１ａ〜ｃが、ベースエレメントの代表ノードおよび割り当てられた特性長さからステップ２１０ｂにおいて決定される。例えば、ｘ座標の上限を、特性長さをベースエレメントの代表ノードのｘ座標のｘ座標値に加算することによって演算することができ、一方、下限を特性長さを代表ノードから減算することによって演算することができる。
【００２４】
上下限が演算され、順序よく並べられたリストが生成されると、プロセス２００は、エレメントが潜在的な近傍空間内（つまり上下限間）にあるか否かをステップ２１０ｃにおける単刀直入なサーチおよび座標の比較によって決定することができる。一の実施形態においては、二分法サーチ（ｂｉ−ｓｅｃｔｉｏｎ  ｓｅａｒｃｈ）がすべての３つの順序よく並べられたリスト６１０ａ〜ｃに対して行なわれる。特に巨大なグリッドモデルを扱う相当なコンピュータリソースを必要とする可能性があるいかなる距離計算も行う必要がない。最終のステップ２１０ｄは、すべての３次元の上下限内に位置するエレメントのみを含めることによって、潜在的な近傍のグループを生成するものである。効率的にステップ２１０ｄを行うために、二分法サーチを、それぞれのエレメントが潜在的な近傍空間内に位置するか否かを決定するために用いることができる。
【００２５】
二分法サーチは、エレメントのあらかじめソートされたあるいは順序よく並べられたリストなど順序よく並べられたサンプルに対する最も効率的なサーチ方式のうちの１つであることを付言しておく。他の手法もまた効率を向上するために用いることができる。例えば、インジケータとエレメントとの間の一対一対応を有するアレイ状インジケータが生成される。一の実施形態において、アレイ状インジケータは初期には０に設定される。その後、特定のインジケータは、対応するエレメントが３次元のうちの１つの次元に関して潜在的な領域内に位置すると決定された場合、インクリメントされる。最終的に、潜在的な近傍は、３次元の場合、３に等しいインジケータを有するエレメントである。他の実施形態においては、インジケータを、他の値に予め設定することができるその後、その値からインクリメントあるいはディクリメントして同じことを達成することができる。
【００２６】
一の側面において、本発明は、ここで説明した機能性を実行可能な１つ以上のコンピュータシステムに対してなされたものである。コンピュータシステム７００の一例を図７に示す。コンピュータシステム７００は、プロセッサ７０４などの１つ以上のプロセッサを有する。プロセッサ７０４はコンピュータシステム内部通信バス７０２に接続されている。種々のソフトウェアの実施形態を、この例示的なコンピュータシステムで説明する。この説明を読むと、いかにして、他のコンピュータシステムおよび／またはコンピューターアーキテクチャーを用いて、本発明を実行するかが、関連する技術分野に習熟しているものには明らかになるであろう。
【００２７】
コンピュータシステム７００は、また、メインメモリ７０８好ましくはランダムアクセスメモリ（ＲＡＭ）を有しており、また二次メモリ７１０を有していてもよい。二次メモリ７１０は、例えば、１つ以上のハードディスクドライブ７１２、および／またはフレキシブルディスクドライブ、磁気テープドライブ、光ディスクドライブなどに代表される１つ以上のリムーバブルストレージドライブ７１４を有することができる。リムーバブルストレージドライブ７１４は、よく知られている方法でリムーバブルストレージユニット７１８から情報を読み取り、および／またはリムーバブルストレージユニット７１８に情報を書き込む。リムーバブルストレージユニット７１８は、リムーバブルストレージドライブ７１４によって読み取り・書き込みされるフレキシブルディスク、磁気テープ、光ディスクなどを表わす。以下にわかるように、リムーバブルストレージユニット７１８は、コンピューターソフトウェアおよび／またはデータを内部に記憶しているコンピュータが使用可能な記憶媒体を有している。
【００２８】
別の実施形態において、二次メモリ７１０は、コンピュータプログラムあるいは他の命令をコンピュータシステム７００にロードすることを可能にする他の同様な手段を有することもできる。このような手段は、例えば、リムーバブルストレージユニット７２２およびインターフェース７２０を有することができる。そのようなものの例は、プログラムカートリッジおよびカートリッジインターフェース（ビデオゲーム機に見られるようなものなど）、リムーバブルメモリチップ（消去可能プログラマブルＲＯＭ（ＥＰＲＯＭ）、ユニバーサルシリアルバス（ＵＳＢ）フラッシュメモリーあるいはＰＲＯＭなど）およびそれらに対応するソケットと、ソフトウェアおよびデータをリムーバブルストレージユニット７２２からコンピュータシステム７００に転送させることを可能にする他のリムーバブルストレージユニット７２２およびインターフェース７２０と、が含まれうる。一般に、コンピュータシステム７００は、プロセススケジューリング、メモリ管理、ネットワーク管理およびＩ／Ｏサービスなどのタスクを行なうオペレーティングシステム（ＯＳ）ソフトウェアによって制御され連係される。
【００２９】
通信インターフェース７２４も、また、バス７０２に接続することができる。通信インターフェース７２４は、ソフトウェアおよびデータがコンピュータシステム７００と外部装置との間で転送することを可能にする。通信インターフェース７２４の例には、モデム、ネットワークインターフェース（イーサネット（登録商標）・カードなど）、コミュニケーションポート、ＰＣＭＣＩＡ（Ｐｅｒｓｏｎａｌ  Ｃｏｍｐｕｔｅｒ  Ｍｅｍｏｒｙ  Ｃａｒｄ  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ａｓｓｏｃｉａｔｉｏｎ）、スロットおよびカードなど、が含まれうる。
【００３０】
コンピュータ７００は、特定の通信手続（つまりプロトコル）を実行してデータを送受信する。一般的なプロトコルの１つは、インターネットにおいて一般的に用いられているＴＣＰ／ＩＰ（Ｔｒａｎｓｍｉｓｓｉｏｎ  Ｃｏｎｔｒｏｌ  Ｐｒｏｔｏｃｏｌ／Ｉｎｔｅｒｎｅｔ  Ｐｒｏｔｏｃｏｌ）である。一般的に、通信インターフェース７２４は、データファイルをデータネットワーク上で伝達される小さいパケットへ分割し、あるいは受信したパケットを元のデータファイルへと組み立てる（再構築する）、いわゆるパケットのアセンブル・リアセンブル管理を行う。さらに、通信インターフェース７２４は、正しい宛先に届くようにそれぞれのパケットのアドレス部分に対処し、あるいはコンピュータ７００が宛先となっているパケットを他に向かわせることなく確実に受信する。
【００３１】
この書類において、「コンピュータプログラム媒体」および「コンピュータで記録可能な記憶媒体」という用語は、リムーバブルストレージドライブ７１４および／またはハードディスクドライブ７１２に組み込まれたハードディスクなどの媒体を通常意味して用いられる。これらのコンピュータプログラム製品は、ソフトウェアをコンピュータシステム７００に提供する手段である。本発明は、このようなコンピュータプログラム製品に対してなされたものである。
【００３２】
コンピュータシステム７００は、また、コンピュータシステム７００にモニタ、キーボード、マウス、プリンタ、スキャナ、プロッターなどとアクセスさせる入出力（Ｉ／Ｏ）インターフェース７３０を有していてもよい。
【００３３】
コンピュータプログラム（コンピュータ制御ロジックともいう）は、メインメモリ７０８および／または二次メモリ７１０にアプリケーションモジュール７０６として記憶される。コンピュータプログラムを、また、通信インターフェース７２４を介して受け取ることもできる。このようなコンピュータプログラムが実行された時、コンピュータプログラムによって、コンピュータシステム７００がここで説明した本発明の特徴を実現することが可能になる。詳細には、コンピュータプログラムが実行された時、コンピュータプログラムによって、プロセッサ７０４がここに説明した本発明の特徴を実現することが可能になる。したがって、このようなコンピュータプログラムは、コンピュータシステム７００のコントローラを表わしている。
【００３４】
ソフトウェアを用いて発明を実行されるある実施形態において、当該ソフトウェアは、コンピュータプログラム製品に記憶され、あるいは、リムーバブルストレージドライブ７１４、ハードドライブ７１２あるいは通信インターフェース７２４を用いて、コンピュータシステム７００へとロードされる。アプリケーションモジュール７０６は、プロセッサ７０４によって実行された時、アプリケーションモジュール７０６によって、プロセッサ７０４がここに説明した本発明の機能を実現する。
【００３５】
所望のタスクを実現するため、Ｉ／Ｏインターフェース７３０を介したユーザ入力によって、あるいは、よることなしに、１つ以上のプロセッサ７０４によって実行することができる１つ以上のアプリケーションモジュール７０６を、メインメモリ７０８に、ロードすることもできる。動作においては、少なくとも１つのプロセッサ７０４がアプリケーションモジュール７０６のうち１つが実行されると、結果が演算され二次メモリ７１０（つまりハードディスクドライブ７１２）に記憶される。ＣＡＥ解析あるいは設計最適化のステータス（例えば、近傍エレメントのリストは表で表示することができ、潜在的な近傍と近傍以外とは異なる色で示すことができ、グリッドモデルはあらゆる所望の斜視図などで表示することができる等）は、テキストあるいはグラフ表示のいずれかでＩ／Ｏインターフェース７３０を介してユーザに報告される。
【００３６】
本発明を具体的な実施形態を参照して説明したが、これらの実施形態は単に例示的なものであって、本発明を限定するものではない。具体的に開示した例示的な実施形態に対する種々の変形あるいは変更が当業者よって提案されよう。例えば、ソリッドの６面体のエレメントを説明し図示したが、他のタイプの有限要素を用いることができる（例えば４面体のエレメント、２次元エレメントなど）。さらに、３つの順序よく並べられたリストを潜在的な近傍空間の定義のために示したが、代わりに２つの順序よく並べられたリストを２次元のグリッドに用いることができる。さらに、立体的空間の辺長を定義するために特性長さを図示し説明したが、他の幾何学的形状あるいはボデイの他の量、例えば球体の半径を特性長さとして用いることができる。最後に、エレメントの重心を近傍判定用のエレメントを表わすノードとして図示し説明したが、代わりにエレメントに関連する他のノード、例えばコーナーノードのうちのいずれかを用いることもできる。つまり、本発明の範囲は、ここに開示した具体的な例示的実施形態に限定されるのではなく、当業者が容易に思いつくあらゆる変形は、本願の精神および認識範囲内および添付の特許請求の範囲の範囲内に含まれる。
【符号の説明】
【００３７】
１００  グリッドモデル
１０２  エレメント
１０４  近傍
１１０  デカルト座標系
３００  長方形領域
３１０  ベースエレメント
３１２ａ，３１２ｂ  特性長さ
３１３ａ，３１３ｂ  特性長さ
３１４  長方形
３１６  重心
３２０  近傍以外の空間
３２２  潜在的な近傍空間
３３０  長方形領域
３４０  ベースエレメント
３４２  半径
３４４  円
３４６  重心
３５０  近傍以外の空間
３５２  潜在的な近傍空間
４０４  潜在的な近傍エレメント
４１０  ベースエレメント
４１４  境界
４１６  重心
４２４  潜在的な近傍
４４４  境界
５００  近傍
５１０  ベースエレメント
５１４  境界
５１６  重心
５２０  近傍エレメント
６１０ａ〜ｃ  リスト
６１１ａ〜ｃ  エレメントＩＤ
６１２ａ〜ｃ  座標
６２１ａ〜ｃ  下限
６２２ａ〜ｃ上限
７００  コンピュータシステム
７０２  バス
７０４  プロセッサ
７０６  アプリケーションモジュール
７０８  メインメモリ
７１０  二次メモリ
７１２  ハードディスクドライブ
７１４  リムーバブルストレージドライブ
７１８  リムーバブルストレージユニット
７２０  インターフェース
７２２  リムーバブルストレージユニット
７２４  通信インターフェース
７３０  Ｉ／Ｏインターフェース
【図１】
2010262644.tif 000003
【図２Ａ】
2010262644.tif 000004
【図２Ｂ】
2010262644.tif 000005
【図３Ａ】
2010262644.tif 000006
【図３Ｂ】
2010262644.tif 000007
【図４Ａ】
2010262644.tif 000008
【図４Ｂ】
2010262644.tif 000009
【図５Ａ】
2010262644.tif 000010
【図５Ｂ】
2010262644.tif 000011
【図６】
2010262644.tif 000012
【図７】
2010262644.tif 000013