Board index » delphi » the fastest algorithm for drawing a circle?

the fastest algorithm for drawing a circle?

I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
unsatisfied with the performance. I believe that there must be some
algorithm far better than mine, can you tell me?
 

Re:the fastest algorithm for drawing a circle?


Search the net for Bresenham's algorithm for circles and you will find what
you need.
--
Finn Tolderlund

"Alphone" <Silf...@sohu.com> skrev i en meddelelse news:3c9e9e1d_1@dnews...

Quote
> I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

Re:the fastest algorithm for drawing a circle?


Quote
"Alphone" <Silf...@sohu.com> wrote in message news:3c9e9e1d_1@dnews...
> I previously use lots of sin(..) & cos(..) calls to do that, and i'm
very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

or you can pre-compute a table of sin/cos values for, say, 12 points round
the circle and use the table values.

Re:the fastest algorithm for drawing a circle?


use lookup tables (arrays) to store sin and cos

Michael.

Quote
"Alphone" <Silf...@sohu.com> wrote in message news:3c9e9e1d_1@dnews...
> I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

Re:the fastest algorithm for drawing a circle?


You can use a table with sin and cos entries. Usually, you won't see the
difference between a true circle and - say - one with about 80 line
segments.

This translates to a table of ONLY 20 value pairs, because, smart hehe, you
only have to hold values for 1 quadrant. The second, third and 4th quadrant
values just require negations on the correct spot.

You can precalculate this sin/cos table and re-use it anywhere where you
need them (circles, ellipses).

If you want to draw a true circle then you can also use the sqr(x) + sqr(y)
= constant property to get there faster. I believe this is the basis for the
aforementioned Bresenham algorithm.

This also works ideally for painting circular areas. Just imagine a square
box (or bitmap) where you go through all the scanlines, top down. For each
pixel you do

if sqr(Xpos - Xmid) + sqr(Ypos - Ymid) < sqr(Radius) then
  Pixel[XPos, YPos] := Black
else
  Pixel[XPos, YPos] := White

You can optimise this by using scanlines, and precalculating sqr(Radius),
and sqr(YPos- YMid) for each scanline.

Using an estimation method to find the left and right x per scanline would
be not too hard. And using the same quadrant copying scheme is not hard too.

You can even make it neater by defining a band (Radius1 & Radius2) of a
pixel wide (or the width you want). Then, define for each pixel corner the
value and doing some math to calculate the pixel's coloring. This would
actually be a anti-aliased circle draw, and probably still miles faster than
your own sin/cos approach.

Regards,

Nils
www.abc-view.com

Quote
Alphone <Silf...@sohu.com> wrote in message news:3c9e9e1d_1@dnews...
> I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

Re:the fastest algorithm for drawing a circle?


Hi

    Make a lookup table for results of sin and cos functions. Then, instead
calculating the value, look for result in the table.

Tomaz

Quote
"Alphone" <Silf...@sohu.com> wrote in message news:3c9e9e1d_1@dnews...
> I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

Re:the fastest algorithm for drawing a circle?


Have you tried the Borland work ?

Put a button on a form and put this code:

Var i : Integer;
begin
  for i := 1 to 500 do
    form1.Canvas.Ellipse(0,0,i,i);
end;

"Alphone" <Silf...@sohu.com> escreveu na mensagem news:3c9e9e1d_1@dnews...

Quote
> I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

Re:the fastest algorithm for drawing a circle?


Quote
> I previously use lots of sin(..) & cos(..)

There was a paper of Prof N. Wirth ETH Zrich
"Drawing Lines, Circles ands Ellipses in a Raster"
using only (32 bit) integer arithmetic (Bresenham)

I have this as PDF: 5 pages, 300 kB.

There is cited
Foley, Van Dam;  Fundamentals of of interactive Computer Graphics; 1982

Cossit; Line drawing with the NS32CG16 and drwaing circles with NS32CG16.
 AN-522 and AN-523 National Semiconductors Corp 1988

Re:the fastest algorithm for drawing a circle?


see
http://www.national.com/apnotes/apnotes_all_1.html
AN-522
Quote
Alphone wrote:

> I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

Re:the fastest algorithm for drawing a circle?


Quote
Alphone wrote:
> I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

Note that you only need to calculate the coords for 1/8 of a circle,
the other points can be mirrored...

--
                                       Andreas
To spam me by mail, please add NOSPAM to my
email address.

Re:the fastest algorithm for drawing a circle?


Quote
> There was a paper of Prof N. Wirth ETH Zrich
> "Drawing Lines, Circles ands Ellipses in a Raster"
> using only (32 bit) integer arithmetic (Bresenham)

I tried to translate the algorithms

UNIT BresPix;
INTERFACE                                                {+unit BresPix}
TYPE
  std_Str=STRING[255];
  std_Int=LongInt;
  PROCEDURE BresPix_Test;
  {====================================================}
