Quelle DottedCornerFinder.cpp Sprache: C

/* -*- 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

quality95%

¤ Dauer der Verarbeitung: 0.1 Sekunden (vorverarbeitet) ¤

Wurzel

Suchen

Beweissystem der NASA

Beweissystem Isabelle

NIST Cobol Testsuite

Cephes Mathematical Library

Wiener Entwicklungsmethode

Haftungshinweis

Die Informationen auf dieser Webseite wurden nach bestem Wissen sorgfältig zusammengestellt. Es wird jedoch weder Vollständigkeit, noch Richtigkeit, noch Qualität der bereit gestellten Informationen zugesichert.

Bemerkung:

Die farbliche Syntaxdarstellung ist noch experimentell.