Course of motion determination

The present invention relates to a method of determining a course of relative motion between an artefact and a device for interacting with the artefact, such as the course of motion of a measurement device mounted on a positioning apparatus for measuring an artefact. In particular, the invention relates to a method of optimised course of motion generation.

In particular the invention is suitable for a measurement apparatus mounted on coordinate positioning apparatus which can vary both the position and orientation of the measurement apparatus. The coordinate positioning apparatus may comprise multiple components, for example an articulating probe head capable of rotational motion about one or more axes, mounted on a coordinate positioning apparatus such as a coordinate measuring machine (CMM), machine tool or the like. The coordinate positioning apparatus may also comprise a single component, such as a manual coordinate measuring arm, inspection robot etc.

It is common practice after workpieces have been produced, to inspect them on a CMM or other type of coordinate positioning apparatus having a quill onto which a measurement probe is mounted which can be driven in three orthogonal directions X,Y,Z within a working volume of the machine.

US Patent No. 5,189,806 describes an articulating probe head capable of orientating a probe with two rotational degrees of freedom to enable the probe to be used in an operation for scanning the surface of workpieces. In general such a probe head includes two rotary drive mechanisms which enable a probe to be orientated about two substantially orthogonal rotary axes. Such an articulating probe head may be mounted on the quill of a CMM to enable the probe tip to be positioned in 5 degrees of freedom (i.e. 3 linear degrees of freedom provided by the CMM and 2 rotary degrees of freedom provided by the articulating probe head).

When a workpiece is to be measured by the probe, the measurement path along which the measurement device will move must be programmed. Measurement paths may be planned manually, typically through interpretation of CAD drawings, or by operators using software to apply measurements to features from geometrical, e.g. CAD, models of a workpiece to be measured.

Two known types of CAD data are boundary representation (B-Rep) and polygonal modelling (also known as mesh modelling). A B-rep is a method for representing shapes using their limits. A solid can be a collection of connected surface elements, representing the boundary between solid and non solid. B-rep models are comprised of two parts: topology and geometry. Topology describes geometric connectivity through a classification of items. The main topology items are faces described as bounded areas of a surface, edges described as bounded curvilinear sections and discrete three dimensional points in space. The advantage of such parametric model formats is that by referencing this. topology their surface descriptions can be actively used in measurement planning.

Polygonal or mesh modelling is another approach for modelling objects by representing or approximating their surfaces using polygons (e.g. triangles). The basic object used in polygonal modelling is a vertex, where a vertex of a polygon is the point of intersection of two polygon edges. Two vertices connected by a straight line become an edge. Three vertices, connected to each other by three edges, define a triangle. Polygonal modeling describes the surface of a workpiece as a collection of polygons (e.g. polygon file format PLY) and often as triangles (e.g. STL, stereolithography format, STL). These formats have the disadvantage that they do not hold parameterised information.

The invention provides a method for generating from a geometric model of an artefact and a geometric model of a tool for interacting with artefact a relative course of motion between the artefact and tool device along an interaction path so

as to comply with one or more optimisation criteria.

According to a first aspect of the invention there is provided a computer- implemented method for determining a course of motion between an artefact and device for interacting with the artefact that are moveable relative in at least one linear and one rotational degree of freedom, the method comprising: receiving geometric data representing the artefact; receiving geometric data representing the device; and determining, from the geometric data, how the device and artefact can be oriented relative to each other along an interaction path so as to comply with one or more optimisation criteria.

Using geometric data of the artefact and of the device itself to automatically determine how to relatively orient the device and artefact in the at least one rotational degree of freedom along the interaction path can improve the performance of an operation. Furthermore, as the computer program determines the relative angular orientation along the interaction path, no input or guidance from the user is required.

The method of the present invention can be used to assess the course of motion the device and/or artefact will take during an actual operation. This assessment can occur prior to an actual operation.

Preferably the device is moveable relative to the artefact. Preferably, the device is moveable in the at least one linear and at least one rotational degree of freedom. Preferably the method comprises determining, from the geometric data, how the device can be oriented in the at least one rotational degree of freedom, along an interaction path so as to comply with one or more optimisation criteria.

Optionally, the method can comprise generating course of motion data describing the relative orientation of the device and artefact. The course of motion data can be used, for example, during an operation to control the relative orientation of a

device and artefact whilst it is interacting with an artefact. Preferably, the data is used by a controller for automatically controlling the relative orientation of the device and artefact in accordance with the control of motion data. The data can comprise coordinate position information. The data can comprise data which can be used by a controller for determining the angle at which the device is to be positioned about the at least one rotational axis.

As will be understood, determining how the device and artefact can be relatively oriented along an interaction path so as to comply with one or more optimisation criteria can occur prior to an actual interaction operation beginning. Accordingly, this can occur as part of a planning stage of an operation. Optionally, this can be performed during an actual operation. Accordingly, the actual operation could begin before the entire course of motion is determined.

The method could comprise outputting the course of motion data. The course of motion data could be output to a controller of a positioning device on which a device or artefact can be mounted. The method could comprise storing the course of motion data in a memory device. The method could further comprise controlling the motion of at least one of a device and artefact mounted on a positioning apparatus according to the course of motion data. The generation of the course of motion data and the controlling the motion of at least one of a device and artefact according to the course of motion data could be performed by the same computer device. Optionally they are performed by separate computer devices. The method could comprise displaying the course of motion data. For instance the course of motion data could be displayed on a visual display unit.

The method can be used to determine a fixed orientation, that is an orientation which does not vary along the interaction path, so as to comply with one or more optimisation criteria. Preferably the method comprises determining how to manipulate the relative orientation between the device and artefact as they relatively move along the interaction path in order to comply with the one or more

