enum { RASTER_MAP_R = 32, RASTER_SHIFT_R = 3, RASTER_MAP_G = 64, RASTER_SHIFT_G = 2, RASTER_MAP_B = 16, RASTER_SHIFT_B = 4, RASTER_MAP_MAX = 64 }; struct PaletteCv { Buffer<byte> cv; byte *At(int r, int b) { return cv + (r << 10) + (b << 6); } byte Get(const RGBA& b) const { return cv[(int(b.r >> RASTER_SHIFT_R) << 10) + (int(b.g >> RASTER_SHIFT_G)) + (int(b.b >> RASTER_SHIFT_B) << 6)]; } PaletteCv() { cv.Alloc(RASTER_MAP_R * RASTER_MAP_G * RASTER_MAP_B); } }; struct sPalCv { PaletteCv& cv_pal; const RGBA *palette; int ncolors; bool done[RASTER_MAP_G]; struct Ginfo { int dist; byte g; byte ii; }; enum { BINS = 16, BINSHIFT = 11 }; Ginfo line[BINS][256]; Ginfo *eline[BINS]; byte *gline; static int Sq(int a, int b) { return (a - b) * (a - b); } void SetLine(int r, int b); int Get(int g); sPalCv(const RGBA *palette, int ncolors, PaletteCv& cv_pal); }; void sPalCv::SetLine(int r, int b) { gline = cv_pal.At(r, b); r = 255 * r / (RASTER_MAP_R - 1); b = 255 * b / (RASTER_MAP_B - 1); for(int i = 0; i < BINS; i++) eline[i] = line[i]; for(int i = 0; i < ncolors; i++) { int dist = Sq(palette[i].r, r) + Sq(palette[i].b, b); int bini = dist >> BINSHIFT; Ginfo *t = eline[bini >= BINS ? BINS - 1 : bini]++; t->dist = dist; t->g = palette[i].g; t->ii = i; } ZeroArray(done); } int sPalCv::Get(int g) { if(done[g]) return gline[g]; int gg = 255 * g / (RASTER_MAP_G - 1); int ii = 0; int dist = INT_MAX; for(int th = 0; th < BINS; th++) { Ginfo *s = line[th]; Ginfo *e = eline[th]; while(s < e) { int sdist = Sq(s->g, gg) + s->dist; if(sdist < dist) { ii = s->ii; dist = sdist; } s++; } if(th < BINS - 1 && dist < ((th + 1) << BINSHIFT)) break; } done[g] = true; gline[g] = ii; return ii; } sPalCv::sPalCv(const RGBA *palette, int ncolors, PaletteCv& cv_pal) : cv_pal(cv_pal), ncolors(ncolors), palette(palette) { byte ender[256]; for(int b = 0; b < RASTER_MAP_B; b++) { ZeroArray(ender); for(int r = 0; r < RASTER_MAP_R; r++) { SetLine(r, b); int g = 0; while(g < RASTER_MAP_G) { int ii = Get(g); int eg = max<int>(g, ender[ii]); if(Get(eg) == ii) while(eg < RASTER_MAP_G - 1 && Get(eg + 1) == ii) eg++; else while(Get(eg) != ii) eg--; ender[ii] = eg; g++; while(g <= eg - 1) { gline[g] = ii; done[g] = true; g++; } } } } }
enum { ... RASTER_SHIFT2_R = ((4-RASTER_SHIFT_R)*2), RASTER_SHIFT2_G = ((4-RASTER_SHIFT_G)*2), RASTER_SHIFT2_B = ((4-RASTER_SHIFT_B)*2), }; r = (r<<RASTER_SHIFT_R) + (r>>RASTER_SHIFT2_R); g = (g<<RASTER_SHIFT_G) + (g>>RASTER_SHIFT2_G); b = (b<<RASTER_SHIFT_B) + (b>>RASTER_SHIFT2_B);
luzr wrote on Fri, 07 April 2006 11:16 |
(to 64K colors here) |
enum { RASTER_MAP_R = 32, RASTER_SHIFT_R = 3, RASTER_MAP_G = 64, RASTER_SHIFT_G = 2, RASTER_MAP_B = 16, RASTER_SHIFT_B = 4, RASTER_MAP_MAX = 64, RASTER_MAP_MAX_SHIFT = 2, RASTER_MAP_R_ADD = (1<<RASTER_SHIFT_R), RASTER_MAP_G_ADD = (1<<RASTER_SHIFT_G), RASTER_MAP_B_ADD = (1<<RASTER_SHIFT_B), RASTER_MAP_MAX_DIST = 3*((RASTER_MAP_MAX-1)*(RASTER_MAP_MAX-1)) }; struct PaletteCv { Buffer<byte> cv; static inline int GetIndex(const RGBA &c) { return (int(c.r >> RASTER_SHIFT_R) << 10) + (int(c.g >> RASTER_SHIFT_G)) + (int(c.b >> RASTER_SHIFT_B) << 6); } byte Get(const RGBA& c) const { return cv[GetIndex(c)]; } PaletteCv() { cv.Alloc(RASTER_MAP_R * RASTER_MAP_G * RASTER_MAP_B); } }; struct sCubePoint : Moveable<sCubePoint> { RGBA mycol; byte index; }; struct sPalCv2 { PaletteCv& cv_pal; const RGBA *palette; int ncolors; void AddPoint(byte r, byte g, byte b, byte idx, Vector<sCubePoint> *feed); sPalCv2(const RGBA *palette, int ncolors, PaletteCv& cv_pal); }; void sPalCv2::AddPoint(byte r, byte g, byte b, byte idx, Vector<sCubePoint> *feed) { sCubePoint pt; int dr = (int(palette[idx].r)-int(r))>>RASTER_MAP_MAX_SHIFT; int dg = (int(palette[idx].g)-int(g))>>RASTER_MAP_MAX_SHIFT; int db = (int(palette[idx].b)-int(b))>>RASTER_MAP_MAX_SHIFT; int dist = dr*dr + dg*dg + db*db; pt.mycol.r = r; pt.mycol.g = g; pt.mycol.b = b; pt.index = idx; ASSERT(dist <= RASTER_MAP_MAX_DIST); feed[dist].Add(pt); } sPalCv2::sPalCv2(const RGBA *palette, int ncolors, PaletteCv& cv_pal) : cv_pal(cv_pal), ncolors(ncolors), palette(palette) { int ii, jj; sCubePoint cubpt; Vector<sCubePoint> feed_me[RASTER_MAP_MAX_DIST+1]; byte filled[RASTER_MAP_R * RASTER_MAP_G * RASTER_MAP_B]; ZeroArray(filled); ii = ncolors; while (ii--) { cubpt.index = ii; cubpt.mycol = palette[ii]; feed_me[0].Add(cubpt); } for (ii = 0; ii <= RASTER_MAP_MAX_DIST; ++ii) { while ( !feed_me[ii].IsEmpty() ) { cubpt = feed_me[ii].Pop(); jj = cv_pal.GetIndex(cubpt.mycol); if (filled[jj] != 0) continue; filled[jj] = 1; cv_pal.cv[jj] = cubpt.index; if ( int(cubpt.mycol.r)+RASTER_MAP_R_ADD <= 255 ) AddPoint(cubpt.mycol.r+RASTER_MAP_R_ADD, cubpt.mycol.g, cubpt.mycol.b, cubpt.index, feed_me); if ( int(cubpt.mycol.r)-RASTER_MAP_R_ADD >= 0 ) AddPoint(cubpt.mycol.r-RASTER_MAP_R_ADD, cubpt.mycol.g, cubpt.mycol.b, cubpt.index, feed_me); if ( int(cubpt.mycol.g)+RASTER_MAP_G_ADD <= 255 ) AddPoint(cubpt.mycol.r, cubpt.mycol.g+RASTER_MAP_G_ADD, cubpt.mycol.b, cubpt.index, feed_me); if ( int(cubpt.mycol.g)-RASTER_MAP_G_ADD >= 0 ) AddPoint(cubpt.mycol.r, cubpt.mycol.g-RASTER_MAP_G_ADD, cubpt.mycol.b, cubpt.index, feed_me); if ( int(cubpt.mycol.b)+RASTER_MAP_B_ADD <= 255 ) AddPoint(cubpt.mycol.r, cubpt.mycol.g, cubpt.mycol.b+RASTER_MAP_B_ADD, cubpt.index, feed_me); if ( int(cubpt.mycol.b)-RASTER_MAP_B_ADD >= 0 ) AddPoint(cubpt.mycol.r, cubpt.mycol.g, cubpt.mycol.b-RASTER_MAP_B_ADD, cubpt.index, feed_me); } } }
/* - new distance square "(d+x)^2" calculation (from old distance square "d^2" and old delta "d") delta will change by +-4 (blue), +-2 (red) or +-1 (green) +-1 : (d+1)^2 = d^2 + (2d + 1) max 62->63: 125 (max distance delta for green) +-2 : (d+2)^2 = d^2 + (4d + 4) nax 60->62: 244 +-4 : (d+4)^2 = d^2 + (8d + 16) max 56->60: 464 */ #ifdef COMPILER_MSC #pragma pack(push, 1) #endif struct sCubePoint3 : Moveable<sCubePoint3> { word address; //high-color 5:6:4 = address into cube space too byte index; //index into palette int8 delta[3]; //current deltas of this point from origin } #ifdef COMPILER_GCC __attribute__((packed)) #endif ; #ifdef COMPILER_MSC #pragma pack(pop) #endif //conversion map struct PaletteCv3 { enum { MAX_DISTANCE_DELTA = (8*56+16), R_SHIFT = 10, G_SHIFT = 0, B_SHIFT = 6, R_MASK = ((RASTER_MAP_R-1)<<R_SHIFT), G_MASK = ((RASTER_MAP_G-1)<<G_SHIFT), B_MASK = ((RASTER_MAP_B-1)<<B_SHIFT), R_ADR_ADD = (1<<R_SHIFT), G_ADR_ADD = (1<<G_SHIFT), B_ADR_ADD = (1<<B_SHIFT), }; Buffer<byte> cv; static inline word GetIndex(const RGBA &c) { return (word(c.r >> RASTER_SHIFT_R) << R_SHIFT) + (word(c.g >> RASTER_SHIFT_G) << G_SHIFT) + (word(c.b >> RASTER_SHIFT_B) << B_SHIFT); } byte Get(const RGBA& c) const { return cv[GetIndex(c)]; } PaletteCv3() { cv.Alloc(RASTER_MAP_R * RASTER_MAP_G * RASTER_MAP_B); } }; //generator of data for conversion maps struct sPalCv3 { PaletteCv3& cv_pal; const RGBA *palette; int ncolors; //FIFO queue for parallel flood fill, radix-sorted by distance of points from their origin //the radix sort works on dynamic subset of distances, as you never need the full range during fill Vector<sCubePoint3> feed_me[PaletteCv3::MAX_DISTANCE_DELTA+1]; byte filled[RASTER_MAP_R * RASTER_MAP_G * RASTER_MAP_B]; void AddPoint(const sCubePoint3 & cubpt, int ii, word add2address, int move, int a, int8 add2delta); sPalCv3(const RGBA *palette, int ncolors, PaletteCv3& cv_pal); }; struct sFillMovementData { word mask; word mask_delta; int8 delta; int a, b; }; static const sFillMovementData fmovedata[3] = { {PaletteCv3::R_MASK, PaletteCv3::R_ADR_ADD, 2, 4, 4}, {PaletteCv3::G_MASK, PaletteCv3::G_ADR_ADD, 1, 2, 1}, {PaletteCv3::B_MASK, PaletteCv3::B_ADR_ADD, 4, 8, 16}, }; void sPalCv3::AddPoint(const sCubePoint3 & cubpt, int ii, word add2address, int move, int a, int8 add2delta) { int newii; sCubePoint3 cubpt2; cubpt2.address = cubpt.address + add2address; if ( filled[cubpt2.address] ) return; newii = ii + a * cubpt.delta[move] + fmovedata[move].b; ASSERT( newii > ii ); if ( newii > PaletteCv3::MAX_DISTANCE_DELTA ) { newii -= PaletteCv3::MAX_DISTANCE_DELTA+1; ASSERT( newii <= PaletteCv3::MAX_DISTANCE_DELTA ); ASSERT( newii < ii ); } cubpt2.delta[0] = cubpt.delta[0]; cubpt2.delta[1] = cubpt.delta[1]; cubpt2.delta[2] = cubpt.delta[2]; cubpt2.index = cubpt.index; cubpt2.delta[move] += add2delta; feed_me[newii].Add(cubpt2); } sPalCv3::sPalCv3(const RGBA *palette, int ncolors, PaletteCv3& cv_pal) : cv_pal(cv_pal), ncolors(ncolors), palette(palette) { int ii, jj = (RASTER_MAP_R * RASTER_MAP_G * RASTER_MAP_B), move; sCubePoint3 cubpt; ZeroArray(filled); feed_me[0].Reserve(ncolors); //Fill up the FIFO queue with colors from palette, //those will start the parallel flood fill in the color cube space ii = ncolors; cubpt.delta[0] = cubpt.delta[1] = cubpt.delta[2] = 0; while (ii--) { cubpt.index = ii; cubpt.address = cv_pal.GetIndex(palette[ii]); feed_me[0].Add(cubpt); } //process the FIFO queue untill all points in color cube space are filled (jj == 0) ii = 0; while ( true ) { //if ( !feed_me[ii].IsEmpty() ) printf("%d\t(%d)\t", ii, feed_me[ii].GetCount()); while ( !feed_me[ii].IsEmpty() ) { cubpt = feed_me[ii].Pop(); if ( filled[cubpt.address] ) continue; cv_pal.cv[cubpt.address] = cubpt.index; if ( --jj == 0 ) return; filled[cubpt.address] = 1; //try all possible moves (6 possible directions) for ( move = 0; move < 3; ++move ) { if ( ( cubpt.delta[move] >= 0 ) && ( (cubpt.address & fmovedata[move].mask) < fmovedata[move].mask ) ) AddPoint(cubpt, ii, fmovedata[move].mask_delta, move, fmovedata[move].a, fmovedata[move].delta); if ( ( cubpt.delta[move] <= 0 ) && ( (cubpt.address & fmovedata[move].mask) > 0 ) ) AddPoint(cubpt, ii, -fmovedata[move].mask_delta, move, -fmovedata[move].a, -fmovedata[move].delta); } } if ( ++ii > PaletteCv3::MAX_DISTANCE_DELTA ) ii = 0; } return; }