Draw a filled circle

[Cybermonkey]

Has anybody a suggestion for an algorithm which draws a filled circle? It's not OpenGL but SDL2 based. So used can be drawing a point at x,y or drawing a line or drawing a filled rectangle.

Ok, I found a solution but it's absolutely slow:

procedure fillcircle (xc,yc,radius:integer);var x,y:integer;
begin
for  y :=-radius to radius do begin
    for x :=-radius to radius do begin
        if (x*x+y*y <= radius*radius) then begin
            dot (xc+x, yc+y);
         end;
     end;
 end;
end;

If anyone knows a faster one I would appreciate some help.

[Super Vegeta]

Hmm, how about... If you know the radius, then of course you know how "wide" the circle will be = how many pixels on the X scale the circle will span. What I'm thinking is, for each pixel-step on X axis, calculate the Y-difference and draw a line from (Xpos, centerY+diffY) to (Xpos, centerY-diffY). Since you'll probably save diffY to a variable to avoid calculating it twice, you could use this knowledge to draw a line on the opposite X-side of the circle.

Pseudocode:

procedure circle(cx,cy,r) {
   r2 = r * r
   for x := r downto 0 {
      y = sqrt(r2 - x*x)
      dx = cx - x
      drawline(dx, cy-y, dx, cy+y)
      dx = cx + x
      drawline(dx, cy-y, dx, cy+y)
      }
   }

[drezgames]

Yea, what @Super Vegeta said.

Here is some code from my old engine. I got a little speed boost because DrawRect was HW accelerated and sin/cos is a lookup table. It worked well enough back then. Maybe this can give your more ideas as well.

procedure TPGRenderDevice.DrawCircle(aX, aY, aRadius: Single; aColor: Cardinal; aRenderState: TPGRenderState; aFilled: Boolean);
var
  a  : integer;
  src: TPGVector3s;
  dst: TPGVector3s;
  dir: TPGVector3s;
begin

  if aFilled then
    begin
      for a := 0 to 90 do
      begin
        dir.x := PG.Math.AngleCos(A) * aRadius;
        dir.y := PG.Math.AngleSin(A) * aRadius;

        src.x := ax - dir.x;
        src.y := ay - dir.y;

        dst.x := ax + dir.x;
        dst.y := ay + dir.y;

        PG.RenderDevice.DrawRect(src.x, src.y, dst.x-src.x, dst.y-src.y, aColor, aRenderState);
      end;
    end
  else
    begin
      for a := 0 to 180 do
      begin
        dir.x := PG.Math.AngleCos(A) * aRadius;
        dir.y := PG.Math.AngleSin(A) * aRadius;

        src.x := ax - dir.x;
        src.y := ay - dir.y;

        dst.x := ax + dir.x;
        dst.y := ay + dir.y;

        PG.RenderDevice.DrawRect(src.x, src.y, 1, 1, aColor, aRenderState);
        PG.RenderDevice.DrawRect(dst.x, dst.y, 1, 1, aColor, aRenderState);

      end;
    end;
end;

[SilverWarior]

Why not simply draw the circle first and then use FlodFill? I belive VCL indelphi uses this approach and it works OK.

Another way you could simply draw bunch of LineTo from the center of the circle. The number of lines needed depends on circumference of a circle.
This approach would probably be slower than one using flod fill especially with large circles.

[Cybermonkey]

Thanks for your suggestions, guys. I just made a test between my old implementation via SDL_gfx (SDL 1.2) and the above and - heck - the new implementation is even faster. SDL 1.2 needs about 1200 ms for 500 filled and outlined circles. SDL2 (and my code) needs for the same task about 650 ms. So I think I can live for now with the simplest implementation. And now the test without the "normal" circles; SDL2 wins again. Maybe that's because SDL2 is faster or maybe because SDL_gfx's circle algorithm is slow.
BTW, the screen was redrawn after each circle.

Oh, I should have tested after the complete task was redrawn ... SDL1.2 -> 6(!) ms, SDL2 ->500ms
Ok, I took the approach of Super Vegeta and it's only about 18 ms now. Thanks.

[Mirage]

OMG, Sqrt/ArcCos within the inner cycle!
http://cboard.cprogramming.com/game-...algorithm.html