Machine interpretation of CAD data for manufacturing applications

ABSTRACT

Machine interpretation of the shape of a component for CAD databases is an important problem in CAD/CAM, computer vision, and intelligent manufacturing. It can be used in CAD/CAM for evaluation of designs, in computer vision for machine recognition and machine inspection of objects, and in intelligent manufacturing for automating and integrating the link between design and manufacturing. This topic has been an active area of research since the late '70s, and a significant number of computational methods have been proposed to identify portions of the geometry of a part having engineering significance (here called “features”). However, each proposed mechanism has been able to solve the problem only for components within a restricted geometric domain (such as polyhedral components), or only for components whose features interact with each other in a restricted manner. The purposes of this article are to review and summarize the development of research on machine recognition of features from CAD data, to discuss the advantages and potential problems of each approach, and to point out some of the promising directions future investigations may take. Since most work in this field has focused on machining features, the article primarily covers those features associated with the manufacturing domain. In order to better understand the state of the art, methods of automated feature recognition are divided into the following categories of methods based on their approach: graph-based, syntactic pattern recognition, rule-based, and volumetric. Within each category we have studied issues such as the definition of features, mechanisms developed for recognition of features, the application scope, and the assumptions made. In addition, the problem is addressed from the perspective of information input requirements and the advantages and disadvantages of boundary representation, constructive solid geometry (CSG), and 2D drawings with respect to machine recognition of features are examined. Emphasis is placed on the mechanisms for attacking problems associated with interacting features.

REFERENCES

