home *** CD-ROM | disk | FTP | other *** search
/ Amiga ISO Collection / AmigaUtilCD2.iso / Programming / Assembler / dse-src3.dms / in.adf / Source / Ham / hamshadow2.txt < prev   
Encoding:
Internet Message Format  |  1993-01-06  |  4.0 KB
  1. From: ahg@k.cc.purdue.edu (Allen Braunsdorf)
  2. Newsgroups: comp.sys.amiga
  3. Subject: HAM Register Selection (was Re: Sculpt-4D Upgrade)
  4. Summary: Use modified median cut algorithm
  5. Date: 26 Oct 88 18:55:41 GMT
  6. Organization: 3-D Computer Graphics From Hell
  7.  
  8. In article <2862@sugar.uu.net> peter@sugar.uu.net (Peter da Silva) writes:
  9. >In article <1121@leah.Albany.Edu>, rsb584@leah.Albany.Edu (Raymond S Brand) writes:
  10. >> If erradicating this defect is that important to you, devise and
  11. >> publish an algorithm/code that when given an X by Y image D bits deep, will
  12. >> output an X by Y HAM image and color table such that the "HAM shadows" are
  13. >> minimized for the image.
  14. >
  15. >Well, the outline is conceptually easy. If you're handling HAM at all you have
  16. >some sort of function that will tell you the distance between seperate colors
  17. >so I'm going to take that as a given.
  18. >
  19. >The simplest algorithm would be to alternate the error propogation on a
  20. >scanline basis, the way nroff does to prevent rivers of whitespace in one
  21. >or the other margin. A better algorithm would be:
  22. >
  23. [Goes on to threshold distance formula and then do some HAM and selection stuff]
  24.  
  25. Admittedly, I haven't read all the followups to this, but here's a very
  26. brief description of the algorithm I use.  The output is >really< sharp!
  27.  
  28. 1.  Generate a histogram.  This histogram should contain a count for each
  29. possible color.  That makes 16 x 16 x 16 = 4096 cells.  In each cell, put the
  30. sum of the "diminished distance formula" calculated for every point of that
  31. color in the image but not in the first column.
  32.  
  33.     The diminished distance formula at a point is found from the color
  34.     of that pixel and the pixel to its left.  Let dr, dg, and db be the
  35.     absolute value of the difference between the red, green, and blue
  36.     components of the two points respectively.  The dimished distance is
  37.     then the sum of the squares of the two lowest deltas.  This will
  38.     give a number in the range (0, 450).
  39.  
  40. The histogram will then contain numbers that will fit in a ULONG.
  41.  
  42. 2.  Median cut this histogram into sixteen bricks as described in Paul
  43. Heckbert's classic article (SIGGRAPH '83).
  44.  
  45. 3.  Optimize register 0.  Find which of the register values found in step 2
  46. will give the lowest mean dimished distance from the pixels in the first
  47. column.  Put this in register 0, the order of the other registers doesn't
  48. matter, but I sort them.
  49.  
  50. 4.  Convert the image.  For each pixel, find the closest register color (using
  51. the ordinary distance formula).  Then find the dimished distance between this
  52. pixel and the one to its left (or register 0 if in the first column).  If
  53. the register distance is lower than the neighbor dimished distance, use that
  54. register to render this pixel, else use HAM.  This will use HAM in the case of
  55. a tie.
  56.  
  57. This algorithm >can< be coded in a very efficient manner.  It can also be a
  58. major waste if implemented poorly!  Be careful out there! :-)
  59.  
  60. If there is a set of registers that will display the picture properly, this
  61. algorithm will find it.  If there is not, the approximation is very close.
  62.  
  63. Yes, I've coded this, I use it, and I love it.  It is part of a general
  64. image resampler that I am writing for the Amiga.  It will convert IFF pictures
  65. of any size (aspect ratio, number of colors) (well, within the limits of the
  66. format, of course) to any other size (aspect ratio, number of colors).  I am
  67. using it to convert "real pictures" (512 x 512 x 24 bits) that I coded in
  68. IFF(!) into Amiga interlaced, overscanned, HAM pictures (also in IFF, natch).
  69. I hope to have this program all done by the end of the year.  I could
  70. probably get it done sooner with some effort, but so far nobody (except me)
  71. has been thrilled by it, so I left it half-baked on the back burner.
  72. Think it's marketable?  If so, be >sure< to get in touch with me! :-)
  73.  
  74. Responses to this article in this newsgroup might miss me, as I do not read it
  75. regularly.  Try mail or comp.graphics instead.
  76.  
  77. Allen Braunsdorf            WORK    k.cc.purdue.edu!ahg
  78. General Consultant            SCHOOL    ei.ecn.purdue.edu!braunsdo
  79. Purdue University Computing Center    HOME    ee.ecn.purdue.edu!gawk!akb
  80.