Last Comment Bug 684759 - Implement better sorting for preserve-3d child layers
: Implement better sorting for preserve-3d child layers
Status: RESOLVED FIXED
[inbound]
:
Product: Core
Classification: Components
Component: Layout (show other bugs)
: unspecified
: x86 Mac OS X
: -- normal (vote)
: mozilla10
Assigned To: Matt Woodrow (:mattwoodrow)
:
Mentors:
Depends on: 693521
Blocks: 505115
  Show dependency treegraph
 
Reported: 2011-09-05 15:00 PDT by Matt Woodrow (:mattwoodrow)
Modified: 2012-06-03 14:04 PDT (History)
4 users (show)
See Also:
Crash Signature:
(edit)
QA Whiteboard:
Iteration: ---
Points: ---
Has Regression Range: ---
Has STR: ---


Attachments
Sort based on the depth at the intersection points (16.21 KB, patch)
2011-09-05 15:00 PDT, Matt Woodrow (:mattwoodrow)
no flags Details | Diff | Review
Sort based on the depth at the intersection points v2 (39.02 KB, patch)
2011-09-06 01:09 PDT, Matt Woodrow (:mattwoodrow)
no flags Details | Diff | Review
Sort based on the depth at the intersection points v3 (31.19 KB, patch)
2011-09-26 01:06 PDT, Matt Woodrow (:mattwoodrow)
no flags Details | Diff | Review
Sort based on the depth at the intersection points v4 (35.19 KB, patch)
2011-09-26 01:10 PDT, Matt Woodrow (:mattwoodrow)
no flags Details | Diff | Review
Part 1: Flatten out nsDisplayWrapLists (4.16 KB, patch)
2011-10-03 16:09 PDT, Matt Woodrow (:mattwoodrow)
no flags Details | Diff | Review
Part 2: Add DirectedGraph and gfxQuad (10.22 KB, patch)
2011-10-03 16:10 PDT, Matt Woodrow (:mattwoodrow)
roc: review+
Details | Diff | Review
Part 3: Add Layer sorting code and event handling (25.87 KB, patch)
2011-10-03 16:11 PDT, Matt Woodrow (:mattwoodrow)
no flags Details | Diff | Review
Part 4: Make the layer managers use layer sorting (4.77 KB, patch)
2011-10-03 16:11 PDT, Matt Woodrow (:mattwoodrow)
no flags Details | Diff | Review
Part 5: Add a test with overlapping layers (2.36 KB, patch)
2011-10-03 16:12 PDT, Matt Woodrow (:mattwoodrow)
no flags Details | Diff | Review
Part 1: Flatten out nsDisplayWrapLists v2 (2.83 KB, patch)
2011-10-03 19:17 PDT, Matt Woodrow (:mattwoodrow)
roc: review+
Details | Diff | Review
Part 3: Add Layer sorting code v2 (20.59 KB, patch)
2011-10-04 19:58 PDT, Matt Woodrow (:mattwoodrow)
roc: review+
Details | Diff | Review
Part 3b: Add event handling (5.99 KB, patch)
2011-10-04 19:59 PDT, Matt Woodrow (:mattwoodrow)
roc: review+
Details | Diff | Review
Part 4: Make the layer managers use layer sorting v2 (4.94 KB, patch)
2011-10-04 20:00 PDT, Matt Woodrow (:mattwoodrow)
roc: review+
Details | Diff | Review
Part 3b: Add event handling v2 (6.27 KB, patch)
2011-10-05 16:20 PDT, Matt Woodrow (:mattwoodrow)
matt.woodrow: review+
Details | Diff | Review
Part 5: Add a test with overlapping layers v2 (7.72 KB, patch)
2011-10-05 16:21 PDT, Matt Woodrow (:mattwoodrow)
roc: review+
Details | Diff | Review

Description Matt Woodrow (:mattwoodrow) 2011-09-05 15:00:50 PDT
Created attachment 558349 [details] [diff] [review]
Sort based on the depth at the intersection points

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.
Comment 1 Matt Woodrow (:mattwoodrow) 2011-09-05 15:07:54 PDT
I also haven't added explicit handling for cycles of layers. Will the current sorting code be able to handle this?
Comment 2 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-09-05 16:31:05 PDT
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 3 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-09-05 17:01:17 PDT
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?
Comment 4 Matt Woodrow (:mattwoodrow) 2011-09-06 01:09:00 PDT
Created attachment 558419 [details] [diff] [review]
Sort based on the depth at the intersection points v2

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.
Comment 5 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-09-06 17:04:41 PDT
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!!!
Comment 6 Matt Woodrow (:mattwoodrow) 2011-09-26 01:06:50 PDT
Created attachment 562369 [details] [diff] [review]
Sort based on the depth at the intersection points v3
Comment 7 Matt Woodrow (:mattwoodrow) 2011-09-26 01:10:32 PDT
Created attachment 562370 [details] [diff] [review]
Sort based on the depth at the intersection points v4

