jteh@mulga.oz (J.T. Teh) (08/28/87)
I need a rotation algorithm that will allow me to rotate the contents of
a bounding rectangle at a given angle. Currently, I am using the standard
algorithm of rotating the point around the origin with
[ cosX -sinX ][ x ]
[ sinX cosX ][ y ]
but this causes the resultant image to have "holes" in it if I am rotating
a filled image (with black). Each set pixel in the bounding rectangle is
rotated in this fashion and is very tedious as each row of pixels has to
be scanned. I know that this is a very slow method but I am currently stuck
with it for want of a better method.
The free rotation method used in SuperPaint does not have this problem and
I would like to know how those guys did it.
I am using the rotation as part of an Honours Project application in visual
recognition and would appreciate it greatly if somebody could mail me a
better algorithm. If there is anyone else who would be interested in such
an algorithm, I will post the suggested algorithms on the news.
Thanks in advance.
J.T. Teh
===========================
UUCP: {seismo,mcvax,ukc,ubc-vision}!mulga!jteh
ARPA: jteh%mulga.oz@seismo.css.gov
CSNET: jteh%mulga.oz@australiaavjewe@cvl.UUCP (08/31/87)
In article <2180@mulga.oz> jteh@mulga.oz (J.T. Teh) writes: >I need a rotation algorithm that will allow me to rotate the contents of >a bounding rectangle at a given angle. Currently, I am using the standard >algorithm of rotating the point around the origin with > [ cosX -sinX ][ x ] > [ sinX cosX ][ y ] >but this causes the resultant image to have "holes" in it if I am rotating Your algorithm is correct, just run it backwards. That is for each point in the destination rectangle, calculate which point in the original maps to it. Presto! no holes. As for your speed problem, I think your out of luck. There are three things I can think of (probobly many I can't) none of which are very helpful. 1) special cases (30, 45, 90 and such) 2) rotate objects rather than dots if available 3) rather than the sin and cosine functions, use pre-filled arrays (e.g. sin[45] instead of sin(45). This only works if you have a well defined small domain) Hope this helps, Andy Jewell disclaimer: I don't really know much about this stuff
thomas%spline.uucp@utah-gr.UUCP (Spencer W. Thomas) (09/01/87)
Summary:
Expires:
Sender:
Followup-To:
Distribution:
There are several algorithms for doing this, all based on a "scanline"
method. The basic idea is to skew the image first in the X direction,
then in the Y direction. You can accomplish a rotation up to 45deg
with this technique. To get rotations > 45 degrees, you first rotate
by a multiple of 90 (easily accomplished). Some references:
Catmull, E. and Smith, A.R., "3-D Transformations of Images in
Scanline Order", Computer Graphics, Vol 14, No 3, July 1980
(SIGGRAPH '80 Conference Proceedings).
Fant, K., "A Nonaliasing, Real-Time Spatial Transform
Technique", IEEE Computer Graphics and Applications, January
1986, (See also Letters to the Editor, IEEE CG&A, March 1986
and July 1986.)
Paeth, A., "A Fast Algorithm for General Raster Rotation",
Graphics Interface '86 Proceedings, May 1986.
I will attempt a picture demonstrating the technique:
.............. .............. ....
. . . . . ...
. . X skew . . Y skew .. ...
. . ------> . . -----> . ...
. . . . ... ..
. . . . ... ..
.............. .............. ... .
... ..
..
=Spencer ({ihnp4,decvax}!utah-cs!thomas, thomas@cs.utah.edu)