home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 6 / AACD06.ISO / AACD / System / Mesa-3.1 / src / AOS / palettes / TODO < prev   
Text File  |  1999-09-23  |  3KB  |  83 lines
  1. In <MPG.123f3c665cf4100a98969b@news.stormnet.com>, Kendall Bennett
  2. writes:
  3.  > I am trying to find out how to build the fastest algorithm to find the 
  4.  > closest RGB color in a palette. This function is used to convert pixels 
  5.  > on the fly from an RGB bitmap to a 256 color bitmap with a specific 
  6.  > palette (no dithering). Right now I am simply doing a search of all 256 
  7.  > entries in the palette and finding the one closest in color range  (ie: 
  8.  > ABS() of all color component differences is smallest).
  9.  
  10. To get a perfect Euclidean mapping to the palette, you could use
  11. Voronoi (sp?) polygons/polyhedra.  A Voronoi polygon is the polygon
  12. bounding the area that consists of all points that would map to the
  13. given palette entry.  Confused?
  14.  
  15.  +--Red-------------------A------+
  16. Green         | |                |
  17.  |           |   |               |  E bisects P2-P4
  18.  |   P1     |     H              B  F bisects P3-P4
  19.  |         |       |             |  G bisects P1-P3
  20.  |        |         |      P2    |  H bisects P2-P3
  21.  D       |           |           |
  22.  |      |     P3      |          |
  23.  |     |               ......E...|
  24.  |    G               -          |
  25.  |   |               -           |
  26.  |  |               -            |
  27.  | |               F       P4    |
  28.  ||               -              |
  29.  |               -               |
  30.  +-----------C-------------------+
  31.  
  32. For the four colour palette (P1-P4), in red & green only, the Voronoi
  33. polygons are:
  34.     V1 (for P1): AGD
  35.     V2 (for P2): ABEH
  36.     V3 (for P3): AHFCDF
  37.     V4 (for P4): EBCF
  38.  
  39. For any colour inside V1, if we did the Euclidean calculation
  40. (min(R-R' * G-G')), the closest palette colour would be P1.  For any
  41. colour outside V1, it would be some other palette colour.
  42.  
  43. Armed with the Voronoi polyhedra, we build a BSP tree.  Due to the
  44. alignment of the bounding surfaces (not orthogonal to the x, y, z (R,
  45. G, B) planes), we need to use non-aligned planes in the BSP tree.
  46. Even then, we will sever some polyhedra when bisecting space.  When
  47. we do, create two replacement polyhedra (V4' and V4" below).
  48.  
  49.  +--Red---------+     +---------A------+
  50. Green         | |     |                |
  51.  |           |   |     |               |
  52.  |   V1     |     H     |              B
  53.  |         |       |     |             |
  54.  |        |         |     |      V2    |
  55.  D       |           |     |           |
  56.  |      |     V3      |     |          |
  57.  |     |               |     |.....E...|
  58.  |    G               - |     |        |
  59.  |   |               -   |     |       |
  60.  |  |               -     |     |      |
  61.  | |               F       |     |  V4"|   /--- here
  62.  ||               -   V4'   |     |    |   \---
  63.  |               -           |     |   |
  64.  +-----------C---------------+     +---+
  65.  
  66. Repeat until every leaf contains only one polyhedron.  Now we have a
  67. BSP: but searched by dot-products (pixel vs plane), rather than the
  68. usual X or Y or Z calculation.
  69.  
  70. Pros:
  71.  * perfect Euclidean mapping to given palette;
  72.  * faster per pixel than exhaustive search;
  73.  
  74. Cons:
  75.  * Expensive to pre-process palette;
  76.  * Requires much more math knowledge than the simpler methods;
  77.  
  78. Edmund.
  79. -- 
  80. Edmund Stephen-Smith            ||  edmund@suave  ||
  81.                                 ||  .demon.co.uk  ||
  82.  
  83.