ph@miro.Berkeley.EDU.berkeley.edu (Paul Heckbert) (11/15/88)
In response to the question about rotating bitmaps by mikem@uhccux.uhcc.hawaii.edu (Mike Morton), came the response: > From: cm26+@andrew.cmu.edu (Curt McDowell) > ... >* CORDIC is the only imaginable way to accomplish this >* task. If anyone thinks I'm wrong, please tell me about your > ... Well, YES, there are several other standard ways. (I've never seen multiple CORDIC steps used for image rotation before -- it's interesting -- but couldn't it take about 10 passes to rotate a 1024x1024 image by an arbitrary angle? And why not do one pass with a 2x2 integer rotation matrix instead, since multiplies are faster than pixel i/o subroutine calls?) Mike Morton's followup summary gave the references to Fant, Foley-Van Dam, Jackson, Paeth, and Tanaka-Kameyama-Kazama-Watanabe, but there are other excellent references that no one has yet mentioned. The original references to multiple pass warps and source image scanning (variations of which were described in Mike's summary) are: multiple-pass image warps: Ed Catmull, Alvy Ray Smith, ``3-D Transformations of Images in Scanline Order'', "Computer Graphics" (SIGGRAPH '80 Proceedings), Vol. 14, No. 3, July 1980, pp. 279-285. (Fant's paper seems to be a very verbose exposition of the straightforward linear interpolation filters suggested by Catmull and Smith) Carl F. R. Weiman, ``Continuous Anti-Aliased Rotation and Zoom of Raster Images'', "Computer Graphics" (SIGGRAPH '80 Proceedings), Vol. 14, No. 3, July 1980, pp. 286-293. Source image scanning (using Bresenham along diagonal lines): Carlo Braccini, Giuseppe Marino, ``Fast Geometrical Manipulations of Digital Images'', "Computer Graphics and Image Processing", Vol. 13, 1980, pp. 127-141. Another important algorithm that no one has mentioned is: scan out the destination image in scanline order, at each destination pixel inverting the rotation transformation to compute the coordinates of the source image mapped to that point, and either point sample that pixel from the source image or filter an area around it. I briefly surveyed these and other methods in the paper: Paul Heckbert, ``Survey of Texture Mapping'', IEEE Computer Graphics and Applications, Nov. 1986, pp. 56-67. an excerpt of which follows: Notes: To relate the following to image warps, wherever I say "texture space" substitute "source image" and where I say "screen space" substitute "destination image". Texture space has coordinates (u,v). Screen space has coordinates (x,y). A 2-D linear warp has the form x=au+bv, y=cu+dv. A 2-D affine warp has the form x=au+bv+c, y=du+ev+f. ----------------- beginning of excerpt ------------------- .SH Scanning Order .LP There are three general approaches to drawing a texture mapped surface: a scan in screen space, a scan in texture space, and two-pass methods. The three algorithms are outlined below: .DS \fBSCREEN SCANNING:\fP for y for x compute u(x,y) and v(x,y) copy TEX[u,v] to SCR[x,y] \fBTEXTURE SCANNING:\fP for v for u compute x(u,v) and y(u,v) copy TEX[u,v] to SCR[x,y] \fBTWO-PASS:\fP for v for u compute x(u,v) copy TEX[u,v] to TEMP[x,v] for x for v compute y(x,v) copy TEMP[x,v] to SCR[x,y] .DE where TEX is the texture array, SCR is the screen array, and TEMP is a temporary array. Note that copying pixels involves filtering. .LP Screen order, sometimes called inverse mapping, is the most common method. For each pixel in screen space, the pre-image of the pixel in texture space is found and this area is filtered. This method is preferable when the screen must be written sequentially (e.g. when output is going to a film recorder), the mapping is readily invertible, and the texture is random access. .LP Texture order may seem simpler than screen order, since inverting the mapping is unnecessary in this case, but doing texture order correctly requires subtlety. Unfortunately, uniform sampling of texture space does not guarantee uniform sampling of screen space except for affine (linear) mappings. Thus, for non-affine mappings texture subdivision must often be done adaptively; otherwise, holes or overlaps will result in screen space. Scanning the texture is preferable when the texture to screen mapping is difficult to invert, or when the texture image must be read sequentially (for example, from tape) and will not fit in random access memory. .LP Two-pass methods decompose a 2-D mapping into two 1-D mappings, the first pass applied to the rows of an image and the second pass applied to the columns [Cat80]. These methods work particularly well for affine and perspective mappings, where the warps for each pass are linear or rational linear functions. Because the mapping and filter are 1-D they are amenable to stream processing techniques such as pipelining. Two-pass methods are preferable when the source image cannot be accessed randomly but it has rapid row and column access, and a buffer for the intermediate image is available. .SH \fIOrthographic Projection\fP .LP Orthographic projections of linearly-parameterized planar textures have an affine composite mapping. The inverse of this mapping is affine as well, of course. This makes them particularly easy to scan in screen order: the cost is only two adds per pixel, disregarding filtering [Smi80]. It is also possible to perform affine mappings by scanning the texture, producing the screen image in non-scanline order. Most of these methods are quite ingenious. .LP Braccini and Marino show that by depositing the pixels of a texture scanline along the path of a Bresenham digital line, an image can be rotated or sheared [Bra80]. To fill the holes that sometimes result between adjacent lines, they draw an extra pixel at each kink in the line. This results in some redundancy. They also use Bresenham's algorithm [Fol82] in a totally different way: to resample an array. This is possible because distributing $m$ source pixels to $n$ screen pixels is analogous to drawing a line with slope $n/m$. .LP Weiman also uses Bresenham's algorithm for scaling but does not draw diagonally across the screen [Wei80]. Instead he decomposes rotation into four scanline operations: xscale, yscale, xshear, and yshear. He does box filtering by averaging together several phases of the scaled image. .LP Affine mappings can be performed with multiple pass methods in several ways. Catmull and Smith decompose such mappings into a composition of two shear-and-scale passes: one horizontal and the other vertical [Cat80]. In a simpler variation discovered by Paeth, a rotational mapping is decomposed into three passes of shears: the first horizontal, the second vertical, and the third horizontal [Pae86]. Filtering for this three pass rotate is particularly simple because resampling the scanlines involves no scaling. ----------------- end of excerpt ----------------- A point on terminology: The word "bitmap" refers to one bit per pixel images, not multiple bit per pixel images. Multiple bit per pixel images should be called "grayscale images" or "color images". Paul Heckbert, CS grad student 508-7 Evans Hall, UC Berkeley UUCP: ucbvax!miro.berkeley.edu!ph Berkeley, CA 94720 ARPA: ph@miro.berkeley.edu