论文部分内容阅读
虚拟积木搭建软件近年来受到更多人的关注,在虚拟积木搭建软件中,用户使用积木模型进行拼接,模型之间可以进行拼接,同时不能出现重叠现象。因此对积木模型进行碰撞检测是虚拟积木搭建软件中基本且必不可少的环节。在积木搭建软件中模型均是非凸模型,为了实现非凸模型碰撞检测的实时性,现在的虚拟积木搭建软件使用人工为模型添加凸碰撞体来对模型进行拟合。但在人工为模型添加凸碰撞体的方案存在添加速度慢、添加不准确等问题。针对上述两种情况,本文提出了一种基于长方体拟合的动态规划算法(Cuboid Fitting Dynamic Programming Algorithm,简称CFDP算法)用于对虚拟积木模型自动化地添加凸碰撞体。使用该方法可以为虚拟积木模型添加凸碰撞体,从而使积木模型在软件中可以有效的进行碰撞检测,本文主要工作如下:(1)本文将自动化地为虚拟积木模型添加凸碰撞体这一问题在空间直角坐标系中进行描述,并在第二章中将问题分解为两个子问题:子问题一是使用可忽略体积的单位长方体作为碰撞体将模型填充;子问题二是将单位长方体进行合并减少碰撞体数量。将问题抽象成为三维数组中的动态规划问题。(2)本文提出了基于长方体拟合的动态规划算法,该算法分为两个步骤:分解步骤与合并步骤,分别对应两个子问题的求解。(3)在第三章中对算法生成碰撞体的结果进行了分析,分别对比了人工添加的碰撞体与使用CFDP算法添加的碰撞体在体积占比、碰撞体数量以及添加时间三方面的区别,实验结论体现了算法的高效性和准确性。(4)在文章最后介绍了该算法在AI制造虚拟积木搭建软件中的应用。在该软件中我们使用CFDP算法为虚拟积木模型添加了凸碰撞体。经过软件功能测试和性能测试,验证使用CFDP算法添加凸碰撞体的积木模型在实际应用中的实用性和可靠性。