# [Math] Drawing a circle, point-by-point, without floating point support

This might be interesting to implement in assembly for any of you assembly heads out there. The idea here is to use derivative calculus concepts to get the next point position instead of calculating sqrt which is slow.

https://yurichev.com/news/20220322_circle/

Here is the final non-naïve algorithm (in case the article goes away):

```function circle(x0, y0, radius)
{
// starting point:
var x = radius;
var y = 0;

var err = 0;

while (x >= y)
{
// main octant:
putPixel(x0 + x, y0 + y);
// copy octant 7 times:
putPixel(x0 + y, y0 + x);
putPixel(x0 - y, y0 + x);
putPixel(x0 - x, y0 + y);
putPixel(x0 - x, y0 - y);
putPixel(x0 - y, y0 - x);
putPixel(x0 + y, y0 - x);
putPixel(x0 + x, y0 - y);

// increase \$y\$ and update \$err\$
y += 1;
err += 2*y + 1;

// if \$err\$ is bigger than zero, decrease \$x\$ and update \$err\$ again
// we do this to maintain the equation x^2 + y^2 - r^2 = 0 (for integer arithmetic)
if (err > 0)
{
x -= 1;
err -= 2*x + 1;
}
}
};```

Just additions, subtractions and bit shifts.

Aangemeld of registreer om reacties te plaatsen

There is a Z80 asm implementation of this code hidden somewhere in the "Compass, the Finally Free Edition" package I did some testing with that algorithm using BASIC-kun. I made a loop which drew circles in SCREEN 5 from radius 1 to 60 with 15 colors, or 900 circles in total. It was considerably faster than BASIC's native CIRCLE:

BASIC-kun: 29,92 seconds
Native: 42,15 seconds

BASIC-kun managed to finish in just 71% of the time. Very impressive.

EDIT: @Grauw, yes, it is.

This is the technic I use in MSXgl in the `Draw_Circle()` function: https://github.com/aoineko-fr/MSXgl/blob/main/engine/src/draw.c
I used this article as a reference: https://ibancg.github.io/A-fast-circle-algorithm-for-ZX-Spec...

yes it is

The program at the top of the page seems to be the same as the one in the link here.

aoineko wrote:

I used this article as a reference: https://ibancg.github.io/A-fast-circle-algorithm-for-ZX-Spectrum/

In that article, it's already been said:

Quote:

The following algorithm is equivalent to the now known mid-point algorithm, but with different error formulation

Meaning that it's very similar to Bresenham's circle algorithm, but with different numbers. Even the speed is also comparable.

The only reason while that algorithm is seemingly faster than the Spectrum built-in version, is because the Spectrum's operating system chose to be optimising all their algorithms in size and not in speed, and their plotting algorithm is therefore a lot slower than the one you see there. Remember that the Spectrum ROM is only 16K in size so that they have much more memory for other more important things, like games.

Yes, even in 1982, the Spectrum already has the Bresenham Circle algorithm built in. And I would not be surprised that the MSX internally also uses the same function.

not sure about circle msx implementation. it also features arcs and ellipsis drawing, not sure if it is doable with a Bresenham's circle algorithm. Plus time ago i coded a Bresenham's circle algorithm in sdcc and it was more faster than msx basic one...