1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/gfx/src/nsRegion.cpp Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,960 @@
1.4 +/* This Source Code Form is subject to the terms of the Mozilla Public
1.5 + * License, v. 2.0. If a copy of the MPL was not distributed with this
1.6 + * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
1.7 +
1.8 +
1.9 +#include "nsRegion.h"
1.10 +#include "nsPrintfCString.h"
1.11 +#include "nsTArray.h"
1.12 +
1.13 +
1.14 +bool nsRegion::Contains(const nsRegion& aRgn) const
1.15 +{
1.16 + // XXX this could be made faster
1.17 + nsRegionRectIterator iter(aRgn);
1.18 + while (const nsRect* r = iter.Next()) {
1.19 + if (!Contains (*r)) {
1.20 + return false;
1.21 + }
1.22 + }
1.23 + return true;
1.24 +}
1.25 +
1.26 +bool nsRegion::Intersects(const nsRect& aRect) const
1.27 +{
1.28 + // XXX this could be made faster
1.29 + nsRegionRectIterator iter(*this);
1.30 + while (const nsRect* r = iter.Next()) {
1.31 + if (r->Intersects(aRect)) {
1.32 + return true;
1.33 + }
1.34 + }
1.35 + return false;
1.36 +}
1.37 +
1.38 +void nsRegion::Inflate(const nsMargin& aMargin)
1.39 +{
1.40 + int n;
1.41 + pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n);
1.42 + for (int i=0; i<n; i++) {
1.43 + nsRect rect = BoxToRect(boxes[i]);
1.44 + rect.Inflate(aMargin);
1.45 + boxes[i] = RectToBox(rect);
1.46 + }
1.47 +
1.48 + pixman_region32_t region;
1.49 + // This will union all of the rectangles and runs in about O(n lg(n))
1.50 + pixman_region32_init_rects(®ion, boxes, n);
1.51 +
1.52 + pixman_region32_fini(&mImpl);
1.53 + mImpl = region;
1.54 +}
1.55 +
1.56 +void nsRegion::SimplifyOutward (uint32_t aMaxRects)
1.57 +{
1.58 + MOZ_ASSERT(aMaxRects >= 1, "Invalid max rect count");
1.59 +
1.60 + if (GetNumRects() <= aMaxRects)
1.61 + return;
1.62 +
1.63 + pixman_box32_t *boxes;
1.64 + int n;
1.65 + boxes = pixman_region32_rectangles(&mImpl, &n);
1.66 +
1.67 + // Try combining rects in horizontal bands into a single rect
1.68 + int dest = 0;
1.69 + for (int src = 1; src < n; src++)
1.70 + {
1.71 + // The goal here is to try to keep groups of rectangles that are vertically
1.72 + // discontiguous as separate rectangles in the final region. This is
1.73 + // simple and fast to implement and page contents tend to vary more
1.74 + // vertically than horizontally (which is why our rectangles are stored
1.75 + // sorted by y-coordinate, too).
1.76 + //
1.77 + // Note: if boxes share y1 because of the canonical representation they
1.78 + // will share y2
1.79 + while ((src < (n)) && boxes[dest].y1 == boxes[src].y1) {
1.80 + // merge box[i] and box[i+1]
1.81 + boxes[dest].x2 = boxes[src].x2;
1.82 + src++;
1.83 + }
1.84 + if (src < n) {
1.85 + dest++;
1.86 + boxes[dest] = boxes[src];
1.87 + }
1.88 + }
1.89 +
1.90 + uint32_t reducedCount = dest+1;
1.91 + // pixman has a special representation for
1.92 + // regions of 1 rectangle. So just use the
1.93 + // bounds in that case
1.94 + if (reducedCount > 1 && reducedCount <= aMaxRects) {
1.95 + // reach into pixman and lower the number
1.96 + // of rects stored in data.
1.97 + mImpl.data->numRects = reducedCount;
1.98 + } else {
1.99 + *this = GetBounds();
1.100 + }
1.101 +}
1.102 +
1.103 +// compute the covered area difference between two rows.
1.104 +// by iterating over both rows simultaneously and adding up
1.105 +// the additional increase in area caused by extending each
1.106 +// of the rectangles to the combined height of both rows
1.107 +static uint32_t ComputeMergedAreaIncrease(pixman_box32_t *topRects,
1.108 + pixman_box32_t *topRectsEnd,
1.109 + pixman_box32_t *bottomRects,
1.110 + pixman_box32_t *bottomRectsEnd)
1.111 +{
1.112 + uint32_t totalArea = 0;
1.113 + struct pt {
1.114 + int32_t x, y;
1.115 + };
1.116 +
1.117 +
1.118 + pt *i = (pt*)topRects;
1.119 + pt *end_i = (pt*)topRectsEnd;
1.120 + pt *j = (pt*)bottomRects;
1.121 + pt *end_j = (pt*)bottomRectsEnd;
1.122 + bool top = false;
1.123 + bool bottom = false;
1.124 +
1.125 + int cur_x = i->x;
1.126 + bool top_next = top;
1.127 + bool bottom_next = bottom;
1.128 + //XXX: we could probably simplify this condition and perhaps move it into the loop below
1.129 + if (j->x < cur_x) {
1.130 + cur_x = j->x;
1.131 + j++;
1.132 + bottom_next = !bottom;
1.133 + } else if (j->x == cur_x) {
1.134 + i++;
1.135 + top_next = !top;
1.136 + bottom_next = !bottom;
1.137 + j++;
1.138 + } else {
1.139 + top_next = !top;
1.140 + i++;
1.141 + }
1.142 +
1.143 + int topRectsHeight = topRects->y2 - topRects->y1;
1.144 + int bottomRectsHeight = bottomRects->y2 - bottomRects->y1;
1.145 + int inbetweenHeight = bottomRects->y1 - topRects->y2;
1.146 + int width = cur_x;
1.147 + // top and bottom are the in-status to the left of cur_x
1.148 + do {
1.149 + if (top && !bottom) {
1.150 + totalArea += (inbetweenHeight+bottomRectsHeight)*width;
1.151 + } else if (bottom && !top) {
1.152 + totalArea += (inbetweenHeight+topRectsHeight)*width;
1.153 + } else if (bottom && top) {
1.154 + totalArea += (inbetweenHeight)*width;
1.155 + }
1.156 + top = top_next;
1.157 + bottom = bottom_next;
1.158 + // find the next edge
1.159 + if (i->x < j->x) {
1.160 + top_next = !top;
1.161 + width = i->x - cur_x;
1.162 + cur_x = i->x;
1.163 + i++;
1.164 + } else if (j->x < i->x) {
1.165 + bottom_next = !bottom;
1.166 + width = j->x - cur_x;
1.167 + cur_x = j->x;
1.168 + j++;
1.169 + } else { // i->x == j->x
1.170 + top_next = !top;
1.171 + bottom_next = !bottom;
1.172 + width = i->x - cur_x;
1.173 + cur_x = i->x;
1.174 + i++;
1.175 + j++;
1.176 + }
1.177 + } while (i < end_i && j < end_j);
1.178 +
1.179 + // handle any remaining rects
1.180 + while (i < end_i) {
1.181 + width = i->x - cur_x;
1.182 + cur_x = i->x;
1.183 + i++;
1.184 + if (top)
1.185 + totalArea += (inbetweenHeight+bottomRectsHeight)*width;
1.186 + top = !top;
1.187 + }
1.188 +
1.189 + while (j < end_j) {
1.190 + width = j->x - cur_x;
1.191 + cur_x = j->x;
1.192 + j++;
1.193 + if (bottom)
1.194 + totalArea += (inbetweenHeight+topRectsHeight)*width;
1.195 + bottom = !bottom;
1.196 + }
1.197 + return totalArea;
1.198 +}
1.199 +
1.200 +static pixman_box32_t *
1.201 +CopyRow(pixman_box32_t *dest_it, pixman_box32_t *src_start, pixman_box32_t *src_end)
1.202 +{
1.203 + // XXX: std::copy
1.204 + pixman_box32_t *src_it = src_start;
1.205 + while (src_it < src_end) {
1.206 + *dest_it++ = *src_it++;
1.207 + }
1.208 + return dest_it;
1.209 +}
1.210 +
1.211 +static pixman_box32_t *
1.212 +MergeRects(pixman_box32_t *topRects, pixman_box32_t *topRectsEnd,
1.213 + pixman_box32_t *bottomRects, pixman_box32_t *bottomRectsEnd,
1.214 + pixman_box32_t *tmpRect)
1.215 +{
1.216 + struct pt {
1.217 + int32_t x, y;
1.218 + };
1.219 +
1.220 + pixman_box32_t *rect;
1.221 + // merge the two spans of rects
1.222 + pt *i = (pt*)topRects;
1.223 + pt *end_i = (pt*)topRectsEnd;
1.224 + pt *j = (pt*)bottomRects;
1.225 + pt *end_j = (pt*)bottomRectsEnd;
1.226 + bool top;
1.227 + bool bottom;
1.228 +
1.229 + int cur_x = i->x;
1.230 + int32_t y1 = topRects->y1;
1.231 + int32_t y2 = bottomRects->y2;
1.232 + if (j->x < cur_x) {
1.233 + top = false;
1.234 + bottom = true;
1.235 + cur_x = j->x;
1.236 + j++;
1.237 + } else if (j->x == cur_x) {
1.238 + top = true;
1.239 + bottom = true;
1.240 + i++;
1.241 + j++;
1.242 + } else {
1.243 + top = true;
1.244 + bottom = false;
1.245 + i++;
1.246 + }
1.247 +
1.248 + rect = tmpRect;
1.249 + bool started = false;
1.250 + do {
1.251 + if (started && !top && !bottom) {
1.252 + rect->x2 = cur_x;
1.253 + rect->y2 = y2;
1.254 + rect++;
1.255 + started = false;
1.256 + } else if (!started) {
1.257 + rect->x1 = cur_x;
1.258 + rect->y1 = y1;
1.259 + started = true;
1.260 + }
1.261 +
1.262 + if (i >= end_i || j >= end_j)
1.263 + break;
1.264 +
1.265 + if (i->x < j->x) {
1.266 + top = !top;
1.267 + cur_x = i->x;
1.268 + i++;
1.269 + } else if (j->x < i->x) {
1.270 + bottom = !bottom;
1.271 + cur_x = j->x;
1.272 + j++;
1.273 + } else { // i->x == j->x
1.274 + top = !top;
1.275 + bottom = !bottom;
1.276 + cur_x = i->x;
1.277 + i++;
1.278 + j++;
1.279 + }
1.280 + } while (true);
1.281 +
1.282 + // handle any remaining rects
1.283 + while (i < end_i) {
1.284 + top = !top;
1.285 + cur_x = i->x;
1.286 + i++;
1.287 + if (!top) {
1.288 + rect->x2 = cur_x;
1.289 + rect->y2 = y2;
1.290 + rect++;
1.291 + } else {
1.292 + rect->x1 = cur_x;
1.293 + rect->y1 = y1;
1.294 + }
1.295 + }
1.296 +
1.297 + while (j < end_j) {
1.298 + bottom = !bottom;
1.299 + cur_x = j->x;
1.300 + j++;
1.301 + if (!bottom) {
1.302 + rect->x2 = cur_x;
1.303 + rect->y2 = y2;
1.304 + rect++;
1.305 + } else {
1.306 + rect->x1 = cur_x;
1.307 + rect->y1 = y1;
1.308 + }
1.309 + }
1.310 + return rect;
1.311 +}
1.312 +
1.313 +void nsRegion::SimplifyOutwardByArea(uint32_t aThreshold)
1.314 +{
1.315 +
1.316 + pixman_box32_t *boxes;
1.317 + int n;
1.318 + boxes = pixman_region32_rectangles(&mImpl, &n);
1.319 +
1.320 + // if we have no rectangles then we're done
1.321 + if (!n)
1.322 + return;
1.323 +
1.324 + pixman_box32_t *end = boxes + n;
1.325 + pixman_box32_t *topRectsEnd = boxes+1;
1.326 + pixman_box32_t *topRects = boxes;
1.327 +
1.328 + // we need some temporary storage for merging both rows of rectangles
1.329 + nsAutoTArray<pixman_box32_t, 10> tmpStorage;
1.330 + tmpStorage.SetCapacity(n);
1.331 + pixman_box32_t *tmpRect = tmpStorage.Elements();
1.332 +
1.333 + pixman_box32_t *destRect = boxes;
1.334 + pixman_box32_t *rect = tmpRect;
1.335 + // find the end of the first span of rectangles
1.336 + while (topRectsEnd < end && topRectsEnd->y1 == topRects->y1) {
1.337 + topRectsEnd++;
1.338 + }
1.339 +
1.340 + // if we only have one row we are done
1.341 + if (topRectsEnd == end)
1.342 + return;
1.343 +
1.344 + pixman_box32_t *bottomRects = topRectsEnd;
1.345 + pixman_box32_t *bottomRectsEnd = bottomRects+1;
1.346 + do {
1.347 + // find the end of the bottom span of rectangles
1.348 + while (bottomRectsEnd < end && bottomRectsEnd->y1 == bottomRects->y1) {
1.349 + bottomRectsEnd++;
1.350 + }
1.351 + uint32_t totalArea = ComputeMergedAreaIncrease(topRects, topRectsEnd,
1.352 + bottomRects, bottomRectsEnd);
1.353 +
1.354 + if (totalArea <= aThreshold) {
1.355 + // merge the rects into tmpRect
1.356 + rect = MergeRects(topRects, topRectsEnd, bottomRects, bottomRectsEnd, tmpRect);
1.357 +
1.358 + // copy the merged rects back into the destination
1.359 + topRectsEnd = CopyRow(destRect, tmpRect, rect);
1.360 + topRects = destRect;
1.361 + bottomRects = bottomRectsEnd;
1.362 + destRect = topRects;
1.363 + } else {
1.364 + // copy the unmerged rects
1.365 + destRect = CopyRow(destRect, topRects, topRectsEnd);
1.366 +
1.367 + topRects = bottomRects;
1.368 + topRectsEnd = bottomRectsEnd;
1.369 + bottomRects = bottomRectsEnd;
1.370 + if (bottomRectsEnd == end) {
1.371 + // copy the last row when we are done
1.372 + topRectsEnd = CopyRow(destRect, topRects, topRectsEnd);
1.373 + }
1.374 + }
1.375 + } while (bottomRectsEnd != end);
1.376 +
1.377 +
1.378 + uint32_t reducedCount = topRectsEnd - pixman_region32_rectangles(&this->mImpl, &n);
1.379 + // pixman has a special representation for
1.380 + // regions of 1 rectangle. So just use the
1.381 + // bounds in that case
1.382 + if (reducedCount > 1) {
1.383 + // reach into pixman and lower the number
1.384 + // of rects stored in data.
1.385 + this->mImpl.data->numRects = reducedCount;
1.386 + } else {
1.387 + *this = GetBounds();
1.388 + }
1.389 +}
1.390 +
1.391 +
1.392 +void nsRegion::SimplifyInward (uint32_t aMaxRects)
1.393 +{
1.394 + NS_ASSERTION(aMaxRects >= 1, "Invalid max rect count");
1.395 +
1.396 + if (GetNumRects() <= aMaxRects)
1.397 + return;
1.398 +
1.399 + SetEmpty();
1.400 +}
1.401 +
1.402 +uint64_t nsRegion::Area () const
1.403 +{
1.404 + uint64_t area = 0;
1.405 + nsRegionRectIterator iter(*this);
1.406 + const nsRect* r;
1.407 + while ((r = iter.Next()) != nullptr) {
1.408 + area += uint64_t(r->width)*r->height;
1.409 + }
1.410 + return area;
1.411 +}
1.412 +
1.413 +nsRegion& nsRegion::ScaleRoundOut (float aXScale, float aYScale)
1.414 +{
1.415 + int n;
1.416 + pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n);
1.417 + for (int i=0; i<n; i++) {
1.418 + nsRect rect = BoxToRect(boxes[i]);
1.419 + rect.ScaleRoundOut(aXScale, aYScale);
1.420 + boxes[i] = RectToBox(rect);
1.421 + }
1.422 +
1.423 + pixman_region32_t region;
1.424 + // This will union all of the rectangles and runs in about O(n lg(n))
1.425 + pixman_region32_init_rects(®ion, boxes, n);
1.426 +
1.427 + pixman_region32_fini(&mImpl);
1.428 + mImpl = region;
1.429 + return *this;
1.430 +}
1.431 +
1.432 +nsRegion& nsRegion::ScaleInverseRoundOut (float aXScale, float aYScale)
1.433 +{
1.434 + int n;
1.435 + pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n);
1.436 + for (int i=0; i<n; i++) {
1.437 + nsRect rect = BoxToRect(boxes[i]);
1.438 + rect.ScaleInverseRoundOut(aXScale, aYScale);
1.439 + boxes[i] = RectToBox(rect);
1.440 + }
1.441 +
1.442 + pixman_region32_t region;
1.443 + // This will union all of the rectangles and runs in about O(n lg(n))
1.444 + pixman_region32_init_rects(®ion, boxes, n);
1.445 +
1.446 + pixman_region32_fini(&mImpl);
1.447 + mImpl = region;
1.448 + return *this;
1.449 +}
1.450 +
1.451 +nsRegion nsRegion::ConvertAppUnitsRoundOut (int32_t aFromAPP, int32_t aToAPP) const
1.452 +{
1.453 + if (aFromAPP == aToAPP) {
1.454 + return *this;
1.455 + }
1.456 +
1.457 + nsRegion region = *this;
1.458 + int n;
1.459 + pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n);
1.460 + for (int i=0; i<n; i++) {
1.461 + nsRect rect = BoxToRect(boxes[i]);
1.462 + rect = rect.ConvertAppUnitsRoundOut(aFromAPP, aToAPP);
1.463 + boxes[i] = RectToBox(rect);
1.464 + }
1.465 +
1.466 + pixman_region32_t pixmanRegion;
1.467 + // This will union all of the rectangles and runs in about O(n lg(n))
1.468 + pixman_region32_init_rects(&pixmanRegion, boxes, n);
1.469 +
1.470 + pixman_region32_fini(®ion.mImpl);
1.471 + region.mImpl = pixmanRegion;
1.472 + return region;
1.473 +}
1.474 +
1.475 +nsRegion nsRegion::ConvertAppUnitsRoundIn (int32_t aFromAPP, int32_t aToAPP) const
1.476 +{
1.477 + if (aFromAPP == aToAPP) {
1.478 + return *this;
1.479 + }
1.480 +
1.481 + nsRegion region = *this;
1.482 + int n;
1.483 + pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n);
1.484 + for (int i=0; i<n; i++) {
1.485 + nsRect rect = BoxToRect(boxes[i]);
1.486 + rect = rect.ConvertAppUnitsRoundIn(aFromAPP, aToAPP);
1.487 + boxes[i] = RectToBox(rect);
1.488 + }
1.489 +
1.490 + pixman_region32_t pixmanRegion;
1.491 + // This will union all of the rectangles and runs in about O(n lg(n))
1.492 + pixman_region32_init_rects(&pixmanRegion, boxes, n);
1.493 +
1.494 + pixman_region32_fini(®ion.mImpl);
1.495 + region.mImpl = pixmanRegion;
1.496 + return region;
1.497 +}
1.498 +
1.499 +nsIntRegion nsRegion::ToPixels (nscoord aAppUnitsPerPixel, bool aOutsidePixels) const
1.500 +{
1.501 + nsRegion region = *this;
1.502 + int n;
1.503 + pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n);
1.504 + for (int i=0; i<n; i++) {
1.505 + nsRect rect = BoxToRect(boxes[i]);
1.506 + nsIntRect deviceRect;
1.507 + if (aOutsidePixels)
1.508 + deviceRect = rect.ToOutsidePixels(aAppUnitsPerPixel);
1.509 + else
1.510 + deviceRect = rect.ToNearestPixels(aAppUnitsPerPixel);
1.511 +
1.512 + boxes[i] = RectToBox(deviceRect);
1.513 + }
1.514 +
1.515 + nsIntRegion intRegion;
1.516 + pixman_region32_fini(&intRegion.mImpl.mImpl);
1.517 + // This will union all of the rectangles and runs in about O(n lg(n))
1.518 + pixman_region32_init_rects(&intRegion.mImpl.mImpl, boxes, n);
1.519 +
1.520 + return intRegion;
1.521 +}
1.522 +
1.523 +nsIntRegion nsRegion::ToOutsidePixels (nscoord aAppUnitsPerPixel) const
1.524 +{
1.525 + return ToPixels(aAppUnitsPerPixel, true);
1.526 +}
1.527 +
1.528 +nsIntRegion nsRegion::ToNearestPixels (nscoord aAppUnitsPerPixel) const
1.529 +{
1.530 + return ToPixels(aAppUnitsPerPixel, false);
1.531 +}
1.532 +
1.533 +nsIntRegion nsRegion::ScaleToNearestPixels (float aScaleX, float aScaleY,
1.534 + nscoord aAppUnitsPerPixel) const
1.535 +{
1.536 + nsIntRegion result;
1.537 + nsRegionRectIterator rgnIter(*this);
1.538 + const nsRect* currentRect;
1.539 + while ((currentRect = rgnIter.Next())) {
1.540 + nsIntRect deviceRect =
1.541 + currentRect->ScaleToNearestPixels(aScaleX, aScaleY, aAppUnitsPerPixel);
1.542 + result.Or(result, deviceRect);
1.543 + }
1.544 + return result;
1.545 +}
1.546 +
1.547 +nsIntRegion nsRegion::ScaleToOutsidePixels (float aScaleX, float aScaleY,
1.548 + nscoord aAppUnitsPerPixel) const
1.549 +{
1.550 + nsIntRegion result;
1.551 + nsRegionRectIterator rgnIter(*this);
1.552 + const nsRect* currentRect;
1.553 + while ((currentRect = rgnIter.Next())) {
1.554 + nsIntRect deviceRect =
1.555 + currentRect->ScaleToOutsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
1.556 + result.Or(result, deviceRect);
1.557 + }
1.558 + return result;
1.559 +}
1.560 +
1.561 +nsIntRegion nsRegion::ScaleToInsidePixels (float aScaleX, float aScaleY,
1.562 + nscoord aAppUnitsPerPixel) const
1.563 +{
1.564 + /* When scaling a rect, walk forward through the rect list up until the y value is greater
1.565 + * than the current rect's YMost() value.
1.566 + *
1.567 + * For each rect found, check if the rects have a touching edge (in unscaled coordinates),
1.568 + * and if one edge is entirely contained within the other.
1.569 + *
1.570 + * If it is, then the contained edge can be moved (in scaled pixels) to ensure that no
1.571 + * gap exists.
1.572 + *
1.573 + * Since this could be potentially expensive - O(n^2), we only attempt this algorithm
1.574 + * for the first rect.
1.575 + */
1.576 +
1.577 + // make a copy of this region so that we can mutate it in place
1.578 + nsRegion region = *this;
1.579 + int n;
1.580 + pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n);
1.581 +
1.582 + nsIntRegion intRegion;
1.583 + if (n) {
1.584 + nsRect first = BoxToRect(boxes[0]);
1.585 + nsIntRect firstDeviceRect =
1.586 + first.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
1.587 +
1.588 + for (int i=1; i<n; i++) {
1.589 + nsRect rect = nsRect(boxes[i].x1, boxes[i].y1,
1.590 + boxes[i].x2 - boxes[i].x1,
1.591 + boxes[i].y2 - boxes[i].y1);
1.592 + nsIntRect deviceRect =
1.593 + rect.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel);
1.594 +
1.595 + if (rect.y <= first.YMost()) {
1.596 + if (rect.XMost() == first.x && rect.YMost() <= first.YMost()) {
1.597 + // rect is touching on the left edge of the first rect and contained within
1.598 + // the length of its left edge
1.599 + deviceRect.SetRightEdge(firstDeviceRect.x);
1.600 + } else if (rect.x == first.XMost() && rect.YMost() <= first.YMost()) {
1.601 + // rect is touching on the right edge of the first rect and contained within
1.602 + // the length of its right edge
1.603 + deviceRect.SetLeftEdge(firstDeviceRect.XMost());
1.604 + } else if (rect.y == first.YMost()) {
1.605 + // The bottom of the first rect is on the same line as the top of rect, but
1.606 + // they aren't necessarily contained.
1.607 + if (rect.x <= first.x && rect.XMost() >= first.XMost()) {
1.608 + // The top of rect contains the bottom of the first rect
1.609 + firstDeviceRect.SetBottomEdge(deviceRect.y);
1.610 + } else if (rect.x >= first.x && rect.XMost() <= first.XMost()) {
1.611 + // The bottom of the first contains the top of rect
1.612 + deviceRect.SetTopEdge(firstDeviceRect.YMost());
1.613 + }
1.614 + }
1.615 + }
1.616 +
1.617 + boxes[i] = RectToBox(deviceRect);
1.618 + }
1.619 +
1.620 + boxes[0] = RectToBox(firstDeviceRect);
1.621 +
1.622 + pixman_region32_fini(&intRegion.mImpl.mImpl);
1.623 + // This will union all of the rectangles and runs in about O(n lg(n))
1.624 + pixman_region32_init_rects(&intRegion.mImpl.mImpl, boxes, n);
1.625 + }
1.626 + return intRegion;
1.627 +
1.628 +}
1.629 +
1.630 +// A cell's "value" is a pair consisting of
1.631 +// a) the area of the subrectangle it corresponds to, if it's in
1.632 +// aContainingRect and in the region, 0 otherwise
1.633 +// b) the area of the subrectangle it corresponds to, if it's in the region,
1.634 +// 0 otherwise
1.635 +// Addition, subtraction and identity are defined on these values in the
1.636 +// obvious way. Partial order is lexicographic.
1.637 +// A "large negative value" is defined with large negative numbers for both
1.638 +// fields of the pair. This negative value has the property that adding any
1.639 +// number of non-negative values to it always results in a negative value.
1.640 +//
1.641 +// The GetLargestRectangle algorithm works in three phases:
1.642 +// 1) Convert the region into a grid by adding vertical/horizontal lines for
1.643 +// each edge of each rectangle in the region.
1.644 +// 2) For each rectangle in the region, for each cell it contains, set that
1.645 +// cells's value as described above.
1.646 +// 3) Calculate the submatrix with the largest sum such that none of its cells
1.647 +// contain any 0s (empty regions). The rectangle represented by the
1.648 +// submatrix is the largest rectangle in the region.
1.649 +//
1.650 +// Let k be the number of rectangles in the region.
1.651 +// Let m be the height of the grid generated in step 1.
1.652 +// Let n be the width of the grid generated in step 1.
1.653 +//
1.654 +// Step 1 is O(k) in time and O(m+n) in space for the sparse grid.
1.655 +// Step 2 is O(mn) in time and O(mn) in additional space for the full grid.
1.656 +// Step 3 is O(m^2 n) in time and O(mn) in additional space
1.657 +//
1.658 +// The implementation of steps 1 and 2 are rather straightforward. However our
1.659 +// implementation of step 3 uses dynamic programming to achieve its efficiency.
1.660 +//
1.661 +// Psuedo code for step 3 is as follows where G is the grid from step 1 and A
1.662 +// is the array from step 2:
1.663 +// Phase3 = function (G, A, m, n) {
1.664 +// let (t,b,l,r,_) = MaxSum2D(A,m,n)
1.665 +// return rect(G[t],G[l],G[r],G[b]);
1.666 +// }
1.667 +// MaxSum2D = function (A, m, n) {
1.668 +// S = array(m+1,n+1)
1.669 +// S[0][i] = 0 for i in [0,n]
1.670 +// S[j][0] = 0 for j in [0,m]
1.671 +// S[j][i] = (if A[j-1][i-1] = 0 then some large negative value else A[j-1][i-1])
1.672 +// + S[j-1][n] + S[j][i-1] - S[j-1][i-1]
1.673 +//
1.674 +// // top, bottom, left, right, area
1.675 +// var maxRect = (-1, -1, -1, -1, 0);
1.676 +//
1.677 +// for all (m',m'') in [0, m]^2 {
1.678 +// let B = { S[m'][i] - S[m''][i] | 0 <= i <= n }
1.679 +// let ((l,r),area) = MaxSum1D(B,n+1)
1.680 +// if (area > maxRect.area) {
1.681 +// maxRect := (m', m'', l, r, area)
1.682 +// }
1.683 +// }
1.684 +//
1.685 +// return maxRect;
1.686 +// }
1.687 +//
1.688 +// Originally taken from Improved algorithms for the k-maximum subarray problem
1.689 +// for small k - SE Bae, T Takaoka but modified to show the explicit tracking
1.690 +// of indices and we already have the prefix sums from our one call site so
1.691 +// there's no need to construct them.
1.692 +// MaxSum1D = function (A,n) {
1.693 +// var minIdx = 0;
1.694 +// var min = 0;
1.695 +// var maxIndices = (0,0);
1.696 +// var max = 0;
1.697 +// for i in range(n) {
1.698 +// let cand = A[i] - min;
1.699 +// if (cand > max) {
1.700 +// max := cand;
1.701 +// maxIndices := (minIdx, i)
1.702 +// }
1.703 +// if (min > A[i]) {
1.704 +// min := A[i];
1.705 +// minIdx := i;
1.706 +// }
1.707 +// }
1.708 +// return (minIdx, maxIdx, max);
1.709 +// }
1.710 +
1.711 +namespace {
1.712 + // This class represents a partitioning of an axis delineated by coordinates.
1.713 + // It internally maintains a sorted array of coordinates.
1.714 + class AxisPartition {
1.715 + public:
1.716 + // Adds a new partition at the given coordinate to this partitioning. If
1.717 + // the coordinate is already present in the partitioning, this does nothing.
1.718 + void InsertCoord(nscoord c) {
1.719 + uint32_t i = mStops.IndexOfFirstElementGt(c);
1.720 + if (i == 0 || mStops[i-1] != c) {
1.721 + mStops.InsertElementAt(i, c);
1.722 + }
1.723 + }
1.724 +
1.725 + // Returns the array index of the given partition point. The partition
1.726 + // point must already be present in the partitioning.
1.727 + int32_t IndexOf(nscoord p) const {
1.728 + return mStops.BinaryIndexOf(p);
1.729 + }
1.730 +
1.731 + // Returns the partition at the given index which must be non-zero and
1.732 + // less than the number of partitions in this partitioning.
1.733 + nscoord StopAt(int32_t index) const {
1.734 + return mStops[index];
1.735 + }
1.736 +
1.737 + // Returns the size of the gap between the partition at the given index and
1.738 + // the next partition in this partitioning. If the index is the last index
1.739 + // in the partitioning, the result is undefined.
1.740 + nscoord StopSize(int32_t index) const {
1.741 + return mStops[index+1] - mStops[index];
1.742 + }
1.743 +
1.744 + // Returns the number of partitions in this partitioning.
1.745 + int32_t GetNumStops() const { return mStops.Length(); }
1.746 +
1.747 + private:
1.748 + nsTArray<nscoord> mStops;
1.749 + };
1.750 +
1.751 + const int64_t kVeryLargeNegativeNumber = 0xffff000000000000ll;
1.752 +
1.753 + struct SizePair {
1.754 + int64_t mSizeContainingRect;
1.755 + int64_t mSize;
1.756 +
1.757 + SizePair() : mSizeContainingRect(0), mSize(0) {}
1.758 +
1.759 + static SizePair VeryLargeNegative() {
1.760 + SizePair result;
1.761 + result.mSize = result.mSizeContainingRect = kVeryLargeNegativeNumber;
1.762 + return result;
1.763 + }
1.764 + SizePair& operator=(const SizePair& aOther) {
1.765 + mSizeContainingRect = aOther.mSizeContainingRect;
1.766 + mSize = aOther.mSize;
1.767 + return *this;
1.768 + }
1.769 + bool operator<(const SizePair& aOther) const {
1.770 + if (mSizeContainingRect < aOther.mSizeContainingRect)
1.771 + return true;
1.772 + if (mSizeContainingRect > aOther.mSizeContainingRect)
1.773 + return false;
1.774 + return mSize < aOther.mSize;
1.775 + }
1.776 + bool operator>(const SizePair& aOther) const {
1.777 + return aOther.operator<(*this);
1.778 + }
1.779 + SizePair operator+(const SizePair& aOther) const {
1.780 + SizePair result = *this;
1.781 + result.mSizeContainingRect += aOther.mSizeContainingRect;
1.782 + result.mSize += aOther.mSize;
1.783 + return result;
1.784 + }
1.785 + SizePair operator-(const SizePair& aOther) const {
1.786 + SizePair result = *this;
1.787 + result.mSizeContainingRect -= aOther.mSizeContainingRect;
1.788 + result.mSize -= aOther.mSize;
1.789 + return result;
1.790 + }
1.791 + };
1.792 +
1.793 + // Returns the sum and indices of the subarray with the maximum sum of the
1.794 + // given array (A,n), assuming the array is already in prefix sum form.
1.795 + SizePair MaxSum1D(const nsTArray<SizePair> &A, int32_t n,
1.796 + int32_t *minIdx, int32_t *maxIdx) {
1.797 + // The min/max indicies of the largest subarray found so far
1.798 + SizePair min, max;
1.799 + int32_t currentMinIdx = 0;
1.800 +
1.801 + *minIdx = 0;
1.802 + *maxIdx = 0;
1.803 +
1.804 + // Because we're given the array in prefix sum form, we know the first
1.805 + // element is 0
1.806 + for(int32_t i = 1; i < n; i++) {
1.807 + SizePair cand = A[i] - min;
1.808 + if (cand > max) {
1.809 + max = cand;
1.810 + *minIdx = currentMinIdx;
1.811 + *maxIdx = i;
1.812 + }
1.813 + if (min > A[i]) {
1.814 + min = A[i];
1.815 + currentMinIdx = i;
1.816 + }
1.817 + }
1.818 +
1.819 + return max;
1.820 + }
1.821 +}
1.822 +
1.823 +nsRect nsRegion::GetLargestRectangle (const nsRect& aContainingRect) const {
1.824 + nsRect bestRect;
1.825 +
1.826 + if (GetNumRects() <= 1) {
1.827 + bestRect = GetBounds();
1.828 + return bestRect;
1.829 + }
1.830 +
1.831 + AxisPartition xaxis, yaxis;
1.832 +
1.833 + // Step 1: Calculate the grid lines
1.834 + nsRegionRectIterator iter(*this);
1.835 + const nsRect *currentRect;
1.836 + while ((currentRect = iter.Next())) {
1.837 + xaxis.InsertCoord(currentRect->x);
1.838 + xaxis.InsertCoord(currentRect->XMost());
1.839 + yaxis.InsertCoord(currentRect->y);
1.840 + yaxis.InsertCoord(currentRect->YMost());
1.841 + }
1.842 + if (!aContainingRect.IsEmpty()) {
1.843 + xaxis.InsertCoord(aContainingRect.x);
1.844 + xaxis.InsertCoord(aContainingRect.XMost());
1.845 + yaxis.InsertCoord(aContainingRect.y);
1.846 + yaxis.InsertCoord(aContainingRect.YMost());
1.847 + }
1.848 +
1.849 + // Step 2: Fill out the grid with the areas
1.850 + // Note: due to the ordering of rectangles in the region, it is not always
1.851 + // possible to combine steps 2 and 3 so we don't try to be clever.
1.852 + int32_t matrixHeight = yaxis.GetNumStops() - 1;
1.853 + int32_t matrixWidth = xaxis.GetNumStops() - 1;
1.854 + int32_t matrixSize = matrixHeight * matrixWidth;
1.855 + nsTArray<SizePair> areas(matrixSize);
1.856 + areas.SetLength(matrixSize);
1.857 +
1.858 + iter.Reset();
1.859 + while ((currentRect = iter.Next())) {
1.860 + int32_t xstart = xaxis.IndexOf(currentRect->x);
1.861 + int32_t xend = xaxis.IndexOf(currentRect->XMost());
1.862 + int32_t y = yaxis.IndexOf(currentRect->y);
1.863 + int32_t yend = yaxis.IndexOf(currentRect->YMost());
1.864 +
1.865 + for (; y < yend; y++) {
1.866 + nscoord height = yaxis.StopSize(y);
1.867 + for (int32_t x = xstart; x < xend; x++) {
1.868 + nscoord width = xaxis.StopSize(x);
1.869 + int64_t size = width*int64_t(height);
1.870 + if (currentRect->Intersects(aContainingRect)) {
1.871 + areas[y*matrixWidth+x].mSizeContainingRect = size;
1.872 + }
1.873 + areas[y*matrixWidth+x].mSize = size;
1.874 + }
1.875 + }
1.876 + }
1.877 +
1.878 + // Step 3: Find the maximum submatrix sum that does not contain a rectangle
1.879 + {
1.880 + // First get the prefix sum array
1.881 + int32_t m = matrixHeight + 1;
1.882 + int32_t n = matrixWidth + 1;
1.883 + nsTArray<SizePair> pareas(m*n);
1.884 + pareas.SetLength(m*n);
1.885 + for (int32_t y = 1; y < m; y++) {
1.886 + for (int32_t x = 1; x < n; x++) {
1.887 + SizePair area = areas[(y-1)*matrixWidth+x-1];
1.888 + if (!area.mSize) {
1.889 + area = SizePair::VeryLargeNegative();
1.890 + }
1.891 + area = area + pareas[ y*n+x-1]
1.892 + + pareas[(y-1)*n+x ]
1.893 + - pareas[(y-1)*n+x-1];
1.894 + pareas[y*n+x] = area;
1.895 + }
1.896 + }
1.897 +
1.898 + // No longer need the grid
1.899 + areas.SetLength(0);
1.900 +
1.901 + SizePair bestArea;
1.902 + struct {
1.903 + int32_t left, top, right, bottom;
1.904 + } bestRectIndices = { 0, 0, 0, 0 };
1.905 + for (int32_t m1 = 0; m1 < m; m1++) {
1.906 + for (int32_t m2 = m1+1; m2 < m; m2++) {
1.907 + nsTArray<SizePair> B;
1.908 + B.SetLength(n);
1.909 + for (int32_t i = 0; i < n; i++) {
1.910 + B[i] = pareas[m2*n+i] - pareas[m1*n+i];
1.911 + }
1.912 + int32_t minIdx, maxIdx;
1.913 + SizePair area = MaxSum1D(B, n, &minIdx, &maxIdx);
1.914 + if (area > bestArea) {
1.915 + bestRectIndices.left = minIdx;
1.916 + bestRectIndices.top = m1;
1.917 + bestRectIndices.right = maxIdx;
1.918 + bestRectIndices.bottom = m2;
1.919 + bestArea = area;
1.920 + }
1.921 + }
1.922 + }
1.923 +
1.924 + bestRect.MoveTo(xaxis.StopAt(bestRectIndices.left),
1.925 + yaxis.StopAt(bestRectIndices.top));
1.926 + bestRect.SizeTo(xaxis.StopAt(bestRectIndices.right) - bestRect.x,
1.927 + yaxis.StopAt(bestRectIndices.bottom) - bestRect.y);
1.928 + }
1.929 +
1.930 + return bestRect;
1.931 +}
1.932 +
1.933 +nsCString
1.934 +nsRegion::ToString() const {
1.935 + nsCString result;
1.936 + result.AppendLiteral("[");
1.937 +
1.938 + int n;
1.939 + pixman_box32_t *boxes = pixman_region32_rectangles(const_cast<pixman_region32_t*>(&mImpl), &n);
1.940 + for (int i=0; i<n; i++) {
1.941 + if (i != 0) {
1.942 + result.AppendLiteral("; ");
1.943 + }
1.944 + result.Append(nsPrintfCString("%d,%d,%d,%d", boxes[i].x1, boxes[i].y1, boxes[i].x2, boxes[i].y2));
1.945 +
1.946 + }
1.947 + result.AppendLiteral("]");
1.948 +
1.949 + return result;
1.950 +}
1.951 +
1.952 +
1.953 +nsRegion nsIntRegion::ToAppUnits (nscoord aAppUnitsPerPixel) const
1.954 +{
1.955 + nsRegion result;
1.956 + nsIntRegionRectIterator rgnIter(*this);
1.957 + const nsIntRect* currentRect;
1.958 + while ((currentRect = rgnIter.Next())) {
1.959 + nsRect appRect = currentRect->ToAppUnits(aAppUnitsPerPixel);
1.960 + result.Or(result, appRect);
1.961 + }
1.962 + return result;
1.963 +}
