Search

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.

Finding which triangle in a planar triangle mesh contains a query point is one of the most frequent tasks in computational geometry. Usually, a large number of point locations has to be performed, and so there is a need for fast algorithms resistant to changes in triangulation and having minimal additional memory requirements. The so-called walking algorithms offer low complexity, easy implementation and negligible additional memory requirements, which makes them suitable for such applications. In this paper, we propose a walking algorithm which significantly improves the current barycentric approach and propose how to effectively combine this algorithm with a suitable hierarchical structure in order to improve its computational complexity. The hierarchical data structure used in our solution is easy to implement and requires low additional memory while providing a significant acceleration thanks to the logarithmic computational complexity of the search process.

The point location problem is one of the most frequent tasks in computational geometry. The walking algorithms are one of the most popular solutions for finding an element in a mesh which contains a query point. Despite their suboptimal complexity, the walking algorithms are very popular because they do not require any additional memory and their implementation is simple. This paper describes the modifications of two walking algorithms for point location on a surface of a star-shaped polyhedron, a generalization of the Remembering Stochastic walk algorithm for a star-shaped polyhedron and a modification of the planar Orthogonal walk algorithm. The latter uses spherical coordinates to transfer the spatial point location problem to the planar point location problem. This way, the problem can be solved by the traditional planar algorithms. Along with the modifications, the paper proposes new methods for finding a proper starting triangle for the walking process with or without preprocessing.