Implement better sorting for preserve-3d child layers

RESOLVED FIXED in mozilla10

Status

()

defect
RESOLVED FIXED
8 years ago
7 years ago

People

(Reporter: mattwoodrow, Assigned: mattwoodrow)

Tracking

unspecified
mozilla10
x86
macOS
Points:
---
Dependency tree / graph

Firefox Tracking Flags

(Not tracked)

Details

(Whiteboard: [inbound])

Attachments

(6 attachments, 9 obsolete attachments)

10.22 KB, patch
roc
: review+
Details | Diff | Splinter Review
2.83 KB, patch
roc
: review+
Details | Diff | Splinter Review
20.59 KB, patch
roc
: review+
Details | Diff | Splinter Review
4.94 KB, patch
roc
: review+
Details | Diff | Splinter Review
6.27 KB, patch
mattwoodrow
: review+
Details | Diff | Splinter Review
7.72 KB, patch
roc
: review+
Details | Diff | Splinter Review
Currently we sort layers based on their z depth at the origin, we can do better by finding points where their 2d projections intersect on the screen plane and sort using the depth at these coordinates.
Attachment #558349 - Flags: review?(roc)
I also haven't added explicit handling for cycles of layers. Will the current sorting code be able to handle this?
Comment on attachment 558349 [details] [diff] [review]
Sort based on the depth at the intersection points

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

I believe the standard name for gfxUnalignedRect is gfxQuad.
Comment on attachment 558349 [details] [diff] [review]
Sort based on the depth at the intersection points

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

::: gfx/thebes/gfxUnalignedRect.h
@@ +45,5 @@
> +#include "nsPoint.h"
> +
> +#include "gfxTypes.h"
> +
> +static PRBool InsideLine(const gfxPoint& aPoint1, const gfxPoint& aPoint2, const gfxPoint& aTest, const gfxPoint& aRef)

Need a comment here, like "tests whether aTest is on the same side as aRef of the line from aPoint1 to aPoint2".

Maybe this should be called "OnSameSideOfLine"?

