Method and apparatus for determining position and orientation of mechanical objects

A method for determining the position and orientation of a workpiece having at least one planar surface using a machine employing a data processing system where numerical data corresponding to a model of the workpiece, with a corresponding planar surface, is stored, comprising the steps of:

• moving a sensor according to a probing route, lying in a probing plane parallel to the planar surface of the workpiece;
• measuring coordinates of a plurality of points located on the probing route;
• determining an approximate Euclidean transformation which correlates the measured coordinates of points located on the probing route to a boundary in the model corresponding to the probing plane of the workpiece, using the coordinates of the points that are measured at an initial stage of moving the sensor;
• and
• improving the accuracy of the approximate Euclidean transformation on the basis of the coordinates of additional points measured on the probing route to obtain an improved transformation which indicates the position and orientation of the workpiece with respect to the model.

For use in connection with a machine, said machine being a machine tool or an inspection system, a method for determining the position and orientation of a workpiece in relation to a known coordinate system in order to enable the machine tool to engage such workpiece accurately or to enable proper inspection of such workpiece by the inspection system, said machine tool or said inspection system employing a data processing system where numerical data corresponding to a model of such workpiece is stored, comprising the steps of:

• measuring coordinates of a plurality of points on a boundary of the workpiece, which boundary is parallel to a machine table;
• interpolating the coordinates so as to determine a plurality of geometrical elements of the boundary;
• computing a set of possible transformations on the basis of two of the geometrical elements determined on the boundary that correlates the plurality of the geometrical elements of the boundary of the workpiece to a plurality of corresponding geometrical elements represented by a corresponding boundary of the model;
• and
• eliminating erroneous transformations from the set of possible transformations so as to determine a correct transformation which indicates the position and orientation of the workpiece with respect to the model;
• whereby the machine is controllable to engage or operate upon the workpiece with a tool, sensor or the like, on the basis of the improved transformation.

A method of digitizing coordinates of a boundary of a workpiece held in a machine comprising the steps of:

• moving a sensor along a first direction;
• changing the first direction of motion of the sensor by a specified angle after the sensor has traveled a predetermined distance;
• reversing the first direction of motion of the sensor if the sensor contacts the boundary of the workpiece;
• and
• determining coordinates of a plurality of points located on the boundary of the workpiece, said points providing digitized representation of said boundary,
• wherein after the sensor contacts a given point on the boundary, the motion of the sensor is such that the sensor starts to move so as to return to the given point, and the sensor does not return to the given point if another boundary point is encountered by the sensor before the given point.

For use in connection with a machine, said machine being a machine tool or an inspection system, a method for determining the position and orientation of a workpiece in relation to a known coordinate system in order to enable the machine tool to engage such workpiece accurately or to enable proper inspection of such workpiece by the inspection system, said machine tool or said inspection system employing a data processing system where numerical data corresponding to a model of such workpiece is stored, comprising the steps of:

• determining an approximate transformation which correlates coordinates of at least one point measured on the workpiece to at least one virtual surface represented by the model;
• measuring, by means of at least one sensor, coordinates of a plurality of points on a first surface of the workpiece;
• improving the accuracy of the approximate transformation so as to obtain an improved transformation which indicates the position and orientation of the workpiece with respect to the model, and in which a sum of squared distances from each point measured on the workpiece to the corresponding virtual surfaces represented by the model is minimized;
• and
• determining a location of a second surface on the workpiece by applying an inverse of the improved transformation to the numerical data represented by the model, so that the second surface may be used to further improve the accuracy of the improved transformation,
• whereby the machine is controllable to engage or operate upon the workpiece with a tool, sensor or the like, on the basis of the improved transformation.

For use in connection with a machine, said machine being a machine tool or an inspection system, a method of determining a geometric representation of a surface of a workpiece in order to enable the machine tool to engage such workpiece accurately or to enable proper inspection of such workpiece by the inspection system, said machine tool or said inspection system employing a data processing system, comprising the steps of:

