[DBC/DBP] Fill circle by looping through less than 1/4 of the pixels

Author

Message

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 19th Jan 2009 21:06

Link

Not sure where this idea came from, I think I may have heard or seen the idea elsewhere. But since a circle is symmetrical on both X and Y, a few simple checks can draw a filled-in circle.

DBC

+ Code Snippet

function fillCircle(x,y,r)
   for yy = y-r to y
      for xx = x-r to x
         d# = (xx-x)^2 + (yy-y)^2
         if d# <= r*r
            box xx,yy,x+(x-xx),yy+1
            if yy <> y then box xx,y+(y-yy),x+(x-xx),y+(y-yy)+1
            exit
         endif
      next xx
   next yy
endfunction

DBP

+ Code Snippet

function fillCircle(x,y,r)
   for yy = y-r to y
      for xx = x-r to x
         d# = (xx-x)^2 + (yy-y)^2
         if d# <= r*r
            box xx,yy,x+(x-xx)+1,yy+1
            if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
            exit
         endif
      next xx
   next yy
endfunction

The reason for the slightly two different versions is in how the BOX command works. DBC seems to be inclusive of the coordinates, where a box from 1,1 to 1,1 would fill 1 pixel. But in DBP, a box with the same coordinates would draw nothing and needs 1,1 to 2,2. At least stretching the circle out 1 extra pixel in pro then gave me equal results between classic and pro.

DB Code Corner

Back to top

Profile PM Email Website

Mr Tank

21

Years of Service

User Offline

Joined: 25th Nov 2002

Location: United Kingdom

Posted: 21st Jan 2009 18:35

Link

You could make it faster by using box to draw lines, and take advantage of the diagonal symmetry. Also using * instead of the ^2 might make it a little faster, though i suspect the computation is a lot quicker than the actual drawing.

Back to top

Profile PM Website

AndrewT

17

Years of Service

User Offline

Joined: 11th Feb 2007

Location: MI, USA

Posted: 21st Jan 2009 19:09

Link

Ya, I gained a 40% performance gain by changing the exponents to multiplication. Here's the changed code:

+ Code Snippet

function fillCircle(x,y,r)
   for yy = y-r to y
      for xx = x-r to x
         d# = ( (xx-x)*(xx-x) ) + ( (yy-y)*(yy-y) )
         if d# <= r*r
            box xx,yy,x+(x-xx)+1,yy+1
            if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
            exit
         endif
      next xx
   next yy
endfunction

Back to top

Profile PM

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 21st Jan 2009 21:39

Link

Not sure what you mean tank, I'm already using box to draw the lines

DB Code Corner

Back to top

Profile PM Email Website

Mr Tank

21

Years of Service

User Offline

Joined: 25th Nov 2002

Location: United Kingdom

Posted: 23rd Jan 2009 01:45 Edited at: 23rd Jan 2009 01:49

Link

Quote: "Not sure what you mean tank, I'm already using box to draw the lines
"

Sorry. I misread your code. I thought that because you were looping over x and y you must have been drawing individual pixels with the box command, but i see what you did now. Quite cunning. I think you could maybe gain by computing the ends of each line using sqrt.. (DBP version)

+ Code Snippet

function fillCircle(x,y,r)
   for yy = y-r to y
         xx= x - sqrt(r*r - (yy-y)^2 )
            box xx,yy,x+(x-xx)+1,yy+1
            if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
   next yy
endfunction

Back to top

Profile PM Website

Phaelax

DBPro Master

21

Years of Service

User Offline

Joined: 16th Apr 2003

Location: Metropia

Posted: 23rd Jan 2009 02:15

Link

ooo clever, but I wonder if the sqrt() affects performance. Fewer loops, but we all know how slow sqrt can be.

Your signature has been erased by a mod because it's larger than 600x120

Back to top

Profile PM Email Website

Mr Tank

21

Years of Service

User Offline

Joined: 25th Nov 2002

Location: United Kingdom

Posted: 23rd Jan 2009 02:28

Link

it's a good question. should do a speed test. Avoiding sqrt, i made the following optimisation. NB i am still using ^2. lose that and it'll get quicker still..

