Scatter Plot won't render a large number of points

geoffgscott commented 3 months ago

I am playing around with large scatter datasets (single series). I noticed over about 180 000 points the plot just stops rendering.

Using scatter.html as a base I created the below minimum example. With a single plot series (plus the empty series[0]) the plot stops rendering at 182 000 points.

The actual number of points does not seem to be an issue. At 180 000 points I am able to see the plot and it on my system the renders in 108ms. I am also able to add a second series also with 180 000 points so the limitation seems to be on a single series with a large number of points. I don't see any debugging output.

<!doctype html>
<html>

<head>
    <meta charset="utf-8">
    <title>Scatter &amp; Bubble</title>
    <meta name="viewport" content="width=device-width, initial-scale=1">

    <link rel="stylesheet" href="../dist/uPlot.min.css">
</head>

<body>
    <script src="./lib/quadtree.js"></script>

    <script type="module">
        import uPlot from "../dist/uPlot.esm.js";

        function randInt(min, max) {
            return Math.floor(Math.random() * (max - min + 1)) + min;
        }

        function filledArr(len, val) {
            let arr = Array(len);

            if (typeof val == "function") {
                for (let i = 0; i < len; ++i)
                    arr[i] = val(i);
            }
            else {
                for (let i = 0; i < len; ++i)
                    arr[i] = val;
            }

            return arr;
        }

        let points = 182000;
        let series = 2;

        console.time("prep");

        const setOne = Array(points)
            .fill(0)
            .map((_, i) => i)

        const setTwo = setOne.map((i) => 1.5 * i + 200)

        let data = filledArr(series, v => [
            filledArr(points, i => randInt(0, 500)),
            filledArr(points, i => randInt(0, 500)),
        ]);

        data[0] = null;

        console.timeEnd("prep");

        console.log(data);

        const drawPoints = (u, seriesIdx, idx0, idx1) => {
            const size = 2 * devicePixelRatio;

            uPlot.orient(u, seriesIdx, (series, dataX, dataY, scaleX, scaleY, valToPosX, valToPosY, xOff, yOff, xDim, yDim, moveTo, lineTo, rect, arc) => {
                let d = u.data[seriesIdx];

                u.ctx.fillStyle = series.stroke();

                let deg360 = 2 * Math.PI;

                console.time("points");

                //  let cir = new Path2D();
                //  cir.moveTo(0, 0);
                //  arc(cir, 0, 0, 3, 0, deg360);

                // Create transformation matrix that moves 200 points to the right
                //  let m = document.createElementNS('http://www.w3.org/2000/svg', 'svg').createSVGMatrix();
                //  m.a = 1;   m.b = 0;
                //  m.c = 0;   m.d = 1;
                //  m.e = 200; m.f = 0;

                let p = new Path2D();

                for (let i = 0; i < d[0].length; i++) {
                    let xVal = d[0][i];
                    let yVal = d[1][i];

                    if (xVal >= scaleX.min && xVal <= scaleX.max && yVal >= scaleY.min && yVal <= scaleY.max) {
                        let cx = valToPosX(xVal, scaleX, xDim, xOff);
                        let cy = valToPosY(yVal, scaleY, yDim, yOff);

                        p.moveTo(cx + size / 2, cy);
                        //  arc(p, cx, cy, 3, 0, deg360);
                        arc(p, cx, cy, size / 2, 0, deg360);

                        //  m.e = cx;
                        //  m.f = cy;
                        //  p.addPath(cir, m);

                        //  qt.add({x: cx - 1.5, y: cy - 1.5, w: 3, h: 3, sidx: seriesIdx, didx: i});
                    }
                }

                console.timeEnd("points");

                u.ctx.fill(p);
            });

            return null;
        };

        function guardedRange(u, min, max) {
            if (max == min) {
                if (min == null) {
                    min = 0;
                    max = 100;
                }
                else {
                    let delta = Math.abs(max) || 100;
                    max += delta;
                    min -= delta;
                }
            }

            return [min, max];
        }

        const opts = {
            title: "Scatter Plot",
            mode: 2,
            width: 2000,
            height: 600,
            legend: {
                live: false,
            },
            hooks: {
                drawClear: [
                    u => {
                        //  qt = qt || new Quadtree(0, 0, u.bbox.width, u.bbox.height);

                        //  qt.clear();

                        // force-clear the path cache to cause drawBars() to rebuild new quadtree
                        u.series.forEach((s, i) => {
                            if (i > 0)
                                s._paths = null;
                        });
                    },
                ],
            },
            scales: {
                x: {
                    time: false,
                    //  auto: false,
                    //  range: [0, 500],
                    // remove any scale padding, use raw data limits
                    range: guardedRange,
                },
                y: {
                    //  auto: false,
                    //  range: [0, 500],
                    // remove any scale padding, use raw data limits
                    range: guardedRange,
                },
            },
            series: [
                {},
                {
                    stroke: "red",
                    fill: "rgba(255,0,0,0.1)",
                    paths: drawPoints,
                },
            ],
        };

        let u = new uPlot(opts, data, document.body);

    </script>