• (a) measuring a set of coordinates of a plurality of points of the surface of the workpiece;
• (b) computing a geometric representation of the surface such that a sum of squared distances from the plurality of points of the workpiece to the geometric representation of the surface is minimized;
• (c) determining coordinates of a first point in the set which is removed from the geometric representation of the surface by a greater distance than any other point in the set;
• (d) computing a new geometric representation of the surface on the basis of a new set, which is the set of coordinates of the plurality of points without the coordinates of said first point;
• and
• (e) determining if the first point is erroneously measured on an incorrect surface by applying F-test analysis to a ratio of the sum of squared distances from the points in the set to the geometric representation of the surface and the sum of squared distances from the points of the new set to the new geometric representation of the surface;
• and
• (f) if the first point has been measured on the incorrect surface, replacing the set by the new set and replacing the geometric representation by the new geometric representation, and repeating the steps (c)-(f);
• whereby the machine is controllable to engage or operate upon the workpiece with a tool, sensor or the like, on the basis of the geometric representation.

A machine tool for precision machining and inspection of arbitrarily or approximately placed workpieces comprising:

• a CAD system where numerical data corresponding to a model of the workpiece is stored;
• sensor means for measuring coordinates of points on a plurality of surfaces of the workpiece;
• and
• data processing means for determining a Euclidean transformation which indicates the position and orientation of the workpiece so as to enable precision machining and inspection of arbitrarily or approximately placed workpieces;
• said transformation correlating a position and orientation of the plurality of points of the workpiece to a plurality of corresponding virtual surfaces represented by the model so that the sum of the squared distances from the plurality of points of the workpiece to the corresponding virtual surfaces of the model is minimized,
• wherein the means for determining comprises means for applying a transformation, which is not a Euclidian transformation, to the coordinates of the plurality of points measured on the plurality of surfaces of such workpiece or to the coordinates of the plurality of points which have been operated on by an approximate Euclidean transformation.

An apparatus for determining the position and orientation of a workpiece comprising:

• a data processing system where numerical data corresponding to a model of the workpiece is stored;
• means for determining coordinates of at least one reference point on the workpiece;
• means for determining an approximate Euclidean transformation which indicates the position and orientation of the workpiece with respect to the model on the basis of said at least one reference point;
• means for determining coordinates of a plurality of points, and providing the information regarding the correspondence between the measured points on the workpiece and virtual surfaces, represented by the model of the workpiece, to the data processing system;
• and
• means for improving the accuracy of the approximate Euclidean transformation so as to obtain an improved transformation which indicates the position and orientation of the workpiece with respect to the model, and in which the sum of the squared distances from the plurality of points of the workpiece to the corresponding virtual surfaces of the model is minimized,
• wherein the means for improving the accuracy of the approximate transformation so as to obtain the improved Euclidean transformation comprises means for modifying the approximate transformation in accordance with a result of applying a transformation, which is not a Euclidian transformation, to the coordinates of the plurality of points measured on the plurality of surfaces of such workpiece or to the coordinates of the plurality of points which have been operated on by the approximate Euclidean transformation.

An apparatus for determining the position and orientation of a workpiece having at least one planar surface comprising:

• a data processing system where numerical data corresponding to a model of the workpiece is stored;
• means for moving a sensor according to a probing route lying in a probing plane parallel to the planar surface of the workpiece;
• means for measuring coordinates of a plurality of points located on the probing route;
• means for determining an approximate Euclidean transformation which correlates the coordinates of the points measured on the probing route to a boundary in the model corresponding to a probing plane of the workpiece using the coordinates of the points that are measured at an initial stage of moving the sensor;
• and
• means for improving the accuracy of the approximate Euclidean transformation on the basis of the coordinates of additional points measured on the probing route to obtain an improved transformation which indicates the position and orientation of the workpiece with respect to the model.

