Path: utzoo!mnetor!uunet!husc6!mailrus!ames!eos!jbm
From: jbm@eos.UUCP (Jeffrey Mulligan)
Newsgroups: comp.graphics
Subject: Re: Mapping algorithm question - NOT cartograpy
Message-ID: <522@eos.UUCP>
Date: 11 Apr 88 18:35:44 GMT
References: <844@agora.UUCP>
Organization: NASA Ames Research Center, California
Lines: 79

From article <844@agora.UUCP>, by rickc@agora.UUCP (Rick Coates):
> A new question:  I am interested in mapping one 2d area into another.
> The first area may be rectangular, the second a collection of vectors
> with four points defined as corresponding to the original rectangle's.
> 

This sounds like a projective transformation (determined by four points).

> This is a 'rubber sheet' analogy, where you draw a picture on a stretchable
> sheet, then deform it.
> 

A projective transformation might be better characterized as taking
the original picture, moving it around in 3-D, and then taking
a perspective view of it:

        x        x                     x
                                             x
                         --->
                                             x
        x        x                     x

Unlike arbitrary rubber sheet deformations, projective transformations
take straight lines into straight lines, while not preserving
metric relationships such as distance and angles.

> Any references?  The closest I have found is some references in older
> ray tracing papers on texture mapping, but the articles just discuss
> this as a concept, not how to do it.
> 

I read a 1910 textbook on projective geometry and then started hacking
(although I'm pretty sure there must be some references out there).

The general form of the projective tranformation is as follows

	x' = (ax+by+c)/(gx+hy+i)

	y' = (dx+ey+f)/(gx+hy+i)

You can set i=1 and solve for the 8 remaining parameters.  The way I
did this invovled setting up a system of 8 linear equations (two
from each of your four specified points) and solving by inverting
an 8 by 8 matrix.

The denominator in the above equations is like the z coordinate you
divide by in the perspective transformation.  Bad things happen when it
is zero.

> I have seen this done - at SIGGRAPH 85 a French company had some
> presentation graphics (? I think) running on a Tektronix 4115 that
> seemed to do this, but I didn't have a chance to play with it.
> 

I have seen an image representing some familiar image processing
pictures (mandrill, girl with feather) stuck onto the faces of
a perspective cube.  Someone on the net must know who did that.

> I realize that this problem is not completely defined - behavior in
> in extreme cases may be odd.  I am interested in any and all input.

I think it is well defined.

> 
> Some other comments: it isn't necessary to transform lines or other
> complex shapes, just points will do - long vectors can be broken into
> short enough ones. Holes might be interesting (what happens if your
> hole goes outside the outer boundary? Do you invert?).
> 

I'm not sure what you mean by holes, but a projective transformation
can take an ellipse into a pair of hyperbolae (two points at infinity).


-- 

	Jeff Mulligan (jbm@ames-aurora.arpa)
	NASA/Ames Research Ctr., Mail Stop 239-3, Moffet Field CA, 94035
	(415) 694-5150