Interference detection among solids and surfaces

ABSTRACT

In many industrial environments it is necessary to determine whether there is interference among components. There are many potential interference problems in products made up of assemblies of components and in product manufacturing and testing. Typically, drawings are used in an attempt to detect such unwanted interferences, but the two-dimensional, static drafting medium does not always show interferences among three-dimensional, moving parts. This paper presents a computer representation for solids and surfaces and algorithms which carry out interference checking among objects so represented. Objects are represented as polyhedra or as piecewise planar surfaces. Two types of interference checking are discussed: detection of intersections among objects in fixed positions and detection of collisions among objects moving along specified trajectories.

REFERENCES

• 1: An Introduction to PADL. Production Automation Project, Rep. TM-22, U. of Rochester, Dec. 1974.
• 2: Bruce G. Baumgart, GEOMED - a geometric editor., Stanford University, Stanford, CA, 1974
• 3: Bruce Guenther Baumgart, Geometric modeling for computer vision., 1974
• 4: Baumgart, B.G. A polyhedron representation for computer vision. Nat. Comptr. Conf., 1975, pp. 589-596.
• 5: Braid, 1.C. Designing with Volumes, 2nd ed. Cantab Press, Cambridge, England, 1974.
• 6: I. C. Braid, The synthesis of solids bounded by many faces, Communications of the ACM, v.18 n.4, p.209-216, April 1975 [doi>10.1145/360715.360727]
• 7: Braid, I.C., and Lang, C.A. Computer-aided design of mechanical components with volume building bricks. Proc. 2nd IFIP/IFAC PROLAMAT Conf., North-Holland Pub. Co., Amsterdam, 1973, pp. 173-184.
• 8: Computer Aided Geometric Design. R.E. Barnhill and R.F. Riesenfeld, Eds. Academic Press, 1974.
• 9: Eastman, C., Lividini, J., and Stoker, D. A database for designing large physical systems. Nat. Comptr. Conf. Proc., 1975, pp. 603-61 I.
• 10: Forrest, A.R. Computational geometry--achievements and problems. In Computer Aided Geometric Design, Academic Press, 1974.
• 11: Maruyama, K. A procedure to determine intersections between polyhedral objects. Int. J. of Comptr. and Inform. Sci. 1, 3 (1972), 255-266.
• 12: Pieper, D.L. The kinematics of manipulators under computer control. Ph.D. Th., CS-116, Comptr. Sci. Dept., Stanford U., October, 1968.
• 13: Requicha, A.A.G., and Voelcker, H.B. Constructive solid geometry. Production Automation Project, Report TM-25, U. of Rochester, November 1977.
• 14: Udupa, S. Collision detection and avoidance in computer controlled manipulators. Proc. 5th Int. Joint Conf. Artif. lntel., Cambridge, Mass., 1977, pp. 737-748.
• 15: Voelcker, H.B., et al. Discrete part manufacturing: theory and practice. Production Automation Project, Rep. TR-I-I, U. of Rochester, 1974.
• 16: Voelcker, H.B., and Requicha, A.A.G. Geometric modeling of mechanical parts and processes. Computer 10, 12 (Dec. 1977), 48-57.
• 17: Warn, D.R. VDAM--a virtual data access manager for computer aided design. Proc. Workshop on Data Bases for Interactive Design, Waterloo, 1975, pp. 104-11 I.
• 18: Widdoes, C. A heuristic collision avoider for the Stanford robot arm. Stanford AI Lab, June 1974, unpublished.
• 19: Robin Williams, A Survey of Data Structures for Computer Graphics Systems, ACM Computing Surveys (CSUR), v.3 n.1, p.1-21, March 1971 [doi>10.1145/356583.356584]

INDEX TERMS

Keywords:
collision detection, graphics, interference checking, intersection detection, polygons, polyhedral representation, solid representation, surfaces