optimisation criteria. Accordingly, the method can be used to determine, prior to or during an operation, how to vary relative orientation of the device and artefact whilst the device and artefact relatively move along an interaction path. This is particularly useful when determining the course of motion for a device and artefact which can actively be relatively reoriented during movement along an interaction path. For example, this is particularly useful when determining the course of motion of a device and artefact that can be relatively reoriented without the need for interaction with a reorientation device.

Accordingly, preferably the relative orientation of the device and artefact is not to be fixed along the interaction path. Rather, preferably their relative orientation is to be varied dynamically along the interaction path.

As will be understood, geometric data can comprise dimension data. Geometric data can comprise shape data. Preferably the geometric data comprises three- dimensional ("3D") data. Accordingly, the geometric data can be 3D models of the artefact and device. Geometric data can comprise position data. The method can comprise retrieving the geometric data. For instance, the geometric data could be retrieved from a memory device. The geometric data could be obtained from a prior obtained measurement of a reference artefact. The geometric data could be generated by a user. For instance, the geometric data can be computer-aided design ("CAD") data. For example the geometric data can be a boundary representation of the artefact. Optionally, the geometric data is a polygonal model of the artefact. As will be understood, the received geometric data of the artefact and device can be combined in a common coordinate frame.

As will be understood the geometric data could be a true representation of what it is describing. Optionally, the geometric data could be an abstract representation of what it is describing. This is especially the ease for the geometric data describing the device. For example, the device geometric data could be an abstract representation of the shape of the device. For instance, even though the

device might be an irregular shape, the geometric data could describe the device using regular shape information. For instance, the geometric data could describe the device as one or more regular shapes. For example, the geometric data could describe the device as at least one sphere. For example, the geometric data could describe the device as at least one cylinder. Taking a contact measurement probe for a particular example, the probe head and/or body could for instance be represented as a sphere, the stylus as a cylinder and the tip as a sphere.

Preferably the method is for generating a course of motion of a device and artefact that are relatively moveable in at least two linear degrees of freedom, more preferably three linear degrees of freedom. Preferably the linear degrees of freedom are perpendicular to each other. Preferably the method is for generating a course of motion of a device and artefact that are relatively moveable in at least two rotational degrees of freedom. Preferably the at least two rotational degrees of freedom are about two substantially perpendicular axes. Devices which are moveable in three degrees of freedom and two rotational degrees of freedom are commonly referred to in the metrological industry as "five-axis" devices. Accordingly, the course of motion data can describe the relative orientation of the device and artefact about at least two axes. However, as will be understood, the invention is not limited to such systems and can be used to determine the course of motion of a device and artefact that are relatively moveable through much more degrees of freedom, for instance through three, four or more rotational and/or linear degrees of freedom.

The device could be a tool for machining the artefact. For instance, the tool could be a drilling, milling or grinding tool.

The device could be a measurement device. The measurement device could be a measurement probe. The measurement probe could be for measuring the dimensions of the artefact. Suitable measurement probes include contact probes.

As will be understood, contact probes typically have a contact tip for interacting

with the artefact to be measured. Contact between the tip and artefact being detectable by the measurement probe. Suitable measurement probes include touch-trigger probes and scanning probes. Suitable measurement probes also include non-contact probes. For instance, the measurement probe could be an inductance probe, a capacitance probe or an optical probe. In particular the measurement probe could be a camera probe.

The measurement device can comprise a surface sensor. This can be the part which interacts with the surface of the artefact in order to measure the artefact. As described below, the surface sensor could be a contact surface sensor or a non- contact surface sensor. The measurement device can comprise a body to which the surface sensor is attached. The surface sensor can be spaced apart from the body. For instance the surface sensor could be mounted toward the distal end of a stylus extending from the body. The body can be the part of the measurement device which is for mounting to a positioning device, for instance on a quill of a positioning device. The body can provide the at least one rotational degree of freedom. Optionally the at least one rotational degree of freedom is provided by the positioning apparatus. For instance the at least one rotational degree of freedom can be provided by a head on which the measurement device is mounted. Accordingly, the axis about which the at least one degree of freedom is provided can be distal to the surface sensor.

As will be understood the interaction path can comprise the path the device takes during an operation. The interaction path could comprise a measurement path a measurement device takes during a measurement operation. Optionally, the interaction path could comprise a machining path a tool takes during a machining operation. The interaction path could be one sub-path of a plurality of sub-paths that when executed in sequence describes a whole interaction operation. The path could comprise position information only. Accordingly, the path could comprise no orientation information.

The interaction path can comprise the path the device takes during a operation whilst it is in an interacting relationship relative to the artefact. For instance, the interaction path can comprise the path a measurement device takes during a measurement operation whilst it is in a position sensing relationship relative to the artefact. Optionally, the interaction path can comprise the path a tool takes during a machining operation whilst it is machining (e.g. cutting, grinding or milling) the artefact. Accordingly, the method can comprise determining how to orient the device whilst interacting with the artefact. For instance, the method can comprise determining how to orient the device whilst obtaining measurement data about the artefact. The interaction path can comprise the path the device takes whilst moving more generally around the artefact. Accordingly, the interaction path can comprise the path the device takes between positions in which it is in an interacting relationship relative to the artefact. As will be understood, the interaction path could be the path on the artefact that is to be interacted with by the device. For example, the interaction path could be a path on the artefact that is to be measured. Optionally, the interaction path could be a path on the artefact that is to be machined, e.g. cut and/or milled.

