layout/painting/DashedCornerFinder.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 "DashedCornerFinder.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 struct BestDashLength {
  20   typedef mozilla::gfx::Float Float;
  21
  22   Float dashLength;
  23   size_t count;
  24
  25   BestDashLength() : dashLength(0.0f), count(0) {}
  26
  27   BestDashLength(Float aDashLength, size_t aCount)
  28       : dashLength(aDashLength), count(aCount) {}
  29 };
  30
  31 static const size_t DashedCornerCacheSize = 256;
  32 nsTHashMap<FourFloatsHashKey, BestDashLength> DashedCornerCache;
  33
  34 DashedCornerFinder::DashedCornerFinder(const Bezier& aOuterBezier,
  35                                        const Bezier& aInnerBezier,
  36                                        Float aBorderWidthH, Float aBorderWidthV,
  37                                        const Size& aCornerDim)
  38     : mOuterBezier(aOuterBezier),
  39       mInnerBezier(aInnerBezier),
  40       mLastOuterP(aOuterBezier.mPoints[0]),
  41       mLastInnerP(aInnerBezier.mPoints[0]),
  42       mLastOuterT(0.0f),
  43       mLastInnerT(0.0f),
  44       mBestDashLength(DOT_LENGTH * DASH_LENGTH),
  45       mHasZeroBorderWidth(false),
  46       mHasMore(true),
  47       mMaxCount(aCornerDim.width + aCornerDim.height),
  48       mType(OTHER),
  49       mI(0),
  50       mCount(0) {
  51   NS_ASSERTION(aBorderWidthH > 0.0f || aBorderWidthV > 0.0f,
  52                "At least one side should have non-zero width.");
  53
  54   DetermineType(aBorderWidthH, aBorderWidthV);
  55
  56   Reset();
  57 }
  58
  59 void DashedCornerFinder::DetermineType(Float aBorderWidthH,
  60                                        Float aBorderWidthV) {
  61   if (aBorderWidthH < aBorderWidthV) {
  62     // Always draw from wider side to thinner side.
  63     std::swap(mInnerBezier.mPoints[0], mInnerBezier.mPoints[3]);
  64     std::swap(mInnerBezier.mPoints[1], mInnerBezier.mPoints[2]);
  65     std::swap(mOuterBezier.mPoints[0], mOuterBezier.mPoints[3]);
  66     std::swap(mOuterBezier.mPoints[1], mOuterBezier.mPoints[2]);
  67     mLastOuterP = mOuterBezier.mPoints[0];
  68     mLastInnerP = mInnerBezier.mPoints[0];
  69   }
  70
  71   // See the comment at mType declaration for each condition.
  72
  73   Float borderRadiusA =
  74       fabs(mOuterBezier.mPoints[0].x - mOuterBezier.mPoints[3].x);
  75   Float borderRadiusB =
  76       fabs(mOuterBezier.mPoints[0].y - mOuterBezier.mPoints[3].y);
  77   if (aBorderWidthH == aBorderWidthV && borderRadiusA == borderRadiusB &&
  78       borderRadiusA > aBorderWidthH * 2.0f) {
  79     Float curveHeight = borderRadiusA - aBorderWidthH / 2.0;
  80
  81     mType = PERFECT;
  82     Float borderLength = M_PI * curveHeight / 2.0f;
  83
  84     Float dashWidth = aBorderWidthH * DOT_LENGTH * DASH_LENGTH;
  85     size_t count = ceil(borderLength / dashWidth);
  86     if (count % 2) {
  87       count++;
  88     }
  89     mCount = count / 2 + 1;
  90     mBestDashLength = borderLength / (aBorderWidthH * count);
  91   }
  92
  93   Float minBorderWidth = std::min(aBorderWidthH, aBorderWidthV);
  94   if (minBorderWidth == 0.0f) {
  95     mHasZeroBorderWidth = true;
  96   }
  97
  98   if (mType == OTHER && !mHasZeroBorderWidth) {
  99     Float minBorderRadius = std::min(borderRadiusA, borderRadiusB);
 100     Float maxBorderRadius = std::max(borderRadiusA, borderRadiusB);
 101     Float maxBorderWidth = std::max(aBorderWidthH, aBorderWidthV);
 102
 103     FindBestDashLength(minBorderWidth, maxBorderWidth, minBorderRadius,
 104                        maxBorderRadius);
 105   }
 106 }
 107
 108 bool DashedCornerFinder::HasMore(void) const {
 109   if (mHasZeroBorderWidth) {
 110     return mI < mMaxCount && mHasMore;
 111   }
 112
 113   return mI < mCount;
 114 }
 115
 116 DashedCornerFinder::Result DashedCornerFinder::Next(void) {
 117   Float lastOuterT, lastInnerT, outerT, innerT;
 118
 119   if (mI == 0) {
 120     lastOuterT = 0.0f;
 121     lastInnerT = 0.0f;
 122   } else {
 123     if (mType == PERFECT) {
 124       lastOuterT = lastInnerT = (mI * 2.0f - 0.5f) / ((mCount - 1) * 2.0f);
 125     } else {
 126       Float last2OuterT = mLastOuterT;
 127       Float last2InnerT = mLastInnerT;
 128
 129       (void)FindNext(mBestDashLength);
 130
 131       //
 132       //          mLastOuterT   lastOuterT
 133       //                    |   |
 134       //                    v   v
 135       //            +---+---+---+---+ <- last2OuterT
 136       //            |   |###|###|   |
 137       //            |   |###|###|   |
 138       //            |   |###|###|   |
 139       //            +---+---+---+---+ <- last2InnerT
 140       //                    ^   ^
 141       //                    |   |
 142       //          mLastInnerT   lastInnerT
 143       lastOuterT = (mLastOuterT + last2OuterT) / 2.0f;
 144       lastInnerT = (mLastInnerT + last2InnerT) / 2.0f;
 145     }
 146   }
 147
 148   if ((!mHasZeroBorderWidth && mI == mCount - 1) ||
 149       (mHasZeroBorderWidth && !mHasMore)) {
 150     outerT = 1.0f;
 151     innerT = 1.0f;
 152   } else {
 153     if (mType == PERFECT) {
 154       outerT = innerT = (mI * 2.0f + 0.5f) / ((mCount - 1) * 2.0f);
 155     } else {
 156       Float last2OuterT = mLastOuterT;
 157       Float last2InnerT = mLastInnerT;
 158
 159       (void)FindNext(mBestDashLength);
 160
 161       //
 162       //               outerT   last2OuterT
 163       //                    |   |
 164       //                    v   v
 165       // mLastOuterT -> +---+---+---+---+
 166       //                |   |###|###|   |
 167       //                |   |###|###|   |
 168       //                |   |###|###|   |
 169       // mLastInnerT -> +---+---+---+---+
 170       //                    ^   ^
 171       //                    |   |
 172       //               innerT   last2InnerT
 173       outerT = (mLastOuterT + last2OuterT) / 2.0f;
 174       innerT = (mLastInnerT + last2InnerT) / 2.0f;
 175     }
 176   }
 177
 178   mI++;
 179
 180   Bezier outerSectionBezier;
 181   Bezier innerSectionBezier;
 182   GetSubBezier(&outerSectionBezier, mOuterBezier, lastOuterT, outerT);
 183   GetSubBezier(&innerSectionBezier, mInnerBezier, lastInnerT, innerT);
 184   return DashedCornerFinder::Result(outerSectionBezier, innerSectionBezier);
 185 }
 186
 187 void DashedCornerFinder::Reset(void) {
 188   mLastOuterP = mOuterBezier.mPoints[0];
 189   mLastInnerP = mInnerBezier.mPoints[0];
 190   mLastOuterT = 0.0f;
 191   mLastInnerT = 0.0f;
 192   mHasMore = true;
 193 }
 194
 195 Float DashedCornerFinder::FindNext(Float dashLength) {
 196   Float upper = 1.0f;
 197   Float lower = mLastOuterT;
 198
 199   Point OuterP, InnerP;
 200   // Start from upper bound to check if this is the last segment.
 201   Float outerT = upper;
 202   Float innerT;
 203   Float W = 0.0f;
 204   Float L = 0.0f;
 205
 206   const Float LENGTH_MARGIN = 0.1f;
 207   for (size_t i = 0; i < MAX_LOOP; i++) {
 208     OuterP = GetBezierPoint(mOuterBezier, outerT);
 209     InnerP = FindBezierNearestPoint(mInnerBezier, OuterP, outerT, &innerT);
 210
 211     // Calculate approximate dash length.
 212     //
 213     //   W = (W1 + W2) / 2
 214     //   L = (OuterL + InnerL) / 2
 215     //   dashLength = L / W
 216     //
 217     //              ____----+----____
 218     // OuterP ___---        |         ---___    mLastOuterP
 219     //    +---              |               ---+
 220     //    |                  |                 |
 221     //    |                  |                 |
 222     //     |               W |              W1 |
 223     //     |                  |                |
 224     //  W2 |                  |                |
 225     //     |                  |    ______------+
 226     //     |              ____+----             mLastInnerP
 227     //      |       ___---
 228     //      |  __---
 229     //      +--
 230     //    InnerP
 231     //                     OuterL
 232     //              ____---------____
 233     // OuterP ___---                  ---___    mLastOuterP
 234     //    +---                              ---+
 235     //    |                  L                 |
 236     //    |            ___----------______     |
 237     //     |      __---                   -----+
 238     //     |  __--                             |
 239     //     +--                                 |
 240     //     |                InnerL ______------+
 241     //     |              ____-----             mLastInnerP
 242     //      |       ___---
 243     //      |  __---
 244     //      +--
 245     //    InnerP
 246     Float W1 = (mLastOuterP - mLastInnerP).Length();
 247     Float W2 = (OuterP - InnerP).Length();
 248     Float OuterL = GetBezierLength(mOuterBezier, mLastOuterT, outerT);
 249     Float InnerL = GetBezierLength(mInnerBezier, mLastInnerT, innerT);
 250     W = (W1 + W2) / 2.0f;
 251     L = (OuterL + InnerL) / 2.0f;
 252     if (L > W * dashLength + LENGTH_MARGIN) {
 253       if (i > 0) {
 254         upper = outerT;
 255       }
 256     } else if (L < W * dashLength - LENGTH_MARGIN) {
 257       if (i == 0) {
 258         // This is the last segment with shorter dashLength.
 259         mHasMore = false;
 260         break;
 261       }
 262       lower = outerT;
 263     } else {
 264       break;
 265     }
 266
 267     outerT = (upper + lower) / 2.0f;
 268   }
 269
 270   mLastOuterP = OuterP;
 271   mLastInnerP = InnerP;
 272   mLastOuterT = outerT;
 273   mLastInnerT = innerT;
 274
 275   if (W == 0.0f) {
 276     return 1.0f;
 277   }
 278
 279   return L / W;
 280 }
 281
 282 void DashedCornerFinder::FindBestDashLength(Float aMinBorderWidth,
 283                                             Float aMaxBorderWidth,
 284                                             Float aMinBorderRadius,
 285                                             Float aMaxBorderRadius) {
 286   // If dashLength is not calculateable, find it with binary search,
 287   // such that there exists i that OuterP_i == OuterP_n and
 288   // InnerP_i == InnerP_n with given dashLength.
 289
 290   FourFloats key(aMinBorderWidth, aMaxBorderWidth, aMinBorderRadius,
 291                  aMaxBorderRadius);
 292   BestDashLength best;
 293   if (DashedCornerCache.Get(key, &best)) {
 294     mCount = best.count;
 295     mBestDashLength = best.dashLength;
 296     return;
 297   }
 298
 299   Float lower = 1.0f;
 300   Float upper = DOT_LENGTH * DASH_LENGTH;
 301   Float dashLength = upper;
 302   size_t targetCount = 0;
 303
 304   const Float LENGTH_MARGIN = 0.1f;
 305   for (size_t j = 0; j < MAX_LOOP; j++) {
 306     size_t count;
 307     Float actualDashLength;
 308     if (!GetCountAndLastDashLength(dashLength, &count, &actualDashLength)) {
 309       if (j == 0) {
 310         mCount = mMaxCount;
 311         break;
 312       }
 313     }
 314
 315     if (j == 0) {
 316       if (count == 1) {
 317         // If only 1 segment fits, fill entire region
 318         //
 319         //   count = 1
 320         //   mCount = 1
 321         //   |   1   |
 322         //   +---+---+
 323         //   |###|###|
 324         //   |###|###|
 325         //   |###|###|
 326         //   +---+---+
 327         //       1
 328         mCount = 1;
 329         break;
 330       }
 331
 332       // targetCount should be 2n.
 333       //
 334       //   targetCount = 2
 335       //   mCount = 2
 336       //   |   1   |   2   |
 337       //   +---+---+---+---+
 338       //   |###|   |   |###|
 339       //   |###|   |   |###|
 340       //   |###|   |   |###|
 341       //   +---+---+---+---+
 342       //     1           2
 343       //
 344       //   targetCount = 6
 345       //   mCount = 4
 346       //   |   1   |   2   |   3   |   4   |   5   |   6   |
 347       //   +---+---+---+---+---+---+---+---+---+---+---+---+
 348       //   |###|   |   |###|###|   |   |###|###|   |   |###|
 349       //   |###|   |   |###|###|   |   |###|###|   |   |###|
 350       //   |###|   |   |###|###|   |   |###|###|   |   |###|
 351       //   +---+---+---+---+---+---+---+---+---+---+---+---+
 352       //     1             2               3             4
 353       if (count % 2) {
 354         targetCount = count + 1;
 355       } else {
 356         targetCount = count;
 357       }
 358
 359       mCount = targetCount / 2 + 1;
 360     }
 361
 362     if (count == targetCount) {
 363       mBestDashLength = dashLength;
 364
 365       // actualDashLength won't be greater than dashLength.
 366       if (actualDashLength > dashLength - LENGTH_MARGIN) {
 367         break;
 368       }
 369
 370       // We started from upper bound, no need to update range when j == 0.
 371       if (j > 0) {
 372         upper = dashLength;
 373       }
 374     } else {
 375       // |j == 0 && count != targetCount| means that |targetCount = count + 1|,
 376       // and we started from upper bound, no need to update range when j == 0.
 377       if (j > 0) {
 378         if (count > targetCount) {
 379           lower = dashLength;
 380         } else {
 381           upper = dashLength;
 382         }
 383       }
 384     }
 385
 386     dashLength = (upper + lower) / 2.0f;
 387   }
 388
 389   if (DashedCornerCache.Count() > DashedCornerCacheSize) {
 390     DashedCornerCache.Clear();
 391   }
 392   DashedCornerCache.InsertOrUpdate(key,
 393                                    BestDashLength(mBestDashLength, mCount));
 394 }
 395
 396 bool DashedCornerFinder::GetCountAndLastDashLength(Float aDashLength,
 397                                                    size_t* aCount,
 398                                                    Float* aActualDashLength) {
 399   // Return the number of segments and the last segment's dashLength for
 400   // the given dashLength.
 401
 402   Reset();
 403
 404   for (size_t i = 0; i < mMaxCount; i++) {
 405     Float actualDashLength = FindNext(aDashLength);
 406     if (mLastOuterT >= 1.0f) {
 407       *aCount = i + 1;
 408       *aActualDashLength = actualDashLength;
 409       return true;
 410     }
 411   }
 412
 413   return false;
 414 }
 415
 416 }  // namespace mozilla