Line data Source code
1 : /* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : // vim:cindent:ts=2:et:sw=2:
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 : #include "DottedCornerFinder.h"
8 :
9 : #include "mozilla/Move.h"
10 : #include "BorderCache.h"
11 : #include "BorderConsts.h"
12 :
13 : namespace mozilla {
14 :
15 : using namespace gfx;
16 :
17 : static inline Float
18 0 : Square(Float x)
19 : {
20 0 : return x * x;
21 : }
22 :
23 : static Point
24 0 : PointRotateCCW90(const Point& aP)
25 : {
26 0 : return Point(aP.y, -aP.x);
27 : }
28 :
29 : struct BestOverlap
30 : {
31 : Float overlap;
32 : size_t count;
33 :
34 0 : BestOverlap()
35 0 : : overlap(0.0f), count(0)
36 0 : {}
37 :
38 0 : BestOverlap(Float aOverlap, size_t aCount)
39 0 : : overlap(aOverlap), count(aCount)
40 0 : {}
41 : };
42 :
43 : static const size_t DottedCornerCacheSize = 256;
44 3 : nsDataHashtable<FourFloatsHashKey, BestOverlap> DottedCornerCache;
45 :
46 0 : DottedCornerFinder::DottedCornerFinder(const Bezier& aOuterBezier,
47 : const Bezier& aInnerBezier,
48 : Corner aCorner,
49 : Float aBorderRadiusX,
50 : Float aBorderRadiusY,
51 : const Point& aC0, Float aR0,
52 : const Point& aCn, Float aRn,
53 0 : const Size& aCornerDim)
54 : : mOuterBezier(aOuterBezier),
55 : mInnerBezier(aInnerBezier),
56 : mCorner(aCorner),
57 0 : mNormalSign((aCorner == C_TL || aCorner == C_BR) ? -1.0f : 1.0f),
58 : mC0(aC0), mCn(aCn),
59 0 : mR0(aR0), mRn(aRn), mMaxR(std::max(aR0, aRn)),
60 : mCenterCurveOrigin(mC0.x, mCn.y),
61 : mInnerCurveOrigin(mInnerBezier.mPoints[0].x, mInnerBezier.mPoints[3].y),
62 : mBestOverlap(0.0f),
63 : mHasZeroBorderWidth(false), mHasMore(true),
64 0 : mMaxCount(aCornerDim.width + aCornerDim.height),
65 : mType(OTHER),
66 0 : mI(0), mCount(0)
67 : {
68 0 : NS_ASSERTION(mR0 > 0.0f || mRn > 0.0f,
69 : "At least one side should have non-zero radius.");
70 :
71 0 : mInnerWidth = fabs(mInnerBezier.mPoints[0].x - mInnerBezier.mPoints[3].x);
72 0 : mInnerHeight = fabs(mInnerBezier.mPoints[0].y - mInnerBezier.mPoints[3].y);
73 :
74 0 : DetermineType(aBorderRadiusX, aBorderRadiusY);
75 :
76 0 : Reset();
77 0 : }
78 :
79 : static bool
80 0 : IsSingleCurve(Float aMinR, Float aMaxR,
81 : Float aMinBorderRadius, Float aMaxBorderRadius)
82 : {
83 0 : return aMinR > 0.0f &&
84 0 : aMinBorderRadius > aMaxR * 4.0f &&
85 0 : aMinBorderRadius / aMaxBorderRadius > 0.5f;
86 : }
87 :
88 : void
89 0 : DottedCornerFinder::DetermineType(Float aBorderRadiusX, Float aBorderRadiusY)
90 : {
91 : // Calculate parameters for the center curve before swap.
92 0 : Float centerCurveWidth = fabs(mC0.x - mCn.x);
93 0 : Float centerCurveHeight = fabs(mC0.y - mCn.y);
94 0 : Point cornerPoint(mCn.x, mC0.y);
95 :
96 0 : bool swapped = false;
97 0 : if (mR0 < mRn) {
98 : // Always draw from wider side to thinner side.
99 0 : Swap(mC0, mCn);
100 0 : Swap(mR0, mRn);
101 0 : Swap(mInnerBezier.mPoints[0], mInnerBezier.mPoints[3]);
102 0 : Swap(mInnerBezier.mPoints[1], mInnerBezier.mPoints[2]);
103 0 : Swap(mOuterBezier.mPoints[0], mOuterBezier.mPoints[3]);
104 0 : Swap(mOuterBezier.mPoints[1], mOuterBezier.mPoints[2]);
105 0 : mNormalSign = -mNormalSign;
106 0 : swapped = true;
107 : }
108 :
109 : // See the comment at mType declaration for each condition.
110 :
111 0 : Float minR = std::min(mR0, mRn);
112 0 : Float minBorderRadius = std::min(aBorderRadiusX, aBorderRadiusY);
113 0 : Float maxBorderRadius = std::max(aBorderRadiusX, aBorderRadiusY);
114 0 : if (IsSingleCurve(minR, mMaxR, minBorderRadius, maxBorderRadius)) {
115 0 : if (mR0 == mRn) {
116 : Float borderLength;
117 0 : if (minBorderRadius == maxBorderRadius) {
118 0 : mType = PERFECT;
119 0 : borderLength = M_PI * centerCurveHeight / 2.0f;
120 :
121 0 : mCenterCurveR = centerCurveWidth;
122 : } else {
123 0 : mType = SINGLE_CURVE_AND_RADIUS;
124 : borderLength = GetQuarterEllipticArcLength(centerCurveWidth,
125 0 : centerCurveHeight);
126 : }
127 :
128 0 : Float diameter = mR0 * 2.0f;
129 0 : size_t count = round(borderLength / diameter);
130 0 : if (count % 2) {
131 0 : count++;
132 : }
133 0 : mCount = count / 2 - 1;
134 0 : if (mCount > 0) {
135 0 : mBestOverlap = 1.0f - borderLength / (diameter * count);
136 : }
137 : } else {
138 0 : mType = SINGLE_CURVE;
139 : }
140 : }
141 :
142 0 : if (mType == SINGLE_CURVE_AND_RADIUS || mType == SINGLE_CURVE) {
143 0 : Size cornerSize(centerCurveWidth, centerCurveHeight);
144 0 : GetBezierPointsForCorner(&mCenterBezier, mCorner,
145 0 : cornerPoint, cornerSize);
146 0 : if (swapped) {
147 0 : Swap(mCenterBezier.mPoints[0], mCenterBezier.mPoints[3]);
148 0 : Swap(mCenterBezier.mPoints[1], mCenterBezier.mPoints[2]);
149 : }
150 : }
151 :
152 0 : if (minR == 0.0f) {
153 0 : mHasZeroBorderWidth = true;
154 : }
155 :
156 0 : if ((mType == SINGLE_CURVE || mType == OTHER) && !mHasZeroBorderWidth) {
157 0 : FindBestOverlap(minR, minBorderRadius, maxBorderRadius);
158 : }
159 0 : }
160 :
161 :
162 : bool
163 0 : DottedCornerFinder::HasMore(void) const
164 : {
165 0 : if (mHasZeroBorderWidth) {
166 0 : return mI < mMaxCount && mHasMore;
167 : }
168 :
169 0 : return mI < mCount;
170 : }
171 :
172 : DottedCornerFinder::Result
173 0 : DottedCornerFinder::Next(void)
174 : {
175 0 : mI++;
176 :
177 0 : if (mType == PERFECT) {
178 0 : Float phi = mI * 4.0f * mR0 * (1 - mBestOverlap) / mCenterCurveR;
179 0 : if (mCorner == C_TL) {
180 0 : phi = -M_PI / 2.0f - phi;
181 0 : } else if (mCorner == C_TR) {
182 0 : phi = -M_PI / 2.0f + phi;
183 0 : } else if (mCorner == C_BR) {
184 0 : phi = M_PI / 2.0f - phi;
185 : } else {
186 0 : phi = M_PI / 2.0f + phi;
187 : }
188 :
189 0 : Point C(mCenterCurveOrigin.x + mCenterCurveR * cos(phi),
190 0 : mCenterCurveOrigin.y + mCenterCurveR * sin(phi));
191 0 : return DottedCornerFinder::Result(C, mR0);
192 : }
193 :
194 : // Find unfilled and filled circles.
195 0 : (void)FindNext(mBestOverlap);
196 0 : if (mHasMore) {
197 0 : (void)FindNext(mBestOverlap);
198 : }
199 :
200 0 : return Result(mLastC, mLastR);
201 : }
202 :
203 : void
204 0 : DottedCornerFinder::Reset(void)
205 : {
206 0 : mLastC = mC0;
207 0 : mLastR = mR0;
208 0 : mLastT = 0.0f;
209 0 : mHasMore = true;
210 0 : }
211 :
212 : void
213 0 : DottedCornerFinder::FindPointAndRadius(Point& C, Float& r,
214 : const Point& innerTangent,
215 : const Point& normal, Float t)
216 : {
217 : // Find radius for the given tangent point on the inner curve such that the
218 : // circle is also tangent to the outer curve.
219 :
220 0 : NS_ASSERTION(mType == OTHER, "Wrong mType");
221 :
222 0 : Float lower = 0.0f;
223 0 : Float upper = mMaxR;
224 0 : const Float DIST_MARGIN = 0.1f;
225 0 : for (size_t i = 0; i < MAX_LOOP; i++) {
226 0 : r = (upper + lower) / 2.0f;
227 0 : C = innerTangent + normal * r;
228 :
229 0 : Point Near = FindBezierNearestPoint(mOuterBezier, C, t);
230 0 : Float distSquare = (C - Near).LengthSquare();
231 :
232 0 : if (distSquare > Square(r + DIST_MARGIN)) {
233 0 : lower = r;
234 0 : } else if (distSquare < Square(r - DIST_MARGIN)) {
235 0 : upper = r;
236 : } else {
237 0 : break;
238 : }
239 : }
240 0 : }
241 :
242 : Float
243 0 : DottedCornerFinder::FindNext(Float overlap)
244 : {
245 0 : Float lower = mLastT;
246 0 : Float upper = 1.0f;
247 : Float t;
248 :
249 0 : Point C = mLastC;
250 0 : Float r = 0.0f;
251 :
252 0 : Float factor = (1.0f - overlap);
253 :
254 0 : Float circlesDist = 0.0f;
255 0 : Float expectedDist = 0.0f;
256 :
257 0 : const Float DIST_MARGIN = 0.1f;
258 0 : if (mType == SINGLE_CURVE_AND_RADIUS) {
259 0 : r = mR0;
260 :
261 0 : expectedDist = (r + mLastR) * factor;
262 :
263 : // Find C_i on the center curve.
264 0 : for (size_t i = 0; i < MAX_LOOP; i++) {
265 0 : t = (upper + lower) / 2.0f;
266 0 : C = GetBezierPoint(mCenterBezier, t);
267 :
268 : // Check overlap along arc.
269 0 : circlesDist = GetBezierLength(mCenterBezier, mLastT, t);
270 0 : if (circlesDist < expectedDist - DIST_MARGIN) {
271 0 : lower = t;
272 0 : } else if (circlesDist > expectedDist + DIST_MARGIN) {
273 0 : upper = t;
274 : } else {
275 0 : break;
276 : }
277 : }
278 0 : } else if (mType == SINGLE_CURVE) {
279 : // Find C_i on the center curve, and calculate r_i.
280 0 : for (size_t i = 0; i < MAX_LOOP; i++) {
281 0 : t = (upper + lower) / 2.0f;
282 0 : C = GetBezierPoint(mCenterBezier, t);
283 :
284 0 : Point Diff = GetBezierDifferential(mCenterBezier, t);
285 0 : Float DiffLength = Diff.Length();
286 0 : if (DiffLength == 0.0f) {
287 : // Basically this shouldn't happen.
288 : // If differential is 0, we cannot calculate tangent circle,
289 : // skip this point.
290 0 : t = (t + upper) / 2.0f;
291 0 : continue;
292 : }
293 :
294 0 : Point normal = PointRotateCCW90(Diff / DiffLength) * (-mNormalSign);
295 0 : r = CalculateDistanceToEllipticArc(C, normal, mInnerCurveOrigin,
296 : mInnerWidth, mInnerHeight);
297 :
298 : // Check overlap along arc.
299 0 : circlesDist = GetBezierLength(mCenterBezier, mLastT, t);
300 0 : expectedDist = (r + mLastR) * factor;
301 0 : if (circlesDist < expectedDist - DIST_MARGIN) {
302 0 : lower = t;
303 0 : } else if (circlesDist > expectedDist + DIST_MARGIN) {
304 0 : upper = t;
305 : } else {
306 0 : break;
307 : }
308 : }
309 : } else {
310 0 : Float distSquareMax = Square(mMaxR * 3.0f);
311 0 : Float circlesDistSquare = 0.0f;
312 :
313 : // Find C_i and r_i.
314 0 : for (size_t i = 0; i < MAX_LOOP; i++) {
315 0 : t = (upper + lower) / 2.0f;
316 0 : Point innerTangent = GetBezierPoint(mInnerBezier, t);
317 0 : if ((innerTangent - mLastC).LengthSquare() > distSquareMax) {
318 : // It's clear that this tangent point is too far, skip it.
319 0 : upper = t;
320 0 : continue;
321 : }
322 :
323 0 : Point Diff = GetBezierDifferential(mInnerBezier, t);
324 0 : Float DiffLength = Diff.Length();
325 0 : if (DiffLength == 0.0f) {
326 : // Basically this shouldn't happen.
327 : // If differential is 0, we cannot calculate tangent circle,
328 : // skip this point.
329 0 : t = (t + upper) / 2.0f;
330 0 : continue;
331 : }
332 :
333 0 : Point normal = PointRotateCCW90(Diff / DiffLength) * mNormalSign;
334 0 : FindPointAndRadius(C, r, innerTangent, normal, t);
335 :
336 : // Check overlap with direct distance.
337 0 : circlesDistSquare = (C - mLastC).LengthSquare();
338 0 : expectedDist = (r + mLastR) * factor;
339 0 : if (circlesDistSquare < Square(expectedDist - DIST_MARGIN)) {
340 0 : lower = t;
341 0 : } else if (circlesDistSquare > Square(expectedDist + DIST_MARGIN)) {
342 0 : upper = t;
343 : } else {
344 0 : break;
345 : }
346 : }
347 :
348 0 : circlesDist = sqrt(circlesDistSquare);
349 : }
350 :
351 0 : if (mHasZeroBorderWidth) {
352 : // When calculating circle around r=0, it may result in wrong radius that
353 : // is bigger than previous circle. Detect it and stop calculating.
354 0 : const Float R_MARGIN = 0.1f;
355 0 : if (mLastR < R_MARGIN && r > mLastR) {
356 0 : mHasMore = false;
357 0 : mLastR = 0.0f;
358 0 : return 0.0f;
359 : }
360 : }
361 :
362 0 : mLastT = t;
363 0 : mLastC = C;
364 0 : mLastR = r;
365 :
366 0 : if (mHasZeroBorderWidth) {
367 0 : const Float T_MARGIN = 0.001f;
368 0 : if (mLastT >= 1.0f - T_MARGIN ||
369 0 : (mLastC - mCn).LengthSquare() < Square(mLastR)) {
370 0 : mHasMore = false;
371 : }
372 : }
373 :
374 0 : if (expectedDist == 0.0f) {
375 0 : return 0.0f;
376 : }
377 :
378 0 : return 1.0f - circlesDist * factor / expectedDist;
379 : }
380 :
381 : void
382 0 : DottedCornerFinder::FindBestOverlap(Float aMinR, Float aMinBorderRadius,
383 : Float aMaxBorderRadius)
384 : {
385 : // If overlap is not calculateable, find it with binary search,
386 : // such that there exists i that C_i == C_n with the given overlap.
387 :
388 : FourFloats key(aMinR, mMaxR,
389 0 : aMinBorderRadius, aMaxBorderRadius);
390 0 : BestOverlap best;
391 0 : if (DottedCornerCache.Get(key, &best)) {
392 0 : mCount = best.count;
393 0 : mBestOverlap = best.overlap;
394 0 : return;
395 : }
396 :
397 0 : Float lower = 0.0f;
398 0 : Float upper = 0.5f;
399 : // Start from lower bound to find the minimum number of circles.
400 0 : Float overlap = 0.0f;
401 0 : mBestOverlap = overlap;
402 0 : size_t targetCount = 0;
403 :
404 0 : const Float OVERLAP_MARGIN = 0.1f;
405 0 : for (size_t j = 0; j < MAX_LOOP; j++) {
406 0 : Reset();
407 :
408 : size_t count;
409 : Float actualOverlap;
410 0 : if (!GetCountAndLastOverlap(overlap, &count, &actualOverlap)) {
411 0 : if (j == 0) {
412 0 : mCount = mMaxCount;
413 0 : break;
414 : }
415 : }
416 :
417 0 : if (j == 0) {
418 0 : if (count < 3 || (count == 3 && actualOverlap > 0.5f)) {
419 : // |count == 3 && actualOverlap > 0.5f| means there could be
420 : // a circle but it is too near from both ends.
421 : //
422 : // if actualOverlap == 0.0
423 : // 1 2 3
424 : // +-------+-------+-------+-------+
425 : // | ##### | ***** | ##### | ##### |
426 : // |#######|*******|#######|#######|
427 : // |###+###|***+***|###+###|###+###|
428 : // |# C_0 #|* C_1 *|# C_2 #|# C_n #|
429 : // | ##### | ***** | ##### | ##### |
430 : // +-------+-------+-------+-------+
431 : // |
432 : // V
433 : // +-------+---+-------+---+-------+
434 : // | ##### | | ##### | | ##### |
435 : // |#######| |#######| |#######|
436 : // |###+###| |###+###| |###+###| Find the best overlap to place
437 : // |# C_0 #| |# C_1 #| |# C_n #| C_1 at the middle of them
438 : // | ##### | | ##### | | ##### |
439 : // +-------+---+-------+---|-------+
440 : //
441 : // if actualOverlap == 0.5
442 : // 1 2 3
443 : // +-------+-------+-------+---+
444 : // | ##### | ***** | ##### |## |
445 : // |#######|*******|##### C_n #|
446 : // |###+###|***+***|###+###+###|
447 : // |# C_0 #|* C_1 *|# C_2 #|###|
448 : // | ##### | ***** | ##### |## |
449 : // +-------+-------+-------+---+
450 : // |
451 : // V
452 : // +-------+-+-------+-+-------+
453 : // | ##### | | ##### | | ##### |
454 : // |#######| |#######| |#######|
455 : // |###+###| |###+###| |###+###| Even if we place C_1 at the middle
456 : // |# C_0 #| |# C_1 #| |# C_n #| of them, it's too near from them
457 : // | ##### | | ##### | | ##### |
458 : // +-------+-+-------+-|-------+
459 : // |
460 : // V
461 : // +-------+-----------+-------+
462 : // | ##### | | ##### |
463 : // |#######| |#######|
464 : // |###+###| |###+###| Do not draw any circle
465 : // |# C_0 #| |# C_n #|
466 : // | ##### | | ##### |
467 : // +-------+-----------+-------+
468 0 : mCount = 0;
469 0 : break;
470 : }
471 :
472 : // targetCount should be 2n, as we're searching C_1 to C_n.
473 : //
474 : // targetCount = 4
475 : // mCount = 1
476 : // 1 2 3 4
477 : // +-------+-------+-------+-------+-------+
478 : // | ##### | ***** | ##### | ***** | ##### |
479 : // |#######|*******|#######|*******|#######|
480 : // |###+###|***+***|###+###|***+***|###+###|
481 : // |# C_0 #|* C_1 *|# C_2 #|* C_3 *|# C_n #|
482 : // | ##### | ***** | ##### | ***** | ##### |
483 : // +-------+-------+-------+-------+-------+
484 : // 1
485 : //
486 : // targetCount = 6
487 : // mCount = 2
488 : // 1 2 3 4 5 6
489 : // +-------+-------+-------+-------+-------+-------+-------+
490 : // | ##### | ***** | ##### | ***** | ##### | ***** | ##### |
491 : // |#######|*******|#######|*******|#######|*******|#######|
492 : // |###+###|***+***|###+###|***+***|###+###|***+***|###+###|
493 : // |# C_0 #|* C_1 *|# C_2 #|* C_3 *|# C_4 #|* C_5 *|# C_n #|
494 : // | ##### | ***** | ##### | ***** | ##### | ***** | ##### |
495 : // +-------+-------+-------+-------+-------+-------+-------+
496 : // 1 2
497 0 : if (count % 2) {
498 0 : targetCount = count + 1;
499 : } else {
500 0 : targetCount = count;
501 : }
502 :
503 0 : mCount = targetCount / 2 - 1;
504 : }
505 :
506 0 : if (count == targetCount) {
507 0 : mBestOverlap = overlap;
508 :
509 0 : if (fabs(actualOverlap - overlap) < OVERLAP_MARGIN) {
510 0 : break;
511 : }
512 :
513 : // We started from upper bound, no need to update range when j == 0.
514 0 : if (j > 0) {
515 0 : if (actualOverlap > overlap) {
516 0 : lower = overlap;
517 : } else {
518 0 : upper = overlap;
519 : }
520 : }
521 : } else {
522 : // |j == 0 && count != targetCount| means that |targetCount = count + 1|,
523 : // and we started from upper bound, no need to update range when j == 0.
524 0 : if (j > 0) {
525 0 : if (count > targetCount) {
526 0 : upper = overlap;
527 : } else {
528 0 : lower = overlap;
529 : }
530 : }
531 : }
532 :
533 0 : overlap = (upper + lower) / 2.0f;
534 : }
535 :
536 0 : if (DottedCornerCache.Count() > DottedCornerCacheSize) {
537 0 : DottedCornerCache.Clear();
538 : }
539 0 : DottedCornerCache.Put(key, BestOverlap(mBestOverlap, mCount));
540 : }
541 :
542 : bool
543 0 : DottedCornerFinder::GetCountAndLastOverlap(Float aOverlap,
544 : size_t* aCount,
545 : Float* aActualOverlap)
546 : {
547 : // Return the number of circles and the last circles' overlap for the
548 : // given overlap.
549 :
550 0 : Reset();
551 :
552 0 : const Float T_MARGIN = 0.001f;
553 0 : const Float DIST_MARGIN = 0.1f;
554 0 : const Float DIST_MARGIN_SQUARE = Square(DIST_MARGIN);
555 0 : for (size_t i = 0; i < mMaxCount; i++) {
556 0 : Float actualOverlap = FindNext(aOverlap);
557 0 : if (mLastT >= 1.0f - T_MARGIN ||
558 0 : (mLastC - mCn).LengthSquare() < DIST_MARGIN_SQUARE) {
559 0 : *aCount = i + 1;
560 0 : *aActualOverlap = actualOverlap;
561 0 : return true;
562 : }
563 : }
564 :
565 0 : return false;
566 : }
567 :
568 : } // namespace mozilla
|
