实体网格模型的变分层次有向包围盒构建

层次有向包围盒(objectorientedboundingboxtree,简称obb-tree)在碰撞检测、实时绘制等诸多场合有着广泛的应用.研究了实体网格模型的层次有向包围盒的构建问题,提出了新的优化求解方法.首先以属于层次包围盒但不属于实体网格模型的这部分外部空间体积作为误差,并给出基于硬件加速的误差计算方法.其次,将层次包围盒的构建问题转化为变分逼近问题,通过求解全局误差最小来最优的层次有向包围盒.在优化计算上,我们提出在同层内采用lloyd分簇迭代与在层次间采用类似multigrid的往复迭代相结合的方法.与前人的结果比较,此方法可以生成对原实体网格模型包裹更紧密的层次有向包围盒逼近,在碰撞检测的实际应用中,使用此方法构建的结果可以减少碰撞检测的计算时间提高检测效率.