Accessibility analysis for automatic inspection in CMMs by using bounding volume hierarchies

Accessibility analysis represents one of the most critical tasks in inspection planning. This analysis determines those probe orientations that can touch an inspection point without collision. This paper presents a methodology based on part discretization and the application of space partitioning techniques (kd-tree) in order to reduce the number of intersection tests between probe and part. A STL model has been used for discretizing the inspection part in a set of triangles, which permits the application of the developed system to any type of part, regardless of its shape and its complexity. Likewise, a recursive ray traversal algorithm has been used in order to speed up the traversal of the kd-tree hierarchical structure and to calculate exclusively the intersection of each probe orientation with those part triangles that can potentially interfere with it. In a further step of the analysis, the real geometry of the probe has been considered. Hence, a simplified model has been developed for each probe component (column, head, touch probe, stylus and tip) using different basic geometrical shapes. Finally, collision-free probe orientations are clustered for minimizing the orientation changes during the inspection process. Furthermore, the applied algorithm allows for determining different valid combinations of clusters. The developed system was applied to two example parts in order to prove that this methodology is adequate for the solution of real cases.