Method of Optimally Operating a Computer Numerical Control Milling Machine to Mill Optimal High Density Interconnect Substrates

This specification includes a computer program listing in microfiche appendix form, comprising one microfiche with a total of 45 frames.

This invention relates to formation of cavities in ceramic substrates for receiving integrated circuit chips and other components of a high density interconnect (HDI) structure and, more particularly, to methods for optimally operating a computer numerical control (CNC) milling machine to form such cavities.

As disclosed in Eichelberger et al. U.S. Pat. No. 4,783,695, and related patents, a high density interconnect (HDI) structure which has been developed by General Electric Company offers many advantages in the compact assembly of digital and other electronic systems. For example, an electronic system such as a microcomputer which incorporates between thirty and fifty chips, or even more, can be fully assembled and interconnected on a single substrate which is fifty mm ( roughly two inches) long by fifty mm wide by 1.27 mm (50 mils) thick. This high density interconnect structure can be disassembled for repair or replacement of a faulty component and then reassembled without significant risk to the good components incorporated in the system. Repairability is particularly important where fifty or more chips having a cost of as much as $2,000.00 each, may be incorporated in a single system on one substrate. This repairability is a substantial advance over prior interconnection systems in which reworking the system to replace damaged components is either impossible or involves substantial risk to the good components. Exemplary testing and repair techniques are disclosed in Eichelberger et al. U.S. Pat. Nos. 4,878,991, 4,884,122 and 4,937,203.

Briefly, in systems employing this high density interconnect structure, a ceramic substrate is provided. The ceramic substrate may be made of alumina, for example, with a thickness between 0.635 and 2.54 mm (25 and 100 mils, respectively). The substrate is of appropriate size and strength for the overall system, typically less than fifty mm square.

Once the positions of the various chips have been specified, individual cavities or one large cavity having appropriate depths at the intended locations of the various chips are prepared. This may be done by starting with a bare substrate having a uniform thickness and the desired size. Conventional, laser or ultrasonic milling may be used to form the cavities in which the various chips and other components will be positioned. For systems where it is desired to place chips of uniform size edge-to-edge, a single large cavity may be satisfactory. That large cavity has a uniform depth where the semiconductor chips have a substantially uniform thickness.

Typically, however, an electronic system includes chips and other components having a variety of overall sizes and thicknesses, and there are a plurality of cavities. Where a relatively thicker or a relatively thinner component will be placed, the corresponding cavity bottom must be made respectively deeper or shallower to place the upper surface of that component in substantially the same plane as the upper surface of the rest of the components and the surface of the unmilled portion of the substrate which surrounds the cavity.

The cavity bottoms are then each provided with a thermoplastic adhesive layer which may preferably be polyetherimide resin available under the trade name ULTEM.RTM. from the General Electric Company, Pittsfield, MA. The various components are then placed in their desired locations within the cavities. The entire structure is heated to the softening point of the ULTEM polyetherimide (in the vicinity of 217.degree. C. to 235.degree. C. depending on the formulation used) and then cooled to thermoplastically bond the individual components to the substrate. At this stage, the upper surfaces of all components and the substrate are disposed in substantially a common plane.

Alternatively, after the cavities are formed, an initial layer of metallization may be deposited over the entire substrate, including the cavity bottoms, and then patterned to define conductors. This initial layer of metallization is termed "metal zero". Patterned "metal zero" conductors formed directly on the substrate are brought out to the edges of the substrate to ultimately facilitate electrical connection to the system. In some cases "metal zero" conductor areas remain in the cavity bottoms to form back side bias connections, and the chips or other components are attached with conductive adhesive to these "metal zero" conductor areas.

In either event, after the components are in place, a multi-layer interconnection structure is built up to electrically interconnect the components into an actual functioning system. To begin the interconnection structure, a polyimide dielectric film which is about 0.0005 to 0.003 inches and which may be KAPTON.RTM. polyimide (12.5 to 75 thick), available from E.I. du Pont de Nemours and Company, Wilmington, DE, is pretreated to promote adhesion and coated on one side with an ULTEM polyetherimide resin or another thermoplastic.

The KAPTON polyimide film is then laminated across the tops of the chips, other components and the substrate, with the ULTEM resin serving as a thermoplastic adhesive to hold the KAPTON film in place.

Next, via holes are laser drilled in the KAPTON film and ULTEM adhesive layers in alignment with the contact pads on the electronic components to which it is desired to make contact. Exemplary laser drilling techniques are disclosed in Eichelberger et al. Pat. Nos. 4,714,516 and 4,894,115; and in Loughran et al. Pat. No. 4,764,485, all of which are assigned to the present assignee..

