The Tor Browser / file comparison
comparison: gfx/src/nsRegion.cpp
gfx/src/nsRegion.cpp
- branch
- TOR_BUG_9701
- changeset 8
- 97036ab72558
equal
deleted
inserted
replaced
| -1:000000000000 | 0:f51918fc43ed |
|---|---|
| 1 /* This Source Code Form is subject to the terms of the Mozilla Public | |
| 2 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
| 4 | |
| 5 | |
| 6 #include "nsRegion.h" | |
| 7 #include "nsPrintfCString.h" | |
| 8 #include "nsTArray.h" | |
| 9 | |
| 10 | |
| 11 bool nsRegion::Contains(const nsRegion& aRgn) const | |
| 12 { | |
| 13 // XXX this could be made faster | |
| 14 nsRegionRectIterator iter(aRgn); | |
| 15 while (const nsRect* r = iter.Next()) { | |
| 16 if (!Contains (*r)) { | |
| 17 return false; | |
| 18 } | |
| 19 } | |
| 20 return true; | |
| 21 } | |
| 22 | |
| 23 bool nsRegion::Intersects(const nsRect& aRect) const | |
| 24 { | |
| 25 // XXX this could be made faster | |
| 26 nsRegionRectIterator iter(*this); | |
| 27 while (const nsRect* r = iter.Next()) { | |
| 28 if (r->Intersects(aRect)) { | |
| 29 return true; | |
| 30 } | |
| 31 } | |
| 32 return false; | |
| 33 } | |
| 34 | |
| 35 void nsRegion::Inflate(const nsMargin& aMargin) | |
| 36 { | |
| 37 int n; | |
| 38 pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n); | |
| 39 for (int i=0; i<n; i++) { | |
| 40 nsRect rect = BoxToRect(boxes[i]); | |
| 41 rect.Inflate(aMargin); | |
| 42 boxes[i] = RectToBox(rect); | |
| 43 } | |
| 44 | |
| 45 pixman_region32_t region; | |
| 46 // This will union all of the rectangles and runs in about O(n lg(n)) | |
| 47 pixman_region32_init_rects(®ion, boxes, n); | |
| 48 | |
| 49 pixman_region32_fini(&mImpl); | |
| 50 mImpl = region; | |
| 51 } | |
| 52 | |
| 53 void nsRegion::SimplifyOutward (uint32_t aMaxRects) | |
| 54 { | |
| 55 MOZ_ASSERT(aMaxRects >= 1, "Invalid max rect count"); | |
| 56 | |
| 57 if (GetNumRects() <= aMaxRects) | |
| 58 return; | |
| 59 | |
| 60 pixman_box32_t *boxes; | |
| 61 int n; | |
| 62 boxes = pixman_region32_rectangles(&mImpl, &n); | |
| 63 | |
| 64 // Try combining rects in horizontal bands into a single rect | |
| 65 int dest = 0; | |
| 66 for (int src = 1; src < n; src++) | |
| 67 { | |
| 68 // The goal here is to try to keep groups of rectangles that are vertically | |
| 69 // discontiguous as separate rectangles in the final region. This is | |
| 70 // simple and fast to implement and page contents tend to vary more | |
| 71 // vertically than horizontally (which is why our rectangles are stored | |
| 72 // sorted by y-coordinate, too). | |
| 73 // | |
| 74 // Note: if boxes share y1 because of the canonical representation they | |
| 75 // will share y2 | |
| 76 while ((src < (n)) && boxes[dest].y1 == boxes[src].y1) { | |
| 77 // merge box[i] and box[i+1] | |
| 78 boxes[dest].x2 = boxes[src].x2; | |
| 79 src++; | |
| 80 } | |
| 81 if (src < n) { | |
| 82 dest++; | |
| 83 boxes[dest] = boxes[src]; | |
| 84 } | |
| 85 } | |
| 86 | |
| 87 uint32_t reducedCount = dest+1; | |
| 88 // pixman has a special representation for | |
| 89 // regions of 1 rectangle. So just use the | |
| 90 // bounds in that case | |
| 91 if (reducedCount > 1 && reducedCount <= aMaxRects) { | |
| 92 // reach into pixman and lower the number | |
| 93 // of rects stored in data. | |
| 94 mImpl.data->numRects = reducedCount; | |
| 95 } else { | |
| 96 *this = GetBounds(); | |
| 97 } | |
| 98 } | |
| 99 | |
| 100 // compute the covered area difference between two rows. | |
| 101 // by iterating over both rows simultaneously and adding up | |
| 102 // the additional increase in area caused by extending each | |
| 103 // of the rectangles to the combined height of both rows | |
| 104 static uint32_t ComputeMergedAreaIncrease(pixman_box32_t *topRects, | |
| 105 pixman_box32_t *topRectsEnd, | |
| 106 pixman_box32_t *bottomRects, | |
| 107 pixman_box32_t *bottomRectsEnd) | |
| 108 { | |
| 109 uint32_t totalArea = 0; | |
| 110 struct pt { | |
| 111 int32_t x, y; | |
| 112 }; | |
| 113 | |
| 114 | |
| 115 pt *i = (pt*)topRects; | |
| 116 pt *end_i = (pt*)topRectsEnd; | |
| 117 pt *j = (pt*)bottomRects; | |
| 118 pt *end_j = (pt*)bottomRectsEnd; | |
| 119 bool top = false; | |
| 120 bool bottom = false; | |
| 121 | |
| 122 int cur_x = i->x; | |
| 123 bool top_next = top; | |
| 124 bool bottom_next = bottom; | |
| 125 //XXX: we could probably simplify this condition and perhaps move it into the loop below | |
| 126 if (j->x < cur_x) { | |
| 127 cur_x = j->x; | |
| 128 j++; | |
| 129 bottom_next = !bottom; | |
| 130 } else if (j->x == cur_x) { | |
| 131 i++; | |
| 132 top_next = !top; | |
| 133 bottom_next = !bottom; | |
| 134 j++; | |
| 135 } else { | |
| 136 top_next = !top; | |
| 137 i++; | |
| 138 } | |
| 139 | |
| 140 int topRectsHeight = topRects->y2 - topRects->y1; | |
| 141 int bottomRectsHeight = bottomRects->y2 - bottomRects->y1; | |
| 142 int inbetweenHeight = bottomRects->y1 - topRects->y2; | |
| 143 int width = cur_x; | |
| 144 // top and bottom are the in-status to the left of cur_x | |
| 145 do { | |
| 146 if (top && !bottom) { | |
| 147 totalArea += (inbetweenHeight+bottomRectsHeight)*width; | |
| 148 } else if (bottom && !top) { | |
| 149 totalArea += (inbetweenHeight+topRectsHeight)*width; | |
| 150 } else if (bottom && top) { | |
| 151 totalArea += (inbetweenHeight)*width; | |
| 152 } | |
| 153 top = top_next; | |
| 154 bottom = bottom_next; | |
| 155 // find the next edge | |
| 156 if (i->x < j->x) { | |
| 157 top_next = !top; | |
| 158 width = i->x - cur_x; | |
| 159 cur_x = i->x; | |
| 160 i++; | |
| 161 } else if (j->x < i->x) { | |
| 162 bottom_next = !bottom; | |
| 163 width = j->x - cur_x; | |
| 164 cur_x = j->x; | |
| 165 j++; | |
| 166 } else { // i->x == j->x | |
| 167 top_next = !top; | |
| 168 bottom_next = !bottom; | |
| 169 width = i->x - cur_x; | |
| 170 cur_x = i->x; | |
| 171 i++; | |
| 172 j++; | |
| 173 } | |
| 174 } while (i < end_i && j < end_j); | |
| 175 | |
| 176 // handle any remaining rects | |
| 177 while (i < end_i) { | |
| 178 width = i->x - cur_x; | |
| 179 cur_x = i->x; | |
| 180 i++; | |
| 181 if (top) | |
| 182 totalArea += (inbetweenHeight+bottomRectsHeight)*width; | |
| 183 top = !top; | |
| 184 } | |
| 185 | |
| 186 while (j < end_j) { | |
| 187 width = j->x - cur_x; | |
| 188 cur_x = j->x; | |
| 189 j++; | |
| 190 if (bottom) | |
| 191 totalArea += (inbetweenHeight+topRectsHeight)*width; | |
| 192 bottom = !bottom; | |
| 193 } | |
| 194 return totalArea; | |
| 195 } | |
| 196 | |
| 197 static pixman_box32_t * | |
| 198 CopyRow(pixman_box32_t *dest_it, pixman_box32_t *src_start, pixman_box32_t *src_end) | |
| 199 { | |
| 200 // XXX: std::copy | |
| 201 pixman_box32_t *src_it = src_start; | |
| 202 while (src_it < src_end) { | |
| 203 *dest_it++ = *src_it++; | |
| 204 } | |
| 205 return dest_it; | |
| 206 } | |
| 207 | |
| 208 static pixman_box32_t * | |
| 209 MergeRects(pixman_box32_t *topRects, pixman_box32_t *topRectsEnd, | |
| 210 pixman_box32_t *bottomRects, pixman_box32_t *bottomRectsEnd, | |
| 211 pixman_box32_t *tmpRect) | |
| 212 { | |
| 213 struct pt { | |
| 214 int32_t x, y; | |
| 215 }; | |
| 216 | |
| 217 pixman_box32_t *rect; | |
| 218 // merge the two spans of rects | |
| 219 pt *i = (pt*)topRects; | |
| 220 pt *end_i = (pt*)topRectsEnd; | |
| 221 pt *j = (pt*)bottomRects; | |
| 222 pt *end_j = (pt*)bottomRectsEnd; | |
| 223 bool top; | |
| 224 bool bottom; | |
| 225 | |
| 226 int cur_x = i->x; | |
| 227 int32_t y1 = topRects->y1; | |
| 228 int32_t y2 = bottomRects->y2; | |
| 229 if (j->x < cur_x) { | |
| 230 top = false; | |
| 231 bottom = true; | |
| 232 cur_x = j->x; | |
| 233 j++; | |
| 234 } else if (j->x == cur_x) { | |
| 235 top = true; | |
| 236 bottom = true; | |
| 237 i++; | |
| 238 j++; | |
| 239 } else { | |
| 240 top = true; | |
| 241 bottom = false; | |
| 242 i++; | |
| 243 } | |
| 244 | |
| 245 rect = tmpRect; | |
| 246 bool started = false; | |
| 247 do { | |
| 248 if (started && !top && !bottom) { | |
| 249 rect->x2 = cur_x; | |
| 250 rect->y2 = y2; | |
| 251 rect++; | |
| 252 started = false; | |
| 253 } else if (!started) { | |
| 254 rect->x1 = cur_x; | |
| 255 rect->y1 = y1; | |
| 256 started = true; | |
| 257 } | |
| 258 | |
| 259 if (i >= end_i || j >= end_j) | |
| 260 break; | |
| 261 | |
| 262 if (i->x < j->x) { | |
| 263 top = !top; | |
| 264 cur_x = i->x; | |
| 265 i++; | |
| 266 } else if (j->x < i->x) { | |
| 267 bottom = !bottom; | |
| 268 cur_x = j->x; | |
| 269 j++; | |
| 270 } else { // i->x == j->x | |
| 271 top = !top; | |
| 272 bottom = !bottom; | |
| 273 cur_x = i->x; | |
| 274 i++; | |
| 275 j++; | |
| 276 } | |
| 277 } while (true); | |
| 278 | |
| 279 // handle any remaining rects | |
| 280 while (i < end_i) { | |
| 281 top = !top; | |
| 282 cur_x = i->x; | |
| 283 i++; | |
| 284 if (!top) { | |
| 285 rect->x2 = cur_x; | |
| 286 rect->y2 = y2; | |
| 287 rect++; | |
| 288 } else { | |
| 289 rect->x1 = cur_x; | |
| 290 rect->y1 = y1; | |
| 291 } | |
| 292 } | |
| 293 | |
| 294 while (j < end_j) { | |
| 295 bottom = !bottom; | |
| 296 cur_x = j->x; | |
| 297 j++; | |
| 298 if (!bottom) { | |
| 299 rect->x2 = cur_x; | |
| 300 rect->y2 = y2; | |
| 301 rect++; | |
| 302 } else { | |
| 303 rect->x1 = cur_x; | |
| 304 rect->y1 = y1; | |
| 305 } | |
| 306 } | |
| 307 return rect; | |
| 308 } | |
| 309 | |
| 310 void nsRegion::SimplifyOutwardByArea(uint32_t aThreshold) | |
| 311 { | |
| 312 | |
| 313 pixman_box32_t *boxes; | |
| 314 int n; | |
| 315 boxes = pixman_region32_rectangles(&mImpl, &n); | |
| 316 | |
| 317 // if we have no rectangles then we're done | |
| 318 if (!n) | |
| 319 return; | |
| 320 | |
| 321 pixman_box32_t *end = boxes + n; | |
| 322 pixman_box32_t *topRectsEnd = boxes+1; | |
| 323 pixman_box32_t *topRects = boxes; | |
| 324 | |
| 325 // we need some temporary storage for merging both rows of rectangles | |
| 326 nsAutoTArray<pixman_box32_t, 10> tmpStorage; | |
| 327 tmpStorage.SetCapacity(n); | |
| 328 pixman_box32_t *tmpRect = tmpStorage.Elements(); | |
| 329 | |
| 330 pixman_box32_t *destRect = boxes; | |
| 331 pixman_box32_t *rect = tmpRect; | |
| 332 // find the end of the first span of rectangles | |
| 333 while (topRectsEnd < end && topRectsEnd->y1 == topRects->y1) { | |
| 334 topRectsEnd++; | |
| 335 } | |
| 336 | |
| 337 // if we only have one row we are done | |
| 338 if (topRectsEnd == end) | |
| 339 return; | |
| 340 | |
| 341 pixman_box32_t *bottomRects = topRectsEnd; | |
| 342 pixman_box32_t *bottomRectsEnd = bottomRects+1; | |
| 343 do { | |
| 344 // find the end of the bottom span of rectangles | |
| 345 while (bottomRectsEnd < end && bottomRectsEnd->y1 == bottomRects->y1) { | |
| 346 bottomRectsEnd++; | |
| 347 } | |
| 348 uint32_t totalArea = ComputeMergedAreaIncrease(topRects, topRectsEnd, | |
| 349 bottomRects, bottomRectsEnd); | |
| 350 | |
| 351 if (totalArea <= aThreshold) { | |
| 352 // merge the rects into tmpRect | |
| 353 rect = MergeRects(topRects, topRectsEnd, bottomRects, bottomRectsEnd, tmpRect); | |
| 354 | |
| 355 // copy the merged rects back into the destination | |
| 356 topRectsEnd = CopyRow(destRect, tmpRect, rect); | |
| 357 topRects = destRect; | |
| 358 bottomRects = bottomRectsEnd; | |
| 359 destRect = topRects; | |
| 360 } else { | |
| 361 // copy the unmerged rects | |
| 362 destRect = CopyRow(destRect, topRects, topRectsEnd); | |
| 363 | |
| 364 topRects = bottomRects; | |
| 365 topRectsEnd = bottomRectsEnd; | |
| 366 bottomRects = bottomRectsEnd; | |
| 367 if (bottomRectsEnd == end) { | |
| 368 // copy the last row when we are done | |
| 369 topRectsEnd = CopyRow(destRect, topRects, topRectsEnd); | |
| 370 } | |
| 371 } | |
| 372 } while (bottomRectsEnd != end); | |
| 373 | |
| 374 | |
| 375 uint32_t reducedCount = topRectsEnd - pixman_region32_rectangles(&this->mImpl, &n); | |
| 376 // pixman has a special representation for | |
| 377 // regions of 1 rectangle. So just use the | |
| 378 // bounds in that case | |
| 379 if (reducedCount > 1) { | |
| 380 // reach into pixman and lower the number | |
| 381 // of rects stored in data. | |
| 382 this->mImpl.data->numRects = reducedCount; | |
| 383 } else { | |
| 384 *this = GetBounds(); | |
| 385 } | |
| 386 } | |
| 387 | |
| 388 | |
| 389 void nsRegion::SimplifyInward (uint32_t aMaxRects) | |
| 390 { | |
| 391 NS_ASSERTION(aMaxRects >= 1, "Invalid max rect count"); | |
| 392 | |
| 393 if (GetNumRects() <= aMaxRects) | |
| 394 return; | |
| 395 | |
| 396 SetEmpty(); | |
| 397 } | |
| 398 | |
| 399 uint64_t nsRegion::Area () const | |
| 400 { | |
| 401 uint64_t area = 0; | |
| 402 nsRegionRectIterator iter(*this); | |
| 403 const nsRect* r; | |
| 404 while ((r = iter.Next()) != nullptr) { | |
| 405 area += uint64_t(r->width)*r->height; | |
| 406 } | |
| 407 return area; | |
| 408 } | |
| 409 | |
| 410 nsRegion& nsRegion::ScaleRoundOut (float aXScale, float aYScale) | |
| 411 { | |
| 412 int n; | |
| 413 pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n); | |
| 414 for (int i=0; i<n; i++) { | |
| 415 nsRect rect = BoxToRect(boxes[i]); | |
| 416 rect.ScaleRoundOut(aXScale, aYScale); | |
| 417 boxes[i] = RectToBox(rect); | |
| 418 } | |
| 419 | |
| 420 pixman_region32_t region; | |
| 421 // This will union all of the rectangles and runs in about O(n lg(n)) | |
| 422 pixman_region32_init_rects(®ion, boxes, n); | |
| 423 | |
| 424 pixman_region32_fini(&mImpl); | |
| 425 mImpl = region; | |
| 426 return *this; | |
| 427 } | |
| 428 | |
| 429 nsRegion& nsRegion::ScaleInverseRoundOut (float aXScale, float aYScale) | |
| 430 { | |
| 431 int n; | |
| 432 pixman_box32_t *boxes = pixman_region32_rectangles(&mImpl, &n); | |
| 433 for (int i=0; i<n; i++) { | |
| 434 nsRect rect = BoxToRect(boxes[i]); | |
| 435 rect.ScaleInverseRoundOut(aXScale, aYScale); | |
| 436 boxes[i] = RectToBox(rect); | |
| 437 } | |
| 438 | |
| 439 pixman_region32_t region; | |
| 440 // This will union all of the rectangles and runs in about O(n lg(n)) | |
| 441 pixman_region32_init_rects(®ion, boxes, n); | |
| 442 | |
| 443 pixman_region32_fini(&mImpl); | |
| 444 mImpl = region; | |
| 445 return *this; | |
| 446 } | |
| 447 | |
| 448 nsRegion nsRegion::ConvertAppUnitsRoundOut (int32_t aFromAPP, int32_t aToAPP) const | |
| 449 { | |
| 450 if (aFromAPP == aToAPP) { | |
| 451 return *this; | |
| 452 } | |
| 453 | |
| 454 nsRegion region = *this; | |
| 455 int n; | |
| 456 pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n); | |
| 457 for (int i=0; i<n; i++) { | |
| 458 nsRect rect = BoxToRect(boxes[i]); | |
| 459 rect = rect.ConvertAppUnitsRoundOut(aFromAPP, aToAPP); | |
| 460 boxes[i] = RectToBox(rect); | |
| 461 } | |
| 462 | |
| 463 pixman_region32_t pixmanRegion; | |
| 464 // This will union all of the rectangles and runs in about O(n lg(n)) | |
| 465 pixman_region32_init_rects(&pixmanRegion, boxes, n); | |
| 466 | |
| 467 pixman_region32_fini(®ion.mImpl); | |
| 468 region.mImpl = pixmanRegion; | |
| 469 return region; | |
| 470 } | |
| 471 | |
| 472 nsRegion nsRegion::ConvertAppUnitsRoundIn (int32_t aFromAPP, int32_t aToAPP) const | |
| 473 { | |
| 474 if (aFromAPP == aToAPP) { | |
| 475 return *this; | |
| 476 } | |
| 477 | |
| 478 nsRegion region = *this; | |
| 479 int n; | |
| 480 pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n); | |
| 481 for (int i=0; i<n; i++) { | |
| 482 nsRect rect = BoxToRect(boxes[i]); | |
| 483 rect = rect.ConvertAppUnitsRoundIn(aFromAPP, aToAPP); | |
| 484 boxes[i] = RectToBox(rect); | |
| 485 } | |
| 486 | |
| 487 pixman_region32_t pixmanRegion; | |
| 488 // This will union all of the rectangles and runs in about O(n lg(n)) | |
| 489 pixman_region32_init_rects(&pixmanRegion, boxes, n); | |
| 490 | |
| 491 pixman_region32_fini(®ion.mImpl); | |
| 492 region.mImpl = pixmanRegion; | |
| 493 return region; | |
| 494 } | |
| 495 | |
| 496 nsIntRegion nsRegion::ToPixels (nscoord aAppUnitsPerPixel, bool aOutsidePixels) const | |
| 497 { | |
| 498 nsRegion region = *this; | |
| 499 int n; | |
| 500 pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n); | |
| 501 for (int i=0; i<n; i++) { | |
| 502 nsRect rect = BoxToRect(boxes[i]); | |
| 503 nsIntRect deviceRect; | |
| 504 if (aOutsidePixels) | |
| 505 deviceRect = rect.ToOutsidePixels(aAppUnitsPerPixel); | |
| 506 else | |
| 507 deviceRect = rect.ToNearestPixels(aAppUnitsPerPixel); | |
| 508 | |
| 509 boxes[i] = RectToBox(deviceRect); | |
| 510 } | |
| 511 | |
| 512 nsIntRegion intRegion; | |
| 513 pixman_region32_fini(&intRegion.mImpl.mImpl); | |
| 514 // This will union all of the rectangles and runs in about O(n lg(n)) | |
| 515 pixman_region32_init_rects(&intRegion.mImpl.mImpl, boxes, n); | |
| 516 | |
| 517 return intRegion; | |
| 518 } | |
| 519 | |
| 520 nsIntRegion nsRegion::ToOutsidePixels (nscoord aAppUnitsPerPixel) const | |
| 521 { | |
| 522 return ToPixels(aAppUnitsPerPixel, true); | |
| 523 } | |
| 524 | |
| 525 nsIntRegion nsRegion::ToNearestPixels (nscoord aAppUnitsPerPixel) const | |
| 526 { | |
| 527 return ToPixels(aAppUnitsPerPixel, false); | |
| 528 } | |
| 529 | |
| 530 nsIntRegion nsRegion::ScaleToNearestPixels (float aScaleX, float aScaleY, | |
| 531 nscoord aAppUnitsPerPixel) const | |
| 532 { | |
| 533 nsIntRegion result; | |
| 534 nsRegionRectIterator rgnIter(*this); | |
| 535 const nsRect* currentRect; | |
| 536 while ((currentRect = rgnIter.Next())) { | |
| 537 nsIntRect deviceRect = | |
| 538 currentRect->ScaleToNearestPixels(aScaleX, aScaleY, aAppUnitsPerPixel); | |
| 539 result.Or(result, deviceRect); | |
| 540 } | |
| 541 return result; | |
| 542 } | |
| 543 | |
| 544 nsIntRegion nsRegion::ScaleToOutsidePixels (float aScaleX, float aScaleY, | |
| 545 nscoord aAppUnitsPerPixel) const | |
| 546 { | |
| 547 nsIntRegion result; | |
| 548 nsRegionRectIterator rgnIter(*this); | |
| 549 const nsRect* currentRect; | |
| 550 while ((currentRect = rgnIter.Next())) { | |
| 551 nsIntRect deviceRect = | |
| 552 currentRect->ScaleToOutsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel); | |
| 553 result.Or(result, deviceRect); | |
| 554 } | |
| 555 return result; | |
| 556 } | |
| 557 | |
| 558 nsIntRegion nsRegion::ScaleToInsidePixels (float aScaleX, float aScaleY, | |
| 559 nscoord aAppUnitsPerPixel) const | |
| 560 { | |
| 561 /* When scaling a rect, walk forward through the rect list up until the y value is greater | |
| 562 * than the current rect's YMost() value. | |
| 563 * | |
| 564 * For each rect found, check if the rects have a touching edge (in unscaled coordinates), | |
| 565 * and if one edge is entirely contained within the other. | |
| 566 * | |
| 567 * If it is, then the contained edge can be moved (in scaled pixels) to ensure that no | |
| 568 * gap exists. | |
| 569 * | |
| 570 * Since this could be potentially expensive - O(n^2), we only attempt this algorithm | |
| 571 * for the first rect. | |
| 572 */ | |
| 573 | |
| 574 // make a copy of this region so that we can mutate it in place | |
| 575 nsRegion region = *this; | |
| 576 int n; | |
| 577 pixman_box32_t *boxes = pixman_region32_rectangles(®ion.mImpl, &n); | |
| 578 | |
| 579 nsIntRegion intRegion; | |
| 580 if (n) { | |
| 581 nsRect first = BoxToRect(boxes[0]); | |
| 582 nsIntRect firstDeviceRect = | |
| 583 first.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel); | |
| 584 | |
| 585 for (int i=1; i<n; i++) { | |
| 586 nsRect rect = nsRect(boxes[i].x1, boxes[i].y1, | |
| 587 boxes[i].x2 - boxes[i].x1, | |
| 588 boxes[i].y2 - boxes[i].y1); | |
| 589 nsIntRect deviceRect = | |
| 590 rect.ScaleToInsidePixels(aScaleX, aScaleY, aAppUnitsPerPixel); | |
| 591 | |
| 592 if (rect.y <= first.YMost()) { | |
| 593 if (rect.XMost() == first.x && rect.YMost() <= first.YMost()) { | |
| 594 // rect is touching on the left edge of the first rect and contained within | |
| 595 // the length of its left edge | |
| 596 deviceRect.SetRightEdge(firstDeviceRect.x); | |
| 597 } else if (rect.x == first.XMost() && rect.YMost() <= first.YMost()) { | |
| 598 // rect is touching on the right edge of the first rect and contained within | |
| 599 // the length of its right edge | |
| 600 deviceRect.SetLeftEdge(firstDeviceRect.XMost()); | |
| 601 } else if (rect.y == first.YMost()) { | |
| 602 // The bottom of the first rect is on the same line as the top of rect, but | |
| 603 // they aren't necessarily contained. | |
| 604 if (rect.x <= first.x && rect.XMost() >= first.XMost()) { | |
| 605 // The top of rect contains the bottom of the first rect | |
| 606 firstDeviceRect.SetBottomEdge(deviceRect.y); | |
| 607 } else if (rect.x >= first.x && rect.XMost() <= first.XMost()) { | |
| 608 // The bottom of the first contains the top of rect | |
| 609 deviceRect.SetTopEdge(firstDeviceRect.YMost()); | |
| 610 } | |
| 611 } | |
| 612 } | |
| 613 | |
| 614 boxes[i] = RectToBox(deviceRect); | |
| 615 } | |
| 616 | |
| 617 boxes[0] = RectToBox(firstDeviceRect); | |
| 618 | |
| 619 pixman_region32_fini(&intRegion.mImpl.mImpl); | |
| 620 // This will union all of the rectangles and runs in about O(n lg(n)) | |
| 621 pixman_region32_init_rects(&intRegion.mImpl.mImpl, boxes, n); | |
| 622 } | |
| 623 return intRegion; | |
| 624 | |
| 625 } | |
| 626 | |
| 627 // A cell's "value" is a pair consisting of | |
| 628 // a) the area of the subrectangle it corresponds to, if it's in | |
| 629 // aContainingRect and in the region, 0 otherwise | |
| 630 // b) the area of the subrectangle it corresponds to, if it's in the region, | |
| 631 // 0 otherwise | |
| 632 // Addition, subtraction and identity are defined on these values in the | |
| 633 // obvious way. Partial order is lexicographic. | |
| 634 // A "large negative value" is defined with large negative numbers for both | |
| 635 // fields of the pair. This negative value has the property that adding any | |
| 636 // number of non-negative values to it always results in a negative value. | |
| 637 // | |
| 638 // The GetLargestRectangle algorithm works in three phases: | |
| 639 // 1) Convert the region into a grid by adding vertical/horizontal lines for | |
| 640 // each edge of each rectangle in the region. | |
| 641 // 2) For each rectangle in the region, for each cell it contains, set that | |
| 642 // cells's value as described above. | |
| 643 // 3) Calculate the submatrix with the largest sum such that none of its cells | |
| 644 // contain any 0s (empty regions). The rectangle represented by the | |
| 645 // submatrix is the largest rectangle in the region. | |
| 646 // | |
| 647 // Let k be the number of rectangles in the region. | |
| 648 // Let m be the height of the grid generated in step 1. | |
| 649 // Let n be the width of the grid generated in step 1. | |
| 650 // | |
| 651 // Step 1 is O(k) in time and O(m+n) in space for the sparse grid. | |
| 652 // Step 2 is O(mn) in time and O(mn) in additional space for the full grid. | |
| 653 // Step 3 is O(m^2 n) in time and O(mn) in additional space | |
| 654 // | |
| 655 // The implementation of steps 1 and 2 are rather straightforward. However our | |
| 656 // implementation of step 3 uses dynamic programming to achieve its efficiency. | |
| 657 // | |
| 658 // Psuedo code for step 3 is as follows where G is the grid from step 1 and A | |
| 659 // is the array from step 2: | |
| 660 // Phase3 = function (G, A, m, n) { | |
| 661 // let (t,b,l,r,_) = MaxSum2D(A,m,n) | |
| 662 // return rect(G[t],G[l],G[r],G[b]); | |
| 663 // } | |
| 664 // MaxSum2D = function (A, m, n) { | |
| 665 // S = array(m+1,n+1) | |
| 666 // S[0][i] = 0 for i in [0,n] | |
| 667 // S[j][0] = 0 for j in [0,m] | |
| 668 // S[j][i] = (if A[j-1][i-1] = 0 then some large negative value else A[j-1][i-1]) | |
| 669 // + S[j-1][n] + S[j][i-1] - S[j-1][i-1] | |
| 670 // | |
| 671 // // top, bottom, left, right, area | |
| 672 // var maxRect = (-1, -1, -1, -1, 0); | |
| 673 // | |
| 674 // for all (m',m'') in [0, m]^2 { | |
| 675 // let B = { S[m'][i] - S[m''][i] | 0 <= i <= n } | |
| 676 // let ((l,r),area) = MaxSum1D(B,n+1) | |
| 677 // if (area > maxRect.area) { | |
| 678 // maxRect := (m', m'', l, r, area) | |
| 679 // } | |
| 680 // } | |
| 681 // | |
| 682 // return maxRect; | |
| 683 // } | |
| 684 // | |
| 685 // Originally taken from Improved algorithms for the k-maximum subarray problem | |
| 686 // for small k - SE Bae, T Takaoka but modified to show the explicit tracking | |
| 687 // of indices and we already have the prefix sums from our one call site so | |
| 688 // there's no need to construct them. | |
| 689 // MaxSum1D = function (A,n) { | |
| 690 // var minIdx = 0; | |
| 691 // var min = 0; | |
| 692 // var maxIndices = (0,0); | |
| 693 // var max = 0; | |
| 694 // for i in range(n) { | |
| 695 // let cand = A[i] - min; | |
| 696 // if (cand > max) { | |
| 697 // max := cand; | |
| 698 // maxIndices := (minIdx, i) | |
| 699 // } | |
| 700 // if (min > A[i]) { | |
| 701 // min := A[i]; | |
| 702 // minIdx := i; | |
| 703 // } | |
| 704 // } | |
| 705 // return (minIdx, maxIdx, max); | |
| 706 // } | |
| 707 | |
| 708 namespace { | |
| 709 // This class represents a partitioning of an axis delineated by coordinates. | |
| 710 // It internally maintains a sorted array of coordinates. | |
| 711 class AxisPartition { | |
| 712 public: | |
| 713 // Adds a new partition at the given coordinate to this partitioning. If | |
| 714 // the coordinate is already present in the partitioning, this does nothing. | |
| 715 void InsertCoord(nscoord c) { | |
| 716 uint32_t i = mStops.IndexOfFirstElementGt(c); | |
| 717 if (i == 0 || mStops[i-1] != c) { | |
| 718 mStops.InsertElementAt(i, c); | |
| 719 } | |
| 720 } | |
| 721 | |
| 722 // Returns the array index of the given partition point. The partition | |
| 723 // point must already be present in the partitioning. | |
| 724 int32_t IndexOf(nscoord p) const { | |
| 725 return mStops.BinaryIndexOf(p); | |
| 726 } | |
| 727 | |
| 728 // Returns the partition at the given index which must be non-zero and | |
| 729 // less than the number of partitions in this partitioning. | |
| 730 nscoord StopAt(int32_t index) const { | |
| 731 return mStops[index]; | |
| 732 } | |
| 733 | |
| 734 // Returns the size of the gap between the partition at the given index and | |
| 735 // the next partition in this partitioning. If the index is the last index | |
| 736 // in the partitioning, the result is undefined. | |
| 737 nscoord StopSize(int32_t index) const { | |
| 738 return mStops[index+1] - mStops[index]; | |
| 739 } | |
| 740 | |
| 741 // Returns the number of partitions in this partitioning. | |
| 742 int32_t GetNumStops() const { return mStops.Length(); } | |
| 743 | |
| 744 private: | |
| 745 nsTArray<nscoord> mStops; | |
| 746 }; | |
| 747 | |
| 748 const int64_t kVeryLargeNegativeNumber = 0xffff000000000000ll; | |
| 749 | |
| 750 struct SizePair { | |
| 751 int64_t mSizeContainingRect; | |
| 752 int64_t mSize; | |
| 753 | |
| 754 SizePair() : mSizeContainingRect(0), mSize(0) {} | |
| 755 | |
| 756 static SizePair VeryLargeNegative() { | |
| 757 SizePair result; | |
| 758 result.mSize = result.mSizeContainingRect = kVeryLargeNegativeNumber; | |
| 759 return result; | |
| 760 } | |
| 761 SizePair& operator=(const SizePair& aOther) { | |
| 762 mSizeContainingRect = aOther.mSizeContainingRect; | |
| 763 mSize = aOther.mSize; | |
| 764 return *this; | |
| 765 } | |
| 766 bool operator<(const SizePair& aOther) const { | |
| 767 if (mSizeContainingRect < aOther.mSizeContainingRect) | |
| 768 return true; | |
| 769 if (mSizeContainingRect > aOther.mSizeContainingRect) | |
| 770 return false; | |
| 771 return mSize < aOther.mSize; | |
| 772 } | |
| 773 bool operator>(const SizePair& aOther) const { | |
| 774 return aOther.operator<(*this); | |
| 775 } | |
| 776 SizePair operator+(const SizePair& aOther) const { | |
| 777 SizePair result = *this; | |
| 778 result.mSizeContainingRect += aOther.mSizeContainingRect; | |
| 779 result.mSize += aOther.mSize; | |
| 780 return result; | |
| 781 } | |
| 782 SizePair operator-(const SizePair& aOther) const { | |
| 783 SizePair result = *this; | |
| 784 result.mSizeContainingRect -= aOther.mSizeContainingRect; | |
| 785 result.mSize -= aOther.mSize; | |
| 786 return result; | |
| 787 } | |
| 788 }; | |
| 789 | |
| 790 // Returns the sum and indices of the subarray with the maximum sum of the | |
| 791 // given array (A,n), assuming the array is already in prefix sum form. | |
| 792 SizePair MaxSum1D(const nsTArray<SizePair> &A, int32_t n, | |
| 793 int32_t *minIdx, int32_t *maxIdx) { | |
| 794 // The min/max indicies of the largest subarray found so far | |
| 795 SizePair min, max; | |
| 796 int32_t currentMinIdx = 0; | |
| 797 | |
| 798 *minIdx = 0; | |
| 799 *maxIdx = 0; | |
| 800 | |
| 801 // Because we're given the array in prefix sum form, we know the first | |
| 802 // element is 0 | |
| 803 for(int32_t i = 1; i < n; i++) { | |
| 804 SizePair cand = A[i] - min; | |
| 805 if (cand > max) { | |
| 806 max = cand; | |
| 807 *minIdx = currentMinIdx; | |
| 808 *maxIdx = i; | |
| 809 } | |
| 810 if (min > A[i]) { | |
| 811 min = A[i]; | |
| 812 currentMinIdx = i; | |
| 813 } | |
| 814 } | |
| 815 | |
| 816 return max; | |
| 817 } | |
| 818 } | |
| 819 | |
| 820 nsRect nsRegion::GetLargestRectangle (const nsRect& aContainingRect) const { | |
| 821 nsRect bestRect; | |
| 822 | |
| 823 if (GetNumRects() <= 1) { | |
| 824 bestRect = GetBounds(); | |
| 825 return bestRect; | |
| 826 } | |
| 827 | |
| 828 AxisPartition xaxis, yaxis; | |
| 829 | |
| 830 // Step 1: Calculate the grid lines | |
| 831 nsRegionRectIterator iter(*this); | |
| 832 const nsRect *currentRect; | |
| 833 while ((currentRect = iter.Next())) { | |
| 834 xaxis.InsertCoord(currentRect->x); | |
| 835 xaxis.InsertCoord(currentRect->XMost()); | |
| 836 yaxis.InsertCoord(currentRect->y); | |
| 837 yaxis.InsertCoord(currentRect->YMost()); | |
| 838 } | |
| 839 if (!aContainingRect.IsEmpty()) { | |
| 840 xaxis.InsertCoord(aContainingRect.x); | |
| 841 xaxis.InsertCoord(aContainingRect.XMost()); | |
| 842 yaxis.InsertCoord(aContainingRect.y); | |
| 843 yaxis.InsertCoord(aContainingRect.YMost()); | |
| 844 } | |
| 845 | |
| 846 // Step 2: Fill out the grid with the areas | |
| 847 // Note: due to the ordering of rectangles in the region, it is not always | |
| 848 // possible to combine steps 2 and 3 so we don't try to be clever. | |
| 849 int32_t matrixHeight = yaxis.GetNumStops() - 1; | |
| 850 int32_t matrixWidth = xaxis.GetNumStops() - 1; | |
| 851 int32_t matrixSize = matrixHeight * matrixWidth; | |
| 852 nsTArray<SizePair> areas(matrixSize); | |
| 853 areas.SetLength(matrixSize); | |
| 854 | |
| 855 iter.Reset(); | |
| 856 while ((currentRect = iter.Next())) { | |
| 857 int32_t xstart = xaxis.IndexOf(currentRect->x); | |
| 858 int32_t xend = xaxis.IndexOf(currentRect->XMost()); | |
| 859 int32_t y = yaxis.IndexOf(currentRect->y); | |
| 860 int32_t yend = yaxis.IndexOf(currentRect->YMost()); | |
| 861 | |
| 862 for (; y < yend; y++) { | |
| 863 nscoord height = yaxis.StopSize(y); | |
| 864 for (int32_t x = xstart; x < xend; x++) { | |
| 865 nscoord width = xaxis.StopSize(x); | |
| 866 int64_t size = width*int64_t(height); | |
| 867 if (currentRect->Intersects(aContainingRect)) { | |
| 868 areas[y*matrixWidth+x].mSizeContainingRect = size; | |
| 869 } | |
| 870 areas[y*matrixWidth+x].mSize = size; | |
| 871 } | |
| 872 } | |
| 873 } | |
| 874 | |
| 875 // Step 3: Find the maximum submatrix sum that does not contain a rectangle | |
| 876 { | |
| 877 // First get the prefix sum array | |
| 878 int32_t m = matrixHeight + 1; | |
| 879 int32_t n = matrixWidth + 1; | |
| 880 nsTArray<SizePair> pareas(m*n); | |
| 881 pareas.SetLength(m*n); | |
| 882 for (int32_t y = 1; y < m; y++) { | |
| 883 for (int32_t x = 1; x < n; x++) { | |
| 884 SizePair area = areas[(y-1)*matrixWidth+x-1]; | |
| 885 if (!area.mSize) { | |
| 886 area = SizePair::VeryLargeNegative(); | |
| 887 } | |
| 888 area = area + pareas[ y*n+x-1] | |
| 889 + pareas[(y-1)*n+x ] | |
| 890 - pareas[(y-1)*n+x-1]; | |
| 891 pareas[y*n+x] = area; | |
| 892 } | |
| 893 } | |
| 894 | |
| 895 // No longer need the grid | |
| 896 areas.SetLength(0); | |
| 897 | |
| 898 SizePair bestArea; | |
| 899 struct { | |
| 900 int32_t left, top, right, bottom; | |
| 901 } bestRectIndices = { 0, 0, 0, 0 }; | |
| 902 for (int32_t m1 = 0; m1 < m; m1++) { | |
| 903 for (int32_t m2 = m1+1; m2 < m; m2++) { | |
| 904 nsTArray<SizePair> B; | |
| 905 B.SetLength(n); | |
| 906 for (int32_t i = 0; i < n; i++) { | |
| 907 B[i] = pareas[m2*n+i] - pareas[m1*n+i]; | |
| 908 } | |
| 909 int32_t minIdx, maxIdx; | |
| 910 SizePair area = MaxSum1D(B, n, &minIdx, &maxIdx); | |
| 911 if (area > bestArea) { | |
| 912 bestRectIndices.left = minIdx; | |
| 913 bestRectIndices.top = m1; | |
| 914 bestRectIndices.right = maxIdx; | |
| 915 bestRectIndices.bottom = m2; | |
| 916 bestArea = area; | |
| 917 } | |
| 918 } | |
| 919 } | |
| 920 | |
| 921 bestRect.MoveTo(xaxis.StopAt(bestRectIndices.left), | |
| 922 yaxis.StopAt(bestRectIndices.top)); | |
| 923 bestRect.SizeTo(xaxis.StopAt(bestRectIndices.right) - bestRect.x, | |
| 924 yaxis.StopAt(bestRectIndices.bottom) - bestRect.y); | |
| 925 } | |
| 926 | |
| 927 return bestRect; | |
| 928 } | |
| 929 | |
| 930 nsCString | |
| 931 nsRegion::ToString() const { | |
| 932 nsCString result; | |
| 933 result.AppendLiteral("["); | |
| 934 | |
| 935 int n; | |
| 936 pixman_box32_t *boxes = pixman_region32_rectangles(const_cast<pixman_region32_t*>(&mImpl), &n); | |
| 937 for (int i=0; i<n; i++) { | |
| 938 if (i != 0) { | |
| 939 result.AppendLiteral("; "); | |
| 940 } | |
| 941 result.Append(nsPrintfCString("%d,%d,%d,%d", boxes[i].x1, boxes[i].y1, boxes[i].x2, boxes[i].y2)); | |
| 942 | |
| 943 } | |
| 944 result.AppendLiteral("]"); | |
| 945 | |
| 946 return result; | |
| 947 } | |
| 948 | |
| 949 | |
| 950 nsRegion nsIntRegion::ToAppUnits (nscoord aAppUnitsPerPixel) const | |
| 951 { | |
| 952 nsRegion result; | |
| 953 nsIntRegionRectIterator rgnIter(*this); | |
| 954 const nsIntRect* currentRect; | |
| 955 while ((currentRect = rgnIter.Next())) { | |
| 956 nsRect appRect = currentRect->ToAppUnits(aAppUnitsPerPixel); | |
| 957 result.Or(result, appRect); | |
| 958 } | |
| 959 return result; | |
| 960 } |
