Log In  8  Cart [#44632#] | Code | 2017-09-26 | License: CC4-BY-NC-SA 8 EDIT: updated demo to include huge optimizations contributed by Felice and ultrabrite in the thread below.

After reading this fascinating article about the Minsky Circle, I started experimenting with the algorithm in Pico-8. In the process, I stumbled upon a method for rasterizing circles that seems to be faster than the native circ() and circfill() functions at larger sizes, and also has a more pleasing look that minimizes low-resolution aliasing.

Demo attached in case anyone finds this useful. Press Z (or whatever key you've bound to button 1) to toggle between the Minsky Circle-based methods and the native Pico-8 draw functions.

 ```--by @musurca and @Felice function minskycirc(x,y,r,c) x,y=x+0.5,y+0.5 local j,k,rat=r,0,1/r poke(0x5f25,c) --set color for i=1,0.785*r do k-=rat*j j+=rat*k pset(x+j,y+k) pset(x+j,y-k) pset(x-j,y+k) pset(x-j,y-k) pset(x+k,y+j) pset(x+k,y-j) pset(x-k,y+j) pset(x-k,y-j) end pset(x,y-r) pset(x,y+r) pset(x-r,y) pset(x+r,y) end -- @musurca, @Felice, and @ultrabrite function minskycircfill(x,y,r,c) x,y=x+0.5,y+0.5 local j,k,rat=r,0,1/r poke(0x5f25,c) --set color for i=1,r*0.786 do k-=rat*j j+=rat*k rectfill(x+j,y+k,x+j,y-k) rectfill(x-j,y+k,x-j,y-k) rectfill(x-k,y-j,x-k,y+j) rectfill(x+k,y-j,x+k,y+j) end rectfill(x,y-r,x,y+r) end ```
P#44528 2017-09-24 07:53 ( Edited 2017-09-26 11:19)  nice find!
even faster when filled (7.813% max), because... rectfill.

 ```function minskydisc(x,y,r,c) r*=0.705 local j,k,rat=r,r,0.5/r poke(0x5f25,c) --set color for i=1,r*5 do k=k-rat*j j=j+rat*k rectfill(x-j,y-k,x+j,y-k) rectfill(x-j,y+k,x+j,y+k) end end ```

(plus minor edits for tokens, I'm into that these days)

thanks for the article, looks like a great read!

P#44536 2017-09-24 11:06 ( Edited 2017-09-24 15:09)  Nice! That's a huge optimization. Updated the demo to include a comparison between your minskydisc() and circfill(), as well as the token shavings.

P#44583 2017-09-24 22:58 ( Edited 2017-09-25 02:58)  This is super cool. Thank you so much for posting it. Bookmarked.

P#44601 2017-09-25 14:16 ( Edited 2017-09-25 18:16)
:: Felice  Just keep in mind that the minsky circle makes up for its overdraw overhead (many pixels are plotted more than once) by having low loop overhead (not much math).

This means the filled-disc version posted here will have considerably more draw overhead if/when zep corrects the bug where the cycle count on rectangles is based on a rectangle one pixel narrower and shorter than it's supposed to be.

P#44604 2017-09-25 15:43 ( Edited 2017-09-25 19:43)  It says "Press X" but it actually checks for the 'O' key!

RUINED!

P#44607 2017-09-25 17:16 ( Edited 2017-09-25 21:16)  er, yes, "because...rectfill" was meant as a caveat. that fell a little short :P
I guess it will eventually come closer to using line(), which bumps the disc to 36% (vs 17% for circfill)
though line() is not optimized for horizontal lines, so proper rectfill() might end up a tad faster than that.

I wish zep pushed a little more hotfixes in between...

P#44609 2017-09-25 17:33 ( Edited 2017-09-25 21:41)
:: Felice  So I took a longer look. Low level rendering code is my playtime. :)

Three issues:

• This code is actually overdrawing more than it needs to, as the constant chosen for the loop length is larger than necessary.

• This code produces two-way symmetry, but not four-way. This indicates that the code can take advantage of one more level of unroll by drawing octants instead of quadrants.

• This code doesn't match the "center of circle at center of pixel" behavior of pico's internal routines.

Here's an updated version that's got better symmetry, less loop overhead, less overdraw, and matches the pico-8 behavior/silhouette better:

 ```-- @Felice was here :) function minskycirc8(x,y,r,c) x,y,r=x+0.5,y+0.5,r*0.707108 local j,k,rat=r,r,0.5/r poke(0x5f25,c) --set color for i=1,r*1.618 do k-=rat*j j+=rat*k pset(x+j,y+k) pset(x+j,y-k) pset(x-j,y+k) pset(x-j,y-k) pset(x+k,y+j) pset(x+k,y-j) pset(x-k,y+j) pset(x-k,y-j) end end ```

Side note: Turned out the golden ratio seems to be the ideal scale for the revised loop length. This may be purely coincidental, but I have to wonder.

Not super crazy about the remaining overdraw, but still, it's cool and definitely fast. Thanks for bringing it to our attention. :)

P#44610 2017-09-25 17:34 ( Edited 2017-09-25 21:37)  @Felice: awesome!
the golden ratio always crops up for no reason ;)

P#44611 2017-09-25 17:49 ( Edited 2017-09-25 21:49)
:: Felice  Addendum:

I think maybe there needs to be a half-step (not sure if backwards or forwards) extracted and placed above the loop. I catch glimpses of odd behaviors at certain sizes when the demo circle is pulsing.

I might track it down later, but I've managed to develop a headache and I'm honestly not in the mood right now.

And, hey, there are a bunch of other programmers here. Fix it if you spot the problem. ;)

