“Haptic deformation using graphics hardware and kd-trees” by Lee, Kim, Park, Lee and Ryu

  • ©Beom-Chan Lee, Jong-Phil Kim, Jeung-Chul Park, Kwan H. Lee, and Jeha Ryu




    Haptic deformation using graphics hardware and kd-trees



     In this paper, we describe a haptic deformation algorithm using graphics hardware and spatial partitioning data structure. Since object-based collision detection methods are generally dependent on the geometrical structure of objects, these are not fast enough for deformable objects. Thus Z-buffer depth comparison using graphics hardware is used for detecting collision between a haptic probe and an object. In order to determine what region to deform in response to a user’s actions, we adopted a nearest neighbor search algorithm based on a kd-tree structure [Moore. 1991]. At the same  time, the reaction force to be presented to the user is calculated in the haptic rendering loop. To compute response force for object’s deformation, mass-spring methods are utilized. Where masses are assigned to vertices and a set of springs are allocated to connect vertices.    



    1. J. P. Kim and J. Ryu, “Hardware Based 2.5D Haptic Rendering Algorithm using Localized Occupancy Map Instance”, ICAT, pp. 132–137, 2004.
    2. Andrew Moore, “An introductory tutorial on kd-trees”, PhD. Thesis, Technical Report No. 209, Computer Laboratory, University of Cambridge, 1991.

ACM Digital Library Publication:

Overview Page: