How to optimize circle draw?

Question

I am wondering how could I optimize my circle draw method. I seek how to generate as quickly as possible the vertices, before sending them to opengl.

void DrawCircle(float x, float y, float radius, Color color, float thickness)
{
    int numOfPoints = 100;
    for (float i = 0; i < numOfPoints; ++i) {
        float pi2 = 6.28318530718;
        float angle = i / numOfPoints * pi2;

        FillRect(
        cos(angle) * radius + x,
        sin(angle) * radius + y, 
        thickness, 
        thickness, 
        color);
    }
}

FillRect function simply draws a quad, so DrawCircle function draws 100 quads which are moved by cos, sin and radius.

FillRect(float x, float y, float w, float h, Color color)

How could I draw circle different way?

https://msdn.microsoft.com/en-us/library/dd162510(v=vs.85).aspx ? — user202729, Jun 24 '18 at 14:22
Are you using windows? If so add the tag. I want me code to be multisystem (Do not how to say it different way), Optimize? Is it too slow now? Yes, it is. Simply when I draw 100 quads fps = ~3000/4000, now with one circle draw fps = ~1500 — IScream, Jun 24 '18 at 14:24
C++ has no built-in way to draw shapes. You must use a library. So what library are you using? — user202729, Jun 24 '18 at 14:26
@user202729 I am using opengl to draw quads. I did not add opengl tag, because my example do not include any of opengl calls. Is there any of different maths equation I could use to draw circle? Maybe pythagoras - I have seen somewhere circle rendered this way, but a long time ago. — IScream, Jun 24 '18 at 14:26
You can move float pi2 = 6.28318530718; outside of the for, you don't have to initialize it every step, only once, it is a constant value. Also float angle = i / numOfPoints * pi2; can be changed(numOfPoints * pi2 can be initialized outside of the for, you need to do it only once, and in the for you do float angle = i / result) But don't know how much it will optimize for you or what you mean by optimization — Raul Cuth, Jun 24 '18 at 14:29
`You can move float pi2 = 6.28318530718; outside of the for, you don't have to initialize it every step` I did it. I am not sure how, but fps slowed down. I will try the rest of your thoughts. — IScream, Jun 24 '18 at 14:30
The fastest way to do it is by using the library builtin, if there is any. Specify your library. — user202729, Jun 24 '18 at 14:31
`The fastest way to do it is by using the library builtin, if there is any. Specify your library` Do not know exactly what you mean. — IScream, Jun 24 '18 at 14:33
If you're using OpenGL... see [this](https://stackoverflow.com/questions/13501752/opengl-rendering-large-amounts-of-dynamic-2d-circles) or [this](https://stackoverflow.com/questions/14962614/performance-drawing-many-2d-circles-in-opengl). — user202729, Jun 24 '18 at 14:37
They do not present my problem. I already have class ready to render many sprites with one draw call. Just this draw circle method is too slow I guess. I do not know, maybe sin and cos slows down it. If I call 100 times `FillRect(0.0f, 0.0f, 100.0f, 100.0f, Color(255, 0, 0, 255))` which draws 100 times rectangle, fps = ~3000/4000. When I want to render the same amout of quads but with certain x and y, it slows down. — IScream, Jun 24 '18 at 14:45
Why do you insist on generating hundreds of rectangles for this? Better option #1: use a triangle fan. Better option #2: use a single square to define the circle and draw it with a fragment shader. — spectras, Jun 24 '18 at 14:52
`use a single square to define the circle and draw it with a fragment shader.` - that is the thought. You meant to draw a quad and shade out the useless pixels? — IScream, Jun 24 '18 at 14:59
`How accurate does it need to be?` I do not really know. The most I guess — IScream, Jun 24 '18 at 15:29

score 3 · Answer 1 · answered Jun 24 '18 at 19:28

Since you explicitly asked for ways to optimize your method generating the vertices coordinates, I'll propose a solution for that. However looking at a few benchmarks measurements (see demo link below), I'm not convinced this is really the cause of any performance issue...

You can compute vertices on a circle centered at (0,0) recursively using rotation matrices:

// Init
X(0) = radius;
Y(0) = 0;
// Loop body
X(n+1) = cos(a) * X(n) - sin(a) * Y(n);
Y(n+1) = sin(a) * X(n) + cos(a) * Y(n);

This replaces cos and sin computations inside the loop with only a few floats multiplications, additions & substractions, which are usually faster.

