| 1 |
– |
/* Copyright 1988 Regents of the University of California */ |
| 2 |
– |
|
| 1 |
|
#ifndef lint |
| 2 |
< |
static char SCCSid[] = "$SunId$ LBL"; |
| 2 |
> |
static const char RCSid[] = "$Id$"; |
| 3 |
|
#endif |
| 6 |
– |
|
| 4 |
|
/* |
| 5 |
|
CLOSEST - nearest-color lookup by locally ordered search |
| 6 |
|
we use distance in rgb space as color metric |
| 12 |
|
Paul Heckbert |
| 13 |
|
*/ |
| 14 |
|
|
| 15 |
+ |
#include <stdlib.h> |
| 16 |
+ |
|
| 17 |
|
#include "ciq.h" |
| 18 |
|
|
| 19 |
|
#define inf 3*256*256 |
| 20 |
< |
#define key ((r&0xe0)<<1|(g&0xe0)>>2|(b&0xe0)>>5) /* hash key: rrrgggbbb */ |
| 20 |
> |
#define key(r,g,b) (((r)&0xe0)<<1|((g)&0xe0)>>2|((b)&0xe0)>>5) |
| 21 |
> |
/* 9-bit hash key: rrrgggbbb */ |
| 22 |
|
|
| 23 |
< |
static struct thing {int mindist,pv;} space[512*257],*next=space,*bucket[512]; |
| 23 |
> |
static struct thing {int mindist,pv;} space[512*257],*next,*bucket[512]; |
| 24 |
|
/* sorted lists of colors */ |
| 25 |
|
|
| 26 |
< |
static int nfill=0,tests=0,calls=0; |
| 26 |
> |
static int nfill,tests,calls; |
| 27 |
|
static char filled[512]; /* has bucket[key] been filled yet? */ |
| 28 |
|
static int sq[511]; |
| 29 |
|
|
| 30 |
< |
initialize() { /* reset the buckets */ |
| 30 |
> |
static int compare(const void *a, const void *b); |
| 31 |
> |
static void fillbucket(int k); |
| 32 |
> |
|
| 33 |
> |
|
| 34 |
> |
void |
| 35 |
> |
initializeclosest(void) { /* reset the buckets */ |
| 36 |
|
int k; |
| 37 |
|
nfill = tests = calls = 0; |
| 38 |
|
for (k=0; k<512; k++) filled[k] = 0; |
| 39 |
|
next = space; |
| 40 |
|
} |
| 41 |
|
|
| 42 |
< |
closest(r,g,b) /* find pv of colormap color closest to (r,g,b) */ |
| 43 |
< |
int r,g,b; |
| 42 |
> |
int |
| 43 |
> |
closest( /* find pv of colormap color closest to (r,g,b) */ |
| 44 |
> |
int r, |
| 45 |
> |
int g, |
| 46 |
> |
int b |
| 47 |
> |
) |
| 48 |
|
{ |
| 49 |
|
register struct thing *p; |
| 50 |
< |
register int *rsq,*gsq,*bsq,dist,min,best; |
| 50 |
> |
register int *rsq,*gsq,*bsq,dist,min; |
| 51 |
> |
int best,k; |
| 52 |
|
struct thing *p0; |
| 53 |
|
|
| 54 |
< |
if (!filled[key]) fillbucket(key); |
| 54 |
> |
k = key(r,g,b); |
| 55 |
> |
if (!filled[k]) fillbucket(k); |
| 56 |
|
min = inf; |
| 57 |
|
rsq = sq+255-r; |
| 58 |
|
gsq = sq+255-g; |
| 59 |
|
bsq = sq+255-b; |
| 60 |
|
|
| 61 |
|
/* stop looking when best is closer than next could be */ |
| 62 |
< |
for (p0=p=bucket[key]; min>p->mindist; p++) { |
| 62 |
> |
for (p0=p=bucket[k]; min>p->mindist; p++) { |
| 63 |
|
dist = rsq[color[0][p->pv]] + gsq[color[1][p->pv]] + |
| 64 |
|
bsq[color[2][p->pv]]; |
| 65 |
|
if (dist<min) { |
| 74 |
|
|
| 75 |
|
#define H 16 /* half-width of a bucket */ |
| 76 |
|
|
| 77 |
< |
compare(a,b) |
| 78 |
< |
register struct thing *a,*b; |
| 77 |
> |
static int |
| 78 |
> |
compare( |
| 79 |
> |
const void *a, |
| 80 |
> |
const void *b |
| 81 |
> |
) |
| 82 |
|
{ |
| 83 |
< |
return a->mindist-b->mindist; |
| 83 |
> |
return ((struct thing*)a)->mindist - ((struct thing*)b)->mindist; |
| 84 |
|
} |
| 85 |
|
|
| 86 |
< |
fillbucket(k) /* make list of colormap colors which could be closest */ |
| 87 |
< |
int k; /* matches for colors in bucket #k */ |
| 86 |
> |
static void |
| 87 |
> |
fillbucket( /* make list of colormap colors which could be closest */ |
| 88 |
> |
int k /* matches for colors in bucket #k */ |
| 89 |
> |
) |
| 90 |
|
{ |
| 91 |
|
register int r,g,b,j,dist,*rsq,*gsq,*bsq,min,best; |
| 92 |
|
struct thing *p,*q; |
| 93 |
|
|
| 94 |
|
if (!sq[0]) for (j= -255; j<256; j++) sq[j+255] = j*j; |
| 95 |
|
|
| 96 |
< |
r = k>>1&0xe0|H; /* center of 32x32x32 cubical bucket */ |
| 97 |
< |
g = k<<2&0xe0|H; |
| 98 |
< |
b = k<<5&0xe0|H; |
| 96 |
> |
r = (k>>1&0xe0)|H; /* center of 32x32x32 cubical bucket */ |
| 97 |
> |
g = (k<<2&0xe0)|H; |
| 98 |
> |
b = (k<<5&0xe0)|H; |
| 99 |
|
rsq = sq+255-r; |
| 100 |
|
gsq = sq+255-g; |
| 101 |
|
bsq = sq+255-b; |
