Jump to content
conibo

Circle drawing algorithm

By conibo, in Other Scripts

Recommended Posts

conibo Junior Member

conibo

Posted
Posted (edited)

This is Bresenham's circle drawing algorithm for SCAR 3.22. I rediscovered it myself; only after writing it did I look it up on Wikipedia.

I reinvented the wheel, kind of.

I got the idea from my calculus 2 classes and from Bresenham's line drawing algorithm, which I still don't understand completely.

 

program New;
const
WHITE = 16777215;
BLACK = 0;
RED = 209910;
BMPSIZE = 499;
COSPIFOURTH = 0.7071068;
var
bmp,qq,y,m,k,j: integer;

procedure drawevencircle2(offsetx,offsety,radius:integer);
//radius includes the outer pixel
var radiussquared,Y0,pixelstodo,count: integer;
   temp1,temp2,temp3,temp4: integer;
begin
pixelstodo:=round(radius*COSPIFOURTH);
radiussquared:= radius*radius;
radiussquared:=radiussquared + radius div 2;
Y0:=radius;
for count:=0 to pixelstodo do begin
   temp1:=offsetx+count+1; temp2:=offsety-Y0;
   temp3:=offsetx-count; temp4:=offsety+Y0+1;
   fastsetpixel(bmp, temp1,temp2 , RED);//second octant
   fastsetpixel(bmp, temp3,temp2 , RED);//third octant
   fastsetpixel(bmp, temp1,temp4 , RED);//seventh octant
   temp1:= offsetx-Y0; temp2:=offsety+count+1;
   fastsetpixel(bmp, temp3,temp4 , RED);//sixth octant
   temp3:=offsety-count; temp4:= offsetx+Y0+1;
   fastsetpixel(bmp, temp1, temp2, RED);//fifth octant
   fastsetpixel(bmp, temp1, temp3, RED);//fourth octant
   fastsetpixel(bmp, temp4, temp2, RED);//eighth octant
   fastsetpixel(bmp, temp4, temp3, RED);//first octant
   if((Y0*Y0+count*count)>radiussquared) then Y0:=Y0-1;
   radiussquared:=radiussquared-1;
   end;
end;
procedure drawevencircleopt(offsetx,offsety,radius:integer);
//radius includes the outer pixel
var radiussquared,Y0,pixelstodo,count,Y0squared,countsquared: integer;
   temp1,temp2,temp3,temp4: integer;
begin
pixelstodo:=round(radius*COSPIFOURTH);
radiussquared:= radius*radius;
Y0squared:=radiussquared;
radiussquared:=radiussquared + radius div 2;
Y0:=radius;
countsquared:=0;
for count:=0 to pixelstodo do begin
   temp1:=offsetx+count+1; temp2:=offsety-Y0;
   temp3:=offsetx-count; temp4:=offsety+Y0+1;
   fastsetpixel(bmp, temp1,temp2 , WHITE);//second octant
   fastsetpixel(bmp, temp3,temp2 , WHITE);//third octant
   fastsetpixel(bmp, temp1,temp4 , WHITE);//seventh octant
   temp1:= offsetx-Y0; temp2:=offsety+count+1;
   fastsetpixel(bmp, temp3,temp4 , WHITE);//sixth octant
   temp3:=offsety-count; temp4:= offsetx+Y0+1;
   fastsetpixel(bmp, temp1, temp2, WHITE);//fifth octant
   fastsetpixel(bmp, temp1, temp3, WHITE);//fourth octant
   fastsetpixel(bmp, temp4, temp2, WHITE);//eighth octant
   fastsetpixel(bmp, temp4, temp3, WHITE);//first octant
   if((Y0squared+countsquared)>radiussquared) then begin
                                Y0squared:=Y0squared-(Y0*2)+1;
                                Y0:=Y0-1;
                                end;
   countsquared:=countsquared+(count*2)+1;
   radiussquared:=radiussquared-1;
   end;
end;


begin
 displayDebugImgWindow(BMPSIZE+1,BMPSIZE+1);
 wait(100);
 qq := GetDebugCanvas;
 bmp := BitmapFromString(BMPSIZE, BMPSIZE, '');
 y:=getbitmapcanvas(bmp);
 m:=1;
 j:=getsystemtime;
 for k:=1 to 20 do begin
     m:=m+2+2*k;
     drawevencircle2(m,22,k);
     end;
 for k:=4 to 200 do begin
     drawevencircle2(250,250,k);
     k:=k+2;
     end;
 writeln(getsystemtime-j);
 m:=1;
 j:=getsystemtime;
 for k:=1 to 20 do begin
     m:=m+2+2*k;
     drawevencircleopt(m,22,k);
     end;
 for k:=4 to 200 do begin
     drawevencircleopt(250,250,k);
     k:=k+2;
     end;
 writeln(getsystemtime-j);
 SafeCopyCanvas(y, qq, 0, 0, BMPSIZE, BMPSIZE, 0, 0, BMPSIZE, BMPSIZE);
 freebitmap(bmp);
