summaryrefslogtreecommitdiff
path: root/gfx/src/TiledRegion.cpp
blob: efaa2346b91ea922d54be42ea6c54fe552c59d24 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
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