693521 - Improve Preserve3D layer sorting

Status: RESOLVED FIXED

(Core :: Graphics, defect)

Description

[Matt Woodrow (:mattwoodrow)]

Attachment: Improve Sorting Again.

Currently the layer sorting code only uses the corners of the projected rectangles to determine Z depths. It's quite easy to construct a test case with 2 rectangles that overlap, yet have no corners within the other rectangle.

We also have quite bad rounding errors that mean that standard '3d cube' examples end up having intersecting planes.

This patch adds in line intersection testing to handle the first case, and ignores differences in Z depth of less than 1 pixel for the latter.

This is starting to get quite complex, suggestions for simplifying this code would be appreciated :)

Working on a test case or two that are fixed by this, probably as reduced forms of this:
http://romaxa.bolshe.net/css3d/cube3d2/cube2.html

Comment 1

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to Matt Woodrow (:mattwoodrow) from comment #0)
> This is starting to get quite complex, suggestions for simplifying this code
> would be appreciated :)

Maybe just bite the bullet and implement plane splitting instead of tweaking this? :-)

Comment 2

[Matt Woodrow (:mattwoodrow)]

This fixes cases that don't intersect in 3d, so don't need plane splitting. I think this is still easier, just.

Comment 3

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 566117 [details] [diff] [review]
Improve Sorting Again.

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

::: gfx/layers/LayerSorter.cpp
@@ +73,5 @@
>  
>      return n/d;
>  }
>  
> +static gfxFloat FlushToZero(double aVal)

SnapToZero?

