JPH096991A - 有限要素分割モデルから辺，面，要素を抽出する方法及びその装置 - Google Patents

Abstract

(57)【要約】 【目的】 大規模な有限要素分割モデルから辺，面，要
素を抽出することが出来、輪郭線が忠実に表示できるよ
うにする、またモデル中の任意の点を内含する要素を高
速に抽出する方法及びその装置を提供することを目的と
する。 【構成】 各要素と該要素を構成する節点とが対応して
記憶されている場合に、１つの辺，面または要素を１つ
のセグメントと見なして、有限要素分割モデルから前記
セグメントを抽出する際に、前記セグメントに対して前
記セグメントを構成する節点の組み合わせを特徴付ける
指標値をつけ、同じ指標値を持つセグメントの情報が連
続に並んだセグメントリスト（図５の（ａ））と、前記
指標値とセグメントリスト上の位置とを関連づける指標
テーブル（図５の（ｂ））とを作成し、前記セグメント
リストと指標テーブルとに基づいて、同じ指標値を持つ
セグメントを抽出して、節点情報を得るようにした。

Description

【発明の詳細な説明】

【０００１】

【産業上の利用分野】本発明は、有限要素解析，境界要
素解析等に使用する有限要素分割モデルから特定の辺，
面または有限要素（ここではこれらを総称し、セグメン
トと呼ぶ）を抽出する際に有用なものであり、有限要素
分割モデルの輪郭線，表面，重複要素の抽出、モデル中
で隣接している要素の抽出、モデル中の任意点に対して
それを内含する要素の抽出等に利用できる有限要素分割
モデルから辺，面，要素を抽出する方法及びその装置に
関するものである。

【０００２】

【従来の技術】近年計算機の急速な発達と共に、有限差
分法，有限要素法，境界要素法等の数値解析が頻繁に行
われるようになった。これらの数値解析法では、一般に
解析モデルを多数の有限要素に分割した有限要素分割モ
デルが使用される（ここでは、有限差分法，有限要素
法，境界要素法等に使用する分割モデルをまとめて有限
要素分割モデルと呼ぶ）。最近では計算機性能の向上に
より、３次元要素分割モデルが一般的に使用されてい
る。

【０００３】本３次元有限要素分割モデルの外形を表示
する際に、モデルの表面を抽出することが多々ある。こ
れはすべての要素を表示すると時間がかかることによる
ものであり、３次元モデルをソリッドとして表示するか
わりに、表面だけを隠面処理して表示することにより時
間短縮をはかろうとするものである。一般に有限要素モ
デルの表面は、複数の要素に共有されない面（フリーフ
ェイスと呼ぶ）と同一であり、従って表面の抽出は本フ
リーフェイスの抽出によってなされる。

【０００４】また、表面の表示と同様に、モデルの輪郭
線を表示することも多い。ここで輪郭線とはモデル表面
の稜線であり、細かくは要素の辺（要素を構成する面の
境界線）から構成されるものである。これは表示を表面
だけを用いて行うよりも更に簡略化したものであり、ｎ
個の要素からなる３次元モデルの場合、単純に考えれば
その表面の数はｎの平方根、輪郭線の数はｎの３乗根の
オーダーとなる。一般に輪郭線は、複数の要素に共有さ
れない辺（フリーエッジ）によって代用される。

【０００５】これらの簡略化した表示の特徴は短時間に
表示を行えることであり、視点位置を決定するための試
行錯誤の段階における表示等において有効である。ま
た、時系列の解析結果のアニメーション表示において
は、短時間に何枚もの図を表示する必要があるが、これ
を表面、輪郭線を用いることで短時間に行えるようにし
たという例もある（特開平４−３４６１７８号）。

【０００６】また、本輪郭線は、要素分割モデルに含ま
れる要素の不整合、例えば、要素の抜け（分割モデルが
要素で完全に満たされていない）、浮き節点（要素の辺
上に節点がある）、節点の重複（同一点に節点が２つ以
上ある）等の発見にも使用される。これは輪郭線を表示
して、モデルの内部に存在する輪郭線を調べることにな
ってなされる。本来、輪郭線は分割モデルの表面だけに
表示されるものであるが、これらの不整合により輪郭線
がモデルの内部に生じるからである。

【０００７】図２０にフリーフェイス，フリーエッジを
抽出して表示する計算機システムのブロック図を示す。
図中、符号１６１は表示部であり、１６２は中央処理装
置（ＣＰＵ）、１６３はメモリ、１６４はデータの入力
部である。通常１６４からデータを入力し、１６２，１
６３を用いて処理を行い、結果を１６１に表示する。な
お、１６３−１はセグメントリスト，１６３−２は指標
テーブルであり、１６３−３は指標値カウンタである。
なお、１６３−４は要素テーブルであるが、これは後述
する本発明の実施例のためのものであり、従来の技術に
属するものではない。

【０００８】上述のように、フリーフェイスは要素の
面、フリーエッジは要素の辺からなるものであり、これ
らの面，辺は共に要素を構成する部品と考えることがで
きる。そこで、ここではこれらの部品をまとめてセグメ
ントと呼ぶことにする。フリーフェイス，フリーエッジ
等のセグメントは、複数の要素に共有されているセグメ
ントを除去するという方法によって抽出することができ
る。本共有セグメントを高速に除去する方法としては、
様々なアルゴリズムが考案されており、以下のようなも
のがある。

【０００９】まず第１の方法は、分割モデルをいくつか
の領域ごとに分割・グループ化するものである。すなわ
ち、モデルを包含する１つの直方体領域を想定し、その
領域をいくつかの部分領域に分ける。そして、各部分領
域ごとにその内部及び境界上の要素をグループ化する。
セグメントが共有されているかどうかの判定を行う際に
は、同じ領域内（同じグループ）の要素のセグメントの
みを対象とする。本方法は、要素が領域内に均一に分散
している場合には効果があるが、一部分に集中している
ような場合には効果が小さいため、一般的にはあまり用
いられない。

【００１０】第２の方法は、１回のチェックに要する時
間を減らす工夫である。本方法は、“中田他：３次元分
割図作成アルゴリズムの改良、日本シミュレーション学
会第９回シミュレーション・テクノロジー・コンファレ
ンス，６１頁−６４頁（１９９０）”に、高速にフリー
フェイスを抽出する方法として述べられているものであ
り、１回のチェックに要する時間を短縮したものであ
る。すなわち、セグメントを構成する節点番号の最大値
をそのセグメントの指標とし、共有されているかどうか
の判定の際に、その指標が一致しない場合には即座に同
一ではないと判定する。しかし、本方法もチェック回数
を減らすということに関しては対処がなされておらず、
あまり用いられていない。

【００１１】第３の方法は、各セグメントに対してセグ
メントを構成する節点の和を指標とし、チェックを行う
際には同一の指標を持つセグメントだけをチェックする
ものである。本方法のアルゴリズムは、特開平４−３４
６１７８号にフリーフェイス，フリーエッジを抽出する
方法として記載されており、容易にプログラミングでき
ること、効果が分割状態に依存しないことから、広く使
用されている。

【００１２】図２１に本方法の流れ図を示す。以下、図
２１に従って複数の要素に共有されないセグメントを抽
出する過程を説明する。複数の要素に共有されないセグ
メントの抽出に先だって、まずセグメントリストと指標
テーブルとを作成する（ステップＢ７０１，Ｂ７０
２）。セグメントリストと指標テーブルとを次に説明す
る。

【００１３】セグメントリストはすべてのセグメントを
登録したものであり、図２２の（ａ）に示すように、リ
スト番号とセグメント節点列との２つの項目からなる。
ここで、リスト番号は１から始まる連続な整数値であ
り、本リストの行番号を表す番地である。セグメント節
点列は各セグメントを構成する節点の番号を並べたもの
である。従って、図２２の（ａ）のセグメントリストで
はセグメントを各要素ごとに独立に登録する。従って、
本リストの行数は次式（１）となる。

【００１４】 ここで、Ｓｉはｉ番目の要素を構成するセグメントの
数、ｅｌｅｍは要素数である。

【００１５】指標テーブルは、図２２の（ｂ）に示した
指標値とリスト番号列との２つからなる。指標値の項は
セグメントの指標値に対応するもので、１から始まる連
続な整数値であり、本テーブルの行番号を表す番地であ
る。リスト番号列は、セグメントリストのリスト番号を
示すものである。リスト番号列は、同じ指標値を持つセ
グメントの数だけ用意しておく必要がある。セグメント
の指標値がわかれば、本テーブルを用いてその指標値を
持つセグメントがセグメントリストのどこに（何番地）
登録されているかを知ることができる。本テーブルの行
は、指標値がとる可能な値の数だけ用意しておかなくて
はならない。セグメントを構成する節点番号の和の最大
は、次式（２）である。

【００１６】 ここで、Ｎはモデルの節点数、ｍは１つのセグメントを
構成する節点の数である。

【００１７】セグメントの抽出にあたって、まず、図２
１のステップＢ７０１でセグメントリストを作成する。
これは各要素のセグメントをセグメントリストに順に登
録していくことによって行う。次に、ステップＢ７０２
で、ステップＢ７０１で作成したセグメントリストの個
々のセグメントの指標値を求め、指標テーブルの該当す
る指標値の行にセグメントリストにおけるリスト番号を
登録する。以上で、セグメントリストと指標テーブルと
の作成を完了する。

【００１８】複数の要素に共有されていないセグメント
の抽出は、ここで作成した指標テーブルのリスト番号列
から同じ節点からなるセグメントを除去することによっ
て行われる。ステップＢ７０３〜ステップＢ７０６は同
じ節点からなるセグメントの除去を行う過程である。ま
ず、ステップＢ７０３にて除去対象とする指標値（ｋ）
を設定する。そして指標テーブルのｋ行目に登録されて
いるセグメントの数を調べ、１つ以下ならばそのセグメ
ントは複数の要素に共有されていないと判定し、ステッ
プＳＢ７０６へ行く。同じ指標値を持つセグメント数が
２つ以上存在したならば、ステップＢ７０５でｋ行目の
セグメントの中で同一のもの（同じ節点の組み合わせか
らなるセグメント）を指標テーブルから除去する。以上
述べたように各セグメントを構成する節点はリスト番号
列に対応したセグメントリストのリスト番号を参照する
ことによって得ることができ、ステップＢ７０５の処理
はここで得た節点番号を比較することによって行う。

【００１９】ステップＳ７０６では、本操作をすべての
指標値について行ったことを確認する。全指標値のチェ
ックが完了していなければ、ステップＢ７０３に戻って
次の指標値のチェックに移る。全指標値のチェックが完
了していれば、複数の要素に共有されているセグメント
の除去処理を完了する。その時に指標テーブル中に残っ
ているセグメントが複数の要素に共有されていないセグ
メントである。

【００２０】以上の操作を要素分割モデルからフリーフ
ェイスを抽出する場合を例にあげて、具体的に説明す
る。図２３は２つの３次元要素からなる分割モデルであ
る。図中、黒丸は節点を示し、近傍の番号は節点番号を
示す（以後同様）。要素Ｅ１は節点１−２−３−４、要
素Ｅ２は節点３−１−４−５からなる４面体要素であ
る。要素Ｅ１は節点１−２−３，１−４−２，２−４−
３，３−４−１、要素Ｅ２は節点３−１−４，３−５−
１，１−５−４，４−５−３のそれぞれ４つの面からな
る。

