1/*
2 * Copyright 2012 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "SkRRect.h"
9#include "SkMatrix.h"
10
11///////////////////////////////////////////////////////////////////////////////
12
13void SkRRect::setRectXY(const SkRect& rect, SkScalar xRad, SkScalar yRad) {
14    if (rect.isEmpty() || !rect.isFinite()) {
15        this->setEmpty();
16        return;
17    }
18
19    if (!SkScalarsAreFinite(xRad, yRad)) {
20        xRad = yRad = 0;    // devolve into a simple rect
21    }
22    if (xRad <= 0 || yRad <= 0) {
23        // all corners are square in this case
24        this->setRect(rect);
25        return;
26    }
27
28    if (rect.width() < xRad+xRad || rect.height() < yRad+yRad) {
29        SkScalar scale = SkMinScalar(rect.width() / (xRad + xRad), rect.height() / (yRad + yRad));
30        SkASSERT(scale < SK_Scalar1);
31        xRad = SkScalarMul(xRad, scale);
32        yRad = SkScalarMul(yRad, scale);
33    }
34
35    fRect = rect;
36    for (int i = 0; i < 4; ++i) {
37        fRadii[i].set(xRad, yRad);
38    }
39    fType = kSimple_Type;
40    if (xRad >= SkScalarHalf(fRect.width()) && yRad >= SkScalarHalf(fRect.height())) {
41        fType = kOval_Type;
42        // TODO: assert that all the x&y radii are already W/2 & H/2
43    }
44
45    SkDEBUGCODE(this->validate();)
46}
47
48void SkRRect::setNinePatch(const SkRect& rect, SkScalar leftRad, SkScalar topRad,
49                           SkScalar rightRad, SkScalar bottomRad) {
50    if (rect.isEmpty() || !rect.isFinite()) {
51        this->setEmpty();
52        return;
53    }
54
55    const SkScalar array[4] = { leftRad, topRad, rightRad, bottomRad };
56    if (!SkScalarsAreFinite(array, 4)) {
57        this->setRect(rect);    // devolve into a simple rect
58        return;
59    }
60
61    leftRad = SkMaxScalar(leftRad, 0);
62    topRad = SkMaxScalar(topRad, 0);
63    rightRad = SkMaxScalar(rightRad, 0);
64    bottomRad = SkMaxScalar(bottomRad, 0);
65
66    SkScalar scale = SK_Scalar1;
67    if (leftRad + rightRad > rect.width()) {
68        scale = rect.width() / (leftRad + rightRad);
69    }
70    if (topRad + bottomRad > rect.height()) {
71        scale = SkMinScalar(scale, rect.height() / (topRad + bottomRad));
72    }
73
74    if (scale < SK_Scalar1) {
75        leftRad = SkScalarMul(leftRad, scale);
76        topRad = SkScalarMul(topRad, scale);
77        rightRad = SkScalarMul(rightRad, scale);
78        bottomRad = SkScalarMul(bottomRad, scale);
79    }
80
81    if (leftRad == rightRad && topRad == bottomRad) {
82        if (leftRad >= SkScalarHalf(rect.width()) && topRad >= SkScalarHalf(rect.height())) {
83            fType = kOval_Type;
84        } else if (0 == leftRad || 0 == topRad) {
85            // If the left and (by equality check above) right radii are zero then it is a rect.
86            // Same goes for top/bottom.
87            fType = kRect_Type;
88            leftRad = 0;
89            topRad = 0;
90            rightRad = 0;
91            bottomRad = 0;
92        } else {
93            fType = kSimple_Type;
94        }
95    } else {
96        fType = kNinePatch_Type;
97    }
98
99    fRect = rect;
100    fRadii[kUpperLeft_Corner].set(leftRad, topRad);
101    fRadii[kUpperRight_Corner].set(rightRad, topRad);
102    fRadii[kLowerRight_Corner].set(rightRad, bottomRad);
103    fRadii[kLowerLeft_Corner].set(leftRad, bottomRad);
104
105    SkDEBUGCODE(this->validate();)
106}
107
108/*
109 *  TODO: clean this guy up and possibly add to SkScalar.h
110 */
111static inline SkScalar SkScalarDecULP(SkScalar value) {
112#if SK_SCALAR_IS_FLOAT
113        return SkBits2Float(SkFloat2Bits(value) - 1);
114#else
115    #error "need impl for doubles"
116#endif
117}
118
119 /**
120 *  We need all combinations of predicates to be true to have a "safe" radius value.
121 */
122static SkScalar clamp_radius_check_predicates(SkScalar rad, SkScalar min, SkScalar max) {
123    SkASSERT(min < max);
124    if (rad > max - min || min + rad > max || max - rad < min) {
125        rad = SkScalarDecULP(rad);
126    }
127    return rad;
128}
129
130// These parameters intentionally double. Apropos crbug.com/463920, if one of the
131// radii is huge while the other is small, single precision math can completely
132// miss the fact that a scale is required.
133static double compute_min_scale(double rad1, double rad2, double limit, double curMin) {
134    if ((rad1 + rad2) > limit) {
135        return SkTMin(curMin, limit / (rad1 + rad2));
136    }
137    return curMin;
138}
139
140void SkRRect::setRectRadii(const SkRect& rect, const SkVector radii[4]) {
141    if (rect.isEmpty() || !rect.isFinite()) {
142        this->setEmpty();
143        return;
144    }
145
146    if (!SkScalarsAreFinite(&radii[0].fX, 8)) {
147        this->setRect(rect);    // devolve into a simple rect
148        return;
149    }
150
151    fRect = rect;
152    memcpy(fRadii, radii, sizeof(fRadii));
153
154    bool allCornersSquare = true;
155
156    // Clamp negative radii to zero
157    for (int i = 0; i < 4; ++i) {
158        if (fRadii[i].fX <= 0 || fRadii[i].fY <= 0) {
159            // In this case we are being a little fast & loose. Since one of
160            // the radii is 0 the corner is square. However, the other radii
161            // could still be non-zero and play in the global scale factor
162            // computation.
163            fRadii[i].fX = 0;
164            fRadii[i].fY = 0;
165        } else {
166            allCornersSquare = false;
167        }
168    }
169
170    if (allCornersSquare) {
171        this->setRect(rect);
172        return;
173    }
174
175    // Proportionally scale down all radii to fit. Find the minimum ratio
176    // of a side and the radii on that side (for all four sides) and use
177    // that to scale down _all_ the radii. This algorithm is from the
178    // W3 spec (http://www.w3.org/TR/css3-background/) section 5.5 - Overlapping
179    // Curves:
180    // "Let f = min(Li/Si), where i is one of { top, right, bottom, left },
181    //   Si is the sum of the two corresponding radii of the corners on side i,
182    //   and Ltop = Lbottom = the width of the box,
183    //   and Lleft = Lright = the height of the box.
184    // If f < 1, then all corner radii are reduced by multiplying them by f."
185    double scale = 1.0;
186
187    scale = compute_min_scale(fRadii[0].fX, fRadii[1].fX, rect.width(),  scale);
188    scale = compute_min_scale(fRadii[1].fY, fRadii[2].fY, rect.height(), scale);
189    scale = compute_min_scale(fRadii[2].fX, fRadii[3].fX, rect.width(),  scale);
190    scale = compute_min_scale(fRadii[3].fY, fRadii[0].fY, rect.height(), scale);
191
192    if (scale < 1.0) {
193        for (int i = 0; i < 4; ++i) {
194            fRadii[i].fX *= scale;
195            fRadii[i].fY *= scale;
196        }
197    }
198
199    // skbug.com/3239 -- its possible that we can hit the following inconsistency:
200    //     rad == bounds.bottom - bounds.top
201    //     bounds.bottom - radius < bounds.top
202    //     YIKES
203    // We need to detect and "fix" this now, otherwise we can have the following wackiness:
204    //     path.addRRect(rrect);
205    //     rrect.rect() != path.getBounds()
206    for (int i = 0; i < 4; ++i) {
207        fRadii[i].fX = clamp_radius_check_predicates(fRadii[i].fX, rect.fLeft, rect.fRight);
208        fRadii[i].fY = clamp_radius_check_predicates(fRadii[i].fY, rect.fTop, rect.fBottom);
209    }
210    // At this point we're either oval, simple, or complex (not empty or rect).
211    this->computeType();
212
213    SkDEBUGCODE(this->validate();)
214}
215
216// This method determines if a point known to be inside the RRect's bounds is
217// inside all the corners.
218bool SkRRect::checkCornerContainment(SkScalar x, SkScalar y) const {
219    SkPoint canonicalPt; // (x,y) translated to one of the quadrants
220    int index;
221
222    if (kOval_Type == this->type()) {
223        canonicalPt.set(x - fRect.centerX(), y - fRect.centerY());
224        index = kUpperLeft_Corner;  // any corner will do in this case
225    } else {
226        if (x < fRect.fLeft + fRadii[kUpperLeft_Corner].fX &&
227            y < fRect.fTop + fRadii[kUpperLeft_Corner].fY) {
228            // UL corner
229            index = kUpperLeft_Corner;
230            canonicalPt.set(x - (fRect.fLeft + fRadii[kUpperLeft_Corner].fX),
231                            y - (fRect.fTop + fRadii[kUpperLeft_Corner].fY));
232            SkASSERT(canonicalPt.fX < 0 && canonicalPt.fY < 0);
233        } else if (x < fRect.fLeft + fRadii[kLowerLeft_Corner].fX &&
234                   y > fRect.fBottom - fRadii[kLowerLeft_Corner].fY) {
235            // LL corner
236            index = kLowerLeft_Corner;
237            canonicalPt.set(x - (fRect.fLeft + fRadii[kLowerLeft_Corner].fX),
238                            y - (fRect.fBottom - fRadii[kLowerLeft_Corner].fY));
239            SkASSERT(canonicalPt.fX < 0 && canonicalPt.fY > 0);
240        } else if (x > fRect.fRight - fRadii[kUpperRight_Corner].fX &&
241                   y < fRect.fTop + fRadii[kUpperRight_Corner].fY) {
242            // UR corner
243            index = kUpperRight_Corner;
244            canonicalPt.set(x - (fRect.fRight - fRadii[kUpperRight_Corner].fX),
245                            y - (fRect.fTop + fRadii[kUpperRight_Corner].fY));
246            SkASSERT(canonicalPt.fX > 0 && canonicalPt.fY < 0);
247        } else if (x > fRect.fRight - fRadii[kLowerRight_Corner].fX &&
248                   y > fRect.fBottom - fRadii[kLowerRight_Corner].fY) {
249            // LR corner
250            index = kLowerRight_Corner;
251            canonicalPt.set(x - (fRect.fRight - fRadii[kLowerRight_Corner].fX),
252                            y - (fRect.fBottom - fRadii[kLowerRight_Corner].fY));
253            SkASSERT(canonicalPt.fX > 0 && canonicalPt.fY > 0);
254        } else {
255            // not in any of the corners
256            return true;
257        }
258    }
259
260    // A point is in an ellipse (in standard position) if:
261    //      x^2     y^2
262    //     ----- + ----- <= 1
263    //      a^2     b^2
264    // or :
265    //     b^2*x^2 + a^2*y^2 <= (ab)^2
266    SkScalar dist =  SkScalarMul(SkScalarSquare(canonicalPt.fX), SkScalarSquare(fRadii[index].fY)) +
267                     SkScalarMul(SkScalarSquare(canonicalPt.fY), SkScalarSquare(fRadii[index].fX));
268    return dist <= SkScalarSquare(SkScalarMul(fRadii[index].fX, fRadii[index].fY));
269}
270
271bool SkRRect::allCornersCircular() const {
272    return fRadii[0].fX == fRadii[0].fY &&
273        fRadii[1].fX == fRadii[1].fY &&
274        fRadii[2].fX == fRadii[2].fY &&
275        fRadii[3].fX == fRadii[3].fY;
276}
277
278bool SkRRect::contains(const SkRect& rect) const {
279    if (!this->getBounds().contains(rect)) {
280        // If 'rect' isn't contained by the RR's bounds then the
281        // RR definitely doesn't contain it
282        return false;
283    }
284
285    if (this->isRect()) {
286        // the prior test was sufficient
287        return true;
288    }
289
290    // At this point we know all four corners of 'rect' are inside the
291    // bounds of of this RR. Check to make sure all the corners are inside
292    // all the curves
293    return this->checkCornerContainment(rect.fLeft, rect.fTop) &&
294           this->checkCornerContainment(rect.fRight, rect.fTop) &&
295           this->checkCornerContainment(rect.fRight, rect.fBottom) &&
296           this->checkCornerContainment(rect.fLeft, rect.fBottom);
297}
298
299static bool radii_are_nine_patch(const SkVector radii[4]) {
300    return radii[SkRRect::kUpperLeft_Corner].fX == radii[SkRRect::kLowerLeft_Corner].fX &&
301           radii[SkRRect::kUpperLeft_Corner].fY == radii[SkRRect::kUpperRight_Corner].fY &&
302           radii[SkRRect::kUpperRight_Corner].fX == radii[SkRRect::kLowerRight_Corner].fX &&
303           radii[SkRRect::kLowerLeft_Corner].fY == radii[SkRRect::kLowerRight_Corner].fY;
304}
305
306// There is a simplified version of this method in setRectXY
307void SkRRect::computeType() {
308    struct Validator {
309        Validator(const SkRRect* r) : fR(r) {}
310        ~Validator() { SkDEBUGCODE(fR->validate();) }
311        const SkRRect* fR;
312    } autoValidate(this);
313
314    if (fRect.isEmpty()) {
315        fType = kEmpty_Type;
316        return;
317    }
318
319    bool allRadiiEqual = true; // are all x radii equal and all y radii?
320    bool allCornersSquare = 0 == fRadii[0].fX || 0 == fRadii[0].fY;
321
322    for (int i = 1; i < 4; ++i) {
323        if (0 != fRadii[i].fX && 0 != fRadii[i].fY) {
324            // if either radius is zero the corner is square so both have to
325            // be non-zero to have a rounded corner
326            allCornersSquare = false;
327        }
328        if (fRadii[i].fX != fRadii[i-1].fX || fRadii[i].fY != fRadii[i-1].fY) {
329            allRadiiEqual = false;
330        }
331    }
332
333    if (allCornersSquare) {
334        fType = kRect_Type;
335        return;
336    }
337
338    if (allRadiiEqual) {
339        if (fRadii[0].fX >= SkScalarHalf(fRect.width()) &&
340            fRadii[0].fY >= SkScalarHalf(fRect.height())) {
341            fType = kOval_Type;
342        } else {
343            fType = kSimple_Type;
344        }
345        return;
346    }
347
348    if (radii_are_nine_patch(fRadii)) {
349        fType = kNinePatch_Type;
350    } else {
351        fType = kComplex_Type;
352    }
353}
354
355static bool matrix_only_scale_and_translate(const SkMatrix& matrix) {
356    const SkMatrix::TypeMask m = (SkMatrix::TypeMask) (SkMatrix::kAffine_Mask
357                                    | SkMatrix::kPerspective_Mask);
358    return (matrix.getType() & m) == 0;
359}
360
361bool SkRRect::transform(const SkMatrix& matrix, SkRRect* dst) const {
362    if (NULL == dst) {
363        return false;
364    }
365
366    // Assert that the caller is not trying to do this in place, which
367    // would violate const-ness. Do not return false though, so that
368    // if they know what they're doing and want to violate it they can.
369    SkASSERT(dst != this);
370
371    if (matrix.isIdentity()) {
372        *dst = *this;
373        return true;
374    }
375
376    // If transform supported 90 degree rotations (which it could), we could
377    // use SkMatrix::rectStaysRect() to check for a valid transformation.
378    if (!matrix_only_scale_and_translate(matrix)) {
379        return false;
380    }
381
382    SkRect newRect;
383    if (!matrix.mapRect(&newRect, fRect)) {
384        return false;
385    }
386
387    // The matrix may have scaled us to zero (or due to float madness, we now have collapsed
388    // some dimension of the rect, so we need to check for that.
389    if (newRect.isEmpty()) {
390        dst->setEmpty();
391        return true;
392    }
393
394    // At this point, this is guaranteed to succeed, so we can modify dst.
395    dst->fRect = newRect;
396
397    // Since the only transforms that were allowed are scale and translate, the type
398    // remains unchanged.
399    dst->fType = fType;
400
401    if (kOval_Type == fType) {
402        for (int i = 0; i < 4; ++i) {
403            dst->fRadii[i].fX = SkScalarHalf(newRect.width());
404            dst->fRadii[i].fY = SkScalarHalf(newRect.height());
405        }
406        SkDEBUGCODE(dst->validate();)
407        return true;
408    }
409
410    // Now scale each corner
411    SkScalar xScale = matrix.getScaleX();
412    const bool flipX = xScale < 0;
413    if (flipX) {
414        xScale = -xScale;
415    }
416    SkScalar yScale = matrix.getScaleY();
417    const bool flipY = yScale < 0;
418    if (flipY) {
419        yScale = -yScale;
420    }
421
422    // Scale the radii without respecting the flip.
423    for (int i = 0; i < 4; ++i) {
424        dst->fRadii[i].fX = SkScalarMul(fRadii[i].fX, xScale);
425        dst->fRadii[i].fY = SkScalarMul(fRadii[i].fY, yScale);
426    }
427
428    // Now swap as necessary.
429    if (flipX) {
430        if (flipY) {
431            // Swap with opposite corners
432            SkTSwap(dst->fRadii[kUpperLeft_Corner], dst->fRadii[kLowerRight_Corner]);
433            SkTSwap(dst->fRadii[kUpperRight_Corner], dst->fRadii[kLowerLeft_Corner]);
434        } else {
435            // Only swap in x
436            SkTSwap(dst->fRadii[kUpperRight_Corner], dst->fRadii[kUpperLeft_Corner]);
437            SkTSwap(dst->fRadii[kLowerRight_Corner], dst->fRadii[kLowerLeft_Corner]);
438        }
439    } else if (flipY) {
440        // Only swap in y
441        SkTSwap(dst->fRadii[kUpperLeft_Corner], dst->fRadii[kLowerLeft_Corner]);
442        SkTSwap(dst->fRadii[kUpperRight_Corner], dst->fRadii[kLowerRight_Corner]);
443    }
444
445    SkDEBUGCODE(dst->validate();)
446
447    return true;
448}
449
450///////////////////////////////////////////////////////////////////////////////
451
452void SkRRect::inset(SkScalar dx, SkScalar dy, SkRRect* dst) const {
453    const SkRect r = fRect.makeInset(dx, dy);
454
455    if (r.isEmpty()) {
456        dst->setEmpty();
457        return;
458    }
459
460    SkVector radii[4];
461    memcpy(radii, fRadii, sizeof(radii));
462    for (int i = 0; i < 4; ++i) {
463        if (radii[i].fX) {
464            radii[i].fX -= dx;
465        }
466        if (radii[i].fY) {
467            radii[i].fY -= dy;
468        }
469    }
470    dst->setRectRadii(r, radii);
471}
472
473///////////////////////////////////////////////////////////////////////////////
474
475size_t SkRRect::writeToMemory(void* buffer) const {
476    SkASSERT(kSizeInMemory == sizeof(SkRect) + sizeof(fRadii));
477
478    memcpy(buffer, &fRect, sizeof(SkRect));
479    memcpy((char*)buffer + sizeof(SkRect), fRadii, sizeof(fRadii));
480    return kSizeInMemory;
481}
482
483size_t SkRRect::readFromMemory(const void* buffer, size_t length) {
484    if (length < kSizeInMemory) {
485        return 0;
486    }
487
488    SkScalar storage[12];
489    SkASSERT(sizeof(storage) == kSizeInMemory);
490
491    // we make a local copy, to ensure alignment before we cast
492    memcpy(storage, buffer, kSizeInMemory);
493
494    this->setRectRadii(*(const SkRect*)&storage[0],
495                       (const SkVector*)&storage[4]);
496    return kSizeInMemory;
497}
498
499#include "SkString.h"
500#include "SkStringUtils.h"
501
502void SkRRect::dump(bool asHex) const {
503    SkScalarAsStringType asType = asHex ? kHex_SkScalarAsStringType : kDec_SkScalarAsStringType;
504
505    fRect.dump(asHex);
506    SkString line("const SkPoint corners[] = {\n");
507    for (int i = 0; i < 4; ++i) {
508        SkString strX, strY;
509        SkAppendScalar(&strX, fRadii[i].x(), asType);
510        SkAppendScalar(&strY, fRadii[i].y(), asType);
511        line.appendf("    { %s, %s },", strX.c_str(), strY.c_str());
512        if (asHex) {
513            line.appendf(" /* %f %f */", fRadii[i].x(), fRadii[i].y());
514        }
515        line.append("\n");
516    }
517    line.append("};");
518    SkDebugf("%s\n", line.c_str());
519}
520
521///////////////////////////////////////////////////////////////////////////////
522
523#ifdef SK_DEBUG
524/**
525 *  We need all combinations of predicates to be true to have a "safe" radius value.
526 */
527static void validate_radius_check_predicates(SkScalar rad, SkScalar min, SkScalar max) {
528    SkASSERT(min <= max);
529    SkASSERT(rad <= max - min);
530    SkASSERT(min + rad <= max);
531    SkASSERT(max - rad >= min);
532}
533
534void SkRRect::validate() const {
535    bool allRadiiZero = (0 == fRadii[0].fX && 0 == fRadii[0].fY);
536    bool allCornersSquare = (0 == fRadii[0].fX || 0 == fRadii[0].fY);
537    bool allRadiiSame = true;
538
539    for (int i = 1; i < 4; ++i) {
540        if (0 != fRadii[i].fX || 0 != fRadii[i].fY) {
541            allRadiiZero = false;
542        }
543
544        if (fRadii[i].fX != fRadii[i-1].fX || fRadii[i].fY != fRadii[i-1].fY) {
545            allRadiiSame = false;
546        }
547
548        if (0 != fRadii[i].fX && 0 != fRadii[i].fY) {
549            allCornersSquare = false;
550        }
551    }
552    bool patchesOfNine = radii_are_nine_patch(fRadii);
553
554    switch (fType) {
555        case kEmpty_Type:
556            SkASSERT(fRect.isEmpty());
557            SkASSERT(allRadiiZero && allRadiiSame && allCornersSquare);
558            break;
559        case kRect_Type:
560            SkASSERT(!fRect.isEmpty());
561            SkASSERT(allRadiiZero && allRadiiSame && allCornersSquare);
562            break;
563        case kOval_Type:
564            SkASSERT(!fRect.isEmpty());
565            SkASSERT(!allRadiiZero && allRadiiSame && !allCornersSquare);
566
567            for (int i = 0; i < 4; ++i) {
568                SkASSERT(SkScalarNearlyEqual(fRadii[i].fX, SkScalarHalf(fRect.width())));
569                SkASSERT(SkScalarNearlyEqual(fRadii[i].fY, SkScalarHalf(fRect.height())));
570            }
571            break;
572        case kSimple_Type:
573            SkASSERT(!fRect.isEmpty());
574            SkASSERT(!allRadiiZero && allRadiiSame && !allCornersSquare);
575            break;
576        case kNinePatch_Type:
577            SkASSERT(!fRect.isEmpty());
578            SkASSERT(!allRadiiZero && !allRadiiSame && !allCornersSquare);
579            SkASSERT(patchesOfNine);
580            break;
581        case kComplex_Type:
582            SkASSERT(!fRect.isEmpty());
583            SkASSERT(!allRadiiZero && !allRadiiSame && !allCornersSquare);
584            SkASSERT(!patchesOfNine);
585            break;
586    }
587
588    for (int i = 0; i < 4; ++i) {
589        validate_radius_check_predicates(fRadii[i].fX, fRect.fLeft, fRect.fRight);
590        validate_radius_check_predicates(fRadii[i].fY, fRect.fTop, fRect.fBottom);
591    }
592}
593#endif // SK_DEBUG
594
595///////////////////////////////////////////////////////////////////////////////
596