end.

 

In this program, ironically, the optimized version is consistently slower than the non-optimized one.

 

EDIT: I messed up the squaring code for the optimized version earlier. It is correct now.

Edited by conibo
  • Like 1
Link to comment
Share on other sites
Janilabo Contributing Member

 Janilabo

Posted
Posted (edited)
This is Bresenham's circle drawing algorithm for SCAR 3.22. I rediscovered it myself; only after writing it did I look it up on Wikipedia.

I reinvented the wheel, kind of.

I got the idea from my calculus 2 classes and from Bresenham's line drawing algorithm, which I still don't understand completely.

 

program New;
const
WHITE = 16777215;
BLACK = 0;
RED = 209910;
BMPSIZE = 499;
COSPIFOURTH = 0.7071068;
var
bmp,qq,y,m,k,j: integer;

procedure drawevencircle2(offsetx,offsety,radius:integer);
//radius includes the outer pixel
var radiussquared,Y0,pixelstodo,count: integer;
   temp1,temp2,temp3,temp4: integer;
begin
pixelstodo:=round(radius*COSPIFOURTH);
radiussquared:= radius*radius;
radiussquared:=radiussquared + radius div 2;
Y0:=radius;
for count:=0 to pixelstodo do begin
   temp1:=offsetx+count+1; temp2:=offsety-Y0;
   temp3:=offsetx-count; temp4:=offsety+Y0+1;
   fastsetpixel(bmp, temp1,temp2 , RED);//second octant
   fastsetpixel(bmp, temp3,temp2 , RED);//third octant
   fastsetpixel(bmp, temp1,temp4 , RED);//seventh octant
   temp1:= offsetx-Y0; temp2:=offsety+count+1;
   fastsetpixel(bmp, temp3,temp4 , RED);//sixth octant
   temp3:=offsety-count; temp4:= offsetx+Y0+1;
   fastsetpixel(bmp, temp1, temp2, RED);//fifth octant
   fastsetpixel(bmp, temp1, temp3, RED);//fourth octant
   fastsetpixel(bmp, temp4, temp2, RED);//eighth octant
   fastsetpixel(bmp, temp4, temp3, RED);//first octant
   if((Y0*Y0+count*count)>radiussquared) then Y0:=Y0-1;
   radiussquared:=radiussquared-1;
   end;
end;
procedure drawevencircleopt(offsetx,offsety,radius:integer);
//radius includes the outer pixel
var radiussquared,Y0,pixelstodo,count,Y0squared,countsquared: integer;
   temp1,temp2,temp3,temp4: integer;
begin
pixelstodo:=round(radius*COSPIFOURTH);
radiussquared:= radius*radius;
Y0squared:=radiussquared;
radiussquared:=radiussquared + radius div 2;
Y0:=radius;
countsquared:=0;
for count:=0 to pixelstodo do begin
   countsquared:=countsquared+(count*2)+1;
   temp1:=offsetx+count+1; temp2:=offsety-Y0;
   temp3:=offsetx-count; temp4:=offsety+Y0+1;
   fastsetpixel(bmp, temp1,temp2 , WHITE);//second octant
   fastsetpixel(bmp, temp3,temp2 , WHITE);//third octant
   fastsetpixel(bmp, temp1,temp4 , WHITE);//seventh octant
   temp1:= offsetx-Y0; temp2:=offsety+count+1;
   fastsetpixel(bmp, temp3,temp4 , WHITE);//sixth octant
   temp3:=offsety-count; temp4:= offsetx+Y0+1;
   fastsetpixel(bmp, temp1, temp2, WHITE);//fifth octant
   fastsetpixel(bmp, temp1, temp3, WHITE);//fourth octant
   fastsetpixel(bmp, temp4, temp2, WHITE);//eighth octant
   fastsetpixel(bmp, temp4, temp3, WHITE);//first octant
   if((Y0squared+countsquared)>radiussquared) then begin
                                Y0:=Y0-1;
                                Y0squared:=Y0squared-(Y0*2)+1;
                                end;
   radiussquared:=radiussquared-1;
   end;
end;


