Movies of Proximity Query Applications

Dynamic Simulation

Collision detection can assist in computing physically realistic motion. Using a prototype of PQP, we performed collision detection on this falling rings example, between all 45 pairs of rings at each of 557 frames of animation. Each ring has 256 triangles. The average query time for each ring pair was .402 ms using a Pentium II 400 MHz machine.

rings.mpg - 1.1 MB

Thanks to Jim Cremer of the University of Iowa for the model and motion sequence.

Virtual Prototyping

This movie shows the motion of a piston (3,614 triangles) in an engine block (5,289 triangles). Collision detection can be used to verify that the piston slides without touching its chamber; distance computation can measure the gap between them. On a 400 MHz Pentium II, our average collision query time between the piston and block was 36.7 ms; the average exact distance query time was 213 ms.

This example is also a good application of tolerance queries. A tolerance query can report whether the piston and engine block come closer than a minimum allowable separation.

engine.mpg - 3.1 MB

Thanks to EAI for the engine model and motion sequences.

Path Planning

The collision free path of a torus (20,000 triangles) in a cave-like model (50,970 triangles) was precomputed by a path planner using distance computation as a subroutine. On a Pentium II 400 MHz machine, the average query time during this precomputation was 25.0 ms. The video demonstrates that the resulting path is piecewise linearly interpolated between six torus configurations.

Tolerance queries can also be used by the planner to produce an identical path. These queries are typically faster than distance queries, although more are required in this application. On an SGI Onyx 2, use of tolerance queries sped up the overall planning time from 133 seconds to 82 seconds.

cave.mpg - 3.4 MB

Thanks to Jean-Claude Latombe and David Hsu of Stanford University for supplying us with the randomized path planner used for this example.

All visualizations created by Stefan Gottschalk.

Copyright 1999. Last modification on June 29, 1999.

Maintained by:

Geometric Algorithms for Modeling, Motion, and Animation