[發明專利]一種規則柵格的相交加速方法、裝置及計算機存儲介質

在審

• 申請號: 202010048753.5
• 申請日: 2020-01-16
• 公開（公告）號: CN111243073A
• 公開（公告）日: 2020-06-05
• 發明（設計）人: 李亮;張競丹;樊良輝
• 申請（專利權）人: 西安芯瞳半導體技術有限公司
• 主分類號: G06T15/00
• 分類號: G06T15/00;G06T15/06;G06T15/50
• 代理公司: 西安維英格知識產權代理事務所(普通合伙) 61253
• 代理人: 歸瑩;李斌棟

1.一種規則柵格的相交加速方法，其特征在于，所述方法包括：

判定當前光線的到達體元為空體元的情況下，根據設定的空體元分布狀態查詢所述當前光線的到達體元位置周圍的空體元分布信息；

基于所述當前光線的到達體元周圍的空體元分布信息將光線跳過所述當前光線的到達體元周圍的空體元，獲得新的到達體元位置；

根據所述新的到達體元位置判定所述新的到達體元是否為空體元。

2.根據權利要求1所述的方法，其特征在于，所述方法還包括：構建一用于場景信息搜索的樹形數據結構以表征所述場景內的體元分布狀態；其中，所述樹形數據結構的葉子結點對應于規則柵格中的每一個體元；所述樹形數據結構的根節點用于表征整個場景；所述樹形數據結構中非根節點且非葉子節點的中間節點被柵格位置相鄰的子節點所指向。

3.根據權利要求2所述的方法，其特征在于，所述樹形數據結構中的葉子節點均包含所述葉子結點對應的體元位置信息、所述葉子結點對應的體元中是否存在圖元的標記以及所述葉子結點在所述樹形數據結構中所指向的上一級節點的位置信息。

4.根據權利要求2所述的方法，其特征在于，所述樹形數據結構中的非根節點且非葉子節點的中間節點都被體元位置相鄰的孩子節點所指向；所述中間節點中所存儲的信息包括：所述中間節點的父節點的位置、標記所述中間節點是否為空的狀態標識以及所述中間節點最左下側的葉子節點位置；且當且僅當指向所述中間節點的所有孩子節點均為空時，所述中間節點的是否為空的狀態標識為空。

5.根據權利要求2至4任一項所述的方法，其特征在于，所述判定當前光線的到達體元為空體元的情況下，根據設定的空體元分布狀態查詢所述當前光線的到達體元位置周圍的空體元分布信息，包括：

根據所述樹形數據結構中的葉子結點判定所述當前光線到達體元是否為空；

相應于所述當前光線到達體元為空，由所述當前光線到達體元對應的葉子結點于所述樹形數據結構向上獲取所述當前光線到達體元對應的葉子結點的一級父節點；

根據所述樹形數據結構中的中間節點判定所述一級父節點是否為空；相應于所述一級父節點為空，則由所述一級父節點于所述樹形數據結構向上獲取所述當前光線到達體元對應的葉子結點的二級父節點，直至獲取到的K級父節點滿足K級父節點為空且K+1級父節點不為空，則所述當前光線的到達體元位置周圍的空體元包括指向所述K級父節點的所有體元。

6.根據權利要求5所述的方法，其特征在于，所述基于所述當前光線的到達體元周圍的空體元分布信息將光線跳過所述當前光線的到達體元周圍的空體元，獲得新的到達體元位置，包括：

根據當前光線的到達體元的位置以及K級父節點的最左下側的葉子節點位置，通過設定的加速空體元遍歷算法確定跳過K級父節點對應的子樹之后的新的到達體元位置以及經典的規則柵格相交加速方案中用于遞歸疊加的判斷比較量。

7.一種規則柵格的相交加速裝置，其特征在于，所述裝置包括：判定部分、查詢部分、計算部分；其中，

所述判定部分，經配置為判定當前光線的到達體元是否為空體元；以及當所述當前光線的到達體元為空體元時，將所述當前光線的到達體元位置傳輸至所述查詢部分；

所述查詢部分，經配置為：根據設定的空體元分布狀態查詢所述當前光線的到達體元位置周圍的空體元分布信息；以及，將所述當前光線的到達體元位置周圍的空體元分布信息傳輸至所屬計算部分；

所述計算部分，經配置為基于所述當前光線的到達體元周圍的空體元分布信息將光線跳過所述當前光線的到達體元周圍的空體元，獲得新的到達體元位置；以及將所述新的到達體元位置傳輸至所述判定部分進行判定。