Minkowski Sums: A Simulation Tool for CAD/CAM

Abstract

Abstract In this paper we provide a survey of Minkowski sums, their applications as a simulation tool in Computer Aided Design and some simple algorithms to compute them. The intent of the paper is to exhibit the relevance of morphological operations, like Minkowski sums, in practical aspects of CAD/CAM and to provide enough motivation to stimulate research in finding efficient algorithms for their computation. Except for cases where the two initial objects are convex, there are no known algorithms which guarantee efficient performance in the polyhedral domain. Some initial work has been done for finding algorithms where the boundaries of the objects are composed of algebraic curves, but again very little is known on how to actually compute the Minkowski sum for objects bounded by general curves. Some of the applications that we describe in this paper include Robot path planning, interference detection, NC cutter path planning, rounding and filleting, shape design, etching and deposition processes in semiconductor process simulation and polyhedral interpolation.