(57)【要約】【課題】  加工品質を確保する面沿い加工工具経路決定方法、面沿い加工工具経路決定プログラム、面沿い加工工具経路決定装置を提供する。【解決手段】  加工形状曲面モデルと、両側経路モデルから、面沿い加工を行う工具の経路を決定する面沿い加工工具経路決定方法であって、加工形状曲面モデルから、加工形状オフセットの陰面消去画像を作成する陰面消去画像作成段階と、両側経路モデルを折線近似し、点群折線モデルとする折線モデル化段階と、折線モデルのボロノイ画像を作成するボロノイ画像作成段階と、ボロノイ画像から、２本の境界ガイド線の中間線を抽出する中間線抽出段階と、中間線の両端点間の距離をほぼ半分とする中間線上の位置に、点を再帰的に挿入する中間点再帰挿入段階と、陰面消去画像と、中間線と、中間点から３次元の面沿い経路を決定する３次元面沿い経路決定段階とを有する。【選択図】  図４
2006334684.tif 000002
【特許請求の範囲】
【請求項１】
加工形状曲面モデルと、両側経路モデルから、面沿い加工を行う工具の経路を決定する面沿い加工工具経路決定方法であって、
前記加工形状曲面モデルから、加工形状オフセットの陰面消去画像を作成する陰面消去画像作成段階と、
前記両側経路モデルを折線近似し、点群折線モデルとする折線モデル化段階と、
折線モデルのボロノイ画像を作成するボロノイ画像作成段階と、
前記ボロノイ画像から、２本の境界ガイド線の中間線を抽出する中間線抽出段階と、
前記中間線の両端点間の距離をほぼ半分とする前記中間線上の位置に、点を再帰的に挿入する中間点再帰挿入段階と、
前記陰面消去画像と、前記中間線と、前記中間点から３次元の面沿い経路を決定する３次元面沿い経路決定段階と
を有することを特徴とする面沿い加工工具経路決定方法。
【請求項２】
前記中間線抽出段階において抽出した中間線に隣り合う境界ガイド線との距離の最大値が許容範囲内となるまで、中間線を再帰的に抽出することを特徴とする請求項１に記載の面沿い加工工具経路決定方法。
【請求項３】
前記中間線は、前記ボロノイ画像で得られる２値境界による領域２分法を用いて抽出されることを特徴とする請求項１または２に記載の面沿い加工工具経路決定方法。
【請求項４】
前記ボロノイ画像作成段階では、
前記点群折線モデルのボロノイ画像を作成することを特徴とする請求項１から３のいずれか１項に記載の面沿い加工工具経路決定方法。
【請求項５】
前記中間点再帰挿入段階では、前記ボロノイ画像で得られるボロノイ辺の画素を用いたトレランス２分法により中間点が挿入されることを特徴とする請求項１から４のいずれか１項に記載の面沿い加工工具経路決定方法。
【請求項６】
前記面沿い経路決定段階では、前記中間点に、前記陰面消去画像で得られた高さ情報を加えることにより、３次元の面沿い経路を決定することを特徴とする請求項１から５のいずれか１項に記載の面沿い加工工具経路決定方法。
【請求項７】
請求項１から６のいずれか１項に記載の面沿い加工工具経路決定方法をコンピュータで実行するための面沿い加工工具経路決定プログラム。
【請求項８】
加工形状曲面モデルと、両側経路モデルから、面沿い加工を行う工具の経路を決定する面沿い加工工具経路決定装置であって、
前記加工形状曲面モデルから、加工形状オフセットの陰面消去画像を作成する陰面消去画像作成手段と、
前記両側経路モデルを折線近似し、点群折線モデルとする折線モデル化手段と、
折線モデルのボロノイ画像を作成するボロノイ画像作成手段と、
前記ボロノイ画像から、前記２本の境界ガイド線の中間線を抽出する中間線抽出手段と、
前記中間線の両端点間の距離をほぼ半分とする前記中間線上の位置に、点を再帰的に挿入する中間点再帰挿入手段と、
前記陰面消去画像と、前記中間線と、前記中間点から３次元の面沿い経路を決定する３次元面沿い経路決定手段と
を有することを特徴とする面沿い加工工具経路決定装置。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、面沿い加工における工具の経路を決定する面沿い加工工具経路決定方法、面沿い加工工具経路決定プログラム、面沿い加工工具経路決定装置に関する。
【背景技術】
【０００２】
近年、縦壁部も含めてカプス高さを一定に保つことで、安定した加工品質を確保しようとする面沿い加工法（図１参照）が着目されている。その一方で、この面沿い加工には２つのレベルのオフセット干渉問題がある。
【０００３】
１つは加工形状面に関する３次元オフセットの干渉、もう１つは、３次元オフセット面上におけるガイド線に関する２次元オフセットの干渉である。後者の問題を具体的に説明すると、図２に示されるように、一方からのオフセット結果の累積が他方からのオフセット結果の累積と干渉することや、曲率有限のガイド線のオフセット累積により自分自身にも干渉することである。
【０００４】
さらに従来の面沿い加工法には、オフセットの逐次処理に原因した乱れの拡大伝播の問題がある。具体的には、図３に示されるように、ガイド線の微小変動の拡大伝播であり、各所で生じた面や線による折れ線や、微小曲率変動は経路に載り、累積オフセット処理で大域的に拡大伝播する。
【０００５】
これらの問題うち、ガイド線に関する２次元オフセットの干渉問題は、工具参照オフセット面上で、先の工具経路を一定距離値面沿いオフセットして次の工具経路工具経路を決めているために上記問題が発生する。
【０００６】
また、オフセットの逐次処理に原因した乱れの拡大伝播の問題は、面沿いオフセット処理は、一方の初期経路からの逐次累積処理になっている。よって、カプス高さを一定に固定すると乱れは面上のオフセット処理に載って拡大伝播する。そして、このように各所から拡大伝播してきた乱れは、互いに干渉することとなる。
【０００７】
従来は、折れや変動に対する抑制機構はなく乱れが累積する一方の成り行き任せとなっている。
【特許文献１】特開２００３−２２３２０８号公報
【特許文献２】特開平７−１９５２５３号公報
【特許文献３】特開２００３−２５６０１２号公報
【非特許文献１】精密工学会誌、６６、１２（２０００）１９０１、ＮＣ加工命令の高速な生成法―逆オフセット法のハードウェアによる高速化―、乾正知、垣尾良輔
【発明の開示】
【発明が解決しようとする課題】
【０００８】
上記問題から生じる加工工具経路の急激な変動は、加工機の動作に影響し、最終的には加工品質が悪化するという問題があった。
【０００９】
本発明は、このような問題点に鑑み、加工品質を確保する面沿い加工工具経路決定方法、面沿い加工工具経路決定プログラム、面沿い加工工具経路決定装置を提供することを目的とする。
【課題を解決するための手段】
【００１０】
上記課題を解決するために、本発明は、加工形状曲面モデルと、両側経路モデルから、面沿い加工を行う工具の経路を決定する面沿い加工工具経路決定方法であって、前記加工形状曲面モデルから、加工形状オフセットの陰面消去画像を作成する陰面消去画像作成段階と、前記両側経路モデルを折線近似し、点群折線モデルとする折線モデル化段階と、折線モデルのボロノイ画像を作成するボロノイ画像作成段階と、前記ボロノイ画像から、２本の境界ガイド線の中間線を抽出する中間線抽出段階と、前記中間線の両端点間の距離をほぼ半分とする前記中間線上の位置に、点を再帰的に挿入する中間点再帰挿入段階と、前記陰面消去画像と、前記中間線と、前記中間点から３次元の面沿い経路を決定する３次元面沿い経路決定段階とを有することを特徴とする。
【００１１】
また、上記課題を解決するために、本発明は、前記中間線抽出段階において抽出した中間線に隣り合う境界ガイド線との距離の最大値が許容範囲内となるまで、中間線が再帰的に抽出することを特徴とする。
【００１２】
また、上記課題を解決するために、本発明は、前記中間線は、前記ボロノイ画像で得られる２値境界による領域２分法を用いて抽出されることを特徴とする。
【００１３】
また、上記課題を解決するために、本発明は、前記ボロノイ画像作成段階では、前記点群折線モデルのボロノイ画像を作成することを特徴とする。
【００１４】
また、上記課題を解決するために、本発明は、前記中間点再帰挿入段階では、前記ボロノイ画像で得られるボロノイ辺の画素を用いたトレランス２分法を用いて中間点が挿入されることを特徴とする。
【００１５】
また、上記課題を解決するために、本発明は、前記面沿い経路決定段階では、前記中間点に、前記陰面消去画像で得られた高さ情報を加えることにより、３次元の面沿い経路を決定することを特徴とする。
【００１６】
また、上記課題を解決するために、本発明は、請求項１から６のいずれか１項に記載の面沿い加工工具経路決定方法をコンピュータで実行するための面沿い加工工具経路決定プログラム。
【００１７】
また、上記課題を解決するために、本発明は、加工形状曲面モデルと、両側経路モデルから、面沿い加工を行う工具の経路を決定する面沿い加工工具経路決定装置であって、前記加工形状曲面モデルから、加工形状オフセットの陰面消去画像を作成する陰面消去画像作成手段と、前記両側経路モデルを折線近似し、点群折線モデルとする折線モデル化手段と、折線モデルのボロノイ画像を作成するボロノイ画像作成手段と、前記ボロノイ画像から、前記２本の境界ガイド線の中間線を抽出する中間線抽出手段と、前記中間線の両端点間の距離をほぼ半分とする前記中間線上の位置に、点を再帰的に挿入する中間点再帰挿入手段と、前記陰面消去画像と、前記中間線と、前記中間点から３次元の面沿い経路を決定する３次元面沿い経路決定手段とを有することを特徴とする。
【発明の効果】
【００１８】
以上説明したように、本発明は、加工品質を確保する面沿い加工工具経路決定方法、面沿い加工工具経路決定プログラム、面沿い加工工具経路決定装置を提供することができる。
【発明を実施するための最良の形態】
【００１９】
以下、図面を参照し、本発明の実施形態について説明する。
【００２０】
図４は、本実施の形態の全体の流れの概要を示しており、面沿い加工工具経路が決定されるまでの段階が記されている。ここでは、各段階について説明し、後に詳細な説明を行うこととする。
【００２１】
まず、ステップＳ１０１で、陰面消去画像作成処理が行われる。この処理は３次元ＸＹＺ空間内において、加工形状曲面モデルから、陰面消去画像処理が行われた多面体モデルを作成する処理であり、この多面体モデルから、ステップＳ１０６でＺ値が参照される。
【００２２】
次のステップＳ１０２は、両側経路モデルの点群折線モデル化処理である。この処理は、２次元ＸＹ平面において、両側経路モデルの各経路を点群折線モデル化する処理である。次のステップＳ１０３は、ボロノイ画像処理である。この処理は、上記処理で求まる折線でのボロノイ画像が作成される処理である。このボロノイ画像における色分け線は、上記折線の中間線である。
【００２３】
ステップＳ１０４は、中間線抽出処理である。この処理は、ボロノイ画像における色の変化に基づき中間線を抽出する処理である。ここで抽出された中間線が新たな境界となる。次のステップＳ１０５は、中間点再帰挿入処理である。この処理は、トレランス２分法を用いて、求まった中間線に中間点を再帰的に挿入する処理である。ここで求まった隣り合う中間点を結ぶことにより得られる折線は、再びボロノイ処理の対象となる。
【００２４】
ステップＳ１０６は、３Ｄ面沿い経路点作成処理である。この処理は、ステップＳ１０５で挿入された中間点におけるＺ値を、多面体モデルを参照することで求めることにより、３Ｄ面沿い経路点を作成する処理である。
【００２５】
ステップＳ１０７は、中間線抽出処理で抽出された中間線と、その左右の境界との距離の最大値が許容範囲内かどうか判断する処理である。許容範囲内ではない場合、再びステップＳ１０３の処理が行われる。許容範囲の場合は、処理が終了する。
【００２６】
以上説明した各ステップのうち、ステップＳ１０１は、陰面消去画像作成段階に対応する。ステップＳ１０２は、折線モデル化段階に対応する。ステップＳ１０３は、ボロノイ画像作成段階に対応する。ステップＳ１０４は、中間線抽出段階に対応する。ステップＳ１０５は、中間点再帰挿入段階に対応する。ステップＳ１０６は、３次元面沿い経路決定段階に対応する。
【００２７】
以上が本実施の形態の概要である。以下、詳細な説明をする。まず、加工工具位置のオフセット関係式を図５に示す。図５は、加工工具の工具形状に対応して、その工具形状における曲面、曲線（Ｇ０接続稜線）、点（Ｇ０接続頂点）でのオフセット関係式をベクトルを用いて示したものである。また、工具形状は、ボールエンド（ＢＥ）と、フラットエンド（ＦＥ）と、ラヂアスエンド（ＲＥ）の３つの加工工具の工具形状となっている。
【００２８】
図５に示される各ベクトルとパラメータについて説明する。まず、ｐは、工具接触点を示し、ｏは工具中心点を示す。また、図５に示されるように、ｎは法線ベクトルである。ｔは接線ベクトルある。ｂは法平面内基準ベクトルである。なお、ｂとｎは、接線ベクトルｔとＺ方向の単位ベクトルｋの外積により上半分が有効になるように決める。
【００２９】
また、曲面での関係式におけるｃ、ｓは、それぞれ、ｃｏｓ（ｖ）、ｓｉｎ（ｖ）（０＜ｖ＜π）である。点での関係式におけるｃ０、ｓ０は、それぞれ、ｃｏｓ（ｕ）、ｓｉｎ（ｕ）（０＜ｕ＜２π）である。また、ｃ１、ｓ１は、それぞれ、ｃｏｓ（ｖ）、ｓｉｎ（ｖ）（０＜ｖ＜π／２）である。ｉ，ｊ，ｋは、直交座標軸ベクトルである。
【００３０】
次に、曲面、曲線、点でのオフセット関係式の決め方について説明する。面要素の場合、接触点と法線によりオフセット工具中心点は一意な点として決まる。線要素の場合、接触点と法平面により拘束される自由度１の工具逆オフセット面となる。自由度１は、方平面内の円と折線近似のガイドで点列になる。点要素の場合、接触点位置に配置する自由度２の工具逆オフセット面になる。自由度２は球の折線近似のガイドで点群となる。
【００３１】
なお、折れのないＧ１連続稜線、Ｇ１連続頂点は、隣接要素とオフセットとが共通となるため、処理は不要となる。
【００３２】
次に、オフセット点群モデルからオフセット多面体モデルの作成について説明する。この作成方法は、加工形状モデルの構成要素上に生成されたオフセット工具中心点群を近傍３点で三角平面とする作成方法である。図６に示される符号２００、２０１、２０２は、それぞれ、曲面、Ｇ０曲線、Ｇ０頂点での三角平面化を示すものである。
【００３３】
三角平面化２００に示される曲面のような面要素の場合、面上のＵＶ座標系における近傍の３点で三角平面を作成する。三角平面化２０１に示されるＧ０曲線のような線要素の場合、線上のＴ座標系における近接の２つの法平面内で折線間に線織面を作成する。三角平面化２０２に示されるようなＧ０頂点の点要素の場合、点の球座標系での近傍３点間で三角平面を作成する。
【００３４】
次に、このように作成されたオフセット多面体モデルでのｉｄの管理について説明する。作成された三角平面は、ｉｄ番号で識別される。このｉｄは、元の加工形状モデルの要素のＩＤと三角平面の要素上の局所座標位置情報に対応付けて管理される。従って、局所座標位置情報はｉｄで求めることができる。
【００３５】
局所座標位置情報は、面要素の場合、曲面上の三角平面（重心等）のＵＶ位置座標である。線要素の場合、局所座標位置情報は、曲線上の線分（重心等）のＴ位置座標である。点要素の場合、局所座標位置情報はなく、球面上の三角平面は全て同じ点の要素ｉｄに対応する。
【００３６】
次に、ｉｄと、それに対応する色について、図７を用いて説明する。図７は、ＩＤまたはｉｄを、色を用いて表現した図である。従って、要素の色が異なれば、その要素のＩＤまたはｉｄは異なる。
【００３７】
加工形状２１０は、上述した加工形状モデルの要素のＩＤを、色を用いて表現した図である。形状接触点２１１は、加工形状に接触する形状接触点のＩＤを、色を用いて表現した図である。工具中心点２１２は、工具中心点（オフセット）のＩＤを、色を用いて表現した図である。次の符号２１３は、カラーバッファ２１４とそれに対応するデプスバッファ２１５を示すものである。カラーバッファ２１４は、ｉｄ場であり、デプスバッファ２１５は、Ｚ場である。
【００３８】
次に、オフセット多面体モデルの陰面消去画像の作成について説明する。陰面消去は、従来より良く使われる画像表示機能により行われる。この表示機能は、図８に示されるように、上記カラーバッファ２２０とデプスバッファ２１５に基づき、色２２３を画素２２４に表示する。
【００３９】
この画像表示機能は、デプスバッファ２１５が示す深さの高値選択で表示を行う。深さが同値の場合、後置き色値が選択される。図９に示されるように、加工形状モデルのオフセット多面体データが画像表示機能に送られると、オフセットのＺ値が示す高さが高値選択されデプスバッファ２１５に蓄積される。それに対応する要素ｉｄが色情報としてカラーバッファ２１４に蓄積される。それにより、オフセット多面体２３０が表示される。
【００４０】
この陰面消去の高値選択により、工具の位置は高い位置となり、干渉を回避することが可能となる。
【００４１】
なお、画像表示機能によっては、加工形状モデルのオフセット多面体データを三角平面列にして送り込むと効率的に表示されるものもある。
【００４２】
上記陰面消去処理により、ＸＹ平面から工具参照オフセット面への有限離散写像が確定することとなる。よって、以後はオフセット面上で、有限離散数学を用いることができる。デプスバッファは、工具中心位置の高さの場となり、カラーバッファは加工形状の接触要素のｉｄの場となる。
【００４３】
次に、２本の境界ガイド線のボロノイ画像の作成について説明する。ボロノイ画像とは、平面（一般的には空間）内の全ての位置ｐを、その位置から最も近い位置にある要素ｑ（点や線分等）を割り当ててできる区間図である。対象となる要素ｑは、サイト（site）と呼ばれる。
【００４４】
ボロノイ図の例を、図１０を用いて説明する。図１０には、点群サイト２４０と、線群サイト２４１と、折線サイト２４２とが示されている。点群サイト２４０は、要素ｑが点となっているボロノイ図である。要素ｑの各点に最も近い点により平面が分割される。線群サイト２４１は、要素ｑが線分となっているボロノイ図である。要素ｑの各線分に最も近い点により平面が分割される。折線サイト２４２は、要素ｑが折線となっているボロノイ図である。要素ｑの各折線に最も近い点により平面が分割される。
【００４５】
一般的な２次元平面において、サイトは点と曲線であるが、曲線は離散近似されるので、サイトは点と線分になる。
【００４６】
点と線分からなるサイトにおいて、要素は図１１に示されるように、各点とサイトの距離値を高さとする距離場を３次元に視覚化される。図１１に示されるのは、点の距離場２５０と、線分の距離場２５１である。いずれの距離場も、その点または線分から点への距離ｄを、その点の高さとする。従って、点の距離場２５０の場合、その形状は、点を頂点とする直円錐となり、線分の距離場２５１の場合、その形状は、２葉直平面となる。
【００４７】
一般のサイトが作る距離場は、サイトを構成する全ての点と線分が作る距離場を重ね合わせて各位置において最寄の距離値を選択して得られる。それら形状を併せてできるｉｄ場がボロノイ図である。距離場の重ね合わせの際に、距離の最寄値選択の論理は、距離を高さとみなすと、低値選択の論理に置き換わる。
【００４８】
図１２に示されるように、視覚化した距離場形状について陰面表示（陰面消去の負論理）を適用すれば、カラーバッファ２１３にはｉｄ値の場が、デプスバッファ２１５には距離値の場ができる。図１２は、先ほど説明した図８と比較して、カラーバッファ２１３が異なっている。
【００４９】
以上説明したボロノイ図を作成するために、２本の境界ガイド線モデルの折線モデルの作成がまず行われる。図１３に示されるように、初期ガイド線モデルでの境界３０１、３０２を折線近似し、線分要素と点要素とからなるような点群折線モデルにする。図１４には、カラーバッファとしてのｉｄ場３１１とデスプバッファとしての距離場３１２が示されている。それぞれ、境界を折線近似したことによる線分３０３、３０４が示されている。ｉｄ場３１１では、要素ｉｄが管理され、そのｉｄは、２値で２本の両側境界ガイド線が識別できる。ｉｄ場３１１の色分け線は、距離場３１２で尾根線となる。
【００５０】
このようにして、図１５に示されるような、２本の折線モデルのボロノイ画像が作成される。距離場において、２本の境界線Ｇ１、Ｇ２は谷筋線になり、中間経路３１３は、２本の谷筋線の間にある尾根筋となる。また、ｉｄ場では色分けの２値境界となる。これにより、中間経路（中間線）は、ボロノイ画像で得られる２値境界による領域２分法を用いて抽出することができる。なお、同値重複は後置きｉｄ値が残る仕様とすると表示順序の管理が必要となる。これは、後に説明する輪郭追跡に影響がある。
【００５１】
以上のようにして作成されたボロノイ画像から中間経路（ボロノイ辺）の抽出が次に行われる。
【００５２】
この中間経路を抽出する対象は、図１６に示されるような、２本の連結な境界線経路で挟まれた領域である。領域３２１、３２２は、ともに境界線経路ｇ０、ｇ１で挟まれた領域に中間経路ｇ１／２が示されている。中間経路の追跡はｉｄ場の２値追跡で開始し、終了することとする。
【００５３】
次に、中間経路抽出の開始処理について説明する。後述する領域の再帰２分の過程で、先の画像追跡の経路間距離の最大点近傍で、次の画像追跡の開始点を探査する。従って、追跡は、必ず中間経路上で始まる。なお、経路間距離の最大点は、例えば図１７に示されるボロノイ図の点３２３である。
【００５４】
中間経路追跡は、図１７に示されるように、両側境界線の等距離位置を辿る。これは距離場の尾根筋追跡で場を微分した勾配ベクトル場の成分の正負２値輪郭抽出すると得られるが、ここでは等価なｉｄ場の色分け境界追跡を行う。この処理は、単なるｉｄ２値スカラ場の輪郭追跡なので負荷が低い。
【００５５】
また、追跡中は絶えず追跡点の距離場の値を監視し、重複区間入り口３２４を検知する。重複区間入り口３２４は、２本の谷筋が１本に合流する谷筋の出会い点である。従って、重複区間入り口３２４からの追跡は、尾根筋追跡から谷筋追跡となる。
【００５６】
重複区間入り口３２４から始まる重複線追跡について説明する。上述したように、同値重複時は、後置き表示の色が一面に蓄積されるため、ｉｄ場の色分け境界追跡は不可能となる。従って、追跡点近傍の距離場の勾配の正負２値境界で追跡する。勾配はベクトル場であり、追跡方向によってＸ成分、Ｙ成分を、追跡方向の直交方向に近い方で使い分ける。
【００５７】
また、追跡中は、絶えず追跡点の周回８近傍点のｉｄ場値の変化を監視し、重複区間出口を検知するようにする。重複区間出口は、１本の谷筋が２本に分流する谷筋の出会い点である。色分け境界の複数検知については、距離場の尾根筋と一致するものを選択する。
【００５８】
以上説明した追跡方法を整理すると、図１８に示されるように、まず開始点ｓが探索され、追跡が開始される。ｉｄ場の色境界追跡では、現在追跡点の距離場値を監視する。そしてｄ≒０で距離場の谷筋追跡となる。谷筋追跡では、追跡点の周回８近傍点のｉｄ値変化を監視する。そして２値変化でｉｄ場の色境界追跡となる。そして、追跡点が開始点に戻ると終了となる。
【００５９】
なお、追跡の際は絶えず経路間距離の最大点情報を残し、次の追跡開始点探索の便宜を図る。追跡経路情報は経路点挿入時、頻繁に参照するため、配列に残すなど便宜を図る。
【００６０】
また、同値重複は後置きｉｄ値とするため、図１９に示されるように、表示順序により表示内容が異なる。表示順序をｇ０、ｇ１の順にすると、表示内容３３０のように表示され、表示順序をｇ１、ｇ０の順にすると、表示内容３３１のように表示される。
【００６１】
次に、上記２値輪郭追跡と尾根筋・谷筋追跡の詳細を説明する。図２０に示されるように、２値輪郭追跡は、左回り周回で探索される。また、各追跡点では、次の追跡点を探索するため、現在の追跡点の８近傍点が左回り周回で探索される。このときに周回される８近傍点の開始点は、図２１に示されるように適宜変えられる。
【００６２】
図２１には、現在の追跡点と、先の追跡点と、追跡開始順を示すブロックが、８つ記載されている。この図の見方をブロック３４５を例にして説明する。ブロック３４５の中心の四角が現在の追跡点を示している。周りの数字が探索する順番を示している。そして、ブロック３４５の場合、順番６が先の追跡点となっている。
【００６３】
図２２は、２値輪郭追跡の様子を示す図である。まず、追跡図３４０、３４１に示されるように、開始点探索が行われる。初期位置と方向軸上で２値有効点を探索し、追跡開始点とする。次に、追跡図３４２に示されるように、追跡点が孤立点かどうかの検査が行われる。このとき、上記図２１で説明した順番で２値有効点が探索される。もし追跡点が孤立点の場合、追跡は終了となる。
【００６４】
２値有効点の追跡で、最初に探索された２値有効点が次の追跡点となる。この処理を繰り返して追跡図３４３に示されるように２値輪郭点を追跡し、追跡図３４４に示されるように開始点に戻ると、処理は終了する。
【００６５】
次に、尾根筋・谷筋追跡について説明する。上述したように、追跡点は周回８近傍におけるスカラ場の勾配の変わり目を次の追跡点とする。この勾配は、元のスカラ場からＸＹ２方向の偏微分で決まるベクトル場である。追跡には追跡方向の直交方向に近い成分が選択されて、周回８近傍に勾配成分がセットされる。勾配Ｘ成分は、あるＹ座標におけるＸ座標ｘ＋１での高さから、Ｘ座標ｘでの高さを引いたものとし、勾配Ｙ成分も同様に、あるＸ座標におけるＹ座標ｙ＋１での高さから、Ｙ座標ｙでの高さを引いたものとする。
【００６６】
例えば、図２３の勾配判断図３５０、３５１は、追跡方向がＹ軸方向なので、Ｘ軸方向の勾配成分が用いられる。一方、勾配判断図３５２、３５３は、追跡方向がＸ軸方向なので、Ｙ軸方向の勾配成分が用いられる。このようにして符号の変化を検知するようにし、符号の変わり目が尾根または谷となる。
【００６７】
次に、中間点の再帰挿入（トレランス２分法）について説明する。中間経路上の経路点は、両端点間の弧長の中間点として再帰繰り返しで決定される。この再帰繰り返しの停止は、中間点と両端の張る弦との間の距離を評価して決定される。
【００６８】
図２４は、ｐ０とｐ１の中間点を決定する様子を示す図である。この図２４において、各四角は、ボロノイ画像の画素を示している。まず、この画素追跡で両端ｐ０とｐ１の間の画素の移動距離を累算して弧長を求める。そして、再度画素追跡と移動距離の累算を実施し、弧長を２分する画素点を探索する。
【００６９】
具体的に、弧長は、図２５に示される弧長の累算に示されるように、隣り合う点の距離の総和となる。隣り合う点の距離は、隣り合う点がそれぞれ縦横にあるならば、１とし、斜めにあるならば２の平方根とする。
【００７０】
また、図２５に示される弧長２分点探索方法は、上記総和を２で割った値が、ｐ０からｐｉの弧長より長く、ｐ０からｐ（ｉ＋１）の弧長よりも短くするｉが存在するので、このｐｉを求めるようにする。そして、このｐｉを中間点とする。このように、ボロノイ画像で得られるボロノイ辺の画素を用いたトレランス２分法により中間点が挿入される。
【００７１】
このようにして中間点は再帰挿入されるが、開いた経路と閉じた経路での実際の挿入について、図２６、２７を用いて説明する。図２６は、開いた経路での中間点の再帰挿入を示す図である。まず、ｐ０とｐ１との中間点ｐ1/2が決定される。次に、ｐ０とｐ1/2の中間点ｐ1/4と、ｐ1/2とｐ１の中間点ｐ3/4が決定される。このように両端間の弧長を２分して中間点は繰り返し挿入されていく。
【００７２】
図２７は、閉じた経路での中間点の再帰投入を示す図である。閉じた経路では、ｐ０とｐ１が一致するため、周回の弧長が２分され、中間点ｐ1/2が決定される。あとは、開いた経路と同様に、両端間の弧長を２分して中間点は繰り返し挿入されていく。
【００７３】
次に、上記再帰挿入の繰り返し処理を停止するかどうかの評価について、図２８を用いて説明する。図２８には、ｐ０とｐ１の中間点ｐ1/2が示されている。このとき、ｔをｐ０からｐ１へ向かう単位ベクトルとし、そのｔを用いてｄを計算する。このｄの大きさが所定の許容範囲ｅにおさまったとき、繰り返し処理を停止する。
【００７４】
このようにして得られた中間経路は精度が管理された折線となり、再度ボロノイ処理の対象となる。
【００７５】
次に領域２分法について説明する。図２９は、開いた領域での領域２分法による中間経路の再帰挿入を示す図である。ｇ０とｇ１との間にｇ1/2がまず挿入される。このｇ1/2は、図に示されるように、挿入された中間経路ｇ1/2上の任意の点からｇ０とｇ１に下ろした垂線の長さが等しくなるように挿入される。以下同様にして、図に示されるようにガイド線に挟まれた中間経路が再帰的に挿入されていく。
【００７６】
図３０は、閉じた領域での領域２分法による中間経路の再帰挿入を示す図である。この場合、１点に縮退した内部ループを設定し、２本のガイド線とする。あるいは、外周を２つに分けて２本のガイド線としても良い。
【００７７】
ｇ０とｇ１との間にｇ1/2がまず挿入される。このｇ1/2は、図に示されるように、挿入された中間経路ｇ1/2上の任意の点からｇ０とｇ１に下ろした垂線の長さが等しくなるように挿入される。以下同様にして、図に示されるようにガイド線に挟まれた中間経路が再帰的に挿入されていく。
【００７８】
次に、上述した領域２分法の効用について説明する。まず、２本のガイド線の中間経路は、各ガイド線にそれぞれ１点で接する２点内接円の中心軌跡である。しかし、図３１、３２に示されるように、ガイド線の曲率が急変する部位では、中間経路は１本のガイド線に２点が接触する３点内接円の中心軌跡となる。この場合、接触点が飛躍することとなる。そのため、中間経路挿入の繰り返しの過程で中間経路の微小変動は拡大伝播せず抑制される。
【００７９】
なお、図３３に示されるように、袋小路部分があっても、ガイド線が連結していれば中間経路は破れることはない。しかし、図３４に示されるように、ガイド線ｇ１が連結されていないため、最後には中間経路が破れることとなる。
【００８０】
以上説明した中間経路と、陰面消去画像から３Ｄ面沿い経路が作成される。これは、ボロノイ画像の中間経路情報に陰面消去画像の高さ情報を加えることで作成される。このことを、図３５から図３９を用いて説明する。
【００８１】
図３５は、ガイド線が重複しない場合の３Ｄ面沿い経路間の距離を求める図である。図３６は、ガイド線が重複し、高さが重複しない場合の３Ｄ面沿い経路間の距離を求める図である。図３７は、ガイド線が重複し、高さも重複する場合の３Ｄ面沿い経路間の距離を求める図である。なお、上述したボロノイ画像の追跡処理において、ＸＹ平面間の経路間距離ｄは、距離場の尾根の高さとして即座に得られる。
【００８２】
まず、図３５から説明する。図３５に示されるように、ガイド線ｇ０、ｇ１は重複していない。この場合、陰面消去画像のＺ値がｐ1/2のＺ値として組み込まれる。この場合の面沿い経路線上の点とガイド線との距離Ｄは、図３８に示されるように、ｐ1/2からガイド線までの距離ｄを、ｋとＮの内積で割ったものとなる。
【００８３】
次に、図３６の説明をする。図３６に示されるように、ガイド線ｇ０、ｇ１は重複しているが高さは重複していない。この場合のＺ値は、陰面消去画像の両側経路のＺ値の中間値となる。従って、面沿い経路線上の点とガイド線との距離Ｄは、陰面消去画像の両側経路のＺ差値となる。
【００８４】
次に、図３７の説明をする。図３７に示されるように、ガイド線ｇ０、ｇ１は重複し高さも重複している。この場合のＺ値は、陰面消去画像の両側経路のＺ値となる。従って、面沿い経路線上の点とガイド線との距離Ｄは０となる。このような場合、経路点に重複フラグを立てて、重複加工回避の方策に便宜を図ることができる。
【００８５】
なお、ＸＹ平面の最短経路間距離方向は、面沿いの最短経路間距離方向のＸＹ投影とは厳密には一致しない。３軸ＮＣの範疇における最大誤差の評価には十分代用可としている。
【００８６】
次に、経路情報の評価について、図３９を用いて説明する。追跡中の３次元面沿い距離の最大値Ｄｍａｘが所定の許容範囲内ｅに納まれば（｜Ｄｍａｘ｜＜ｅ）、中間経路の挿入を停止する。納まらない場合は、求めた中間経路と左右の境界線でそれぞれ組をつくり、新たな中間経路３７１が挿入される。その場合、その中間経路はｉｄで管理され、再びボロノイ画像が作成され、上述したその後に続く処理が行われる。
【００８７】
以上説明した処理により、面沿い経路が決定される。このように、本実施の形態により、３次元オフセットの干渉問題は、陰面消去の画像処理で解決され、２次元オフセットの干渉問題は、ボロノイ画像処理で解決される。また、本実施の形態では、両側経路における領域２分法、両端点における経路２分法、２層の再帰２分法で全体から詳細へ詰めていくので、累積伝播の原因である逐次処理は排除されている。したがって、本実施の形態では、局所で生じる乱れの大域への拡大伝播をなくすことができる。さらに領域２分法における特異処理により、縦壁も含めて一定の面沿い加工品質が保証される。
【００８８】
以上説明した本実施の形態を実行するためのハードウェア構成例を、図４０を用いて説明する。
【００８９】
図４０に示されるように、面沿い加工工具経路決定装置のハードウェア構成は、それぞれバスＢで相互に接続されている入力装置２２と，表示装置２３と，ドライブ装置２４と，記録媒体２５と，補助記憶装置２６と，メモリ装置２７と，演算処理装置２０と，インタフェース装置２１とを含む。
【００９０】
入力装置２２は、キーボード及びマウスなどで構成され、面沿い加工工具経路決定装置に各種操作信号を入力するために用いられる。表示装置２３は、面沿い加工工具経路決定装置を操作するのに必要な各種ウィンドウやデータ等を表示する。インタフェース装置２１は、面沿い加工工具経路決定装置をネットワークに接続する為のインタフェースや他の機器を接続するためのインタフェースであり、例えばＮＩＣ（Network Interface Card）やモデム、ＵＳＢ（Universal Serial Bus）等で構成される。
【００９１】
そして、面沿い加工工具経路決定装置を動作させるためのプログラムは、ＣＤ−ＲＯＭ等の記録媒体２５によって提供されるか、ネットワークを通じてダウンロードされる。また、記録媒体２５は、ドライブ装置２４にセットされ、データやプログラムが記録媒体２５からドライブ装置２４を介して補助記憶装置２６にインストールされる。
【００９２】
補助記憶装置２６は、データやプログラムを格納されると共に、必要なファイル等を格納する。メモリ装置２７は、面沿い加工工具経路決定装置の起動時に補助記憶装置２６からプログラムを読み出して格納する。演算処理装置２０は、メモリ装置２７に読み出され格納されたプログラムに従って処理を実行する。
【００９３】
次に、面沿い加工工具経路決定装置のソフトウェアブロック例を、図４１に示す。図４１には、陰面消去画像作成部５１と、折線モデル化部５２と、中間線抽出部５３と、３Ｄ面沿い経路決定部５４と、ボロノイ画像作成部５５と、中間点挿入部５６とが示されている。
【００９４】
これらは、例えばハードディスクなどの補助記憶装置からプログラムが読み出され、各スレッドとして起動して、動作するようにしても良い。
【００９５】
なお、各ブロックと図４との対応は、陰面消去画像作成部５１が、ステップＳ１０１の処理を行う。折線モデル化部５２は、ステップＳ１０２の処理を行う。ボロノイ画像作成部５５は、ステップＳ１０３の処理を行う。中間線抽出部５３は、ステップＳ１０４の処理を行う。中間点挿入部５６は、ステップＳ１０５の処理を行う。３Ｄ面沿い経路決定部５４は、ステップＳ１０６、１０７の処理を行う。
【００９６】
以上説明した各ブロックのうち、陰面消去画像作成部５１は、陰面消去画像作成手段に対応する。折線モデル化部５２は、折線モデル化手段に対応する。ボロノイ画像作成部５５は、ボロノイ画像作成手段に対応する。中間線抽出部５３は、中間線抽出手段に対応する。中間点挿入部５６は、中間点再帰挿入手段に対応する。３Ｄ面沿い経路決定部５４は、３次元面沿い経路決定手段に対応する。
【図面の簡単な説明】
【００９７】
【図１】面沿い加工法を示す図である。
【図２】ガイド線のオフセットによる干渉を示す図である。
【図３】ガイド線の微小変動の拡大伝播を示す図である。
【図４】本実施の形態の全体の流れを示す図である。
【図５】加工工具位置のオフセット関係式を示す図である。
【図６】三角平面化を示す図である。
【図７】ｉｄ（ＩＤ）と色の関係を示す図である。
【図８】表示機能を示す図である。
【図９】オフセットの陰面消去を示す図である。
【図１０】ボロノイ図の例を示す図である。
【図１１】基本要素のボロノイ図を示す図である。
【図１２】表示機能を示す図である。
【図１３】ガイド線モデルを示す図である。
【図１４】ｉｄ場と距離場を示す図である。
【図１５】２本の折線モデルのボロノイ画像を示す図である。
【図１６】２本の連結な境界線経路で挟まれた領域を示す図である。
【図１７】谷の出会い点と距離場とｉｄ場を示す図である。
【図１８】追跡の切り替えを示す図である。
【図１９】表示順序と表示内容を示す図である。
【図２０】２値輪郭追跡を示す図である。
【図２１】追跡開始順を示す図である。
【図２２】２値輪郭追跡の様子を示す図である。
【図２３】勾配判断を示す図である。
【図２４】中間点を決定する様子を示す図である。
【図２５】弧長の計算方法と、弧長の２分点探索方法を示す図である。
【図２６】開いた経路での中間点の再帰挿入を示す図である。
【図２７】閉じた経路での中間点の再帰挿入を示す図である。
【図２８】弧弦距離の評価を示す図である。
【図２９】開いた領域での領域２分法による中間経路の再帰挿入を示す図である。
【図３０】閉じた領域での領域２分法による中間経路の再帰挿入を示す図である。
【図３１】中間経路挿入の繰り返しの過程を示す図である。
【図３２】中間経路挿入の繰り返しの過程を示す図である。
【図３３】袋小路部分がある場合の中間経路挿入を示す図である。
【図３４】破れがある場合の中間経路挿入を示す図である。
【図３５】ガイド線が重複しない場合の３Ｄ面沿い経路間の距離を求める図である。
【図３６】ガイド線が重複し、高さが重複しない場合の３Ｄ面沿い経路間の距離を求める図である。
【図３７】ガイド線が重複し、高さも重複する場合の３Ｄ面沿い経路間の距離を求める図である。
【図３８】面沿い経路線上の点とガイド線との距離Ｄの求め方を示す図である。
【図３９】経路情報の評価を示す図である。
【図４０】面沿い加工工具経路決定装置のハードウェア構成例を示す図である。
【図４１】面沿い加工工具経路決定装置のソフトウェアブロック例を示す図である。
【符号の説明】
【００９８】
１０  加工形状モデル
１１  両側経路モデル
２０  演算処理装置
２１  インタフェース装置
２２  入力装置
２３  表示装置
２４  ドライブ装置
２５  記録媒体
２６  補助記憶装置
２７  メモリ装置
５１  陰面消去画像作成部
５２  折線モデル化部
５３  中間線抽出部
５４  ３Ｄ面沿い経路決定部
５５  ボロノイ画像作成部
５６  中間点挿入部
２００、２０１、２０２  三角平面化
２１０  加工形状
２１１  形状接触点
２１２  工具中心点
２１３、２１４  カラーバッファ
２１５  デプスバッファ
２２３  色
２２４  画素
２３０  オフセット多面体
２４０  点群サイト
２４１  線群サイト
２４２  折線サイト
２５０  点の距離場
２５１  線分の距離場
３０１、３０２  境界
３０３、３０４  線分
３１１  ｉｄ場
３１２  距離場
３１３、３７１  中間経路
３２１、３２２  領域
３２３  点
３２４  重複区間入り口
３３０、３３１  表示内容
３４０、３４１、３４２、３４３、３４４  追跡図
３４５  ブロック
３５０、３５１、３５２、３５３  勾配判断図
【図１】
2006334684.tif 000003
【図２】
2006334684.tif 000004
【図３】
2006334684.tif 000005
【図４】
2006334684.tif 000006
【図５】
2006334684.tif 000007
【図６】
2006334684.tif 000008
【図７】
2006334684.tif 000009
【図８】
2006334684.tif 000010
【図９】
2006334684.tif 000011
【図１０】
2006334684.tif 000012
【図１１】
2006334684.tif 000013
【図１２】
2006334684.tif 000014
【図１３】
2006334684.tif 000015
【図１４】
2006334684.tif 000016
【図１５】
2006334684.tif 000017
【図１６】
2006334684.tif 000018
【図１７】
2006334684.tif 000019
【図１８】
2006334684.tif 000020
【図１９】
2006334684.tif 000021
【図２０】
2006334684.tif 000022
【図２１】
2006334684.tif 000023
【図２２】
2006334684.tif 000024
【図２３】
2006334684.tif 000025
【図２４】
2006334684.tif 000026
【図２５】
2006334684.tif 000027
【図２６】
2006334684.tif 000028
【図２７】
2006334684.tif 000029
【図２８】
2006334684.tif 000030
【図２９】
2006334684.tif 000031
【図３０】
2006334684.tif 000032
【図３１】
2006334684.tif 000033
【図３２】
2006334684.tif 000034
【図３３】
2006334684.tif 000035
【図３４】
2006334684.tif 000036
【図３５】
2006334684.tif 000037
【図３６】
2006334684.tif 000038
【図３７】
2006334684.tif 000039
【図３８】
2006334684.tif 000040
【図３９】
2006334684.tif 000041
【図４０】
2006334684.tif 000042
【図４１】
2006334684.tif 000043