Efficient way to draw circles-CodePudding

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 ?

CodePudding user response：

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

CodePudding user response：

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 ?