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 <brianosman@google.com>
Commit-Queue: Mike Klein <mtklein@chromium.org>

2 files changed, 53 insertions, 157 deletions

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 <int dim>
-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<dim-1>(src, stride*lo + index, stride*limit),
-         H = this->interpDimension<dim-1>(src, stride*hi + index, stride*limit);
+    // Recursively sample at lo and hi.
+    Sk4f L = interp_dimension<dim-1>(table,limits,src, stride*lo + index, stride*limit),
+         H = interp_dimension<dim-1>(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 <int dim>
+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<dim>(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<const float>(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 <int dim>
-    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