ゲームのスコープと視線の効果的な計算

戦略的なゲームでは、通常、プレイヤーが戦略を熟考して次の動きを行えるように、NPCの範囲を知る必要があります。 マップ上の多数のNPCでゲームの速度を浪費しない合理的なモデルの数学と実装を検討します。 完成したインタラクティブデモモデルをご覧になりたい場合は、 こちらからブラウザで直接プレイしてください！ デモのスクリーンショットは次のとおりです。



観察者の視界のパラメータ（視界の方向、視界の距離、視野の角度）があるため、観察者が見える領域を見つける必要があります。 視野（FoV）を定義します。 障害物がない場合は、2つの面（半径）とそれらを結ぶ円弧で構成される円の扇形になります（図1を参照）。 さらに、世界に特定のポイントがあるため、それが観測者に見えるかどうか、つまり、 特定のポイントの見通し（LOS）要求を処理する必要があります。 これらの操作は両方とも、リアルタイムレンダリングで使用するのに十分効率的に実行できます。


図 1

観測者の位置は赤い点で表され、矢印は視界の方向を示し、 rは視程の距離、 θは視野の半分の角度です。

1入力

• 世界の境界線を含むポリゴンのセット。
• FoVオプション
  
  • オブザーバーの位置
  • ビューの方向、 V
  • 画角2θ<180°
  • 可視距離、 r

注：ここおよび以下では、小文字はスカラー値を示し、大文字はベクトルです。

1.1ポリゴンとエッジ

2Dで世界を記述する場合、建物は自然にポリゴンに分割されるため、アルゴリズムへの入力になります。 ただし、技術的には、視野は壁によって制限されています。 ポリゴンのエッジ。 さらに、ポリゴンのエッジを操作すると、交差点をチェックするときに主にジオメトリプリミティブを扱うため、詳細と制御が向上します。 したがって、ほとんどの場合、アルゴリズムはエッジで直接機能し、高レベルの抽象化（ポリゴン）には適用されません。

2基本アルゴリズム

頭に浮かぶ最初の興味深いアイデアは、ポリゴンの輪郭で可視性セクターをトリミングすることです。 ただし、可視性を検討しているため、輪郭に沿ってトリミングすることでこの問題を解決しようとしてもうまくいかず、最終結果は不正確になります。 トリミングは2つの領域の交点のみを切断するため、これは理解できます。また、可視性のために、交点だけでなく、放射状の原理に従ってその背後のすべてを切断する必要があります。 図 図2は、トリミングの結果（左）と、そのような構成で予想される結果（右）を示しています。


図 2

現実の世界では、光線が自由に目に入ると物体が見えます。 直観的に、可視性は逆演算、つまり 目から世界へと輝いています。 光源の場合、光線はすべての方向に放出されます。 実際の実装では、レイは所定の間隔で放射状に放射されます。たとえば、5°ごとに1つのビーム、円全体で72のレイです。 ビームは、エッジでブロックされるまで移動する必要があります。 360°を通る光線の放射と2Dの光源で照らされた領域の決定は、解決された問題です[1]。 この方法の精度は、放出される光線の間隔に依存します。 間隔を短くすると、ビーム密度が大きくなります。


図 3

つまり、光線の放出は、光線と線分との交差のチェックです。 m個のセグメントを持つ特定のレイに対して、 m個のチェックが実行され、それをブロックするレイに最も近いエッジが決定されます。 したがって、 mエッジでn光線を放射する光線追跡アルゴリズムでは、 n×mチェックを実行する必要があります。 ただし、多くの光源が存在する巨大な世界では、光線と線分（エッジ）の交差をチェックするリソース強度がどれほど小さくても、このアプローチはコストがかかりすぎる可能性があります。

