1274673 - Use binary space partitioning for sorting/drawing layers

Status: RESOLVED FIXED

(Core :: Graphics: Layers, defect)

Description

[Jeff Muizelaar [:jrmuizel]]

This is what Chrome uses and also seems to be what CoreAnimation uses. It's properties basically match we're looking for.

https://docs.google.com/document/d/1XKD8d8Ud4D9aR1-pwnoFUn9jSfW1lNe2xeJmFJ8kSq8/edit

Comment 1

[Miko Mynttinen]

Attachment: Bug 1274673 - Use binary space partitioning for sorting/drawing layers - Part 1: Add Point4D construction/conversion from/to Point3D

Review commit: https://reviewboard.mozilla.org/r/97502/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/97502/

Comment 2

[Miko Mynttinen]

Attachment: Bug 1274673 - Use binary space partitioning for sorting/drawing layers - Part 2: Rename Polygon3D to Polygon, and use 4D points for all calculations

Review commit: https://reviewboard.mozilla.org/r/97504/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/97504/

Comment 3

[Miko Mynttinen]

Attachment: Bug 1274673 - Use binary space partitioning for sorting/drawing layers - Part 3: Use BSPTree for layer sorting

Review commit: https://reviewboard.mozilla.org/r/97506/diff/#index_header
See other reviews: https://reviewboard.mozilla.org/r/97506/

Comment 4

[Miko Mynttinen]

List of changes to existing files:

Polygon/BSPTree:
------------------------
- All calculations are now done in homogeneous space.
- Because the Polygon3D class now has operations in both 2D and 3D, and use 4D points, renaming it to just Polygon makes sense to avoid confusion.
- Points with w < 0 components are now clipped when transforming polygon back to screen space. This clipping could be improved to avoid using fixed w = 0.00001f, but as it is a relatively rare case, I think it makes sense to land it as it is and do such improvements later.


Compositor (part 2):
----------------------------
- Fix failing reftests with other texture effect types.
- Removed texture coordinate assertion because of weird Android FF behaviour (invalid texture coordinates).


Compositor (part 3):
----------------------------
- Add SupportsLayerGeometry() method that returns true if the compositor implementation supports layers with arbitrary geometry.


OGLCompositor / gfxPrefs:
-------------------------
- Add layers.geometry.opengl.enabled pref flag to allow toggling rendering arbitrary geometry layers with OpenGL compositor backend.

Comment 5

[Miko Mynttinen]

Most of the changes to actual layer implementations involve passing around a new aGeometry parameter of RenderLayer() method.

Comment 6

[Matt Woodrow (:mattwoodrow)]

Comment on attachment 8817074 [details]
Bug 1274673 - Use binary space partitioning for sorting/drawing layers - Part 3: Use BSPTree for layer sorting

https://reviewboard.mozilla.org/r/97506/#review97904

::: gfx/layers/Layers.h:2157
(Diff revision 1)
>      Mutated();
>    }
>  
>    virtual void FillSpecificAttributes(SpecificLayerAttributes& aAttrs) override;
>  
> -  void SortChildrenBy3DZOrder(nsTArray<Layer*>& aArray);
> +  nsTArray<LayerPolygon> SortChildrenBy3DZOrder(bool aUseLayerGeometry);

Can you make this return value nsTArray<LayerPolygon>&&? And then return Move(array);

We can get quite large layer arrays at times, so moving them seems simple and worthwhile.

::: gfx/layers/Layers.h:2246
(Diff revision 1)
>    void DidInsertChild(Layer* aLayer);
>    void DidRemoveChild(Layer* aLayer);
>  
>    void Collect3DContextLeaves(nsTArray<Layer*>& aToSort);
>  
> +  nsTArray<Layer*> CollectChildren() {

Add a comment about how this collects preserve-3d leaves, not just direct children, but doesn't do any sorting of them.

This could even be a 3rd mode to SortChildrenBy3DZOrder instead of a separate function (maybe using this name instead though).

::: gfx/layers/Layers.cpp:1349
(Diff revision 1)
>          }
>        }
>    );
>  }
>  
> -void
> +static nsTArray<LayerPolygon>