A metallization layer is deposited over the KAPTON film layer so as to extend into the via holes and make electrical contact to the contact pads disposed thereunder. This metallization layer may be patterned to form individual conductors during its deposition process, or may be deposited as a continuous layer and then patterned using photoresist and etching. The photoresist is preferably exposed using a laser which is scanned relative to the substrate to provide an accurately aligned conductor pattern at the end of the process. Exemplary techniques for patterning the metallization layer are disclosed in Wojnarowski et al. U.S. Pat No. 4,780,177 and 4,842,677; and in Eichelberger et al. Pat. No. 4,835,704, all of which are assigned to the present assignee.

Additional dielectric and metallization layers are provided as required in order to provide all of the desired electrical connections among the chips. Any misposition of the individual electronic components and their contact pads is compensated for by an adaptive laser lithography system as disclosed in Eichelberger et al. U.S. Pat. No. 4,835,704 which is assigned to the present assignee..

The designer of such a system incorporated in a high density interconnect (HDI) structure typically specifies the arrangement of the chips and other components to best suit circuit topology, without particular regard to the required cavities in the substrate, except to keep the overall size of the system such that it will fit on a fifty mm by fifty mm (roughly two inch by two inch) substrate, for example. Certain design rules are involved in the arrangement of the various components. For example, in order to allow for inaccuracies in a "pick and place" machine which places individual chips within cavities on the substrate, a specific minimum distance between neighboring chips must be maintained, for example 0.400 mm (15.75 mils). Although not an initial concern of the circuit designer, a related consideration is that the individual cavities must be larger than the chips, for example, by about 0.254 mm (10 mils) on each side. It would be difficult to automatically place chips in cavities which were precisely to size, necessitating exact positioning.

As a result of these considerations, what is known at the time when the cavities are to be formed, based on the locations and dimensions of the various components, are locations and dimensions of a set of cavities corresponding to the components on a one-for-one basis. Particular neighboring cavities of this set will either overlap or be separated by walls, since they were not dealt with being that they were not of concern during the initial stages of circuit design and layout.

A suitable machine for milling such cavities in a substrate is a model DM2800 computer numerical control (CNC) milling machine made by Dyna Mechtronics, of Sunnyvale, California. Although intended for milling metal, the DM2800 CNC milling machine, when appropriately programmed, has been found suitable for milling ceramic substrates, which have a hardness approaching that of diamond. As is known, such CNC milling machines operate under program control and execute program instructions in a particular language which includes such instructions as move to a particular point in space, repeat a sequence of instructions a specified number of times, skip to a particular instruction step, and execute a subroutine.

There exist so-called computer aided manufacturing (CAM) programs which serve to take the specification of a part, potentially a complex part, and generate CNC program instructions to direct a milling machine to form that part. However, application of such CAM program to the specific task of generating CNC instructions for milling an HDI substrate has a number of disadvantages. As one example, such CAM program may leave extremely thin and thus fragile walls between neighboring cavities. The thin walls are highly prone to subsequent breakage. As another deficiency, such prior CAM programs generate CNC instructions which produce overlapping cavities that are milled separately and independently, resulting in an inefficient and slower tool path.

Prior CAM programs exhibit a variety of other deficiencies when their use is attempted for the particular application of generating CNC instructions to mill ceramic HDI substrates. Such CAM programs generally operate to minimize tool movement. While this is a reasonable approach when milling metal, when ceramic is milled, minimizing tool wear is a significant consideration, which must be taken into account when specifying a tool path. As noted above, the ceramic HDI substrate material is very hard, almost as hard as diamond. Also, a CAM program intended for generating program instructions for milling metal will generally not generate program instructions which result in producing a suitably smooth finish when milling ceramic.

Accordingly, it is an object of the invention to provide a method for optimally directing a CNC milling machine to form a cavity or cavities for components to be interconnected by means of an HDI structure as briefly described hereinabove.

It is a related object of the invention to provide a method for operating a CNC milling machine to produce an optimal HDI substrate in minimal time.

It is a related object of the invention to provide a method for operating a CNC milling machine in a manner which results in minimal tool wear when milling a ceramic substrate.

Briefly, in accordance with a preferred embodiment of the invention, a method is provided for optimally directing a CNC milling machine to form in a substrate at least one cavity for a plurality of electronic components to be interconnected through a structure overlying and bonded to the substrate and the components. Program instructions for the CNC milling machine are generated based on locations and dimensions of the components which, through a set of design rules, provide locations and dimensions of an initial set of cavities corresponding to the components on a one-for-one basis. Depending upon the particular arrangement of the components, particular neighboring cavities of the initial set may either overlap or be separated by walls.

The method includes an initial step of forming a representation of the location and dimensions of each of the cavities of the initial set. Typically, the representation is in the form of a computer screen display based on data stored in the computer memory, or other storage medium.

