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"        // std::size
  10 #include "mozilla/ServoStyleConsts.h"  // StylePathCommand
  11 #include "gfx2DGlue.h"
  12 #include "SVGArcConverter.h"
  13 #include "nsMathUtils.h"
  14 #include "nsTextFormatter.h"
  15
  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 float CalcDistanceBetweenPoints(const Point& aP1, const Point& aP2) {
  24   return NS_hypot(aP2.x - aP1.x, aP2.y - aP1.y);
  25 }
  26
  27 static void SplitQuadraticBezier(const Point* aCurve, Point* aLeft,
  28                                  Point* aRight) {
  29   aLeft[0].x = aCurve[0].x;
  30   aLeft[0].y = aCurve[0].y;
  31   aRight[2].x = aCurve[2].x;
  32   aRight[2].y = aCurve[2].y;
  33   aLeft[1].x = (aCurve[0].x + aCurve[1].x) / 2;
  34   aLeft[1].y = (aCurve[0].y + aCurve[1].y) / 2;
  35   aRight[1].x = (aCurve[1].x + aCurve[2].x) / 2;
  36   aRight[1].y = (aCurve[1].y + aCurve[2].y) / 2;
  37   aLeft[2].x = aRight[0].x = (aLeft[1].x + aRight[1].x) / 2;
  38   aLeft[2].y = aRight[0].y = (aLeft[1].y + aRight[1].y) / 2;
  39 }
  40
  41 static void SplitCubicBezier(const Point* aCurve, Point* aLeft, Point* aRight) {
  42   Point tmp;
  43   tmp.x = (aCurve[1].x + aCurve[2].x) / 4;
  44   tmp.y = (aCurve[1].y + aCurve[2].y) / 4;
  45   aLeft[0].x = aCurve[0].x;
  46   aLeft[0].y = aCurve[0].y;
  47   aRight[3].x = aCurve[3].x;
  48   aRight[3].y = aCurve[3].y;
  49   aLeft[1].x = (aCurve[0].x + aCurve[1].x) / 2;
  50   aLeft[1].y = (aCurve[0].y + aCurve[1].y) / 2;
  51   aRight[2].x = (aCurve[2].x + aCurve[3].x) / 2;
  52   aRight[2].y = (aCurve[2].y + aCurve[3].y) / 2;
  53   aLeft[2].x = aLeft[1].x / 2 + tmp.x;
  54   aLeft[2].y = aLeft[1].y / 2 + tmp.y;
  55   aRight[1].x = aRight[2].x / 2 + tmp.x;
  56   aRight[1].y = aRight[2].y / 2 + tmp.y;
  57   aLeft[3].x = aRight[0].x = (aLeft[2].x + aRight[1].x) / 2;
  58   aLeft[3].y = aRight[0].y = (aLeft[2].y + aRight[1].y) / 2;
  59 }
  60
  61 static float CalcBezLengthHelper(const Point* aCurve, uint32_t aNumPts,
  62                                  uint32_t aRecursionCount,
  63                                  void (*aSplit)(const Point*, Point*, Point*)) {
  64   Point left[4];
  65   Point right[4];
  66   float length = 0, dist;
  67   for (uint32_t i = 0; i < aNumPts - 1; i++) {
  68     length += CalcDistanceBetweenPoints(aCurve[i], aCurve[i + 1]);
  69   }
  70   dist = CalcDistanceBetweenPoints(aCurve[0], aCurve[aNumPts - 1]);
  71   if (length - dist > PATH_SEG_LENGTH_TOLERANCE &&
  72       aRecursionCount < MAX_RECURSION) {
  73     aSplit(aCurve, left, right);
  74     ++aRecursionCount;
  75     return CalcBezLengthHelper(left, aNumPts, aRecursionCount, aSplit) +
  76            CalcBezLengthHelper(right, aNumPts, aRecursionCount, aSplit);
  77   }
  78   return length;
  79 }
  80
  81 static inline float CalcLengthOfCubicBezier(const Point& aPos,
  82                                             const Point& aCP1,
  83                                             const Point& aCP2,
  84                                             const Point& aTo) {
  85   Point curve[4] = {aPos, aCP1, aCP2, aTo};
  86   return CalcBezLengthHelper(curve, 4, 0, SplitCubicBezier);
  87 }
  88
  89 static inline float CalcLengthOfQuadraticBezier(const Point& aPos,
  90                                                 const Point& aCP,
  91                                                 const Point& aTo) {
  92   Point curve[3] = {aPos, aCP, aTo};
  93   return CalcBezLengthHelper(curve, 3, 0, SplitQuadraticBezier);
  94 }
  95
  96 // Basically, this is just a variant version of the above TraverseXXX functions.
  97 // We just put those function inside this and use StylePathCommand instead.
  98 // This function and the above ones should be dropped by Bug 1388931.
  99 /* static */
 100 void SVGPathSegUtils::TraversePathSegment(const StylePathCommand& aCommand,
 101                                           SVGPathTraversalState& aState) {
 102   switch (aCommand.tag) {
 103     case StylePathCommand::Tag::Close:
 104       if (aState.ShouldUpdateLengthAndControlPoints()) {
 105         aState.length += CalcDistanceBetweenPoints(aState.pos, aState.start);
 106         aState.cp1 = aState.cp2 = aState.start;
 107       }
 108       aState.pos = aState.start;
 109       break;
 110     case StylePathCommand::Tag::Move: {
 111       const Point& p = aCommand.move.point.ToGfxPoint();
 112       aState.start = aState.pos =
 113           aCommand.move.by_to == StyleByTo::To ? p : aState.pos + p;
 114       if (aState.ShouldUpdateLengthAndControlPoints()) {
 115         // aState.length is unchanged, since move commands don't affect path=
 116         // length.
 117         aState.cp1 = aState.cp2 = aState.start;
 118       }
 119       break;
 120     }
 121     case StylePathCommand::Tag::Line: {
 122       Point to = aCommand.line.by_to == StyleByTo::To
 123                      ? aCommand.line.point.ToGfxPoint()
 124                      : aState.pos + aCommand.line.point.ToGfxPoint();
 125       if (aState.ShouldUpdateLengthAndControlPoints()) {
 126         aState.length += CalcDistanceBetweenPoints(aState.pos, to);
 127         aState.cp1 = aState.cp2 = to;
 128       }
 129       aState.pos = to;
 130       break;
 131     }
 132     case StylePathCommand::Tag::CubicCurve: {
 133       const bool isRelative = aCommand.cubic_curve.by_to == StyleByTo::By;
 134       Point to = isRelative
 135                      ? aState.pos + aCommand.cubic_curve.point.ToGfxPoint()
 136                      : aCommand.cubic_curve.point.ToGfxPoint();
 137       if (aState.ShouldUpdateLengthAndControlPoints()) {
 138         Point cp1 = aCommand.cubic_curve.control1.ToGfxPoint();
 139         Point cp2 = aCommand.cubic_curve.control2.ToGfxPoint();
 140         if (isRelative) {
 141           cp1 += aState.pos;
 142           cp2 += aState.pos;
 143         }
 144         aState.length +=
 145             (float)CalcLengthOfCubicBezier(aState.pos, cp1, cp2, to);
 146         aState.cp2 = cp2;
 147         aState.cp1 = to;
 148       }
 149       aState.pos = to;
 150       break;
 151     }
 152     case StylePathCommand::Tag::QuadCurve: {
 153       const bool isRelative = aCommand.quad_curve.by_to == StyleByTo::By;
 154       Point to = isRelative
 155                      ? aState.pos + aCommand.quad_curve.point.ToGfxPoint()
 156                      : aCommand.quad_curve.point.ToGfxPoint();
 157       if (aState.ShouldUpdateLengthAndControlPoints()) {
 158         Point cp = isRelative
 159                        ? aState.pos + aCommand.quad_curve.control1.ToGfxPoint()
 160                        : aCommand.quad_curve.control1.ToGfxPoint();
 161         aState.length += (float)CalcLengthOfQuadraticBezier(aState.pos, cp, to);
 162         aState.cp1 = cp;
 163         aState.cp2 = to;
 164       }
 165       aState.pos = to;
 166       break;
 167     }
 168     case StylePathCommand::Tag::Arc: {
 169       const auto& arc = aCommand.arc;
 170       Point to = arc.by_to == StyleByTo::To
 171                      ? arc.point.ToGfxPoint()
 172                      : aState.pos + arc.point.ToGfxPoint();
 173       if (aState.ShouldUpdateLengthAndControlPoints()) {
 174         float dist = 0;
 175         Point radii = arc.radii.ToGfxPoint();
 176         if (radii.x == 0.0f || radii.y == 0.0f) {
 177           dist = CalcDistanceBetweenPoints(aState.pos, to);
 178         } else {
 179           Point bez[4] = {aState.pos, Point(0, 0), Point(0, 0), Point(0, 0)};
 180           const bool largeArcFlag = arc.arc_size == StyleArcSize::Large;
 181           const bool sweepFlag = arc.arc_sweep == StyleArcSweep::Cw;
 182           SVGArcConverter converter(aState.pos, to, radii, arc.rotate,
 183                                     largeArcFlag, sweepFlag);
 184           while (converter.GetNextSegment(&bez[1], &bez[2], &bez[3])) {
 185             dist += CalcBezLengthHelper(bez, 4, 0, SplitCubicBezier);
 186             bez[0] = bez[3];
 187           }
 188         }
 189         aState.length += dist;
 190         aState.cp1 = aState.cp2 = to;
 191       }
 192       aState.pos = to;
 193       break;
 194     }
 195     case StylePathCommand::Tag::HLine: {
 196       Point to(aCommand.h_line.by_to == StyleByTo::To
 197                    ? aCommand.h_line.x
 198                    : aState.pos.x + aCommand.h_line.x,
 199                aState.pos.y);
 200       if (aState.ShouldUpdateLengthAndControlPoints()) {
 201         aState.length += std::fabs(to.x - aState.pos.x);
 202         aState.cp1 = aState.cp2 = to;
 203       }
 204       aState.pos = to;
 205       break;
 206     }
 207     case StylePathCommand::Tag::VLine: {
 208       Point to(aState.pos.x, aCommand.v_line.by_to == StyleByTo::To
 209                                  ? aCommand.v_line.y
 210                                  : aState.pos.y + aCommand.v_line.y);
 211       if (aState.ShouldUpdateLengthAndControlPoints()) {
 212         aState.length += std::fabs(to.y - aState.pos.y);
 213         aState.cp1 = aState.cp2 = to;
 214       }
 215       aState.pos = to;
 216       break;
 217     }
 218     case StylePathCommand::Tag::SmoothCubic: {
 219       const bool isRelative = aCommand.smooth_cubic.by_to == StyleByTo::By;
 220       Point to = isRelative
 221                      ? aState.pos + aCommand.smooth_cubic.point.ToGfxPoint()
 222                      : aCommand.smooth_cubic.point.ToGfxPoint();
 223       if (aState.ShouldUpdateLengthAndControlPoints()) {
 224         Point cp1 = aState.pos - (aState.cp2 - aState.pos);
 225         Point cp2 = isRelative ? aState.pos +
 226                                      aCommand.smooth_cubic.control2.ToGfxPoint()
 227                                : aCommand.smooth_cubic.control2.ToGfxPoint();
 228         aState.length +=
 229             (float)CalcLengthOfCubicBezier(aState.pos, cp1, cp2, to);
 230         aState.cp2 = cp2;
 231         aState.cp1 = to;
 232       }
 233       aState.pos = to;
 234       break;
 235     }
 236     case StylePathCommand::Tag::SmoothQuad: {
 237       Point to = aCommand.smooth_quad.by_to == StyleByTo::To
 238                      ? aCommand.smooth_quad.point.ToGfxPoint()
 239                      : aState.pos + aCommand.smooth_quad.point.ToGfxPoint();
 240       if (aState.ShouldUpdateLengthAndControlPoints()) {
 241         Point cp = aState.pos - (aState.cp1 - aState.pos);
 242         aState.length += (float)CalcLengthOfQuadraticBezier(aState.pos, cp, to);
 243         aState.cp1 = cp;
 244         aState.cp2 = to;
 245       }
 246       aState.pos = to;
 247       break;
 248     }
 249   }
 250 }
 251
 252 // Possible directions of an edge that doesn't immediately disqualify the path
 253 // as a rectangle.
 254 enum class EdgeDir {
 255   LEFT,
 256   RIGHT,
 257   UP,
 258   DOWN,
 259   // NONE represents (almost) zero-length edges, they should be ignored.
 260   NONE,
 261 };
 262
 263 Maybe<EdgeDir> GetDirection(Point v) {
 264   if (!std::isfinite(v.x.value) || !std::isfinite(v.y.value)) {
 265     return Nothing();
 266   }
 267
 268   bool x = fabs(v.x) > 0.001;
 269   bool y = fabs(v.y) > 0.001;
 270   if (x && y) {
 271     return Nothing();
 272   }
 273
 274   if (!x && !y) {
 275     return Some(EdgeDir::NONE);
 276   }
 277
 278   if (x) {
 279     return Some(v.x > 0.0 ? EdgeDir::RIGHT : EdgeDir::LEFT);
 280   }
 281
 282   return Some(v.y > 0.0 ? EdgeDir::DOWN : EdgeDir::UP);
 283 }
 284
 285 EdgeDir OppositeDirection(EdgeDir dir) {
 286   switch (dir) {
 287     case EdgeDir::LEFT:
 288       return EdgeDir::RIGHT;
 289     case EdgeDir::RIGHT:
 290       return EdgeDir::LEFT;
 291     case EdgeDir::UP:
 292       return EdgeDir::DOWN;
 293     case EdgeDir::DOWN:
 294       return EdgeDir::UP;
 295     default:
 296       return EdgeDir::NONE;
 297   }
 298 }
 299
 300 struct IsRectHelper {
 301   Point min;
 302   Point max;
 303   EdgeDir currentDir;
 304   // Index of the next corner.
 305   uint32_t idx;
 306   EdgeDir dirs[4];
 307
 308   bool Edge(Point from, Point to) {
 309     auto edge = to - from;
 310
 311     auto maybeDir = GetDirection(edge);
 312     if (maybeDir.isNothing()) {
 313       return false;
 314     }
 315
 316     EdgeDir dir = maybeDir.value();
 317
 318     if (dir == EdgeDir::NONE) {
 319       // zero-length edges aren't an issue.
 320       return true;
 321     }
 322
 323     if (dir != currentDir) {
 324       // The edge forms a corner with the previous edge.
 325       if (idx >= 4) {
 326         // We are at the 5th corner, can't be a rectangle.
 327         return false;
 328       }
 329
 330       if (dir == OppositeDirection(currentDir)) {
 331         // Can turn left or right but not a full 180 degrees.
 332         return false;
 333       }
 334
 335       dirs[idx] = dir;
 336       idx += 1;
 337       currentDir = dir;
 338     }
 339
 340     min.x = fmin(min.x, to.x);
 341     min.y = fmin(min.y, to.y);
 342     max.x = fmax(max.x, to.x);
 343     max.y = fmax(max.y, to.y);
 344
 345     return true;
 346   }
 347
 348   bool EndSubpath() {
 349     if (idx != 4) {
 350       return false;
 351     }
 352
 353     if (dirs[0] != OppositeDirection(dirs[2]) ||
 354         dirs[1] != OppositeDirection(dirs[3])) {
 355       return false;
 356     }
 357
 358     return true;
 359   }
 360 };
 361
 362 bool ApproxEqual(gfx::Point a, gfx::Point b) {
 363   auto v = b - a;
 364   return fabs(v.x) < 0.001 && fabs(v.y) < 0.001;
 365 }
 366
 367 Maybe<gfx::Rect> SVGPathToAxisAlignedRect(Span<const StylePathCommand> aPath) {
 368   Point pathStart(0.0, 0.0);
 369   Point segStart(0.0, 0.0);
 370   IsRectHelper helper = {
 371       Point(0.0, 0.0),
 372       Point(0.0, 0.0),
 373       EdgeDir::NONE,
 374       0,
 375       {EdgeDir::NONE, EdgeDir::NONE, EdgeDir::NONE, EdgeDir::NONE},
 376   };
 377
 378   for (const StylePathCommand& cmd : aPath) {
 379     switch (cmd.tag) {
 380       case StylePathCommand::Tag::Move: {
 381         Point to = cmd.move.point.ToGfxPoint();
 382         if (helper.idx != 0) {
 383           // This is overly strict since empty moveto sequences such as "M 10 12
 384           // M 3 2 M 0 0" render nothing, but I expect it won't make us miss a
 385           // lot of rect-shaped paths in practice and lets us avoidhandling
 386           // special caps for empty sub-paths like "M 0 0 L 0 0" and "M 1 2 Z".
 387           return Nothing();
 388         }
 389
 390         if (!ApproxEqual(pathStart, segStart)) {
 391           // If we were only interested in filling we could auto-close here
 392           // by calling helper.Edge like in the ClosePath case and detect some
 393           // unclosed paths as rectangles.
 394           //
 395           // For example:
 396           //  - "M 1 0 L 0 0 L 0 1 L 1 1 L 1 0" are both rects for filling and
 397           //  stroking.
 398           //  - "M 1 0 L 0 0 L 0 1 L 1 1" fills a rect but the stroke is shaped
 399           //  like a C.
 400           return Nothing();
 401         }
 402
 403         if (helper.idx != 0 && !helper.EndSubpath()) {
 404           return Nothing();
 405         }
 406
 407         if (cmd.move.by_to == StyleByTo::By) {
 408           to = segStart + to;
 409         }
 410
 411         pathStart = to;
 412         segStart = to;
 413         if (helper.idx == 0) {
 414           helper.min = to;
 415           helper.max = to;
 416         }
 417
 418         break;
 419       }
 420       case StylePathCommand::Tag::Close: {
 421         if (!helper.Edge(segStart, pathStart)) {
 422           return Nothing();
 423         }
 424         if (!helper.EndSubpath()) {
 425           return Nothing();
 426         }
 427         pathStart = segStart;
 428         break;
 429       }
 430       case StylePathCommand::Tag::Line: {
 431         Point to = cmd.line.point.ToGfxPoint();
 432         if (cmd.line.by_to == StyleByTo::By) {
 433           to = segStart + to;
 434         }
 435
 436         if (!helper.Edge(segStart, to)) {
 437           return Nothing();
 438         }
 439         segStart = to;
 440         break;
 441       }
 442       case StylePathCommand::Tag::HLine: {
 443         Point to = gfx::Point(cmd.h_line.x, segStart.y);
 444         if (cmd.h_line.by_to == StyleByTo::By) {
 445           to.x += segStart.x;
 446         }
 447
 448         if (!helper.Edge(segStart, to)) {
 449           return Nothing();
 450         }
 451         segStart = to;
 452         break;
 453       }
 454       case StylePathCommand::Tag::VLine: {
 455         Point to = gfx::Point(segStart.x, cmd.v_line.y);
 456         if (cmd.h_line.by_to == StyleByTo::By) {
 457           to.y += segStart.y;
 458         }
 459
 460         if (!helper.Edge(segStart, to)) {
 461           return Nothing();
 462         }
 463         segStart = to;
 464         break;
 465       }
 466       default:
 467         return Nothing();
 468     }
 469   }
 470
 471   if (!ApproxEqual(pathStart, segStart)) {
 472     // Same situation as with moveto regarding stroking not fullly closed path
 473     // even though the fill is a rectangle.
 474     return Nothing();
 475   }
 476
 477   if (!helper.EndSubpath()) {
 478     return Nothing();
 479   }
 480
 481   auto size = (helper.max - helper.min);
 482   return Some(Rect(helper.min, Size(size.x, size.y)));
 483 }
 484
 485 }  // namespace mozilla