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