[發(fā)明專利]一種基于鏈表排序平衡二叉樹的層次包圍盒樹構(gòu)建方法在審
| 申請?zhí)枺?/td> | 201710717268.0 | 申請日： | 2017-08-21 |
| 公開（公告）號： | CN107689078A | 公開（公告）日： | 2018-02-13 |
| 發(fā)明（設(shè)計）人： | 葉秀芬;江帆;梅新奎;劉文智;王天;趙新華;崔建文;賈同超;宮垠;孫晶 | 申請（專利權(quán)）人： | 哈爾濱工程大學(xué) |
| 主分類號： | G06T17/00 | 分類號： | G06T17/00;G06T19/00 |
| 代理公司： | 暫無信息 | 代理人： | 暫無信息 |
| 地址： | 150001 黑龍江省哈爾濱市南崗區(qū)*** | 國省代碼： | 黑龍江;23 |
| 權(quán)利要求書： | 查看更多 | 說明書： | 查看更多 |
| 摘要： | |||
| 搜索關(guān)鍵詞： | 一種 基于 排序 平衡 二叉 層次 包圍 構(gòu)建 方法 | ||
1.一種基于鏈表排序平衡二叉樹的層次包圍盒樹構(gòu)建方法，其特征在于，具體的實現(xiàn)步驟包括：
(1)將所要建立包圍盒樹的物體按照合理精度劃分成基本幾何圖元，對每一個幾何圖元生成一個AABB層次包圍盒，將每個獨立的包圍盒看做為一棵二叉樹，每個二叉樹只有一個根節(jié)點，選擇一個物體或者地點作為參照物；
(2)創(chuàng)建一個鏈表存儲二叉樹：對步驟(1)中所建立所有只有根節(jié)點的二叉樹進(jìn)行遍歷，對鏈表中每個二叉樹對象增加一個屬性值，存儲該二叉樹到參照地點的長度；
(3)根據(jù)鏈表中每個二叉樹到參照地點的長度對鏈表進(jìn)行升序排列；
(4)遍歷鏈表，將鏈表中的二叉樹兩兩進(jìn)行合并，奇數(shù)元素作為合并后子樹的左孩子，偶數(shù)元素作為合并后子樹的右孩子，合并結(jié)果存入該鏈表；
(5)重復(fù)執(zhí)行步驟(3)至步驟(4)的過程，直到所有二叉樹合并為一個二叉樹為止。
2.根據(jù)權(quán)利要求1所述的一種基于鏈表排序平衡二叉樹的層次包圍盒樹構(gòu)建方法，其特征在于，所述的步驟(1)的具體實現(xiàn)步驟包括：
(1.1)將存于CPU端的模型三角片面數(shù)據(jù)復(fù)制到設(shè)備端全局存儲器中；
(1.2)CUDA多線程并行執(zhí)行為每個幾何圖元建立獨立包圍盒樹的核函數(shù)KernelA，并對每個幾何圖元生成包圍盒樹對象設(shè)置標(biāo)志屬性，初始化全部設(shè)置為false，表示這些節(jié)點還沒被合并。
3.根據(jù)權(quán)利要求1所述的一種基于鏈表排序平衡二叉樹的層次包圍盒樹構(gòu)建方法，其特征在于，所述的步驟(2)的實現(xiàn)方式為設(shè)定并執(zhí)行核函數(shù)KernelB，具體的實現(xiàn)方式為：CUDA多線程并行計算參照地點到每個包圍盒中心的長度，并將該長度值設(shè)置到包圍盒二叉樹對象中，依次將每個對象插入到鏈表中。
4.根據(jù)權(quán)利要求1所述的一種基于鏈表排序平衡二叉樹的層次包圍盒樹構(gòu)建方法，其特征在于，所述的步驟(3)的具體實現(xiàn)方式為：根據(jù)二叉樹包圍盒節(jié)點對象距離參照地點的長度對步驟(3)中形成的鏈表進(jìn)行排序，該過程不存在并行性，將在主機端執(zhí)行。
5.根據(jù)權(quán)利要求1所述的一種基于鏈表排序平衡二叉樹的層次包圍盒樹構(gòu)建方法，其特征在于，所述的步驟(4)的實現(xiàn)方式為并行執(zhí)行核函數(shù)KernelC，具體實現(xiàn)步驟包括：
(4.1)從鏈表中并行取出兩個包圍盒二叉樹節(jié)點，將取出的對象標(biāo)志值設(shè)置為true，表示這兩個節(jié)點已經(jīng)被合并過；
(4.2)將兩個二叉樹包圍盒進(jìn)行合并，之后重新計算大包圍盒的中心到參照地點的長度，并將長度設(shè)置到新生產(chǎn)的二叉樹包圍盒對象中，設(shè)置該對象的標(biāo)志值為false；
(4.3)將步驟(4.2)中的新生產(chǎn)的二叉樹包圍盒對象插入鏈表。
6.根據(jù)權(quán)利要求1所述的一種基于鏈表排序平衡二叉樹的層次包圍盒樹構(gòu)建方法，其特征在于，所述的步驟(5)的具體實現(xiàn)步驟包括：
(5.1)判斷鏈表中節(jié)點的數(shù)量是否為1；
(5.2)若節(jié)點的數(shù)量為1，說明AABB層次包圍盒樹的構(gòu)造完成，最后的節(jié)點就是整個包圍盒樹的根節(jié)點；
(5.3)否則重復(fù)執(zhí)行步驟(3)，重新構(gòu)建；
(5.4)不斷重復(fù)執(zhí)行步驟(3)至步驟(4)的過程，直到所有二叉樹合并為一個二叉樹為止。
7.根據(jù)權(quán)利要求1所述的一種基于鏈表排序平衡二叉樹的層次包圍盒樹構(gòu)建方法，其特征在于：步驟(1)中所述的基本幾何圖元使用的是三角片元。
8.根據(jù)權(quán)利要求1所述的一種基于鏈表排序平衡二叉樹的層次包圍盒樹構(gòu)建方法，其特征在于：所述的步驟(4)中使用平衡二叉樹方式構(gòu)造時，在合并生成新的二叉樹時不需要在每次合并后都重新計算距離，而是將鏈表中的元素兩兩合并后再計算距離。
9.根據(jù)權(quán)利要求1所述的一種基于鏈表排序平衡二叉樹的層次包圍盒樹構(gòu)建方法，其特征在于：所述的步驟(4)中如果鏈表中元素數(shù)量為偶數(shù)，則可以完全合并；如果元素數(shù)量為奇數(shù)，則保留最后一個元素，在下一輪合并時使用。
10.根據(jù)權(quán)利要求2所述的一種基于鏈表排序平衡二叉樹的層次包圍盒樹構(gòu)建方法，其特征在于：步驟(1.1)中所述的三角片面數(shù)據(jù)為三角形的三個頂點數(shù)據(jù)。
該專利技術(shù)資料僅供研究查看技術(shù)是否侵權(quán)等信息，商用須獲得專利權(quán)人授權(quán)。該專利全部權(quán)利屬于哈爾濱工程大學(xué)，未經(jīng)哈爾濱工程大學(xué)許可，擅自商用是侵權(quán)行為。如果您想購買此專利、獲得商業(yè)授權(quán)和技術(shù)合作，請聯(lián)系【客服】
本文鏈接：http://www.szxzyx.cn/pat/books/201710717268.0/1.html，轉(zhuǎn)載請聲明來源鉆瓜專利網(wǎng)。
