發(fā)布時(shí)間：2021-07-11 16:12

　　針對(duì)復(fù)雜物體三維點(diǎn)集的建模問(wèn)題,提出一種基于凸包的最小體積的封閉有向包圍盒生成算法.對(duì)凸包和其最小體積有向包圍盒的關(guān)系進(jìn)行分析,總結(jié)了其4種邊面接觸類(lèi)型.通過(guò)枚舉凸包中邊的所有可能的組合,唯一確定包圍盒的最優(yōu)方向.實(shí)驗(yàn)證明,該算法可以快速生成符合模型體積特征的最小有向包圍盒,且擬合效果良好. 

【文章來(lái)源】：湖南大學(xué)學(xué)報(bào)(自然科學(xué)版). 2019,46(02)北大核心EICSCD

【文章頁(yè)數(shù)】：7 頁(yè)

【部分圖文】：

凸包及其OBB的四種不同邊緣接觸示例

（a）Sphere（10）（b）Sphere（100）（c）Sphere（500）圖6Sphere（n）數(shù)據(jù)集OBB示例Fig.6OBBsamplesforSphere（n）算法運(yùn)行時(shí)性能如圖7所示，其中X軸表示數(shù)據(jù)凸包中頂點(diǎn)的數(shù)量，Y軸表示計(jì)算OBB所對(duì)應(yīng)的時(shí)間，實(shí)際數(shù)據(jù)以細(xì)線(xiàn)繪制.結(jié)果表明，當(dāng)凸包頂點(diǎn)數(shù)在10000以下時(shí)，算法表現(xiàn)與預(yù)期的O（n3/2（logn）2）性能回歸曲線(xiàn)有較好的匹配.00.20.40.60.81.020151050time/sSphere（n）O（n3/2（logn）2）n圖7數(shù)據(jù)集Sphere（n）中計(jì)算最小體積OBB耗時(shí)Fig.7TimetakentocomputetheminimumvolumeOBBforSphere（n）由于包圍盒僅取決于模型的凸包，因此先將GAMMAGroup真實(shí)模型數(shù)據(jù)集中的模型進(jìn)行預(yù)處理.算法的擬合效果如圖8所示，可以看出對(duì)復(fù)雜物體模型，算法所計(jì)算出的包圍盒也可以進(jìn)行非常緊密的包圍.圖9中散點(diǎn)圖顯示了算法的性能情況，X軸為該對(duì)象的凸包上的點(diǎn)數(shù)，Y軸表示計(jì)算OBB所需的時(shí)間（s）.這個(gè)基準(zhǔn)測(cè)試的結(jié)果表明，大多數(shù)現(xiàn)實(shí)世界模型對(duì)象的計(jì)算性能與Sphere（n）的情況非常相似.如圖9所示在參與測(cè)試的2088個(gè)模型中，大部分模型表現(xiàn)接近最佳預(yù)期.圖8GAMMAGroup模型OBB示例Fig.8OBBsamplesforGAMMAGrouptime/s6543210500100015002000250030003500400045002001animalsarchitecgeometrymechanicalO（n3/2（logn）2）n圖9GAMMAGroup數(shù)據(jù)集下計(jì)算最小體積OBB耗時(shí)Fig.9TimetakentocomputetheminimumvolumeOBBforGAMMAGroup在GAMMAGroup數(shù)據(jù)庫(kù)的5個(gè)不同數(shù)據(jù)集中，分別對(duì)本文所提算法和文獻(xiàn)[10]中的HYBBRID算法進(jìn)行對(duì)比試驗(yàn)，包圍效果如圖10所示.因?yàn)槟Ｐ蛡�(gè)體形狀差異較大，所以選取算法在不同數(shù)據(jù)集中最優(yōu)情況，中位數(shù)情況和最差表現(xiàn)比較所得OBB包圍盒?

