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 #include "DashedCornerFinder.h"
8
9 #include <utility>
10
11 #include "BorderCache.h"
12 #include "BorderConsts.h"
13
14 namespace mozilla {
15
16 using namespace gfx;
17
18 struct BestDashLength {
19 typedef mozilla::gfx::Float Float;
20
21 Float dashLength;
22 size_t count;
23
BestDashLengthmozilla::BestDashLength24 BestDashLength() : dashLength(0.0f), count(0) {}
25
BestDashLengthmozilla::BestDashLength26 BestDashLength(Float aDashLength, size_t aCount)
27 : dashLength(aDashLength), count(aCount) {}
28 };
29
30 static const size_t DashedCornerCacheSize = 256;
31 nsTHashMap<FourFloatsHashKey, BestDashLength> DashedCornerCache;
32
DashedCornerFinder(const Bezier & aOuterBezier,const Bezier & aInnerBezier,Float aBorderWidthH,Float aBorderWidthV,const Size & aCornerDim)33 DashedCornerFinder::DashedCornerFinder(const Bezier& aOuterBezier,
34 const Bezier& aInnerBezier,
35 Float aBorderWidthH, Float aBorderWidthV,
36 const Size& aCornerDim)
37 : mOuterBezier(aOuterBezier),
38 mInnerBezier(aInnerBezier),
39 mLastOuterP(aOuterBezier.mPoints[0]),
40 mLastInnerP(aInnerBezier.mPoints[0]),
41 mLastOuterT(0.0f),
42 mLastInnerT(0.0f),
43 mBestDashLength(DOT_LENGTH * DASH_LENGTH),
44 mHasZeroBorderWidth(false),
45 mHasMore(true),
46 mMaxCount(aCornerDim.width + aCornerDim.height),
47 mType(OTHER),
48 mI(0),
49 mCount(0) {
50 NS_ASSERTION(aBorderWidthH > 0.0f || aBorderWidthV > 0.0f,
51 "At least one side should have non-zero width.");
52
53 DetermineType(aBorderWidthH, aBorderWidthV);
54
55 Reset();
56 }
57
DetermineType(Float aBorderWidthH,Float aBorderWidthV)58 void DashedCornerFinder::DetermineType(Float aBorderWidthH,
59 Float aBorderWidthV) {
60 if (aBorderWidthH < aBorderWidthV) {
61 // Always draw from wider side to thinner side.
62 std::swap(mInnerBezier.mPoints[0], mInnerBezier.mPoints[3]);
63 std::swap(mInnerBezier.mPoints[1], mInnerBezier.mPoints[2]);
64 std::swap(mOuterBezier.mPoints[0], mOuterBezier.mPoints[3]);
65 std::swap(mOuterBezier.mPoints[1], mOuterBezier.mPoints[2]);
66 mLastOuterP = mOuterBezier.mPoints[0];
67 mLastInnerP = mInnerBezier.mPoints[0];
68 }
69
70 // See the comment at mType declaration for each condition.
71
72 Float borderRadiusA =
73 fabs(mOuterBezier.mPoints[0].x - mOuterBezier.mPoints[3].x);
74 Float borderRadiusB =
75 fabs(mOuterBezier.mPoints[0].y - mOuterBezier.mPoints[3].y);
76 if (aBorderWidthH == aBorderWidthV && borderRadiusA == borderRadiusB &&
77 borderRadiusA > aBorderWidthH * 2.0f) {
78 Float curveHeight = borderRadiusA - aBorderWidthH / 2.0;
79
80 mType = PERFECT;
81 Float borderLength = M_PI * curveHeight / 2.0f;
82
83 Float dashWidth = aBorderWidthH * DOT_LENGTH * DASH_LENGTH;
84 size_t count = ceil(borderLength / dashWidth);
85 if (count % 2) {
86 count++;
87 }
88 mCount = count / 2 + 1;
89 mBestDashLength = borderLength / (aBorderWidthH * count);
90 }
91
92 Float minBorderWidth = std::min(aBorderWidthH, aBorderWidthV);
93 if (minBorderWidth == 0.0f) {
94 mHasZeroBorderWidth = true;
95 }
96
97 if (mType == OTHER && !mHasZeroBorderWidth) {
98 Float minBorderRadius = std::min(borderRadiusA, borderRadiusB);
99 Float maxBorderRadius = std::max(borderRadiusA, borderRadiusB);
100 Float maxBorderWidth = std::max(aBorderWidthH, aBorderWidthV);
101
102 FindBestDashLength(minBorderWidth, maxBorderWidth, minBorderRadius,
103 maxBorderRadius);
104 }
105 }
106
HasMore(void) const107 bool DashedCornerFinder::HasMore(void) const {
108 if (mHasZeroBorderWidth) {
109 return mI < mMaxCount && mHasMore;
110 }
111
112 return mI < mCount;
113 }
114
Next(void)115 DashedCornerFinder::Result DashedCornerFinder::Next(void) {
116 Float lastOuterT, lastInnerT, outerT, innerT;
117
118 if (mI == 0) {
119 lastOuterT = 0.0f;
120 lastInnerT = 0.0f;
121 } else {
122 if (mType == PERFECT) {
123 lastOuterT = lastInnerT = (mI * 2.0f - 0.5f) / ((mCount - 1) * 2.0f);
124 } else {
125 Float last2OuterT = mLastOuterT;
126 Float last2InnerT = mLastInnerT;
127
128 (void)FindNext(mBestDashLength);
129
130 //
131 // mLastOuterT lastOuterT
132 // | |
133 // v v
134 // +---+---+---+---+ <- last2OuterT
135 // | |###|###| |
136 // | |###|###| |
137 // | |###|###| |
138 // +---+---+---+---+ <- last2InnerT
139 // ^ ^
140 // | |
141 // mLastInnerT lastInnerT
142 lastOuterT = (mLastOuterT + last2OuterT) / 2.0f;
143 lastInnerT = (mLastInnerT + last2InnerT) / 2.0f;
144 }
145 }
146
147 if ((!mHasZeroBorderWidth && mI == mCount - 1) ||
148 (mHasZeroBorderWidth && !mHasMore)) {
149 outerT = 1.0f;
150 innerT = 1.0f;
151 } else {
152 if (mType == PERFECT) {
153 outerT = innerT = (mI * 2.0f + 0.5f) / ((mCount - 1) * 2.0f);
154 } else {
155 Float last2OuterT = mLastOuterT;
156 Float last2InnerT = mLastInnerT;
157
158 (void)FindNext(mBestDashLength);
159
160 //
161 // outerT last2OuterT
162 // | |
163 // v v
164 // mLastOuterT -> +---+---+---+---+
165 // | |###|###| |
166 // | |###|###| |
167 // | |###|###| |
168 // mLastInnerT -> +---+---+---+---+
169 // ^ ^
170 // | |
171 // innerT last2InnerT
172 outerT = (mLastOuterT + last2OuterT) / 2.0f;
173 innerT = (mLastInnerT + last2InnerT) / 2.0f;
174 }
175 }
176
177 mI++;
178
179 Bezier outerSectionBezier;
180 Bezier innerSectionBezier;
181 GetSubBezier(&outerSectionBezier, mOuterBezier, lastOuterT, outerT);
182 GetSubBezier(&innerSectionBezier, mInnerBezier, lastInnerT, innerT);
183 return DashedCornerFinder::Result(outerSectionBezier, innerSectionBezier);
184 }
185
Reset(void)186 void DashedCornerFinder::Reset(void) {
187 mLastOuterP = mOuterBezier.mPoints[0];
188 mLastInnerP = mInnerBezier.mPoints[0];
189 mLastOuterT = 0.0f;
190 mLastInnerT = 0.0f;
191 mHasMore = true;
192 }
193
FindNext(Float dashLength)194 Float DashedCornerFinder::FindNext(Float dashLength) {
195 Float upper = 1.0f;
196 Float lower = mLastOuterT;
197
198 Point OuterP, InnerP;
199 // Start from upper bound to check if this is the last segment.
200 Float outerT = upper;
201 Float innerT;
202 Float W = 0.0f;
203 Float L = 0.0f;
204
205 const Float LENGTH_MARGIN = 0.1f;
206 for (size_t i = 0; i < MAX_LOOP; i++) {
207 OuterP = GetBezierPoint(mOuterBezier, outerT);
208 InnerP = FindBezierNearestPoint(mInnerBezier, OuterP, outerT, &innerT);
209
210 // Calculate approximate dash length.
211 //
212 // W = (W1 + W2) / 2
213 // L = (OuterL + InnerL) / 2
214 // dashLength = L / W
215 //
216 // ____----+----____
217 // OuterP ___--- | ---___ mLastOuterP
218 // +--- | ---+
219 // | | |
220 // | | |
221 // | W | W1 |
222 // | | |
223 // W2 | | |
224 // | | ______------+
225 // | ____+---- mLastInnerP
226 // | ___---
227 // | __---
228 // +--
229 // InnerP
230 // OuterL
231 // ____---------____
232 // OuterP ___--- ---___ mLastOuterP
233 // +--- ---+
234 // | L |
235 // | ___----------______ |
236 // | __--- -----+
237 // | __-- |
238 // +-- |
239 // | InnerL ______------+
240 // | ____----- mLastInnerP
241 // | ___---
242 // | __---
243 // +--
244 // InnerP
245 Float W1 = (mLastOuterP - mLastInnerP).Length();
246 Float W2 = (OuterP - InnerP).Length();
247 Float OuterL = GetBezierLength(mOuterBezier, mLastOuterT, outerT);
248 Float InnerL = GetBezierLength(mInnerBezier, mLastInnerT, innerT);
249 W = (W1 + W2) / 2.0f;
250 L = (OuterL + InnerL) / 2.0f;
251 if (L > W * dashLength + LENGTH_MARGIN) {
252 if (i > 0) {
253 upper = outerT;
254 }
255 } else if (L < W * dashLength - LENGTH_MARGIN) {
256 if (i == 0) {
257 // This is the last segment with shorter dashLength.
258 mHasMore = false;
259 break;
260 }
261 lower = outerT;
262 } else {
263 break;
264 }
265
266 outerT = (upper + lower) / 2.0f;
267 }
268
269 mLastOuterP = OuterP;
270 mLastInnerP = InnerP;
271 mLastOuterT = outerT;
272 mLastInnerT = innerT;
273
274 if (W == 0.0f) {
275 return 1.0f;
276 }
277
278 return L / W;
279 }
280
FindBestDashLength(Float aMinBorderWidth,Float aMaxBorderWidth,Float aMinBorderRadius,Float aMaxBorderRadius)281 void DashedCornerFinder::FindBestDashLength(Float aMinBorderWidth,
282 Float aMaxBorderWidth,
283 Float aMinBorderRadius,
284 Float aMaxBorderRadius) {
285 // If dashLength is not calculateable, find it with binary search,
286 // such that there exists i that OuterP_i == OuterP_n and
287 // InnerP_i == InnerP_n with given dashLength.
288
289 FourFloats key(aMinBorderWidth, aMaxBorderWidth, aMinBorderRadius,
290 aMaxBorderRadius);
291 BestDashLength best;
292 if (DashedCornerCache.Get(key, &best)) {
293 mCount = best.count;
294 mBestDashLength = best.dashLength;
295 return;
296 }
297
298 Float lower = 1.0f;
299 Float upper = DOT_LENGTH * DASH_LENGTH;
300 Float dashLength = upper;
301 size_t targetCount = 0;
302
303 const Float LENGTH_MARGIN = 0.1f;
304 for (size_t j = 0; j < MAX_LOOP; j++) {
305 size_t count;
306 Float actualDashLength;
307 if (!GetCountAndLastDashLength(dashLength, &count, &actualDashLength)) {
308 if (j == 0) {
309 mCount = mMaxCount;
310 break;
311 }
312 }
313
314 if (j == 0) {
315 if (count == 1) {
316 // If only 1 segment fits, fill entire region
317 //
318 // count = 1
319 // mCount = 1
320 // | 1 |
321 // +---+---+
322 // |###|###|
323 // |###|###|
324 // |###|###|
325 // +---+---+
326 // 1
327 mCount = 1;
328 break;
329 }
330
331 // targetCount should be 2n.
332 //
333 // targetCount = 2
334 // mCount = 2
335 // | 1 | 2 |
336 // +---+---+---+---+
337 // |###| | |###|
338 // |###| | |###|
339 // |###| | |###|
340 // +---+---+---+---+
341 // 1 2
342 //
343 // targetCount = 6
344 // mCount = 4
345 // | 1 | 2 | 3 | 4 | 5 | 6 |
346 // +---+---+---+---+---+---+---+---+---+---+---+---+
347 // |###| | |###|###| | |###|###| | |###|
348 // |###| | |###|###| | |###|###| | |###|
349 // |###| | |###|###| | |###|###| | |###|
350 // +---+---+---+---+---+---+---+---+---+---+---+---+
351 // 1 2 3 4
352 if (count % 2) {
353 targetCount = count + 1;
354 } else {
355 targetCount = count;
356 }
357
358 mCount = targetCount / 2 + 1;
359 }
360
361 if (count == targetCount) {
362 mBestDashLength = dashLength;
363
364 // actualDashLength won't be greater than dashLength.
365 if (actualDashLength > dashLength - LENGTH_MARGIN) {
366 break;
367 }
368
369 // We started from upper bound, no need to update range when j == 0.
370 if (j > 0) {
371 upper = dashLength;
372 }
373 } else {
374 // |j == 0 && count != targetCount| means that |targetCount = count + 1|,
375 // and we started from upper bound, no need to update range when j == 0.
376 if (j > 0) {
377 if (count > targetCount) {
378 lower = dashLength;
379 } else {
380 upper = dashLength;
381 }
382 }
383 }
384
385 dashLength = (upper + lower) / 2.0f;
386 }
387
388 if (DashedCornerCache.Count() > DashedCornerCacheSize) {
389 DashedCornerCache.Clear();
390 }
391 DashedCornerCache.InsertOrUpdate(key,
392 BestDashLength(mBestDashLength, mCount));
393 }
394
GetCountAndLastDashLength(Float aDashLength,size_t * aCount,Float * aActualDashLength)395 bool DashedCornerFinder::GetCountAndLastDashLength(Float aDashLength,
396 size_t* aCount,
397 Float* aActualDashLength) {
398 // Return the number of segments and the last segment's dashLength for
399 // the given dashLength.
400
401 Reset();
402
403 for (size_t i = 0; i < mMaxCount; i++) {
404 Float actualDashLength = FindNext(aDashLength);
405 if (mLastOuterT >= 1.0f) {
406 *aCount = i + 1;
407 *aActualDashLength = actualDashLength;
408 return true;
409 }
410 }
411
412 return false;
413 }
414
415 } // namespace mozilla
416