Algorithm to calculate the Minkowski sums of 3-polytopes based on normal fans

Prompted by the development of algorithms for analysing geometric tolerancing, this article describes a method to determine the Minkowski sum for 3-dimensional polytopes. This method is based exclusively on intersection operations on normal cones, using the properties of the normal fan of a Minkowski sum obtained by common refinement of the normal fans of the operands. It can be used to determine from which vertices of the operands the vertices of the Minkowski sum derive. It is also possible to determine to which facets of the operands each facet of the Minkowski sum is oriented. The basic properties of the algorithms can be applied to n-polytopes.First, the main properties of the duality of normal cones and primal cones associated with the vertices of a polytope are described. Next, the properties of normal fans are applied to define the vertices and facets of the Minkowski sum of two polytopes. An algorithm is proposed, which generalises the method. Lastly, there is a discussion of the features of this algorithm, developed using the OpenCascade environment.     

Configuration products and quotients in geometric modeling

The six-dimensional space SE(3) is traditionally associated with the space of configurations of a rigid solid (a subset of Euclidean three-dimensional space R³). But a solid itself can be also considered to be a set of configurations, and therefore a subset of SE(3). This observation removes the artificial distinction between shapes and their configurations, and allows formulation and solution of a large class of problems in mechanical design and manufacturing. In particular, the configuration product of two subsets of configuration space is the set of all configurations obtained when one of the sets is transformed by all configurations of the other. The usual definitions of various sweeps, Minkowski sum, and other motion related operations are then realized as projections of the configuration product into R³. Similarly, the dual operation of configuration quotient subsumes the more common operations of unsweep and Minkowski difference. We identify the formal properties of these operations that are instrumental in formulating and solving both direct and inverse problems in computer aided design and manufacturing. Finally, we show that all required computations may be approximated using a fast parallel sampling method on a GPU and provide error estimates for the approximation.     

Quantizing gravity using physical states of a superstring

A symmetric zero-mass tensor of rank two is constructed using the superstring modes of excitation, which satisfies the physical state constraints of a superstring. These states have a one to one correspondence with the quantized field operators and are shown to be the absorption and emission quanta of the Minkowski space Lorentz tensor, using the quantum field theory method of quantization. The principle of equivalence makes the tensor identical to the metric tensor at any arbitrary space-time point. The propagator for the quantized field is deduced. The gravitational interaction is switched on by going over from ordinary derivatives to co-derivatives. The Riemann-Christoffel affine connections are calculated, and the weak field Ricci tensor R _μν ⁰ is shown to vanish. The interaction part R _μν ^int is found, and the exact R _μν of the theory of gravity is expressed in terms of the quantized metric. The quantum-mechanical self-energy of the gravitational field in vacuum is shown to vanish. By the use of a projection operator, it is shown that gravitons are quanta of the general relativity field which gives the Einstein equation G _μν = 0. It is suggested that quantum gravity may be renormalizable by the use of the massless ground state of this superstring theory for general relativity, and a tachyonic vacuum creates and annihilates quanta of quantized gravitational field.     

Exact Minkowksi Sums of Polyhedra and Exact and Efficient Decomposition of Polyhedra into Convex Pieces

We present the first exact and robust implementation of the 3D Minkowski sum of two non-convex polyhedra. Our implementation decomposes the two polyhedra into convex pieces, performs pairwise Minkowski sums on the convex pieces, and constructs their union. We achieve exactness and the handling of all degeneracies by building upon 3D Nef polyhedra as provided by Cgal. The implementation also supports open and closed polyhedra. This allows the handling of degenerate scenarios like the tight passage problem in robot motion planning. The bottleneck of our approach is the union step. We address efficiency by optimizing this step by two means: we implement an efficient decomposition that yields a small number of convex pieces, and develop, test and optimize multiple strategies for uniting the partial sums by consecutive binary union operations. The decomposition that we implemented as part of the Minkowski sum is interesting in its own right. It is the first robust implementation of a decomposition of polyhedra into convex pieces that yields at most O(r ²) pieces, where r is the number of edges whose adjacent facets comprise an angle of more than 180 degrees with respect to the interior of the polyhedron. This work was partially supported by the Netherlands’ Organisation for Scientific Research (NWO) under project no. 639.023.301.     

Exact and efficient construction of Minkowski sums of convex polyhedra with applications

