Computer representations of machined parts for automatic inspection

A comparison is made between octrees, which are regular decompositions of volumes, and new, irregular decompositions called R-trees. This comparison is made within the context of the volume intersection problems that might be associated with an automatic inspection system. The results show that the irregular decomposition is independent of object position and can provide a more space efficient encoding for certain shapes. However, detecting intersections between R-trees requires an algorithm of greater complexity due to the irregularity of the decomposition.

Algorithms are given for obtaining tree decompositions from a hierarchic relational model of a volume. Among these algorithms is a procedure for finding the minimal enclosing rectangular parallelepiped of a boundary representation, and a generalization of the point-in-polygon algorithm to boundaries on curved surfaces. Both of these algorithms have computation times that are proportional to the total number of components of the boundary's representation.