機械加工シミュレーションを最適化するためのシステム及び方法
本発明の実施の形態は、工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される工作物の機械加工のシミュレーションを最適化する方法で、ボリュームはセルのセットに分割され、各セルにこのセルと交差する掃引されたボリュームのサブセットを表す距離フィールドのサブセットを関連付けるステップであって、掃引されたボリュームのサブセットの少なくとも一部はセルの複合サーフェイスを形成する関連付けるステップと、セルに少なくとも１つの方向からこのセルに入射する光線のセットを当てるステップと、距離フィールドのサブセットの或る距離フィールドを選択して、セルと関連付けられた最適サブセットに含めるステップであって、距離フィールドによって表される掃引されたボリュームの境界は、複合サーフェイス上に位置する交点において少なくとも１つの光線と交差する選択して含めるステップとを含む方法である。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、包括的には機械加工シミュレーションに関し、より詳細には、距離フィールドの最適サブセットを決定して機械加工プロセスのシミュレーションを最適化することに関する。
【背景技術】
【０００２】
数値制御フライス加工
数値制御（ＮＣ：ｎｕｍｅｒｉｃａｌｌｙ ｃｏｎｔｒｏｌｌｅｄ）機械加工（例えばフライス加工又は施削）のプロセスをシミュレートすることは、コンピュータコンピュータ支援設計（ＣＡＤ：ｃｏｍｐｕｔｅｒ ａｉｄｅｄ ｄｅｓｉｇｎ）及びコンピュータ支援製造（ＣＡＭ：ｃｏｍｐｕｔｅｒ ａｉｄｅｄ ｍａｎｕｆａｃｔｕｒｉｎｇ）において根本的に重要である。シミュレーション中に、工作物のコンピュータモデルが、工具、例えば、ＮＣフライス加工工具のコンピュータ表現及び１組の工具運動を用いて編集され、機械加工プロセスがシミュレートされる。
【０００３】
シミュレーションは、工作物と工具保持器との間等の部品間の可能性のある衝突を検出し、工作物の最終形状を検証するために、工作物のモデル及び工具の表現を視覚化する。
【０００４】
工作物の最終的な形状は、工具及び工具運動の選択によって影響を及ぼされる。これらの運動を制御するための命令が通常は、コンピュータ支援製造システムを用いて、工作物の所望の最終的な形状のグラフィック表現から生成される。それらの運動は通常、準備コード（ｐｒｅｐａｒａｔｏｒｙ ｃｏｄｅ）又はＧコードとしても知られている、数値制御プログラミング言語を用いて実現される。以下の標準規格ＲＳ２７４Ｄ及びＤＩＮ ６６０２５／ＩＳＯ ６９８３を参照されたい。
【０００５】
コンピュータ支援製造システムによって生成されるＧコードは、所望の最終的な形状の正確な複製物を製造しない場合がある。さらに、ＮＣ工具の動きは、機械加工システムのモータによって支配されるが、その速度、運動範囲、並びに加速及び減速能力は限られているため、実際の工具運動は、ＮＣ機械加工命令に厳密には従わない場合がある。
【０００６】
工作物の実際の最終的な形状と、工作物の所望の最終的な形状との間の不一致は極めて小さい場合があり、見ることが難しい。状況によっては、これらの不一致の結果として、工作物の最終的な形状の表面に、サイズがほぼ数マイクロメートル程度の深さ及び幅、ほぼ数十マイクロメートル程度の長さにわたる望ましくない溝状の傷（ｇｏｕｇｅ）又は欠け目（ｎｉｃｋ）が生じる。
【０００７】
通常、所望の部品を機械加工する前に、より軟質で安価な材料から形成される試験工作物をフライス加工することによって、ＮＣ機械加工命令のセットが試験される。その試験工作物の外観検査によって、試験工作物において望ましくない不一致が見つかった場合には、それに応じて、ＮＣ機械加工命令が変更される。
【０００８】
しかしながら、この手動試験は、時間及びコストがかかる。単一の試験工作物を機械加工するための時間は、ほぼ数時間程度かかる場合があり、許容できるＮＣ機械加工命令のセットが得られるまでに、何度か繰り返すことが必要な場合がある。したがって、コンピュータを利用したシミュレーション及びレンダリングを用いて、これらの不一致を試験することが望ましい。コンピュータに基づくシミュレーションの例は、参照により本明細書に援用される、米国特許出願第１２／４９５，５８８号及び同第１２／４６８，６０７号に記載されている。
【０００９】
工具
図２Ａは、ＮＣフライス加工において用いられる１組の通常の工具２０２、２０４、２０６、及び２０８を示している。工具が工作物２１０に対して動かされるとき、工具は工作物から材料を削り取る。ここで、工具２０２、２０４、２０６、及び２０８は、一般に「掃引されたボリューム（ｓｗｅｐｔ ｖｏｌｕｍｅ）」と呼ばれる、サーフェイス２１２、２１４、２１６、及び２１８に対応する材料を工作物から除去する。各工具によって除去される材料の形状は、工具の形状と、工作物に対する工具の経路とによって決まる。
【００１０】
掃引されたボリューム
機械加工中に、工具の支持された運動、すなわち工具経路に従って、工具が工作物に対して動き、工具経路は工作物に対する工具の相対的な位置、向き及び他の形状データについての情報を含むことができる。
【００１１】
工具が工具経路に沿って動くとき、工具は「掃引されたボリューム」を切り出す。機械加工中に、工具が工具経路に沿って動くとき、掃引されたボリュームによって横切られる工作物の部分が除去される。この材料除去は、コンピュータにおいて、空間領域構成法（ＣＳＧ：ｃｏｎｓｔｒｕｃｔｉｖｅ ｓｏｌｉｄ ｇｅｏｍｅｔｒｙ）差分演算としてモデル化することができ、その演算によれば、工作物からの掃引されたボリュームのＣＳＧ減算演算を用いて、工作物のその部分が工作物から除去される。
【００１２】
図２Ｂは、経路２５２に沿って動かされた形状２５０の掃引されたボリューム２６０を示している。経路２５２は、形状２５０の特定の点の位置を時間の関数として指定する。経路は、形状の向き２５６、２５７、及び２５８を時間の関数として指定することができる。経路は、形状のスケール又は形状の任意の変換を時間の関数として指定することもできる。図２Ｂにおいて、形状２５０の元の位置、向き、及びジオメトリは、経路に沿って動くにつれ、形状２５４の最終的な位置、向き、及びジオメトリに変換される。
【００１３】
図３Ａは、工具３０２が直線３０４に沿って動かされる線形経路を示している。
【００１４】
図３Ｂは、工具３０２の先端３１０が円弧３１２に沿って動かされる円弧経路を示しており、工具の元の軸方向３１４が経路の端部で最終軸方向３１６に変換される。
【００１５】
図３Ｃは、工具３０２の先端３１０が曲線３２０に沿って動かされる曲線経路を示している。
【００１６】
他の可能な経路形式は、ほんの数例を挙げると、工具を或る点に位置決めすること、工具をポリラインとして知られる連続した線に沿って動かすこと、工具を渦巻き状又はらせん状の曲線に沿って動かすこと、工具を二次ベジエ曲線若しくは三次ベジエ曲線等の多項式曲線、又は区分的多項式曲線として知られる連続した多項式曲線に沿って動かすことを含む。工作物の形状又は材料組成によって影響を受ける経路等の、手順によって規定される経路を含む、シミュレートすることができる任意の形式の経路を検討することができる。
【００１７】
距離フィールド
オブジェクトの距離フィールドｄ（ｐ）はスカラフィールドであり、空間内の点ｐにおけるｄ（ｐ）の値は点ｐからオブジェクトのサーフェイスまでの距離である。従来技術において多くの可能な距離フィールドが知られているが、最も一般的で有用であるのは、ユークリッド距離フィールドである。ユークリッド距離フィールドでは、距離はオブジェクトのサーフェイスに対する最小距離であり、ｄ（ｐｓ）＝０として定義される。
【００１８】
加えて、距離フィールドは、オブジェクトの外側を内側と区別するために符号を付され、例えば内側はｄ（ｐ）＞０であり、外側はｄ（ｐ）＜０である。また、ｐにおける距離フィールドの勾配ベクトルは最小距離の方向を指し、オブジェクトのサーフェイスにおいて、正規化された勾配ベクトルはサーフェイスの法線ベクトルに等しい。参照により本明細書に援用される、米国特許第６，３９６，４９２号、同第６，７２４，３９３号、同第６，８２６，０２４号、及び同第７，０４２，４５８号に記載されているように、距離フィールドは陰関数の形式をとり、形状をレンダリング及び編集するための効果的な表現である。
【００１９】
適応的にサンプリングされる距離フィールド（ＡＤＦ：ａｄａｐｔｉｖｅｌｙ ｓａｍｐｌｅｄ ｄｉｓｔａｎｃｅ ｆｉｅｌｄｓ）は、ディテール指向サンプリング（ｄｅｔａｉｌ−ｄｉｒｅｃｔｅｄ ｓａｍｐｌｉｎｇ）を用いて、距離フィールドの空間及び時間的に効率の良い表現を提供する。ＡＤＦは、複数のセルからなる空間的な階層内に距離フィールドを格納する。各セルは、距離データと、そのセルに関連する距離フィールドの部分を再構成するための再構成法とを含む。距離データは、距離フィールドの値と、距離フィールドの勾配及び偏導関数とを含むことができる。メモリ要件及び計算要件を削減するために、セル内の距離フィールドは、必要とされるときに再構成することができる。
【００２０】
ＣＳＧ演算を用いてフライス加工をシミュレートするために、ＡＤＦを用いることができる。フライス加工される工作物及びフライス加工工具は、ＡＤＦとして表すことができる。シミュレートされるフライス加工プロセスは、例えば工作物のＡＤＦを変更することにより、シミュレートされる工作物のＡＤＦを明示的に生成することができる。代替的には、シミュレートされる工作物は、複合ＡＤＦとして暗黙的に表すことができる。複合ＡＤＦは、工作物の距離フィールド及びフライス加工工具と、フライス加工工具のためのＣＳＧ減算演算子のような、距離フィールドに対応する演算子と、格納された距離フィールドをレンダリング又は他の処理中に要求に応じて合成する距離フィールド再構成法とを格納する。
【００２１】
フライス加工工具は、工具距離フィールドによって表すことができる。工具経路は、パラメータ関数によって表すことができる。掃引されたボリュームの距離フィールドは、フライス加工工具を経路に沿って動かすことによって生成される掃引されたボリュームを表すように定義され、ここで掃引されたボリュームの距離フィールドは、掃引されたボリュームの再構成方法に従って連続して定義される。掃引されたボリュームの再構成方法は、サンプル点において掃引されたボリュームの距離フィールドを再構成することができる。
【００２２】
特に関心のあるサンプル点の例は、距離フィールドｄの値がゼロに等しい、すなわちｄ＝０である、任意のオブジェクトの距離フィールドの等値面（ｉｓｏｓｕｒｆａｃｅ）上の点である。本明細書において述べられるように、オブジェクトの距離フィールドのゼロ値等値面は、オブジェクトの境界、例えば工作物の境界であるか、又は掃引されたボリュームの境界である。
【００２３】
図１Ａはセル、例えば１０１、１０２、及び１０３のセルの空間階層からなる複合ＡＤＦ１００の２Ｄの図であり、工作物のボリュームの一部分及び距離フィールドを表し、それらの境界が示されている。この例では、距離フィールド１０４〜１０７は、初期工作物の境界を定義した平面である。距離フィールド１０８〜１１０は、ボールエンドミル工具の掃引を表す３つの距離フィールドである。複合ＡＤＦの各セルは、元の工作物及びフライス加工工具の掃引されたボリュームを表す距離フィールドのセットのサブセットと関連付けられる。例えば、セル１１１と関連付けられるのは距離フィールド１０４、１０８、及び１０９であり、これらの距離フィールドは、合わせてセル１１１内の複合サーフェイスを画定する。距離フィールドのセットのサブセットを組み合わせて工作物の複合距離フィールドを再構成するために、ＣＳＧ差等の手続き的再構成方法もセルと関連付けられる。複合サーフェイスは、元の工作物距離フィールド及び掃引された工具距離フィールドの境界のパッチからなる、工作物のシミュレートされた境界となるように定義される。
【００２４】
セルと関連付けられた距離フィールドのサブセットは、複数の方法によって選択することができる。例えば、サブセットは、セルの中心から境界への距離の絶対値が、セルを完全に取り囲む球の直径よりも小さい距離フィールドのみに限定することができる。代替的に、サブセットは、境界の少なくとも一部分がセルと交差するこの境界を有する掃引されたボリュームを表す距離フィールドのみに制限することができる。これらの距離フィールドは、例えば、距離フィールドがゼロに等しいセル内の点を、境界／セル交差試験を用いて検索することによって決定することができる。
【００２５】
セルと関連付けられた距離フィールドのセットのサブセットが、セル内で複合サーフェイスを実際に形成して、幾何演算、例えばレンダリング中に処理されなくてはならない距離フィールド数を最小にすることによって、シミュレータ性能を最大にする距離フィールドのみを含むことが望ましい。不都合なことに、セルの距離フィールドのサブセットを決定する上述した方法は、結果としてのシミュレータ性能が悪い可能性がある。なぜなら、これらの方法によって見つかるサブセットの複数の距離フィールドは、セルには入るが工作物境界の一部分を形成しない掃引されたボリュームを表す可能性があるためである。
【００２６】
図１Ｂは、工作物の一部分の従来の表現の一例を示している。工作物を表す複合ＡＤＦは、セルのセット、例えばセル１０１と、掃引されたボリューム１１０等の、工具の掃引されたボリュームを表す距離フィールド１０２〜１０５のセットとを含む。工作物１０７の一部分は、セル１０１と、掃引されたボリュームの距離フィールド１０３〜１０５のサブセットとによって表される。掃引されたボリュームの距離フィールド１０２は、セルの境界と交差しないので、この距離フィールドは通常、サブセットに含まれない。しかしながら、この例において見てとることができるように、掃引されたボリュームの距離フィールド１０３及び１０４は、工作物の境界の一部分を形成せず、このため、これらもサブセットに含まれるべきではない。
【００２７】
特定の例として、４００ミクロンの辺寸法を有する、ｘ軸、ｙ軸、及びｚ軸に位置合わせされた立方体セルと、ｘ、ｙ平面においてｘ軸に平行な平行掃引で動く半径２ｍｍの球状の工具とを考える。ここで、掃引間は５０ミクロンだけ隔てられ、工具の高さは、工具の最小点がセルの底辺の極めて僅かに上にあるようになっている。このとき、５６個の工具掃引ボリュームがセル内に境界を有するが、これらの掃引ボリュームのうちの９個のみが工作物の境界を形成する。
【００２８】
したがって、フライス加工プロセスのシミュレーションの性能を最適化するために、セルと関連付けられた距離フィールドのサブセットを最適化する必要がある。
【発明の概要】
【発明が解決しようとする課題】
【００２９】
本発明の目的は、フライス加工プロセスのシミュレーションの性能を最適化することである。
【００３０】
本発明の更なる目的は、工作物及び掃引されたボリュームを表す距離フィールドのサブセットを最適化することである。
【課題を解決するための手段】
【００３１】
本発明の様々な実施の形態において、工作物及び掃引されたボリュームは、距離フィールドを用いて表される。セルと交差する境界を表す距離フィールドを最初に含む距離フィールドのサブセットがセルと関連付けられる。本発明の実施の形態は、サブセットを最適化して、工作物の複合サーフェイスを形成する境界を表す距離フィールドを含む最適サブセットを形成する。
【００３２】
実施の形態は、セル内の工作物の、この工作物から掃引されたボリュームを除去することによって形成された複合サーフェイスが、セル及び／又は複合サーフェイスに入射する光線を当てられた場合、これらの光線と、掃引されたボリューム及び複合サーフェイスの境界との交点は、実際に複合サーフェイスを形成した掃引ボリュームを示すという認識に基づいている。
【００３３】
本発明の１つの実施の形態は、工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される工作物のフライス加工のシミュレーションを最適化する方法であって、ボリュームはセルのセットに分割され、この方法は、各セルに、このセルと交差する距離フィールド境界のサブセットを表す距離フィールドのサブセットを関連付けるステップであって、境界のサブセットの少なくとも一部はセル内で工作物の複合サーフェイスを形成する、関連付けるステップと、セルに、少なくとも１つの方向からこのセルに入射する光線のセットを当てるステップであって、各光線は直線の伝播を表す、当てるステップと、距離フィールドのサブセットの或る距離フィールドを選択して、セルと関連付けられた最適サブセットに含めるステップであって、距離フィールドによって表される掃引されたボリュームの境界は、複合サーフェイス上に位置する交点において少なくとも１つの光線と交差する、選択して含めるステップと、を含み、この方法のステップは、プロセッサによって実行される、工作物のボリュームから掃引されたボリュームのセットを除去することによって実施される工作物のフライス加工のシミュレーションを最適化する方法を開示する。
【００３４】
別の実施の形態は、工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される工作物のフライス加工のシミュレーションを最適化する方法であって、ボリュームはセルのセットに分割され、各セルには、このセルと交差する掃引されたボリュームのサブセットが関連付けられ、掃引されたボリュームのサブセットの少なくとも一部がセルの複合サーフェイスを形成するようにされ、この方法は、セルに、このセルに入射する光線のセットを当てるステップであって、光線はこのセルに向かう直線の伝播を表す、当てるステップと、掃引されたボリュームのサブセットの或る掃引されたボリュームを選択して、セルと関連付けられた最適サブセットに含めるステップであって、掃引されたボリュームの境界は、複合サーフェイス上に位置する交点において少なくとも１つの光線と交差する、選択して含めるステップと、を含む、工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される工作物のフライス加工のシミュレーションを最適化する方法を開示する。
【００３５】
更に別の実施の形態は、工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される工作物のフライス加工のシミュレーションを最適化するシステムであって、ボリュームはセルのセットに分割され、このシステムは、各セルに、このセルと交差する掃引されたボリュームのサブセットを表す距離フィールドのサブセットを関連付ける手段であって、掃引されたボリュームのサブセットの少なくとも一部はセルの複合サーフェイスを形成する、関連付ける手段と、セルに、少なくとも１つの方向からこのセルに入射する光線のセットを当てる手段であって、各光線は直線の伝播を表す、当てる手段と、距離フィールドのサブセットの或る距離フィールドを選択して、セルと関連付けられた最適サブセットに含めるように構成されたプロセッサであって、距離フィールドによって表される掃引されたボリュームの境界は、複合サーフェイス上に位置する交点において少なくとも１つの光線と交差する、プロセッサと、を備える、工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される前記工作物のフライス加工のシミュレーションを最適化するシステムを開示する。
【図面の簡単な説明】
【００３６】
【図１Ａ】機械加工された工作物を表す複合ＡＤＦの概略図である。
【図１Ｂ】工作物の一部分の従来の表現の一例の概略図である。
【図２Ａ】フライス加工に用いられる工具、及びこの工具を経路に沿って動かすことによって工作物から除去された掃引されたボリュームの概略図である。
【図２Ｂ】曲線経路に沿って２Ｄ経路を掃引することによって求められた、掃引されたボリュームの概略図である。
【図３Ａ】フライス加工工具の異なる経路の概略図である。
【図３Ｂ】フライス加工工具の異なる経路の概略図である。
【図３Ｃ】フライス加工工具の異なる経路の概略図である。
【図４Ａ】本発明の実施の形態による、工作物境界を形成する複数の境界を有するセルの２Ｄ概略図である。
【図４Ｂ】本発明の実施の形態による、光線とセル内の境界との交差を示す２Ｄ概略図である。
【図４Ｃ】本発明の実施の形態による、光線とセル内の境界との交差を示す２Ｄ概略図である。
【図５Ａ】産業環境における本発明の実施の形態の概略図である。
【図５Ｂ】本発明の実施の形態による、フライス加工工作物の複合サーフェイスを正確に表すのに必要な掃引された工具の境界の最小リストを決定する方法の流れ図である。
【図６】本発明の実施の形態による、規則的に離間されたグリッド上の光線のセットを示す２Ｄ概略図である。
【図７】本発明の実施の形態による、光線のセットを決定する方法を示す２Ｄ概略図である。
【図８】本発明の実施の形態によるコンピュータメモリの構成の一例である。
【図９】メモリを用いて最適サブセットを決定する方法９００の流れ図である。
【図１０】本発明の実施の形態による複合サーフェイスを形成する境界を表す距離フィールドを求めた結果の例である。
【図１１Ａ】本発明の実施の形態による複合サーフェイスを形成する境界を表す距離フィールドを求めた結果の例である。
【図１１Ｂ】本発明の実施の形態による複合サーフェイスを形成する境界を表す距離フィールドを求めた結果の例である。
【図１１Ｃ】本発明の実施の形態による複合サーフェイスを形成する境界を表す距離フィールドを求めた結果の例である。
【発明を実施するための形態】
【００３７】
システム概観
図４Ａは、本発明の実施の形態によって対処される問題を示している。セル４００内で、境界４０２は工作物のフライス加工のシミュレーションの開始時の工作物４０１の元のサーフェイスを定義している。シミュレーション中、３つの掃引されたボリュームの境界４０３、４０４、及び４０５がセルと交差する。したがって、掃引されたボリュームは、セルによって表される工作物のボリュームから除去される。工作物の内部４０７を取り囲む工作物の複合サーフェイス４０６は、境界４０２及び境界４０５によって形成される。
【００３８】
本発明の様々な実施の形態では、工作物及び掃引されたボリュームは、距離フィールドを用いて表される。セルは、このセルと交差する境界４０２〜４０５を表す距離フィールドを最初に含む距離フィールドのサブセット５５１と関連付けられる（４５０）。本発明の実施の形態は、サブセットを最適化して（５００）、工作物の複合サーフェイスを形成する境界、例えば境界４０２及び４０５を表す距離フィールドを含む最適サブセット５５９を形成する。
【００３９】
境界は、距離フィールドのゼロ値等値面によって定義される。
【００４０】
加えて、共通符号規約の下では、距離フィールドは、掃引されたボリューム内で正であり、境界においてゼロであり、外側で負である。一方、フライス加工プロセスのシミュレーションにおいて、掃引されたボリュームと交差する工作物サーフェイスのいかなる部分も除去されているので、掃引されたボリュームの内部は、工作物の複合サーフェイスの外部にある。したがって、本発明の実施の形態は、掃引されたボリュームを表す距離フィールドをネゲートする、すなわちこの距離フィールドに−１を乗算する。
【００４１】
したがって、元のサーフェイスの境界４０２及び掃引されたボリュームの境界４０５は、セルの最適サブセットを形成し、工作物の内部を取り囲む。ここで、工作物の複合距離フィールドはゼロより大きいあらゆるところにある。境界４０３及び４０４は複合サーフェイスの外側にあり、すなわち、セル内のこれらの境界上のすべての点が工作物の複合サーフェイスに対し負の距離を有する。
【００４２】
光線
本発明の実施の形態は、セルによって表され、工作物から掃引されたボリュームを除去することによって形成されたこの工作物の複合サーフェイスが、セル及び／又は複合サーフェイスに入射する光線を当てられた場合、これらの光線と、掃引されたボリューム及び複合サーフェイスの境界との交点が、複合サーフェイスを実際に形成した掃引されたボリュームを示すという認識に基づく。
【００４３】
光線は、直線と同一の数学的構造である。光線は、３Ｄ空間内の原点Ｒ０から発生し、ベクトルＲｄによって与えられた方向に直線で伝播する。光線の伝播は、３Ｄ空間内の光線の位置がＲ（ｓ）＝Ｒ０＋Ｒｄｓによって定義されるように、時間のような座標（ｔｉｍｅ−ｌｉｋｅ ｃｏｏｒｄｉｎａｔｅ）ｓによってパラメータ化することができる。
【００４４】
図４Ｂは、光線と、掃引されたボリュームの境界との交差の２次元（２Ｄ）の図を示している。例えば、光線４０８は、点４０９から発生し、直線で伝播し、点４１０、４１２、及び４１３において、掃引されたボリュームの境界と交差し、点４１１において元のサーフェイスの境界と交差する。光線のいずれの交点が複合サーフェイス上にあるかを求めることは、光線と、境界のそれぞれとの交点からの距離フィールドの値に基づく。
【００４５】
光線と、掃引されたボリュームの境界との交点は、掃引されたボリュームの距離フィールドのゼロ値、すなわちｄ（Ｒ（ｓ））＝０が結果として得られる値ｓによって特定される。交点を求める問題は、当該技術分野において既知の様々な解法を有する従来のルート発見問題（ｒｏｏｔ ｆｉｎｄｉｎｇ ｐｒｏｂｌｅｍ）として定式化することができる。本発明の１つの実施の形態は、交差を解析的に求める。別の実施の形態は、ニュートン法及び／又は挟み撃ち（ｒｅｇｕｌａ ｆａｌｓｉ）法等の反復手順を用いて、光線と掃引されたボリュームの境界との交点を求める。
【００４６】
図４Ｃは、当該技術分野において球投光（ｓｐｈｅｒｅ ｃａｓｔｉｎｇ）として知られる、光線・サーフェイス交差法を示している。光線４３０は、点４３１から発生し、解析的光線／平面交差によって容易に見つけることができる点４３２においてセルと交差する。点４３２において、掃引されたボリューム４３３への距離がこの掃引されたボリューム４３３の距離フィールドから求められ、４３４によって示される。新たな試験点４３５が、光線に沿って距離４３４だけ動かすことによって求められる。次に、プロセスは、距離４３６を計算し、次に新たな試験点４３７を計算し、次に更なる試験点を計算することによって、交点４３８が求められるまで反復的に繰り返される。
【００４７】
１つの実施の形態では、距離フィールドのサブセット５５１は、交点ｐにおける距離フィールドｉの値がｄｉ（ｐ）になるようにｉ∈［１，Ｎ］によってインデックス付けされたＮ個の距離フィールドを含む。このとき、点ｐは、ｉ＝ｊ∈［１，Ｎ］の特定の値についてｄｉ（ｐ）＝０であり、かつ全てのｉ≠ｊについてｄｉ（ｐ）＞０である場合にのみ複合サーフェイス４０６上にある。さらに、ｊは光線４０８によって示された複合サーフェイスを形成する距離フィールドのインデックスである。例えば、点４１３は複合サーフェイス上にあり、全ての他の点は複合サーフェイスの外側にある。なぜなら、境界と光線との各他の交点、すなわち点４１０〜４１２から境界４０５への距離、例えば距離４６０は、正であるためである。
【００４８】
したがって、本明細書に定義されるように、距離フィールドのサブセットからの距離フィールドは、距離フィールドの境界と光線との交点がセル内にあり、かつ交点とサブセット内の残りの掃引されたボリュームとの間の距離のセット内の各距離が正である場合、複合サーフェイスの一部分を形成する。境界を表す距離フィールドの値が交点において正である場合、距離は正である。
【００４９】
通常、セルは少なくとも１つの方向から光線のセットを当てられる。複合サーフェイスを形成する全ての境界を求めるために、光線のセット内の光線は互いに平行であり、かつ離間される。例えば、別の光線４１４は、点４１５から発生し、光線４０８に平行に伝播する。光線４１４は、点４１６においてのみ境界４０２と交差し、点４１６は、光線４１４によって示すように、複合サーフェイス上にある。したがって、異なる点から発生し、かつ／又は異なる方向に伝播する光線はそれぞれ、境界のうちのいずれが（存在する場合）複合サーフェイスを形成するかを求めることができる。
【００５０】
幾つかの例では、光線のサブセットは、複合サーフェイスの境界を示さない。例えば、光線４１７は、点４１８から発生し、点４２１、４２２、及び４２３において境界４０３、４０４、及び４０５と交差する。しかしながら、これらの交点の全てがセルの複合サーフェイスの外側にある。また、光線は、セルの外側の点（図示せず）において境界と交差する可能性がある。セルの外側の交点は、セルと関連付けられた複合サーフェイス上の有効な点ではない。
【００５１】
さらに、境界はセルと交差するが、複合サーフェイスを形成しない可能性がある。例えば、境界４０３は、工作物の元のサーフェイスの境界４０２と交差せず、複合サーフェイスを形成しない。境界４０４は、境界４０２と交差し、シミュレーションにおいて以前に複合サーフェイスの一部分を形成した可能性がある。しかしながら、図４Ｂに示す例の時点において、境界４０４は、セル内の複合サーフェイスの外側にある。したがって、境界４０２及び４０５のみがセルの距離フィールドの最適サブセット５５９の要素である。
【００５２】
距離フィールドの最適サブセットの決定
図５Ａは、本発明の１つの実施の形態を示している。機械加工命令５０１のセットが、ネットワークを介してファイルとして、ＣＤ若しくはＤＶＤから、又は当該技術分野において既知の他の手段によって、ＮＣ機械加工コントローラ５０２に提供される。コントローラ５０２は、プロセッサ５０３と、メモリ５０４と、機械の動作を示すディスプレイ５０５とを備える。フライス加工命令５０１を受信し、本発明の実施の形態５００を用いてディスプレイ５０５上にシミュレートされた工作物の画像５０７を生成する機械加工シミュレータ５０６がプロセッサ上で実行される。
【００５３】
図５Ｂは、セル４００と関連付けられた距離フィールドの最適サブセット５５９を決定する方法５００のブロック図である。距離フィールドのサブセット５５１及び光線のセット５５５が本方法への入力である。距離フィールドのサブセットは、セルと交差する掃引されたボリュームの境界を表す。本方法は当該技術分野において既知のプロセッサ５０３によって実施される。様々な実施の形態において、セル４００は異なる形状及び／又は寸法を有する。
【００５４】
例えば、上述した境界／セル交差法を用いて、距離フィールドのセットから距離フィールドのサブセットが選択される。１つの実施の形態では、境界／セル交差法は、セル内の掃引されたボリュームの境界のサーフェイス法線ベクトルのｘ成分、ｙ成分、及びｚ成分のそれぞれの絶対値の最大値を求める。
【００５５】
光線のセットからの各光線５５２は、起点及び伝播方向によって特定される。光線のセットは、光線がセル４００に入射するように決定される（５５４）。１つの実施の形態では、光線のセットは、サブセット５５１、セル内の境界の向き５５３の範囲に基づいて決定される。
【００５６】
本発明の様々な実施の形態が、異なる方法を用いて光線のセットを決定する。例えば、１つの実施の形態では、セットは、特定の方向における境界のサーフェイス法線の最大成分が閾値よりも大きい場合にのみ、その特定の方向から伝播した光線を含む。
【００５７】
実施の形態は、光線のセット内の光線５５２ごとに、上述した解析的方法及び／又は反復的方法を用いて、光線と境界５５１との間の交点のセット５７５を決定する（５７０）。光線と境界との交点５７６が複合サーフェイス上にあると判断された（５８０）場合、境界を表す距離フィールド５８５が最適サブセット５５９内で選択される（５９０）。光線のセット内の全ての光線が処理された後、距離フィールドの最適サブセット５５９が決定される。
【００５８】
光線のセットの決定
図６は、本発明の１つの実施の形態による、光線のセット５５５のサブセット６１１及び６２２を決定する一例を示している。光線のサブセット６１１は、セルの第１の境界６１０の外側の、正方形の等しく離間された格子の点から発生し、第１の境界に対し垂直にセルを通して伝播する。光線のセットの別のサブセット６２２は、第１の境界に対し垂直な、セルの第２の境界６２０の外側から発生し、第２の境界に対し垂直に伝播する。実施の形態の３Ｄ実施態様では、光線のセットの第３のサブセットは、最初の２つの境界に対し垂直な第３の境界の外側から発生し、第３の境界に対し垂直に伝播する。１つの実施の形態では、光線のそのような規則的なセットは最適サブセットを決定するのに十分である。
【００５９】
一方、他の実施の形態は、光線の規則的なセットを変更する。例えば、１つの実施の形態では、フラットエンドミル加工工具による１組の掃引は、同一の高さ及び工具の向きを用いてセルを通って移動し、それによってセル内の掃引されたボリュームの境界が互いに局所的に同一となる。この実施の形態では、最適サブセットを決定するのに単一の光線で十分である。
【００６０】
図７は、本発明の代替的な実施の形態を示している。この実施の形態では、光線７０１及び７０２が伝播され、境界７０４及び７０５が最適サブセット内にあると判断される。しかしながら、これもまた最適サブセットの一部である境界７０６が見逃され、不正確な複合サーフェイスが生成された。
【００６１】
光線の不完全なサブセットによって生じる複合サーフェイスの欠陥を回避するために、１つの実施の形態は、図５Ｂに示す適応プロセス５８０を含む。決定中（５８０）、適応プロセスは、光線によって実行される複合サーフェイスのサンプリングが、正確な最適サブセットを得るのに十分であるか否かを特定する。十分でない場合、より少ない光線又は更なる光線が伝播される。
【００６２】
例えば、光線７０１と境界７０４との交点７０７、及び光線７０２と境界７０５との交点７０８は境界７０６に近く、それによって点７０７及び７０８における境界７０４及び７０５のサーフェイスに対する法線が、境界７０４及び７０５が光線７０１と７０２との間の点７０９において境界７０６と交わることを示している。したがって、最適サブセットの正確度を改善するために、更なる光線７０３を伝播し、複合サーフェイスのサンプリングを増大させる。
【００６３】
キャッシング
本発明の１つの実施の形態は、セルの距離フィールドのサブセット５５１が変更されるたびに最適サブセットを決定する。例えば、フライス加工シミュレータは、フライス加工プログラム内の命令ごとに、工作物の複合サーフェイスの更新画像を生成する。画像のレンダリング時間を最小にするために、フライス加工命令によって生成された新たな距離フィールドによって変更されたＡＤＦのセルごとに、距離フィールドの最適サブセットを更新する必要がある。実施の形態の１つの変形形態は、データ、例えば交点５７５をメモリ５６１内にキャッシュし、方法５５０を高速化する。メモリ５６１は、ランダムアクセスメモリ（ＲＡＭ：ｒａｎｄｏｍ ａｃｃｅｓｓ ｍｅｍｏｒｙ）等、当該技術分野において既知の任意のメモリとすることができる。フライス加工命令ごとに最適サブセットが更新され、すなわち、距離フィールドが追加及び／若しくは除去されるか、又は最適サブセットは変更されないままである。
【００６４】
図８は、メモリとして割り当てられたコンピュータメモリのブロック８００の例を示している。ブロックはＭ個の等しいサイズのサブブロック８０１に分割され、これらのサブブロックは、それぞれ１つのセルに関するデータを格納することができる。各サブブロックは、Ｎ個のロケーション８０３に更に分割される。各ロケーションは、１つの光線と関連付けられる。例えば、データは、光線と複合サーフェイスとの交点、及びその境界が光線において複合サーフェイスを形成する距離フィールドを一意に特定する数である。複合サーフェイスが存在しない光線の場合、フラグ値、例えば数−１が距離フィールド識別子の代わりに格納される。
【００６５】
各サブブロックは、サブブロックＩＤ８０４と関連付けられる。サブブロックＩＤ８０４は、そのデータが現在サブブロック内に格納されているセルの識別子として機能する。例えば、１つの実施の形態では、工作物内のセルの位置のｘ座標、ｙ座標、及びｚ座標の組合せから一意のセル識別子数が形成される。
【００６６】
図９は、メモリを用いて最適サブセットを決定する方法９００の流れ図である。セル識別子９０１が形成される。ハッシュ関数が、大きな範囲から、キャッシュサブブロック数に対応する［０，Ｍ−１］の所望の範囲にセル識別子をマッピングする（９０２）。ハッシュ関数の例はｏｕｔ（ｋ）＝ｋ ｍｏｄｕｌｏ Ｍであり、入力セル識別子値ｋを、モジュロ数学関数を用いて所望の範囲内の出力値ｏｕｔにマッピングする。ハッシュ関数からの出力値を、セルに関するデータを格納するキャッシュサブブロックのアドレスとして用いる（９０３）。
【００６７】
サブブロックが正確なセルに関するデータを格納していることを確かめるために、キャッシュからサブブロックＩＤが取り出され（９０４）、セル識別子と比較される（９０５）。識別子が一致しない場合、サブブロックは、現在のセルによって用いるためにクリアされ、セル識別子を用いてサブブロックＩＤが書き込まれる（９０６）。最適サブセットの決定（９０７）は、上述したように非キャッシュ式で進み、各光線に関するデータ９０８がキャッシュに格納され（９０９）、最適サブセット９１０を更新するために用いられる。
【００６８】
代替的に、値が一致するとき、サブブロック内のデータは最適サブセットを決定するのに用いられる。このため、方法９００は全ての光線にわたって反復する（９１１）。光線ごとに、交点は新たな距離フィールドについてのみ計算され（９１２）、交点の点を用いて、この光線について複合サーフェイスを形成する距離フィールド境界を決定する（９１３）。
【００６９】
図１０は、セル内に光線と新たな距離フィールドとの交差が存在するか否か、及びキャッシュ内にその光線に関するデータが存在するか否か、すなわち距離フィールド識別子が≠−１であるか否かに応じた、決定（９１３）の４つの可能な結果を示している。
【００７０】
交差及びキャッシュデータが存在しない場合、光線から何もわからないので、図１１Ａ〜図１１Ｃは、３つの上述した事例の例を示している。
【００７１】
図１１Ａにおいて、距離フィールド１１０２、１１０３、及び１１０４がセル１１０１と現在関連付けられており、距離フィールド１１０５は新たな距離フィールドである。光線１１０６は、点１１０７において距離フィールド１１０５の境界と交差し、キャッシュは光線１１０６に関するデータを含まない。したがって、交点１１０７において、現在セル内にある距離フィールド１１０２〜１１０４のサブセットの距離フィールド値が計算される。
【００７２】
交点における距離フィールドの値が全て正である、すなわち０より大きい場合、新たな距離フィールドは、この光線について複合サーフェイスを形成し、最適サブセットに追加される。図１１Ａに示す例において、距離フィールド値は全て負であり、距離フィールド１１０５は、最適サブセットに追加されない。
【００７３】
図１１Ｂにおいて、距離フィールド１１２２〜１１２４が現在セル１１２１に関連付けられており、距離フィールド１１２５は新たな距離フィールドである。光線１１２６は、セル内の距離フィールド１１２５の境界と交差しないが、キャッシュは、光線１１２６と距離フィールド１１２３の境界との交点１１２７を含む。この場合、交差は存在しないが、キャッシュは光線の有効なデータを含み、次に、キャッシュされた交点において新たな距離フィールドの値が求められる。
【００７４】
値が正である場合、キャッシュされた距離フィールドが最適サブセットに追加される。例示した例において、交点１１２７は距離フィールド１１２５の外側にあり、キャッシュされた距離フィールドが、光線１１２６に起因して最適サブセットに追加されることがないことを意味する。これは、距離フィールド１１２６が別の光線に起因して最適サブセットに追加される可能性を排除しないことを理解することが重要である。
【００７５】
最後に、図１１Ｃにおいて、距離フィールド１１３２〜１１３４が現在セル１１３１と関連付けられており、距離フィールド１１３５は新たな距離フィールドである。光線１１３６は点１１３８において距離フィールド１１３５の境界と交差し、キャッシュは、光線１１３６と距離フィールド１１３３の境界との交点１１３７を含む。この場合、交点が存在し、かつ有効なキャッシュされたデータが存在し、次に、新たな交点１１３８においてキャッシュされた距離フィールド１１３３の値が計算される。
【００７６】
値が正である場合、新たな距離フィールド１１３５が最適サブセットに追加される。そうでない場合、キャッシュされた距離フィールド１１３３が最適サブセットに追加される。この例では、交点１１３８は距離フィールド１１３３の境界内にあり（すなわちｄ＞０）、このため、距離フィールド１１３５が最適サブセットに追加される。
【００７７】
全ての光線が処理された後、各光線に関するデータがキャッシュに書き込まれ、最適サブセット９１０が完成する。
【００７８】
本発明を、好ましい実施の形態の例として説明してきたが、本発明の趣旨及び範囲内で他のさまざまな適合及び変更を行えることが理解されるべきである。したがって、本発明の真の趣旨及び範囲内に入る全ての変形及び変更を包含することが、添付の特許請求の範囲の目的である。
【技術分野】
【０００１】
本発明は、包括的には機械加工シミュレーションに関し、より詳細には、距離フィールドの最適サブセットを決定して機械加工プロセスのシミュレーションを最適化することに関する。
【背景技術】
【０００２】
数値制御フライス加工
数値制御（ＮＣ：ｎｕｍｅｒｉｃａｌｌｙ ｃｏｎｔｒｏｌｌｅｄ）機械加工（例えばフライス加工又は施削）のプロセスをシミュレートすることは、コンピュータコンピュータ支援設計（ＣＡＤ：ｃｏｍｐｕｔｅｒ ａｉｄｅｄ ｄｅｓｉｇｎ）及びコンピュータ支援製造（ＣＡＭ：ｃｏｍｐｕｔｅｒ ａｉｄｅｄ ｍａｎｕｆａｃｔｕｒｉｎｇ）において根本的に重要である。シミュレーション中に、工作物のコンピュータモデルが、工具、例えば、ＮＣフライス加工工具のコンピュータ表現及び１組の工具運動を用いて編集され、機械加工プロセスがシミュレートされる。
【０００３】
シミュレーションは、工作物と工具保持器との間等の部品間の可能性のある衝突を検出し、工作物の最終形状を検証するために、工作物のモデル及び工具の表現を視覚化する。
【０００４】
工作物の最終的な形状は、工具及び工具運動の選択によって影響を及ぼされる。これらの運動を制御するための命令が通常は、コンピュータ支援製造システムを用いて、工作物の所望の最終的な形状のグラフィック表現から生成される。それらの運動は通常、準備コード（ｐｒｅｐａｒａｔｏｒｙ ｃｏｄｅ）又はＧコードとしても知られている、数値制御プログラミング言語を用いて実現される。以下の標準規格ＲＳ２７４Ｄ及びＤＩＮ ６６０２５／ＩＳＯ ６９８３を参照されたい。
【０００５】
コンピュータ支援製造システムによって生成されるＧコードは、所望の最終的な形状の正確な複製物を製造しない場合がある。さらに、ＮＣ工具の動きは、機械加工システムのモータによって支配されるが、その速度、運動範囲、並びに加速及び減速能力は限られているため、実際の工具運動は、ＮＣ機械加工命令に厳密には従わない場合がある。
【０００６】
工作物の実際の最終的な形状と、工作物の所望の最終的な形状との間の不一致は極めて小さい場合があり、見ることが難しい。状況によっては、これらの不一致の結果として、工作物の最終的な形状の表面に、サイズがほぼ数マイクロメートル程度の深さ及び幅、ほぼ数十マイクロメートル程度の長さにわたる望ましくない溝状の傷（ｇｏｕｇｅ）又は欠け目（ｎｉｃｋ）が生じる。
【０００７】
通常、所望の部品を機械加工する前に、より軟質で安価な材料から形成される試験工作物をフライス加工することによって、ＮＣ機械加工命令のセットが試験される。その試験工作物の外観検査によって、試験工作物において望ましくない不一致が見つかった場合には、それに応じて、ＮＣ機械加工命令が変更される。
【０００８】
しかしながら、この手動試験は、時間及びコストがかかる。単一の試験工作物を機械加工するための時間は、ほぼ数時間程度かかる場合があり、許容できるＮＣ機械加工命令のセットが得られるまでに、何度か繰り返すことが必要な場合がある。したがって、コンピュータを利用したシミュレーション及びレンダリングを用いて、これらの不一致を試験することが望ましい。コンピュータに基づくシミュレーションの例は、参照により本明細書に援用される、米国特許出願第１２／４９５，５８８号及び同第１２／４６８，６０７号に記載されている。
【０００９】
工具
図２Ａは、ＮＣフライス加工において用いられる１組の通常の工具２０２、２０４、２０６、及び２０８を示している。工具が工作物２１０に対して動かされるとき、工具は工作物から材料を削り取る。ここで、工具２０２、２０４、２０６、及び２０８は、一般に「掃引されたボリューム（ｓｗｅｐｔ ｖｏｌｕｍｅ）」と呼ばれる、サーフェイス２１２、２１４、２１６、及び２１８に対応する材料を工作物から除去する。各工具によって除去される材料の形状は、工具の形状と、工作物に対する工具の経路とによって決まる。
【００１０】
掃引されたボリューム
機械加工中に、工具の支持された運動、すなわち工具経路に従って、工具が工作物に対して動き、工具経路は工作物に対する工具の相対的な位置、向き及び他の形状データについての情報を含むことができる。
【００１１】
工具が工具経路に沿って動くとき、工具は「掃引されたボリューム」を切り出す。機械加工中に、工具が工具経路に沿って動くとき、掃引されたボリュームによって横切られる工作物の部分が除去される。この材料除去は、コンピュータにおいて、空間領域構成法（ＣＳＧ：ｃｏｎｓｔｒｕｃｔｉｖｅ ｓｏｌｉｄ ｇｅｏｍｅｔｒｙ）差分演算としてモデル化することができ、その演算によれば、工作物からの掃引されたボリュームのＣＳＧ減算演算を用いて、工作物のその部分が工作物から除去される。
【００１２】
図２Ｂは、経路２５２に沿って動かされた形状２５０の掃引されたボリューム２６０を示している。経路２５２は、形状２５０の特定の点の位置を時間の関数として指定する。経路は、形状の向き２５６、２５７、及び２５８を時間の関数として指定することができる。経路は、形状のスケール又は形状の任意の変換を時間の関数として指定することもできる。図２Ｂにおいて、形状２５０の元の位置、向き、及びジオメトリは、経路に沿って動くにつれ、形状２５４の最終的な位置、向き、及びジオメトリに変換される。
【００１３】
図３Ａは、工具３０２が直線３０４に沿って動かされる線形経路を示している。
【００１４】
図３Ｂは、工具３０２の先端３１０が円弧３１２に沿って動かされる円弧経路を示しており、工具の元の軸方向３１４が経路の端部で最終軸方向３１６に変換される。
【００１５】
図３Ｃは、工具３０２の先端３１０が曲線３２０に沿って動かされる曲線経路を示している。
【００１６】
他の可能な経路形式は、ほんの数例を挙げると、工具を或る点に位置決めすること、工具をポリラインとして知られる連続した線に沿って動かすこと、工具を渦巻き状又はらせん状の曲線に沿って動かすこと、工具を二次ベジエ曲線若しくは三次ベジエ曲線等の多項式曲線、又は区分的多項式曲線として知られる連続した多項式曲線に沿って動かすことを含む。工作物の形状又は材料組成によって影響を受ける経路等の、手順によって規定される経路を含む、シミュレートすることができる任意の形式の経路を検討することができる。
【００１７】
距離フィールド
オブジェクトの距離フィールドｄ（ｐ）はスカラフィールドであり、空間内の点ｐにおけるｄ（ｐ）の値は点ｐからオブジェクトのサーフェイスまでの距離である。従来技術において多くの可能な距離フィールドが知られているが、最も一般的で有用であるのは、ユークリッド距離フィールドである。ユークリッド距離フィールドでは、距離はオブジェクトのサーフェイスに対する最小距離であり、ｄ（ｐｓ）＝０として定義される。
【００１８】
加えて、距離フィールドは、オブジェクトの外側を内側と区別するために符号を付され、例えば内側はｄ（ｐ）＞０であり、外側はｄ（ｐ）＜０である。また、ｐにおける距離フィールドの勾配ベクトルは最小距離の方向を指し、オブジェクトのサーフェイスにおいて、正規化された勾配ベクトルはサーフェイスの法線ベクトルに等しい。参照により本明細書に援用される、米国特許第６，３９６，４９２号、同第６，７２４，３９３号、同第６，８２６，０２４号、及び同第７，０４２，４５８号に記載されているように、距離フィールドは陰関数の形式をとり、形状をレンダリング及び編集するための効果的な表現である。
【００１９】
適応的にサンプリングされる距離フィールド（ＡＤＦ：ａｄａｐｔｉｖｅｌｙ ｓａｍｐｌｅｄ ｄｉｓｔａｎｃｅ ｆｉｅｌｄｓ）は、ディテール指向サンプリング（ｄｅｔａｉｌ−ｄｉｒｅｃｔｅｄ ｓａｍｐｌｉｎｇ）を用いて、距離フィールドの空間及び時間的に効率の良い表現を提供する。ＡＤＦは、複数のセルからなる空間的な階層内に距離フィールドを格納する。各セルは、距離データと、そのセルに関連する距離フィールドの部分を再構成するための再構成法とを含む。距離データは、距離フィールドの値と、距離フィールドの勾配及び偏導関数とを含むことができる。メモリ要件及び計算要件を削減するために、セル内の距離フィールドは、必要とされるときに再構成することができる。
【００２０】
ＣＳＧ演算を用いてフライス加工をシミュレートするために、ＡＤＦを用いることができる。フライス加工される工作物及びフライス加工工具は、ＡＤＦとして表すことができる。シミュレートされるフライス加工プロセスは、例えば工作物のＡＤＦを変更することにより、シミュレートされる工作物のＡＤＦを明示的に生成することができる。代替的には、シミュレートされる工作物は、複合ＡＤＦとして暗黙的に表すことができる。複合ＡＤＦは、工作物の距離フィールド及びフライス加工工具と、フライス加工工具のためのＣＳＧ減算演算子のような、距離フィールドに対応する演算子と、格納された距離フィールドをレンダリング又は他の処理中に要求に応じて合成する距離フィールド再構成法とを格納する。
【００２１】
フライス加工工具は、工具距離フィールドによって表すことができる。工具経路は、パラメータ関数によって表すことができる。掃引されたボリュームの距離フィールドは、フライス加工工具を経路に沿って動かすことによって生成される掃引されたボリュームを表すように定義され、ここで掃引されたボリュームの距離フィールドは、掃引されたボリュームの再構成方法に従って連続して定義される。掃引されたボリュームの再構成方法は、サンプル点において掃引されたボリュームの距離フィールドを再構成することができる。
【００２２】
特に関心のあるサンプル点の例は、距離フィールドｄの値がゼロに等しい、すなわちｄ＝０である、任意のオブジェクトの距離フィールドの等値面（ｉｓｏｓｕｒｆａｃｅ）上の点である。本明細書において述べられるように、オブジェクトの距離フィールドのゼロ値等値面は、オブジェクトの境界、例えば工作物の境界であるか、又は掃引されたボリュームの境界である。
【００２３】
図１Ａはセル、例えば１０１、１０２、及び１０３のセルの空間階層からなる複合ＡＤＦ１００の２Ｄの図であり、工作物のボリュームの一部分及び距離フィールドを表し、それらの境界が示されている。この例では、距離フィールド１０４〜１０７は、初期工作物の境界を定義した平面である。距離フィールド１０８〜１１０は、ボールエンドミル工具の掃引を表す３つの距離フィールドである。複合ＡＤＦの各セルは、元の工作物及びフライス加工工具の掃引されたボリュームを表す距離フィールドのセットのサブセットと関連付けられる。例えば、セル１１１と関連付けられるのは距離フィールド１０４、１０８、及び１０９であり、これらの距離フィールドは、合わせてセル１１１内の複合サーフェイスを画定する。距離フィールドのセットのサブセットを組み合わせて工作物の複合距離フィールドを再構成するために、ＣＳＧ差等の手続き的再構成方法もセルと関連付けられる。複合サーフェイスは、元の工作物距離フィールド及び掃引された工具距離フィールドの境界のパッチからなる、工作物のシミュレートされた境界となるように定義される。
【００２４】
セルと関連付けられた距離フィールドのサブセットは、複数の方法によって選択することができる。例えば、サブセットは、セルの中心から境界への距離の絶対値が、セルを完全に取り囲む球の直径よりも小さい距離フィールドのみに限定することができる。代替的に、サブセットは、境界の少なくとも一部分がセルと交差するこの境界を有する掃引されたボリュームを表す距離フィールドのみに制限することができる。これらの距離フィールドは、例えば、距離フィールドがゼロに等しいセル内の点を、境界／セル交差試験を用いて検索することによって決定することができる。
【００２５】
セルと関連付けられた距離フィールドのセットのサブセットが、セル内で複合サーフェイスを実際に形成して、幾何演算、例えばレンダリング中に処理されなくてはならない距離フィールド数を最小にすることによって、シミュレータ性能を最大にする距離フィールドのみを含むことが望ましい。不都合なことに、セルの距離フィールドのサブセットを決定する上述した方法は、結果としてのシミュレータ性能が悪い可能性がある。なぜなら、これらの方法によって見つかるサブセットの複数の距離フィールドは、セルには入るが工作物境界の一部分を形成しない掃引されたボリュームを表す可能性があるためである。
【００２６】
図１Ｂは、工作物の一部分の従来の表現の一例を示している。工作物を表す複合ＡＤＦは、セルのセット、例えばセル１０１と、掃引されたボリューム１１０等の、工具の掃引されたボリュームを表す距離フィールド１０２〜１０５のセットとを含む。工作物１０７の一部分は、セル１０１と、掃引されたボリュームの距離フィールド１０３〜１０５のサブセットとによって表される。掃引されたボリュームの距離フィールド１０２は、セルの境界と交差しないので、この距離フィールドは通常、サブセットに含まれない。しかしながら、この例において見てとることができるように、掃引されたボリュームの距離フィールド１０３及び１０４は、工作物の境界の一部分を形成せず、このため、これらもサブセットに含まれるべきではない。
【００２７】
特定の例として、４００ミクロンの辺寸法を有する、ｘ軸、ｙ軸、及びｚ軸に位置合わせされた立方体セルと、ｘ、ｙ平面においてｘ軸に平行な平行掃引で動く半径２ｍｍの球状の工具とを考える。ここで、掃引間は５０ミクロンだけ隔てられ、工具の高さは、工具の最小点がセルの底辺の極めて僅かに上にあるようになっている。このとき、５６個の工具掃引ボリュームがセル内に境界を有するが、これらの掃引ボリュームのうちの９個のみが工作物の境界を形成する。
【００２８】
したがって、フライス加工プロセスのシミュレーションの性能を最適化するために、セルと関連付けられた距離フィールドのサブセットを最適化する必要がある。
【発明の概要】
【発明が解決しようとする課題】
【００２９】
本発明の目的は、フライス加工プロセスのシミュレーションの性能を最適化することである。
【００３０】
本発明の更なる目的は、工作物及び掃引されたボリュームを表す距離フィールドのサブセットを最適化することである。
【課題を解決するための手段】
【００３１】
本発明の様々な実施の形態において、工作物及び掃引されたボリュームは、距離フィールドを用いて表される。セルと交差する境界を表す距離フィールドを最初に含む距離フィールドのサブセットがセルと関連付けられる。本発明の実施の形態は、サブセットを最適化して、工作物の複合サーフェイスを形成する境界を表す距離フィールドを含む最適サブセットを形成する。
【００３２】
実施の形態は、セル内の工作物の、この工作物から掃引されたボリュームを除去することによって形成された複合サーフェイスが、セル及び／又は複合サーフェイスに入射する光線を当てられた場合、これらの光線と、掃引されたボリューム及び複合サーフェイスの境界との交点は、実際に複合サーフェイスを形成した掃引ボリュームを示すという認識に基づいている。
【００３３】
本発明の１つの実施の形態は、工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される工作物のフライス加工のシミュレーションを最適化する方法であって、ボリュームはセルのセットに分割され、この方法は、各セルに、このセルと交差する距離フィールド境界のサブセットを表す距離フィールドのサブセットを関連付けるステップであって、境界のサブセットの少なくとも一部はセル内で工作物の複合サーフェイスを形成する、関連付けるステップと、セルに、少なくとも１つの方向からこのセルに入射する光線のセットを当てるステップであって、各光線は直線の伝播を表す、当てるステップと、距離フィールドのサブセットの或る距離フィールドを選択して、セルと関連付けられた最適サブセットに含めるステップであって、距離フィールドによって表される掃引されたボリュームの境界は、複合サーフェイス上に位置する交点において少なくとも１つの光線と交差する、選択して含めるステップと、を含み、この方法のステップは、プロセッサによって実行される、工作物のボリュームから掃引されたボリュームのセットを除去することによって実施される工作物のフライス加工のシミュレーションを最適化する方法を開示する。
【００３４】
別の実施の形態は、工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される工作物のフライス加工のシミュレーションを最適化する方法であって、ボリュームはセルのセットに分割され、各セルには、このセルと交差する掃引されたボリュームのサブセットが関連付けられ、掃引されたボリュームのサブセットの少なくとも一部がセルの複合サーフェイスを形成するようにされ、この方法は、セルに、このセルに入射する光線のセットを当てるステップであって、光線はこのセルに向かう直線の伝播を表す、当てるステップと、掃引されたボリュームのサブセットの或る掃引されたボリュームを選択して、セルと関連付けられた最適サブセットに含めるステップであって、掃引されたボリュームの境界は、複合サーフェイス上に位置する交点において少なくとも１つの光線と交差する、選択して含めるステップと、を含む、工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される工作物のフライス加工のシミュレーションを最適化する方法を開示する。
【００３５】
更に別の実施の形態は、工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される工作物のフライス加工のシミュレーションを最適化するシステムであって、ボリュームはセルのセットに分割され、このシステムは、各セルに、このセルと交差する掃引されたボリュームのサブセットを表す距離フィールドのサブセットを関連付ける手段であって、掃引されたボリュームのサブセットの少なくとも一部はセルの複合サーフェイスを形成する、関連付ける手段と、セルに、少なくとも１つの方向からこのセルに入射する光線のセットを当てる手段であって、各光線は直線の伝播を表す、当てる手段と、距離フィールドのサブセットの或る距離フィールドを選択して、セルと関連付けられた最適サブセットに含めるように構成されたプロセッサであって、距離フィールドによって表される掃引されたボリュームの境界は、複合サーフェイス上に位置する交点において少なくとも１つの光線と交差する、プロセッサと、を備える、工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される前記工作物のフライス加工のシミュレーションを最適化するシステムを開示する。
【図面の簡単な説明】
【００３６】
【図１Ａ】機械加工された工作物を表す複合ＡＤＦの概略図である。
【図１Ｂ】工作物の一部分の従来の表現の一例の概略図である。
【図２Ａ】フライス加工に用いられる工具、及びこの工具を経路に沿って動かすことによって工作物から除去された掃引されたボリュームの概略図である。
【図２Ｂ】曲線経路に沿って２Ｄ経路を掃引することによって求められた、掃引されたボリュームの概略図である。
【図３Ａ】フライス加工工具の異なる経路の概略図である。
【図３Ｂ】フライス加工工具の異なる経路の概略図である。
【図３Ｃ】フライス加工工具の異なる経路の概略図である。
【図４Ａ】本発明の実施の形態による、工作物境界を形成する複数の境界を有するセルの２Ｄ概略図である。
【図４Ｂ】本発明の実施の形態による、光線とセル内の境界との交差を示す２Ｄ概略図である。
【図４Ｃ】本発明の実施の形態による、光線とセル内の境界との交差を示す２Ｄ概略図である。
【図５Ａ】産業環境における本発明の実施の形態の概略図である。
【図５Ｂ】本発明の実施の形態による、フライス加工工作物の複合サーフェイスを正確に表すのに必要な掃引された工具の境界の最小リストを決定する方法の流れ図である。
【図６】本発明の実施の形態による、規則的に離間されたグリッド上の光線のセットを示す２Ｄ概略図である。
【図７】本発明の実施の形態による、光線のセットを決定する方法を示す２Ｄ概略図である。
【図８】本発明の実施の形態によるコンピュータメモリの構成の一例である。
【図９】メモリを用いて最適サブセットを決定する方法９００の流れ図である。
【図１０】本発明の実施の形態による複合サーフェイスを形成する境界を表す距離フィールドを求めた結果の例である。
【図１１Ａ】本発明の実施の形態による複合サーフェイスを形成する境界を表す距離フィールドを求めた結果の例である。
【図１１Ｂ】本発明の実施の形態による複合サーフェイスを形成する境界を表す距離フィールドを求めた結果の例である。
【図１１Ｃ】本発明の実施の形態による複合サーフェイスを形成する境界を表す距離フィールドを求めた結果の例である。
【発明を実施するための形態】
【００３７】
システム概観
図４Ａは、本発明の実施の形態によって対処される問題を示している。セル４００内で、境界４０２は工作物のフライス加工のシミュレーションの開始時の工作物４０１の元のサーフェイスを定義している。シミュレーション中、３つの掃引されたボリュームの境界４０３、４０４、及び４０５がセルと交差する。したがって、掃引されたボリュームは、セルによって表される工作物のボリュームから除去される。工作物の内部４０７を取り囲む工作物の複合サーフェイス４０６は、境界４０２及び境界４０５によって形成される。
【００３８】
本発明の様々な実施の形態では、工作物及び掃引されたボリュームは、距離フィールドを用いて表される。セルは、このセルと交差する境界４０２〜４０５を表す距離フィールドを最初に含む距離フィールドのサブセット５５１と関連付けられる（４５０）。本発明の実施の形態は、サブセットを最適化して（５００）、工作物の複合サーフェイスを形成する境界、例えば境界４０２及び４０５を表す距離フィールドを含む最適サブセット５５９を形成する。
【００３９】
境界は、距離フィールドのゼロ値等値面によって定義される。
【００４０】
加えて、共通符号規約の下では、距離フィールドは、掃引されたボリューム内で正であり、境界においてゼロであり、外側で負である。一方、フライス加工プロセスのシミュレーションにおいて、掃引されたボリュームと交差する工作物サーフェイスのいかなる部分も除去されているので、掃引されたボリュームの内部は、工作物の複合サーフェイスの外部にある。したがって、本発明の実施の形態は、掃引されたボリュームを表す距離フィールドをネゲートする、すなわちこの距離フィールドに−１を乗算する。
【００４１】
したがって、元のサーフェイスの境界４０２及び掃引されたボリュームの境界４０５は、セルの最適サブセットを形成し、工作物の内部を取り囲む。ここで、工作物の複合距離フィールドはゼロより大きいあらゆるところにある。境界４０３及び４０４は複合サーフェイスの外側にあり、すなわち、セル内のこれらの境界上のすべての点が工作物の複合サーフェイスに対し負の距離を有する。
【００４２】
光線
本発明の実施の形態は、セルによって表され、工作物から掃引されたボリュームを除去することによって形成されたこの工作物の複合サーフェイスが、セル及び／又は複合サーフェイスに入射する光線を当てられた場合、これらの光線と、掃引されたボリューム及び複合サーフェイスの境界との交点が、複合サーフェイスを実際に形成した掃引されたボリュームを示すという認識に基づく。
【００４３】
光線は、直線と同一の数学的構造である。光線は、３Ｄ空間内の原点Ｒ０から発生し、ベクトルＲｄによって与えられた方向に直線で伝播する。光線の伝播は、３Ｄ空間内の光線の位置がＲ（ｓ）＝Ｒ０＋Ｒｄｓによって定義されるように、時間のような座標（ｔｉｍｅ−ｌｉｋｅ ｃｏｏｒｄｉｎａｔｅ）ｓによってパラメータ化することができる。
【００４４】
図４Ｂは、光線と、掃引されたボリュームの境界との交差の２次元（２Ｄ）の図を示している。例えば、光線４０８は、点４０９から発生し、直線で伝播し、点４１０、４１２、及び４１３において、掃引されたボリュームの境界と交差し、点４１１において元のサーフェイスの境界と交差する。光線のいずれの交点が複合サーフェイス上にあるかを求めることは、光線と、境界のそれぞれとの交点からの距離フィールドの値に基づく。
【００４５】
光線と、掃引されたボリュームの境界との交点は、掃引されたボリュームの距離フィールドのゼロ値、すなわちｄ（Ｒ（ｓ））＝０が結果として得られる値ｓによって特定される。交点を求める問題は、当該技術分野において既知の様々な解法を有する従来のルート発見問題（ｒｏｏｔ ｆｉｎｄｉｎｇ ｐｒｏｂｌｅｍ）として定式化することができる。本発明の１つの実施の形態は、交差を解析的に求める。別の実施の形態は、ニュートン法及び／又は挟み撃ち（ｒｅｇｕｌａ ｆａｌｓｉ）法等の反復手順を用いて、光線と掃引されたボリュームの境界との交点を求める。
【００４６】
図４Ｃは、当該技術分野において球投光（ｓｐｈｅｒｅ ｃａｓｔｉｎｇ）として知られる、光線・サーフェイス交差法を示している。光線４３０は、点４３１から発生し、解析的光線／平面交差によって容易に見つけることができる点４３２においてセルと交差する。点４３２において、掃引されたボリューム４３３への距離がこの掃引されたボリューム４３３の距離フィールドから求められ、４３４によって示される。新たな試験点４３５が、光線に沿って距離４３４だけ動かすことによって求められる。次に、プロセスは、距離４３６を計算し、次に新たな試験点４３７を計算し、次に更なる試験点を計算することによって、交点４３８が求められるまで反復的に繰り返される。
【００４７】
１つの実施の形態では、距離フィールドのサブセット５５１は、交点ｐにおける距離フィールドｉの値がｄｉ（ｐ）になるようにｉ∈［１，Ｎ］によってインデックス付けされたＮ個の距離フィールドを含む。このとき、点ｐは、ｉ＝ｊ∈［１，Ｎ］の特定の値についてｄｉ（ｐ）＝０であり、かつ全てのｉ≠ｊについてｄｉ（ｐ）＞０である場合にのみ複合サーフェイス４０６上にある。さらに、ｊは光線４０８によって示された複合サーフェイスを形成する距離フィールドのインデックスである。例えば、点４１３は複合サーフェイス上にあり、全ての他の点は複合サーフェイスの外側にある。なぜなら、境界と光線との各他の交点、すなわち点４１０〜４１２から境界４０５への距離、例えば距離４６０は、正であるためである。
【００４８】
したがって、本明細書に定義されるように、距離フィールドのサブセットからの距離フィールドは、距離フィールドの境界と光線との交点がセル内にあり、かつ交点とサブセット内の残りの掃引されたボリュームとの間の距離のセット内の各距離が正である場合、複合サーフェイスの一部分を形成する。境界を表す距離フィールドの値が交点において正である場合、距離は正である。
【００４９】
通常、セルは少なくとも１つの方向から光線のセットを当てられる。複合サーフェイスを形成する全ての境界を求めるために、光線のセット内の光線は互いに平行であり、かつ離間される。例えば、別の光線４１４は、点４１５から発生し、光線４０８に平行に伝播する。光線４１４は、点４１６においてのみ境界４０２と交差し、点４１６は、光線４１４によって示すように、複合サーフェイス上にある。したがって、異なる点から発生し、かつ／又は異なる方向に伝播する光線はそれぞれ、境界のうちのいずれが（存在する場合）複合サーフェイスを形成するかを求めることができる。
【００５０】
幾つかの例では、光線のサブセットは、複合サーフェイスの境界を示さない。例えば、光線４１７は、点４１８から発生し、点４２１、４２２、及び４２３において境界４０３、４０４、及び４０５と交差する。しかしながら、これらの交点の全てがセルの複合サーフェイスの外側にある。また、光線は、セルの外側の点（図示せず）において境界と交差する可能性がある。セルの外側の交点は、セルと関連付けられた複合サーフェイス上の有効な点ではない。
【００５１】
さらに、境界はセルと交差するが、複合サーフェイスを形成しない可能性がある。例えば、境界４０３は、工作物の元のサーフェイスの境界４０２と交差せず、複合サーフェイスを形成しない。境界４０４は、境界４０２と交差し、シミュレーションにおいて以前に複合サーフェイスの一部分を形成した可能性がある。しかしながら、図４Ｂに示す例の時点において、境界４０４は、セル内の複合サーフェイスの外側にある。したがって、境界４０２及び４０５のみがセルの距離フィールドの最適サブセット５５９の要素である。
【００５２】
距離フィールドの最適サブセットの決定
図５Ａは、本発明の１つの実施の形態を示している。機械加工命令５０１のセットが、ネットワークを介してファイルとして、ＣＤ若しくはＤＶＤから、又は当該技術分野において既知の他の手段によって、ＮＣ機械加工コントローラ５０２に提供される。コントローラ５０２は、プロセッサ５０３と、メモリ５０４と、機械の動作を示すディスプレイ５０５とを備える。フライス加工命令５０１を受信し、本発明の実施の形態５００を用いてディスプレイ５０５上にシミュレートされた工作物の画像５０７を生成する機械加工シミュレータ５０６がプロセッサ上で実行される。
【００５３】
図５Ｂは、セル４００と関連付けられた距離フィールドの最適サブセット５５９を決定する方法５００のブロック図である。距離フィールドのサブセット５５１及び光線のセット５５５が本方法への入力である。距離フィールドのサブセットは、セルと交差する掃引されたボリュームの境界を表す。本方法は当該技術分野において既知のプロセッサ５０３によって実施される。様々な実施の形態において、セル４００は異なる形状及び／又は寸法を有する。
【００５４】
例えば、上述した境界／セル交差法を用いて、距離フィールドのセットから距離フィールドのサブセットが選択される。１つの実施の形態では、境界／セル交差法は、セル内の掃引されたボリュームの境界のサーフェイス法線ベクトルのｘ成分、ｙ成分、及びｚ成分のそれぞれの絶対値の最大値を求める。
【００５５】
光線のセットからの各光線５５２は、起点及び伝播方向によって特定される。光線のセットは、光線がセル４００に入射するように決定される（５５４）。１つの実施の形態では、光線のセットは、サブセット５５１、セル内の境界の向き５５３の範囲に基づいて決定される。
【００５６】
本発明の様々な実施の形態が、異なる方法を用いて光線のセットを決定する。例えば、１つの実施の形態では、セットは、特定の方向における境界のサーフェイス法線の最大成分が閾値よりも大きい場合にのみ、その特定の方向から伝播した光線を含む。
【００５７】
実施の形態は、光線のセット内の光線５５２ごとに、上述した解析的方法及び／又は反復的方法を用いて、光線と境界５５１との間の交点のセット５７５を決定する（５７０）。光線と境界との交点５７６が複合サーフェイス上にあると判断された（５８０）場合、境界を表す距離フィールド５８５が最適サブセット５５９内で選択される（５９０）。光線のセット内の全ての光線が処理された後、距離フィールドの最適サブセット５５９が決定される。
【００５８】
光線のセットの決定
図６は、本発明の１つの実施の形態による、光線のセット５５５のサブセット６１１及び６２２を決定する一例を示している。光線のサブセット６１１は、セルの第１の境界６１０の外側の、正方形の等しく離間された格子の点から発生し、第１の境界に対し垂直にセルを通して伝播する。光線のセットの別のサブセット６２２は、第１の境界に対し垂直な、セルの第２の境界６２０の外側から発生し、第２の境界に対し垂直に伝播する。実施の形態の３Ｄ実施態様では、光線のセットの第３のサブセットは、最初の２つの境界に対し垂直な第３の境界の外側から発生し、第３の境界に対し垂直に伝播する。１つの実施の形態では、光線のそのような規則的なセットは最適サブセットを決定するのに十分である。
【００５９】
一方、他の実施の形態は、光線の規則的なセットを変更する。例えば、１つの実施の形態では、フラットエンドミル加工工具による１組の掃引は、同一の高さ及び工具の向きを用いてセルを通って移動し、それによってセル内の掃引されたボリュームの境界が互いに局所的に同一となる。この実施の形態では、最適サブセットを決定するのに単一の光線で十分である。
【００６０】
図７は、本発明の代替的な実施の形態を示している。この実施の形態では、光線７０１及び７０２が伝播され、境界７０４及び７０５が最適サブセット内にあると判断される。しかしながら、これもまた最適サブセットの一部である境界７０６が見逃され、不正確な複合サーフェイスが生成された。
【００６１】
光線の不完全なサブセットによって生じる複合サーフェイスの欠陥を回避するために、１つの実施の形態は、図５Ｂに示す適応プロセス５８０を含む。決定中（５８０）、適応プロセスは、光線によって実行される複合サーフェイスのサンプリングが、正確な最適サブセットを得るのに十分であるか否かを特定する。十分でない場合、より少ない光線又は更なる光線が伝播される。
【００６２】
例えば、光線７０１と境界７０４との交点７０７、及び光線７０２と境界７０５との交点７０８は境界７０６に近く、それによって点７０７及び７０８における境界７０４及び７０５のサーフェイスに対する法線が、境界７０４及び７０５が光線７０１と７０２との間の点７０９において境界７０６と交わることを示している。したがって、最適サブセットの正確度を改善するために、更なる光線７０３を伝播し、複合サーフェイスのサンプリングを増大させる。
【００６３】
キャッシング
本発明の１つの実施の形態は、セルの距離フィールドのサブセット５５１が変更されるたびに最適サブセットを決定する。例えば、フライス加工シミュレータは、フライス加工プログラム内の命令ごとに、工作物の複合サーフェイスの更新画像を生成する。画像のレンダリング時間を最小にするために、フライス加工命令によって生成された新たな距離フィールドによって変更されたＡＤＦのセルごとに、距離フィールドの最適サブセットを更新する必要がある。実施の形態の１つの変形形態は、データ、例えば交点５７５をメモリ５６１内にキャッシュし、方法５５０を高速化する。メモリ５６１は、ランダムアクセスメモリ（ＲＡＭ：ｒａｎｄｏｍ ａｃｃｅｓｓ ｍｅｍｏｒｙ）等、当該技術分野において既知の任意のメモリとすることができる。フライス加工命令ごとに最適サブセットが更新され、すなわち、距離フィールドが追加及び／若しくは除去されるか、又は最適サブセットは変更されないままである。
【００６４】
図８は、メモリとして割り当てられたコンピュータメモリのブロック８００の例を示している。ブロックはＭ個の等しいサイズのサブブロック８０１に分割され、これらのサブブロックは、それぞれ１つのセルに関するデータを格納することができる。各サブブロックは、Ｎ個のロケーション８０３に更に分割される。各ロケーションは、１つの光線と関連付けられる。例えば、データは、光線と複合サーフェイスとの交点、及びその境界が光線において複合サーフェイスを形成する距離フィールドを一意に特定する数である。複合サーフェイスが存在しない光線の場合、フラグ値、例えば数−１が距離フィールド識別子の代わりに格納される。
【００６５】
各サブブロックは、サブブロックＩＤ８０４と関連付けられる。サブブロックＩＤ８０４は、そのデータが現在サブブロック内に格納されているセルの識別子として機能する。例えば、１つの実施の形態では、工作物内のセルの位置のｘ座標、ｙ座標、及びｚ座標の組合せから一意のセル識別子数が形成される。
【００６６】
図９は、メモリを用いて最適サブセットを決定する方法９００の流れ図である。セル識別子９０１が形成される。ハッシュ関数が、大きな範囲から、キャッシュサブブロック数に対応する［０，Ｍ−１］の所望の範囲にセル識別子をマッピングする（９０２）。ハッシュ関数の例はｏｕｔ（ｋ）＝ｋ ｍｏｄｕｌｏ Ｍであり、入力セル識別子値ｋを、モジュロ数学関数を用いて所望の範囲内の出力値ｏｕｔにマッピングする。ハッシュ関数からの出力値を、セルに関するデータを格納するキャッシュサブブロックのアドレスとして用いる（９０３）。
【００６７】
サブブロックが正確なセルに関するデータを格納していることを確かめるために、キャッシュからサブブロックＩＤが取り出され（９０４）、セル識別子と比較される（９０５）。識別子が一致しない場合、サブブロックは、現在のセルによって用いるためにクリアされ、セル識別子を用いてサブブロックＩＤが書き込まれる（９０６）。最適サブセットの決定（９０７）は、上述したように非キャッシュ式で進み、各光線に関するデータ９０８がキャッシュに格納され（９０９）、最適サブセット９１０を更新するために用いられる。
【００６８】
代替的に、値が一致するとき、サブブロック内のデータは最適サブセットを決定するのに用いられる。このため、方法９００は全ての光線にわたって反復する（９１１）。光線ごとに、交点は新たな距離フィールドについてのみ計算され（９１２）、交点の点を用いて、この光線について複合サーフェイスを形成する距離フィールド境界を決定する（９１３）。
【００６９】
図１０は、セル内に光線と新たな距離フィールドとの交差が存在するか否か、及びキャッシュ内にその光線に関するデータが存在するか否か、すなわち距離フィールド識別子が≠−１であるか否かに応じた、決定（９１３）の４つの可能な結果を示している。
【００７０】
交差及びキャッシュデータが存在しない場合、光線から何もわからないので、図１１Ａ〜図１１Ｃは、３つの上述した事例の例を示している。
【００７１】
図１１Ａにおいて、距離フィールド１１０２、１１０３、及び１１０４がセル１１０１と現在関連付けられており、距離フィールド１１０５は新たな距離フィールドである。光線１１０６は、点１１０７において距離フィールド１１０５の境界と交差し、キャッシュは光線１１０６に関するデータを含まない。したがって、交点１１０７において、現在セル内にある距離フィールド１１０２〜１１０４のサブセットの距離フィールド値が計算される。
【００７２】
交点における距離フィールドの値が全て正である、すなわち０より大きい場合、新たな距離フィールドは、この光線について複合サーフェイスを形成し、最適サブセットに追加される。図１１Ａに示す例において、距離フィールド値は全て負であり、距離フィールド１１０５は、最適サブセットに追加されない。
【００７３】
図１１Ｂにおいて、距離フィールド１１２２〜１１２４が現在セル１１２１に関連付けられており、距離フィールド１１２５は新たな距離フィールドである。光線１１２６は、セル内の距離フィールド１１２５の境界と交差しないが、キャッシュは、光線１１２６と距離フィールド１１２３の境界との交点１１２７を含む。この場合、交差は存在しないが、キャッシュは光線の有効なデータを含み、次に、キャッシュされた交点において新たな距離フィールドの値が求められる。
【００７４】
値が正である場合、キャッシュされた距離フィールドが最適サブセットに追加される。例示した例において、交点１１２７は距離フィールド１１２５の外側にあり、キャッシュされた距離フィールドが、光線１１２６に起因して最適サブセットに追加されることがないことを意味する。これは、距離フィールド１１２６が別の光線に起因して最適サブセットに追加される可能性を排除しないことを理解することが重要である。
【００７５】
最後に、図１１Ｃにおいて、距離フィールド１１３２〜１１３４が現在セル１１３１と関連付けられており、距離フィールド１１３５は新たな距離フィールドである。光線１１３６は点１１３８において距離フィールド１１３５の境界と交差し、キャッシュは、光線１１３６と距離フィールド１１３３の境界との交点１１３７を含む。この場合、交点が存在し、かつ有効なキャッシュされたデータが存在し、次に、新たな交点１１３８においてキャッシュされた距離フィールド１１３３の値が計算される。
【００７６】
値が正である場合、新たな距離フィールド１１３５が最適サブセットに追加される。そうでない場合、キャッシュされた距離フィールド１１３３が最適サブセットに追加される。この例では、交点１１３８は距離フィールド１１３３の境界内にあり（すなわちｄ＞０）、このため、距離フィールド１１３５が最適サブセットに追加される。
【００７７】
全ての光線が処理された後、各光線に関するデータがキャッシュに書き込まれ、最適サブセット９１０が完成する。
【００７８】
本発明を、好ましい実施の形態の例として説明してきたが、本発明の趣旨及び範囲内で他のさまざまな適合及び変更を行えることが理解されるべきである。したがって、本発明の真の趣旨及び範囲内に入る全ての変形及び変更を包含することが、添付の特許請求の範囲の目的である。
【特許請求の範囲】
【請求項１】
工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される前記工作物の機械加工のシミュレーションを最適化する方法であって、前記工作物の前記ボリュームはセルのセットに分割され、前記方法は、
各セルに、前記セルと交差する掃引されたボリュームのサブセットを表す距離フィールドのサブセットを関連付けるステップであって、前記掃引されたボリュームのサブセットの少なくとも一部は前記セルの複合サーフェイスを形成する、関連付けるステップと、
前記セルに、少なくとも１つの方向から前記セルに入射する光線のセットを当てるステップであって、各光線は直線の伝播を表す、当てるステップと、
前記距離フィールドのサブセットの或る距離フィールドを選択して、前記セルと関連付けられた最適サブセットに含めるステップであって、前記距離フィールドによって表される前記掃引されたボリュームの境界は、前記複合サーフェイス上に位置する交点において少なくとも１つの光線と交差する、選択して含めるステップと、
を含み、前記方法の前記ステップはプロセッサによって実行される、工作物のボリュームから掃引されたボリュームのセットを除去することによって実施される前記工作物の機械加工のシミュレーションを最適化する方法。
【請求項２】
前記交点において、前記距離フィールドのサブセットからの各距離フィールドの値を求めるステップと、
前記交点における前記距離フィールドの値がゼロであり、かつ前記サブセット内の残りの距離フィールドの値が正である場合、前記距離フィールドを選択して前記最適サブセットに含めるステップと、
を更に含む、請求項１に記載の方法。
【請求項３】
前記交点における前記距離フィールドの値がゼロであり、かつ前記交点における前記サブセット内の残りの距離フィールドの値が正である、請求項１に記載の方法。
【請求項４】
ｉ＝ｊ∈［１，Ｎ］についてｄｉ（ｐ）＝０であり、ｉ≠ｊについてｄｉ（ｐ）＞０であり、前記距離フィールドのサブセットはｉ∈［１，Ｎ］によってインデックス付けされたＮ個の距離フィールドを含み、ｄｉ（ｐ）は前記交点ｐにおける前記距離フィールドの前記値を定義し、ｊは前記最適サブセットにおいて選択された前記距離フィールドのインデックスである、請求項３に記載の方法。
【請求項５】
前記セル内に位置する前記交点を求めるステップ、
を更に含む、請求項１に記載の方法。
【請求項６】
前記セルの外側の点において前記光線を発生させるステップ、
を更に含む、請求項１に記載の方法。
【請求項７】
１つの方向からの前記光線は互いに平行であり、異なる方向からの前記光線は互いに直交する、請求項１に記載の方法。
【請求項８】
前記光線のセットを少なくとも２つの方向から前記セルに向かって伝播させるステップ、
を更に含む、請求項１に記載の方法。
【請求項９】
前記光線のセットを前記複合サーフェイスに対する法線に基づいて決定するステップ、
を更に含む、請求項１に記載の方法。
【請求項１０】
前記掃引されたボリュームのセットを更新するステップと、
前記更新に応答して、前記距離フィールドの最適サブセットを決定するステップと、
を更に含む、請求項１に記載の方法。
【請求項１１】
前記決定中に計算されたデータの少なくとも一部をメモリにキャッシュするステップ、
を更に含む、請求項１０に記載の方法。
【請求項１２】
前記メモリを等しいサイズのサブブロックに分割するステップであって、各サブブロックは１つのセルに関するデータを格納する、分割するステップと、
前記サブブロックを複数のロケーションに分割するステップであって、各ロケーションは１つの光線と関連付けられる、分割するステップと、
を更に含む、請求項１１に記載の方法。
【請求項１３】
前記ロケーションにおける前記データは、前記交点において前記光線と交差する前記境界を表す前記距離フィールドを特定する、請求項１２に記載の方法。
【請求項１４】
前記ロケーションにおける前記データは、前記光線が前記複合サーフェイスと交差していないことを特定する、請求項１２に記載の方法。
【請求項１５】
前記掃引されたボリュームを表す前記距離フィールドの値は、前記掃引されたボリュームの内部の場合、負である、請求項１に記載の方法。
【請求項１６】
工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される前記工作物のフライス加工のシミュレーションを最適化する方法であって、前記ボリュームはセルのセットに分割され、各セルは、前記セルと交差する掃引されたボリュームのサブセットと関連付けられ、前記掃引されたボリュームのサブセットの少なくとも一部が前記セルの複合サーフェイスを形成するようにされ、前記方法は、
前記セルに、前記セルに入射する光線のセットを当てるステップであって、光線は前記セルに向かう直線の伝播を表す、当てるステップと、
前記掃引されたボリュームのサブセットの或る掃引されたボリュームを選択して、前記セルと関連付けられた最適サブセットに含めるステップであって、前記掃引されたボリュームの境界は、前記複合サーフェイス上に位置する交点において少なくとも１つの光線と交差する、選択して含めるステップと、
を含む、工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される前記工作物のフライス加工のシミュレーションを最適化する方法。
【請求項１７】
前記境界の前記交点と、前記光線と前記サブセット内の残りの掃引されたボリュームの境界との交点との間の距離のセットを求めるステップと、
前記距離のセット内の各距離が正である場合、前記掃引されたボリュームを選択して前記最適サブセットに含めるステップと、
を更に含む、請求項１５に記載の方法。
【請求項１８】
工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される前記工作物のフライス加工のシミュレーションを最適化するシステムであって、前記ボリュームはセルのセットに分割され、前記システムは、
各セルに、前記セルと交差する掃引されたボリュームのサブセットを表す距離フィールドのサブセットを関連付ける手段であって、前記掃引されたボリュームのサブセットの少なくとも一部は前記セルの複合サーフェイスを形成する、関連付ける手段と、
前記セルに、少なくとも１つの方向から前記セルに入射する光線のセットを当てる手段であって、各光線は直線の伝播を表す、当てる手段と、
前記距離フィールドのサブセットの或る距離フィールドを選択して、前記セルと関連付けられた最適サブセットに含めるように構成されたプロセッサであって、前記距離フィールドによって表される前記掃引されたボリュームの境界は、前記複合サーフェイス上に位置する交点において少なくとも１つの光線と交差する、プロセッサと、
を備える、工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される前記工作物のフライス加工のシミュレーションを最適化するシステム。
【請求項１９】
前記交点において、前記距離フィールドのサブセットからの各距離フィールドの値を求める手段と、
前記交点における前記距離フィールドの値がゼロであり、かつ前記サブセット内の残りの距離フィールドの値が正である場合、前記距離フィールドを選択して前記最適サブセットに含める手段と、
を更に備える、請求項１８に記載のシステム。
【請求項２０】
前記求める手段によって計算されたデータの少なくとも一部をメモリにキャッシュする手段と、
前記メモリを等しいサイズのサブブロックに分割する手段であって、各サブブロックは１つのセルに関するデータを格納する、分割する手段と、
前記サブブロックを複数のロケーションに分割する手段であって、各ロケーションは１つの光線と関連付けられる、分割する手段と、
を更に備える、請求項１８に記載のシステム。
【請求項１】
工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される前記工作物の機械加工のシミュレーションを最適化する方法であって、前記工作物の前記ボリュームはセルのセットに分割され、前記方法は、
各セルに、前記セルと交差する掃引されたボリュームのサブセットを表す距離フィールドのサブセットを関連付けるステップであって、前記掃引されたボリュームのサブセットの少なくとも一部は前記セルの複合サーフェイスを形成する、関連付けるステップと、
前記セルに、少なくとも１つの方向から前記セルに入射する光線のセットを当てるステップであって、各光線は直線の伝播を表す、当てるステップと、
前記距離フィールドのサブセットの或る距離フィールドを選択して、前記セルと関連付けられた最適サブセットに含めるステップであって、前記距離フィールドによって表される前記掃引されたボリュームの境界は、前記複合サーフェイス上に位置する交点において少なくとも１つの光線と交差する、選択して含めるステップと、
を含み、前記方法の前記ステップはプロセッサによって実行される、工作物のボリュームから掃引されたボリュームのセットを除去することによって実施される前記工作物の機械加工のシミュレーションを最適化する方法。
【請求項２】
前記交点において、前記距離フィールドのサブセットからの各距離フィールドの値を求めるステップと、
前記交点における前記距離フィールドの値がゼロであり、かつ前記サブセット内の残りの距離フィールドの値が正である場合、前記距離フィールドを選択して前記最適サブセットに含めるステップと、
を更に含む、請求項１に記載の方法。
【請求項３】
前記交点における前記距離フィールドの値がゼロであり、かつ前記交点における前記サブセット内の残りの距離フィールドの値が正である、請求項１に記載の方法。
【請求項４】
ｉ＝ｊ∈［１，Ｎ］についてｄｉ（ｐ）＝０であり、ｉ≠ｊについてｄｉ（ｐ）＞０であり、前記距離フィールドのサブセットはｉ∈［１，Ｎ］によってインデックス付けされたＮ個の距離フィールドを含み、ｄｉ（ｐ）は前記交点ｐにおける前記距離フィールドの前記値を定義し、ｊは前記最適サブセットにおいて選択された前記距離フィールドのインデックスである、請求項３に記載の方法。
【請求項５】
前記セル内に位置する前記交点を求めるステップ、
を更に含む、請求項１に記載の方法。
【請求項６】
前記セルの外側の点において前記光線を発生させるステップ、
を更に含む、請求項１に記載の方法。
【請求項７】
１つの方向からの前記光線は互いに平行であり、異なる方向からの前記光線は互いに直交する、請求項１に記載の方法。
【請求項８】
前記光線のセットを少なくとも２つの方向から前記セルに向かって伝播させるステップ、
を更に含む、請求項１に記載の方法。
【請求項９】
前記光線のセットを前記複合サーフェイスに対する法線に基づいて決定するステップ、
を更に含む、請求項１に記載の方法。
【請求項１０】
前記掃引されたボリュームのセットを更新するステップと、
前記更新に応答して、前記距離フィールドの最適サブセットを決定するステップと、
を更に含む、請求項１に記載の方法。
【請求項１１】
前記決定中に計算されたデータの少なくとも一部をメモリにキャッシュするステップ、
を更に含む、請求項１０に記載の方法。
【請求項１２】
前記メモリを等しいサイズのサブブロックに分割するステップであって、各サブブロックは１つのセルに関するデータを格納する、分割するステップと、
前記サブブロックを複数のロケーションに分割するステップであって、各ロケーションは１つの光線と関連付けられる、分割するステップと、
を更に含む、請求項１１に記載の方法。
【請求項１３】
前記ロケーションにおける前記データは、前記交点において前記光線と交差する前記境界を表す前記距離フィールドを特定する、請求項１２に記載の方法。
【請求項１４】
前記ロケーションにおける前記データは、前記光線が前記複合サーフェイスと交差していないことを特定する、請求項１２に記載の方法。
【請求項１５】
前記掃引されたボリュームを表す前記距離フィールドの値は、前記掃引されたボリュームの内部の場合、負である、請求項１に記載の方法。
【請求項１６】
工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される前記工作物のフライス加工のシミュレーションを最適化する方法であって、前記ボリュームはセルのセットに分割され、各セルは、前記セルと交差する掃引されたボリュームのサブセットと関連付けられ、前記掃引されたボリュームのサブセットの少なくとも一部が前記セルの複合サーフェイスを形成するようにされ、前記方法は、
前記セルに、前記セルに入射する光線のセットを当てるステップであって、光線は前記セルに向かう直線の伝播を表す、当てるステップと、
前記掃引されたボリュームのサブセットの或る掃引されたボリュームを選択して、前記セルと関連付けられた最適サブセットに含めるステップであって、前記掃引されたボリュームの境界は、前記複合サーフェイス上に位置する交点において少なくとも１つの光線と交差する、選択して含めるステップと、
を含む、工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される前記工作物のフライス加工のシミュレーションを最適化する方法。
【請求項１７】
前記境界の前記交点と、前記光線と前記サブセット内の残りの掃引されたボリュームの境界との交点との間の距離のセットを求めるステップと、
前記距離のセット内の各距離が正である場合、前記掃引されたボリュームを選択して前記最適サブセットに含めるステップと、
を更に含む、請求項１５に記載の方法。
【請求項１８】
工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される前記工作物のフライス加工のシミュレーションを最適化するシステムであって、前記ボリュームはセルのセットに分割され、前記システムは、
各セルに、前記セルと交差する掃引されたボリュームのサブセットを表す距離フィールドのサブセットを関連付ける手段であって、前記掃引されたボリュームのサブセットの少なくとも一部は前記セルの複合サーフェイスを形成する、関連付ける手段と、
前記セルに、少なくとも１つの方向から前記セルに入射する光線のセットを当てる手段であって、各光線は直線の伝播を表す、当てる手段と、
前記距離フィールドのサブセットの或る距離フィールドを選択して、前記セルと関連付けられた最適サブセットに含めるように構成されたプロセッサであって、前記距離フィールドによって表される前記掃引されたボリュームの境界は、前記複合サーフェイス上に位置する交点において少なくとも１つの光線と交差する、プロセッサと、
を備える、工作物のボリュームから、掃引されたボリュームのセットを除去することによって実施される前記工作物のフライス加工のシミュレーションを最適化するシステム。
【請求項１９】
前記交点において、前記距離フィールドのサブセットからの各距離フィールドの値を求める手段と、
前記交点における前記距離フィールドの値がゼロであり、かつ前記サブセット内の残りの距離フィールドの値が正である場合、前記距離フィールドを選択して前記最適サブセットに含める手段と、
を更に備える、請求項１８に記載のシステム。
【請求項２０】
前記求める手段によって計算されたデータの少なくとも一部をメモリにキャッシュする手段と、
前記メモリを等しいサイズのサブブロックに分割する手段であって、各サブブロックは１つのセルに関するデータを格納する、分割する手段と、
前記サブブロックを複数のロケーションに分割する手段であって、各ロケーションは１つの光線と関連付けられる、分割する手段と、
を更に備える、請求項１８に記載のシステム。
【図１Ａ】
【図１Ｂ】
【図２Ａ】
【図２Ｂ】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図５Ａ】
【図５Ｂ】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１Ａ】
【図１１Ｂ】
【図１１Ｃ】
【図１Ｂ】
【図２Ａ】
【図２Ｂ】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図４Ａ】
【図４Ｂ】
【図４Ｃ】
【図５Ａ】
【図５Ｂ】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１Ａ】
【図１１Ｂ】
【図１１Ｃ】
【公表番号】特表２０１３−５１７５３５（Ｐ２０１３−５１７５３５Ａ）
【公表日】平成２５年５月１６日（２０１３．５．１６）
【国際特許分類】
【出願番号】特願２０１２−５３１９２４（Ｐ２０１２−５３１９２４）
【出願日】平成２３年３月１６日（２０１１．３．１６）
【国際出願番号】ＰＣＴ／ＪＰ２０１１／０５７０７３
【国際公開番号】ＷＯ２０１１／１２２４２３
【国際公開日】平成２３年１０月６日（２０１１．１０．６）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
【公表日】平成２５年５月１６日（２０１３．５．１６）
【国際特許分類】
【出願日】平成２３年３月１６日（２０１１．３．１６）
【国際出願番号】ＰＣＴ／ＪＰ２０１１／０５７０７３
【国際公開番号】ＷＯ２０１１／１２２４２３
【国際公開日】平成２３年１０月６日（２０１１．１０．６）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
[ Back to top ]