English   español  
Please use this identifier to cite or link to this item: http://hdl.handle.net/10261/30526
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:


3D collision detection: a survey

AuthorsJiménez Schlegl, Pablo ; Thomas, Federico ; Torras, Carme
KeywordsCollision detection
Interference tests
Geometric algorithms
Languages and systems
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
Appears in Collections:(IRII) Artículos
Files in This Item:
File Description SizeFormat 
doc1.pdf276,3 kBAdobe PDFThumbnail
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.