/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ // vim:cindent:ts=2:et:sw=2: /* 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 "mozilla/Move.h" #include "BorderCache.h" #include "BorderConsts.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; nsDataHashtable<FourFloatsHashKey, BestOverlap> DottedCornerCache; DottedCornerFinder::DottedCornerFinder(const Bezier& aOuterBezier, const Bezier& aInnerBezier, mozilla::css::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), 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. Swap(mC0, mCn); Swap(mR0, mRn); Swap(mInnerBezier.mPoints[0], mInnerBezier.mPoints[3]); Swap(mInnerBezier.mPoints[1], mInnerBezier.mPoints[2]); Swap(mOuterBezier.mPoints[0], mOuterBezier.mPoints[3]); 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) { Swap(mCenterBezier.mPoints[0], mCenterBezier.mPoints[3]); 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.Put(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