Feature Recognition Research at The University of Maryland

Feature Recognition Research

at The University of Maryland

This research is the Ph.D. thesis work of William C. Regli of the Department of Computer Science and Institute for Systems Research. Advisor: Dana S. Nau.

The Problem:

Automated recognition of features from CAD models has been attempted for a wide range of application domains in mechanical engineering. However, the absence of a clear mathematical formalism for the problem has made it difficult to develop a general approach---and thus most of these methods are limited in scope.

In this work we develop a formalization of the problem of recognizing a class of machinable features expressed as MRSEVs (a PDES/STEP library of machining features), and an algorithm for solving this problem. Some of the characteristics of this approach are:

the algorithm handles a large variety of hole and pocket features along with elementary accessibility constraints and blends for those features;
it is provably complete, even if the features intersect with each other in arbitrarily complex ways;
it has O(n^2) worst-case time complexity in the number of solid modeling operations.

If you would like to go directly to some examples click here.

Overview of our Approach:

Although many approaches have been developed for recognizing machinable features in solid models of mechanical parts, most previous work on this topic has focused on introducing new techniques for getting a solution to the problem, without fully exploring the capabilities and limitations of these techniques. As a result, it has often been unclear what specific classes of objects, features, and feature interactions can be handled by previous approaches, making it difficult to evaluate their overall utility.

As a first step toward addressing this difficulty, we have developed a formalization of the problem of recognizing a subset of the set of all machinable features expressible as MRSEVs (Material Removal Shape Element Volumes) developed by Thomas Kramer at NIST. MRSEVs are volumetric features corresponding to machining operations on 3-axis milling machines. MRSEVs can be defined using EXPRESS (the official PDES information modeling language) and PDES form features. Kramer has already done this for a subset of the MRSEV library, and has defined the rest using an EXPRESS-like language.

Based on this formalization, we have developed an algorithm for solving the problem of recognizing every solid that can be described as the difference between an arbitrary piece of stock and an arbitrary set of machinable features. Currently, our approach is designed only to handle linearly swept features (i.e., holes and pockets). However, our definitions of holes and pockets are more general than the definitions used in a number of feature recognition systems; for example, the pockets may be complicated swept contours that include corner radii, islands, blends and other characteristics, in order to realistically describe a non-trivial set of mechanical parts.

The algorithm is provably complete over the set of all solids in our class, even if the features intersect with each other in arbitrarily complex ways. For example, our algorithm can handle each of the objects in the figures that follow.

The primary goal of our work has been to develop a general definition of the problem domain, an algorithm capable of handling all problems in that domain, and formal analyses of the algorithm's completeness and complexity in an attempt to address the significant deficiencies that existing approaches in one or more of these areas. The new approach we have developed has the following benefits:

Instead of using expert-system rules as are used in many previous systems, we have adopted an algorithmic approach to the development and specification of our feature recognition methodology. The benefits to such an approach include: an explicit specification of the input and the output domain of the feature recognition algorithm; a pseudo-code recognition algorithm in terms of solid modeling operations that are used; and the ability to perform an analysis of complexity on the algorithm. In particular, our algorithm is guaranteed to find feature models for all parts describable with our features, regardless of how complicated the interactions are among the features.
The algorithm's complexity of O(n^2) (in the number of solid modeling operations) represents an improvement over other approaches such as those based on subgraph isomorphism matching and expert systems, some of which require exponential time in the worst case. In addition, O(n^2) is a worst-case bound on the algorithm and would only occur in the most geometrically pathological examples. The typical-case run-time would likely be lower.

Some Examples:

This part:

contains instances of hole and pocket features.

Here is the set of holes found by our algorithm:

This is the pocket found:

This figure shows the complete feature model with respect to the part. Click on the image to see full sized picture...

The following part may pose a problem to existing feature recognition systems. It was presented to us an audience memeber at the 1993 ACM/IEEE Symposium on Solid Modeling and Applications. It is basically a simple part with what appears to be four interacting holes.

Many (perhaps most) feature recognition systems do not take into account the fact that pockets may have corner-radii or rounded sides. The interacting of the holes with other features may remove information vital in finding a feature model. Problems occur if one tries to recognize this part as four holes alone. The reason? The material volumes removed by the machining operations creating the holes do not remove all the necessary stock material. This can be seen in the solid model of the workpiece on the right hand side. Click on the image to see...

Our methodology finds, in addition to the holes, the pocket needed to reduce the stock to the part. This is as expected---we have proven that our algorithms are complete over the set of parts that the hole and pocket MRSEVs describe (i.e. if there is a set of features that describe the part, it will be found).

For the next two examples, we modeled real machined parts. While admittedly they are not the most extrodinarilly complex examples of machined parts they do contain real instances of real machined features.