【００２１】本分割モデルからフリーフェイスを抽出す
る過程を、図２１の流れに沿って説明する。 （１）ステップＢ７０１では、まず、要素Ｅ１の面の構
成節点を順に図２２の（ａ）のリストに登録する。本操
作を要素Ｅ２の面についても行うことにより、図２４の
（ａ）のセグメントリスト（面リスト）を得る。

【００２２】（２）次に、ステップＢ７０２では、前項
で得た面リストの各面の指標値（面を構成する節点の番
号の和）をそれぞれ計算し、指標テーブルのその指標値
の行に面リストのリスト番号をそれぞれ登録する。すべ
ての面を登録することにより図２４の（ｂ）を得る。 （３）ステップＢ７０３，Ｂ７０４，Ｂ７０５では、指
標テーブルから、重複した（同じ節点番号からなる）面
を示すリスト番号を除去する。これは同じ指標値をもつ
面（指標テーブルの同じ行）の中で同じ節点の組み合わ
せからなるものを除去することによって行う。本例では
指標値８，９以外については、すべて登録されている面
が１つ以下であることから何も行わない。指標値８，９
はそれぞれ２つの面が登録されていることから、２つの
面の節点番号を調べ（それぞれリスト番号４，５および
３，６を参照する）、２つの面が同一であるかどうかを
チェックする。その結果、指標値８の２つの面が共に節
点１，３，４で構成されていることから２つの面は同一
であると判定し、リスト番号４，５を指標テーブルから
除去する。

【００２３】以上の処理の結果、指標テーブルに残った
面（リスト番号１，２，３，６，７，８の面）がフリー
フェイスである。要素分割モデルからフリーエッジを抽
出するには、以上のフリーフェイス抽出過程における面
を辺に単純に置き換えるだけでよい。次に、図２３の分
割モデルからフリーエッジを抽出する過程を説明する。

【００２４】（１）図２１のステップＢ７０１では、ま
ず、要素Ｅ１の辺の構成節点を順に図２２の（ａ）のリ
ストに登録する。本操作を要素Ｅ２の辺についても行う
ことにより、図２５の（ａ）のセグメントリスト（辺リ
スト）を得る。 （２）次に、ステップＢ７０２では、本リストの各辺の
指標値（辺を構成する節点の番号の和）をそれぞれ計算
し、指標テーブルの対応する行に辺リストのリスト番号
をそれぞれ登録する。すべての辺を登録することによ
り、図２５の（ｂ）を得る。

【００２５】（３）ステップＢ７０３，Ｂ７０４，Ｂ７
０５では、本指標テーブルから、同じ辺を示すリスト番
号を除去する。本例では指標値３，８，９については登
録されている辺が１つ以下であることから何も行わな
い。指標値４，５，６，７はそれぞれ２つ以上の辺が登
録されていることから、それぞれの指標値内で辺の節点
番号を調べ、重複した辺があるかどうかをチェックす
る。その結果、指標値４，７の２つの辺および指標値５
の２つの辺（リスト番号６，８）が同一であると判定さ
れ、これらのリスト番号を指標テーブルから除去する。

【００２６】以上の処理の結果指標テーブルに残った辺
（リスト番号１，２，４，１０，１２，１１の辺）がフ
リーエッジである。図２６はここで抽出されたフリーエ
ッジを描画したものである。なお、図２６中の破線は図
２３で破線で示されていたものをそのまま表示したもの
である。また、要素分割モデル中に存在する点につい
て、点がどの要素の内部に位置しているかを知る必要が
しばしばある。これは、その点における場を計算する場
合等に生じるものであり、点を含む要素を抽出すること
により、その要素の解析結果から容易にその点の場を計
算することができる。

【００２７】従来、このような点を含む要素の抽出は、
全ての要素を対象にして内含するかどうかをチェックす
ることにより行っていた。その結果、最悪の場合には、
要素数だけのチェックを必要としていた。ｎ個の要素か
らなる分割モデルの場合、本チェック回数の平均はｎ／
２である。

【００２８】

【発明が解決しようとする課題】しかしながら、従来の
方法で用いられていたセグメントリストと指標テーブル
とは、データの持ち方に無駄が多くメモリを無駄に消費
してしまうという欠点があった。以下、この欠点につい
て説明する。まず、セグメントリストでは各セグメント
に対してセグメントを構成する節点の数だけメモリを必
要とした。例えば図２４の（ａ）の面リストの場合、１
つのセグメントに対して３つの整数値（節点番号）を登
録する必要がある。従って、セグメントを構成する節点
の数が多い場合には大量のメモリが必要となっていた。
また、計算機の都合上、一般に各セグメントごとに用意
しておくメモリは同じである必要がある。従って、セグ
メントごとに節点の数が異なる場合には、その最大の数
にあわせてメモリを用意しておく必要があった。その結
果、最大の節点数よりも少ない節点で構成されるセグメ
ントに対しては、メモリが無駄になっていた。

【００２９】一方、指標テーブルでは、各指標値に対応
して登録されるセグメントの数が予めわからないため、
全指標値に対して常に大きめのメモリを用意しておく必
要があった。例えば図２４の（ｂ）の例では１つの指標
値に５つのリスト番号まで登録できるように準備してい
たが、実際には最大でも２つ（指標値８，９）しか用い
られていない。また、同図からわかるように、各指標値
に登録されるセグメントの数は異なる。それに対して、
セグメントの場合と同様に、全指標値に対して用意して
おくメモリは同じである必要がある。従って、対応する
セグメントが少ない指標値についてはメモリが無駄にな
る。

【００３０】このように従来の方法ではメモリを無駄に
消費した。その結果、大規模なモデル（要素数の多いモ
デル）の場合には膨大なメモリを必要とし、少量のメモ
リしか搭載されていない計算機では処理できなかった。
次に、例えば、６面体要素からなる１００万要素、１０
０万節点の分割モデルについて、フリーフェイスを抽出
する際に、従来のセグメントリストと指標テーブルとが
使用するメモリを計算し、このことを具体的に説明す
る。

【００３１】まず、面リストが必要とするメモリを計算
する。各要素を構成する面は４辺形であるため、セグメ
ント情報は１セグメント当たり、４整数分（１整数当た
り４バイトとすると１６バイト必要、以下同様）のメモ
リを必要とする。リストの行数は、１要素が６つの面か
らなることから、式（１）を用いて６００万行である。
従って、セグメントリストに要するメモリは９６Ｍ（１
６×６００万）バイトである。

【００３２】次に、指標テーブルが必要とするメモリを
計算する。発明者の経験から、一般に１つの分割モデル
中で同じ指標値を持つセグメントの個数は最大８〜１０
個であるとわかっている。そこで、本テーブルで、同じ
指標値を持つセグメント（面）を１０個まで登録できる
ようにすると、１指標値当たりの使用メモリは４０バイ
ト（４バイト×１０個）となる。テーブルの行数は、式
（２）から約４００万（正確には（４００万−３））行
である。従って、指標テーブルに要するメモリは約１６
０Ｍ（４０×４００万）バイトである。

【００３３】この結果、本分割モデルに要するメモリは
合計２５６Ｍバイト（９６Ｍ＋１６０Ｍ）となる。この
メモリ容量は現在の計算機をもってしても大容量であ
り、一般的な計算機では処理が不可能である。また、従
来の指標テーブルでは同じ指標値をもつセグメントの数
が制限範囲を越えた場合には対応できなかった。例え
ば、図２４の（ｂ）の例では同じ指標値を持つセグメン
トが６つ以上になると対応できなかった。このことは、
上で同じ指標値を持つセグメントの個数は最大８〜１０
個であるといったことと矛盾するが、上で説明したのは
あくまでも一般的な話であり、１０以上になることもあ
りえることに基づく。

【００３４】また、従来の輪郭線をフリーエッジで代用
して表示する方法には、本来輪郭線として表示されるべ
きなのに表示されない場合があるという欠点があった。
例えば図２６に示した輪郭線には、節点１−４，４−
３，３−１からなる線もこれらの線がモデルの稜線であ
ることから表示されるべきなのに表示されていない。ま
た、従来の点を内含する要素を抽出する方法では、各要
素について点を内含するかどうかのチェックを行わなけ
ればならず、点が大量にある場合には抽出のために長時
間を要していた。

【００３５】本発明は、このような課題に対処すること
を目的になされたものであり、少量のメモリしか搭載さ
れていない計算機でも大規模な分割モデルからセグメン
トを抽出することが出来、輪郭線が忠実に表示できるよ
うにする、またモデル中の任意の点を内含する要素を高
速に抽出する有限要素分割モデルから辺，面，要素を抽
出する方法及びその装置を提供することを目的とする。

【００３６】

【課題を解決するための手段】上記課題を解決するため
に、本発明の有限要素分割モデルから辺，面，要素を抽
出する方法は、各要素と該要素を構成する節点とが対応
して記憶されている場合に、１つの辺，面または要素を
１つのセグメントと見なして、有限要素分割モデルから
前記セグメントを抽出する際に、前記セグメントに対し
て前記セグメントを構成する節点の組み合わせを特徴付
ける指標値をつけ、同じ指標値を持つセグメントの情報
が連続に並んだセグメントリストと、前記指標値と前記
セグメントリスト上の位置とを関連づける指標テーブル
とを作成し、前記セグメントリストと前記指標テーブル
とに基づいて、同じ指標値を持つセグメントを抽出し
て、抽出されたセグメントを構成する節点情報を得るよ
うにしたことを特徴とする。

【００３７】ここで、前記セグメントリストに記憶され
る情報は、各セグメントを有する要素を特定する第１識
別子と、該セグメントが前記要素の何番目のセグメント
であるかを示す第２識別子とで表現される。また、前記
セグメントリストに記憶されるセグメントは、前記指標
値の大きい順または小さい順に並ぶ。また、前記第１識
別子に１つの要素を構成するセグメントの数以上の所定
の整数値を乗じ、これに前記第２識別子を加えることに
より、前記第１及び第２識別子を１つの整数値として記
憶する。また、前記指標テーブルの各指標値の情報は、
該指標値に該当するセグメントの個数と該セグメントが
記憶されるセグメントリストの先頭を指すポインタとで
表現される。また、前記ポインタに１０以上の整数値を
乗じ、これに前記セグメントの個数を加えることによ
り、前記個数及びポインタを１つの整数値として記憶す
る。

【００３８】更に、抽出したセグメントの内、同一の節
点からなるセグメントから構成される複数の要素を隣接
要素として抽出する。更に、前記同一の節点からなるセ
グメントを前記セグメントリストから除去することによ
り、前記セグメントリストには重複のないセグメントだ
けが残るようにする。又、本発明の有限要素分割モデル
から要素を抽出する方法は、有限要素分割モデル中の１
点Ｐ_e を内含する要素を抽出する方法であって、ある要
素Ｅ₀ に内含されている既知の点Ｐ₀ を始点として、２
点Ｐ_e とＰ₀ を結ぶ線分と交差する要素Ｅ₀ の面Ｆ₀ を
求め、要素Ｅ₀ と面Ｆ₀ を境界にして隣接する要素Ｅ₁
を求め、２点Ｐ_e とＰ₀ を結ぶ線分と交差する要素Ｅ₁
のＦ₀ 以外の面Ｆ₁ を求め、該面Ｆ₁ で要素Ｅ₁ と隣接
する要素Ｅ₂ を求めるという処理を繰り返し、隣接する
要素を辿っていくことにより、点Ｐ_e を内含する要素を
抽出することを特徴とする。

