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
27namespace WebCore {
28
29static const float kPathSegmentLengthTolerance = 0.00001f;
30
31static 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
36static 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
43struct 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 bool operator==(const QuadraticBezier& rhs) const
53 {
54 return start == rhs.start
55 && control == rhs.control
56 && end == rhs.end;
57 }
58
59 float approximateDistance() const
60 {
61 return distanceLine(start, control) + distanceLine(control, end);
62 }
63
64 bool split(QuadraticBezier& left, QuadraticBezier& right) const
65 {
66 left.control = midPoint(start, control);
67 right.control = midPoint(control, end);
68
69 FloatPoint leftControlToRightControl = midPoint(left.control, right.control);
70 left.end = leftControlToRightControl;
71 right.start = leftControlToRightControl;
72
73 left.start = start;
74 right.end = end;
75
76 return !(left == *this) && !(right == *this);
77 }
78
79 FloatPoint start;
80 FloatPoint control;
81 FloatPoint end;
82};
83
84struct CubicBezier {
85 CubicBezier() { }
86 CubicBezier(const FloatPoint& s, const FloatPoint& c1, const FloatPoint& c2, const FloatPoint& e)
87 : start(s)
88 , control1(c1)
89 , control2(c2)
90 , end(e)
91 {
92 }
93
94 bool operator==(const CubicBezier& rhs) const
95 {
96 return start == rhs.start
97 && control1 == rhs.control1
98 && control2 == rhs.control2
99 && end == rhs.end;
100 }
101
102 float approximateDistance() const
103 {
104 return distanceLine(start, control1) + distanceLine(control1, control2) + distanceLine(control2, end);
105 }
106
107 bool split(CubicBezier& left, CubicBezier& right) const
108 {
109 FloatPoint startToControl1 = midPoint(control1, control2);
110
111 left.start = start;
112 left.control1 = midPoint(start, control1);
113 left.control2 = midPoint(left.control1, startToControl1);
114
115 right.control2 = midPoint(control2, end);
116 right.control1 = midPoint(right.control2, startToControl1);
117 right.end = end;
118
119 FloatPoint leftControl2ToRightControl1 = midPoint(left.control2, right.control1);
120 left.end = leftControl2ToRightControl1;
121 right.start = leftControl2ToRightControl1;
122
123 return !(left == *this) && !(right == *this);
124 }
125
126 FloatPoint start;
127 FloatPoint control1;
128 FloatPoint control2;
129 FloatPoint end;
130};
131
132// FIXME: This function is possibly very slow due to the ifs required for proper path measuring
133// A simple speed-up would be to use an additional boolean template parameter to control whether
134// to use the "fast" version of this function with no PathTraversalState updating, vs. the slow
135// version which does update the PathTraversalState. We'll have to shark it to see if that's necessary.
136// Another check which is possible up-front (to send us down the fast path) would be to check if
137// approximateDistance() + current total distance > desired distance
138template<class CurveType>
139static float curveLength(const PathTraversalState& traversalState, const CurveType& originalCurve, FloatPoint& previous, FloatPoint& current)
140{
141 static const unsigned curveStackDepthLimit = 20;
142 CurveType curve = originalCurve;
143 Vector<CurveType, curveStackDepthLimit> curveStack;
144 float totalLength = 0;
145
146 while (true) {
147 float length = curve.approximateDistance();
148
149 CurveType leftCurve;
150 CurveType rightCurve;
151
152 if ((length - distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance && curveStack.size() < curveStackDepthLimit && curve.split(leftCurve, rightCurve)) {
153 curve = leftCurve;
154 curveStack.append(rightCurve);
155 continue;
156 }
157
158 totalLength += length;
159 if (traversalState.action() == PathTraversalState::Action::VectorAtLength) {
160 previous = curve.start;
161 current = curve.end;
162 if (traversalState.totalLength() + totalLength > traversalState.desiredLength())
163 break;
164 }
165
166 if (curveStack.isEmpty())
167 break;
168
169 curve = curveStack.last();
170 curveStack.removeLast();
171 }
172
173 if (traversalState.action() != PathTraversalState::Action::VectorAtLength) {
174 ASSERT(curve.end == originalCurve.end);
175 previous = curve.start;
176 current = curve.end;
177 }
178
179 return totalLength;
180}
181
182PathTraversalState::PathTraversalState(Action action, float desiredLength)
183 : m_action(action)
184 , m_desiredLength(desiredLength)
185{
186 ASSERT(action != Action::TotalLength || !desiredLength);
187}
188
189void PathTraversalState::closeSubpath()
190{
191 m_totalLength += distanceLine(m_current, m_start);
192 m_current = m_start;
193}
194
195void PathTraversalState::moveTo(const FloatPoint& point)
196{
197 m_previous = m_current = m_start = point;
198}
199
200void PathTraversalState::lineTo(const FloatPoint& point)
201{
202 m_totalLength += distanceLine(m_current, point);
203 m_current = point;
204}
205
206void PathTraversalState::quadraticBezierTo(const FloatPoint& newControl, const FloatPoint& newEnd)
207{
208 m_totalLength += curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd), m_previous, m_current);
209}
210
211void PathTraversalState::cubicBezierTo(const FloatPoint& newControl1, const FloatPoint& newControl2, const FloatPoint& newEnd)
212{
213 m_totalLength += curveLength<CubicBezier>(*this, CubicBezier(m_current, newControl1, newControl2, newEnd), m_previous, m_current);
214}
215
216bool PathTraversalState::finalizeAppendPathElement()
217{
218 if (m_action == Action::TotalLength)
219 return false;
220
221 if (m_action == Action::SegmentAtLength) {
222 if (m_totalLength >= m_desiredLength)
223 m_success = true;
224 return m_success;
225 }
226
227 ASSERT(m_action == Action::VectorAtLength);
228
229 if (m_totalLength >= m_desiredLength) {
230 float slope = FloatPoint(m_current - m_previous).slopeAngleRadians();
231 float offset = m_desiredLength - m_totalLength;
232 m_current.move(offset * cosf(slope), offset * sinf(slope));
233
234 if (!m_isZeroVector && !m_desiredLength)
235 m_isZeroVector = true;
236 else {
237 m_success = true;
238 m_normalAngle = rad2deg(slope);
239 }
240 }
241
242 m_previous = m_current;
243 return m_success;
244}
245
246bool PathTraversalState::appendPathElement(PathElementType type, const FloatPoint* points)
247{
248 switch (type) {
249 case PathElementMoveToPoint:
250 moveTo(points[0]);
251 break;
252 case PathElementAddLineToPoint:
253 lineTo(points[0]);
254 break;
255 case PathElementAddQuadCurveToPoint:
256 quadraticBezierTo(points[0], points[1]);
257 break;
258 case PathElementAddCurveToPoint:
259 cubicBezierTo(points[0], points[1], points[2]);
260 break;
261 case PathElementCloseSubpath:
262 closeSubpath();
263 break;
264 }
265
266 return finalizeAppendPathElement();
267}
268
269bool PathTraversalState::processPathElement(PathElementType type, const FloatPoint* points)
270{
271 if (m_success)
272 return true;
273
274 if (m_isZeroVector) {
275 PathTraversalState traversalState(*this);
276 m_success = traversalState.appendPathElement(type, points);
277 m_normalAngle = traversalState.m_normalAngle;
278 return m_success;
279 }
280
281 return appendPathElement(type, points);
282}
283
284}
285
286