An apparatus for determining a position and an orientation of a workpiece comprising:

• a data processing system where numerical data corresponding to a model of the workpiece is stored;
• means for determining coordinates of a plurality of points on a boundary of the workpiece, said boundary is parallel to a machine table;
• means for interpolating the coordinates so as to determine a plurality of geometrical elements of the boundary;
• means for computing a set of possible transformations on the basis of two of the geometrical elements determined on the boundary that correlates the plurality of the geometrical elements of the boundary of the workpiece to a plurality of corresponding geometrical elements represented by a corresponding boundary of the model;
• and
• means for eliminating erroneous transformations from the set of possible transformations.

An apparatus for digitizing coordinates of a boundary of a workpiece comprising:

• means for moving a sensor along a first direction;
• means for changing the first direction of motion of the sensor by a predetermined angle after the sensor has traveled a predetermined distance;
• means for reversing the first direction of motion of the sensor if the sensor contacts the boundary of the workpiece;
• and
• means for determining coordinates of a plurality of points located on the boundary of the workpiece,
• wherein the motion of the sensor is programmed such that after the sensor contacts a given point, the sensor starts to move so as to return to the given point, and the sensor does not return to the given point if another boundary point is encountered by the sensor before the given point.

An apparatus for digitizing and modeling geometric features of a surface of a workpiece comprising:

• a data processing system;
• means for determining a set of coordinates of a plurality of points of the surface of the workpiece;
• means for computing a geometric representation of the surface such that a sum of squared distances from the plurality of points of the workpiece to the geometric representation of the surface is minimized;
• means for determining coordinates of a first point in the set which is removed from the geometric representation of the surface by a greater distance than any other point in the set;
• means for computing a new geometric representation of the surface on the basis of a new set, which is the set of coordinates of the plurality of points without the coordinates of said first point;
• and
• means for determining if the first point is erroneously measured on an incorrect surface by applying F-test analysis to a ratio of the sum of squared distances from the points in the set to the geometric representation of the surface and the sum of squared distances from the points of the new set of the new geometric representation of the surface.

For use in connection with a machine, said machine being a machine tool or an inspection system, a method for determining the position and orientation of a workpiece in relation to a known coordinate system in order to enable the machine tool to engage such workpiece accurately or to enable proper inspection of such workpiece by the inspection system, said machine tool or said inspection system employing a data processing system where numerical data corresponding to a model of such workpiece is stored, comprising the steps of:

• measuring, by means of at least one sensor, coordinates of a plurality of points on surfaces of the workpiece;
• determining an approximate transformation which correlates the coordinates of the plurality of points of the workpiece to a plurality of corresponding virtual surfaces represented by the model;
• and
• improving the accuracy of the approximate transformation so as to obtain an improved transformation which indicates the position and orientation of the workpiece with respect to the model, and in which the sum of the squared distances from the plurality of points of the workpiece to the corresponding virtual surfaces of the model is minimized, wherein the step of improving the transformation comprising:
• determining a plane TP.sub.i, which is tangent to a virtual surface S.sub.i represented by the model, that corresponds to a surface of the workpiece where a point P.sub.i on the surface is measured, so that a point of tangency of S.sub.i and TP.sub.i is closer to p.sub.i than any other point on S.sub.i ;
• computing a rotational transformation vector r and a translational transformation vector v, such that after supplying a tangent transformation T.sub.r,v to each point p.sub.i, the sum of squared distances from each point T.sub.r,v (p.sub.i) having had the tangent transformation applied thereto, to the corresponding tangent plane TP.sub.i is minimized;
• and
• modifying the transformation by multiplying the transformation by the Euclidean transformation U.sub.r,v, which is defined by the vectors r and v;
• whereby the machine is controllable to engage or operate upon the workpiece with a tool, sensor or the like, on the basis of the improved transformation.

