境界ボリューム: コンピューター ビジョンにおける空間表現の探求

By Fouad Sabry

バウンディングボリュームとは

コンピュータ グラフィックスおよび計算幾何学では、オブジェクトのセットの境界ボリュームは、セット内のオブジェクトの結合を完全に含む閉じた領域です。バウンディング ボリュームは、単純な領域を使用するなど、幾何学的操作の効率を向上させるために使用され、重複をテストする簡単な方法が得られます。

どのようなメリットがあるのか

(I) 以下のトピックに関する洞察と検証:

第 1 章: 境界ボリューム

第 2 章: スフィア

第 3 章: 楕円体

第 4 章: 衝突検出

第 5 章: コーン

第 6 章: シリンダー

第 7 章: 凸多面体

第 8 章: 境界ボリューム階層

第 9 章: 最小境界ボックス

第 10 章: 幾何学的な区切り記号

(II) 境界ボリュームに関する一般のトップの質問に答える。

(III) 多くの分野でバウンディング ボリュームを使用する実際の例。

この本は誰に向けたものなのか

専門家、学部生および大学院生、愛好家、趣味人、およびあらゆる種類のバウンディング ボリュームに関する基本的な知識や情報を超えたいと考えている人。

• Language: 日本語
• Publisher: 10億人の知識があります [Japanese]
• Release date: May 4, 2024

Book preview

第 1 章: バウンディング ボリューム

コンピュータグラフィックスや計算幾何学では、オブジェクトの集合のバウンディングボリュームは、それらの結合を完全に囲む閉じたボリュームです。単純なボリュームを使用してより複雑なオブジェクトを保持し、境界ボリュームを使用して幾何学的プロセスの効率を高めます。通常、単純なボリュームには、より単純なオーバーラップ検出方法があります。

項目のコレクションのバウンディングボリュームは、それらの和集合によって形成されるオブジェクトのバウンディングボリュームでもあり、その逆も同様です。したがって、記述は、空ではなく、有界 (有限) であると推定される単一のオブジェクトに制限できます。

ほとんどの場合、バウンディングボリュームは特定のタイプのテストを高速化するために使用されます。

レイトレーシングでは、バウンディングボリュームはレイ交差テストに使用され、多くのレンダリング手法では、錐台テストに使用されます。光線または視錐台がバウンディング ボリュームと交差しない場合、その中に含まれる項目と交差することは不可能であり、些細な拒絶が可能になります。同様に、錐台に境界ボリュームの全体が含まれている場合は、追加の検査なしで内容が受け入れられる可能性があります。これらの交差テストは、表示可能なオブジェクト(レンダリング、ラスタライズ)のリストを生成します。

衝突検出の 2 つのバウンディング ボリュームが交差しない場合、含まれるオブジェクトは衝突できません。

