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

更新 發佈閱讀 2 分鐘

bvh(Bounding Volume Hierachies)簡介

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

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

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

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

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

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

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

vocus|新世代的創作平台

bvh建立後會大致像左圖

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

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



vocus|新世代的創作平台


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





vocus|新世代的創作平台


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





vocus|新世代的創作平台

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

vocus|新世代的創作平台






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

vocus|新世代的創作平台





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

留言
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
這是一場修復文化與重建精神的儀式,觀眾不需要完全看懂《遊林驚夢:巧遇Hagay》,但你能感受心與土地團聚的渴望,也不急著在此處釐清或定義什麼,但你的在場感受,就是一條線索,關於如何找著自己的路徑、自己的聲音。
Thumbnail
這是一場修復文化與重建精神的儀式,觀眾不需要完全看懂《遊林驚夢:巧遇Hagay》,但你能感受心與土地團聚的渴望,也不急著在此處釐清或定義什麼,但你的在場感受,就是一條線索,關於如何找著自己的路徑、自己的聲音。
Thumbnail
定義 圖Graph: 由節點和邊所組成的一個網狀資料結構。 圖的表達方式Graph representation: 常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。 本文以adjacenct list作為示範。 節點Vertex: 節點
Thumbnail
定義 圖Graph: 由節點和邊所組成的一個網狀資料結構。 圖的表達方式Graph representation: 常見的有相鄰串列adjacency list或相鄰矩陣adjacency matrix。 本文以adjacenct list作為示範。 節點Vertex: 節點
Thumbnail
5 月將於臺北表演藝術中心映演的「2026 北藝嚴選」《海妲・蓋柏樂》,由臺灣劇團「晃晃跨幅町」製作,本文將以從舞台符號、聲音與表演調度切入,討論海妲・蓋柏樂在父權社會結構下的困境,並結合榮格心理學與馮.法蘭茲對「阿尼姆斯」與「永恆少年」原型的分析,理解女人何以走向精神性的操控、毀滅與死亡。
Thumbnail
5 月將於臺北表演藝術中心映演的「2026 北藝嚴選」《海妲・蓋柏樂》,由臺灣劇團「晃晃跨幅町」製作,本文將以從舞台符號、聲音與表演調度切入,討論海妲・蓋柏樂在父權社會結構下的困境,並結合榮格心理學與馮.法蘭茲對「阿尼姆斯」與「永恆少年」原型的分析,理解女人何以走向精神性的操控、毀滅與死亡。
Thumbnail
給定一個輸入陣列,每一個tuple代表節點之間了從屬關係。 請從從屬關係重建整顆二元樹,並且返回整顆二元樹的根結點。
Thumbnail
給定一個輸入陣列,每一個tuple代表節點之間了從屬關係。 請從從屬關係重建整顆二元樹,並且返回整顆二元樹的根結點。
Thumbnail
本文分析導演巴里・柯斯基(Barrie Kosky)如何運用極簡的舞臺配置,將布萊希特(Bertolt Brecht)的「疏離效果」轉化為視覺奇觀與黑色幽默,探討《三便士歌劇》在當代劇場中的新詮釋,並藉由舞臺、燈光、服裝、音樂等多方面,分析該作如何在保留批判核心的同時,觸及觀眾的觀看位置與人性幽微。
Thumbnail
本文分析導演巴里・柯斯基(Barrie Kosky)如何運用極簡的舞臺配置,將布萊希特(Bertolt Brecht)的「疏離效果」轉化為視覺奇觀與黑色幽默,探討《三便士歌劇》在當代劇場中的新詮釋,並藉由舞臺、燈光、服裝、音樂等多方面,分析該作如何在保留批判核心的同時,觸及觀眾的觀看位置與人性幽微。
Thumbnail
題目會給定給我們一顆二元樹的根結點,要求我們輸出Level-order traversal的拜訪結果。 在這題,我們會複習並利用BFS模板,來實現逐層搜索演算法。
Thumbnail
題目會給定給我們一顆二元樹的根結點,要求我們輸出Level-order traversal的拜訪結果。 在這題,我們會複習並利用BFS模板,來實現逐層搜索演算法。
Thumbnail
背景:從冷門配角到市場主線,算力與電力被重新定價   小P從2008進入股市,每一個時期的投資亮點都不同,記得2009蘋果手機剛上市,當時蘋果只要在媒體上提到哪一間供應鏈,隔天股價就有驚人的表現,當時光學鏡頭非常熱門,因為手機第一次搭上鏡頭可以拍照,也造就傳統相機廠的殞落,如今手機已經全面普及,題
Thumbnail
背景:從冷門配角到市場主線,算力與電力被重新定價   小P從2008進入股市,每一個時期的投資亮點都不同,記得2009蘋果手機剛上市,當時蘋果只要在媒體上提到哪一間供應鏈,隔天股價就有驚人的表現,當時光學鏡頭非常熱門,因為手機第一次搭上鏡頭可以拍照,也造就傳統相機廠的殞落,如今手機已經全面普及,題
Thumbnail
題目會給定一顆二元樹的根結點,要求我們驗證這一顆樹是否為合法的二元搜索樹, 也就是所謂的Binary search tree, aka BST?
Thumbnail
題目會給定一顆二元樹的根結點,要求我們驗證這一顆樹是否為合法的二元搜索樹, 也就是所謂的Binary search tree, aka BST?
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)框架, 並且以二分搜尋法的概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個實用的演算法框架。 Binary search 二分搜尋法框架 用途: 在已經排序好的數列中尋找目標值。
Thumbnail
這篇文章,會帶著大家複習以前學過的二分搜尋法(Binary Search)框架, 並且以二分搜尋法的概念為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個實用的演算法框架。 Binary search 二分搜尋法框架 用途: 在已經排序好的數列中尋找目標值。
Thumbnail
這篇文章,會帶著大家複習以前學過的二元搜尋樹(Binary Search Tree)框架, 並且以二分搜尋樹的概念與定義為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 二元搜尋樹(Binary Search Tree)的定義
Thumbnail
這篇文章,會帶著大家複習以前學過的二元搜尋樹(Binary Search Tree)框架, 並且以二分搜尋樹的概念與定義為核心, 貫穿一些相關聯的題目,透過框架複現來幫助讀者理解這個演算法框架。 二元搜尋樹(Binary Search Tree)的定義
追蹤感興趣的內容從 Google News 追蹤更多 vocus 的最新精選內容追蹤 Google News