[80]  1  /********************************************************************** <BR>


 2  This file is part of Crack dot Com's free source code release of


 3  Golgotha. <a href="http://www.crack.com/golgotha_release"> <BR> for


 4  information about compiling & licensing issues visit this URL</a>


 5  <PRE> If that doesn't help, contact Jonathan Clark at


 6  golgotha_source@usa.net (Subject should have "GOLG" in it)


 7  ***********************************************************************/


 8 


 9  #include "arch.hh"


 10  #include "quantize/median.hh"


 11  #include "quantize/histogram.hh"


 12  #include <stdlib.h>


 13  #include "memory/malloc.hh"


 14 


 15  // counts for each color, global so that it can be accessed by qsort function


 16  static w32 *counts;


 17 


 18 


 19  static int red_compare(const void *a, const void *b)


 20  {


 21  w16 color1=counts[*((w16 *)a)],


 22  color2=counts[*((w16 *)b)];


 23 


 24  return ((sw32) ((color1 & ( (1  2  4  8  16) << 11))>>11))


 25  ((sw32) ((color2 & ( (1  2  4  8  16) << 11))>>11));


 26  }


 27 


 28 


 29  static int green_compare(const void *a, const void *b)


 30  {


 31  w16 color1=counts[*((w16 *)a)],


 32  color2=counts[*((w16 *)b)];


 33 


 34  return ((sw32) (color1 & ( (1  2  4  8  16  32) << 5)))


 35  ((sw32) (color2 & ( (1  2  4  8  16  32) << 5)));


 36  }


 37 


 38 


 39  static int blue_compare(const void *a, const void *b)


 40  {


 41  w16 color1=counts[*((w16 *)a)],


 42  color2=counts[*((w16 *)b)];


 43 


 44  return ((sw32) (color1 & ( (1  2  4  8  16) << 0)))


 45  ((sw32) (color2 & ( (1  2  4  8  16) << 0)));


 46  }


 47 


 48 


 49  struct box


 50  {


 51  w32 index;


 52  w32 colors;


 53  w32 sum;


 54  };


 55 


 56  static int box_compare(const void *a, const void *b)


 57  {


 58  return ((box *)b)>sum((box *)a)>sum;


 59  }


 60 


 61  inline void _16_to_rgb(w32 rgb, w8 &r, w8 &g, w8 &b)


 62  {


 63  b=(rgb & (1  2  4  8  16))<<3;


 64  rgb>>=5;


 65 


 66  g=(rgb & (1  2  4  8  16  32))<<2;


 67  rgb>>=6;


 68 


 69  r=(rgb & (1  2  4  8  16))<<3;


 70  }


 71 


 72  void i4_median_cut(i4_histogram_class *hist,


 73  w32 skip_colors,


 74  w32 t_colors,


 75  w32 *return_palette)


 76 


 77  {


 78  enum { HIST_SIZE=0x10000, // 16 bit histogram table


 79  MAX_COLORS=256 };


 80 


 81  counts=hist>counts;


 82 


 83  box *box_list=(box *)i4_malloc(sizeof(box) * MAX_COLORS, "boxes");


 84 


 85  // setup the initial box


 86  w32 total_boxes = 1;


 87  box_list[0].index = 0;


 88  box_list[0].colors = hist>tcolors;


 89  box_list[0].sum = hist>total_pixels;


 90 


 91  w32 box_index;


 92  w32 loop_count;


 93 


 94  // split boxes until we have all the colors


 95  while ( total_boxes < t_colorsskip_colors )


 96  {


 97  // Find the first splittable box.


 98  for ( box_index = 0; box_index < total_boxes; ++box_index )


 99  if (box_list[box_index].colors >= 2)


 100  break;


 101 


 102  if ( box_index == total_boxes)


 103  break; /* ran out of colors! */


 104 


 105 


 106  w32 start = box_list[box_index].index;


 107  w32 end = start + box_list[box_index].colors;


 108 


 109  w8 min_r=0xff, max_r=0x00,


 110  min_g=0xff, max_g=0x00,


 111  min_b=0xff, max_b=0x00,


 112  r,g,b;


 113 


 114 


 115  // now find the minimum and maximum r g b values for this box


 116  for (loop_count = start; loop_count<end; loop_count++)


 117  {


 118  _16_to_rgb(hist>reference[loop_count],r,g,b);


 119 


 120  if (r>max_r) max_r=r;


 121  if (r<min_r) min_r=r;


 122 


 123  if (g>max_g) max_g=g;


 124  if (g<min_g) min_g=g;


 125 


 126  if (b>max_b) max_b=b;


 127  if (b<min_b) min_b=b;


 128  }


 129 


 130 


 131  // Find the largest dimension, and sort by that component.


 132  if (((max_r  min_r) >= (max_g  min_g)) && ((max_r  min_r) >= (max_b  min_b)))


 133  qsort(hist>reference + start,


 134  endstart, // total elements to sort


 135  sizeof(w16),


 136  red_compare);


 137  else if ( (max_g  min_g) >= (max_b  min_b) )


 138  qsort(hist>reference + start,


 139  endstart, // total elements to sort


 140  sizeof(w16),


 141  green_compare);


 142  else


 143  qsort(hist>reference + start,


 144  endstart, // total elements to sort


 145  sizeof(w16),


 146  blue_compare);


 147 


 148 


 149 


 150  // now find the division which closest divides into an equal number of pixels


 151  w32 low_count= counts[hist>reference[start]];


 152  w32 mid_number=box_list[box_index].sum/2;


 153 


 154  for (loop_count = start+1; loop_count<end1 && low_count<mid_number ; loop_count++)


 155  low_count+=counts[hist>reference[loop_count]];


 156 


 157 


 158  // now split the box


 159  box_list[total_boxes].index = loop_count;


 160  box_list[total_boxes].colors = endloop_count;


 161  box_list[total_boxes].sum = box_list[box_index].sumlow_count;


 162  total_boxes++;


 163 


 164  box_list[box_index].colors= loop_countstart;


 165  box_list[box_index].sum = low_count;


 166 


 167  // sort to bring the biggest boxes to the top


 168  qsort(box_list, total_boxes, sizeof(box), box_compare );


 169 


 170  /* for (int z=0;z<total_boxes;z++)


 171  {


 172  printf("box #%d : index = %d, colors= %d, sum=%d\n",z,


 173  box_list[z].index, box_list[z].colors, box_list[z].sum);


 174  } */


 175 


 176  }


 177 


 178 


 179  // we should have 256 boxes, we now need to choose a color for each box


 180  // we do this by averaging all the colors within the box


 181  w32 r_tot, g_tot, b_tot;


 182  for (box_index = 0; box_index<total_boxesskip_colors; box_index++)


 183  {


 184  r_tot = g_tot = b_tot = 0;


 185 


 186  w32 start = box_list[box_index].index;


 187  w32 end = start + box_list[box_index].colors;


 188 


 189  w8 r,g,b;


 190  for (loop_count = start; loop_count < end; loop_count++)


 191  {


 192  _16_to_rgb(hist>reference[loop_count],r,g,b);


 193 


 194  r_tot+=r;


 195  g_tot+=g;


 196  b_tot+=b;


 197  }


 198 


 199  r_tot/=(endstart);


 200  g_tot/=(endstart);


 201  b_tot/=(endstart);


 202 


 203  return_palette[box_index+skip_colors] = (r_tot<<16)


 204  (g_tot<<8) 


 205  b_tot;


 206  }


 207 


 208  for (;box_index + skip_colors<t_colors; box_index++)


 209  return_palette[box_index+skip_colors] = 0;


 210 


 211 


 212  i4_free(box_list);


 213 


 214  }


 215 

