Fast filled circles (DBP command replacement)

Author

Message

David T

Retired Moderator

21

Years of Service

User Offline

Joined: 27th Aug 2002

Location: England

Posted: 19th Mar 2003 22:12

Link

I've remade the circle command complete with shading too. It's around 500 fps on my beast of a machine, shouldn't be too slow

+ Code Snippet

sync rate 0 : sync on : set text opaque
do
ink rgb(255,255,255),0
  if mouseclick()=1 then FillCircle(mousex(),mousey(),50)
  ink rgb(200,0,0),0
  text 10,10,"Fast filled circles by David Tattersall :: FPS: "+str$(screen fps())
  sync
loop
Function Fillcircle(x,y,r)
for ang = 1 to 180
px = x + sin(360-ang) * r
py = y + cos(360-ang) * r
px2 = x + sin(ang) * r
py2 = y + cos(ang) * r
line px,py,px2,py2
next ang
endfunction

You are the http://s15.sitemeter.com/meter.asp?site=s15dtsig[/img]th person to view this signature.
Programmers don't die, they just Gosub without return....

Back to top

Profile PM Email Website

Easily Confused

21

Years of Service

User Offline

Joined: 22nd Oct 2002

Location: U.K. Earth. (turn right at Venus)

Posted: 20th Mar 2003 01:25 Edited at: 20th Mar 2003 01:46

Link

Out of curiosity, how fast are these versions?

+ Code Snippet

sync rate 0 : sync on : set text opaque

do
ink rgb(255,255,255),0
  if mouseclick()=1 then FillCircle(mousex(),mousey(),50)
  ink rgb(200,0,0),0
  text 10,10,"Fast filled circles :: FPS: "+str$(screen fps())
  sync
loop

Function Fillcircle(x,y,r)
  for ang = 0 to 180
    dx = sin(ang) * r
    dy = cos(ang) * r
    box x - dx, y - dy, x + dx, y - dy+1
  next ang
endfunction

...and

+ Code Snippet

sync rate 0 : sync on : set text opaque

do
ink rgb(255,255,255),0
  if mouseclick()=1 then FillCircle(mousex(),mousey(),50)
  ink rgb(200,0,0),0
  text 10,10,"Fast filled circles :: FPS: "+str$(screen fps())
  sync
loop

Function Fillcircle(x,y,r)
  for ang = 0 to 90
    dx = sin(ang) * r
    dy = cos(ang) * r
    box x - dx, y - dy, x + dx, y + dy
  next ang
endfunction

Programming anything is an art, and you can't rush art.
Unless your name is Bob Ross, then you can do it in thirty minutes.

Back to top

Profile PM

David T

Retired Moderator

21

Years of Service

User Offline

Joined: 27th Aug 2002

Location: England

Posted: 20th Mar 2003 21:21

Link

