(57)【要約】【課題】ＥＤＭ工程用の電極形状を設計するための効率的かつ正確な技法を提供すること。【解決手段】コンピュータ可読記憶媒体が、軌道経路形状を得るための実行可能命令を含む。軌道経路形状上の各点は、軌道経路形状に沿って工具形状が移動されたときの工具形状の変位を表す。工具形状は、軌道経路形状に沿って移動されたとき、所望のキャビティ形状を掃引する。これらの実行可能命令は、掃引しようとする所望のキャビティ形状に対応する入力ソリッドモデルを得る、また、軌道経路形状と、入力ソリッドモデルに対応する面の集合、エッジの集合、および頂点の集合とに基づいて、工具形状のソリッドモデル用の面の集合を導出するための命令をさらに含む。これらの実行可能命令は、工具形状のソリッドモデルを生成するように、工具形状のソリッドモデル用に導出された面の集合の部分集合を合成するための命令をさらに含む。一実施形態では、工具形状は、軌道経路形状に対する入力ソリッドモデルのミンコフスキー分解に対応する。【選択図】図２
2010033568.tif 000002
【特許請求の範囲】
【請求項１】
軌道経路形状を得るためのプログラムであって、前記軌道経路形状上の各点は、前記軌道経路形状に沿って工具形状が移動されたときの前記工具形状の変位を表し、前記工具形状は、前記軌道経路形状に沿って移動されたとき、所望のキャビティ形状を掃引することと、
掃引しようとする前記所望のキャビティ形状に対応する入力ソリッドモデルを得ることと、
前記軌道経路形状と、前記入力ソリッドモデルに対応する面の集合、エッジの集合、および頂点の集合とに基づいて、前記工具形状のソリッドモデル用の面の集合を導出することと、
前記工具形状の前記ソリッドモデルを生成するように、前記工具形状の前記ソリッドモデル用に導出された前記面の集合の部分集合を合成することであって、前記工具形状は、前記軌道経路形状に対する前記入力ソリッドモデルのミンコフスキー分解に対応する、合成することと
をコンピュータに実行させるためのプログラムを記憶したことを特徴とするコンピュータ可読記憶媒体。
【請求項２】
前記面の集合の少なくとも部分集合は、ソリッドモデラによって定義される様々なオフセットサーフェス幾何形状を使用して前記工具形状の前記ソリッドモデル用に導出されることを特徴とする請求項１に記載のコンピュータ可読記憶媒体。
【請求項３】
前記工具形状の前記ソリッドモデルは、電極形状のＣＡＤモデルを表すことを特徴とする請求項１に記載のコンピュータ可読記憶媒体。
【請求項４】
前記プログラムは、前記入力ソリッドモデル内の前記面の集合に関連付けられた前記幾何形状の部分集合を前記軌道経路形状の部分集合と畳み込むことによって、前記入力ソリッドモデル内の前記面の集合の部分集合に対応する前記工具形状の前記ソリッドモデル用の前記面の集合の部分集合を導出することをさらにコンピュータに実行させることを特徴とする請求項１に記載のコンピュータ可読記憶媒体。
【請求項５】
前記入力ソリッドモデル内の各面を前記ミンコフスキー分解の境界上にある前記軌道経路形状と畳み込んだものにある各点は、前記工具形状の前記ソリッドモデルに対応する前記面の集合内に含まれることを特徴とする請求項４に記載のコンピュータ可読記憶媒体。
【請求項６】
前記プログラムは、前記入力ソリッドモデル内の前記エッジの集合に関連付けられた前記幾何形状の部分集合を前記軌道経路形状の部分集合と畳み込むことによって、前記入力ソリッドモデル内の前記エッジの集合の部分集合に対応する前記工具形状の前記ソリッドモデル用の前記面の集合の部分集合を導出することをさらにコンピュータに実行させることを特徴とする請求項１に記載のコンピュータ可読記憶媒体。
【請求項７】
前記入力ソリッドモデル内の各面を前記ミンコフスキー分解の境界上にある前記軌道経路形状と畳み込んだものにある各点は、前記工具形状の前記ソリッドモデルに対応する前記面の集合内に含まれることを特徴とする請求項６に記載のコンピュータ可読記憶媒体。
【請求項８】
前記プログラムは、前記入力ソリッドモデル内の前記頂点の集合に関連付けられた前記幾何形状の部分集合を前記軌道経路形状の部分集合と畳み込むことによって、前記入力ソリッドモデル内の前記頂点の集合の部分集合に対応する前記工具形状の前記ソリッドモデル用の前記面の集合の部分集合を導出することをさらにコンピュータに実行させることを特徴とする請求項１に記載のコンピュータ可読記憶媒体。
【請求項９】
前記入力ソリッドモデル内の各面を前記ミンコフスキー分解の境界上にある前記軌道経路形状と畳み込んだものにある各点は、前記工具形状の前記ソリッドモデルに対応する前記面の集合内に含まれることを特徴とする請求項８に記載のコンピュータ可読記憶媒体。
【請求項１０】
前記プログラムは、前記軌道経路形状を得るための前記実行可能命令は、前記入力ソリッドモデルの境界上の例外フィーチャの集合およびシルエットフィーチャの集合に対応する前記軌道経路形状内の領域を識別するために前記軌道経路形状を解析することをさらにコンピュータに実行させることを特徴とする請求項１に記載のコンピュータ可読記憶媒体。
【請求項１１】
前記プログラムは、前記例外フィーチャの集合および前記シルエットフィーチャの集合を使用し、前記入力ソリッドモデルの境界を１つまたは複数のストリップに区分することをさらにコンピュータに実行させ、前記ストリップは、前記軌道経路形状内の前記領域に対応することを特徴とする請求項１０に記載のコンピュータ可読記憶媒体。
【請求項１２】
前記プログラムは、前記工具形状の前記ソリッドモデルを生成するための前記実行可能命令は、前記入力ソリッドモデル内の前記ストリップを前記工具形状の前記ソリッドモデル内の対応するストリップにマッピングすることをさらにコンピュータに実行させることを特徴とする請求項１１に記載のコンピュータ可読記憶媒体。
【請求項１３】
前記プログラムは、前記入力ソリッドモデル内の例外点を識別し、前記例外点を、対応するパラメータ化された面と置き換えることをさらにコンピュータに実行させることを特徴とする請求項１０に記載のコンピュータ可読記憶媒体。
【請求項１４】
前記プログラムは、前記工具形状の前記ソリッドモデルを修復することをさらにコンピュータに実行させることを特徴とする請求項１に記載のコンピュータ可読記憶媒体。
【請求項１５】
前記工具形状の前記ソリッドモデルを修復することは、同じ場所を占める例外面の集合および同じ場所を占めるシルエット面の集合を検出し、前記工具形状の前記ソリッドモデルから除去すること含むことを特徴とする請求項１４に記載のコンピュータ可読記憶媒体。
【請求項１６】
前記工具形状の前記ソリッドモデルを修復することは、前記工具形状の前記ソリッドモデル内で面積ゼロの面および長さゼロのエッジの集合を検出し、前記面積ゼロの面および長さゼロのエッジの集合をエッジおよび頂点の集合と置き換えることをさらに含むことを特徴とする請求項１４に記載のコンピュータ可読記憶媒体。
【請求項１７】
前記工具形状の前記ソリッドモデルを修復することは、同じ場所を占める面、同じ場所を占めるエッジ、および同じ場所を占める頂点の集合内で重複を検出し、前記工具形状の前記ソリッドモデルから除去することをさらに含むことを特徴とする請求項１４に記載のコンピュータ可読記憶媒体。
【請求項１８】
前記工具形状の前記ソリッドモデルを修復することは、前記工具形状の前記ソリッドモデル内の自己交差を検出および除去することをさらに含むことを特徴とする請求項１４に記載のコンピュータ可読記憶媒体。
【請求項１９】
前記工具形状の前記ソリッドモデルは、前記工具形状の中間モデルであることを特徴とする請求項１に記載のコンピュータ可読記憶媒体。
【請求項２０】
前記プログラムは、前記工具形状の最終ソリッドモデルを生成するように、複数のソリッドモデリング演算を前記工具形状の前記中間モデルに対して実施することをさらにコンピュータに実行させることを特徴とする請求項１９に記載のコンピュータ可読記憶媒体。
【請求項２１】
前記複数のソリッドモデリング演算は、火花ギャップ効果を補償するように前記工具形状の前記中間ソリッドモデルを処理することを含むことを特徴とする請求項２０に記載のコンピュータ可読記憶媒体。
【請求項２２】
前記プログラムは、前記工具形状の前記ソリッドモデルの製造可能性についてユーザに通知することをさらにコンピュータに実行させることを特徴とする請求項１に記載のコンピュータ可読記憶媒体。
【請求項２３】
前記軌道経路形状は、平面的な軌道経路形状であることを特徴とする請求項１に記載のコンピュータ可読記憶媒体。
【請求項２４】
前記軌道経路形状は、円形の軌道経路形状であることを特徴とする請求項１に記載のコンピュータ可読記憶媒体。
【請求項２５】
前記工具形状の前記ソリッドモデル用の前記面の集合内の少なくとも１つの面に関連付けられたサーフェスは、複数の分岐を使用し、その形状を定義することを特徴とする請求項１に記載のコンピュータ可読記憶媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
（関連出願の相互参照）
本願は、２００８年７月１８日に出願された「Apparatus and Method for Designing An Electrode Shape For An Electrical Discharge Machining (EDM) Process」という名称の米国特許仮出願第６１／０８２０６７号明細書、および２００９年６月１２日に出願された「Apparatus and Method for Designing an Electrode Shape for an Electrical Discharge Machining Process」という名称の米国特許出願第１２／４８３９０３号明細書に対する優先権を主張するものであり、これらの内容を参照により本明細書に組み込む。
【０００２】
本発明は、一般にコンピュータ援用設計（ＣＡＤ）に関し、より詳細には、放電加工（ＥＤＭ）工程用の電極形状など、所望の形状を得るために経路に沿って掃引されるボディ形状（ｂｏｄｙ  ｓｈａｐｅ）を設計するための方法に関する。
【背景技術】
【０００３】
ＥＤＭは、エネルギーの大きな電界の存在下で、電極（切削工具）と被加工物の間の一連の、急速に繰り返すアーク放電によって金属を除去するために使用される金属除去工程である。金属除去工程は、一般に、軌道経路に沿って電極を移動しながら、電極を介して被加工物に高周波電流のパルス放電を印加することによって実施される。これは、非常に小さな金属片を、制御された速度で被加工物から除去または浸食除去し、所望の形状を有する、仕上げられた被加工物を作り出す。
【０００４】
ＥＤＭ工程用の電極の設計において軌道形状に対処するために、いくつかの手法が存在する。１つのそのような手法は、１組の設計規則に基づいて、電極に対応するＣＡＤモデルを手動で設計することを含む。しかし、電極のＣＡＤモデルの手動設計は時間がかかるものであり、概して誤りを犯しやすい。さらに、設計規則の使用は、一般に、複雑な目標キャビティ形状を生成するために設計者が複雑な工具形状を生み出すことができるほど十分に洗練されていない。さらに、設計規則は、一般に、目標キャビティ形状のための電極工具形状が存在しない可能性がある状況を検出するほど十分に洗練されていない。
【０００５】
ＥＤＭ工程用の電極形状の設計は、コンピュータをベースとする解決策を使用して実施することもできる。コンピュータをベースとする解決策は、いくつかの多角形軌道経路のための電極形状を計算することができるが、一般に、非多角形軌道経路のためには、経路の形状の近似が必要とされる。１つのそのような解決策は、電極の軌道経路形状を多角形近似することを含む。なめらかに湾曲する軌道を多角形によって近似することは、電極上の誤った鋭い隅部（Ｓｈａｒｐ  ｃｏｎｅｒｓ）を生じる可能性がある。さらに、非多角形軌道経路が近似されるとき、得られる電極形状は、一般に、元のキャビティモデルより面が多くなり、これらの近似を実施するＣＡＤアプリケーションにおける性能およびロバスト性問題を引き起こす。その結果、電極の形状を計算するための、所望のレベルの精度を、効率的に達成することができない。
【０００６】
また、電極の軌道運動に対処するために不均一オフセット技法（ｎｏｎ−ｕｎｉｆｏｒｍ  ｏｆｆｓｅｔｔｉｎｇ  ｔｅｃｈｎｉｑｕｅ）の適用に基づいて電極の幾何形状を修正する電極設計技法が開発されている。これらの技法は、一般に、軌道パターンに従ってサンプル済みの点の不均一オフセットを実施することによって目標表面を近似することを必要とする。上記で論じた他の近似技法の場合と同様に、これらの手法を使用すると、一般に、電極形状設計に関して、所望のレベルの精度の達成と所望のレベルの性能の達成との兼ね合いが生じる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国特許出願公開第２００７／０２３９３１１号明細書
【特許文献２】米国特許第６９４１２５１号明細書
【非特許文献】
【０００８】
【非特許文献１】Gang Wang, Yan Shan,“Compensation of electrode orbiting in electrical discharge machining based on non-uniform offsetting”, International Journal of Machine Tools & Manufacture 45 (2005) 1628-1634
【非特許文献２】Martin Peternell, Tibor Steiner:“Minkowski sum boundary surfaces of 3D-objects”, Graphical Models 69(3-4): 180-190 (2007)
【非特許文献３】X.M.Ding, J.Y.H. Fuh, and K.S. Lee:“Computer aided EDM electrode design”, Computers & Industrial Engineering 42(2-4) 259-269 (2002)
【発明の概要】
【発明が解決しようとする課題】
【０００９】
したがって、ＥＤＭ工程用の電極形状を設計するための効率的かつ正確な技法を開発することが望ましいであろう。
【課題を解決するための手段】
【００１０】
本発明の実施形態は、ＥＤＭ工程用の電極形状など、所望の形状を得るために経路に沿って掃引されるボディ形状を設計するための装置および方法に関する。一実施形態では、コンピュータ可読記憶媒体が、工具形状のソリッドモデルを生成することをコンピュータに実行させるためのプログラム（実行可能命令）を記憶している。これらの実行可能命令は、軌道経路形状を得るための命令を含む。軌道経路形状上の各点は、軌道経路形状に沿って工具形状が移動されたときの工具形状の変位を表す。工具形状は、軌道経路形状に沿って移動されたとき、所望のキャビティ形状を掃引する。これらの実行可能命令は、掃引しようとする所望のキャビティ形状に対応する入力ソリッドモデルを得る、また、軌道経路形状と、入力ソリッドモデルに対応する面の集合、エッジの集合、および頂点の集合とに基づいて、工具形状のソリッドモデル用の面の集合を導出するための命令をさらに含む。これらの実行可能命令は、工具形状のソリッドモデルを生成するように、工具形状のソリッドモデル用に導出された面の集合の部分集合を合成する（ｃｏｍｂｉｎｅ）ための命令をさらに含む。一実施形態では、工具形状は、軌道経路形状に対する入力ソリッドモデルのミンコフスキー分解に対応する。
【００１１】
本発明のいくつかの実施形態は、以下の詳細の説明を添付の図面と併せ読めば、より完全に理解される。
【図面の簡単な説明】
【００１２】
【図１】本発明の一実施形態に従って構成されたコンピュータの図である。
【図２】本発明の一実施形態による、ＥＤＭ工程用の電極形状を自動的に生成するための処理演算を示す流れ図である。
【図３】本発明の一実施形態による、ＥＤＭ工程のための軌道経路に対応する例示的な形状の図である。
【図４】本発明の一実施形態による、ＥＤＭ工程のための軌道経路を描く、閉じられた平面的な曲線の図である。
【図５】本発明の一実施形態による、固定された凸性の領域に曲線が分割される、変曲点を有する曲線内の直線領域の図である。
【図６（ａ）】本発明の一実施形態による、任意の方向で平行または逆平行の接ベクトルを有する最大２つの点を有する曲線の図である。
【図６（ｂ）】本発明の一実施形態による、特定の方向で平行または逆平行の接ベクトルを有する３つ以上の点を有する曲線の図である。
【図７】本発明の一実施形態による、２πより大きい転向角を有し、変曲点がなく、特定の方向で平行または逆平行の接ベクトルを有する３つ以上の点を有する曲線の図である。
【図８】本発明の一実施形態による、垂直方向で表面法線を有する点に対する潜在的な変位ベクトルを有する曲線の図である。
【図９】本発明の一実施形態による、曲線内の鋭い隅点に関連付けられた接ベクトルの図である。
【図１０】本発明の一実施形態による、モデルの境界上の鋭いエッジに関連付けられた複数の表面法線を示すソリッドモデルの横断面図である。
【図１１】本発明の一実施形態による、モデルの境界上の凸形エッジおよび凹形エッジを示すソリッドモデルの横断面図である。
【図１２】本発明の一実施形態による、水平トーラスに関する例外曲線の図である。
【図１３】本発明の一実施形態による、曲線を諸領域に分離する変曲点、および直線領域によって引き起こされるシルエット方向の図である。
【図１４】本発明の一実施形態による、モデルの、垂直ストリップへのセグリゲーション（ｓｅｇｒｅｇａｔｉｏｎ）を示すソリッドモデルの横断面図である。
【図１５】本発明の一実施形態による、図１４におけるストリップのコピーを図１３における曲線の対応する領域によって調整することによって形成されたストリップの集合の横断面図である。
【図１６】本発明の一実施形態による、元のモデル上のストリップの、オフセットモデル上のストリップへのマッピングを示すソリッドモデルの横断面図である。
【図１７】本発明の一実施形態による、三角形（垂直）プリズムを方形の軌道経路に沿って並進させたとき、シルエットエッジによって生成されたシルエット面を示すソリッドモデルの横断面図である。
【図１８】本発明の一実施形態による、軌道経路形状の様々な分岐に対するオフセット演算の実施の図である。
【図１９】本発明の一実施形態による、１／２面の円柱に関する内向き分岐および外向き分岐のパラメータ空間を表すものの図である。
【図２０】本発明の一実施形態による、円形経路の２つの分岐に対応する、軌道平面内で左方向および右方向に円柱を並進させるソリッドモデルの横断面図である。
【発明を実施するための形態】
【００１３】
次に、本発明の実施形態の演算に関連する様々な特徴について述べる。そのような説明の前に、いくつかの実施形態に適用可能な用語集を提供する。
【００１４】
ブーリアン補集合（Boolean complement）：いくつかの実施形態では、空間内の点の集合のブーリアン補集合は、その集合の一部でない空間内の点すべてとして定義される。たとえば、ソリッド球のブーリアン補集合は、球と同じ中心および半径を有する球形キャビティを取り囲む点の集合である。
【００１５】
ソリッド：いくつかの実施形態によれば、ソリッドは、物理形状を表すことが意図された３次元空間内の点の集合である。
【００１６】
ソリッドの境界：ソリッドの境界は、ソリッドの内部をその外部から分離する点の集合である。極めて薄い２次元（シート）ソリッド、１次元（ワイヤ）ソリッド、または０次元（点）ソリッドの場合には、ソリッドは、それ自体の境界を形成する。
【００１７】
境界表現：いくつかの実施形態によれば、境界表現は、ソリッドの形状を、その境界のプロパティ（たとえば、形状、接続性）を介して表すための技法である。
【００１８】
Ｂ−Ｒｅｐソリッドモデル：いくつかの実施形態によれば、Ｂ−Ｒｅｐソリッドモデルは、境界表現の技法を使用してソリッドの形状を指定するデータである。
【００１９】
外向きにオフセットする（ｏｆｆｓｅｔ  ｏｕｔｗａｒｄｓ）：いくつかの実施形態によれば、「外向きにオフセットする」は、材料の層をソリッドの境界の周りで追加し、それにより、同様の形状の新しい、より大きなソリッドを生み出すこととして定義される。
【００２０】
内向きにオフセットする（ｏｆｆｓｅｔ  ｉｎｗａｒｄｓ）：いくつかの実施形態によれば、「内向きにオフセットする」は、材料の層をソリッドの境界の周りで除去し、それにより、同様の形状の新しい、より小さなソリッドを生み出すこととして定義される。
【００２１】
サーフェス：いくつかの実施形態によれば、サーフェスは、一般に１対１マッピングを介して平坦な２次元空間内の矩形にパラメータ化された、３次元空間内の点の２次元接続された集合である。
【００２２】
曲線：いくつかの実施形態によれば、曲線は、一般に１対１マッピングを介して平坦な１次元空間内の線分にパラメータ化された、３次元空間内の点の１次元接続された集合である。
【００２３】
面：いくつかの実施形態によれば、面は、ソリッドモデルの境界の２次元要素である。特定の面の幾何形状は、一般に、ソリッドモデルの境界上の特定のサーフェスの、接続された２次元部分集合として定義される。隣り合う面は、一般に、エッジおよび／または頂点の集まりによって分離される。
【００２４】
エッジ：いくつかの実施形態によれば、エッジは、ソリッドモデルの境界の１次元要素である。特定のエッジの幾何形状は、一般に、ソリッドモデルの境界上の特定の曲線の、接続された１次元部分集合として定義される。隣り合うエッジは、一般に、頂点によって分離される。
【００２５】
頂点：いくつかの実施形態によれば、頂点は、ソリッドモデルの境界の０次元要素である。特定の頂点の幾何形状は、一般に、ソリッドモデルの境界上の特定の点として定義される。
【００２６】
例外点：いくつかの実施形態によれば、例外点は、その点のところでの表面法線が軌道平面に対して垂直である条件が満たされるソリッドの境界上の点である。
【００２７】
非例外点：いくつかの実施形態によれば、非例外点は、例外点でないソリッドの境界上の点である。
【００２８】
例外領域：いくつかの実施形態によれば、例外領域は、例外点の２次元接続された集合である。
【００２９】
例外曲線：いくつかの実施形態によれば、例外曲線は、例外点の１次元接続された集合である。
【００３０】
孤立（ｉｓｏｌａｔｅｄ）例外点：いくつかの実施形態によれば、孤立例外点は、他のどの例外点にも隣接しない例外点であり、たとえば、要素を１つしかもたない、例外点の０次元接続された集合に等しい。
【００３１】
例外面：いくつかの実施形態によれば、例外面は、例外領域に関連付けられる面である。
【００３２】
例外エッジ：いくつかの実施形態によれば、例外エッジは、例外曲線に関連付けられるエッジである。
【００３３】
例外頂点：いくつかの実施形態によれば、例外頂点は、孤立例外点に関連付けられる頂点である。
【００３４】
接多様体（ｔａｎｇｅｎｔ  ｍａｎｉｆｏｌｄ）：いくつかの実施形態によれば、接多様体は、多様体上の点でその多様体に接するベクトルによって生成された平坦な空間である。２次元サーフェスに対する接多様体は平面であり、１次元曲線に対する接多様体は直線であり、０次元点に対する接多様体は空（empty）である。２つの接多様体は、一方の接多様体の生成元を他方の接多様体の生成元の１次結合として表すことができる場合、平行であると言われる。本発明の一実施形態によれば、０次元点の接多様体は、任意の他の接多様体に対して平行とみなされる。
【００３５】
シルエット方向：いくつかの実施形態によれば、シルエット方向は、軌道経路の解析を経て得られる３次元空間内の特別な方向である。
【００３６】
シルエット点：いくつかの実施形態によれば、シルエット点は、その接多様体がシルエット方向に対して平行であるソリッドの境界上の点である。
【００３７】
シルエット領域：いくつかの実施形態によれば、シルエット領域は、シルエット点の２次元接続された集合である。
【００３８】
シルエット曲線：いくつかの実施形態によれば、シルエット曲線は、シルエット点の１次元接続された集合である。たとえば、昼の領域と夜の領域を分離する地球上の明暗境界線円がシルエット曲線の例であり、シルエット方向は、太陽から地球の方向にある。
【００３９】
孤立シルエット点：いくつかの実施形態によれば、孤立シルエット点は、他のどのシルエット点にも隣接しないシルエット点であり、たとえば、要素を１つしかもたない、シルエット点の０次元接続された集合に等しい。
【００４０】
鋭いエッジ：いくつかの実施形態によれば、鋭いエッジは、その隣り合う面が接しない、すなわち表面法線が、エッジに沿って、平行でないエッジである。
【００４１】
膨張するエッジ：いくつかの実施形態によれば、拡張エッジは、隣り合う面の境界が、特定の方向でオフセットするとき発散する、鋭いエッジである。外向きにオフセットするとき、凸形エッジが膨張しつつあり、内向きにオフセットするとき、凹エッジが膨張しつつある。
【００４２】
収縮するエッジ：いくつかの実施形態によれば、収縮するエッジは、隣り合う面の境界が、特定の方向でオフセットするとき収束する、鋭いエッジである。外向きにオフセットするとき、凹エッジが収縮しつつあり、内向きにオフセットするとき、凸エッジが収縮しつつある。
【００４３】
ミンコフスキー和：いくつかの実施形態によれば、２つの点集合Ａ、Ｂについて、ミンコフスキー和は、ＢをＡ内のあらゆる点に移動することによって掃引される点すべての集合として定義される。
【００４４】
畳み込み：いくつかの実施形態によれば、２つの点集合（たとえば、２つのサーフェス、サーフェスと曲線など）の畳み込みは、それらのミンコフスキー和の境界である。
【００４５】
部分集合：いくつかの実施形態によれば、２つの要素Ａ、Ｂについて、Ｂのあらゆる要素がＡの要素でもある場合、ＢはＡの部分集合である。Ａはそれ自体の部分集合となることもできることに留意されたい。
【００４６】
分岐：いくつかの実施形態によれば、分岐は、元のモデルの境界上の特定のストリップに対応する軌道経路を定義する曲線の領域である。
【００４７】
図１は、本発明の一実施形態に従って構成されたコンピュータ１００を示す。コンピュータ１００は、バス１０６によってリンクされる中央処理装置（ＣＰＵ）１０２および入力／出力デバイス１０４を含めて、様々な構成要素を含む。いくつかの実施形態では、ネットワークインターフェース回路（ＮＩＣ）１０８がネットワーク（図示せず）への接続を可能にし、それによりコンピュータ１００は、ネットワーク環境内で動作することができる。
【００４８】
メモリ１１０もまた、バス１０６に接続される。メモリ１１０は、本明細書に述べられている演算を実施するために、１つまたは複数の実行可能モジュールを含む。一実施形態では、メモリ１１０は、コンピュータ援用設計（ＣＡＤ）モジュール１１２を含む。一実施形態では、ＣＡＤモジュール１１２は、コロラド州ブルームフィールドのＳｐａｔｉａｌ  Ｃｏｒｐｏｒａｔｉｏｎから市販されているＡＣＩＳ  Ｇｅｏｍｅｔｒｉｃ  Ｍｏｄｅｌｅｒを含む。特定の実施形態では、ＣＡＤモジュール１１２は、ＥＤＭ工程用の電極の形状を自動的に生成するための実行可能命令をも含む。ＣＡＤモジュール１１２によって実施される演算については、下記の図２でより詳細に論じる。
【００４９】
ＣＡＤモジュール１１２は、例として提供されていることに留意されたい。オペレーティングシステムやグラフィカルユーザインターフェースモジュールなど追加のモジュールが含まれてもよい。モジュールの機能は組み合わせることができることを理解されたい。さらに、モジュールの機能は、単一のマシン上で実施される必要はない。むしろこれらの機能は、望むならネットワーク全体にわたって分散されてもよい。実際には、本発明のいくつかの実施形態は、クライアント−サーバ環境で実施され、様々な構成要素がクライアント側および／またはサーバ側で実装される。
【００５０】
図２は、本発明の一実施形態による、工具形状のソリッドモデルを生成するための処理演算を示す流れ図である。一実施形態では、工具形状のソリッドモデルは、ＥＤＭ電極形状のＣＡＤモデルを表す。特定の実施形態では、ＣＡＤモジュール１１２内の１つまたは複数のサブモジュールが、工具形状のソリッドモデルを生成するための実行可能命令を含む。工具形状のソリッドモデルを生成するための演算の例示的なセット（１２０〜１３８）について、下記で詳細に論じる。
【００５１】
（軌道経路形状を得る演算）
最初に、工具形状に対応する軌道経路形状を得るための演算が実施される（ブロック１２０）。一実施形態では、ユーザが軌道経路形状を指定する。たとえば、ユーザには、たとえば図３に示されているように、「円」１４０、「方形」１４２、または「規則正しいＮ角形」１４４など、１組の事前定義された形状が提示されてもよい。次いで、ユーザは、円のための「半径」や、規則正しいＮ角形のための「Ｎ」「辺の長さ」「回転角」など、パラメータを選択または指定することができる。一般に、軌道経路形状は、任意の多角形形状または任意の非多角形形状とすることができる。
【００５２】
他の実施形態では、ユーザは、図４に示されているように、軌道経路を描く、閉じられた平面的な曲線を指定することができる。この曲線は、実際の軌道経路、または軌道経路に対応する平面的な領域の境界を表すことができる。たとえば、ユーザは、ＣＡＤモデラインターフェースを介して、閉じられた平面的な曲線を指定することができる。いくつかの実施形態では、ユーザは、軌道経路（に対する、たとえば法線）の向きを、また軌道経路が「埋められている（ｆｉｌｌｅｄ）」１４８（実際の経路は、指定された曲線が境界である平面的な領域）か、それとも「埋められていない（ｕｎｆｉｌｌｅｄ）」１４６（実際の経路は、指定された曲線）かを指定することができる。具体的には、軌道経路形状上の各点は、軌道経路形状に沿った工具形状の運動中の、工具形状の変位を表す。下記でより詳細に論じるように、工具形状は、軌道経路形状に沿って移動されたとき、所望のキャビティ形状を掃引する。
【００５３】
（所望のキャビティ形状に対応する入力ソリッドモデルを得る演算）
次いで、掃引しようとする所望のキャビティ形状に対応する点の所望の軌跡の入力ソリッドモデルを得るための演算が実施される（ブロック１２２）。一実施形態では、入力ソリッドモデルは、除去しようとする材料の入力ＣＡＤモデルである。特定の実施形態では、除去しようとする材料の入力ＣＡＤモデルは、電極の未調整形状（すなわち、被加工物内の所望のキャビティ形状を材料で埋めることによって得られるはずの部分の形状）のモデルである。他の実施形態では、除去しようとする材料の入力ＣＡＤモデルは、キャビティそれ自体の形状、すなわち電極の未調整形状のブーリアン補集合のモデルである。
【００５４】
（軌道経路形状を解析する演算）
次いで、軌道経路形状を解析するための演算が実施される（ブロック１２４）。一実施形態では、軌道経路形状を解析し、入力ソリッドモデルの境界上の点の軌跡に対応する経路の領域を識別する。特定の実施形態では、軌道経路形状の解析は、軌道経路形状を１組の領域に区分することを含む。図５は、直線領域を有する軌道経路形状を示す。図の例では、軌道経路は、直線領域１５０と、２つの変曲点１５２を有する、閉じられた平面的な曲線によって描かれる。本明細書では、「変曲点」は、曲率ゼロの点を指す。具体的には、軌道経路形状は、２π以下の転向角を有する、固定された凸性の領域１５４に分割される。軌道経路形状を、固定された凸性の領域に分割すること、および変曲点を識別することにより、入力ソリッドモデルの境界上の点の集合から、工具形状のソリッドモデル（すなわち、電極形状のＣＡＤモデル）の境界上の１組の点への１対１マッピングが可能になる。
【００５５】
閉じられた平面的な曲線に対する平行または逆平行の接線を有する３つ以上の点を有する非直線領域は、電極形状のＣＡＤモデルの境界上の複数の領域にマッピングされる入力ソリッドモデルの境界上の領域に帰着することに留意されたい。また、２π以下の総積分転向角（ｔｏｔａｌ  ｉｎｔｅｇｒａｔｅｄ  ｔｕｒｎｉｎｇ  ａｎｇｌｅ）を有する、固定された凸性の領域は、任意の方向で平行または逆平行の接線を有する２つ以下の内部点を有することになることに留意されたい。
【００５６】
図６（ａ）は、任意の方向で平行または逆平行の接ベクトルを有する最大２つの点を有する曲線を示す。図６（ｂ）は、特定の方向で平行または逆平行の接ベクトルを有する３つ以上の点を有する曲線を示す。図７は、２πより大きい転向角を有し、変曲点がなく、特定の方向で平行または逆平行の接ベクトルを有する３つ以上の点を有する曲線を示す。
【００５７】
一実施形態では、入力ＣＡＤモデルの境界上の特定の点が、電極形状のＣＡＤモデルの境界上の１つまたは複数の点にマッピングされ、その結果、電極形状のＣＡＤモデル内の特定のオフセット点と、入力ＣＡＤモデル内の対応する元の点との差が、軌道経路を定義する曲線上のある点に関する変位ベクトルになり、その曲線上のその点での、その曲線に対する接ベクトルは、入力ＣＡＤモデルの境界上の点での表面法線に対して垂直である。図８は、表面法線が水平方向に対して平行である、入力ＣＡＤモデルの境界上の特定の点に関する潜在的な変位ベクトルを有する曲線を示す。原点１５８、およびこの点に関する変位ベクトル１５６が示されている。入力ＣＡＤモデルの境界および円形軌道上の非例外点については、表面法線の、その平面内への投影の方向で円のダイアゴナル（ｄｉａｇｏｎａｌ：直径線）の端部に対応する、そのような点が２つあることに留意されたい。そのような複数の変位の場合には、入力ソリッドＣＡＤモデル内のサーフェスが各変位について別々にコピーされ、各コピーが、異なる変位だけ変形される。
【００５８】
特定の実施形態では、軌道経路形状の解析は、以下のように実施される（ブロック１２４）。
【００５９】
曲線の直線領域、および各直線領域内の単位接線の方向が識別される。
【００６０】
変曲点（すなわち、単位接線の曲線に沿った導関数がゼロまたはヌルである直線領域の外の点）、および各変曲点での単位接線の方向が識別される。
【００６１】
１組の単位接ベクトルが、曲線上の各点に関連付けられる。軌道経路形状の「隅部」（経路がＧ１連続でない点）では、この１組は、不連続の左側の曲線を不連続の右側の曲線に接続する微小円弧の単位接線すべてを含む。当業者には理解されるように、サーフェスＳは、点ｓ付近で法線ベクトルを定義する単一値の連続関数がある場合、ｓでのＧ１連続と呼ぶことができる。ＳがｓでＧ１でない場合には、法線ベクトル（したがって接平面）は、その点で多値である。たとえば、無限に薄い中空の球は、どこでもＧ１であり、無限に薄い中空の立方体は、１２個のエッジおよび８個の隅部に沿ってＧ１ではなく、無限に薄い円錐は、その頂点でＧ１ではない。同様に、曲線については、（法平面に対して垂直である）その接ベクトルが連続である場合、曲線はＧ１である。非Ｇ１連続は、１つまたは複数の方向で無限曲率の領域と考えることができるため、しばしば「鋭い」不連続と呼ばれる。
【００６２】
図９は、曲線内の鋭い隅点に関連付けられた接ベクトルを示す。経路がＧ１連続である点では、この１組は、その曲線に対する単位接線からなる。
【００６３】
曲線上の点と単位接ベクトルとの関係を逆転し、各単位接ベクトルに関連付けられた曲線上の点の集合を得る。円形経路の場合には、各単位接ベクトルに関連付けられた２つの点があり、その単位接ベクトルは、その接線に対して垂直なダイアゴナルの端部で、それらの２つの点によって定義される。多角形経路の場合には、その多角形の１つまたは複数の隅部が、その多角形の辺の１つに対して平行でも逆平行でもない各単位接線に関連付けられる。
【００６４】
単位接ベクトルと境界点の集合との逆の関係を解析し、曲線内の「シルエット」方向を識別する。一実施形態では、シルエット方向の集合は、曲線の直線領域の単位接線と変曲点の単位接線の和集合である。曲線が１を超える巻数を有し、直線領域または変曲点がない場合には、シルエット方向の集合は、任意に選択し変曲点として扱うことができる単一の単位接ベクトルであるように定義される。この構造は、通常、曲線が自己交差しないものであり、変曲点を有していない場合、必要とされない。単一のシルエット方向は、一般に、曲線のどの領域も１を超える巻数を有さないようにすることに留意されたい。
【００６５】
上記で論じた、電極運動に対する軌道経路を得る演算（ブロック１２０）、および軌道経路形状を解析する演算（ブロック１２４）は、解析の結果を得るのに先立っていつでも実施することができる。一実施形態では、軌道経路の解析は、軌道経路形状の所定の集合に関するアプリケーション開発の時点で実施することができる。他の実施形態では、演算１２０、１２４は、実行時に、ＣＡＤモジュール１１２内の１つまたは複数のサブモジュールなど、１組の解析ルーチンによって実行することができる。いくつかの実施形態では、軌道経路の解析の一部分をアプリケーション開発の時点で実施することができ、解析の残りの部分を解析の結果の実施時に実施することができる。
【００６６】
（入力ソリッドモデルを解析する演算）
次いで、入力ソリッドモデルを解析するための演算が実施される（ブロック１２６）。一実施形態では、入力ソリッドモデル（すなわち、入力ＣＡＤモデル）を解析することは、軌道経路形状と、入力ＣＡＤモデルに対応する面の集合、エッジの集合、および頂点の集合とに基づいて、工具形状のソリッドモデル（すなわち、電極形状の出力ＣＡＤモデル）のための面の集合を導出することを含む。次いで、面の集合の部分集合を合成し、工具形状のソリッドモデルを生成する。一実施形態では、工具形状は、軌道経路形状に対する入力ＣＡＤモデルのミンコフスキー分解に対応する。
【００６７】
（ミンコフスキー分解の考察）
当業者には理解されるように、オブジェクトの並進運動によって掃引される点の軌跡は、「ミンコフスキー和」と呼ばれる数学的構造に関連する。２つの点集合Ａ、Ｂのミンコフスキー和は、ａをＡにおける変位、ｂをＢにおける変位として、ベクトルａ＋ｂによって原点から変位された点の集合として定義される。２つの点集合Ａ、Ｂのミンコフスキー和を計算するための演算は、「ミンコフスキー加算」と呼ばれる。したがって、オブジェクトの運動によって掃引される点の軌跡は、オブジェクトの形状Ｔと運動Ｐの経路のミンコフスキー和であり、掃引形状Ｓ＝Ｔ＋Ｐである。
【００６８】
ミンコフスキー加算に対応する逆問題は、一般に、「ミンコフスキー分解」と呼ばれる。ミンコフスキー分解は、所与の点集合Ｃについて、ミンコフスキー和Ａ＋ＢがＣに等しい１対の点集合Ａ、Ｂを決定する。加工工程では、一般に所望の形状Ｓと、工具形状Ｔまたは経路Ｐとが与えられ、一方、対応する経路Ｐまたは工具形状Ｔが計算されることになる。Ｔが与えられる場合には、ミンコフスキー分解は、ｐ、ｓ、ｔがそれぞれＰ、Ｓ、Ｔにおける変位として、すべての変位ｐ＝ｓ−ｔの集合によって定義される点集合を見つけることによって実施することができる。Ｐが与えられる場合には、ミンコフスキー分解は、ｔ＝ｓ−ｐである。分解される集合の１つが既知であるミンコフスキー分解のこの形態は、「ミンコフスキー減算」と呼ばれ、下記で論じるように、ミンコフスキー和によって表すことができる。
【００６９】
ミンコフスキー減算は、一般に、点集合のブーリアン補集合を定義することによって実施することができる。点集合Ａのブーリアン補集合！Ａは、Ａのメンバではない点を指す。たとえば、Ａが原点を中心とする半径ｒの球形ソリッドである場合には、！Ａは、原点を中心とする半径ｒの対応する球形キャビティであり、逆もまた同様である。同様に、点集合の原点を介する鏡映は、以下のように定義される。（−Ａ）がＡの原点を介する鏡映である場合には、Ａにおけるあらゆる変位ａについて、（−Ａ）における対応する変位−ａがあり、逆もまた同様である。
【００７０】
上記に基づいて、Ｔ＝Ｓ−Ｐ（ミンコフスキー減算）である場合には、！Ｔ＝！Ｓ＋（−Ｐ）（ミンコフスキー加算）であることを示すことができる。これは、Ｓ−ＰがＳ＋（−Ｐ）に等しくなく、むしろＴ＝Ｓ−Ｐ＝！（！Ｓ＋（−Ｐ））であることを意味する。掃引される体積（ｖｏｌｕｍｅ）で表せば、工具形状Ｔに対応するキャビティを取り囲む材料は、形状Ｓに対応するキャビティを取り囲む材料を経路（−Ｐ）に沿って移動することによって見つけることができる。
【００７１】
ミンコフスキー分解は、分解される点集合の１つが既知である場合でさえ、唯一の手順ではないことに留意されたい。具体的には、所与の点集合Ｃ、Ａについて、Ａ＋Ｂ＝Ｃになるような無限に多数の点集合Ｂが存在する可能性がある。一般に、可能な解集合Ｂは、和集合Ｃの内部の点だけに影響を及ぼす形状の変化によって差異を生じることになる。すなわち、可能な解集合Ｂは、Ａとの和によって「ウォッシュアウト（ｗａｓｈｅｄ  ｏｕｔ）」されるＢの変化に対応する。また、特定の点集合Ｃ、Ａについて、Ａ＋Ｂ＝Ｃになるような点集合Ｂが存在しない可能性もある。換言すれば、Ｃは、常にＡに対して分解することができるわけではない。これは、所望の形状Ｓを工具形状Ｔまたは経路Ｐに対して分解することができないとき、加工工程において問題とされ、この場合には、その形状は、特定の加工工程によって、それぞれその特定の工具形状または経路を使用して製造可能なものではない。
【００７２】
さらに、ソリッドを表す点集合のミンコフスキー和の計算は、これらのソリッドの境界のミンコフスキー和の計算によって、Ｂ−Ｒｅｐモデラ用に実装することができる。当業者には理解されるように、「境界表現」またはＢ−Ｒｅｐ法は、ソリッドをＣＡＤシステム内で表す方法を指す。この技法は、３次元ソリッドの「内側」の点を、そのソリッドの２次元境界の外向き法線と共に、その境界に基づいて表すことに基づく。Ｂ−Ｒｅｐモデラ内でミンコフスキー和を計算することで表せば、境界のミンコフスキー和は、以下のように定義することができる。Ｂｎｄ（Ａ）が点集合Ａの境界として定義される（この場合、工具経路など極めて薄い点集合の境界は、点集合それ自体であるように定義される）場合には、Ｂｎｄ（Ａ）は、それ自体が点集合であり、Ｂｎｄ（Ａ＋Ｂ）は、Ｂｎｄ（Ｂｎｄ（Ａ）＋Ｂｎｄ（Ｂ））の部分集合である。
【００７３】
換言すれば、Ｂ−Ｒｅｐモデルと工具経路のミンコフスキー和は、モデルの境界の、工具形状の境界とのミンコフスキー和の境界を計算し、次いでその境界をその和の境界として解釈し、得られるモデルの内部にある境界の部分を除去することに基づいて計算することができる。たとえば、Ｂｎｄ（Ａ）およびＢｎｄ（Ｂ）は、一般に、サーフェス、曲線、および点の集まりを指し、２つのサーフェスＳ１、Ｓ２のミンコフスキー和の境界は、一般に、Ｓ１とＳ２の畳み込みと呼ばれ、Ｓ１＊Ｓ２＝Ｂｎｄ（Ｓ１＋Ｓ２）として定義することができる。サーフェスの、曲線との畳み込み、または２つの曲線の畳み込みも同様に定義することができる。点の、サーフェス、曲線、または点との畳み込みは、その点と畳み込まれるオブジェクトの並進として定義される。したがって、ミンコフスキー和Ａ＋Ｂの境界は、境界の畳み込みによって表すことができ、Ｂｎｄ（Ａ＋Ｂ）は、Ｂｎｄ（Ａ）＊Ｂｎｄ（Ｂ）の部分集合である。
【００７４】
２つの点集合Ａ、Ｂの畳み込みＡ＊Ｂの特性は、ａがＡの要素であり、ｂがＢの要素であり、ａでのＡの接多様体がｂでのＢの接多様体に対して平行であるとして、すべての点ｃ＝ａ＋ｂの集合Ｃの部分集合になることである。これは、ＡをＢに沿って（またはＢをＡに沿って）移動することによって掃引される点の集合の包絡線の境界としてＡ＊Ｂを解釈することによって理解することができる。ＡがＢ内の特定の位置ｂで配置されたとき、ｂの接多様体に対してその接多様体が平行でないＡの境界上の任意の点ａは、ｂに近接するＢ内の新しい位置ｂ’にＡが微小運動した後で包絡線の内部上の点ｃ＝ａ＋ｂに対応することになり、それにより、それらの接多様体が平行であるａとｂの組合せだけが包絡線の境界内に現れることができ、したがって畳み込みの要素となることができる。次に、ミンコフスキー和の計算は、それらの接多様体が平行であるＡおよびＢの境界上でそれぞれ点ａ、ｂの対を識別することに分解することができ、そのような点の変位の和は、潜在的にミンコフスキー和の境界上にある点を定義することに留意されたい。本発明の実施形態によれば、ＣＡＤモジュール１１２内の解析ルーチンは、そのような点の１つまたは複数の対を自動的に識別することによってミンコフスキー和を計算するための実行可能命令を含む。
【００７５】
点のそのような対の識別に対する他の条件は、２つの集合Ａ、Ｂのミンコフスキー和の境界、Ｂｎｄ（Ａ＋Ｂ）が、ＡとＢの境界の畳み込みＢｎｄ（Ａ）＊Ｂｎｄ（Ｂ）の部分集合であることを想起することによって得ることができる。Ｂｎｄ（Ａ）およびＢｎｄ（Ｂ）が共に適正な境界である、すなわち、Ｂｎｄ（Ａ）またはＢｎｄ（Ｂ）の要素でないそれぞれＡおよびＢの「内部」点が存在する場合には、一般に、畳み込みＢｎｄ（Ａ）＊Ｂｎｄ（Ｂ）の２つの接続された構成要素がある。これらの２つの構成要素は、識別されたＢｎｄ（Ａ）内の点ａおよびＢｎｄ（Ｂ）内の点ｂで「外向き」（内部から離れる）法線を調べることによって特徴付けることができ、一般に、一方の構成要素は、法線間で正のドット積（ｄｏｔ  ｐｒｏｄｕｃｔ）を有することになり、一方、他方の構成要素は、法線間で負の内積を有することになる。外向きにオフセットするとき、負の構成要素は、一般に、全体としてミンコフスキー和Ａ＋Ｂの内部上にあることになり、その結果、廃棄することができ、同様に、正の構成要素は、内向きにシェルする（ｓｈｅｌｌｉｎｇ）とき、廃棄することができる。本発明の実施形態によれば、識別された点ａと点ｂとの、このより強い対応関係は、「有向の（ｄｉｒｅｃｔｅｄ）」対応関係と呼ばれ、この対応関係は、ａ＋ｂが含まれる構成要素の特徴付けに基づいて「平行」または「逆平行」とすることができる。上述のように、ＣＡＤモジュール１１２内の解析ルーチンは、そのような点の１つまたは複数の対を自動的に識別することによってミンコフスキー和を計算するための実行可能命令を含む。
【００７６】
当業者には理解されるように、鋭い不連続は、２つのオブジェクト（サーフェスまたは曲線）の畳み込みを計算するとき、複雑さの１つの発生源である。というのは、接多様体が、不連続の点のところで単一値でないからである。概念上の解決策は、特異点付近で、大きい、しかし有限の曲率を有する１組のサーフェスの限界（ｌｉｍｉｔ）として不連続サーフェスを扱うことにより、無限曲率を調節することである。畳み込みを計算することで表せば、これは、一方のサーフェスの鋭い不連続上の特定の点が、一般に、他方のサーフェス上の１つまたは複数の（点ではなく）領域に対応することになることを暗示する。これは、追加の面が、一般に畳み込みに追加され、寸法におけるこの高さ（ｅｌｅｖａｔｉｏｎ  ｉｎ  ｄｉｍｅｎｓｉｏｎ）を表すことになることを暗示する。本発明のいくつかの実施形態によれば、これは、適切な追加の面を導入するように、任意の鋭い不連続に対して半径ゼロのフィレットを実行することによって実施される。
【００７７】
（入力ソリッドモデルを解析する演算の詳細な考察）
入力ＣＡＤモデルを解析する演算１２６を実施することに関する考察に戻ると、一実施形態では、入力ＣＡＤモデル内の不連続は、そのトポロジに、立方体のエッジおよび頂点など「鋭い」エッジおよび隅部を関連付けることによって識別される。入力ＣＡＤモデル境界上の非Ｇ１フィーチャ（ｆｅａｔｕｒｅ：形態）は、一般に、それらに関連付けられた複数の表面法線を有し、その結果、ミンコフスキー和オフセットを実施したとき、出力ＣＡＤモデル境界上の領域に対応する可能性がある。これは、一般に、外向きにシェルするとき凸形のエッジおよび頂点がその場合であり、内向きにシェルするとき凹形のエッジおよび頂点がその場合であり、この文脈における「凸」または「凹」は、エッジまたは頂点に隣接する面法線間の角度を指す。本明細書では、「ローリングボールオフセット（ｒｏｌｌｉｎｇ−ｂａｌｌ  ｏｆｆｓｅｔ）」とも呼ばれる「ミンコフスキー和オフセット」は、オフセットモデルがボディを経路に沿って移動することによって掃引される点の集合を表す、オフセットさせる演算を指す。（球形の経路に対応する）一定のオフセット演算については、これにより、鋭いエッジが、円形断面を有する面によって置き換えられ、一方、鋭い頂点は、球形の面によって置き換えられる。これに対して、また当業者には理解されるように、ＣＡＤオフセットは、鋭いエッジおよび頂点に隣接するサーフェスを延長し、オフセットモデル上で新しい鋭いエッジおよび頂点を得るように、それらのサーフェスを再交差させる。
【００７８】
図１０は、モデルの境界上の鋭いエッジと関連付けられた複数の表面法線を横断面図で示す。表面法線１６２が発散しつつある場合には、鋭いエッジ１６０は、凸形エッジと呼ばれる。他方、表面法線が収束しつつある場合には、鋭いエッジは、凹形エッジと呼ばれる。図１１は、モデルの境界上の凸形エッジ１６４および凹形エッジ１６６を示す。本明細書では、外向きにオフセットするとき、凸形エッジは、「膨張する」エッジと呼ばれ、一方、凹形エッジは、「収縮する」エッジと呼ばれる。内向きにオフセットするとき、凸形エッジが「収縮する」エッジと呼ばれ、凹形エッジが「膨張する」エッジと呼ばれる。図１１はまた、接エッジ１６８と、凹形エッジ１６６に隣接する１組の面１７０とを横断面図で示す。
【００７９】
特定の実施形態では、入力ＣＡＤモデルを解析する演算１２６は、新しい面を導入することによって、出力ＣＡＤモデル上で新しい領域を表すことを含む。その結果、入力ＣＡＤモデル上のあらゆる鋭いフィーチャについて、半径ゼロのローリングボールオフセットに対応する幾何形状を有する１つまたは複数の新しい面が導入される。「膨張する」という分類は、エッジ全体にわたる凸性に左右されるため、入力ＣＡＤモデル内の混合エッジは、限定された凸性（凸、接線、または凹）のエッジに分割される。（「膨張」に似ているが、凸性が反転された）「収縮」しつつある鋭いフィーチャがある場合には、これらのフィーチャは、軌道運動のため一般に加工することができないモデル内のフィーチャを示す。一実施形態では、製造不能警報が要求された場合、エンドユーザに通知される。いくつかの実施形態では、また下記でより詳細に論じるように、入力ソリッドモデルを解析する演算中に、幾何解析をも実施し、自己交差するオフセットサーフェス幾何形状を生じる幾何構成を探索することによって、製造不能な部分を検出することができる。
【００８０】
ＥＤＭ電極の状況では、内向きにオフセットすることによって得られる電極形状は、最大の量の材料を含めることに対応することに留意されたい。電極を軌道経路に沿って移動することによって掃引される体積が変更されない限り、追加の材料を電極から除去することができる。これに関する基準は、基本的に２つである。すなわち、材料の除去により、一般に電極の内部にボイド（ｖｏｉｄ：空間）を導入することはできず、材料の除去により、一般に、所望の形状（元のモデル）の有限面積領域内にマップされる電極（オフセットモデル）の境界のどの領域をも除去することはできない。たとえば、内向きにシェルするときの膨張する鋭いエッジの状況では、隣り合うサーフェスが延長され再交差される標準的なＣＡＤオフセット技法を使用し、そのエッジに関連付けられたオフセットモデルの領域を表すことができる。これは、面の幾何形状が、エッジの形状の、経路とのミンコフスキー和に対応する、エッジに対応する面を追加する技法と対照的なものである。
【００８１】
さらに、平面的な軌道経路については、表面法線が軌道平面に対して垂直である（すなわち、経路に対する接線が法線に対して垂直である）入力ＣＡＤモデル上の点は、その経路内の点すべてに対応するため、特別なものである。本明細書では、そのような点は「例外」点と呼ばれ、入力ＣＡＤモデルの境界上の例外点すべての集合は、任意の数の孤立点（例外点）、１Ｄ曲線（例外曲線）、および２Ｄ領域（例外領域）の集まりである。その軸が軌道平面に対して垂直であるトーラスは、２つの例外曲線、すなわちトーラスの上部および下部にある平坦な円を有する。
【００８２】
図１２は、そのようなトーラスに関する上部例外曲線１６９を示す。そのトーラスは、軸が軌道平面に対してもはや垂直でないようにわずかに傾けられた場合には、４つの孤立例外点、すなわち軌道平面の法線の方向にある２つの極値（ｅｘｔｒｅｍａ）、ならびに短いダイアゴナルに沿ったこれらの極値の反対側の、対応する鞍点を有する。球は、２つの孤立例外点、すなわち北極と南極（この場合、赤道は、軌道平面内にあるように定義される）を有する。例外フィーチャの重要性は、出力ＣＡＤモデル上で、入力ＣＡＤモデル上とは異なる次元数を有する可能性があることである。典型的には、凸形ソリッドを外向きに、または凹形ソリッドを内向きにオフセットするとき、フィーチャの次元は、経路の次元だけ、最大最終の２次元まで増大される。その結果、曲線（１Ｄ）である軌道経路については、元のモデル上の例外点（０Ｄ）は、オフセットモデル上の例外曲線（１Ｄ）に対応し、例外曲線（１Ｄ）は、例外領域（２Ｄ）に対応し、例外領域（２Ｄ）は、（最大２Ｄにより）例外領域に対応する。埋められている軌道経路（２Ｄ領域）については、元のモデル上の例外点、例外曲線、例外領域は、一般にすべて、オフセットモデル上の例外領域に対応する。一実施形態では、新しいフィーチャは、オフセットモデル内で、軌道経路のサイズ限界ゼロ（ｚｅｒｏ−ｓｉｚｅ  ｌｉｍｉｔ）に対応する新しい（例外領域に関して）面または（例外曲線に関して）エッジを導入することによって表される。これらの面は、それらのエッジ幾何形状が新しいオフセットされたエッジ幾何形状で置き換えられたとき、ゼロでない面積を獲得することになる。逆に、凸形ソリッドを内向きに、または凹形ソリッドを外向きにオフセットするとき、フィーチャの次元が減少される可能性がある。本明細書では、「元のモデル」および「オフセットモデル」という用語は、一実施形態において、それぞれ入力ＣＡＤモデル、および出力ＣＡＤモデルに対応する。
【００８３】
当業者にはさらに理解されるように、シルエットフィーチャは、軌道経路内の境界領域から現れる。入力ＣＡＤモデル上の特定の面と、出力ＣＡＤモデル上の対応する面との間のマッピングが、確実に単一の領域を含むようにするために、表面法線が任意の領域の任意の端点で接ベクトルに対して垂直であるシルエット曲線に沿って（シルエット方向）、（元の面を分割する）シルエットエッジがモデルに挿入される。図１３は、変曲点および直線領域によって引き起こされるシルエット方向を示す。図の例では、符号１７２は、シルエット方向を示し、符号１７４は、直線領域を示し、符号１７５は、軌道経路１７６内の変曲点を示す。軌道経路内の追加の領域が、それぞれ符号１７８、１８０、１８２によって示されている。
【００８４】
したがって、入力ＣＡＤモデルは、図１４に横断面図で示されているように、（例外フィーチャによって上部および下部で結合された）垂直「ストリップ」に分けられる（ｓｅｇｒｅｇａｔｅｄ）。ストリップ１８４は、ある領域の内部上の任意の点が、あるストリップ上の内部点に対応する場合には、そのストリップ上の各点が、その領域内の少なくとも１つの点に対応する特性を有し、この場合、この文脈における「対応する」は、対応する点での接多様体が平行であることを示す。シルエットエッジは、符号１８６によって示されている。特に、符号１８５は、図１３における直線領域１７４に対応するシルエットエッジを示す。このシルエットエッジは、直線領域に対応するため、（面積ゼロの）シルエット面がエッジに沿って追加されることになる。
【００８５】
図１４はまた、ストリップと領域との対応関係を示す。具体的には、図１４は、図１３における領域１７４、１７８、１８０、１８２に対応するストリップ１８８、１８９、１９０、１９１、１９２、１９３を示す。特に、（たとえば、図１３における埋められている経路により）上記で論じた「平行」の有向対応関係だけを使用したとき、ストリップ１８８は領域１７８、１８０、１８２に対応し、ストリップ１８９は領域１７８、１８０、１８２に対応し、ストリップ１９０は領域１８２に対応し、ストリップ１９１は領域１８２に対応し、ストリップ１９２は領域１７８に対応し、ストリップ１９３は領域１７８に対応する。凹形領域１８０に対応するストリップは、それぞれ合計３つの領域に対応し、一方、凹形領域に対応しないストリップは、それぞれ１つのストリップにしか対応しないことに留意されたい。すなわち、これは、ストリップの凸性と経路の凸性が一致しない領域内で、ストリップの横断面図上の点間の、経路上の対応する点との同一性を「遡る（ｂａｃｋｔｒａｃｋｉｎｇ）」ことから理解することができる。上記で論じた（内向きの関係を外向きの関係から区別する）有向対応関係については、ストリップ上の各点は、その領域が直線でない限り、その領域内の点１つだけに対応する。有向対応関係は、埋められている平面的な経路の場合に問題とされ、元のモデルの表面法線の投影が、それらの２つの点において内部から離れる方向で、曲線に対する法線に対して（逆平行ではなく）平行であることを示す。平行の分岐および逆平行の分岐は、一般に同じオフセットストリップに寄与しないため、元のストリップのパラメータ化を使用し、オフセットストリップをパラメータ化することができる。
【００８６】
図１５は、図１４に示されている入力ＣＡＤモデルを、図１３に示されている（埋められている）経路１７６に沿って掃引することで生まれるボディを示す。一実施形態では、このボディの境界は、オフセットストリップ１９４〜２０３と、シルエット面２０４とで構成される。オフセットストリップ１９４〜２０３のそれぞれは、図１４におけるストリップと図１３における領域との対応関係に対応し、一方、シルエット面２０４は、図１４におけるシルエットエッジ１８５と図１３における直線領域１７４との対応関係に対応する。具体的には、オフセットストリップ１９４は、ストリップ１８９と領域１７８との対応関係によって生成され、オフセットストリップ１９５は、ストリップ１８９と領域１８０との対応関係によって生成され、オフセットストリップ１９６は、ストリップ１８８と領域１８０との対応関係によって生成され、オフセットストリップ１９７は、ストリップ１８８と領域１８２との対応関係によって生成され、オフセットストリップ１９８は、ストリップ１８９と領域１８２との対応関係によって生成され、オフセットストリップ１９９は、ストリップ１９０と領域１８２との対応関係によって生成され、オフセットストリップ２００は、ストリップ１９１と領域１８２との対応関係によって生成され、オフセットストリップ２０１は、ストリップ１９２と領域１７８との対応関係によって生成され、オフセットストリップ２０２は、ストリップ１９３と領域１７８との対応関係によって生成され、オフセットストリップ２０３は、ストリップ１８８と領域１７８との対応関係によって生成される。この場合も、これらの対応関係は、個々の点を経路に沿って移動し、ストリップ上で対応する点を探すことを考えることによって理解することができる。
【００８７】
図１６は、本発明の他の実施形態による、元のモデル上のストリップの、オフセットモデル上のストリップへのマッピングを示す。元のモデル２０５上の各ストリップ２０７または２０８は、特定の領域および法線の向きを介して、オフセットモデル２０６上の対応するストリップ２０９、２１０にマッピングすることができる。オフセットモデル２０６の境界は、元のモデル２０５の境界の、マッピング後のストリップによってカバーされるものと考えることができ、元のモデル２０５のある特定のストリップは、オフセットモデル２０６の１つまたは複数のストリップにマッピングされる。一実施形態では、図１６に示されているように、各ストリップの重複度がマッピングの重複度と合致するように、ストリップが元のモデル２０５上でコピーされる。次いで、元のモデル２０５上の各コピーされたストリップは、オフセットモデル２０６上のストリップと「１対１」マッピングされる。
【００８８】
元のモデル２０５からオフセットモデル２０６へのストリップのマッピングは、オフセットモデル２０６を全体的にカバーしない可能性があることに留意されたい。一般にストリップ解析に参加しない例外面、および鋭いフィーチャから現れる面の他に、軌道経路の直線領域に対応するオフセットモデル２０６の境界の領域もある。これらの領域の幾何形状は、シルエット曲線をシルエット方向で掃引することに対応する。一実施形態では、そのような面は、同じシルエット方向２１２を有するシルエット面２１３にもはや隣接していないシルエットエッジ２１１を識別することによって表される。そのエッジ２１１は、同じシルエット方向２１２を有するシルエット面２１３で置き換えられ、面２１３は、図１６にさらに示されているように、シルエット方向２１２でのシルエット曲線の掃引に対応する幾何形状を有する。ある特定のエッジが複数のシルエット方向に対応する場合、そのエッジは、複数の面で置き換えることができることに留意されたい。たとえば、図１７は、三角形（垂直）プリズム２１５、および方形の軌道経路２１４を示す。シルエットエッジ２１６は、三角形２１５の非例外エッジである。これらのエッジのうちの１つ２１７が、オフセットモデル２２０上で２つのシルエット面２１９に関連付けられる。
【００８９】
元のモデルのストリップの様々なコピーが、オフセットモデルの境界をカバーするが、一般的なストリップ間の隣接関係は、スクランブルされる可能性がある。この問題に対処するための１つの方法は、すべてのシルエットおよび例外エッジに沿ってモデルをステッチ解除し、次いで、下記で述べるように、トポロジ修復段階中に、オフセットモデル上でストリップを再ステッチすることである。
【００９０】
オフセットサーフェス境界をパラメータ化する際に必要とされる１つの態様は、元のモデルの境界上の、例外点の（またシルエット点が存在すればその）存在から生じる。元のモデルの境界上の例外点は、一般に、曲線（または例外領域の境界を定める曲線）にマッピングされる。例外点が埋め込まれるサーフェスが、その点で（たとえば、球の北極での緯度／経度における特異点のような）半径方向パラメトリック特異点（ｒａｄｉａｌ  ｐａｒａｍｅｔｒｉｃ  ｓｉｎｇｕｌａｒｉｔｙ）を有する場合には、角度座標θを使用し、曲線をパラメータ化することができる。そうでないときには、一般に、元のサーフェス上の単一の座標値が、オフセットサーフェスの境界曲線全体にマッピングされ、これは、オフセットサーフェスが前記境界に沿って非Ｃ０不連続を有することを暗示することを、当業者なら理解するであろう。この問題に対処するための１つの方法は、元のモデルの境界から小さな円盤（ｄｉｓｋ）を切り取り、そのサーフェスが適切なパラメトリック特異点を有する面と置き換えることである。１つのそのようなサーフェスは、円盤の境界と例外点の間を補間する、またこの領域内で元の幾何形状を近似する、周期的なエルミートＢスプラインパッチである。元のサーフェス幾何形状に合致する置換え用円盤が望ましい場合には、Ｂスプラインパッチを使用し、元の形状を複製する手続きサーフェスをパラメータ化することができ、それは、たとえば、垂直投影技法を使用し、Ｂスプラインパッチ上の点から元のサーフェス上に投影し、特定のパラメータ値に関するその形状関数の値が元のサーフェス内への投影の結果によって決定される手続きサーフェスを得ることによる。
【００９１】
（入力ソリッドモデルを解析する演算の特定の実施形態）
特定の実施形態では、入力ＣＡＤモデルを解析する演算１２６は、入力ＣＡＤモデル内の面の集合内の各面に対応する工具形状のソリッドモデル用の１組の面を、入力ソリッドモデル内の面の集合に関連付けられた幾何形状の部分集合を軌道経路形状の部分集合と畳み込むことによって導出することを含む。工具形状のソリッドモデル内の面の集合の部分集合の各面上の各点は、軌道経路形状に関する入力ＣＡＤモデルの、特定のミンコフスキー分解の境界上にある。具体的には、入力ソリッドモデル内の各面をミンコフスキー分解の境界上にある軌道経路形状と畳み込んだものにある各点は、工具形状のソリッドモデルに対応する面の集合内に含まれる。入力ソリッドモデル内の各点に対応する１組のエッジおよび頂点も、同様に導出される。
【００９２】
例示的な１組の演算において、入力ＣＡＤモデルを解析する演算１２６は、以下のように実施される。
【００９３】
非Ｇ１面を不連続に沿って分割することによって、各面のサーフェスが、どこでも確実に、少なくともＧ１連続となるようにする。
【００９４】
入力ＣＡＤモデル内の各面について、その面のサーフェス上のすべての例外点および／またはシルエット点の集合が決定される。本明細書では、「例外点」は、表面法線が経路の平面に対して垂直である点を指し、「シルエット点」は、表面法線が、経路を描く曲線のシルエット方向に対して垂直である非例外点を指す。一実施形態では、例外点および／またはシルエット点の集合は、孤立例外点および／または孤立シルエット点、例外曲線および／またはシルエット曲線、ならびに／あるいは２次元例外領域および／または２次元シルエット領域の集まりを含む。例外曲線および例外領域は、幾何学的に平面のものであり、一方、シルエット領域は、概して線引きされる（ｔｙｐｉｃａｌｌｙ  ｒｕｌｅｄ）ことに留意されたい。
【００９５】
入力ＣＡＤモデル内の各２次元例外領域が、平面的な面で置き換えられる。
【００９６】
各例外曲線またはシルエット曲線に沿って１つまたは複数の新しいエッジを挿入することによって、入力ＣＡＤモデルが分割される。外向きにオフセットするとき、各凸形の例外点の周りの小さな隣接物は、そのサーフェスが半径方向座標でパラメータ化され、その原点が例外点にあり、頂点が例外点にある面と置き換えられる。典型的にはＥＤＭ電極形状を計算する場合のように、内向きにオフセットするとき、そのような凹形の点が置き換えられる。置換え用面の幾何形状は、一実施形態では、それが取って代わる元の幾何形状に対する近似、または別の実施形態では、あらゆる所で元の幾何形状と同じ場所を占め、しかし異なる（半径方向）座標を有する、手続き上定義されたサーフェスとすることができる。そのような近似の例は、Ｂスプライン近似を含むことができる。
【００９７】
あらゆるエッジが、そのエッジに沿った各点でのボディの凸性に従って、「凸形エッジ」「凹形エッジ」「接エッジ」、または（凸形領域と凹形領域を共に含めて）「混合エッジ」として分類される。
【００９８】
混合凸性エッジすべてが、その凸性が変化する各点で分割される。
【００９９】
例外面およびシルエット面すべてが識別される。例外面は、その法線が例外方向を指す平面的な面であり、一方、シルエット面は、その法線が、あらゆる点でシルエット方向に対して垂直である面である。
【０１００】
「膨張する」エッジおよび頂点すべてが識別される。外向きにオフセットするときには、エッジの場合に例外面またはシルエット面に隣接していない限り、凸形エッジおよび頂点が膨張しつつある。典型的にはＥＤＭ電極形状を計算する場合のように、内向きにシェルするときには、エッジの場合に例外面またはシルエット面に隣接していない限り、凹形エッジおよび頂点が膨張しつつある。
【０１０１】
「収縮する」エッジおよび頂点すべてが識別される。
【０１０２】
何らかの収縮するエッジまたは頂点が存在し、ユーザが製造不能通知を要求している場合、そのモデルの製造不能を示すものがユーザに通知される。
【０１０３】
各膨張する例外エッジは、そのエッジの、並べられたコピー（ｓｉｄｅ−ｂｙ−ｓｉｄｅ  ｃｏｐｉｅｓ）によって境界が定められた、かつその幾何形状が、エッジの幾何形状を埋め込むことができる例外平面である、面積ゼロの例外面と置き換えられる。本明細書では、「例外エッジ」は、例外曲線に沿って走るエッジを指す。
【０１０４】
直線領域に対応する各膨張するシルエットエッジまたは接シルエットエッジは、そのエッジの、並べられたコピーによって境界が定められた、かつそのエッジがそのような面にすでに隣接していない限り、その幾何形状が、シルエット（直線領域）方向でエッジ幾何形状を直線掃引したものである、面積ゼロのシルエット面と置き換えられる。膨張するシルエットエッジについては、複数の直線領域に対応する複数のシルエット方向との互換性により、一般に、複数のそのようなシルエット面を挿入することができる。その場合には、法線方向が単調に回転するように面を順序付けることができる。
【０１０５】
各膨張する非シルエットエッジおよび非例外エッジは、そのエッジの、並べられたコピーによって境界が定められた、かつその幾何形状が、そのエッジに沿った半径ゼロのフィレットの幾何形状である、面積ゼロの面と置き換えられる。
【０１０６】
各膨張する例外点は、微小円形エッジによって境界が定められた、かつその幾何形状が、その点の表面法線に対応する例外平面である、面積ゼロの例外面と置き換えられる。
【０１０７】
シルエットエッジがある場合、そのモデルは、これらのエッジに沿ってステッチ解除される。
【０１０８】
モデル上のストリップが、ステッチ解除されたシルエットエッジと、例外面に隣接するエッジとによって境界が定められた面の集まりとして識別される。
【０１０９】
各ストリップについて、ストリップをモデルの残りの部分に接続するエッジまたは頂点があればそれらが識別され、そのモデルが、これらのエッジおよび頂点に沿ってステッチ解除される。ストリップの境界内の他のどのエッジもすでにステッチ解除されていることになるので、これらのエッジは例外となることに留意されたい。
【０１１０】
非シルエット面を有する各ストリップについて、非シルエット、非例外テスト点があればそれが識別され、経路を描く曲線上の対応する点が決定される。曲線である経路については、対応する点は、そのテスト点で軌道平面に対しても表面法線に対しても垂直な単位（接）ベクトルに関連付けられた点である。領域である経路については、外向きにオフセットするとき、その領域に対する２Ｄ法線が表面法線ベクトルの、軌道平面内への投影に対して平行であるというさらなる制約が、対応する点の集合に課される。内向きにオフセットするときには、ベクトルは逆平行である。各対応する点について、その点を含む経路を描く曲線上の領域が決定される。さらに、その点は、外向きの２Ｄ法線が表面法線の、経路の平面内への投影に対して平行であるか、それとも逆平行であるかについて特徴付けられる。領域については、外向きの２Ｄ法線は、その領域の法線である。２Ｄ領域の境界である曲線については、外向きの２Ｄ法線は、その領域の法線である。２Ｄ領域の境界でない曲線については、外向きの２Ｄ法線は、接線がその曲線に沿った経路の平面に対する法線のクロス積（ｃｒｏｓｓ  ｐｒｏｄｕｃｔ）として任意に定義され、この場合、曲線の方向は、一貫しているが任意である。曲線のこの領域は、２Ｄ法線の特徴付けを伴って、一実施形態では「分岐」と呼ばれる。
【０１１１】
シルエット面からなる各ストリップについて、同様の解析が実施される。各ストリップは、変曲点および／または直線領域の何らかの集合に対応することになり、各直線領域については、その領域内の任意の対応する点は、その領域を特徴付けるために選択すべきである。これらの変曲点および／または直線領域は、２Ｄ法線のそれらの特徴付けを伴って、同様に一実施形態では「分岐」と呼ばれる。
【０１１２】
各ストリップについて、また第１のものを除く前記ストリップに対応する各分岐について、ストリップがコピーされ、次いで、原点を含めてストリップの各コピーが、異なる分岐に関連付けられる。
【０１１３】
（新しい幾何形状を作成する演算）
新しい幾何形状を作成する演算が実施される（ブロック１２８）。新しい幾何形状は、一実施形態では、特定のストリップの幾何形状を、対応する特定の分岐の幾何形状と畳み込むことによって定義される。これは、ストリップ上の各点について、分岐上の対応する点を見つけ出し、分岐上のその点の位置を変位として扱うことによって決定される変位を追加することによって行われる。ＣＡＤモデラ内の機能は、「手続き」サーフェスに対するサポートであり、この場合、特定のサーフェスの形状関数は、「プロジェニタ（ｐｒｏｇｅｎｉｔｏｒ）」と呼ばれる他のサーフェスまたは曲線の形状関数に依存する可能性がある。たとえば、ローリングボールフィレットサーフェスの形状関数は、一般に、そのフィレットに隣接するサポート面の形状関数に依存する。一定のオフセットでは、オフセットサーフェス形状は、以下のように、元のサーフェス位置を表面法線の方向で距離Ｄだけ変位することによって定義される。すなわち、Ｃ（ｕ，ｖ）＝Ａ（ｕ，ｖ）＋Ｄ＊Ｎ＿Ａ（ｕ，ｖ）であり、上式で、Ｃ（ｕ，ｖ）は、オフセットサーフェスを描く形状関数であり、Ａ（ｕ，ｖ）は、元のサーフェスを描く形状関数であり、Ｎ＿Ａ（ｕ，ｖ）は、パラメータ値（ｕ，ｖ）でのサーフェスに対する単位法線ベクトルである。Ｄ＊Ｎ＿Ａは、元のサーフェスＡがそれに沿って並進されたときオフセットサーフェスＣを生成する経路に対応する球上の点に対する変位ベクトルであることに留意されたい。また、正のＤは、外向きにオフセットすることを示し、一方、負のＤは、内向きにオフセットすることを表すことに留意されたい。非球形経路を有するＥＤＭの場合には、元のサーフェス位置とオフセットサーフェス位置との差は、その接空間がＮ＿Ａ（ｕ，ｖ）に対して垂直である経路上の点に対応する変位ベクトルである。すなわち、Ｃ（ｕ，ｖ）＝Ａ（ｕ，ｖ）＋Ｂ＿ｉ（Ｎ＿Ａ（ｕ，ｖ）；ｕ，ｖ）であり、上式で、Ｃ、Ａ、およびＮ＿Ａは、前述のように定義され、一方、Ｂ＿ｉは、Ａの表面法線を軌道経路上の点にマッピングする連続変位関数であり、その結果、軌道経路上のそのような点での接多様体が、その表面法線が直交するＡ上の接多様体に対して平行になる。下付き文字「ｉ」は、特定の軌道経路形状が複数の変位関数Ｂ＿ｉ（Ｎ（ｕ，ｖ）；ｕ，ｖ）を生成することができることを示すものとし、一方、追加の引数ｕ、ｖは、（連続性上の理由で）特定のＢ＿ｉを形成するために使用される軌道経路形状の特定の分岐がｕおよびｖに依存する可能性があることを示す。図１８は、オフセット演算を軌道経路形状の様々な分岐に対して実施することを示す。具体的には、図１８は、元のボディ上の特定の点を軌道経路の様々な分岐にオフセットする例示的な演算に対応する、変位ベクトル２２２、投影された表面法線２２４、経路に対する接線２２６、経路２２８、および元のボディ２３０を示す。
【０１１４】
複数の変位関数が、元のサーフェス上の特定のストリップ（上記の考察参照）と、オフセットサーフェス上の対応するストリップ、すなわち、あるストリップに関連付けられた複数の分岐との間の様々な変位に対応する。一実施形態では、サーフェス形状関数Ｃ（ｕ，ｖ）を、手続きサーフェスを可能にするＣＡＤモデル内で表すことができる。
【０１１５】
当業者には理解されるように、ＣＡＤモデラは、一般に、サーフェスを何らかのｕｖ矩形内で数学的に行儀よく振る舞う（たとえば、連続する、自己交差しない、など）ように定義する。また、ＣＡＤモデラは、一般に、たとえばＣＡＤオフセットまたはフィレット演算を実施するとき、サーフェスをそれらの元のｕｖ矩形を越えて延長する。そのようなパラメトリック矩形が例外曲線またはシルエット曲線を含む場合には、変位関数Ｂ＿ｉ（Ｎ（ｕ，ｖ）；ｕ，ｖ）は、一般に、ｕｖ矩形の様々な領域内で様々な分岐に関連付けられ、分岐間の変化は、例外曲線またはシルエット曲線に沿って生じる。一実施形態では、「分岐スイッチャ（ｂｒａｎｃｈ  ｓｗｉｔｃｈｅｒ）」オブジェクトが、オフセットモデル内の各サーフェスについて導入され、そのサーフェスに対応する面内の較正点が決定される。較正点（ｕ０，ｖ０）では、Ｂ＿ｉは、特定の分岐上にあるように選択され、分岐のこの選択は、Ｂ＿ｉのＧ０連続をパラメトリック矩形全体に課すことによって、（ｕ０，ｖ０）から離れるように延長される。たとえば、円など単純な経路については、一般に２つの分岐、すなわち「外向き」（投影された法線に対して平行な方向でオフセットする）および「内向き」（逆平行の方向でオフセットする）がある。外向きにオフセットする場合には、テスト点、および例外曲線と交差することなしにテスト点から到達可能な点すべてにおいて、「外向き」分岐が選択される。（高次の根（ｈｉｇｈｅｒ−ｏｒｄｅｒ  ｒｏｏｔ）がないものと仮定して）単一の例外曲線と交差することによって到達可能な点すべてが、一般に「内向き」分岐を使用する。偶数の例外曲線と交差することによって到達可能な点は、一般に「外向き」分岐を使用し、奇数の交差によって到達可能な点は、一般に「内向き」分岐を使用する。ちょうど例外曲線上の点に関する「外向き」と「内向き」の間の方向の曖昧さは、連続性の要件によって決定される、その曲線に沿った方向を指定することによって解決することができる。Ｂ＿ｉは、様々な領域（および例外曲線に沿った方向）の「外向き」と「内向き」の割当てを逆にすることに対応する。
【０１１６】
別の例では、円形経路、およびその軸が軌道平面に対して平行である（水平）円柱については、例外曲線は、パラメータ空間内で１／２周期だけ分離された直線の等値線である。これらの２本の線は、円柱を２つの（１／２円柱）領域に分離する。Ｂ＿ｉの一方は、第１の領域内の「外向き」分岐と、第２の領域内の「内向き」分岐とを使用し、一方、他方のＢ＿ｉは、第１の領域内の「内向き」分岐と、第２の領域内の「外向き」分岐とを使用する。
【０１１７】
図１９は、ＵＶ空間内で、各領域に１つずつ、１対の１／２円柱面に関する１対の分岐スイッチャを示す。完全円柱のＵＶ空間に対応する各ＵＶ矩形は、対応する面が部分集合である（完全円柱）サーフェス全体に関する連続性を維持するように、内向き分岐２３４と外向き分岐２３６の間で切り替わる。２つのＵＶ矩形は、符号２４２によって示されている。
【０１１８】
２つの分岐スイッチャ２３８、２４０は、軌道平面内で、円柱２４８をそれぞれ左２４４と右２４６に並進させることに対応し、この場合、左方向および右方向は、図２０に示されているように、円柱の軸に対して垂直なものとして定義される。符号２５０は、円柱上の例外エッジを示し、符号２５２は、円柱２４８上の面、および並進された円柱２４４上の対応するオフセット面を示し、符号２５４は、結果的として生じるボディ２４９の内部上にあり、その結果、結果的として生じるボディ２４９の境界を定義する面の境界の外側にあるオフセットサーフェス２４４、２４６の一部分を示す。これらの領域２５４はどちらも、図１９における内向き分岐２３４に対応することに留意されたい。面に対応するサーフェス幾何形状に加えて、ソリッドモデラは、一般に、エッジに対応する曲線幾何形状と、頂点に対応する点幾何形状とを有し、この追加の幾何形状もまた、オフセットすべきである。オフセットモデル内でエッジ（または頂点）に関する幾何形状を得るための１つの技法は、元の幾何形状を、元のエッジに隣接する面に対応する元のサーフェスの１つに埋め込まれものとして表すことであり、サーフェスパラメータ空間（ｕ，ｖ）内の曲線（または点）を生じる。次いで、オフセット曲線（または点）幾何形状は、オフセットサーフェス上の同じｕｖ曲線（または点）に対応する。オフセット曲線に関する特別な手続き幾何形状を実装することができ、またはそのような埋め込まれた幾何形状タイプをモデラ内に含めることができる。オフセット点幾何形状は、ＣＡＤモデラが一般に修正なしに表すことができるｘｙｚ位置である。
【０１１９】
（新しい幾何形状を作成する演算の特定の実施形態）
特定の実施形態では、新しい幾何形状を作成する演算（ブロック１２８）が、以下のように実施される。
【０１２０】
モデル内の各ストリップ上の非例外、非シルエット面については、新しい連続的なサーフェス幾何形状が定義され、この場合、各点の位置は、そのサーフェス上のその元の位置に、元の位置に関連付けられた１つの分岐上の対応する点によって定義される変位を加えた和として計算される。この演算は、面の内部上の非例外参照点と、経路を描く曲線の、対応する分岐とを識別することとして考えることができる。参照点に対応する新しいサーフェス幾何形状は、テスト点に関連する変位だけ並進されたテスト点の、そのストリップの分岐上の位置となるように定義される。次いで、面に対応する元のサーフェス内のすべての例外曲線またはシルエット曲線を決定することができる。これらの曲線は、元のサーフェスを、互いに疎な領域に区分する。各互いに疎な領域については、新しいサーフェスがＧ０連続となる要件に基づいて、分岐が選択される。一実施形態では、サーフェス上の各点について分岐分類を管理する、かつそのエバリュエータが、元のサーフェス上の点に適切な分岐からの変位を加算することに対応するサーフェスオブジェクトが作成される。複雑さの低減された経路形状とサーフェス形状の組合せについては、オフセット幾何形状の形状がモデラ内で表現可能である可能性があることに留意されたい。そのような場合には、手続きオフセット機構を使用するのではなく、適切なサーフェスを作成し使用することができる。たとえば、直線経路曲線については、オフセットサーフェスは、一般に、元のサーフェスの並進である。円形経路曲線については、（短径以下の長径を有する、自己交差する「渦」「レモン」「リンゴ」円環を含めて）球形および円環状の元のサーフェスは、一般に球または円環にオフセットされ、水平円柱（軸が軌道平面内にある）は、一般に、並進された円柱にオフセットされ、垂直円柱（軸が軌道平面に対して垂直）は、一般に、異なる半径を有する垂直円柱にオフセットされる。
【０１２１】
モデル内の各ストリップ上の各シルエット面については、新しいサーフェス幾何形状が、そのサーフェス位置に関連付けられた１つの分岐上の点によって定義される変位だけ元の幾何形状を並進（シルエット方向での直線掃引）することによって計算される。曲線の直線領域に対応するシルエット方向については、この並進は、その直線領域内の任意の点を使用して実施することができる。というのは、シルエット幾何形状は、一般に、シルエット方向での並進を受けても不変であるからである。
【０１２２】
幾何形状調整は、一般に、例外面については実施されない。というのは、それらの（平面的な）幾何形状は、軌道運動の方向で並進不変であるからである。しかし、面の範囲は、境界を定めるエッジおよび頂点の幾何形状の調整により、変化する可能性がある。
【０１２３】
少なくとも１つの非例外、非シルエット面に隣接する各エッジについては、エッジの曲線を隣接する非例外、非シルエット面に投影し、曲線上の各点の位置を、サーフェス上の投影された点の変位だけ変位させることによって、新しい幾何形状が計算され、新しい曲線オブジェクトが作成される。
【０１２４】
少なくとも１つの非例外、非シルエット面に隣接する各頂点については、頂点の位置を隣接する非例外、非シルエット面に投影し、頂点の位置を、サーフェス上の投影された点の変位だけ変位させることによって、新しい位置が計算される。次いで、新しい頂点位置オブジェクトが作成される。
【０１２５】
（元の幾何形状を新しい幾何形状と置き換える演算）
次いで、元の幾何形状を新しい幾何形状と置き換えるための演算が実施される（ブロック１３０）。
【０１２６】
新しいオフセット幾何形状が計算された後で、上記で論じた元のモデル内のあらゆる面、エッジ、頂点の（コピー）すべてについて、各面、エッジ、頂点の幾何形状が、対応するオフセット幾何形状と置き換えられる。すなわち、各新しいサーフェス、曲線、頂点位置について、対応する面、エッジ、または頂点の幾何形状が、新しい幾何形状と置き換えられる。いくつかの実施形態では、新しい幾何形状は、一般に手続き的なものであるが、軌道経路および元のサーフェス幾何形状の、いくつかの特別な構成では、オフセット幾何形状は、ＣＡＤモデラ内であまり複雑でない形で表すことができる形状とすることができる。
【０１２７】
（トポロジを修復する演算）
トポロジを修復するための演算が実施される（ブロック１３２）。幾何形状を置き換えた後で、オフセットモデル（すなわち、工具形状のソリッドモデル）のトポロジが修復される。場合によっては、修復演算は、元のモデルの修正を実施するための逆演算として考えることができる。修復演算を実施することは、たとえば、解析演算中にモデル内の面をコピーするステップを、トポロジ修復ステップ中に面の、同じ場所を占めるコピーを除去する演算と比較することなどによれば、（上記で論じた）解析演算１２４を逆にしたものとして考えることができる。初期の外向きオフセットの解析ステップによりトポロジ（たとえば、追加の面）がモデルに追加される場合、後続の、同一の内向きオフセット中の解析後トポロジ修復演算により、一般にそれらが除去されることになる。一実施形態では、トポロジを修復する演算（ブロック１３２）は、以下のように実施される。
【０１２８】
同じ場所を占める例外面またはシルエット面の、背中合わせの領域が検出され、その背中合わせの領域が除去される。これは、例外エッジの境界を定めるエッジの幾何形状を調整する間に作成される例外領域の膨張をアンドゥ（ｕｎｄｏ：取り消し）することとして考えることができる。
【０１２９】
面積ゼロである（すなわち、幾何学的にエッジまたは頂点に対応する）面およびエッジが検出され、対応するエッジまたは頂点と置き換えられる。これは、たとえば、例外エッジもしくは頂点、シルエットエッジもしくは頂点、または鋭いエッジもしくは頂点を置き換えるように、面積ゼロの面またはエッジが挿入されるアンドゥ演算として考えることができる。そのような面は、電極形状における鋭いエッジまたは頂点に対応するため、ＥＤＭ電極形状計算において共通のものとすることができる。
【０１３０】
隣り合うストリップは、それらの自由エッジに沿って共にステッチされる。この演算は、元のモデルをストリップに分解した、実施済みのステッチ解除をアンドゥすることとして考えることができる。
【０１３１】
同じ場所を占める面、エッジ、および頂点が検出され、重複がモデルから除去される。一例では、これは、上記で開示されている、ストリップをコピーする演算をアンドゥすることとして考えることができる。
【０１３２】
次いで、工具形状のソリッドモデルが自己交差を含むかどうか判定するためのチェックが実施される（ブロック１３４）。自己交差は、局所的にソリッドモデルの境界上にある点が、モデルの何らかの他の（非局所的な）領域のオフセットの内部にあることを暗示する。ＣＡＤオフセット演算を使用し、オフセット境界のナイーブな（ｎａｉｖｅ：単純な）境界内の自己交差を決定し、またこれらの自己交差を除去することができる。
【０１３３】
自己交差が見つけられた場合、その部分が製造可能なものではなく、オフセット演算は、失敗することも、オフセットモデルの内部上にある境界のそれらの部片を除去することによって自己交差を修復することによって進めることもできることが、ユーザに通知される（ブロック１３６）。換言すれば、そのような自己交差は、軌道経路に沿って並進されたとき、所望の形状のキャビティを焼き付けることができる電極形状がないことを示す。いくつかの実施形態では、自己交差検出はまた、工程内のより早期の演算として実施することができる。たとえば、特定の面のオフセットに関連付けられたサーフェス幾何形状が構築されつつあるとき、自己交差を求めてこの幾何形状を調べることができる。同様に、（エッジが微小オフセット後にモデルの内部にある）「収縮する」エッジは、オフセットモデルの境界内で自己交差を示す可能性がある。シルエット面または例外面に隣接するエッジは、オフセット演算によりエッジが面内で移動するため、一般に収縮していないことに留意されたい。
【０１３４】
次いで、クリーンアップおよび成功を示す演算が実施される（ブロック１３８）。上記で論じた演算（１２０〜１３８）の結果として、工具形状のソリッドモデルを表す出力ＣＡＤモデルが生成される。最終段階として、たとえば、（電極形状のモデルを得るために）そのブーリアン補集合をとることによって、またはＥＤＭ機械内で電極の設置を可能にするように、加工されることになる領域の外側でベース材料（たとえば、クランプ用固定具）を追加することによってなど、複数のソリッドモデリング（ＣＡＤ）演算を使用して、出力モデルをさらに処理することができ、その後で、成功を知らせることができる。一実施形態では、ＥＤＭ火花ギャップに関してモデルを補償することによってなど、モデルを標準的な方法でさらに処理することができる。
【０１３５】
当業者なら、本明細書に記載されている実施形態を開発する上で、追加の説明を必要としないが、非特許文献１、非特許文献２、非特許文献３、Ｇａｓｐａｒｒａｊの「A method for Under-sizing Electrodes for Polygonal Orbit Electric Discharge Machining」という名称の米国特許出願公開（特許文献１参照）、Ｓｔａｌｌｉｎｇｓらの「Method for Transforming CAD Model Using General Function Composition Mechanism」という名称の米国特許（特許文献２参照）には、軌道経路形状を計算し、ＣＡＤアプリケーションを使用して形状を変形することに関して何らかの有用な手引きを見つけることができ、これらの開示を全体として参照により本明細書に組み込む。
【０１３６】
本発明の一実施形態は、コンピュータによって実施される様々な演算を実施するためにコンピュータコードを有するコンピュータ可読媒体を備えるコンピュータ記憶製品に関する。この媒体およびコンピュータコードは、本発明のために特別に設計および構築されたものとすることも、コンピュータソフトウェアの当業者に周知かつ使用可能な種類のものとすることもできる。コンピュータ可読媒体の例には、それだけには限らないが、ハードディスク、フロッピディスク、および磁気テープなど磁気媒体、ＣＤ−ＲＯＭ、ＤＶＤ、およびホログラフィデバイスなど光媒体、光磁気媒体、ならびに特定用途向け集積回路（ＡＳＩＣ）、プログラマブルロジックデバイス（ＰＬＤ）、ＲＯＭデバイス、ＲＡＭデバイスなど、プログラムコードを記憶および実行するように特別に構成されるハードウェアデバイスが含まれる。コンピュータコードの例には、コンパイラによって生成されるものなどマシンコード、およびインタープリタを使用してコンピュータによって実行される、より上位のコードを含むファイルが含まれる。たとえば、本発明の一実施形態は、Ｊａｖａ（登録商標）、Ｃ＋＋、または他のオブジェクト指向プログラミング言語および開発ツールを使用して実装することができる。本発明の他の実施形態は、マシン実行可能ソフトウェア命令の代わりに、またはそれと組み合わせて、ハードワイヤード回路内で実施することができる。
【０１３７】
前述の説明は、本発明を完全に理解することができるように、説明のために特定の用語を使用している。しかし、本発明を実施するためにいくつかの詳細は必要とされないことが、当業者には明らかであろう。したがって、本発明の特定の実施形態についての前述の説明は、例示および説明のために提示されている。これらは、網羅的なものでも、本発明を開示されているその形態に限定するものでもなく、上記の教示に鑑みて、多数の修正および変形が可能であることが自明である。諸実施形態は、本発明の原理を最もよく説明するために選ばれ述べられており、それにより、他の当業者は、本発明、ならびに企図されている特定の使用に適した様々な修正を有する様々な実施形態を最もよく使用することができる。以下の特許請求の範囲、およびそれらの均等物が本発明の範囲を定義するものとする。
【図１】
2010033568.tif 000003
【図２】
2010033568.tif 000004
【図３】
2010033568.tif 000005
【図４】
2010033568.tif 000006
【図５】
2010033568.tif 000007
【図６（ａ）】
2010033568.tif 000008
【図６（ｂ）】
2010033568.tif 000009
【図７】
2010033568.tif 000010
【図８】
2010033568.tif 000011
【図９】
2010033568.tif 000012
【図１０】
2010033568.tif 000013
【図１１】
2010033568.tif 000014
【図１２】
2010033568.tif 000015
【図１３】
2010033568.tif 000016
【図１４】
2010033568.tif 000017
【図１５】
2010033568.tif 000018
【図１６】
2010033568.tif 000019
【図１７】
2010033568.tif 000020
【図１８】
2010033568.tif 000021
【図１９】
2010033568.tif 000022
【図２０】
2010033568.tif 000023
【外国語明細書】
2010033568000001.pdf