|
Published Articles >> Table of Contents >> Abstract
Computer Graphics and Applications, 12th Pacific Conference on (PG'04)
pp. 392-401
Accurate Minkowski Sum Approximation of Polyhedral Models
Gokul Varadhan, University of North Carolina at Chapel Hill
Dinesh Manocha, University of North Carolina at Chapel Hill
Full Article Text:
  
DOI Bookmark: http://doi.ieeecomputersociety.org/10.1109/PCCGA.2004.1348370
Send link to a friend
| Abstract |
|
We present an algorithm to approximate the 3D Minkowski sum of polyhedral objects. Our algorithm decomposes the polyhedral objects into convex pieces, generates pairwise convex Minkowski sums and computes their union. We approximate the union by generating a voxel grid, computing signed distance on the grid points and performing isosurface extraction from the distance field. The accuracy of the algorithm is mainly governed by the resolution of the underlying volumetric grid. Insufficient resolution can result in unwanted handles or disconnected components in the approximation. We use an adaptive sub-division algorithm that overcomes these problems by generating a volumetric grid at an appropriate resolution. We guarantee that our approximation has the same topology as the exact Minkowski sum. We also provide a two-sided Hausdorff distance bound on the approximation. Our algorithm is relatively simple to implement and works well on complex models. We have used it for exact 3D translation motion planning, offset computation, mathematical morphological operations and bounded-error penetration depth estimation.
|
 Additional Information
|
Citation:
Gokul Varadhan, Dinesh Manocha,
"Accurate Minkowski Sum Approximation of Polyhedral Models,"
pg,
pp. 392-401,
Computer Graphics and Applications, 12th Pacific Conference on (PG'04),
2004
|
|
