Add local triangulation of cubic curve control points

[Kenneth Russell]

As part of the GPU accelerated path rendering algorithm in https://bugs.webkit.org/show_bug.cgi?id=44729 , a local triangulation algorithm is needed for the four points defining a cubic curve. This triangulator needs to support walking the interior edges of the shape in order to feed those edges to a more general triangulation algorithm which handles filling of the interior of the shape.

[Kenneth Russell]

Created attachment 66611 [details]
Patch

From the ChangeLog:

Adding a localized triangulation algorithm which takes as input the four control points of a cubic curve segment and provides both triangles as well as the ability to walk the interior edges. The latter will be used later to fill the interior of shapes bounded by these cubic curves, quadratic curves and line segments.

[James Robinson]

Comment on attachment 66611 [details]
Patch

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

> WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp:35
> +using namespace LoopBlinnMathUtils;
explicitly 'using' the functions used in this cpp

> WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp:39
> +    for (int i = 0; i < 3; i++)
nit: could use indexForVertex()

> WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp:45
> +LoopBlinnLocalTriangulator::Vertex* LoopBlinnLocalTriangulator::Triangle::nextVertex(LoopBlinnLocalTriangulator::Vertex* cur, bool ccw)
rename params as in header

> WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp:101
> +    bool done = false;
instead of having a done flag, could the work in the first half of this function be a helper that early-returns?

> WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp:107
> +    for (int i = 0; i < 4 && !done; i++)
> +        for (int j = i + 1; j < 4 && !done; j++)
these need braces

> WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp:231
> +                    if (!next->marked()
> +                        && !isSharedEdge(v, next)
> +                        && (!next->interior() || next->end())) {
intentation looks funny. I think the predicate can go one line

> WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp:242
> +            // Something went wrong with the above algorithm; add the last
add a FIXME?

> WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.h:46
> +        Vertex()
initialize the flags in here

> WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.h:141
> +        Vertex* nextVertex(Vertex* cur, bool ccw);
cur -> current

ccw -> counterClockWise, or an enum { ClockWise, CounterClockWise }

> WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.h:165
> +        Vertex* m_vertices[3];
Add a comment indicating why these are raw pointers (that they point to data from the arena or something of that sort).

> WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.h:196
> +    void triangulate(bool computeInsideEdges,
> +                     bool fillRightSide);
these bool params should be enums so callsites look more like triangulage(ComputeInsideEdges, FillLeftSide);

[Kenneth Russell]

Created attachment 67083 [details]
Revised patch

Revised patch addressing above code review comments.

[Kenneth Russell]

(In reply to comment #2)
> (From update of attachment 66611 [details])
> View in context: https://bugs.webkit.org/attachment.cgi?id=66611&action=prettypatch
> 
> > WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp:35
> > +using namespace LoopBlinnMathUtils;
> explicitly 'using' the functions used in this cpp

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp:39
> > +    for (int i = 0; i < 3; i++)
> nit: could use indexForVertex()

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp:45
> > +LoopBlinnLocalTriangulator::Vertex* LoopBlinnLocalTriangulator::Triangle::nextVertex(LoopBlinnLocalTriangulator::Vertex* cur, bool ccw)
> rename params as in header

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp:101
> > +    bool done = false;
> instead of having a done flag, could the work in the first half of this function be a helper that early-returns?

Yes. Done; refactored first half into triangulateHelper.

> > WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp:107
> > +    for (int i = 0; i < 4 && !done; i++)
> > +        for (int j = i + 1; j < 4 && !done; j++)
> these need braces

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp:231
> > +                    if (!next->marked()
> > +                        && !isSharedEdge(v, next)
> > +                        && (!next->interior() || next->end())) {
> intentation looks funny. I think the predicate can go one line

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.cpp:242
> > +            // Something went wrong with the above algorithm; add the last
> add a FIXME?

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.h:46
> > +        Vertex()
> initialize the flags in here

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.h:141
> > +        Vertex* nextVertex(Vertex* cur, bool ccw);
> cur -> current
> 
> ccw -> counterClockWise, or an enum { ClockWise, CounterClockWise }

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.h:165
> > +        Vertex* m_vertices[3];
> Add a comment indicating why these are raw pointers (that they point to data from the arena or something of that sort).

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnLocalTriangulator.h:196
> > +    void triangulate(bool computeInsideEdges,
> > +                     bool fillRightSide);
> these bool params should be enums so callsites look more like triangulage(ComputeInsideEdges, FillLeftSide);

Done.

[Kenneth Russell]

Created attachment 67149 [details]
Revised patch

Renamed numTriangles to numberOfTriangles and numInteriorVertices to numberOfInteriorVertices to avoid abbreviations.

[James Robinson]

Comment on attachment 67149 [details]
Revised patch

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

Looks good!

[Kenneth Russell]

Committed r68045: <http://trac.webkit.org/changeset/68045>

[Kenneth Russell]

Committed r68439: <http://trac.webkit.org/changeset/68439>

[WebKit Review Bot]

http://trac.webkit.org/changeset/68439 might have broken Qt Linux Release
The following changes are on the blame list:
http://trac.webkit.org/changeset/68440
http://trac.webkit.org/changeset/68439