サンプル点において掃引容積の距離場を再構成する方法
【課題】掃引容積の高精度のモデルを表現し、レンダリングするための空間および時間効率の良い方法を提供する。
【解決手段】プロセッサ上で実行される方法が、サンプル点において物体の距離場を再構成する。物体は経路に沿って或る形状を動かすことによって生成される掃引容積である。形状を形状距離場によって表す。経路をパラメトリック関数によって表す。サンプル点における距離データを求め、距離データはサンプル点における物体の距離場を特徴付ける。経路に沿った形状の最適な配置を定義する最適な１組のパラメータを連続的に求める。形状距離場を最適な配置に変換して、変換された形状距離場を生成する。サンプル点において、変換された形状距離場から距離データを求め、サンプル点において距離場を再構成する。
【解決手段】プロセッサ上で実行される方法が、サンプル点において物体の距離場を再構成する。物体は経路に沿って或る形状を動かすことによって生成される掃引容積である。形状を形状距離場によって表す。経路をパラメトリック関数によって表す。サンプル点における距離データを求め、距離データはサンプル点における物体の距離場を特徴付ける。経路に沿った形状の最適な配置を定義する最適な１組のパラメータを連続的に求める。形状距離場を最適な配置に変換して、変換された形状距離場を生成する。サンプル点において、変換された形状距離場から距離データを求め、サンプル点において距離場を再構成する。
【発明の詳細な説明】
【技術分野】
【０００１】
この発明は、包括的には距離場を生成することに関し、より詳細には掃引容積の距離場を生成することに関するものである。
［関連特許出願］
以下の特許出願は、すべて関連し、同時に出願され、互いに援用される。
２００９年５月１９日にＦｒｉｓｋｅｎ他によって出願された「Ａ Ｍｅｔｈｏｄ ｆｏｒ Ｒｅｃｏｎｓｔｒｕｃｔｉｎｇ ａ Ｄｉｓｔａｎｃｅ Ｆｉｅｌｄ ｏｆ ａ Ｓｗｅｐｔ Ｖｏｌｕｍｅ ａｔ ａ Ｓａｍｐｌｅ Ｐｏｉｎｔ」と題するＭＥＲＬ−２１７２、米国非仮特許出願第１２／ＸＸＸ，ＸＸＸ号、および、
２００９年５月１９日にＦｒｉｓｋｅｎ他によって出願された「Ａ Ｍｅｔｈｏｄ ｆｏｒ Ｓｉｍｕｌａｔｉｎｇ Ｎｕｍｅｒｉｃａｌｌｙ Ｃｏｎｔｒｏｌｌｅｄ Ｍｉｌｌｉｎｇ ｕｓｉｎｇ Ａｄａｐｔｉｖｅｌｙ Ｓａｍｐｌｅｄ Ｄｉｓｔａｎｃｅ Ｆｉｅｌｄｓ」と題するＭＥＲＬ−２１７３、米国非仮特許出願第１２／ＸＸＸ，ＸＸＸ号。
【背景技術】
【０００２】
ＮＣフライス加工
数値制御（ＮＣ）フライス加工の工程をシミュレートすることは、コンピュータ支援設計（ＣＡＤ）およびコンピュータ支援製造（ＣＡＭ）において根本的に重要である。シミュレーション中に、工作物のコンピュータモデルが、ＮＣフライス加工工具のコンピュータ表現および１組のＮＣフライス加工工具運動を用いて編集され、フライス加工工程がシミュレートされる。
【０００３】
工作物モデルおよび工具表現を、シミュレーション中に可視化して、工作物および工具ホルダのような部品間の潜在的な衝突を検出することができ、シミュレーション後に、工作物の最終的な形状を検証することができる。
【０００４】
工作物の最終的な形状は、工具および工具運動の選択によって影響を及ぼされる。これらの運動を制御するための命令が典型的には、コンピュータ支援製造システムを用いて、工作物の所望の最終的な形状のグラフィック表現から生成される。それらの運動は典型的には、準備コード（ｐｒｅｐａｒａｔｏｒｙ ｃｏｄｅ）またはＧコードとしても知られている、数値制御プログラミング言語を用いて実現される。以下の標準規格ＲＳ２７４ＤおよびＤＩＮ ６６０２５／ＩＳＯ ６９８３を参照されたい。
【０００５】
コンピュータ支援製造システムによって生成されるＧコードは、所望の形状の正確な複製物を製造しない場合がある。さらに、ＮＣ工具の動きは、ＮＣフライス盤のモータによって支配されるが、その速度、運動範囲、ならびに加速および減速能力は限られているため、実際の工具運動は、ＮＣ機械命令に厳密には従わない場合がある。
【０００６】
工作物の実際の最終的な形状と、工作物の所望の形状との間の不一致は、極めて小さい場合がある。状況によっては、これらの不一致の結果として、工作物の最終的な形状の表面に、サイズが概ね数マイクロメートルの深さおよび幅、数十マイクロメートルの長さにわたる望ましくない溝状の傷（ｇｏｕｇｅ）または欠け目（ｎｉｃｋ）が生じる可能性がある。
【０００７】
典型的には、所望の部品をフライス加工する前に、より軟質で安価な材料から形成される試験工作物をフライス加工することによって、１組のＮＣ機械命令が試験される。その試験工作物の外観検査によって、試験工作物において望ましくない不一致が見つかった場合には、それに応じて、ＮＣ機械命令を変更することができる。
【０００８】
この手動試験は、時間およびコストがかかる。単一の試験工作物を加工するための時間は、概ね数時間かかる場合があり、許容できる１組のＮＣ機械命令が得られるまでに、何度か繰り返すことが必要な場合がある。したがって、コンピュータを利用したシミュレーションおよびレンダリングを用いて、これらの不一致を試験することが望ましい。しかしながら、概ね１メートルの寸法を有する場合がある工作物に対して、概ね数マイクロメートルの寸法で不一致を検出するために、極めて正確なコンピュータモデルが必要とされる。この発明の目的は、フライス加工シミュレーションのためにそのような高精度のモデルを表現し、レンダリングするための空間および時間効率の良い方法を提供することである。
【０００９】
掃引容積
フライス加工中に、本明細書において工具経路と呼ばれる所定の工具運動に従って、工具が工作物に対して動き、工具経路は、工作物に対する工具の相対的な位置、向きおよび他の形状データについての情報を含むことができる。
【００１０】
工具が工具経路に沿って動くとき、工具は「掃引容積」を切り出す。フライス加工中に、工具が工具経路に沿って動くとき、掃引容積によって横切られる工作物の部分が除去される。この材料除去は、コンピュータにおいて、空間領域構成法（ｃｏｎｓｔｒｕｃｔｉｖｅ ｓｏｌｉｄ ｇｅｏｍｅｔｒｙ）（ＣＳＧ）差分演算としてモデル化することができ、その演算によれば、工作物からの掃引容積のＣＳＧ減算演算を用いて、工作物のその部分が工作物から除去される。
【００１１】
高精度のフライス加工シミュレーションを提供するために、掃引容積の正確な表現を有する必要がある。したがって、この発明の目的は、掃引容積の高精度のモデルを表現し、レンダリングするための空間および時間効率の良い方法を提供することである。
【００１２】
本明細書において、一例としてＮＣフライス加工シミュレーションが用いられるが、掃引容積は、科学、工学、エンターテインメントおよびコンピュータグラフィックスの数多くの分野において用途を有する。いくつかの具体的な用途は、数例を挙げると、コンピュータ支援設計、フリーフォーム設計、コンピュータを利用した製図、アニメーション、立体モデリング、ロボティックス、製造自動化および可視化を含む。以下の説明は、掃引容積の正確な表現が必要とされるか、または望まれるすべての分野に当てはまる。
【００１３】
ここでは３次元座標系を重点的に取り扱うが、用語「掃引容積」は、さらに一般的には、Ｎ次元座標系に拡張することができる。詳細には、以下の論考は、２次元空間内の経路に沿って動く１次元または２次元の形状によって掃出されるエリアに、またはさらに高次元の空間内の経路または表面にわたって動く形状によって掃出される超体積にも当てはまる。
【００１４】
この発明の分野における従来技術の概説から始める。掃引容積研究の重要性および課題の概説が、「Ｓｗｅｐｔ Ｖｏｌｕｍｅｓ： Ｆｏｕｎｄａｔｉｏｎｓ，Ｐｅｒｓｐｅｃｔｉｖｅｓ，ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ」（Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｓｈａｐｅ Ｍｏｄｅｌｉｎｇ，２００６，Ａｂｄｅｌ−Ｍａｌｅｋ，Ｂｌａｃｋｍｏｒｅ，ａｎｄ Ｊｏｙ）において提示される。彼らは、コンピュータソフトウエアにおいて掃引（ｓｗｅｅｐ）の複雑な数学的定式化を実現するのが難しいことによって、この分野における研究が制限されること、ならびに掃引容積の境界を計算するには難問が未解決であり、より良好な可視化ツール、およびさらに正確な方法が必要とされることを結論として述べている。
【００１５】
特許文献１に記述されるように、単純な経路に沿って動く単純な形状の掃引容積は多くの場合に、解析的に表現することができる。しかしながら、それらの方法は、複雑な形状および複雑な工具経路まで一般化しない。
【００１６】
いくつかの手法が、多角形の形状の掃引容積を近似する。非特許文献１の場合のようにＣＳＧ演算を介して効率的に編集するために、または特許文献２の場合のように効率的に衝突検出するために、多角形の形状のモデルを空間的な階層内に符号化することができる。
【００１７】
多角形の物体の掃引容積を近似するための方法が、非特許文献２に記述される。
【００１８】
特許文献３は、掃引容積の多角形モデルに関するＣＳＧ演算を用いて機械加工をシミュレートするための方法を記述する。その方法では、工作物の境界が１組のセルの中に入れられ、各セルは、そのセルを横切る掃引容積多角形への参照を含む。工作物と特定のセル内の掃引容積多角形との間の交差部分を要求に応じて処理して、狭い対象領域においてフライス加工される表面の高精度のレンダリングを生成することができる。しかしながら、全体モデルを高精度で可視化するには、非常に時間がかかる。さらに、掃引容積の生成および交差部分の処理は記述されない。
【００１９】
特許文献４は、物体を多面体として表すことを記述する。その物体は、一連の変換を用いて、離散的な時間ステップにおいて、その経路に沿って配置される。掃引容積の境界に位置する多面体表現の辺および面が各時間ステップにおいて求められ、接続されて、その掃引容積の多面体近似が生成される。
【００２０】
これらの多角形法のそれぞれの精度は、物体モデルの多角形表現によって制限される。複雑な工具の曲面を正確に表現するには、数十億もの多角形が必要とされる場合があり、特に曲率半径が小さい場合にはなおさらである。したがって、それらの方法は、精度が限られているか、若しくは掃引容積の高精度のモデルを生成するのに非常な処理時間およびメモリ要件を要するかのいずれか、またはその両方である。さらに、掃引容積を一連の離散的な時間ステップとして近似する方法では、時間ステップ間の精度が限られており、エイリアシングアーティファクトを受けやすい。
【００２１】
フライス加工シミュレーションのための別の一般的な表現はＺバッファまたはＤｅｘｅｌ法として知られている。その手法は非特許文献３において記述される。特許文献５は、同じような方法を記述しており、その方法では、工作物が、すべてｚ方向内にある直線の格子によってモデル化され、フライス加工シミュレーションは、その格子にわたって工具モデルを動かし、その工具によって横切られる工作物を表す線の高さを変更することによって実行される。
【００２２】
Ｄｅｘｅｌ法は典型的には、ｚ軸と一致しない方向において特に、分解能が限られるという難点があり、掃引容積の高精度のモデルを生成するのに適していない。
【００２３】
Ｄｅｘｅｌ表現はボクセルベース表現に関連する。非特許文献４において、Ｋａｕｆｍａｎはボクセルベース表現、およびボクセルベース表現をレンダリングし、処理するための方法を記述する。非特許文献５および非特許文献６はいずれも、物体のボクセルベース表現に関するＣＳＧ演算を用いてスカルプティング（ｓｃｕｌｐｔｉｎｇ）をシミュレートする。
【００２４】
２値ボクセルを用いて掃引容積を表現する方法は、特許文献６「Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ｓｈａｐｉｎｇ Ｇｅｏｍｅｔｒｉｃ Ｓｈａｐｅｓ」および非特許文献７を含む。これらの方法はいずれも、掃引容積を表すために用いられる最小ボクセルのサイズによって精度が制限される。
【００２５】
距離場
特許文献７、特許文献８、特許文献９および特許文献１０において記述されるように、距離場が、形状をレンダリングし、編集するための有効な表現である。
【００２６】
距離場は陰関数の一形態であり、掃引容積を表現し、レンダリングするために用いられている。非特許文献８は、陰関数に関して掃引容積の包絡線を定義するための理論的基礎を記述した。非特許文献９において、ＳｏｕｒｉｎおよびＰａｓｋｏは、陰表面を用いて掃引容積を表現した。しかしながら、陰表面はレンダリングするのが困難である可能性があり、任意の複雑な工具形状に関して適した陰表現を定義するのは難しい。
【００２７】
適応的にサンプリングされる距離場（ＡＤＦ）は、ディテール指向サンプリング（ｄｅｔａｉｌ−ｄｉｒｅｃｔｅｄ ｓａｍｐｌｉｎｇ）を用いて、距離場の空間および時間的に効率の良い表現を提供する。ＡＤＦは、複数のセルから成る空間的な階層内に距離場を格納する。各セルは距離データと、そのセルに関連する距離場の部分を再構成するための再構成法とを含む。距離データは、距離場の値と、距離場の勾配および偏導関数とを含むことができる。メモリおよび計算を節約するために、セル内の距離場は必要とされるときにのみ再構成することができる。
【００２８】
ＣＳＧ演算を用いて編集をシミュレートするために、ＡＤＦを用いることができる。編集されるモデルおよび編集ツールは、距離関数、規則的にサンプリングされる距離場、またはＡＤＦとして表すことができる。その編集過程は、たとえば、そのモデルのＡＤＦを変更することによって、編集される形状のＡＤＦを明示的に生成することができる。代替的には、編集される形状は、複合ＡＤＦとして暗黙的に表すことができる。複合ＡＤＦは、そのモデルの距離場および編集ツールと、編集ツールのためのＣＳＧ減算演算子のような、距離場に対応する演算子と、格納された距離場をレンダリングまたは他の処理中に要求に応じて合成する距離場再構成法とを格納する。
【００２９】
特許文献８は、工具が曲線経路に沿って動くときに、工具の外形に対応する掃引容積を用いてＡＤＦを編集するための方法を記述する。その方法は、サンプル点から経路までの距離を求め、その後、工具外形を用いて、工具の表面までの距離を求める。しかしながら、その方法は、球対称でない形状のための距離場の正確な表現を提供しないため、高精度のモデル化に適していない。
【００３０】
各ＡＤＦセル内の距離場を再構成するために用いられる再構成法は、セルごとに規定することができ、鋭い端および角のようなセル内の表面特徴に特化することができる。特化した再構成法を用いて、そのような特徴付近のＡＤＦ表現の精度を改善することができる。
【００３１】
非特許文献１０において、Ｋｏｂｂｅｌｔ、Ｂｏｔｓｃｈ、ＳｃｈｗａｎｅｋｅおよびＳｅｉｄｅｌは、従来のサンプリングされた距離場表現の精度を改善する代替の方法を記述した。その方法では、形状境界と、正のｘ、ｙおよびｚ方向にあるサンプリング格子との間の最も近い交差部分までの対応するｘ、ｙおよびｚ距離が各サンプル点において格納される。その方法は、マーチングキューブの修正版を用いて、サンプリングされたデータからさらに正確な表面モデルを再構成するために用いることができる。
【００３２】
非特許文献１１において、Ｈｕａｎｇ、Ｌｉ、ＣｒａｗｆｉｓおよびＬｕは、従来のサンプルリングされる距離場表現を増やして、物体境界および物体のオフセット表面をさらに正確に再構成できるようにした。規則的にまたは適応的にサンプリングされる距離場を用いることができる。物体境界または内部オフセット表面に影響を及ぼす場合がある多角形への参照が各セル内に格納され、それにより、多角形表面モデルまでの距離を正確に計算できるようにする。しかしながら、レンダリングされる表面は点モデルを用いて再構成およびレンダリングされ、点モデル内の点は、レンダリングされる表面を含むセルの中央に位置する。したがって、最終的な表面の精度は、境界セルの分解能によって制限される。
【００３３】
掃引容積を表現するために、距離場が用いられてきた。特許文献１１は、工具形状および掃引容積の両方を、規則的にサンプリングされる距離場として表す。掃引容積は、工具の規則的にサンプリングされる距離場を、工具経路に沿った１組の離散位置に変換することによって構成される。工具の距離場は、工具位置ごとに掃引容積の各サンプル点において再構成され、各サンプル点において、再構成された距離のＣＳＧ結合が実行される。掃引容積の表面の三角形モデルが、マーチングキューブを用いて再構成される。非特許文献１２を参照されたい。掃引容積の精度は、工具の規則的にサンプリングされる距離場および掃引容積の分解能によって、さらには工具経路の離散的なサンプリングによって制限される。
【００３４】
非特許文献１３において、Ｋｉｍ、Ｖａｒａｄｈａｎ、ＬｉｎおよびＭａｎｏｃｈａは、複雑な物体の掃引容積を近似するための手法を記述した。その手法では、複雑な物体が多角形近似を用いて近似される。その近似における多角形への符号なし距離が規則的な格子上で計算され、その後、後処理されて符号付き距離が求められる。サンプリングされる距離場の等値面を再構成して、掃引容積の境界を求める。その手法では、精度は、表面要素の多角形近似によって、且つ距離格子の分解能によって制限される。
【００３５】
上記の方法はいずれも、任意の形状の高精度の掃引容積を表すために必要とされる分解能を提供することができない。これらの方法は、形状および掃引容積の表現の空間分解能によって、且つ工具運動を近似するための工具経路の離散的なサンプリングによって制限される。
【００３６】
非特許文献９において、Ｓｏｕｒｉｎ ａｎｄ Ｐａｓｋｏは工具および掃引容積の陰表現を用いて、曲面の正確な表現を提供し、工具経路をサンプリングすることに起因するアーティファクトを低減しようと試みた。掃引容積の陰表現は、工具経路に沿った離散的な１組のＮ個のサンプリングされる時刻ｔ０、ｔ１、・・・、ｔＮ−１に対応する、工具経路に沿った離散的な１組の点に変換される工具の陰表現のＣＳＧ結合と定義される。
【００３７】
その手法において、１つのサンプル点における掃引容積の陰関数の値は、「離散的に」近似される。最初に、工具の陰表現が、経路に沿ったＮ個のサンプリングされる時刻ｔ０、ｔ１、・・・、ｔＮ−１に対応する１組の位置に変換され、そのサンプル点において数値計算され、位置ごとにサンプリングされた値が求められる。工具がそのサンプル点に最も近いときに、工具経路に沿った最適な時間を挟む一対のサンプリングされる時刻ｔｉおよびｔｉ＋１が求められ、１）サンプリングされる時刻ｔｉおよびｔｉ＋１に対応する一対のサンプリングされた値が混合されるか、または（２）サンプリングされる時刻ｔｉおよびｔｉ＋１を混合して、最適な時刻ｔの近似値が計算され、工具の陰表現がｔに対応する工具経路に沿った点に変換され、工具の変換された陰表現がサンプル点において数値計算される。
【００３８】
その手法における計算の大部分は、変換された陰関数を経路に沿った時間ごとに数値計算することに費やされる。各サンプル点における陰関数の値は離散的に数値計算されるため、掃引容積を正確に近似するには、Ｎが非常に大きいことが要求される。したがって、工具の変換された陰表現は、サンプル点ごとに何度も数値計算されなければならない。その方法は、掃引容積の高精度モデルを提供することができるが、非常に時間がかかり、実際には広く採用されていない。
【先行技術文献】
【特許文献】
【００３９】
【特許文献１】米国特許第４，８３３，６１７号明細書
【特許文献２】米国特許第６，０９９，５７３号明細書
【特許文献３】米国特許第６，８６２，５６０号明細書
【特許文献４】米国特許第６，９９３，４６１号明細書
【特許文献５】米国特許第７，１４９，６６８号明細書
【特許文献６】米国特許第６，０４４，３０６号明細書
【特許文献７】米国特許第６，３９６，４９２号明細書
【特許文献８】米国特許第６，７２４，３９３号明細書
【特許文献９】米国特許第６，８２６，０２４号明細書
【特許文献１０】米国特許第７，０４２，４５８号明細書
【特許文献１１】米国特許第５，５４２，０３６号明細書
【非特許文献】
【００４０】
【非特許文献１】Ｂｕｔｃｈｅｒ著「Ｉｎｔｅｒａｃｔｉｖｅ ＣＳＧ」（Ｐｒｏｃｅｅｄｉｎｇｓ，Ｔｅｃｈｎｉｃａｌ Ｓｋｅｔｃｈｅｓ，ＳＩＧＧＲＡＰＨ，１９９９）
【非特許文献２】ＡｂｒａｍｓおよびＡｌｌｅｎ著「Ｃｏｍｐｕｔｉｎｇ Ｓｗｅｐｔ Ｖｏｌｕｍｅｓ」（Ｊｏｕｒｎａｌ ｏｆ Ｖｉｓｕａｌｉｚａｔｉｏｎ ａｎｄ Ａｎｉｍａｔｉｏｎ，２０００）
【非特許文献３】ｖａｎ Ｈｏｏｋ著「Ｒｅａｌ−ｔｉｍｅ Ｓｈａｄｅｄ ＮＣ Ｍｉｌｌｉｎｇ Ｄｉｓｐｌａｙ」（Ｐｒｏｃｅｅｄｉｎｇｓ，ＳＩＧＧＲＡＰＨ １９８６）
【非特許文献４】Ｋａｕｆｍａｎ著「Ｖｏｌｕｍｅ Ｖｉｓｕａｌｉｚａｔｉｏｎ」（ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｐｒｅｓｓ，１９９１）
【非特許文献５】ＧａｌｙｅａｎおよびＨｕｇｈｅｓ著「Ｓｃｕｌｐｔｉｎｇ：ａｎ Ｉｎｔｅｒａｃｔｉｖｅ Ｖｏｌｕｍｅｔｒｉｃ Ｍｏｄｅｌｉｎｇ Ｔｅｃｈｎｉｑｕｅ」（Ｐｒｏｃｅｅｄｉｎｇｓ，ＳＩＧＧＲＡＰＨ １９９１）
【非特許文献６】ＷａｎｇおよびＫａｕｆｍａｎ著「Ｖｏｌｕｍｅ Ｓｃｕｌｐｔｉｎｇ：」（Ｐｒｏｃｅｅｄｉｎｇｓ，ＳＩＧＧＲＡＰＨ １９９５）
【非特許文献７】ＥｒｄｉｍおよびＩｌｉｅｓ著「Ｏｃｔｒｅｅ−ｂａｓｅｄ Ｂｏｕｎｄａｒｙ Ｅｖａｌｕａｔｉｏｎ ｆｏｒ Ｇｅｎｅｒａｌ Ｓｗｅｅｐｓ」（Ｐｒｏｃｅｅｄｉｎｇｓ，ＴＭＣＥ，２００８）
【非特許文献８】ＭａｒｔｉｎおよびＳｔｅｐｈｅｎｓｏｎ著「Ｓｗｅｅｐｉｎｇ ｏｆ Ｔｈｒｅｅ Ｄｉｍｅｎｓｉｏｎａｌ Ｏｂｊｅｃｔｓ」（Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｄｅｓｉｇｎ，２０（４），１９９０）
【非特許文献９】ＳｏｕｒｉｎおよびＰａｓｋｏ著「Ｆｕｎｃｔｉｏｎ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｆｏｒ Ｓｗｅｅｐｉｎｇ ｂｙ ａ Ｍｏｖｉｎｇ Ｓｏｌｉｄ」（Ｐｒｏｃｅｅｄｉｎｇｓ，Ｓｏｌｉｄ Ｍｏｄｅｌｉｎｇ，１９９５）
【非特許文献１０】Ｋｏｂｂｅｌｔ，Ｂｏｔｓｃｈ，ＳｃｈｗａｎｅｋｅおよびＳｅｉｄｅｌ著「Ｆｅａｔｕｒｅ ｓｅｎｓｉｔｉｖｅ ｓｕｒｆａｃｅ ｅｘｔｒａｃｔｉｏｎ ｆｒｏｍ ｖｏｌｕｍｅ ｄａｔａ」（Ｐｒｏｃｅｅｄｉｎｇｓ，ＳＩＧＧＲＡＰＨ ２００１）
【非特許文献１１】Ｈｕａｎｇ，Ｌｉ，ＣｒａｗｆｉｓおよびＬｕ著「Ｃｏｍｐｌｅｔｅ Ｄｉｓｔａｎｃｅ Ｆｉｅｌｄ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ」（Ｐｒｏｃｅｅｄｉｎｇｓ，ＩＥＥＥ Ｖｉｓｕａｌｉｚａｔｉｏｎ，２００１）
【非特許文献１２】ＬｏｒｅｎｓｅｎおよびＣｌｉｎｅ著「Ｍａｒｃｈｉｎｇ Ｃｕｂｅｓ： Ａ ｈｉｇｈ ｒｅｓｏｌｕｔｉｏｎ ３Ｄ ｓｕｒｆａｃｅ ｃｏｎｓｔｒｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ」（Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ，Ｖｏｌ． ２１，Ｎｒ． ４，Ｊｕｌｙ １９８７）
【非特許文献１３】Ｋｉｍ，Ｖａｒａｄｈａｎ，ＬｉｎおよびＭａｎｏｃｈａ著「Ｆａｓｔ Ｓｗｅｐｔ Ｖｏｌｕｍｅ Ａｐｐｒｏｘｉｍａｔｉｏｎ ｏｆ Ｃｏｍｐｌｅｘ Ｐｏｌｙｈｅｄｒａｌ Ｍｏｄｅｌｓ」（Ｐｒｏｃｅｅｄｉｎｇｓ，Ｓｈａｐｅ Ｍｏｄｅｌｉｎｇ，２００３）
【発明の概要】
【発明が解決しようとする課題】
【００４１】
したがって、その精度が形状表現、または工具経路の離散的なサンプリングによって制限されない、任意の経路に沿って任意の形状を動かすことによって生成される掃引容積の高精度の表現を生成するための空間および時間効率の良い方法が必要とされている。さらに、概ね１メートルの寸法を有する工作物において、概ね数マイクロメートルのサイズを有する望ましくない特徴物を表現することができる空間および時間効率の良いＮＣフライス加工シミュレーションシステムが必要とされている。
【課題を解決するための手段】
【００４２】
サンプル点において物体の距離場を再構成する方法が提供され、物体は、経路に沿って或る形状を動かすことによって生成される掃引容積である。本方法はプロセッサ上で実行される。形状は、形状距離場によって表される。経路はパラメトリック関数によって表される。
【００４３】
サンプル点における距離データが求められ、距離データは、サンプル点における物体の距離場を特徴付ける。経路に沿った形状の最適な配置を定義する最適な１組のパラメータが連続的に求められる。
【００４４】
形状距離場を最適な配置に変換して、変換された形状距離場を生成する。サンプル点において、変換された形状距離場から距離データを求め、サンプル点において距離場を再構成する。
【発明の効果】
【００４５】
この発明によれば、掃引容積の高精度のモデルを表現し、レンダリングするための空間および時間効率の良い方法を提供することができる。
【図面の簡単な説明】
【００４６】
【図１】この発明の実施の形態１による、ＮＣフライス盤、ならびにＮＣフライス加工をシミュレートするためのシステムおよび方法のフロー図である。
【図２Ａ】フライス加工のために用いられる典型的な工具、および或る経路に沿ってそのような工具を動かすことによって行なわれる工作物における典型的な編集の図である。
【図２Ｂ】曲線経路に沿って２Ｄ形状を掃引することによって求められる掃引容積の概略図である。
【図３Ａ】工具の直線経路の図である。
【図３Ｂ】工具軸が経路に沿って変化する、工具の弧状経路の図である。
【図３Ｃ】工具の曲線経路の図である。
【図４】この発明の実施の形態１による、１組のＧコードまたはＮＣ機械命令を用いて或る工具形状による工作物のフライス加工をシミュレートするための方法のフロー図である。
【図５】サンプル点において或る形状の掃引容積の距離場を再構成するための方法のブロック図である。
【図６Ａ】掃引容積を離散的に近似するための従来技術の方法の図である。
【図６Ｂ】この発明の実施の形態１による、掃引容積の距離場を連続的に求めるための方法の図である。
【図６Ｃ】この発明の実施の形態１による、掃引容積の距離場を連続的に求めるための方法の図である。
【図７Ａ】フライス加工のために用いられる典型的な１組の円筒対称の工具の図である。
【図７Ｂ】図７Ａの工具の２次元断面図である。
【図７Ｃ】図７Ｂの断面の２次元距離場を示す図である。
【図８Ａ】パラメータｔによってパラメータ化される経路に沿って動く円筒対称工具の図である。
【図８Ｂ】この発明の実施の形態１による、サンプル点を円筒対称工具の断面の２次元距離場上にマッピングする、ｔによってパラメータ化される曲線の図である。
【発明を実施するための形態】
【００４７】
実施の形態１．
システムおよび方法の概説
図１はＮＣフライス加工システム１００、および数値制御（ＮＣ）フライス加工シミュレーションシステム１５０を示す。ＮＣフライス加工システム１００では、コンピュータ支援設計（ＣＡＤ）モデル１０２がコンピュータ支援製造（ＣＡＭ）システム１０４に入力され、ＣＡＭシステム１０４は、ＮＣフライス盤を制御するためのＧコード１０６を生成する。ＮＣフライス加工中に、ＧコードはＮＣフライス加工コンソール１０８に入力され、コンソール１０８は各Ｇコードを処理して、対応する１組のＮＣ機械命令１１０を生成する。ＮＣ機械命令はＮＣコントローラ１１２に入力され、ＮＣコントローラ１１２は、工作物をフライス加工するために、工作物１１８に対して工具１１６を動かす１組のモータ制御信号１１４を生成する。
【００４８】
シミュレーションシステム１５０は、入力として、コンピュータ支援製造システム１０４によって生成されたＧコード１０６、またはＮＣコンソール１０８によって生成されるＮＣ機械命令１１０を取り込むことができる。シミュレーションシステムへの入力はコンピュータプロセッサ１５２によって読み取られ、コンピュータプロセッサ１５２は工作物の機械加工をシミュレートし、シミュレートされたモデル１５４を出力し、モデル１５４はコンピュータメモリ１５６に格納することができる。プロセッサ１５２は、格納されるシミュレートされたモデル１５４をレンダリングして、レンダリングされた画像１５８を生成することができ、画像１５８は表示デバイス１６０に出力することができる。表示された画像１６２をコンピュータ支援設計モデル１０２と比較して、工作物の実際のＮＣフライス加工を実行する前に、Ｇコード１０６またはＮＣ機械命令１１０を検証することができる。
【００４９】
工具
図２Ａは、ＮＣフライス加工において用いられる１組の典型的な工具形状２０２、２０４、２０６および２０８を示す。工具が工作物２１０に対して動かされるとき、その工具は工作物から材料を削り出す。ここで、工具２０２、２０４、２０６および２０８は工作物から、表面２１２、２１４、２１６および２１８に対応する材料を除去する。各工具によって除去される材料の形状は、工具形状、および工作物に対する工具の経路によって決定される。除去される材料の形状は、工具が経路に沿って動くときの、工作物と工具の掃引容積との交差部分である。
【００５０】
本明細書においてＮＣフライス加工シミュレーションを重点的に取り扱うが、掃引容積は、コンピュータ支援設計、フリーフォーム設計、立体モデリング、ロボティックス、製造自動化および可視化を含む、科学、工学、およびコンピュータグラフィックスの多くの分野において用途を有する。
【００５１】
掃引容積
図２Ｂは、経路２５２に沿って動かされる形状２５０の掃引容積２６０を示す。経路２５２は、形状２５０の特定の点の位置を時間の関数として規定する。その経路は、その形状の向き２５６、２５７および２５８を時間の関数として規定することができる。また、その経路は、その形状のスケール、またはその形状の任意の変換を時間の関数として規定することもできる。図２Ｂでは、形状２５０の元の位置、向きおよび外形が、その形状が経路に沿って動くのに応じて、形状の２５４の最終的な位置、向きおよび外形に変換される。
【００５２】
工具経路
工作物に対する工具の経路は数多くの形において規定することができる。
【００５３】
図３Ａは直線経路を示しており、工具３０２が直線３０４に沿って動かされる。
【００５４】
図３Ｂは円弧状経路を示しており、工具３０２の先端３１０が円弧３１２に沿って動かされ、その経路の終点において、工具の元の軸方向３１４が最終的な軸方向３１６に変換される。
【００５５】
図３Ｃは曲線経路を示しており、工具３０２の先端３１０が曲線３２０に沿って動かされる。
【００５６】
他の取り得る経路形状は、数例を挙げると、工具を或る点に位置決めすること、ポリラインとして知られている一連の線に沿って工具を動かすこと、渦巻または螺旋形の曲線に沿って工具を動かすこと、２次ベジエ曲線または３次ベジエ曲線、或いは区分的多項式曲線として知られている一連の多項式曲線のような、多項式曲線に沿って工具を動かすことを含む。工作物の形状または材料組成によって影響を及ぼされる経路のような、或る手順によって定義される経路を含む、シミュレートすることができる任意の形の経路を考えることができる。
【００５７】
フライス加工シミュレーション
図４は、シミュレーションプロセッサ４００を用いて或る工具形状による工作物のフライス加工をシミュレートし、フライス加工される工作物の表現をメモリ４４０に格納し、レンダリングプロセッサ４６０を用いて、フライス加工される工作物の表現を表示デバイス４８０にレンダリングするための方法を示す。
【００５８】
工作物形状、および１組の距離場４０４から複合距離場を再構成するための方法を用いて、複合ＡＤＦ４４４が生成され、メモリ４４０に格納される場合がある。工作物形状は、工作物外形４０２によって規定され、１組の幾何学的要素を含む。
【００５９】
工作物外形の各幾何学的要素は、１組の幾何学的要素距離場を規定する距離場表現に変換される。各幾何学的要素距離場は、数例を挙げると、解析距離関数、陰距離関数、規則的にサンプリングされる距離場、ＡＤＦ、距離関数の合成、または手順のうちの１つとして表すことができる。
【００６０】
フライス加工シミュレーションのための好ましい実施形態では、複合ＡＤＦが８分木としてメモリに格納され、８分木は、工作物形状のバウンディングボックスを取り囲む根セルで開始してトップダウンで生成される。工作物外形４０２内の各特定の幾何学的要素の距離場表現が、複合ＡＤＦの葉セルに追加され、葉セルの距離場は特定の幾何学的要素によって影響を及ぼされる。レンダリングおよび処理中に、複合距離場再構成法４０４を用いて葉セル内の距離場を合成することによって、サンプル点において特定の葉セルの距離場を再構成することができる。
【００６１】
種々の合成方法が可能であり、当該技術分野において知られている。好ましい実施形態では、その合成はブール減算演算子を用いて、工具によって掃引される容積による工作物からの材料の除去をシミュレートする。
【００６２】
ＡＤＦ生成中に、規定された最大数よりも多くの距離場を含む葉セルが細分され、各葉セル内の距離場が複雑になるのを制限する。したがって、複合ＡＤＦはディテール指向である；少ない距離場によって影響を及ぼされる工作物の領域ほど、大きなセルが生じ、多くの距離場によって影響を及ぼされる工作物の領域ほど、小さなセルが生じる。
【００６３】
複合ＡＤＦに新たな距離場を追加することによって、或る葉セル内の距離場の関連がなくなる場合には、関連のない距離場は葉セルから除去される。たとえば、工具運動が或る葉セルからすべての材料を除去する場合には、その葉セル内のすべての距離場の関連がなくなる場合があり、その葉セルは距離場を除去され、外部セルとしてラベル付けされる。
【００６４】
したがって、新たな工具運動のシミュレーションは、或る葉セルおよびその同胞内の既存の数の距離場を規定された最大数未満に削減することができる。この場合、その葉セルおよび同胞の距離場はその共通の親セル内に配置され、その葉セルおよび同胞は複合ＡＤＦから削除される。
【００６５】
フライス加工シミュレーション法は、工具形状４０８から形状距離場４１２を定義し（４１０）、形状距離場４１２は、数例を挙げると、解析距離関数、陰距離関数、規則的にサンプリングされる距離場、ＡＤＦ、距離関数の合成、または手順のうちの１つとすることができる。
【００６６】
ＮＣ機械命令４１４、または代わりに、Ｇコード４１６を用いて、工具の運動に対応するパラメトリック経路関数４２０を定義する。工具運動ごとに、形状距離場１２およびパラメトリック経路関数４２０を用いて、工具運動に対応する工具の掃引容積を表す掃引容積距離場４２４を定義する（４２２）。
【００６７】
工具運動による工作物のフライス加工をシミュレートするために、複合ＡＤＦ４４４が、掃引容積距離場４２４を用いて編集される（４２６）。編集中に、掃引容積距離場が、工具の掃引容積によって横切られる複合ＡＤＦのセルに追加され、それによって横切られたセル内のＡＤＦが再生される。
【００６８】
複合ＡＤＦを用いて、レンダリングモデル要素から成るレンダリングモデル４６４を生成することができ（４６２）、表示デバイス４８０にレンダリングすることができる（４６６）。ポイントレンダリング、三角形レンダリングおよびレイトレーシングのような、当該技術分野において知られているレンダリング法を用いて、レンダリングモデル４６４を生成し、レンダリングすることができる。
【００６９】
フライス加工シミュレーションのための代替の実施形態では、各ＮＣ機械命令４１４またはＧコード４１６に対応する各形状距離場、および工作物外形４０２の各幾何学的要素に対応する各距離場が、対応するＮＣ機械命令、Ｇコードまたは幾何学的要素のための固有識別子を割り当てられる。
【００７０】
レンダリングモデル生成４６２中に、レンダリングモデル４６４の各特定の要素が、特定のレンダリングモデル要素に寄与する距離場の固有識別子で注釈を付される。１組のレンダリング属性を各固有識別子と関連付けることによって、レンダリングモデル４６４は、どの幾何学的要素、およびどの工具経路が工作物の各部分に寄与するかを符号化する。たとえば、固有の色を、特定のＧコードの形状距離場の識別子と関連付けることによって、特定のＧコードによって影響を及ぼされる工作物の領域を、表示デバイス４８０上で容易に可視化することができる。
【００７１】
代替形態として、不透明度を複合ＡＤＦ内の特定の距離場内の識別子と関連付けることができる。たとえば、特定の工具運動に対応する特定の距離場に関連付けられるレンダリング要素を透明としてレンダリングすることができる。代替的には、固有識別子をブール演算子と関連付けることができ、そのブール演算子は、対応するレンダリング要素がレンダリングされるべきであるか否かを指示する。他のレンダリング属性を用いて、付加的な効果を生成し、フライス加工される工作物の可視化を支援することができる。
【００７２】
距離場は物理的なシミュレーションにおいて数多くの利点を有する。フライス加工シミュレーションのための代替の実施形態は、距離場を用いて、ＮＣフライス加工工程を検証する。たとえば、フライス加工シミュレータ４００によって生成される複合ＡＤＦ４４４を、コンピュータ支援設計モデル１０２の距離場表現と比較することができる。その比較は、表示デバイス４８０を用いて外観検査によって行なうことができる。
【００７３】
代替的には、その比較は、複数のサンプル点において、複合ＡＤＦ４４４およびコンピュータ支援設計モデル１０２の距離場をサンプリングし、それらのサンプル点において距離データを比較することによって行なうことができる。代替的には、その比較は、複合ＡＤＦ４４４およびコンピュータ支援設計モデル１０２の距離場の一方を他方から減算することにより差距離場を生成し、差距離場を可視化することによって行なうことができる。
【００７４】
また、距離場を用いて、各工具運動によって除去される材料の或る物理的特性を測定することもできる。たとえば、特定の工具運動の場合に、工作物と、特定の工具運動に対応する掃引容積との交差を表す交差距離場を生成することができる。その後、交差距離場を処理して、数例を挙げると、その質量、体積、または慣性モーメントを含む、その特定の工具運動によって除去される材料の種々の特性を求めることができる。
【００７５】
掃引容積の距離場の再構成
図５は、プロセッサ５００を用いて、サンプル点において掃引容積の距離場を再構成するための方法を示す。形状距離場５０４およびパラメトリック経路関数５０６が、上記のように、工具および工具運動を規定する。サンプル点５０２を与えられると、掃引容積再構成法５１０は、そのサンプル点５０２において距離場を再構成するために、そのサンプル点における距離データを求める。その方法は、経路に沿った工具の最適な配置を「連続的に」求める（５１２）。
【００７６】
最適な１組のパラメータを求めている（５１２）最中に、その経路に沿った工具形状の初期配置を定義する１組の初期パラメータが選択される。好ましい実施形態では、その経路は単一のパラメータｔによってパラメータ化され、パラメータｔは、その経路に沿って工具が移動する時間に対応し、ｔの初期値が選択される（５１４）。形状距離場は、その経路に沿って時刻ｔにおいて工具の形状を配置するように変換され（５１６）、サンプル点５０２において形状距離場が再構成される（５１８）。
【００７７】
サンプル点において再構成される距離データは、数例を挙げると、サンプル点から変換された形状までの距離、距離場の勾配、および距離場の偏導関数を含むことができる。
【００７８】
その形状を経路に沿ってサンプリング点に近い配置に動かすために、再構成された距離データを用いて、パラメータ値ｔを繰返し変更する（５２０）。その変更は連続的に行われ、すなわち、所定の１組の離散値からｔを選択するのではなく、パラメータｔは、その経路に沿った形状の位置を改善する方向に任意の量だけ繰返し変更される。その変更は、最適なｔが求められるまで、または繰り返しているうちにｔの変化がｔの或る最小変化未満になるまで、または繰返しの最大数が行なわれるまで繰り返される。最適なｔが求められると、その形状は、対応する最適な配置に変換され（５３０）、変換された形状から距離データが再構成されて（５４０）、サンプル点５０２において距離データが求められる（５１０）。
【００７９】
図６Ａは、サンプル点６０１において掃引容積の距離場を離散的に再構成するための従来技術の方法を示す。工具形状６０２が、１組の離散時刻ｔ０ ６０６、ｔ１ ６０８、・・・、ｔＮ−１ ６１０に対応する、工具経路６０４に沿った離散的な１組の配置に置かれる。
【００８０】
サンプリングされる時刻ごとに、Ｐ ６０１から工具形状までの対応するサンプリングされる距離が求められる。この図では、離散時刻ｔｉ ６１２およびｔｉ＋１ ６１４が最適な時間を挟む。従来技術の方法は、以下のうちの１つとしてＰ ６０１から掃引容積までの距離を近似する：１）ｔｉおよびｔｉ＋１について求められる距離の最小値、２）ｔｉおよびｔｉ＋１について求められる距離の平均または混合、または３）時刻ｔ＊において配置されるときの形状までの距離。ただし、ｔ＊はｔｉおよびｔｉ＋１の重み付け平均として求められる。
【００８１】
図６Ｂはこの発明の好ましい実施形態を示す。工具形状６０２は最初に、経路６０４に沿ってパラメータｔに対応する配置に置かれる。工具形状６０２の距離場からのサンプル点Ｐ ６０１における距離データ６２２を用いて、その形状を経路に沿って、最適なパラメータｔ＊６２６によって定義される最適な配置の方向に向かって点ｔ＋Δｔ ６２４まで連続的に動かす。
【００８２】
その好ましい実施形態では、サンプル点における距離場の勾配を用いて、パラメータｔを変更する。その変更は、その形状を経路に沿って、距離場の外向きの勾配ベクトルと一致する方向に動かす。この方向は、ｔにおける経路の接線ベクトルと外向きの勾配ベクトルとのドット積をとることによって求められる。そのドット積が正である場合には、パラメータｔを大きくし、そのドット積が負である場合には小さくする。そのドット積の大きさは、ｔの変化に関する尺度を与える。ドット積が０に近い場合には、その形状は局所的に距離場に直交し、ｔのための最適値が求められたことを指示する。
【００８３】
その経路が２つ以上のパラメータによってパラメータ化される場合には、各経路パラメータに関する偏導関数を用いて、ｔを変更することができる。
【００８４】
連続的に最適化する際の最も大きな難題のうちの１つは、局所的な最適値が存在することによって、連続最適化問題の出力が大域的な最適値であることを保証するのが難しくなることである。工具形状および工具経路が相対的に複雑である場合には、いくつかの局所的な最適値が存在する場合がある。代替の実施形態では、これは、上記の方法への２つの変更を用いて解決される。
【００８５】
第１の変更では、ｔが相対的に少ない数のサンプリングされる時刻においてサンプリングされ、サンプリングされる時刻ごとに距離データが再構成される。サンプリングされる時刻の中から、形状がサンプル点に最も近い時刻ｔを選択することによって、大域的な最大値に収束する可能性が最も高い点において、最適化問題が初期化される。２つ以上のサンプリングされる時刻が有力である場合には、大域的な最適値を見つけるために、その方法を各有力なサンプリングされる時間において初期化することができる。
【００８６】
第２の変更は図６Ｃに示される。この変更では、最適なｔ ６２６を挟むものと判断される開始時刻ｔＳ ６３０および終了時刻ｔＥ ６３４が初期化される。ｔを変更するための方法が両方の値ｔＳ ６３０およびｔＥ ６３４を互いに向かって動かすことになる場合には、２つのｔ値は最適なｔ値を挟む。その変更を繰り返す度に、サンプル点Ｐ ６０１において、ｔＳ ６３０およびｔＥ ６３４にそれぞれ対応する距離データ６３２および６３６が求められ、ｔＳ ６３０とｔＥ ６３４との間の最適ｔ値が求められるまで、ｔＳおよびｔＥのうちの一方または両方が他方に向かって動かされる。
【００８７】
好ましい実施形態、ならびに第１の変更および第２の変更に対する種々の代替形態が存在する。パラメータｔを連続的に変更するためのさらなる代替方法を、連続最適化の分野に精通している人に知られている技法から導出できることは当業者には理解されたい。
【００８８】
複数のサンプル点における距離場の数値計算
複合ＡＤＦをレンダリングすること、または物体間の衝突を検出するために複合ＡＤＦを使用することのような特定の処理では、複数のサンプル点においてＡＤＦの距離場が再構成される必要がある。
【００８９】
たとえば、複合ＡＤＦを点モデルに変換して、ポイントレンダリングを介して表示デバイスにレンダリングすることができる。点モデルは点として知られている１組の幾何学的基本要素を含み、各点は空間内の位置および１組のレンダリング属性に関連付けられる。レンダリング中に、複数の点が画像位置にマッピングされ、レンダリング属性を用いてその画像にレンダリングされる。レンダリング属性の例をいくつか挙げると、点の色、不透明度、サイズ、反射率特性および法線ベクトルを含む。
【００９０】
１組の点における各点は、以下のステップで複合ＡＤＦを用いて生成することができる。第１に、その点の位置が複合ＡＤＦのセル内の位置に初期化される。第２に、その点の位置において距離場が再構成され、距離場の大きさおよび勾配ベクトルを用いて、その点が複合ＡＤＦの表面に向かって動かされる。その点が複合ＡＤＦの表面上に存在することを再構成された距離が指示するまで、第２のステップが繰り返される。最後に、距離場が再構成され、その点にレンダリング属性を割り当てるために用いられる。たとえば、その点は、その点の位置に影響を及ぼす距離場の固有識別子に基づいて、色を割り当てられる場合がある。第２の例として、その点は、複合ＡＤＦの局所的な勾配に基づいて、法線ベクトルを割り当てられる場合がある。
【００９１】
代替的に、レイキャスティングまたはレイトレーシングを用いて複合ＡＤＦを画像に変換し、画像として表示デバイスにレンダリングすることができる。レイキャスティング中に、画像内のピクセルごとに１組の光線が複合ＡＤＦ内に投光される。複合ＡＤＦの表面を横切る各光線は、交点において複合ＡＤＦから再構成される距離データに従って、１組のレンダリング属性を割り当てられる。各組の光線のレンダリング属性を合成して、画像内の対応する各ピクセルの色が求められる。
【００９２】
光線に沿った種々のサンプル点において複合ＡＤＦから距離データを再構成することによって、その光線と複合ＡＤＦの表面との間の交点が特定される。掃引容積の距離場を再構成するための上記の方法と同じように、交点は、離散的に、または連続的に特定することができる。その交点が離散的に特定される場合には、その表面に最も近いサンプル点の混合を用いて、その交点を近似することができる。交点が連続的に特定される場合には、連続最適化法を用いて、その交点が求められる。
【００９３】
また、２つの物体間の衝突を検出するには、距離データが、複数のサンプル点において複合ＡＤＦから再構成される必要がある。２つの物体間の衝突は、いくつかの方法で、再構成された距離データから検出することができる。たとえば、物体のうちの一方のための距離データを他方の物体上で１組の表面点として再構成して、第２の物体の第１の物体に対する近接性の指標を求めることができる。その近接性データが、２つの物体が或る最小しきい値距離よりも近いことを指示する場合には、２つの物体間の衝突が検出される。
【００９４】
求められた近接性データは、物体のうちの一方の形状を変更するために、または物体のうちの一方の経路を変更して、たとえば、衝突を回避するために、ＮＣフライス加工シミュレーション、ロボット経路計画および製造のような用途において用いることができる。
【００９５】
円筒対称工具
上記のように、複合ＡＤＦをレンダリングすること、または物体間の衝突を検出するために複合ＡＤＦを使用することなどの特定の用途では、複数のサンプル点において複合ＡＤＦが再構成される必要がある。再構成法の効率を改善するために、円筒対称の工具形状に合うように好ましい実施形態を変更することができる。
【００９６】
円筒対称工具が或る経路に沿って動く場合、サンプル点に対して最も近い工具表面上の点は常に、サンプル点と、その経路に沿った工具のすべての配置のための工具軸とを含む平面上に存在する。工具軸を通る平面は、工具の断面を画定する。工具は円筒対称であるため、断面の形状は、工具軸を通るいかなる平面の場合にも同じである。
【００９７】
図７Ａは、ＮＣフライス加工のために用いられる典型的な１組の円筒対称工具７０２、７０３、７０４および７０５を示す。
【００９８】
図７Ｂは、それぞれ、工具７０２、７０３、７０４および７０５のそれぞれの２次元断面７１２、７１３、７１４および７１５を示す。
【００９９】
図７Ｃは、２次元断面７１２、７１３、７１４および７１５をそれぞれ表す２次元距離場７２２、７２３、７２４および７２５を示す。
【０１００】
或るサンプル点から、或る経路に沿って動く円筒対称工具形状までの距離は、工具の断面がそのサンプル点を含む平面内に存在するときに、そのサンプル点から、その断面のエッジまでの距離に等しい。
【０１０１】
したがって、この発明の代替の実施形態は、サンプル点を工具形状の断面の２次元座標にマッピングし、工具形状の２次元断面を表す２次元距離場から距離データを計算することによって距離データを求める。
【０１０２】
図８Ａは、開始時刻ｔＳ ８０４から終了時刻ｔＥ ８０８まで経路８０１に沿って動き、任意の時刻ｔ ８０６を通過する工具８０２を示す。この発明の好ましい実施形態によれば、サンプル点Ｐ ８０３において距離データを連続的に再構成することができる。
【０１０３】
代替の実施形態では、図８Ｂに示されるように、その経路に沿った時刻ごとに、点Ｐ ８０６が、２次元距離場８２０として表される、工具の断面の２次元座標系にマッピングされる。たとえば、サンプル点Ｐ ８０６は、その経路に沿った時刻ｔＳにおける工具の配置に対応するサンプル点Ｐ’（ｔＳ）にマッピングされ、その経路に沿った時刻ｔＥにおける工具の配置に対応するサンプル点Ｐ’（ｔＥ）にマッピングされ、且つその経路に沿った時刻ｔにおける工具の配置に対応するサンプル点Ｐ’（ｔ）にマッピングされる。
【０１０４】
図８Ｂに示されるように、１組のマッピングされたサンプル点は、その工具の断面の２次元座標空間内のマッピングされた経路８１４を定義する。したがって、代替の実施形態では、工具形状が物体に最も近い点は、マッピングされた経路を連続的に探索することによって求められる。
【０１０５】
数多くのサンプル点が数値計算されることになる場合には、複数の方法において、代替の実施形態の効率をさらに改善することができる。たとえば、マッピングされた経路は複数の区間に分割することができ、各区間は、局所的に滑らかである工具の断面の２次元距離場の領域を通る。言い換えると、距離場が或る経路区間内で少なくともＣ１連続であるように、その経路が距離場の不連続点を横切る点において、その経路を分割することができる。本明細書において定義されるように、Ｃ１連続は、距離場の１次導関数が、その経路区間に沿って連続であることを意味する。代替的には、距離場が、連続最適化法の信頼性および効率を改善するために当該技術分野において知られている特性を、或る経路区間に沿って２次までの範囲で変化させるように、経路を分割することができる。
【０１０６】
動作環境
この発明は、数多くの汎用または専用コンピューティングシステム環境または構成で動作する。この発明と共に用いるのに適している既知のコンピューティングシステム、環境および／または構成の例は、限定はしないが、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドデバイスまたはラップトップデバイス、マルチプロセッサまたはマルチコアシステム、グラフィックス処理ユニット（ＧＰＵ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、マイクロコントローラベースシステム、ネットワークＰＣ、メインフレームコンピュータ、上記のシステムまたはデバイスのうちの任意のものを含む分散コンピューティング環境など、すなわち、一般的にはプロセッサを含む。モニタまたは他のタイプの表示デバイス１６０が、上記のシステムのうちの任意のものに接続され、この発明を可視化する（１６２）ことを可能にする。
【０１０７】
この発明を、好ましい実施形態の例として説明してきたが、この発明の精神および範囲内で他のさまざまな適合および変更を行えることが理解されるべきである。したがって、この発明の真の精神および範囲内に入るすべての変形および変更を包含することが、添付の特許請求の範囲の目的である。
【技術分野】
【０００１】
この発明は、包括的には距離場を生成することに関し、より詳細には掃引容積の距離場を生成することに関するものである。
［関連特許出願］
以下の特許出願は、すべて関連し、同時に出願され、互いに援用される。
２００９年５月１９日にＦｒｉｓｋｅｎ他によって出願された「Ａ Ｍｅｔｈｏｄ ｆｏｒ Ｒｅｃｏｎｓｔｒｕｃｔｉｎｇ ａ Ｄｉｓｔａｎｃｅ Ｆｉｅｌｄ ｏｆ ａ Ｓｗｅｐｔ Ｖｏｌｕｍｅ ａｔ ａ Ｓａｍｐｌｅ Ｐｏｉｎｔ」と題するＭＥＲＬ−２１７２、米国非仮特許出願第１２／ＸＸＸ，ＸＸＸ号、および、
２００９年５月１９日にＦｒｉｓｋｅｎ他によって出願された「Ａ Ｍｅｔｈｏｄ ｆｏｒ Ｓｉｍｕｌａｔｉｎｇ Ｎｕｍｅｒｉｃａｌｌｙ Ｃｏｎｔｒｏｌｌｅｄ Ｍｉｌｌｉｎｇ ｕｓｉｎｇ Ａｄａｐｔｉｖｅｌｙ Ｓａｍｐｌｅｄ Ｄｉｓｔａｎｃｅ Ｆｉｅｌｄｓ」と題するＭＥＲＬ−２１７３、米国非仮特許出願第１２／ＸＸＸ，ＸＸＸ号。
【背景技術】
【０００２】
ＮＣフライス加工
数値制御（ＮＣ）フライス加工の工程をシミュレートすることは、コンピュータ支援設計（ＣＡＤ）およびコンピュータ支援製造（ＣＡＭ）において根本的に重要である。シミュレーション中に、工作物のコンピュータモデルが、ＮＣフライス加工工具のコンピュータ表現および１組のＮＣフライス加工工具運動を用いて編集され、フライス加工工程がシミュレートされる。
【０００３】
工作物モデルおよび工具表現を、シミュレーション中に可視化して、工作物および工具ホルダのような部品間の潜在的な衝突を検出することができ、シミュレーション後に、工作物の最終的な形状を検証することができる。
【０００４】
工作物の最終的な形状は、工具および工具運動の選択によって影響を及ぼされる。これらの運動を制御するための命令が典型的には、コンピュータ支援製造システムを用いて、工作物の所望の最終的な形状のグラフィック表現から生成される。それらの運動は典型的には、準備コード（ｐｒｅｐａｒａｔｏｒｙ ｃｏｄｅ）またはＧコードとしても知られている、数値制御プログラミング言語を用いて実現される。以下の標準規格ＲＳ２７４ＤおよびＤＩＮ ６６０２５／ＩＳＯ ６９８３を参照されたい。
【０００５】
コンピュータ支援製造システムによって生成されるＧコードは、所望の形状の正確な複製物を製造しない場合がある。さらに、ＮＣ工具の動きは、ＮＣフライス盤のモータによって支配されるが、その速度、運動範囲、ならびに加速および減速能力は限られているため、実際の工具運動は、ＮＣ機械命令に厳密には従わない場合がある。
【０００６】
工作物の実際の最終的な形状と、工作物の所望の形状との間の不一致は、極めて小さい場合がある。状況によっては、これらの不一致の結果として、工作物の最終的な形状の表面に、サイズが概ね数マイクロメートルの深さおよび幅、数十マイクロメートルの長さにわたる望ましくない溝状の傷（ｇｏｕｇｅ）または欠け目（ｎｉｃｋ）が生じる可能性がある。
【０００７】
典型的には、所望の部品をフライス加工する前に、より軟質で安価な材料から形成される試験工作物をフライス加工することによって、１組のＮＣ機械命令が試験される。その試験工作物の外観検査によって、試験工作物において望ましくない不一致が見つかった場合には、それに応じて、ＮＣ機械命令を変更することができる。
【０００８】
この手動試験は、時間およびコストがかかる。単一の試験工作物を加工するための時間は、概ね数時間かかる場合があり、許容できる１組のＮＣ機械命令が得られるまでに、何度か繰り返すことが必要な場合がある。したがって、コンピュータを利用したシミュレーションおよびレンダリングを用いて、これらの不一致を試験することが望ましい。しかしながら、概ね１メートルの寸法を有する場合がある工作物に対して、概ね数マイクロメートルの寸法で不一致を検出するために、極めて正確なコンピュータモデルが必要とされる。この発明の目的は、フライス加工シミュレーションのためにそのような高精度のモデルを表現し、レンダリングするための空間および時間効率の良い方法を提供することである。
【０００９】
掃引容積
フライス加工中に、本明細書において工具経路と呼ばれる所定の工具運動に従って、工具が工作物に対して動き、工具経路は、工作物に対する工具の相対的な位置、向きおよび他の形状データについての情報を含むことができる。
【００１０】
工具が工具経路に沿って動くとき、工具は「掃引容積」を切り出す。フライス加工中に、工具が工具経路に沿って動くとき、掃引容積によって横切られる工作物の部分が除去される。この材料除去は、コンピュータにおいて、空間領域構成法（ｃｏｎｓｔｒｕｃｔｉｖｅ ｓｏｌｉｄ ｇｅｏｍｅｔｒｙ）（ＣＳＧ）差分演算としてモデル化することができ、その演算によれば、工作物からの掃引容積のＣＳＧ減算演算を用いて、工作物のその部分が工作物から除去される。
【００１１】
高精度のフライス加工シミュレーションを提供するために、掃引容積の正確な表現を有する必要がある。したがって、この発明の目的は、掃引容積の高精度のモデルを表現し、レンダリングするための空間および時間効率の良い方法を提供することである。
【００１２】
本明細書において、一例としてＮＣフライス加工シミュレーションが用いられるが、掃引容積は、科学、工学、エンターテインメントおよびコンピュータグラフィックスの数多くの分野において用途を有する。いくつかの具体的な用途は、数例を挙げると、コンピュータ支援設計、フリーフォーム設計、コンピュータを利用した製図、アニメーション、立体モデリング、ロボティックス、製造自動化および可視化を含む。以下の説明は、掃引容積の正確な表現が必要とされるか、または望まれるすべての分野に当てはまる。
【００１３】
ここでは３次元座標系を重点的に取り扱うが、用語「掃引容積」は、さらに一般的には、Ｎ次元座標系に拡張することができる。詳細には、以下の論考は、２次元空間内の経路に沿って動く１次元または２次元の形状によって掃出されるエリアに、またはさらに高次元の空間内の経路または表面にわたって動く形状によって掃出される超体積にも当てはまる。
【００１４】
この発明の分野における従来技術の概説から始める。掃引容積研究の重要性および課題の概説が、「Ｓｗｅｐｔ Ｖｏｌｕｍｅｓ： Ｆｏｕｎｄａｔｉｏｎｓ，Ｐｅｒｓｐｅｃｔｉｖｅｓ，ａｎｄ Ａｐｐｌｉｃａｔｉｏｎｓ」（Ｉｎｔｅｒｎａｔｉｏｎａｌ Ｊｏｕｒｎａｌ ｏｆ Ｓｈａｐｅ Ｍｏｄｅｌｉｎｇ，２００６，Ａｂｄｅｌ−Ｍａｌｅｋ，Ｂｌａｃｋｍｏｒｅ，ａｎｄ Ｊｏｙ）において提示される。彼らは、コンピュータソフトウエアにおいて掃引（ｓｗｅｅｐ）の複雑な数学的定式化を実現するのが難しいことによって、この分野における研究が制限されること、ならびに掃引容積の境界を計算するには難問が未解決であり、より良好な可視化ツール、およびさらに正確な方法が必要とされることを結論として述べている。
【００１５】
特許文献１に記述されるように、単純な経路に沿って動く単純な形状の掃引容積は多くの場合に、解析的に表現することができる。しかしながら、それらの方法は、複雑な形状および複雑な工具経路まで一般化しない。
【００１６】
いくつかの手法が、多角形の形状の掃引容積を近似する。非特許文献１の場合のようにＣＳＧ演算を介して効率的に編集するために、または特許文献２の場合のように効率的に衝突検出するために、多角形の形状のモデルを空間的な階層内に符号化することができる。
【００１７】
多角形の物体の掃引容積を近似するための方法が、非特許文献２に記述される。
【００１８】
特許文献３は、掃引容積の多角形モデルに関するＣＳＧ演算を用いて機械加工をシミュレートするための方法を記述する。その方法では、工作物の境界が１組のセルの中に入れられ、各セルは、そのセルを横切る掃引容積多角形への参照を含む。工作物と特定のセル内の掃引容積多角形との間の交差部分を要求に応じて処理して、狭い対象領域においてフライス加工される表面の高精度のレンダリングを生成することができる。しかしながら、全体モデルを高精度で可視化するには、非常に時間がかかる。さらに、掃引容積の生成および交差部分の処理は記述されない。
【００１９】
特許文献４は、物体を多面体として表すことを記述する。その物体は、一連の変換を用いて、離散的な時間ステップにおいて、その経路に沿って配置される。掃引容積の境界に位置する多面体表現の辺および面が各時間ステップにおいて求められ、接続されて、その掃引容積の多面体近似が生成される。
【００２０】
これらの多角形法のそれぞれの精度は、物体モデルの多角形表現によって制限される。複雑な工具の曲面を正確に表現するには、数十億もの多角形が必要とされる場合があり、特に曲率半径が小さい場合にはなおさらである。したがって、それらの方法は、精度が限られているか、若しくは掃引容積の高精度のモデルを生成するのに非常な処理時間およびメモリ要件を要するかのいずれか、またはその両方である。さらに、掃引容積を一連の離散的な時間ステップとして近似する方法では、時間ステップ間の精度が限られており、エイリアシングアーティファクトを受けやすい。
【００２１】
フライス加工シミュレーションのための別の一般的な表現はＺバッファまたはＤｅｘｅｌ法として知られている。その手法は非特許文献３において記述される。特許文献５は、同じような方法を記述しており、その方法では、工作物が、すべてｚ方向内にある直線の格子によってモデル化され、フライス加工シミュレーションは、その格子にわたって工具モデルを動かし、その工具によって横切られる工作物を表す線の高さを変更することによって実行される。
【００２２】
Ｄｅｘｅｌ法は典型的には、ｚ軸と一致しない方向において特に、分解能が限られるという難点があり、掃引容積の高精度のモデルを生成するのに適していない。
【００２３】
Ｄｅｘｅｌ表現はボクセルベース表現に関連する。非特許文献４において、Ｋａｕｆｍａｎはボクセルベース表現、およびボクセルベース表現をレンダリングし、処理するための方法を記述する。非特許文献５および非特許文献６はいずれも、物体のボクセルベース表現に関するＣＳＧ演算を用いてスカルプティング（ｓｃｕｌｐｔｉｎｇ）をシミュレートする。
【００２４】
２値ボクセルを用いて掃引容積を表現する方法は、特許文献６「Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ｓｈａｐｉｎｇ Ｇｅｏｍｅｔｒｉｃ Ｓｈａｐｅｓ」および非特許文献７を含む。これらの方法はいずれも、掃引容積を表すために用いられる最小ボクセルのサイズによって精度が制限される。
【００２５】
距離場
特許文献７、特許文献８、特許文献９および特許文献１０において記述されるように、距離場が、形状をレンダリングし、編集するための有効な表現である。
【００２６】
距離場は陰関数の一形態であり、掃引容積を表現し、レンダリングするために用いられている。非特許文献８は、陰関数に関して掃引容積の包絡線を定義するための理論的基礎を記述した。非特許文献９において、ＳｏｕｒｉｎおよびＰａｓｋｏは、陰表面を用いて掃引容積を表現した。しかしながら、陰表面はレンダリングするのが困難である可能性があり、任意の複雑な工具形状に関して適した陰表現を定義するのは難しい。
【００２７】
適応的にサンプリングされる距離場（ＡＤＦ）は、ディテール指向サンプリング（ｄｅｔａｉｌ−ｄｉｒｅｃｔｅｄ ｓａｍｐｌｉｎｇ）を用いて、距離場の空間および時間的に効率の良い表現を提供する。ＡＤＦは、複数のセルから成る空間的な階層内に距離場を格納する。各セルは距離データと、そのセルに関連する距離場の部分を再構成するための再構成法とを含む。距離データは、距離場の値と、距離場の勾配および偏導関数とを含むことができる。メモリおよび計算を節約するために、セル内の距離場は必要とされるときにのみ再構成することができる。
【００２８】
ＣＳＧ演算を用いて編集をシミュレートするために、ＡＤＦを用いることができる。編集されるモデルおよび編集ツールは、距離関数、規則的にサンプリングされる距離場、またはＡＤＦとして表すことができる。その編集過程は、たとえば、そのモデルのＡＤＦを変更することによって、編集される形状のＡＤＦを明示的に生成することができる。代替的には、編集される形状は、複合ＡＤＦとして暗黙的に表すことができる。複合ＡＤＦは、そのモデルの距離場および編集ツールと、編集ツールのためのＣＳＧ減算演算子のような、距離場に対応する演算子と、格納された距離場をレンダリングまたは他の処理中に要求に応じて合成する距離場再構成法とを格納する。
【００２９】
特許文献８は、工具が曲線経路に沿って動くときに、工具の外形に対応する掃引容積を用いてＡＤＦを編集するための方法を記述する。その方法は、サンプル点から経路までの距離を求め、その後、工具外形を用いて、工具の表面までの距離を求める。しかしながら、その方法は、球対称でない形状のための距離場の正確な表現を提供しないため、高精度のモデル化に適していない。
【００３０】
各ＡＤＦセル内の距離場を再構成するために用いられる再構成法は、セルごとに規定することができ、鋭い端および角のようなセル内の表面特徴に特化することができる。特化した再構成法を用いて、そのような特徴付近のＡＤＦ表現の精度を改善することができる。
【００３１】
非特許文献１０において、Ｋｏｂｂｅｌｔ、Ｂｏｔｓｃｈ、ＳｃｈｗａｎｅｋｅおよびＳｅｉｄｅｌは、従来のサンプリングされた距離場表現の精度を改善する代替の方法を記述した。その方法では、形状境界と、正のｘ、ｙおよびｚ方向にあるサンプリング格子との間の最も近い交差部分までの対応するｘ、ｙおよびｚ距離が各サンプル点において格納される。その方法は、マーチングキューブの修正版を用いて、サンプリングされたデータからさらに正確な表面モデルを再構成するために用いることができる。
【００３２】
非特許文献１１において、Ｈｕａｎｇ、Ｌｉ、ＣｒａｗｆｉｓおよびＬｕは、従来のサンプルリングされる距離場表現を増やして、物体境界および物体のオフセット表面をさらに正確に再構成できるようにした。規則的にまたは適応的にサンプリングされる距離場を用いることができる。物体境界または内部オフセット表面に影響を及ぼす場合がある多角形への参照が各セル内に格納され、それにより、多角形表面モデルまでの距離を正確に計算できるようにする。しかしながら、レンダリングされる表面は点モデルを用いて再構成およびレンダリングされ、点モデル内の点は、レンダリングされる表面を含むセルの中央に位置する。したがって、最終的な表面の精度は、境界セルの分解能によって制限される。
【００３３】
掃引容積を表現するために、距離場が用いられてきた。特許文献１１は、工具形状および掃引容積の両方を、規則的にサンプリングされる距離場として表す。掃引容積は、工具の規則的にサンプリングされる距離場を、工具経路に沿った１組の離散位置に変換することによって構成される。工具の距離場は、工具位置ごとに掃引容積の各サンプル点において再構成され、各サンプル点において、再構成された距離のＣＳＧ結合が実行される。掃引容積の表面の三角形モデルが、マーチングキューブを用いて再構成される。非特許文献１２を参照されたい。掃引容積の精度は、工具の規則的にサンプリングされる距離場および掃引容積の分解能によって、さらには工具経路の離散的なサンプリングによって制限される。
【００３４】
非特許文献１３において、Ｋｉｍ、Ｖａｒａｄｈａｎ、ＬｉｎおよびＭａｎｏｃｈａは、複雑な物体の掃引容積を近似するための手法を記述した。その手法では、複雑な物体が多角形近似を用いて近似される。その近似における多角形への符号なし距離が規則的な格子上で計算され、その後、後処理されて符号付き距離が求められる。サンプリングされる距離場の等値面を再構成して、掃引容積の境界を求める。その手法では、精度は、表面要素の多角形近似によって、且つ距離格子の分解能によって制限される。
【００３５】
上記の方法はいずれも、任意の形状の高精度の掃引容積を表すために必要とされる分解能を提供することができない。これらの方法は、形状および掃引容積の表現の空間分解能によって、且つ工具運動を近似するための工具経路の離散的なサンプリングによって制限される。
【００３６】
非特許文献９において、Ｓｏｕｒｉｎ ａｎｄ Ｐａｓｋｏは工具および掃引容積の陰表現を用いて、曲面の正確な表現を提供し、工具経路をサンプリングすることに起因するアーティファクトを低減しようと試みた。掃引容積の陰表現は、工具経路に沿った離散的な１組のＮ個のサンプリングされる時刻ｔ０、ｔ１、・・・、ｔＮ−１に対応する、工具経路に沿った離散的な１組の点に変換される工具の陰表現のＣＳＧ結合と定義される。
【００３７】
その手法において、１つのサンプル点における掃引容積の陰関数の値は、「離散的に」近似される。最初に、工具の陰表現が、経路に沿ったＮ個のサンプリングされる時刻ｔ０、ｔ１、・・・、ｔＮ−１に対応する１組の位置に変換され、そのサンプル点において数値計算され、位置ごとにサンプリングされた値が求められる。工具がそのサンプル点に最も近いときに、工具経路に沿った最適な時間を挟む一対のサンプリングされる時刻ｔｉおよびｔｉ＋１が求められ、１）サンプリングされる時刻ｔｉおよびｔｉ＋１に対応する一対のサンプリングされた値が混合されるか、または（２）サンプリングされる時刻ｔｉおよびｔｉ＋１を混合して、最適な時刻ｔの近似値が計算され、工具の陰表現がｔに対応する工具経路に沿った点に変換され、工具の変換された陰表現がサンプル点において数値計算される。
【００３８】
その手法における計算の大部分は、変換された陰関数を経路に沿った時間ごとに数値計算することに費やされる。各サンプル点における陰関数の値は離散的に数値計算されるため、掃引容積を正確に近似するには、Ｎが非常に大きいことが要求される。したがって、工具の変換された陰表現は、サンプル点ごとに何度も数値計算されなければならない。その方法は、掃引容積の高精度モデルを提供することができるが、非常に時間がかかり、実際には広く採用されていない。
【先行技術文献】
【特許文献】
【００３９】
【特許文献１】米国特許第４，８３３，６１７号明細書
【特許文献２】米国特許第６，０９９，５７３号明細書
【特許文献３】米国特許第６，８６２，５６０号明細書
【特許文献４】米国特許第６，９９３，４６１号明細書
【特許文献５】米国特許第７，１４９，６６８号明細書
【特許文献６】米国特許第６，０４４，３０６号明細書
【特許文献７】米国特許第６，３９６，４９２号明細書
【特許文献８】米国特許第６，７２４，３９３号明細書
【特許文献９】米国特許第６，８２６，０２４号明細書
【特許文献１０】米国特許第７，０４２，４５８号明細書
【特許文献１１】米国特許第５，５４２，０３６号明細書
【非特許文献】
【００４０】
【非特許文献１】Ｂｕｔｃｈｅｒ著「Ｉｎｔｅｒａｃｔｉｖｅ ＣＳＧ」（Ｐｒｏｃｅｅｄｉｎｇｓ，Ｔｅｃｈｎｉｃａｌ Ｓｋｅｔｃｈｅｓ，ＳＩＧＧＲＡＰＨ，１９９９）
【非特許文献２】ＡｂｒａｍｓおよびＡｌｌｅｎ著「Ｃｏｍｐｕｔｉｎｇ Ｓｗｅｐｔ Ｖｏｌｕｍｅｓ」（Ｊｏｕｒｎａｌ ｏｆ Ｖｉｓｕａｌｉｚａｔｉｏｎ ａｎｄ Ａｎｉｍａｔｉｏｎ，２０００）
【非特許文献３】ｖａｎ Ｈｏｏｋ著「Ｒｅａｌ−ｔｉｍｅ Ｓｈａｄｅｄ ＮＣ Ｍｉｌｌｉｎｇ Ｄｉｓｐｌａｙ」（Ｐｒｏｃｅｅｄｉｎｇｓ，ＳＩＧＧＲＡＰＨ １９８６）
【非特許文献４】Ｋａｕｆｍａｎ著「Ｖｏｌｕｍｅ Ｖｉｓｕａｌｉｚａｔｉｏｎ」（ＩＥＥＥ Ｃｏｍｐｕｔｅｒ Ｓｏｃｉｅｔｙ Ｐｒｅｓｓ，１９９１）
【非特許文献５】ＧａｌｙｅａｎおよびＨｕｇｈｅｓ著「Ｓｃｕｌｐｔｉｎｇ：ａｎ Ｉｎｔｅｒａｃｔｉｖｅ Ｖｏｌｕｍｅｔｒｉｃ Ｍｏｄｅｌｉｎｇ Ｔｅｃｈｎｉｑｕｅ」（Ｐｒｏｃｅｅｄｉｎｇｓ，ＳＩＧＧＲＡＰＨ １９９１）
【非特許文献６】ＷａｎｇおよびＫａｕｆｍａｎ著「Ｖｏｌｕｍｅ Ｓｃｕｌｐｔｉｎｇ：」（Ｐｒｏｃｅｅｄｉｎｇｓ，ＳＩＧＧＲＡＰＨ １９９５）
【非特許文献７】ＥｒｄｉｍおよびＩｌｉｅｓ著「Ｏｃｔｒｅｅ−ｂａｓｅｄ Ｂｏｕｎｄａｒｙ Ｅｖａｌｕａｔｉｏｎ ｆｏｒ Ｇｅｎｅｒａｌ Ｓｗｅｅｐｓ」（Ｐｒｏｃｅｅｄｉｎｇｓ，ＴＭＣＥ，２００８）
【非特許文献８】ＭａｒｔｉｎおよびＳｔｅｐｈｅｎｓｏｎ著「Ｓｗｅｅｐｉｎｇ ｏｆ Ｔｈｒｅｅ Ｄｉｍｅｎｓｉｏｎａｌ Ｏｂｊｅｃｔｓ」（Ｃｏｍｐｕｔｅｒ Ａｉｄｅｄ Ｄｅｓｉｇｎ，２０（４），１９９０）
【非特許文献９】ＳｏｕｒｉｎおよびＰａｓｋｏ著「Ｆｕｎｃｔｉｏｎ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ ｆｏｒ Ｓｗｅｅｐｉｎｇ ｂｙ ａ Ｍｏｖｉｎｇ Ｓｏｌｉｄ」（Ｐｒｏｃｅｅｄｉｎｇｓ，Ｓｏｌｉｄ Ｍｏｄｅｌｉｎｇ，１９９５）
【非特許文献１０】Ｋｏｂｂｅｌｔ，Ｂｏｔｓｃｈ，ＳｃｈｗａｎｅｋｅおよびＳｅｉｄｅｌ著「Ｆｅａｔｕｒｅ ｓｅｎｓｉｔｉｖｅ ｓｕｒｆａｃｅ ｅｘｔｒａｃｔｉｏｎ ｆｒｏｍ ｖｏｌｕｍｅ ｄａｔａ」（Ｐｒｏｃｅｅｄｉｎｇｓ，ＳＩＧＧＲＡＰＨ ２００１）
【非特許文献１１】Ｈｕａｎｇ，Ｌｉ，ＣｒａｗｆｉｓおよびＬｕ著「Ｃｏｍｐｌｅｔｅ Ｄｉｓｔａｎｃｅ Ｆｉｅｌｄ Ｒｅｐｒｅｓｅｎｔａｔｉｏｎ」（Ｐｒｏｃｅｅｄｉｎｇｓ，ＩＥＥＥ Ｖｉｓｕａｌｉｚａｔｉｏｎ，２００１）
【非特許文献１２】ＬｏｒｅｎｓｅｎおよびＣｌｉｎｅ著「Ｍａｒｃｈｉｎｇ Ｃｕｂｅｓ： Ａ ｈｉｇｈ ｒｅｓｏｌｕｔｉｏｎ ３Ｄ ｓｕｒｆａｃｅ ｃｏｎｓｔｒｕｃｔｉｏｎ ａｌｇｏｒｉｔｈｍ」（Ｃｏｍｐｕｔｅｒ Ｇｒａｐｈｉｃｓ，Ｖｏｌ． ２１，Ｎｒ． ４，Ｊｕｌｙ １９８７）
【非特許文献１３】Ｋｉｍ，Ｖａｒａｄｈａｎ，ＬｉｎおよびＭａｎｏｃｈａ著「Ｆａｓｔ Ｓｗｅｐｔ Ｖｏｌｕｍｅ Ａｐｐｒｏｘｉｍａｔｉｏｎ ｏｆ Ｃｏｍｐｌｅｘ Ｐｏｌｙｈｅｄｒａｌ Ｍｏｄｅｌｓ」（Ｐｒｏｃｅｅｄｉｎｇｓ，Ｓｈａｐｅ Ｍｏｄｅｌｉｎｇ，２００３）
【発明の概要】
【発明が解決しようとする課題】
【００４１】
したがって、その精度が形状表現、または工具経路の離散的なサンプリングによって制限されない、任意の経路に沿って任意の形状を動かすことによって生成される掃引容積の高精度の表現を生成するための空間および時間効率の良い方法が必要とされている。さらに、概ね１メートルの寸法を有する工作物において、概ね数マイクロメートルのサイズを有する望ましくない特徴物を表現することができる空間および時間効率の良いＮＣフライス加工シミュレーションシステムが必要とされている。
【課題を解決するための手段】
【００４２】
サンプル点において物体の距離場を再構成する方法が提供され、物体は、経路に沿って或る形状を動かすことによって生成される掃引容積である。本方法はプロセッサ上で実行される。形状は、形状距離場によって表される。経路はパラメトリック関数によって表される。
【００４３】
サンプル点における距離データが求められ、距離データは、サンプル点における物体の距離場を特徴付ける。経路に沿った形状の最適な配置を定義する最適な１組のパラメータが連続的に求められる。
【００４４】
形状距離場を最適な配置に変換して、変換された形状距離場を生成する。サンプル点において、変換された形状距離場から距離データを求め、サンプル点において距離場を再構成する。
【発明の効果】
【００４５】
この発明によれば、掃引容積の高精度のモデルを表現し、レンダリングするための空間および時間効率の良い方法を提供することができる。
【図面の簡単な説明】
【００４６】
【図１】この発明の実施の形態１による、ＮＣフライス盤、ならびにＮＣフライス加工をシミュレートするためのシステムおよび方法のフロー図である。
【図２Ａ】フライス加工のために用いられる典型的な工具、および或る経路に沿ってそのような工具を動かすことによって行なわれる工作物における典型的な編集の図である。
【図２Ｂ】曲線経路に沿って２Ｄ形状を掃引することによって求められる掃引容積の概略図である。
【図３Ａ】工具の直線経路の図である。
【図３Ｂ】工具軸が経路に沿って変化する、工具の弧状経路の図である。
【図３Ｃ】工具の曲線経路の図である。
【図４】この発明の実施の形態１による、１組のＧコードまたはＮＣ機械命令を用いて或る工具形状による工作物のフライス加工をシミュレートするための方法のフロー図である。
【図５】サンプル点において或る形状の掃引容積の距離場を再構成するための方法のブロック図である。
【図６Ａ】掃引容積を離散的に近似するための従来技術の方法の図である。
【図６Ｂ】この発明の実施の形態１による、掃引容積の距離場を連続的に求めるための方法の図である。
【図６Ｃ】この発明の実施の形態１による、掃引容積の距離場を連続的に求めるための方法の図である。
【図７Ａ】フライス加工のために用いられる典型的な１組の円筒対称の工具の図である。
【図７Ｂ】図７Ａの工具の２次元断面図である。
【図７Ｃ】図７Ｂの断面の２次元距離場を示す図である。
【図８Ａ】パラメータｔによってパラメータ化される経路に沿って動く円筒対称工具の図である。
【図８Ｂ】この発明の実施の形態１による、サンプル点を円筒対称工具の断面の２次元距離場上にマッピングする、ｔによってパラメータ化される曲線の図である。
【発明を実施するための形態】
【００４７】
実施の形態１．
システムおよび方法の概説
図１はＮＣフライス加工システム１００、および数値制御（ＮＣ）フライス加工シミュレーションシステム１５０を示す。ＮＣフライス加工システム１００では、コンピュータ支援設計（ＣＡＤ）モデル１０２がコンピュータ支援製造（ＣＡＭ）システム１０４に入力され、ＣＡＭシステム１０４は、ＮＣフライス盤を制御するためのＧコード１０６を生成する。ＮＣフライス加工中に、ＧコードはＮＣフライス加工コンソール１０８に入力され、コンソール１０８は各Ｇコードを処理して、対応する１組のＮＣ機械命令１１０を生成する。ＮＣ機械命令はＮＣコントローラ１１２に入力され、ＮＣコントローラ１１２は、工作物をフライス加工するために、工作物１１８に対して工具１１６を動かす１組のモータ制御信号１１４を生成する。
【００４８】
シミュレーションシステム１５０は、入力として、コンピュータ支援製造システム１０４によって生成されたＧコード１０６、またはＮＣコンソール１０８によって生成されるＮＣ機械命令１１０を取り込むことができる。シミュレーションシステムへの入力はコンピュータプロセッサ１５２によって読み取られ、コンピュータプロセッサ１５２は工作物の機械加工をシミュレートし、シミュレートされたモデル１５４を出力し、モデル１５４はコンピュータメモリ１５６に格納することができる。プロセッサ１５２は、格納されるシミュレートされたモデル１５４をレンダリングして、レンダリングされた画像１５８を生成することができ、画像１５８は表示デバイス１６０に出力することができる。表示された画像１６２をコンピュータ支援設計モデル１０２と比較して、工作物の実際のＮＣフライス加工を実行する前に、Ｇコード１０６またはＮＣ機械命令１１０を検証することができる。
【００４９】
工具
図２Ａは、ＮＣフライス加工において用いられる１組の典型的な工具形状２０２、２０４、２０６および２０８を示す。工具が工作物２１０に対して動かされるとき、その工具は工作物から材料を削り出す。ここで、工具２０２、２０４、２０６および２０８は工作物から、表面２１２、２１４、２１６および２１８に対応する材料を除去する。各工具によって除去される材料の形状は、工具形状、および工作物に対する工具の経路によって決定される。除去される材料の形状は、工具が経路に沿って動くときの、工作物と工具の掃引容積との交差部分である。
【００５０】
本明細書においてＮＣフライス加工シミュレーションを重点的に取り扱うが、掃引容積は、コンピュータ支援設計、フリーフォーム設計、立体モデリング、ロボティックス、製造自動化および可視化を含む、科学、工学、およびコンピュータグラフィックスの多くの分野において用途を有する。
【００５１】
掃引容積
図２Ｂは、経路２５２に沿って動かされる形状２５０の掃引容積２６０を示す。経路２５２は、形状２５０の特定の点の位置を時間の関数として規定する。その経路は、その形状の向き２５６、２５７および２５８を時間の関数として規定することができる。また、その経路は、その形状のスケール、またはその形状の任意の変換を時間の関数として規定することもできる。図２Ｂでは、形状２５０の元の位置、向きおよび外形が、その形状が経路に沿って動くのに応じて、形状の２５４の最終的な位置、向きおよび外形に変換される。
【００５２】
工具経路
工作物に対する工具の経路は数多くの形において規定することができる。
【００５３】
図３Ａは直線経路を示しており、工具３０２が直線３０４に沿って動かされる。
【００５４】
図３Ｂは円弧状経路を示しており、工具３０２の先端３１０が円弧３１２に沿って動かされ、その経路の終点において、工具の元の軸方向３１４が最終的な軸方向３１６に変換される。
【００５５】
図３Ｃは曲線経路を示しており、工具３０２の先端３１０が曲線３２０に沿って動かされる。
【００５６】
他の取り得る経路形状は、数例を挙げると、工具を或る点に位置決めすること、ポリラインとして知られている一連の線に沿って工具を動かすこと、渦巻または螺旋形の曲線に沿って工具を動かすこと、２次ベジエ曲線または３次ベジエ曲線、或いは区分的多項式曲線として知られている一連の多項式曲線のような、多項式曲線に沿って工具を動かすことを含む。工作物の形状または材料組成によって影響を及ぼされる経路のような、或る手順によって定義される経路を含む、シミュレートすることができる任意の形の経路を考えることができる。
【００５７】
フライス加工シミュレーション
図４は、シミュレーションプロセッサ４００を用いて或る工具形状による工作物のフライス加工をシミュレートし、フライス加工される工作物の表現をメモリ４４０に格納し、レンダリングプロセッサ４６０を用いて、フライス加工される工作物の表現を表示デバイス４８０にレンダリングするための方法を示す。
【００５８】
工作物形状、および１組の距離場４０４から複合距離場を再構成するための方法を用いて、複合ＡＤＦ４４４が生成され、メモリ４４０に格納される場合がある。工作物形状は、工作物外形４０２によって規定され、１組の幾何学的要素を含む。
【００５９】
工作物外形の各幾何学的要素は、１組の幾何学的要素距離場を規定する距離場表現に変換される。各幾何学的要素距離場は、数例を挙げると、解析距離関数、陰距離関数、規則的にサンプリングされる距離場、ＡＤＦ、距離関数の合成、または手順のうちの１つとして表すことができる。
【００６０】
フライス加工シミュレーションのための好ましい実施形態では、複合ＡＤＦが８分木としてメモリに格納され、８分木は、工作物形状のバウンディングボックスを取り囲む根セルで開始してトップダウンで生成される。工作物外形４０２内の各特定の幾何学的要素の距離場表現が、複合ＡＤＦの葉セルに追加され、葉セルの距離場は特定の幾何学的要素によって影響を及ぼされる。レンダリングおよび処理中に、複合距離場再構成法４０４を用いて葉セル内の距離場を合成することによって、サンプル点において特定の葉セルの距離場を再構成することができる。
【００６１】
種々の合成方法が可能であり、当該技術分野において知られている。好ましい実施形態では、その合成はブール減算演算子を用いて、工具によって掃引される容積による工作物からの材料の除去をシミュレートする。
【００６２】
ＡＤＦ生成中に、規定された最大数よりも多くの距離場を含む葉セルが細分され、各葉セル内の距離場が複雑になるのを制限する。したがって、複合ＡＤＦはディテール指向である；少ない距離場によって影響を及ぼされる工作物の領域ほど、大きなセルが生じ、多くの距離場によって影響を及ぼされる工作物の領域ほど、小さなセルが生じる。
【００６３】
複合ＡＤＦに新たな距離場を追加することによって、或る葉セル内の距離場の関連がなくなる場合には、関連のない距離場は葉セルから除去される。たとえば、工具運動が或る葉セルからすべての材料を除去する場合には、その葉セル内のすべての距離場の関連がなくなる場合があり、その葉セルは距離場を除去され、外部セルとしてラベル付けされる。
【００６４】
したがって、新たな工具運動のシミュレーションは、或る葉セルおよびその同胞内の既存の数の距離場を規定された最大数未満に削減することができる。この場合、その葉セルおよび同胞の距離場はその共通の親セル内に配置され、その葉セルおよび同胞は複合ＡＤＦから削除される。
【００６５】
フライス加工シミュレーション法は、工具形状４０８から形状距離場４１２を定義し（４１０）、形状距離場４１２は、数例を挙げると、解析距離関数、陰距離関数、規則的にサンプリングされる距離場、ＡＤＦ、距離関数の合成、または手順のうちの１つとすることができる。
【００６６】
ＮＣ機械命令４１４、または代わりに、Ｇコード４１６を用いて、工具の運動に対応するパラメトリック経路関数４２０を定義する。工具運動ごとに、形状距離場１２およびパラメトリック経路関数４２０を用いて、工具運動に対応する工具の掃引容積を表す掃引容積距離場４２４を定義する（４２２）。
【００６７】
工具運動による工作物のフライス加工をシミュレートするために、複合ＡＤＦ４４４が、掃引容積距離場４２４を用いて編集される（４２６）。編集中に、掃引容積距離場が、工具の掃引容積によって横切られる複合ＡＤＦのセルに追加され、それによって横切られたセル内のＡＤＦが再生される。
【００６８】
複合ＡＤＦを用いて、レンダリングモデル要素から成るレンダリングモデル４６４を生成することができ（４６２）、表示デバイス４８０にレンダリングすることができる（４６６）。ポイントレンダリング、三角形レンダリングおよびレイトレーシングのような、当該技術分野において知られているレンダリング法を用いて、レンダリングモデル４６４を生成し、レンダリングすることができる。
【００６９】
フライス加工シミュレーションのための代替の実施形態では、各ＮＣ機械命令４１４またはＧコード４１６に対応する各形状距離場、および工作物外形４０２の各幾何学的要素に対応する各距離場が、対応するＮＣ機械命令、Ｇコードまたは幾何学的要素のための固有識別子を割り当てられる。
【００７０】
レンダリングモデル生成４６２中に、レンダリングモデル４６４の各特定の要素が、特定のレンダリングモデル要素に寄与する距離場の固有識別子で注釈を付される。１組のレンダリング属性を各固有識別子と関連付けることによって、レンダリングモデル４６４は、どの幾何学的要素、およびどの工具経路が工作物の各部分に寄与するかを符号化する。たとえば、固有の色を、特定のＧコードの形状距離場の識別子と関連付けることによって、特定のＧコードによって影響を及ぼされる工作物の領域を、表示デバイス４８０上で容易に可視化することができる。
【００７１】
代替形態として、不透明度を複合ＡＤＦ内の特定の距離場内の識別子と関連付けることができる。たとえば、特定の工具運動に対応する特定の距離場に関連付けられるレンダリング要素を透明としてレンダリングすることができる。代替的には、固有識別子をブール演算子と関連付けることができ、そのブール演算子は、対応するレンダリング要素がレンダリングされるべきであるか否かを指示する。他のレンダリング属性を用いて、付加的な効果を生成し、フライス加工される工作物の可視化を支援することができる。
【００７２】
距離場は物理的なシミュレーションにおいて数多くの利点を有する。フライス加工シミュレーションのための代替の実施形態は、距離場を用いて、ＮＣフライス加工工程を検証する。たとえば、フライス加工シミュレータ４００によって生成される複合ＡＤＦ４４４を、コンピュータ支援設計モデル１０２の距離場表現と比較することができる。その比較は、表示デバイス４８０を用いて外観検査によって行なうことができる。
【００７３】
代替的には、その比較は、複数のサンプル点において、複合ＡＤＦ４４４およびコンピュータ支援設計モデル１０２の距離場をサンプリングし、それらのサンプル点において距離データを比較することによって行なうことができる。代替的には、その比較は、複合ＡＤＦ４４４およびコンピュータ支援設計モデル１０２の距離場の一方を他方から減算することにより差距離場を生成し、差距離場を可視化することによって行なうことができる。
【００７４】
また、距離場を用いて、各工具運動によって除去される材料の或る物理的特性を測定することもできる。たとえば、特定の工具運動の場合に、工作物と、特定の工具運動に対応する掃引容積との交差を表す交差距離場を生成することができる。その後、交差距離場を処理して、数例を挙げると、その質量、体積、または慣性モーメントを含む、その特定の工具運動によって除去される材料の種々の特性を求めることができる。
【００７５】
掃引容積の距離場の再構成
図５は、プロセッサ５００を用いて、サンプル点において掃引容積の距離場を再構成するための方法を示す。形状距離場５０４およびパラメトリック経路関数５０６が、上記のように、工具および工具運動を規定する。サンプル点５０２を与えられると、掃引容積再構成法５１０は、そのサンプル点５０２において距離場を再構成するために、そのサンプル点における距離データを求める。その方法は、経路に沿った工具の最適な配置を「連続的に」求める（５１２）。
【００７６】
最適な１組のパラメータを求めている（５１２）最中に、その経路に沿った工具形状の初期配置を定義する１組の初期パラメータが選択される。好ましい実施形態では、その経路は単一のパラメータｔによってパラメータ化され、パラメータｔは、その経路に沿って工具が移動する時間に対応し、ｔの初期値が選択される（５１４）。形状距離場は、その経路に沿って時刻ｔにおいて工具の形状を配置するように変換され（５１６）、サンプル点５０２において形状距離場が再構成される（５１８）。
【００７７】
サンプル点において再構成される距離データは、数例を挙げると、サンプル点から変換された形状までの距離、距離場の勾配、および距離場の偏導関数を含むことができる。
【００７８】
その形状を経路に沿ってサンプリング点に近い配置に動かすために、再構成された距離データを用いて、パラメータ値ｔを繰返し変更する（５２０）。その変更は連続的に行われ、すなわち、所定の１組の離散値からｔを選択するのではなく、パラメータｔは、その経路に沿った形状の位置を改善する方向に任意の量だけ繰返し変更される。その変更は、最適なｔが求められるまで、または繰り返しているうちにｔの変化がｔの或る最小変化未満になるまで、または繰返しの最大数が行なわれるまで繰り返される。最適なｔが求められると、その形状は、対応する最適な配置に変換され（５３０）、変換された形状から距離データが再構成されて（５４０）、サンプル点５０２において距離データが求められる（５１０）。
【００７９】
図６Ａは、サンプル点６０１において掃引容積の距離場を離散的に再構成するための従来技術の方法を示す。工具形状６０２が、１組の離散時刻ｔ０ ６０６、ｔ１ ６０８、・・・、ｔＮ−１ ６１０に対応する、工具経路６０４に沿った離散的な１組の配置に置かれる。
【００８０】
サンプリングされる時刻ごとに、Ｐ ６０１から工具形状までの対応するサンプリングされる距離が求められる。この図では、離散時刻ｔｉ ６１２およびｔｉ＋１ ６１４が最適な時間を挟む。従来技術の方法は、以下のうちの１つとしてＰ ６０１から掃引容積までの距離を近似する：１）ｔｉおよびｔｉ＋１について求められる距離の最小値、２）ｔｉおよびｔｉ＋１について求められる距離の平均または混合、または３）時刻ｔ＊において配置されるときの形状までの距離。ただし、ｔ＊はｔｉおよびｔｉ＋１の重み付け平均として求められる。
【００８１】
図６Ｂはこの発明の好ましい実施形態を示す。工具形状６０２は最初に、経路６０４に沿ってパラメータｔに対応する配置に置かれる。工具形状６０２の距離場からのサンプル点Ｐ ６０１における距離データ６２２を用いて、その形状を経路に沿って、最適なパラメータｔ＊６２６によって定義される最適な配置の方向に向かって点ｔ＋Δｔ ６２４まで連続的に動かす。
【００８２】
その好ましい実施形態では、サンプル点における距離場の勾配を用いて、パラメータｔを変更する。その変更は、その形状を経路に沿って、距離場の外向きの勾配ベクトルと一致する方向に動かす。この方向は、ｔにおける経路の接線ベクトルと外向きの勾配ベクトルとのドット積をとることによって求められる。そのドット積が正である場合には、パラメータｔを大きくし、そのドット積が負である場合には小さくする。そのドット積の大きさは、ｔの変化に関する尺度を与える。ドット積が０に近い場合には、その形状は局所的に距離場に直交し、ｔのための最適値が求められたことを指示する。
【００８３】
その経路が２つ以上のパラメータによってパラメータ化される場合には、各経路パラメータに関する偏導関数を用いて、ｔを変更することができる。
【００８４】
連続的に最適化する際の最も大きな難題のうちの１つは、局所的な最適値が存在することによって、連続最適化問題の出力が大域的な最適値であることを保証するのが難しくなることである。工具形状および工具経路が相対的に複雑である場合には、いくつかの局所的な最適値が存在する場合がある。代替の実施形態では、これは、上記の方法への２つの変更を用いて解決される。
【００８５】
第１の変更では、ｔが相対的に少ない数のサンプリングされる時刻においてサンプリングされ、サンプリングされる時刻ごとに距離データが再構成される。サンプリングされる時刻の中から、形状がサンプル点に最も近い時刻ｔを選択することによって、大域的な最大値に収束する可能性が最も高い点において、最適化問題が初期化される。２つ以上のサンプリングされる時刻が有力である場合には、大域的な最適値を見つけるために、その方法を各有力なサンプリングされる時間において初期化することができる。
【００８６】
第２の変更は図６Ｃに示される。この変更では、最適なｔ ６２６を挟むものと判断される開始時刻ｔＳ ６３０および終了時刻ｔＥ ６３４が初期化される。ｔを変更するための方法が両方の値ｔＳ ６３０およびｔＥ ６３４を互いに向かって動かすことになる場合には、２つのｔ値は最適なｔ値を挟む。その変更を繰り返す度に、サンプル点Ｐ ６０１において、ｔＳ ６３０およびｔＥ ６３４にそれぞれ対応する距離データ６３２および６３６が求められ、ｔＳ ６３０とｔＥ ６３４との間の最適ｔ値が求められるまで、ｔＳおよびｔＥのうちの一方または両方が他方に向かって動かされる。
【００８７】
好ましい実施形態、ならびに第１の変更および第２の変更に対する種々の代替形態が存在する。パラメータｔを連続的に変更するためのさらなる代替方法を、連続最適化の分野に精通している人に知られている技法から導出できることは当業者には理解されたい。
【００８８】
複数のサンプル点における距離場の数値計算
複合ＡＤＦをレンダリングすること、または物体間の衝突を検出するために複合ＡＤＦを使用することのような特定の処理では、複数のサンプル点においてＡＤＦの距離場が再構成される必要がある。
【００８９】
たとえば、複合ＡＤＦを点モデルに変換して、ポイントレンダリングを介して表示デバイスにレンダリングすることができる。点モデルは点として知られている１組の幾何学的基本要素を含み、各点は空間内の位置および１組のレンダリング属性に関連付けられる。レンダリング中に、複数の点が画像位置にマッピングされ、レンダリング属性を用いてその画像にレンダリングされる。レンダリング属性の例をいくつか挙げると、点の色、不透明度、サイズ、反射率特性および法線ベクトルを含む。
【００９０】
１組の点における各点は、以下のステップで複合ＡＤＦを用いて生成することができる。第１に、その点の位置が複合ＡＤＦのセル内の位置に初期化される。第２に、その点の位置において距離場が再構成され、距離場の大きさおよび勾配ベクトルを用いて、その点が複合ＡＤＦの表面に向かって動かされる。その点が複合ＡＤＦの表面上に存在することを再構成された距離が指示するまで、第２のステップが繰り返される。最後に、距離場が再構成され、その点にレンダリング属性を割り当てるために用いられる。たとえば、その点は、その点の位置に影響を及ぼす距離場の固有識別子に基づいて、色を割り当てられる場合がある。第２の例として、その点は、複合ＡＤＦの局所的な勾配に基づいて、法線ベクトルを割り当てられる場合がある。
【００９１】
代替的に、レイキャスティングまたはレイトレーシングを用いて複合ＡＤＦを画像に変換し、画像として表示デバイスにレンダリングすることができる。レイキャスティング中に、画像内のピクセルごとに１組の光線が複合ＡＤＦ内に投光される。複合ＡＤＦの表面を横切る各光線は、交点において複合ＡＤＦから再構成される距離データに従って、１組のレンダリング属性を割り当てられる。各組の光線のレンダリング属性を合成して、画像内の対応する各ピクセルの色が求められる。
【００９２】
光線に沿った種々のサンプル点において複合ＡＤＦから距離データを再構成することによって、その光線と複合ＡＤＦの表面との間の交点が特定される。掃引容積の距離場を再構成するための上記の方法と同じように、交点は、離散的に、または連続的に特定することができる。その交点が離散的に特定される場合には、その表面に最も近いサンプル点の混合を用いて、その交点を近似することができる。交点が連続的に特定される場合には、連続最適化法を用いて、その交点が求められる。
【００９３】
また、２つの物体間の衝突を検出するには、距離データが、複数のサンプル点において複合ＡＤＦから再構成される必要がある。２つの物体間の衝突は、いくつかの方法で、再構成された距離データから検出することができる。たとえば、物体のうちの一方のための距離データを他方の物体上で１組の表面点として再構成して、第２の物体の第１の物体に対する近接性の指標を求めることができる。その近接性データが、２つの物体が或る最小しきい値距離よりも近いことを指示する場合には、２つの物体間の衝突が検出される。
【００９４】
求められた近接性データは、物体のうちの一方の形状を変更するために、または物体のうちの一方の経路を変更して、たとえば、衝突を回避するために、ＮＣフライス加工シミュレーション、ロボット経路計画および製造のような用途において用いることができる。
【００９５】
円筒対称工具
上記のように、複合ＡＤＦをレンダリングすること、または物体間の衝突を検出するために複合ＡＤＦを使用することなどの特定の用途では、複数のサンプル点において複合ＡＤＦが再構成される必要がある。再構成法の効率を改善するために、円筒対称の工具形状に合うように好ましい実施形態を変更することができる。
【００９６】
円筒対称工具が或る経路に沿って動く場合、サンプル点に対して最も近い工具表面上の点は常に、サンプル点と、その経路に沿った工具のすべての配置のための工具軸とを含む平面上に存在する。工具軸を通る平面は、工具の断面を画定する。工具は円筒対称であるため、断面の形状は、工具軸を通るいかなる平面の場合にも同じである。
【００９７】
図７Ａは、ＮＣフライス加工のために用いられる典型的な１組の円筒対称工具７０２、７０３、７０４および７０５を示す。
【００９８】
図７Ｂは、それぞれ、工具７０２、７０３、７０４および７０５のそれぞれの２次元断面７１２、７１３、７１４および７１５を示す。
【００９９】
図７Ｃは、２次元断面７１２、７１３、７１４および７１５をそれぞれ表す２次元距離場７２２、７２３、７２４および７２５を示す。
【０１００】
或るサンプル点から、或る経路に沿って動く円筒対称工具形状までの距離は、工具の断面がそのサンプル点を含む平面内に存在するときに、そのサンプル点から、その断面のエッジまでの距離に等しい。
【０１０１】
したがって、この発明の代替の実施形態は、サンプル点を工具形状の断面の２次元座標にマッピングし、工具形状の２次元断面を表す２次元距離場から距離データを計算することによって距離データを求める。
【０１０２】
図８Ａは、開始時刻ｔＳ ８０４から終了時刻ｔＥ ８０８まで経路８０１に沿って動き、任意の時刻ｔ ８０６を通過する工具８０２を示す。この発明の好ましい実施形態によれば、サンプル点Ｐ ８０３において距離データを連続的に再構成することができる。
【０１０３】
代替の実施形態では、図８Ｂに示されるように、その経路に沿った時刻ごとに、点Ｐ ８０６が、２次元距離場８２０として表される、工具の断面の２次元座標系にマッピングされる。たとえば、サンプル点Ｐ ８０６は、その経路に沿った時刻ｔＳにおける工具の配置に対応するサンプル点Ｐ’（ｔＳ）にマッピングされ、その経路に沿った時刻ｔＥにおける工具の配置に対応するサンプル点Ｐ’（ｔＥ）にマッピングされ、且つその経路に沿った時刻ｔにおける工具の配置に対応するサンプル点Ｐ’（ｔ）にマッピングされる。
【０１０４】
図８Ｂに示されるように、１組のマッピングされたサンプル点は、その工具の断面の２次元座標空間内のマッピングされた経路８１４を定義する。したがって、代替の実施形態では、工具形状が物体に最も近い点は、マッピングされた経路を連続的に探索することによって求められる。
【０１０５】
数多くのサンプル点が数値計算されることになる場合には、複数の方法において、代替の実施形態の効率をさらに改善することができる。たとえば、マッピングされた経路は複数の区間に分割することができ、各区間は、局所的に滑らかである工具の断面の２次元距離場の領域を通る。言い換えると、距離場が或る経路区間内で少なくともＣ１連続であるように、その経路が距離場の不連続点を横切る点において、その経路を分割することができる。本明細書において定義されるように、Ｃ１連続は、距離場の１次導関数が、その経路区間に沿って連続であることを意味する。代替的には、距離場が、連続最適化法の信頼性および効率を改善するために当該技術分野において知られている特性を、或る経路区間に沿って２次までの範囲で変化させるように、経路を分割することができる。
【０１０６】
動作環境
この発明は、数多くの汎用または専用コンピューティングシステム環境または構成で動作する。この発明と共に用いるのに適している既知のコンピューティングシステム、環境および／または構成の例は、限定はしないが、パーソナルコンピュータ、サーバコンピュータ、ハンドヘルドデバイスまたはラップトップデバイス、マルチプロセッサまたはマルチコアシステム、グラフィックス処理ユニット（ＧＰＵ）、特定用途向け集積回路（ＡＳＩＣ）、フィールドプログラマブルゲートアレイ（ＦＰＧＡ）、マイクロコントローラベースシステム、ネットワークＰＣ、メインフレームコンピュータ、上記のシステムまたはデバイスのうちの任意のものを含む分散コンピューティング環境など、すなわち、一般的にはプロセッサを含む。モニタまたは他のタイプの表示デバイス１６０が、上記のシステムのうちの任意のものに接続され、この発明を可視化する（１６２）ことを可能にする。
【０１０７】
この発明を、好ましい実施形態の例として説明してきたが、この発明の精神および範囲内で他のさまざまな適合および変更を行えることが理解されるべきである。したがって、この発明の真の精神および範囲内に入るすべての変形および変更を包含することが、添付の特許請求の範囲の目的である。
【特許請求の範囲】
【請求項１】
サンプル点において物体の距離場を再構成する方法であって、前記方法のステップを実行するためのプロセッサを備え、前記物体は、経路に沿って或る形状を動かすことによって生成される掃引容積を含み、
前記方法は、
前記形状を形状距離場によって表すステップと、
前記経路をパラメトリック関数によって表すステップと、
前記サンプル点における距離データを求めるステップと、を含み、
前記距離データは、前記サンプル点における前記物体の前記距離場を特徴付け、
前記距離データを求めるステップは、
前記経路を表す前記パラメトリック関数の最適な１組のパラメータを連続的に求めるステップであって、前記最適な１組のパラメータは、前記経路に沿った前記形状の最適な配置を定義する、ステップと、
前記形状距離場を前記最適な配置に変換するステップであって、変換された形状距離場を生成するステップと、
前記サンプル点において前記変換された形状距離場から距離データを求めるステップであって、前記サンプル点において前記距離場を再構成するステップと、
をさらに含む、方法。
【請求項２】
前記パラメトリック関数の前記最適な１組のパラメータを求めるステップは、
前記経路に沿った前記形状の特定の配置に対応する前記パラメトリック関数の特定の１組のパラメータを選択するステップと、
前記形状距離場を変換するステップであって、前記形状を前記特定の配置に置くステップと、
前記変換された形状距離場から前記サンプル点における距離データを求めるステップと、
前記最適な１組のパラメータが求められるまで、前記距離データを用いて前記特定の１組のパラメータを繰返し変更するステップと、
をさらに含む、請求項１に記載の方法。
【請求項３】
複数のサンプル点において前記物体の前記距離場を再構成するステップであって、前記物体を表示デバイスにレンダリングするステップ、をさらに含む、請求項１に記載の方法。
【請求項４】
前記物体を前記表示デバイスにレンダリングするための１組の表面点を生成するステップを含み、前記１組の表面点は、前記複数のサンプル点の一部を含み、
各特定の前記表面点を生成するステップは、
前記複数のサンプル点の特定のサンプル点において前記特定の表面点を位置決めするステップと、
前記特定の表面点における前記再構成された距離データを用いて、前記特定の表面点を前記物体の前記表面に動かすステップと、
前記特定の表面点における前記再構成された距離データから、前記特定の表面点に関するレンダリング属性を求めるステップと、
前記レンダリング属性を用いて、前記特定の表面点を前記表示デバイスにレンダリングするステップと、
をさらに含む、請求項３に記載の方法。
【請求項５】
前記物体を前記表示デバイスにレンダリングするための前記物体の画像を生成するステップと、
前記画像を前記表示デバイスにレンダリングするステップと、を含み、
前記画像は、１組のピクセルを含み、
前記１組のピクセル内の各ピクセルを生成するステップは、
前記ピクセルから１組の光線を前記物体に向けて投光するステップであって、各光線は、前記複数のサンプル点からの特定の１組のサンプル点に関連付けられる、ステップと、
前記特定の１組のサンプル点内の一部のサンプル点において再構成された前記距離データを用いて、前記１組の光線内の前記光線ごとに、前記光線と前記物体の表面との間の交点を求めるステップと、
前記１組の光線内の前記光線ごとに、前記交点における交差距離データを再構成するステップと、
前記１組の光線の前記交差距離データを組み合わせるステップであって、前記ピクセルの色を求めるステップと、
をさらに含む、請求項３に記載の方法。
【請求項６】
複数のサンプル点において前記距離場を再構成するステップであって、前記物体と基準物体との間の近接性データを検出するステップ、を含む、請求項１に記載の方法。
【請求項７】
前記形状は工具形状であり、前記基準物体は工作物である、請求項６に記載の方法。
【請求項８】
前記近接性データを用いるステップであって、前記物体と前記基準物体との間の衝突を検出するステップ、をさらに含む、請求項６に記載の方法。
【請求項９】
前記近接性データを用いるステップであって、前記形状を変更するステップ、をさらに含む請求項６に記載の方法。
【請求項１０】
前記近接性データを用いるステップであって、前記基準物体を変更するステップ、をさらに含む請求項６に記載の方法。
【請求項１１】
前記近接性データを用いるステップであって、前記経路を変更するステップ、をさらに含む請求項６に記載の方法。
【請求項１２】
前記物体および前記基準物体から、交差の適応的にサンプリングされる距離場（ＡＤＦ）を生成するステップであって、前記交差ＡＤＦは、前記物体と前記基準物体との交差を表す、ステップと、
前記交差ＡＤＦから、前記物体と前記基準物体との交差の物理特性を求めるステップであって、前記物理特性は、材料体積、表面積、面積、材料質量、慣性モーメント、およびそれらの組み合わせを含む群から選択される、ステップと、
をさらに含む、請求項６に記載の方法。
【請求項１３】
前記距離データから前記物体の特性を求めるステップであって、前記特性は、材料体積、表面積、面積、材料質量、または慣性モーメントを含む、ステップ、をさらに含む、請求項１に記載の方法。
【請求項１４】
前記形状は、３次元且つ円筒対称であり、前記形状距離場は、前記円筒対称形状の２次元断面を表す２次元距離場であり、
前記方法は、
前記形状の前記経路を前記形状の前記２次元断面の２次元座標系にマッピングするステップと、
前記２次元座標系内の前記形状の前記経路を表す前記パラメトリック関数を定義するステップと、
をさらに含む、請求項１に記載の方法。
【請求項１５】
前記形状距離場は、距離マップ、適応的にサンプリングされる距離場（ＡＤＦ）、解析関数、陰関数、距離場の合成、または手順から成る群から選択される、請求項１に記載の方法。
【請求項１６】
前記パラメトリック関数は、点、線、折れ線、円弧、曲線、渦巻曲線、螺旋曲線、多項式曲線、２次ベジエ曲線、３次ベジエ曲線、区分的多項式曲線、および手続き的曲線（ｐｒｏｃｅｄｕｒａｌ ｃｕｒｖｅ）のうちの１つを含む前記経路を表す、請求項１に記載の方法。
【請求項１７】
前記パラメトリック関数は、前記形状の１組の属性を特定し、前記１組の属性は、前記形状の位置、前記形状の向き、前記形状のスケール、または前記形状の一般的な変形を含む、請求項１に記載の方法。
【請求項１８】
前記距離データは、前記サンプルから前記物体への距離、前記サンプル点における前記距離場の勾配、または前記サンプル点における前記距離場の偏導関数を含む、請求項１に記載の方法。
【請求項１９】
前記特定の１組のパラメータを選択するステップは、
パラメータの１組のサンプリングされた組を求めるステップであって、前記パラメータの１組のサンプリングされた組は、前記経路に沿った１組のサンプリングされた配置に対応する、ステップと、
前記パラメータの１組のサンプリングされた組から前記特定の１組のパラメータを選択するステップと、
をさらに含む、請求項２に記載の方法。
【請求項２０】
前記最適な１組のパラメータを求めるステップは、
前記形状の第２の配置に対応する第２の１組のパラメータを選択するステップであって、前記特定の配置および前記第２の配置は、前記経路に沿った前記形状の最適な配置を挟む、ステップと、
前記最適な１組のパラメータを求めるステップの間に、前記第２の１組のパラメータを繰り返し変更するステップであって、前記経路に沿った前記形状の最適な配置を挟み続けるようにする、ステップと、
をさらに含む、請求項２に記載の方法。
【請求項２１】
前記特定の１組のパラメータを変更するために用いられる前記距離データは、距離値、前記変換された形状距離場の勾配、または前記変換された形状距離場の偏導関数を含む、請求項２に記載の方法。
【請求項２２】
前記特定の１組のパラメータを変更するステップは、
前記特定の１組のパラメータに対応する経路データを求めるステップと、
前記経路データを用いて前記特定の１組のパラメータを変更するステップと、
をさらに含む、請求項２に記載の方法。
【請求項２３】
前記経路データは、前記経路の接線ベクトル、または前記特定の１組のパラメータ内の特定のパラメータに関する前記経路の偏導関数を含む、請求項２２に記載の方法。
【請求項２４】
前記経路を前処理するステップであって、前記最適な１組のパラメータを求めるステップの効率を改善するステップ、をさらに含む、請求項１４に記載の方法。
【請求項２５】
前記前処理することは、
前記経路を複数の経路区間に分割するステップであって、前記複数の経路区間の各々は、前記２次元距離場の領域にマッピングし、前記２次元距離場の１次導関数は前記領域内で連続である、ステップ、をさらに含む、請求項２４に記載の方法。
【請求項２６】
前記前処理するステップは、
前記経路を複数の経路区間に分割するステップであって、各特定の経路区間は、前記２次元距離場の領域に対応し、前記距離場は、前記領域内で前記経路区間に沿って２次的に変化する、ステップ、
を含む、請求項２４に記載の方法。
【請求項１】
サンプル点において物体の距離場を再構成する方法であって、前記方法のステップを実行するためのプロセッサを備え、前記物体は、経路に沿って或る形状を動かすことによって生成される掃引容積を含み、
前記方法は、
前記形状を形状距離場によって表すステップと、
前記経路をパラメトリック関数によって表すステップと、
前記サンプル点における距離データを求めるステップと、を含み、
前記距離データは、前記サンプル点における前記物体の前記距離場を特徴付け、
前記距離データを求めるステップは、
前記経路を表す前記パラメトリック関数の最適な１組のパラメータを連続的に求めるステップであって、前記最適な１組のパラメータは、前記経路に沿った前記形状の最適な配置を定義する、ステップと、
前記形状距離場を前記最適な配置に変換するステップであって、変換された形状距離場を生成するステップと、
前記サンプル点において前記変換された形状距離場から距離データを求めるステップであって、前記サンプル点において前記距離場を再構成するステップと、
をさらに含む、方法。
【請求項２】
前記パラメトリック関数の前記最適な１組のパラメータを求めるステップは、
前記経路に沿った前記形状の特定の配置に対応する前記パラメトリック関数の特定の１組のパラメータを選択するステップと、
前記形状距離場を変換するステップであって、前記形状を前記特定の配置に置くステップと、
前記変換された形状距離場から前記サンプル点における距離データを求めるステップと、
前記最適な１組のパラメータが求められるまで、前記距離データを用いて前記特定の１組のパラメータを繰返し変更するステップと、
をさらに含む、請求項１に記載の方法。
【請求項３】
複数のサンプル点において前記物体の前記距離場を再構成するステップであって、前記物体を表示デバイスにレンダリングするステップ、をさらに含む、請求項１に記載の方法。
【請求項４】
前記物体を前記表示デバイスにレンダリングするための１組の表面点を生成するステップを含み、前記１組の表面点は、前記複数のサンプル点の一部を含み、
各特定の前記表面点を生成するステップは、
前記複数のサンプル点の特定のサンプル点において前記特定の表面点を位置決めするステップと、
前記特定の表面点における前記再構成された距離データを用いて、前記特定の表面点を前記物体の前記表面に動かすステップと、
前記特定の表面点における前記再構成された距離データから、前記特定の表面点に関するレンダリング属性を求めるステップと、
前記レンダリング属性を用いて、前記特定の表面点を前記表示デバイスにレンダリングするステップと、
をさらに含む、請求項３に記載の方法。
【請求項５】
前記物体を前記表示デバイスにレンダリングするための前記物体の画像を生成するステップと、
前記画像を前記表示デバイスにレンダリングするステップと、を含み、
前記画像は、１組のピクセルを含み、
前記１組のピクセル内の各ピクセルを生成するステップは、
前記ピクセルから１組の光線を前記物体に向けて投光するステップであって、各光線は、前記複数のサンプル点からの特定の１組のサンプル点に関連付けられる、ステップと、
前記特定の１組のサンプル点内の一部のサンプル点において再構成された前記距離データを用いて、前記１組の光線内の前記光線ごとに、前記光線と前記物体の表面との間の交点を求めるステップと、
前記１組の光線内の前記光線ごとに、前記交点における交差距離データを再構成するステップと、
前記１組の光線の前記交差距離データを組み合わせるステップであって、前記ピクセルの色を求めるステップと、
をさらに含む、請求項３に記載の方法。
【請求項６】
複数のサンプル点において前記距離場を再構成するステップであって、前記物体と基準物体との間の近接性データを検出するステップ、を含む、請求項１に記載の方法。
【請求項７】
前記形状は工具形状であり、前記基準物体は工作物である、請求項６に記載の方法。
【請求項８】
前記近接性データを用いるステップであって、前記物体と前記基準物体との間の衝突を検出するステップ、をさらに含む、請求項６に記載の方法。
【請求項９】
前記近接性データを用いるステップであって、前記形状を変更するステップ、をさらに含む請求項６に記載の方法。
【請求項１０】
前記近接性データを用いるステップであって、前記基準物体を変更するステップ、をさらに含む請求項６に記載の方法。
【請求項１１】
前記近接性データを用いるステップであって、前記経路を変更するステップ、をさらに含む請求項６に記載の方法。
【請求項１２】
前記物体および前記基準物体から、交差の適応的にサンプリングされる距離場（ＡＤＦ）を生成するステップであって、前記交差ＡＤＦは、前記物体と前記基準物体との交差を表す、ステップと、
前記交差ＡＤＦから、前記物体と前記基準物体との交差の物理特性を求めるステップであって、前記物理特性は、材料体積、表面積、面積、材料質量、慣性モーメント、およびそれらの組み合わせを含む群から選択される、ステップと、
をさらに含む、請求項６に記載の方法。
【請求項１３】
前記距離データから前記物体の特性を求めるステップであって、前記特性は、材料体積、表面積、面積、材料質量、または慣性モーメントを含む、ステップ、をさらに含む、請求項１に記載の方法。
【請求項１４】
前記形状は、３次元且つ円筒対称であり、前記形状距離場は、前記円筒対称形状の２次元断面を表す２次元距離場であり、
前記方法は、
前記形状の前記経路を前記形状の前記２次元断面の２次元座標系にマッピングするステップと、
前記２次元座標系内の前記形状の前記経路を表す前記パラメトリック関数を定義するステップと、
をさらに含む、請求項１に記載の方法。
【請求項１５】
前記形状距離場は、距離マップ、適応的にサンプリングされる距離場（ＡＤＦ）、解析関数、陰関数、距離場の合成、または手順から成る群から選択される、請求項１に記載の方法。
【請求項１６】
前記パラメトリック関数は、点、線、折れ線、円弧、曲線、渦巻曲線、螺旋曲線、多項式曲線、２次ベジエ曲線、３次ベジエ曲線、区分的多項式曲線、および手続き的曲線（ｐｒｏｃｅｄｕｒａｌ ｃｕｒｖｅ）のうちの１つを含む前記経路を表す、請求項１に記載の方法。
【請求項１７】
前記パラメトリック関数は、前記形状の１組の属性を特定し、前記１組の属性は、前記形状の位置、前記形状の向き、前記形状のスケール、または前記形状の一般的な変形を含む、請求項１に記載の方法。
【請求項１８】
前記距離データは、前記サンプルから前記物体への距離、前記サンプル点における前記距離場の勾配、または前記サンプル点における前記距離場の偏導関数を含む、請求項１に記載の方法。
【請求項１９】
前記特定の１組のパラメータを選択するステップは、
パラメータの１組のサンプリングされた組を求めるステップであって、前記パラメータの１組のサンプリングされた組は、前記経路に沿った１組のサンプリングされた配置に対応する、ステップと、
前記パラメータの１組のサンプリングされた組から前記特定の１組のパラメータを選択するステップと、
をさらに含む、請求項２に記載の方法。
【請求項２０】
前記最適な１組のパラメータを求めるステップは、
前記形状の第２の配置に対応する第２の１組のパラメータを選択するステップであって、前記特定の配置および前記第２の配置は、前記経路に沿った前記形状の最適な配置を挟む、ステップと、
前記最適な１組のパラメータを求めるステップの間に、前記第２の１組のパラメータを繰り返し変更するステップであって、前記経路に沿った前記形状の最適な配置を挟み続けるようにする、ステップと、
をさらに含む、請求項２に記載の方法。
【請求項２１】
前記特定の１組のパラメータを変更するために用いられる前記距離データは、距離値、前記変換された形状距離場の勾配、または前記変換された形状距離場の偏導関数を含む、請求項２に記載の方法。
【請求項２２】
前記特定の１組のパラメータを変更するステップは、
前記特定の１組のパラメータに対応する経路データを求めるステップと、
前記経路データを用いて前記特定の１組のパラメータを変更するステップと、
をさらに含む、請求項２に記載の方法。
【請求項２３】
前記経路データは、前記経路の接線ベクトル、または前記特定の１組のパラメータ内の特定のパラメータに関する前記経路の偏導関数を含む、請求項２２に記載の方法。
【請求項２４】
前記経路を前処理するステップであって、前記最適な１組のパラメータを求めるステップの効率を改善するステップ、をさらに含む、請求項１４に記載の方法。
【請求項２５】
前記前処理することは、
前記経路を複数の経路区間に分割するステップであって、前記複数の経路区間の各々は、前記２次元距離場の領域にマッピングし、前記２次元距離場の１次導関数は前記領域内で連続である、ステップ、をさらに含む、請求項２４に記載の方法。
【請求項２６】
前記前処理するステップは、
前記経路を複数の経路区間に分割するステップであって、各特定の経路区間は、前記２次元距離場の領域に対応し、前記距離場は、前記領域内で前記経路区間に沿って２次的に変化する、ステップ、
を含む、請求項２４に記載の方法。
【図１】
【図２Ａ】
【図２Ｂ】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図４】
【図５】
【図６Ａ】
【図６Ｂ】
【図６Ｃ】
【図７Ａ】
【図７Ｂ】
【図７Ｃ】
【図８Ａ】
【図８Ｂ】
【図２Ａ】
【図２Ｂ】
【図３Ａ】
【図３Ｂ】
【図３Ｃ】
【図４】
【図５】
【図６Ａ】
【図６Ｂ】
【図６Ｃ】
【図７Ａ】
【図７Ｂ】
【図７Ｃ】
【図８Ａ】
【図８Ｂ】
【公開番号】特開２０１０−２７７５８５（Ｐ２０１０−２７７５８５Ａ）
【公開日】平成２２年１２月９日（２０１０．１２．９）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１０−１０６５８２（Ｐ２０１０−１０６５８２）
【出願日】平成２２年５月６日（２０１０．５．６）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
【公開日】平成２２年１２月９日（２０１０．１２．９）
【国際特許分類】
【出願番号】特願２０１０−１０６５８２（Ｐ２０１０−１０６５８２）
【出願日】平成２２年５月６日（２０１０．５．６）
【出願人】（５９７０６７５７４）ミツビシ・エレクトリック・リサーチ・ラボラトリーズ・インコーポレイテッド (484)
【住所又は居所原語表記】２０１ ＢＲＯＡＤＷＡＹ， ＣＡＭＢＲＩＤＧＥ， ＭＡＳＳＡＣＨＵＳＥＴＴＳ ０２１３９， Ｕ．Ｓ．Ａ．
【Ｆターム（参考）】
[ Back to top ]