Efficient way to draw circles

Question

I'm drawing circles in the following way:

for each pixel px
{
    if (isInside(px)) px.color =  white
    else px.color = black
}

bool isInside(pixel p)
{
    for each circle cir
    {
        if (PixelInsideCircle(p, cir)) return true
    }
    return false
}
    
bool PixelInsideCircle(pixel p, circle cir)
{
    float x = p.pos.x - cir.pos.x, y = p.pos.y - cir.pos.y;
    return x*x + y*y <= cir.radius*cir.radius
}

Here's the result:

There are around 50 circles. Any way to optimize it? I'm using unity3d. I'm filling the RenderTexture using compute shader and directly drew (Graphics.Blit) to the camera. I'm drawing only circles and I want to increase the circles from 50 to 1000. I've tried to use aabb and kd tree but could not figure out how to correctly implement it, using tree only worsen the performance. Thought to use intersection test for every column but not sure if it's a good idea. I'm making this for android and ios. Any help ?

@MickyD I'm drawing similar to this with only circles .https://math.stackexchange.com/questions/4459729/blend-multiple-shapes — Hello Humans, Jul 12 '22 at 08:06
@MickyD I'm able to draw what I want, the problem is that I'm checking every pixels which is waste of resource.So I want a way to reduce the number of pixels to check. — Hello Humans, Jul 12 '22 at 08:19
_"efficient"_ might be _subject to opinion_ and if so is sadly off-topic for SO. [ask]. Consider re-phrasing your question to be [constructive subjective](https://stackoverflow.com/help/dont-ask) — , Jul 12 '22 at 08:21
_"the problem is that I'm checking every pixels which is waste of resource"_ - that's not necessarily true. After-all [GPGPU-based _ray tracing_ does that and more no problem!](http://blog.three-eyed-games.com/2018/05/03/gpu-ray-tracing-in-unity-part-1/). What might be inefficient in conventional graphics might not be in GPGPU. — , Jul 12 '22 at 08:24
@MickyD The code above is Naive. I could reduce the number of pixels to check by half by using intersection test but I wanted to know if there is any better approach than intersection before implementing it. — Hello Humans, Jul 12 '22 at 08:37
@MickyD Since lighting is not concerned, it isn't necessary to check every pixel. — Hello Humans, Jul 12 '22 at 08:38
@Spektre My initial test was 12 fps. After using quads it was 35 fps! Almost 3x improvement. My setup: Intel i3 7020U 2.3GHz , Intel HD graphics 620 (pretty sick GPU) and resolution is 1366x768. End result after adding noise to circles: https://i.imgur.com/OkJEcqH.png — Hello Humans, Jul 13 '22 at 09:58
@HelloHumans nice therm `pretty sick GPU` :) I totally agree all the Intel GPUs are hardly usable as they lack good drivers and its usually getting worse with newer HW ... had countless issues and headaches due to them ... — Spektre, Jul 13 '22 at 12:48
@HelloHumans I moved the comment into answer and added some more stuff check it out and let me know if it improves speed even more... — Spektre, Jul 14 '22 at 05:34

Spektre · Accepted Answer · 2022-07-14T05:47:46.537

I do not code in/with unity/C#/DirectX but if you insist on filling by pixels see

Is there a more efficient way of texturing a circle?

for some ideas on easing the math ...

I would not use compute shaders but render QUADS (AABB) for each circle instead using Vertex+Fragment shaders.

As next step I would try to use Geometry shader that emits triangle fan around your circle (so the ratio between filled and empty space is better) this also require just center and radius instead of AABB so you can use POINTS instead of QUADS see:

rendering cubics in GLSL

Its doing similar things (but its in GLSL). Also I noted you have:

return (p.pos.x - cir.pos.x)^2 + (p.pos.y - cir.pos.y)^2 - (cir.radius)^2 <= 0

try to change it to:

return (p.pos.x - cir.pos.x)^2 + (p.pos.y - cir.pos.y)^2 <= (cir.radius)^2

its one less operation. Also (cir.radius)^2 should be passed to Fragment from Vertex (or Geometry) so it does not need to be computed on per pixel basis

In unity (C#) `^` is XOR. I used mathematical symbol here. `pow(x , 2)` — Hello Humans, Jul 14 '22 at 05:41
@HelloHumans You should add that as comment in your question's code so its obvious ... for everyone that reads it however `x*x` is usually much faster than `pow(x,2)` — Spektre, Jul 14 '22 at 05:46

score 0 · Answer 2 · answered Jul 13 '22 at 20:43

Using compute shaders and checking distances is probably the faster way. In the worst case, for 1000 circles, it would execute "PixelInsideCircle" 1000 times and in the best case just once per pixel. When a pixel is found inside a circle it leaves the loop and return white.

This is faster than any other solution on CPU (quadtree) + GPU (compute shaders). Let your GPU run everything in a single loop per pixel.

Only the pixel number (width * height) * circles will affect the performance. You could go for a smaller texture (50~99%) and upscale on the Blit, its even better for mobile since screens are smaller.

Also other solutions using meshes, circle textures would be bad as mobile GPUs are memory bandwidth bound, passing more commands and data around is worse than calculating on the GPU itself.

You can try replacing your "PixelInsideCircle" with HLSL: distance() or length(), (they'll probaly have a internal Sqrt though), but since they are internal functions, maybe they are faster. Just test it.

Do you run this once like a map generator or its run every frame ?

using quads as suggested by @Spektre will reduce the total number of pixels to calculate. eg: let's say a circle can fit inside 40x40 quad, so instead of calculating for entire width * height of RenderTexture we can calculate only for 40x40 pixels. — Hello Humans, Jul 14 '22 at 04:02

Efficient way to draw circles

2 Answers2