Adding support for color interpolation hints to CSS gradients.

Source/core/css/CSSGradientValue.cpp

 /*
  * Copyright (C) 2008 Apple Inc.  All rights reserved.
  *
  * Redistribution and use in source and binary forms, with or without
  * modification, are permitted provided that the following conditions
  * are met:
  * 1. Redistributions of source code must retain the above copyright
  *    notice, this list of conditions and the following disclaimer.
  * 2. Redistributions in binary form must reproduce the above copyright
  *    notice, this list of conditions and the following disclaimer in the
@@ skipping 19 matching lines @@
 #include "core/css/CSSCalculationValue.h"
 #include "core/css/CSSToLengthConversionData.h"
 #include "core/css/Pair.h"
 #include "core/dom/NodeRenderStyle.h"
 #include "core/dom/TextLinkColors.h"
 #include "core/rendering/RenderObject.h"
 #include "platform/geometry/IntSize.h"
 #include "platform/graphics/Gradient.h"
 #include "platform/graphics/GradientGeneratedImage.h"
 #include "platform/graphics/Image.h"
+#include "platform/graphics/skia/SkiaUtils.h"

[f(malita), 2014/10/08 16:13:54]

Is this used at all?

[rosca, 2014/10/08 17:18:51]

Yes, it is used for WebCoreFloatNearlyEqual(...)

 #include "wtf/text/StringBuilder.h"
 #include "wtf/text/WTFString.h"
 
 namespace blink {
 
 void CSSGradientColorStop::trace(Visitor* visitor)
 {
     visitor->trace(m_position);
     visitor->trace(m_color);
 }
@@ skipping 57 matching lines @@
 
     GradientStop()
         : offset(0)
         , specified(false)
     { }
 };
 
 PassRefPtrWillBeRawPtr<CSSGradientValue> CSSGradientValue::gradientWithStylesResolved(const TextLinkColors& textLinkColors, Color currentColor)
 {
     bool derived = false;
-    for (unsigned i = 0; i < m_stops.size(); i++)
-        if (m_stops[i].m_color->colorIsDerivedFromElement()) {
-            m_stops[i].m_colorIsDerivedFromElement = true;
+    for (auto& stop : m_stops) {
+        if (stop.m_color && stop.m_color->colorIsDerivedFromElement()) {

[f(malita), 2014/10/08 16:13:54]

I think these checks would look better if we add an explicit
CSSGradientColorStop helper:

bool CSSGradientColorStop::isHint() const {
    ASSERT(m_color || m_position);
    return !m_color;
}

WDYT?

[rosca, 2014/10/08 17:18:52]

Sounds good. I added it inline.

+            stop.m_colorIsDerivedFromElement = true;
             derived = true;
             break;
         }
+    }
 
     RefPtrWillBeRawPtr<CSSGradientValue> result = nullptr;
     if (!derived)
         result = this;
     else if (isLinearGradientValue())
         result = toCSSLinearGradientValue(this)->clone();
     else if (isRadialGradientValue())
         result = toCSSRadialGradientValue(this)->clone();
     else {
         ASSERT_NOT_REACHED();
         return nullptr;
     }
 
-    for (unsigned i = 0; i < result->m_stops.size(); i++)
-        result->m_stops[i].m_resolvedColor = textLinkColors.colorFromPrimitiveValue(result->m_stops[i].m_color.get(), currentColor);
+    for (auto& stop : result->m_stops) {
+        if (stop.m_color)

[f(malita), 2014/10/08 16:13:54]

!stop.isHint()?

[rosca, 2014/10/08 17:18:52]

Done.

+            stop.m_resolvedColor = textLinkColors.colorFromPrimitiveValue(stop.m_color.get(), currentColor);
+    }
 
     return result.release();
 }
 
+static inline int interpolate(int v0, int v1, float p)
+{

[f(malita), 2014/10/08 16:13:54]

ASSERT(p >= 0 && p <= 1)?

[rosca, 2014/10/08 17:18:52]

Done.

+    return v0 + static_cast<int>(p * (v1 - v0));
+}
+
+static inline Color interpolate(Color c1, Color c2, float p)
+{
+    int r = interpolate(c1.red(), c2.red(), p);
+    int g = interpolate(c1.green(), c2.green(), p);
+    int b = interpolate(c1.blue(), c2.blue(), p);
+    int a = interpolate(c1.alpha(), c2.alpha(), p);
+    return Color(r, g, b, a);
+}
+
+static void replaceColorHintsWithColorStops(Vector<GradientStop>& stops, const Vector<CSSGradientColorStop, 2>& cssGradientStops)

[f(malita), 2014/10/08 16:13:54]

Since cssGradientStops is always a CSSGradientValue field, can we make this a
non-static const CSSGradientValue method with a single parameter (stops)?

[rosca, 2014/10/08 17:18:52]

The problem here is that "struct GradientStop" is define here in cpp, being an
implementation detail. Do you think we should move it to the interface, as well?

[f(malita), 2014/10/08 17:34:30]

Ah, you're right, I missed that part. Let's leave it alone, not a big deal.

+{
+    // This algorithm will replace each color interpolation hint with 9 regular
+    // color stops. The color values for the new color stops will be calculated
+    // using the color weighting formula defined in the spec. The new color
+    // stops will be positioned in such a way that all the pixels between the two
+    // user defined color stops have color values close to the interpolation curve.
+    // If the hint is closer to the left color stop, add 2 stops to the left and
+    // 6 to the right, else add 6 stops to the left and 2 to the right.
+    // The color stops on the side with more space start midway because
+    // the curve approximates a line in that region.
+    // Using this aproximation, it is possible to discern the color steps when
+    // the gradient is large. If this becomes an issue, we can consider improving
+    // the algorithm, or adding support for color interpolation hints to skia shaders.
+
+    int indexOffset = 0;
+
+    // The first and the last color stops cannot be color hints.
+    for (size_t i = 1; i < cssGradientStops.size() - 1; ++i) {
+        // Not a color interpolation hint.
+        if (cssGradientStops[i].m_color)

[f(malita), 2014/10/08 16:13:54]

!cssGradientStops[i].isHint()?

[rosca, 2014/10/08 17:18:52]

Done.

+            continue;
+
+        // The current index of the stops vector.
+        size_t x = i + indexOffset;

[f(malita), 2014/10/08 16:13:54]

Let's ASSERT(x >= 1) since indexOffset can potentially become negative.

[rosca, 2014/10/08 17:18:51]

Done.

+
+        // offset1            offset                            offset2
+        //   |-------------------|---------------------------------|
+        //          leftDist                 rightDist
+
+        float offset1 = stops[x - 1].offset;
+        float offset2 = stops[x + 1].offset;
+        float offset = stops[x].offset;
+        float leftDist = offset - offset1;
+        float rightDist = offset2 - offset;
+        float totalDist = offset2 - offset1;
+
+        Color leftColor = stops[x - 1].color;
+        Color rightColor = stops[x + 1].color;
+
+        ASSERT(offset1 <= offset && offset <= offset2);
+
+        // If the color hint is positioned exactly in the middle, we can remove it.
+        if (WebCoreFloatNearlyEqual(leftDist, rightDist)) {

[f(malita), 2014/10/08 16:13:54]

Should we also drop the hint if offset1 == offset2 (overlapping color stops =>
no interpolation)?

[rosca, 2014/10/08 17:18:51]

This expression (leftDist == rightDist) should always be true when offset1 ==
offset2.

+            stops.remove(x);
+            --indexOffset;
+            continue;
+        }
+
+        // Check if the color hint coincides with the left color stop.
+        if (WebCoreFloatNearlyEqual(leftDist, .0f)) {
+            stops[x].color = rightColor;
+            continue;
+        }
+
+        // Check if the color hint coincides with the right color stop.
+        if (WebCoreFloatNearlyEqual(rightDist, .0f)) {
+            stops[x].color = leftColor;
+            continue;
+        }
+
+        GradientStop newStops[9];
+        // Position the new color stops.
+        if (leftDist > rightDist) {
+            for (size_t y = 0; y < 7; ++y)
+                newStops[y].offset = offset1 + leftDist * (7 + y) / 13;
+            newStops[7].offset = offset + rightDist / 3;
+            newStops[8].offset = offset + rightDist * 2 / 3;
+        } else {
+            newStops[0].offset = offset1 + leftDist / 3;
+            newStops[1].offset = offset1 + leftDist * 2 / 3;
+            for (size_t y = 0; y < 7; ++y)
+                newStops[y + 2].offset = offset + rightDist * y / 13;
+        }
+
+        // calculate colors for the new color hints.
+        // The color weighting for the new color stops will be pointRelativeOffset^(ln(0.5)/ln(hintRelativeOffset)).
+        float hintRelativeOffset = leftDist / totalDist;
+        for (size_t y = 0; y < 9; ++y) {
+            float pointRelativeOffset = (newStops[y].offset - offset1) / totalDist;
+            float weighting = powf(pointRelativeOffset, logf(.5f) / logf(hintRelativeOffset));
+            newStops[y].color = interpolate(leftColor, rightColor, weighting);
+        }
+
+        // Replace the color hint with the new color stops.
+        stops.remove(x);
+        stops.insert(x, newStops, 9);
+        indexOffset += 8;
+    }
+}
+
 void CSSGradientValue::addStops(Gradient* gradient, const CSSToLengthConversionData& conversionData, float maxLengthForRepeat)
 {
     if (m_gradientType == CSSDeprecatedLinearGradient || m_gradientType == CSSDeprecatedRadialGradient) {
         sortStopsIfNeeded();
 
         for (unsigned i = 0; i < m_stops.size(); i++) {
             const CSSGradientColorStop& stop = m_stops[i];
 
             float offset;
             if (stop.m_position->isPercentage())
                 offset = stop.m_position->getFloatValue(CSSPrimitiveValue::CSS_PERCENTAGE) / 100;
             else
                 offset = stop.m_position->getFloatValue(CSSPrimitiveValue::CSS_NUMBER);
 
             gradient->addColorStop(offset, stop.m_resolvedColor);
         }
 
         return;
     }
 
     size_t numStops = m_stops.size();
 
     Vector<GradientStop> stops(numStops);
 
     float gradientLength = 0;
     bool computedGradientLength = false;
 
+    size_t numColorHints = 0;

[f(malita), 2014/10/08 16:13:54]

I don't think we really care about the number here, this can be bool hasHints =
false;

[rosca, 2014/10/08 17:18:51]

Done.

+
     FloatPoint gradientStart = gradient->p0();
     FloatPoint gradientEnd;
     if (isLinearGradientValue())
         gradientEnd = gradient->p1();
     else if (isRadialGradientValue())
         gradientEnd = gradientStart + FloatSize(gradient->endRadius(), 0);
 
     for (size_t i = 0; i < numStops; ++i) {
         const CSSGradientColorStop& stop = m_stops[i];
 
-        stops[i].color = stop.m_resolvedColor;
+        if (stop.m_color)

[f(malita), 2014/10/08 16:13:54]

!stop.isHint()?

[rosca, 2014/10/08 17:18:51]

Done.

+            stops[i].color = stop.m_resolvedColor;
+        else
+            ++numColorHints;

[f(malita), 2014/10/08 16:13:54]

hasHints = true?

[rosca, 2014/10/08 17:18:51]

Done.

 
         if (stop.m_position) {
             if (stop.m_position->isPercentage())
                 stops[i].offset = stop.m_position->getFloatValue(CSSPrimitiveValue::CSS_PERCENTAGE) / 100;
             else if (stop.m_position->isLength() || stop.m_position->isCalculatedPercentageWithLength()) {
                 if (!computedGradientLength) {
                     FloatSize gradientSize(gradientStart - gradientEnd);
                     gradientLength = gradientSize.diagonalLength();
                 }
                 float length;
@@ skipping 57 matching lines @@
 
                     for (size_t j = unspecifiedRunStart; j < unspecifiedRunEnd; ++j)
                         stops[j].offset = lastSpecifiedOffset + (j - unspecifiedRunStart + 1) * delta;
                 }
 
                 inUnspecifiedRun = false;
             }
         }
     }
 
+    ASSERT(stops.size() == m_stops.size());
+    if (numColorHints) {

[f(malita), 2014/10/08 16:13:54]

hasHints?

[rosca, 2014/10/08 17:18:51]

Done.

+        replaceColorHintsWithColorStops(stops, m_stops);
+        numStops = stops.size();
+    }
+
     // If the gradient is repeating, repeat the color stops.
     // We can't just push this logic down into the platform-specific Gradient code,
     // because we have to know the extent of the gradient, and possible move the end points.
     if (m_repeating && numStops > 1) {
         // If the difference in the positions of the first and last color-stops is 0,
         // the gradient defines a solid-color image with the color of the last color-stop in the rule.
         float gradientRange = stops[numStops - 1].offset - stops[0].offset;
         if (!gradientRange) {
             stops.first().offset = 0;
             stops.first().color = stops.last().color;
@@ skipping 195 matching lines @@
 
         if (stop.m_position->isFontRelativeLength())
             return false;
     }
 
     return true;
 }
 
 bool CSSGradientValue::knownToBeOpaque(const RenderObject*) const
 {
-    for (size_t i = 0; i < m_stops.size(); ++i) {
-        if (m_stops[i].m_resolvedColor.hasAlpha())
+    for (auto& stop : m_stops) {
+        if (stop.m_color && stop.m_resolvedColor.hasAlpha())

[f(malita), 2014/10/08 16:13:54]

!stop.isHint()?

[rosca, 2014/10/08 17:18:52]

Done.

             return false;
     }
     return true;
 }
 
 void CSSGradientValue::traceAfterDispatch(Visitor* visitor)
 {
     visitor->trace(m_firstX);
     visitor->trace(m_firstY);
     visitor->trace(m_secondX);
@@ skipping 89 matching lines @@
             wroteSomething = true;
         }
 
         if (wroteSomething)
             result.appendLiteral(", ");
 
         for (unsigned i = 0; i < m_stops.size(); i++) {
             const CSSGradientColorStop& stop = m_stops[i];
             if (i)
                 result.appendLiteral(", ");
-            result.append(stop.m_color->cssText());
-            if (stop.m_position) {
+            if (stop.m_color)
+                result.append(stop.m_color->cssText());
+            if (stop.m_color && stop.m_position)
                 result.append(' ');
+            if (stop.m_position)
                 result.append(stop.m_position->cssText());
-            }
         }
 
     }
 
     result.append(')');
     return result.toString();
 }
 
 // Compute the endpoints so that a gradient of the given angle covers a box of the given size.
 static void endPointsFromAngle(float angleDeg, const IntSize& size, FloatPoint& firstPoint, FloatPoint& secondPoint, CSSGradientType type)
@@ skipping 297 matching lines @@
             wroteSomething = true;
         }
 
         if (wroteSomething)
             result.appendLiteral(", ");
 
         for (unsigned i = 0; i < m_stops.size(); i++) {
             const CSSGradientColorStop& stop = m_stops[i];
             if (i)
                 result.appendLiteral(", ");
-            result.append(stop.m_color->cssText());
-            if (stop.m_position) {
+            if (stop.m_color)
+                result.append(stop.m_color->cssText());
+            if (stop.m_color && stop.m_position)
                 result.append(' ');
+            if (stop.m_position)
                 result.append(stop.m_position->cssText());
-            }
         }
 
     }
 
     result.append(')');
     return result.toString();
 }
 
 float CSSRadialGradientValue::resolveRadius(CSSPrimitiveValue* radius, const CSSToLengthConversionData& conversionData, float* widthOrHeight)
 {
@@ skipping 278 matching lines @@
     visitor->trace(m_firstRadius);
     visitor->trace(m_secondRadius);
     visitor->trace(m_shape);
     visitor->trace(m_sizingBehavior);
     visitor->trace(m_endHorizontalSize);
     visitor->trace(m_endVerticalSize);
     CSSGradientValue::traceAfterDispatch(visitor);
 }
 
 } // namespace blink