Browsing by Author "Kim, Myung-Soo"

Now showing 1 - 2 of 2
  • Thumbnail Image
    Item
    Efficient Minimum Distance Computation for Solids of Revolution
    (The Eurographics Association and John Wiley & Sons Ltd., 2020) Son, Sang-Hyun; Yoon, Seung-Hyun; Kim, Myung-Soo; Elber, Gershon; Panozzo, Daniele and Assarsson, Ulf
    We present a highly efficient algorithm for computing the minimum distance between two solids of revolution, each of which is defined by a planar cross-section region and a rotation axis. The boundary profile curve for the cross-section is first approximated by a bounding volume hierarchy (BVH) of fat arcs. By rotating the fat arcs around the axis, we generate the BVH of fat tori that bounds the surface of revolution. The minimum distance between two solids of revolution is then computed very efficiently using the distance between fat tori, which can be boiled down to the minimum distance computation for circles in the three-dimensional space. Our circle-based approach to the solids of revolution has distinctive features of geometric simplification. The main advantage is in the effectiveness of our approach in handling the complex cases where the minimum distance is obtained in non-convex regions of the solids under consideration. Though we are dealing with a geometric problem for solids, the algorithm actually works in a computational style similar to that of handling planar curves. Compared with conventional BVH-based methods, our algorithm demonstrates outperformance in computing speed, often 10-100 times faster. Moreover, the minimum distance can be computed very efficiently for the solids of revolution under deformation, where the dynamic reconstruction of fat arcs dominates the overall computation time and takes a few milliseconds.
  • Thumbnail Image
    Item
    Maximum-Clearance Planar Motion Planning Based on Recent Developments in Computing Minkowski Sums and Voronoi Diagrams
    (The Eurographics Association, 2021) Jung, Mingyu; Kim, Myung-Soo; Lee, Sung-Hee and Zollmann, Stefanie and Okabe, Makoto and Wünsche, Burkhard
    We present a maximum-clearance motion planning algorithm for planar geometric models with three degrees of freedom (translation and rotation). This work is based on recent developments in real-time algorithms for computing the Minkowski sums and Voronoi diagrams of planar geometric models bounded by G1-continuous sequences of circular arcs. Compared with their counterparts using polygons with no G1-continuity at vertices, the circle-based approach greatly simplifies the Voronoi structure of the collision-free space for the motion planning in a plane with three degrees of freedom. We demonstrate the effectiveness of the proposed approach by test sets of maximum-clearance motion planning through narrow passages in a plane.