| Abstract: | Interference detection is a useful technique, but it is also generally time-consuming. In this paper, a new type of interference detection algorithm is proposed for real-time interference detection. The algorithm first rasterizes the projection of the target objects and calculates the z-values, just as done by the z-buffer visible surface algorithm. For interference detection, all z-values and pointers to the corresponding faces of objects are saved in a z-list for each pixel. Sorting the z-list against the z-values allows the detection of overlapping objects in the z-direction at each pixel position and, thus, finds interfering faces by referring to the face pointers in the z-list. The algorithm is simple and easy to implement. Its computational complexity is directly proportional to the number of polygons, and, in addition, standard graphics hardware can be used to greatly accelerate execution. Another advantage is that the algorithm can be applied to all ‘ray-traceable’ objects, including algebraic surfaces, and procedurally defined objects; traditionally these were not suitable subjects for interference detection. The algorithm is implemented on a graphics workstation using a standard graphics library. Interference detection at a practical interaction speed is achieved for complicated objects such as polyhedra with thousands of polygons. The algorithm can be used in two ways: for inexpensive interference detection, and as an efficient culling method for more precise collision/interference detection algorithms. |
