Page 1 of 2 12 LastLast
Results 1 to 10 of 11

Thread: Draw a filled circle

  1. #1

    Draw a filled circle

    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:
    Code:
    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.
    Last edited by Cybermonkey; 30-10-2013 at 09:54 PM.
    Best regards,
    Cybermonkey

  2. #2
    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:
    Code:
    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)
          }
       }

  3. #3
    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.


    Code:
    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;

  4. #4
    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.

  5. #5
    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.
    Last edited by Cybermonkey; 31-10-2013 at 12:41 PM.
    Best regards,
    Cybermonkey

  6. #6

  7. #7
    Quote Originally Posted by Mirage View Post
    OMG, Sqrt/ArcCos within the inner cycle!
    http://cboard.cprogramming.com/game-...algorithm.html
    But your link does not refer to a filled circle algorithm. You see in my first post I had a solution without sqrt. But it was awfully slow.
    I came to this, which is fast and does not overlap anymore (this can be seen when drawing alphablended):
    Code:
    procedure fillcircle (cx,cy,r:integer); 
    var x,y,r2,dx:integer;
    begin
        if r = 0 then begin
            r:=1;
        end;
       r2 := r * r;
       for x := r downto 0 do begin
          y := round(sqrt(r2 - x*x));
          dx := cx - x;
          line(dx-1, cy-y, dx-1, cy+y);
          dx := cx + x;
          line(dx, cy-y, dx, cy+y);
          end;
    end;
    Best regards,
    Cybermonkey

  8. #8
    PGDCE Developer Carver413's Avatar
    Join Date
    Jun 2010
    Location
    Spokane,WA,Usa
    Posts
    206
    well I suppose that works but what if you want a 6 sided circle or an ellipse or a half circle. might be better to use a more conventual routine with a fill routine.

  9. #9
    Sometimes, but fill routine makes it much slower. It is checking for pixels on every draw to find where the borders are, and could also be allocating dynamic arrays for point data, depending on algorithm. You can modify algorithms to make filled half circle etc. And if you need to draw the circle on top of a complex drawing, fill no longer works. And it's in addition that you would use sin/cos/sqrt for outline anyway

    Here's algorithm for above given function translated, filled and non-filled circle. (Drawing to TForm.canvas directly was bad idea, i know... but it showed it at least.)
    Code:
    procedure DrawPixel(x, y: longint; color: TColor);
    begin
      form1.Canvas.Pixels[x, y]:=color;
    end;
    
    procedure DrawLine(x1, x2, y: longint; color: TColor);
    var x: integer;
    begin
      for x:=x1 to x2 do
        form1.Canvas.Pixels[x, y]:=color;
    end;
    
    procedure retro_circle(xc, yc, r: longint; color: TColor);
    var x, y, d: longint;
    begin
      x:=0; y:=r;
      d:=1 - r;
      while x < y do begin
        if d < 0 then
          d:=d + 2*x + 3
        else begin
          d:=d + 2*x - 2*y + 5;
          dec(y);
        end;
        DrawPixel(xc + x, yc - y, color); // Top
        DrawPixel(xc - x, yc - y, color);
        DrawPixel(xc + y, yc - x, color); // Upper middle
        DrawPixel(xc - y, yc - x, color);
        DrawPixel(xc + y, yc + x, color); // Lower middle
        DrawPixel(xc - y, yc + x, color);
        DrawPixel(xc + x, yc + y, color); // Bottom
        DrawPixel(xc - x, yc + y, color);
        inc(x);
      end;
    end;
    
    procedure retro_fill_circle(xc, yc, r: longint; color: TColor);
    var x, y, d: longint;
    begin
      x:=0; y:=r;
      d:=1 - r;
      while x < y do begin
        if d < 0 then
          d:=d + 2*x + 3
        else begin
          d:=d + 2*x - 2*y + 5;
          dec(y);
        end;
        DrawLine(xc - x, xc + x, yc - y, color);
        DrawLine(xc - y, xc + y, yc - x, color);
        DrawLine(xc - y, xc + y, yc + x, color);
        DrawLine(xc - x, xc + x, yc + y, color);
        inc(x);
      end;
    end;
    Also as far as i see, the fill function may draw some pixels overlapped. Not perfectly optimal this way.
    Last edited by User137; 13-11-2013 at 10:49 PM. Reason: Didn't need those n variables

  10. #10
    Quote Originally Posted by Cybermonkey View Post
    But your link does not refer to a filled circle algorithm.
    If you can draw a circle bound, you know all its points. And then you can draw all the needed horizontal lines very fast.

Page 1 of 2 12 LastLast

Bookmarks

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •