Add adaptive forward differencing option for bezier tessellation.

[wtholliday]

Caching paths is great, but sometimes your paths are changing often. In that case, you need the fastest tessellation algorithm possible.

In my app, Adaptive Forward Differencing (AFD) provides a 4x speedup over the existing De Casteljau subdivision algorithm. YMMV. Also, note that the existing algorithm does not handle certain (arguably degenerate) cases correctly, like collinear control points with the endpoints in the middle.

I've added a function to select between tessellation algorithms (nvgBezierTessellation), defaulted to the old algorithm, so this will not change the behavior of your existing code. Currently, AFD produces about twice the points (the flatness test could be improved), but GPUs are fast.

Add nvg__tesselateBezierAFD which implements the tessellation. Add nvgBezierTessellation to select tessellation algorithm.

[QUItCoding]

I tested this alternative tessellation patch by cherry-picking it on top of (https://github.com/QUItCoding/nanovg) fork and using that in QNanoPainter (https://github.com/QUItCoding/qnanopainter). Based on my usage & testing, AFD was slower on both Macbook Pro & Nexus 6. Here's screenshots on macbook:

So with this torture test, fps drops from 19 to 11 while vertices count increases about 3x. Of course this is just one usage and like @wtholliday said, YMMV.

[olliwang]

I also did a pressure test for my app on iPhone 6s+. It seems there is no difference in my case.

Original:

AFD:

[wtholliday]

@QUItCoding The AFD would benefit from a better flatness condition. How much time is your test spending on tessellation? (inside nvg__tesselateBezier or nvg__tesselateBezierAFD)

@olliwang How much time is your test spending on tessellation?

[mulle-kybernetik-tv]

I tried this with a SVG drawing of the GhostscriptTiger, were tesselation was and still is a massive bottleneck and the speedup was significant.

I actually also think the quality is better. But wouldn't vouch for that :)

[michealowen]

Caching paths is great, but sometimes your paths are changing often. In that case, you need the fastest tessellation algorithm possible.

In my app, Adaptive Forward Differencing (AFD) provides a 4x speedup over the existing De Casteljau subdivision algorithm. YMMV. Also, note that the existing algorithm does not handle certain (arguably degenerate) cases correctly, like collinear control points with the endpoints in the middle.

I've added a function to select between tessellation algorithms (nvgBezierTessellation), defaulted to the old algorithm, so this will not change the behavior of your existing code. Currently, AFD produces about twice the points (the flatness test could be improved), but GPUs are fast.

Add nvg__tesselateBezierAFD which implements the tessellation. Add nvgBezierTessellation to select tessellation algorithm.

Hi! I tried to read the paper you mentioned, but I cant exactly understand the algorithm. Besides, I analyze the time complexity of nvg__tesselateBezier and nvg__tesselateBezierAFD and I found if both algorithmThe time complexity of algorithm A is at most twice that of Bs generate the same number of vertices, the time complexity of nvg__tesselateBezier is at most twice that of nvg__tesselateBezierAFD. For nvg__tesselateBezier, its time compplexity is O(2^n) and generate 2^(n-1) vertices, so if nvg__tesselateBezierAFD also generates 2^(n-1) vertices, it will at least cost O(2^(n-1)).

I dont konw why you can got 4x sppedup by nvg__tesselateBezierAFD. And is there any other information about the algorithm besides the paper?

[wtholliday]

Hi! I tried to read the paper you mentioned, but I cant exactly understand the algorithm. Besides, I analyze the time complexity of nvg__tesselateBezier and nvg__tesselateBezierAFD and I found if both algorithmThe time complexity of algorithm A is at most twice that of Bs generate the same number of vertices, the time complexity of nvg__tesselateBezier is at most twice that of nvg__tesselateBezierAFD. For nvg__tesselateBezier, its time compplexity is O(2^n) and generate 2^(n-1) vertices, so if nvg__tesselateBezierAFD also generates 2^(n-1) vertices, it will at least cost O(2^(n-1)).

I dont konw why you can got 4x sppedup by nvg__tesselateBezierAFD. And is there any other information about the algorithm besides the paper?

Both algorithms are linear in number of output vertices. The difference comes from avoiding recursion, and is a constant factor, not an asymptotic difference. But I never got the flatness test to be good enough to minimize the number of output vertices.

I've since moved on to using implicit methods to render things, avoiding any tessellation. See http://GitHub.com/Audulus/vger

[0xBYTESHIFT]

so, is this repo dead?