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

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

更新於 發佈於 閱讀時間約 2 分鐘

bvh(Bounding Volume Hierachies)簡介

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

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

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

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

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

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

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

raw-image

bvh建立後會大致像左圖

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

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



raw-image


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





raw-image


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





raw-image

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

raw-image






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

raw-image





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

avatar-img
s_SoNg的沙龍
4會員
11內容數
留言
avatar-img
留言分享你的想法!
s_SoNg的沙龍 的其他內容
在工作上遇到nodejs呼叫執行檔執行失敗問題,最後發現是由於nodejs專案本身有用nssm包成服務,在服務環境的nodejs呼叫的執行檔也執行在服務中,造成程式不會跳出視窗而導致失敗。
準備專案 這邊首先準備一個新的專案,可以參考react官網,完成後參考README.md輸入npm run dev就可以啟動並在瀏覽器看到畫面 準備nssm工具 在google上搜nssm,第一個項目點進去後,找到並下載穩定版,附上下載鏈接 壓縮檔下載完畢後,解壓縮到喜歡的地方,然後進入資料
如果有個算法是2秒以上很耗時的長任務,希望在執行長任務前後修改state渲染loading畫面,可能會難以達到預期效果,會看到loading畫面一閃而過。 把setState改非同步的方法...
4/5React await setStat
在工作上遇到nodejs呼叫執行檔執行失敗問題,最後發現是由於nodejs專案本身有用nssm包成服務,在服務環境的nodejs呼叫的執行檔也執行在服務中,造成程式不會跳出視窗而導致失敗。
準備專案 這邊首先準備一個新的專案,可以參考react官網,完成後參考README.md輸入npm run dev就可以啟動並在瀏覽器看到畫面 準備nssm工具 在google上搜nssm,第一個項目點進去後,找到並下載穩定版,附上下載鏈接 壓縮檔下載完畢後,解壓縮到喜歡的地方,然後進入資料
如果有個算法是2秒以上很耗時的長任務,希望在執行長任務前後修改state渲染loading畫面,可能會難以達到預期效果,會看到loading畫面一閃而過。 把setState改非同步的方法...
4/5React await setStat