Bug 45521 – Incorporate algorithm for processing paths into GPU-renderable triangle meshes

• Component: Layout and Rendering
• Status: RESOLVED FIXED

[Kenneth Russell]

The main algorithm for transforming paths into triangle meshes which can be efficiently rendered on the GPU needs to be integrated. This is the last step in initial integration of Loop and Blinn's algorithm; the rest involves invoking this algorithm and drawing the results via GraphicsContext3D, which will be integrated separately.

[Kenneth Russell]

Created attachment 67158 [details]
Patch

From the ChangeLog:

Adding an implementation of Loop and Blinn's GPU accelerated path rendering algorithm from GPU Gems 3. This implementation pays particular attention to the efficiency of the curve subdivision phase needed for correct rendering. It utilizes the OpenGL utility library tessellator for triangulation of the interior of the shape. The regions handled by Loop and Blinn's algorithm are handled by the local triangulator previously incorporated.

No tests yet; pixel tests will eventually be used to verify this algorithm and prevent regressions.

[James Robinson]

Comment on attachment 67158 [details]
Patch

I've looked through everything here except for:
determineSidesToFill()
determineOrientation()
subdivideCurves()
conditionallySubdivide()
subdivideCurvesSlow()

I think we should go through those together, the math looks tricky.  Otherwise this patch is looking great.

