layout/painting/DottedCornerFinder.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 "DottedCornerFinder.h"
   8
   9 #include <utility>
  10
  11 #include "BorderCache.h"
  12 #include "BorderConsts.h"
  13
  14 namespace mozilla {
  15
  16 using namespace gfx;
  17
  18 static inline Float Square(Float x) { return x * x; }
  19
  20 static Point PointRotateCCW90(const Point& aP) { return Point(aP.y, -aP.x); }
  21
  22 struct BestOverlap {
  23   Float overlap;
  24   size_t count;
  25
  26   BestOverlap() : overlap(0.0f), count(0) {}
  27
  28   BestOverlap(Float aOverlap, size_t aCount)
  29       : overlap(aOverlap), count(aCount) {}
  30 };
  31
  32 static const size_t DottedCornerCacheSize = 256;
  33 nsTHashMap<FourFloatsHashKey, BestOverlap> DottedCornerCache;
  34
  35 DottedCornerFinder::DottedCornerFinder(const Bezier& aOuterBezier,
  36                                        const Bezier& aInnerBezier,
  37                                        Corner aCorner, Float aBorderRadiusX,
  38                                        Float aBorderRadiusY, const Point& aC0,
  39                                        Float aR0, const Point& aCn, Float aRn,
  40                                        const Size& aCornerDim)
  41     : mOuterBezier(aOuterBezier),
  42       mInnerBezier(aInnerBezier),
  43       mCorner(aCorner),
  44       mNormalSign((aCorner == C_TL || aCorner == C_BR) ? -1.0f : 1.0f),
  45       mC0(aC0),
  46       mCn(aCn),
  47       mR0(aR0),
  48       mRn(aRn),
  49       mMaxR(std::max(aR0, aRn)),
  50       mCenterCurveOrigin(mC0.x, mCn.y),
  51       mCenterCurveR(0.0),
  52       mInnerCurveOrigin(mInnerBezier.mPoints[0].x, mInnerBezier.mPoints[3].y),
  53       mBestOverlap(0.0f),
  54       mHasZeroBorderWidth(false),
  55       mHasMore(true),
  56       mMaxCount(aCornerDim.width + aCornerDim.height),
  57       mType(OTHER),
  58       mI(0),
  59       mCount(0) {
  60   NS_ASSERTION(mR0 > 0.0f || mRn > 0.0f,
  61                "At least one side should have non-zero radius.");
  62
  63   mInnerWidth = fabs(mInnerBezier.mPoints[0].x - mInnerBezier.mPoints[3].x);
  64   mInnerHeight = fabs(mInnerBezier.mPoints[0].y - mInnerBezier.mPoints[3].y);
  65
  66   DetermineType(aBorderRadiusX, aBorderRadiusY);
  67
  68   Reset();
  69 }
  70
  71 static bool IsSingleCurve(Float aMinR, Float aMaxR, Float aMinBorderRadius,
  72                           Float aMaxBorderRadius) {
  73   return aMinR > 0.0f && aMinBorderRadius > aMaxR * 4.0f &&
  74          aMinBorderRadius / aMaxBorderRadius > 0.5f;
  75 }
  76
  77 void DottedCornerFinder::DetermineType(Float aBorderRadiusX,
  78                                        Float aBorderRadiusY) {
  79   // Calculate parameters for the center curve before swap.
  80   Float centerCurveWidth = fabs(mC0.x - mCn.x);
  81   Float centerCurveHeight = fabs(mC0.y - mCn.y);
  82   Point cornerPoint(mCn.x, mC0.y);
  83
  84   bool swapped = false;
  85   if (mR0 < mRn) {
  86     // Always draw from wider side to thinner side.
  87     std::swap(mC0, mCn);
  88     std::swap(mR0, mRn);
  89     std::swap(mInnerBezier.mPoints[0], mInnerBezier.mPoints[3]);
  90     std::swap(mInnerBezier.mPoints[1], mInnerBezier.mPoints[2]);
  91     std::swap(mOuterBezier.mPoints[0], mOuterBezier.mPoints[3]);
  92     std::swap(mOuterBezier.mPoints[1], mOuterBezier.mPoints[2]);
  93     mNormalSign = -mNormalSign;
  94     swapped = true;
  95   }
  96
  97   // See the comment at mType declaration for each condition.
  98
  99   Float minR = std::min(mR0, mRn);
 100   Float minBorderRadius = std::min(aBorderRadiusX, aBorderRadiusY);
 101   Float maxBorderRadius = std::max(aBorderRadiusX, aBorderRadiusY);
 102   if (IsSingleCurve(minR, mMaxR, minBorderRadius, maxBorderRadius)) {
 103     if (mR0 == mRn) {
 104       Float borderLength;
 105       if (minBorderRadius == maxBorderRadius) {
 106         mType = PERFECT;
 107         borderLength = M_PI * centerCurveHeight / 2.0f;
 108
 109         mCenterCurveR = centerCurveWidth;
 110       } else {
 111         mType = SINGLE_CURVE_AND_RADIUS;
 112         borderLength =
 113             GetQuarterEllipticArcLength(centerCurveWidth, centerCurveHeight);
 114       }
 115
 116       Float diameter = mR0 * 2.0f;
 117       size_t count = round(borderLength / diameter);
 118       if (count % 2) {
 119         count++;
 120       }
 121       mCount = count / 2 - 1;
 122       if (mCount > 0) {
 123         mBestOverlap = 1.0f - borderLength / (diameter * count);
 124       }
 125     } else {
 126       mType = SINGLE_CURVE;
 127     }
 128   }
 129
 130   if (mType == SINGLE_CURVE_AND_RADIUS || mType == SINGLE_CURVE) {
 131     Size cornerSize(centerCurveWidth, centerCurveHeight);
 132     GetBezierPointsForCorner(&mCenterBezier, mCorner, cornerPoint, cornerSize);
 133     if (swapped) {
 134       std::swap(mCenterBezier.mPoints[0], mCenterBezier.mPoints[3]);
 135       std::swap(mCenterBezier.mPoints[1], mCenterBezier.mPoints[2]);
 136     }
 137   }
 138
 139   if (minR == 0.0f) {
 140     mHasZeroBorderWidth = true;
 141   }
 142
 143   if ((mType == SINGLE_CURVE || mType == OTHER) && !mHasZeroBorderWidth) {
 144     FindBestOverlap(minR, minBorderRadius, maxBorderRadius);
 145   }
 146 }
 147
 148 bool DottedCornerFinder::HasMore(void) const {
 149   if (mHasZeroBorderWidth) {
 150     return mI < mMaxCount && mHasMore;
 151   }
 152
 153   return mI < mCount;
 154 }
 155
 156 DottedCornerFinder::Result DottedCornerFinder::Next(void) {
 157   mI++;
 158
 159   if (mType == PERFECT) {
 160     Float phi = mI * 4.0f * mR0 * (1 - mBestOverlap) / mCenterCurveR;
 161     if (mCorner == C_TL) {
 162       phi = -M_PI / 2.0f - phi;
 163     } else if (mCorner == C_TR) {
 164       phi = -M_PI / 2.0f + phi;
 165     } else if (mCorner == C_BR) {
 166       phi = M_PI / 2.0f - phi;
 167     } else {
 168       phi = M_PI / 2.0f + phi;
 169     }
 170
 171     Point C(mCenterCurveOrigin.x + mCenterCurveR * cos(phi),
 172             mCenterCurveOrigin.y + mCenterCurveR * sin(phi));
 173     return DottedCornerFinder::Result(C, mR0);
 174   }
 175
 176   // Find unfilled and filled circles.
 177   (void)FindNext(mBestOverlap);
 178   if (mHasMore) {
 179     (void)FindNext(mBestOverlap);
 180   }
 181
 182   return Result(mLastC, mLastR);
 183 }
 184
 185 void DottedCornerFinder::Reset(void) {
 186   mLastC = mC0;
 187   mLastR = mR0;
 188   mLastT = 0.0f;
 189   mHasMore = true;
 190 }
 191
 192 void DottedCornerFinder::FindPointAndRadius(Point& C, Float& r,
 193                                             const Point& innerTangent,
 194                                             const Point& normal, Float t) {
 195   // Find radius for the given tangent point on the inner curve such that the
 196   // circle is also tangent to the outer curve.
 197
 198   NS_ASSERTION(mType == OTHER, "Wrong mType");
 199
 200   Float lower = 0.0f;
 201   Float upper = mMaxR;
 202   const Float DIST_MARGIN = 0.1f;
 203   for (size_t i = 0; i < MAX_LOOP; i++) {
 204     r = (upper + lower) / 2.0f;
 205     C = innerTangent + normal * r;
 206
 207     Point Near = FindBezierNearestPoint(mOuterBezier, C, t);
 208     Float distSquare = (C - Near).LengthSquare();
 209
 210     if (distSquare > Square(r + DIST_MARGIN)) {
 211       lower = r;
 212     } else if (distSquare < Square(r - DIST_MARGIN)) {
 213       upper = r;
 214     } else {
 215       break;
 216     }
 217   }
 218 }
 219
 220 Float DottedCornerFinder::FindNext(Float overlap) {
 221   Float lower = mLastT;
 222   Float upper = 1.0f;
 223   Float t;
 224
 225   Point C = mLastC;
 226   Float r = 0.0f;
 227
 228   Float factor = (1.0f - overlap);
 229
 230   Float circlesDist = 0.0f;
 231   Float expectedDist = 0.0f;
 232
 233   const Float DIST_MARGIN = 0.1f;
 234   if (mType == SINGLE_CURVE_AND_RADIUS) {
 235     r = mR0;
 236
 237     expectedDist = (r + mLastR) * factor;
 238
 239     // Find C_i on the center curve.
 240     for (size_t i = 0; i < MAX_LOOP; i++) {
 241       t = (upper + lower) / 2.0f;
 242       C = GetBezierPoint(mCenterBezier, t);
 243
 244       // Check overlap along arc.
 245       circlesDist = GetBezierLength(mCenterBezier, mLastT, t);
 246       if (circlesDist < expectedDist - DIST_MARGIN) {
 247         lower = t;
 248       } else if (circlesDist > expectedDist + DIST_MARGIN) {
 249         upper = t;
 250       } else {
 251         break;
 252       }
 253     }
 254   } else if (mType == SINGLE_CURVE) {
 255     // Find C_i on the center curve, and calculate r_i.
 256     for (size_t i = 0; i < MAX_LOOP; i++) {
 257       t = (upper + lower) / 2.0f;
 258       C = GetBezierPoint(mCenterBezier, t);
 259
 260       Point Diff = GetBezierDifferential(mCenterBezier, t);
 261       Float DiffLength = Diff.Length();
 262       if (DiffLength == 0.0f) {
 263         // Basically this shouldn't happen.
 264         // If differential is 0, we cannot calculate tangent circle,
 265         // skip this point.
 266         t = (t + upper) / 2.0f;
 267         continue;
 268       }
 269
 270       Point normal = PointRotateCCW90(Diff / DiffLength) * (-mNormalSign);
 271       r = CalculateDistanceToEllipticArc(C, normal, mInnerCurveOrigin,
 272                                          mInnerWidth, mInnerHeight);
 273
 274       // Check overlap along arc.
 275       circlesDist = GetBezierLength(mCenterBezier, mLastT, t);
 276       expectedDist = (r + mLastR) * factor;
 277       if (circlesDist < expectedDist - DIST_MARGIN) {
 278         lower = t;
 279       } else if (circlesDist > expectedDist + DIST_MARGIN) {
 280         upper = t;
 281       } else {
 282         break;
 283       }
 284     }
 285   } else {
 286     Float distSquareMax = Square(mMaxR * 3.0f);
 287     Float circlesDistSquare = 0.0f;
 288
 289     // Find C_i and r_i.
 290     for (size_t i = 0; i < MAX_LOOP; i++) {
 291       t = (upper + lower) / 2.0f;
 292       Point innerTangent = GetBezierPoint(mInnerBezier, t);
 293       if ((innerTangent - mLastC).LengthSquare() > distSquareMax) {
 294         // It's clear that this tangent point is too far, skip it.
 295         upper = t;
 296         continue;
 297       }
 298
 299       Point Diff = GetBezierDifferential(mInnerBezier, t);
 300       Float DiffLength = Diff.Length();
 301       if (DiffLength == 0.0f) {
 302         // Basically this shouldn't happen.
 303         // If differential is 0, we cannot calculate tangent circle,
 304         // skip this point.
 305         t = (t + upper) / 2.0f;
 306         continue;
 307       }
 308
 309       Point normal = PointRotateCCW90(Diff / DiffLength) * mNormalSign;
 310       FindPointAndRadius(C, r, innerTangent, normal, t);
 311
 312       // Check overlap with direct distance.
 313       circlesDistSquare = (C - mLastC).LengthSquare();
 314       expectedDist = (r + mLastR) * factor;
 315       if (circlesDistSquare < Square(expectedDist - DIST_MARGIN)) {
 316         lower = t;
 317       } else if (circlesDistSquare > Square(expectedDist + DIST_MARGIN)) {
 318         upper = t;
 319       } else {
 320         break;
 321       }
 322     }
 323
 324     circlesDist = sqrt(circlesDistSquare);
 325   }
 326
 327   if (mHasZeroBorderWidth) {
 328     // When calculating circle around r=0, it may result in wrong radius that
 329     // is bigger than previous circle.  Detect it and stop calculating.
 330     const Float R_MARGIN = 0.1f;
 331     if (mLastR < R_MARGIN && r > mLastR) {
 332       mHasMore = false;
 333       mLastR = 0.0f;
 334       return 0.0f;
 335     }
 336   }
 337
 338   mLastT = t;
 339   mLastC = C;
 340   mLastR = r;
 341
 342   if (mHasZeroBorderWidth) {
 343     const Float T_MARGIN = 0.001f;
 344     if (mLastT >= 1.0f - T_MARGIN ||
 345         (mLastC - mCn).LengthSquare() < Square(mLastR)) {
 346       mHasMore = false;
 347     }
 348   }
 349
 350   if (expectedDist == 0.0f) {
 351     return 0.0f;
 352   }
 353
 354   return 1.0f - circlesDist * factor / expectedDist;
 355 }
 356
 357 void DottedCornerFinder::FindBestOverlap(Float aMinR, Float aMinBorderRadius,
 358                                          Float aMaxBorderRadius) {
 359   // If overlap is not calculateable, find it with binary search,
 360   // such that there exists i that C_i == C_n with the given overlap.
 361
 362   FourFloats key(aMinR, mMaxR, aMinBorderRadius, aMaxBorderRadius);
 363   BestOverlap best;
 364   if (DottedCornerCache.Get(key, &best)) {
 365     mCount = best.count;
 366     mBestOverlap = best.overlap;
 367     return;
 368   }
 369
 370   Float lower = 0.0f;
 371   Float upper = 0.5f;
 372   // Start from lower bound to find the minimum number of circles.
 373   Float overlap = 0.0f;
 374   mBestOverlap = overlap;
 375   size_t targetCount = 0;
 376
 377   const Float OVERLAP_MARGIN = 0.1f;
 378   for (size_t j = 0; j < MAX_LOOP; j++) {
 379     Reset();
 380
 381     size_t count;
 382     Float actualOverlap;
 383     if (!GetCountAndLastOverlap(overlap, &count, &actualOverlap)) {
 384       if (j == 0) {
 385         mCount = mMaxCount;
 386         break;
 387       }
 388     }
 389
 390     if (j == 0) {
 391       if (count < 3 || (count == 3 && actualOverlap > 0.5f)) {
 392         // |count == 3 && actualOverlap > 0.5f| means there could be
 393         // a circle but it is too near from both ends.
 394         //
 395         // if actualOverlap == 0.0
 396         //               1       2       3
 397         //   +-------+-------+-------+-------+
 398         //   | ##### | ***** | ##### | ##### |
 399         //   |#######|*******|#######|#######|
 400         //   |###+###|***+***|###+###|###+###|
 401         //   |# C_0 #|* C_1 *|# C_2 #|# C_n #|
 402         //   | ##### | ***** | ##### | ##### |
 403         //   +-------+-------+-------+-------+
 404         //                   |
 405         //                   V
 406         //   +-------+---+-------+---+-------+
 407         //   | ##### |   | ##### |   | ##### |
 408         //   |#######|   |#######|   |#######|
 409         //   |###+###|   |###+###|   |###+###| Find the best overlap to place
 410         //   |# C_0 #|   |# C_1 #|   |# C_n #| C_1 at the middle of them
 411         //   | ##### |   | ##### |   | ##### |
 412         //   +-------+---+-------+---|-------+
 413         //
 414         // if actualOverlap == 0.5
 415         //               1       2     3
 416         //   +-------+-------+-------+---+
 417         //   | ##### | ***** | ##### |## |
 418         //   |#######|*******|##### C_n #|
 419         //   |###+###|***+***|###+###+###|
 420         //   |# C_0 #|* C_1 *|# C_2 #|###|
 421         //   | ##### | ***** | ##### |## |
 422         //   +-------+-------+-------+---+
 423         //                 |
 424         //                 V
 425         //   +-------+-+-------+-+-------+
 426         //   | ##### | | ##### | | ##### |
 427         //   |#######| |#######| |#######|
 428         //   |###+###| |###+###| |###+###| Even if we place C_1 at the middle
 429         //   |# C_0 #| |# C_1 #| |# C_n #| of them, it's too near from them
 430         //   | ##### | | ##### | | ##### |
 431         //   +-------+-+-------+-|-------+
 432         //                 |
 433         //                 V
 434         //   +-------+-----------+-------+
 435         //   | ##### |           | ##### |
 436         //   |#######|           |#######|
 437         //   |###+###|           |###+###| Do not draw any circle
 438         //   |# C_0 #|           |# C_n #|
 439         //   | ##### |           | ##### |
 440         //   +-------+-----------+-------+
 441         mCount = 0;
 442         break;
 443       }
 444
 445       // targetCount should be 2n, as we're searching C_1 to C_n.
 446       //
 447       //   targetCount = 4
 448       //   mCount = 1
 449       //               1       2       3       4
 450       //   +-------+-------+-------+-------+-------+
 451       //   | ##### | ***** | ##### | ***** | ##### |
 452       //   |#######|*******|#######|*******|#######|
 453       //   |###+###|***+***|###+###|***+***|###+###|
 454       //   |# C_0 #|* C_1 *|# C_2 #|* C_3 *|# C_n #|
 455       //   | ##### | ***** | ##### | ***** | ##### |
 456       //   +-------+-------+-------+-------+-------+
 457       //                       1
 458       //
 459       //   targetCount = 6
 460       //   mCount = 2
 461       //               1       2       3       4       5       6
 462       //   +-------+-------+-------+-------+-------+-------+-------+
 463       //   | ##### | ***** | ##### | ***** | ##### | ***** | ##### |
 464       //   |#######|*******|#######|*******|#######|*******|#######|
 465       //   |###+###|***+***|###+###|***+***|###+###|***+***|###+###|
 466       //   |# C_0 #|* C_1 *|# C_2 #|* C_3 *|# C_4 #|* C_5 *|# C_n #|
 467       //   | ##### | ***** | ##### | ***** | ##### | ***** | ##### |
 468       //   +-------+-------+-------+-------+-------+-------+-------+
 469       //                       1               2
 470       if (count % 2) {
 471         targetCount = count + 1;
 472       } else {
 473         targetCount = count;
 474       }
 475
 476       mCount = targetCount / 2 - 1;
 477     }
 478
 479     if (count == targetCount) {
 480       mBestOverlap = overlap;
 481
 482       if (fabs(actualOverlap - overlap) < OVERLAP_MARGIN) {
 483         break;
 484       }
 485
 486       // We started from upper bound, no need to update range when j == 0.
 487       if (j > 0) {
 488         if (actualOverlap > overlap) {
 489           lower = overlap;
 490         } else {
 491           upper = overlap;
 492         }
 493       }
 494     } else {
 495       // |j == 0 && count != targetCount| means that |targetCount = count + 1|,
 496       // and we started from upper bound, no need to update range when j == 0.
 497       if (j > 0) {
 498         if (count > targetCount) {
 499           upper = overlap;
 500         } else {
 501           lower = overlap;
 502         }
 503       }
 504     }
 505
 506     overlap = (upper + lower) / 2.0f;
 507   }
 508
 509   if (DottedCornerCache.Count() > DottedCornerCacheSize) {
 510     DottedCornerCache.Clear();
 511   }
 512   DottedCornerCache.InsertOrUpdate(key, BestOverlap(mBestOverlap, mCount));
 513 }
 514
 515 bool DottedCornerFinder::GetCountAndLastOverlap(Float aOverlap, size_t* aCount,
 516                                                 Float* aActualOverlap) {
 517   // Return the number of circles and the last circles' overlap for the
 518   // given overlap.
 519
 520   Reset();
 521
 522   const Float T_MARGIN = 0.001f;
 523   const Float DIST_MARGIN = 0.1f;
 524   const Float DIST_MARGIN_SQUARE = Square(DIST_MARGIN);
 525   for (size_t i = 0; i < mMaxCount; i++) {
 526     Float actualOverlap = FindNext(aOverlap);
 527     if (mLastT >= 1.0f - T_MARGIN ||
 528         (mLastC - mCn).LengthSquare() < DIST_MARGIN_SQUARE) {
 529       *aCount = i + 1;
 530       *aActualOverlap = actualOverlap;
 531       return true;
 532     }
 533   }
 534
 535   return false;
 536 }
 537
 538 }  // namespace mozilla