(57)【特許請求の範囲】
【請求項１】
メモリを有する計算機により有限要素分割モデルから辺，面，要素を抽出する方法であって、
各要素と該要素を構成する節点とが対応して前記メモリ上の要素テーブルに記憶されている場合に、１つの辺，面または要素を１つのセグメントと見なして、有限要素分割モデルから前記セグメントを抽出する際に、
前記セグメントに対して前記セグメントを構成する節点の組み合わせを特徴付ける指標値をつけ、
同じ指標値を持つセグメントの情報が連続に並んだセグメントリストと、前記指標値と前記セグメントリスト上の位置とを関連づける指標テーブルとを前記メモリ上に作成し、
前記メモリ上の前記セグメントリストと前記指標テーブルとに基づいて、同じ指標値を持つセグメントを抽出して、抽出されたセグメントを構成する節点情報を得るようにしたことを特徴とする有限要素分割モデルから辺，面，要素を抽出する方法。
【請求項２】
前記セグメントリストに記憶される情報は、各セグメントを有する要素を特定する第１識別子と、該セグメントが前記要素の何番目のセグメントであるかを示す第２識別子とで表現されることを特徴とする請求項１記載の有限要素分割モデルから辺，面，要素を抽出する方法。
【請求項３】
前記セグメントリストに記憶されるセグメントは、前記指標値の大きい順または小さい順に並ぶことを特徴とする請求項１記載の有限要素分割モデルから辺，面，要素を抽出する方法。
【請求項４】
前記第１識別子に１つの要素を構成するセグメントの数以上の所定の整数値を乗じ、これに前記第２識別子を加えることにより、前記第１及び第２識別子を１つの整数値として記憶することを特徴とする請求項２記載の有限要素分割モデルから辺，面，要素を抽出する方法。
【請求項５】
前記指標テーブルの各指標値の情報は、該指標値に該当するセグメントの個数と該セグメントが記憶されるセグメントリストの先頭を指すポインタとで表現されることを特徴とする請求項１記載の有限要素分割モデルから辺，面，要素を抽出する方法。
【請求項６】
前記ポインタに１０以上の整数値を乗じ、これに前記セグメントの個数を加えることにより、前記個数及びポインタを１つの整数値として記憶することを特徴とする請求項５記載の有限要素分割モデルから辺，面，要素を抽出する方法。
【請求項７】
前記セグメントリストと前記指標テーブルとは、各セグメントの指標値に基づいて各指標値のセグメント個数を求め、求めた個数を指標値の小さい順または大きい順に加算していくことにより前記ポインタを求め、前記ポインタをもとに各セグメントの情報を前記セグメントリストに登録していくという手順で作成されることを特徴とする請求項５記載の有限要素分割モデルから辺，面，要素を抽出する方法。
【請求項８】
更に、抽出したセグメントの内、同一の節点からなるセグメントから構成される複数の要素を隣接要素として抽出することを特徴とする請求項１記載の有限要素分割モデルから辺，面，要素を抽出する方法。
【請求項９】
更に、前記同一の節点からなるセグメントをセグメントリストから除去することにより、セグメントリストには重複のないセグメントだけが残るようにすることを特徴とする請求項１記載の有限要素分割モデルから辺，面，要素を抽出する方法。
【請求項１０】
前記セグメントが有限要素分割モデルを構成する面であって、前記セグメントリストには複数の要素に共有されない面であるフリーフェイスが残るようにすることを特徴とする請求項９記載の有限要素分割モデルから辺，面，要素を抽出する方法。
【請求項１１】
前記セグメントが有限要素分割モデルを構成する辺であって、前記セグメントリストには複数の要素を構成しないフリーエッジが残るようにすることを特徴とする請求項９記載の有限要素分割モデルから辺，面，要素を抽出する方法。
【請求項１２】
メモリを有する計算機により有限要素分割モデル中の１点Ｐeを内含する要素を抽出する方法であって、
ある要素Ｅ0に内含されている既知の点Ｐ0を始点として、２点ＰeとＰ0を結ぶ線分と交差する要素Ｅ0の面Ｆ0を求め、
要素Ｅ0と面Ｆ0を境界にして隣接する要素Ｅ1を求め、
２点ＰeとＰ0を結ぶ線分と交差する要素Ｅ1のＦ0以外の面Ｆ1 を求め、
該面Ｆ1 で要素Ｅ1と隣接する要素Ｅ2を求めるという処理を繰り返し、
前記隣接する要素の抽出では、
各要素と該要素を構成する節点とが対応して前記メモリ上の要素テーブルに記憶されている場合に、１つの辺，面または要素を１つのセグメントと見なして、前記セグメントに対して前記セグメントを構成する節点の組み合わせを特徴付ける指標値をつけ、
同じ指標値を持つセグメントの情報が連続に並んだセグメントリストと、前記指標値と前記セグメントリスト上の位置とを関連づける指標テーブルとを前記メモリ上に作成し、
前記メモリ上の前記セグメントリストと前記指標テーブルとに基づいて、同じ指標値を持つセグメントを抽出して、抽出されたセグメントを構成する節点情報を得て、
抽出したセグメントの内、同一の節点からなるセグメントから構成される複数の要素を隣接要素とし、
隣接する要素を辿っていくことにより、点Ｐeを内含する要素を抽出することを特徴とする有限要素分割モデルから要素を抽出する方法。
【請求項１３】
メモリを有する計算機により有限要素分割モデルから辺を抽出する方法であって、
各要素と該要素を構成する節点とが対応して前記メモリ上の要素テーブルに記憶されている場合に、１つの辺を１つのセグメントと見なして、前記セグメントに対して前記セグメントを構成する節点の組み合わせを特徴付ける指標値をつけ、
同じ指標値を持つセグメントの情報が連続に並んだセグメントリストと、前記指標値と前記セグメントリスト上の位置とを関連づける指標テーブルとを前記メモリ上に作成し、
前記メモリ上の前記セグメントリストと前記指標テーブルとに基づいて、同じ指標値を持つセグメントを抽出して、抽出されたセグメントを構成する節点情報を得て、
同一の節点からなるセグメントを前記セグメントリストから除去し、前記セグメントリストに残った面を複数の要素に共有されない面であるフリーフェイスとすることにより、３次元有限要素モデルからフリーフェイスを抽出し、
該フリーフェイスを膜状要素の２次元要素とみなして、隣接する２次元要素を抽出し、
隣接する２次元要素のなす角度θを求め、
角度θの値が、許容値をδとすると、０≦θ＜（π−δ）、または（π＋δ）＜θ＜２πであるとき、前記２つの２次元要素の境界線を輪郭線として抽出することを特徴とする有限要素分割モデルから辺を抽出する方法。
【請求項１４】
更に、抽出したフリーフェイスに膜状要素の２次元要素からなる３次元形状の分割モデルを加えて、隣接する２次元要素を抽出し、
角度θの値が、許容値をδとすると、δ≦θ＜（π−δ）、または（π＋δ）＜θ＜２π−δであるとき、前記２つの２次元要素の境界線を輪郭線として抽出することを特徴とする請求項１３記載の有限要素分割モデルから辺を抽出する方法。
【請求項１５】
前記隣接する２次元要素の抽出では、
各要素と該要素を構成する節点とが対応して記憶されている場合に、１つの面を１つのセグメントと見なして、前記セグメントに対して前記セグメントを構成する節点の組み合わせを特徴付ける指標値をつけ、
同じ指標値を持つセグメントの情報が連続に並んだセグメントリストと、前記指標値と前記セグメントリスト上の位置とを関連づける指標テーブルとを作成し、
前記セグメントリストと前記指標テーブルとに基づいて、同じ指標値を持つセグメントを抽出して、抽出されたセグメントを構成する節点情報を得て、
抽出したセグメントの内、同一の節点からなるセグメントから構成される複数の要素を隣接面とすることを特徴とする請求項１３または１４記載の有限要素分割モデルから辺を抽出する方法。
【請求項１６】
有限要素分割モデルから辺，面，要素を抽出する装置であって、
各要素と該要素を構成する節点とを対応して記憶する手段と、
１つの辺，面または要素を１つのセグメントと見なして、前記セグメントに対して前記セグメントを構成する節点の組み合わせを特徴付ける指標値をつける手段と、
同じ指標値を持つセグメントの情報が連続に並んだセグメントリストと、前記指標値と前記セグメントリスト上の位置とを関連づける指標テーブルとを作成する手段と、
前記セグメントリストと前記指標テーブルとに基づいて、同じ指標値を持つセグメントを抽出して、前記各要素と該要素を構成する節点との対応に基づいて、抽出されたセグメントを構成する節点情報を得る手段とを備えることを特徴とする有限要素分割モデルから辺，面，要素を抽出する装置。
【発明の詳細な説明】
【０００１】
【産業上の利用分野】
本発明は、有限要素解析，境界要素解析等に使用する有限要素分割モデルから特定の辺，面または有限要素（ここではこれらを総称し、セグメントと呼ぶ）を抽出する際に有用なものであり、有限要素分割モデルの輪郭線，表面，重複要素の抽出、モデル中で隣接している要素の抽出、モデル中の任意点に対してそれを内含する要素の抽出等に利用できる有限要素分割モデルから辺，面，要素を抽出する方法及びその装置に関するものである。
【０００２】
【従来の技術】
近年計算機の急速な発達と共に、有限差分法，有限要素法，境界要素法等の数値解析が頻繁に行われるようになった。これらの数値解析法では、一般に解析モデルを多数の有限要素に分割した有限要素分割モデルが使用される（ここでは、有限差分法，有限要素法，境界要素法等に使用する分割モデルをまとめて有限要素分割モデルと呼ぶ）。最近では計算機性能の向上により、３次元要素分割モデルが一般的に使用されている。
【０００３】
本３次元有限要素分割モデルの外形を表示する際に、モデルの表面を抽出することが多々ある。これはすべての要素を表示すると時間がかかることによるものであり、３次元モデルをソリッドとして表示するかわりに、表面だけを隠面処理して表示することにより時間短縮をはかろうとするものである。一般に有限要素モデルの表面は、複数の要素に共有されない面（フリーフェイスと呼ぶ）と同一であり、従って表面の抽出は本フリーフェイスの抽出によってなされる。
【０００４】
また、表面の表示と同様に、モデルの輪郭線を表示することも多い。ここで輪郭線とはモデル表面の稜線であり、細かくは要素の辺（要素を構成する面の境界線）から構成されるものである。これは表示を表面だけを用いて行うよりも更に簡略化したものであり、ｎ個の要素からなる３次元モデルの場合、単純に考えればその表面の数はｎの平方根、輪郭線の数はｎの３乗根のオーダーとなる。一般に輪郭線は、複数の要素に共有されない辺（フリーエッジ）によって代用される。
【０００５】
これらの簡略化した表示の特徴は短時間に表示を行えることであり、視点位置を決定するための試行錯誤の段階における表示等において有効である。また、時系列の解析結果のアニメーション表示においては、短時間に何枚もの図を表示する必要があるが、これを表面、輪郭線を用いることで短時間に行えるようにしたという例もある（特開平４−３４６１７８号）。
【０００６】
また、本輪郭線は、要素分割モデルに含まれる要素の不整合、例えば、要素の抜け（分割モデルが要素で完全に満たされていない）、浮き節点（要素の辺上に節点がある）、節点の重複（同一点に節点が２つ以上ある）等の発見にも使用される。これは輪郭線を表示して、モデルの内部に存在する輪郭線を調べることになってなされる。本来、輪郭線は分割モデルの表面だけに表示されるものであるが、これらの不整合により輪郭線がモデルの内部に生じるからである。
【０００７】
図２０にフリーフェイス，フリーエッジを抽出して表示する計算機システムのブロック図を示す。図中、符号１６１は表示部であり、１６２は中央処理装置（ＣＰＵ）、１６３はメモリ、１６４はデータの入力部である。通常１６４からデータを入力し、１６２，１６３を用いて処理を行い、結果を１６１に表示する。なお、１６３−１はセグメントリスト，１６３−２は指標テーブルであり、１６３−３は指標値カウンタである。なお、１６３−４は要素テーブルであるが、これは後述する本発明の実施例のためのものであり、従来の技術に属するものではない。
【０００８】
上述のように、フリーフェイスは要素の面、フリーエッジは要素の辺からなるものであり、これらの面，辺は共に要素を構成する部品と考えることができる。そこで、ここではこれらの部品をまとめてセグメントと呼ぶことにする。
フリーフェイス，フリーエッジ等のセグメントは、複数の要素に共有されているセグメントを除去するという方法によって抽出することができる。本共有セグメントを高速に除去する方法としては、様々なアルゴリズムが考案されており、以下のようなものがある。
【０００９】
まず第１の方法は、分割モデルをいくつかの領域ごとに分割・グループ化するものである。すなわち、モデルを包含する１つの直方体領域を想定し、その領域をいくつかの部分領域に分ける。そして、各部分領域ごとにその内部及び境界上の要素をグループ化する。セグメントが共有されているかどうかの判定を行う際には、同じ領域内（同じグループ）の要素のセグメントのみを対象とする。本方法は、要素が領域内に均一に分散している場合には効果があるが、一部分に集中しているような場合には効果が小さいため、一般的にはあまり用いられない。
【００１０】
第２の方法は、１回のチェックに要する時間を減らす工夫である。本方法は、“中田他：３次元分割図作成アルゴリズムの改良、日本シミュレーション学会第９回シミュレーション・テクノロジー・コンファレンス，６１頁−６４頁（１９９０）”に、高速にフリーフェイスを抽出する方法として述べられているものであり、１回のチェックに要する時間を短縮したものである。すなわち、セグメントを構成する節点番号の最大値をそのセグメントの指標とし、共有されているかどうかの判定の際に、その指標が一致しない場合には即座に同一ではないと判定する。しかし、本方法もチェック回数を減らすということに関しては対処がなされておらず、あまり用いられていない。
【００１１】
第３の方法は、各セグメントに対してセグメントを構成する節点の和を指標とし、チェックを行う際には同一の指標を持つセグメントだけをチェックするものである。本方法のアルゴリズムは、特開平４−３４６１７８号にフリーフェイス，フリーエッジを抽出する方法として記載されており、容易にプログラミングできること、効果が分割状態に依存しないことから、広く使用されている。
【００１２】
図２１に本方法の流れ図を示す。以下、図２１に従って複数の要素に共有されないセグメントを抽出する過程を説明する。
複数の要素に共有されないセグメントの抽出に先だって、まずセグメントリストと指標テーブルとを作成する（ステップＢ７０１，Ｂ７０２）。セグメントリストと指標テーブルとを次に説明する。
【００１３】
セグメントリストはすべてのセグメントを登録したものであり、図２２の（ａ）に示すように、リスト番号とセグメント節点列との２つの項目からなる。ここで、リスト番号は１から始まる連続な整数値であり、本リストの行番号を表す番地である。セグメント節点列は各セグメントを構成する節点の番号を並べたものである。従って、図２２の（ａ）のセグメントリストではセグメントを各要素ごとに独立に登録する。従って、本リストの行数は次式（１）となる。
【００１４】
0003624015.tif 000002
ここで、Ｓｉはｉ番目の要素を構成するセグメントの数、ｅｌｅｍは要素数である。
【００１５】
指標テーブルは、図２２の（ｂ）に示した指標値とリスト番号列との２つからなる。指標値の項はセグメントの指標値に対応するもので、１から始まる連続な整数値であり、本テーブルの行番号を表す番地である。リスト番号列は、セグメントリストのリスト番号を示すものである。リスト番号列は、同じ指標値を持つセグメントの数だけ用意しておく必要がある。セグメントの指標値がわかれば、本テーブルを用いてその指標値を持つセグメントがセグメントリストのどこに（何番地）登録されているかを知ることができる。本テーブルの行は、指標値がとる可能な値の数だけ用意しておかなくてはならない。セグメントを構成する節点番号の和の最大は、次式（２）である。
【００１６】
0003624015.tif 000003
ここで、Ｎはモデルの節点数、ｍは１つのセグメントを構成する節点の数である。
【００１７】
セグメントの抽出にあたって、まず、図２１のステップＢ７０１でセグメントリストを作成する。これは各要素のセグメントをセグメントリストに順に登録していくことによって行う。次に、ステップＢ７０２で、ステップＢ７０１で作成したセグメントリストの個々のセグメントの指標値を求め、指標テーブルの該当する指標値の行にセグメントリストにおけるリスト番号を登録する。以上で、セグメントリストと指標テーブルとの作成を完了する。
【００１８】
複数の要素に共有されていないセグメントの抽出は、ここで作成した指標テーブルのリスト番号列から同じ節点からなるセグメントを除去することによって行われる。ステップＢ７０３〜ステップＢ７０６は同じ節点からなるセグメントの除去を行う過程である。
まず、ステップＢ７０３にて除去対象とする指標値（ｋ）を設定する。そして指標テーブルのｋ行目に登録されているセグメントの数を調べ、１つ以下ならばそのセグメントは複数の要素に共有されていないと判定し、ステップＳＢ７０６へ行く。同じ指標値を持つセグメント数が２つ以上存在したならば、ステップＢ７０５でｋ行目のセグメントの中で同一のもの（同じ節点の組み合わせからなるセグメント）を指標テーブルから除去する。以上述べたように各セグメントを構成する節点はリスト番号列に対応したセグメントリストのリスト番号を参照することによって得ることができ、ステップＢ７０５の処理はここで得た節点番号を比較することによって行う。
【００１９】
ステップＳ７０６では、本操作をすべての指標値について行ったことを確認する。全指標値のチェックが完了していなければ、ステップＢ７０３に戻って次の指標値のチェックに移る。全指標値のチェックが完了していれば、複数の要素に共有されているセグメントの除去処理を完了する。その時に指標テーブル中に残っているセグメントが複数の要素に共有されていないセグメントである。
【００２０】
以上の操作を要素分割モデルからフリーフェイスを抽出する場合を例にあげて、具体的に説明する。
図２３は２つの３次元要素からなる分割モデルである。図中、黒丸は節点を示し、近傍の番号は節点番号を示す（以後同様）。要素Ｅ１は節点１−２−３−４、要素Ｅ２は節点３−１−４−５からなる４面体要素である。要素Ｅ１は節点１−２−３，１−４−２，２−４−３，３−４−１、要素Ｅ２は節点３−１−４，３−５−１，１−５−４，４−５−３のそれぞれ４つの面からなる。
【００２１】
本分割モデルからフリーフェイスを抽出する過程を、図２１の流れに沿って説明する。
（１）ステップＢ７０１では、まず、要素Ｅ１の面の構成節点を順に図２２の（ａ）のリストに登録する。本操作を要素Ｅ２の面についても行うことにより、図２４の（ａ）のセグメントリスト（面リスト）を得る。
【００２２】
（２）次に、ステップＢ７０２では、前項で得た面リストの各面の指標値（面を構成する節点の番号の和）をそれぞれ計算し、指標テーブルのその指標値の行に面リストのリスト番号をそれぞれ登録する。すべての面を登録することにより図２４の（ｂ）を得る。
（３）ステップＢ７０３，Ｂ７０４，Ｂ７０５では、指標テーブルから、重複した（同じ節点番号からなる）面を示すリスト番号を除去する。これは同じ指標値をもつ面（指標テーブルの同じ行）の中で同じ節点の組み合わせからなるものを除去することによって行う。本例では指標値８，９以外については、すべて登録されている面が１つ以下であることから何も行わない。指標値８，９はそれぞれ２つの面が登録されていることから、２つの面の節点番号を調べ（それぞれリスト番号４，５および３，６を参照する）、２つの面が同一であるかどうかをチェックする。その結果、指標値８の２つの面が共に節点１，３，４で構成されていることから２つの面は同一であると判定し、リスト番号４，５を指標テーブルから除去する。
【００２３】
以上の処理の結果、指標テーブルに残った面（リスト番号１，２，３，６，７，８の面）がフリーフェイスである。
要素分割モデルからフリーエッジを抽出するには、以上のフリーフェイス抽出過程における面を辺に単純に置き換えるだけでよい。次に、図２３の分割モデルからフリーエッジを抽出する過程を説明する。
【００２４】
（１）図２１のステップＢ７０１では、まず、要素Ｅ１の辺の構成節点を順に図２２の（ａ）のリストに登録する。本操作を要素Ｅ２の辺についても行うことにより、図２５の（ａ）のセグメントリスト（辺リスト）を得る。
（２）次に、ステップＢ７０２では、本リストの各辺の指標値（辺を構成する節点の番号の和）をそれぞれ計算し、指標テーブルの対応する行に辺リストのリスト番号をそれぞれ登録する。すべての辺を登録することにより、図２５の（ｂ）を得る。
【００２５】
（３）ステップＢ７０３，Ｂ７０４，Ｂ７０５では、本指標テーブルから、同じ辺を示すリスト番号を除去する。本例では指標値３，８，９については登録されている辺が１つ以下であることから何も行わない。指標値４，５，６，７はそれぞれ２つ以上の辺が登録されていることから、それぞれの指標値内で辺の節点番号を調べ、重複した辺があるかどうかをチェックする。その結果、指標値４，７の２つの辺および指標値５の２つの辺（リスト番号６，８）が同一であると判定され、これらのリスト番号を指標テーブルから除去する。
【００２６】
以上の処理の結果指標テーブルに残った辺（リスト番号１，２，４，１０，１２，１１の辺）がフリーエッジである。
図２６はここで抽出されたフリーエッジを描画したものである。なお、図２６中の破線は図２３で破線で示されていたものをそのまま表示したものである。
また、要素分割モデル中に存在する点について、点がどの要素の内部に位置しているかを知る必要がしばしばある。これは、その点における場を計算する場合等に生じるものであり、点を含む要素を抽出することにより、その要素の解析結果から容易にその点の場を計算することができる。
【００２７】
従来、このような点を含む要素の抽出は、全ての要素を対象にして内含するかどうかをチェックすることにより行っていた。その結果、最悪の場合には、要素数だけのチェックを必要としていた。ｎ個の要素からなる分割モデルの場合、本チェック回数の平均はｎ／２である。
【００２８】
【発明が解決しようとする課題】
しかしながら、従来の方法で用いられていたセグメントリストと指標テーブルとは、データの持ち方に無駄が多くメモリを無駄に消費してしまうという欠点があった。以下、この欠点について説明する。
まず、セグメントリストでは各セグメントに対してセグメントを構成する節点の数だけメモリを必要とした。例えば図２４の（ａ）の面リストの場合、１つのセグメントに対して３つの整数値（節点番号）を登録する必要がある。従って、セグメントを構成する節点の数が多い場合には大量のメモリが必要となっていた。また、計算機の都合上、一般に各セグメントごとに用意しておくメモリは同じである必要がある。従って、セグメントごとに節点の数が異なる場合には、その最大の数にあわせてメモリを用意しておく必要があった。その結果、最大の節点数よりも少ない節点で構成されるセグメントに対しては、メモリが無駄になっていた。
【００２９】
一方、指標テーブルでは、各指標値に対応して登録されるセグメントの数が予めわからないため、全指標値に対して常に大きめのメモリを用意しておく必要があった。例えば図２４の（ｂ）の例では１つの指標値に５つのリスト番号まで登録できるように準備していたが、実際には最大でも２つ（指標値８，９）しか用いられていない。また、同図からわかるように、各指標値に登録されるセグメントの数は異なる。それに対して、セグメントの場合と同様に、全指標値に対して用意しておくメモリは同じである必要がある。従って、対応するセグメントが少ない指標値についてはメモリが無駄になる。
【００３０】
このように従来の方法ではメモリを無駄に消費した。その結果、大規模なモデル（要素数の多いモデル）の場合には膨大なメモリを必要とし、少量のメモリしか搭載されていない計算機では処理できなかった。
次に、例えば、６面体要素からなる１００万要素、１００万節点の分割モデルについて、フリーフェイスを抽出する際に、従来のセグメントリストと指標テーブルとが使用するメモリを計算し、このことを具体的に説明する。
【００３１】
まず、面リストが必要とするメモリを計算する。各要素を構成する面は４辺形であるため、セグメント情報は１セグメント当たり、４整数分（１整数当たり４バイトとすると１６バイト必要、以下同様）のメモリを必要とする。リストの行数は、１要素が６つの面からなることから、式（１）を用いて６００万行である。従って、セグメントリストに要するメモリは９６Ｍ（１６×６００万）バイトである。
【００３２】
次に、指標テーブルが必要とするメモリを計算する。発明者の経験から、一般に１つの分割モデル中で同じ指標値を持つセグメントの個数は最大８〜１０個であるとわかっている。そこで、本テーブルで、同じ指標値を持つセグメント（面）を１０個まで登録できるようにすると、１指標値当たりの使用メモリは４０バイト（４バイト×１０個）となる。テーブルの行数は、式（２）から約４００万（正確には（４００万−３））行である。従って、指標テーブルに要するメモリは約１６０Ｍ（４０×４００万）バイトである。
【００３３】
この結果、本分割モデルに要するメモリは合計２５６Ｍバイト（９６Ｍ＋１６０Ｍ）となる。このメモリ容量は現在の計算機をもってしても大容量であり、一般的な計算機では処理が不可能である。
また、従来の指標テーブルでは同じ指標値をもつセグメントの数が制限範囲を越えた場合には対応できなかった。例えば、図２４の（ｂ）の例では同じ指標値を持つセグメントが６つ以上になると対応できなかった。このことは、上で同じ指標値を持つセグメントの個数は最大８〜１０個であるといったことと矛盾するが、上で説明したのはあくまでも一般的な話であり、１０以上になることもありえることに基づく。
【００３４】
また、従来の輪郭線をフリーエッジで代用して表示する方法には、本来輪郭線として表示されるべきなのに表示されない場合があるという欠点があった。例えば図２６に示した輪郭線には、節点１−４，４−３，３−１からなる線もこれらの線がモデルの稜線であることから表示されるべきなのに表示されていない。
また、従来の点を内含する要素を抽出する方法では、各要素について点を内含するかどうかのチェックを行わなければならず、点が大量にある場合には抽出のために長時間を要していた。
【００３５】
本発明は、このような課題に対処することを目的になされたものであり、少量のメモリしか搭載されていない計算機でも大規模な分割モデルからセグメントを抽出することが出来、輪郭線が忠実に表示できるようにする、またモデル中の任意の点を内含する要素を高速に抽出する有限要素分割モデルから辺，面，要素を抽出する方法及びその装置を提供することを目的とする。
【００３６】
【課題を解決するための手段】
上記課題を解決するために、本発明の有限要素分割モデルから辺，面，要素を抽出する方法は、メモリを有する計算機により有限要素分割モデルから辺，面，要素を抽出する方法であって、各要素と該要素を構成する節点とが対応して前記メモリ上の要素テーブルに記憶されている場合に、１つの辺，面または要素を１つのセグメントと見なして、有限要素分割モデルから前記セグメントを抽出する際に、前記セグメントに対して前記セグメントを構成する節点の組み合わせを特徴付ける指標値をつけ、同じ指標値を持つセグメントの情報が連続に並んだセグメントリストと、前記指標値と前記セグメントリスト上の位置とを関連づける指標テーブルとを前記メモリ上に作成し、前記メモリ上の前記セグメントリストと前記指標テーブルとに基づいて、同じ指標値を持つセグメントを抽出して、抽出されたセグメントを構成する節点情報を得るようにしたことを特徴とする。
【００３７】
ここで、前記セグメントリストに記憶される情報は、各セグメントを有する要素を特定する第１識別子と、該セグメントが前記要素の何番目のセグメントであるかを示す第２識別子とで表現される。また、前記セグメントリストに記憶されるセグメントは、前記指標値の大きい順または小さい順に並ぶ。また、前記第１識別子に１つの要素を構成するセグメントの数以上の所定の整数値を乗じ、これに前記第２識別子を加えることにより、前記第１及び第２識別子を１つの整数値として記憶する。また、前記指標テーブルの各指標値の情報は、該指標値に該当するセグメントの個数と該セグメントが記憶されるセグメントリストの先頭を指すポインタとで表現される。また、前記ポインタに１０以上の整数値を乗じ、これに前記セグメントの個数を加えることにより、前記個数及びポインタを１つの整数値として記憶する。
【００３８】
更に、抽出したセグメントの内、同一の節点からなるセグメントから構成される複数の要素を隣接要素として抽出する。更に、前記同一の節点からなるセグメントをセグメントリストから除去することにより、セグメントリストには重複のないセグメントだけが残るようにする。
又、本発明の有限要素分割モデルから要素を抽出する方法は、メモリを有する計算機により有限要素分割モデル中の１点Ｐeを内含する要素を抽出する方法であって、ある要素Ｅ0に内含されている既知の点Ｐ0を始点として、２点ＰeとＰ0を結ぶ線分と交差する要素Ｅ0の面Ｆ0を求め、要素Ｅ0と面Ｆ0を境界にして隣接する要素Ｅ1を求め、２点ＰeとＰ0を結ぶ線分と交差する要素Ｅ1のＦ0以外の面Ｆ1 を求め、該面Ｆ1 で要素Ｅ1と隣接する要素Ｅ2を求めるという処理を繰り返し、前記隣接する要素の抽出では、各要素と該要素を構成する節点とが対応して前記メモリ上の要素テーブルに記憶されている場合に、１つの辺，面または要素を１つのセグメントと見なして、前記セグメントに対して前記セグメントを構成する節点の組み合わせを特徴付ける指標値をつけ、同じ指標値を持つセグメントの情報が連続に並んだセグメントリストと、前記指標値と前記セグメントリスト上の位置とを関連づける指標テーブルとを前記メモリ上に作成し、前記メモリ上の前記セグメントリストと前記指標テーブルとに基づいて、同じ指標値を持つセグメントを抽出して、抽出されたセグメントを構成する節点情報を得て、抽出したセグメントの内、同一の節点からなるセグメントから構成される複数の要素を隣接要素とし、隣接する要素を辿っていくことにより、点Ｐeを内含する要素を抽出することを特徴とする。
【００３９】
又、本発明の有限要素分割モデルから辺を抽出する方法は、メモリを有する計算機により有限要素分割モデルから辺を抽出する方法であって、各要素と該要素を構成する節点とが対応して前記メモリ上の要素テーブルに記憶されている場合に、１つの辺を１つのセグメントと見なして、前記セグメントに対して前記セグメントを構成する節点の組み合わせを特徴付ける指標値をつけ、同じ指標値を持つセグメントの情報が連続に並んだセグメントリストと、前記指標値と前記セグメントリスト上の位置とを関連づける指標テーブルとを前記メモリ上に作成し、前記メモリ上の前記セグメントリストと前記指標テーブルとに基づいて、同じ指標値を持つセグメントを抽出して、抽出されたセグメントを構成する節点情報を得て、同一の節点からなるセグメントを前記セグメントリストから除去し、前記セグメントリストに残った面を複数の要素に共有されない面であるフリーフェイスとすることにより、３次元有限要素モデルからフリーフェイスを抽出し、該フリーフェイスを膜状要素の２次元要素とみなして、隣接する２次元要素を抽出し、隣接する２次元要素のなす角度θを求め、角度θの値が、許容値をδとすると、０≦θ＜（π−δ）、または（π＋δ）＜θ＜２πであるとき、前記２つの２次元要素の境界線を輪郭線として抽出することを特徴とする。更に、抽出したフリーフェイスに膜状要素の２次元要素からなる３次元形状の分割モデルを加えて、隣接する２次元要素を抽出し、角度θの値が、許容値をδとすると、δ≦θ＜（π−δ）、または（π＋δ）＜θ＜２π−δであるとき、前記２つの２次元要素の境界線を輪郭線として抽出する。
【００４０】
又、本発明の有限要素分割モデルから辺，面，要素を抽出する装置は、各要素と該要素を構成する節点とを対応して記憶する手段と、１つの辺，面または要素を１つのセグメントと見なして、前記セグメントに対して前記セグメントを構成する節点の組み合わせを特徴付ける指標値をつける手段と、同じ指標値を持つセグメントの情報が連続に並んだセグメントリストと、前記指標値と前記セグメントリスト上の位置とを関連づける指標テーブルとを作成する手段と、前記セグメントリストと前記指標テーブルとに基づいて、同じ指標値を持つセグメントを抽出して、前記各要素と該要素を構成する節点との対応に基づいて、抽出されたセグメントを構成する節点情報を得る手段とを備えることを特徴とする。
【００４２】
【作用】
かかる構成において、セグメントリスト中で、セグメントは構成する節点の数に関わらず要素番号と局所セグメント番号との２つで表現される。また、指標テーブルも同一の指標値を持つセグメントの数に関わらず該当数と先頭リスト番号との２つで表現される。その結果、セグメントリスト，指標テーブル中で、それぞれ１セグメント，１指標値当たりに消費されるメモリはそれぞれ整数２つ分となり、メモリを有効に使えるようになる。また、輪郭線はフリーフェイス間の稜線として抽出されることから、すべての輪郭線がもれなく抽出されるようになる。また、点を内含する要素の抽出は、隣接する要素を辿っていくことにより、ほぼ直線的に検索を進めて目的とする要素に到達できるようになり、短時間で目的とする要素に行き着く。
【００４３】
【実施例】
以下、本発明を実施例に従って詳細に説明する。
図２０に有限要素分割モデルからフリーフェイス，フリーエッジを抽出して表示する計算機システムのブロック図を示す。
図中、１６１は有限要素分割モデルあるいは抽出されたフリーフェイス，フリーエッジを表示する表示部であり、１６２は演算・制御用の中央処理装置（ＣＰＵ）、１６３は補助記憶用のＲＡＭであり、セグメントリストを記憶するセグメントリスト領域１６３−１，指標テーブルを記憶する指標テーブル領域１６３−２，指標値のカウント値を記憶する指標値カウンタ領域１６３−３，各要素を定義する節点の列を記憶する要素テーブル領域１６３−４を含む。１６４は有限要素分割モデルのデータあるいは指示命令を入力する入力部、１６５はＣＰＵ１６２の処理手順を格納するＲＯＭである。通常、入力部１６４からデータ及び指示を入力し、指示に対応してＲＯＭ１６５に格納された手順に従いＣＰＵ１６２で有限要素分割モデルからのフリーフェイス，フリーエッジの抽出を行い、結果を表示部１６１に表示する。
【００４４】
（実施例１）
図１〜図４に、本実施例による複数の要素に共有されないセグメントを抽出する処理の流れを、図５に本実施例で作成するセグメントリストと指標テーブルとの形式を示す。
本実施例では、セグメントリストを図５の（ａ）に示すようにリスト番号，要素番号及び局所セグメント番号の３項目で構成する。本リストは、リストに登録されるセグメントの順序及びリスト内でのセグメントの表現法を除いては、従来のセグメントリストと同じである。従って、本リストの行数は式（１）となる。以下に、本リストと従来のリストとの違いを説明する。
【００４５】
まず、本リストでは、セグメントの指標値（従来と同じセグメントを構成する節点番号の和）が同じものが連続のリスト番号に登録されているようにする。例えば、リスト番号に対してセグメントは指標値の小さい順に登録されるようにする。また、本リストでは１つのセグメントを要素番号と局所セグメント番号の２つで表現する。このことについて詳しく説明する。
一般に要素分割モデルの要素を構成する節点番号の列は、要素形状に対応して予め定められた一定の規定に従ってメモリ登録される。従って、要素内のすべてのセグメントについて、セグメントを構成する節点の組み合わせはメモリに登録されている節点番号列から一義的に決定される。そこで、予め各要素形状に対してすべてのセグメントに番号（局所セグメント番号と呼ぶ）を振っておけば、そのセグメント番号からそのセグメントを構成する節点列を一義的に求めることができる。
【００４６】
このことを、図６，図７を用いて具体的に説明する。
図６は節点ｎ１  〜ｎ６  からなる３角柱形状をした要素である。本３角柱要素において、常に節点はメモリにｎ１  −ｎ２  −ｎ３  −ｎ４  −ｎ５  −ｎ６  の順に登録されるものとする。すなわち、節点は底面の３角形、上面の３角形の順に登録され、１番目と４番目に登録される節点は１本の辺でつながっている。また、底面と上面で節点のまわる（登録される）方向は同じである。すると、本要素を構成する面は図７の（ａ）に示した５つである。そこで、５つの面に対して図７の（ａ）に示したような１〜５の面番号を振る。図６に図７の（ａ）で割り振った５つの面の番号を示す。
【００４７】
ここで、ｎ１  〜ｎ６  を一般的な節点番号と考えると、図７の（ａ）の各面はメモリ上でｎ１  〜ｎ６  に対応した場所に登録されている節点から構成される面とみなすことができる。例えば、面番号１はメモリ上で１〜３番目に登録されている節点から構成される面とみなすことができる。従って、どのような３角柱要素に対しても面番号を指定することによって、その面を構成する節点の組み合わせを一義的に求めることができる。
【００４８】
このことは辺についても同様であり、一般的なセグメントに対しても同じである。図７の（ｂ）に３角柱要素を構成する辺の節点列を示し、各辺に振った辺番号を図６に示す。例えば、辺番号１はメモリ上で、１，２番目に登録されている節点（ｎ１  ，ｎ２  ）から構成される辺を示す。
以上のように、すべてのセグメントは、そのセグメントを持つ要素番号と局所セグメント番号とを用いて表現でき、２つのデータからセグメントを構成する節点を求めることができる。すなわち、どのようなセグメントに対しても、セグメントリスト中ではこのような２つのデータを登録しておくだけで十分である。
【００４９】
次に、本実施例で使用する指標テーブルについて説明する。指標テーブルは図５の（ｂ）に示すように、指標値，該当数，先頭リスト番号の３つの項目からなる。ここで、指標値は従来と同様に１から始まる連続的な整数値であり、本テーブルの行番号を示す番地として使用する。また、番地をセグメントの指標値と対応させる。従って、本テーブルの必要とする行数は従来と同じ（２）式で与えられる。本実施例では、本テーブルに各指標値を持つセグメントの数（該当数）と、及び指標値に対応するセグメントリストの最初の番地を指す先頭リスト番号とを登録する。
【００５０】
このことについて、以下に詳しく説明する．以下の説明中で括弧内は図５との対応を示す。
すでに述べたように、本実施例のセグメントリスト中では、同じ指標値をもつセグメントは連続のリスト番号に並んで登録されている。そして、本指標テーブルの該当数と先頭リスト番号とは、各指標値を持つセグメントの数とそのセグメントが登録されているリストの先頭の行番号とを指す。従って、本セグメントリストと指標テーブルとを使用することで、あるセグメントが与えられたとき、そのセグメントと同じ指標値を持つセグメントを容易に検索することができる。
【００５１】
すなわち、まず与えられたセグメントの節点から指標値を計算し（＝３とする）、指標テーブルのその指標値の行を参照する。そして、そのセグメントと同じ指標値を持つセグメントの数（該当数＝２）と先頭リスト番号（＝１）を得る。次に、その先頭リスト番号（＝１）からそれに続く該当数の数（＝２）だけの行のセグメントリストを参照することで、個々のセグメントがわかる。なお、ここでわかる個々のセグメントは、要素番号と局所セグメント番号という形式で与えられる。しかし、これは上で説明したように、メモリ上に登録されている要素を構成する節点番号の列と、局所セグメント番号の割り振り方を参照することで、容易にセグメントを構成する節点番号の列に変換することができる。
【００５２】
図１に従って、セグメントリストと指標テーブルとを作成する手順およびそれらを使用して複数の要素に共有されないセグメントを抽出する処理の流れを説明する。
まず、図１のステップＡ１０１〜Ａ１０３でセグメントリストと指標テーブルを作成する。ステップＡ１０１の詳細を図２に示す。ステップＡ１０１の処理は、各指標値を持つセグメントがそれぞれいくつあるかを求め、指標テーブルの各指標値の該当数の項にその値を登録するものである。本処理では、まずステップＡ１１１で、指標テーブルの該当数の項をすべて零にする。次に、ステップＡ１１２でセグメントの設定を行い、ステップＡ１１３で各セグメントについて指標値を計算する（＝ｋとする）。その計算毎に対応する指標値の該当数の値（Ｍｋ  ）をステップＡ１１４にて新しい値（旧値よりも１つ大きい値、すなわち（Ｍｋ  ＋１））に更新することによって行う。
【００５３】
図１のステップＡ１０２の詳細を図３に示す。ステップＡ１０１の処理で各指標値を持つセグメントの数がわかったので、本処理では各セグメントがセグメントテーブルに連続して（空行なく）登録されるようにその先頭リスト番号を計算する。図３は、セグメントリスト中でセグメントが指標値の小さい順に並ぶようにする手順である。ステップＡ１２１〜Ａ１２６の処理によって、指標テーブルのｋ行目の先頭リスト番号として、１〜（ｋ−１）行目の該当数の加算値（すべてを足し合わせた数）に１を加えた値がステップＡ１２３にて登録される。
【００５４】
図１のステップＡ１０３の詳細を図４に示す。ここでは、ステップＡ１０１〜Ａ１０２で作成した指標テーブルを使用してセグメントリストを作成する。リスト作成にあたって、指標テーブルの各指標値にそれぞれカウンタを用意し、ステップＡ１３１ですべてのカウンタを零に初期化しておく。次に、ステップＡ１３２，Ａ１３３で、各要素のセグメントについて指標値を計算し（＝ｋとする）、ステップＡ１３４で指標テーブルとカウンタとからその指標値の先頭リスト番号（Ｌｋ  ）およびカウンタ値（Ｍｋ  ）を得る。ステップＡ１３５では、その先頭リスト番号にカウンタ値を加えた番地のセグメントリストの行（Ｌｋ  ＋Ｍｋ  行目）にそのセグメントの要素番号と局所セグメント番号とを登録する。その後、ステップＡ１３６で指標値ｋのカウンタの値（Ｍｋ  ）は１つ大きい値（Ｍｋ  ＋１）に更新する。
【００５５】
以上のようにして、すべてのセグメントは、セグメントリストの１行目から空行なく指標値の小さい順に並ぶ。
なお、ここでは各指標値に対して新たにカウンタ用のメモリを設けたが、これは指標テーブルの該当数のメモリを一時的に代用してもよい。すなわち、まずステップＡ１３１にて指標テーブルの該当数の項をすべて零に初期化し、以後ステップＡ１３２〜Ａ１３７の処理では、本該当数の項を上記カウンタとして用いる。ステップＡ１３２，Ａ１３３の指標値計算後、ステップＡ１３４では指標テーブルのｋ行目のカウンタ値（該当数の項の値Ｍｋ  ）と先頭リスト番号（Ｌｋ  ）を得る。ステップＡ１３５では、先頭リスト番号にカウンタ値を加えた番地のセグメントリストの行（Ｌｋ  ＋Ｍｋ  行目）にセグメントを登録する。次に、ステップＡ１３６で、セグメントを登録するたびにカウンタ値（該当数の項の値）に１を加算して更新する。なお、カウンタ値は、すべてのセグメントを登録した段階で、ステップＡ１３１で初期化する前の該当数の値と同じとなる。従って、このように該当数のメモリを一時的にカウンタとして代用しても、該当数を復元するための後処理は不要である。該当数のメモリをカウンタとして代用することにより、使用するメモリをセグメントリストと指標テーブルとだけにすることができ、メモリの節約をはかることができる。
【００５６】
なお、ここではセグメントを指標値の小さい順に並べたが、大きい順に並べてもよい。これは指標テーブルの先頭リスト番号を作成する過程（図３）で、該当数の値を指標値が最大の行から小さい方に順に加算することによって達成される。具体的には図３のステップＡ１２１の処理中で、“ｋ←（２）式の計算値”とし、ステップＡ１２２を“ｋ←（ｋ−１）”、ステップＡ１２６を“ｋ＞１”とすればよい。
【００５７】
次に、作成したセグメントリストと指標テーブルとを用いて、複数の要素に共有されないセグメントを抽出する過程を説明する。本過程は、図１のステップＡ１０４〜Ａ１０７に示される。以下本図に従って説明する。
まず、ステップＡ１０４でチェックの対象とする指標値（ｋとする）を設定する。そして、ステップＡ１０５にて指標テーブルのｋ行目の該当数をチェックし、１つ以下なスば本指標値を持つセグメント中に同じものはないと判定し、なにも行わずステスプＡ１０７の処理に移る。２つ以上の該当するセグメントがあるならば、指標スーブルから先頭リスト番号（Ｌｋ  ）と該当数（Ｍｋ  ）を得る。そして、セグメントリストのＬｋ  行目から始まるＭｋ  行のセグメント間で重複するものがないかを、構成する節点を比較することでチェックする。
【００５８】
もし重複するものがあれば、ステップＡ１０６にてセグメントリストからその重複するセグメントを両者とも除去する。除去はセグメントリスト中の該当する要素番号を零や負の数等、要素番号としてありえない数値に更新することによって行う。ステップＡ１０４〜Ａ１０６の操作をすべての指標値に対して終了したかを、ステップＡ１０７でチェックし、終了していなければステップＡ１０４に戻って処理を繰返し、抽出過程が完了するまで行う。本過程終了後、セグメントリスト中で妥当な要素番号を持つセグメントが、複数の要素に共有されないセグメントである。
【００５９】
以上の複数の要素に共有されないセグメントを抽出する過程を、実際の簡単な要素分割モデルからフリーフェイスを抽出する過程を例にとって説明する。
図８は、従来技術の項で説明に用いたのと同じ、２つの４面体要素からなる分割モデルである。ここで各要素を構成する節点はそれぞれ次のようにメモリ上に登録されているものとする。
【００６０】
Ｅ１：１−２−３−４
Ｅ２：３−１−４−５
２つの要素の節点番号は同じ規則に従って登録されている。すなわち１〜３番目に登録されている節点のまわり方が、その方向に右ネジを回したときネジが要素の重心方向に向かうようになっている。
【００６１】
ここで、４面体要素を構成する面の番号を要素Ｅ１の場合を例にとり、次のように定義する。
面１：節点１−２−３  （指標値：６（＝１＋２＋３））
面２：節点１−４−２  （指標値：７）
面３：節点２−４−３  （指標値：９）
面４：節点３−４−１  （指標値：８）
すると、要素Ｅ２を構成する面の面番号との関係は次のようになる。
【００６２】
面１：節点３−１−４  （指標値：８）
面２：節点３−５−１  （指標値：９）
面３：節点１−５−４  （指標値：１０）
面４：節点４−５−３  （指標値：１２）
ここで、括弧内の値は、各面の指標値である。
【００６３】
要素Ｅ２の面は、メモリ上の要素Ｅ１の構成節点列からＥ１を構成する各面の節点の組み合わせを作成したのと全く同様に作成したものである。例えば面１の節点はメモリ上の１〜３番目の節点番号を順に並べたものである。
図８に各面番号を要素Ｅ１のものについては数字を丸で囲んで、要素Ｅ２については四角で囲んで示した。
【００６４】
本分割モデルについて作成したセグメント（面）リストと指標テーブルとを図９に示す。本リストとテーブルを作成する手順を以下に説明する。
（１）指標テーブルの該当数の項を作成する（図２）。ステップＡ１１１にて、まず指標テーブルの該当数の項をすべて零に初期化する。次に、ステップＡ１１３にて要素Ｅ１の面１の指標値を計算し（＝６）、ステップＡ１１４にて、指標テーブルの６行目の該当数の値を１つ大きい値（１←０＋１）に更新する。要素Ｅ１，Ｅ２のすべての面について更新を完了することにより、図９の（ｂ）の該当数の値を得る。
【００６５】
（２）次に指標テーブルの先頭リストの項を作成する（図３）。これは指標値の小さい順に該当数を加算して、指標テーブルのｋ行目に１〜（ｋ−１）行目の該当数の加算値（すべてを足し合わせた値）を登録する。本処理により図９の（ｂ）の先頭リスト番号の値を得る。
（３）面リストを作成する（図４）。本処理では、まずステップＡ１３１で指標テーブルの該当数（カウンタとして用いる）をすべて零に初期化する。次に、ステップＡ１３３で要素Ｅ１の面１から順に指標値を計算し、その値からステップＡ１３４で先頭リスト番号とカウンタ値（該当数の項の値）とを参照し、ステップＡ１３５にて該当する面リストの項に面を登録する。例えば、要素Ｅ１の面１の指標値は６であることから、指標テーブルの６行目の先頭リスト番号（＝１）およびカウンタ値（＝０）を参照し、面リストの１（＝１＋０）行目に、本面（要素Ｅ１の面番号１）を登録する。登録後、ステップ１３６では、本指標値のカウンタ値は古い値に１を加えた値に更新する。ここでは、指標テーブル６行目のカウンタ値（該当数の値）を零から１に更新する。本操作をすべてのセグメントに対して行うことにより図９の（ａ）の面リストを得る。
【００６６】
面リストと指標テーブルとを作成後、フリーフェイスを抽出する。本処理は、ここで作成した面リストから複数の要素に共有されている面を除去することによって行う。以下にその手順を示す。
（４）ステップＡ１０４で、指標値１をチェック対象として設定する（図１）。
【００６７】
（５）ステップＡ１０５，Ａ１５２，Ａ１０７，Ａ１５１では、指標テーブルの１行目を参照し、該当数の項の値が零であることから、なにも行わず次の指標値の設定に移る。
（６）指標値２〜７についても、該当セグメントは１以下であることからなにも行わない。
【００６８】
（７）指標値８をチェック対象として設定する。
（８）ステップＡ１０５で指標テーブルの８行目を参照し、該当数が２であることから、２つの面について重複を調べる。まず、指標テーブルの先頭リスト番号（＝３）を参照し、その番号から対応する面リストの３行目と４行目（該当数が２であることから２行）を参照する。これによって、要素Ｅ１の面４と要素Ｅ２の面１が指標値８に対応した面であることがわかる。要素番号と面番号を構成する節点番号に変換し（本変換が容易に行えることは既に説明済み）、共に節点１，３，４からなっていることがわかる。そこでこれらの面はフリーフェイスではないので、面リストから除去する。具体的には面リストの３，４行目の要素番号の項を零にする。
【００６９】
（９）指標値９〜１２についても同様にチェックする。指標値９は該当する面が２つ（要素Ｅ１の面３と要素Ｅ２の面２）あるが、構成する節点番号が異なる。その他の指標値は該当数がすべて１以下であることがわかる。その結果除去される面はない。
以上の処理の結果、図９の（ａ）の面リストから３，４行目を除いた面がフリーフェイスとして抽出される。
【００７０】
次にここで用いた２つの４面体要素の分割モデルから、フリーエッジを抽出する例について説明する。まず、各要素を構成する辺の番号を図１０に示す。図中、要素Ｅ１，Ｅ２の局所辺番号をそれぞれ数字を丸、四角で囲んで示した。ここで、各要素の辺番号と構成節点とは、フリーフェイス抽出の場合と同様に、メモリ上の構成節点列から規則的につけたものである。各要素の辺を構成する節点番号と各辺の指標値とは、次の通りである。
【００７１】
0003624015.tif 000004
本分割モデルについて作成したセグメント（辺）リストと指標テーブルとを図１１に示す。本リストとテーブルとを作成する手順を以下に説明する。本手順は、フリーフェイス抽出の際のリストとテーブルの作成処理とほぼ同様である。
【００７２】
（１）指標テーブルの該当数の項を作成する（図２）。まず、ステップＡ１１１にて、指標テーブルの該当数の項をすべて零に初期化する。ステップＡ１１３では、要素Ｅ１の辺１の指標値を計算し（＝３）、ステップＡ１１４にて、指標テーブルの３行目の該当数の値を１つ大きい値（１←０＋１）に更新する。要素Ｅ１，Ｅ２のすべての辺について更新を完了することにより、図１１の（ｂ）の該当数の値を得る。
【００７３】
（２）指標テーブルの先頭リストの項を作成する（図３）。指標値の小さい順に該当数を加算して、指標テーブルのｋ行目に１〜（ｋ−１）行目の該当数の加算値（すべてを足し合わせた値）を登録する。本処理により、図１１の（ｂ）の先頭リスト番号の値を得る。
（３）辺リストを作成する（図４）。まず、ステップＡ１３１にて、指標テーブルの該当数（カウンタとして用いる）をすべて零に初期化する。ステップＡ１３３で、要素Ｅ１の辺１から順に指標値を計算し、その指標値から、ステップＡ１３４では、先頭リスト番号とカウンタ値（該当数の項の値）を参照し、ステップ１３５で、該当する面リストの項に面を登録する。例えば、要素Ｅ１の辺１の指標値は３であることから、指標テーブルの３行目の先頭リスト（＝１）およびカウンタ値（＝０）を参照し、面リストの１（＝１＋０）行目に、本辺（要素Ｅ１の辺番号１）を登録する。ステップＡ１３５の登録後、ステップＡ１３６で本指標値のカウンタ値（該当数の項の値）は古い値に１を加えた値に更新する。ここでは、指標テーブル３行目のカウンタ値（該当数）を零から１に更新する。本操作をすべてのセグメントに対して行うことにより図１１の（ａ）のリストを得る。
【００７４】
辺リストと指標テーブルとを作成後、フリーエッジを抽出する。本処理は、ここで作成した辺リストから複数の要素に共有されている辺を除去することによって行う。以下にその手順を示す。
（４）指標値１をチェック対象として設定する（図１ステップＡ１０４）。
（５）ステップＡ１０５，Ａ１５２，Ａ１０７，Ａ１５１では、指標テーブルの１行目を参照し、該当数の項の値が零であることから、なにも行わず次の指標値の設定に移る。
【００７５】
（６）指標値２，３についても、該当セグメントは１以下であることからなにも行わない。
（７）指標値４をチェック対象として設定する。
（８）ステップＡ１０５で指標テーブルの４行目を参照し、該当数が２であることから、２つの辺について重複を調べることにする。まず、指標テーブルの先頭リスト番号（＝２）を参照し、その番号に対応する面リストの２行目と３行目（該当数が２であることから２行）を参照する。これによって、要素Ｅ１の辺３と要素Ｅ２の辺１とが本指標値に対応した面であることがわかる。要素番号と辺番号を構成する節点番号に変換し、共に節点１，３からなっていることがわかる。そこで、これらの辺はフリーエッジではないので、辺リストから除去する。具体的には辺リストの２，３行目の要素番号を零にする。
【００７６】
（９）指標値５〜９についても同様にチェックする。その結果、辺リストのリスト番号５，６，９，１０が除去される。
以上の処理の結果、図１１の（ａ）の辺リストにおける１，４，７，８，１１，１２行の辺がフリーエッジとして抽出される。
なお以上の処理では、セグメントリスト中でセグメントを要素番号と局所セグメント番号との２つの整数値で表現し、１つのセグメントに対して２整数分のメモリを使用した。しかし、これは１つのメモリで済ませることが可能である。すなわち局所セグメント番号は必ず１つの要素を構成するセグメントの数以下となる。そこでセグメントを次式（３）のＳＧで表現して登録する。
【００７７】
ＳＧ＝（要素番号）×（α＋１）＋（セグメント番号）            （３）
ここで、αは１要素当たりのセグメント数以上の整数値である。
なお、本表現から要素番号とセグメント番号には、次式によって戻すことができる。
要素番号＝ＳＧ／（α＋１）                                    （４）
セグメント番号＝ＭＯＤ（ＳＧ、（α＋１））                      （５）
（ＳＧを（α＋１）で割った剰余）
ここで、式（４）の要素番号は右辺の計算値の小数点以下を切り捨てた整数値である。
【００７８】
モデル中にいくつかの要素形状が含まれている場合には、形状によりセグメントの数が異なる。このような場合にはその最大値をαとすればよい。
また、以上の説明ではセグメント番号を１番から始めたが、これを０から始めてもよい。こうすることにより式（３）乃至（５）における（α＋１）はαになる。
【００７９】
このようにセグメントを１つの整数値で表現することにより、セグメントリストが使用するメモリは半分になる。
これと同様に指標テーブルの該当数と先頭リスト番号も１つの整数値で表すことができる。発明者の経験によれば、通常の分割モデルにおいて同一の指標値の持つセグメントは１０個以下である。すなわち、該当数は１０以下の整数値となり、該当数と先頭リスト番号とを（６）式のＡＤで表現することができる。
【００８０】
ＡＤ＝（先頭リスト番号）×β＋（該当数）                      （６）
ここで、βは１０以上の整数である。
なお、本表現から該当数と先頭リスト番号には、次式によって戻すことができる。
先頭リスト番号＝ＡＤ／β                                      （７）
該当数＝ＭＯＤ（ＡＤ、β）；（ＡＤをβで割った余剰）          （８）
ここで、式（７）の先頭リスト番号は右辺の計算値の小数点以下を切り捨てた整数値である。
【００８１】
このように指標テーブルの該当数と先頭リスト番号とを１つの整数値で表現することにより、使用するメモリは更に減る。
従来技術の課題でとりあげた、６面体要素からなる１００万要素、１００万節点の分割モデルからフリーフェイスを抽出する場合について、本方法を用いた場合の所要メモリを計算してみる。
【００８２】
まず、面リストが必要とするメモリは、１セグメント当たりのセグメント情報が１整数分（４バイト）、リストの行数が従来と同じ６００万行であることから２４Ｍ（４×６００万）バイトである。また、指標テーブルが必要とするメモリは、１指標値当たりの使用メモリが４バイト、テーブルの行数が従来と同じ約４００万行であることから、約１６Ｍ（４×４００万）バイトである。
【００８３】
この結果、本分割モデルに要するメモリは合計４０Ｍバイト（２４Ｍ＋１６Ｍ）となる。このメモリ容量は、現在の計算機をもってすれば十分対応可能な値であり、一般的な計算機でも処理が可能である。
なおここでは、３次元分割モデルからフリーフェイス，フリーエッジを抽出するに場合について説明したが、本方法は２次元モデルからフリーエッジを抽出する際にも同様に適用することができ、また一般的なセグメントを抽出する方法として使用することができる。
【００８４】
（実施例２）
実施例１では、全セグメントから複数の要素に共有されるセグメントを除去することによって、フリーフェイス，フリーエッジ等の複数の要素に共有されないセグメントを抽出した。一方、実施例１で除去した複数の要素に共有されているセグメントは、そのセグメントによって複数の要素が隣接していることを意味する。そこで本実施例では、実施例１で作成したセグメントリストと指標テーブルとを利用して、隣接する要素を抽出する方法について説明する。
【００８５】
使用するセグメントリストと指標テーブルとは、図１のステップＡ１０１〜Ａ１０３で作成したものと同じなので作成方法の説明を省略し、ここでは隣接する要素を抽出する方法だけを説明する。
図１２に隣接する要素を抽出する処理の流れを示す。本処理はセグメントリストと指標テーブルとを作成した後に行うものである。
【００８６】
まず、どの要素のどのセグメントで隣接する要素を抽出したいのかをステップＡ８０１にて設定する。ここで、要素を要素番号（Ｅｉ  とする）で、セグメントを局所セグメント番号（Ｌｉ  とする）で指定する。なお、局所セグメント番号とは実施例１で説明した要素内でのセグメントの番号である。そして、ステップＡ８０２にてセグメントＬｉ  の指標値（Ｍｉ  とする）を計算する。次に、ステップＡ８０３にて、指標テーブルのＭｉ  行目を参照し、該当数が１ならば、ステップＡ８０６で要素Ｅｉ  のセグメントＬｉ  で隣接している要素はない。該当数が２以上ならば、実施例１で説明したのと同様な方法で本セグメントと同じ節点からなるセグメントを検索する。もし要素Ｅｉ  のセグメントＬｉ  以外に同一のセグメントがなければ、ステップＡ８０６で隣接要素はないとする。あれば、そのセグメントを持っている要素が隣接要素である。
【００８７】
本処理を簡単な要素分割モデルを用いて具体的に説明する。
図１３は３つの４面体要素からなる分割モデルである。本分割モデルは図２３の分割モデルに節点５−１−４−６からなる要素Ｅ３を付加したものである。要素Ｅ１，Ｅ２の局所番号は図８に示した通りであり、要素Ｅ３の面は次の通りである。括弧内は各面の指標値である。
【００８８】
面１：節点５−１−４  （指標値：１０）
面２：節点５−６−１  （指標値：１２）
面３：節点１−６−４  （指標値：１１）
面４：節点４−６−５  （指標値：１５）
本分割モデルにおいて、要素Ｅ３とＥ３の面１で隣接する要素を抽出する場合を説明する。
【００８９】
抽出に先だって、図１４の（ａ）に示す面リストと図１４の（ｂ）に示す指標テーブルとを作成する。本リストとテーブルは、図１のステップＡ１０１〜Ａ１０３の処理で作成されるものであり、その作成法は省略する。リストとテーブルを作成後、以下の処理を行う。
（１）図１２のステップＡ８０２では、要素Ｅ３の面番号１の指標値を計算する。指標値は１０である。
【００９０】
（２）ステップＡ８０３で指標テーブルの１０行目を参照する。
（３）ステップＡ８０４では、該当数が２で先頭リスト番号が７であることから、面リストの７，８行目を参照し、本指標値を持つ面が要素Ｅ２の面番号３と要素Ｅ３の面番号１であることがわかる。そこで、これらの要素番号と面番号の情報を面を構成する節点番号に変換して、２つの面が同一であるかをステップＡ８０５にて検査する。検査の結果２つの面は同一である（共に節点１，４，５からなる）ことがわかり、隣接する要素としてＥ２が抽出される。
【００９１】
本処理を通して、要素Ｅ２とＥ３とはそれぞれ局所面番号３，１でお互いに隣接していることがわかった。
以上の説明からわかるように、本方法は基本的に実施例１で説明したセグメントリストと指標テーブルとを用いたセグメントの抽出方法を応用したものである。セグメントリストと指標テーブルとは短時間で作成することができることから、本方法によれば高速に隣接する要素を抽出することができる。
【００９２】
なお、ここでは面で隣接している場合の例について述べたが、これはその他のセグメントで隣接してもよい。例えば辺，節点で隣接している（辺，節点を共有している）場合についても、図１２の操作で同様に抽出を行うことができる。ただし辺，節点の場合には、分割モデルの構造上、ステップＡ８０５においては複数個の隣接する要素が抽出される。
【００９３】
（実施例３）
実施例２では、隣接する要素を抽出する方法について述べた。ここで抽出した隣接要素を用いれば、分割モデル中の任意の点について、その点を内含する要素を容易に抽出することが可能である。本実施例では実施例２で説明した隣接要素をこのような、点を含む要素の抽出に適用した例について説明する。
【００９４】
処理の流れを図１５に示し、図１３の点Ｐｅ  を含む要素を抽出する場合を例に説明する。なお、図１３中で点Ｐｅ  は要素Ｅ３に内含されている。
以下、図１５に従って処理の流れを説明する。
（１）図１５のステップＢ１０１では、どの要素に内含されているかが既にわかっている点Ｐ０  を設定し、その要素番号をｉとする。図１３では要素Ｅ１の重心をＰ０  とした。従って図１５中でｉは１である。
【００９５】
（２）ステップＢ１０２で、点Ｐｅ  が要素Ｅｉ（Ｅ１）に内含されているかどうかをチェックする。本チェックは以下の手順で容易に行うことができる。
まず、要素Ｅｉ  を構成する１つの面Ｆｎ  の法線ベクトルＡを計算する。本法線ベクトルは次式（９）によって計算される。
Ａｘ＝  （ｙ１−ｙ３）（ｚ２−ｚ３）−（ｙ２−ｙ３）（ｚ１−ｚ３）
Ａｙ＝  （ｚ１−ｚ３）（ｘ２−ｘ３）−（ｚ２−ｚ３）（ｘ１−ｘ３）
Ａｚ＝  （ｘ１−ｘ３）（ｙ２−ｙ３）−（ｘ２−ｘ３）（ｙ１−ｙ３）                            （９）
ここで、Ａｘ  ，Ａｙ  ，Ａｚ  は法線ベクトルの成分、（ｘ１  ，ｙ１  ，ｚ１  ），（ｘ２  ，ｙ２  ，ｚ２  ），（ｘ３  ，ｙ３  ，ｚ３  ）は面Ｆｎ  を構成する３つの節点の座標値である。３つの節点の順番は実施例１で述べたように、メモリに登録された節点番号から規則的に作成したものとする。３つの節点の順番をこのようにすることにより、本法線ベクトルは、要素Ｅｉ  に対して同じ方向を向く。例えば図１３において、各面の法線ベクトルはすべての要素の重心方向を向く。そこで、ここでは点Ｐｅ  が、各面に対して法線方向を基準にしたときにどちら側に位置しているかを調べることにより、内含をチェックする。
【００９６】
すなわち、まず次式（１０）の（ｘ，ｙ，ｚ）に点Ｐｅ  の座標値を代入し、Ｖを計算する。
Ｖ  ＝Ａｘ（ｘ−ｘ１）＋Ａｙ（ｙ−ｙ１）＋Ａｚ（ｚ−ｚ１）                            （１０）
ここで、Ｖ＞０ならば、点Ｐｅ  は面Ｆｎ  に対してその法線方向側に位置し、Ｖ＜０ならば、法線方向と反対側に位置していることを意味する（Ｖ＝０ならば面上の点である。例えば図１３の場合、Ｖ＞０ならば要素の重心方向、Ｖ＜０ならば要素の外方向に点Ｐｅ  は位置していることを意味する。そこで、Ｖを要素を構成するすべての面について計算し、すべての面について点Ｐｅ  が要素の重心側に位置している場合に、点Ｐｅ  は要素Ｅｉ  に内含されているとする。１つ以上の面について要素の外側に位置しているならば、内含していないとする。
【００９７】
（３）ステップＢ１０３では、点Ｐｅ  が要素Ｅｉ  に内含されていないならば、線分Ｐ０  Ｐｅ  と交差する要素Ｅｉ  の面（面番号Ｌｋ  とする）を求める。図１３の場合、線分Ｐ０  Ｐｅ  は要素Ｅ１の面３−１−４と点Ｐ１  で交差している。交差する面の抽出は、要素Ｅｉ  の面の内から２点Ｐ０  ，Ｐｅ  がそれぞれ面をはさんで異なる側にあるものを選択することによって行う。これは式（１０）に、点Ｐ０  ，Ｐｅ  の座標値を代入しそれぞれのＶを計算し、２つのＶの値の符号が異なる面を選択すればよい。Ｐｅ  が要素Ｅｉ  に内含されていないならば、必ず線分Ｐ０  Ｐｅ  と交差する（２点Ｐ０  ，Ｐｅ  が異なる側にある）面が存在する。
【００９８】
（４）ステップＢ１０４で、要素Ｅｉ  と面Ｌｋ  で隣接している要素を求める（Ｅｊ  とする）。これは実施例２で説明した方法で行う。図１３ではＥｊ  はＥ２である。
（５）ステップＢ１０５で、ここで求めた隣接要素Ｅｊ  にＥｉ  を置き換えて、再び点Ｐｅ  が要素Ｅｉ（Ｅ２）に内含されるかどうかをステップＢ１０２でチェックする。内含されていなければ再びステップＢ１０３にて、線分Ｐ０  Ｐｅ  と交差する要素Ｅｉ（Ｅ２）の面を求める。ただし、ステップＢ１０３を２回目以降実行する場合は、前回求めた面を求める面の対象から外す。例えば、図１３において要素Ｅ２の面のうち面３−１−４はステップＢ１０３の１回目の実行で求められたので外し、面１−４−５を得る。
【００９９】
（６）ステップＢ１０２〜Ｂ１０５の処理を、要素Ｅｉ  が点Ｐｅ  を内含するようになるまで繰り返す。図１３では、要素Ｅ２の面１−４−５の隣接要素として要素Ｅ３を得、要素Ｅ３が点Ｐｅ  を内含する。
このように本方法によれば、分割モデル中の適当な点（ここでは点Ｐ０  ）を始点として、隣接する要素を辿ることにより、目的とする点Ｐｅ  を内含する要素を抽出することができる。なお、発明者の経験から、隣接する要素を辿っていく本方法によれば、辿る経路はほぼ直線的であり、比較的早く目的とする要素に到達することがわかっている。すなわち、ｎ個の要素からなる分割モデルの場合、約ｎの３乗根の要素について内含のチェックを行えば、目的とする要素にたどりつく。
【０１００】
なお、ここでは始点を適当に定めたが、複数の点がモデル中にあるような場合には、前に抽出した点を始点として次の点を抽出するとよい。これは、点が曲線上に乗って順に並んでいるような場合に、隣接する要素を辿っていく道のりが短くて済み効率的だからである。
（実施例４）
従来はフリーエッジを輪郭線の代用として使用した。ここでは、実施例２で説明した隣接する要素を求める方法を利用して、フリーフェイスのなす角度から輪郭線を求める方法について説明する。
【０１０１】
３次元要素分割モデルから抽出したフリーフェイスは、２次元要素（膜状要素）からなる。そこで、抽出した各フリーフェイスに対してそれぞれ隣接する２次元要素を求め、その隣接する２つのフリーフェイスのなす角度を計算することにより、その稜線（２つの要素の境界線）を輪郭線として登録するかどうかを判定する。本輪郭線を抽出する過程を図１６に示し、以下本図に従って処理過程を説明する。
【０１０２】
まず、分割モデルからステップＢ２０１にてフリーフェイスを抽出する。本処理は実施例１で既に説明したので、ここでは説明を省略する。次に、ステップＢ２０２で、抽出したフリーフェイスを２次元要素とみなして、辺リストと指標テーブルとを作成する。本リストとテーブルを作成する方法も実施例１と同様である。次に、ステップＢ２０３〜Ｂ２０８にて、フリーフェイスの１つ（Ｅｉ  とする）について、そのフリーフェイスの１つの辺（Ｌｊ  とする）を境界にして隣接するフリーフェイスを抽出する。本処理は実施例２で図１２に示した方法で行うものであり、図中、ステップＢ２０３とＢ２０４はステップＡ８０１に対応し、ステップＢ２０５〜Ｂ２０８はステップＡ８０２〜Ａ８０５にそれぞれ順に対応する。
【０１０３】
フリーフェイスＥｉ  と辺Ｌｊ  で隣接するフリーフェイスを抽出した後、両者のなす角度（θとする）をステップＢ２０９で計算する。本角度の計算は両者の法線ベクトルをそれぞれ求め、その法線ベクトルのなす角度を計算することによって求めることができる。そして法線ベクトルのなす角度がπにほぼ等しければ、２つの面がほぼ１平面上にあることを意味するので何も行わない。それ以外ならば、両面が隣接している辺Ｌｊ  を輪郭線としてステップＢ２１２で登録する。図１６においては、角度θがほぼπに等しいかどうかを、許容値δを用いて比較している。なお、ステップＢ２０７，Ｂ２０８において、該当数が１つまたは隣接フリーフェイスがないと判定された場合には、本フリーフェイスの辺Ｌｊ  は端部の辺であると判定し、辺Ｌｊ  を輪郭線として登録する。本操作を全フリーフェイスのすべての辺について実行することにより、すべての輪郭線を抽出できる。
【０１０４】
以上の操作を図１７に示した簡単な分割モデルを用いて具体的に説明する。なお、図１７のモデルは図２３と同じである。
（１）実施例１で説明した方法で、図１６のステップＢ２０１で、次の６つの面をフリーフェイスとして抽出する。そして各フリーフェイスに対して、新たに２次元要素としての要素番号をつける（Ｆ１〜Ｆ６とする）。
【０１０５】
0003624015.tif 000005
（２）要素Ｆ１〜Ｆ６について、辺をセグメントとしてセグメントリストと指標テーブルとをステップＢ２０２で作成する。ここでは、要素Ｆ１，Ｆ２の局所セグメント番号（辺番号）を以下のように定義し、図１７に各要素の辺番号をそれぞれ数字を丸、四角で囲んで示した。作成したセグメントテーブルを図１８に示す。なお、図１８には要素Ｆ１，Ｆ２に関係した一部分だけを記載した。
【０１０６】
0003624015.tif 000006
（３）要素Ｆ１と同要素の辺番号１を境界にして隣接する要素を、ステップＢ２０３〜Ｂ２０８で求める。その結果、要素Ｆ２が抽出される。
【０１０７】
（４）要素Ｆ１とＦ２とのなす角度（θ）を計算する。本角度の計算は次のように行う。
まず、２つの面の法線ベクトル（図１７中のベクトルＡ１  ，Ａ２  ）を計算する。法線ベクトルＡ１  ，Ａ２  は、前出の式（９）によって計算される。実施例３で述べたように、２次元要素（フリーフェイス）を構成する節点番号の順番に規則性を持たせれば、本法線ベクトルは２次元要素の元となる３次元要素に対して同じ方向を向く。例えば図１７において、すべての２次元要素の法線ベクトルは、要素を構成する節点の順番に右ネジを回したときネジの進む方向を向き、それは元の３次元要素（４面体要素）の重心方向である。このことは、法線ベクトルがすべて、モデルの表面においてモデルの内側を向くことを示す。
【０１０８】
従って、２つの法線ベクトルＡ１  ，Ａ２  のなす角度が、要素Ｆ１とＦ２とのなす角度θとなる。これは次式（１１）によって計算される。
【０１０９】
0003624015.tif 000007
ただし、ここでは、０≦θ≦πとする。θを０〜２πとしなくても問題がないことは、図１６のステップＢ２０９の判定条件からわかる。
【０１１０】
ここでは、θ＜（π−δ）であることから、ステップＢ２１２で要素Ｆ１の辺１を輪郭線として登録する。
（５）前記の（３），（４）項の操作を全ての要素のすべての辺について行う（ステップＢ２１０，Ｂ２１１）。その結果、本例では全ての要素の全ての辺が輪郭線として抽出される。
【０１１１】
なお、ここで登録された辺はすべて重複している。すなわち各辺は、辺を境界線として持つ隣接する２つの要素でそれぞれ登録される。この重複は、各辺について既に輪郭線として登録されたかどうかをフラグを設けてチェックすることで容易に回避することができる。
ここでは、３次元要素からなる分割モデルから輪郭線を抽出する場合について説明した。しかし、これは２次元要素（膜状要素）からなる３次元形状のモデルの場合についても適用可能である。すなわち、図１６における抽出したフリーフェイスの代わりに本２次元要素（膜状要素）を使用すればよい。なおこの場合は、ステップＢ２０９において角度θの判定としてθが零に近い場合にも輪郭線として登録しないようにする必要がある。すなわち、ステップＢ２０９の条件に代えて、次式（１２）を満たすとき、隣接する２次元要素の境界線を輪郭線として登録する。
【０１１２】
δ＜θ＜（π−δ）、または（π＋δ）＜θ＜（２π−δ）      （１２）
これは、３次元要素のフリーフェイスの場合、上で述べたように、モデルに対して法線方向を統一できるのに対して（上記例ではモデルの内側に向くように統一した）、一般的な２次元要素の場合は統一できないことによるものである。
また、式（１２）を判定条件に用いて輪郭線を抽出する方法は、３次元要素と２次元要素が混在したモデルについても同様に適用できる。すなわち、まず３次元要素からフリーフェイスを抽出し、抽出したフリーフェイスに２次元要素を加えて、全体を２次元要素とみなして処理を行えばよい。
【０１１３】
なお発明者の経験から、ここで使用した許容値δの値は、
π／１８０≦δ≦π／１８                                    （１３）
とすることで、ほとんどの分割モデルに対して妥当な輪郭線を抽出できることがわかっている。そこで、本許容値δは、デフォルト値として式（１３）の範囲の値を設定しておき、プログラム使用中に、ユーザが任意の値に変更できるようにするとよい。ユーザが任意に変更できるようにすることにより、どのようなモデルに対しても妥当な輪郭線を抽出できるようになる。
【０１１４】
（実施例５）
実施例１では、分割モデルの全セグメントから複数の要素に共有されるセグメントをとり除くことにより、複数の要素に共有されないセグメントを抽出した。本方法を応用すれば、分割モデルから複数の要素に共有されるセグメントも容易に抽出することができる。そしてこれはセグメントを要素自身に置き換えることにより重複した要素も容易に抽出できる。重複した要素を抽出することは、分割モデルのチェック、または表示のための前処理として有効である。例えば実施例４において、輪郭線は２度重複して登録されることを述べた。そこで、本輪郭線を描画する前に重複するものを抽出し、１つにまとめれば同じ線を２度書きすることなく表示することができる。ここでは、このような重複した要素を抽出して１つにまとめる方法について説明する。
【０１１５】
重複した要素を除去して、重複をなくすための処理の流れは図１とほぼ同様である。すなわち、図１におけるセグメントリストを要素リストにし、要素番号だけを登録するようにする。また、ステップＡ１０６において、該当する要素リストから重複する要素を除去して重複をなくす。ステップＡ１０７で、すべての指標値についてチェックを終了後、要素リストに残った要素が重複していない要素である。
【０１１６】
本処理を図２３の分割モデルに要素Ｅ２と同一の要素Ｅ３を付加したモデルについて行った場所について具体的に説明する。
（１）ステップＡ１０１〜Ａ１０３によって、要素リストと指標テーブルとを作成する。作成したリストとテーブルを図１９に示す。指標値は要素を構成する節点の番号の和であり、要素リストには要素番号だけを登録している。
【０１１７】
（２）チェック対象の指標値として１〜１２を設定した場合には、該当数が１以下であることからなにも行われない（ステップＡ１０４，Ａ１０５，Ａ１５２）。
（３）チェック対象の指標値として１３をステップＡ１０４で設定する。ステップＡ１０５では、該当数が２であることから、要素リストの２，３行目の要素について節点を比較する。その結果、この２つは同一であることが判明し、ステップＡ１０６で、２つのうちいずれかを要素リストから除去する（ここではＥ３を除去）。
【０１１８】
（４）指標値１４についても同様にチェックを行うが該当数が零であることから何も行われない。
以上の結果、要素Ｅ１とＥ２とが重複した要素を１つにまとめた結果として要素リストに残る。
ここでは、重複した要素を１つにまとめることにより、すべて重複しない要素として結果を求めたが、本方法を用いることにより、重複する要素の抽出、重複していない要素の抽出等も容易に行えることは明かである。
【０１１９】
なお、実施例においては、有限差分法，有限要素法及び境界要素法に使用される要素について説明したが、本発明はこれらと同様な構造を有するデータに対して適用しうることは明らかである。また、本発明は、複数の機器から構成されるシステムに適用しても、１つの機器から成る装置に適用しても良い。また、本発明はシステム或は装置にプログラムを供給することによって達成される場合にも適用できることは言うまでもない。
【０１２０】
【発明の効果】
以上の説明から明らかなように、本発明によれば、少量のメモリしか搭載されていない計算機でも大規模な分割モデルからセグメントを抽出することが出来、輪郭線が忠実に表示できるようにする、またモデル中の任意の点を内含する要素を高速に抽出する有限要素分割モデルから辺，面，要素を抽出する方法及びその装置を提供できる。
【０１２１】
更に詳細には、以下のような効果が得られる。
本発明によれば、セグメントリストに必要なメモリを１セグメント当たり１整数分で済ますことができた。また指標テーブルについても同様に１指標値当たり１整数分でよくなった。その結果全体として使用メモリを大幅に削減でき、メモリをあまり搭載していない計算機でも、大規模な分割モデルからセグメントを抽出できるようになった。例えば、６面体要素からなる１００万要素、１００万節点の分割モデルからフリーフェイスを抽出するために、従来は２５６Ｍバイトのメモリを要していたが、本発明により４０Ｍバイトで済むようになった。
【０１２２】
また、本発明によれば、同じ指標値を持つセグメントの数が多い場合も問題がなくなった。これは、式（６）のβをあらかじめ大きめに設定しておくことで、容易に対応できるからである。
また、本発明によれば、分割モデルから隣接する要素を、検索対象を同一の指標値を持つセグメントに限定することにより、非常に高速に抽出できるようになった。
【０１２３】
また、本隣接要素の抽出方法を利用すれば、分割モデル中に存在する点を内含する要素も高速に抽出できる。これは高速に隣接する要素を抽出できることから、目的となる要素に向かって、モデル中を高速にほぼ直線的に突き進んで検索を行うことができるようになったことによるものである。ｎ個の要素からなる分割モデルの場合、従来ｎ／２回の内含チェックを行っていたものが、ｎの３乗根の回数で済むようになった。
【０１２４】
また、モデルに忠実な輪郭線を高速に得られるようにもなった。この忠実性は、輪郭線を、隣接するフリーフェイス間の角度から求めるようにしたことに起因する。例えば、図１９のモデルに対して、従来は図２２で示したフリーエッジを輪郭線として表示していたが、本発明により図２２における線分１−４，１−３，３−１も輪郭線として抽出できるようになった。また本高速性は隣接するフリーフェイスを高速に求めることができるようになったことに起因する。
【０１２５】
また本発明を用いて、分割モデルから重複した要素を高速に抽出することもできるようになった。
【図面の簡単な説明】
【図１】実施例１の処理の流れを示す図である。
【図２】図１のＡ１０１の詳細な処理の流れを示す図である。
【図３】図１のＡ１０２の詳細な処理の流れを示す図である。
【図４】図１のＡ１０３の詳細な処理の流れを示す図である。
【図５】実施例１の処理中に作成するリストとテーブルの形式である。
【図６】実施例１のセグメントを説明するための図である。
【図７】実施例１のセグメントを説明するための図である。
【図８】実施例１でセグメントを面とする場合の具体的処理を説明するための図である。
【図９】実施例１でセグメントを面とする場合の具体的処理を説明するための図である。
【図１０】実施例１でセグメントを辺とする場合の具体的処理を説明するための図である。
【図１１】実施例１でセグメントを辺とする場合の具体的処理を説明するための図である。
【図１２】実施例２の処理の流れを示す図である。
【図１３】実施例２でセグメントを面とする場合の具体的処理を説明するための図である。
【図１４】実施例２でセグメントを面とする場合の具体的処理を説明するための図である。
【図１５】実施例３の処理の流れを示す図である。
【図１６】実施例４処理の流れを示す図である。
【図１７】実施例４の具体的処理を説明するための図である。
【図１８】実施例４の具体的処理を説明するための図である。
【図１９】実施例５を説明する図である。
【図２０】本実施例を実現する計算機の構成を示すブロック図である。
【図２１】従来技術を説明する処理の流れ図である。
【図２２】従来技術の処理中に作成するリストとテーブルとの形式を示す図である。
【図２３】従来技術の具体的処理を説明するための図である。
【図２４】従来技術でセグメントを面とする場合の具体的処理を説明するための図である。
【図２５】従来技術でセグメントを辺とする場合の具体的処理を説明するための図である。
【図２６】従来技術の具体的処理の結果を説明するための図である。
【符号の説明】
Ｅ１〜Ｅ３，Ｆ１〜Ｆ６  要素
▲１▼〜▲６▼，１〜６  局所セグメント番号
Ｐ０  〜Ｐ２  ，Ｐｅ    分割モデル中の点
１６１  表示部
１６２  ＣＰＵ
１６３  ＲＡＭ
１６３−１  セグメントリスト領域
１６３−２  指標テーブル領域
１６３−３  指標値カウンタ領域
１６３−４  要素テーブル領域
１６４  入力部
１６５  ＲＯＭ
【図１】
0003624015.tif 000008
【図２】
0003624015.tif 000009
【図３】
0003624015.tif 000010
【図４】
0003624015.tif 000011
【図５】
0003624015.tif 000012
【図６】
0003624015.tif 000013
【図７】
0003624015.tif 000014
【図８】
0003624015.tif 000015
【図９】
0003624015.tif 000016
【図１０】
0003624015.tif 000017
【図１１】
0003624015.tif 000018
【図１２】
0003624015.tif 000019
【図１３】
0003624015.tif 000020
【図１４】
0003624015.tif 000021
【図１５】
0003624015.tif 000022
【図１６】
0003624015.tif 000023
【図１７】
0003624015.tif 000024
【図１８】
0003624015.tif 000025
【図１９】
0003624015.tif 000026
【図２０】
0003624015.tif 000027
【図２１】
0003624015.tif 000028
【図２２】
0003624015.tif 000029
【図２３】
0003624015.tif 000030
【図２４】
0003624015.tif 000031
【図２５】
0003624015.tif 000032
【図２６】
0003624015.tif 000033