Minsky Circle Demo

Cart File | Forum Post |

	More cartridges by musurca

More Cartridges [View All]

 

Minsky Circle Demo

by musurca

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

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!

Nice! That's a huge optimization. Updated the demo to include a comparison between your minskydisc() and circfill(), as well as the token shavings.

This is super cool. Thank you so much for posting it. Bookmarked.

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.

It says "Press X" but it actually checks for the 'O' key!

RUINED!

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

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

@Felice: awesome!
the golden ratio always crops up for no reason ;)

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. ;)

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

Minsky Circle Thunderdome

by musurca

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

(And yes, I've swapped the keys to match Pico-8 convention. Thank you apLundell...)

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.

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