Added missing file
Comment 8 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-09-26 03:05:54 PDT
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.
Comment 9 Matt Woodrow (:mattwoodrow) 2011-09-26 17:12:02 PDT
> 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.
Comment 10 Matt Woodrow (:mattwoodrow) 2011-10-02 21:28:54 PDT
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.
Comment 11 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-10-02 21:43:09 PDT
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.
Comment 12 Matt Woodrow (:mattwoodrow) 2011-10-03 16:09:41 PDT
Created attachment 564378 [details] [diff] [review]
Part 1: Flatten out nsDisplayWrapLists

This flattens out preserve-3d hierarchies so that all the children we care about are direct siblings.
Comment 13 Matt Woodrow (:mattwoodrow) 2011-10-03 16:10:25 PDT
Created attachment 564379 [details] [diff] [review]
Part 2: Add DirectedGraph and gfxQuad

Helper classes for sorting
Comment 14 Matt Woodrow (:mattwoodrow) 2011-10-03 16:11:20 PDT
Created attachment 564381 [details] [diff] [review]
Part 3: Add Layer sorting code and event handling
Comment 15 Matt Woodrow (:mattwoodrow) 2011-10-03 16:11:59 PDT
Created attachment 564382 [details] [diff] [review]
Part 4: Make the layer managers use layer sorting
Comment 16 Matt Woodrow (:mattwoodrow) 2011-10-03 16:12:35 PDT
Created attachment 564383 [details] [diff] [review]
Part 5: Add a test with overlapping layers
Comment 17 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-10-03 18:21:14 PDT
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
Comment 18 Matt Woodrow (:mattwoodrow) 2011-10-03 19:17:10 PDT
(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.
Comment 19 Matt Woodrow (:mattwoodrow) 2011-10-03 19:17:41 PDT
Created attachment 564433 [details] [diff] [review]
Part 1: Flatten out nsDisplayWrapLists v2
Comment 20 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-10-04 12:39:14 PDT
Your patches need PRBool -> bool
Comment 21 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-10-04 13:12:32 PDT
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.
Comment 22 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-10-04 13:12:59 PDT
Also, it's probably worth breaking patch 3 into separate layers and event-handling patches.
Comment 23 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-10-04 13:15:18 PDT
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 24 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-10-04 13:16:37 PDT
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.
Comment 25 Matt Woodrow (:mattwoodrow) 2011-10-04 19:14:36 PDT
(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.
Comment 26 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-10-04 19:34:09 PDT
It's an auto-array, so it's just a memcpy. No heap allocations involved. Really, it's fine.
Comment 27 Matt Woodrow (:mattwoodrow) 2011-10-04 19:58:21 PDT
(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 (< -> <=)
Comment 28 Matt Woodrow (:mattwoodrow) 2011-10-04 19:58:52 PDT
Created attachment 564744 [details] [diff] [review]
Part 3: Add Layer sorting code v2
Comment 29 Matt Woodrow (:mattwoodrow) 2011-10-04 19:59:29 PDT
Created attachment 564746 [details] [diff] [review]
Part 3b: Add event handling
Comment 30 Matt Woodrow (:mattwoodrow) 2011-10-04 20:00:08 PDT
Created attachment 564747 [details] [diff] [review]
Part 4: Make the layer managers use layer sorting v2
Comment 31 Matt Woodrow (:mattwoodrow) 2011-10-04 20:05:10 PDT
(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 32 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-10-04 20:13:23 PDT
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
Comment 33 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-10-04 20:17:30 PDT
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.
Comment 34 Matt Woodrow (:mattwoodrow) 2011-10-04 22:00:18 PDT
(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.
Comment 35 Robert O'Callahan (:roc) (Exited; email my personal email if necessary) 2011-10-04 22:06:36 PDT
(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.
Comment 36 Matt Woodrow (:mattwoodrow) 2011-10-05 16:20:43 PDT
Created attachment 565056 [details] [diff] [review]
Part 3b: Add event handling v2

Fixed review comments, carrying forward r=roc
Comment 37 Matt Woodrow (:mattwoodrow) 2011-10-05 16:21:22 PDT
Created attachment 565058 [details] [diff] [review]
Part 5: Add a test with overlapping layers v2

Added more tests and pushed the queue to tryserver.

Note You need to log in before you can comment on or make changes to this bug.