Polygonal Boundary Evaluation of Minkowski Sums and Swept Volumes

Simple item page
dc.contributor.authorMarcel Campenen_US
dc.contributor.authorLeif Kobbelten_US
dc.date.accessioned2015-02-23T17:15:37Z
dc.date.available2015-02-23T17:15:37Z
dc.date.issued2010en_US
dc.description.abstractAbstract We present a novel technique for the efficient boundary evaluation of sweep operations applied to objects in polygonal boundary representation. These sweep operations include Minkowski addition, offsetting, and sweeping along a discrete rigid motion trajectory. Many previous methods focus on the construction of a polygonal superset (containing self-intersections and spurious internal geometry) of the boundary of the volumes which are swept. Only few are able to determine a clean representation of the actual boundary, most of them in a discrete volumetric setting. We unify such superset constructions into a succinct common formulation and present a technique for the robust extraction of a polygonal mesh representing the outer boundary, i.e. it makes no general position assumptions and always yields a manifold, watertight mesh. It is exact for Minkowski sums and approximates swept volumes polygonally. By using plane-based geometry in conjunction with hierarchical arrangement computations we avoid the necessity of arbitrary precision arithmetics and extensive special case handling. By restricting operations to regions containing pieces of the boundary, we significantly enhance the performance of the algorithm.en_US
dc.description.number5en_US
dc.description.seriesinformationComputer Graphics Forumen_US
dc.description.volume29en_US
dc.identifier.doi10.1111/j.1467-8659.2010.01770.xen_US
dc.identifier.pages1613-1622en_US
dc.identifier.urihttps://diglib.eg.org/handle/10.2312/CGF.v29i5pp1613-1622en_US
dc.identifier.urihttps://diglib.eg.org/handle/10.2312/CGF.v29i5pp1613-1622
dc.titlePolygonal Boundary Evaluation of Minkowski Sums and Swept Volumesen_US
Files
Collections
29-Issue 5
SGP10: Eurographics Symposium on Geometry Processing