code.vuplus.com Git - vuplus_webkit/blob - Source/WebCore/platform/graphics/PathTraversalState.cpp

   1 /*
   2  * Copyright (C) 2006, 2007 Eric Seidel <eric@webkit.org>
   3  *
   4  * This library is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU Library General Public
   6  * License as published by the Free Software Foundation; either
   7  * version 2 of the License, or (at your option) any later version.
   8  *
   9  * This library is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  12  * Library General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU Library General Public License
  15  * along with this library; see the file COPYING.LIB.  If not, write to
  16  * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
  17  * Boston, MA 02110-1301, USA.
  18  */
  19
  20 #include "config.h"
  21 #include "PathTraversalState.h"
  22
  23 #include <wtf/MathExtras.h>
  24 #include <wtf/Vector.h>
  25
  26 namespace WebCore {
  27
  28 static const float kPathSegmentLengthTolerance = 0.00001f;
  29
  30 static inline FloatPoint midPoint(const FloatPoint& first, const FloatPoint& second)
  31 {
  32     return FloatPoint((first.x() + second.x()) / 2.0f, (first.y() + second.y()) / 2.0f);
  33 }
  34
  35 static inline float distanceLine(const FloatPoint& start, const FloatPoint& end)
  36 {
  37     return sqrtf((end.x() - start.x()) * (end.x() - start.x()) + (end.y() - start.y()) * (end.y() - start.y()));
  38 }
  39
  40 struct QuadraticBezier {
  41     QuadraticBezier() { }
  42     QuadraticBezier(const FloatPoint& s, const FloatPoint& c, const FloatPoint& e)
  43         : start(s)
  44         , control(c)
  45         , end(e)
  46     {
  47     }
  48
  49     float approximateDistance() const
  50     {
  51         return distanceLine(start, control) + distanceLine(control, end);
  52     }
  53
  54     void split(QuadraticBezier& left, QuadraticBezier& right) const
  55     {
  56         left.control = midPoint(start, control);
  57         right.control = midPoint(control, end);
  58
  59         FloatPoint leftControlToRightControl = midPoint(left.control, right.control);
  60         left.end = leftControlToRightControl;
  61         right.start = leftControlToRightControl;
  62
  63         left.start = start;
  64         right.end = end;
  65     }
  66
  67     FloatPoint start;
  68     FloatPoint control;
  69     FloatPoint end;
  70 };
  71
  72 struct CubicBezier {
  73     CubicBezier() { }
  74     CubicBezier(const FloatPoint& s, const FloatPoint& c1, const FloatPoint& c2, const FloatPoint& e)
  75         : start(s)
  76         , control1(c1)
  77         , control2(c2)
  78         , end(e)
  79     {
  80     }
  81
  82     float approximateDistance() const
  83     {
  84         return distanceLine(start, control1) + distanceLine(control1, control2) + distanceLine(control2, end);
  85     }
  86
  87     void split(CubicBezier& left, CubicBezier& right) const
  88     {
  89         FloatPoint startToControl1 = midPoint(control1, control2);
  90
  91         left.start = start;
  92         left.control1 = midPoint(start, control1);
  93         left.control2 = midPoint(left.control1, startToControl1);
  94
  95         right.control2 = midPoint(control2, end);
  96         right.control1 = midPoint(right.control2, startToControl1);
  97         right.end = end;
  98
  99         FloatPoint leftControl2ToRightControl1 = midPoint(left.control2, right.control1);
 100         left.end = leftControl2ToRightControl1;
 101         right.start = leftControl2ToRightControl1;
 102     }
 103
 104     FloatPoint start;
 105     FloatPoint control1;
 106     FloatPoint control2;
 107     FloatPoint end;
 108 };
 109
 110 // FIXME: This function is possibly very slow due to the ifs required for proper path measuring
 111 // A simple speed-up would be to use an additional boolean template parameter to control whether
 112 // to use the "fast" version of this function with no PathTraversalState updating, vs. the slow
 113 // version which does update the PathTraversalState.  We'll have to shark it to see if that's necessary.
 114 // Another check which is possible up-front (to send us down the fast path) would be to check if
 115 // approximateDistance() + current total distance > desired distance
 116 template<class CurveType>
 117 static float curveLength(PathTraversalState& traversalState, CurveType curve)
 118 {
 119     static const unsigned curveStackDepthLimit = 20;
 120
 121     Vector<CurveType> curveStack;
 122     curveStack.append(curve);
 123
 124     float totalLength = 0;
 125     do {
 126         float length = curve.approximateDistance();
 127         if ((length - distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance && curveStack.size() <= curveStackDepthLimit) {
 128             CurveType leftCurve;
 129             CurveType rightCurve;
 130             curve.split(leftCurve, rightCurve);
 131             curve = leftCurve;
 132             curveStack.append(rightCurve);
 133         } else {
 134             totalLength += length;
 135             if (traversalState.m_action == PathTraversalState::TraversalPointAtLength
 136              || traversalState.m_action == PathTraversalState::TraversalNormalAngleAtLength) {
 137                 traversalState.m_previous = curve.start;
 138                 traversalState.m_current = curve.end;
 139                 if (traversalState.m_totalLength + totalLength > traversalState.m_desiredLength)
 140                     return totalLength;
 141             }
 142             curve = curveStack.last();
 143             curveStack.removeLast();
 144         }
 145     } while (!curveStack.isEmpty());
 146
 147     return totalLength;
 148 }
 149
 150 PathTraversalState::PathTraversalState(PathTraversalAction action)
 151     : m_action(action)
 152     , m_success(false)
 153     , m_totalLength(0)
 154     , m_segmentIndex(0)
 155     , m_desiredLength(0)
 156     , m_normalAngle(0)
 157 {
 158 }
 159
 160 float PathTraversalState::closeSubpath()
 161 {
 162     float distance = distanceLine(m_current, m_start);
 163     m_current = m_control1 = m_control2 = m_start;
 164     return distance;
 165 }
 166
 167 float PathTraversalState::moveTo(const FloatPoint& point)
 168 {
 169     m_current = m_start = m_control1 = m_control2 = point;
 170     return 0;
 171 }
 172
 173 float PathTraversalState::lineTo(const FloatPoint& point)
 174 {
 175     float distance = distanceLine(m_current, point);
 176     m_current = m_control1 = m_control2 = point;
 177     return distance;
 178 }
 179
 180 float PathTraversalState::quadraticBezierTo(const FloatPoint& newControl, const FloatPoint& newEnd)
 181 {
 182     float distance = curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd));
 183
 184     m_control1 = newControl;
 185     m_control2 = newEnd;
 186
 187     if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength)
 188         m_current = newEnd;
 189
 190     return distance;
 191 }
 192
 193 float PathTraversalState::cubicBezierTo(const FloatPoint& newControl1, const FloatPoint& newControl2, const FloatPoint& newEnd)
 194 {
 195     float distance = curveLength<CubicBezier>(*this, CubicBezier(m_current, newControl1, newControl2, newEnd));
 196
 197     m_control1 = newEnd;
 198     m_control2 = newControl2;
 199
 200     if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength)
 201         m_current = newEnd;
 202
 203     return distance;
 204 }
 205
 206 void PathTraversalState::processSegment()
 207 {
 208     if (m_action == TraversalSegmentAtLength && m_totalLength >= m_desiredLength)
 209         m_success = true;
 210
 211     if ((m_action == TraversalPointAtLength || m_action == TraversalNormalAngleAtLength) && m_totalLength >= m_desiredLength) {
 212         FloatSize change = m_current - m_previous;
 213         float slope = atan2f(change.height(), change.width());
 214         if (m_action == TraversalPointAtLength) {
 215             float offset = m_desiredLength - m_totalLength;
 216             m_current.move(offset * cosf(slope), offset * sinf(slope));
 217         } else
 218             m_normalAngle = rad2deg(slope);
 219         m_success = true;
 220     }
 221     m_previous = m_current;
 222 }
 223
 224 }
 225