One higher level comment - could we move Contour and Triangle to their own file or files?  I see that they are internal and not exposed API, but LoopBlinnPathProcessor.cpp is pretty big.  One option would be to move them to *Internal.h/cpp.

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

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:184
> +        // Try to set up a link between "this->prev()" and "left".
> +        if (prev()) {
> +            left->setPrev(prev());
> +            prev()->setNext(left);
> +        }
> +        // Try to set up a link between "this->next()" and "right".
> +        Segment* n = next();
> +        if (n) {
I'm pretty sure prev() and next() can never be null here, since Contour uses a sentinel value.

Can this just call m_contour->add(right) ?

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:347
> +            // m_first->prev() is the sentinel.
> +            Segment* sentinel = m_first->prev();
> +            Segment* last = sentinel->prev();
Why not use m_sentinel?

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:388
> +    Segment* end() const { return m_first->prev(); }
m_first->prev() should always == sentinel, right?  Adding an ASSERT() and returning &m_sentinel seems a bit better.

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:393
> +    const FloatRect& boundingBox() const
This doesn't need to be const (and thus m_boundingBox(Dirty)? don't need to be mutable).

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:516
> +    for (Vector<Contour*>::iterator iter = m_contours.begin();
> +         iter != m_contours.end();
> +         iter++) {
nit: could be a one-liner

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:548
> +                                cache.addVertex(vert->xyCoordinates().x(),
> +                                                vert->xyCoordinates().y(),
> +                                                vert->klmCoordinates().x(),
> +                                                vert->klmCoordinates().y(),
> +                                                vert->klmCoordinates().z());
Maybe LoopBlinnPathCache::addVertex should just take a LoopBlinnLocalTriangulator::Vertex*

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:670
> +Vector<Segment*> LoopBlinnPathProcessor::allSegmentsOverlappingY(Contour* queryContour, float x, float y)
should this be behind #ifndef NDEBUG?

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:675
> +    for (Vector<Contour*>::iterator iter = m_contours.begin();
> +         iter != m_contours.end();
> +         iter++) {
nit: one line

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:693
> +inline String valueToString(const float& value)
nit: I think you want static here instead of inline

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:698
> +inline String valueToString(void* const& value)
s/inline/static/

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:720
> +    for (Vector<Contour*>::iterator iter = m_contours.begin();
> +         iter != m_contours.end();
> +         iter++) {
nit: one line

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:739
> +    for (Vector<Contour*>::iterator iter = m_contours.begin();
> +         iter != m_contours.end();
> +         iter++) {
nit: one line

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:755
> +        for (Segment* seg = cur->begin();
> +             ambiguous && seg != cur->end();
> +             seg = seg->next()) {
nit: one line

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1144
> +    GLdouble* outVertex = static_cast<GLdouble*>(malloc(3 * sizeof(GLdouble)));
I think you should use fastMalloc() here.  It's #defined to system malloc in chromium (which is tcmalloc on windows/linux) but can also be #defined to debug allocators in some configs, which is handy.

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1154
> +    // No-op just to prevent triangle strips and fans from being passed to us.
I had to do some googling to figure out what this meant.  Guessing this is because of this text from http://glprogramming.com/red/chapter11.html:
"Since edge flags make no sense in a triangle fan or triangle strip, if there is a callback associated with GLU_TESS_EDGE_FLAG that enables edge flags, the GLU_TESS_BEGIN callback is called only with GL_TRIANGLES. The GLU_TESS_EDGE_FLAG callback works exactly analogously to the OpenGL glEdgeFlag*() call."?

Could you add a reference to some canonical source of info for this?

Don't name the GLboolean flag if it is unused, this will avoid unusued variable warnings.

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1170
> +    for (Vector<Contour*>::iterator iter = m_contours.begin();
> +         iter != m_contours.end();
> +         iter++) {
nit: one line

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1220
> +        free(state.allocatedPointers[i]);
fastFree() here

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.h:66
> +    LoopBlinnPathProcessor();
> +    explicit LoopBlinnPathProcessor(PassRefPtr<PODArena> arena);
Should this class just take a Path in the constructor?  It looks like it's tied to the path object itself and not used for multiple paths (at least currently).

nit: don't name this parameter (same with path, cache, contour, seg, queryContour below)

> WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.h:104
> +    // For debugging the orientation computation. Returns all of the
> +    // segments overlapping the given Y coordinate.
> +    Vector<LoopBlinnPathProcessorImplementation::Segment*> allSegmentsOverlappingY(LoopBlinnPathProcessorImplementation::Contour* queryContour, float x, float y);
should this move behind the #ifndef NDEBUG guard?

[Adam Barth]

Comment on attachment 67158 [details]
Patch

Can you upload a new version of this patch that addresses James comments?

[Kenneth Russell]

(In reply to comment #3)
> (From update of attachment 67158 [details])
> Can you upload a new version of this patch that addresses James comments?

Eventually, yes. I have been swamped for the past three months.

[Kenneth Russell]

(In reply to comment #2)
> (From update of attachment 67158 [details])
> I've looked through everything here except for:
> determineSidesToFill()
> determineOrientation()
> subdivideCurves()
> conditionallySubdivide()
> subdivideCurvesSlow()
> 
> I think we should go through those together, the math looks tricky.  Otherwise this patch is looking great.

We can certainly go through those methods together. Agreed, the math is tricky, and you can see from the FIXME in process() that it isn't 100% bug-free yet.

> One higher level comment - could we move Contour and Triangle to their own file or files?  I see that they are internal and not exposed API, but LoopBlinnPathProcessor.cpp is pretty big.  One option would be to move them to *Internal.h/cpp.

Let's discuss this. I'd like to avoid creating too many new files, and WebKit style is one top-level class per file.

> View in context: https://bugs.webkit.org/attachment.cgi?id=67158&action=prettypatch
> 
> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:184
> > +        // Try to set up a link between "this->prev()" and "left".
> > +        if (prev()) {
> > +            left->setPrev(prev());
> > +            prev()->setNext(left);
> > +        }
> > +        // Try to set up a link between "this->next()" and "right".
> > +        Segment* n = next();
> > +        if (n) {
> I'm pretty sure prev() and next() can never be null here, since Contour uses a sentinel value.

The guards are there to allow the Segment to be subdivided before it's in the Contour's chain, in case we ever need that to work.

> Can this just call m_contour->add(right) ?

No. The key here is that the segment subdivides itself, adding the new second half immediately after itself in the segment chain.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:347
> > +            // m_first->prev() is the sentinel.
> > +            Segment* sentinel = m_first->prev();
> > +            Segment* last = sentinel->prev();
> Why not use m_sentinel?

Good point. ASSERT added, and code changed to use m_sentinel.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:388
> > +    Segment* end() const { return m_first->prev(); }
> m_first->prev() should always == sentinel, right?  Adding an ASSERT() and returning &m_sentinel seems a bit better.

Good point. Changed.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:393
> > +    const FloatRect& boundingBox() const
> This doesn't need to be const (and thus m_boundingBox(Dirty)? don't need to be mutable).

Fair point. Changed.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:516
> > +    for (Vector<Contour*>::iterator iter = m_contours.begin();
> > +         iter != m_contours.end();
> > +         iter++) {
> nit: could be a one-liner

Changed.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:548
> > +                                cache.addVertex(vert->xyCoordinates().x(),
> > +                                                vert->xyCoordinates().y(),
> > +                                                vert->klmCoordinates().x(),
> > +                                                vert->klmCoordinates().y(),
> > +                                                vert->klmCoordinates().z());
> Maybe LoopBlinnPathCache::addVertex should just take a LoopBlinnLocalTriangulator::Vertex*

For the case of handling stroked shapes, we will want the flexibility of not using the LoopBlinnLocalTriangulator::Vertex data structure.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:670
> > +Vector<Segment*> LoopBlinnPathProcessor::allSegmentsOverlappingY(Contour* queryContour, float x, float y)
> should this be behind #ifndef NDEBUG?

Yes. Fixed.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:675
> > +    for (Vector<Contour*>::iterator iter = m_contours.begin();
> > +         iter != m_contours.end();
> > +         iter++) {
> nit: one line

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:693
> > +inline String valueToString(const float& value)
> nit: I think you want static here instead of inline

These printing helpers changed structure after Nico's clang cleanups.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:698
> > +inline String valueToString(void* const& value)
> s/inline/static/

Same here.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:720
> > +    for (Vector<Contour*>::iterator iter = m_contours.begin();
> > +         iter != m_contours.end();
> > +         iter++) {
> nit: one line

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:739
> > +    for (Vector<Contour*>::iterator iter = m_contours.begin();
> > +         iter != m_contours.end();
> > +         iter++) {
> nit: one line

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:755
> > +        for (Segment* seg = cur->begin();
> > +             ambiguous && seg != cur->end();
> > +             seg = seg->next()) {
> nit: one line

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1144
> > +    GLdouble* outVertex = static_cast<GLdouble*>(malloc(3 * sizeof(GLdouble)));
> I think you should use fastMalloc() here.  It's #defined to system malloc in chromium (which is tcmalloc on windows/linux) but can also be #defined to debug allocators in some configs, which is handy.

Agreed. Fixed.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1154
> > +    // No-op just to prevent triangle strips and fans from being passed to us.
> I had to do some googling to figure out what this meant.  Guessing this is because of this text from http://glprogramming.com/red/chapter11.html:
> "Since edge flags make no sense in a triangle fan or triangle strip, if there is a callback associated with GLU_TESS_EDGE_FLAG that enables edge flags, the GLU_TESS_BEGIN callback is called only with GL_TRIANGLES. The GLU_TESS_EDGE_FLAG callback works exactly analogously to the OpenGL glEdgeFlag*() call."?
> 
> Could you add a reference to some canonical source of info for this?

Added a comment referencing that chapter in the OpenGL Programming Guide.

> Don't name the GLboolean flag if it is unused, this will avoid unusued variable warnings.

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1170
> > +    for (Vector<Contour*>::iterator iter = m_contours.begin();
> > +         iter != m_contours.end();
> > +         iter++) {
> nit: one line

Done.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1220
> > +        free(state.allocatedPointers[i]);
> fastFree() here

Changed.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.h:66
> > +    LoopBlinnPathProcessor();
> > +    explicit LoopBlinnPathProcessor(PassRefPtr<PODArena> arena);
> Should this class just take a Path in the constructor?  It looks like it's tied to the path object itself and not used for multiple paths (at least currently).

We'll want the flexibility of reusing the path processor. It isn't tied to the path; it builds up and throws away data structures while it processes each path.

> nit: don't name this parameter (same with path, cache, contour, seg, queryContour below)

All removed.

> > WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.h:104
> > +    // For debugging the orientation computation. Returns all of the
> > +    // segments overlapping the given Y coordinate.
> > +    Vector<LoopBlinnPathProcessorImplementation::Segment*> allSegmentsOverlappingY(LoopBlinnPathProcessorImplementation::Contour* queryContour, float x, float y);
> should this move behind the #ifndef NDEBUG guard?

Yes. Moved.

[Kenneth Russell]

Created attachment 81734 [details]
Patch

[Brian Salomon]

test comment by request from KBR

[Brian Salomon]

I did an unofficial review of the functions James didn't get to. Some minor points but nothing that should block submission. LGTM.

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

> Source/WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:980
> +            if (seg->kind() == Segment::Cubic) {

test is redundant with first loop's filtering, make assert?

> Source/WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1017
> +                tree.add(event.interval());

Add after we have the query result?

> Source/WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1029
> +                            if (trianglesOverlap(event.interval().data()->triangle,

Depending on whether you're gpu or cpu bound, could consider skipping the exact test

> Source/WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1095
> +            if (seg->kind() == Segment::Cubic) {

again, redundant with first loop

[Brian Salomon]

(In reply to comment #8)
> I did an unofficial review of the functions James didn't get to. Some minor points but nothing that should block submission. LGTM.
> 
> View in context: https://bugs.webkit.org/attachment.cgi?id=81734&action=review
> 
> > Source/WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:980
> > +            if (seg->kind() == Segment::Cubic) {
> 
> test is redundant with first loop's filtering, make assert?
> 
> > Source/WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1017
> > +                tree.add(event.interval());
> 
> Add after we have the query result?
> 
> > Source/WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1029
> > +                            if (trianglesOverlap(event.interval().data()->triangle,
> 
> Depending on whether you're gpu or cpu bound, could consider skipping the exact test
> 
> > Source/WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1095
> > +            if (seg->kind() == Segment::Cubic) {
> 
> again, redundant with first loop

Two more comments I forgot to add:
Can't the ray-cast be used to do the winding rule since you have counted the number of intersections?

> Source/WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1116
> +        curSegments = nextSegments;

It would nice if we could do a swap to avoid memcpys here

[Kenneth Russell]

Created attachment 82037 [details]
Patch

[Kenneth Russell]

(In reply to comment #8)
> I did an unofficial review of the functions James didn't get to. Some minor points but nothing that should block submission. LGTM.
> 
> View in context: https://bugs.webkit.org/attachment.cgi?id=81734&action=review
> 
> > Source/WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:980
> > +            if (seg->kind() == Segment::Cubic) {
> 
> test is redundant with first loop's filtering, make assert?

Done.

> > Source/WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1017
> > +                tree.add(event.interval());
> 
> Add after we have the query result?

Done.

> > Source/WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1029
> > +                            if (trianglesOverlap(event.interval().data()->triangle,
> 
> Depending on whether you're gpu or cpu bound, could consider skipping the exact test

Agreed. I'll leave this precise for the moment, and once we're running more complex content through the algorithm we can benchmark it. My prior experience was that once the algorithmic complexity of the overlap test was reduced (using the plane-sweep algorithm), the cost of the individual triangles' overlap tests was negligible.

> > Source/WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1095
> > +            if (seg->kind() == Segment::Cubic) {
> 
> again, redundant with first loop

Changed to an ASSERT.

[Kenneth Russell]

(In reply to comment #9)
> Two more comments I forgot to add:
> Can't the ray-cast be used to do the winding rule since you have counted the number of intersections?

It is. The only "knob" on the Loop/Blinn shader is whether it fills the left or right side of the curve. This has to be set based on a combination of (1) the number of intersections of the surrounding contours, and (2) the clockwise / counterclockwise orientation of the contour.

> > Source/WebCore/platform/graphics/gpu/LoopBlinnPathProcessor.cpp:1116
> > +        curSegments = nextSegments;
> 
> It would nice if we could do a swap to avoid memcpys here

Good point. Changed both instances of this in the code to use Vector::swap().

[James Robinson]

Comment on attachment 82037 [details]
Patch

Looks good to me!

[Kenneth Russell]

Committed r78264: <http://trac.webkit.org/changeset/78264>

[Mike Reed]

LGTM