Broad Phase 與 Narrow Phase 兩階段碰撞檢測

核心思維

先用便宜的方法剔掉一堆「絕對不可能」的候選，剩下少數再用昂貴的方法精確判斷。

看到「對 N 個東西做貴的計算」就要問：有沒有便宜的方法先剔掉大部分？

兩階段的分工

Broad phase（廣域階段）：快但粗略

只回答：「這個候選有沒有可能符合？」用簡化、寬鬆的判斷快速過濾。允許誤放幾個進下一階段，但不能漏放真的符合的。

Narrow phase（窄域階段）：慢但精確

對 broad phase 沒剔掉的少數候選做真正的判斷。

「寧可誤放，別漏放」的關鍵性質

Broad phase 必須是 conservative（保守的）：

真實狀況	Broad phase 判斷	結果
符合	「有可能」	✓ 進 narrow phase
符合	「不可能」	✗ 致命錯誤，永遠漏掉
不符合	「有可能」	沒關係，narrow phase 會修正
不符合	「不可能」	✓ 正確剔除

關鍵不對稱：誤放只是浪費一點時間，漏放是 bug。所以 broad phase 的判斷條件要刻意放寬。

為什麼有效

成本由「最常發生的情況」主導。大量候選的場景中，絕大多數其實不符合 — 對這些跑昂貴的精算就是純浪費。

• Broad phase 對「絕大多數不符合」的情況極便宜
• Narrow phase 只跑在「少數可能符合」的情況上
• 平均成本趨近 broad phase 的成本

候選越多、narrow phase 越貴，效益越大。

它是個思維框架，不只是碰撞檢測

這個「便宜剔除 → 昂貴精算」的兩階段思路，遍及各領域：

領域	Broad phase	Narrow phase
命中測試	包圍盒	精確幾何判斷
物理引擎	空間切分	形狀對形狀碰撞
3D 渲染	視錐剔除、遮擋剔除	像素深度測試
資料庫查詢	索引	行內 WHERE 條件
全文搜尋	倒排索引	相關性評分
程式碼搜尋	檔名/路徑過濾	內容 grep
履歷篩選	關鍵字過濾	人工面試

連 DB 索引本質上都是 broad phase — 用樹結構快速剔掉 99% 不符合的 row，剩下才掃。

何時不該用

候選數量少、或精算本來就便宜時，直接做就好。Broad phase 自己也有成本（維護、更新），少量候選時得不償失。

「premature optimization is the root of all evil」適用 — 先寫直接的，profile 出來精算階段真的是瓶頸再加 broad phase。

進階：分層

候選極大時，broad phase 自身的 O(n) 也會痛。這時 broad phase 要再加速 — 階層式包圍、空間索引、樹結構，把 broad phase 從 O(n) 降到 O(log n) 或 O(1)。

本質上是同一招的遞迴應用：對 broad phase 的候選清單，再做一次 broad phase。

設計時的問句

遇到「處理大量候選」的問題時自問：

1. 精算的成本是什麼？候選數乘上去會痛嗎？
2. 有沒有一個「便宜很多、但會誤放」的判斷？
3. 這個便宜判斷能保證 conservative 嗎？（不會漏放真的符合的）
4. 預期誤放率多少？剔除率夠不夠值得？

四題都過 → 加 broad phase。