Mark's circles wtf

Started by meems, February 13, 2018, 10:22:10

Previous topic - Next topic

Derron

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

meems

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.

meems

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.

windman

Quote from: meems on February 14, 2018, 16:11:44

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


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?

meems

I dunno. it would have to be a different algorithm

Qube

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.
Mac Studio M1 Max ( 10 core CPU - 24 core GPU ), 32GB LPDDR5, 512GB SSD,
Beelink SER7 Mini Gaming PC, Ryzen 7 7840HS 8-Core 16-Thread 5.1GHz Processor, 32G DDR5 RAM 1T PCIe 4.0 SSD
MSI MEG 342C 34" QD-OLED Monitor

Until the next time.

GaborD

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.

Qube

QuoteQube's image approach is probably the easiest and fastest.
\o/

QuoteBut 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)
Mac Studio M1 Max ( 10 core CPU - 24 core GPU ), 32GB LPDDR5, 512GB SSD,
Beelink SER7 Mini Gaming PC, Ryzen 7 7840HS 8-Core 16-Thread 5.1GHz Processor, 32G DDR5 RAM 1T PCIe 4.0 SSD
MSI MEG 342C 34" QD-OLED Monitor

Until the next time.

Derron

Quote from: GaborD on January 03, 2019, 04:59:52
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

GaborD

Quote from: Derron on January 03, 2019, 08:11:26
Quote from: GaborD on January 03, 2019, 04:59:52
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.


Quote from: Qube on January 03, 2019, 05:29:39
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.

Xerra

Quote from: Qube on January 03, 2019, 05:29:39
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/
M2 Pro Mac mini - 16GB 512 SSD
ACER Nitro 5 15.6" Gaming Laptop - Intel® Core™ i7, RTX 3050, 1 TB SSD
Vic 20 - 3.5k 1mhz 6502

Latest game - https://xerra.itch.io/Gridrunner
Blog: http://xerra.co.uk
Itch.IO: https://xerra.itch.io/

windman

#26
I went all the way up to 82 and it still shows at least one empty space.

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


meems

>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... :(

Kryzon

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: 


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

3DzForMe

Most awesome circle Ness code
BLitz3D, IDEal, AGK Studio, BMax, Java Code, Cerberus
Recent Hardware: Dell Laptop
Oldest Hardware: Commodore Amiga 1200 with 1084S Monitor & Blitz Basic 2.1