Index: src/core/SkTileGrid.cpp |
diff --git a/src/core/SkTileGrid.cpp b/src/core/SkTileGrid.cpp |
index 30ca4b9179b7e29d71425a65b0ad4d1dfd31fc8b..7b319f8039b3e62bf758b55f8f12234d4c6ec628 100644 |
--- a/src/core/SkTileGrid.cpp |
+++ b/src/core/SkTileGrid.cpp |
@@ -6,17 +6,25 @@ |
*/ |
#include "SkTileGrid.h" |
+#include "Sk4x.h" |
SkTileGrid::SkTileGrid(int xTiles, int yTiles, const SkTileGridFactory::TileGridInfo& info) |
: fXTiles(xTiles) |
- , fYTiles(yTiles) |
- , fInvWidth( SkScalarInvert(info.fTileInterval.width())) |
- , fInvHeight(SkScalarInvert(info.fTileInterval.height())) |
- , fMarginWidth (info.fMargin.fWidth +1) // Margin is offset by 1 as a provision for AA and |
- , fMarginHeight(info.fMargin.fHeight+1) // to cancel the outset applied by getClipDeviceBounds. |
- , fOffset(SkPoint::Make(info.fOffset.fX, info.fOffset.fY)) |
- , fGridBounds(SkRect::MakeWH(xTiles * info.fTileInterval.width(), |
- yTiles * info.fTileInterval.height())) |
+ , fNumTiles(xTiles * yTiles) |
+ , fGridBounds(0, 0, xTiles * info.fTileInterval.width(), yTiles * info.fTileInterval.height()) |
+ , fMargin(-info.fMargin.fWidth - 1, // Margin is increased by 1 as a provision for AA |
+ -info.fMargin.fHeight - 1, // and to cancel the outset applied by |
+ +info.fMargin.fWidth + 1, // getClipDeviceBounds(). |
+ +info.fMargin.fHeight + 1) |
+ , fOffset(info.fOffset.fX, |
+ info.fOffset.fY, |
+ info.fOffset.fX - SK_ScalarNearlyZero, // We scrunch user-provided bounds in a little |
+ info.fOffset.fY - SK_ScalarNearlyZero) // to make right and bottom edges exclusive. |
+ , fUserToGrid(SkScalarInvert(info.fTileInterval.width()), |
+ SkScalarInvert(info.fTileInterval.height()), |
+ SkScalarInvert(info.fTileInterval.width()), |
+ SkScalarInvert(info.fTileInterval.height())) |
+ , fGridHigh(fXTiles - 1, yTiles - 1, fXTiles - 1, yTiles - 1) |
, fTiles(SkNEW_ARRAY(SkTDArray<unsigned>, xTiles * yTiles)) {} |
SkTileGrid::~SkTileGrid() { |
@@ -24,7 +32,7 @@ SkTileGrid::~SkTileGrid() { |
} |
void SkTileGrid::reserve(unsigned opCount) { |
- if (fXTiles * fYTiles == 0) { |
+ if (fNumTiles == 0) { |
return; // A tileless tile grid is nonsensical, but happens in at least cc_unittests. |
} |
@@ -34,9 +42,9 @@ void SkTileGrid::reserve(unsigned opCount) { |
// If we take those observations and further assume the ops are distributed evenly |
// across the picture, we get this guess for number of ops per tile: |
- const int opsPerTileGuess = (2 * opCount) / (fXTiles * fYTiles); |
+ const int opsPerTileGuess = (2 * opCount) / fNumTiles; |
- for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + (fXTiles * fYTiles); tile++) { |
+ for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + fNumTiles; tile++) { |
tile->setReserve(opsPerTileGuess); |
} |
@@ -45,49 +53,67 @@ void SkTileGrid::reserve(unsigned opCount) { |
} |
void SkTileGrid::flushDeferredInserts() { |
- for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + (fXTiles * fYTiles); tile++) { |
+ for (SkTDArray<unsigned>* tile = fTiles; tile != fTiles + fNumTiles; tile++) { |
tile->shrinkToFit(); |
} |
} |
-// Adjustments to user-provided bounds common to both insert() and search(). |
-// Call this after making insert- or search- specific adjustments. |
-void SkTileGrid::commonAdjust(SkRect* rect) const { |
- // Apply our offset. |
- rect->offset(fOffset); |
+// Convert user-space bounds to grid tiles they cover (LT+RB both inclusive). |
+// Out of bounds queries are clamped to the single nearest tile. |
+void SkTileGrid::userToGrid(const Sk4f& user, SkIRect* out) const { |
+ // Map from user coordinates to grid tile coordinates. |
+ Sk4f grid = user.multiply(fUserToGrid); |
- // Scrunch the bounds in just a little to make the right and bottom edges |
- // exclusive. We want bounds of exactly one tile to hit exactly one tile. |
- rect->fRight -= SK_ScalarNearlyZero; |
- rect->fBottom -= SK_ScalarNearlyZero; |
+ // Now that we're in grid coordinates, clamp to the grid bounds. |
+ grid = Sk4f::Max(grid, Sk4f(0,0,0,0)); |
+ grid = Sk4f::Min(grid, fGridHigh); |
+ |
+ // Truncate to integers. |
+ grid.cast<Sk4i>().store(&out->fLeft); |
+} |
+ |
+// If the rect is inverted, sort it. |
+static Sk4f sorted(const Sk4f& ltrb) { |
+ // To sort: |
+ // left, right = minmax(left, right) |
+ // top, bottom = minmax(top, bottom) |
+ Sk4f rblt = ltrb.zwxy(), |
+ ltlt = Sk4f::Min(ltrb, rblt), // Holds (2 copies of) new left and top. |
+ rbrb = Sk4f::Max(ltrb, rblt), // Holds (2 copies of) new right and bottom. |
+ sort = Sk4f::XYAB(ltlt, rbrb); |
+ return sort; |
} |
-// Convert user-space bounds to grid tiles they cover (LT inclusive, RB exclusive). |
-void SkTileGrid::userToGrid(const SkRect& user, SkIRect* grid) const { |
- grid->fLeft = SkPin32(user.left() * fInvWidth , 0, fXTiles - 1); |
- grid->fTop = SkPin32(user.top() * fInvHeight, 0, fYTiles - 1); |
- grid->fRight = SkPin32(user.right() * fInvWidth , 0, fXTiles - 1) + 1; |
- grid->fBottom = SkPin32(user.bottom() * fInvHeight, 0, fYTiles - 1) + 1; |
+// Do these two LTRB rectangles intersect? |
+static bool intersects(const Sk4f& r1, const Sk4f& r2) { |
+ // Two rects intersect if lefts are less than the |
+ // opposite rights and tops less than opposite bottoms. |
+ Sk4f lt = Sk4f::XYAB(r1, r2), // r1.L r1.T r2.L r2.T < |
+ rb = Sk4f::ZWCD(r2, r1); // r2.R r2.B r1.R r1.B ? |
+ return lt.lessThan(rb).allTrue(); |
} |
void SkTileGrid::insert(unsigned opIndex, const SkRect& originalBounds, bool) { |
- SkRect bounds = originalBounds; |
- bounds.outset(fMarginWidth, fMarginHeight); |
- this->commonAdjust(&bounds); |
+ Sk4f bounds = Sk4f(&originalBounds.fLeft).add(fMargin).add(fOffset); |
+ SkASSERT(sorted(bounds).equal(bounds).allTrue()); |
- // TODO(mtklein): can we assert this instead to save an intersection in Release mode, |
- // or just allow out-of-bound insertions to insert anyway (clamped to nearest tile)? |
- if (!SkRect::Intersects(bounds, fGridBounds)) { |
+ // TODO(mtklein): skip this check and just let out-of-bounds rects insert into nearest tile? |
+ if (!intersects(bounds, fGridBounds)) { |
return; |
} |
SkIRect grid; |
this->userToGrid(bounds, &grid); |
- for (int y = grid.fTop; y < grid.fBottom; y++) { |
- for (int x = grid.fLeft; x < grid.fRight; x++) { |
- fTiles[y * fXTiles + x].push(opIndex); |
+ // This is just a loop over y then x. This compiles to a slightly faster and |
+ // more compact loop than if we just did fTiles[y * fXTiles + x].push(opIndex). |
+ SkTDArray<unsigned>* row = &fTiles[grid.fTop * fXTiles + grid.fLeft]; |
+ for (int y = 0; y <= grid.fBottom - grid.fTop; y++) { |
+ SkTDArray<unsigned>* tile = row; |
+ for (int x = 0; x <= grid.fRight - grid.fLeft; x++) { |
+ (tile++)->push(opIndex); |
} |
+ row += fXTiles; |
} |
} |
@@ -97,25 +123,16 @@ void SkTileGrid::insert(unsigned opIndex, const SkRect& originalBounds, bool) { |
// require 512 tiles of size 256 x 256 pixels. |
static const int kStackAllocationTileCount = 1024; |
+ |
void SkTileGrid::search(const SkRect& originalQuery, SkTDArray<unsigned>* results) const { |
- // The inset counteracts the outset that applied in 'insert', which optimizes |
- // for lookups of size 'tileInterval + 2 * margin' (aligned with the tile grid). |
- SkRect query = originalQuery; |
- query.inset(fMarginWidth, fMarginHeight); |
- this->commonAdjust(&query); |
- |
- // The inset may have inverted the rectangle, so sort(). |
- // TODO(mtklein): It looks like we only end up with inverted bounds in unit tests |
- // that make explicitly inverted queries, not from insetting. If we can drop support for |
- // unsorted bounds (i.e. we don't see them outside unit tests), I think we can drop this. |
- query.sort(); |
- |
- // No intersection check. We optimize for queries that are in bounds. |
- // We're safe anyway: userToGrid() will clamp out-of-bounds queries to nearest tile. |
+ // The .subtract(fMargin) counteracts the .add(fMargin) applied in insert(), |
+ // which optimizes for lookups of size tileInterval + 2 * margin (aligned with the tile grid). |
+ Sk4f query = sorted(Sk4f(&originalQuery.fLeft).subtract(fMargin).add(fOffset)); |
+ |
SkIRect grid; |
this->userToGrid(query, &grid); |
- const int tilesHit = (grid.fRight - grid.fLeft) * (grid.fBottom - grid.fTop); |
+ const int tilesHit = (grid.fRight - grid.fLeft + 1) * (grid.fBottom - grid.fTop + 1); |
reed1
2014/10/15 20:48:11
I see a +1 here, and a change from < to <= down be
mtklein
2014/10/15 20:55:28
Ah, yeah, you're watching work in progress. That
|
SkASSERT(tilesHit > 0); |
if (tilesHit == 1) { |
@@ -130,8 +147,8 @@ void SkTileGrid::search(const SkRect& originalQuery, SkTDArray<unsigned>* result |
// Gather pointers to the starts and ends of the tiles to merge. |
SkAutoSTArray<kStackAllocationTileCount, const unsigned*> starts(tilesHit), ends(tilesHit); |
int i = 0; |
- for (int y = grid.fTop; y < grid.fBottom; y++) { |
- for (int x = grid.fLeft; x < grid.fRight; x++) { |
+ for (int y = grid.fTop; y <= grid.fBottom; y++) { |
+ for (int x = grid.fLeft; x <= grid.fRight; x++) { |
starts[i] = fTiles[y * fXTiles + x].begin(); |
ends[i] = fTiles[y * fXTiles + x].end(); |
i++; |