Collision and proximity queries

Ming C. Lin, Dinesh Manocha, Young J. Kim

Research output: Chapter in Book/Report/Conference proceedingChapterpeer-review

16 Scopus citations


In a geometric context, a collision or proximity query reports information about the relative configuration or placement of two objects. Some of the common examples of such queries include checking whether two objects overlap in space, or whether their boundaries intersect, or computing the minimum Euclidean separation distance between their boundaries. Hundreds of papers have been published on different aspects of these queries in computational geometry and related areas such as robotics, computer graphics, virtual environments, and computer-aided design. These queries arise in different applications including robot motion planning, dynamic simulation, haptic rendering, virtual prototyping, interactive walkthroughs, computer gaming, and molecular modeling. For example, a large-scale virtual environment, e.g., a walkthrough, creates a model of the environment with virtual objects. Such an environment is used to give the user a sense of presence in a synthetic world and it should make the images of both the user and the surrounding objects feel solid. The objects should not pass through each other, and objects should move as expected when pushed, pulled, or grasped; see Fig. 39.0.1. Such actions require fast and accurate collision detection between the geometric representations of both real and virtual objects. Another example is rapid prototyping, where digital representations of mechanical parts, tools, and machines, need to be tested for interconnectivity, functionality, and reliability. In Fig. 39.0.2, the motion of the pistons within the combustion chamber wall is simulated to check for tolerances and verify the design.

Original languageEnglish
Title of host publicationHandbook of Discrete and Computational Geometry, Third Edition
PublisherCRC Press
Number of pages28
ISBN (Electronic)9781498711425
ISBN (Print)9781498711395
StatePublished - 1 Jan 2017

Bibliographical note

Publisher Copyright:
© 2018 by Taylor & Francis Group, LLC.


Dive into the research topics of 'Collision and proximity queries'. Together they form a unique fingerprint.

Cite this