複数のデクセルによって表わされるモデル化ボリュームの設計
【課題】複数のデクセルのセットによって表されるモデル化ボリュームを設計するための改良型解決法を提供する。
【解決手段】改良型解決法には、複数の始線に基づくモデル化ボリュームを表す複数のデクセルの初期セットをスカルプチャ生成するステップＳ１０と、複数の始線を精緻化することによって複数の新しい線を提供するステップＳ２０と、スカルプチャ生成プロセスを経た後の、複数の新しい線に基づくモデル化ボリュームを表す複数のデクセルの新しいセットを決定するステップＳ３０が含まれている。この方法によれば、複数のデクセルのセットによって表されるモデル化ボリュームの設計が改善される。
【解決手段】改良型解決法には、複数の始線に基づくモデル化ボリュームを表す複数のデクセルの初期セットをスカルプチャ生成するステップＳ１０と、複数の始線を精緻化することによって複数の新しい線を提供するステップＳ２０と、スカルプチャ生成プロセスを経た後の、複数の新しい線に基づくモデル化ボリュームを表す複数のデクセルの新しいセットを決定するステップＳ３０が含まれている。この方法によれば、複数のデクセルのセットによって表されるモデル化ボリュームの設計が改善される。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明はコンピュータプログラムおよびシステムの分野に関し、より詳細には複数のデクセルのセットによって表わされるモデル化されたボリューム（ｍｏｄｅｌｅｄ ｖｏｌｕｍｅ、以下、モデル化ボリューム）を設計するための方法、システムおよびプログラムに関する。
【背景技術】
【０００２】
市場には、オブジェクトを設計し、エンジニアリングし、かつ、製造するための多くのシステムおよびプログラムが提供されている。ＣＡＤは、Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ Ｄｅｓｉｇｎの頭辞語であり、例えばオブジェクトを設計するためのソフトウェア解決法に関連している。ＣＡＥは、Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ Ｅｎｇｉｎｅｅｒｉｎｇの頭辞語であり、例えば将来の製品の物理的挙動を模擬するためのソフトウェア解決法に関連している。ＣＡＭは、Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ Ｍａｎｕｆａｃｔｕｒｉｎｇの頭辞語であり、例えば製造プロセスおよび操作を定義するためのソフトウェア解決法に関連している。このようなシステムでは、グラフィカルユーザインタフェース（ＧＵＩ）は、技法の有効性に関して重要な役割を果たしている。これらの技法は、ＰＬＭ（Ｐｒｏｄｕｃｔ Ｌｉｆｅｃｙｃｌｅ Ｍａｎａｇｅｍｅｎｔ）システムの中に埋め込むことができる。ＰＬＭは、概念からその寿命が尽きるまでの製品開発のために、拡張企業の概念を超えて製品データを共有し、共通プロセスを適用し、かつ、企業知識をてこ入れするために会社を援助するビジネス戦略を意味している。
【０００３】
Ｄａｓｓａｕｌｔ Ｓｙｓｔｅｍｅｓが（ＣＡＴＩＡ、ＥＮＯＶＩＡおよびＤＥＬＭＩＡの商標の下で）提供しているＰＬＭ解決法は、製品エンジニアリング知識を系統だてるＥｎｇｉｎｅｅｒｉｎｇ Ｈｕｂ、製造エンジニアリング知識を管理するＭａｎｕｆａｃｔｕｒｉｎｇ Ｈｕｂ、および企業がＥｎｇｉｎｅｅｒｉｎｇ ＨｕｂおよびＭａｎｕｆａｃｔｕｒｉｎｇ Ｈｕｂの両方に統合し、かつ、接続することができるＥｎｔｅｒｐｒｉｓｅ Ｈｕｂを提供している。これらのすべてが相俟って、システムは、最適化製品定義、製造準備、製造およびサービスを駆動するオープンオブジェクトモデルリンキング製品、プロセス、動的知識ベース製品生成および決定支援を可能にする資源を引き渡している。
【０００４】
これらのシステムのいくつかは、複数のデクセルのセットを使用したモデル化ボリュームの表現を可能にしている。いくつかの論文または特許文書は、機械加工シミュレーションまたはインタラクティブなスカルプチャ生成のためのデクセル表現の使用を明白に提案している。
【０００５】
このような文書の例は、
− 非特許文献１
− 非特許文献２
− 非特許文献３
− 非特許文献４
− 非特許文献５
− 非特許文献６
− 特許文献１
− 特許文献２
である。
【０００６】
ＧＰＧＰＵ（Ｇｅｎｅｒａｌ−Ｐｕｒｐｏｓｅ ｃｏｍｐｕｔｉｎｇ ｏｎ Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔｓ）は、中央処理装置（ＣＰＵ）によって伝統的に処理されているアプリケーションにおける計算を実施するために、一般的にはコンピュータグラフィックのための計算のみを処理するグラフィック処理装置（ＧＰＵ）を使用する技法である。いくつかの論文に、デクセル表現のための近代のグラフィック処理装置（ＧＰＵ）の計算能力の使用が考察されている。これらの論文には、特定のメモリモデルに関連付けられるＬＤＮＩ（Ｌａｙｅｒｅｄ Ｄｅｐｔｈ−Ｎｏｒｍａｌ Ｉｍａｇｅｓ）アルゴリズムが利用されている。
【０００７】
このような論文の例は、
− 非特許文献７
− 非特許文献８
である。
【０００８】
何人かの著者は、階層的格子改良を使用して細部のレベルを管理することにより、デクセルモデルの最も単純な具体化である深さバッファモデルの改善を提案している。これは、非特許文献９に明白に提案されている。
【０００９】
しかしながら、上に挙げた解決法には、とりわけ使用者利用の観点から有効性が欠けている。この文脈においては、複数のデクセルのセットによって表されるモデル化ボリュームを設計するための改良型解決法が依然として必要である。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】米国特許第５７１０７０９号明細書
【特許文献２】米国特許第７７４７４１８号明細書
【非特許文献】
【００１１】
【非特許文献１】the paper entitled “A Virtual Sculpting System Based on Triple Dcxcl Models with Haptics”, Xiaobo Peng and Weihan Zhang, Computer-Aided Design and Applications, 2009
【非特許文献２】the paper entitled “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
【非特許文献４】the paper entitled “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
【非特許文献５】the paper entitled “Simulation of NC machining based on the dexel model: A critical analysis”, Sabine Stifter, The International Journal of Advanced Manufacturing Technology, 1995
【非特許文献６】the paper entitled “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
【非特許文献７】the paper entitled “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
【非特許文献８】the paper entitled “Layered Depth-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)
【非特許文献９】the paper entitled “Real-time, dynamic level-of-detail management for three-axis NC milling simulation”, by S.Q. Liu, S.K. Ong, Y.P. Chen, A.Y.C. Nee
【発明の概要】
【００１２】
したがって一態様によれば、モデル化ボリュームを設計するためのコンピュータ実施方法が提供される。この方法には、モデル化ボリュームへのスカルプチャ生成プロセス、複数の始線（ｉｎｉｔｉａｌ ｌｉｎｅ）、およびスカルプチャ生成プロセスを経た後の、複数の始線に基づくモデル化ボリュームを表す複数のデクセルの初期セットを提供するステップが含まれている。初期セットの個々のデクセルは、個々の始線とモデル化ボリュームとの間の交差を表す少なくとも１つの線分のセットを備えている。この方法には、次に、複数の始線を精緻化する（ｒｅｆｉｎｅ）ことによって複数の新しい線を提供するステップが含まれている。また、この方法には、スカルプチャ生成プロセスを経た後の、複数の新しい線に基づくモデル化ボリュームを表す複数のデクセルの新しいセットを決定するステップが同じく含まれている。複数のデクセルの新しいセットを決定するステップには、個々の新しい線と、スカルプチャ生成プロセスを経る前のモデル化ボリュームとの間の交差を表す少なくとも１つの線分の複数のセットを決定するステップと、次に、少なくとも１つの線分の複数の決定済みセットにスカルプチャ生成プロセスを加えるステップが含まれている。
【００１３】
この方法は、
− 複数の始線を精緻化するステップが、複数の始線の密度を高くするステップ、複数の始線の方向を変更するステップ、および／または複数の始線の一部を捨てるステップのうちの任意のステップまたはステップの組合せを含む
− 複数の始線を精緻化するステップが、スカルプチャ生成プロセスを経る前のモデル化ボリュームの少なくとも一部を拘束するボックス、ボックスの概観を提供するステップ、および所定の密度で概観の方向にボックスと交差する複数の線を描くステップを含む
− 複数のデクセルの初期セットの複数のデクセルが、それらに影響を及ぼしたスカルプチャ生成操作に関連付けられており、スカルプチャ生成プロセスが一連のスカルプチャ生成操作として提供される
− スカルプチャ生成操作が、それらが最後に影響を及ぼした複数のデクセルの複数の線分と結合している
− スカルプチャ生成操作の各々が、複数のデクセルのそれぞれの線分と結合しており、また、その前に実施された、それぞれの線分に対する影響を有するスカルプチャ生成操作の結果である
− 方法がスクリーン上にモデル化ボリュームを表示するステップを含み、また、複数の始線を精緻化するステップが、スクリーンの１ピクセル当たり最大１本の線まで複数の始線の密度を高くするステップを含み、それにより１本の線がスクリーンの個々のピクセルに関連付けられる
のうちの１つまたは複数を含むことができる。
【００１４】
さらに、上記方法を実施するための命令がその上に記録されたメモリと、メモリに結合されたプロセッサと、プロセッサに結合された、命令の実行に適した少なくとも１つのグラフィカルユーザインタフェースとを備えたＣＡＭシステムが提案される。プロセッサはＧＰＵ（Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）であってもよい。
【００１５】
さらに、上記方法を実施するための命令を含んだコンピュータプログラムが提案される。
【００１６】
さらに、上記コンピュータプログラムがその上に記録されたコンピュータ可読記憶媒体が提案される。
【図面の簡単な説明】
【００１７】
以下、本発明の実施形態について、添付の図面を参照して、非制限の例によって説明する。
【００１８】
【図１】方法の一例の流れ図を示す図である。
【図２】グラフィカルユーザインタフェースの一例を示す図である。
【図３】クライアントコンピュータシステムの一例を示す図である。
【図４】方法の例を示す図である。
【図５】方法の例を示す図である。
【図６】方法の例を示す図である。
【図７】方法の例を示す図である。
【図８】方法の例を示す図である。
【図９】方法の例を示す図である。
【図１０】方法の例を示す図である。
【発明を実施するための形態】
【００１９】
図１は、モデル化ボリュームを設計するためのコンピュータ実施方法の一例の流れ図を示したものである。この方法には、モデル化ボリュームへのスカルプチャ生成プロセス、複数の始線、および複数のデクセルの初期セットを提供するステップ（Ｓ１０）が含まれている。複数のデクセルの初期セットは、スカルプチャ生成プロセスを経た後の、複数の始線に基づくモデル化ボリュームを表している。初期セットの個々のデクセルは、個々の始線とモデル化ボリュームとの間の交差を表す少なくとも１つの線分のセットを備えている。この方法には、次に、複数の始線を精緻化することによって複数の新しい線を提供するステップ（Ｓ２０）が含まれている。この方法には、さらに、スカルプチャ生成プロセスを経た後の、複数の新しい線に基づくモデル化ボリュームを表す複数のデクセルの新しいセットを決定するステップ（Ｓ３０）が含まれている。複数のデクセルの新しいセットを決定するステップ（Ｓ３０）には、個々の新しい線と、スカルプチャ生成プロセスを経る前のモデル化ボリュームとの間の交差を表す少なくとも１つの線分の複数のセットを決定するステップ（Ｓ３１）と、次に、少なくとも１つの線分の複数の決定済みセットにスカルプチャ生成プロセスを加えるステップ（Ｓ３２）が含まれている。この方法によれば、モデル化ボリュームのデクセル表現が改良される。
【００２０】
この方法は、ＣＡＤモデル化オブジェクト（ＣＡＤ ｍｏｄｅｌｅｄ ｏｂｊｅｃｔ）を設計するプロセスの中に含むことができる。「ＣＡＤモデル化オブジェクトを設計する」とは、モデル化オブジェクトにみがきをかけるプロセスの少なくとも一部である任意のアクションまたは一連のアクションを意味している。したがってこの方法は、最初からＣＡＤモデル化オブジェクトを生成するステップを含むことができる。あるいはこの方法は、その前に生成されたＣＡＤモデル化オブジェクトを提供するステップ、および次にそのＣＡＤモデル化オブジェクトを修正するステップを含むことができる。いずれの場合においても、この方法によって設計されるモデル化ボリュームは、ＣＡＤモデル化オブジェクトまたは少なくともその一部を表すことができ、例えばＣＡＤモデル化オブジェクトによって占有される３Ｄ空間を表すことができる。この方法によれば、複数のデクセルのセットによって表されるモデル化ボリュームの設計が改善されるため、ＣＡＤモデル化オブジェクトの設計が同じくこの方法によって改善される。
【００２１】
モデル化オブジェクトは、コンピュータシステムのメモリに記憶されているデータによって画定される任意のオブジェクトである。拡張すると、「モデル化オブジェクト」という表現は、データ自体を表している。ＣＡＤモデル化オブジェクトは、ＣＡＤシステムのメモリに記憶されているデータによって画定される任意のオブジェクトである。このタイプのシステムによれば、様々な種類のデータによってモデル化オブジェクトを画定することができる。ＣＡＤシステムは、モデル化オブジェクトの図形表現に基づいてモデル化オブジェクトを少なくとも設計するのに適した、ＣＡＴＩＡなどの任意のシステムである。したがってＣＡＤモデル化オブジェクトを画定するデータは、モデル化オブジェクトを表現することができるデータからなっている（例えば幾何学データであって、例えば空間中における相対位置を含むデータ）。
【００２２】
この方法は、この方法を実施した後に、モデル化ボリュームに対応する物理的な製品を製造するステップを含むことができる製造プロセスの中に含むことができる。いずれの場合においても、この方法によって設計されるモデル化ボリュームは、製造オブジェクトを表すことができる。したがってモデル化ボリュームは、モデル化固体（つまり固体を表すモデル化オブジェクト）であってもよい。製造オブジェクトは、部品または複数の部品のアセンブリなどの製品であってもよい。この方法によればモデル化ボリュームの設計が改善されるため、製品の製造が同じくこの方法によって改善され、したがって製造プロセスの生産性が向上する。この方法は、ＤＥＬＭＩＡなどのＣＡＭシステムを使用して実施することができる。ＣＡＭシステムは、製造プロセスおよび操作を少なくとも定義し、模擬し、かつ、制御するのに適した任意のシステムである。
【００２３】
この方法はコンピュータによって実施される。それは、この方法が少なくとも１つのコンピュータまたは同様の任意のシステム上で実行されることを意味している。他に特に言及されていない限り、この方法のすべてのステップはコンピュータによって実施され、つまり使用者の介在を必要とすることなく実施される。例えば、決定ステップ（Ｓ３０）のステップは、コンピュータによって単独で実施することができ、一方、提供ステップ（Ｓ１０）のステップおよび提供ステップ（Ｓ２０）のステップは、使用者の相互作用を介して実施することができる。実際、提供ステップ（Ｓ１０）のステップは、使用者によって先行して実施することができる。したがってこの方法によれば、モデル化ボリュームを表す複数のデクセルのセットを、恐らくは使用者によって提供される（Ｓ２０）複数の新しい線の関数で自動的に修正することができる。
【００２４】
この方法のコンピュータ実施態様の典型的な例は、この目的のために適したシステムを使用してこの方法を実施することである。システムは、この方法を実施するための命令がその上に記録されたメモリを備えることができる。言い換えると、直ちに使用するためにソフトウェアが既にメモリ上に準備されている。したがってシステムは、他のソフトウェアのインストールを全く必要とすることなく、この方法を実施するのに適している。また、このようなシステムは、メモリに結合された、命令を実行するための少なくとも１つのプロセッサを備えることも可能である。言い換えると、システムは、プロセッサに結合されたメモリ上に符号化された命令を備えており、これらの命令は、方法を実施するための手段を提供している。このようなシステムは、モデル化ボリュームを設計するための有効なツールである。
【００２５】
このようなシステムはＣＡＤシステムであってもよい。システムは、ＣＡＥおよび／またはＣＡＭシステムであってもよく、また、ＣＡＤモデル化オブジェクトは、ＣＡＥモデル化オブジェクトおよび／またはＣＡＭモデル化オブジェクトであってもよい。モデル化オブジェクトは、ＣＡＤシステム、ＣＡＥシステムおよびＣＡＭシステムの任意の組合せに対応するデータによって画定することができるため、実際、これらのＣＡＤシステム、ＣＡＥシステムおよびＣＡＭシステムは、これらのうちの１つに限定されない。
【００２６】
システムは、例えば使用者が命令の実行を開始するための少なくとも１つのＧＵＩを備えることができる。特に、ＧＵＩは、使用者による提供ステップ（Ｓ１０）のステップの実施を可能にすることができる。これは、提供ステップ（Ｓ２０）に先立って実施することができる。あるいは、複数の始線を精緻化することによって複数の新しい線を使用者が提供する（Ｓ２０）際に、スカルプチャ生成プロセス、複数の始線および複数のデクセルの初期セットを検索することができる。また、ＧＵＩは、使用者によるスカルプチャ生成操作の提供（Ｓ２０）を許容することも可能である。ＧＵＩはＧＰＵを備えることができる。このような場合、プロセッサはＧＰＵであってもよい。言い換えると、この方法の少なくともいくつかのステップ、とりわけ決定ステップ（Ｓ３０）のステップを実行するプロセッサはＧＰＵであってもよい。このようなシステムは、使用者がモデル化ボリュームを設計するための有効なツールである。デクセルに基づくアルゴリズムは、超並列ハードウェアにはうってつけであるため、近代のグラフィック処理装置（ＧＰＵ）の計算能力の使用を考慮することは当然である。
【００２７】
モデル化ボリュームは３Ｄ（つまり三次元）であってもよい。これは、モデル化ボリュームは、その３Ｄ表現を可能にするデータによって画定されることを意味している。３Ｄ表現により、表されたボリュームをあらゆる角度から見ることができる。例えばモデル化ボリュームは、３Ｄで表現されると、その任意の軸の周りに、または表現が表示されるスクリーン内の任意の軸の周りに操作することができ、また、回転させることができる。これは、３Ｄモデル化ではない２Ｄアイコンを明らかに排他している。３Ｄ表現で表示することによって設計が容易になる（つまり設計者が統計的に自身のタスクを達成している速度が速くなる）。製品の設計は製造プロセスの一部であるため、したがって産業における製造プロセスがスピードアップされる。
【００２８】
図２は、典型的なＣＡＤシステムのＧＵＩの一例を示したものである。
【００２９】
ＧＵＩ２１００は、標準メニューバー２１１０、２１２０、ならびに底部ツールバー２１４０および側部ツールバー２１５０を有する典型的なＣＡＤ様インタフェースであってもよい。このようなメニューバーおよびツールバーには、複数の使用者選択可能アイコンのセットが含まれており、個々のアイコンは、当分野で知られているように１つまたは複数の操作または機能に関連付けられている。これらのアイコンのうちのいくつかは、ＧＵＩ２１００の中に表示されている３Ｄモデル化オブジェクト２０００上で編集および／または作業するために適合されたソフトウェアツールに関連付けられている。ソフトウェアツールは、複数のワークベンチに分類することができる。個々のワークベンチは、複数のソフトウェアツールのサブセットを備えている。詳細には、これらのワークベンチのうちの１つは、モデル化製品２０００の幾何学的特徴を編集するのに適した編集ワークベンチである。動作中、設計者は、例えばオブジェクト２０００の一部を予め選択し、次に適切なアイコンを選択することにより、操作（例えばスカルプチャ生成操作または寸法、色、等々の変更などの任意の他の操作）を開始し、または幾何学的な制約の編集を開始することができる。例えば、典型的なＣＡＤ操作は、スクリーン上に表示されている３Ｄモデル化オブジェクトの押抜きまたは畳み込みのモデル化である。
【００３０】
ＧＵＩは、例えば、表示されている製品２０００に関連するデータ２５００を表示することができる。図２の例では、「特徴ツリー」として表示されているデータ２５００およびそれらの３Ｄ表現２０００は、ブレーキキャリパおよびディスクを含んだブレーキアセンブリに関している。ＧＵＩは、さらに、例えばオブジェクトの３Ｄ配向を容易にするために、編集済み製品の動作のシミュレーションをトリガするために、または表示されている製品２０００の様々な属性を描写するために、様々なタイプの図形ツール２１３０、２０７０、２０８０を示すことができる。カーソル２０６０は、使用者と図形ツールとの相互作用を可能にする触覚デバイスによって制御することができる。
【００３１】
図３は、クライアントコンピュータシステム、例えば使用者のワークステーションとしてのシステムのアーキテクチャの一例を示したものである。
【００３２】
クライアントコンピュータは、内部通信バスＢＵＳ１０００に接続された中央処理装置（ＣＰＵ）１０１０、同じくＢＵＳに接続されたランダムアクセスメモリ（ＲＡＭ）１０７０を備えている。クライアントコンピュータは、さらに、ＢＵＳに接続されたビデオランダムアクセスメモリ１１００に関連付けられているグラフィック処理装置（ＧＰＵ）１１１０を備えている。ビデオＲＡＭ１１００は、当分野ではフレームバッファとしても知られている。大容量記憶装置コントローラ１０２０は、ハードドライブ１０３０などのマスメモリデバイスへのアクセスを管理している。コンピュータプログラム命令およびデータを有形の形で具体化するのに適しているマスメモリデバイスには、一例として、ＥＰＲＯＭ、ＥＥＰＲＯＭなどの半導体メモリデバイスおよびフラッシュメモリデバイス、内部ハードディスクおよび取外し可能ディスクなどの磁気ディスク、光磁気ディスクおよびＣＤ−ＲＯＭディスク１０４０を始めとするあらゆる形態の不揮発性メモリがある。上記の任意のマスメモリデバイスは、特別に設計されたＡＳＩＣ（専用集積回路）によって補うことができ、またはこれらのＡＳＩＣの中に組み込むことができる。ネットワークアダプタ１０５０は、ネットワーク１０６０へのアクセスを管理している。また、クライアントコンピュータは、カーソル制御デバイス、キーボード、等々などの触覚デバイス１０９０を含むことも可能である。カーソル制御デバイスは、図２を参照して言及したように、使用者によるスクリーン１０８０上の任意の所望の位置へのカーソルの選択的配置を可能にするためにクライアントコンピュータに使用されている。スクリーンとは、表示を実施することができる、コンピュータモニタなどの任意のサポートを意味している。さらに、カーソル制御デバイスは、使用者による様々なコマンドの選択および制御信号の入力を可能にしている。カーソル制御デバイスには、システムに制御信号を入力するための多くの信号発生デバイスが含まれている。通常、カーソル制御デバイスはマウスであってもよく、マウスのボタンは、信号を発生するために使用される。
【００３３】
システムに方法を実施させるために、コンピュータが実行するための命令を含んだコンピュータプログラムが提供されており、命令には、そのための手段が含まれている。プログラムは、例えばディジタル電子回路の中で、またはコンピュータハードウェア、ファームウェア、ソフトウェアの中で、あるいはそれらの組合せの中で実施することができる。本発明の装置は、プログラマブルプロセッサによって実行するための機械可読記憶装置の中に有形で具体化されたコンピュータプログラム製品の中で実施することができ、また、本発明の方法ステップは、入力データ上で動作し、かつ、出力を生成することによって本発明の機能を実施するための命令のプログラムを実行するプログラマブルプロセッサによって実施することができる。命令は、有利には、データ記憶システムからデータおよび命令を受け取り、かつ、データ記憶システムにデータおよび命令を転送するように結合された少なくとも１つのプログラマブルプロセッサ、少なくとも１つの入力デバイスおよび少なくとも１つの出力デバイスを含んだプログラマブルシステム上で実行することができる１つまたは複数のコンピュータプログラムの中で実施することができる。アプリケーションプログラムは、必要に応じて高水準手続き形プログラミング言語またはオブジェクト指向プログラミング言語で、あるいはアセンブリ言語または機械言語で実施することができ、また、いずれの場合においても、言語は、コンパイル済み言語または翻訳済み言語であってもよい。プログラムは、フルインストレーションプログラムであっても、または更新プログラムであってもよい。更新プログラムの場合、プログラムは、システムが方法を実施するのに適した状態になるよう、既存のＣＡＤシステムを更新する。
【００３４】
この方法には、モデル化ボリュームを表す複数のデクセルの複数のセットが利用されている。これは、モデル化ボリュームの軽い表現を可能にしている（言い換えると、モデル化ボリュームをわずかなメモリ空間を使用して表現することができる）。また、これは、容易に操作することができるモデル化ボリュームの表現を可能にしている。特に、モデル化ボリュームが複数のデクセルのセットによって表されると、複数のデクセルのセットのデータ構造のため、モデル化ボリューム上での設計操作を極めて効率的に実施することができる。実際、高い応答性および高い頑強性で設計操作を実施することができる。特に、並列処理を使用して、線毎に複数のデクセルのセット上で操作を実施することができるため、高い効率が得られる。
【００３５】
ステップ（Ｓ１０）で提供される複数のデクセルの初期セットは、複数の始線（つまり第１の複数の線）に基づく複数のデクセルの第１のセットであり、一方、複数のデクセルの新しいセットは、ステップ（Ｓ２０）で提供される第２の複数の線である複数の新しい線に基づく複数のデクセルの第２のセットである。
【００３６】
「デクセル」という用語は、「深さエレメント」に対するショートカット（ｓｈｏｒｔｃｕｔ）として知られている（「ピクセル」という用語が「ピクチャエレメント」に対するショートカットであるのと全く同様に）。デクセルの概念については、極めて多くの研究論文で言及されている。本発明による方法の文脈においては、デクセルは、少なくとも１つの線分のセット、つまり一対の３Ｄポイントを備えている。一例では、モデル化ボリュームは、少なくとも２つの線分のセットを備えた少なくとも１つのデクセルを備えている（例えば複数のデクセルの初期セットおよび／または複数のデクセルの新しいセットは、少なくとも２つの線分を備えている）。デクセルの線分は、複数の線分が存在している場合、整列していても（このような場合、デクセルはリストである）、または整列していなくてもよい。デクセルの線分は、線とモデル化ボリュームとの間の交差を表している。言い換えると、モデル化ボリュームと交差している仮想線を考察すると、デクセルは、所与の線から始まる、交差の計算から得られる複数の線分のセットである。そのため、デクセルは、複数の線に基づいている、と言われている（つまりその線分はその線上に位置している）。例えば、複数のデクセルの初期セットは複数の始線に基づいており、一方、複数のデクセルの新しいセットは複数の新しい線に基づいている。したがって、複数のデクセルの初期セットを提供するステップ（Ｓ１０）および／または複数のデクセルの新しいセットを決定するステップ（Ｓ３０）は、例えば仮想線を描くことによってこのような交差を計算するステップ、およびＢ−Ｒｅｐによって、または任意の他のボリューム表現によって最初に表すことができるモデル化ボリュームとの交差を計算するステップを含むことができる。したがって複数のデクセルのこれらのセットはモデル化ボリュームを表している。
【００３７】
複数のデクセルのこれらのセットは、コンピュータ実施データとして提供されることに留意することは重要である。したがってモデル化ボリュームの任意の表現に関して上で提供した定義および以下で提供する定義は、データ構造の観点から密接な関係を有している。例えば、線分は、一対の３Ｄ位置（例えば互いに結合している２つの３Ｄ位置）として提供することができる。３Ｄ位置自体は、関連する３Ｄフレームに関連付けられた３つの座標（例えば浮動小数点）のリストとして提供することができる。デクセルは複数の線分のセットであり、これは、複数の線分が集合構造で一体に結合していることを意味している。複数のデクセルのセットの複数のデクセルも同じく一体に結合させることができる。それら自体が少なくとも１つの線分のセットを備えている複数のデクセルのセットによってモデル化ボリュームを表すことにより、決定ステップ（Ｓ３０）を速くすることができる。
【００３８】
次に、デクセル構造６７として複数のデクセルの初期セットを提供するステップ（Ｓ１０）のステップの一例を示す図４〜６を参照して、複数のデクセルの概念について実例で説明する。複数のデクセルの新しいセットを決定するステップ（Ｓ３０）も、図４〜６の例に基づいて実施することができる。
【００３９】
モデル化ボリュームが与えられ、かつ、無限線が与えられると、デクセルは、無限線とモデル化ボリュームとの間の交差を表す複数の線分（または区間）のセットである。複数の線分のこのセットは、個々の線分の複数の境界点のセットとしてメモリに捕獲される。デクセル構造は、例えば長方形格子上に整列させることによって系統だてられている複数のデクセルのセットである（個々のデクセルは複数の線分のセットを備えている）。図４および５は、モデル化ボリューム４０を１０×１０の格子線５０と共に示したものである。この方法例には、図４に示されているように、例えばＢ−Ｒｅｐとしてモデル化ボリューム４０を提供するステップが含まれている。この方法例には、次に、図５に示されているようにモデル化ボリューム４０と交差する（少なくとも部分的に）１０×１０格子線５０を画定するステップが含まれている。この方法例には、次に、図６に示されているように複数の線分６０および／または６２の複数のセットを備えている複数のデクセル６５を計算するステップが含まれている。図には１つのデクセル６５が円で囲まれている。デクセル６５は、線５０が１つのスポットでモデル化ボリューム４０と交差しているか、または複数の個別のスポットでモデル化ボリューム４０と交差しているかどうかに応じて、複数の線分６０または１つの線分６２を備えることができる。当然、この方法は、別法としてメモリから複数のデクセル６５を検索することも可能である。いずれの場合においても、このようにしてデクセル構造６７が提供される。
【００４０】
図６は、結果として得られたデクセル構造６７を示したものである。同じ数の複数のデクセル６５をもたらすために必ずしもすべての線５０がモデル化ボリューム４０と交差しているわけではない（この例では、モデル化ボリューム４０と交差しているのは５２本の線にすぎない）ことに注意されたい（モデル化ボリューム４０と交差していない線は、実際には捨てられ、デクセルをもたらすことはない）。さらに、いくつかの線５０は、１つの線分６２を介してモデル化ボリューム４０と交差しており（例えばデクセル（２、３）またはデクセル（９、６））、他の線５０は、複数の線分６０、例えば２つの線分を介してモデル化ボリューム４０と交差しており（例えばデクセル（７、７）またはデクセル（４、７））、もしくは３つの線分を介してモデル化ボリューム４０と交差しており（デクセル（２、８）またはデクセル（５、８））、または４つの線分を介してモデル化ボリューム４０と交差している（デクセル（２、９）またはデクセル（４、９））。結果として得られたデクセル構造６７には、５２個のデクセル６５が含まれており、そのうちの３６個のデクセル６５は１つの線分６２を備えており、６個のデクセル６５は２つの線分６０を備えており、５個のデクセル６５は３つの線分６０を備えており、また、５個のデクセルは４つの線分６０を備えている。
【００４１】
（Ｓ１０）で提供される（または（Ｓ３０）で決定される）複数のデクセルのセットは、トライデクセル構造であってもよい。トライデクセル構造は、通常、ｘ軸に対して平行のデクセル構造、ｙ軸に対して平行のデクセル構造およびｚ軸に対して平行のデクセル構造の３つのデクセル構造を備えることによって画定される。この方法は、任意の時間におけるモデル化ボリューム、例えば提供ステップ（Ｓ２０）および決定ステップ（Ｓ３０）の間のモデル化ボリュームの図形表現を表示するステップを含むことができる。表示するステップは、複数のデクセルのセット（いつ表示するかに応じて複数のデクセルの初期セットまたは複数のデクセルの新しいセット）に基づくことができる。トライデクセル構造は、その「観察方向」依存性が小さいため、良好な表示を提供する。トライデクセル構造は、とりわけ、使用者が視点を変更した場合により正確な表示を提供する。
【００４２】
図６〜８は、同じモデル化ボリュームを表すデクセル構造をそれぞれ示したものである。言い換えると、モデル化ボリュームは、図６〜８の３つのデクセル構造を含んだトライデクセルデータによって画定することができる。図６は、ｙ軸に沿ったデクセル構造６７を示したものである。図７は、ｘ軸に沿ったデクセル構造６８を示したものである。図８は、ｚ軸に沿ったデクセル構造６９を示したものである。個々の図では、複数のデクセルの複数の線は、それぞれの軸に対して平行である。
【００４３】
また、線分の端点におけるモデル化ボリュームの境界に対する外部法線ベクトルをデータの中に提供することも可能である。それによりモデル化ボリュームをより鮮明に表現することができる。
【００４４】
また、この方法には、モデル化ボリュームへのスカルプチャ生成プロセスを提供するステップが含まれている。スカルプチャ生成プロセスは、任意の一連の少なくとも１つのスカルプチャ生成操作である。スカルプチャ生成操作は、モデル化ボリュームをスカルプチャ生成するためのシステムによって提供される任意の操作である。モデル化ボリュームをスカルプチャ生成することは、ブール演算によってモデル化ボリュームにボリュームを加え、および／またはモデル化ボリュームからボリュームを除去することを意味している。したがってスカルプチャ生成操作は、モデル化ボリュームに対する少なくとも１つのボリュームブール演算の任意の組合せである。例えば局所ボリューム除去および局所ボリューム追加はスカルプチャ生成操作であり、一方、表面からの押出しは、ブール演算には全く基づいていないため、スカルプチャ生成操作ではない。一例では、スカルプチャ生成操作は、時間継続期間の間、モデル化ボリュームに追加される（またはモデル化ボリュームから除去される）連続ボリューム（つまり解体されないボリューム）を必要とする一連の連続するブール演算である。例えばスカルプチャ生成操作は、機械加工操作を表している。
【００４５】
したがって複数のデクセルのセットは任意の固体を表すことができ、また、スカルプチャ生成プロセスは、固体の実際のスカルプチャ生成を模擬することができる。この方法は、とりわけ、計算機援用設計システムを使用した実時間機械加工シミュレーションに含むことができる。言い換えると、固体は原料であってもよく、また、方法は、切断工具によって仮想的に機械加工されている原料の形状を表示することができる。このような場合、モデル化ボリュームは原料を表し、また、プロセスは切断プロセスである。この例は、複合製造および仮想粘土の形状のスカルプチャ生成など、一部品に同じく材料が加えられる他の製造プロセスに一般化することができる。この例は、機械設計、形状設計、建設建築物、等々を始めとする従来のあらゆる固体モデル化アプリケーションにも一般化することができる。最後に、この方法は、その性能能力のため、インタラクティブな３Ｄスカルプチャ生成などのより精巧なアプリケーションを取り扱うことができる。最も一般的には、スカルプチャ生成操作は機械加工操作を表すことができる。このような場合、モデル化ボリュームは、機械加工操作が施されているワークピースを表すことができ、したがってこの方法によれば、ワークピースの機械加工のシミュレーションが改善される。したがってこの方法は、仮想機械加工プロセスを試験するための良好な基礎として働くことができる。
【００４６】
実際、この方法には、さらに、複数の始線を精緻化する（つまり使用者の要求に応じて修正する）ことによって複数の新しい線を提供するステップ（Ｓ２０）、およびスカルプチャ生成プロセスを経た後の、複数の新しい線に基づくモデル化ボリュームを表す複数のデクセルの新しいセットを決定するステップ（Ｓ３０）が含まれている。言い換えると、この方法は、複数の新しい線にスカルプチャ生成プロセスを加え、または、さらに言い換えると、この方法は、スカルプチャ生成プロセスに従って、複数の新しい線に基づく複数のデクセルのセットによって画定されるモデル化ボリュームのスカルプチャ生成の結果を決定する。複数のデクセルの新しいセットは、複数の線の精緻化された後のセットに基づくスカルプチャ生成（例えば機械加工）後のオブジェクトを表している。したがってこの方法によれば、スカルプチャ生成プロセスを経た後のモデル化ボリュームの表現を改良された表現に向けて修正することができる。
【００４７】
個々のデクセルは、複数の線分のセットを備えている。モデル化ボリュームと交差する線のすべての線分は、１つのデクセルに分類される。これは線毎に可能であり、したがって、例えば並列処理が可能であるため、モデル化ボリュームのより有効な処理が可能である。実際、この方法は、線毎の並列処理によって実行することができる。
【００４８】
並列処理は、複数のタスクをシステムによって同時に実施するステップからなっている。この方法の場合、複数のデクセルの新しいセットを決定するステップ（Ｓ３０）は、複数の新しい線の各々に対して単一命令スレッドを実行するステップを含むことができる。したがって複数のデクセルの新しいセットを決定するステップ（Ｓ３０）は、ＳＩＭＤ（Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ Ｍｕｌｔｉｐｌｅ Ｄａｔａ）並列処理によって実施することができる。この方法を実行するシステムのプロセッサは、例えばシステムが１０個または１００個を超えるプロセッサでネットワーク化される場合、とりわけ超並列処理装置であってもよい。
【００４９】
一例では、この方法には、使用者によって実施される機械加工シミュレーションフェーズが含まれている（またはこの方法は、機械加工シミュレーションフェーズ後に実施される）。常に、複数のデクセルのセットは、それが示しているように、任意の固体、例えばワークピースを表すモデル化ボリュームの表現である。機械加工シミュレーションフェーズでは、使用者は、複数のデクセルの「オリジン」セットにスカルプチャ生成プロセスを加える。複数のデクセルの「オリジン」セットは、メモリから検索することができ、または複数の「オリジン」線のセットを、基準ボリューム、例えば原料、例えば図４〜８を参照して上で説明したＢ−Ｒｅｐとして保存されている原料と交差させることによって検索することができる。複数のデクセルの「オリジン」セットにスカルプチャ生成プロセスを加えるステップは、任意の知られている手順に従って実施することができる。例えば、スカルプチャ生成プロセスに切断操作が含まれている場合、影響を受けるデクセルは、その複数の線分のうちの１つまたは複数を控除することができ、またはその複数の線分のうちの１つまたは複数を短くすることができる。一方、スカルプチャ生成プロセスに材料追加操作が含まれている場合、影響を受けるデクセルは、その複数の線分のうちの１つまたは複数を長くするか、または１つまたは複数の新しい線分を加えることができる。複数のデクセルの「オリジン」セットにスカルプチャ生成プロセスを加えることによって最終的には複数のデクセルのセットが修正され、それにより複数のデクセルの初期セットに到達する。また、スカルプチャ生成プロセスおよび基準モデル化ボリューム（例えばＢ−Ｒｅｐまたは複数のデクセルのオリジンセット）に対するデータが節約される。
【００５０】
この時点で、使用者（恐らくは同じ使用者、または他の使用者）は、この方法を実施することができる。例えば使用者は、複数のデクセルの初期セットを検索することができる。このようなデータから複数の始線を決定することができる。あるいは複数の始線を記憶しておくことも可能であり、また、この方法は、それらを直接検索するステップを含むことができる。また、この方法には、機械加工フェーズのスカルプチャ生成プロセスを提供するステップが含まれている。言い換えると、モデル化ボリュームに施されたスカルプチャ生成プロセス（基準ボリュームから複数のデクセルの初期セットに到達するために）を表すデータが提供される。それにより、モデル化オブジェクトのスカルプチャ生成履歴をいつでも検索することができる。複数のデクセルの初期セットは、使用者に表示することができる。
【００５１】
次に、この方法は、複数の始線を精緻化することによって複数の新しい線を提供する（Ｓ２０）。複数の始線の精緻化は、モデル化ボリュームの表現（このような表現は、この時点における複数のデクセルの初期セットである）を修正するために使用者によって実施される任意の要求であってもよい。複数の始線を精緻化するステップは、複数の始線の密度（つまり単位ボリューム当たりの数）を高くするステップ、複数の始線（のうちの少なくとも一部）の方向を変更するステップ、および／または複数の始線の一部を捨てる（つまり削除する）ステップのうちの任意のステップまたはステップの組合せを含むことができる。言い換えると、使用者はモデル化ボリュームの新しい表現を要求し、また、この方法は、複数の新しい線を提供してモデル化ボリュームと交差させることによってこのような要求を処理している。ステップ（Ｓ３０）で新しい複数のデクセルが決定され、また、新しい表現を使用者に表示することができる。したがって使用者の要求に応じてモデル化ボリュームの表現を効果的に修正することができる。したがって延いては、使用者に表示されたモデル化ボリュームの表現をオンデマンドで修正することができる。したがって例えば他の機械加工シミュレーションフェーズのための使用者の作業を容易にすることができる。
【００５２】
例えば使用者はズームを要求することができる。このような場合、この方法は、要求されたズーミングゾーンに対応するモデル化ボリュームのゾーンを選択することができ、そのゾーンと交差しない複数の始線を捨てることができる。この方法は、さらに、そのゾーンと交差する複数の線の密度を高くすることができ、それにより複数の新しい線がもたらされる。また、この方法は、視点（ディスプレイの）を修正するステップを含むことも可能であり、したがってその新しい視線に従って導かれるよう、複数の始線の方向を修正するステップを含むことも可能である。そのため、とりわけスクリーン上のモデル化ボリュームの投影の境界でのより鮮明な表現が可能である。
【００５３】
また、使用者は、スカルプチャ生成プロセスの高品位視覚化をいつでも要求することができる。このような場合、この方法は、線の数を増やすステップを含むことができ、例えば１ピクセル当たり最大１本の線まで増やすステップを含むことができる。例えばスクリーンの個々のピクセルに１本の線を関連付けることができる。言い換えると、１本の線がスクリーンの個々のピクセルを通過しており、モデル化ボリュームと交差することができる。したがって最適数の線を使用して最も鮮明な表示が可能である。
【００５４】
この方法によれば、スカルプチャ生成プロセスを経た後の、複数の新しい線に基づくモデル化ボリュームを表す複数のデクセルの新しいセットが決定される（Ｓ３０）。これは、複数の新しい線と基準ボリューム（つまり処理されていないモデル化ボリューム）との交わりを決定し、つまり個々の新しい線と、スカルプチャ生成プロセスを経る前のモデル化ボリュームとの間の交差を表す少なくとも１つの線分の複数のセットを決定し（Ｓ３１）、次に少なくとも１つの線分の複数の決定済みセットにスカルプチャ生成プロセスを加える（Ｓ３２）ことによって実施することができる（ちょうど上で説明したように、任意の知られている方法に従って）。
【００５５】
スカルプチャ生成プロセスに対するデータおよびスカルプチャ生成プロセスを経る前のモデル化ボリュームに対するデータなどの重要なデータを維持することにより、この方法は、モデル化ボリュームを表す複数のデクセルのセットを精緻化することができ、また、例えばそれにより、複数のデクセルのセットに基づいて、効果的な方法でいつでもモデル化ボリュームの表示を改良することができる。実際、この方法は、排他的に複数の新しい線を提供することができ、また、次に、複数のデクセルを画定している複数の線分の複数のセットに対して、これらの複数の新しい線に対する操作を実施してこれらの複数の新しい線を少なくすることができる。これにより、プロセッサの観点から、高い効率が提供される。また、この精緻化は高度に頑丈であり、かつ、使用者の要求に高度に応答する（この方法の実行は安全で、かつ、高速である）。これは、モデル化ボリュームを使用者に表示する場合にとりわけ有利であり、また、表示を実時間で修正するために使用者が複数の新しい線を提供する場合にとりわけ有利である。
【００５６】
複数の始線の精緻化は、使用者のアクションによって実施することができ、例えば複数のデクセルの初期セットの図形表示との使用者との相互作用の結果として実施することができる。例えば、複数の始線を精緻化するステップには、スカルプチャ生成プロセスを経る前のモデル化ボリュームの少なくとも一部を拘束するボックス、ボックスの概観を提供するステップ、および所定の密度で概観の方向にボックスと交差する複数の線を描くステップを含むことができる。ボックスは、一般的には、モデル化ボリュームの少なくとも一部を拘束する平行六面体、球または任意のボリュームであってもよい。例えば使用者は、ある観点から、システムの触覚デバイスを使用して、例えば１つまたは複数のカメラの位置および／または配向を画定することによって選択することができ、それによりこの方法は、対応するボックスを自動的に提供する。ところで、ボックスの概観は、恐らくは（例えば同じ）使用者のアクションによって、またはそうではなくても画定することができる。「概観」とは遠景を意味しており、この遠景に従ってモデル化ボリュームが表示される。したがってボックスと交差する複数の線を描く（つまり複数の線を引く）ステップは、その概観の方向に実施することができる（つまり描かれる個々の新しい線は、オブジェクトが観察される方向に対応させることができる）。言い換えると、これらの線は、モデル化ボリュームの複数の点がスクリーン上に投影される方向に沿って描かれる。これらの線は、平行であっても、または平行でなくてもよいことに留意されたい。概観の方向は、実際、単一であってもよいが、例えば円錐遠景である場合、複数であってもよい。いずれの場合においても、これらの線は、必ず、その概観によって強いられる方向に沿って描かれる（この方向は、恐らく線毎に異なっている）。
【００５７】
複数のデクセルの初期セットの複数のデクセルは、それらに影響を及ぼしたスカルプチャ生成操作に関連付けられることができる。このような場合、スカルプチャ生成プロセスは、一連の前述のスカルプチャ生成操作として提供される（例えばスカルプチャ生成操作が実施されるシーケンスに関する情報も恐らく記憶される）。言い換えると、複数のデクセルの初期セットのために提供されるデータは、複数のデクセルの各々に影響を及ぼしたスカルプチャ生成操作、つまりデクセル幾何学を修正したスカルプチャ生成操作に関する情報を含むことができる。したがって加えるステップ（Ｓ３２）を有効に実施することができる。実際、提供ステップ（Ｓ２０）に引き続いて、複数の始線のうちのいくつかを維持することができる。複数のデクセルに対するスカルプチャ生成操作、または等価的にこのような複数のデクセルに対応する複数の線に対するスカルプチャ生成操作を関連させることにより、この方法は、一連のすべてのスカルプチャ生成操作の代わりに、維持されている複数の始線に関連付けられている一連のスカルプチャ生成操作としてスカルプチャ生成プロセスを加えることができる（Ｓ４０）。
【００５８】
スカルプチャ生成操作は、それらが最後に影響を及ぼした複数のデクセルの複数の線分に結合することができる。言い換えると、ステップ（Ｓ１０）で提供されるデータには、スカルプチャ生成操作と複数のデクセルの複数の線分との間のリンクが含まれており、それによりそれらの複数の線分を介して複数のデクセルに対するスカルプチャ生成操作が結合される。これらの線分は、前記スカルプチャ生成操作によって影響される最後の線分である。
【００５９】
あるいはスカルプチャ生成操作の各々は、複数のデクセルのそれぞれの線分と結合しており、また、その前に実施された、それぞれの線分に対する影響を有するスカルプチャ生成操作の結果である。言い換えると、「合成」操作を提供するためにいくつかのスカルプチャ生成操作が組み合わされる。それによりメモリが節約され、また、その前に実施されたスカルプチャ生成操作が、複数のデクセルに対する同じ影響を最適化された方法でもたらす単一のスカルプチャ生成操作として記憶される。したがって加えるステップ（Ｓ３２）のステップは、より迅速に実施することができる。
【００６０】
デクセル線分の個々の末端は、基本操作基準欄（例えば整数）を備えることができる。例えば機械加工シミュレーションの場合、基本操作基準は、結合（工具、例えば切断工具、または材料追加ツール、および軌道の要素）に向かう基準である。シミュレーション中にデクセル線分の末端が更新されると、基準欄は、その更新を誘導したスカルプチャ生成プロセス中の対応する基本操作基準として更新される。言い換えると、個々の線分の末端は、そのトリミング操作を示している。
【００６１】
したがって加えるステップ（Ｓ３２）は、初期格子からの初期化を計算し、次に、表されている固体の現在の状態の境界に実際に寄与しているスカルプチャ生成操作、一般的にはブール演算のサブセットのみを利用することによって加速される。これは、現在の固体の状態がこの方法のオプションである極めて多くのスカルプチャ生成操作をもたらす場合にとりわけ有利である。例えば機械加工シミュレーションは、通常、スイープされた固体を使用して何百万もの局所ブール演算によって得られる固体状態を取り扱うことができる。
【００６２】
有効な精緻化手順を任意の微小格子、したがって細かい格子に対して実施することができるため、オンデマンドで、ゆとりのある応答時間内で任意の精度が提供される。実際には、これは、局部的に正確なズーム、つまり合理的な計算時間で精緻化された計算を可能にしている。
【００６３】
次に、この方法の一例を説明する。
【００６４】
スカルプチャ生成プロセスが与えられ、そのスカルプチャ生成プロセスがある特定のポイントまでその前に実行されている基準格子が与えられ、かつ、ボックスが与えられると、精緻化手順は、その与えられたボックス内のより細かい格子フィッティングに対してもう一度そのスカルプチャ生成プロセスを実行する。ボックスは、使用者によって画定された新しいズームおよび視点を捕獲する。これを効果的に実行するために、手順は、以下のステップを実施する。
【００６５】
１．ボックスに属している複数の線分端点のセットが収集され、そこから２種類の情報が集められる。第１の種類は結果の幾何学近似値であり、第２の種類は、収集された複数のデクセルの末端に関連付けられている複数の基本操作基準のセットである。
【００６６】
２．より細かい格子は、収集された近似幾何学から初期化される。機械加工操作などの負のブール演算（集合差）の場合は、近似値（を含んだ）上部、または正のブール演算（和集合、ミンコフスキー和、等々）の場合は下部近似値（近似値が含まれている）。
【００６７】
３．収集された基本操作基準に対応するスカルプチャ生成プロセスのサブセットが、細かい格子に対して実行される。機械加工シミュレーションの場合、デクセル線分の収集されたいくつかの末端がそのことを言及している場合、このステップには、初期固体を初期化するステップを含むことができ、また、収集されたすべての軌道要素を再生する。
【００６８】
より細かい格子は、通常、基準格子の微小サブセット上で実施することができるため、実行しなければならない複数の基本操作のセットは、全シナリオよりはるかに小さくしなければならないようである。図９〜１０を参照すると、より細かい格子に対応するボックスは、軸系に対して平行ではない平行六面体９０であっても、または精緻化の目的が局所視角化（ズーム）である場合、切頭体１００であってもよい。ボックスが切頭体である場合、格子内の複数の新しい線１０２は、所与の方向に対して平行ではなく、円錐遠景に対して好都合である。図から分かるように、複数の新しい線９２または１０２は、複数の初期デクセル９４および１０４とは異なる方向のデクセルであってもよい。
【技術分野】
【０００１】
本発明はコンピュータプログラムおよびシステムの分野に関し、より詳細には複数のデクセルのセットによって表わされるモデル化されたボリューム（ｍｏｄｅｌｅｄ ｖｏｌｕｍｅ、以下、モデル化ボリューム）を設計するための方法、システムおよびプログラムに関する。
【背景技術】
【０００２】
市場には、オブジェクトを設計し、エンジニアリングし、かつ、製造するための多くのシステムおよびプログラムが提供されている。ＣＡＤは、Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ Ｄｅｓｉｇｎの頭辞語であり、例えばオブジェクトを設計するためのソフトウェア解決法に関連している。ＣＡＥは、Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ Ｅｎｇｉｎｅｅｒｉｎｇの頭辞語であり、例えば将来の製品の物理的挙動を模擬するためのソフトウェア解決法に関連している。ＣＡＭは、Ｃｏｍｐｕｔｅｒ−Ａｉｄｅｄ Ｍａｎｕｆａｃｔｕｒｉｎｇの頭辞語であり、例えば製造プロセスおよび操作を定義するためのソフトウェア解決法に関連している。このようなシステムでは、グラフィカルユーザインタフェース（ＧＵＩ）は、技法の有効性に関して重要な役割を果たしている。これらの技法は、ＰＬＭ（Ｐｒｏｄｕｃｔ Ｌｉｆｅｃｙｃｌｅ Ｍａｎａｇｅｍｅｎｔ）システムの中に埋め込むことができる。ＰＬＭは、概念からその寿命が尽きるまでの製品開発のために、拡張企業の概念を超えて製品データを共有し、共通プロセスを適用し、かつ、企業知識をてこ入れするために会社を援助するビジネス戦略を意味している。
【０００３】
Ｄａｓｓａｕｌｔ Ｓｙｓｔｅｍｅｓが（ＣＡＴＩＡ、ＥＮＯＶＩＡおよびＤＥＬＭＩＡの商標の下で）提供しているＰＬＭ解決法は、製品エンジニアリング知識を系統だてるＥｎｇｉｎｅｅｒｉｎｇ Ｈｕｂ、製造エンジニアリング知識を管理するＭａｎｕｆａｃｔｕｒｉｎｇ Ｈｕｂ、および企業がＥｎｇｉｎｅｅｒｉｎｇ ＨｕｂおよびＭａｎｕｆａｃｔｕｒｉｎｇ Ｈｕｂの両方に統合し、かつ、接続することができるＥｎｔｅｒｐｒｉｓｅ Ｈｕｂを提供している。これらのすべてが相俟って、システムは、最適化製品定義、製造準備、製造およびサービスを駆動するオープンオブジェクトモデルリンキング製品、プロセス、動的知識ベース製品生成および決定支援を可能にする資源を引き渡している。
【０００４】
これらのシステムのいくつかは、複数のデクセルのセットを使用したモデル化ボリュームの表現を可能にしている。いくつかの論文または特許文書は、機械加工シミュレーションまたはインタラクティブなスカルプチャ生成のためのデクセル表現の使用を明白に提案している。
【０００５】
このような文書の例は、
− 非特許文献１
− 非特許文献２
− 非特許文献３
− 非特許文献４
− 非特許文献５
− 非特許文献６
− 特許文献１
− 特許文献２
である。
【０００６】
ＧＰＧＰＵ（Ｇｅｎｅｒａｌ−Ｐｕｒｐｏｓｅ ｃｏｍｐｕｔｉｎｇ ｏｎ Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔｓ）は、中央処理装置（ＣＰＵ）によって伝統的に処理されているアプリケーションにおける計算を実施するために、一般的にはコンピュータグラフィックのための計算のみを処理するグラフィック処理装置（ＧＰＵ）を使用する技法である。いくつかの論文に、デクセル表現のための近代のグラフィック処理装置（ＧＰＵ）の計算能力の使用が考察されている。これらの論文には、特定のメモリモデルに関連付けられるＬＤＮＩ（Ｌａｙｅｒｅｄ Ｄｅｐｔｈ−Ｎｏｒｍａｌ Ｉｍａｇｅｓ）アルゴリズムが利用されている。
【０００７】
このような論文の例は、
− 非特許文献７
− 非特許文献８
である。
【０００８】
何人かの著者は、階層的格子改良を使用して細部のレベルを管理することにより、デクセルモデルの最も単純な具体化である深さバッファモデルの改善を提案している。これは、非特許文献９に明白に提案されている。
【０００９】
しかしながら、上に挙げた解決法には、とりわけ使用者利用の観点から有効性が欠けている。この文脈においては、複数のデクセルのセットによって表されるモデル化ボリュームを設計するための改良型解決法が依然として必要である。
【先行技術文献】
【特許文献】
【００１０】
【特許文献１】米国特許第５７１０７０９号明細書
【特許文献２】米国特許第７７４７４１８号明細書
【非特許文献】
【００１１】
【非特許文献１】the paper entitled “A Virtual Sculpting System Based on Triple Dcxcl Models with Haptics”, Xiaobo Peng and Weihan Zhang, Computer-Aided Design and Applications, 2009
【非特許文献２】the paper entitled “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
【非特許文献４】the paper entitled “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
【非特許文献５】the paper entitled “Simulation of NC machining based on the dexel model: A critical analysis”, Sabine Stifter, The International Journal of Advanced Manufacturing Technology, 1995
【非特許文献６】the paper entitled “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
【非特許文献７】the paper entitled “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
【非特許文献８】the paper entitled “Layered Depth-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)
【非特許文献９】the paper entitled “Real-time, dynamic level-of-detail management for three-axis NC milling simulation”, by S.Q. Liu, S.K. Ong, Y.P. Chen, A.Y.C. Nee
【発明の概要】
【００１２】
したがって一態様によれば、モデル化ボリュームを設計するためのコンピュータ実施方法が提供される。この方法には、モデル化ボリュームへのスカルプチャ生成プロセス、複数の始線（ｉｎｉｔｉａｌ ｌｉｎｅ）、およびスカルプチャ生成プロセスを経た後の、複数の始線に基づくモデル化ボリュームを表す複数のデクセルの初期セットを提供するステップが含まれている。初期セットの個々のデクセルは、個々の始線とモデル化ボリュームとの間の交差を表す少なくとも１つの線分のセットを備えている。この方法には、次に、複数の始線を精緻化する（ｒｅｆｉｎｅ）ことによって複数の新しい線を提供するステップが含まれている。また、この方法には、スカルプチャ生成プロセスを経た後の、複数の新しい線に基づくモデル化ボリュームを表す複数のデクセルの新しいセットを決定するステップが同じく含まれている。複数のデクセルの新しいセットを決定するステップには、個々の新しい線と、スカルプチャ生成プロセスを経る前のモデル化ボリュームとの間の交差を表す少なくとも１つの線分の複数のセットを決定するステップと、次に、少なくとも１つの線分の複数の決定済みセットにスカルプチャ生成プロセスを加えるステップが含まれている。
【００１３】
この方法は、
− 複数の始線を精緻化するステップが、複数の始線の密度を高くするステップ、複数の始線の方向を変更するステップ、および／または複数の始線の一部を捨てるステップのうちの任意のステップまたはステップの組合せを含む
− 複数の始線を精緻化するステップが、スカルプチャ生成プロセスを経る前のモデル化ボリュームの少なくとも一部を拘束するボックス、ボックスの概観を提供するステップ、および所定の密度で概観の方向にボックスと交差する複数の線を描くステップを含む
− 複数のデクセルの初期セットの複数のデクセルが、それらに影響を及ぼしたスカルプチャ生成操作に関連付けられており、スカルプチャ生成プロセスが一連のスカルプチャ生成操作として提供される
− スカルプチャ生成操作が、それらが最後に影響を及ぼした複数のデクセルの複数の線分と結合している
− スカルプチャ生成操作の各々が、複数のデクセルのそれぞれの線分と結合しており、また、その前に実施された、それぞれの線分に対する影響を有するスカルプチャ生成操作の結果である
− 方法がスクリーン上にモデル化ボリュームを表示するステップを含み、また、複数の始線を精緻化するステップが、スクリーンの１ピクセル当たり最大１本の線まで複数の始線の密度を高くするステップを含み、それにより１本の線がスクリーンの個々のピクセルに関連付けられる
のうちの１つまたは複数を含むことができる。
【００１４】
さらに、上記方法を実施するための命令がその上に記録されたメモリと、メモリに結合されたプロセッサと、プロセッサに結合された、命令の実行に適した少なくとも１つのグラフィカルユーザインタフェースとを備えたＣＡＭシステムが提案される。プロセッサはＧＰＵ（Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）であってもよい。
【００１５】
さらに、上記方法を実施するための命令を含んだコンピュータプログラムが提案される。
【００１６】
さらに、上記コンピュータプログラムがその上に記録されたコンピュータ可読記憶媒体が提案される。
【図面の簡単な説明】
【００１７】
以下、本発明の実施形態について、添付の図面を参照して、非制限の例によって説明する。
【００１８】
【図１】方法の一例の流れ図を示す図である。
【図２】グラフィカルユーザインタフェースの一例を示す図である。
【図３】クライアントコンピュータシステムの一例を示す図である。
【図４】方法の例を示す図である。
【図５】方法の例を示す図である。
【図６】方法の例を示す図である。
【図７】方法の例を示す図である。
【図８】方法の例を示す図である。
【図９】方法の例を示す図である。
【図１０】方法の例を示す図である。
【発明を実施するための形態】
【００１９】
図１は、モデル化ボリュームを設計するためのコンピュータ実施方法の一例の流れ図を示したものである。この方法には、モデル化ボリュームへのスカルプチャ生成プロセス、複数の始線、および複数のデクセルの初期セットを提供するステップ（Ｓ１０）が含まれている。複数のデクセルの初期セットは、スカルプチャ生成プロセスを経た後の、複数の始線に基づくモデル化ボリュームを表している。初期セットの個々のデクセルは、個々の始線とモデル化ボリュームとの間の交差を表す少なくとも１つの線分のセットを備えている。この方法には、次に、複数の始線を精緻化することによって複数の新しい線を提供するステップ（Ｓ２０）が含まれている。この方法には、さらに、スカルプチャ生成プロセスを経た後の、複数の新しい線に基づくモデル化ボリュームを表す複数のデクセルの新しいセットを決定するステップ（Ｓ３０）が含まれている。複数のデクセルの新しいセットを決定するステップ（Ｓ３０）には、個々の新しい線と、スカルプチャ生成プロセスを経る前のモデル化ボリュームとの間の交差を表す少なくとも１つの線分の複数のセットを決定するステップ（Ｓ３１）と、次に、少なくとも１つの線分の複数の決定済みセットにスカルプチャ生成プロセスを加えるステップ（Ｓ３２）が含まれている。この方法によれば、モデル化ボリュームのデクセル表現が改良される。
【００２０】
この方法は、ＣＡＤモデル化オブジェクト（ＣＡＤ ｍｏｄｅｌｅｄ ｏｂｊｅｃｔ）を設計するプロセスの中に含むことができる。「ＣＡＤモデル化オブジェクトを設計する」とは、モデル化オブジェクトにみがきをかけるプロセスの少なくとも一部である任意のアクションまたは一連のアクションを意味している。したがってこの方法は、最初からＣＡＤモデル化オブジェクトを生成するステップを含むことができる。あるいはこの方法は、その前に生成されたＣＡＤモデル化オブジェクトを提供するステップ、および次にそのＣＡＤモデル化オブジェクトを修正するステップを含むことができる。いずれの場合においても、この方法によって設計されるモデル化ボリュームは、ＣＡＤモデル化オブジェクトまたは少なくともその一部を表すことができ、例えばＣＡＤモデル化オブジェクトによって占有される３Ｄ空間を表すことができる。この方法によれば、複数のデクセルのセットによって表されるモデル化ボリュームの設計が改善されるため、ＣＡＤモデル化オブジェクトの設計が同じくこの方法によって改善される。
【００２１】
モデル化オブジェクトは、コンピュータシステムのメモリに記憶されているデータによって画定される任意のオブジェクトである。拡張すると、「モデル化オブジェクト」という表現は、データ自体を表している。ＣＡＤモデル化オブジェクトは、ＣＡＤシステムのメモリに記憶されているデータによって画定される任意のオブジェクトである。このタイプのシステムによれば、様々な種類のデータによってモデル化オブジェクトを画定することができる。ＣＡＤシステムは、モデル化オブジェクトの図形表現に基づいてモデル化オブジェクトを少なくとも設計するのに適した、ＣＡＴＩＡなどの任意のシステムである。したがってＣＡＤモデル化オブジェクトを画定するデータは、モデル化オブジェクトを表現することができるデータからなっている（例えば幾何学データであって、例えば空間中における相対位置を含むデータ）。
【００２２】
この方法は、この方法を実施した後に、モデル化ボリュームに対応する物理的な製品を製造するステップを含むことができる製造プロセスの中に含むことができる。いずれの場合においても、この方法によって設計されるモデル化ボリュームは、製造オブジェクトを表すことができる。したがってモデル化ボリュームは、モデル化固体（つまり固体を表すモデル化オブジェクト）であってもよい。製造オブジェクトは、部品または複数の部品のアセンブリなどの製品であってもよい。この方法によればモデル化ボリュームの設計が改善されるため、製品の製造が同じくこの方法によって改善され、したがって製造プロセスの生産性が向上する。この方法は、ＤＥＬＭＩＡなどのＣＡＭシステムを使用して実施することができる。ＣＡＭシステムは、製造プロセスおよび操作を少なくとも定義し、模擬し、かつ、制御するのに適した任意のシステムである。
【００２３】
この方法はコンピュータによって実施される。それは、この方法が少なくとも１つのコンピュータまたは同様の任意のシステム上で実行されることを意味している。他に特に言及されていない限り、この方法のすべてのステップはコンピュータによって実施され、つまり使用者の介在を必要とすることなく実施される。例えば、決定ステップ（Ｓ３０）のステップは、コンピュータによって単独で実施することができ、一方、提供ステップ（Ｓ１０）のステップおよび提供ステップ（Ｓ２０）のステップは、使用者の相互作用を介して実施することができる。実際、提供ステップ（Ｓ１０）のステップは、使用者によって先行して実施することができる。したがってこの方法によれば、モデル化ボリュームを表す複数のデクセルのセットを、恐らくは使用者によって提供される（Ｓ２０）複数の新しい線の関数で自動的に修正することができる。
【００２４】
この方法のコンピュータ実施態様の典型的な例は、この目的のために適したシステムを使用してこの方法を実施することである。システムは、この方法を実施するための命令がその上に記録されたメモリを備えることができる。言い換えると、直ちに使用するためにソフトウェアが既にメモリ上に準備されている。したがってシステムは、他のソフトウェアのインストールを全く必要とすることなく、この方法を実施するのに適している。また、このようなシステムは、メモリに結合された、命令を実行するための少なくとも１つのプロセッサを備えることも可能である。言い換えると、システムは、プロセッサに結合されたメモリ上に符号化された命令を備えており、これらの命令は、方法を実施するための手段を提供している。このようなシステムは、モデル化ボリュームを設計するための有効なツールである。
【００２５】
このようなシステムはＣＡＤシステムであってもよい。システムは、ＣＡＥおよび／またはＣＡＭシステムであってもよく、また、ＣＡＤモデル化オブジェクトは、ＣＡＥモデル化オブジェクトおよび／またはＣＡＭモデル化オブジェクトであってもよい。モデル化オブジェクトは、ＣＡＤシステム、ＣＡＥシステムおよびＣＡＭシステムの任意の組合せに対応するデータによって画定することができるため、実際、これらのＣＡＤシステム、ＣＡＥシステムおよびＣＡＭシステムは、これらのうちの１つに限定されない。
【００２６】
システムは、例えば使用者が命令の実行を開始するための少なくとも１つのＧＵＩを備えることができる。特に、ＧＵＩは、使用者による提供ステップ（Ｓ１０）のステップの実施を可能にすることができる。これは、提供ステップ（Ｓ２０）に先立って実施することができる。あるいは、複数の始線を精緻化することによって複数の新しい線を使用者が提供する（Ｓ２０）際に、スカルプチャ生成プロセス、複数の始線および複数のデクセルの初期セットを検索することができる。また、ＧＵＩは、使用者によるスカルプチャ生成操作の提供（Ｓ２０）を許容することも可能である。ＧＵＩはＧＰＵを備えることができる。このような場合、プロセッサはＧＰＵであってもよい。言い換えると、この方法の少なくともいくつかのステップ、とりわけ決定ステップ（Ｓ３０）のステップを実行するプロセッサはＧＰＵであってもよい。このようなシステムは、使用者がモデル化ボリュームを設計するための有効なツールである。デクセルに基づくアルゴリズムは、超並列ハードウェアにはうってつけであるため、近代のグラフィック処理装置（ＧＰＵ）の計算能力の使用を考慮することは当然である。
【００２７】
モデル化ボリュームは３Ｄ（つまり三次元）であってもよい。これは、モデル化ボリュームは、その３Ｄ表現を可能にするデータによって画定されることを意味している。３Ｄ表現により、表されたボリュームをあらゆる角度から見ることができる。例えばモデル化ボリュームは、３Ｄで表現されると、その任意の軸の周りに、または表現が表示されるスクリーン内の任意の軸の周りに操作することができ、また、回転させることができる。これは、３Ｄモデル化ではない２Ｄアイコンを明らかに排他している。３Ｄ表現で表示することによって設計が容易になる（つまり設計者が統計的に自身のタスクを達成している速度が速くなる）。製品の設計は製造プロセスの一部であるため、したがって産業における製造プロセスがスピードアップされる。
【００２８】
図２は、典型的なＣＡＤシステムのＧＵＩの一例を示したものである。
【００２９】
ＧＵＩ２１００は、標準メニューバー２１１０、２１２０、ならびに底部ツールバー２１４０および側部ツールバー２１５０を有する典型的なＣＡＤ様インタフェースであってもよい。このようなメニューバーおよびツールバーには、複数の使用者選択可能アイコンのセットが含まれており、個々のアイコンは、当分野で知られているように１つまたは複数の操作または機能に関連付けられている。これらのアイコンのうちのいくつかは、ＧＵＩ２１００の中に表示されている３Ｄモデル化オブジェクト２０００上で編集および／または作業するために適合されたソフトウェアツールに関連付けられている。ソフトウェアツールは、複数のワークベンチに分類することができる。個々のワークベンチは、複数のソフトウェアツールのサブセットを備えている。詳細には、これらのワークベンチのうちの１つは、モデル化製品２０００の幾何学的特徴を編集するのに適した編集ワークベンチである。動作中、設計者は、例えばオブジェクト２０００の一部を予め選択し、次に適切なアイコンを選択することにより、操作（例えばスカルプチャ生成操作または寸法、色、等々の変更などの任意の他の操作）を開始し、または幾何学的な制約の編集を開始することができる。例えば、典型的なＣＡＤ操作は、スクリーン上に表示されている３Ｄモデル化オブジェクトの押抜きまたは畳み込みのモデル化である。
【００３０】
ＧＵＩは、例えば、表示されている製品２０００に関連するデータ２５００を表示することができる。図２の例では、「特徴ツリー」として表示されているデータ２５００およびそれらの３Ｄ表現２０００は、ブレーキキャリパおよびディスクを含んだブレーキアセンブリに関している。ＧＵＩは、さらに、例えばオブジェクトの３Ｄ配向を容易にするために、編集済み製品の動作のシミュレーションをトリガするために、または表示されている製品２０００の様々な属性を描写するために、様々なタイプの図形ツール２１３０、２０７０、２０８０を示すことができる。カーソル２０６０は、使用者と図形ツールとの相互作用を可能にする触覚デバイスによって制御することができる。
【００３１】
図３は、クライアントコンピュータシステム、例えば使用者のワークステーションとしてのシステムのアーキテクチャの一例を示したものである。
【００３２】
クライアントコンピュータは、内部通信バスＢＵＳ１０００に接続された中央処理装置（ＣＰＵ）１０１０、同じくＢＵＳに接続されたランダムアクセスメモリ（ＲＡＭ）１０７０を備えている。クライアントコンピュータは、さらに、ＢＵＳに接続されたビデオランダムアクセスメモリ１１００に関連付けられているグラフィック処理装置（ＧＰＵ）１１１０を備えている。ビデオＲＡＭ１１００は、当分野ではフレームバッファとしても知られている。大容量記憶装置コントローラ１０２０は、ハードドライブ１０３０などのマスメモリデバイスへのアクセスを管理している。コンピュータプログラム命令およびデータを有形の形で具体化するのに適しているマスメモリデバイスには、一例として、ＥＰＲＯＭ、ＥＥＰＲＯＭなどの半導体メモリデバイスおよびフラッシュメモリデバイス、内部ハードディスクおよび取外し可能ディスクなどの磁気ディスク、光磁気ディスクおよびＣＤ−ＲＯＭディスク１０４０を始めとするあらゆる形態の不揮発性メモリがある。上記の任意のマスメモリデバイスは、特別に設計されたＡＳＩＣ（専用集積回路）によって補うことができ、またはこれらのＡＳＩＣの中に組み込むことができる。ネットワークアダプタ１０５０は、ネットワーク１０６０へのアクセスを管理している。また、クライアントコンピュータは、カーソル制御デバイス、キーボード、等々などの触覚デバイス１０９０を含むことも可能である。カーソル制御デバイスは、図２を参照して言及したように、使用者によるスクリーン１０８０上の任意の所望の位置へのカーソルの選択的配置を可能にするためにクライアントコンピュータに使用されている。スクリーンとは、表示を実施することができる、コンピュータモニタなどの任意のサポートを意味している。さらに、カーソル制御デバイスは、使用者による様々なコマンドの選択および制御信号の入力を可能にしている。カーソル制御デバイスには、システムに制御信号を入力するための多くの信号発生デバイスが含まれている。通常、カーソル制御デバイスはマウスであってもよく、マウスのボタンは、信号を発生するために使用される。
【００３３】
システムに方法を実施させるために、コンピュータが実行するための命令を含んだコンピュータプログラムが提供されており、命令には、そのための手段が含まれている。プログラムは、例えばディジタル電子回路の中で、またはコンピュータハードウェア、ファームウェア、ソフトウェアの中で、あるいはそれらの組合せの中で実施することができる。本発明の装置は、プログラマブルプロセッサによって実行するための機械可読記憶装置の中に有形で具体化されたコンピュータプログラム製品の中で実施することができ、また、本発明の方法ステップは、入力データ上で動作し、かつ、出力を生成することによって本発明の機能を実施するための命令のプログラムを実行するプログラマブルプロセッサによって実施することができる。命令は、有利には、データ記憶システムからデータおよび命令を受け取り、かつ、データ記憶システムにデータおよび命令を転送するように結合された少なくとも１つのプログラマブルプロセッサ、少なくとも１つの入力デバイスおよび少なくとも１つの出力デバイスを含んだプログラマブルシステム上で実行することができる１つまたは複数のコンピュータプログラムの中で実施することができる。アプリケーションプログラムは、必要に応じて高水準手続き形プログラミング言語またはオブジェクト指向プログラミング言語で、あるいはアセンブリ言語または機械言語で実施することができ、また、いずれの場合においても、言語は、コンパイル済み言語または翻訳済み言語であってもよい。プログラムは、フルインストレーションプログラムであっても、または更新プログラムであってもよい。更新プログラムの場合、プログラムは、システムが方法を実施するのに適した状態になるよう、既存のＣＡＤシステムを更新する。
【００３４】
この方法には、モデル化ボリュームを表す複数のデクセルの複数のセットが利用されている。これは、モデル化ボリュームの軽い表現を可能にしている（言い換えると、モデル化ボリュームをわずかなメモリ空間を使用して表現することができる）。また、これは、容易に操作することができるモデル化ボリュームの表現を可能にしている。特に、モデル化ボリュームが複数のデクセルのセットによって表されると、複数のデクセルのセットのデータ構造のため、モデル化ボリューム上での設計操作を極めて効率的に実施することができる。実際、高い応答性および高い頑強性で設計操作を実施することができる。特に、並列処理を使用して、線毎に複数のデクセルのセット上で操作を実施することができるため、高い効率が得られる。
【００３５】
ステップ（Ｓ１０）で提供される複数のデクセルの初期セットは、複数の始線（つまり第１の複数の線）に基づく複数のデクセルの第１のセットであり、一方、複数のデクセルの新しいセットは、ステップ（Ｓ２０）で提供される第２の複数の線である複数の新しい線に基づく複数のデクセルの第２のセットである。
【００３６】
「デクセル」という用語は、「深さエレメント」に対するショートカット（ｓｈｏｒｔｃｕｔ）として知られている（「ピクセル」という用語が「ピクチャエレメント」に対するショートカットであるのと全く同様に）。デクセルの概念については、極めて多くの研究論文で言及されている。本発明による方法の文脈においては、デクセルは、少なくとも１つの線分のセット、つまり一対の３Ｄポイントを備えている。一例では、モデル化ボリュームは、少なくとも２つの線分のセットを備えた少なくとも１つのデクセルを備えている（例えば複数のデクセルの初期セットおよび／または複数のデクセルの新しいセットは、少なくとも２つの線分を備えている）。デクセルの線分は、複数の線分が存在している場合、整列していても（このような場合、デクセルはリストである）、または整列していなくてもよい。デクセルの線分は、線とモデル化ボリュームとの間の交差を表している。言い換えると、モデル化ボリュームと交差している仮想線を考察すると、デクセルは、所与の線から始まる、交差の計算から得られる複数の線分のセットである。そのため、デクセルは、複数の線に基づいている、と言われている（つまりその線分はその線上に位置している）。例えば、複数のデクセルの初期セットは複数の始線に基づいており、一方、複数のデクセルの新しいセットは複数の新しい線に基づいている。したがって、複数のデクセルの初期セットを提供するステップ（Ｓ１０）および／または複数のデクセルの新しいセットを決定するステップ（Ｓ３０）は、例えば仮想線を描くことによってこのような交差を計算するステップ、およびＢ−Ｒｅｐによって、または任意の他のボリューム表現によって最初に表すことができるモデル化ボリュームとの交差を計算するステップを含むことができる。したがって複数のデクセルのこれらのセットはモデル化ボリュームを表している。
【００３７】
複数のデクセルのこれらのセットは、コンピュータ実施データとして提供されることに留意することは重要である。したがってモデル化ボリュームの任意の表現に関して上で提供した定義および以下で提供する定義は、データ構造の観点から密接な関係を有している。例えば、線分は、一対の３Ｄ位置（例えば互いに結合している２つの３Ｄ位置）として提供することができる。３Ｄ位置自体は、関連する３Ｄフレームに関連付けられた３つの座標（例えば浮動小数点）のリストとして提供することができる。デクセルは複数の線分のセットであり、これは、複数の線分が集合構造で一体に結合していることを意味している。複数のデクセルのセットの複数のデクセルも同じく一体に結合させることができる。それら自体が少なくとも１つの線分のセットを備えている複数のデクセルのセットによってモデル化ボリュームを表すことにより、決定ステップ（Ｓ３０）を速くすることができる。
【００３８】
次に、デクセル構造６７として複数のデクセルの初期セットを提供するステップ（Ｓ１０）のステップの一例を示す図４〜６を参照して、複数のデクセルの概念について実例で説明する。複数のデクセルの新しいセットを決定するステップ（Ｓ３０）も、図４〜６の例に基づいて実施することができる。
【００３９】
モデル化ボリュームが与えられ、かつ、無限線が与えられると、デクセルは、無限線とモデル化ボリュームとの間の交差を表す複数の線分（または区間）のセットである。複数の線分のこのセットは、個々の線分の複数の境界点のセットとしてメモリに捕獲される。デクセル構造は、例えば長方形格子上に整列させることによって系統だてられている複数のデクセルのセットである（個々のデクセルは複数の線分のセットを備えている）。図４および５は、モデル化ボリューム４０を１０×１０の格子線５０と共に示したものである。この方法例には、図４に示されているように、例えばＢ−Ｒｅｐとしてモデル化ボリューム４０を提供するステップが含まれている。この方法例には、次に、図５に示されているようにモデル化ボリューム４０と交差する（少なくとも部分的に）１０×１０格子線５０を画定するステップが含まれている。この方法例には、次に、図６に示されているように複数の線分６０および／または６２の複数のセットを備えている複数のデクセル６５を計算するステップが含まれている。図には１つのデクセル６５が円で囲まれている。デクセル６５は、線５０が１つのスポットでモデル化ボリューム４０と交差しているか、または複数の個別のスポットでモデル化ボリューム４０と交差しているかどうかに応じて、複数の線分６０または１つの線分６２を備えることができる。当然、この方法は、別法としてメモリから複数のデクセル６５を検索することも可能である。いずれの場合においても、このようにしてデクセル構造６７が提供される。
【００４０】
図６は、結果として得られたデクセル構造６７を示したものである。同じ数の複数のデクセル６５をもたらすために必ずしもすべての線５０がモデル化ボリューム４０と交差しているわけではない（この例では、モデル化ボリューム４０と交差しているのは５２本の線にすぎない）ことに注意されたい（モデル化ボリューム４０と交差していない線は、実際には捨てられ、デクセルをもたらすことはない）。さらに、いくつかの線５０は、１つの線分６２を介してモデル化ボリューム４０と交差しており（例えばデクセル（２、３）またはデクセル（９、６））、他の線５０は、複数の線分６０、例えば２つの線分を介してモデル化ボリューム４０と交差しており（例えばデクセル（７、７）またはデクセル（４、７））、もしくは３つの線分を介してモデル化ボリューム４０と交差しており（デクセル（２、８）またはデクセル（５、８））、または４つの線分を介してモデル化ボリューム４０と交差している（デクセル（２、９）またはデクセル（４、９））。結果として得られたデクセル構造６７には、５２個のデクセル６５が含まれており、そのうちの３６個のデクセル６５は１つの線分６２を備えており、６個のデクセル６５は２つの線分６０を備えており、５個のデクセル６５は３つの線分６０を備えており、また、５個のデクセルは４つの線分６０を備えている。
【００４１】
（Ｓ１０）で提供される（または（Ｓ３０）で決定される）複数のデクセルのセットは、トライデクセル構造であってもよい。トライデクセル構造は、通常、ｘ軸に対して平行のデクセル構造、ｙ軸に対して平行のデクセル構造およびｚ軸に対して平行のデクセル構造の３つのデクセル構造を備えることによって画定される。この方法は、任意の時間におけるモデル化ボリューム、例えば提供ステップ（Ｓ２０）および決定ステップ（Ｓ３０）の間のモデル化ボリュームの図形表現を表示するステップを含むことができる。表示するステップは、複数のデクセルのセット（いつ表示するかに応じて複数のデクセルの初期セットまたは複数のデクセルの新しいセット）に基づくことができる。トライデクセル構造は、その「観察方向」依存性が小さいため、良好な表示を提供する。トライデクセル構造は、とりわけ、使用者が視点を変更した場合により正確な表示を提供する。
【００４２】
図６〜８は、同じモデル化ボリュームを表すデクセル構造をそれぞれ示したものである。言い換えると、モデル化ボリュームは、図６〜８の３つのデクセル構造を含んだトライデクセルデータによって画定することができる。図６は、ｙ軸に沿ったデクセル構造６７を示したものである。図７は、ｘ軸に沿ったデクセル構造６８を示したものである。図８は、ｚ軸に沿ったデクセル構造６９を示したものである。個々の図では、複数のデクセルの複数の線は、それぞれの軸に対して平行である。
【００４３】
また、線分の端点におけるモデル化ボリュームの境界に対する外部法線ベクトルをデータの中に提供することも可能である。それによりモデル化ボリュームをより鮮明に表現することができる。
【００４４】
また、この方法には、モデル化ボリュームへのスカルプチャ生成プロセスを提供するステップが含まれている。スカルプチャ生成プロセスは、任意の一連の少なくとも１つのスカルプチャ生成操作である。スカルプチャ生成操作は、モデル化ボリュームをスカルプチャ生成するためのシステムによって提供される任意の操作である。モデル化ボリュームをスカルプチャ生成することは、ブール演算によってモデル化ボリュームにボリュームを加え、および／またはモデル化ボリュームからボリュームを除去することを意味している。したがってスカルプチャ生成操作は、モデル化ボリュームに対する少なくとも１つのボリュームブール演算の任意の組合せである。例えば局所ボリューム除去および局所ボリューム追加はスカルプチャ生成操作であり、一方、表面からの押出しは、ブール演算には全く基づいていないため、スカルプチャ生成操作ではない。一例では、スカルプチャ生成操作は、時間継続期間の間、モデル化ボリュームに追加される（またはモデル化ボリュームから除去される）連続ボリューム（つまり解体されないボリューム）を必要とする一連の連続するブール演算である。例えばスカルプチャ生成操作は、機械加工操作を表している。
【００４５】
したがって複数のデクセルのセットは任意の固体を表すことができ、また、スカルプチャ生成プロセスは、固体の実際のスカルプチャ生成を模擬することができる。この方法は、とりわけ、計算機援用設計システムを使用した実時間機械加工シミュレーションに含むことができる。言い換えると、固体は原料であってもよく、また、方法は、切断工具によって仮想的に機械加工されている原料の形状を表示することができる。このような場合、モデル化ボリュームは原料を表し、また、プロセスは切断プロセスである。この例は、複合製造および仮想粘土の形状のスカルプチャ生成など、一部品に同じく材料が加えられる他の製造プロセスに一般化することができる。この例は、機械設計、形状設計、建設建築物、等々を始めとする従来のあらゆる固体モデル化アプリケーションにも一般化することができる。最後に、この方法は、その性能能力のため、インタラクティブな３Ｄスカルプチャ生成などのより精巧なアプリケーションを取り扱うことができる。最も一般的には、スカルプチャ生成操作は機械加工操作を表すことができる。このような場合、モデル化ボリュームは、機械加工操作が施されているワークピースを表すことができ、したがってこの方法によれば、ワークピースの機械加工のシミュレーションが改善される。したがってこの方法は、仮想機械加工プロセスを試験するための良好な基礎として働くことができる。
【００４６】
実際、この方法には、さらに、複数の始線を精緻化する（つまり使用者の要求に応じて修正する）ことによって複数の新しい線を提供するステップ（Ｓ２０）、およびスカルプチャ生成プロセスを経た後の、複数の新しい線に基づくモデル化ボリュームを表す複数のデクセルの新しいセットを決定するステップ（Ｓ３０）が含まれている。言い換えると、この方法は、複数の新しい線にスカルプチャ生成プロセスを加え、または、さらに言い換えると、この方法は、スカルプチャ生成プロセスに従って、複数の新しい線に基づく複数のデクセルのセットによって画定されるモデル化ボリュームのスカルプチャ生成の結果を決定する。複数のデクセルの新しいセットは、複数の線の精緻化された後のセットに基づくスカルプチャ生成（例えば機械加工）後のオブジェクトを表している。したがってこの方法によれば、スカルプチャ生成プロセスを経た後のモデル化ボリュームの表現を改良された表現に向けて修正することができる。
【００４７】
個々のデクセルは、複数の線分のセットを備えている。モデル化ボリュームと交差する線のすべての線分は、１つのデクセルに分類される。これは線毎に可能であり、したがって、例えば並列処理が可能であるため、モデル化ボリュームのより有効な処理が可能である。実際、この方法は、線毎の並列処理によって実行することができる。
【００４８】
並列処理は、複数のタスクをシステムによって同時に実施するステップからなっている。この方法の場合、複数のデクセルの新しいセットを決定するステップ（Ｓ３０）は、複数の新しい線の各々に対して単一命令スレッドを実行するステップを含むことができる。したがって複数のデクセルの新しいセットを決定するステップ（Ｓ３０）は、ＳＩＭＤ（Ｓｉｎｇｌｅ Ｉｎｓｔｒｕｃｔｉｏｎ Ｍｕｌｔｉｐｌｅ Ｄａｔａ）並列処理によって実施することができる。この方法を実行するシステムのプロセッサは、例えばシステムが１０個または１００個を超えるプロセッサでネットワーク化される場合、とりわけ超並列処理装置であってもよい。
【００４９】
一例では、この方法には、使用者によって実施される機械加工シミュレーションフェーズが含まれている（またはこの方法は、機械加工シミュレーションフェーズ後に実施される）。常に、複数のデクセルのセットは、それが示しているように、任意の固体、例えばワークピースを表すモデル化ボリュームの表現である。機械加工シミュレーションフェーズでは、使用者は、複数のデクセルの「オリジン」セットにスカルプチャ生成プロセスを加える。複数のデクセルの「オリジン」セットは、メモリから検索することができ、または複数の「オリジン」線のセットを、基準ボリューム、例えば原料、例えば図４〜８を参照して上で説明したＢ−Ｒｅｐとして保存されている原料と交差させることによって検索することができる。複数のデクセルの「オリジン」セットにスカルプチャ生成プロセスを加えるステップは、任意の知られている手順に従って実施することができる。例えば、スカルプチャ生成プロセスに切断操作が含まれている場合、影響を受けるデクセルは、その複数の線分のうちの１つまたは複数を控除することができ、またはその複数の線分のうちの１つまたは複数を短くすることができる。一方、スカルプチャ生成プロセスに材料追加操作が含まれている場合、影響を受けるデクセルは、その複数の線分のうちの１つまたは複数を長くするか、または１つまたは複数の新しい線分を加えることができる。複数のデクセルの「オリジン」セットにスカルプチャ生成プロセスを加えることによって最終的には複数のデクセルのセットが修正され、それにより複数のデクセルの初期セットに到達する。また、スカルプチャ生成プロセスおよび基準モデル化ボリューム（例えばＢ−Ｒｅｐまたは複数のデクセルのオリジンセット）に対するデータが節約される。
【００５０】
この時点で、使用者（恐らくは同じ使用者、または他の使用者）は、この方法を実施することができる。例えば使用者は、複数のデクセルの初期セットを検索することができる。このようなデータから複数の始線を決定することができる。あるいは複数の始線を記憶しておくことも可能であり、また、この方法は、それらを直接検索するステップを含むことができる。また、この方法には、機械加工フェーズのスカルプチャ生成プロセスを提供するステップが含まれている。言い換えると、モデル化ボリュームに施されたスカルプチャ生成プロセス（基準ボリュームから複数のデクセルの初期セットに到達するために）を表すデータが提供される。それにより、モデル化オブジェクトのスカルプチャ生成履歴をいつでも検索することができる。複数のデクセルの初期セットは、使用者に表示することができる。
【００５１】
次に、この方法は、複数の始線を精緻化することによって複数の新しい線を提供する（Ｓ２０）。複数の始線の精緻化は、モデル化ボリュームの表現（このような表現は、この時点における複数のデクセルの初期セットである）を修正するために使用者によって実施される任意の要求であってもよい。複数の始線を精緻化するステップは、複数の始線の密度（つまり単位ボリューム当たりの数）を高くするステップ、複数の始線（のうちの少なくとも一部）の方向を変更するステップ、および／または複数の始線の一部を捨てる（つまり削除する）ステップのうちの任意のステップまたはステップの組合せを含むことができる。言い換えると、使用者はモデル化ボリュームの新しい表現を要求し、また、この方法は、複数の新しい線を提供してモデル化ボリュームと交差させることによってこのような要求を処理している。ステップ（Ｓ３０）で新しい複数のデクセルが決定され、また、新しい表現を使用者に表示することができる。したがって使用者の要求に応じてモデル化ボリュームの表現を効果的に修正することができる。したがって延いては、使用者に表示されたモデル化ボリュームの表現をオンデマンドで修正することができる。したがって例えば他の機械加工シミュレーションフェーズのための使用者の作業を容易にすることができる。
【００５２】
例えば使用者はズームを要求することができる。このような場合、この方法は、要求されたズーミングゾーンに対応するモデル化ボリュームのゾーンを選択することができ、そのゾーンと交差しない複数の始線を捨てることができる。この方法は、さらに、そのゾーンと交差する複数の線の密度を高くすることができ、それにより複数の新しい線がもたらされる。また、この方法は、視点（ディスプレイの）を修正するステップを含むことも可能であり、したがってその新しい視線に従って導かれるよう、複数の始線の方向を修正するステップを含むことも可能である。そのため、とりわけスクリーン上のモデル化ボリュームの投影の境界でのより鮮明な表現が可能である。
【００５３】
また、使用者は、スカルプチャ生成プロセスの高品位視覚化をいつでも要求することができる。このような場合、この方法は、線の数を増やすステップを含むことができ、例えば１ピクセル当たり最大１本の線まで増やすステップを含むことができる。例えばスクリーンの個々のピクセルに１本の線を関連付けることができる。言い換えると、１本の線がスクリーンの個々のピクセルを通過しており、モデル化ボリュームと交差することができる。したがって最適数の線を使用して最も鮮明な表示が可能である。
【００５４】
この方法によれば、スカルプチャ生成プロセスを経た後の、複数の新しい線に基づくモデル化ボリュームを表す複数のデクセルの新しいセットが決定される（Ｓ３０）。これは、複数の新しい線と基準ボリューム（つまり処理されていないモデル化ボリューム）との交わりを決定し、つまり個々の新しい線と、スカルプチャ生成プロセスを経る前のモデル化ボリュームとの間の交差を表す少なくとも１つの線分の複数のセットを決定し（Ｓ３１）、次に少なくとも１つの線分の複数の決定済みセットにスカルプチャ生成プロセスを加える（Ｓ３２）ことによって実施することができる（ちょうど上で説明したように、任意の知られている方法に従って）。
【００５５】
スカルプチャ生成プロセスに対するデータおよびスカルプチャ生成プロセスを経る前のモデル化ボリュームに対するデータなどの重要なデータを維持することにより、この方法は、モデル化ボリュームを表す複数のデクセルのセットを精緻化することができ、また、例えばそれにより、複数のデクセルのセットに基づいて、効果的な方法でいつでもモデル化ボリュームの表示を改良することができる。実際、この方法は、排他的に複数の新しい線を提供することができ、また、次に、複数のデクセルを画定している複数の線分の複数のセットに対して、これらの複数の新しい線に対する操作を実施してこれらの複数の新しい線を少なくすることができる。これにより、プロセッサの観点から、高い効率が提供される。また、この精緻化は高度に頑丈であり、かつ、使用者の要求に高度に応答する（この方法の実行は安全で、かつ、高速である）。これは、モデル化ボリュームを使用者に表示する場合にとりわけ有利であり、また、表示を実時間で修正するために使用者が複数の新しい線を提供する場合にとりわけ有利である。
【００５６】
複数の始線の精緻化は、使用者のアクションによって実施することができ、例えば複数のデクセルの初期セットの図形表示との使用者との相互作用の結果として実施することができる。例えば、複数の始線を精緻化するステップには、スカルプチャ生成プロセスを経る前のモデル化ボリュームの少なくとも一部を拘束するボックス、ボックスの概観を提供するステップ、および所定の密度で概観の方向にボックスと交差する複数の線を描くステップを含むことができる。ボックスは、一般的には、モデル化ボリュームの少なくとも一部を拘束する平行六面体、球または任意のボリュームであってもよい。例えば使用者は、ある観点から、システムの触覚デバイスを使用して、例えば１つまたは複数のカメラの位置および／または配向を画定することによって選択することができ、それによりこの方法は、対応するボックスを自動的に提供する。ところで、ボックスの概観は、恐らくは（例えば同じ）使用者のアクションによって、またはそうではなくても画定することができる。「概観」とは遠景を意味しており、この遠景に従ってモデル化ボリュームが表示される。したがってボックスと交差する複数の線を描く（つまり複数の線を引く）ステップは、その概観の方向に実施することができる（つまり描かれる個々の新しい線は、オブジェクトが観察される方向に対応させることができる）。言い換えると、これらの線は、モデル化ボリュームの複数の点がスクリーン上に投影される方向に沿って描かれる。これらの線は、平行であっても、または平行でなくてもよいことに留意されたい。概観の方向は、実際、単一であってもよいが、例えば円錐遠景である場合、複数であってもよい。いずれの場合においても、これらの線は、必ず、その概観によって強いられる方向に沿って描かれる（この方向は、恐らく線毎に異なっている）。
【００５７】
複数のデクセルの初期セットの複数のデクセルは、それらに影響を及ぼしたスカルプチャ生成操作に関連付けられることができる。このような場合、スカルプチャ生成プロセスは、一連の前述のスカルプチャ生成操作として提供される（例えばスカルプチャ生成操作が実施されるシーケンスに関する情報も恐らく記憶される）。言い換えると、複数のデクセルの初期セットのために提供されるデータは、複数のデクセルの各々に影響を及ぼしたスカルプチャ生成操作、つまりデクセル幾何学を修正したスカルプチャ生成操作に関する情報を含むことができる。したがって加えるステップ（Ｓ３２）を有効に実施することができる。実際、提供ステップ（Ｓ２０）に引き続いて、複数の始線のうちのいくつかを維持することができる。複数のデクセルに対するスカルプチャ生成操作、または等価的にこのような複数のデクセルに対応する複数の線に対するスカルプチャ生成操作を関連させることにより、この方法は、一連のすべてのスカルプチャ生成操作の代わりに、維持されている複数の始線に関連付けられている一連のスカルプチャ生成操作としてスカルプチャ生成プロセスを加えることができる（Ｓ４０）。
【００５８】
スカルプチャ生成操作は、それらが最後に影響を及ぼした複数のデクセルの複数の線分に結合することができる。言い換えると、ステップ（Ｓ１０）で提供されるデータには、スカルプチャ生成操作と複数のデクセルの複数の線分との間のリンクが含まれており、それによりそれらの複数の線分を介して複数のデクセルに対するスカルプチャ生成操作が結合される。これらの線分は、前記スカルプチャ生成操作によって影響される最後の線分である。
【００５９】
あるいはスカルプチャ生成操作の各々は、複数のデクセルのそれぞれの線分と結合しており、また、その前に実施された、それぞれの線分に対する影響を有するスカルプチャ生成操作の結果である。言い換えると、「合成」操作を提供するためにいくつかのスカルプチャ生成操作が組み合わされる。それによりメモリが節約され、また、その前に実施されたスカルプチャ生成操作が、複数のデクセルに対する同じ影響を最適化された方法でもたらす単一のスカルプチャ生成操作として記憶される。したがって加えるステップ（Ｓ３２）のステップは、より迅速に実施することができる。
【００６０】
デクセル線分の個々の末端は、基本操作基準欄（例えば整数）を備えることができる。例えば機械加工シミュレーションの場合、基本操作基準は、結合（工具、例えば切断工具、または材料追加ツール、および軌道の要素）に向かう基準である。シミュレーション中にデクセル線分の末端が更新されると、基準欄は、その更新を誘導したスカルプチャ生成プロセス中の対応する基本操作基準として更新される。言い換えると、個々の線分の末端は、そのトリミング操作を示している。
【００６１】
したがって加えるステップ（Ｓ３２）は、初期格子からの初期化を計算し、次に、表されている固体の現在の状態の境界に実際に寄与しているスカルプチャ生成操作、一般的にはブール演算のサブセットのみを利用することによって加速される。これは、現在の固体の状態がこの方法のオプションである極めて多くのスカルプチャ生成操作をもたらす場合にとりわけ有利である。例えば機械加工シミュレーションは、通常、スイープされた固体を使用して何百万もの局所ブール演算によって得られる固体状態を取り扱うことができる。
【００６２】
有効な精緻化手順を任意の微小格子、したがって細かい格子に対して実施することができるため、オンデマンドで、ゆとりのある応答時間内で任意の精度が提供される。実際には、これは、局部的に正確なズーム、つまり合理的な計算時間で精緻化された計算を可能にしている。
【００６３】
次に、この方法の一例を説明する。
【００６４】
スカルプチャ生成プロセスが与えられ、そのスカルプチャ生成プロセスがある特定のポイントまでその前に実行されている基準格子が与えられ、かつ、ボックスが与えられると、精緻化手順は、その与えられたボックス内のより細かい格子フィッティングに対してもう一度そのスカルプチャ生成プロセスを実行する。ボックスは、使用者によって画定された新しいズームおよび視点を捕獲する。これを効果的に実行するために、手順は、以下のステップを実施する。
【００６５】
１．ボックスに属している複数の線分端点のセットが収集され、そこから２種類の情報が集められる。第１の種類は結果の幾何学近似値であり、第２の種類は、収集された複数のデクセルの末端に関連付けられている複数の基本操作基準のセットである。
【００６６】
２．より細かい格子は、収集された近似幾何学から初期化される。機械加工操作などの負のブール演算（集合差）の場合は、近似値（を含んだ）上部、または正のブール演算（和集合、ミンコフスキー和、等々）の場合は下部近似値（近似値が含まれている）。
【００６７】
３．収集された基本操作基準に対応するスカルプチャ生成プロセスのサブセットが、細かい格子に対して実行される。機械加工シミュレーションの場合、デクセル線分の収集されたいくつかの末端がそのことを言及している場合、このステップには、初期固体を初期化するステップを含むことができ、また、収集されたすべての軌道要素を再生する。
【００６８】
より細かい格子は、通常、基準格子の微小サブセット上で実施することができるため、実行しなければならない複数の基本操作のセットは、全シナリオよりはるかに小さくしなければならないようである。図９〜１０を参照すると、より細かい格子に対応するボックスは、軸系に対して平行ではない平行六面体９０であっても、または精緻化の目的が局所視角化（ズーム）である場合、切頭体１００であってもよい。ボックスが切頭体である場合、格子内の複数の新しい線１０２は、所与の方向に対して平行ではなく、円錐遠景に対して好都合である。図から分かるように、複数の新しい線９２または１０２は、複数の初期デクセル９４および１０４とは異なる方向のデクセルであってもよい。
【特許請求の範囲】
【請求項１】
モデル化ボリュームを設計するためのコンピュータ実施方法であって、
前記モデル化ボリュームへのスカルプチャ生成プロセス、複数の始線、および前記スカルプチャ生成プロセスを経た後の、前記複数の始線に基づく前記モデル化ボリュームを表す複数のデクセルの初期セットを提供するステップ（Ｓ１０）であって、前記初期セットの個々のデクセルが、個々の始線と前記モデル化ボリュームとの間の交差を表す少なくとも１つの線分のセットを含むステップ（Ｓ１０）と、
前記複数の始線を精緻化することによって複数の新しい線を提供するステップ（Ｓ２０）と、
前記スカルプチャ生成プロセスを経た後の、前記複数の新しい線に基づく前記モデル化ボリュームを表す複数のデクセルの新しいセットを決定するステップ（Ｓ３０）であって、個々の新しい線と、前記スカルプチャ生成プロセスを経る前の前記モデル化ボリュームとの間の前記交差を表す少なくとも１つの線分の複数のセットを決定するステップ（Ｓ３１）と、少なくとも１つの線分の前記複数の決定済みセットに前記スカルプチャ生成プロセスを加えるステップ（Ｓ３２）とを含む、ステップ（Ｓ３０）と
を含むことを特徴とする方法。
【請求項２】
前記複数の始線を精緻化するステップは、
前記複数の始線の密度を高くするステップと、
前記複数の始線の方向を変更するステップと、および／または
前記複数の始線の一部を捨てるステップ
のうちの任意のステップまたはステップの組合せを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記複数の始線を精緻化するステップは、前記スカルプチャ生成プロセスを経る前の前記モデル化ボリュームの少なくとも一部を拘束するボックス、前記ボックスの概観を提供するステップ、および所定の密度で前記概観の方向に前記ボックスと交差する複数の線を描くステップを含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記複数のデクセルの前記初期セットの複数のデクセルは、それらに影響を及ぼしたスカルプチャ生成操作に関連付けられており、前記スカルプチャ生成プロセスが一連の前記スカルプチャ生成操作として提供されることを特徴とする請求項１から請求項３のいずれか一項に記載の方法。
【請求項５】
前記スカルプチャ生成操作は、それらが最後に影響を及ぼした前記複数のデクセルの前記複数の線分と結合していることを特徴とする請求項４に記載の方法。
【請求項６】
前記スカルプチャ生成操作の各々は、前記複数のデクセルのそれぞれの線分と結合しており、また、その前に実施された、前記それぞれの線分に対する影響を有するスカルプチャ生成操作の結果であることを特徴とする請求項４に記載の方法。
【請求項７】
前記方法は、スクリーン上に前記モデル化ボリュームを表示するステップを含み、また、前記複数の始線を精緻化するステップは、前記スクリーンの１ピクセル当たり最大１本の線まで前記複数の始線の密度を高くするステップを含み、それにより１本の線が前記スクリーンの個々のピクセルに関連付けられることを特徴とする請求項２に記載の方法。
【請求項８】
請求項１から請求項７のいずれか一項に記載の方法を実施するための命令がその上に記録されたメモリと、
前記メモリに結合されたプロセッサと、
前記プロセッサに結合された、前記命令の実行に適した少なくとも１つのグラフィカルユーザインタフェースと
を備えることを特徴とするＣＡＭシステム。
【請求項９】
前記プロセッサはＧＰＵ（Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）であることを特徴とする請求項８に記載のシステム。
【請求項１０】
請求項１から請求項７のいずれか一項に記載の方法を実施するための命令を含むことを特徴とするコンピュータプログラム。
【請求項１１】
請求項１０に記載のコンピュータプログラムがその上に記録されたことを特徴とするコンピュータ可読記憶媒体。
【請求項１】
モデル化ボリュームを設計するためのコンピュータ実施方法であって、
前記モデル化ボリュームへのスカルプチャ生成プロセス、複数の始線、および前記スカルプチャ生成プロセスを経た後の、前記複数の始線に基づく前記モデル化ボリュームを表す複数のデクセルの初期セットを提供するステップ（Ｓ１０）であって、前記初期セットの個々のデクセルが、個々の始線と前記モデル化ボリュームとの間の交差を表す少なくとも１つの線分のセットを含むステップ（Ｓ１０）と、
前記複数の始線を精緻化することによって複数の新しい線を提供するステップ（Ｓ２０）と、
前記スカルプチャ生成プロセスを経た後の、前記複数の新しい線に基づく前記モデル化ボリュームを表す複数のデクセルの新しいセットを決定するステップ（Ｓ３０）であって、個々の新しい線と、前記スカルプチャ生成プロセスを経る前の前記モデル化ボリュームとの間の前記交差を表す少なくとも１つの線分の複数のセットを決定するステップ（Ｓ３１）と、少なくとも１つの線分の前記複数の決定済みセットに前記スカルプチャ生成プロセスを加えるステップ（Ｓ３２）とを含む、ステップ（Ｓ３０）と
を含むことを特徴とする方法。
【請求項２】
前記複数の始線を精緻化するステップは、
前記複数の始線の密度を高くするステップと、
前記複数の始線の方向を変更するステップと、および／または
前記複数の始線の一部を捨てるステップ
のうちの任意のステップまたはステップの組合せを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記複数の始線を精緻化するステップは、前記スカルプチャ生成プロセスを経る前の前記モデル化ボリュームの少なくとも一部を拘束するボックス、前記ボックスの概観を提供するステップ、および所定の密度で前記概観の方向に前記ボックスと交差する複数の線を描くステップを含むことを特徴とする請求項２に記載の方法。
【請求項４】
前記複数のデクセルの前記初期セットの複数のデクセルは、それらに影響を及ぼしたスカルプチャ生成操作に関連付けられており、前記スカルプチャ生成プロセスが一連の前記スカルプチャ生成操作として提供されることを特徴とする請求項１から請求項３のいずれか一項に記載の方法。
【請求項５】
前記スカルプチャ生成操作は、それらが最後に影響を及ぼした前記複数のデクセルの前記複数の線分と結合していることを特徴とする請求項４に記載の方法。
【請求項６】
前記スカルプチャ生成操作の各々は、前記複数のデクセルのそれぞれの線分と結合しており、また、その前に実施された、前記それぞれの線分に対する影響を有するスカルプチャ生成操作の結果であることを特徴とする請求項４に記載の方法。
【請求項７】
前記方法は、スクリーン上に前記モデル化ボリュームを表示するステップを含み、また、前記複数の始線を精緻化するステップは、前記スクリーンの１ピクセル当たり最大１本の線まで前記複数の始線の密度を高くするステップを含み、それにより１本の線が前記スクリーンの個々のピクセルに関連付けられることを特徴とする請求項２に記載の方法。
【請求項８】
請求項１から請求項７のいずれか一項に記載の方法を実施するための命令がその上に記録されたメモリと、
前記メモリに結合されたプロセッサと、
前記プロセッサに結合された、前記命令の実行に適した少なくとも１つのグラフィカルユーザインタフェースと
を備えることを特徴とするＣＡＭシステム。
【請求項９】
前記プロセッサはＧＰＵ（Ｇｒａｐｈｉｃｓ Ｐｒｏｃｅｓｓｉｎｇ Ｕｎｉｔ）であることを特徴とする請求項８に記載のシステム。
【請求項１０】
請求項１から請求項７のいずれか一項に記載の方法を実施するための命令を含むことを特徴とするコンピュータプログラム。
【請求項１１】
請求項１０に記載のコンピュータプログラムがその上に記録されたことを特徴とするコンピュータ可読記憶媒体。
【図１】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図１０】
【図９】
【図２】
【図３】
【図４】
【図５】
【図６】
【図７】
【図８】
【図１０】
【図９】
【公開番号】特開２０１３−９７８１２（Ｐ２０１３−９７８１２Ａ）
【公開日】平成２５年５月２０日（２０１３．５．２０）
【国際特許分類】
【外国語出願】
【出願番号】特願２０１２−２４２６５１（Ｐ２０１２−２４２６５１）
【出願日】平成２４年１１月２日（２０１２．１１．２）
【出願人】（５００１０２４３５）ダッソー システムズ (52)
【氏名又は名称原語表記】ＤＡＳＳＡＵＬＴ ＳＹＳＴＥＭＥＳ
【Ｆターム（参考）】
【公開日】平成２５年５月２０日（２０１３．５．２０）
【国際特許分類】
【出願番号】特願２０１２−２４２６５１（Ｐ２０１２−２４２６５１）
【出願日】平成２４年１１月２日（２０１２．１１．２）
【出願人】（５００１０２４３５）ダッソー システムズ (52)
【氏名又は名称原語表記】ＤＡＳＳＡＵＬＴ ＳＹＳＴＥＭＥＳ
【Ｆターム（参考）】
[ Back to top ]