summaryrefslogtreecommitdiff
path: root/layout/base/DottedCornerFinder.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'layout/base/DottedCornerFinder.cpp')
-rw-r--r--layout/base/DottedCornerFinder.cpp568
1 files changed, 568 insertions, 0 deletions
diff --git a/layout/base/DottedCornerFinder.cpp b/layout/base/DottedCornerFinder.cpp
new file mode 100644
index 0000000000..fb9534f54e
--- /dev/null
+++ b/layout/base/DottedCornerFinder.cpp
@@ -0,0 +1,568 @@
+/* -*- 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
generated by cgit v1.2.3 (git 2.26.2) at 2024-11-15 10:34:08 +0000