Evaluating the boundary and covering degree of planar Minkowski sums and other geometrical convolutions. (English) Zbl 1140.65020

Farouki, Rida T.; Hass, Joel

J. Comput. Appl. Math. 209, No. 2, 246-266 (2007).

Minkowski sums and specific types of geometrical convolution are heavily used in computer-aided geometric, image processing, computer graphics and animation, path planning for robots and so forth.
The paper presents a new approach based on topological arguments to compute Minkowski sums \(\mathcal{A}\bigoplus \mathcal{B}= \{\mathbf{a}+\mathbf{b}\mid \mathbf{a}\in \mathcal{A},\text{ and }\mathbf{b}\in \mathcal{B}\}\), where \(\mathcal{A},\mathcal{B}\subset\mathbb{R}^2\) have smooth curved boundaries. The problem consists in designing algorithms to compute efficiently \(\mathbf{\alpha}(u)\bigoplus \mathbf{\beta}(u)\), where \(\mathbf{\alpha}\) and \(\mathbf{\beta}\) are closed \(C^2\) curves in \(\mathbb{R}^2\) which describe the boundaries \(\partial \mathcal{A}\) and \(\partial \mathcal{B}\), respectively. These procedures should be able to minimize intermediate calculations which do not contribute to the final result (internal edges must be discarded). In this respect, the authors present a new algorithm which employs a decomposition of the Minkowski sum envelope into smooth segments along which the \(x\) and \(y\) coordinates vary monotonically. Many of the ideas and methods developed in relation to this algorithm can be extended to other geometrical convolutions in \(\mathbb{R}^2\).

Reviewer: Jesus Illán González (Vigo)

MSC:

65D18	Numerical aspects of computer graphics, image analysis, and computational geometry
65D17	Computer-aided design (modeling of curves and surfaces)
68U05	Computer graphics; computational geometry (digital and algorithmic aspects)
68U07	Computer science aspects of computer-aided design

Keywords:

Minkowski sums; geometrical convolutions; covering degree; planar graph; topological configuration; singular points; Gauss map; curvature; computer-aided geometric design; image processing; computer graphics; animation; path planning for robots; algorithm

References:

