From: james dolan <jdolan@math.ucr.edu>
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.