A UNIFIED COMPUTATIONAL FRAMEWORK FOR MINKOWSKI OPERATIONS

In this paper we present a complete computational theory of Minkowski addition and Minkowski decomposition of boundary-represented objects. The theory can be summarized as a unified algorithm to compute Minkowski operations of 2D and 3D continuous objects. We unify the two Minkowski operations as a single operation by introducing the notion of negative shape; in contrast to that, the shapes of ordinary objects may be considered positive. More interestingly, the concept of negative shape makes possible further unification since exactly the same computational technique works for convex as well as nonconvex objects. This happens because conceptually a convex object can be viewed as a pure object-either completely positive or completely negative, while a nonconvex object is like a mixture of positive and negative ones. To make the unified algorithm conceptually simpler and computationally more efficient, we devise a new representation scheme, called the slope diagram representation, to represent the input polygons and polyhedra. The slope diagram representation also allows us to provide a nice geometric interpretation of negative shape. Finally, we take up various special cases to show how the unified algorithm can be quickly simplified when the input objects are endowed with more structure (such as, the objects are all convex, or, the boundaries of the objects can be expressed as smooth analytic functions, etc.).