Method and apparatus for determining position and orientation of mechanical objects

• US 5,208,763 A
• Filed: 09/14/1990
• Issued: 05/04/1993
• Est. Priority Date: 09/14/1990
• Status: Expired due to Term

• Current Assignee: New York University
• Original Assignee: New York University
• Inventors: Hong, Jiawei, Tan, Xiaonan
• Primary Examiner(s): Lall, Parshotam S.
• Assistant Examiner(s): ZANELLI, MICHAEL J
• Application Number:
  US07/582,582
• Time in Patent Office: 963 Days
• Field of Search: 364/551.01, 364/559, 364/560, 364/577, 364/578, 364/579, 364/580, 364/474.01, 364/474.02, 364/474.05, 364/474.15, 364/474.22, 364/474.23 , 364/474.24, 364/474.25, 364/474.31, 364/474.34, 364/474.35, 364/474.36, 364/474.37, 364/191, 364/551.02, 364/571, 364/513, 364/148 , 364/150, 364/167.01, 33/503, 33/504, 401/9, 401/10, 401/16
• US Class Current: 702/95
• CPC Class Codes: G05B 19/402 characterised by control arrangements for positioning, e.g. centring a tool relative to a hole in the workpiece, additional detection means to correct position G05B19/19 takes precedence
• CPC Class Codes: G05B 2219/37194 Probe work, calculate shape independent of position, orientation, best fit
• CPC Class Codes: G05B 2219/37197 From measured data derive form, roundness, orientation, parallel, straightness
• CPC Class Codes: G05B 2219/37198 Machine as measuring station, use tool or probe, in process incycle
• CPC Class Codes: G05B 2219/37205 Compare measured, vision data with computer model, cad data
• CPC Class Codes: G05B 2219/37439 Computer assisted inspection, cad interactive with manual commands
• CPC Class Codes: G05B 2219/37496 Root mean square
• CPC Class Codes: G05B 2219/50152 Align axis cylinder, tube with rotation axis machine
• CPC Class Codes: G06T 2207/30164 Workpiece; Machine component
• CPC Class Codes: G06T 7/75 involving models
• CPC Class Codes: G06V 10/242 by image rotation, e.g. by 90 degrees

Abstract

A computer-controlled machine equipped with sensors determines position and orientation of a workpiece, with respect to a model of the workpiece, which is stored in a data processing system interfaced to the machine, by measuring coordinates of points on the surfaces of the workpiece and determining a transformation in which a sum of squared distances from the points to the corresponding surfaces of the model is minimized. The determined transformation is improved so as to satisfy the specified tolerances.

Claims

1. 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 at least one reference point on the workpiece;

determining an approximate Euclidean transformation which indicates the position and orientation of such workpiece with respect to the model on the basis of said at least one reference point;

measuring, by means of at least one sensor, coordinates of a plurality of points on a plurality of surfaces of the workpieces such that the information regarding the correspondence between the measured points on the workpiece and virtual surfaces, represented by the model of the workpiece, is provided to the data processing system; and

improving the accuracy of the approximate transformation so as to obtain an improved Euclidean 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 approximate transformation so as to obtain the improved Euclidean transformation comprises 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;

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.

2. The method of claim 1 further comprising the steps of:

selecting certain of the virtual surfaces represented by the model; and

wherein the coordinates of the plurality of the points are determined by moving a sensor to such points when the surface of the workpiece upon which they lie corresponds to the selected virtual surface of the model.

3. The method of claim 1 wherein the step of improving the transformation comprises:

determining a plane TP_i which is tangent to a virtual surface S_i represented by the model that corresponds to a surface of the workpiece where a point p_i on the surface is measured so that a point of tangency of S_i and TP_i is closer to p_i than any other point on S_i ;

computing a rotational transformation vector r and a translational transformation vector v, such that after applying a tangent transformation T_r,v to each point p_i, the sum of squared distances from each point T_r,v (p_i) having had the tangent transformation applied thereto, to the corresponding tangent plane TPi is minimized; and

modifying the transformation by multiplying the transformation by the Euclidean transformation U_r,v, which is computed on the basis of the vectors r and v.