Next, the representation is enhanced to represent locations and dimensions of cavities of an optimized set by employing a "combine pockets" step and a "remove borders" step.

The "combine pockets" step includes determining which cavities of the initial set overlap, are in alignment, and have depths within a predetermined tolerance of each other, if any cavities satisfy these three conditions. Then, the overlapping cavities are combined to define a single cavity. Such single cavity is milled much more efficiently than the plurality of cavities of the initial set.

The "remove borders" step includes selectively removing walls separating neighboring cavities having less than a predetermined minimal wall thickness by extending at least one of the cavities to meet another cavity. Typically, this step comprises extending a shallower one of the neighboring cavities to meet a deeper one of the neighboring cavities.

In an automated process for the "remove borders" step, each cavity in turn is checked against its neighbors on all four sides. Thus, for each cavity, each adjacent cavity is examined and, for each adjacent cavity at least partially in alignment and sharing a common wall, the common walls having a thickness less than a predetermined thickness are determined, and such common walls are removed.

Finally, CNC program instructions are generated for forming the cavities of the optimized set. Instructions for tool movement are generated so as to minimize tool wear when milling a ceramic substrate.

While the novel features of the invention are set forth with particularity in the appended claims, the invention, both as organization and content, will be better understood and appreciated from the following detailed description, taken in conjunction with the drawings, in which:

FIG. 1 is a perspective, cutaway view illustrating an HDI structure comprising a plurality of integrated circuit chips mounted in cavities formed in a ceramic substrate and interconnected over their upper surfaces;

FIG. 2 depicts a model DM2800 CNC milling machine which may be to form the cavities in the substrate of FIG. 1;

FIG. 3 an illustration of an on-screen computer display a typical HDI ceramic substrate by the locations of the integrated circuit chips only, without showing the locations and dimensions of the substrate cavities which are implied by the chip locations when design rules are applied;

FIG. 4 is a plan view, lined for color, which is comparable to FIG. 3 except that the corresponding cavities in the substrate are represented;

FIG. 5 is partly lined for color and depicts "command button" areas, of a graphical command interface as shown on a computer display;

FIG. 6 which is lined for color, represents the illustration of FIG. 4 after a "combine pockets" operation;

FIG. 7 is an illustration of an on-screen computer display that diagrammatically depicts criteria for border removal in an HDI ceramic substrate;

FIG. 8, lined for color, is an enlargement of a portion of FIG. 6, depicting selected cavities prior to a "remove borders" operation;

FIG. 9, lined for color, illustrates the results of a "remove borders" operation as applied to the cavities depicted in FIG. 8;

FIG. 10 is an illustration of an on-screen computer display that depicts an operation of providing corner relief in an HDI ceramic substrate;

FIG. 11 is a top level flow chart depicting the overall structure of a representative computer program for implementing the subject invention;

FIG. 12 is a flow chart representing program instructions for manually combining cavities;

FIG. 13 is a flow chart representing program instructions for automatically combining cavities;

FIG. 14 is a flow chart representing program instructions for removing borders or walls between adjacent cavities;

FIG. 15 is a flow chart representing program operations for reading initial information into the program employed in the invention;

FIGS. 16a, 16b and 16c together comprise a flow chart representing program instructions for generating CNC program instructions for milling the cavities of the optimized set;

FIGS. 17a and 17b together comprise a flow chart representing program instructions for generating CNC program instructions to rough out a pocket, as called for by program instructions represented by the flow chart of FIG. 16b;

FIG. 18 is a flow chart representing program instructions for generating CNC program instructions for a frame cut, as called by program instructions represented by the flow chart of FIG. 16b; and

FIG. 19 is a flow Chart representing program instructions for generating CNC program instructions for forming a double cut, as called by program instructions represented the flow chart of FIG. 16c.

FIG. 1 depicts a portion of an electronic system 20 employing a high density interconnect (HDI) structure. The electronic system 20 includes a ceramic substrate 22 having representative cavities 24, 26 and 28 milled by a CNC milling machine executing CNC program instructions generated in accordance with the subject invention. As described hereinabove, substrate 22 may, for example, be 2.54 mm (100 mils) thick, and of appropriate size and strength for the overall system. A typical size is fifty mm (about two inches) square.

Placed within the various cavities 24, 26 and 28 are a plurality of components in the representative form of individual integrated circuit chips 30, 32, 34 and 36. These chips have respective upper surfaces 40, 42, 44 and 46 with representative contact pads 48 disposed thereon.

Chip upper surfaces 40, 42, 44 and 46 are all generally even with (i.e. lie in a common plane with) each other and with an upper surface 50 of substrate 22, the substrate 22 upper surface 50 being an unmilled portion of substrate 22. As is apparent from FIG. 1, chips 32 and 34 are relatively thinner than chips 30 and 36, and cavity 26 within which chips 32 and 34 are positioned is not as deep as cavities 24 and 28 within which chips 30 and 36 are respectively positioned.

