Minkowski sum computation for planar freeform geometric models using G1 -biarc approximation and interior disk culling

Sangjun Han, Seung Hyun Yoon, Myung Soo Kim, Gershon Elber

Research output: Contribution to journalArticlepeer-review

3 Scopus citations

Abstract

We present an efficient algorithm for computing the Minkowski sum of two planar geometric models bounded by B-spline curves. The boundary curves are first approximated by G1-biarc splines within a given error bound ϵ> 0. A superset of Minkowski sum boundary is then generated using the biarc approximations. For non-convex models, the superset contains redundant arcs. An efficient and robust elimination of the redundancies is the main challenge of Minkowski sum computation. For this purpose, we use the Minkowski sum of interior disks of the two input models, which are again disks in the Minkowski sum interior. The majority of redundant arcs are eliminated by testing each against a small number of interior disks selected for efficiency. From the planar arrangement of remaining arcs, we construct the Minkowski sum boundary in a correct topology. We demonstrate a real-time performance and the stability of circle-based Minkowski sum computation using a large set of test data.

Original languageEnglish
Pages (from-to)921-933
Number of pages13
JournalVisual Computer
Volume35
Issue number6-8
DOIs
StatePublished - 1 Jun 2019

Keywords

  • B-spline curves
  • Biarc splines
  • Interior disks
  • Minkowski sum
  • Trimming

Fingerprint

Dive into the research topics of 'Minkowski sum computation for planar freeform geometric models using G1 -biarc approximation and interior disk culling'. Together they form a unique fingerprint.

Cite this