フラットランドの類推
エドウィン・アボットの『フラットランド』（1884）：二次元の平面に住む人々。彼らは長さと幅しか知覚できない。奥行き——彼らの上にある第三の次元——は不可視であり、知覚も利用も構築もできない。彼らの世界のジオメトリは、構造的に破棄された次元を含んでいる。
MOAD-0007 も同じように動作する。3D 空間内のオブジェクトは位置、回転、バウンディングボリュームという豊かなジオメトリ構造を持つ。線形走査はそれらを平坦なリストとして扱う。空間構造は存在するが、使用されず、破棄される。すべての交差判定はリスト全体を走査し、あたかもオブジェクトにジオメトリも位置もないかのように振る舞う。
Three.js の例
Three.js Raycaster.intersectObjects(): 3D空間内の位置と方向で定義されるレイ（光線）を与えると、そのレイと交差するすべてのオブジェクトを検出します。実装は、シーン内のN個のオブジェクトをすべて走査し、それぞれをレイとテストします。呼び出しごとにO(N)です。
ホバーイベントハンドラは、1秒間に60フレームで毎フレームintersectObjects()を呼び出します。N=100オブジェクトの場合：1秒あたり6,000回の交差テスト。N=10,000オブジェクトの場合：1秒あたり600,000回のテスト。コストは、実際にレイと交差するオブジェクト数ではなく、Nに比例します。
N=100の場合：目に見えません。60fpsでのフレーム予算（16.7ms）は、苦もなくこのコストを吸収します。
N=10,000の場合：支配的になります。1秒あたり600,000回の交差テストがメインスレッドを飽和させ、フレームレートが低下します。N=100で動作していたシーンは、Nが閾値を超えると静かに崩壊します。
リニアスキャンが捨てている構造
オブジェクトは空間内に位置を占めています。位置(1000, 0, 0)にあるオブジェクトは、位置(0, 0, 0)から方向(-1, 0, 0)を向いたレイとは交差できません。オブジェクトは逆方向に存在するからです。しかしリニアスキャンはそれでもテストします。
オブジェクトにはバウンディングボリューム（球体またはボックス）があります。オブジェクトのバウンディングボリュームと交差しないレイは、そのオブジェクト自体とも交差できません。しかしリニアスキャンは完全な交差テストを計算します。
ジオメトリは、どのオブジェクトをスキップすべきかをエンコードしています。リニアスキャンはそのジオメトリを無視します。これが「discard」です。
「構造の破棄」とは何か
Flatland のアナロジー：アボットの住人たちは奥行きを認識できなかった。Flatland Defect とは、データに実際に存在するがアルゴリズムに決して渡されない幾何学的構造を破棄してしまうことを指す。
ハッシュ集合が 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)。オブジェクトを位置によって整理するため、近接クエリは幾何学的に離れたオブジェクトをスキップできる。
| 質問 | 正しい構造 | 誤った構造 |
|---|---|---|
| オブジェクト X はこのセットに含まれているか？ | HashSet (O(1)) | リニアリスト (O(N)) |
| このレイと交差するオブジェクトはどれか？ | BVH/オクトリー/k-d 木 (O(log N)) | リニアスキャン または HashSet (O(N) または O(N)) |
MOAD-0001 & MOAD-0007: どちらも O(N) の操作をより高速なものに置き換えた。質問が異なるため、必要な構造も異なる。 [BLOCK_TYPE SECTION/STEP]
構築するタイミングとスキップするタイミング
[BLOCK_TYPE SECTION/STEP]BVH の構築コストは O(N log N)。クエリコストは O(log N + k)。ブレークイーブン点は、クエリ回数が構築回数を十分に上回り、クエリによる節約が構築コストを上回る場合。 [BLOCK_TYPE SECTION/STEP]
N=100 の場合：線形スキャンはマイクロ秒単位。BVH 構築はオーバーヘッドを追加する。BVH をスキップする。 [BLOCK_TYPE SECTION/STEP]
N=10,000 で 60Hz の場合：線形スキャンがフレーム予算を圧迫する。BVH クエリは線形スキャンの 1/1,000 のコスト。BVH を一度構築し、1秒間に 60 回クエリする。最初のフレームより前にブレークイーブンに達する。 [BLOCK_TYPE SECTION/STEP]
ルール：N * Q > N log N のとき構築する。ここで Q は再構築サイクルあたりのクエリ回数。インタラクティブな 3D シーンでは Q = 60/秒、N の閾値は数百オブジェクト程度。
3D シーンの診断と修正 [BLOCK_TYPE SECTION/STEP]
3D 可視化アプリケーションが 5,000 個のジオメトリオブジェクトを描画する。ホバーイベントは 1秒間に 60 回発生する。各ホバーイベントでハンドラは scene.intersectObjects(ray, objects) を呼び出し、5,000 個のオブジェクトすべてを反復してレイと交差判定する。フレームレートが 60fps から 8fps に低下した。
チームメイトの提案: 「すべてのオブジェクトを Set に入れて O(1) のルックアップにしよう。」