• 1: ALDEFELD, B. 1983. On automatic recognition of 3D structure from 2D representations. Comput. Aided Des. 15, 2, 59-64.
• 2: Bruce G. Baumgart, Winged edge polyhedron representation., Stanford University, Stanford, CA, 1972
• 3: BROWN, P. AND RAY, S. 1987. Research issues on process planning at the National Bureau of Standards. In Proceedings of the 19th CIRP International Seminar on Manufacturing Systerns.
• 4: BURN, J.M. 1991. B-Rep to CSG Conversion Tool-Oriented Process Planning. Springer- Verlag.{
• 5: CHAMBERLAIN, M.A., JONEJA, A., AND CHANG, T.- C. 1993. Protrusion-features handling in design and manufacturing planning. Comput. Aided Des. 25, 1, 19-28.
• 6: CHANG, T.C., ANDERSON, D.C., AND MITCHELL, O.R. 1988. QTC--an integrated design/ manufacturing/inspection system for prismatic parts. In Proceedings of ASME Conference on Computers in Engineering (San Francisco, CA), Vol. 1, 417-426.
• 7: CHEN, X. AND HOFFMAN, C.M. 1995. On editability of feature-based design. Comput. Aided Des. 27, 12, 905-914.
• 8: CHIREHDAST, M. AND PAPALAMBROS, P.Y. 1994. Conversion of spatial-enumeration scheme into constructive solid geometry. Comput. Aided Des. 26, 4, 302-314.
• 9: CHOI, B.K. 1982. CAD/CAM compatible tooloriented process planning for machining centers. Ph. D. Thesis, Purdue University.
• 10: CHOI, B.K., BARASH, M.M., AND ANDERSON, D.C. 1984. Automatic recognition of machined surfaces from 3-D solid model. Comput. Aided Des. 16, 2, 81-86.
• 11: S. H. Chuang , M. R. Henderson, Three-dimensional shape pattern recognition using vertex-edge graphs, Computer-Aided Design, v.22 n.6, p.377-387, July/August 1990 [doi>10.1016/0010-4485(90)90088-T]
• 12: CLARK, D.E.R. AND CORNEY, J. 1994. Identification of general protrusion and depression features. In Proceedings of ASME Conference on Computers in Engineering, Vol. 1, 55-65.
• 13: CORNEY, J. AND CLARK, D. E.R. 1991. Method for finding holes and pockets that connect multiple faces in 2 1/2D objects. Comput. Aided Des. 23, 10, 658-668.
• 14: DAVE, P. AND SAKURAI, H. 1995. Maximal volume decomposition and its application to feature recognition. In Proceedings of ASME Conference on Computers in Engineering, 553-568.
• 15: L. de Floriani, Feature Extraction from Boundary Models of Three-Dimensional Objects, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.11 n.8, p.785-798, August 1989 [doi>10.1109/34.31442]
• 16: T. De Martino , B. Falcidieno , F. Giannini, An adaptive feature recognition process for machining contexts, Advances in Engineering Software, v.20 n.2-3, p.91-105, 1994 [doi>10.1016/0965-9978(94)90052-3]
• 17: DE MARTINO, T., FALCIDIENO, B., GIANNINI, F., HAS- SINGER, S., AND OVTCHAROVA, J. 1994b. Feature-based modeling by integrating design and recognition approaches. Comput. Aided Des. 26, 8, 646-653.
• 18: DONG, X. AND WOZNY, M. 1988. FRAFES, a frame-based feature extraction system, In International Conference on Computer Integrated Manufacturing (IEEE, Troy, NY), 296- 305.
• 19: DORI, D. AND TOMBRE, K. 1995. From engineering drawings to 3D CAD models: Are we ready now? Comput. Aided Des. 27, 4, 243-254.
• 20: DUAN, W., ZHOU, J., AND LAI, K. 1993. FSMT: A feature solid-modeling tool for feature-based design and manufacture. Comput. Aided Des. 25, 11, 29-38.
• 21: Bianca Falcidieno , Franca Giannini, Automatic recognition and representation of shape-based features in a geometric modeling system, Computer Vision, Graphics, and Image Processing, v.48 n.1, p.93-123, Oct. 1989 [doi>10.1016/0734-189X(89)90106-0]
• 22: FENG, C.-X. AND KUSIAK, A. 1995. Constraintbased design of parts. Comput. Aided Des. 27, 5, 343-352.
• 23: FIELDS, M. C. AND ANDERSON, D.C. 1994. Fast feature extraction for machining applications. Comput. Aided Des. 26, 11, 803-813.
• 24: FINGER, S. AND SAFIER, S. 1990. Representing and recognizing features in mechanical designs. In Proceedings of Design Theory & Methodology Conference (Chicago, IL), 19-25.
• 25: Fu, K.S. 1982. Syntactic Pattern Recognition and Applications. Prentice-Hall, Englewood Cliffs, NJ.
• 26: GADH, R. AND PRINZ, F.B. 1992. Recognition of geometric forms using the differential depth filter. Comput. Aided Des. 24, 11, 583-599.
• 27: GUPTA, S.K. AND NAU, D.S. 1995. Systematic approach to analyzing the manufacturability of machined parts. Comput. Aided Des. 27, 5, 323-342.
• 28: Satyandra K. Gupta , Thomas R. Kramer , Dana S. Nau , William C. Regli , Guangming Zhang, Building MRSEV models for CAM applications, Advances in Engineering Software, v.20 n.2-3, p.121-139, 1994 [doi>10.1016/0965-9978(94)90054-X]
• 29: HAN, J. H. AND REQUICHA, A. A.G. 1994. Incremental recognition of machining features. In Proceedings of ASME Conference on Computers in Engineering, Vol. 1, 143-149.
• 30: HENDERSON, M.R. 1984. Extraction of feature information from three dimensional CAD data. Ph.D. Thesis, Purdue University.
• 31: HENDERSON, M. R., CHUANG, S. H., AND GAVANKAR, G.P. 1990. Graph-based feature extraction. In Proceedings of NSF Design and Manufacturing Systems Conference (Tempe, AZ), 183-189.
• 32: HUMMEL, K.E. 1989. Coupling rule-based and object oriented programming for the classification of machined features. In Proceedings of ASME Conference on Computers in Engineering, Vol. 1, 409-418.
• 33: HWANG, T.-S. AND ULLMAN, D.G. 1994. Recognize features from freehand sketches. In Proceedings of ASME Conference on Computers in Engineering, Vol. 1, 67-78.
• 34: JAKUBOWSKI, R. 1982. Syntactic characterization of machine-parts shapes. In Cybern. Syst. Int. J. 13, 1-24.
• 35: JI, Q. AND MAREFAT, M. 1995. Extracting and identifying form features: A Bayesian approach. Comput. Aided Des. 27, 6, 435-454.
• 36: 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]
• 37: JUAN-ARINYO, R. AND SOLE, J. 1995. Constructing face-octrees from voxel-based volume representations. Comput. Aided Des. 27, 10, 783- 791.
• 38: Raghu R. Karinthi , Dana Nau, An Algebraic Approach to Feature Interactions, IEEE Transactions on Pattern Analysis and Machine Intelligence, v.14 n.4, p.469-484, April 1992 [doi>10.1109/34.126807]
• 39: Yong Se Kim, Convex decomposition and solid geometric modeling, Stanford University, Stanford, CA, 1990
• 40: KIM, Y.S. 1992. Recognition of form features using convex decomposition. Comput. Aided Des. 24, 9, 461-477.
• 41: KIM, Y.S. 1993. Form feature recognition using convex decomposition. In Proceedings of NSF Design and Manufacturing Systems Conference (Charlotte, NC).
• 42: KIM, Y. S. AND ROE, K.D. 1992. Conversions in form feature recognition using convex decomposition. In Proceedings of ASME Conference on Computers in Engineering, Vol. 1,233-244.
• 43: Heedong Ko , Myon-woong Park, Integration methodology for feature-based modeling and recognition, Advances in Engineering Software, v.20 n.2-3, p.75-89, 1994 [doi>10.1016/0965-9978(94)90051-5]
• 44: Ko, H., PARK, M.-W., KANG, H., SOHN, Y., AND KIM, H.S. 1993. Integration methodology for feature-based modeling and recognition. In Proceedings of ASME Conference on Computers in Engineering, 23-34.
• 45: KUNG, H. 1984. An investigation into development of process plans from solid geometric modeling representation. Ph.D. Thesis, Oklahoma State University.
• 46: KYPRIANOU, L.K. 1980. Shape classification in computer-aided design. Ph. D. Thesis, Cambridge University, U.K.
• 47: LAKKO, T. AND MANTYLA, M. 1993. Feature modeling by incremental feature recognition. Comput. Aided Des. 25, 8, 479-492.
• 48: LEE, Y. C. AND FU, K.S. 1987. Machine understanding of CSG: Extraction and unification of manufacturing features. IEEE Comput. Graph. Appl. 7, 1, 20-23.
• 49: LENTZ, D.H. AND SOWERBY, R. 1993. Feature extraction of concave and convex regions and their intersections. Comput. Aided Des. 25, 7, 421-437.
• 50: LENTZ, D.H. AND SOWERBY, R. 1994. Hole extraction for sheet metal components. Comput. Aided Des. 26, 10, 771-783.
• 51: Pei-Gen Li, Computer-aided design of a microwave amplifier, 1986
• 52: MAREFAT, M. AND KASHYAP, R.L. 1992. Automatic construction of process plan from solid model representations. IEEE Trans. Syst. Man Cyber. 22, 5, 1097-1115.
• 53: 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]
• 54: M. Marefat , S. J. Feghhi , R. L. Kashyap, IDP: automating the CAD/CAM link by reasoning about shape, Proceedings of the sixth conference on Artificial intelligence applications, p.138-145, January 1990, Santa Barbara, California, United States
• 55: Martti Mäntylä , Dana Nau , Jami Shah, Challenges in feature-based manufacturing research, Communications of the ACM, v.39 n.2, p.77-85, Feb. 1996 [doi>10.1145/230798.230808]
• 56: MARKOWSKY, G. AND WESLEY, M.A. 1986. Generation of solid models from two-dimensional and three-dimensional data. In Solid Modeling by Computer: From Theory to Application. Plenum, New York, 23-51.
• 57: MEERAN, S. AND PRATT, M.J. 1993. Automated feature recognition from 2D drawings. Comput. Aided Des. 25, 1, 7-17.
• 58: MENON, S. AND KIM, Y.S. 1994. Handling blending features in form feature recognition using convex decomposition. In Proceedings of ASME Conference on Computers in Engineering, Vol. 1, 79-92.
• 59: NAU, D.S., GUPTA, S.K., KRAMER, T.R., REGLI, W. C., AND ZHANG, G. 1993. Development of machining alternatives based on MRSEVs. In Proceedings of ASME Conference on Computers in Engineering, 47-57.
• 60: Penny Nii, The blackboard model of problem solving, AI Magazine, v.7 n.2, p.38-53, Summer 1986
• 61: OVTCHAROVA, J. AND JASNOCH, U. 1993. Towards a consistency management in a feature-based design. In Proceedings of ASME Conference on Computers in Engineering, 129-143.
• 62: Jivka Ovtcharova , Uwe Jasnoch, Feature-based design and consistency management in CAD applications: a unified approach, Advances in Engineering Software, v.20 n.2-3, p.65-73, 1994 [doi>10.1016/0965-9978(94)90050-7]
• 63: OVTCHAROVA, J., HABINGER, S., VIEIRA, A. S., JAS- NOCH, U., AND RIX, J. 1994. SINFONIA: An open feature-based design module. In Proceedings of ASME Conference on Computers in Engineering, Vol. 1, 29-43.
• 64: PARRY-BARWICK, S. AND BOWYER, A. 1995. Multidimensional set-theoretic feature recognition. Comput. Aided Des. 27, 10, 731-740.
• 65: Judea Pearl, Probabilistic reasoning in intelligent systems: networks of plausible inference, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1988
• 66: PERNG, D.B. 1988. Automatic 3D machining feature extraction from 2D CAD data. Ph. D. Thesis, National Chiao Tung University, Taiwan.
• 67: D.-B. Perng , Z. Chen , R.-K. Li, Automatic 3D machining feature extraction from 3D CSG solid input, Computer-Aided Design, v.22 n.5, p.285-295, June 1990 [doi>10.1016/0010-4485(90)90093-R]
• 68: PETERS, T.J. 1993. Mechanical design heuristics to reduce the combinatorial complexity for feature recognition. Res. Eng. Des. 4, 4, 195- 201.
• 69: D. T. Pham, Artificial Intelligence in Design, Springer-Verlag New York, Inc., Secaucus, NJ, 1991
• 70: PRABHAKAR, S. AND HENDERSON, M.R. 1992. Automatic form-feature recognition using neural-network-based techniques on boundary representations of solid models. Comput. Aided Des. 24, 7, 381-393.
• 71: REGLI, W. C., GUPTA, S. K., AND NAU, D.S. 1994. Feature recognition for manufacturing analysis. In Proceedings of ASME Conference on Computers in Engineering, Vol. 1, 93-104.
• 72: Aristides G. Requicha, Representations for Rigid Solids: Theory, Methods, and Systems, ACM Computing Surveys (CSUR), v.12 n.4, p.437-464, Dec. 1980 [doi>10.1145/356827.356833]
• 73: Aristides A. G. Requicha, Geometric reasoning for intelligent manufacturing, Communications of the ACM, v.39 n.2, p.71-76, Feb. 1996 [doi>10.1145/230798.230807]
• 74: REQUICHA, A.A.G. AND VOELCKER, H.B. 1985. Boolean operations in solid modeling: Boundary evaluation and merging algorithms. Proc. IEEE 73, 1, 30-44.
• 75: ROSEN, D.W. 1993. Feature-based design: 4 hypotheses for future CAD systems. In Proceedings of ASME Conference on Computers in Engineering, 119-128.
• 76: ROSSIGNAC, J.R. AND O'CONNOR, M. 1990. Selective geometric complex: A dimension-independent model for pointsets with internal structures and incomplete boundaries. In Geometric Modeling for Product Engineering, M. Wozny, J.U. Turner, and K. Preiss, eds., North-Holland.
• 77: SAKURAI, H. 1994. Decomposing a delta volume into maximal convex volumes and sequencing them for machining. In Proceedings of ASME Conference on Computers in Engineering, Vol. 1, 135-142.{
• 78: SAKURAI, H. 1995. Volume decomposition and feature recognition: Part 1--polyhedral objects. Comput. Aided Des. 27, 11, 833-843.
• 79: SAKURAI, H. AND CHIN, C.-W. 1993. Defining and recognizing cavity and protrusion by volumes. In Proceedings of ASME Conference on Computers in Engineering, 59-65.
• 80: Hiroshi Sakurai , David C. Gossard, Recognizing Shape Features in Solid Models, IEEE Computer Graphics and Applications, v.10 n.5, p.22-32, September 1990 [doi>10.1109/38.59033]
• 81: Robert Sedgewick, Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 82: SHAPER, G. 1976. A Mathematical Theory of Evidence. Princeton University Press, Princeton, NJ.
• 83: J. J. Shah, Assessment of features technology, Computer-Aided Design, v.23 n.5, p.331-343, June 1991 [doi>10.1016/0010-4485(91)90027-T]
• 84: Jami J. Shah , Jamie J. Shah , Martti Mantyla, Parametric and Feature Based CAD/Cam: Concepts, Techniques, and Applications, John Wiley & Sons, Inc., New York, NY, 1995
• 85: Jami J. Shah , Martti Mantyla , Dana S. Nau, Advances in Feature-Based Manufacturing, Elsevier Science Inc., New York, NY, 1994
• 86: Vadim Shapiro , Donald L. Vossler, Separation for boundary to CSG conversion, ACM Transactions on Graphics (TOG), v.12 n.1, p.35-55, Jan. 1993 [doi>10.1145/169728.169723]
• 87: SHPITALNI, M. AND FISCHER, A. 1994. Separation of disconnected machining regions on the basis of a CSG model. Comput. Aided Des. 26, 1, 46 -58.
• 88: STALEY, S., HENDERSON, M. R., AND ANDERSON, D. C. 1983. Using syntactic pattern recognition to extract feature information from a solid geometric data. Comput. Mech. Eng. 2, 2, 61-66.
• 89: K. Tang , T. Woo, Algorithmic aspects of alternating sum of volumes part 1: data structure and difference operation, Computer-Aided Design, v.23 n.5, p.357-366, June 1991 [doi>10.1016/0010-4485(91)90029-V]
• 90: K. Tang , T. Woo, Algorithmic aspects of alternating sum of volumes. Part 2: Nonvergence and its remedy, Computer-Aided Design, v.23 n.6, p.435-443, July/Aug. 1991 [doi>10.1016/0010-4485(91)90011-K]
• 91: 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]
• 92: TSENG, Y.-J. AND JOSHI, S.B. 1994. Recognizing multiple interpretations of interacting machining features. Comput. Aided Des. 26, 9, 667-688.
• 93: VAGHUL, M. AND DIXON, J.R. 1985. Expert systems in a CAD environment: Injection molding part design as an example. In Proceedings of ASME Conference on Computers in Engineering, Vol. 2, 77-82.
• 94: VAN HOUTEN, F. J. A. M., VAN'T ERVE, A.H., AND JONKERS, F. J. C.M. 1989. PART, a CAPP system with a flexible architecture. In Second CIRP Workshop on CAPP (Hannover).
• 95: Jan Hendrik Vandenbrande , Aristides A. Requicha, Automatic recognition of machinable features in solid models, 1990
• 96: VANDENBRANDE, J. AND REQUICHA, A.A. 1990. Spatial reasoning for automatic recognition of interacting features. In Proceedings of ASME Computers in Engineering Conference, Vol. 1, 251-256.
• 97: 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]
• 98: Pascal Vaxivière , Karl Tombre, Celesstin: CAD Conversion of Mechanical Drawings, Computer, v.25 n.7, p.46-54, July 1992 [doi>10.1109/2.144439]
• 99: WACO, D.L. AND KIM, Y.S. 1993. Considerations in positive to negative conversion for machining features using convex decomposition. In Proceedings of ASME Conference on Computers in Engineering, 35-46.
• 100: WACO, D.L. AND KIM, Y.S. 1994a. Geometric reasoning for machining features using convex decomposition. Comput. Aided Des. 26, 6, 477-489.
• 101: Douglas L. Waco , Yong Se Kim, Handling interacting positive components in machining feature reasoning using convex decomposition, Advances in Engineering Software, v.20 n.2-3, p.107-119, 1994 [doi>10.1016/0965-9978(94)90053-1]
• 102: WANG, E. 1992. Using automatic feature recognition to interface CAD to CAPP. In Proceedings of ASME Conference on Computers in Engineering, Vol. 1, 215-231.
• 103: Woo, T.C. 1982. Feature extraction by volume decomposition. In Proceedings of Conference on CAD/CAM Technology in Mechanical Engineering (MIT, Cambridge, MA), 76-94.
• 104: J. R. Woodwark, Some speculations on feature recognition, Computer-Aided Design, v.20 n.4, p.189-196, May, 1988 [doi>10.1016/0010-4485(88)90276-X]
• 105: Yu, T.-T., CHEN, Y.-M., AND MILLER, R.A. 1992. A framework for sheet metal part design and manufacturing assessment. In Proceedings of ASME Conference on Computers in Engineering, Vol. 1, 53-60.

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Curve, surface, solid, and object representations

Additional Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.1 Applications and Expert Systems
          Subjects: Industrial automation
  I.3 COMPUTER GRAPHICS
      I.3.5 Computational Geometry and Object Modeling
          Subjects: Geometric algorithms, languages, and systems; Boundary representations; Constructive solid geometry (CSG)**
  I.5 PATTERN RECOGNITION
      I.5.1 Models
          Subjects: Geometric
      I.5.2 Design Methodology
          Subjects: Pattern analysis

  J. Computer Applications
  J.2 PHYSICAL SCIENCES AND ENGINEERING
      Subjects: Engineering

General Terms:
Performance, Reliability

Keywords:
artificial intelligence, automated process planning, computer-aided design, computer-integrated manufacturing, feature recognition, flexible automation