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

By pizzapower

Expert (72)

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.

ログイン/登録して投稿

By turbor

Champion (499)

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

By Grauw

Ascended (10604)

Grauw さんの画像

24-03-2022, 17:21

By Parn

Paladin (791)

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.

By aoineko

Champion (477)

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

By PingPong

Prophet (3898)

PingPong さんの画像

24-03-2022, 22:33

yes it is

By Timmy

Master (191)

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:

引用:

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.

By PingPong

Prophet (3898)

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