Faster implementation of text-decoration-skip: ink
authormmaxfield@apple.com <mmaxfield@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 21 Dec 2013 01:55:10 +0000 (01:55 +0000)
committermmaxfield@apple.com <mmaxfield@apple.com@268f45cc-cd09-0410-ab3c-d52691b4dbfc>
Sat, 21 Dec 2013 01:55:10 +0000 (01:55 +0000)
https://bugs.webkit.org/show_bug.cgi?id=125718

Reviewed by Simon Fraser.

Source/WebCore:

This new implementation of text-decoration-skip: ink extracts
each glyph into a path, then decomposes each path into a series
of contours. It then intersects each contour with the top and
bottom of the underline (by approximating the contour with a line).
It then draws underlines in between these intersection regions.

Tests for text-decoration-skip: ink already exist in
fast/css3-text/css3-text-decoration/text-decoration-skip

* platform/graphics/Font.h: Signature of new function
* platform/graphics/mac/FontMac.mm:
(WebCore::GlyphIterationState::GlyphIterationState): Persistent
between calls to findPathIntersections
(WebCore::findIntersectionPoint): Calculates an intersection point
between two lines
(WebCore::findPathIntersections): Called by CGPathApply to find
intersections of each contour
(WebCore::Font::intersectionPoints): Function to get the places
where an underline would intersect a TextRun.
* rendering/InlineTextBox.cpp:
(WebCore::compareTuples): Used for sorting intersection ranges
(WebCore::translateIntersectionPointsToSkipInkBoundaries): Converts
a sequence of intersection points to the locations where
text-decoration-skip: ink should draw underlines
(WebCore::drawSkipInkUnderline): Draws a sequence of short underlines
(WebCore::InlineTextBox::paintDecoration):
* rendering/TextPainter.cpp:
(WebCore::TextPainter::intersectionPoints): Calls Font::intersectionPoints
* rendering/TextPainter.h:

Source/WTF:

This creates a new preprocessor define, CSS3_TEXT_DECORATION_SKIP_INK,
which enables the use of the text-decoration-skip: ink CSS value.
Creating this new value simplifies the logic about when to enable the
codepath for this CSS value.

* wtf/Platform.h:

git-svn-id: https://svn.webkit.org/repository/webkit/trunk@160951 268f45cc-cd09-0410-ab3c-d52691b4dbfc

Source/WTF/ChangeLog
Source/WTF/wtf/Platform.h
Source/WebCore/ChangeLog
Source/WebCore/platform/graphics/Font.h
Source/WebCore/platform/graphics/mac/FontMac.mm
Source/WebCore/rendering/InlineTextBox.cpp
Source/WebCore/rendering/TextPainter.cpp
Source/WebCore/rendering/TextPainter.h

index fb073f1713a94bf02094f3b74aa6bc2dbe89519e..2a6f6055d2a489eaf09734877837273cd350b5b2 100644 (file)
@@ -1,3 +1,17 @@
+2013-12-20  Myles C. Maxfield  <mmaxfield@apple.com>
+
+        Faster implementation of text-decoration-skip: ink
+        https://bugs.webkit.org/show_bug.cgi?id=125718
+
+        Reviewed by Simon Fraser.
+
+        This creates a new preprocessor define, CSS3_TEXT_DECORATION_SKIP_INK,
+        which enables the use of the text-decoration-skip: ink CSS value.
+        Creating this new value simplifies the logic about when to enable the
+        codepath for this CSS value.
+
+        * wtf/Platform.h:
+
 2013-12-20  Simon Fraser  <simon.fraser@apple.com>
 
         Change "threaded scrolling" terminology to "asynchronous scrolling"
index d7e7b4669be08eef42e3843b4b58540885bc6b03..e1ebfd3392ced5c8af6d63932713e79438b9d8cf 100644 (file)
 #define ENABLE_OPENTYPE_VERTICAL 1
 #endif
 
+#if ENABLE(CSS3_TEXT_DECORATION) && PLATFORM(MAC)
+#define ENABLE_CSS3_TEXT_DECORATION_SKIP_INK 1
+#endif
+
 #endif /* WTF_Platform_h */
