From 6a14edc8d8762a54a174c2df1bee5715fc0a0526 Mon Sep 17 00:00:00 2001 From: Mike Klein Date: Wed, 9 Aug 2017 15:04:27 -0400 Subject: Remove SkColorLookUpTable::interp3D(). It looks like our recursive approach is faster than interp3D(), and we'd prefer trilinear interpolation over tetrahedral for quality. Change-Id: I1019254b9ecf24b2f4feff17ed8ae1b48fcc281e Reviewed-on: https://skia-review.googlesource.com/32800 Reviewed-by: Brian Osman Commit-Queue: Mike Klein --- src/core/SkColorLookUpTable.cpp | 161 ++++++++++------------------------------ src/core/SkColorLookUpTable.h | 49 +++--------- 2 files changed, 53 insertions(+), 157 deletions(-) (limited to 'src') diff --git a/src/core/SkColorLookUpTable.cpp b/src/core/SkColorLookUpTable.cpp index d53a509070..c558afb0e1 100644 --- a/src/core/SkColorLookUpTable.cpp +++ b/src/core/SkColorLookUpTable.cpp @@ -9,147 +9,68 @@ #include "SkColorSpaceXformPriv.h" #include "SkFloatingPoint.h" -void SkColorLookUpTable::interp(float* dst, const float* src) const { - if (fInputChannels == 3) { - return this->interp3D(dst, src); - } +SkColorLookUpTable::SkColorLookUpTable(uint8_t inputChannels, const uint8_t limits[]) { + fInputChannels = inputChannels; + SkASSERT(inputChannels >= 1 && inputChannels <= kMaxColorChannels); + memcpy(fLimits, limits, fInputChannels * sizeof(uint8_t)); - Sk4f rgb; - switch (fInputChannels-1) { - case 0: rgb = this->interpDimension<0>(src); break; - case 1: rgb = this->interpDimension<1>(src); break; - case 3: rgb = this->interpDimension<3>(src); break; - default: SkDEBUGFAIL("oops"); + for (int i = 0; i < inputChannels; i++) { + SkASSERT(fLimits[i] > 1); } - - rgb = Sk4f::Max(0, Sk4f::Min(rgb, 1)); - dst[0] = rgb[0]; - dst[1] = rgb[1]; - dst[2] = rgb[2]; } +// Our general strategy is to recursively interpolate each dimension, +// accumulating the index to sample at, and our current pixel stride to help accumulate the index. template -Sk4f SkColorLookUpTable::interpDimension(const float* src, int index, int stride) const { - int limit = fLimits[dim]; +static Sk4f interp_dimension(const float* table, const uint8_t* limits, + const float* src, int index, int stride) { + // We'd logically like to sample this dimension at x. + int limit = limits[dim]; float x = src[dim] * (limit - 1); + // We can't index an array by a float (darn) so we have to snap to nearby integers lo and hi. int lo = (int)(x ), hi = (int)(x + 0.9999f); - Sk4f L = this->interpDimension(src, stride*lo + index, stride*limit), - H = this->interpDimension(src, stride*hi + index, stride*limit); + // Recursively sample at lo and hi. + Sk4f L = interp_dimension(table,limits,src, stride*lo + index, stride*limit), + H = interp_dimension(table,limits,src, stride*hi + index, stride*limit); + // Linearly interpolate those colors based on their distance to x. float t = (x - lo); return (1 - t)*L + t*H; } +// Bottom out our recursion at 0 dimensions, i.e. just return the color at index. template <> -Sk4f SkColorLookUpTable::interpDimension<-1>(const float* src, int index, int stride) const { +Sk4f interp_dimension<-1>(const float* table, const uint8_t* limits, + const float* src, int index, int stride) { return { - this->table()[kOutputChannels*index+0], - this->table()[kOutputChannels*index+1], - this->table()[kOutputChannels*index+2], + table[3*index+0], + table[3*index+1], + table[3*index+2], 0.0f, }; } -void SkColorLookUpTable::interp3D(float* dst, const float* src) const { - SkASSERT(3 == kOutputChannels); - // Call the src components x, y, and z. - const uint8_t maxX = fLimits[0] - 1; - const uint8_t maxY = fLimits[1] - 1; - const uint8_t maxZ = fLimits[2] - 1; - - // An approximate index into each of the three dimensions of the table. - const float x = src[0] * maxX; - const float y = src[1] * maxY; - const float z = src[2] * maxZ; - - // This gives us the low index for our interpolation. - int ix = sk_float_floor2int(x); - int iy = sk_float_floor2int(y); - int iz = sk_float_floor2int(z); - - // Make sure the low index is not also the max index. - ix = (maxX == ix) ? ix - 1 : ix; - iy = (maxY == iy) ? iy - 1 : iy; - iz = (maxZ == iz) ? iz - 1 : iz; - - // Weighting factors for the interpolation. - const float diffX = x - ix; - const float diffY = y - iy; - const float diffZ = z - iz; - - // Constants to help us navigate the 3D table. - // Ex: Assume x = a, y = b, z = c. - // table[a * n001 + b * n010 + c * n100] logically equals table[a][b][c]. - const int n000 = 0; - const int n001 = 3 * fLimits[1] * fLimits[2]; - const int n010 = 3 * fLimits[2]; - const int n011 = n001 + n010; - const int n100 = 3; - const int n101 = n100 + n001; - const int n110 = n100 + n010; - const int n111 = n110 + n001; - - // Base ptr into the table. - const float* ptr = &(table()[ix*n001 + iy*n010 + iz*n100]); - - // The code below performs a tetrahedral interpolation for each of the three - // dst components. Once the tetrahedron containing the interpolation point is - // identified, the interpolation is a weighted sum of grid values at the - // vertices of the tetrahedron. The claim is that tetrahedral interpolation - // provides a more accurate color conversion. - // blogs.mathworks.com/steve/2006/11/24/tetrahedral-interpolation-for-colorspace-conversion/ - // - // I have one test image, and visually I can't tell the difference between - // tetrahedral and trilinear interpolation. In terms of computation, the - // tetrahedral code requires more branches but less computation. The - // SampleICC library provides an option for the client to choose either - // tetrahedral or trilinear. - for (int i = 0; i < 3; i++) { - if (diffZ < diffY) { - if (diffZ > diffX) { - dst[i] = (ptr[n000] + diffZ * (ptr[n110] - ptr[n010]) + - diffY * (ptr[n010] - ptr[n000]) + - diffX * (ptr[n111] - ptr[n110])); - } else if (diffY < diffX) { - dst[i] = (ptr[n000] + diffZ * (ptr[n111] - ptr[n011]) + - diffY * (ptr[n011] - ptr[n001]) + - diffX * (ptr[n001] - ptr[n000])); - } else { - dst[i] = (ptr[n000] + diffZ * (ptr[n111] - ptr[n011]) + - diffY * (ptr[n010] - ptr[n000]) + - diffX * (ptr[n011] - ptr[n010])); - } - } else { - if (diffZ < diffX) { - dst[i] = (ptr[n000] + diffZ * (ptr[n101] - ptr[n001]) + - diffY * (ptr[n111] - ptr[n101]) + - diffX * (ptr[n001] - ptr[n000])); - } else if (diffY < diffX) { - dst[i] = (ptr[n000] + diffZ * (ptr[n100] - ptr[n000]) + - diffY * (ptr[n111] - ptr[n101]) + - diffX * (ptr[n101] - ptr[n100])); - } else { - dst[i] = (ptr[n000] + diffZ * (ptr[n100] - ptr[n000]) + - diffY * (ptr[n110] - ptr[n100]) + - diffX * (ptr[n111] - ptr[n110])); - } - } - - // |src| is guaranteed to be in the 0-1 range as are all entries - // in the table. For "increasing" tables, outputs will also be - // in the 0-1 range. While this property is logical for color - // look up tables, we don't check for it. - // And for arbitrary, non-increasing tables, it is easy to see how - // the output might not be 0-1. So we clamp here. - dst[i] = clamp_0_1(dst[i]); +template +static Sk4f interp_dimension(const float* table, const uint8_t* limits, const float* src) { + // Start our accumulated index and stride off at their identity values, 0 and 1. + return interp_dimension(table, limits, src, 0,1); +} - // Increment the table ptr in order to handle the next component. - // Note that this is the how table is designed: all of nXXX - // variables are multiples of 3 because there are 3 output - // components. - ptr++; +void SkColorLookUpTable::interp(float* dst, const float* src) const { + Sk4f rgb; + switch (fInputChannels-1) { + case 0: rgb = interp_dimension<0>(this->table(), fLimits, src); break; + case 1: rgb = interp_dimension<1>(this->table(), fLimits, src); break; + case 2: rgb = interp_dimension<2>(this->table(), fLimits, src); break; + case 3: rgb = interp_dimension<3>(this->table(), fLimits, src); break; + default: SkDEBUGFAIL("oops"); return; } + + rgb = Sk4f::Max(0, Sk4f::Min(rgb, 1)); + dst[0] = rgb[0]; + dst[1] = rgb[1]; + dst[2] = rgb[2]; } diff --git a/src/core/SkColorLookUpTable.h b/src/core/SkColorLookUpTable.h index d6eac10a41..743f110ba9 100644 --- a/src/core/SkColorLookUpTable.h +++ b/src/core/SkColorLookUpTable.h @@ -19,28 +19,14 @@ class SkColorLookUpTable : public SkRefCnt { public: static constexpr uint8_t kOutputChannels = 3; - SkColorLookUpTable(uint8_t inputChannels, const uint8_t limits[kMaxColorChannels]) - : fInputChannels(inputChannels) { - SkASSERT(inputChannels >= 1 && inputChannels <= kMaxColorChannels); - memcpy(fLimits, limits, fInputChannels * sizeof(uint8_t)); + SkColorLookUpTable(uint8_t inputChannels, const uint8_t limits[]); - for (int i = 0; i < inputChannels; i++) { - SkASSERT(fLimits[i] > 1); - } - } - - /** - * If fInputChannels == kOutputChannels == 3, performs tetrahedral interpolation, otherwise - * performs multilinear interpolation (ie LERP for n =1, bilinear for n=2, trilinear for n=3) - * with fInputChannels input dimensions and kOutputChannels output dimensions. - * |dst| can be |src| only when fInputChannels == kOutputChannels == 3 - * |dst| is the destination pixel, must have at least kOutputChannels elements. - * |src| is the source pixel, must have at least fInputChannels elements. - */ - void interp(float* dst, const float* src) const; - - int inputChannels() const { return fInputChannels; } + // This always does the appropriate multilinear interpolation. + // We used to do tetrahedral for 3D tables, but found that was slower! + // src must point to fInputChannels values, one per channel. + void interp(float dst[3], const float src[]) const; + int inputChannels() const { return fInputChannels; } int outputChannels() const { return kOutputChannels; } // TODO: Rename to somethingBetter(int)? @@ -49,30 +35,19 @@ public: return fLimits[dimension]; } + // Objects of this type are created in a custom fashion using sk_malloc_throw + // and therefore must be sk_freed. + void* operator new(size_t size) = delete; + void* operator new(size_t, void* p) { return p; } + void operator delete(void* p) { sk_free(p); } + private: const float* table() const { return SkTAddOffset(this, sizeof(SkColorLookUpTable)); } - /** - * Performs tetrahedral interpolation with 3 input and 3 output dimensions. - * |dst| can be |src| - */ - void interp3D(float* dst, const float* src) const; - - // recursively LERPs one dimension at a time. Used by interp() for the general case - template - Sk4f interpDimension(const float* src, int index=0, int stride=1) const; - uint8_t fInputChannels; uint8_t fLimits[kMaxColorChannels]; - -public: - // Objects of this type are created in a custom fashion using sk_malloc_throw - // and therefore must be sk_freed. - void* operator new(size_t size) = delete; - void* operator new(size_t, void* p) { return p; } - void operator delete(void* p) { sk_free(p); } }; #endif -- cgit v1.2.3