Path: utzoo!utgpu!news-server.csri.toronto.edu!mailrus!cs.utexas.edu!rutgers!njin!princeton!gauss!markv
From: markv@gauss.Princeton.EDU (Mark VandeWettering)
Newsgroups: comp.graphics
Subject: Re: Raster Rotation (Paeth's 3-pass algorithm)
Message-ID: <2033@idunno.Princeton.EDU>
Date: 23 Aug 90 01:46:33 GMT
References: <1990Aug5.001427.11318@msuinfo.cl.msu.edu> <3880003@hpspkla.spk.hp. <26c79b40-824.3graphics-1@oldcolo.UUCP> <623@ntpdvp1.UUCP>
Sender: news@idunno.Princeton.EDU
Reply-To: markv@gauss.Princeton.EDU (Mark VandeWettering)
Organization: Princeton University
Lines: 61

In article <623@ntpdvp1.UUCP> willr@ntpdvp1.UUCP (Will Raymond) writes:
	[ asks for the algorithm or further references ]

This is now outlined in the newest Foley et. al. (I am sure it will be 
a siggbowl question sometime to name the other authors).  For fun, here is 
the gist of the algorithm.  

A 2-d rotation about the origin can be expressed as a point transform by
the following matrix
			[ x y ] [ cos(theta)  sin(theta) ]
				[ -sin(theta) cos(theta) ]

We would like to write the rotation matrix R above as the product of three 
pure shear matrices.  For our example, we will have an x shear, a y shear, 
and then another x shear.   An X shear matrix is written as

	[ 1 0 ]
	[ a 1 ]

and a y shear matrix as

	[ 1 b ] 
	[ 0 1 ]

Hence if we wish to write our rotation as the three shears, we need
	
	R = 	[ 1 0 ] [ 1 b ] [ 1 0 ] = [ 1 + bc 		b      ]
		[ a 1 ] [ 0 1 ] [ c 1 ]   [ c + a + abc		1 + a b]

therefore b = sin(theta), and ab = bc, therefore a = c, therefore
1 + b a == cos(theta), a = (cos(theta) - 1) / sin(theta).  

This gives a result that is usable, except that where theta -> 0, this blows
up.  Well, I would leave it at that, but Andrew Glassner's graphics gems 
book has the following solution using the half angle identity for tangents.

tan(theta/2) = (1 - cos(theta)) / sin(theta), therefore our shears should be:

	[ 1  			0 ]
	[ -tan(theta) / 2, 	1 ]

	[ 1            sin(theta) ]
	[ 0,			1 ]

	[ 1  			0 ]
	[ -tan(theta) / 2, 	1 ]

Well, all of this is fine and good, but what makes this neat?  Why is this 
better than a plethora of other bitmap rotations like the 2-pass of Alvy 
Ray Smith.  The answer is, its pretty easy to implement!

If you think about what each of the shears is doing, it is copying a row
or column "pixelwise" to another location.  But, it does it in a nice way, 
no interpolations or other nastiness is needed.  Basically, for the cost 
of three copies per pixel, you can achieve a bitmap rotation.  It is 
trivial to extend this to allow for nice filtering.

I like this scheme alot.  I recommend it highly.  Check out Foley & Van
Damn & Glassner's Graphics Gems for more details.

Mark