1 /* 2 * Copyright (C) 2006, 2007 Eric Seidel <eric (at) 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 "core/platform/graphics/PathTraversalState.h" 22 23 #include "wtf/MathExtras.h" 24 #include "wtf/Vector.h" 25 26 namespace WebCore { 27 28 static const float kPathSegmentLengthTolerance = 0.00001f; 29 30 static 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 35 static 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 40 struct 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 72 struct 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 116 template<class CurveType> 117 static 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 150 PathTraversalState::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 160 float 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 167 float PathTraversalState::moveTo(const FloatPoint& point) 168 { 169 m_current = m_start = m_control1 = m_control2 = point; 170 return 0; 171 } 172 173 float 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 180 float 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 193 float 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 void 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