A New Line-based Algorithm for Real Time Haptic Interactions with Virtual Environments

In real time computer graphics, "interactivity" is limited to a display rate of 30 frames per second. However, in multimodal virtual environments involving haptic interactions, a much higher update rate of about 1 kHz is necessary to ensure continuous interactions and smooth transitions. The simplest and most efficient interaction paradigm in such environments is to represent the haptic cursor as a point. However, in many situations, such as those in the development of real time simulations involving the interactions of long slender tools with complex models, such a paradigm is nonrealistic and at least a line-based interaction is more desirable. While such paradigms exist, the main impediment to their widespread use is the associated computational complexity. In this paper, we introduce, for the first time, an efficient algorithm for computing the interaction of a line-shaped haptic cursor and polygonal surface models which has a near constant complexity. The algorithm relies on space-time coherence, topological information and the properties of lines in 3D space to maintain proximity information between a line segment and triangle meshes. For interaction with convex objects, the line is represented by its end points and a dynamic point, which is chosen to be the closest point on the line to any potentially colliding triangle. To deal with multiple contacts and non-convexities, the line is decomposed into segments and a dynamic point is used for each segment. Realistic examples are presented to demonstrate the effectiveness of our approach.