Bug 59255 – [chromium] Improve sorting of 3D layers

• Component: WebCore Misc.
• Status: RESOLVED FIXED

[Vangelis Kokkevis]

Currently layers in hierarchies that perserve-3d are sorted based on the Z coordinate of the layer's center which doesn't work well in a number of cases, including when layers are close to perpendicular.

[Vangelis Kokkevis]

Created attachment 90810 [details]
Patch

[WebKit Review Bot]

Attachment 90810 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/8496558

[WebKit Review Bot]

Attachment 90810 [details] did not build on chromium:
Build output: http://queues.webkit.org/results/8493717

[Vangelis Kokkevis]

Created attachment 90949 [details]
Patch

[Vangelis Kokkevis]

New patch uploaded that fixes compile failure.

[Eric Seidel (no email)]

@kbr: please review this as part of the reviewathon.

[Kenneth Russell]

Comment on attachment 90949 [details]
Patch

View in context: https://bugs.webkit.org/attachment.cgi?id=90949&action=review

The overall idea of the patch looks good. There are a couple of logic flaws that definitely need to be fixed. I won't insist that code be shared between this class and LoopBlinnMathUtils, but it would be nice if at least some could be. More layout tests for edge cases would be good.

> Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:61
> +inline static bool pointInSegment(const FloatPoint& p, const FloatPoint& a, const FloatPoint& b)

How about naming this "pointInCollinearSegment" then and deleting the comment?

> Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:65
> +        return ((p.x() >= min(a.x(), b.x()) && p.x() <= max(a.x(), b.x())));

There's an unnecessary pair of parentheses around the expression.

> Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:67
> +    return ((p.y() >= min(a.y(), b.y()) && p.y() <= max(a.y(), b.y())));

Another unnecessary pair of parentheses.

> Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:70
> +static bool segmentSegmentIntersect(const FloatPoint& a, const FloatPoint& b, const FloatPoint& c, const FloatPoint& d, FloatPoint& r)

There's another edge/edge test in Source/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp. It would be better to reuse it. It doesn't currently report the intersection point though. It also has different semantics than this (collinear lines do not report overlap) so perhaps that's a reason to have a different version. Still it would be nice to refactor this code, perhaps into a new math utility class.

> Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:72
> +    static float epsilon = 0.00001;

It's unfortunate that there are multiple, differing, local epsilon values throughout this file.

> Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:82
> +        return false;

This early return subsumes all of the code below it. There is something wrong with the logic here.

> Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:124
> +static bool pointInTriangle(const FloatPoint& p, const FloatPoint& a, const FloatPoint& b, const FloatPoint& c)

There's another pointInTriangle in Source/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp. It would be better to reuse it.

> Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:159
> +    (triangleTriangleIntersect(m_nodeA->m_c1, m_nodeA->m_c2, m_nodeA->m_c3, m_nodeB->m_c1, m_nodeB->m_c2, m_nodeB->m_c3)
> +     || triangleTriangleIntersect(m_nodeA->m_c1, m_nodeA->m_c2, m_nodeA->m_c3, m_nodeB->m_c1, m_nodeB->m_c2, m_nodeB->m_c3)

These two lines are equivalent.

> Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:167
> +bool CCLayerSorter::LayerIntersector::segmentTriangleIntersect(const FloatPoint& p, const FloatPoint& q, const FloatPoint& a, const FloatPoint& b, const FloatPoint& c)

There's another edge/triangle test in Source/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp. It would be better to reuse it.

> Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:179
> +bool CCLayerSorter::LayerIntersector::triangleTriangleIntersect(const FloatPoint& a1, const FloatPoint& b1, const FloatPoint& c1, const FloatPoint& a2, const FloatPoint& b2, const FloatPoint& c2)

There's another triangle/triangle overlap test in Source/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp. It would be better to reuse it. Note however that that version deliberately does not report "true" if the triangles only share a single coincident vertex or edge.

> Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:288
> +        GraphNode* node = &m_nodes.at(m_nodes.size() - 1);

Why not write "GraphNode& node = m_nodes.at(m_nodes.size() - 1);", making the intent more clear?

> Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:334
> +    m_edges.clear();
> +    m_activeEdges.clear();

It seems risky to separate out the clearing of the edges and active edges from the clearing of the node list because these retain pointers into the list.

> Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:479
> +    for (LayerList::iterator it = first; it < last; it++)
> +        *it = sortedList[count++]->m_layer;

This looks risky. GraphNode doesn't currently increment the reference count of its layer, so I could imagine the assignment here decrementing the current referent of "*it" to zero and causing it to be deleted.

> Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:480
> +

For cleanliness it looks to me like m_nodes and m_edges should be cleared on the way out of this method.

> Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.h:51
> +        CCLayerImpl* m_layer;

WebKit naming convention is to drop the m_ prefix in structs.

[Vangelis Kokkevis]

Created attachment 91696 [details]
Patch

[Vangelis Kokkevis]

(In reply to comment #7)
> (From update of attachment 90949 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=90949&action=review
> 
> The overall idea of the patch looks good. There are a couple of logic flaws that definitely need to be fixed. I won't insist that code be shared between this class and LoopBlinnMathUtils, but it would be nice if at least some could be. More layout tests for edge cases would be good.
> 
Thanks for pointing those out.  I was able to re-use one of them but not all.  Please see below.

> > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:61
> > +inline static bool pointInSegment(const FloatPoint& p, const FloatPoint& a, const FloatPoint& b)
> 
> How about naming this "pointInCollinearSegment" then and deleting the comment?
> 

Done.

> > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:65
> > +        return ((p.x() >= min(a.x(), b.x()) && p.x() <= max(a.x(), b.x())));
> 
> There's an unnecessary pair of parentheses around the expression.
> 

Done.

> > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:67
> > +    return ((p.y() >= min(a.y(), b.y()) && p.y() <= max(a.y(), b.y())));
> 
> Another unnecessary pair of parentheses.
> 
Done.

> > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:70
> > +static bool segmentSegmentIntersect(const FloatPoint& a, const FloatPoint& b, const FloatPoint& c, const FloatPoint& d, FloatPoint& r)
> 
> There's another edge/edge test in Source/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp. It would be better to reuse it. It doesn't currently report the intersection point though. It also has different semantics than this (collinear lines do not report overlap) so perhaps that's a reason to have a different version. Still it would be nice to refactor this code, perhaps into a new math utility class.
> 

Unfortunately I could not re-use the LoopBlinnMathUtils implementation as sorting does indeed care about co-linear edges.


> > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:72
> > +    static float epsilon = 0.00001;
> 
> It's unfortunate that there are multiple, differing, local epsilon values throughout this file.
> 

Epsilons have mostly been removed from the file as they weren't truly necessary.

> > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:82
> > +        return false;
> 
> This early return subsumes all of the code below it. There is something wrong with the logic here.
> 
> > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:124
> > +static bool pointInTriangle(const FloatPoint& p, const FloatPoint& a, const FloatPoint& b, const FloatPoint& c)
> 
> There's another pointInTriangle in Source/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp. It would be better to reuse it.
> 

Switched over to that implementation.  

> > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:159
> > +    (triangleTriangleIntersect(m_nodeA->m_c1, m_nodeA->m_c2, m_nodeA->m_c3, m_nodeB->m_c1, m_nodeB->m_c2, m_nodeB->m_c3)
> > +     || triangleTriangleIntersect(m_nodeA->m_c1, m_nodeA->m_c2, m_nodeA->m_c3, m_nodeB->m_c1, m_nodeB->m_c2, m_nodeB->m_c3)
> 
> These two lines are equivalent.

Ooops... done.

> 
> > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:167
> > +bool CCLayerSorter::LayerIntersector::segmentTriangleIntersect(const FloatPoint& p, const FloatPoint& q, const FloatPoint& a, const FloatPoint& b, const FloatPoint& c)
> 
> There's another edge/triangle test in Source/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp. It would be better to reuse it.
> 
> > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:179
> > +bool CCLayerSorter::LayerIntersector::triangleTriangleIntersect(const FloatPoint& a1, const FloatPoint& b1, const FloatPoint& c1, const FloatPoint& a2, const FloatPoint& b2, const FloatPoint& c2)
> 
> There's another triangle/triangle overlap test in Source/WebCore/platform/graphics/gpu/LoopBlinnMathUtils.cpp. It would be better to reuse it. Note however that that version deliberately does not report "true" if the triangles only share a single coincident vertex or edge.
> 

I could not use that test as it depends on the edge-edge test that needs to be special in this case.

> > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:288
> > +        GraphNode* node = &m_nodes.at(m_nodes.size() - 1);
> 
> Why not write "GraphNode& node = m_nodes.at(m_nodes.size() - 1);", making the intent more clear?
> 

Done.

> > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:334
> > +    m_edges.clear();
> > +    m_activeEdges.clear();
> 
> It seems risky to separate out the clearing of the edges and active edges from the clearing of the node list because these retain pointers into the list.
> 

Good point.  Moved clears over to the end of the sort method.

> > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:479
> > +    for (LayerList::iterator it = first; it < last; it++)
> > +        *it = sortedList[count++]->m_layer;
> 
> This looks risky. GraphNode doesn't currently increment the reference count of its layer, so I could imagine the assignment here decrementing the current referent of "*it" to zero and causing it to be deleted.
> 

It does look risky but it's not a real risk in this case as the layers in that list are always kept alive by their RefCounted parent node.

> > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.cpp:480
> > +
> 
> For cleanliness it looks to me like m_nodes and m_edges should be cleared on the way out of this method.

Done.

> 
> > Source/WebCore/platform/graphics/chromium/cc/CCLayerSorter.h:51
> > +        CCLayerImpl* m_layer;
> 
> WebKit naming convention is to drop the m_ prefix in structs.

[Vangelis Kokkevis]

Created attachment 91757 [details]
Patch

[Vangelis Kokkevis]

(In reply to comment #10)
> Created an attachment (id=91757) [details]
> Patch

This last patch addresses the last review comment about removing the m_ prefix from all struct members.

[Kenneth Russell]

Comment on attachment 91757 [details]
Patch

Thanks, looks better. r=me

[Vangelis Kokkevis]

Committed r85814: <http://trac.webkit.org/changeset/85814>