Fast method of drawing round points

[bforl]

I'm working on a custom WPF control that displays a scatter point chart, showing upwards of 200k points. This chart is interactive, meaning the user can pan, scroll, zoom etc and the rendering will update.

However, the performance when trying to render such a large number of points is pretty poor, and the interactive element is ... less interactive than I would like (as its so laggy)

I am currently using SKCanvas.DrawPoints, and the documentation specifically mentions that points are rendered "one at a time". I was wondering if there is some other method I could be using? perhaps something that uses some kind of geometry instancing? (i.e one draw call, multiple data)

Some information about my use case

• The list of points is static, but when panning/scrolling/zooming, their relative position on screen changes, so whilst the data is static, the position on screen is dynamic.
• the size of each point is the same
• colours are all the same
• needs to support opacity

Some things I have noticed :

• rendering as a square instead of a circle is MUCH faster (but would prefer round)
• IsAntialias makes little to no difference

One option would be to dynamically to switch from round to square depending on the number of points.

Here is some example code for what I am doing.

NOTE : The memory allocation of creating the points each time is not the bottleneck, it is the render call that takes all the time. But I have written it like this as it keeps the example code simple.

private void OnPaintSurface(object sender, SKPaintSurfaceEventArgs e)
{
    var canvas = e.Surface.Canvas;
    canvas.Clear(SKColors.White);

    using var paint = new SKPaint
    {
        Color = SKColors.Black.WithAlpha(50),
        IsAntialias = false,
        Style = SKPaintStyle.Fill,
        StrokeCap = SKStrokeCap.Round,
        StrokeWidth = 6,
    };

    var points = new List<SKPoint>();
    var r = new Random(0);

    for (int i = 0; i < 200_000; ++i)
    {
        points.Add(new SKPoint((float)(r.NextSingle() * ActualWidth), (float)(r.NextSingle() * ActualHeight)));
    }

    canvas.DrawPoints(SKPointMode.Points, points.ToArray(), paint);
}

[bforl]

Any suggestions? :)

[mattleibow]

I still think the issue is that you are drawing 200k points. If you have a view that is 400x400 and draw a single point in each pixel, you still can only draw 160k points before you start overlapping.

I also think that maybe "don't draw so many points" is ambiguous. I am meaning don't do 200k draw calls as that is a waste. Most likely you can give the illusion of 200k by merging nearby points. Especially since the size of each dot is 6px. This means you are most likely drawing multiple times over.

Do you have a sample of real data? I can have a quick play around and also do benchmarking.

How long does a single frame take to render with the CPU/raster and how long with the GPU/GL? If you use the profiling tools in VS, where is the main time?

[mattleibow]

Here is an example of a 800x800 canvas with 200k random points:

[mattleibow]

I wrote the simplest filter ever that just checks to see if any points are close together and I went from 500ms to 25ms with 200k points:

var filtered = new Dictionary<SKPoint, SKPoint>(points.Count);
foreach (var point in points)
{
    var key = new SKPoint((int)(point.X / 6), (int)(point.Y / 6));
    filtered[key] = point;
}

return filtered.Values.ToArray();

This was still slow because all the points are evenly distributed across the board, but with a real dataset, this may even be far less as most of the time they are located in chunks.

This does filter evenly and thus density is lost, but if we are to reduce the data set, we could instead have some sort of density-based filter where it keeps more points in dense areas and loses more in less areas - exaggerating the graph.

In many cases, the user can't really make out data if all 200k points are presented as it will just look like a blob. Using exaggeration will help with data presentation.

[mattleibow]

Testing with the SKGLElement view, I can draw things 10x faster. All 200k points at 50ms instead of 500ms and the filtered one at 7ms instead of 25ms.

So definitely use that.

[bforl]

As already mentioned, its a scatter plot with a large number of points. Opacity is used to see where build up of points occur for further filtering. So overlapping points is by design.

(This is the type of thing, although this is showing fewer points)

Yes - its a large number of points, but its a large data set :) (users can zoom in and out to explore the data)

I have since figured out a more efficient of way rendering using SIMD. I take the SKSurface and get a pointer to it's backbuffer, and then draw my own points using AVX instructions. It's about 4x quicker (10x quicker if I sort the points by their Y position).

So am I now rendering 256k points to a RGBA 3500x1400 back buffer in 5ms (vs 95ms with DrawAtlas/DrawPoints)

The main thing I have learnt though is that the bottleneck is not so much the rendering (although that definitely plays a part), but the memory usage. With such a large image buffer, there are a lot of cache misses.

All the above is with SKElement.

in regard to SKGLElement, I find it can certainly be quicker when you only have one, but if you have multiple (e.g a dashboard), the performance is goes right down, and CPU rendering becomes quicker.

[mattleibow]

I think I may be seeing some potential issues:

• the .ToArray() is far more expensive than it looks because each call is allocating a new array instance, consuming memory and then causing the GC to collect.
• there are GPU views that may result in a faster render time - in SkiaSharp 3.x there is a new SKGLElement that we just added
• there may be unnecessary points

For the first option, I know there is no alternative API and we need to add one that uses a span. However, even with the nice fast span, the backing/source collection also needs to be accessible via an array - this may help: https://learn.microsoft.com/dotnet/api/system.runtime.interopservices.collectionsmarshal.asspan

If you try the new GPU-backed view in 3.x, is it faster?

Besides all this, trying to draw 200k points is also sometimes less useful if the points are off the screen. It may be worth breaking the points up into regions. For example, if the total chart is holding points in a visible region of 500x300px, then it may be useful to break the points into boxes of 100x100px and just drawing those. This does not solve the case where all the points are visible, but it may help with panning.

You may also want to look at merging points at very zoomed out levels. Instead of drawing 7 points in a single pixel or even a 3x3px area, just draw one. This will involve processing the point data, but drawing less is always faster.

I know some of this does not help you now, but the GPU accelerated view may help. If the point collection is fixed, then it may be worth creating the array one time to pass to the points method, then it does not matter about array vs span vs anything, there is a single, long-lived array instance.

EDIT: I also just realized the .ToArray() may just be for example purposes - but also may not. So still valid.

[bforl]

Thanks

I did specifically mention the array allocations in the original question (I tested with a static array and it made no noticeable difference).

And yep, I recently tried SKGLElement, but sadly, made no noticeable difference.

I agree with all your other points about approaching the problem from another angle by simplifying the point collection, and that is something I will probably do, but it was more a question to see if there was anything lower level I could use. 200k might sound like a lot, .. but by todays hardware really isn't that much work (even if the points are polygons).

Im guessing that each point is tessellated on the CPU? as opposed to it being tessellated on the GPU?

And of course, I appreciate that I am probably expecting too much from this library, (trying to use it for something it wasn't intended for) which of course is fair enough :)

[mattleibow]

This may be a question for the skia-discuss group as there may be a totally different way to do something like this: https://groups.google.com/g/skia-discuss

[artemiusgreat]

If you don't need to support Web UI, you could use OpenGL library instead, e.g. this one
https://github.com/artemiusgreat/GLGraph