As will be understood if, for example, the interaction path is a fixed path on the artefact, then it might be necessary to relatively reposition the artefact and device in the at least one linear degree of freedom in order to obtain the determined orientation. Accordingly, determining how the device and artefact can be oriented relative to each other can comprise determining the relative position of the device and artefact in the at least one linear degree of freedom.

The method could comprise obtaining the data representing the interaction path. The interaction path could be input by the user. Accordingly, the method could comprise receiving an interaction path from a user interface device. The interaction path could be predetermined for the artefact to be measured. That is the interaction path could be determined prior to execution of the method of the invention. Accordingly, the method could comprise retrieving the interaction

path. The interaction path could be retrieved from a memory device.

Optionally, the interaction path could be generated from geometric data. The method could comprise generating the interaction path from the geometric data.

The interaction path data could comprise a plurality of points. For instance, a interaction path could comprise a plurality of points on the artefact which are to be interacted with. For instance, a measurement path could comprise a plurality of points on the artefact which are to be measured. The points could be discrete points. Optionally the interaction path data could comprise a line, dimension, degree of freedom or the like. For instance, the measurement path data could comprise a line, dimension, degree of freedom or the like along which measurements are to be taken. For instance the interaction path could comprise vector data. Optionally, the interaction path could be defined as a curve between two points.

Suitable optimisation criteria for use with the present invention can include criteria relating to the performance of an interaction operation. Accordingly, the method can comprise determining how the relative orientation of the device and artefact can be manipulated during movement of the device along an interaction path in order to meet one or more performance criteria. Performance criteria can comprise a speed of interaction. For instance, performance criteria can comprise a speed of measurement or speed of machining. Performance criteria can comprise interaction path length. Performance criteria can comprise predetermined acceleration level. The predetermined acceleration level can relate to the acceleration of the device. The predetermined acceleration level can comprise a maximum acceleration. Performance criteria can comprise the direction of motion. Performance criteria can comprise ensuring minimum movement of the positioning apparatus which controls the translational movement of the device and/or artefact through the measurement volume. Performance criteria can comprise maintaining a predetermined relative orientation between the device and

the artefact being measured. Performance criteria can comprise ensuring that the device is dragged along the interaction path. For instance, performance criteria can comprise ensuring that the measurement device is dragged along the measurement path. This can be for instance when the measurement device's surface sensor trails the point at which the measurement device is mounted to the positioning apparatus. This can be as opposed to the measurement device being pushed along the measurement path.

Suitable optimisation criteria for use with the present invention can optionally comprise criteria relating to the boundaries of motion. For instance, optimisation criteria can comprise that the course of motion ensures collision free movement.

This can comprise collision free movement between the device and the artefact.

Accordingly, the method can comprise determining how the device and artefact can be oriented relative to each other along an interaction path in order to avoid collision between the device and the artefact.

This can also comprise collision free movement between any other relatively moveable objects located in the device's movement volume. For instance, this can comprise collision free movements of the part which effects relative movement of the device and artefact. Accordingly, the method can further comprise receiving geometric data relating to objects that will be located in the device's movement volume during an operation. Such an object could be a rack for storing the device. Such an object could be a calibration device, such as an object used to calibrate the device. Such an object could be one that is used to reorient the device. Such an object can include fixture devices used for positioning the artefact. Such an object could be another artefact. Such an object could be a positioning apparatus, such as the positioning apparatus on which the device is mounted.

As will be understood, in embodiments in which the device is moveable, a collision can comprise unwanted contact between the device and the artefact or

any other object located in the device's movement space. Further, in embodiments in which the artefact is moveable, a collision can comprise unwanted contact between the artefact and the device or any other object located in the artefact' s movement space. In embodiments in which the device is a non- contact measurement device a collision could comprise any contact between the non-contact measurement device and the artefact or any other object.

In embodiments in which the device has a contact part which is intended for contact with the artefact during the operation, a collision could comprise contact between any part of the device other than the contact part and the artefact. This could also comprise unintended contact between the contact part and the artefact, for example, contact between the contact part and a part of the artefact that isn't to be interacted with. For example, in embodiments in which the measurement device is a contact probe having a sensing tip a collision could comprise contact between any part of the measurement device other than the sensing tip and the artefact. This could also comprise unintended contact between the sensing tip and the artefact which is being measured, for example, contact between the sensing tip and a part of the artefact that isn't being measured.

A collision can be determined by identifying any undesirable intersection between geometric data representing different components. For example, a collision can be determined by identifying any undesirable intersection between geometric data representing the device and geometric data describing other parts, for instance the artefact, in the device's movement volume. As will be understood in ■ embodiments in which the device comprises an artefact contact part, such as a surface sensor, some intersection can be allowed. For instance, intersection between geometric data representing the artefact contact part and the point on the artefact that is to be interacted with can be allowed. However, all other intersections can be undesirable.

The method can comprise for each of a plurality of points along the interaction

path determining a plurality of relative orientations between the device and artefact. The method can further comprise for each of a plurality of points along the interaction path selecting collision free orientations only. The method can further comprise selecting from collision free orientations those orientations which comply with one or more other optimisation criteria. The method can comprise determining the cost associated with the movement between a pair of points along the interaction path. The, cost could depend on the relative orientation of the device and artefact at the pair of points. Accordingly, the method can comprise determining the cost of movement between a pair of points having a first orientation combination. The method can further comprise determining the cost of movement between the same pair of points having a second orientation combination. As will be understood, the orientation combination of a pair of points describes the relative orientation of the device and artefact at first and second points along the interaction path. The relative orientation of the device and artefact at the first and second points can be the same or can be different.

Preferably, the orientation of the device at at least one of the first and second points is different in the second orientation combination to the first orientation combination. The method can comprise selecting the orientation combination having the lowest cost.

