Log In  

Cart #44632 | 2017-09-26 | Code ▽ | Embed ▽ | License: CC4-BY-NC-SA
15

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)

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)

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)

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


(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)

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]

Follow Lexaloffle:          
Generated 2024-03-28 13:43:14 | 0.025s | Q:33