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
2047676359 1493784828 2148155904 2022891348 1997959223 2113525359 1990843467 2031093399 2033849809 1674535469 2045471590 2053212688 2069476964 2294676795 1999250663 2013526052 1994039838 2159923417 2075528047
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 The Voxmap-PointShell TM (VPS) Algorithm is a haptic rendering algorithm able to compute collision responses with 1 kHz update-rates with arbitrarily complex scenarios. This work introduces fast algorithms to generate the two haptic data-structures used by the VPS algorithm: voxmaps - voxelized volume structures for static objects - and pointshells - point-clouds describing moving objects - . For generating voxmaps, collision tests based on the Separating Axis Theorem are carried out. On the other hand, pointshells are generated utilizing optimization strategies to place points uniformly on the surface of the objects. The improvements in performance and quality obtained compared to the previous generating algorithms from DLR are included, all of them carried out on virtual car models provided by Volkswagen and artificial models. We present an accelerated proximity query algorithm between moving convex polyhedra. The algorithm combines Voronoi-based feature tracking with a multi-level-of-detail representation, in order to adapt to the variation in levels of coherence and speed up the computation. It provides a progressive refinement framework for collision detection and distance queries. We have implemented our algorithm and have observed significant performance improvements in our experiments, especially on scenarios where the coherence is low. Virtual Reality (VR) technology holds promise as a virtual prototyping tool for mechanical assembly; however, several developmental challenges still need to be addressed before virtual prototyping applications can successfully be integrated into the product realization process. This paper describes the development of SHARP (System for Haptic Assembly & Realistic Prototyping), a portable VR interface for virtual assembly. SHARP uses physically-based modeling for simulating realistic part-to-part and hand-to-part interactions in virtual environments. A dual handed haptic interface for realistic part interaction using the PHANToM® haptic devices is presented. The capability of creating subassemblies enhances the application’s ability to handle a wide variety of assembly scenarios. Swept volumes are implemented for addressing maintainability issues and a network module is added for communicating with different VR systems at dispersed geographic locations. Support for various types of VR systems allows an easy integration of SHARP into the product realization process resulting in faster product development, faster identification of assembly and design issues and a more efficient and less costly product design process. Real-time evaluation of distributed contact forces for rigid or deformable 3D objects is important for providing multi-sensory feedback in emerging real-time applications, such as 6-DoF haptic force-feedback rendering. Unfortunately, at very high temporal rates (1 kHz for haptics), there is often insufficient time to resolve distributed contact between geometrically complex objects. In this paper, we present a spatially and temporally adaptive sample-based approach to approximate contact forces under hard real-time constraints. The approach is CPU based, and supports contact between a rigid and a reduced deformable model with complex geometry. Penalty-based contact forces are efficiently resolved using a multi-resolution point-based representation for one object, and a signed-distance field for the other. Hard realtime approximation of distributed contact forces uses multi-level progressive point-contact sampling, and exploits temporal coherence, graceful degradation and other optimizations. We present several examples of 6-DoF haptic rendering of geometrically complex rigid and deformable objects in distributed contact at real-time kilohertz rates. The need to perform fast and accurate proximity queries arises frequently in physically-based modeling, simulation, animation, real-time interaction within a virtual environment, and game dynamics. The set of proximity queries include intersection detection, tolerance verification, exact and approximate minimum distance computation, and (disjoint) contact determination. Specialized data structures and algorithms have often been designed to perform each type of query separately. We present a unified approach to perform any of these queries seamlessly for general, rigid polyhedral objects with boundary representations which are orientable 2-manifolds. The proposed method involves a hierarchical data structure built upon a surface decomposition of the models. Furthermore, the incremental query algorithm takes advantage of coherence between successive frames. It has been applied to complex benchmarks and compares very favorably with earlier algorithms and systems. 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. Purpose – The paper aims to present interactive simulation with haptic feedback as a valid method for solving complex assembly problems in the context of industrial product development. Its purpose is to clarify the position of interactive simulation with respect to other methods, and to emphasize its specific value for design engineers.Design methodology approach – The paper describes the challenges faced by design engineers in the context of design for assembly and assembly process planning. It introduces and compares automatic path planning and interactive simulation as two different approaches for checking the feasibility of assembly tasks. It provides a review of the scientific challenges and technical issues faced when implementing interactive simulation with haptic feedback in this context. It presents recent research results in the domains of final insertion and human model simulation.Findings – The paper provides an overview of the scientific, technological and practical aspects of interactive si... A simple, fast, and approximate voxel-based approach to 6-DOF haptic rendering is presented. It can reliably sustain a 1000 Hz haptic refresh rate without resorting to asynchronous physics and haptic rendering loops. It enables the manipulation of a modestly complex rigid object within an arbitrarily complex environment of static rigid objects. It renders a short-range force field surrounding the static objects, which repels the manipulated object and strives to maintain a voxel-scale minimum separation distance that is known to preclude exact surface interpenetration. Force discontinuities arising from the use of a simple penalty force model are mitigated by a dynamic simulation based on virtual coupling. A generalization of octree improves voxel memory efficiency. In a preliminary implementation, a commercially available 6-DOF haptic prototype device is driven at a constant 1000 Hz haptic refresh rate from one dedicated haptic processor, with a separate processor for graphics. This system yields stable and convincing force feedback for a wide range of user controlled motion inside a large, complex virtual environment, with very few surface interpenetration events. This level of performance appears suited to applications such as certain maintenance and assembly task simulations that can tolerate voxel-scale minimum separation distances. 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 different kinds of queries, 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. Moreover, we present a time-critical version of the penetration volume computation that is able to achieve very tight upper and lower bounds within a fixed budget of query time. The main idea is to bound the object from the inside with a bounding volume hierarchy, which can be constructed based on dense sphere packings. In order to build our new 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. This article presents the Voronoi-clip, or V-Clip, collision detection alogrithm for polyhedral objects specified by a boundary representation. V-Clip tracks the closest pair of features between convex polyhedra, using an approach reminiscent of the Lin-Canny closest features algorithm. V-Clip is an improvement over the latter in several respects. Coding complexity is reduced, and robustness is significantly improved; the implementation has no numerical tolerances and does not exhibit cycling problems. The algorithm also handles penetrating polyhedra, and can therefore be used to detect collisions between nonvconvex polyhedra described as hierarchies of convex pieces. The article presents the theoretical principles of V-Clip, and gives a pseudocode description of the algorithm. It also documents various test that compare V-Clip, Lin-Canny, and the Enhanced GJK algorithm, a simplex-based algorithm that is widely used for the same application. The results show V-Clip to be a strong contender in this field, comparing favorably with the other algorithms in most of the tests, in term of both performance and robustness. Hierarchical object representations play an important role in performing efficient collision handling. Many different geometric primitives have been used to construct these representations, which allow areas of interaction to be localized quickly. For time-critical algorithms, there are distinct advantages to using hierarchies of spheres, known as sphere-trees, for object representation. This article presents a novel algorithm for the construction of sphere-trees. The algorithm presented approximates objects, both convex and non-convex, with a higher degree of fit than existing algorithms. In the lower levels of the representations, there is almost an order of magnitude decrease in the number of spheres required to represent the objects to a given accuracy. We present a data structure and an algorithm for efficient and exact interference detection amongst complex models undergoing rigid motion. The algorithm is applicable to all general polygonal models. It pre-computes a hierarchical representation of models using tight-fitting oriented bounding box trees (OBBTrees). At runtime, the algorithm traverses two such trees and tests for overlaps between oriented bounding boxes based on a separating axis theorem, which takes less than 200 operations in practice. It has been implemented and we compare its performance with other hierarchical data structures. In particular, it can robustly and accurately detect all the contacts between large complex geometries composed of hundreds of thousands of polygons at interactive rates. CR Haptic interaction in six degrees of freedom is critical to numerous applications, but is still prohibitively complex for realistic environments. This paper presents an approach to rendering six-degree-of-freedom contact among virtual objects using a novel data structure referred to as an implicit sphere tree. This data structure allows an extremely compact representation of volumetric objects and extremely rapid intersection testing among objects, which broadens the scope of virtual environments that can be rendered in six degrees of freedom at interactive rates. We introduce this data structure, along with appropriate techniques for collision detection and haptic rendering, and demonstrate its efficiency in representing and manipulating complex models. 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. Virtual reality (VR) technology holds promise as a virtual prototyping (VP) tool for mechanical assembly; however, several developmental challenges still need to be addressed before VP applications can successfully be integrated into the product realization process. This paper describes the development of System for Haptic Assembly and Realistic Prototyping (SHARP), a portable virtual assembly system. SHARP uses physics-based modeling for simulating realistic part-to-part and hand-to-part interactions in virtual environments. A dual-handed haptic interface for a realistic part interaction using the PHANToM® haptic devices is presented. The capability of creating subassemblies enhances the application’s ability to handle a wide variety of assembly scenarios at the part level as well as at the subassembly level. Swept volumes are implemented for addressing maintainability issues, and a network module is added for communicating with different VR systems at dispersed geographic locations. Support for various types of VR systems allows an easy integration of SHARP into the product realization process, resulting in faster product development, faster identification of assembly and design issues, and a more efficient and less costly product design process. An approach is presented for realizing an order-of-magnitude improvement in spatial accuracy for voxel-based 6-DOF haptics. It trades constant-time performance for greater spatial accuracy. This helps to make 6-DOF haptics applicable to extraordinarily complex real-world task simulations, which often admit no other known solution short of physical mockup. A reduction of haptic fidelity is tactically incurred but simultaneously mitigated by augmenting standard voxel-sampling methodology with distance fields, temporal coherence, and culling of redundant polyhedral surface interactions. This is applied to large-scale haptic scenarios involving multiple moving objects and to collaborative virtual environments.