4. The method of claim 3 wherein the step of computing the transformation vectors further comprises selecting a closest tangent homing transformation T_r,v if the tangent transformation can not be computed uniquely, such that the sum of squared distances from each point T_r,v (p_i), having the closest tangent transformation applied thereto, to a corresponding point U(p_i), having the transformation U applied thereto, is minimized.

5. The method of claim 1 further comprising the step of 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.

6. The method of claim 5 wherein the step of minimizing the objective function comprises:

obtaining a minimum gradient direction data by computing a derivative of a parametric representation of the improved transformation with respect to each parameter of the representation; and

applying a Golden Section search method to the objective function so as to determine a minimum value of the function in the gradient direction.

7. The method of claim 6 further comprising the steps of:

computing new tolerance requirements by multiplying each value of the tolerance requirements by a narrowing factor variable;

determining the transformation which transforms the coordinates of the points so as to satisfy the new tolerance requirements; and

assigning a new value to the narrowing factor variable.

8. The method of claim 1 further comprising the step of 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.

9. The method of claim 8 wherein the step of performing the reliability analysis comprises performing a translational reliability analysis.

10. The method of claim 9 wherein the step of performing the translational reliability analysis comprises:

simulating a translation of the points of the workpiece along a specified direction;

computing an increase in a sum of squared distances from the points of the workpiece to the corresponding virtual surfaces represented by the model during the translation; and

applying F-test analysis to a ratio of a sum of squared distances computed after simulating the translation and a sum of squared distances computed before simulating the translation so as to determine a bound of a translational error of the improved transformation.

11. The method of claim 8 wherein the step of performing reliability analysis comprises performing a rotational reliability analysis.

12. The method of claim 11 wherein the step of performing rotational reliability analysis comprises:

simulating a rotation of the points about a specified axis;

computing an increase in a sum of squared distances from the points of the workpiece to the corresponding virtual surfaces during rotation; and

applying F-test analysis to the ratio of a sum of squared distances computed after simulating the rotation and a sum of square distances computed before simulating the rotation so as to determine a bound of an angular error of the improved transformation.

13. The method of claim 1 further comprising the step of modifying tool path data, stored in the data processing system for machining the workpiece, using the improved transformation.

14. The method of claim 1 further comprising:

computing a z-axis transformation, using the improved transformation, which correlates a z-direction of the workpiece with a z-axis of the model;

automatically moving a machine table on which a workpiece is placed, so as to align the z-direction of the workpiece with the z-axis of the model; and

modifying the tool path data, stored in the data processing system for machining the workpiece, using a transformation which is a product of the inverse of the improved transformation and the z-axis transformation.

15. 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.

16. The method of claim 15, further comprising the step of locating 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.

17. 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.

18. The method of claim 17 wherein the step of eliminating erroneous transformations comprises eliminating transformations which transform the coordinates of a certain point in the set inside the corresponding boundary represented by the model such that transformed coordinates of the certain point are removed from the corresponding boundary represented by the model by a distance greater than a predetermined constant.

19. The method of claim 18 further comprising the step of locating a clamp by measuring coordinates of a point, which, under each transformation in the set of possible transformations, is transformed outside the corresponding boundary represented by the model to a distance greater than the predetermined constant.

20. 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.

21. 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.

22. A method of claim 21 wherein the step of improving the transformation comprises

determining a plane TP_i which is tangent to a virtual surface S_i represented by the model that corresponds to a surface of the workpiece where a point p_i on the surface is measured so that a point of tangency of S_i and TP_i is closer to p_i than any other point on S_i ;

computing a rotational transformation vector r and a translational transformation v, such that after applying a tangent transformation T_r,v to each point p_i, the sum of squared distances from each point T_r,v (p_i) having had the tangent transformation applied thereto, to the corresponding tangent plane TP_i is minimized; and

modifying the transformation by multiplying the transformation by the Euclidean transformation U_r,v, which is computed on the basis of the vectors r and v.

23. The method of claim 21 further comprising t he step of 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.

24. 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.

25. 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.