For use in connection with a machine, said machine being a machine tool or an inspection system, a method for determining the position and orientation of a workpiece in relation to a known coordinate system in order to enable the machine tool to engage such workpiece accurately or to enable proper inspection of such workpiece by the inspection system, said machine tool or said inspection system employing a data processing system where numerical data corresponding to a model of such workpiece is stored, comprising the steps of:

• measuring by means of at least one sensor coordinates of a plurality of points on surfaces of the workpiece;
• determining an approximate transformation which correlates the coordinates of the plurality of points of the workpiece to a plurality of corresponding virtual surfaces represented by the model;
• improving the accuracy of the transformation so as to obtain an improved transformation which indicates the position and orientation of the workpiece with respect to the model, and in which the sum of the squared distances from the plurality of points of the workpiece to the corresponding virtual surfaces of the model is minimized;
• and
• minimizing an objective function of the improved transformation so as to obtain a transformation which transforms the coordinates of the plurality of points so as to satisfy tolerance requirements of the workpiece stored in the data processing system;
• whereby the machine is controllable to engage or operate upon the workpiece with a tool, sensor or the like, on the basis of the improved transformation.

For use in connection with a machine, said machine being a machine tool or an inspection system, a method for determining the position and orientation of a workpiece in relation to a known coordinate system in order to enable the machine tool to engage such workpiece accurately or to enable proper inspection of such workpiece by the inspection system, said machine tool or said inspection system employing a data processing system where numerical data corresponding to a model of such workpiece is stored, comprising the steps of:

• measuring by means of at least one sensor, coordinates of a plurality of points on surfaces of the workpiece;
• determining an approximate transformation which correlates the coordinates of the plurality of points of the workpiece to a plurality of corresponding virtual surfaces represented by the mode;
• improving the accuracy of the approximate transformation so as to obtain an improved transformation which indicates the position and orientation of the workpiece with respect to the model, and in which the sum of the squared distances from the plurality of points of the workpiece to the corresponding virtual surfaces of the model is minimized;
• and
• performing a reliability analysis of the improved transformation so as to determine a bound of an error of a computed position and orientation of the workpiece, which computed position and orientation are represented by the numerical data corresponding to the model transformed by an inverse of the improved transformation;
• whereby the machine is controllable to engage or operate upon the workpiece with a tool, sensor or the like, on the basis of the improved transformation.

A method for determining the position and orientation of a workpiece having at least one planar surface using a machine employing a data processing system where numerical data corresponding to a model of the workpiece with a corresponding planar surface is stored, comprising the steps of:

• moving a sensor according to a probing route lying in a probing plane parallel to the planar surface of the workpiece;
• measuring coordinates of a plurality of points located on the probing route;
• determining an approximate transformation which correlates the measured coordinates of pints located on the probing route to a boundary in the model corresponding to the probing plane of the workpiece, using the coordinates of the points that are measured at an initial stage of moving the sensor;
• and
• improving the accuracy of the approximate transformation on the basis of the coordinates of additional points measured on the probing route to obtain an improved transformation which indicates the position and orientation of the workpiece with respect to the model;
• and
• locating the position of a clamp by identifying at least one point which cannot be transformed by the improved transformation to a corresponding virtual surface represented by the model.

An apparatus for determining the position and orientation of a workpiece comprising:

