Feature recognition

Yet another heuristic

In the seminal papers related to CAD feature recognition, people proposed simple rules aimed at making the process efficient. One of such was excluding all the faces having convex-only adjacency with its neighbors. We read that "a face that is adjacent to all its neighboring faces with a convex angle does not form part of a feature" in [Joshi, S., & Chang, T. C. (1988). Graph-based heuristics for recognition of machined features from a 3D solid model. Computer-Aided Design, 20(2), 58-66] (read full text). That might be a reasonable observation, of course, and it's trivial to implement. I wouldn't say "we can do better," but there's definitely one extension that is worth trying at least.

A sample part with its convex hull. The faces coincident with the convex hull surface are colored.

The very idea of feature recognition is to extract as much knowledge from a geometric artifact as possible. In Analysis Situs, we do that on attributed graphs, where each attribute represents a bit of knowledge about a single face or an edge. Having a single attributed adjacency graph (AAG) shared among a handful of algorithms, we can oxygenate it with attributes of different nature. Some of them might simply encode the geometry of a specific face (whether it is planar or cylindrical), while others might pop up from a somewhat advanced analysis, e.g., fillet/chamfer recognition.

As a result, we end up having the AAG decorated with all sorts of attributes just like a Christmas tree with toys and balls. Based on that knowledge and perhaps some other rationale, we can compose the ultimate features and extract their properties, e.g., the radius of a fillet chain or the type of a drilled hole. That's a classical old-schoolish approach to the feature recognition problem. It's not as fancy as machine learning (btw, has anyone seen any workable solution based on ML?) but it has a bunch of killing properties: it's fast, reliable, and easy to debug.

A sample part with its convex hull (orange).

Long story short, today I'd like to talk about yet another AAG attribute that can be seen as a more restricted version of what Joshi & Chang proposed (see the link to their paper above). Let's name it the "convex hull property" and assign it to all the CAD faces lying on the workpiece's convex hull. One might argue that such a property does not bring a lot compared to the original angle-based clue. The new property labels all the exterior faces of a model globally and excludes all local protrusions, such as pocket islands. Such a heuristic detects all the CAD faces that are as close to the initial stock volume as possible.

To build a convex hull for a CAD part, one can employ the algorithm developed by Antti Kuukka, which is public domain. The mesh nodes can be used as the input for the algorithm. Other than that, there is not much to say about convex hulls.

Sampling CAD face

Sampling CAD face is easy. You just switch to the UV space and overlay a uniform grid over the parametric portrait of your face.

The UV domain of a face to sample.

Each cell can be colorized in its corners by the scalar values indicating whether the corresponding point belongs to the interior or not.

The overlayed grid.

Such sampling gives us nothing but a black & white raster image. Together with another guy from Switzerland, we are thinking to use that simple technique for automatic object classification based on neural networks. But I digress. Let's leave image recognition aside and just use that simple rasterization for point sampling. Also, let's forget about any parametric distortions for the moment as it's not going to be that important. What we need to know is whether a sampled point belongs to the convex hull of a shape or not. And for that, we first map the sampled UV coordinates back to 3D.

The sampled points mapped to 3D.

To classify if a point is inside, outside, or belongs to the boundary of a parametric portrait, one can use IntTools_FClass2d class of OpenCascade. In this screencast, though, we discover that the OpenCascade's classifier is an overkill that's going to slow down the ultimate algorithm quite a bit. The choice of a fast and reliable PMC method is a subject in itself, and we continue that investigation on the forum, so you may want to jump in and check the current status of this topic.

Point-to-mesh distance

For projecting a point onto a triangulation, Analysis Situs comes up with asiAlgo_ProjectPointOnMesh utility. The computation is fast thanks to using a suitable spatial data structure, which is BVH in that case.

The convex hull of a part with its BVH (yellow) for fast projection.

Once projected, each point is checked for the distance to the projection image. If that distance is within a certain tolerance, the point is said to lie on the convex hull surface. If all sampled points of a specific face are tightly bound to the hull, the entire face is attributed as a convex-hull face.

Applications and discussion

The convex-hull property is yet another geometric clue one could use for automatic feature recognition. It can be seen as a restricted version of the convex-neighbor property proposed in the early days of the CAD feature recognition field. Although we used efficient computations at each stage of the algorithm, the overall execution time is unsurprisingly worse than a simple analysis of dihedral angles. Nevertheless, we now have this heuristic in our toolbox and the plan is to plug it in for the recognition of slots and grooves. Stay tuned.

Want to discuss this? Jump in to our forum.