The existing shape diameter function (SDF) algorithm has to compute intersection points between the input surface and the rays bounded by an inward cone,and thus can not deal with point clouds with holes or gaps.In this paper,we propose a fast algorithm for this problem.We first give an explicit formula of SDF on smooth surfaces and then extend this formula to the discrete setting where the volume of a cone is discretized into 120 units.We employ a voting technique to select the valid penetration distance for each unit and further use the OBB tree of the input point cloud to handle points in a batch mode,rather than one by one.The final SDF at each point is reported by averaging the penetration distances associated with these units.Experimental results show that our algorithm can be used to many applications including shape retrieval and thickness visualization.%针对已有的形状直径函数(SDF)算法需要计算落在锥体里面的若干条射线和物体表面的交点,不能直接处理点云曲面或者带洞的几何模型的问题,提出点云上的SDF算法.首先推导了连续曲面上的SDF显式公式,并将其推广至离散点集;然后在离散情况下把锥体内部空间离散化为120个单元,采用投票技巧筛选出每个单元上的有效穿透距离;再采用OBB树批量处理点云数据,而不是逐点判断;最后把所有单元块的穿透距离进行加权得到最终的SDF值.实验结果表明,该算法可应用于形状检索和厚度可视化等多种场合.
展开▼