• a data processing system where numerical data corresponding to a model of the workpiece is stored;
• means for determining coordinates of a plurality of points on a corresponding plurality of surfaces of the workpiece;
• means for determining an approximate transformation which correlates the coordinates of the plurality of points of the workpiece to a plurality of corresponding virtual surfaces represented by the model;
• means for improving the accuracy of the approximate transformation so as to obtain an improved transformation which indicates the position and orientation of the workpiece with respect to the model, and in which the sum of the squared distances from the plurality of points of the workpiece to the corresponding virtual surfaces of the model is minimized, wherein the means for improving the accuracy comprises:
• means for determining a plane TP.sub.i which is tangent to a virtual surface S.sub.i represented by the model that corresponds to a surface of the workpiece where a point p.sub.i on the surface is measured so that a point of tangency of S.sub.i and TP.sub.i is closer to p.sub.i than any other point on S.sub.i ;
• means for computing a rotational transformation vector r and a translational transformation vector v, such that after applying a tangent transformation T.sub.r,v to each point p.sub.i the sum of squared distances from each point T.sub.r,v (p.sub.i) having had the tangent transformation applied thereto, to the corresponding tangent plane TP.sub.i is minimized;
• and
• means for modifying the transformation by multiplying the transformation by the Euclidean transformation U.sub.r,v, defined by the vectors r and v.

An apparatus for determining a position and an orientation of a workpiece comprising:

• a data processing system where numerical data corresponding to a model of the workpiece is stored;
• means for determining coordinates of a plurality of points on a corresponding plurality of surfaces of the workpiece;
• means for determining an approximate transformation which correlates the coordinates of the plurality of points of the workpiece to a plurality of corresponding virtual surfaces represented by the model;
• means for improving the accuracy of the approximate transformation so as to obtain an improved transformation which indicates the position and orientation of the workpiece with respect to the model, and in which the sum of the squared distances from the plurality of points of the workpiece to the corresponding virtual surfaces of the model is minimized;
• and
• means for performing a reliability analysis of the improved transformation so as to determine a bound of an error of a computed position and orientation of the workpiece, which computed position and orientation is the numerical data corresponding to the model transformed by an inverse of the improved transformation.

An apparatus for determining the position and orientation of a workpiece comprising:

• a data processing system where numerical data corresponding to a model of the workpiece is stored;
• means for determining coordinates of a plurality of points on a corresponding plurality of surfaces of the workpiece;
• means for determining an approximate transformation which correlates the coordinates of the plurality of points of the workpiece to a plurality of corresponding virtual surfaces represented by the model;
• means for improving the accuracy of the approximate transformation so as to obtain an improved transformation which indicates the position and orientation of the workpiece with respect to the model, and in which the sum of the squared distances from the plurality of points of the workpiece to the corresponding virtual surfaces of the model is minimized;
• and
• means for minimizing an objective function of the improved transformation so as to obtain a transformation which transforms the coordinates of the points so as to satisfy tolerance requirements of the workpiece stored in the data processing system.

A method for determining the position and orientation of a workpiece using a machine employing a data processing system where numerical data corresponding to a model of the workpiece is stored, comprising the steps of:

• measuring, by means of at least one sensor, coordinates of a plurality of points on surfaces of the workpiece;
• determining an approximate transformation which correlates the coordinates of the plurality of points of the workpiece to a plurality of corresponding virtual surfaces represented by the model;
• improving the accuracy of the approximate transformation so as to obtain an improved transformation which indicates the position and orientation of the workpiece with respect to the model, and in which the sum of the squared distances from the plurality of points of the workpiece to the corresponding virtual surfaces of the model is minimized;
• modifying tool path data, stored in the data processing system for machining the workpiece, using the improved transformation.

An apparatus for determining the position and orientation of a workpiece comprising:

• a data processing system where numerical data corresponding to a model of the workpiece is stored;
• means for determining coordinates of a plurality of points on a corresponding plurality of surfaces of the workpiece;
• means for determining an approximate transformation which correlates the coordinates of the plurality of points of the workpiece to a plurality of corresponding virtual surfaces represented by the model;
• means for improving the accuracy of the approximate transformation so as to obtain an improved transformation which indicates the position and orientation of the workpiece with respect to the model, and in which the sum of the squared distances from the plurality of points of the workpiece to the corresponding virtual surfaces of the model is minimized;
• and
• means for modifying tool path data, stored in the data processing system for machining the workpiece, using the improved transformation.