We 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.
Our algorithm is a generalization of conservative advancement to general polyhedra. In this approach, we calculate the motion bound of a moving polyhedral model and estimate the TOC based on this bound, and advance the model by the current TOC estimate. We iterate this process until the inter-distance between the moving model and the other objects in the environments becomes below a user defined distance threshold. We pose the problem of calculating the motion bound as a linear programming and provide an efficient, novel solution based on the simplex method. Moreover, we also provide a hierarchical advancement technique based on bounding volume traversal tree to generalize the conservative advancement for non-convex models.
Our algorithm is relatively simple to implement and has very small computational overhead of merely performing discrete collision detection multiple times. We extensively benchmarked our algorithm in different scenarios, and in comparison to other known continuous collision detection algorithm, the performance improvement ranges by a factor of 1.2 ~ 150 depending on benchmarking scenarios. Moreover, our algorithm can perform CCD at 105 ~ 51546 frames per seconds on a 3.6 GHz Pentium 4 PC for complex models consisting of 10K ~ 70K triangles.
1. Santa vs Thin Board: Given two configurations of q0, q1 of a highly non-convex Santa model with 37888 triangles, separated by approximately 5 times the bounding box size of Santa, a board (12 triangles) is initially located below q0. By varying the position of the board toward q1, we calculate tTOC of the Santa model when it tries to reach from q0 to q1.
In the figure, the red, blue, and green Santas denote the Santa model at configurations, q0, q1, q(tTOC), respectively.
plus π/3 rotation around Y axis relative to q0.
3. Torusknot vs Torusknot: It is similar to the bunny vs bunny benchmarking scenario.. However, instead, we use torus-knots in different complexities, 2880, 11520 and 34560 triangles, for benchmarking models.
artificial interpenetration at q1 from this simulation (the simulation itself is collision-free all the time), we slightly modify the q1 before impact, and thus we can invoke our CCD algorithm to find tTOC.
5. Rigid Body Dynamics for Rings: We conduct similar dynamics experiments for rings consisting of 10K triangles each.