Haptic Rendering of Point Set Surfaces

We present a haptic rendering algorithm for a point set surface. Given a point set, its point set surface is an implicit surface defined by local projection of point sets using the moving least square (MLS) method. Our haptic algorithm is a penalty-based method which requires a calculation of the minimum distance between the haptic interaction point (HIP) and point set surfaces. Thus, a rapid calculation of this distance is the main ingredient of our haptic rendering algorithm. As preprocess, our algorithm builds a bounding volume hierarchy (BVH) of swept sphere volumes (SSV)for each of given point sets. Here, the SSV is defined as volume swept by a moving sphere. Then, at run-time, we find a pair of closest points between the point set and HIP using a SSV hierarchy. We attempt to further refine the distance by projecting the closest pair of point to its local point set surface by using the MLS projection. In order to execute the MLS projection, we need to find points in a local neighborhood of the closest point pair. We again use the SSV hierarchy to find the neighborhood by performing collision detection between a sphere, defining the local neighborhood, and the SSV hierarchy. This results in a highly fast and reliable calculation of closest surface distance between the point set model and HIP. In practice, our algorithm takes 0.2 ~ 0.3 msec to calculate haptic feedback for a point set consisting of more than 24K points