Computer Graphics Asked by Gusman on August 27, 2021
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
This morning I was thinking about how I would tackle the problem:
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:
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)
Answered by Ron Jensen on August 27, 2021
Get help from others!
Recent Answers
Recent Questions
© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP