Line data Source code
1 : /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
2 : /* vim: set ts=8 sts=2 et sw=2 tw=80: */
3 : /* This Source Code Form is subject to the terms of the Mozilla Public
4 : * License, v. 2.0. If a copy of the MPL was not distributed with this
5 : * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
6 :
7 : #include "TiledRegion.h"
8 :
9 : #include <algorithm>
10 :
11 : #include "mozilla/fallible.h"
12 :
13 : namespace mozilla {
14 : namespace gfx {
15 :
16 : static const int32_t kTileSize = 256;
17 : static const size_t kMaxTiles = 1000;
18 :
19 : /**
20 : * TiledRegionImpl stores an array of non-empty rectangles (pixman_box32_ts) to
21 : * represent the region. Each rectangle is contained in a single tile;
22 : * rectangles never cross tile boundaries. The rectangles are sorted by their
23 : * tile's origin in top-to-bottom, left-to-right order.
24 : * (Note that this can mean that a rectangle r1 can come before another
25 : * rectangle r2 even if r2.y1 < r1.y1, as long as the two rects are in the same
26 : * row of tiles and r1.x1 < r2.x1.)
27 : * Empty tiles take up no space in the array - there is no rectangle stored for
28 : * them. As a result, any algorithm that needs to deal with empty tiles will
29 : * iterate through the mRects array and compare the positions of two
30 : * consecutive rects to figure out whether there are any empty tiles between
31 : * them.
32 : */
33 :
34 : static pixman_box32_t
35 1362 : IntersectionOfNonEmptyBoxes(const pixman_box32_t& aBox1,
36 : const pixman_box32_t& aBox2)
37 : {
38 : return pixman_box32_t {
39 1362 : std::max(aBox1.x1, aBox2.x1),
40 1362 : std::max(aBox1.y1, aBox2.y1),
41 1362 : std::min(aBox1.x2, aBox2.x2),
42 1362 : std::min(aBox1.y2, aBox2.y2)
43 5448 : };
44 : }
45 :
46 : // A TileIterator points to a specific tile inside a certain tile range, or to
47 : // the end of the tile range. Advancing a TileIterator will move to the next
48 : // tile inside the range (or to the range end). The next tile is either the
49 : // tile to the right of the current one, or the first tile of the next tile
50 : // row if the current tile is already the last tile in the row.
51 : class TileIterator {
52 : public:
53 1594 : TileIterator(const pixman_box32_t& aTileBounds, const IntPoint& aPosition)
54 1594 : : mTileBounds(aTileBounds)
55 1594 : , mPos(aPosition)
56 1594 : {}
57 :
58 2669 : bool operator!=(const TileIterator& aOther) { return mPos != aOther.mPos; }
59 13 : bool operator==(const TileIterator& aOther) { return mPos == aOther.mPos; }
60 :
61 259 : IntPoint operator*() const { return mPos; }
62 :
63 1362 : const TileIterator& operator++() {
64 1362 : mPos.x += kTileSize;
65 1362 : if (mPos.x >= mTileBounds.x2) {
66 370 : mPos.x = mTileBounds.x1;
67 370 : mPos.y += kTileSize;
68 : }
69 1362 : return *this;
70 : }
71 :
72 13 : TileIterator& operator=(const IntPoint& aPosition)
73 : {
74 13 : mPos = aPosition;
75 13 : return *this;
76 : }
77 :
78 1411 : bool IsBeforeTileContainingPoint(const IntPoint& aPoint) const
79 : {
80 2835 : return (mPos.y + kTileSize) <= aPoint.y ||
81 4123 : (mPos.y <= aPoint.y && (mPos.x + kTileSize) <= aPoint.x);
82 : }
83 :
84 1402 : bool IsAtTileContainingPoint(const IntPoint& aPoint) const
85 : {
86 3986 : return mPos.y <= aPoint.y && aPoint.y < (mPos.y + kTileSize) &&
87 3346 : mPos.x <= aPoint.x && aPoint.x < (mPos.x + kTileSize);
88 :
89 : }
90 :
91 1362 : pixman_box32_t IntersectionWith(const pixman_box32_t& aRect) const
92 : {
93 2724 : pixman_box32_t tile = { mPos.x, mPos.y,
94 2724 : mPos.x + kTileSize, mPos.y + kTileSize };
95 1362 : return IntersectionOfNonEmptyBoxes(tile, aRect);
96 : }
97 :
98 : private:
99 : const pixman_box32_t& mTileBounds;
100 : IntPoint mPos;
101 : };
102 :
103 : // A TileRange describes a range of tiles contained inside a certain tile
104 : // bounds (which is a rectangle that includes all tiles that you're
105 : // interested in). The tile range can start and end at any point inside a
106 : // tile row.
107 : // The tile range end is described by the tile that starts at the bottom
108 : // left corner of the tile bounds, i.e. the first tile under the tile
109 : // bounds.
110 : class TileRange {
111 : public:
112 : // aTileBounds, aStart and aEnd need to be aligned with the tile grid.
113 136 : TileRange(const pixman_box32_t& aTileBounds,
114 : const IntPoint& aStart, const IntPoint& aEnd)
115 136 : : mTileBounds(aTileBounds)
116 : , mStart(aStart)
117 136 : , mEnd(aEnd)
118 136 : {}
119 : // aTileBounds needs to be aligned with the tile grid.
120 306 : explicit TileRange(const pixman_box32_t& aTileBounds)
121 306 : : mTileBounds(aTileBounds)
122 612 : , mStart(mTileBounds.x1, mTileBounds.y1)
123 918 : , mEnd(mTileBounds.x1, mTileBounds.y2)
124 306 : {}
125 :
126 442 : TileIterator Begin() const { return TileIterator(mTileBounds, mStart); }
127 1152 : TileIterator End() const { return TileIterator(mTileBounds, mEnd); }
128 :
129 : // The number of tiles in this tile range.
130 272 : size_t Length() const
131 : {
132 272 : if (mEnd.y == mStart.y) {
133 8 : return (mEnd.x - mStart.x) / kTileSize;
134 : }
135 264 : int64_t numberOfFullRows = (((int64_t)mEnd.y - (int64_t)mStart.y) / kTileSize) - 1;
136 264 : int64_t tilesInFirstRow = ((int64_t)mTileBounds.x2 - (int64_t)mStart.x) / kTileSize;
137 264 : int64_t tilesInLastRow = ((int64_t)mEnd.x - (int64_t)mTileBounds.x1) / kTileSize;
138 264 : int64_t tilesInFullRow = ((int64_t)mTileBounds.x2 - (int64_t)mTileBounds.x1) / kTileSize;
139 264 : int64_t total = tilesInFirstRow + (tilesInFullRow * numberOfFullRows) + tilesInLastRow;
140 264 : MOZ_ASSERT(total > 0);
141 : // The total may be larger than what fits in a size_t, so clamp it to
142 : // SIZE_MAX in that case.
143 264 : return ((uint64_t)total > (uint64_t)SIZE_MAX) ? SIZE_MAX : (size_t)total;
144 : }
145 :
146 : // If aTileOrigin does not describe a tile inside our tile bounds, move it
147 : // to the next tile that you'd encounter by "advancing" a tile iterator
148 : // inside these tile bounds. If aTileOrigin is after the last tile inside
149 : // our tile bounds, move it to the range end tile.
150 : // The result of this method is a valid end tile for a tile range with our
151 : // tile bounds.
152 13 : IntPoint MoveIntoBounds(const IntPoint& aTileOrigin) const
153 : {
154 13 : IntPoint p = aTileOrigin;
155 13 : if (p.x < mTileBounds.x1) {
156 0 : p.x = mTileBounds.x1;
157 13 : } else if (p.x >= mTileBounds.x2) {
158 9 : p.x = mTileBounds.x1;
159 9 : p.y += kTileSize;
160 : }
161 13 : if (p.y < mTileBounds.y1) {
162 0 : p.y = mTileBounds.y1;
163 0 : p.x = mTileBounds.x1;
164 13 : } else if (p.y >= mTileBounds.y2) {
165 : // There's only one valid state after the end of the tile range, and that's
166 : // the bottom left point of the tile bounds.
167 9 : p.x = mTileBounds.x1;
168 9 : p.y = mTileBounds.y2;
169 : }
170 13 : return p;
171 : }
172 :
173 : private:
174 : const pixman_box32_t& mTileBounds;
175 : const IntPoint mStart;
176 : const IntPoint mEnd;
177 : };
178 :
179 : static IntPoint
180 13 : TileContainingPoint(const IntPoint& aPoint)
181 : {
182 26 : return IntPoint(RoundDownToMultiple(aPoint.x, kTileSize),
183 39 : RoundDownToMultiple(aPoint.y, kTileSize));
184 : }
185 :
186 : enum class IterationAction : uint8_t {
187 : CONTINUE,
188 : STOP
189 : };
190 :
191 : enum class IterationEndReason : uint8_t {
192 : NOT_STOPPED,
193 : STOPPED
194 : };
195 :
196 : template<
197 : typename HandleEmptyTilesFunction,
198 : typename HandleNonEmptyTileFunction,
199 : typename RectArrayT>
200 306 : IterationEndReason ProcessIntersectedTiles(const pixman_box32_t& aRect,
201 : RectArrayT& aRectArray,
202 : HandleEmptyTilesFunction aHandleEmptyTiles,
203 : HandleNonEmptyTileFunction aHandleNonEmptyTile)
204 : {
205 : pixman_box32_t tileBounds = {
206 306 : RoundDownToMultiple(aRect.x1, kTileSize),
207 306 : RoundDownToMultiple(aRect.y1, kTileSize),
208 306 : RoundUpToMultiple(aRect.x2, kTileSize),
209 306 : RoundUpToMultiple(aRect.y2, kTileSize)
210 1224 : };
211 306 : if (tileBounds.x2 < tileBounds.x1 || tileBounds.y2 < tileBounds.y1) {
212 : // RoundUpToMultiple probably overflowed. Bail out.
213 0 : return IterationEndReason::STOPPED;
214 : }
215 :
216 306 : TileRange tileRange(tileBounds);
217 306 : TileIterator rangeEnd = tileRange.End();
218 :
219 : // tileIterator points to the next tile in tileRange, or to rangeEnd if we're
220 : // done.
221 306 : TileIterator tileIterator = tileRange.Begin();
222 :
223 : // We iterate over the rectangle array. Depending on the position of the
224 : // rectangle we encounter, we may need to advance tileIterator by zero, one,
225 : // or more tiles:
226 : // - Zero if the rectangle we encountered is outside the tiles that
227 : // intersect aRect.
228 : // - One if the rectangle is in the exact tile that we're interested in next
229 : // (i.e. the tile that tileIterator points at).
230 : // - More than one if the encountered rectangle is in a tile that's further
231 : // to the right or to the bottom than tileIterator. In that case there is
232 : // at least one empty tile between the last rectangle we encountered and
233 : // the current one.
234 1708 : for (size_t i = 0; i < aRectArray.Length() && tileIterator != rangeEnd; i++) {
235 1411 : MOZ_ASSERT(aRectArray[i].x1 < aRectArray[i].x2 && aRectArray[i].y1 < aRectArray[i].y2, "empty rect");
236 1411 : IntPoint rectOrigin(aRectArray[i].x1, aRectArray[i].y1);
237 1411 : if (tileIterator.IsBeforeTileContainingPoint(rectOrigin)) {
238 13 : IntPoint tileOrigin = TileContainingPoint(rectOrigin);
239 13 : IntPoint afterEmptyTiles = tileRange.MoveIntoBounds(tileOrigin);
240 13 : TileRange emptyTiles(tileBounds, *tileIterator, afterEmptyTiles);
241 13 : if (aHandleEmptyTiles(aRectArray, i, emptyTiles) == IterationAction::STOP) {
242 9 : return IterationEndReason::STOPPED;
243 : }
244 13 : tileIterator = afterEmptyTiles;
245 13 : if (tileIterator == rangeEnd) {
246 9 : return IterationEndReason::NOT_STOPPED;
247 : }
248 : }
249 1402 : if (tileIterator.IsAtTileContainingPoint(rectOrigin)) {
250 652 : pixman_box32_t rectIntersection = tileIterator.IntersectionWith(aRect);
251 652 : if (aHandleNonEmptyTile(aRectArray, i, rectIntersection) == IterationAction::STOP) {
252 0 : return IterationEndReason::STOPPED;
253 : }
254 652 : ++tileIterator;
255 : }
256 : }
257 :
258 297 : if (tileIterator != rangeEnd) {
259 : // We've looked at all of our existing rectangles but haven't covered all
260 : // of the tiles that we're interested in yet. So we need to deal with the
261 : // remaining tiles now.
262 123 : size_t endIndex = aRectArray.Length();
263 123 : TileRange emptyTiles(tileBounds, *tileIterator, *rangeEnd);
264 123 : if (aHandleEmptyTiles(aRectArray, endIndex, emptyTiles) == IterationAction::STOP) {
265 0 : return IterationEndReason::STOPPED;
266 : }
267 : }
268 297 : return IterationEndReason::NOT_STOPPED;
269 : }
270 :
271 : static pixman_box32_t
272 652 : UnionBoundsOfNonEmptyBoxes(const pixman_box32_t& aBox1,
273 : const pixman_box32_t& aBox2)
274 : {
275 652 : return { std::min(aBox1.x1, aBox2.x1),
276 652 : std::min(aBox1.y1, aBox2.y1),
277 652 : std::max(aBox1.x2, aBox2.x2),
278 1956 : std::max(aBox1.y2, aBox2.y2) };
279 : }
280 :
281 : // Returns true when adding the rectangle was successful, and false if
282 : // allocation failed.
283 : // When this returns false, our internal state might not be consistent and we
284 : // need to be cleared.
285 : bool
286 306 : TiledRegionImpl::AddRect(const pixman_box32_t& aRect)
287 : {
288 : // We are adding a rectangle that can span multiple tiles.
289 : // For each empty tile that aRect intersects, we need to add the intersection
290 : // of aRect with that tile to mRects, respecting the order of mRects.
291 : // For each tile that already has a rectangle, we need to enlarge that
292 : // existing rectangle to include the intersection of aRect with the tile.
293 612 : return ProcessIntersectedTiles(aRect, mRects,
294 846 : [&aRect](nsTArray<pixman_box32_t>& rects, size_t& rectIndex, TileRange emptyTiles) {
295 136 : CheckedInt<size_t> newLength(rects.Length());
296 136 : newLength += emptyTiles.Length();
297 272 : if (!newLength.isValid() || newLength.value() >= kMaxTiles ||
298 136 : !rects.InsertElementsAt(rectIndex, emptyTiles.Length(), fallible)) {
299 0 : return IterationAction::STOP;
300 : }
301 3248 : for (TileIterator tileIt = emptyTiles.Begin();
302 1692 : tileIt != emptyTiles.End();
303 710 : ++tileIt, ++rectIndex) {
304 1420 : rects[rectIndex] = tileIt.IntersectionWith(aRect);
305 : }
306 136 : return IterationAction::CONTINUE;
307 : },
308 652 : [](nsTArray<pixman_box32_t>& rects, size_t rectIndex, const pixman_box32_t& rectIntersectionWithTile) {
309 652 : rects[rectIndex] =
310 652 : UnionBoundsOfNonEmptyBoxes(rects[rectIndex], rectIntersectionWithTile);
311 652 : return IterationAction::CONTINUE;
312 612 : }) == IterationEndReason::NOT_STOPPED;
313 : }
314 :
315 : static bool
316 0 : NonEmptyBoxesIntersect(const pixman_box32_t& aBox1, const pixman_box32_t& aBox2)
317 : {
318 0 : return aBox1.x1 < aBox2.x2 && aBox2.x1 < aBox1.x2 &&
319 0 : aBox1.y1 < aBox2.y2 && aBox2.y1 < aBox1.y2;
320 : }
321 :
322 : bool
323 0 : TiledRegionImpl::Intersects(const pixman_box32_t& aRect) const
324 : {
325 : // aRect intersects this region if it intersects any of our rectangles.
326 0 : return ProcessIntersectedTiles(aRect, mRects,
327 0 : [](const nsTArray<pixman_box32_t>& rects, size_t& rectIndex, TileRange emptyTiles) {
328 : // Ignore empty tiles and keep on iterating.
329 : return IterationAction::CONTINUE;
330 0 : },
331 0 : [](const nsTArray<pixman_box32_t>& rects, size_t rectIndex, const pixman_box32_t& rectIntersectionWithTile) {
332 0 : if (NonEmptyBoxesIntersect(rects[rectIndex], rectIntersectionWithTile)) {
333 : // Found an intersecting rectangle, so aRect intersects this region.
334 0 : return IterationAction::STOP;
335 : }
336 0 : return IterationAction::CONTINUE;
337 0 : }) == IterationEndReason::STOPPED;
338 : }
339 :
340 : static bool
341 0 : NonEmptyBoxContainsNonEmptyBox(const pixman_box32_t& aBox1, const pixman_box32_t& aBox2)
342 : {
343 0 : return aBox1.x1 <= aBox2.x1 && aBox2.x2 <= aBox1.x2 &&
344 0 : aBox1.y1 <= aBox2.y1 && aBox2.y2 <= aBox1.y2;
345 : }
346 :
347 : bool
348 0 : TiledRegionImpl::Contains(const pixman_box32_t& aRect) const
349 : {
350 : // aRect is contained in this region if aRect does not intersect any empty
351 : // tiles and, for each non-empty tile, if the intersection of aRect with that
352 : // tile is contained in the existing rectangle we have in that tile.
353 0 : return ProcessIntersectedTiles(aRect, mRects,
354 0 : [](const nsTArray<pixman_box32_t>& rects, size_t& rectIndex, TileRange emptyTiles) {
355 : // Found an empty tile that intersects aRect, so aRect is not contained
356 : // in this region.
357 : return IterationAction::STOP;
358 0 : },
359 0 : [](const nsTArray<pixman_box32_t>& rects, size_t rectIndex, const pixman_box32_t& rectIntersectionWithTile) {
360 0 : if (!NonEmptyBoxContainsNonEmptyBox(rects[rectIndex], rectIntersectionWithTile)) {
361 : // Our existing rectangle in this tile does not cover the part of aRect that
362 : // intersects this tile, so aRect is not contained in this region.
363 0 : return IterationAction::STOP;
364 : }
365 0 : return IterationAction::CONTINUE;
366 0 : }) == IterationEndReason::NOT_STOPPED;
367 : }
368 :
369 : } // namespace gfx
370 : } // namespace mozilla
|