【００３９】又、本発明の有限要素分割モデルから辺を
抽出する方法は、３次元有限要素モデルからフリーフェ
イスを抽出し、該フリーフェイスを膜状要素の２次元要
素とみなして、隣接する２次元要素を抽出し、隣接する
２次元要素のなす角度θを求め、角度θの値が、許容値
をδとすると、０≦θ＜（π−δ）、または（π＋δ）
＜θ＜２πであるとき、前記２つの２次元要素の境界線
を輪郭線として抽出することを特徴とする。更に、抽出
したフリーフェイスに膜状要素の２次元要素からなる３
次元形状の分割モデルを加えて、隣接する２次元要素を
抽出し、角度θの値が、許容値をδとすると、δ≦θ＜
（π−δ）、または（π＋δ）＜θ＜２π−δであると
き、前記２つの２次元要素の境界線を輪郭線として抽出
する。

【００４０】又、本発明の有限要素分割モデルから辺，
面，要素を抽出する装置は、各要素と該要素を構成する
節点とを対応して記憶する手段と、１つの辺，面または
要素を１つのセグメントと見なして、前記セグメントに
対して前記セグメントを構成する節点の組み合わせを特
徴付ける指標値をつける手段と、同じ指標値を持つセグ
メントの情報が連続に並んだセグメントリストと、前記
指標値と前記セグメントリスト上の位置とを関連づける
指標テーブルとを作成する手段と、前記セグメントリス
トと前記指標テーブルとに基づいて、同じ指標値を持つ
セグメントを抽出して、前記各要素と該要素を構成する
節点との対応に基づいて、抽出されたセグメントを構成
する節点情報を得る手段とを備えることを特徴とする。

【００４１】ここで、前記セグメントリストに記憶され
る情報は、各セグメントを有する要素を特定する第１識
別子と、該セグメントが前記要素の何番目のセグメント
であるかを示す第２識別子とで表現される。また、前記
セグメントリストに記憶されるセグメントは、前記指標
値の大きい順または小さい順に並ぶ。また、前記第１識
別子に１つの要素を構成するセグメントの数以上の所定
の整数値を乗じ、これに前記第２識別子を加えることに
より、前記第１及び第２識別子を１つの整数値として記
憶する。また、前記指標テーブルの各指標値の情報は、
該指標値に該当するセグメントの個数と該セグメントが
記憶されるセグメントリストの先頭を指すポインタとで
表現される。また、前記ポインタに１０以上の整数値を
乗じ、これに前記セグメントの個数を加えることによ
り、前記個数及びポインタを１つの整数値として記憶す
る。

【００４２】

【作用】かかる構成において、セグメントリスト中で、
セグメントは構成する節点の数に関わらず要素番号と局
所セグメント番号との２つで表現される。また、指標テ
ーブルも同一の指標値を持つセグメントの数に関わらず
該当数と先頭リスト番号との２つで表現される。その結
果、セグメントリスト，指標テーブル中で、それぞれ１
セグメント，１指標値当たりに消費されるメモリはそれ
ぞれ整数２つ分となり、メモリを有効に使えるようにな
る。また、輪郭線はフリーフェイス間の稜線として抽出
されることから、すべての輪郭線がもれなく抽出される
ようになる。また、点を内含する要素の抽出は、隣接す
る要素を辿っていくことにより、ほぼ直線的に検索を進
めて目的とする要素に到達できるようになり、短時間で
目的とする要素に行き着く。

【００４３】

【実施例】以下、本発明を実施例に従って詳細に説明す
る。図２０に有限要素分割モデルからフリーフェイス，
フリーエッジを抽出して表示する計算機システムのブロ
ック図を示す。図中、１６１は有限要素分割モデルある
いは抽出されたフリーフェイス，フリーエッジを表示す
る表示部であり、１６２は演算・制御用の中央処理装置
（ＣＰＵ）、１６３は補助記憶用のＲＡＭであり、セグ
メントリストを記憶するセグメントリスト領域１６３−
１，指標テーブルを記憶する指標テーブル領域１６３−
２，指標値のカウント値を記憶する指標値カウンタ領域
１６３−３，各要素を定義する節点の列を記憶する要素
テーブル領域１６３−４を含む。１６４は有限要素分割
モデルのデータあるいは指示命令を入力する入力部、１
６５はＣＰＵ１６２の処理手順を格納するＲＯＭであ
る。通常、入力部１６４からデータ及び指示を入力し、
指示に対応してＲＯＭ１６５に格納された手順に従いＣ
ＰＵ１６２で有限要素分割モデルからのフリーフェイ
ス，フリーエッジの抽出を行い、結果を表示部１６１に
表示する。

【００４４】（実施例１）図１〜図４に、本実施例によ
る複数の要素に共有されないセグメントを抽出する処理
の流れを、図５に本実施例で作成するセグメントリスト
と指標テーブルとの形式を示す。本実施例では、セグメ
ントリストを図５の（ａ）に示すようにリスト番号，要
素番号及び局所セグメント番号の３項目で構成する。本
リストは、リストに登録されるセグメントの順序及びリ
スト内でのセグメントの表現法を除いては、従来のセグ
メントリストと同じである。従って、本リストの行数は
式（１）となる。以下に、本リストと従来のリストとの
違いを説明する。

【００４５】まず、本リストでは、セグメントの指標値
（従来と同じセグメントを構成する節点番号の和）が同
じものが連続のリスト番号に登録されているようにす
る。例えば、リスト番号に対してセグメントは指標値の
小さい順に登録されるようにする。また、本リストでは
１つのセグメントを要素番号と局所セグメント番号の２
つで表現する。このことについて詳しく説明する。一般
に要素分割モデルの要素を構成する節点番号の列は、要
素形状に対応して予め定められた一定の規定に従ってメ
モリ登録される。従って、要素内のすべてのセグメント
について、セグメントを構成する節点の組み合わせはメ
モリに登録されている節点番号列から一義的に決定され
る。そこで、予め各要素形状に対してすべてのセグメン
トに番号（局所セグメント番号と呼ぶ）を振っておけ
ば、そのセグメント番号からそのセグメントを構成する
節点列を一義的に求めることができる。

【００４６】このことを、図６，図７を用いて具体的に
説明する。図６は節点ｎ₁ 〜ｎ₆ からなる３角柱形状を
した要素である。本３角柱要素において、常に節点はメ
モリにｎ₁ −ｎ₂ −ｎ₃ −ｎ₄ −ｎ₅ −ｎ₆ の順に登録
されるものとする。すなわち、節点は底面の３角形、上
面の３角形の順に登録され、１番目と４番目に登録され
る節点は１本の辺でつながっている。また、底面と上面
で節点のまわる（登録される）方向は同じである。する
と、本要素を構成する面は図７の（ａ）に示した５つで
ある。そこで、５つの面に対して図７の（ａ）に示した
ような１〜５の面番号を振る。図６に図７の（ａ）で割
り振った５つの面の番号を示す。

【００４７】ここで、ｎ₁ 〜ｎ₆ を一般的な節点番号と
考えると、図７の（ａ）の各面はメモリ上でｎ₁ 〜ｎ₆
に対応した場所に登録されている節点から構成される面
とみなすことができる。例えば、面番号１はメモリ上で
１〜３番目に登録されている節点から構成される面とみ
なすことができる。従って、どのような３角柱要素に対
しても面番号を指定することによって、その面を構成す
る節点の組み合わせを一義的に求めることができる。

【００４８】このことは辺についても同様であり、一般
的なセグメントに対しても同じである。図７の（ｂ）に
３角柱要素を構成する辺の節点列を示し、各辺に振った
辺番号を図６に示す。例えば、辺番号１はメモリ上で、
１，２番目に登録されている節点（ｎ₁ ，ｎ₂ ）から構
成される辺を示す。以上のように、すべてのセグメント
は、そのセグメントを持つ要素番号と局所セグメント番
号とを用いて表現でき、２つのデータからセグメントを
構成する節点を求めることができる。すなわち、どのよ
うなセグメントに対しても、セグメントリスト中ではこ
のような２つのデータを登録しておくだけで十分であ
る。

【００４９】次に、本実施例で使用する指標テーブルに
ついて説明する。指標テーブルは図５の（ｂ）に示すよ
うに、指標値，該当数，先頭リスト番号の３つの項目か
らなる。ここで、指標値は従来と同様に１から始まる連
続的な整数値であり、本テーブルの行番号を示す番地と
して使用する。また、番地をセグメントの指標値と対応
させる。従って、本テーブルの必要とする行数は従来と
同じ（２）式で与えられる。本実施例では、本テーブル
に各指標値を持つセグメントの数（該当数）と、及び指
標値に対応するセグメントリストの最初の番地を指す先
頭リスト番号とを登録する。

【００５０】このことについて、以下に詳しく説明す
る．以下の説明中で括弧内は図５との対応を示す。すで
に述べたように、本実施例のセグメントリスト中では、
同じ指標値をもつセグメントは連続のリスト番号に並ん
で登録されている。そして、本指標テーブルの該当数と
先頭リスト番号とは、各指標値を持つセグメントの数と
そのセグメントが登録されているリストの先頭の行番号
とを指す。従って、本セグメントリストと指標テーブル
とを使用することで、あるセグメントが与えられたと
き、そのセグメントと同じ指標値を持つセグメントを容
易に検索することができる。

【００５１】すなわち、まず与えられたセグメントの節
点から指標値を計算し（＝３とする）、指標テーブルの
その指標値の行を参照する。そして、そのセグメントと
同じ指標値を持つセグメントの数（該当数＝２）と先頭
リスト番号（＝１）を得る。次に、その先頭リスト番号
（＝１）からそれに続く該当数の数（＝２）だけの行の
セグメントリストを参照することで、個々のセグメント
がわかる。なお、ここでわかる個々のセグメントは、要
素番号と局所セグメント番号という形式で与えられる。
しかし、これは上で説明したように、メモリ上に登録さ
れている要素を構成する節点番号の列と、局所セグメン
ト番号の割り振り方を参照することで、容易にセグメン
トを構成する節点番号の列に変換することができる。

【００５２】図１に従って、セグメントリストと指標テ
ーブルとを作成する手順およびそれらを使用して複数の
要素に共有されないセグメントを抽出する処理の流れを
説明する。まず、図１のステップＡ１０１〜Ａ１０３で
セグメントリストと指標テーブルを作成する。ステップ
Ａ１０１の詳細を図２に示す。ステップＡ１０１の処理
は、各指標値を持つセグメントがそれぞれいくつあるか
を求め、指標テーブルの各指標値の該当数の項にその値
を登録するものである。本処理では、まずステップＡ１
１１で、指標テーブルの該当数の項をすべて零にする。
次に、ステップＡ１１２でセグメントの設定を行い、ス
テップＡ１１３で各セグメントについて指標値を計算す
る（＝ｋとする）。その計算毎に対応する指標値の該当
数の値（Ｍ_k）をステップＡ１１４にて新しい値（旧値
よりも１つ大きい値、すなわち（Ｍ_k＋１））に更新す
ることによって行う。

【００５３】図１のステップＡ１０２の詳細を図３に示
す。ステップＡ１０１の処理で各指標値を持つセグメン
トの数がわかったので、本処理では各セグメントがセグ
メントテーブルに連続して（空行なく）登録されるよう
にその先頭リスト番号を計算する。図３は、セグメント
リスト中でセグメントが指標値の小さい順に並ぶように
する手順である。ステップＡ１２１〜Ａ１２６の処理に
よって、指標テーブルのｋ行目の先頭リスト番号とし
て、１〜（ｋ−１）行目の該当数の加算値（すべてを足
し合わせた数）に１を加えた値がステップＡ１２３にて
登録される。

