A Data Structure for Analyzing Collisions of Moving Objects

Computer systems that simulate dynamic systems of bodies require the detection and analysis of collisions between moving bodies. For a restricted class of parameterized objects, collision detection is relatively simple. However, when a simulation system uses a solid modeler to obtain objects with arbitrarily complex topology, detecting collisions efficiently between two moving objects becomes difficult. This paper presents a new data structure for analyzing the spatial relationship of two objects. Given the objects as boundary representations (B-reps), a spatial index is constructed for the B-reps which allows fast edge and vertex classifications to be performed. This data structure solves the collision detection problem efficiently, and uses, moreover, purely solid modeling techniques. 1Tltis work has been supported in par ~ by NSF Grant CCR-86-19817 to Purdue University.