index c6702d7483536c724c46688c86d230858b9d7d1c..7638c06b4f5e0214dafc510c1efd6807846fd4f4 100644 (file)
@@ -1,3 +1,40 @@
+2013-12-20  Myles C. Maxfield  <mmaxfield@apple.com>
+
+        Faster implementation of text-decoration-skip: ink
+        https://bugs.webkit.org/show_bug.cgi?id=125718
+
+        Reviewed by Simon Fraser.
+
+        This new implementation of text-decoration-skip: ink extracts
+        each glyph into a path, then decomposes each path into a series
+        of contours. It then intersects each contour with the top and
+        bottom of the underline (by approximating the contour with a line).
+        It then draws underlines in between these intersection regions.
+
+        Tests for text-decoration-skip: ink already exist in
+        fast/css3-text/css3-text-decoration/text-decoration-skip
+
+        * platform/graphics/Font.h: Signature of new function
+        * platform/graphics/mac/FontMac.mm:
+        (WebCore::GlyphIterationState::GlyphIterationState): Persistent
+        between calls to findPathIntersections
+        (WebCore::findIntersectionPoint): Calculates an intersection point
+        between two lines
+        (WebCore::findPathIntersections): Called by CGPathApply to find
+        intersections of each contour
+        (WebCore::Font::intersectionPoints): Function to get the places
+        where an underline would intersect a TextRun.
+        * rendering/InlineTextBox.cpp:
+        (WebCore::compareTuples): Used for sorting intersection ranges
+        (WebCore::translateIntersectionPointsToSkipInkBoundaries): Converts
+        a sequence of intersection points to the locations where
+        text-decoration-skip: ink should draw underlines
+        (WebCore::drawSkipInkUnderline): Draws a sequence of short underlines
+        (WebCore::InlineTextBox::paintDecoration):
+        * rendering/TextPainter.cpp:
+        (WebCore::TextPainter::intersectionPoints): Calls Font::intersectionPoints
+        * rendering/TextPainter.h:
+
 2013-12-20  Joseph Pecoraro  <pecoraro@apple.com>
 
         Web Inspector: Give the CommandLineAPIModule its own Host object, making InjectedScriptHost viable for a JS Context
index 9fb579f6d471c00f48c36eadadf6314da6c83015..c3f3706666bdcfa8f41385962f2cfedb057a98e5 100644 (file)
@@ -25,6 +25,7 @@
 #ifndef Font_h
 #define Font_h
 
+#include "DashArray.h"
 #include "FontDescription.h"
 #include "FontGlyphs.h"
 #include "SimpleFontData.h"
@@ -100,6 +101,8 @@ public:
     void drawText(GraphicsContext*, const TextRun&, const FloatPoint&, int from = 0, int to = -1, CustomFontNotReadyAction = DoNotPaintIfFontNotReady) const;
     void drawEmphasisMarks(GraphicsContext*, const TextRun&, const AtomicString& mark, const FloatPoint&, int from = 0, int to = -1) const;
 
+    DashArray dashesForIntersectionsWithRect(const TextRun&, const FloatPoint& textOrigin, int from, int to, const FloatRect& lineExtents) const;
+
     float width(const TextRun&, HashSet<const SimpleFontData*>* fallbackFonts = 0, GlyphOverflow* = 0) const;
     float width(const TextRun&, int& charsConsumed, String& glyphName) const;
 
index 718c16d9605612c9089d0403d60a031d8f3041fc..98fb78cd028307c7be262d01c12176609ca8bc70 100644 (file)
@@ -23,6 +23,7 @@
 #import "config.h"
 #import "Font.h"
 
+#import "DashArray.h"
 #import "GlyphBuffer.h"
 #import "GraphicsContext.h"
 #import "Logging.h"
@@ -323,4 +324,103 @@ void Font::drawGlyphs(GraphicsContext* context, const SimpleFontData* font, cons
 #endif
 }
 
