模型适应的凸包围多面体并行生成算法

摘要

包围盒在计算机图形学和计算几何领域中应用广泛,常用于加速几何求交、光线跟踪和碰撞检测等多种算法.凸包围多面体是包围盒的推广,对于一般不规则形体,可达到比包围盒更好的紧致程度.本文提出一种快速构造给定点集的紧致凸包围多面体的方法.该方法首先根据点集的近似凸包,通过k-means算法生成k个截面法向,然后利用GPU沿各法向搜索切点构成截面,最后求交构成多面体.实验结果表明,与同类算法相比,该方法能够更快地构造给定点集更紧致的凸包围多面体,并能有效加速碰撞检测算法.