Figure 1: Interactions between three slots and a composite hole
Jan H. Vandenbrande [+] and Aristides A. G. Requicha
Computer Science Department and Institute for Robotics and Intelligent
Systems
University of Southern California
This paper appeared in: IEEE Pattern Analysis and Machine Intelligence, vol. 15, no. 12, pp. 1269-1285, December 1993.
Note: This web pages is still under construction as not all symbols transferred correctly.
A generate-and-test strategy is used. OPS-5 production rules generate hints or clues for the existence of features, and post them on a blackboard. The clues are assessed, and those judged promising are processed to ensure that they correspond to actual features, and to gather information for process planning. An incompletely-specified solid feature, represented as a partially-filled frame, is associated with each promising hint. Computational geometry techniques are used to produce the largest volumetric feature compatible with the available data. The feature's accessibility, and its interactions with others are analyzed. Interactions are represented by segmenting the feature into "optional" and "required" volumes. Because some of the proposed features may rely on faulty hints, these are tested for validity in a verification phase. The validity tests ensure that the proposed features are accessible, do not intrude into the desired part, and satisfy other machinability conditions. The process continues until it produces a complete decomposition of the volume to be machined into fully-specified features.
The recognizer is implemented in a rapid prototyping test bed consisting of the KnowledgeCraft(TM) AI environment tightly coupled with the PADL-2 solid modeler, and running on Sun workstations.
Features provide natural means to associate domain knowledge with object representations. They also serve to "discretize" some problems. For example, given a part representation in terms of machining features, process planning becomes essentially a discrete, or combinatorial search problem, because machining features are readily associated with manufacturing processes. One can think of machining features as "differences" between raw material and a goal object in a means-ends problem solving formulation [3]. Differences can be reduced by applying relevant machining operators. Some of the operator pre-conditions can be cast as feature validity conditions, as we will see below.
Recent research on design by features and on concurrent product and process design suggests that parts be designed in terms of manufacturing features. We think that such an approach has serious drawbacks because (i) designers should work in terms of functional features, which are linked to performance requirements, and (ii) manufacturing features are closely tied to specific processes, and therefore restrict one's ability to select the best manufacturing methods. Process dependency is especially pernicious for parts that remain active for long periods of time, during which manufacturing-process technology may evolve significantly. We believe that design by features is an excellent idea, but that features relevant for design are not the same as those relevant for machining. For example, webs are design features that are not directly machinable, and therefore are not machining features. A web is machined indirectly, usually by clearing an area or pocket bounded by the web and other features. Undoubtedly designers should take manufacturing into account, but it is unreasonable and undesirable to force them to specify products in terms of manufacturing processes instead of functional or behavioral characteristics. An analogy with electronic design may be helpful: VLSI circuitry is not designed in terms of explicit manufacturing procedures, although it takes process capabilities into account. It follows from this discussion that feature recognition is crucial for the full automation of machining planning.
This paper focuses on the recognition of machinable features from solid models of parts and, optionally, from additional data such as design features, tolerances, and surface attributes (e.g., threads). Our approach exploits knowledge of design features when these are available, but does not require that a part be entirely designed using features. We consider only conventional machining, and focus on non-rotational parts that are typically manufactured in 3-axis machining centers. Process and tool selection, setup planning, cutter-path generation, and other important issues in machining planning are outside the scope of the paper.
Much has been written on feature recognition for machining--see [20] for a critical discussion of the literature prior to 1989. Kyprianou in seminal work introduced a method for detecting depressions and protrusions by analyzing convexity and concavity of edge loops [9]. His ideas have been used in almost all of the subsequent feature finders. In another landmark thesis Henderson showed that volumetric features could be extracted from solid models by searching for certain face and edge patterns in a solid's boundary representation (BRep), and introduced accessibility considerations [7].
More recently several researchers have used graph algorithms to recognize face and edge patterns--for examples of this approach see [4, 13, 16]. De Floriani recognizes certain features attached to a single face or pair of faces by using connected-component algorithms. Other authors define a feature by a graph involving faces, edges, adjacency information, and attributes such as edge convexity. The entire part is described by a similar graph, and feature finding becomes a subgraph isomorphism problem. In essence, features are associated with graph grammars, and feature recognition is accomplished by parsing. The linguistic approach is attractive because a graph grammar typically is more expressive than a simple enumeration of patterns. However, there are two drawbacks. First, unlike string grammars, useful graph grammars do not appear to have efficient parsing techniques. Subgraph isomorphism is NP complete, and various heuristics suggested in the literature do not break such a complexity barrier. Secondly, and perhaps more importantly, general interactions between features are very difficult to accomodate. The difficulties seem to be inherently associated with approaches based primarily on "topological" information. Face and edge relationships are altered by feature interactions, and it seems impractical to define all the resulting patterns. Because of the interactions some of the faces that correspond to a feature may be entirely absent, partially missing, or fragmented into several regions. Faces may be shared without clear demarcations between features. Edges may be missing, or unexpected edges may appear. Figure 1 shows a simple part with three slots and a hole that interact to create a complex pattern of faces and edges, not recognizable by most of the existent feature finders. (The decomposition shown was generated automatically by our feature recognizer.)
Figure 1: Interactions between three slots and a composite hole
Amongst on-going research, two projects at Carnegie Mellon University [5] are especially interesting because they are investigating non-conventional approaches. One of the projects looks directly for edge loops by studying a solid's "silhouettes" as seen from several directions. The other uses skeletons or medial axis transforms of the objects. Neither of these methods has demonstrated a strong capability to recognize interacting features.
Our approach differs radically from most of those previously reported, and is closest in spirit to a recent development at Purdue [10], which makes a significant attempt to deal with general feature interactions. The Purdue work was conducted independently from ours and at about the same time, but led to similar ideas such as generate-and-test and face extension. 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.
From the descriptions available in the open literature we conclude that all of the existent feature finders suffer from at least one of the following deficiencies.
The research reported here is motivated by these deficiencies, and is a significant step towards overcoming them.
Figure 2 illustrates a linear solid slot, which is a volume swept by a cylindrical cutter in a linear-motion cut. Observe that the slot can be parameterized as shown, and therefore can be represented as a generic object in a system such as PADL-2 [1] that has facilities for representing parameterized object families.
Figure 2: A linear-slot volumetric feature.
A surface feature, on the other hand, is a collection of workpiece faces that result from machining (i.e., subtracting) a volumetric feature. Figure 3 shows a surface feature associated with the volumetric slot of Figure 2. Observe that not all the faces of the volumetric feature are present in the surface feature, and that some of the faces that are present have missing portions. These discrepancies between volume and surface features arise from interacting features (such as the hole in Figure 3) and from additional space that is swept by a cutter but does not contribute to faces in the final part (e.g., the cylindrical ends of the volumetric slot in Figure 2).
Figure 3: A linear-slot surface feature.
More formally, a surface feature S is the contribution of the boundary [[partialdiff]]V of the volumetric feature to the part's boundary, and is defined as S = V [[intersection]] [[partialdiff]]Part, where [[intersection]] denotes non-regularized set intersection, and [[partialdiff]] is the topological boundary operator. (A surface feature may be composed of "sub-faces", rather than entire BRep faces of an object.) A part is fully decomposed when the union of all solid features Vi contains the removal or delta volume [[Delta]], i.e., [[Delta]] Í [[union]]S(*,i) Vi , where Vi is a solid feature, [[Delta]] = Stock -* Part, and -*, [[union]]*, and [[intersection]]* denote regularized set difference, union and intersection [14].
The delta volume is the material that must be removed to transform the stock into the desired part. 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. The boundary of the delta volume is a more convenient source of data for feature finding than the boundary of the part, because it is easy to show that [[partialdiff]][[Delta]] contains only stock faces to be removed and part faces to be generated, whereas [[partialdiff]]Part may contain faces that are not machined and therefore are of no interest [20].
For linear, radial or circular extensions, a cross-sectional surface is a surface that is normal to every trajectory. For linear and circular directions the cross-sectional surfaces are planar, and for radial trajectories the surfaces are cylindrical. A cross-section X is the 2-D region of intersection of a set extension with a cross-sectional surface. A set extension that equals a linear extension of a planar cross-section is often called an extrusion. A circular extension of a planar cross section with a value of 2[[pi]] is a solid of revolution.
The three types of extension trajectories we consider are related to the cutting motions available in 3-axis machining centers. All of the volumetric features considered in this paper can be defined by extending cross-sections. Furthermore, it is straightforward to compute a cross-section of a feature from a (sufficiently large) portion of the feature's boundary. Two examples follow. A cylindrical hole is the extension along the axis direction of a circular cross-section, which can be found easily from a subset of the cylindrical surface. A groove (Figure 4) is the radial extension of a cross-section which is a cylindrical surface bounded by two parallel planes. (A groove also is a linear extension of an annular, planar cross-section.)
A maximal linear extension of a cross-section is a semi-infinite slab, and corresponds to an extension with unbounded (semi-infinite) linear segments. A maximal radial extension of a cross-section involves either an infinite value (for "outward" extensions) or a value equal to the radius of the cylindrical cross-section (for "inward" extensions); the result is either a semi-infinite solid with a cylindrical hole or (a subset of) a solid cylinder. A maximal circular extension has a value of 2[[pi]] and therefore is a solid of revolution. Maximal extensions produce the largest volumetric features compatible with a given cross-section, and are used extensively in an operation called feature completion, discussed in Section 3.
If V intruded into Part, the manufacturing operation associated with V would cut too much. Observe that non-intrusion is very easy to check in a solid modeler that supports Boolean operations, because V is a solid feature. If only surface features were available, non-intrusion testing would be a very delicate operation.
The answer depends on the feature type and the underlying physics of machining, and has some degree of arbitrariness. For example, a linear-slot surface feature in our work is required to have a non-null portion of both lateral faces of the corresponding volumetric slot (as shown in Figures 2 and 3). This seems reasonable (and is probably essential for a functional slot), but is not necessary to ensure that the feature can be produced by a single linear cut with a flat-end mill. On the other hand, a "partial hole" (i.e., a cylindrical surface that does not extend through a complete 2[[pi]] angular range) cannot be drilled safely unless there is enough material around it to provide support for the drilling operation and prevent chatter and tool breakage. This poses constraints on the minimal angular extent of hole features.
Accessibility is also important for feature categorization. Distinct features may be geometrically identical, but require different manufacturing processes because of their accessibility characteristics. For example, in Figure 4, the inner groove requires machining from within, while the circular slot is machined from the top.
Figure 4: Feature categorization based on accessibility.
For the reasons cited earlier, we seek only necessary conditions for accessibility. We consider several conditions, called local, semi-infinite, partial, and lateral accessibility, which ensure that certain cutter abstractions can reach a feature. If a suitable set-up and physical cutter can be found, a feature that satisfies our accessibility conditions is almost surely machinable.
We define local accessibility in terms of a point cutter moving along a specified family of trajectories. For the class of parts producible in 3-axis machining centers, trajectories can be either linear, concentrically circular, or radially emanating from an axis. (Radial trajectories are used for turning, boring, and certain side cutting operations.) We reason that a physical cutter must be larger than a point, and that a cutter must contact all points of a volumetric feature to be able to remove it. Local accessibility is checked (conceptually) by extending a volumetric feature (see Section 2.2) by an infinitesimal amount along a set of directions which depend on the type of feature. If the volume thus swept intersects the workpiece the feature is inaccessible. Figure 5 shows a dove-tail slot and its infinitesimal linear extensions along vertical and horizontal directions. The slot is locally inaccessible along the vertical direction (a), but locally accessible along the horizontal axis (b).
A feature is semi-infinitely accessible if a half-line of constant orientation can be placed so that its end-point coincides with every point of the solid feature without colliding with the part (Figure 6). The rationale for this definition is simple. A cutter and spindle assembly must be thicker than a halfline parallel to its axis, and must have essentially unlimited clearance in the axis approach direction. Therefore, if the half line abstraction collides with the workpiece, so does the cutter and machine tool structure. (A similar definition is useful for high-level planning of inspection operations [17, 18].)
(a)
(b)
Figure 5: Local accessibility of a dove-tail slot.
Figure 6: Semi-infinite accessibility.
Note that semi-infinite accessibility implies local accessibility, but the converse is not true. Both accessibility concepts are useful, because local accessibility is easier to test computationally. If a feature fails a local accessibility test for a given direction, it can be discarded since it is not semi-infinitely accessible along the same direction.
A feature is partially (semi-infinitely) accessible if only a proper subset of its volume can be reached non-intrusively by a half-line abstract cutter with a given orientation. The semi-infinite volume obtained by sweeping a half-line over the reachable subset is called the partial accessibility volume. Figure 7 shows a dove-tail slot and its partial accessibility volume. Note that the existence of a partial accessibility volume is crucial to ensure shank clearance while machining the slot with a dove-tail cutter.
Figure 7: Partial accessibility.
Figure 8: Lateral accessibility.
A slight generalization of partial accessibility, called lateral accessibility, is needed to deal with certain side cutting operations. A volumetric feature V is laterally accessible in direction d if the feature or its extension is partially accessible along d. For lateral accessibility the extension trajectories must be normal to the accessibility direction. The analog of the partial accessibility volume is called a lateral accessibility volume. Consider the groove shown on the right of Figure 8, and its associated volumetric feature V. Lateral accessibility in direction A1 is required to ensure shank clearance for the side-milling operation shown on the left of the figure.
Figure 9: Dimensional limits.
Dimensional constraints of the second type ensure that features remain roughly in the domain of applicability of common tools. They guarantee, for example, that holes are not too deep and slots not too wide. Since many of these factors are dependent on the machining environment and do not reflect absolute physical limits, they are user adjustable. These rules facilitate feature categorization when several interpretations are possible.
Composite features consist of a combination of primitive features that obey certain aggregation rules. Thus, the union of the solid primitive features that constitute a composite must form one connected solid, and certain relationships between the primitive features must be satisfied. For example, a composite hole is the union of coaxial and spatially adjacent primitive holes.
Composite volume and surface features must obey the same validation rules as primitive features. This implies that the constituent primitive features must be valid themselves. One of the computational benefits of composite features is that complicated geometric tests on primitive features can be simplified by considering the composite first. For instance, the cylindrical end of a blind, bottomless slot determines a unique approach direction for the slot, which is difficult to infer solely from its planar faces.
Both primitive and composite feature classes (or types) and their validity rules are defined in the system. That is, user-defined feature types are not supported. It is not difficult to design facillities for the definition of new feature types. But we do not know how to produce automatically (or even with user assistance) the rules and procedures needed to recognize a new, user-defined feature class.
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 10). 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 10: Optional and required portions of a hole.
Required and optional volumes provide supplemental information that facilitates geometric reasoning for planning. An example is presented below to illustrate the power of this idea. Other examples can be found in [20]. In Figure 11, 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 11: Center portion of hole interferes with feature X.
Features are represented by computational structures called feature frames, which evolve during the feature recognition process. A feature frame contains the following information:
The primitive solid cylindrical hole shown in Figure 12 is the simplest of the template features.
Figure 12: Primitive solid cylindrical hole feature.
The solid cylindrical primitive hole parameters are:
Radius: R Axis Direction: A = (ax ay az) with || A || = 1 Axis Origin: P = (px py pz) with A orth P Local Z-axis: Z' = A Local Y-axis: Y' = P / || P || Local X-axis: X' = Y' x Z' Position of closing half [d1, d2] d1< d2 along spaces: increasing A, wrt origin P Optional/Required Volumes: [da, db, dc, ....] d1<= da < db< .... <= d2 Local & Semi-Infinite -A or +A (or both) Accessibility
Observe that the feature's parameters suffice to construct solid primitives for representing the entire volumetric feature as well as its optional and required portions in CSG.
Similar definitions and representations apply to conical, toroidal and spherical holes, and also to linear and circular slots and grooves cut with flat-end, bull-end or ball-end tools. (The details are given in [20], where presence rules for each feature type also are discussed.)
A 2.5-D pocket is a connected solid that results from sweeping a planar region (the "floor") along the normal direction to the plane, and (possibly) by filletting the floor's contour. A pocket may have "islands", and must be semi-infinitely accessible along the sweep direction. Additional accessibility properties lead to subclasses of 2.5-D pockets such as closed pockets, open pockets, steps, and slabs. Finally, profiles are "floorless pockets", accessible along two opposing directions. (Again, see [20] for details and examples.)
The input is processed by production rules that generate hints for the presence of machining features. A feature hint may be generated by a characteristic combination of part faces, by a design feature from which a manufacturing feature can be inferred, or by a tolerance or attribute specification that can be associated with a certain feature type. For example, a thread attribute can trigger a hole hint. We search initially for feature hints, rather than for complete features, to be able to deal with feature interactions. A hint-based strategy also can accommodate diverse sources of information, by combining the hints generated from all the sources. In our work we consider primarily hints generated from the part and stock's boundaries, although the overall architecture of the recognizer supports more general hint generators.
Feature hints are passed through a hint classifier which categorizes them into three groups: promising, unpromising, and rejected. Rejected hints are discarded. Unpromising hints are stored in a partitioned blackboard and all activity on them is temporarily suspended. They may be reactivated later if they become part of a composite feature, or if the promising hints do not lead to a complete decomposition of the part into features. Promising hints are further processed by the "feature completer", which searches for all the relevant data about the feature, and generates the largest possible feature volume that does not intrude into the part and is consistent with the available data. Optional and required portions of the feature are computed.
Figure 13: Architecture of the feature finder.
The processed features are stored in the blackboard, where another set of rules attempts to combine them with other features that satisfy certain conditions. For instance, two coaxial and adjacent holes are combined to form a counter-bored hole, which is a specific type of composite hole.
The final step in our feature finder is verification, which is necessary because some of the proposed features may not be machinable. For example, the hint generators that operate on nominal geometry rely on partial information, and sometimes are misled. Feature hints based on design features may also be incorrect. The verifier checks the validity of the proposed features by performing tests for part intrusion, presence of faces associated with the feature, accessibility, and dimensional constraints. (Some of these tests are partially built into the hint generators, to avoid proliferation of poor clues.)
The feature verifier can either accept a proposed feature or reject it. If the feature is accepted, it becomes part of the set of recognized features in the blackboard. If it is rejected, the feature is discarded and, sometimes, clues for other features are generated and fed back into the blackboard.
The feature finder uses both fine-grained and coarse-grained control. The fine-grained control selects a rule to activate, while the coarse-grained control coordinates the overall sequence in which sets of rules are activated. The first step performed by the fine-grained controller is to determine which rules are valid in a specific instance by finding all the rules whose antecedents (LHS) are satisfied. Next, one rule is selected from the active list and processing is activated. When the rule finishes, the process cyclically repeats itself until no further active rules are found, or the process is explicitly halted.
The fine-grained control keeps track of the data used and the changes that have occurred, to ensure that the same rule will not be activated repeatedly on the same set of data, and to update the list of active rules. Heuristics are used to select one active rule over another. Currently we use primarily the heuristics provided by the OPS-5 system. Generally, the most specific rule (i.e., the one that has the most complicated antecedents) is used on the most recent data (when several sets of data satisfy a rule). Additional heuristics can be added to give preference to certain types of rules (e.g., give preference to the hint generators based on design features, or preference to certain types of features), although this has not been used in our implementation.
The coarse-grained control coordinates the general sequence of rule activation. The feature finder processes information in two phases, by activating sets of rules. In the first phase, the rules for generating primitive-feature hints, grouping them into composite hints, and merging similar hints from different sources are activated. The results of these activations are further processed by the procedures shown in Figure 13 before being deposited back in the partitioned blackboard. This process continues until either all the feature hint rules or all the part faces have been used. (This latter test does not ensure that a complete decomposition has been found because features may share common faces--other goal attainment tests are discussed below.)
In the second, verification phase, the rules and procedures for verifying clues and detecting conflicts are activated, and the hint generation rules are deactivated. We proceed in two stages mainly to exploit composite features. The existence of a composite feature reinforces its constituents, which might individually be considered unpromising candidates for verification. Because the order in which features are proposed is unknown, the second phase cannot be started until the composite features are completed. Second-phase rules remain active until a feature decomposition is found that encloses the delta volume. If the delta volume is not fully decomposed into features, and no unverified features remain, the hint generators are reactivated and the whole process repeats itself. If this fails to produce additional hints, the list of suspended features is examined for viable candidates, which in turn go through verification. If this also fails, the feature finder is unable to decompose the entire workpiece into features.
The hint generators may produce duplicate and conflicting hints. If several hints for the same feature are generated, they reinforce one another and are easily combined. (Grouping hints for composite features also can be viewed as a reinforcing process.) But a single face (or group of faces) of an object may be associated with hints for several distinct volumetric features. These are contradictory (or conflicting) hints. Two things can happen: (i) All but one of the conflicting hints are invalid and the conflict is resolved after the verification stage, or (ii) several hints are accepted by the verifier. In the latter case, the feature finder is not be able to resolve the conflict. This is not a deficiency of the feature finder; it simply reflects the non-uniqueness of feature-based representations.
Figure 14: Multiple interpretations of two interacting features.
For example, the delta volume of Figure 14 can be decomposed into two valid alternatives: A hole and a slab, shown on the left of the figure, or a slab and a slot with rounded floor, shown on the right. We think that a feature recognizer should be able to generate both alternatives, so that a process planner can select one of them by invoking appropriate machining criteria. Observe that the order in which features are machined influences their validity. For example, the hole/slab alternative is acceptable only if the hole is drilled first. If the slab is produced first the material adjacent to the hemi-cylindrical cavity does not provide sufficient support for a hole-making operation. In our feature recognizer features such as the hole in Figure 14 contain information on "conditional validity", to alert a process planner to sequencing dependencies.
A hint, technically, is the initial state of a proposed 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). Thus, a hint can be viewed as an incomplete representation for a possible volumetric feature (or set of features). The recognizer attempts to complete the proposed feature frames, and to generate a frame that corresponds to a valid feature. The generate-and-test strategy used by the recognizer may produce many invalid hints. To avoid unnecessary computations, hints are evaluated before further processing. Feature evaluation is performed by a hint classifier based on feature validation rules.
A hole hint is triggered by the existence of a face that can be produced by machining a solid primitive hole. The two most common hole hints are generated by either cylindrical or conical faces. Figure 15 shows a part with several faces that generate hole hints. Note that not all of the hints will be validated in this example.
Primitive linear slots and grooves are found by searching for two opposing and parallel planar faces. If a floor connects the two walls of a slot, it will provide useful information for evaluating the hint, but the floor is not used as the primary trigger for hint generation. Hints for circular slots consist of two opposing concentric faces. Additional processing is required to discriminate between linear slots, linear grooves, and circular grooves. Linear slots and grooves differ in accessibility, whereas linear slots and circular grooves have different floor characteristics.
A pocket hint is generated by a planar face (the floor) surrounded by zero or more adjacent part faces forming the pocket's walls. For 2.5-D pockets produced with flat-end milling cutters, the wall faces must be ruled surfaces with rulings parallel to the floor's normal. (The hint generation procedures are slightly more complicated when other cutters are considered, to take into account the rounded transitions between the floors and the walls.) If the lateral boundary of the pocket consists only of part faces, a hint for a closed pocket is generated. Otherwise the pocket type cannot be determined at this stage, and further processing is needed.
Figure 15: Primitive hole hints.
Profile hints are triggered by a cylindrical face, or by a planar face which is either tangent to, or makes a concave angle with an adjacent face of the delta volume. The faces must be ruled surfaces with rulings parallel to the profile axis, and cannot be directly adjacent to a common floor. When a profile hint is found, the search continues for additional adjacent faces that satisfy these criteria. We reject delta volume faces that meet at a convex angle, to ensure that a profile can be finished in a single cut by side milling with a cutter of non-zero radius.
where:
VS(*) Maximal extension (see Section 2.2) of the
cross-section X along the directions or
trajectories specified in {Dirs}, which may be
linear, radial or circular, depending on the
feature type.
VS(*) [[intersection]]* Regularized intersection of the maximal extension
Stock with the stock. It is always a bounded solid.
Min(...) Minimal volumetric feature that encloses
VS(*)[[intersection]]* Stock, i.e., VS(*)
[[intersection]]* Stock Í Min(VS(*)
[[intersection]]* Stock).
Min(...) -* Part Difference between the minimal enclosure volume
and the part. (This eliminates all the portions
of the proposed volume that intrude into the
part.)
CComp[...] Connected components, denoted by VS(*,i).
AAC(Max ,VS(*,i) Largest volumetric feature that fits within each
[[intersection]]* Part = VS(*,i) without intruding into the part.
0 ) {...}
{Vi} Resulting set of maximal, non-intrusive
volumetric features.
Figure 16 illustrates the feature completion process for a hole hint generated by a cylindrical surface S1. The example is somewhat contrived, but it demonstrates all the operations in the formula, and shows why they are useful.
Figure 16: 1-D feature completion.
A cylindrical half-space VS(*) results from extending the cross-section of the feature hint S1 along the specified axis. For parameterized features such as holes, slots and grooves, extending a feature 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 the smallest cylindrical hole. The ends are orthogonal to the axis and correspond to the starting and ending positions for a rotating cutter. 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 largest possible solid cylinder that is totally enclosed by the component is computed.
In Figure 16 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 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 semi-infinite 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 semi-infinitely accessible. Part intrusion testing is redundant because the volume features that are generated are non-intrusive by construction. (Features that are not generated by this method, for example design form features, must pass a part intrusion test.)
where
[[partialdiff]]V Boundary of the volumetric feature.
[[partialdiff]]Part [[intersection]] [[partialdiff]]V Intersection of the boundary of the part and boundary of the volumetric feature.
CComp{...} Connected components of the resulting faces.
Min(...) The result of enclosing each 2-D connected component with the smallest solid feature that has the same properties as the original volumetric feature V (e.g. same axis and diameter). Note that Min maps a 2-D entity onto a solid.
Figure 17 illustrates how the required portions of a solid hole V are found. Note that the top surface feature S2 is uneven. The formula produces two volumes, each of which fully encloses the respective surface feature. The required portion of a feature corresponds to the minimal volume a cutter must sweep to produce the desired surface feature. (In this example, VS(R,2) cannot be removed without traversing VS(R,1) and the volume between them. If it were physically possible, machining only the required volumes would produce the part.)
Figure 17: Extracting required portions.
The optional volumes are given by {VS(o,j)} = CComp { V -* ([[union]]* VS(R,i) ) }, as shown in Figure 18 for the volume feature of Figure 17.
Figure 18: Extracting optional portions.
Feature classification involves segmenting the volume VS(*)[[intersection]]*[[Delta]], by introducing cross-sectional surfaces (see Section 2.2) with respect to the specified set of directions {Dirs}. The separation surfaces are computed by analyzing the interactions of the faces of VS(*)[[intersection]]*[[Delta]] with adjacent faces. These interactions also provide the information necessary to classify the segments, i.e., to determine their membership in the various sets that figure in the completion formulae. Classification results for every face are combined so as to produce the final results.
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.
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 still use the 1-D completion formula, but without the Min and Max operators, and with the following interpretations for the terms: (1) VS(*) is an infinite slab normal to the specified direction and (2) only the non-intrusive connected components whose boundaries include the given surface features are retained.
The optional/required formula also needs to be interpreted differently. The Min operator for 2-D extension produces the smallest "slab" (translationally swept volume) that includes each connected component of [[partialdiff]] V [[intersection]] [[partialdiff]] Part.
Figures 19 through 21 illustrate 2-D completion of a pocket hint. The floor corresponding to the original hint Face-1 is enlarged, as shown in Figure 20, so as to contain Face-2 and Face-3, because they lie in the same plane as Face-1. The shaded areas correspond to portions of the floor which are coincident with existing faces and will later be marked "required".
Figure 19: Pocket hint.
Figure 20: Enlarged pocket floor.
Figure 21: Resulting pocket volume.
In Figure 20, the connected component of the volume that has a face coincident with the original hint is retained. 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. 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. [9]) typically have problems with such situations, especially if a protrusion sticks out from multiply embedded depressions.
Features other than holes require additional processing in conjunction with feature completion. This is done partly for efficiency reasons and partly because partial information about a feature provided by a hint is often insufficient to perform feature completion. For instance, linear slot hints consisting of parallel, opposing, planar faces do not fully specify completion directions, and pocket hints often do not contain the entire pocket boundaries because of interactions with other features. In either case, a cross-section is not immediately available for extension.
To find the desired information, the faces adjacent to the feature hint are searched and analyzed. If the search is successful, completion proceeds as described earlier. On the other hand, if the search fails, procedures analogous to completion in several directions are used. For example, for a linear slot a slab is constructed from the two parallel and opposing half-spaces provided by the slot hint, and the slab is intersected with the delta volume. The resulting volume is analyzed, for example by searching for potential floors by using a generate-and-test strategy. If the analysis is successful, segmentation and classification commence. Details may be found in [20].
Still, certain tests are needed after a feature is successfully completed, and these are accomplished in the "feature verifier" of Figure 13. These tests include lateral accessibility analysis for grooves and conditional validity for holes [20].
In the current experimental implementation the BReps of the delta volume and the stock are converted into a frame-based structure in KC and enhanced with adjacency links, edge convexity flags and other useful information. Hint generation is based exclusively on BRep information. Hints from design features, tolerances and attributes are not implemented.
The BRep structure is processed by KC/OPS-5 rules which fire when certain face patterns and geometric conditions are satisfied. Some of these conditions are checked by calls to the modeler. The number of rules is relatively small, in the order of 20. The standard, built-in KC/OPS-5 "lexical" mechanism for selecting rules within a Rete pattern matcher is used [2]. It is overlaid with a coarse control structure which activates and deactivates certain sets of rules, as previously described.
Hints and completed features are represented by frames ("schemas" in KC terminology). Feature frames are organized in an object-oriented scheme with multiple inheritance. The blackboard is implemented through the working memory of KC/OPS-5, as sets of frames organized into partitions or KC "contexts". Coarse control is implemented by switching contexts.
The following examples show (paraphrased) rules for generating hints, combining features and detecting conflicts. Note that each rule consists of an antecedent (LHS) and an action part (RHS).
Find Linear Slot RuleSEARCH During Hint Cycle for:
A planar, non-stock face of the Delta Volume
A second planar, non-stock face of the Delta Volume,
not equal to, but parallel and opposing to the first face
NOT( A previously created linear slot using these two faces )THEN
Extend feature in all directions
Search for slot floors
Classify feature along, and perpendicular to, the sweep directions
Evaluate classification for partial verification
This rule is only active during the hint generation phase. The first antecedent searches the BRep partition of the blackboard for a planar non-stock face of the Delta Volume. The second antecedent searches for a second planar face which is different but parallel and opposing to the first. This latter test is performed by KC/LISP functions. The third antecedent ensures that no linear slot hint was generated previously that uses the same two faces.
After an appropriate pattern is found, another set of KC/LISP functions are called that (i) extends the two faces in all directions constrained by the two halfspaces and performs the geometric computations described earlier, (ii) searches for suitable slot floors to determine sweep and tool axis directions (which may involve additional solid modeling operations), and (iii) classifies the feature along, and perpendicular to, the sweep direction for each potential slot floor. These results are then analyzed to identify potentially machinable slots. This process produces either (i) a promising feature, when a semi-verified solid feature is generated from the hint, (ii) a suspended feature, when insufficient information is obtained to either reject or accept the feature (e.g., no sweep direction was found), or (iii) a rejected feature hint, which is either deleted or passed to another feature hint type processor.
The next rule combines two primitive slots as a potential composite slot.
Find Composite Slot RuleSEARCH During Hint Cycle for:
A primtive slot
Another primitive slot, different from the first, with a different
type, physically adjacent, with macthing parameters, and
not previously linkedTHEN
Link the two slots
For slots to be linked certain critical parameters must match up, for example, the widths and cross sections. This rule considers both promising and unpromising primitive slots. If the rule fires, a new entity called a composite slot is created with the information common to its primitive constituents. This information in turn is used to analyze the unpromising constituents, e.g. to establish partial accessibility for an otherwise inaccessible bottom portion of a T-Slot. Thus, expensive computations such as partial accessibility testing can sometimes be eliminated. A composite slot is further tested for validity during the verification cycle, for example to decide whether a semi-cylindrical slot-end is present or can be fitted at either end to allow cutter overshoot.
The third rule shown below illustrates conflict detection between slots and pockets:
Detect Slot/Pocket Ambiguities RuleSEARCH During Verification Cycle for:
Either an open or closed pocket br> Either a primitive or composite slot whose faces are a subset of
the above featureTHEN
Report dual decomposition
A slot is merely a pocket with certain specific machining properties. As a result most slots also produce pocket hints. This rule searches through all linear and circular slots and determines whether their corresponding surface features form a subset of the surfaces used by either a closed or an open pocket. This rule is activated only in the second, or verification phase. Currently, the conflict is merely reported, and no further processing performed. Similar rules exist to report other alternative decompositions.
In the current implementation, the "Hint" cycle is active until all KC/OPS-5 feature hint rules are exhausted. No rules exist to halt this cycle prematurely when a "suitable" but non-exhaustive feature decomposition is found. The verification, or "Check" cycle, is activated after the Hint cycle terminates. Because all feature hints are exhausted at this point, the "Hint" cycle cannot be reactivated to search for additional decompositions.
Figure 22 shows a simple example with almost no feature interactions taken from [8]. (Figures in this section were generated automatically by the recognizer, with shading and annotations added manually.) The part is totally surrounded by stock, which results in 6 "slabs" that correspond to facing operations. The composite holes are extended through the part and subdivided into their required and optional parts. The "notch-and-pocket" depression is recognized as two closed pockets with different floors. Only the portion of Pocket 1 that is common with the notch is required, and the rest is considered optional.
Figure 22: A simple example with limited feature interaction.
Figure 23 illustrates alternative decompositions for another example containing substantial interactions. The first alternative, shown at the top, consists of Open-Pocket 1, Step/Slab, and Slot 2. The second, shown at the bottom, is Slot 1, Slot 2, Composite-Slot, Open-Pocket 2, Open-Pocket 3, and the same Step/Slab as in the first alternative. The dark shaded regions indicate the required portions of the pockets (imagine the volume swept by the shaded face along the direction of the cutter axis). The lightly shaded walls correspond to faces of the part and therefore cannot be violated, while the unshaded walls can be crossed by a cutter. Also note that Slot 1 is extended upwards, and Composite Slot is extended along its axis up to the closest corner of the object.
Figure 23: A more complex example with interacting features.
For each of the two objects shown, the feature finder produces a decomposition (including the information derived from feature completion, such as optional/required volumes, and accessibility), on a 15 MIPS machine (SUN 4/360) in about two and a half minutes. The input data in these tests consists solely of the solid models of the stock and part, and no clues are used except those generated by analyzing the nominal geometry of the stock and part. Most time consuming are the geometric tests performed by the PADL-2 system. Approximately 50 PADL-2 procedures are called by the feature finder. The calls to PADL-2 can be categorized as (1) general calls (e.g. part retrieval, display), (2) mathematical calls (e.g. vector computations), (3) transfer of data to KC (e.g. BRep, edge and face parameters), and (4) evaluation of edge, face and solid data (e.g. determining edge/face properties, or computing the BRep from a given CSG string). Some of the most expensive computations are associated with feature completion, which involves Boolean operations between delta volumes and feature extensions. The space used grows from an initial binary image size of ca. 8 MBytes (which contains both PADL-2 and the KC-system) to over 40 MBytes. Temporary data retained within PADL-2 contribute the major portion of this space.
The recognizer uses a rule-based approach for generating clues or hints about potential features from partial information gathered from several sources--nominal and toleranced geometry, attributes (e.g. threads), and functional features specified by a designer. Most of the methods proposed in the feature recognition literature could be used as additional hint generators. Instead of simply accepting the output of such recognizers as verified features, we would consider them as hints to be further processed by our system. For example, some of the linguistic recognition methods may be useful sources of clues for non-interacting features.
Hint validity is assessed by using geometric tests based on criteria closely associated with machinability constraints such as non-invasive machining. (We believe, but have not proved formally, that the recognized features are always machinable in a suitable set-up and with appropriate cutters.) Complex interactions among features are accommodated because the search process does not rely on complete information, and missing portions of a feature are inferred by extending the feature volumetrically through a procedure called feature completion.
The generate-and-test cycle continues until the recognized features are sufficient to transform the raw material into the desired part. The final output of the feature finder is a decomposition of the volume to be removed into a set of volumetric (solid) features that correspond to manufacturing processes typically performed in 3-axis machining centers. Solid features are crucial for performing geometric tests, and should prove very useful to process planning systems for calculating intermediate workpieces, testing for potential collisions, determining feeds and speeds from the volumes to be removed, and so on. The features may overlap in common regions, which are classified as "optional", and alternative feature decompositions may be produced. Adjacent features with common properties are grouped together into composite features. Accessibility and interaction information are provided to facilitate reasoning about precedences and process sequencing.
The recognizer's output in essence is a CSG representation, in which the desired part is (re-)defined through set difference operations that remove volumetric features from an initial stock. (DSG, for Destructive Solid Geometry, might be a better name...) Although we use CSG-based computations in portions of our experimental recognizer, all of the computations can also be supported by a pure BRep modeler. Therefore, our algorithm can be viewed as a BRep to DSG converter for the domain of parts machinable in 3-axis machining centers.
A proof-of-concept implementation is running in the Knowledge Craft/PADL-2 testbed. Much of the computation is centered on feature completion and verification, and involves geometric tests performed by calling individual procedures of the solid modeler and by manipulating the returned values in Knowledge Craft.
The current recognizer has several conceptual limitations. Specifically, (i) feature completion is limited to 2.5-D swept features, (ii) face segmentation (i.e. associating face subsets with features) for non-template features is not adequately addressed in our work (or in any other existent recognizer, as far we know), (iii) the number of alternative feature decompositions produced is not well controlled, and (iv) 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.
Our current research is aimed at refining some of the ideas and their implementations, and at integration with upstream (design) and downstream (manufacturing) modules. We intend to devise a more sophisticated and flexible hint management system, improve the accessibility analysis (for example, lateral accessibility analysis was not implemented), and link the feature finder to a design-by-features system and to a process planner and NC code generator that exploit the geometric information (e.g., on feature interactions) provided by the recognizer. An important goal is to operate the feature finder incrementally, while an object is being constructed by a designer, so as to support manufacturability critiques in a concurrent engineering environment.
More thinking about efficiency also is needed to cater to complex parts. Some of the approaches to be studied are (i) pre-processing the input so as to minimize the search for geometric patterns (for example, by "sorting" surfaces by principal directions), (ii) using other published feature recognition methods, which are fast but cannot deal with interactions or guarantee validity, as means of generating "strong" hints, and (iii) specification of preferences to focus attention on the more promising hints and to decide which alternatives to pursue first.