This method can comprise determining the cost for a plurality of pairs of points along the interaction path. The method can comprise selecting those orientations in which the total cost along the interaction path complies with predetermined criteria. The predetermined criteria could be selecting the interaction path having the minimum co st.

As will be understood, the cost of movement can be a value which represents a property of the movement between the two points. For instance the property could be speed. The property could be time. The property could be distance. The property could be acceleration. The cost could be a combination of two or more of the above mentioned properties. Optionally, the cost property could be input by

a user.

The method can comprise determining a plurality of different possible courses of motion, each describing how the orientation of the measurement device can be controlled along the interaction path. The method can comprise selecting at least one course of motion from the plurality of course of motions which comply with the one or more optimisation criteria. The selected at least one course of motion can be that which complies with the optimisation criteria. Optionally, the selected at least one course of motion can be that which best complies with at least one of the one or more optimisation criteria. For instance, the selected at least one course of motion could be that which ensures collision free movement. The selected at least one course of motion could be that which ensures minimum device acceleration. The selected at least one course of motion could be that which ensures minimum interaction duration. The selected at least one course of motion could be that which complies with one or more of the above mentioned criteria.

The method can comprise receiving optimisation criteria. The optimisation criteria can be determined and input by a user. Optionally, the method can comprise receiving rules input by a user, and determining the optimisation criteria based on those rules. The method can comprise determining the optimisation criteria from the application of rules and logic to geometric data.

As will be understood, the interaction path might cover a portion of the artefact. Optionally, the interaction path could cover substantially the whole of the artefact. In this case the interaction path could comprise a plurality of sub-paths.

The method can comprise receiving an instruction to measure at least one portion of the artefact. The instruction can be received from a user interface device. Accordingly, the instruction can be input by a user. This enables a user to select which portions of an artefact are to be measured.

According to a second aspect of the invention there is provided computer program code comprising instructions which, when executed by a computer causes the computer to perform the above described method.

According to a third aspect of the invention there is provided a computer readable medium, bearing computer program code as described above.

According to a fourth aspect of the invention there is provided a computer comprising: a processor; and a memory, wherein at least one of the processor and memory is adapted to perform the above described method.

According to a further aspect of the invention there is provided a method of generating a path along which a measurement apparatus will move when measuring a part, using a geometric model of the part, the method comprising: (a) generating a plurality of points on a surface of the geometric model of the part; (b) generating multiple orientations of the measurement apparatus for measurement of each point; (c) generating an optimised path for the measurement apparatus, determining position and orientation, for measurement of the plurality of points. Preferably the geometric model is a CAD model, for example a boundary representation or a polygonal model. The multiple orientations of the measurement apparatus for measurement of each point generated in step (b) may be a discrete set or functionally derived. In a preferred embodiment, the geometric model of the part is combined with a geometric model of the measurement apparatus and coordinate positioning apparatus. For each orientation of the measurement apparatus in step (c), it is determined whether there is a collision between the measurement apparatus or coordinate positioning apparatus and part. Only those collision free orientations of the measurement apparatus and coordinate positioning apparatus are used to generate the optimised path. The measurement apparatus may comprise a measurement probe. A measurement probe may comprise a contact measuring probe with a stylus having a workpiece contacting tip. A measurement probe may comprise a non contact probe, for

example an optical, inductance or capacitance probe. The measurement apparatus may comprise a camera. Preferably the measurement apparatus is mounted on a coordinate positioning apparatus. The coordinate positioning apparatus may comprise apparatus which enables both the position and orientation of the measurement apparatus mounted on it to be varied. The coordinate positioning apparatus may comprise several components, for example an articulating probe head which provides rotational motion about two or more axes mounted on a coordinate positioning apparatus, such as a coordinate measuring machine (CMM). The coordinate positioning apparatus may comprise a single component, for example a manual coordinate measuring arm, a robotic arm, or the like. The path in step (c) may be optimised for criteria such as speed of measurement,, path length, acceleration constraints of the coordinate positioning apparatus, etc.

A yet further aspect of the invention provides a computer programme for generating a path along which a measurement apparatus will move when measuring a part, the computer programme comprising code adapted to perform the following steps when executed on a computer: (a) inputting a geometric model of a part; (b) generating a plurality of points on a surface of the geometric model of the part; (c) generating multiple orientations of the measurement apparatus for measurement of each point; (d) generating an optimised path for the measurement apparatus, determining position and orientation, for measurement of the plurality of points. Preferably the computer programme is provided on a carrier, such as a CD, USB stick or other medium, which when loaded into a computer carries out the invention. The computer program may also be downloaded directly from the internet. The computer programme may have the additional step of outputting the optimised path, displaying the optimised path or storing the optimised path in memory.

Preferred embodiments of the present invention will be illustrated by way of example with reference to the accompanying drawings, where:

Fig 1 illustrates a CMM on which a workpiece is mounted;

Fig 2 illustrates an articulated scanning head for mounting on the CMM of Fig l;

Fig 3 is a flow diagram illustrating an overview of the method of the present invention;

Fig 4 is a flow diagram of a method of generating multiple points on a selected surface;

Fig 5 illustrates a helical measurement profile on a periodic surface;

Figs 6A-C illustrate curvilinear measurement profile based on a sinewave, sharks tooth and square wave profile respectively on a NURBS surface;

Fig 7 illustrates a curvilinear measurement profile for a two loop surface;

Figs 8A-8D illustrate different curvilinear measurement profiles for a three loop non periodic surface;

Fig 9 is a flow diagram for an alternative method of creating a measurement profile on a planar surface;

Fig 10 illustrates a sine- wave curvilinear measurement profile parallel but offset from a planar surface of a cylinder;

