• Home
  • History
  • Annotate
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 blink {
27 
midPoint(const FloatPoint & first,const FloatPoint & second)28 static inline FloatPoint midPoint(const FloatPoint& first, const FloatPoint& second)
29 {
30     return FloatPoint((first.x() + second.x()) / 2.0f, (first.y() + second.y()) / 2.0f);
31 }
32 
distanceLine(const FloatPoint & start,const FloatPoint & end)33 static inline float distanceLine(const FloatPoint& start, const FloatPoint& end)
34 {
35     return sqrtf((end.x() - start.x()) * (end.x() - start.x()) + (end.y() - start.y()) * (end.y() - start.y()));
36 }
37 
38 struct QuadraticBezier {
QuadraticBezierblink::QuadraticBezier39     QuadraticBezier() { }
QuadraticBezierblink::QuadraticBezier40     QuadraticBezier(const FloatPoint& s, const FloatPoint& c, const FloatPoint& e)
41         : start(s)
42         , control(c)
43         , end(e)
44         , splitDepth(0)
45     {
46     }
47 
magnitudeSquaredblink::QuadraticBezier48     double magnitudeSquared() const
49     {
50         return ((double)(start.dot(start)) + (double)(control.dot(control)) + (double)(end.dot(end))) / 9.0;
51     }
52 
approximateDistanceblink::QuadraticBezier53     float approximateDistance() const
54     {
55         return distanceLine(start, control) + distanceLine(control, end);
56     }
57 
splitblink::QuadraticBezier58     void split(QuadraticBezier& left, QuadraticBezier& right) const
59     {
60         left.control = midPoint(start, control);
61         right.control = midPoint(control, end);
62 
63         FloatPoint leftControlToRightControl = midPoint(left.control, right.control);
64         left.end = leftControlToRightControl;
65         right.start = leftControlToRightControl;
66 
67         left.start = start;
68         right.end = end;
69 
70         left.splitDepth = right.splitDepth = splitDepth + 1;
71     }
72 
73     FloatPoint start;
74     FloatPoint control;
75     FloatPoint end;
76     unsigned short splitDepth;
77 };
78 
79 struct CubicBezier {
CubicBezierblink::CubicBezier80     CubicBezier() { }
CubicBezierblink::CubicBezier81     CubicBezier(const FloatPoint& s, const FloatPoint& c1, const FloatPoint& c2, const FloatPoint& e)
82         : start(s)
83         , control1(c1)
84         , control2(c2)
85         , end(e)
86         , splitDepth(0)
87     {
88     }
89 
magnitudeSquaredblink::CubicBezier90     double magnitudeSquared() const
91     {
92         return ((double)(start.dot(start)) + (double)(control1.dot(control1)) + (double)(control2.dot(control2)) + (double)(end.dot(end))) / 16.0;
93     }
94 
approximateDistanceblink::CubicBezier95     float approximateDistance() const
96     {
97         return distanceLine(start, control1) + distanceLine(control1, control2) + distanceLine(control2, end);
98     }
99 
splitblink::CubicBezier100     void split(CubicBezier& left, CubicBezier& right) const
101     {
102         FloatPoint startToControl1 = midPoint(control1, control2);
103 
104         left.start = start;
105         left.control1 = midPoint(start, control1);
106         left.control2 = midPoint(left.control1, startToControl1);
107 
108         right.control2 = midPoint(control2, end);
109         right.control1 = midPoint(right.control2, startToControl1);
110         right.end = end;
111 
112         FloatPoint leftControl2ToRightControl1 = midPoint(left.control2, right.control1);
113         left.end = leftControl2ToRightControl1;
114         right.start = leftControl2ToRightControl1;
115 
116         left.splitDepth = right.splitDepth = splitDepth + 1;
117     }
118 
119     FloatPoint start;
120     FloatPoint control1;
121     FloatPoint control2;
122     FloatPoint end;
123     unsigned short splitDepth;
124 };
125 
126 template<class CurveType>
curveLength(PathTraversalState & traversalState,CurveType curve)127 static float curveLength(PathTraversalState& traversalState, CurveType curve)
128 {
129     static const unsigned short curveSplitDepthLimit = 20;
130     static const double pathSegmentLengthToleranceSquared = 1.e-16;
131 
132     double curveScaleForToleranceSquared = curve.magnitudeSquared();
133     if (curveScaleForToleranceSquared < pathSegmentLengthToleranceSquared)
134         return 0;
135 
136     Vector<CurveType> curveStack;
137     curveStack.append(curve);
138 
139     float totalLength = 0;
140     do {
141         float length = curve.approximateDistance();
142         double lengthDiscrepancy = length - distanceLine(curve.start, curve.end);
143         if ((lengthDiscrepancy * lengthDiscrepancy) / curveScaleForToleranceSquared > pathSegmentLengthToleranceSquared && curve.splitDepth < curveSplitDepthLimit) {
144             CurveType leftCurve;
145             CurveType rightCurve;
146             curve.split(leftCurve, rightCurve);
147             curve = leftCurve;
148             curveStack.append(rightCurve);
149         } else {
150             totalLength += length;
151             if (traversalState.m_action == PathTraversalState::TraversalPointAtLength || traversalState.m_action == PathTraversalState::TraversalNormalAngleAtLength) {
152                 traversalState.m_previous = curve.start;
153                 traversalState.m_current = curve.end;
154                 if (traversalState.m_totalLength + totalLength > traversalState.m_desiredLength)
155                     return totalLength;
156             }
157             curve = curveStack.last();
158             curveStack.removeLast();
159         }
160     } while (!curveStack.isEmpty());
161 
162     return totalLength;
163 }
164 
PathTraversalState(PathTraversalAction action)165 PathTraversalState::PathTraversalState(PathTraversalAction action)
166     : m_action(action)
167     , m_success(false)
168     , m_totalLength(0)
169     , m_segmentIndex(0)
170     , m_desiredLength(0)
171     , m_normalAngle(0)
172 {
173 }
174 
closeSubpath()175 float PathTraversalState::closeSubpath()
176 {
177     float distance = distanceLine(m_current, m_start);
178     m_current = m_start;
179     return distance;
180 }
181 
moveTo(const FloatPoint & point)182 float PathTraversalState::moveTo(const FloatPoint& point)
183 {
184     m_current = m_start = point;
185     return 0;
186 }
187 
lineTo(const FloatPoint & point)188 float PathTraversalState::lineTo(const FloatPoint& point)
189 {
190     float distance = distanceLine(m_current, point);
191     m_current = point;
192     return distance;
193 }
194 
quadraticBezierTo(const FloatPoint & newControl,const FloatPoint & newEnd)195 float PathTraversalState::quadraticBezierTo(const FloatPoint& newControl, const FloatPoint& newEnd)
196 {
197     float distance = curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd));
198 
199     if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength)
200         m_current = newEnd;
201 
202     return distance;
203 }
204 
cubicBezierTo(const FloatPoint & newControl1,const FloatPoint & newControl2,const FloatPoint & newEnd)205 float PathTraversalState::cubicBezierTo(const FloatPoint& newControl1, const FloatPoint& newControl2, const FloatPoint& newEnd)
206 {
207     float distance = curveLength<CubicBezier>(*this, CubicBezier(m_current, newControl1, newControl2, newEnd));
208 
209     if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength)
210         m_current = newEnd;
211 
212     return distance;
213 }
214 
processSegment()215 void PathTraversalState::processSegment()
216 {
217     if (m_action == TraversalSegmentAtLength && m_totalLength >= m_desiredLength)
218         m_success = true;
219 
220     if ((m_action == TraversalPointAtLength || m_action == TraversalNormalAngleAtLength) && m_totalLength >= m_desiredLength) {
221         float slope = FloatPoint(m_current - m_previous).slopeAngleRadians();
222         if (m_action == TraversalPointAtLength) {
223             float offset = m_desiredLength - m_totalLength;
224             m_current.move(offset * cosf(slope), offset * sinf(slope));
225         } else {
226             m_normalAngle = rad2deg(slope);
227         }
228         m_success = true;
229     }
230     m_previous = m_current;
231 }
232 
233 } // namespace blink
234 
235