Rasterization performance

[tdewolff]

Improve rasterization performance. How does FreeType perform? Why is the vector one slow?

• vector: https://github.com/golang/image/tree/master/vector
• FreeType: https://github.com/golang/freetype
• exp: https://github.com/golang/exp/blob/master/shiny/iconvg/rasterizer.go
• rasterx: https://github.com/srwiley/rasterx for a combination of vector and FreeType

Make sure the new rasterizer supports both fill types: EvenOdd and NonZero (vector does not support EvenOdd).

EDIT: see the following links for some ideas.

• font-rs: https://medium.com/@raphlinus/inside-the-fastest-font-renderer-in-the-world-75ae5270c445, also see https://www.cryptologie.net/article/406/simd-instructions-in-go for implementing in Go
• Signed distance fields: https://github.com/Chlumsky/msdfgen

EDIT: actually, Nigel Tao has an implementation of font-rs in Go here: https://github.com/google/font-go. It says in https://github.com/golang/image/blob/master/vector/vector.go that font-go is proof of concept, but doesn't actually import vector...?

[chmike]

font-rs is using the algorithm described here http://nothings.org/gamedev/rasterize/. It is smart but support only non-zero winding (not even-odd). The vector package of Nigel Tao is using this algorithm with the optimization to use fixed point instead of floats when the image size is smaller than 500 pixel in width and height (if I understood correctly), and assembly with SIMD.

The method is fast for rasterizing but generates only a mask or gray map. Other operations like combining images are O(N²) since each pixel is processed. The method is thus good for rasterizing text which is dense and a small image size, not for general 2D graphics on big images.

The package font-go is a proof of concept of a font rasterizer using the font-rs algorithm. The rasterizer algorithm is implemented in the vector package. The x/image/font package is using the x/image/vector package.

The algorithm to flatten bézier curves in the vector package may be interesting to look at. I think it comes from FreeType. It looks simple and efficient. It may not be optimal in the number of line segments generated, but it is surely optimal to compute the number of steps of t when compared to the method described here.

[tdewolff]

This library currently uses the vector implementation of Nigel Tao, which is as far as I know the fastest rasterizer in pure Go. We should improve performance when using a gamma correcting color space, as it slows down the rasterizer a lot. Additionally, we could look at rasterization at the GPU level, but for that we need tesselation, some shader work for displaying Béziers or arcs (or otherwise we need to flatten those which is what vector does), setup an OpenGL environment, render the image to a texture and retrieve it. This may be faster only for very large images I suppose...

Also see flattening: create the fewest amount of linear segments for quad/cube Béziers and arcs.

[tdewolff]

Flattening has been implemented which is slightly better than Nigel Tao's version. Otherwise, improving rasterization performance is a high-priority but re-implementing a rasterizer is not.

[tdewolff]

This may have improved dramatically with the fix for #334. In the future we may need to implement our own rasterizer for RGBA and NRGBA (for PNGs) images, with gamma correction and subpixel rasterization for text.