Fig 11 illustrates the cylinder of Fig 10 with the measurement profile projected onto its planar surface; Fig 12 is a flow diagram for generating a surface profile on a cylindrical surface;

Fig 13 A illustrates a helical measurement profile plotted inside an internal bore of cylinder;

Fig 13B illustrates a helical measurement profile projected onto the surface of the internal bore of Fig 13 A;

Fig 14 is a flow diagram for generating a surface measurement profile on a general face;

Fig 15 is a flow diagram of a method of generating multiple orientations of the measurement apparatus for each point; Fig 16 illustrates the application of Dijkstra's algorithm to the generation of an optimised path;

Fig 17 is a schematically illustrates the calculation of various orientations of a measurement probe relative to an artefact to be measured along a measurement path; and

Fig 18 is a schematic illustration of the determined orientation of the a measurement probe relative to an artefact along a measurement path.

Fig 1 illustrates measurement apparatus, in the form of a measurement probe 28 mounted on a coordinate positioning apparatus. In this embodiment, the coordinate positioning apparatus comprises an articulating probe head 16 mounted on a CMM 14. A workpiece 10 to be measured is mounted on a table 12 of the CMM 14 and an articulating probe head 16 is mounted on a quill 18 of the CMM 14. The quill is driveable in three directions X ₅ Y ₅ Z relative to the table by motors in a known manner. The CMM is provided by motors and transducers to provide and measure motion in each axis. This arrangement is described further in international patent application no. WO90/07097. The articulating probe head enables a probe or stylus mounted on the articulating probe head to be rotated about two orthogonal axes. Thus a probe or stylus mounted on the articulating probe head may be angularly oriented about these two axes whilst the articulating probe head can be positioned by the coordinate positioning machine in any position within the working volume of the machine. Such an articulating probe head provides a coordinate positioning machine with greater scanning flexibility because the articulating probe head can position the probe or stylus in many different orientations.

As illustrated in Fig 2, the articulating probe head 16 comprises a fixed part formed by a base or housing 20 supporting a movable part in the form of a shaft 22 rotatable by a motor Ml relative to the housing 20 about an axis Al . The shaft 22 is secured to a further housing 24 which in turn supports a shaft 26 rotatable by a motor M2 relative to the housing 24 about an axis A2 perpendicular to the axis Al.

A probe 28 with a stylus 29 having a workpiece contacting tip 30 is mounted onto the articulating probe head. The arrangement is such that the motors Ml, M2 of the articulating probe head can position the workpiece-contacting tip angularly about the axes Al or A2 and the motors of the CMM can position the articulating probe head linearly anywhere within the three-dimensional coordinate framework of the CMM to bring the stylus tip into a predetermined relationship with the surface being scanned.

Linear position transducers (not shown) are provided on the CMM for measuring linear displacement of the articulating probe head and angular position transducers Tl and T2 are provided in the articulating probe head for measuring angular displacement of the stylus about the respective axes Aland A2.

A measurement controller 32 sends drive signals to the motors of the coordinate positioning apparatus (e.g. CMM and articulating probe head) to control their motion and receives inputs from the transducers of the coordinate positioning apparatus (e.g. CMM and articulating probe head) and measurement apparatus (e.g. measurement probe). The controller 32 may be a bespoke device or software on a computer.

The measurement apparatus may be a measurement probe, such as a contact probe having a stylus with a workpiece contacting tip. Known types of contact probe include a touch trigger probe, in which deflection of the stylus causes an output which latches the position of the coordinate positioning apparatus at which the trigger occurred. Another type of known contact probe is a scanning probe, in which transducers in the probe measure the amount of stylus deflection. The measurement apparatus can also include non contact probes (e.g. optical, capacitance and inductance probes) and devices such as cameras.

When a workpiece is to be measured, a course of motion which is to be followed by the measurement apparatus must be programmed.

The course of motion is planned in software 34 which communicates with the measurement controller 32. The measurement controller and software may be run on the same device (i.e. the same PC, machine controller or bespoke device) or be 5 separate devices.

An overview of the course of motion planning method will now be described with reference to Fig 3. hi a first step a geometric model of a workpiece, such as a CAD model, is loaded into the path planning software 40. The model may for o example comprise a boundary representation (B -Rep) or a polygonal model, as described in more detail in the embodiments below. A part co-ordinate system is created for the geometric model and this is aligned with the coordinate system of the coordinate positioning apparatus which will be used to measure the workpiece 42. In this way, the model is placed virtually on the table of the coordinate5 positioning apparatus.

The software allows the user to select one or more surfaces of the geometric model to be measured 44. The use of a CAD model enables a list of faces of the model to be displayed, which can be selected and/or de-selected for inclusion in a 0 measurement plan. A B-Rep model already has defined faces, whereas these faces must first be created from a non parameterised model, such as a polygonal model.

Once a surface of the geometric model has been selected, multiple points on each surface are generated 46. These points are locations at which measurements will5 be taken using the measurement apparatus and are part of the measurement path. The multiple points may be received as part of a surface measurement profile, individually selected by a user or automatically generated by the software 34 based on the geometric model of the surface as described in more detail below..

0 For each surface point, the software 34 generates multiple possible orientations and/or positions of the measurement apparatus which allow the measurement of

the surface point to be taken 48.

The software then generates an optimised path for the measurement apparatus to follow, enabling measurement of each of the surface points 50. This measurement path may be optimised for difference factors, for example for speed, distance, acceleration constraints etc.

The step of automatically generating multiple measurement points on a selected surface that make up the measurement path will now be described in more detail, referring to the flow diagram of Fig 4. The measurement path is also commonly referred to as a measurement profile.