+#if ENABLE(CSS3_TEXT_DECORATION_SKIP_INK)
+struct GlyphIterationState {
+    GlyphIterationState(CGPoint startingPoint, CGPoint currentPoint, CGFloat y1, CGFloat y2, CGFloat minX, CGFloat maxX)
+        : startingPoint(startingPoint)
+        , currentPoint(currentPoint)
+        , y1(y1)
+        , y2(y2)
+        , minX(minX)
+        , maxX(maxX)
+    {
+    }
+    CGPoint startingPoint;
+    CGPoint currentPoint;
+    CGFloat y1;
+    CGFloat y2;
+    CGFloat minX;
+    CGFloat maxX;
+};
+
+static bool findIntersectionPoint(float y, CGPoint p1, CGPoint p2, CGFloat& x)
+{
+    x = p1.x + (y - p1.y) * (p2.x - p1.x) / (p2.y - p1.y);
+    return (p1.y < y && p2.y > y) || (p1.y > y && p2.y < y);
+}
+
+// This function is called by CGPathApply and is therefore invoked for each
+// contour in a glyph. This function models each contours as a straight line
+// and calculates the intersections between each pseudo-contour and
+// two horizontal lines (the upper and lower bounds of an underline) found in
+// GlyphIterationState::y1 and GlyphIterationState::y2. It keeps track of the
+// leftmost and rightmost intersection in GlyphIterationState::minX and
+// GlyphIterationState::maxX.
+static void findPathIntersections(void* stateAsVoidPointer, const CGPathElement* e)
+{
+    auto& state = *static_cast<GlyphIterationState*>(stateAsVoidPointer);
+    bool doIntersection = false;
+    CGPoint point = CGPointZero;
+    switch (e->type) {
+    case kCGPathElementMoveToPoint:
+        state.startingPoint = e->points[0];
+        state.currentPoint = e->points[0];
+        break;
+    case kCGPathElementAddLineToPoint:
+        doIntersection = true;
+        point = e->points[0];
+        break;
+    case kCGPathElementAddQuadCurveToPoint:
+        doIntersection = true;
+        point = e->points[1];
+        break;
+    case kCGPathElementAddCurveToPoint:
+        doIntersection = true;
+        point = e->points[2];
+        break;
+    case kCGPathElementCloseSubpath:
+        doIntersection = true;
+        point = state.startingPoint;
+        break;
+    }
+    if (!doIntersection)
+        return;
+    CGFloat x;
+    if (findIntersectionPoint(state.y1, state.currentPoint, point, x)) {
+        state.minX = std::min(state.minX, x);
+        state.maxX = std::max(state.maxX, x);
+    }
+    if (findIntersectionPoint(state.y2, state.currentPoint, point, x)) {
+        state.minX = std::min(state.minX, x);
+        state.maxX = std::max(state.maxX, x);
+    }
+    state.currentPoint = point;
+}
+
+DashArray Font::dashesForIntersectionsWithRect(const TextRun& run, const FloatPoint& textOrigin, int textRunStartIndex, int textRunEndIndex, const FloatRect& lineExtents) const
+{
+    float deltaX;
+    GlyphBuffer glyphBuffer;
+    if (codePath(run) != Complex)
+        deltaX = getGlyphsAndAdvancesForSimpleText(run, textRunStartIndex, textRunEndIndex, glyphBuffer);
+    else
+        deltaX = getGlyphsAndAdvancesForComplexText(run, textRunStartIndex, textRunEndIndex, glyphBuffer);
+    CGAffineTransform translation = CGAffineTransformMakeTranslation(textOrigin.x() + deltaX, textOrigin.y());
+    translation = CGAffineTransformScale(translation, 1, -1);
+    DashArray result;
+    for (int i = 0; i < glyphBuffer.size(); ++i) {
+        GlyphIterationState info = GlyphIterationState(CGPointMake(0, 0), CGPointMake(0, 0), lineExtents.y(), lineExtents.y() + lineExtents.height(), lineExtents.x() + lineExtents.width(), lineExtents.x());
+        RetainPtr<CGPathRef> path = adoptCF(CTFontCreatePathForGlyph(glyphBuffer.fontDataAt(i)->platformData().ctFont(), glyphBuffer.glyphAt(i), &translation));
+        CGPathApply(path.get(), &info, &findPathIntersections);
+        if (info.minX < info.maxX) {
+            result.append(info.minX - lineExtents.x());
+            result.append(info.maxX - lineExtents.x());
+        }
+        GlyphBufferAdvance advance = glyphBuffer.advanceAt(i);
+        translation = CGAffineTransformTranslate(translation, advance.width(), advance.height());
+    }
+    return result;
+}
+#endif
+
 }
index 2251272411e0ebc448ec25f66210f1ebb2e88bbf..f2522d90d926914d88d1bf7b0d1e2555a39be28f 100644 (file)
@@ -25,6 +25,7 @@
 
 #include "Chrome.h"
 #include "ChromeClient.h"
+#include "DashArray.h"
 #include "Document.h"
 #include "DocumentMarkerController.h"
 #include "Editor.h"
