This paper summarizes the experience of authors in solving a broad range of CAD modeling problems where the formalism of graph theory demonstrates its expressive power. Some results reported in this paper have never been published elsewhere. The set of topological and geometric heuristics backing the subgraph isomorphism algorithm is presented to achieve decent performance in our extensible feature recognition framework. By the example of sheet metal features, we show that using wise topological and geometric heuristics speeds up the search process up to interactive performance rates. For detecting CAD part's type, we present the connected components' analysis in the attributed adjacency graph. Our approach allows for identifying two-sided CAD parts, such as sheet metals, tubes, and flat plates. We use the notion of face transition graph for the unfoldability analysis. The basic operations on hierarchical assembly graphs are formalized in terms of graph theory for handling CAD assemblies. We describe instance singling operation that allows for addressing unique part's occurrences in the component tree of an assembly. The presented algorithms and ideas demonstrated their efficiency and accuracy in the bunch of industrial applications developed by our team.
Because of its inherent simplicity, the apparatus of graph theory found extensive use
in industrial geometric modeling. One of the well-turned ideas emerged early on was
distinguishing between the syntax (topology) and the semantics (geometry) of digital
shape representation. In the boundary representation scheme [
Besides the topology graph, many other graph structures arise in the modeling systems for solving specific problems. We name a few most commonly used data structures here. The face adjacency graphs are extensively used in feature recognition methods. The hierarchical assembly graphs are employed to represent and manipulate complex product representations where single components are arranged following their ”part-of” relations. The function dependency graphs allow building up the parametric CAD models and automate the dependent algorithms’ execution. Additional specialized graph structures serve at solving specific design problems, such as recognition of a model type or digital shape reconstruction. For polygonal models, graph formalism facilitates segmentation aimed at the recovery of missing design intent.
In this paper, we review some of the commonly used graph structures following
our CAD software development experience. Some reported results have never been
published elsewhere. Among such, the formalism that we used for simplification of
CAD models in our CAD Processor software [
A graph is a pair (V; E), where V is a set of vertices (nodes) and E is a set of edges (arcs). We use the terms ”nodes,” ”vertices,” ”arcs,” and ”edges” interchangeably as the meaning of each term should be clear from the context. 1.1
One of the early contributions to the feature recognition field was the introduction of
attributed adjacency graph or AAG [
The AAG plays a central role in recognizing volume features, such as holes, pockets,
or bosses [
The hierarchical assembly graph (HAG) is a directed acyclic graph aimed at representing complex CAD products. The nodes of the graph represent CAD parts and subassemblies (also called ”prototypes”), while arcs denote occurrences of prototypes within each other following their ”part-of” relations. Affine transformations are attached to arcs to give the corresponding occurrences proper placement in the modeling space. We present more details on HAG in section 4.
On the Role of Graph Theory Apparatus in a CAD Modeling Kernel 3
G5 Graph theory found such widespread use in the computer-aided design field that it is hardly possible to enumerate all its occurrences. Below, we briefly discuss some additional application areas that are of particular interest to our research team. The reader is directed to the cited papers for more details on the touched subjects.
Topological naming One issue which is well-understood yet hard to resolve is topological naming. The naming mechanism supplies boundary elements of a CAD model with persistent identifiers invariant over modifications of a model, including its rebuilding from scratch. The application has to reattach any attributes associated with faces, edges, and vertices whenever a model’s geometry is changed. Such a mechanism is traditionally a backbone of history-based parametric modeling systems.
Re´mi Lequette attempts to establish a topological naming mechanism in a
geometric modeling kernel (CAS.CADE) independent from any CAD system [
Jiri Kripac introduces one of the well-known approaches [
The graph tracks the evolution of faces, including their creation, split, merge, and deletion. The face history graph is a directed acyclic graph with the nodes representing the faces being traced. The incoming edges of this graph represent the information of the ancestors of the face. The outgoing edges represent what happened to the face.
It should be noted that both approaches mentioned above use a variety of topological and geometric cues for seeking the boundary elements. A general mechanism for pattern matching is, therefore, of particular interest. In section 2.2, we elaborate on a set of efficient heuristics for matching CAD model’s faces.
Region adjacency graph Region adjacency graph (RAG) is the generalization of
attributed adjacency graph to the sets of faces. Unlike AAG, where each node represents
a single face of a boundary representation, each node of the RAG encodes a region (a
collection of faces). The graph edges express adjacency relations between the regions.
One of RAG’s application is the mesh segmentation [
Mesh-based regions tend to capture the missing design intent of a polygonal model.
The knowledge of regions unlocks further 3D processing workflows, such as
quadrilateral meshing [
Dependency graphs A dependency graph is a data structure that allows for the automatic execution of algorithms whose inputs and outputs are interrelated. Such graphs found extensive use in the engineering software packages ranging from computer-aided design to numerical simulation (ANSYS Workbench system is an example).
Fig. 2 illustrates a part of the dependency graph used in our reverse engineering
software package [
On the Role of Graph Theory Apparatus in a CAD Modeling Kernel 5 of this graph represent the algorithms, and the arcs denote the dependency relations. For example, the algorithm P1 cannot be executed unless the algorithms C3 and E3 are done. A critical aspect of any system that employs dependency graphs is searching and resolving cyclic dependencies. 2
In this section, we discuss the applications of graph theory to solving the feature recognition problem. In contrast to the ”design-by-features” paradigm of modeling, feature recognition allows for extracting the design intent from a CAD model that does not possess a construction history. The applications of the feature recognition technique are manifold, ranging from shape modeling to fabrication costs estimation.
This section explains how graph theory’s formalism can be exploited in solving two engineering problems: CAD data simplification and sheet metal unfolding. Feature recognition aims at extracting specific groups of B-rep faces for further reasoning. In simplification, the engineer may want to suppress all small holes and blends to switch from a detailed design geometry to a simulation-ready model (e.g., to perform structural analysis with FEM). In sheet metal recognition, extracting such features as bends, walls, louvers, or bridges (to name a few) facilitates manufacturing planning.
One approach for the recognition of isolated features was presented in our previous
paper [
Let G be the attributed adjacency graph of a CAD part in question, and F =
fb1; fb2; :::; fbN
be the serial indices of the selected base faces [
The following properties are checked to detect and suppress the isolated features starting from a set of base faces: Separability The subgraph G F obtained by the deletion of the base faces’ nodes should contain at least c + 1 connected components (there can be more if the base faces enclose several inner contours). Here, c is the number of connected components in the initial graph G. This condition can only hold if the target feature is geometrically separable, i.e., it does not contain any perforations such as through holes. Therefore, for the successful detection of isolated features, the CAD model may need additional simplification to ensure the separability property.
Suppressibility This property captures the ability to suppress the detected feature faces
for the sake of CAD part simplification [
Inner boundary inclusion Let C (G F ) be a connected component capped by the base faces F . Let e( ) denote all B-rep edges extracted from a face set in question. Let i(e( )) denote the inner edges, i.e., the edges constituting inner contours of a face set (Fig. 3). Then, the condition i(e(F )) e(C) expresses the requirement of boundary inclusion for the inner edges of F into the separated feature C. If this condition does not hold, the inner edges of the base faces could not be suppressed. The inclusion condition should be tested for each inner contour of the base set F independently as, for example, this condition does not hold for a base face with multiple holes.
inner contour
outer contour
Outer boundary exclusion Let o(e( )) denote the outer edges of a given face set (Fig. 3). Let Co G denote the faces in G that are adjacent to F via its outer edges o(e(F )). The condition C \ Co = ; restricts the isolated feature C from having any common edges with the outer contour of F . If this condition does not hold, the outer edges of F do not remain intact on suppression, hence the feature is not suppressible.
The outer boundary exclusion condition may look excessive as most separable features growing from the inner edges automatically satisfy it. However, this condition
On the Role of Graph Theory Apparatus in a CAD Modeling Kernel 7 ensures that the suppression algorithm will never affect the capping faces’ outer boundaries as such behavior is considered destructive.
The formalism outlined above allows for generalization to a disconnected set of
faces when fbi are not adjacent (Fig. 4). As a result, through channels between the
specified inlet and outlet faces can be extracted (to be used in CFD analysis, for example).
Two graphs G and G0 are said to be isomorphic if there is a one-to-one correspondence
between their nodes and arcs such that the incidence relationship is preserved [
The subgraph isomorphism problem is known to be NP-complete [
We apply the classic Ullman’s algorithm for subgraph isomorphism [
The algorithm starts by constructing an attributed adjacency graph G for the whole CAD part (Fig. 5). The pattern feature to match is represented by the attributed adjacency graph P (Fig. 6). If what follows, we assume that all graphs are specified with their adjacency matrices. The adjacency matrix G for the test part illustrated by Fig. Fig.5.SamplepartwithitsattributedadjacencygraphGforsubgraphmatching. 3 5 has the following form (dashed lines decorate the corresponding 1-based indices of B-rep faces): The adjacency matrix P is represented as follows:
The algorithm sequentially constructs candidate isomorphism matrices M of dimensions [K N], where K is the number of nodes in P, and N is the number of nodes in G. Checking
On the Role of Graph Theory Apparatus in a CAD Modeling Kernel 9
M (M G)T = P (1) one can verify that the following matrix M encodes the sought-for bijection (that can be verified looking at Figures 5 and 6):
The initial matrix M0 is constructed in a way to specify all possible bijections between the nodes of P and G. E.g., the following matrix prohibits mapping (2; 8) as d(2) 6= d(8), where d( ) denotes a degree of a graph node.
The algorithm constructs candidate matrices M deriving them from M0 so that each row contains exactly one 1, and a column contains at most one 1. Each candidate matrix is checked for isomorphism using the equation (1).
For efficient matching, the initial matrix M0 should be as sparse as possible. Furthermore, the dimension N can often be reduced based on the geometric rationale. Both reduction techniques contribute to the search space pruning employing dedicated geometric and topological heuristics that are discussed below.
Sparsing M0 matrix The element M (vP ; vG) is nullified if any of the following conditions are satisfied for any pair of vertices in P and G graphs: – d(vP ) > d(vG), i.e., the pattern’s vertex vP has more incident arcs than the corresponding vertex vG of the problem graph G. This condition is hardly a heuristic as it should always hold. We enumerate it here with others to have the entire heuristics set in one list. – Since AAG encodes concave/convex properties of the dihedral angles in its arc attributes, they are also taken into account. Let ( ) be angle type attribute in the adjacency graph. We formulate AP = f (ei) : ei 2 EP g, where EP is the set of edges for the graph P . The set AG is formulated similarly. The heuristic for M (vP ; vG) nullification requires that AP AG, i.e. all the pattern’s angles can be found in the subgraph of G being tested. – As every AAG node corresponds to a B-rep face, some additional properties can be queried from the geometric and topological data structures. E.g., the number of vertices, edges, and contours should be identical for the matched faces (though, in some cases, this restriction can be relaxed). The types of host surfaces should match as well. – More heuristics can be added to narrow down the search space. E.g., it is possible to take into account such geometric properties as dimensions of the B-rep elements being matched.
Dimension reduction Joshi and Chang proposed a heuristic aimed at efficient
recognition of negative volume features, such as holes or pockets [
A practical implementation of the graph isomorphism method should employ one or the other heuristic set depending on the feature type. From the software architecture standpoint, all detectable features and their effective heuristics can be organized in a catalog (e.g., a file or a database). With such a data-driven architecture, the users are permitted to extend the catalog with their application-specific features. counterbored hole
Table 1 shows the results of experiment conducted on a laptop computer with Intel(R) Core(TM) i5-6300HQ CPU @ 2.30GHz, 16GB RAM, OS Windows 10. The input CAD model represents a flat plate with a rectangular pattern of counterbored holes (Fig. 7). Each hole is a shell composed of four faces (K = 4). The total number of faces N is a modeling parameter.
As one can see from the experimental data, excluding convex-only faces allows us to cope with the algorithm’s high inherent complexity. The detection is done in a fraction of second even for large CAD parts containing thousands of faces.
Another advantage of the heuristics mentioned above is that they break down the initial graph G into a set of connected components. Since all connected components are independent of each other, the graph isomorphism algorithm can be launched in parallel mode (using several CPU or GPU cores). In our experiments, we process each connected component separately and leave parallel processing for future investigation.
N 406 906 1606 2506 3606 4906 100 225 400 625 900 1225
Two-sided models are widely spread in the industry. For these kinds of models, humans can quickly identify a lower and an upper side, usually residing at a constant thickness from each other. Some examples of such objects include flat plates (Fig. 7), folded sheet metal parts (Fig. 8), profiles, and tubes (Fig. 9). These objects are computationally convenient as they possess a certain set of properties that allow for reliable checking by ad-hoc heuristics. The graph-based heuristics play a central role in capturing the essence of a two-sided object: the possibility of separating both sides. Here we describe the recognition process for the folded sheet metal parts, including straight rectangular tubes. For other two-sided objects, the recognition principles may differ in the set of employed heuristics, while the basic principle of AAG separation holds.
The recognition process starts from choosing a seed face (typically, a planar one) and finding the opposite (mate) face by casting a ray pointing inside the part’s material.
From the two detected faces, a propagation procedure starts. All neighbor faces are visited in the order, which assumes that the cylindrical faces (bends) accompany the planar faces. All neighbors should be smoothly connected. The iteration is done twice: starting from the seed face and its opposite one. The iteration procedure terminates when no neighbor faces are left in the model. All faces remaining unvisited by the end of propagation are declared as ”thickness candidates.” The indices of these faces ground the primary separation heuristics.
Sheet faces
Thickness face
The first heuristic consists of the deletion of the unvisited nodes from the AAG (Fig. 10a) and checking the number of connected components remaining in the graph (the elimination of a graph vertex always implies the deletion of its incident edges). For the two-sided parts, precisely two connected components have to remain after the removal of the thickness candidates (Fig. 10b).
The other heuristics starts from deleting all but unvisited faces from the initial state of AAG. The remaining nodes may yield a set of connected components representing both the sheet model’s cutouts (Fig. 8) and its corner thickness faces. The cutouts are distinguished as the face sets residing on the internal contours of the base sheet faces (detected by the propagation process as described above). The detected groups of inner faces are eliminated from the reduced graph so that it finally contains one or several connected components representing only the outer cuttings of the sheet. The remaining nodes should either have no incident edges or yield circuits in the graph, i.e., they should happen to be arranged in loops, where each vertex has a degree of two (Fig. 10c). If a CAD part is recognized as a sheet metal object, that does not necessarily mean that it allows for unfolding (that is a basic requirement for properly designed sheet metals).
On the Role of Graph Theory Apparatus in a CAD Modeling Kernel 13 13 12 (a) 11 7 9 8 4
2 10 6 3 5 1 6 5 13 12 7 8 11 3 9 4 2 1 10 (b) (c)
From the AAG, we derive a graph named face transition graph (FTG). FTG is constructed by eliminating all vertices vb representing the bend faces and collapsing their incident edges. The remaining vertices represent the sheet faces (sheet metal walls).
A two-stage procedure verifies if a CAD model is topologically closed. At the first stage, the FTG is searched for a circuit (Fig. 11), i.e. a closed train of vertices having the degree of two: v1 e1 v2 e2 ::: v1, deg(vi) = 2. If no circuits are detected, the verification procedure stops. Otherwise, a circuit is subsequently verified against the extra set of geometric heuristics that imply certain geometric checks on visiting the graph nodes. Stated briefly, the heuristics aim to calculate the angle spanned by the radius vector, pointing to each face being traversed. If the accumulated angle equals 2 , the CAD model is considered closed, hence not unfoldable. Otherwise, the next circuit is checked until no circuits remain in the FTG. 4
A hierarchical assembly graph (HAG) represents the as-designed structure of a digital product. The nodes of a HAG are the assembly components nested into each other. The directed arcs denote ”part-of” relationships between the components. The components are nested into each other by instancing, i.e., referencing a unique geometry or subassembly (we use the ”prototype” term to refer to both) with a specific matrix of rigid body transformation. The possibility for a prototype to be referenced several times yields multiple parent nodes in the graph. For example, consider a car chassis containing two axles and two wheels. Then, given that HAG is a multigraph (nodes are the prototypes, arcs are the instances), the assembly can be represented as shown in Fig. 12.
32 48 32
48 26 26 2 2 30
55 30 55 17 17 46 46 5 5 32
48 7 21 7 21 23 23
chassis wheel axle Fig. 12. A hierarchical assembly graph for a chassis model (nodes are the prototypes and arcs are the instances).
On the Role of Graph Theory Apparatus in a CAD Modeling Kernel 15
Any modification of a prototype affects all its occurrences in a product. However,
it is often necessary to work with a single occurrence of a component that is addressed
uniquely by a path of edges in the graph. Therefore, a mechanism to extract unique
occurrences of the assembly components is of high interest. Such a tool called instance
singling was thoroughly discussed by A. Rappoport [
chassis wheel
axle wheel [new] chassis (b)
wheel-axle wheel axle
Let us consider a chassis model composed of two wheel-axle subassemblies (Fig. 12). A path from the root node down to the ultimate leaf addresses a single wheel of interest (Fig. 13a). After instance singling, the graph illustrated in Fig. 13b is obtained. Informally, instance singling operates as a ”path disambiguation” operation. Once isolated, any domain-specific attributes, such as colors or design review notes, can be associated with the part in question, not affecting its other occurrences. In the example above, instance singling operation aims at deep copying the geometric representation of a part while preserving its placement in the modeling space.
Let Mi;j denote the nodes of the HAG, where i is the depth from the root, and j is a serial index within a parent. Let P = (e0; e1; :::ek 1) be a path to the node Mk;j (not necessarily the leaf one). The instance singling operation transforms the hierarchical graph in a way to keep the number of paths unchanged while reusing as many existing connections between nodes as possible. The operation automatically copies the nodes preceding Mk;j along the path P . Any edge e 2= P and incident with the nodes of P is reused. Some results of the singling transformation are depicted in Fig. 14. 5
Understanding graph formalism is one of the essential competencies a CAD practitioner has to possess. Graphs not only allow us to design efficient data structures but serve to formalize the driving ideas behind the CAD algorithms. For example, as we saw above, graphs can play a central role in recognizing sheet metal parts. As practice proves, adjacency graphs, including their variations, such as RAG or FTG, define a sound framework for feature recognition and object classification. At the higher level of
Mi,0 Mi,0
Y Mi-1,p
Mi-1,k X Mi-1, p+1
Mi-1,k Mi-1,p
Mi,0
Y X2 (b) (d)
Mi,n Z
Mi-1, k+1
X1 Mi-1,
p+1 Mi,0
X1
X3
X4
X Fig. 14. (a) The initial HAG. The dashed lines denote the path to be singled. (b) The transformed HAG. The dashed lines denote the image of the singled path. The figures (c) and (d) illustrate how one prototype can be instanced by several assemblies. abstraction, hierarchical assembly graphs serve to represent complex digital products. Any modification to the product structure is then expressed in the language of graph theory. A sound formalism is a critical factor in developing efficient and sustainable algorithms.
We publish parts of our research under open-source terms to stimulate interest in
geometric modeling and feature recognition. Our Analysis Situs framework [
Some topics remain for future investigation. Among such, we consider further development of graph isomorphism approach aimed at combining feature definitions with the corresponding ad-hoc heuristics. Additionally, we are looking into developing a data framework for the hierarchical assembly graphs and exposing a common API for dealing with product structures while remaining compliant with international standards like ISO 10303 (STEP). Designing such a framework is currently our work in progress. The utilization of the region adjacency graphs for mesh segmentation is another direction of our future work.
Graphs allow for insightful visualization being of much help in 3D data analysis and geometric reasoning. According to our experience, graph visualization facilities are underexploited in the CAD community. Therefore, additional efforts worth spending on developing a software package aimed at cognitive visualization of graph structures in their application to CAD.
On the Role of Graph Theory Apparatus in a CAD Modeling Kernel 17