Subversion Repositories eduke32

Rev

Rev 8489 | Details | Compare with Previous | Last modification | View Log | RSS feed

Rev Author Line No. Line
5359 hendricks2 1
 
2
#include "colmatch.h"
3
 
4
#define FASTPALCOLDEPTH 256
5
#define FASTPALRIGHTSHIFT 3
6
#define FASTPALRGBDIST (FASTPALCOLDEPTH*2+1)
7
static int32_t rdist[FASTPALRGBDIST], gdist[FASTPALRGBDIST], bdist[FASTPALRGBDIST];
8
#define FASTPALGRIDSIZ (FASTPALCOLDEPTH>>FASTPALRIGHTSHIFT)
7806 terminx 9
static char colhere[((FASTPALGRIDSIZ+2)*(FASTPALGRIDSIZ+2)*(FASTPALGRIDSIZ+2)+7)>>3];
5359 hendricks2 10
static char colhead[(FASTPALGRIDSIZ+2)*(FASTPALGRIDSIZ+2)*(FASTPALGRIDSIZ+2)];
11
static int32_t colnext[256];
12
#define FASTPALCOLDIST (1<<FASTPALRIGHTSHIFT)
13
#define FASTPALCOLDISTMASK (FASTPALCOLDIST-1)
14
static uint8_t coldist[FASTPALCOLDIST];
15
static int32_t colscan[27];
16
 
17
static uint8_t const * colmatch_palette;
18
 
19
#define pow2char(x) (1u << (x))
20
 
21
//
8488 hendricks2 22
// paletteInitClosestColor
5359 hendricks2 23
//
8488 hendricks2 24
void paletteInitClosestColorScale(int32_t rscale, int32_t gscale, int32_t bscale)
5359 hendricks2 25
{
26
    int32_t j = 0;
5829 terminx 27
    for (bssize_t i=256; i>=0; i--)
5359 hendricks2 28
    {
29
        //j = (i-64)*(i-64);
30
        rdist[i] = rdist[FASTPALCOLDEPTH*2-i] = j*rscale;
31
        gdist[i] = gdist[FASTPALCOLDEPTH*2-i] = j*gscale;
32
        bdist[i] = bdist[FASTPALCOLDEPTH*2-i] = j*bscale;
33
        j += FASTPALRGBDIST-(i<<1);
34
    }
35
}
8488 hendricks2 36
void paletteInitClosestColorMap(uint8_t const * const pal)
5359 hendricks2 37
{
38
    Bmemset(colhere,0,sizeof(colhere));
39
    Bmemset(colhead,0,sizeof(colhead));
40
 
41
    colmatch_palette = pal;
42
 
5540 terminx 43
    char const *pal1 = (char const *)&pal[768-3];
5829 terminx 44
    for (bssize_t i=255; i>=0; i--,pal1-=3)
5359 hendricks2 45
    {
46
        int32_t const j = (pal1[0]>>FASTPALRIGHTSHIFT)*FASTPALGRIDSIZ*FASTPALGRIDSIZ
47
            + (pal1[1]>>FASTPALRIGHTSHIFT)*FASTPALGRIDSIZ + (pal1[2]>>FASTPALRIGHTSHIFT)
48
            + FASTPALGRIDSIZ*FASTPALGRIDSIZ + FASTPALGRIDSIZ + 1;
49
        if (colhere[j>>3]&pow2char(j&7)) colnext[i] = colhead[j]; else colnext[i] = -1;
50
        colhead[j] = i;
51
        colhere[j>>3] |= pow2char(j&7);
52
    }
5367 hendricks2 53
 
8488 hendricks2 54
    paletteFlushClosestColor();
5359 hendricks2 55
}
8488 hendricks2 56
void paletteInitClosestColorGrid(void)
5359 hendricks2 57
{
58
    int i = 0;
59
    int32_t x, y, z;
60
    for (x=-FASTPALGRIDSIZ*FASTPALGRIDSIZ; x<=FASTPALGRIDSIZ*FASTPALGRIDSIZ; x+=FASTPALGRIDSIZ*FASTPALGRIDSIZ)
61
        for (y=-FASTPALGRIDSIZ; y<=FASTPALGRIDSIZ; y+=FASTPALGRIDSIZ)
62
            for (z=-1; z<=1; z++)
63
                colscan[i++] = x+y+z;
64
    i = colscan[13]; colscan[13] = colscan[26]; colscan[26] = i;
65
 
66
    for (i = 0; i < FASTPALCOLDIST/2; i++)
67
        coldist[i] = i;
68
    for (; i < FASTPALCOLDIST; i++)
69
        coldist[i] = FASTPALCOLDIST-i;
70
}
71
 
