summaryrefslogtreecommitdiffstats
path: root/gfx/src/TiledRegion.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'gfx/src/TiledRegion.cpp')
-rw-r--r--gfx/src/TiledRegion.cpp370
1 files changed, 370 insertions, 0 deletions
diff --git a/gfx/src/TiledRegion.cpp b/gfx/src/TiledRegion.cpp
new file mode 100644
index 000000000..efaa2346b
--- /dev/null
+++ b/gfx/src/TiledRegion.cpp
@@ -0,0 +1,370 @@
+/* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* vim: set ts=8 sts=2 et sw=2 tw=80: */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "TiledRegion.h"
+
+#include <algorithm>
+
+#include "mozilla/fallible.h"
+
+namespace mozilla {
+namespace gfx {
+
+static const int32_t kTileSize = 256;
+static const size_t kMaxTiles = 1000;
+
+/**
+ * TiledRegionImpl stores an array of non-empty rectangles (pixman_box32_ts) to
+ * represent the region. Each rectangle is contained in a single tile;
+ * rectangles never cross tile boundaries. The rectangles are sorted by their
+ * tile's origin in top-to-bottom, left-to-right order.
+ * (Note that this can mean that a rectangle r1 can come before another
+ * rectangle r2 even if r2.y1 < r1.y1, as long as the two rects are in the same
+ * row of tiles and r1.x1 < r2.x1.)
+ * Empty tiles take up no space in the array - there is no rectangle stored for
+ * them. As a result, any algorithm that needs to deal with empty tiles will
+ * iterate through the mRects array and compare the positions of two
+ * consecutive rects to figure out whether there are any empty tiles between
+ * them.
+ */
+
+static pixman_box32_t
+IntersectionOfNonEmptyBoxes(const pixman_box32_t& aBox1,
+ const pixman_box32_t& aBox2)
+{
+ return pixman_box32_t {
+ std::max(aBox1.x1, aBox2.x1),
+ std::max(aBox1.y1, aBox2.y1),
+ std::min(aBox1.x2, aBox2.x2),
+ std::min(aBox1.y2, aBox2.y2)
+ };
+}
+
+// A TileIterator points to a specific tile inside a certain tile range, or to
+// the end of the tile range. Advancing a TileIterator will move to the next
+// tile inside the range (or to the range end). The next tile is either the
+// tile to the right of the current one, or the first tile of the next tile
+// row if the current tile is already the last tile in the row.
+class TileIterator {
+public:
+ TileIterator(const pixman_box32_t& aTileBounds, const IntPoint& aPosition)
+ : mTileBounds(aTileBounds)
+ , mPos(aPosition)
+ {}
+
+ bool operator!=(const TileIterator& aOther) { return mPos != aOther.mPos; }
+ bool operator==(const TileIterator& aOther) { return mPos == aOther.mPos; }
+
+ IntPoint operator*() const { return mPos; }
+
+ const TileIterator& operator++() {
+ mPos.x += kTileSize;
+ if (mPos.x >= mTileBounds.x2) {
+ mPos.x = mTileBounds.x1;
+ mPos.y += kTileSize;
+ }
+ return *this;
+ }
+
+ TileIterator& operator=(const IntPoint& aPosition)
+ {
+ mPos = aPosition;
+ return *this;
+ }
+
+ bool IsBeforeTileContainingPoint(const IntPoint& aPoint) const
+ {
+ return (mPos.y + kTileSize) <= aPoint.y ||
+ (mPos.y <= aPoint.y && (mPos.x + kTileSize) <= aPoint.x);
+ }
+
+ bool IsAtTileContainingPoint(const IntPoint& aPoint) const
+ {
+ return mPos.y <= aPoint.y && aPoint.y < (mPos.y + kTileSize) &&
+ mPos.x <= aPoint.x && aPoint.x < (mPos.x + kTileSize);
+
+ }
+
+ pixman_box32_t IntersectionWith(const pixman_box32_t& aRect) const
+ {
+ pixman_box32_t tile = { mPos.x, mPos.y,
+ mPos.x + kTileSize, mPos.y + kTileSize };
+ return IntersectionOfNonEmptyBoxes(tile, aRect);
+ }
+
+private:
+ const pixman_box32_t& mTileBounds;
+ IntPoint mPos;
+};
+
+// A TileRange describes a range of tiles contained inside a certain tile
+// bounds (which is a rectangle that includes all tiles that you're
+// interested in). The tile range can start and end at any point inside a
+// tile row.
+// The tile range end is described by the tile that starts at the bottom
+// left corner of the tile bounds, i.e. the first tile under the tile
+// bounds.
+class TileRange {
+public:
+ // aTileBounds, aStart and aEnd need to be aligned with the tile grid.
+ TileRange(const pixman_box32_t& aTileBounds,
+ const IntPoint& aStart, const IntPoint& aEnd)
+ : mTileBounds(aTileBounds)
+ , mStart(aStart)
+ , mEnd(aEnd)
+ {}
+ // aTileBounds needs to be aligned with the tile grid.
+ explicit TileRange(const pixman_box32_t& aTileBounds)
+ : mTileBounds(aTileBounds)
+ , mStart(mTileBounds.x1, mTileBounds.y1)
+ , mEnd(mTileBounds.x1, mTileBounds.y2)
+ {}
+
+ TileIterator Begin() const { return TileIterator(mTileBounds, mStart); }
+ TileIterator End() const { return TileIterator(mTileBounds, mEnd); }
+
+ // The number of tiles in this tile range.
+ size_t Length() const
+ {
+ if (mEnd.y == mStart.y) {
+ return (mEnd.x - mStart.x) / kTileSize;
+ }
+ int64_t numberOfFullRows = (((int64_t)mEnd.y - (int64_t)mStart.y) / kTileSize) - 1;
+ int64_t tilesInFirstRow = ((int64_t)mTileBounds.x2 - (int64_t)mStart.x) / kTileSize;
+ int64_t tilesInLastRow = ((int64_t)mEnd.x - (int64_t)mTileBounds.x1) / kTileSize;
+ int64_t tilesInFullRow = ((int64_t)mTileBounds.x2 - (int64_t)mTileBounds.x1) / kTileSize;
+ int64_t total = tilesInFirstRow + (tilesInFullRow * numberOfFullRows) + tilesInLastRow;
+ MOZ_ASSERT(total > 0);
+ // The total may be larger than what fits in a size_t, so clamp it to
+ // SIZE_MAX in that case.
+ return ((uint64_t)total > (uint64_t)SIZE_MAX) ? SIZE_MAX : (size_t)total;
+ }
+
+ // If aTileOrigin does not describe a tile inside our tile bounds, move it
+ // to the next tile that you'd encounter by "advancing" a tile iterator
+ // inside these tile bounds. If aTileOrigin is after the last tile inside
+ // our tile bounds, move it to the range end tile.
+ // The result of this method is a valid end tile for a tile range with our
+ // tile bounds.
+ IntPoint MoveIntoBounds(const IntPoint& aTileOrigin) const
+ {
+ IntPoint p = aTileOrigin;
+ if (p.x < mTileBounds.x1) {
+ p.x = mTileBounds.x1;
+ } else if (p.x >= mTileBounds.x2) {
+ p.x = mTileBounds.x1;
+ p.y += kTileSize;
+ }
+ if (p.y < mTileBounds.y1) {
+ p.y = mTileBounds.y1;
+ p.x = mTileBounds.x1;
+ } else if (p.y >= mTileBounds.y2) {
+ // There's only one valid state after the end of the tile range, and that's
+ // the bottom left point of the tile bounds.
+ p.x = mTileBounds.x1;
+ p.y = mTileBounds.y2;
+ }
+ return p;
+ }
+
+private:
+ const pixman_box32_t& mTileBounds;
+ const IntPoint mStart;
+ const IntPoint mEnd;
+};
+
+static IntPoint
+TileContainingPoint(const IntPoint& aPoint)
+{
+ return IntPoint(RoundDownToMultiple(aPoint.x, kTileSize),
+ RoundDownToMultiple(aPoint.y, kTileSize));
+}
+
+enum class IterationAction : uint8_t {
+ CONTINUE,
+ STOP
+};
+
+enum class IterationEndReason : uint8_t {
+ NOT_STOPPED,
+ STOPPED
+};
+
+template<
+ typename HandleEmptyTilesFunction,
+ typename HandleNonEmptyTileFunction,
+ typename RectArrayT>
+IterationEndReason ProcessIntersectedTiles(const pixman_box32_t& aRect,
+ RectArrayT& aRectArray,
+ HandleEmptyTilesFunction aHandleEmptyTiles,
+ HandleNonEmptyTileFunction aHandleNonEmptyTile)
+{
+ pixman_box32_t tileBounds = {
+ RoundDownToMultiple(aRect.x1, kTileSize),
+ RoundDownToMultiple(aRect.y1, kTileSize),
+ RoundUpToMultiple(aRect.x2, kTileSize),
+ RoundUpToMultiple(aRect.y2, kTileSize)
+ };
+ if (tileBounds.x2 < tileBounds.x1 || tileBounds.y2 < tileBounds.y1) {
+ // RoundUpToMultiple probably overflowed. Bail out.
+ return IterationEndReason::STOPPED;
+ }
+
+ TileRange tileRange(tileBounds);
+ TileIterator rangeEnd = tileRange.End();
+
+ // tileIterator points to the next tile in tileRange, or to rangeEnd if we're
+ // done.
+ TileIterator tileIterator = tileRange.Begin();
+
+ // We iterate over the rectangle array. Depending on the position of the
+ // rectangle we encounter, we may need to advance tileIterator by zero, one,
+ // or more tiles:
+ // - Zero if the rectangle we encountered is outside the tiles that
+ // intersect aRect.
+ // - One if the rectangle is in the exact tile that we're interested in next
+ // (i.e. the tile that tileIterator points at).
+ // - More than one if the encountered rectangle is in a tile that's further
+ // to the right or to the bottom than tileIterator. In that case there is
+ // at least one empty tile between the last rectangle we encountered and
+ // the current one.
+ for (size_t i = 0; i < aRectArray.Length() && tileIterator != rangeEnd; i++) {
+ MOZ_ASSERT(aRectArray[i].x1 < aRectArray[i].x2 && aRectArray[i].y1 < aRectArray[i].y2, "empty rect");
+ IntPoint rectOrigin(aRectArray[i].x1, aRectArray[i].y1);
+ if (tileIterator.IsBeforeTileContainingPoint(rectOrigin)) {
+ IntPoint tileOrigin = TileContainingPoint(rectOrigin);
+ IntPoint afterEmptyTiles = tileRange.MoveIntoBounds(tileOrigin);
+ TileRange emptyTiles(tileBounds, *tileIterator, afterEmptyTiles);
+ if (aHandleEmptyTiles(aRectArray, i, emptyTiles) == IterationAction::STOP) {
+ return IterationEndReason::STOPPED;
+ }
+ tileIterator = afterEmptyTiles;
+ if (tileIterator == rangeEnd) {
+ return IterationEndReason::NOT_STOPPED;
+ }
+ }
+ if (tileIterator.IsAtTileContainingPoint(rectOrigin)) {
+ pixman_box32_t rectIntersection = tileIterator.IntersectionWith(aRect);
+ if (aHandleNonEmptyTile(aRectArray, i, rectIntersection) == IterationAction::STOP) {
+ return IterationEndReason::STOPPED;
+ }
+ ++tileIterator;
+ }
+ }
+
+ if (tileIterator != rangeEnd) {
+ // We've looked at all of our existing rectangles but haven't covered all
+ // of the tiles that we're interested in yet. So we need to deal with the
+ // remaining tiles now.
+ size_t endIndex = aRectArray.Length();
+ TileRange emptyTiles(tileBounds, *tileIterator, *rangeEnd);
+ if (aHandleEmptyTiles(aRectArray, endIndex, emptyTiles) == IterationAction::STOP) {
+ return IterationEndReason::STOPPED;
+ }
+ }
+ return IterationEndReason::NOT_STOPPED;
+}
+
+static pixman_box32_t
+UnionBoundsOfNonEmptyBoxes(const pixman_box32_t& aBox1,
+ const pixman_box32_t& aBox2)
+{
+ return { std::min(aBox1.x1, aBox2.x1),
+ std::min(aBox1.y1, aBox2.y1),
+ std::max(aBox1.x2, aBox2.x2),
+ std::max(aBox1.y2, aBox2.y2) };
+}
+
+// Returns true when adding the rectangle was successful, and false if
+// allocation failed.
+// When this returns false, our internal state might not be consistent and we
+// need to be cleared.
+bool
+TiledRegionImpl::AddRect(const pixman_box32_t& aRect)
+{
+ // We are adding a rectangle that can span multiple tiles.
+ // For each empty tile that aRect intersects, we need to add the intersection
+ // of aRect with that tile to mRects, respecting the order of mRects.
+ // For each tile that already has a rectangle, we need to enlarge that
+ // existing rectangle to include the intersection of aRect with the tile.
+ return ProcessIntersectedTiles(aRect, mRects,
+ [&aRect](nsTArray<pixman_box32_t>& rects, size_t& rectIndex, TileRange emptyTiles) {
+ CheckedInt<size_t> newLength(rects.Length());
+ newLength += emptyTiles.Length();
+ if (!newLength.isValid() || newLength.value() >= kMaxTiles ||
+ !rects.InsertElementsAt(rectIndex, emptyTiles.Length(), fallible)) {
+ return IterationAction::STOP;
+ }
+ for (TileIterator tileIt = emptyTiles.Begin();
+ tileIt != emptyTiles.End();
+ ++tileIt, ++rectIndex) {
+ rects[rectIndex] = tileIt.IntersectionWith(aRect);
+ }
+ return IterationAction::CONTINUE;
+ },
+ [](nsTArray<pixman_box32_t>& rects, size_t rectIndex, const pixman_box32_t& rectIntersectionWithTile) {
+ rects[rectIndex] =
+ UnionBoundsOfNonEmptyBoxes(rects[rectIndex], rectIntersectionWithTile);
+ return IterationAction::CONTINUE;
+ }) == IterationEndReason::NOT_STOPPED;
+}
+
+static bool
+NonEmptyBoxesIntersect(const pixman_box32_t& aBox1, const pixman_box32_t& aBox2)
+{
+ return aBox1.x1 < aBox2.x2 && aBox2.x1 < aBox1.x2 &&
+ aBox1.y1 < aBox2.y2 && aBox2.y1 < aBox1.y2;
+}
+
+bool
+TiledRegionImpl::Intersects(const pixman_box32_t& aRect) const
+{
+ // aRect intersects this region if it intersects any of our rectangles.
+ return ProcessIntersectedTiles(aRect, mRects,
+ [](const nsTArray<pixman_box32_t>& rects, size_t& rectIndex, TileRange emptyTiles) {
+ // Ignore empty tiles and keep on iterating.
+ return IterationAction::CONTINUE;
+ },
+ [](const nsTArray<pixman_box32_t>& rects, size_t rectIndex, const pixman_box32_t& rectIntersectionWithTile) {
+ if (NonEmptyBoxesIntersect(rects[rectIndex], rectIntersectionWithTile)) {
+ // Found an intersecting rectangle, so aRect intersects this region.
+ return IterationAction::STOP;
+ }
+ return IterationAction::CONTINUE;
+ }) == IterationEndReason::STOPPED;
+}
+
+static bool
+NonEmptyBoxContainsNonEmptyBox(const pixman_box32_t& aBox1, const pixman_box32_t& aBox2)
+{
+ return aBox1.x1 <= aBox2.x1 && aBox2.x2 <= aBox1.x2 &&
+ aBox1.y1 <= aBox2.y1 && aBox2.y2 <= aBox1.y2;
+}
+
+bool
+TiledRegionImpl::Contains(const pixman_box32_t& aRect) const
+{
+ // aRect is contained in this region if aRect does not intersect any empty
+ // tiles and, for each non-empty tile, if the intersection of aRect with that
+ // tile is contained in the existing rectangle we have in that tile.
+ return ProcessIntersectedTiles(aRect, mRects,
+ [](const nsTArray<pixman_box32_t>& rects, size_t& rectIndex, TileRange emptyTiles) {
+ // Found an empty tile that intersects aRect, so aRect is not contained
+ // in this region.
+ return IterationAction::STOP;
+ },
+ [](const nsTArray<pixman_box32_t>& rects, size_t rectIndex, const pixman_box32_t& rectIntersectionWithTile) {
+ if (!NonEmptyBoxContainsNonEmptyBox(rects[rectIndex], rectIntersectionWithTile)) {
+ // Our existing rectangle in this tile does not cover the part of aRect that
+ // intersects this tile, so aRect is not contained in this region.
+ return IterationAction::STOP;
+ }
+ return IterationAction::CONTINUE;
+ }) == IterationEndReason::NOT_STOPPED;
+}
+
+} // namespace gfx
+} // namespace mozilla