@@ +49,5 @@
> +static PRBool InsideLine(const gfxPoint& aPoint1, const gfxPoint& aPoint2, const gfxPoint& aTest, const gfxPoint& aRef)
> +{
> +  // Solve the equation y - aPoint1.y - ((aPoint2.y - aPoint1.y)/(aPoint2.x - aPoint1.x))(x - aPoint1.x) for both test and ref
> +  
> +  gfxFloat temp = (aPoint2.y - aPoint1.y) / (aPoint2.x / aPoint1.x);

division by zero? Maybe you can find a way to do this using only multiplication.

@@ +55,5 @@
> +  gfxFloat test = aTest.y - aPoint1.y - temp * (aTest.x - aPoint1.x);
> +  gfxFloat ref = aRef.y - aPoint1.y - temp * (aRef.x - aPoint1.x);
> +
> +  // If both results have the same sign, then we're on the correct side of the line.
> +  // 0 (on the line) is always considered out.

This seems wrong. By excluding points on the edge of the rectangle, this means that if you compare the z-positions of two quads that are identical, we won't check any points and we'll get the wrong answer sometimes.

::: layout/base/nsDisplayList.cpp
@@ +2738,5 @@
> +    PRBool temp = ZFromProjectedPoint(ourTransform, points.ElementAt(i)) < ZFromProjectedPoint(otherTransform, points.ElementAt(i));
> +    if (i == 0) {
> +      drawBefore = temp; 
> +    } else if (drawBefore != temp) {
> +      return PR_TRUE;

This seems a bit overcomplicated. Can't we just return false whenever the ZFromProjectedPoint comparison returns > 0?
This moves the sorting logic into layers and fixes lots of bugs.

This should make it easier to implement layer splitting and/or depth buffering at a later point. Any takers? :)

I don't overly like the gfxDirectedGraph interface, suggestions to improve it would be appreciated.

I haven't fixed the SameSideOfLine code yet, not sure how to make it multiplication only.
Attachment #558419 - Flags: review?(roc)
Attachment #558349 - Attachment is obsolete: true
Attachment #558349 - Flags: review?(roc)
Comment on attachment 558419 [details] [diff] [review]
Sort based on the depth at the intersection points v2

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

Fix that API stuff and then I'll review the rest...

::: gfx/layers/LayerSorter.h
@@ +43,5 @@
> +namespace mozilla {
> +namespace layers {
> +
> +namespace LayerSorter
> +{  

Don't need this additional namespace

@@ +44,5 @@
> +namespace layers {
> +
> +namespace LayerSorter
> +{  
> +    void SortLayers(nsTArray<Layer*>& aLayers);

Call this SortLayersBy3DZOrder?

::: gfx/layers/Layers.h
@@ +1088,5 @@
>    }
>  
>    virtual void FillSpecificAttributes(SpecificLayerAttributes& aAttrs);
>  
> +  nsTArray<Layer*> SortChildren();

SortChildrenBy3DZOrder?

@@ +1138,5 @@
>     */
>    PRBool SupportsComponentAlphaChildren() { return mSupportsComponentAlphaChildren; }
>  
> +  PRBool IsSortable() { return mSortable; }
> +  void SetSortable(PRBool aSortable) { mSortable = aSortable; }

Use a new content flag ... say CONTENT_PRESERVE_3D?

::: gfx/thebes/gfxDirectedGraph.h
@@ +1,1 @@
> +/* -*- Mode: C++; tab-width: 20; indent-tabs-mode: nil; c-basic-offset: 4 -*-

Perhaps this should be mozilla::layers::DirectedGraph until we know we need it elsewhere?

@@ +41,5 @@
> +#include "gfxTypes.h"
> +#include "nsTArray.h"
> +
> +template <typename T>
> +struct gfxGraphEdge {

Might make more sense as an Edge class nested in gfxDirectedGraph.

@@ +66,5 @@
> +
> +  /**
> +   * Get the list of edges.
> +   */
> +  const nsTArray<gfxGraphEdge<T> >& GetEdgeList() const;

Might be better to pass an array as an out-parameter. Then the caller can use an nsAutoTArray.

@@ +86,5 @@
> +
> +  /**
> +   * Get the list of all edges going from aNode
> +   */
> +  nsTArray<gfxGraphEdge<T> > GetEdgesFrom(T aNode);

Might be better to pass an array as an out-parameter. Then the caller can use an nsAutoTArray.

@@ +95,5 @@
> +  unsigned int GetEdgeCount() { return mEdges.Length(); }
> +
> +private:
> +
> +  nsTArray<gfxGraphEdge<T> > mEdges;

This is an awful representation but I guess it'll do for now. (You really want two hash tables, and for each node two linked lists of the edges in and out.)

::: gfx/thebes/gfxQuad.h
@@ +15,5 @@
> + * The Original Code is Oracle Corporation code.
> + *
> + * The Initial Developer of the Original Code is Oracle Corporation.
> + * Portions created by the Initial Developer are Copyright (C) 2005
> + * the Initial Developer. All Rights Reserved.

Fix this!!!!

@@ +55,5 @@
> +  gfxFloat test = aTest.y - aPoint1.y - temp * (aTest.x - aPoint1.x);
> +  gfxFloat ref = aRef.y - aPoint1.y - temp * (aRef.x - aPoint1.x);
> +
> +  // If both results have the same sign, then we're on the correct side of the line.
> +  // 0 (on the line) is always considered out.

in!!!
Attachment #558419 - Attachment is obsolete: true
Attachment #558419 - Flags: review?(roc)
Attachment #562369 - Flags: review?(roc)
Added missing file
Attachment #562369 - Attachment is obsolete: true
Attachment #562369 - Flags: review?(roc)
Attachment #562370 - Flags: review?(roc)
Comment on attachment 562370 [details] [diff] [review]
Sort based on the depth at the intersection points v4

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

Maybe LayerSorter should leave everything unsorted if the input is too large, say 100 layers? The code there is quite slow and could easily effectively hang.

::: gfx/layers/DirectedGraph.h
@@ +102,5 @@
> +   */
> +  void RemoveEdgesTo(T aNode)
> +  {
> +    RemoveEdgesToComparator c;
> +    mEdges.RemoveElement(aNode, c);

This only removes the first edge going into aNode?

::: gfx/layers/LayerSorter.cpp
@@ +195,5 @@
> +  }
> +
> +  // Move each item without incoming edges into the sorted list,
> +  // and remove edges from it.
> +  while (noIncoming.Length() > 0) {

!noIncoming.IsEmpty()

@@ +216,5 @@
> +    }
> +
> +    // If there are no nodes without incoming edges, but there
> +    // are still edges, then we have a cycle.
> +    if (!noIncoming.Length() && graph.GetEdgeCount()) {

noIncoming.IsEmpty()

::: gfx/layers/Layers.cpp
@@ +424,5 @@
> +
> +  for (Layer* l = GetFirstChild(); l; l = l->GetNextSibling()) {
> +    ContainerLayer* container = l->AsContainerLayer();
> +    if (container && container->GetContentFlags() & CONTENT_PRESERVE_3D) {
> +      toSort.AppendElement(l);

Shouldn't we be calling l->SortChildren() and appending the results to toSort?

(In which case SortChildren should probably take a parameter array to append the results to)

@@ +429,5 @@
> +    } else {
> +      if (toSort.Length() > 0) {
> +        SortLayersBy3DZOrder(toSort);
> +        children.AppendElements(toSort);
> +        toSort.Clear();

children.MoveElementsFrom(toSort);

::: gfx/layers/Layers.h
@@ +1094,5 @@
>    }
>  
>    virtual void FillSpecificAttributes(SpecificLayerAttributes& aAttrs);
>  
> +  nsTArray<Layer*> SortChildren();

SortChildrenBy3DZOrder?

@@ +1180,5 @@
>    FrameMetrics mFrameMetrics;
>    PRPackedBool mUseIntermediateSurface;
>    PRPackedBool mSupportsComponentAlphaChildren;
>    PRPackedBool mMayHaveReadbackChild;
> +  PRPackedBool mSortable;

What's this for? You seem to not use it.

::: layout/base/nsDisplayList.cpp
@@ +769,5 @@
>    // z-indices here, because that might overflow a 32-bit int.
>    PRInt32 index1 = nsLayoutUtils::GetZIndex(aItem1->GetUnderlyingFrame());
>    PRInt32 index2 = nsLayoutUtils::GetZIndex(aItem2->GetUnderlyingFrame());
>    if (index1 == index2)
> +    return IsContentLEQ(aItem1, aItem2, aClosure);

How does Z-ordering work for events now?

@@ +2524,5 @@
>      BuildContainerLayerFor(aBuilder, aManager, mFrame, this, *mStoredList.GetList(),
>                             aContainerParameters, &newTransformMatrix);
> +
> +  if (mFrame->Preserves3D()) {
> +    container->SetContentFlags(container->GetContentFlags() | Layer::CONTENT_PRESERVE_3D);

Document somewhere that BuildContainerLayerFor resets the flags, so that we don't have to explicitly clear CONTENT_PRESERVE_3D.
> Maybe LayerSorter should leave everything unsorted if the input is too
> large, say 100 layers? The code there is quite slow and could easily
> effectively hang.

Probably a good idea, I'll add a comment saying that we could look into enabling depth buffering in that case too.

> Shouldn't we be calling l->SortChildren() and appending the results to
> toSort?
> 
> (In which case SortChildren should probably take a parameter array to append
> the results to)

I don't think we want to descend into the children and sort their elements too. Each child should get SortChildren called separately when they get drawn. I think we should have all the elements we want sorted in the same container already, unless something like opacity/clipping is forcing another ContainerLayer child, and we wouldn't want to sort through that anyway.

For the 'poster-circle' case, we get all 36 elements contained within a single parent container.

> 
> ::: layout/base/nsDisplayList.cpp
> @@ +769,5 @@
> >    // z-indices here, because that might overflow a 32-bit int.
> >    PRInt32 index1 = nsLayoutUtils::GetZIndex(aItem1->GetUnderlyingFrame());
> >    PRInt32 index2 = nsLayoutUtils::GetZIndex(aItem2->GetUnderlyingFrame());
> >    if (index1 == index2)
> > +    return IsContentLEQ(aItem1, aItem2, aClosure);
> 
> How does Z-ordering work for events now?

I had managed to completely forget about this. As far as I can tell, it probably doesn't work at all now.

Do you have any suggestions for this? Reimplementing the sort in layout code is a lot harder since nested hierarchies haven't been flattened until we create layers.
Currently we only sort layers when there are multiple, sequential layers with the preserve-3d flag. We also fail to sort 'correctly' if there are intersections/cycles.

The two solutions I see for handling this for events are to sort within nsDisplayList::HitTest and sort from the caller of this (instead of just retrieving the first item in the returned list).

If we sort the entire returned list, then we could be sorting layers that won't ever be sorted on screen.

If we sort within nsDisplayList::HitTest then we could be missing sorting opportunities.

A common pattern is:

nsDisplayWrapList
  nsDisplayWrapList
    nsDisplayTransform
  nsDisplayWrapList
    nsDisplayTransform

Which becomes:

ContainerLayer
  ContainerLayer - transformed, preserve-3d
  ContainerLayer - transformed, preserve-3d

So we'd need to also sort the results of recursive calls into nsDisplayList::HitTest, but only if the resulting layers will be siblings. This seems non-trivial, but I may be missing something.

Both approaches assume that when we sort, we always succeed, which isn't necessarily true. As discussed, this is probably a non-issue and can be improved further (at a later date) using depth buffering or plane splitting.
Mark the nsDisplayWrapList item for a transformed element which is the root of a preserve-3d subtree, and sort within that? We should be able to flatten out things so that all the children we care about are immediate children of the nsDisplayWrapList.
This flattens out preserve-3d hierarchies so that all the children we care about are direct siblings.
Attachment #562370 - Attachment is obsolete: true
Attachment #562370 - Flags: review?(roc)
Attachment #564378 - Flags: review?(roc)
Helper classes for sorting
Attachment #564379 - Flags: review?(roc)
Attachment #564383 - Flags: review?(roc)
Comment on attachment 564378 [details] [diff] [review]
Part 1: Flatten out nsDisplayWrapLists

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

::: layout/generic/nsFrame.cpp
@@ +1736,5 @@
> +      resultList.AppendToTop(wrap->GetList());
> +      delete wrap;
> +    } else {
> +      resultList.AppendToTop(item);
> +    }

Can't we do this flattening in WrapPreserve3DList?

@@ +2020,5 @@
> +          nsDisplayWrapList(aBuilder, aChild, &list));
> +      NS_ENSURE_SUCCESS(rv, rv);
> +    } else {
> +      aLists.PositionedDescendants()->AppendToTop(&list);
> +    }

this chunk looks good in its own right
(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #17)
> Can't we do this flattening in WrapPreserve3DList?

You're right, we can. I was worried that this would interfere with Z position sorting, but I was mistaken.

This makes it a lot easier too.
Attachment #564378 - Attachment is obsolete: true
Attachment #564378 - Flags: review?(roc)
Attachment #564433 - Flags: review?(roc)
Your patches need PRBool -> bool
Comment on attachment 564381 [details] [diff] [review]
Part 3: Add Layer sorting code and event handling

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

::: gfx/layers/LayerSorter.cpp
@@ +156,5 @@
> +#define MAX_SORTABLE_LAYERS 100
> +
> +void SortLayersBy3DZOrder(nsTArray<Layer*>& aLayers)
> +{
> +  unsigned int nodeCount = aLayers.Length();

PRUint32 (all over the place)

::: layout/base/nsDisplayList.cpp
@@ +679,5 @@
>    }
>    return PR_FALSE;
>  }
>  
> +struct FrameSort

call this FramesWithDepth? And add a comment explaining what this is for.

@@ +732,5 @@
> +        //Stable sort temp, and add all the frames to aOutFrames
> +        temp.Sort();
> +        for (PRUint32 j = 0; j < temp.Length(); j++) {
> +          aOutFrames->AppendElements(temp[j].mFrames);
> +        }

Share this code with the other version below via some helper function.

And shouldn't we be clearing temp here?

@@ +742,5 @@
>          if (!GetMouseThrough(f) &&
>              f->GetStyleVisibility()->mPointerEvents != NS_STYLE_POINTER_EVENTS_NONE) {
>            aOutFrames->AppendElement(f);
>          }
>        }

We could avoid duplicating this code by doing it before the preserve-3d stuff; running through outFrames and appending the frames that survive the test to a new temporary array.

Then you could simplify things a bit and pass in the temporary array as another parameter of the FramesWithDepth constructor.

@@ +746,5 @@
>        }
>  
>      }
>    }
> +  //Stable sort temp, and add all the frames to aOutFrames

// Stable

@@ +747,5 @@
>  
>      }
>    }
> +  //Stable sort temp, and add all the frames to aOutFrames
> +  temp.Sort();