First snippet: ~219
Second: ~256 when drawing (600 when not but that doesn't count)

You are the

th person to view this signature.
Programmers don't die, they just Gosub without return....

Back to top

Profile PM Email Website

IanM

Retired Moderator

21

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 20th Mar 2003 21:56

Link

You have far too much overdraw (writing the same pixels again and again) and your calculations are too intensive.

Here's a replacement with no overdraw and less intensive calculations (uses pythagoras instead of sin/cos) - it was as fast as I could make it - this was version 5 or 6 (OK, I was bored!).

+ Code Snippet

function FillCircle( CX as integer, CY as integer, R as integer )
   local x as integer
   local y as integer
   local i as integer
   i=R*R
   box CX-R, CY, CX+R+1, CY+1
   for y=1 to R
      x=sqrt( i-(y*y) )
      box CX-x, CY-y, CX+x+1, CY-y+1
      box CX-x, CY+y, CX+x+1, CY+y+1
   next x
endfunction

These are the fps I get with each one.
David89: 233
EC/1: 415
EC/2: 310
Mine: 445

Not drawing anything in the loop gets me 495 fps. It's not a super machine either - 850Mhz PIII laptop with an ATI M4 Mobility.

Back to top

Profile PM Email Website

David T

Retired Moderator

21

Years of Service

User Offline

Joined: 27th Aug 2002

Location: England

Posted: 20th Mar 2003 22:09

Link

I was wondering - what ovewrdraw?

My function draws horizontal lines across the screen from one side of the circle to the other. Since the lines are not horizontal, that cannot be diagonal, and when that happens you get overdraw.

.........
.....=====......
.================.
.================.
.================.
.================.
.....=====......
.........

How's overdraw possible? (within one use of the function)

You are the

th person to view this signature.
Programmers don't die, they just Gosub without return....

Back to top

Profile PM Email Website

IanM

Retired Moderator

21

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 20th Mar 2003 22:38 Edited at: 20th Mar 2003 22:41

Link

Because you are using angles you are drawing some of the horizontal lines over previously drawn lines.

For example, using a cirle with a radius of 50, when you work out the x coord for angles 88 and 89 degrees you will see that they both come out as 49 point something. When you draw you drop the fractions they will overlap.

Here's a piece of code that counts the number of overdrawn lines:

+ Code Snippet

sync rate 0
sync on

cls rgb(0,0,0)
ink rgb(255,255,255),0
print FillCircle(200,200,50)

sync
wait key
end

Function Fillcircle(x,y,r)
   overdraw=0
   for ang = 1 to 180
      px = x + sin(360-ang) * r
      py = y + cos(360-ang) * r
      px2 = x + sin(ang) * r
      py2 = y + cos(ang) * r
      ` Check the centre of the new line to see if we've already drawn here
      if point(x,py) <> point(0,0) then inc overdraw
      line px,py,px2,py2
   next ang
endfunction overdraw

EC's code had much more overdraw but it was hardware accelerated.

Back to top

Profile PM Email Website

Easily Confused

21

Years of Service

User Offline

Joined: 22nd Oct 2002

Location: U.K. Earth. (turn right at Venus)

Posted: 20th Mar 2003 22:51

Link

Very true, especialy when drawing smaller circles.

Programming anything is an art, and you can't rush art.
Unless your name is Bob Ross, then you can do it in thirty minutes.

Back to top

Profile PM

David T

Retired Moderator

21

Years of Service

User Offline

Joined: 27th Aug 2002

Location: England

Posted: 21st Mar 2003 21:30

Link

Ah, I see. Looks like my diagram didn't turn out too well

I'm not a maths expert, just had an idea

You are the

th person to view this signature.
Programmers don't die, they just Gosub without return....

Back to top

Profile PM Email Website

IanM

Retired Moderator

21

Years of Service

User Offline

Joined: 11th Sep 2002

Location: In my moon base

Posted: 22nd Mar 2003 15:43

Link

Here's another even faster version

I think I'll stop with this one now!

+ Code Snippet

cls

start=timer()
for i=1 to 10000
   FillCircle(125,125,50)
next i
finish=timer()
print finish-start

sync
wait key

function FillCircle( CX as integer, CY as integer, R as integer )
   local x as integer
   local y as integer
   local i as integer
   local s as integer

   s=R*0.70710678 : ` this number is sin(45) - precalculate!
   box CX-s, CY-s, CX+s+1, CY+s+1
   s=s+1 : ` Faster than 'inc s'?
   i=R*R
   for y=s to R
      x=sqrt( i-(y*y) )

      ` Draw top and bottom
      box CX-x, CY-y, CX+x+1, CY-y+1
      box CX-x, CY+y, CX+x+1, CY+y+1

      ` Draw left and right
      box CX-y, CY-x, CX-y+1, CY+x+1
      box CX+y, CY-x, CX+y+1, CY+x+1
   next y
endfunction

This one draws a central box, and then fills out the top/bottom/sides.

Instead of timing using fps, I've switched to timing how long it takes to draw 10000 circles.
This code reduced the time from 2.725 seconds to 1.984 seconds on my pc - a drop of about 28%.

Back to top

Profile PM Email Website

Sorry your browser is not supported!

The 20 Line Challenge / Fast filled circles (DBP command replacement)