(57)【要約】コンピュータ実行プロセスはＣＡＤソフトウェアで実施される高次の複雑な幾何学形状を表面ベースの組合せ幾何学形状（SBCG）フォーマットへ変換する。変換プロセスは商用のＣＡＤソフトウェアシステムから普通に利用可能な２つのデータセットで動作する１組の低レベルのアルゴリズムからなる。プロセスは所定の部品を作るトリム表面（ステップ36）のリストを書込む。これらのデータは典型的にIGES、STEPまたはACISのような標準的な幾何学形状表示の１つから利用できる。プロセスはまたノードデータのリスト、即ち内部または外部部品として指定される点座標の過密なグループを書込む（ステップ38）。これらのデータは標準的なFEツール（例えばProMechanica）を使用して関係する部品の内外の固体幾何学形状を分割して得られる。プロセスはこれらの２つのデータセットを解析表面のリストと良好に配置されたゾーニングステートメントへ変換し（ステップ40）、そのステートメントを最適化する（ステップ50）。【選択図】      図４ｂ
2006528814.tif 000002
【特許請求の範囲】
【請求項１】
高次の複雑な幾何学形状をコンピュータ援用設計（ＣＡＤ）モデル（30）から、解析表面のリストと良好に配置されたゾーニングステートメントとを含む表面ベースの組合せ幾何学形状フォーマット（32）に変換するコンピュータにより実行される方法において、
ＣＡＤモデルからトリムされた表面52のリストを書込み（ステップ36）、前記トリムされた表面はスペース中の幾何学形状表面の境界を限定された表示であり、
部品内またはＣＡＤモデルで表される無効スペース内のいずれかに位置するノードのリスト（60、61）を生成し（ステップ38）、
トリム表面から解析的な境界表面63を計算し（ステップ42）、
曖昧表面（64）を形成するため相互に解析的な境界表面を比較し（ステップ33）、前記境界表面および曖昧表面は解析的な表面（62）のリストを形成し、
ノードゾーニングステートメント（67）のシーケンスを生成するために各ノード（65）を各解析表面と比較し（ステップ46、48）、前記特別なノードゾーニングステートメントは共に良好に配置されたゾーミングステートメント（68）を形成しているコンピュータにより実行される方法。
【請求項２】
トリム表面のリストは複数のエンティティと、各エンティティのタイプの指定子と、変換マトリックスとを含んでおり、トリムされていない空間的要素の抽出は、
幾何学幾何学形状オブジェクトのタイプを決定するために各エンティティを検査し（ステップ70−110）、
適切な変換によりエンティティを幾何学幾何学形状の対象物の解析的境界表面へマップする（ステップ112−268）するステップを含んでいる請求項１記載のコンピュータにより実行される方法。
【請求項３】
曖昧表面は、
全ての境界表面の対の比較（272）を行い、
境界表面の各対間に条件274が存在するか否かを決定し、存在するならば、
境界表面が区別に不十分であるスペースの領域を弁別するために特別な解析的曖昧表面（276）を生成することにより形成される請求項１記載のコンピュータにより実行される方法。
【請求項４】
ゾーニングステートメントは、その行が異なるノードゾーニングステートメントに対応する真理値表（321）によって表され、さらに、
サブテーブルを最適化するための３理論を有する遺伝アルゴリズムを使用して、初期の真理値表を反復的にＴおよびＦサブテーブルに二分割し（ステップ320−344）、開始点として先の解を使用して各再統合された真理値表を最適化するために同一の遺伝アルゴリズムを使用しながらサブテーブルを反復的に再結合することによりゾーニングステートメントを最適化するステップを含んでいる請求項１記載のコンピュータにより実行される方法。
【請求項５】
反復的な二分割は、
その部品に対する真理値表Ｔと、無効スペースに対するその補数Ｆと、関連する強制テーブルＭとを選択し（ステップ322）、
二分割列を選択し（ステップ324）、
サブドメインに対応する二分割列で真理値表Ｔに対するサブテーブルＴＡおよびＴＢを生成し（ステップ326、328）、
補数のサブテーブルＦＡ、ＦＢを生成し（ステップ330、332、334、336）、
Ｍテーブルを二分割列でサブテーブルＭＡ、ＭＢに分割し（ステップ329）、
サブテーブルＴＡ、ＴＢ、補数ＦＡ、ＦＢ、ＭサブテーブルＭＡ、ＭＢを簡単にし（ステップ342、344）、
これらが十分に小さくなるまで、各真理値表Ｔのサブテーブルに対してプロセスを反復する（ステップ320）ステップを含んでいる請求項４記載のコンピュータにより実行される方法。
【請求項６】
遺伝アルゴリズムは、
部品の真理値表Ｔのサブテーブルとその補数とを開き（ステップ350、352）、
３ゾーニングステートメントとして真理値表Ｔのサブテーブルからシードオーガニズムを形成し（ステップ354）、
シードから初期オーガニズムのプールを生成し（ステップ356−366）、
ポピュレーションが安定するまで、プールを増殖し（ステップ368−376）、
最高のスコアの３ゾーニングステートメントを選択する（ステップ378）ステップを含んでいる請求項４または５記載のコンピュータにより実行される方法。
【請求項７】
後退は、
次に高いレベルのサブドメインから真理値表Ｔのサブテーブルとその補数Ｆとを選択し（ステップ384）、
サブテーブルＴの２つの最小化された３ゾーニングステートメントを検索し（ステップ388）、
２つの最小化された３ゾーニングステートメントからシードオーガニズムを形成し（ステップ390）、
シードから初期オーガニズムのプールを生成し（ステップ392）、
ポピュレーションが安定するまで、プールを増殖し（ステップ392）、
最高のスコアの３ゾーニングステートメントを選択する（ステップ394）ステップを含んでいる請求項４、５、または６のいずれか１項記載のコンピュータにより実行される方法。
【請求項８】
空間における高次の幾何学形状の表面の限定された解析的表示を形成するトリム表面（52）のリストを発生する部品に対するＣＡＤモデル（30）を生成するＣＡＤシステムと、
部品（60）上に位置するノードのリストと、無効スペース（61）に位置するノードのリストを生成するために部品を分割するソフトウェアツールと、
トリム表面およびノードのリストを、境界表面（63）および曖昧表面（64）ならびに良好に配置されたゾーニングステートメント（68）を有する解析表面62のリストを含んでいる表面ベースの組合せ幾何学形状（ＳＢＣＧ）フォーマット32に変換する変換プログラムと、
ＳＢＣＧフォーマットのデータで動作する光線追跡プログラムとを有しているコンピュータにより実行されるシステム。
【請求項９】
変換プログラムは、
境界表面を設けるためにトリム方面から解析的な境界表面を計算し（ステップ42）、
境界表面を相互に比較することにより良好に配置されたゾーニングステートメントに対して必要とされる曖昧表面を形成し（ステップ44）、
ノードゾーニングステートメントのシーケンスを生成するために各ノードを各解析表面と比較するステップ（ステップ48）により変換を行い、前記特有のノードゾーニングステートメントが共に良好に配置されたゾーニングステートメント（68）を形成する請求項８記載のコンピュータにより実行されるシステム。
【請求項１０】
変換プログラムは２進最小化を使用してゾーニングステートメントを最適化する請求項８記載のコンピュータに実行されるシステム。
【請求項１１】
変換プログラムは、
真理値表（321）としてゾーニングステートメントを表し、
サブテーブルを最適化するため３理論による遺伝アルゴリズムを使用して（ステップ350−380）真理値表をサブテーブルに反復的に二分割し（ステップ320−344）、開始点として先の解を使用して各再統合された真理値表を最適化するために同じ遺伝アルゴリズムを使用しながらサブテーブルを反復的に再結合するステップ（ステップ382−396）によって２進最小化を実行する請求項１０記載のコンピュータにより実行されるシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータ援用設計（ＣＡＤ）モデルから、核放射転送、光学設計、熱放射転送、可視情景描写、またはその他の通常の光線追跡応用で普通に使用されるような表面ベースの組合せ幾何学形状（ＳＢＣＧ）フォーマットへの高次の複雑な幾何学形状を変換するコンピュータ実行技術に関する。
【背景技術】
【０００２】
本出願は2003年５月19日出願の米国特許出願第60/471,580号明細書（発明の名称“Computerized Modeling System and Method to Transform Nodal and Parametric Surface Data from CAD Product Form into Efficient, High Accuracy, Combinatorial Geometry”）に対して35 U.S.C. 119(e)下で優先権の利点を主張しており、この明細書の内容全体は本願で参考文献とされている。
【０００３】
ＣＡＤシステムにおけるハードウェアの幾何学形状記述の発展は基本的に放射転送およびその他の光線追跡応用の文脈で同一の幾何学形状を記述することに関する問題とは異なる。典型的に、ＣＡＤシステムは機構の設計目的に基づいて、複雑なアセンブリの構築および変更を容易にすることを意図されている。他方で、放射転送コードは、単に物体を通過するエネルギ粒子の運動に関係し、設計目的も部品の機械的目的もこの文脈では意味をもたない。ＣＡＤソフトウェアを使用して設計されたシステムの放射効果を解析するために、これらの設計はそれらの元の形態から標準的な放射転送ツールの要求に適合する形態に変換されなければならない。
【０００４】
特定の商用のＣＡＤ幾何学形状データ構造の詳細は（ＩＧＥＳ、ＡＣＩＳ、ＳＴＥＰのような標準的な出力フォーマットを別として）典型的に独占であるが、簡単な幾何学形状の構造から複雑な部品およびアセンブリを組立てる手段として構造固体幾何学形状（ＣＳＧ）を考察するために十分に例示的である。ＣＳＧでは、部品は典型的に変換、回転、スケーリングのような簡単な動作を球体、シリンダ、ボックスのような有限の基本固体について行うことにより設計される。さらに、対象物はブールの演算子の使用により組合わせて変形されることができる。ブール演算のセットは２つの対象物のセットの合併または交差を取り、同様に相互に関連する固体材料から対象物の１つのセットに関連する空間を減算することを含んでいる。ベース16に形成されている丸みを付けられた端部14を有するスロット12を有している簡単な部品10が図１のａおよびｂに示されている。ＣＳＧフレームワークでは、この対象物は部品のベースを作り上げるボックスを例示し、スロットの丸みをつけられた端部を有する２つのシリンダを生成し、次に２つのシリンダを接合するボックスを生成することにより生成される。ブール演算はその後、シリンダをそれらの整列されたボックスと接合するように行われ、そのオリジナルベースからユニオンを減算し、部品を図示されているようにする。このフレームワークでは、非常にわずかの演算がかなり複雑にされた幾何学形状の形態を説明するために必要とされる。非常の複雑な形態を組立てるための簡単な演算の連続するセットを使用する能力はむしろ機械加工プロセスの呼出しである。実際に、ＣＳＧ方法は、２次元の製図者によく知られた基本のセット、即ち線セグメントと曲線から開始する３次元のＣＡＤシステムの発生から成長した。
【０００５】
ＣＡＤ幾何学形状とは異なって、放射転送幾何学形状の最も有力な模範はこの３０年間、大きな変更をされていない。主要な放射転送コードの第１の公式化はもともと国立研究所の物理学者により提案され、幾何学形状処理に当てられた計算サイクルの割合を最小にすることが重要であった。そのときのコンピュータは毎秒当りの浮動小数点演算の第１０位のみが可能であり、統計的に重要な数における核反応の計算の処理は非常に合理化された幾何学形状計算を必要とした。
【０００６】
ローレンスリバーモア国立研究所（ＬＬＮＬ）、ロスアラモス国立研究所（ＬＡＮＬ）の物理学者が放射転送コードで使用するためのデータをフォーマットするために獲得した解は非同時的で、概念上同一である。ＴＡＲＴ（ＬＬＮＬ）とＭＣＮＰ（ＬＡＮＬ）コードは空間中の領域を単に限定するために限定されていない解析表面を使用する。両コードはそれぞれ識別目的で特有のインデックスを有する全ての解析的な表面定義をリストし、さらに、領域の境界を含む表面インデックスの簡単なサブリストとして空間の各特有の領域をリストする入力見出し（ｄｅｃｋ）を有している。これらの表面インデックスは関心のある領域（通常セルまたはゾーンと呼ばれる）が解析表面の内部にあるかまたは外部にあるかの随意選択的な規定に基づいて正または負の符号にされる。
【０００７】
解析表面は、簡単な閉じた形態の式が随意選択的に位置されたベクトルとの表面の直交点を生成する特有の特性を有している。結果として、幾何学形状が最初に解析表面により規定されるならば、解析形態を回復するための任意のその後の計算の必要性は減少されることができる。さらに、符号を付けられた境界表面だけに関してゾーンを規定することは、粒子が任意の特定の軌跡に沿ってゾーンを離れる時を決定するための必要な計算を最小にする。放射転送コード中の幾何学形状模範は簡単な交差理論（例えば良好に配置されたゾーニングステートメント）のゾーン定義により共に結合された限定されていない解析表面から構成される。これは表面ベースの組合せ幾何学形状（ＳＢＣＧ）と呼ばれる。解析表面ライブラリはコードにより異なるが、典型的に、最低でも、球、円筒、平面、および円錐を含んでいる。このような表面の定義はこれらを空間で変換、回転、スケールするための情報を含んでいる。
【０００８】
コンピュータ援用設計（ＣＡＤ）モデルからＳＢＣＧフォーマットへの高次の複雑な幾何学形状の変換に対する現在の実用されている方法は労力を要し、時間を浪費し、エラーを生じやすい。非常に正確なエンジニアは複雑な部品のＣＡＤ図面が与えられ、各部品を作る解析表面に対する式を決定するために定規および分度器を使用する。続いて、彼らは手書きのスケッチと試行錯誤の方法を使用してゾーニングステートメントを決定する。例示の部分に戻ると、解析表面20のリストはＳＢＣＧフォーマットで必要とされる図２のｂに示されているような良好に配置されたゾーニングステートメント26により部品10に対する図２のａに示されているようなゾーンＺ１、Ｚ２、Ｚ３、Ｚ４を規定するために使用されることのできる境界表面22（Ｓ１−Ｓ８）と曖昧表面24（Ｓ９−Ｓ１０）の両者を含んでいる。このプロセスは各部品に対して多くの時間がかかり、人間によるエラーを生じやすい。単一のエラーは不適切に配置されたゾーニングステートメントと、さらに妥当ではない変換を生成する。手動変換の複雑性は複雑な３次元部品で劇的に増加する。
【発明の開示】
【発明が解決しようとする課題】
【０００９】
生成されたＣＡＤフォーマットからＳＢＣＧフォーマットへ高次の複雑な幾何学形状を変換するコンピュータによって実行されるプロセスが緊急に必要とされている。このような自動化された変換は核放射転送用だけでなく、光学設計、迷光解析、熱放射転送、可視情景描写、およびその他の通常の光線追跡応用においても有効である。
【課題を解決するための手段】
【００１０】
本発明は、ＣＡＤモデルから、核放射転送、光学設計、迷光解析、熱放射転送、可視情景描写、またはその他の通常の光線追跡用に使用されるような表面ベースの組合せ幾何学形状（ＳＢＣＧ）フォーマットへの高次の複雑な幾何学形状の自動変換を提供する。
【００１１】
自動化された変換はＣＡＤソフトウェアおよびツールから必要とされるトリム表面とノードデータを抽出し、そのデータを解析表面のリストに変換し、良好に配置されたゾーニングステートメントを公式化し、そのゾーニングステートメントを最適化することによって実現される。特に、コンピュータはトリム表面のリストから解析的な境界表面を計算し、任意の必要とされる解析的曖昧表面を形成し、ノードデータから部品のリストと無効なスペースノードを発生し、各ノードを各解析表面と比較して初期的なゾーニングステートメントを公式化する。コンピュータはその後、冗長表面への参照を消去し、例えば２進最小化アルゴリズムを使用してゾーンをマージすることによりゾーニングステートメントを最適化する。
【００１２】
例示的な実施形態では、ＣＡＤソフトウェアは部品を含んでいる幾何学形状エンティティについての情報を含んでいるファイルを提供する。コンピュータは幾何学形状対象物のタイプを決定し、任意の表面タイプエンティティを適切な変換により解析境界表面にマップするために各エンティティを検査する。コンピュータはその後、各境界表面と１つおきの境界表面との比較を行い、任意の条件のリストが満たされているか否かを決定する。特定の条件が真であるならば、コンピュータは２つの境界表面の交差でゾーンを区別するために必要な解析的曖昧表面を生成する。
【００１３】
ＣＡＤソフトウェアまたは関連するツール（有限エレメントまたはランダムノードの生成）は候補ノードの２つのリストを提供し、その一方は部品をカバーし、他方は任意の無効スペースをカバーする。種々の技術が、部品の最小の特徴さえもその中のノードによって、またはノードなしに適切に特徴付けされるように、ノードリストが十分にポピュレートされていることを確認するために使用される。
【００１４】
解析的な境界および曖昧表面のこのリストと、ノードデータのリストとを装備することにより、この例示的な実施形態の次のステップは各ノードを各解析方面と比較し、符号を付けられた数（“ノードゾーニングステートメント”）のリストによりノードが各解析表面の“内部”にあるか“外部”にあるか否かを指示し、リストを他のノードに対応する他の既存のリストと比較することにより初期ゾーニングステートメントを公式化することである。一致が存在するならば、コンピュータはノードに既存の同一リストのラベルを割当てる。一致が存在しないならば、コンピュータはノードに新しいラベルを割当てる。ノードと幾何学形状の各表面との間の関係のこれらのリストの完全なテーブルは初期ゾーンステートメントを含んでいる。
【００１５】
最後に、初期ゾーンステートメントは、最小の寸法にされたサブテーブルのセットが得られるまで、これらの表の関係リストが漸進的に小さくなるサブテーブルへさらに反復的に分割される２進最小化アルゴリズムを使用して最適化される。この点において、各サブテーブルは遺伝アルゴリズムを使用して解かれることができる。この情報は分解プロセスを通して後退し、部品の幾何学形状全体が再度統合されるまで、各再統合されたサブテーブルで解手順を反復することにより伝播されることができる。
【発明を実施するための最良の形態】
【００１６】
本発明のこれらおよび他の特徴と利点は添付図面を参照にした好ましい実施形態の以下の詳細な説明から当業者に明白であろう。
【００１７】
本発明は、部品の高次の複雑な形状に対するＣＡＤモデルから、核放射転送、光学設計、迷光解析、熱放射転送、可視情景描写、およびその他の通常の光線追跡応用で使用される表面ベースの組合せ幾何学形状（ＳＢＣＧ）フォーマットへ変換するための自動化されたコンピュータが実行するプロセスを与える。自動化された変換はＣＡＤモデルから必要なトリム表面およびノードデータを抽出し、そのデータを解析表面のリストに変換し、良好に配置されたゾーニングステートメントを公式化し、最後にそのゾーニングステートメントを最適化するステップを含んでいる。
【００１８】
図３に示されているように、部品の高次の複雑な幾何学形状はコンピュータ34で実行される自動化されたプロセスを使用してＣＡＤモデル30からＳＢＣＧフォーマット32に変換され、これは変換の速度、正確度、一貫性を改良している。自動化されたプロセスを進展する第１のステップはこのような自動化された変換に必要なデータがＰｒｏＥｎｇｉｎｅｅｒのような全ての主要なＣＡＤプログラムおよび、ＣＡＤプログラムと共に普通に使用されるＰｒｏ  ＭｅｃｈａｎｉｃａまたはＡＮＳＹＳのような有限エレメント（ＦＥ）ツールにより容易にサポートされたことを認識することである。特に、ＣＡＤプログラムは３次元ＣＡＤモデルを形成する通常の出力としてトリムされた表面のリストを書込む（ステップ36）。ＣＡＤプログラム、例えばＦＥツールまたはランダムノード発生アルゴリズムは部品に対するノードのリストと、任意の無効なスペースのリストを書込む（ステップ38）。
【００１９】
第２のステップはトリム表面のリストを解析表面のリストに変換し、これらの表面および候補ノードから得られたノードデータを使用して良好に配置されたゾーニングステートメントを公式化してコンピュータが実行するプロセスを発展させることである（ステップ40）。自動化された変換および公式化は、コンピュータがトリム表面のリストから境界表面に対する解析式を計算し（ステップ42）、任意の必要とされる曖昧表面を形成し（ステップ44）、境界表面の十分に近くに位置する任意のノードを消去し、十分な密度を確実にするようにノードを付加するために部品のリストおよび無効スペースを改良し（ステップ46）、スペース（“ゾーン”）の各特有の領域のノードに対するゾーニングステートメントを形成するために各ノードを各解析表面と比較する（ステップ48）４つのステッププロセスである。ノードゾーニングステートメントのリストは初期の良好に配置されたゾーニングステートメントを形成する。境界表面（“ＩＧＥＳｒｅａｄ”）、曖昧表面（“Ａｍｂｉｓｕｒｆ”）、および初期ゾーニングステートメント（“Ｍｉｄｎｏｄｅ”）を発生する自動化されたステップはそれぞれ図６ａ−６ｆ、図７、図８ａ−８ｃに詳細に示されている。コンピュータがＣＡＤモデルをＳＢＣＧフォーマットに変換すると、通常、例えば２進最小化アルゴリズムを使用して変換効率を改良するため、ゾーンを混合し、冗長表面の参照を除去することによりゾーンステートメントを最適化する（ステップ50）ことが望ましいが、必ずしも必要ではない。反復的にゾーニングステートメントをより小さい問題に二分し、その後遺伝アルゴリズムを使用してさらに細分化された問題を解決する２進最小化アルゴリズムが図９ａ−９ｄ（“Ｂｒｅａｋ”、“Ｚｏｎｅｒ”、“Ｒｅｂｕｉｌｄ”）に詳細に示されている。自動化されたコンピュータの実行するステップの１つの例示の１例が図１０に与えられている。
【００２０】
簡単なスロット部品10に対するアルゴリズムの適用が図４、５および８ｃに示されている。ＣＡＤプログラムはリストにスロット部品10のトリムされた表面52のＳ１，Ｓ２，…，Ｓ８を書込む。表面Ｓ１、Ｓ２、Ｓ３、Ｓ４はベース16を限定し、表面Ｓ５、Ｓ６はスロット12の側面を限定し、表面Ｓ７、Ｓ８は丸い端部14を限定している。スロット12内およびベース16外のスペースは無効スペース54を規定する。例えばＦＥツールはそれぞれ部品および任意の無効スペースでメッシュ56および58を生成する。各メッシュの全ての頂点のリストは部品と無効スペースに対する候補ノード60、61の１対のリストを形成する。部品または無効スペースに対して内部のノードは黒い丸で示され、一方、境界表面に位置するノードは中が白い丸で示されている。コンピュータはベース16を限定する境界表面63のＵ１、Ｕ２、Ｕ３、Ｕ４と、スロット12の側面を限定する表面Ｕ５、Ｕ６と、丸い端部14を限定する表面Ｕ７、Ｕ８とを計算し、ノードが部品または無効スペースに位置するかを決定するのに境界表面が十分ではない曖昧表面64のＡ１、Ａ２を形成することによって解析表面62を生成する。コンピュータはその後、任意の曖昧なノードを除去するためにノード60、61のリストを改善する。第１のリスト60は部品上に存在する“黒い丸”のノード65を含んでいる。第２のリスト61は無効表面に位置する“黒い丸”のノード65を含んでいる。境界表面上またはその非常に近くに位置する“白い丸”のノード66は廃棄される。図８ｃに示されているように、ノードゾーニングステートメント67のシーケンスを発生するためにコンピュータは各ノードを各解析表面と比較する。ノードゾーニングステートメント67の表は初期のゾーニングステートメント68を形成する。コンピュータはその後、例えば労力のかかる手動プロセスを使用して生成された図２のｂに示されている同一のゾーニングステートメント26を生成するためゾーニングステートメントを最適化する。説明を明瞭にするために、この例はスロット部品の２次元投影だけを考慮した。しかしながら、全ての原理および技術はさらに一般的な３次元表示と、さらに複雑な部品にも拡張可能である。
【００２１】
［境界表面の計算］  
図４のトリム表面52から図５の境界表面63を計算するタスクは重要である。トリム表面のリストのＩＧＥＳファイル構造はとりわけ複数のエンティティ（トリム表面、ラインセグメント、閉じた曲線、座標変形等）を含んでいる。このような各エンティティはエンティティの幾何学形状の対象物の種類と、エンティティを規定する特別なデータを特定するパラメータ情報へのポインタとを特定するタイプ番号により特徴付けされる。さらに、多数のエンティティタイプはまた任意の回転、変換、またはエンティティのスケーリングを記述する変換マトリックスを参照する。コンピュータが実行するプロセスは各エンティティを検査して、ｂスプライン表面、トーラスまたは球面、回転面、シリンダまたは回転コーンであるか否かを決定する。各エンティティが識別されると、トリム表面は適切な変換（回転、変換またはスケーリング）により対応する解析表面へマップされ、解析表面62のリスト中にエンティティとして記憶される。
【００２２】
ＩＧＥＳ（初期グラフィック交換仕様）標準は主要なＣＡＤシステムによりサポートされる典型的な幾何学的形状の１つである。図６ａ乃至６ｆはＩＧＥＳファイルから直接境界表面を計算するための１つの可能な方法（ＩＧＳｐｒｅａｄと呼ばれるコード）を示している。ここで説明するＩＧＳｐｒｅａｄのバージョンはＰｒｏＥｎｇｉｎｅｅｒにより書かれたＩＧＥＳファイルと共に使用するために特別に書かれたが、他のＣＡＤプログラムにより生成されるＩＧＥＳファイルに対しても同一のことを行うように適合されることができる。さらに、類似のルーチンはＳＴＥＰまたはＡＣＩＳファイルからデータを抽出するために生成されることができる。このコードの計画された拡張は応用可能な表面タイプのリストを拡張するために既に適切である同一の基本技術を使用し、徐々にＴＡＲＴおよびＭＣＮＰ中の解析表面のライブラリ全体をカバーする。
【００２３】
ＩＧＥＳファイル仕様は１９７９年以来のＮＩＳＴサポート標準であり、これはさらに最も古く、ＣＡＤプロダクト間でモデルデータの交換に最も広く使用されている機構である。ＩＧＥＳファイル構造は５つの主要なセクション、即ち、タイトル、ヘッダ、エンティティデータ、パラメータデータ、終了ラインからなる。ファイルの重要な部分はエンティティおよびパラメータデータであり、エンティティセクションは各ノード、ライン、構造表面の存在を特定する整数およびテキストデータからなる。エンティティデータ中の整数の中には、エンティティの幾何学的形状対象物の種類を特定する形式番号と、スペース中のエンティティの任意の回転、変換またはスケーリングを記述する変形マトリックスに対するポインタと、その特定のエンティティに適用するパラメータデータの第１のラインに対するポインタとが存在する。パラメータデータは関係するエンティティの特別な特徴を規定する整数および実数のデータから構成されている。パラメータはまた対象物を特定する助けをする他のエンティティに対するポインタを含んでいてもよい。
【００２４】
ＩＧＥＳｒｅａｄの最上レベルが図６ａに示されている。ＩＧＥＳｒｅａｄは所望の幾何学形状を含んでいるユーザ特定ＩＧＥＳファイルを開くことにより開始する（ステップ70）。コードはタイトルおよびヘッダデータをスキップし（ステップ72）、エンティティおよびパラメータデータを読取り、都合のよいデータ構造で記憶する（ステップ74、76）。アルゴリズムはその後、順番に各エンティティを試験して、エンティティが１次のｂスプライン表面であるか否かを決定し（ステップ78）、そうであるならば、サブルーチンＢｓｃａｌｃを呼出し、これ自体は図６のｂに示されている。次に、コードはデータを通してさらに通過を行い（ステップ80）、このとき回転された表面、即ち特定された軸の周囲の特定の曲線または直線（母点）を回転することにより生成される表面を探す。この通過期間中、アルゴリズムは直線母線のデータを記憶し（ステップ82、84）、湾曲している母線を処理する（ステップ86、88）。湾曲した母線は回転されるとき球面またはトロイドを形成し、これらの表面を再構成する例示的なプロセスは図６ｃに示されている。回転される表面がアークでも線でもないならば、スキップされる（ステップ90）。この通過が完了するとき（ステップ92）、回転されるラインセグメントのリストを通る通過が行われる（ステップ94）。各母線はこれが軸と共通の平面であるか否かを決定するために順次にチェックされ、共通平面ではないならば、線は傾斜され（ステップ96）、回転手順は標準的ではない表面タイプを生成し、それによってエンティティはスキップされる（ステップ98）。次に、ラインセグメントは垂直について試験され（ステップ100）、これらが垂直であるならば、母線は平面を規定し（ステップ102）、平面の式が計算され、図６ｄに説明されているように記憶される。垂直でも曲げられてもいないならば、線は平行性について試験され（ステップ104）、この場合、シリンダが形成される（ステップ106）。図６ｅはシリンダの抽出コードのフローを示している。最後に、軸に対して垂直でも平行でも傾斜でもない任意の直線の母線は回転されるときコーンを規定し（ステップ108）、このアルゴリズム部分は図６ｆに示されている。各主要なステップを以下の段落でさらに詳細に説明する。プロセスは回転される線がなくなるまで反復する（ステップ110）。
【００２５】
［１次のＢスプライン表面］  
前述したように、図６ｂに示されているＢｓｃａｌｃサブルーチンは１次のｂスプライン表面で呼出される。このサブルーチンは１次のｂスプライン表面エンティティから都合のよいデータ構造へパラメータデータを移動する（ステップ112）。そのアルゴリズムはデータが実際に１次のｂスプラインに対して予測された配置に一致するか否か、即ちこれが正確な数のパラメータを有しているか否かを決定するために一連のチェックを行い（ステップ114）、変換カードが存在しないかを決定し（ステップ116）、全ての加重係数が１．０に等しいかを決定する（ステップ118）。これらのいずれかが正しくないならば、アルゴリズムはエラーを出力し、次のエンティティで継続する（ステップ120）。一連のテストに合格したならば、アルゴリズムは４つの各ノードに対する制御点データを識別する（ステップ122）。次に、アルゴリズムは第１のノードから他の３つのノードのそれぞれへ３つのベクトルを形成する（ステップ124）。アルゴリズムは第１の２つのベクトルのクロス乗積とベクトル積の大きさを計算する（ステップ126）。この情報により、アルゴリズムは平面が数学的に良好に形成されていることを示すためさらに２つの試験を完了し、これは試験によって全ての４つのノードが同一線上にはないことを検知し（ステップ128）、４つの点の全てが同一平面上にあることを検知する（ステップ130）。これらの条件のいずれかが満たされないならば、エラーが発生し（ステップ120）、アルゴリズムは次のエンティティへ進む。平面の式が計算される（ステップ132）。平面がまだ規定されていないならば（ステップ134）、サブルーチンは平面の式を記憶し（ステップ136）、終了し（ステップ138）、制御はコードの主体に戻る。
【００２６】
［トロイドおよび球面］  
軸を中心とする円弧の回転により形成されるトロイドまたは球面を抽出するためのアルゴリズムが図６ｃに示されている。この抽出はエンティティの回転軸（ａ１＆ａ２）を規定する点データを記憶することにより開始する（ステップ140）。円弧データ（母線）は変換下で３つの点、即ち円弧の中心および円弧の終端点として記憶される（ステップ142）。所望の解析表面の定義は全て限定されていないので、中心および１つの終端点がアルゴリズム（ｇ’１＆ｇ’２）で特定されることを必要とされる。次に、円弧に関連する変換マトリックスが抽出され（ステップ144）、ｇ’点に適用され、それによって円弧の実際の空間位置（ｇ１＆ｇ２）が計算される（ステップ146）。次に、軸を形成するベクトルが計算され（ステップ148）、その大きさが評価される（ステップ150）。この情報を使用して、アルゴリズムはパラメータＴを計算し（ステップ151）、その後円弧の中心から軸までの距離を計算し、これは主半径ｒ２である（ステップ152）。アルゴリズムはその後、ｇ１からｇ２までのベクトルを形成し（ステップ154）（挿入を参照）、その長さ、即ち短い軸ｒ１を計算する（ステップ156）。ｒ２の値は球面からトーラスを弁別するのに必要な情報を構成する。主半径がゼロに等しいならば（ステップ158）（これは実際に任意の小さい許容値よりも小さいとして構成される）、構造は球面であり（ステップ160）、これを記述するのに必要な全てのデータが計算される。中心は点ｇ１にあり、半径はｒ１である。アルゴリズムは、抽出されるエンティティを先に規定された球面と比較することによって、これが新しいことを確認するためにチェックし（ステップ162）、それが新しい場合にのみそのデータを記憶する（ステップ164）。ｒ２がゼロよりも大きいとき、エンエィティはトロイドである（ステップ166）。この場合、ｇ１に最も近い回転軸上の点の位置と、軸の方位角および上下角を計算することが必要である（ステップ172）。この計算は以下のように行われる。
【００２７】
軸は以下のようにパラメータ化される。  
ｘ＝ｘ１＋ｔ×（ｘ１−ｘ２）  ｙ＝ｙ１＋ｔ×（ｙ１−ｙ２）  
ｚ＝ｚ１＋ｔ×（ｚ１−ｚ２）  
ここでａ１＝（ｘ１，ｙ１，ｚ１）およびａ２＝（ｘ２，ｙ２，ｚ２）  
ｇ１＝（ｘ３，ｙ３，ｚ３）からパラメータ化されたライン上の任意の点までの距離の２乗は以下のようになる。  
ｄ２＝（ｘ３−ｘ１−（ｘ１−ｘ２）ｔ）２＋（ｙ３−ｙ１−（ｙ１−ｙ２）ｔ）２＋（ｚ３−ｚ１−（ｚ１−ｚ２）ｔ）２ 
∂（ｄ２）／∂ｔ＝０を評価し、ｔを解くことによって、最小距離に対応するパラメータｃが与えられる。  
ｔ０＝［（ｘ１−ｘ２）（ｘ３−ｘ１）］＋［（ｙ１−ｙ２）（ｙ３−ｙ１）］＋［（ｚ１−ｚ２）（ｚ３−ｚ１）］  
およびｘ０＝ｘ１＋（ｘ１−ｘ２）ｔ０、ｙ０＝ｙ１＋（ｙ１−ｙ２）ｔ０、ｚ０＝ｚ１＋（ｚ１−ｚ２）ｔ０であり、これらはトロイドの中心座標である。軸の角度はφ＝ａｃｏｓ［ａ（ｚ）／‖ａ‖］およびθ＝ａｔａｎ２［ａ（ｙ），ａ（ｘ）］である。
【００２８】
アルゴリズムは抽出されたエンティティがこれを先の規定されたトーラス毎に比較することにより新しいことを確認するチェックを行い（ステップ174）、これが新しい場合にのみそのデータを記憶し（ステップ176）、最後にアルゴリズムが終了し、制御を主プログラムに戻す（ステップ178）。
【００２９】
［回転されるラインセグメント−平面］  
回転されるラインセグメントからなる識別された表面を最後に通過するとき、ＩＧＥＳｒｅａｄは軸周囲の傾斜ラインの掃引によって生成された表面を識別し、スキップすることにより開始する。次に、アルゴリズムは軸および母線が相互に直交するとき、このようなラインが送信されるときを識別し、結果的な表面は平面である。図６ｄに示されているように回転された平面を抽出するアルゴリズムは軸および母線を構成する２つのラインセグメントに対する点データを抽出することにより開始する（ステップ180、182）。コードはその後、軸および母線に対応するベクトルを形成する（ステップ184、186）。これらの２つのベクトルのドット積が計算される（ステップ188）。ドット積が０ではないならば（ステップ190）、ラインセグメントは直交せず、コードのこの部分はエラーで到達される（ステップ192）。この試験の実行後、軸ベクトルの大きさが計算され（ステップ194）、（軸ベクトルになる）表面に対して垂直のベクトルの方向余弦が計算される（ステップ196、198、200）。最後に、アルゴリズムは新しく計算された平面を先に規定された平面と比較して、平面が新しいことを決定する（ステップ202）。平面が先に識別されていないならば、記憶されるデータは母線の第１の点のｘ、ｙ、ｚ座標と同様に３方向余弦から構成される（ステップ204）。
【００３０】
［回転されるラインセグメント−シリンダ］  
回転されるラインセグメントの次の可能性は軸および母線が平行であることであり、この場合形成される表面は図６ｅに示されているようにシリンダである。最初に、アルゴリズムは２つのラインセグメントの点データを抽出し（ステップ210、212）、ベクトルがそれぞれに対して形成される（ステップ214、216）。次に、軸ベクトルの大きさが評価され（ステップ218）、軸および母線ベクトルのクロス乗積が計算される（ステップ220）。（ステップ222）で計算されたベクトルのクロス乗積の大きさがゼロではないならば（ステップ224）、ラインは平行ではなく、それ故エラーが発生される（ステップ226）。次に、シリンダの半径は円弧の中心に最も近い軸上の点を計算するために使用される技術と同じ技術を使用して計算され、これはＩＧＥＳｒｅａｄのトロイド発生部分で開発された（ステップ228、230）。この場合、適切なパラメータが計算されると、半径自体は近隣点座標の代わりに計算される。その後、軸がｚ＝０平面と交差する点が計算される（ステップ232）。これは軸のパラメータ化された形態の使用と、ｚ＝０のときにｘとｙを解くことにより発見される。最後のシリンダパラメータはこれらが丁度トロイドの場合のように、軸の方位角および上下角を決定することにより計算される（ステップ234）。最後に、シリンダは先の全ての各シリンダに対して比較され（ステップ236）、それが新しい場合にのみ記憶される（ステップ238）。
【００３１】
［回転されるラインセグメント−コーン］  
最後に、ＩＧＥＳｒｅａｄは傾斜されておらず、直交もせず、平行でもない回転されたラインセグメントを処理する。これはコーン（錐体）のファミリである。図６ｆのフロー図は先に説明したエントリで展開された多数の同様の数学的関係を使用する。そのアルゴリズムは必要な点データ（軸ａ１＝（ｘ１、ｙ１、ｚ１）、ａ２＝（ｘ２、ｙ２、ｚ２））を抽出し（ステップ240）、母線ｇ１＝（ｘ３、ｙ３、ｚ３）、ｇ２＝（ｘ４、ｙ４、ｚ４）を発生し（ステップ242）、各ラインセグメントに対するベクトルを形成することにより開始し（ステップ244、245、246）、所望の表面が円錐であることを確認するためにドット積およびクロス積を試験する（ステップ248、250、252、254、256、258）。次に軸および母線の交差点が計算され（ステップ260、262）、これはコーンの頂点である。これは次の２つのラインをパラメータ化し、
軸：ｘ＝ｘ１＋ｔ１×（ｘ２−ｘ１）  ｙ＝ｙ１＋ｔ１×（ｙ２−ｙ１）  ｚ＝ｚ１＋ｔ１×（ｚ２−ｚ１）  
母線：ｘ＝ｘ３＋ｔ２×（ｘ４−ｘ３）  ｙ＝ｙ３＋ｔ２×（ｙ４−ｙ３）  ｚ＝ｚ３＋ｔ２×（ｚ４−ｚ３）  
式の全てのセットが同時に単一の（ｘ、ｙ、ｚ）トリオにより解かれるようにｔ１とｔ２を解くことにより行われる。これは勿論２つの未知の３つの式を生成し、過剰に特定化されるが、ＩＧＥＳｐｒｅａｄは置換を削除する場合の構造を含み、軸に平行なラインセグメントの場合の特異性を除去する。最後に、軸の方位角および上下角が前述したように計算され（ステップ264）、さらに軸と母線との間の角度が計算され、‖ａ×ｇ‖＝‖ａ‖‖ｇ‖ｓｉｎθであり、ここでθはベクトルａとｇとの間の角度であるので、ｓｉｎθ＝‖ａ×ｇ‖／‖ａ‖／‖ｇ‖である。抽出された円錐データは全ての先に特定された円錐と比較され（ステップ266）、これらが特有であることが決定される場合にのみ記憶される（ステップ268）。
【００３２】
［曖昧表面の生成］  
解析表面62のリストを完成するために、コンピュータが実行するアルゴリズムは良好に配置されたゾーニングステートメントに対して必要とされる全ての曖昧表面64を識別し、形成しなければならない。曖昧表面は部分をオリジナルのトリム表面から生成されないゾーンにさらに分割することが必要である付加的な表面を含んでおり、その理由はこれらが境界表面ではないためである。典型的な場合が図５に示されており、ここでは丸い端部を有するスロットは平面Ｓ５とＳ６との間にあり２つの円形の表面Ｓ７とＳ８の外である幾何学形状の種々の領域を弁別するために、いずれかの端部14近くに付加的な表面を必要とする（ＴＡＲＴで構成される表面はユニバースを２つのピース、即ち内部の空間と、表面の外部とにのみ分解することを背景の説明から想起し、“この表面の左上へのスペース”の表記はない）。これらの曖昧表面は図面ではＡ１およびＡ２と付された平面である。ＡｍｂｉｓｕｒｆのアルゴリズムはＩＧＥＳｒｅａｄによる部分から抽出された全ての表面の対の比較である。図７に示されているように、表面の対272のライブラリ270が開発され、これは１以上の曖昧表面の発生が必要となる可能性のある条件274をリストしている。ライブラリはまた２つの表面の交差における弁別で必要とされる曖昧表面276に対する公式を含んでいる。経験がここで説明するツールを使用して複雑なモデルの描写で得られるので、このライブラリは時間で成長することが予測される。
【００３３】
［ノードデータの生成］  
良好に構成されたゾーニングステートメントの公式化に必要なノードデータは、最初に部品リスト60と無効スペースリスト61を含んでいるドメイン全体に対する候補ノードのリストを提供し、その後、図４ｂと４ｃで先に示された部品ノード60のリストと無効スペースノードのリスト61を生成するためにこれらのリストを改善することによりＭｉｄｎｏｄｅにより生成される。候補ノードのリストとその後の個々のリストを生成するためのメッシュ関連方法およびランダムノード生成を含んだ種々の方法が存在する。
【００３４】
［メッシュからのノード生成］  
メッシュからノードデータを発生する技術はエレメントの頂点、エレメントの重心、中間側面のノード、許容されるオフセットノード、エッジ追跡を含んでいる。メッシュ情報はコーナーノードの位置だけでなく、コーナーノードのセットから固体エレメントを作る方法を提供する。コンピュータは１つのノードから別のノードまでのラインを追跡し、ドメインのマテリアル部分だけが（幾つかの警告を有して）トラバースされていることを知る。この例示的なプロセスの目的に対して、図４ｂで示されているようなメッシュは商用のメッシュツールを使用して描写され、そのツールの使用によって得られるデータは少なくとも各エレメントの各頂点のノード座標（または有限の差メッシュの場合は制御量）および各エレメントを含むノードに対する基準であるが、それに限定されないことが仮定される。各方法を以下概説する。
【００３５】
［エレメントの頂点］  
各エレメントの頂点は直接ノードとして使用されることができる。しかしながら、頂点はしばしば境界表面と一致し、表面のどの側面にノードが存在するかを試験しようとするときには選択が困難である。実際に、メッシュ生成中の不正確さは、それが位置することが仮定される表面の非常に近くに、しかし不正確な側面に頂点を生成することにつながる。この問題は許容値を設定し、各頂点とそれぞれの表面との間の距離を測定し、許容値よりも任意の表面に近い任意の点を廃棄することによって緩和される。この方法は実践で行われるために例証されている。しかしながら、全てのこのような頂点が廃棄される可能性があるのでエレメントの１つの層のみによりメッシュされるマテリアルの領域はしばしばこの方法を避ける。この難点は付加的なノードとして重心および中間側面のノードの使用に導く。
【００３６】
［エレメントの重心］  
頂点の各座標の平均値を計算することによるエレメントの重心の決定は典型的に表面と一致しないノードデータを獲得する１方法であり、薄い領域に位置されることができる。しかしながら、凹面の外部またはそれに近い領域を記述するエレメントの場合、薄いエレメントの重心は凹面内で終端することができる。この矛盾はエレメントの３つの頂点が単一の表面上に位置されることを確認し、このようなエレメントの重心を廃棄することによって防止されることができる。
【００３７】
［中間側面ノード］  
薄い領域にノードを位置させる別の方法は、中間ノードを形成するために隣接する頂点の各対の平均座標位置を計算することである。この方法は重心方法よりもさらに多くのノードを発生し、したがって幾何学形状のさらに包括的な表示を行う。１対の頂点が共通の表面に両者ともに位置するか否かを決定するための試験が行われ、このような点は廃棄される。
【００３８】
［許容されるオフセットノード］  
重心および中間エッジノードを使用してさえも、幾つかの領域はノードデータにより捕捉されない可能性がある。この場合には、（前述の）許容距離よりも僅かに大きな距離だけエッジを規定する各頂点から離れて位置する各エレメントのエッジ上にノードを付加することがこれらの領域を捕捉するのに効率的であることが証明されている。
【００３９】
［エッジ追跡］  
非常に複雑な幾何学形状では、先の４つの方法を使用して実現したノード密度は部品を特徴付けするのに十分ではない。これらの場合では、各エレメントの各エッジに沿って追跡し、遭遇する表面交差数をカウントし、それぞれに対して付加的なノードを発生することによる付加的なノードの生成は部品の特徴付けに有効であることが証明されている。
【００４０】
エッジ追跡は１エッジの端部のエレメント頂点を順次にその幾何学形状の各表面と比較し、その表面のどの側面に頂点が存在するかを決定することによって例示的なアルゴリズムで実行される。表面交差数は先の２つの演算で生成されたノードゾーニングステートメントの差を計算することによって計算される。最後に、エッジはただ１つの表面交差が計算されるまで１つの頂点に関して連続的に二分され、その位置はノードの発生に使用される。このプロセスは各表面交差に対応するノードを生成するために反復的に使用される。時によっては、凹面は粗いメッシュエレメントのエッジにより２度交差されることができる。この状態では、両頂点に関して任意の表面の両面に位置する任意の予測されるノードを廃棄することが効率的である。
【００４１】
［ランダムなノード生成］  
幾つかのＣＡＤまたは幾何学形状のモデル化構造は所定の座標位置がマテリアル中またはマテリアル領域を囲む空間の領域或いはその内部に存在するか否かを決定する能力をサポートする。関連する部分がこのような文脈に存在するならば、部品を形式的にメッシュする必要はなく、単に部品よりもやや大きいドメインでランダムノードを十分の密度分布を生成することによって必要なデータを提供する。メッシュ方法を使用して、部品のマテリアルと部品内および部品周囲の無効スペースを別々にメッシュすることが必要であり、対応して、ランダムノードが生成されるとき、それらは２つのグループ、即ち無効ノードとマテリアルノードに分類される必要がある、メッシュの場合、モデルの点の問合せ期間中に進展する不正確さによる曖昧さを回避するために、任意の表面の許容距離内で生成される任意のランダムなノードを廃棄することが賢明である。各座標方向の均一な分布は試験点の適切なアレイを生成するが、データがモデルの種々の領域の複雑性に関して存在するならば、幾つかの利点はこれらの局所的に生成される試験点の数の密度を増加させることにより実現されることができる。
【００４２】
［ゾーニングステートメントの公式化］  
部品の解析表面62とノードデータ60および61の完全なリストが利用可能であると、コンピュータが実行するプロセスは良好に配置されたゾーニングステートメントを公式化することができる。基本的に、アルゴリズムはノードと、表面のリストからのノードと各表面との間の関係を記述する各ノードに対する順序を定められた２進リストを編集する。各これらのリストをここでは“ノードゾーニングステートメント”と呼ぶ。解析表面はスペースを２つの領域、即ち“内部”および“外部”領域に分割することを想起されたい。２進リストは対応するノードを例えば左または右、上または下へ“内部”または“外部”に位置するとして識別し、リスト上の各表面は一連の“真”および“偽”ステートメントまたは２進項の“１”および“０”を使用する。各連続するノードが処理されるとき、これは早期のノードの全ての先に計算された２進リストに対して比較される。リストが既に存在するならば、ノードは無視される。存在しないならば、そのノードに対する２進リストは全ての先の特有のノードを具備するリストに添付され、リストの表は部品の良好に配置されたゾーニングステートメントである。
【００４３】
図８ａに示されているように、コンピュータが実行するＭｉｄｎｏｄｅアルゴリズムはネストされたループ構造であり、それにおいては、図８ｂの各ノード279が順次に選択され、後続するノードに進む前に表面リストからのそれぞれの表面と比較される。特に、リストの第１のノードが選択され（ステップ280）、リストの第１の表面が選択される（ステップ282）。ノードから表面までの距離が計算され（ステップ284）、距離が予め限定された許容値よりも小さいか否かを決定する（適切には１×１０−５距離単位）（ステップ286）。小さいならば、その面のいずれの側に点が実際に存在したかについて計算の誤りを生じる潜在的な不正確性を防止するために、そのノードは廃棄される。アルゴリズムは任意のさらに別のノードがリストに存在するか否かを決定するためにチェックし（ステップ288）、その結果がイエスならば、ノードをインクリメントし（ステップ290）、ループを反復する。ノードが表面に非常に近くないならば、アルゴリズムはノードに関して“表面のセンス”を計算する（ステップ292）。それぞれの解析表面が全てのスペースを２つの領域に分割するので、一方が表面の“内部”を構成し、他は“外部”を構成するためにこれらのスペースのサブ領域の１つを随意選択的に解釈する。アルゴリズムはノードが表面の“内部”であるか否かを決定し（ステップ294）、ノードゾーニングステートメントに“真”または“偽”を添付する（ステップ296、298）。リストにさらに表面が存在するならば（ステップ300）、アルゴリズムは表面をインクリメントし（ステップ302）、距離を計算する（ステップ284）。モデル中のあらゆる表面に関するノードの位置の知識を使用して、ノードゾーニングステートメント67が構成され、これは表面番号により順序付けされ、図８ｃに示されているように、ノードが“内部”であるあらゆる表面に対応する“真”（“＋”）（“１”）エントリと、ノードが“外部”である各表面に対する“偽”（“−”）（“０”）エントリとを有する単一の行の真理値表である。
【００４４】
ノードのゾーニングステートメント67が１つのノードで適切に完了されるとき、そのゾーニングステートメントは全ての先のノードで先に計算されたゾーニングステートメントと比較される（ステップ304）。新しく計算されたゾーニングステートメントが真に新しいならば、これは特有のノードゾーニングステートメントのリストに添付される（ステップ306）。全てのノードがこのようにして処理されるとき、特有のノードゾーニングステートメントの完全なリストはその部品に対する完全なゾーニングステートメント68を構成すると言うことができる（ステップ308）。図８ｂに示されているように、表面から十分に離れて位置する各ノードはＭ１，Ｍ２，…，Ｍ６としてラベルを付される。同じノードゾーニングステートメントを有するノードはこの図面では同一のラベルを有するとして示される。
【００４５】
部品の真理値表（ゾーニングステートメント）Ｔと任意の無効スペースの真理値表Ｆとが計算されると、解が良好に配置されるために絶対的に必要な真理値表エントリを予め計算するのに（このプロセスでは必要ではないが）しばしば有効である（ステップ309）。これは全てのエントリが初期的に誤りである指定テーブルＭを生成することにより行われる。マテリアルの真理値表Ｔの行は１つづつ無効の真理値表Ｆの各行に対して比較される。１対のこのような行がただ１つのエントリだけ異なることが発見されたならば、エントリは常に良好に配置される解に対する任意の試行解中に維持されなければならないことが確実になる。したがって、Ｍテーブルのエントリは真に設定される。このようなエントリが消去されるならば、幾つかの無効部分からマテリアル部分を弁別するものは何もなく、２つはオーバーラップしなければならず、これは物理的に可能ではない。
【００４６】
部品の組合せ幾何学形状ステートメントを構成するためにＭｉｄｎｏｄｅアルゴリズムにより生成されるゾーニングステートメントを使用することが可能であるが、実際には、部品に対する最適化されたゾーニングステートメントは、放射転送解析を行うとき典型的に２次の大きさの改良を作動時間中に提供することができる。それ故、このプロセスの最終的なステップは部品のゾーニングステートメントについて最適化ルーチンの使用を示唆している（ステップ310）。
【００４７】
［ゾーニングステートメントの最適化］  
最適化はステートメントの冗長表面とマージゾーンに対する参照の消去を必要とし、部品および無効スペースリストの両者における全てのノードの位置をエンティティを含む解析表面（境界表面と曖昧表面の両者）へ関連付ける真理値表（図８ｃに示されているベースゾーニングステートメント68）について動作することにより実現される。通常の２進最小化問題の特別な公式化である最適化プロセスは任意の数の形態を取ることができるが、現在の最良の実際のものは部品のドメイン（例えば“正値の真理値表”）を反復的にさらに分割し、遺伝アルゴリズムを使用して各十分に小さいピースを独立して解き、分解プロセスを介して後退し、全体の幾何学形状が再度一体化するまで、各再結合された再ドメインで解の手順を反復する包括的な方法である。このアルゴリズムの十分な説明は2004年出願の米国特許出願（発明の名称“Method for Solving the Binary Minimization Problem and a Variant Thereof”）に記載されており、これは本願で参考文献とされている。
【００４８】
特に、“ブレーク”ルーチンはドメイン（真理値表）をより小さいサブドメイン（サブテーブル）へ反復的に二分割する。“ゾーナー”ルーチンは最低レベルのサブテーブルについて動作し、それぞれに対して最適化されたゾーニングステートメントを計算する。“リビルド”ルーチンは最低レベルで開始し、後方に動作する二分割されたサブテーブルを反復的に再結合する。最低レベルのサブテーブルからのゾーニングステートメントを使用して、リビルドはさらに次に高いレベルでゾーニングを改善する。完了したとき、リビルドは問題全体に対して最適化されたゾーニングステートメントを表す単一の真理値表を生成する。この手順は解の時間に関して（同時に）全体的な幾何学形状に適用されるような一般的な解手順をしのぐだけでなく、典型的にさらに最適な解に到達する。このプロセスは一体化の反復毎に動作解、およびそれに続く全ての最小のサブドメインの解を提供する付加的な利点を有する。したがって、非常に複雑であるため最終的な一体化ステップが非常に時間がかかり厄介である任意の幾何学形状に対しては、動作解は任意の介在時間で出力から突き止められることができる。
【００４９】
［ブレーク］  
二分割プロセスの開始では、入力データの完全なセットは変換アルゴリズムにより供給されることが予測される。この入力データは少なくとも２つの真理値表を含んでいなければならず、第１の表は［真］値の出力を生じる明確に知られている入力セットを表し、第２の表は［偽］値の出力を生じる明確に知られている入力セットを表している。幾何学形状に関しては、これらはそれぞれマテリアルおよび無効の真理値表として構成されることができる。これらのテーブルは完成されることが必要とはされず、即ち共にこれらは列の入力値のそれぞれ可能なブール組合せを表す必要はない。少なくとも幾何学形状の公式化の場合には、ある入力の組合せは可能ではなく、それ故徹底的に完全な表を必要とするためにこの解の手順のフレームワークを制限する。入力はまた指令の真理値表を含んでいてもよい。これらの指令エントリはまた二分割手順に与えられることができ、これは問題が二分されるときこれらを再度公式化することでき、必要な情報を通過し、アルゴリズムが進行するときにツリーをバックアップする。
【００５０】
入力は二分割線として選択するための任意の演繹的な列（表面）のランキングも含むことができる。論理的な二分割候補はアルゴリズムが進行するときに計算されることができ、これらが入力で有効である要件はない。二分割の列はノード加重表面選択、領域加重表面選択、パラメータによるタイプまたは表面選択による表面選択を使用して選択されることもできる。最も頑丈な構造はこれらの規準の幾つかを同時に使用する。これは最も最適な表面がプロセスの早期に選択されることを可能にし、これは最小の計算時間で非常に最適にされた解を生成することが立証されている。
【００５１】
［ノード加重表面の選択］  
真理値表データがオリジナルの幾何学形状の有限要素分離を使用して構成されるとき、サイズ変更可能なノード点の断片は幾何学形状の境界表面に位置する。最もノードでポピュレートされている表面は二分割の列として選択される。
【００５２】
［領域加重表面の選択］  
有限要素分割が利用可能ではないか、あるいは非常に高価であるために計算できない幾何学形状の公式化では、部品の各限定された外部表面の領域が計算されることができる。魅力的な二分割表面は大きい外部表面領域を限定する表面である。
【００５３】
［表面タイプによる表面選択］  
しばしば、幾何学形状部分を形成する限定されていない表面は多くの異なるタイプ、例えば球面、シリンダ、平面である。部品の幾何学形状の演繹的な知識は良好な二分割表面を作る表面のタイプを決定することができる。
【００５４】
［表面パラメータによる表面選択］  
１つのパラメータまたは１組のパラメータが良好の候補と悪い候補とを弁別するために使用されることができる。表面エンティティの半径または角度の整列の使用は二分割表面の選択を基礎付ける特定の重要なパラメータである。
【００５５】
二分割プロセスは部品に対する真理値表Ｔと、無効スペースに対するその補数Ｆと、関連する強制テーブルＭと、二分割列とを選択することにより開始する。コンピュータはその後、二分割列とそれらの補数の真理値表Ｔのサブテーブルを生成する。Ｍテーブルは真理値表のサブテーブルの分割に対応するようにサブテーブルに分割される。最終的に、コンピュータはＴサブテーブル、補数およびＭサブテーブルを簡単にする。全てのサブテーブルは記憶され、プロセスはこれらが十分に小さくなるまで各Ｔサブテーブルに対して反復される。
【００５６】
二分割プロセスのフローチャートおよびグラフィック表示が図９ａおよび図９ｂに示されている。プロセスは行のしきい値数よりも多い行を有する任意の残りの真理値表が存在するか否かを決定することにより開始される（ステップ320）。しきい値は随意選択的に設定されることができるが、適切な値１５は試行錯誤により選択された。任意のこのようなテーブルが存在するならば、プロセスは真理値表Ｔ321とその補数Ｆを選択し（ステップ322）、真理値表Ｔの二分割列を選択する（ステップ324）。
【００５７】
二分割列が選択されると、さらに大きい真理値表を２つに分割することは２つの新しいもっと小さいサブテーブル323、325を単に構築することにより行われ、一つは選択された列に対するエントリとして［真］を有するオリジナルテーブルＴＡからの各行のコピーである（ステップ326）。他のサブテーブルＴＢは選択された列で［偽］を読取る全ての行のコピーを得る（ステップ328）。この動作は［真］値の真理値表で行われる。さらに、（［真］の真理値表と１対１で対応する行および列を有する）強制エントリのアレイＭは同様に２つのピースに分割されることができ、真理値表の対応する行がその列で［真］を有するかまたは［偽］値を有するかにしたがって、各行は二分割列の［真］ＭＡまたは［偽］ＭＢの側に対応するサブテーブルに割当てられる（ステップ329）。２つのコピーが［偽］値の真理値表（ＦＡ、ＦＢ）から形成され（ステップ330、332）、１つのコピーがそれぞれ半分の［真］値の真理値表に割当てられる。次に、付加的な情報が各２つの新しいコピーに添付され（ステップ334、336）、各サブテーブルはそれに添付される反対の半分の［真］値の真理値表の行を有する（ＦＡ＝Ｆ＋ＴＢ；ＦＢ＝Ｆ＋ＴＡ）。これは解が進行するとき、２つの低いレベルの解がいかなる条件下でも重複しないことを確実にする。
【００５８】
二分ルーチンのステップ毎に、真理値表のサブテーブルのコピーは後で再構成期間中に、使用するために記憶される。例示的な最適化ルーチンでは、真理値表のサブテーブルは同一の行を除去し、部品を表示するのに必要ではない全ての列を除去し、最後に列の選別によって生成される全ての同一の行を除去することによって各ステップで簡単にされる（ステップ342、344）。全てのステップにおいて、プロセスのその点でサブテーブルにおいて存続する（本来の真理値表を参照する）列および行の順序付けられたリストが記憶される。さらに、幾つかの種類の可逆性の通路構造は反復的な二分割が行われるときに記憶され、それによってマップが構成されることができ、これはファイルの適切な対が適切な順序で再度一体化されることを可能にし、全てをオリジナルの真理値表の構成に戻す。
【００５９】
最後に、２分割プロセスは全ての残りの［真］値の真理値表のサブテーブルがあるしきい値よりも小さい点に対して反復されるとき、即ちステップ320が誤りであるとき、所望の最適化ルーチン（“ゾーナー”）がこの最低レベルにおいて適用されることができる。これらの低レベルの最適化は相互に独立しているので、これらは所望ならば並列プロセスとして実行されることができる。本発明の例示的な構成では、遺伝アルゴリズムを含む２進最小化アルゴリズムが真理値表の最適化に使用されるが、任意の最適化ルーチンはこのプロセスで適切に使用されることができる。
【００６０】
［ゾーナー］  
“ゾーナー”で実行される２進最小化アルゴリズムは各サブテーブルの表す問題を解決し、これは無効スペースから部品を分離するために必要な最少のゾーンおよび解析表面を有する簡単化された３ゾーニングステートメントとして部品のサブドメインを表している。現在の実施形態では、これは３表示を使用してシードオーガニズムを形成し、シードから初期オーガニズムのプールを生成し、ポピュレーションが安定化するまでそのプールを育成し、最高のスコアの３ゾーニングステートメントを選択することにより各真理値表のサブテーブルで実現される。証明された理論は親の子供が良好なオーガニズムであり高いスコアであることである。この遺伝アルゴリズムはランダムまたは徹底的なサーチよりも非常に高い速度で最適化されたゾーニングステートメントに集中する。
【００６１】
図９ｃに示されているように、“ゾーナー”は真理値表ファイルを開き（ステップ350）、真理値表のサブテーブルファイルを読取って記憶し（ステップ352）、その後オーガニズムの初期ポピュレーションを生成するループに入り、マテリアル真理値表から直接形成されたオーガニズムで開始する（ステップ354）。シードオーガニズムは各真理値表Ｔエントリを“１”にマッピングし、各偽テーブルエントリを“−１”にマッピングすることにより形成される。オーガニズムの初期のプールはシードを複製し、幾つかの＋１、−１値をゼロに変更することにより生成される。これは、所定の行の強制エントリを除く全て、または隣接する行の異なるエントリに対してランダムに行われることができる。例えば全体で全ての最終的なポピュレーションの１０分の１のサイズのオーガニズムのプールが形成されるとき、各オーガニズムは作動中にスコアされる（ステップ356）。オーガニズムがＦテーブルからのエントリを許容するならば（例えば部品として無効スペースの１点を識別する）、これはゼロのスコアを割当てられる。そうでなければスコアはオーガニズムの特有の行数とこれらの特有の行のゼロではないエントリ数との積に反比例する。したがって偽のエントリを導入せずに少数の行と多数のゼロを有するオーガニズムは非常に高いスコアを有する。（ステップ358で）しきい値のスコアを満たさない任意のオーガニズムはセーブされず、置換が直ちに行われる（ステップ360）。
【００６２】
十分な量のオーガニズムが生成され保存されるとき（ステップ362、364）、オーガニズムはスコアにより（例えば共通の分類ルーチンＨｅａｐｓｏｒｔを使用して）分類される（ステップ366）。後にループを通過するとき、オーガニズムの下部９０％は破壊されるが（ステップ368）最初にループを通過するとき、全体のプールの１０％だけが生成され、したがってオーガニズムは破壊されない。プールはその後、種々の突然変異技術による無性２進再生のような育成手順により満たされる（ステップ368）。この点で、アルゴリズムはポピュレーションが安定性を示すまで、その主要なタスク、即ちスコアリング（ステップ370）、ランキング（ステップ372）、キリング（ステップ374）、増殖（ステップ368）を反復的に開始する（ステップ376）。“ポピュレーションの安定性”は生存者のスコアの変化のない組合せおよび幾つかの連続する世代の同じトップスコアの反復として規定される。安定性は成功した結果が得られることが保証されるが、しきい値が非常に大きく設定されるならば、遭遇する結果がかなり最適な解に合理的に近づく場合である可能性もあり、そうではない場合もある可能性がある。安定されると、ゾーナーはゾーン定義を出力ファイルに書込み（ステップ378）、さらにゾーンへのファイルが存在するか否かを決定する（ステップ380）。
【００６３】
［再構築］  
各最小の最適化問題に対する解決策は２つのサブテーブルが再度一体にされるときに、ブックキーピングを簡単にする役目を行う真理値表のアナログフォーマットで説明されることができる。この形態では、行−列フォーマットは１対１の対応で保持されるが、テーブルのエントリはそれぞれ［真］、［ｎ／ａ］、［偽］に対応する３データ、例えば（１，０，−１）である。最適化された解中の行番号を保持するために、２以上の行の解を含む任意の項の多数のコピーが解テーブル中で形成される。これは重複解の行はいずれも実際に単一の解の項だけを表しているので、解が実際に、真理値表に行が存在するような多くの項を含んでいることを意味しない。
【００６４】
中間テーブルが二分割プロセス中に記憶されるならば、２つの低いレベルのサブテーブルを再度一体化することは必要ない。これらの高いレベルのサブテーブルはそれぞれその固有の権利でフレッシュな問題のステートメントであるが、低いレベルのサブテーブルに対する２つの解テーブルを使用することは高いレベルの問題の解を生成するが、さらに高いレベルで解を最適にすることが可能である。解テーブルは解の行をそれらの適切な位置にインターリーブすることにより組合わされ（高いレベルの真理値表は行を２グループに分割することにより２つに分断され、各解の行は低いレベルの真理値表の行に直接対応することを想起されたい）、任意の欠如した列は［ｎ／ａ］３相関（０）で充填される。この新しい解テーブルを開始点として使用して、最適化は典型的に計算時間において数桁の大きさだけ頻繁で大幅に簡単にされる。
【００６５】
解および解の再統合手順は連続して高いレベルのサブテーブルに適用され、反対に二分割手順を複製する。非常に複雑化された問題に対しては、これはサブテーブルが非常に大きくなったとき、最適化に関するペイオフは増加された解時間だけの価値がないことになる。この解手順は、任意の中間解が問題全体の有効な解（およびしばしば高度に最適化された解）であるので早過ぎる終了に対して容易に修正可能である。この場合には、前述の手順にしたがって全ての最高レベルの解を結合し、実効的な解が設定されることができることだけが必要である。再統合および高いレベルの解プロセスはまた対によっても独立しており、所望ならば並列アルゴリズムとして構成することも非常に簡単である。
【００６６】
前述の論理を実行する例示的なアルゴリズムは図９ｄに示されている。この手順では、ループ構造は反復的な二分割および簡単化により生成されるサブテーブルのツリーで開始し、その場合に各ブランチの最低レベルだけが解かれる。手順は全てのサブテーブルが２進再結合により集められるときに終了し、解全体が計算される（ステップ382）。それぞれループを通過することによって、最低の残りの解かれていないレベルからの１対の相補サブテーブル（ＴとＦ）が選択される（ステップ384）。真理値表Ｔのサイズが増加すると、新しい解を計算するのにかかる時間の長さは劇的に増加することが発見されている。さらに、解における実質的な改良の可能性は低いレベルの解が与えられるとき、Ｔの大きさにより減少することが発見されている。それ故、現在の構成はＴが増加するとき解の安定性の許容値を減少させ、したがって計算のための改良が行われないか高価であるとき、過大な時間量が費やされない（ステップ386）。
【００６７】
解の手順は２つの低レベルの解テーブルを（ＴＡおよびＴＢの解から）識別し、これらの解から遺伝情報を抽出し、任意の除去された列に対応する各行内にゼロを付加することによって高いレベルのサブテーブルの要求を満たすようにそれを再度公式化し、Ｔに一致するように解の行をインターリーブすることにより開始する（ステップ388）。この試験的な解の遺伝子はＴに対する解を表す遺伝オーガニズムのポピュレーションをシードするためにオーガニズムの生成に使用される（ステップ390）。次に、ゾーナーアルゴリズムは提案された解を遺伝的に改良するために予め決定された許容値と試用解と協調して試用される（ステップ392）。許容値が得られたとき、その解は記憶され（ステップ394）、低いレベルの真理値表は消去されるか、解かれたとしてフラグが与えられる（ステップ396）。解がＴに対して完全であるとき、ループはその後続の最低のレベルの未解決のサブテーブルを識別することにより継続する。
【００６８】
［例：ＴＡＲＴフォーマットに対するＰｒｏＥ  ＣＡＤ  モデル］  
図１０の例示的なプロセスはＰｒｏＥ  ＣＡＤ部品データからＴＡＲＴフォーマットで組合せ幾何学形状を生成するための完全な変換方式の１つの例である。第１のステップは部品の幾何学形状を表すＩＧＥＳファイル（Ｐａｒｔ．ｉｇｓ）402をＰｒｏＥから抽出することである（ステップ400）。このデータは部品のトリムされた境界表面データを含んでいる。ＰｒｏＥのＰｒｏＭｅｃｈａｎｉｃａパッケージは部品とその周囲のスペースを分離するために使用されることができる（ステップ404）。これらの２つのメッシュはそれぞれＰａｒｔ．ａｎｓ406とＰａｒｔ．ａｎｓ408としてＡＮＳＹＳフォーマットで記憶される。
【００６９】
次のステップはＩＧＥＳｒｅａｄルーチンを動作させることである（ステップ410）。これは入力としてＩＧＥＳファイルＰａｒｔ．ｉｇｓを受取り、出力としてファイルＰａｒｔ．ｓｕｒ412の部品に対する境界表面のプリミティブを生成する。Ａｍｂｉｓｕｒｆルーチンが候補の曖昧表面プリミティブを計算するために実行される（414）。出力ファイルＰａｒｔ．ｚｓｒ416は境界と曖昧表面プリミティブとの組合わされたリスティングである。
【００７０】
Ｍｉｄｎｏｄｅルーチンは１つの幾何学形状からの問題を論理に関して厳密に述べられた形状に変換する（ステップ418）。Ｐａｒｔ．ａｎｓファイル中の各ノードはＰａｒｔ．ｚｓｒファイルの各表面と比較され、真理値表の行が構成され、それは全ての表面に関して（二進の意味で）ノードの位置を表し、各境界表面は全ての空間を正の領域（真）と負の領域（偽）とに分割することを想起されたい。真理値表は各メッシュ点に対する真の行情報を収集する。Ｍｉｄｎｏｄｅはまたメッシュデータから付加的な点を計算し、同様に真理値表にこれらを集収する。このプロセスは部品周辺およびその内部の無効スペースに対してＰａｒｔ．ａｎｓ中のメッシュで反復される。次に、Ｍｉｄｎｏｄｅは無効領域からマテリアル領域を弁別するのに絶対的に必要ではない重複する行および表面を除去することによって真理値表を簡単にする。これらの簡単にされた真理値表はＰａｒｔ．ｎｏｄ420とＰａｒｔ．ｎｏｄ422中に記憶される。最後に、Ｍｉｄｎｏｄｅはファイルに付加的なデータを書込み、それらのデータとしては、Ｐａｒｔ．ｓｎｘ424は簡単にされた真理値表中で使用されるＰａｒｔ．ｓｕｒから順序付けされた表面インデックスをリストし、Ｐａｒｔ．ｍｓｔ426は無効スペースから部品を弁別するのに必要であるために予め計算されることのできる真理値表エントリを示すマテリアルの真理値表のアナログであり、Ｐａｒｔ．ｎｚｆ428は（番号がデフォルト１である点に）いくつのＰａｒｔ．ｎｏｄファイルが存在するかについての情報を伝送するために生成され、Ｐａｒｔ．ｒｅｃ430は二分割動作に対する良好な候補である表面についての情報を含んでいる。
【００７１】
Ｂｒｅａｋルーチンは問題の反復的な二分割を行い（ステップ432）、真理値表を簡単にし、各ステップでＰａｒｔ．ｎｏｄ434、Ｐａｒｔ．ｎｏｄ436、Ｐａｒｔ．ｍｓｔ438、Ｐａｒｔ．ｓｎｘ440ファイルの２つのセットを生成する。二分割が進行するとき、Ｐａｒｔ．ｂｂｄファイル442はプロセスを通じて二分割ツリーの追跡を維持するために連続して更新される。また、Ｐａｒｔ．ｎｚｆファイルはブックキーピングに対して生成されるファイルの総数で連続して更新される。
【００７２】
Ｚｏｎｅｒコードはファイルツリーの全ての最低レベルのメンバで動作し、（３理論で）それぞれに対して最小化されたゾーニングステートメントを計算する（ステップ444）。これらはＰａｒｔ．ｇｅｎ＃ファイル446である。さらにＰａｒｔ．ｚｏｄファイル448が各反復で生成され更新され、これはファイルツリーの最低のレベルのメンバを表すファイルに関する情報を含んでいる。
【００７３】
次に、再構築ルーチンは最低レベルで開始し、後方に作動する二分割された真理値表を反復的に再結合する（ステップ450）。最低レベルのエンティティからのゾーニングステートメントを使用して、再構築はさらに次に高いレベルでゾーニングを改善する。完了するとき、再構築は問題全体の計算され最小化されたゾーニングステートメントを表す単一のＰａｒｔ．ｇｅｎファイル452を生成する。
【００７４】
図１０からの例示的な手順の最後のステップはルーチンＭａｋｅＴＡＲＴであり、これは問題の幾何学形状表示を再度導入し、表面プリミティブ情報（Ｐａｒｔ．ｚｓｒ）と計算されたゾーニングステートメント（Ｐａｒｔ．ｇｅｎ）とを結合して、ＴＡＲＴコード（456）に対するＰａｒｔ．ｔａｒｔ  ｉｎ  ｆｉｌｅ454の動作入力デックを形成する。
【００７５】
本発明の幾つかの例示的な実施形態を示し説明したが、多数の変更および代わりの実施形態が当業者により行われるであろう。このような変更および代わりの実施形態が考慮され、特許請求の範囲に限定されているように本発明の技術的範囲を逸脱せずに行われることができる。
【図面の簡単な説明】
【００７６】
【図１】簡単な２次元部品の斜視図および平面図。
【図２】強調されている境界表面と曖昧表面および、幾何学形状の典型的なゾーニングステートメントを有する２次元部品の平面図。
【図３】本発明にしたがった高次の複雑な幾何学形状をＣＡＤモデルから表面ベースの組合せ幾何学形状（ＳＢＣＧ）フォーマットに変換するための自動化プロセスのフローチャート。
【図４ａ】ＣＡＤプログラムにより生成されるトリム表面を有する２次元部品の平面図。
【図４ｂ】それぞれ２次元部品と無効スペースに対するＦＥプログラムにより発生されるノードメッシュの平面図。
【図４ｃ】それぞれ２次元部品と無効スペースに対するＦＥプログラムにより発生されるノードメッシュの平面図。
【図５】解析的な境界および曖昧表面を示している２次元部品の平面図。
【図６ａ】解析的な境界および曖昧表面をＩＧＥＳファイル中の構成データから抽出するための詳細なフローチャート。
【図６ｂ】解析的な境界および曖昧表面をＩＧＥＳファイル中の構成データから抽出するための詳細なフローチャート。
【図６ｃ】解析的な境界および曖昧表面をＩＧＥＳファイル中の構成データから抽出するための詳細なフローチャート。
【図６ｄ】解析的な境界および曖昧表面をＩＧＥＳファイル中の構成データから抽出するための詳細なフローチャート。
【図６ｅ】解析的な境界および曖昧表面をＩＧＥＳファイル中の構成データから抽出するための詳細なフローチャート。
【図６ｆ】解析的な境界および曖昧表面をＩＧＥＳファイル中の構成データから抽出するための詳細なフローチャート。
【図７】曖昧表面を生成するための規則表。
【図８ａ】初期ゾーニングステートメントを公式化するためのステップの説明図。
【図８ｂ】初期ゾーニングステートメントを公式化するためのステップの説明図。
【図８ｃ】初期ゾーニングステートメントを公式化するためのステップの説明図。
【図９ａ】特定の２進最小化アルゴリズムを使用して、初期ゾーニングステートメントを最適化するためのステップの説明図。
【図９ｂ】特定の２進最小化アルゴリズムを使用して、初期ゾーニングステートメントを最適化するためのステップの説明図。
【図９ｃ】特定の２進最小化アルゴリズムを使用して、初期ゾーニングステートメントを最適化するためのステップの説明図。
【図９ｄ】特定の２進最小化アルゴリズムを使用して、初期ゾーニングステートメントを最適化するためのステップの説明図。
【図１０】自動化された変換プロセスの１実施形態の詳細なフローチャート。
【図１ａ】
2006528814.tif 000003
【図１ｂ】
2006528814.tif 000004
【図２ａ】
2006528814.tif 000005
【図２ｂ】
2006528814.tif 000006
【図３】
2006528814.tif 000007
【図４ａ】
2006528814.tif 000008
【図４ｂ】
2006528814.tif 000009
【図４ｃ】
2006528814.tif 000010
【図５】
2006528814.tif 000011
【図６ａ】
2006528814.tif 000012
【図６ｂ】
2006528814.tif 000013
【図６ｃ】
2006528814.tif 000014
【図６ｄ】
2006528814.tif 000015
【図６ｅ】
2006528814.tif 000016
【図６ｆ】
2006528814.tif 000017
【図７ａ】
2006528814.tif 000018
【図７ｂ】
2006528814.tif 000019
【図８ａ】
2006528814.tif 000020
【図８ｂ】
2006528814.tif 000021
【図８ｃ】
2006528814.tif 000022
【図９ａ】
2006528814.tif 000023
【図９ｂ】
2006528814.tif 000024
【図９ｃ】
2006528814.tif 000025
【図９ｄ】
2006528814.tif 000026
【図１０】
2006528814.tif 000027
【国際調査報告】
2006528814.tif 000028
2006528814.tif 000029
2006528814.tif 000030
2006528814.tif 000031