Haptic-assisted virtual assembly and prototyping has seen significant attention over the past two decades. However, in spite of the appealing prospects, its adoption has been slower than expected. We identify the main roadblocks as the inherent geometric complexities faced when assembling objects of arbitrary shape, and the computation time limitation imposed by the notorious 1 kHz haptic refresh rate. We addressed the first problem in a recent work by introducing a generic energy model for geometric guidance and constraints between features of arbitrary shape. In the present work, we address the second challenge by leveraging Fourier transforms to compute the constraint forces and torques. Our new concept of “geometric energy” field is computed automatically from a cross-correlation of “skelet al densities” in the frequency domain, and serves as a generalization of the manually specified virtual fixtures or heuristically identified mating constraints proposed in the literature. The formulation of the energy field as a convolution enables efficient computation using fast Fourier transforms (FFTs) on the graphics processing unit (GPU). We show that our method is effective for low-clearance assembly of objects of arbitrary geometric and syntactic complexity.
Among the combinatorial CD methods that are popular in haptic assembly---due to their computational efficiency in the presence of the 1 kHz requirement---are Voronoi-clipping marching methods (e.g., V-Clip @cite_7 , SWIFT @cite_54 , and SWIFT++ @cite_10 ), oriented bounding box (OBB) tree-based methods (e.g, H-COLLIDE @cite_20 @cite_55 and RAPID @cite_1 ), and volumetric enumeration methods (e.g., the well-known Voxmap PointShell (VPS) @cite_8 @cite_11 used in the earlier versions of SHARP @cite_29 @cite_51 , and its improved variants @cite_15 @cite_35 ). More efficient hierarchical data structures have been developed using spherical primitives (e.g., hierarchical bounding sphere (HBS) tree-based methods @cite_56 @cite_12 and inner sphere tree (IST) methods @cite_53 @cite_39 successfully applied to haptic rendering @cite_24 @cite_31 @cite_30 ). By leveraging the spherical symmetry in primitive collision predicates, sphere trees are generally more efficient alternatives to OBB trees, and represent nonuniform extensions to the uniform volumetric enumeration in VPS at every layer of the hierarchy. Although they have been shown to outperform VPS for nonconvex moving objects, their effectiveness to handle thin objects is yet to be tested @cite_18 .
@cite_30 @cite_35 @cite_54 @cite_29 @cite_15 @cite_10 @cite_20 @cite_18 @cite_8 @cite_39 @cite_7 @cite_55 @cite_56 @cite_12 @cite_53 @cite_1 @cite_24 @cite_31 @cite_51 @cite_11
1990843467 2047676359 190320872 1994039838
We present a framework for fast and accurate collision detection for haptic interaction with polygonal models. Given a model, we pre-compute a hybrid hierarchical representation, consisting of uniform grids and trees of tight-fitting oriented bounding box trees (OBB-Trees). At run time, we use hybrid hierarchical representations and exploit frame-to-frame coherence for fast proximity queries. We describe a new overlap test, which is specialized for intersection of a line segment with an oriented bounding box for haptic simulation and takes 6-36 operations excluding transformation costs. The algorithms have been implemented as part of H-COLLIDE and interfaced with a PHANToM arm and its haptic toolkit, GHOST, and applied to a number of models. As compared to the commercial implementation, we are able to achieve up to 20 times speedup in our experiments and sustain update rates over 1000Hz on a 400MHz Pentium II. We present a novel geometric data structure for approximate collision detection at haptic rates between rigid objects. Our data structure, which we call inner sphere trees, supports both proximity queries and the penetration volume; the latter is related to the water displacement of the overlapping region and, thus, corresponds to a physically motivated force. Moreover, we present a multi-threaded version of the penetration volume computation for time-critical haptic rendering that is based on separation lists and the novel notion of expected overlapping volumes. Finally, we show how to use the penetration volume to compute continuous contact forces and torques that enable a stable rendering of 6-DOF penalty-based distributed contacts. The main idea of our new data structure is to bound the object from the inside with a bounding volume hierarchy, which can be built based on dense sphere packings. In order to construct an efficient hierarchy, we propose to use an AI clustering algorithm, which we extend and adapt here. The results show performance at haptic rates both for proximity and penetration volume queries for models consisting of hundreds of thousands of polygons.© 2009 ASME This paper presents work in progress on a new technique for visu- alising and manipulating large hierarchies. The information slices approach compactly visualises hierarchical structures using a series of semi-circular discs. The technique is described in the context of our early experience with a prototype file system visualiser based on information slices. Over the last few years, the emerging field of information visuali- sation has resulted in a numerous techniques for helping visualise and make sense of large information spaces (10). Among these are several techniques for visualising and interacting with large hierar- chies which go beyond the traditional approach taken in 2d scrolling browsers such as the Windows Explorer. Treemaps (6, 9) are space-filling visualisations of hierarchies based on successive horizontal and vertical subdivision of screen rectangles. The area of each rectangle is proportional to some at- tribute of the underlying hierarchy such as the (total) size of each subtree. Xdu (4) is a utility for the X window system which displays a graphical disk usage for Unix file systems. Rectangles are stacked from left to right as the directory tree is descended. The current di- rectory is represented by the leftmost rectangle, which is the entire height of the window. Subdirectories are represented by neighbour- ing rectangles in the next column, whose height are proportional to the size of each subdirectory. The hyperbolic browser (7) uses a focus and context technique based on hyperbolic geometry. A hierarchy is laid out uniformly on the hyperbolic plane and then mapped to the unit disc for display on screen. Nodes in the centre of the disc are largest and nodes are assigned progressively less space towards the perimeter of the disc. Cheops (3) is based on multiple re-use of overlaid triangles in the display. Working top-down, the selection of a node (triangle) at a particular level designates that node's children are to be represented Based on our new geometric data structure, the inner sphere trees, we present fast and stable algorithms for different kinds of collision detection queries between rigid objects at haptic rates. Namely, proximity queries and the penetration volume, which is related to the water displacement of the overlapping region and thus corresponds to a physically motivated force. The latter allows us to define a novel penalty-based collision response scheme that provides continuous forces and torques which are applicable to physically-based simulations as well as to haptic rendering scenarios. Moreover, we present a time-critical version of the penetration volume computation that is able to achieve very tight bounds within a fixed budget of query time. The main idea of our new data structure is to bound the object from the inside with a set of non-overlapping bounding volumes. The results show performance at haptic rates both for proximity and penetration volume queries, independent from the polygon count of the objects.