Also evident in FIG. 1 are design rule considerations whereby cavity dimensions are implied by chip dimensions. Thus, for example, chip 36 is placed in a cavity 28 which is larger than the chip so as to provide space around the chip to accommodate variations in precise location as the chip is inserted into the cavity by a "pick and place" machine (not shown). As discussed hereinabove, a circuit designer will generally specify the locations of chips 30, 32, 34 and 36. The dimensions of cavities 24, 26 and 28 are then implied or determined by the application of design rules.

In the case of chips 32 and 34, these design rules result in the definition of cavities corresponding to each. However, because the cavities are larger than the chips, and because the chips are close together, the resultant cavities overlap and, after milling, are indistinguishable from and actually comprise a single large cavity 26, even though they might be individually milled in accordance with prior CAM techniques. In other words, a common wall which would otherwise separate individual cavities holding chips 32 and 34 is completely eliminated during the milling process. According to the invention, rather than generating CNC program instructions for producing two individual cavities for chips 32 and 34, CNC program instructions for producing the single larger cavity 26 are generated, resulting in a more efficient milling operation.

Also evident in FIG. 1 are a wall 52 between cavities 24 and 26, and a wall 54 between cavities 26 and 28. Chips 30 and 32 and chips 34 and 36 are sufficiently spaced apart such that, even when the design rules have been applied, there is no overlap between the cavities. In some cases, walls 52 and 54, are extremely thin and thus unduly subject to breakage, particularly in view of the brittle nature of the ceramic substrate material. In those situations, it is best for such thin walls to be eliminated. Wall 52, as illustrated has sufficient thickness that it may remain; however, for purposes of illustrating the invention, assume that it would be desirable to eliminate wall 52. In that instance, shallower cavity 26 would be extended to meet deeper cavity 24, as indicated by a dashed line 57 representing a potential extension of cavity 26. Ordinarily a shallower cavity would be extended to meet a deeper cavity, rather than vice versa, to avoid undercutting substrate material below the potential location of a chip, which could result in locally inadequate heat sinking.

Also shown in FIG. 1 is a "metal zero" layer optionally deposited on substrate 22 after milling, but before chips 30, 32, 34 and 36 are placed. In the bottoms of cavities 24, 26 and 28, this metal zero layer is designated 56. On the substrate upper surface 50, this metal zero layer is designated 60. Although not shown in FIG. 1, the metal zero layer, particularly portion 60 thereof on the substrate upper surface 50, is typically patterned, particularly around the edges (not shown) of the substrate, in order to facilitate external connections to electronic system 20.

Metal zero layer portions 56 in the bottoms of cavities 24, 26 and 28 may serve as back side bias connections in the case of chips 30, 32, 34 and 36, which are attached with conductive adhesive. In order to provide reliable electrical connection to lower metal zero areas 56, a level or ramp-like structure 62 is milled in substrate 22 from its upper surface 50 down to the bottom of cavity 26, for example. Typical metal deposition processes, such as sputtering, are otherwise likely to leave metal discontinuities along vertical cavity sidewalls, and the bevel or ramp 62 reliably facilitates continuous metal deposition for electrical continuity.

To complete the FIG. 1 structure, an interconnection structure in the form of an overcoat 68 is built up as described in the various patents referred to hereinabove. Briefly, a polyimide film 70, such as KAPTON polyetherimide, which is about 12.5 to 75 microns (0.5 to 3.0 mils) thick, is pre-treated on one side with a coating of ULTEM polyetherimide resin 72, or another thermoplastic, in order to promote adhesion, and laminated across the tops 40, 42, 44 and 46 of chips 30, 32, 34 and 36, respectively and across the upper, unmilled surface 50 of substrate 22. Thereafter, via holes 74 are laser drilled in the KAPTON polyetherimide 70 and ULTEM adhesive 72 layers in alignment with contact pads 48 on chips 30, 32, 34 and 36 to which it is desired to make contact.

Buildup of an HDI overcoat 68 continues by depositing a patterned metallization layer 76 over KAPTON layer 70 so as to extend into via holes 74 to make electrical contact with contact pads 48. Additional dielectric and metallization layers are provided as required in order to provide all of the desired electrical connections among chips 30, 32, 34 and 36, such as representative KAPTON dielectric layer 70', representative ULTEM adhesive layer 72', and representative metallization layer 76'. Preferably, a final dielectric layer 78, such as KAPTON, is formed to cover the overall structure.

