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 "platform/graphics/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
midPoint(const FloatPoint & first,const FloatPoint & second)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
distanceLine(const FloatPoint & start,const FloatPoint & end)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 {
QuadraticBezierWebCore::QuadraticBezier41 QuadraticBezier() { }
QuadraticBezierWebCore::QuadraticBezier42 QuadraticBezier(const FloatPoint& s, const FloatPoint& c, const FloatPoint& e)
43 : start(s)
44 , control(c)
45 , end(e)
46 {
47 }
48
approximateDistanceWebCore::QuadraticBezier49 float approximateDistance() const
50 {
51 return distanceLine(start, control) + distanceLine(control, end);
52 }
53
splitWebCore::QuadraticBezier54 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 {
CubicBezierWebCore::CubicBezier73 CubicBezier() { }
CubicBezierWebCore::CubicBezier74 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
approximateDistanceWebCore::CubicBezier82 float approximateDistance() const
83 {
84 return distanceLine(start, control1) + distanceLine(control1, control2) + distanceLine(control2, end);
85 }
86
splitWebCore::CubicBezier87 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>
curveLength(PathTraversalState & traversalState,CurveType curve)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 || traversalState.m_action == PathTraversalState::TraversalNormalAngleAtLength) {
136 traversalState.m_previous = curve.start;
137 traversalState.m_current = curve.end;
138 if (traversalState.m_totalLength + totalLength > traversalState.m_desiredLength)
139 return totalLength;
140 }
141 curve = curveStack.last();
142 curveStack.removeLast();
143 }
144 } while (!curveStack.isEmpty());
145
146 return totalLength;
147 }
148
PathTraversalState(PathTraversalAction action)149 PathTraversalState::PathTraversalState(PathTraversalAction action)
150 : m_action(action)
151 , m_success(false)
152 , m_totalLength(0)
153 , m_segmentIndex(0)
154 , m_desiredLength(0)
155 , m_normalAngle(0)
156 {
157 }
158
closeSubpath()159 float PathTraversalState::closeSubpath()
160 {
161 float distance = distanceLine(m_current, m_start);
162 m_current = m_control1 = m_control2 = m_start;
163 return distance;
164 }
165
moveTo(const FloatPoint & point)166 float PathTraversalState::moveTo(const FloatPoint& point)
167 {
168 m_current = m_start = m_control1 = m_control2 = point;
169 return 0;
170 }
171
lineTo(const FloatPoint & point)172 float PathTraversalState::lineTo(const FloatPoint& point)
173 {
174 float distance = distanceLine(m_current, point);
175 m_current = m_control1 = m_control2 = point;
176 return distance;
177 }
178
quadraticBezierTo(const FloatPoint & newControl,const FloatPoint & newEnd)179 float PathTraversalState::quadraticBezierTo(const FloatPoint& newControl, const FloatPoint& newEnd)
180 {
181 float distance = curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd));
182
183 m_control1 = newControl;
184 m_control2 = newEnd;
185
186 if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength)
187 m_current = newEnd;
188
189 return distance;
190 }
191
cubicBezierTo(const FloatPoint & newControl1,const FloatPoint & newControl2,const FloatPoint & newEnd)192 float PathTraversalState::cubicBezierTo(const FloatPoint& newControl1, const FloatPoint& newControl2, const FloatPoint& newEnd)
193 {
194 float distance = curveLength<CubicBezier>(*this, CubicBezier(m_current, newControl1, newControl2, newEnd));
195
196 m_control1 = newEnd;
197 m_control2 = newControl2;
198
199 if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength)
200 m_current = newEnd;
201
202 return distance;
203 }
204
processSegment()205 void PathTraversalState::processSegment()
206 {
207 if (m_action == TraversalSegmentAtLength && m_totalLength >= m_desiredLength)
208 m_success = true;
209
210 if ((m_action == TraversalPointAtLength || m_action == TraversalNormalAngleAtLength) && m_totalLength >= m_desiredLength) {
211 float slope = FloatPoint(m_current - m_previous).slopeAngleRadians();
212 if (m_action == TraversalPointAtLength) {
213 float offset = m_desiredLength - m_totalLength;
214 m_current.move(offset * cosf(slope), offset * sinf(slope));
215 } else {
216 m_normalAngle = rad2deg(slope);
217 }
218 m_success = true;
219 }
220 m_previous = m_current;
221 }
222
223 }
224
225