Closed Bug 945079 Opened 6 years ago Closed 6 years ago

Add a way to simplify regions vertically

Categories

(Core :: Graphics, defect)

x86
macOS
defect
Not set

Tracking

()

RESOLVED FIXED
mozilla32
Tracking Status
firefox31 --- fixed
firefox32 --- fixed

People

(Reporter: jrmuizel, Assigned: jrmuizel)

References

Details

Attachments

(2 files, 3 obsolete files)

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.
Attached patch An ugly first attempt (obsolete) — Splinter Review
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.
Attached patch A slightly less ugly version (obsolete) — Splinter Review
Attachment #8341978 - Attachment is obsolete: true
Comment on attachment 8378644 [details] [diff] [review]
A slightly less ugly version

Matt, are you interested in reviewing this?
Attachment #8378644 - Flags: feedback?(matt.woodrow)
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.
Blocks: 995267
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!
(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.
Attached patch patchSplinter Review
Attachment #8378644 - Attachment is obsolete: true
Attachment #8378644 - Flags: feedback?(matt.woodrow)
Attachment #8418336 - Flags: review?(matt.woodrow)
Comment on attachment 8418336 [details] [diff] [review]
patch

I don't think you meant to upload this patch
Attachment #8418336 - Flags: review?(matt.woodrow)
Attached patch Address some of the comments (obsolete) — Splinter Review
Attachment #8418353 - Flags: review?(matt.woodrow)
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.
Attachment #8418353 - Flags: review?(matt.woodrow) → review+
(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.
Attached patch WIPSplinter Review
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.
Attachment #8418353 - Attachment is obsolete: true
Assignee: nobody → jmuizelaar
Whiteboard: [leave open]
No longer depends on: 1008573
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.
Attachment #8419032 - Flags: approval-mozilla-aurora?
Jeff, could you fill the uplift request template? Thanks
Flags: needinfo?(jmuizelaar)
Comment on attachment 8419032 [details] [diff] [review]
WIP

Approving because RyanVM needs it to avoid a bustage on aurora.
Attachment #8419032 - Flags: approval-mozilla-aurora? → approval-mozilla-aurora+
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
Flags: needinfo?(jmuizelaar)
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.
Status: NEW → RESOLVED
Closed: 6 years ago
Resolution: --- → FIXED
Whiteboard: [leave open]
Target Milestone: --- → mozilla32
Jeff, are there tests for this, or something that QA can do to manually test this fix? Thanks!
Flags: needinfo?(jmuizelaar)
(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.
Flags: needinfo?(jmuizelaar)
Flags: in-testsuite+
You need to log in before you can comment on or make changes to this bug.