(57)【特許請求の範囲】
【請求項１】
切削部および非切削部を有する切削ツールによる工作物の機械加工をシミュレートするための、コンピュータ実施方法であって、
前記工作物および前記切削ツールの軌道を表すモデル化されたボリュームを提供するステップ（Ｓ１０）と、
前記切削ツールの衝突掃引を決定するステップ（Ｓ２０）であって、前記衝突掃引は、前記切削ツールが前記軌道をたどる場合に、前記切削ツールの非切削前部によって掃引される前記ボリュームを表し、前記非切削前部は、移動方向の前面における前記非切削部の外側境界である、ステップ（Ｓ２０）と、
前記決定ステップ（Ｓ２０）に従って前記工作物との衝突をテストするステップ（Ｓ３０）とを含むことを特徴とする方法。
【請求項２】
前記切削ツールの保護前部を決定するステップを含み、前記衝突掃引を決定するステップは、前記非切削部によって掃引される前記ボリュームおよび前記保護前部によって掃引される前記ボリュームを決定するステップを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記工作物はデクセルのセットによって表され、各デクセルは線と前記工作物との間の交差を表す少なくとも１つのセグメントのセットを含み、前記衝突をテストするステップは、それぞれのデクセルについて、
前記保護前部によって掃引される前記ボリュームと交差する前記それぞれのデクセルの前記セグメントを決定するステップと、
それに応じて前記それぞれのデクセルを更新するステップと、
更新された前記それぞれのデクセルの前記セグメントが前記非切削部によって掃引される前記ボリュームと交差するかどうかを評価するステップと
を含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記切削部は凸状であり、前記それぞれのデクセルの前記セグメントは順序付けられ、前記それぞれのデクセルを更新するステップは、
前記保護前部によって掃引される前記ボリュームと交差する最小順番の前記セグメントを短縮するステップと、
前記保護前部によって掃引される前記ボリュームと交差する最大順番の前記セグメントを短縮するステップと、
前記最小順番のセグメントと前記最大順番のセグメントとの間のすべてのセグメントを除去するステップと
を含むことを特徴とする請求項３に記載の方法。
【請求項５】
前記衝突掃引を決定するステップは、前記切削ツールが前記軌道をたどる場合、前記切削ツールの前記非切削前部によって掃引される前記ボリュームを決定するステップを含むことを特徴とする請求項１に記載の方法。
【請求項６】
請求項１から５のいずれか一項に記載の方法を実行するための命令が記録されているメモリと、
前記メモリに結合されたプロセッサと、
前記プロセッサに結合され、前記命令を実行するように好適な、少なくとも１つのグラフィカルユーザインターフェースと
を備えることを特徴とするＣＡＭシステム。
【請求項７】
前記プロセッサはＧＰＵ（グラフィック処理ユニット）であることを特徴とする請求項６に記載のシステム。
【請求項８】
請求項１から５のいずれか一項に記載の方法を実行するための命令を含むことを特徴とするコンピュータプログラム。
【請求項９】
請求項８に記載のコンピュータプログラムが記録されていることを特徴とするコンピュータ読み取り可能記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータプログラムおよびシステムの分野に関し、より詳細には、切削部および非切削部を有する切削ツールによる工作物の機械加工をシミュレートするための方法、システム、およびプログラムに関する。
【背景技術】
【０００２】
物体の設計、エンジニアリング、および製造に関する市場には、いくつかのシステムおよびプログラムが提供されている。ＣＡＤはコンピュータ支援設計の頭字語であり、例えば物体を設計するためのソフトウェアソリューションに関する。ＣＡＥはコンピュータ支援エンジニアリングの頭字語であり、例えば将来の製品の物理的挙動をシミュレートするためのソフトウェアソリューションに関する。ＣＡＭはコンピュータ支援製造の頭字語であり、例えば製造のプロセスおよび動作を定義するためのソフトウェアソリューションに関する。こうしたシステムにおいて、技法の効率に関しては、グラフィカルユーザインターフェース（ＧＵＩ）が重要な役割を果たす。これらの技法は、製品ライフサイクル管理（ＰＬＭ）システム内に埋め込むことが可能である。ＰＬＭは、拡張された企業の概念全体にわたって、企業が製品データを共有し、共通のプロセスを適用し、製品の出現から寿命の終了まで製品の開発に関する企業知識を活用するための一助となる、ビジネス戦略を指す。
【０００３】
Ｄａｓｓａｕｌｔ  Ｓｙｓｔｅｍｓによって（商標ＣＡＴＩＡ、ＥＮＯＶＩＡ、およびＤＥＬＭＩＡで）提供されるＰＬＭソリューションは、製品エンジニアリング知識を組織化するエンジニアリングハブ、製造エンジニアリング知識を管理する製造ハブ、ならびに、エンジニアリングハブおよび製造ハブの両方への企業の統合および接続を可能にする企業ハブを提供する。すべてが一緒になって、システムは、動的な知識ベースの製品創出および意思決定支援を可能にするように製品、プロセス、リソースをリンクし、最適化された製品の定義、製造準備、生産、およびサービスを推進するオープンオブジェクトモデルをもたらす。
【０００４】
これらのシステムのいくつかは、切削ツールによる工作物の機械加工のシミュレーションを可能にする。しかしながら、これらのシステムはしばしば不十分なシミュレーションの原因となる。
【０００５】
こうしたシステムの例が、論文（例えば、非特許文献１および非特許文献２を参照）に記載されている。
【０００６】
いくつかのシステムは、デクセルのセットを用いたモデル化されたボリュームの表現を可能にする。いくつかの文書では、機械加工シミュレーションまたは対話型彫刻に関してデクセル表現を使用することを特に提案している。
【０００７】
こうした文書の例（例えば、非特許文献３、非特許文献４、非特許文献５、非特許文献６、非特許文献７、非特許文献８、非特許文献９、特許文献１、および特許文献２を参照）がある。
【０００８】
ＧＰＧＰＵ（Ｇｅｎｅｒａｌ−Ｐｕｒｐｏｓｅ  ｃｏｍｐｕｔｉｎｇ  ｏｎ  Ｇｒａｐｈｉｃｓ  Ｐｒｏｃｅｓｓｉｎｇ  Ｕｎｉｔｓ）は、従来は中央処理ユニット（ＣＰＵ）によって処理されるアプリケーション内の計算を実行するために、通常はコンピュータグラフィック専用の計算を処理するグラフィック処理ユニット（ＧＰＵ）を使用する技法である。いくつかの論文では、デクセル表現に関して現在のグラフィック処理ユニット（ＧＰＵ）の計算能力を使用することについて考察している。これらの論文は、特定のメモリモデルに関連付けられたＬＤＮＩ（Ｌａｙｅｒｅｄ  Ｄｅｐｔｈ−Ｎｏｒｍａｌ  Ｉｍａｇｅｓ）アルゴリズムを使用している。
【０００９】
こうした論文の例（例えば、非特許文献１０および非特許文献１１を参照）がある。
【００１０】
これに関連して、切削部および非切削部を有する切削ツールによる工作物の機械加工をシミュレートするための改良されたソリューションが、依然として求められている。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】米国特許第５７１０７０９号明細書
【特許文献２】米国特許第７７４７４１８号明細書
【非特許文献】
【００１２】
【非特許文献１】"Precise global collision detection in multi-axis NC-machining", Oleg Ilushina, Gershon Elberb, Dan Halperin, Ron Wein, Myung-Soo Kim, Computer-Aided Design 37 (2005) 909 - 920
【非特許文献２】"The sweep plane algorithm for global collision detection with workpiece geometry update for five-axis NC machining", T.D. Tang, Erik I., J. Bohez, Pisut Koomsap, Computer-Aided Design 39 (2007) 1012 - 1024
【非特許文献３】"A Virtual Sculpting System Based on Triple Dexel Models with Haptics", Xiaobo Peng and Weihan Zhang, Computer-Aided Design and Applications, 2009
【非特許文献４】"NC Milling Error Assessment and Tool Path Correction", Yunching Huang and James H. Oliver, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, 1994
【非特許文献５】"NC milling simulation and dimensional verification via dexel representation", Oliver, J.H, and Huang, Y., US Patent 5,710,709 - 1998
【非特許文献６】"Online Sculpting and Visualization of Multi-Dexel Volumes", Heinrich Muller, Tobias Surmann, Marc Stautner, Frank Albersmann, Klaus Weinert, SM '03 Proceedings of the eighth ACM symposium on Solid modeling and applications
【非特許文献７】"Virtual prototyping and manufacturing planning by using tri-dexel models and haptic force feedback", Yongfu Ren, Susana K. Lai-Yuen and Yuan-Shin Lee, Virtual and Physical Prototyping, 2006
【非特許文献８】"Simulation of NC machining based on the dexel model: A critical analysis", Sabine Stiffer, The International Journal of Advanced Manufacturing Technology, 1995
【非特許文献９】"Real time simulation and visualization of NC milling processes for inhomogeneous materials on low-end graphics hardware", Konig, A.N. and Groller, E., Computer Graphics International, 1998. Proceedings
【非特許文献１０】"GPGPU-based Material Removal Simulation and Cutting Force Estimation", B. Tukora and T. Szalay, CCP: 94: Proceedings Of The Seventh International Conference On Engineering Computational Technology
【非特許文献１１】"Layered Depth-Normal Images: a Sparse Implicit Representation of Solid Models", Charlie C. L. Wang and Yong Chen, Proceedings of ASME international design engineering technical conferences. Brooklyn (NY)
【発明の概要】
【発明が解決しようとする課題】
【００１３】
したがって、一態様によれば、切削部および非切削部を有する切削ツールによる工作物の機械加工をシミュレートするための、コンピュータ実施方法が提供される。この方法は、工作物および切削ツールの軌道を表すモデル化されたボリュームを提供することを含む。この方法は、切削ツールの衝突掃引を決定することも含む。衝突掃引とは、切削ツールが軌道をたどる場合に、切削ツールの非切削前部によって掃引されるボリュームを表す。この方法は、決定ステップに従って工作物との衝突をテストすることも含む。
【課題を解決するための手段】
【００１４】
この方法は、以下のうちの１つまたは複数を含むことができる。
【００１５】
−  この方法は、切削ツールの保護前部（ｐｒｏｔｅｃｔｉｖｅ  ｆｒｏｎｔ）を決定することを含み、衝突掃引を決定することは、非切削部によって掃引されるボリュームおよび保護前部によって掃引されるボリュームを決定することを含む。
【００１６】
−  工作物はデクセルのセットによって表され、各デクセルは線と工作物との間の交差を表す少なくとも１つのセグメントのセットを含み、衝突をテストすることは、それぞれのデクセルについて、保護前部によって掃引されるボリュームと交差するそれぞれのデクセルのセグメントを決定すること、それに応じてそれぞれのデクセルを更新すること、および、更新されたそれぞれのデクセルのセグメントが非切削部によって掃引されるボリュームと交差するかどうかを評価することを含む。
【００１７】
−  切削部は凸状であり、それぞれのデクセルのセグメントは順序付けられ、それぞれのデクセルを更新することは、保護前部によって掃引されるボリュームと交差する最小順番のセグメントを短縮すること、保護前部によって掃引されるボリュームと交差する最大順番のセグメントを短縮すること、および、最小順番のセグメントと最大順番のセグメントとの間のすべてのセグメントを除去することを含む。
【００１８】
−  衝突掃引を決定することは、切削ツールが軌道をたどる場合、切削ツールの非切削前部によって掃引されるボリュームを決定することを含む。
【００１９】
ＣＡＭシステムは、上記方法を実行するための命令が記録されているメモリと、メモリに結合されたプロセッサと、プロセッサに結合され、命令を実行するように好適な、少なくとも１つのグラフィカルユーザインターフェースとを備えることが、さらに提案される。
【００２０】
プロセッサは、ＧＰＵ（グラフィック処理ユニット）であってよい。
【００２１】
上記方法を実行するための命令を含むコンピュータプログラムが、さらに提案される。
【００２２】
上記コンピュータプログラムが記録されているコンピュータ読み取り可能記憶媒体が、さらに提案される。
【図面の簡単な説明】
【００２３】
次に、本発明の実施形態について、非限定的な例を用いて添付の図面を参照しながら説明する。
【００２４】
【図１】本発明の方法の例を示す流れ図である。
【図２】本発明のグラフィカルユーザインターフェースの例を示す図である。
【図３】本発明のクライアントコンピュータシステムの例を示す図である。
【図４】本発明の方法の例を示す図である。
【図５】本発明の方法の例を示す図である。
【図６】本発明の方法の例を示す図である。
【図７】本発明の方法の例を示す図である。
【図８】本発明の方法の例を示す図である。
【図９】本発明の方法の例を示す図である。
【図１０】本発明の方法の例を示す図である。
【図１１】本発明の方法の例を示す図である。
【図１２】本発明の方法の例を示す図である。
【図１３】本発明の方法の例を示す図である。
【図１４】本発明の方法の例を示す図である。
【図１５】本発明の方法の例を示す図である。
【図１６】本発明の方法の例を示す図である。
【図１７】本発明の方法の例を示す図である。
【図１８】本発明の方法の例を示す図である。
【図１９】本発明の方法の例を示す図である。
【図２０】本発明の方法の例を示す図である。
【図２１】本発明の方法の例を示す図である。
【発明を実施するための形態】
【００２５】
図１は、切削部および非切削部を有する切削ツールによる工作物の機械加工をシミュレートするための、コンピュータ実施方法の例の流れ図を示す。この方法は、工作物および切削ツールの軌道を表すモデル化されたボリュームを提供すること（Ｓ１０）を含む。この方法は、切削ツールの衝突掃引を決定すること（Ｓ２０）も含む。衝突掃引とは、切削ツールが軌道をたどる場合に、切削ツールの非切削前部によって掃引されるボリュームを表す。この方法は、決定することに従って工作物との衝突をテストすること（Ｓ３０）をさらに含む。こうした方法によって、切削ツールによる工作物の機械加工のシミュレーションが向上する。
【００２６】
この方法は、製造物体を表すＣＡＤモデル化物体を設計するプロセスを含むことができる。製造物体は、任意の物理的製品とすることが可能であり、工作物上で実行される機械加工プロセスに従って製造することが可能である。例えば製造物体は、切削ツールによりストックを機械加工することによって取得可能である。工作物は、機械加工中静止しているようなストックからなる。この方法は、こうした機械加工をシミュレートする。
【００２７】
「ＣＡＤモデル化物体を設計すること」は、モデル化された物体を精密に作り上げるプロセスの少なくとも一部である、任意のアクションまたは一連のアクションを指定する。例えばこの方法は、工作物を表すモデル化されたボリュームをストックとして提供すること、および、モデル化されたボリュームの切削をシミュレートすること（したがってストックの切削をシミュレートすること）によって工作物の機械加工をシミュレートすることを、含むことができる。モデル化されたボリュームは、工作物によって占有される３Ｄ空間を定義する。したがって、モデル化されたボリュームはモデル化された立体である。この方法は、切削部および非切削部を有する切削ツールによる工作物の機械加工のシミュレーションを向上させるものであるため、この方法は、製造物体を表すＣＡＤモデル化物体の設計も向上させる。
【００２８】
モデル化された物体とは、コンピュータシステムのメモリ内に格納されたデータによって定義される任意の物体である。拡大解釈すれば、「モデル化された物体」という表現は、データ自体を指定する。ＣＡＤモデル化物体とは、ＣＡＤシステムのメモリ内に格納されたデータによって定義される任意の物体である。システムのタイプにより、モデル化された物体は異なる種類のデータによって定義することができる。ＣＡＤシステムとは、ＣＡＴＩＡなどの、モデル化された物体のグラフィック表現に基づいてモデル化された物体を設計するために少なくとも好適な、任意のシステムである。したがって、ＣＡＤモデル化物体を定義するデータは、モデル化された物体の表現を可能にするデータ（例えば、例えば空間内の相対的位置を含む、幾何学データ）を含む。
【００２９】
この方法は、方法の実行後、方法によってシミュレートされた機械加工プロセスに従って製造物体を生産することを含むことが可能な、製造プロセスに含まれることが可能である。言い換えれば、テスト（Ｓ３０）の後、例えば、テスト（Ｓ３０）によって衝突がない旨の結果が引き出された場合、方法は、軌道に従い切削ツールによって（モデル化された物体によって表される）工作物を実際に切削することを含むことができる。製造物体は、部品または部品のアセンブリなどの製品とすることができる。この方法はモデル化された物体の設計を向上させるものであるため、この方法は、製品の製造を向上させ、製造プロセスの生産性を向上させるものでもある。この方法は、ＤＥＬＭＩＡなどのＣＡＭシステムを使用して実施することが可能である。ＣＡＭシステムとは、製造のプロセスおよび動作を定義、シミュレート、および制御するために少なくとも好適な、任意のシステムである。
【００３０】
この方法はコンピュータ実施される。すなわち、この方法は、少なくとも１台のコンピュータ、または任意の同様のシステム上で実行される。特に言及されていない限り、方法のすべてのステップは、コンピュータによって、すなわちユーザの介入なしに実行される。例えば、決定ステップ（Ｓ２０）およびテストステップ（Ｓ３０）は単独のコンピュータによって実施することができ、提供ステップ（Ｓ１０）は単独のコンピュータによって、またはユーザ対話を通じて実施することができる。これによって方法は、機械加工の自動テストが可能となる。
【００３１】
この方法のコンピュータ実施の典型的な例は、この目的に好適なシステムによって方法を実行することである。システムは、方法を実行するための命令が記録されたメモリを備えることができる。言い換えれば、ソフトウェアは即時使用のためにメモリ上に既に準備されている。したがってシステムは、任意の他のソフトウェアをインストールせずに、方法を実行するために好適である。こうしたシステムは、命令を実行するためにメモリに結合された少なくとも１つのプロセッサを備えることも可能である。言い換えればシステムは、プロセッサに結合されたメモリ上に符号化された命令を備え、この命令が、方法を実行するための手段を提供する。こうしたシステムは、モデル化されたボリュームを設計するための効率的なツールである。
【００３２】
こうしたシステムは、ＣＡＤまたはＣＡＭシステムとすることができる。システムは、ＣＡＥシステムとすることも可能であり、モデル化された物体はＣＡＥモデル化物体および／またはＣＡＭモデル化物体とすることも可能である。実際には、モデル化された物体がこれらのシステムの任意の組み合わせに対応するデータによって定義可能であるため、ＣＡＤ、ＣＡＥ、およびＣＡＭシステムは互いに排他的ではない。
【００３３】
システムは、例えばユーザによって命令の実行を開始するための少なくとも１つのグラフィカルユーザインターフェース（ＧＵＩ）を備えることができる。特に、ＧＵＩは、モデル化されたボリュームを設計すること、および／もしくはスクラッチからの切削ツールの軌道を定義することによって、ならびに／または、モデル化されたボリュームおよび／もしくは切削ツールの軌道を、システムのメモリから、または例えばネットワークサービスによってシステムに結合されているがシステムの外部にあるメモリから取り出すことによって、ユーザが提供ステップ（Ｓ１０）を開始できるようにすることができる。ＧＵＩはＧＰＵを含むことができる。このような場合、プロセッサはＧＰＵとすることができる。言い換えれば、少なくともこの方法のステップ、特に決定ステップ（Ｓ２０）および／またはテストステップ（Ｓ３０）を実行するプロセッサは、ＧＰＵとすることができる。こうしたシステムは、ユーザによってモデル化されたボリュームを設計するための効率的なツールである。これは、モデル化されたボリュームがデクセルのセットとして提供される場合に、特に有利である。デクセルベースのアルゴリズムは、超並列ハードウェアに好適であるため、最新のグラフィック処理ユニット（ＧＰＵ）の計算機能の使用を考慮するのは当然である。
【００３４】
モデル化されたボリュームは３Ｄ（すなわち３次元）とすることができる。これは、モデル化されたボリュームが、その３Ｄ表現を可能にするデータによって定義されることを意味する。３Ｄ表現は、すべての角度から表されたボリュームを見ることができるようにする。例えばモデル化されたボリュームは、３Ｄで表された場合、その任意の軸を中心に、または表現が表示される画面内の任意の軸を中心に、処理および回転することができる。これは特に、３Ｄモデル化されていない２Ｄアイコンを排除する。３Ｄ表現の表示は、設計を容易にする（すなわち、設計者が統計的に自分のタスクを実施する速度を上げる）。製品の設計は製造プロセスの一部であるため、これによって業界における製造プロセスの速度が上昇する。
【００３５】
図２は、典型的なＣＡＤシステムのＧＵＩの例を示す。
【００３６】
ＧＵＩ２１００は、標準メニューバー２１１０、２１２０、ならびに下部およびサイドのツールバー２１４０、２１５０を有する、典型的なＣＡＤ様インターフェースとすることができる。こうしたメニューバーおよびツールバーは、ユーザ選択可能アイコンのセットを含み、各アイコンは、当分野で知られるような１つまたは複数の操作または機能に関連付けられている。これらのアイコンのうちのいくつかは、ＧＵＩ２１００内に表示された３Ｄモデル化された物体２０００上での編集および／または作業に適合した、ソフトウェアツールに関連付けられる。ソフトウェアツールはワークベンチにグループ分けすることができる。各ワークベンチはソフトウェアツールのサブセットを含む。特に、ワークベンチのうちの１つは、モデル化された製品２０００の幾何学的特徴を編集するのに好適な編集ワークベンチである。操作時に、設計者は例えば物体２０００の一部を事前に選択し、その後、操作（例えば彫刻操作、または寸法、色などを変更するような任意の他の操作）を開始するか、または適切なアイコンを選択することによって幾何学的制約を編集することができる。例えば、典型的なＣＡＤ操作は、画面上に表示された３Ｄモデル化物体のパンチングまたはフォールディングのモデル化である。
【００３７】
ＧＵＩは、例えば、表示された製品２０００に関するデータ２５００を表示することができる。図２の例では、「特徴ツリー」として表示されたデータ２５００およびそれらの３Ｄモデル化された物体２０００は、ブレーキのキャリパおよびディスクを含むブレーキアセンブリに関連する。ＧＵＩは、例えば、物体の３Ｄ配向を容易にするため、編集された製品の動作のシミュレーションをトリガするため、または表示された製品２０００の様々な属性をレンダリングするために、様々なタイプのグラフィックツール２１３０、２０７０、２０８０をさらに示すことができる。カーソル２０６０は、ユーザがグラフィックツールと対話できるようにするために、触覚デバイスによって制御可能である。
【００３８】
図３は、例えばユーザのワークステーションなどのクライアントコンピュータシステムとして、システムのアーキテクチャの例を示す。
【００３９】
クライアントコンピュータは、内部通信ＢＵＳ１０００に接続された中央処理ユニット（ＣＰＵ）１０１０と、同じくＢＵＳに接続されたランダムアクセスメモリ（ＲＡＭ）１０７０とを備える。クライアントコンピュータには、ＢＵＳに接続されたビデオランダムアクセスメモリ１１００に関連付けられたグラフィクス処理ユニット（ＧＰＵ）１１１０がさらに提供される。ビデオＲＡＭ１１００は、当分野ではフレームバッファとも呼ばれる。大容量記憶デバイスコントローラ１０２０は、ハードドライブ１０３０などの大容量メモリデバイスへのアクセスを管理する。コンピュータプログラムの命令およびデータを有形に具体化するために好適な大容量メモリデバイスは、例えば、ＥＰＲＯＭ、ＥＥＰＲＯＭ、およびフラッシュメモリデバイスなどの半導体メモリデバイスと、内部ハードディスクおよび取り外し可能ディスクなどの磁気ディスクと、光磁気ディスクと、ＣＤ−ＲＯＭディスク１０４０とを含む、すべての形の不揮発性メモリを含む。前述のいずれかは、特別に設計されたＡＳＩＣ（特定用途向け集積回路）によって補助されるか、またはこれに組み込まれることが可能である。ネットワークアダプタ１０５０は、ネットワーク１０６０へのアクセスを管理する。クライアントコンピュータは、カーソル制御デバイス、キーボードなどの、触覚デバイス１０９０を含むこともできる。カーソル制御デバイスは、図２を参照しながら述べたように、ユーザがカーソルをディスプレイ１０８０上の任意の所望な位置に選択的に配置できるようにするために、クライアントコンピュータ内で使用される。画面により、コンピュータモニタなど、表示を実施することができる任意のサポートを意味している。加えてカーソル制御デバイスは、ユーザが様々なコマンドを入力し、制御信号を入力できるようにするものである。カーソル制御デバイスは、システムに制御信号を入力するためのいくつかの信号生成デバイスを含む。典型的には、カーソル制御デバイスはマウスとすることが可能であり、マウスのボタンは信号を生成するために使用される。
【００４０】
システムに方法を実行させるために、コンピュータによる実行のための命令を含むコンピュータプログラムが提供され、命令はこの目的のための手段を含む。プログラムは、例えば、デジタル電子回路内、もしくはコンピュータハードウェア、ファームウェア、ソフトウェア内、またはそれらの組み合わせ内に実装可能である。本発明の装置は、プログラム可能プロセッサによる実行のためにマシン読み取り可能記憶デバイス内に有形に具体化された、コンピュータプログラム製品内に実装可能であり、本発明の方法ステップは、入力データに対する演算および出力の生成によって本発明の機能を実行するために命令のプログラムを実行する、プログラム可能プロセッサによって実施することができる。命令は、データ記憶システム、少なくとも１つの入力デバイス、および少なくとも１つの出力デバイスから、データおよび命令を受信するため、ならびにそれらへデータおよび命令を送信するために結合された、少なくとも１つのプログラム可能プロセッサを含むプログラム可能システム上で実行可能な、１つまたは複数のコンピュータプログラム内に有利に実装可能である。アプリケーションプログラムは、高水準手続き型プログラミング言語もしくはオブジェクト指向プログラミング言語で、または、所望であればアセンブリ言語もしくは機械言語で実装可能であり、いずれの場合も、言語はコンパイル済み言語または解釈済み言語とすることができる。プログラムは、完全インストールプログラムまたは更新プログラムとすることができる。後者の場合、プログラムは既存のＣＡＤシステムを、システムが方法の実行に好適な状態に更新する。
【００４１】
方法は、工作物および切削ツールの軌道を表すモデル化されたボリュームを提供すること（Ｓ１０）を含む。モデル化されたボリュームは、任意のボリュームモデリングを使用して提供可能である。例えば、モデル化されたボリュームは、代数的定式化として提供可能である。あるいは、モデル化されたボリュームは、Ｂ−Ｒｅｐ（境界表現、すなわちモデル化されたボリュームの境界面に関する定式化）として、または多面体として提供可能である。モデル化されたボリュームは、以下で論じるように、デクセルのセットとしても提供可能である。モデル化されたボリューム、例えば３Ｄの表現は、方法の間、常時ユーザに表示することも可能である。切削ツールの軌道は、工作物の機械加工時に切削ツールによって取られることになる位置の任意の順序付けされたセットである。切削ツールの表現、例えば３Ｄを、ユーザに表示することも可能である。軌道の提供は、ユーザによって、例えば工作物の切削をシミュレートするために表示されたモデル化されたボリューム方向に切削ツールを移動させるなど、例えば画面上の切削ツールの表現を処理するユーザによって実施することができる。この方法は、切削ツールの軌道に従ってモデル化されたボリュームを更新することができる。例えばこの方法は、モデル化されたボリューム上で切削を実行すること、ならびに、その一方でまたは事前に、例えばリアルタイムで、例えば衝突が検出された場合に切削を停止するように、決定（Ｓ２０）およびテスト（Ｓ３０）を実行することを、含むことができる。このような場合、方法は、衝突が検出された旨の情報をユーザに表示することを含むことができる。
【００４２】
方法は、切削ツールの衝突掃引を決定すること（Ｓ２０）も含むことができる。衝突掃引は、切削ツールが軌道をたどる場合に、切削ツールの非切削前部によって掃引されるボリュームを表すデータである。一般に、切削ツールは切削部および非切削部を有し、これらはそれぞれ「切削ボリューム」および「非切削ボリューム」と呼ばれることもある。切削部と非切削部との間の境界は可変である可能性があり、すなわち異なる境界が存在可能であるため、それにより、場合によっては切削ツールの切削部および非切削部からなる異なるペアを定義する。切削ツールは、フライス盤、ボール盤、さらにはナイフとすることができる。いずれの場合でも、切削ツールは、例えば作業者またはロボットによって切削ツールを例えば処理および移動させるための、非切削部（例えばハンドル）を有する。実際に、切削ツールは、切削部および非切削部の剛性アセンブリである。ツールの軌道は、例えばユーザによって定義される一連の位置である。非切削部は、材料を切削しない切削ツールの一部であるため、遭遇する任意の固体と衝突する。切削ツールが軌道をたどる場合、切削ツールの非切削前部は、軌道上の切削ツールの所与の位置での、切削ツールが軌道をたどる場合にそうした位置で固体に衝突することになる（切削ツールが軌道をたどり始める前に固体がそうした位置に配置されている場合）ような、切削ツールのポイントのサブセットである。非切削前部の正式な定式化は、後で提供される。非切削前部によって掃引されるボリュームは、（例えば、工作物の少なくとも一部がこうした掃引されるボリューム内にある場合）潜在的な衝突が存在するボリュームである。衝突掃引は、こうしたボリューム（場合によっては掃引されるボリュームそれ自体またはその近似）を表す任意のボリュームデータである。これによって方法は、軌道の機能において切削ツールのポイントの衝突位置を表す３Ｄ空間のボリュームを決定することができる。
【００４３】
この方法は、決定（Ｓ２０）ステップに従って（すなわち、決定された衝突掃引の機能において）、工作物との衝突をテストすること（Ｓ３０）をさらに含む。テストすること（Ｓ３０）は、衝突を検出した場合（潜在的な衝突の場合）に肯定的な結果を引き出すこと、またはその逆の場合に否定的な結果を引き出すことができる。例えば、テストすること（Ｓ３０）は、衝突掃引と工作物との間に交差が存在するかどうかを決定することを含むことができる。したがってこの方法は、衝突掃引（によって表されるボリューム）が工作物と交差するか否かを決定することができる。交差する場合、方法によって衝突が検出される。
【００４４】
この方法のコンテキストは、コンピュータ支援システムまたはコンピュータ支援製造システムを使用するリアルタイムの機械加工シミュレーションである。この方法は、切削部および非切削部を有する切削ツールによって工作物を機械加工する、信頼できるシミュレーションを提供する。実際に、この方法は、わずかな偽の否定的結果を伴い（すなわち、わずかな可能な衝突がテスト（Ｓ３０）によって見逃されて）、高速に衝突を検出する。これは衝突掃引を決定する（Ｓ２０）際に、切削ツールの軌道が考慮されるためである。
【００４５】
決定すること（Ｓ２０）は、軌道を基本ステップに区分することを含むことができる。このような場合、決定すること（Ｓ２０）およびテストすること（Ｓ３０）は、各基本ステップに対して実施することができる。これにより、衝突掃引が容易に決定されるように、高速テスト（Ｓ３０）が可能となる。また、これによって、テスト（Ｓ３０）の偽の肯定的な結果を有する機会も減少する。ツール軌道の基本ステップは、２つの連続する位置の間でのツールの動きとすることができる。ツール軌道の各基本ステップで、切削部によって保護された非切削可動部の表面によって掃引されるボリュームを、非切削部によって掃引されるボリュームから差し引くことができる。その結果が現行の工作物と交差していない場合、この基本的な動きではクラッシュ（すなわち衝突）が発生しない旨を決定することができる。このチェックの後、（基本的な動きに従ってモデル化されたボリュームの一部を切削することにより）現行の工作物を更新することができる。これにより、速度の向上および信頼性の向上の両方が得られる。実際に、この方法は、それぞれの基本軌道ステップを改善する（したがって良好な性能を可能にする）必要はなく、信頼性はいずれの数値精度値にも依存しない。性能および信頼性は、変位ベクトルの方向に依存しない。
【００４６】
この区分は、所定の時間ステップに依存することができる。例えばこの方法は、それぞれが所定の時間ステップ中のユーザによる切削ツールの表現の処理に対応する、基本ステップに、軌道を区分することが可能である。あるいはこの方法は、所定の長さの基本ステップに軌道を区分することが可能である。あるいはこの方法は、等しい長さの所定数の基本ステップに軌道を区分することが可能である。
【００４７】
あるいはこの方法は、それぞれが規則正しい軌道を定義する基本ステップに軌道を区分することが可能である。規則正しい軌道により、切削ツールの各所与のポイントについて、所与のポイントの一連の位置によって定義される曲線は（切削ツールが軌道をたどる場合）、尖点を有さない（すなわち特異点を有さない）。例えば基本ステップは、彫刻ツールのキネマティックの記述のための、線形、円形、らせん形の弧（すなわちコイル部分）または曲線とすることができる。こうした区分が、テストステップ（Ｓ３）での偽の肯定の回数を効率的に低減させる。
【００４８】
切削ツールは、切削と何らかの他の非切削との何らかの境界を伴う凸状の面とすることができる。これにより、テスト（Ｓ３０）のより信頼できる結果が保証される。
【００４９】
この方法は、工作物を更新する間の、ツールの切削部の動きとツールの非切削部の動きとを分離する。これは、方法の適用例を示す図４〜６を参照しながら例示される。
【００５０】
この例では、方法は、切削部４２および非切削部４４を備える切削ツール４０、ならびに工作物を表すモデル化されたボリューム４６を、ユーザに表示することを含む。図４では、モデル化されたボリューム４６は更新前の工作物を表す。図５〜６では、モデル化されたボリューム４６は更新後の工作物を表す。
【００５１】
切削部４２はツール４０の半球部分であり、非切削部４４はツール４０の円柱部分（例えばツール胴部）である。切削ステップ前の工作物は、図４の台形形状のボリューム４６である。
【００５２】
ツール４０が右上から左下へと降下している場合、図５に示されるように切削前部はツール胴部に先行するため、（実際の機械加工プロセスにおいて）衝突は発生しないことが観察できる。これに対して、左下から右上へと上昇すると、図６に示されるようにツール胴部が切削前部に先行するため、（実際の機械加工において）ツール胴部４４と工作物との間に衝突４８が生じる。
【００５３】
したがって方法は、この非対称的な挙動を予測するために設計され、図６の場合では衝突を効率的に検出するが、図５の場合では衝突を効率的に検出しない。さらにこのような場合、軌道は単一の基本ステップを含むことができる。したがって方法は、軌道全体に対してテスト（Ｓ３０）を高速に実行することができる。
【００５４】
次に、図７〜２１を参照しながら、この方法の例について論じる。これらの例は、図４〜６を参照しながら論じた例と組み合わせ可能である。
【００５５】
可動の切削ツール４０は、切削ボリューム４２および非切削ボリューム４４に分解される。切削ボリューム４２および非切削ボリューム４４によって共有される内部境界７２は、実際的な意義を有さず、材料の除去または衝突挙動に影響を与えないことに留意されたい。したがって、この境界７２表面は計算の便宜上選択され、任意に設定可能である。この例では、境界７２は便宜的にディスクとして選択される。
【００５６】
第１の例では、衝突掃引を決定することは、切削ツール４０が軌道をたどる場合、切削ツール４０の非切削前部によって掃引されるボリュームを決定することを含む。言い換えれば、この方法は、切削ツール４０が軌道をたどる場合、切削ツール４０の非切削前部によって掃引されるボリュームを実際に決定し、衝突掃引はこうして決定されたボリュームに等しいことが可能である。
【００５７】
この例では、ツール４０は、切削ボリューム４２および非切削ボリューム４４を含む剛性可動アセンブリである。Ｖを非切削ボリューム４４の値としてみる。本来の手法では、工作物と掃引されるボリュームＶとの交差を考慮することができる。軌道を、関数ｔ∈［０，１］→Ｔｒａｊ（ｔ）によって定義し、この式で、各ｔ∈［０，１］について、Ｔｒａｊ（ｔ）は等長変換であるとすると、掃引されるボリュームＶは、
【００５８】
【数１】
0006282798.tif 000002
【００５９】
である。
【００６０】
各ｔ∈［０，１］で、等長変換Ｔｒａｊ（ｔ）は回転Ｒｏｔ（ｔ）および変換Ｔｒａｎｓ（ｔ）によって定義され、これは、３次元空間のポイントｘが位置Ｔｒａｊ（ｔ）（ｘ）＝Ｒｏｔ（ｔ）ｘ＋Ｔｒａｎｓ（ｔ）で移動されることを意味する。
【００６１】
この方法は、本来の掃引されるボリュームの概念の代わりに、いわゆる前進する外側前部の合併を使用することによって、より高度な定義を考慮する。Ｓouterを、ツール参照で定義された、ツール４０の外側境界でもある切削ボリューム４２の境界とする。図７の例では、ツールは切削ボリューム４２および非切削ボリューム４４に分解される。図８は、対応するＳouterを実線（非破線）として示している。任意のポイントｘ∈Ｓouterで、図９に示されるように、外側法線ベクトルｎ（ｘ）が示される。
【００６２】
所与のｔ∈［０，１］について、Ｆｒｏｎｔ（ｔ）で示されるツール４０の非切削前部を、以下のように定義されるＳouterのサブセットとする。
【００６３】
【数２】
0006282798.tif 000003
【００６４】
上式で、＜ｕ，ｖ＞はベクトルｕとｖとの間のスカラ積を示し、Ｒｏｔ（ｔ）は軌道Ｔｒａｊ（ｔ）の回転構成要素である。言い換えれば、Ｆｒｏｎｔ（ｔ）はＳouterのポイントのセットであり、時間ｔでのその瞬間速度ベクトルは可動のツール４０の外部方向に配向される。
【００６５】
例えば、図１０に示されるように、ツール４０は、ポイントＰ1からポイントＰ2へと線セグメント１００に沿って移動可能である。したがって、すべてのｔについてＲｏｔ（ｔ）＝Ｉｄであるため、Ｔｒａｊ（ｔ）ｘ＝ｘ＋ｔ（Ｐ2−Ｐ1）である。そこで、すべてのｔについて、
【００６６】
【数３】
0006282798.tif 000004
【００６７】
である。したがってｔ＝０では、Ｆｒｏｎｔ（ｔ）は図１０で太線によって示される垂直セグメント１０２である。
【００６８】
Ｐ2からＰ1への逆軌道１１０は、図１１で逆Ｌ字形太線１１２によって示されるような、異なるＦｒｏｎｔ（ｔ＝０）を誘導する。
【００６９】
この方法は、「衝突掃引」をＦｒｏｎｔ（ｔ）によって掃引されるボリュームとして、以下のように決定すること（Ｓ２０）ができる。
【００７０】
【数４】
0006282798.tif 000005
【００７１】
この方法は、現行の工作物に照らして非切削ボリューム掃引をチェックすることとは対照的に、現行の工作物に照らして衝突掃引をチェックする。
【００７２】
図１２は、下降する軌道に従って計算された衝突掃引１２０を示す。明らかに、衝突掃引１２０およびモデル化されたボリューム４６は分離され、これは、ツール４０の非切削ボリュームが、軌道のこの部分の間に、モデル化されたボリューム４６にクラッシュしないことを意味する。
【００７３】
次に、図１３は、上昇する軌道に従った衝突掃引１２０を示す。Ｆｒｏｎｔ（ｔ＝０）の形状により、衝突掃引１２０は異なり、ボリューム４６と重複する。これは、ツール４０の非切削ボリューム４４が、軌道のこの部分の間に、モデル化されたボリューム４６に実際にクラッシュすることを意味する。
【００７４】
第２の例では、この方法は、切削ツールの保護前部を決定することを含む。切削ツールの保護前部は、切削ツールが軌道をたどる場合、軌道上の切削ツールの所与の位置での切削ツールのポイントのサブセットであり、切削ツールが軌道をたどる場合、切削ツールの他のポイントがそうした位置にある固体と衝突するのを防ぐ（切削ツールが軌道をたどり始める前に固体がそうした位置に配置されている場合）。保護前部の正式な定式化は、後で提供される。
【００７５】
衝突掃引を決定すること（Ｓ２０）は、このような場合、非切削部によって掃引されるボリュームおよび保護前部によって掃引されるボリュームを決定することを含むことができる。その後、この方法は、当該２つのボリューム間の相違を決定することができる。テストすること（Ｓ３０）は、当該ボリュームの相違がモデル化されたボリュームと交差するかどうかを評価することを含むことが可能であり、交差する場合は肯定結果を引き出し、交差しない場合は否定結果を引き出す。これにより、高速でロバストな決定（Ｓ２０）が可能である。
【００７６】
便宜上、例は２Ｄで示されている。しかしながら実際は、前述のように３次元である。図１４〜１５は、例の３Ｄ図を提供する。図１４は、非切削ボリューム４４を（長方形ではなく）円柱形として示している。図１５は、衝突掃引１２０が、傾斜軌道に沿って半円柱形フランクによって掃引されるボリュームであり、凸面体でないことを示している。
【００７７】
この第２の例ならびに第１の例では、方法の実装はマルチデクセルモデルとすることができる。言い換えれば、工作物は（それによってモデル化されたボリュームを表す）デクセルのセットによって表すことができる。言い換えれば、この例では、モデル化されたボリュームはデクセルのセットとして提供される。（デクセルのセットの）各デクセルは、少なくとも１つのセグメントのセットを備える。こうしたセグメントは、線と工作物との間の交差を表す。
【００７８】
工作物を表すためにデクセルのセットを使用することで、（少ないメモリスペースを使用する）軽量表現が可能となる。これにより、容易に処理可能な工作物の表現も可能となる。特に、デクセルのセットのデータ構造により、工作物がデクセルのセットによって表される場合、切削は特に効率的に実行することができる。実際に、設計動作は高反応性および高ロバストネスで実施することができる。特に、デクセルのセットに対する演算は、効率が増大するように、並列処理を介して線ごとに実施することができる。したがって、システムのプロセッサはＧＰＵとすることができることが効率的である。
【００７９】
「デクセル」という用語は、「深さ要素」のショートカットであるものと知られている（「ピクセル」という用語が「画像要素」のショートカットであるのと同様）。デクセルの概念は、数多くの研究論文で言及されている。この方法との関連において、デクセルは少なくとも１つのセグメントのセット、すなわち３Ｄポイントのペアを含む。ある例では、モデル化されたボリュームは、少なくとも２つのセグメントのセットを含む少なくとも１つのデクセルを含む（例えば、デクセルの初期セットおよび／またはデクセルの新規セットは少なくとも２つのセグメントを含む）。デクセルのセグメントは、いくつかある場合、順序付けする（このような場合、デクセルはリストである）か、または順序付けしないことが可能である。デクセルのセグメントは、線と工作物との間の交差を表す。言い換えれば、仮想線が工作物と交差するものと考えると、デクセルは所与の線から始まるセグメントのセットであり、交差の計算の結果から生じる。
【００８０】
デクセルのセットは、コンピュータ実施データとして提供されることに留意されたい。したがって、モデル化されたボリュームの任意の表現に関して上記および下記で提供される定義は、図のデータ構造ポイントからの影響を受ける。例えば、セグメントは３Ｄ位置のペア（例えば互いにリンクされた２つの３Ｄ位置）として提供可能である。３Ｄ位置は、それ自体、参照３Ｄフレームに関連付けられた３つの座標（例えば浮動小数点）のリストとして提供可能である。デクセルは、セグメントがセット構造において互いにリンクされていることを示唆する、セグメントのセットである。デクセルのセットのデクセルも、同様に互いにリンクされることが可能である。モデル化されたボリュームを、それら自体が少なくとも１つのセグメントのセットを有するデクセルのセットによって表すことにより、モデル化されたボリュームの高速テスト（Ｓ３０）ならびに高速の隠された更新が可能となる。
【００８１】
衝突をテストすること（Ｓ３０）は、それぞれのデクセルについて、保護前部によって掃引されるボリュームと交差するそれぞれのデクセルのセグメントを決定すること、それに応じて（すなわち、決定されたセグメントの機能において、すなわち決定されたデクセルを短縮および／または廃棄することによって）それぞれのデクセルを更新すること、ならびに、更新されたそれぞれのデクセルのセグメントが非切削部によって掃引されるボリュームと交差するかどうかを評価することを、含むことができる。その後、方法は、評価が肯定である場合はテストの肯定結果を、または評価が否定である場合は否定結果を、引き出すことができる。
【００８２】
この方法は、保護前部および非切削部を定義する（例えば、前述のように、保護前部は任意で定義可能であり、切削ツールを切削部と非切削部に分割することができる）ことを含むことができるため、結果として、保護前部によって掃引されるボリュームおよび非切削部によって掃引されるボリュームは凸状の面となる。当業者であれば、こうした分割を実行してどのように凸面部を取得するかについて理解されよう。このような場合、保護前部によって掃引されるボリュームと交差するそれぞれのデクセルのセグメントを決定すること、および、更新されたそれぞれのデクセルのセグメントが非切削部によって掃引されるボリュームと交差するかどうかを評価することが、特に高速に実行される。
【００８３】
実際に、それぞれのデクセルのセグメントは、典型的に順序付けすることができる（実際の順序は、デクセルを定義するデータ内に存在可能であるか、またはこうした順序を本来存在するままに取り出すことができる）。非切削部は、例えば、非切削部が凸状の面であり、基本ステップが単純変換である場合、凸面ボリュームを掃引することができる。加えて、保護前部も同様に凸面ボリュームを掃引することができる。例えば、切削部も同様に凸状の面とすることができる。軌道は、単純変換からなる基本ステップに分割することができる。それぞれのデクセルを更新することは、保護前部によって掃引されるボリュームと交差する最小順番のセグメント（例えば、それぞれのデクセルのセグメントの順序で進められる場合、保護前部によって掃引されるボリュームと交差する第１のセグメント）を短縮すること、保護前部によって掃引されるボリュームと交差する最大順番のセグメント（例えば、それぞれのデクセルのセグメントの順序で進められる場合、保護前部によって掃引されるボリュームと交差する最後のセグメント）を短縮すること、および、最小順番のセグメントと最大順番のセグメントとの間のすべてのセグメントを除去することを含む。
【００８４】
次に、この方法の第２の例について、図１６〜２１を参照しながら論じる。
【００８５】
デクセルの使用との関連において、処理ポイントの観点から、凸面衝突掃引を管理すること、または不可能な場合、２つの凸面セットの減算によって定義された固体を管理することが、より効率的である可能性がある。実際に、２つの凸面セットの相違のセットＳ、Ｓ＝Ｃ1−Ｃ2とセグメントとの交差は、以下のように実施することができる。
【００８６】
この方法は、Ｃ1およびＣ2を備えるセグメントをサポートする線Ｌと交差することが可能であり、これによって、２つの可能な空のセグメントＩ1＝Ｌ∩Ｃ1およびＩ2＝Ｌ∩Ｃ2が与えられる。Ｌ∩Ｓ＝Ｌ∩（Ｃ1−Ｃ2）＝（Ｌ∩Ｃ1）−（Ｌ∩Ｃ2）＝Ｉ1−Ｉ2であることが観察できる。もちろん、線Ｌによってサポートされるセグメントは、Ｌのパラメータ表示内の間隔として表すことができる。Ｓと共にＬによってサポートされるセグメントの交差は、２つの間隔の相違を伴う間隔の交差にまとめられ、後者は、最悪の場合、２つの間隔の合併である。
【００８７】
このため、以前に提示された第１の例は、特にデクセルモデルとの関連において、この方法をより実際的にするために再公式化することができる。凸面の非切削ボリュームＶについて考えてみる。発明者等は、Ｓouter内にないＶの境界をＳprotectと呼ぶ。言い換えれば、Ｓprotectは、ツールの他の切削ボリュームまたは非切削ボリュームと接触しているＶの面を含む。
【００８８】
ＮＣ機械加工シミュレーションなどの実際的な状況において、最も一般的なツールの形状は、Ｓprotectが１つまたは複数の平面を含むことを可能にする。しかしながら、切削ボリュームと非切削ボリュームとの間の内部分離に物理的な意義はなく、したがって、結果として生じる挙動にいかなる影響も無しに、平面としてしばしば選択される可能性があることに留意されたい。
【００８９】
図４〜１５の例の場合、Ｓprotectはディスクとすることができる。図１６〜１８に示されるように、Ｓprotectは切削ボリュームと非切削ボリュームとを分離する実線である。
【００９０】
この方法は、衝突掃引を、全凸面非切削ボリュームの掃引とＳprotectのサブセットの掃引との間の設定された理論上の相違として定義することができる。このサブセットは、外側法線ポイントが掃引方向にある、Ｓprotectのすべてのポイントを含む。一般的な非変換軌道の場合、Ｓprotectのある部分は、即時掃引速度方向に向かう外側法線ポイントを有し、ある部分は有さないことが可能である。この場合、Ｓprotectのサブセットのみを掃引することができる。変換掃引の場合、これは２つの凸面セットの減算であり、マルチデクセルモデルにおいて容易に管理可能である。
【００９１】
正式には、この方法は以下のように定義可能である。
【００９２】
【数５】
0006282798.tif 000006
【００９３】
したがって、衝突掃引の以前の定義に従い、以下の式が得られる。
【００９４】
【数６】
0006282798.tif 000007
【００９５】
したがって、マルチデクセルグリッド表現を使用する機械加工シミュレーションとの関連において、この方法は、以下の動作によって基本軌道中の衝突を容易にチェックすることができる。
【００９６】
各デクセルについて、この方法は、図１９に示されたように、非切削ボリューム１９０の掃引との交差によって与えられる、間隔Ａi（すなわち、この例のデクセルのサポート線上の間隔として格納されたデクセルのセグメント）を計算することができる。これらの間隔Ａiのすべてが現行の工作物との空の交差を有する場合、衝突が生じないことを保証することが可能であり、すなわち、テストすること（Ｓ３０）は否定結果を引き出すことができる。
【００９７】
さもなければ、この方法は、ｔ＝０からｔ＝１までｐｒｏｔｅｃｔＦｒｏｎｔによって掃引されるボリュームを計算することができる（軌道、または基本ステップが、０から１へ進むパラメータ化で定義される場合）。この場合、方法は、その外側法線が変位ベクトルを用いる正のドット積を有する、Ｓprotectの面２００を集めることができる。その後、この方法は、図２０に示されるように、これらの面２００によって掃引されるボリュームを計算することができる。この方法は、最終的に、図２０に示されるように、デクセルとこの掃引されるボリューム２０２との間の交差に等しい間隔Ｂiを計算することができる。この方法は、ブール１次元減算Ｃ1＝Ａi−Ｂiを計算することが可能であり、この結果として生じる間隔は、図２１に示されるように、デクセルと衝突掃引ボリューム１９０との間の交差を表す。これらのＣ1間隔が工作物層を格納するデクセル間隔との空でない交差を有する場合、そのデクセル上で衝突が生じることになるものと結論付けることができる。衝突深さも推測可能である。さもなければ、図２１に示されるように、そのデクセル上に衝突は発生しない。
【符号の説明】
【００９８】
４０  切削ツール
４２  切削ボリューム
４４、１９０  非切削ボリューム
４６、２０２  ボリューム
４８  衝突
７２  内部境界
１００  線セグメント
１０２  垂直セグメント
１１０  逆軌道
１１２  逆Ｌ字形太線
１２０  衝突掃引
２００  面
１０００  内部通信ＢＵＳ
１０１０  ＣＰＵ
１０２０  大容量記憶デバイスコントローラ
１０３０  ハードドライブ
１０４０  ＣＤＲＯＭ
１０５０  ネットワークアダプタ
１０６０  ネットワーク
１０７０  ＲＡＭ
１０８０  ディスプレイ
１０９０  触覚デバイス
１１００  ビデオＲＡＭ
１１１０  ＧＰＵ
２０００  物体
２０６０  カーソル
２０７０、２０８０、２１３０  グラフィックツール  
２１００  ＧＵＩ
２１１０、２１２０  標準メニューバー
２１４０、２１５０  ツールバー
【図１】
0006282798.tif 000008
【図２】
0006282798.tif 000009
【図３】
0006282798.tif 000010
【図４】
0006282798.tif 000011
【図５】
0006282798.tif 000012
【図６】
0006282798.tif 000013
【図７】
0006282798.tif 000014
【図８】
0006282798.tif 000015
【図９】
0006282798.tif 000016
【図１０】
0006282798.tif 000017
【図１１】
0006282798.tif 000018
【図１２】
0006282798.tif 000019
【図１３】
0006282798.tif 000020
【図１４】
0006282798.tif 000021
【図１５】
0006282798.tif 000022
【図１６】
0006282798.tif 000023
【図１７】
0006282798.tif 000024
【図１８】
0006282798.tif 000025
【図１９】
0006282798.tif 000026
【図２０】
0006282798.tif 000027
【図２１】
0006282798.tif 000028