（a）Sphere（10）（b）Sphere（100）（c）Sphere（500）圖6Sphere（n）數(shù)據(jù)集OBB示例Fig.6OBBsamplesforSphere（n）算法運(yùn)行時(shí)性能如圖7所示，其中X軸表示數(shù)據(jù)凸包中頂點(diǎn)的數(shù)量，Y軸表示計(jì)算OBB所對(duì)應(yīng)的時(shí)間，實(shí)際數(shù)據(jù)以細(xì)線(xiàn)繪制.結(jié)果表明，當(dāng)凸包頂點(diǎn)數(shù)在10000以下時(shí)，算法表現(xiàn)與預(yù)期的O（n3/2（logn）2）性能回歸曲線(xiàn)有較好的匹配.00.20.40.60.81.020151050time/sSphere（n）O（n3/2（logn）2）n圖7數(shù)據(jù)集Sphere（n）中計(jì)算最小體積OBB耗時(shí)Fig.7TimetakentocomputetheminimumvolumeOBBforSphere（n）由于包圍盒僅取決于模型的凸包，因此先將GAMMAGroup真實(shí)模型數(shù)據(jù)集中的模型進(jìn)行預(yù)處理.算法的擬合效果如圖8所示，可以看出對(duì)復(fù)雜物體模型，算法所計(jì)算出的包圍盒也可以進(jìn)行非常緊密的包圍.圖9中散點(diǎn)圖顯示了算法的性能情況，X軸為該對(duì)象的凸包上的點(diǎn)數(shù)，Y軸表示計(jì)算OBB所需的時(shí)間（s）.這個(gè)基準(zhǔn)測(cè)試的結(jié)果表明，大多數(shù)現(xiàn)實(shí)世界模型對(duì)象的計(jì)算性能與Sphere（n）的情況非常相似.如圖9所示在參與測(cè)試的2088個(gè)模型中，大部分模型表現(xiàn)接近最佳預(yù)期.圖8GAMMAGroup模型OBB示例Fig.8OBBsamplesforGAMMAGrouptime/s6543210500100015002000250030003500400045002001animalsarchitecgeometrymechanicalO（n3/2（logn）2）n圖9GAMMAGroup數(shù)據(jù)集下計(jì)算最小體積OBB耗時(shí)Fig.9TimetakentocomputetheminimumvolumeOBBforGAMMAGroup在GAMMAGroup數(shù)據(jù)庫(kù)的5個(gè)不同數(shù)據(jù)集中，分別對(duì)本文所提算法和文獻(xiàn)[10]中的HYBBRID算法進(jìn)行對(duì)比試驗(yàn)，包圍效果如圖10所示.因?yàn)槟Ｐ蛡�(gè)體形狀差異較大，所以選取算法在不同數(shù)據(jù)集中最優(yōu)情況，中位數(shù)情況和最差表現(xiàn)比較所得OBB包圍盒?

【參考文獻(xiàn)】：
期刊論文
[1]一種散亂點(diǎn)云的均勻精簡(jiǎn)算法[J]. 李仁忠,楊曼,劉陽(yáng)陽(yáng),張緩緩.  光學(xué)學(xué)報(bào). 2017(07)
[2]基于改進(jìn)OBB包圍盒的碰撞檢測(cè)算法[J]. 史旭升,喬立紅,朱作為.  湖南大學(xué)學(xué)報(bào)(自然科學(xué)版). 2014(05)
[3]基于遺傳算法的散亂點(diǎn)云最小包圍盒求解[J]. 孫殿柱,史陽(yáng),劉華東,李延瑞.  北京航空航天大學(xué)學(xué)報(bào). 2013(08)
[4]基于非線(xiàn)性主成分分析的最小包圍盒計(jì)算方法[J]. 陳柏松,葉雪梅,安利.  計(jì)算機(jī)集成制造系統(tǒng). 2010(11)
[5]確定任意形狀物體最小包圍盒的一種方法[J]. 陳華.  工程圖學(xué)學(xué)報(bào). 2010(02)



本文編號(hào)：3278418