summaryrefslogtreecommitdiffstats
path: root/layout/base/DashedCornerFinder.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'layout/base/DashedCornerFinder.cpp')
-rw-r--r--layout/base/DashedCornerFinder.cpp427
1 files changed, 427 insertions, 0 deletions
diff --git a/layout/base/DashedCornerFinder.cpp b/layout/base/DashedCornerFinder.cpp
new file mode 100644
index 000000000..cb58eb51e
--- /dev/null
+++ b/layout/base/DashedCornerFinder.cpp
@@ -0,0 +1,427 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 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 "DashedCornerFinder.h"
+
+#include "mozilla/Move.h"
+#include "BorderCache.h"
+#include "BorderConsts.h"
+
+namespace mozilla {
+
+using namespace gfx;
+
+struct BestDashLength
+{
+ typedef mozilla::gfx::Float Float;
+
+ Float dashLength;
+ size_t count;
+
+ BestDashLength()
+ : dashLength(0.0f), count(0)
+ {}
+
+ BestDashLength(Float aDashLength, size_t aCount)
+ : dashLength(aDashLength), count(aCount)
+ {}
+};
+
+static const size_t DashedCornerCacheSize = 256;
+nsDataHashtable<FourFloatsHashKey, BestDashLength> DashedCornerCache;
+
+DashedCornerFinder::DashedCornerFinder(const Bezier& aOuterBezier,
+ const Bezier& aInnerBezier,
+ Float aBorderWidthH, Float aBorderWidthV,
+ const Size& aCornerDim)
+ : mOuterBezier(aOuterBezier),
+ mInnerBezier(aInnerBezier),
+ mLastOuterP(aOuterBezier.mPoints[0]), mLastInnerP(aInnerBezier.mPoints[0]),
+ mLastOuterT(0.0f), mLastInnerT(0.0f),
+ mBestDashLength(DOT_LENGTH * DASH_LENGTH),
+ mHasZeroBorderWidth(false), mHasMore(true),
+ mMaxCount(aCornerDim.width + aCornerDim.height),
+ mType(OTHER),
+ mI(0), mCount(0)
+{
+ NS_ASSERTION(aBorderWidthH > 0.0f || aBorderWidthV > 0.0f,
+ "At least one side should have non-zero width.");
+
+ DetermineType(aBorderWidthH, aBorderWidthV);
+
+ Reset();
+}
+
+void
+DashedCornerFinder::DetermineType(Float aBorderWidthH, Float aBorderWidthV)
+{
+ if (aBorderWidthH < aBorderWidthV) {
+ // Always draw from wider side to thinner side.
+ 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]);
+ mLastOuterP = mOuterBezier.mPoints[0];
+ mLastInnerP = mInnerBezier.mPoints[0];
+ }
+
+ // See the comment at mType declaration for each condition.
+
+ Float borderRadiusA = fabs(mOuterBezier.mPoints[0].x -
+ mOuterBezier.mPoints[3].x);
+ Float borderRadiusB = fabs(mOuterBezier.mPoints[0].y -
+ mOuterBezier.mPoints[3].y);
+ if (aBorderWidthH == aBorderWidthV &&
+ borderRadiusA == borderRadiusB &&
+ borderRadiusA > aBorderWidthH * 2.0f) {
+ Float curveHeight = borderRadiusA - aBorderWidthH / 2.0;
+
+ mType = PERFECT;
+ Float borderLength = M_PI * curveHeight / 2.0f;
+
+ Float dashWidth = aBorderWidthH * DOT_LENGTH * DASH_LENGTH;
+ size_t count = ceil(borderLength / dashWidth);
+ if (count % 2) {
+ count++;
+ }
+ mCount = count / 2 + 1;
+ mBestDashLength = borderLength / (aBorderWidthH * count);
+ }
+
+ Float minBorderWidth = std::min(aBorderWidthH, aBorderWidthV);
+ if (minBorderWidth == 0.0f) {
+ mHasZeroBorderWidth = true;
+ }
+
+ if (mType == OTHER && !mHasZeroBorderWidth) {
+ Float minBorderRadius = std::min(borderRadiusA, borderRadiusB);
+ Float maxBorderRadius = std::max(borderRadiusA, borderRadiusB);
+ Float maxBorderWidth = std::max(aBorderWidthH, aBorderWidthV);
+
+ FindBestDashLength(minBorderWidth, maxBorderWidth,
+ minBorderRadius, maxBorderRadius);
+ }
+}
+
+bool
+DashedCornerFinder::HasMore(void) const
+{
+ if (mHasZeroBorderWidth) {
+ return mI < mMaxCount && mHasMore;
+ }
+
+ return mI < mCount;
+}
+
+DashedCornerFinder::Result
+DashedCornerFinder::Next(void)
+{
+ Float lastOuterT, lastInnerT, outerT, innerT;
+
+ if (mI == 0) {
+ lastOuterT = 0.0f;
+ lastInnerT = 0.0f;
+ } else {
+ if (mType == PERFECT) {
+ lastOuterT = lastInnerT = (mI * 2.0f - 0.5f) / ((mCount - 1) * 2.0f);
+ } else {
+ Float last2OuterT = mLastOuterT;
+ Float last2InnerT = mLastInnerT;
+
+ (void)FindNext(mBestDashLength);
+
+ //
+ // mLastOuterT lastOuterT
+ // | |
+ // v v
+ // +---+---+---+---+ <- last2OuterT
+ // | |###|###| |
+ // | |###|###| |
+ // | |###|###| |
+ // +---+---+---+---+ <- last2InnerT
+ // ^ ^
+ // | |
+ // mLastInnerT lastInnerT
+ lastOuterT = (mLastOuterT + last2OuterT) / 2.0f;
+ lastInnerT = (mLastInnerT + last2InnerT) / 2.0f;
+ }
+ }
+
+ if ((!mHasZeroBorderWidth && mI == mCount - 1) ||
+ (mHasZeroBorderWidth && !mHasMore)) {
+ outerT = 1.0f;
+ innerT = 1.0f;
+ } else {
+ if (mType == PERFECT) {
+ outerT = innerT = (mI * 2.0f + 0.5f) / ((mCount - 1) * 2.0f);
+ } else {
+ Float last2OuterT = mLastOuterT;
+ Float last2InnerT = mLastInnerT;
+
+ (void)FindNext(mBestDashLength);
+
+ //
+ // outerT last2OuterT
+ // | |
+ // v v
+ // mLastOuterT -> +---+---+---+---+
+ // | |###|###| |
+ // | |###|###| |
+ // | |###|###| |
+ // mLastInnerT -> +---+---+---+---+
+ // ^ ^
+ // | |
+ // innerT last2InnerT
+ outerT = (mLastOuterT + last2OuterT) / 2.0f;
+ innerT = (mLastInnerT + last2InnerT) / 2.0f;
+ }
+ }
+
+ mI++;
+
+ Bezier outerSectionBezier;
+ Bezier innerSectionBezier;
+ GetSubBezier(&outerSectionBezier, mOuterBezier, lastOuterT, outerT);
+ GetSubBezier(&innerSectionBezier, mInnerBezier, lastInnerT, innerT);
+ return DashedCornerFinder::Result(outerSectionBezier, innerSectionBezier);
+}
+
+void
+DashedCornerFinder::Reset(void)
+{
+ mLastOuterP = mOuterBezier.mPoints[0];
+ mLastInnerP = mInnerBezier.mPoints[0];
+ mLastOuterT = 0.0f;
+ mLastInnerT = 0.0f;
+ mHasMore = true;
+}
+
+Float
+DashedCornerFinder::FindNext(Float dashLength)
+{
+ Float upper = 1.0f;
+ Float lower = mLastOuterT;
+
+ Point OuterP, InnerP;
+ // Start from upper bound to check if this is the last segment.
+ Float outerT = upper;
+ Float innerT;
+ Float W = 0.0f;
+ Float L = 0.0f;
+
+ const Float LENGTH_MARGIN = 0.1f;
+ for (size_t i = 0; i < MAX_LOOP; i++) {
+ OuterP = GetBezierPoint(mOuterBezier, outerT);
+ InnerP = FindBezierNearestPoint(mInnerBezier, OuterP, outerT, &innerT);
+
+ // Calculate approximate dash length.
+ //
+ // W = (W1 + W2) / 2
+ // L = (OuterL + InnerL) / 2
+ // dashLength = L / W
+ //
+ // ____----+----____
+ // OuterP ___--- | ---___ mLastOuterP
+ // +--- | ---+
+ // | | |
+ // | | |
+ // | W | W1 |
+ // | | |
+ // W2 | | |
+ // | | ______------+
+ // | ____+---- mLastInnerP
+ // | ___---
+ // | __---
+ // +--
+ // InnerP
+ // OuterL
+ // ____---------____
+ // OuterP ___--- ---___ mLastOuterP
+ // +--- ---+
+ // | L |
+ // | ___----------______ |
+ // | __--- -----+
+ // | __-- |
+ // +-- |
+ // | InnerL ______------+
+ // | ____----- mLastInnerP
+ // | ___---
+ // | __---
+ // +--
+ // InnerP
+ Float W1 = (mLastOuterP - mLastInnerP).Length();
+ Float W2 = (OuterP - InnerP).Length();
+ Float OuterL = GetBezierLength(mOuterBezier, mLastOuterT, outerT);
+ Float InnerL = GetBezierLength(mInnerBezier, mLastInnerT, innerT);
+ W = (W1 + W2) / 2.0f;
+ L = (OuterL + InnerL) / 2.0f;
+ if (L > W * dashLength + LENGTH_MARGIN) {
+ if (i > 0) {
+ upper = outerT;
+ }
+ } else if (L < W * dashLength - LENGTH_MARGIN) {
+ if (i == 0) {
+ // This is the last segment with shorter dashLength.
+ mHasMore = false;
+ break;
+ }
+ lower = outerT;
+ } else {
+ break;
+ }
+
+ outerT = (upper + lower) / 2.0f;
+ }
+
+ mLastOuterP = OuterP;
+ mLastInnerP = InnerP;
+ mLastOuterT = outerT;
+ mLastInnerT = innerT;
+
+ if (W == 0.0f) {
+ return 1.0f;
+ }
+
+ return L / W;
+}
+
+void
+DashedCornerFinder::FindBestDashLength(Float aMinBorderWidth,
+ Float aMaxBorderWidth,
+ Float aMinBorderRadius,
+ Float aMaxBorderRadius)
+{
+ // If dashLength is not calculateable, find it with binary search,
+ // such that there exists i that OuterP_i == OuterP_n and
+ // InnerP_i == InnerP_n with given dashLength.
+
+ FourFloats key(aMinBorderWidth, aMaxBorderWidth,
+ aMinBorderRadius, aMaxBorderRadius);
+ BestDashLength best;
+ if (DashedCornerCache.Get(key, &best)) {
+ mCount = best.count;
+ mBestDashLength = best.dashLength;
+ return;
+ }
+
+ Float lower = 1.0f;
+ Float upper = DOT_LENGTH * DASH_LENGTH;
+ Float dashLength = upper;
+ size_t targetCount = 0;
+
+ const Float LENGTH_MARGIN = 0.1f;
+ for (size_t j = 0; j < MAX_LOOP; j++) {
+ size_t count;
+ Float actualDashLength;
+ if (!GetCountAndLastDashLength(dashLength, &count, &actualDashLength)) {
+ if (j == 0) {
+ mCount = mMaxCount;
+ break;
+ }
+ }
+
+ if (j == 0) {
+ if (count == 1) {
+ // If only 1 segment fits, fill entire region
+ //
+ // count = 1
+ // mCount = 1
+ // | 1 |
+ // +---+---+
+ // |###|###|
+ // |###|###|
+ // |###|###|
+ // +---+---+
+ // 1
+ mCount = 1;
+ break;
+ }
+
+ // targetCount should be 2n.
+ //
+ // targetCount = 2
+ // mCount = 2
+ // | 1 | 2 |
+ // +---+---+---+---+
+ // |###| | |###|
+ // |###| | |###|
+ // |###| | |###|
+ // +---+---+---+---+
+ // 1 2
+ //
+ // targetCount = 6
+ // mCount = 4
+ // | 1 | 2 | 3 | 4 | 5 | 6 |
+ // +---+---+---+---+---+---+---+---+---+---+---+---+
+ // |###| | |###|###| | |###|###| | |###|
+ // |###| | |###|###| | |###|###| | |###|
+ // |###| | |###|###| | |###|###| | |###|
+ // +---+---+---+---+---+---+---+---+---+---+---+---+
+ // 1 2 3 4
+ if (count % 2) {
+ targetCount = count + 1;
+ } else {
+ targetCount = count;
+ }
+
+ mCount = targetCount / 2 + 1;
+ }
+
+ if (count == targetCount) {
+ mBestDashLength = dashLength;
+
+ // actualDashLength won't be greater than dashLength.
+ if (actualDashLength > dashLength - LENGTH_MARGIN) {
+ break;
+ }
+
+ // We started from upper bound, no need to update range when j == 0.
+ if (j > 0) {
+ upper = dashLength;
+ }
+ } 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) {
+ lower = dashLength;
+ } else {
+ upper = dashLength;
+ }
+ }
+ }
+
+ dashLength = (upper + lower) / 2.0f;
+ }
+
+ if (DashedCornerCache.Count() > DashedCornerCacheSize) {
+ DashedCornerCache.Clear();
+ }
+ DashedCornerCache.Put(key, BestDashLength(mBestDashLength, mCount));
+}
+
+bool
+DashedCornerFinder::GetCountAndLastDashLength(Float aDashLength,
+ size_t* aCount,
+ Float* aActualDashLength)
+{
+ // Return the number of segments and the last segment's dashLength for
+ // the given dashLength.
+
+ Reset();
+
+ for (size_t i = 0; i < mMaxCount; i++) {
+ Float actualDashLength = FindNext(aDashLength);
+ if (mLastOuterT >= 1.0f) {
+ *aCount = i + 1;
+ *aActualDashLength = actualDashLength;
+ return true;
+ }
+ }
+
+ return false;
+}
+
+} // namespace mozilla
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-10 11:51:50 +0000