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