• Skip to content
  • Skip to link menu
  • KDE API Reference
  • kdelibs-4.14.38 API Reference
  • KDE Home
  • Contact Us
 

KHTML

  • khtml
  • platform
  • graphics
PathTraversalState.cpp
Go to the documentation of this file.
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_start = m_control1 = m_control2 = m_current;
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
PathTraversalState.h
Path.h
WebCore::FloatPoint
Definition: FloatPoint.h:61
WebCore::FloatPoint::y
float y() const
Definition: FloatPoint.h:70
WebCore::FloatPoint::x
float x() const
Definition: FloatPoint.h:69
WebCore::PathTraversalState
Definition: PathTraversalState.h:39
WebCore::PathTraversalState::m_control2
FloatPoint m_control2
Definition: PathTraversalState.h:63
WebCore::PathTraversalState::PathTraversalState
PathTraversalState(PathTraversalAction)
Definition: PathTraversalState.cpp:150
WebCore::PathTraversalState::m_start
FloatPoint m_start
Definition: PathTraversalState.h:61
WebCore::PathTraversalState::quadraticBezierTo
float quadraticBezierTo(const FloatPoint &newControl, const FloatPoint &newEnd)
Definition: PathTraversalState.cpp:180
WebCore::PathTraversalState::m_totalLength
float m_totalLength
Definition: PathTraversalState.h:65
WebCore::PathTraversalState::closeSubpath
float closeSubpath()
Definition: PathTraversalState.cpp:160
WebCore::PathTraversalState::m_control1
FloatPoint m_control1
Definition: PathTraversalState.h:62
WebCore::PathTraversalState::lineTo
float lineTo(const FloatPoint &)
Definition: PathTraversalState.cpp:173
WebCore::PathTraversalState::m_desiredLength
float m_desiredLength
Definition: PathTraversalState.h:67
WebCore::PathTraversalState::m_previous
FloatPoint m_previous
Definition: PathTraversalState.h:70
WebCore::PathTraversalState::cubicBezierTo
float cubicBezierTo(const FloatPoint &newControl1, const FloatPoint &newControl2, const FloatPoint &newEnd)
Definition: PathTraversalState.cpp:193
WebCore::PathTraversalState::PathTraversalAction
PathTraversalAction
Definition: PathTraversalState.h:41
WebCore::PathTraversalState::TraversalPointAtLength
@ TraversalPointAtLength
Definition: PathTraversalState.h:43
WebCore::PathTraversalState::TraversalNormalAngleAtLength
@ TraversalNormalAngleAtLength
Definition: PathTraversalState.h:45
WebCore::PathTraversalState::m_current
FloatPoint m_current
Definition: PathTraversalState.h:60
WebCore::PathTraversalState::moveTo
float moveTo(const FloatPoint &)
Definition: PathTraversalState.cpp:167
WebCore::PathTraversalState::m_action
PathTraversalAction m_action
Definition: PathTraversalState.h:57
end
const KShortcut & end()
WebCore
Definition: CSSHelper.h:7
WebCore::kPathSegmentLengthTolerance
static const float kPathSegmentLengthTolerance
Definition: PathTraversalState.cpp:31
WebCore::curveLength
static float curveLength(PathTraversalState &traversalState, CurveType curve)
Definition: PathTraversalState.cpp:120
WebCore::distanceLine
static float distanceLine(const FloatPoint &start, const FloatPoint &end)
Definition: PathTraversalState.cpp:38
WebCore::midPoint
static FloatPoint midPoint(const FloatPoint &first, const FloatPoint &second)
Definition: PathTraversalState.cpp:33
This file is part of the KDE documentation.
Documentation copyright © 1996-2023 The KDE developers.
Generated on Mon Feb 20 2023 00:00:00 by doxygen 1.9.6 written by Dimitri van Heesch, © 1997-2006

KDE's Doxygen guidelines are available online.

KHTML

Skip menu "KHTML"
  • Main Page
  • Namespace List
  • Namespace Members
  • Alphabetical List
  • Class List
  • Class Hierarchy
  • Class Members
  • File List
  • File Members
  • Related Pages

kdelibs-4.14.38 API Reference

Skip menu "kdelibs-4.14.38 API Reference"
  • DNSSD
  • Interfaces
  •   KHexEdit
  •   KMediaPlayer
  •   KSpeech
  •   KTextEditor
  • kconf_update
  • KDE3Support
  •   KUnitTest
  • KDECore
  • KDED
  • KDEsu
  • KDEUI
  • KDEWebKit
  • KDocTools
  • KFile
  • KHTML
  • KImgIO
  • KInit
  • kio
  • KIOSlave
  • KJS
  •   KJS-API
  •   WTF
  • kjsembed
  • KNewStuff
  • KParts
  • KPty
  • Kross
  • KUnitConversion
  • KUtils
  • Nepomuk
  • Plasma
  • Solid
  • Sonnet
  • ThreadWeaver
Report problems with this website to our bug tracking system.
Contact the specific authors with questions and comments about the page contents.

KDE® and the K Desktop Environment® logo are registered trademarks of KDE e.V. | Legal