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