Construction of Minkowski sums and derivatives morphological com

Details Construction of Minkowski sums and derivatives morphological com Construction of Minkowski sums and derivatives morphological com

1991-07-05

1992-10-27

Harkcom, Gary V.

395133, 395141, G06F 562

Patent

active

051595125

ABSTRACT:
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.

REFERENCES:
patent: 3987412 (1976-10-01), Morrin
patent: 3990044 (1976-11-01), Fahey et al.
patent: 4736306 (1988-04-01), Christensen et al.
patent: 4785399 (1988-11-01), Evans et al.
A Mathematical Model for Shape Description Using Minkowski Operators, Computer Vision G raphics and Image Processing, vol. 44, No. 3, Dec. 1988, New York, US, pp. 239-243, 247-269.
J. Serra, "Introduction to Mathematical Morphology," (1986) Computer Vision, Graphics, and Image Processing, 35, pp. 283-305.
J. Serra, (1982) Image Analysis and Mathematical Morphology, Academia Press, pp. 47-48.
T. Lozano-Perez et al., "An Algorithm for Planning Collision-Free Paths Among Polyhedral Obstacles," (1979), Comm. ACM, 22, pp. 560-570.
J. Rossignac et al., "Offsetting Operations in Solid Modelling," (1986), Computer Aided Geom. Design, 3, pp. 129-148.
J. R. Rossignac, "Blending and Offsetting Solid Models," (1985), TM 54 Production Automation Project, Univ. of Rochester.
R. T. Farouki, "The Approximation of Non-Degenerate Offset Surfaces," (1985), Computer Aided Geom. Design, 3, pp. 15-43.
R. C. Evans et al., "Shaping Geom. Objects by Cumulative Translational Sweeps," (1987) IBM J. Res. Develop., 31, pp. 343-360.
G. M. Koppelman et al. "OYSTER: A Study of Integrated Circuits in Three-Dimensional Structures," (1983) IBM J. Res & Dev, 27, pp. 149-163.
M. A. Wesley et al., "A Geometric Modeling System for Automated Mechanical Assembly," (1980) IBM J Res & Dev, 24, No. 1, pp. 64-74.
R. N. Wolfe et al., "Solid Modeling for Production Design" (1987) IBM J. Res. & Dev., 31, No. 3, pp. 277-294.
R. T. Farouki, "Exact Offset Procedures for Simple Solids" (1985) Computer Aided Geometric Design 2, pp. 257-279.

Affiliated with

Also associated with

Rating

Construction of Minkowski sums and derivatives morphological com does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Construction of Minkowski sums and derivatives morphological com, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Construction of Minkowski sums and derivatives morphological com will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-910400