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