Continuous penetration depth computation for rigid models using dynamic Minkowski sums

We present a novel, real-time algorithm for computing the continuous penetration depth (CPD) between two interpenetrating rigid models bounded by triangle meshes. Our algorithm guarantees gradient continuity for the penetration depth (PD) results, unlike conventional penetration depth (PD) algorithms that may have directional discontinuity due to the Euclidean projection operator involved with PD computation. Moreover, unlike prior CPD algorithms, our algorithm is able to handle an orientation change in the underlying model and deal with a topologically-complicated model with holes. Given two intersecting models, we interpolate tangent planes continuously on the boundary of the Minkowski sums between the models and find the closest point on the boundary using Phong projection. Given the high complexity of computing the Minkowski sums for polygonal models in 3D, our algorithm estimates a solution subspace for CPD and dynamically constructs and updates the Minkowski sums only locally in the subspace. We implemented our algorithm on a standard PC platform and tested its performance in terms of speed and continuity using various benchmarks of complicated rigid models, and demonstrated that our algorithm can compute CPD for general polygonal models consisting of tens of thousands of triangles with a hole in a few milli-seconds while guaranteeing the continuity of PD gradient. Moreover, our algorithm can compute more optimal PD values than a state-of-the-art PD algorithm due to the dynamic Minkowski sum computation.     

Improvements to algorithms for computing the Minkowski sum of 3-polytopes

A Minkowski sum is a geometric operation that is equivalent either to the vector additions of all points in two operands or to the sweeping of one operand around the profile of the other without changing the relative orientation. Applications of Minkowski sums are found in computer graphics, robotics, spatial planning, and CAD. This paper presents two algorithms for computing Minkowski sum of convex polyhedron in three space (3-polytopes). Both algorithms are improvements on current ones found in the literature. One is based on convex hulls and the other on slope diagrams. The original convex hull based Minkowski algorithm is costly, while the original slope diagram based algorithms require the operation of stereographic projection from 3D to 2D for merging the slope diagrams of the two operands. Implementation of stereographic projection is complicated which increases the computation time and reduces the accuracy of the geometric information that is needed for constructing the resultant solid. This paper reports on improvements that have been made to these two algorithms and their implementation. These improvements include using vector operations to find the interrelations between points, arcs and regions on a unit sphere for the slope diagram algorithm, and addition of a pre-sorting procedure before constructing convex hull for convex hull based Minkowski sum algorithm. With these improvements, the computation time and complexity for both algorithms have been reduced significantly, and the computational accuracy of the slope diagram algorithm has been improved. This paper also compares these two algorithms to each other and to their original counterparts. The potential for extending these algorithms to higher dimensions is briefly discussed.     

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.     

Minkowski sums of point sets defined by inequalities

The existing approaches support Minkowski sums for the boundary, set-theoretic, and ray representations of solids. In this paper, we consider the Minkowski sum operation in the context of geometric modeling using real functions. The problem is to find a real function f₃(X) for the Minkowski sum of two objects defined by the inequalities f₁(X) ≥ 0 and f₂(X) ≥ 0. We represent the Minkowski sum as a composition of other operations: the Cartesian product, resulting in a higher-dimensional object, and a mapping to the original space. The Cartesian product is realized as an intersection in the higher-dimensional space, using an R-function. The mapping projects the resulting object along n coordinate axes, where n is the dimension of the original space. We discuss the properties of the resulting function and the problems of analytic and numeric implementation, especially for the projection operation. Finally, we apply Minkowski sums to implement offsetting and metamorphosis between set-theoretic solids with curvilinear boundaries.     

Fast and reliable collision culling using graphics hardware

We present a reliable culling algorithm that enables fast and accurate collision detection between triangulated models in a complex environment. Our algorithm performs fast visibility queries on the GPUs for eliminating a subset of primitives that are not in close proximity. In order to overcome the accuracy problems caused by the limited viewport resolution, we compute the Minkowski sum of each primitive with a sphere and perform reliable 2.5D overlap tests between the primitives. We are able to achieve more effective collision culling as compared to prior object-space culling algorithms. We integrate our culling algorithm with CULLIDE and use it to perform reliable GPU-based collision queries at interactive rates on all types of models, including nonmanifold geometry, deformable models, and breaking objects.     

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.     

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.     

Fast and robust retrieval of Minkowski sums of rotating convex polyhedra in 3-space