【００５４】図１のステップＡ１０３の詳細を図４に示
す。ここでは、ステップＡ１０１〜Ａ１０２で作成した
指標テーブルを使用してセグメントリストを作成する。
リスト作成にあたって、指標テーブルの各指標値にそれ
ぞれカウンタを用意し、ステップＡ１３１ですべてのカ
ウンタを零に初期化しておく。次に、ステップＡ１３
２，Ａ１３３で、各要素のセグメントについて指標値を
計算し（＝ｋとする）、ステップＡ１３４で指標テーブ
ルとカウンタとからその指標値の先頭リスト番号（Ｌ
_k ）およびカウンタ値（Ｍ_k ）を得る。ステップＡ１３
５では、その先頭リスト番号にカウンタ値を加えた番地
のセグメントリストの行（Ｌ_k ＋Ｍ_k 行目）にそのセグ
メントの要素番号と局所セグメント番号とを登録する。
その後、ステップＡ１３６で指標値ｋのカウンタの値
（Ｍ_k ）は１つ大きい値（Ｍ_k ＋１）に更新する。

【００５５】以上のようにして、すべてのセグメント
は、セグメントリストの１行目から空行なく指標値の小
さい順に並ぶ。なお、ここでは各指標値に対して新たに
カウンタ用のメモリを設けたが、これは指標テーブルの
該当数のメモリを一時的に代用してもよい。すなわち、
まずステップＡ１３１にて指標テーブルの該当数の項を
すべて零に初期化し、以後ステップＡ１３２〜Ａ１３７
の処理では、本該当数の項を上記カウンタとして用い
る。ステップＡ１３２，Ａ１３３の指標値計算後、ステ
ップＡ１３４では指標テーブルのｋ行目のカウンタ値
（該当数の項の値Ｍ_k ）と先頭リスト番号（Ｌ_k ）を得
る。ステップＡ１３５では、先頭リスト番号にカウンタ
値を加えた番地のセグメントリストの行（Ｌ_k ＋Ｍ_k 行
目）にセグメントを登録する。次に、ステップＡ１３６
で、セグメントを登録するたびにカウンタ値（該当数の
項の値）に１を加算して更新する。なお、カウンタ値
は、すべてのセグメントを登録した段階で、ステップＡ
１３１で初期化する前の該当数の値と同じとなる。従っ
て、このように該当数のメモリを一時的にカウンタとし
て代用しても、該当数を復元するための後処理は不要で
ある。該当数のメモリをカウンタとして代用することに
より、使用するメモリをセグメントリストと指標テーブ
ルとだけにすることができ、メモリの節約をはかること
ができる。

【００５６】なお、ここではセグメントを指標値の小さ
い順に並べたが、大きい順に並べてもよい。これは指標
テーブルの先頭リスト番号を作成する過程（図３）で、
該当数の値を指標値が最大の行から小さい方に順に加算
することによって達成される。具体的には図３のステッ
プＡ１２１の処理中で、“ｋ←（２）式の計算値”と
し、ステップＡ１２２を“ｋ←（ｋ−１）”、ステップ
Ａ１２６を“ｋ＞１”とすればよい。

【００５７】次に、作成したセグメントリストと指標テ
ーブルとを用いて、複数の要素に共有されないセグメン
トを抽出する過程を説明する。本過程は、図１のステッ
プＡ１０４〜Ａ１０７に示される。以下本図に従って説
明する。まず、ステップＡ１０４でチェックの対象とす
る指標値（ｋとする）を設定する。そして、ステップＡ
１０５にて指標テーブルのｋ行目の該当数をチェック
し、１つ以下なスば本指標値を持つセグメント中に同じ
ものはないと判定し、なにも行わずステスプＡ１０７の
処理に移る。２つ以上の該当するセグメントがあるなら
ば、指標スーブルから先頭リスト番号（Ｌ_k ）と該当数
（Ｍ_k ）を得る。そして、セグメントリストのＬ_k 行目
から始まるＭ_k 行のセグメント間で重複するものがない
かを、構成する節点を比較することでチェックする。

【００５８】もし重複するものがあれば、ステップＡ１
０６にてセグメントリストからその重複するセグメント
を両者とも除去する。除去はセグメントリスト中の該当
する要素番号を零や負の数等、要素番号としてありえな
い数値に更新することによって行う。ステップＡ１０４
〜Ａ１０６の操作をすべての指標値に対して終了したか
を、ステップＡ１０７でチェックし、終了していなけれ
ばステップＡ１０４に戻って処理を繰返し、抽出過程が
完了するまで行う。本過程終了後、セグメントリスト中
で妥当な要素番号を持つセグメントが、複数の要素に共
有されないセグメントである。

【００５９】以上の複数の要素に共有されないセグメン
トを抽出する過程を、実際の簡単な要素分割モデルから
フリーフェイスを抽出する過程を例にとって説明する。
図８は、従来技術の項で説明に用いたのと同じ、２つの
４面体要素からなる分割モデルである。ここで各要素を
構成する節点はそれぞれ次のようにメモリ上に登録され
ているものとする。

【００６０】Ｅ１：１−２−３−４ Ｅ２：３−１−４−５ ２つの要素の節点番号は同じ規則に従って登録されてい
る。すなわち１〜３番目に登録されている節点のまわり
方が、その方向に右ネジを回したときネジが要素の重心
方向に向かうようになっている。

【００６１】ここで、４面体要素を構成する面の番号を
要素Ｅ１の場合を例にとり、次のように定義する。 面１：節点１−２−３ （指標値：６（＝１＋２＋
３）） 面２：節点１−４−２ （指標値：７） 面３：節点２−４−３ （指標値：９） 面４：節点３−４−１ （指標値：８） すると、要素Ｅ２を構成する面の面番号との関係は次の
ようになる。

【００６２】 面１：節点３−１−４ （指標値：８） 面２：節点３−５−１ （指標値：９） 面３：節点１−５−４ （指標値：１０） 面４：節点４−５−３ （指標値：１２） ここで、括弧内の値は、各面の指標値である。

【００６３】要素Ｅ２の面は、メモリ上の要素Ｅ１の構
成節点列からＥ１を構成する各面の節点の組み合わせを
作成したのと全く同様に作成したものである。例えば面
１の節点はメモリ上の１〜３番目の節点番号を順に並べ
たものである。図８に各面番号を要素Ｅ１のものについ
ては数字を丸で囲んで、要素Ｅ２については四角で囲ん
で示した。

【００６４】本分割モデルについて作成したセグメント
（面）リストと指標テーブルとを図９に示す。本リスト
とテーブルを作成する手順を以下に説明する。 （１）指標テーブルの該当数の項を作成する（図２）。
ステップＡ１１１にて、まず指標テーブルの該当数の項
をすべて零に初期化する。次に、ステップＡ１１３にて
要素Ｅ１の面１の指標値を計算し（＝６）、ステップＡ
１１４にて、指標テーブルの６行目の該当数の値を１つ
大きい値（１←０＋１）に更新する。要素Ｅ１，Ｅ２の
すべての面について更新を完了することにより、図９の
（ｂ）の該当数の値を得る。

【００６５】（２）次に指標テーブルの先頭リストの項
を作成する（図３）。これは指標値の小さい順に該当数
を加算して、指標テーブルのｋ行目に１〜（ｋ−１）行
目の該当数の加算値（すべてを足し合わせた値）を登録
する。本処理により図９の（ｂ）の先頭リスト番号の値
を得る。 （３）面リストを作成する（図４）。本処理では、まず
ステップＡ１３１で指標テーブルの該当数（カウンタと
して用いる）をすべて零に初期化する。次に、ステップ
Ａ１３３で要素Ｅ１の面１から順に指標値を計算し、そ
の値からステップＡ１３４で先頭リスト番号とカウンタ
値（該当数の項の値）とを参照し、ステップＡ１３５に
て該当する面リストの項に面を登録する。例えば、要素
Ｅ１の面１の指標値は６であることから、指標テーブル
の６行目の先頭リスト番号（＝１）およびカウンタ値
（＝０）を参照し、面リストの１（＝１＋０）行目に、
本面（要素Ｅ１の面番号１）を登録する。登録後、ステ
ップ１３６では、本指標値のカウンタ値は古い値に１を
加えた値に更新する。ここでは、指標テーブル６行目の
カウンタ値（該当数の値）を零から１に更新する。本操
作をすべてのセグメントに対して行うことにより図９の
（ａ）の面リストを得る。

【００６６】面リストと指標テーブルとを作成後、フリ
ーフェイスを抽出する。本処理は、ここで作成した面リ
ストから複数の要素に共有されている面を除去すること
によって行う。以下にその手順を示す。 （４）ステップＡ１０４で、指標値１をチェック対象と
して設定する（図１）。

【００６７】（５）ステップＡ１０５，Ａ１５２，Ａ１
０７，Ａ１５１では、指標テーブルの１行目を参照し、
該当数の項の値が零であることから、なにも行わず次の
指標値の設定に移る。 （６）指標値２〜７についても、該当セグメントは１以
下であることからなにも行わない。

【００６８】（７）指標値８をチェック対象として設定
する。 （８）ステップＡ１０５で指標テーブルの８行目を参照
し、該当数が２であることから、２つの面について重複
を調べる。まず、指標テーブルの先頭リスト番号（＝
３）を参照し、その番号から対応する面リストの３行目
と４行目（該当数が２であることから２行）を参照す
る。これによって、要素Ｅ１の面４と要素Ｅ２の面１が
指標値８に対応した面であることがわかる。要素番号と
面番号を構成する節点番号に変換し（本変換が容易に行
えることは既に説明済み）、共に節点１，３，４からな
っていることがわかる。そこでこれらの面はフリーフェ
イスではないので、面リストから除去する。具体的には
面リストの３，４行目の要素番号の項を零にする。

【００６９】（９）指標値９〜１２についても同様にチ
ェックする。指標値９は該当する面が２つ（要素Ｅ１の
面３と要素Ｅ２の面２）あるが、構成する節点番号が異
なる。その他の指標値は該当数がすべて１以下であるこ
とがわかる。その結果除去される面はない。 以上の処理の結果、図９の（ａ）の面リストから３，４
行目を除いた面がフリーフェイスとして抽出される。

【００７０】次にここで用いた２つの４面体要素の分割
モデルから、フリーエッジを抽出する例について説明す
る。まず、各要素を構成する辺の番号を図１０に示す。
図中、要素Ｅ１，Ｅ２の局所辺番号をそれぞれ数字を
丸、四角で囲んで示した。ここで、各要素の辺番号と構
成節点とは、フリーフェイス抽出の場合と同様に、メモ
リ上の構成節点列から規則的につけたものである。各要
素の辺を構成する節点番号と各辺の指標値とは、次の通
りである。

【００７１】 要素Ｅ１ 辺１：節点１−２ （指標値：３（＝１＋２）） 辺２：節点２−３ （指標値：５） 辺３：節点３−１ （指標値：４） 辺４：節点２−４ （指標値：６） 辺５：節点３−４ （指標値：７） 辺６：節点１−４ （指標値：５） 要素Ｅ２ 辺１：節点３−１ （指標値：４（＝１＋３）） 辺２：節点１−４ （指標値：５） 辺３：節点４−３ （指標値：７） 辺４：節点１−５ （指標値：６） 辺５：節点４−５ （指標値：９） 辺６：節点３−５ （指標値：８） 本分割モデルについて作成したセグメント（辺）リスト
と指標テーブルとを図１１に示す。本リストとテーブル
とを作成する手順を以下に説明する。本手順は、フリー
フェイス抽出の際のリストとテーブルの作成処理とほぼ
同様である。