IMPLEMENTATION                                           {+unit BresPix}
USES  Crt  ;
TYPE
  xyPix_Rec=RECORD
    xPix,yPix:{Vw0Typ .}std_Int;
  END;

  PROCEDURE PixelPut(x:xyPix_Rec; c:Char);
  BEGIN                                            {+procedure PixelPut}
    Crt .GotoXY(x.xPix+1,x.yPix+1);    Write(c);
  END;                                             {+procedure PixelPut}

  PROCEDURE LineSimple(a,b:{Vw0Typ .}std_Int);
  VAR
    x:xyPix_Rec;
  BEGIN                                          {+procedure LineSimple}
    x.xPix:=0;
    WHILE (x.xPix<a) DO BEGIN                                    {+ _1_}
      x.yPix:=b*x.xPix DIV a;
      PixelPut(x,'1');
    Inc(x.xPix); END;
  END;                                           {+procedure LineSimple}

  PROCEDURE LineBres(a,b:{Vw0Typ .}std_Int);
  VAR
    x:xyPix_Rec;
    i:RECORD
      hlp:{Vw0Typ .}std_Int;
      b_a:{Vw0Typ .}std_Int;
    END;
  BEGIN                                            {+procedure LineBres}
    x.xPix:=0;    x.yPix:=0;
    i.hlp:=b-(a DIV 2)-(b div 2){ correct for 1 pixel };
    i.b_a:=b-a;
    WHILE (x.xPix<a) DO BEGIN                                    {+ _2_}
      PixelPut(x,'2');
      IF (i.hlp<=0) THEN BEGIN
        i.hlp:=i.hlp+b;
      END ELSE BEGIN
        i.hlp:=i.hlp+(i.b_a);        x.yPix:=x.yPix+1;
      END;
    Inc(x.xPix); END;
  END;                                             {+procedure LineBres}

  PROCEDURE CircleBresQuadrantHalf(r:{Vw0Typ .}std_Int);
  VAR
    x:xyPix_Rec;
    i:RECORD
      hlp:{Vw0Typ .}std_Int;
    END;
  BEGIN                                          {+procedure CircleBres}
    x.xPix:=r;    x.yPix:=0;
    i.hlp:=1-r;
    WHILE (x.yPix<x.xPix) DO BEGIN                               {+ _3_}
      PixelPut(x,'c');
      IF (i.hlp<0) THEN BEGIN
        i.hlp:=i.hlp+2*x.yPix+3;
      END ELSE BEGIN
        i.hlp:=i.hlp+2*(x.yPix-x.xPix)+5;        x.xPix:=x.xPix-1;
      END;
    Inc(x.yPix); END;
  END;                                           {+procedure CircleBres}

  PROCEDURE EllipseBresQuadrant1(a,b:{Vw0Typ .}std_Int);
  VAR
    x:xyPix_Rec;
    i:RECORD
      d,g,h:{Vw0Typ .}std_Int;
    END;
    y:RECORD
      y1:{Vw0Typ .}std_Int;
      a2,b2:{Vw0Typ .}std_Int;
    END;
  BEGIN                                         {+procedure EllipseBres}
    y.a2:=a*a;    y.b2:=b*b;
    BEGIN
      x.xPix:=0;      x.yPix:=b;
      i.h:=(y.a2 DIV 4)-b*y.a2+y.b2;
      i.g:=Round((9/4)*y.a2)-3*b*y.a2+y.b2;
      WHILE (i.g<0) DO BEGIN                                     {+ _4_}
        PixelPut(x,'E');
        IF (i.h<0) THEN BEGIN
          i.d:=(2*x.xPix+3)*y.b2;
          i.g:=i.g+i.d;
        END ELSE BEGIN
          i.d:=(2*x.xPix+3)*y.b2-2*(x.yPix-1)*y.a2;
          i.g:=i.g+i.d+2*y.a2;
          x.yPix:=x.yPix-1;
        END;
        i.h:=i.h+i.d;
      Inc(x.xPix); END;
    END;
    BEGIN
      x.xPix:=a;      y.y1:=x.yPix;       x.yPix:=0;
      i.h:=(y.b2 DIV 4)-a*y.b2+2*y.a2;
      WHILE (x.yPix<=y.y1) DO BEGIN                              {+ _5_}
        PixelPut(x,'e');
        IF (i.h<0) THEN BEGIN
          i.h:=i.h+(2*x.yPix+3)*y.a2;
        END ELSE BEGIN
          i.h:=i.h+(2*x.yPix+3)*y.a2-2*(x.xPix-1)*y.b2;
          x.xPix:=x.xPix-1;
        END;
      Inc(x.yPix); END;
    END;
  END;                                          {+procedure EllipseBres}
  {= = = = = = = = = = = = = = = = = = = = = = = = = = }
  PROCEDURE BresPix_Test;
  BEGIN                                        {+procedure BresPix_Test}
    Crt .ClrScr;
    LineSimple(60,20);
    LineBres(60,20);
    CircleBresQuadrantHalf(15);
    EllipseBresQuadrant1(70,20);
  END;                                         {+procedure BresPix_Test}

BEGIN                                                    {+unit BresPix}
  {$DEFINE Test_BresPix}
  {$IFDEF Test_BresPix }BresPix_Test{$ENDIF };
END {$IFDEF VwDel6 }{$WARNINGS OFF}{$ENDIF}.             {+unit BresPix}

Re:the fastest algorithm for drawing a circle?


There is another way to do it using rotations.
Imagine the circle with center (X0, Y0) and radius R
Set the initial point (R, 0) => (X0+R, Y0)

var
  X, Y : Double;
  I : Integer;

X:=R;
Y:=0;

Set the number of points to 2.Pi.R

for I:=0 to Round(2*Pi*R) do
  begin
    Plot(X0+X, Y0+Y);
    { Rotate point (X,Y) }
    X:=X-Y/R;
    Y:=Y+X/R;
  end;

The angle between each point is (2.Pi)/(2.Pi.R) = 1/R

Cos(X) for small X is near 1 and Sin(X) for small X is near X and that is
the magic.
I know the X in the second expression (Y=...) is new and this is an error
but it works.

[]s
Arthur

Alphone <Silf...@sohu.com> escreveu nas notcias de mensagem:3c9e9e1d_1@dnews...

Quote
> I previously use lots of sin(..) & cos(..) calls to do that, and i'm very
> unsatisfied with the performance. I believe that there must be some
> algorithm far better than mine, can you tell me?

Other Threads