begin
 displayDebugImgWindow(BMPSIZE+1,BMPSIZE+1);
 wait(100);
 qq := GetDebugCanvas;
 bmp := BitmapFromString(BMPSIZE, BMPSIZE, '');
 y:=getbitmapcanvas(bmp);
 m:=1;
 j:=getsystemtime;
 for k:=1 to 20 do begin
     m:=m+2+2*k;
     drawevencircle2(m,22,k);
     end;
 for k:=4 to 200 do begin
     drawevencircle2(250,250,k);
     k:=k+2;
     end;
 writeln(getsystemtime-j);
 m:=1;
 j:=getsystemtime;
 for k:=1 to 20 do begin
     m:=m+2+2*k;
     drawevencircleopt(m,22,k);
     end;
 for k:=4 to 200 do begin
     drawevencircleopt(250,250,k);
     k:=k+2;
     end;
 writeln(getsystemtime-j);
 SafeCopyCanvas(y, qq, 0, 0, BMPSIZE, BMPSIZE, 0, 0, BMPSIZE, BMPSIZE);
 freebitmap(bmp);
end.

 

In this program, ironically, the optimized version is consistently slower than the non-optimized one.

Nice work conibo!

Interesting code you have wrote there.

 

By the way, here is the 3.35+ version of it (tested with 3.38 & 3.39):

 

const
 WHITE = 16777215;
 BLACK = 0;
 RED = 209910;
 BMPSIZE = 499;
 COSPIFOURTH = 0.7071068;

var
 bmp: TSCARBitmap;
 m, k, j: Integer;

//radius includes the outer pixel
procedure DrawEvenCircle2(offsetx, offsety, radius: Integer);
var
 radiussquared, Y0, pixelstodo, count: Integer;
 temp1, temp2, temp3, temp4: Integer;
begin
 pixelstodo := Round(radius * COSPIFOURTH);
 radiussquared := (radius * radius);
 radiussquared := (radiussquared + (radius div 2));
 Y0 := radius;
 for count := 0 to pixelstodo do
 begin
   temp1 := ((offsetx + count) + 1);
   temp2 := (offsety - Y0);
   temp3 := (offsetx - count);
   temp4 := ((offsety + Y0) + 1);
   bmp.Pixels[temp1, temp2] := RED;//second octant
   bmp.Pixels[temp3, temp2] := RED;//third octant
   bmp.Pixels[temp1, temp4] := RED;//seventh octant
   temp1 := (offsetx - Y0);
   temp2 := (offsety + count + 1);
   bmp.Pixels[temp3, temp4] := RED;//sixth octant
   temp3 := (offsety - count);
   temp4 := ((offsetx + Y0) + 1);
   bmp.Pixels[temp1, temp2] := RED;//fifth octant
   bmp.Pixels[temp1, temp3] := RED;//fourth octant
   bmp.Pixels[temp4, temp2] := RED;//eighth octant
   bmp.Pixels[temp4, temp3] := RED;//first octant
   if (((Y0 * Y0) + (count * count)) > radiussquared) then
     Y0 := (Y0 - 1);
   radiussquared := (radiussquared - 1);
 end;
end;

//radius includes the outer pixel
procedure DrawEvenCircleopt(offsetx, offsety, radius: Integer);
var
 radiussquared, Y0, pixelstodo, count, Y0squared, countsquared: Integer;
 temp1, temp2, temp3, temp4: Integer;
begin
 pixelstodo := Round(radius * COSPIFOURTH);
 radiussquared := (radius * radius);
 Y0squared := radiussquared;
 radiussquared := (radiussquared + (radius div 2));
 Y0 := radius;
 countsquared := 0;
 for count := 0 to pixelstodo do
 begin
   temp1 := (offsetx + count + 1);
   temp2 := (offsety - Y0);
   temp3 := (offsetx - count);
   temp4 := ((offsety + Y0) + 1);
   bmp.Pixels[temp1, temp2] := WHITE;//second octant
   bmp.Pixels[temp3, temp2] := WHITE;//third octant
   bmp.Pixels[temp1, temp4] := WHITE;//seventh octant
   temp1 := (offsetx - Y0);
   temp2 := ((offsety + count) + 1);
   bmp.Pixels[temp3, temp4] := WHITE;//sixth octant
   temp3 := (offsety - count);
   temp4 := ((offsetx + Y0) + 1);
   bmp.Pixels[temp1, temp2] := WHITE;//fifth octant
   bmp.Pixels[temp1, temp3] := WHITE;//fourth octant
   bmp.Pixels[temp4, temp2] := WHITE;//eighth octant
   bmp.Pixels[temp4, temp3] := WHITE;//first octant
   if ((Y0squared + countsquared) > radiussquared) then
   begin            
     Y0squared := (Y0squared - (Y0 * 2) + 1);
     Y0 := (Y0 - 1);
   end;          
   countsquared := (countsquared + (count * 2) + 1);
   radiussquared := (radiussquared - 1);
 end;