レイブロッキングエッジをブロッキングエッジと呼びましょう。 図 3それらは赤で強調表示されています。 ビームがブロッキングエッジを横切るポイントは、ヒットポイントと呼ばれます。 すべてのヒットポイントを見つけた後、それらを循環的に接続する必要があります。 すべてのヒットポイントは角度で並べられ、光源で照らされる領域を決定するために線で接続されます。 結果は、不正な閉ループになります。 この方法で交差点を接続すると、多角形の一部の角または部分が切り取られるため、照明領域が不正確または精度が低下することに注意してください。 光線の放出間隔を短くすることで改善できます。 間隔が小さいほど、光線が多くなり、カバレッジが向上します。 結果は改善されますが、生産性が低下します。

照明領域を決定するこの問題を使用して、問題を解決するために使用する主なアプローチであるレイキャスティング法を検討しました。 光線は、障害物と交差するまですべての方向で光源から発せられることに注意してください。 制限がないため、視界の角度と距離が制限されている問題よりも問題が簡単になります。 この理由については、セクション3で説明します。

2.1最適化

すべての方向に（一定の間隔で）光線を放出する代わりに、タスクは通常、エッジの端が位置する方向にのみ光線を放出することにより最適化されます。 これにより、必要な交差チェックの数が大幅に削減されます。 上記のnの値は小さくなるはずです。 この方法のもう1つの利点は、精度が高いことです。定義されたスコープの正確さのために、選択した間隔に依存しなくなりました。


図 4

これらのエッジの端を呼び出して、角のポイントとして光線の放射角度を与えます。 この名前は冗長で無意味なように見えるかもしれませんが、後で便利になります。 コーナーポイントは、可視光線が放射されるポイントです。 図 4つのコーナーポイントは、赤、青、黒でマークされています。 これらすべてのポイントで光線が放出されます。 ビームに最も近いポイントは、赤でマークされたヒットポイントに変換されます。 光線が届かないポイントは黒でマークされます。 これらの光線はより近いエッジと交差し、青でマークされたヒットポイントを作成します。

2.2角度のないビジョン

リブの端でのみ光線を放射するのが適していますが、わずかな欠陥があります。 図の注意 4光線はポリゴンのコーナーに放出され、角度を作成するエッジの1つと交差し、移動しません。 ただし、場合によっては、可視性が角を越えている必要があります。 この問題を解決するスマートなアプローチは、インタラクティブな記事[2]に示されています。

アイデアは、プライマリレイ（リブの端のレイ）を2つの補助的なレイに分割し、時計回りと反時計回りにイオタ角で偏向させることです。 視界が角の周りに広がる場合、これらの補助光線の1つが角を通過するため、背後の視界が決まります。 このアプローチの欠点は、1つのビームではなく、コーナーポイントごとに3つを放射する必要があることです。これは、速度に3倍以上影響します。 処理する必要のあるコーナーポイントの数を最小限に抑えると便利です。


図 5

補助光線はオレンジ色で強調表示されます。 逸脱の角度（オレンジと黒の光線の間）は明確にするために意図的に誇張されていますが、もっと小さく、たとえば0.5度にする必要があります。

簡単な最適化は、角度を形成する両方のエッジが表示されるかどうか、または一方が他方によって隠されるかどうかを判断することです。 両方が表示されている場合、補助光線は不要です。これは、可視性がそれ以上広がることができないためです。 図 4三角形の頂点は可視角です。可視性はこれ以上広がることができないため、ここでは補助光線は必要ありません。 補助光線は、2つのエッジの一方が観測者から隠されている場合にのみ必要です。 両方のエッジを非表示にすることはできません。ポリゴンの各コーナーを別々に見るためです-2つのエッジとそれらが接続するポイント（図6、黒い矢印と青い点を参照）。 エッジの1つが隠れていても、2つの補助光線の放出は冗長です。 1つだけが簡単に角を曲がるので、1つを避けることができます。 図 5、プライマリを時計回りに回転させることによって作成される補助ビームは冗長です。


図 6

