A manufacturing process of particular prominence, with a long history, is
milling.
A Numerical Control (NC) milling machine cuts a part out of a block of metal or
other material (the ``stock'') by moving a cutting tool through space. For
3-axis
machining, a rotating cutting tool, with a vertical axis of rotation, does
the cutting. An ``NC program'' specifies the movement.
Typically, the program
consists of a ``cutter location file,'' which is a long list of
coordinates for successive tool locations.
The tool is moved to the first spatial location,
then moves along a straight line (or, say, a circular arc)
to the next, then along a straight line
from the second location to the third, and so on, until the list of locations
is completed. (Actually, the file also contains other information, such as
tool sizes, and instructions for when tools must be changed.)
For 5-axis machines, two additional coordinates giving the
angular orientation of the tool axis are also specified and the tool
linearly interpolates both spatial and angular coordinates.
Typically these NC programs are created by tool programmers. The programmers begin with a geometric representation of the part expressed in Constructive Solid Geometry (CSG), or some sort of boundary representation using splines, and generate series of tool movements that are supposed to mill the part from the stock.
As with computer programs, NC programs are error-prone. Bugs can produce cuts that are too deep or leave too much material. Thus, an important practical problem is: ``Given a surface of known equation and a file of NC tool movements, does the shape that the tool cuts match the mathematical shape to within a given tolerance?'' It has been claimed [53] that ``current methods of verifying NC part programs result in one of the highest non-recurring cost factors in producing NC machined parts within the aerospace industry.'' It is also a significant cost within the aircraft and automotive industries, among others.
The early approach to finding bugs was to use ``proofing runs'' on wood or foam; this is still a popular technique. Later systems would move a graphical display of a cutter over a display of the part. The user could visually check for errors as the tool moved on the graphics display. Only gross errors could be detected in this way, however. In the 70's, work began on programs that actually detected errors in NC programs or verified that none existed. A good overview of this problem, including a precise mathematical formulation, history, and summary of its current state is found in [100].
Some of these methods use ``complete'' representations of the current state of the partially cut workpiece. Researchers investigated the feasibility of using CSG systems or solid modelers for the simulation of NC programs [76]. Others developed systems based on octree [111] or boundary representation [135] of the workpiece. For each method, every tool movement would update the workpiece, and at the end the workpiece was compared to the desired piece. Unfortunately, all of these approaches were slow. Each tool movement subtracts a fairly complex shape from the current workpiece representation and requires significant updating. For example, for a simple 3-axis movement with a ball-end cutter the swept volume is bounded by parts of two spheres, three cylinders, and two planes; the number of movements is typically on the order of 10,000.
To avoid this problem, a number of people took advantage of the fact that it is not necessary to represent the entire state of the workpiece to verify the correctness of an NC program. The desired shape is known in advance, and this information can be used to simplify the process. Several researchers used an image-space approach, where an extended Z-buffer is provided for each pixel in a given graphical view of the part, and each tool movement updates the pixel information for each pixel that it passes over [143][138][11]. CGTech's Vericut simulator uses such an approach. These methods are faster than the complete methods but they are view-dependent. Because of this, errors might not be visible from a certain view direction and would therefore be missed. (Consider a nearly flat surface viewed edge-on. A large surface would be mapped into a thin line represented by only a few pixels, and errors that occurred where there were no pixels would be missed.)
Another approach is to grow vectors normal to the surface of the part [30]. These vectors are ``mowed down'' by the passage of the cutting tool, and their lengths are checked at the end of the run. Vectors that stick out above the surface indicate excess material and vectors cut below the surface point to gouges. One might use pixels to select these vectors (one vector for each pixel) [113]. Or one might use properties of the tool size and the surface curvature to pick fewer vectors while still guaranteeing that they will find all errors greater than a user-set tolerance [43].
A recent modification of the extended Z-buffer, called ray representations (ray-reps), has been proposed [99]. A ray-rep is the intersection of a grid of parallel rays in some direction with the part. (Note that the intersection of a ray and a part consists of zero, one, or several line segments.) Given such a representation, all of the operations of CSG can be computed quickly by using a specialized parallel computer for processing ray-reps, called a raycasting engine. All of the approaches using modified Z-buffers or vectors introduce error. Even if the intersection with the tool path movement is calculated exactly (more on this below), in effect the part surface is being replaced by a set of discrete points. What can we say about the correctness of the surface at points where there are no vectors? All of these approaches use enough vectors to be fairly accurate in practice, but with a few exceptions none of them attempt to analyze errors introduced by the approach to check whether they fall within tolerance.
The ray-rep representation seems an ideal candidate for such analysis. Even with the special-purpose parallel computer one wishes not to use more rays that are needed. But how to analyze the errors introduced remains an open question, as is the determination of the optimal number of rays to use. It is also interesting to look at other possible applications of this representation and to analyze the relationship between the spacing of the rays and the error introduced.
A second area that needs more study is the one of intersecting rays with surfaces. Intersecting rays with part surfaces is reasonably well understood. However, when the surfaces are represented parametrically using B-splines or similar methods, computing intersections generally requires a slow interactive technique. One must also compute the intersection of rays with the envelopes swept out by tool movements. This is not too difficult for 3-axis movements of ball-end cutters. But the same cannot be said of the intersection of a ray with a 3-axis toroidal-end cutter movement. Most existing codes use a polygonal approximation to the envelope or a large number of discrete tool locations. Unfortunately, no error analysis is available.
For 5-axis cutter movement, an efficient method has been given for computing the intersection within a given error bound by using 3-axis tool movement as an approximation and relying on tree-based localization technique to quickly decide which of the 3-axis movements is the one intersected first [122]. See also [92]. What remains open is to find a method for generating a polygonal approximation for the 5-axis envelope with a provable error bound that generates a reasonable number of triangles. Finding such a provably good approximation technique is an interesting and important open problem.