willr@ntpdvp1.UUCP (Will Raymond) (08/23/90)
Hello comp.graphics
I cannot find the article mentioned in Freq. Asked Quest. #6 referencing
Paeth's three shear operation rotation algorithm. I have checked four
local universities and none have Graphics Interface '86. If you could
post a seperate reference to the same article or the algorithm itself,
I would appreciate it.
******* Will Raymond - Northern Telecom NTP in RTP
| | ~ ~ | |
. O o . I speak for myself.
| .V. |
._ _.
| U |markv@gauss.Princeton.EDU (Mark VandeWettering) (08/23/90)
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.
Markpmoran@m.cs.uiuc.edu (08/24/90)
> Written 2:19 pm Aug 22, 1990 by willr@ntpdvp1.UUCP .... > /* ---------- "Raster Rotation" ---------- */ > Hello comp.graphics > > I cannot find the article mentioned in Freq. Asked Quest. #6 referencing > Paeth's three shear operation rotation algorithm. I have checked four > local universities and none have Graphics Interface '86. If you could > post a seperate reference to the same article or the algorithm itself, > I would appreciate it. > ******* Will Raymond - Northern Telecom NTP in RTP Check out "A Fast Algorithm for General Raster Rotation" in the new Graphics Gems, page 179. Quoting from the footnote: "This paper revises and updates the journal article (Paeth, 1986a) ....
willr@ntpdvp1.UUCP (Will Raymond) (08/28/90)
Thank - you to all the people who responded ( Skip, Anselmo, Mark, Jim, Ron,
pmoran..)....I'm looking for Gem's and have bought Foley et al.
( yes..a great book ).
I've found that the shear operation gives fast - down and dirty results for
"interactive" rotations -- I then convolve the image with a mex. hat
filter to smooth it a little more...works great.
Thank-you again,
Will
******* Will Raymond - Northern Telecom NTP in RTP
| | ~ ~ | |
. O o . I speak for myself.
| .V. |
._ _.
| U |