The University of Edinburgh -
Division of Informatics
Forrest Hill & 80 South Bridge

PhD Thesis #8403

Title:Modelling Solids in Motion.
Date: 1984
Abstract:This thesis is concerned with the problem of producing and using a computer model that describes a set of solid objects in motion; in particular, I considered the efficient solution to the clash detection problem as encountered in the field of robotics. The r-set model of three-dimensional solid objects is taken and extended to four dimensions to give a mathematical basis for the modelling of objects in motion, and I show that such models can be constructed with relative ease when working in a constructive solid geometry (CSG) framework. The clash detection problem is the problem of deciding whether a collision will occur between a set of moving objects, and I show that this is equivalent to deciding whether any pair of four-dimensional models intersect. Three basic methods are considered for performing clash detection using a computer. The first tackles the problem by repeatedly testing for static interference between objects over many values of time. The second considers the four-dimensional models of the objects in motion directly, and performs an interference test between these. The third method creates a new set of three-dimensional models by sweeping the original objects through space, and then performs a test for interference between these. The first method has been implemented in my CSG based geometric modelling system, robmod, and includes several refinements based on the calculation of the minimum distance between objects. The second method has also been implemented for a certain class of allowable motions, and both robmod and the implementations are described herein. All three methods rely on being able to tell whether a pair of multidimensional sets intersect; this problem has been examined in some detail and I describe a new, efficient solution that I have developed.

[Search These Pages] [DAI Home Page] [Comment]