+ Code Snippet

function fillCirclea(x,y,r)
   xs=x-r
   lasty=y+r
   for yy = y to lasty
      ysq=(yy-y)^2
      for xx = xs to x
         d = (xx-x)^2 + ysq
         if d <= r*r
            box xx,yy,x+(x-xx)+1,yy+1
            if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
            exit
         endif
      next xx
      xs=xx
   next yy
endfunction

Back to top

Profile PM Website

Mr Tank

21

Years of Service

User Offline

Joined: 25th Nov 2002

Location: United Kingdom

Posted: 23rd Jan 2009 02:39 Edited at: 23rd Jan 2009 02:50

Link

OK check it out. 4 versions of the function in order of speed, with the box commands commented out. Your original first, then an altered version with different looping, the same again with ^2 not used, then the sqrt version. The sqrt one is significantly quicker.

timestart=timer()
fillCircle(100,100,550)
fillCircle(300,300,2050)
time1=timer()-timestart

timestart=timer()
fillCirclea(100,100,550)
fillCirclea(300,300,2050)
time2=timer()-timestart

timestart=timer()
fillCirclea1(100,100,550)
fillCirclea1(300,300,2050)
time3=timer()-timestart

timestart=timer()
fillCirclenew(100,100,550)
fillCirclenew(300,300,2050)
time4=timer()-timestart

print time1
print time2
print time3
print time4

wait key
end

function fillCircle(x,y,r)
   for yy = y-r to y
      for xx = x-r to x
         d# = (xx-x)^2 + (yy-y)^2
         if d# <= r*r
          `  box xx,yy,x+(x-xx)+1,yy+1
          `  if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
            exit
         endif
      next xx
   next yy
endfunction

function fillCirclea(x,y,r)
   xs=x-r
   lasty=y+r
   for yy = y to lasty
      ysq=(yy-y)^2
      for xx = xs to x
         d = (xx-x)^2 + ysq
         if d <= r*r
         `   box xx,yy,x+(x-xx)+1,yy+1
         `   if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
            exit
         endif
      next xx
      xs=xx
   next yy
endfunction

function fillCirclea1(x,y,r)
   xs=x-r
   lasty=y+r
   for yy = y to lasty
      ysq=(yy-y)*(yy-y)
      for xx = xs to x
         d = (xx-x)*(xx-x) + ysq
         if d <= r*r
         `   box xx,yy,x+(x-xx)+1,yy+1
         `   if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
            exit
         endif
      next xx
      xs=xx
   next yy
endfunction

function fillCirclenew(x,y,r)
   for yy = y-r to y
         xx= x - sqrt(r*r - (yy-y)^2 )
          `  box xx,yy,x+(x-xx)+1,yy+1
          `  if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
   next yy
endfunction

+ Code Snippet

timestart=timer()
fillCircle(100,100,550)
fillCircle(300,300,2050)
time1=timer()-timestart

timestart=timer()
fillCirclea(100,100,550)
fillCirclea(300,300,2050)
time2=timer()-timestart

timestart=timer()
fillCirclea1(100,100,550)
fillCirclea1(300,300,2050)
time3=timer()-timestart

timestart=timer()
fillCirclenew(100,100,550)
fillCirclenew(300,300,2050)
time4=timer()-timestart

print time1
print time2
print time3
print time4

wait key
end

function fillCircle(x,y,r)
   for yy = y-r to y
      for xx = x-r to x
         d# = (xx-x)^2 + (yy-y)^2
         if d# <= r*r
          `  box xx,yy,x+(x-xx)+1,yy+1
          `  if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
            exit
         endif
      next xx
   next yy
endfunction


function fillCirclea(x,y,r)
   xs=x-r
   lasty=y+r
   for yy = y to lasty
      ysq=(yy-y)^2
      for xx = xs to x
         d = (xx-x)^2 + ysq
         if d <= r*r
         `   box xx,yy,x+(x-xx)+1,yy+1
         `   if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
            exit
         endif
      next xx
      xs=xx
   next yy
endfunction


