Octree based assembly sequence generation

ABSTRACT

This paper describes a system for the automatic recognition of assembly features and the generation of assembly/disassembly sequences. The paper starts by reviewing the nature and use of assembly features. One of the conclusions drawn from this survey is that the majority of assembly features involve sets of spatially adjacent faces. Two principle types of adjacency relationships are identified and an algorithm is presented for identifying assembly features which arise from “spatial” and “contact” face adjacency relationships (known as s-adjacency and c-adjacency respectively).

The algorithm uses an octree representation of a B-rep model to support the geometric reasoning required to locate assembly features on disjoint bodies. A pointerless octree representation is generated by recursively sub-dividing the assembly model's bounding box into octants which are used to locate:

• Those portions of faces which are c-adjacent (i.e. they effectively touch within the tolerance of the octree).

• Those portions of faces which are s-adjacent to a nominated face.

The resulting system can locate and partition spatially adjacent faces in a wide range of situations and a different resolutions. The assembly features located are recorded as attributes in the B-rep model and are then used to generate a disassembly sequence plan for the assembly. This sequence plan is represented by a transition state tree which incorporates knowledge of the availability of feasible gripping features.

By way of illustration, the algorithm is applied to several trial components

REFERENCES

• 1: Anantha, R., Kramer, G.A. and Crawford, R.H. Assembly modelling by geometric constraint satisfaction, Computer- Aided Design, Vol. 28, No. 9, 1996, 707-722.
• 2: Winfried van Holland , Willem F. Bronsvoort, Assembly features and sequence planning, Proceedings of the fifth IFIP TC5/WG5.2 international workshop on geometric modeling in computer aided design on Product modeling for computer integrated design and manufacture, p.275-284, January 1997, Airlie, Virginia, United States
• 3: Bronsvoort, W.F., and van Holland, W. Extracting grip areas from feature information, CD-ROM Proceedings of the ASME 1996 Design Engineering Technical Conferences and Computers in Engineering Conference, 19-22 August, Irvine, USA, McCarthy J.M. (ed), ASME, New York, 1996b.
• 4: Winfried van Holland , Willem F. Bronsvoort , Frederik W. Jansen, Feature Modelling for Assembly, Graphics and Robotics, p.131-148, April 19-22, 1993
• 5: Chen, S.F., and Liu, Y.L. A multi-level genetic assembly planner, CD-ROM Proceedings of the ASME 2000 Design Engineering Technical Conferences and Computers and Information in Engineering Conference, 10-13 September, ASME, New York.
• 6: De Fazio, T. L., and Whitney, D. E. Simplified generation of all mechanical assembly sequences, IEEE Journal of Robotics and Automation, RA-3, No. 6, 1987.
• 7: Deneux, D. Introduction to assembly features: an illustrated synthesis methodology, Journal of Intelligent Manufacturing, Vol. 10, 1999, 29-39.
• 8: Gui, J. K., and Mantyla, M. Functional understanding of assembly modelling, Computer-Aided Design, Vol. 26, No. 6, 1994, 435-451.
• 9: Henson, B. W., and Juster, N. P. Information requirements for the support of assembly mating conditions, Proc DECT, ASME Design Engineering Technical Conferences, 1997.
• 10: Homen De Mello, L.S., and Sanderson, A.S. A correct and complete algorithm for the generation of mechanical assembly sequences, IEEE Transactions on Robotics and Automation, Vol. 7, No 2, 1991, 228-240.
• 11: Homen De Mello, L.S., and Sanderson, A.S. AND/OR graph representation of assembly plans, IEEE Transactions on Robotics and Automation, Vol. 6, No 2, 1990, 188-199.
• 12: Huang, C.T. The disassembly matrix for computer-aided disassembly, CD-ROM Proceedings of the ASME 2000 Design Engineering Technical Conferences and Computers and Information in Engineering Conference, 10-13 September, ASME, New York.
• 13: Kunwoo Lee , David C. Gossard, A hierarchical data structure for representing assemblies: part I, Computer-Aided Design, v.17 n.1, p.15-19, Jan./Feb. 1985 [doi>10.1016/0010-4485(85)90005-3]
• 14: Mullins, S. H., and Anderson, D. C. Automatic identification of geometric constraints in mechanical assemblies, Computer-Aided Design, Vol. 30, No. 9, 1998, pp 715-726.
• 15: Prabhakar, S. An experiment on the use of neural nets in form feature recognition, M.S, Arizona State University, 1990.
• 16: Hanan Samet, Neighbor finding in images represented by octrees, Computer Vision, Graphics, and Image Processing, v.46 n.3, p.367-307, June 1989 [doi>10.1016/0734-189X(89)90038-8]
• 17: Shah, J. J., and Rogers, M. T. Assembly modelling as an extension of feature-based desigu, Res. Engng Des. 5, 1993, 218-237.
• 18: Sung, R. C. W., Comey, J. R., and Clark, D. E. R, Octree based recognition of assembly features, CD-ROM Proceedings of the ASME 2000 Design Engineering Technical Conferences and Computers and Information in Engineering Conference, 10-13 September, ASME, New York.
• 19: Van Holland, W. Assembly Features in Modelling and Planning", Ph.D Thesis, Delft University of Technology, Holland, 1997.
• 20: Randall H. Wilson , Jean-Claude Latombe, Geometric reasoning about mechanical assembly, Artificial Intelligence, v.71 n.2, p.371-396, Dec. 1994 [doi>10.1016/0004-3702(94)90048-5]

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.4 IMAGE PROCESSING AND COMPUTER VISION
      I.4.6 Segmentation
          Subjects: Edge and feature detection
  I.5 PATTERN RECOGNITION
      I.5.2 Design Methodology
          Subjects: Feature evaluation and selection

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
assembly features, assembly planning, feature recognition, geometric modelling, octree representation