@@ -65,6 +66,75 @@ COMPILE_ASSERT(sizeof(InlineTextBox) == sizeof(SameSizeAsInlineTextBox), InlineT
 typedef WTF::HashMap<const InlineTextBox*, LayoutRect> InlineTextBoxOverflowMap;
 static InlineTextBoxOverflowMap* gTextBoxesWithOverflow;
 
+#if ENABLE(CSS3_TEXT_DECORATION_SKIP_INK)
+static bool compareTuples(std::pair<float, float> l, std::pair<float, float> r)
+{
+    return l.first < r.first;
+}
+
+static DashArray translateIntersectionPointsToSkipInkBoundaries(const DashArray& intersections, float dilationAmount, float totalWidth)
+{
+    ASSERT(!(intersections.size() % 2));
+    
+    // Step 1: Make pairs so we can sort based on range starting-point. We dilate the ranges in this step as well.
+    Vector<std::pair<float, float>> tuples;
+    for (auto i = intersections.begin(); i != intersections.end(); i++, i++)
+        tuples.append(std::make_pair(*i - dilationAmount, *(i + 1) + dilationAmount));
+    std::sort(tuples.begin(), tuples.end(), &compareTuples);
+
+    // Step 2: Deal with intersecting ranges.
+    Vector<std::pair<float, float>> intermediateTuples;
+    if (tuples.size() >= 2) {
+        intermediateTuples.append(*tuples.begin());
+        auto lastIntermediate = intermediateTuples.begin();
+        for (auto i = tuples.begin() + 1; i != tuples.end(); i++) {
+            float& firstEnd = lastIntermediate->second;
+            float secondStart = i->first;
+            float secondEnd = i->second;
+            if (secondStart <= firstEnd && secondEnd <= firstEnd) {
+                // Ignore this range completely
+            } else if (secondStart <= firstEnd)
+                firstEnd = secondEnd;
+            else {
+                intermediateTuples.append(*i);
+                ++lastIntermediate;
+            }
+        }
+    } else
+        intermediateTuples = tuples;
+
+    // Step 3: Output the space between the ranges, but only if the space warrants an underline.
+    float previous = 0;
+    DashArray result;
+    for (auto i = intermediateTuples.begin(); i != intermediateTuples.end(); i++) {
+        if (i->first - previous > dilationAmount) {
+            result.append(previous);
+            result.append(i->first);
+        }
+        previous = i->second;
+    }
+    if (totalWidth - previous > dilationAmount) {
+        result.append(previous);
+        result.append(totalWidth);
+    }
+    
+    return result;
+}
+
+static void drawSkipInkUnderline(TextPainter& textPainter, GraphicsContext& context, FloatPoint localOrigin, float underlineOffset, float width, bool isPrinting, int m_start, int m_len)
+{
+    FloatPoint adjustedLocalOrigin = localOrigin;
+    adjustedLocalOrigin.move(0, underlineOffset);
+    FloatRect underlineBoundingBox = context.computeLineBoundsForText(adjustedLocalOrigin, width, isPrinting);
+    DashArray intersections = textPainter.dashesForIntersectionsWithRect(underlineBoundingBox, m_start, m_start + m_len);
+    DashArray a = translateIntersectionPointsToSkipInkBoundaries(intersections, underlineBoundingBox.height(), width);
+
+    ASSERT(!(a.size() % 2));
+    for (auto i = a.begin(); i != a.end(); i++, i++)
+        context.drawLineForText(FloatPoint(localOrigin.x() + *i, localOrigin.y() + underlineOffset), *(i+1) - *i, isPrinting);
+}
+#endif
+
 InlineTextBox::~InlineTextBox()
 {
     if (!knownToHaveNoOverflow() && gTextBoxesWithOverflow)
@@ -1072,7 +1142,7 @@ void InlineTextBox::paintDecoration(GraphicsContext& context, const FloatPoint&
         // Offset between lines - always non-zero, so lines never cross each other.
         float doubleOffset = textDecorationThickness + 1;
         
-        bool clipDecorationToMask = lineStyle.textDecorationSkip() == TextDecorationSkipInk;
+        bool clipDecorationToMask = false;
         
         GraphicsContextStateSaver stateSaver(context, false);
         
@@ -1115,10 +1185,23 @@ void InlineTextBox::paintDecoration(GraphicsContext& context, const FloatPoint&
                 break;
             }
             default:
-                context.drawLineForText(FloatPoint(localOrigin.x(), localOrigin.y() + underlineOffset), width, isPrinting);
-
-                if (decorationStyle == TextDecorationStyleDouble)
-                    context.drawLineForText(FloatPoint(localOrigin.x(), localOrigin.y() + underlineOffset + doubleOffset), width, isPrinting);
+#if ENABLE(CSS3_TEXT_DECORATION_SKIP_INK)
+                if (lineStyle.textDecorationSkip() == TextDecorationSkipInk) {
+                    if (!context.paintingDisabled()) {
+                        drawSkipInkUnderline(textPainter, context, localOrigin, underlineOffset, width, isPrinting, m_start, m_len);
+
+                        if (decorationStyle == TextDecorationStyleDouble)
+                            drawSkipInkUnderline(textPainter, context, localOrigin, underlineOffset + doubleOffset, width, isPrinting, m_start, m_len);
+                    }
+                } else {
+#endif // CSS3_TEXT_DECORATION_SKIP_INK
+                    context.drawLineForText(FloatPoint(localOrigin.x(), localOrigin.y() + underlineOffset), width, isPrinting);
+
+                    if (decorationStyle == TextDecorationStyleDouble)
+                        context.drawLineForText(FloatPoint(localOrigin.x(), localOrigin.y() + underlineOffset + doubleOffset), width, isPrinting);
+#if ENABLE(CSS3_TEXT_DECORATION_SKIP_INK)
+                }
+#endif
             }
 #else
             // Leave one pixel of white between the baseline and the underline.
@@ -1136,11 +1219,24 @@ void InlineTextBox::paintDecoration(GraphicsContext& context, const FloatPoint&
                 break;
             }
             default:
+#if ENABLE(CSS3_TEXT_DECORATION_SKIP_INK)
+                if (lineStyle.textDecorationSkip() == TextDecorationSkipInk) {
+                    if (!context.paintingDisabled()) {
+                        drawSkipInkUnderline(textPainter, context, localOrigin, 0, width, isPrinting, m_start, m_len);
+
+                        if (decorationStyle == TextDecorationStyleDouble)
+                            drawSkipInkUnderline(textPainter, context, localOrigin, -doubleOffset, width, isPrinting, m_start, m_len);
+                    }
+                } else {
+#endif // CSS3_TEXT_DECORATION_SKIP_INK
 #endif // CSS3_TEXT_DECORATION
-                context.drawLineForText(localOrigin, width, isPrinting);
+                    context.drawLineForText(localOrigin, width, isPrinting);
 #if ENABLE(CSS3_TEXT_DECORATION)
-                if (decorationStyle == TextDecorationStyleDouble)
-                    context.drawLineForText(FloatPoint(localOrigin.x(), localOrigin.y() - doubleOffset), width, isPrinting);
+                    if (decorationStyle == TextDecorationStyleDouble)
+                        context.drawLineForText(FloatPoint(localOrigin.x(), localOrigin.y() - doubleOffset), width, isPrinting);
+#if ENABLE(CSS3_TEXT_DECORATION_SKIP_INK)
+                }
+#endif
             }
 #endif // CSS3_TEXT_DECORATION
         }
