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
留言分享你的想法!
簡單明了易記-avatar-img
發文者
2024/10/15
Three-mesh-bvh shapecast函式提及了這篇文章,趕快過去看看吧!
avatar-img
s_SoNg的沙龍
4會員
12內容數
s_SoNg的沙龍的其他內容
2025/04/28
在工作上遇到nodejs呼叫執行檔執行失敗問題,最後發現是由於nodejs專案本身有用nssm包成服務,在服務環境的nodejs呼叫的執行檔也執行在服務中,造成程式不會跳出視窗而導致失敗。
Thumbnail
2025/04/28
在工作上遇到nodejs呼叫執行檔執行失敗問題,最後發現是由於nodejs專案本身有用nssm包成服務,在服務環境的nodejs呼叫的執行檔也執行在服務中,造成程式不會跳出視窗而導致失敗。
Thumbnail
2025/04/08
準備專案 這邊首先準備一個新的專案,可以參考react官網,完成後參考README.md輸入npm run dev就可以啟動並在瀏覽器看到畫面 準備nssm工具 在google上搜nssm,第一個項目點進去後,找到並下載穩定版,附上下載鏈接 壓縮檔下載完畢後,解壓縮到喜歡的地方,然後進入資料
Thumbnail
2025/04/08
準備專案 這邊首先準備一個新的專案,可以參考react官網,完成後參考README.md輸入npm run dev就可以啟動並在瀏覽器看到畫面 準備nssm工具 在google上搜nssm,第一個項目點進去後,找到並下載穩定版,附上下載鏈接 壓縮檔下載完畢後,解壓縮到喜歡的地方,然後進入資料
Thumbnail
2024/10/30
如果有個算法是2秒以上很耗時的長任務,希望在執行長任務前後修改state渲染loading畫面,可能會難以達到預期效果,會看到loading畫面一閃而過。 把setState改非同步的方法...
2024/10/30
如果有個算法是2秒以上很耗時的長任務,希望在執行長任務前後修改state渲染loading畫面,可能會難以達到預期效果,會看到loading畫面一閃而過。 把setState改非同步的方法...
看更多
你可能也想看
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
創作者營運專員/經理(Operations Specialist/Manager)將負責對平台成長及收入至關重要的 Partnership 夥伴創作者開發及營運。你將發揮對知識與內容變現、影響力變現的精準判斷力,找到你心中的潛力新星或有聲量的中大型創作者加入 vocus。
Thumbnail
定義 圖Graph: 由節點和邊所組成的一個網狀資料結構。 圖的表達方式Graph representation: 常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。 本文以adjacenct list作為示範。 節點Vertex: 節點
Thumbnail
定義 圖Graph: 由節點和邊所組成的一個網狀資料結構。 圖的表達方式Graph representation: 常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。 本文以adjacenct list作為示範。 節點Vertex: 節點
Thumbnail
給定一個輸入陣列,每一個tuple代表節點之間了從屬關係。 請從從屬關係重建整顆二元樹,並且返回整顆二元樹的根結點。
Thumbnail
給定一個輸入陣列,每一個tuple代表節點之間了從屬關係。 請從從屬關係重建整顆二元樹,並且返回整顆二元樹的根結點。
Thumbnail
這篇文章,會帶著大家複習以前學過的二元搜尋樹(Binary Search Tree)框架, 並且以二分搜尋樹的概念與定義為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 二元搜尋樹(Binary Search Tree)的定義
Thumbnail
這篇文章,會帶著大家複習以前學過的二元搜尋樹(Binary Search Tree)框架, 並且以二分搜尋樹的概念與定義為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 二元搜尋樹(Binary Search Tree)的定義
Thumbnail
這篇文章,會帶著大家複習以前學過的二分搜尋法(Binary Search)框架, 並且以二分搜尋法的概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個實用的演算法框架。 Binary search 二分搜尋法框架 用途: 在已經排序好的數列中尋找目標值。
Thumbnail
這篇文章,會帶著大家複習以前學過的二分搜尋法(Binary Search)框架, 並且以二分搜尋法的概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個實用的演算法框架。 Binary search 二分搜尋法框架 用途: 在已經排序好的數列中尋找目標值。
Thumbnail
題目敘述 題目會給定我們一顆二元搜索樹BST的根結點, 還有一個指定區間的上邊界R 和 下邊界L。 請問二元搜索樹中,所有落在指定區間內的節點元素值的總和是多少? 題目的原文敘述 測試範例 Example 1: Input: root = [10,5,15,3,7,null,18], l
Thumbnail
題目敘述 題目會給定我們一顆二元搜索樹BST的根結點, 還有一個指定區間的上邊界R 和 下邊界L。 請問二元搜索樹中,所有落在指定區間內的節點元素值的總和是多少? 題目的原文敘述 測試範例 Example 1: Input: root = [10,5,15,3,7,null,18], l
Thumbnail
題目會給定一顆二元樹的根結點,要求我們驗證這一顆樹是否為合法的二元搜索樹, 也就是所謂的Binary search tree, aka BST?
Thumbnail
題目會給定一顆二元樹的根結點,要求我們驗證這一顆樹是否為合法的二元搜索樹, 也就是所謂的Binary search tree, aka BST?
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News