Feature recognition in nutshell

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.

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. 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 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 actual recognition from. Actually, 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.

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

Rule

For the given position of AAG iterator, 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 notes can be recorded 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).

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).