Least-squares fitting of analytic primitives on a GPU

Metrology systems take coordinate information directly from the surface of a manufactured part and generate millions of (xx, yy, zz) data points. The inspection process often involves fitting analytic primitives such as sphere, cone, torus, cylinder, and plane to these points, which represent an object with the corresponding shape. Typically, a least-squares fit of the parameters of the shape to the point set is performed. The least-squares fit attempts to minimize the sum of the squares of the distances between the points and the primitive. The objective function, however, cannot be solved in the closed form, and numerical minimization techniques are required to obtain the solution. These techniques as applied to primitive fitting entail iteratively solving large systems of linear equations generally involving arithmetic-intensive operations. The current problem faced in in-process metrology is the large computational time for the analysis of these millions of streaming data points. This paper presents a framework to address the bottleneck using a graphical processing unit (GPU) to optimize operations and obtain significant gain in computation time.