Surface point location by walking algorithm for haptic visualization of triangulated 3D models

Haptic devices are nowadays gaining popularity because of their increasing availability. These special input/output devices provide, unlike mouse or keyboard, a native 3D manipulation, especially a more precise control and a force interaction. With more accurate description of the model, haptics can achieve more realistic force feedback. Therefore, triangulated surface models are often used for an authentic interpretation of 3D models. A common task in haptic visualization using triangulated surface models is to find a triangle which is in the collision trajectory of the haptic probe. Since the render rate of the haptic visualization is relatively high (usually about 1kHz), the task becomes highly non-trivial for complex mesh models, especially for the meshes which are changing over time. The paper presents a fast and novel location algorithm able to find the triangle which is close to the haptic probe and in the direction of the probe motion vector. The algorithm has negligible additional memory requirements, since it does not need additional searching data structures and uses only the information usually available for triangulated models. Therefore, the algorithm could handle even triangular meshes changing over time. Results show that the proposed algorithm is fast enough to be used in haptic visualization of complex-shaped models with hundreds of thousands of triangles.