layout/painting/DottedCornerFinder.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
   2 /* vim: set ts=8 sts=2 et sw=2 tw=80: */
   3 /* This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 #ifndef mozilla_DottedCornerFinder_h_
   8 #define mozilla_DottedCornerFinder_h_
   9
  10 #include "mozilla/gfx/2D.h"
  11 #include "mozilla/gfx/BezierUtils.h"
  12 #include "gfxRect.h"
  13
  14 namespace mozilla {
  15
  16 // Calculate C_i and r_i for each filled/unfilled circles in dotted corner.
  17 // Returns circle with C_{2j} and r_{2j} where 0 < 2j < n.
  18 //
  19 //                            ____-----------+
  20 //                      __----  *****     ###|
  21 //                __----      *********  ####|
  22 //           __---  #####    ***********#####|
  23 //        _--     #########  *****+*****#####+ C_0
  24 //      _-       ########### *** C_1****#####|
  25 //     /         #####+#####  *********  ####|
  26 //    /       .  ### C_2 ###    *****     ###|
  27 //   |            #########       ____-------+
  28 //   |     .        #####____-----
  29 //  |              __----
  30 //  |    .       /
  31 // |           /
  32 // |  *****   |
  33 // | ******* |
  34 // |*********|
  35 // |****+****|
  36 // | C_{n-1} |
  37 // | ******* |
  38 // |  *****  |
  39 // |  #####  |
  40 // | ####### |
  41 // |#########|
  42 // +----+----+
  43 //     C_n
  44
  45 class DottedCornerFinder {
  46   typedef mozilla::gfx::Bezier Bezier;
  47   typedef mozilla::gfx::Float Float;
  48   typedef mozilla::gfx::Point Point;
  49   typedef mozilla::gfx::Size Size;
  50
  51  public:
  52   struct Result {
  53     // Center point of dot and its radius.
  54     Point C;
  55     Float r;
  56
  57     Result(const Point& aC, Float aR) : C(aC), r(aR) { MOZ_ASSERT(aR >= 0); }
  58   };
  59
  60   //                        aBorderRadiusX
  61   //                       aCornerDim.width
  62   //                     |<----------------->|
  63   //                     |                   | v
  64   //                   --+-------------___---+--
  65   //                   ^ |         __--      | |
  66   //                   | |       _-          | | aR0
  67   //                   | |     /         aC0 +--
  68   //                   | |   /               | ^
  69   //                   | |  |                |
  70   //  aBorderRadiusY   | | |             __--+
  71   // aCornerDim.height | ||            _-
  72   //                   | ||           /
  73   //                   | |           /
  74   //                   | |          |
  75   //                   | |          |
  76   //                   | |         |
  77   //                   | |         |
  78   //                   v |    aCn  |
  79   //                   --+----+----+
  80   //                     |    |
  81   //                     |<-->|
  82   //                      aRn
  83   //
  84   // aCornerDim and (aBorderRadiusX, aBorderRadiusY) can be different when
  85   // aBorderRadiusX is smaller than aRn*2 or
  86   // aBorderRadiusY is smaller than aR0*2.
  87   //
  88   //                                        aCornerDim.width
  89   //                                      |<----------------->|
  90   //                                      |                   |
  91   //                                      | aBorderRadiusX    |
  92   //                                      |<--------->|       |
  93   //                                      |           |       |
  94   //                   -------------------+-------__--+-------+--
  95   //                   ^                ^ |     _-            | ^
  96   //                   |                | |   /               | |
  97   //                   |                | |  /                | |
  98   //                   | aBorderRadiusY | | |                 | | aR0
  99   //                   |                | ||                  | |
 100   //                   |                | |                   | |
 101   // aCornerDim.height |                v |                   | v
 102   //                   |                --+               aC0 +--
 103   //                   |                  |                   |
 104   //                   |                  |                   |
 105   //                   |                  |                   |
 106   //                   |                  |                   |
 107   //                   |                  |                   |
 108   //                   v                  |        aCn        |
 109   //                   -------------------+---------+---------+
 110   //                                      |         |
 111   //                                      |<------->|
 112   //                                          aRn
 113   DottedCornerFinder(const Bezier& aOuterBezier, const Bezier& aInnerBezier,
 114                      mozilla::Corner aCorner, Float aBorderRadiusX,
 115                      Float aBorderRadiusY, const Point& aC0, Float aR0,
 116                      const Point& aCn, Float aRn, const Size& aCornerDim);
 117
 118   bool HasMore(void) const;
 119   Result Next(void);
 120
 121  private:
 122   static const size_t MAX_LOOP = 32;
 123
 124   // Bezier control points for the outer curve, the inner curve, and a curve
 125   // that center points of circles are on (center curve).
 126   //
 127   //               ___---+ outer curve
 128   //           __--      |
 129   //         _-          |
 130   //       /        __---+ center curve
 131   //     /      __--     |
 132   //    |     /          |
 133   //   |    /        __--+ inner curve
 134   //  |    |       _-
 135   //  |    |      /
 136   // |     |     /
 137   // |    |     |
 138   // |    |     |
 139   // |    |    |
 140   // |    |    |
 141   // |    |    |
 142   // +----+----+
 143   Bezier mOuterBezier;
 144   Bezier mInnerBezier;
 145   Bezier mCenterBezier;
 146
 147   mozilla::Corner mCorner;
 148
 149   // Sign of the normal vector used in radius calculation, flipped depends on
 150   // corner and start and end radii.
 151   Float mNormalSign;
 152
 153   // Center points and raii for start and end circles, mR0 >= mRn.
 154   // mMaxR = max(mR0, mRn)
 155   //
 156   //                           v
 157   //               ___---+------
 158   //           __--     #|#    | mRn
 159   //         _-        ##|##   |
 160   //       /           ##+## ---
 161   //     /              mCn    ^
 162   //    |               #|#
 163   //   |             __--+
 164   //  |            _-
 165   //  |           /
 166   // |           /
 167   // |          |
 168   // |          |
 169   // |  #####  |
 170   // | ####### |
 171   // |#########|
 172   // +----+----+
 173   // |## mC0 ##|
 174   // | ####### |
 175   // |  #####  |
 176   // |    |
 177   // |<-->|
 178   //
 179   //  mR0
 180   //
 181   Point mC0;
 182   Point mCn;
 183   Float mR0;
 184   Float mRn;
 185   Float mMaxR;
 186
 187   // Parameters for the center curve with perfect circle and the inner curve.
 188   // The center curve doesn't necessarily share the origin with others.
 189   //
 190   //               ___---+
 191   //           __--      |
 192   //         _-          |
 193   //       /        __-+ |
 194   //     /      __--     |
 195   //    |     /          |
 196   //   |    /        __--+--
 197   //  |    |       _-    | ^
 198   //  |    |      /      | |
 199   // |     |     /       | |
 200   // |    |     |        | |
 201   // |    |     |        | | mInnerHeight
 202   // |    |    |         | |
 203   // |    +    |         | |
 204   // |         |         | v
 205   // +---------+---------+
 206   //           |         | mInnerCurveOrigin
 207   //           |<------->|
 208   //           mInnerWidth
 209   //
 210   //               ___---+
 211   //           __--
 212   //         _-
 213   //       /        __-+
 214   //     /      __--   |
 215   //    |     /        |
 216   //   |    /        __--+
 217   //  |    |       _-  |
 218   //  |    |      /    |
 219   // |     |     /     |
 220   // |    |     |      |
 221   // |    |     |      |
 222   // |    |    |       |
 223   // |    +--- | ------+
 224   // |    |    |       | mCenterCurveOrigin
 225   // +    |    +       |
 226   //      |            |
 227   //      |            |
 228   //      |            |
 229   //      |            |
 230   //      |<---------->|
 231   //       mCenterCurveR
 232   //
 233   Point mCenterCurveOrigin;
 234   Float mCenterCurveR;
 235   Point mInnerCurveOrigin;
 236   Float mInnerWidth;
 237   Float mInnerHeight;
 238
 239   Point mLastC;
 240   Float mLastR;
 241   Float mLastT;
 242
 243   // Overlap between two circles.
 244   // It uses arc length on PERFECT, SINGLE_CURVE_AND_RADIUS, and SINGLE_CURVE,
 245   // and direct distance on OTHER.
 246   Float mBestOverlap;
 247
 248   // If one of border-widths is 0, do not calculate overlap, and draw circles
 249   // until it reaches the other side or exceeds mMaxCount.
 250   bool mHasZeroBorderWidth;
 251   bool mHasMore;
 252
 253   // The maximum number of filled/unfilled circles.
 254   size_t mMaxCount;
 255
 256   enum {
 257     //                      radius.width
 258     //                 |<----------------->|
 259     //                 |                   |
 260     //               --+-------------___---+----
 261     //               ^ |         __--     #|#  ^
 262     //               | |       _-        ##|## |
 263     //               | |     /           ##+## | top-width
 264     //               | |   /             ##|## |
 265     //               | |  |               #|#  v
 266     //               | | |             __--+----
 267     // radius.height | ||            _-
 268     //               | ||           /
 269     //               | |           /
 270     //               | |          |
 271     //               | |          |
 272     //               | |  #####  |
 273     //               | | ####### |
 274     //               v |#########|
 275     //               --+----+----+
 276     //                 |#########|
 277     //                 | ####### |
 278     //                 |  #####  |
 279     //                 |         |
 280     //                 |<------->|
 281     //                  left-width
 282
 283     // * top-width == left-width
 284     // * radius.width == radius.height
 285     // * top-width < radius.width * 2
 286     //
 287     // All circles has same radii and are on single perfect circle's arc.
 288     // Overlap is known.
 289     //
 290     // Split the perfect circle's arc into 2n segments, each segment's length is
 291     // top-width * (1 - overlap).  Place each circle's center point C_i on each
 292     // end of the segment, each circle's radius r_i is top-width / 2
 293     //
 294     //                       #####
 295     //                      #######
 296     // perfect             #########
 297     // circle's          ___---+####
 298     // arc     ##### __--  ## C_0 ##
 299     //   |    #####_-       ###|###
 300     //   |   ####+####       ##|##
 301     //   |   ##/C_i ##         |
 302     //   |    |######          |
 303     //   |   | #####           |
 304     //   +->|                  |
 305     //     |                   |
 306     //   ##|##                 |
 307     //  ###|###                |
 308     // ####|####               |
 309     // ####+-------------------+
 310     // ## C_n ##
 311     //  #######
 312     //   #####
 313     PERFECT,
 314
 315     // * top-width == left-width
 316     // * 0.5 < radius.width / radius.height < 2.0
 317     // * top-width < min(radius.width, radius.height) * 2
 318     //
 319     // All circles has same radii and are on single elliptic arc.
 320     // Overlap is known.
 321     //
 322     // Split the elliptic arc into 2n segments, each segment's length is
 323     // top-width * (1 - overlap).  Place each circle's center point C_i on each
 324     // end of the segment, each circle's radius r_i is top-width / 2
 325     //
 326     //                            #####
 327     //                           #######
 328     //             #####        #########
 329     //            #######   ____----+####
 330     // elliptic  ######__---    ## C_0 ##
 331     // arc       ##__+-###       ###|###
 332     //   |      / # C_i #         ##|##
 333     //   +--> /    #####            |
 334     //       |                      |
 335     //   ###|#                      |
 336     //  ###|###                     |
 337     // ####|####                    |
 338     // ####+------------------------+
 339     // ## C_n ##
 340     //  #######
 341     //   #####
 342     SINGLE_CURVE_AND_RADIUS,
 343
 344     // * top-width != left-width
 345     // * 0 < min(top-width, left-width)
 346     // * 0.5 < radius.width / radius.height < 2.0
 347     // * max(top-width, left-width) < min(radius.width, radius.height) * 2
 348     //
 349     // All circles are on single elliptic arc.
 350     // Overlap is unknown.
 351     //
 352     // Place each circle's center point C_i on elliptic arc, each circle's
 353     // radius r_i is the distance between the center point and the inner curve.
 354     // The arc segment's length between C_i and C_{i-1} is
 355     // (r_i + r_{i-1}) * (1 - overlap).
 356     //
 357     //  outer curve
 358     //           /
 359     //          /
 360     //         /         / center curve
 361     //        / ####### /
 362     //       /##       /#
 363     //      +#        /  #
 364     //     /#        /    #
 365     //    / #   C_i /     #
 366     //   /  #      +      #  /
 367     //  /   #     /  \    # / inner curve
 368     //      #    /     \  #/
 369     //       #  /   r_i  \+
 370     //        #/       ##/
 371     //        / ####### /
 372     //                 /
 373     SINGLE_CURVE,
 374
 375     // Other cases.
 376     // Circles are not on single elliptic arc.
 377     // Overlap are unknown.
 378     //
 379     // Place tangent point innerTangent on the inner curve and find circle's
 380     // center point C_i and radius r_i where the circle is also tangent to the
 381     // outer curve.
 382     // Distance between C_i and C_{i-1} is (r_i + r_{i-1}) * (1 - overlap).
 383     //
 384     //  outer curve
 385     //           /
 386     //          /
 387     //         /
 388     //        / #######
 389     //       /##       ##
 390     //      +#           #
 391     //     /# \           #
 392     //    / #    \        #
 393     //   /  #      +      #  /
 394     //  /   #   C_i  \    # / inner curve
 395     //      #          \  #/
 396     //       #      r_i  \+
 397     //        ##       ##/ innerTangent
 398     //          ####### /
 399     //                 /
 400     OTHER
 401   } mType;
 402
 403   size_t mI;
 404   size_t mCount;
 405
 406   // Determine mType from parameters.
 407   void DetermineType(Float aBorderRadiusX, Float aBorderRadiusY);
 408
 409   // Reset calculation.
 410   void Reset(void);
 411
 412   // Find radius for the given tangent point on the inner curve such that the
 413   // circle is also tangent to the outer curve.
 414   void FindPointAndRadius(Point& C, Float& r, const Point& innerTangent,
 415                           const Point& normal, Float t);
 416
 417   // Find next dot.
 418   Float FindNext(Float overlap);
 419
 420   // Find mBestOverlap for parameters.
 421   void FindBestOverlap(Float aMinR, Float aMinBorderRadius,
 422                        Float aMaxBorderRadius);
 423
 424   // Fill corner with dots with given overlap, and return the number of dots
 425   // and last two dots's overlap.
 426   bool GetCountAndLastOverlap(Float aOverlap, size_t* aCount,
 427                               Float* aActualOverlap);
 428 };
 429
 430 }  // namespace mozilla
 431
 432 #endif /* mozilla_DottedCornerFinder_h_ */