バウンディングボリュームのジオメトリは単純化されているため、バウンディングボリュームに対するテストは、多くの場合、アイテム自体に対するテストよりもはるかに高速です。これは、「オブジェクト」がポリゴンまたはポリゴンを使用して近似されるデータ構造で構成されることが多いという事実によるものです。オブジェクトが表示されない場合、各ポリゴンをビュー ボリュームに対してテストするのは計算効率が悪くなります。(画面上のオブジェクトは、その表面が表示されているかどうかに関係なく、画面に「クリップ」する必要があります。

複雑なオブジェクトのバウンディングボリュームを取得するには、シーングラフまたはOBBツリーなどのバウンディングボリューム階層を使用して、オブジェクト/シーンを分解するのが通例です。主なアイデアは、シーンをツリーのような構造で整理し、ルートがシーン全体を表し、各リーフがコンポーネントを表すことです。

「ビジュアルハル」は、コンピューターステレオビジョン内のアイテムのシルエットから再構築された境界ボリュームです。

オブジェクトのバウンディング ボリュームを計算する計算コスト、オブジェクトが移動したり、形状やサイズを変更したりできるアプリケーションでバウンディング ボリュームを更新するコスト、交差を決定するコスト、および交差テストに必要な精度は、特定のアプリケーションのバウンディング ボリュームのタイプの選択に影響を与えます。交差テストの精度は、境界オブジェクトに関連付けられていない境界ボリューム内の空隙スペースの量に比例します。一般に、高度なバウンディング ボリュームでは、空き領域は少なくなりますが、処理コストが高くなります。迅速だが不正確なテスト用の安価なものと、より正確だがより高価なものなど、複数のタイプを同時に採用するのが一般的です。

ここで説明するすべてのタイプには、凸状の境界ボリュームがあります。拘束されている項目が凸状であることがわかっている場合、これは拘束ではありません。非凸境界ボリュームが必要な場合は、多数の凸境界ボリュームの和集合として表すことができます。残念ながら、交差チェックは、バウンディングボックスの複雑さが増すにつれて、徐々にコストが高くなります。

オブジェクトのバウンディングボックスは直方体、つまり 2 次元では長方形です。動的シミュレーションでは、交差テストの精度が不可欠な場合、ほぼ直方体形状のオブジェクトに対して、境界球や円柱などの代替タイプの境界ボリュームよりも境界ボックスが優先されます。地面に横たわっている自動車など、他の人の上に載っている物体の場合、その利点は明らかです。バウンディングスフィアは、車が地面と交差する可能性があることを示しており、拒否するには車の実際のモデルのより高価なテストが必要になります。ただし、バウンディングボックスは、車が地面と交差していないことを即座に示すため、より高価なテストが不要になります。

多くのアプリケーションでは、境界ボックスは座標系の軸に位置合わせされ、その時点で軸に平行な境界ボックス (AABB) と呼ばれます。一般的な状況を AABB と区別するために、任意の境界ボックスは、既存のオブジェクトのローカル座標系が採用されている場合、方向付き境界ボックス (OBB) または OOBB と呼ばれることがあります。AABBはOBBよりも交差の検証が容易ですが、モデルを回転させると再計算が必要となり、単純に回転させることはできません。

バウンディングカプセルは、オブジェクトを囲むスイープ球(球体が直線セグメントに沿って移動するときに占める体積)です。スイープされた球体の半径と、スイープされた球体がスイープされるセクションを使用して、カプセルをシンボル表示できます。円柱と特性を共有していますが、交差試験がそれほど複雑ではないため、操作が簡単です。カプセルと別のオブジェクトが交差するのは、カプセルの定義セグメントと他のオブジェクトのフィーチャとの間の距離がカプセルの半径よりも小さい場合です。たとえば、2つのカプセルは、セグメント間の距離が半径の合計よりも小さい場合に交差します。これは任意に回転するカプセルにも当てはまるため、実際の用途ではシリンダーよりも望ましいものになります。

外接円柱は、アイテムを含む円柱です。円柱の軸は、多くの場合、ほとんどのアプリケーションでシーンの垂直方向に位置合わせされます。円柱は、垂直軸に沿ってのみ回転でき、他の軸については回転できず、それ以外は並進運動のみに制限される 3 次元オブジェクトに適しています。垂直軸に平行な 2 つの円柱は、垂直軸上の投影 (2 つの線分) と水平面上の投影 (2 つの円形円盤) が同時に交差するときに衝突します。それぞれを簡単にテストできます。ビデオゲームでは、バウンディングシリンダーは直立した人のバウンディングボリュームとして頻繁に使用されます。

オブジェクトの境界楕円体は、オブジェクトを含む楕円体です。通常、楕円体は球体よりもタイトなフィッティングを生成します。楕円体との交差は、楕円体の主軸に沿って、楕円体の半径の乗法の逆数に等しい係数で他のオブジェクトをスケーリングすることで実現されるため、スケーリングされた項目を単位球と交差させるように問題が単純化されます。適用されたスケーリングによってスキューが発生する場合は、複雑にならないように注意する必要があります。スキューは、2 つの任意の楕円体が衝突する場合など、状況によっては楕円体の使用を実行できなくなる可能性があります。

バウンディング スフィアは、オブジェクトが格納されているフィアです。2次元グラフィックスでは、これは円です。球状境界の中心と半径は、球状境界を表します。2 つの球体は、中心間の距離が半径の合計よりも小さい場合に衝突します。これは、衝突の非常に迅速なテストです。これにより、バウンディング スフィアは任意の次元でオブジェクトを移動するのに適しています。

境界スラブは、軸に沿ってある程度投影されるボリュームであり、2 つの平面で囲まれたスラブとも呼ばれます。境界ボックスは、直交する方向を持つ境界スラブの交差です。バウンディング スラブは、レイ トレーシングを高速化するために使用されました。

2-D 境界三角形は、B スプライン曲線のクリッピングまたは可視領域テストを高速化するのに非常に役立ちます。その適用の図については、「クリッピング (コンピュータグラフィックス)」の「円と B スプラインのクリッピングアルゴリズム」を参照してください。

オブジェクトの凸包は、それを含むことができる最小の凸状ボリュームです。その凸包は、物体が有限の点の集合の和集合である場合、多面体である。

離散配向ポリトープ (DOP) は、バウンディング ボックスの概念を拡張します。k-DOP は、ブール論理を使用した k 方向に沿った範囲の交差です。したがって、k-DOPは、k個のバウンディングスラブと、そのアイテムを含む凸多面体(2次元では多角形、3次元では多面体)のブール積集合です。2-DOP 特殊ケースは 2-D 四角形であり、3-DOP 特殊ケースは 3-D ボックスです。DOPの軸は直交している必要はなく、空間次元よりも多くの軸が存在する可能性があります。たとえば、すべての辺と角が面取りされた 3-D ボックスは、13-DOP として作成できます。一部の面が縮退し、エッジまたは頂点に縮小される場合、実際の面の数は k の 2 倍未満になることがあります。

最小外接四角形 (MBR) (2-D で最小の AABB) は、地理 (または「地理空間」) データ項目の記述で一般的に使用され、データ検索 (該当する場合は空間クエリを含む) と表示の目的で、データセットの空間範囲 (地理空間メタデータを参照) の簡略化されたプロキシとして機能します。また、R ツリー空間インデックス手法の基本的なコンポーネントでもあります。

バウンディングボリュームの一部の形式(OBBおよび凸多面体)では、分離軸定理が効果的なチェックを提供します。2 つのオブジェクトが重なり合わない軸が存在する場合、2 つのオブジェクトは交差しません。通常、調査される軸は、ボリュームの基本軸 (AABB の場合は単位軸、OBB の場合は各 OBB の 3 つの基本軸) です。多くの場合、これに続いて、前の軸の外積 (各オブジェクトから 1 つの軸) を調べます。

AABBの場合、単位軸に関しては、このテストは基本的なオーバーラップテストのシーケンスになります。

M,N で定義される AABB と O,P で定義される AABB が (Mx > Px) または (Ox > Nx) または (My > Py) または (Oy > Ny) または (Mz > Pz)