From shulman@topaz.RUTGERS.EDU (Jeff Shulman) Wed Nov 27 09:29:19 1985
Relay-Version: version B 2.10.1 6/24/83; site umcp-cs.UUCP
Posting-Version: version B 2.10.3 4.3bsd-beta 6/6/85; site topaz.RUTGERS.EDU
Path: umcp-cs!seismo!caip!topaz!shulman
From: shulman@topaz.RUTGERS.EDU (Jeff Shulman)
Newsgroups: net.graphics
Subject: Re: bitmap rotation algorithm needed
Message-ID: <4242@topaz.RUTGERS.EDU>
Date: Wed, 27-Nov-85 09:29:19 EST
Date-Received: Wed, 27-Nov-85 22:38:05 EST
References: <4224@topaz.RUTGERS.EDU> <2809@watcgl.UUCP> <35@brl-tgr.ARPA>
Reply-To: shulman@topaz.UUCP (Jeff Shulman)
Organization: Rutgers Univ., New Brunswick, N.J.
Lines: 26


Since noone came up with any more algorithms than I already knew I will
mention those.  They can be found in "ACM Transactions on Graphics" Vol 1
No. 3, July 1982 Pages 191-214.

The first algorithm, shearing, can work on any N x N matrix and you need
an extra 2N x 2N temporary bitmap for storage.  The gist of this algorithm
is that individual rows and columns are rotated around themselves in
stepwise amounts.  In the first rotation you rotate the I'th row around
itself by I bits.  You then rotate the J'th column by N - J - 1 bits down.
You finally rotate back the I'th row by N - I - 1 bits left.

The second algorithm, binary mask (developed by Floyd), works on an N x N
matrix where N is a power of two.  This algorithm works by swapping
halves and then opposite corners of the bitmap recursively halving the
size of the pieces being swapped.  By cleverly using a mask it is possible
to accomplish all the recursive swapping in parallel.  A better explanation
of this algorithm can be found in "Smalltalk-80, the language and an
implementation" (I believe that's the correct title) on pages 408-410.


							Jeff

uucp:   ...{harvard, seismo, ut-sally, sri-iu, ihnp4!packard}!topaz!shulman
arpa:   SHULMAN@RUTGERS
CIS:    76136,667
Delphi: JEFFS