@@ +76,5 @@
>  
> +static gfxFloat FlushToZero(double aVal)
> +{
> +  if (-1.0 < aVal && aVal < 1.0)
> +    return 0.0;

Is 1.0 really needed here? It would look better if your epsilon was 10^-6 or something like that.

@@ +111,5 @@
>  
>    // Make a list of all points that are within the other rect.
> +  // Could we just check Contains() on the bounds rects. ie, is it possible
> +  // for layers to overlap without intersections (in 2d space) and yet still
> +  // have their bounds rects not completely enclose each other?

I'm not really sure what this means.

@@ +160,5 @@
> +      gfxLineSegment two(otherTransformedRect.mPoints[j],
> +                         otherTransformedRect.mPoints[(j + 1) % 4]);
> +      if (one.Intersects(two, intersection)) {
> +        points.AppendElement(intersection);
> +      }

How about building a set of points that includes all corners and all edge intersections, and test all those? That'd be a little simpler.

@@ +266,5 @@
>  
>    // Move each item without incoming edges into the sorted list,
>    // and remove edges from it.
> +  do {
> +    if (!noIncoming.IsEmpty()) {

Why are you changing this?

Comment 4

[Matt Woodrow (:mattwoodrow)]

(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #3)
> @@ +76,5 @@
> >  
> > +static gfxFloat FlushToZero(double aVal)
> > +{
> > +  if (-1.0 < aVal && aVal < 1.0)
> > +    return 0.0;
> 
> Is 1.0 really needed here? It would look better if your epsilon was 10^-6 or
> something like that.

It does seem to be, sadly. In reduced versions of the linked test case I was getting differences as high at 0.7 for edges that should have been coincident.

> 
> @@ +111,5 @@
> >  
> >    // Make a list of all points that are within the other rect.
> > +  // Could we just check Contains() on the bounds rects. ie, is it possible
> > +  // for layers to overlap without intersections (in 2d space) and yet still
> > +  // have their bounds rects not completely enclose each other?
> 
> I'm not really sure what this means.

I was hoping that we could just test

if (ourBounds.Contains(otherBounds) || otherBounds.Contains(ourBounds))

and skip the corner checks entirely. But I can't think of a way to detect true 3d intersections with this logic now, so that comment can probably just go.

> 
> @@ +160,5 @@
> > +      gfxLineSegment two(otherTransformedRect.mPoints[j],
> > +                         otherTransformedRect.mPoints[(j + 1) % 4]);
> > +      if (one.Intersects(two, intersection)) {
> > +        points.AppendElement(intersection);
> > +      }
> 
> How about building a set of points that includes all corners and all edge
> intersections, and test all those? That'd be a little simpler.

I think I decided that this was invalid when a corner was also an intersection. It's also just more expensive and unnecessary if the corner testing has determined an order

> 
> @@ +266,5 @@
> >  
> >    // Move each item without incoming edges into the sorted list,
> >    // and remove edges from it.
> > +  do {
> > +    if (!noIncoming.IsEmpty()) {
> 
> Why are you changing this?

This was a bug, if the initial was list empty (all layers were part of cycles), then we never did any attempts at sorting.

Comment 5

[Robert O'Callahan (:roc) (email my personal email if necessary)]

(In reply to Matt Woodrow (:mattwoodrow) from comment #4)
> (In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #3)
> > Is 1.0 really needed here? It would look better if your epsilon was 10^-6 or
> > something like that.
> 
> It does seem to be, sadly. In reduced versions of the linked test case I was
> getting differences as high at 0.7 for edges that should have been
> coincident.

That seems very high. Are you sure that's not just a bug? If you're seeing errors up to 0.7 then probably 1.0 is not enough, and that's just wrong.

> > How about building a set of points that includes all corners and all edge
> > intersections, and test all those? That'd be a little simpler.
> 
> I think I decided that this was invalid when a corner was also an
> intersection.

How's that? Some points may be unnecessary, but adding points inside both quads shouldn't make things invalid.

> It's also just more expensive and unnecessary if the corner
> testing has determined an order

Does that really matter?

> > >    // Move each item without incoming edges into the sorted list,
> > >    // and remove edges from it.
> > > +  do {
> > > +    if (!noIncoming.IsEmpty()) {
> > 
> > Why are you changing this?
> 
> This was a bug, if the initial was list empty (all layers were part of
> cycles), then we never did any attempts at sorting.

OK.

Comment 6

[Matt Woodrow (:mattwoodrow)]

(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #5)
> That seems very high. Are you sure that's not just a bug? If you're seeing
> errors up to 0.7 then probably 1.0 is not enough, and that's just wrong.

I agree, but I can't see any obvious bugs.

This is the output from transforming two identical rects into sides of a cube:

http://pastebin.mozilla.org/1353082

Note that points 3,4 from the first transformed rect match up (almost) with points 2,1 from the second.

Rendered Image: http://imgur.com/cHe1t

Page Source: http://pastebin.mozilla.org/1353084

I can't see any obvious reason why there's almost 0.8 difference in the computed points for one of the corners. I might see if I can generate the matrices as doubles and see if it improves things.

Comment 7

[Matt Woodrow (:mattwoodrow)]

So WebKit is doing this slightly differently, and avoiding needing to round.

They do a similar method of comparing corners/intersections (except with triangles), but only remember the point with the highest Z absolute difference. The also break out early from the intersection if the current highest difference is bigger than a given threshhold.

So rather than failing with intersecting layers, they still generate an ordering based on the depths and hope that it produces better looking output than having these layers ordered arbitrarily - which it does.

I'm not sure if that approach is better than ignoring small intersections, but failing on 'true' intersections. Either way it's an approximation, and the resulting drawing order is the same for basic examples like 3d cubes.

Comment 8

[Matt Woodrow (:mattwoodrow)]

Attachment: Improve Sorting Again. v2

The WebKit idea seems better now that I think about it.

This now just generates a list of all intersections points, and picks the one with the greatest Z difference. Layer ordering is based on this point alone.

This gives us the best rendering that I've seen so far, the linked 3d cube example now looks completely correct.

Comment 9

[Robert O'Callahan (:roc) (email my personal email if necessary)]

Comment on attachment 566949 [details] [diff] [review]
Improve Sorting Again. v2

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

r+ with that fixed.

::: gfx/thebes/gfx3DMatrix.cpp
@@ +667,5 @@
>    return gfxRect(min_x, min_y, max_x - min_x, max_y - min_y);
>  }
>  
>  gfxQuad 
> +gfx3DMatrix::TransformRect(const gfxRect& aRect, gfxRect* aBounds) const

I think it would make more sense to have gfxQuad::GetBounds(), then you don't need the out parameter here.

::: gfx/thebes/gfxLineSegment.h
@@ +66,5 @@
> +  }
> +
> +  /**
> +   * Determines if two line segments intersect, and returns the intersection
> +   * point in aIntersection if they do

Document here that coincident lines are treated as not intersecting.

Comment 10

[Matt Woodrow (:mattwoodrow)]

Attachment: Improve Sorting Again. v3

Fixed review comments, carrying forward r=roc

Comment 11

[Matt Woodrow (:mattwoodrow)]

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

Comment 12

[Ed Morley [:emorley]]

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