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

有效

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

1.一種用于光線跟蹤的SAH-KD樹設計方法，其特征在于，該方法包括如下步驟：

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

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

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

其中，NT為新一層三角面片的總和；NL為左子節點的三角面片數，NR為右子節點的三角面片數，i為自然數；D為偏移；

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

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

其中，所述的用于光線跟蹤的SAH-KD樹設計方法為CPU/GPU混合編程的SAH-KD樹設計方法，利用GPU使用寬度優先搜索構建所述SAH-KD樹，所述CPU對每次結果進行同步。

2.根據權利要求1所述的用于光線跟蹤的SAH-KD樹設計方法，其特征在于，步驟S1中，所述包圍盒為AABB包圍盒。

3.根據權利要求1所述的用于光線跟蹤的SAH-KD樹設計方法，其特征在于，步驟S3中，選擇所述包圍盒最長的維度作為需要劃分的維度。