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