エッジの一方が他方をブロックしているかどうかを判断するには、分割軸定理を使用できます。 両方のエッジのベクトルを一次光線に垂直なベクトルに投影すると、エッジの一方が他方をブロックしている場合、異なる兆候が得られます。 また、最初のrib骨の投影の符号に応じて、2つの補助光線のどちらが必要かを調べることができます。 図 図6は、上部に3つの可能性のある状況を、下に投影結果を示しています。 黒い点は、一次光線が放射される観察者の位置を示します（赤）。 エッジベクトル（黒）は、垂直なプライマリベクトル（緑）に投影されます。 補助光線が不要な場合、両方の投影は負の値を与えます。これは、両方のエッジベクトルが垂線の負の半空間にあるためです。 補助光線（オレンジ）が必要な他の2つの場合、投影のサインはベクトルのサインと異なります。 長いエッジのベクトルの符号が負の場合、時計回りに回転した補助光線で十分であり、正の場合、反時計回りに回転した光線で十分です。

3ブロックリブとコーナーポイント

検討中の問題では、視界は角度と距離によって制限されます。 これは興味深い状況に私たちを導きます。

• コーナーポイントは、エッジのすべての端ではなく、可視性セクターの領域にある端のみです。
  
  • これにより、放出される光線の量が少なくとも半分になります。 nはさらに小さくなりました。
  • これを利用するには、コーナーポイントをエッジの端から分離する努力が必要です。 これに使用する手法は、コンパートメント自体にあまり時間がかからないように十分に高速でなければなりません。
  
  
• さらに、ほとんどのエッジは潜在的にブロックされません。 私たちにとっては、セクターに含まれているか、それによって遮断されているものだけが重要です。
  
  • これにより、必要な交差チェックの数が減ります。 mの値は減少するはずです。
  • この目的のために、不要なエッジを切り取るための簡単なアルゴリズムも考えるべきです。

セクション2で説明した基本アルゴリズムとの主な違いは、エッジのエッジセットに含まれないコーナーポイントが存在する可能性があることです。 より多くのコーナーポイントを識別する必要がある場合があります。 図の構成を参照してください。 7と8。エッジの端は、可視性のセクターの外側にあるため、コーナーポイントとしては役に立ちません。 スコープの正しい定義に必要なすべてのコーナーポイント（黒、青、赤でマーク）は、エッジの端と一致しません。 それらのそれぞれが必要であり、それらのいずれかにビームを放射することは不可能であるため、スコープの不正確な定義につながります。 それらはどのように異なり、どのように定義するのですか？

視野は画角によって制限されるため、2つのコーナーポイントが必要であり、エッジの存在に関係なく確実に撮影する必要があります。 それらは、セクターの端にある極端なポイントです。 光線が放射され、衝撃点が決定されます。 図 図7は、これらの暗黙のコーナーポイントの1つを黒で示しています。セクターの右端のポイントのために発生したコーナーポイントです。 そこに放出されたビームはエッジでブロックされ、青い点が現れます。 左rib骨のコーナーポイントで放出される別の光線は、妨げられることなく通過します。 したがって、ヒットポイントはコーナーポイント自体になり、青で強調表示されます。 そのため、青い点は簡単に判別でき、チェックする必要はありません。 それらの位置は一定であり、可視性セクターの位置と方向に依存します。

アークとセクターのエッジの交点にある赤いコーナーポイント（ビームが何にも遮られていないためにヒットポイントになっている）を考慮してください。 もう1つの交差チェックが必要です。アークとラインセグメントの交差をチェックします。 これらのコーナーポイントは、エッジがセクターアークを横切るときに必要です。


図 7

光線は矢印のポイントで示され、エッジには終点があります。


図 8

これを念頭に置いて、コーナーポイントの発生のケースをリストします。

• 目の前の端点
• エッジが交差するセクターの円弧上の任意のポイント

さらに、セクター内に完全または部分的に配置されたリブは、潜在的なブロッキングエッジです。

