"計算機支援幾何学的デザインシステムにおける、第1のモデル化オブジェクトおよび第2のモデル化オブジェクトから、前記第1のモデル化オブジェクトを第1の三角形分割多面体閉曲面によってモデル化し、前記第2のモデル化オブジェクトを第2の三角形分割多面体閉曲面によってモデル化し、結果として得られる三角形分割多面体閉曲面を計算するコンピュータで実行する方法であって、前記第1のモデル化オブジェクトの三角形と、前記第2のモデル化オブジェクトの三角形との間の積集合を計算するステップS30と、前記第1のモデル化オブジェクトの三角形および第2のモデル化オブジェクトの三角形を、前記積集合に隣接する多角形ファセットに分割するステップS40と、各三角形および各多角形ファセット用に、2つの巻き数対p、qを計算するステップS60であって、各巻き数対の前記第1の巻き数を、前記第1の三角形分割多面体閉曲面から計算し、各巻き数対の前記第2の巻き数を、前記第2の三角形分割多面体閉曲面から計算するステップと、各三角形および各多角形ファセット用に係数kを計算するステップS70であって、前記係数を、各三角形および各多角形ファセットの前記2つの巻き数対p、qを入力としてもつ関数φで計算するステップと、三角形および多角形ファセットを、前記計算された係数に従って、選択するステップS80と、前記選択された多角形ファセットを三角形分割するステップS90と、前記選択された三角形および前記三角形分割された選択された多角形ファセットをもつ、結果として得られる前記三角形分割多面体閉曲面を取得するステップS100とを備えたことを特徴とするコンピュータで実行する方法。三角形分割多面体閉曲面によってモデル化された前記第1のモデル化オブジェクトまたは三角形分割多面体閉曲面によってモデル化された前記第2のモデル化オブジェクトの少なくとも一方は、自己積集合を含み、前記三角形の間の積集合を計算するステップは、三角形分割多面体閉曲面によってモデル化された前記第1のモデル化オブジェクトまたは三角形分割多面体閉曲面によってモデル化された前記第2のモデル化オブジェクトの前記少なくとも一方の三角形の間の積集合を計算するステップをさらに含むことを特徴とする請求項1に記載のコンピュータで実行する方法。前記三角形を分割するステップの後に、少なくとも1つの領域を計算するステップであって、領域は互いに隣接し、かつ前記計算された積集合の1つによって区切られる、三角形および/または多角形ファセットの集合を有するステップをさらに含むことを特徴とする請求項1から2の1つに記載のコンピュータで実行する方法。前記領域のすべての三角形および/またはすべての多角形ファセットを判定するステップであって、前記三角形および/または多角形ファセットは、計算された共通の積集合に隣接し、各三角形および/または各多角形ファセットは、前記各三角形および/または前記各多角形ファセットの独自のジオメトリおよび独自の配向に従って定義される法線ベクトルを有するステップと、所与の三角形ファセットまたは所与の多角形ファセット用に2つの巻き数対p、qを計算するステップと、前記所与の三角形または多角形ファセットから開始して、前記計算された積集合の周りを動径方向に従って回転するステップと、前記計算された積集合に隣接する他の三角形および/または他の多角形ファセットの交差を検出するステップと、各交差の後に、前記交差した三角形および/または前記交差した多角形ファセットの前記法線ベクトルの配向に従って、前記2つの巻き数対p、qを更新するステップとをさらに備えたことを特徴とする請求項3に記載のコンピュータで実行する方法。前記2つの巻き数対を計算するステップにおいて、前記第1の巻き数対Cbelowは、前記三角形および前記多角形ファセットの法線ベクトルに従って、前記三角形および前記多角形ファセットの下であり、前記第2の巻き数対Caboveは、前記三角形および多角形ファセットの前記法線ベクトルに従って、前記三角形および多角形ファセットの上であることを特徴とする請求項1から4の1つに記載のコンピュータで実行する方法。各三角形および各多角形ファセットの前記2つの巻き数対p、qを入力としてもつ前記関数φは、φp,q=min1,pqφp,q=p×qφp,q=max0,p-qという演算の1つを実行することを特徴とする請求項1乃至5のいずれかに記載のコンピュータで実行する方法。前記三角形および前記多角形ファセットは、前記計算された係数kがゼロとは異なるときに選択されることを特徴とする請求項1乃至6のいずれかに記載のコンピュータで実行する方法。前記積集合を計算するステップにおいて、前記第1のモデル化オブジェクトの前記三角形と前記第2のモデル化オブジェクトの前記三角形との間の三角形の共通エッジまたは共通頂点は除外されることを特徴とする請求項1乃至7のいずれかに記載のコンピュータで実行する方法。前記積集合を計算するステップは、精密な算術を用いて実施されることを特徴とする請求項8に記載のコンピュータで実行する方法。前記三角形を分割するステップの後で、前記計算された積集合を表すオーバーレイを計算するステップをさらに含むことを特徴とする請求項1乃至9のいずれかに記載のコンピュータで実行する方法。前記計算されたオーバーレイは、有理座標を有することを特徴とする請求項10に記載のコンピュータで実行する方法。第1のモデル化オブジェクトおよび第2のモデル化オブジェクトから、前記第1のモデル化オブジェクトを第1の三角形分割多面体閉曲面によってモデル化し、前記第2のモデル化オブジェクトを第2の三角形分割多面体閉曲面によってモデル化し、結果として得られる三角形分割多面体閉曲面を計算するコンピュータ可読媒体に記憶されるコンピュータプログラムであって、前記コンピュータプログラムは、請求項1乃至11のいずれか一項に記載の方法をコンピュータに実行させるコード手段を備えたことを特徴とするコンピュータプログラム。第1のモデル化オブジェクトおよび第2のモデル化オブジェクトから、前記第1のモデル化オブジェクトを第1の三角形分割多面体閉曲面によってモデル化し、前記第2のモデル化オブジェクトを第2の三角形分割多面体閉曲面によってモデル化し、結果として得られる三角形分割多面体閉曲面を計算する機器であって、請求項1乃至11のいずれか一項に記載の方法を実行する手段を備えたことを特徴とする機器。本発明は、計算機支援幾何学的デザインシステムにおける、第1のモデル化オブジェクトおよび第2のモデル化オブジェクトから結果として得られる三角形分割多面体閉曲面を計算するコンピュータ実施プロセスを対象とする。第1のモデル化オブジェクトは、第1の三角形分割多面体閉曲面によってモデル化され、第2のモデル化オブジェクトは、第2の三角形分割多面体閉曲面によってモデル化される。このプロセスは、第1のモデル化オブジェクトの三角形と第2のモデル化オブジェクトの三角形との間の積集合を計算するステップを含む。次に、第1のモデル化オブジェクトおよび第2のモデル化オブジェクトの三角形は、その積集合に隣接する多角形ファセットに分割される。次いで、2つの巻き数対p、qと記すが、各三角形および各多角形ファセット用に計算される。各巻き数対の第1の巻き数は、第1の三角形分割多面体閉曲面から計算され、各巻き数対の第2の巻き数は、第2の三角形分割多面体閉曲面から計算される。次いで、係数kと記すが、各三角形および各多角形ファセット用に計算される。この係数は、各三角形および各多角形ファセットの2つの巻き数対p、qと記すを入力としてもつ関数φで計算される。次に、三角形および多角形ファセットが、計算された係数に従って選択される。多角形ファセットは三角形分割され、結果として得られる三角形分割多面体閉曲面が、選択された三角形および三角形分割された選択多角形ファセットを用いて取得される。有利には、本発明は、三角形分割多面体閉曲面によってモデル化されるとともに、たとえば、単体2環などの多面体環として表される第1のモデル化オブジェクトおよび第2のモデル化オブジェクトの間のブール演算を素早く正確に計算するのに適した、一般的、効率的かつ堅牢な方法を提供する。被演算子の有効性チェックは、第1のモデル化オブジェクトおよび/または第2のモデル化オブジェクトが自己積集合をもつかどうかを検証するのにさほど必要がないため、比較的速い。したがって、チェックするための一意の基準は、第1のモデル化オブジェクトおよび第2のモデル化オブジェクトの密閉性である。さらに、この密閉性基準が遵守される場合、本発明は、それゆえに、その結果の品質を保証することができる。言い換えると、第1のモデル化オブジェクトおよび/または第2のモデル化オブジェクトに対する連続的演算は、失敗を発生することなく実施することができる。したがって、いくつかの演算が連続して実行され得るので、堅牢性が増す。さらに、こうした演算は、たとえば、正の巻き数のみを保つことによって、巻き数対を計算することにより取得される内部空間および外部空間の概念のおかげで一般化される。単体的複体とは、点、線分、三角形、およびより一般的にはそのp次元の等価物を貼り合わせることによって構築される位相空間である。単体的複体を使う利点の1つは、こうした複体のプロパティが、任意の次元mに関しても一般化され得ることである。単体的複体は、2008年11月7日の特許文献1の2から5ページに記載されている他の方法より資源を必要としない単純な算術演算によりモデル化オブジェクトの境界を計算することを可能にする。具体的には、単体的複体は、トポロジー的に矛盾のない閉多面体表現を提供する。この表現は、それ自体と交わり得るが、組合せとして密閉である。具体的には、微小摂動または浮動小数点の丸めが出力に適用される場合、有効なトポロジーとして正しく、密閉なままであるので、堅牢性をもたらす。単体的2鎖とは、単体的複体の特定のケースである。3次元ユークリッド空間内の単体的2鎖は、三角形の集合とともに、3D空間内の座標によって与えられる有限の頂点集合によって定義される。各三角形は、頂点のインデックスからなる順序付けられた3つ組と、その多重度を定義する整数とによって定義される。三角形の多重度の符号と、その三角形を定義する組の順序とを同時に変えることからなる演算は、鎖を変えない。単体2環とは、以下で定義されるゼロ境界条件を満足する単体的2鎖である。有利には、立体を表す単体2環の有効性の基準は純粋に組合せであり、すなわち通常の多面体表現とは異なり、数値に依存しないので、本発明は、従来技術と比較して堅牢性を提供する。具体的には、提案される一般化されたブール演算子は、数の丸めに耐性があり、座標の丸めは、被演算子の有効性に影響しない。たとえば、被演算子の頂点に対して、浮動小数点算術計算を使って回転を適用すると、組合せの構造を維持するので、その有効性には影響しない。逆に、最先端の多面体に同じ回転実際には、きわめて通常の演算を適用すると、自己積集合を生じる可能性があるので、最先端の有効性の基準図1を参照して上述したに従うと、その結果は矛盾するものになる。言い換えると、本発明は、頂点座標が整数や浮動小数点などの固定長の数表現を使う単体2環による立体の表現に適合する、一般化されたブール演算子である。一般に、単体2環とは、自己積集合を特徴とし得る三角形分割多面体閉曲面である。ここで図8を参照し、Cで記す単体2環が与えられると、Cの支持集合|C|は、単体2環Cの三角形すべての和集合として定義される。支持集合|C|はしたがって、3D空間R3の部分集合である。図8において、|C|は、2つの自己積集合81、82を特徴とするCの支持集合である。多面体環のすべての三角形の和集合であるものは、多面体環たとえば、Cで記す単体2環の支持集合と定義される。3D空間内の、多面体環の支持集合の補集合の結合された要素は、3Dセルと呼ばれる。1つの3Dセルだけが、境界されず、外部セルと呼ばれる。ここで図9を参照すると、R3-|C|と記す、|C|の3D補集合は、少なくとも2つの結合要素を含む。グレーエリアは、|C|の補集合の結合された要素を表す。4つの結合要素91、92、93、94がある。4つの要素を越えると、外側91には境界がない。|C|の補集合の各点には、図10に示すように、巻き数と呼ばれる、明確に定義された整数が関連づけられる。巻き数は、|C|の補集合の各結合要素92、93、94に対する定数であり、|C|に対してはいかなる巻き数も定義されない。Cと記す、単体2環などの多面体環が与えられると、Cの各三角形が、その3つの頂点によって順序づけによって配向され、この順序づけは法線ベクトルを定義することを思い起こされたい。さらに、Cの各三角形は、整数の多重度をもつ。Cにある任意の三角形にも属さない、3次元空間内の点Xが与えられると、Cに関するXの巻き数は、以下のように定義される整数Wである。説明のために、多面体-環たとえば、単体2環は、ゼロ境界条件と呼ばれる条件を遵守することを思い出されたい。多面体-環がゼロ境界条件を満たすと、密閉特性が多面体-環に授けられる。実際、多面体-環は、符号つき整数をもち、多重度と呼ばれ、各単体に割り当てられ、配向された単体の集合である。たとえば、エッジの多重度は、同じ端頂点を共有する複数のエッジの数である。図10に表すように、Xで始まり、にあるどのエッジとも交わらない、配向された半直線Δを検討する。このような半直線Δは常に存在する。δを、Xから無限大の方を指すΔの向きを定義する単位ベクトルと呼ぶ。Δが、Cにある三角形Tと交わると、Δは、Tの法線nTとのδのドット積が正である場合はTと前方交差し、負である場合は後方交差すると言う。ドット積は、ΔがCにある少なくとも1つのエッジと交わることを意味しており、ゼロになることはない。整数Wを、値W=0で初期化する。Δが、Cにある三角形Tと多重度μTで交差する度に、ΔがTと前方交差する場合はμTのWを増分し、ΔがTと後方交差する場合はμTのWを減分する。このことは、W:=WsignnTδμTと記すことができる。結果として得られる数WX,Cは、所与の点、すなわちCに対する3次元空間内の点Xの巻き数3D巻き数という場合もあると呼ばれる。この数は、半直線Δに依存せず、どの3Dセル内でも一定であり、このことは、WX,Cが同じ3Dセル内のすべての点Xに対して同じ値をもつことを意味する。具体的には、外部セル内のすべての点Xに対してWX,C=0である。本発明は、巻き数概念を利用する。巻き数の概念の2次元バージョンは、従来技術において十分に解説されている。3次元巻き数も、数学的位相次数の適用として、従来技術において解説されており、たとえば、非特許文献7を参照されたい。本説明の残りの部分では、巻き数および3次元巻き数という用語は、区別なく使われる。図10は、自己と二度交わる平面輪郭を用いた巻き数計算を示す。線分の配向が、法線ベクトルを定義する。平面輪郭は、右から左に配向される。半直線Δ上で点Xが与えられると、その巻き数Wの計算は、初期化W:=0を行い、半直線Δに沿ってXから無限大に向かって図の右側に向かって動くことである。この動きの間、輪郭と交差するとき、図に示すように増分W:=W1を行い、または減分W:=W-1を行う。巻き数計算の結果、単体2環Cが、立体を次のように定義する。すなわち、立体は、図11に示すように、正の巻き数をもつ点集合の閉包である。このような単体2環の集合は、頂点が浮動小数点座標をもつ通常の多面体の配向された境界の集合を含む。ただし、従来の多面体境界とは異なり、単体2環は、一般に自己と交わることが認められる。さらに進む前に、内側、外側およびブール演算というよく知られている概念を一般化するためのいくつかの定義が必要である。単体2環Aを図12に、2単体2環Bを図13に示す。3次元オブジェクトを、図12~17、19~23で論じるが、簡略化のために、2次元オブジェクトのみを示してある。ついでながら、図28~30はそれぞれ、図12、図13、および図14、19に示すオブジェクトの3次元表現を示す。Aは矩形であり、Bは二重の三角形である。A、Bは、それぞれの配向および巻き数とともに別々に表される。Aは正であり、正多面体の境界を表す。Bは、自己積集合をもち、したがって、先に論じたように、立体の従来技術の有効性の基準に従って正である。それぞれの巻き数関数を、wA:R3-|A|→ZおよびwB:R3-|B|→Zと記す。φ:Z×Z→Zを、2つの整数を与えられると1つの整数を計算する関数とする。関数φおよび巻き数、すなわちψx=φwAx,wBxを構成することによって、関数ψ:D→Zを定義することとするが、ここでD=R3-|A|∪|B|は、wAおよびwBの両方が明確に定義される3D定義域である。明らかに、関数ψは、D=R3-|A|∪|B|の各結合要素に渡って一定である。関数ψは、すべての0<ε≦ε0に対して、Ox,εと記される、xを中心とする半径εの開球体へのψの制約が一価関数である実数ε0>0が存在する場合、点x∈|A|∪|B|の近傍において局地的に一定であると言われる。言い換えると、関数ψは、x∈|A|∪|B|の各辺において同じ定数値をもつ。次いで、定義により、関数ψの境界δψは、点xの集合∈|A|∪|B|であり、ここでψは局地的に一価ではない。これは、結果として得られる単体2環の幾何学的軌跡を定義する。x∈δψを、ψが局地的に二価である点とする。ψ、ψを、初期被演算子の結果として得られる配向に従って、ψまたはψがδψの正辺またはδψの反対辺における値である、こうした2つの値とする。次いで、差ψ-ψは、点xでの符号つき多重度を定義する。したがって、δψのすべての三角形に対する多重度がセットされる。したがって、2つの単体2環AとBとの間の一般化されたブール演算を定義することは、関数φを定義することである。結果として得られる単体2環はしたがって、三角形の多重度に関連づけられたδψである。ここで図14を参照すると、2つの単体2環A、Bが、演算、たとえば、AとBの和集合の計算のための位置に、D=R3-|A|∪|B|の各結合要素に対する値対wA,wBとともに表されている。値対の第1の数は、単体2環Aから計算され、各巻き数対の第2の巻き数は、単体2環Bから計算される。図15において、値対wA,wBは、関数φを通した結果で置き換えられているが、この結果は、この例では、積φwA,wB=wAwBと定義される。図16において、点線は、関数ψx=wAxwBxが局地的に一価である、|A|∪|B|の部分を表し、|A|∪|B|が、ψが同じ値をもつ2つの領域を、局地的に分離させることを意味する。図17において、図面は、2つの単体2環A、Bに対して実行される演算の結果を表す。すなわち、関数ψが局地的に一価でない|A|∪|B|の部分を保持することによって、新たな環が取得される。初期配向および関数ψの値により、上方の三角形エッジの多重度は、被演算子Bから継承されるエッジに対しては0--1=1、被演算子Aから継承されるエッジに対しては-1-0=-1である。下方の三角形エッジの多重度は、1-0=1である。したがって、2つの単体2環A、Bが与えられ、関数φが与えられると、本発明によるプロセスは、δψによって定義される、単体2環結果を計算する。以下の関数φは、正多面体に対する通常のブール演算を再定義することが理解されよう。すなわち、2つの立体の和集合は関数φp,q=min1,pqによって、積集合は関数φp,q=pqによって、差集合は関数φp,q=max0,p-qによって定義される。さらに、ブール演算子は、何らかの弦誤差基準によって駆動されるエッジ消去手順を適用することによって取得される結果を簡略化し得る。たとえば、座標の丸めによって誘発される摂動と長さが同程度の規模であるエッジは、幾何情報を大幅に損失することなく消去され得る。有利には、本発明のプロセスの結果として得られる単体2環は、自己積集合を特徴とし得る三角形分割多面体閉曲面であるため、2つの単体2環A、Bに対する演算が、境界の自己積集合を誘発しそうな場合であっても、結果は、無効にされない。ここで図18を参照して、本発明によるプロセスの実施形態を説明する。ステップS10、S12で、第1の三角形分割多面体閉曲面によってモデル化された第1のモデル化オブジェクト、および第2の三角形分割多面体閉曲面によってモデル化された第2のモデル化オブジェクトを入力する。通常、第1のモデル化オブジェクトおよび第2のモデル化オブジェクトは、単体2環である。必要であれば、符号つき整数を、第1および第2の三角形分割多面体閉曲面の三角形に関連づけ、配向反転および/または多重度を取り込むことができる。ステップS20で、関数φ:Z×Z→Zを選択する。関数φの選択により、第1のモデル化オブジェクトと第2のモデル化オブジェクトとの間で実行するための演算を選択することができる。一般に、関数φは、2つの立体の和集合、積集合、および差集合など、通常のブール演算を再定義する。本発明を用いるアプリケーションの目的に依存して、どの関数φを定義してもよい。たとえば、空間掃引の結果として得られる自己と交わるオブジェクトを扱うとき、関数φの定義により、対象となっている空間領域は、巻き数が正である場所であると決めることができ、関数φの別の定義により、対象となっている空間領域は、巻き数がゼロでない場所であると決めることができる。通常のブール演算を再定義すると、関数φの制約のない定義は、本発明によって与えられる設計上の柔軟性となる。実際に、関数φは、設計セッション中にユーザによって選択される。関数φは、CAGDシステムによってデフォルトで選択することもできる。次いで、ステップS30で、第1のモデル化オブジェクトの三角形と第2のモデル化オブジェクトの三角形との間の積集合を計算する。積集合とは、2つの三角形が出会う点、エッジまたは多角形である。したがってステップS30は、第1のモデル化オブジェクトまたは第2のモデル化オブジェクトの三角形の共通エッジまたは頂点にはない、三角形の積集合をすべて見つけることである。積集合を計算するのに、いくつかの方法を用いることができ、たとえば、標準浮動小数点算術をイプシロンプログラミングとともに使う。実際に、積集合の計算は、精密な算術を用いて実行される。精密な算術は、数値計算を実行するときに丸めおよび切捨てを利用しない。精密な算術手法を用い、数値的に堅牢な幾何学的アルゴリズムを実行する。有利には、精密な算術は、オブジェクトの正しい位相構造を取得することを可能にするので、こうした構造には矛盾がない。さらに、先に見たように、単体2環とは、自己積集合を特徴とし得る三角形分割多面体閉曲面である。実際に、第1のモデル化オブジェクトおよび/または第2のモデル化オブジェクトは、自己積集合を含み得るので、三角形の間の積集合の計算は、第1のモデル化オブジェクトの三角形の間、および/または第2のモデル化オブジェクトの三角形の間の積集合を計算することをさらに含む。ここで図19を参照すると、2つの単体2環A、Bが入力済みである。第1のオブジェクトAは、図12に示した矩形であり、第2のオブジェクトBは、図13に示した自己積集合を含む二重三角形である。オブジェクトA、Bは、図28~30に示すように、3次元オブジェクトであるが、簡略化のために、図面19~23では2次元オブジェクトが使われることを思い出されたい。実際に、ユーザは、当該分野において公知であるように2つのオブジェクトを入力する。さらに、オブジェクトA、Bは、オブジェクトBがオブジェクトAの上になるように、互いに位置決めされている。通常、この位置決めもユーザによって実行される。図20に、オブジェクトAとオブジェクトBとの間の積集合200、202、204、および206を表してある。さらに、オブジェクトBの自己積集合208も表してある。簡略化のために、オブジェクトA、Bの表現は、図19~23では2D表現であり、3DオブジェクトA、Bの三角形の間で計算される積集合は、エッジまたは頂点であることを思い出されたい。積集合の計算は、当該分野において公知であるように、たとえば、精密な算術を使って実行される。図18に参照を戻すと、ステップS40で、第1のモデル化オブジェクトおよび第2のモデル化オブジェクトの三角形が、その計算された積集合に隣接する多角形ファセットに分割される。つまり、第1のモデル化オブジェクトおよび第2のモデル化オブジェクトA、Bは、ステップS30で計算された積集合に従って細分化されると言う。たとえば、図21において、オブジェクトAとオブジェクトBとの間の計算された積集合は、オブジェクトAを、隣接する4つの部分2、10、4、5に細分化し、オブジェクトBを、隣接する6つの部分1、7、9、3、8、6に分割する。次に、ステップS50で、少なくとも1つの領域を計算する。領域は、互いと隣接するとともに計算された積集合の1つで区切られる三角形および/または多角形ファセットの集合を含む。言い換えると、領域とは、計算された積集合に沿った、第1のモデル化オブジェクトAおよび第2のモデル化オブジェクトBの境界の一部である。つまり、第1のモデル化オブジェクトAおよび第2のモデル化オブジェクトBがその上で出会い、または自己と交わる頂点もしくはエッジに隣接する三角形および/または多角形ファセットの集合が、領域を形成すると言う。実際に、各三角形を多角形ファセットに分割する、計算された積集合の配置のオーバーレイが築かれる。オーバーレイの確立は、当該分野において公知であるように、計算された積集合を組み合わせることになる。この段階で、初期オブジェクトA、Bの各三角形を、オブジェクトA、Bの同じ多面体環を数学的に定義する新規表現が取得されるように、多角形ファセットに細分化される。有利には、多面体環の支持複体は、周囲の3次元空間に組み込まれる。言い換えると、新たな環の多角形ファセットまたはエッジのどの交わるペアも、共通エッジもしくは頂点に沿って交わる。この構築は、精密に行われ、有利には、エッジおよび三角形の積集合、または3つの三角形の積集合の結果として得られる頂点が有理座標をもつことを含意する。新規表現の構築は記号を使って管理されるが、このことは、ほとんどの場合、こうした有理座標が明示的には計算されないことを含意する。有利には、こうした有理座標は計算される必要がないので、CAGDシステムのリソースは維持されるたとえばCPU、メモリなど。一般的でない状況が起こる場合があり、こうした状況は、当該分野において公知であるように解決される。たとえば、三角形が重なる場合があり、いくつかのエッジが同じ点で三角形と交わり、または3つより多い三角形が一地点で出会う場合がある。こうした一般的でない状況の中で、重複三角形が新規多角形ファセットを生じる特定の状況がある。このようなケースでは、計算された新規係数kステップS70で論じるは、2つの重複三角形のそれぞれの係数kの和である。次に、ステップS60で、2つの巻き数対つまり、3D巻き数p、qを、各三角形および各多角形ファセット用に計算する。3次元オブジェクトの巻き数または3D巻き数により、多角形-環の内部空間および外部空間の概念が一般化される。各巻き数対ごとに、第1の巻き数が第1の三角形分割多面体閉曲面から計算され、第2の巻き数が第2の三角形分割多面体閉曲面から計算される。少なくとも一回のレイトレーシングが、このステップで三角形に対して実行される。有利には、完全な堅牢性のために、このステップは、精密な算術および単純さのシミュレーションの両方を必要とする。単純さのシミュレーションは、たとえば、非特許文献8において教示されるように、幾何学的アルゴリズムにおいて縮退ケースに取り組むための技法である。実際に、第1の巻き数対および第2の巻き数対は、それぞれ三角形および多角形ファセットの各辺用に計算される。多角形ファセットの第1の辺同じことが三角形に当てはまるは下と呼ばれ、第2の辺は上と呼ばれる。多角形ファセットの下および上という概念は、各多角形ファセットの法線ベクトルに基づく任意の取り決めに依拠する。実際、多面体環たとえば、単体2環の各三角形は、その3つの頂点の順序づけによって配向され、3つの頂点の順序づけは任意選択であることを思い起こされたい。また、この順序づけが法線ベクトルを定義する。たとえば、図26に、共通エッジEをもつ三角形の集合が表示されている。各三角形は、図に示すように、それ自体の法線ベクトルをもつ。三角形260は配向され、この配向に基づいて、法線ベクトルが定義され、三角形の上を指示する。したがって、Cbelowと記す第1の巻き数対は、その三角形および多角形ファセットの法線ベクトルにより、その三角形および多角形ファセットの下である。反対に、Caboveと記す第2の巻き数対は、その三角形および多角形ファセットの法線ベクトルにより上記三角形および多角形ファセットの上である。図22を参照すると、第1のモデル化オブジェクトAおよび第2のモデル化オブジェクトBの巻き数の値対wA,wBが示されている。オブジェクトBの部分1は、2つの巻き数対をもつ。部分1の第1の対は、Cbelow=0,0と記され、第2の対はCabove=0,-1と記される。この例では、部分1の法線ベクトル図21に表すは、対0,-1を部分1の上であると任意に見なすことを引き起こす。オブジェクトA、Bの他の部分については、下の表で論じる。実際に、ステップS50で計算された各領域に、2つの3D巻き数対を関連づける。第1の巻き数対は、計算された領域の法線ベクトルのすぐ下のCbelow=wA,wBであり、第2の巻き数対は、領域の法線ベクトルのすぐ上のCabove=wA,wBである。計算された各領域に関連づけられる2つの対Cbelow=wA,wBおよびCabove=wA,wBは、その領域に属す多角形ファセットまたは三角形用に計算される2つの巻き数対である。次いで、3D巻き数CbelowおよびCaboveの対は、隣接する領域および三角形に伝播される。伝播という用語は、第1の対Cbelowおよび第2の対Caboveが、計算された新規多角形ファセットおよび/または三角形に広がることを意味する。言い換えると、専用のアルゴリズムを用い、領域の他の多角形ファセットの3D巻き数の対を計算する。このアルゴリズムはしたがって、計算された領域に依拠し、領域に属す多角形ファセットの巻き数対の計算を実行する。このアルゴリズムを、ここで詳述する。このアルゴリズムは、第1の計算領域に属す多角形ファセットまたは三角形のCbelowおよびCaboveの計算で始まる。多角形ファセットの選択は任意であり、このアルゴリズムの出力に影響を与えない。次いで、こうした2つの巻き数対CbelowおよびCaboveの値が、隣接する多角形ファセットに対して計算される伝播されると言うこともできよう。この段階で、隣接する多角形ファセットは、別の計算領域でも三角形でもよい。定義により、2つの多角形は、少なくとも1つのエッジを共有する場合は隣接することを思い起こされたい。さらに、やはり定義により、正確に2つの多角形によって共有されるエッジは、図24に表すように多様体エッジである。やはり定義により、3つ以上の多角形によって共有されるエッジは非多様体エッジである。図25で、非多様体エッジが、4つの付随多角形を有して描画されている。ここで、図26、27を参照して、隣接するファセットの巻き数対CbelowおよびCaboveの計算または伝播について詳述する。図26において、Eを、4つの多角形によって共有される非多様体エッジとする。このエッジは、第1のモデル化オブジェクトAおよび第2のモデル化オブジェクトBとの間の計算された積集合であり、すなわち、2つの水平多角形260、262は第1のモデル化オブジェクトAに属し、2つの垂直多角形264、266は第2のモデル化オブジェクトBに属す。ついでながら、各多角形は、先に論じたように、そのジオメトリおよび配向により法線ベクトルを含むことに気付かれよう。ここで図27を参照し、1つの隣接多角形に対する2つの巻き数対CbelowおよびCabove、たとえば、多角形260の巻き数対Cbelow=wA,wBおよびCabove=wA,wBが分かっていると仮定する。多角形は、エッジEの周りを動径方向にソートされる。動径方向は、エッジEの周りの回転に従って選ぶことができる。たとえば、多角形260から反時計回転268を始めると、エッジEに隣接する多角形の動径方向は、260、266、262、264となる。次いで、所与の三角形または所与の多角形ファセットから開始すると、回転が、計算された積集合の周りを動径方向に従って実行される。これは、多角形260から開始して、多角形266、262、264が連続して交差されることになる。次に、計算された積集合に隣接する他の三角形および/または多角形ファセットの交差が検出される。各交差検出の後、2つの巻き数対が更新される。更新は、交差される三角形および/または多角形ファセットの法線ベクトルの配向に従って実行される。更新を、以下の3つの規則に基づいて実行することができる。i第1のモデル化オブジェクトAの多角形の法線ベクトルが動径方向または反動径方向に配向される場合、その多角形との交差は、巻き数wAをwA1またはwA-1に変える。ii第2のモデル化オブジェクトBの多角形の法線ベクトルが動径方向または反動径方向に配向される場合、その多角形との交差は、巻き数wBをwB1またはwB-1に変える。iii第1のモデル化オブジェクトAまたはBにある多角形との交差は、巻き数wBまたはwAを変えない。図27は、上述した規則の適用を示す。簡略化のために、巻き数対Cabove=wA,wBの計算または伝播に例を限定する。巻き数対Cabove=wA,wBをもつ多角形260から開始すると、最初に交差される多角形は、多角形266である。多角形266の交差が検出されると、巻き数対が更新され、その結果更新により巻き数wBがwB-1に変わる。多角形266の計算された巻き数対はしたがって、Cabove=wA,wB-1となる。同様に、多角形262が交差され、多角形262の計算された巻き数対はそれに従ってCabove=wA1,wB-1となる。次に、多角形264と交差した後、多角形264の計算された巻き数対はCabove=wA1,wBとなる。したがって、巻き数の変動が分かっているので、多様体または非多様体の計算された積集合に隣接する、計算されたすべての領域の巻き数対CbelowおよびCaboveを更新するのは容易である。このアルゴリズムの利点は、巻き数の計算回数が減少することであることが理解されよう。これは、システムのリソースが維持され、計算時間が大きく削減されるので、特に有利である。巻き数対の計算は、拡張領域に対して実施することもできる。拡張領域は、領域に隣接する三角形および/または多角形ファセットの集合を含まない。拡張領域とは、第2のモデル化オブジェクトの多角形とも接せず、自己積集合とも接しない第1のモデル化オブジェクトの隣接三角形の集合からなる。したがって、拡張領域内の三角形のCbelowおよびCaboveの初期値は、同じ拡張領域内ですべての三角形に対して同じであることが理解されよう。つまり、拡張領域は、同じCbelowおよびCaboveをもつモデル化オブジェクトの結合三角形の最大数を含むと言うことができる。したがって、拡張領域内では、計算された初期巻き数対CbelowおよびCaboveは、モデル化オブジェクトの結合三角形全体に容易に計算されることができる伝播すると言うこともできよう。したがって、拡張領域内での計算手順は、モデル化オブジェクトの各結合三角形に対して繰り返される。繰り返しになるが、有利には本発明によるプロセスの性能を向上させ、かつCAGDシステムのリソースを維持することができることが理解されよう。次いで、図18のステップS70で、第1のモデル化オブジェクトおよび第2のモデル化オブジェクトの各三角形および各多角形ファセット用に係数kを計算する。定義により、関数ψの境界δψは、点x∈|A|∪|B|の集合であり、ここでψは局地的に一価ではないので、結果として得られる単体2環δψの幾何学的軌跡を定義すること、ならびにψおよびψは、初期被演算子の結果として得られる配向に従って、ψまたはψがδψの正辺またはδψの反対辺における値である2つの値であることを思い出されたい。次いで、差ψ-ψが、点xでの符号つき多重度を定義し、したがって、δψのすべての三角形に対する多重度が設定される。結果として得られる単体2環はしたがって、三角形の多重度に関連づけられたδψである。多重度により有利には、整数値をもつ関数ψの場合において単体2環が取得され得ることが理解されよう。そうでなければ、関数ψは、0または1のみを値としてもつことになる。係数kは、第1のモデル化オブジェクトおよび第2のモデル化オブジェクトの各三角形および各多角形ファセット用に計算される2つの巻き数対p、qを入力としてもつ関数φで計算される。実際に、係数kは、k=φCbelow-φCaboveのように計算され、これはつまり、第1のモデル化オブジェクトおよび第2のモデル化オブジェクトの各三角形および各多角形ファセットに対する符号つき多重度を計算することである。次に、ステップS80で、第1のモデル化オブジェクトおよび第2のモデル化オブジェクトの三角形および多角形ファセットが、計算された係数に従って選択される。ここでの選択は、選択された三角形および多角形ファセットが、単体2環結果を取得するために保たれることを意味する。実際に、三角形および多角形ファセットは、計算された係数kがゼロとは異なるときに選択される。次に、ステップS90で、三角形ではない多角形ファセットを、三角形分割する。三角形分割は、当該分野において公知であるように実行される。次いで、ステップ100で、結果として三角形分割多面体閉曲面を、選択された三角形および三角形分割された選択多角形ファセットを有して取得する。ステップS60からS100は、図20~23で示される。図20で、オブジェクトAとBとの間の積集合200、202、204、206、210およびオブジェクトBの自己積集合208が表され、第1のモデル化オブジェクトAおよび第2のモデル化オブジェクトBが、計算された積集合に従って細分化される。次いで、図21に、拡張領域を示してある。拡張領域は、図において、数値1から10で識別される。この例では、オブジェクトAの隣接する4つの部分2、10、4、5および部分Bの隣接する6つの部分1、7、9、3、8、6が拡張領域である。ここで、次の表に集められるように、結果として得られる単体2環、すなわちCbelow、Caboveおよびk=φCbelow-φCaboveを選択するのに使われる係数すべてを各拡張領域に関連づけることが可能である。次の表の例では、φwA,wB=wAwBをとる。結果として得られる単体2環に属す拡張領域は、一番右の列に見られる。図23には、拡張領域5、6、7、8、9、10によって定義される、結果として得られる単体2環を示してある。拡張領域5は、上の表中のφCbelow-φCaboveの符号によって取り込まれる反対配向新規配向を示してあるに従って、作用しなければならないことに気付かれよう。こうすることにより、結果として得られる単体2環の面の配向は大域的に矛盾がないことが保証できるようになる。上記方法は、どのCAGDシステムにも適用され得ることを理解されたい。本発明は、システム、方法、またはコンピュータプログラムとして実施することができる。本発明は、デジタル電子回路機構において、もしくはコンピュータハードウェア、ファームウェア、常駐ソフトウェア、マイクロコード、ソフトウェアにおいて、またはその組合せにおいて実施することができる。本発明の装置は、プログラム制御可能なプロセッサによる実行のためにマシン可読記憶装置内で有形に実施されるコンピュータプログラム製品で実施することができる。また、本発明の方法ステップは、入力データに対して作用し出力を生成することによって、本発明の機能を実施するための命令からなるプログラムを実行するプログラム可能プロセッサによって実行することができる。本発明は有利には、データ記憶システム、少なくとも1つの入力装置、および少なくとも1つの出力装置からデータおよび命令を受信するとともに、データおよび命令を送信するように結合された少なくとも1つのプログラム可能プロセッサを含むプログラム可能システム上で実行可能な1つまたは複数のコンピュータプログラムで実施することができる。アプリケーションプログラムは、高度手続き型プログラミング言語もしくはオブジェクト指向プログラミング言語で、または所望される場合はアセンブリ言語もしくはマシン言語で実施することができる。いずれのケースでも、言語は、コンパイラ型言語またはインタープリタ型言語でよい。一般に、プロセッサが、リードオンリメモリおよび/またはランダムアクセスメモリから命令およびデータを受信することになる。1つまたは複数のコンピュータ可読媒体のどの組合せも、命令を記憶するのに使用することができる。コンピュータ可読媒体は、コンピュータ可読記憶媒体でよい。コンピュータ可読記憶媒体は、たとえば、電子、磁気、光学、電磁気、赤外線、または半導体システム、機器、もしくは装置、あるいは上記の適切な任意の組合せだが、それに限定されない。コンピュータプログラム命令およびデータを有形に実施するのに適した記憶装置は、例としてEPROM、EEPROM、およびフラッシュメモリ素子などの半導体メモリ素子と、内部ハードディスクおよび取外し可能ディスクなどの磁気ディスクと、光磁気ディスクと、CD-ROMディスクとを含むすべての形の不揮発性メモリを含む。上記のいずれも、特殊設計ASIC特定用途向け集積回路によって補われ、またはそこに組み込まれ得る。コンピュータ可読媒体は、コンピュータ可読信号媒体でよい。コンピュータ可読信号媒体は、媒体中で実施されるコンピュータ可読プログラムコードをもつ伝播データ信号を、たとえば、ベースバンド中に、または搬送波の一部として含み得る。このような伝播信号は、電磁気、光学、またはこれらの適切な任意の組合せを含むが、それに限定されない様々な形のいずれもとり得る。コンピュータ可読信号媒体は、コンピュータ可読記憶媒体ではなく、命令実行システム、機器、または装置による、またはこれらと関連して使用するためのプログラムを伝達し、伝播し、または移送し得るどのコンピュータ可読媒体でもよい。本発明の好ましい実施形態について記載してきた。本発明の精神および範囲から逸脱することなく、様々な修正が行われ得ることが理解されよう。したがって、他の実施形態も、添付の請求項の範囲内である。たとえば、本発明によるプロセス全体の性能を、最適化により向上させることが可能である。第1の最適化は、たとえば、非特許文献9、非特許文献10および非特許文献11に記載されている、フィルタリングされた述語の概念を用いることにあり得る。さらに、構築された頂点の重心座標は、区間算術で計算される。述語が呼び出される度に、通常は行列式の符号を戻すが、こうした区間座標を使って符号を判定しようとし、この判定が可能でない場合は、述語の有理数演算バージョンを呼び出し、この呼出しが以前行われたことがない場合は、影響を受ける構築された頂点の求められる重心座標を最初に計算する。図18に示すプロセスのステップS30で、第1のモデル化オブジェクトの三角形と第2のモデル化オブジェクトの三角形との間の積集合の計算は、以下のように定義され、パッチと呼ばれる、三角形の集合にある被演算子の区画を使って加速され得る。iパッチの配向された三角形の法線ベクトルすべてをもつ、正のドット積を特徴とするベクトルdが存在する。iiパッチの境界のdと直交する面の上の向きdに沿った投影、自己積集合をもたない。実際、この場合、パッチが自己積集合をもたず、別個のパッチの三角形の間の可能な積集合を検査するのに十分であることが示され得る。こうしたパッチが、ボクセルや八文木などの空間区画構造においてローカライズされる場合、たとえば非特許文献12および非特許文献13に記載されているように、ステップS30は大幅に高速化され得る。たとえば、ボクセルがただ1つのパッチを含む場合、積集合はあり得ない。さらに、別の最適化は、弦誤差によって駆動される一連のエッジ消去によって、結果として結果として得られる三角形分割多面体閉曲面を簡略化するS100ことにあり得る。実際、上記ステップS30~S90で実行される演算は精密であるため、極めて小さい、おそらく入力被演算子の頂点の座標を定義する浮動小数点数の最終桁の重みよりはるかに小さい三角形が起こり得る。本発明のプロセスでは、この簡略化手順は、浮動小数点における数の丸めに相当する組み合わせ物である。"