void DrawCircle(float x, float y, float radius, Color color, float thickness) {
    int numOfPoints = 100;
    float pi2 = 6.28318530718;
    float fSize = numOfPoints;
    float alpha = 1 / fSize * pi2;
    // matrix coefficients
    const float cosA = cos(alpha);
    const float sinA = sin(alpha);
    // initial values
    float curX = radius;
    float curY = 0;
    for (size_t i = 0; i < numOfPoints; ++i) {
        FillRect(curX + x, curY + y, thickness, thickness, color);
        // recurrence formula
        float ncurX = cosA * curX - sinA * curY;
        curY =        sinA * curX + cosA * curY;
        curX = ncurX;
    }
}

Live demo & simplistic comparison benchmark

The drawback of using exclusively recursion is that you accumulate tiny computations errors over each iteration. As the demo shows, the error is insignificant for 100 iterations.

Spektre · Answer 2 · 2018-06-25T07:50:36.303

In your comments you mention you are using OpenGL for rendering (assuming old API) so using individual GL_QUADS is your problem. As you are doing OpenGL calls for each separate "pixel" of your circle. That is usually much slower then the rendering itself. What options are there to solve this?

VBO

this is your best bet just create VBO holding the cos(a),sin(a) unit circle points and render as single glDrawArray call (applying transform matrices to transform unit circle to desired position and radius). That should be almost as fast as single GL_QUADS call... (unless you got too many points per circle) but you will lose the thickness (unless combining 2 circles and stencil...). Here:
- complete GL+GLSL+VAO/VBO C++ example
you can find how VAO/VBO are used in OpenGL. Also see this on how to make holes (for the thickness):
- I have an OpenGL Tessellated Sphere and I want to cut a cylindrical hole in it

GL_LINE_LOOP

you can use thick lines instead of rectangles that way you decrease glVertex calls from 4 to 1 per "pixel". It would look something like this:

void DrawCircle(float x, float y, float radius, Color color, float thickness)
    {
    const int numOfPoints = 100;
    const float pi2=6.28318530718; // = 2.0*M_PI
    const float da=pi2/numOfPoints;
    float a;
    glColor3f(color.r,color.g,color.b);
    glLineWidth(thickness/2.0);
    glBegin(GL_LINE_LOOP);
    for (a=0;a<pi2;a+=da) glVertex2f(cos(a)*radius + x, sin(a) * radius + y); 
    glEnd();
    glLineWidth(1.0);
    }

of coarse as I do not know how the color is organized the color settings might change. Also glLineWidth is not guaranteed to work for arbitrary thickness ...

If you want still to use GL_QUADS then at least turn it to GL_QUAD_STRIP which will need half of the glVertex calls...

void DrawCircle(float x, float y, float radius, Color color, float thickness)
    {
    const int numOfPoints = 100;
    const float pi2=6.28318530718; // = 2.0*M_PI
    const float da=pi2/numOfPoints;
    float a,r0=radius-0.5*thickness,r1=radius+0.5*thickness,c,s;
    int e;
    glColor3f(color.r,color.g,color.b);
    glBegin(GL_QUAD_STRIP);
    for (e=1,a=0.0;e;a+=da) 
      {
      if (a>=pi2) { e=0; a=pi2; }
      c=cos(a); s=sin(a);
      glVertex2f(c*r0 + x, s * r0 + y); 
      glVertex2f(c*r1 + x, s * r1 + y); 
      }
    glEnd();
    }

Shaders

you can even create shader that takes as input center,thickness and radius of your circle (as uniforms) and using it by rendering single QUAD bbox around circle. then inside fragment shader discard all fragments outside your circle circumference. Something like this:
- How can i make gradient sphere on glsl?

Implementing #2 is the easiest. with #1 is some work needed but not too much if you know how to use VBO. #3 is also not too complicated but if you do not have any experience with shaders that might pose a problem...

I have never said that I am using GL_QUADS. I am using GL_TRIANGLES with my batched renderer. It looks like: 1. Create vao, vbo(with no data), ebo(with indices data), 2. Map a buffer, 3. Add data to the buffer (Using DrawRect(), FillRect(), DrawCircle(), DrawLine(), methodes), 4. unmap the buffer 5. Draw elements with one draw call Your DrawCircle method shows the legacy. — IScream, Jun 25 '18 at 11:15
This batched renderer is very efficient. I can render 100k textured rectshaped sprites while having ~3k fps. Maybe Geometry shader renderer would be more efficient - I do not know, I have not read about geometry shader yet. — IScream, Jun 25 '18 at 11:19
@IScream Geometry shaders are usually slow and not working properly on all implementations. If you are on new GL then **#3** is the way as it needs just single QUAD: **VAO/VBO** per circle that can even be static with placement matrix and fragment shader do the rest .... btw you should add the info from your last comment into your question as it is a significant spec. — Spektre, Jun 25 '18 at 11:53

How to optimize circle draw?

2 Answers2