diff options
Diffstat (limited to 'dviware/umddvi/misc/rot.alg')
-rw-r--r-- | dviware/umddvi/misc/rot.alg | 44 |
1 files changed, 44 insertions, 0 deletions
diff --git a/dviware/umddvi/misc/rot.alg b/dviware/umddvi/misc/rot.alg new file mode 100644 index 0000000000..76aa85e718 --- /dev/null +++ b/dviware/umddvi/misc/rot.alg @@ -0,0 +1,44 @@ +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 + + |