Loading article…
コンピュータグラフィックスや計算幾何学において、オブジェクトの集合に対する境界ボリューム（または境界領域）とは、その集合に含まれるオブジェクトの和集合を完全に包含する閉じた領域のことです。境界ボリュームは、単純な領域を使用したり、重なりを判定するより簡単な方法を用意したりするなど、幾何学的演算の効率を向上させるために使用されます。
複数のオブジェクトの境界体積は、それらの集合の和集合からなる単一のオブジェクトの境界体積でもあり、その逆もまた然りです。したがって、記述を単一のオブジェクトの場合に限定することが可能であり、その単一のオブジェクトは空ではなく、有界（有限）であると仮定されます。
バウンディングボリュームは、特定の種類のテストを高速化するために最もよく使用されます。
レイトレーシングでは、バウンディングボリュームはレイ交差判定に使用され、多くのレンダリングアルゴリズムでは、ビューフラスタム判定に使用されます。レイまたはビューフラスタムがバウンディングボリュームと交差しない場合、その内部に含まれるオブジェクトと交差することはないため、簡単に拒否できます。同様に、フラスタムがバウンディングボリューム全体を含んでいる場合、その内容は追加のテストなしで簡単に受け入れられます。これらの交差判定によって、「表示」（レンダリング、ラスタライズ）する必要のあるオブジェクトのリストが生成されます。
衝突検出において、2つの境界ボリュームが交差しない場合、その中に含まれるオブジェクトは衝突しない。
バウンディングボリュームに対するテストは、オブジェクト自体に対するテストよりもはるかに高速です。これは、バウンディングボリュームの形状が単純であるためです。オブジェクトは通常、ポリゴンまたはポリゴン近似に縮小されたデータ構造で構成されています。いずれの場合も、オブジェクトが表示されていない場合は、各ポリゴンをビューボリュームに対してテストするのは計算的に無駄です。（画面上のオブジェクトは、その表面が実際に表示されているかどうかに関わらず、画面に「クリップ」する必要があります。）
複雑なオブジェクトのバウンディングボリュームを取得する一般的な方法は、シーングラフ、より具体的にはOBBツリーなどのバウンディングボリューム階層を使用してオブジェクト/シーンを分割することです。この背後にある基本的な考え方は、ルートがシーン全体を構成し、各リーフがより小さなサブパートを含むツリー状の構造でシーンを整理することです。[ 1 ]
コンピュータステレオビジョンでは、物体のシルエットから再構築された境界ボリュームは「ビジュアルハル」として知られています。[ 2 ]
特定のアプリケーションにおける境界ボリュームの種類の選択は、さまざまな要因によって決まります。オブジェクトの境界ボリュームを計算する際の計算コスト、オブジェクトが移動したり形状やサイズが変わったりするアプリケーションで境界ボリュームを更新する際のコスト、交差判定のコスト、および交差判定に必要な精度などです。交差判定の精度は、境界ボリューム内で境界オブジェクトに関連付けられていない空間の量（ボイドスペース）に関係します。高度な境界ボリュームは一般的にボイドスペースを少なくできますが、計算コストが高くなります。多くの場合、複数の種類を組み合わせて使用します。例えば、安価で迅速な大まかな判定が可能なものと、より高精度でコストも高いものを組み合わせて使用するといった具合です。
ここで扱う型はすべて凸境界ボリュームを生成します。境界を付ける対象が凸であることが分かっている場合は、これは制約になりません。非凸境界ボリュームが必要な場合は、複数の凸境界ボリュームの和集合として表現する方法があります。ただし、境界ボリュームが複雑になるにつれて、交差判定のコストは急速に高くなります。
バウンディングボックス、または最小バウンディングボックス（MBB）は、オブジェクトを囲む直方体、または2次元では長方形です。動的シミュレーションでは、交差判定をかなり正確に行う必要がある場合、おおよそ直方体形状のオブジェクトに対して、バウンディング球や円柱などの他の形状のバウンディングボリュームよりもバウンディングボックスが好まれます。その利点は明らかです。たとえば、地面に置かれた車のように、他のオブジェクトの上に載っているオブジェクトの場合、バウンディング球では車が地面と交差する可能性があると表示され、その後、車の実際のモデルに対するよりコストのかかるテストによってそれを拒否する必要があります。一方、バウンディングボックスでは、車が地面と交差していないことがすぐに表示されるため、よりコストのかかるテストを省略できます。
最小境界矩形（MBR）は、2次元における最小のAABBであり、地理データ（または「地理空間」データ）項目の説明によく用いられます。これは、データ検索（該当する場合は空間クエリを含む）および表示のために、データセットの空間範囲（地理空間メタデータを参照）を簡略化した代理変数として機能します。また、空間インデックス作成のRツリー方式の基本要素でもあります。
多くのアプリケーションでは、境界ボックスは座標系の軸に沿って配置され、軸に沿った境界ボックスとして知られています（AABB）。一般的なケースをAABBと区別するために、任意のバウンディングボックスは、方向付きバウンディングボックス（OBB）、またはOOBBは、既存オブジェクトのローカル座標系が使用されている場合に発生します。AABBはOBBよりも交差判定がはるかに簡単ですが、モデルが回転すると単純に一緒に回転させることができず、再計算する必要があるという欠点があります。
Aバウンディングカプセルは、対象物を含むスイープ球です。カプセルは、スイープ球の半径と、球がスイープされるセグメントによって表すことができます。カプセルは円柱に似た特性を持ちますが、交差判定が簡単なため、使いやすくなっています。カプセルと他のオブジェクトは、カプセルの定義セグメントと他のオブジェクトの何らかの特徴との間の距離がカプセルの半径よりも小さい場合に交差します。たとえば、2つのカプセルは、カプセルのセグメント間の距離がそれらの半径の合計よりも小さい場合に交差します。これは、任意の回転カプセルにも当てはまるため、実際には円柱よりも魅力的です。
Aバウンディングシリンダーとは、オブジェクトを囲む円筒のことです。ほとんどのアプリケーションでは、シリンダーの軸はシーンの垂直方向と平行になります。シリンダーは、垂直軸を中心に回転することはできても、他の軸を中心に回転することはできず、移動も平行移動のみに制限されている3Dオブジェクトに適しています。垂直軸に沿って配置された2つのシリンダーは、垂直軸への投影（2つの線分）と水平面への投影（2つの円盤）が同時に交差するときに交差します。どちらも簡単にテストできます。ビデオゲーム、バウンディングシリンダーは、直立した人物のバウンディングボリュームとしてよく使用されます。
A境界楕円体とは、対象物を包含する楕円体のことです。楕円体は通常、球よりもぴったりと対象物を囲みます。楕円体との交差は、対象物を主軸逆数に等しい量だけ縮小することで行われます。これにより、問題は拡大縮小された対象物と単位球歪みが生じる場合は、問題を回避するよう注意が必要です。歪みによって、例えば任意の2つの楕円体の衝突など、特定のケースでは楕円体の使用が非現実的になることがあります。
バウンディングスフィアとは、対象物を囲む球体のことです。2次元グラフィックスでは、これは円に相当します。バウンディングスフィアは中心と半径で表されます。バウンディングスフィアは衝突判定が非常に高速です。2つの球体の中心間の距離が半径の合計を超えない場合、それらは交差していると判定されます。このため、バウンディングスフィアは、任意の次元で移動可能なオブジェクトに適しています。
Aバウンディングスラブは、軸上に投影されるボリュームであり、スラブ、レイ トレーシングを高速化するために使用されてきました[ 3 ]
A2次元空間における境界三角形は、Bスプライン曲線のクリッピングや可視性判定を高速化するのに非常に役立ちます。使用例については、「クリッピング（コンピュータグラフィックス）」の「円とBスプラインのクリッピングアルゴリズム」
凸包とは、対象物を包含する最小の凸体積のことである。対象物が有限個の点の集合の和集合である場合、その凸包は多面体となる。
A離散方向多面体(DOP) は、境界ボックスを一般化したものです。k-DOP は、k方向に沿った範囲のブール交差です。したがって、kk 個の境界スラブのブール交差オブジェクト (2 次元では多角形、3 次元では多面体凸多面体。2 次元の長方形は 2-DOP の特殊なケースであり、3 次元のボックスは 3-DOP の特殊なケースです。一般に、DOP の軸は直交している必要はなく、空間の次元よりも多くの軸を持つことができます。たとえば、すべての辺と角が面取りされた 3 次元ボックスは 13-DOP として構築できます。一部の面が縮退して辺または頂点に縮小すると、k
一部の境界体積（OBBおよび凸多面体）の場合、分離軸定理は有効な検証手段となります。この定理の考え方は、オブジェクトが重ならない軸が存在する場合、オブジェクトは交差しないというものです。通常、検証される軸は、体積の基本軸（AABBの場合は単位軸、OBBの場合は各OBBの3つの基本軸）です。多くの場合、これに続いて、前述の軸（各オブジェクトの1つの軸）の積も検証されます。
AABB の場合、このテストは単位軸に関して単純な重なりテストのセットになります。M 、Nで定義されるAABBとO、Pで定義される AABB は、 ( M x > P x ) または ( O x > N x ) または ( M y > P y ) または ( O y > N y )または( M z > P z )または ( O z > N z ) の場合、交差しません。
AABBは軸に沿って投影することもできます。たとえば、辺の長さがLで中心がCにあるAABBが、軸Nに沿って投影される場合などです。 、 そしてまたは、 そして ここで、mとnはそれぞれ最小範囲と最大範囲を表す。
OBBもこの点では似ていますが、少し複雑です。上記のようにLとCを持ち、I、J、KをOBBの基軸とするOBBの場合、次のようになります。
範囲m、nおよびo、pについては、 m > pまたはo > nの場合、交差しないと言えます。したがって、2 つの OBB の範囲を各 OBB の I、J、K 軸に投影し、交差しないかどうかを確認することで、交差しないかどうかを検出できます。さらに、これらの軸の積 (I 0 ×I 1、I 0 ×J 1、...) に沿って確認することで、交差が不可能であることをより確実にすることができます。
軸投影を用いて非交差を判定するというこの概念は、凸多面体にも適用できますが、その場合は基軸の代わりに各多面体の面の法線が使用され、範囲は各頂点と軸との最小および最大の内積に基づいて決定されます。なお、この説明では、判定はワールド空間で行われることを前提としています。
2 つのk - DOPの交差はAABB と非常によく似た方法で計算できます。各方向について、2 つの DOP の対応する 2 つの区間をチェックするだけです。したがって、DOP が AABB の一般化であるのと同様に、交差テストは AABB の重なりテストの一般化です。2 つの DOP の重なりテストの複雑さはO( k )です。ただし、これは両方の DOP が同じ方向のセットに関して与えられていることを前提としています。どちらか一方が回転している場合は、これはもはや真ではありません。その場合、2 つの DOP をチェックする比較的簡単な方法の 1 つは、交差部分は回転したものを囲むものであり、、別の最小の囲みDOPによってこれは、第１のDOPの向きに関して配向されている。その手順はもう少し複雑ですが、最終的にはO( k )の計算量を持つ行列ベクトル乗算に相当します。[ 4 ]
