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 "platform/graphics/PathTraversalState.h" 22 23#include "wtf/MathExtras.h" 24#include "wtf/Vector.h" 25 26namespace WebCore { 27 28static inline FloatPoint midPoint(const FloatPoint& first, const FloatPoint& second) 29{ 30 return FloatPoint((first.x() + second.x()) / 2.0f, (first.y() + second.y()) / 2.0f); 31} 32 33static inline float distanceLine(const FloatPoint& start, const FloatPoint& end) 34{ 35 return sqrtf((end.x() - start.x()) * (end.x() - start.x()) + (end.y() - start.y()) * (end.y() - start.y())); 36} 37 38struct QuadraticBezier { 39 QuadraticBezier() { } 40 QuadraticBezier(const FloatPoint& s, const FloatPoint& c, const FloatPoint& e) 41 : start(s) 42 , control(c) 43 , end(e) 44 , splitDepth(0) 45 { 46 } 47 48 double magnitudeSquared() const 49 { 50 return ((double)(start.dot(start)) + (double)(control.dot(control)) + (double)(end.dot(end))) / 9.0; 51 } 52 53 float approximateDistance() const 54 { 55 return distanceLine(start, control) + distanceLine(control, end); 56 } 57 58 void split(QuadraticBezier& left, QuadraticBezier& right) const 59 { 60 left.control = midPoint(start, control); 61 right.control = midPoint(control, end); 62 63 FloatPoint leftControlToRightControl = midPoint(left.control, right.control); 64 left.end = leftControlToRightControl; 65 right.start = leftControlToRightControl; 66 67 left.start = start; 68 right.end = end; 69 70 left.splitDepth = right.splitDepth = splitDepth + 1; 71 } 72 73 FloatPoint start; 74 FloatPoint control; 75 FloatPoint end; 76 unsigned short splitDepth; 77}; 78 79struct CubicBezier { 80 CubicBezier() { } 81 CubicBezier(const FloatPoint& s, const FloatPoint& c1, const FloatPoint& c2, const FloatPoint& e) 82 : start(s) 83 , control1(c1) 84 , control2(c2) 85 , end(e) 86 , splitDepth(0) 87 { 88 } 89 90 double magnitudeSquared() const 91 { 92 return ((double)(start.dot(start)) + (double)(control1.dot(control1)) + (double)(control2.dot(control2)) + (double)(end.dot(end))) / 16.0; 93 } 94 95 float approximateDistance() const 96 { 97 return distanceLine(start, control1) + distanceLine(control1, control2) + distanceLine(control2, end); 98 } 99 100 void split(CubicBezier& left, CubicBezier& right) const 101 { 102 FloatPoint startToControl1 = midPoint(control1, control2); 103 104 left.start = start; 105 left.control1 = midPoint(start, control1); 106 left.control2 = midPoint(left.control1, startToControl1); 107 108 right.control2 = midPoint(control2, end); 109 right.control1 = midPoint(right.control2, startToControl1); 110 right.end = end; 111 112 FloatPoint leftControl2ToRightControl1 = midPoint(left.control2, right.control1); 113 left.end = leftControl2ToRightControl1; 114 right.start = leftControl2ToRightControl1; 115 116 left.splitDepth = right.splitDepth = splitDepth + 1; 117 } 118 119 FloatPoint start; 120 FloatPoint control1; 121 FloatPoint control2; 122 FloatPoint end; 123 unsigned short splitDepth; 124}; 125 126template<class CurveType> 127static float curveLength(PathTraversalState& traversalState, CurveType curve) 128{ 129 static const unsigned short curveSplitDepthLimit = 20; 130 static const double pathSegmentLengthToleranceSquared = 1.e-16; 131 132 double curveScaleForToleranceSquared = curve.magnitudeSquared(); 133 if (curveScaleForToleranceSquared < pathSegmentLengthToleranceSquared) 134 return 0; 135 136 Vector<CurveType> curveStack; 137 curveStack.append(curve); 138 139 float totalLength = 0; 140 do { 141 float length = curve.approximateDistance(); 142 double lengthDiscrepancy = length - distanceLine(curve.start, curve.end); 143 if ((lengthDiscrepancy * lengthDiscrepancy) / curveScaleForToleranceSquared > pathSegmentLengthToleranceSquared && curve.splitDepth < curveSplitDepthLimit) { 144 CurveType leftCurve; 145 CurveType rightCurve; 146 curve.split(leftCurve, rightCurve); 147 curve = leftCurve; 148 curveStack.append(rightCurve); 149 } else { 150 totalLength += length; 151 if (traversalState.m_action == PathTraversalState::TraversalPointAtLength || traversalState.m_action == PathTraversalState::TraversalNormalAngleAtLength) { 152 traversalState.m_previous = curve.start; 153 traversalState.m_current = curve.end; 154 if (traversalState.m_totalLength + totalLength > traversalState.m_desiredLength) 155 return totalLength; 156 } 157 curve = curveStack.last(); 158 curveStack.removeLast(); 159 } 160 } while (!curveStack.isEmpty()); 161 162 return totalLength; 163} 164 165PathTraversalState::PathTraversalState(PathTraversalAction action) 166 : m_action(action) 167 , m_success(false) 168 , m_totalLength(0) 169 , m_segmentIndex(0) 170 , m_desiredLength(0) 171 , m_normalAngle(0) 172{ 173} 174 175float PathTraversalState::closeSubpath() 176{ 177 float distance = distanceLine(m_current, m_start); 178 m_current = m_start; 179 return distance; 180} 181 182float PathTraversalState::moveTo(const FloatPoint& point) 183{ 184 m_current = m_start = point; 185 return 0; 186} 187 188float PathTraversalState::lineTo(const FloatPoint& point) 189{ 190 float distance = distanceLine(m_current, point); 191 m_current = point; 192 return distance; 193} 194 195float PathTraversalState::quadraticBezierTo(const FloatPoint& newControl, const FloatPoint& newEnd) 196{ 197 float distance = curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd)); 198 199 if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength) 200 m_current = newEnd; 201 202 return distance; 203} 204 205float PathTraversalState::cubicBezierTo(const FloatPoint& newControl1, const FloatPoint& newControl2, const FloatPoint& newEnd) 206{ 207 float distance = curveLength<CubicBezier>(*this, CubicBezier(m_current, newControl1, newControl2, newEnd)); 208 209 if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength) 210 m_current = newEnd; 211 212 return distance; 213} 214 215void PathTraversalState::processSegment() 216{ 217 if (m_action == TraversalSegmentAtLength && m_totalLength >= m_desiredLength) 218 m_success = true; 219 220 if ((m_action == TraversalPointAtLength || m_action == TraversalNormalAngleAtLength) && m_totalLength >= m_desiredLength) { 221 float slope = FloatPoint(m_current - m_previous).slopeAngleRadians(); 222 if (m_action == TraversalPointAtLength) { 223 float offset = m_desiredLength - m_totalLength; 224 m_current.move(offset * cosf(slope), offset * sinf(slope)); 225 } else { 226 m_normalAngle = rad2deg(slope); 227 } 228 m_success = true; 229 } 230 m_previous = m_current; 231} 232 233} 234 235