summaryrefslogtreecommitdiffstats
path: root/gfx/skia/skia/src/core/SkRect.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'gfx/skia/skia/src/core/SkRect.cpp')
-rw-r--r--gfx/skia/skia/src/core/SkRect.cpp309
1 files changed, 309 insertions, 0 deletions
diff --git a/gfx/skia/skia/src/core/SkRect.cpp b/gfx/skia/skia/src/core/SkRect.cpp
new file mode 100644
index 0000000000..254aab27ce
--- /dev/null
+++ b/gfx/skia/skia/src/core/SkRect.cpp
@@ -0,0 +1,309 @@
+/*
+ * Copyright 2006 The Android Open Source Project
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#include "include/core/SkRect.h"
+
+#include "include/core/SkM44.h"
+#include "include/private/base/SkDebug.h"
+#include "src/core/SkRectPriv.h"
+
+class SkMatrix;
+
+bool SkIRect::intersect(const SkIRect& a, const SkIRect& b) {
+ SkIRect tmp = {
+ std::max(a.fLeft, b.fLeft),
+ std::max(a.fTop, b.fTop),
+ std::min(a.fRight, b.fRight),
+ std::min(a.fBottom, b.fBottom)
+ };
+ if (tmp.isEmpty()) {
+ return false;
+ }
+ *this = tmp;
+ return true;
+}
+
+void SkIRect::join(const SkIRect& r) {
+ // do nothing if the params are empty
+ if (r.fLeft >= r.fRight || r.fTop >= r.fBottom) {
+ return;
+ }
+
+ // if we are empty, just assign
+ if (fLeft >= fRight || fTop >= fBottom) {
+ *this = r;
+ } else {
+ if (r.fLeft < fLeft) fLeft = r.fLeft;
+ if (r.fTop < fTop) fTop = r.fTop;
+ if (r.fRight > fRight) fRight = r.fRight;
+ if (r.fBottom > fBottom) fBottom = r.fBottom;
+ }
+}
+
+/////////////////////////////////////////////////////////////////////////////
+
+void SkRect::toQuad(SkPoint quad[4]) const {
+ SkASSERT(quad);
+
+ quad[0].set(fLeft, fTop);
+ quad[1].set(fRight, fTop);
+ quad[2].set(fRight, fBottom);
+ quad[3].set(fLeft, fBottom);
+}
+
+#include "src/base/SkVx.h"
+
+bool SkRect::setBoundsCheck(const SkPoint pts[], int count) {
+ SkASSERT((pts && count > 0) || count == 0);
+
+ if (count <= 0) {
+ this->setEmpty();
+ return true;
+ }
+
+ skvx::float4 min, max;
+ if (count & 1) {
+ min = max = skvx::float2::Load(pts).xyxy();
+ pts += 1;
+ count -= 1;
+ } else {
+ min = max = skvx::float4::Load(pts);
+ pts += 2;
+ count -= 2;
+ }
+
+ skvx::float4 accum = min * 0;
+ while (count) {
+ skvx::float4 xy = skvx::float4::Load(pts);
+ accum = accum * xy;
+ min = skvx::min(min, xy);
+ max = skvx::max(max, xy);
+ pts += 2;
+ count -= 2;
+ }
+
+ const bool all_finite = all(accum * 0 == 0);
+ if (all_finite) {
+ this->setLTRB(std::min(min[0], min[2]), std::min(min[1], min[3]),
+ std::max(max[0], max[2]), std::max(max[1], max[3]));
+ } else {
+ this->setEmpty();
+ }
+ return all_finite;
+}
+
+void SkRect::setBoundsNoCheck(const SkPoint pts[], int count) {
+ if (!this->setBoundsCheck(pts, count)) {
+ this->setLTRB(SK_ScalarNaN, SK_ScalarNaN, SK_ScalarNaN, SK_ScalarNaN);
+ }
+}
+
+#define CHECK_INTERSECT(al, at, ar, ab, bl, bt, br, bb) \
+ SkScalar L = std::max(al, bl); \
+ SkScalar R = std::min(ar, br); \
+ SkScalar T = std::max(at, bt); \
+ SkScalar B = std::min(ab, bb); \
+ do { if (!(L < R && T < B)) return false; } while (0)
+ // do the !(opposite) check so we return false if either arg is NaN
+
+bool SkRect::intersect(const SkRect& r) {
+ CHECK_INTERSECT(r.fLeft, r.fTop, r.fRight, r.fBottom, fLeft, fTop, fRight, fBottom);
+ this->setLTRB(L, T, R, B);
+ return true;
+}
+
+bool SkRect::intersect(const SkRect& a, const SkRect& b) {
+ CHECK_INTERSECT(a.fLeft, a.fTop, a.fRight, a.fBottom, b.fLeft, b.fTop, b.fRight, b.fBottom);
+ this->setLTRB(L, T, R, B);
+ return true;
+}
+
+void SkRect::join(const SkRect& r) {
+ if (r.isEmpty()) {
+ return;
+ }
+
+ if (this->isEmpty()) {
+ *this = r;
+ } else {
+ fLeft = std::min(fLeft, r.fLeft);
+ fTop = std::min(fTop, r.fTop);
+ fRight = std::max(fRight, r.fRight);
+ fBottom = std::max(fBottom, r.fBottom);
+ }
+}
+
+////////////////////////////////////////////////////////////////////////////////////////////////
+
+#include "include/core/SkString.h"
+#include "src/core/SkStringUtils.h"
+
+static const char* set_scalar(SkString* storage, SkScalar value, SkScalarAsStringType asType) {
+ storage->reset();
+ SkAppendScalar(storage, value, asType);
+ return storage->c_str();
+}
+
+void SkRect::dump(bool asHex) const {
+ SkScalarAsStringType asType = asHex ? kHex_SkScalarAsStringType : kDec_SkScalarAsStringType;
+
+ SkString line;
+ if (asHex) {
+ SkString tmp;
+ line.printf( "SkRect::MakeLTRB(%s, /* %f */\n", set_scalar(&tmp, fLeft, asType), fLeft);
+ line.appendf(" %s, /* %f */\n", set_scalar(&tmp, fTop, asType), fTop);
+ line.appendf(" %s, /* %f */\n", set_scalar(&tmp, fRight, asType), fRight);
+ line.appendf(" %s /* %f */);", set_scalar(&tmp, fBottom, asType), fBottom);
+ } else {
+ SkString strL, strT, strR, strB;
+ SkAppendScalarDec(&strL, fLeft);
+ SkAppendScalarDec(&strT, fTop);
+ SkAppendScalarDec(&strR, fRight);
+ SkAppendScalarDec(&strB, fBottom);
+ line.printf("SkRect::MakeLTRB(%s, %s, %s, %s);",
+ strL.c_str(), strT.c_str(), strR.c_str(), strB.c_str());
+ }
+ SkDebugf("%s\n", line.c_str());
+}
+
+////////////////////////////////////////////////////////////////////////////////////////////////
+
+template<typename R>
+static bool subtract(const R& a, const R& b, R* out) {
+ if (a.isEmpty() || b.isEmpty() || !R::Intersects(a, b)) {
+ // Either already empty, or subtracting the empty rect, or there's no intersection, so
+ // in all cases the answer is A.
+ *out = a;
+ return true;
+ }
+
+ // 4 rectangles to consider. If the edge in A is contained in B, the resulting difference can
+ // be represented exactly as a rectangle. Otherwise the difference is the largest subrectangle
+ // that is disjoint from B:
+ // 1. Left part of A: (A.left, A.top, B.left, A.bottom)
+ // 2. Right part of A: (B.right, A.top, A.right, A.bottom)
+ // 3. Top part of A: (A.left, A.top, A.right, B.top)
+ // 4. Bottom part of A: (A.left, B.bottom, A.right, A.bottom)
+ //
+ // Depending on how B intersects A, there will be 1 to 4 positive areas:
+ // - 4 occur when A contains B
+ // - 3 occur when B intersects a single edge
+ // - 2 occur when B intersects at a corner, or spans two opposing edges
+ // - 1 occurs when B spans two opposing edges and contains a 3rd, resulting in an exact rect
+ // - 0 occurs when B contains A, resulting in the empty rect
+ //
+ // Compute the relative areas of the 4 rects described above. Since each subrectangle shares
+ // either the width or height of A, we only have to divide by the other dimension, which avoids
+ // overflow on int32 types, and even if the float relative areas overflow to infinity, the
+ // comparisons work out correctly and (one of) the infinitely large subrects will be chosen.
+ float aHeight = (float) a.height();
+ float aWidth = (float) a.width();
+ float leftArea = 0.f, rightArea = 0.f, topArea = 0.f, bottomArea = 0.f;
+ int positiveCount = 0;
+ if (b.fLeft > a.fLeft) {
+ leftArea = (b.fLeft - a.fLeft) / aWidth;
+ positiveCount++;
+ }
+ if (a.fRight > b.fRight) {
+ rightArea = (a.fRight - b.fRight) / aWidth;
+ positiveCount++;
+ }
+ if (b.fTop > a.fTop) {
+ topArea = (b.fTop - a.fTop) / aHeight;
+ positiveCount++;
+ }
+ if (a.fBottom > b.fBottom) {
+ bottomArea = (a.fBottom - b.fBottom) / aHeight;
+ positiveCount++;
+ }
+
+ if (positiveCount == 0) {
+ SkASSERT(b.contains(a));
+ *out = R::MakeEmpty();
+ return true;
+ }
+
+ *out = a;
+ if (leftArea > rightArea && leftArea > topArea && leftArea > bottomArea) {
+ // Left chunk of A, so the new right edge is B's left edge
+ out->fRight = b.fLeft;
+ } else if (rightArea > topArea && rightArea > bottomArea) {
+ // Right chunk of A, so the new left edge is B's right edge
+ out->fLeft = b.fRight;
+ } else if (topArea > bottomArea) {
+ // Top chunk of A, so the new bottom edge is B's top edge
+ out->fBottom = b.fTop;
+ } else {
+ // Bottom chunk of A, so the new top edge is B's bottom edge
+ SkASSERT(bottomArea > 0.f);
+ out->fTop = b.fBottom;
+ }
+
+ // If we have 1 valid area, the disjoint shape is representable as a rectangle.
+ SkASSERT(!R::Intersects(*out, b));
+ return positiveCount == 1;
+}
+
+bool SkRectPriv::Subtract(const SkRect& a, const SkRect& b, SkRect* out) {
+ return subtract<SkRect>(a, b, out);
+}
+
+bool SkRectPriv::Subtract(const SkIRect& a, const SkIRect& b, SkIRect* out) {
+ return subtract<SkIRect>(a, b, out);
+}
+
+
+bool SkRectPriv::QuadContainsRect(const SkMatrix& m, const SkIRect& a, const SkIRect& b) {
+ return QuadContainsRect(SkM44(m), SkRect::Make(a), SkRect::Make(b));
+}
+
+bool SkRectPriv::QuadContainsRect(const SkM44& m, const SkRect& a, const SkRect& b) {
+ SkDEBUGCODE(SkM44 inverse;)
+ SkASSERT(m.invert(&inverse));
+ // With empty rectangles, the calculated edges could give surprising results. If 'a' were not
+ // sorted, its normals would point outside the sorted rectangle, so lots of potential rects
+ // would be seen as "contained". If 'a' is all 0s, its edge equations are also (0,0,0) so every
+ // point has a distance of 0, and would be interpreted as inside.
+ if (a.isEmpty()) {
+ return false;
+ }
+ // However, 'b' is only used to define its 4 corners to check against the transformed edges.
+ // This is valid regardless of b's emptiness or sortedness.
+
+ // Calculate the 4 homogenous coordinates of 'a' transformed by 'm' where Z=0 and W=1.
+ auto ax = skvx::float4{a.fLeft, a.fRight, a.fRight, a.fLeft};
+ auto ay = skvx::float4{a.fTop, a.fTop, a.fBottom, a.fBottom};
+
+ auto max = m.rc(0,0)*ax + m.rc(0,1)*ay + m.rc(0,3);
+ auto may = m.rc(1,0)*ax + m.rc(1,1)*ay + m.rc(1,3);
+ auto maw = m.rc(3,0)*ax + m.rc(3,1)*ay + m.rc(3,3);
+
+ if (all(maw < 0.f)) {
+ // If all points of A are mapped to w < 0, then the edge equations end up representing the
+ // convex hull of projected points when A should in fact be considered empty.
+ return false;
+ }
+
+ // Cross product of adjacent vertices provides homogenous lines for the 4 sides of the quad
+ auto lA = may*skvx::shuffle<1,2,3,0>(maw) - maw*skvx::shuffle<1,2,3,0>(may);
+ auto lB = maw*skvx::shuffle<1,2,3,0>(max) - max*skvx::shuffle<1,2,3,0>(maw);
+ auto lC = max*skvx::shuffle<1,2,3,0>(may) - may*skvx::shuffle<1,2,3,0>(max);
+
+ // Before transforming, the corners of 'a' were in CW order, but afterwards they may become CCW,
+ // so the sign corrects the direction of the edge normals to point inwards.
+ float sign = (lA[0]*lB[1] - lB[0]*lA[1]) < 0 ? -1.f : 1.f;
+
+ // Calculate distance from 'b' to each edge. Since 'b' has presumably been transformed by 'm'
+ // *and* projected, this assumes W = 1.
+ auto d0 = sign * (lA*b.fLeft + lB*b.fTop + lC);
+ auto d1 = sign * (lA*b.fRight + lB*b.fTop + lC);
+ auto d2 = sign * (lA*b.fRight + lB*b.fBottom + lC);
+ auto d3 = sign * (lA*b.fLeft + lB*b.fBottom + lC);
+
+ // 'b' is contained in the mapped rectangle if all distances are >= 0
+ return all((d0 >= 0.f) & (d1 >= 0.f) & (d2 >= 0.f) & (d3 >= 0.f));
+}
generated by cgit v1.2.3 (git 2.39.1) at 2024-09-14 09:18:49 +0000