From: james dolan Subject: Re: Minkowski Sum tutorial? Date: Fri, 01 Dec 2000 05:17:07 GMT Newsgroups: sci.math Summary: [missing] phlip_cpp@my-deja.com wrote: |I have a public high-school education. Don't ask how I got a job |writing computer graphics programs that visualize multidimensional |objects. | |What's the simplest tutorial on the 'net that explains "Minkowski |Sums"? Or maybe someone could go ahead and author a quick one? ok, here's a minkowski sum tutorial aimed at computer graphics programmers with american public high-school educations. first of all, forget about "minkowski sum". instead of telling you about "minkowski sum", i'm going to tell you about "minkowski interpolation" (a name i just made up), which is almost exactly the same thing as "minkowski sum", but probably a bit more useful for computer graphics programmers. "minkowski interpolation" is just about the simplest imaginable way of "morphing" a convex shape x (for example the interior of a square) into some other convex shape y (for example the interior of a circle). that is, "minkowski interpolation" is a function that takes in three inputs x (a convex shape), y (another convex shape), and t (a real number between 0 and 1 that we think of as representing a moment of "time"), and outputs a convex shape that looks like "x about a fraction t of the way towards turning into y". (so for example if t is 0.5 then the output looks like an exactly half-and-half mixture of x and y, while if t is 0.75 then the output is three quarters of the way towards turning into y.) and the way it works is like this: a point p belongs to the time t minkowski interpolation of x and y precisely in case there's a point x1 in x and a point y1 in y such that p is on the straight line from x1 to y1, exactly a fraction t of the distance from x1 to y1. in other words: suppose for example the shape x is 3 pixels big, and the shape y is 7 pixels big. then to do minkowski-interpolation morphing of x into y, you should hire 21 (=3x7) ants, and give each one of them the job of walking at a steady pace (faster or slower depending on the distance they have to cover) on the screen from one of the 3 pixels in x to one of the 7 pixels in y. (make sure the ants don't mind crowding on top of each other when necessary. for example at the beginning they're stacked in piles 7 ants high onto just 3 pixels, while at the end they're stacked in piles 3 ants high onto 7 pixels.) in pseudo-code: for x1 := 1 to 3 do for y1 := 1 to 7 do {hire one ant to walk from the x1^th pixel of x to the y1^th pixel of y.} of course, a clever programmer might figure out better ways of accomplishing this than hiring ants. so how good is this as a morphing technique? it's rather primitive, i think. as a matter of fact i know practically nothing about the computer graphics business, but i'd imagine that if computer graphics programmers use minkowski interpolation it would be in situations where they want something "quick and dirty" rather than something that actually looks good. another way of understanding what the time t minkowski-interpolation of x and y looks like is that it's what you get if you "try to draw a picture of x using a pencil whose point is shaped like y", with t representing how big the pencil point is and 1-t representing how big a picture you're trying to draw. returning to the example where x is the interior of a square and y is the interior of a circle, it's thus like "trying to draw a picture of a square using a pencil whose point is shaped like a circle". if t is close to zero then you're trying to draw a big square with a sharp pencil point and the result looks like a square with maybe just very slightly rounded corners. if t is close to 1 though then you're trying to draw a small square with a blunt circular pencil point, and the result looks more like the circular pencil point than like the picture you're trying to draw. (the corners of the "square" become so rounded that the "square" looks more like a circle.) if i remember correctly, "the minkowski sum of x and y" means something like "the time 1/2 minkowski interpolation of x and y". Sent via Deja.com http://www.deja.com/ Before you buy.