Using Bresenham's circle algorithm (or another alternative algorithm) to draw an arc

Question

I'm trying to create some graphic functions for a ZX Spectrum (Z80) machine in assembler. I already have the basics except for the arc.

I need a fast algorithm to draw an arc, ideally one that uses integer or fixed point math.

I know there must be some way to draw an arc using the Bresenham's circle algorithm but I'm unable to find concrete info about it, there are sentences like "set the pixels only if they fall into the wanted interval" but I have no clue on how to determine if the pixels fall within it.

I only miss how to determine if a pixel lies in the arc, if the algorithm were completely linear (start at 0º and sweep to 360º) it would be easy to skip pixels until the start point and then continue drawing until the last point is reached, but the Bresenham's algorithm is drawn in octants simultaneously so I have no idea on how to do it. Also I had the idea to compute the circle's area in pixels and then divide 360 by the number of pixels to know how many degrees a pixel represents so I could use the start and end angle and check if a pixel must be drawn or not, but it does not work as the computed area is ideal and not the real one that Bresenham's algorithm generates.

As input data I have the circle's center and radius and the start and end points of the arc in the circle (I can derive the start and end angle from those, no problem), I'm not tied to anything so any other algorithm is welcome, no need to be specifically for the spectrum, just any assembler algorithm to draw an arc using integer or fixed point math will be enough even if I need different info (like the three point arc algorithm).

Cheers.

EDIT: I already have the circle's implementation, in C and assembler, I only need to determine what pixels of the circle belong to the arc to skip the ones that doesn't belong.

Here is the assembler implementation:

;--------------CIRCLE ROUTINE
; Plot function isn't included as it's very specific for the ZX Spectrum
;because of the way the video memory is mapped and it's irrelevant to the question

CENTER_X: .defb 0        ;Input parameter
CENTER_Y: .defb 0        ;Input parameter
RADII: .defb 0           ;Input parameter

CIRCLE_D: .defw 0        ;Temp variable
CIRCLE_D_SIGN: .defb 0   ;Temp variable


Draw_Circle:            ;D = X, E = Y

LD DE, 5
LD A, (RADII)
LD L, A
LD H, 0


OR A
ADD HL, HL 
ADD HL, HL
EX DE, HL
SBC HL, DE
JP P, POS_VAL
LD A, -1
LD (CIRCLE_D_SIGN), A

;NEG HL
xor a
sub l
ld l,a
sbc a,a
sub h
ld h,a


LD C, 4
CALL HL_Div_C

;NEG HL
xor a
sub l
ld l,a
sbc a,a
sub h
ld h,a

JR D_DONE
POS_VAL:
LD A, 1
LD (CIRCLE_D_SIGN), A
LD C, 4
CALL HL_Div_C
D_DONE:
LD (CIRCLE_D), HL


LD D, 0
LD A, (RADII)
LD E, A

CIRCLE_LOOP:

LD A, (CENTER_X)
LD H, A
LD A, (CENTER_Y)
LD L, A

;seq x.X/y.Y

LD A, H             ;center_x
ADD A, D                ;x
LD C, A             ;point_x
LD A, L             ;center_y
ADD A, E                ;y
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

LD A, H             ;center_x
ADD A, D                ;x
LD C, A             ;point_x
LD A, L             ;center_y
SUB A, E                ;y
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

LD A, H             ;center_x
SUB A, D                ;x
LD C, A             ;point_x
LD A, L             ;center_y
ADD A, E                ;y
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

LD A, H             ;center_x
SUB A, D                ;x
LD C, A             ;point_x
LD A, L             ;center_y
SUB A, E                ;y
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

;seq x.Y/y.X

LD A, H             ;center_x
ADD A, E                ;y
LD C, A             ;point_x
LD A, L             ;center_y
ADD A, D                ;x
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL


LD A, H             ;center_x
ADD A, E                ;y
LD C, A             ;point_x
LD A, L             ;center_y
SUB A, D                ;x
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

LD A, H             ;center_x
SUB A, E                ;y
LD C, A             ;point_x
LD A, L             ;center_y
ADD A, D                ;x
LD B, A             ;point_y

PUSH HL
PUSH DE
CALL Plot
POP DE
POP HL

LD A, H             ;center_x
SUB A, E                ;y
LD C, A             ;point_x
LD A, L             ;center_y
SUB A, D                ;x
LD B, A             ;point_y

PUSH DE
CALL Plot
POP DE


LD HL, (CIRCLE_D)               ;if (d < 0)
LD A, (CIRCLE_D_SIGN)
CP -1
JR Z, NEGATIVE_D



POSITIVE_D:                     ;no
PUSH DE
PUSH HL
LD L, D
LD H, 0
LD D, 0
XOR A
SBC HL, DE
ADD HL, HL
INC HL
POP DE
ADD HL, DE
POP DE

LD A, H                         ;is negative?
CP #FF
JP NZ, POS_VAL_POS
LD A, -1                        ;yes
LD (CIRCLE_D_SIGN), A
JP DEC_Y

POS_VAL_POS:                    ;no
LD A, 1
LD (CIRCLE_D_SIGN), A

DEC_Y:
DEC E
JP STORE_D

NEGATIVE_D:
PUSH HL
LD L, D
LD H,0
ADD HL, HL
INC HL

LD A, D                     ;2 * x
ADD A, A
INC A                       ; + 1

LD C, A
LD B, 0
POP HL
ADD HL, BC                  ;d = d +

LD A, H                     ;is negative?
CP #FF
JP NZ, POS_VAL_NEG

LD A, -1                    ;yes
LD (CIRCLE_D_SIGN), A
JP STORE_D

POS_VAL_NEG:
LD A, 1                 ;no
LD (CIRCLE_D_SIGN), A

STORE_D:
INC D
LD (CIRCLE_D), HL


TEST_LOOP:
LD A, E
CP D
JP P, CIRCLE_LOOP

RET

Answer 1

This morning I was thinking about how I would tackle the problem:

1. Draw a circle of radius R and origin (H, K)
2. Using integer math
3. No anti-aliasing
4. Speed is important

The first thing I noticed is if we assume (H, K) is (0,0), there is 8-way symmetry in the problem. That means if I find a pixel (x, y) between 0° and 45°, I already know 7 more pixel locations:

• pixel (x, y) is between 0° and 45°
• pixel (y, x) is between 45° and 90°
• pixel (-y, x) is between 90° and 135°
• pixel (-x, y) is between 135° and 180°
• pixel (-x, -y) is between 180° and 225°
• pixel (-y, -x) is between 225° and 270°
• pixel (y, -x) is between 270° and 315°
• pixel (x, -y) is between 315° and 360°

Because the tangent line to the circle between 0° and 45° has as slope less than -1, there is exactly 1 integer x value for any y value in that range. We find the x values for all $ y \in [0, \frac{\sqrt{2}}{2} R ]$, plot them using symmetry, and we're done.

In Python it the algorithm would look like this:

def circle(h, k, r):
    d=round( r* math.sqrt(2)/2 ) # find the 45 degree value
    r2=r**2 # square r
    p=r

    for y in range(0, d+1): 
#####   x=round(math.sqrt(r2 - y*y ))
        q=(r2-p*p-y*y)
        if( q < -p):
            p-=1
        x=p
        setPixel(h+x, k+y)
        setPixel(h+y, k+x)
        setPixel(h-y, k+x)
        setPixel(h-x, k+y)
        setPixel(h-x, k-y)
        setPixel(h-y, k-x)
        setPixel(h+y, k-x)
        setPixel(h+x, k-y)