Figure 1. A few primitive features.
(a) Electronic Data Systems-Unigraphics Division, CAM-Development, 10824 Hope Street, Cypress, CA 90630. InterNet: jan@edsug.com
(b) Programmable Automation Laboratory, Computer Science Department and Institute for Robotics and Intelligent Systems, University of Southern California, Los Angeles, CA 90089-0781. InterNet: requicha@lipari.usc.edu
This article appeared in the book: J. Shah, D. Nau and M. Mäntylä, Eds. Advances in feature based manufacturing , North Holland: Elsevier, 1994.
Note: This web pages is still under construction as not all symbols transferred correctly.
Machining process planners, both humans and automata, reason in terms of features such as holes, slots and pockets. Some of today's CAD systems provide capabilities for defining objects through features. But these are essentially shape macros. They are not guaranteed to be machinable, and often do not correspond directly to machining features. To establish a bridge between CAD and CAM systems, machining features must be automatically recognized.
Spatially interacting features are a major source of difficulties in feature recognition. Feature interferences alter the face and edge patterns associated with the features. This complicates both the identification of the features in a part, and the derivation of all the data about the features required for automated manufacturing planning.
This paper discusses the geometrical aspects of an automatic feature recognizer recently developed at the University of Southern California for the domain of parts that can be machined on 3-axis machining centers. The recognizer is implemented in an environment consisting of the KnowledgeCraft(TM) AI shell coupled with either the Parasolid(TM) or the PADL-2 solid modelers, and running on Sun workstations. It automatically produces feature removal volumes and representations for feature interactions. The recognizer's ability to deal with interacting features is due mainly to an operation called feature completion, described in this paper. Completion is a surface-to-solid transformation. It produces the largest volumetric feature that is machinable and compatible with its traces present in the object's boundary.
This paper concentrates on one of the early steps of manufacturing planning: decomposing the object into a set of volumes called machining features (henceforth called simply features) associated with distinctive machining processes. These features must satisfy certain validity constraints--discussed in Section 3--to ensure that they are machinable. The feature representations should also contain information to facilitate spatial reasoning by the downstream planning stages.
Our starting point is a pair of boundary representations (BReps), one for the desired part and the other for the stock. A BRep can be derived regardless of which solid product definition technique is used, and is provided by virtually all solid modelers. Therefore we make no assumptions on how the object is designed. We also have no restrictions on how the manufacturing features interact, how the part is set-up, and in which sequence the features are machined. We believe that the latter two issues are the responsibility of a set-up and process planner, which manipulates the information derived by the feature finder.
We use a "generate and test" strategy based on feature hints. The architecture supports hints generated from a variety of sources, although we have focused most of our efforts on generating feature hints directly from the BReps of the object and stock. A (BRep-generated) feature hint or clue is a characteristic trace left by a feature on the boundary of a part. Other good sources of hints are tolerance specifications (e.g., a parallelism tolerance between two faces indicates the possible presence of a slot), attributes (e.g. a thread), and certain design features (e.g., holes). In fact, we could use as hint generators most of the existing feature recognizers, which can neither handle general interactions nor guarantee the machinability of their features. We can also accommodate feature mappers, which attempt to associate machining features directly with design features (e.g., associate a slot to two parallel webs) [Shah et al. 1990]. Certain design features are easy to map into machining features, but the general mapping problem seems to be very difficult. It is likely to require a very large number of special-case mapping rules to be industrially useful, and it may be impossible to guarantee that all cases are accounted for. In our approach we can use simple cases of feature mapping to generate hints, and leave completeness issues to the recognizer, which is capable of producing all the missing clues solely from BRep information. Regardless of the hints' origins, they undergo additional processing to validate their machinability and to infer information required for the downstream planning stages.
The search process does not rely on features to be found in any specific sequence. We believe this is a question of search strategy efficiency (e.g., find "likely" features first), which does not affect the ultimate set of features found, including all alternative decompositions.
Once a trace of a particular feature has been found, we complete the feature by extending it in one or more directions without intruding into the part. The goal is to produce the largest volumetric feature that is compatible with the available data. Feature completion is a general method to deal with feature interactions. It associates volumes to (partial) boundary data, "reconnects" portions of a feature that were split due to interactions, and produces accessibility information. The completion process also segments features into optional and required portions to represent interactions with other features.
Finally, we verify each feature by checking whether it satisfies all the machinability conditions. This is necessary because a feature may have been based on a faulty hint. The recognition process continues until it produces a complete decomposition of the volume to be machined. A side effect of this recognition strategy is that alternative feature decompositions are also found.
A prototype feature recognizer was built using the PADL-2 modeler [Brown 1982] and the LISP-based KnowledgeCraft(TM) (KC) AI environment, tightly coupled through foreign-function calls [Vandenbrande 1990]. The current, modified version also operates with the Parasolid(TM) modeler, and handles all the modeler-KC interface through Unix inter-process communication. Symbolic reasoning and search is done in KC, whereas geometric processing is performed by the solid modeler upon request from KC's reasoning process.
The recognizer's architecture and symbolic processing are well described in [Vandenbrande and Requicha 1993]. Here we focus on feature completion, which is primarily a geometric operation and the key to the recognizer's ability to handle feature interactions. The remainder of the paper is organized as follows. Section 2 is a brief overview of the literature on feature recognition. Section 3 is concerned with the input and output of the feature completion process, and provides the background necessary to understand Section 4. It introduces the types of features and associated properties we consider in this work, discusses hint generation, and the representation of feature interactions. Section 4 is dedicated to the feature completion process, and is the main contribution of this paper. First one dimensional completion is described, followed by its two dimensional counterpart. Section 5 discusses the implementation. The final section summarizes the paper and suggests directions for future research.
Much of the previous research is based on linguistic methods such as syntactic pattern recognition applied to face and edge patterns. Feature recognition shares many problems with computer vision. For example, both must deal with incomplete data. In computer vision incompleteness is due to occlusions, whereas in feature recognition it is due to spatial interactions. Syntactic pattern recognition has proven largely ineffective in 3-D computer vision, and we suspect that it may also be inherently unsuited for recognizing interacting features.
We opted for a completely different approach, which is closest in spirit to a recent development at Purdue [Marefat & Kashyap 1990]. The Purdue work was conducted independently from ours and at about the same time. It attempted to treat general feature interactions, and led to ideas such as generate-and-test and face extension that are similar to ours. Marefat and Kashyap define features as graphs and deal with feature interactions by computing "virtual links", which are akin to edges of intersection between extended or "unified" faces. Unlike ours, the Purdue recognizer caters only to polyhedral objects, does not consider accessibility, and does not produce volumetric features. It also does not appear to be able to recognize pockets with arbitrary contours that include concave edges and islands.
The research by Karinthi and Nau at the University of Maryland [Karinthi 1990] does not address the problem of feature recognition, but develops techniques for producing alternative decompositions into volumetric features. Combining their feature algebra with our required/optional classification of features--discussed in Section 3--might provide powerful tools for exploring alternative interpretations of a part.
We consider two types of features: solid and surface features. A machinable solid feature is a connected solid that can be removed in a single machining operation, in a single setup. A machining operation, however, may consist of several passes (e.g., rough and finish) with one or more cutters. A surface feature is a set of faces (or "sub-faces") that result from subtracting a volumetric feature from an evolving workpiece. It is a subset of the boundary of the part and of the boundary of the associated solid feature.
The delta volume is the material that must be removed, and is defined as the Boolean difference between the stock and the desired part. The goal of the feature recognizer is to find a set of solid features that contains the delta volume. Observe that the union of all the features may be slightly larger than the delta volume, because the volume swept by a cutter may be larger than the amount of material removed.
We define a set of primitive features plus rules to combine them into more complex shapes called composite features. Primitive features either correspond to elementary volumes typically created by a series of cuts from a particular class of machining operations (e.g., a cylinder is a primitive hole) or are chosen for convenience, and do not necessarily represent physically machinable entities by themselves (e.g., semi-cylindrical slot ends). The latter type of primitive feature occurs only in combination with other primitives.
We subdivide our primitive features into several classes, each class roughly corresponding to the degrees of freedom (DOF) of the cutter motion (see Figure 1 for several examples). For example, 1-DOF features are made by plunging a cutter along its axis to produce holes; 2-DOF features are made by plunging and sweeping the cutter along a specific trajectory to produce features such as slots; and 2.5-DOF features are made by plunging a cutter and then clearing an area to produce pocket-like features (e.g., open and closed pockets, slabs, and steps).
Figure 1. A few primitive features.
For a solid feature to be machinable, it must satisfy several validity conditions. First, the feature must not intrude into the desired part, i.e., the regularized intersection of the feature and the part must be null. This is the non-intrusion condition. Second, the feature must contribute a meaningful portion to the part boundary. This is the feature existence or presence condition, which will be discussed in greater depth below because feature hint generation relies on it. Third, the feature must be accessible along certain directions to allow a cutter to enter the feature volume and to maintain enough clearance for the cutter, shank and spindle during cutting. Each feature type therefore has its own accessibility criterion, which consist of a set of directions along which the cutter/machine assembly can move without colliding with the part. Figure 1 shows the accessibility directions for the primitive features shown. For example, a 2.5-D pocket must be accessible along the tool axis direction.
The accessibility rules are also crucial for feature categorization because certain solid features are geometrically identical but differ in accessibility and in machining method. For example, 2.5-D pockets are subdivided into closed pockets (plunge only), open pockets (one or more side entrances exist), steps (accessible from 3 sides), and slabs (entirely wall-less).
Finally, the parameters of a feature must satisfy certain numerical constraints to ensure manufacturability (dimensional rules). For example, cylinders with large diameters are not drilled, and therefore not considered holes. A feature that passes all our validity conditions is called a valid feature.
Hint generation based on presence rules is crucial to ensure that all necessary hints are produced, and that no recognizable features are missed. The following informal argument shows that presence-based hints ensure that the recognizer is complete in the following sense; for any part that can be described by our set of features, the system will produce a decomposition into valid features. (A similar argument is reported in [Regli & Nau 1993].)
Suppose that a delta volume can be decomposed into a set of valid volumetric features. Now extend each feature by using the completion procedure described in Section 4. The result is a new set of features, each of which is also valid and is not smaller than the original, non-completed feature. The set of completed features also corresponds to a decomposition of the entire delta volume into valid machinable features. Since the original features are valid, they leave in the part traces (surface features) that satisfy the appropriate presence rules. If the recognizer always generates a hint when there is a face pattern that satisfies the presence rules for a feature, and if the completion mechanism extends features correctly, the system will generate a decomposition into valid completed features. Note, however, that we may not obtain the original features, and that additional features may be found. These correspond to alternative decompositions of the delta volume.
To represent volumetric interactions, each solid feature is subdivided into required and optional portions. The required portions correspond to the subset of the volumetric feature that must be manufactured by a process associated with the feature, so as to produce the corresponding surface feature in the part. The optional portions correspond to the volume of the feature that is shared with other features (and in some cases, with empty space as well). Optional portions may be removed by machining the feature itself, or as a side effect of machining nearby features.
The definitions of required and optional portions reflect properties of machining. For example, a drill can only plunge or retract along the axis of a cylindrical hole. The volume removed is axis-symmetric and therefore bounded by planar halfspaces perpendicular to the axis. These planes indicate the positions where the tool starts and stops cutting, even though the corresponding surface feature may not have planar orthogonal boundaries (Figure 2). Note also in the figure that the required portions include the entire surface feature plus some additional material that does not contribute to part faces. Thus, the required portions represent the minimal volume the cutter must sweep to generate the corresponding surface feature.
Figure 2. Optional and required portions of a hole.
Required and optional volumes provide supplemental information that facilitates geometric reasoning for planning. Several examples are presented below to illustrate the power of this idea. Although a hole is used throughout the examples, similar reasoning is applicable to other feature types.
In Figure 3, the optional volume of the hole corresponds to the portion that is shared by the adjacent feature X. The hole can be machined starting at the top of X thereby cutting the optional volume in feature X. (Holes are often drilled first in pockets to provide access for another tool and to reduce wear on that tool.) Alternatively, the hole can be machined starting at the floor of X, if X was cut previously. The process planner can choose the most appropriate sequence. In addition, because these optional/required regions are solids, a process planner can apply geometric tests to an in-process solid model to determine which optional portions of each feature still require machining.
Figure 3. Start of hole is affected by interfering feature X.
In Figure 4, the optional volume of the hole indicates how much a drill may overshoot into the adjacent feature.
Figure 4. Permissible cutter overshoot.
This is important in manufacturing since many features require a cutter to overshoot into adjacent features (or air) because of cutter geometry or to avoid burrs and thin walls. For example, through-holes are commonly made by drills with conical tips. Making a through hole as if it were flat bottomed is unnecessary and costly.
In Figure 5, the optional portion of the hole spans the cavity created by the intersecting feature X. Spanning a large gap with a drill may cause excessive tool deflection resulting in inaccurately produced holes or even tool failure. To prevent this, the hole should either be manufactured before the cavity, or made as two individual features. A user-specified distance may be needed to define what is meant by "a large gap". Tolerancing information may also be able to resolve the conflict. If the alignment of the two holes is important (e.g., for guiding a shaft), and the total length is not too large, the two holes should be made in a single operation before the adjacent feature. Because information on the interaction is explicitly provided through the required/optional parts, reasoning by a planner is facilitated.
Figure 5. Center portion of hole interferes with feature X.
The cross-section of a set extension is its intersection with a surface orthogonal to the sweep trajectories. For linear and circular extensions the cross-sections are planar, and for radial extensions they are cylindrical. A maximal linear extension of a planar cross-section is a semi-infinite slab that corresponds to an extension with semi-infinite linear trajectories. A maximal radial extension produces either a semi-infinite solid with a cylindrical hole (for "outward" extensions), or a solid cylinder (for "inward" extensions). A maximal circular extension is a solid of revolution.
Observe that all the volumetric features we consider can be defined as extensions of suitable cross-sections. Furthermore, the cross-sections are easy to compute from the surface features that are guaranteed to exist by the presence rules. For example, a hole's cross-section can be recovered from any 2-D portion of its cylindrical surface. This implies that maximal extensions can be computed from the traces left by a feature on the boundary of the part or the delta volume. This is a crucial operation for feature completion, which we discuss next.
Figure 6. 1-D feature completion.
A cylindrical half-space VS(*) is the maximal extension of the cross-section of the feature hint S1 along the specified axis directions. For template features such as holes, slots and grooves, extending the features is simple because it amounts to increasing one of the feature's parameters.
The unbounded cylindrical half-space VS(*) is intersected with the Stock to create a finite solid. (Note that the terminating half-spaces are not orthogonal to the cylinder's axis.) Next, the solid volume is enclosed by a minimal-length cylinder. The ends are orthogonal to the axis and correspond to the starting and ending positions for a rotating cutter. Then the Part is subtracted from this volume to eliminate all the portions that intrude into the object.
Several disjoint volumes may result. The connected components are extracted. For each of the connected components, the maximal-length cylinder that is totally enclosed by the component is computed.
In Figure 6 the hint S1 produces two disjoint primitive volume features V1 and V2. V1 is associated with the original hint, whereas V2 is linked with another hole surface feature S3. The initial hint S1 is connected with S2 because of the extension process. S1 and S2 are separated in the Part boundary because of the interaction with the inner groove. V1 terminates at the conical surface because the largest primitive hole is fit within the part without intruding, and without altering vital parameters such as the diameter. The volume feature must always remain in contact with a portion of the original hint to ensure that the boundary of the volumetric feature includes the corresponding surface feature. V1 and V2 both extend beyond the original delta volume, and include regions of empty space outside the stock. Such regions, however, must be swept by a cutter when the holes are machined.
Information on accessibility can be derived from feature extension with some additional reasoning. Both V1 and V2 penetrate through the Stock. Because no material exists beyond the top of V1 in direction A1 and beyond the bottom of V2 in direction A2, both of the features are accessible along those directions. Part intrusion testing is not necessary because the volume features that are generated are non-intrusive by construction.
One-dimensional completion is easy to generalize to other types of features. Slots, grooves, pockets and profiles also are completed in 1-D along the cutter axis direction. Slots and grooves undergo a second 1-D completion operation along the feed trajectory, while pockets undergo a 2-D completion process explained below.
Figure 7. Extracting required portions.
The optional volumes are obtained as shown in Figure 8. First, the required portions are added (by set union). Then, the result is subtracted from the whole feature, and the connected components are computed.
Figure 8. Extracting optional portions.
Instead of using the Part and Stock, we use the delta volume and label it by attaching to each of its faces information about the face's origin (i.e., whether it is a Stock or Part face). The maximal, minimal and connected component computations are performed simultaneously by a "feature classifier", which also extracts the volume's required and optional portions and produces information on accessibility.
Feature classification involves segmenting the intersection of the maximal extension with the labeled delta volume, and assigning one of the classification values discussed below to each segment. All of the information needed for feature completion is inferred from the classification results. Segmentation is performed by introducing cross-sectional surfaces (see Section 4.1) with respect to a set of directions specific to the type of feature being completed.
Segmentation "slices" the volumetric feature orthogonal to the extension trajectories. The separation surfaces are computed in two steps. First, we consider only the primary faces of the feature. These are the subsets of the boundary of the maximal extension that are "aligned" with the extension trajectories and are faces of the intersection of the maximal extension with the delta volume. For example, the cylindrical face of a hole, the two parallel planar faces of a linear slot, or the wall faces of a pocket are primary faces. The second step takes into account secondary faces, which are Part faces that intrude into the maximal extension but are not in its boundary.
Adjacency information is exploited heavily in the computations for primary faces. The interactions between primary faces and other faces that intersect them provide all the information necessary to segment (slice) the features and produce an initial classification for each slice. (The term "classification" is used because of the similarity of the associated procedure with set membership classification [Tilove 1980].)
Let us assume initially that the interaction of a primary face with another face is confined to a range in the extension trajectory where no other interactions occur. For each primary face, we proceed as follows. We begin with a portion of the primary face that is a Part face, and we label it ON (meaning that it contributes to the boundary of the delta volume). Then we conceptually traverse the primary face, moving along the extension trajectory. (This process must be performed both for the positive and negative directions associated with the extension.) When we encounter another Part or Stock face that intersects the primary face, we reason as shown in Figure 9. The delta volume is the shaded area in the figure.
In Figure 9 (a) the ON portion of the primary face meets another face at a concave angle (with respect to the delta volume). This implies a transition from ON the boundary to IN the delta volume. A separation surface is introduced at the furthest point of the intersection. This implements the minimal enclosure operation needed to compute the required portions of the feature.
Figure 9. Feature classification.
In part (b) of the figure, an ON portion of the primary face terminates in a stock face at a convex angle. A separation surface is positioned at the furthest point of the stock face. This implements the minimal enclosure operation. The slice that follows is labeled OUT-S to indicate a transition to out of the delta volume and out of the stock.
The next illustration, (c), shows a transition into part material. Any continued cutter motion beyond the transition point would result in invasive machining. The separation surfaces are positioned at the nearest point of the intersection and the transition is called OUT-P (out of the delta volume and into the part). A similar strategy is used for secondary faces (d). This implements the maximal inclusion operation and ensures non-intrusion.
If there were no other primary faces, no secondary faces, and no multiple interactions over a common parameter range along the extension trajectory, we would essentially be done. Let us consider now the case of multiple primary faces. Figure 10 shows a simple slot whose primary faces lead to different slicing results.
Figure 10. Classification results for two primary features.
After each primary face has been processed, the classification results are combined (or merged) according to the rules shown in Figure 11. These rules resemble the "combine" step of divide-and-conquer algorithms for set membership classification [Tilove 1980, Requicha & Voelcker 1985].
Figure 11. Merging classifications.
In the figure each vertical bar corresponds to a separation surface, and each horizontal segment to a subset of the feature contained between two separation surfaces. Each segment has an associated label that corresponds to a classification value. When several labels are associated with a segment a disjunction is implied. For example, the top, left segment of Figure 11 has a classification either of ON, IN or OUT-S. X and Y represent arbitrary classifications, although they usually differ from their adjacent values. The ON/X or IN/Y notations imply that X or Y need to be known before the classifications can be merged. The star in ON* or IN* indicates that a feature may be invalid and additional processing is required. (For simplicity we will ignore such additional processing in this paper--see [Vandenbrande 1990] for details.) Each rule depicts on the left two segmentations of a volumetric feature, each segmentation induced by one primary face. On the right is the result of merging the two segmentations.
The first rule in Figure 11-a is interpreted as follows. Suppose that a primary face segments the feature into two pieces as shown in the top left trace, and that the leftmost segment classifies ON. Suppose that another primary face segments the feature as shown in the second trace, with a rightmost segment also classifying ON. The two classification values agree over a common region of the feature. The result of merging these two classifications over the common region also is ON. This is shown in the central region of the trace on the right. Similar considerations apply if the classification values agree but are either IN or OUT-S. The resulting classification values for the left and right segments of the merged segmentation, where the individual classifications may not agree, cannot be computed without knowledge of the values X and Y.
The next two merging rules show the effect of the non-intrusion condition. When a face extension intrudes into the part, the corresponding portion of the extended volume is off limits to a cutter regardless of the classification values for other primary faces. The rule in Figure 11-(d) determines the feature's required portions. In the central region of the merged segmentation, one of the primary faces is coincident with the surface feature, while the other is either IN the delta volume or OUT of the delta volume and stock. The required portion must include the entire surface feature. Therefore the feature slice is either ON or invalid, and additional analysis is needed for that region [Vandenbrande 1990]. The final rule (e) combines an IN classification with an OUT-S value. The result is IN or invalid because a cutter's sweep needs to span the entire volume to be removed. Let us turn now to multiple interactions and secondary faces (Figures 12 and 13).
Figure 12. Multiple interactions.
Figure 13. Secondary faces.
Multiple interactions are relatively rare. Figure 12 shows a simple but contrived example when two or more faces interact with a primary face simultaneously, over the same parameter range along the extension trajectory. We treat each face interaction separately, construct a segmentation and then merge all the segmentations, as if we were dealing with several primary faces.
Secondary faces create OUT-P regions throughout the entire parameter range they cover (see Figures 9 (d) and 13). These OUT-P slices are merged with the other classification results.
After all the classifications results are merged, the resulting list is examined. First, all the adjacent elements with the same values are merged. (The "starred" classifications are not merged because, depending on the feature type, each element may be subject to further processing.) A volumetric feature cannot extend across a transition to OUT-P because this would cause part intrusion. Therefore, the feature is split whenever an OUT-P transition is encountered. This implements the connected component operation. The split produces classification results that correspond to the connected components. The feature is globally inaccessible towards the OUT-P separation surfaces.
Required portions correspond to the ON parts, while the IN parts correspond to the optional portions. Transitions to OUT-S require further reasoning to determine accessibility and feature connectivity. For instance, the top hole in Figure 14 is accessible because no further material is present in the upwards direction. In the other direction, the upper hole is only locally accessible because of the blind hole on the bottom.
Figure 14. OUT-S segmentation.
The feature classification procedure is logically complicated but involves only one relatively expensive geometric operation: the computation of extrema for faces. This is non-trivial for certain curved faces and non-orthogonal interactions, but is similar to face "boxing" procedures used by PADL-2 and other geometric modeling systems.
Features other than holes require additional processing in conjunction with feature completion. This is done for efficiency and because the information about a feature provided by a hint may be insufficient to perform feature completion. For instance, linear slot hints consisting of parallel, opposing, planar faces do not fully specify completion directions. A slot hint consists of two faces which partially overlap when projected on each other. The most crucial data about a slot are the cutter Sweep trajectory, and the Up direction, which corresponds to the spindle's axis (see Figure 15). These parameters are necessary for further analysis (e.g., to determine accessibility), and to extract all the slots that are associated with a slot hint, because a pair of overlapping faces may contribute to several slots, as shown in Figure 15. Much of the additional processing required for slots is concerned with searching for potential floors. Details are given in [Vandenbrande 1990].
A pocket hint consists of a face in the delta volume, called the pocket's floor, that is accessible along the floor's normal direction and may be surrounded by several faces. If the floor is totally enclosed by a set of faces (including internal boundaries for islands), the pocket can completed in 1-D, along the direction of the floor's normal. More often, a pocket hint lacks a complete boundary surrounding the floor or may have uncertainties caused by depressions in the floor (e.g., an island may stick out of a depression). To create a solid feature, the pocket must be grown "laterally", by 2-D feature completion.
2-D completion differs from its 1-D counterpart in certain respects. Area clearance operations can produce almost arbitrary contours. Therefore, the computation of extrema for faces, and the minimal enclosure and maximal inclusion operations used in 1-D completion to slice the volume orthogonally are inappropriate for 2-D completion. We can use a procedure similar to 1-D completion, but without the Min and Max operators, and with the following modifications: (1) The maximal extension VS(*) is now an infinite slab (i.e., a planar half-space) with boundary normal to the specified direction and (2) only the non-intrusive connected components whose boundaries include the surface features that constitute the hint are retained.
The procedure is illustrated with Figures 16 through 18. The first figure shows a pocket hint (Face-1, shaded area) in the part, instead of the delta volume, for clarity. Hf is the underlying half-space of Face-1, and N its outward normal. The step and pocket horizontal faces are coplanar.
Figure 16. Pocket hint.
The delta volume is intersected by Hf to produce [[Delta]] f (Figure 17). [[Delta]] f has two solid connected components, one (CS(ext,1)) associated with the pocket face Face-1, the other (CS(ext,2)) with Face-3 of the Step. The shaded areas correspond to portions of the floor which are coincident with existing faces of the delta volume, and will later be marked as required.
Figure 17. Pocket floor extension.
In Figure 18, the connected component of the volume that has a face coincident with the original hint is retained. This volume is identified as a closed pocket because the only permissible entry is by plunging a cutter. The protrusion is considered an island in the new pocket. All the faces surrounding the pocket are part faces.
Figure 18. Resulting pocket volume.
Enlarging the pocket floor has several advantages. It connects it with other segments that may have been separated by depressions in the part, as shown in this example. Reconnecting the two portions of the pocket allows them to be machined in the same machining operation, if so desired. It is also beneficial for detecting protrusions, even if the protrusion sticks out from depressions within the pocket floor. Our example shows a protrusion which is considered an island, surrounded by an optional region, similar to a moat. Feature finders that are purely based on edge/face adjacency relationships (e.g. [Kyprianou 1980]) typically have problems with such situations, especially if a protrusion sticks out from multiply embedded depressions.
The BReps of the delta volume and the stock are enhanced with adjacency links, edge convexity flags and other useful information, and converted into a frame-based structure in KC. Hint generation is based exclusively on BRep information, using KC/OPS-5 rules enhanced with geometric tests performed by the solid modeler. The built-in KC/OPS-5 "lexical" mechanism for selecting rules within a Rete pattern matcher is used [Brownston 1986]. Hints from design features, tolerances and attributes are not implemented.
Hints and completed features are represented by computational structures called feature frames ("schemas" in KC terminology). A feature frame typically contains the following information:
Feature frames are organized in an object-oriented scheme with multiple inheritance to allow common methods to be inherited (Figure 19). Some primitive feature schemas inherit properties and methods from several template schemas because of their relationship to several feature types (e.g., the Cylindrical Slot and Slot End in Figure 19).
A hint is represented by an incomplete feature frame. Typically, a hint contains only information on the feature type, associated surface features, and easily derivable parameters (e.g., diameter and axis of a hole, width of a slot). Feature completion generates the missing information, if the hint corresponds to a valid feature. The desired output of the feature completer is a solid feature V with the correct position and orientation, and interferences with other features identified. The completer must also supply additional information to support subsequent feature machinability validation.
Figure 19. Primitive and Composite Feature Hierarchy.
The feature completer acts on the feature hints to extend and classify the features along the appropriate directions as described earlier. It uses LISP/KC code to perform geometric reasoning, and the modeler for geometric operations (e.g., slice the object with half spaces, or intersect volumes to detect part intrusion). These geometric operations do not rely on any specific solid representation (they can be done with either a BRep or a CSG modeler) and are accurate to within the modeler's tolerance. However, these computations consume significant amount of space and time, especially with complicated objects. Therefore heuristics are used to defer the tests until they are absolutely required or to avoid them altogether.
The remainder of this section shows a simple but interesting example. Figure 20 shows the part with the crossing slots and the recognized features. (Figures in this section, as well as recognition examples throughout this paper, were generated automatically by the recognizer; annotations and shading were added manually.) This part illustrates several complicated interferences that are typically not handled in other feature recognizers. The slots cross each other, and at their intersection is a hole which is slightly larger than the width of the largest slot. In addition, one of the slots has another, smaller slot through the middle of its floor. The resulting intersection is therefore fairly complex without any clear edge-connectivity between the different halves of each slot. Finally, the slots do not end "nicely", but rather end in a point, with the walls stopping before the floor does. In the case of the double embedded slot, the wider slot does not even contain the final "tip" of the floor. The stock is an enclosing box around the entire part.
Figure 20. Crossing slots.
Figure 21 shows on the left the delta volume. The interactions between the features do not affect the hint generation process, which relies on the cylindrical and conical face for the hole and on the opposing and parallel faces for the slots.
Hints for all the features are readily available and each hint undergoes completion as explained earlier. The slot halves are reconnected where they cross each other, and extended outwards to the furthest point on the part. The slots are also extended upwards, which is most noticeable with the thin Embedded "Slot 3". It penetrates through "Slot 1" with the volume shared labeled as "optional". An intermediate step in the completion of the thin slot is shown on the right of Figure 21. The segmentation and classification along the Sweep and Up axes produce several segmentation planes that indicate transitions with machining significance.
The resulting "Slot 3" is shown in more detail in Figure 22. Along the sweep axis, only the darker shaded portion is optional, the rest is required.
The slot is accessible along both sweep directions. Regarding the Up direction, the lighter shaded portion of the slot is optional, whereas only the unshaded bottom part is required. The slot is also entirely accessible towards its top.
Not shown in the above figures are two alternative decompositions for the crossing slots. The first alternative decomposition is a pocket whose floor is the same as that of the two larger crossing slots and a second alternative is a pocket which includes the smaller embedded "Slot 3" and part of the hole. The overlapping interpretations are equally viable and are reported as possible alternatives. The feature recognizer does not have sufficient information to decide which decomposition is better. Additional information such as a tight parallelism between the opposing faces could justify a preference for the slot alternative instead of the pockets.
Once a feature hint is found, the missing portions of the feature are inferred by extending the feature volumetrically in several directions through a process called feature completion. Completion produces the largest non-gouging (i.e., non-intruding) volumetric feature compatible with the hint. The result is a solid that reconnects portions of the feature that were separated by interferences with other features. The completion process also derives additional data on feature accessibility and on feature interactions that are important for determining the sequence of machining operations in later planning stages. Each feature is volumetrically subdivided into a required portion, which must be removed by the machining operation associated with the feature, and optional portion, which may be produced as a side effect of another machining operation.
The feature completion process was implemented as part of an experimental feature finder using the Knowledge Craft(TM) AI environment tightly coupled with the PADL-2 (and, more recently, the Parasolid(TM)) solid modeler, which performs the geometric calculations.
The following are the most interesting characteristics of our research.
Our research is limited to 2.5-D, swept features that correspond to the manufacturing processes typically performed in 3-axis machining centers. Additional limitations of the feature recognizer are that (i) face segmentation (i.e., associating face subsets with features) is not adequately addressed (or in any other existing recognizer, as far we know), and (ii) features and associated geometric tests are hard-coded and not easily modified by users, who may wish to define their own features. The feature finder also has its share of implementational limitations, which are not difficult to overcome conceptually but involve substantial programming effort.
Future research on feature completion will refine some of the ideas and their implementations; extend the feature completion procedure to more complex features, e.g. those made with shaped cutters; and address issues of efficiency.
Work on the recognizer itself is continuing at USC, with two main goals: integrating the recognizer with upstream (design-by features) and downstream (NC cutter-path generation) modules; and operating incrementally, so as to provide immediate feedback to a designer about the manufacturing consequences of design decisions.