Interactive Continuous Collision Detection for NonConvex Polyhedra


AbstractWe present a highly interactive, continuous collision detection algorithm for rigid, general polyhedra. Given initial and final configurations of a moving polyhedral model, our algorithm creates a continuous motion with constant translational and angular velocities, interpolating the initial and final configurations of the model. Then, our algorithm reports whether the model under the interpolated motion collides with other rigid polyhedral models in environments, and if it does, the algorithm reports its first time of contact (TOC) with the environment as well as its associated contact features at TOC.




Benchmarking Scenarios1. Santa vs Thin Board: Given two configurations of q_{0},
q_{1}
of a highly nonconvex Santa model with 37888 triangles, separated by
approximately 5 times the bounding box size of Santa, a board (12 triangles) is
initially located below q_{0}.
By varying the position of the board toward q_{1},
we calculate t_{TOC}
of the Santa model when it tries to reach from q0 to q_{1}. 2. Bunny vs Bunny: Each bunny consists of 69664
triangles. As shown in the figure, one of the bunny is shot from a random
configuration q_{0} (red) toward a random configuration q_{1}
(blue) against a fixed bunny (yellow) with constant translational and angular
velocities. We perform this test for more than 200 trials, and between [0,100]
steps of the test trial, q_{1} has only translation relative to q_{0}.
Afterwards, plus the translational motion, q1 has
π/3 rotation around X axis 3. Torusknot vs Torusknot: It is similar to the bunny vs bunny benchmarking scenario.. However, instead, we use torusknots in different complexities, 2880, 11520 and 34560 triangles, for benchmarking models. 4. Rigid Body Dynamics for Bunnies: Using HAVOK, we
perform rigid body dynamics to simulate the falling of a red bunny against a
blue one, each consisting of 26K triangles, due to gravity. Each simulation step
provides q_{0}, q_{1} of the blue moving bunny, and we plug
these into our CCD algorithm and measure the performance. Moreover, in order to
create 5. Rigid Body Dynamics for Rings: We conduct similar dynamics experiments for rings consisting of 10K triangles each.


