00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022 #include "config.h"
00023 #include "PathTraversalState.h"
00024
00025 #include "Path.h"
00026
00027 #include <math.h>
00028
00029 namespace WebCore {
00030
00031 static const float kPathSegmentLengthTolerance = 0.00001f;
00032
00033 static inline FloatPoint midPoint(const FloatPoint& first, const FloatPoint& second)
00034 {
00035 return FloatPoint((first.x() + second.x()) / 2.0f, (first.y() + second.y()) / 2.0f);
00036 }
00037
00038 static inline float distanceLine(const FloatPoint& start, const FloatPoint& end)
00039 {
00040 return sqrtf((end.x() - start.x()) * (end.x() - start.x()) + (end.y() - start.y()) * (end.y() - start.y()));
00041 }
00042
00043 struct QuadraticBezier {
00044 QuadraticBezier() { }
00045 QuadraticBezier(const FloatPoint& s, const FloatPoint& c, const FloatPoint& e)
00046 : start(s)
00047 , control(c)
00048 , end(e)
00049 {
00050 }
00051
00052 float approximateDistance() const
00053 {
00054 return distanceLine(start, control) + distanceLine(control, end);
00055 }
00056
00057 void split(QuadraticBezier& left, QuadraticBezier& right) const
00058 {
00059 left.control = midPoint(start, control);
00060 right.control = midPoint(control, end);
00061
00062 FloatPoint leftControlToRightControl = midPoint(left.control, right.control);
00063 left.end = leftControlToRightControl;
00064 right.start = leftControlToRightControl;
00065
00066 left.start = start;
00067 right.end = end;
00068 }
00069
00070 FloatPoint start;
00071 FloatPoint control;
00072 FloatPoint end;
00073 };
00074
00075 struct CubicBezier {
00076 CubicBezier() { }
00077 CubicBezier(const FloatPoint& s, const FloatPoint& c1, const FloatPoint& c2, const FloatPoint& e)
00078 : start(s)
00079 , control1(c1)
00080 , control2(c2)
00081 , end(e)
00082 {
00083 }
00084
00085 float approximateDistance() const
00086 {
00087 return distanceLine(start, control1) + distanceLine(control1, control2) + distanceLine(control2, end);
00088 }
00089
00090 void split(CubicBezier& left, CubicBezier& right) const
00091 {
00092 FloatPoint startToControl1 = midPoint(control1, control2);
00093
00094 left.start = start;
00095 left.control1 = midPoint(start, control1);
00096 left.control2 = midPoint(left.control1, startToControl1);
00097
00098 right.control2 = midPoint(control2, end);
00099 right.control1 = midPoint(right.control2, startToControl1);
00100 right.end = end;
00101
00102 FloatPoint leftControl2ToRightControl1 = midPoint(left.control2, right.control1);
00103 left.end = leftControl2ToRightControl1;
00104 right.start = leftControl2ToRightControl1;
00105 }
00106
00107 FloatPoint start;
00108 FloatPoint control1;
00109 FloatPoint control2;
00110 FloatPoint end;
00111 };
00112
00113
00114
00115
00116
00117
00118
00119 template<class CurveType>
00120 static float curveLength(PathTraversalState& traversalState, CurveType curve)
00121 {
00122 Vector<CurveType> curveStack;
00123 curveStack.append(curve);
00124
00125 float totalLength = 0.0f;
00126 do {
00127 float length = curve.approximateDistance();
00128 if ((length - distanceLine(curve.start, curve.end)) > kPathSegmentLengthTolerance) {
00129 CurveType left, right;
00130 curve.split(left, right);
00131 curve = left;
00132 curveStack.append(right);
00133 } else {
00134 totalLength += length;
00135 if (traversalState.m_action == PathTraversalState::TraversalPointAtLength
00136 || traversalState.m_action == PathTraversalState::TraversalNormalAngleAtLength) {
00137 traversalState.m_previous = curve.start;
00138 traversalState.m_current = curve.end;
00139 if (traversalState.m_totalLength + totalLength > traversalState.m_desiredLength)
00140 return totalLength;
00141 }
00142 curve = curveStack.last();
00143 curveStack.removeLast();
00144 }
00145 } while (!curveStack.isEmpty());
00146
00147 return totalLength;
00148 }
00149
00150 PathTraversalState::PathTraversalState(PathTraversalAction action)
00151 : m_action(action)
00152 , m_success(false)
00153 , m_totalLength(0.0f)
00154 , m_segmentIndex(0)
00155 , m_desiredLength(0.0f)
00156 , m_normalAngle(0.0f)
00157 {
00158 }
00159
00160 float PathTraversalState::closeSubpath()
00161 {
00162 float distance = distanceLine(m_current, m_start);
00163 m_start = m_control1 = m_control2 = m_current;
00164 return distance;
00165 }
00166
00167 float PathTraversalState::moveTo(const FloatPoint& point)
00168 {
00169 m_current = m_start = m_control1 = m_control2 = point;
00170 return 0.0f;
00171 }
00172
00173 float PathTraversalState::lineTo(const FloatPoint& point)
00174 {
00175 float distance = distanceLine(m_current, point);
00176 m_current = m_control1 = m_control2 = point;
00177 return distance;
00178 }
00179
00180 float PathTraversalState::quadraticBezierTo(const FloatPoint& newControl, const FloatPoint& newEnd)
00181 {
00182 float distance = curveLength<QuadraticBezier>(*this, QuadraticBezier(m_current, newControl, newEnd));
00183
00184 m_control1 = newControl;
00185 m_control2 = newEnd;
00186
00187 if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength)
00188 m_current = newEnd;
00189
00190 return distance;
00191 }
00192
00193 float PathTraversalState::cubicBezierTo(const FloatPoint& newControl1, const FloatPoint& newControl2, const FloatPoint& newEnd)
00194 {
00195 float distance = curveLength<CubicBezier>(*this, CubicBezier(m_current, newControl1, newControl2, newEnd));
00196
00197 m_control1 = newEnd;
00198 m_control2 = newControl2;
00199
00200 if (m_action != TraversalPointAtLength && m_action != TraversalNormalAngleAtLength)
00201 m_current = newEnd;
00202
00203 return distance;
00204 }
00205
00206 }
00207