【００７２】（１）指標テーブルの該当数の項を作成す
る（図２）。まず、ステップＡ１１１にて、指標テーブ
ルの該当数の項をすべて零に初期化する。ステップＡ１
１３では、要素Ｅ１の辺１の指標値を計算し（＝３）、
ステップＡ１１４にて、指標テーブルの３行目の該当数
の値を１つ大きい値（１←０＋１）に更新する。要素Ｅ
１，Ｅ２のすべての辺について更新を完了することによ
り、図１１の（ｂ）の該当数の値を得る。

【００７３】（２）指標テーブルの先頭リストの項を作
成する（図３）。指標値の小さい順に該当数を加算し
て、指標テーブルのｋ行目に１〜（ｋ−１）行目の該当
数の加算値（すべてを足し合わせた値）を登録する。本
処理により、図１１の（ｂ）の先頭リスト番号の値を得
る。 （３）辺リストを作成する（図４）。まず、ステップＡ
１３１にて、指標テーブルの該当数（カウンタとして用
いる）をすべて零に初期化する。ステップＡ１３３で、
要素Ｅ１の辺１から順に指標値を計算し、その指標値か
ら、ステップＡ１３４では、先頭リスト番号とカウンタ
値（該当数の項の値）を参照し、ステップ１３５で、該
当する面リストの項に面を登録する。例えば、要素Ｅ１
の辺１の指標値は３であることから、指標テーブルの３
行目の先頭リスト（＝１）およびカウンタ値（＝０）を
参照し、面リストの１（＝１＋０）行目に、本辺（要素
Ｅ１の辺番号１）を登録する。ステップＡ１３５の登録
後、ステップＡ１３６で本指標値のカウンタ値（該当数
の項の値）は古い値に１を加えた値に更新する。ここで
は、指標テーブル３行目のカウンタ値（該当数）を零か
ら１に更新する。本操作をすべてのセグメントに対して
行うことにより図１１の（ａ）のリストを得る。

【００７４】辺リストと指標テーブルとを作成後、フリ
ーエッジを抽出する。本処理は、ここで作成した辺リス
トから複数の要素に共有されている辺を除去することに
よって行う。以下にその手順を示す。 （４）指標値１をチェック対象として設定する（図１ス
テップＡ１０４）。 （５）ステップＡ１０５，Ａ１５２，Ａ１０７，Ａ１５
１では、指標テーブルの１行目を参照し、該当数の項の
値が零であることから、なにも行わず次の指標値の設定
に移る。

【００７５】（６）指標値２，３についても、該当セグ
メントは１以下であることからなにも行わない。 （７）指標値４をチェック対象として設定する。 （８）ステップＡ１０５で指標テーブルの４行目を参照
し、該当数が２であることから、２つの辺について重複
を調べることにする。まず、指標テーブルの先頭リスト
番号（＝２）を参照し、その番号に対応する面リストの
２行目と３行目（該当数が２であることから２行）を参
照する。これによって、要素Ｅ１の辺３と要素Ｅ２の辺
１とが本指標値に対応した面であることがわかる。要素
番号と辺番号を構成する節点番号に変換し、共に節点
１，３からなっていることがわかる。そこで、これらの
辺はフリーエッジではないので、辺リストから除去す
る。具体的には辺リストの２，３行目の要素番号を零に
する。

【００７６】（９）指標値５〜９についても同様にチェ
ックする。その結果、辺リストのリスト番号５，６，
９，１０が除去される。 以上の処理の結果、図１１の（ａ）の辺リストにおける
１，４，７，８，１１，１２行の辺がフリーエッジとし
て抽出される。なお以上の処理では、セグメントリスト
中でセグメントを要素番号と局所セグメント番号との２
つの整数値で表現し、１つのセグメントに対して２整数
分のメモリを使用した。しかし、これは１つのメモリで
済ませることが可能である。すなわち局所セグメント番
号は必ず１つの要素を構成するセグメントの数以下とな
る。そこでセグメントを次式（３）のＳＧで表現して登
録する。

【００７７】 ＳＧ＝（要素番号）×（α＋１）＋（セグメント番号） （３） ここで、αは１要素当たりのセグメント数以上の整数値
である。なお、本表現から要素番号とセグメント番号に
は、次式によって戻すことができる。 要素番号＝ＳＧ／（α＋１） （４） セグメント番号＝ＭＯＤ（ＳＧ、（α＋１)) （５） （ＳＧを（α＋１）で割った剰余） ここで、式（４）の要素番号は右辺の計算値の小数点以
下を切り捨てた整数値である。

【００７８】モデル中にいくつかの要素形状が含まれて
いる場合には、形状によりセグメントの数が異なる。こ
のような場合にはその最大値をαとすればよい。また、
以上の説明ではセグメント番号を１番から始めたが、こ
れを０から始めてもよい。こうすることにより式（３）
乃至（５）における（α＋１）はαになる。

【００７９】このようにセグメントを１つの整数値で表
現することにより、セグメントリストが使用するメモリ
は半分になる。これと同様に指標テーブルの該当数と先
頭リスト番号も１つの整数値で表すことができる。発明
者の経験によれば、通常の分割モデルにおいて同一の指
標値の持つセグメントは１０個以下である。すなわち、
該当数は１０以下の整数値となり、該当数と先頭リスト
番号とを（６）式のＡＤで表現することができる。

【００８０】 ＡＤ＝（先頭リスト番号）×β＋（該当数） （６） ここで、βは１０以上の整数である。なお、本表現から
該当数と先頭リスト番号には、次式によって戻すことが
できる。 先頭リスト番号＝ＡＤ／β （７） 該当数＝ＭＯＤ（ＡＤ、β）；（ＡＤをβで割った余剰） （８） ここで、式（７）の先頭リスト番号は右辺の計算値の小
数点以下を切り捨てた整数値である。

【００８１】このように指標テーブルの該当数と先頭リ
スト番号とを１つの整数値で表現することにより、使用
するメモリは更に減る。従来技術の課題でとりあげた、
６面体要素からなる１００万要素、１００万節点の分割
モデルからフリーフェイスを抽出する場合について、本
方法を用いた場合の所要メモリを計算してみる。

【００８２】まず、面リストが必要とするメモリは、１
セグメント当たりのセグメント情報が１整数分（４バイ
ト）、リストの行数が従来と同じ６００万行であること
から２４Ｍ（４×６００万）バイトである。また、指標
テーブルが必要とするメモリは、１指標値当たりの使用
メモリが４バイト、テーブルの行数が従来と同じ約４０
０万行であることから、約１６Ｍ（４×４００万）バイ
トである。

【００８３】この結果、本分割モデルに要するメモリは
合計４０Ｍバイト（２４Ｍ＋１６Ｍ）となる。このメモ
リ容量は、現在の計算機をもってすれば十分対応可能な
値であり、一般的な計算機でも処理が可能である。なお
ここでは、３次元分割モデルからフリーフェイス，フリ
ーエッジを抽出するに場合について説明したが、本方法
は２次元モデルからフリーエッジを抽出する際にも同様
に適用することができ、また一般的なセグメントを抽出
する方法として使用することができる。

【００８４】（実施例２）実施例１では、全セグメント
から複数の要素に共有されるセグメントを除去すること
によって、フリーフェイス，フリーエッジ等の複数の要
素に共有されないセグメントを抽出した。一方、実施例
１で除去した複数の要素に共有されているセグメント
は、そのセグメントによって複数の要素が隣接している
ことを意味する。そこで本実施例では、実施例１で作成
したセグメントリストと指標テーブルとを利用して、隣
接する要素を抽出する方法について説明する。

【００８５】使用するセグメントリストと指標テーブル
とは、図１のステップＡ１０１〜Ａ１０３で作成したも
のと同じなので作成方法の説明を省略し、ここでは隣接
する要素を抽出する方法だけを説明する。図１２に隣接
する要素を抽出する処理の流れを示す。本処理はセグメ
ントリストと指標テーブルとを作成した後に行うもので
ある。

【００８６】まず、どの要素のどのセグメントで隣接す
る要素を抽出したいのかをステップＡ８０１にて設定す
る。ここで、要素を要素番号（Ｅ_i とする）で、セグメ
ントを局所セグメント番号（Ｌ_i とする）で指定する。
なお、局所セグメント番号とは実施例１で説明した要素
内でのセグメントの番号である。そして、ステップＡ８
０２にてセグメントＬ_i の指標値（Ｍ_i とする）を計算
する。次に、ステップＡ８０３にて、指標テーブルのＭ
_i 行目を参照し、該当数が１ならば、ステップＡ８０６
で要素Ｅ_i のセグメントＬ_i で隣接している要素はな
い。該当数が２以上ならば、実施例１で説明したのと同
様な方法で本セグメントと同じ節点からなるセグメント
を検索する。もし要素Ｅ_i のセグメントＬ_i 以外に同一
のセグメントがなければ、ステップＡ８０６で隣接要素
はないとする。あれば、そのセグメントを持っている要
素が隣接要素である。

【００８７】本処理を簡単な要素分割モデルを用いて具
体的に説明する。図１３は３つの４面体要素からなる分
割モデルである。本分割モデルは図２３の分割モデルに
節点５−１−４−６からなる要素Ｅ３を付加したもので
ある。要素Ｅ１，Ｅ２の局所番号は図８に示した通りで
あり、要素Ｅ３の面は次の通りである。括弧内は各面の
指標値である。

【００８８】 面１：節点５−１−４ （指標値：１０） 面２：節点５−６−１ （指標値：１２） 面３：節点１−６−４ （指標値：１１） 面４：節点４−６−５ （指標値：１５） 本分割モデルにおいて、要素Ｅ３とＥ３の面１で隣接す
る要素を抽出する場合を説明する。

【００８９】抽出に先だって、図１４の（ａ）に示す面
リストと図１４の（ｂ）に示す指標テーブルとを作成す
る。本リストとテーブルは、図１のステップＡ１０１〜
Ａ１０３の処理で作成されるものであり、その作成法は
省略する。リストとテーブルを作成後、以下の処理を行
う。 （１）図１２のステップＡ８０２では、要素Ｅ３の面番
号１の指標値を計算する。指標値は１０である。

【００９０】（２）ステップＡ８０３で指標テーブルの
１０行目を参照する。 （３）ステップＡ８０４では、該当数が２で先頭リスト
番号が７であることから、面リストの７，８行目を参照
し、本指標値を持つ面が要素Ｅ２の面番号３と要素Ｅ３
の面番号１であることがわかる。そこで、これらの要素
番号と面番号の情報を面を構成する節点番号に変換し
て、２つの面が同一であるかをステップＡ８０５にて検
査する。検査の結果２つの面は同一である（共に節点
１，４，５からなる）ことがわかり、隣接する要素とし
てＥ２が抽出される。

【００９１】本処理を通して、要素Ｅ２とＥ３とはそれ
ぞれ局所面番号３，１でお互いに隣接していることがわ
かった。以上の説明からわかるように、本方法は基本的
に実施例１で説明したセグメントリストと指標テーブル
とを用いたセグメントの抽出方法を応用したものであ
る。セグメントリストと指標テーブルとは短時間で作成
することができることから、本方法によれば高速に隣接
する要素を抽出することができる。

【００９２】なお、ここでは面で隣接している場合の例
について述べたが、これはその他のセグメントで隣接し
てもよい。例えば辺，節点で隣接している（辺，節点を
共有している）場合についても、図１２の操作で同様に
抽出を行うことができる。ただし辺，節点の場合には、
分割モデルの構造上、ステップＡ８０５においては複数
個の隣接する要素が抽出される。

