awpaeth@watcgl.waterloo.edu (Alan Wm Paeth) (01/13/89)
In article <2901@pixar.UUCP> efo@pixar.uucp (efo) writes: >In article <17963@dhw68k.cts.com> stein@dhw68k.cts.com (Rick Stein) writes: >>I'm curious to know about how one performs rotations on pixel data. >And the other answer is, yes, you can decompose a rotation into shears >which can be done quite cheaply; see...[Catmull/Smith, SIGGRAPH '80] The citation previously posted does *not* treat the shearing approach but instead focusses on 2-pass separable forms (Smith reprises the 2-pass methods in SIGGRAPH '87 pp. 263-272). The work has direct application in image warping. 3-pass rotation using shear matrices appears in: ``A Fast Algorithm for General Raster Rotation'' Paeth, A. W. Proceedings, Graphics Interface '86, Canadian Information Processing Society, Vancouver, pp 77-81. Shearing (i.e. no image stretching or scaling) yields a very efficient inner- loop despite the extra pass, but leaves the technique rotation-specific. It also allows for 90-degree rotation (which 2-pass techniques do not): here it generalizes the 90deg 3-pass shuffle used by the Blit terminal and elsewhere (eg: Kornfeld, C. ``The Image Prism: A Device for Rotating and Mirroring Bitmap Images'' IEEE Computer Graphics and Applications 7(5) pp 25.). The scale invariance during rotation can be used nicely in making circle or polygon generaters that are provably correct. The matrix forms in the paper shed light on how and why the following oft-cited bit of CS lore works: /* Find next CW point along circle perimeter, start with [X,Y] = [1,0] */ X' = X + eps*Y; Y' = -eps*X'+ Y; /* carry down __X'__, not X for best results! */ As proposed by Newman and Sproull (vol I only), ascribed to I.E. Sutherland, and mentioned recently in Jim Blinn's Corner (Algorithm 6 in ``How Many Ways Can You Draw A Circle, IEEE CG&A, August, 1987). Adding a third line: X'' = X' + eps*Y'; /* carry down some more! */ corresponding to the third shearing pass (plus some one-time-only trig to find eps in statement two, because eps[1]=eps[3]<>eps[2]) now gives rise to a circle drawer in which "eps" can be large enough to draw closed n-gons with impunity. Incidentally, the earliest reference I find to three-pass shear matrix techniques goes to C. F. Gauss. His application was, ironically: Ray Tracing! (Three shear passes occur for each refraction-transfer-refraction of a ray through a lens. See Blaker, J. W., __Geometric Optics -- The Matrix Theory__, Marcel Dekker, (New York) 1971). I have previously posted the fuctional source appearing in the raster rotation paper; I'm happy to mail interested parties (or post given sufficient interest) a TeX document which refines the above circle-generator discussion along the lines of Blinn's CG&A article. /Alan Paeth Computer Graphics Laboratory University of Waterloo