missing data gap clipping should honour line width

[michi42]

Currently the gap clipping for missing data does not take into account the fact that a line width > 1 can lead to pixels being painted outside of the strict boundaries of a gap. This is particularly true if the data is significantly different between the start and end points of the gap.

For instance if on https://leeoniya.github.io/uPlot/demos/missing-data.html you modify

data[2][92] = 0.1
data[2][93] = 0.1
u.series[2].width=3
u.setData(data)

you get a part of the line connecting the gap, which should have been clipped away, visible:

[leeoniya]

well, it tries to account for it 😅, but it's imperfect, as you can tell. otherwise you'd see the full line width at the start and end descenders. i'll see if i can improve this, but as you've already pointed out, the accuracy of the gap boundaries would have to suffer, which may be a worse outcome. e.g. if you decided to make width 10px, then your gaps would just be very wrong. it's a tough trade-off to make given the single-path nature of the rendering code.

[michi42]

Sorry, probably I'm missing something stupid ... but even with single path, is there a reason why we can not use Path2D.moveTo() instead of clipping after the drawing for lines? This would have the advantage that it would also work correctly for mode=2 in all cases. For fills probably you would still need to clip though.

I'm thinking of something along these lines (of course proper handling for vertical X axes direction to be added):

				let inGap = false;
				for (let i = dir == 1 ? idx0 : idx1; i >= idx0 && i <= idx1; i += dir) {
					let yVal = dataY[i];

					if (yVal === null)
						inGap = true;
					else if (yVal != null) {
						inGap ? stroke.moveTo(pixelForX(dataX[i]), pixelForY(yVal)) : lineTo(stroke, pixelForX(dataX[i]), pixelForY(yVal));
						inGap = false;
					}
				}

[leeoniya]

is there a reason why we can not use Path2D.moveTo() instead of clipping after the drawing for lines?

unfortunately, we cannot use moveTo() because that causes fill() to break. that's why i had to work around it by clipping a lineTo-only path :(

https://jsfiddle.net/3srjqak7/

[michi42]

Thanks for the explanation! Yes, fill does not work with moveTo() but as I understand the code it generates two paths, one for stroke and one for fill (currently initialized based on a copy of the stroke path, then a few points are added to close the path). I think the clipping solution works well for filling, but as we see here not so great for strokes.
Would it be possible to create the fill and stroke paths in parallel but independently - fill with a closed path and gap clipping, stroke with moveTo instead of clipping? Performance hit?

[leeoniya]

Performance hit?

yeah, i think you'd have to simultaneously create two paths which would double the cost instead of basically just copying the the existing stroke path and closing it.

uPlot/src/paths/linear.js

Line 132 in 3a56bc6

let fill = _paths.fill = new Path2D(stroke);

[michi42]

Just gave it a quick try, indeed it gives a ~50-80% performance hit on path creation: https://jsfiddle.net/qf8oge67/
On the other hand if there is no fill it will be faster as we can ditch the clippling logic (iterating once more through the series to find gaps and create the clipping path, and then applying it to draw).

Of course from an user perspective it would be nice to use the fastest solution in every case (or to have the choice) - clipping for series with fill, moveTo and no clipping for series without fill, ...

[leeoniya]

ditch the clippling logic (iterating once more through the series to find gaps and create the clipping path, and then applying it to draw).

this part is surprisingly fast. much faster than doubling the lineTo() commands that already account for the majority of the profile. i'm not super convinced this is worthwhile, tbh.

[michi42]

Well, imho the advantage would be two-fold for series with no fill - the moveTo() solution will be slightly faster (only one path to fill and no clipping logic), and more robust (no graphical glitches for thick lines, no issues in mode=2 when x coordinates are not strictly ascending). Of course, at the price of added extra logic to distinguish this case.

For series with fill, one could either fall back to the current (fast) solution with clipping which will probably be good in most of the cases, or allow the user to choose ...

[leeoniya]

i see where you're coming from, but...

1. in the 6 year history of uPlot, this has only been noticed 2 or 3 times, despite being the core rendering logic in Grafana for 5 years of that time, in addition to many other OSS and closed source monitoring tools.
2. this would need to be done also for stepped and spline renderers
3. i don't think the proposed solution is simple at all, given that...
   a. since the linear builder does decimation as part of the rendering loop, integrating gap detection as well is quite complex. it's actually something i decoupled into two passes several years ago because it was so complex, and this refactor resulted in a performance boost due to the conditional branching simplification in the hot loop.
   b. since path filling is a necessary part of rendering bands, that entire thing needs to be re-tested to also accommodate multi-path behavior, etc.
4. having each renderer with two different sets of logic that diverge into additional different sets of logic is not something i want to have.
5. i don't want users to have to understand and choose between these different internal rendering strategies

one way i can imagine improving the current situation is to somehow insert an additional lineTo() that extends into the null gap by the line width, and at the same slope, so that when clipped the connection is fully within clip region. but i don't think this can be done without first undoing #684 to pull the gap detection logic into the draw/decimation loop again.

