English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/30526
Share/Impact:
Statistics
logo share SHARE logo core CORE   Add this article to your Mendeley library MendeleyBASE

Visualizar otros formatos: MARC | Dublin Core | RDF | ORE | MODS | METS | DIDL
Exportar a otros formatos:
Title

3D collision detection: a survey

AuthorsJiménez Schlegl, Pablo ; Thomas, Federico ; Torras, Carme
KeywordsCollision detection
Interference tests
Geometric algorithms
Languages and systems
Robotics
Issue Date2001
PublisherPergamon Press
CitationComputers & Graphics 25(2): 269-285 (2001)
AbstractMany applications in Computer Graphics require fast and robust 3D collision detection algorithms. These algorithms can be grouped into four approaches: space-time volume intersection, swept volume interference, multiple interference detection and trajectory parameterization. While some approaches are linked to a particular object representation scheme (e.g., space-time volume intersection is particularly suited to a CSG representation), others do not. The multiple interference detection approach has been the most widely used under a variety of sampling strategies, reducing the collision detection problem to multiple calls to static interference tests. In most cases, these tests boil down to detecting intersections between simple geometric entities, such as spheres, boxes aligned with the coordinate axes, or polygons and segments. The computational cost of a collision detection algorithm depends not only on the complexity of the basic interference test used, but also on the number of times this test is applied. Therefore, it is crucial to apply this test only at those instants and places where a collision can truly occur. Several strategies have been developed to this end: 1) to find a lower time bound for the first collision, 2) to reduce the pairs of primitives within objects susceptible of interfering, and 3) to cut down the number of object pairs to be considered for interference. These strategies rely on distance computation algorithms, hierarchical object representations, orientation-based pruning criteria, and space partitioning schemes. This paper tries to provide a comprehensive survey of all these techniques from a unified viewpoint, so that well-known algorithms are presented as particular instances of general approaches.
Publisher version (URL)http://dx.doi.org/10.1016/S0097-8493(00)00130-8
URIhttp://hdl.handle.net/10261/30526
DOI10.1016/S0097-8493(00)00130-8
ISSN0097-8493
Appears in Collections:(IRII) Artículos
Files in This Item:
File Description SizeFormat 
doc1.pdf276,3 kBAdobe PDFThumbnail
View/Open
Show full item record
Review this work
 

Related articles:


WARNING: Items in Digital.CSIC are protected by copyright, with all rights reserved, unless otherwise indicated.