[發明專利]用于光線跟蹤的SAH-KD樹設計方法

有效

• 申請號: 201810061647.3
• 申請日: 2018-01-22
• 公開（公告）號: CN108171785B
• 公開（公告）日: 2021-12-10
• 發明（設計）人: 廖勝輝;李建鋒;譚耀華;夏佳志;郭璠;趙于前;鄒北驥
• 申請（專利權）人: 中南大學;吉首大學
• 主分類號: G06T15/06
• 分類號: G06T15/06;G06T17/00;G06T17/20;G06T1/20
• 代理公司: 深圳市中原力和專利商標事務所(普通合伙) 44289
• 代理人: 謝芝柏

本發明提供了一種用于光線跟蹤的SAH?KD樹設計方法，包括：步驟S1、在進行所述SAH?KD樹的構建之前，對節點中的當前根節點的所有三角面片進行預處理；步驟S2、按層次遞歸構建所述SAH?KD樹，生成當前所述節點的左、右子節點的有序包圍盒序列，并計算出當前層次每個所述節點的包圍盒的三個維度的表面積；步驟S3、求出當前節點需要劃分的維度，生成每一層所有所述節點的空間樹和候選劃分點，計算出每個所述候選劃分點對應的SAH值；步驟S4、選擇最小SAH值對應的所述候選劃分點作為當前節點的最優劃分點，并將該當前節點分成左、右兩個子節點。與相關技術相比，本發明提供的用于光線跟蹤的SAH?KD樹設計方法構建的SAH?KD樹性能好且效率高。

技術領域

本發明涉及數據處理技術領域，尤其涉及一種用于光線跟蹤的SAH-KD樹設計方法。

背景技術

K維樹(KD樹)是一類坐標軸對齊的平衡二叉樹，是常用于K維空間中進行空間劃分的數據結構，被當作加速結構廣泛的應用于圖形應用與查詢領域，比如光線跟蹤中三角面集合與光線的相交檢測和最近鄰查詢等。KD樹的遍歷成本在不同的應用領域有不同的計算方式，在光線跟蹤中需要計算出每條光線穿過的KD樹所有葉節點。為了達到高效遍歷，通常在構建時使用表面積啟發式劃分法(SAH)，通過最小化每個節點上三角面片與光線相交測試復雜度期望選擇劃分點。

相關技術中，為了快速高效的構造用于光線跟蹤的SAH-KD樹，一種方法是串行構造方法，最簡單的思路是對構造的SAH-KD樹的每個節點上所有劃分點進行全遍歷計算SAH值，其計算復雜度為O(N²)，由于計算復雜度較高，使得該方法無法應用于大場景；另一種是并行化構建方法，在上層大節點通過一個高性能線程進行計算，直到每個節點計算量足夠小，才將它們分配到多核系統中的構造思路，該方法雖然提高了SAH-KD樹的構建效率，但是算法遍歷時由于頂層的中值選擇效率有些退化，在超大型場景有不同程度的性能損失。

因此，實有必要提供一種新的用于光線跟蹤的SAH-KD樹設計方法解決上述問題。

發明內容

本發明需要解決的技術問題是提供性能好且效率高的用于光線跟蹤的SAH-KD樹設計方法。

為解決上述技術問題，本發明提供了一種用于光線跟蹤的SAH-KD樹設計方法，該方法包括如下步驟：

步驟S1、在進行所述SAH-KD樹的構建之前，對節點中的當前根節點的所有三角面片進行預處理，計算所述當前根節點的所有三角面片的包圍盒，將所述包圍盒在三個維度排列，形成有序包圍盒序列；

步驟S2、按層次遞歸構建所述SAH-KD樹，通過遍歷上層每個所述節點的所述有序包圍盒序列，生成當前所述節點的左、右子節點的有序包圍盒序列，并計算出當前層次每個所述節點的包圍盒的三個維度的表面積；

步驟S3、根據每個所述節點的所述包圍盒求出當前節點需要劃分的維度，生成每一層所有所述節點的空間樹和候選劃分點，利用所述空間樹并行計算出每個所述候選劃分點對應的SAH值；

步驟S4、對于當前層的每個所述節點，遍歷其包含的所述候選劃分點，選擇最小SAH值對應的所述候選劃分點作為當前節點的最優劃分點，并將該當前節點分成左、右兩個子節點。

優選的，步驟S1中，所述包圍盒為AABB包圍盒。

優選的，步驟S1中，將所述包圍盒在三個維度按升序排列。

優選的，步驟S2中，具體還包括：

迭代計算出每個節點在新的一層空間中的偏移D，使用AssignTri算法將所述左、右子節點包含的所述三角面片有序指派至所述左、右子節點中：