home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #31 / NN_1992_31.iso / spool / comp / programm / 3350 < prev    next >
Encoding:
Internet Message Format  |  1992-12-22  |  2.4 KB
  1. Path: sparky!uunet!noc.near.net!hri.com!spool.mu.edu!yale.edu!qt.cs.utexas.edu!cs.utexas.edu!convex!convex!dodson
  2. From: dodson@convex.COM (Dave Dodson)
  3. Newsgroups: comp.programming
  4. Subject: Re: Fast array rotation
  5. Message-ID: <1992Dec22.154338.15357@news.eng.convex.com>
  6. Date: 22 Dec 92 15:43:38 GMT
  7. References: <u895027.724990251@tasman>
  8. Sender: usenet@news.eng.convex.com (news access account)
  9. Reply-To: dodson@convex.COM (Dave Dodson)
  10. Organization: Engineering, CONVEX Computer Corp., Richardson, Tx., USA
  11. Lines: 30
  12. Originator: dodson@bach.convex.com
  13. Nntp-Posting-Host: bach.convex.com
  14. X-Disclaimer: This message was written by a user at CONVEX Computer
  15.               Corp. The opinions expressed are those of the user and
  16.               not necessarily those of CONVEX.
  17.  
  18. In article <u895027.724990251@tasman> u895027@tasman.cc.utas.edu.au (Mark Mackey) writes:
  19. >
  20. >    I am currently writing a terrain display routine which utilises
  21. >a fast surface display algorithm based on scan-line processing. As
  22. >part of the algorith I need to rotate the raw data array. I have an
  23. >algorithm to do this using two 1d transforms, but in between these
  24. >transforms the data array needs to be transposed.
  25. >    Does anyone out there have any code for fast array transposition
  26. >on disk, minimising disk access time? Alternatively, if anyone out there
  27. >has ideas on how to rotate a large array (512*512 reals) efficiently
  28. >I would be most grateful.
  29.  
  30. I assume you have the array stored on disk in row- or column-major order.
  31. There is a way to transpose the array by reading and writing the matrix
  32. twice.  For simplicity, assume you have row-major order, 4 byte reals,
  33. and a scratch array of length 64K bytes.  Read 65536/4/512 = 16 rows into
  34. the scratch array.  Write 16 x 16 square blocks onto a scratch file.  There
  35. will be 512/16 = 32 of them for every 16 rows.  Repeat for all rows of the
  36. matrix.  Now randomly read blocks 1, 33, 65, ... .  Transpose each 16 x 16
  37. block in memory, and write out the first 16 rows of the transposed matrix.
  38. Repeat with blocks 2, 34, 66, ... , 3, 35, 67, ... .
  39.  
  40. Alternatively, you might consider storing your 512 x 512 matrix in those
  41. 16 x 16 blocks as your standard storage format.  Then you can easily read
  42. or write it in either normal or transposed form using that 64K scratch array.
  43.  
  44. ----------------------------------------------------------------------
  45.  
  46. Dave Dodson                                     dodson@convex.COM
  47. Convex Computer Corporation      Richardson, Texas      (214) 497-4234
  48.