Rval reference here too please

::: gfx/layers/Layers.cpp:1371
(Diff revision 1)
> +    gfx::Polygon polygon = gfx::Polygon::FromRect(gfx::Rect(bounds));
> +
> +    // Transform the polygon to screen space.
> +    polygon.TransformToScreenSpace(transform);
> +
> +    if (polygon.GetPoints().Length() >= 3) {

When would this not be true?

Only if the bounds rect was empty? Can we just check for that instead?

::: gfx/layers/Layers.cpp:1396
(Diff revision 1)
> +  }
> +
> +  return orderedLayers;
> +}
> +
> +static nsTArray<LayerPolygon>

And here, and others.

::: gfx/layers/Layers.cpp:1415
(Diff revision 1)
> +
> +  return layers;
> +}
> +
> +nsTArray<LayerPolygon>
> +ContainerLayer::SortChildrenBy3DZOrder(bool aUseLayerGeometry)

Rather than a bool, can you use a two value enum for the different modes?

It just makes it a lot easier to understand the meaning from the callsites.

::: gfx/layers/Layers.cpp:1877
(Diff revision 1)
>      if (aDumpHtml) {
>        aStream << "<ul>";
>      }
>  
> -    for (Layer* child : children) {
> -      child->Dump(aStream, pfx.get(), aDumpHtml, aSorted);
> +    for (LayerPolygon& child : children) {
> +      child.layer->Dump(aStream, pfx.get(), aDumpHtml, aSorted);

Would be cool if we dumped the polygons here too, something to add when you get bored on a plane?

::: gfx/layers/composite/ContainerLayerComposite.cpp:446
(Diff revision 1)
>      } else {
> -      layerToRender->RenderLayer(clipRect.ToUnknownRect());
> +      Maybe<gfx::Polygon> geometry =
> +        SelectLayerGeometry(aGeometry, childGeometry);
> +
> +      if (geometry && !layer->Is3DContextLeaf()) {
> +        TransformLayerGeometry(layer, geometry);

This code (and the impl of this function is quite confusing).

The problem we're trying to solve here is that aGeometry is in the coordinate space of |aContainer| (the ContainerLayerComposite), but layer->RenderLayer expects geometry in the coordinate space of |layer|, right?

So don't we only need to do work in the case where we used aGeometry (both where we used it solely, and where we intersected it with childGeometry)?

We also need to do the transformation *before* we intersect the two geometries, since they are in different coord spaces.

We could also make TransformLayerGeometry take the two layer pointers (aContainer and layer), then the loop to accumulate transforms can just loop GetParent() until parent == aContainer.

Comment 7

[:kip (Kearwood Gilbert)]

Comment on attachment 8817073 [details]
Bug 1274673 - Use binary space partitioning for sorting/drawing layers - Part 2: Rename Polygon3D to Polygon, and use 4D points for all calculations

https://reviewboard.mozilla.org/r/97504/#review97946

This looks good, thanks!

Comment 8

[Bas Schouten (:bas.schouten)]

Comment on attachment 8817072 [details]
Bug 1274673 - Use binary space partitioning for sorting/drawing layers - Part 1: Add Point4D construction/conversion from/to Point3D

https://reviewboard.mozilla.org/r/97502/#review98102

Comment 9

[Miko Mynttinen]

Comment on attachment 8817074 [details]
Bug 1274673 - Use binary space partitioning for sorting/drawing layers - Part 3: Use BSPTree for layer sorting

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/97506/diff/1-2/

Comment 10

[Miko Mynttinen]

Comment on attachment 8817074 [details]
Bug 1274673 - Use binary space partitioning for sorting/drawing layers - Part 3: Use BSPTree for layer sorting

https://reviewboard.mozilla.org/r/97506/#review97904

> Can you make this return value nsTArray<LayerPolygon>&&? And then return Move(array);
> 
> We can get quite large layer arrays at times, so moving them seems simple and worthwhile.

My understanding of move semantics is that returning an rvalue reference to a function local temporary is not usually what is wanted.
Modern compilers avoid making a copy by performing named return value optimization (http://en.cppreference.com/w/cpp/language/copy_elision).

> When would this not be true?
> 
> Only if the bounds rect was empty? Can we just check for that instead?

Transforming polygon back to screen space clips w < 0 points, and this might result in degenerate polygons.

> Would be cool if we dumped the polygons here too, something to add when you get bored on a plane?

Done.

> This code (and the impl of this function is quite confusing).
> 
> The problem we're trying to solve here is that aGeometry is in the coordinate space of |aContainer| (the ContainerLayerComposite), but layer->RenderLayer expects geometry in the coordinate space of |layer|, right?
> 
> So don't we only need to do work in the case where we used aGeometry (both where we used it solely, and where we intersected it with childGeometry)?
> 
> We also need to do the transformation *before* we intersect the two geometries, since they are in different coord spaces.
> 
> We could also make TransformLayerGeometry take the two layer pointers (aContainer and layer), then the loop to accumulate transforms can just loop GetParent() until parent == aContainer.

Unless I understand incorrectly, we have to go upwards the layer hierarchy until we encounter a parent 3D context leaf. I added some comments to clarify this.

Comment 11

[Miko Mynttinen]

Comment on attachment 8817074 [details]
Bug 1274673 - Use binary space partitioning for sorting/drawing layers - Part 3: Use BSPTree for layer sorting

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/97506/diff/2-3/

Comment 12

[Miko Mynttinen]

Comment on attachment 8817074 [details]
Bug 1274673 - Use binary space partitioning for sorting/drawing layers - Part 3: Use BSPTree for layer sorting

Review request updated; see interdiff: https://reviewboard.mozilla.org/r/97506/diff/3-4/

Comment 13

[Matt Woodrow (:mattwoodrow)]

Comment on attachment 8817074 [details]
Bug 1274673 - Use binary space partitioning for sorting/drawing layers - Part 3: Use BSPTree for layer sorting

https://reviewboard.mozilla.org/r/97506/#review98326

Comment 14

[Jeff Muizelaar [:jrmuizel]]

Comment on attachment 8817074 [details]
Bug 1274673 - Use binary space partitioning for sorting/drawing layers - Part 3: Use BSPTree for layer sorting

https://reviewboard.mozilla.org/r/97506/#review98392

Comment 15

[Miko Mynttinen]

https://treeherder.mozilla.org/#/jobs?repo=try&revision=f5ec411e93c9880a79942be1858427dca6f39198

Comment 16

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/integration/autoland/rev/101085325329
Use binary space partitioning for sorting/drawing layers - Part 1: Add Point4D construction/conversion from/to Point3D r=bas
https://hg.mozilla.org/integration/autoland/rev/29b6c0a80512
Use binary space partitioning for sorting/drawing layers - Part 2: Rename Polygon3D to Polygon, and use 4D points for all calculations r=kip
https://hg.mozilla.org/integration/autoland/rev/459802a227c2
Use binary space partitioning for sorting/drawing layers - Part 3: Use BSPTree for layer sorting r=jrmuizel,mattwoodrow

Comment 17

[Carsten Book [:Tomcat]]

https://hg.mozilla.org/mozilla-central/rev/101085325329
https://hg.mozilla.org/mozilla-central/rev/29b6c0a80512
https://hg.mozilla.org/mozilla-central/rev/459802a227c2

Comment 18

[Jeff Muizelaar [:jrmuizel]]

This could probably use a reftest

Comment 19

[Pulsebot]

Pushed by [e-mail]:
https://hg.mozilla.org/projects/graphics/rev/05f6c6e2e3d4
Fix build bustage from merging bug 1274673. r=jrmuizel?

Comment 20

[Kartikaya Gupta (email:[e-mail])]

Sorry about that, I didn't think pulsebot would comment on this bug. The above change is for the graphics branch only.

Comment 21

[Miko Mynttinen]

(In reply to Jeff Muizelaar [:jrmuizel] from comment #18)
> This could probably use a reftest

Definitely. I'll add some along with BasicCompositor backend changes.