dom/svg/SVGPathDataParser.cpp

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