KHtml

PathTraversalState.cpp
1 /*
2  * This file is part of the WebKit open source project.
3  *
4  * Copyright (C) 2006, 2007 Eric Seidel ([email protected])
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 "PathTraversalState.h"
23 
24 #include "Path.h"
25 
26 #include <math.h>
27 
28 namespace WebCore
29 {
30 
31 static const float kPathSegmentLengthTolerance = 0.00001f;
32 
33 static 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 
38 static 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 
43 struct 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 
75 struct 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
119 template<class CurveType>
120 static 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  }
143  curve = curveStack.last();
144  curveStack.removeLast();
145  }
146  } while (!curveStack.isEmpty());
147 
148  return totalLength;
149 }
150 
151 PathTraversalState::PathTraversalState(PathTraversalAction action)
152  : m_action(action)
153  , m_success(false)
154  , m_totalLength(0.0f)
155  , m_segmentIndex(0)
156  , m_desiredLength(0.0f)
157  , m_normalAngle(0.0f)
158 {
159 }
160 
161 float PathTraversalState::closeSubpath()
162 {
163  float distance = distanceLine(m_current, m_start);
164  m_start = m_control1 = m_control2 = m_current;
165  return distance;
166 }
167 
168 float PathTraversalState::moveTo(const FloatPoint &point)
169 {
170  m_current = m_start = m_control1 = m_control2 = point;
171  return 0.0f;
172 }
173 
174 float PathTraversalState::lineTo(const FloatPoint &point)
175 {
176  float distance = distanceLine(m_current, point);
177  m_current = m_control1 = m_control2 = point;
178  return distance;
179 }
180 
181 float PathTraversalState::quadraticBezierTo(const FloatPoint &newControl, const FloatPoint &newEnd)
182 {
183  float distance = curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd));
184 
185  m_control1 = newControl;
186  m_control2 = newEnd;
187 
188  if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength) {
189  m_current = newEnd;
190  }
191 
192  return distance;
193 }
194 
195 float PathTraversalState::cubicBezierTo(const FloatPoint &newControl1, const FloatPoint &newControl2, const FloatPoint &newEnd)
196 {
197  float distance = curveLength<CubicBezier>(*this, CubicBezier(m_current, newControl1, newControl2, newEnd));
198 
199  m_control1 = newEnd;
200  m_control2 = newControl2;
201 
202  if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength) {
203  m_current = newEnd;
204  }
205 
206  return distance;
207 }
208 
209 }
210 
QTextStream & right(QTextStream &stream)
QTextStream & left(QTextStream &stream)
int distance(const GeoCoordinates &coord1, const GeoCoordinates &coord2)
This file is part of the KDE documentation.
Documentation copyright © 1996-2021 The KDE developers.
Generated on Mon Oct 25 2021 22:48:19 by doxygen 1.8.11 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.