Real-time interference analysis between a tool and an environment

In applications such as haptic rendering, NC Verification and CAM, it is of ten necessary to rapidly detect and correct collision between a known tool, such as a cutting tool, and an arbitrary environment, such as the workpiec e to be machined. In these situations, the tool can be manually pre-defined , but the workpiece needs a general representation; and careful fulfillment of these requirements enables extremely rapid performance. We describe an algorithm and representations for rapidly detecting and correcting collisio n between a manually pre-defined tool and an arbitrary workpiece. For the t ool, we prescribe a form of CSG consisting of implicit equations separated by binary space partitions. This representation can be enhanced to also yie ld depth information and exit vector information for many useful solids. Th e user must hand-construct the tool using this representation. For the envi ronment, we use a cloud of over 10,000 points. This is a general representa tion. The collision between tens of thousands of points and the implicit re presentation can be accelerated with a bounding box hierarchy. We show that we can compute collision and correction information at the rate of 1000 ti mes a second, making it possible to perform force control for haptics using the collision detection algorithm in the real-time loop. (C) 2001 Elsevier Science Ltd. All rights reserved.