Closed Bug 1274673 Opened 6 years ago Closed 5 years ago

Use binary space partitioning for sorting/drawing layers

Categories

(Core :: Graphics: Layers, defect)

defect
Not set
normal

Tracking

()

RESOLVED FIXED
mozilla53
Tracking Status
firefox53 --- fixed

People

(Reporter: jrmuizel, Assigned: miko)

References

Details

(Keywords: feature, Whiteboard: [gfx-noted])

Attachments

(3 files)

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
Blocks: 689498
Keywords: feature
Whiteboard: [gfx-noted]
Assignee: nobody → mikokm
Status: NEW → ASSIGNED
Blocks: 1286716
Depends on: 1292390
Depends on: 1301818
Depends on: 1286412
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.
Most of the changes to actual layer implementations involve passing around a new aGeometry parameter of RenderLayer() method.
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 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!
Attachment #8817073 - Flags: review?(kgilbert) → review+
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
Attachment #8817072 - Flags: review?(bas) → review+
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 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
Attachment #8817074 - Flags: review?(matt.woodrow) → review+
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
Attachment #8817074 - Flags: review?(jmuizelaar) → review+
Keywords: checkin-needed
Pushed by cbook@mozilla.com:
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
Keywords: checkin-needed
https://hg.mozilla.org/mozilla-central/rev/101085325329
https://hg.mozilla.org/mozilla-central/rev/29b6c0a80512
https://hg.mozilla.org/mozilla-central/rev/459802a227c2
Status: ASSIGNED → RESOLVED
Closed: 5 years ago
Resolution: --- → FIXED
Target Milestone: --- → mozilla53
This could probably use a reftest
Pushed by kgupta@mozilla.com:
https://hg.mozilla.org/projects/graphics/rev/05f6c6e2e3d4
Fix build bustage from merging bug 1274673. r=jrmuizel?
Sorry about that, I didn't think pulsebot would comment on this bug. The above change is for the graphics branch only.
(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.
Depends on: 1328020
Depends on: 1345843
Depends on: 1351426
Depends on: 1359699
You need to log in before you can comment on or make changes to this bug.