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

A method that approximates a solid object by object oriented bounding box tree (OBB-Tree) having minimal summed volume outside the object is proposed. First, the outside volume for a single OBB is defined and computed by a hardware-accelerated algorithm. Then, the construction of one OBB-Tree is formulated into a variational approximation. To solve such an approximation, this paper presents an algorithm that minimizes the total outside volume over all OBBs in the same level using the iterative Lloyd clustering and using a variant of iterative MultiGrid among levels. In experiments, comparing against a state-of-the-art alternative, the resulting OBB-Tree is tighter and has better performance in the test of collision detection.

Supported by the National Natural Science Foundation of China under Grant No.60773184 (国家自然科学基金)