This thesis presents a real-time collision detection methodology between a pair of convex polyhedral objects undergoing fast rotational and translational motion. The method models the collision detection problem as a linear program. In addition to robustness and speed, the mathematical programming approach offers other advantages such as simpler data structures, and it naturally address situations such as high speed (inter-frame) collisions. Inter-frame collision is ignored by other known collision detection algorithms. Yet, cases such as flight simulations, miUtary training, or high-speed machining inter-frame colUsions are frequently experienced due to existence of fast moving objects. The collision detection technique presented in this thesis naturally addresses the inter-frame collisions.

The strength of developed approach is demonstrated by solving the generated linear programs using a primal-dual interior point method. The method can detect collisions between multiple object pairs. Since interior point method solves primal and dual models simultaneously, dual slack variables gives the closest features from each objects. Without an extra computational expense, in each frame, problem size is reduced. This saves significant amount of time when checking collision between objects with large number of vertices. The objects are specified by a set of vertices, and movements specified by a set of global translation and rotation matrices generated through any virtual reality environment.

Experimental results show that mathematical programming approaches offer substantial advantages in speed and robustness, when compared with two well known toolkits for this problem:​ I-COLLIDE and SOLID, which provide easy to use public domain access for two of the most popular algorithms — Lin Canny (LC) closest feature algorithm and Enhanced Gilbert Johnson and Keerthi (GJK) algorithm. The collision detection technique introduced in this thesis requires vertex information of objects as an only input. Unlike other popular techniques, it does not require a database to trace adjacency information of vertices. Therefore, memory usage in this technique is more efficient comparing to other techniques mentioned in this thesis.