We present an exact implementation of an efficient algorithm that computes Minkowski sums of convex polyhedra in R³. Our implementation is complete in the sense that it does not assume general position. Namely, it can handle degenerate input, and it produces exact results. We also present applications of the Minkowski-sum computation to answer collision and proximity queries about the relative placement of two convex polyhedra in R³. The algorithms use a dual representation of convex polyhedra, and their implementation is mainly based on the Arrangement package of Cgal, the Computational Geometry Algorithm Library. We compare our Minkowski-sum construction with the only three other methods that produce exact results we are aware of. One is a simple approach that computes the convex hull of the pairwise sums of vertices of two convex polyhedra. The second is based on Nef polyhedra embedded on the sphere, and the third is an output-sensitive approach based on linear programming. Our method is significantly faster. The results of experimentation with a broad family of convex polyhedra are reported. The relevant programs, source code, data sets, and documentation are available at http://www.cs.tau.ac.il/~efif/CD and a short movie [Fogel E, Halperin D. Video: Exact Minkowski sums of convex polyhedra. In: Proceedings of 21st annual ACM symposium on computational geometry. 2005. p. 382-3] that describes some of the concepts portrayed in this paper can be downloaded from http://www.cs.tau.ac.il/~efif/CD/Mink3d.avi.     

Exact Minkowski Products of N Complex Disks

An exact parameterization for the boundary of the Minkowski product of N circular disks in the complex plane is derived. When N > 2, this boundary curve may be regarded as a generalization of the Cartesian oval that bounds the Minkowski product of two disks. The derivation is based on choosing a system of coordinated polar representations for the N operands, identifying sets of corresponding points with matched logarithmic Gauss map that may contribute to the Minkowski product boundary. By means of inversion in the operand circles, a geometrical characterization for their corresponding points is derived, in terms of intersections with the circles of a special coaxal system. The resulting parameterization is expressed as a product of N terms, each involving the radius of one disk, a single square root, and the sine and cosine of a common angular variable over a prescribed domain. As a special case, the N-th Minkowski power of a single disk is bounded by a higher trochoid. In certain applications, the availability of exact Minkowski products is a useful alternative to the naive bounding approximations that are customarily employed in "complex circular arithmetic."     

Approximate unions of lines and minkowski sums