index fe8549cc55fe83235943f10315fd58b76e622159..cfd9753f21ad6a9878a478a0fbbe9f1ee36f7138 100644 (file)
@@ -176,4 +176,11 @@ void TextPainter::paintTextInContext(GraphicsContext& context, float amountToInc
     m_savedDrawingStateForMask = savedDrawingStateForMask;
 }
 
+#if ENABLE(CSS3_TEXT_DECORATION_SKIP_INK)
+DashArray TextPainter::dashesForIntersectionsWithRect(const FloatRect& lineExtents, int textRunStartIndex, int textRunEndIndex)
+{
+    return m_font.dashesForIntersectionsWithRect(m_textRun, m_textOrigin, textRunStartIndex, textRunEndIndex, lineExtents);
+}
+#endif
+
 } // namespace WebCore
index cf855a4ad348cf7aa003f3067211835fc8797a0e..af659cd09ff5300ee7dac91e78066c67abc9e073 100644 (file)
@@ -24,6 +24,7 @@
 #define TextPainter_h
 
 #include "AffineTransform.h"
+#include "DashArray.h"
 #include "RenderText.h"
 
 namespace WebCore {
@@ -67,6 +68,8 @@ public:
     void paintText();
     void paintTextInContext(GraphicsContext&, float amountToIncreaseStrokeWidthBy);
 
+    DashArray dashesForIntersectionsWithRect(const FloatRect& lineExtents, int textRunStartIndex, int textRunEndIndex);
+
 private:
     bool m_paintSelectedTextOnly;
     bool m_paintSelectedTextSeparately;