(57)【要約】      （修正有）【課題】機械加工される部品の加工性を分析し、工程設計を行うためのコンピュータ実装システムおよびその方法を提供する。【解決手段】ウェブ上のシステムおよび方法は、加工設定のモデルと、任意の形状の設計された部品の情報とを用いて、２つの連続するステージからなる工程計画を作成する。第１のステージで、部品の形状を分析する。方向性を有する機械加工の工具から機械加工可能な最大容積を決定するクエリを、方向性を有する機械加工の工具の先端に配置された仮想カメラの視界から部品表面の可視性を判定するクエリに変える。第２のステージで、全ての工具の方向性に対する機械加工可能な最大容積の合計を集計する。加工性および工程計画にフィードバックを提供するために、原材料と所望の部品との間の差を全てカバーする機械加工可能な最大容積の組合せを評価する。【選択図】図２
2014115991.tif 000002
【特許請求の範囲】
【請求項１】
切削される容積を求めることにより機械加工される部品に関する工程計画を作成するためのコンピュータ実装方法であって、
複数の工具の方向性を含み、回転する刃先を縦方向に移動させるフライス加工の工具に関するパラメータを検索するステップと、
前記部品の表面を規定する部品のモデルにアクセスするステップと、
前記回転する刃先と前記部品の表面との間の衝突を避ける、前記工具に関する平行移動の最大設定を検索するステップであって、各平行移動には、前記工具の方向性、および前記平行移動により切削可能な容積が含まれる、ステップと、
前記最大設定内の前記平行移動の交点を計算し、前記交差する平行移動に関する前記切削される容積の和集合を算出するステップと、
前記和集合が前記部品の負の容積と実質的に等しいことを条件として、前記工具による機械加工の動作を含む工程計画を決定するステップと、を含む方法。
【請求項２】
前記工具により機械加工可能な、前記工具の表面の外側の前記平行移動の前記最大設定の最大空間を決定するステップと、
前記工具に関する機械加工可能な最大容積として、前記工具の前記平行移動の前記最大設定の交点を算出するステップと、
前記機械加工可能な最大容積の和集合が部品の負の容積と実質的に等しいかどうかに基づいて、前記部品の加工性を評価するステップと、をさらに含む請求項１に記載の方法。
【請求項３】
前記工具の起点からの前記部品の表面に対する工具の接近に垂直な前記部品の高さマップを計算するステップと、
工具の起点を中心とし、部品の表面から離れていく方向に向かって見る、前記工具の高さマップを計算するステップと、
前記工具を前記部品の表面上にスイーピングさせることにより作成される容積を含む、切削される各容積の高さマップを作成するステップと、
前記工具の前記高さマップ内の各点に関する、前記部品の表面と前記工具の交点の間で衝突が特定されると、部品の表面から離れていく方向に前記工具の貫通深さ分だけ、前記工具の前記平行移動を行うステップと、
前記工具の衝突しない平行移動の和集合が、前記部品の負の容積と実質的に等しいかどうかに基づいて、前記部品の  加工性を評価するステップと、をさらに含む請求項１に記載の方法。
【請求項４】
前記部品、前記工具および前記切削される容積のそれぞれの前記高さマップをＺバッファーとして形成するステップをさらに含む請求項３に記載の方法。
【請求項５】
前記工具Ｔの前記衝突しない平行移動を、機械加工可能な最大容積「Ｖｍａｘ」として式、
【数１】
2014115991.tif 000017
に従って決定するステップであって、
「δ（）」はミンコフシキー和であり、「Ｐａｃｃ」はアクセス可能な前記部品Ｐの境界であり、「Ｓ」は原材料に関するステージモデルであり、前記原材料から前記部品Ｐが前記工具Ｔにより機械加工される、ステップと、
６次元空間内の前記工具Ｔの前記衝突しない平行移動を同次商として式、
【数２】
2014115991.tif 000018
に従って決定するステップであって、「Ｐｃ」は、次元「ｉ」で部品Ｐとの衝突「ｃ」なしに工具Ｔに適用可能な前記平行移動の最大設定である、ステップと、のうちの少なくとも一方をさらに含む請求項３に記載の方法。
【請求項６】
畳み込み積分を通して機械加工される部品の加工性を分析するコンピュータ実装システムであって、
記憶装置であって
複数の工具の方向性を含み、縦方向に回転する刃先を移動させるフライス加工の工具に関するパラメータと、
前記部品の表面を規定する部品のモデルと、を含む記憶装置と、
プロセッサにより実行されるコードを格納するプロセッサおよびメモリであって
前記工具の方向性ごとに前記部品の機械加工可能な最大容積を決定するよう設定される工具評価モジュールであって、
前記回転する刃先と前記部品の表面との間の衝突を避ける、前記工具の平行移動の最大設定を計算するよう設定される平行移動モジュールと、
前記工具により機械加工可能な、前記部品の表面の外側の前記工具の前記平行移動の前記最大設定の最大空間を決定し、前記工具に関する機械加工可能な最大容積として、前記工具の前記平行移動の前記最大設定の交点を算出するよう設定される容積モジュールと、を含む工具評価モジュールと、
前記機械加工可能な最大容積の和集合が、部品の負の容積と実質的に等しいかどうかに基づいて、前記部品の加工性を評価するよう設定される加工性モジュールと、
前記部品が製造可能であることを条件として、前記工具による機械加工の動作を含む工程計画を決定するよう設定される工程計画モジュールと、をさらに含むプロセッサおよびメモリと、を含むシステム。
【請求項７】
前記工具Ｔの前記平行移動の前記最大設定が、同次商として式、
【数３】
2014115991.tif 000019
に従って決定され、「Ｐｃ」が部品Ｐのコンプリメントを示す、請求項６に記載のシステム。
【請求項８】
前記工具の平行移動の前記最大設定が、前記工具により各方向に到達可能な位置でのみ制限され、前記工具Ｔの前記到達可能な作業空間Ｒ内の前記工具により各方向に到達可能な前記位置だけが式、
【数４】
2014115991.tif 000020
に従って決定され、「Ｐｃ」が部品Ｐのコンプリメントを示す、請求項６に記載のシステム。
【請求項９】
前記工具Ｔに関する前記機械加工可能な最大容積「Ｖｍａｘ」が式、
【数５】
2014115991.tif 000021
に従って決定され、最大設定および「Ｓ」が原材料であり、前記原材料から前記部品が前記工具Ｔにより機械加工される、請求項６に記載のシステム。
【請求項１０】
前記工具に関する前記機械加工可能な最大容積のシーケンスに関して規定される工程計画の候補のリストを特定する特定モジュールと、
前記工具ごとの仕様書を含む工具のライブラリ内の工具のリストに対応する加工設定を作成し、使用可能な工具の能力をアップロードされた幾何モデルに接続させ、質的な工程計画を提供する計画モジュールと、のうちの少なくとも一方をさらに含む請求項６に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本出願は、一般にコンピュータ支援による工程計画に関し、具体的には、機械加工される部品の加工性を分析し、工程設計を行うためのコンピュータ実装システムおよびその方法に関する。
【背景技術】
【０００２】
原材料または材料（通常は金属）からの部品の機械加工とは、部品が意図される形状および大きさになるまで、原材料を少しずつ削っていく切削加工の一形態である。機械加工中の動作では、原材料に、主として旋盤加工、穴あけ加工、およびフライス加工を施して、所望の部品に加工する。旋盤加工では、静止している切削工具に対して原材料を回転させることによりその原材料を切削し、穴あけ加工では、原材料を静止状態で保持し、先端に刃先を有するドリルを回転させて軸方向に穴をあけ、フライス加工では、回転するドリルの側面および先端の全体に沿って刃先を有するドリルを回転させて原材料を切削することにより、原材料が削除されるよう要求する。穴あけ加工およびフライス加工では、両方とも、Ｚ方向で縦方向に沿って回転ドリルを平行移動させる。３次元の空間で加工を行うフライス加工でも、平面に沿ったＸＹ方向に回転ドリルを平行移動させる。その他の種類の機械加工動作および工具も存在する。一般に機械加工では、特定な公差内で原材料を切削して粗加工を行い、さらに、ならし加工、研磨加工、仕上げ加工、またはその他の加工を行って、最終形状に部品を仕上げる加工処理が必要となる。
【０００３】
製品ライフサイクル管理のその他の局面と同様に、機械加工でもコンピュータとの統合が進むことによりその恩恵を受けている。例えば、デジタル的に自動化されたフライス盤をプログラムして、コンピュータ数値制御（ＣＮＣ）による機械加工命令により、部品を原材料から加工することができる。一般に、これらの機械加工命令は、ユーザによる入力に基づいて、自動設計された後の処理確認と組み合わせて、コンピュータ支援加工（ＣＡＭ）のソフトウェアにより作成される。コンピュータ支援設計（ＣＡＤ）のプログラムから出力される、電子的に格納されたモデルを通して、デジタル的に部品を表現し、ＣＡＭソフトウェアが、機械加工の工具を含む加工設定のモデルと組み合わせて、この部品のデジタルモデルを用いて、一連の機械加工命令を作成する。
【０００４】
ＣＡＤ、ＣＡＭおよびそれに関連するデジタル加工ソフトウェアにより、設計および加工の一部が進歩できたにもかかわらず、従来の作業では、製品ライフサイクル管理と実際の現場での加工との間の効率的な統合をよりよく補助することを目指し、人間が作成した加工の工程計画の確認の補助にその焦点が主に当てられている。一般に、これらのソフトウェアにより仮想環境が提供され、この仮想環境では、加工処理のモデリング、計画、シミュレーションおよび分析を実行可能となり、これらの作業はアルゴリズムによりサポートされ、これらのアルゴリズムが経路計画、衝突判定、サイクル時間計算、レイアウトモデリングおよびリソース割り当てを実行し、かつ、単一動作から加工プログラム全体に渡る範囲のユーザによる入力を確認する。
【０００５】
しかし、例えば、ＣＮＣプログラムで表現可能な、機械加工命令のシーケンスを規定する加工の工程計画を同期させて原材料から部品を作成するという課題が残る。自動化しないで手作業でこの課題に取り組むことは、部品の形状の複雑さによっては、時間の浪費でありコストのかかる作業となる。さらに、工程計画ステージの大部分がこの作業に費やされる可能性があり、デジタル処理で加工する工具一式を用いて実行されることが確認される前に、十分な工程を決定するために常に人間が介入し、創造性および経験が必要とする。
【０００６】
逆に、一般的に複数の解決策があり、部品の幾何学的な複雑さが増すにつれ解空間が広がり、機械加工の工具のより大きなセットが使用可能になり、このためデジタル的に自動化した機械加工により機械部品を加工するための工程計画を決定するときに設定不良が同様な問題となる。さらに、機械の特定なパラメータ、設定時間および加工時間とそのコスト、設計の公差、レイアウト設計などに工程計画は左右される。解空間が扱いにくくなり、加工性の分析および工程計画の選択を誘導可能な処理主導によるフィードバックが少なくなる。任意の幾何学的な複雑さを有する部品に関する加工のための工程計画を作成するだけの従来の解決策では、これらの課題は解決できない。
【０００７】
例えば、ＡＳＭＥ  ２０１２  Ｉｎｔｅｒｎａｔｉｏｎａｌ  Ｄｅｓｉｇｎ  Ｅｎｇｉｎｅｅｒｉｎｇ  Ｔｅｃｈｎｉｃａｌ  Ｃｏｎｆｓ．＆Ｃｏｍｐｓ  ａｎｄ  Ｉｎｆｏｒｍａｔｉｏｎ  ｉｎ  Ｅｎｇｉｎｅｅｒｉｎｇ  Ｃｏｎｆｅｒｅｎｃｅ（２０１２年８月１２日〜１５日）でのＷ。Ｆｕ  ｅｔ  ａｌ．による、「Ａ  Ｇｒａｐｈ  Ｇｒａｍｍａｒ  Ｂａｓｅｄ  Ａｐｐｒｏａｃｈ  ｔｏ  Ａｕｔｏｍａｔｅｄ  Ｍａｎｕｆａｃｔｕｒｉｎｇ  Ｐｌａｎｎｉｎｇ」には、部品の加工性について推論するためのグラフ文法表現が記載されており、この開示は、参照することにより本明細書に組み込まれる。部品を複数のサブ容積に分解し、これらの各サブ容積が１回の作業で機械加工可能であるか否かを確認する。サブ容積が機械加工可能であるという確認に基づいて、分解された部品をグラフに変換し、部品を加工するために必要な機械加工動作のシーケンスとして加工計画の候補を作成する。しかし、部品の分解に依存することで、加工可能とみなされる部品のクラスが制限され、このグラフ文法の方法は発見法に依存するため、この発見法のアプリケーションでは、探索しなければならない解空間が急激に広がり、これにより、加工性の評価の速度は著しく低下する。
【発明の概要】
【発明が解決しようとする課題】
【０００８】
したがって、設計された部品が基本的に製造可能かどうかを確認し、可能であれば、どのような加工の工程計画のシーケンスを用いるかを確認する方法が依然として必要である。
【課題を解決するための手段】
【０００９】
ウェブベースのシステムおよび方法では、加工設定のモデル、および任意の形状で設計された部品の情報を用いて、連続する２ステージからなる工程計画を作成する。第１のステージで、部品形状を分析する。方向性を有する機械加工の工具から機械加工可能な最大容積を判定するクエリが、方向性を有する機械加工の工具の先端に取り付けられた仮想カメラの視界による部品の表面の可視性の判定に変換される。第２のステージで、全ての工具の方向の設定に対する機械加工可能な最大容積の集合を集計する。加工性および工程計画に関するフィードバックを提供するために、機械加工可能な最大容積の組み合わせによりカバーされる、原材料と所望の部品との差全体を評価する。さらなる実施形態では、任意の幾何学的な複雑さを有する工具および機械に関する加工性を、高次元配置空間分析を用いて分析する。
【００１０】
一実施形態では、切削される容積を求めることにより、機械加工される部品に関するする工程計画を作成するコンピュータ実装システムおよび方法が提供される。この方法では、フライス加工の工具に関するパラメータを検索し、このパラメータは工具の複数の方向性を含み、その全長方向に回転する刃先を移動させる。部品の表面を規定する部品のモデルにアクセスする。回転する刃先と部品の表面の衝突を避ける工具に関する平行移動の最大設定を検索する。各平行移動には、工具の方向性およびその平行移動により切削可能な容積が含まれる。最大設定内の平行移動の交点を計算する。交差する平行移動に関する切削される容積の和集合を算出する。この和集合が部品の負の容積と実質的に等しいことを条件として、工具による機械加工の動作を含む工程計画を決定する。
【００１１】
さらなる実施形態では、畳み込み積分を通して機械加工される部品の加工性を分析するコンピュータ実装システムおよびその方法が提供される。この方法では、フライス加工の工具のパラメータを検索し、このパラメータは工具の複数の方向性を含み、その全長方向に回転する刃先を平行移動させる。次いで、部品の表面を規定する部品のモデルにアクセスする。工具の方向性ごとに、部品の機械加工可能な最大容積を決定する。回転する刃先と部品の表面の衝突を避ける工具の平行移動の最大設定を計算する。工具により機械加工可能な部品の表面の外側の工具の平行移動の最大設定の最も大きな空間を決定する。工具の平行移動の最大設定の交点を、工具に関する機械加工可能な最大容積として算出する。機械加工可能な最大容積の和集合が、部品の負の容積と実質的に等しいかどうかに基づいて、部品の加工性を評価する。この和集合が部品の負の容積と実質的に等しいことを条件として、工具による機械加工の動作を含む工程計画を決定する。
【００１２】
さらなる実施形態では、次元降下と可視性分析を通して、機械加工される部品の加工性を分析するコンピュータ実装システムおよびその方法が提供される。この方法では、フライス加工の工具のパラメータを検索し、このパラメータはこの工具の複数の方向性を含み、全長方向に回転する刃先を平行移動させる。部品の表面を規定する部品のモデルにアクセスし、この部品にはアンダーカット形状がない。衝突しない工具の平行移動を決定する。部品の表面へ接近する工具と、垂直な部品の高さマップを工具の起点から計算する。工具の起点を中心として部品の表面から離れていく方向に向かって見る工具の高さマップを計算する。工具を部品の表面の上にスイープさせることにより作成される容積を含む、切削される容積の高さマップを作成する。部品の表面と工具の衝突が特定されると、工具の高さマップの各点に関する工具と部品の表面の交点を算出し、部品の表面から離れる方向に工具が貫通する深さ分だけ、工具を平行移動させる。工具が衝突しない平行移動の和集合が、部品の負の容積と実質的に等しいかどうかに基づいて、部品の加工性を評価する。部品が製造可能であることを条件として、工具による機械加工の動作を含む工程計画を決定する。
【００１３】
詳細に説明する同期の課題と、部品の加工性の分析に基づく複数の加工工程の計画は、デジタル加工の分野では一意であり、製品ライフサイクルの間の重要なギャップを埋めることができる。従来、設計と加工は、２つの異なる部門とみなされ、機械加工に関するデジタル加工の作業の大半は、技術者が機械と処理をシミュレーションして、彼らの設計および工程計画を手動で確認することにその焦点が当てられている。本明細書に記載される方法は、工程計画を同期させるだけでなく、設計者と工程技術者にフィードバックを提供し、かつウェブ上に配置することができる。
【図面の簡単な説明】
【００１４】
【図１】図１は、人間により作られた加工工程計画を確認する従来技術のシステムを、例として示す機能ブロック図である。
【図２】図２は、一実施形態による、機械加工による部品の加工性を分析し工程計画を行うコンピュータ実装システムを示す機能ブロック図である。
【図３】図３は、図２のシステム用いて、フライス加工により加工される部品を、例として示すブロック図である。
【図４】図４は、図２のシステム用いて、１つの方向性を有する工具に対して計算された部品の１ステージのモデルを、例として示すブロック図である。
【図５】図５は、図２のシステム用いて、１つの方向性を有する工具に対して計算された部品の１ステージのモデルを、例として示すブロック図である。
【図６】図６は、一実施形態による、機械加工される部品の加工性を分析し工程計画を行う、コンピュータにより実行される方法を示す流れ図である。
【図７】図７は、図６の方法の中で行われる、加工性を評価するルーチンを示す流れ図である。
【図８】図８は、図７のルーチンの中で行われる、機械加工可能な最大容積を集計するルーチンを示す流れ図である。
【図９】図９は、ボールエンドミルの接触面の高さマップを、例として示す図である。
【図１０】図１０は、図７のルーチンの中で行われる、可視性分析を行うルーチンを示す流れ図である。
【図１１】図１１は、図１０の可視性分析のルーチンの徐々に進行するステージを、例として示すブロック図である。
【発明を実施するための形態】
【００１５】
従来、組織内で設計と加工は密接に連動して動いているが、未だに機能的な作業範囲は分離している。一般には、まず製品の設計が行われ、それに続いて、製品の実現化および製品の加工が行われる。設計部門からの個別の出力として部品の設計は扱われ、設計が終了しその後、製品の加工が始まる前に、部品加工に関する、人間により作成された工程計画の確認が行われる。
【００１６】
加工工程計画に対する従来のアプローチは、製品ライフサイクル管理と実際の現場の生産をよりよく統合することを目的としてきたが、設計と加工の間の相違が付随的に明確となっていた。図１は、人間により作成された加工工程計画を確認する従来技術システム１０を、例として示す機能ブロック図である。設計に続くその後の製品ライフサイクルのステージの間に加工性が評価される。製品の設計は、設計部門１１と加工部門１２の間を、設計された部品が最終的に製造可能と判定されるまで、何度も往復しなければならない可能性がある。部品の設計と加工の間で行き来するサイクルは、これらの部門で別々に担当作業が実行されるために起こる。人間により作成された加工工程計画の確認を行うために必要なこのようなやり取りは、時間の浪費でありコスト高になる恐れがある。
【００１７】
加工性の分析と工程計画の自動化は、部品レベルでの高度な幾何学的推論に依存し、それらの推論の結果と、加工設定のモデル（具体的には、各部品を機械加工するために用いる工具）と組み合わせて、設計者および加工技術者の両方を支援する複雑な課題である。現在のアプローチでは、例えば、部品のモデル内の特別な種類の特徴に対する解決策を提供するとき、加工時間およびコストを見積もるとき、または技術者のために工場をシミュレーションして加工性を可視化し確認するときなど、最小限の範囲でこのような機能が取り組まれている。
【００１８】
加工設定の詳細なモデルをより早い段階で、（具体的には設計の工程中に）、製品ライフサイクルに導入することで、その構造により、かつ加工性および同様の問題に関するフィードバックを作成することにより、機械加工される部品の設計、およびそれにしたがって、部品加工に関する工程計画が正しいことを確認する。図２は、一実施形態による、機械加工による部品の加工性を分析し工程計画を行うコンピュータ実装システム２０を示す機能ブロック図である。ウェブ上のサービス２３は、加工設定の元来の機能をモデリングすることにより、具体的な部品の加工性に関する詳細なフィードバックを提供する。有線接続または無線接続を使用する、インターネットなどの、広域公衆データ通信ネットワーク上のウェブを通して、遠隔的にアクセス可能な集中型サーバ２２を介して、プログラム２１が提供される。パーソナルコンピュータ２７または同様の装置上で実行するウェブのブラウザ２８を通して、ユーザはサーバ２２にアクセスする。サーバ２２は記憶装置２４と操作可能に接続し、その記憶装置の中には、例えば、ボクセルまたは同様の容積測定単位を用いて表される、設計された部品２５のモデル、および機械加工工具２６のライブラリが格納される。サーバ２２およびパーソナルコンピュータ２７は両方共、中央処理装置、メモリ、入力ポート／出力ポート、ネットワークインターフェース、および不揮発性記憶装置などの、従来、汎用性プログラム可能コンピュータ装置内で見ることができる構成部品を含むが、その他の構成部品も含むこともできる。さらに、その他のコンピュータ構成部品も含むことも可能性である。
【００１９】
プログラム２１は、ジオメトリックエンジンを実装し、このジオメトリックエンジンが、工具の形状および自由度、または周りの治具および固定具の存在を想定しないで、任意の幾何モデルを自動的に加工性分析するための、一連の空間計画アルゴリズムを実行する。加工設定モデルは、使用可能な工具ごとの仕様書を含む機械加工の工具２６のライブラリに対応し、プログラム２１は、アップロードされた各部品２５の幾何モデルに対して、使用可能な各工具の機能に接続して質的に異なる工程計画を提供する。これらの工程計画は、ＪＳＯＮ（「ＪａｖａＳｃｒｉｐｔ（登録商標）  Ｏｂｊｅｃｔ  Ｎｏｔａｔｉｏｎ」）ファイルまたは同様の構造符号化の形態、あるいは人間が読める形式で表示され、個々の設計ごとに詳細なフィードバックを行う。幾何学的推論を行うアルゴリズムは、ライブラリ２６からの工具情報を用いて、工具の方向性ごとに部品ストックをもとに機械加工可能な最大容積の探索空間を構築し、続いて、探索アルゴリズムが、この空間を自由に平行移動し工程計画の一連の候補を特定する。これに関しては、図６を参照して下記にさらに詳しく説明する。プログラム２１は、この探索空間に解決法が存在するかどうかを確認した後、平行移動を開始する。
【００２０】
幾何学的推論を行うアルゴリズムは、剛的動作の配置空間の特性に依存する数学的原理に基づき、パーソナルコンピュータ２７またはその他の同様の装置を用いて、グラフィックハードウェア上の畳み込み積分に関して抽象的に実行可能である。さらに、工具形状がアンダーカット形状を処理しない特別なケースでは、次元降下と可視性の分析により実行されるアルゴリズムにより、畳み込み積分のアルゴリズムと比較して、著しいスピードアップと解像度が提供される。
【００２１】
以下の定義を用いる。
・膨張：「δ」により示され、そのマップは「δ（Ｍ，Ｘ）＝∪ｍ∈ＭＸｍ」により規定される。但し、「Ｘｍ」は剛性移動「ｍ」により平行移動される個体Ｘを表す。膨張とは、１つのパラメータスイープの通常動作、および、例えば、Ｊ．  Ｓｅｒｒａによる、「Ｉｍａｇｅ  Ａｎａｌｙｓｉｓ  ａｎｄ  Ｍａｔｈｅｍａｔｉｃａｌ  Ｍｏｒｐｈｏｌｏｇｙ、Ｖ．１（１９８２年）」に記載されたミンコフシキー和を一般化したものであり、上記の開示は参照することにより、本明細書に組み込まれるものとする。
・浸食：「ε」により示され、そのマップは「ε（Ｍ，Ｘ）＝∩ｍ∈ＭＸｍ」によりを規定される。浸食とは、例えば、Ｈ．Ｔ．  Ｉｌｉｅｓ  ｅｔ  ａｌによる「Ｄｕａｌ  ｏｆ  Ｓｗｅｅｐ」Ｃｏｍｐ．  Ａｉｄ．  Ｄｅｓｉｇｎ、３１（３）：１８５〜２０１ページ（１９９９年）に記載された（１つのパラメータの）非スイープの動作、およびミンコフシキー差を一般化したものであり、上記の開示は参照することにより、本明細書に組み込まれるものとする。
・同次構成積、または単に同次積：静止個体との間で衝突を引き起こす、移動個体の剛性移動の最大集合を求める演算である。移動個体Ｔの動作が静止個体Ｓの存在下の平行移動に制限される場合、例えば、Ｊ．Ｃ．  Ｌａｔｏｍｂｅによる、「Ｒｏｂｏｔ  Ｍｏｔｉｏｎ  Ｐｌａｎｎｉｎｇ（１９９０年）」に記載されるように、同次積は、ＳおよびＴの平行移動配置空間の障害である。上記の開示は、参照することにより本明細書に組み込まれるものとする。
・左同次構成商、または単に左商：静止個体Ｓ内に封じ込められる移動個体Ｔの全ての剛性移動を求める演算
【数１】
2014115991.tif 000003
である。平行移動の場合、例えば、上記のＪ．  Ｓｅｒｒａに記載されるように左商は浸食に関連する。
【００２２】
機械および切削工具のライブラリを用いて、機械加工される部品の加工性を評価し、金属の原材料に関する機械加工の動作を決定し、製造可能部品を作成することは、自動化に関して著しく広い範囲を提供する課題である。図３〜図５は、フライス加工により加工される部品、および２つの異なる方向性を有する工具に関して、図２のシステム２０を用いて計算された２ステージの部品のモデルを、それぞれ例として示すブロック図である。各ステージのモデル（機械加工の動作後も切削されずに残る材料）は、一般に、いくつかの方向で再固定され、これにより、部品の表面全体を切削工具が機械加工することができる。１つの組（Ｓ、Ｐ）を考慮すると、Ｓは固定される原材料またはステージのモデルを表し、Ｐは加工される部品を表し、ＳからＰに機械加工するために選択される工具をＴで表す。全ての個体をＭの要素として表すと仮定する。加工性の分析では暗黙時に衝突判定を行って機械加工可能な最大容積を計算するため、以後の全てのステージでは、部品を含む全体の据え付け配置をＰと置き換えることができる。最初に図３を参照すると、設計される部品のモデルが示される。材料の長方形のピースから原材料を切削することにより部品が加工される。次に、図４および図５を参照すると、２つの異なる方向性を有する工具（グリーン）が、原材料（パープル）を機械加工するために計算される２ステージのモデル（イエロー）が示される。長方形の原材料内の各ステージモデルの補数は機械加工可能な最大容積を表す。
【００２３】
ステージモデルでは、複数の方向は直線的に伸びるため、誰かが単純に工具Ｔを所望の方向Ｔ＊に向け、機械加工可能な最大容積を再計算しなければならないことを示す。必要であれば、部品を加工する動作のシーケンスを決定する間に、材料Ｓもあらゆるステージモデルで交換することができる。したがって、多軸フライス盤を用いて「多面」のフライス加工を行う場合、つまり、工具の複数の方向性を有する平行移動可能なフライス加工動作を行う場合にも、工具を平行移動させるための機械加工可能な最大容積を計算する分析が適用され得る。部品を全ての工具方向に対して再固定させる必要がないため、多面フライス加工では設定時間を短くさせ易いとともに機械加工の精度も向上させる。
【００２４】
空間計画アルゴリズムは、切削工具の自由度または周りの治具および固定具の存在を想定することなしに、工具および材料形状の大きなクラスに関する原材料に対する機械加工の動作のシーケンスを決定する。図６は、一実施形態による、機械加工される部品の加工性を分析し工程計画を行う、コンピュータにより実行される方法４０を示す流れ図である。例えば、サーバなどの汎用性のプログラムされたコンピュータにより実行される一連のプロセスまたは方法のステップとしてこの方法を実行する。
【００２５】
まず、設計された部品を機械加工するために使用される工具のライブラリを含む加工設定のモデルと、設計された部品の情報とをそれぞれ検索する（ステップ４１およびステップ４２）。工具が動作可能な方向性および位置を含む、各種類のフライス加工の工具に関する情報が、このライブラリに格納される。次いで、空間設計は、２つの連続するステージにおおまかに区別される。以下に図７を参照してさらに詳しく説明する通り、最初にライブラリ内の各工具により、機械加工される容積に対して部品の加工性を評価する幾何学的推論が行われる（ステップ４３）。これに続いて、部品が製造可能ならば（ステップ４４）、探索アルゴリズムが、切削される容積のシーケンスに関して規定される計画を作成する（ステップ４５）。切削される容積とは、設計された部品の表面上に工具をスイーピングさせることにより作成される容積である。以下に図８を参照してさらに詳しく説明する通り、機械加工可能な最大容積の和集合が部品の負の容積と等しければ、その部品は工具により製造可能である。以下に図１０を参照してさらに詳しく説明する通り、さらなる実施形態では、工具の衝突しない平行移動の和集合による工具のスイープが、部品の負の容積と等しければ、その部品は工具により製造可能である。さらにさらなる実施形態では、機械加工可能な最大容積の和集合、または衝突しない平行移動は、必要に応じて、全ての機械加工可能な最大容積、または衝突しない平行移動の全部または一部の和集合であり得る。さらに、機械加工可能な最大容積または衝突しない平行移動の和集合は、絶対測定値よりは、むしろ特定の公差までの部品の負の容積と同等であり得る。さらにその他の加工性の基準も使用可能である。
【００２６】
加工性を分析中、部品レベルの高度な幾何学的推論と加工設定のモデル（具体的には各部品を機械加工するために使用する工具）を組み合わせて、部品が製造可能かどうかを判定する。図７は、図６の方法４０で使用する、加工性を評価するルーチン５０を示す流れ図である。ライブラリ内の各工具を次の通りに評価する（ステップ５１〜ステップ５７）。まず、工具の形状を分析して（ステップ５２）、設計された部品が、工具のアンダーカット形状を必要とするかどうかを判定する。以下に図８を参照してさらに詳しく説明する通り、アンダーカット形状を必要とする場合（ステップ５３）、各方向に工具により機械加工可能な最大容積を集計する（ステップ５４）。以下に図９を参照してさらに詳しく説明する通り、工具の形状がアンダーカット形状を有さない場合（ステップ５３）、機械加工可能な最大容積を集計するときに、畳み込み積分のアルゴリズムを使う代わりに、次元降下と可視性分析を通して実行されるアルゴリズムを使うことができる（ステップ５６）。最終的に、集計された機械加工可能な最大容積に基づいて、または場合により可視性分析に基づいて、加工性を判定する（ステップ５５）。ライブラリ内の各工具の関しても同様の処理を行う（ステップ５７）。
【００２７】
工具Ｔに関する機械加工可能な最大容積を集計するには、工具Ｔが設計された部品Ｐと干渉することなしに取り除くことができる固定された原材料Ｓの最も大きな部分を判定しなければならない。図８は、図７のルーチン内で行われる、機械加工可能な最大容積を集計するルーチンを示す流れ図である。説明を簡単にするために、まず問題を平行移動する工具を用いて、静止材料から機械加工可能な最大容積を判定することと規定する。例えば、この状況は実際に、３つの軸のフライス盤を用いて固定された材料から金属を切削するときに見られる。平行移動する単一の工具に関する形式を伸ばして、工具と部品の間に複数の相対配向を形成すると簡単明瞭である。
【００２８】
次の通りに、工具Ｔの各方向性を評価する（ステップ６１〜ステップ６６）。製造可能と判定される部品Ｐに関して、工具Ｔ上の基準点が、その時点の方向から達することができるいくつかの位置の間に原材料Ｓを固定して配置する。全ての機械加工可能な最大容積の和集合が、部品の負の容積、つまり、固定された原材料Ｓから容積が差し引かれた部品Ｐと同じ場合、およびその場合に限って、部品Ｐは工具Ｔにより製造可能である。
【００２９】
最初に、部品Ｐとの衝突を避ける工具Ｔの平行移動の最大設定を計算する（ステップ６２）。絶対座標系の起点が工具Ｔ上の基準点と一致していることを確認する。同次商を規定することにより、Ｐｃ内に残る工具Ｔ、つまり、Ｐと衝突しない工具Ｔに適用可能な平行移動の最大設定は下記の式で表せる。
【数２】
2014115991.tif 000004
この式により、その時点の方向の工具Ｔに適用可能な平行移動の空間全体の最も大きな部分の外形が表される（ステップ６３）。
【００３０】
しかし、実際には、機械加工は使用可能な作業空間、または工具が到達可能な複数の位置および方向により制限される。固定された方向性を含むその時点の状況は、工具の全ての到達可能な位置、すなわち到達可能な作業空間の設定だけに関係する。到達可能な作業空間をＲで示し、工具Ｔに適用可能な平行移動の最大設定
【数３】
2014115991.tif 000005
を下記の式に修正する（ステップ６４）。
【数４】
2014115991.tif 000006
したがって、スイープδ（Ｋ、Ｔ）は、部品Ｐの形状と干渉することなしに許される平行移動の最大設定による工具のスイープを示す。
【００３１】
最終的に、原材料（またはステージモデル）Ｓから機械加工可能な最大容積は下記の式により算出される（ステップ６５）。
【数５】
2014115991.tif 000007
到達可能な作業空間の計算された部分により、スイープされた工具Ｔの容積は、構造により、部品形状の外側に残ることが保証されているため、スイープδ（Ｋ、Ｔ）は部品の負の容積と交差する必要はない。工具Ｔの各方向に関しても同様の処理を行う（ステップ６６）。
【００３２】
さらなる実施形態では、任意の幾何学的な複雑さを有する工具および機械に関する加工性を、高次元配置空間分析を用いて分析する。式（３）により計算された機械加工可能な最大容積により部品の境界の一部がさらされる場合、接触可能な境界「δＰａｃｃ」は、「κ（Ｖｍａｘ）∩∂（Ｐ）」で正確に表すことができる。但し、κ（Ｘ）および∂（Ｘ）は、集合Ｘの閉包および境界をそれぞれ表す。それと反対に、「δＰａｃｃ」は、固定された方向の材料またはステージモデルから最大切削可能容積を工具が機械加工するときに、さらされる部品の境界の完全部分である。
【００３３】
工具Ｔが無限大の長さおよび厚さゼロを有する極端な例を考察すると、そのとき、式（３）は、関心の方向に沿って「Ｐａｃｃ」内の任意の点に接近する工具は、固定された部品に干渉しないことを示唆する。この極端な例では、特定な方向に沿って見ることができる点の集合「Ｐｖｉｓ⊂∂（Ｐ）」は全て機械加工可能である。より一般的には、アンダーカット形状のない無限大の長さを有する工具（または議論のために、無限に長いとみなすことができる工具）に関して、ｘとｙに接続する線分が完全に自由な物理的空間Ｐｃ内になるように、任意の点「ｘ∈Ｐａｃｃ」から発せられる光線は、いくらかの点「ｙ∈Ｔ」で衝突しない構成の工具と必ずしも交差しない。したがって、「Ｐａｃｃ」内の全ての点はこのような工具から見ることができると言われる。
【００３４】
式（１）で集合
【数６】
2014115991.tif 000008
全体を計算することを避けるために、この特別な例では、工具Ｔがアンダーカット形状をもたず、無限大の長さを有するとき、「Ｖｍａｘ」を可視性の分析を通して計算することができる。最初に、ゼロでない厚さ「Ｐａｃｃ≠Ｐｖｉｓ」を有する工具に関する。δ（Ｐｉｎａｃｃ，Ｔ）∩Ｐ≠φとなるように、集合「Ｐｉｎａｃｃ⊂Ｐｖｉｓ」は目に見える工具の位置の中の到達できない位置を表す。したがって、機械加工可能な最大容積「Ｐｖｉｓ」を最初に計算し続いて、その和集合の全体に渡って分散する膨張を監視することにより「δ（Ｐｉｎａｃｃ，Ｔ）」を抽出する。
【数７】
2014115991.tif 000009
【００３５】
工具が無限大の長さを有するとき、この「Ｖｍａｘ」の形式は式（３）と等しい。「Ｖｍａｘ」を計算することを考えると、工具のクラスに関する可視性を用いる方法は効率的な代替案である。
【００３６】
高さマップに関して可視性を暗黙的に符号化する。次に、切削される高さマップＲＨｍａｐから切削される容積を計算する。３次元の計画空間（Ｘ，Ｙ，Ｚ）内の各点（ｘ，ｙ，ｚ）を工具の（Ｘ’，Ｙ’，Ｚ’）の座標系に投影し、その空間内の点（ｘ’，ｙ’，ｚ’）がＲＨｍａｐ（ｘ’，ｙ’）より上か下かを判定する。より正確には、ｚ’＜ＲＨｍａｐ（ｘ’，ｙ’）の場合、点（ｘ’，ｙ’，ｚ’）は切削される容積内である。
【００３７】
表面に接触する無限から発せられる遮られない光線に関して所与の方向から可視性を規定する。無限を、有限（しかし十分に長い距離）と置き換えた場合、標準のＺバッファー法による隠面消去と正投影を用いて、表面上の可視点のサンプリングを計算することができる。コンピュータグラフィックスでは、このＺバッファー法が、画像内の全ての画素に関して、最も近い面までの距離を計算する標準的な方法であり、これにより離れた面は近い面により正確に遮られる。Ｚバッファーのアルゴリズムは、単に高さマップを保持し、最初に全ての画素に関して無限と設定し、モザイク式のモデル内の全ての三角形内の全ての画素を描こうと試み、その画素から三角形までの距離が、その画素に関するＺバッファーの中のどの値よりもその時点で小さい場合、所与の画素だけを描き、その場合、Ｚバッファーを更新する。
【００３８】
３つの軸のフライス盤内の軸に関する正式名称は、工具が周りを回転する軸をＺ軸と呼び、部品に向かう移動を＋Ｚ方向の移動と呼ぶ。工具は、Ｘ、Ｙ、またはＺに沿って、平行移動することができ、かつＺの周りだけを回転することができる。Ｚの周り回転を無視し（回転対象の工具、または工具がそのスイープされた容積により表されると仮定する）、状態空間および工具が許される平行移動に関するＺバッファーのアルゴリズムのマップを用いて、高さマップを計算する。全ての（Ｘ，Ｙ）組に関して、対応する高さマップの値は、部品の内側に衝突することなしに、工具が＋Ｚ方向に平行移動することができる距離の上限である。無限大に薄い工具では、高さマップの値は正確であるが、有限の厚さを有する工具では、衝突は依然として問題であり、したがって「Ｐａｃｃ≠Ｐｖｉｓ」かつ「Ｐｉｎａｃｃ⊂Ｐｖｉｓ」である。部品の観点からすると、アンダーカットのない工具の先端面は、−Ｚ方向から見ると工具の可視部となる。図９は、ボールエンドミルの接触面の高さマップを、例として示す図であり、ボクセルまたは同様の容積測定単位の高さマップとして表されている。工具が部品に接近するとき、その工具は、＋Ｚ方向に移動すると言う、したがって接触面は最大のＺ軸値を有する工具の表面である。
【００３９】
重要なことは、−Ｚ方向は部品から離れる方向であり、−Ｚ方向に移動することにより、無限大の長さを有するアンダーカット形状のない工具は部品と衝突していない状態から衝突する状態に移行することはあり得ないということである。それどころか、衝突状態から衝突していない状態にのみ工具は移行可能であり、有限の部品に関しては、最終的に衝突している工具が、衝突していない状態に移行することが保証される。したがって、工具の表面の一部が部品の内側に衝突する場合、所与の（Ｘ，Ｙ）に関して、非無限大に薄い工具が部品と衝突することなしに到達することができる、最も遠くの＋Ｚ方向の位置を見つけるために、Ｚバッファーの高さマップ内の上限を推測し、工具を繰り返し−Ｚ方向へ移動させることにより可視性分析を開始することができる。図１０は、図７のルーチンで使用される可視性分析を実行するルーチン８０を示す流れ図である。最初に、部品Ｐを起点の中心に配置する（ステップ８１）。工具の接近方向Ｚを考慮して−Ｚに沿って離れた地点から正投影的に部品をレンダリングすることにより、部品ＰのＺバッファーの高さマップ「ＰＨｍａｐ」を計算する（ステップ８２）。この点が工具の起点である。
【００４０】
次に、上記と同じ方法を用いるが、工具の起点の中心に仮想カメラを配置し、−Ｚ方向に向かって見ながら、工具の高さマップＴＨｍａｐを計算する（ステップ８３）。工具Ｔが衝突することなしに部品上をスイープした後に残る容積である、切削される容積に関する高さマップ「ＲＨｍａｐ」を作成し、全ての点を初期化してゼロにする（ステップ８４）。次の通りに、部品の高さマップ「ＰＨｍａｐ」内の各点（Ｘ，Ｙ）を処理する（ステップ８５〜ステップ９１）。最初に、工具のＺ方向の最大移動量Ｚｍａｘを、「Ｚｍａｘ（Ｘ，Ｙ）＝ＰＨｍａｐ（Ｘ，Ｙ）」として初期化する（ステップ８６）。工具の高さマップ「ＴＨｍａｐ」内の各点（Ｘ’，Ｙ’）を衝突に関して確認する（ステップ８７〜ステップ９０）。つまり、「ｍｉｎＸ（ＴＨｍａｐ）≦Ｘ’≦ｍａｘＸ（ＴＨｍａｐ）」かつ「ｍｉｎＹ（ＴＨｍａｐ）≦Ｙ’≦ｍａｘＹ（ＴＨｍａｐ）」であるかどうかを、次の通りに確認する。その時点の「Ｚｍａｘ」に関する値を考慮した場合、「ＴＨｍａｐ」の所与の点（Ｘ’，Ｙ’）が、部品Ｐの内側に衝突する可能性があり（ステップ８８）、「Ｚｍａｘ」を−Ｚ方向に貫通する深さ分だけ平行移動させる（ステップ８９）。各（Ｘ’，Ｙ’）に関してもこの処理を行い（ステップ９０）、各（Ｘ，Ｙ）に関してもこの処理を行う（ステップ９１）。
【００４１】
可視性分析のアルゴリズムの種々のステージを示すことができる。図１１は、図１０の可視性分析のルーチンの徐々に進行するステージを、例として示すブロック図である。上段左側のブロックでは、工具の座標系内でマッピングされた工具Ｔ（ブルー）と部品（レッド）が示される。上段右側のブロックでは、工具Ｔの所与の（Ｘ，Ｙ）平行移動に対して、「Ｚｍａｘ（Ｘ，Ｙ）」をＰＨｍａｐ（Ｘ，Ｙ）に初期化する。中断左側のブロックでは、「Ｚｍａｘ（Ｘ，Ｙ）」を工具Ｔの最大貫通深さ分だけ−Ｚ方向に平行移動させる、そのため部品Ｐとは衝突していない。中断右側のブロックでは、全ての（Ｘ，Ｙ）対してアルゴリズムを実行する。下段左側のブロックでは、「（ｘ，ｙ）∈（Ｘ，Ｙ）」に関して「Ｚｍａｘ（Ｘ，Ｙ）」である。最終的に、下段右側のブロックでは、「（ｘ，ｙ）∈（Ｘ，Ｙ）」に関して「ＲＨｍａｐ（ｘ，ｙ）」である。
【００４２】
工具Ｔが、設定Ｗ内で行われる平行移動に従って移動することを確認する。この設定Ｗは作業空間と呼ばれ、空間の剛性平行移動の配置空間ＳＥ（３）の部分である。工具に取り付けられた座標フレームの位置に関して、工具Ｔがその動作中に到達可能な位置および方向が表される。そのような各フレームは、最初に、広域座標系で揃えられ、その絶対座標系に対して平行移動が表されていることをさらに確認する。暗黙的に、作業空間Ｗも絶対座標系に対して位置および工具の方向性を表す。各フレームの起点がＴの基準点であり、工具Ｔと原材料Ｓが接触する特別な点を示し、この点を用いて、加工性に関する工具Ｔの正式な空間位置を分析する。
【００４３】
各工具Ｔにより原材料Ｓから機械加工可能な最大容積は式（１）および（２）をＳＥ（３）に拡張することにより表される。したがって、Ｔごとの機械加工可能な最大容積は下記の式で表される。
【数８】
2014115991.tif 000010
【００４４】
元来の６次元の計算は、
【数９】
2014115991.tif 000011
の半直積構造により小さい３次元の計算に分解される。実際には、ＳＥ（３）の半直積構造は下記の式を示唆する。
【数１０】
2014115991.tif 000012
式（９）は複数の３次元のミンコフシキー差の計算に分解することにより扱い易くした６次元の同次商の計算を表す。この計算では、機械工具の作業空間における回転「ＳＯ（３）」の３次元のグループの離散化が必要である。ＳＯ（３）の広域離散化は複数の方法で行うことができ、それらの全ては、回転グループのいくらかの局所離散化また広域離散化用いて、離散パラメータ値を選択することに依存し、この局所離散化また広域離散化は、Ｓ．  Ｎｅｌａｔｕｒｉ  ｅｔ  ａｌによる「Ｓｏｌｖｉｎｇ  Ｉｎｖｅｒｓｅ  Ｃｏｎｆｉｇｕｒａｔｉｏｎ  Ｓｐａｃｅ  Ｐｒｏｂｌｅｍｓ  ｂｙ  Ａｄａｐｔｉｖｅ  Ｓａｍｐｌｉｎｇ」Ｓｙｍｐ．  Ｓｏｌｉｄ  ＆  Ｐｈｙｓ．  Ｍｏｄｅｌ．  ２０１２  （２０１２年）に記載され、この内容を参照することより本明細書に組み込まれるものとする。
【００４５】
多軸の機械加工を行うため、一般に使用可能な機械工具の方向は軸ごとに提供される。これらの方向を「ＳＯ（３）」の単一の探索可能部分に組み合わせることができ、これには、作業空間内で構成積を用いて到達可能な全ての方向性が含まれる。この内容はＳ．  Ｎｅｌａｔｕｒｉ  ｅｔ  ａｌによる「Ｃｏｎｆｉｇｕｒａｔｉｏｎ  Ｐｒｏｄｕｃｔｓ  ａｎｄ  Ｑｕｏｔｉｅｎｔｓ  ｉｎ  Ｇｅｏｍｅｔｒｉｃ  Ｍｏｄｅｌｉｎｇ」、Ｃｏｍｐ．  Ａｉｄ．  Ｄｅｓｉｇｎ  （２０１２年）に記載され、この開示を参照することにより本明細書に組み込まれるものとする。「Ａ，Ｂ⊂ＳＥ（３）」に関して、構成積は
【数１１】
2014115991.tif 000013
マップであり、下記の式に演算子定される。
【数１２】
2014115991.tif 000014
式（１０）で、演算子「・」は、ＳＥ（３）内のグループ演算（そのサブグループのうちのどれか）を表す。ＳＥ（３）内の要素が４×４の同次平行移動マトリクスとして表される場合、演算子「・」は行列乗算と等しい。
【００４６】
５つの軸を有するフライス盤は３方向の平行移動動作に加えて、２つの回転軸の周りの回転自由度を有する。有効軸の周りの回転をＲΘおよびＲΦで示す場合、式（９）内のミンコフシキー差を計算しなければならない「ＳＯ（３）」の部分は、空間回転組成の非交換性のために
【数１３】
2014115991.tif 000015
により算出される。同次商は次の式で計算することができる。
【数１４】
2014115991.tif 000016
【図１】
2014115991.tif 000022
【図２】
2014115991.tif 000023
【図３】
2014115991.tif 000024
【図４】
2014115991.tif 000025
【図５】
2014115991.tif 000026
【図６】
2014115991.tif 000027
【図７】
2014115991.tif 000028
【図８】
2014115991.tif 000029
【図９】
2014115991.tif 000030
【図１０】
2014115991.tif 000031
【図１１】
2014115991.tif 000032