FIG. 2 depicts a typical CNC milling machine 90, such as may be used to form cavities 24, 26 and 28 in the ceramic substrate of FIG. 1. The illustrated milling machine is a Dyna Myte model DM2800 manufactured by Dyna Mechtronics, 926 W Maude Avenue, Sunnyvale, California. The machine is capable of precision three-axis movement of a rotating tool 92 in order to mill a work piece (not shown) placed within a work piece holder area 94. Although the DM2800 CNC milling machine is intended for milling metal, in accordance with the present invention the machine has been found suitable for milling ceramic HDI substrates, when appropriately programmed.

FIG. 3 depicts a typical HDI substrate 100 in plan view as the substrate 100 may be represented, for example, on a computer video display. The extent of substrate 100 of FIG. 3 corresponds to the outer boundaries of the FIG. 1 substrate 22. Also shown in FIG. 3 are the locations of a plurality of integrated circuit chips 102, individually designated "1" through "36". In FIG. 3 the locations of chips 102 are shown by dashed lines; on a computer screen they may be indicated using lines and numbers of a particular color, for example, light gray. The chips placement is provided by a circuit designer in an arrangement as shown in FIG. 3, which best suits circuit topology. In order to allow for inaccuracies in a "pick and place" machine which places individual chips 102 within cavities on substrate 100, a certain minimum distance, for example 0.400 mm (15.75 mils) is maintained between neighboring chips 102. (This minimum distance between chips is less than twice the 0.254 mm (10 mil) allowance by which cavity dimensions exceed chip dimensions on each side. Thus cavities may overlap.)

Although not depicted in FIG. 3, the locations of chips 102 also determine the locations and dimensions of a set of cavities corresponding to the chips on a one-for-one basis. As discussed hereinabove with reference to FIG. 1, and in accordance with established design rules, each individual cavity is larger than the chips contained therein, and the cavities may overlap (encroach upon each other).

APPENDIX A is a printout of an "information file" as may be produced by an HDI computer aided design (CAD) system employed by a circuit designer in determining placement of, and interconnections between, chips 102. The APPENDIX A information file is generally representative of the chip arrangement depicted graphically in FIG. 3, and the file itself constitutes a data structure.

Thus, initially considering the second part of APPENDIX A (following the double horizontal line) beginning with the column heading "Chip #", the first column identifies individual integrated circuit chips by chip number "1" through "36". The second column heading "Name" identifies the part number for the particular chip. The third and fourth columns contain information not directly relevant to the present invention, namely, the relative orientation of each chip on the substrate, and the tool to be used by the "pick-and-place" machine to place the chip on the substrate, selected in accordance with the overall size of the chip.

The next five columns are the relevant locations and dimensions of the individual chips. Thus, the two columns identified as "Center" provide the x- and y coordinates of the center of each of the chips relative to a mill fiducial, while the three columns labeled "Dimension" give the x-axis, y-axis and z-axis dimensions of each of the chips. It will be appreciated that the z-axis dimensions, that is the numbers in the column beginning with representative entry 0.390, are the thickness of each of the chips in mm.

The final column headed "Pocket" in the second part of APPENDIX A identifies the pocket or cavity number initially assigned to each of the chips. The pockets or cavities initially correspond to the chips on a one-for-one basis and, as a matter of convenience, are initially assigned numbers identical to the chip numbers.

Considering now the first part of APPENDIX A, the "information file" begins with file header information, followed by locations and dimensions of the initial set of cavities corresponding to the chips on a one-for-one basis. Comparing the first part of APPENDIX A with the second part of APPENDIX A previously discussed, it will be seen that each pocket or cavity has the same center position as the corresponding chip, but the x-axis and y-axis dimensions are greater in accordance with the design rules as discussed hereinabove. However, the z-axis dimensions or depth of the pockets or cavities are identical to the chip z-axis dimensions, so that the chip upper surfaces lie in a common plane with the upper (unmilled) surface of the substrate, as discussed hereinabove with reference to FIG. 1. (Actually, the z-axis dimensions may be adjusted to account for the thickness of the adhesive layer which secures the chips to the substrate, typically 0.0254 to 0.0508 mm (1 to 2 mils).)

The final column in the first part of the file printout of APPENDIX A identifies the number of chips per pocket. Initially, since the cavities correspond to the chips on a one-for-one basis, there is only one chip per pocket.

FIG. 4 is comparable to FIG. 3, except that it depicts the cavities corresponding to the chips of FIG. 3. To provide a useful on-screen computer display, different cavity depths corresponding to different chip thicknesses are represented in different colors. In an actual on-screen display corresponding to FIG. 4, the outer boundaries of the represented cavities 104 are shown in white lines, and overlap or encroachment of one cavity into another is evident. In the on-screen representation, a color representing a relatively deeper cavity has precedence over a color representing a relatively shallower cavity. Thus, where cavities overlap or encroach on each other, the area of overlap is indicated as the color of the relatively deeper of the two cavities, although the outer boundaries of all cavities are shown in white. Also, the actual chip locations 102 of FIG. 3 would be shown in gray. However, for clarity of illustration these are omitted from FIG. 4.

