1/* 2 * Copyright (C) 2006, 2007 Eric Seidel <eric@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 "PathTraversalState.h" 22 23#include <wtf/MathExtras.h> 24#include <wtf/Vector.h> 25 26namespace WebCore { 27 28static const float kPathSegmentLengthTolerance = 0.00001f; 29 30static 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 35static 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 40struct 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 72struct 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 116template<class CurveType> 117static 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 150PathTraversalState::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 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; 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 206void 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