945079 - Add a way to simplify regions vertically

Status: RESOLVED FIXED

(Core :: Graphics, defect)

Description

[Jeff Muizelaar [:jrmuizel]]

This will be helpful for bug 938395 / bug 934860.

The basic idea is to compare horizontal region spans and see how much area would be added to the region if they were merged. If the added area is a below a threshold than we merge the regions. This should give us simplification semantics closer to what IE 11 uses.

Comment 1

[Jeff Muizelaar [:jrmuizel]]

Attachment: An ugly first attempt

This has the basic implementation working. The code is pretty ugly and I can only guarantee that it works on the regions included in the test. But it should be a useful starting point.

Comment 2

[Jeff Muizelaar [:jrmuizel]]

Attachment: A slightly less ugly version

Comment 3

[Jeff Muizelaar [:jrmuizel]]

Comment on attachment 8378644 [details] [diff] [review]
A slightly less ugly version

Matt, are you interested in reviewing this?

Comment 4

[Matt Woodrow (:mattwoodrow)]

Yeah, I probably can. Can you add some more comments please :)

In particular, an overview of what the algorithm is doing would make this a lot easier.

Comment 5

[Matt Woodrow (:mattwoodrow)]

Comment on attachment 8378644 [details] [diff] [review]
A slightly less ugly version

Review of attachment 8378644 [details] [diff] [review]:
-----------------------------------------------------------------

I had to draw an example pair of spans to figure out how this worked :(

Would it be simpler to compute the new area and the old area and subtract them to find the difference?

::: gfx/src/nsRegion.cpp
@@ +122,5 @@
> +  //XXX: we could probably simplify this condition and perhaps move it into the loop below
> +  if (j->x < cur_x) {
> +    cur_x = j->x;
> +    j++;
> +    bottom_next = !bottom;

bottom is always false here, right?

@@ +225,5 @@
> +      bottomRectsEnd++;
> +    }
> +    int totalArea = ComputeMergedAreaIncrease(topRects, topRectsEnd, bottomRects, bottomRectsEnd);
> +
> +    if (totalArea <= aThreshold) {

signed/unsigned mismatch.

::: gfx/src/nsRegion.h
@@ +240,5 @@
> +   * rects.  The simplified region will be a superset of the original region.
> +   * The simplified region's bounding box will be the same as for the current
> +   * region.
> +   */
> +  void SimplifyOutwardByArea(uint32_t aThreshold);

Can you add a wrapper of this to nsIntRegion too please!

Comment 6

[Jeff Muizelaar [:jrmuizel]]

(In reply to Matt Woodrow (:mattwoodrow) from comment #5)
> Comment on attachment 8378644 [details] [diff] [review]
> A slightly less ugly version
> 
> Review of attachment 8378644 [details] [diff] [review]:
> -----------------------------------------------------------------
> 
> I had to draw an example pair of spans to figure out how this worked :(
> 
> Would it be simpler to compute the new area and the old area and subtract
> them to find the difference?

I've thought about it and I'm not sure if it would be simpler or not. I'm willing to try post landing.

> ::: gfx/src/nsRegion.cpp
> @@ +122,5 @@
> > +  //XXX: we could probably simplify this condition and perhaps move it into the loop below
> > +  if (j->x < cur_x) {
> > +    cur_x = j->x;
> > +    j++;
> > +    bottom_next = !bottom;
> 
> bottom is always false here, right?

Correct. I think I kept things this way for consistency with the code inside the loop.

Comment 7

[Jeff Muizelaar [:jrmuizel]]

Attachment: patch

Comment 8

[Matt Woodrow (:mattwoodrow)]

Comment on attachment 8418336 [details] [diff] [review]
patch

I don't think you meant to upload this patch

Comment 9

[Jeff Muizelaar [:jrmuizel]]

Attachment: Address some of the comments

Comment 10

[Matt Woodrow (:mattwoodrow)]

Comment on attachment 8418353 [details] [diff] [review]
Address some of the comments

Review of attachment 8418353 [details] [diff] [review]:
-----------------------------------------------------------------

Ok, I'm happy with taking this as long as it gets a lot more comments.

Most of my comments below are basically just examples of inline comments I'd like to have.

One idea I had was to put i, top and top_next into their own struct and have 'increment' functions for moving to the next edge, flipping top/top_next etc. RectIterator::Advance, RectIterator::IsRightEdge/IsInRect or something. Less worried about that, but it might make it easier to follow.

::: gfx/src/nsRegion.cpp
@@ +96,5 @@
>      *this = GetBounds();
>    }
>  }
>  
> +// compute the covered area difference between two rows.

A high level description of *how* it does this should go here, or there, or somewhere.

@@ +111,5 @@
> +
> +  pt *i = (pt*)topRects;
> +  pt *end_i = (pt*)topRectsEnd;
> +  pt *j = (pt*)bottomRects;
> +  pt *end_j = (pt*)bottomRectsEnd;

i and j can point to either the left edge or right edge or a rectangle, so each time we increment them we need to invert the state of top/bottom to record if we're currently inside a rect or between them (via top_next/bottom_next since we still need the old value for now).

@@ +113,5 @@
> +  pt *end_i = (pt*)topRectsEnd;
> +  pt *j = (pt*)bottomRects;
> +  pt *end_j = (pt*)bottomRectsEnd;
> +  bool top = false;
> +  bool bottom = false;

top and bottom specify if the top and bottom are present in the band between cur_x and the previous cur_x (the distance specified by 'width').

@@ +136,5 @@
> +
> +  int topRectsHeight = topRects->y2 - topRects->y1;
> +  int bottomRectsHeight = bottomRects->y2 - bottomRects->y1;
> +  int inbetweenHeight = bottomRects->y1 - topRects->y2;
> +  int width = cur_x;

Why initialize this to cur_x? bottom and top and guaranteed to be false for the first iteration, and we always set it after that.

@@ +166,5 @@
> +      width = i->x - cur_x;
> +      cur_x = i->x;
> +      i++;
> +      j++;
> +    }

This block is basically identical to the earlier one except for being ordered differently and computing the width. Could we move them both out into a helper 'FindNextEdge' or something?

A description of how it moves the left-most of i/j to the next rect edge and then computes the appropriate cur_x and width would be good too.

@@ +169,5 @@
> +      j++;
> +    }
> +  } while (i < end_i && j < end_j);
> +
> +  // handle any remaining rects

