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
26namespace WebCore {
27
28static const float kPathSegmentLengthTolerance = 0.00001f;
29
30static 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
35static 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
40struct 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
72struct 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
116template<class CurveType>
117static 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
150PathTraversalState::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
160float 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
167float PathTraversalState::moveTo(const FloatPoint& point)
168{
169    m_current = m_start = m_control1 = m_control2 = point;
170    return 0;
171}
172
173float 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
180float 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
193float 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
206void 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
225