フラットランドの類推
Edwin AbbottのFlatland (1884): 2次元平面の住民たち。彼らは長さと幅を認識します。彼らにとって深さは、上に存在する3次元が不可視です。彼らはそれを見ることができず、それを使用することもできず、それを構築することもできません。彼らの世界のジオメトリは、彼らが構造的に捨てる次元を含んでいます。
MOAD-0007は同様に機能します。3D空間のオブジェクトは、位置、回転、境界ボリュームを持ちます：豊かなジオメトリ構造です。線形スキャンでは、それらを平べったいリストとして扱います。空間構造は存在しますが、使用されません、捨てられます。すべての交差テストでは、オブジェクトが位置を持っていないかのように、オブジェクトがジオメトリを持っていないかのように、リスト全体をスキャンします。
Three.jsの例
Three.js Raycaster.intersectObjects(): 与えられたレイ（3D空間の位置と方向）に対して、レイが交差するすべてのオブジェクトを見つける。実装：N個のシーンオブジェクトをすべて繰り返し、各オブジェクトをレイに対してテストします。O(N)ごとに呼び出します。
ホバーイベントハンドラは、1フレームごとに60フレーム毎秒でintersectObjects()を呼び出します。N=100のオブジェクトの場合：毎秒6,000の交差テスト。N=10,000のオブジェクトの場合：毎秒600,000のテスト。コストはNに比例し、レイが実際に交差するオブジェクトの数に比例しません。
N=100の場合：不可視。フレームバジェット（60fpsで16.7ms）はコストを無理なく吸収します。
N=10,000の場合：主流。600,000の交差テスト毎秒でメインスレッドを飽和します。フレームレートが低下します。N=100で動作したシーンは、閾値を超えるNの値で静かに崩壊します。
線形スキャンで捨てる構造
オブジェクトは空間の位置に存在します。位置（1000, 0, 0）にあるオブジェクトは、位置（0, 0, 0）から(-1, 0, 0)方向のレイと交差できない：オブジェクトは反対方向にある。線形スキャンではそれをチェックします。
オブジェクトは境界ボリュームを持っています：オブジェクトを完全に含む球体や箱。レイがオブジェクトの境界ボリュームと交差しない場合、オブジェクトと交差しないことを示します。線形スキャンでは、完全な交差テストを計算します。
ジオメトリは、オブジェクトをスキップするものです。線形スキャンはジオメトリを無視します。これが捨てられることです。
「ジオメトリ構造の捨て方」は何を意味するか
フラットランドの類推：アボットの住民は深度を認識できませんでした。フラットランドの欠陥は、データに存在する幾何学的構造を捨て、アルゴリズムにその構造は入らないようにします。
なぜハッシュセットでMOAD-0007を修正できないか
MOAD-0001修正：順序的なメンバーシップテストをハッシュセットに置き換えます。list.contains(x): O(N)。set.has(x): O(1)。メンバーシップの質問：「xはこのコレクションにありますか？」。空間幾何学は含まれていません。
MOAD-0007修正：線形空間スキャンを空間インデックス(BVH、オクテートリ、k-d木、R木)に置き換えます。空間質問：「この集合内のオブジェクトは、このレイ、球、フラストムに相交しますか？」。空間的近さが必要です。
ハッシュセットは、メンバーシップ：「この正確なオブジェクトは存在しますか？」を回答します。O(1)。しかし、近さ：「このレイの近くにあるオブジェクトは何ですか？」を回答できません。ハッシュセットは距離や空間的な拡大に関する概念がありません。ハッシュングは、線形スキャンと同じように幾何学を捨てます。
BVHは、空間的なクエリの範囲内にあるオブジェクトを回答します：「この空間クエリの範囲内にあるオブジェクトは何ですか？」。O(log N + k)。BVHは、オブジェクトを位置に組織化するため、近さのクエリは幾何学的に遠いオブジェクトをスキップします。
| 質問 | 正しい構造 | 間違った構造 |
|----------|------------------|-----------------|
| Is object X in this set? | HashSet (O(1)) | Linear list (O(N)) |
| Which objects intersect this ray? | BVH/octree/k-d tree (O(log N)) | Linear scan OR HashSet (O(N) or O(N)) |
MOAD-0001 & MOAD-0007: どちらも O(N) 操作が高速なものに置き換えられます。質問が異なるため、異なる構造が必要です。
ビルドするときとスキップするとき
BVHの構築は O(N log N)です。クエリは O(log N + k)です。ブレイクイーブンは、クエリがビルドを上回り、クエリの節約がビルドコストを上回るまでに十分なクエリ数が必要です。
N=100の場合: 線形スキャンはマイクロ秒で終了します。BVHのビルドはオーバーヘッドです。BVHを構築しません。
N=10,000で60Hz: 線形スキャンがフレーム予算を占めています。BVHクエリは線形スキャンに対して1/1,000のコストです。BVHを一度構築し、60回ごとにクエリを実行します。ブレイクイーブンは最初のフレーム前に達成されます。
ルール: N * Q > N log N です。インタラクティブ3Dシーンの場合: Q = 1秒間に60回、Nしきい値は何十個のオブジェクトでもうまくいく。
3Dシーンの診断と修正
3Dビジュアリゼーションアプリケーションは5,000個の幾何学的オブジェクトをレンダリングしています。ホバー ハンドラは1秒間に60回トリガーされます。ホバーイベントごとに、ハンドラはscene.intersectObjects(ray, objects)を呼び出します。この関数は、すべての5,000個のオブジェクトをループし、それぞれをレイに対してテストします。フレームレートは60fpsから8fpsに低下しました。
チームメイトからの提案:'すべてのオブジェクトをSetに格納し、O(1)の検索で簡単に検索できるようにしましょう。'