Referring to FIG. 4 and APPENDIX A together, the thickest chips and therefore deepest cavities are numbers "5" through "12" and "25" through "28", which are all lined arbitrarily to indicate the color pink, for example. Although cavities "5" through "12" have a depth of 0.534 mm, and cavities "25" through "28" have a slightly different depth of 0.532 mm, these different depths are within a predetermined tolerance (e.g., .+-.0.127 mm) of each other, and are treated as identical for purposes of display.

The next shallower cavities are cavities "13" through "20" which are lined arbitrarily to indicate the color orange, for example. Each has a depth of 0.445 mm.

Continuing in order of decreasing thickness and thus cavity depth, lined arbitrarily to indicate the color blue are cavities "1" through "4" and "33" through "36". Again, and with reference also to APPENDIX A, two different actual depths 0.390 mm and 0.391 mm are predetermined tolerance of each other, and are treated as the same depth for the purpose of the representation.

Finally, the shallowest cavities for the thinnest chips are numbered "21" through "24" and "29" through "32", and are lined arbitrarily to indicate the color green. Again with reference to APPENDIX A, it will be seen that two different chip thicknesses 0.282 mm and 0.270 mm are treated the same for purposes of this representation.

FIG. 5 shows a graphical command interface which appears on the computer screen to the right of either FIG. 3 or FIG. 4 to facilitate user communication with the program when performing steps in accordance with the method of the invention. This graphical command interface permits enhancement of the FIG. 4 representation to depict locations and dimensions of cavities of an optimized set. In FIG. 5, the large box 106 has various program functions labeled, and these functions are selected by positioning a cursor 108 by means of a mouse, and "clicking" on the function. Various ones of these functions are described in detail hereinbelow.

Area 110 is lined for color, and is a key or reminder indicating the relative depths signified by each of the assigned colors. Thus, the relatively deepest cavity depth is represented by the color pink at the lower portion of key 110, and the relatively shallowest depth is represented by the color green at the top of key 110. Actually, FIG. 5 is somewhat abbreviated in this regard, as in the actual program implementation there are nine different colors to represent different cavity depths. This is the number of colors that can easily be called by the "C" language "fill" routine.

FIG. 6 is comparable to FIG. 4, but illustrates the results of a "combine pockets" operation whereby the representation is enhanced by combining overlapping cavities to define a single cavity. By recognizing and combining such overlapping pockets, the efficiency of the milling procedure is maximized.

Specific criteria for a "combine pockets" operation are as follows:

