On the Role of Graph Theory Apparatus in a CAD Modeling Kernel Sergey Slyadnev1 , Alexander Malyshev1 , Andrey Voevodin1 , and Vadim Turlapov2 1 OPEN CASCADE, Nizhny Novgorod, Russia. 2 Lobachevsky State University of Nizhny Novgorod, Nizhny Novgorod, Russia. {sergey.slyadnev, al.s.malyshev, a.m.voyevodin, vadim.turlapov}@gmail.com Abstract. This paper summarizes the experience of authors in solving a broad range of CAD modeling problems where the formalism of graph theory demon- strates 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 fea- tures, 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 demon- strated their efficiency and accuracy in the bunch of industrial applications devel- oped by our team. Keywords: Computer-aided Design, Geometric Modeling, Feature Recognition, Hierarchical Assembly Graph, Attributed Adjacency Graph, Subgraph Isomor- phism 1 Introduction 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 [15], the topology can be expressed in the form of an acyclic directed simple graph (having no self-loops and par- allel edges [4]). The topology graph determines how the primary topological elements (faces, edges, and vertices) are nested. The possibility to have several parent nodes for a Copyright © 2020 for this paper by its authors. Use permitted under Creative Commons Li- cense Attribution 4.0 International (CC BY 4.0). 2 S. Slyadnev et al. single child enables sharing and instancing of the boundary elements. Therefore, graph structures persist in the very foundation of the geometric modeling systems. Besides the topology graph, many other graph structures arise in the modeling sys- tems 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 mod- els 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 [13] (see subsection 2.1). The graph- based approach aimed at the recognition of two-sided models and their types (section 3) also presents the novelty of our paper. 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 Attributed adjacency graph One of the early contributions to the feature recognition field was the introduction of attributed adjacency graph or AAG [8]. The AAG is an undirected graph whose nodes represent B-rep faces, and the arcs encode their adjacency relations (Fig. 1). AAG fa- cilitates solving a wide range of recognition problems bringing there the formalism of graph theory. All nodes and arcs of the AAG can be associated with the application- specific attributes. The attributes aim to capture specific properties of the underlying shape, such as dihedral angles, surface types, and different topological cues (e.g., pres- ence of inner contours in faces). The AAG plays a central role in recognizing volume features, such as holes, pockets, or bosses [11]. The same apparatus applies to the recognition of the secondary features, such as blends and chamfers [17]. The methods presented in sections 2 and 3 exploit AAG as the primary data structure. 1.2 Hierarchical assembly graph The hierarchical assembly graph (HAG) is a directed acyclic graph aimed at represent- ing complex CAD products. The nodes of the graph represent CAD parts and subassem- blies (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 G1 G5 G4 G6 F G3 G2 G1 G2 G6 G3 G5 G4 Convex F Concave Fig. 1. Attributed adjacency graph (on the bottom) for a portion of a CAD model (on the top). The dashed lines represent concave dihedral angles. The solid lines represent convex dihedral angles. 1.3 Other uses of graphs 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 addi- tional 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 topo- logical naming. The naming mechanism supplies boundary elements of a CAD model with persistent identifiers invariant over modifications of a model, including its rebuild- ing 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. Rémi Lequette attempts to establish a topological naming mechanism in a geo- metric modeling kernel (CAS.CADE) independent from any CAD system [10]. Two approaches are discussed by Lequette: labeling and pattern matching. The labeling technique attaches application-specific identifiers directly to the boundary elements of a model (if the geometric kernel supports this) or to the nodes of a history graph. Given that geometric modeling operations support the history of modification, these ap- proaches are equivalent. The pattern matching technique based on searching for graph isomorphisms is seen as a complementary technique for labeling and is aimed at re- moving ambiguities. Jiri Kripac introduces one of the well-known approaches [9] to solve the topolog- ical naming problem. His method is based on the utilization of a face history graph. 4 S. Slyadnev et al. The graph tracks the evolution of faces, including their creation, split, merge, and dele- tion. 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 at- tributed 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 [1]. As in the case of AAG, the nodes and arcs of RAG carry on the application-specific attributes, such as angle type, curvature maps, and others. 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 quadrilat- eral meshing [3, 2], digital shape reconstruction [22], mesh refinement or simplification [5]. Dependency graphs A dependency graph is a data structure that allows for the auto- matic 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). EDGE 3 DEPENDENCY FLOW E3 C3 P4 P1 P3 P2 S3 S10 S2 S7 Fig. 2. A component of a dependency graph in digital shape reconstruction system. Fig. 2 illustrates a part of the dependency graph used in our reverse engineering software package [16] for parameterizing the shape reconstruction process. The nodes 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 Feature recognition In this section, we discuss the applications of graph theory to solving the feature recog- nition 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. 2.1 Isolated features One approach for the recognition of isolated features was presented in our previous pa- per [11]. In particular, it was shown how to compose different geometric and topological heuristics for detecting specific types of volume features, such as holes, bosses, pock- ets, and arbitrarily shaped cavities. In addition to that work, we present a new method for detecting isolated groups of faces that are separable from the given set of capping faces. 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 [11] (we assume that some topology exploration algorithm enumerates all faces of a model). A base face is a face separating a feature from the rest of a CAD model (we elaborate on the separability property below). 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. 6 S. Slyadnev et al. Suppressibility This property captures the ability to suppress the detected feature faces for the sake of CAD part simplification [19]. If |F | = 1, suppression is done by a graph reduction algorithm that eliminates the detected boundary elements from the topology graph of a B-rep model [11]. Such an approach allows for working at the model’s syntax level without running any geometric computations. Therefore, the suppression method is fast and reliable, though it is limited to simple cases only. If |F | > 1, a more general face removal (FR) operator [23] is used for suppression. The FR algorithm removes a target face or a set of faces from the structure of a model with subsequently merging the adjacent faces to restore adjacency. The analysis of suppressibility employs checking two properties expanded below. 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 Fig. 3. To the detection of isolated features. 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 fea- tures 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 bound- aries as such behavior is considered destructive. Capping faces Inner feature Fig. 4. Sample part with a pair of capping faces selected to isolate an inner cavity. 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 spec- ified inlet and outlet faces can be extracted (to be used in CFD analysis, for example). 2.2 Efficient heuristics for subgraph isomorphism 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 [4]. Sim- ilarly, a graph P is isomorphic to a subgraph of G if there can be found a subgraph g ⊂ G isomorphic to P . The subgraph isomorphism problem is known to be NP-complete [6]. The discovery of NP-completeness is often posed as an argument to avoid using the algorithm as it is anticipated to be computationally exhaustive and hence impractical. We consider two primary techniques for gaining a satisfactory performance in the graph matching procedure: sparsing M0 matrix and dimension reduction. Both methods are described below in more detail. We apply the classic Ullman’s algorithm for subgraph isomorphism [21]. Adrian Neumann gives some helpful implementation guides on his website [12] that we also followed. 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 adja- cency 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. 8 S. Slyadnev et al. 1 4 8 7 3 7 2 3 2 6 1 8 5 4 6 5 Fig. 5. Sample part with its attributed adjacency graph G for subgraph matching. 1 2 3 2 1 3 Fig. 6. Pattern feature with its attributed adjacency graph P . 5 has the following form (dashed lines decorate the corresponding 1-based indices of B-rep faces): 1 2 3 4 5 6 7 8 ----------------+ 0 1 1 1 1 0 0 0 | 1 1 0 1 0 1 1 0 0 | 2 1 1 0 1 0 1 1 0 | 3 1 0 1 0 1 1 0 0 | 4 1 1 0 1 0 1 0 0 | 5 0 1 1 1 1 0 0 0 | 6 0 0 1 0 0 0 0 1 | 7 0 0 0 0 0 0 1 0 | 8 The adjacency matrix P is represented as follows: 1 2 3 ------+ 0 1 0 | 1 1 0 1 | 2 0 1 0 | 3 The algorithm sequentially constructs candidate isomorphism matrices M of di- mensions [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): 1 2 3 4 5 6 7 8 ----------------+ 0 0 1 0 0 0 0 0 | 1 0 0 0 0 0 0 1 0 | 2 0 0 0 0 0 0 0 1 | 3 The initial matrix M0 is constructed in a way to specify all possible bijections be- tween 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. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 1 1 1 1 1 1 1 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. Fur- thermore, the dimension N can often be reduced based on the geometric rationale. Both reduction techniques contribute to the search space pruning employing dedicated geo- metric 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 corre- sponding 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 = {α(ei ) : ei ∈ EP }, 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. 10 S. Slyadnev et al. Dimension reduction Joshi and Chang proposed a heuristic aimed at efficient recog- nition of negative volume features, such as holes or pockets [8]. The heuristic consists of eliminating (from AAG) the B-rep faces having convex edges only. Another graph reduction heuristic that we adopted in our work is the exclusion of 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 or louvers [7], but not for countersunk or counterbored holes (the latter often employ faces with inner contours). 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 Fig. 7. Sample flat part with a number of blind counterbored holes. Table 1 shows the results of experiment conducted on a laptop computer with In- tel(R) Core(TM) i5-6300HQ CPU @ 2.30GHz, 16GB RAM, OS Windows 10. The in- put 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. On the Role of Graph Theory Apparatus in a CAD Modeling Kernel 11 Table 1. Execution time of subgraph isomorphism with and without graph reduction heuristics. Graph isomorphism was used to detect all counterbored holes on a flat shape (K = 4). N Num. features No heuristics [sec] Exclude convex [sec] 406 100 0.06 0.04 906 225 0.6 0.05 1606 400 3.2 0.09 2506 625 12.2 0.15 3606 900 36.9 0.22 4906 1225 98 0.35 3 Object classification 3.1 Two-sided models 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. Sheet faces Thickness faces Cutout Fig. 8. Sheet metal part. 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. 12 S. Slyadnev et al. 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 Fig. 9. Tube part. 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). 3.2 Check for unbendable sheets 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 10 5 3 3 9 10 6 7 13 9 (b) 11 4 1 8 2 12 8 2 7 12 1 5 13 6 11 4 (a) (c) Fig. 10. AAG decomposition into connected components for the recognition of sheet metal parts. The graph in (a) corresponds to the CAD part illustrated in the Fig. 8. The derived connected components for the sheet and thickness faces are shown in (b) and (c). From the AAG, we derive a graph named face transition graph (FTG). FTG is con- structed 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 Hierarchical assembly graph A hierarchical assembly graph (HAG) represents the as-designed structure of a digi- tal 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 com- ponents 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. 14 S. Slyadnev et al. 53 30 30 32 48 32 48 55 55 46 46 26 26 23 23 7 7 2 17 2 17 21 21 5 5 30 30 32 48 32 48 55 55 46 46 26 26 23 23 7 7 2 17 2 17 21 21 5 5 30 32 48 55 46 26 23 7 2 17 21 5 Fig. 11. FTG constructed for one side of a sample rectangular tube. Three simple circuits are outlined in bold. The indices of nodes correspond to the indices of faces in the CAD model. chassis wheel-axle 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 [14]. chassis chassis wheel-axle wheel-axle wheel-axle [new] wheel axle wheel wheel axle [new] (a) (b) Fig. 13. (a) The hierarchical assembly graph for the chassis model. The dashed lines denote the path to be singled. (b) The hierarchical assembly graph after transformation. The dashed lines denote the image of the input path in the modified graph. 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 iso- lated, any domain-specific attributes, such as colors or design review notes, can be as- sociated 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 ∈ / P and incident with the nodes of P is reused. Some results of the singling transformation are depicted in Fig. 14. 5 Conclusions and future work Understanding graph formalism is one of the essential competencies a CAD practi- tioner 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 prac- tice 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 16 S. Slyadnev et al. Mi-1,k Mi-1,k Mi-1, k+1 Mi,0 X Mi,n X Mi,0 Mi,n X1 Y Z Y Z (a) (b) Mi-1,p Mi-1, Mi-1,p Mi-1, p+1 p+1 Mi,0 X Mi,0 X1 X2 X3 X4 X (c) (d) 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 [18] al- lows reading CAD models in STEP format, construct AAG, and compute basic shape characteristics, such as dihedral angles. While initially purposed as a prototyping work- bench, this software starts seeing some interest from academia [24] and industry. The recognition of sheet metal parts and feature-based approaches for CAD simplification are commercialized in our CAD Processor software package [13] backed by the corre- sponding research paper [20]. Some topics remain for future investigation. Among such, we consider further de- velopment 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 deal- ing 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 References 1. Agathos, A., Pratikakis, I., Perantonis, S., Sapidis, N., Azariadis, P.: 3D Mesh Segmentation Methodologies for CAD applications. Computer-Aided Design and Applications 4(6), 827– 841 (jan 2007) 2. Boier-Martin, I., Rushmeier, H., Jin, J.: Parameterization of triangle meshes over quadrilat- eral domains. ACM International Conference Proceeding Series 71, 193–203 (2004) 3. Bommes, D., Lévy, B., Pietroni, N., Puppo, E., Silva, C., Tarini, M., Zorin, D.: Quad-Mesh Generation and Processing: A Survey. Computer Graphics Forum 32(6), 51–76 (sep 2013) 4. Deo, N.: Graph Theory with Applications to Engineering and Computer Science (Prentice Hall Series in Automatic Computation). Prentice-Hall, Inc., USA (1974) 5. Gao, S., Zhao, W., Lin, H., Yang, F., Chen, X.: Feature suppression based CAD mesh model simplification. Computer-Aided Design 42(12), 1178–1188 (dec 2010) 6. Garey, M.R., Johnson, D.S.: Computers and Intractability: A Guide to the Theory of NP- Completeness. W. H. Freeman & Co., USA (1979) 7. Gupta, R.K., Gurumoorthy, B.: Classification, representation, and automatic extraction of deformation features in sheet metal parts. Computer-Aided Design 45(11), 1469–1484 (nov 2013) 8. Joshi, S., Chang, T.C.: Graph-based heuristics for recognition of machined features from a 3D solid model. Computer-Aided Design 20(2), 58–66 (mar 1988) 9. Kripac, J.: A mechanism for persistently naming topological entities in history-based para- metric solid models. Computer-Aided Design 29(2), 113–122 (feb 1997) 10. Lequette, R.: Considerations on topological naming. In: Pratt, M.J., Sriram, R.D., Wozny, M.J. (eds.) Product Modeling for Computer Integrated Design and Manufacture: TC5/WG5.2 International Workshop on Geometric Modeling in Computer Aided Design 19–23 May 1996, Airlie, Virginia, USA. pp. 394–403. Springer US, Boston, MA (1997) 11. Malyshev, A., Slyadnev, S., Turlapov, V.: Graph-based feature recognition and suppression on the solid models. In: GraphiCon 2017. pp. 319–322 (2017) 12. Neumann, A.: Ullman’s subgraph isomorphism algorithm. URL: https://adriann.github.io/ullman subgraph isomorphism.html (accessed: 20.06.2020) 13. OPENCASCADE: CAD Processor: CAD-neutral simplification and preparation. URL: https://www.opencascade.com/content/cad-processor (accessed: 28.06.2020) 14. Rappoport, A.: A scheme for single instance representation in hierarchical assembly graphs. In: Falcidieno, B., Kunii, T.L. (eds.) Modeling in Computer Graphics. pp. 213–223. Springer Berlin Heidelberg, Berlin, Heidelberg (1993) 15. Requicha, A.G.: Representations for Rigid Solids: Theory, Methods, and Systems. ACM Computing Surveys 12(4), 437–464 (dec 1980) 16. Slyadnev, S.E., Turlapov, V.E.: To the Development of Open Source Software for the Recon- struction of CAD Models. Programming and Computer Software 45(4), 202–212 (jul 2019) 17. Slyadnev, S.E., Turlapov, V.E.: Simplification of CAD Models by Automatic Recognition and Suppression of Blend Chains. Programming and Computer Software 46(3), 233–243 (may 2020) 18. Slyadnev, S., Malyshev, A., Turlapov, V.: CAD model inspection utility and prototyping framework based on OpenCascade. In: GraphiCon 2017. pp. 323–327. Perm, Russia (2017) 19. Slyadnev, S., Malyshev, A., Turlapov, V.: Automated history-free simplification of mechani- cal CAD models and assemblies. In: GraphiCon 2018. pp. 488–494 (2018) 20. Slyadnev, S., Malyshev, A., Turlapov, V.: Automated history-free simplification of mechani- cal CAD models and assemblies (in Russian). In: GraphiCon 2018. pp. 488–494 (2018) 21. Ullmann, J.R.: An Algorithm for Subgraph Isomorphism. Journal of the ACM (JACM) 23(1), 31–42 (jan 1976). https://doi.org/10.1145/321921.321925 18 S. Slyadnev et al. 22. Varady, T.: Automatic Procedures to Create CAD Models from Measured Data. Computer- Aided Design and Applications 5(5), 577–588 (jan 2008) 23. Venkataraman, S., Sohoni, M.: Reconstruction of feature volumes and feature suppression. In: Proceedings of the Seventh ACM Symposium on Solid Modeling and Applications. p. 60–71. SMA ’02, Association for Computing Machinery, New York, NY, USA (2002) 24. Zhu, F.: Application of analytical and AI-based feature detecting methods for an Energy optimized industrial process. Bachelor’s thesis, Technische Universitat Darmstadt (2019)