72
#define COLRESULTSIZ 4096
73
 
8488 hendricks2 74
static uint32_t colmatchresults[COLRESULTSIZ];
75
static int32_t numcolmatchresults;
5359 hendricks2 76
 
8488 hendricks2 77
void paletteFlushClosestColor(void)
5359 hendricks2 78
{
8488 hendricks2 79
    Bmemset(colmatchresults, 0, COLRESULTSIZ * sizeof(uint32_t));
80
    numcolmatchresults = 0;
5359 hendricks2 81
}
82
 
8491 hendricks2 83
#define checkbitfield(field, idx) ((field)[(idx)>>3] & (1u<<((idx)&7)))
84
 
5359 hendricks2 85
// Finds a color index in [0 .. lastokcol] closest to (r, g, b).
86
// <lastokcol> must be in [0 .. 255].
8491 hendricks2 87
int32_t paletteGetClosestColorWithBlacklist(int32_t const r, int32_t const g, int32_t const b, int32_t const lastokcol, uint8_t const * const blacklist)
5359 hendricks2 88
{
89
#ifdef DEBUGGINGAIDS
90
    Bassert(lastokcol >= 0 && lastokcol <= 255);
91
#endif
92
 
93
    uint32_t const col = r | (g<<8) | (b<<16);
94
 
95
    int mindist = -1;
96
 
8488 hendricks2 97
    int const k = (numcolmatchresults > COLRESULTSIZ) ? COLRESULTSIZ : numcolmatchresults;
5359 hendricks2 98
 
8488 hendricks2 99
    if (!numcolmatchresults) goto skip;
5359 hendricks2 100
 
8488 hendricks2 101
    if (col == (colmatchresults[(numcolmatchresults-1) & (COLRESULTSIZ-1)] & 0x00ffffff))
102
        return colmatchresults[(numcolmatchresults-1) & (COLRESULTSIZ-1)]>>24;
5359 hendricks2 103
 
104
    int i;
105
 
8315 hendricks2 106
    for (i = 0; i <= k-4; i+=4)
5359 hendricks2 107
    {
8488 hendricks2 108
        if (col == (colmatchresults[i]   & 0x00ffffff)) { mindist = i; break; }
109
        if (col == (colmatchresults[i+1] & 0x00ffffff)) { mindist = i+1; break; }
110
        if (col == (colmatchresults[i+2] & 0x00ffffff)) { mindist = i+2; break; }
111
        if (col == (colmatchresults[i+3] & 0x00ffffff)) { mindist = i+3; break; }
5359 hendricks2 112
    }
113
 
114
    if (mindist == -1)
115
    for (; i < k; i++)
8488 hendricks2 116
        if (col == (colmatchresults[i] & 0x00ffffff)) { mindist = i; break; }
5359 hendricks2 117
 
8491 hendricks2 118
    if (mindist != -1)
119
    {
120
        uint32_t const idx = colmatchresults[mindist]>>24;
121
        if (idx <= (unsigned)lastokcol && (blacklist == nullptr || !checkbitfield(blacklist, idx)))
122
            return idx;
123
    }
5359 hendricks2 124
 
125
skip:
8491 hendricks2 126
    i = paletteGetClosestColorWithBlacklistNoCache(r, g, b, lastokcol, blacklist);
8488 hendricks2 127
    colmatchresults[numcolmatchresults++ & (COLRESULTSIZ-1)] = col | (i << 24);
5376 hendricks2 128
    return i;
129
}
5359 hendricks2 130
 
