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
26namespace blink {
27
28static 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
33static 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
38struct QuadraticBezier {
39    QuadraticBezier() { }
40    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
48    double magnitudeSquared() const
49    {
50        return ((double)(start.dot(start)) + (double)(control.dot(control)) + (double)(end.dot(end))) / 9.0;
51    }
52
53    float approximateDistance() const
54    {
55        return distanceLine(start, control) + distanceLine(control, end);
56    }
57
58    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
79struct CubicBezier {
80    CubicBezier() { }
81    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
90    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
95    float approximateDistance() const
96    {
97        return distanceLine(start, control1) + distanceLine(control1, control2) + distanceLine(control2, end);
98    }
99
100    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
126template<class CurveType>
127static 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
165PathTraversalState::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
175float PathTraversalState::closeSubpath()
176{
177    float distance = distanceLine(m_current, m_start);
178    m_current = m_start;
179    return distance;
180}
181
182float PathTraversalState::moveTo(const FloatPoint& point)
183{
184    m_current = m_start = point;
185    return 0;
186}
187
188float PathTraversalState::lineTo(const FloatPoint& point)
189{
190    float distance = distanceLine(m_current, point);
191    m_current = point;
192    return distance;
193}
194
195float 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
205float 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
215void 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