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.
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.
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?
Comment on attachment 67158 [details] Patch Can you upload a new version of this patch that addresses James comments?
(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.
(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.
Created attachment 81734 [details] Patch
test comment by request from KBR
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
(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
Created attachment 82037 [details] Patch
(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.
(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().
Comment on attachment 82037 [details] Patch Looks good to me!
Committed r78264: <http://trac.webkit.org/changeset/78264>
LGTM