(57)【特許請求の範囲】
【請求項１】
複数のプロセッサとメモリとを有するコンピューティングデバイスによって実行可能な、対応する物体に関連する１つ又は複数の３次元保護区域を前記コンピューティングデバイスに決定させるための命令を有するコンピュータプログラムであって、
前記命令は、
前記物体に関連する隣接する平面を結合する交線を識別することと、
隣接する平面の間の交線における外角を凹又は凸として分類することと、
前記外角が凸と分類される場合に、前記物体の外面の周りに円筒面を決定することであって、前記円筒面が、前記隣接する平面の間の前記交線を中心として半径ｒの位置に配置される、決定することと、
前記外角が凹と分類される場合に、２等分面を用いて前記外角の２等分を決定することと、
前記物体に関連する３次元保護区域を決定することであって、前記３次元保護区域は、（i）与えられた円筒面の接平面であり、前記物体から前記距離ｒにある、前記物体に平行な第１の保護区域平面、（ii）与えられた２等分面と交差し、前記物体から前記距離ｒにある、前記物体に平行な第２の保護区域平面、又は（iii）前記第１及び第２の保護区域平面の結合により構成される、ことと、
からなる機能を前記コンピューティングデバイスに実行させるのに有効であり、
前記命令は、
組み合わせ和同時書き込み命令を実行することにより、各プロセッサが決定した保護区域平面を前記メモリの共用メモリロケーションに書き込むことにより、各プロセッサによって決定された保護区域平面についてのフラグの値をインクリメントすることと、
一つのプロセッサにより決定された一つの保護区域平面が別のプロセッサにより決定された別の保護区域平面に重なり合うか否かを前記フラグの値が１であるか或いは１より大きいかに基づいて判定することと、
からなる機能を前記複数のプロセッサに実行させるのに有効である、コンピュータプログラム。
【請求項２】
前記機能が、前記外角が１８０°よりも大きい場合に、隣接する平面の間の前記交線における前記外角を凸として分類することをさらに含む、請求項１に記載のコンピュータプログラム。
【請求項３】
前記機能が、前記外角が１８０°よりも小さい場合に、隣接する平面の間の前記交線における前記外角を凹として分類することをさらに含む、請求項１に記載のコンピュータプログラム。
【請求項４】
前記３次元保護区域を決定することが、前記物体の境界を定める平面、直線、球面及び円筒面から成る群から選択される構成要素を含む閉領域を、前記距離ｒ未満の距離を有する、前記物体の境界上の点と前記３次元保護区域の境界上の点のペアが存在しないように決定することを含む、請求項１に記載のコンピュータプログラム。
【請求項５】
前記機能が、
前記物体の２つの隣接する尖点の間の交線を識別することと、
尖点を有する前記物体の隣接する平面を識別することと、
前記尖点を有する前記物体の前記隣接する平面の間の交線における外角が、凸と分類される場合に、前記尖点において前記半径ｒの球面を決定することと、
をさらに含む、請求項１乃至請求項４のうち何れか１項に記載のコンピュータプログラム。
【請求項６】
前記機能が、前記物体からｒ未満の距離にある保護区域平面の部分を、前記３次元保護区域から除外することをさらに含む、請求項１乃至請求項４のうち何れか１項に記載のコンピュータプログラム。
【請求項７】
前記機能の各段階は、一つのコンピューティングデバイスにより順次実行されるか、又は複数のコンピューティングデバイスにより並列的に実行される、請求項１乃至請求項４のうち何れか１項に記載のコンピュータプログラム。
【請求項８】
前記機能が、前記物体においてノッチを識別することであって、ノッチが、凸と分類された隣接しない交線において開始及び終了する、前記物体の前記面の外側の領域である、識別することをさらに含む、請求項１乃至請求項４のうち何れか１項に記載のコンピュータプログラム。
【請求項９】
前記機能が、
第２の物体に対する第２の３次元保護区域を決定することと、
前記物体及び／又は前記第２の物体におけるノッチを識別することと、
前記３次元保護区域、前記第２の３次元保護区域、並びに前記物体及び／又は前記第２の物体における前記ノッチを使用して、前記物体及び前記第２の物体の各々が互いの間に最小分離距離しかおかないように、前記物体及び前記第２の物体の配置を計算することと、
をさらに含む、請求項８に記載のコンピュータプログラム。
【請求項１０】
対応する物体に関連する１つ又は複数の３次元保護区域を計算するように構成されたシステムであって、
物体に関連する情報を記憶するように構成されたメモリであって、前記情報が、前記物体に関連する尖点、交線、及び平面の座標を含み、複数の連続する交線が、前記物体に関連する平面を形成する、メモリと、
複数のプロセッサであって、
前記物体に関連する隣接する平面を結合する交線を識別することと、
隣接する平面の間の交線における外角を凹又は凸として分類することと、
前記外角が凸と分類される場合に、前記物体の外面の周りに円筒面を決定することであって、前記円筒面が、前記隣接する平面の間の前記交線を中心として半径ｒの位置に配置される、決定することと、
前記外角が凹と分類される場合に、２等分面を用いて前記外角の２等分を決定することとを実行するように構成された複数のプロセッサと、
前記物体に関連する３次元保護区域を決定するように構成された出力プロセッサであって、前記３次元保護区域は、（i）与えられた円筒面の接平面であり、前記物体から前記距離ｒにある、前記物体に平行な第１の保護区域平面、（ii）与えられた２等分面と交差し、前記物体から前記距離ｒにある、前記物体に平行な第２の保護区域平面、又は（iii）前記第１及び第２の保護区域平面の結合により構成される、出力プロセッサと、を備え、
前記複数のプロセッサは、
組み合わせ和同時書き込み命令を実行することにより、各プロセッサが決定した保護区域平面を前記メモリの共用メモリロケーションに書き込むことにより、各プロセッサによって決定された保護区域平面についてのフラグの値をインクリメントすることと、
一つのプロセッサにより決定された一つの保護区域平面が別のプロセッサにより決定された別の保護区域平面に重なり合うか否かを前記フラグの値が１であるか或いは１より大きいかに基づいて判定することと、
を実行するように構成される、システム。
【請求項１１】
前記複数のプロセッサ及び前記出力プロセッサは、単一のマルチコアプロセッサで構成されている、請求項１０に記載のシステム。
【請求項１２】
前記複数のプロセッサが、同時読み取り（ＣＲ）命令を使用して、それぞれの隣接する平面及び前記隣接する平面の間の前記直線に関連する情報を、前記メモリから受け取るように構成される、請求項１０に記載のシステム。
【請求項１３】
前記出力プロセッサが、前記物体に関連する前記３次元保護区域から、与えられた保護区域構成要素の部分を除外するように構成され、前記除外される部分が、前記物体から事前に定められた距離未満の距離にある、請求項１０又は請求項１１に記載のシステム。
【請求項１４】
前記複数のプロセッサは、一つの保護区域平面が別の保護区域平面に重なり合うとの決定に応答して、前記一つの保護区域平面を除外して、変更された保護区域平面に関連する情報を生成する、請求項１０に記載のシステム。
【請求項１５】
前記複数のプロセッサが各々、前記変更された保護区域平面に関連する前記情報を、前記共用メモリロケーションに同時に書き込むようにさらに構成される、請求項１４に記載のシステム。
【請求項１６】
１つ又は複数の物体に関連する保護区域を計算するための方法であって、
物体を構成する尖点、交線、及び平面の座標を含む、前記物体に関連する情報をメモリに記憶することであって、複数の連続する直線が、前記物体の平面を形成する、記憶することと、
複数のプロセッサが、前記物体に関連する隣接する平面を結合する交線を識別することと、
前記複数のプロセッサが、隣接する平面の間の交線における外角を凹又は凸として分類することと、
前記外角が凸と分類される場合に、前記複数のプロセッサが、前記物体の外面の周りに円筒面を決定することであって、前記円筒面が、前記隣接する平面の間の前記交線を中心として半径ｒの位置に配置される、決定することと、
前記外角が凹と分類される場合に、前記複数のプロセッサが、２等分面を用いて前記外角の２等分を決定することと、
出力プロセッサが、前記物体に関連する３次元保護区域を決定することであって、前記３次元保護区域は、（i）与えられた円筒面の接平面であり、前記物体から前記距離ｒにある、前記物体に平行な第１の保護区域平面、（ii）与えられた２等分面と交差し、前記物体から前記距離ｒにある、前記物体に平行な第２の保護区域平面、又は（iii）前記第１及び第２の保護区域平面の結合により構成される、ことと、
前記複数のプロセッサが、組み合わせ和同時書き込み命令を実行することにより、各プロセッサが決定した保護区域平面を前記メモリの共用メモリロケーションに書き込むことにより、各プロセッサによって決定された保護区域平面についてのフラグの値をインクリメントすることと、
前記複数のプロセッサが、一つのプロセッサにより決定された一つの保護区域平面が別のプロセッサにより決定された別の保護区域平面に重なり合うか否かを前記フラグの値が１であるか或いは１より大きいかに基づいて判定することと、
第２の物体に対する第２の３次元保護区域を決定することと、
前記物体及び／又は前記第２の物体におけるノッチを識別することであって、前記ノッチが、凸と分類された隣接しない交線において開始及び終了する、前記物体及び／又は前記第２の物体の前記面の外側の領域である、ことと、
前記３次元保護区域、前記第２の３次元保護区域、並びに前記物体及び／又は前記第２の物体における前記ノッチのうちの１つ又は複数を使用して、前記物体及び前記第２の物体の各々が互いの間に最小分離距離しかおかないように、前記物体及び前記第２の物体の配置を決定することと、
を含む方法。
【発明の詳細な説明】
【技術分野】
【０００１】
関連出願の参照
本出願は、２０１１年１月７日にインドにおいて出願された、出願番号１９／ＫＯＬ／２０１１の対応する特許出願の優先権を主張し、同特許出願の全内容は、参照により本明細書に組み込まれる。
【背景技術】
【０００２】
本明細書において別途指摘がない限り、本節で説明される手法は、本出願の特許請求の範囲の先行技術ではなく、本節に含まれることによって、先行技術であると認められることはない。
【０００３】
超大規模集積（ＶＬＳＩ）回路の設計は、間違いを犯しやすく、時間のかかる、面倒な仕事であり得る。３次元（３Ｄ）集積回路の設計を容易にするため、あらかじめ設計された部分回路またはモジュールを使用することがある。ブロックレベルの回路設計では、モジュールの配置は、例えば、電気的障害（またはクロストーク）、熱の発生、および伝搬信号の遅延などの、性能要因を考慮する。そのような動作上のリスクを最低限に抑えるため、モジュールは、互いの間に安全な距離をおいて配置することができるが、この距離は、所望の性能要因に応じて変化することがある。それと同時に、モジュールは、ＶＬＳＩ回路を実現するのに必要とされる空間の総量が最適化されるように、ごく接近して配置されることがある。ブロックは、ブロックを接続するのに必要とされる配線を最短化するために、ごく接近して配置されることもある。
【０００４】
フィーチャサイズを小さくし（例えば、マイクロメートルからナノメートル）、チップ寸法を大きくする（例えば、数百万のトランジスタの組み込み）ことを求める要求の結果、技術は、２Ｄから３Ｄに変化し、例えば、設計において、相互接続遅延が増大し、パワーバジェットが高まったせいで、ＶＬＳＩ回路を設計する際の課題が増加した。課題は、例えば、３Ｄ設計における、面積または空間の最小化および相互接続レイヤの最小化などの要因から、３Ｄ寄生を伴う信号干渉、信号伝搬遅延、および熱危険性などのいくつかの性能要件にまで、多方面にわたる。
【発明の概要】
【０００５】
３次元物体に関連する保護区域の計算に一般に関する技法が開示される。本開示のいくつかの例では、対応する物体に関連する１つまたは複数の３次元保護区域をコンピューティングデバイスに決定させる、コンピューティングデバイスによって実行可能な命令を記憶する、コンピュータ可読記憶媒体が提供される。命令は、物体に関連する隣接する平面を結合する交線を識別することと、隣接する平面の間の交線における外角を凹または凸として分類することとを含むことができる機能をコンピューティングデバイスに実行させるのに有効とすることができる。いくつかの例では、外角が凸と分類される場合、機能は、物体の外面の周りに円筒面を決定することを含むことができ、円筒面は、隣接する平面の間の交線を中心として半径ｒの位置に配置することができる。いくつかの例では、外角が凹と分類される場合、機能は、２等分面を用いて外角の２等分を決定することを含むことができる。加えて、機能は、与えられた円筒面の接平面であり、物体から距離ｒにある、物体に平行な第１の保護区域平面を提供すること、与えられた２等分面と交差し、物体から距離ｒにある、物体に平行な第２の保護区域平面を提供すること、および／または隣接する保護区域平面を結合することの１つまたは複数によって、物体の３次元保護区域を決定することを含むことができる。
【０００６】
さらなる例は、対応する物体に関連する１つまたは複数の３次元保護区域を計算するように構成されたシステムを含むことができる。システムは、メモリと、複数のプロセッサと、出力プロセッサとを備える。メモリは、物体に関連する直線および平面の座標を含む、物体に関連する情報を記憶するように構成することができ、複数の連続する直線は、物体に関連する平面を形成することができる。複数のプロセッサの各々は、隣接する平面および隣接する平面の間の直線に関連するそれぞれの情報をメモリから受け取るように構成することができ、複数のプロセッサの各々は、隣接する平面と直線の異なるペアに関連する情報を受け取るように構成することができる。複数のプロセッサの各々は、隣接する平面の間の直線において生成される外角を計算し、外角に基づいて、隣接する平面の間の直線に対する保護区域構成要素を決定するように構成することができる。出力プロセッサは、複数のプロセッサの各々から保護区域構成要素に関連する情報を受け取り、複数のプロセッサの各々からの保護区域構成要素に関連する情報を組み合わせることによって、物体に関連する３次元保護区域を決定するように構成することができる。
【０００７】
さらなる例は、１つまたは複数の物体に関連する保護区域を計算するための方法を含むことができる。方法は、物体を構成する直線および平面の座標を含む、物体に関連する情報をメモリに記憶することを含むことができ、複数の連続する直線が、物体の平面を形成する。方法は、複数のプロセッサの各々において、それぞれの隣接する平面および隣接する平面の間の直線に関連する情報をメモリから受け取ることも含むことができ、複数のプロセッサの各々は、隣接する平面と直線の異なるペアに関連する情報を受け取るように構成することができる。方法は、複数のプロセッサの各々が、隣接する平面の間の直線において生成される外角を計算することと、外角に基づいて、複数のプロセッサの各々が、隣接する平面の間の直線に対する保護区域構成要素を決定することとをさらに含むことができる。方法は、複数のプロセッサの各々からの保護区域構成要素に関連する情報を組み合わせることによって、物体に対する保護区域を決定することも含むことができる。方法は、第２の物体に対する第２の３次元保護区域を決定することと、物体および／または第２の物体におけるノッチを識別することと、３次元保護区域、第２の３次元保護区域、ならびに物体および／または第２の物体におけるノッチのうちの１つまたは複数を使用して、物体および第２の物体の各々が互いの間に最小分離距離しかおかないように、物体および第２の物体の配置を決定することとをさらに含むことができる。
【０００８】
上述の要約は、例示的なものにすぎず、限定的であることは決して意図していない。上で説明した例示的な態様、実施形態、および特徴に加えて、さらなる態様、実施形態、および特徴が、図面および以下の詳細な説明を参照することによって明らかになろう。
【図面の簡単な説明】
【０００９】
【図１】例示的な２次元（２Ｄ）物体１０２の例示的な保護区域を示す図である。
【図２】３Ｄ物体の断面の一部と、３Ｄ物体の周囲において計算された保護区域の一部とを示す図である。
【図３】２つの隣接する平面ＡおよびＢが交差し、交差する平面の間に凹（外）角θが形成された、３Ｄ物体の一部を示す図である。
【図４】３Ｄ物体の断面の一部と、保護区域の一部とを示す図である。
【図５】３Ｄ物体の断面の例示的な一部と、保護区域の一部とを示す図である。
【図６】（実線で示された）３Ｄ物体の例示的な一部と、（点線で示された）保護区域の一部とを示す図である。
【図７】各々がノッチを含む立体物（solid object）の例示的な保護区域Ｇ１およびＧ２の２Ｄ図である。
【図８】物体の３Ｄ保護区域を計算するための方法の例示的な実施形態についてのフローチャートである。
【図９】球保護区域が形成される尖点（peak vertex）を有する例示的な平面を示す図である。
【図１０】並列処理を使用して３Ｄ物体の保護区域を計算するための例示的なシステムを示すブロック図である。
【図１１】（実線で示される）３Ｄ物体の部分および（点線で示される）保護区域の部分の２Ｄ断面の４つの例の１つを示す図である。
【図１２ａ】（点線で示された）保護区域を有する（実線で示された）３Ｄ物体の例示的な断面を示す図である。
【図１２ｂ】（点線で示された）保護区域を有する（実線で示された）３Ｄ物体の例示的な断面を示す図である。
【図１３】例示的な３Ｄ物体を示す図である。
【図１４】図１３の例示的な３Ｄ物体についての例示的なハッシュマップを示す図である。
【図１５】キーが平面識別子（例えばＰ１からＰ６）であり、値が図１３に示されるような関連する平面を構成する交線を含む集合への参照である、例示的なハッシュマップを示す図である。
【図１６】物体の外角情報とともに、交線に接続する平面識別子を含む表である。
【図１７】物体の保護区域を計算するために構成された例示的なコンピューティングデバイスを示すブロック図である。
【図１８】コンピューティングデバイス上でコンピュータプロセスを実行するためのコンピュータプログラムを含む、例示的なコンピュータプログラム製品の概念的な部分図を示す概略図である。
【発明を実施するための形態】
【００１０】
すべての図面は、本明細書で説明する少なくともいくつかの実施形態に従って構成されている。
【００１１】
以下の詳細な説明では、本明細書の一部を形成する添付の図面を参照する。図面では、文脈からそうではないと分かる場合を除いて、一般に、同様の記号は、同様の構成要素を識別する。詳細な説明、図面、および特許請求の範囲において説明される例示的な実施形態は、限定的であることを意図していない。本明細書で提示される本発明の主旨または範囲から逸脱することなく、他の実施形態を利用することができ、他の変更を施すことができる。本明細書で一般的に説明され、図に示されるような、本開示の態様は、多種多様な異なる構成で配置、置換、結合、分離、および設計することができ、それらのすべてが本明細書において明示的に企図されていることが容易に理解されよう。
【００１２】
本開示は、とりわけ、３Ｄ物体のための３次元（３Ｄ）保護区域の計算に関する方法、デバイス、およびシステムに関する。簡潔に述べると、本明細書で一般に開示される技法は、３次元物体の保護区域の計算に関する。いくつかの例では、保護区域は、物体の隣接する平面を結合する交線を識別し、隣接する平面の間の交線における外角を凹または凸として分類することによって計算することができる。いくつかの実施形態では、凸角の場合、隣接する平面の間の交線を中心として、物体の外面の周りに配置される、円筒面を決定することができる。いくつかの実施形態では、凹角の場合、外角は、２等分面を用いて２等分することができる。保護区域は、（ｉ）与えられた円筒面の接平面である、物体に平行な保護区域平面を提供すること、（ｉｉ）与えられた２等分面と交差する、物体に平行な保護区域平面を提供すること、および／または（ｉｉｉ）隣接する保護区域平面を結合することの１つまたは複数によって形成することができる。本明細書で説明する例示的な実施形態は、別々に使用することができ、または場合によっては、組み合わせることができる（もしくは部分を組み合わせることができる）。
【００１３】
図１は、例示的な２次元（２Ｄ）物体１０２の例示的な保護区域１００を示している。示された２Ｄ物体１０２は、時計回りにｖ１からｖ２７までの名前が付けられた頂点を有する。しかし、もちろん、異なる形状を有する物体は、より多数または少数の頂点を有することができる。保護区域１００は、（２Ｄ）計算幾何学の分野において説明される。しかし、２Ｄ多角形は、３Ｄ物体の断面とすることができ、したがって、例えば、保護区域１００は、３Ｄ保護区域の断面とすることができる。
【００１４】
３Ｄ物体の場合、保護区域計算は、次のように定義することができ、３Ｄ物体Ｓ（現実に入手可能な物体）を与えた場合、（幅ｒの）保護区域Ｇは、物体Ｓと境を接する、平面、直線、（半径ｒの）球面、および円筒面から成る閉（３Ｄ）空間であって、（Ｓの境界上の）点ｐと（Ｇの境界上の）点ｑのペアの中に、ユークリッド距離ｄ（ｐ，ｑ）がｒより小さいペアが存在しないような閉（３Ｄ）空間である。図１に示されるように、２Ｄ物体１０２の境界上の点の中には、保護区域１００の境界までの距離が所定の距離ｒよりも小さい点は存在しない。保護区域１００の境界は、保護区域１００の境界上の２つのエッジ（直線分（複数可）および／または球状面（複数可））が保護区域１００の内部において交差（または通過）しないという意味で、領域を表現する。
【００１５】
図２は、３Ｄ物体２００の断面の一部と、本明細書で説明される少なくともいくつかの実施形態に従って配置された、３Ｄ物体２００の周囲において計算された保護区域２０２の一部とを示している。図２では、（例えば、左から右に向かってｖ１からｖ９までの名前が付けられた）すべての頂点は、凸頂点（ｃｏｎｖｅｘ  ｖｅｒｔｅｘ）または凹頂点（ｃｏｎｃａｖｅ  ｖｅｒｔｅｘ）に分類することができる。物体は、凸頂点と凹頂点の両方を含むことができ、物体のいくつかの平面は、頂点で交差することができる。立体物の各頂点では、少なくとも３つの平面が交差することができる。例えば、立体物の頂点では、４つ以上の平面が交差することもできる。
【００１６】
凹頂点（または点）は、３Ｄ物体２００が内側に屈曲する頂点である。立体物Ｓの頂点ｖは、（２Ｄ図では）頂点ｖで合わさる隣接する平面の各ペアの間の、物体の外側の角度（すなわち頂点ｖにおける外角）が、１８０°よりも小さい場合に、凹と定義される。例えば、３Ｄ物体２００の２Ｄ断面の場合、頂点ｖ６とｖ７を接続する直線は、頂点ｖ５とｖ６を接続する直線と交差しており、交差する直線の間の、３Ｄ物体２００の外側の角度は、１８０°よりも小さい角度として示されている。したがって、頂点ｖ６は、凹頂点と定義される。３Ｄ物体２００では、頂点ｖ６は、３Ｄ物体２００の頂点というより、３Ｄ物体２００の隣接する平面の間の交線上の点とすることができることに留意されたい。同様に、例えば、頂点ｖ４およびｖ５は、凹頂点である。
【００１７】
凸頂点（または点）は、３Ｄ物体２００が外側に屈曲する頂点である。２次元では、立体物Ｓの頂点ｖは、頂点ｖで合わさる隣接する平面のペアの間の、物体の外側の角度（すなわち頂点ｖにおける外角）が、１８０°よりも大きい場合に、凸と定義される。例えば、３Ｄ物体２００の２Ｄ断面の場合、頂点ｖ１とｖ２を接続する直線は、頂点ｖ２とｖ３を接続する直線と交差しており、交差する直線の間の、３Ｄ物体２００の外側の角度は、１８０°よりも大きい角度として示されている。したがって、頂点ｖ２は、凸頂点と定義される。３Ｄ物体２００では、頂点ｖ２は、３Ｄ物体２００の頂点というより、３Ｄ物体２００の隣接する平面の間の交線上の点とすることができることに留意されたい。同様に、例えば、頂点ｖ３、ｖ７、およびｖ８は、凹点である。
【００１８】
凹頂点では、３Ｄ物体２００の隣接する平面の各ペアは、交差し、（交線に沿って）１８０°よりも小さい外角を形成する。凸頂点では、３Ｄ物体２００の隣接する平面の少なくとも１つのペアは、交差し、（交線に沿って）１８０°よりも大きい外角を形成する。
【００１９】
図３は、２つの隣接する平面ＡおよびＢが交差し、交差する平面の間に凹（外）角θが形成された、３Ｄ物体の一部を示している。点線は、（立体物内部の）平面ＡおよびＢの想像上の部分を示している。隣接する平面ＡおよびＢの間の、物体の外側の角度θが、凸であるか、それとも凹であるかを決定するために、法線ベクトル（ｎｏｒｍａｌ  ｖｅｃｔｏｒ）を考えることができる。例えば、平面Ａの法線ベクトルはｎ１であり、平面Ｂの法線ベクトルはｎ２である。平面ＡおよびＢの間の角度は、平面ＡおよびＢの法線ベクトルｎ１およびｎ２の間の角度と同じである。したがって、平面ＡおよびＢの間の角度θは、以下のように決定することができる。
【００２０】
【数１】
0005726330.tif 000002
このようにして、物体の外角は、（例えば漸近的上限（ａｓｙｍｐｔｏｔｉｃ  ｕｐｐｅｒ  ｂｏｕｎｄ））Ｏ（ｌ）の時間内に（凹または凸として）計算することができ、ここで、ｌは、例えば、物体の隣接する平面の間の交線の数である。
【００２１】
いくつかの例では、凹角および凸角は、式（１）を使用して、面法線（ｓｕｒｆａｃｅ  ｎｏｒｍａｌ）に関して定義することができる。凹角または凸角は、例えば、３Ｄ物体の外面に対するものとすることができる。
【００２２】
図２を再び参照すると、３Ｄ物体２００の保護区域２０２は、頂点を凸または凹に分類することによって決定することができる。頂点を分類するため、３Ｄ物体２００の隣接する平面の交差によって生成された交線に、ｌ１，ｌ２，．．．，ｌｌと名前を付ける。交線は、ｖ２およびｖ３が３Ｄ物体２００の頂点である場合に、頂点ｖ２およびｖ３を接続する直線のような、隣接する頂点を接続する直線とすることができる。
【００２３】
（物体の２つの隣接する平面が交差する）各交線について、３Ｄ物体２００の外側の角度は、上記の式（１）を使用して決定することができる。角度が１８０°よりも大きい場合、頂点（ひいては交線）は、凸と見なすことができ、２Ｄ断面図では、保護区域を決定するために、半径ｒの円筒面である円弧を、３Ｄ物体２００の外側に交線に沿って識別することができる。図２では、これは、例えば、頂点ｖ８において示されている。３Ｄ図では、保護区域を決定するために、半径ｒの円筒面を、３Ｄ物体２００の外側に交線に沿って描くことができる。
【００２４】
そうではなく、（式（１）を使用して決定された）角度が１８０°よりも小さい場合、頂点（ひいては交線）は、凹と見なすことができ、外角は、交線に沿って２等分される。図２では、２等分線（例えばｂｓ１およびｂｓ２）が、頂点ｖ４およびｖ５において示されている。２Ｄ断面図では、保護区域を決定するために、その後、３Ｄ物体２００に外側の距離ｒのところに、直線が、直線（ｌｉ，ｌｉ＋１）、１≦ｉ＜ｌに平行して描かれる。３Ｄ図では、その後、３Ｄ物体２００に外側の距離ｒのところに、平面が、平面（ｌｉ，ｌｉ＋ｌ）、１≦ｉ＜ｌに平行して描かれる。例えば、交線ｌ３４（例えば、頂点ｖ３およびｖ４を接続する直線）と交線ｌ４５（例えば、頂点ｖ４およびｖ５を接続する直線）の場合、２等分線ｂｓ１が、頂点ｖ４のところに描かれている。その後、平面が、頂点ｖ３およびｖ４を接続する平面に平行して描かれ、平面ｐｑをもたらす。平面ｐｑは、例えば、保護区域２０２の一部と見なすことができる。
【００２５】
図４は、３Ｄ物体２００の断面の一部と、保護区域２０２の一部とを示している。頂点には、例えば、２Ｄ断面のｘおよびｙ座標を表す（ｘ１，ｙ１）、（ｘ２，ｙ２）、（ｘ３，ｙ３）、（ｘ４，ｙ４）という新たな名前が付けられている。頂点（ｘ３，ｙ３）は、凹頂点であり、したがって、頂点（ｘ３，ｙ３）に形成される角度を２等分する２等分線（ｂｓ）を描くことができる。２等分線（ｂｓ）は、点Ｐ１からＴまでの距離が、点Ｐ２からＴまでの距離に等しく（または実質的に等しく）なるように描くことができ、この距離は、保護区域距離ｒに等しい。
【００２６】
上で説明したような、頂点が凸か、それとも凹かを決定し、その後、円筒面または平面を描く、これらのステップを使用すると、例えば、隣接する各円筒面および平面を互いに接続することによって、保護区域２０２を決定し、形成することができる。２Ｄ物体の場合、保護区域を決定するために、円弧および直線を互いに結合することができ、２Ｄ物体は、３Ｄ物体の断面と見なすことができる。したがって、３Ｄ物体の場合、例えば、線分は、平面（例えば面）で置き換えることができ、２Ｄ物体の場合に多角形頂点のところに描かれた（半径ｒの）円弧は、半径ｒの円筒面または球面で置き換えることができる。
【００２７】
図２に示されるような保護区域２０２を計算する例が、以下で説明される。図２のエッジｖ２ｖ３について考える。ここで、頂点ｖ２およびｖ３は、ともに凸である。ｖ２ｖ３に平行で、長さがｖ２ｖ３と同じ平面が、頂点ｖ２を中心とする半径ｒの円筒面または球面とともに、３Ｄ物体２００の多角形エッジから距離ｒだけ離れたところに描かれる（図２では、平面および面の２Ｄ断面を表す直線および円弧が示されている）。ｖ２ｖ３に平行な平面は、ｖ２を中心とする（半径ｒの）円筒面の接平面である。
【００２８】
別の例として、エッジｖ３ｖ４について考える。ここで、頂点ｖ３は、凸頂点と見なすことができ、頂点ｖ４は、凹頂点と見なすことができる。ｖ３ｖ４に平行な保護区域２０２の平面の長さは、ｖ４が凹頂点であるので、平面ｖ３ｖ４の長さよりも短い。ここで、保護区域２０２の平面ｖ３ｖ４も、図２の点ｐにおいて、ｖ３を中心とする円筒面に（接平面として）接触し、（凹頂点であるｖ４に近い）他の端部では、保護区域２０２の平面は、以下で述べるように、点ｑまで引き延ばされる。点ｑは、平面ｖ３ｖ４およびｖ４ｖ５の間の角度（すなわち頂点ｖ４における角度）において描かれた、２等分面ｂｓ１との交点である。
【００２９】
図２のエッジｖ４ｖ５について考えると、頂点ｖ４およびｖ５は、ともに凹頂点であると決定される。保護区域２０２のこの部分については、円筒面は必要とされない。保護区域２０２の平面ｖ４ｖ５は、点ｑから点ｓまでの平面を決定することによって獲得することができ、ここで、ｓは、頂点ｖ５を２等分する平面（例えば２等分面ｂｓ２）における点である。保護区域２０２の平面ｖ４ｖ５の長さは、３Ｄ物体２００の平面ｖ４ｖ５の長さよりも短い。
【００３０】
図５は、３Ｄ物体５００の断面の例示的な一部と、保護区域５０２の一部とを示している。この例では、３Ｄ物体５００の平面ｖ４ｖ５の長さ、ならびに頂点ｖ４およびｖ５における外角は、２等分面ｂｓ１およびｂｓ２の交点ｆとの間の距離が、平面ｖ３ｖ４およびｖ５ｖ６に平行な保護区域５０２の２つの平面の交点ｇとの間の距離よりも短くなるような大きさである。この場合、平面ｖ４ｖ５に平行な平面として決定される、保護区域５０２の平面は存在しない。一般に、ｖ４ｖ５のような単一のエッジの代わりに、多角形には、例えば、保護区域の部分が特に計算されない、いくつかのエッジまたはいくつかのノッチが存在することがある。
【００３１】
図６は、（実線で示された）３Ｄ物体６００の例示的な一部と、（点線で示された）保護区域６０２の一部とを示している。図６における図は、３次元で表されている。３Ｄ物体６００は、３つの連続した平面Ａ、Ｂ、およびＣを含む。例えば点（ｍ−ｎ−ｏ−ｐ）は、平面Ａを決定し、点（ｏ−ｐ−ｑ−ｒ）は、平面Ｂを決定し、点（ｑ−ｒ−ｓ−ｔ）は、平面Ｃを決定する。保護区域の平面は、平面Ａ’、Ｂ’、およびＣ’を含む。点（ｍ’−ｎ’−ｏ’−ｐ’）は、平面Ａ’を決定し、点（ｏ’−ｐ’−ｑ”−ｒ”）は、平面Ｂ’を決定し、点（ｑ’−ｒ’−ｓ’−ｔ’）は、平面Ｃ’を決定する。
【００３２】
保護区域を計算するため、平面ＡおよびＢは、交線ｏ−ｐに沿って凹角を形成するので、平面ＡおよびＢの間の外角を、平面で２等分することができる。２等分面が、点（ｏ−ｐ−ｕ−ｖ）によって示されている。その後、開始面（図示されず）から２等分面まで、平面Ａ’を（点（ｍ’−ｎ’−ｏ’−ｐ’）を用いて）決定することができる。
【００３３】
平面ＢおよびＣは、交線ｑ−ｒに沿って凸角を形成し、したがって、保護区域を計算するために、平面ＢおよびＣが合わさった交線であって、交線ｑ−ｒに沿って凸外角を形成する交線ｑ−ｒを中心として、（例えば、所定の半径値の）円筒面ｑ’−ｒ’−ｒ”−ｑ”を計算することができる。立体物のＡ−Ｂ−Ｃの各点から、それらの保護区域平面Ａ’−Ｂ’−Ｃ’の各点までの最小距離は、半径値として与えることができることに留意されたい。半径値は、立体物の外側の保護区域を計算している間、維持することができる。あるいは、半径値は、例えば、保護区域の各部分ごとに調整することができる。半径値は、用途に基づいて変化することができ、例示的な値は、例えば、ナノメートルの範囲にあることができる。
【００３４】
凹外角を有する物体の部分について考える場合、物体にノッチが存在することがあり、保護区域を計算するときにノッチを考慮することができる。ノッチ２０４は、図２に示されるように、多角形の外側に形成され、例えば、頂点ｖ３およびｖ７を接続する点線の下側の部分である。ノッチは、例えば、物体の偽包絡エッジ（ｆａｌｓｅ  ｈｕｌｌ  ｅｄｇｅ）、包絡エッジ（ｈｕｌｌ  ｅｄｇｅ）、凸包（ｃｏｎｖｅｘ  ｈｕｌｌ）、および凸集合（ｃｏｎｖｅｘ  ｓｅｔ）を使用して、定義することができる。
【００３５】
物体は、例えば、物体内のどの点ペアについても、任意の点ペアをつなぐ直線分上のすべての点がやはり物体内に存在し、したがって、すべての点が凸集合を構成する場合に、凸と見なすことができる。凸包は、凸集合の点によって形成された境界であり、多角形の境界を形成する線分の一連の頂点によって表される。したがって、凸包は、平面上の与えられた任意の点の組について、すべての点が境界上または多角形内に存在するような、最小面積の（凹外角を有さない）凸多角形である。偽包絡エッジは、凸包を獲得する場合に導入される包絡エッジである。例えば、図１を参照すると、頂点ｖ１およびｖ１０、ｖ１２およびｖ１６、ｖ２０およびｖ２７の間に、点線によって描かれた偽包絡エッジが存在している。同様に、図２を参照すると、頂点ｖ２およびｖ８の間に、点線によって偽包絡エッジが描かれている。
【００３６】
しばしば、ノッチは、偽包絡エッジの２つの頂点において開始および終了する一連の物体Ｐのエッジで形成される、物体Ｐの外側の多角形領域と見なすことができる。Ｐが多角形であり、ＣＨ（Ｐ）が多角形Ｐの凸包を表す場合、ＣＨ（Ｐ）およびＰの面積の差は、多角形Ｐの外側の複数の分離されたノッチから成る。この例では、ノッチは、図２に示されるように、多角形の外側に形成され、頂点ｖ２およびｖ８を接続する点線の下側の部分である。または、例えば、ノッチは、図１に示されるように、多角形の外側に形成することができ、頂点ｖ１およびｖ１０、ｖ１２およびｖ１６、ｖ２０およびｖ２７を接続する点線の下側の部分である。
【００３７】
ここでは、ノッチは、隣接していない、多角形の２つの連続した凸頂点において開始および終了する、多角形の外側の多角形領域と見なされる。ノッチは、凸頂点（例えば、ｖ３）において開始し、多角形のエッジ（および頂点）を（特定の一方向に）辿りながら、１つまたは複数の凹頂点（例えば、ｖ４、ｖ５、ｖ６）を通過し、凸頂点（例えば、ｖ７）において終了する。したがって、ノッチは、物体の（いくつかの）交線について凹外角（複数可）が存在する場合に、形成される。したがって、ノッチ２０４は、図２に示されるように、多角形の外側に形成され、例えば、頂点ｖ３およびｖ７を接続する点線の下側の部分である。
【００３８】
図７ａ〜ｅは、各々がノッチを含む立体物の例示的な保護区域Ｇ１およびＧ２の２Ｄ図を示している。ノッチの形状が、保護区域Ｇ１およびＧ２において反映されている。保護区域計算を使用して、隣接性および安全な分離距離を維持しながら、２つ以上の立体物を最小の３Ｄ空間内に収容することができ、ノッチは、安全な分離距離を獲得することをさらに可能にすることができる。例えば、２つの保護区域Ｇ１およびＧ２の場合、図７ｂ〜ｅに示される例示的なレイアウトなど、物体のいくつかの可能な３Ｄ割り当てが存在する。例えば、図７ｄに示されるレイアウトなど、レイアウトの１つは、最小の空間量しか必要としないことができる。この例では、ノッチの存在が、そのような割り当てを可能にしている。したがって、１組の３Ｄ物体の保護区域を計算することができ、その場合、例えば、ノッチを使用して、最小の３Ｄ空間内に、物体を割り当てることができる。
【００３９】
図８は、物体の３Ｄ保護区域を計算するための方法８００の例示的な実施形態についてのフローチャートを示している。本明細書で開示されるこのおよび他のプロセスおよび方法について、フローチャートは、本実施形態の１つの可能な実施の機能および動作を示すことを理解されたい。この点に関して、各ブロックは、モジュール、セグメント、またはプログラムコードの部分を表すことができ、それらは、方法における特定の論理機能、アクション、またはステップを実施するための、プロセッサによって実行可能な１つまたは複数の命令を含むことができる。プログラムコードは、例えば、ディスクまたはハードドライブを含む記憶デバイスなど、任意のタイプのコンピュータ可読媒体に記憶することができる。コンピュータ可読媒体は、例えば、レジスタメモリ、プロセッサキャッシュ、およびランダムアクセスメモリ（ＲＡＭ）のような、データを短期間記憶するコンピュータ可読媒体など、非一時的コンピュータ可読媒体を含むことができる。コンピュータ可読媒体は、例えば、リードオンリメモリ（ＲＯＭ）、光または磁気ディスク、コンパクトディスクリードオンリメモリ（ＣＤ−ＲＯＭ）のような、２次的または永続的な長期記憶など、非一時的媒体も含むことができる。コンピュータ可読媒体は、他の任意の揮発性または不揮発性記憶システムとすることもできる。コンピュータ可読媒体は、例えば、コンピュータ可読記憶媒体、または有形な記憶デバイスと見なすことができる。
【００４０】
加えて、図８の各ブロックは、プロセスにおける特定の論理機能を実行するように配線することができる回路を表すことができる。当業者であれば理解するように、含まれる機能に応じて、実質的に同時または逆順を含む、示された順序または説明された順序とは異なる順序で機能が実行され得る代替的な実施も、本開示の例示的な実施形態の範囲内に含まれる。
【００４１】
方法８００は、１つまたは複数のブロック８０２、８０４、８０６、８０８、８１０、８１２、８１４、８１６、８１８、８２０、８２２、８２４、８２６、８２８、８３０、８３２、および／または８３４によって示されるような、１つまたは複数の動作、機能、またはアクションを含むことができる。ブロックは、順次的な順序で示されているが、これらのブロックは、並列で、および／または本明細書で説明する順序とは異なる順序で実行することもできる。また、様々なブロックは、所望の実施に基づいて、組み合わせてより少数のブロックにすること、分割してさらなるブロックを生み出すこと、および／または除去することができる。
【００４２】
方法８００の処理は、ブロック８０２「物体に関連するデータを受け取り、境界線に名前を付ける」において開始することができる。例えば、最初に、物体（Ｓ）に関連するデータをメモリ内に、またはプロセッサによって受け取ることができ、すべての境界線（または隣接する平面の交線）にｌ１，ｌ２，．．．，ｌｌという名前を付けることができる。データは、例えば、１つまたは複数の頂点、直線、形状、長さ、半径などの集まりなどの物体を表す値から成ることができる。図６を参照すると、隣接する平面の例示的な境界線または交線が、直線（ｐｏ）として示されている。
【００４３】
ブロック８０２の後には、ブロック８０４「隣接する平面の交差の角度を識別する」が続くことができる。例えば、（例えば、データがｌ本の直線を含む場合）直線ｉ＝１からｌ−１について、隣接する平面の交差の角度は、凹または凸として識別することができる。例えば、上で説明した式（１）をプロセッサによって使用して、角度を凸または凹として識別および／または分類することができる。
【００４４】
角度が凸と識別された場合、ブロック８０４の後には、ブロック８０６「物体の外面の周りに、交差する面の交線を中心とする半径ｒの円筒面を決定する」が続くことができる。例えば、凸角の場合、物体の外面の周りに円筒面を決定することができ、半径ｒの円筒面は、交差する面の交線を中心とする。図６の図を再び参照すると、交線ｑ−ｒを中心とする例示的な円筒面ｑ’−ｒ’−ｒ”−ｑ”を計算および決定することができる。
【００４５】
ブロック８０６の後には、ブロック８０８「隣接する平面の交差の角度を識別する」が続くことができる。例えば、方法８００は、引き続き、次の隣接する平面（ｌｉ，ｌｉ＋１）の交差の外角を識別することができる。外角は、やはり、凹または凸として識別することができる。
【００４６】
次の外角が凸と識別された場合、ブロック８０８の後には、ブロック８１０「面が交差する線を中心とする半径ｒの面を決定する」が続くことができる。例えば、角度が凸である場合、物体の外面の周りに、隣接する面によって形成されるその角度の線を中心とする半径ｒの円筒面を決定することができる。
【００４７】
ブロック８１０の後には、ブロック８１２「２つの円筒面の間に、物体の外面から距離ｒのところにある平行な平面を決定する」が続くことができる。したがって、物体の外面から距離ｒだけ離れたところにある、（例えば、ブロック８０６および８１０において描かれた）直線ｌｉおよびｌｉ＋１のところに描かれた２つの円筒面に共通する接平面である、（ｌｉ，ｌｉ＋１）に平行な平面を描くことができる。例えば、２つの円筒面を接続する平面が描かれる。
【００４８】
ブロック８０８において識別された角度が凹である場合、ブロック８０８の後には、ブロック８１４「平面を用いて外角の２等分を決定する」が続くことができる。凹角の場合、外角は、平面を用いて２等分することができる。図６の図を再び参照すると、例えば、点（ｏ−ｐ−ｕ−ｖ）として２等分面が示されている。ちなみに、２等分面は、保護区域の部分として形成されること、または示されることはなく、むしろ、保護区域の一部を計算するために使用することができる。
【００４９】
ブロック８１４の後には、ブロック８１６「円筒面と２等分面の間に、物体の外面から距離ｒのところにある平面を決定する」が続くことができる。例えば、円筒面と２等分面の間に、物体から距離ｒだけ離れたところにある、ｌｉのところに描かれた円筒面の接平面であり、２等分面と交差する、（ｌｉ，ｌｉ＋１）に平行な平面が描かれる。したがって、この例では、円筒面の接平面として２等分面まで延びる保護区域の一部のためのエンドポイントとして、２等分面を使用することができる。
【００５０】
ブロック８０４に戻り、交差する隣接平面のペアが凹角を形成する場合、ブロック８０４の後には、ブロック８１８「平面を用いて外角の２等分を決定する」が続くことができる。上で説明したように、いくつかの例では、２等分面は、保護区域の部分として決定されることはなく、むしろ、保護区域の一部を計算するために使用することができる。
【００５１】
ブロック８１８の後には、ブロック８２０「隣接する平面の交差の角度を識別する」が続くことができる。次の隣接する平面（ｌｉ，ｌｉ＋１）の交差の外角について、外角が凹または凸として識別される。
【００５２】
次の角度が凸と識別された場合、ブロック８２０の後には、ブロック８２２「面が交差する線を中心とする半径ｒの面を決定する」が続くことができる。角度が凸である場合、例えば、物体の表面の外側に、交線を中心とする半径ｒの円筒面が決定される。
【００５３】
ブロック８２２の後には、ブロック８２４「２等分面と円筒面の間に、物体の外面から距離ｒのところにある平面を決定する」が続くことができる。例えば、その場合、（物体の外側の）物体の平面から距離ｒだけ離れたところにある、２等分面と交差し、決定された円筒面の接平面である、（ｌｉ，ｌｉ＋１）に平行な平面が決定される。平面は、物体の保護区域の一部である。
【００５４】
次の角度を凹と識別することができる場合、ブロック８２０の後には、ブロック８２６「平面を用いて外角の２等分を決定する」が続くことができる。例えば、ブロック８２０によって角度が凹と決定された場合、外角は、平面（例えば、第２の２等分面）を用いて２等分することができ、この平面は、もっぱら保護区域計算の目的で使用することができる。
【００５５】
ブロック８２６の後には、ブロック８２８「２つの２等分面の間に、物体の外面から距離ｒのところにある平面を決定する」が続くことができる。例えば、（物体の外側の）物体の平面から距離ｒだけ離れたところにある、第１および第２の２等分面と交差する、（ｌｉ，ｌｉ＋１）に平行な平面が決定される。平面は、物体の保護区域の一部である。
【００５６】
ブロック８０４〜８１２は、隣接する交線における角度がともに凸角である場合に、保護区域の一部を計算するための例を示し、説明しており、ブロック８０４〜８０８およびブロック８１４〜８１６は、隣接する交線における角度が凸角および凹角である場合に、保護区域の一部を計算するための例を示し、説明しており、ブロック８０４およびブロック８１８〜８２４は、隣接する交線における角度が凹角および凸角である場合に、保護区域の一部を計算するための例を示し、説明しており、ブロック８０４、ブロック８１８〜８２０、およびブロック８２６〜８２８は、隣接する交線における角度がともに凹角である場合に、保護区域の一部を計算するための例を示し、説明している。ブロック８０４〜８２８は、ブロック８３０に示されるように、直線ｉ＝１からｌ−１の各々について繰り返すことができる。
【００５７】
ブロック８３０の後には、ブロック８３２「平面の間の交線の端点（ｅｎｄ  ｖｅｒｔｅｘ）が物体の尖点であると決定される、隣接する平面の間の凸角の場合、頂点の各々において球面を決定する」が続くことができる。例えば、平面の間の交線の２つの端点が（立体物の２つの尖点である）ｕおよびｖである、物体の２つの隣接する平面の間の凸外角の場合、頂点に関連する保護区域平面が、球面（複数可）に共通する接平面になるか、または球面と交差するように、頂点ｕおよびｖの各々において、半径ｒの球面がそれぞれ描かれる。
【００５８】
一例では、（１組の平面によって覆われる）立体物の入力は、（３Ｄ座標系に関する）（ｘ、ｙ、ｚ）座標およびそれらの隣接する座標として、その尖点によって与えられる。物体の隣接する２つの尖点が、交線を形成し、少なくとも３つの交線が（尖点の隣接性に基づいて）、３Ｄ物体の平面を形成する。説明するように、ｕおよびｖをつなぐ交線が凸外角を形成する場合、（物体の外側に）交線を中心とする半径ｒの円筒面が決定され、それ以外の場合、ｕおよびｖをつなぐ交線に沿った外角は２等分され、立体物のｕおよびｖをつなぐ交線に隣接する関連する平面に対して決定された保護区域平面の各々は、（考察中の交線に隣接する物体の平面に対して計算された保護区域平面の各々が、平面から距離ｒだけ離れたところにあるように）２等分面のところで合わさる。頂点ｕおよびｖが尖点である場合、頂点が完全に凸である（例えば、尖点で終了する交線の各々が凸外角を形成する）ならば、ｕおよびｖをつなぐ交線に対して決定される保護区域平面の各々は、尖頭において描かれる半径ｒの球面に対する接平面になる。他方、そのような尖点が部分的に凸である（例えば、尖点で終了する交線のいくつが凸外角を形成し、残りの交線は凹外角を形成する）ならば、ｕおよびｖをつなぐ凹交線に対する隣接する保護区域平面は、例えば、尖頭において決定される半径ｒの球面を切る。
【００５９】
図９ａ〜ｄは、球保護区域が決定される尖点を有する例示的な平面を示している。図９ａ〜ｃは、交線ｔｐ、ｔｑ、ｔｒ、ｐｑ、ｑｒを有する３Ｄ物体の隣接する平面（ｔｐｑおよびｔｑｒ）の一例を示しており、ｔは、物体の尖点であり、頂点ｔは、凸である。図９ａでは、点線は、物体の一部に対する保護区域を示し、ｔ１ｐ１（ｔ２ｒ１）は、物体の交線ｔｐ（ｔｒ）に対する保護区域の表面上の直線である。交線ｔｐ（ｔｒ）が凸外角を形成する場合、ｔ１ｐ１（ｔ２ｒ１）は、保護区域の円筒面上にあり、それ以外の場合、ｔ１ｐ１（ｔ２ｒ１）は、保護区域上、およびｔｐ（ｔｒ）に隣接する平面によって形成される凹外角の２等分面上にあることに留意されたい。加えて、ｔ１ｔ２は、物体の凸尖点ｔに起因する保護区域球面である。図９ｂでは、交線ｔｑが凸外角を形成することを仮定する一例において、ｔｑを中心とする円筒面ｔ３ｑ１ｑ２ｔ４が形成され、保護区域平面Ｐ１（すなわちｔ３ｑ１ｒ１ｔ１）およびＰ２（すなわちｔ４ｑ２ｐ１ｔ２）は、円筒面に対する接平面である。さらに、Ｐ１およびＰ２は、（凸である）尖点ｔに起因して決定される球保護区域面ｔ１ｔ３ｔ４ｔ２に対する接平面でもある。図９ｃでは、交線ｔｑが凹外角を形成することを仮定する一例において、ｔｑに沿った角度が２等分され、その２等分面ｔ’ｑ１上に、保護区域平面Ｐ３およびＰ４が出会う直線が存在する。加えて、Ｐ３（すなわちｔ’ｒ１ｑ１）およびＰ４（すなわちｔ’ｑ１ｐ１）は、ｔ１ｔ’ｔ２に沿って（ｔに起因する）球保護区域面と交差する。
【００６０】
図９ｄは、３Ｄ物体の凸尖点に対する球保護区域の例示的な断面図または上面図を示している。この例では、少なくとも１１個の平面および１１個の交線が、物体の頂点において出会い、それらのうち、隣接する平面の２つのペアが、凹外角を形成する。例えば、図９ｄには、ａｂ、ｄｅ、ｇｈを含む、３つの円弧が存在する。これは上面図であるので、各円弧は、円筒面を表し、保護区域の円筒面は、物体の凸外角を形成する２つの隣接する平面に対して獲得される。各断面ｂｃｄまたはｅｆｇは、物体の２つの隣接する平面に対して形成される凹外角に起因する保護区域部分として獲得される。加えて、物体の少なくとも１つのさらなる平面が存在し、球面に対する接平面である保護区域平面ａｈが、それに対して決定される。
【００６１】
図８を再び参照すると、ブロック８３２の後には、ブロック８３４「交差し、物体の平面または頂点から距離がｒ未満しか離れていない、保護区域の部分を除外する」が続くことができる。例えば、保護区域の２つの平面、平面と円筒面／球面、または２つの円筒面／球面が交差する場合、（物体の外側の）物体の平面または頂点から距離がｒ未満しか離れていない、平面（複数可）および／または円筒面／球面（複数可）の部分が除外される。
【００６２】
保護区域を計算する方法８００の時間計算量について以下で説明する。ｎ個の頂点、ｌ個の交線、およびｐ個の平面（ｐ個の面）の凸物体の保護区域は、ｐ個の平面（または面）、ｌ個の円筒弧、およびｎ個の球面を有する凸（３Ｄ）領域であり、ｎ＝Ｏ（ｌ）、およびｐ＝Ｏ（ｌ）である。保護区域の平面は、物体の外側から距離ｒだけ離れて、物体の平面と平行であり、保護区域の２つの隣接する平面は、物体の関連する交線を中心とする半径ｒの円筒面によって、つなぐことができる。半径ｒの球面は、各々が、物体の頂点（または尖点）において計算される保護区域の一部として導入され、保護区域の関連する平面は、円筒面および球面に対する接平面であり、保護区域の円筒部分も、物体の頂点（または尖点）の近くでは、保護区域の球面になって終了する。結果として、凸立体物の３次元保護区域を計算するのに必要な時間は、ｎおよびｐはｌのオーダ（例えば、ｎ＝Ｏ（ｌ）、ｐ＝Ｏ（ｌ））であるので、Ｏ（ｎ＋ｌ＋ｐ）＝Ｏ（ｌ）として近似することができる。
【００６３】
物体の交線である、平面の連続する境界線ｌｉおよびｌｉ＋１の場合、一方の直線（例えばｌｉ）は、先の反復において、隣接する平面の保護区域を計算するために、すでに考慮されているが、もう一方（例えばｌｉ＋１）は、検討中の平面の保護区域を計算するために、初めて考慮される。（その保護区域が計算されている）物体の平面、および凸または凹である角度の場合、すべての計算に一定の時間がかかる。したがって、ｎ個の頂点、ｌ個の交線、およびｐ個の平面からなる物体の場合、物体の保護区域を計算するのに必要とされる最悪ケースの総時間は、Ｏ（ｎ＋ｌ＋ｐ）＝Ｏ（ｌ）として近似することができる。
【００６４】
例えば、保護区域のセグメントが計算される物体の平面、交線、および頂点から距離がｒ未満しか離れていない、計算された保護区域の部分を除外するための、方法８００の残りの部分の場合、これは、近似的にＯ（ｌ）の時間で実現することができる。例えば、交線および平面に対する保護区域の計算中、保護区域の内側かつ物体の外側の点の座標（例えば、ｘ、ｙ、ｚ）は、一定の時間で識別することができる。視覚化のため、例えば、特定の強度値を有する色を使用して、座標の位置を示すことができる。あるいは、例えば、他の交線のための、保護区域の新たに計算された領域に座標が含まれる場合、座標に対してフラグを設定し、更新することができる。
【００６５】
なお、ｎ個の頂点、ｌ個の交線、およびｐ個の平面からなる物体の保護区域を計算する下限は、物体の構成要素の各々は少なくとも一度考慮されるので、近似的にΩ（ｎ＋ｌ＋ｐ）またはΩ（ｌ）とすることができる。例えば、ｎ個の頂点、ｌ個の交線、およびｐ個の平面からなる３Ｄ立体物の保護区域を計算する下限は、Ω（ｎ＋ｌ＋ｐ）またはΩ（ｌ）であり、保護区域を計算する上限は、Ｏ（ｎ＋ｌ＋ｐ）またはＯ（ｌ）であるので、例の中で、ｎ個の頂点、ｌ個の交線、およびｐ個の平面からなる物体の保護区域は、時間最適であり得る漸近的にタイトな限界（ａｓｙｍｐｔｏｔｉｃ  ｔｉｇｈｔ  ｂｏｕｎｄ）Θ（ｎ＋ｌ＋ｐ）またはΘ（ｌ）の時間で計算することができる。
【００６６】
例示的な実施形態では、３Ｄ物体の保護区域は、物体の各部分が順次的に検討される、順次的なアルゴリズムを使用して、計算することができる。例えば、（３Ｄ物体の何らかの構成要素の）保護区域は、１つのプロセッサによって実行される順次的なアルゴリズムを使用して、一定の時間で計算することができる。プロセッサは、例えば、隣接する平面とともに、１つの交線の保護区域を計算することができる。順次的なアルゴリズムの全体的な時間計算量は、約Ｏ（ｌ）とすることができ、ここで、ｌは３Ｄ物体の交線の数である。
【００６７】
他の例では、３Ｄ物体の保護区域は、並列で計算することができ、物体の複数の部分が、同時に検討される。例えば、図８の方法を使用する一例において実行できるような、単一のプロセッサを使用する順次的な方法で、保護区域の計算を実行する代わりに、ｎ個の頂点、ｌ個の交線、およびｐ個の平面からなる３Ｄ物体の保護区域は、分散コンピューティング環境において、複数のプロセッサ（例えばＯ（ｌ））を使用して計算することができる。
【００６８】
図１０は、並列処理を使用して３Ｄ物体の保護区域を計算するための例示的なシステム１０００を示すブロック図である。例示的なシステム１０００は、メモリ１００２と、プロセッサ１００４ａ〜１００４ｌと、プロセッサ１００６とを含む。メモリ１００２は、例えば、任意の形態のコンピュータ可読媒体またはコンピュータ可読記憶媒体とすることができる。プロセッサ１００４ａ〜１００４ｌおよびプロセッサ１００６は、例えばマイクロプロセッサ（μＰ）、マイクロコントローラ（μＣ）、デジタル信号プロセッサ（ＤＳＰ）、またはそれらの任意の組み合わせなど、任意のタイプのプロセッサとすることができる。
【００６９】
（３Ｄ図において物体の平面を形成する連続する交線である）ｌ個の交線ｌ１，ｌ２，．．．，ｌｌ、およびｍ個の平面ｐ１，ｐ２，．．．，ｐｍなど、物体に関連する情報またはデータは、メモリ１００２のＯ（ｌ）個の共用メモリロケーションに入力される。３Ｄ物体の交線の数に等しい数のプロセッサを使用することができる。この例では、システム１０００は、ｌ個のプロセッサ（例えば、１００４ａ〜１００４ｌ）を含むことができる。あるいは、示されるように、システム１０００は、より多数（または少数）のプロセッサを含むことができ、３Ｄ物体の直線の数に等しい数のプロセッサを計算に使用することができる。システム１０００は、例えば、分散コンピューティング環境の一部とすることができ、または分散コンピューティング環境を含むことができる。
【００７０】
第１のプロセッサ１００４ａは、交線ｌｉ（例えば、平面の間の直線）と、（交線ｌｉの生成に係わる）隣接する平面ｐｉ−１およびｐｉとに関連するデータを同時に読み取るように構成することができ、ｌｉにおいて生成される外角を計算または決定するように構成することができる。プロセッサ１００４ａは、４つの可能な保護区域計算の１つを検討し、交線ｌｉおよび平面ｐｉに対する保護区域Ｇの部分を計算するように適合することができる。図１１ａ〜ｄは、（実線で示される）３Ｄ物体の部分および本明細書で説明される少なくともいくつかの技法に従って決定される（点線で示される）保護区域の部分の２Ｄ断面の４つの例である。
【００７１】
図１１ａでは、平面ｐｉは、凸外角を有する（２つの）端部交線ｌｉおよびｌｉ＋１を有する。プロセッサ１００４ａは、例えば、ｌｉおよびｌｉ＋１を中心とする半径ｒの（物体の外側の）円筒面を計算し、その後、保護区域の部分についての長さが（ｌｉ，ｌｉ＋１）と同じであり、ｌｉおよびｌｉ＋１において計算された両方の円筒面に共通する接平面である、物体の平面から（物体の外側に）距離ｒだけ離れた、ｐｉに平行な平面を計算するように構成することができる。
【００７２】
図１１ｂでは、平面ｐｉは、凸である端部交線ｌｉと、凹外角を有する端部交線ｌｉ＋１とを有する。プロセッサ１００４ａは、ｌｉを中心とする半径ｒの（物体の外側の）円筒面を計算し、ｌｉ＋１における角度を２等分し、２等分ｂｓｉ＋１を表すように構成することができる。その後、プロセッサ１００４ａは、例えば、ｌｉにおいて描かれた円筒面に対する接平面であり、（例えば、直線ｃｉ＋１のような）直線においてｂｓｉ＋１と交差する、立体物の平面から（立体物の外側に）距離ｒだけ離れた、ｐｉに平行な平面を計算するように構成することができる。
【００７３】
図１１ｃでは、平面ｐｉは、角度が凹である端部交線ｌｉと、角度が凸である直線ｌｉ＋１とを有する。プロセッサ１００４ａは、ｌｉにおける角度を２等分し、２等分ｂｓｉを表し、ｌｉ＋１を中心とする半径ｒの（立体物の外側の）円筒面を計算するように構成することができる。その後、プロセッサ１００４ａは、例えば、直線（例えば、直線ｃｉ）においてｂｓｉと交差または接触し、ｌｉ＋１において計算された円筒面に対する接平面である、物体の平面から（物体の外側に）距離ｒだけ離れた、ｐｉに平行な平面を計算するように構成することができる。
【００７４】
図１１ｄでは、平面ｐｉは、外角が凹である（２つの）端部交線ｌｉおよびｌｉ＋１を有する。プロセッサ１００４ａは、それぞれ、ｌｉおよびｌｉ＋１における角度を２等分し、２等分ｂｓｉおよびｂｓｉ＋１を表すように構成することができる。その後、プロセッサ１００４ａは、例えば、直線（例えば、直線ｃｉ）においてｂｓｉと、直線（例えば、直線ｃｉ＋１）においてｂｓｉ＋１と交差または接触する、物体の平面から（物体の外側に）距離ｒだけ離れた、ｐｉに平行な平面を、ｂｓｉおよびｂｓｉ＋１の交線からｐｉへの距離がｒより大きい場合に、計算するように構成することができる。
【００７５】
図１０に戻ると、プロセッサ１００４ａは、図１１ａ〜ｄに示されるような４つの可能性の１つを検討し、交線ｌｉおよび平面ｐｉに対する保護区域Ｇの部分を計算するように構成することができる。プロセッサ１００４ａ〜ｌの各々は、例えば、それぞれの隣接する交線および隣接する平面に関する情報またはデータを受け取り（プロセッサ１００４ａ〜ｌの各々は、交線および隣接する平面の異なるペアを受け取る）、図１１ａ〜ｄに示される例示的な構成に基づいて、３Ｄ物体の保護区域Ｇの部分を計算するように適合することができる。
【００７６】
プロセッサ１００４ａ〜ｌの各々は、物体の３Ｄ保護区域の計算された部分に関連するデータを、（例えば、出力プロセッサとすることができる）プロセッサ１００６に出力するように適合することができる。プロセッサ１００６は、例えば、計算された部分に関連するデータを解析し、保護区域の平面セグメント（複数可）および／または円筒面／球面（複数可）が立体物の外側で交差する場合、物体の平面、交線、または頂点から距離がｒ未満しか離れていない、計算された保護区域の平面セグメント（複数可）および／または円筒面／球面（複数可）の部分に関するデータを除外するように構成することができる。プロセッサ１００６は、例えば、物体の保護区域の全体を表すデータセットを生成するために、保護区域の計算された部分に関連するデータを組み合わせるように構成することもできる。
【００７７】
本明細書で説明される例示的なアルゴリズムの時間計算量は、制御ユニットが、それぞれのデータ上ですべてのプロセッサによって同時（または実質的に同時）に実行される命令を発行する、単一命令ストリーム多重データストリーム（ＳＩＭＤ：ｓｉｎｇｌｅ  ｉｎｓｔｒｕｃｔｉｏｎ  ｓｔｒｅａｍ  ｍｕｌｔｉｐｌｅ  ｄａｔａ  ｓｔｒｅａｍ）並列コンピューティング環境において、同時読み取り同時書き込み（ＣＲＣＷ：ｃｏｎｃｕｒｒｅｎｔ  ｒｅａｄ  ｃｏｎｃｕｒｒｅｎｔ  ｗｒｉｔｅ）並列ランダムアクセス機械（ＰＲＡＭ：ｐａｒａｌｌｅｌ  ｒａｎｄｏｍ  ａｃｃｅｓｓ  ｍａｃｈｉｎｅ）を使用することによって、考えることができる。
【００７８】
図１０を参照して上で説明したように、物体のｌ個の交線の座標は、ＰＲＡＭのＯ（ｌ）個の共用メモリロケーションに維持することができる。Ｏ（ｌ）個のプロセッサによって実行される同時読み取り（ＣＲ）命令を使用して、２つ以上のプロセッサは、同時に同じメモリロケーションから読み取ることができる。例えば、交線ｌｉ＋２の座標に関連するデータには、プロセッサｐｉからｐｉ＋３がアクセスすることができる。したがって、命令ＣＲが実行される場合、プロセッサＰｉが交線ｌｉ−１、ｌｉ、ｌｉ＋１、ｌｉ＋２の座標を読み取るなど、Ｏ（ｌ）個のプロセッサは、Ｏ（ｌ）個のメモリロケーションの内容を同時に読み取るように適合することができる。これは、Ｏ（ｌ）個のプロセッサによる排他読み取り（ＥＲ）命令を使用して実行することもでき、その場合、プロセッサは、例えば、１対１方式で読み取りを行う目的で、メモリロケーションにアクセスする。ＥＲ命令が実行される場合、Ｏ（ｌ）個のプロセッサの各々が１つのメモリロケーションから読み取り、関連するＯ（ｌ）個のメモリロケーションの各々が１つのプロセッサによって読み取られるなど、Ｏ（ｌ）個のプロセッサは、Ｏ（ｌ）個の異なるメモリロケーションの内容を同時に読み取る。一例では、ＣＲがＥＲを含むことに留意されたい。
【００７９】
その後、プロセッサＰｉは、平面（ｌｉ−１，ｌｉ）、（ｌｉ，ｌｉ＋１）、（ｌｉ＋１，ｌｉ＋２）（すなわち、それぞれｐｉ−１、ｐｉ、ｐｉ＋１）を計算し、交線ｌｉおよびｌｉ＋１における外角を計算するように構成することができる。プロセッサＰｉは、図１１ａ〜ｄにおいて説明したような、４つの可能な保護区域の１つを決定するように適合することができる。したがって、プロセッサは、角度（複数可）が凸である場合は、円筒面（複数可）を計算し、および／または角度（複数可）が凹である場合は、角度（複数可）を２等分するように構成することができる。加えて、プロセッサは、計算されている保護区域Ｇの一部として、物体の平面から（物体の外側に）距離ｒだけ離れた、ｐｉに平行な平面を計算するように構成することができる。
【００８０】
したがって、物体の保護区域は、一定の時間で計算することができ、それは、ノッチ（複数可）の存在に起因する、（重なり合う）平面および／または円筒面／球面といったいくつかの冗長な部分を含むことができる。Ｇの望まない部分を除去するために、Ｏ（ｌ）個のプロセッサによる組み合わせ和ＣＷ（ｃｏｍｂｉｎｅｄ  ｓｕｍ  ＣＷ）の形式の同時書き込み（ＣＷ）命令を実行することができ、例えば、２つ以上のプロセッサは、同じメモリロケーションに同時に書き込むことができ、結果として得られるデータの和が、そのメモリロケーションに残される。例えば、ＣＷ命令の場合、１組のプロセッサがあるメモリロケーションに同時に書き込むことができるすべての値は、組み合わされて単一の値になり、その後、その値が、そのロケーションに記憶される。ＣＷ命令は、結果を（メモリロケーションに）記憶する前に、（いくつかのプロセッサによって書き込まれた）値を組み合わせるために、どの関数を使用しているかに応じて、いくつかの形式を取ることができる。これらの形式のいくつかでは、例えば、それぞれ、ＳＵＭ（加算）もしくはＰＲＯＤＵＣＴ（乗算）などの算術関数を使用して、書き込まれる値を組み合わせることができ、またはＡＮＤ、ＯＲ、もしくはＥＸ−ＯＲなどの論理関数を使用して、１組のブール値を組み合わせることができ、またはＭＡＸもしくはＭＩＮなどの選択関数を使用して、書き込まれる値の最大値もしくは最小値を選択することができる。一例では、プロセッサＰｉは、３Ｄ物体の平面ｐｉとともに、交線ｌｉに対する保護区域を計算することを担当することができる。同様に、ｌ個のプロセッサはすべて、同時にタスクを実行する。したがって、組み合わせ和ＣＷの命令に続いて、３Ｄ物体の完全な保護区域は、メモリのロケーションにもたらされるデータとして計算される。
【００８１】
さらに、ＣＷ命令が実行される場合、Ｏ（ｌ）個のプロセッサは、同時（または実質的に同時）に１つのメモリロケーションに書き込むことができる。立体物の平面または交線から（立体物の外側に）距離がｒ未満しか離れていないＧの部分を除外するため、プロセッサＰｉは、Ｇの内側かつ物体の外側の（プロセッサが担当する）領域に対するフラグの値を１に設定することができる。その後、すべてのプロセッサによって同時に計算され、ＰＲＡＭの第（ｌ＋１）の共用メモリロケーションに書き込まれる、Ｇの内側かつ物体の外側の領域に対して、ＣＷ命令が、上で述べたように、Ｏ（ｌ）個のプロセッサによって実行される。保護区域のいくつかの領域（すなわち、Ｇの内側かつＳの外側）は、領域が重なり合う場合にインクリメントされるフラグを有することができる（例えば、フラグは２以上になることができる）。説明のため、強度Ｉを有する色Ｃを使用して、Ｇの領域を立体物から区別することができ、（ＰＲＡＭの第（ｌ＋１）の共用メモリロケーションに書き込まれる）計算された保護区域のｌ個の異なる部分を合計した後、例えば、重なり合う領域は、Ｉとは異なる強度を有する色Ｃを有することができる。
【００８２】
図１２ａ、図１２ｂは、（点線で示された）保護区域を有する（実線で示された）３Ｄ物体の例示的な断面を示している。３Ｄ物体の頂点ｖ２およびｖ５の間にノッチが形成されており、（それぞれｖ２およびｖ５を通過する）対応する交線ｌ２およびｌ５が、２ｒ未満の距離にあり、このノッチに対して、（点線で示された）保護区域が獲得されている。プロセッサＰｉは、３Ｄ物体の平面ｐｉとともに、交線ｌｉに対する保護区域を計算でき、保護区域の内側かつ立体物の外側においてフラグに１を設定できることが理解できよう。ここでは、ｖ２およびｖ５の間の距離は２ｒ未満であるので、部分ｖ１−ｖ２−ｖ３および部分ｖ６−ｖ５−ｖ４に対する保護区域は、（それらの２Ｄ図における）点ｐおよびｑにおいて交差する（または交わる）。したがって、すべてのプロセッサによって組み合わせ和ＣＷ命令を同時に実行した後、重なり合う領域（ｐｑ）内のフラグは、２にインクリメントされ、一方、重なり合う領域（ｐｑ）外のフラグは、１のままである。図１２ｂに示されるように、交差する点を除いて（すなわち、点ｐおよびｑは別として）、重なり合う領域（ｐｑ）内の保護区域を除外した後、３Ｄ物体のこの部分に対する（穴を含むことができる）所望の保護区域が計算され、例えば、物体の外側かつ保護区域の内側のフラグは、すべて１である。例えば、（フラグ１の代わりに）強度Ｉを有する色Ｃおよび（フラグ２の代わりに）Ｉ以外の強度を有する同じ色Ｃを使用できることが理解できよう。
【００８３】
１以外のフラグ値（またはＩ以外の強度を有する色Ｃ）を有する領域の境界を除外するため、すべてのプロセッサは、ＣＲ命令を実行するように適合することができる。例えば、Ｏ（ｌ）個のプロセッサはすべて、今では全体としていくつかの冗長部分を含むことができる保護区域である、ＰＲＡＭの第（ｌ＋１）の共用メモリロケーションの内容を同時に読み取るように構成することができる。プロセッサの各々は、フラグが１以上に設定された、Ｇの内側かつ物体の外側の指定された領域についての情報（すなわち座標）を読み取るように構成することができる。プロセッサＰｉは、プロセッサが担当する第ｉの部分以外の、Ｇに関連する部分のデータを除外する。プロセッサＰｉは、プロセッサＰｉによって計算されたＧの内側（かつ物体の外側）の領域が、１以外のフラグを有するいずれかの座標を含むかどうかを検証するように構成することができる。領域が見つからない場合、プロセッサＰｉは、何のアクションも取らない。それ以外の場合、Ｐｉは、座標が１以外のフラグを有する、（プロセッサＰｉによって計算された）Ｇに関連する部分のデータを除外するように構成することができる。例えば、これも、一定の時間で計算することができる。
【００８４】
ＣＷ命令は、すべてのプロセッサによって同時に計算された保護区域Ｇの変更された部分を、ＰＲＡＭの第（ｌ＋１）の共用メモリロケーションに書き込むために実行することができる。したがって、立体物Ｓに対して計算された保護区域Ｇは、共用メモリの第（ｌ＋１）のロケーションにおいて入手可能である。
【００８５】
一例では、本明細書で説明する方法の実行時間は、近似的にＯ（ｌ）である。Ｏ（ｌ）個のプロセッサが保護区域の計算に関与するので、方法は、コスト最適とすることができる。例えば、隣接する平面の間にｌ個の交線を有する立体物の保護区域は、一定の時間で計算することができる。
【００８６】
図１３〜図１６は、本明細書で開示される様々な技法に従って、並列処理を使用して、物体の保護区域を計算する一例を示している。図１３は、例示的な３Ｄ物体を示している。物体は、８個の尖点ＡからＨと、１２個の（凸）交線（ＡＢ、ＡＤ、ＡＦ、ＢＣ、ＢＧ、ＣＤ、ＣＨ、ＤＥ、ＥＦ、ＥＨ、ＦＧ、ＧＨ）の組と、６個の（長方形）平面Ｐ１＜ＡＢＣＤ＞、Ｐ２＜ＡＤＥＦ＞、Ｐ３＜ＡＢＧＦ＞、Ｐ４＜ＢＣＨＧ＞、Ｐ５＜ＣＤＥＨ＞、Ｐ６＜ＥＦＧＨ＞とを含み、平面ペア＜Ｐ１，Ｐ６＞、＜Ｐ２，Ｐ４＞、＜Ｐ３，Ｐ５＞は、互いに平行（かつ同一）である。
【００８７】
図１３の３Ｄ物体の保護区域を計算するため、３Ｄ立体物の尖点（すなわちＡからＨ）の座標に関連するデータを、近隣情報とともに、入力としてシステムにおいて（例えば、メモリ内に、またはプロセッサによって）受け取ることができる。近隣情報は、ハッシュマップに記憶することができ、そのキーは、頂点識別子であり、値は、近隣頂点識別子を含む集合への参照である。図１４は、図１３の例示的な３Ｄ物体についての例示的なハッシュマップを示している。マッピングは、頂点隣接性に関する情報を提供する。図１４の左列は、物体の尖点の各々に対応する（キー値としての）頂点識別子を含み、右列は、指定されたキー（尖点）に交線を介して隣接する尖点を含む。
【００８８】
システムの出力は、１組の物体であり、各物体は、以下の３つのパラメータ、すなわち、交線、交線に隣接する２つの平面、交線に沿った２つの平面の間の外角（凹または凸）を含むことができる。
【００８９】
出力を提供するため、個々の頂点座標および近隣情報が処理されて、平面を構成する１組の交線を識別する。図１３の例の場合、例えば、図１５のデータ構造のようなデータ構造を構築することができる。図１５は、例示的なハッシュマップを示しており、そのキーは、平面識別子（例えばＰ１からＰ６）であり、値は、図１３に示されるような関連する平面を構成する交線を含む集合への参照である。したがって、図１５は、平面に隣接する交線に関する情報を含む、図１３に示される３Ｄ物体についてのハッシュマップである。左列は、物体の平面の各々に対応する（キー値としての）平面識別子を含み、右列は、平面を含む（値としての）交線の集合を含む。
【００９０】
次に、図１５のハッシュマップを処理して、特定の交線に関連する平面を識別することができる。図１５のハッシュマップから、識別できる２つの隣接する平面に交線を関連付けることができる（例えば、図１５では、平面識別子がＰ１およびＰ３である２つの異なる交線の集合内に交線ＡＢが存在する）。
【００９１】
以下の情報、すなわち、交線（例えば、ＡＢ）、２つの平面識別子（例えば、ＡＢに隣接するＰ１およびＰ３）、ならびに交線に沿って２つの隣接する平面の間に形成される外角のタイプ（例えば、凹または凸）を含むことができる、１組のオブジェクトが構築される。例えば、図１４および図１５によれば、生成される１組のオブジェクトは、例えば、図１６の表に示されるようなものとすることができる。図１６は、物体の外角情報とともに、交線に接続する平面識別子を含む表である。平面識別子は、例えば、メタデータとしての、凹または凸の（外）角情報とともに、関連する交線を伴う。
【００９２】
続いて、図１６の表に示されるような、交線の個々の要素を処理して、（３Ｄ）物体のそれぞれの部分の保護区域を構築することができる。
【００９３】
本明細書で説明する例示的な実施形態を使用して、ＶＬＳＩ設計における構成要素のレイアウトを可能にするために、保護区域を計算することができる。回路構成要素（または機能ユニット／モジュールもしくは異なる部分回路のグループ／ブロック）は、構成要素間の電気的障害（または寄生効果）を回避するために、互いに一定の距離をおいて配置するように指定することができる。チップ上の回路構成要素は、３次元空間内の１組の立体物と見なすことができる。各回路構成要素（Ｃｉ）は、幅δｉの最小空き区域をＣｉの周りに維持するように、パラメータδｉに関連付けることができる。回路構成要素を収容するために必要とされる空間は、一般に、アイソセティック（ｉｓｏｔｈｅｔｉｃ）な３次元物体とすることができる。立体物に対する（指定された幅の）保護区域の位置は、例えば、３Ｄ  ＶＬＳＩ回路の設計において回路構成要素をサイズ変更するために使用することができる。
【００９４】
一例として、３Ｄ  ＶＬＳＩチップのブロックレベル設計の階層には、ｋ個のモジュール（Ｂ１，Ｂ２，．．．，Ｂｋ）を配置することができ、各Ｂｉは、残りのブロックＢｊ、ｊ≠ｉの各々から距離ｒｉ、１≦ｉ≦ｋを必要とする物体と見なすことができる。目的は、ｋ個のブロックすべての最小３Ｄ配置を計算することとすることができ、ＢｉおよびＢｊが隣接して配置される場合、これら２つのブロックの面上のすべての点ペア（一方はＢｉの面上にあり、他方はＢｊの面上にある）は、ｍａｘ（ｒｉ，ｒｊ）の最小分離、または場合によっては、ｒｉ＋ｒｊの最小分離にあることができる。部分回路の間の相互接続を達成するため、ブロックは、さらに遠ざける（または引き離す）ことができるが、上で述べた最小分離未満に調整することはできない。保護区域計算は、例えば、３Ｄ回路の所望のパッキング密度および／または効率的なレイアウトを達成するように、ブロックのレイアウトを決定するために、使用することができる。
【００９５】
いくつかの例では、保護区域（または安全区域）は、３Ｄ立体物のすべての可能な点または断面において計算されないことがある。代わりに、例えば、物体の各断面に沿った保護区域の近似を（補間を介して）達成するために、３Ｄ物体に沿った点または断面を選択することができる。
【００９６】
例示的な実施形態では、物体の外側の幅ｒの３Ｄ領域（または空間、保護区域）を計算することができる。他の例では、物体の内側の幅ｒの３Ｄ領域（または空間、保護区域）を計算することができる。例えば、３Ｄ物体は、中身が詰まっていないことがあり、代わりに、厚さｄの中空部分であること、または中空部分を含むことがある。したがって、物体の外側ばかりでなく、内側の保護区域も計算することができる。物体の内側の保護区域を計算するため、本明細書で説明する例示的な方法を実行することができる。３Ｄ物体の交線に沿った外角が凸（凹）である場合、（交線に沿った）内角は凹（凸）であることに留意されたい。
【００９７】
図１７は、物体の保護区域を計算するために構成された例示的なコンピューティングデバイス１７００を示すブロック図である。非常に基本的な構成１７０２では、コンピューティングデバイス１７００は、一般に、１つまたは複数のプロセッサ１７０４と、システムメモリ１７０６とを含む。メモリバス１７０８は、プロセッサ１７０４とシステムメモリ１７０６の間で通信するために使用することができる。
【００９８】
所望の構成に応じて、プロセッサ１７０４は、マイクロプロセッサ（μＰ）、マイクロコントローラ（μＣ）、デジタル信号プロセッサ（ＤＳＰ）、またはそれらの任意の組み合わせを含むが、それらに限定されない、任意のタイプを取ることができる。プロセッサ１７０４は、レベル１キャッシュ１７１０およびレベル２キャッシュ１７１２などの１つまたは複数のレベルのキャッシングと、プロセッサコア１７１４と、レジスタ１７１６とを含むことができる。プロセッサコア１７１４は、算術論理演算ユニット（ＡＬＵ）、浮動小数点ユニット（ＦＰＵ）、デジタル信号処理コア（ＤＳＰコア）、またはそれらの任意の組み合わせを含むことができる。メモリコントローラ１７１８も、プロセッサ１７０４とともに使用することができ、またはいくつかの実施では、メモリコントローラ１７１８は、プロセッサ１７０４の内部部品とすることができる。
【００９９】
所望の構成に応じて、システムメモリ１７０６は、（ＲＡＭなどの）揮発性メモリ、（ＲＯＭ、フラッシュメモリなどの）不揮発性メモリ、またはそれらの任意の組み合わせを含むが、それらに限定されない、任意のタイプを取ることができる。システムメモリ１７０６は、一般に、オペレーティングシステム１７２０と、１つまたは複数のアプリケーション１７２２と、プログラムデータ１７２４とを含む。アプリケーション１７２２は、コンピューティングデバイス１７００の構成に応じて、例えば、本明細書で説明する方法のいずれかを実行するように構成できる、アルゴリズム１７２６を含む。プログラムデータ１７２４は、例えば、頂点位置または識別子に対応する値１７２８を含む。いくつかの例示的な実施形態では、アプリケーション１７２２は、オペレーティングシステム１７２０上でプログラムデータ１７２４を用いて動作するように構成することができる。説明したこの基本構成は、図１７においては、破線１７０２内の構成要素によって示されている。
【０１００】
コンピューティングデバイス１７００は、追加の特徴または機能、ならびに基本構成１７０２と任意の必要なデバイスおよびインターフェースの間の通信を円滑化するための追加のインターフェースを有することができる。例えば、バス／インターフェースコントローラ１７３０は、ストレージインターフェースバス１７３２を介する、基本構成１７０２と１つまたは複数のデータ記憶装置１７３２の間の通信を円滑化するために使用することができる。データ記憶装置１７３２は、取外し式記憶装置１７３６、非取外し式記憶装置１７３８、またはそれらの組み合わせとすることができる。取外し式記憶装置および非取外し式記憶装置の例は、いくつかの名前を挙げると、フレキシブルディスクドライブおよびハードディスクドライブ（ＨＤＤ）などの磁気ディスク装置、コンパクトディスク（ＣＤ）ドライブまたはデジタル多用途ディスク（ＤＶＤ）ドライブなどの光ディスクドライブ、ソリッドステートドライブ（ＳＳＤ）、ならびにテープドライブを含む。例示的なコンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータなどの情報を記憶するための任意の方法または技術で実施された、揮発性および不揮発性の取外し式および非取外し式媒体を含むことができる。
【０１０１】
システムメモリ１７０６、取外し式ストレージ１７３６、および非取外し式ストレージ１７３８はすべて、コンピュータ記憶媒体の例である。コンピュータ記憶媒体（またはコンピュータ可読記憶媒体）は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、もしくは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）、もしくは他の光ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージ、もしくは他の磁気記憶装置、または所望の情報を記憶するのに使用でき、コンピューティングデバイス１７００によってアクセスできる他の任意の媒体を含むが、それらに限定されない。そのようなコンピュータ記憶媒体はいずれも、デバイス１７００の一部とすることができる。
【０１０２】
コンピューティングデバイス１７００は、バス／インターフェースコントローラ１７３０を介する、様々なインターフェース装置（例えば、出力インターフェース、周辺インターフェース、および通信インターフェース）から基本構成１７０２への通信を円滑化するための、インターフェースバス１７４０も含むことができる。例示的な出力インターフェース１７４２は、１つまたは複数のＡ／Ｖポート１７４８を介してディスプレイまたはスピーカなどの様々な外部装置と通信するように構成できる、グラフィック処理ユニット１７４４およびオーディオ処理ユニット１７４６を含む。例示的な周辺インターフェース１７５０は、１つまたは複数のＩ／Ｏポート１７５６を介して入力装置（例えば、キーボード、マウス、ペン、音声入力装置、タッチ入力装置など）または他の周辺装置（例えば、プリンタ、スキャナなど）などの外部装置と有線または無線接続を介して通信するように構成できる、シリアルインターフェースコントローラ１７５２またはパラレルインターフェースコントローラ１７５４を含む。例示的な通信インターフェース１７５８は、１つまたは複数の通信ポート１７６４を介する、ネットワーク通信による、１つまたは複数の他のコンピューティングデバイス１７６２との通信を円滑化するように構成できる、ネットワークコントローラ１７６０を含む。通信接続は、通信媒体の一例である。通信媒体は、変調データ信号内のコンピュータ可読命令、データ構造、プログラムモジュール、または他のデータによって一般に具現することができ、任意の情報配送媒体を含む。「変調データ信号」は、情報を信号内に符号化するような方法で、その特性の１つまたは複数が設定または変更された信号とすることができる。限定することなく、例を挙げると、通信媒体は、有線ネットワークまたは直接配線接続などの有線媒体、ならびに音響、無線周波（ＲＦ）、赤外線（ＩＲ）、および他の無線媒体などの無線媒体を含むことができる。
【０１０３】
コンピューティングデバイス１７００および／またはコンピューティングデバイスの部分は、セルフォン、携帯情報端末（ＰＤＡ）、パーソナルメディアプレーヤデバイス、ワイヤレスウェブ視聴デバイス、パーソナルハンドセットデバイス、特定用途デバイス、または上記機能のいずれかを含むハイブリッドデバイスなど、フォームファクタが小さいポータブル（またはモバイル）電子デバイスの一部として実施することができる。コンピューティングデバイス１７００は、ラップトップコンピュータと非ラップトップコンピュータ構成の両方を含むパーソナルコンピュータとして実施することもできる。
【０１０４】
図１８は、本明細書で提示される少なくともいくつかの実施形態に従って構成される、コンピューティングデバイス上でコンピュータプロセスを実行するためのコンピュータプログラムを含む、例示的なコンピュータプログラム製品１８００の概念的な部分図を示す概略図である。例示的なコンピュータプログラム製品１８００の例示的な実施形態が、信号伝達媒体１８０２を使用して提供される。信号伝達媒体１８０２は、例えば、プロセッサによって実行されたときに、図１〜図１７に関して上で説明した機能または機能の部分を提供できる、１つまたは複数のプログラミング命令１８０４を含むことができる。したがって、例えば、フロー図８００について言えば、図８のブロック８０２、８０４、８０６、８０８、８１０、８１２、８１４、８１６、８１８、８２０、８２２、８２４、８２６、８２８、８３０、８３２、および／または８３４の１つまたは複数の機能は、信号伝達媒体１８０２に関連する１つまたは複数の命令によって行うことができる。
【０１０５】
いくつかの例では、信号伝達媒体１８０２は、ハードディスクドライブ、コンパクトディスク（ＣＤ）、デジタルビデオディスク（ＤＶＤ）、デジタルテープ、メモリなどの、しかしそれらに限定されない、コンピュータ可読媒体１８０６を包含することができる。いくつかの実施では、信号伝達媒体１８０２は、メモリ、リード／ライト（Ｒ／Ｗ）ＣＤ、Ｒ／Ｗ  ＤＶＤなどの、しかしそれらに限定されない、コンピュータ記録可能媒体１８０８を包含することができる。いくつかの実施では、信号伝達媒体１８０２は、デジタルおよび／またはアナログ通信媒体（例えば、光ファイバケーブル、導波路、有線通信リンク、無線通信リンクなど）などの、しかしそれらに限定されない、通信媒体１８１０を包含することができる。したがって、例えば、信号伝達媒体１８０２は、無線形態の通信媒体１８１０（例えば、ＩＥＥＥ８０２．１１規格に準拠する無線通信媒体）によって伝達することができる。
【０１０６】
１つまたは複数のプログラミング命令１８０４は、例えば、コンピュータ実行可能および／または論理実施命令とすることができる。いくつかの例では、図１７のコンピューティングデバイス１７００などのコンピューティングデバイスは、コンピュータ可読媒体１８０６、コンピュータ記録可能媒体１８０８、および／または通信媒体１８１０の１つまたは複数によって、コンピューティングデバイス１７００に伝達されたプログラミング命令１８０４に応答して、様々な動作、機能、またはアクションを提供するように構成することができる。
【０１０７】
本開示は、様々な態様の例示として意図されている、本出願で説明した特定の実施形態に関して限定されない。当業者には明らかなように、本開示の主旨および範囲から逸脱することなく、多くの変更および変形を行うことができる。本明細書で列挙しているものに加えて、本開示の範囲内にある機能的に等価な方法および装置が、上述の説明から当業者には明らかである。そのような変更および変形は、添付の特許請求の範囲内に包含されることが意図されている。本開示は、添付の特許請求の範囲に加えて、そのような特許請求の範囲に権利が与えられる均等物の全範囲に関してのみ限定される。本開示は、当然様々であり得る、特定の方法、試薬、化合物、合成物、または生体系に限定されないことを理解されたい。本明細書で使用された用語は、特定の実施形態を説明するためのものにすぎず、限定する意図はないことも理解されたい。
【０１０８】
本明細書における実質的にすべての複数形および／または単数形の用語の使用に対して、当業者は、状況および／または用途に適切なように、複数形から単数形に、および／または単数形から複数形に変換することができる。様々な単数形／複数形の置き換えは、理解しやすいように、本明細書で明確に説明することができる。
【０１０９】
通常、本明細書において、特に添付の特許請求の範囲（たとえば、添付の特許請求の範囲の本体部）において使用される用語は、全体を通じて「オープンな（ｏｐｅｎ）」用語として意図されていることが、当業者には理解されよう（例えば、用語「含む（ｉｎｃｌｕｄｉｎｇ）」は、「含むがそれに限定されない（ｉｎｃｌｕｄｉｎｇ  ｂｕｔ  ｎｏｔ  ｌｉｍｉｔｅｄ  ｔｏ）」と解釈されるべきであり、用語「有する（ｈａｖｉｎｇ）」は、「少なくとも有する（ｈａｖｉｎｇ  ａｔ  ｌｅａｓｔ）」と解釈されるべきであり、用語「含む（ｉｎｃｌｕｄｅｓ）」は、「含むがそれに限定されない（ｉｎｃｌｕｄｅｓ  ｂｕｔ  ｉｓ  ｎｏｔ  ｌｉｍｉｔｅｄ  ｔｏ）」と解釈されるべきである、など）。導入される請求項で具体的な数の記載が意図される場合、そのような意図は、当該請求項において明示的に記載されることになり、そのような記載がない場合、そのような意図は存在しないことが、当業者にはさらに理解されよう。例えば、理解の一助として、添付の特許請求の範囲は、導入句「少なくとも１つの（ａｔ  ｌｅａｓｔ  ｏｎｅ）」および「１つまたは複数の（ｏｎｅ  ｏｒ  ｍｏｒｅ）」を使用して請求項の記載を導くことを含む場合がある。しかし、そのような句の使用は、同一の請求項が、導入句「１つまたは複数の」または「少なくとも１つの」および「ａ」または「ａｎ」などの不定冠詞を含む場合であっても、不定冠詞「ａ」または「ａｎ」による請求項の記載の導入が、そのように導入される請求項の記載を含む任意の特定の請求項を、単に１つのそのような記載を含む実施形態に限定する、ということを示唆していると解釈されるべきではない（例えば、「ａ」および／または「ａｎ」は、「少なくとも１つの」または「１つまたは複数の」を意味すると解釈されるべきである）。同じことが、請求項の記載を導入するのに使用される定冠詞の使用にも当てはまる。また、導入される請求項の記載で具体的な数が明示的に記載されている場合でも、そのような記載は、少なくとも記載された数を意味すると解釈されるべきであることが、当業者には理解されよう（例えば、他の修飾語なしでの「２つの記載（ｔｗｏ  ｒｅｃｉｔａｔｉｏｎｓ）」の単なる記載は、少なくとも２つの記載、または２つ以上の記載を意味する）。さらに、「Ａ、ＢおよびＣ、などの少なくとも１つ」に類似の慣例表現が使用されている事例では、通常、そのような構文は、当業者がその慣例表現を理解するであろう意味で意図されている（例えば、「Ａ、Ｂ、およびＣの少なくとも１つを有するシステム」は、Ａのみ、Ｂのみ、Ｃのみ、ＡおよびＢを共に、ＡおよびＣを共に、ＢおよびＣを共に、ならびに／またはＡ、Ｂ、およびＣを共に、などを有するシステムを含むが、それに限定されない）。「Ａ、Ｂ、またはＣ、などの少なくとも１つ」に類似の慣例表現が使用されている事例では、通常、そのような構文は、当業者がその慣例表現を理解するであろう意味で意図されている（例えば、「Ａ、Ｂ、またはＣの少なくとも１つを有するシステム」は、Ａのみ、Ｂのみ、Ｃのみ、ＡおよびＢを共に、ＡおよびＣを共に、ＢおよびＣを共に、ならびに／またはＡ、Ｂ、およびＣを共に、などを有するシステムを含むが、���れに限定されない）。２つ以上の代替用語を提示する事実上いかなる離接する語および／または句も、明細書、特許請求の範囲、または図面のどこにあっても、当該用語の一方（ｏｎｅ  ｏｆ  ｔｈｅ  ｔｅｒｍｓ）、当該用語のいずれか（ｅｉｔｈｅｒ  ｏｆ  ｔｈｅ  ｔｅｒｍｓ）、または両方の用語（ｂｏｔｈ  ｔｅｒｍｓ）を含む可能性を企図すると理解されるべきであることが、当業者にはさらに理解されよう。例えば、句「ＡまたはＢ」は、「Ａ」または「Ｂ」あるいは「ＡおよびＢ」の可能性を含むことが理解されよう。
【０１１０】
加えて、本開示の特徴または態様がマーカッシュグループに関して説明される場合、本開示が、それによって、マーカッシュグループのいずれか個々の要素または要素からなるサブグループに関しても説明されていることを当業者は理解されよう。
【０１１１】
当業者によって理解されるように、文書による説明を提供することなどに関するありとあらゆる目的のため、本明細書で開示されたすべての範囲は、すべての範囲のありとあらゆる可能な部分範囲および部分範囲の組み合わせも包含する。いずれの列挙された範囲も、当該範囲を十分に説明したものとして、また当該範囲を少なくとも等分に２分割、３分割、４分割、５分割、１０分割などすることが可能なものとして容易に認識することができる。非限定的な一例として、本明細書で説明された各範囲は、下位３分の１、中間３分の１、および上位３分の１などに容易に分割することができる。やはり当業者によって理解されるように、「最大で」、「少なくとも」、「より大きい」、「より少ない」などのすべての言葉は、挙げられた数を含み、上で説明されたように後で部分範囲に分割できる範囲に言及している。最後に、当業者によって理解されるように、範囲は、各個別要素を含む。したがって、例えば、１つ〜３つのセルを有する群は、１つ、２つ、または３つのセルを有する群に言及している。同様に、１つ〜５つのセルを有する群は、１つ、２つ、３つ、４つ、または５つのセルを有する群に言及しており、その他についても同様である。
【０１１２】
本明細書において様々な態様および実施形態が開示されたが、他の態様および実施形態も当業者には明らかである。本明細書において開示された様々な態様および実施形態は、説明を目的としており、限定的であることは意図しておらず、真の範囲および主旨は、以下の特許請求の範囲によって示されている。
【図１】
0005726330.tif 000003
【図２】
0005726330.tif 000004
【図３】
0005726330.tif 000005
【図４】
0005726330.tif 000006
【図５】
0005726330.tif 000007
【図６】
0005726330.tif 000008
【図７（ａ）】
0005726330.tif 000009
【図７（ｂ）】
0005726330.tif 000010
【図７（ｃ）】
0005726330.tif 000011
【図７（ｄ）】
0005726330.tif 000012
【図７（ｅ）】
0005726330.tif 000013
【図８】
0005726330.tif 000014
【図９（ａ）】
0005726330.tif 000015
【図９（ｂ）】
0005726330.tif 000016
【図９（ｃ）】
0005726330.tif 000017
【図９（ｄ）】
0005726330.tif 000018
【図１０】
0005726330.tif 000019
【図１１】
0005726330.tif 000020
【図１２ａ】
0005726330.tif 000021
【図１２ｂ】
0005726330.tif 000022
【図１３】
0005726330.tif 000023
【図１４】
0005726330.tif 000024
【図１５】
0005726330.tif 000025
【図１６】
0005726330.tif 000026
【図１７】
0005726330.tif 000027
【図１８】
0005726330.tif 000028