June 27, 2019, 12:09:20 AM

Author Topic: Mark's circles wtf  (Read 1704 times)

Offline Derron

  • Hero Member
  • *****
  • Posts: 2170
Re: Mark's circles wtf
« Reply #15 on: February 14, 2018, 07:26:47 PM »
You will miss pixels with this for loop (to draw a solid circle)...
On the other hand I assume it is faster to have "KISS" principles for circles (have another function for "drawOval" than for "drawCircle").


bye
Ron

Offline meems

  • Sr. Member
  • ****
  • Posts: 310
Re: Mark's circles wtf
« Reply #16 on: February 14, 2018, 08:35:16 PM »
I know what u mean, I used it to draw solid circles. Drawing 2 identical circles via this method, 1 pixel apart, is enough to eliminate 99.999% of missed pixels.

Offline meems

  • Sr. Member
  • ****
  • Posts: 310
Re: Mark's circles wtf
« Reply #17 on: February 14, 2018, 08:49:17 PM »
wrt the kiss idea, whatever that is, to draw ovals or other non circles, the function is simple enough its easier to mod it by including extra terms or changing the writepixel x and y parameters.

Offline windman

  • Jr. Member
  • **
  • Posts: 30
Re: Mark's circles wtf
« Reply #18 on: January 02, 2019, 10:13:22 PM »

I'm so glad you asked!  :D
Behold, a modest genius's finely crafted exhibit!

Code: [Select]
Function my_circle(x,y,r,col=222+(222 Shl 8)+(222 Shl 16))

x2#=r
y2#=0
n=r*6.29  ; if gaps in circle then increase this number, but should be ok

For i=0 To n
 WritePixel x+x2,y+y2,col
 x2=x2-y2/r
 y2=y2+x2/r
Next

End Function

Actually, back in the blitzforum days, I saw others write their own circle and oval functions. We never got to the point of testing against each other to see whose was the fastest and most versatile. But some of us noobs were surprised we could beat Mark, and it made us feel like leet programmers for a moment.

I use the OVAL function but how does a person fill this in if necessary?

Offline meems

  • Sr. Member
  • ****
  • Posts: 310
Re: Mark's circles wtf
« Reply #19 on: January 02, 2019, 11:08:57 PM »
I dunno. it would have to be a different algorithm

Offline Qube

  • Administrator
  • Hero Member
  • *****
  • Posts: 1925
Re: Mark's circles wtf
« Reply #20 on: January 03, 2019, 02:56:57 AM »
Couldn't you just cheat with this and have a large circle image and just scale it to the dimensions you want?. Surely that would be faster than drawing a filled circle / oval via code?

I remember once writing an image rotation routine in AMOS. My God was it slow doing that in interpreted code.
Until the next time...

Offline GaborD

  • Sr. Member
  • ****
  • Posts: 284
Re: Mark's circles wtf
« Reply #21 on: January 03, 2019, 04:59:52 AM »
Qube's image approach is probably the easiest and fastest.

But if you want to do it in code,
if it's a circle (not an oval) the simplest way (not the fastest though) would be to just bruteforce it. For next through a square of the appropiate size and plot pixels that are nearer to the middle than the radius.

The better approach would be to for next halfway around the circle/oval from top to bottom (really simple with sin/cos) and every time you switch to the next y position draw a line from the max -x to the max +x of the last line. You just have to ensure that your step-size doesn't exceed one line worth of movement.

Offline Qube

  • Administrator
  • Hero Member
  • *****
  • Posts: 1925
Re: Mark's circles wtf
« Reply #22 on: January 03, 2019, 05:29:39 AM »
Quote
Qube's image approach is probably the easiest and fastest.
\o/

Quote
But if you want to do it in code
Maybe a mini comp in a designated language to do the fastest filled circle / oval routine could be good fun?  8)
Until the next time...

Offline Derron

  • Hero Member
  • *****
  • Posts: 2170
Re: Mark's circles wtf
« Reply #23 on: January 03, 2019, 08:11:26 AM »
The better approach would be to for next halfway around the circle/oval from top to bottom (really simple with sin/cos) and every time you switch to the next y position draw a line from the max -x to the max +x of the last line. You just have to ensure that your step-size doesn't exceed one line worth of movement.

and when doing his you also draw a line at "y + distanceOfCenterAndCurrentPointY" - so you eg. only calculate (not exactly but I guess you get what I want to say) the upper half of a circle. So in essence you only calculate a quarter of a circle and mirror the other parts.


bye
Ron

Offline GaborD

  • Sr. Member
  • ****
  • Posts: 284
Re: Mark's circles wtf
« Reply #24 on: January 03, 2019, 08:47:05 AM »
The better approach would be to for next halfway around the circle/oval from top to bottom (really simple with sin/cos) and every time you switch to the next y position draw a line from the max -x to the max +x of the last line. You just have to ensure that your step-size doesn't exceed one line worth of movement.

and when doing his you also draw a line at "y + distanceOfCenterAndCurrentPointY" - so you eg. only calculate (not exactly but I guess you get what I want to say) the upper half of a circle. So in essence you only calculate a quarter of a circle and mirror the other parts.


bye
Ron

Yeah you are right, only need to do a quarter.
I think this approach should be pretty fast.


Maybe a mini comp in a designated language to do the fastest filled circle / oval routine could be good fun?  8)

Mini comps like this would be fun. Maybe with a bit more complex "problems" to solve than just a circle, but still simple enough so that everyone can give it a quick shot.
You would prolly get quite a few entries and as a side benefit the site would build up a small code repository for these common programming issues.