【００９３】（実施例３）実施例２では、隣接する要素
を抽出する方法について述べた。ここで抽出した隣接要
素を用いれば、分割モデル中の任意の点について、その
点を内含する要素を容易に抽出することが可能である。
本実施例では実施例２で説明した隣接要素をこのよう
な、点を含む要素の抽出に適用した例について説明す
る。

【００９４】処理の流れを図１５に示し、図１３の点Ｐ
_e を含む要素を抽出する場合を例に説明する。なお、図
１３中で点Ｐ_e は要素Ｅ３に内含されている。以下、図
１５に従って処理の流れを説明する。 （１）図１５のステップＢ１０１では、どの要素に内含
されているかが既にわかっている点Ｐ₀ を設定し、その
要素番号をｉとする。図１３では要素Ｅ１の重心をＰ₀
とした。従って図１５中でｉは１である。

【００９５】（２）ステップＢ１０２で、点Ｐ_e が要素
Ｅ_i(Ｅ１）に内含されているかどうかをチェックする。
本チェックは以下の手順で容易に行うことができる。ま
ず、要素Ｅ_i を構成する１つの面Ｆ_n の法線ベクトルＡ
を計算する。本法線ベクトルは次式（９）によって計算
される。 A_x＝ (y₁-y₃)(z₂-z₃)-(y₂-y₃)(z₁-z₃) A_y＝ (z₁-z₃)(x₂-x₃)-(z₂-z₃)(x₁-x₃) A_z＝ (x₁-x₃)(y₂-y₃)-(x₂-x₃)(y₁-y₃) （９） ここで、Ａ_x ，Ａ_y ，Ａ_z は法線ベクトルの成分、（ｘ
₁ ，ｙ₁ ，ｚ₁ ），（ｘ₂ ，ｙ₂ ，ｚ₂ ），（ｘ₃ ，ｙ
₃ ，ｚ₃ ）は面Ｆ_n を構成する３つの節点の座標値であ
る。３つの節点の順番は実施例１で述べたように、メモ
リに登録された節点番号から規則的に作成したものとす
る。３つの節点の順番をこのようにすることにより、本
法線ベクトルは、要素Ｅ_i に対して同じ方向を向く。例
えば図１３において、各面の法線ベクトルはすべての要
素の重心方向を向く。そこで、ここでは点Ｐ_e が、各面
に対して法線方向を基準にしたときにどちら側に位置し
ているかを調べることにより、内含をチェックする。

【００９６】すなわち、まず次式（１０）の（ｘ，ｙ，
ｚ）に点Ｐ_e の座標値を代入し、Ｖを計算する。 V ＝A_x(x-x₁)＋A_y(y-y₁)＋A_z(z-z₁) （１０） ここで、Ｖ＞０ならば、点Ｐ_e は面Ｆ_n に対してその法
線方向側に位置し、Ｖ＜０ならば、法線方向と反対側に
位置していることを意味する（Ｖ＝０ならば面上の点で
ある。例えば図１３の場合、Ｖ＞０ならば要素の重心方
向、Ｖ＜０ならば要素の外方向に点Ｐ_e は位置している
ことを意味する。そこで、Ｖを要素を構成するすべての
面について計算し、すべての面について点Ｐ_e が要素の
重心側に位置している場合に、点Ｐ_e は要素Ｅ_i に内含
されているとする。１つ以上の面について要素の外側に
位置しているならば、内含していないとする。

【００９７】（３）ステップＢ１０３では、点Ｐ_e が要
素Ｅ_i に内含されていないならば、線分Ｐ₀ Ｐ_e と交差
する要素Ｅ_i の面（面番号Ｌ_k とする）を求める。図１
３の場合、線分Ｐ₀ Ｐ_e は要素Ｅ１の面３−１−４と点
Ｐ₁ で交差している。交差する面の抽出は、要素Ｅ_i の
面の内から２点Ｐ₀ ，Ｐ_e がそれぞれ面をはさんで異な
る側にあるものを選択することによって行う。これは式
（１０）に、点Ｐ₀ ，Ｐ_e の座標値を代入しそれぞれの
Ｖを計算し、２つのＶの値の符号が異なる面を選択すれ
ばよい。Ｐ_e が要素Ｅ_i に内含されていないならば、必
ず線分Ｐ₀ Ｐ_eと交差する（２点Ｐ₀ ，Ｐ_e が異なる側
にある）面が存在する。

【００９８】（４）ステップＢ１０４で、要素Ｅ_i と面
Ｌ_k で隣接している要素を求める（Ｅ_j とする）。これ
は実施例２で説明した方法で行う。図１３ではＥ_j はＥ
２である。 （５）ステップＢ１０５で、ここで求めた隣接要素Ｅ_j
にＥ_i を置き換えて、再び点Ｐ_e が要素Ｅ_i(Ｅ２）に内
含されるかどうかをステップＢ１０２でチェックする。
内含されていなければ再びステップＢ１０３にて、線分
Ｐ₀ Ｐ_e と交差する要素Ｅ_i(Ｅ２）の面を求める。ただ
し、ステップＢ１０３を２回目以降実行する場合は、前
回求めた面を求める面の対象から外す。例えば、図１３
において要素Ｅ２の面のうち面３−１−４はステップＢ
１０３の１回目の実行で求められたので外し、面１−４
−５を得る。

【００９９】（６）ステップＢ１０２〜Ｂ１０５の処理
を、要素Ｅ_i が点Ｐ_e を内含するようになるまで繰り返
す。図１３では、要素Ｅ２の面１−４−５の隣接要素と
して要素Ｅ３を得、要素Ｅ３が点Ｐ_e を内含する。この
ように本方法によれば、分割モデル中の適当な点（ここ
では点Ｐ₀ ）を始点として、隣接する要素を辿ることに
より、目的とする点Ｐ_e を内含する要素を抽出すること
ができる。なお、発明者の経験から、隣接する要素を辿
っていく本方法によれば、辿る経路はほぼ直線的であ
り、比較的早く目的とする要素に到達することがわかっ
ている。すなわち、ｎ個の要素からなる分割モデルの場
合、約ｎの３乗根の要素について内含のチェックを行え
ば、目的とする要素にたどりつく。

【０１００】なお、ここでは始点を適当に定めたが、複
数の点がモデル中にあるような場合には、前に抽出した
点を始点として次の点を抽出するとよい。これは、点が
曲線上に乗って順に並んでいるような場合に、隣接する
要素を辿っていく道のりが短くて済み効率的だからであ
る。 （実施例４）従来はフリーエッジを輪郭線の代用として
使用した。ここでは、実施例２で説明した隣接する要素
を求める方法を利用して、フリーフェイスのなす角度か
ら輪郭線を求める方法について説明する。

【０１０１】３次元要素分割モデルから抽出したフリー
フェイスは、２次元要素（膜状要素）からなる。そこ
で、抽出した各フリーフェイスに対してそれぞれ隣接す
る２次元要素を求め、その隣接する２つのフリーフェイ
スのなす角度を計算することにより、その稜線（２つの
要素の境界線）を輪郭線として登録するかどうかを判定
する。本輪郭線を抽出する過程を図１６に示し、以下本
図に従って処理過程を説明する。

【０１０２】まず、分割モデルからステップＢ２０１に
てフリーフェイスを抽出する。本処理は実施例１で既に
説明したので、ここでは説明を省略する。次に、ステッ
プＢ２０２で、抽出したフリーフェイスを２次元要素と
みなして、辺リストと指標テーブルとを作成する。本リ
ストとテーブルを作成する方法も実施例１と同様であ
る。次に、ステップＢ２０３〜Ｂ２０８にて、フリーフ
ェイスの１つ（Ｅ_i とする）について、そのフリーフェ
イスの１つの辺（Ｌ_j とする）を境界にして隣接するフ
リーフェイスを抽出する。本処理は実施例２で図１２に
示した方法で行うものであり、図中、ステップＢ２０３
とＢ２０４はステップＡ８０１に対応し、ステップＢ２
０５〜Ｂ２０８はステップＡ８０２〜Ａ８０５にそれぞ
れ順に対応する。

【０１０３】フリーフェイスＥ_i と辺Ｌ_j で隣接するフ
リーフェイスを抽出した後、両者のなす角度（θとす
る）をステップＢ２０９で計算する。本角度の計算は両
者の法線ベクトルをそれぞれ求め、その法線ベクトルの
なす角度を計算することによって求めることができる。
そして法線ベクトルのなす角度がπにほぼ等しければ、
２つの面がほぼ１平面上にあることを意味するので何も
行わない。それ以外ならば、両面が隣接している辺Ｌ_j
を輪郭線としてステップＢ２１２で登録する。図１６に
おいては、角度θがほぼπに等しいかどうかを、許容値
δを用いて比較している。なお、ステップＢ２０７，Ｂ
２０８において、該当数が１つまたは隣接フリーフェイ
スがないと判定された場合には、本フリーフェイスの辺
Ｌ_j は端部の辺であると判定し、辺Ｌ_j を輪郭線として
登録する。本操作を全フリーフェイスのすべての辺につ
いて実行することにより、すべての輪郭線を抽出でき
る。

【０１０４】以上の操作を図１７に示した簡単な分割モ
デルを用いて具体的に説明する。なお、図１７のモデル
は図２３と同じである。 （１）実施例１で説明した方法で、図１６のステップＢ
２０１で、次の６つの面をフリーフェイスとして抽出す
る。そして各フリーフェイスに対して、新たに２次元要
素としての要素番号をつける（Ｆ１〜Ｆ６とする）。

【０１０５】 要素Ｆ１：節点１−２−３ Ｆ２：節点１−４−２ Ｆ３：節点２−４−３ Ｆ４：節点３−５−１ Ｆ５：節点１−５−４ Ｆ６：節点４−５−３ （２）要素Ｆ１〜Ｆ６について、辺をセグメントとして
セグメントリストと指標テーブルとをステップＢ２０２
で作成する。ここでは、要素Ｆ１，Ｆ２の局所セグメン
ト番号（辺番号）を以下のように定義し、図１７に各要
素の辺番号をそれぞれ数字を丸、四角で囲んで示した。
作成したセグメントテーブルを図１８に示す。なお、図
１８には要素Ｆ１，Ｆ２に関係した一部分だけを記載し
た。

【０１０６】 （３）要素Ｆ１と同要素の辺番号１を境界にして隣接す
る要素を、ステップＢ２０３〜Ｂ２０８で求める。その
結果、要素Ｆ２が抽出される。

【０１０７】（４）要素Ｆ１とＦ２とのなす角度（θ）
を計算する。本角度の計算は次のように行う。まず、２
つの面の法線ベクトル（図１７中のベクトルＡ₁ ，Ａ
₂ ）を計算する。法線ベクトルＡ₁ ，Ａ₂ は、前出の式
（９）によって計算される。実施例３で述べたように、
２次元要素（フリーフェイス）を構成する節点番号の順
番に規則性を持たせれば、本法線ベクトルは２次元要素
の元となる３次元要素に対して同じ方向を向く。例えば
図１７において、すべての２次元要素の法線ベクトル
は、要素を構成する節点の順番に右ネジを回したときネ
ジの進む方向を向き、それは元の３次元要素（４面体要
素）の重心方向である。このことは、法線ベクトルがす
べて、モデルの表面においてモデルの内側を向くことを
示す。

【０１０８】従って、２つの法線ベクトルＡ₁ ，Ａ₂ の
なす角度が、要素Ｆ１とＦ２とのなす角度θとなる。こ
れは次式（１１）によって計算される。

【０１０９】 ただし、ここでは、０≦θ≦πとする。θを０〜２πと
しなくても問題がないことは、図１６のステップＢ２０
９の判定条件からわかる。

【０１１０】ここでは、θ＜（π−δ）であることか
ら、ステップＢ２１２で要素Ｆ１の辺１を輪郭線として
登録する。 （５）前記の（３），（４）項の操作を全ての要素のす
べての辺について行う（ステップＢ２１０，Ｂ２１
１）。その結果、本例では全ての要素の全ての辺が輪郭
線として抽出される。

【０１１１】なお、ここで登録された辺はすべて重複し
ている。すなわち各辺は、辺を境界線として持つ隣接す
る２つの要素でそれぞれ登録される。この重複は、各辺
について既に輪郭線として登録されたかどうかをフラグ
を設けてチェックすることで容易に回避することができ
る。ここでは、３次元要素からなる分割モデルから輪郭
線を抽出する場合について説明した。しかし、これは２
次元要素（膜状要素）からなる３次元形状のモデルの場
合についても適用可能である。すなわち、図１６におけ
る抽出したフリーフェイスの代わりに本２次元要素（膜
状要素）を使用すればよい。なおこの場合は、ステップ
Ｂ２０９において角度θの判定としてθが零に近い場合
にも輪郭線として登録しないようにする必要がある。す
なわち、ステップＢ２０９の条件に代えて、次式（１
２）を満たすとき、隣接する２次元要素の境界線を輪郭
線として登録する。

【０１１２】 δ＜θ＜（π−δ）、または（π＋δ）＜θ＜（２π−δ） （１２） これは、３次元要素のフリーフェイスの場合、上で述べ
たように、モデルに対して法線方向を統一できるのに対
して（上記例ではモデルの内側に向くように統一し
た）、一般的な２次元要素の場合は統一できないことに
よるものである。また、式（１２）を判定条件に用いて
輪郭線を抽出する方法は、３次元要素と２次元要素が混
在したモデルについても同様に適用できる。すなわち、
まず３次元要素からフリーフェイスを抽出し、抽出した
フリーフェイスに２次元要素を加えて、全体を２次元要
素とみなして処理を行えばよい。

【０１１３】なお発明者の経験から、ここで使用した許
容値δの値は、 π／１８０≦δ≦π／１８ （１３） とすることで、ほとんどの分割モデルに対して妥当な輪
郭線を抽出できることがわかっている。そこで、本許容
値δは、デフォルト値として式（１３）の範囲の値を設
定しておき、プログラム使用中に、ユーザが任意の値に
変更できるようにするとよい。ユーザが任意に変更でき
るようにすることにより、どのようなモデルに対しても
妥当な輪郭線を抽出できるようになる。

【０１１４】（実施例５）実施例１では、分割モデルの
全セグメントから複数の要素に共有されるセグメントを
とり除くことにより、複数の要素に共有されないセグメ
ントを抽出した。本方法を応用すれば、分割モデルから
複数の要素に共有されるセグメントも容易に抽出するこ
とができる。そしてこれはセグメントを要素自身に置き
換えることにより重複した要素も容易に抽出できる。重
複した要素を抽出することは、分割モデルのチェック、
または表示のための前処理として有効である。例えば実
施例４において、輪郭線は２度重複して登録されること
を述べた。そこで、本輪郭線を描画する前に重複するも
のを抽出し、１つにまとめれば同じ線を２度書きするこ
となく表示することができる。ここでは、このような重
複した要素を抽出して１つにまとめる方法について説明
する。

【０１１５】重複した要素を除去して、重複をなくすた
めの処理の流れは図１とほぼ同様である。すなわち、図
１におけるセグメントリストを要素リストにし、要素番
号だけを登録するようにする。また、ステップＡ１０６
において、該当する要素リストから重複する要素を除去
して重複をなくす。ステップＡ１０７で、すべての指標
値についてチェックを終了後、要素リストに残った要素
が重複していない要素である。

【０１１６】本処理を図２３の分割モデルに要素Ｅ２と
同一の要素Ｅ３を付加したモデルについて行った場所に
ついて具体的に説明する。 （１）ステップＡ１０１〜Ａ１０３によって、要素リス
トと指標テーブルとを作成する。作成したリストとテー
ブルを図１９に示す。指標値は要素を構成する節点の番
号の和であり、要素リストには要素番号だけを登録して
いる。

【０１１７】（２）チェック対象の指標値として１〜１
２を設定した場合には、該当数が１以下であることから
なにも行われない（ステップＡ１０４，Ａ１０５，Ａ１
５２）。 （３）チェック対象の指標値として１３をステップＡ１
０４で設定する。ステップＡ１０５では、該当数が２で
あることから、要素リストの２，３行目の要素について
節点を比較する。その結果、この２つは同一であること
が判明し、ステップＡ１０６で、２つのうちいずれかを
要素リストから除去する（ここではＥ３を除去）。

【０１１８】（４）指標値１４についても同様にチェッ
クを行うが該当数が零であることから何も行われない。 以上の結果、要素Ｅ１とＥ２とが重複した要素を１つに
まとめた結果として要素リストに残る。ここでは、重複
した要素を１つにまとめることにより、すべて重複しな
い要素として結果を求めたが、本方法を用いることによ
り、重複する要素の抽出、重複していない要素の抽出等
も容易に行えることは明かである。

【０１１９】なお、実施例においては、有限差分法，有
限要素法及び境界要素法に使用される要素について説明
したが、本発明はこれらと同様な構造を有するデータに
対して適用しうることは明らかである。また、本発明
は、複数の機器から構成されるシステムに適用しても、
１つの機器から成る装置に適用しても良い。また、本発
明はシステム或は装置にプログラムを供給することによ
って達成される場合にも適用できることは言うまでもな
い。

【０１２０】

【発明の効果】以上の説明から明らかなように、本発明
によれば、少量のメモリしか搭載されていない計算機で
も大規模な分割モデルからセグメントを抽出することが
出来、輪郭線が忠実に表示できるようにする、またモデ
ル中の任意の点を内含する要素を高速に抽出する有限要
素分割モデルから辺，面，要素を抽出する方法及びその
装置を提供できる。

【０１２１】更に詳細には、以下のような効果が得られ
る。本発明によれば、セグメントリストに必要なメモリ
を１セグメント当たり１整数分で済ますことができた。
また指標テーブルについても同様に１指標値当たり１整
数分でよくなった。その結果全体として使用メモリを大
幅に削減でき、メモリをあまり搭載していない計算機で
も、大規模な分割モデルからセグメントを抽出できるよ
うになった。例えば、６面体要素からなる１００万要
素、１００万節点の分割モデルからフリーフェイスを抽
出するために、従来は２５６Ｍバイトのメモリを要して
いたが、本発明により４０Ｍバイトで済むようになっ
た。

【０１２２】また、本発明によれば、同じ指標値を持つ
セグメントの数が多い場合も問題がなくなった。これ
は、式（６）のβをあらかじめ大きめに設定しておくこ
とで、容易に対応できるからである。また、本発明によ
れば、分割モデルから隣接する要素を、検索対象を同一
の指標値を持つセグメントに限定することにより、非常
に高速に抽出できるようになった。

【０１２３】また、本隣接要素の抽出方法を利用すれ
ば、分割モデル中に存在する点を内含する要素も高速に
抽出できる。これは高速に隣接する要素を抽出できるこ
とから、目的となる要素に向かって、モデル中を高速に
ほぼ直線的に突き進んで検索を行うことができるように
なったことによるものである。ｎ個の要素からなる分割
モデルの場合、従来ｎ／２回の内含チェックを行ってい
たものが、ｎの３乗根の回数で済むようになった。

【０１２４】また、モデルに忠実な輪郭線を高速に得ら
れるようにもなった。この忠実性は、輪郭線を、隣接す
るフリーフェイス間の角度から求めるようにしたことに
起因する。例えば、図１９のモデルに対して、従来は図
２２で示したフリーエッジを輪郭線として表示していた
が、本発明により図２２における線分１−４，１−３，
３−１も輪郭線として抽出できるようになった。また本
高速性は隣接するフリーフェイスを高速に求めることが
できるようになったことに起因する。

【０１２５】また本発明を用いて、分割モデルから重複
した要素を高速に抽出することもできるようになった。

【図面の簡単な説明】

【図１】実施例１の処理の流れを示す図である。

【図２】図１のＡ１０１の詳細な処理の流れを示す図で
ある。

【図３】図１のＡ１０２の詳細な処理の流れを示す図で
ある。

【図４】図１のＡ１０３の詳細な処理の流れを示す図で
ある。

【図５】実施例１の処理中に作成するリストとテーブル
の形式である。

【図６】実施例１のセグメントを説明するための図であ
る。

【図７】実施例１のセグメントを説明するための図であ
る。

【図８】実施例１でセグメントを面とする場合の具体的
処理を説明するための図である。

【図９】実施例１でセグメントを面とする場合の具体的
処理を説明するための図である。

【図１０】実施例１でセグメントを辺とする場合の具体
的処理を説明するための図である。

【図１１】実施例１でセグメントを辺とする場合の具体
的処理を説明するための図である。

【図１２】実施例２の処理の流れを示す図である。

【図１３】実施例２でセグメントを面とする場合の具体
的処理を説明するための図である。

【図１４】実施例２でセグメントを面とする場合の具体
的処理を説明するための図である。

【図１５】実施例３の処理の流れを示す図である。

【図１６】実施例４処理の流れを示す図である。

【図１７】実施例４の具体的処理を説明するための図で
ある。

【図１８】実施例４の具体的処理を説明するための図で
ある。

【図１９】実施例５を説明する図である。

【図２０】本実施例を実現する計算機の構成を示すブロ
ック図である。

【図２１】従来技術を説明する処理の流れ図である。

【図２２】従来技術の処理中に作成するリストとテーブ
ルとの形式を示す図である。

【図２３】従来技術の具体的処理を説明するための図で
ある。

【図２４】従来技術でセグメントを面とする場合の具体
的処理を説明するための図である。

【図２５】従来技術でセグメントを辺とする場合の具体
的処理を説明するための図である。

【図２６】従来技術の具体的処理の結果を説明するため
の図である。

【符号の説明】

Ｅ１〜Ｅ３，Ｆ１〜Ｆ６ 要素 〜，１〜６ 局所セグメント番号 Ｐ₀ 〜Ｐ₂ ，Ｐ_e 分割モデル中の点 １６１ 表示部 １６２ ＣＰＵ １６３ ＲＡＭ １６３−１ セグメントリスト領域 １６３−２ 指標テーブル領域 １６３−３ 指標値カウンタ領域 １６３−４ 要素テーブル領域 １６４ 入力部 １６５ ＲＯＭ

Claims (27)

【特許請求の範囲】
1. 【請求項１】 有限要素分割モデルから辺，面，要素を
   抽出する方法であって、 各要素と該要素を構成する節点とが対応して記憶されて
   いる場合に、１つの辺，面または要素を１つのセグメン
   トと見なして、有限要素分割モデルから前記セグメント
   を抽出する際に、 前記セグメントに対して前記セグメントを構成する節点
   の組み合わせを特徴付ける指標値をつけ、 同じ指標値を持つセグメントの情報が連続に並んだセグ
   メントリストと、前記指標値と前記セグメントリスト上
   の位置とを関連づける指標テーブルとを作成し、 前記セグメントリストと前記指標テーブルとに基づい
   て、同じ指標値を持つセグメントを抽出して、抽出され
   たセグメントを構成する節点情報を得るようにしたこと
   を特徴とする有限要素分割モデルから辺，面，要素を抽
   出する方法。
2. 【請求項２】 前記セグメントリストに記憶される情報
   は、各セグメントを有する要素を特定する第１識別子
   と、該セグメントが前記要素の何番目のセグメントであ
   るかを示す第２識別子とで表現されることを特徴とする
   請求項１記載の有限要素分割モデルから辺，面，要素を
   抽出する方法。
3. 【請求項３】 前記セグメントリストに記憶されるセグ
   メントは、前記指標値の大きい順または小さい順に並ぶ
   ことを特徴とする請求項１記載の有限要素分割モデルか
   ら辺，面，要素を抽出する方法。
4. 【請求項４】 前記第１識別子に１つの要素を構成する
   セグメントの数以上の所定の整数値を乗じ、これに前記
   第２識別子を加えることにより、前記第１及び第２識別
   子を１つの整数値として記憶することを特徴とする請求
   項２記載の有限要素分割モデルから辺，面，要素を抽出
   する方法。
5. 【請求項５】 前記指標テーブルの各指標値の情報は、
   該指標値に該当するセグメントの個数と該セグメントが
   記憶されるセグメントリストの先頭を指すポインタとで
   表現されることを特徴とする請求項１記載の有限要素分
   割モデルから辺，面，要素を抽出する方法。
6. 【請求項６】 前記ポインタに１０以上の整数値を乗
   じ、これに前記セグメントの個数を加えることにより、
   前記個数及びポインタを１つの整数値として記憶するこ
   とを特徴とする請求項５記載の有限要素分割モデルから
   辺，面，要素を抽出する方法。
7. 【請求項７】 前記セグメントリストと前記指標テーブ
   ルとは、各セグメントの指標値に基づいて各指標値のセ
   グメント個数を求め、求めた個数を指標値の小さい順ま
   たは大きい順に加算していくことにより前記ポインタを
   求め、前記ポインタをもとに各セグメントの情報を前記
   セグメントリストに登録していくという手順で作成され
   ることを特徴とする請求項５記載の有限要素分割モデル
   から辺，面，要素を抽出する方法。
8. 【請求項８】 更に、抽出したセグメントの内、同一の
   節点からなるセグメントから構成される複数の要素を隣
   接要素として抽出することを特徴とする請求項１記載の
   有限要素分割モデルから辺，面，要素を抽出する方法。
9. 【請求項９】 更に、前記同一の節点からなるセグメン
   トをセグメントリストから除去することにより、セグメ
   ントリストには重複のないセグメントだけが残るように
   することを特徴とする請求項１記載の有限要素分割モデ
   ルから辺，面，要素を抽出する方法。
10. 【請求項１０】 前記セグメントが有限要素分割モデル
    を構成する面であって、前記セグメントリストには複数
    の要素を構成しないフリーフェイスが残るようにするこ
    とを特徴とする請求項９記載の有限要素分割モデルから
    辺，面，要素を抽出する方法。
11. 【請求項１１】 前記セグメントが有限要素分割モデル
    を構成する辺であって、前記セグメントリストには複数
    の要素を構成しないフリーエッジが残るようにすること
    を特徴とする請求項９記載の有限要素分割モデルから
    辺，面，要素を抽出する方法。
12. 【請求項１２】 有限要素分割モデル中の１点Ｐ_e を内
    含する要素を抽出する方法であって、 ある要素Ｅ₀ に内含されている既知の点Ｐ₀ を始点とし
    て、２点Ｐ_e とＰ₀ を結ぶ線分と交差する要素Ｅ₀ の面
    Ｆ₀ を求め、 要素Ｅ₀ と面Ｆ₀ を境界にして隣接する要素Ｅ₁ を求
    め、 ２点Ｐ_e とＰ₀ を結ぶ線分と交差する要素Ｅ₁ のＦ₀ 以
    外の面Ｆ₁ を求め、 該面Ｆ₁ で要素Ｅ₁ と隣接する要素Ｅ₂ を求めるという
    処理を繰り返し、 隣接する要素を辿っていくことにより、点Ｐ_e を内含す
    る要素を抽出することを特徴とする有限要素分割モデル
    から要素を抽出する方法。
13. 【請求項１３】 前記隣接する要素の抽出では、 各要素と該要素を構成する節点とが対応して記憶されて
    いる場合に、１つの辺，面または要素を１つのセグメン
    トと見なして、前記セグメントに対して前記セグメント
    を構成する節点の組み合わせを特徴付ける指標値をつ
    け、 同じ指標値を持つセグメントの情報が連続に並んだセグ
    メントリストと、前記指標値と前記セグメントリスト上
    の位置とを関連づける指標テーブルとを作成し、 前記セグメントリストと前記指標テーブルとに基づい
    て、同じ指標値を持つセグメントを抽出して、抽出され
    たセグメントを構成する節点情報を得て、 抽出したセグメントの内、同一の節点からなるセグメン
    トから構成される複数の要素を隣接要素とすることを特
    徴とする請求項１２記載の有限要素分割モデルから要素
    を抽出する方法。
14. 【請求項１４】 ３次元有限要素モデルからフリーフェ
    イスを抽出し、 該フリーフェイスを膜状要素の２次元要素とみなして、
    隣接する２次元要素を抽出し、 隣接する２次元要素のなす角度θを求め、 角度θの値が、許容値をδとすると、０≦θ＜（π−
    δ）、または（π＋δ）＜θ＜２πであるとき、前記２
    つの２次元要素の境界線を輪郭線として抽出することを
    特徴とする有限要素分割モデルから辺を抽出する方法。
15. 【請求項１５】 更に、抽出したフリーフェイスに膜状
    要素の２次元要素からなる３次元形状の分割モデルを加
    えて、隣接する２次元要素を抽出し、 角度θの値が、許容値をδとすると、δ≦θ＜（π−
    δ）、または（π＋δ）＜θ＜２π−δであるとき、前
    記２つの２次元要素の境界線を輪郭線として抽出するこ
    とを特徴とする請求項１４記載の有限要素分割モデルか
    ら辺を抽出する方法。
16. 【請求項１６】 許容値δの値を、デフォルト値とし
    て、π／１８０≦δ≦π／１８と設定しておき、 プログラム使用中にはユーザが任意に指定できるように
    することを特徴とする請求項１４または１５記載の有限
    要素分割モデルから辺を抽出する方法。
17. 【請求項１７】 前記フリーフェイスの抽出では、 各要素と該要素を構成する節点とが対応して記憶されて
    いる場合に、１つの辺を１つのセグメントと見なして、
    前記セグメントに対して前記セグメントを構成する節点
    の組み合わせを特徴付ける指標値をつけ、 同じ指標値を持つセグメントの情報が連続に並んだセグ
    メントリストと、前記指標値と前記セグメントリスト上
    の位置とを関連づける指標テーブルとを作成し、 前記セグメントリストと前記指標テーブルとに基づい
    て、同じ指標値を持つセグメントを抽出して、抽出され
    たセグメントを構成する節点情報を得て、 同一の節点からなるセグメントを前記セグメントリスト
    から除去することにより、前記セグメントリストに残っ
    た面をフリーフェイスとすることを特徴とする請求項１
    ４記載の有限要素分割モデルから辺を抽出する方法。
18. 【請求項１８】 前記隣接する２次元要素の抽出では、 各要素と該要素を構成する節点とが対応して記憶されて
    いる場合に、１つの面を１つのセグメントと見なして、
    前記セグメントに対して前記セグメントを構成する節点
    の組み合わせを特徴付ける指標値をつけ、 同じ指標値を持つセグメントの情報が連続に並んだセグ
    メントリストと、前記指標値と前記セグメントリスト上
    の位置とを関連づける指標テーブルとを作成し、 前記セグメントリストと前記指標テーブルとに基づい
    て、同じ指標値を持つセグメントを抽出して、抽出され
    たセグメントを構成する節点情報を得て、 抽出したセグメントの内、同一の節点からなるセグメン
    トから構成される複数の要素を隣接面とすることを特徴
    とする請求項１４または１５記載の有限要素分割モデル
    から辺を抽出する方法。
19. 【請求項１９】 有限要素分割モデルから辺，面，要素
    を抽出する装置であって、 各要素と該要素を構成する節点とを対応して記憶する手
    段と、 １つの辺，面または要素を１つのセグメントと見なし
    て、前記セグメントに対して前記セグメントを構成する
    節点の組み合わせを特徴付ける指標値をつける手段と、 同じ指標値を持つセグメントの情報が連続に並んだセグ
    メントリストと、前記指標値と前記セグメントリスト上
    の位置とを関連づける指標テーブルとを作成する手段
    と、 前記セグメントリストと前記指標テーブルとに基づい
    て、同じ指標値を持つセグメントを抽出して、前記各要
    素と該要素を構成する節点との対応に基づいて、抽出さ
    れたセグメントを構成する節点情報を得る手段とを備え
    ることを特徴とする有限要素分割モデルから辺，面，要
    素を抽出する装置。
20. 【請求項２０】 前記セグメントリストに記憶される情
    報は、各セグメントを有する要素を特定する第１識別子
    と、該セグメントが前記要素の何番目のセグメントであ
    るかを示す第２識別子とで表現されることを特徴とする
    請求項１９記載の有限要素分割モデルから辺，面，要素
    を抽出する装置。
21. 【請求項２１】 前記セグメントリストに記憶されるセ
    グメントは、前記指標値の大きい順または小さい順に並
    ぶことを特徴とする請求項１９記載の有限要素分割モデ
    ルから辺，面，要素を抽出する装置。
22. 【請求項２２】 前記第１識別子に１つの要素を構成す
    るセグメントの数以上の所定の整数値を乗じ、これに前
    記第２識別子を加えることにより、前記第１及び第２識
    別子を１つの整数値として記憶することを特徴とする請
    求項２０記載の有限要素分割モデルから辺，面，要素を
    抽出する装置。
23. 【請求項２３】 前記指標テーブルの各指標値の情報
    は、該指標値に該当するセグメントの個数と該セグメン
    トが記憶されるセグメントリストの先頭を指すポインタ
    とで表現されることを特徴とする請求項１９記載の有限
    要素分割モデルから辺，面，要素を抽出する装置。
24. 【請求項２４】 前記ポインタに１０以上の整数値を乗
    じ、これに前記セグメントの個数を加えることにより、
    前記個数及びポインタを１つの整数値として記憶するこ
    とを特徴とする請求項２３記載の有限要素分割モデルか
    ら辺，面，要素を抽出する装置。
25. 【請求項２５】 前記セグメントリストと前記指標テー
    ブルとを作成する手段は、 各セグメントの指標値に基づいて各指標値のセグメント
    個数を求める手段と、 求めた個数を指標値の小さい順または大きい順に加算し
    ていくことにより前記ポインタを求める手段と、 前記ポインタをもとに各セグメントの情報を前記セグメ
    ントリストに登録していく手段とを備えることを特徴と
    する請求項５記載の有限要素分割モデルから辺，面，要
    素を抽出する装置。
26. 【請求項２６】 更に、抽出したセグメントの内、同一
    の節点からなるセグメントから構成される複数の要素を
    隣接要素として抽出する手段を備えることを特徴とする
    請求項１９記載の有限要素分割モデルから辺，面，要素
    を抽出する装置。
27. 【請求項２７】 更に、前記同一の節点からなるセグメ
    ントを前記セグメントリストから除去する除去手段を備
    えることにより、前記セグメントリストには重複のない
    セグメントだけが残るようにすることを特徴とする請求
    項１９記載の有限要素分割モデルから辺，面，要素を抽
    出する装置。