zzo38 wrote:
One algorithm I know for drawing (approximately) circles is Minsky's circle algorithm, which works like:
Code:
for(;;) {
y-=epsilon*x;
x+=epsilon*y;
plot(x,y);
}
The value
epsilon is less than one. If it is 1/256 then you do not need to implement multiplication/division; you can just use the carrying (you do not even need bit shifting). Note that these coordinates are signed numbers, which complicates the implementation a bit.
This is very interesting!
It seems that as epsilon gets larger, it becomes more elliptical, diagonally oblong. As epsilon gets smaller it becomes more circular.
At first glance it seems similar to just
rotating a 2D point, which is one of the "normal" ways to produce a circle:
Code:
ox = x;
oy = y;
a = cos(angle); // constant
b = sin(angle); // constant
x = a * ox - b * oy;
y = b * ox + a * oy;
But in your Minsky example only has one multiply, not two, and the way the Y update feeds back into the X update instead of using a temporary value makes the actual result kinda complicated to analyze. I feel like each iteration does like half of an approximation of the rotation somehow?
The speed of the rotation is dependent on epsilon, so probably you're limited to power-of-2-ish factors for epsilon unless you want a full generic multiply, but it does appear to be quite stable (I was testing it with 8.8 fixed point) and easy to control the radius because it stays on the circle you start X/Y on!
I wrote a simple
processing sketch to test it, attached below. Click the mouse to pick a starting point for X/Y, and press A/Z to adjust epsilon.