-
-
Notifications
You must be signed in to change notification settings - Fork 17
This page gathers R&D ideas to improve both performance and quality:
last updated: 2016.12.20
Implement an efficient path clipping algorithm that should handle also affine transforms ie the clip rectangle may be rotated, sheared, translated … Moreover, clipping may have a major impact on dashed paths to ignore invisible dashes !
Handle dash phase efficiently with very huge segments (clip) and ignore too small dash increments
As Andréa Aimé pointed this problem out, the Stroker has several issues leading to some overheads: extra intermediate points are generated (collinear) and processed by the renderer stage: Caps:
- square caps: 3 extra segments are generated: 2 collinear points could be eliminated.
- round caps: tune the threshold detecting visually useless round caps Joins:
- mitter joins: 2 extra segments are generated: 2 collinear points could be eliminated.
- round joins: tune the threshold detecting visually useless round joins
For now, Marlin provides an optional polygon Simplifier that skips collinear points but this supplementary step is less efficient than directly avoiding the generation of useless points.
Marlin could provide a generic polyline simplifier to only render really visible details like the progressive Douglas-Pecker algorithm: http://geomalgorithms.com/a16-_decimate-1.html
Refine the subdivision thresholds (quadratic) or adaptive thresholds (cubic) depending on the desired quality hint (performance vs quality): see Renderer class
It takes into account the curvature (d2x/y) or the speed of the curve (dx/y) but the algorithm should use positional error instead (in subpixels)
Almost fixed in v0.7.5: new tuning parameters and refined d2x/y norm
From Marlin v0.7, DDA (32.32) is in use at the renderer stage but subpixel coordinates are still 1/8th pixel (8x8 grid).
It is tunable but using an higher precision subpixel grid leads to an important performance penalty (256x256) !
Let's use another approach: compute the exact polygon area covering a pixel row ie the scanline will be 1 pixel height.
Handle properly (and test) NaN and coordinate overflows to avoid any rendering artefacts: done in v0.7.3
Use double instead of float in the early stages of the pipeline (Normalizer, Dasher, Stroker, Transformer) to reduce the round-off errors and get better subpixel coordinates notably with affine transforms (rotation ...) It may be a bit slower but not that much on 64bits platforms.
Implemented as the Double pipeline (use the DMarlinRenderingEngine instead) ~ same performance on intel cpu
Handle properly the gamma correction (multiply alpha coverage by inverse gamma) to take into account the non-linearity of CRT / LCD displays: done in marlin 0.4.5
Moreover, the stroke width must compensate the gamma correction to avoid having “thin” shapes.
It should be implement in the mask fill algorithm as it is experimentally implemented in MarlinGraphics BlendComposite.
See https://bel.fi/alankila/lcd/index.html See http://www.freetype.org/#news (Freetype 2.6.2)
Several solutions have been implemented in GPU to compute more accurately the pixel coverage of a primitive (line):
- Analytical line coverage: Using the signed area coverage for a trapezoid, it is possible to compute the exact pixel or subpixel area covered by the polygon: see openjdk's MaskFill.c
See the algorithmic approach (Anti-Grain Geometry like): http://nothings.org/gamedev/rasterize/
- Edge distance function: See [2] for proper line rendering using 4 distance functions and filtering
As shown in [1], supersampled images should be filtered before rescaling to avoid artefacts (moire patterns or jaggies). Marlin only counts subpixels to compute the pixel coverage ie all subpixels (8x8) have the same weight (=1). To improve the visual quality, better resampling filters can be implemented (tent or gaussian filters).
TODO:
- precompute filter weights according to the subpixel grid (2x2 up to 16x16) but also their integration onto the subpixel grid for performance reasons to improve scaline processing (sp_x, sp_y)
- instead of counting covered subpixels during scanline processing, use filter weights per covered subpixels (use integer weights by scaling up by a scaling factor) before summation and store weighted coverage into alpha line (as usual). Warning: for each edge only 1 subpixel corresponds to the edge intersection; the pixel coverage corresponds to all subpixels between 2 edges: take care of correct filter integral between these subpixels: same several pixel(s)
- normalize pixel coverages once all scanlines have been processed per pixel line according to the filter scaling factor
- convert then the pixel coverage (int) to an alpha value (byte) [0..1] ie [0.255] using the maximal precision ie 1/256 uncertainty
STATUS: done in marlin 0.6.0 (branch use_Filter) but the filter support must be larger than +/- 0.5 pixel ie typically +/- 1 pixel for gaussian filters and +/- 2 pixels for cubic filters: it requires more complex coverage integration to keep few scan lines in memory before computing the alpha coverage (sum + normalize)
[1] Study of Supersampling Methods for Computer Graphics Hardware Antialiasing Goss, Michael E.; Wu, Kevin 12/05/2000 http://www.hpl.hp.com/techreports/1999/HPL-1999-121R1.html
[2] Prefiltered Antialiased Lines Using Half-Plane Distance Functions McNamara, Robert ; McCormack, Joel ; Jouppi, Norman P. 1998 http://www.hpl.hp.com/techreports/Compaq-DEC/WRL-98-2.html