8491 hendricks2 131
int32_t paletteGetClosestColorWithBlacklistNoCache(int32_t r, int32_t g, int32_t b, int32_t const lastokcol, uint8_t const * const blacklist)
5376 hendricks2 132
{
133
#ifdef DEBUGGINGAIDS
134
    Bassert(lastokcol >= 0 && lastokcol <= 255);
135
#endif
136
 
137
    int const j = (r>>FASTPALRIGHTSHIFT)*FASTPALGRIDSIZ*FASTPALGRIDSIZ
138
        + (g>>FASTPALRIGHTSHIFT)*FASTPALGRIDSIZ + (b>>FASTPALRIGHTSHIFT)
139
        + FASTPALGRIDSIZ*FASTPALGRIDSIZ
140
        + FASTPALGRIDSIZ + 1;
141
 
5359 hendricks2 142
    int const minrdist = rdist[coldist[r&FASTPALCOLDISTMASK]+FASTPALCOLDEPTH];
143
    int const mingdist = gdist[coldist[g&FASTPALCOLDISTMASK]+FASTPALCOLDEPTH];
144
    int const minbdist = bdist[coldist[b&FASTPALCOLDISTMASK]+FASTPALCOLDEPTH];
145
 
5376 hendricks2 146
    int mindist = min(minrdist, mingdist);
5359 hendricks2 147
    mindist = min(mindist, minbdist) + 1;
148
 
149
    r = FASTPALCOLDEPTH-r, g = FASTPALCOLDEPTH-g, b = FASTPALCOLDEPTH-b;
150
 
151
    int retcol = -1;
152
 
5829 terminx 153
    for (bssize_t k=26; k>=0; k--)
5359 hendricks2 154
    {
5376 hendricks2 155
        int i = colscan[k]+j;
5359 hendricks2 156
 
157
        if ((colhere[i>>3]&pow2char(i&7)) == 0)
158
            continue;
159
 
160
        i = colhead[i];
161
 
162
        do
163
        {
5540 terminx 164
            char const * const pal1 = (char const *)&colmatch_palette[i*3];
5359 hendricks2 165
            int dist = gdist[pal1[1]+g];
166
 
8491 hendricks2 167
            if (dist >= mindist || i > lastokcol || (blacklist != nullptr && checkbitfield(blacklist, i))) continue;
5359 hendricks2 168
            if ((dist += rdist[pal1[0]+r]) >= mindist) continue;
169
            if ((dist += bdist[pal1[2]+b]) >= mindist) continue;
170
 
171
            mindist = dist;
172
            retcol = i;
173
        }
174
        while ((i = colnext[i]) >= 0);
175
    }
176
 
177
    if (retcol >= 0)
178
        return retcol;
179
 
180
    mindist = INT32_MAX;
181
 
8489 hendricks2 182
    for (bssize_t i = 0; i <= lastokcol; ++i)
5359 hendricks2 183
    {
8491 hendricks2 184
        if (blacklist != nullptr && checkbitfield(blacklist, i))
185
            continue;
186
 
5540 terminx 187
        char const * const pal1 = (char const *)&colmatch_palette[i*3];
5359 hendricks2 188
        int dist = gdist[pal1[1]+g];
189
 
190
        if (dist >= mindist) continue;
191
        if ((dist += rdist[pal1[0]+r]) >= mindist) continue;
192
        if ((dist += bdist[pal1[2]+b]) >= mindist) continue;
193
 
194
        mindist = dist;
195
        retcol = i;
196
    }
197
 
198
    return retcol;
199
}