(57)【特許請求の範囲】
【請求項１】
ＣＡＤ／ＣＡＭシステムにおいてコンピュータが生成した、実在のオブジェクトのスイープした容積モデルの計算に使用するための方法において、該システムが備えるプロセッサが、
エッジで結合した複数の三角形を含んでなる、前記オブジェクトのモデルの三次元多面体表現を生成するステップであって、前記三角形が、モデル化された前記オブジェクトの三角形分割表現を生成するもの、
モデル化された前記オブジェクトの三次元の動きを、モデル化された前記オブジェクトの三次元空間における一連の連続した位置によって表現するステップ、
モデル化された前記オブジェクトの前記一連の連続した位置の一つ一つについて、
（ｉ）前記エッジの部分集合について該部分集合中の一つ一つのエッジが対応する第１のゾーンを通る軌跡を持つことを判定するステップであって、前記軌跡において、モデル化された前記オブジェクトが現在位置から次の位置へ動く間、対応するエッジがスイープした容積モデルの境界上を動き、ここで、そのような各エッジの前記対応する第１のゾーンは、モデル化された前記オブジェクトのマテリアルの外部の領域であり、前記エッジで結合する前記三角形の面方向の拡張によって境界が定まるもの、
（ｉｉ）前記三角形の部分集合について、モデル化された前記オブジェクトが前の位置から現在位置へ、そして該現在位置から次の位置へ動く間、該部分集合中の一つ一つの三角形が対応する第２のゾーンを通る軌跡を持つことを判定し該部分集合をテーブルに追加するステップであって、ここで、一つ一つのそのような三角形の第２のゾーンは半球によって表現されるゾーンを持ち、該半球は平面で境界が定まり、該平面は前記三角形の平面であり、かつ、該半球はモデル化された前記オブジェクトの内側に広がっており、および、前記第２のゾーンは、モデル化された前記オブジェクトが前記前の位置にあったときに、モデル化された前記オブジェクトの少なくとも一部が占有していた空間を表すもの、および、
（ｉｉｉ）前記前の位置と前記次の位置の間の前記エッジの部分集合の動きのトレースを生成するステップであって、該生成したトレースが、前記テーブルに追加した前記三角形の部分集合を利用するもの、
並びに、
前記テーブルに追加した三角形から、前記スイープした容積モデルの表現を構築するステップであって、該構築するステップがさらに、前記一連の連続した位置の前記現在位置のそれぞれにおいて、前記スイープした容積モデルの境界を、一つ一つのそのような現在位置と関連する前記三角形の部分集合によって定めることを含むもの
を実行することを特徴とする方法。
【請求項２】
請求項１に記載の方法において、
モデル化された前記オブジェクトの２つの連続した位置の間の動きが、直線的な動きとしてモデル化されることを特徴とする方法。
【請求項３】
請求項１に記載の方法において、
前記連続した位置による動きの表現が、回転の表現と平行移動の表現を含むことを特徴とする方法。
【請求項４】
実在のオブジェクトのスイープした容積モデルの計算に使用するためのＣＡＤ／ＣＡＭシステムにおいて、
動作可能にメモリに結合されたプロセッサと、
ユーザ入力デバイスと、
ディスプレイと、
前記ユーザ入力デバイスを用いた、前記メモリに記憶されたプログラムを前記プロセッサにより実行させることによる起動に応答するグラフィックユーザインタフェースとを備え、
前記プログラムにより前記プロセッサを設定して、前記プロセッサを、
（ａ）前記オブジェクトのコンピュータモデルの三次元多面体表現を生成する計算であって、前記三次元多面体表現がエッジで結合した複数の三角形を含み、前記三角形が、モデル化された前記オブジェクトの三角形分割表現を生成するものを実行する手段、
（ｂ）モデル化された前記オブジェクトの三次元の動きを位置行列の集合で表現する計算を実行する手段、
（ｃ）該位置行列で代表される、モデル化された前記オブジェクトの一連の連続した位置の一つ一つについて、
（ｉ）前記エッジの部分集合について該部分集合中の一つ一つのエッジが対応する第１のゾーンを通る軌跡を持つことを判定する計算であって、前記軌跡において、モデル化された前記オブジェクトが現在位置から次の位置へ動く間、対応するエッジがスイープした容積モデルの境界上を動き、ここで、そのような各エッジの前記対応する第１のゾーンは、モデル化された前記オブジェクトのマテリアルの外部の領域であり、前記エッジで結合する前記三角形の面方向の拡張によって境界が定まるものを実行する手段、
（ｉｉ）前記三角形の部分集合について、モデル化された前記オブジェクトが前の位置から現在位置へ、そして該現在位置から次の位置へ動く間、該部分集合中の一つ一つの三角形が対応する第２のゾーンを通る軌跡を持つことを判定し該部分集合をテーブルに追加する計算であって、ここで、一つ一つのそのような三角形の第２のゾーンは半球によって表現されるゾーンを持ち、該半球は、モデル化された前記オブジェクトが前記前の位置にあったときに、モデル化された前記オブジェクトの少なくとも一部が占有していた空間の内側に広がっているものを実行する手段、および、
（ｉｉｉ）前記現在の位置と前記次の位置の間の前記エッジの部分集合の動きによってトレースを生成する計算を実行する手段であって、該生成したトレースが、前記テーブルに追加した前記三角形の部分集合を利用するもの、
並びに、
（ｄ）前記スイープした容積モデルの表現を前記テーブルに追加した三角形から構築し、および、前記一連の連続した位置の前記現在位置のそれぞれにおいて、一つ一つのそのような現在位置と関連する前記三角形の部分集合によって境界を定める計算を実行する手段
として機能させることを特徴とするＣＡＤ／ＣＡＭシステム。
【請求項５】
請求項４に記載のＣＡＤ／ＣＡＭシステムにおいて、
動きを表現する前記位置行列は、物理的実験時に収集される実在のオブジェクトに関連する動きデータを含むことを特徴とするＣＡＤ／ＣＡＭシステム。
【請求項６】
ＣＡＤ／ＣＡＭシステムのためのコンピュータプログラムを記憶したコンピュータ可読媒体において、
該コンピュータプログラムにより、該システムが備えるプロセッサに、
（ａ）実在のオブジェクトのコンピュータモデルの三次元多面体表現を生成する機能であって、前記三次元多面体表現がエッジで結合した複数の三角形を含み、前記三角形が、モデル化された前記オブジェクトの三角形分割表現を生成するもの、
（ｂ）モデル化された前記オブジェクトの三次元の動きを位置行列の集合で表現する機能、
（ｃ）該位置行列で代表される、モデル化された前記オブジェクトの一連の連続した位置の一つ一つについて、
（ｉ）前記エッジの部分集合について該部分集合中の一つ一つのエッジが対応する第１のゾーンを通る軌跡を持つことを判定する機能であって、前記軌跡において、モデル化された前記オブジェクトが現在位置から次の位置へ動く間、対応するエッジがスイープした容積モデルの境界上を動き、ここで、そのような各エッジの前記対応する第１のゾーンは、モデル化された前記オブジェクトのマテリアルの外部の領域であり、前記エッジで結合する前記三角形の面方向の拡張によって境界が定まるもの、
（ｉｉ）前記三角形の部分集合について、モデル化された前記オブジェクトが前の位置から現在位置へ、そして該現在位置から次の位置へ動く間、該部分集合中の一つ一つの三角形が対応する第２のゾーンを通る軌跡を持つことを判定し該部分集合をテーブルに追加する機能であって、ここで、一つ一つのそのような三角形の第２のゾーンは半球によって表現されるゾーンを持ち、該半球は、モデル化された前記オブジェクトが前記前の位置にあったときに、モデル化された前記オブジェクトの少なくとも一部が占有していた空間の内側に広がっているもの、および、
（ｉｉｉ）前記現在の位置と前記次の位置の間の前記エッジの部分集合の動きのトレースを生成する機能であって、該生成したトレースが、前記テーブルに追加した前記三角形の部分集合を利用するもの、
並びに、
（ｄ）前記スイープした容積モデルの表現を前記テーブルに追加した三角形から構築し、および、前記一連の連続した位置の前記現在位置のそれぞれにおいて、一つ一つのそのような現在位置と関連する前記三角形の部分集合によって境界を定める機能
を実行させることを特徴とするコンピュータ可読媒体。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、コンピュータのソフトウェアユーティリティプログラムに関するものであり、さらに詳細には、コンピュータ援用設計およびコンピュータ援用製造（ＣＡＤ／ＣＡＭ）ソフトウェアシステムにおいてスウェプト容積モデルを作成するための機械と方法に関するものである。
【０００２】
【従来の技術】
ＣＡＤ／ＣＡＭアプリケーションを使用しているときに、可動パーツ（moving part）が移動している間に占有する空間的包含領域または全領域をモデル化するとがしばしば望ましい。可動パーツの空間的包含のことを、スウェプト容積（swept volume）と呼ぶことがある。パーツに適切な間隔を持たせて設計するためには、スウェプト容積のエンベロープまたは境界を決定するようにするとよい。間隔は、例えば、動いているパーツが思いがけず周囲のオブジェクトに接触するのを避けるために必要である。さらに、スウェプト容積を正確にモデル化することで、空間コストの点で効率化することもできる。機能をできるだけコンパクトに設計すると有効な場合も多い。
【０００３】
現在市販されているシステムのいくつかは、動いているパーツを可動オブジェクトのマルチインスタンス化（multi-instantiation）を使用してモデル化することができる。この手法では、パーツが動いている間の瞬間瞬間のパーツのモデルを作成する。作成される瞬間モデルが増えるほど、あるモデルから次のモデルへの遷移が滑らかになる。この手法を使って品質を許容できるものにする場合、プロセッサ集約的になる傾向があり、パーツについての複数のイメージを作成する必要がある。
【０００４】
他の手法では、可動オブジェクトのマルチインスタンス化をブール演算と組み合わせて使用している。この手法を用いると、一方の瞬間モデルから他方の瞬間モデルへ外挿することで、ストレートのマルチインスタンス化モデルを改良することができる。外挿法により、得られるモデルの面表現（surface representation）を滑らかにできる。しかし、このモデル化手法でも、まだ複数の瞬間モデルを作成しなければならず、また大きな処理能力を必要とする。
【０００５】
他のアプローチとして、スウェプト容積のボクセル表現を使用したり、マーチングキューブアルゴリズム（marching cubes algorithm）を使用するものがある。
【０００６】
【発明が解決しようとする課題】
そこで、本発明では、コンピュータでシミュレートしたオブジェクトに対するスウェプト容積をモデル化する方法と装置を実現する。
【０００７】
一般に、一態様において、本発明は、コンピュータでモデル化したオブジェクトの多面体表現を生成し、オブジェクトの動きを位置行列の集合を用いて表現するステップを含む。本発明では、行列毎に自由近傍エンティティ（free neighborhood entities）の部分集合を決定し、自由近傍エンティティの動きのトレースを生成できる。トレースからのスウェプト容積の表現も構築できる。例えば、自由近傍エンティティはエッジや三角形を含むことができる。
【０００８】
一実施形態では、自由近傍は、多角形の境界を構成する様々な種類のエンティティの角部分によって表現することができる。他の態様としては、オブジェクトのマテリアル（material）を含んだ半球により表現され、かつ三角形の面により境界が定まるマテリアルゾーン（material zone）、すなわち、球体の２つの部分で表現されるタンジェントゾーン（tangent zone）を含んでおり、球体のその２つの部分が隣接三角形の面によって境界が定まる自由近傍を含んでいる。
【０００９】
一般に、他の態様として、エッジの平行移動を表す２つの三角形による多面体表現がある。多面体表現は、さらに、エッジの平行移動と回転運動を表す４つの三角形を含む場合がある。
【００１０】
他の態様では、オブジェクトを含み、オブジェクトのマテリアルパス（material path）内部で動くエンティティをフィルタに通して、処理が効率化される。
【００１１】
【課題を解決するための手段】
本発明は、さらに、コンピュータシステム、プログラムされたコンピュータ、コンピュータ読み取り可能な媒体に格納されたコンピュータプログラム、またはコンピュータと相互作用し、上記概念を具現化する方法も実現することができる。
【００１２】
本発明の１つまたは複数の実施形態を添付図面に示し、以下の段で詳述する。実装により、移動している可動パーツが占有する空間的包含領域または全領域のコンピュータモデルを効率よく作成する機能などの利点を実現できる。本発明の他の特長、目的、および利点は、説明、図面、および特許請求の範囲から明白である。
【００１３】
【発明の実施の形態】
図１を参照すると、コンピュータシステム１００の物理リソースを図示している。コンピュータ１００は、データ、アドレス、およびコントロール信号を提供するプロセッサホストバス１０２と接続されたセントラルプロセッサ１０１を有している。プロセッサ１０１は、Ｐｅｎｔｉｕｍ（登録商標）シリーズプロセッサ、Ｋ６プロセッサ、ＭＩＰＳ（登録商標）プロセッサ、ＰｏｗｅｒＰＣ（登録商標）プロセッサ、またはＡＬＰＨＡ（登録商標）プロセッサなどの、従来の通常の目的のシングルチップまたはマルチチップマイクロプロセッサのいずれかとすることができる。さらに、プロセッサ１０１は、ディジタルシグナルプロセッサまたはグラフィックプロセッサなどの、従来の特別な目的のマイクロプロセッサのいずれかとすることもできる。マイクロプロセッサ１０１は、プロセッサホストバス１０２と結合した従来のアドレス、データ、およびコントロールラインを有することができる。
【００１４】
コンピュータ１００は、統合型ＲＡＭメモリコントローラ１０４を有するシステムコントローラ１０３を含むことができる。システムコントローラ１０３は、ホストバス１０２と接続し、ランダムアクセスメモリ１０５へのインターフェイスを提供することができる。システムコントローラ１０３は、周辺バスのブリッジ機能に対するホストバスも提供することができる。したがって、コントローラ１０３は、プロセッサホストバス１０２上の信号を主周辺バス１１０上の信号と互換に交換することを可能にする。例えば、周辺バス１１０は、Ｐｅｒｉｐｈｅｒａｌ  Ｃｏｍｐｏｎｅｎｔ  Ｉｎｔｅｒｃｏｎｎｅｃｔ（ＰＣＩ）バス、Ｉｎｄｕｓｔｒｙ  Ｓｔａｎｄａｒｄ  Ａｒｃｈｉｔｅｃｔｕｒｅ（ＩＳＡ）バス、またはＭｉｃｒｏ−Ｃｈａｎｎｅｌバスとすることができる。さらに、コントローラ１０３は、ホストバス１０２と周辺バス１１０間のデータバッファリングおよびデータ転送レートマッチングを提供することができる。したがって、コントローラ１０３は、例えば６４ビット６６ＭＨｚインターフェースと５３３Ｍｂｙｔｅ／ｓｅｃｏｎｄデータ転送レートを持ったプロセッサ１０１がデータパスビット幅、クロック速度、またはデータ転送レートが異なるデータパスを有するＰＣＩバス１１０にインターフェイスすることを可能にする。
【００１５】
例えば、ハードディスクドライブ１１４と結合したハードディスクコントロールインターフェイス１１１、ビデオディスプレイ１１５と結合したビデオディスプレイコントローラ１１２、キーボード、およびマウスコントローラ１１３などの付属デバイスは周辺バス１１０と結合され、プロセッサ１０１によって制御されることができる。コンピュータシステムは、インターネットおよびイントラネットなどのコンピュータシステムネットワークへの接続も含むことができる。データおよび情報はそのような接続を通して送受信することができる。
【００１６】
コンピュータ１００は、基本的なコンピュータソフトウェアルーチンを格納する不揮発性ＲＯＭメモリ１０７も含むことができる。ＲＯＭ１０７は、コンフィグレーションデータを格納するＥＥＰＲＯＭ（Electronically Erasable Programmable Read Only Memory）などの可変メモリを含むことができる。ＢＩＯＳルーチン１２３はＲＯＭ１０７に含められ、コンピュータの基本的な初期設定、システムの検査、入出力（Ｉ／Ｏ）サービスを提供することができる。ＢＩＯＳ１２３は、オペレーティングシステムをディスク１１３から「ブート」することができるルーチンも含むことができる。高水準オペレーティングシステムの例として、Ｍｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ９８（商標）、ＷｉｎｄｏｗｓＮＴ（商標）、ＵＮＩＸ、ＬＩＮＵＸ、Ａｐｐｌｅ  ＭａｃＯＳ（商標）オペレーティングシステム、または他のオペレーティングシステムがある。
【００１７】
オペレーティングシステムは、完全にＲＡＭメモリ１０５にロードされるか、あるいは、ＲＡＭメモリ１０５、ディスクドライブ記憶装置１１４、またはネットワークに配置した記憶装置内に一部が含まれるようにすることもできる。オペレーティングシステムは、ソフトウェアアプリケーション、ソフトウェアシステム、およびソフトウェアシステムのツールを実行するための機能性を提供することができる。ソフトウェアの機能性によってビデオディスプレイコントローラ１１２およびコンピュータシステム１００の他のリソースにアクセスし、ビデオコンピュータディスプレイ１１５上に２次元（２−Ｄ）および３次元（３−Ｄ）モデルを提供することができる。
【００１８】
そこで図２を参照すると、例えば、ＣＡＤ／ＣＡＭシステム上で表示されるコンピュータ生成モデルは多面体表現を持つオブジェクトを含むことができ、その際にこのオブジェクトは三角形の集合によって表される。オブジェクトの動きは、順序付けられた位置行列の集合で表すことができる。それぞれの行列は、前の位置および／または次の位置で類似の三角形と相関のある三角形の集合を含むことができる。オブジェクトの動きの一モデルでは、動きは２つの連続する行列位置間で直線的であると仮定することができる。動いてるエッジの多面体表現は、２つまたは４つの三角形で表すことができる。平行移動のみを受けるエッジ１  ２０１〜２０２は２つの三角形で表すことができる。平行移動と回転運動を受けるエッジ２  ２０３〜２０４は４つの三角形で表すことができる。例えば、エッジ１  ２０１は時刻ｔにおいて平行移動のみが行え、時刻ｔ＋Δｔ２０２におけるエッジとなる。エッジ１のこの平行移動は、２つの三角形２１１と２１２で表すことができる。移動方向は、１つの矢印２１４で表すことができる。
【００１９】
さらに動きは、平行移動と回転の組み合わせを含むこともできる。時刻ｔにおけるエッジ２  ２０３は、時刻ｔ＋Δｔ２０４におけるエッジ２となるまで平行移動と回転運動を受けることができる。平行移動および回転運動によるエッジ２の多面体表現は、４つの三角形２２１〜２２４を含むことができる。動きの方向は、２つの矢印２３０と２３１で表すことができる。
【００２０】
動きは、ユーザメニュー、すなわちアイコンなどのその他対話的デバイスやコマンドライン入力から選択することによって、モデル上でシミュレートすることができる。ユーザは、回転、直線移動、または円弧移動などの動きの種類を指定し、そして動きを与えるモデルオブジェクトを選択することができる。他のオプションは、オブジェクトを選択して、そのオブジェクトに与える動きを選択することを含む。選択は、ポインティングデバイス、キーボード、スタイラスペン、タッチスクリーン、またはその他のユーザ入力デバイスを用いて行うことができる。
【００２１】
他の実施形態では、動きデータをデータベースに格納し、後で、データに関係する動きをシミュレートするために参照することができる。データベースに収められたデータは、実験または他の現実世界の収集方法からコンパイルすることができる。例えば、自動車のホイールに取り付けられているセンサによって、自動車が運転中の回転速度と垂直移動をモニタすることができる。センサから収集されたデータはデータベースに格納できる。コンピュータで定義されたモデルを使ってデータベースを参照し、ホイールの動きをエミュレートすることかできる。このようにして、自然界のモニタできるほとんどの動きはコンピュータモデルによってエミュレートできる。さらに、キーボードなどの入力デバイスにより手動でデータを入力したり、あるいは別の方法でコンパイルすることができる。コンピュータ定義モデルを使用することで、データによって表現される動きをエミュレートすることができる。
【００２２】
スウェプト容積を表現するために本発明は、容積の境界、つまり容積を閉じている面（２Ｄエンティティ）の集合を定めることができる。この境界またはエンベロープはコンピュータ定義モデルで計算することができる。時刻ｔにおいて、動いているオブジェクトの境界に属する点は、スウェプト容積に関する近傍が充満してない場合は、つまりその点がオブジェクトのマテリアルの内側にない場合はスウェプト容積の境界に属する。スウェプト容積に関する点の近傍は、動いているオブジェクトに関する点の近傍の動きによって発生されるスウェプト容積と等しくなるようにできる。点ｐについて、自由近傍は、点ｐの動きから発生される近傍が充満していないように、ｐの近傍に属する点の集合とすることができる。点ｐの近傍は、ｐが動いている間にスウェプト容積の境界上にとどまり、マテリアルの内側境界に入り込まないのであれば、充満していない。自由近傍内で動いている点は、モデル化されたオブジェクトのマテリアルの面に沿って滑っている点と等価である。
【００２３】
スウェプト容積の境界は、一般に、動いているオブジェクトの境界に属し、スウェプト容積の境界に沿って滑る点の部分集合をそれぞれの時刻ｔについて決定することによりモデル化することができる。この決定は、点の自由近傍の研究に基づく。点の動きによりトレースを計算し、生成することができる。スウェプト容積は、複数のトレースの表現から構築することができる。
【００２４】
ここで図３を参照すると、オブジェクトの多面体表現においてエッジを表す三角形３１０は、動いている「肘（elbow）」によってトレースできる。トレース３００は、三角形３２０〜３２５の複数の例示を含むことができる。移動方向は、方向矢印３１１と３１２で示すことができる。点は、２Ｄ表現におけるエッジに属するか、または３Ｄ表現における三角形に属する。点は、類似の近傍とさらに類似の自由近傍を持つことができる。したがって、動いているオブジェクトの境界のエッジまたは三角形エンティティに含まれる１つの点がその自由近傍内で動いているならば、エンティティ全体がその自由近傍内で動いている。
【００２５】
２種類の自由近傍を、スウェプト容積の計算に利用することができる。三角形の自由近傍は、マテリアルを含んでおり、三角形の面によって境界が定まる半球を用いて表現することができる。この種の自由近傍のことを、マテリアルゾーンと呼ぶことができる。
【００２６】
エッジの自由近傍は、隣接する三角形の面により境界が定まる、球体の２つの部分によって表現することができる。この種の近傍のことを、タンジェントゾーンと呼ぶことができる。
【００２７】
ここで図４を参照すると、多角形４１０は平行移動することができる。例えば、平行移動の軌道４２０は、多角形の例示４１０〜４１３内の中心点などの点から追跡することができる。
【００２８】
ここで図５を参照すると、自由近傍は、多角形の境界に属する様々な種類のエンティティの角部分で表現することができる。例えば、自由近傍は、隣接するエッジに関して点５２０のタンジェントベクトル５３１および５３２に基づくことができる。エッジ５１１の場合、自由近傍またはマテリアルゾーンは、法線ベクトル５１２に基づく。
【００２９】
２Ｄエッジの自由近傍に含まれる三角形は、オブジェクトのマテリアルを含んでおり、三角形の面によって制限される半球５１０で表現することができる。半球５１０をマテリアルゾーンと呼ぶことができる。エッジの場合、点５２０により２Ｄ内で表現されるが、自由近傍は、球体５２１および５２２の２つの部分で表現できる。これら球体は、隣接する三角形５３１および５３２の面によって境界が定まる。エッジ５２１および５２２の自由近傍をタンジェントゾーンと呼ぶことができる。
【００３０】
ここで図６を参照すると、動きベクトル６１１〜６１３は、多角形オブジェクトに含まれる異なるエンティティの平行移動を示すことができる。動きベクトル６１１〜６１３は、多角形オブジェクト４０５の軌道４２０に関連付けることができる。エンティティは例えば、エッジ６３０または三角形６２０を含むことができる。
【００３１】
ここで図７を参照すると、スウェプト容積の境界にとどまっているエンティティは、追跡でき、スウェプト容積を形成する多面体の計算に含めることができる。多角形オブジェクトのマテリアルの経路内に入るエンティティが取り除かれることで、プロセッサの能力を節約することができる。例えば、動きベクトル７２１に従うエッジ７２０は、タンジェントゾーン５２１内を移動することができる。したがって、エッジ７２０を追跡でき、スウェプト容積モデル内で使用することができる。同様に、ベクトル７３１に沿って平行移動する三角形７３０はマテリアルゾーン５１０内を移動することができる。したがって、エッジ７３０を追跡してスウェプト容積モデルを決定することができる。
【００３２】
多角形のマテリアルパス内を移動する部分にフィルタを適用できる。フィルタリングによって、コンピュータのプロセッサ１０１によって実行する計算量を減らすことができる。例えば、ベクトル７１１に沿って平行移動するエッジ７１０は多角形４０５のマテリアルパス内を移動できる。したがって、エッジ７１０をスウェプト容積の計算から除去することができる。
【００３３】
ここで図８を参照すると、多角形オブジェクト４０５の平行移動を追跡するトレース８１０〜８１６の集合は、図９に表示されているスウェプト容積境界９１０を形成することができる。
【００３４】
ここで図１０を参照すると、一実施形態において、ステップ１０１０〜１０２７を含む論理の流れは、多面体オブジェクトの動きによって生じるスウェプト容積を決定するために使用されるプロセスを表すことができる。スウェプト容積プログラム実行を開始する「スウェプト容積開始」コマンド（１０１０）は、ユーザによって発行でき、またコンピュータ１００で実行される他のプログラムから呼び出すことができる。移動体は、コンピュータで生成されたモデル表示から選択することができる（１０１１）。選択を行うには、マウスまたは他のポインティングデバイスを使用するか、またはキーボードなどの入力デバイスを使用する。プログラムによって、三角形とエッジからなる配列を抽出することができる（１０１２）。抽出では、記憶されている三角形情報を参照し、その情報を変更することなく図内に挿入することができる。
【００３５】
動きは、位置行列の選択によって選択することができる（１０１３）。その後、ループをそれぞれの位置行列について設定することができる（１０１４）。このループによってプログラムを呼び出し、三角形とエッジの配列を変換することができる（１０１５）。それぞれのエッジについてサブループを設定することができる（１０１６）。エッジのサブループ内で、テストによって、タンジェントゾーン内で現在のエッジが動いているかどうかを判別することができる（１０１７）。タンジェントゾーン内で現在のエッジが動いているならば、プログラムはエッジによって生成されるトレースを計算することができる（１０１８）。エッジによって生成されたトレースを計算する（１０１８）際に、プログラムは２つの三角形を利用し、多角形の平行移動および回転を含む動きについて多角形と４つの三角形の平行移動を表現することができる。
【００３６】
三角形の変換には、コネクティングロッドなどのパーツを構成する三角形の位置を修正を含むことができる。位置の設定順序は、種々の例示においてパーツを表現する選択動き位置行列から定義することができる。コネクティングロッドの例では、配列のエッジ上の三角形の位置は、コネクティングロッドがｔ０における元の位置にある間はＸ０、Ｙ０、およびＺ０とすることができる。垂直の平行移動のみであれば、コネクティングロッドの一番上の位置は、Ｘ０、Ｙ０、およびＺ１であり、ここでＺは垂直軸である。平行移動により、各エッジにおける各三角形の各点の位置を修正することができる。
【００３７】
エッジによって生じるトレースの計算（１０１８）に続いて、プログラムによって三角形をテーブルに追加することができる（１０１９）。テーブルに格納された三角形を後で参照し、スウェプト容積の多面体表現をモデル化することができる。最後のエッジを計算するまで、各エッジについてループが続行される（１０２０）。
【００３８】
各三角形に対するループ（１０２１）も処理できる。ループの論理的順序は重要でない。三角形のループがエッジのループの前に来るか、またはエッジのループが三角形のループの前に来る。各三角形のループにより、マテリアルゾーン内の三角形の動きをテストすることができる（１０２２）。マテリアルゾーンを移動する三角形を、多面体を計算するために用いられるテーブルに追加することができる（１０２３）。最後の三角形を計算するまで、各三角形についてループが続行される（１０２４）。
【００３９】
行列ループは三角形とエッジの配列の変形を続け、最後の行列に達するまで各行列についてエッジと三角形のサブループが実行される（１０２５）。すべての行列が処理されたら、三角形が格納されているテーブルに記述されている情報からプログラムによって多面体を計算することができる（１０２６）。最後に、スウェプト容積コマンドプログラムは終わりに達する（１０２７）。
【００４０】
図１１を参照すると、円柱の平行移動によって生成されるスウェプト容積モデル１１１０が表されている。円柱の平行移動および回転運動によって生成されるスウェプト容積モデルは、図１２中の１２１０に示されている。図１１と図１２は、他のものが絡んでいない平行移動と回転の動きパターンが生じる単純な円柱状のオブジェクトを表している。
【００４１】
図１３を参照すると、少し複雑なモデルの図が示されている。ピストン１３１０はコネクティングロッド１３２０に接続され、クランクシャフト１３３０がモデル化されている。クランクシャフト１３３０の回転により、コネクティングロッド１３２０に平行移動および回転運動を発生させ、ピストン１３１０に平行移動を発生させることができる。図１４は、平行移動を受けるピストン１３１０のスウェプト容積モデル１４１０を表す。スウェプト容積モデル１４１０は、コネクティングロッド１３２０の平行移動および回転運動についても示されている。クランクシャフト１３３０の動きはモデル化されていない。ユーザは、モデルに含まれている特定のオブジェクトを選択し、選択されたオブジェクトのみについてスウェプト容積モデルを構築することができる。この選択プロセスによって、図に表されているオブジェクトのコンテキストにおいてスウェプト容積モデルを明確にすることができる。
【００４２】
本発明は、デジタル電子回路、またはコンピュータのハードウェア、ファームウェア、ソフトウェアで、またはそれらを組み合わせて実装することができる。本発明の装置は、プログラム可能なプロセッサによって実行される機械読み取り可能な記憶装置で明確に具現化されたコンピュータプログラム製品で実装することができ、また本発明の方法ステップは、入力データの演算および出力の生成によって本発明の機能を実行するための命令からなるプログラムを実行するプログラム可能なプロセッサによって実行することができる。
【００４３】
本発明は、データおよび命令の送受信を行うために結合された少なくとも１つのプログラム可能なプロセッサと、データストレージシステムと、少なくとも１つの入力デバイスと、少なくとも１つの出力デバイスとを含んだ、プログラム可能なシステム上で実行できる１つ以上のコンピュータプログラムで都合よく実装することができる。それぞれのコンピュータプログラムは、高レベルの手続型またはオブジェクト指向プログラミング言語、あるいは、必要ならばアセンブリ言語または機械語で実装することができ、如何なる場合も、言語をコンパイル型またはインタプリタ型の言語とすることができる。
【００４４】
一般に、プロセッサは読み取り専用メモリおよび／またはランダムアクセスメモリから命令およびデータを受け取る。コンピュータプログラムの命令およびデータを明確に具現化するのに適したストレージ装置はあらゆる形態の不揮発性メモリを含み、例えば、ＥＰＲＯＭやＥＥＰＲＯＭやフラッシュメモリデバイスなどの半導体メモリデバイス、内蔵ハードディスクや着脱式ディスクなどの磁気ディスク、光磁気ディスク、およびＣＤ−ＲＯＭディスクを含む。前記の事項は、専用設計ＡＳＩＣ（特定用途向け集積回路）によって補うか、あるいは組み込むことができる。
【００４５】
本発明の多数の実施形態について説明してきた。本発明の精神と範囲を逸脱することなく様々な修正を加えられることは理解されるであろう。したがって、他の実装も首記の特許請求の範囲内にある。
【図面の簡単な説明】
【図１】本発明に従ったコンピュータを表す図である。
【図２】オブジェクトの単純多面体表現を表す図である。
【図３】曲げを通じてトレースされた多面体表現におけるエッジを表す図である。
【図４】平行移動を受ける多角形を表す図である。
【図５】自由近傍タンジェント（Free Neighborhood Tangent）およびマテリアルゾーンを表す図である。
【図６】多角形の平行移動を示す動きベクトルを表す図である。
【図７】自由近傍エンティティの追跡を表す図である。
【図８】多角形の平行移動の追跡を表す図である。
【図９】図８の平行移動からのスウェプト容積境界形成を表す図である。
【図１０】スウェプト容積生成のプロセスの一実施形態のフローチャートである。
【図１１】平行移動を受ける円柱のスウェプト容積モデルを表す図である。
【図１２】平行移動および回転運動を受ける円柱のスウェプト容積モデルを表す図である。
【図１３】静止状態にあるピストン、コネクティングロッド、およびクランクシャフトを表す図である。
【図１４】ピストンとコネクティングロッドが移動を示している状態のピストン、コネクティングロッド、およびクランクシャフトのスウェプト容積モデルを表す図である。
【符号の説明】
１００  コンピュータ
１０１  プロセッサ
２０１〜２０２  エッジ１
２０３〜２０４  エッジ２
２１１，２１２，２２１〜２２４，３１０，３２０〜３２５，５３１，５３２，６２０  三角形
２１４，２３０，２３１  矢印
３００  トレース
３１１，３１２  方向矢印
４０１〜４１３  多角形
４２０  軌道
５１０  マテリアルゾーン
５１１，６３０，７１０，７２０，７３０  エッジ
５１２  法線ベクトル
５２０  点
５２１，５２２  タンジェントゾーン
５２１，５２２  球体
５３１，５３２  タンジェントベクトル
６１１〜６１３，７２１  動きベクトル
７１１，７３１  ベクトル
８１０〜８１６  トレースの集合
９１０  スウェプト容積境界
１３１０  ピストン
１３２０  コネクティングロッド
１３３０  クランクシャフト
１４１０  スウェプト容積モデル
ｐ  点
ｔ  時刻
【図１】
0003971085.tif 000002
【図２】
0003971085.tif 000003
【図３】
0003971085.tif 000004
【図４】
0003971085.tif 000005
【図５】
0003971085.tif 000006
【図６】
0003971085.tif 000007
【図７】
0003971085.tif 000008
【図８】
0003971085.tif 000009
【図９】
0003971085.tif 000010
【図１０】
0003971085.tif 000011
【図１１】
0003971085.tif 000012
【図１２】
0003971085.tif 000013
【図１３】
0003971085.tif 000014
【図１４】
0003971085.tif 000015