A graph-based framework for feature recognition

ABSTRACT

This paper discusses a feature recognition system for recognizing User Defined Features (UDF). The feature recognizer uses a graph-based approach to represent and recognize features. An attributed face adjacency graph consisting of topological and geometric attributes is used to represent UDF's. The feature recognition step involves finding similar subgraphs in the part graph. The novelty of the framework lies in the usage of a rich set of attributes to recognize a wide range of features efficiently. A unique representation using graph grammars has also been developed to define family of features such as pockets with variable number of side faces. The feature recognizer also addresses many kinds of feature interactions by progressive suppression of the identified features. New techniques have been implemented for suppressing degenerate or virtual features. The feature recognizer also consists of a parameterization module to extract user-defined parameters from the recognized features.

REFERENCES

• 1: Jami J. Shah , Martti Mantyla , Dana S. Nau, Advances in Feature-Based Manufacturing, Elsevier Science Inc., New York, NY, 1994
• 2: Tseng, Y. J. and Joshi, S. B., Recognizing multiple interpretations of interacting machining features. Computer Aided Design, 1994. Vol. 26(9), 667-688.
• 3: S. Joshi , T. C. Chang, Graph-based heuristics for recognition of machined features from a 3D solid model, Computer-Aided Design, v.20 n.2, p.58-66, March, 1988 [doi>10.1016/0010-4485(88)90050-4]
• 4: Narayan, S. V. and Ling, Z. K., Heuristics based feature recognition: a graph approach. Advances in Design Automation. 1994, Vol. 1,299-306.
• 5: Gao S., and Shah J. J., Automatic recognition of interacting machining features based on minimal condition subgraph. Computer Aided I)esign, 1998. Vol. 30(9), 727-739,
• 6: J. H. Vandenbrande , A. A. G. Requicha, Spatial Reasoning for the Automatic Recognition of Machinable Features in Solid Models, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.15 n.12, p.1269-1285, December 1993 [doi>10.1109/34.250845]
• 7: Nalluri Rao SRP, Fornl feature generation model for feature technology, PhD thesis, Department of Mechaniczd Engineering, Indian Institute of Science, Bangalore, India, 1994.
• 8: Regli W, C., Gupta S. R., and Nau D. S., Feature Recognition fbr manttfhcturability analysis. ASME International Computers on Engineering Conference, Minneapolis, 1994.
• 9: M. Marefat , R. L. Kashyap, Geometric Reasoning for Recognition of Three-Dimensional Object Features, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.12 n.10, p.949-965, October 1990 [doi>10.1109/34.58868]
• 10: S. N. Trika , R. L. Kashyap, Geometric Reasoning for Extraction of Manufacturing Features in Iso-Oriented Polyhedrons, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.16 n.11, p.1087-1100, November 1994 [doi>10.1109/34.334388]
• 11: Sashikumar Venkataraman , Milind Sohoni , Gershon Elber, Blend recognition algorithm and applications, Proceedings of the sixth ACM symposium on Solid modeling and applications, p.99-108, May 2001, Ann Arbor, Michigan, United States [doi>10.1145/376957.376970]
• 12: ACIS Geometric Modeller, Format Manual. Version 6.0, Spatial Technologies, (www,spatial.com) .lune 2000.
• 13: Parasolid, Functional Description Manual, Version 11, Unigraphics Solutions, (www.parasolid.com) May 2000.
• 14: Tecnomatix PART, Tecnomatix Technologies Ltd.. www.tecllomatix.corrl.
• 15: Little G., Tuttle R., Clerk D.E.R., Corney L, The Heriot-Watt feature finder: A Graph-Based Approach to Recognition. Proceedings of DETC97. ASME Design Eilgg. Coference, Sept 1997.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.2 Grammars and Other Rewriting Systems
          Subjects: Grammar types (e.g., context-free, context-sensitive)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Boundary representations
  I.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Edge and feature detection
      I.4.7 Feature Measurement
          Subjects: Feature representation

General Terms:
Algorithms, Design, Languages, Performance, Theory

Keywords:
attributed graphs, boundary representation, design tree, feature interactions, feature parameterization, feature suppression, feature-based design, graph grammars, user-defined features