1/* 2 * Copyright (C) 2006 Zack Rusin <zack@kde.org> 3 * 2006 Rob Buis <buis@kde.org> 4 * 2009, 2010 Dirk Schulze <krit@webkit.org> 5 * 6 * All rights reserved. 7 * 8 * Redistribution and use in source and binary forms, with or without 9 * modification, are permitted provided that the following conditions 10 * are met: 11 * 1. Redistributions of source code must retain the above copyright 12 * notice, this list of conditions and the following disclaimer. 13 * 2. Redistributions in binary form must reproduce the above copyright 14 * notice, this list of conditions and the following disclaimer in the 15 * documentation and/or other materials provided with the distribution. 16 * 17 * THIS SOFTWARE IS PROVIDED BY APPLE COMPUTER, INC. ``AS IS'' AND ANY 18 * EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 19 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR 20 * PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL APPLE COMPUTER, INC. OR 21 * CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, 22 * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, 23 * PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR 24 * PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY 25 * OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 26 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 27 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 28 */ 29 30#include "config.h" 31#include "Path.h" 32 33#include "AffineTransform.h" 34#include "FloatRect.h" 35#include "GraphicsContext.h" 36#include "ImageBuffer.h" 37#include "PlatformString.h" 38#include "StrokeStyleApplier.h" 39#include <QPainterPath> 40#include <QTransform> 41#include <QString> 42#include <wtf/MathExtras.h> 43#include <wtf/OwnPtr.h> 44 45namespace WebCore { 46 47Path::Path() 48{ 49} 50 51Path::~Path() 52{ 53} 54 55Path::Path(const Path& other) 56 : m_path(other.m_path) 57{ 58} 59 60Path& Path::operator=(const Path& other) 61{ 62 m_path = other.m_path; 63 return *this; 64} 65 66static inline bool areCollinear(const QPointF& a, const QPointF& b, const QPointF& c) 67{ 68 // Solved from comparing the slopes of a to b and b to c: (ay-by)/(ax-bx) == (cy-by)/(cx-bx) 69 return qFuzzyCompare((c.y() - b.y()) * (a.x() - b.x()), (a.y() - b.y()) * (c.x() - b.x())); 70} 71 72static inline bool withinRange(qreal p, qreal a, qreal b) 73{ 74 return (p >= a && p <= b) || (p >= b && p <= a); 75} 76 77// Check whether a point is on the border 78static bool isPointOnPathBorder(const QPolygonF& border, const QPointF& p) 79{ 80 // null border doesn't contain points 81 if (border.isEmpty()) 82 return false; 83 84 QPointF p1 = border.at(0); 85 QPointF p2; 86 87 for (int i = 1; i < border.size(); ++i) { 88 p2 = border.at(i); 89 if (areCollinear(p, p1, p2) 90 // Once we know that the points are collinear we 91 // only need to check one of the coordinates 92 && (qAbs(p2.x() - p1.x()) > qAbs(p2.y() - p1.y()) ? 93 withinRange(p.x(), p1.x(), p2.x()) : 94 withinRange(p.y(), p1.y(), p2.y()))) { 95 return true; 96 } 97 p1 = p2; 98 } 99 return false; 100} 101 102bool Path::contains(const FloatPoint& point, WindRule rule) const 103{ 104 Qt::FillRule savedRule = m_path.fillRule(); 105 const_cast<QPainterPath*>(&m_path)->setFillRule(rule == RULE_EVENODD ? Qt::OddEvenFill : Qt::WindingFill); 106 107 bool contains = m_path.contains(point); 108 109 if (!contains) { 110 // check whether the point is on the border 111 contains = isPointOnPathBorder(m_path.toFillPolygon(), point); 112 } 113 114 const_cast<QPainterPath*>(&m_path)->setFillRule(savedRule); 115 return contains; 116} 117 118static GraphicsContext* scratchContext() 119{ 120 static QImage image(1, 1, QImage::Format_ARGB32_Premultiplied); 121 static QPainter painter(&image); 122 static GraphicsContext* context = new GraphicsContext(&painter); 123 return context; 124} 125 126bool Path::strokeContains(StrokeStyleApplier* applier, const FloatPoint& point) const 127{ 128 ASSERT(applier); 129 130 QPainterPathStroker stroke; 131 GraphicsContext* context = scratchContext(); 132 applier->strokeStyle(context); 133 134 QPen pen = context->platformContext()->pen(); 135 stroke.setWidth(pen.widthF()); 136 stroke.setCapStyle(pen.capStyle()); 137 stroke.setJoinStyle(pen.joinStyle()); 138 stroke.setMiterLimit(pen.miterLimit()); 139 stroke.setDashPattern(pen.dashPattern()); 140 stroke.setDashOffset(pen.dashOffset()); 141 142 return stroke.createStroke(m_path).contains(point); 143} 144 145void Path::translate(const FloatSize& size) 146{ 147 QTransform matrix; 148 matrix.translate(size.width(), size.height()); 149 m_path = m_path * matrix; 150} 151 152FloatRect Path::boundingRect() const 153{ 154 return m_path.boundingRect(); 155} 156 157FloatRect Path::strokeBoundingRect(StrokeStyleApplier* applier) const 158{ 159 GraphicsContext* context = scratchContext(); 160 QPainterPathStroker stroke; 161 if (applier) { 162 applier->strokeStyle(context); 163 164 QPen pen = context->platformContext()->pen(); 165 stroke.setWidth(pen.widthF()); 166 stroke.setCapStyle(pen.capStyle()); 167 stroke.setJoinStyle(pen.joinStyle()); 168 stroke.setMiterLimit(pen.miterLimit()); 169 stroke.setDashPattern(pen.dashPattern()); 170 stroke.setDashOffset(pen.dashOffset()); 171 } 172 return stroke.createStroke(m_path).boundingRect(); 173} 174 175void Path::moveTo(const FloatPoint& point) 176{ 177 m_path.moveTo(point); 178} 179 180void Path::addLineTo(const FloatPoint& p) 181{ 182 m_path.lineTo(p); 183} 184 185void Path::addQuadCurveTo(const FloatPoint& cp, const FloatPoint& p) 186{ 187 m_path.quadTo(cp, p); 188} 189 190void Path::addBezierCurveTo(const FloatPoint& cp1, const FloatPoint& cp2, const FloatPoint& p) 191{ 192 m_path.cubicTo(cp1, cp2, p); 193} 194 195void Path::addArcTo(const FloatPoint& p1, const FloatPoint& p2, float radius) 196{ 197 FloatPoint p0(m_path.currentPosition()); 198 199 FloatPoint p1p0((p0.x() - p1.x()), (p0.y() - p1.y())); 200 FloatPoint p1p2((p2.x() - p1.x()), (p2.y() - p1.y())); 201 float p1p0_length = sqrtf(p1p0.x() * p1p0.x() + p1p0.y() * p1p0.y()); 202 float p1p2_length = sqrtf(p1p2.x() * p1p2.x() + p1p2.y() * p1p2.y()); 203 204 double cos_phi = (p1p0.x() * p1p2.x() + p1p0.y() * p1p2.y()) / (p1p0_length * p1p2_length); 205 206 // The points p0, p1, and p2 are on the same straight line (HTML5, 4.8.11.1.8) 207 // We could have used areCollinear() here, but since we're reusing 208 // the variables computed above later on we keep this logic. 209 if (qFuzzyCompare(qAbs(cos_phi), 1.0)) { 210 m_path.lineTo(p1); 211 return; 212 } 213 214 float tangent = radius / tan(acos(cos_phi) / 2); 215 float factor_p1p0 = tangent / p1p0_length; 216 FloatPoint t_p1p0((p1.x() + factor_p1p0 * p1p0.x()), (p1.y() + factor_p1p0 * p1p0.y())); 217 218 FloatPoint orth_p1p0(p1p0.y(), -p1p0.x()); 219 float orth_p1p0_length = sqrt(orth_p1p0.x() * orth_p1p0.x() + orth_p1p0.y() * orth_p1p0.y()); 220 float factor_ra = radius / orth_p1p0_length; 221 222 // angle between orth_p1p0 and p1p2 to get the right vector orthographic to p1p0 223 double cos_alpha = (orth_p1p0.x() * p1p2.x() + orth_p1p0.y() * p1p2.y()) / (orth_p1p0_length * p1p2_length); 224 if (cos_alpha < 0.f) 225 orth_p1p0 = FloatPoint(-orth_p1p0.x(), -orth_p1p0.y()); 226 227 FloatPoint p((t_p1p0.x() + factor_ra * orth_p1p0.x()), (t_p1p0.y() + factor_ra * orth_p1p0.y())); 228 229 // calculate angles for addArc 230 orth_p1p0 = FloatPoint(-orth_p1p0.x(), -orth_p1p0.y()); 231 float sa = acos(orth_p1p0.x() / orth_p1p0_length); 232 if (orth_p1p0.y() < 0.f) 233 sa = 2 * piDouble - sa; 234 235 // anticlockwise logic 236 bool anticlockwise = false; 237 238 float factor_p1p2 = tangent / p1p2_length; 239 FloatPoint t_p1p2((p1.x() + factor_p1p2 * p1p2.x()), (p1.y() + factor_p1p2 * p1p2.y())); 240 FloatPoint orth_p1p2((t_p1p2.x() - p.x()), (t_p1p2.y() - p.y())); 241 float orth_p1p2_length = sqrtf(orth_p1p2.x() * orth_p1p2.x() + orth_p1p2.y() * orth_p1p2.y()); 242 float ea = acos(orth_p1p2.x() / orth_p1p2_length); 243 if (orth_p1p2.y() < 0) 244 ea = 2 * piDouble - ea; 245 if ((sa > ea) && ((sa - ea) < piDouble)) 246 anticlockwise = true; 247 if ((sa < ea) && ((ea - sa) > piDouble)) 248 anticlockwise = true; 249 250 m_path.lineTo(t_p1p0); 251 252 addArc(p, radius, sa, ea, anticlockwise); 253} 254 255void Path::closeSubpath() 256{ 257 m_path.closeSubpath(); 258} 259 260void Path::addArc(const FloatPoint& p, float r, float sar, float ear, bool anticlockwise) 261{ 262 qreal xc = p.x(); 263 qreal yc = p.y(); 264 qreal radius = r; 265 266 267 //### HACK 268 // In Qt we don't switch the coordinate system for degrees 269 // and still use the 0,0 as bottom left for degrees so we need 270 // to switch 271 sar = -sar; 272 ear = -ear; 273 anticlockwise = !anticlockwise; 274 //end hack 275 276 float sa = rad2deg(sar); 277 float ea = rad2deg(ear); 278 279 double span = 0; 280 281 double xs = xc - radius; 282 double ys = yc - radius; 283 double width = radius*2; 284 double height = radius*2; 285 286 if ((!anticlockwise && (ea - sa >= 360)) || (anticlockwise && (sa - ea >= 360))) { 287 // If the anticlockwise argument is false and endAngle-startAngle is equal to or greater than 2*PI, or, if the 288 // anticlockwise argument is true and startAngle-endAngle is equal to or greater than 2*PI, then the arc is the whole 289 // circumference of this circle. 290 span = 360; 291 292 if (anticlockwise) 293 span = -span; 294 } else { 295 if (!anticlockwise && (ea < sa)) 296 span += 360; 297 else if (anticlockwise && (sa < ea)) 298 span -= 360; 299 300 // this is also due to switched coordinate system 301 // we would end up with a 0 span instead of 360 302 if (!(qFuzzyCompare(span + (ea - sa) + 1, 1.0) 303 && qFuzzyCompare(qAbs(span), 360.0))) { 304 // mod 360 305 span += (ea - sa) - (static_cast<int>((ea - sa) / 360)) * 360; 306 } 307 } 308 309 // If the path is empty, move to where the arc will start to avoid painting a line from (0,0) 310 // NOTE: QPainterPath::isEmpty() won't work here since it ignores a lone MoveToElement 311 if (!m_path.elementCount()) 312 m_path.arcMoveTo(xs, ys, width, height, sa); 313 else if (!radius) { 314 m_path.lineTo(xc, yc); 315 return; 316 } 317 318 m_path.arcTo(xs, ys, width, height, sa, span); 319 320} 321 322void Path::addRect(const FloatRect& r) 323{ 324 m_path.addRect(r.x(), r.y(), r.width(), r.height()); 325} 326 327void Path::addEllipse(const FloatRect& r) 328{ 329 m_path.addEllipse(r.x(), r.y(), r.width(), r.height()); 330} 331 332void Path::clear() 333{ 334 if (!m_path.elementCount()) 335 return; 336 m_path = QPainterPath(); 337} 338 339bool Path::isEmpty() const 340{ 341 // Don't use QPainterPath::isEmpty(), as that also returns true if there's only 342 // one initial MoveTo element in the path. 343 return !m_path.elementCount(); 344} 345 346bool Path::hasCurrentPoint() const 347{ 348 return !isEmpty(); 349} 350 351FloatPoint Path::currentPoint() const 352{ 353 return m_path.currentPosition(); 354} 355 356void Path::apply(void* info, PathApplierFunction function) const 357{ 358 PathElement pelement; 359 FloatPoint points[3]; 360 pelement.points = points; 361 for (int i = 0; i < m_path.elementCount(); ++i) { 362 const QPainterPath::Element& cur = m_path.elementAt(i); 363 364 switch (cur.type) { 365 case QPainterPath::MoveToElement: 366 pelement.type = PathElementMoveToPoint; 367 pelement.points[0] = QPointF(cur); 368 function(info, &pelement); 369 break; 370 case QPainterPath::LineToElement: 371 pelement.type = PathElementAddLineToPoint; 372 pelement.points[0] = QPointF(cur); 373 function(info, &pelement); 374 break; 375 case QPainterPath::CurveToElement: 376 { 377 const QPainterPath::Element& c1 = m_path.elementAt(i + 1); 378 const QPainterPath::Element& c2 = m_path.elementAt(i + 2); 379 380 Q_ASSERT(c1.type == QPainterPath::CurveToDataElement); 381 Q_ASSERT(c2.type == QPainterPath::CurveToDataElement); 382 383 pelement.type = PathElementAddCurveToPoint; 384 pelement.points[0] = QPointF(cur); 385 pelement.points[1] = QPointF(c1); 386 pelement.points[2] = QPointF(c2); 387 function(info, &pelement); 388 389 i += 2; 390 break; 391 } 392 case QPainterPath::CurveToDataElement: 393 Q_ASSERT(false); 394 } 395 } 396} 397 398void Path::transform(const AffineTransform& transform) 399{ 400 QTransform qTransform(transform); 401 m_path = qTransform.map(m_path); 402} 403 404float Path::length() const 405{ 406 return m_path.length(); 407} 408 409FloatPoint Path::pointAtLength(float length, bool& ok) const 410{ 411 ok = (length >= 0 && length <= m_path.length()); 412 413 qreal percent = m_path.percentAtLength(length); 414 QPointF point = m_path.pointAtPercent(percent); 415 416 return point; 417} 418 419float Path::normalAngleAtLength(float length, bool& ok) const 420{ 421 ok = (length >= 0 && length <= m_path.length()); 422 423 qreal percent = m_path.percentAtLength(length); 424 qreal angle = m_path.angleAtPercent(percent); 425 426 // Normalize angle value. 427 // QPainterPath returns angle values with the origo being at the top left corner. 428 // In case of moveTo(0, 0) and addLineTo(0, 10) the angle is 270, 429 // while the caller expects it to be 90. 430 // Normalize the value by mirroring it to the x-axis. 431 // For more info look at pathLengthApplierFunction(). 432 if (angle > 0) 433 angle = 360 - angle; 434 return angle; 435} 436 437} 438 439// vim: ts=4 sw=4 et 440