基于三维凸包计算凸多面体 Minkowski 和算法

摘要

In the calculation of the exact collision detection between the actual object,the traditional Minkowski sum algorithm are dif⁃ficult to directly obtain data required for operation,so there needs for large amounts of data pre⁃processing.In order to improve the computing speed,reduce the amount of data processing,a new calculation method of 3D convex hull is designed and used to calculate the Minkowski sum of two spatial convex polyhedrons directly through their point cloud information.And the Minkowski sum boundary information is represented by the calculated results of convex hull face set.A detailed description of the algorithm is given and the complexity of the algorithm is analyzed.The results show that the algorithm is effectiveness through comparing the experimental data.%传统的 Minkowski 和算法在计算实际物体间的精确的碰撞干涉时，很难直接获取运算所需的数据，进而需要进行大量的数据预处理。为了提高运算速度，减少数据处理量，本文设计了一种新的三维凸包计算方法，通过空间两凸多面体外表的点云信息直接计算其 Minkowski 和，用计算得到的凸包的面集表示 Minkowski 和的边界信息。然后，给出详细的算法描述和复杂度分析，并通过对比分析实验数据，验证了该算法的有效性。