The surface parameters of the selected surface are determined 54, which gives information such as whether the surface is periodic or has loops. This method is particularly suitable if the geometric model is in the form of B-Rep, as the surface parameters are included in the model.

Once the surface parameters of the selected surface have been determined, the surface can be identified as a particular surface type and a measurement profile suitable for that surface type can be generated on the surface.

The flow diagram in Fig 4 shows one method of generating a measurement path according to surface type.

It is determined from the surface parameters of the selected surface whether the surface is periodic 56. If the surface is periodic, a measurement path suitable for the periodic surface is chosen 58, e.g. a helical pattern for a cylindrical surface. Where more than one measurement path is available, a default measurement path may be applied or the user may be allowed to select the measurement path of their choice for a surface.

Fig 5 illustrates a turbine blade 72 having a periodic surface between loop

boundaries 74,76. A loop is a circuit of edge bounding a face. A helical measurement path 78 is shown.

If the surface is non periodic, it is determined how many face loops the surface ^' has. A loop is a B-Rep term for a closed edge. Different measurement paths can be generated, depending on whether there are one, two or more loops. Fig 4 illustrates that for a surface having one loop 60, a suitable measurement path is generated 62, for example a single curvilinear measurement path based on a sine- wave.

Figs 6A-C illustrate measurement path on a typical NURBS (Non-uniform, rational B-spline) surface 72, for example a face of a turbine blade. The surface has a single loop with a loop boundary 80. In Fig 6A, a curvilinear measurement path based on a sine-wave 82 is shown. Fig 6B shows a curvilinear measurement path based on a 'sharks tooth' 81 and Fig 6B shows a measurement path based on a square wave 83. Alternative curvilinear profiles may also be used.

Figure 4 illustrates that for a face having two loops 64, a suitable measurement path is generated between the two loops 66. Fig 7 illustrates a typical NURBS surface 72, (e.g. a face of a turbine blade) with two loop boundaries 80,86. A curvilinear measurement path 88 is shown between the loop boundaries.

If there are more than two loops, the surface maybe partitioned into areas such that each loop has an associated area to which it belongs 68. A suitable surface measurement path is generated for each area 70. Figs 8A-8D illustrate a typical

NURBS surface 72 (e.g. a face of a turbine blade) with three loop boundaries 80,90,92. In Fig 8A, a partition line has been created 94 to create two areas 96,98 equivalent to that illustrated in Fig 7. Areas 96,98 contain loops 90,92 respectively. Curvilinear surface measurement paths 99 are shown in each area 96,98. Other measurement paths may be created using alternative strategies, for example Fig 8B illustrates a 'sharks tooth' curvilinear measurement path 101 over

the whole surface and Figs 8C and 8D illustrate different arrangements of curvilinear measurement paths 103.

Figs 6,7 and 8 illustrate curvilinear measurement paths based on sine waves. However, other measurement paths may be used. Furthermore a set of discrete measurement paths can be generated for each surface or area.

Once the measurement path has been created, a set of surface points can be generated along the path at a selected frequency.

An alternative method of creating measurement paths on each surface is described below with reference to Figs 9-14. This method is particularly suitable for use with polygonal models but can be used for general geometric models in other formats, including B-Rep. As polygonal models are not parameterised, surfaces of the model must be identified using techniques which will not be described here further.

Fig 9 is a flow diagram for the method of creating a measurement profile on a planar surface. Once the planar surface has been selected 123, a face aligned bounding box is created 124. A measurement path, in this example a curvilinear path based on a sine wave is generated across the bounding box face which is parallel to the plane of the planar surface 126. Each point of the measurement path is projected on to the plane of the planar surface 128 using the normal of the bounding box's face. Points which do not contact the surface of the planar face are removed from the measurement path. The software determines whether points have been removed 130.

If points have been removed, then for each segment of the measurement path, it is determined whether a collision free path can generated 134 to join segments. The profile segments are either joined directly 136 by a path along the surface if possible or joined by an off surface path 138.

A resulting surface measurement path is thereby created 132.

Figs 10 and 11 illustrate a measurement path being created on a planar surface of a cylinder in this way. In Fig 10 a curvilinear profile 140 is shown plotted on a plane parallel but offset to the planar surface 142 of the cylinder 144. In Fig 11 the curvilinear path 146 is plotted onto the planar surface 142. The measurement path has been modified by paths 148 along the surface and off surface paths 150 which join segments of the measurement path.

Fig 12 is a flow diagram for the method of creating a measurement path on a periodic face, such as a cylindrical face. The periodic face is first selected 150 and a periodic measurement path, such as a helix is generated 152 which, for an external cylinder is larger than the cylindrical face and for an internal cylinder is smaller than the cylindrical face. As before, each point of the helix is projected onto the cylinder. Points which do not contact the surface are removed from the helix 154. The software determines whether points have been removed 156.

As before, where points are removed, a path is generated to join segments of the measurement path. It is determined whether a collision free linear path can be generated between the segments of the measurement profile 160. If it can, a linear path is generated to join the segments together 162. Otherwise, the segments can be joined by an off surface path 164. A resulting surface measurement path is thereby created 158.

Figs 13 A and 13B illustrate a measurement path being created on an internal cylindrical face of a cylinder. Fig 13A illustrates a helical path 166 plotted inside the internal bore 168 of the cylinder 144. Fig 13B illustrates the helix 170 projected onto the bore surface with path modification 172 and off surface paths 174 to join segments of the measurement path across surface discontinuities.

