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

Par pizzapower

Master (172)

Portrait de pizzapower

24-03-2022, 16:29

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.

!login ou Inscrivez-vous pour poster

Par turbor

Hero (529)

Portrait de turbor

24-03-2022, 16:55

There is a Z80 asm implementation of this code hidden somewhere in the "Compass, the Finally Free Edition" package Wink

Par Grauw

Ascended (10821)

Portrait de Grauw

24-03-2022, 17:21

Par Parn

Paladin (854)

Portrait de Parn

24-03-2022, 18:14

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.

Par aoineko

Paragon (1140)

Portrait de aoineko

24-03-2022, 21:50

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

Par PingPong

Enlighted (4156)

Portrait de PingPong

24-03-2022, 22:33

yes it is

Par Timmy

Master (200)

Portrait de Timmy

25-03-2022, 11:55

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.

Par PingPong

Enlighted (4156)

Portrait de PingPong

26-03-2022, 09:22

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