home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1993 #1 / NN_1993_1.iso / spool / comp / graphics / 13595 < prev    next >
Encoding:
Text File  |  1993-01-09  |  2.1 KB  |  91 lines
  1. Newsgroups: comp.graphics
  2. Path: sparky!uunet!cs.utexas.edu!torn!news.ccs.queensu.ca!qucis.queensu.ca!hausner
  3. From: hausner@qucis.queensu.ca (Alejo Hausner)
  4. Subject: fast bitmap rotation
  5. Message-ID: <1993Jan9.045327.21333@qucis.queensu.ca>
  6. Keywords: shear, rotation, bitmap
  7. Organization: M.Sc, C.S, Queen's, Kingston, Canada.
  8. Date: Sat, 9 Jan 1993 04:53:27 GMT
  9. Lines: 80
  10.  
  11.  
  12. How to rotate a bitmap using two shears:
  13. (from Foley and van Dam).
  14.  
  15. Reference: E. Catmull and A.R. Smith, "3-D transformations of
  16. images in scan-line order", SIGGRAPH 80, 279-285.
  17.  
  18. You want to rotate an n x n array of pixels by an angle phi.
  19. A mathematician would tell you that the necessary transformation
  20. is:
  21.  
  22. x' = x cos(phi) - y sin(phi)
  23. y' = x sin(phi) + y cos(phi)
  24.  
  25. But this involves n^2 multiplications, and is slow. 
  26. If we replace it with a two-step transformation, we can do it
  27. faster.  First we go from (x,y) to (u,v), then to (x',y').  The
  28. transformation equations are:
  29.  
  30. u = x
  31. v = x sin(phi) + y cos(phi)
  32.  
  33. x' = u sec(phi) - v tan(phi)
  34. y' = v
  35.  
  36. If you substitute the first pair into the second pair of
  37. equations, you retrieve the original transformation, so it works.
  38.  
  39.  
  40. Note that when phi=90 degrees, the secant and tangent terms are
  41. infinite, so the transformation doesn't work.  Hence rotations by
  42. 90 and 270 degrees must be handled as special cases.  This isn't
  43. a problem.  Also if phi is close to 90 or 270 degrees, there will
  44. be accuracy problems, and in that case it is better to rotate the
  45. bitmap by 90 (or 270) degrees first, and then rotate by 90-phi
  46. (or 270-phi) degrees.
  47.  
  48. Algorithm:
  49.  
  50. sinphi = sin(phi)
  51. cosphi = cos(phi)
  52. secphi = 1.0/cosphi
  53. tanphi = sinphi/cosphi
  54.  
  55. for x = 1 to n
  56.   xs[x] = x * sinphi
  57.   us[x] = x * secphi
  58.   ys[x] = x * cosphi
  59.   vt[x] = x * tanphi
  60. end for
  61.  
  62. for x = 1 to n
  63.   u = x
  64.   xsinphi = xs[x]
  65.   for y = 1 to n
  66.     v = xsinphi + yc[y]
  67.  
  68.     array2[u,v] = array[x,y]
  69.   end for
  70. end for
  71.  
  72. for v = 1 to n
  73.   yp = v
  74.   vtanphi = vt[v]
  75.   for u = 1 to n
  76.     xp = us[u] - vtanphi
  77.  
  78.     array[xp,yp] = array2[u,v]
  79.   end for
  80. end for
  81.  
  82.  
  83. I hope that works.  I just threw it together on the fly.
  84.  
  85.  
  86. Alejo Hausner (hausner@qucis.queensu.ca)
  87.  
  88. -- 
  89. Alejo Hausner.  (hausner@qucis.queensu.ca)
  90.  
  91.