[發明專利]用于產生加速結構的方法和設備

有效

• 申請號: 201710794757.6
• 申請日: 2017-09-06
• 公開（公告）號: CN108022284B
• 公開（公告）日: 2023-06-02
• 發明（設計）人: 辛容三;李源宗
• 申請（專利權）人: 三星電子株式會社
• 主分類號: G06T15/06
• 分類號: G06T15/06
• 代理公司: 北京銘碩知識產權代理有限公司 11286
• 代理人: 張川緒;王兆賡

1.一種用于產生用于光線跟蹤的加速結構的方法，所述方法包括：

產生線性碼，線性碼表示包括在三維空間中的多個圖元中的每個圖元的位置；

根據產生的線性碼，布置所述多個圖元；

將布置的所述多個圖元順序地輸入到產生的包圍盒中，直到所有圖元被包括在包圍盒中；

每當布置的所述多個圖元中的每個圖元被輸入到包圍盒中時，確定包圍盒的大小；

將先前數量的圖元的包圍盒的大小與當前數量的圖元的包圍盒的大小進行比較；

基于比較結果，確定產生的包圍盒的大小的改變率；

基于布置的結果設置權重，其中，設置的步驟從布置的所述多個圖元的布置順序的中心減小權重；

基于設置的權重和產生的包圍盒的大小的改變率，選擇布置的所述多個圖元之一；

根據選擇的圖元，將布置的所述多個圖元分類到多個確定的包圍盒中，分類的步驟將布置的所述多個圖元分類到第一包圍盒和第二包圍盒中，第一包圍盒包括選擇的圖元和在選擇的圖元之前布置的至少一個圖元，第二包圍盒包括在選擇的圖元之后布置的至少一個圖元；

產生與第一包圍盒相應的第一節點和與第二包圍盒相應的第二節點；

將第一節點和第二節點添加為加速結構的子節點。

2.如權利要求1所述的方法，其中，確定的步驟包括：

將第一圖元的下一個被布置的第二圖元輸入到包括布置的所述多個圖元之中的第一圖元的包圍盒中；

確定包括第一圖元和第二圖元的包圍盒相對于包括第一圖元的包圍盒的增大率。

3.如權利要求1所述的方法，其中，選擇的步驟選擇布置的所述多個圖元之中的與產生的包圍盒的大小的最大的改變率相關聯的圖元。

4.如權利要求1所述的方法，其中，所述多個圖元中的每個圖元的位置基于三維空間中的所述多個圖元中的每個圖元的中心的坐標信息。

5.如權利要求1所述的方法，其中，線性碼包括莫頓碼。

6.如權利要求1所述的方法，其中，產生的包圍盒的大小的改變是產生的包圍盒的表面積的改變。

7.一種用于產生用于光線跟蹤的加速結構的設備，所述設備包括：

存儲器，存儲加速結構和關于包括在三維空間中的多個圖元中的每個圖元的位置的信息；

處理器，被配置為：根據線性碼布置所述多個圖元，線性碼基于關于所述多個圖元中的每個圖元的位置的信息；將布置的所述多個圖元順序地輸入到產生的包圍盒中，直到所有圖元被包括在包圍盒中；每當布置的所述多個圖元中的每個圖元被輸入到包圍盒中時，確定包圍盒的大小；將先前數量的圖元的包圍盒的大小與當前數量的圖元的包圍盒的大小進行比較；基于比較結果，確定產生的包圍盒的大小的改變率；基于布置的所述多個圖元的布置順序來設置權重，其中，設置的處理包括從布置的所述多個圖元的布置順序的中心減小權重；基于設置的權重和產生的包圍盒的大小的改變率，選擇布置的所述多個圖元之一；根據選擇的圖元，將布置的所述多個圖元分類到多個確定的包圍盒中，其中，分類的處理包括將布置的所述多個圖元分類到第一包圍盒和第二包圍盒中，第一包圍盒包括選擇的圖元和在選擇的圖元之前布置的至少一個圖元，第二包圍盒包括在選擇的圖元之后布置的至少一個圖元；產生與第一包圍盒相應的第一節點和與第二包圍盒相應的第二節點，并將第一節點和第二節點添加為加速結構的子節點。

8.如權利要求7所述的設備，其中，處理器：

將第一圖元的下一個被布置的第二圖元輸入到包括布置的所述多個圖元之中的第一圖元的包圍盒中；

確定包括第一圖元和第二圖元的包圍盒相對于包括第一圖元的包圍盒的增大率。

9.如權利要求7所述的設備，其中，處理器被配置為選擇布置的所述多個圖元之中的與產生的包圍盒的大小的最大的改變率相關聯的圖元。

10.如權利要求7所述的設備，其中，所述多個圖元中的每個圖元的位置基于三維空間中的所述多個圖元中的每個圖元的中心的坐標信息。