Computing the Minkowski sum of two polyhedra exactly has been shown difficult. Despite its fundamental role in many geometric problems in robotics, to the best of our knowledge, no 3-d Minkowski sum software for general polyhedra is available to the public. One of the main reasons is the difficulty of implementing the existing methods. There are two main approaches for computing Minkowski sums: divide-and-conquer and convolution. The first approach decomposes the input polyhedra into convex pieces, computes the Minkowski sums between a pair of convex pieces, and unites all the pairwise Minkowski sums. Although conceptually simple, the major problems of this approach include: (1) The size of the decomposition and the pairwise Minkowski sums can be extremely large and (2) robustly computing the union of a large number of components can be very tricky. On the other hand, convolving two polyhedra can be done more efficiently. The resulting convolution is a superset of the Minkowski sum boundary. For non-convex inputs, filtering or trimming is needed. This usually involves computing (1) the arrangement of the convolution and its substructures and (2) the winding numbers for the arrangement subdivisions. Both computations are difficult to implement robustly in 3-d. In this paper we present a new approach that is simple to implement and can efficiently generate accurate Minkowski sum boundary. Our method is convolution based but it avoids computing the 3-d arrangement and the winding numbers. The premise of our method is to reduce the trimming problem to the problems of computing 2-d arrangements and collision detection, which are much better understood in the literature. To maintain the simplicity, we intentionally sacrifice the exactness. While our method generates exact solutions in most cases, it does not produce low dimensional boundaries, e.g., boundaries enclosing zero volume. We classify our method as 'nearly exact' to distinguish it from the exact and approximate methods.
展开▼
机译：计算两种多面体的Minkowski总和恰恰难以显示。尽管在机器人中的许多几何问题中，据我们所知，尽管我们所知，但公众可以获得一般多面体的3-D Minkowski Sum Sumply。其中一个主要原因是实现现有方法的难度。计算Minkowski Sum有两种主要方法：划分和征服和卷积。第一方法将输入的多面体分解成凸片，计算一对凸片之间的Minkowski和，并将所有成对Minkowski和汇总。虽然概念性简单，这种方法的主要问题包括：（1）分解的大小和成对Minkowski Sums可以非常大，并且（2）强大地计算大量组件的结合可以非常棘手。另一方面，可以更有效地完成卷积两个多面体。由此产生的卷积是Minkowski Sum边界的超集。对于非凸输入，需要过滤或修剪。这通常涉及计算（1）卷积的布置及其子结构的布置和（2）排列细分的绕组数。两个计算难以在3-D中强大地实施。在本文中，我们提出了一种简单实现的新方法，可以有效地生成准确的Minkowski和边界。我们的方法是基于卷积，但它避免了计算3-D布置和绕组数。我们的方法的前提是减少对计算2-D布置和碰撞检测的问题的修剪问题，这在文献中更好地理解。为了保持简单性，我们故意牺牲精确性。虽然我们的方法在大多数情况下生成精确的解决方案，但它不会产生低维边界，例如封闭零卷的边界。我们将方法分类为“几乎精确”，以区别于精确和近似的方法。
展开▼