But is this really stable? I think this does a quicksort, which isn't stable.

You can probably fix this by making FramesWithDepth include the address of the element as a secondary key.

@@ +750,5 @@
> +  //Stable sort temp, and add all the frames to aOutFrames
> +  temp.Sort();
> +  for (PRUint32 j = 0; j < temp.Length(); j++) {
> +    aOutFrames->AppendElements(temp[j].mFrames);
> +  }

aOutFrames->MoveElementsFrom(temp[j].mFrames)

(not that it really matters)

@@ +2693,5 @@
> +  
> +  if (matrix.IsSingular() ||
> +      (mFrame->GetStyleDisplay()->mBackfaceVisibility == NS_STYLE_BACKFACE_VISIBILITY_HIDDEN &&
> +       matrix.GetNormalVector().z <= 0.0)) {
> +    return 0.0f;

Is this really the minimum depth? I don't know of anything that prevents real content from having negative depth.
Also, it's probably worth breaking patch 3 into separate layers and event-handling patches.
Comment on attachment 564382 [details] [diff] [review]
Part 4: Make the layer managers use layer sorting

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

::: gfx/layers/basic/BasicLayers.cpp
@@ +1892,4 @@
>        readback.BuildUpdates(container);
>      }
> +  
> +    nsTArray<Layer*> children = container->SortChildrenBy3DZOrder();