Fig 14 is a flow diagram for path planning on general surfaces. As can be seen, most of the steps on Fig 14 are the same as for Figs 9 and 12, showing path planning on planar and cylindrical faces. However, in step 176 the user selects an unknown fact and in step 178 the user chooses the measurement path, rather than a default one being chosen for the surface type. For example line, curvilinear, and helical path may be chosen, in addition to manually created profiles. Steps 180- 190 are similar to steps 154-164 in Fig 12.

As in the method described with reference to Figs 4-8 the measurement path can be used to generate a series of surface points.

Once the measurement path has been generated (step 46 in Fig 3), multiple orientations of the probe 28 along the measurement path can be generated (step 48 in Fig 3). A method of generating the multiple orientations of the measurement apparatus for each point is described below with reference to Fig 15.

In a first step, a series of surface points are generated 102, for example as described in the methods described with reference to Figs 4-8 and Figs 9-14.

Each surface point is checked to ensure that the surface detection region of the probe 28 may be positioned in a position sensing relationship with it without the probe 28 colliding with other faces of the workpiece 104. For a contact probe, the surface detection region is the probe tip and it is in a position sensing relationship with the point when it is contact with the point. For a non contact probe, the surface detection region may comprise a point or plane offset from the measurement apparatus which is preferably positioned at the surface for optimal measurement, for example a focal point for an optical probe.

In a next step, the required motion of the surface detection region is generated between surface points 106. This motion of the surface detection region is checked to ensure the surface detection region remains on the surface of the

workpiece during the move 108 and that there is no collision with other surfaces of the workpiece 110.

In a next step, the coordinate positioning apparatus positions are calculated to position the surface detection region of the probe 28 at a position sensing relationship with the surface points 112. Multiple coordinate positioning apparatus positions are generated for each surface point, each with the surface detection region at the surface point but with the probe 28 positioned at different orientations. In the case where the coordinate positioning apparatus comprises an articulating probe head mounted on a positioning apparatus, different probe head angles (Al and A2 angles) are calculated to provide different probe 28 orientations. The term probe head angle relates to the angle the probe head holds the measurement apparatus about the Al and A2 axes.

The generation of different probe 28 orientations may be influenced by parameters of the part, such as a principle axis of a surface and its periodicity. For example, an internal cylindrical surface, such as a bore, has a principle axis along its centre and is periodic. This principle axis determines the preferred locus of orientations of the probe 28.

This is equivalent to a mathematical function based approach to course of motion generation. For example, for a periodic surface such as a bore a course of motion may be generated by oscillating the articulating probe head around the Al axis while moving the articulating probe head along the principal axis of the bore.

Where such a functional approach is used, the possible orientations of the probe 28 may be limited, for example to within a defined plane or cone.

If parameters of the workpiece, such as principle axis and periodicity are not available, then a random set of orientations of the probe 28 can be generated.

Irrespective of their generation method, the orientations of the probe must be 'legal'. An orientation can be considered legal when it is collision free. Other factors for determining whether an orientation is legal can also include whether the probe is within mechanical constraints such as the typical working volume of the coordinate positioning apparatus and its consequent available configuration space. Factors for determining whether an orientation is legal can further include whether the orientation violates any configuration constraints such as the angle between the probe and surface normal.

Each orientation of the measurement apparatus is checked to see if it places the probe or coordinate positioning apparatus in collision with the workpiece or any other part in the measurement volume. Collision free orientations are kept and used to generate an optimised course of motion, whilst other orientations are rejected.

Where the movement of the probe head has been initially constrained by generating head angles along a preferred head locus any found collisions have the effect of loosening' the path as further probe configurations are generated that deviate away from those preferred head angles. A function based approach will be similarly affected by collision checking.

Collision free orientations of the probe 28 are generated until a required number is obtained, or until a maximum number of generation iterations is reached. The former has the advantage of achieving comprehensive orientation generation within a practical time frame. The latter constraint has the benefit of preventing the system from entering an orientation generation loop caused by an unreachable, i.e. the probe cannot physically access the point, and consequently un-measurable surface point.

The calculation of the orientations of the probe at a measurement point is

schematically illustrated with reference to Figure 17 in which there is shown a CAD model 33 of an artefact to be measured by the probe. A measurement path 35 along which the artefact is to be measured has been calculated, for example using the above described methods. The probe for measuring the artefact is abstractly represented in the CAD model 37 as a first sphere 39 representing the probe tip, a cylinder 41 representing the stylus and a second sphere 43 representing the probe head. The software generates a plurality of different orientations of a CAD model 37 of the probe 28 relative to the CAD model 33 of the artefact for a plurality of points along the measurement path.

For example, for a first measurement point A, the CAD model 37 of the probe is shown at first 37a, second 37b and third 37c calculated orientations relative to the CAD model 35 of the artefact. As shown, the probe tip 39 is at the same point on the surface of the CAD model 33 of the artefact for each of the three orientations. Accordingly, the different orientations are achieved by effectively repositioning the model of the head 43 of the probe relative to the model 33 of the artefact. For the three shown orientations, only the first 37a orientation is legal as at least a part of the CAD model 37 of the probe at the other two orientations 37b and 37c are in a collision state with the CAD model 33 of the artefact. The parts in collision are illustrated by dotted lines 45. Accordingly, in this case the software can choose the first orientation 37a only out of the three determined orientations.

Again, for a second measurement point B, the CAD model 37 of the probe is shown at first 37d, second 37e and third 37f calculated orientations relative to the CAD model 35 of the artefact. As shown, the probe tip 39 is at the same point on the surface of the CAD model 33 of the artefact for each of the three orientations. Accordingly, the different orientations are achieved by repositioning the model of the head 43 of the probe relative to the model 33 of the artefact. For the three shown orientations, the first 37d and second 37e orientations are legal but the third orientation 37f is not - a part of the CAD model 37 of the probe at the third orientation 37f is in a collision state with the CAD model 33 of the artefact

