Similarity Assessment Of 3D CAD Models Based On Efficient Graph Matching

The similarity assessment of three-dimensional CAD models can effectively support the retrieval of three-dimensional CAD model and thus reuse existing designs significantly, shorten product development cycles and reduce product development costs. Because of the topology, geometry and high-level semantics information contained by three-dimensional CAD models, attributed graphs are often used as the representation of three-dimensional CAD models. However, the traditional graph matching is NP-complete problem and their complexity is exponential, can not meet the practical application requirements. Therefore how to evaluate the similarity between three-dimensional CAD models efficiently based on graph matching is an imperative task for design knowledge reuse. In this thesis, the approach to assessing the similarity between two three-dimensional CAD models based on efficient graph matching is discussed.The main contents are presented as follows:A new similarity assessment method for three-dimensional models based on enhanced random-walks graph matching is proposed. In this approach, the traditional random-walk graph matching is extended to the feature dependency graph whereas its efficiency is maintained. Graph translation function is used to eliminate the sink nodes in feature dependency graph. Probability normalization function is used to eliminate the unreasonable disturbance among features. Classification of nodes is used to reduce the matching space and improve the efficiency.A new three-dimensional assembly model similarity assessment based on tree-graph matching is proposed. In this approach assembly construct relationship, assembly constraint relationship and parts attribute are all considered. A tree and a smaller graph are provided to instead the large graph of traditional JNC representation. Assembly construct tree is used to represent assembly construct relationship. Assembly constraint graph is used to represent assembly constraint relationship. The nodes attributes are used to represent the parts attribute. Assembly constraint graph matching efficiency is improved by the guidance provided by assembly construct tree matching results.Based on above results, a similarity assessment function module is implemented and embedded into the design reuse-oriented three-dimensional CAD model retrieval prototype system ZD-DRCMRS (ZheDa Design Reuse Oriented 3D CAD Model Retrieval System) developed by our research team. Some tests on this function module with some CAD models are conducted, and the results show the validity and the efficiency of the proposed approaches.