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