end;

begin
 DisplayDebugImgWindow((BMPSIZE + 1), (BMPSIZE + 1));
 Wait(100);          
 bmp := TSCARBitmap.Create('');
 bmp.SetSize(BMPSIZE, BMPSIZE);
 m := 1;
 j := GetSystemTime;
 for k := 1 to 20 do
 begin
   m := ((m + 2) + (2 * k));
   DrawEvenCircle2(m, 22, k);
 end;
 for k := 4 to 200 do
 begin
   DrawEvenCircle2(250, 250, k);
   k := (k + 2);
 end;
 WriteLn(IntToStr(GetSystemTime - j) + ' ms.');
 m := 1;
 j := GetSystemTime;
 for k := 1 to 20 do
 begin
   m := ((m + 2) + (2 * k));
   DrawEvenCircleopt(m, 22, k);
 end;
 for k := 4 to 200 do
 begin
   DrawEvenCircleopt(250, 250, k);
   k := (k + 2);
 end;
 WriteLn(IntToStr(GetSystemTime - j) + ' ms.');
 DebugBitmap(bmp);
 bmp.Free;
end.

 

Once again, good job conibo! Thanks for sharing your code with the community man.

Edited by Janilabo
Included squaring fixes by conibo
Link to comment
Share on other sites
slacky Senior Member

 slacky

Posted
Posted (edited)

What you got there is a bad implementation of Bresenham's circle, and the use of a constant which from what I see is unsuited (COSPIFOURTH), and it destroys small circles from what I can tell. Not tryin' to be rude, but just stating the obvious.

 

Now this is a proper implementation of Bresenham's circle:

program new;

{ Creates all the points needed to define a simple circle }
function Circle(C: TPoint; Radius:Integer): TPointArray;
var
 err,x,y,h: Integer;
begin
 x := radius;
 y := 0;
 err := 1-x;
 h := 0;
 while(x >= y) do
 begin
   h := h + 8;
   SetLength(Result, h);  
   Result[h-1] := Point(C.x + x, C.y + y);
   Result[h-2] := Point(C.x - x, C.y + y);
   Result[h-3] := Point(C.x + x, C.y - y);
   Result[h-4] := Point(C.x - x, C.y - y);
   Result[h-5] := Point(C.x + y, C.y + x);
   Result[h-6] := Point(C.x - y, C.y + x);
   Result[h-7] := Point(C.x + y, C.y - x);
   Result[h-8] := Point(C.x - y, C.y - x);
   Inc(y);
   if(err < 0) then
     err := err + (2*y+1)
   else begin
     Dec(x);
     err := err + (2*(y-x+1));
   end;
 end;
end;


var
 i: Integer;
 TPA: TPointArray;
 bmp: TSCARBitmap;
begin
 bmp := TSCARBitmap.Create('');
 bmp.SetSize(300, 300);

 for i:=1 to 12 do  
 begin
   tpa := Circle(Point(150,150), Round(Sqr(i)));
   bmp.SetPixels(TPA, RandomRange(100000,16000000));  
 end;

 DebugBitmap(bmp);
 bmp.Free;
end.

 

But it's nice to see people contributing, so don't let me scare you away just cuz I can be an ass!! :-)

Edited by slacky
Uppdated - Support SCAR 3.4
Link to comment
Share on other sites
conibo Junior Member

conibo

Posted
  • Author
Posted
What you got there is a bad implementation of Bresenham's circle, and the use of a constant which from what I see is unsuited (COSPIFOURTH), and it destroys small circles from what I can tell.

 

My algorithm as posted doesn't really distort the smaller circles; it just assumes the center of the circle is between pixels, not on a pixel. Thus, "drawevencircle".

 

Radius times the cosine of one fourth of pi is the number of pixels in an octant, which is what I want to draw.

 

All that's required to turn the algorithm into a near-perfect Bresenham clone is changing the following lines

    temp1:=offsetx+count+1;
   temp4:=offsety+Y0+1;
   temp2:=offsety+count+1;
   temp4:= offsetx+Y0+1;

with these, respectively:

    temp1:=offsetx+count;
   temp4:=offsety+Y0;
   temp2:=offsety+count;
   temp4:= offsetx+Y0;

