CAD feature recognition in nutshell

Compared to B-rep faces, features are higher level entities that model the correspondence between design information and manufacturing activities. For example, while CAD data encompasses a model's shape, features communicate how a specific artifact might be manufactured or assembled [Regli, 1995].

Feature recognition provides a communication medium between CAD and manufacturing applications. Sometimes, feature recognition comes up as an integral part of solid modeling systems and kernels. However, even after decades of research, there is no any conventional systematic approach to feature recognition, because it remains largely application-dependent. We are mainly interested in the material removal features that are common for subtractive technologies, such as milling. At the same time, as practice reveals, a feature recognition framework that serves as a backbone for application-specific feature recognition tends to be abstract enough to stay independent from any particular application.

This section covers the principal CAD feature recognition approaches available in Analysis Situs. Read more on the recognition of specific features in the follow up sections.

Feature recognition approaches

We use two approaches to feature recognition in CAD models:

Rule-based.
Isomorphism.

We do not employ any machine learning techniques, although we do provide means to prepare data for ML, such as voxelization. You can find more information on the AI approaches in feature recognition, for example, in [Ghadai et al, 2018].

The rule-based approach is pretty fast. It can also deal with some feature interactions. At the same time, this method is not highly extendable. Still, this method is somewhat standard as it is probably the most straightforward way to get the result. The essence of the approach is to iterate all B-rep faces while attempting to compose them into groups based on some ad-hoc heuristics. We have listed some of such heuristics in our brief conference paper [Malyshev et al, 2017].

There is a bit of ambiguity in referring to some feature recognition approach as "graph-based." For example, finding isomorphous faces is completely abstract and graph-based as it searches for a pattern's subgraph in the entire model's AAG. At the same time, the rule-based approach is also graph-based as it matches just the same AAG, though in different ways (i.e., by iteration). Therefore, we avoid using this "graph-based" naming in Analysis Situs.

More on rule-based approach

Historically first, this approach remains our favorite. If implemented correctly, it gives the right balance between recognition accuracy and efficiency. All rules are programmed in C++, and that's arguably the downside of the approach, because any customization would require recompilation. At the same time, the method is highly maintainable as it is entirely deterministic and straightforward. The following notions are used throughout the rule-based recognition methods:

Recognizer

The Recognizer is a C++ class, which is the entry point to the recognition routine. The Recognizer accepts a CAD model (or its AAG) and returns the set of faces (and their indices) corresponding to the detected features. There's always an option to store the corresponding attributes in AAG to make the extracted features persistent.

The Recognizer contains the main loop of iterating over the B-rep faces. It may also search for the seed faces that look promising to start recognition from. In fact, it can just iterate over all faces of the model and let the Rules (see below) decide whether they can start recognition from the current face or not. In that sense, the Recognizer handles a recognition "cursor" by moving it over the AAG and letting the Rules do some real job.

The Recognizer manages the Rules. It may apply several Rules if necessary.

Rule

For the given position of AAG iterator (a "cursor"), a Rule performs recognition by applying a certain set of geometric and topological heuristics. The Rule is allowed to visit any faces of the AAG, so it can be seen as a nested loop (or loops) for the main recognition loop. All visited nodes are usually memorized to avoid checking them twice in the main loop.

One of the fundamental heuristics is the dihedral angle between feature faces.

A typical Rule employs the following stages:

Get ready: take the current face and mark it as "visited."
Apply heuristics: attempt to recognize a feature starting from the current face inclusively (the iterated faces are marked as "visited" down the road).
Compose the result: in case of success, and return all "visited" faces as a result.

The Recognizer checks the Rule's status at each iteration. If a Rule fails, the Recognizer cancels the "visited" faces returned by a Rule. If a Rule succeeds, the Recognizer makes sure to skip the visited faces, i.e., to avoid passing them as new seeds at subsequent iterations.

Recognition workflow

The feature recognition tools available in Analysis Situs might be combined freely. They all work on the AAG constructed out of the initial shape. You may choose to build up a new AAG each time you run a recognizer or, alternatively, reuse the same AAG and collect all recognized features as its attributes. Whatever option you prefer, the recognizers will give you a series of indices to address the detected feature faces uniquely.

Imagine you detect all cylindrical holes in the model using the rule-based approach. Let's also assume that the applied rule does not differentiate between different types of holes, i.e., you get through, blind, countersunk, and counterbored holes all in one result set. To distinguish between various hole types, you can apply isomorphism matching. That would be a good idea since the rule-based recognizers have narrowed down the entire search space, and you have as many connected components out of the initial AAG as many features were detected. Finding isomorphous faces is a computationally expensive operation, and partitioning the initial graph will speed up the process drastically (see [Slyadnev et al, 2020] for more details).

Isomorphism

Finding isomorphous faces is a straightforward way for feature matching. The entire process can be broken down to the following steps:

Decompose the initial AAG onto as many connected component subgraphs as you can. This would allow for running the isomorphism algorithm independently and on the reduced search space. One best practice is to use the rule-based recognition for the broad-phase decomposition, and then apply series of isomorphism matches over the decomposed subgraphs.
Prepare the dictionary of features you want to recognize. By "dictionary" we mean a domain-specific storage of feature descriptors that are going to be matched over the CAD part in question. This can be anything, starting from a text file to a remote database holding all feature patterns relevant to your application, machnining process or organization.

The following image illustrates a "stress test" CAD model for the feature recognizer. The model contains three types of holes: countersunk, counterbored, and simple cylindrical holes, in many possible variations.

Recognizing a hole with a rule-based approach may end up with a bunch of hole features, separated from each other. Running the isomorphism matching on each component would allow for extracting such properties as bore's diameter, sink angle, etc. The job of isomorphism is to match the pattern's faces that have some semantics attached to the faces with unknown semantics.

The base class for all rule-based recognizers, which is asiAlgo_Recognizer provides a virtual method named matchConnectedComponent() that is supposed to be overriden by the subclasses. This method accepts a single connected component (e.g., a generic hole) and lets the derived logic to extract all missing properties, such as bore or sink holes' faces using the isomorphism technique.

Limitations

There are some limitations in the recognition methods that employ geometric and topological heuristics:

The input model should be a valid solid.
The CAD faces should be maximized.
The canonical faces should be represented with the analytical surfaces (e.g., if a face is visually planar, it needs to be declared as a plane in the underlying B-rep).