Bug 120362 – [BlackBerry] Accelerated compositing layers are incorrectly Z sorted

• Component: WebKit BlackBerry
• Status: RESOLVED INVALID

[Arvid Nilsson]

The BlackBerry port used to sort layers by the Z coordinate of their
centroid, which is far too simplistic to yield the correct Z sorting
order.

According to section 6.1 of http://www.w3.org/TR/css3-transforms, "User
agents must render intersection by subdividing the planes of
intersecting elements as described by Newell's algorithm. [...] the
rendering order of non-intersecting elements is based on their position
on the Z axis after the application of the accumulated transform.
Elements at the same Z position render in stacking context order."

[Arvid Nilsson]

Created attachment 209867 [details]
Patch

[Arvid Nilsson]

Hi guys! Bjorn had great success implementing Z sorting using BSP instead of Newell's algorithm like the spec suggests.

I'm not sure where Coordinated Graphics are at when it comes to Z sorting, but perhaps this code can be interesting to you as well.

The drawback is the BSP generates more clipping than Newell's algorithm, which gives more layers to draw, but if drawing clipped layers is fast it's no problem. You can draw the layer multiple times using different texture coordinates to accomplish the clipping, for example.

LayerPlane, LayerPolygon and LayerBSPTree contain the main code, and should be easily portable to Coordinated Graphics. Perhaps by moving the classes up one step and renaming them GraphicsLayer*.h/cpp.

It works by accepting one or more LayerPolygon as input, builds a BSP tree from them and collects the resulting clipped LayerPolygon:s in order.

It uses a MemoryBucket class to allocate per-frame objects (the BSPTreeNodes that is) and throw them away all at once at the beginning of the next frame (similar idea to RenderArena).

Typical tree building time is less than 0.1-1 ms on most things we threw at it on the BlackBerry Z10. Typically it results in 1-3x the number of layers.

[Noam Rosenthal]

(In reply to comment #2)
> Hi guys! Bjorn had great success implementing Z sorting using BSP instead of Newell's algorithm like the spec suggests.
> 
> I'm not sure where Coordinated Graphics are at when it comes to Z sorting, but perhaps this code can be interesting to you as well.
> 
> The drawback is the BSP generates more clipping than Newell's algorithm, which gives more layers to draw, but if drawing clipped layers is fast it's no problem. You can draw the layer multiple times using different texture coordinates to accomplish the clipping, for example.
> 
> LayerPlane, LayerPolygon and LayerBSPTree contain the main code, and should be easily portable to Coordinated Graphics. Perhaps by moving the classes up one step and renaming them GraphicsLayer*.h/cpp.
> 
> It works by accepting one or more LayerPolygon as input, builds a BSP tree from them and collects the resulting clipped LayerPolygon:s in order.
> 
> It uses a MemoryBucket class to allocate per-frame objects (the BSPTreeNodes that is) and throw them away all at once at the beginning of the next frame (similar idea to RenderArena).
> 
> Typical tree building time is less than 0.1-1 ms on most things we threw at it on the BlackBerry Z10. Typically it results in 1-3x the number of layers.

Thanks Arvid
Yes, this is very interesting for coordinated graphics
I'll look at it after back from vacation in a few weeks but if someone else feels like picking it up go ahead

[Arvid Nilsson]

Obviously you only need to Z-sort layers that overlap in screen space. So we tried adding a pre-pass last week, filtering out the ones that don't overlap anything and only passing those that do to the BSP. It reduced the number of input layers on idzr.org/404 by quite a lot, thus reducing the amount of redundant clipping in the BSP tree, but didn't result in better framerate for us. I'm just noting it here in case someone else wants to try that out.

[Arvid Nilsson]

Created attachment 210445 [details]
Patch

New version of patch incorporates a bug fix courtesy of Gordon Sun, prevent LayerBSPTree from returning dangling pointers to the last frame's layers when called with an empty polygon list in the next frame (by setting m_rootNode to 0 when build is called with empty polygon list).