(illustrated by dotted line 45). Accordingly, in this case the software can choose between the first 37d and second 37e orientations for use in the final course of motion. How the software chooses between these orientations is described in more detail below and can for example depend on performance factors.

Only a few orientations for a couple of measurement points are shown in connection with Figure 17 for the sake of simplicity and clarity of illustration. However, as will be understood, it is possible to calculate fewer or more orientations of the CAD model 37 of the probe relative to the CAD model 33 of the artefact for each measurement point along a path. Furthermore, it is possible to determine orientations for many more measurement points along the measurement path 35.

Once a sufficient number of orientations of the probe 28 have been generated, an optimised course of motion for the probe 28 is generated (see step 50, Fig 3). This course of motion joins one of the multiple probe 28 orientations for each surface point. The course of motion of the probe 28 can be optimised for different criteria, for example for the shortest or fastest path of the probe 28.

In particular, the coordinate positioning apparatus may have different inertial deflection characteristics for different axes and the path may be optimised to limit the accelerations of the different parts of the system based on the known inertial deflection characteristics of each axis, such that the best speed can be achieved for a given required accuracy. For the case where the coordinate positioning apparatus comprises an articulating probe head mounted on a CMM, the articulating probe head may be stiffer than the CMM and thus bend less than the CMM under acceleration. The course of motion can therefore be optimised by minimising acceleration of the CMM to thereby reduce bending.

Different methods may be used to optimise the course of motion, for example A* search, Floyd- Warshall algorithms, Johnson's and Bellman-Ford algorithms and

Genetic algorithms. All are well known and are not described further.

In a preferred embodiment, Dijkstra's algorithm is used and this is described in more detail below. This is a well known computationally expensive algorithm that can determine the shortest path by taking a source node and computing an edge weight between it and all other nodes. The weight of each edge is a value that describes the desirability of using it, with the lowest value indicating the most desirable node pair connection. Once the most desirable node pair connection is found the first node is removed from the set and process repeated with the second node and so on.

The application of Dijkstra's algorithm to course of motion optimisation in the present invention is described below with reference to Fig 16.

Fig 16 illustrates four surface points 200, 202, 204, 206 on a surface measurement path. For each surface point 202-206, a number of different legal probe orientations have been generated, with each orientation as a node. Fig 16 illustrates a set of nodes representing the set of probe orientations for each surface point. For example surface point 202 has three probe orientations 202A, 202B, 202C. For different surface points the number of possible probe orientation differs. All possible measurement apparatus orientations (nodes) are connected by edges (represented bylines 208 joining the nodes) and the weights 210 on each edge 208 have been computed as the cost of moving between node pairs. The 'cost' is dependent upon applied metrics.

The applied metrics employed to assign desirability weights are chosen in accordance with factors governing the optimisation of the path. Examples of possible metrics include the computation of the time required to perform the move of the probe between start and finish points and the distance moved by the coordinate positioning apparatus to position the measurement apparatus. In this

way the course of motion may be optimised for different factors, such as the shortest or fastest course of motion.

Other cost metrics may also be used, such as methods that weight course of motions to minimise acceleration of parts of the coordinate positioning apparatus (such as the CMM when the coordinate positioning apparatus comprises an articulating probe head mounted on a CMM).

The values in the boxes 212 beneath each node are the minimum cost of moving to that node from the previous node. Therefore, the course of motion that is selected can, for instance, be the one with the minimum cost on any node of the last point. This is shown as the bold path 114.

Figure 18 provides a schematic CAD model illustration of the determined course of motion of the probe along a part of the measurement path of the artefact to be measured, at a plurality of discrete measurement points. In particular, the chosen orientation of the probe at each of a plurality of measurement points along the measurement path 35 of the CAD model 33 of the artefact is shown by the CAD models 37 of the probe. As will be understood, the orientation of the probe at fewer or greater measurement points than shown can be calculated as part of the course of motion.

As will be understood, it is not essential that the method of the invention generates visual CAD models illustrating the various possible orientations (e.g. as shown in Figure 17) or the final determined course of motion (e.g. as shown in Figure 18). Rather, Figures 17 and 18 have been provided to merely aid the description of how the method of the invention might be executed in one particular embodiment. Nevertheless, as will be understood, it could be an optional feature of the invention that a visual representation of the relationship between the CAD model

of the artefact and CAD model of the probe is provided. This could for instance aid a user in assessing the determined course of motion.

In the described embodiments the probe is mounted on a mounting structure equivalent to the quill of a CMM. This invention is also suitable for use with planning the course of motion of a measurement device mounted on other machine types. For example, the probe may be mounted onto the distal end of an inspection robot, which may for example comprise a robotic arm having several articulating j oints.

In the described embodiments, it is assumed that the probe is moved. However, as will be understood, the invention can also be applicable to embodiments in which the workpiece is moved instead of or as well as the probe. For instance, the workpiece could be mounted on the moveable quill of a positioning apparatus. Optionally the workpiece could be mounted on a table that can be rotated, and/or reoriented relative to the probe.

Furthermore, the described embodiment relates to a measurement device and an operation for measuring an artefact. As will be understood, the invention can also be used to generate course of motion data for other types of devices, and for example for tools for machining an artefact. For instance, the invention could be used to determine the course of motion of a milling tool during a milling operation. For example, path data which represents a path across a surface of an artefact along which a cutting tool is to cut a feature (e.g. a channel) can be received as well as and geometric data representing the cutting tool, and the method could be used to determine how to orient the cutting tool whilst it is moved along the cutting path.