tor-browser

DottedCornerFinder.cpp (16963B)

---

/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
/* vim: set ts=8 sts=2 et sw=2 tw=80: */
/* This Source Code Form is subject to the terms of the Mozilla Public
* License, v. 2.0. If a copy of the MPL was not distributed with this
* file, You can obtain one at http://mozilla.org/MPL/2.0/. */

#include "DottedCornerFinder.h"

#include <utility>

#include "BorderCache.h"
#include "BorderConsts.h"
#include "nsTHashMap.h"

namespace mozilla {

using namespace gfx;

static inline Float Square(Float x) { return x * x; }

static Point PointRotateCCW90(const Point& aP) { return Point(aP.y, -aP.x); }

struct BestOverlap {
 Float overlap;
 size_t count;

 BestOverlap() : overlap(0.0f), count(0) {}

 BestOverlap(Float aOverlap, size_t aCount)
     : overlap(aOverlap), count(aCount) {}
};

static const size_t DottedCornerCacheSize = 256;
MOZ_RUNINIT nsTHashMap<FourFloatsHashKey, BestOverlap> DottedCornerCache;

DottedCornerFinder::DottedCornerFinder(const Bezier& aOuterBezier,
                                      const Bezier& aInnerBezier,
                                      Corner aCorner, Float aBorderRadiusX,
                                      Float aBorderRadiusY, const Point& aC0,
                                      Float aR0, const Point& aCn, Float aRn,
                                      const Size& aCornerDim)
   : mOuterBezier(aOuterBezier),
     mInnerBezier(aInnerBezier),
     mCorner(aCorner),
     mNormalSign((aCorner == C_TL || aCorner == C_BR) ? -1.0f : 1.0f),
     mC0(aC0),
     mCn(aCn),
     mR0(aR0),
     mRn(aRn),
     mMaxR(std::max(aR0, aRn)),
     mCenterCurveOrigin(mC0.x, mCn.y),
     mCenterCurveR(0.0),
     mInnerCurveOrigin(mInnerBezier.mPoints[0].x, mInnerBezier.mPoints[3].y),
     mBestOverlap(0.0f),
     mHasZeroBorderWidth(false),
     mHasMore(true),
     mMaxCount(aCornerDim.width + aCornerDim.height),
     mType(OTHER),
     mI(0),
     mCount(0) {
 NS_ASSERTION(mR0 > 0.0f || mRn > 0.0f,
              "At least one side should have non-zero radius.");

 mInnerWidth = fabs(mInnerBezier.mPoints[0].x - mInnerBezier.mPoints[3].x);
 mInnerHeight = fabs(mInnerBezier.mPoints[0].y - mInnerBezier.mPoints[3].y);

 DetermineType(aBorderRadiusX, aBorderRadiusY);

 Reset();
}

static bool IsSingleCurve(Float aMinR, Float aMaxR, Float aMinBorderRadius,
                         Float aMaxBorderRadius) {
 return aMinR > 0.0f && aMinBorderRadius > aMaxR * 4.0f &&
        aMinBorderRadius / aMaxBorderRadius > 0.5f;
}

void DottedCornerFinder::DetermineType(Float aBorderRadiusX,
                                      Float aBorderRadiusY) {
 // Calculate parameters for the center curve before swap.
 Float centerCurveWidth = fabs(mC0.x - mCn.x);
 Float centerCurveHeight = fabs(mC0.y - mCn.y);
 Point cornerPoint(mCn.x, mC0.y);

 bool swapped = false;
 if (mR0 < mRn) {
   // Always draw from wider side to thinner side.
   std::swap(mC0, mCn);
   std::swap(mR0, mRn);
   std::swap(mInnerBezier.mPoints[0], mInnerBezier.mPoints[3]);
   std::swap(mInnerBezier.mPoints[1], mInnerBezier.mPoints[2]);
   std::swap(mOuterBezier.mPoints[0], mOuterBezier.mPoints[3]);
   std::swap(mOuterBezier.mPoints[1], mOuterBezier.mPoints[2]);
   mNormalSign = -mNormalSign;
   swapped = true;
 }

 // See the comment at mType declaration for each condition.

 Float minR = std::min(mR0, mRn);
 Float minBorderRadius = std::min(aBorderRadiusX, aBorderRadiusY);
 Float maxBorderRadius = std::max(aBorderRadiusX, aBorderRadiusY);
 if (IsSingleCurve(minR, mMaxR, minBorderRadius, maxBorderRadius)) {
   if (mR0 == mRn) {
     Float borderLength;
     if (minBorderRadius == maxBorderRadius) {
       mType = PERFECT;
       borderLength = M_PI * centerCurveHeight / 2.0f;

       mCenterCurveR = centerCurveWidth;
     } else {
       mType = SINGLE_CURVE_AND_RADIUS;
       borderLength =
           GetQuarterEllipticArcLength(centerCurveWidth, centerCurveHeight);
     }

     Float diameter = mR0 * 2.0f;
     size_t count = round(borderLength / diameter);
     if (count % 2) {
       count++;
     }
     mCount = count / 2 - 1;
     if (mCount > 0) {
       mBestOverlap = 1.0f - borderLength / (diameter * count);
     }
   } else {
     mType = SINGLE_CURVE;
   }
 }

 if (mType == SINGLE_CURVE_AND_RADIUS || mType == SINGLE_CURVE) {
   Size cornerSize(centerCurveWidth, centerCurveHeight);
   GetBezierPointsForCorner(&mCenterBezier, mCorner, cornerPoint, cornerSize);
   if (swapped) {
     std::swap(mCenterBezier.mPoints[0], mCenterBezier.mPoints[3]);
     std::swap(mCenterBezier.mPoints[1], mCenterBezier.mPoints[2]);
   }
 }

 if (minR == 0.0f) {
   mHasZeroBorderWidth = true;
 }

 if ((mType == SINGLE_CURVE || mType == OTHER) && !mHasZeroBorderWidth) {
   FindBestOverlap(minR, minBorderRadius, maxBorderRadius);
 }
}

bool DottedCornerFinder::HasMore(void) const {
 if (mHasZeroBorderWidth) {
   return mI < mMaxCount && mHasMore;
 }

 return mI < mCount;
}

DottedCornerFinder::Result DottedCornerFinder::Next(void) {
 mI++;

 if (mType == PERFECT) {
   Float phi = mI * 4.0f * mR0 * (1 - mBestOverlap) / mCenterCurveR;
   if (mCorner == C_TL) {
     phi = -M_PI / 2.0f - phi;
   } else if (mCorner == C_TR) {
     phi = -M_PI / 2.0f + phi;
   } else if (mCorner == C_BR) {
     phi = M_PI / 2.0f - phi;
   } else {
     phi = M_PI / 2.0f + phi;
   }

   Point C(mCenterCurveOrigin.x + mCenterCurveR * cos(phi),
           mCenterCurveOrigin.y + mCenterCurveR * sin(phi));
   return DottedCornerFinder::Result(C, mR0);
 }

 // Find unfilled and filled circles.
 (void)FindNext(mBestOverlap);
 if (mHasMore) {
   (void)FindNext(mBestOverlap);
 }

 return Result(mLastC, mLastR);
}

void DottedCornerFinder::Reset(void) {
 mLastC = mC0;
 mLastR = mR0;
 mLastT = 0.0f;
 mHasMore = true;
}

void DottedCornerFinder::FindPointAndRadius(Point& C, Float& r,
                                           const Point& innerTangent,
                                           const Point& normal, Float t) {
 // Find radius for the given tangent point on the inner curve such that the
 // circle is also tangent to the outer curve.

 NS_ASSERTION(mType == OTHER, "Wrong mType");

 Float lower = 0.0f;
 Float upper = mMaxR;
 const Float DIST_MARGIN = 0.1f;
 for (size_t i = 0; i < MAX_LOOP; i++) {
   r = (upper + lower) / 2.0f;
   C = innerTangent + normal * r;

   Point Near = FindBezierNearestPoint(mOuterBezier, C, t);
   Float distSquare = (C - Near).LengthSquare();

   if (distSquare > Square(r + DIST_MARGIN)) {
     lower = r;
   } else if (distSquare < Square(r - DIST_MARGIN)) {
     upper = r;
   } else {
     break;
   }
 }
}

Float DottedCornerFinder::FindNext(Float overlap) {
 Float lower = mLastT;
 Float upper = 1.0f;
 Float t;

 Point C = mLastC;
 Float r = 0.0f;

 Float factor = (1.0f - overlap);

 Float circlesDist = 0.0f;
 Float expectedDist = 0.0f;

 const Float DIST_MARGIN = 0.1f;
 if (mType == SINGLE_CURVE_AND_RADIUS) {
   r = mR0;

   expectedDist = (r + mLastR) * factor;

   // Find C_i on the center curve.
   for (size_t i = 0; i < MAX_LOOP; i++) {
     t = (upper + lower) / 2.0f;
     C = GetBezierPoint(mCenterBezier, t);

     // Check overlap along arc.
     circlesDist = GetBezierLength(mCenterBezier, mLastT, t);
     if (circlesDist < expectedDist - DIST_MARGIN) {
       lower = t;
     } else if (circlesDist > expectedDist + DIST_MARGIN) {
       upper = t;
     } else {
       break;
     }
   }
 } else if (mType == SINGLE_CURVE) {
   // Find C_i on the center curve, and calculate r_i.
   for (size_t i = 0; i < MAX_LOOP; i++) {
     t = (upper + lower) / 2.0f;
     C = GetBezierPoint(mCenterBezier, t);

     Point Diff = GetBezierDifferential(mCenterBezier, t);
     Float DiffLength = Diff.Length();
     if (DiffLength == 0.0f) {
       // Basically this shouldn't happen.
       // If differential is 0, we cannot calculate tangent circle,
       // skip this point.
       t = (t + upper) / 2.0f;
       continue;
     }

     Point normal = PointRotateCCW90(Diff / DiffLength) * (-mNormalSign);
     r = CalculateDistanceToEllipticArc(C, normal, mInnerCurveOrigin,
                                        mInnerWidth, mInnerHeight);

     // Check overlap along arc.
     circlesDist = GetBezierLength(mCenterBezier, mLastT, t);
     expectedDist = (r + mLastR) * factor;
     if (circlesDist < expectedDist - DIST_MARGIN) {
       lower = t;
     } else if (circlesDist > expectedDist + DIST_MARGIN) {
       upper = t;
     } else {
       break;
     }
   }
 } else {
   Float distSquareMax = Square(mMaxR * 3.0f);
   Float circlesDistSquare = 0.0f;

   // Find C_i and r_i.
   for (size_t i = 0; i < MAX_LOOP; i++) {
     t = (upper + lower) / 2.0f;
     Point innerTangent = GetBezierPoint(mInnerBezier, t);
     if ((innerTangent - mLastC).LengthSquare() > distSquareMax) {
       // It's clear that this tangent point is too far, skip it.
       upper = t;
       continue;
     }

     Point Diff = GetBezierDifferential(mInnerBezier, t);
     Float DiffLength = Diff.Length();
     if (DiffLength == 0.0f) {
       // Basically this shouldn't happen.
       // If differential is 0, we cannot calculate tangent circle,
       // skip this point.
       t = (t + upper) / 2.0f;
       continue;
     }

     Point normal = PointRotateCCW90(Diff / DiffLength) * mNormalSign;
     FindPointAndRadius(C, r, innerTangent, normal, t);

     // Check overlap with direct distance.
     circlesDistSquare = (C - mLastC).LengthSquare();
     expectedDist = (r + mLastR) * factor;
     if (circlesDistSquare < Square(expectedDist - DIST_MARGIN)) {
       lower = t;
     } else if (circlesDistSquare > Square(expectedDist + DIST_MARGIN)) {
       upper = t;
     } else {
       break;
     }
   }

   circlesDist = sqrt(circlesDistSquare);
 }

 if (mHasZeroBorderWidth) {
   // When calculating circle around r=0, it may result in wrong radius that
   // is bigger than previous circle.  Detect it and stop calculating.
   const Float R_MARGIN = 0.1f;
   if (mLastR < R_MARGIN && r > mLastR) {
     mHasMore = false;
     mLastR = 0.0f;
     return 0.0f;
   }
 }

 mLastT = t;
 mLastC = C;
 mLastR = r;

 if (mHasZeroBorderWidth) {
   const Float T_MARGIN = 0.001f;
   if (mLastT >= 1.0f - T_MARGIN ||
       (mLastC - mCn).LengthSquare() < Square(mLastR)) {
     mHasMore = false;
   }
 }

 if (expectedDist == 0.0f) {
   return 0.0f;
 }

 return 1.0f - circlesDist * factor / expectedDist;
}

void DottedCornerFinder::FindBestOverlap(Float aMinR, Float aMinBorderRadius,
                                        Float aMaxBorderRadius) {
 // If overlap is not calculateable, find it with binary search,
 // such that there exists i that C_i == C_n with the given overlap.

 FourFloats key(aMinR, mMaxR, aMinBorderRadius, aMaxBorderRadius);
 BestOverlap best;
 if (DottedCornerCache.Get(key, &best)) {
   mCount = best.count;
   mBestOverlap = best.overlap;
   return;
 }

 Float lower = 0.0f;
 Float upper = 0.5f;
 // Start from lower bound to find the minimum number of circles.
 Float overlap = 0.0f;
 mBestOverlap = overlap;
 size_t targetCount = 0;

 const Float OVERLAP_MARGIN = 0.1f;
 for (size_t j = 0; j < MAX_LOOP; j++) {
   Reset();

   size_t count;
   Float actualOverlap;
   if (!GetCountAndLastOverlap(overlap, &count, &actualOverlap)) {
     if (j == 0) {
       mCount = mMaxCount;
       break;
     }
   }

   if (j == 0) {
     if (count < 3 || (count == 3 && actualOverlap > 0.5f)) {
       // |count == 3 && actualOverlap > 0.5f| means there could be
       // a circle but it is too near from both ends.
       //
       // if actualOverlap == 0.0
       //               1       2       3
       //   +-------+-------+-------+-------+
       //   | ##### | ***** | ##### | ##### |
       //   |#######|*******|#######|#######|
       //   |###+###|***+***|###+###|###+###|
       //   |# C_0 #|* C_1 *|# C_2 #|# C_n #|
       //   | ##### | ***** | ##### | ##### |
       //   +-------+-------+-------+-------+
       //                   |
       //                   V
       //   +-------+---+-------+---+-------+
       //   | ##### |   | ##### |   | ##### |
       //   |#######|   |#######|   |#######|
       //   |###+###|   |###+###|   |###+###| Find the best overlap to place
       //   |# C_0 #|   |# C_1 #|   |# C_n #| C_1 at the middle of them
       //   | ##### |   | ##### |   | ##### |
       //   +-------+---+-------+---|-------+
       //
       // if actualOverlap == 0.5
       //               1       2     3
       //   +-------+-------+-------+---+
       //   | ##### | ***** | ##### |## |
       //   |#######|*******|##### C_n #|
       //   |###+###|***+***|###+###+###|
       //   |# C_0 #|* C_1 *|# C_2 #|###|
       //   | ##### | ***** | ##### |## |
       //   +-------+-------+-------+---+
       //                 |
       //                 V
       //   +-------+-+-------+-+-------+
       //   | ##### | | ##### | | ##### |
       //   |#######| |#######| |#######|
       //   |###+###| |###+###| |###+###| Even if we place C_1 at the middle
       //   |# C_0 #| |# C_1 #| |# C_n #| of them, it's too near from them
       //   | ##### | | ##### | | ##### |
       //   +-------+-+-------+-|-------+
       //                 |
       //                 V
       //   +-------+-----------+-------+
       //   | ##### |           | ##### |
       //   |#######|           |#######|
       //   |###+###|           |###+###| Do not draw any circle
       //   |# C_0 #|           |# C_n #|
       //   | ##### |           | ##### |
       //   +-------+-----------+-------+
       mCount = 0;
       break;
     }

     // targetCount should be 2n, as we're searching C_1 to C_n.
     //
     //   targetCount = 4
     //   mCount = 1
     //               1       2       3       4
     //   +-------+-------+-------+-------+-------+
     //   | ##### | ***** | ##### | ***** | ##### |
     //   |#######|*******|#######|*******|#######|
     //   |###+###|***+***|###+###|***+***|###+###|
     //   |# C_0 #|* C_1 *|# C_2 #|* C_3 *|# C_n #|
     //   | ##### | ***** | ##### | ***** | ##### |
     //   +-------+-------+-------+-------+-------+
     //                       1
     //
     //   targetCount = 6
     //   mCount = 2
     //               1       2       3       4       5       6
     //   +-------+-------+-------+-------+-------+-------+-------+
     //   | ##### | ***** | ##### | ***** | ##### | ***** | ##### |
     //   |#######|*******|#######|*******|#######|*******|#######|
     //   |###+###|***+***|###+###|***+***|###+###|***+***|###+###|
     //   |# C_0 #|* C_1 *|# C_2 #|* C_3 *|# C_4 #|* C_5 *|# C_n #|
     //   | ##### | ***** | ##### | ***** | ##### | ***** | ##### |
     //   +-------+-------+-------+-------+-------+-------+-------+
     //                       1               2
     if (count % 2) {
       targetCount = count + 1;
     } else {
       targetCount = count;
     }

     mCount = targetCount / 2 - 1;
   }

   if (count == targetCount) {
     mBestOverlap = overlap;

     if (fabs(actualOverlap - overlap) < OVERLAP_MARGIN) {
       break;
     }

     // We started from upper bound, no need to update range when j == 0.
     if (j > 0) {
       if (actualOverlap > overlap) {
         lower = overlap;
       } else {
         upper = overlap;
       }
     }
   } else {
     // |j == 0 && count != targetCount| means that |targetCount = count + 1|,
     // and we started from upper bound, no need to update range when j == 0.
     if (j > 0) {
       if (count > targetCount) {
         upper = overlap;
       } else {
         lower = overlap;
       }
     }
   }

   overlap = (upper + lower) / 2.0f;
 }

 if (DottedCornerCache.Count() > DottedCornerCacheSize) {
   DottedCornerCache.Clear();
 }
 DottedCornerCache.InsertOrUpdate(key, BestOverlap(mBestOverlap, mCount));
}

bool DottedCornerFinder::GetCountAndLastOverlap(Float aOverlap, size_t* aCount,
                                               Float* aActualOverlap) {
 // Return the number of circles and the last circles' overlap for the
 // given overlap.

 Reset();

 const Float T_MARGIN = 0.001f;
 const Float DIST_MARGIN = 0.1f;
 const Float DIST_MARGIN_SQUARE = Square(DIST_MARGIN);
 for (size_t i = 0; i < mMaxCount; i++) {
   Float actualOverlap = FindNext(aOverlap);
   if (mLastT >= 1.0f - T_MARGIN ||
       (mLastC - mCn).LengthSquare() < DIST_MARGIN_SQUARE) {
     *aCount = i + 1;
     *aActualOverlap = actualOverlap;
     return true;
   }
 }

 return false;
}

}  // namespace mozilla