1/*
2 * This file is part of the WebKit open source project.
3 *
4 * Copyright (C) 2006, 2007 Eric Seidel (eric@webkit.org)
5 *
6 * This library is free software; you can redistribute it and/or
7 * modify it under the terms of the GNU Library General Public
8 * License as published by the Free Software Foundation; either
9 * version 2 of the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14 * Library General Public License for more details.
15 *
16 * You should have received a copy of the GNU Library General Public License
17 * along with this library; see the file COPYING.LIB.  If not, write to
18 * the Free Software Foundation, Inc., 51 Franklin Street, Fifth Floor,
19 * Boston, MA 02110-1301, USA.
20 */
21
22#include "config.h"
23#include "PathTraversalState.h"
24
25#include "Path.h"
26
27#include <math.h>
28
29namespace WebCore {
30
31static const float kPathSegmentLengthTolerance = 0.00001f;
32
33static inline FloatPoint midPoint(const FloatPoint& first, const FloatPoint& second)
34{
35    return FloatPoint((first.x() + second.x()) / 2.0f, (first.y() + second.y()) / 2.0f);
36}
37
38static inline float distanceLine(const FloatPoint& start, const FloatPoint& end)
39{
40    return sqrtf((end.x() - start.x()) * (end.x() - start.x()) + (end.y() - start.y()) * (end.y() - start.y()));
41}
42
43struct QuadraticBezier {
44    QuadraticBezier() { }
45    QuadraticBezier(const FloatPoint& s, const FloatPoint& c, const FloatPoint& e)
46        : start(s)
47        , control(c)
48        , end(e)
49    {
50    }
51
52    float approximateDistance() const
53    {
54        return distanceLine(start, control) + distanceLine(control, end);
55    }
56
57    void split(QuadraticBezier& left, QuadraticBezier& right) const
58    {
59        left.control = midPoint(start, control);
60        right.control = midPoint(control, end);
61
62        FloatPoint leftControlToRightControl = midPoint(left.control, right.control);
63        left.end = leftControlToRightControl;
64        right.start = leftControlToRightControl;
65
66        left.start = start;
67        right.end = end;
68    }
69
70    FloatPoint start;
71    FloatPoint control;
72    FloatPoint end;
73};
74
75struct CubicBezier {
76    CubicBezier() { }
77    CubicBezier(const FloatPoint& s, const FloatPoint& c1, const FloatPoint& c2, const FloatPoint& e)
78        : start(s)
79        , control1(c1)
80        , control2(c2)
81        , end(e)
82    {
83    }
84
85    float approximateDistance() const
86    {
87        return distanceLine(start, control1) + distanceLine(control1, control2) + distanceLine(control2, end);
88    }
89
90    void split(CubicBezier& left, CubicBezier& right) const
91    {
92        FloatPoint startToControl1 = midPoint(control1, control2);
93
94        left.start = start;
95        left.control1 = midPoint(start, control1);
96        left.control2 = midPoint(left.control1, startToControl1);
97
98        right.control2 = midPoint(control2, end);
99        right.control1 = midPoint(right.control2, startToControl1);
100        right.end = end;
101
102        FloatPoint leftControl2ToRightControl1 = midPoint(left.control2, right.control1);
103        left.end = leftControl2ToRightControl1;
104        right.start = leftControl2ToRightControl1;
105    }
106
107    FloatPoint start;
108    FloatPoint control1;
109    FloatPoint control2;
110    FloatPoint end;
111};
112
113// FIXME: This function is possibly very slow due to the ifs required for proper path measuring
114// A simple speed-up would be to use an additional boolean template parameter to control whether
115// to use the "fast" version of this function with no PathTraversalState updating, vs. the slow
116// version which does update the PathTraversalState.  We'll have to shark it to see if that's necessary.
117// Another check which is possible up-front (to send us down the fast path) would be to check if
118// approximateDistance() + current total distance > desired distance
119template<class CurveType>
120static float curveLength(PathTraversalState& traversalState, CurveType curve)
121{
122    Vector<CurveType> curveStack;
123    curveStack.append(curve);
124
125    float totalLength = 0.0f;
126    do {
127        float length = curve.approximateDistance();
128        if ((length - distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance) {
129            CurveType left, right;
130            curve.split(left, right);
131            curve = left;
132            curveStack.append(right);
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.0f)
154    , m_segmentIndex(0)
155    , m_desiredLength(0.0f)
156    , m_normalAngle(0.0f)
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.0f;
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
206}
207
208