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

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

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

【部分圖文】：

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

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

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



本文編號：3278418