ここで問題は、多くのコーナーポイント（新しいものを検索し、不要なエンドポイントを破棄する）と多くの潜在的なブロッキングエッジ（非ブロッキングエッジを切り取る）を取得するタスクになります。 このタスクは迅速に完了する必要があります。結果として処理サイクルに負荷がかからないように、できるだけ早く不正な要素を破棄します。 目標は、 n （放出される光線の数=コーナーポイントの数）とm （光線との交差をチェックするためのセグメントの数=潜在的にブロックするエッジの数）の値を減らすことで、FoVを決定するための迅速なアルゴリズムを提供します。

3.1クリッピング

[3]では、理想的なクリッピングアルゴリズム（実際にはリソース集約型で、浮動小数点数の精度の問題により複雑になります）は多くの可視ポイントのみを残し、十分なアルゴリズムは不可視のほとんどを破棄し、正確に可視で潜在的に可視のままにします。 潜在的に見えるポイントを破棄するとき、それは保守的です。 言い換えれば、リブが視界を妨げないことを完全に確信できない場合、彼はそれを落とさない。

3.1.1早期の些細な拒絶の段階

不適切なエンドポイントとエッジを破棄する最も簡単なアイデアは、セクター内のエッジのエンドポイントのみをチェックすることです。 これはコーナーポイントには適していますが、エッジのブロックには十分ではありません。エッジの端点がセクター内にない構成では機能しませんが、エッジは可視性をブロックします（図7および8を参照）。 より詳細な分析に進む前に、エッジを破棄できる場合、エンドポイント検証は完全にスキップできます。

3.1.1.1境界円とエッジの交差

円の中心に最も近いセグメントの点が円の内側にある場合、それはその中にあるか、または交差します。 このアプローチは、[4]で詳細に説明されています。 エッジとセクターの境界円の助けを借りて、境界円に含まれていないすべてのエッジを破棄できます。 この段階の後、円の中にないすべてのエッジは考慮されません。 これは交点を検索するためのチェックではなく、単に余分なエッジを切り取るため、結果はブール形式で表示され、すぐに判明します。 このチェックを実装するには、2つのベクトル減算操作（ベクトルを与える）とスカラー積のみが必要です。1つは（投影により）最も近い点を見つけ、もう1つはそれから円の中心までの距離の2乗を計算します。

このチェックの結果は図に示されています。 9.可視性セクターの境界円は点線で示されています。 各エッジの青い点は、円の中心に最も近い点を示しています。 緑色のリブは、さらに計算するために保存されます。 ライラックも持続しますが、偽陽性です。 赤は捨てられます。 境界円に接触するエッジも、可視性を妨げないため、破棄されます。


図 9

偽陽性の結果を積極的に拒否するには、円ではなくセクター内の最も近い点をチェックするというアイデアが魅力的です。 ただし、肯定的な結果を拒否するため、このようなチェックは正しくありません。 図 9ライラックドットと共に、緑のエッジも破棄され、その最も近いポイントはセクター外にあります。

3.1.1.2セクターに関連するポイント

ポイントとセクターがあれば、すぐに判断できます

1. オブザーバーの背後にあるポイント
2. オブザーバーの前で
   
   1. 見えない
   2. 視距離内と
      
      1. セクター内
      2. セクターの外側、ただし境界の半円の内側

スカラー積とベクトル積のみを使用します。 ベクトル積は2Dで定義されていないため、z = 0を使用してベクトルを3Dに転送します。ベクトル積の結果はベクトルですが、z = 0であるため、xとyに関連する要素は0になり、zのみが非ゼロになります（ベクトルが平行でない場合）。 したがって、このベクトル積からスカラー結果を取得します。 [5]の2Dのベクトル積のさまざまな定義を参照してください。

円の中心から点までのベクトルを（U）、セクターのエッジのベクトル-E1、E2とします。 すでに見通し線Vがあります。

