2007-01-02 Eric Seidel <eric@webkit.org>
[WebKit-https.git] / WebCore / platform / graphics / PathTraversalState.cpp
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., 59 Temple Place - Suite 330,
19  * Boston, MA 02111-1307, USA.
20  */
21
22 #include "config.h"
23 #include "PathTraversalState.h"
24
25 #include "Path.h"
26
27 namespace WebCore {
28
29 static const float kPathSegmentLengthTolerance = 0.00001f;
30
31 static inline FloatPoint midPoint(const FloatPoint& first, const FloatPoint& second)
32 {
33     return FloatPoint((first.x() + second.x()) / 2.0f, (first.y() + second.y()) / 2.0f);
34 }
35
36 static inline float distanceLine(const FloatPoint& start, const FloatPoint& end)
37 {
38     return sqrtf((end.x() - start.x()) * (end.x() - start.x()) + (end.y() - start.y()) * (end.y() - start.y()));
39 }
40
41 struct QuadraticBezier {
42     QuadraticBezier() { }
43     QuadraticBezier(const FloatPoint& s, const FloatPoint& c, const FloatPoint& e)
44         : start(s)
45         , control(c)
46         , end(e)
47     {
48     }
49     
50     float approximateDistance() const
51     {
52         return distanceLine(start, control) + distanceLine(control, end);
53     }
54     
55     void split(QuadraticBezier& left, QuadraticBezier& right) const
56     {
57         left.control = midPoint(start, control);
58         right.control = midPoint(control, end);
59         
60         FloatPoint leftControlToRightControl = midPoint(left.control, right.control);
61         left.end = leftControlToRightControl;
62         right.start = leftControlToRightControl;
63
64         left.start = start;
65         right.end = end;
66     }
67     
68     FloatPoint start;
69     FloatPoint control;
70     FloatPoint end;
71 };
72
73 struct CubicBezier {
74     CubicBezier() { }
75     CubicBezier(const FloatPoint& s, const FloatPoint& c1, const FloatPoint& c2, const FloatPoint& e)
76         : start(s)
77         , control1(c1)
78         , control2(c2)
79         , end(e)
80     {
81     }
82     
83     float approximateDistance() const
84     {
85         return distanceLine(start, control1) + distanceLine(control1, control2) + distanceLine(control2, end);
86     }
87         
88     void split(CubicBezier& left, CubicBezier& right) const
89     {    
90         FloatPoint startToControl1 = midPoint(control1, control2);
91         
92         left.start = start;
93         left.control1 = midPoint(start, control1);
94         left.control2 = midPoint(left.control1, startToControl1);
95         
96         right.control2 = midPoint(control2, end);
97         right.control1 = midPoint(right.control2, startToControl1);
98         right.end = end;
99         
100         FloatPoint leftControl2ToRightControl1 = midPoint(left.control2, right.control1);
101         left.end = leftControl2ToRightControl1;
102         right.start = leftControl2ToRightControl1;
103     }
104     
105     FloatPoint start;
106     FloatPoint control1;
107     FloatPoint control2;
108     FloatPoint end;
109 };
110
111 // FIXME: This function is possibly very slow due to the ifs required for proper path measuring
112 // A simple speed-up would be to use an additional boolean template parameter to control whether
113 // to use the "fast" version of this function with no PathTraversalState updating, vs. the slow
114 // version which does update the PathTraversalState.  We'll have to shark it to see if that's necessary.
115 // Another check which is possible up-front (to send us down the fast path) would be to check if
116 // approximateDistance() + current total distance > desired distance
117 template<class CurveType>
118 static float curveLength(PathTraversalState& traversalState, CurveType curve)
119 {
120     Vector<CurveType> curveStack;
121     curveStack.append(curve);
122
123     float totalLength = 0.0f;
124     do {
125         float length = curve.approximateDistance();
126         if ((length - distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance) {
127             CurveType left, right;
128             curve.split(left, right);
129             curve = left;
130             curveStack.append(right);
131         } else {
132             totalLength += length;
133             if (traversalState.m_action == PathTraversalState::TraversalPointAtLength
134              || traversalState.m_action == PathTraversalState::TraversalNormalAngleAtLength) {
135                 traversalState.m_previous = curve.start;
136                 traversalState.m_current = curve.end;
137                 if (traversalState.m_totalLength + totalLength > traversalState.m_desiredLength)
138                     return totalLength;
139             }
140             curve = curveStack.last();
141             curveStack.removeLast();
142         }
143     } while (!curveStack.isEmpty());
144     
145     return totalLength;
146 }
147
148 PathTraversalState::PathTraversalState(PathTraversalAction action)
149     : m_action(action)
150     , m_success(false)
151     , m_totalLength(0.0f)
152     , m_segmentIndex(0)
153     , m_desiredLength(0.0f)
154     , m_normalAngle(0.0f)
155 {
156 }
157
158 float PathTraversalState::closeSubpath()
159 {
160     float distance = distanceLine(m_current, m_start);
161     m_start = m_control1 = m_control2 = m_current;
162     return distance;
163 }
164
165 float PathTraversalState::moveTo(const FloatPoint& point)
166 {
167     m_current = m_start = m_control1 = m_control2 = point;
168     return 0.0f;
169 }
170
171 float PathTraversalState::lineTo(const FloatPoint& point)
172 {
173     float distance = distanceLine(m_current, point);
174     m_current = m_control1 = m_control2 = point;
175     return distance;
176 }
177
178 float PathTraversalState::quadraticBezierTo(const FloatPoint& newControl, const FloatPoint& newEnd)
179 {
180     float distance = curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd));
181     m_control1 = newControl;
182     m_control2 = m_current = newEnd;
183     return distance;
184 }
185
186 float PathTraversalState::cubicBezierTo(const FloatPoint& newControl1, const FloatPoint& newControl2, const FloatPoint& newEnd)
187 {
188     float distance = curveLength<CubicBezier>(*this, CubicBezier(m_current, newControl1, newControl2, newEnd));
189     m_control1 = m_current = newEnd;
190     m_control2 = newControl2;
191     return distance;
192 }
193
194 }
195