(57)【特許請求の範囲】
【請求項１】
メモリとＣＰＵとを備え、該ＣＰＵが前記メモリに記憶されたプログラムを実行することで、判定手段と設定手段とを実現する有限要素モデル処理装置において、前記判定手段が、有限要素分割モデルに検索点が与えられたとき、特定の要素を最初の検索対象要素としてスタートし、現在の検索対象要素が前記検索点を内含するかを判定する判定工程と、前記判定工程において内含しないと判定された場合に、前記設定手段が、現在の検索対象要素の境界に関して、その要素の重心と前記検索点とが反対側となる境界で隣接する要素を探索し、その隣接する要素を次の検索対象要素として設定する設定工程とを備え、前記判定工程と前記設定工程とを繰り返し実行していくことにより、前記検索点を内含する要素を検索する有限要素モデル処理方法において、前記設定工程において、前記設定手段が、現在の検索対象要素に対して、その要素の重心と前記検索点とが反対側となる境界で隣接する要素が無い場合、前記要素の重心と前記検索点との位置に関係なく現在の検索対象要素に隣接する要素を次の検索対象要素として設定することを特徴とする有限要素モデル処理方法。
【請求項２】
前記設定工程における前記隣接する要素の探索では、前記設定手段が、現在の検索対象要素の各境界に対して、その要素の重心と前記検索点とが反対側となるかを判定し、反対側となると判定された場合に、その境界で隣接する要素が存在するかを判定することを特徴とする請求項１記載の有限要素モデル処理方法。
【請求項３】
前記設定工程において、前記設定手段が、次の検索対象要素を、検索対象要素として未設定の要素の中から設定することを特徴とする請求項１または２記載の有限要素モデル処理方法。
【請求項４】
前記設定工程において、前記設定手段が、現在の検索対象要素に隣接する要素の全てが既設定であった場合、現在の検索対象要素に隣接する要素以外で未設定の要素を次の検索対象要素として設定することを特徴とする請求項３記載の有限要素モデル処理方法。
【請求項５】
前記判定工程において、前記判定手段が、現在の検索対象要素が前記検索点を内含するかを判定する際に、要素の形状関数を用いた写像を使用することを特徴とする請求項１乃至４のいずれか１項に記載の有限要素モデル処理方法。
【請求項６】
前記設定工程において、前記設定手段が、前記要素の重心と前記検索点とが反対側となる境界で隣接する要素が無いことの発生回数をカウントし、そのカウント値が解析者の指定した値を超える場合、前記検索点は有限要素分割モデルの外の点であると判定することを特徴とする請求項２記載の有限要素モデル処理方法。
【請求項７】
有限要素分割モデルに検索点が与えられたとき、特定の要素を最初の検索対象要素としてスタートし、現在の検索対象要素が前記検索点を内含するかを判定する判定手段と、該判定手段により内含しないと判定された場合に現在の検索対象要素の境界に関して、その要素の重心と前記検索点とが反対側となる境界で隣接する要素を探索し、その隣接する要素を次の検索対象要素として設定する設定手段とを備え、前記判定手段による判定と前記設定手段による設定とを繰り返し実行していくことにより、前記検索点を内含する要素を検索する有限要素モデル処理装置において、前記設定手段が、現在の検索対象要素に対して、その要素の重心と前記検索点とが反対側となる境界で隣接する要素が無い場合、前記要素の重心と前記検索点との位置に関係なく現在の検索対象要素に隣接する要素を次の検索対象要素として設定することを特徴とする有限要素モデル処理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、有限要素分割モデルを処理する有限要素モデル処理方法及び装置に関する。
【０００２】
【従来の技術】
近年、偏微分方程式によって表わされる工学的問題を解析するために、有限要素解析が設計支援ツールとして広く使用されている。この有限要素解析では、物体及び空気を有限な要素に分割した有限要素分割モデルを使用し、結果として各要素位置における場（磁束密度、電界強度、電位、応力、変異、温度等）を得る。
【０００３】
有限要素解析では、これら各要素位置における結果を用いて任意の点（以下、Ｐと記述する）での場を求める等のため、点Ｐを内含する要素を検索する必要が多々発生する。点Ｐを検索する最も単純な方法は、個々の要素について順に内含しているか否かをチェックしていく方法である。しかし、このような方法では、要素数が多い場合、検索すべき点Ｐの数が多い場合に、長大な検索時間を必要とする。
【０００４】
そこで、検索時間を短縮する方法が、“Lawson,C.L.Software for C interporation,in Rice,J.(ed.)MathematicalSoftware III,Academic Press,New York,pp.161-194(1977)”に述べられている。また、“J.W.Sloan,A fast algorithm for constructingDelaunay triangulationsin the plane,Adv.Eng.Software,Vol9,No1(1987)”には、本方法（以下、Lawsonの方法と記述する）を有限要素分割処理プロセスに利用した例が示されている。
【０００５】
Lawsonの方法では、任意の条件に基づいて定めた検索を開始する要素Ｅｓ（例えば、要素番号１の要素）から点Ｐの方向に互いに隣接し合った要素（ここでは検索途上で辿る要素を検索対象要素と記述する）を辿っていくことにより点Ｐに行き着く。そして、その辿るべき方向の隣接要素を決めるものとして、２次元モデルの場合、検索対象要素の各辺に対する点Ｐとその要素の重心との位置関係を使用する。
【０００６】
次に、Lawsonの方法を用いた従来の有限要素検索装置を図７〜図１３を用いて詳しく説明する。
【０００７】
図７は、Lawsonの方法を用いた従来の有限要素検索装置であるコンピュータの構成を示すブロック図である。同図において、７０１は全体の動作を制御する中央処理装置（ＣＰＵ）で、該中央処理装置７０１には、表示装置７０２、入力装置７０３、メモリ７０４及び外部記憶装置７０５がバス７０６を介して接続されている。表示装置７０１は解析結果等を表示するものである。入力装置７０３は解析者が入力を行うものである。メモリ７０４は、検索プログラムが格納され且つ制御動作時の各種情報が格納され且つ読み出される。外部記憶装置７０５は、システムに収まらないデータを保存すると共に、システムが終了した後もデータを保存する。
【０００８】
次に、図８に示す３角形要素から構成される分割モデルを例に、従来の検索処理を行うプログラムの構成及び処理の流れを図９〜図１１を用いて説明する。
【０００９】
図８は、３角形要素から構成される分割モデルの一例を示す図、図９は検索処理プログラムの構成を示す図である。
【００１０】
図９において、９０１は処理の全体の流れを制御する制御部で、該制御部９０１に対して、隣接要素テーブル作成部９０２、辺に対する要素重心と点Ｐの位置関係判定部９０３及び隣接要素設定部９０４がコールできるようになっている。
【００１１】
ここで、隣接要素テーブル作成部９０２は、各要素に対して隣接している要素が全て分かるようにした一覧表（隣接要素テーブル）を作成する。
【００１２】
図１０に隣接要素テーブル作成部９０２により作成された隣接要素テーブルの一例を示す。同図に示す隣接要素テーブルから、要素番号１の要素には要素２，６，７が隣接していることが分かる。この隣接要素テーブルの作成方法については、従来周知の技術であるから、その説明は省略する。
【００１３】
図９における辺に対する要素重心と点Ｐの位置関係判定部９０３は、要素Ｅを構成する１つの辺Ｊが与えられたとき、辺Ｊ（の両端を延ばした直線）に対して要素Ｅの重心と点Ｐが同じ側にあるか、反対側にあるかを判定する。この判定は、単純な幾何学計算で容易に実現できる。隣接要素設定部９０４は、要素検索段階で要素Ｅを構成する１つの辺Ｊが与えられたとき、要素Ｅに辺Ｊを介して隣接する要素を、図１０に示すような隣接要素テーブルを用いて求め、新たな検索対象要素としてメモリ７０４上に設定するものである。
【００１４】
図１１は図９に示す制御部９０１が行う処理の流れを示すフローチャートである。図１１に示す処理中、ステップＳ１１０１は図９の隣接要素テーブル作成部９０２が、ステップＳ１１０５は図９の辺に対する要素重心と点Ｐの位置関係判定部９０３が、ステップＳ１１０９及びステップＳ１１１１は図９の隣接要素設定部９０４がそれぞれ担当する。
【００１５】
以下、図１１に基づいて検索過程を順を追って説明する。
【００１６】
まず、ステップＳ１１０１で図９の隣接要素テーブル作成部９０２により、図１０に示すような隣接要素テーブルを作成する。次にステップＳ１１０２で検索開始要素Ｅｓを検索対象要素Ｅとする。この検索開始要素Ｅｓは分割モデルに応じて適当に設定する。一般には、番号１の要素とする。次にステップＳ１１０３で変数ｊに１を設定する。次にステップＳ１１０４で検索対象要素Ｅの辺ｊを内含判定辺Ｊに設定する。なお、ここでは要素Ｅを構成する辺に１から始まる番号をふっている。
【００１７】
次にステップＳ１１０５で図９の辺に対する要素重心と点Ｐの位置関係判定部９０３により、要素Ｅと点Ｐの位置関係、即ち、検索対象要素Ｅの辺ｊに対して点Ｐは、要素Ｅの重心と反対側にあるか否かを判定する。そして、内含判定辺Ｊに対して点Ｐと要素Ｅの重心が同じ側にある場合、次のステップＳ１１０６で全ての辺に対する要素重心と点Ｐの位置関係の判定が完了したか否かを判別する。そして、全ての辺に対する要素重心と点Ｐの位置関係の判定が完了した場合、即ち、要素Ｅの全ての辺に対して要素Ｅの重心と点Ｐとが同じ側にある場合は、ステップＳ１１０７で要素Ｅが点Ｐを内含すると判定した後、本検索処理動作を終了する。
【００１８】
一方、前記ステップＳ１１０６において全ての辺に対する要素重心と点Ｐの位置関係の判定が完了していない場合は、ステップＳ１１０８で変数ｊにｊ＋１を設定した後、前記ステップＳ１１０４へ戻って、再び検索対象要素Ｅの辺ｊを内含判定辺Ｊに設定する。
【００１９】
また、前記ステップＳ１１０５において内含判定辺Ｊに対して点Ｐと要素Ｅの重心が反対側にある場合は、ステップＳ１１０９で図９の隣接要素設定部９０４により、辺ｊを介して要素Ｅと隣接する要素Ｅ’が有るか否かを判別する。そして、辺ｊを介して要素Ｅと隣接する要素Ｅ’が無い場合は、ステップＳ１１１０で点Ｐは分割モデル領域外であると判定した後、本検索処理動作を終了する。また、前記ステップＳ１１０９において辺ｊを介して要素Ｅと隣接する要素Ｅ’が有る場合は、ステップＳ１１１１で図９の隣接要素設定部９０４により、辺ｊを介して要素Ｅと隣接する要素Ｅ’を新たな検索対象要素Ｅに設定した後、前記ステップＳ１１０３へ戻って、再び、変数ｊに１を設定する。
【００２０】
以上の処理によって、点Ｐを内含する要素が検索、抽出される。
【００２１】
図８に本検索処理過程における検索対象要素の変遷の一例を矢印で示す。本検索方法によれば、検索は、１つの３角形から次の３角形へ、点Ｐのあるおおよその方向にほぼ直線的に進む。
【００２２】
なお、ここでは２次元の３角形からなるモデルを例にして説明したが、本検索方法は、２次元４角形要素に対しても同様に適応することができる。更に、３次元のモデルに対しても、図１１の処理フロー中の辺による内含判定、隣接要素の設定等を要素Ｅを構成する面に置き換えることで、対応可能なことは容易に分かる。
【００２３】
【発明が解決しようとする課題】
しかしながら、上述した従来のLawsonの方法によれば、モデルが凹凸形状をしている（モデル外形に凹みがある）、またはモデル中に穴がある場合及び高次の要素からなるモデルの場合について、正常に検索できない場合があった。このことを図１２及び図１３を用いて説明する。
【００２４】
図１２はモデルが凹形状をしている例を示す図である。同図において、要素Ｅｓから開始して、点Ｐを検索しようとした場合、検索は図中矢印で示した履歴を辿り、最終的に点Ｐは分割モデル領域外であると判定されてしまう。このことは、モデル中に穴があり、検索開始要素Ｅｓと点Ｐが、その穴を隔てて対岸にある場合にも発生する。
【００２５】
図１３は２次の要素からなる分割モデルの一例を示す図である。同図において、白丸は各要素の頂点となる節点、バツ印は辺の中間点である節点（中間節点）を表わす。
【００２６】
このような高次要素からなるモデルの場合、上述した方法を適用するにあたって、図中、バツ印で表示した中間節点を便宜上無視する。即ち、図中、要素Ｅ１は、点線で示した形状と見なす（以下、高次要素の場合、この点線を辺「仮の辺」と記述する）。この様にすることにより、上述した方法が適用できるが、次のような問題が発生する。即ち、図の点Ｐを内含する要素を検索するための検索対象要素ＥとしてＥ１が設定された場合、要素Ｅ１は点Ｐを内含していないにも拘らず、内含していると判定されてしまう。
【００２７】
本発明は上述した従来の技術の有するこのような問題点に鑑みてなされたものであり、その目的とするところは、どのような分割モデルに対しても、高速且つ正確に任意の点を内含する要素を検索可能な有限要素モデル処理方法及び装置を提供しようとするものである。
【００２８】
【課題を解決するための手段】
上記目的を達成するために請求項１記載の有限要素モデル処理方法は、メモリとＣＰＵとを備え、該ＣＰＵが前記メモリに記憶されたプログラムを実行することで、判定手段と設定手段とを実現する有限要素モデル処理装置において、前記判定手段が、有限要素分割モデルに検索点が与えられたとき、特定の要素を最初の検索対象要素としてスタートし、現在の検索対象要素が前記検索点を内含するかを判定する判定工程と、前記判定工程において内含しないと判定された場合に、前記設定手段が、現在の検索対象要素の境界に関して、その要素の重心と前記検索点とが反対側となる境界で隣接する要素を探索し、その隣接する要素を次の検索対象要素として設定する設定工程とを備え、前記判定工程と前記設定工程とを繰り返し実行していくことにより、前記検索点を内含する要素を検索する有限要素モデル処理方法において、前記設定工程において、前記設定手段が、現在の検索対象要素に対して、その要素の重心と前記検索点とが反対側となる境界で隣接する要素が無い場合、前記要素の重心と前記検索点との位置に関係なく現在の検索対象要素に隣接する要素を次の検索対象要素として設定することを特徴とする。
【００２９】
また、上記目的を達成するために請求項２記載の有限要素モデル処理方法は、請求項１記載の有限要素モデル処理方法において、前記設定工程における前記隣接する要素の探索では、前記設定手段が、現在の検索対象要素の各境界に対して、その要素の重心と前記検索点とが反対側となるかを判定し、反対側となると判定された場合に、その境界で隣接する要素が存在するかを判定することを特徴とする。
【００３０】
また、上記目的を達成するために請求項３記載の有限要素モデル処理方法は、請求項１または２記載の有限要素モデル処理方法において、前記設定工程において、前記設定手段が、次の検索対象要素を、検索対象要素として未設定の要素の中から設定することを特徴とする。
【００３１】
また、上記目的を達成するために請求項４記載の有限要素モデル処理方法は、請求項３記載の有限要素モデル処理方法において、前記設定工程において、前記設定手段が、現在の検索対象要素に隣接する要素の全てが既設定であった場合、現在の検索対象要素に隣接する要素以外で未設定の要素を次の検索対象要素として設定することを特徴とする。
【００３３】
また、上記目的を達成するために請求項５記載の有限要素モデル処理方法は、請求項１乃至４のいずれか１項に記載の有限要素モデル処理方法において、前記設定工程において、前記設定手段が、現在の検索対象要素が前記検索点を内含するかを判定する際に、要素の形状関数を用いた写像を使用することを特徴とする。
【００３４】
また、上記目的を達成するために請求項６記載の有限要素モデル処理方法は、請求項２記載の有限要素モデル処理方法において、前記設定工程において、前記設定手段が、前記要素の重心と前記検索点とが反対側となる境界で隣接する要素が無いことの発生回数をカウントし、そのカウント値が解析者の指定した値を超える場合、前記検索点は有限要素分割モデルの外の点であると判定することを特徴とする。
【００３５】
また、上記目的を達成するために請求項７記載の有限要素モデル処理装置は、有限要素分割モデルに検索点が与えられたとき、特定の要素を最初の検索対象要素としてスタートし、現在の検索対象要素が前記検索点を内含するかを判定する判定手段と、該判定手段により内含しないと判定された場合に現在の検索対象要素の境界に関して、その要素の重心と前記検索点とが反対側となる境界で隣接する要素を探索し、その隣接する要素を次の検索対象要素として設定する設定手段とを備え、前記判定手段による判定と前記設定手段による設定とを繰り返し実行していくことにより、前記検索点を内含する要素を検索する有限要素モデル処理装置において、前記設定手段が、現在の検索対象要素に対して、その要素の重心と前記検索点とが反対側となる境界で隣接する要素が無い場合、前記要素の重心と前記検索点との位置に関係なく現在の検索対象要素に隣接する要素を次の検索対象要素として設定することを特徴とする。
【００４２】
【発明の実施の形態】
以下、本発明の各実施の形態を図面に基づき説明する。
【００４３】
（第１の実施の形態）
まず、本発明の第１の実施の形態を図１〜図６に基づき説明する。なお、本発明に係る有限要素検索装置であるコンピュータの構成は、上述した従来例の図７と同一であるから、同図を流用して説明する。
【００４４】
本発明においては、メモリに格納するデータ及びプログラムは、以下に述べるように変更される。特に、データに関しては、各要素が既に検索対象要素として点Ｐを内含するか否かのチェックを行ったこと（既検出要素）を示す内含判定済みフラグ配列（Ｆｌｇ）が付け加わる。
【００４５】
図１は、内含判定済みフラグ配列（Ｆｌｇ）の一例を示す図であり、各要素番号に対して内含関係の判定を済ませたことを示すフラグデータ（未の場合は０、済み「既検索要素」の場合は１）領域が用意されている。
【００４６】
図２は、本実施の形態に係る有限要素検索処理プログラムの構成を示す図であり、同図中、２０１は処理の全体の流れを制御する制御部で、該制御部９０１に対して、隣接要素テーブル作成部２０２、辺に対する要素重心と点Ｐの位置関係判定部２０３、第１の隣接要素設定部２０４、第２の隣接要素設定部２０５、新規検索対象要素設定部２０６及び点Ｐの内含判定部２０７がコールできるようになっている。
【００４７】
ここで、隣接要素テーブル作成部２０２及び辺に対する要素重心と点Ｐの位置関係判定部２０３は、従来例として説明した図９における隣接要素テーブル作成部９０２及び辺に対する要素重心と点Ｐの位置関係判定部９０３と同一である。
【００４８】
第１の隣接要素設定部２０４は、要素Ｅが与えられたとき、要素Ｅに隣接する要素のうち内含判定を済ませていないもの（Ｆｌｇ＝０の要素）の１つを返すものである。本機能は、隣接要素テーブルと内含判定済みフラグ配列（Ｆｌｇ）を用いることで容易に実現できる。
【００４９】
第２の隣接要素設定部２０５は、基本的には従来の隣接要素設定部（図９の隣接要素設定部９０４）と同一であり、要素Ｅを構成する１つの辺が与えられたとき、要素Ｅに辺Ｊを介して隣接する要素を前記隣接要素テーブルを用いて求め、次の検索対象要素としてメモリ７０５（図７参照）上に設定する。但し、本実施の形態のものは、設定すべき隣接要素が既に点Ｐの内含判定を済ませている場合（Ｆｌｇ＝１の場合）、その旨のデータを返して隣接要素の設定は行わないことが、従来のものと異なる。
【００５０】
新規検索対象要素設定部２０６は、任意の条件に基づいて定めた内含判定を済ませていない要素の１つ（例えば、要素番号の最も小さいもの）を、次の検索対象要素としてメモリ７０５（図７参照）上に設定する。
【００５１】
点Ｐの内含判定部２０７は、点Ｐが要素Ｅの内部／外部のいずれにあるかを判定する。本判定は、形状関数を用いて、要素Ｅを点Ｐと共に要素Ｅの局所座標系に写像するとにより位置関係を判定する。例えば、図３（ａ）に示す２次の３角形要素は、同図（ｃ）に示す形状関数の式を用いることにより、同図（ｂ）に示す局所座標系中の直角三角形に写像される。そこで、点Ｐも同様に本局所座標系に写像することにより、内含関係を容易に判定できる。本形状関数は、有限要素法で用いる全ての要素形状に対して定義でき、従って、全ての要素形状に対して同様の方法で内含判定を行うことができる。即ち、要素を構成する辺が曲線となる高次要素の場合にも、内含関係を正確に判定できる。
【００５２】
図４は図２の制御部２０１が行う処理の流れを示すフローチャートである。図４に示す処理中、ステップＳ４０５は図２の点Ｐの内含判定部２０７が、ステップＳ４１０は図２の第１隣接要素設定部２０４が、ステップＳ４１１は図２の新規検索対象要素設定部２０６が、ステップＳ４１５〜ステップＳ４１７は図２の第２隣接要素設定部２０５がそれぞれ担当する。
【００５３】
以下、図４に基づいて検索過程を順を追って説明する。
【００５４】
まず、ステップＳ４０１で内含判定済みフラグ配列（Ｆｌｇ）の初期化を行う。本初期化では、全要素のフラグを未検索状態（Ｆｌｇ＝０）に設定する。次にステップＳ４０２で図２の隣接要素テーブル作成部２０２により、隣接要素テーブルを作成する。次にステップＳ４０３で検索開始要素Ｅｓを検索対象要素Ｅとする。この検索開始要素Ｅｓは分割モデルに応じて適当に設定する。一般には、番号１の要素とする。次にステップＳ４０４で内含判定済みフラグ配列（Ｆｌｇ）の要素Ｅの部分を既検索状態（Ｆｌｇ＝１）にする。
【００５５】
次にステップＳ４０５で図２の点Ｐの内含判定部２０７により、要素Ｅが点Ｐを内含するか否かを判定する。そして、要素Ｅが点Ｐを内含する場合は、ステップＳ４１３で要素Ｅを点Ｐの内含要素として検索を終了する。また、前記ステップＳ４０５において要素Ｅが点Ｐを内含しない場合は、ステップＳ４０６で変数ｊに１を設定する。次にステップＳ４０７で検索対象要素Ｅの辺ｊを内含判定辺Ｊに設定する。なお、ここでは要素Ｅを構成する辺に１から始まる番号をふっている。
【００５６】
次にステップＳ４０８で図２の辺に対する要素重心と点Ｐの位置関係判定部２０３により、要素Ｅと点Ｐの位置関係、即ち、検索対象要素Ｅの辺ｊに対して点Ｐは、要素Ｅの重心と反対側にあるか否かを判定する。そして、内含判定辺Ｊに対して点Ｐと要素Ｅの重心が同じ側にある場合、次のステップＳ４０９で全ての辺に対する要素重心と点Ｐの位置関係の判定が完了したか否かを判別する。そして、全ての辺に対する要素重心と点Ｐの位置関係の判定が完了した場合、即ち、要素Ｅの全ての辺に対して要素Ｅの重心と点Ｐとが同じ側にある場合は、ステップＳ４１０で図２の第１隣接要素設定部２０４により、要素Ｅに隣接する要素のうち、まだ、検索対象要素になっていないもの、即ちＦｌｇ＝０のものが有るか否かを判定する。そして、Ｆｌｇ＝０のものが有る場合は、前記ステップＳ４０４へ戻って、再び内含判定済みフラグ配列（Ｆｌｇ）の要素Ｅの部分を既検索状態（Ｆｌｇ＝１）にする。
【００５７】
一方、前記ステップＳ４０９において全ての辺に対する要素重心と点Ｐの位置関係の判定が完了していない場合は、ステップＳ４１４で変数ｊにｊ＋１を設定した後、前記ステップＳ４０７へ戻って、再び検索対象要素Ｅの辺ｊを内含判定辺Ｊに設定する。
【００５８】
また、前記ステップＳ４０８において内含判定辺Ｊに対して点Ｐと要素Ｅの重心が反対側にある場合は、ステップＳ４１５で図２の第２隣接要素設定部２０５により、辺ｊを介して要素Ｅと隣接する要素Ｅ’が有るか否かを判別する。そして、辺ｊを介して要素Ｅと隣接する要素Ｅ’が無い場合は、前記ステップＳ４１０へ進む。また、前記ステップＳ４１５において、辺ｊを介して要素Ｅと隣接する要素Ｅ’が有る場合は、ステップＳ４１６で図２の第２隣接要素設定部２０５により、Ｆｌｇ（Ｅ’）＝０であるか否かを判定する。そして、Ｆｌｇ（Ｅ’）＝０で有る場合は、ステップＳ４１７で図２の第２隣接要素設定部２０５により、辺ｊを介して要素Ｅと隣接する要素Ｅ’を新たな検索対象要素Ｅに設定した後、前記ステップＳ４０４へ戻って、再び、内含判定済みフラグ配列（Ｆｌｇ）の要素Ｅの部分を既検索状態（Ｆｌｇ＝１）にする。また、前記ステップＳ４１６においてＦｌｇ（Ｅ’）＝０でない場合は、前記ステップＳ４０９へ進んで全ての辺に対する要素重心と点Ｐの位置関係の判定が完了したか否かを判定する。
【００５９】
また、前記ステップＳ４１０においてＦｌｇ＝０のものが無い場合は、ステップＳ４１１で図２の新規検索対象要素設定部２０６により、未検索の要素（Ｆｌｇ＝０）が有るか否かを判定する。そして、まだ、内含判定を行っていない要素が存在しない場合（Ｆｌｇ＝０の要素無し）は、次のステップＳ４１２で点Ｐは分割モデル領域外であると判定した後、本検索処理動作を終了する。また、前記ステップＳ４１１において、まだ、内含判定を行っていない要素が存在する場合（Ｆｌｇ＝０の要素有り）は、前記ステップＳ４０４へ戻って、再び、内含判定済みフラグ配列（Ｆｌｇ）の要素Ｅの部分を既検索状態（Ｆｌｇ＝１）にする。
【００６０】
以上の処理によって、点Ｐを内含する要素が検索、抽出される。
【００６１】
なお、前記ステップＳ４１０及びステップＳ４１１において、２段構えで新規の検索対象要素を設定するようになっているが、その理由について説明する。
【００６２】
まず、本発明によれば、基本的には検索対象要素は、ほぼ直線的に点Ｐの方向に近づく（図４のステップＳ４１５〜ステップＳ４１７を経るループ）。そして、その例外処理として、ステップＳ４１０に▲１▼から入るケースがあり、これは点Ｐに向かうべき方向が定まらない場合（図１３のような場合）への対処である。また、ステップＳ４１０に▲２▼から入るケースというのは、直進して点Ｐには近づけない場合（回り込みを行う必要が有る場合）への対処である。
【００６３】
このようなケースに陥った場合、まずは、現在の検索対象要素近傍の要素から新たに検索を開始するのが点Ｐに近づく近道である。これが図４のステップＳ４１０に該当する。
【００６４】
ところが、これだけでは不十分である。その例を図５を用いて説明する。
【００６５】
図５は４角形要素からなるモデルの一例を示す図である。同図において、検索開始要素Ｅｓ及び検索点Ｐが図の位置にあるとき、検索対象要素は矢印のように変化し、図４のステップＳ４１０による新検索要素の設定だけでは、要素Ｅｅで隣接要素にＦｌｇ＝０のものが無くなり行き詰まってしまう。そこで、これを打開するために図４のステップＳ４１１の処理が生きてくる。即ち、この様な場合は、図２の新規検索対象要素設定部２０６によって全く異なる位置に有る要素が次の検索対象要素として設定され、検索処理が続行される。
【００６６】
図６に従来の項で説明した凹形状をした分割モデルに本発明の検索処理を使用した場合の、検索対象要素の変遷の一例を矢印で示す。図４のステップＳ４１０に▲２▼から入ることにより、検索がモデルの境界部分に到達した（直進して点Ｐには近づけない）後も検索が実行されることから、検索はモデルの凹んだ部分を回り込むように、ほぼ最短距離で点Ｐの方向へ進む。このことは、モデル中に穴のあるモデルにおいて、検索開始要素Ｅｓと検索点Ｐがその穴を隔ててお互いの対岸に設定されている場合も同様である。検索対象要素は穴の周りを回り込むように点Ｐのある方向へ進む。
【００６７】
また、本発明によれば、図４のステップＳ４１０に▲１▼から入ることにより、点Ｐに向かう方向が定まらないときも検索が続行されることから、高次要素からなるモデルの場合も何等かの形で検索は点Ｐの方向へ進む。例えば、本発明を図１３の２次要素からなるモデルに適用した場合、検索対象要素Ｅに要素Ｅ１が設定された場合にも、図４のステップＳ４０５によって点Ｐは要素Ｅ１には内含されないと判定され、ステップＳ４１０またはステップＳ４１１によって新たな検索対象要素が設定される。そして、最終的に点Ｐを内含する要素Ｅ２に行き着く。
【００６８】
以上の説明から明らかなように、本発明によれば、まず、点Ｐの方向に隣接する要素がない場合に、点Ｐの方向に関係なく現在の検索対象要素に隣接する要素が次の検索対象要素として設定される（図４のステップＳ４１０に▲２▼から入るケース）。その結果、分割モデルが凹形状もしくは穴がある形状の場合にも、検索対象要素は回り込んで点Ｐに到達するようになる。
【００６９】
しかし、これだけでは高次要素モデルにおいて検索できないケースが発生する。そこで、これに対応するため、点Ｐに向かうべき方向が定まらない（現在の検索対象要素の全ての辺「仮の辺」に対して、要素重心と点Ｐの方向が同じ側に位置することにより、点Ｐの方向に隣接する要素が定まらない）場合は、点Ｐの方向に関係なく現在の検索対象要素に隣接する要素が次の検索対象要素として設定される（図４のステップＳ４１０に▲１▼から入るケース）。その結果、高次要素からなるモデルの場合も点Ｐに到達するようになった。
【００７０】
しかし、これだけでは検索過程で同一経路を巡回し続けるという事態が発生することがあることが容易に分かる。これを回避するため、新たな検索対象要素として設定する要素は未検索の要素に限定している（図４のステップＳ４１０、ステップＳ４１１、ステップＳ４１７）。これによって、検索経路の無限巡回はなくなり、複雑な形状をした分割モデルにも対応できるようになった。
【００７１】
なお、これだけでは現在の検索対象要素に隣接する要素の全てが既検索であった場合に、検索に行き詰まってしまう。そこで、このような場合には、任意の条件に基づいて定めた未検索の要素を次の検索対象要素に設定している（図４のステップＳ４１１）。これによって検索が行き詰まった場合にも新たな展開が開け、その結果、図５に示すような更に複雑な形状のモデルに対しても、検索開始要素Ｅｓの取り方に拘らず安定して点Ｐに到達できるようになった。
【００７２】
最後に、最終的な内含判定は要素の形状関数を用いた写像を用いて行っている。これによって、高次要素からなるモデルの場合にも正確な内含要素を導けるようになった。
【００７３】
なお、以上の説明から明らかなように、本発明における検索対象要素は、従来の場合と同様に、点Ｐに対してほぼ直線的に進むことから、検索所要時間は従来とほとんど変わらない。
【００７４】
また、ここでは２次元のモデルを例にして説明したが、３次元モデルに対しても図４の処理フローにおいて、“要素Ｅの辺（高次要素の場合、仮の辺）”という言葉を“要素Ｅを構成する面”に置き換えることで対応できることは容易に分かる。なお、これらの差は、要素の境界という言葉を使うことで包括することができる。
【００７５】
なお、３次元要素の場合、仮の面とは面を構成する頂点だけからなる面（中間節点を含まない）ということになる。ところが、本面が４辺形の場合、その４頂点が同一面上にない場合が発生する。しかし、このような場合にも、例えば、面を構成する４頂点（節点）の中から任意の方法で選択した３つの頂点を面上に持つ平面を更なる仮の面として代用することで、最終的には内含要素を検索できることは容易に分かる。
【００７６】
本実施の形態に係る有限要素モデル処理装置によれば、検索途上で点Ｐの方向に要素がない、または点Ｐを内含していないにも拘らず内含していると判定され、その結果、点Ｐのある方向が分からなくなった場合にも、未検索の要素を新たな検策対象要素に設定して検索を続けるようにした。
【００７７】
また、要素Ｅの全ての辺に対して点Ｐと要素Ｅの重心が同じ側にある場合（図１１のステップＳ１１０７）及び辺Ｊを介して要素Ｅと隣接する要素がない場合（図１１のステップＳ１１１１）にも未検索の要素を起点にした検索処理が継続実行される。このとき、常に未検索の要素を新たな検索対象要素とすることから、同一の検索経路を巡回し続けるということは起こらない。
【００７８】
（第２の実施の形態）
次に本発明の第２の実施の形態を説明する。なお、本実施の形態における有限要素モデル処理装置であるコンピュータの構成は、上述した従来の図７と同一であるから、同図を流用して説明する。
【００７９】
上述した第１の実施の形態によれば、点Ｐが分割モデルの領域外にある場合に、その最終的な判定を行うためには、全要素に対して点Ｐの内含判定を行う必要があることから、非常に長大な時間を要した。
【００８０】
そこで、本実施の形態では、上述した第１の実施の形態に新たな仕組みを追加することで、点Ｐが分割モデルの領域外にある場合にも、その判定を早く下せるようにしたものである。
【００８１】
上述した第１の実施の形態において、図４のステップＳ４１０に▲２▼から入るケースというのは、検索対象要素が直線的には点Ｐに近づけない場合であることを説明した。ところが分割モデルが凸形状をしている（モデル外形に凹んだ部分がない）場合には、図４のステップＳ４１０に▲２▼から入った時点で、即座に点Ｐが分割モデルの領域外であると判定することが可能である。また、分割モデルが凹形状をしている場合でも、図４のステップＳ４１０に▲２▼から入る回数の上限が（回り込みを行う経路の要素の数から）予め分かっている場合も多い。
【００８２】
そこで、本実施の形態では、メモリ７０４上に図示しないカウンタを設け、図４のステップＳ４１０に▲２▼から入る回数をカウントする。そして、その回数が解析者の指定した回数（例えば、回り込み経路上の要素数）を超えた場合、その時点で点Ｐを分割モデルの領域外であると判定して、検索処理を終了する。
【００８３】
【発明の効果】
以上詳述したように、本発明の有限要素モデル処理方法及び装置によれば、従来問題となっていた凹形状の分割モデル、穴がある分割モデル、要素の辺が曲線からなる高次の要素を使用した分割モデル等に対しても、最初の検索対象要素の設定に拘らず検索点を内含する要素を安定して検索することができるという効果を奏する。
【００８４】
また、内含判定を要素の形状関数を使用して行う態様によれば、極めて正確な判定が可能となり、更に、解析者がモデル形状に応じてパラメータ（図４の２を通過する上限）を設定する態様によれば、検索点が分割モデルの領域外にある場合の判定も迅速に行えるという効果を奏する。
【図面の簡単な説明】
【図１】本発明の第１の実施の形態に係る有限要素モデル処理装置における内含判定済みフラグ配列の一例を示す図である。
【図２】本発明の第１の実施の形態に係る有限要素モデル処理装置におけるプログラムの構成を示す図である。
【図３】本発明の第１の実施の形態に係る有限要素モデル処理装置における局所座標系への写像を説明する図である。
【図４】本発明の第１の実施の形態に係る有限要素モデル処理装置における処理フローを示すフローチャートである。
【図５】本発明の第１の実施の形態に係る有限要素モデル処理装置における検索対象要素の履歴を説明する図である。
【図６】本発明の第１の実施の形態に係る有限要素モデル処理装置における検索対象要素の履歴を説明する図である。
【図７】従来の有限要素モデル処理装置であるコンピュータの構成を示すブロック図である。
【図８】従来の有限要素モデル処理装置における検索対象要素の履歴を説明する図である。
【図９】従来の有限要素モデル処理装置におけるプログラムの構成を示す図である。
【図１０】従来の有限要素モデル処理装置における隣接要素テーブルを説明する図である。
【図１１】従来の有限要素モデル処理装置における処理フローを示すフローチャートである。
【図１２】従来の有限要素モデル処理装置における検索対象要素の履歴を説明する図である。
【図１３】従来の有限要素モデル処理装置における高次要素モデルの一例を示す図である。
【符号の説明】
２０１    制御部
２０２    隣接要素テーブル作成部
２０３    辺に対する要素重心と点Ｐの位置関係判定部
２０４    第１隣接要素設定部
２０５    第２隣接要素設定部
２０６    新規検索対象要素設定部
２０７    点Ｐの内含判定部
７０１    ＣＰＵ（中央処理装置）
７０２    表示装置
７０３    入力装置
７０４    メモリ
７０５    外部記憶装置
７０６    バス
９０１    制御部
９０２    隣接要素テーブル作成部
９０３    辺に対する要素重心と点Ｐの位置関係判定部
９０４    隣接要素設定部
【図１】
0003912854.tif 000002
【図２】
0003912854.tif 000003
【図３】
0003912854.tif 000004
【図４】
0003912854.tif 000005
【図５】
0003912854.tif 000006
【図６】
0003912854.tif 000007
【図７】
0003912854.tif 000008
【図８】
0003912854.tif 000009
【図９】
0003912854.tif 000010
【図１０】
0003912854.tif 000011
【図１１】
0003912854.tif 000012
【図１２】
0003912854.tif 000013
【図１３】
0003912854.tif 000014