dom/svg/SVGPathSegUtils.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 "SVGPathSegUtils.h"
   8
   9 #include "mozilla/ArrayUtils.h"  // MOZ_ARRAY_LENGTH
  10 #include "gfx2DGlue.h"
  11 #include "SVGPathDataParser.h"
  12 #include "nsMathUtils.h"
  13 #include "nsTextFormatter.h"
  14
  15 using namespace mozilla::dom::SVGPathSeg_Binding;
  16 using namespace mozilla::gfx;
  17
  18 namespace mozilla {
  19
  20 static const float PATH_SEG_LENGTH_TOLERANCE = 0.0000001f;
  21 static const uint32_t MAX_RECURSION = 10;
  22
  23 /* static */
  24 void SVGPathSegUtils::GetValueAsString(const float* aSeg, nsAString& aValue) {
  25   // Adding new seg type? Is the formatting below acceptable for the new types?
  26   static_assert(
  27       NS_SVG_PATH_SEG_LAST_VALID_TYPE == PATHSEG_CURVETO_QUADRATIC_SMOOTH_REL,
  28       "Update GetValueAsString for the new value.");
  29   static_assert(NS_SVG_PATH_SEG_MAX_ARGS == 7,
  30                 "Add another case to the switch below.");
  31
  32   uint32_t type = DecodeType(aSeg[0]);
  33   char16_t typeAsChar = GetPathSegTypeAsLetter(type);
  34
  35   // Special case arcs:
  36   if (IsArcType(type)) {
  37     bool largeArcFlag = aSeg[4] != 0.0f;
  38     bool sweepFlag = aSeg[5] != 0.0f;
  39     nsTextFormatter::ssprintf(aValue, u"%c%g,%g %g %d,%d %g,%g", typeAsChar,
  40                               aSeg[1], aSeg[2], aSeg[3], largeArcFlag,
  41                               sweepFlag, aSeg[6], aSeg[7]);
  42   } else {
  43     switch (ArgCountForType(type)) {
  44       case 0:
  45         aValue = typeAsChar;
  46         break;
  47
  48       case 1:
  49         nsTextFormatter::ssprintf(aValue, u"%c%g", typeAsChar, aSeg[1]);
  50         break;
  51
  52       case 2:
  53         nsTextFormatter::ssprintf(aValue, u"%c%g,%g", typeAsChar, aSeg[1],
  54                                   aSeg[2]);
  55         break;
  56
  57       case 4:
  58         nsTextFormatter::ssprintf(aValue, u"%c%g,%g %g,%g", typeAsChar, aSeg[1],
  59                                   aSeg[2], aSeg[3], aSeg[4]);
  60         break;
  61
  62       case 6:
  63         nsTextFormatter::ssprintf(aValue, u"%c%g,%g %g,%g %g,%g", typeAsChar,
  64                                   aSeg[1], aSeg[2], aSeg[3], aSeg[4], aSeg[5],
  65                                   aSeg[6]);
  66         break;
  67
  68       default:
  69         MOZ_ASSERT(false, "Unknown segment type");
  70         aValue = u"<unknown-segment-type>";
  71         return;
  72     }
  73   }
  74 }
  75
  76 static float CalcDistanceBetweenPoints(const Point& aP1, const Point& aP2) {
  77   return NS_hypot(aP2.x - aP1.x, aP2.y - aP1.y);
  78 }
  79
  80 static void SplitQuadraticBezier(const Point* aCurve, Point* aLeft,
  81                                  Point* aRight) {
  82   aLeft[0].x = aCurve[0].x;
  83   aLeft[0].y = aCurve[0].y;
  84   aRight[2].x = aCurve[2].x;
  85   aRight[2].y = aCurve[2].y;
  86   aLeft[1].x = (aCurve[0].x + aCurve[1].x) / 2;
  87   aLeft[1].y = (aCurve[0].y + aCurve[1].y) / 2;
  88   aRight[1].x = (aCurve[1].x + aCurve[2].x) / 2;
  89   aRight[1].y = (aCurve[1].y + aCurve[2].y) / 2;
  90   aLeft[2].x = aRight[0].x = (aLeft[1].x + aRight[1].x) / 2;
  91   aLeft[2].y = aRight[0].y = (aLeft[1].y + aRight[1].y) / 2;
  92 }
  93
  94 static void SplitCubicBezier(const Point* aCurve, Point* aLeft, Point* aRight) {
  95   Point tmp;
  96   tmp.x = (aCurve[1].x + aCurve[2].x) / 4;
  97   tmp.y = (aCurve[1].y + aCurve[2].y) / 4;
  98   aLeft[0].x = aCurve[0].x;
  99   aLeft[0].y = aCurve[0].y;
 100   aRight[3].x = aCurve[3].x;
 101   aRight[3].y = aCurve[3].y;
 102   aLeft[1].x = (aCurve[0].x + aCurve[1].x) / 2;
 103   aLeft[1].y = (aCurve[0].y + aCurve[1].y) / 2;
 104   aRight[2].x = (aCurve[2].x + aCurve[3].x) / 2;
 105   aRight[2].y = (aCurve[2].y + aCurve[3].y) / 2;
 106   aLeft[2].x = aLeft[1].x / 2 + tmp.x;
 107   aLeft[2].y = aLeft[1].y / 2 + tmp.y;
 108   aRight[1].x = aRight[2].x / 2 + tmp.x;
 109   aRight[1].y = aRight[2].y / 2 + tmp.y;
 110   aLeft[3].x = aRight[0].x = (aLeft[2].x + aRight[1].x) / 2;
 111   aLeft[3].y = aRight[0].y = (aLeft[2].y + aRight[1].y) / 2;
 112 }
 113
 114 static float CalcBezLengthHelper(const Point* aCurve, uint32_t aNumPts,
 115                                  uint32_t aRecursionCount,
 116                                  void (*aSplit)(const Point*, Point*, Point*)) {
 117   Point left[4];
 118   Point right[4];
 119   float length = 0, dist;
 120   for (uint32_t i = 0; i < aNumPts - 1; i++) {
 121     length += CalcDistanceBetweenPoints(aCurve[i], aCurve[i + 1]);
 122   }
 123   dist = CalcDistanceBetweenPoints(aCurve[0], aCurve[aNumPts - 1]);
 124   if (length - dist > PATH_SEG_LENGTH_TOLERANCE &&
 125       aRecursionCount < MAX_RECURSION) {
 126     aSplit(aCurve, left, right);
 127     ++aRecursionCount;
 128     return CalcBezLengthHelper(left, aNumPts, aRecursionCount, aSplit) +
 129            CalcBezLengthHelper(right, aNumPts, aRecursionCount, aSplit);
 130   }
 131   return length;
 132 }
 133
 134 static inline float CalcLengthOfCubicBezier(const Point& aPos,
 135                                             const Point& aCP1,
 136                                             const Point& aCP2,
 137                                             const Point& aTo) {
 138   Point curve[4] = {aPos, aCP1, aCP2, aTo};
 139   return CalcBezLengthHelper(curve, 4, 0, SplitCubicBezier);
 140 }
 141
 142 static inline float CalcLengthOfQuadraticBezier(const Point& aPos,
 143                                                 const Point& aCP,
 144                                                 const Point& aTo) {
 145   Point curve[3] = {aPos, aCP, aTo};
 146   return CalcBezLengthHelper(curve, 3, 0, SplitQuadraticBezier);
 147 }
 148
 149 static void TraverseClosePath(const float* aArgs,
 150                               SVGPathTraversalState& aState) {
 151   if (aState.ShouldUpdateLengthAndControlPoints()) {
 152     aState.length += CalcDistanceBetweenPoints(aState.pos, aState.start);
 153     aState.cp1 = aState.cp2 = aState.start;
 154   }
 155   aState.pos = aState.start;
 156 }
 157
 158 static void TraverseMovetoAbs(const float* aArgs,
 159                               SVGPathTraversalState& aState) {
 160   aState.start = aState.pos = Point(aArgs[0], aArgs[1]);
 161   if (aState.ShouldUpdateLengthAndControlPoints()) {
 162     // aState.length is unchanged, since move commands don't affect path length.
 163     aState.cp1 = aState.cp2 = aState.start;
 164   }
 165 }
 166
 167 static void TraverseMovetoRel(const float* aArgs,
 168                               SVGPathTraversalState& aState) {
 169   aState.start = aState.pos += Point(aArgs[0], aArgs[1]);
 170   if (aState.ShouldUpdateLengthAndControlPoints()) {
 171     // aState.length is unchanged, since move commands don't affect path length.
 172     aState.cp1 = aState.cp2 = aState.start;
 173   }
 174 }
 175
 176 static void TraverseLinetoAbs(const float* aArgs,
 177                               SVGPathTraversalState& aState) {
 178   Point to(aArgs[0], aArgs[1]);
 179   if (aState.ShouldUpdateLengthAndControlPoints()) {
 180     aState.length += CalcDistanceBetweenPoints(aState.pos, to);
 181     aState.cp1 = aState.cp2 = to;
 182   }
 183   aState.pos = to;
 184 }
 185
 186 static void TraverseLinetoRel(const float* aArgs,
 187                               SVGPathTraversalState& aState) {
 188   Point to = aState.pos + Point(aArgs[0], aArgs[1]);
 189   if (aState.ShouldUpdateLengthAndControlPoints()) {
 190     aState.length += CalcDistanceBetweenPoints(aState.pos, to);
 191     aState.cp1 = aState.cp2 = to;
 192   }
 193   aState.pos = to;
 194 }
 195
 196 static void TraverseLinetoHorizontalAbs(const float* aArgs,
 197                                         SVGPathTraversalState& aState) {
 198   Point to(aArgs[0], aState.pos.y);
 199   if (aState.ShouldUpdateLengthAndControlPoints()) {
 200     aState.length += std::fabs(to.x - aState.pos.x);
 201     aState.cp1 = aState.cp2 = to;
 202   }
 203   aState.pos = to;
 204 }
 205
 206 static void TraverseLinetoHorizontalRel(const float* aArgs,
 207                                         SVGPathTraversalState& aState) {
 208   aState.pos.x += aArgs[0];
 209   if (aState.ShouldUpdateLengthAndControlPoints()) {
 210     aState.length += std::fabs(aArgs[0]);
 211     aState.cp1 = aState.cp2 = aState.pos;
 212   }
 213 }
 214
 215 static void TraverseLinetoVerticalAbs(const float* aArgs,
 216                                       SVGPathTraversalState& aState) {
 217   Point to(aState.pos.x, aArgs[0]);
 218   if (aState.ShouldUpdateLengthAndControlPoints()) {
 219     aState.length += std::fabs(to.y - aState.pos.y);
 220     aState.cp1 = aState.cp2 = to;
 221   }
 222   aState.pos = to;
 223 }
 224
 225 static void TraverseLinetoVerticalRel(const float* aArgs,
 226                                       SVGPathTraversalState& aState) {
 227   aState.pos.y += aArgs[0];
 228   if (aState.ShouldUpdateLengthAndControlPoints()) {
 229     aState.length += std::fabs(aArgs[0]);
 230     aState.cp1 = aState.cp2 = aState.pos;
 231   }
 232 }
 233
 234 static void TraverseCurvetoCubicAbs(const float* aArgs,
 235                                     SVGPathTraversalState& aState) {
 236   Point to(aArgs[4], aArgs[5]);
 237   if (aState.ShouldUpdateLengthAndControlPoints()) {
 238     Point cp1(aArgs[0], aArgs[1]);
 239     Point cp2(aArgs[2], aArgs[3]);
 240     aState.length += (float)CalcLengthOfCubicBezier(aState.pos, cp1, cp2, to);
 241     aState.cp2 = cp2;
 242     aState.cp1 = to;
 243   }
 244   aState.pos = to;
 245 }
 246
 247 static void TraverseCurvetoCubicSmoothAbs(const float* aArgs,
 248                                           SVGPathTraversalState& aState) {
 249   Point to(aArgs[2], aArgs[3]);
 250   if (aState.ShouldUpdateLengthAndControlPoints()) {
 251     Point cp1 = aState.pos - (aState.cp2 - aState.pos);
 252     Point cp2(aArgs[0], aArgs[1]);
 253     aState.length += (float)CalcLengthOfCubicBezier(aState.pos, cp1, cp2, to);
 254     aState.cp2 = cp2;
 255     aState.cp1 = to;
 256   }
 257   aState.pos = to;
 258 }
 259
 260 static void TraverseCurvetoCubicRel(const float* aArgs,
 261                                     SVGPathTraversalState& aState) {
 262   Point to = aState.pos + Point(aArgs[4], aArgs[5]);
 263   if (aState.ShouldUpdateLengthAndControlPoints()) {
 264     Point cp1 = aState.pos + Point(aArgs[0], aArgs[1]);
 265     Point cp2 = aState.pos + Point(aArgs[2], aArgs[3]);
 266     aState.length += (float)CalcLengthOfCubicBezier(aState.pos, cp1, cp2, to);
 267     aState.cp2 = cp2;
 268     aState.cp1 = to;
 269   }
 270   aState.pos = to;
 271 }
 272
 273 static void TraverseCurvetoCubicSmoothRel(const float* aArgs,
 274                                           SVGPathTraversalState& aState) {
 275   Point to = aState.pos + Point(aArgs[2], aArgs[3]);
 276   if (aState.ShouldUpdateLengthAndControlPoints()) {
 277     Point cp1 = aState.pos - (aState.cp2 - aState.pos);
 278     Point cp2 = aState.pos + Point(aArgs[0], aArgs[1]);
 279     aState.length += (float)CalcLengthOfCubicBezier(aState.pos, cp1, cp2, to);
 280     aState.cp2 = cp2;
 281     aState.cp1 = to;
 282   }
 283   aState.pos = to;
 284 }
 285
 286 static void TraverseCurvetoQuadraticAbs(const float* aArgs,
 287                                         SVGPathTraversalState& aState) {
 288   Point to(aArgs[2], aArgs[3]);
 289   if (aState.ShouldUpdateLengthAndControlPoints()) {
 290     Point cp(aArgs[0], aArgs[1]);
 291     aState.length += (float)CalcLengthOfQuadraticBezier(aState.pos, cp, to);
 292     aState.cp1 = cp;
 293     aState.cp2 = to;
 294   }
 295   aState.pos = to;
 296 }
 297
 298 static void TraverseCurvetoQuadraticSmoothAbs(const float* aArgs,
 299                                               SVGPathTraversalState& aState) {
 300   Point to(aArgs[0], aArgs[1]);
 301   if (aState.ShouldUpdateLengthAndControlPoints()) {
 302     Point cp = aState.pos - (aState.cp1 - aState.pos);
 303     aState.length += (float)CalcLengthOfQuadraticBezier(aState.pos, cp, to);
 304     aState.cp1 = cp;
 305     aState.cp2 = to;
 306   }
 307   aState.pos = to;
 308 }
 309
 310 static void TraverseCurvetoQuadraticRel(const float* aArgs,
 311                                         SVGPathTraversalState& aState) {
 312   Point to = aState.pos + Point(aArgs[2], aArgs[3]);
 313   if (aState.ShouldUpdateLengthAndControlPoints()) {
 314     Point cp = aState.pos + Point(aArgs[0], aArgs[1]);
 315     aState.length += (float)CalcLengthOfQuadraticBezier(aState.pos, cp, to);
 316     aState.cp1 = cp;
 317     aState.cp2 = to;
 318   }
 319   aState.pos = to;
 320 }
 321
 322 static void TraverseCurvetoQuadraticSmoothRel(const float* aArgs,
 323                                               SVGPathTraversalState& aState) {
 324   Point to = aState.pos + Point(aArgs[0], aArgs[1]);
 325   if (aState.ShouldUpdateLengthAndControlPoints()) {
 326     Point cp = aState.pos - (aState.cp1 - aState.pos);
 327     aState.length += (float)CalcLengthOfQuadraticBezier(aState.pos, cp, to);
 328     aState.cp1 = cp;
 329     aState.cp2 = to;
 330   }
 331   aState.pos = to;
 332 }
 333
 334 static void TraverseArcAbs(const float* aArgs, SVGPathTraversalState& aState) {
 335   Point to(aArgs[5], aArgs[6]);
 336   if (aState.ShouldUpdateLengthAndControlPoints()) {
 337     float dist = 0;
 338     Point radii(aArgs[0], aArgs[1]);
 339     if (radii.x == 0.0f || radii.y == 0.0f) {
 340       dist = CalcDistanceBetweenPoints(aState.pos, to);
 341     } else {
 342       Point bez[4] = {aState.pos, Point(0, 0), Point(0, 0), Point(0, 0)};
 343       SVGArcConverter converter(aState.pos, to, radii, aArgs[2], aArgs[3] != 0,
 344                                 aArgs[4] != 0);
 345       while (converter.GetNextSegment(&bez[1], &bez[2], &bez[3])) {
 346         dist += CalcBezLengthHelper(bez, 4, 0, SplitCubicBezier);
 347         bez[0] = bez[3];
 348       }
 349     }
 350     aState.length += dist;
 351     aState.cp1 = aState.cp2 = to;
 352   }
 353   aState.pos = to;
 354 }
 355
 356 static void TraverseArcRel(const float* aArgs, SVGPathTraversalState& aState) {
 357   Point to = aState.pos + Point(aArgs[5], aArgs[6]);
 358   if (aState.ShouldUpdateLengthAndControlPoints()) {
 359     float dist = 0;
 360     Point radii(aArgs[0], aArgs[1]);
 361     if (radii.x == 0.0f || radii.y == 0.0f) {
 362       dist = CalcDistanceBetweenPoints(aState.pos, to);
 363     } else {
 364       Point bez[4] = {aState.pos, Point(0, 0), Point(0, 0), Point(0, 0)};
 365       SVGArcConverter converter(aState.pos, to, radii, aArgs[2], aArgs[3] != 0,
 366                                 aArgs[4] != 0);
 367       while (converter.GetNextSegment(&bez[1], &bez[2], &bez[3])) {
 368         dist += CalcBezLengthHelper(bez, 4, 0, SplitCubicBezier);
 369         bez[0] = bez[3];
 370       }
 371     }
 372     aState.length += dist;
 373     aState.cp1 = aState.cp2 = to;
 374   }
 375   aState.pos = to;
 376 }
 377
 378 using TraverseFunc = void (*)(const float*, SVGPathTraversalState&);
 379
 380 static TraverseFunc gTraverseFuncTable[NS_SVG_PATH_SEG_TYPE_COUNT] = {
 381     nullptr,  //  0 == PATHSEG_UNKNOWN
 382     TraverseClosePath,
 383     TraverseMovetoAbs,
 384     TraverseMovetoRel,
 385     TraverseLinetoAbs,
 386     TraverseLinetoRel,
 387     TraverseCurvetoCubicAbs,
 388     TraverseCurvetoCubicRel,
 389     TraverseCurvetoQuadraticAbs,
 390     TraverseCurvetoQuadraticRel,
 391     TraverseArcAbs,
 392     TraverseArcRel,
 393     TraverseLinetoHorizontalAbs,
 394     TraverseLinetoHorizontalRel,
 395     TraverseLinetoVerticalAbs,
 396     TraverseLinetoVerticalRel,
 397     TraverseCurvetoCubicSmoothAbs,
 398     TraverseCurvetoCubicSmoothRel,
 399     TraverseCurvetoQuadraticSmoothAbs,
 400     TraverseCurvetoQuadraticSmoothRel};
 401
 402 /* static */
 403 void SVGPathSegUtils::TraversePathSegment(const float* aData,
 404                                           SVGPathTraversalState& aState) {
 405   static_assert(
 406       MOZ_ARRAY_LENGTH(gTraverseFuncTable) == NS_SVG_PATH_SEG_TYPE_COUNT,
 407       "gTraverseFuncTable is out of date");
 408   uint32_t type = DecodeType(aData[0]);
 409   gTraverseFuncTable[type](aData + 1, aState);
 410 }
 411
 412 }  // namespace mozilla