jteh@mulga.oz (J.T. Teh) (09/09/87)
Thanks for all those who replied to my post requesting a rotation algorithm
that would solve the problem of the rotated sihloutte having "holes".
The main algorithm that would solve the above problem is to do the map
backwards and test if the unrotated pixel was set. However, no faster
algorithm was suggested. My current algorithm still scans the whole
array (a 200 by 200 in about 1 minute 30 seconds with optimisation by
removing multiplications and divisions from the loops).
I would still like to know if there is a fast algorithm for doing a rotation
as in SuperPaint which can do it in less than 2 seconds.
Below are the replies I received.
---------------------------------------------------------------------------
From: sho@tybalt.caltech.edu (Sho Kuwamoto)
Re: rotations
This is a typical problem with any graphics operation involving stretching,
rotations, or any type of distortion. The solution is to do the map backwards.
Take every point in your target, and map it back to its corresponding point
in the source.
What kind of work are you doing? I helped a friend of mine on this exact
topic. He was working on some sort of vision related program which dealt
with some things called textons. I don't know what they are, but I though
you might.
-Sho
-----------------------------------------------------------------------------
From: uunet!rutgers!moss!codas!auscso!mentat (Robert Dorsett)
I've faced similar problems, but with 3d generation algorithms. I don't know
of any better algorithms, but you might want to try one of the following two
techniques:
1. Don't use the SANE transcendental package more than once. That is, create
a lookup table and put the SANE cos and sin values in it. If you need single-
degree precision, just use something like
double cos[360],sin[360]
If you need mixed-point precision, you can iterate an in-between value with
great accuracy. SANE is SLOW.
2. Depending on your aplication, you MIGHT find the type "FIXED" or "LONGINT"
to be somewhat useful in calculations. Particularly with Longint, if you can
somehow skip between-point numbers, you can totally avoid the floating-point
bog by simply setting your lookup table to, say, four digits of accuracy. A
0.7071 number, for example, would exist in the lookup table as 7071. If you
need X cos[X] (where X===7071, it'd just be one multiply (X7071) and one div-
ide (X7071/10000). You do lose a bit of precision if you lose track of your
original matrix and continue to rotate an already-rotated matrix, though.
For references, I recommend Foley and Van Dam's "Fundamentals of Interactive
Computer Graphics" and, for a modern update, Artwick's "Microcomputer Diplays,
Graphics, and Animation." Artwick's book is a bit more elementary than the
Foley/Van Dam book, but has better sections on numerical techniques and a
really good section on hardware technology. It's more applications-oriented.
Robert
---------------------------------------------------------------------------
From: sun!rainier!dchen (David Chenevert)
What you're doing is taking each pixel in a source rectangle and
dropping it into a destination 'diamond' (rotated rectangle), right? And
some of the pixels in the destination diamond don't get anything dropped on
them, right? How about the following: Take each pixel in the destination
diamond, back-compute which pixel should be copied into it, and do that copy.
This will assure that each destination pixel gets written on.
No faster than before, but better results, I think.
----------------------------------------------------------------------------
If you have an answer on this one, please let me also know.
Im trying to get a quick algorithm for converting a flat-image
to a bol-image.
The problems involved seem the same.
One of the hints is: make a table for sine, cosine from 0 - 90 degrees in
float numbers, steps of 1/4 degree. This will take you 4 bytes * 90 degrees
* 4 entrys per degree * 2 tables ==>> not too much space if you take
a global predefined array.
Piter Jonker
Hilversum, Holland.
ihnp4!hvlpa!pjonker.
------------------------------------------------------------------------------
From: Ken "Turk" Turkowski <turk@apple>
Try defining a polygon, rotating the polygon vertices, and filling the
resultant polygon.
------------------------------------------------------------------------------
The suggestion by Ken 'Turk' Turkowski seems the faster algorithm for my
particular problem but is there a faster _general_ rotation algorithm?
Thanks to all who replied in response to my query.
J.T. Teh
===========================
UUCP: {seismo,mcvax,ukc,ubc-vision}!mulga!jteh
ARPA: jteh%mulga.oz@seismo.css.gov
CSNET: jteh%mulga.oz@australia