Only one of these two loops can be taken.

@@ +231,5 @@
> +      struct pt {
> +	      int32_t x, y;
> +      };
> +
> +      // merge the two spans of rects

This function is massive, can you split MergeRows and CopyRow out so the control flow is easier to see.

@@ +237,5 @@
> +      pt *end_i = (pt*)topRectsEnd;
> +      pt *j = (pt*)bottomRects;
> +      pt *end_j = (pt*)bottomRectsEnd;
> +      bool top;
> +      bool bottom;

Probably want similar comments here about the nature of i/j and the meaning of top/bottom.

@@ +239,5 @@
> +      pt *end_j = (pt*)bottomRectsEnd;
> +      bool top;
> +      bool bottom;
> +
> +      int cur_x = i->x;

A high level description of this would be good too.

Starting from the leftmost edge walk right until we find an right-edge that isn't within a rect of the other row. Create a rect using those bounds, add it to the merged list and repeat.

@@ +258,5 @@
> +        bottom = false;
> +        i++;
> +      }
> +
> +      rect = tmpRect;

move the declaration of this down to here?

@@ +359,5 @@
> +          while (src_it < topRectsEnd) {
> +            *dest_it++ = *src_it++;
> +          }
> +          topRectsEnd = dest_it;
> +        }

This same block of code exists 3 times! I repeat my request for a 'CopyRow' function.

Comment 11

[Matt Woodrow (:mattwoodrow)]

(In reply to Matt Woodrow (:mattwoodrow) from comment #10)
> 
> One idea I had was to put i, top and top_next into their own struct and have
> 'increment' functions for moving to the next edge, flipping top/top_next
> etc. RectIterator::Advance, RectIterator::IsRightEdge/IsInRect or something.
> Less worried about that, but it might make it easier to follow.

The more I think about this, the more I like it. We could have ::IsAtEnd() instead of end_i/j, and since we never use the 'y' member of pt we can just not expose it at all and have CurrentPoint() instead.

Comment 12

[Jeff Muizelaar [:jrmuizel]]

Attachment: WIP

This separates out CopyRow and MergeRow, which is a big improvement in readability. It might be worth committing this now so we can get the testing of its users. I'm happy to continue working on it in tree.

Comment 13

[Matt Woodrow (:mattwoodrow)]

https://hg.mozilla.org/integration/mozilla-inbound/rev/a929ed3a2330

Comment 14

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/a929ed3a2330

Comment 15

[Jeff Muizelaar [:jrmuizel]]

Comment on attachment 8419032 [details] [diff] [review]
WIP

Review of attachment 8419032 [details] [diff] [review]:
-----------------------------------------------------------------

This is needed to fix bug 812695 and has no additional risk because just this alone has no callers.

Comment 16

[Sylvestre Ledru [:Sylvestre]]

Jeff, could you fill the uplift request template? Thanks

Comment 17

[Sylvestre Ledru [:Sylvestre]]

Comment on attachment 8419032 [details] [diff] [review]
WIP

Approving because RyanVM needs it to avoid a bustage on aurora.

Comment 18

[Ryan VanderMeulen [:RyanVM]]

For posterity:

[Approval Request Comment]
Bug caused by (feature/regressing bug #): N/A
User impact if declined: Various gfx issues experienced by end users are blocked on this bug, including the already-uplifted (and currently busted) bug 938395.
Testing completed (on m-c, etc.): on m-c for almost 4 weeks now
Risk to taking this patch (and alternatives if risky): Per comment 15, very low
String or IDL/UUID changes made by this patch: N/A

Comment 19

[Ryan VanderMeulen [:RyanVM]]

https://hg.mozilla.org/releases/mozilla-aurora/rev/12ed2a5094be

Jeff, it seems very unlikely that much more work is going to happen here before the uplift. So we're not dealing with tracking the status of this bug across multiple releases, let's close this bug and leave any future work for new bugs.

Comment 20

[Liz Henry (:lizzard) (relman/hg->git project)]

Jeff, are there tests for this, or something that QA can do to manually test this fix? Thanks!

Comment 21

[Jeff Muizelaar [:jrmuizel]]

(In reply to Liz Henry :lizzard from comment #20)
> Jeff, are there tests for this, or something that QA can do to manually test
> this fix? Thanks!

Yes, there are tests in the tree.