26. 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.

27. The apparatus of claim 26 further comprising:

means for selecting certain of the virtual surfaces represented by the model;

wherein the coordinates of the plurality of the points are determined by moving a sensor to such points when the surface of the workpiece upon which they lie corresponds to the selected virtual surface of the model.

28. The apparatus of claim 26 wherein the means for improving the transformation comprises:

means for determining a plane TP_i which is tangent to a virtual surface S_i represented by the model that corresponds to a surface of the workpiece where a point p_i on the surface is measured so that a point of tangency of S_i and TP_i is closer to p_i than any other point on S_i ;

means for computing a rotational transformation vector r and a translational transformation vector v, such that after applying a tangent transformation T_r,v to each point p_i, the sum of squared distances from each point T_r,v (p_i) having had the tangent transformation applied thereto, to the corresponding tangent plane TP_i is minimized; and

means for modifying the transformation by multiplying the transformation by the Euclidean transformation U_r,v, which is computed on the basis of the vectors r and v.

29. The apparatus of claim 26 further comprising 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.

30. The apparatus of claim 29 wherein the means for minimizing the objective function comprises:

means for obtaining a minimum gradient direction data by computing a derivative of a parametric representation of the improved transformation with respect to each parameter of the representation; and

means for applying a Golden Section search method to the objective function so as to determine a minimum value of the function in the gradient direction.

31. The apparatus of claim 26 further comprising 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.

32. The apparatus of claim 31 comprising:

means for simulating a translation of the points of the workpiece along a specified direction;

means for computing an increase in a sum of squared distances from the points of the workpiece to corresponding virtual surfaces represented by the model during the translation;

means for applying F-test analysis to a ratio of a sum of squared distances computed after simulating the translation and a sum of squared distances computed before simulating the translation so as to determine a bound of a translational error of the improved transformation;

means for simulating a rotation of the points about a specified axis;

means for computing an increase in a sum of squared distances from the points of the workpiece to the corresponding virtual surfaces during rotation; and

means for applying F-test analysis to the ratio of a sum of squared distances computed after simulating the rotation and a sum of square distances before simulating the rotation so as to determine a bound of an angular error of the improved transformation.

33. The apparatus of claim 26 further comprising means for modifying tool path data, stored in the data processing system for machining the workpiece, using the improved transformation.

34. The apparatus of claim 26 further comprising:

means for computing a z-axis transformation using the improved transformation, which correlates a z-direction of the workpiece with a z-axis of the mode; and

means for automatically moving a machine table on which a workpiece is placed, so as to align the z-direction of the workpiece with the z-axis of the model;

means for modifying the tool path data, stored in the data processing system for machining the workpiece, using a transformation which is a product of the inverse of the improved transformation and the z-axis transformation.

35. 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.

36. 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.

37. 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.

38. 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.

39. 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_i, which is tangent to a virtual surface S_i represented by the model, that corresponds to a surface of the workpiece where a point P_i on the surface is measured, so that a point of tangency of S_i and TP_i is closer to p_i than any other point on S_i ;

computing a rotational transformation vector r and a translational transformation vector v, such that after supplying a tangent transformation T_r,v to each point p_i, the sum of squared distances from each point T_r,v (p_i) having had the tangent transformation applied thereto, to the corresponding tangent plane TP_i is minimized; and

modifying the transformation by multiplying the transformation by the Euclidean transformation U_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.

40. 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.

41. 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.

42. 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.

43. 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_i which is tangent to a virtual surface S_i represented by the model that corresponds to a surface of the workpiece where a point p_i on the surface is measured so that a point of tangency of S_i and TP_i is closer to p_i than any other point on S_i ;

means for computing a rotational transformation vector r and a translational transformation vector v, such that after applying a tangent transformation T_r,v to each point p_i the sum of squared distances from each point T_r,v (p_i) having had the tangent transformation applied thereto, to the corresponding tangent plane TP_i is minimized; and

means for modifying the transformation by multiplying the transformation by the Euclidean transformation U_r,v, defined by the vectors r and v.

44. 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.

45. 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.

46. 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.

47. 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.