Offline Xerra

  • Hero Member
  • *****
  • Posts: 607
    • Retro Evolved
Re: Mark's circles wtf
« Reply #25 on: January 03, 2019, 11:18:31 AM »
Maybe a mini comp in a designated language to do the fastest filled circle / oval routine could be good fun?  8)

10 print "  **"
20 print " ***"
30 print "*****"
40 print " ***"
50 print "  **"

Your winner !! \O/

Offline windman

  • Jr. Member
  • **
  • Posts: 30
Mark's circles
« Reply #26 on: January 03, 2019, 09:53:24 PM »
I went all the way up to 82 and it still shows at least one empty space.

Code: [Select]
x2#=r
y2#=0
n=r*82.29  ; if gaps in circle then increase this number, but should be ok

For i=0 To n
 WritePixel x+x2,y+y2,col
 x2=x2-y2/r
 y2=y2+x2/r
Next

At this high of a number, it's much slower than using the oval function in BB.
At very small sizes where the radius is 6 or 7, the function makes the circles irregular.
Overall it is a very speedy function though.
Great Job Mark


Offline meems

  • Sr. Member
  • ****
  • Posts: 310
Re: Mark's circles wtf
« Reply #27 on: January 04, 2019, 12:12:55 PM »
>I went all the way up to 82 and it still shows at least one empty space.
It'd be quicker to draw 2 circles displaced by one pixel with n=r*6.29, or some minor mod to fill in the pixel if its in a regular place

>At very small sizes where the radius is 6 or 7, the function makes the circles irregular.
I haven't tried but I'd guess it might help accuracy if the iteration variables were given 2 values each i.e.
x[0] and x[1] and y[0] and y[1]
then each iteration flip between array elements 0 and 1.

>Great Job Mark
Mark gets credit for everything... :(

Offline Kryzon

  • Full Member
  • ***
  • Posts: 120
Re: Mark's circles wtf
« Reply #28 on: January 05, 2019, 04:31:40 AM »
I only thought of filled\solid ovals, too lazy to think of the outline version right now... This uses the radius-based technique that GaborD mentioned, but comparing squared distances for the extra speed up. 

You can download BlitzPlus as pay-what-you-want (even if zero) in here: https://blitzresearch.itch.io/blitzplus 

Template code: 


Code: [Select]
Const IMAGE_WIDTH = 512
Const IMAGE_HEIGHT = 256
Const WIDTH_PADDING = 16 + 16
Const HEIGHT_PADDING = 16 + 16 + 1 + 12 + 16 + 6

Function argb(r, g, b)
    Return $ff000000 Or (r Shl 16) Or (g Shl 8) Or b
End Function


Function greyARGB(r)
    Return $ff000000 Or (r Shl 16) Or (r Shl 8) Or r
End Function


Function drawFunction(buffer)
    ; Plotting function, put your algorithim(s) in here.
    ; buffer = buffer address to be used with WritePixelFast().
   
    If IMAGE_WIDTH = IMAGE_HEIGHT Then
        ; Circle.
        halfWidth# = (IMAGE_WIDTH - 1.0) * 0.5
        halfHeight# = halfWidth       
        radiusSquared# = halfWidth * halfWidth
       
        For y = 0 To IMAGE_HEIGHT - 1
            For x = 0 To IMAGE_WIDTH - 1
                deltaX# = (x - halfWidth)
                deltaY# = (y - halfHeight)
                If (deltaX*deltaX + deltaY*deltaY) <= radiusSquared Then
                    WritePixelFast(x, y, greyARGB(255), buffer)
                EndIf
            Next
        Next
    Else
        ; Ellipse.
        invWidth# = 1.0 / (IMAGE_WIDTH - 1)
        invHeight# = 1.0 / (IMAGE_HEIGHT - 1)
        radiusSquared# = 0.5 * 0.5 

        For y = 0 To IMAGE_HEIGHT - 1
            For x = 0 To IMAGE_WIDTH - 1
                deltaX# = (x * invWidth) - 0.5
                deltaY# = (y * invHeight) - 0.5
                If (deltaX*deltaX + deltaY*deltaY) <= radiusSquared Then
                    WritePixelFast(x, y, greyARGB(255), buffer)
                EndIf
            Next
        Next
    EndIf
End Function


AppTitle("Plotting Speed Test")
Graphics(IMAGE_WIDTH + WIDTH_PADDING, IMAGE_HEIGHT + HEIGHT_PADDING, 0, 2) ; Windowed mode.
Cls()
image = CreateImage(IMAGE_WIDTH, IMAGE_HEIGHT)
buffer = ImageBuffer(image)

LockBuffer(buffer)
startTime = MilliSecs()
drawFunction(buffer)
deltaTime = MilliSecs() - startTime
UnlockBuffer(buffer)

DrawImage(image, GraphicsWidth() * 0.5 - IMAGE_WIDTH * 0.5, 16)
overlayY = 16 + IMAGE_HEIGHT + 16 + 1
Line(0, overlayY, GraphicsWidth(), overlayY)
Text(0, overlayY+1, "Delta time: " + Str(deltaTime) + "ms")
Text(0, overlayY+1+16, "Press any key to end.")
Flip()

WaitKey()
End

Offline 3DzForMe

  • Hero Member
  • *****
  • Posts: 584
Re: Mark's circles wtf
« Reply #29 on: January 05, 2019, 04:07:22 PM »
Most awesome circle Ness code