International Business Machines Corporation

Roger C Evans

Vadakkedathu Thomas Rajan

Jaroslaw R Rossignac

David D Grossman

Peter M Will

George M Koppelman

Michael A O'Connor

John E Griffith

Myron M Kutcher

A method for constructing the Minkowski sum and derivative morphological combinations of arbitray polyhedra uses operations supported in current CAD/CAM systems. The method has application to three-dimensional modeling of very large scale integrated (VLSI) circuits, their design and simulation of fabrication, and to automated mechanical assembly. The method also has application to n-dimensional modeling in robotics as well as other applications of CAD/CAM systems. In one aspect, an exact Minkowski sum of two polyhedra is obtained by a generalization of sweeping a face along an edge. More generally, according to a second aspect, the Minkowski sum of two polyhedra is computed as the union of linear translational sweeps enabled by the first aspect. The method implements techniques and formulas which greatly reduces the overall cost of the computation of Minkowski sums and, in particular, avoids computations involving non-transversal polyhedra. In a third aspect, the method reduces the difficulty of computing the Minkowski sum of a convex polyhedron and a general polyhedron by using simpler surrogate sets for the convex polyhedron.

Construction of Minkowski sums and derivatives morphological

Cumulative translational sweeps are used to shape geometric objects in a computer model, and they permit display of the resulting changes in shape in the object modelled, and control of processes involving the object modelled. If the geometric object is polyhedral, the cumulative translational sweeps, by creating additional facets, effect selective rounding along model edges and around model vertices. This permits computer modelling of the growth of layers, encompassing in addition to flat surface growth, growth with rounding around corners and over obstacles. Such growth occurs in the manufacture of semiconductors. Modelling a change in a solid structure in stages of growth (or shrinking) and of rounding, as might take place during processing of integrated circuits is achieved by controlled sweep sequences that sweep the structure a finite number of times in accordance with a rayset and stipulated parameters of shape, balance, convexity/concavity, degree of faceting, and memory limitation. The cumulative translational sweep (CTS) is applied in combination with Boolean operations to simulate growth and shrinking over the boundary regions of polyhedral models. By creating additional facets, it effects stipulated selective or global rounding effects along model edges and around model vertices. Such sweeps are examined in terms of Minkowski sums--of the geometric objects that are swept, with structuring geometric shapes that are convex polyhedron from the zonotope subclass of the mathematical family of objects known as polytopes.

Shaping geometric objects by cumulative translational sweeps

A method and apparatus for calibrating a robot and using the results of this calibration to compensate for inaccuracies of the robot and also to diagnose robot deterioration. The method includes moving the robot to a set of nominal positions, commanded by the robot controller or measured by position encoders built into the robot, and determining the associated actual positions by measuring the robot position with an independent accurate measuring means or by aligning the robot end effector with an accurate calibration mask. The calibration results are stored and subsequently used to compensate for robot inaccuracy so that the robot moves to the actual desired positions.

Method and apparatus for calibrating a robot to compensate for

Growing community of inventors

Yorktown Heights, NY, United States of America

Roger C Evans