1. U⋅V <0の場合、ポイントは観測者の背後にあります。
2. それ以外の場合、U⋅U =‖U‖2> r ^2の場合、ポイントは見えなくなります。
3. それ以外の場合、符号（E1×U）=符号（U×E2）の場合、ポイントはセクター内にあります。
4. , .

説明が必要な2つの最適化を使用しました。 長さを見つけることはsqrt ( )を使用することを意味するため、長さを比較する代わりに長さの2乗（2）を比較します。 これを回避し、コンピューターグラフィックスの操作に慣れている最適化を適用します（[7]）。 ポイントがセクター内にあるかどうかを確認するには（3）、セクターの最初のエッジの反対側の角度を見つけて、許容視野角（2θ）内にあるかどうかを確認します。 ただし、このためには、三角関数acos ()を使用する必要があります。これは、算術演算のみが使用されるベクトル積のペアを計算するよりも高価になる可能性があります。

エッジが前のテストを「生き残った」場合、エンドポイントをチェックして、それらがどこにあるかを判断します。 図 図10は、現在の状況を示しています：観測者の後ろの灰色の点（1）、セクターの外側の赤い点（2）、セクターの内側の緑色の端点（3）、および境界の半円の内側であるがセクターの外側の紫色の端点（4）。


図 10

結果からコーナーポイントとブロックエッジを決定できます。

1. 両端が観測者の背後にある場合（1）、それらは可視性を妨げません。 それらを破棄し、処理しなくなりました。
2. 両端がセクター内にある場合（3）、両方をコーナーポイントとして、エッジをブロックとしてマークします。 さらなる処理を停止します。
3. それらの1つがセクター（3）内にあり、もう1つが（1）、（2）、（4）でない場合、1つをコーナーポイントとして、エッジをブロックとしてマークします。 このエッジは扇形の弧を横切り、新しいコーナーポイントを作成できます。
4. 両方がセクターの外側にある場合-（2）、（4）-端点は角度ではありませんが、エッジはセクターの円弧と交差して、新しいコーナーポイントを作成できます。 エッジが円弧またはセクターのエッジを横切る場合、エッジがブロックしている可能性があります。

ケース3および4では、エッジ内に含まれるエンドポイントではないコーナーポイントを検出し、エッジによる可視性をブロックするために追加のチェックが必要です。 これにより、カットオフを狭める段階に進みます。

3.2狭小化の段階

この時点で、他の誤検知を取り除き、よりコストのかかるチェックを行って、光線放射性能を改善します。 アーチのエッジとアーチの交差、および/またはエッジとエッジの交差を確認できます。

ただし、セグメントとアークの交差のやや高価な検証を実行する前に（平方根と3つ以上の分岐操作を使用）、前の検証の結果を使用して、検証が必要であることを確認できます。 エッジがアークを横断する能力を持っている場合にのみ、検証が必要です。 両方の端点が境界円の内側にある場合、エッジは円を横断できません。 端の1つがオブザーバーの前にあり、もう1つが境界円の外側にある場合にのみ、エッジがセクターの円弧を横断できます（セクション3.1.1.2のケース2.1）。

表1. エッジの終点の可能な位置と状態

いや	終了	終了b	状態
1	内側	内部（2.2.1）	コーナーポイント：A、B•ブロック
2	内側	戻る（1）	コーナーポイント：A•ブロック
3	内側	半円内（2.2.2）	コーナーポイント：A•ブロック
4	内側	外（2.1）	コーナーポイント：A•ブロック•円弧を横断できます
5	後ろ	後ろ	破棄されました
6	後ろ	外で	アークを横断する場合があります•ブロックする場合があります
7	後ろ	半円で	ブロックすることがあります
8	半円で	半円で	ブロックすることがあります
9	半円で	外で	アークを横断する場合があります•ブロックする場合があります
10	外で	外で	アークを横断する場合があります•ブロックする場合があります