(1) The two cavities overlap (encroach on each other;

(2) The two cavities line up exactly in either the x or y direction. In terms of the x- and y-coordinates of the cavities, this means that either:

(a) The x-coordinates of the center of the two cavities are equal and the width (x dimension) of the two cavities are equal; or

(b) The y-coordinates of the center of the two cavities are equal and the height (y dimension) of the two cavities are equal; and

(3) The depths of the two cavities are within.+-.0.127 mm (.+-.0.5 mil) of each other.

Applying these criteria, as one example, cavities "5" and "9" of the initial set shown in FIG. 4 are combined into a single cavity "5" of the enhanced set, as depicted in FIG. 6. The following table indicates the complete results of the "combine pockets" operation:

The steps involved in a "combine pockets" operation as depicted in FIG. 6 are described in greater detail hereinbelow with reference to FIGS. 12 and 13.

Another operation involved in enhancing the representation to represent locations and dimensions of cavities of the optimized set is a "remove borders" operation (designated "REMOVE BDR" in FIG. 5) whereby walls separating neighboring cavities are selectively removed. In particular, walls having less than a predetermined wall thickness are removed by extending at least one of the cavities to meet another cavity. Usually, the relatively shallower cavity is extended to meet the relatively deeper cavity. FIG. 7 diagrammatically depicts criteria for border removal, while FIGS. 8 and 9 are "before" and "after" representations, respectively, illustrating the "remove borders" operation .

There are two criteria which must be satisfied before borders or walls are removed by adjusting pocket dimensions:

(1) The wall or border between two adjacent cavities must be less than a predetermined minimum thickness specified by the user, for example, 0.2 mm (7.9 mils); and

(2) The cavities must be at least partly aligned with each other such that the x or y dimension (depending on the side) of one cavity either partially or fully overlaps that of the other. Thus, unlike the "combine pockets" operation, for the "remove borders" operation alignment between the adjacent cavities need not be exact .

FIG. 7 depicts several arbitrary "A" and "B" pairs of adjacent pockets, illustrating various situations where the foregoing criteria are applied. In FIG. 7, pairs 121, 122, 124, 125 and 127 are candidates for border removal, while pairs 123 and 126 are not, since their x or y dimensions do not overlap.

Referring now in detail to the "before" and "after" border removal depictions of FIGS. 8 and 9, each of these FIGS. is an enlargement generally corresponding to the lower right-hand corner of FIG. 6, showing pockets "15", "19", "23" and "27" of the enhanced set, as well as portions of cavities "3", "7" and "11" of the enhanced set. FIGS. 8 and 9 are lined for color as are FIGS. 4 and 6, with the boundaries of the individual cavities indicated with heavier lines, which would typically be white lines on an on-screen display. FIGS. 8 and 9 also show the dashed-line outlines of the individual chips 102, as described hereinabove with reference to FIG. 3, which outlines would typically be gray lines on an on-screen display. It will be appreciated that combined cavity "11" of the enhanced set contains chips "15" and "19", and combined cavity "7" of the enhanced set contains chips "7" and "11".

In the portion of the layout representation shown in FIG. 8, each of cavities "19", "23" and "27" is a candidate for border removal with reference to cavity "11" above and also with reference to cavity "7" below, in accordance with the criteria described hereinabove. However, the wall or border between cavity "19" and cavity "11" above is thicker than the 0.2 mm (7.9 mil) minimum allowable border width, as is the border or wall between cavity "19" and cavity "7" below. In the case of cavities "23" and "27", the respective walls or borders between each Of these cavities and cavity "11" above is equal to or less than the 0.2 mm (7 .9 mil) minimum border width, as are the walls or borders between cavities "23" and "27" and cavity "7" below.

Accordingly, as shown in the "after" depiction of FIG. 9, cavities "23" and "27" are extended to meet cavities "11" and "7", while cavity "19" remains unchanged. Each of cavities "23" and "27" is shallower than either of the adjacent cavities "11" and "7", as indicated by the on-screen color coding as discussed hereinabove.

FIG. 10 represents an on-screen display whereby the user of a program can interactively select cavity corners where relief is to be provided. Corner relief is necessary in some instances because the actual milling tool has a certain minimum radius such that the corners of cavities 104 are not square. Thus, the boundaries of the cavities are slightly extended as indicated by corner relief symbols 130. Where the corner of a relatively deeper pocket overlaps (encroaches) into a relatively shallower pocket, generally corner relief is provided for the relatively deeper pocket.

FIGS. 11-19 are a set of flow charts representing program instructions of a computer program implementing the subject invention, named the "mill" program.

Complete "C" language source code for the "mill" program represented by the flow charts of FIGS. 11-19 is included in the microfiche Appendix hereto. This version of the "mill" program runs on an IBM-PC, with EGA or VGA graphics.

FIG. 11 is a top level flow chart depicting the overall structure of the "mill" program. The program begins with initializing and setup steps, and then waits for a mouse command as indicated by a series of steps identified generally along the left edge of the FIG. 11 flow chart generally corresponding to the graphical interface described hereinabove with reference to FIG. 5. Particularly relevant in the context of the present invention and shown in FIG. 11 are the "combine pockets" operation begun at step 140 (manual combine) or step 142 (automatic combine), respectively selected by the "COMBINE" and "AUTOCOMBINE" buttons on the FIG. 5 graphical interface, and the "remove borders" operation, begun at step 144 of FIG. 11, selected by the "REMOVE BDR" button on the graphical interface. The ultimate step of generating CNC program instructions is begun at step 146 of FIG. 11, and is selected by the "CODEGEN" button on the FIG. 5 graphical interface. As indicated by steps 148, 150, 152, 154 and 156, the flow charts of FIGS. 12, 13, 14, 15, 16a, 16b and 16c provide further details of particular operations. The flow charts of FIGS. 17a and 17b, 18 and 19 likewise provide further details of operations indicated in the flow charts of FIGS. 16a, 16b and 16c, respectively.

When the user selects the manual "combine pockets" operation of step 140 of FIG. 11, the user, viewing the onscreen display and based on judgment, at steps 160 and 162 selects two cavities to be combined. At step 148 of FIG. 11, the flow chart of FIG. 12 is referred to for the actual operation of combining the two selected pockets. Alternatively, if the user selects auto combine at step 142 of FIG. 11, the next step 150 refers to the flow chart of FIG. 13 to determine which pockets are to be combined. FIG. 13 in turn refers to the flow chart of FIG. 12 for performing the actual operation of combining the cavities once selected.

Thus, the user may either manually select cavities to combine, or request that the program automatically select and combine any or all cavities which meet the criteria specified hereinabove. If so requested, the program compares each cavity in the data structure represented in APPENDIX A to every other cavity, applying these criteria. If two cavities meet the criteria, then they are combined and the data structure is updated to reflect the combination. Assuming that two cavities arbitrarily designated "A" and "B" are to be combined, the data structure entry for one of the cavities ("A" or "B") is modified, and the other entry is deleted from the data structure after the entry for the combined cavity is updated. (Since the data are stored as a list of data structures, the first entry in the list is retained.)

As indicated by the program flow chart steps of FIG. 12, the cavities are combined in the following manner:

(1) The upper left corner of the combined cavity is set equal to the upper left corner of the leftmost of cavities "A" and "B".

(2) The lower right corner of the combined cavity is set equal to the lower right corner of the rightmost of cavities "A" and "B".

(3) New x and y dimensions (width and height) are calculated from the x and y coordinates of the new upper left and lower right corners, and are supplied into the data structure array to replace the first entry.

(4) The x and y coordinates of the new center of the pocket are calculated and are supplied into the array at the same location.

(5) The depth of the cavity is set equal to the shallower of the depths of cavities "A" and "B".

(6) Other data structure items which depend on these new dimensions are updated.

(7) The list of chips which are included in the resulting cavity is set to the combined lists of chips in cavity "A" and chips in cavity "B".

(8) The second data structure array entry is deleted.

(9) The data structure array entry for each chip in the new combined pocket is updated to place the chip in the new pocket.

When the user selects the "remove borders" operation, as indicated by step 144 in FIG. 11, at step 160 the program prompts the user to enter the minimum border width, which typically will be 0.2 mm (7.9 mils). Then, as indicated by step 152 in FIG. 11, all overlapping borders with less than the minimum width are removed in accordance with the flow chart of FIG. 14, which implements the operations generally described hereinabove.

To provide useful output information, the final step is to generate CNC program instructions, which is accomplished when the user clicks on the FIG. 5 "CODEGEN" button, to perform step 146 of FIG. 11. At step 162, the user is allowed to specify pocket corner relief as discussed hereinabove with reference to FIG. 10. Then, at step 154, the program instructions represented by the flow chart of FIG. 15 are executed, whereby various items of information are entered into the program, as indicated.

Finally, as indicated generally at step 156, the actual CNC program instructions are generated.

By way of example, APPENDIX B is a print out of actual CNC program instructions generated by the mill program in the language of the DM2800 CNC milling machine.

FIGS. 16a, 16b, 16c, 17a, 17b, 18 and 19 show the various program operations in generating the actual CNC program instructions in accordance with the invention. Program source code is provided in the microfiche appendix.

The flow charts assume that several milling tools will be used, for example three tools, starting with the tool of relatively largest diameter (e.g. 2.515 mm), then the tool of intermediate diameter (e.g. 1.499 mm), and finishing with tool of relatively smallest diameter (e.g. 0.991 mm). The tools employed are end mills comprising solid steel cylinders, with a diamond abrasive powder coating the cylindrical surface and flat bottom of the tool. As a practical matter, the abrasive powder coating produces a slight edge radius at the lower end of the tool.

In the generated CNC program instructions, a number of techniques are employed to produce an optimum finish when milling ceramic, while minimizing tool wear. For example, when forming a cavity, the tool path is a series of rectangular spirals at increasing depths from the center out (using the CYCLE XY instruction in the particular language of the DM2800 CNC milling machine). This may be referred to as a "spiral out" cut. Conventional practice when milling a rectangular pocket in metal is to specify a tool path which spirals from the outside in. Moreover, the direction of the "spiral out" cut is selected in view of the direction of tool rotation such that cutting debris is directed away from the tool to minimize tool wear.

To provide a smooth bottom finish, there is a final cleanup cut spiraling from the outside in (a "spiral in" cut) at the final depth (z-axis position) of the last "spiral out" cut. This "spiral in" cleanup cut at the final depth is in the opposite direction along a path which is shifted so that each path segment of the final "spiral in" cut straddles two path segments of the previous "spiral out" cut.

Similarly, a frame cut to precisely form the outer boundaries of a given cavity is done as a final step after the cavity itself has basically been formed.

Another technique employed is a "zig-zag" back and forth movement when moving the tool down in the z-axis dimension. In other words, the tool is not simply plunged down to each successive depth.

For more efficient tool movement, cutouts of rectangular cavities are started in the longer direction.

The flow charts assume that several milling tools will be used, for example three tools, starting with the tool of relatively largest diameter (e.g. 2.515 mm), then the tool of intermediate diameter (e.g. 1.499 mm), and finishing with the tool of relatively smallest diameter (e.g. 0.991 mm). The tools are end mills, with a slight edge radius.

While specific embodiments of the invention have been illustrated and described herein, it is realized that numerous modifications and changes will occur to those skilled in the art. It is therefore to be understood that the appended claims are intended to cover all such modifications and the changes as fall within the true spirit and scope of the invention.