[1]	Abdel-Malek, K.; Yeh, H. J., Geometric representation of the swept volume using Jacobian rank deficiency conditions, Comput. Aided Design, 29, 457-468 (1997)
[2]	Agarwal, P. K.; Flato, E.; Halperin, D., Polygon decomposition for efficient construction of Minkowski sums, Comput. Geometry—Theory Appl., 21, 39-61 (2002) · Zbl 0991.68124
[3]	Ahn, J. W.; Kim, M. S.; Lim, S. B., Approximate general sweep boundary of 2D object, CVGIP: Graph. Models and Image Process., 55, 98-128 (1993)
[4]	Arnborg, S.; Feng, H., Algebraic decomposition of regular curves, J. Symbol. Comput., 5, 131-140 (1988) · Zbl 0666.14012
[5]	Arnon, D. S., Topologically reliable display of algebraic curves, ACM Comput. Graphics, 17, 219-227 (1983)
[6]	Arnon, D. S.; Collins, G. E.; McCallum, S., Cylindrical algebraic decomposition I: The basic algorithm, SIAM J. Comput., 13, 865-877 (1984) · Zbl 0562.14001
[7]	Arnon, D. S.; Collins, G. E.; McCallum, S., Cylindrical algebraic decomposition II: An adjacency algorithm for the plane, SIAM J. Comput., 13, 878-889 (1984) · Zbl 0562.14001
[8]	Arnon, D. S.; McCallum, S., A polynomial-time algorithm for the topological type of a real algebraic curve, J. Symbol. Comput., 5, 213-236 (1988) · Zbl 0664.14017
[9]	Baek, B.; Shin, S. Y.; Chwa, K. Y., On computing translational swept volumes, Internat. J. Comput. Geometry Appl., 9, 293-317 (1999) · Zbl 0949.68154
[10]	Blackmore, D.; Leu, M. C.; Shih, F., Analysis and modeling of deformed swept volumes, Comput. Aided Design, 26, 315-326 (1994) · Zbl 0805.68128
[11]	Blackmore, D.; Leu, M. C.; Wang, L. P., The sweep-envelope differential equation algorithm and its applications to NC machining verification, Comput. Aided Design, 29, 629-637 (1997)
[12]	Blackmore, D.; Leu, M. C.; Wang, L. P.; Jiang, H., Swept volumes: a retrospective and prospective view, Neural Parallel Sci. Comput., 5, 81-102 (1997)
[13]	Blum, H.; Nagel, R. N., Shape description using weighted symmetric axis features, Pattern Recogn., 10, 167-180 (1978) · Zbl 0379.68067
[14]	Boltyanskii, V. G., Envelopes (1964), Macmillan: Macmillan New York · Zbl 0126.37102
[15]	Bookstein, F. L., The line-skeleton, Comput. Graphics Image Process., 11, 123-137 (1979)
[16]	Bracewell, R. N., The Fourier Transform and its Applications (1999), McGraw-Hill: McGraw-Hill New York · Zbl 0068.16503
[17]	Bruce, J. W.; Giblin, P. J., What is an envelope?, Math. Gazette, 65, 186-192 (1981)
[18]	Bruce, J. W.; Giblin, P. J., Curves and Singularities (1984), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0534.58008
[19]	Cameron, S., Collision detection by four-dimensional intersection testing, IEEE Trans. Robot. Automat., 6, 291-302 (1990)
[20]	Cellini, P.; Gianni, P.; Traverso, C., Algorithms for the shape of semialgebraic sets: a new approach, (Lecture Notes in Computer Science, vol. 539 (1991), Springer: Springer Berlin), 1-18 · Zbl 0779.14022
[21]	do Carmo, M. P., Differential Geometry of Curves and Surfaces (1976), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0326.53001
[22]	Dorf, R. C.; Bishop, R. H., Modern Control Systems (2005), Prentice-Hall: Prentice-Hall Upper Saddle River, NJ
[23]	Elber, G.; Lee, I.-K.; Kim, M.-S., Comparing offset curve approximation methods, IEEE Comput. Graphics Appl., 17, 3, 62-71 (1997)
[24]	Erdmann, M. A., Protein similarity from knot theory and geometric convolutions, (Proceedings of the Annual Conference on Research in Computational Molecular Biology. Proceedings of the Annual Conference on Research in Computational Molecular Biology, San Diego (2004)), 195-204
[25]	Farouki, R. T., The approximation of non-degenerate offset surfaces, Comput. Aided Geom. Design, 3, 15-43 (1986) · Zbl 0621.65003
[26]	Farouki, R. T., Pythagorean-hodograph curves, (Farin, G.; Hoschek, J.; Kim, M.-S., Handbook of Computer Aided Geometric Design (2002), Elsevier: Elsevier Amsterdam), 405-427 · Zbl 1003.68179
[27]	Farouki, R. T., Minkowski combinations of complex sets—geometry algorithms, and applications, (Lyche, T.; Mazure, M.-L.; Schumaker, L. L., Curve and Surface Design: Saint-Malo 2002 (2003), Nashboro Press), 123-146 · Zbl 1047.65029
[28]	Farouki, R. T.; Chastang, J.-C. A., Curves and surfaces in geometrical optics, (Lyche, T.; Schumaker, L. L., Mathematical Methods in Computer Aided Geometric Design II (1992), Academic Press: Academic Press New York), 239-260 · Zbl 0918.68127
[29]	Farouki, R. T.; Chastang, J.-C. A., Exact equations of “simple” wavefronts, Optik, 91, 109-121 (1992)
[30]	Farouki, R. T.; Gu, W.; Moon, H. P., Minkowski roots of complex sets, (Geometric Modeling and Processing 2000 (2000), IEEE Computer Society Press), 287-300
[31]	Farouki, R. T.; Han, C. Y., Computation of Minkowski values of polynomials over complex sets, Numer. Algorithms, 36, 13-29 (2004) · Zbl 1073.12006
[32]	Farouki, R. T.; Han, C. Y., Solution of elementary in the Minkowski geometric algebra of complex sets, Adv. Comput. Math., 22, 325-352 (2005)
[33]	R.T. Farouki, C.Y. Han, Root neighborhoods, generalized lemniscates, and robust stability of dynamic systems, Appl. Algebra Eng. Comm. Comput., 2006, to appear.; R.T. Farouki, C.Y. Han, Root neighborhoods, generalized lemniscates, and robust stability of dynamic systems, Appl. Algebra Eng. Comm. Comput., 2006, to appear. · Zbl 1192.65018
[34]	Farouki, R. T.; Han, C. Y.; Hass, J., Boundary evaluation algorithms for Minkowski combinations of complex sets using topological analysis of implicit curves, Numer. Algorithms, 40, 251-283 (2005) · Zbl 1087.65011
[35]	Farouki, R. T.; Hinds, J. K., A hierarchy of geometric forms, IEEE Comput. Graphics Appl., 5, 5, 51-78 (1985)
[36]	Farouki, R. T.; Moon, H. P., Minkowski geometric algebra and the stability of characteristic polynomials, (Hege, H.-C.; Polthier, K., Visualization and Mathematics III (2003), Springer: Springer Berlin), 163-188 · Zbl 1175.93182
[37]	Farouki, R. T.; Moon, H. P.; Ravani, B., Algorithms for Minkowski products and implicitly-defined complex sets, Adv. Comput. Math., 13, 199-229 (2000) · Zbl 0948.65016
[38]	Farouki, R. T.; Moon, H. P.; Ravani, B., Minkowski geometric algebra of complex sets, Geom. Dedicata, 85, 283-315 (2001) · Zbl 0987.51012
[39]	Farouki, R. T.; Neff, C. A., Analytic properties of plane offset curves & Algebraic properties of plane offset curves, Comput. Aided Geom. Design, 7 (1990), 83-99, 101-127 · Zbl 0718.53003
[40]	Farouki, R. T.; Pottmann, H., Exact Minkowski products of \(N\) complex disks, Reliab. Comput., 8, 43-66 (2002) · Zbl 1028.65048
[41]	Fowler, R. H., The Elementary Differential Geometry of Plane Curves (1929), Cambridge University Press: Cambridge University Press Cambridge · JFM 55.1014.05
[42]	Ganter, M.; Uiker, J., Dynamic collision detection using swept solids, ASME J. Mech. Transmissions, Automat. Design, 108, 549-555 (1986)
[43]	Ghosh, P. K., A mathematical model for shape description using Minkowski operators, Comput. Vision Graphics Image Process., 44, 239-269 (1988)
[44]	Gonzalez-Vega, L.; Necula, I., Efficient topology determination of implicitly defined algebraic plane curves, Comput. Aided Geom. Design, 19, 719-743 (2002) · Zbl 1043.68105
[45]	Grandine, T. A.; Klein, F. W., A new approach to the surface intersection problem, Comput. Aided Geom. Design, 14, 111-134 (1997) · Zbl 0906.68151
[46]	Hadwiger, H., Vorlesungen über Inhalt, Oberfläche, und Isoperimetrie (1957), Springer: Springer Berlin · Zbl 0078.35703
[47]	Hartquist, E. E.; Menon, J. P.; Suresh, K.; Voelcker, H. B.; Zagajac, J., A computing strategy for applications involving offsets, sweeps, and Minkowski operators, Comput. Aided Design, 31, 175-183 (1999) · Zbl 1053.68743
[48]	J. Hass, R.T. Farouki, C.Y. Han, X. Song, T.W. Sederberg, Guaranteed consistency of surface intersections and trimmed surfaces using a coupled topology resolution and domain decomposition scheme, Adv. Comput. Math., 2006, to appear.; J. Hass, R.T. Farouki, C.Y. Han, X. Song, T.W. Sederberg, Guaranteed consistency of surface intersections and trimmed surfaces using a coupled topology resolution and domain decomposition scheme, Adv. Comput. Math., 2006, to appear. · Zbl 1118.65011
[49]	Hernandez Barrera, A., Computing the Minkowski sum of monotone polygons, IEICE Trans. Inform. Syst., E80D, 218-222 (1997)
[50]	Hong, H., An efficient method for analyzing the topology of plane real algebraic curves, Math. Comput. Simulation, 42, 571-582 (1996) · Zbl 1037.14503
[51]	Hwang, H. K., A Poisson geometric convolution law for the number of components in unlabelled combinatorial structures, Combin. Probab. Comput., 7, 89-110 (1998) · Zbl 0899.60008
[52]	Imani, B. M.; Elbestawi, M. A., Geometric simulation of ball-end milling operations, ASME J. Manufact. Sci. Eng., 123, 177-184 (2001)
[53]	Karunakaran, K. P.; Shanmuganathan, P. V.; Gupta, N.; Isaac, M., Swept volume of a generic cutter, J. Eng. Manuf., 214, 915-938 (2000)
[54]	A. Kaul, Computing Minkowski sums, Ph.D. Thesis, Columbia University, 1993.; A. Kaul, Computing Minkowski sums, Ph.D. Thesis, Columbia University, 1993.
[55]	Kaul, A.; Farouki, R. T., Computing Minkowski sums of plane curves, Internat. J. Comput. Geometry Appl., 5, 413-432 (1995) · Zbl 0854.68102
[56]	Kaul, A.; Rossignac, J. R., Solid interpolating deformations: construction and animation of PIPS, Comput. Graphics, 16, 107-115 (1992)
[57]	Kieffer, J.; Litvin, F. L., Swept volume determination and interference detection for moving 3D solids, ASME J. Mech. Design, 113, 456-463 (1991)
[58]	Kim, M. S.; Ahn, J. W.; Lim, S. B., An algebraic algorithm to compute the exact general sweep boundary of a 2D curved object, Inform. Process. Lett., 47, 221-229 (1993) · Zbl 0782.68116
[59]	Kim, Y. J.; Varadhan, G.; Lin, M. C.; Manocha, D., Fast swept volume approximation of complex polyhedral models, Comput. Aided Design, 36, 1013-1027 (2004)
[60]	Lee, I. K.; Kim, M. S., Polynomial/rational approximation of Minkowski sum boundary curves, Graph. Models Image Process., 60, 136-165 (1998)
[61]	Lee, I. K.; Kim, M. S.; Elber, G., New approximation methods of planar offset and convolution curves, (Strasser, W.; Klein, R.; Rau, R., Geometric Modeling: Theory and Practice (1997), Springer: Springer Berlin), 83-101 · Zbl 0898.68084
[62]	Leu, M. C.; Park, S. H.; Wang, K. K., Geometric representation of translational swept volumes and its applications, ASME J. Eng. Industry, 108, 113-119 (1986)
[63]	Ling, Z. K.; Chase, T., Generating the swept area of a body undergoing planar motion, ASME J. Mech. Design, 118, 221-223 (1996)
[64]	Ling, Z. K.; Hu, Z. J., Use of swept volumes in the design of interference free spatial mechanisms, Mechanism Mach. Theory, 32, 459-476 (1997)
[65]	Lozano-Pérez, T.; Wesley, M. A., An algorithm for planning collision-free paths among polyhedral obstacles, Comm. ACM, 22, 560-570 (1979)
[66]	Maiteh, B. Y.; Blackmore, D.; Abdel-Malek, K.; Leu, M. C., Swept-volume computation for machining simulation and virtual reality application, J. Mat. Process. Manuf. Sci., 7, 380-390 (1999)
[67]	Martin, R. R.; Stephenson, P. C., Sweeping of three dimensional objects, Comput. Aided Design, 22, 223-234 (1990) · Zbl 0754.65019
[68]	Middleditch, A. E., Applications of a vector sum operator, Comput. Aided Design, 20, 183-188 (1988) · Zbl 0656.65021
[69]	Milnor, J., Morse Theory (1963), Princeton University Press: Princeton University Press Princeton, NJ · Zbl 0108.10401
[70]	Minkowski, H., Volumen und Oberfläche, Math. Ann., 57, 447-495 (1903) · JFM 34.0649.01
[71]	Moore, R. E., Interval Analysis (1966), Prentice-Hall: Prentice-Hall Englewood Cliffs, NJ · Zbl 0176.13301
[72]	Parida, L.; Mudur, S. P., Computational methods for evaluating swept object boundaries, Visual Comput., 10, 266-276 (1994)
[73]	Petković, M. S.; Petković, L. D., Complex Interval Arithmetic and its Applications (1998), Wiley-VCH: Wiley-VCH Berlin · Zbl 0664.65020
[74]	Ramamurthy, R.; Farouki, R. T., Voronoi diagram and medial axis algorithm for planar domains with curved boundaries I. Theoretical foundations & II. Detailed algorithm description, J. Comput. Appl. Math., 102 (1999), 119-141, 253-277 · Zbl 0939.65018
[75]	Rossignac, J. R.; Requicha, A. A.G., Offsetting operations in solid modelling, Comput. Aided Geom. Design, 3, 129-148 (1986) · Zbl 0631.65144
[76]	Roy, M.-F.; Szpirglas, A., Complexity of the computation of cylindrical decomposition and topology of real algebraic curves using Thom’s Lemma, (Lecture Notes in Mathematics, vol. 1420 (1990), Springer: Springer Berlin), 223-236 · Zbl 0718.14028
[77]	Sakkalis, T., The topological configuration of a real algebraic curve, Bull. Austral. Math. Soc., 43, 37-50 (1991) · Zbl 0716.14034
[78]	Sambandan, K.; Kedem, K.; Wang, K. K., Generalized planar sweeping of polygons, J. Manuf. Syst., 11, 246-257 (1992)
[79]	Serra, J., Image Analysis and Mathematical Morphology (1982), Academic Press: Academic Press London · Zbl 0565.92001
[80]	Serra, J., Introduction to mathematical morphology, Comput. Vision Graphics Image Process., 35, 283-305 (1986) · Zbl 0648.92001
[81]	Song, X.; Sederberg, T. W.; Zheng, J.; Farouki, R. T.; Hass, J., Linear perturbation methods for topologically consistent representations of free-form surface intersections, Comput. Aided Geom. Design, 21, 303-319 (2004) · Zbl 1069.65567
[82]	Uspensky, J. V., Theory of Equations (1948), McGraw-Hill: McGraw-Hill New York · Zbl 0005.11104
[83]	Wang, G. P.; Sun, J. G.; Hua, X. J., The sweep-envelope differential equation for general deformed swept volumes, Comput. Aided Geom. Design, 17, 399-418 (2000) · Zbl 0938.68133
[84]	Wang, W. P.; Wang, K. K., Geometric modeling for swept volume of moving solids, IEEE Comput. Graphics Appl., 6, 12, 8-17 (1986)
[85]	Weinert, K.; Du, S. J.; Damm, P.; Stautner, M., Swept volume generation for the simulation of machining processes, Internat. J. Mach. Tools Manuf., 44, 617-628 (2004)
[86]	Weld, J. D.; Leu, M. C., Geometric representation of swept volumes with application to polyhedral objects, Internat. J. Robot. Res., 9, 105-117 (1990)
[87]	Yang, J. Z.; Abdel-Malek, K., Approximate swept volume of NURBS surfaces or solids, Comput. Aided Geom. Design, 22, 1-26 (2005) · Zbl 1205.65111