Automatic discovery of common design structures in CAD models

This paper presents an approach for extracting common design structures from a set of B-rep models. Here, a B-rep model is first transformed into a face adjacency graph (FAG), and then each node of an FAG is mapped to a point in a two-dimensional plane after representing face shape characteristics with two coordinates. Thus, the common design structures are just the frequently appearing subgraphs of FAGs drawn in a plane. In the area of data mining, the apriori-based graph mining (AGM) is a well-known algorithm for solving the problem of frequent subgraph discovery, but its efficiency is still low in processing large graphs like the FAGs of CAD models. In this research, we develop a novel algorithm that improves AGM in two aspects. First, the exact subgraph-isomorphism checking is replaced by comparing the shape descriptors composed from the point coordinates corresponding to the nodes of the subgraphs in question. Second, a new approach for generating frequent subgraph candidates is adopted, which allows large frequent subgraphs to be found in fewer iterations. Experiments show that the proposed method is efficient and can produce a reasonable result. (C) 2010 Elsevier Ltd. All rights reserved.