tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

SVGPathSegUtils.cpp (15148B)

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