Computer-graphics-visible-surface-detection
可視表面検出
不透明なオブジェクトと表面を含む画像を表示すると、目に近いオブジェクトの背後にあるオブジェクトをビューから見ることができません。 現実的な画面イメージを得るには、これらの隠された表面を削除する必要があります。 これらの表面の識別と除去は、*隠面問題*と呼ばれます。
隠れた表面の問題を除去するための2つのアプローチがあります-オブジェクト空間法*と*画像空間法。 オブジェクト空間法は物理座標系で実装され、画像空間法は画面座標系で実装されます。
2D画面に3Dオブジェクトを表示する場合、選択した表示位置から見える画面の部分を識別する必要があります。
深度バッファ（Zバッファ）メソッド
この方法はCutmullによって開発されました。 これはイメージ空間アプローチです。 基本的な考え方は、各サーフェスのZ深度をテストして、最も近い（可視の）サーフェスを決定することです。
この方法では、各サーフェスは、サーフェス全体で一度に1つのピクセル位置で個別に処理されます。 ピクセルの深度値が比較され、最も近い（最小のz）表面がフレームバッファーに表示される色を決定します。
ポリゴンの表面に非常に効率的に適用されます。 表面は任意の順序で処理できます。 遠いポリゴンから近いポリゴンをオーバーライドするには、 frame buffer および* depth buffer、*という名前の2つのバッファーが使用されます。
- 深さバッファ*は、サーフェスが処理されるときに（0≤深さ≤1）、（x、y）位置の深さ値を格納するために使用されます。
- フレームバッファ*は、各位置（x、y）のカラー値の強度値を格納するために使用されます。
Z座標は通常、範囲[0、1]に正規化されます。 Z座標の0の値は後方のクリッピングペインを示し、Z座標の1の値は前方のクリッピングペインを示します。
アルゴリズム
- ステップ-1 *-バッファ値を設定します-
深度バッファ（x、y）= 0
フレームバッファ（x、y）=背景色
- ステップ-2 *-各ポリゴンを処理します（一度に1つ）
ポリゴンの投影された（x、y）ピクセル位置ごとに、深度zを計算します。
Z> depthbuffer（x、y）の場合
表面色の計算、
デプスバッファ（x、y）= zを設定
フレームバッファ（x、y）= surfacecolor（x、y）
利点
- 実装は簡単です。
- ハードウェアに実装されている場合、速度の問題が軽減されます。
- 一度に1つのオブジェクトを処理します。
デメリット
- 大きなメモリが必要です。
- 時間のかかるプロセスです。
スキャンライン方式
これは、目に見える表面を識別するための画像空間法です。 このメソッドには、単一のスキャンラインのみの深度情報があります。 深度値の1つのスキャンラインを必要とするために、次のスキャンラインを処理する前に、特定のスキャンラインと交差するすべてのポリゴンを同時にグループ化して処理する必要があります。 このために、* edgeテーブル*と* polygonテーブル*の2つの重要なテーブルが維持されています。
*The Edge Table* -シーン内の各ラインの座標エンドポイント、各ラインの逆スロープ、およびエッジをサーフェスに接続するためのポリゴンテーブルへのポインターが含まれています。ポリゴンテーブル-平面係数、サーフェスマテリアルプロパティ、その他のサーフェスデータが含まれ、エッジテーブルへのポインタである場合があります。
特定のスキャンラインを横切る表面の検索を容易にするために、アクティブなエッジのリストが形成されます。 アクティブリストには、スキャンラインを横切るエッジのみがxの昇順で保存されます。 また、スキャンラインに沿った位置がサーフェスの内側か外側かを示すフラグが各サーフェスに設定されます。
各スキャンラインのピクセル位置は左から右に処理されます。 サーフェスとの左の交差点で、サーフェスフラグがオンになり、右側でフラグがオフになります。 特定のスキャンライン位置で複数のサーフェスのフラグがオンになっている場合にのみ、深度計算を実行する必要があります。
エリア細分化方法
領域の細分化方法は、単一の表面の一部を表すビュー領域を見つけることで利用します。 各表示領域が単一の可視表面の一部の投影になるか、表面がまったくなくなるまで、表示領域全体をますます小さな長方形に分割します。
サブディビジョンが単一のサーフェスに属するものとして簡単に分析されるまで、または単一ピクセルのサイズに縮小されるまで、このプロセスを続けます。 これを簡単に行うには、各ステップでエリアを4つの等しい部分に連続的に分割します。 指定された領域境界とサーフェスが持つことができる4つの可能な関係があります。
- 周囲の表面-領域を完全に囲むもの。
- 重複する表面-部分的に領域の内側と外側にあるもの。
- 内側の表面-完全に領域の内側にあるもの。
- 外面-領域の完全に外側にあるもの。
エリア内の表面可視性を決定するためのテストは、これらの4つの分類の観点から述べることができます。 次の条件のいずれかが当てはまる場合、指定された領域のさらなる細分化は必要ありません-
- すべての表面は、面積に関して外側の表面です。
- 領域内にあるのは、内側、オーバーラップ、または周囲の1つの表面のみです。
- 周囲の表面は、エリア境界内の他のすべての表面を覆い隠します。
背面検出
多面体の背面を識別するための高速でシンプルなオブジェクト空間の方法は、「内部-外部」テストに基づいています。 点（x、y、z）は、平面パラメーターA、B、C、およびDのポリゴンサーフェスの「内側」にあります。私たちはその顔の内側にいて、表示位置から正面を見ることができません）。
デカルト成分（A、B、C）を持つポリゴンサーフェスに対する法線ベクトル N を考慮することにより、このテストを簡略化できます。
一般に、Vが目（または「カメラ」）位置からの視線方向のベクトルである場合、このポリゴンは
*V.N> 0*さらに、オブジェクトの説明が投影座標に変換され、表示方向が表示z軸に平行な場合、-
V =（0、0、V〜z〜）およびV.N = V〜Z〜C
したがって、Cの符号のみを法線ベクトル N のコンポーネントと見なす必要があります。
負の$ Z _ \ {V} $軸に沿った表示方向を持つ右手系表示システムでは、C <0の場合、ポリゴンは背面になります。 また、視線方向がそのポリゴンに向かっているため、法線のzコンポーネントがC = 0である面は表示されません。 したがって、一般的に、その法線ベクトルがz成分値を持っている場合、背面として任意のポリゴンにラベルを付けることができます-
*C <= 0*同様の方法は、左利きの表示システムを使用するパッケージで使用できます。 これらのパッケージでは、平面パラメータA、B、C、およびDは、右回りシステムで使用される反時計回りとは異なり、時計回りに指定されたポリゴン頂点座標から計算できます。
また、背面には表示位置から離れる方向を指す法線ベクトルがあり、表示方向が正の$ Z _ \ {v} $軸に沿っている場合、C> = 0で識別されます。 オブジェクトを定義するさまざまな平面のパラメーターCを調べることにより、すべての背面をすぐに識別できます。
A-Bufferメソッド
A-bufferメソッドは、depth-bufferメソッドを拡張したものです。 A-bufferメソッドは、レンダリングシステムRenders Everything You Ever Saw（REYES）のためにLucas film Studiosで開発された可視性検出メソッドです。
Aバッファは、透明度を許可するために深度バッファ方式を拡張します。 Aバッファの主要なデータ構造は、蓄積バッファです。
Aバッファの各位置には2つのフィールドがあります-
- 深度フィールド-正または負の実数を格納します
- 強度フィールド-表面強度情報またはポインター値を保存します
深さ> = 0の場合、その位置に格納される数値は、対応するピクセル領域に重なる単一の表面の深さです。 強度フィールドには、その時点での表面色のRGBコンポーネントとピクセルカバレッジの割合が格納されます。
深さ<0の場合、ピクセル強度への複数面の寄与を示します。 強度フィールドには、表面データのリンクリストへのポインターが格納されます。 Aバッファの表面バッファには以下が含まれます-
- RGB強度成分
- 不透明度パラメーター
- 深さ
- エリアカバレッジの割合
- 表面識別子
アルゴリズムは、深度バッファアルゴリズムと同様に進行します。 深度と不透明度の値は、ピクセルの最終的な色を決定するために使用されます。
深度ソート方法
深度ソート方法では、画像空間とオブジェクト空間の両方の操作を使用します。 深さソート方法は、2つの基本的な機能を実行します-
- 最初に、表面は深さの降順にソートされます。
- 第二に、表面は最大の深さの表面から順番にスキャン変換されます。
ポリゴンサーフェスのスキャン変換は、画像空間で実行されます。 隠面の問題を解決するためのこの方法は、多くの場合*ペインターのアルゴリズム*と呼ばれます。 次の図は、深度ソートの効果を示しています-
アルゴリズムは、深さでソートすることから始まります。 たとえば、ポリゴンの最初の「深度」推定値は、ポリゴンの頂点の最も近いz値であると見なされます。
リストの最後にあるポリゴンPを見てみましょう。 Z範囲がPに重なるすべてのポリゴンQを考えます。 Pを描く前に、次のテストを行います。 次のテストのいずれかが陽性の場合、Qの前にPを描画できると仮定できます。
- X範囲は重複していませんか？
- y範囲は重複していませんか？
- Pは視点から見てQ平面の反対側に完全にありますか？
- Qは視点とP平面の完全に同じ側にありますか？
- ポリゴンの投影は重なりませんか？
すべてのテストが失敗した場合、もう一方のプレーンを使用してPまたはQを分割します。 新しいカットポリゴンが深度順に挿入され、プロセスが続行されます。 理論的には、この分割によりO（n ^ 2 ^）個のポリゴンが生成される可能性がありますが、実際にはポリゴンの数ははるかに少なくなります。
バイナリスペースパーティション（BSP）ツリー
可視性の計算には、バイナリ空間分割が使用されます。 BSPツリーを構築するには、ポリゴンから始めて、すべてのエッジにラベルを付ける必要があります。 一度に1つのエッジのみを処理し、各エッジを拡張して、プレーンを2つに分割します。 ツリーの最初のエッジをルートとして配置します。 内側か外側かに基づいて、後続のエッジを追加します。 すでにツリー内にあるエッジの拡張にまたがるエッジは2つに分割され、両方がツリーに追加されます。
- 上の図から、最初に A をルートとして取得します。
- 図（a）のすべてのノードのリストを作成します。
- 図* bに示すように、ルート A の前にあるすべてのノードをノード A の左側に配置し、ルート A の後ろにあるすべてのノードを右側に配置します。
- 最初にすべてのフロントノードを処理し、次にバックノードを処理します。
- 図（c）に示すように、最初にノード B を処理します。 ノード B の前には何もないので、NILを配置しました。 ただし、ノード B の後ろにノード C があるため、ノード C はノード B の右側に移動します。
- ノード D に対して同じプロセスを繰り返します。