function fillCirclea1(x,y,r)
   xs=x-r
   lasty=y+r
   for yy = y to lasty
      ysq=(yy-y)*(yy-y)
      for xx = xs to x
         d = (xx-x)*(xx-x) + ysq
         if d <= r*r
         `   box xx,yy,x+(x-xx)+1,yy+1
         `   if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
            exit
         endif
      next xx
      xs=xx
   next yy
endfunction

function fillCirclenew(x,y,r)
   for yy = y-r to y
         xx= x - sqrt(r*r - (yy-y)^2 )
          `  box xx,yy,x+(x-xx)+1,yy+1
          `  if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
   next yy
endfunction

here's with the drawing commands back in:

sync on

timestart=timer()
fillCircle(100,100,550)
fillCircle(300,300,2050)
time1=timer()-timestart

timestart=timer()
fillCirclea(100,100,550)
fillCirclea(300,300,2050)
time2=timer()-timestart

timestart=timer()
fillCirclea1(100,100,550)
fillCirclea1(300,300,2050)
time3=timer()-timestart

timestart=timer()
fillCirclenew(100,100,550)
fillCirclenew(300,300,2050)
time4=timer()-timestart

sync

ink 0,0

print time1
print time2
print time3
print time4

sync

wait key
end

function fillCircle(x,y,r)
   for yy = y-r to y
      for xx = x-r to x
         d# = (xx-x)^2 + (yy-y)^2
         if d# <= r*r
            box xx,yy,x+(x-xx)+1,yy+1
            if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
            exit
         endif
      next xx
   next yy
endfunction

function fillCirclea(x,y,r)
   xs=x-r
   lasty=y+r
   for yy = y to lasty
      ysq=(yy-y)^2
      for xx = xs to x
         d = (xx-x)^2 + ysq
         if d <= r*r
            box xx,yy,x+(x-xx)+1,yy+1
            if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
            exit
         endif
      next xx
      xs=xx
   next yy
endfunction

function fillCirclea1(x,y,r)
   xs=x-r
   lasty=y+r
   for yy = y to lasty
      ysq=(yy-y)*(yy-y)
      for xx = xs to x
         d = (xx-x)*(xx-x) + ysq
         if d <= r*r
            box xx,yy,x+(x-xx)+1,yy+1
            if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
            exit
         endif
      next xx
      xs=xx
   next yy
endfunction

function fillCirclenew(x,y,r)
   for yy = y-r to y
         xx= x - sqrt(r*r - (yy-y)^2 )
            box xx,yy,x+(x-xx)+1,yy+1
            if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
   next yy
endfunction

+ Code Snippet

sync on

timestart=timer()
fillCircle(100,100,550)
fillCircle(300,300,2050)
time1=timer()-timestart

timestart=timer()
fillCirclea(100,100,550)
fillCirclea(300,300,2050)
time2=timer()-timestart

timestart=timer()
fillCirclea1(100,100,550)
fillCirclea1(300,300,2050)
time3=timer()-timestart

timestart=timer()
fillCirclenew(100,100,550)
fillCirclenew(300,300,2050)
time4=timer()-timestart

sync

ink 0,0

print time1
print time2
print time3
print time4

sync

wait key
end

function fillCircle(x,y,r)
   for yy = y-r to y
      for xx = x-r to x
         d# = (xx-x)^2 + (yy-y)^2
         if d# <= r*r
            box xx,yy,x+(x-xx)+1,yy+1
            if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
            exit
         endif
      next xx
   next yy
endfunction


function fillCirclea(x,y,r)
   xs=x-r
   lasty=y+r
   for yy = y to lasty
      ysq=(yy-y)^2
      for xx = xs to x
         d = (xx-x)^2 + ysq
         if d <= r*r
            box xx,yy,x+(x-xx)+1,yy+1
            if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
            exit
         endif
      next xx
      xs=xx
   next yy
endfunction