早期拒否の段階で、ポイント1、2、3、および5をすでに処理しており、それらを使用する必要はありません。 ポイント4では、追加のコーナーポイントが不要であることを確認するために、エッジと円弧の交差をチェックする必要があります。 初期の段階では、すでにその端点の1つをコーナーポイントとして、エッジをブロックとしてマークしています。 ポイント6〜10は、ナローイングの段階で最も興味深いものです。 ポイント6、9、および10では、コーナーポイントが交差点で発生するかどうかを知るために、エッジとアークの交差点を確認する必要があります。 その場合、エッジにブロッキングのマークを付ける必要があります。 これらのポイントがテストに合格しない場合、ポイント7および8にアタッチされます。コーナーポイントを持つことはできませんが、可視性をブロックするかどうかを知るために、エッジとエッジの交点のチェックに合格する必要があります。

3.2.1セクターのエッジとアークの交差

表1の項目4、6、9、および10では、セグメントとアークの交差の検証を使用して、エッジがセクターアークと交差するかどうかをチェックします[6]。 その場合、交差点をコーナーポイントとして、エッジをブロックとしてマークします。 それ以上の処理は必要ありません。 そうでない場合、エッジにコーナーポイントを含めることはできませんが、エッジは可視性をブロックするために次のテストに合格する必要があります。

本質的に、これは線と円の交点のチェックであり、その結果は2点です。 セグメントと円弧の両方にあるポイントは、交差ポイントと見なされます。 ここで、少し最適化を行うことができます。両方の交差点がオブザーバーの後ろにある場合、セグメントは可視性をブロックできず、コーナーポイントを持つため、エッジはそれ以上処理せずに破棄できます。


図 11

図 図11に示すように、灰色のエッジは、可視性を超えた一方の端点と観察者の後ろの他の端点でチェックされますが、両方の交差点は観察者の後ろにあります。 両方の点が半円になっている緑のエッジはチェックされません。 可視性の外側に1つの端点を持つ赤いエッジがチェックされますが、見つかった唯一の交差点（青）は円弧上にありません。 このエッジにはコーナーポイントを設定できませんが、次の段階（エッジとエッジの交差点のチェック）に進み、ブロッキングをチェックします。 適切な（赤）交点を持つ、境界円の外側または片方の端点を持つ他のすべてのエッジ（黒）はブロックとしてマークされ、交点はコーナーポイントとしてマークされます。表1

3.2.2リブとセクターのリブの交差

前のテストに一度も合格したことのないポイント7および8、および交差点を見つけられなかったテストに合格したポイント（6、9、および10）の場合、エッジにコーナーポイントは存在できません。 両方の端点はセクター内になく、円弧上に新しいコーナーポイントはありません。 ただし、このようなエッジは、ブロックすることも（図8を参照）、ブロックしないこともできるため（図10を参照、ライラックの端点を持つエッジ）、破棄できません。 2つのオプションがあります：安全にするためにブロックとしてマークするか、セクターのエッジとの交差をチェックすることを確認します。 最初のオプションを選択すると、可視性セクターとの各偽陽性の非交差に対して、各光線が潜在的なブロッキングエッジとの交差をチェックするため、光線の放射段階でセグメントとセグメントnの交差のチェックが行われます。 誤検知に対してn回支払う代わりに、 n + 2 （最悪の場合）を費やすのが最善のオプションです。 したがって、セクターの両方のエッジとの交差についてエッジをチェックします。 エッジがそれらの少なくとも1つと交差する場合、ブロッキングとしてマークします。


図 12

図のポイント6-10 12対応するエッジが2つあります。1つは正（緑）、もう1つは負（赤）です。 図から、このチェックは可視性と一致しないエッジをドロップする可能性が高いことが明らかです。

4光線放射

