dom/svg/nsSVGPathDataParser.cpp

   1 /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* This Source Code Form is subject to the terms of the Mozilla Public
   3  * License, v. 2.0. If a copy of the MPL was not distributed with this
   4  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   5
   6 #include "nsSVGPathDataParser.h"
   7
   8 #include "mozilla/gfx/Point.h"
   9 #include "nsSVGDataParser.h"
  10 #include "SVGContentUtils.h"
  11 #include "SVGPathData.h"
  12 #include "SVGPathSegUtils.h"
  13
  14 using namespace mozilla;
  15 using namespace mozilla::gfx;
  16
  17 static inline char16_t ToUpper(char16_t aCh)
  18 {
  19   return aCh >= 'a' && aCh <= 'z' ? aCh - 'a' + 'A' : aCh;
  20 }
  21
  22 bool
  23 nsSVGPathDataParser::Parse()
  24 {
  25   mPathSegList->Clear();
  26   return ParsePath();
  27 }
  28
  29 //----------------------------------------------------------------------
  30
  31 bool
  32 nsSVGPathDataParser::ParseCoordPair(float& aX, float& aY)
  33 {
  34   return SVGContentUtils::ParseNumber(mIter, mEnd, aX) &&
  35          SkipCommaWsp() &&
  36          SVGContentUtils::ParseNumber(mIter, mEnd, aY);
  37 }
  38
  39 bool
  40 nsSVGPathDataParser::ParseFlag(bool& aFlag)
  41 {
  42   if (mIter == mEnd || (*mIter != '0' && *mIter != '1')) {
  43     return false;
  44   }
  45   aFlag = (*mIter == '1');
  46
  47   ++mIter;
  48   return true;
  49 }
  50
  51 //----------------------------------------------------------------------
  52
  53 bool
  54 nsSVGPathDataParser::ParsePath()
  55 {
  56   while (SkipWsp()) {
  57     if (!ParseSubPath()) {
  58       return false;
  59     }
  60   }
  61
  62   return true;
  63 }
  64
  65 //----------------------------------------------------------------------
  66
  67 bool
  68 nsSVGPathDataParser::ParseSubPath()
  69 {
  70   return ParseMoveto() && ParseSubPathElements();
  71 }
  72
  73 bool
  74 nsSVGPathDataParser::ParseSubPathElements()
  75 {
  76   while (SkipWsp() && !IsStartOfSubPath()) {
  77     char16_t commandType = ToUpper(*mIter);
  78
  79     // Upper case commands have absolute co-ordinates,
  80     // lower case commands have relative co-ordinates.
  81     bool absCoords = commandType == *mIter;
  82
  83     ++mIter;
  84     SkipWsp();
  85
  86     if (!ParseSubPathElement(commandType, absCoords)) {
  87       return false;
  88     }
  89   }
  90   return true;
  91 }
  92
  93 bool
  94 nsSVGPathDataParser::ParseSubPathElement(char16_t aCommandType,
  95                                          bool aAbsCoords)
  96 {
  97   switch (aCommandType) {
  98     case 'Z':
  99       return ParseClosePath();
 100     case 'L':
 101       return ParseLineto(aAbsCoords);
 102     case 'H':
 103       return ParseHorizontalLineto(aAbsCoords);
 104     case 'V':
 105       return ParseVerticalLineto(aAbsCoords);
 106     case 'C':
 107       return ParseCurveto(aAbsCoords);
 108     case 'S':
 109       return ParseSmoothCurveto(aAbsCoords);
 110     case 'Q':
 111       return ParseQuadBezierCurveto(aAbsCoords);
 112     case 'T':
 113       return ParseSmoothQuadBezierCurveto(aAbsCoords);
 114     case 'A':
 115       return ParseEllipticalArc(aAbsCoords);
 116   }
 117   return false;
 118 }
 119
 120 bool
 121 nsSVGPathDataParser::IsStartOfSubPath() const
 122 {
 123   return *mIter == 'm' || *mIter == 'M';
 124 }
 125
 126 //----------------------------------------------------------------------
 127
 128 bool
 129 nsSVGPathDataParser::ParseMoveto()
 130 {
 131   if (!IsStartOfSubPath()) {
 132     return false;
 133   }
 134
 135   bool absCoords = (*mIter == 'M');
 136
 137   ++mIter;
 138   SkipWsp();
 139
 140   float x, y;
 141   if (!ParseCoordPair(x, y)) {
 142     return false;
 143   }
 144
 145   if (NS_FAILED(mPathSegList->AppendSeg(
 146                   absCoords ? PATHSEG_MOVETO_ABS : PATHSEG_MOVETO_REL,
 147                   x, y))) {
 148     return false;
 149   }
 150
 151   if (!SkipWsp() || IsAlpha(*mIter)) {
 152     // End of data, or start of a new command
 153     return true;
 154   }
 155
 156   SkipCommaWsp();
 157
 158   // Per SVG 1.1 Section 8.3.2
 159   // If a moveto is followed by multiple pairs of coordinates,
 160   // the subsequent pairs are treated as implicit lineto commands
 161   return ParseLineto(absCoords);
 162 }
 163
 164 //----------------------------------------------------------------------
 165
 166 bool
 167 nsSVGPathDataParser::ParseClosePath()
 168 {
 169   return NS_SUCCEEDED(mPathSegList->AppendSeg(PATHSEG_CLOSEPATH));
 170 }
 171
 172 //----------------------------------------------------------------------
 173
 174 bool
 175 nsSVGPathDataParser::ParseLineto(bool aAbsCoords)
 176 {
 177   while (true) {
 178     float x, y;
 179     if (!ParseCoordPair(x, y)) {
 180       return false;
 181     }
 182
 183     if (NS_FAILED(mPathSegList->AppendSeg(
 184                    aAbsCoords ? PATHSEG_LINETO_ABS : PATHSEG_LINETO_REL,
 185                    x, y))) {
 186       return false;
 187     }
 188
 189     if (!SkipWsp() || IsAlpha(*mIter)) {
 190       // End of data, or start of a new command
 191       return true;
 192     }
 193     SkipCommaWsp();
 194   }
 195 }
 196
 197 //----------------------------------------------------------------------
 198
 199 bool
 200 nsSVGPathDataParser::ParseHorizontalLineto(bool aAbsCoords)
 201 {
 202   while (true) {
 203     float x;
 204     if (!SVGContentUtils::ParseNumber(mIter, mEnd, x)) {
 205       return false;
 206     }
 207
 208     if (NS_FAILED(mPathSegList->AppendSeg(
 209                     aAbsCoords ? PATHSEG_LINETO_HORIZONTAL_ABS : PATHSEG_LINETO_HORIZONTAL_REL,
 210                     x))) {
 211       return false;
 212     }
 213
 214     if (!SkipWsp() || IsAlpha(*mIter)) {
 215       // End of data, or start of a new command
 216       return true;
 217     }
 218     SkipCommaWsp();
 219   }
 220 }
 221
 222 //----------------------------------------------------------------------
 223
 224 bool
 225 nsSVGPathDataParser::ParseVerticalLineto(bool aAbsCoords)
 226 {
 227   while (true) {
 228     float y;
 229     if (!SVGContentUtils::ParseNumber(mIter, mEnd, y)) {
 230       return false;
 231     }
 232
 233     if (NS_FAILED(mPathSegList->AppendSeg(
 234                     aAbsCoords ? PATHSEG_LINETO_VERTICAL_ABS : PATHSEG_LINETO_VERTICAL_REL,
 235                     y))) {
 236       return false;
 237     }
 238
 239     if (!SkipWsp() || IsAlpha(*mIter)) {
 240       // End of data, or start of a new command
 241       return true;
 242     }
 243     SkipCommaWsp();
 244   }
 245 }
 246
 247 //----------------------------------------------------------------------
 248
 249 bool
 250 nsSVGPathDataParser::ParseCurveto(bool aAbsCoords)
 251 {
 252   while (true) {
 253     float x1, y1, x2, y2, x, y;
 254
 255     if (!(ParseCoordPair(x1, y1) &&
 256           SkipCommaWsp() &&
 257           ParseCoordPair(x2, y2) &&
 258           SkipCommaWsp() &&
 259           ParseCoordPair(x, y))) {
 260       return false;
 261     }
 262
 263     if (NS_FAILED(mPathSegList->AppendSeg(
 264                     aAbsCoords ? PATHSEG_CURVETO_CUBIC_ABS : PATHSEG_CURVETO_CUBIC_REL,
 265                     x1, y1, x2, y2, x, y))) {
 266       return false;
 267     }
 268
 269     if (!SkipWsp() || IsAlpha(*mIter)) {
 270       // End of data, or start of a new command
 271       return true;
 272     }
 273     SkipCommaWsp();
 274   }
 275 }
 276
 277 //----------------------------------------------------------------------
 278
 279 bool
 280 nsSVGPathDataParser::ParseSmoothCurveto(bool aAbsCoords)
 281 {
 282   while (true) {
 283     float x2, y2, x, y;
 284     if (!(ParseCoordPair(x2, y2) &&
 285           SkipCommaWsp() &&
 286           ParseCoordPair(x, y))) {
 287       return false;
 288     }
 289
 290     if (NS_FAILED(mPathSegList->AppendSeg(
 291                     aAbsCoords ? PATHSEG_CURVETO_CUBIC_SMOOTH_ABS : PATHSEG_CURVETO_CUBIC_SMOOTH_REL,
 292                     x2, y2, x, y))) {
 293       return false;
 294     }
 295
 296     if (!SkipWsp() || IsAlpha(*mIter)) {
 297       // End of data, or start of a new command
 298       return true;
 299     }
 300     SkipCommaWsp();
 301   }
 302 }
 303
 304 //----------------------------------------------------------------------
 305
 306 bool
 307 nsSVGPathDataParser::ParseQuadBezierCurveto(bool aAbsCoords)
 308 {
 309   while (true) {
 310     float x1, y1, x, y;
 311     if (!(ParseCoordPair(x1, y1) &&
 312          SkipCommaWsp() &&
 313          ParseCoordPair(x, y))) {
 314       return false;
 315     }
 316
 317     if (NS_FAILED(mPathSegList->AppendSeg(
 318                     aAbsCoords ? PATHSEG_CURVETO_QUADRATIC_ABS : PATHSEG_CURVETO_QUADRATIC_REL,
 319                     x1, y1, x, y))) {
 320       return false;
 321     }
 322
 323     if (!SkipWsp() || IsAlpha(*mIter)) {
 324       // Start of a new command
 325       return true;
 326     }
 327     SkipCommaWsp();
 328   }
 329 }
 330
 331 //----------------------------------------------------------------------
 332
 333 bool
 334 nsSVGPathDataParser::ParseSmoothQuadBezierCurveto(bool aAbsCoords)
 335 {
 336   while (true) {
 337     float x, y;
 338     if (!ParseCoordPair(x, y)) {
 339       return false;
 340     }
 341
 342     if (NS_FAILED(mPathSegList->AppendSeg(
 343                     aAbsCoords ? PATHSEG_CURVETO_QUADRATIC_SMOOTH_ABS : PATHSEG_CURVETO_QUADRATIC_SMOOTH_REL,
 344                     x, y))) {
 345       return false;
 346     }
 347
 348     if (!SkipWsp() || IsAlpha(*mIter)) {
 349       // End of data, or start of a new command
 350       return true;
 351     }
 352     SkipCommaWsp();
 353   }
 354 }
 355
 356 //----------------------------------------------------------------------
 357
 358 bool
 359 nsSVGPathDataParser::ParseEllipticalArc(bool aAbsCoords)
 360 {
 361   while (true) {
 362     float r1, r2, angle, x, y;
 363     bool largeArcFlag, sweepFlag;
 364
 365     if (!(SVGContentUtils::ParseNumber(mIter, mEnd, r1) &&
 366           SkipCommaWsp() &&
 367           SVGContentUtils::ParseNumber(mIter, mEnd, r2) &&
 368           SkipCommaWsp() &&
 369           SVGContentUtils::ParseNumber(mIter, mEnd, angle)&&
 370           SkipCommaWsp() &&
 371           ParseFlag(largeArcFlag) &&
 372           SkipCommaWsp() &&
 373           ParseFlag(sweepFlag) &&
 374           SkipCommaWsp() &&
 375           ParseCoordPair(x, y))) {
 376       return false;
 377     }
 378
 379     // We can only pass floats after 'type', and per the SVG spec for arc,
 380     // non-zero args are treated at 'true'.
 381     if (NS_FAILED(mPathSegList->AppendSeg(
 382                     aAbsCoords ? PATHSEG_ARC_ABS : PATHSEG_ARC_REL,
 383                     r1, r2, angle,
 384                     largeArcFlag ? 1.0f : 0.0f,
 385                     sweepFlag ? 1.0f : 0.0f,
 386                     x, y))) {
 387       return false;
 388     }
 389
 390     if (!SkipWsp() || IsAlpha(*mIter)) {
 391       // End of data, or start of a new command
 392       return true;
 393     }
 394     SkipCommaWsp();
 395   }
 396 }
 397
 398 //-----------------------------------------------------------------------
 399
 400
 401
 402
 403 static double
 404 CalcVectorAngle(double ux, double uy, double vx, double vy)
 405 {
 406   double ta = atan2(uy, ux);
 407   double tb = atan2(vy, vx);
 408   if (tb >= ta)
 409     return tb-ta;
 410   return 2 * M_PI - (ta-tb);
 411 }
 412
 413
 414 nsSVGArcConverter::nsSVGArcConverter(const Point& from,
 415                                      const Point& to,
 416                                      const Point& radii,
 417                                      double angle,
 418                                      bool largeArcFlag,
 419                                      bool sweepFlag)
 420 {
 421   const double radPerDeg = M_PI/180.0;
 422   mSegIndex = 0;
 423
 424   if (from == to) {
 425     mNumSegs = 0;
 426     return;
 427   }
 428
 429   // Convert to center parameterization as shown in
 430   // http://www.w3.org/TR/SVG/implnote.html
 431   mRx = fabs(radii.x);
 432   mRy = fabs(radii.y);
 433
 434   mSinPhi = sin(angle*radPerDeg);
 435   mCosPhi = cos(angle*radPerDeg);
 436
 437   double x1dash =  mCosPhi * (from.x-to.x)/2.0 + mSinPhi * (from.y-to.y)/2.0;
 438   double y1dash = -mSinPhi * (from.x-to.x)/2.0 + mCosPhi * (from.y-to.y)/2.0;
 439
 440   double root;
 441   double numerator = mRx*mRx*mRy*mRy - mRx*mRx*y1dash*y1dash -
 442                      mRy*mRy*x1dash*x1dash;
 443
 444   if (numerator < 0.0) {
 445     //  If mRx , mRy and are such that there is no solution (basically,
 446     //  the ellipse is not big enough to reach from 'from' to 'to'
 447     //  then the ellipse is scaled up uniformly until there is
 448     //  exactly one solution (until the ellipse is just big enough).
 449
 450     // -> find factor s, such that numerator' with mRx'=s*mRx and
 451     //    mRy'=s*mRy becomes 0 :
 452     double s = sqrt(1.0 - numerator/(mRx*mRx*mRy*mRy));
 453
 454     mRx *= s;
 455     mRy *= s;
 456     root = 0.0;
 457
 458   }
 459   else {
 460     root = (largeArcFlag == sweepFlag ? -1.0 : 1.0) *
 461       sqrt( numerator/(mRx*mRx*y1dash*y1dash + mRy*mRy*x1dash*x1dash) );
 462   }
 463
 464   double cxdash = root*mRx*y1dash/mRy;
 465   double cydash = -root*mRy*x1dash/mRx;
 466
 467   mC.x = mCosPhi * cxdash - mSinPhi * cydash + (from.x+to.x)/2.0;
 468   mC.y = mSinPhi * cxdash + mCosPhi * cydash + (from.y+to.y)/2.0;
 469   mTheta = CalcVectorAngle(1.0, 0.0, (x1dash-cxdash)/mRx, (y1dash-cydash)/mRy);
 470   double dtheta = CalcVectorAngle((x1dash-cxdash)/mRx, (y1dash-cydash)/mRy,
 471                                   (-x1dash-cxdash)/mRx, (-y1dash-cydash)/mRy);
 472   if (!sweepFlag && dtheta>0)
 473     dtheta -= 2.0*M_PI;
 474   else if (sweepFlag && dtheta<0)
 475     dtheta += 2.0*M_PI;
 476
 477   // Convert into cubic bezier segments <= 90deg
 478   mNumSegs = static_cast<int>(ceil(fabs(dtheta/(M_PI/2.0))));
 479   mDelta = dtheta/mNumSegs;
 480   mT = 8.0/3.0 * sin(mDelta/4.0) * sin(mDelta/4.0) / sin(mDelta/2.0);
 481
 482   mFrom = from;
 483 }
 484
 485 bool
 486 nsSVGArcConverter::GetNextSegment(Point* cp1, Point* cp2, Point* to)
 487 {
 488   if (mSegIndex == mNumSegs) {
 489     return false;
 490   }
 491
 492   double cosTheta1 = cos(mTheta);
 493   double sinTheta1 = sin(mTheta);
 494   double theta2 = mTheta + mDelta;
 495   double cosTheta2 = cos(theta2);
 496   double sinTheta2 = sin(theta2);
 497
 498   // a) calculate endpoint of the segment:
 499   to->x = mCosPhi * mRx*cosTheta2 - mSinPhi * mRy*sinTheta2 + mC.x;
 500   to->y = mSinPhi * mRx*cosTheta2 + mCosPhi * mRy*sinTheta2 + mC.y;
 501
 502   // b) calculate gradients at start/end points of segment:
 503   cp1->x = mFrom.x + mT * ( - mCosPhi * mRx*sinTheta1 - mSinPhi * mRy*cosTheta1);
 504   cp1->y = mFrom.y + mT * ( - mSinPhi * mRx*sinTheta1 + mCosPhi * mRy*cosTheta1);
 505
 506   cp2->x = to->x + mT * ( mCosPhi * mRx*sinTheta2 + mSinPhi * mRy*cosTheta2);
 507   cp2->y = to->y + mT * ( mSinPhi * mRx*sinTheta2 - mCosPhi * mRy*cosTheta2);
 508
 509   // do next segment
 510   mTheta = theta2;
 511   mFrom = *to;
 512   ++mSegIndex;
 513
 514   return true;
 515 }