Collision detection of deformable polyhedral objects via inner-outer ellipsoids

For deformable polyhedral objects undergoing vertex repositioning, this paper develops a collision detection procedure by virtue of inner-outer ellipsoidal bounds of deformation. A new design of collision detector with tunable accuracy, defined by a linear inequality for easily computed and updated parameters, is presented. It utilizes and tracks a measure of proximity/penetration between two objects in the direction of shortest path between two inner ellipsoids. Moreover, it does not incur additional computational expenses since no costly updating process and heavy dependence on the geometric details of the deformed polyhedral objects is needed, so that the efficiency is comparable to that of rigid cases. Numerical experiments on pairs of randomly scaling convex polyhedra, lacking geometry coherence, demonstrated that the efficiency of the new collision detector is comparable to the rigid case.