A framework for bounded-time collision detection in haptic interactions

In this paper we present the V-GRAPH, a framework for bounded-time collision detection for point-like haptic interactions. This frame-work employs strategies similar to those used by the Lin-Canny and Dobkin-Kirkpatrick algorithms but, differently from these ones, it uses a partition of the space focused on vertices only, which al-lows both for an easier implementation and for usage with non-convex objects without the need for splitting the original mesh. In a preprocessing phase the mesh is analyzed to extract neighboring information based on Voronoi theory, then this data is used at run-time in a greedy visit exploiting motion coherence to achieve fast proximity queries. Finally standard segment-triangle intersection tests are eventually carried out to identify the exact point of collision. Moreover the framework can be easily extended to multiple levels of detail. Computational analysis and experimental results show that execution times are independent from mesh complexity, achieving same running times even on models composed by mil-lions of polygons. These features make it particularly suited for virtual museum and digital sculpting applications. Implementation is straightforward and freely available tools can be used for pre-processing.