# US 2003/0208285 A1 · Method for comparing solid models

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 2003/0208285 A1
- Document ID: US20030208285A1
- Status: Published application
- Kind: A1
- Application number: 10/430,046
- Filed: 2003-05-06
- Published: 2003-11-06
- Earliest claimed: 2002-05-06
- Assignees: Drexel University
- Inventors: William C. Regli; Vincent A. Cicirello
- Web page: https://patentgrep.com/patent/US20030208285A1

## CPC

- G05B 19/4097: characterised by using design data to control NC machines, e.g. CAD/CAM (G05B19/4093 takes precedence)
- G06F 30/17: Mechanical parametric or variational design
- G06V 30/1988: {Graph matching (graphical image representation G06V30/18181)}
- G06F 2111/04: Constraint-based CAD
- G05B: CONTROL OR REGULATING SYSTEMS IN GENERAL; FUNCTIONAL ELEMENTS OF SUCH SYSTEMS; MONITORING OR TESTING ARRANGEMENTS FOR SUCH SYSTEMS OR ELEMENTS (systems for controlling or regulating non-electric variables G05D; systems for regulating electric or magnetic variables G05F; control devices or systems insofar as characterised by mechanical features only G05G)
- G06F: ELECTRIC DIGITAL DATA PROCESSING (computer systems based on specific computational models G06N)
- G06V: IMAGE OR VIDEO RECOGNITION OR UNDERSTANDING

## Abstract

A method for determining a similarity of a first solid model to a second solid model is disclosed. The method includes the steps of: selecting a set of features for representing the first solid model; extracting features corresponding to the selected set of features from the first solid model; constructing an undirected model dependency graph of the first solid model based on the selected set of features; extracting features corresponding to the selected set of features from the second solid model; constructing an undirected model dependency graph of the second solid model based on the selected set of features; comparing the undirected model dependency graph of the first solid model with the undirected model dependency graph of the second solid model; and outputting a numerical measure indicative of the similarity of the first solid model to the second solid model.

## Claims

### Claim 1

A method for determining a similarity of a first solid model to a second solid model, the method comprising the steps of:
selecting a set of features for representing the first solid model;
extracting features corresponding to the selected set of features from the first solid model;
constructing an undirected model dependency graph of the first solid model based on the selected set of features;
extracting features corresponding to the selected set of features from the second solid model;
constructing an undirected model dependency graph of the second solid model based on the selected set of features;
comparing the undirected model dependency graph of the first solid model with the undirected model dependency graph of the second solid model; and
outputting a numerical measure indicative of the similarity of the first solid model to the second solid model.

### Claim 2 (depends on 1)

The method of claim 1, wherein the step of comparing the undirected model dependency graph of the first solid model with the undirected model dependency graph of the second solid model includes the step of testing for the existence of a subgraph isomorphism of the undirected model dependency graphs of the first solid model and the second solid model.

### Claim 3 (depends on 1)

The method of claim 1, further including the step of finding a large enough common subgraph of the undirected model dependency.

### Claim 4 (depends on 1)

The method of claim 1, wherein the numerical measure is based on a ratio of mismatched edges to total edges of the smaller of the undirected model dependency graphs being compared.

### Claim 5 (depends on 1)

The method of claim 1, further including the step of classifying the second model into one of a plurality of predetermined categories based upon a value of the numerical measure.

### Claim 6

A method of identifying at least one solid model in a knowledge-base storing a plurality of solid models having a predetermined similarity to a query model, the method comprising the steps of:
selecting a set of features for representing the query model;
extracting features corresponding to the selected set of features from the query model;
constructing an undirected model dependency graph of the query model based on the selected set of features;
comparing the undirected model dependency graph of the query model with an undirected model dependency graph of at least one of the plurality of solid models;
computing a numerical measure indicative of the similarity of the query model to the at least one of the plurality of solid models; and
identifying the at least one solid model having the predetermined similarity based upon the numerical measure of similarity being within a predetermined range.

### Claim 7 (depends on 6)

The method of claim 6, wherein the knowledge-base is indexed by the relative similarity of each of the plurality of solid models to each other, the method further comprising the steps of:
comparing the undirected model dependency graph of the query model with the undirected model dependency graph of each of the plurality of solid models;
computing the numerical measure of similarity of the query model relative to each of the plurality of solid models; and
identifying each one of the plurality of solid models as having the predetermined similarity by the measure of similarity falling within the predetermined range.

### Claim 8 (depends on 6)

The method of claim 6, wherein the knowledge-base is indexed with a tree having a root node and child nodes, the method further comprising the steps of:
comparing the undirected model dependency graph of the query model with an undirected model dependency graph of a solid model associated with the root node;
computing the numerical measure of similarity of the query model relative to the solid model associated with the root node;
selecting a branch of the root node based on the outcome of comparing the numerical measure of similarity with a predetermined value;
repeating the comparing, computing and selecting steps with each subsequent child node of the root node until a leaf is reached; and
identifying each one of the solid models as having the predetermined similarity by the numerical measure of similarity being within the predetermined range.

### Claim 9

A method of partitioning a plurality of solid models stored in a knowledge base comprising the steps of:
selecting a set of features for representing a first solid model;
extracting features corresponding to the selected set of features from the first solid model;
constructing an undirected model dependency graph of the first solid model based on the selected set of features;
extracting features corresponding to the selected set of features from each of the plurality of solid models;
constructing an undirected model dependency graph of each of the plurality of solid models based on the selected set of features;
comparing the undirected model dependency graph of the first solid model with the undirected model dependency graph of each of the plurality of solid models;
computing a numerical measure indicative of the similarity of the first solid model to each of the plurality of solid models; and
partitioning the plurality of solid models based on the similarity measure.
