Архивы

Searching for subgraph isomorphisms has been considered as a general way of a feature matching over the past decades. Although this method is known to possess high complexity, it has remarkable advantages over the rule-based approaches which employ ad-hoc shape interrogation procedures. The primary benefit of the subgraph isomorphism method is its ability to handle custom feature definitions (i.e., the user's features). It is a single common algorithm that operates with whatever feature descriptors represented with their AAG subgraphs. In practice, the availability of isomorphism searching algorithms allows users of a geometric modeling system to specify their features using a formal graph language or simply by interactive picking of feature faces.

The computational complexity of subgraph isomorphism is O(N^K), where N is the number of faces in the problem graph, and K is the number of feature faces to match. While such a complexity implies a computationally exhaustive implementation, the overall approach remains practical. An appropriate set of topological and geometric heuristics should be employed to reduce computation time. The purpose of heuristics is two-fold. First, by preliminary elimination of some nodes from the CAD model's AAG, one reduces the dimension of a problem, i.e., the employed adjacency matrix. Second, eliminating impossible bijections from the candidate isomorphism matrix reduces the number of checks, making the overall computation less intensive than in a general case.

In this blog post, we will conduct a simple experiment of searching for counterbored holes in a flat sheet metal part (e.g., a front panel). The purpose of this small study is to prove that the isomorphism technique can be practical if used wisely. Let us start with constructing a counterbored hole that will serve as a feature to match. Here is how you can do this in Analysis Situs:

> make-cylinder cyl1
> make-cylinder cyl2 0 0 -2 1.5 2
> bop-fuse feat cyl1 cyl2; donly feat
> set-as-part feat; fit

Counterbored hole as a solid body to subtract from a stock shape later on.

Now we need to prepare the test model, which is a parallelepiped stock shape having a rectangular pattern of holes. Here is the script for constructing that sort of shape:

> set numRows 10
> set numCols 10
> disable-browser
> disable-plotter
> disable-notifier
> disable-transactions
> make-box plate -10 -10 -2 [expr 10*$numCols + 10] [expr 10*$numRows + 10] 5
> make-compound tool
> for {set col 0} {$col < $numCols} {incr col} { for {set row 0} {$row < $numRows} {incr row} { make-cylinder cyl1 [expr $col*10] [expr $row*10] 0 1 1; make-cylinder cyl2 [expr $col*10] [expr $row*10] -2 1.5 2; bop-fuse feat${row}_${col} cyl1 cyl2; add-subshape tool feat${row}_${col}} }
> bop-cut plate plate tool
> enable-transactions
> enable-notifier
> enable-plotter
> enable-browser
> set-as-part plate; donly; fit

There are many "disable" and "enable" commands that are used to eliminate all housekeeping overheads induced by visualization, data model transactions, logging and updating UI widgets. That's a simple trick that allows measuring the pure algorithm's performance, without any side effects. The rest of the code is quite self-explanatory: we build up a tool body (to be used in Boolean subtraction) in the double for-loop, and then cut the parallelepiped shape with that tool. Another performance hint here is to avoid using the Boolean operation many times; otherwise, it's gonna get stuck for many minutes.

Plate model with a rectangular grid of counterbored holes.

Subgraph isomorphism algorithm is available in our open-sourced Analysis Situs platform, so I do not reveal much of implementation details over here. Still, there is no magic in the Ullman's algorithm of matching, and one can easily discover how bad things are if we omit using smart heuristics. Notice the inherently nonlinear increase in the computation time (where N is the number of faces in a CAD part):

Execution time of subgraph isomorphism without graph reduction heuristics.

In the paper [Joshi, S. and Chang, T.C. 1988. Graph-based heuristics for recognition of machined features from a 3D solid model. Computer-Aided Design 20, 2, 58-66], authors propose a heuristic aimed at efficient recognition of negative volume features. The heuristic consists of eliminating (from AAG) the B-rep faces having convex edges only.

Wireframe representation of a CAD part with colors encoding convex/concave properties of dihedral angles.

Another heuristic that allows reducing the dimension of the graph isomorphism problem is excluding faces having internal loops (base faces). Applicability of one or another heuristic depends on the type of feature being matched. E.g., base faces can often be excluded when searching for sheet metal features, such as bridges, louvers, etc., but not for countersunk or counterbored holes (the latter often employ faces with inner contours).

Execution time of subgraph isomorphism when convex-only faces are excluded.

If you want to know more about feature recognition and pattern matching, meet us at Graphicon 2020 this year. We hope to bring there a talk on graph methods in computer-aided design.

Want to discuss this? Jump in to our forum.