Link to comment
Share on other sites
conibo Junior Member

conibo

Posted
  • Author
Posted

I just thought of an optimization for my algorithm that would probably have been obvious to the more experienced programmers: merging Y0squared and countsquared into one variable.

 

For Scar 3.38, modified from the code graciously posted by Janilabo:

 

procedure DrawEvenCircleopt(offsetx, offsety, radius: Integer);
var
 radiussquared, Y0, pixelstodo, count, Y0squaredpluscountsquared: Integer;
 temp1, temp2, temp3, temp4: Integer;
begin
 pixelstodo := Round(radius * COSPIFOURTH);
 radiussquared := (radius * radius);
 Y0squaredpluscountsquared := radiussquared;
 radiussquared := (radiussquared + (radius div 2));
 Y0 := radius;
 for count := 0 to pixelstodo do
 begin
   temp1 := (offsetx + count);
   temp2 := (offsety - Y0);
   temp3 := (offsetx - count);
   temp4 := (offsety + Y0);
   bmp.Pixels[temp1, temp2] := WHITE;//second octant
   bmp.Pixels[temp3, temp2] := WHITE;//third octant
   bmp.Pixels[temp1, temp4] := WHITE;//seventh octant
   temp1 := (offsetx - Y0);
   temp2 := (offsety + count);
   bmp.Pixels[temp3, temp4] := WHITE;//sixth octant
   temp3 := (offsety - count);
   temp4 := (offsetx + Y0);
   bmp.Pixels[temp1, temp2] := WHITE;//fifth octant
   bmp.Pixels[temp1, temp3] := WHITE;//fourth octant
   bmp.Pixels[temp4, temp2] := WHITE;//eighth octant
   bmp.Pixels[temp4, temp3] := WHITE;//first octant
   if ((Y0squaredpluscountsquared) > radiussquared) then
   begin            
     Y0squaredpluscountsquared := (Y0squaredpluscountsquared - (Y0 * 2) + 1);
     Y0 := (Y0 - 1);
   end;          
   Y0squaredpluscountsquared := (Y0squaredpluscountsquared + (count * 2) + 1);
   radiussquared := (radiussquared - 1);
 end;
end;

 

And for Scar 3.22:

procedure drawevencircleopt(offsetx,offsety,radius:integer);

var radiussquared,Y0,pixelstodo,count,Y0squaredpluscountsquared: integer;
   temp1,temp2,temp3,temp4: integer;
begin
pixelstodo:=round(radius*COSPIFOURTH);
radiussquared:= radius*radius;
Y0squaredpluscountsquared:=radiussquared;
radiussquared:=radiussquared + radius div 2;
Y0:=radius;
for count:=0 to pixelstodo do begin
   temp1:=offsetx+count; temp2:=offsety-Y0;
   temp3:=offsetx-count; temp4:=offsety+Y0;
   fastsetpixel(bmp, temp1,temp2 , WHITE);//second octant
   fastsetpixel(bmp, temp3,temp2 , WHITE);//third octant
   fastsetpixel(bmp, temp1,temp4 , WHITE);//seventh octant
   temp1:= offsetx-Y0; temp2:=offsety+count;
   fastsetpixel(bmp, temp3,temp4 , WHITE);//sixth octant
   temp3:=offsety-count; temp4:= offsetx+Y0;
   fastsetpixel(bmp, temp1, temp2, WHITE);//fifth octant
   fastsetpixel(bmp, temp1, temp3, WHITE);//fourth octant
   fastsetpixel(bmp, temp4, temp2, WHITE);//eighth octant
   fastsetpixel(bmp, temp4, temp3, WHITE);//first octant
   if((Y0squaredpluscountsquared)>radiussquared) then begin
                                Y0squaredpluscountsquared:=Y0squaredpluscountsquared-(Y0*2)+1;
                                Y0:=Y0-1;
                                end;
   radiussquared:=radiussquared-1;
   Y0squaredpluscountsquared:=Y0squaredpluscountsquared+(count*2)+1;
   end;
end;

Link to comment
Share on other sites

Join the conversation

You can post now and register later. If you have an account, sign in now to post with your account.

Guest
Reply to this topic...

×   Pasted as rich text.   Paste as plain text instead

  Only 75 emoji are allowed.

×   Your link has been automatically embedded.   Display as a link instead

×   Your previous content has been restored.   Clear editor

×   You cannot paste images directly. Upload or insert images from URL.

×
Go to topic listing
×
×
  • Create New...