[發(fā)明專利]用于光線跟蹤的SAH-KD樹設(shè)計方法

有效

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

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

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

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

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

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

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

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

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

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

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