"コンピューティングデバイスによって実行可能な、対応する物体に関連する1つまたは複数の3次元保護区域を前記コンピューティングデバイスに決定させるための命令を記憶するコンピュータ可読記憶媒体であって、前記命令は、前記物体に関連する隣接する平面を結合する交線を識別することと、隣接する平面の間の交線における外角を凹または凸として分類することと、前記外角が凸と分類される場合に、前記物体の外面の周りに円筒面を決定することであって、前記円筒面が、前記隣接する平面の間の前記交線を中心として半径rの位置に配置される、決定することと、前記外角が凹と分類される場合に、2等分面を用いて前記外角の2等分を決定することと、与えられた円筒面の接平面であり、前記物体から前記距離rにある、前記物体に平行な第1の保護区域平面を提供することと、与えられた2等分面と交差し、前記物体から前記距離rにある、前記物体に平行な第2の保護区域平面を提供することと、および/または隣接する保護区域平面を結合することとの1つまたは複数によって、前記物体に関連する3次元保護区域を決定することととからなる機能を前記コンピューティングデバイスに実行させるのに有効である、コンピュータ可読記憶媒体。前記機能が、前記外角が約180°よりも大きい場合に、隣接する平面の間の前記交線における前記外角を凸として分類することをさらに含む、請求項1に記載のコンピュータ可読記憶媒体。前記機能が、前記外角が約180°よりも小さい場合に、隣接する平面の間の前記交線における前記外角を凹として分類することをさらに含む、請求項1に記載のコンピュータ可読記憶媒体。前記3次元保護区域を決定することが、前記物体の境界を定める平面、直線、球面および円筒面から成る群から選択される構成要素を含む閉領域を、前記距離r未満の距離を有する、前記物体の境界上の点と前記3次元保護区域の境界上の点のペアが存在しないように決定することを含む、請求項1に記載のコンピュータ可読記憶媒体。前記機能が、前記物体の2つの隣接する尖点の間の交線を識別することと、尖点を有する前記物体の隣接する平面を識別することと、前記尖点を有する前記物体の前記隣接する平面の間の交線における外角が、凸と分類される場合に、前記尖点において前記半径rの球面を決定することとをさらに含む、請求項1~4の1項に記載のコンピュータ可読記憶媒体。前記機能が、前記物体からr未満の距離にある保護区域平面の部分を、前記3次元保護区域から除外することをさらに含む、請求項1~4の1項に記載のコンピュータ可読記憶媒体。前記機能が、順次的な方法および/または並列的な方法の1つまたは複数で実行される、請求項1~4の1項に記載のコンピュータ可読記憶媒体。前記機能が、前記物体においてノッチを識別することであって、ノッチが、凸と分類された隣接しない交線において開始および終了する、前記物体の前記面の外側の領域である、識別することをさらに含む、請求項1~4の1項に記載のコンピュータ可読記憶媒体。前記機能が、第2の物体に対する第2の3次元保護区域を決定することと、前記物体および/または前記第2の物体におけるノッチを識別することと、前記3次元保護区域、前記第2の3次元保護区域、ならびに前記物体および/または前記第2の物体における前記ノッチを使用して、前記物体および前記第2の物体の各々が互いの間に最小分離距離しかおかないように、前記物体および前記第2の物体の配置を計算することとをさらに含む、請求項8に記載のコンピュータ可読記憶媒体。対応する物体に関連する1つまたは複数の3次元保護区域を計算するように構成されたシステムであって、物体に関連する情報を記憶するように構成されたメモリであって、前記情報が、前記物体に関連する尖点、交線、および平面の座標を含み、複数の連続する交線が、前記物体に関連する平面を形成する、メモリと、複数のプロセッサであって、前記プロセッサの各々が、隣接する平面および前記隣接する平面の間の直線に関連するそれぞれの情報を前記メモリから受け取るように構成され、前記複数のプロセッサの各々が、隣接する平面と直線の異なるペアに関連する情報を受け取るように構成され、前記複数のプロセッサの各々が、前記隣接する平面の間の前記直線において生成される外角を計算し、前記外角に基づいて、前記隣接する平面の間の前記直線および前記直線に隣接する前記平面の1つに対する保護区域構成要素を決定するように構成される、複数のプロセッサと、前記複数のプロセッサの各々から前記保護区域構成要素に関連する情報を受け取るように構成され、また前記複数のプロセッサの各々からの前記保護区域構成要素に関連する情報を組み合わせることによって、前記物体に関連する3次元保護区域を決定するように構成された出力プロセッサとを備えるシステム。前記複数のプロセッサおよび前記出力プロセッサが、単一のマルチコアプロセッサに関連する、請求項10に記載のシステム。前記複数のプロセッサが、同時読み取りCR命令を使用して、それぞれの隣接する平面および前記隣接する平面の間の前記直線に関連する情報を、前記メモリから受け取るように構成される、請求項10に記載のシステム。前記隣接する平面の間の前記直線に対する前記保護区域構成要素が、前記隣接する平面の間の前記直線における前記外角が凸である場合に、前記直線を中心とする半径rの、前記物体の外面の周りの円筒面であると決定される、請求項10~12の1項に記載のシステム。前記隣接する平面の間の前記直線に対する前記保護区域構成要素が、前記隣接する平面の間の前記直線における前記外角が凹である場合に、前記外角を2等分する平面と交差する、前記物体から距離rにある、前記物体に平行な平面であると決定される、請求項10~12の1項に記載のシステム。前記出力プロセッサが、前記物体に関連する前記3次元保護区域から、与えられた保護区域構成要素の部分を除外するように構成され、前記除外される部分が、前記物体から事前に定められた距離未満の距離にある、請求項10~12の1項に記載のシステム。前記複数のプロセッサが各々、各プロセッサによって決定された前記保護区域構成要素についてのフラグを設定し、前記複数のプロセッサの各々から前記メモリの共用メモリロケーションに前記保護区域構成要素を書き込むために、組み合わせ和同時書き込みCW命令を実行し、前記保護区域が別の保護区域構成要素と重なり合うかどうかを判定し、前記保護区域構成要素が別の保護区域構成要素と重なり合うと判定された場合に、前記保護区域構成要素についての前記フラグをインクリメントするように構成される、請求項10~12の1項に記載のシステム。前記複数のプロセッサが、前記保護区域構成要素を含む前記メモリの前記共用メモリロケーションの内容を同時に読み取り、変更された保護区域構成要素に関連する情報を生成するために、それぞれの保護区域構成要素についての前記フラグがインクリメントされている場合、前記それぞれの保護区域構成要素の部分を除外するように構成される、請求項16に記載のシステム。前記複数のプロセッサが各々、前記変更された保護区域構成要素に関連する前記情報を、前記共用メモリロケーションに同時に書き込むようにさらに構成される、請求項17に記載のシステム。1つまたは複数の物体に関連する保護区域を計算するための方法であって、物体を構成する尖点、交線、および平面の座標を含む、前記物体に関連する情報をメモリに記憶することであって、複数の連続する直線が、前記物体の平面を形成する、記憶することと、複数のプロセッサの各々において、それぞれの交線および対応する隣接する平面に関連する情報を前記メモリから受け取ることであって、前記複数のプロセッサの各々が、隣接する平面と前記隣接する平面の間の交線の異なるペアに関連する情報を受け取るように構成される、受け取ることと、前記複数のプロセッサの各々が、前記隣接する平面の間の前記交線において生成される外角を計算することと、前記外角に基づいて、前記複数のプロセッサの各々が、前記隣接する平面の間の前記交線および前記隣接する平面のうちの1つに対する保護区域構成要素を決定することと、前記複数のプロセッサの各々からの前記保護区域構成要素に関連する情報を組み合わせることによって、前記物体に対する保護区域を決定することと、第2の物体に対する第2の3次元保護区域を決定することと、前記物体および/または前記第2の物体におけるノッチを識別することと、前記3次元保護区域、前記第2の3次元保護区域、ならびに前記物体および/または前記第2の物体における前記ノッチのうちの1つまたは複数を使用して、前記物体および前記第2の物体の各々が互いの間に最小分離距離しかおかないように、前記物体および前記第2の物体の配置を決定することとを含む方法。前記外角が凸と分類される場合、前記保護区域構成要素を決定することが、前記物体の外面の周りに円筒面を決定することであって、前記円筒面が、前記隣接する平面の間の前記直線を中心として半径rの位置に配置される、決定することを含み、前記外角が凹と分類される場合、前記保護区域構成要素を決定することが、2等分面を用いて前記外角の2等分を決定することを含む請求項19に記載の方法。すべての図面は、本明細書で説明する少なくともいくつかの実施形態に従って構成されている。以下の詳細な説明では、本明細書の一部を形成する添付の図面を参照する。図面では、文脈からそうではないと分かる場合を除いて、一般に、同様の記号は、同様の構成要素を識別する。詳細な説明、図面、および特許請求の範囲において説明される例示的な実施形態は、限定的であることを意図していない。本明細書で提示される本発明の主旨または範囲から逸脱することなく、他の実施形態を利用することができ、他の変更を施すことができる。本明細書で一般的に説明され、図に示されるような、本開示の態様は、多種多様な異なる構成で配置、置換、結合、分離、および設計することができ、それらのすべてが本明細書において明示的に企図されていることが容易に理解されよう。本開示は、とりわけ、3D物体のための3次元3D保護区域の計算に関する方法、デバイス、およびシステムに関する。簡潔に述べると、本明細書で一般に開示される技法は、3次元物体の保護区域の計算に関する。いくつかの例では、保護区域は、物体の隣接する平面を結合する交線を識別し、隣接する平面の間の交線における外角を凹または凸として分類することによって計算することができる。いくつかの実施形態では、凸角の場合、隣接する平面の間の交線を中心として、物体の外面の周りに配置される、円筒面を決定することができる。いくつかの実施形態では、凹角の場合、外角は、2等分面を用いて2等分することができる。保護区域は、i与えられた円筒面の接平面である、物体に平行な保護区域平面を提供すること、ii与えられた2等分面と交差する、物体に平行な保護区域平面を提供すること、および/またはiii隣接する保護区域平面を結合することの1つまたは複数によって形成することができる。本明細書で説明する例示的な実施形態は、別々に使用することができ、または場合によっては、組み合わせることができるもしくは部分を組み合わせることができる。図1は、例示的な2次元2D物体102の例示的な保護区域100を示している。示された2D物体102は、時計回りにv1からv27までの名前が付けられた頂点を有する。しかし、もちろん、異なる形状を有する物体は、より多数または少数の頂点を有することができる。保護区域100は、2D計算幾何学の分野において説明される。しかし、2D多角形は、3D物体の断面とすることができ、したがって、例えば、保護区域100は、3D保護区域の断面とすることができる。3D物体の場合、保護区域計算は、次のように定義することができ、3D物体S現実に入手可能な物体を与えた場合、幅rの保護区域Gは、物体Sと境を接する、平面、直線、半径rの球面、および円筒面から成る閉3D空間であって、Sの境界上の点pとGの境界上の点qのペアの中に、ユークリッド距離dp,qがrより小さいペアが存在しないような閉3D空間である。図1に示されるように、2D物体102の境界上の点の中には、保護区域100の境界までの距離が所定の距離rよりも小さい点は存在しない。保護区域100の境界は、保護区域100の境界上の2つのエッジ直線分複数可および/または球状面複数可が保護区域100の内部において交差または通過しないという意味で、領域を表現する。図2は、3D物体200の断面の一部と、本明細書で説明される少なくともいくつかの実施形態に従って配置された、3D物体200の周囲において計算された保護区域202の一部とを示している。図2では、例えば、左から右に向かってv1からv9までの名前が付けられたすべての頂点は、凸頂点convexvertexまたは凹頂点concavevertexに分類することができる。物体は、凸頂点と凹頂点の両方を含むことができ、物体のいくつかの平面は、頂点で交差することができる。立体物の各頂点では、少なくとも3つの平面が交差することができる。例えば、立体物の頂点では、4つ以上の平面が交差することもできる。凹頂点または点は、3D物体200が内側に屈曲する頂点である。立体物Sの頂点vは、2D図では頂点vで合わさる隣接する平面の各ペアの間の、物体の外側の角度すなわち頂点vにおける外角が、180°よりも小さい場合に、凹と定義される。例えば、3D物体200の2D断面の場合、頂点v6とv7を接続する直線は、頂点v5とv6を接続する直線と交差しており、交差する直線の間の、3D物体200の外側の角度は、180°よりも小さい角度として示されている。したがって、頂点v6は、凹頂点と定義される。3D物体200では、頂点v6は、3D物体200の頂点というより、3D物体200の隣接する平面の間の交線上の点とすることができることに留意されたい。同様に、例えば、頂点v4およびv5は、凹頂点である。凸頂点または点は、3D物体200が外側に屈曲する頂点である。2次元では、立体物Sの頂点vは、頂点vで合わさる隣接する平面のペアの間の、物体の外側の角度すなわち頂点vにおける外角が、180°よりも大きい場合に、凸と定義される。例えば、3D物体200の2D断面の場合、頂点v1とv2を接続する直線は、頂点v2とv3を接続する直線と交差しており、交差する直線の間の、3D物体200の外側の角度は、180°よりも大きい角度として示されている。したがって、頂点v2は、凸頂点と定義される。3D物体200では、頂点v2は、3D物体200の頂点というより、3D物体200の隣接する平面の間の交線上の点とすることができることに留意されたい。同様に、例えば、頂点v3、v7、およびv8は、凹点である。凹頂点では、3D物体200の隣接する平面の各ペアは、交差し、交線に沿って180°よりも小さい外角を形成する。凸頂点では、3D物体200の隣接する平面の少なくとも1つのペアは、交差し、交線に沿って180°よりも大きい外角を形成する。図3は、2つの隣接する平面AおよびBが交差し、交差する平面の間に凹外角θが形成された、3D物体の一部を示している。点線は、立体物内部の平面AおよびBの想像上の部分を示している。隣接する平面AおよびBの間の、物体の外側の角度θが、凸であるか、それとも凹であるかを決定するために、法線ベクトルnormalvectorを考えることができる。例えば、平面Aの法線ベクトルはn1であり、平面Bの法線ベクトルはn2である。平面AおよびBの間の角度は、平面AおよびBの法線ベクトルn1およびn2の間の角度と同じである。したがって、平面AおよびBの間の角度θは、以下のように決定することができる。このようにして、物体の外角は、例えば漸近的上限asymptoticupperboundOlの時間内に凹または凸として計算することができ、ここで、lは、例えば、物体の隣接する平面の間の交線の数である。いくつかの例では、凹角および凸角は、式1を使用して、面法線surfacenormalに関して定義することができる。凹角または凸角は、例えば、3D物体の外面に対するものとすることができる。図2を再び参照すると、3D物体200の保護区域202は、頂点を凸または凹に分類することによって決定することができる。頂点を分類するため、3D物体200の隣接する平面の交差によって生成された交線に、l1,l2,...,llと名前を付ける。交線は、v2およびv3が3D物体200の頂点である場合に、頂点v2およびv3を接続する直線のような、隣接する頂点を接続する直線とすることができる。物体の2つの隣接する平面が交差する各交線について、3D物体200の外側の角度は、上記の式1を使用して決定することができる。角度が180°よりも大きい場合、頂点ひいては交線は、凸と見なすことができ、2D断面図では、保護区域を決定するために、半径rの円筒面である円弧を、3D物体200の外側に交線に沿って識別することができる。図2では、これは、例えば、頂点v8において示されている。3D図では、保護区域を決定するために、半径rの円筒面を、3D物体200の外側に交線に沿って描くことができる。そうではなく、式1を使用して決定された角度が180°よりも小さい場合、頂点ひいては交線は、凹と見なすことができ、外角は、交線に沿って2等分される。図2では、2等分線例えばbs1およびbs2が、頂点v4およびv5において示されている。2D断面図では、保護区域を決定するために、その後、3D物体200に外側の距離rのところに、直線が、直線li,li1、1≦i<lに平行して描かれる。3D図では、その後、3D物体200に外側の距離rのところに、平面が、平面li,lil、1≦i<lに平行して描かれる。例えば、交線l34例えば、頂点v3およびv4を接続する直線と交線l45例えば、頂点v4およびv5を接続する直線の場合、2等分線bs1が、頂点v4のところに描かれている。その後、平面が、頂点v3およびv4を接続する平面に平行して描かれ、平面pqをもたらす。平面pqは、例えば、保護区域202の一部と見なすことができる。図4は、3D物体200の断面の一部と、保護区域202の一部とを示している。頂点には、例えば、2D断面のxおよびy座標を表すx1,y1、x2,y2、x3,y3、x4,y4という新たな名前が付けられている。頂点x3,y3は、凹頂点であり、したがって、頂点x3,y3に形成される角度を2等分する2等分線bsを描くことができる。2等分線bsは、点P1からTまでの距離が、点P2からTまでの距離に等しくまたは実質的に等しくなるように描くことができ、この距離は、保護区域距離rに等しい。上で説明したような、頂点が凸か、それとも凹かを決定し、その後、円筒面または平面を描く、これらのステップを使用すると、例えば、隣接する各円筒面および平面を互いに接続することによって、保護区域202を決定し、形成することができる。2D物体の場合、保護区域を決定するために、円弧および直線を互いに結合することができ、2D物体は、3D物体の断面と見なすことができる。したがって、3D物体の場合、例えば、線分は、平面例えば面で置き換えることができ、2D物体の場合に多角形頂点のところに描かれた半径rの円弧は、半径rの円筒面または球面で置き換えることができる。図2に示されるような保護区域202を計算する例が、以下で説明される。図2のエッジv2v3について考える。ここで、頂点v2およびv3は、ともに凸である。v2v3に平行で、長さがv2v3と同じ平面が、頂点v2を中心とする半径rの円筒面または球面とともに、3D物体200の多角形エッジから距離rだけ離れたところに描かれる図2では、平面および面の2D断面を表す直線および円弧が示されている。v2v3に平行な平面は、v2を中心とする半径rの円筒面の接平面である。別の例として、エッジv3v4について考える。ここで、頂点v3は、凸頂点と見なすことができ、頂点v4は、凹頂点と見なすことができる。v3v4に平行な保護区域202の平面の長さは、v4が凹頂点であるので、平面v3v4の長さよりも短い。ここで、保護区域202の平面v3v4も、図2の点pにおいて、v3を中心とする円筒面に接平面として接触し、凹頂点であるv4に近い他の端部では、保護区域202の平面は、以下で述べるように、点qまで引き延ばされる。点qは、平面v3v4およびv4v5の間の角度すなわち頂点v4における角度において描かれた、2等分面bs1との交点である。図2のエッジv4v5について考えると、頂点v4およびv5は、ともに凹頂点であると決定される。保護区域202のこの部分については、円筒面は必要とされない。保護区域202の平面v4v5は、点qから点sまでの平面を決定することによって獲得することができ、ここで、sは、頂点v5を2等分する平面例えば2等分面bs2における点である。保護区域202の平面v4v5の長さは、3D物体200の平面v4v5の長さよりも短い。図5は、3D物体500の断面の例示的な一部と、保護区域502の一部とを示している。この例では、3D物体500の平面v4v5の長さ、ならびに頂点v4およびv5における外角は、2等分面bs1およびbs2の交点fとの間の距離が、平面v3v4およびv5v6に平行な保護区域502の2つの平面の交点gとの間の距離よりも短くなるような大きさである。この場合、平面v4v5に平行な平面として決定される、保護区域502の平面は存在しない。一般に、v4v5のような単一のエッジの代わりに、多角形には、例えば、保護区域の部分が特に計算されない、いくつかのエッジまたはいくつかのノッチが存在することがある。図6は、実線で示された3D物体600の例示的な一部と、点線で示された保護区域602の一部とを示している。図6における図は、3次元で表されている。3D物体600は、3つの連続した平面A、B、およびCを含む。例えば点m-n-o-pは、平面Aを決定し、点o-p-q-rは、平面Bを決定し、点q-r-s-tは、平面Cを決定する。保護区域の平面は、平面A’、B’、およびC’を含む。点m’-n’-o’-p’は、平面A’を決定し、点o’-p’-q-rは、平面B’を決定し、点q’-r’-s’-t’は、平面C’を決定する。保護区域を計算するため、平面AおよびBは、交線o-pに沿って凹角を形成するので、平面AおよびBの間の外角を、平面で2等分することができる。2等分面が、点o-p-u-vによって示されている。その後、開始面図示されずから2等分面まで、平面A’を点m’-n’-o’-p’を用いて決定することができる。平面BおよびCは、交線q-rに沿って凸角を形成し、したがって、保護区域を計算するために、平面BおよびCが合わさった交線であって、交線q-rに沿って凸外角を形成する交線q-rを中心として、例えば、所定の半径値の円筒面q’-r’-r-qを計算することができる。立体物のA-B-Cの各点から、それらの保護区域平面A’-B’-C’の各点までの最小距離は、半径値として与えることができることに留意されたい。半径値は、立体物の外側の保護区域を計算している間、維持することができる。あるいは、半径値は、例えば、保護区域の各部分ごとに調整することができる。半径値は、用途に基づいて変化することができ、例示的な値は、例えば、ナノメートルの範囲にあることができる。凹外角を有する物体の部分について考える場合、物体にノッチが存在することがあり、保護区域を計算するときにノッチを考慮することができる。ノッチ204は、図2に示されるように、多角形の外側に形成され、例えば、頂点v3およびv7を接続する点線の下側の部分である。ノッチは、例えば、物体の偽包絡エッジfalsehulledge、包絡エッジhulledge、凸包convexhull、および凸集合convexsetを使用して、定義することができる。物体は、例えば、物体内のどの点ペアについても、任意の点ペアをつなぐ直線分上のすべての点がやはり物体内に存在し、したがって、すべての点が凸集合を構成する場合に、凸と見なすことができる。凸包は、凸集合の点によって形成された境界であり、多角形の境界を形成する線分の一連の頂点によって表される。したがって、凸包は、平面上の与えられた任意の点の組について、すべての点が境界上または多角形内に存在するような、最小面積の凹外角を有さない凸多角形である。偽包絡エッジは、凸包を獲得する場合に導入される包絡エッジである。例えば、図1を参照すると、頂点v1およびv10、v12およびv16、v20およびv27の間に、点線によって描かれた偽包絡エッジが存在している。同様に、図2を参照すると、頂点v2およびv8の間に、点線によって偽包絡エッジが描かれている。しばしば、ノッチは、偽包絡エッジの2つの頂点において開始および終了する一連の物体Pのエッジで形成される、物体Pの外側の多角形領域と見なすことができる。Pが多角形であり、CHPが多角形Pの凸包を表す場合、CHPおよびPの面積の差は、多角形Pの外側の複数の分離されたノッチから成る。この例では、ノッチは、図2に示されるように、多角形の外側に形成され、頂点v2およびv8を接続する点線の下側の部分である。または、例えば、ノッチは、図1に示されるように、多角形の外側に形成することができ、頂点v1およびv10、v12およびv16、v20およびv27を接続する点線の下側の部分である。ここでは、ノッチは、隣接していない、多角形の2つの連続した凸頂点において開始および終了する、多角形の外側の多角形領域と見なされる。ノッチは、凸頂点例えば、v3において開始し、多角形のエッジおよび頂点を特定の一方向に辿りながら、1つまたは複数の凹頂点例えば、v4、v5、v6を通過し、凸頂点例えば、v7において終了する。したがって、ノッチは、物体のいくつかの交線について凹外角複数可が存在する場合に、形成される。したがって、ノッチ204は、図2に示されるように、多角形の外側に形成され、例えば、頂点v3およびv7を接続する点線の下側の部分である。図7a~eは、各々がノッチを含む立体物の例示的な保護区域G1およびG2の2D図を示している。ノッチの形状が、保護区域G1およびG2において反映されている。保護区域計算を使用して、隣接性および安全な分離距離を維持しながら、2つ以上の立体物を最小の3D空間内に収容することができ、ノッチは、安全な分離距離を獲得することをさらに可能にすることができる。例えば、2つの保護区域G1およびG2の場合、図7b~eに示される例示的なレイアウトなど、物体のいくつかの可能な3D割り当てが存在する。例えば、図7dに示されるレイアウトなど、レイアウトの1つは、最小の空間量しか必要としないことができる。この例では、ノッチの存在が、そのような割り当てを可能にしている。したがって、1組の3D物体の保護区域を計算することができ、その場合、例えば、ノッチを使用して、最小の3D空間内に、物体を割り当てることができる。図8は、物体の3D保護区域を計算するための方法800の例示的な実施形態についてのフローチャートを示している。本明細書で開示されるこのおよび他のプロセスおよび方法について、フローチャートは、本実施形態の1つの可能な実施の機能および動作を示すことを理解されたい。この点に関して、各ブロックは、モジュール、セグメント、またはプログラムコードの部分を表すことができ、それらは、方法における特定の論理機能、アクション、またはステップを実施するための、プロセッサによって実行可能な1つまたは複数の命令を含むことができる。プログラムコードは、例えば、ディスクまたはハードドライブを含む記憶デバイスなど、任意のタイプのコンピュータ可読媒体に記憶することができる。コンピュータ可読媒体は、例えば、レジスタメモリ、プロセッサキャッシュ、およびランダムアクセスメモリRAMのような、データを短期間記憶するコンピュータ可読媒体など、非一時的コンピュータ可読媒体を含むことができる。コンピュータ可読媒体は、例えば、リードオンリメモリROM、光または磁気ディスク、コンパクトディスクリードオンリメモリCD-ROMのような、2次的または永続的な長期記憶など、非一時的媒体も含むことができる。コンピュータ可読媒体は、他の任意の揮発性または不揮発性記憶システムとすることもできる。コンピュータ可読媒体は、例えば、コンピュータ可読記憶媒体、または有形な記憶デバイスと見なすことができる。加えて、図8の各ブロックは、プロセスにおける特定の論理機能を実行するように配線することができる回路を表すことができる。当業者であれば理解するように、含まれる機能に応じて、実質的に同時または逆順を含む、示された順序または説明された順序とは異なる順序で機能が実行され得る代替的な実施も、本開示の例示的な実施形態の範囲内に含まれる。方法800は、1つまたは複数のブロック802、804、806、808、810、812、814、816、818、820、822、824、826、828、830、832、および/または834によって示されるような、1つまたは複数の動作、機能、またはアクションを含むことができる。ブロックは、順次的な順序で示されているが、これらのブロックは、並列で、および/または本明細書で説明する順序とは異なる順序で実行することもできる。また、様々なブロックは、所望の実施に基づいて、組み合わせてより少数のブロックにすること、分割してさらなるブロックを生み出すこと、および/または除去することができる。方法800の処理は、ブロック802物体に関連するデータを受け取り、境界線に名前を付けるにおいて開始することができる。例えば、最初に、物体Sに関連するデータをメモリ内に、またはプロセッサによって受け取ることができ、すべての境界線または隣接する平面の交線にl1,l2,...,llという名前を付けることができる。データは、例えば、1つまたは複数の頂点、直線、形状、長さ、半径などの集まりなどの物体を表す値から成ることができる。図6を参照すると、隣接する平面の例示的な境界線または交線が、直線poとして示されている。ブロック802の後には、ブロック804隣接する平面の交差の角度を識別するが続くことができる。例えば、例えば、データがl本の直線を含む場合直線i=1からl-1について、隣接する平面の交差の角度は、凹または凸として識別することができる。例えば、上で説明した式1をプロセッサによって使用して、角度を凸または凹として識別および/または分類することができる。角度が凸と識別された場合、ブロック804の後には、ブロック806物体の外面の周りに、交差する面の交線を中心とする半径rの円筒面を決定するが続くことができる。例えば、凸角の場合、物体の外面の周りに円筒面を決定することができ、半径rの円筒面は、交差する面の交線を中心とする。図6の図を再び参照すると、交線q-rを中心とする例示的な円筒面q’-r’-r-qを計算および決定することができる。ブロック806の後には、ブロック808隣接する平面の交差の角度を識別するが続くことができる。例えば、方法800は、引き続き、次の隣接する平面li,li1の交差の外角を識別することができる。外角は、やはり、凹または凸として識別することができる。次の外角が凸と識別された場合、ブロック808の後には、ブロック810面が交差する線を中心とする半径rの面を決定するが続くことができる。例えば、角度が凸である場合、物体の外面の周りに、隣接する面によって形成されるその角度の線を中心とする半径rの円筒面を決定することができる。ブロック810の後には、ブロック8122つの円筒面の間に、物体の外面から距離rのところにある平行な平面を決定するが続くことができる。したがって、物体の外面から距離rだけ離れたところにある、例えば、ブロック806および810において描かれた直線liおよびli1のところに描かれた2つの円筒面に共通する接平面である、li,li1に平行な平面を描くことができる。例えば、2つの円筒面を接続する平面が描かれる。ブロック808において識別された角度が凹である場合、ブロック808の後には、ブロック814平面を用いて外角の2等分を決定するが続くことができる。凹角の場合、外角は、平面を用いて2等分することができる。図6の図を再び参照すると、例えば、点o-p-u-vとして2等分面が示されている。ちなみに、2等分面は、保護区域の部分として形成されること、または示されることはなく、むしろ、保護区域の一部を計算するために使用することができる。ブロック814の後には、ブロック816円筒面と2等分面の間に、物体の外面から距離rのところにある平面を決定するが続くことができる。例えば、円筒面と2等分面の間に、物体から距離rだけ離れたところにある、liのところに描かれた円筒面の接平面であり、2等分面と交差する、li,li1に平行な平面が描かれる。したがって、この例では、円筒面の接平面として2等分面まで延びる保護区域の一部のためのエンドポイントとして、2等分面を使用することができる。ブロック804に戻り、交差する隣接平面のペアが凹角を形成する場合、ブロック804の後には、ブロック818平面を用いて外角の2等分を決定するが続くことができる。上で説明したように、いくつかの例では、2等分面は、保護区域の部分として決定されることはなく、むしろ、保護区域の一部を計算するために使用することができる。ブロック818の後には、ブロック820隣接する平面の交差の角度を識別するが続くことができる。次の隣接する平面li,li1の交差の外角について、外角が凹または凸として識別される。次の角度が凸と識別された場合、ブロック820の後には、ブロック822面が交差する線を中心とする半径rの面を決定するが続くことができる。角度が凸である場合、例えば、物体の表面の外側に、交線を中心とする半径rの円筒面が決定される。ブロック822の後には、ブロック8242等分面と円筒面の間に、物体の外面から距離rのところにある平面を決定するが続くことができる。例えば、その場合、物体の外側の物体の平面から距離rだけ離れたところにある、2等分面と交差し、決定された円筒面の接平面である、li,li1に平行な平面が決定される。平面は、物体の保護区域の一部である。次の角度を凹と識別することができる場合、ブロック820の後には、ブロック826平面を用いて外角の2等分を決定するが続くことができる。例えば、ブロック820によって角度が凹と決定された場合、外角は、平面例えば、第2の2等分面を用いて2等分することができ、この平面は、もっぱら保護区域計算の目的で使用することができる。ブロック826の後には、ブロック8282つの2等分面の間に、物体の外面から距離rのところにある平面を決定するが続くことができる。例えば、物体の外側の物体の平面から距離rだけ離れたところにある、第1および第2の2等分面と交差する、li,li1に平行な平面が決定される。平面は、物体の保護区域の一部である。ブロック804~812は、隣接する交線における角度がともに凸角である場合に、保護区域の一部を計算するための例を示し、説明しており、ブロック804~808およびブロック814~816は、隣接する交線における角度が凸角および凹角である場合に、保護区域の一部を計算するための例を示し、説明しており、ブロック804およびブロック818~824は、隣接する交線における角度が凹角および凸角である場合に、保護区域の一部を計算するための例を示し、説明しており、ブロック804、ブロック818~820、およびブロック826~828は、隣接する交線における角度がともに凹角である場合に、保護区域の一部を計算するための例を示し、説明している。ブロック804~828は、ブロック830に示されるように、直線i=1からl-1の各々について繰り返すことができる。ブロック830の後には、ブロック832平面の間の交線の端点endvertexが物体の尖点であると決定される、隣接する平面の間の凸角の場合、頂点の各々において球面を決定するが続くことができる。例えば、平面の間の交線の2つの端点が立体物の2つの尖点であるuおよびvである、物体の2つの隣接する平面の間の凸外角の場合、頂点に関連する保護区域平面が、球面複数可に共通する接平面になるか、または球面と交差するように、頂点uおよびvの各々において、半径rの球面がそれぞれ描かれる。一例では、1組の平面によって覆われる立体物の入力は、3D座標系に関するx、y、z座標およびそれらの隣接する座標として、その尖点によって与えられる。物体の隣接する2つの尖点が、交線を形成し、少なくとも3つの交線が尖点の隣接性に基づいて、3D物体の平面を形成する。説明するように、uおよびvをつなぐ交線が凸外角を形成する場合、物体の外側に交線を中心とする半径rの円筒面が決定され、それ以外の場合、uおよびvをつなぐ交線に沿った外角は2等分され、立体物のuおよびvをつなぐ交線に隣接する関連する平面に対して決定された保護区域平面の各々は、考察中の交線に隣接する物体の平面に対して計算された保護区域平面の各々が、平面から距離rだけ離れたところにあるように2等分面のところで合わさる。頂点uおよびvが尖点である場合、頂点が完全に凸である例えば、尖点で終了する交線の各々が凸外角を形成するならば、uおよびvをつなぐ交線に対して決定される保護区域平面の各々は、尖頭において描かれる半径rの球面に対する接平面になる。他方、そのような尖点が部分的に凸である例えば、尖点で終了する交線のいくつが凸外角を形成し、残りの交線は凹外角を形成するならば、uおよびvをつなぐ凹交線に対する隣接する保護区域平面は、例えば、尖頭において決定される半径rの球面を切る。図9a~dは、球保護区域が決定される尖点を有する例示的な平面を示している。図9a~cは、交線tp、tq、tr、pq、qrを有する3D物体の隣接する平面tpqおよびtqrの一例を示しており、tは、物体の尖点であり、頂点tは、凸である。図9aでは、点線は、物体の一部に対する保護区域を示し、t1p1t2r1は、物体の交線tptrに対する保護区域の表面上の直線である。交線tptrが凸外角を形成する場合、t1p1t2r1は、保護区域の円筒面上にあり、それ以外の場合、t1p1t2r1は、保護区域上、およびtptrに隣接する平面によって形成される凹外角の2等分面上にあることに留意されたい。加えて、t1t2は、物体の凸尖点tに起因する保護区域球面である。図9bでは、交線tqが凸外角を形成することを仮定する一例において、tqを中心とする円筒面t3q1q2t4が形成され、保護区域平面P1すなわちt3q1r1t1およびP2すなわちt4q2p1t2は、円筒面に対する接平面である。さらに、P1およびP2は、凸である尖点tに起因して決定される球保護区域面t1t3t4t2に対する接平面でもある。図9cでは、交線tqが凹外角を形成することを仮定する一例において、tqに沿った角度が2等分され、その2等分面t’q1上に、保護区域平面P3およびP4が出会う直線が存在する。加えて、P3すなわちt’r1q1およびP4すなわちt’q1p1は、t1t’t2に沿ってtに起因する球保護区域面と交差する。図9dは、3D物体の凸尖点に対する球保護区域の例示的な断面図または上面図を示している。この例では、少なくとも11個の平面および11個の交線が、物体の頂点において出会い、それらのうち、隣接する平面の2つのペアが、凹外角を形成する。例えば、図9dには、ab、de、ghを含む、3つの円弧が存在する。これは上面図であるので、各円弧は、円筒面を表し、保護区域の円筒面は、物体の凸外角を形成する2つの隣接する平面に対して獲得される。各断面bcdまたはefgは、物体の2つの隣接する平面に対して形成される凹外角に起因する保護区域部分として獲得される。加えて、物体の少なくとも1つのさらなる平面が存在し、球面に対する接平面である保護区域平面ahが、それに対して決定される。図8を再び参照すると、ブロック832の後には、ブロック834交差し、物体の平面または頂点から距離がr未満しか離れていない、保護区域の部分を除外するが続くことができる。例えば、保護区域の2つの平面、平面と円筒面/球面、または2つの円筒面/球面が交差する場合、物体の外側の物体の平面または頂点から距離がr未満しか離れていない、平面複数可および/または円筒面/球面複数可の部分が除外される。保護区域を計算する方法800の時間計算量について以下で説明する。n個の頂点、l個の交線、およびp個の平面p個の面の凸物体の保護区域は、p個の平面または面、l個の円筒弧、およびn個の球面を有する凸3D領域であり、n=Ol、およびp=Olである。保護区域の平面は、物体の外側から距離rだけ離れて、物体の平面と平行であり、保護区域の2つの隣接する平面は、物体の関連する交線を中心とする半径rの円筒面によって、つなぐことができる。半径rの球面は、各々が、物体の頂点または尖点において計算される保護区域の一部として導入され、保護区域の関連する平面は、円筒面および球面に対する接平面であり、保護区域の円筒部分も、物体の頂点または尖点の近くでは、保護区域の球面になって終了する。結果として、凸立体物の3次元保護区域を計算するのに必要な時間は、nおよびpはlのオーダ例えば、n=Ol、p=Olであるので、Onlp=Olとして近似することができる。物体の交線である、平面の連続する境界線liおよびli1の場合、一方の直線例えばliは、先の反復において、隣接する平面の保護区域を計算するために、すでに考慮されているが、もう一方例えばli1は、検討中の平面の保護区域を計算するために、初めて考慮される。その保護区域が計算されている物体の平面、および凸または凹である角度の場合、すべての計算に一定の時間がかかる。したがって、n個の頂点、l個の交線、およびp個の平面からなる物体の場合、物体の保護区域を計算するのに必要とされる最悪ケースの総時間は、Onlp=Olとして近似することができる。例えば、保護区域のセグメントが計算される物体の平面、交線、および頂点から距離がr未満しか離れていない、計算された保護区域の部分を除外するための、方法800の残りの部分の場合、これは、近似的にOlの時間で実現することができる。例えば、交線および平面に対する保護区域の計算中、保護区域の内側かつ物体の外側の点の座標例えば、x、y、zは、一定の時間で識別することができる。視覚化のため、例えば、特定の強度値を有する色を使用して、座標の位置を示すことができる。あるいは、例えば、他の交線のための、保護区域の新たに計算された領域に座標が含まれる場合、座標に対してフラグを設定し、更新することができる。なお、n個の頂点、l個の交線、およびp個の平面からなる物体の保護区域を計算する下限は、物体の構成要素の各々は少なくとも一度考慮されるので、近似的にΩnlpまたはΩlとすることができる。例えば、n個の頂点、l個の交線、およびp個の平面からなる3D立体物の保護区域を計算する下限は、ΩnlpまたはΩlであり、保護区域を計算する上限は、OnlpまたはOlであるので、例の中で、n個の頂点、l個の交線、およびp個の平面からなる物体の保護区域は、時間最適であり得る漸近的にタイトな限界asymptotictightboundΘnlpまたはΘlの時間で計算することができる。例示的な実施形態では、3D物体の保護区域は、物体の各部分が順次的に検討される、順次的なアルゴリズムを使用して、計算することができる。例えば、3D物体の何らかの構成要素の保護区域は、1つのプロセッサによって実行される順次的なアルゴリズムを使用して、一定の時間で計算することができる。プロセッサは、例えば、隣接する平面とともに、1つの交線の保護区域を計算することができる。順次的なアルゴリズムの全体的な時間計算量は、約Olとすることができ、ここで、lは3D物体の交線の数である。他の例では、3D物体の保護区域は、並列で計算することができ、物体の複数の部分が、同時に検討される。例えば、図8の方法を使用する一例において実行できるような、単一のプロセッサを使用する順次的な方法で、保護区域の計算を実行する代わりに、n個の頂点、l個の交線、およびp個の平面からなる3D物体の保護区域は、分散コンピューティング環境において、複数のプロセッサ例えばOlを使用して計算することができる。図10は、並列処理を使用して3D物体の保護区域を計算するための例示的なシステム1000を示すブロック図である。例示的なシステム1000は、メモリ1002と、プロセッサ1004a~1004lと、プロセッサ1006とを含む。メモリ1002は、例えば、任意の形態のコンピュータ可読媒体またはコンピュータ可読記憶媒体とすることができる。プロセッサ1004a~1004lおよびプロセッサ1006は、例えばマイクロプロセッサμP、マイクロコントローラμC、デジタル信号プロセッサDSP、またはそれらの任意の組み合わせなど、任意のタイプのプロセッサとすることができる。3D図において物体の平面を形成する連続する交線であるl個の交線l1,l2,...,ll、およびm個の平面p1,p2,...,pmなど、物体に関連する情報またはデータは、メモリ1002のOl個の共用メモリロケーションに入力される。3D物体の交線の数に等しい数のプロセッサを使用することができる。この例では、システム1000は、l個のプロセッサ例えば、1004a~1004lを含むことができる。あるいは、示されるように、システム1000は、より多数または少数のプロセッサを含むことができ、3D物体の直線の数に等しい数のプロセッサを計算に使用することができる。システム1000は、例えば、分散コンピューティング環境の一部とすることができ、または分散コンピューティング環境を含むことができる。第1のプロセッサ1004aは、交線li例えば、平面の間の直線と、交線liの生成に係わる隣接する平面pi-1およびpiとに関連するデータを同時に読み取るように構成することができ、liにおいて生成される外角を計算または決定するように構成することができる。プロセッサ1004aは、4つの可能な保護区域計算の1つを検討し、交線liおよび平面piに対する保護区域Gの部分を計算するように適合することができる。図11a~dは、実線で示される3D物体の部分および本明細書で説明される少なくともいくつかの技法に従って決定される点線で示される保護区域の部分の2D断面の4つの例である。図11aでは、平面piは、凸外角を有する2つの端部交線liおよびli1を有する。プロセッサ1004aは、例えば、liおよびli1を中心とする半径rの物体の外側の円筒面を計算し、その後、保護区域の部分についての長さがli,li1と同じであり、liおよびli1において計算された両方の円筒面に共通する接平面である、物体の平面から物体の外側に距離rだけ離れた、piに平行な平面を計算するように構成することができる。図11bでは、平面piは、凸である端部交線liと、凹外角を有する端部交線li1とを有する。プロセッサ1004aは、liを中心とする半径rの物体の外側の円筒面を計算し、li1における角度を2等分し、2等分bsi1を表すように構成することができる。その後、プロセッサ1004aは、例えば、liにおいて描かれた円筒面に対する接平面であり、例えば、直線ci1のような直線においてbsi1と交差する、立体物の平面から立体物の外側に距離rだけ離れた、piに平行な平面を計算するように構成することができる。図11cでは、平面piは、角度が凹である端部交線liと、角度が凸である直線li1とを有する。プロセッサ1004aは、liにおける角度を2等分し、2等分bsiを表し、li1を中心とする半径rの立体物の外側の円筒面を計算するように構成することができる。その後、プロセッサ1004aは、例えば、直線例えば、直線ciにおいてbsiと交差または接触し、li1において計算された円筒面に対する接平面である、物体の平面から物体の外側に距離rだけ離れた、piに平行な平面を計算するように構成することができる。図11dでは、平面piは、外角が凹である2つの端部交線liおよびli1を有する。プロセッサ1004aは、それぞれ、liおよびli1における角度を2等分し、2等分bsiおよびbsi1を表すように構成することができる。その後、プロセッサ1004aは、例えば、直線例えば、直線ciにおいてbsiと、直線例えば、直線ci1においてbsi1と交差または接触する、物体の平面から物体の外側に距離rだけ離れた、piに平行な平面を、bsiおよびbsi1の交線からpiへの距離がrより大きい場合に、計算するように構成することができる。図10に戻ると、プロセッサ1004aは、図11a~dに示されるような4つの可能性の1つを検討し、交線liおよび平面piに対する保護区域Gの部分を計算するように構成することができる。プロセッサ1004a~lの各々は、例えば、それぞれの隣接する交線および隣接する平面に関する情報またはデータを受け取りプロセッサ1004a~lの各々は、交線および隣接する平面の異なるペアを受け取る、図11a~dに示される例示的な構成に基づいて、3D物体の保護区域Gの部分を計算するように適合することができる。プロセッサ1004a~lの各々は、物体の3D保護区域の計算された部分に関連するデータを、例えば、出力プロセッサとすることができるプロセッサ1006に出力するように適合することができる。プロセッサ1006は、例えば、計算された部分に関連するデータを解析し、保護区域の平面セグメント複数可および/または円筒面/球面複数可が立体物の外側で交差する場合、物体の平面、交線、または頂点から距離がr未満しか離れていない、計算された保護区域の平面セグメント複数可および/または円筒面/球面複数可の部分に関するデータを除外するように構成することができる。プロセッサ1006は、例えば、物体の保護区域の全体を表すデータセットを生成するために、保護区域の計算された部分に関連するデータを組み合わせるように構成することもできる。本明細書で説明される例示的なアルゴリズムの時間計算量は、制御ユニットが、それぞれのデータ上ですべてのプロセッサによって同時または実質的に同時に実行される命令を発行する、単一命令ストリーム多重データストリームSIMD:singleinstructionstreammultipledatastream並列コンピューティング環境において、同時読み取り同時書き込みCRCW:concurrentreadconcurrentwrite並列ランダムアクセス機械PRAM:parallelrandomaccessmachineを使用することによって、考えることができる。図10を参照して上で説明したように、物体のl個の交線の座標は、PRAMのOl個の共用メモリロケーションに維持することができる。Ol個のプロセッサによって実行される同時読み取りCR命令を使用して、2つ以上のプロセッサは、同時に同じメモリロケーションから読み取ることができる。例えば、交線li2の座標に関連するデータには、プロセッサpiからpi3がアクセスすることができる。したがって、命令CRが実行される場合、プロセッサPiが交線li-1、li、li1、li2の座標を読み取るなど、Ol個のプロセッサは、Ol個のメモリロケーションの内容を同時に読み取るように適合することができる。これは、Ol個のプロセッサによる排他読み取りER命令を使用して実行することもでき、その場合、プロセッサは、例えば、1対1方式で読み取りを行う目的で、メモリロケーションにアクセスする。ER命令が実行される場合、Ol個のプロセッサの各々が1つのメモリロケーションから読み取り、関連するOl個のメモリロケーションの各々が1つのプロセッサによって読み取られるなど、Ol個のプロセッサは、Ol個の異なるメモリロケーションの内容を同時に読み取る。一例では、CRがERを含むことに留意されたい。その後、プロセッサPiは、平面li-1,li、li,li1、li1,li2すなわち、それぞれpi-1、pi、pi1を計算し、交線liおよびli1における外角を計算するように構成することができる。プロセッサPiは、図11a~dにおいて説明したような、4つの可能な保護区域の1つを決定するように適合することができる。したがって、プロセッサは、角度複数可が凸である場合は、円筒面複数可を計算し、および/または角度複数可が凹である場合は、角度複数可を2等分するように構成することができる。加えて、プロセッサは、計算されている保護区域Gの一部として、物体の平面から物体の外側に距離rだけ離れた、piに平行な平面を計算するように構成することができる。したがって、物体の保護区域は、一定の時間で計算することができ、それは、ノッチ複数可の存在に起因する、重なり合う平面および/または円筒面/球面といったいくつかの冗長な部分を含むことができる。Gの望まない部分を除去するために、Ol個のプロセッサによる組み合わせ和CWcombinedsumCWの形式の同時書き込みCW命令を実行することができ、例えば、2つ以上のプロセッサは、同じメモリロケーションに同時に書き込むことができ、結果として得られるデータの和が、そのメモリロケーションに残される。例えば、CW命令の場合、1組のプロセッサがあるメモリロケーションに同時に書き込むことができるすべての値は、組み合わされて単一の値になり、その後、その値が、そのロケーションに記憶される。CW命令は、結果をメモリロケーションに記憶する前に、いくつかのプロセッサによって書き込まれた値を組み合わせるために、どの関数を使用しているかに応じて、いくつかの形式を取ることができる。これらの形式のいくつかでは、例えば、それぞれ、SUM加算もしくはPRODUCT乗算などの算術関数を使用して、書き込まれる値を組み合わせることができ、またはAND、OR、もしくはEX-ORなどの論理関数を使用して、1組のブール値を組み合わせることができ、またはMAXもしくはMINなどの選択関数を使用して、書き込まれる値の最大値もしくは最小値を選択することができる。一例では、プロセッサPiは、3D物体の平面piとともに、交線liに対する保護区域を計算することを担当することができる。同様に、l個のプロセッサはすべて、同時にタスクを実行する。したがって、組み合わせ和CWの命令に続いて、3D物体の完全な保護区域は、メモリのロケーションにもたらされるデータとして計算される。さらに、CW命令が実行される場合、Ol個のプロセッサは、同時または実質的に同時に1つのメモリロケーションに書き込むことができる。立体物の平面または交線から立体物の外側に距離がr未満しか離れていないGの部分を除外するため、プロセッサPiは、Gの内側かつ物体の外側のプロセッサが担当する領域に対するフラグの値を1に設定することができる。その後、すべてのプロセッサによって同時に計算され、PRAMの第l1の共用メモリロケーションに書き込まれる、Gの内側かつ物体の外側の領域に対して、CW命令が、上で述べたように、Ol個のプロセッサによって実行される。保護区域のいくつかの領域すなわち、Gの内側かつSの外側は、領域が重なり合う場合にインクリメントされるフラグを有することができる例えば、フラグは2以上になることができる。説明のため、強度Iを有する色Cを使用して、Gの領域を立体物から区別することができ、PRAMの第l1の共用メモリロケーションに書き込まれる計算された保護区域のl個の異なる部分を合計した後、例えば、重なり合う領域は、Iとは異なる強度を有する色Cを有することができる。図12a、図12bは、点線で示された保護区域を有する実線で示された3D物体の例示的な断面を示している。3D物体の頂点v2およびv5の間にノッチが形成されており、それぞれv2およびv5を通過する対応する交線l2およびl5が、2r未満の距離にあり、このノッチに対して、点線で示された保護区域が獲得されている。プロセッサPiは、3D物体の平面piとともに、交線liに対する保護区域を計算でき、保護区域の内側かつ立体物の外側においてフラグに1を設定できることが理解できよう。ここでは、v2およびv5の間の距離は2r未満であるので、部分v1-v2-v3および部分v6-v5-v4に対する保護区域は、それらの2D図における点pおよびqにおいて交差するまたは交わる。したがって、すべてのプロセッサによって組み合わせ和CW命令を同時に実行した後、重なり合う領域pq内のフラグは、2にインクリメントされ、一方、重なり合う領域pq外のフラグは、1のままである。図12bに示されるように、交差する点を除いてすなわち、点pおよびqは別として、重なり合う領域pq内の保護区域を除外した後、3D物体のこの部分に対する穴を含むことができる所望の保護区域が計算され、例えば、物体の外側かつ保護区域の内側のフラグは、すべて1である。例えば、フラグ1の代わりに強度Iを有する色Cおよびフラグ2の代わりにI以外の強度を有する同じ色Cを使用できることが理解できよう。1以外のフラグ値またはI以外の強度を有する色Cを有する領域の境界を除外するため、すべてのプロセッサは、CR命令を実行するように適合することができる。例えば、Ol個のプロセッサはすべて、今では全体としていくつかの冗長部分を含むことができる保護区域である、PRAMの第l1の共用メモリロケーションの内容を同時に読み取るように構成することができる。プロセッサの各々は、フラグが1以上に設定された、Gの内側かつ物体の外側の指定された領域についての情報すなわち座標を読み取るように構成することができる。プロセッサPiは、プロセッサが担当する第iの部分以外の、Gに関連する部分のデータを除外する。プロセッサPiは、プロセッサPiによって計算されたGの内側かつ物体の外側の領域が、1以外のフラグを有するいずれかの座標を含むかどうかを検証するように構成することができる。領域が見つからない場合、プロセッサPiは、何のアクションも取らない。それ以外の場合、Piは、座標が1以外のフラグを有する、プロセッサPiによって計算されたGに関連する部分のデータを除外するように構成することができる。例えば、これも、一定の時間で計算することができる。CW命令は、すべてのプロセッサによって同時に計算された保護区域Gの変更された部分を、PRAMの第l1の共用メモリロケーションに書き込むために実行することができる。したがって、立体物Sに対して計算された保護区域Gは、共用メモリの第l1のロケーションにおいて入手可能である。一例では、本明細書で説明する方法の実行時間は、近似的にOlである。Ol個のプロセッサが保護区域の計算に関与するので、方法は、コスト最適とすることができる。例えば、隣接する平面の間にl個の交線を有する立体物の保護区域は、一定の時間で計算することができる。図13~図16は、本明細書で開示される様々な技法に従って、並列処理を使用して、物体の保護区域を計算する一例を示している。図13は、例示的な3D物体を示している。物体は、8個の尖点AからHと、12個の凸交線AB、AD、AF、BC、BG、CD、CH、DE、EF、EH、FG、GHの組と、6個の長方形平面P1<ABCD>、P2<ADEF>、P3<ABGF>、P4<BCHG>、P5<CDEH>、P6<EFGH>とを含み、平面ペア<P1,P6>、<P2,P4>、<P3,P5>は、互いに平行かつ同一である。図13の3D物体の保護区域を計算するため、3D立体物の尖点すなわちAからHの座標に関連するデータを、近隣情報とともに、入力としてシステムにおいて例えば、メモリ内に、またはプロセッサによって受け取ることができる。近隣情報は、ハッシュマップに記憶することができ、そのキーは、頂点識別子であり、値は、近隣頂点識別子を含む集合への参照である。図14は、図13の例示的な3D物体についての例示的なハッシュマップを示している。マッピングは、頂点隣接性に関する情報を提供する。図14の左列は、物体の尖点の各々に対応するキー値としての頂点識別子を含み、右列は、指定されたキー尖点に交線を介して隣接する尖点を含む。システムの出力は、1組の物体であり、各物体は、以下の3つのパラメータ、すなわち、交線、交線に隣接する2つの平面、交線に沿った2つの平面の間の外角凹または凸を含むことができる。出力を提供するため、個々の頂点座標および近隣情報が処理されて、平面を構成する1組の交線を識別する。図13の例の場合、例えば、図15のデータ構造のようなデータ構造を構築することができる。図15は、例示的なハッシュマップを示しており、そのキーは、平面識別子例えばP1からP6であり、値は、図13に示されるような関連する平面を構成する交線を含む集合への参照である。したがって、図15は、平面に隣接する交線に関する情報を含む、図13に示される3D物体についてのハッシュマップである。左列は、物体の平面の各々に対応するキー値としての平面識別子を含み、右列は、平面を含む値としての交線の集合を含む。次に、図15のハッシュマップを処理して、特定の交線に関連する平面を識別することができる。図15のハッシュマップから、識別できる2つの隣接する平面に交線を関連付けることができる例えば、図15では、平面識別子がP1およびP3である2つの異なる交線の集合内に交線ABが存在する。以下の情報、すなわち、交線例えば、AB、2つの平面識別子例えば、ABに隣接するP1およびP3、ならびに交線に沿って2つの隣接する平面の間に形成される外角のタイプ例えば、凹または凸を含むことができる、1組のオブジェクトが構築される。例えば、図14および図15によれば、生成される1組のオブジェクトは、例えば、図16の表に示されるようなものとすることができる。図16は、物体の外角情報とともに、交線に接続する平面識別子を含む表である。平面識別子は、例えば、メタデータとしての、凹または凸の外角情報とともに、関連する交線を伴う。続いて、図16の表に示されるような、交線の個々の要素を処理して、3D物体のそれぞれの部分の保護区域を構築することができる。本明細書で説明する例示的な実施形態を使用して、VLSI設計における構成要素のレイアウトを可能にするために、保護区域を計算することができる。回路構成要素または機能ユニット/モジュールもしくは異なる部分回路のグループ/ブロックは、構成要素間の電気的障害または寄生効果を回避するために、互いに一定の距離をおいて配置するように指定することができる。チップ上の回路構成要素は、3次元空間内の1組の立体物と見なすことができる。各回路構成要素Ciは、幅δiの最小空き区域をCiの周りに維持するように、パラメータδiに関連付けることができる。回路構成要素を収容するために必要とされる空間は、一般に、アイソセティックisotheticな3次元物体とすることができる。立体物に対する指定された幅の保護区域の位置は、例えば、3DVLSI回路の設計において回路構成要素をサイズ変更するために使用することができる。一例として、3DVLSIチップのブロックレベル設計の階層には、k個のモジュールB1,B2,...,Bkを配置することができ、各Biは、残りのブロックBj、j≠iの各々から距離ri、1≦i≦kを必要とする物体と見なすことができる。目的は、k個のブロックすべての最小3D配置を計算することとすることができ、BiおよびBjが隣接して配置される場合、これら2つのブロックの面上のすべての点ペア一方はBiの面上にあり、他方はBjの面上にあるは、maxri,rjの最小分離、または場合によっては、rirjの最小分離にあることができる。部分回路の間の相互接続を達成するため、ブロックは、さらに遠ざけるまたは引き離すことができるが、上で述べた最小分離未満に調整することはできない。保護区域計算は、例えば、3D回路の所望のパッキング密度および/または効率的なレイアウトを達成するように、ブロックのレイアウトを決定するために、使用することができる。いくつかの例では、保護区域または安全区域は、3D立体物のすべての可能な点または断面において計算されないことがある。代わりに、例えば、物体の各断面に沿った保護区域の近似を補間を介して達成するために、3D物体に沿った点または断面を選択することができる。例示的な実施形態では、物体の外側の幅rの3D領域または空間、保護区域を計算することができる。他の例では、物体の内側の幅rの3D領域または空間、保護区域を計算することができる。例えば、3D物体は、中身が詰まっていないことがあり、代わりに、厚さdの中空部分であること、または中空部分を含むことがある。したがって、物体の外側ばかりでなく、内側の保護区域も計算することができる。物体の内側の保護区域を計算するため、本明細書で説明する例示的な方法を実行することができる。3D物体の交線に沿った外角が凸凹である場合、交線に沿った内角は凹凸であることに留意されたい。図17は、物体の保護区域を計算するために構成された例示的なコンピューティングデバイス1700を示すブロック図である。非常に基本的な構成1702では、コンピューティングデバイス1700は、一般に、1つまたは複数のプロセッサ1704と、システムメモリ1706とを含む。メモリバス1708は、プロセッサ1704とシステムメモリ1706の間で通信するために使用することができる。所望の構成に応じて、プロセッサ1704は、マイクロプロセッサμP、マイクロコントローラμC、デジタル信号プロセッサDSP、またはそれらの任意の組み合わせを含むが、それらに限定されない、任意のタイプを取ることができる。プロセッサ1704は、レベル1キャッシュ1710およびレベル2キャッシュ1712などの1つまたは複数のレベルのキャッシングと、プロセッサコア1714と、レジスタ1716とを含むことができる。プロセッサコア1714は、算術論理演算ユニットALU、浮動小数点ユニットFPU、デジタル信号処理コアDSPコア、またはそれらの任意の組み合わせを含むことができる。メモリコントローラ1718も、プロセッサ1704とともに使用することができ、またはいくつかの実施では、メモリコントローラ1718は、プロセッサ1704の内部部品とすることができる。所望の構成に応じて、システムメモリ1706は、RAMなどの揮発性メモリ、ROM、フラッシュメモリなどの不揮発性メモリ、またはそれらの任意の組み合わせを含むが、それらに限定されない、任意のタイプを取ることができる。システムメモリ1706は、一般に、オペレーティングシステム1720と、1つまたは複数のアプリケーション1722と、プログラムデータ1724とを含む。アプリケーション1722は、コンピューティングデバイス1700の構成に応じて、例えば、本明細書で説明する方法のいずれかを実行するように構成できる、アルゴリズム1726を含む。プログラムデータ1724は、例えば、頂点位置または識別子に対応する値1728を含む。いくつかの例示的な実施形態では、アプリケーション1722は、オペレーティングシステム1720上でプログラムデータ1724を用いて動作するように構成することができる。説明したこの基本構成は、図17においては、破線1702内の構成要素によって示されている。コンピューティングデバイス1700は、追加の特徴または機能、ならびに基本構成1702と任意の必要なデバイスおよびインターフェースの間の通信を円滑化するための追加のインターフェースを有することができる。例えば、バス/インターフェースコントローラ1730は、ストレージインターフェースバス1732を介する、基本構成1702と1つまたは複数のデータ記憶装置1732の間の通信を円滑化するために使用することができる。データ記憶装置1732は、取外し式記憶装置1736、非取外し式記憶装置1738、またはそれらの組み合わせとすることができる。取外し式記憶装置および非取外し式記憶装置の例は、いくつかの名前を挙げると、フレキシブルディスクドライブおよびハードディスクドライブHDDなどの磁気ディスク装置、コンパクトディスクCDドライブまたはデジタル多用途ディスクDVDドライブなどの光ディスクドライブ、ソリッドステートドライブSSD、ならびにテープドライブを含む。例示的なコンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータなどの情報を記憶するための任意の方法または技術で実施された、揮発性および不揮発性の取外し式および非取外し式媒体を含むことができる。システムメモリ1706、取外し式ストレージ1736、および非取外し式ストレージ1738はすべて、コンピュータ記憶媒体の例である。コンピュータ記憶媒体またはコンピュータ可読記憶媒体は、RAM、ROM、EEPROM、フラッシュメモリ、もしくは他のメモリ技術、CD-ROM、デジタル多用途ディスクDVD、もしくは他の光ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ、もしくは他の磁気記憶装置、または所望の情報を記憶するのに使用でき、コンピューティングデバイス1700によってアクセスできる他の任意の媒体を含むが、それらに限定されない。そのようなコンピュータ記憶媒体はいずれも、デバイス1700の一部とすることができる。コンピューティングデバイス1700は、バス/インターフェースコントローラ1730を介する、様々なインターフェース装置例えば、出力インターフェース、周辺インターフェース、および通信インターフェースから基本構成1702への通信を円滑化するための、インターフェースバス1740も含むことができる。例示的な出力インターフェース1742は、1つまたは複数のA/Vポート1748を介してディスプレイまたはスピーカなどの様々な外部装置と通信するように構成できる、グラフィック処理ユニット1744およびオーディオ処理ユニット1746を含む。例示的な周辺インターフェース1750は、1つまたは複数のI/Oポート1756を介して入力装置例えば、キーボード、マウス、ペン、音声入力装置、タッチ入力装置などまたは他の周辺装置例えば、プリンタ、スキャナなどなどの外部装置と有線または無線接続を介して通信するように構成できる、シリアルインターフェースコントローラ1752またはパラレルインターフェースコントローラ1754を含む。例示的な通信インターフェース1758は、1つまたは複数の通信ポート1764を介する、ネットワーク通信による、1つまたは複数の他のコンピューティングデバイス1762との通信を円滑化するように構成できる、ネットワークコントローラ1760を含む。通信接続は、通信媒体の一例である。通信媒体は、変調データ信号内のコンピュータ可読命令、データ構造、プログラムモジュール、または他のデータによって一般に具現することができ、任意の情報配送媒体を含む。変調データ信号は、情報を信号内に符号化するような方法で、その特性の1つまたは複数が設定または変更された信号とすることができる。限定することなく、例を挙げると、通信媒体は、有線ネットワークまたは直接配線接続などの有線媒体、ならびに音響、無線周波RF、赤外線IR、および他の無線媒体などの無線媒体を含むことができる。コンピューティングデバイス1700および/またはコンピューティングデバイスの部分は、セルフォン、携帯情報端末PDA、パーソナルメディアプレーヤデバイス、ワイヤレスウェブ視聴デバイス、パーソナルハンドセットデバイス、特定用途デバイス、または上記機能のいずれかを含むハイブリッドデバイスなど、フォームファクタが小さいポータブルまたはモバイル電子デバイスの一部として実施することができる。コンピューティングデバイス1700は、ラップトップコンピュータと非ラップトップコンピュータ構成の両方を含むパーソナルコンピュータとして実施することもできる。図18は、本明細書で提示される少なくともいくつかの実施形態に従って構成される、コンピューティングデバイス上でコンピュータプロセスを実行するためのコンピュータプログラムを含む、例示的なコンピュータプログラム製品1800の概念的な部分図を示す概略図である。例示的なコンピュータプログラム製品1800の例示的な実施形態が、信号伝達媒体1802を使用して提供される。信号伝達媒体1802は、例えば、プロセッサによって実行されたときに、図1~図17に関して上で説明した機能または機能の部分を提供できる、1つまたは複数のプログラミング命令1804を含むことができる。したがって、例えば、フロー図800について言えば、図8のブロック802、804、806、808、810、812、814、816、818、820、822、824、826、828、830、832、および/または834の1つまたは複数の機能は、信号伝達媒体1802に関連する1つまたは複数の命令によって行うことができる。いくつかの例では、信号伝達媒体1802は、ハードディスクドライブ、コンパクトディスクCD、デジタルビデオディスクDVD、デジタルテープ、メモリなどの、しかしそれらに限定されない、コンピュータ可読媒体1806を包含することができる。いくつかの実施では、信号伝達媒体1802は、メモリ、リード/ライトR/WCD、R/WDVDなどの、しかしそれらに限定されない、コンピュータ記録可能媒体1808を包含することができる。いくつかの実施では、信号伝達媒体1802は、デジタルおよび/またはアナログ通信媒体例えば、光ファイバケーブル、導波路、有線通信リンク、無線通信リンクなどなどの、しかしそれらに限定されない、通信媒体1810を包含することができる。したがって、例えば、信号伝達媒体1802は、無線形態の通信媒体1810例えば、IEEE802.11規格に準拠する無線通信媒体によって伝達することができる。1つまたは複数のプログラミング命令1804は、例えば、コンピュータ実行可能および/または論理実施命令とすることができる。いくつかの例では、図17のコンピューティングデバイス1700などのコンピューティングデバイスは、コンピュータ可読媒体1806、コンピュータ記録可能媒体1808、および/または通信媒体1810の1つまたは複数によって、コンピューティングデバイス1700に伝達されたプログラミング命令1804に応答して、様々な動作、機能、またはアクションを提供するように構成することができる。本開示は、様々な態様の例示として意図されている、本出願で説明した特定の実施形態に関して限定されない。当業者には明らかなように、本開示の主旨および範囲から逸脱することなく、多くの変更および変形を行うことができる。本明細書で列挙しているものに加えて、本開示の範囲内にある機能的に等価な方法および装置が、上述の説明から当業者には明らかである。そのような変更および変形は、添付の特許請求の範囲内に包含されることが意図されている。本開示は、添付の特許請求の範囲に加えて、そのような特許請求の範囲に権利が与えられる均等物の全範囲に関してのみ限定される。本開示は、当然様々であり得る、特定の方法、試薬、化合物、合成物、または生体系に限定されないことを理解されたい。本明細書で使用された用語は、特定の実施形態を説明するためのものにすぎず、限定する意図はないことも理解されたい。本明細書における実質的にすべての複数形および/または単数形の用語の使用に対して、当業者は、状況および/または用途に適切なように、複数形から単数形に、および/または単数形から複数形に変換することができる。様々な単数形/複数形の置き換えは、理解しやすいように、本明細書で明確に説明することができる。通常、本明細書において、特に添付の特許請求の範囲たとえば、添付の特許請求の範囲の本体部において使用される用語は、全体を通じてオープンなopen用語として意図されていることが、当業者には理解されよう例えば、用語含むincludingは、含むがそれに限定されないincludingbutnotlimitedtoと解釈されるべきであり、用語有するhavingは、少なくとも有するhavingatleastと解釈されるべきであり、用語含むincludesは、含むがそれに限定されないincludesbutisnotlimitedtoと解釈されるべきである、など。導入される請求項で具体的な数の記載が意図される場合、そのような意図は、当該請求項において明示的に記載されることになり、そのような記載がない場合、そのような意図は存在しないことが、当業者にはさらに理解されよう。例えば、理解の一助として、添付の特許請求の範囲は、導入句少なくとも1つのatleastoneおよび1つまたは複数のoneormoreを使用して請求項の記載を導くことを含む場合がある。しかし、そのような句の使用は、同一の請求項が、導入句1つまたは複数のまたは少なくとも1つのおよびaまたはanなどの不定冠詞を含む場合であっても、不定冠詞aまたはanによる請求項の記載の導入が、そのように導入される請求項の記載を含む任意の特定の請求項を、単に1つのそのような記載を含む実施形態に限定する、ということを示唆していると解釈されるべきではない例えば、aおよび/またはanは、少なくとも1つのまたは1つまたは複数のを意味すると解釈されるべきである。同じことが、請求項の記載を導入するのに使用される定冠詞の使用にも当てはまる。また、導入される請求項の記載で具体的な数が明示的に記載されている場合でも、そのような記載は、少なくとも記載された数を意味すると解釈されるべきであることが、当業者には理解されよう例えば、他の修飾語なしでの2つの記載tworecitationsの単なる記載は、少なくとも2つの記載、または2つ以上の記載を意味する。さらに、A、BおよびC、などの少なくとも1つに類似の慣例表現が使用されている事例では、通常、そのような構文は、当業者がその慣例表現を理解するであろう意味で意図されている例えば、A、B、およびCの少なくとも1つを有するシステムは、Aのみ、Bのみ、Cのみ、AおよびBを共に、AおよびCを共に、BおよびCを共に、ならびに/またはA、B、およびCを共に、などを有するシステムを含むが、それに限定されない。A、B、またはC、などの少なくとも1つに類似の慣例表現が使用されている事例では、通常、そのような構文は、当業者がその慣例表現を理解するであろう意味で意図されている例えば、A、B、またはCの少なくとも1つを有するシステムは、Aのみ、Bのみ、Cのみ、AおよびBを共に、AおよびCを共に、BおよびCを共に、ならびに/またはA、B、およびCを共に、などを有するシステムを含むが、それに限定されない。2つ以上の代替用語を提示する事実上いかなる離接する語および/または句も、明細書、特許請求の範囲、または図面のどこにあっても、当該用語の一方oneoftheterms、当該用語のいずれかeitheroftheterms、または両方の用語bothtermsを含む可能性を企図すると理解されるべきであることが、当業者にはさらに理解されよう。例えば、句AまたはBは、AまたはBあるいはAおよびBの可能性を含むことが理解されよう。加えて、本開示の特徴または態様がマーカッシュグループに関して説明される場合、本開示が、それによって、マーカッシュグループのいずれか個々の要素または要素からなるサブグループに関しても説明されていることを当業者は理解されよう。当業者によって理解されるように、文書による説明を提供することなどに関するありとあらゆる目的のため、本明細書で開示されたすべての範囲は、すべての範囲のありとあらゆる可能な部分範囲および部分範囲の組み合わせも包含する。いずれの列挙された範囲も、当該範囲を十分に説明したものとして、また当該範囲を少なくとも等分に2分割、3分割、4分割、5分割、10分割などすることが可能なものとして容易に認識することができる。非限定的な一例として、本明細書で説明された各範囲は、下位3分の1、中間3分の1、および上位3分の1などに容易に分割することができる。やはり当業者によって理解されるように、最大で、少なくとも、より大きい、より少ないなどのすべての言葉は、挙げられた数を含み、上で説明されたように後で部分範囲に分割できる範囲に言及している。最後に、当業者によって理解されるように、範囲は、各個別要素を含む。したがって、例えば、1つ~3つのセルを有する群は、1つ、2つ、または3つのセルを有する群に言及している。同様に、1つ~5つのセルを有する群は、1つ、2つ、3つ、4つ、または5つのセルを有する群に言及しており、その他についても同様である。本明細書において様々な態様および実施形態が開示されたが、他の態様および実施形態も当業者には明らかである。本明細書において開示された様々な態様および実施形態は、説明を目的としており、限定的であることは意図しておらず、真の範囲および主旨は、以下の特許請求の範囲によって示されている。"