Using subgraph isomorphisms to recognize and decompose boundary representation features

S. H F Chuang, Mark Henderson

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


A method using subgraph isomorphisms is presented for both computer recognition of shape features and feature-based decomposition of a solid from a boundary representation (B-rep). Prior to the recognition process, the face-edge graph of an object is extracted from a B-rep and is labeled by shape elements as a shape graph, which is an abridged B-rep input to the recognition system. A feature is defined by a user as a feature graph, which is conceptualized from a regional surface shape on a valid solid. Feature recognition is achieved by finding a subgraph from the shape graph of a designed object where the subgraph is isomorphic to a feature graph. Because of the high complexity in subgraph matching, a node classification algorithm is used to reduce the search space. Through this recognition process, the surface of a solid can be decomposed into a collection of features according to a library of feature graphs. The feature relationships are represented in a relationship graph considering the features as nodes and their relationships as arcs. This research shows that the definition of features can be user-definable and consist of valid boundary representation elements in the solid world, and that a heuristically fast algorithm can increase the possibility to recognize features in a reasonable time.

Original languageEnglish (US)
Pages (from-to)793-800
Number of pages8
JournalJournal of Mechanical Design, Transactions of the ASME
Issue number3
StatePublished - Sep 1994

ASJC Scopus subject areas

  • Mechanics of Materials
  • Mechanical Engineering
  • Computer Science Applications
  • Computer Graphics and Computer-Aided Design


Dive into the research topics of 'Using subgraph isomorphisms to recognize and decompose boundary representation features'. Together they form a unique fingerprint.

Cite this