すべてのコーナーポイントとブロッキングエッジがあります。 光線を追跡する前に、角度でコーナーポイントを並べ替えて、インパクトポイントをエッジやアークに接続するときに、視野の最終形状が正しくなるようにする必要があります。 さらに、2つ以上のコーナーポイントと観察者の位置が同一直線上にある場合、複数の光線が一方向に放出されます。 重複するコーナーポイントは、不要な光線を避けるために破棄する必要があります。

並べ替えにはテクニックを使用できます。 セクション3.1.1.2で説明：ベクトル積を使用して、ポイントが可視性セクター内にあるかどうかを判別します。 重複したコーナーポイントは、ベクトル積を使用して簡単に再度処理できます。 各コーナーポイントの光線を放出する前に、前の光線とベクトル的に乗算され、結果がゼロの場合、ベクトルは線形依存（平行）であり、無視できることを意味します。

一次光線は、ソートされたコーナーポイントで放出されます。 ポイントがエッジの終点であり、交点ではないことがわかっている場合は、補助光線を放射する必要があります（詳細については、セクション2.2を参照）。 補助光線は、エッジの端点であるコーナーポイントでのみ放出され、交差ポイントでは放出されません。ポリゴンのコーナーになることはできないためです。 可視性はそれらを超えることはできません。

放出された光線ごとに、光線とそれに最も近いエッジの交点を見つけます。 ビームの衝突点になります。 このポイントが可視距離rの外側にある場合、ヒットポイントをビームに沿ったポイントと見なします。これは、観測者から距離rにあります。 つまり ヒットポイントから観察者までの距離がrと等しくなるまで、ヒットポイントを後方にドラッグします。 見つかった各ヒットポイントが円弧の境界上にあるかどうかを確認します。 これと前の点が円弧の境界上にある場合、それらを円弧で接続し、そうでなければ-セグメントで接続します。 ただし、このタスクを「盲目的に」実行すると、小さな問題が発生します。


図 13

図 13のヒットポイント（右から左に番号が付けられています）1と2は円弧上にあり、円弧で接続する必要があります。 ヒットポイント3と4についても同様です。ただし、アークと交差するエッジがあるため、ヒットポイント2と3は線で接続する必要があります。 ヒットポイント3を見つけて、それと前のヒットポイントが円弧上にあることを確認した場合、それらをアークで接続する前に、それらを接続する線がヒットポイント3がある最も近いエッジと平行であるかどうかを確認する必要があります。それらが平行である場合は、セグメントで接続します

5視線

オブザーバーの特定のパラメーターについて、ワールドXの特定のポイントがオブザーバーに見えるかどうかの質問に答えるには、視線のクエリが必要です （セクション1を参照）。 ブロッキングエッジとコーナーポイントを見つけたら、これは簡単です。 まず、セクション3.1.1.2に従ってXを分類します。 ポイントがセクター内にない場合、 falseを返しfalse 。 内部にある場合、ブロッキングエッジのいずれかが、Xをオブザーバーに接続することによって形成されたセグメントと交差するかどうかを確認します。 交差しない場合は、 trueを返しtrue 。これは、オブザーバーからオブジェクトへの視線または光線を妨げるものがないためです。 したがって、オブジェクトが表示されます。

6参照

1. 2D可視性 、アミットパテル
2. 視力と光 、ニッキーケース
3. §14.2カリングテクニック、 リアルタイムレンダリング 、第3版、トーマスアケニン-メラー、エリックヘインズ、ネイティホフマン
4. 線分から円への衝突/交差点の検出 、David Stygstra
5. §A.2.1、3 -Dコンピューターグラフィックス 、サミュエルR.バス
6. 2Dの線形および円形コンポーネントの交差 、デビッドエバリー
7. §2.2.5、 ゲームおよびインタラクティブアプリケーションに不可欠な数学 、第2版、James Van VerthおよびLars M. Bishop
8. グラフィックスとゲーム開発のための3D数学入門 、第2版、フレッチャーダンとイアンパーベリー
9. 3Dゲームプログラミングとコンピューターグラフィックスの数学 、第3版、エリックレンジェル