The Shape Diameter Function on Point Clouds

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.