We present a novel method for fast retrieval of exact Minkowski sums of pairs of convex polytopes in R³, where one of the polytopes frequently rotates. The algorithm is based on pre-computing a so-called criticality map, which records the changes in the underlying graph structure of the Minkowski sum of the two polytopes, while one of them rotates. We give tight combinatorial bounds on the complexity of the criticality map when the rotating polytope rotates about one, two, or three axes. The criticality map can be rather large already for rotations about one axis, even for summand polytopes with a moderate number of vertices each. We therefore focus on the restricted case of rotations about a single, though arbitrary, axis.Our work targets applications that require exact collision detection such as motion planning with narrow corridors and assembly maintenance where high accuracy is required. Our implementation handles all degeneracies and produces exact results. It efficiently handles the algebra of exact rotations about an arbitrary axis in R³, and it well balances between preprocessing time and space on the one hand, and query time on the other.We use Cgal arrangements and in particular the support for spherical Gaussian maps to efficiently compute the exact Minkowski sum of two polytopes. We conducted several experiments (i) to verify the correctness of the algorithm and its implementation, and (ii) to compare its efficiency with an alternative (static) exact method. The results are reported.     

Controlled linear perturbation

We present an algorithmic solution to the robustness problem in computational geometry, called controlled linear perturbation, and demonstrate it on Minkowski sums of polyhedra. The robustness problem is how to implement real RAM algorithms accurately and efficiently using computer arithmetic. Approximate computation in floating point arithmetic is efficient but can assign incorrect signs to geometric predicates, which can cause combinatorial errors in the algorithm output. We make approximate computation accurate by performing small input perturbations, which we compute using differential calculus. This strategy supports fast, accurate Minkowski sum computation. The only prior robust implementation uses a less efficient algorithm, requires exact algebraic computation, and is far slower based on our extensive testing.     

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²).     

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.     

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.     

Map segmentation for geospatial data mining through generalized higher-order Voronoi diagrams with sequential scan algorithms

Segmentation is one popular method for geospatial data mining. We propose efficient and effective sequential-scan algorithms for higher-order Voronoi diagram districting. We extend the distance transform algorithm to include complex primitives (point, line, and area), Minkowski metrics, different weights and obstacles for higher-order Voronoi diagrams. The algorithm implementation is explained along with efficiencies and error. Finally, a case study based on trade area modeling is described to demonstrate the advantages of our proposed algorithms.     

Minkowski sum boundary surfaces of 3D-objects

Given two objects A and B with piecewise smooth boundary we discuss the computation of the boundary Γ of the Minkowski sum A + B. This boundary surface Γ is part of the envelope when B is moved by translations defined by vectors a  A, or vice versa. We present an efficient algorithm working for dense point clouds or for triangular meshes. Besides this the global self-intersections of the boundary Γ are detected and resolved. Additionally we point to some relations between Minkowski sums and kinematics, and compute local quadratic approximations of the envelope.     

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.     

Geographic knowledge discovery from Web Map segmentation through generalized Voronoi diagrams

Web maps have become an important decision making tool for our daily lives. We propose a flexible Web Map segmentation method in order to better use them for decision makings. We extend the distance transform algorithm to include complex primitives (point, line and area), Minkowski metrics, different weights and obstacles. The algorithms and proof are explained thoroughly and illustrated. Efficiency and error for the novel algorithms are also detailed. Finally, the usefulness of the algorithms is demonstrated through a series of real-life case studies.     

Interactive vizualization of constructive solid geometry scenes on graphic processors

A ray-tracing algorithm for interactive visualization of very large and structurally complicated scenes presented in the constructive solid geometry (CSG) form is suggested. The algorithm is capable of visualizing such scenes in real time by using a graphic processor. As primitives, classical shapes and objects represented in an analytical form (in particular, second-order surfaces and implicit functions) are used. Unlike other similar algorithms, our algorithm produces the final image in a single pass and has no constraints on the maximum number of primitives and on the CSG tree depth. The key feature of the algorithm is a method for optimizing CSG models, which converts the input tree to an equivalent spatially coherent and well-balanced form (a completely balanced equivalent tree may not exist). The performance of visualization after applying the optimization technique is shown to depend on only the computational resource of the GPU (in contrast to multi-pass algorithms whose performance is restricted by memory capacity). It has been shown experimentally that our algorithm is capable of rendering CSG models consisting of more than a million CSG primitives with the tree depth up to 24.     

Computing the Minkowski sum of ruled surfaces

The boundary of the Minkowski sum of two geometric objects is part of the so-called convolution surface of the boundary surfaces of the two input objects. In most cases, convolution surfaces can be computed only by numerical algorithms. The present paper studies convolution surfaces of ruled surfaces. There, explicit parameterizations for the convolution surface can be derived. Moreover, we study the rational convolution surface of two rational ruled surfaces and the connection to rational parameterizations of offsets of rational ruled surfaces.