デクセルによって表現されるモデル化ボリュームの設計
【課題】モデル化ボリュームを設計するコンピュータ実装方法が提供される。
【解決手段】方法は、モデル化ボリュームを表すデクセルの集合を提供すること（Ｓ１０）であって、各デクセルは、直線とモデル化ボリュームとの共通部分を表す少なくとも１つの線分の集合を含み、デクセルの集合が、隣接デクセルのグループに区分され、グループのデクセルのそれぞれに含まれる線分の最大数に応じたメモリ空間が、各グループに割り振られること、モデル化ボリュームに対する彫刻操作を提供すること（Ｓ２０）、および彫刻操作に応答してデクセルの集合を更新すること（Ｓ３０）を含む。そのような方法は、デクセルの集合によって表されるモデル化ボリュームの設計を改善する。
【解決手段】方法は、モデル化ボリュームを表すデクセルの集合を提供すること（Ｓ１０）であって、各デクセルは、直線とモデル化ボリュームとの共通部分を表す少なくとも１つの線分の集合を含み、デクセルの集合が、隣接デクセルのグループに区分され、グループのデクセルのそれぞれに含まれる線分の最大数に応じたメモリ空間が、各グループに割り振られること、モデル化ボリュームに対する彫刻操作を提供すること（Ｓ２０）、および彫刻操作に応答してデクセルの集合を更新すること（Ｓ３０）を含む。そのような方法は、デクセルの集合によって表されるモデル化ボリュームの設計を改善する。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、コンピュータプログラムおよびシステムの分野に関し、より詳細には、デクセルの集合によって表されるモデル化ボリュームを設計する方法、システム、およびプログラムに関する。
【背景技術】
【０００２】
オブジェクトの設計、エンジニアリング、および製造のための複数のシステムおよびプログラムが市場で提供されている。ＣＡＤはコンピュータ支援設計（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ Ｄｅｓｉｇｎ）の頭字語であり、例えばＣＡＤは、オブジェクトを設計するためのソフトウェア解決策に関係する。ＣＡＥはコンピュータ支援エンジニアリング（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ Ｅｎｇｉｎｅｅｒｉｎｇ）の頭字語であり、例えばＣＡＥは、将来の製品の物理的挙動をシミュレートするためのソフトウェア解決策に関係する。ＣＡＭはコンピュータ支援製造（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ Ｍａｎｕｆａｃｔｕｒｉｎｇ）の頭字語であり、例えばＣＡＭは、製造工程および運用を定義するためのソフトウェア解決策に関係する。そのようなシステムでは、グラフィカルユーザインターフェース（ＧＵＩ）が、技法の効率に関して重要な役割を果たす。こうした技法を製品ライフサイクル管理（ＰＬＭ）システム内に組み込むことができる。ＰＬＭは、拡張された企業の概念にわたって、会社が製品データを共有し、共通のプロセスを適用し、概念から製品の寿命の終わりまでの製品の開発に関する会社の知識を活用する助けとなるビジネス戦略を指す。
【０００３】
Ｄａｓｓａｕｌｔ Ｓｙｓｔｅｍｓによって（ＣＡＴＩＡ、ＥＮＯＶＩＡ、およびＤＥＬＭＩＡという商標の下で）提供されるＰＬＭ解決策は、製品エンジニアリング知識を編成するＥｎｇｉｎｅｅｒｉｎｇ Ｈｕｂ、製造エンジニアリング知識を管理するＭａｎｕｆａｃｔｕｒｉｎｇ Ｈｕｂ、およびＥｎｇｉｎｅｅｒｉｎｇ ＨｕｂとＭａｎｕｆａｃｔｕｒｉｎｇ Ｈｕｂの両方への企業統合および接続を可能にするＥｎｔｅｒｐｒｉｓｅ Ｈｕｂを提供する。全体として、システムは、最適化製品定義、製造準備、製品およびサービスを推進する動的な知識ベースの製品作成および決定サポートを可能にするためのオープンオブジェクトモデルリンキング製品、プロセス、リソースを達成する。
【０００４】
こうしたシステムの一部は、デクセルの集合を用いたモデル化ボリュームの表現を可能にする。いくつかの論文または特許文書は特に、機械加工シミュレーションまたは対話式彫刻のためにデクセル表現を使用することを示唆している（例えば、非特許文献１〜６、特許文献１および２参照）。
【０００５】
ＧＰＧＰＵ（Ｇｅｎｅｒａｌ−Ｐｕｒｐｏｓｅ Ｃｏｍｐｕｔｉｎｇ ｏｎ Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔｓ）は、コンピュータグラフィックスのみに関する計算を一般に処理するグラフィック処理装置（ＧＰＵ）を使用して、従来は中央演算処理装置（ＣＰＵ）によって処理されたアプリケーション内の計算を実行する技法である。いくつかの論文は、現代のグラフィックス処理装置（ＧＰＵ）の処理能力（ｃｏｍｐｕｔａｔｉｏｎ ｐｏｗｅｒ）をデクセル表現のために使用することを考慮している。こうした論文はＬＤＮＩ（Ｌａｙｅｒｅｄ Ｄｅｐｔｈ−Ｎｏｒｍａｌ Ｉｍａｇｅｓ）アルゴリズムを利用し、ＬＤＮＩアルゴリズムは特定のメモリモデルに関連付けられる（例えば、非特許文献７および８参照）。
【０００６】
しかし、先行技術文献に列挙した解決策は、特にメモリ性能の観点およびユーザ利用の観点から、効率が欠けている。この状況の中で、デクセルの集合によって表されるモデル化ボリュームを設計するための改良型の解決策が依然として求められている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国特許第５７１０７０９号明細書
【特許文献２】米国特許第７７４７４１８号明細書
【非特許文献】
【０００８】
【非特許文献１】"A Virtual Sculpting System Based on Triple Dexcl Models with Haptics", Xiaobo Peng and Weihan Zhang, Computer-Aided Design and Applications, 2009
【非特許文献２】"NC Milling Error Assessment and Tool Path Correction", Yunching Huang and James H. Oliver, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, 1994
【非特許文献３】"Online Sculpting and Visualization of Multi-Dexel Volumes", Heinrich Muller, Tobias Surmann, Marc Stautner, Frank Albersmann, Klaus Weinert, SM '03 Proceedings of the eighth ACM symposium on Solid modeling and applications
【非特許文献４】"Virtual prototyping and manufacturing planning by using tri-dexel models and haptic force feedback", Yongfu Ren, Susana K. Lai-Yuen, and Yuan-Shin Lee, Virtual and Physical Prototyping, 2006
【非特許文献５】"Simulation of NC machining based on the dexel model: A critical analysis", Sabine Stifter, The International Journal of Advanced Manufacturing Technology, 1995
【非特許文献６】"Real time simulation and visualization of NC milling processes for inhomogeneous materials on low-end graphics hardware", Konig, A. H. and Grolier, E., Computer Graphics International, 1998. Proceedings
【非特許文献７】"GPGPU-based Material Removal Simulation and Cutting Force Estimation", B. Tukora and T. Szalay, CCP: 94: Proceedings Of The Seventh International Conference On Engineering Computational Technology
【非特許文献８】"Layered Dept-Normal Images: a Sparse Implicit Representation of Solid Models", Charlie C. L., Wang and Yong Chen, Proceedings of ASME international design engineering technical conferences. Brooklyn (NY)
【発明の概要】
【課題を解決するための手段】
【０００９】
したがって、一態様によれば、モデル化ボリュームを設計するコンピュータ実装方法が提供される。方法は、モデル化ボリュームを表すデクセルの集合を提供することを含む。各デクセルは、直線とモデル化ボリュームとの共通部分を表す少なくとも１つの線分の集合を含む。デクセルの集合は、隣接デクセルのグループに区分される。グループのデクセルのそれぞれに含まれる線分の最大数に応じたメモリ空間が、各グループに割り振られる。方法はまた、モデル化ボリュームに対する彫刻操作を提供すること、および彫刻操作に応答してデクセルの集合を更新することをも含む。
【００１０】
方法は、以下のうちの１つまたは複数を含むことができる。
−デクセルの集合を更新することが、彫刻操作によって影響を受ける隣接デクセルのグループを求めること、および求めたグループのそれぞれを更新することを含み、
−求めたグループのそれぞれを更新することが、それぞれのグループについて、並列処理によってそれぞれのグループのデクセルを更新することを含み、
−それぞれのグループのデクセルを更新することが、それぞれのグループのそれぞれのデクセルについて、それぞれのデクセルに対する彫刻操作の影響を評価すること、およびそれに応じてそれぞれのデクセルを修正することを含み、
−それぞれのデクセルに対する彫刻操作の影響を評価することが、それぞれのデクセルの線分に対する彫刻操作の影響を評価することを含み、
−それぞれのグループのデクセルを更新することが、ＳＩＭＤ（単一命令多重データ）並列処理によって実施され、
−方法は、更新後グループのデクセルのそれぞれに含まれる線分の最大数が修正されるとき、更新後グループに割り振られたメモリ空間を適合させることをさらに含み、
−デクセルの集合が、方法の実行で示唆されるハードウェアおよび／または彫刻コンテキストへの適合の際に、隣接デクセルのグループに区分される。
【００１１】
モデル化ボリュームを設計するシステムがさらに提案され、システムは、上記の方法を実行する命令がその上に記録されたメモリと、命令を実行するメモリに結合された少なくとも１つのプロセッサとを備える。
【００１２】
プロセッサは超並列処理ユニットでよい。システムは、命令の実行を開始するのに適した少なくとも１つのＧＵＩを含むことができる。ＧＵＩはＧＰＵを含むことができ、プロセッサはＧＰＵでよい。
【００１３】
上記の方法を実行する命令を含むコンピュータプログラムがさらに提案される。
【００１４】
上記のコンピュータプログラムがその上に記録されたコンピュータ可読記憶媒体がさらに提案される。
【００１５】
次に、非限定的な例として、添付の図面を参照しながら本発明の実施形態を説明する。
【図面の簡単な説明】
【００１６】
【図１】方法の一例の流れ図を示す図である。
【図２】グラフィカルユーザインターフェースの一例を示す図である。
【図３】クライアントコンピュータシステムの一例を示す図である。
【図４】方法の例を示す図である。
【図５】方法の例を示す図である。
【図６】方法の例を示す図である。
【図７】方法の例を示す図である。
【図８】方法の例を示す図である。
【図９】従来技術を示す図である。
【図１０】従来技術を示す図である。
【図１１】従来技術を示す図である。
【図１２】従来技術を示す図である。
【図１３】従来技術を示す図である。
【図１４】方法の例を示す図である。
【発明を実施するための形態】
【００１７】
図１に、モデル化ボリュームを設計するコンピュータ実装方法（以後、「方法」と呼ぶ）の一例の流れ図を示す。方法は、デクセルの集合を提供することを含む（Ｓ１０）。デクセルの集合はモデル化ボリュームを表す。（デクセルの集合の）各デクセルは、少なくとも１つの線分の集合を含む。そのような線分は、直線とモデル化ボリュームとの間の共通部分を表す。デクセルの集合は、隣接デクセルのグループに区分される。グループのデクセルのそれぞれに含まれる線分の最大数に応じたメモリ空間が、各グループに割り振られる。方法はまた、モデル化ボリュームに対する彫刻操作を提供することをも含む（Ｓ２０）。方法は、彫刻操作に応答してデクセルの集合を更新することをさらに含む（Ｓ３０）。そのような方法は、デクセルの集合によって表されるモデル化ボリュームの設計を改善する。
【００１８】
デクセルの集合によって表されるモデル化ボリュームも提供され、（デクセルの集合の）各デクセルは、少なくとも１つの線分の集合を含む。そのような線分は、直線とモデル化ボリュームとの間の共通部分を表す。デクセルの集合は、隣接デクセルのグループに区分される。グループのデクセルのそれぞれに含まれる線分の最大数に応じたメモリ空間が、各グループに割り振られる。以下で説明する方法の特徴および例は、そのようなモデル化ボリュームにも当てはまる。
【００１９】
デクセルの集合によってモデル化ボリュームを表現する符号化方式も提供される。符号化方式は、ボリュームの定義を提供することを含む。次いで符号化方式は、直線の集合を定義し、直線の集合とボリュームとの共通部分を計算し、対応するデクセルを求める。符号化方式はさらに、デクセルの集合を隣接デクセルのグループに区分し、グループのデクセルのそれぞれに含まれる線分の最大数に応じたメモリ空間を各グループに割り振る。デクセルの集合を提供するステップ（Ｓ１０）は、符号化方式を実装することができる。以下で説明する方法の特徴および例は、そのような符号化方式にも当てはまる。
【００２０】
ＣＡＤモデル化オブジェクトを設計するプロセスに方法を含めることができる。「ＣＡＤモデル化オブジェクトを設計する」ことは、モデル化オブジェクトを精巧に作るプロセスの少なくとも一部である任意の処置または一連の処置を指す。したがって、方法は、ＣＡＤモデル化オブジェクトを最初から作成することを含むことができる。あるいは、方法は、以前に作成したＣＡＤモデル化オブジェクトを提供し、次いでＣＡＤモデル化オブジェクトを修正することを含むことができる。いずれにしても、方法によって設計されるモデル化ボリュームは、ＣＡＤモデル化オブジェクトまたはその少なくとも一部、例えばＣＡＤモデル化オブジェクトによって占有される３Ｄ空間を表すことができる。方法は、デクセルの集合によって表されるモデル化ボリュームの設計を改善するので、方法は、ＣＡＤモデル化オブジェクトの設計をも改善する。
【００２１】
モデル化オブジェクトは、コンピュータシステムのメモリに格納されたデータによって定義される任意のオブジェクトである。拡張すれば、「モデル化オブジェクト」という表現はデータ自体を指す。ＣＡＤモデル化オブジェクトは、ＣＡＤシステムのメモリに格納されたデータによって定義される任意のオブジェクトである。システムのタイプに従って、異なる種類のデータによってモデル化オブジェクトを定義することができる。ＣＡＤシステムは、ＣＡＴＩＡなどの、モデル化オブジェクトのグラフィカル表現に基づいてモデル化オブジェクトを設計するのに少なくとも適した任意のシステムである。したがって、ＣＡＤモデル化オブジェクトを定義するデータは、モデル化オブジェクトの表現を可能にするデータを含む（例えば空間内の相対位置を含む、例えば幾何学データ）。
【００２２】
方法を製造工程に含めることができ、製造工程は、方法を実施した後、モデル化ボリュームに対応する物理的製品を生産することを含むことができる。いずれにしても、方法によって設計されるモデル化ボリュームは、製造オブジェクトを表すことができる。したがって、モデル化ボリュームはモデル化立体でよい（すなわち、立体を表すモデル化オブジェクト）。製造オブジェクトは、部品、部品のアセンブリなどの製品でよい。方法はモデル化ボリュームの設計を改善するので、方法は製品の製造をも改善し、したがって製造工程の生産性を向上させる。方法は、ＤＥＬＭＩＡなどのＣＡＭシステムを使用して実装することができる。ＣＡＭシステムは、製造工程および運用を定義し、シミュレートし、制御するのに少なくとも適した任意のシステムである。
【００２３】
方法はコンピュータ実装される。このことは、少なくとも１つのコンピュータまたは同様の任意のシステム上で方法が実行されることを意味する。別段の言及がない限り、方法のすべてのステップは、コンピュータによって、すなわちユーザの介入なしに実施される。例えば、更新するステップ（Ｓ３０）はコンピュータのみによって実施することができ、デクセルの集合を提供するステップ（Ｓ１０）および彫刻操作を提供するステップ（Ｓ２０）は、コンピュータのみによって、またはユーザ対話を通じて実施することができる。実際、デクセルの集合を提供するステップ（Ｓ１０）は、ユーザによって開始することができる。それによって、方法は、恐らくはユーザによって実現される彫刻操作に応じた、モデル化ボリュームを表すデクセルの集合の自動更新（Ｓ３０）を可能にする。方法のステップがユーザの介入を可能にすることができることに言及することにも価値がある。例えば、ユーザは、例えば、コンピュータによって実行されるアルゴリズムの結果を修正するために、例えば更新された（Ｓ３０）デクセルの集合を修正するために介入することができる。このことは、更新されたときにデクセルの集合を修正するステップと同等であり、修正するステップは、更新するステップ（Ｓ３０）の後に実行される。
【００２４】
方法のコンピュータ実装の典型的な例は、この目的に適したシステムで方法を実施することである。システムは、方法を実施する命令をその上に記録したメモリを備えることができる。言い換えれば、ソフトウェアは、直ちに使用するためにメモリ上で既に準備されている。したがってシステムは、何らかの他のソフトウェアをインストールすることなく方法を実施するのに適している。そのようなシステムはまた、命令を実行する、メモリに結合された少なくとも１つのプロセッサをも備えることができる。言い換えれば、システムは、プロセッサに結合されたメモリ上にコーディングされた命令を含み、命令は、方法を実施する手段を提供する。そのようなシステムは、モデル化ボリュームを設計するのに効率的なツールである。
【００２５】
そのようなシステムはＣＡＤシステムでよい。システムはまた、ＣＡＥおよび／またはＣＡＭシステムでもよく、ＣＡＤモデル化オブジェクトは、ＣＡＥモデル化オブジェクトおよび／またはＣＡＭモデル化オブジェクトでもよい。実際、ＣＡＤ、ＣＡＥ、およびＣＡＭシステムの任意の組合せに対応するデータによってモデル化オブジェクトを定義することができるので、こうしたシステムは互いに排他的ではない。
【００２６】
システムは、例えばユーザによって命令の実行を開始する少なくとも１つのＧＵＩを備えることができる。特に、ＧＵＩは、最初からデクセルの集合を設計すること（Ｓ１０）により、またはシステムのメモリから、もしくはシステムの外部であるが例えばネットワークサービスによってシステムに結合されたメモリからデクセルの集合を取り出すことにより、ユーザがそのようなデクセルの集合を提供するステップ（Ｓ１０）を開始することを可能にすることができる。ＧＵＩはまた、ユーザが彫刻操作を提供する（Ｓ２０）ことをも可能にすることができる。ＧＵＩはＧＰＵを備えることができる。そのような場合、プロセッサはＧＰＵでよい。言い換えれば、方法のステップ、具体的には更新するステップ（Ｓ３０）を少なくとも実行するプロセッサはＧＰＵでよい。そのようなシステムは、ユーザによってモデル化ボリュームを設計するのに効率的なツールである。デクセルベースのアルゴリズムは、超並列ハードウェアに十分に適しているので、現代のグラフィック処理装置（ＧＰＵ）の計算能力を使用することを考慮することは自然である。
【００２７】
モデル化ボリュームは３Ｄ（すなわち３次元）でよい。このことは、モデル化ボリュームがその３Ｄ表現を可能にするデータによって定義されることを意味する。３Ｄ表現は、表現されるボリュームのすべての角度からの閲覧を可能にする。例えば、モデル化ボリュームが３Ｄ表現されるとき、モデル化ボリュームを処理し、その任意の軸の周りに、または表現が表示される画面内の任意の軸の周りに回転することができる。これは特に、３Ｄモデル化されない２Ｄアイコンを除外する。３Ｄ表現のディスプレイは設計を容易にする（すなわち、設計者がその作業を統計的に達成する速度を向上させる）。製品の設計は製造工程の一部であるので、これにより、業界での製造工程が加速される。
【００２８】
図２に、典型的なＣＡＤシステムのＧＵＩの一例を示す。
【００２９】
ＧＵＩ２１００は、標準メニューバー２１１０、２１２０、ならびに下端ツールバー２１４０およびサイドツールバー２１５０を有する典型的なＣＡＤ状のインターフェースでよい。当技術分野で周知のように、そのようなメニューバーおよびツールバーは、ユーザ選択可能なアイコンのセットを含み、各アイコンは、１つまたは複数の操作または機能に関連付けられる。こうしたアイコンの一部は、ＧＵＩ２１００内に表示される３Ｄモデル化オブジェクト２０００に対する編集および／または作業のために適合されたソフトウェアツールに関連付けられる。ソフトウェアツールはワークベンチとしてグループ化することができる。各ワークベンチはソフトウェアツールのサブセットを含む。具体的には、ワークベンチのうちの１つは、モデル化製品２０００の幾何学的特徴を編集するのに適した編集ワークベンチである。動作の際に、設計者は、例えばオブジェクト２０００の一部を事前選択し、次いで操作（例えば、彫刻操作、または寸法、色などを変更するような任意の他の操作）を開始し、または適切なアイコンを選択することによって幾何学的制約を編集することができる。例えば、典型的なＣＡＤ操作は、画面上に表示された３Ｄモデル化オブジェクトの打抜きまたは折曲げのモデリングである。
【００３０】
ＧＵＩは、例えば、表示された製品２０００に関するデータ２５００を表示することができる。図２の例では、「特徴ツリー」として表示されるデータ２５００、およびその３Ｄ表現２０００が、ブレーキキャリパおよびディスクを含むブレーキアセンブリに関係する。ＧＵＩはさらに、例えばオブジェクトの３Ｄ配向を容易にし、編集される製品の操作のシミュレーションをトリガする、様々なタイプのグラフィックツール２１３０、２０７０、２０８０を示すことができ、または表示される製品２０００の様々な属性をレンダリングすることができる。ユーザがグラフィックツールと対話することを可能にするように、カーソル２０６０を触覚デバイスによって制御することができる。
【００３１】
図３に、クライアントコンピュータシステム、例えばユーザのワークステーションとしてのシステムのアーキテクチャの一例を示す。
【００３２】
クライアントコンピュータは、内部通信バス１０００に接続された中央演算処理装置（ＣＰＵ）１０１０と、やはりバスに接続されたランダムアクセスメモリ（ＲＡＭ）１０７０とを備える。クライアントコンピュータは、バスに接続されたビデオランダムアクセスメモリ１１００に関連付けられるグラフィックス処理装置（ＧＰＵ）１１１０をさらに備える。ビデオＲＡＭ１１００は、当技術分野ではフレームバッファとしても知られる。大容量記憶デバイスコントローラ１０２０は、ハードドライブ１０３０などの大容量メモリデバイスへのアクセスを管理する。コンピュータプログラム命令およびデータを有形に実施するのに適した大容量メモリデバイスは、例としてＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリデバイスなどの半導体メモリデバイス、内部ハードディスクや取外し可能ディスクなどの磁気ディスク、光磁気ディスク、およびＣＤ−ＲＯＭディスク１０４０を含む、すべての形態の不揮発性メモリを含む。上記のいずれかを、特別に設計されたＡＳＩＣ（特定用途向け集積回路）によって補足することができ、または特別に設計されたＡＳＩＣに組み込むことができる。ネットワークアダプタ１０５０は、ネットワーク１０６０へのアクセスを管理する。クライアントコンピュータはまた、カーソル制御デバイス、キーボードなどの触覚デバイス１０９０をも含むことができる。カーソル制御デバイスはクライアントコンピュータで使用され、図２を参照しながら述べたように、ユーザが画面１０８０上の任意の所望の位置にカーソルを選択的に配置することが可能となる。画面により、コンピュータモニタなどの、その上で表示を実施することのできる任意のサポートを意味する。さらに、カーソル制御デバイスは、ユーザが様々なコマンドを選択し、制御信号を入力することを可能にする。カーソル制御デバイスは、システムに対する入力制御信号用の複数の信号生成デバイスを含む。通常、カーソル制御デバイスはマウスでよく、マウスのボタンは信号を生成するのに使用される。
【００３３】
システムに方法を実施させるために、コンピュータによって実行される命令を含むコンピュータプログラムが提供され、命令はこのための手段を含む。プログラムは、例えば、デジタル電子回路で、またはコンピュータハードウェア、ファームウェア、ソフトウェア、もしくはそれらの組合せで実装することができる。本発明の装置は、プログラマム可能プロセッサによる実行のために機械可読記憶デバイスで有形に実施されたコンピュータプログラム製品で実装することができ、本発明の方法ステップは、入力データに作用し、出力を生成することによって本発明の機能を実施するための命令のプログラムを実行するプログラム可能プロセッサで実施することができる。有利には、命令は、データ記憶システム、少なくとも１つの入力デバイス、および少なくとも１つの出力デバイスからデータおよび命令を受信し、それらに対してデータおよび命令を送信するように結合された少なくとも１つのプログラム可能プロセッサを含むプログラム可能システム上で実行可能な１つまたは複数のコンピュータプログラムで実装することができる。アプリケーションプログラムは、高水準手続き型またはオブジェクト指向プログラミング言語、または望むならアセンブリ言語または機械語で実装することができ、いずれの場合も、言語はコンパイル型言語またはインタプリタ型言語でよい。プログラムは、フルインストールプログラムまたは更新プログラムでよい。後者の場合、プログラムは、システムが方法を実施するのに適した状態に、既存のＣＡＤシステムを更新する。
【００３４】
方法は、モデル化ボリュームを表すデクセルの集合を提供すること（Ｓ１０）を含む。これにより、モデル化ボリュームの軽い表現が可能となる（言い換えれば、少ないメモリ空間を使用してモデル化ボリュームを表現することができる）。これにより、容易に処理することのできるモデル化ボリュームの表現も可能となる。特に、デクセルの集合のデータ構造のために、モデル化ボリュームがデクセルの集合によって表されるとき、モデル化ボリュームに対する設計操作を特に効率的に実施することができる。実際に、高い応答性および高いロバストネスで設計操作を実施することができる。
【００３５】
「デクセル」という用語は、（「ピクセル」という用語が「ピクチャ要素」に対するショートカットであるのと同様に）「深さ要素（ｄｅｐｔｈ ｅｌｅｍｅｎｔ）」に関するショートカットであることが知られている。デクセルの概念は、多数の研究論文で言及されている。この方法の状況では、デクセルは、少なくとも１つの線分、すなわち１対の３Ｄ点の集合を含む。一例では、モデル化ボリュームは、少なくとも２つの線分の集合を含む少なくとも１つのデクセルを含む。デクセルの線分がいくつかある場合、それを順序付けることができ（そのような場合、デクセルはリストである）、または無順序でよい。デクセルの線分は、直線とモデル化ボリュームとの間の共通部分を表す。言い換えれば、モデル化ボリュームと交わる仮想直線を考慮すると、デクセルは、所与の直線を起源とし、共通部分の計算の結果として得られる線分の集合である。したがって、デクセルの集合を提供すること（Ｓ１０）は、例えば、仮想直線を追跡し、仮想直線とモデル化ボリュームとの間の共通部分を計算することにより、そのような共通部分を計算することを含むことができ、モデル化ボリュームは当初、Ｂ−Ｒｅｐまたは任意の他のボリューム表現によって表現することができる。したがって、デクセルの集合はモデル化ボリュームを表す。
【００３６】
デクセルの集合がコンピュータ実装データとして提供される（Ｓ１０）ことに留意することは重要である。したがって、モデル化ボリュームの任意の表現に関する、上記および下記で与えられる定義は、データ構造の観点からの含意を有する。例えば、線分を１対の３Ｄ位置（例えば、互いにリンクされた２つの３Ｄ位置）として与えることができる。３Ｄ位置自体は、基準３Ｄフレームに関連付けられる３つの座標（例えば浮動小数点）のリストとして提供することができる。デクセルは線分の集合であり、そのことは、線分が集合構造で互いにリンクされることを示唆する。デクセルの集合のデクセルも互いにリンクすることができる。少なくとも１つの線分の集合をそれ自体含むデクセルの集合によってモデル化ボリュームを表現することにより、モデル化ボリュームの高速な更新（Ｓ３０）が可能となる。
【００３７】
次に、デクセル構造６７としてデクセルの集合を提供するステップ（Ｓ１０）の一例を提示する図４〜６を参照しながら、デクセルの概念を示す。
【００３８】
モデル化ボリュームが与えられ、無限直線が与えられるとすれば、デクセルは、無限直線とモデル化ボリュームとの間の共通部分を表す線分（または間隔）の集合である。この線分の集合が、各線分の境界点の集合としてメモリに取り込まれる。デクセル構造は、例えば矩形グリッド上に順序付けられることによって編成される（線分の集合をそれぞれ含む）デクセルの集合である。図４および５に、モデル化ボリューム４０を１０×１０の直線のグリッド５０と共に示す。この例の方法は、図４上に示すように、例えばＢ−Ｒｅｐとしてモデル化ボリューム４０を設けることを含む。次いで、この例の方法は、図５上に示すように、モデル化ボリューム４０と（少なくとも部分的に）交わる１０×１０の直線のグリッド５０を定義することを含む。次いで、この例の方法は、図６上に表すように、線分６０および／または６２の集合を含むデクセル６５を計算することを含む。図上では、１つのデクセル６５を円で囲んでいる。デクセル６５は、直線５０がモデル化ボリューム４０と１つの地点で交わるか、それともいくつかの別々の地点で交わるかに応じて、いくつかの線分６０、または１つの線分６２を含むことができる。もちろん、あるいは、方法は、メモリからデクセル６５を取り出すこともできる。いずれの場合も、デクセル構造６７がそのようにして提供される。
【００３９】
図６に、得られるデクセル構造６７を示す。すべての直線５０がモデル化ボリューム４０と交わるわけではなく（この例では、モデル化ボリューム４０と交わる直線は５２本だけである）、同数のデクセル６５が生じることに気付くはずである（モデル化ボリューム４０と交わらない直線を実際に廃棄することができ、その直線はデクセルを生じない）。さらに、ある直線５０は１つの線分６２を通じてモデル化ボリューム４０と交わり（例えば、デクセル（２，３）またはデクセル（９，６））、他の直線５０は、いくつかの線分６０を通じて、例えば２つの線分（例えば、デクセル（７，７）またはデクセル（４，７））、または３つの線分（デクセル（２，８）またはデクセル（５，８））、または４つの線分（デクセル（２，９）またはデクセル（４，９））を通じてモデル化ボリューム４０と交わる。得られるデクセル構造６７は、１つの線分６２を有する３６個のデクセル６５と、２つの線分６０を有する６個のデクセル６５と、３つの線分６０を有する５個のデクセル６５と、４つの線分６０を有する５個のデクセルとを含む、５２個のデクセル６５を含む。
【００４０】
（Ｓ１０）で提供されるデクセルの集合は、トリデクセル構造でよい。トリデクセル構造は、通常はｘ軸に平行なデクセル構造、ｙ軸に平行なデクセル構造、およびｚ軸に平行なデクセル構造である、３つのデクセル構造を含むことによって定義される。方法は、任意の時に、例えば提供（Ｓ２０）中および更新（Ｓ３０）中に、モデル化ボリュームのグラフィカル表現を表示することを含むことができる。表示は、デクセルの集合に基づくことができる。トリデクセル構造は、わずかに「閲覧方向」依存であるので、良好な表示をもたらす。トリデクセル構造は特に、ユーザが視点を変更するときにより正確な表示をもたらす。
【００４１】
図６〜８はそれぞれ、同一のモデル化ボリュームを表すデクセル構造を表す。言い換えれば、図６〜８の３つのデクセル構造を含むトリデクセルデータによってモデル化ボリュームを定義することができる。図６は、ｙ軸に沿ったデクセル構造６７を示す。図７は、ｘ軸に沿ったデクセル構造６８を示す。図８は、ｚ軸に沿ったデクセル構造６９を示す。各図上で、デクセルの直線は、それぞれの軸に対して平行である。
【００４２】
データ間で、線分の終点でのモデル化ボリュームの境界に対する外部法線ベクトルを与えることもできる。これにより、モデル化ボリュームのより精細なレンダリングが可能となる。
【００４３】
方法はまた、モデル化ボリューム上に対する彫刻操作（Ｓ２０）を提供することをも含む。彫刻操作は、システムによって提供される、モデル化ボリュームを彫刻する任意の操作である。モデル化ボリュームを彫刻することにより、ブール演算を介してモデル化ボリュームからボリュームを追加および／または除去することを意味する。したがって、彫刻操作は、モデル化ボリュームに対する少なくとも１つのボリュームブール演算の任意の組合せである。例えば、ローカルボリューム除去およびローカルボリューム追加は彫刻操作であるが、表面からの押出しは、何らかのブール演算に基づくものではないので、彫刻操作ではない。彫刻プロセスは、任意の一連の少なくとも１つの彫刻操作である。一例では、彫刻操作は、持続時間にわたってモデル化ボリュームに加えられる（引かれる）連続的ボリューム（すなわち、互いに素ではない）に関係する一連の連続するブール演算である。例えば、彫刻操作は機械加工操作を表す。
【００４４】
したがって、デクセルの集合は任意の立体を表すことができ、方法は、立体の実際の彫刻をシミュレートすることができる。方法は特に、コンピュータ支援設計システムまたはコンピュータ支援製造システムを使用するリアルタイム機械加工シミュレーションに含めることができる。言い換えれば、立体はストックでよく、方法は、切削工具によって仮想的に機械加工されるストックの形状を表示することができる。そのような場合、モデル化ボリュームはストックを表し、操作は切削操作である。この例を、仮想粘土に対する複合製造および形状彫刻などの、材料も部品に追加される他の製造工程に一般化することができる。この例を、機械設計、形状設計、建築などを含むすべての従来型立体モデリングアプリケーションに一般化することもできる。最後に、その性能により、方法は、対話式３Ｄ彫刻などのより先進的なアプリケーションを扱うことができる。最も一般的には、彫刻操作は機械加工操作を表すことができる。そのような場合、モデル化ボリュームは、機械加工操作を受ける工作物を表すことができ、したがって方法は、工作物の機械加工のシミュレーションを改善する。したがって方法は、仮想機械加工プロセスをテストするための良い基礎として働くことができる。
【００４５】
実際、方法は、彫刻操作に応答して（すなわち彫刻操作に従って）デクセルの集合を更新する（Ｓ３０）（すなわち修正する）ことをさらに含む。言い換えれば、方法は、当初提供されたデクセルの集合（Ｓ１０）に彫刻操作を適用する。更新後のデクセルの集合は、彫刻（例えば機械加工）後のオブジェクトを表す。
【００４６】
各デクセルは線分の集合を含む。モデル化ボリュームと交わる直線のすべての線分が、１つのデクセルとしてグループ化される。これにより、モデル化ボリュームの直線ごとの処理が可能となり、したがって、例えば並列処理が可能となるので、より効率的な処理が可能となる。さらに、デクセルの集合が隣接デクセルのグループに区分される。デクセルは、デクセル間の距離が所定のしきい値より低いとき、隣接すると言われる。したがって、デクセルの集合を隣接デクセル（すなわち、グループのうちの２つのデクセルが必ず隣接する）に区分することができる（すなわち、デクセルの互いに素なサブ集合に分割することができ、その再結合は、デクセルの集合全体を構成する）。第１のデクセルと第２のデクセルとの間の距離は、第１のデクセルの直線と第２のデクセルの直線との間の距離である。第１の直線と第２の直線との間の距離は、第１の直線が第２の直線からどれほど離れた位置にあるかの尺度となる任意の距離でよい。例えば、直線が平行である場合、距離は、第１の直線の点と第２の直線の点との間の最小ユークリッド距離でよい。直線が平行ではない場合、距離は、第１の直線の点と第２の直線の点との間の最小ユークリッド距離でよく、２つの点は、デクセルの集合の凸閉包に属する。
【００４７】
グループのデクセルのそれぞれに含まれる線分の最大数に応じたメモリ空間が、各グループに割り振られる。言い換えれば、グループに割り振られるメモリ空間は、グループの各デクセルに含まれる線分の最大数の関数であり、この関数は、増加関数、恐らくは線形関数である。これにより、デクセルの集合に割り振られたメモリ空間の最適化された使用が可能となる。実際、彫刻操作、特に機械加工操作を表す彫刻操作は、モデル化ボリュームに対して局所的影響を及ぼす。デクセルを近隣デクセルのグループにグループ化することにより、デクセルの集合を更新する（Ｓ３０）とき、デクセルの集合のグループごとの処理が可能となる。それによって、例を参照しながら説明するように、グループごとにメモリを割り振り、グローバル割振りメモリを最適化することが可能となる。
【００４８】
方法の実行で示唆されるハードウェアおよび／または彫刻コンテキストへの適合の際に、デクセルの集合を隣接デクセルのグループに区分することができる。言い換えれば、方法の実行のために使用されるハードウェア（プロセッサおよび／またはメモリなど）および／または彫刻コンテキスト（すなわち、方法のコンテキストに関する情報）に対して区分化を適合させることができる（すなわち、区分化はそれらに依存することができる）。例えば、１つのグループ内部の隣接デクセルの最大数は、プロセッサが実行することのできる並列スレッド数の増加関数でよい。彫刻コンテキストは、モデル化ボリュームおよび／または彫刻操作に関する情報を含むことができる。例えば、彫刻コンテキストは、モデル化ボリュームの複雑さ（例えば、モデル化ボリュームがどれだけ不規則であるかの尺度）および／または彫刻操作の複雑さ（例えば、彫刻操作を実施するために仮想的に使用される工具の幾何形状）を測定することができる。彫刻コンテキストはまた、そのような工具のサイズに関する情報をも含むことができる。例えば、１つのグループ内部の隣接デクセルの最大数は、モデル化ボリュームの複雑さ、彫刻操作の複雑さの減少関数、および／または彫刻工具のサイズの増加関数でよい。
【００４９】
次に、方法の利点を強調するために従来技術を論じる。
【００５０】
従来技術で知られるＬＤＮＩ実装の決定的な弱点は、所与の精度レベルに達するのに必要なメモリのサイズである。周知のＬＤＮＩ実装は、「フレームバッファ」および「レイヤ」を利用し、ＯｐｅｎＧＬおよびＳｈａｄｅｒｓプログラミングを使用するＧＰＵで、モデル化ボリュームを表すデクセルの集合を処理する。「フレームバッファ」は、当初はピクセルの２次元アレイとしてイメージを格納する専用にされた、ＧＰＵ内に配置されるメモリエリアである。ＧＰＧＰＵ技術は、このフレームバッファを使用して、深さ間隔（すなわち、デクセルの線分）の２次元アレイを格納する。フレームバッファの各要素は１つの線分のみを含むことを理解しなければならない。「レイヤ」は以下のように定義される。各デクセル内で、線分が深さ順序に従ってソートされる。「レイヤ」は、同一の深さ順序を有するすべての線分の集合である。
【００５１】
ＯｐｅｎＧＬおよびＳｈａｄｅｒｓプログラミングを使用する従来技術の計算は、各レイヤを格納するために完全なフレームバッファを必要とする。したがって、デクセル構造が与えられるとして、デクセルの間隔の最大数をＮmaxとすると、Ｎmax個のレイヤが計算され、同数のフレームバッファに格納される。計算するフレームバッファの大部分が非常に希薄である場合であっても、このコンテキストでのメモリ管理の剛性は、異存がない限り、性能のために、ＧＰＵボード上にモデル全体が常駐するように保つことを要求する。したがって、デクセルの集合がＮx＊Ｎy個のデクセルを含む場合、オンボードメモリは、サイズＮx＊Ｎy＊Ｎmaxのバッファを確保しなければならない。このことを図９〜１３を参照しながら示す。
【００５２】
図６のデクセル構造６７について、フレームバッファサイズは、１０＊１０の直線のグリッドに従ってＮx＊Ｎy＝１０＊１０である。少なくとも１つのデクセル（例えば、図６の円で囲ったデクセル６５）が４つの線分６０を含むので、図９に示されるように、４つのレイヤ（７２、７４、７６、および７８）がデクセルによって定義される。次に、サイズ１０＊１０のグリッドとしてフレームバッファを表現する図１０〜１３も参照し、フレームバッファがボックスに対応するグリッド上の位置およびフレームバッファに対応するレイヤに関するデクセル線分を格納する場合、×印がそのボックス内に存在する。第１のフレームバッファ８２は、線分の第１のレイヤ７２を格納し、第２のフレームバッファ８４は、線分の第２のレイヤ７４を格納し、第３のフレームバッファ８６は、線分の第３のレイヤ７６を格納し、第４のフレームバッファ８８は、線分の第４のレイヤ７８を格納する。図１０〜１３の表は、フレームバッファ８２〜８８の使用されるメモリスロットおよび未使用のメモリスロットを示す。Ｘフラグを付けたボックス８７は１つの線分を格納し、空のボックス８９は未使用メモリである。すべての４つのフレームバッファ（８２、８４、８６、８８）は、割り振られたメモリであり、大量の未使用メモリを示すことを理解しなければならない。
【００５３】
従来技術のこの例に関する、割り振られたメモリと使用されるメモリとの間のバランスは以下の通りである。すべての４つのフレームバッファに対して必要なメモリサイズはＮx＊Ｎy＊Ｎmax＝１０＊１０＊４＝４００であり、使用されるメモリは、デクセルの間隔の数である８３である。さらに、ＬＤＮＩフレームバッファの希薄なデータ表現は、レイヤのリンクリストや、デクセル／スレッドレベルの間接テーブル（ｉｎｄｉｒｅｃｔｉｏｎ ｔａｂｌｅ）などの通常の希薄な行列表現からは直接的に導出されない。実際、そのような技法は、超並列ハードウェアアーキテクチャおよび対応するプログラミング抽象化に適合されず、したがってこれにより、実行速度およびデータフローが非効率となる。
【００５４】
従来技術とは対照的に、方法は、高速かつロバストな更新（Ｓ３０）を可能にすると共に、使用するメモリ空間が比較的わずかである。実際、少なくとも１つの線分の集合をそれぞれ含むデクセルの集合として編成されるデータの構造により、並列処理が可能となる。隣接デクセルのグループへの区分化と、グループのデクセルのそれぞれに含まれる線分の最大数に応じたメモリ空間の割振りとにより、グループごとに並列処理を実行することが可能となる。彫刻操作は通常は局所的効果を有するので、これにより、並列処理の利点を獲得することが可能となると共に、従来技術でのメモリサイズ占有に関する不都合が回避される。
【００５５】
デクセルの集合を更新すること（Ｓ３０）は、彫刻操作によって影響を受ける隣接デクセルのグループを求めること、および求めたグループのそれぞれを更新することを含むことができる。言い換えれば、更新すること（Ｓ３０）により、効率が向上するように、更新時に実際に修正すべきグループが修正される。実際に、例えば計算を加速するために、隣接デクセルのどのグループが彫刻操作によって影響を受けるかを予測することは有用であることがある。
【００５６】
求めたグループのそれぞれを更新することは、それぞれのグループについて、並列処理によってそれぞれのグループのデクセルを更新することを含むことができる。これにより、より高速な更新（Ｓ３０）が可能となり、したがってデクセルの集合が表示される場合、彫刻操作を与えるユーザアクションに対するより高速な応答が可能となる。
【００５７】
並列処理は、システムによって複数のタスクを同時に実行することからなる。この方法の場合、それぞれのグループのデクセルを更新することは、それぞれのグループのデクセルのそれぞれに関する単一命令スレッドを実行することを含むことができる。したがって、それぞれのグループのデクセルを更新することは、ＳＩＭＤ（単一命令多重データ）並列処理によって実行することができる。方法を実行するシステムのプロセッサは特に、例えばシステムが１０または１００を超えるプロセッサとネットワーキングされる場合、超並列処理ユニットでよい。
【００５８】
各デクセルについて、ブール演算、オフセット、コリジョン検出などの通常のモデリング演算子は、その１次元カウンターパート、すなわち線分に対する単純な演算となる。あるデクセルの計算および更新は、別のデクセルに関する対応する演算には依拠しないので、モデルは超並列処理に良く適合する。
【００５９】
次に、ワーキンググループおよび単一命令多重データ実行を論じ、図示する。ワーキンググループおよび単一命令多重データを介して方法を実行することができる。隣接デクセルのグループはワーキンググループを構成し、更新するステップ（Ｓ３０）は、彫刻操作によって影響を受けると判定した各グループに関するＳＩＭＤ実行を含むことができる（そのような判定は、恐らくはＳＩＭＤ実行の最初のステップである）。
【００６０】
ワーキンググループおよびＳＩＭＤ（単一命令多重データ）実行はＯｐｅｎＣＬ概念である。すなわち、同一のワーキンググループに属するすべてのスレッドが、「単一命令多重データ」方式に従って挙動する。一例として、２つの入力数の最大数を出力する非常に単純なプログラムをここで考慮する。すなわち、ａおよびｂが２つの入力数であるとして、ｍａｘ（ａ，ｂ）である。
【００６１】
プログラムは以下の命令を含むことができる。
01 if(a>b)then
02 c:=a
03 else
04 c:=b
05 end if
06 return c
このプログラムは６つの命令を含む。ここで、「ｍａｘ」プログラムを３回呼び出すことによって３対の数の最大数を計算する以下の「Ｔｅｓｔ」プログラムを考慮する。
Program Test
x:=max(5,4)
y:=max(2,6)
z:=max(3,3)
end.
「Ｔｅｓｔ」プログラムの順次実行は、コンピュータが、第１の呼出しの命令１、２、５、６、第２の呼出しの命令１、３、４、５、６、および第３の呼出しの命令１、３、４、５、６を次々に実行するためのものである。この結果、１４個の命令が実行される。
【００６２】
次に、同一のワーキンググループに属する３つのトレッドが、「Ｔｅｓｔ」プログラムを実行することができる。各スレッドは、ＳＩＭＤ戦略に従って「ｍａｘ」プログラムに対する１つの呼出しを実行する。このことは、プログラム「ｍａｘ」に対するすべての３つの呼出しの命令が、異なるデータセットを処理するにも関わらず「同時に」実行されることを意味する。より厳密には、表Ｉがステップバイステッププロセスを示す。
【００６３】
【表１】
【００６４】
計算のステップ１で、ワーキンググループが、すべての３つのデータセットと共に、「ｍａｘ」プログラムの第１の命令「ｉｆ（ａ＞ｂ）ｔｈｅｎ」を実行する。ステップ２で、分岐効果は、第１のスレッドが「ｍａｘ」プログラムの命令２を実行し、第２および第３のスレッドがこの期間中待機するようなものとなる。これは、第２および第３のスレッドがａ≦ｂの状況を管理し、第１のスレッドがａ＞ｂの状況を管理するからである。ステップ３で、第２および第３のスレッドが「ｍａｘ」プログラムの命令３を実行し、第１のスレッドが待機する。これが表で示されるように続行される。下端の行は、１４個の命令を実行する順次戦略とは対照的に、３つのスレッドワーキンググループが、等価なコンピューティング時間の６個の命令を実行することによって「ｍａｘ」プログラムの３つの呼出しを実行することである。
【００６５】
明らかに、この例は、独立したデータセットと共にプログラムが実行されるとき、かつ分岐論理がある実行から別の実行に発散し過ぎないとき、同期スレッドのワーキンググループが効率的であることを示す。
【００６６】
同様に、方法は、各グループのデクセルに対してＳＩＭＤを実行することによってグループのそれぞれを更新することができる。各グループのデクセルは隣接するので、ＳＩＭＤは、ワーキンググループ（隣接デクセルのグループ）のすべてのスレッド（すなわち、隣接デクセルの前記グループのデクセル）上で適時に同様の方式で実行される可能性が高い。実際に、同一のグループのデクセルは統計的に同様であり、彫刻操作によって同様に影響を受ける。したがって、同一のグループのデクセルの更新は通常、（ほぼ）同一の操作を含む。このため、並列処理の利点が得られ、メモリ空間が節約される。
【００６７】
方法は、更新後グループのデクセルのそれぞれに含まれる線分の最大数が修正されるとき、更新後グループに割り振られるメモリ空間を適合させることをさらに含むことができる。言い換えれば、方法は、彫刻操作に応答してデクセルの集合を更新した（Ｓ３０）後に、メモリの割振りを修正することをさらに含むことができる。このことは、メモリブロックを割振り解除すること、またはメモリブロックをさらに割り振ることを含むことができる。このブロック割振り／割振り解除機構は、メモリモデルの効率を劇的に改善する。実際には、オンボードメモリのサイズが束縛されるので、このブロック割振り／割振り解除機構は、所与のメモリサイズに対してずっと良好な精度を可能にする。このブロック割振り／割振り解除機構は、性能の向上も促す。
【００６８】
それによって、方法は、（例えば、ＣＵＤＡまたはＯｐｅｎＣＬプログラミング抽象化としての）超並列ハードウェアの状況に適合されたメモリブロック割振り／割振り解除の機構を提供することができる。ワーキンググループレベル（Ｏｐｅｎ ＣＬ概念）でブロックを割振り／割振り解除することができ、間接テーブルが、それぞれのワーキンググループおよび対応するデクセルのグループについて、こうしたブロックをアドレス指定することができる。
【００６９】
ＣＵＤＡおよびＯｐｅｎＣＬ言語は、一例を参照しながら以下で論じる特徴と共に、超並列ハードウェアのためのプログラミング抽象化を提供する。
【００７０】
この例では、スレッドがワーキンググループ（ＯｐｅｎＣＬ用語）にグループ化される。すなわち、好ましくは、同一のワーキンググループに属するスレッドがＳＩＭＤ式（単一命令多重データ）に実行され、したがって分岐発散が小さいときにより効率的となる。
【００７１】
メモリは、２つの主なカテゴリに分割される。第１は、アクセスが迅速であり、単一のスレッドに対してプライベートであり、またはワーキンググループによって共有される、小さいサイズのプライベート／ローカル（ＯｐｅｎＣＬ用語）メモリである。第２は、アクセスが低速であり、すべてのスレッドから可視であり、好ましくは連続するブロックによってアクセスされる、大きいグローバルメモリエリアである。
【００７２】
更新（Ｓ３０）のあるステージで、個々のスレッドが個々のデクセルの更新を管理し、同期スレッドの「ワーキンググループ」が、ここではデクセルグループと呼ぶ近隣デクセルのグループを管理する。この例のデータ構造は、すべてのデクセルグループがｋと表す同数のデクセルを有するように設計される。同一のデクセルグループ（通常はグリッド内部の小さいサブグリッド）のデクセルの幾何学的近接は、類似の構成の可能性および必要なレイヤ数を増大させる。
【００７３】
図６の例に戻ると、この例の方法に従って、デクセル構造６７を５＊５のグリッド＝２５デクセルグループに区分することができ、各グループはｋ＝４デクセルを含む。同一のグループ内のすべてのデクセルに、前記グループのすべてのデクセルの線分の最大数に応じてますます多く、同一のメモリサイズを割り振ることができる。図１４に、デクセルグループを、それぞれの線分の最大数１４０と共に示す。
【００７４】
このデクセルグループ構造に対して割り振られるメモリサイズは、１線分デクセルの１０グループ、３線分デクセルの３グループ、２線分デクセルの１グループ、および４線分デクセルの３グループ、すなわち（１０＊１＋３＊３＋１＊２＋４＊３）＊４＝１３２メモリユニットを格納する。従来技術で必要とされる４００メモリユニットと比較して、これは、メモリ空間の特に高い向上である。
【００７５】
処理の間、同一のデクセルグループのデクセルの線分の最大数が１つ増加するとき、グローバルメモリのブロックを割り振ることができる。もちろん、このメモリブロックは線分を格納するようなサイズにされる。逆に、同一のワーキンググループ内のすべてのデクセルの間隔の最大数が減少するとき、メモリブロックテーブル内の対応するブロックを割振り解除することができる。このようにして、次の再割振りがフリーブロックを再利用することができる。したがって、これをＳＩＭＤ（同期）スレッドのグループによって最適に実施することができる。
【００７６】
この点で、グループのデクセルのそれぞれをどのように更新するかに関しては、更新するステップ（Ｓ３０）が各グループに関する並列処理によって実行されるようにＳＩＭＤを介してそのような更新を行うことができることを別にして、ほとんど述べなかった。方法は、デクセルのそれぞれを更新するための任意の方式を含むことができる。例えば、それぞれのグループのデクセルを更新することは、それぞれのグループのそれぞれのデクセルについて、それぞれのデクセルに対する彫刻操作の影響を評価し、それに応じてそれぞれのデクセルを修正することを含む。例えば、彫刻操作が切削操作である場合、そのような操作によって影響を受けるデクセルから切削容積を差し引くことができる。
【００７７】
それぞれのデクセルに対する彫刻操作の影響を評価することは、それぞれのデクセルの線分に対する彫刻操作の影響を評価することを含むことができる。言い換えれば、更新は線分レベルで行われる。実際に、彫刻操作は、デクセルの線分構造を修正することができ、例えばある線分を削除することができ、ある線分を追加することができ、かつ／またはある線分を修正することができる。
【技術分野】
【０００１】
本発明は、コンピュータプログラムおよびシステムの分野に関し、より詳細には、デクセルの集合によって表されるモデル化ボリュームを設計する方法、システム、およびプログラムに関する。
【背景技術】
【０００２】
オブジェクトの設計、エンジニアリング、および製造のための複数のシステムおよびプログラムが市場で提供されている。ＣＡＤはコンピュータ支援設計（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ Ｄｅｓｉｇｎ）の頭字語であり、例えばＣＡＤは、オブジェクトを設計するためのソフトウェア解決策に関係する。ＣＡＥはコンピュータ支援エンジニアリング（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ Ｅｎｇｉｎｅｅｒｉｎｇ）の頭字語であり、例えばＣＡＥは、将来の製品の物理的挙動をシミュレートするためのソフトウェア解決策に関係する。ＣＡＭはコンピュータ支援製造（Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ Ｍａｎｕｆａｃｔｕｒｉｎｇ）の頭字語であり、例えばＣＡＭは、製造工程および運用を定義するためのソフトウェア解決策に関係する。そのようなシステムでは、グラフィカルユーザインターフェース（ＧＵＩ）が、技法の効率に関して重要な役割を果たす。こうした技法を製品ライフサイクル管理（ＰＬＭ）システム内に組み込むことができる。ＰＬＭは、拡張された企業の概念にわたって、会社が製品データを共有し、共通のプロセスを適用し、概念から製品の寿命の終わりまでの製品の開発に関する会社の知識を活用する助けとなるビジネス戦略を指す。
【０００３】
Ｄａｓｓａｕｌｔ Ｓｙｓｔｅｍｓによって（ＣＡＴＩＡ、ＥＮＯＶＩＡ、およびＤＥＬＭＩＡという商標の下で）提供されるＰＬＭ解決策は、製品エンジニアリング知識を編成するＥｎｇｉｎｅｅｒｉｎｇ Ｈｕｂ、製造エンジニアリング知識を管理するＭａｎｕｆａｃｔｕｒｉｎｇ Ｈｕｂ、およびＥｎｇｉｎｅｅｒｉｎｇ ＨｕｂとＭａｎｕｆａｃｔｕｒｉｎｇ Ｈｕｂの両方への企業統合および接続を可能にするＥｎｔｅｒｐｒｉｓｅ Ｈｕｂを提供する。全体として、システムは、最適化製品定義、製造準備、製品およびサービスを推進する動的な知識ベースの製品作成および決定サポートを可能にするためのオープンオブジェクトモデルリンキング製品、プロセス、リソースを達成する。
【０００４】
こうしたシステムの一部は、デクセルの集合を用いたモデル化ボリュームの表現を可能にする。いくつかの論文または特許文書は特に、機械加工シミュレーションまたは対話式彫刻のためにデクセル表現を使用することを示唆している（例えば、非特許文献１〜６、特許文献１および２参照）。
【０００５】
ＧＰＧＰＵ（Ｇｅｎｅｒａｌ−Ｐｕｒｐｏｓｅ Ｃｏｍｐｕｔｉｎｇ ｏｎ Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔｓ）は、コンピュータグラフィックスのみに関する計算を一般に処理するグラフィック処理装置（ＧＰＵ）を使用して、従来は中央演算処理装置（ＣＰＵ）によって処理されたアプリケーション内の計算を実行する技法である。いくつかの論文は、現代のグラフィックス処理装置（ＧＰＵ）の処理能力（ｃｏｍｐｕｔａｔｉｏｎ ｐｏｗｅｒ）をデクセル表現のために使用することを考慮している。こうした論文はＬＤＮＩ（Ｌａｙｅｒｅｄ Ｄｅｐｔｈ−Ｎｏｒｍａｌ Ｉｍａｇｅｓ）アルゴリズムを利用し、ＬＤＮＩアルゴリズムは特定のメモリモデルに関連付けられる（例えば、非特許文献７および８参照）。
【０００６】
しかし、先行技術文献に列挙した解決策は、特にメモリ性能の観点およびユーザ利用の観点から、効率が欠けている。この状況の中で、デクセルの集合によって表されるモデル化ボリュームを設計するための改良型の解決策が依然として求められている。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】米国特許第５７１０７０９号明細書
【特許文献２】米国特許第７７４７４１８号明細書
【非特許文献】
【０００８】
【非特許文献１】"A Virtual Sculpting System Based on Triple Dexcl Models with Haptics", Xiaobo Peng and Weihan Zhang, Computer-Aided Design and Applications, 2009
【非特許文献２】"NC Milling Error Assessment and Tool Path Correction", Yunching Huang and James H. Oliver, Proceedings of the 21st annual conference on Computer graphics and interactive techniques, 1994
【非特許文献３】"Online Sculpting and Visualization of Multi-Dexel Volumes", Heinrich Muller, Tobias Surmann, Marc Stautner, Frank Albersmann, Klaus Weinert, SM '03 Proceedings of the eighth ACM symposium on Solid modeling and applications
【非特許文献４】"Virtual prototyping and manufacturing planning by using tri-dexel models and haptic force feedback", Yongfu Ren, Susana K. Lai-Yuen, and Yuan-Shin Lee, Virtual and Physical Prototyping, 2006
【非特許文献５】"Simulation of NC machining based on the dexel model: A critical analysis", Sabine Stifter, The International Journal of Advanced Manufacturing Technology, 1995
【非特許文献６】"Real time simulation and visualization of NC milling processes for inhomogeneous materials on low-end graphics hardware", Konig, A. H. and Grolier, E., Computer Graphics International, 1998. Proceedings
【非特許文献７】"GPGPU-based Material Removal Simulation and Cutting Force Estimation", B. Tukora and T. Szalay, CCP: 94: Proceedings Of The Seventh International Conference On Engineering Computational Technology
【非特許文献８】"Layered Dept-Normal Images: a Sparse Implicit Representation of Solid Models", Charlie C. L., Wang and Yong Chen, Proceedings of ASME international design engineering technical conferences. Brooklyn (NY)
【発明の概要】
【課題を解決するための手段】
【０００９】
したがって、一態様によれば、モデル化ボリュームを設計するコンピュータ実装方法が提供される。方法は、モデル化ボリュームを表すデクセルの集合を提供することを含む。各デクセルは、直線とモデル化ボリュームとの共通部分を表す少なくとも１つの線分の集合を含む。デクセルの集合は、隣接デクセルのグループに区分される。グループのデクセルのそれぞれに含まれる線分の最大数に応じたメモリ空間が、各グループに割り振られる。方法はまた、モデル化ボリュームに対する彫刻操作を提供すること、および彫刻操作に応答してデクセルの集合を更新することをも含む。
【００１０】
方法は、以下のうちの１つまたは複数を含むことができる。
−デクセルの集合を更新することが、彫刻操作によって影響を受ける隣接デクセルのグループを求めること、および求めたグループのそれぞれを更新することを含み、
−求めたグループのそれぞれを更新することが、それぞれのグループについて、並列処理によってそれぞれのグループのデクセルを更新することを含み、
−それぞれのグループのデクセルを更新することが、それぞれのグループのそれぞれのデクセルについて、それぞれのデクセルに対する彫刻操作の影響を評価すること、およびそれに応じてそれぞれのデクセルを修正することを含み、
−それぞれのデクセルに対する彫刻操作の影響を評価することが、それぞれのデクセルの線分に対する彫刻操作の影響を評価することを含み、
−それぞれのグループのデクセルを更新することが、ＳＩＭＤ（単一命令多重データ）並列処理によって実施され、
−方法は、更新後グループのデクセルのそれぞれに含まれる線分の最大数が修正されるとき、更新後グループに割り振られたメモリ空間を適合させることをさらに含み、
−デクセルの集合が、方法の実行で示唆されるハードウェアおよび／または彫刻コンテキストへの適合の際に、隣接デクセルのグループに区分される。
【００１１】
モデル化ボリュームを設計するシステムがさらに提案され、システムは、上記の方法を実行する命令がその上に記録されたメモリと、命令を実行するメモリに結合された少なくとも１つのプロセッサとを備える。
【００１２】
プロセッサは超並列処理ユニットでよい。システムは、命令の実行を開始するのに適した少なくとも１つのＧＵＩを含むことができる。ＧＵＩはＧＰＵを含むことができ、プロセッサはＧＰＵでよい。
【００１３】
上記の方法を実行する命令を含むコンピュータプログラムがさらに提案される。
【００１４】
上記のコンピュータプログラムがその上に記録されたコンピュータ可読記憶媒体がさらに提案される。
【００１５】
次に、非限定的な例として、添付の図面を参照しながら本発明の実施形態を説明する。
【図面の簡単な説明】
【００１６】
【図１】方法の一例の流れ図を示す図である。
【図２】グラフィカルユーザインターフェースの一例を示す図である。
【図３】クライアントコンピュータシステムの一例を示す図である。
【図４】方法の例を示す図である。
【図５】方法の例を示す図である。
【図６】方法の例を示す図である。
【図７】方法の例を示す図である。
【図８】方法の例を示す図である。
【図９】従来技術を示す図である。
【図１０】従来技術を示す図である。
【図１１】従来技術を示す図である。
【図１２】従来技術を示す図である。
【図１３】従来技術を示す図である。
【図１４】方法の例を示す図である。
【発明を実施するための形態】
【００１７】
図１に、モデル化ボリュームを設計するコンピュータ実装方法（以後、「方法」と呼ぶ）の一例の流れ図を示す。方法は、デクセルの集合を提供することを含む（Ｓ１０）。デクセルの集合はモデル化ボリュームを表す。（デクセルの集合の）各デクセルは、少なくとも１つの線分の集合を含む。そのような線分は、直線とモデル化ボリュームとの間の共通部分を表す。デクセルの集合は、隣接デクセルのグループに区分される。グループのデクセルのそれぞれに含まれる線分の最大数に応じたメモリ空間が、各グループに割り振られる。方法はまた、モデル化ボリュームに対する彫刻操作を提供することをも含む（Ｓ２０）。方法は、彫刻操作に応答してデクセルの集合を更新することをさらに含む（Ｓ３０）。そのような方法は、デクセルの集合によって表されるモデル化ボリュームの設計を改善する。
【００１８】
デクセルの集合によって表されるモデル化ボリュームも提供され、（デクセルの集合の）各デクセルは、少なくとも１つの線分の集合を含む。そのような線分は、直線とモデル化ボリュームとの間の共通部分を表す。デクセルの集合は、隣接デクセルのグループに区分される。グループのデクセルのそれぞれに含まれる線分の最大数に応じたメモリ空間が、各グループに割り振られる。以下で説明する方法の特徴および例は、そのようなモデル化ボリュームにも当てはまる。
【００１９】
デクセルの集合によってモデル化ボリュームを表現する符号化方式も提供される。符号化方式は、ボリュームの定義を提供することを含む。次いで符号化方式は、直線の集合を定義し、直線の集合とボリュームとの共通部分を計算し、対応するデクセルを求める。符号化方式はさらに、デクセルの集合を隣接デクセルのグループに区分し、グループのデクセルのそれぞれに含まれる線分の最大数に応じたメモリ空間を各グループに割り振る。デクセルの集合を提供するステップ（Ｓ１０）は、符号化方式を実装することができる。以下で説明する方法の特徴および例は、そのような符号化方式にも当てはまる。
【００２０】
ＣＡＤモデル化オブジェクトを設計するプロセスに方法を含めることができる。「ＣＡＤモデル化オブジェクトを設計する」ことは、モデル化オブジェクトを精巧に作るプロセスの少なくとも一部である任意の処置または一連の処置を指す。したがって、方法は、ＣＡＤモデル化オブジェクトを最初から作成することを含むことができる。あるいは、方法は、以前に作成したＣＡＤモデル化オブジェクトを提供し、次いでＣＡＤモデル化オブジェクトを修正することを含むことができる。いずれにしても、方法によって設計されるモデル化ボリュームは、ＣＡＤモデル化オブジェクトまたはその少なくとも一部、例えばＣＡＤモデル化オブジェクトによって占有される３Ｄ空間を表すことができる。方法は、デクセルの集合によって表されるモデル化ボリュームの設計を改善するので、方法は、ＣＡＤモデル化オブジェクトの設計をも改善する。
【００２１】
モデル化オブジェクトは、コンピュータシステムのメモリに格納されたデータによって定義される任意のオブジェクトである。拡張すれば、「モデル化オブジェクト」という表現はデータ自体を指す。ＣＡＤモデル化オブジェクトは、ＣＡＤシステムのメモリに格納されたデータによって定義される任意のオブジェクトである。システムのタイプに従って、異なる種類のデータによってモデル化オブジェクトを定義することができる。ＣＡＤシステムは、ＣＡＴＩＡなどの、モデル化オブジェクトのグラフィカル表現に基づいてモデル化オブジェクトを設計するのに少なくとも適した任意のシステムである。したがって、ＣＡＤモデル化オブジェクトを定義するデータは、モデル化オブジェクトの表現を可能にするデータを含む（例えば空間内の相対位置を含む、例えば幾何学データ）。
【００２２】
方法を製造工程に含めることができ、製造工程は、方法を実施した後、モデル化ボリュームに対応する物理的製品を生産することを含むことができる。いずれにしても、方法によって設計されるモデル化ボリュームは、製造オブジェクトを表すことができる。したがって、モデル化ボリュームはモデル化立体でよい（すなわち、立体を表すモデル化オブジェクト）。製造オブジェクトは、部品、部品のアセンブリなどの製品でよい。方法はモデル化ボリュームの設計を改善するので、方法は製品の製造をも改善し、したがって製造工程の生産性を向上させる。方法は、ＤＥＬＭＩＡなどのＣＡＭシステムを使用して実装することができる。ＣＡＭシステムは、製造工程および運用を定義し、シミュレートし、制御するのに少なくとも適した任意のシステムである。
【００２３】
方法はコンピュータ実装される。このことは、少なくとも１つのコンピュータまたは同様の任意のシステム上で方法が実行されることを意味する。別段の言及がない限り、方法のすべてのステップは、コンピュータによって、すなわちユーザの介入なしに実施される。例えば、更新するステップ（Ｓ３０）はコンピュータのみによって実施することができ、デクセルの集合を提供するステップ（Ｓ１０）および彫刻操作を提供するステップ（Ｓ２０）は、コンピュータのみによって、またはユーザ対話を通じて実施することができる。実際、デクセルの集合を提供するステップ（Ｓ１０）は、ユーザによって開始することができる。それによって、方法は、恐らくはユーザによって実現される彫刻操作に応じた、モデル化ボリュームを表すデクセルの集合の自動更新（Ｓ３０）を可能にする。方法のステップがユーザの介入を可能にすることができることに言及することにも価値がある。例えば、ユーザは、例えば、コンピュータによって実行されるアルゴリズムの結果を修正するために、例えば更新された（Ｓ３０）デクセルの集合を修正するために介入することができる。このことは、更新されたときにデクセルの集合を修正するステップと同等であり、修正するステップは、更新するステップ（Ｓ３０）の後に実行される。
【００２４】
方法のコンピュータ実装の典型的な例は、この目的に適したシステムで方法を実施することである。システムは、方法を実施する命令をその上に記録したメモリを備えることができる。言い換えれば、ソフトウェアは、直ちに使用するためにメモリ上で既に準備されている。したがってシステムは、何らかの他のソフトウェアをインストールすることなく方法を実施するのに適している。そのようなシステムはまた、命令を実行する、メモリに結合された少なくとも１つのプロセッサをも備えることができる。言い換えれば、システムは、プロセッサに結合されたメモリ上にコーディングされた命令を含み、命令は、方法を実施する手段を提供する。そのようなシステムは、モデル化ボリュームを設計するのに効率的なツールである。
【００２５】
そのようなシステムはＣＡＤシステムでよい。システムはまた、ＣＡＥおよび／またはＣＡＭシステムでもよく、ＣＡＤモデル化オブジェクトは、ＣＡＥモデル化オブジェクトおよび／またはＣＡＭモデル化オブジェクトでもよい。実際、ＣＡＤ、ＣＡＥ、およびＣＡＭシステムの任意の組合せに対応するデータによってモデル化オブジェクトを定義することができるので、こうしたシステムは互いに排他的ではない。
【００２６】
システムは、例えばユーザによって命令の実行を開始する少なくとも１つのＧＵＩを備えることができる。特に、ＧＵＩは、最初からデクセルの集合を設計すること（Ｓ１０）により、またはシステムのメモリから、もしくはシステムの外部であるが例えばネットワークサービスによってシステムに結合されたメモリからデクセルの集合を取り出すことにより、ユーザがそのようなデクセルの集合を提供するステップ（Ｓ１０）を開始することを可能にすることができる。ＧＵＩはまた、ユーザが彫刻操作を提供する（Ｓ２０）ことをも可能にすることができる。ＧＵＩはＧＰＵを備えることができる。そのような場合、プロセッサはＧＰＵでよい。言い換えれば、方法のステップ、具体的には更新するステップ（Ｓ３０）を少なくとも実行するプロセッサはＧＰＵでよい。そのようなシステムは、ユーザによってモデル化ボリュームを設計するのに効率的なツールである。デクセルベースのアルゴリズムは、超並列ハードウェアに十分に適しているので、現代のグラフィック処理装置（ＧＰＵ）の計算能力を使用することを考慮することは自然である。
【００２７】
モデル化ボリュームは３Ｄ（すなわち３次元）でよい。このことは、モデル化ボリュームがその３Ｄ表現を可能にするデータによって定義されることを意味する。３Ｄ表現は、表現されるボリュームのすべての角度からの閲覧を可能にする。例えば、モデル化ボリュームが３Ｄ表現されるとき、モデル化ボリュームを処理し、その任意の軸の周りに、または表現が表示される画面内の任意の軸の周りに回転することができる。これは特に、３Ｄモデル化されない２Ｄアイコンを除外する。３Ｄ表現のディスプレイは設計を容易にする（すなわち、設計者がその作業を統計的に達成する速度を向上させる）。製品の設計は製造工程の一部であるので、これにより、業界での製造工程が加速される。
【００２８】
図２に、典型的なＣＡＤシステムのＧＵＩの一例を示す。
【００２９】
ＧＵＩ２１００は、標準メニューバー２１１０、２１２０、ならびに下端ツールバー２１４０およびサイドツールバー２１５０を有する典型的なＣＡＤ状のインターフェースでよい。当技術分野で周知のように、そのようなメニューバーおよびツールバーは、ユーザ選択可能なアイコンのセットを含み、各アイコンは、１つまたは複数の操作または機能に関連付けられる。こうしたアイコンの一部は、ＧＵＩ２１００内に表示される３Ｄモデル化オブジェクト２０００に対する編集および／または作業のために適合されたソフトウェアツールに関連付けられる。ソフトウェアツールはワークベンチとしてグループ化することができる。各ワークベンチはソフトウェアツールのサブセットを含む。具体的には、ワークベンチのうちの１つは、モデル化製品２０００の幾何学的特徴を編集するのに適した編集ワークベンチである。動作の際に、設計者は、例えばオブジェクト２０００の一部を事前選択し、次いで操作（例えば、彫刻操作、または寸法、色などを変更するような任意の他の操作）を開始し、または適切なアイコンを選択することによって幾何学的制約を編集することができる。例えば、典型的なＣＡＤ操作は、画面上に表示された３Ｄモデル化オブジェクトの打抜きまたは折曲げのモデリングである。
【００３０】
ＧＵＩは、例えば、表示された製品２０００に関するデータ２５００を表示することができる。図２の例では、「特徴ツリー」として表示されるデータ２５００、およびその３Ｄ表現２０００が、ブレーキキャリパおよびディスクを含むブレーキアセンブリに関係する。ＧＵＩはさらに、例えばオブジェクトの３Ｄ配向を容易にし、編集される製品の操作のシミュレーションをトリガする、様々なタイプのグラフィックツール２１３０、２０７０、２０８０を示すことができ、または表示される製品２０００の様々な属性をレンダリングすることができる。ユーザがグラフィックツールと対話することを可能にするように、カーソル２０６０を触覚デバイスによって制御することができる。
【００３１】
図３に、クライアントコンピュータシステム、例えばユーザのワークステーションとしてのシステムのアーキテクチャの一例を示す。
【００３２】
クライアントコンピュータは、内部通信バス１０００に接続された中央演算処理装置（ＣＰＵ）１０１０と、やはりバスに接続されたランダムアクセスメモリ（ＲＡＭ）１０７０とを備える。クライアントコンピュータは、バスに接続されたビデオランダムアクセスメモリ１１００に関連付けられるグラフィックス処理装置（ＧＰＵ）１１１０をさらに備える。ビデオＲＡＭ１１００は、当技術分野ではフレームバッファとしても知られる。大容量記憶デバイスコントローラ１０２０は、ハードドライブ１０３０などの大容量メモリデバイスへのアクセスを管理する。コンピュータプログラム命令およびデータを有形に実施するのに適した大容量メモリデバイスは、例としてＥＰＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリデバイスなどの半導体メモリデバイス、内部ハードディスクや取外し可能ディスクなどの磁気ディスク、光磁気ディスク、およびＣＤ−ＲＯＭディスク１０４０を含む、すべての形態の不揮発性メモリを含む。上記のいずれかを、特別に設計されたＡＳＩＣ（特定用途向け集積回路）によって補足することができ、または特別に設計されたＡＳＩＣに組み込むことができる。ネットワークアダプタ１０５０は、ネットワーク１０６０へのアクセスを管理する。クライアントコンピュータはまた、カーソル制御デバイス、キーボードなどの触覚デバイス１０９０をも含むことができる。カーソル制御デバイスはクライアントコンピュータで使用され、図２を参照しながら述べたように、ユーザが画面１０８０上の任意の所望の位置にカーソルを選択的に配置することが可能となる。画面により、コンピュータモニタなどの、その上で表示を実施することのできる任意のサポートを意味する。さらに、カーソル制御デバイスは、ユーザが様々なコマンドを選択し、制御信号を入力することを可能にする。カーソル制御デバイスは、システムに対する入力制御信号用の複数の信号生成デバイスを含む。通常、カーソル制御デバイスはマウスでよく、マウスのボタンは信号を生成するのに使用される。
【００３３】
システムに方法を実施させるために、コンピュータによって実行される命令を含むコンピュータプログラムが提供され、命令はこのための手段を含む。プログラムは、例えば、デジタル電子回路で、またはコンピュータハードウェア、ファームウェア、ソフトウェア、もしくはそれらの組合せで実装することができる。本発明の装置は、プログラマム可能プロセッサによる実行のために機械可読記憶デバイスで有形に実施されたコンピュータプログラム製品で実装することができ、本発明の方法ステップは、入力データに作用し、出力を生成することによって本発明の機能を実施するための命令のプログラムを実行するプログラム可能プロセッサで実施することができる。有利には、命令は、データ記憶システム、少なくとも１つの入力デバイス、および少なくとも１つの出力デバイスからデータおよび命令を受信し、それらに対してデータおよび命令を送信するように結合された少なくとも１つのプログラム可能プロセッサを含むプログラム可能システム上で実行可能な１つまたは複数のコンピュータプログラムで実装することができる。アプリケーションプログラムは、高水準手続き型またはオブジェクト指向プログラミング言語、または望むならアセンブリ言語または機械語で実装することができ、いずれの場合も、言語はコンパイル型言語またはインタプリタ型言語でよい。プログラムは、フルインストールプログラムまたは更新プログラムでよい。後者の場合、プログラムは、システムが方法を実施するのに適した状態に、既存のＣＡＤシステムを更新する。
【００３４】
方法は、モデル化ボリュームを表すデクセルの集合を提供すること（Ｓ１０）を含む。これにより、モデル化ボリュームの軽い表現が可能となる（言い換えれば、少ないメモリ空間を使用してモデル化ボリュームを表現することができる）。これにより、容易に処理することのできるモデル化ボリュームの表現も可能となる。特に、デクセルの集合のデータ構造のために、モデル化ボリュームがデクセルの集合によって表されるとき、モデル化ボリュームに対する設計操作を特に効率的に実施することができる。実際に、高い応答性および高いロバストネスで設計操作を実施することができる。
【００３５】
「デクセル」という用語は、（「ピクセル」という用語が「ピクチャ要素」に対するショートカットであるのと同様に）「深さ要素（ｄｅｐｔｈ ｅｌｅｍｅｎｔ）」に関するショートカットであることが知られている。デクセルの概念は、多数の研究論文で言及されている。この方法の状況では、デクセルは、少なくとも１つの線分、すなわち１対の３Ｄ点の集合を含む。一例では、モデル化ボリュームは、少なくとも２つの線分の集合を含む少なくとも１つのデクセルを含む。デクセルの線分がいくつかある場合、それを順序付けることができ（そのような場合、デクセルはリストである）、または無順序でよい。デクセルの線分は、直線とモデル化ボリュームとの間の共通部分を表す。言い換えれば、モデル化ボリュームと交わる仮想直線を考慮すると、デクセルは、所与の直線を起源とし、共通部分の計算の結果として得られる線分の集合である。したがって、デクセルの集合を提供すること（Ｓ１０）は、例えば、仮想直線を追跡し、仮想直線とモデル化ボリュームとの間の共通部分を計算することにより、そのような共通部分を計算することを含むことができ、モデル化ボリュームは当初、Ｂ−Ｒｅｐまたは任意の他のボリューム表現によって表現することができる。したがって、デクセルの集合はモデル化ボリュームを表す。
【００３６】
デクセルの集合がコンピュータ実装データとして提供される（Ｓ１０）ことに留意することは重要である。したがって、モデル化ボリュームの任意の表現に関する、上記および下記で与えられる定義は、データ構造の観点からの含意を有する。例えば、線分を１対の３Ｄ位置（例えば、互いにリンクされた２つの３Ｄ位置）として与えることができる。３Ｄ位置自体は、基準３Ｄフレームに関連付けられる３つの座標（例えば浮動小数点）のリストとして提供することができる。デクセルは線分の集合であり、そのことは、線分が集合構造で互いにリンクされることを示唆する。デクセルの集合のデクセルも互いにリンクすることができる。少なくとも１つの線分の集合をそれ自体含むデクセルの集合によってモデル化ボリュームを表現することにより、モデル化ボリュームの高速な更新（Ｓ３０）が可能となる。
【００３７】
次に、デクセル構造６７としてデクセルの集合を提供するステップ（Ｓ１０）の一例を提示する図４〜６を参照しながら、デクセルの概念を示す。
【００３８】
モデル化ボリュームが与えられ、無限直線が与えられるとすれば、デクセルは、無限直線とモデル化ボリュームとの間の共通部分を表す線分（または間隔）の集合である。この線分の集合が、各線分の境界点の集合としてメモリに取り込まれる。デクセル構造は、例えば矩形グリッド上に順序付けられることによって編成される（線分の集合をそれぞれ含む）デクセルの集合である。図４および５に、モデル化ボリューム４０を１０×１０の直線のグリッド５０と共に示す。この例の方法は、図４上に示すように、例えばＢ−Ｒｅｐとしてモデル化ボリューム４０を設けることを含む。次いで、この例の方法は、図５上に示すように、モデル化ボリューム４０と（少なくとも部分的に）交わる１０×１０の直線のグリッド５０を定義することを含む。次いで、この例の方法は、図６上に表すように、線分６０および／または６２の集合を含むデクセル６５を計算することを含む。図上では、１つのデクセル６５を円で囲んでいる。デクセル６５は、直線５０がモデル化ボリューム４０と１つの地点で交わるか、それともいくつかの別々の地点で交わるかに応じて、いくつかの線分６０、または１つの線分６２を含むことができる。もちろん、あるいは、方法は、メモリからデクセル６５を取り出すこともできる。いずれの場合も、デクセル構造６７がそのようにして提供される。
【００３９】
図６に、得られるデクセル構造６７を示す。すべての直線５０がモデル化ボリューム４０と交わるわけではなく（この例では、モデル化ボリューム４０と交わる直線は５２本だけである）、同数のデクセル６５が生じることに気付くはずである（モデル化ボリューム４０と交わらない直線を実際に廃棄することができ、その直線はデクセルを生じない）。さらに、ある直線５０は１つの線分６２を通じてモデル化ボリューム４０と交わり（例えば、デクセル（２，３）またはデクセル（９，６））、他の直線５０は、いくつかの線分６０を通じて、例えば２つの線分（例えば、デクセル（７，７）またはデクセル（４，７））、または３つの線分（デクセル（２，８）またはデクセル（５，８））、または４つの線分（デクセル（２，９）またはデクセル（４，９））を通じてモデル化ボリューム４０と交わる。得られるデクセル構造６７は、１つの線分６２を有する３６個のデクセル６５と、２つの線分６０を有する６個のデクセル６５と、３つの線分６０を有する５個のデクセル６５と、４つの線分６０を有する５個のデクセルとを含む、５２個のデクセル６５を含む。
【００４０】
（Ｓ１０）で提供されるデクセルの集合は、トリデクセル構造でよい。トリデクセル構造は、通常はｘ軸に平行なデクセル構造、ｙ軸に平行なデクセル構造、およびｚ軸に平行なデクセル構造である、３つのデクセル構造を含むことによって定義される。方法は、任意の時に、例えば提供（Ｓ２０）中および更新（Ｓ３０）中に、モデル化ボリュームのグラフィカル表現を表示することを含むことができる。表示は、デクセルの集合に基づくことができる。トリデクセル構造は、わずかに「閲覧方向」依存であるので、良好な表示をもたらす。トリデクセル構造は特に、ユーザが視点を変更するときにより正確な表示をもたらす。
【００４１】
図６〜８はそれぞれ、同一のモデル化ボリュームを表すデクセル構造を表す。言い換えれば、図６〜８の３つのデクセル構造を含むトリデクセルデータによってモデル化ボリュームを定義することができる。図６は、ｙ軸に沿ったデクセル構造６７を示す。図７は、ｘ軸に沿ったデクセル構造６８を示す。図８は、ｚ軸に沿ったデクセル構造６９を示す。各図上で、デクセルの直線は、それぞれの軸に対して平行である。
【００４２】
データ間で、線分の終点でのモデル化ボリュームの境界に対する外部法線ベクトルを与えることもできる。これにより、モデル化ボリュームのより精細なレンダリングが可能となる。
【００４３】
方法はまた、モデル化ボリューム上に対する彫刻操作（Ｓ２０）を提供することをも含む。彫刻操作は、システムによって提供される、モデル化ボリュームを彫刻する任意の操作である。モデル化ボリュームを彫刻することにより、ブール演算を介してモデル化ボリュームからボリュームを追加および／または除去することを意味する。したがって、彫刻操作は、モデル化ボリュームに対する少なくとも１つのボリュームブール演算の任意の組合せである。例えば、ローカルボリューム除去およびローカルボリューム追加は彫刻操作であるが、表面からの押出しは、何らかのブール演算に基づくものではないので、彫刻操作ではない。彫刻プロセスは、任意の一連の少なくとも１つの彫刻操作である。一例では、彫刻操作は、持続時間にわたってモデル化ボリュームに加えられる（引かれる）連続的ボリューム（すなわち、互いに素ではない）に関係する一連の連続するブール演算である。例えば、彫刻操作は機械加工操作を表す。
【００４４】
したがって、デクセルの集合は任意の立体を表すことができ、方法は、立体の実際の彫刻をシミュレートすることができる。方法は特に、コンピュータ支援設計システムまたはコンピュータ支援製造システムを使用するリアルタイム機械加工シミュレーションに含めることができる。言い換えれば、立体はストックでよく、方法は、切削工具によって仮想的に機械加工されるストックの形状を表示することができる。そのような場合、モデル化ボリュームはストックを表し、操作は切削操作である。この例を、仮想粘土に対する複合製造および形状彫刻などの、材料も部品に追加される他の製造工程に一般化することができる。この例を、機械設計、形状設計、建築などを含むすべての従来型立体モデリングアプリケーションに一般化することもできる。最後に、その性能により、方法は、対話式３Ｄ彫刻などのより先進的なアプリケーションを扱うことができる。最も一般的には、彫刻操作は機械加工操作を表すことができる。そのような場合、モデル化ボリュームは、機械加工操作を受ける工作物を表すことができ、したがって方法は、工作物の機械加工のシミュレーションを改善する。したがって方法は、仮想機械加工プロセスをテストするための良い基礎として働くことができる。
【００４５】
実際、方法は、彫刻操作に応答して（すなわち彫刻操作に従って）デクセルの集合を更新する（Ｓ３０）（すなわち修正する）ことをさらに含む。言い換えれば、方法は、当初提供されたデクセルの集合（Ｓ１０）に彫刻操作を適用する。更新後のデクセルの集合は、彫刻（例えば機械加工）後のオブジェクトを表す。
【００４６】
各デクセルは線分の集合を含む。モデル化ボリュームと交わる直線のすべての線分が、１つのデクセルとしてグループ化される。これにより、モデル化ボリュームの直線ごとの処理が可能となり、したがって、例えば並列処理が可能となるので、より効率的な処理が可能となる。さらに、デクセルの集合が隣接デクセルのグループに区分される。デクセルは、デクセル間の距離が所定のしきい値より低いとき、隣接すると言われる。したがって、デクセルの集合を隣接デクセル（すなわち、グループのうちの２つのデクセルが必ず隣接する）に区分することができる（すなわち、デクセルの互いに素なサブ集合に分割することができ、その再結合は、デクセルの集合全体を構成する）。第１のデクセルと第２のデクセルとの間の距離は、第１のデクセルの直線と第２のデクセルの直線との間の距離である。第１の直線と第２の直線との間の距離は、第１の直線が第２の直線からどれほど離れた位置にあるかの尺度となる任意の距離でよい。例えば、直線が平行である場合、距離は、第１の直線の点と第２の直線の点との間の最小ユークリッド距離でよい。直線が平行ではない場合、距離は、第１の直線の点と第２の直線の点との間の最小ユークリッド距離でよく、２つの点は、デクセルの集合の凸閉包に属する。
【００４７】
グループのデクセルのそれぞれに含まれる線分の最大数に応じたメモリ空間が、各グループに割り振られる。言い換えれば、グループに割り振られるメモリ空間は、グループの各デクセルに含まれる線分の最大数の関数であり、この関数は、増加関数、恐らくは線形関数である。これにより、デクセルの集合に割り振られたメモリ空間の最適化された使用が可能となる。実際、彫刻操作、特に機械加工操作を表す彫刻操作は、モデル化ボリュームに対して局所的影響を及ぼす。デクセルを近隣デクセルのグループにグループ化することにより、デクセルの集合を更新する（Ｓ３０）とき、デクセルの集合のグループごとの処理が可能となる。それによって、例を参照しながら説明するように、グループごとにメモリを割り振り、グローバル割振りメモリを最適化することが可能となる。
【００４８】
方法の実行で示唆されるハードウェアおよび／または彫刻コンテキストへの適合の際に、デクセルの集合を隣接デクセルのグループに区分することができる。言い換えれば、方法の実行のために使用されるハードウェア（プロセッサおよび／またはメモリなど）および／または彫刻コンテキスト（すなわち、方法のコンテキストに関する情報）に対して区分化を適合させることができる（すなわち、区分化はそれらに依存することができる）。例えば、１つのグループ内部の隣接デクセルの最大数は、プロセッサが実行することのできる並列スレッド数の増加関数でよい。彫刻コンテキストは、モデル化ボリュームおよび／または彫刻操作に関する情報を含むことができる。例えば、彫刻コンテキストは、モデル化ボリュームの複雑さ（例えば、モデル化ボリュームがどれだけ不規則であるかの尺度）および／または彫刻操作の複雑さ（例えば、彫刻操作を実施するために仮想的に使用される工具の幾何形状）を測定することができる。彫刻コンテキストはまた、そのような工具のサイズに関する情報をも含むことができる。例えば、１つのグループ内部の隣接デクセルの最大数は、モデル化ボリュームの複雑さ、彫刻操作の複雑さの減少関数、および／または彫刻工具のサイズの増加関数でよい。
【００４９】
次に、方法の利点を強調するために従来技術を論じる。
【００５０】
従来技術で知られるＬＤＮＩ実装の決定的な弱点は、所与の精度レベルに達するのに必要なメモリのサイズである。周知のＬＤＮＩ実装は、「フレームバッファ」および「レイヤ」を利用し、ＯｐｅｎＧＬおよびＳｈａｄｅｒｓプログラミングを使用するＧＰＵで、モデル化ボリュームを表すデクセルの集合を処理する。「フレームバッファ」は、当初はピクセルの２次元アレイとしてイメージを格納する専用にされた、ＧＰＵ内に配置されるメモリエリアである。ＧＰＧＰＵ技術は、このフレームバッファを使用して、深さ間隔（すなわち、デクセルの線分）の２次元アレイを格納する。フレームバッファの各要素は１つの線分のみを含むことを理解しなければならない。「レイヤ」は以下のように定義される。各デクセル内で、線分が深さ順序に従ってソートされる。「レイヤ」は、同一の深さ順序を有するすべての線分の集合である。
【００５１】
ＯｐｅｎＧＬおよびＳｈａｄｅｒｓプログラミングを使用する従来技術の計算は、各レイヤを格納するために完全なフレームバッファを必要とする。したがって、デクセル構造が与えられるとして、デクセルの間隔の最大数をＮmaxとすると、Ｎmax個のレイヤが計算され、同数のフレームバッファに格納される。計算するフレームバッファの大部分が非常に希薄である場合であっても、このコンテキストでのメモリ管理の剛性は、異存がない限り、性能のために、ＧＰＵボード上にモデル全体が常駐するように保つことを要求する。したがって、デクセルの集合がＮx＊Ｎy個のデクセルを含む場合、オンボードメモリは、サイズＮx＊Ｎy＊Ｎmaxのバッファを確保しなければならない。このことを図９〜１３を参照しながら示す。
【００５２】
図６のデクセル構造６７について、フレームバッファサイズは、１０＊１０の直線のグリッドに従ってＮx＊Ｎy＝１０＊１０である。少なくとも１つのデクセル（例えば、図６の円で囲ったデクセル６５）が４つの線分６０を含むので、図９に示されるように、４つのレイヤ（７２、７４、７６、および７８）がデクセルによって定義される。次に、サイズ１０＊１０のグリッドとしてフレームバッファを表現する図１０〜１３も参照し、フレームバッファがボックスに対応するグリッド上の位置およびフレームバッファに対応するレイヤに関するデクセル線分を格納する場合、×印がそのボックス内に存在する。第１のフレームバッファ８２は、線分の第１のレイヤ７２を格納し、第２のフレームバッファ８４は、線分の第２のレイヤ７４を格納し、第３のフレームバッファ８６は、線分の第３のレイヤ７６を格納し、第４のフレームバッファ８８は、線分の第４のレイヤ７８を格納する。図１０〜１３の表は、フレームバッファ８２〜８８の使用されるメモリスロットおよび未使用のメモリスロットを示す。Ｘフラグを付けたボックス８７は１つの線分を格納し、空のボックス８９は未使用メモリである。すべての４つのフレームバッファ（８２、８４、８６、８８）は、割り振られたメモリであり、大量の未使用メモリを示すことを理解しなければならない。
【００５３】
従来技術のこの例に関する、割り振られたメモリと使用されるメモリとの間のバランスは以下の通りである。すべての４つのフレームバッファに対して必要なメモリサイズはＮx＊Ｎy＊Ｎmax＝１０＊１０＊４＝４００であり、使用されるメモリは、デクセルの間隔の数である８３である。さらに、ＬＤＮＩフレームバッファの希薄なデータ表現は、レイヤのリンクリストや、デクセル／スレッドレベルの間接テーブル（ｉｎｄｉｒｅｃｔｉｏｎ ｔａｂｌｅ）などの通常の希薄な行列表現からは直接的に導出されない。実際、そのような技法は、超並列ハードウェアアーキテクチャおよび対応するプログラミング抽象化に適合されず、したがってこれにより、実行速度およびデータフローが非効率となる。
【００５４】
従来技術とは対照的に、方法は、高速かつロバストな更新（Ｓ３０）を可能にすると共に、使用するメモリ空間が比較的わずかである。実際、少なくとも１つの線分の集合をそれぞれ含むデクセルの集合として編成されるデータの構造により、並列処理が可能となる。隣接デクセルのグループへの区分化と、グループのデクセルのそれぞれに含まれる線分の最大数に応じたメモリ空間の割振りとにより、グループごとに並列処理を実行することが可能となる。彫刻操作は通常は局所的効果を有するので、これにより、並列処理の利点を獲得することが可能となると共に、従来技術でのメモリサイズ占有に関する不都合が回避される。
【００５５】
デクセルの集合を更新すること（Ｓ３０）は、彫刻操作によって影響を受ける隣接デクセルのグループを求めること、および求めたグループのそれぞれを更新することを含むことができる。言い換えれば、更新すること（Ｓ３０）により、効率が向上するように、更新時に実際に修正すべきグループが修正される。実際に、例えば計算を加速するために、隣接デクセルのどのグループが彫刻操作によって影響を受けるかを予測することは有用であることがある。
【００５６】
求めたグループのそれぞれを更新することは、それぞれのグループについて、並列処理によってそれぞれのグループのデクセルを更新することを含むことができる。これにより、より高速な更新（Ｓ３０）が可能となり、したがってデクセルの集合が表示される場合、彫刻操作を与えるユーザアクションに対するより高速な応答が可能となる。
【００５７】
並列処理は、システムによって複数のタスクを同時に実行することからなる。この方法の場合、それぞれのグループのデクセルを更新することは、それぞれのグループのデクセルのそれぞれに関する単一命令スレッドを実行することを含むことができる。したがって、それぞれのグループのデクセルを更新することは、ＳＩＭＤ（単一命令多重データ）並列処理によって実行することができる。方法を実行するシステムのプロセッサは特に、例えばシステムが１０または１００を超えるプロセッサとネットワーキングされる場合、超並列処理ユニットでよい。
【００５８】
各デクセルについて、ブール演算、オフセット、コリジョン検出などの通常のモデリング演算子は、その１次元カウンターパート、すなわち線分に対する単純な演算となる。あるデクセルの計算および更新は、別のデクセルに関する対応する演算には依拠しないので、モデルは超並列処理に良く適合する。
【００５９】
次に、ワーキンググループおよび単一命令多重データ実行を論じ、図示する。ワーキンググループおよび単一命令多重データを介して方法を実行することができる。隣接デクセルのグループはワーキンググループを構成し、更新するステップ（Ｓ３０）は、彫刻操作によって影響を受けると判定した各グループに関するＳＩＭＤ実行を含むことができる（そのような判定は、恐らくはＳＩＭＤ実行の最初のステップである）。
【００６０】
ワーキンググループおよびＳＩＭＤ（単一命令多重データ）実行はＯｐｅｎＣＬ概念である。すなわち、同一のワーキンググループに属するすべてのスレッドが、「単一命令多重データ」方式に従って挙動する。一例として、２つの入力数の最大数を出力する非常に単純なプログラムをここで考慮する。すなわち、ａおよびｂが２つの入力数であるとして、ｍａｘ（ａ，ｂ）である。
【００６１】
プログラムは以下の命令を含むことができる。
01 if(a>b)then
02 c:=a
03 else
04 c:=b
05 end if
06 return c
このプログラムは６つの命令を含む。ここで、「ｍａｘ」プログラムを３回呼び出すことによって３対の数の最大数を計算する以下の「Ｔｅｓｔ」プログラムを考慮する。
Program Test
x:=max(5,4)
y:=max(2,6)
z:=max(3,3)
end.
「Ｔｅｓｔ」プログラムの順次実行は、コンピュータが、第１の呼出しの命令１、２、５、６、第２の呼出しの命令１、３、４、５、６、および第３の呼出しの命令１、３、４、５、６を次々に実行するためのものである。この結果、１４個の命令が実行される。
【００６２】
次に、同一のワーキンググループに属する３つのトレッドが、「Ｔｅｓｔ」プログラムを実行することができる。各スレッドは、ＳＩＭＤ戦略に従って「ｍａｘ」プログラムに対する１つの呼出しを実行する。このことは、プログラム「ｍａｘ」に対するすべての３つの呼出しの命令が、異なるデータセットを処理するにも関わらず「同時に」実行されることを意味する。より厳密には、表Ｉがステップバイステッププロセスを示す。
【００６３】
【表１】
【００６４】
計算のステップ１で、ワーキンググループが、すべての３つのデータセットと共に、「ｍａｘ」プログラムの第１の命令「ｉｆ（ａ＞ｂ）ｔｈｅｎ」を実行する。ステップ２で、分岐効果は、第１のスレッドが「ｍａｘ」プログラムの命令２を実行し、第２および第３のスレッドがこの期間中待機するようなものとなる。これは、第２および第３のスレッドがａ≦ｂの状況を管理し、第１のスレッドがａ＞ｂの状況を管理するからである。ステップ３で、第２および第３のスレッドが「ｍａｘ」プログラムの命令３を実行し、第１のスレッドが待機する。これが表で示されるように続行される。下端の行は、１４個の命令を実行する順次戦略とは対照的に、３つのスレッドワーキンググループが、等価なコンピューティング時間の６個の命令を実行することによって「ｍａｘ」プログラムの３つの呼出しを実行することである。
【００６５】
明らかに、この例は、独立したデータセットと共にプログラムが実行されるとき、かつ分岐論理がある実行から別の実行に発散し過ぎないとき、同期スレッドのワーキンググループが効率的であることを示す。
【００６６】
同様に、方法は、各グループのデクセルに対してＳＩＭＤを実行することによってグループのそれぞれを更新することができる。各グループのデクセルは隣接するので、ＳＩＭＤは、ワーキンググループ（隣接デクセルのグループ）のすべてのスレッド（すなわち、隣接デクセルの前記グループのデクセル）上で適時に同様の方式で実行される可能性が高い。実際に、同一のグループのデクセルは統計的に同様であり、彫刻操作によって同様に影響を受ける。したがって、同一のグループのデクセルの更新は通常、（ほぼ）同一の操作を含む。このため、並列処理の利点が得られ、メモリ空間が節約される。
【００６７】
方法は、更新後グループのデクセルのそれぞれに含まれる線分の最大数が修正されるとき、更新後グループに割り振られるメモリ空間を適合させることをさらに含むことができる。言い換えれば、方法は、彫刻操作に応答してデクセルの集合を更新した（Ｓ３０）後に、メモリの割振りを修正することをさらに含むことができる。このことは、メモリブロックを割振り解除すること、またはメモリブロックをさらに割り振ることを含むことができる。このブロック割振り／割振り解除機構は、メモリモデルの効率を劇的に改善する。実際には、オンボードメモリのサイズが束縛されるので、このブロック割振り／割振り解除機構は、所与のメモリサイズに対してずっと良好な精度を可能にする。このブロック割振り／割振り解除機構は、性能の向上も促す。
【００６８】
それによって、方法は、（例えば、ＣＵＤＡまたはＯｐｅｎＣＬプログラミング抽象化としての）超並列ハードウェアの状況に適合されたメモリブロック割振り／割振り解除の機構を提供することができる。ワーキンググループレベル（Ｏｐｅｎ ＣＬ概念）でブロックを割振り／割振り解除することができ、間接テーブルが、それぞれのワーキンググループおよび対応するデクセルのグループについて、こうしたブロックをアドレス指定することができる。
【００６９】
ＣＵＤＡおよびＯｐｅｎＣＬ言語は、一例を参照しながら以下で論じる特徴と共に、超並列ハードウェアのためのプログラミング抽象化を提供する。
【００７０】
この例では、スレッドがワーキンググループ（ＯｐｅｎＣＬ用語）にグループ化される。すなわち、好ましくは、同一のワーキンググループに属するスレッドがＳＩＭＤ式（単一命令多重データ）に実行され、したがって分岐発散が小さいときにより効率的となる。
【００７１】
メモリは、２つの主なカテゴリに分割される。第１は、アクセスが迅速であり、単一のスレッドに対してプライベートであり、またはワーキンググループによって共有される、小さいサイズのプライベート／ローカル（ＯｐｅｎＣＬ用語）メモリである。第２は、アクセスが低速であり、すべてのスレッドから可視であり、好ましくは連続するブロックによってアクセスされる、大きいグローバルメモリエリアである。
【００７２】
更新（Ｓ３０）のあるステージで、個々のスレッドが個々のデクセルの更新を管理し、同期スレッドの「ワーキンググループ」が、ここではデクセルグループと呼ぶ近隣デクセルのグループを管理する。この例のデータ構造は、すべてのデクセルグループがｋと表す同数のデクセルを有するように設計される。同一のデクセルグループ（通常はグリッド内部の小さいサブグリッド）のデクセルの幾何学的近接は、類似の構成の可能性および必要なレイヤ数を増大させる。
【００７３】
図６の例に戻ると、この例の方法に従って、デクセル構造６７を５＊５のグリッド＝２５デクセルグループに区分することができ、各グループはｋ＝４デクセルを含む。同一のグループ内のすべてのデクセルに、前記グループのすべてのデクセルの線分の最大数に応じてますます多く、同一のメモリサイズを割り振ることができる。図１４に、デクセルグループを、それぞれの線分の最大数１４０と共に示す。
【００７４】
このデクセルグループ構造に対して割り振られるメモリサイズは、１線分デクセルの１０グループ、３線分デクセルの３グループ、２線分デクセルの１グループ、および４線分デクセルの３グループ、すなわち（１０＊１＋３＊３＋１＊２＋４＊３）＊４＝１３２メモリユニットを格納する。従来技術で必要とされる４００メモリユニットと比較して、これは、メモリ空間の特に高い向上である。
【００７５】
処理の間、同一のデクセルグループのデクセルの線分の最大数が１つ増加するとき、グローバルメモリのブロックを割り振ることができる。もちろん、このメモリブロックは線分を格納するようなサイズにされる。逆に、同一のワーキンググループ内のすべてのデクセルの間隔の最大数が減少するとき、メモリブロックテーブル内の対応するブロックを割振り解除することができる。このようにして、次の再割振りがフリーブロックを再利用することができる。したがって、これをＳＩＭＤ（同期）スレッドのグループによって最適に実施することができる。
【００７６】
この点で、グループのデクセルのそれぞれをどのように更新するかに関しては、更新するステップ（Ｓ３０）が各グループに関する並列処理によって実行されるようにＳＩＭＤを介してそのような更新を行うことができることを別にして、ほとんど述べなかった。方法は、デクセルのそれぞれを更新するための任意の方式を含むことができる。例えば、それぞれのグループのデクセルを更新することは、それぞれのグループのそれぞれのデクセルについて、それぞれのデクセルに対する彫刻操作の影響を評価し、それに応じてそれぞれのデクセルを修正することを含む。例えば、彫刻操作が切削操作である場合、そのような操作によって影響を受けるデクセルから切削容積を差し引くことができる。
【００７７】
それぞれのデクセルに対する彫刻操作の影響を評価することは、それぞれのデクセルの線分に対する彫刻操作の影響を評価することを含むことができる。言い換えれば、更新は線分レベルで行われる。実際に、彫刻操作は、デクセルの線分構造を修正することができ、例えばある線分を削除することができ、ある線分を追加することができ、かつ／またはある線分を修正することができる。
【特許請求の範囲】
【請求項１】
モデル化ボリュームを設計するコンピュータ実装方法であって、
前記モデル化ボリュームを表すデクセルの集合を提供するステップ（Ｓ１０）であって、各デクセルは、直線とモデル化ボリュームとの共通部分を表す少なくとも１つの線分の集合を含み、前記デクセルの集合が、隣接デクセルのグループに区分され、前記グループの前記デクセルのそれぞれに含まれる線分の最大数に応じたメモリ空間が、各グループに割り振られるステップと、
前記モデル化ボリュームに対する彫刻操作を提供するステップ（Ｓ２０）と、
前記彫刻操作に応答して前記デクセルの集合を更新するステップ（Ｓ３０）と
を含むことを特徴とする方法。
【請求項２】
前記デクセルの集合を更新するステップは、前記彫刻操作によって影響を受ける隣接デクセルのグループを求めるステップと、求めたグループのそれぞれを更新するステップとを含むことを特徴とする請求項１に記載の方法。
【請求項３】
求めたグループのそれぞれを更新するステップは、それぞれのグループについて、並列処理によって前記それぞれのグループの前記デクセルを更新するステップを含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記それぞれのグループの前記デクセルを更新するステップは、前記それぞれのグループのそれぞれのデクセルについて、前記それぞれのデクセルに対する前記彫刻操作の影響を評価するステップと、それに応じて前記それぞれのデクセルを修正するステップとを含むことを特徴とする請求項２または３に記載の方法。
【請求項５】
前記それぞれのデクセルに対する前記彫刻操作の影響を評価するステップは、前記それぞれのデクセルの前記線分に対する前記彫刻操作の影響を評価するステップを含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記それぞれのグループの前記デクセルを更新するステップが、ＳＩＭＤ（単一命令多重データ）並列処理によって実施されることを特徴とする請求項５に記載の方法。
【請求項７】
更新後グループの前記デクセルのそれぞれに含まれる線分の最大数が修正されるとき、前記更新後グループに割り振られた前記メモリ空間を適合させるステップをさらに含むことを特徴とする請求項２〜６のいずれかに記載の方法。
【請求項８】
前記デクセルの集合が、方法の実行で示唆されるハードウェアおよび／または彫刻コンテキストへの適合の際に、隣接デクセルのグループに区分されることを特徴とする請求項１〜７のいずれかに記載の方法。
【請求項９】
モデル化ボリュームを設計するシステムであって、請求項１〜８のいずれかに記載の方法を実行する命令がその上に記録されたメモリと、前記命令を実行する前記メモリに結合された少なくとも１つのプロセッサとを備えることを特徴とするシステム。
【請求項１０】
前記プロセッサは超並列処理ユニットであることを特徴とする請求項９に記載のシステム。
【請求項１１】
前記命令の実行を開始するのに適した少なくとも１つのＧＵＩを備えることを特徴とする請求項９または１０に記載のシステム。
【請求項１２】
ＧＵＩはＧＰＵを含み、前記プロセッサは前記ＧＰＵであることを特徴とする請求項１１に記載のシステム。
【請求項１３】
コンピュータプログラムであって、請求項１〜８のいずれかに記載の方法を実施する命令を含むことを特徴とするコンピュータプログラム。
【請求項１４】
コンピュータ可読記憶媒体であって、請求項１３に記載のコンピュータプログラムがその上に記録されたことを特徴とするコンピュータ可読記憶媒体。
【請求項１】
モデル化ボリュームを設計するコンピュータ実装方法であって、
前記モデル化ボリュームを表すデクセルの集合を提供するステップ（Ｓ１０）であって、各デクセルは、直線とモデル化ボリュームとの共通部分を表す少なくとも１つの線分の集合を含み、前記デクセルの集合が、隣接デクセルのグループに区分され、前記グループの前記デクセルのそれぞれに含まれる線分の最大数に応じたメモリ空間が、各グループに割り振られるステップと、
前記モデル化ボリュームに対する彫刻操作を提供するステップ（Ｓ２０）と、
前記彫刻操作に応答して前記デクセルの集合を更新するステップ（Ｓ３０）と
を含むことを特徴とする方法。
【請求項２】
前記デクセルの集合を更新するステップは、前記彫刻操作によって影響を受ける隣接デクセルのグループを求めるステップと、求めたグループのそれぞれを更新するステップとを含むことを特徴とする請求項１に記載の方法。
【請求項３】
求めたグループのそれぞれを更新するステップは、それぞれのグループについて、並列処理によって前記それぞれのグループの前記デクセルを更新するステップを含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記それぞれのグループの前記デクセルを更新するステップは、前記それぞれのグループのそれぞれのデクセルについて、前記それぞれのデクセルに対する前記彫刻操作の影響を評価するステップと、それに応じて前記それぞれのデクセルを修正するステップとを含むことを特徴とする請求項２または３に記載の方法。
【請求項５】
前記それぞれのデクセルに対する前記彫刻操作の影響を評価するステップは、前記それぞれのデクセルの前記線分に対する前記彫刻操作の影響を評価するステップを含むことを特徴とする請求項４に記載の方法。
【請求項６】
前記それぞれのグループの前記デクセルを更新するステップが、ＳＩＭＤ（単一命令多重データ）並列処理によって実施されることを特徴とする請求項５に記載の方法。
【請求項７】
更新後グループの前記デクセルのそれぞれに含まれる線分の最大数が修正されるとき、前記更新後グループに割り振られた前記メモリ空間を適合させるステップをさらに含むことを特徴とする請求項２〜６のいずれかに記載の方法。
【請求項８】
前記デクセルの集合が、方法の実行で示唆されるハードウェアおよび／または彫刻コンテキストへの適合の際に、隣接デクセルのグループに区分されることを特徴とする請求項１〜７のいずれかに記載の方法。
【請求項９】
モデル化ボリュームを設計するシステムであって、請求項１〜８のいずれかに記載の方法を実行する命令がその上に記録されたメモリと、前記命令を実行する前記メモリに結合された少なくとも１つのプロセッサとを備えることを特徴とするシステム。
【請求項１０】
前記プロセッサは超並列処理ユニットであることを特徴とする請求項９に記載のシステム。
【請求項１１】
前記命令の実行を開始するのに適した少なくとも１つのＧＵＩを備えることを特徴とする請求項９または１０に記載のシステム。
【請求項１２】
ＧＵＩはＧＰＵを含み、前記プロセッサは前記ＧＰＵであることを特徴とする請求項１１に記載のシステム。
【請求項１３】
コンピュータプログラムであって、請求項１〜８のいずれかに記載の方法を実施する命令を含むことを特徴とするコンピュータプログラム。
【請求項１４】
コンピュータ可読記憶媒体であって、請求項１３に記載のコンピュータプログラムがその上に記録されたことを特徴とするコンピュータ可読記憶媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図９】
【図１０】
【図１１】
【図１２】
【図１３】
【図１４】
【公開番号】特開２０１３−９７８１１（Ｐ２０１３−９７８１１Ａ）
【公開日】平成２５年５月２０日（２０１３．５．２０）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１２−２４２６２９（Ｐ２０１２−２４２６２９）
【出願日】平成２４年１１月２日（２０１２．１１．２）
【出願人】（５００１０２４３５）ダッソー システムズ (52)
【氏名又は名称原語表記】ＤＡＳＳＡＵＬＴ ＳＹＳＴＥＭＥＳ
【Ｆターム（参考）】
【公開日】平成２５年５月２０日（２０１３．５．２０）
【国際特許分類】
【出願番号】特願２０１２−２４２６２９（Ｐ２０１２−２４２６２９）
【出願日】平成２４年１１月２日（２０１２．１１．２）
【出願人】（５００１０２４３５）ダッソー システムズ (52)
【氏名又は名称原語表記】ＤＡＳＳＡＵＬＴ ＳＹＳＴＥＭＥＳ
【Ｆターム（参考）】
[ Back to top ]