Polygonal boundary approximation for a 2D general sweep based on envelope and boolean operations

Abstract

This paper presents an algorithm that approximates (using polygons) the boundary of a general sweep for an arbitrary 2D curved object (possibly with holes). Based on set-theoretic properties of the general sweep, our algorithm generates the polygonal sweep boundary incrementally, where envelope approximations and union operations are repeatedly applied to intermediate boundaries of the sweep and consecutive instances of the moving object at sampled locations of the motion. For approximation, each instance of the object is polygonized along the motion, where the object may experience dynamic shape transformation with topological changes such as creating and/or destroying internal holes. The incremental nature of the proposed algorithm makes the boundary construction of a general sweep useful for applications in interactive shape design, collision detection, and mechanical part design. Our algorithm generates a precise approximation of the boundary of a general sweep with real-time performance in computing unsweeps, Minkowski sums and differences, and constant radius offsets. Some experimental results are also given in this paper.