P#44612 2017-09-25 17:55 ( Edited 2017-09-25 22:00)  Felice -- rad!! Drawing octants was a great idea. But I think we can go even deeper...

Here's a new-and-improved minskycirc() that draws fewer pixels than minskycirc8() at radii > 4, with less overdraw (at some radii), and no more magic numbers. (And the outline looks a bit cleaner, I think.)

 ```-- @musurca & @Felice function minskycirc(x,y,r,c) x,y=x+0.5,y+0.5,r local j,k,rat=r,0,1/r poke(0x5f25,c) --set color for i=1,r do k-=rat*j j+=rat*k pset(x+j,y+k) pset(x+j,y-k) pset(x-j,y+k) pset(x-j,y-k) pset(x+k,y+j) pset(x+k,y-j) pset(x-k,y+j) pset(x-k,y-j) end pset(x,y-r) pset(x,y+r) pset(x-r,y) pset(x+r,y) end ```

And a demo to compare it to minskycirc8():

Cart [#44627#] | Code | 2017-09-26 | License: CC4-BY-NC-SA  (And yes, I've swapped the keys to match Pico-8 convention. Thank you apLundell...)

P#44624 2017-09-26 02:58 ( Edited 2017-09-27 09:13)
:: Felice  Nice!

If you limit the radius to 63, you can just use the screen itself to check (and show) overdraw:

 ```function plot(x,y,c) assert(x>=0 and x<128 and y>=0 and y<128) c=c or peek(0x5f25) if pget(x,y)!=0 then overdrawn+=1 c=8 end pixelsdrawn+=1 _pset(x,y,c) end ```

(Could also do multiple colors to show multiple overdraw. I'm being lazy here and just switching to red.)

Visualization is always nice vs. showing numbers.

P#44629 2017-09-26 05:44 ( Edited 2017-09-26 09:52)  That's a great idea. And yes, the visualization helped point out an even faster version, which for some radii (e.g. 39) has 0%(!) overdraw:

 ```-- @musurca & @Felice function minskycirc(x,y,r,c) x,y=x+0.5,y+0.5 local j,k,rat=r,0,1/r poke(0x5f25,c) --set color for i=1,r*0.785 do k-=rat*j j+=rat*k pset(x+j,y+k) pset(x+j,y-k) pset(x-j,y+k) pset(x-j,y-k) pset(x+k,y+j) pset(x+k,y-j) pset(x-k,y+j) pset(x-k,y-j) end pset(x,y-r) pset(x,y+r) pset(x-r,y) pset(x+r,y) end ```

(The magic scalar 0.785 draws a single octant, and then we mirror it everywhere.)

And BONUS -- a version of minskycircfill() that should remain fairly speedy even after the great rectfill correction:

 ```-- @musurca, @Felice, and @ultrabrite function minskycircfill(x,y,r,c) x,y=x+0.5,y+0.5 local j,k,rat=r,0,1/r poke(0x5f25,c) --set color for i=1,r*0.786 do k-=rat*j j+=rat*k rectfill(x+j,y+k,x+j,y-k) rectfill(x-j,y+k,x-j,y-k) rectfill(x-k,y-j,x-k,y+j) rectfill(x+k,y-j,x+k,y+j) end rectfill(x,y-r,x,y+r) end ```
P#44630 2017-09-26 06:44 ( Edited 2017-09-26 17:56)

[Please log in to post a comment]

About | Contact | Updates | Terms of Use
Generated 2019-08-24 00:55 | 0.080s | 4194k | Q:63