1
$\begingroup$

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
$\endgroup$
  • $\begingroup$ Here is a link to a related question: click me - In my answer, I also linked a tutorial. Maybe that helps. $\endgroup$ – wychmaster Jun 9 at 12:38
  • $\begingroup$ Have you considered working with 2D bounds for each quadrant? Generating those for every possible case will involve some logic (more than I have time to hash out in a full answer) but only simple integer math. $\endgroup$ – Olivier Jun 9 at 13:59
  • $\begingroup$ @Olivier Sorry, I don't understand, how would it help me to determine which pixels I must draw? $\endgroup$ – Gusman Jun 9 at 14:12
  • 1
    $\begingroup$ By only drawing the pixels inside the 2D bounds. Try splitting your circle in 4 quadrants. Draw a random arc on the circle. Now draw a tight box around the part of the arc in each quadrant. You'll see that you can fully define any arc that way. And the coordinates of the boxes all correspond to your circle center, center +/- radius or start/end point. You just need the logic to pick the right numbers for each case. $\endgroup$ – Olivier Jun 9 at 14:37
  • $\begingroup$ @Olivier Hmmm, ok, I think I start to understand it... I'm going to do some visual tests and see if I understood everything to code it. Thanks a lot! $\endgroup$ – Gusman Jun 9 at 14:42
0
$\begingroup$

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)

| improve this answer | |
$\endgroup$
  • $\begingroup$ Sorry if my question wasn't clear, I need to draw an arc, not a circle, a segment of the circle. I already have implemented the circle function using the Bresenham's algorithm using integer math and no square root nor floating point operations. I have the start point and end point of the arc in the circle and the problem I face is how to determine if a pixel of the circle belongs to the arc segment to draw it or skip it. As I state in the question the Bresenham's algorithm uses octants (like your answser) what makes difficult to determine it. $\endgroup$ – Gusman Jun 10 at 20:08
  • $\begingroup$ I'm thinking that for any two points on the circumference of a circle, you can draw a bounding rectangle that encloses the minor arc. You can use this bounding rectangle to mask the arc segment you want. E.g., if you want the minor arc, only plot points inside the rectangle and if you want the major arc, only plot points outside the rectangle. The only issue with this technique is if the points are on a diameter. Then a corner of your bounding rectangle will touch the circle. $\endgroup$ – Ron Jensen - We are all Monica Jun 11 at 0:21
  • $\begingroup$ More or less that's what I'm testing as Oliver already gave me the idea of using bounding boxes, but instead of many boxes only one per quadrant. $\endgroup$ – Gusman Jun 11 at 0:24
  • $\begingroup$ I came up with another, perhaps better, idea this morning. You can use arc lengths. Math nerds use radians to measure angles because radians directly correspond to arc lengths. For this problem we can measure arc length in pixels to be set and pixels to skip. I may work this up as an answer today if I get a chance. $\endgroup$ – Ron Jensen - We are all Monica Jun 11 at 15:47

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.