|
|
|
|
Collision Detection and Proximity Query PackagesDEEPDEEP, dual-space expansion for estimating penetration depth, is an incremental algorithm to estimate the penetration depth between convex polytopes along with the associated penetration direction. Here, penetration depth (PD) is defined as the minimum translation distance to make the interiors of two polytopes disjoint. DEEP finds a locally optimal solution by walking on the surface of the Minkowski sums. Furthermore, DEEP is designed to fully utilize the frame-to-frame motion coherence in the environment. H-COLLIDEH-COLLIDE is a framework for fast and accurate collision detection for haptic interaction. It consists of a number of algorithms and a system specialized for computing contact(s) between the probe of the force-feedback device and objects in the virtual environment. To meet the stringent performance requirements for haptic interaction, we use an approach that specializes many earlier algorithms for this application. Our framework utilizes:
I-COLLIDEI-COLLIDE only works for models which are convex polyhedra. But it exploits the special characteristics of convex polytopes to very quickly determine contact status. It also exploits temporal coherence, so that collision query times are extremely fast when the models are moved only a relatively small amount between frames. I-COLLIDE employs a similar n-body processing algorithm to V-COLLIDE. I-COLLIDE maintains the placements of all the models, and updates the potential contact pair list as the models placements' are modified. So, objects may be added and deleted from the managed set whenever the client wishes. One of I-COLLIDE's great strengths is that it returns the distance between interesting pairs of objects (you get to decide beforehand what pairs are considered interesting). The SWIFT package provides the same functionality as I-COLLIDE and more. It is also faster and much more robust and should be used instead. IMMPACTWe describe an approach for interactive collision detection and proximity computations on massive models composed of millions of geometric primitives. We address issues related to interactive data access and processing in a large geometric database, which may not fit into main memory of typical desktop workstations or computers. We present a new algorithm using overlap graphs for localizing the "regions of interest" within a massive model, thereby reducing runtime memory requirements. The overlap graph is computed off-line, pre-processed using graph partitioning algorithms, and modified on the fly as needed. At run time, we traverse localized sub-graphs to check the corresponding geometry for proximity and pre-fetch geometry and auxiliary data structures. To perform interactive proximity queries, we use bounding-volume hierarchies and take advantage of spatial and temporal coherence. Based on the proposed algorithms, we have developed a system called IMMPACT and used it for interaction with a CAD model of a power plant consisting of over 15 million triangles. We are able to perform a number of proximity queries in real-time on such a model. PIVOTPIVOT, proximity information from Voronoi techniques, is currently a two-dimensional proximity engine. The engine utilizes hardware accelerated multi-pass rendering techniques and distance computation to perform a variety of proximity queries between objects. The supported queries include detecting collisions, computing intersections, separation distances, penetration depth, and contact points with normals. We use a hybrid geometry- and image-based approach that balances CPU and graphics subsystems that allows the use to customize settings for their particular application. PIVOT handles two-dimensional simple closed polygons. The polygon can be non-convex however, saving the application the problem of decomposing objects into triangles. PIVOT has performed very well in applications that require detailed information about the proximity even when objects are penetrating, such as penalty-based simulators. PIVOT2D has been released to the public. PQPAs compared to RAPID, PQP also provides support for distance computation and tolerance verification queries (in addition to collision detection). Its API is similar to that of RAPID. It is applicable to general polygonal models and needs no topological information. Given two models, PQP supports a number of different queries. It makes use of swept sphere volumes as the choice of BV for distance queries. Furthermore, it allows the client program the flexibility of using more than one bounding volume for a given query. More details are available. RAPIDOf the packages, RAPID is the smallest and easiest to use. It works with polygon soups, which are just polygonal models which do not require any particular topological structure, such as forming a mesh or even a closed object. RAPID will accept a cloud of disconnected triangles as a model. RAPID does require that the models be composed of triangles (as opposed to quadrilaterals, for instance). Given two models and their placement within a world coordinate system, RAPID returns a list of the triangle contact pairs - where each contact pair is a triangle taken from each model. If the list it returns is an empty list, then the models do not touch. To process a pair of models, the client program must explicitly call a collision procedure, passing those two models and their placements. Hence, RAPID does not perform n-body processing - which is the determination of which pairs of a collection of models are in contact. RAPID only processes a specific pair of models upon an explicit command from the client program. So, if you have a small or moderate number of complex polygonal models on which you (as author of the client program) are willing to make pair-processing queries explicitly, RAPID is probably the right system for you. SWIFTSWIFT provides proximity queries such as intersection detection, exact and approximate distance computation, and contact determination of three-dimensional objects undergoing rigid motion. The allowed objects are convex polyhedra or composite objects constructed from convex pieces. SWIFT uses a sweep and prune test to remove uninteresting pairs from further consideration and then uses an improved Lin-Canny closest features algorithm to find the answer for the "close" pairs of objects. The I-COLLIDE package provides a subset of the functionality provided by SWIFT. In addition, SWIFT is much faster and more robust, so it should be used instead of I-COLLIDE. SWIFT++SWIFT++ provides proximity queries such as intersection detection, tolerance verification, exact and approximate distance computation, and contact determination of general three-dimensional polyhedral objects undergoing rigid motion. SWIFT++ operates by first computing a surface decomposition of the input models. The pieces are then grouped hierarchically using convex hulls. A pair of bounding volume hierarchies (BVHs) are tested using an improved Lin-Canny closest feature tracking algorithm. SWIFT++ uses the SWIFT core for the overlap test between convex pieces in the BVHs. More about SWIFT++ V-COLLIDEV-COLLIDE is an n-body processor built on top of the RAPID system. Once your client program tells V-COLLIDE where all the models are in world space, V-COLLIDE performs a fast sweep-and-prune operation to decide which pairs of models are potentially in contact, and then for each potential contact pair it uses RAPID to determine true contact status. V-COLLIDE remembers where all the models are, and you can update some or all of the model placements by telling V-COLLIDE their new placements - RAPID makes incremental changes in the potential contact information with each placement modification. V-COLLIDE also works with polygon soups, and reports only contact status (but not distance). If you have many complex objects, many of which can bump into many of the other objects, then V-COLLIDE is probably the right choice. In addition to updating the models' positions, the client program can also add or delete models from the collection being managed by the V-COLLIDE collision detection engine. V-COLLIDE also supports multiple independent collision detection engines. This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder. |