Three-mesh-bvh套件加速搜尋原理簡介

bvh（Bounding Volume Hierachies）簡介

一種樹狀結構，會為模型建立很多層由大到小的包圍框。常用來加速尋找符合條件的網格，可快速判斷是否與另一個模型相交、快速找最近點等。

直接判斷兩個模型是否相交

直接判斷兩個模型是否相交，可以遍歷其中一個模型所有頂點，檢查是否有點在另一個模型內部。

檢查某個點是否與另一個模型相交，可以以該點為起點，朝任意方向發射射線，判斷第一個射中的是否為另一個模型的背面。

射線偵測比較耗時，此方法需為模型每個點做射線偵測，Three-mesh-bvh套件可以過濾掉大部分點，原理如下：

Three-mesh-bvh判斷兩個模型是否相交

Three-mesh-bvh套件會為模型建立bvh樹，由模型整個包圍框逐漸細分，直到包圍框只包含幾個三角形。

bvh建立後會大致像左圖

橘色為整個模型包圍框，藍色為橘色的細分，綠色為藍色的細分，紅色為綠色的細分

由於紅色只包圍了幾個三角形，接著細分對加速搜尋效果不大，所以不繼續細分

例如要確認是否與紫色圓圈是否與黑色模型相交，會先判斷是否與最外面橘色框相交

再判斷與哪個藍框相交，排除未相交的，細分有相交的藍框

再判斷與哪個綠框相交，排除未相交的，細分有相交的綠框

再判斷與哪個紅框相交，排除未相交的，獲得相交的紅框裡所有三角形

最後，只需遍歷紅框內所有三角形，很快就能找到兩個藍色的點在紫色圓形裡面