Actually for efficiency we should make 'children' an nsAutoTArray and make SortChildrenBy3DZOrder append to a parameter array.

@@ +1893,5 @@
>      }
> +  
> +    nsTArray<Layer*> children = container->SortChildrenBy3DZOrder();
> +
> +    for (unsigned int i = 0; i < children.Length(); i++) {

PRUint32 (everywhere)
Comment on attachment 564383 [details] [diff] [review]
Part 5: Add a test with overlapping layers

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

I think we could really use some more tests here. At least a test with a cycle of three layers which don't interpenetrate. We also need event-handling tests.
(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #21)
> 
> @@ +742,5 @@
> >          if (!GetMouseThrough(f) &&
> >              f->GetStyleVisibility()->mPointerEvents != NS_STYLE_POINTER_EVENTS_NONE) {
> >            aOutFrames->AppendElement(f);
> >          }
> >        }
> 
> We could avoid duplicating this code by doing it before the preserve-3d
> stuff; running through outFrames and appending the frames that survive the
> test to a new temporary array.
> 

My worry with doing this is it adds a needless stack allocation and overhead of copying all the frames into it when we won't be doing a preserve-3d sort very often.

I can use a pointer so that we copy directly into aOutFrames in the non-preserve-3d case, but this doesn't solve the allocation.

I'd really like to write the chosen frames back into outFrames and avoid needing a new array, but can't think of a way to do this without having entirely seperate code and/or making it hideously ugly.
It's an auto-array, so it's just a memcpy. No heap allocations involved. Really, it's fine.
(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #26)
> It's an auto-array, so it's just a memcpy. No heap allocations involved.
> Really, it's fine.

Too late! I fixed it.

(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #21)
> But is this really stable? I think this does a quicksort, which isn't stable

The comment was actually from earlier when the temp array contained an entry for each frame, and we needed a stable sort to make sure that frames from within the same nsDisplayTransform didn't get moved.

Though, we do have the rare case of two planes being completely parallel (true intersections at the hit point are already broken). I've added your suggestion to make this stable, and made a change to the Layers sorting code so that it's correct there too (< -> <=)
Attachment #564381 - Attachment is obsolete: true
Attachment #564381 - Flags: review?(roc)
Attachment #564744 - Flags: review?(roc)
Posted patch Part 3b: Add event handling (obsolete) — Splinter Review
Attachment #564746 - Flags: review?(roc)
Attachment #564382 - Attachment is obsolete: true
Attachment #564382 - Flags: review?(roc)
Attachment #564747 - Flags: review?(roc)
(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #24)
> Comment on attachment 564383 [details] [diff] [review] [diff] [details] [review]
> Part 5: Add a test with overlapping layers
> 
> Review of attachment 564383 [details] [diff] [review] [diff] [details] [review]:
> -----------------------------------------------------------------
> 
> I think we could really use some more tests here. At least a test with a
> cycle of three layers which don't interpenetrate. We also need
> event-handling tests.

How would you suggest we test the cycle? The current behaviour for cycles is 'give up sorting', I'm not sure what we can actually test here (except for making it fail and wait for plane splitting to fix it).

I'll write some event handling tests now.
Comment on attachment 564746 [details] [diff] [review]
Part 3b: Add event handling

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

::: layout/base/nsDisplayList.cpp
@@ +740,5 @@
> +      nsTArray<nsIFrame*> *writeFrames = aOutFrames;
> +      if (item->GetType() == nsDisplayItem::TYPE_TRANSFORM &&
> +          item->GetUnderlyingFrame()->Preserves3D()) {
> +        nsDisplayTransform *transform = static_cast<nsDisplayTransform*>(item);
> +        temp.AppendElement(FramesWithDepth(transform->GetHitDepthAtPoint(aRect.TopLeft())));

Probably go for the center of the rectangle
Attachment #564746 - Flags: review?(roc) → review+
Comment on attachment 564383 [details] [diff] [review]
Part 5: Add a test with overlapping layers

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

We could at least have something that tests parallel planes and planes that would intersect but only outside the bounds of the visible region.
(In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #32)
> 
> Probably go for the center of the rectangle

What does it actually mean when HitTest is called with a rectangle (instead of a point).

We can't really have a definitive ordering of frames for an area, so I assumed that the list of contained frames was all that mattered, and not the specific ordering.

I went with TopLeft() since it's simple and correct for the point case.
(In reply to Matt Woodrow (:mattwoodrow) from comment #34)
> (In reply to Robert O'Callahan (:roc) (Mozilla Corporation) from comment #32)
> > 
> > Probably go for the center of the rectangle
> 
> What does it actually mean when HitTest is called with a rectangle (instead
> of a point).

It means we're looking for all elements that intersect the rectangle.

I don't expect it's worth getting this exactly right for 3D transforms.

> I went with TopLeft() since it's simple and correct for the point case.

Yeah it probably doesn't matter, but when a rectangle is specified the center is probably slightly better approximation.
Fixed review comments, carrying forward r=roc
Attachment #564746 - Attachment is obsolete: true
Attachment #565056 - Flags: review+
Added more tests and pushed the queue to tryserver.
Attachment #564383 - Attachment is obsolete: true
Attachment #564383 - Flags: review?(roc)
Attachment #565058 - Flags: review?(roc)
Depends on: 693521
Depends on: 740789
No longer depends on: 740789
You need to log in before you can comment on or make changes to this bug.