Given two planar curves, their convolution curve is defined as the set
of all vector sums generated by all pairs of curve points which have
the same curve normal direction. The Minkowski sum of two planar objec
ts is closely related to the convolution curve of the two object bound
ary curves. That is, the convolution curve is a superset of the Minkow
ski sum boundary. By eliminating all redundant parts in the convolutio
n curve, one can generate the Minkowski sum boundary. The Minkowski su
m can be used in various important geometric computations, especially
for collision detection among planar curved objects. Unfortunately, th
e convolution curve of two rational curves is not rational, in general
. Therefore, in practice, one needs to approximate the convolution cur
ves with polynomial/rational curves. Conventional approximation method
s of convolution curves typically use piecewise linear approximations,
which is not acceptable in many CAD systems due to data proliferation
. In this paper, we generalize conventional approximation techniques o
f offset curves and develop several new methods for approximating conv
olution curves. Moreover, we introduce efficient methods to estimate t
he error in convolution curve approximation. This paper also discusses
various other important issues in the boundary construction of the Mi
nkowski sum. (C) 1998 Academic Press.