</body>

</html>

leeoniya commented 3 months ago

does this happen in all browsers? all OSs? all machines? might also be limit of specific gpu or driver?

there's nothing in uPlot that restricts data size, so any issues where some arbitrary number fails to draw will probably be env/hardware dependent.

geoffgscott commented 3 months ago

Tested a few different things:

Macbook Pro 16:

Works in Safari
Works in Chrome (121)

Dell Precision 5760 - Arch Linux:

Works in Firefox
Does not work in Chrome (121)

Dell Precision 5760 - Windows:

Works in Firefox
Does not work in Chrome (120 or 121)
Does not work in Edge (120 or 121; unsurprising as it's still Chromium)
Works in Chrome with hardware acceleration disabled

To confirm the behavior does seem to be related to the number of points in a single series (which makes no sense to me). Adding multiple additional series in different colors on the same plots works as long as the single series is below 180 000. So the total number of Canvas elements can very easily exceed the 180 000 limit.

geoffgscott commented 3 months ago

Alright a little more info:

Seems to be related to some combination of Chrome, hardware acceleration, and some intel hardware?

This thread looks similiar although I think two issues are getting conflated into one there.

Forcing the canvas into software mode does fix the issue (with obvious side effects). const ctx = (self.ctx = can.getContext("2d", { willReadFrequently: true }));

leeoniya commented 3 months ago

interesting :+1:

leeoniya commented 3 months ago

it might be some limit with Path2D()

you can draw directly to u.ctx and do your own ctx.fill() and ctx.stroke() calls, and just return null from the path builder. you don't benefit from path caching this way, but that might be a better issue to have than some arbitrary path limit.

leeoniya commented 3 months ago

btw, usually seeing all raw data is unnecessary. you can sample 10-20% and still get a full understanding of the distribution. there's not much that 180k points will tell you that 50k points won't.

you can also create a heatmap from the full dataset. a heatmap will always have some fixed and reasonable limit to the number of items in the grid, and will be much faster, since you can also skip alpha opacity, and avoid antialiasing by drawing squares instead of circles. then maybe use a scatter plot as a second level drill-down when clicking on subset of heatmap cells.

geoffgscott commented 2 months ago

It took a while before I got back to this but confirmed it is a problem with Path2D. Agree 180k points is too many but I plot user generated data so I have minimal control over what comes in without opaquely decimating data.

For anyone else running into this problem:

const drawPoints: Series.PathBuilder = (u, seriesIdx) => {
    const size = 2 * devicePixelRatio

    uPlot.orient(
        u,
        seriesIdx,
        (
            series,
            dataX,
            dataY,
            scaleX,
            scaleY,
            valToPosX,
            valToPosY,
            xOff,
            yOff,
            xDim,
            yDim,
            moveTo,
            lineTo,
            rect,
            arc,
        ) => {
            const x = u.data[seriesIdx][0]
            const y = u.data[seriesIdx][1]

            u.ctx.fillStyle = series?.stroke?.()

            const deg360 = 2 * Math.PI

            console.time('points')

            const paths = [new Path2D()]
            let pathIdx = 0

            const r = size / 2

            if (!x || !Array.isArray(x) || !Array.isArray(y)) return

            x.forEach((x_pos, idx) => {
                if (idx % 5 !== 0) return

                // There are chrome issues rendering past 180000 points. Create a new path every 150000 points to be safe
                if (idx && idx % 150000 === 0) {
                    paths.push(new Path2D())
                    pathIdx += 1
                }

                const y_pos = y[idx]

                if (
                    x_pos >= scaleX.min &&
                    x_pos <= scaleX.max &&
                    y_pos >= scaleY.min &&
                    y_pos <= scaleY.max
                ) {
                    const cx = valToPosX(x_pos, scaleX, xDim, xOff)
                    const cy = valToPosY(y_pos, scaleY, yDim, yOff)

                    paths[pathIdx].moveTo(cx + r, cy)
                    arc(paths[pathIdx], cx, cy, r, 0, deg360)
                }
            })

            console.timeEnd('points')
            paths.forEach((p) => u.ctx.fill(p))
        },
    )

    return null
}

leeoniya / uPlot

Scatter Plot won't render a large number of points #919