(57)【特許請求の範囲】
【請求項１】
少なくとも１つの切削部と少なくとも１つの非切削部とを有する切削ツールを用いて、
工作物の機械加工をシミュレートするための、コンピュータ実施方法であって、
前記工作物のモデリングされた体積を表わすデクセルの集合であって、各デクセルは、線と前記工作物のモデリングされた前記体積との間の交差を表わす少なくとも１つの線分（ｓｅｇｍｅｎｔ）の集合を含む、該デクセルの集合と、
精密な動きである、３次元空間における線を含む前記切削ツールの軌道と、
メッシュ（Ｍ）の集合であって、各々が前記切削ツールのそれぞれの切削部又は非切削部を表わす、該メッシュ（Ｍ）の集合と
を提供するステップ（Ｓ１０）と、
各デクセル（Ｄ）について、
前記切削ツールの軌道に従って、前記デクセル（Ｄ）の線と前記メッシュとの間の交差の時間（ｔ）を、交差の高さ（ｈ）の関数として記述する全ポリライン（Ｌ1，Ｌ2，Ｌ3）の端点を各メッシュ（Ｍ）について計算するステップ（Ｓ２０）と、
前記デクセルに沿って前記切削ツールと前記工作物との衝突をテストするステップ（Ｓ３０）であって、前記テストは、全メッシュの全ポリラインの集合のより低い包絡線に属する位置に対応する高さ値について、前記位置に属する前記ポリラインが非切削部に関連付けられているか否かを決定するステップを含み、前記高さの値は前記デクセルの線分に属する、該テストするステップ（Ｓ３０）と
を備えたことを特徴とするコンピュータ実施方法。
【請求項２】
前記全ポリライン（Ｌ1，Ｌ2，Ｌ3）の前記端点を計算するステップ（Ｓ２０）は、各メッシュ（Ｍ）についておよびそれぞれのポリラインの各端点について、
前記それぞれのポリラインに関連付けられた前記メッシュの全ての面に基づいて、前記端点に対応する前記デクセルの前記線の交差を伴った、前記切削ツールの前記軌道に従って、前記メッシュの面によって掃引された体積（Ｓ（τ））の境界面を決定するステップ（Ｓ２８２）と、
前記デクセルの前記線と前記決定された境界面との間の交差に基づいて、時間と高さを計算するステップ（Ｓ２８４）と
を備えたことを特徴とする請求項１記載のコンピュータ実施方法。
【請求項３】
前記全ポリライン（Ｌ1，Ｌ2，Ｌ3）の前記端点を計算するステップ（Ｓ２０）は、各メッシュ（Ｍ）について、
前記メッシュ（Ｍ+）の可視部を決定するステップ（Ｓ２２）であって、前記可視部は前記切削ツールの軌道の方向へ向かった前記メッシュの部分である、該決定するステップ（Ｓ２２）と、
前記切削ツールの前記軌道に従って、前記可視部によって掃引される体積（Ｓ（Ｍ+））の境界（∂Ｓ（Ｍ+））を計算するステップ（Ｓ２４）と、
前記端点に対応する前記デクセルの前記線の交差を伴った、前記メッシュの面によって掃引された体積Ｓ（τ））の境界面を決定する前記ステップ（Ｓ２８２）および時間と高さを計算する前記ステップ（Ｓ２８４）を、それぞれのポリラインの各端点について、繰返して行うステップ（２８）であって、前記境界面を決定すること（Ｓ２８２）は、前記可視部によって掃引される体積（Ｓ（Ｍ+））の前記計算された境界（∂Ｓ（Ｍ+））のそれぞれの境界面を識別することを含む、該繰返して行うステップ（２８）と
をさらに備えたことを特徴とする請求項２記載のコンピュータ実施方法。
【請求項４】
前記全ポリライン（Ｌ1，Ｌ2，Ｌ3）の前記端点を計算するステップ（Ｓ２０）は、
各メッシュ（Ｍ）について、前記可視部の面によって掃引されたボリュームに対する隣接情報を決定するステップ（Ｓ２６）と、
各それぞれのポリラインについて：
前記ポリラインの第１の端点に対応する前記デクセルの前記線の交差を伴った、前記メッシュの面によって掃引された体積（Ｓ（τ））の境界面を決定すること（Ｓ２８２）であって、前記可視部によって掃引される体積（Ｓ（Ｍ+））の前記計算された境界（∂Ｓ（Ｍ+））の第１の面を幾何学的計算によって決定することからなり、前記第１の面は前記デクセルの前記線によって交差されている、該決定するステップ（Ｓ２８２）と、
前記ポリラインの第２の端点に対応する前記デクセルの前記線の交差を伴った、前記面によって掃引された体積（Ｓ（τ））の境界面を決定すること（Ｓ２８２）であって、前記可視部によって掃引される体積（Ｓ（Ｍ+））の前記計算された境界（∂Ｓ（Ｍ+））の第２の面を前記隣接情報に基づいたトポロジ伝播によって決定することからなり、前記第２の面は前記デクセルの前記線によって交差されている、該決定するステップ（Ｓ２８２）と
をさらに備えたことを特徴とする請求項３記載のコンピュータ実施方法。
【請求項５】
前記繰返して行うステップ（２８）は、前記デクセルの集合上で、並列計算を実行することを特徴とする請求項４記載のコンピュータ実施方法。
【請求項６】
前記第１の面を決定するステップ（２８２）は、前記デクセルの集合上で、２次元グリッドの要素と見なされるデクセルにわたる前記境界（∂Ｓ（Ｍ+））の全ての要素のラスタライゼーションを実行することを特徴とする請求項５記載のコンピュータ実施方法。
【請求項７】
製品を生産するための方法であって、該方法は、請求項１ないし６のいずれかの機械加工をシミュレートするための方法が繰返され、およびこれにより工作物上で機械加工フェーズが実行されるシミュレーションフェーズを含むことを特徴とする方法。
【請求項８】
請求項１ないし６のいずれかの方法を実行するための命令が記録されたメモリに結合されたプロセッサを備えたことを特徴とするシステム。
【請求項９】
前記プロセッサは、グラフィカル・プロセッシング・ユニットであることを特徴とする請求項８記載のシステム。
【請求項１０】
請求項１ないし６のいずれかの方法を実行するための命令を含むことを特徴とするコンピュータプログラム。
【請求項１１】
請求項１０のコンピュータプログラムが記録されたことを特徴とするコンピュータ読取可能記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータプログラムおよびシステムの分野に関し、より詳細には、工作物の機械加工をシミュレートするための方法、システム、およびプログラムに関する。
【背景技術】
【０００２】
オブジェクトの設計、エンジニアリング、および製造に関する市場には、いくつかのシステムおよびプログラムが提供されている。ＣＡＤはコンピュータ支援設計の頭字語であり、例えば物体を設計するためのソフトウェアソリューションに関する。ＣＡＥはコンピュータ支援エンジニアリングの頭字語であり、例えば将来の製品の物理的挙動をシミュレートするためのソフトウェアソリューションに関する。ＣＡＭはコンピュータ支援製造の頭字語であり、例えば製造のプロセスおよび動作を定義するためのソフトウェアソリューションに関する。こうしたコンピュータ支援設計システムにおいて、技法の効率に関しては、グラフィカルユーザインターフェース（ＧＵＩ）が重要な役割を果たす。これらの技法は、製品ライフサイクル管理（ＰＬＭ）システム内に埋め込むことが可能である。ＰＬＭは、拡張された企業の概念全体にわたって、企業が製品データを共有し、共通のプロセスを適用し、製品の出現から寿命の終了まで製品の開発に関する企業知識を活用するための一助となる、ビジネス戦略を指す。
【０００３】
ＤＡＳＳＡＵＬＴ  ＳＹＳＴＥＭＳによって（商標ＣＡＴＩＡ、ＥＮＯＶＩＡ、およびＤＥＬＭＩＡで）提供されるＰＬＭソリューションは、製品エンジニアリング知識を組織化するエンジニアリングハブ、製造エンジニアリング知識を管理する製造ハブ、ならびに、エンジニアリングハブおよび製造ハブの両方への企業の統合および接続を可能にする企業ハブを提供する。すべてが一緒になって、システムは、動的な知識ベースの製品創出および意思決定支援を可能にするように製品、プロセス、リソースをリンクし、最適化された製品の定義、製造準備、生産、およびサービスを推進するオープンオブジェクトモデルをもたらす。
【０００４】
いくつかのシステムは、デクセル（ｄｅｘｅｌ）の集合（ｓｅｔ）を用いたモデル化されたボリュームの表現を可能にする。いくつかの文書では、機械加工シミュレーションまたは対話型彫刻に関してデクセル表現を使用することを特に提案している。
【０００５】
こうした文書の例（例えば、非特許文献１、非特許文献２、非特許文献３、非特許文献４、非特許文献５、非特許文献６、特許文献１、および特許文献２を参照）がある。
【０００６】
ＧＰＧＰＵ（ＧＥＮＥＲＡＬ−ＰＵＲＰＯＳＥ  ＣＯＭＰＵＴＩＮＧ  ＯＮ  ＧＲＡＰＨＩＣＳ  ＰＲＯＣＥＳＳＩＮＧ  ＵＮＩＴＳ）は、従来は中央処理ユニット（ＣＰＵ）によって処理されるアプリケーション内の計算を実行するために、通常はコンピュータグラフィック専用の計算を処理するグラフィック処理ユニット（ＧＰＵ）を使用する技法である。いくつかの論文では、デクセル表現に関して現在のグラフィック処理ユニット（ＧＰＵ）の計算能力を使用することについて考察している。これらの論文は、特定のメモリモデルに関連付けられたＬＤＮＩ（ＬＡＹＥＲＥＤ  ＤＥＰＴＨ−ＮＯＲＭＡＬ  ＩＭＡＧＥＳ）アルゴリズムを使用している。
【０００７】
こうした論文の例（例えば、非特許文献７および非特許文献８を参照）がある。
【０００８】
一般的に衝突検出のためのアルゴリズムは、例えばｎ個の動的オブジェクトの場合における検出を記述する。多角形の描写に関して、多く衝突検出方法は、例えば２値空間分割又は指向バウンディングボリューム（Ｏｒｉｅｎｔｅｄ  Ｂｏｕｎｄｉｎｇ  Ｖｏｌｕｍｅｓ）などの古典的な幾何学的オブジェクトに基づく。いくつかのアルゴリズムは、ＣＧＳによって表現されたソリッド（ｓｏｌｉｄ）に関して存在する。ＣＧＳ構造は、単一のプリミティブ上で実行されるブール（Ｂｏｏｌｅａｎ）演算のシーケンスの結果として、３Ｄクローズド・ソリッド（ｃｌｏｓｅｄ  ｓｏｌｉｄ）を記述する。結局、ソリッドは、パラメータ方程式又は陰方程式によってされる。これの描写は、表面間の交差をテストするための多くのアルゴリズムに至る。これらのアプローチは、例えば分析法、ラティス（ｌａｔｔｉｃｅ）法、追跡法、陰方程式など、いくつかのグループに集約される。
【０００９】
こうした論文の例（例えば、非特許文献９、非特許文献１０、非特許文献１１、非特許文献１２、および非特許文献１３を参照）がある。
【００１０】
しかし、ＮＣシミュレーション用の衝突検出は、特別である。機械加工シミュレーションの特殊性は、２つに分けられる。その一つは、工作物のジオメトリーは、機械加工プロセスの間中、連続的に展開する。そのもう１つは、動的工具（ｔｏｏｌ）は、切削部と非切削部、例えば柄（工具の側面）と保持部などを含む。ＮＣ機械加工シミュレーション又はより一般的な彫刻シミュレーションの構成において、ほとんどの作成者が、非切削機械加工部と展開する工作物との間での衝突をチェックすることとをほとんど考慮していない。
【００１１】
下記の文献（例えば、非特許文献１４、非特許文献１５、および非特許文献１６を参照）において、衝突を検出する問題は、各衝突テスト間の部品のジオメトリーを更新することによって述べられる。
【００１２】
観察したように、機械加工シミュレーションの歴史は長い。しかし、既存の解決策は、とりわけ、メモリ性能の観点から、シミュレーションの正確性の観点から、および／またはユーザ利用の観点から、効率に欠ける。
【００１３】
図１〜図３は、工作物の機械加工をシミュレートするときに現れる問題を示す。工具位置で衝突のみを検出するアプローチ（これは、非特許文献１７参照）では、各工具位置で衝突検出を行う。結果として、工具が１つの位置から次の位置へ移動するとき、何が発生したのかは、無視される。このような欠点に対処するために、工具の軌道（ｔｒａｊｅｃｔｏｒｙ）は、２つの一連の工具位置間の距離が所定の許容誤差を超えないように、常に全面的に独立して描かれる。これは、膨大なチェック数を必要とすることから、性能面で落ちる傾向にある。図１は、工作物１０と工具１４の非切削部１２との間での誤った衝突を示す。図２は、十分な離散的配置による、工作物１０と工具１４の非切削部１２との間での誤った衝突２０の検出を示す。そのような離散的配置はコスト高（その結果として、例えばシミュレーションのビジュアル的な流動性の欠落となる）であり、決して１００％安全とすることができない。
【００１４】
いくつかのアプローチでは、工作物が固定したままであることは、機械加工プロセスを扱うとき、材料移動事象が行われず、非現実的であるということを意味することと仮定できる。これらのアプローチは、時間の間じゅうは進展がないと思われる２つのオブジェクト間の衝突を検出する、より一般的なクラスのアルゴリズムに属する。これらのアルゴリズムは、一般的に経路計画問題を解決するために使用される。機械加工シミュレーションの内容において、それらは設計された部分に対して衝突が生じないことをチェックするために使用される。
【００１５】
少数のアプローチでは、先の２つの問題を取扱うことができる。すなわち、これらのアプローチでは、工作物を時間と共に進展するものとみなし、および工具位置のみならず、工具の動きに沿った衝突を検出することを許容することを目的とする。しかし、これらのアプローチでは、工具のジオメトリー（ｇｅｏｍｅｔｒｙ）について制限的な仮定に基づくことができ、および例えば隆起のような膨大（および無限）な数の凸部を必要とするいくつかの工具を破棄することができる。これらのアプローチでは、工具上の窪み又は丸みを特徴とする工具も取扱うことができない。さらに一般的には、これらのアプローチは、凸部間のブーリアン（Ｂｏｏｌｅａｎ）減算から得られる工具を取扱うことができない。凸部の接合によってそのような工具に近似させることは、実際的にパフォーマンスに欠け、および正確性を損なう。図３は、非切削部３６との衝突無しに、工作物３４を機械加工することができる非凸切削部３２を有する切削工具３０を示す。見てわかるように、切削工具の形状およびその軌道は、その切削部が常に最初に工作物材料に当たることが保証されているため、衝突は生じない。しかし、これらのアプローチは、（他の見地からのパフォーマンスを通じて）誤って衝突と報告しやすい。
【００１６】
これに関連して、工作物の機械加工をシミュレートするための改良された解決策が、依然として求められている。
【先行技術文献】
【特許文献】
【００１７】
【特許文献１】米国特許第５７１０７０９号明細書
【特許文献２】米国特許第７７４７４１８号明細書
【非特許文献】
【００１８】
【非特許文献１】“Ａ  ＶＩＲＴＵＡＬ  ＳＣＵＬＰＴＩＮＧ  ＳＹＳＴＥＭ  ＢＡＳＥＤ  ＯＮ  ＴＲＩＰＬＥ  ＤＥＸＥＬ  ＭＯＤＥＬＳ  ＷＩＴＨ  ＨＡＰＴＩＣＳ”，  ＸＩＡＯＢＯ  ＰＥＮＧ  ＡＮＤ  ＷＥＩＨＡＮ  ＺＨＡＮＧ，  ＣＯＭＰＵＴＥＲ−ＡＩＤＥＤ  ＤＥＳＩＧＮ  ＡＮＤ  ＡＰＰＬＩＣＡＴＩＯＮＳ，  ２００９
【非特許文献２】“ＮＣ  ＭＩＬＬＩＮＧ  ＥＲＲＯＲ  ＡＳＳＥＳＳＭＥＮＴ  ＡＮＤ  ＴＯＯＬ  ＰＡＴＨ  ＣＯＲＲＥＣＴＩＯＮ”，  ＹＵＮＣＨＩＮＧ  ＨＵＡＮＧ  ＡＮＤ  ＪＡＭＥＳ  Ｈ．  ＯＬＩＶＥＲ，  ＰＲＯＣＥＥＤＩＮＧＳ  ＯＦ  ＴＨＥ  ２１ＳＴ  ＡＮＮＵＡＬ  ＣＯＮＦＥＲＥＮＣＥ  ＯＮ  ＣＯＭＰＵＴＥＲ  ＧＲＡＰＨＩＣＳ  ＡＮＤ  ＩＮＴＥＲＡＣＴＩＶＥ  ＴＥＣＨＮＩＱＵＥＳ，  １９９４
【非特許文献３】“ＯＮＬＩＮＥ  ＳＣＵＬＰＴＩＮＧ  ＡＮＤ  ＶＩＳＵＡＬＩＺＡＴＩＯＮ  ＯＦ  ＭＵＬＴＩ−ＤＥＸＥＬ  ＶＯＬＵＭＥＳ”，  ＨＥＩＮＲＩＣＨ  ＭＵＬＬＥＲ，  ＴＯＢＩＡＳ  ＳＵＲＭＡＮＮ，  ＭＡＲＣ  ＳＴＡＵＴＮＥＲ，  ＦＲＡＮＫ  ＡＬＢＥＲＳＭＡＮＮ，  ＫＬＡＵＳ  ＷＥＩＮＥＲＴ，  ＳＭ  ’０３  ＰＲＯＣＥＥＤＩＮＧＳ  ＯＦ  ＴＨＥ  ＥＩＧＨＴＨ  ＡＣＭ  ＳＹＭＰＯＳＩＵＭ  ＯＮ  ＳＯＬＩＤ  ＭＯＤＥＬＩＮＧ  ＡＮＤ  ＡＰＰＬＩＣＡＴＩＯＮＳ
【非特許文献４】“ＶＩＲＴＵＡＬ  ＰＲＯＴＯＴＹＰＩＮＧ  ＡＮＤ  ＭＡＮＵＦＡＣＴＵＲＩＮＧ  ＰＬＡＮＮＩＮＧ  ＢＹ  ＵＳＩＮＧ  ＴＲＩ−ＤＥＸＥＬ  ＭＯＤＥＬＳ  ＡＮＤ  ＨＡＰＴＩＣ  ＦＯＲＣＥ  ＦＥＥＤＢＡＣＫ”，  ＹＯＮＧＦＵ  ＲＥＮ，  ＳＵＳＡＮＡ  Ｋ．  ＬＡＩ−ＹＵＥＮ  ＡＮＤ  ＹＵＡＮ−ＳＨＩＮ  ＬＥＥ，  ＶＩＲＴＵＡＬ  ＡＮＤ  ＰＨＹＳＩＣＡＬ  ＰＲＯＴＯＴＹＰＩＮＧ，  ２００６
【非特許文献５】“ＳＩＭＵＬＡＴＩＯＮ  ＯＦ  ＮＣ  ＭＡＣＨＩＮＩＮＧ  ＢＡＳＥＤ  ＯＮ  ＴＨＥ  ＤＥＸＥＬ  ＭＯＤＥＬ：  Ａ  ＣＲＩＴＩＣＡＬ  ＡＮＡＬＹＳＩＳ”，  ＳＡＢＩＮＥ  ＳＴＩＦＦＥＲ，  ＴＨＥ  ＩＮＴＥＲＮＡＴＩＯＮＡＬ  ＪＯＵＲＮＡＬ  ＯＦ  ＡＤＶＡＮＣＥＤ  ＭＡＮＵＦＡＣＴＵＲＩＮＧ  ＴＥＣＨＮＯＬＯＧＹ，  １９９５
【非特許文献６】“ＲＥＡＬ  ＴＩＭＥ  ＳＩＭＵＬＡＴＩＯＮ  ＡＮＤ  ＶＩＳＵＡＬＩＺＡＴＩＯＮ  ＯＦ  ＮＣ  ＭＩＬＬＩＮＧ  ＰＲＯＣＥＳＳＥＳ  ＦＯＲ  ＩＮＨＯＭＯＧＥＮＥＯＵＳ  ＭＡＴＥＲＩＡＬＳ  ＯＮ  ＬＯＷ−ＥＮＤ  ＧＲＡＰＨＩＣＳ  ＨＡＲＤＷＡＲＥ”，  ＫＯＮＩＧ，  Ａ．Ｎ．  ＡＮＤ  ＧＲＯＬＬＥＲ，  Ｅ．，  ＣＯＭＰＵＴＥＲ  ＧＲＡＰＨＩＣＳ  ＩＮＴＥＲＮＡＴＩＯＮＡＬ，  １９９８．  ＰＲＯＣＥＥＤＩＮＧＳ
【非特許文献７】“ＧＰＧＰＵ−ＢＡＳＥＤ  ＭＡＴＥＲＩＡＬ  ＲＥＭＯＶＡＬ  ＳＩＭＵＬＡＴＩＯＮ  ＡＮＤ  ＣＵＴＴＩＮＧ  ＦＯＲＣＥ  ＥＳＴＩＭＡＴＩＯＮ”，  Ｂ．  ＴＵＫＯＲＡ  ＡＮＤ  Ｔ．  ＳＺＡＬＡＹ，  ＣＣＰ：  ９４：  ＰＲＯＣＥＥＤＩＮＧＳ  ＯＦ  ＴＨＥ  ＳＥＶＥＮＴＨ  ＩＮＴＥＲＮＡＴＩＯＮＡＬ  ＣＯＮＦＥＲＥＮＣＥ  ＯＮ  ＥＮＧＩＮＥＥＲＩＮＧ  ＣＯＭＰＵＴＡＴＩＯＮＡＬ  ＴＥＣＨＮＯＬＯＧＹ
【非特許文献８】“ＬＡＹＥＲＥＤ  ＤＥＰＴＨ−ＮＯＲＭＡＬ  ＩＭＡＧＥＳ：  Ａ  ＳＰＡＲＳＥ  ＩＭＰＬＩＣＩＴ  ＲＥＰＲＥＳＥＮＴＡＴＩＯＮ  ＯＦ  ＳＯＬＩＤ  ＭＯＤＥＬＳ”，  ＣＨＡＲＬＩＥ  Ｃ．  Ｌ．  ＷＡＮＧ  ＡＮＤ  ＹＯＮＧ  ＣＨＥＮ，  ＰＲＯＣＥＥＤＩＮＧＳ  ＯＦ  ＡＳＭＥ  ＩＮＴＥＲＮＡＴＩＯＮＡＬ  ＤＥＳＩＧＮ  ＥＮＧＩＮＥＥＲＩＮＧ  ＴＥＣＨＮＩＣＡＬ  ＣＯＮＦＥＲＥＮＣＥＳ  ＢＲＯＯＫＬＹＮ  （ＮＹ）
【非特許文献９】“Ｃｏｌｌｉｓｉｏｎ  ｄｅｔｅｃｔｉｏｎ  ｂｅｔｗｅｅｎ  ｇｅｏｍｅｔｒｉｃ  ｍｏｄｅｌｓ: Ａ  ｓｕｒｖｅｙ”，Ｌｉｎ，Ｍ．ａｎｄＧｏｔｔｓｃｈａｌｋ，Ｓ．Ｐｒｏｃ．ｏｆＩＭＡ  Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｍａｔｈｅｍａｔｉｃｓ  ｏｆ  Ｓｕｕｒｆａｃｅｓ，１９９８；
【非特許文献１０】“Ｉｍｐｒｏｖｅｍｅｎｔ  ｏｆ  ｃｏｌｌｉｓｉｏｎ−ｄｅｔｅｃｔｉｏｎ  ａｌｇｏｒｉｔｈｍ  ｂａｓｅｄ  ｏｎ  ＯＢＢ”，  Ｊｏｕｒｎａｌ  ｏｆ  Ｈｕａｚｈｏｎｇ  Ｕｎｉｖｅｒｓｉｔｙ  ｏｆ  Ｓｃｉｅｎｃｅ  ａｎｄ  Ｔｅｃｎｏｌｏｇｙ，  Ｚｈａｎｇ  Ｑｉｎ，  Ｈｕａｎｇ  Ｋｕｎ，  Ｌｉ  Ｇｕａｎｇｍｉｎｇ；
【非特許文献１１】“Ｃｏｌｌｉｓｉｏｎ  ｄｅｔｅｃｔｉｏｎ  ａｎｄ  ａｎａｌｙｓｉｓ  ｉｎ  ａ  ｐｈｙｓｉｃａｌｌｙ  ｂａｓｅｄ  ｏｎ  ｓｉｍｕｌａｔｉｏｎ”，  Ｗ．Ｂｏｕｍａ  ａｎｄ  Ｇ．Ｖａｎｅｃｋ，Ｐｒｏｃｅｅｄｉｎｇｓ  Ｅｕｒｏｇｒａｐｈｉｃｓ  ｗｏｒｋｓｈｏｐ  ｏｎ  ａｎｉｍａｔｉｏｎ  ａｎｄ  ｓｉｍｕｌａｔｉｏｎ，１９９１；
【非特許文献１２】“Ａ  ｎｅｗ  ｃｏｌｌｉｓｉｏｎ］  ｄｅｔｅｃｔｉｏｎ  ｍｅｔｈｏｄ  ｆｏｒ  ＣＧＳ−ｒｅｐｒｅｓｅｎｔｅｄ  ｏｂｊｅｃｔｓ  ｉｎ  ｖｉｒｔｕａｌ  ｍａｎｕｆａｃｔｕｒｉｎｇ”，Ｃｈｕａｎ−Ｊｕｎ  Ｓｕｂ，  Ｆｕｈｕａ  Ｌｉｎａ，  ａｎｄ  Ｌａｎ  Ｙｅｂ，  Ｃｏｍｐｕｔｅｒｓ  ｉｎ  Ｉｎｄｕｓｔｒｙ，Ｖｏｌｕｍｅ  ４０，Ｉｓｓｕ  １，  Ｓｅｐｔｅｍｂｅｒ  １９９９，  Ｐａｇｅｓ  １−１３；
【非特許文献１３】“Ｇｅｏｍｅｔｒｉｃ  ａｎｄ  Ｓｏｌｉｄ  Ｍｏｄｅｌｉｎｇ”；Ｃ．Ｍ．Ｈｏｆｆｍａｎｎ，  Ｍｏｒｇａｎ  ＫＡＵｆｍａｎｎ，  Ｓａｎ  Ｍａｔｅｏ，  Ｃａｌｉｆｏｏｒｎｉａ，１９８９
【非特許文献１４】“ＰＲＥＣＩＳＥ  ＧＬＯＢＡＬ  ＣＯＬＬＩＳＩＯＮ  ＤＥＴＥＣＴＩＯＮ  ＩＮ  ＭＵＬＴＩ−ＡＸＩＳ  ＮＣ−ＭＡＣＨＩＮＩＮＧ”，  ＯＬＥＧ  ＩＬＵＳＨＩＮＡ，  ＧＥＲＳＨＯＮ  ＥＬＢＥＲＢ，  ＤＡＮ  ＨＡＬＰＥＲＩＮ，  ＲＯＮ  ＷＥＩＮ，  ＭＹＵＮＧ−ＳＯＯ  ＫＩＭ，  ＣＯＭＰＵＴＥＲ−ＡＩＤＥＤ  ＤＥＳＩＧＮ  ３７  （２００５）  ９０９  −  ９２０
【非特許文献１５】“ＴＨＥ  ＳＷＥＥＰ  ＰＬＡＮＥ  ＡＬＧＯＲＩＴＨＭ  ＦＯＲ  ＧＬＯＢＡＬ  ＣＯＬＬＩＳＩＯＮ  ＤＥＴＥＣＴＩＯＮ  ＷＩＴＨ  ＷＯＲＫＰＩＥＣＥ  ＧＥＯＭＥＴＲＹ  ＵＰＤＡＴＥ  ＦＯＲ  ＦＩＶＥ−ＡＸＩＳ  ＮＣ  ＭＡＣＨＩＮＩＮＧ”，  Ｔ．Ｄ．  ＴＡＮＧ，  ＥＲＩＫ  Ｉ．，  Ｊ．  ＢＯＨＥＺ，  ＰＩＳＵＴ  ＫＯＯＭＳＡＰ，  ＣＯＭＰＵＴＥＲ−ＡＩＤＥＤ  ＤＥＳＩＧＮ  ３９  （２００７）  １０１２  −  １０２４
【非特許文献１６】“Ｃｏｍｍｅｒｃｉａｌ  ｓｏｆｔｗａｒｅ  ＣＡＭＷｏｒｋｓ  （ｒｅｇｓｉｔｅｒｅｄ  ｔｒａｄｅ  ｍａｒｋ）”
【非特許文献１７】“Ｐｒｅｃｉｓｅ  ｇｌｏｂａｌ  ｃｏｌｌｉｓｉｏｎ  ｄｅｔｅｃｔｉｏｎ  ｉｎ  ｍｕｌｔｉ−ａｘｉｓ  ＮＣ−ｍａｃｈｉｎｇ”，Ｏｌｅｇ  Ｉｌｕｓｈｉｍａ，  Ｇｅｒｓｈｏｎ  Ｅｌｂｅｒｂ，Ｄａｎ  Ｈａｌｐｅｒｉｎ，Ｒｏｎ  Ｗｅｉｎ，Ｍｙｕｎｇ−Ｓｏｏ  Ｋｉｍ，Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ  ３７（２００５）９０９−９２０，ａｎｄ  ＣＡＭＷｏｒｋｓ
【非特許文献１８】Ｓｗｅｐｔ  Ｖｏｌｕｍｅｓ、Ｍ．Ｐｅｔｅｒｎｅｌｌ、Ｈ．Ｐｏｔｔｍａｎｎ、Ｔ．Ｓｔｅｉｎｅｒ、Ｈ．Ｚｈａｏ、Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ  Ｄｅｓｉｇｎ  ＆  Ａｐｐｌｉｃａｔｉｏｎｓ、Ｖｏｌ．２、Ｎｏ．５、２００５年、５９９〜６０８ページ
【非特許文献１９】Ｍａｔｈｅｍａｔｉｃａｌ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｎｕｍｅｒｉｃａｌ  Ｍｅｔｈｏｄｓ  ｆｏｒ  Ｓｃｉｅｎｃｅ  ａｎｄ  Ｔｅｃｈｎｏｌｏｇｙ、２２９ページ
【非特許文献２０】Ａｄａｐｔｉｖｅ  Ｐｒｅｃｉｓｉｏｎ  Ｆｌｏａｔｉｎｇ−Ｐｏｉｎｔ  Ａｒｉｔｈｍｅｔｉｃ  ａｎｄ  Ｆａｓｔ  Ｒｏｂｕｓｔ  Ｐｒｅｄｉｃａｔｅｓ  ｆｏｒ  Ｃｏｍｐｕｔａｔｉｏｎａｌ  Ｇｅｏｍｅｔｒｙ
【発明の概要】
【発明が解決しようとする課題】
【００１９】
本発明では、工作物の機械加工をシミュレートするための改善された方法、システム、およびプログラムを提供すること。
【課題を解決するための手段】
【００２０】
一態様によれば、したがって、少なくとも１つの刃部および少なくとも１つの非刃部を有する切削工具を用いる工作物の機械加工をシミュレートするためのコンピュータ実施方法が提供される。方法は、工作物を表すデクセルの集合であって、各デクセルは、直線と工作物との間の交わりを表す少なくとも１つの線分からなる集合を含む、デクセルの集合と、切削工具の軌道であって、剛体運動である切削工具の軌道と、メッシュの集合であって、各々が、切削工具のそれぞれの刃部または非刃部を表す、メッシュの集合とを提供するステップを含む。次に、方法は、各デクセルについて、各メッシュについて、切削工具の軌道に従って、デクセルの直線とメッシュとの間の交わりの時刻を交わりの高さの関数として記述する、すべてのポリラインの端点を計算するステップを含む。方法は、デクセルに沿って切削工具の工作物との衝突をテストするステップを含む。テストするステップは、すべてのメッシュのすべてのポリラインからなる集合の下側エンベロープに属する位置に対応する高さの値について、その位置が属するポリラインが、非刃部に関連付けられる場合、高さの値が、デクセルの線分に属するかどうかを決定するステップを含む。
【００２１】
方法は、以下のうちの１または複数を含む。  
−  すべてのポリラインの端点を計算するステップは、各メッシュについて、およびそれぞれのポリラインの各端点について、それぞれのポリラインに関連付けられたメッシュのすべての面分に基づいて、デクセルの直線のそれとの交わりが端点に対応する、切削工具の軌道に従ってメッシュの面分によって掃引された体積の境界面分を決定するステップと、デクセルの直線と決定された境界面分との間の交わりに基づいて、時刻および高さを計算するステップとを含み、
−  すべてのポリラインの端点を計算するステップは、各メッシュについて、メッシュの可視部分を決定するステップであって、可視部分は、切削工具の軌道に向かって方向付けられたメッシュの部分である、ステップと、切削工具の軌道に従って、可視部分によって掃引された体積の境界を計算するステップと、次に、それぞれのポリラインの各端点について、デクセルの直線のそれとの交わりが端点に対応する、メッシュの面分によって掃引された体積の境界面分を決定するステップと、時刻および高さを計算するステップとを反復するステップであって、境界面分を決定するステップは、可視部分によって掃引された体積の計算された境界のそれぞれの境界面分を識別することから成る、ステップとをさらに含み、
−  すべてのポリラインの端点を計算するステップは、各メッシュについて、可視部分の面分によって掃引された体積に関する隣接性情報を決定するステップであって、各それぞれのポリラインについて、デクセルの直線のそれとの交わりがポリラインの第１の端点に対応する、メッシュの面分によって掃引された体積の境界面分を決定するステップは、幾何学的な計算によって、可視部分によって掃引された体積の計算された境界の第１の面分を決定することから成り、前記第１の面分は、デクセルの直線によって交わられ、デクセルの直線のそれとの交わりがポリラインの第２の端点に対応する、面分によって掃引された体積の境界面分を決定するステップは、隣接性情報に基づいたトポロジ的な伝搬によって、可視部分によって掃引された体積の計算された境界の第２の面分を決定することから成り、前記第２の面分は、デクセルの直線によって交わられる、ステップをさらに含み、ならびに／または
−  反復するステップは、デクセルの集合にわたって並列化され、
−  第１の面分を決定するステップは、デクセルの集合にわたってラスタ化を実施する。
【００２２】
本発明の方法による、少なくとも１つの刃部および少なくとも１つの非刃部を有する切削工具を用いる工作物の機械加工のシミュレーションの細目を含む（例えば、ファイル内に記憶される）データ構造が、さらに提案される。
【００２３】
方法を実行するための命令を記録したメモリに結合されたプロセッサを備えるシステムが、さらに提案される。プロセッサは、超並列処理ユニットである。システムは、命令の実行を起動するのに適した少なくとも１つのＧＵＩを備える。ＧＵＩは、ＧＰＵを備え、プロセッサは、ＧＰＵである。
【００２４】
上述の方法を実行するための命令を含むコンピュータプログラムが、さらに提案される。
【００２５】
上述のコンピュータプログラムを記録したコンピュータ可読記憶媒体が、さらに提案される。
【００２６】
製品を生産／製造するための方法が、さらに提案される。生産方法は、機械加工をシミュレートするための上述の方法が繰り返されるシミュレーションフェーズと、次に、工作物に対する機械加工フェーズとを含む。
【図面の簡単な説明】
【００２７】
本発明の実施形態が、非限定的な例を用いて、また添付の図面を参照して、今から説明される。
【図１】機械加工シミュレーションにおける主な問題を示す図である。
【図２】機械加工シミュレーションにおける主な問題を示す図である。
【図３】機械加工シミュレーションにおける主な問題を示す図である。
【図４】方法の例のフローチャートである。
【図５】グラフィカルユーザインターフェースの例を示す図である。
【図６】クライアントコンピュータシステムの例を示す図である。
【図７】方法を示す図である。
【図８】方法を示す図である。
【図９】方法を示す図である。
【図１０】方法を示す図である。
【図１１】方法を示す図である。
【図１２】方法を示す図である。
【図１３】方法を示す図である。
【図１４】方法を示す図である。
【図１５】方法を示す図である。
【図１６】方法を示す図である。
【図１７】方法を示す図である。
【図１８】方法を示す図である。
【図１９】方法を示す図である。
【図２０】方法を示す図である。
【図２１】方法を示す図である。
【図２２】方法を示す図である。
【図２３】方法を示す図である。
【図２４】方法を示す図である。
【図２５】方法を示す図である。
【図２６】方法を示す図である。
【図２７】方法を示す図である。
【図２８】方法を示す図である。
【図２９】方法を示す図である。
【図３０】方法を示す図である。
【図３１】方法を示す図である。
【図３２】方法を示す図である。
【図３３】方法を示す図である。
【図３４】方法を示す図である。
【図３５】方法を示す図である。
【図３６】方法を示す図である。
【図３７】方法を示す図である。
【図３８】方法を示す図である。
【図３９】方法を示す図である。
【図４０】方法を示す図である。
【図４１】方法を示す図である。
【図４２】方法を示す図である。
【発明を実施するための形態】
【００２８】
図４を参照すると、切削工具を用いる工作物の機械加工をシミュレートするためのコンピュータ実施方法が提供される。方法によって企図される切削工具は、少なくとも１つの刃部と、少なくとも１つの（切削工具が潜在的に−いくぶんかは−衝突する物体となるような、「衝突部分」とも呼ばれる）非刃部とを有する。方法は、工作物を（３Ｄで）表すデクセルの集合を提供するステップＳ１０を含む（デクセルの集合および／または工作物は、以下では「モデリングされた体積／物体」とも呼ばれる）。定義によって、各デクセルは、直線と工作物（例えば、工作物によって占有される体積）との間の交わりを表す少なくとも１つの線分からなる集合を含む。ここで、デクセルは、工作物の材料が存在する直線上の位置（すなわち、デクセルの線分）に対応する。しかしながら、「デクセル」という用語は、あるいは、いくつかのデクセルが、例えば、最初から、または方法によって、任意の材料／線分を奪われるような、そのような３Ｄモデルのすべての直線に関連付けられたデータを指すことに留意されたい。これは、単に定義の問題である。Ｓ１０において提供されるデータは、切削工具の（あるいは、軌道は平面、例えば、平面内の一連の位置、例えば、２．５軸軌道であるが、３Ｄ内の、例えば、非平面の）軌道（の細目）も含む。本発明の方法の場合、切削工具の軌道は、剛体運動である（一連の剛体運動から成るより複雑な軌道への一般化、および一連の剛体運動の各々に方法を繰り返すことへの一般化を妨げない）。Ｓ１０において提供されるデータは、メッシュの集合も含む。各メッシュは、切削工具のそれぞれの刃部または非刃部を表す（したがって、メッシュの集合は、切削工具を表す）。次に、方法は、各デクセルについての（例えば、ＧＰＵを用いる）特定の（例えば、並列）処理を含む。これは、各メッシュについて（例えば、方法はメッシュの集合においてループする）、すべてのポリラインの端点を計算するステップＳ２０を含み、ポリラインは、デクセルの直線とメッシュ（すなわち、メッシュの面分−または辺もしくは頂点のことさえある）との間の交わりの時刻を交わりの高さの関数として記述し、計算するステップＳ２０は、Ｓ１０において提供された切削工具の軌道に従って実行される。これには、デクセルに沿って切削工具（例えば、切削工具の掃引）の工作物との衝突をテストするステップＳ３０が続く（すなわち、切削工具の刃部がデクセルを更新／変更するにつれてのデクセルの変化を考慮して、切削工具−の非刃部−が、デクセルの少なくとも１つの材料線分と衝突する−例えば、時間的にいくつかの点において交わる−かどうかという問いに少なくとも応答する）。特に、テストするステップは、すべてのメッシュのすべてのポリラインからなる集合の下側エンベロープに属する位置に対応する高さの値について、その位置が属するポリラインが、非刃部に関連付けられる場合、高さの値が、デクセルの線分に属するかどうかを決定するステップを含む（したがって、高さのそのような値が存在するかどうかがテストされる）。そのような方法は、工作物の機械加工のシミュレーションを改善する。
【００２９】
特に、本発明の方法は、少なくとも１つの刃部および少なくとも１つの非刃部を有する切削工具を用いて工作物を機械加工するシミュレーションに関し、切削工具は、軌道を辿り（方法は、距離相対時間に関して−任意のスピードが、例えば、任意の一定のスピードが計算において企図されるように、軌道が辿られるスピードに関心がなく）、方法は、切削工具（より具体的には、切削工具の非刃部、したがって、衝突部分）の工作物との衝突を検出する（Ｓ２０およびＳ３０）。したがって、方法は、工業用機械加工の良好なシミュレーションを可能にする。
【００３０】
さらに、方法は、デクセル表現に基づいており、したがって、それは、（デクセルは離散的で超並列化可能な表現を可能にするので）バッファリングおよび計算に関して軽い。結果として、方法は、流れるようで／滑らかであり、したがって、応答性がよく、それは、ユーザエンドにおいて高く評価される。方法が、さらに、工作物の表現と、軌道を辿る切削工具の表現とを、例えば、機械加工の表現と完全に一緒に表示する場合、そのような表示は、相対的に流れるようで／滑らかであり、断続的ではない。今度は、方法は、さらに、特定のデータ、すなわち、Ｓ２０において計算されたそれらに基づいて、Ｓ３０においてテストを実行し、特に、方法は、切削工具の軌道に従って、デクセルの直線とメッシュとの間の交わりの時刻を交わりの高さの関数として記述する、すべてのポリラインの端点を計算する。やはり、これらのデータは、離散的であり、Ｓ２０において企図されたデータの構造は、計算がデクセルにわたって並列化されることを保証する。したがって、方法は、計算、応答性、およびメモリバッファリングの観点から見て、なおさら効率的である。
【００３１】
さらに、計算されるデータは、特定の意味を有し、それらは、Ｓ３０において方法によって提案される（離散的な手法と見なされることができる先に言及された先行技術の時間ステップベースの方法とは対照的に、連続関数としての、時間に関する）特定の容易で包括的なテストを可能にする特定の数学的な特性を有する。実際に、方法は、問題がひとたび良好に書かれると、幾何学的な条件を決定することに相当し、そのことは、方法に正しい結果を、したがって、現実的で正しいシミュレーションを出力させる。これらの数学的な特性は、後で詳述される。現段階では、方法は、非凸の切削工具および／または非凸の刃部を有する切削工具についてさえも良好に機能するように、相対的に恣意的な工具を扱うことが可能である（すなわち、シミュレーションは正しい、例えば、より多くの衝突が正しく報告され、および／またはより少ない衝突が誤って報告される）ことに留意されたい。切削工具は、（もちろん、そうであることは可能であるが）回転体であることに制約されない。切削工具は、例えば、空隙を特徴とし、またはラウンドオーバ工具である。より一般的には、切削工具は、凸部分の間のブール減算からもたらされる形状を有する。例えば、方法は、図３の状況において、かなり良好なアニメーションスピードで良好に機能する（すなわち、衝突が誤って報告されない）。切削工具は、例では、コーナ丸めエンドミル、クォータラウンド工具、フライスの集合、または組み合わせフライスである。また、方法の背後の数学は、方法が工具軌道に関して相対的に限定されないように、任意の（一連の）剛体運動の場合にも、それを相対的に良好に機能させる。
【００３２】
したがって、本発明の方法は、工具表現が相対的に恣意的な場合に、および／または工作物の変化が相対的に恣意的な場合に、ロバストで、流れるような／滑らかな、包括的な方法で、工具移動の間の衝突検出を扱う。
【００３３】
本発明の方法は、コンピュータ実施される。方法のステップは、実際に、コンピュータシステムにおいて、コンピュータシステムのみによって、またはグラフィカルユーザ対話（すなわち、ユーザがコンピュータシステムのＧＵＩと対話すること）によって実行される。したがって、コンピュータシステムによって明確に実行されるステップは、完全に自動的に実行される。例では、方法のステップの少なくともいくつかのトリガリングは、ユーザ−コンピュータ対話を通して実行される。特に、提供するステップＳ１０は、Ｓ１０において提供されるデータをユーザが指定するユーザ対話によって実行される。Ｓ１０は、実際に、ユーザが機械加工シミュレーションを起動することに対応する。計算するステップＳ２０およびテストするステップＳ３０は、その後、自動的に実行される。必要とされるユーザ−コンピュータ対話のレベルは、予知され、ユーザの望みを実施するために必要なものとバランスが取られる、自動性のレベルに依存する。例では、このレベルは、ユーザ定義され、および／または事前に定められる。
【００３４】
方法のコンピュータ実施の典型的な例は、この目的のために適合されたシステムを用いて方法を実行することである。システムは、メモリおよびグラフィカルユーザインターフェース（ＧＵＩ）に結合されたプロセッサを備え、メモリは、方法を実行するための命令を含むコンピュータプログラムを記録している。メモリは、データベースも記憶する。メモリは、そのような記憶のために適合され、おそらくはいくつかの物理的な個別部分（例えば、プログラム用に１つ、またおそらくはデータベース用に１つ）を備える、任意のハードウェアである。ＧＵＩは、ＧＰＵを備える。そのような場合、プロセッサは、ＧＰＵである。言い換えると、方法の少なくともステップを、特に、計算するステップＳ２０および／またはテストするステップＳ３０を実行するプロセッサは、ＧＰＵである。そのようなシステムは、機械加工をシミュレートするための効率的な工具である。このことは、工作物がデクセルの集合として表される場合には特にそうである。デクセルベースのアルゴリズムは、超並列ハードウェアによく適しているので、それは、現代のグラフィック処理ユニット（ＧＰＵ）の計算能力を使用して考察すると効率的である。
【００３５】
本発明の方法は、一般に、モデリングされた物体を操作する。モデリングされた物体は、データベース内に記憶されたデータによって定義される任意の物体である。広義には、「モデリングされた物体」という表現は、データ自体も指す。本発明の方法は、モデリングされた物体（例えば、工作物）を、例えば、最初に、工作物（したがって、３Ｄモデリングされた物体）を定義し、次に、方法によって工作物の機械加工をシミュレートすることによって、設計するためのプロセスの一部である。「３Ｄモデリングされた物体を設計する」とは、３Ｄモデリングされた物体を精巧に作成するプロセスの少なくとも一部である、任意のアクションまたは一連のアクションを指す。したがって、方法は、ゼロから３Ｄモデリングされた物体を作成するステップを含む。あるいは、本発明の方法は、以前に作成された３Ｄモデリングされた物体を提供するステップと、次に、特に方法によってシミュレートされた機械加工によって、３Ｄモデリングされた物体を変更するステップとを含む。
【００３６】
システムの種類に従って、モデリングされた物体は、異なる種類のデータによって定義される。システムは、実際には、ＣＡＤシステム、ＣＡＥシステム、ＣＡＭシステム、ＰＤＭシステム、および／またはＰＬＭシステムの任意の組み合わせである。それらの異なるシステムでは、モデリングされた物体は、対応するデータによって定義される。したがって、ＣＡＤオブジェクト、ＰＬＭオブジェクト、ＰＤＭオブジェクト、ＣＡＥオブジェクト、ＣＡＭオブジェクト、ＣＡＤデータ、ＰＬＭデータ、ＰＤＭデータ、ＣＡＭデータ、ＣＡＥデータについて説明する。しかしながら、モデリングされた物体は、これらのシステムの任意の組み合わせに対応するデータによって定義されるので、これらのシステムは、他に対して排他的なものではない。したがって、システムは、以下で提供されるそのようなシステムの定義から明らかなように、ＣＡＤシステムおよびＰＬＭシステムの両方であろう。
【００３７】
ＣＡＤシステムによって、ＣＡＴＩＡなど、モデリングされた物体のグラフィカル表現に基づいて、モデリングされた物体を少なくとも設計するように適合された、任意のシステムが、意味される。この場合、モデリングされた物体を定義するデータは、モデリングされた物体の表現を可能にするデータを含む。ＣＡＤシステムは、例えば、辺または直線を使用して、場合によっては、面分または面を用いて、ＣＡＤのモデリングされた物体の表現を提供する。直線、辺、または面は、様々な方法で、例えば、非一様有理Ｂスプライン（ＮＵＲＢＳ）で表現される。具体的には、ＣＡＤファイルは、それから幾何学的形状が生成される仕様を含み、それが、今度は、表現が生成されることを可能にする。モデリングされた物体の仕様は、単一または複数のＣＡＤファイル内に記憶される。ＣＡＤシステムにおけるモデリングされた物体を表すファイルの典型的なサイズは、部品当たり１メガバイトの範囲内にある。モデリングされた物体は、一般に、数千の部品からなる組立体である。
【００３８】
ＣＡＤシステムとの関連では、モデリングされた物体は、一般に、例えば、部品もしくは部品の組立体などの製品、または場合によっては、製品の組立体を表す、３Ｄモデリングされた物体である。「３Ｄモデリングされた物体」によって、３Ｄ表現を可能にするデータによってモデリングされた任意の物体が、意味される。３Ｄ表現は、すべての角度から、部品を見ることを可能にする。例えば、３Ｄモデリングされた物体は、３Ｄ表現された場合、自らの軸のいずれかの周りで、または表現が表示されるスクリーン内のいずれかの軸の周りで、操作および回転させられる。これは、特に、３Ｄモデリングされていない、２Ｄアイコンを除外する。３Ｄ表現の表示は、設計を容易にする（すなわち、統計的に設計者が仕事を達成するスピードを速める）。製品の設計は、製造またはモデリングプロセスの一部であるので、これは、工業における製造プロセスをスピードアップする。
【００３９】
３Ｄモデリングされた物体は、（例えば、機械）部品もしくは部品の組立体、またはより一般的に、任意の剛体組立体（例えば、移動メカニズム）など、例えば、ＣＡＤソフトウェアソリューションまたはＣＡＤシステムを用いる仮想設計が完了した後で、現実世界で製造される製品の幾何学的形状を表す。ＣＡＤソフトウェアソリューションは、航空宇宙、建築、建設、消費財、ハイテクデバイス、産業機器、輸送、海上および／もしくは沖合、または輸送を含む、様々な限りない産業分野における、製品の設計を可能にする。本発明の方法によって設計される３Ｄモデリングされた物体は、したがって、（例えば、自動車および軽トラック機器、レーシングカー、オートバイ、トラックおよびモータ機器、トラックおよびバス、列車を含む）地上車の部品、（例えば、機体機器、航空宇宙機器、推進機器、防衛製品、航空機器、宇宙機器を含む）飛行体の部品、（例えば、海軍機器、商船、沖合機器、ヨットおよび作業船、舶用機器を含む）船舶の部品、（例えば、工業製造機械、移動重機械または機器、設置機器、産業機器製品、加工金属製品、タイヤ製造製品を含む）機械部品、（例えば、民生用電子機器、セキュリティおよび／または制御および／または計装製品、コンピューティングおよび通信機器、半導体、医療デバイスおよび機器を含む）電気機械または電子部品、（例えば、家具、住宅および庭製品、レジャー用品、ファッション製品、耐久消費財小売業者製品、非耐久消費財小売業者製品を含む）消費財、（例えば、食品および飲料および煙草、美容およびパーソナルケア、家庭用品パッケージングを含む）パッケージングである、工業製品を表す。
【００４０】
ＰＬＭシステムによって、物理的な製造製品を表すモデリングされた物体の管理のために適合された任意のシステムが、意味される。ＰＬＭシステムでは、モデリングされた物体は、したがって、物理的な物体の製造に適したデータによって定義される。これらは、一般に、寸法値および／または許容値である。物体の正確な製造のために、そのような値を有することは、実際に、より良いことである。
【００４１】
ＣＡＭは、コンピュータ援用製造を表す。ＣＡＭソリューションによって、製品の製造データを管理するように適合された、任意のソリューション、ハードウェアのソフトウェアが、意味される。製造データは、一般に、製造する製品、製造プロセス、および必要とされるリソースに関連するデータを含む。ＣＡＭソリューションは、製品の全製造プロセスを計画し、最適化するために使用される。例えば、それは、実現可能性、製造プロセスの持続時間、または製造プロセスの特定のステップにおいて使用される、特定のロボットなどの、リソースの数についての情報を、ＣＡＭユーザに提供することができ、したがって、管理または必要とされる投資についての決定を可能にする。ＣＡＭは、ＣＡＤプロセスおよび潜在的なＣＡＥプロセスの後の後続プロセスである。そのようなＣＡＭソリューションは、ＤＥＬＭＩＡ（登録商標）という商標の下で、Ｄａｓｓａｕｌｔ  Ｓｙｓｔｅｍｅｓによって提供されている。
【００４２】
ＣＡＥは、コンピュータ援用エンジニアリングを表す。ＣＡＥソリューションによって、モデリングされた物体の物理的挙動の分析のために適合された、任意のソリューション、ソフトウェア、またはハードウェアが、意味される。よく知られた広く使用されているＣＡＥ技法は、モデリングされた物体を、物理的挙動が式を通して計算され、シミュレートされることができる要素に分割することを一般に含む、有限要素法（ＦＥＭ）である。そのようなＣＡＥソリューションは、ＳＩＭＵＬＩＡ（登録商標）という商標の下で、Ｄａｓｓａｕｌｔ  Ｓｙｓｔｅｍｅｓによって提供されている。別の成長しつつあるＣＡＥ技法は、ＣＡＤの幾何学的形状データを用いない、物理学の異なる分野に属する複数の構成要素から成る複雑なシステムのモデリングおよび分析を含む。ＣＡＥソリューションは、シミュレーションを可能にし、したがって、製造する製品の最適化、改良、および検証を可能にする。そのようなＣＡＥソリューションは、ＤＹＭＯＬＡ（登録商標）という商標の下で、Ｄａｓｓａｕｌｔ  Ｓｙｓｔｅｍｅｓによって提供されている。
【００４３】
ＰＤＭは、製造データ管理を表す。ＰＤＭソリューションによって、特定の製品に関連するすべての種類のデータを管理するように適合された、任意のソリューション、ソフトウェア、またはハードウェアが、意味される。ＰＤＭソリューションは、製品のライフサイクルに関わるすべての当事者によって、すなわち、主にエンジニアによって、しかし、プロジェクトマネージャ、財務担当者、販売担当者、および購入者によっても、使用される。ＰＤＭソリューションは、一般に、製品指向データベースに基づいている。それは、ユーザが、製品についての一貫したデータを共有することを可能にし、したがって、当事者が、異なるデータを使用することを防止する。そのようなＰＤＭソリューションは、ＥＮＯＶＩＡ（登録商標）という商標の下で、ＤＡＳＳＡＵＬＴ  ＳＹＳＴＥＭＥＳによって提供されている。
【００４４】
図５は、システムのＧＵＩの例を示しており、システムは、ＣＡＤシステムである。
【００４５】
ＧＵＩ２１００は、典型的なＣＡＤ様のインターフェースであり、標準的なメニューバー２１１０、２１２０、ならびにボトム工具バー２１４０およびサイド工具バー２１５０を有する。そのようなメニューバーおよび工具バーは、ユーザ選択可能なアイコンのセットを含み、各アイコンは、当技術分野において知られているような、１または複数の操作または機能と関連付けられる。これらのアイコンのいくつかは、ＧＵＩ２１００内に表示された３Ｄモデリングされた物体２０００における編集および／または作業のために適合された、ソフトウェアツールと関連付けられ、表示された３Ｄモデリングされた物体２０００は、例えば、方法を実行した結果である。ソフトウェアツールは、ワークベンチにグループ化される。各ワークベンチは、ソフトウェアツールのサブセットを含む。特に、ワークベンチの１つは、モデリングされた製品２０００の幾何学的な特徴を編集するのに適した、編集ワークベンチである。操作の際、設計者は、例えば、物体２０００の一部を事前選択し、その後、操作を開始し（例えば、寸法、色などを変え）、または適切なアイコンを選択することによって、幾何学的な制約を編集する。例えば、典型的なＣＡＤ操作は、スクリーン上に表示された３Ｄモデリングされた物体の穴開けまたは折り曲げのモデリングである。ＧＵＩは、例えば、表示された製品２０００に関連するデータ２５００を表示する。図２の例では、「フィーチャツリー」として表示されるデータ２５００、およびそれらの３Ｄ表現２０００は、ブレーキキャリパおよびブレーキディスクを含むブレーキ組立体に関する。ＧＵＩは、様々な種類のグラフィックツール２１３０、２０７０、２０８０を、例えば、物体の３Ｄ方向付けを容易にするためのもの、編集された製品の動作のシミュレーションをトリガするためのもの、または表示された製品２０００の様々な属性をレンダリングするためのものをさらに示す。カーソル２０６０は、ユーザがグラフィックツールと対話することを可能にするために、触覚デバイスによって制御される。
【００４６】
図６は、システムの例を示しており、システムは、クライアントコンピュータシステム、例えば、ユーザのワークステーションである。
【００４７】
例のクライアントコンピュータは、内部通信バス１０００に接続された中央処理装置（ＣＰＵ）１０１０と、やはりバスに接続されたランダムアクセスメモリ（ＲＡＭ）１０７０とを備える。クライアントコンピュータは、バスに接続されたビデオランダムアクセスメモリ１１００と関連付けられたグラフィカル処理ユニット（ＧＰＵ）１１１０をさらに提供される。ビデオＲＡＭ１１１０は、当技術分野では、フレームバッファとしても知られている。大容量記憶デバイスコントローラ１０２０は、ハードドライブ１０３０などの、大容量メモリデバイスへのアクセスを管理する。コンピュータプログラム命令およびデータを有形に実施するのに適した大容量メモリデバイスは、例として、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュメモリデバイスなどの半導体メモリデバイスと、内蔵ハードディスクおよび着脱可能ディスクなどの磁気ディスクと、光磁気ディスクと、ＣＤ−ＲＯＭディスク１０４０とを含む、すべての形態の不揮発性メモリを含む。上記のいずれも、特別に設計されたＡＳＩＣ（特定用途向け集積回路）によって補完され、またはそれに組み込まれる。ネットワークアダプタ１０５０は、ネットワーク１０６０へのアクセスを管理する。クライアントコンピュータは、カーソル制御デバイスまたはキーボードなどの触覚デバイス１０９０も含む。カーソル制御デバイスは、ユーザが、ディスプレイ１０８０上の任意の所望の位置にカーソルを選択的に位置付けることを可能にするために、クライアントコンピュータにおいて使用される。加えて、カーソル制御デバイスは、ユーザが、様々なコマンドを選択すること、および制御信号を入力することを可能にする。カーソル制御デバイスは、システムに入力される制御信号のための数々の信号生成デバイスを含む。典型的には、カーソル制御デバイスは、マウスであり、マウスのボタンが、信号を生成するために使用される。あるいは、または加えて、クライアントコンピュータシステムは、センシティブ／タッチパッド、および／またはセンシティブ／タッチスクリーンを備える。
【００４８】
コンピュータプログラムは、コンピュータによって実行可能な命令を含み、命令は、上述のシステムに方法を実行させるための手段を構成する。プログラムは、システムのメモリを含む、任意のデータ記憶媒体上に記録可能である。プログラムは、例えば、デジタル電子回路で、またはコンピュータハードウェア、ファームウェア、ソフトウェア、もしくはそれらの組み合わせで実施される。プログラムは、装置として、例えば、プログラム可能なプロセッサによる実行のために機械可読記憶デバイス内で有形に実施される製品として実施される。方法ステップは、入力データを操作し、出力を生成することによって、方法の機能を実行するために、命令からなるプログラムを実行する、プログラム可能なプロセッサによって実行される。したがって、プロセッサは、データ記憶システム、少なくとも１つの入力デバイス、および少なくとも１つの出力デバイスからデータおよび命令を受信し、それらにデータおよび命令を送信するように、プログラム可能であり、結合される。アプリケーションプログラムは、高水準手続き型プログラミング言語もしくはオブジェクト指向プログラミング言語で、またはそれが望ましければ、アセンブリ言語もしくは機械語で実施される。いずれの場合も、言語は、コンパイラ言語またはインタープリタ言語である。プログラムは、完全インストールプログラムまたは更新プログラムである。システム上でのプログラムの適用は、いずれの場合も、方法を実行するための命令という結果となる。
【００４９】
さらに、方法の細目（すなわち、Ｓ１０において提供されたデータ、Ｓ２０において計算されたデータ、およびＳ３０において決定された結果）は、すべて、例えば、第三者による後の使用のために、例えば、データファイル内に記憶されることに留意されたい。特に、シミュレーティングは、いつでも、再生／再表示される。また、シミュレーションは、例えば、データファイルに基づいて実行される、製品生産／製造プロセスにおいて実施される。そのようなプロセスは、知られているように、機械加工シミュレーションが繰り返されるシミュレーションフェーズと、その後の、シミュレーションの結果に基づいた、（実際の）工作物に対する（実際の）機械加工フェーズとを含む。例えば、衝突が検出された各シミュレーションにおいて、プロセスは、軌道を調整することによって、シミュレーションを繰り返す。図４のシミュレーションが、衝突の深さ（機械加工の分野において重要であることが知られている古典的データ）の容易な計算を可能にすること、したがって、軌道が、そのようなデータに基づいて、効率的に調整されることができることにここで留意されたい。これは、衝突が検出されなくなるまで、および／または満足な軌道が決定されるまで、繰り返されることができる。その後、実際の機械加工が、実行され、保持されたシミュレーションの軌道を再現する。
【００５０】
提供するステップＳ１０が、今から説明される。
【００５１】
方法は、（工作物の）モデリングされた体積を表すデクセルの集合を提供するステップＳ１０を含む。これは、モデリングされた体積の軽い表現を可能にする（言い換えると、モデリングされた体積は、僅かなメモリ空間しか使用せずに表現される）。これは、容易に処理されるモデリングされた体積の表現も可能にする。特に、モデリングされた体積に対する設計操作は、モデリングされた体積がデクセルの集合によって表される場合、デクセルの集合のデータ構造のおかげで、特に効率的に実行される（例えば、並列化される）。言い換えると、この構造は、超並列処理を可能にする。したがって、設計操作は、高い応答性および高いロバスト性でもって実行される。
【００５２】
本発明の方法の場合、デクセル表現は、衝突テストを実行するために、Ｓ２０およびＳ３０において、さらに明確に依存される。したがって、方法は、デクセル表現の計算上の利点と、シミュレーションにおける現実性についての検討事項とを効率的に結び付ける。
【００５３】
「デクセル」という用語は、（「ピクセル」という用語が、「ピクチャ要素」の簡便表現であるのとまさに同様に）「深さ要素」の簡便表現として知られている。デクセルの概念は、多数の研究論文において言及されている。本発明の方法との関連において、デクセルは、少なくとも１つの線分、すなわち、３Ｄ点の対からなる集合を含む。例では、モデリングされた体積は、少なくとも２つの線分からなる集合を含む、少なくとも１つのデクセルを含む。デクセルの線分は、いくつかある場合は、順序付けられ（そのような場合、デクセルはリストである）、または順序付けられない。デクセルの線分は、直線とモデリングされた体積との間の交わりを表す。言い換えると、モデリングされた体積と交わる仮想直線を考えた場合、デクセルは、与えられた直線に由来し、交わりの計算から得られる線分からなる集合である。したがって、デクセルの集合を提供するステップは、例えば、仮想直線を辿り、Ｂ−Ｒｅｐまたは他の任意の体積表現によって初期的に表されるモデリングされた体積との交わりを計算することによって、そのような交わりを計算するステップを含む。したがって、デクセルの集合は、モデリングされた体積（すなわち、工作物）を表す。
【００５４】
デクセルの集合は、Ｓ１０において、コンピュータ実施データとして提供されることに留意することが大切である。したがって、モデリングされた体積のいずれの表現に関しても、上および下で提供される定義は、データ構造の観点からの意味合いを有する。例えば、線分は、例えば、デクセル直線上の高さなどの、３Ｄ位置の対（例えば、互いに結び付けられる２つの３Ｄ位置）として提供され、また、直線の幾何学（基準点と方向）を用いても提供される。３Ｄ位置は、また、参照３Ｄフレームに関連付けられた３つの座標（例えば、浮動小数点数）のリストとして提供される。デクセルは、線分の集合であり、このことは、定められた構造内で線分が一緒に結び付けられることを暗示する。デクセルの集合のうちのデクセルも、同様に、一緒に結び付けられる。それ自体が少なくとも１つの線分からなる集合を含むデクセルの集合によって工作物を表現することは、工作物の高速な更新ステップＳ３０を可能にする。
【００５５】
デクセルの概念が、デクセルの集合をデクセル構造６７として提供するステップＳ１０の例を提示する、図７ないし図９を参照して、今から図説される。
【００５６】
モデリングされた体積を与え、また無限直線を与えた場合、デクセルは、無限直線と（工作物の）モデリングされた体積との間の交わりを表す線分（または区間）からなる集合である。線分からなるこの集合は、各線分の境界点の集合として、メモリ内にキャプチャされる。例えば、基準点／原点（高さが０−ゼロ−の点）が、各直線上に定義され、その直線上の高さ（例えば、代数値、すなわち、負または正のスカラ値、例えば、符号化された整数または実数、例えば、浮動小数点数または他の任意の適合されたデータ種類）が、境界点を決定する（高さを定義するためのこのフレームワークはＳ２０に適用され、例えば、同じ原点が用いられることに留意されたい）。デクセル構造は、例えば、長方形グリッド上に順序付けられることによって組織された、（各々が線分の集合を含む）デクセルの集合である（例えば、同じ方向を共有し、例えば、構造全体は、その方向が２つずつ直交する３つのグリッドを含む）。図７および図８は、モデリングされた体積４０を、１０×１０の直線５０のグリッドと一緒に示している。例の方法は、（工作物を表す）モデリングされた体積４０を、図７に示されるように、例えば、Ｂ−Ｒｅｐとして、提供するステップを含む。次に、例の方法は、図８に示されるように、モデリングされた体積４０と（少なくとも部分的に）交わる１０×１０の直線５０のグリッドを定めるステップを含む。次に、例の方法は、図９に表されるように、線分６０および／または線分６２の集合を含むデクセル６５を計算するステップを含む。図では、１つのデクセル６５が、円で囲まれている。デクセル６５は、直線５０がモデリングされた体積４０と１つの場所で交わるか、それともいくつかの別々の場所で交わるかに応じて、いくつかの線分６０、または１つの線分６２を含む。もちろん、方法は、あるいは、デクセル６５をメモリから取り出す。いずれの場合も、デクセル構造６７は、このようにして提供される。
【００５７】
図９は、結果のデクセル構造６７を示している。必ずしもすべての直線５０がモデリングされた体積４０と交わるわけではなく（例では、５２本の直線のみがモデリングされた体積４０と交わる）、交わったのと同数のデクセル６５を生成する（モデリングされた体積４０と交わらない直線は完全に捨てられ、デクセルを生成しない）ことに留意されたい。さらに、いくつかの直線５０は、１つの線分６２を通して、モデリングされた体積４０と交わり（例えば、デクセル（２，３）またはデクセル（９，６））、他は、いくつかの線分６０を通して、例えば、２つの線分（例えば、デクセル（７，７）もしくはデクセル（４，７））、または３つの線分（デクセル（２，８）もしくはデクセル（５，８））、または４つの線分（デクセル（２，９）もしくはデクセル（４，９））を通して、モデリングされた体積４０と交わる。結果のデクセル構造６７は、１つの線分６２を有する３６個のデクセル６５、２つの線分６０を有する６個のデクセル６５、３つの線分６０を有する５個のデクセル６５、および４つの線分６０を有する５個のデクセルを含む、５２個のデクセル６５を含む。
【００５８】
Ｓ１０において提供されるデクセルの集合は、トリデクセル構造である。トリデクセル構造は、３つのデクセル構造を含むことによって、一般に、ｘ軸に平行なデクセル構造、ｙ軸に平行なデクセル構造、およびｚ軸に平行なデクセル構造を含むことによって定義される。方法は、任意の時間に、例えば、計算するステップＳ２０およびテストするステップＳ３０の間に、工作物のグラフィカル表現を表示するステップを含む。表示するステップは、デクセルの集合に基づく。トリデクセル構造は、「ビュー方向」にほとんど依存しないので、良好な表示を提供する。トリデクセル構造は、特に、ユーザが視点を変えた場合に、より正確な表示を提供する。
【００５９】
図１０ないし図１２は、各々が、同じモデリングされた体積を表すデクセル構造を示している。言い換えると、モデリングされた体積は、図１０ないし図１２の（例えば、直交した方向を有する）３つのデクセル構造を含む、トリデクセルデータによって定義される。図１０は、ｙ軸に沿ったデクセル構造６７を示している。図１１は、ｘ軸に沿ったデクセル構造６８を示している。図１２は、ｚ軸に沿ったデクセル構造６９を示している。各図において、デクセルの直線は、それぞれの軸に平行である。
【００６０】
本発明の方法のための機械加工シミュレーションの原理は、各デクセルの工具の掃引体積との交わりを計算すること、およびその材料区間をしかるべく切り取ることである。本発明は、少なくとも仮想的に、（１）Ｓ２０において、工具の刃部との交わりおよび非刃部との交わりを計算することによって、ならびに（２）Ｓ３０において、これらの交わりを時系列に従って順序付けることによって、１ステップさらに先に進む。次に、刃部が非刃部より前に材料と出会うか、それとも後に出会うかを理解し、実際の衝突のみを報告することが可能である。
【００６１】
Ｓ１０において提供されるデータは、また、（切削工具の幾何学的形状に対応する）メッシュの集合の形態での切削工具の表現を含む。メッシュは、頂点（３Ｄ位置）と、頂点を２つずつ結び付け、メッシュのいわゆる面分（すなわち、辺の最小循環）を形成する辺（例えば、線分）とを有する、任意のグラフ構造を指定する。メッシュは、特に、Ｓ２０における高速で簡単な計算のための、（主にまたは完全に４辺の−凸−面分からなる）四辺形メッシュ、および（主にまたは完全に３辺の面分からなる）三角形メッシュを含む、凸面分メッシュ−例えば、凸多角形の面分を有するメッシュ−など、異なる種類のうちの１つである。他の精緻化された例では、メッシュは、Ｂ−Ｒｅｐなどの、より複雑な構造を有し、「メッシュ」という用語は、そのようなケースでは、最も汎用的な定義で理解される。
【００６２】
（現実世界の工具に対応する）工具モデルは、各立体が刃部または非刃部である、隣接する立体のリストによって定義される。例では、メッシュは、立体の三角分割された境界である。結果として、工具は、Ｓ１０において、閉じられた自身と交わらないメッシュのリストとして提供される。各メッシュは、工具の刃部または工具の非刃部を表す。刃部を表すメッシュは、例えば、「切削」とラベル付けされ、および／または非刃部を表すメッシュは、例えば、「衝突」とラベル付けされる。工具の２つのメッシュの交わりは、ゼロ体積を有し、すなわち、２つのメッシュは、分離されているか、またはそれらは、接触エリアをモデリングする面分（もしくは面分の重なり）を共有することを意味する。任意の工具の幾何学的形状が、ブール多面体操作を使用することによって、このように表されることができる。そのため、これらの仮定は、方法の一般性を制約しない。
【００６３】
また、Ｓ１０において、切削工具の軌道が、提供される。方法は、主に３軸軌道について後で説明されるが、より複雑な軌道（例えば、５軸）に拡張されることができる。軌道は、３次元空間における折れ線として提供され、各直線分は、以下では、「基本軌道」と呼ばれる。３軸軌道の直線分に沿って、工具は、平行移動によって移動する。５軸軌道の直線分に沿って、工具は、平行移動によって移動し、加えて、工具の軸が、初期の向きから最終の向きに線形に変化する。しかしながら、Ｓ１０において提供される軌道を規定する他の任意の方法も、企図されている。
【００６４】
次に、方法は、モデリングされた体積の各デクセルＤに対する特定の処理を含む。最初に、方法は、Ｓ２０において、各メッシュＭに関して、シミュレーションのいわゆる「（ｈ，ｔ）図」を形成する、（以下では、Ｌ1、Ｌ2、Ｌ3と呼ばれる）すべてのポリラインの端点を計算する。定義によって、ポリラインは、（ｈ，ｔ）位置を記述し、言い換えると、（例えば、任意の−例えば、恣意的な−原点／基準、および／または任意の−例えば、恣意的な−スケールに基づいた、例えば、上で言及された高さの定義を使用する）デクセルの高さに対応する横座標と、時刻に対応する縦座標とを用いて、２Ｄ位置を記述する。方法のどこで与えられるデクセルに対しても、スケールが一貫している（例えば、同じである）限り、任意の高さスケールおよび／または時間スケールが、実施される。より容易な実施のために、同じスケールが、すべてのデクセルに対して実施される。高さスケールに関して、例えば、図１０ないし図１２のうちの１つなどの、トリデクセル構造の場合、各方向の原点は、同じ方向を有する直線によって支持されるすべてのデクセルについて−その直線に直交する同じ平面上に定義される。必ずしもすべてのこれらのデータが、Ｓ２０において計算されるわけではなく、（（切削／衝突属性情報は別として）さらなるどのような情報も用いずに、単なる整数および／または実数の値の組（すなわち、順序付けられた対）として表される）比較可能な（ｈ，ｔ）位置を有することが必要であるにすぎないことに留意されたい。したがって、後でより詳細に説明される（ｈ，ｔ）図は、またポリラインでさえも、本発明の方法によって処理されるデータが関連付けられる数学的対象として理解されなければならない（特に、Ｓ２０において計算されるデータは、図のすべてのポリラインの端点を含む）。
【００６５】
さて、ポリラインは、定義によって、切削工具の軌道に従った、それぞれのデクセルＤの直線とそれぞれのメッシュとの間の交わりの時刻ｔを、交わりの高さｈの関数として記述する／表す（したがって、ポリラインは、メッシュの集合のうちのそれぞれのメッシュに関連付けられるが、１つのメッシュは、軌道の複雑さと、同じくメッシュの複雑さとに応じて、いくつかのそれぞれのポリラインに関連付けられることに留意されたく、メッシュが凸体積を定義する場合、それは−例えば、平行移動軌道上に−単一のポリラインを生成するが、メッシュが凸体積を定義しない場合、同じ軌道に対して、それは可視部分が接続部分を有するのと同じ数のポリラインを生成することに留意されたい）（上で言及されたように、任意のタイミング／スピード、例えば、一定時間が、軌道について保持され、そのため、接続された完全な線分から各々が成るポリラインを獲得しなければならず、後で詳述される（ｈ，ｔ）図の主な特性は、いずれにせよ、より一般的なケースにも同様に適用されることに留意されたい）。実際に、各メッシュは、軌道に従って仮想的に動かされ、それによって、各デクセルの直線と仮想的に出会う／交わる（交わらない−例えば、メッシュが与えられた直線と決して出会わない−ことは、数学的には−したがって、実施においては−一般性を失うことなく、空／ゼロのポリラインに関連付けられた空の交わりとして理解される）。方法は、すべてのメッシュについて、時刻に対するそのような出会いの高さを仮想的に追跡する。次に、方法は、高さに対する出会いの時刻（追跡されたデータの逆）を仮想的に考える。しかし、方法は、最終的に、Ｓ２０において、ポリラインの端点のみを計算する。
【００６６】
Ｓ２０および（すべてのメッシュについて）すべてのポリラインの端点を考えるおかげで、また（ｈ，ｔ）図の特定の性質のおかげで、次に、方法は、Ｓ３０において、衝突があるかどうかを（依然として各デクセルについて）単純にテストし、それは、衝突がある場合は、衝突の深さ（デクセル直線、およびデクセル直線上における衝突の境界高さ）をさらに提供する。テストするステップＳ３０は、特に、すべてのメッシュのすべてのポリラインからなる集合の下側包絡線（ｅｎｖｅｌｏｐｅ）に属する位置に対応する高さの値について、その位置が属するポリラインが非刃部に関連付けられる場合、高さの値が、デクセルの線分に属するか（すなわち、高さの値も、デクセル内に保たれた材料区間内に含まれるか）どうかを決定するステップを含む。（（ｈ，ｔ）図の特定の向きに関する、言い換えると、時刻に関する、さらに言い換えると、ｈ軸上への射影に関する、（ｈ，ｔ）図内のポリラインに関する場合の古典的な下側包絡線（ｅｎｖｅｌｏｐｅ）の定義では、高さに対するポリラインの最小時刻位置−言い換えると、（ｈ，ｔ）の組−として定義される）すべてのメッシュのすべてのポリラインからなる集合の下側包絡線（ｅｎｖｅｌｏｐｅ）は、仮想的に考えられた数学的対象にすぎず、テストするステップは、実際には、そのような対象が計算されることを必要としないことにここで再び留意されたい。ポリラインの２Ｄ図における下側包絡線（ｅｎｖｅｌｏｐｅ）は、（０，−∞）に座って上方を見上げている観測者によって見られることができるポリラインの一部として定義される２Ｄオブジェクトでもある。掃引メッシュとデクセルとの間の交わりによって与えられる、（ｈ，ｔ）平面内のポリラインは、区分的線形関数のグラフであることに留意されたい。したがって、時間値に関する下側包絡線（ｅｎｖｅｌｏｐｅ）の計算は、古典的な定義の適用にすぎない。実際に、デクセルの線分／区間上の（したがって、空中／空に対応するデクセルの非線分位置とは対照的に、工作物材料に対応する）点は、（時間的に）最初に切削メッシュによって出会われるか、それとも衝突メッシュによって出会われるかをテストされるにすぎない。これは、すべてのポリラインのすべての端点が、集められ、それらのポリラインが対応するメッシュの種類に基づいて、「切削」または「衝突」ラベル／属性にひとたび関連付けられると、（後で説明される（ｈ，ｔ）図の特性のおかげで）上で提供された数学的な便法を用いて容易に行われる。ある意味では、これは、ポリラインの下側包絡線（ｅｎｖｅｌｏｐｅ）をデクセル上に射影し、デクセルの各線分の各位置について、衝突ラベルを付された位置が最初に射影されたものかどうかを決定することに相当する（該当する場合は、衝突があるが、それは、その反対の−すなわち、切削ラベルを付された位置が最初に射影された、またはポリライン位置がまったく射影されない−場合は、衝突がなく、刃部との出会いがあり、したがって、材料の除去を行うためであり、または出会いがまったくないためである）。
【００６７】
明らかに、テストＳ３０がひとたび実行されると、例えば、特に、テストの結論が、衝突がないというものである場合、方法は、切削工具の刃部との交わりの位置−すなわち、高さ−（および、例えば、その時刻）に従って、線分またはその部分を除去することによって、デクセルの集合を更新するステップを含む。そのようなデータは、実際には、Ｓ２０および／またはＳ３０において決定されるデータの一部である。
【００６８】
したがって、方法は、衝突の高速な検出を可能にし、それは、衝突の深さ（衝突の大きさおよび位置）さえ正確に提供することができ、デクセルにわたる超並列化を介して実行されることができる。（ロバストで包括的な衝突検出を提供する）正確な解の問題に取り組むことは、先行技術においては、おそらくは、機械加工の全工程の記述を獲得することは、（計算の観点から見て）複雑すぎると考えられていたために、（機械加工シミュレーションはすでに長年にわたって研究されてきたが）実行されていないことに留意されたい。基本的に、連続問題は、コンピュータ実施ソリューションが理論的に提示する際限のない複雑さのために、当然ながら回避される。しかしながら、方法は、（テストＳ３０をＳ２０において計算された端点、したがって、入力の離散化集合に基づかせて）問題を離散化することによって、正確な解に到達する。しかしながら、離散化は、（先行技術の時系列方法におけるように）時間上ではなく、デクセル上で実行され、このことが、より現実的な解をもたらす。これは、端点を支持する基礎となる図の特定の特性を利用することによって行われる。これは、後で詳述される。さらに、この表現は、超並列計算により適しており、精巧な工作物の離散化の場合であっても良好な性能を可能にする。
【００６９】
例では、方法は、（例えば、立体の三角分割された境界を掃引することによる）掃引体積、および／または掃引表面を（Ｓ２０内で）計算するために、Ｓ１０において提供された軌道を利用する。典型的な参考文献（例えば、非特許文献１８を参照）が存在する。この概念は、これ以降で詳述される。
【００７０】
３次元空間の部分集合
【００７１】
【数１】
0006787661.tif 000002
【００７２】
を与え、点
【００７３】
【数２】
0006787661.tif 000003
【００７４】
を与えると、Ｍ＋Ｐという表記は、集合ＭをＰに平行移動したものである。正確には、Ｍ＋Ｐ＝｛ｘ＋Ｐ，ｘ∈Ｍ｝である。
【００７５】
メッシュＭを与え、それぞれ基本軌道の始点および終点である
【００７６】
【数３】
0006787661.tif 000004
【００７７】
を与えると、基本軌道に沿ったメッシュＭの掃引Ｓ（Ｍ）は、
【００７８】
【数４】
0006787661.tif 000005
【００７９】
によって定義される。
【００８０】
掃引は、直線分［Ｐstart，Ｐend］に沿ったＭのすべての平行移動の和集合である。先の式において、パラメータｔ∈［０，１］は、時間の役割を果たす。ｔ＝０において、メッシュＭは、位置Ｐstartに平行移動され、それは、Ｍ＋Ｐstartと書かれる。ｔ＝１において、メッシュＭは、位置Ｐendに平行移動され、それは、Ｍ＋Ｐendと書かれる。これは、（明確にするために２Ｄで）図１３に示されている。
【００８１】
計算上の目的で、またロバスト性の目的で（特に、循環ポリラインとは対照的に、利用可能なポリラインを考えるために）、Ｍの可視部分のみが、方法によって使用される（さらなる詳細は後で提供される）。Ｍ+と表記されるＭの可視部分は、Ｐend−Ｐstartと、ＮPと表記されるＰにおけるＭの外向き法線とのスカラ積が正である、すなわち、〈Ｐend−Ｐstart，ＮP〉＞０であるような、点Ｐ∈Ｍの集合である。図１４は、可視Ｍの２Ｄの例を示している。Ｍ+は直線分から作成されるので、掃引エリアＳ（Ｍ+）は、図１５に示されるように、隣接する平行四辺形から作成される。三角分割されたＭの３Ｄバージョンが、図１６に示されている。左図は、Ｍであり、右図は、ＰstartおよびＰendに従ったＭ+である。図１７は、Ｍ+の１つの三角形の掃引を示している。それは、基本掃引体積という結果を生じ、それは、以下の境界面分（すなわち、三角形メッシュ面分の軌道にわたる積分−掃引−によって定義される体積の外側面分、そのような境界面分は、それらが掃引体積の外側表面全体の区画化を形成する限り、おそらく任意の方法で、例えば、外側表面のすべての最大平面として、またはそれの最大三角形として、定義される）を含む、すなわち、開始三角形τstartと、終了三角形τendと、６つの側面三角形とを含む、三角柱（ｐｒｉｓｍ）である。（三角柱も、文献（例えば、非特許文献１９を参照）において説明されているように、三角形の軌道に沿った時間を定義する１Ｄ線分とのデカルト積であることに留意されたい。）これら６つの側面三角形は、３軸機械加工軌道を扱う場合は、３つの平行四辺形であることが分かる。結果の掃引体積Ｓ（Ｍ+）は、Ｍ+の各三角形に対して１つの三角柱の、隣接するそのような三角柱から作成される。明確にするために、必ずしもすべての三角形が示されるわけではないことに留意されたい。
【００８２】
方法は、いわゆる（ｈ，ｔ）図を巧みに考える。図１８は、軌道（太い矢印）に従って初期位置から終了位置まで（一定のスピードで）掃引された、ｙｚ空間内における直線分Ｍ（太い直線）を示している。Ｍの掃引エリアＳ（Ｍ）は、平行四辺形である。
【００８３】
デクセル（垂直線）と関連付けられた（ｈ，ｔ）図が、今から詳述される。（上で説明されたように、実際には、方法によって必ずしも実行される必要がない、（ｈ，ｔ）図を描くための）第１のステップは、デクセル直線と掃引エリアＳ（Ｍ）の境界との間の交点を計算することであり、それは、点Ｐ1およびＰ2を生成する。これらの交点から、デクセル直線上のそれぞれの横座標である、高さｈ1およびｈ2が得られる。次に、（例えば、一定）スピードの移動という仮定のおかげで、時刻ｔ1およびｔ2が、図１８に示されるように、しかるべく計算される。計算の数学的操作が、後で詳述される。
【００８４】
今から、デクセルと関連付けられた（ｈ，ｔ）図が、略述される。それは、（３次元工作物および工具用ではあるが）２次元図である。高さ値ｈ1およびｈ2は、水平ｈ軸上で報告され、時刻値ｔ1およびｔ2は、垂直ｔ軸上で報告される。これは、図１９に示されるように、点（ｈ1，ｔ1）と点（ｈ2，ｔ2）を結合する直線分を定める。
【００８５】
物理的表現は、以下の通りである。時刻ｔ＜ｔ1である場合、デクセル直線は、移動する直線分Ｍと会わない。時刻ｔ＝ｔ1である場合、直線分の下側頂点が、高さｈ1においてデクセル直線と出会う。時刻ｔ＝ｔ1から時刻ｔ＝ｔ2までは、直線デクセルと移動する直線分Ｍとの間の交点は、直線デクセルに沿ってＰ1からＰ2まで移動する点である。ｔとｈとの間の従属性は、線形である。ｔ＞ｔ2である場合、デクセルは、もはや移動する直線分Ｍと会わない。
【００８６】
明確にするために、以下の説明は、２次元工作物および工具を用いて、詳しく説明される。今から、図２０に示される、２Ｄ工作物、工具、軌道、デクセルについて考察する。
【００８７】
まさに最初のステップは、デクセル直線と工作物との間の交わりである、初期工作物区間を計算することである。これは、図２１に示されるように、値ｈ0および値ｈ9を生成する。工作物の形状に応じて、デクセルとの交わりは、いくつかの区間を含む。次に、工具の非刃部の掃引体積が、計算され、それのデクセル直線との交わりは、図２２に示されるように、ｔ1、ｔ2、ｈ1、ｈ2を生成する。次に、工具の第１の刃部の掃引体積が、計算され、それのデクセル直線との交わりは、図２３に示されるように、ｔ3、ｔ4、ｈ3、ｈ4を生成する。次に、工具の第２の刃部の掃引体積が、計算され、それのデクセル直線との交わりは、図２４に示されるように、ｔ5、ｔ6、ｈ5、ｈ6を生成する。次に、工具の第３の刃部の掃引体積が、計算され、それのデクセル直線との交わりは、図２５に示されるように、ｔ7、ｔ8、ｈ7、ｈ8を生成する。
【００８８】
高さおよび時刻の先の計算のすべてが、今度は、図２６に示されるように、デクセルＤの（ｈ，ｔ）図内に集められる。［ｈ0，ｈ9］線分は、デクセル直線と工作物との間の交わりである、いわゆる工作物区間である。それは、ｈ軸上に表される。（ｈ，ｔ）図は、正確な衝突診断が実行されることができるように、時間情報および空間情報をキャプチャする。
【００８９】
（ｈ，ｔ）図は、「切削」または「衝突」とラベル付けされた非垂直の直線分の集合を含む。衝突診断（Ｓ３０）は、以下のように実施される。工作物区間のすべての点から、ｔ方向に垂直線を描く。そのような各直線が、衝突直線よりも前に切削直線と出会った場合、衝突はない。そうではない場合、衝突がある。例では、切削直線２、３が、衝突直線よりもｔ方向に関して下側に配置されているので、期待通り、衝突はない。
【００９０】
本発明の方法の衝突診断の簡潔性およびロバスト性をもたらす、（ｈ，ｔ）図の先に言及された特性が、今から説明される。
【００９１】
構成によって、（ｈ，ｔ）図は、「切削」または「衝突」とラベル付けされた（軌道は点軌道を除外した−すなわち、ＰＳｔａｒｔ≠ＰＥｎｄである−剛体運動であるという事実によって確保される）非垂直の直線分の集合を含む。これらの直線分は、計算を加速するための有益な特性を特徴とする。第１に、２つの直線分は、図２７に示されるものとは異なり、内部点において交差することができない。第２に、２つの直線分は、図２８に示されるものとは異なり、端点を共有すること、および重なり合うことができない。これは、刃部の内部と非刃部の内部は、同じ時刻に同じ場所に配置されることができないからである。
【００９２】
結果として、（ｈ，ｔ）図の直線分は、各々が数学的写像
【００９３】
【数５】
0006787661.tif 000006
【００９４】
によって定義される、切削ポリラインと衝突ポリラインからなる集合として（より正確には、そのような区分的線形写像のグラフとして）配置されることができる。さらに、任意の２つのポリラインは、内部点において交差することができない。
【００９５】
【数６】
0006787661.tif 000007
【００９６】
であれば、Ｌi（ｈ）＝＋∞であるという規定は、以下における最小値計算を容易にする。
【００９７】
２Ｄの例は、切削ポリライン
【００９８】
【数７】
0006787661.tif 000008
【００９９】
と、切削ポリライン
【０１００】
【数８】
0006787661.tif 000009
【０１０１】
と、衝突ポリライン
【０１０２】
【数９】
0006787661.tif 000010
【０１０３】
とに中心的役割を演じさせる。
【０１０４】
（衝突診断を計算する）Ｓ３０の例が、今から説明される。この例は、単に１つの可能な実施であるにすぎず、この例の一般的なアイデアは、他の方法でも実施される。
【０１０５】
計算の観点から見て、与えられたデクセルＤの衝突診断は、例では、以下のように実行される。ポリライン
【０１０６】
【数１０】
0006787661.tif 000011
【０１０７】
を与え、デクセルＤのすべての工作物区間の和集合Ｂを与えると、第１のステップは、数
【０１０８】
【数１１】
0006787661.tif 000012
【０１０９】
の集合をソートして、リストｈ1≦ｈ2≦…≦ｈ2nにすることである。この順序付けられたリストは、衝突ポリラインの横座標ｈjと切削ポリラインの横座標ｈjとを混ぜ合わせたものであることが理解されなければならない。第２のステップは、すべての衝突区間［ｈj，ｈj+1］を、その上方で定義されたより下方のポリラインの種類に応じて、識別することである。次のアルゴリズムは、衝突集合Ｃを、すべての衝突区間［ｈj，ｈj+1］の和集合として計算する。
【０１１０】
Ｃ：＝φ
Ｆｏｒ  ｊ：＝１  ｔｏ  ２ｎ−１  ｄｏ  ｂｅｇｉｎ
【０１１１】
【数１２】
0006787661.tif 000013
【０１１２】
Ｌk（ｍ）＝ｍｉｎ｛Ｌi（ｍ），ｉ＝１，…，ｎ｝であるような、ｋ∈（１，…，ｎ）を見つける
Ｉｆ  ポリラインＬkの種類が「衝突」  ｔｈｅｎ
Ｃ：＝Ｃ∪［ｈj，ｈj+1］
Ｅｎｄ  ｉｆ
Ｅｎｄ  ｆｏｒ
工作物集合Ｂが衝突集合Ｃと出会う、すなわち、Ｃ∩Ｂ≠φである場合に限って、衝突が発生する。これは、工作物の材料が、デクセルに沿って、工具の刃部よりも前に工具の非刃部と出会うことを意味する。
【０１１３】
図２９は、３つのポリライン
【０１１４】
【数１３】
0006787661.tif 000014
【０１１５】
についてのアルゴリズムを示している。横座標ｈj、ｉ＝１，…，６のソートされたリストは、
【０１１６】
【数１４】
0006787661.tif 000015
【０１１７】
である。結果の衝突集合は、
【０１１８】
【数１５】
0006787661.tif 000016
【０１１９】
である。例えば、区間
【０１２０】
【数１６】
0006787661.tif 000017
【０１２１】
は、
【０１２２】
【数１７】
0006787661.tif 000018
【０１２３】
であるために、またＬ2が衝突ポリラインであるために、衝突区間である。工作物集合は、示されていない。
【０１２４】
２Ｄの例に戻ると、衝突集合は、工作物区間Ｂ＝［ｈ0，ｈ9］と出会わない、Ｃ＝［ｈ6，ｈ2］であり、そのため、デクセルに沿って、衝突はない。
【０１２５】
方法によって従われる（少なくとも概念的な）スキームの要約が、これ以降で説明される（方法はむしろポリライン端点のみを計算するにすぎないことに今一度留意されたい）。
【０１２６】
工具は、隣接する刃部と非刃部とを含む。各部分は、「メッシュ」と呼ばれる、三角分割された閉じられた境界によってモデリングされる。工作物は、トリデクセル構造によってモデリングされる。物体の掃引は、軌道に沿って平行移動された物体のコピーの和集合である。工具軌道の基本ステップは、２つの連続する位置の間における工具の運動である。一般性を失うことなく、方法は、時間が２つの連続する工具位置の間で線形に変化し、始点は０に等しい時刻であり、終点は１に等しい時刻であると見なす。デクセルと工具掃引との間の交わりを計算する間に、方法は、各工具メッシュがデクセルと交わる時刻も計算する。時刻からなる結果の集合をソートすることによって、方法は、工具部分がデクセル上に保たれた物質区間（物質区間は工作物物質を表すことを想起されたい）と最初に出会うあらゆる場所を決定することが可能である。非刃部が物質と最初に出会う場合、衝突は、報告されない。
【０１２７】
例における方法の主要な特徴は、掃引体積の幾何学的形状をもっぱら使用することによって、デクセルとの交わりの時刻を計算することである。この情報は、いわゆる（ｈ，ｔ）図内に集められる。これは、スピードの向上、信頼性の向上、および一般性の向上という結果となる。各基本軌道ステップを精緻化することは、必要とされず、したがって、良好なスピード性能を可能にする。信頼性は、いかなる数値精度値にも依存しない。性能および信頼性は、変位ベクトルの方向に依存しない。一般性：入力メッシュに対して設けられる唯一の仮定は、これらのメッシュは現実の３Ｄ立体の境界に近づくはずであるので、ほとんどのケースで検証される。必要である場合は、多くの既存のアルゴリズムが、これらのメッシュを修復するためのプリプロセッサとして、使用されることができる。
【０１２８】
より具体的には、例では、（例えば、Ｌ1、Ｌ2、Ｌ3と上で呼ばれた）すべてのポリラインの端点を計算するステップＳ２０は、各メッシュＭについて、およびそれぞれのポリラインの各端点について、それぞれのポリラインに関連付けられたメッシュのすべての面分に基づいて、デクセルの直線のそれとの交わりが端点に対応する、切削工具の軌道に従ってメッシュの面分によって掃引された体積Ｓ（τ）の境界面分を決定する（Ｓ２８２と呼ばれる）サブステップを含む。（ｈ，ｔ）図の定義、およびそれを形成するポリラインの定義のおかげで、また３Ｄ幾何学理論のおかげで、ポリラインの端点は、（それぞれのデクセルの）支持直線と、それぞれのメッシュの面分のうちの１つによって掃引された体積の外側境界との交わりに対応する。図１７に関する説明を参照して、メッシュの面分によって掃引された体積Ｓ（τ）の「境界面分」について説明する。方法は、すべての潜在的な境界面分のうちで、そのような境界面分を決定する（すべてのそのような境界面分は、必ずしも計算される必要がないことに留意されたい）。次に、例の計算するステップＳ２０は、デクセルの直線と決定された境界面分との間のそのような（幾何学的な）交わりに基づいて、（保持されたスケールに関して）それぞれの端点を定める時刻および高さを計算する（Ｓ２８４と呼ばれる）サブステップを含む。これは、簡単な計算するステップＳ２０を可能にする。実際に、この時刻の計算は、３Ｄ交点が同じ三角柱内に保たれる限り、時刻と高さとは線形に変化するので、幾何学的な考察から直接的にもたらされる。
【０１２９】
３Ｄ直線／三角形の交わりを通して「ｈ」パラメータを計算するこの方法が、例において、今からさらに詳述される。
【０１３０】
三角形
【０１３１】
【数１８】
0006787661.tif 000019
【０１３２】
および直線
【０１３３】
【数１９】
0006787661.tif 000020
【０１３４】
を考える。目標は、直線が三角形と交わるかどうかをテストすることと、交わる場合、デクセルフレームにおける交点の座標を計算することである。特に、これらの座標は、Ｄ上の高さを含む（または少なくとももたらす）。
【０１３５】
Ｑを、Ｄに直交する平面とし、ｄを、ＤとＱとの交点とする。ｘｙｚが基準軸座標系であることに留意すると、Ｄが（高さを表す）ｚ軸に平行である場合、Ｑは、ｘｙ平面であり、Ｄは、（デクセルグリッドの支持平面を表す）平面ｘｙ内の２つの座標（ｘD，ｙD）によって定義される。Ｄがｙ軸に平行である場合、Ｑは、ｚｘ平面であり、Ｄは、平面ｚｘ内の２つの座標（ｚD，ｘD）によって定義される。Ｄがｘ軸に平行である場合、Ｑは、ｙｚ平面であり、Ｄは、平面ｙｚ内の２つの座標（ｙD，ｚD）によって定義される。
【０１３６】
Ｕ、Ｖ、Ｗを、三角形Δの頂点とし、Ｕ’、Ｖ’、Ｗ’を、２Ｄ三角形Δ’を定義する、平面Ｑ上のそれぞれの射影とする。図３１は、Ｄがｚ軸に平行である場合の幾何学を示している。
【０１３７】
点ｄが三角形Δ’の内部にある場合に限って、直線Ｄが三角形Δと出会うことが、現状技術からよく知られている。３つの代数的エリアＡｒｅａ（ｄ，Ｖ’，Ｗ’）、Ａｒｅａ（Ｕ’，ｄ，Ｗ’）、およびＡｒｅａ（Ｕ’，Ｖ’，ｄ）のすべてが、同じ符号を有する場合に限って、点ｄは、三角形Δ’の内部にある。さらに、交点Ｄ∩Δの高さｈは、
【０１３８】
【数２０】
0006787661.tif 000021
【０１３９】
であり、ここで、ｈu、ｈv、ｈwは、それぞれ、直線Ｄに沿った点Ｕ、Ｖ、Ｗの高さである。
【０１４０】
最後に、点Ｄ∩Δの３Ｄ座標は、平面Ｑ内におけるＤの２Ｄ座標をｈと一緒に組み合わせることによって知られる。Ｄがｚ軸に平行である場合、Ｄ∩Δ＝（ｘD，ｙD，ｈ）である。Ｄがｙ軸に平行である場合、Ｄ∩Δ＝（ｘD，ｈ，ｚD）である。Ｄがｘ軸に平行である場合、Ｄ∩Δ＝（ｈ，ｙD，ｚD）である。
【０１４１】
「ｔ」パラメータを計算するこの方法が、例において、今から説明される。
【０１４２】
三角形
【０１４３】
【数２１】
0006787661.tif 000022
【０１４４】
が
【０１４５】
【数２２】
0006787661.tif 000023
【０１４６】
から
【０１４７】
【数２３】
0006787661.tif 000024
【０１４８】
まで平行移動される状況について考える。Ｔを、（非退化三角柱である）対応する掃引体積であるとする。
【０１４９】
【数２４】
0006787661.tif 000025
【０１５０】
Ａ、Ｂ、Ｃを、三角形τの頂点、ｅ1＝Ｂ−Ａ、ｅ2＝Ｃ−Ａ、ｅ3＝Ｐend−Ｐstartとする。これは、図３２に示されている。τstart＝τ＋Ｐstartを、三角形τの初期コピーとし、τend＝τ＋Ｐendを、三角形τの最終コピーとする。三角形τは、退化していないので、ベクトルｅ1とベクトルｅ2は、同一線上にない。三角形τは、その支持平面に沿って平行移動されないので、ベクトルｅ3は、ｅ1とｅ2とによって張られた平面に属さない。このことは、行列［ｅ1  ｅ2  ｅ3］を可逆にする。結果として、任意の点Ｐ∈Ｔは、３つの数ｒ、ｓ、ｔによって、
Ｐ＝Ａ＋ｒｅ1＋ｓｅ2＋ｔｅ3
のように一意的に表される。
【０１５１】
ベクトルｅ1、ｅ2、ｅ3は、正規化されておらず、それらは、互いに直交しないことに留意されたい。
【０１５２】
点Ｐの座標を与えると、数ｒ、ｓ、ｔは、１次連立方程式
【０１５３】
【数２５】
0006787661.tif 000026
【０１５４】
を解くことによって計算されることができる。
【０１５５】
数ｔは、三角形τがＰstartからＰendまで移動するときに、時間の役割を果たす。ｔ＝０である場合、点Ｐは、τstartに属し、ｔ＝１である場合、点Ｐは、τendに属し、０＜ｔ＜１である場合、点Ｐは、中間三角形τ＋（ｔＰend＋（１−ｔ）Ｐstart）に属する。
【０１５６】
３次元幾何学の（ｈ，ｔ）図への一般化が、今から説明される。
【０１５７】
三角柱は、２つの三角形（τstartおよびτend）と、３つの平面の平行四辺形とを含む。平行四辺形は、三角柱Ｔが、τstartおよびτendに加えて、６つの側面三角形を含むように三角分割される。そのような三角分割された三角柱と、デクセル直線Ｄとを与えると、Ｄ∩Ｔを計算することは、先の段落で説明されたように、直線／三角形の交わりの問題になる。Ｐ∈Ｄ∩Ｔとする。ｈパラメータは、式（１）を使用して計算され、ｔパラメータは、式（２）を使用して計算される。Ｐがτstartに属する場合、ｔパラメータは、ｔ＝０である。Ｐがτendに属する場合、ｔパラメータは、ｔ＝１である。
【０１５８】
データ構造は、例では、Ｄ∩Ｔ内に点が存在するのと、またＤとの非空の交わりを特徴とする三角柱Ｔが存在するのと同数の（ｈ，ｔ）パラメータをデクセルＤと関連付ける。例では、ポリラインの端点のみが保持され、または最初に計算されさえする。
【０１５９】
図３３は、Ｄ∩Ｔ＝｛Ｐ1，Ｐ2｝を示しており、ここで、Ｐ1∈τstart、すなわち、ｔ1＝０であり、Ｐ2は、側面三角形に属し、すなわち、０＜ｔ2＜１である。データ構造は、（ｈ1，ｔ1）および（ｈ2，ｔ2）をデクセルＤと関連付ける。図３４は、Ｄ∩Ｔ＝｛Ｐ1，Ｐ2｝を示しており、ここで、Ｐ1およびＰ2は、側面三角形に属し、すなわち、０＜ｔ1＜１、０＜ｔ2＜１である。データ構造は、（ｈ1，ｔ1）および（ｈ2，ｔ2）をデクセルＤと関連付ける。
【０１６０】
図３１ないし図３４を参照して設計された例示的な計算の５軸軌道への一般化が、今から説明される。
【０１６１】
平行移動によって定義される基本軌道のための方法は、回転を含む剛体運動によって定義される基本軌道に一般化されることができる。これは、回転の角度値が十分に小さいならば、なおさらそうである。以下は、この状況において、（ｈ，ｔ）パラメータをどのように計算するかを説明する。
【０１６２】
τstartおよびτendを、基本軌道の初期三角形および終了三角形とする。掃引体積の境界は、三角形τstartおよびτendと一緒に、６つの側面三角形によって近似される。τstartの頂点をτend内のそのそれぞれのコピーと結び付ける３つの直線分は、図３５に示されるように、「時間線分」と呼ばれる。次に、近似掃引体積が、３つの四面体に分割される。それらのうちの１つは、τstartを含み、別の１つは、τendを含む。各四面体は、図３６に示されるように、ただ１つの時間線分を含む。ベクトルｅ1、ｅ2、ｅ3は、以下の戦略に従って、各四面体に関連付けられる。ベクトルｅ3は、時間線分であり、ベクトルｅ1、ｅ2は、ｅ3に付随するτstartおよび／またはτendの辺である。図３７は、各四面体のｅ1、ｅ2、ｅ3ベクトルを示している。
【０１６３】
（ｈ，ｔ）パラメータの計算は、直線デクセルを各四面体の各境界面分と交わらせることによって、また式（１）および式（２）を使用することによって実行される。（ｈ，ｔ）図のポリラインが、しかるべく生成される。
【０１６４】
上の説明は、方法の態様についての一般的な詳細、方法の背後にある一般的な直感（すなわち、（ｈ，ｔ）図）についての詳細、および（例えば、特に１つのデクセルと１つの三角柱との間の交わりを詳細に説明する）幾何学的な交わりを介してポリラインの端点を取得するために方法によって実行されるいくつかの計算の例を提供する。しかしながら、現実の機械加工シミュレーションは、膨大な数のデクセルおよび三角形を含み、計算時間を重大な問題にする。以下は、デクセルがどのように配置されるか、および（隣接三角形を掃引することによって引き起こされる）三角柱のトポロジ的な隣接性が、計算を加速するために、どのように使用されるかについての方法の例を説明する。
【０１６５】
この例では、（Ｌ1、Ｌ2、Ｌ3など）すべてのポリラインの端点を計算するステップＳ２０は、各メッシュＭについて、最初に、メッシュ（Ｍ）の可視部分（Ｍ+）を決定する（Ｓ２２と呼ばれる）サブステップをさらに含む。可視部分は、図１４ないし図１６を参照して説明されたように、切削工具の軌道に向かって方向付けられたメッシュの部分（例えば、面分からなる最小部分集合）である。Ｍ+は、いくつかのサブメッシュ（すなわち、各々が接続された面分からなる、分離されたサブメッシュ）を含むことに留意されたい。これは、任意の方法で実行される。次に、計算するステップＳ２０は、切削工具の軌道に従って、可視部分によって掃引された体積（Ｓ（Ｍ+））の（∂Ｓ（Ｍ+）と呼ばれる）境界を計算する（Ｓ２４と呼ばれる）サブステップを含む。これは、上で説明されたように、三角柱および／または四面体を使用して実行される。そして次に、計算するステップＳ２０は、（計算された）それぞれのポリラインの各端点について、Ｓ２８２と呼ばれる上で言及された決定するサブステップと、Ｓ２８４と呼ばれる上で言及された計算するサブステップとを反復する、（Ｓ２８と呼ばれる）反復サブステップを含む。境界面分を決定するサブステップＳ２８２は、可視部分によって掃引された体積（Ｓ（Ｍ+））の計算された境界∂Ｓ（Ｍ+）のそれぞれの境界面分を識別することから成る。実際に、構成によって、（ｈ，ｔ）図内のポリラインの端点は、デクセル直線と、メッシュ面分によって掃引された体積の境界面分、任意の境界面分ではなく、境界∂Ｓ（Ｍ+）を形成するものとの間の交わりに対応する。したがって、例の方法は、問題の幾何学的な特性を巧みに使用して、効率を向上させる。
【０１６６】
例の計算するステップＳ２０は、（明らかに）各メッシュＭについて、可視部分の面分によって掃引された体積に関する隣接性情報を決定するサブステップＳ２６をさらに含む。この情報は、面分によって掃引されたどの体積（例えば、三角柱および／または四面体）が隣接するかを示す任意の種類の情報である。これは、メッシュのトポロジに基づいて、メッシュ内の面分の隣接性および／または接続性情報に基づいて、単純な方法で実行される。このトポロジ情報は、それにもかかわらず、大きなスピード効率を可能にする。
【０１６７】
実際に、各それぞれのポリラインについて、次に、計算するステップＳ２０は、計算された境界∂Ｓ（Ｍ+）の「第１の」（または「入口」）面分と、計算された境界∂Ｓ（Ｍ+）の「第２の」（または「出口」）面分とを、異なる方法で決定するサブステップＳ２８２を含む。それぞれのポリラインの端は、一般に、定義によって、２つの３Ｄ点（すなわち、同じデクセル直線と計算された境界∂Ｓ（Ｍ+）の２つの要素との間の交わりにおけるそれら）に対応する。さて、例において実施される反復するサブステップＳ２８において、方法は、そのような境界面分を対で（すなわち、デクセル直線が掃引体積に、例えば、入る「第１の面分」と、デクセル直線が掃引体積から、例えば、出る「第２の面分」とを）考える。順序付け（「第１」と「第２」、「入る」と「出る」）は、純粋に恣意的であり、実施に依存する。
【０１６８】
問題なのは、そのようなすべての面分を力ずくで識別することの代わりに、方法が、第１の面分を決定する／見つけるたびに、それに関連付けられた面分（すなわち、「第２の面分」）を見つけるために、いわゆる「トポロジ的な伝搬」を実施することである。具体的には、ポリラインの端点に関連付けられた体積Ｓ（τ）の境界面分を決定するサブステップＳ２８２は、幾何学的な計算（したがって、図３１ないし図３７を参照して先に説明された第１の計算ステップなど、通常の３Ｄの交わりおよび相対的に重い計算）によって、デクセルの直線によって交わられる計算された境界∂Ｓ（Ｍ+）の第１の面分を決定することからなる。しかし、反復するサブステップＳ２８の間の交替では、同じポリラインの他方の端点に関連付けられた体積Ｓ（τ）の境界面分を決定するサブステップＳ２８２は、隣接性情報に基づいた（したがって、相対的に非常に高速な方法での）トポロジ的な伝搬によって、デクセルの直線によって交わられる計算された境界∂Ｓ（Ｍ+）の第２の面分（言い換えると、デクセルの直線は、点の２以上の対において、したがって、おそらくは２以上のそのような対またはそのインスタンスにおいて、境界∂Ｓ（Ｍ+）と交わるので、対のうちの第１の面分に関連付けられた面分）を決定することからなる。
【０１６９】
このトポロジ的な伝搬の特徴が、今からさらに詳述される。
【０１７０】
デクセル−三角形の交わりを計算するステップは、例では、以下のように実行される。Ｍを、初期メッシュとし、ＰstartおよびＰendを、それぞれ、基本軌道の始点および終点とする。Ｍ+を、基本軌道に向かって方向付けられたＭの部分とし、Ｅ+を、Ｍ+の境界とする。一般性を失うことなく、Ｍ+は接続された集合であると仮定する。本質的に、Ｅ+は、３次元の閉じられたポリラインである。図３８は、状況を例示している。
【０１７１】
今から、方向Ｖ＝Ｐend−Ｐstartに沿ったＭ+の掃引体積Ｓ（Ｍ+）について考察する。Ｓ（Ｍ+）の境界は、∂Ｓ（Ｍ+）と呼ばれる。実際に、Ｓ（Ｍ+）は、隣接する三角柱から作成され、以下の特性を特徴とする。  
●  各三角柱ｐiは、Ｍ+の三角形τiの押し出しである。  
●  Ｓ（Ｍ+）の境界∂Ｓ（Ｍ+）は、
□  Ｅ+の辺から押し出された平行四辺形
□  初期位置ＰstartにおけるＭ+の三角形
□  終了位置ＰendにおけるＭ+の三角形
を含む。  
●  ２つの隣接する三角柱ｐiおよびｐjによって共有される平行四辺形は、Ｍ+の三角形τiおよびτjによって共有される辺の押し出しである。
【０１７２】
これらの隣接性特性は、適切なトポロジデータ構造を通してキャプチャされる。それらは、伝搬アルゴリズムによって集中的に使用される。第１のステップは、Ｄと∂Ｓ（Ｍ+）との間の交点を計算することである。交わりが発生する面分ｆ0∈∂Ｓ（Ｍ+）が、トポロジ的な伝搬を開始する。次に、Ｄと交わらされるＳ（Ｍ+）の次の三角柱が、ｆ0の近傍を訪れることによって見つけられる。これは、図３９の図のラベルＡとラベルＢとの間で実行される。
【０１７３】
伝搬は、Ｓ（Ｍ+）の境界上にある点を計算したときに終了する。アルゴリズムは、Ｍ+が接続された集合ではない、一般的なケースにおけるように、ＤとＳ（Ｍ+）の境界面分との間の別の交点をサーチすることによって続行する。この伝搬方法によれば、交点から計算されるｈ値は、まったく自然にソートされており、そのことが、効率を向上されることに留意されたい。（すなわち、ｈ値に対していかなるソートも行わずに）この特性は、（ｈ，ｔ）図を構築するために使用される。
【０１７４】
以下から、トポロジ的な伝搬の中核が、説明される。それは、図４０の図のラベルＡとラベルＢとの間で行われる。主として、面分ｆ0に境界付けする、または面分ｆ0を生み出す、境界付け辺ｌ0が識別され、ｌ0またはｆ0に関連する適切な三角形τ∈Ｍ+も識別される。次の三角柱は、三角形τによって生み出されたものである。プロセスは、図４０の図において説明されるように、面分ｆ0の自然な平行四辺形対三角形に依存する。
【０１７５】
アルゴリズムが、図４１に示される状況において例示される。
１．Ｄと∂Ｓ（Ｍ+）との間の交点が、面分ｆ0において発生する。
２．面分ｆ0は平行四辺形であるので、境界面分ｆ0を生み出した境界辺ｌ0∈Ｅ+を取得する。
３．ｌ0によって境界付けされる一意的な三角形τ1を取得する。
４．Ｄとτ1の押し出しｐ1の面分との間の他の交点を計算する。
５．Ｄと交わるｐ1の面分ｆ1を開始する辺ｌ1を取得する。
６．τ1とｌ1を共有する三角形τ2を取得する。
７．Ｄとτ2の押し出しｐ2の面分との間の他の交点を計算する。
８．Ｄと交わるｐ2の面分ｆ2を開始する辺ｌ2を取得する。
９．τ2とｌ2を共有する三角形τ3を取得する。
１０．Ｄとτ3の押し出しｐ3の面分との間の他の交点を計算する。
１１．Ｄと交わるｐ3の面分ｆ3を開始する辺ｌ3を取得する。
１２．辺ｌ3はＭ+の境界辺であり、そのため、ｆ3はＳ（Ｍ+）の境界面分であり、デクセルＤは局所的にＳ（Ｍ+）から出るので、伝搬は終了する。
【０１７６】
アルゴリズムが、別の状況において例示される。図４２の左図は、デクセルＤと交わる面分ｆ0が三角形である状況を示している。図４２の右図は、Ｖ＝Ｐend−Ｐstartによって定義される視点から見られるＳ（Ｍ+）を示している。この右図において、各三角形は、ビュー平面と直交する三角柱の底面である。  
１．Ｄと∂Ｓ（Ｍ+）との間の交点が、面分ｆ0において発生する。  
２．面分ｆ0は三角形であり、辺ｌ0はＤと交わる平行四辺形を生成するものである。Ｄとこの平行四辺形との間の交点を計算する。  
３．ｆ0とｌ0を共有する一意的な三角形τ1を取得する。  
４．Ｄとτ1の押し出しｐ1の面分との間の他の交点を計算する。  
５．Ｄと交わるｐ1の面分ｆ1を開始する辺ｌ1を取得する。  
６．τ1とｌ1を共有する三角形τ2を取得する。  
７．Ｄとτ2の押し出しｐ2の面分との間の他の交点を計算する。
【０１７７】
Ｄと交わるｐ2の面分ｆ2はＳ（Ｍ+）の境界面分であり、そのため、デクセルＤは局所的にＳ（Ｍ+）から出るので、伝搬は終了する。
【０１７８】
ここで、さらなる改良として、第１の面分を決定するサブステップＳ２８２は、デクセルの集合にわたって、ラスタ化を実施する。言い換えると、第１の面分を決定するサブステップＳ２８２は、２Ｄグリッドの要素と見なされるデクセルにわたる、境界∂Ｓ（Ｍ+）のすべての要素のラスタ化によって提供される。デクセルは、２Ｄグリッドの要素と見なされる（グリッドに直交する平面において、デクセルはピクセルにたとえられる２Ｄ位置である）。
【０１７９】
各ｘ、ｙ、ｚ方向のデクセルは、ｎｍ個のデクセルからなる隣接する長方形グループに配置される。実施は、ｎ＝ｍ＝８が良好な性能を与えることを示す。各デクセルグループは、その境界付けボックスと関連付けられる。どのデクセルが与えられた三角柱と交わるかをサーチすることは、境界付けボックスが三角柱と出会わないデクセルのグループを最初に排除することによって、フィルタリングされる。
【０１８０】
上述の例は、明らかな変更も企図されるので、本発明の方法の範囲を限定しないことに留意されたい。特に、上述の説明は、（交わりが常に３Ｄ位置と見なされた、デクセル直線と境界面分との間の）「クリーン」な３Ｄ交わりを常に提示した。しかしながら、デクセル直線が境界面分と交わって、（点ではなく）交わり線分／直線を形成する場合、デクセルが１つの境界面分と交わらず、いくつかの境界面分とそれらの間の境界において（２つの面分の間の直線において、または例えば、３以上の面分の間の点においてさえも）交わる場合を含む、極端な場合に対する明らかな適合は、すべて、本発明の方法によって企図されることが理解されよう。方法は、例えば、いわゆる正確な述語に依存することによって、これらの退化ケースに対処し（非特許文献２０を参照）、それは、ロバスト性および効率を保証する。（例えば、特定の軌道のせいで）同じ境界面分と複数回交わるデクセル直線の扱いなど、すべての特定の明らかな実施も、方法によって企図される。
【図１】
0006787661.tif 000027
【図２】
0006787661.tif 000028
【図３】
0006787661.tif 000029
【図４】
0006787661.tif 000030
【図５】
0006787661.tif 000031
【図６】
0006787661.tif 000032
【図７】
0006787661.tif 000033
【図８】
0006787661.tif 000034
【図９】
0006787661.tif 000035
【図１０】
0006787661.tif 000036
【図１１】
0006787661.tif 000037
【図１２】
0006787661.tif 000038
【図１３】
0006787661.tif 000039
【図１４】
0006787661.tif 000040
【図１５】
0006787661.tif 000041
【図１６】
0006787661.tif 000042
【図１７】
0006787661.tif 000043
【図１８】
0006787661.tif 000044
【図１９】
0006787661.tif 000045
【図２０】
0006787661.tif 000046
【図２１】
0006787661.tif 000047
【図２２】
0006787661.tif 000048
【図２３】
0006787661.tif 000049
【図２４】
0006787661.tif 000050
【図２５】
0006787661.tif 000051
【図２６】
0006787661.tif 000052
【図２７】
0006787661.tif 000053
【図２８】
0006787661.tif 000054
【図２９】
0006787661.tif 000055
【図３０】
0006787661.tif 000056
【図３１】
0006787661.tif 000057
【図３２】
0006787661.tif 000058
【図３３】
0006787661.tif 000059
【図３４】
0006787661.tif 000060
【図３５】
0006787661.tif 000061
【図３６】
0006787661.tif 000062
【図３７】
0006787661.tif 000063
【図３８】
0006787661.tif 000064
【図３９】
0006787661.tif 000065
【図４０】
0006787661.tif 000066
【図４１】
0006787661.tif 000067
【図４２】
0006787661.tif 000068