?  search:
summary | log | graphiclog1 | graphiclog2 | commit | commitdiff | tree | refs | edit | fork
blame | history | raw | HEAD
Initial import of Scalos. To decrease size I have
[AROS-Contrib.git] / scalos / libraries / scalosgfx / Dither.c
blobc2faabba310f5f31909fa6f644b1de4cc7225106
1 // Dither.c
2 // $Date$
3 // $Revision$
4
5
6 #include <exec/types.h>
7 #include <graphics/gels.h>
8 #include <graphics/rastport.h>
9 #include <graphics/scale.h>
10 #include <cybergraphx/cybergraphics.h>
11 #include <datatypes/datatypes.h>
12 #include <datatypes/pictureclass.h>
13 #include <datatypes/iconobject.h>
14 #include <libraries/mcpgfx.h>
15 #include <scalos/scalosgfx.h>
16
17 #define __USE_SYSBASE
18
19 #include <proto/dos.h>
20 #include <proto/exec.h>
21 #include <proto/graphics.h>
22 #include <proto/utility.h>
23 #include <proto/cybergraphics.h>
24 #include <proto/datatypes.h>
25 #include <proto/intuition.h>
26 #include <proto/scalos.h>
27
28 #include <clib/alib_protos.h>
29
30 #include <defs.h>
31
32 #include <string.h>
33 #include <stdio.h>
34 #include <stdarg.h>
35 #include <stdlib.h>
36 #include <limits.h>
37
38 #include "scalosgfx.h"
39
40 //-----------------------------------------------------------------------
41
42 #define HASH_SIZE 20023
43
44 #define MAXCOLORS 32767
45
46 /* #define LARGE_NORM */
47 #define LARGE_LUM
48
49 /* #define REP_CENTER_BOX */
50 /* #define REP_AVERAGE_COLORS */
51 #define REP_AVERAGE_PIXELS
52
53 //-----------------------------------------------------------------------
54
55 #define PPM_MAXMAXVAL PGM_MAXMAXVAL
56
57 #define PPM_GETR(p) ((p).Red)
58 #define PPM_GETG(p) ((p).Green)
59 #define PPM_GETB(p) ((p).Blue)
60
61 /************* added definitions *****************/
62
63 #define PPM_EQUAL(p,q) ( (p).Red == (q).Red \
64 && (p).Green == (q).Green \
65 && (p).Blue == (q).Blue )
66
67 /* Color scaling macro -- to make writing ppmtowhatever easier. */
68
69 #define PPM_DEPTH(newp, p, oldmaxval, newmaxval) \
70 (newp).Red = ( (int) (p).Red * (newmaxval) + (oldmaxval) / 2 ) / (oldmaxval); \
71 (newp).Green = ( (int) (p).Green * (newmaxval) + (oldmaxval) / 2 ) / (oldmaxval); \
72 (newp).Blue = ( (int) (p).Blue * (newmaxval) + (oldmaxval) / 2 ) / (oldmaxval)
73
74
75 /* Luminance macro. */
76
77 #define PPM_LUMIN(p) ( 0.299 * (p).Red + 0.587 * (p).Green + 0.114 * (p).Blue )
78
79 struct box
80 {
81 int ind;
82 int colors;
83 int sum;
84 };
85
86 /* Color histogram stuff. */
87
88 struct colorhist_item
89 {
90 struct ARGB color;
91 int value;
92 };
93
94 struct colorhist_list_item
95 {
96 struct colorhist_item ch;
97 struct colorhist_list_item * next;
98 };
99
100 struct longRGB
101 {
102 LONG Red;
103 LONG Green;
104 LONG Blue;
105 };
106
107 //-----------------------------------------------------------------------
108
109 static struct colorhist_item *mediancut( struct colorhist_item * chv, int colors,
110 int sum, ULONG maxval, int newcolors, struct ScalosGfxBase *ScalosGfxBase);
111 static int redcompare(const void *c1, const void *c2);
112 static int greencompare(const void *c1, const void *c2);
113 static int bluecompare(const void *c1, const void *c2);
114 static int sumcompare(const void *c1, const void *c2);
115 static long ppm_hashpixel(const struct ARGB *p);
116 static struct colorhist_item * ppm_computecolorhist(const struct ARGBHeader *argbh,
117 int maxcolors, int *colorsP, struct ScalosGfxBase *ScalosGfxBase);
118 static struct colorhist_list_item **ppm_computecolorhash(const struct ARGBHeader *argbh,
119 int maxcolors, int *colorsP, struct ScalosGfxBase *ScalosGfxBase);
120 static struct colorhist_list_item ** ppm_alloccolorhash(struct ScalosGfxBase *ScalosGfxBase);
121 static int ppm_addtocolorhash(struct colorhist_list_item **cht, const struct ARGB *colorP, int value, struct ScalosGfxBase *ScalosGfxBase);
122 static struct colorhist_item * ppm_colorhashtocolorhist(struct colorhist_list_item ** cht, int maxcolors, struct ScalosGfxBase *ScalosGfxBase);
123 static int ppm_lookupcolor(struct colorhist_list_item ** cht, const struct ARGB *colorP);
124 static void ppm_freecolorhist(struct colorhist_item * chv, struct ScalosGfxBase *ScalosGfxBase);
125 static void ppm_freecolorhash(struct colorhist_list_item ** cht, struct ScalosGfxBase *ScalosGfxBase);
126 static void *pm_allocrow(int cols, int size, struct ScalosGfxBase *ScalosGfxBase);
127 static void pm_freerow(void *itrow, struct ScalosGfxBase *ScalosGfxBase);
128
129 //-----------------------------------------------------------------------
130
131 /*
132 ** Copyright (C) 1989, 1991 by Jef Poskanzer.
133 **
134 ** Permission to use, copy, modify, and distribute this software and its
135 ** documentation for any purpose and without fee is hereby granted, provided
136 ** that the above copyright notice appear in all copies and that both that
137 ** copyright notice and this permission notice appear in supporting
138 ** documentation. This software is provided "as is" without express or
139 ** implied warranty.
140 */
141
142
143 struct ScalosBitMapAndColor *MedianCut(struct ARGBHeader *argbh,
144 ULONG Depth, ULONG newcolors,
145 BOOL floyd, struct BitMap *FriendBM,
146 struct ScalosGfxBase *ScalosGfxBase)
147 {
148 struct ScalosBitMapAndColor *sac = NULL;
149 struct ARGBHeader mappixels;
150 struct ARGB *pixels;
151 UBYTE *AllocPixelLine = NULL;
152 struct BitMap *TempBM = NULL;
153 int row;
154 int col, limitcol;
155 ULONG maxval, newmaxval;
156 int colors = 0;
157 int ind;
158 struct colorhist_item *chv = NULL;
159 struct colorhist_item *colormap = NULL;
160 struct colorhist_list_item **cht = NULL;
161 BOOL usehash;
162 struct longRGB *thiserr = NULL;
163 struct longRGB *nexterr = NULL;
164 #define FS_SCALE 1024
165 BOOL fs_direction = FALSE;
166 BOOL Success = FALSE;
167
168 d1(KPrintF(__FILE__ "/" "%s/%ld: START w=%ld h=%ld floyd=%ld\n", \
169 __LINE__, argbh->argb_Width, argbh->argb_Height, floyd));
170
171 d1(KPrintF(__FILE__ "/" "%s/%ld: argb_ImageData: A=%ld R=%ld G=%ld B=%ld\n", \
172 __LINE__, argbh->argb_ImageData->Alpha, \
173 argbh->argb_ImageData->Red, argbh->argb_ImageData->Green, \
174 argbh->argb_ImageData->Blue));
175
176 do {
177 ULONG *pColorTable;
178 struct RastPort rp;
179 struct RastPort TempRp;
180 struct longRGB s = { 0, 0, 0 };
181
182 InitRastPort(&rp);
183 InitRastPort(&TempRp);
184
185 memset(&mappixels, 0, sizeof(mappixels));
186
187 if (newcolors < 2)
188 {
189 d1(KPrintF(__FILE__ "/" "%s/%ld:number of colors must be > 2\n", __FUNC__, __LINE__));
190 break;
191 }
192 if (newcolors > 256)
193 {
194 d1(KPrintF(__FILE__ "/" "%s/%ld:number of colors must be < 256\n", __FUNC__, __LINE__));
195 break;
196 }
197
198 maxval = 255;
199
200 sac = AllocSAC(argbh->argb_Width, argbh->argb_Height, Depth, FriendBM, NULL, ScalosGfxBase);
201 if (NULL == sac)
202 break;
203
204 sac->sac_TransparentColor = SAC_TRANSPARENT_NONE;
205
206 rp.BitMap = sac->sac_BitMap;
207 d1(KPrintF(__FILE__ "/" "%s/%ld: rp.BitMap=%08lx\n", __FUNC__, __LINE__, rp.BitMap));
208
209 // setup temp. RastPort for use by WritePixelLine8()
210 TempRp.Layer = NULL;
211 TempRp.BitMap = TempBM = AllocBitMap(TEMPRP_WIDTH(argbh->argb_Width), 1, 8, 0, NULL);
212 if (NULL == TempBM)
213 break;
214
215 // allocate pens for 1 line (1 byte per pixel)
216 AllocPixelLine = ScalosGfxAllocVecPooled(ScalosGfxBase, ((argbh->argb_Width + 15) >> 4) << 4);
217 if (NULL == AllocPixelLine)
218 break;
219
220 /*
221 ** Step 2: attempt to make a histogram of the colors, unclustered.
222 ** If at first we don't succeed, lower maxval to increase color
223 ** coherence and try again. This will eventually terminate, with
224 ** maxval at worst 15, since 32^3 is approximately MAXCOLORS.
225 */
226 for ( ; ; )
227 {
228 d1(KPrintF(__FILE__ "/" "%s/%ld: making histogram...\n", __FUNC__, __LINE__));
229 chv = ppm_computecolorhist(argbh, MAXCOLORS, &colors, ScalosGfxBase);
230 if ( chv != (struct colorhist_item *) NULL )
231 break;
232
233 d1(KPrintF(__FILE__ "/" "%s/%ld: too many colors!\n", __FUNC__, __LINE__));
234
235 newmaxval = maxval / 2;
236 d1(KPrintF(__FILE__ "/" "%s/%ld: scaling colors from maxval=%d to maxval=%d to improve clustering...\n",
237 __LINE__, maxval, newmaxval));
238 for ( row = 0, pixels = argbh->argb_ImageData;
239 row < argbh->argb_Height;
240 ++row, pixels += argbh->argb_Width)
241 {
242 struct ARGB *pP = pixels;
243 for ( col = 0; col < argbh->argb_Width; ++col, ++pP )
244 {
245 PPM_DEPTH(*pP, *pP, maxval, newmaxval);
246 }
247 }
248 maxval = newmaxval;
249 }
250 d1(KPrintF(__FILE__ "/" "%s/%ld: %d colors found\n", __FUNC__, __LINE__, colors));
251
252 /*
253 ** Step 3: apply median-cut to histogram, making the new colormap.
254 */
255 d1(KPrintF(__FILE__ "/" "%s/%ld: choosing %d colors...\n", __FUNC__, __LINE__, newcolors));
256 colormap = mediancut( chv, colors, argbh->argb_Height * argbh->argb_Width, maxval, newcolors, ScalosGfxBase );
257 if (NULL == colormap)
258 break;
259
260 d1(KPrintF(__FILE__ "/" "%s/%ld: colormap: %08lx %08lx %08lx %08lx\n", \
261 __LINE__, *((ULONG *) &colormap[0].color), \
262 *((ULONG *) &colormap[1].color), \
263 *((ULONG *) &colormap[2].color), \
264 *((ULONG *) &colormap[3].color)));
265
266 /*
267 ** Step 4: map the colors in the image to their closest match in the
268 ** new colormap, and write 'em out.
269 */
270 d1(KPrintF(__FILE__ "/" "%s/%ld: mapping image to new colors...\n", __FUNC__, __LINE__));
271 cht = ppm_alloccolorhash(ScalosGfxBase);
272 d1(KPrintF(__FILE__ "/" "%s/%ld: cht=%08lx\n", __FUNC__, __LINE__, cht));
273 if (NULL == cht)
274 break;
275
276 usehash = TRUE;
277 //+++ ppm_writeppminit( stdout, argbh->argb_Width, argbh->argb_Height, maxval, 0 );
278 if ( floyd )
279 {
280 struct DateStamp ds;
281
282 /* Initialize Floyd-Steinberg error vectors. */
283 thiserr = (struct longRGB *) pm_allocrow( argbh->argb_Width + 2, sizeof(struct longRGB), ScalosGfxBase);
284 if (NULL == thiserr)
285 break;
286 nexterr = (struct longRGB *) pm_allocrow( argbh->argb_Width + 2, sizeof(struct longRGB), ScalosGfxBase );
287 if (NULL == nexterr)
288 break;
289
290 DateStamp(&ds);
291 srand(ds.ds_Tick);
292
293 d1(KPrintF(__FILE__ "/" "%s/%ld: thiserr=%08lx nexterr=%08lx\n", \
294 __LINE__, thiserr, nexterr));
295
296 for ( col = 0; col < argbh->argb_Width + 2; ++col )
297 {
298 thiserr[col].Red = rand() % ( FS_SCALE * 2 ) - FS_SCALE;
299 thiserr[col].Green = rand() % ( FS_SCALE * 2 ) - FS_SCALE;
300 thiserr[col].Blue = rand() % ( FS_SCALE * 2 ) - FS_SCALE;
301 /* (random errors in [-1 .. 1]) */
302 d1(KPrintF(__FILE__ "/" "%s/%ld: F/S error[%ld]: R=%08lx G=%08lx B=%08lx\n", \
303 __LINE__, col, thiserr[col].Red, thiserr[col].Green, thiserr[col].Blue));
304 }
305
306 fs_direction = TRUE;
307 }
308
309 d1(KPrintF(__FILE__ "/" "%s/%ld: \n", __FUNC__, __LINE__));
310
311 for ( row = 0, pixels = argbh->argb_ImageData;
312 row < argbh->argb_Height;
313 ++row, pixels += argbh->argb_Width)
314 {
315 UBYTE *pPixelLine;
316 struct ARGB *pP;
317
318 d1(KPrintF(__FILE__ "/" "%s/%ld: row=%ld pixels=%08lx\n", __FUNC__, __LINE__, row, pixels));
319
320 if ( floyd )
321 {
322 for ( col = 0; col < argbh->argb_Width + 2; ++col )
323 nexterr[col].Red = nexterr[col].Green = nexterr[col].Blue = 0;
324 }
325 if ( ( ! floyd ) || fs_direction )
326 {
327 col = 0;
328 limitcol = argbh->argb_Width;
329 pP = pixels;
330 pPixelLine = AllocPixelLine;
331 }
332 else
333 {
334 col = argbh->argb_Width - 1;
335 limitcol = -1;
336 pP = pixels + col;
337 pPixelLine = AllocPixelLine + col;
338 }
339
340 d1(KPrintF(__FILE__ "/" "%s/%ld: pP=%08lx\n", __FUNC__, __LINE__, pP));
341
342 do {
343 if ( floyd )
344 {
345 /* Use Floyd-Steinberg errors to adjust actual color. */
346 d1(KPrintF(__FILE__ "/" "%s/%ld: thiserr[%ld]: R=%4ld G=%4ld B=%4ld\n", \
347 __LINE__, col + 1, thiserr[col + 1].Red, thiserr[col + 1].Green, thiserr[col + 1].Blue));
348
349 s.Red = pP->Red + thiserr[col + 1].Red / FS_SCALE;
350 s.Green = pP->Green + thiserr[col + 1].Green / FS_SCALE;
351 s.Blue = pP->Blue + thiserr[col + 1].Blue / FS_SCALE;
352
353 if ( s.Red < 0 )
354 s.Red = 0;
355 else if ( s.Red > maxval )
356 s.Red = maxval;
357 if ( s.Green < 0 )
358 s.Green = 0;
359 else if ( s.Green > maxval )
360 s.Green = maxval;
361 if ( s.Blue < 0 )
362 s.Blue = 0;
363 else if ( s.Blue > maxval )
364 s.Blue = maxval;
365
366 d1(KPrintF(__FILE__ "/" "%s/%ld: Red=%3d s.Red=%ld\n", __FUNC__, __LINE__, pP->Red, s.Red));
367 d1(KPrintF(__FILE__ "/" "%s/%ld: Green=%3d s.Green=%ld\n", __FUNC__, __LINE__, pP->Green, s.Green));
368 d1(KPrintF(__FILE__ "/" "%s/%ld: Blue=%3d s.Blue=%ld\n", __FUNC__, __LINE__, pP->Blue, s.Blue));
369
370 pP->Red = s.Red;
371 pP->Green = s.Green;
372 pP->Blue = s.Blue;
373 }
374
375 /* Check hash table to see if we have already matched this color. */
376 ind = ppm_lookupcolor( cht, pP );
377 d1(KPrintF(__FILE__ "/" "%s/%ld: ind=%ld\n", __FUNC__, __LINE__, ind));
378 if ( ind == -1 )
379 {
380 /* No; search colormap for closest match. */
381 int i, r1, g1, b1;
382 long dist;
383
384 r1 = pP->Red;
385 g1 = pP->Green;
386 b1 = pP->Blue;
387 dist = LONG_MAX;
388 for ( i = 0; i < newcolors; ++i )
389 {
390 int r2, g2, b2;
391 long newdist;
392
393 r2 = colormap[i].color.Red;
394 g2 = colormap[i].color.Green;
395 b2 = colormap[i].color.Blue;
396
397 newdist = ( r1 - r2 ) * ( r1 - r2 ) +
398 ( g1 - g2 ) * ( g1 - g2 ) +
399 ( b1 - b2 ) * ( b1 - b2 );
400 if ( newdist < dist )
401 {
402 ind = i;
403 dist = newdist;
404 }
405 }
406 if ( usehash )
407 {
408 if ( ppm_addtocolorhash( cht, pP, ind, ScalosGfxBase) < 0 )
409 {
410 d1(KPrintF(__FILE__ "/" "%s/%ld: out of memory adding to hash table, proceeding without it\n", __FUNC__, __LINE__));
411 usehash = FALSE;
412 }
413 }
414 }
415
416 if ( floyd )
417 {
418 /* Propagate Floyd-Steinberg error terms. */
419 long err;
420
421 if ( fs_direction )
422 {
423 err = (s.Red - (long) colormap[ind].color.Red) * FS_SCALE;
424 d1(KPrintF(__FILE__ "/" "%s/%ld: Red err=%ld\n", __FUNC__, __LINE__, err));
425 thiserr[col + 2].Red += ( err * 7 ) / 16;
426 nexterr[col ].Red += ( err * 3 ) / 16;
427 nexterr[col + 1].Red += ( err * 5 ) / 16;
428 nexterr[col + 2].Red += ( err ) / 16;
429 err = (s.Green - (long) colormap[ind].color.Green) * FS_SCALE;
430 d1(KPrintF(__FILE__ "/" "%s/%ld: Green err=%ld\n", __FUNC__, __LINE__, err));
431 thiserr[col + 2].Green += ( err * 7 ) / 16;
432 nexterr[col ].Green += ( err * 3 ) / 16;
433 nexterr[col + 1].Green += ( err * 5 ) / 16;
434 nexterr[col + 2].Green += ( err ) / 16;
435 err = (s.Blue - (long) colormap[ind].color.Blue) * FS_SCALE;
436 d1(KPrintF(__FILE__ "/" "%s/%ld: Blue err=%ld\n", __FUNC__, __LINE__, err));
437 thiserr[col + 2].Blue += ( err * 7 ) / 16;
438 nexterr[col ].Blue += ( err * 3 ) / 16;
439 nexterr[col + 1].Blue += ( err * 5 ) / 16;
440 nexterr[col + 2].Blue += ( err ) / 16;
441 }
442 else
443 {
444 err = (s.Red - (long) colormap[ind].color.Red) * FS_SCALE;
445 d1(KPrintF(__FILE__ "/" "%s/%ld: Red err=%ld\n", __FUNC__, __LINE__, err));
446 thiserr[col ].Red += ( err * 7 ) / 16;
447 nexterr[col + 2].Red += ( err * 3 ) / 16;
448 nexterr[col + 1].Red += ( err * 5 ) / 16;
449 nexterr[col ].Red += ( err ) / 16;
450 err = (s.Green - (long) colormap[ind].color.Green) * FS_SCALE;
451 d1(KPrintF(__FILE__ "/" "%s/%ld: Green err=%ld\n", __FUNC__, __LINE__, err));
452 thiserr[col ].Green += ( err * 7 ) / 16;
453 nexterr[col + 2].Green += ( err * 3 ) / 16;
454 nexterr[col + 1].Green += ( err * 5 ) / 16;
455 nexterr[col ].Green += ( err ) / 16;
456 err = (s.Blue - (long) colormap[ind].color.Blue) * FS_SCALE;
457 d1(KPrintF(__FILE__ "/" "%s/%ld: Blue err=%ld\n", __FUNC__, __LINE__, err));
458 thiserr[col ].Blue += ( err * 7 ) / 16;
459 nexterr[col + 2].Blue += ( err * 3 ) / 16;
460 nexterr[col + 1].Blue += ( err * 5 ) / 16;
461 nexterr[col ].Blue += ( err ) / 16;
462 }
463 }
464
465 pP->Red = colormap[ind].color.Red;
466 pP->Green = colormap[ind].color.Green;
467 pP->Blue = colormap[ind].color.Blue;
468
469 // Check transparency, and set color index to 0 for transparent pixels
470 if (pP->Alpha >= 128)
471 *pPixelLine = 1 + ind;
472 else
473 {
474 // mark this pixel as transparent
475 *pPixelLine = sac->sac_TransparentColor = 0;
476 }
477
478 d1(KPrintF(__FILE__ "/" "%s/%ld: row=%ld col=%ld ind=%ld color=%08lx\n", \
479 __LINE__, row, col, ind, *((ULONG *) pP)));
480
481 if ( ( ! floyd ) || fs_direction )
482 {
483 ++col;
484 ++pP;
485 ++pPixelLine;
486 }
487 else
488 {
489 --col;
490 --pP;
491 --pPixelLine;
492 }
493 } while ( col != limitcol );
494
495 if ( floyd )
496 {
497 struct longRGB *temperr;
498
499 temperr = thiserr;
500 thiserr = nexterr;
501 nexterr = temperr;
502 fs_direction = !fs_direction;
503 }
504
505 d1(KPrintF(__FILE__ "/" "%s/%ld: row=%ld\n", __FUNC__, __LINE__, row));
506
507 WritePixelLine8(&rp, 0, row,
508 argbh->argb_Width, AllocPixelLine, &TempRp);
509 }
510
511 d1(KPrintF(__FILE__ "/" "%s/%ld: \n", __FUNC__, __LINE__));
512
513 // fill sac_ColorTable
514 // leave first entry in sac_ColorTable free since
515 // it is used as transparency indicator
516 for (ind = 0, pColorTable = sac->sac_ColorTable + 3;
517 ind < sac->sac_NumColors - 1; ind++)
518 {
519 *pColorTable++ = colormap[ind].color.Red << 24;
520 *pColorTable++ = colormap[ind].color.Green << 24;
521 *pColorTable++ = colormap[ind].color.Blue << 24;
522 }
523 Success = TRUE;
524 } while (0);
525
526 d1(KPrintF(__FILE__ "/" "%s/%ld: \n", __FUNC__, __LINE__));
527
528 if (!Success)
529 FreeSAC(sac, ScalosGfxBase);
530 if (colormap)
531 ScalosGfxFreeVecPooled(ScalosGfxBase, colormap);
532 if (cht)
533 ppm_freecolorhash(cht, ScalosGfxBase);
534 if (chv)
535 ppm_freecolorhist( chv, ScalosGfxBase);
536 if (thiserr)
537 pm_freerow(thiserr, ScalosGfxBase);
538 if (nexterr)
539 pm_freerow(nexterr, ScalosGfxBase);
540 if (AllocPixelLine)
541 ScalosGfxFreeVecPooled(ScalosGfxBase, AllocPixelLine);
542 if (TempBM)
543 FreeBitMap(TempBM);
544
545 d1(KPrintF(__FILE__ "/" "%s/%ld: END Success=%ld\n", __FUNC__, __LINE__, Success));
546
547 return sac;
548 }
549
550
551 /*
552 ** Here is the fun part, the median-cut colormap generator. This is based
553 ** on Paul Heckbert's paper "Color Image Quantization for Frame Buffer
554 ** Display", SIGGRAPH '82 Proceedings, page 297.
555 */
556 static struct colorhist_item *mediancut( struct colorhist_item * chv,
557 int colors, int sum, ULONG maxval, int newcolors,
558 struct ScalosGfxBase *ScalosGfxBase )
559 {
560 struct colorhist_item * colormap;
561 struct box * bv;
562 int bi, i;
563 int boxes;
564
565 bv = (struct box *) ScalosGfxAllocVecPooled(ScalosGfxBase, sizeof(struct box) * newcolors );
566 colormap = (struct colorhist_item *) ScalosGfxAllocVecPooled(ScalosGfxBase, sizeof(struct colorhist_item) * newcolors );
567
568 if (bv == NULL || colormap == NULL)
569 {
570 d1(KPrintF(__FILE__ "/" "%s/%ld: out of memory\n", __FUNC__, __LINE__));
571 return NULL;
572 }
573
574 for ( i = 0; i < newcolors; ++i )
575 {
576 colormap[i].color.Alpha = 0xff;
577 colormap[i].color.Red = 0;
578 colormap[i].color.Green = 0;
579 colormap[i].color.Blue = 0;
580 }
581
582 /*
583 ** Set up the initial box.
584 */
585 bv[0].ind = 0;
586 bv[0].colors = colors;
587 bv[0].sum = sum;
588 boxes = 1;
589
590 /*
591 ** Main loop: split boxes until we have enough.
592 */
593 while ( boxes < newcolors )
594 {
595 int indx, clrs;
596 int sm;
597 int minr, maxr, ming, maxg, minb, maxb, v;
598 int halfsum, lowersum;
599
600 /*
601 ** Find the first splittable box.
602 */
603 for ( bi = 0; bi < boxes; ++bi )
604 {
605 if ( bv[bi].colors >= 2 )
606 break;
607 }
608 if ( bi == boxes )
609 break; /* ran out of colors! */
610
611 indx = bv[bi].ind;
612 clrs = bv[bi].colors;
613 sm = bv[bi].sum;
614
615 /*
616 ** Go through the box finding the minimum and maximum of each
617 ** component - the boundaries of the box.
618 */
619 minr = maxr = chv[indx].color.Red;
620 ming = maxg = chv[indx].color.Green;
621 minb = maxb = chv[indx].color.Blue;
622
623 for ( i = 1; i < clrs; ++i )
624 {
625 v = chv[indx + i].color.Red;
626 if ( v < minr )
627 minr = v;
628 if ( v > maxr )
629 maxr = v;
630 v = chv[indx + i].color.Green;
631 if ( v < ming )
632 ming = v;
633 if ( v > maxg )
634 maxg = v;
635 v = chv[indx + i].color.Blue;
636 if ( v < minb )
637 minb = v;
638 if ( v > maxb )
639 maxb = v;
640 }
641
642 /*
643 ** Find the largest dimension, and sort by that component. I have
644 ** included two methods for determining the "largest" dimension;
645 ** first by simply comparing the range in RGB space, and second
646 ** by transforming into luminosities before the comparison. You
647 ** can switch which method is used by switching the commenting on
648 ** the LARGE_ defines at the beginning of this source file.
649 */
650 #ifdef LARGE_NORM
651 if ( maxr - minr >= maxg - ming && maxr - minr >= maxb - minb )
652 qsort((char*) &(chv[indx]), clrs, sizeof(struct colorhist_item), redcompare );
653 else if ( maxg - ming >= maxb - minb )
654 qsort((char*) &(chv[indx]), clrs, sizeof(struct colorhist_item), greencompare );
655 else
656 qsort((char*) &(chv[indx]), clrs, sizeof(struct colorhist_item), bluecompare );
657 #endif /*LARGE_NORM*/
658
659 #ifdef LARGE_LUM
660 {
661 struct ARGB p;
662 float rl, gl, bl;
663
664 p.Red = maxr - minr;
665 p.Green = 0;
666 p.Blue = 0;
667
668 rl = PPM_LUMIN(p);
669
670 p.Red = 0;
671 p.Green = maxg - ming;
672 p.Blue = 0;
673 gl = PPM_LUMIN(p);
674
675 p.Red = 0;
676 p.Green = 0;
677 p.Blue = maxb - minb;
678 bl = PPM_LUMIN(p);
679
680 if ( rl >= gl && rl >= bl )
681 qsort((char*) &(chv[indx]), clrs, sizeof(struct colorhist_item), redcompare );
682 else if ( gl >= bl )
683 qsort((char*) &(chv[indx]), clrs, sizeof(struct colorhist_item), greencompare );
684 else
685 qsort((char*) &(chv[indx]), clrs, sizeof(struct colorhist_item), bluecompare );
686 }
687 #endif /*LARGE_LUM*/
688
689 /*
690 ** Now find the median based on the counts, so that about half the
691 ** pixels (not colors, pixels) are in each subdivision.
692 */
693 lowersum = chv[indx].value;
694 halfsum = sm / 2;
695 for ( i = 1; i < clrs - 1; ++i )
696 {
697 if ( lowersum >= halfsum )
698 break;
699 lowersum += chv[indx + i].value;
700 }
701
702 /*
703 ** Split the box, and sort to bring the biggest boxes to the top.
704 */
705 bv[bi].colors = i;
706 bv[bi].sum = lowersum;
707 bv[boxes].ind = indx + i;
708 bv[boxes].colors = clrs - i;
709 bv[boxes].sum = sm - lowersum;
710 ++boxes;
711
712 qsort( (char*) bv, boxes, sizeof(struct box), sumcompare );
713 }
714
715 /*
716 ** Ok, we've got enough boxes. Now choose a representative color for
717 ** each box. There are a number of possible ways to make this choice.
718 ** One would be to choose the center of the box; this ignores any structure
719 ** within the boxes. Another method would be to average all the colors in
720 ** the box - this is the method specified in Heckbert's paper. A third
721 ** method is to average all the pixels in the box. You can switch which
722 ** method is used by switching the commenting on the REP_ defines at
723 ** the beginning of this source file.
724 */
725 for ( bi = 0; bi < boxes; ++bi )
726 {
727 #ifdef REP_CENTER_BOX
728 int indx = bv[bi].ind;
729 int clrs = bv[bi].colors;
730 int minr, maxr, ming, maxg, minb, maxb, v;
731
732 minr = maxr = chv[indx].color.Red;
733 ming = maxg = chv[indx].color.Green;
734 minb = maxb = chv[indx].color.Blue;
735 for ( i = 1; i < clrs; ++i )
736 {
737 v = chv[indx + i].color.Red;
738 minr = min( minr, v );
739 maxr = max( maxr, v );
740 v = chv[indx + i].color.Green;
741 ming = min( ming, v );
742 maxg = max( maxg, v );
743 v = chv[indx + i].color.Blue;
744 minb = min( minb, v );
745 maxb = max( maxb, v );
746 }
747
748 colormap[bi].color.Red = (minr + maxr) / 2;
749 colormap[bi].color.Green = (ming + maxg) / 2;
750 colormap[bi].color.Blue = (minb + maxb) / 2;
751
752 #endif /*REP_CENTER_BOX*/
753 #ifdef REP_AVERAGE_COLORS
754 int indx = bv[bi].ind;
755 int clrs = bv[bi].colors;
756 long r = 0, g = 0, b = 0;
757
758 for ( i = 0; i < clrs; ++i )
759 {
760 r += chv[indx + i].color.Red;
761 g += chv[indx + i].color.Green;
762 b += chv[indx + i].color.Blue;
763 }
764 colormap[bi].color.Red = r / clrs;
765 colormap[bi].color.Green = g / clrs;
766 colormap[bi].color.Blue = b / clrs;
767 #endif /*REP_AVERAGE_COLORS*/
768
769 #ifdef REP_AVERAGE_PIXELS
770 int indx = bv[bi].ind;
771 int clrs = bv[bi].colors;
772 long r = 0, g = 0, b = 0, sum = 0;
773
774 for ( i = 0; i < clrs; ++i )
775 {
776 r += chv[indx + i].color.Red * chv[indx + i].value;
777 g += chv[indx + i].color.Green * chv[indx + i].value;
778 b += chv[indx + i].color.Blue * chv[indx + i].value;
779 sum += chv[indx + i].value;
780 }
781 r = r / sum;
782 if ( r > maxval )
783 r = maxval; /* avoid math errors */
784 g = g / sum;
785 if ( g > maxval )
786 g = maxval;
787 b = b / sum;
788 if ( b > maxval )
789 b = maxval;
790
791 colormap[bi].color.Red = r;
792 colormap[bi].color.Green = g;
793 colormap[bi].color.Blue = b;
794 #endif /*REP_AVERAGE_PIXELS*/
795 }
796
797 /*
798 ** All done.
799 */
800
801 ScalosGfxFreeVecPooled(ScalosGfxBase, (char*) bv); //+++
802
803 return colormap;
804 }
805
806 static int redcompare(const void *c1, const void *c2)
807 {
808 const struct colorhist_item * ch1 = c1;
809 const struct colorhist_item * ch2 = c2;
810
811 return (int) (ch1->color.Red - ch2->color.Red);
812 }
813
814 static int greencompare(const void *c1, const void *c2)
815 {
816 const struct colorhist_item * ch1 = c1;
817 const struct colorhist_item * ch2 = c2;
818
819 return (int) (ch1->color.Green - ch2->color.Green);
820 }
821
822 static int bluecompare(const void *c1, const void *c2)
823 {
824 const struct colorhist_item * ch1 = c1;
825 const struct colorhist_item * ch2 = c2;
826
827 return (int) (ch1->color.Blue - ch2->color.Blue);
828 }
829
830 static int sumcompare(const void *c1, const void *c2)
831 {
832 const struct box *b1 = c1;
833 const struct box *b2 = c2;
834
835 return b2->sum - b1->sum;
836 }
837
838
839 static long ppm_hashpixel(const struct ARGB *p)
840 {
841 return (long) ((p->Red * 33023 + p->Green * 30013 + p->Blue * 27011) & 0x7fffffff ) % HASH_SIZE;
842 }
843
844
845 static struct colorhist_item * ppm_computecolorhist(const struct ARGBHeader *argbh,
846 int maxcolors, int *colorsP, struct ScalosGfxBase *ScalosGfxBase)
847 {
848 struct colorhist_list_item ** cht;
849 struct colorhist_item * chv;
850
851 cht = ppm_computecolorhash(argbh, maxcolors, colorsP, ScalosGfxBase);
852 if ( cht == (struct colorhist_list_item **) 0 )
853 return (struct colorhist_item *) 0;
854
855 chv = ppm_colorhashtocolorhist( cht, maxcolors, ScalosGfxBase);
856 ppm_freecolorhash( cht, ScalosGfxBase );
857
858 return chv;
859 }
860
861
862 static struct colorhist_list_item ** ppm_computecolorhash(const struct ARGBHeader *argbh,
863 int maxcolors, int *colorsP, struct ScalosGfxBase *ScalosGfxBase)
864 {
865 struct colorhist_list_item ** cht;
866 struct colorhist_list_item * chl;
867 int row;
868 const struct ARGB *argb = argbh->argb_ImageData;
869
870 cht = ppm_alloccolorhash(ScalosGfxBase);
871 *colorsP = 0;
872
873 /* Go through the entire image, building a hash table of colors. */
874 for (row = 0; row < argbh->argb_Height; ++row)
875 {
876 int col;
877 const struct ARGB *pP = argb;
878
879 argb += argbh->argb_Width;
880
881 for (col = 0; col < argbh->argb_Width; ++col, ++pP)
882 {
883 int hash;
884
885 hash = ppm_hashpixel(pP);
886
887 for ( chl = cht[hash]; chl != NULL; chl = chl->next )
888 {
889 if ( PPM_EQUAL( chl->ch.color, *pP ) )
890 break;
891 }
892
893 if ( chl != NULL)
894 ++(chl->ch.value);
895 else
896 {
897 if ( ++(*colorsP) > maxcolors )
898 {
899 ppm_freecolorhash( cht, ScalosGfxBase );
900 return NULL;
901 }
902 chl = (struct colorhist_list_item *) ScalosGfxAllocVecPooled(ScalosGfxBase, sizeof(struct colorhist_list_item) );
903 if ( chl == 0 )
904 {
905 d1(KPrintF(__FILE__ "/" "%s/%ld: out of memory computing hash table\n", __FUNC__, __LINE__));
906 return NULL;
907 }
908 chl->ch.color = *pP;
909 chl->ch.value = 1;
910 chl->next = cht[hash];
911 cht[hash] = chl;
912 }
913 }
914 }
915
916 return cht;
917 }
918
919
920 static struct colorhist_list_item ** ppm_alloccolorhash(struct ScalosGfxBase *ScalosGfxBase)
921 {
922 struct colorhist_list_item ** cht;
923 int i;
924
925 cht = (struct colorhist_list_item **) ScalosGfxAllocVecPooled(ScalosGfxBase, HASH_SIZE * sizeof(struct colorhist_list_item *) );
926 if (NULL == cht)
927 {
928 d1(KPrintF(__FILE__ "/" "%s/%ld: out of memory allocating hash table\n", __FUNC__, __LINE__));
929 return NULL;
930 }
931
932 for ( i = 0; i < HASH_SIZE; ++i )
933 cht[i] = NULL;
934
935 return cht;
936 }
937
938
939 static int ppm_addtocolorhash(struct colorhist_list_item **cht, const struct ARGB *colorP, int value, struct ScalosGfxBase *ScalosGfxBase)
940 {
941 int hash;
942 struct colorhist_list_item * chl;
943
944 chl = (struct colorhist_list_item *) ScalosGfxAllocVecPooled(ScalosGfxBase, sizeof(struct colorhist_list_item) );
945 if (NULL == chl)
946 return -1;
947 hash = ppm_hashpixel(colorP);
948 chl->ch.color = *colorP;
949 chl->ch.value = value;
950 chl->next = cht[hash];
951 cht[hash] = chl;
952
953 return 0;
954 }
955
956
957 static struct colorhist_item * ppm_colorhashtocolorhist(struct colorhist_list_item ** cht, int maxcolors, struct ScalosGfxBase *ScalosGfxBase)
958 {
959 struct colorhist_item * chv;
960 struct colorhist_list_item * chl;
961 int i, j;
962
963 /* Now collate the hash table into a simple colorhist array. */
964 chv = (struct colorhist_item *) ScalosGfxAllocVecPooled(ScalosGfxBase, maxcolors * sizeof(struct colorhist_item) );
965 /* (Leave room for expansion by caller.) */
966 if (NULL == chv)
967 {
968 d1(KPrintF(__FILE__ "/" "%s/%ld: out of memory generating histogram\n", __FUNC__, __LINE__));
969 return NULL;
970 }
971
972 /* Loop through the hash table. */
973 j = 0;
974 for ( i = 0; i < HASH_SIZE; ++i )
975 {
976 for ( chl = cht[i]; chl != (struct colorhist_list_item *) 0; chl = chl->next )
977 {
978 /* Add the new entry. */
979 chv[j] = chl->ch;
980 ++j;
981 }
982 }
983
984 /* All done. */
985 return chv;
986 }
987
988
989 static int ppm_lookupcolor(struct colorhist_list_item ** cht, const struct ARGB *colorP)
990 {
991 int hash;
992 struct colorhist_list_item * chl;
993
994 hash = ppm_hashpixel(colorP);
995
996 for ( chl = cht[hash]; chl != (struct colorhist_list_item *) 0; chl = chl->next )
997 {
998 if ( PPM_EQUAL( chl->ch.color, *colorP ) )
999 return chl->ch.value;
1000 }
1001
1002 return -1;
1003 }
1004
1005
1006 static void ppm_freecolorhist(struct colorhist_item *chv, struct ScalosGfxBase *ScalosGfxBase)
1007 {
1008 ScalosGfxFreeVecPooled(ScalosGfxBase, (char*) chv );
1009 }
1010
1011
1012 static void ppm_freecolorhash(struct colorhist_list_item **cht, struct ScalosGfxBase *ScalosGfxBase)
1013 {
1014 int i;
1015 struct colorhist_list_item *chl, *chlnext;
1016
1017 for ( i = 0; i < HASH_SIZE; ++i )
1018 {
1019 for ( chl = cht[i]; chl != NULL; chl = chlnext )
1020 {
1021 chlnext = chl->next;
1022 ScalosGfxFreeVecPooled(ScalosGfxBase, (char*) chl );
1023 }
1024 }
1025 ScalosGfxFreeVecPooled(ScalosGfxBase, (char*) cht );
1026 }
1027
1028
1029 static void *pm_allocrow(int cols, int size, struct ScalosGfxBase *ScalosGfxBase)
1030 {
1031 void *itrow;
1032
1033 itrow = ScalosGfxAllocVecPooled(ScalosGfxBase, cols * size );
1034 if (NULL == itrow)
1035 d1(KPrintF(__FILE__ "/" "%s/%ld: out of memory allocating a row\n", __FUNC__, __LINE__));
1036
1037 return itrow;
1038 }
1039
1040
1041 static void pm_freerow(void *itrow, struct ScalosGfxBase *ScalosGfxBase)
1042 {
1043 ScalosGfxFreeVecPooled(ScalosGfxBase, itrow );
1044 }
1045
Mirror of AROS' Contrib svn.