function fillCirclea1(x,y,r)
   xs=x-r
   lasty=y+r
   for yy = y to lasty
      ysq=(yy-y)*(yy-y)
      for xx = xs to x
         d = (xx-x)*(xx-x) + ysq
         if d <= r*r
            box xx,yy,x+(x-xx)+1,yy+1
            if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
            exit
         endif
      next xx
      xs=xx
   next yy
endfunction

function fillCirclenew(x,y,r)
   for yy = y-r to y
         xx= x - sqrt(r*r - (yy-y)^2 )
            box xx,yy,x+(x-xx)+1,yy+1
            if yy <> y then box xx,y+(y-yy),x+(x-xx)+1,y+(y-yy)+1
   next yy
endfunction

BTW i have no idea why the 3rd command appears to be slower than the 2nd one!! Also, you can get a tiny bit more speed by calculating r*r at the start of the function.

Back to top

Profile PM Website

Mr Kohlenstoff

17

Years of Service

User Offline

Joined: 7th Jun 2006

Location: Germany

Posted: 24th Jan 2009 18:31

Link

Interesting, I did something similar some months ago, don't know where the code is however.

@MrTank: The third one seems to be the fastest here, around 50% faster than 2 and 4. The first function is around 200 times slower.

Back to top

Profile PM Email

IanM

Retired Moderator

21

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 24th Jan 2009 19:21

Link

Has anyone tried the version I put into codebase a 'short' while back?

http://www.thegamecreators.com/?m=codebase_view_code&i=c6a376253a019691f5fcc97de1c5247a

There are still a few possible cycles that can be squeezed out of it if anyone wants to bother.

Utility plug-ins collection (updated 29/12/08) and
http://www.matrix1.demon.co.uk

Back to top

Profile PM Email Website

Mr Tank

21

Years of Service

User Offline

Joined: 25th Nov 2002

Location: United Kingdom

Posted: 25th Jan 2009 04:54 Edited at: 25th Jan 2009 04:56

Link

Quote: "@MrTank: The third one seems to be the fastest here, around 50% faster than 2 and 4. The first function is around 200 times slower."

Interesting. For me 4 is way faster than 2 or 3, but maybe square roots are slower relative to normal operations for you than they are for me. Wierd.

Quote: "Has anyone tried the version I put into codebase a 'short' while back?"

Dude that's sweet. I hadn't thought to but the box in the middle.

Back to top

Profile PM Website

Diggsey

18

Years of Service

User Offline

Joined: 24th Apr 2006

Location: On this web page.

Posted: 28th Feb 2009 21:03

Link

This code will draw random filled circles with an average radius of 37 pixels, with an average speed of 0.24 milliseconds per circle. I don't know how that compares with the others:

+ Code Snippet

sync on

do
    start = timer()
    for i = 1 to 10000
        fillcircle(rnd(screen width()),rnd(screen height()),rnd(50)+5)
    next i
    finish = timer()
    cls 0
    print finish-start
    sync : sync
    wait key
loop

function fillcircle(x,y,radius)
    r# = radius
    for i = -radius to 0
        offx = sin(acos(i/r#))*r#
        x1 = x-offx
        x2 = x+offx
        y1 = y+i
        y2 = y-i
        box x1,y1,x2,y1+1
        box x1,y2,x2,y2+1
    next i
endfunction

[b]Yuor signutare was aresed by a deslyxic mud...
BOX2D V2 HAS HELP FILES! AND A WIKI!

Back to top

Profile PM Email Website

calcyman

16

Years of Service

User Offline

Joined: 31st Aug 2007

Location: The Uncertainty Principle

Posted: 2nd Mar 2009 21:49

Link

Have you considered using lock pixels/unlock pixels to make rendering faster?

The optimist's right, The pessimist's right.

Back to top

Profile PM Email

IanM

Retired Moderator

21

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 2nd Mar 2009 22:10

Link

Yes, but it doesn't (or didn't use to) have an effect on drawing speed with the BOX command because BOX uses DirectX to render it.

Utility plug-ins collection (updated 29/12/08) and
http://www.matrix1.demon.co.uk

Back to top

Profile PM Email Website

Sorry your browser is not supported!

Code Snippets / [DBC/DBP] Fill circle by looping through less than 1/4 of the pixels