基于凸包的最小体积有向包围盒生成算法
发布时间：2021-07-11 16:12
针对复杂物体三维点集的建模问题,提出一种基于凸包的最小体积的封闭有向包围盒生成算法.对凸包和其最小体积有向包围盒的关系进行分析,总结了其4种边面接触类型.通过枚举凸包中边的所有可能的组合,唯一确定包围盒的最优方向.实验证明,该算法可以快速生成符合模型体积特征的最小有向包围盒,且拟合效果良好.
【文章来源】：湖南大学学报(自然科学版). 2019,46(02)北大核心EICSCD
【文章页数】：7 页
【部分图文】：
凸包及其OBB的四种不同边缘接触示例
（a）Sphere（10）（b）Sphere（100）（c）Sphere（500）图6Sphere（n）数据集OBB示例Fig.6OBBsamplesforSphere（n）算法运行时性能如图7所示，其中X轴表示数据凸包中顶点的数量，Y轴表示计算OBB所对应的时间，实际数据以细线绘制.结果表明，当凸包顶点数在10000以下时，算法表现与预期的O（n3/2（logn）2）性能回归曲线有较好的匹配.00.20.40.60.81.020151050time/sSphere（n）O（n3/2（logn）2）n图7数据集Sphere（n）中计算最小体积OBB耗时Fig.7TimetakentocomputetheminimumvolumeOBBforSphere（n）由于包围盒仅取决于模型的凸包，因此先将GAMMAGroup真实模型数据集中的模型进行预处理.算法的拟合效果如图8所示，可以看出对复杂物体模型，算法所计算出的包围盒也可以进行非常紧密的包围.图9中散点图显示了算法的性能情况，X轴为该对象的凸包上的点数，Y轴表示计算OBB所需的时间（s）.这个基准测试的结果表明，大多数现实世界模型对象的计算性能与Sphere（n）的情况非常相似.如图9所示在参与测试的2088个模型中，大部分模型表现接近最佳预期.图8GAMMAGroup模型OBB示例Fig.8OBBsamplesforGAMMAGrouptime/s6543210500100015002000250030003500400045002001animalsarchitecgeometrymechanicalO（n3/2（logn）2）n图9GAMMAGroup数据集下计算最小体积OBB耗时Fig.9TimetakentocomputetheminimumvolumeOBBforGAMMAGroup在GAMMAGroup数据库的5个不同数据集中，分别对本文所提算法和文献[10]中的HYBBRID算法进行对比试验，包围效果如图10所示.因为模型个体形状差异较大，所以选取算法在不同数据集中最优情况，中位数情况和最差表现比较所得OBB包围盒?
（a）Sphere（10）（b）Sphere（100）（c）Sphere（500）图6Sphere（n）数据集OBB示例Fig.6OBBsamplesforSphere（n）算法运行时性能如图7所示，其中X轴表示数据凸包中顶点的数量，Y轴表示计算OBB所对应的时间，实际数据以细线绘制.结果表明，当凸包顶点数在10000以下时，算法表现与预期的O（n3/2（logn）2）性能回归曲线有较好的匹配.00.20.40.60.81.020151050time/sSphere（n）O（n3/2（logn）2）n图7数据集Sphere（n）中计算最小体积OBB耗时Fig.7TimetakentocomputetheminimumvolumeOBBforSphere（n）由于包围盒仅取决于模型的凸包，因此先将GAMMAGroup真实模型数据集中的模型进行预处理.算法的拟合效果如图8所示，可以看出对复杂物体模型，算法所计算出的包围盒也可以进行非常紧密的包围.图9中散点图显示了算法的性能情况，X轴为该对象的凸包上的点数，Y轴表示计算OBB所需的时间（s）.这个基准测试的结果表明，大多数现实世界模型对象的计算性能与Sphere（n）的情况非常相似.如图9所示在参与测试的2088个模型中，大部分模型表现接近最佳预期.图8GAMMAGroup模型OBB示例Fig.8OBBsamplesforGAMMAGrouptime/s6543210500100015002000250030003500400045002001animalsarchitecgeometrymechanicalO（n3/2（logn）2）n图9GAMMAGroup数据集下计算最小体积OBB耗时Fig.9TimetakentocomputetheminimumvolumeOBBforGAMMAGroup在GAMMAGroup数据库的5个不同数据集中，分别对本文所提算法和文献[10]中的HYBBRID算法进行对比试验，包围效果如图10所示.因为模型个体形状差异较大，所以选取算法在不同数据集中最优情况，中位数情况和最差表现比较所得OBB包围盒?
【参考文献】：
期刊论文
[1]一种散乱点云的均匀精简算法[J]. 李仁忠,杨曼,刘阳阳,张缓缓. 光学学报. 2017(07)
[2]基于改进OBB包围盒的碰撞检测算法[J]. 史旭升,乔立红,朱作为. 湖南大学学报(自然科学版). 2014(05)
[3]基于遗传算法的散乱点云最小包围盒求解[J]. 孙殿柱,史阳,刘华东,李延瑞. 北京航空航天大学学报. 2013(08)
[4]基于非线性主成分分析的最小包围盒计算方法[J]. 陈柏松,叶雪梅,安利. 计算机集成制造系统. 2010(11)
[5]确定任意形状物体最小包围盒的一种方法[J]. 陈华. 工程图学学报. 2010(02)
本文编号：3278418
【文章来源】：湖南大学学报(自然科学版). 2019,46(02)北大核心EICSCD
【文章页数】：7 页
【部分图文】：
凸包及其OBB的四种不同边缘接触示例
（a）Sphere（10）（b）Sphere（100）（c）Sphere（500）图6Sphere（n）数据集OBB示例Fig.6OBBsamplesforSphere（n）算法运行时性能如图7所示，其中X轴表示数据凸包中顶点的数量，Y轴表示计算OBB所对应的时间，实际数据以细线绘制.结果表明，当凸包顶点数在10000以下时，算法表现与预期的O（n3/2（logn）2）性能回归曲线有较好的匹配.00.20.40.60.81.020151050time/sSphere（n）O（n3/2（logn）2）n图7数据集Sphere（n）中计算最小体积OBB耗时Fig.7TimetakentocomputetheminimumvolumeOBBforSphere（n）由于包围盒仅取决于模型的凸包，因此先将GAMMAGroup真实模型数据集中的模型进行预处理.算法的拟合效果如图8所示，可以看出对复杂物体模型，算法所计算出的包围盒也可以进行非常紧密的包围.图9中散点图显示了算法的性能情况，X轴为该对象的凸包上的点数，Y轴表示计算OBB所需的时间（s）.这个基准测试的结果表明，大多数现实世界模型对象的计算性能与Sphere（n）的情况非常相似.如图9所示在参与测试的2088个模型中，大部分模型表现接近最佳预期.图8GAMMAGroup模型OBB示例Fig.8OBBsamplesforGAMMAGrouptime/s6543210500100015002000250030003500400045002001animalsarchitecgeometrymechanicalO（n3/2（logn）2）n图9GAMMAGroup数据集下计算最小体积OBB耗时Fig.9TimetakentocomputetheminimumvolumeOBBforGAMMAGroup在GAMMAGroup数据库的5个不同数据集中，分别对本文所提算法和文献[10]中的HYBBRID算法进行对比试验，包围效果如图10所示.因为模型个体形状差异较大，所以选取算法在不同数据集中最优情况，中位数情况和最差表现比较所得OBB包围盒?
（a）Sphere（10）（b）Sphere（100）（c）Sphere（500）图6Sphere（n）数据集OBB示例Fig.6OBBsamplesforSphere（n）算法运行时性能如图7所示，其中X轴表示数据凸包中顶点的数量，Y轴表示计算OBB所对应的时间，实际数据以细线绘制.结果表明，当凸包顶点数在10000以下时，算法表现与预期的O（n3/2（logn）2）性能回归曲线有较好的匹配.00.20.40.60.81.020151050time/sSphere（n）O（n3/2（logn）2）n图7数据集Sphere（n）中计算最小体积OBB耗时Fig.7TimetakentocomputetheminimumvolumeOBBforSphere（n）由于包围盒仅取决于模型的凸包，因此先将GAMMAGroup真实模型数据集中的模型进行预处理.算法的拟合效果如图8所示，可以看出对复杂物体模型，算法所计算出的包围盒也可以进行非常紧密的包围.图9中散点图显示了算法的性能情况，X轴为该对象的凸包上的点数，Y轴表示计算OBB所需的时间（s）.这个基准测试的结果表明，大多数现实世界模型对象的计算性能与Sphere（n）的情况非常相似.如图9所示在参与测试的2088个模型中，大部分模型表现接近最佳预期.图8GAMMAGroup模型OBB示例Fig.8OBBsamplesforGAMMAGrouptime/s6543210500100015002000250030003500400045002001animalsarchitecgeometrymechanicalO（n3/2（logn）2）n图9GAMMAGroup数据集下计算最小体积OBB耗时Fig.9TimetakentocomputetheminimumvolumeOBBforGAMMAGroup在GAMMAGroup数据库的5个不同数据集中，分别对本文所提算法和文献[10]中的HYBBRID算法进行对比试验，包围效果如图10所示.因为模型个体形状差异较大，所以选取算法在不同数据集中最优情况，中位数情况和最差表现比较所得OBB包围盒?
【参考文献】：
期刊论文
[1]一种散乱点云的均匀精简算法[J]. 李仁忠,杨曼,刘阳阳,张缓缓. 光学学报. 2017(07)
[2]基于改进OBB包围盒的碰撞检测算法[J]. 史旭升,乔立红,朱作为. 湖南大学学报(自然科学版). 2014(05)
[3]基于遗传算法的散乱点云最小包围盒求解[J]. 孙殿柱,史阳,刘华东,李延瑞. 北京航空航天大学学报. 2013(08)
[4]基于非线性主成分分析的最小包围盒计算方法[J]. 陈柏松,叶雪梅,安利. 计算机集成制造系统. 2010(11)
[5]确定任意形状物体最小包围盒的一种方法[J]. 陈华. 工程图学学报. 2010(02)
本文编号：3278418
本文链接：https://www.wllwen.com/kejilunwen/sousuoyinqinglunwen/3278418.html
