Programming Research Group Technical Monograph PRG-85

Stephen Cameron

July 1990, 49 pages, ISBN 0-902928-64-3

Testing for the existence of intersections is an important part of algorithms for interference detection, collision detection, and the like. We describe three techniques that can be used to implement an efficient intersection detection routine when entities are described constructively; that is, as set combinations of primitive entities. All three techniques are described in a domain where constructive solid geometry is the principal entity description used, although their use in boundary representation schemes are also discussed. The first technique, called S-bounds, is a method of reasoning about where intersections may be taking place; in practise it is fast, and often sufficient. S-bounds can also be used as a general constraint manipulation method over Boolean algebras. The second technique is based on spatial subdivision, and is used mainly to improve the speed of the intersection test. The third technique is employed only on the regions of space that are left by the first two techniques; it is a specialisation of the "classical" technique of generate-and-test. The combination of these techniques has been implemented as an intersection detection routine which shows a speed-up over the "classical" algorithm of about two orders of magnitude.