[leeoniya]

actually, looking at the gap clipping code, i don't see anything that accounts horizontally for stroke width, only some vertical accommodation for top and bottom of plot.

clipGaps is a public util API, so i think i would need to add the stroke width to the end of it. gonna look...

uPlot/src/paths/utils.js

Lines 178 to 181 in 3a56bc6

	// hack to ensure we expand the clip enough to avoid cutting off strokes at edges
	let maxStrokeWidth = 10;
	w > 0 && rect(clip, prevGapEnd, plotTop - maxStrokeWidth / 2, w, plotTop + plotHgt + maxStrokeWidth);

EDIT: i was probably remembering the code in stepped path builder that solves the same problem:

uPlot/src/paths/stepped.js

Lines 95 to 98 in 3a56bc6

	// expand/contract clips for ascenders/descenders
	let halfStroke = (series.width * pxRatio) / 2;
	let startsOffset = (ascDesc || align == 1) ? halfStroke : -halfStroke;
	let endsOffset = (ascDesc || align == -1) ? -halfStroke : halfStroke;

i should look into making a unified strategy here and pull this stepped-only code into clipGaps() and pass in the series line width.

[leeoniya]

did a quick test on the this clipGaps-stroke-width branch. (only does the leading edge adjustment). can't say i like it very much.

[michi42]

Thanks a lot for looking into this!

I also played a bit with a few options, but I couldn't get the clipping approach to work well reliably in certain edge cases ... as you say, either we clip too much or too little, and mode=2 is yet another story.

I tried exploring a bit the clipping-less approach for cases where it is not needed (no fill) ... adds a few lines but does not look super complex to me: michi42@903a3e0 (of course, would have to be done for other renderers as well)

Some more examples:
My patched version: https://michi.web.cern.ch/tmp/uPlot/demos/missing-data-test.html
Original version: https://michi.web.cern.ch/tmp/uPlot/demos/missing-data-test-orig.html

Of course, these are all made-up examples to specifically probe the edge cases... of course one can question if these are worth the extra logic (although the mode=2 case looks quite bad ...)

[leeoniya]

cool, thanks for poking around!

i dont fancy having this work just for stroke-only paths, so i applied the Feynman Algorithm to the problem 😅

it turns out we can actually get this done without incurring the cost of 2x the lineTo() commands for stroke + fill paths, and retain a lot of the benefits of creating the stroke path from the fill path.

https://jsfiddle.net/45kn0rmL/1/

the idea is to create an intermediate path to use as a scratch pad, and then use .addPath() method to copy all the accumulated lineTo() commands for any segment without gaps. this way for paths without gaps we only have the overhead of creating a single empty Path2D object per redraw call. if you have a lot of gaps, well then you'll have an additional Path2D for each segment.

let can = document.getElementById("canvas");
let ctx = can.getContext("2d");

let f = new Path2D();
let s = new Path2D();

// wip path, first used for stroke, then at gaps added to s, then and amended for fill and added to f
let t = new Path2D();

// first seg
t.moveTo(0, 200);
t.lineTo(50, 20);
t.lineTo(100, 50);

// gap detected here

s.addPath(t);

// down to baseline
t.lineTo(100, 200);
t.lineTo(0, 200);

f.addPath(t);

// next segment

t = new Path2D();

t.moveTo(150, 50);
t.lineTo(200, 100);

s.addPath(t);

// down to baseline
t.lineTo(200, 200);
t.lineTo(150, 200);

f.addPath(t);

// draw

ctx.fillStyle = '#f003';
ctx.fill(f);

ctx.strokeStyle = '#f00';
ctx.stroke(s);

i think this approach might be worth trying, but unfortunately would have to undo #684 and once again interlace the gap-detection logic into current and future pathbuilders. e.g. i'm not sure how the spline pathbuilder would be adapted because it uses a single curve with control points computed across gaps; how does this work if the curve now has to be split into multiple segments?

maybe instead of undoing #684, we can run the gap-finding loop up-front (instead of at the end) and just add a simple check inside the path-build/decimation loop whether we're in a gap region that needs to be path-split. not sure. i really want to avoid bringing back gap detection logic into the decimation loop.

for the spline thing, it might be okay to allow either approach to be used so we dont need to adjust every pathbuilder for this.

and mode=2 is yet another story.

i dont expect this pathbuilder to work for mode 2 where you're just connecting arbitrarily-ordered data points. it's not even clear how "fill" would work in those scenarios. for a mode 2 linear builder you would just do raw lineTo() and moveTo() calls without involving any of the decimation logic that exists in the current linear builder, which comes with ordering assumptions.

[leeoniya]

we only have the overhead of creating a single empty Path2D object per redraw call

i should actually check that this is true. if addPath() actually copies the path then there would be additional (maybe significant) memory cost to this. if we run the gap detection first we could probably avoid this for cases without gaps.

[leeoniya]

additionally, this approach will likely not work for bands, which will need to maintain the current strategy. that's probably an okay compromise.