cf537172723365db0c6db8cdc9cc29c275047167
[WebKit-https.git] / 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         float slope = FloatPoint(m_current - m_previous).slopeAngleRadians();
213         if (m_action == TraversalPointAtLength) {
214             float offset = m_desiredLength - m_totalLength;
215             m_current.move(offset * cosf(slope), offset * sinf(slope));
216         } else
217             m_normalAngle = rad2deg(slope);
218         m_success = true;
219     }
220     m_previous = m_current;
221 }
222
223 }
224