We study the complexity of, and algorithms to construct, approximations of the union of lines and of the Minkowski sum of two simple polygons. We also studythick unions of lines and Minkowski sums, which are inflated with a small disc. Letb=D/ɛ be the ratio of the diameter of the region of interest and the maximum distance (or error) of the approximation. An approximate union of lines or Minkowski sum has complexity Θ (b ²) in the worst case. The thick union ofn lines has complexity Ω(n+b ²) andO(n +b√bn), and thick Minkowski sums have complexity Ω(n ²+b²) andO((n+b)n√blogn+n ² logn) in the worst case. We present algorithms that run inO(n+n ^2/3+δ b ^4/3 andO(min(bn,n ^4/3+δ b ^2/3)) time (any δ>0) for approximate and thick arrangements. For approximate Minkowski sums, the running time isO(min(b ² n,n ² +b ² + (nb)^4/3+δ); thick Minkowski sums takeO(n ^8/3+δ b ^2/3) time to compute.     

State estimation for Markovian Jump Linear Systems with bounded disturbances

In this paper, we investigate the state estimation problem for a class of Markovian Jump Linear Systems (MJLSs) in the presence of bounded polyhedral disturbances. A set-membership estimation algorithm is first proposed to find the smallest consistent set of all possible states, which is shown to be expressed by a union of multiple polytopes. The posterior probabilities of the system jumping modes are then estimated by introducing the Lebesgue measure, based on which the optimal point estimate is further provided. Moreover, a similarity relationship for polytopes is defined and an approximate method is presented to calculate the Minkowski sum of polytopes, which can help reduce the computational complexity of the overall estimation algorithm.     

Hurwitz testing sets for parallel polytopes of polynomials

In considering robustness of linear systems with uncertain paramenters, one is lead to consider simultaneous stability of families of polynomials. Efficient Hurwitz stability tests for polytopes of polynomials have earlier been developed using evaluations on the imaginary axis. This paper gives a stability criterion for parallel polytopes in terms of Hurwitz stability of a number of corners and edges. The ‘testing set’ of edges and corners depends entirely on the edge directions of the polytope, hence the results are particularly applicable in simultaneous analysis of several polytopes with equal edge directions.It follows as a consequence, that Kharitonov's four polynomial test for independent coefficient uncertainties is replaced by a test of 2q polynomials, when the stability region is a sector Ω = { e^iv | > 0, rπ/q < | v | ≤ π } and r/q is a rational number.     

Voxelized Minkowski sum computation on the GPU with robust culling

We present a new approach for computing the voxelized Minkowski sum (excluding any enclosed voids) of two polyhedral objects using programmable Graphics Processing Units (GPUs). We first cull out surface primitives that will not contribute to the final boundary of the Minkowski sum, analyzing and adaptively bounding the rounding errors of the culling algorithm to solve the floating point error problem. The remaining surface primitives are then rendered to depth textures along six orthogonal directions to generate an initial solid voxelization of the Minkowski sum. Finally we employ fast flood fill to find all the outside voxels. We generate both solid and surface voxelizations of Minkowski sums without enclosed voids and support high volumetric resolution of 1024³ with low video memory cost. The whole algorithm runs on the GPU and is at least one order of magnitude faster than existing boundary representation (B-rep) based algorithms. It avoids the large number of 3D Boolean operations needed in most existing algorithms and is easy to implement. The voxelized Minkowski sums can be used in a variety of applications including motion planning and penetration depth computation.     

From the zonotope construction to the Minkowski addition of convex polytopes

A zonotope is the Minkowski addition of line segments in R^d. The zonotope construction problem is to list all extreme points of a zonotope given by its line segments. By duality, it is equivalent to the arrangement construction problem—that is, to generate all regions of an arrangement of hyperplanes.By replacing line segments with convex V-polytopes, we obtain a natural generalization of the zonotope construction problem: the construction of the Minkowski addition of k polytopes. Gritzmann and Sturmfels studied this general problem in various aspects and presented polynomial algorithms for the problem when one of the parameters k or d is fixed. The main objective of the present work is to introduce an efficient algorithm for variable d and k. Here we call an algorithm efficient or polynomial if it runs in time bounded by a polynomial function of both the input size and the output size. The algorithm is a natural extension of a known algorithm for the zonotope construction, based on linear programming and reverse search. It is compact, highly parallelizable and very easy to implement.This work has been motivated by the use of polyhedral computation for optimal tolerance determination in mechanical engineering.     

Shortest Path Geometric Rounding

Exact implementations of algorithms of computational geometry are subject to exponential growth in running time and space. In particular, coordinate bit-complexity can grow exponentially when algorithms are cascaded : the output of one algorithm becomes the input to the next. Cascading is a significant problem in practice. We propose a geometric rounding technique: shortest path rounding . Shortest path rounding trades accuracy for space and time and eliminates the exponential cost introduced by cascading. It can be applied to all algorithms which operate on planar polygonal regions, for example, set operations, transformations, convex hull, triangulation, and Minkowski sum. Unlike other geometric rounding techniques, shortest path rounding can round vertices to arbitrary lattices, even in polar coordinates, as long as the rounding cells are connected. (Other rounding techniques can only round to the integer grid.) On the integer grid, shortest path rounding introduces less combinatorial change and geometric error than the other rounding methods. Three algorithms are given for shortest path rounding, one of which we have used in industrial application software since 1992. In combination with recent advances in exact floating point evaluation of numerical primitives, shortest path geometric rounding yields a practical solution to numerical issues in computational geometry. Geometric algorithms can be implemented exactly on floating point input coordinates; the exact output coordinates can be rounded to accurate floating point approximations; and the cost of each arithmetic operation is only a little more than if it were implemented as a single hardware floating point operation. Received February 7, 1997; revised September 9, 1998.     

Logical Methods for Studying Relations in Criterial Spaces with Arbitrary Ordinal Scales

Proposed was an approach enabling one to reduce studies of the properties of ordinal relations for criteria with an arbitrary (including finite) set of values to similar problems for relations defined over the entire n-dimensional real space R ⁿ. It enabled one to prove that all main findings, methods, and algorithms obtained previously for the ordinal relations on R ⁿ can be extended in arbitrary criterial spaces to the ordinal relations with the criterion scale cardinalities not less than three.     

Incremental penetration depth estimation between convex polytopes using dual-space expansion

We present a fast algorithm to estimate the penetration depth between convex polytopes in 3D. The algorithm incrementally seeks a "locally optimal solution" by walking on the surface of the Minkowski sums. The surface of the Minkowski sums is computed implicitly by constructing a local dual mapping on the Gauss map. We also present three heuristic techniques that are used to estimate the initial features used by the walking algorithm. We have implemented the algorithm and compared its performance with earlier approaches. In our experiments, the algorithm is able to estimate the penetration depth in about a milli-second on an 1 GHz Pentium PC. Moreover, its performance is almost independent of model complexity in environments with high coherence between successive instances.     

A study of the motion of a relativistic continuous medium

The main purpose of the present paper is to give an exact and correct expression describing the properties of the proper length in arbitrary relativistic translationally moving media in Minkowski space. We show, in particular, that the standard solution of Bell’s well-known problem [1] must be revised. A new solution has been found, describing the behavior of a finite physical length in the Lagrangian non-inertial reference frame comoving to the medium. This solution is absent in the existing literature. We conclude that, in the case of large enough accelerations a ₀ and initial distances between some points of the medium, i.e., under the condition u ≡ a ₀ L ₀/c ² ≫ 1, where c is the speed of light, the calculations presented in some well-known papers (namely, [1, 2, 10–12]) are incorrect and should be revised. For the velocity values u ≪ 1, our results and those of all the enumerated papers coincide.     

Contributing vertices-based Minkowski sum computation of convex polyhedra

Minkowski sum is an important operation. It is used in many domains such as: computer-aided design, robotics, spatial planning, mathematical morphology, and image processing. We propose a novel algorithm, named the Contributing Vertices-based Minkowski Sum (CVMS) algorithm for the computation of the Minkowski sum of convex polyhedra. The CVMS algorithm allows to easily obtain all the facets of the Minkowski sum polyhedron only by examining the contributing vertices—a concept we introduce in this work, for each input facet. We exploit the concept of contributing vertices to propose the Enhanced and Simplified Slope Diagram-based Minkowski Sum (ESSDMS) algorithm, a slope diagram-based Minkowski sum algorithm sharing some common points with the approach proposed by Wu et al. [Wu Y, Shah J, Davidson J. Improvements to algorithms for computing the Minkowski sum of 3-polytopes. Comput Aided Des. 2003; 35(13): 1181-92]. The ESSDMS algorithm does not embed input polyhedra on the unit sphere and does not need to perform stereographic projections. Moreover, the use of contributing vertices brings up more simplifications and improves the overall performance. The implementations for the mentioned algorithms are straightforward, use exact number types, produce exact results, and are based on CGAL, the Computational Geometry Algorithms Library. More examples and results of the CVMS algorithm for several convex polyhedra can be found at http://liris.cnrs.fr/hichem.barki/mksum/CVMS-convex.     

Voronoi diagrams of moving points in the plane and of lines in space: tight bounds for simple configurations

The combinatorial complexities of (1) the Voronoi diagram of moving points in 2D and (2) the Voronoi diagram of lines in 3D, both under the Euclidean metric, continues to challenge geometers because of the open gap between the Ω(n²) lower bound and the O(n3+?) upper bound. Each of these two combinatorial problems has a closely related problem involving Minkowski sums: (1′) the complexity of a Minkowski sum of a planar disk with a set of lines in 3D and (2′) the complexity of a Minkowski sum of a sphere with a set of lines in 3D. These Minkowski sums can be considered “cross-sections” of the corresponding Voronoi diagrams. Of the four complexity problems mentioned, problems (1′) and (2′) have recently been shown to have a nearly tight bound: both complexities are O(n2+?) with lower bound Ω(n²).In this paper, we determine the combinatorial complexities of these four problems for some very simple input configurations. In particular, we study point configurations with just two degrees of freedom (DOFs), exploring both the Voronoi diagrams and the corresponding Minkowski sums. We consider the traditional versions of these problems to have 4 DOFs. We show that even for these simple configurations the combinatorial complexities have upper bounds of either O(n²) or O(n2+?) and lower bounds of Ω(n²).     

2D and 3D Optimal Parallel Image Warping

Spatial image warping is useful for image processing and graphics. In this paper, we present concurrent-read-exclusive-write (CREW) and exclusive-read-exclusive-write (EREW) parallel-random-access-machine (PRAM) algorithms that achieve O(1) asymptotic run time. The significant result is the creative processor assignment that results in an EREW PRAM algorithm. The forward algorithm calculates any nonscaling affine transform including arbitrary skewings, translations, and rotations. The EREW algorithm is the most efficient in practice, and the MasPar MP-1 with 16K processors rotates a 4-million-element image in under a second and a 2-million-element volume in one-half of a second. This high performance allows interactive viewing of volumes from arbitrary viewpoints and illustrates linear speedup. This practical efficiency is analyzed and illustrated by using a bridging model of computation. We develop the mixed cost communication machine (MCCM) to quantify the communication costs and correlate these costs to the MasPar MP-1. The forward algorithm has provable N = 1 congestion on the MCCM, while the backward algorithm has congestion N > 1 which varies with the transform. There are also important quality advantages using our direct warping techniques; empirical measurements are given to provide comparisons to multipass warps.     

Computing global visibility maps for regions on the boundaries of polyhedra using Minkowski sums

A global visibility map is a spherical image built to describe the complete set of global visible view directions for a surface. In this paper, we consider the computation of global visibility maps for regions on the boundary of a polyhedron. Both the self-occlusions introduced by a region and the global occlusions introduced by the rest of the surfaces on the boundary of the polyhedron are considered for computing a global visibility map. We show that the occluded view directions introduced between a pair of polyhedral surfaces can be computed from the spherical projection of the Minkowski sum of one surface and the reflection of the other. A suitable subset of the Minkowski sum, which shares the identical spherical projection with the complete Minkowski sum, is constructed to obtain the spherical images representing global occlusions. Our method has been successfully tested on many CAD models. It extends the previous methods for computing global visibility maps using convex decomposition, and it exhibits a better performance.